| /* SCC value numbering for trees |
| Copyright (C) 2006-2019 Free Software Foundation, Inc. |
| Contributed by Daniel Berlin <dan@dberlin.org> |
| |
| This file is part of GCC. |
| |
| GCC is free software; you can redistribute it and/or modify |
| it under the terms of the GNU General Public License as published by |
| the Free Software Foundation; either version 3, or (at your option) |
| any later version. |
| |
| GCC is distributed in the hope that it will be useful, |
| but WITHOUT ANY WARRANTY; without even the implied warranty of |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| GNU General Public License for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with GCC; see the file COPYING3. If not see |
| <http://www.gnu.org/licenses/>. */ |
| |
| #include "config.h" |
| #include "system.h" |
| #include "coretypes.h" |
| #include "backend.h" |
| #include "rtl.h" |
| #include "tree.h" |
| #include "gimple.h" |
| #include "ssa.h" |
| #include "expmed.h" |
| #include "insn-config.h" |
| #include "memmodel.h" |
| #include "emit-rtl.h" |
| #include "cgraph.h" |
| #include "gimple-pretty-print.h" |
| #include "alias.h" |
| #include "fold-const.h" |
| #include "stor-layout.h" |
| #include "cfganal.h" |
| #include "tree-inline.h" |
| #include "internal-fn.h" |
| #include "gimple-fold.h" |
| #include "tree-eh.h" |
| #include "gimplify.h" |
| #include "flags.h" |
| #include "dojump.h" |
| #include "explow.h" |
| #include "calls.h" |
| #include "varasm.h" |
| #include "stmt.h" |
| #include "expr.h" |
| #include "tree-dfa.h" |
| #include "tree-ssa.h" |
| #include "dumpfile.h" |
| #include "cfgloop.h" |
| #include "params.h" |
| #include "tree-ssa-propagate.h" |
| #include "tree-cfg.h" |
| #include "domwalk.h" |
| #include "gimple-iterator.h" |
| #include "gimple-match.h" |
| #include "stringpool.h" |
| #include "attribs.h" |
| #include "tree-pass.h" |
| #include "statistics.h" |
| #include "langhooks.h" |
| #include "ipa-utils.h" |
| #include "dbgcnt.h" |
| #include "tree-cfgcleanup.h" |
| #include "tree-ssa-loop.h" |
| #include "tree-scalar-evolution.h" |
| #include "tree-ssa-loop-niter.h" |
| #include "builtins.h" |
| #include "tree-ssa-sccvn.h" |
| |
| /* This algorithm is based on the SCC algorithm presented by Keith |
| Cooper and L. Taylor Simpson in "SCC-Based Value numbering" |
| (http://citeseer.ist.psu.edu/41805.html). In |
| straight line code, it is equivalent to a regular hash based value |
| numbering that is performed in reverse postorder. |
| |
| For code with cycles, there are two alternatives, both of which |
| require keeping the hashtables separate from the actual list of |
| value numbers for SSA names. |
| |
| 1. Iterate value numbering in an RPO walk of the blocks, removing |
| all the entries from the hashtable after each iteration (but |
| keeping the SSA name->value number mapping between iterations). |
| Iterate until it does not change. |
| |
| 2. Perform value numbering as part of an SCC walk on the SSA graph, |
| iterating only the cycles in the SSA graph until they do not change |
| (using a separate, optimistic hashtable for value numbering the SCC |
| operands). |
| |
| The second is not just faster in practice (because most SSA graph |
| cycles do not involve all the variables in the graph), it also has |
| some nice properties. |
| |
| One of these nice properties is that when we pop an SCC off the |
| stack, we are guaranteed to have processed all the operands coming from |
| *outside of that SCC*, so we do not need to do anything special to |
| ensure they have value numbers. |
| |
| Another nice property is that the SCC walk is done as part of a DFS |
| of the SSA graph, which makes it easy to perform combining and |
| simplifying operations at the same time. |
| |
| The code below is deliberately written in a way that makes it easy |
| to separate the SCC walk from the other work it does. |
| |
| In order to propagate constants through the code, we track which |
| expressions contain constants, and use those while folding. In |
| theory, we could also track expressions whose value numbers are |
| replaced, in case we end up folding based on expression |
| identities. |
| |
| In order to value number memory, we assign value numbers to vuses. |
| This enables us to note that, for example, stores to the same |
| address of the same value from the same starting memory states are |
| equivalent. |
| TODO: |
| |
| 1. We can iterate only the changing portions of the SCC's, but |
| I have not seen an SCC big enough for this to be a win. |
| 2. If you differentiate between phi nodes for loops and phi nodes |
| for if-then-else, you can properly consider phi nodes in different |
| blocks for equivalence. |
| 3. We could value number vuses in more cases, particularly, whole |
| structure copies. |
| */ |
| |
| /* There's no BB_EXECUTABLE but we can use BB_VISITED. */ |
| #define BB_EXECUTABLE BB_VISITED |
| |
| static vn_lookup_kind default_vn_walk_kind; |
| |
| /* vn_nary_op hashtable helpers. */ |
| |
| struct vn_nary_op_hasher : nofree_ptr_hash <vn_nary_op_s> |
| { |
| typedef vn_nary_op_s *compare_type; |
| static inline hashval_t hash (const vn_nary_op_s *); |
| static inline bool equal (const vn_nary_op_s *, const vn_nary_op_s *); |
| }; |
| |
| /* Return the computed hashcode for nary operation P1. */ |
| |
| inline hashval_t |
| vn_nary_op_hasher::hash (const vn_nary_op_s *vno1) |
| { |
| return vno1->hashcode; |
| } |
| |
| /* Compare nary operations P1 and P2 and return true if they are |
| equivalent. */ |
| |
| inline bool |
| vn_nary_op_hasher::equal (const vn_nary_op_s *vno1, const vn_nary_op_s *vno2) |
| { |
| return vno1 == vno2 || vn_nary_op_eq (vno1, vno2); |
| } |
| |
| typedef hash_table<vn_nary_op_hasher> vn_nary_op_table_type; |
| typedef vn_nary_op_table_type::iterator vn_nary_op_iterator_type; |
| |
| |
| /* vn_phi hashtable helpers. */ |
| |
| static int |
| vn_phi_eq (const_vn_phi_t const vp1, const_vn_phi_t const vp2); |
| |
| struct vn_phi_hasher : nofree_ptr_hash <vn_phi_s> |
| { |
| static inline hashval_t hash (const vn_phi_s *); |
| static inline bool equal (const vn_phi_s *, const vn_phi_s *); |
| }; |
| |
| /* Return the computed hashcode for phi operation P1. */ |
| |
| inline hashval_t |
| vn_phi_hasher::hash (const vn_phi_s *vp1) |
| { |
| return vp1->hashcode; |
| } |
| |
| /* Compare two phi entries for equality, ignoring VN_TOP arguments. */ |
| |
| inline bool |
| vn_phi_hasher::equal (const vn_phi_s *vp1, const vn_phi_s *vp2) |
| { |
| return vp1 == vp2 || vn_phi_eq (vp1, vp2); |
| } |
| |
| typedef hash_table<vn_phi_hasher> vn_phi_table_type; |
| typedef vn_phi_table_type::iterator vn_phi_iterator_type; |
| |
| |
| /* Compare two reference operands P1 and P2 for equality. Return true if |
| they are equal, and false otherwise. */ |
| |
| static int |
| vn_reference_op_eq (const void *p1, const void *p2) |
| { |
| const_vn_reference_op_t const vro1 = (const_vn_reference_op_t) p1; |
| const_vn_reference_op_t const vro2 = (const_vn_reference_op_t) p2; |
| |
| return (vro1->opcode == vro2->opcode |
| /* We do not care for differences in type qualification. */ |
| && (vro1->type == vro2->type |
| || (vro1->type && vro2->type |
| && types_compatible_p (TYPE_MAIN_VARIANT (vro1->type), |
| TYPE_MAIN_VARIANT (vro2->type)))) |
| && expressions_equal_p (vro1->op0, vro2->op0) |
| && expressions_equal_p (vro1->op1, vro2->op1) |
| && expressions_equal_p (vro1->op2, vro2->op2)); |
| } |
| |
| /* Free a reference operation structure VP. */ |
| |
| static inline void |
| free_reference (vn_reference_s *vr) |
| { |
| vr->operands.release (); |
| } |
| |
| |
| /* vn_reference hashtable helpers. */ |
| |
| struct vn_reference_hasher : nofree_ptr_hash <vn_reference_s> |
| { |
| static inline hashval_t hash (const vn_reference_s *); |
| static inline bool equal (const vn_reference_s *, const vn_reference_s *); |
| }; |
| |
| /* Return the hashcode for a given reference operation P1. */ |
| |
| inline hashval_t |
| vn_reference_hasher::hash (const vn_reference_s *vr1) |
| { |
| return vr1->hashcode; |
| } |
| |
| inline bool |
| vn_reference_hasher::equal (const vn_reference_s *v, const vn_reference_s *c) |
| { |
| return v == c || vn_reference_eq (v, c); |
| } |
| |
| typedef hash_table<vn_reference_hasher> vn_reference_table_type; |
| typedef vn_reference_table_type::iterator vn_reference_iterator_type; |
| |
| |
| /* The set of VN hashtables. */ |
| |
| typedef struct vn_tables_s |
| { |
| vn_nary_op_table_type *nary; |
| vn_phi_table_type *phis; |
| vn_reference_table_type *references; |
| } *vn_tables_t; |
| |
| |
| /* vn_constant hashtable helpers. */ |
| |
| struct vn_constant_hasher : free_ptr_hash <vn_constant_s> |
| { |
| static inline hashval_t hash (const vn_constant_s *); |
| static inline bool equal (const vn_constant_s *, const vn_constant_s *); |
| }; |
| |
| /* Hash table hash function for vn_constant_t. */ |
| |
| inline hashval_t |
| vn_constant_hasher::hash (const vn_constant_s *vc1) |
| { |
| return vc1->hashcode; |
| } |
| |
| /* Hash table equality function for vn_constant_t. */ |
| |
| inline bool |
| vn_constant_hasher::equal (const vn_constant_s *vc1, const vn_constant_s *vc2) |
| { |
| if (vc1->hashcode != vc2->hashcode) |
| return false; |
| |
| return vn_constant_eq_with_type (vc1->constant, vc2->constant); |
| } |
| |
| static hash_table<vn_constant_hasher> *constant_to_value_id; |
| static bitmap constant_value_ids; |
| |
| |
| /* Obstack we allocate the vn-tables elements from. */ |
| static obstack vn_tables_obstack; |
| /* Special obstack we never unwind. */ |
| static obstack vn_tables_insert_obstack; |
| |
| static vn_reference_t last_inserted_ref; |
| static vn_phi_t last_inserted_phi; |
| static vn_nary_op_t last_inserted_nary; |
| |
| /* Valid hashtables storing information we have proven to be |
| correct. */ |
| static vn_tables_t valid_info; |
| |
| |
| /* Valueization hook. Valueize NAME if it is an SSA name, otherwise |
| just return it. */ |
| tree (*vn_valueize) (tree); |
| |
| |
| /* This represents the top of the VN lattice, which is the universal |
| value. */ |
| |
| tree VN_TOP; |
| |
| /* Unique counter for our value ids. */ |
| |
| static unsigned int next_value_id; |
| |
| |
| /* Table of vn_ssa_aux_t's, one per ssa_name. The vn_ssa_aux_t objects |
| are allocated on an obstack for locality reasons, and to free them |
| without looping over the vec. */ |
| |
| struct vn_ssa_aux_hasher : typed_noop_remove <vn_ssa_aux_t> |
| { |
| typedef vn_ssa_aux_t value_type; |
| typedef tree compare_type; |
| static inline hashval_t hash (const value_type &); |
| static inline bool equal (const value_type &, const compare_type &); |
| static inline void mark_deleted (value_type &) {} |
| static inline void mark_empty (value_type &e) { e = NULL; } |
| static inline bool is_deleted (value_type &) { return false; } |
| static inline bool is_empty (value_type &e) { return e == NULL; } |
| }; |
| |
| hashval_t |
| vn_ssa_aux_hasher::hash (const value_type &entry) |
| { |
| return SSA_NAME_VERSION (entry->name); |
| } |
| |
| bool |
| vn_ssa_aux_hasher::equal (const value_type &entry, const compare_type &name) |
| { |
| return name == entry->name; |
| } |
| |
| static hash_table<vn_ssa_aux_hasher> *vn_ssa_aux_hash; |
| typedef hash_table<vn_ssa_aux_hasher>::iterator vn_ssa_aux_iterator_type; |
| static struct obstack vn_ssa_aux_obstack; |
| |
| static vn_nary_op_t vn_nary_op_insert_stmt (gimple *, tree); |
| static unsigned int vn_nary_length_from_stmt (gimple *); |
| static vn_nary_op_t alloc_vn_nary_op_noinit (unsigned int, obstack *); |
| static vn_nary_op_t vn_nary_op_insert_into (vn_nary_op_t, |
| vn_nary_op_table_type *, bool); |
| static void init_vn_nary_op_from_stmt (vn_nary_op_t, gimple *); |
| static void init_vn_nary_op_from_pieces (vn_nary_op_t, unsigned int, |
| enum tree_code, tree, tree *); |
| static tree vn_lookup_simplify_result (gimple_match_op *); |
| |
| /* Return whether there is value numbering information for a given SSA name. */ |
| |
| bool |
| has_VN_INFO (tree name) |
| { |
| return vn_ssa_aux_hash->find_with_hash (name, SSA_NAME_VERSION (name)); |
| } |
| |
| vn_ssa_aux_t |
| VN_INFO (tree name) |
| { |
| vn_ssa_aux_t *res |
| = vn_ssa_aux_hash->find_slot_with_hash (name, SSA_NAME_VERSION (name), |
| INSERT); |
| if (*res != NULL) |
| return *res; |
| |
| vn_ssa_aux_t newinfo = *res = XOBNEW (&vn_ssa_aux_obstack, struct vn_ssa_aux); |
| memset (newinfo, 0, sizeof (struct vn_ssa_aux)); |
| newinfo->name = name; |
| newinfo->valnum = VN_TOP; |
| /* We are using the visited flag to handle uses with defs not within the |
| region being value-numbered. */ |
| newinfo->visited = false; |
| |
| /* Given we create the VN_INFOs on-demand now we have to do initialization |
| different than VN_TOP here. */ |
| if (SSA_NAME_IS_DEFAULT_DEF (name)) |
| switch (TREE_CODE (SSA_NAME_VAR (name))) |
| { |
| case VAR_DECL: |
| /* All undefined vars are VARYING. */ |
| newinfo->valnum = name; |
| newinfo->visited = true; |
| break; |
| |
| case PARM_DECL: |
| /* Parameters are VARYING but we can record a condition |
| if we know it is a non-NULL pointer. */ |
| newinfo->visited = true; |
| newinfo->valnum = name; |
| if (POINTER_TYPE_P (TREE_TYPE (name)) |
| && nonnull_arg_p (SSA_NAME_VAR (name))) |
| { |
| tree ops[2]; |
| ops[0] = name; |
| ops[1] = build_int_cst (TREE_TYPE (name), 0); |
| vn_nary_op_t nary; |
| /* Allocate from non-unwinding stack. */ |
| nary = alloc_vn_nary_op_noinit (2, &vn_tables_insert_obstack); |
| init_vn_nary_op_from_pieces (nary, 2, NE_EXPR, |
| boolean_type_node, ops); |
| nary->predicated_values = 0; |
| nary->u.result = boolean_true_node; |
| vn_nary_op_insert_into (nary, valid_info->nary, true); |
| gcc_assert (nary->unwind_to == NULL); |
| /* Also do not link it into the undo chain. */ |
| last_inserted_nary = nary->next; |
| nary->next = (vn_nary_op_t)(void *)-1; |
| nary = alloc_vn_nary_op_noinit (2, &vn_tables_insert_obstack); |
| init_vn_nary_op_from_pieces (nary, 2, EQ_EXPR, |
| boolean_type_node, ops); |
| nary->predicated_values = 0; |
| nary->u.result = boolean_false_node; |
| vn_nary_op_insert_into (nary, valid_info->nary, true); |
| gcc_assert (nary->unwind_to == NULL); |
| last_inserted_nary = nary->next; |
| nary->next = (vn_nary_op_t)(void *)-1; |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fprintf (dump_file, "Recording "); |
| print_generic_expr (dump_file, name, TDF_SLIM); |
| fprintf (dump_file, " != 0\n"); |
| } |
| } |
| break; |
| |
| case RESULT_DECL: |
| /* If the result is passed by invisible reference the default |
| def is initialized, otherwise it's uninitialized. Still |
| undefined is varying. */ |
| newinfo->visited = true; |
| newinfo->valnum = name; |
| break; |
| |
| default: |
| gcc_unreachable (); |
| } |
| return newinfo; |
| } |
| |
| /* Return the SSA value of X. */ |
| |
| inline tree |
| SSA_VAL (tree x, bool *visited = NULL) |
| { |
| vn_ssa_aux_t tem = vn_ssa_aux_hash->find_with_hash (x, SSA_NAME_VERSION (x)); |
| if (visited) |
| *visited = tem && tem->visited; |
| return tem && tem->visited ? tem->valnum : x; |
| } |
| |
| /* Return the SSA value of the VUSE x, supporting released VDEFs |
| during elimination which will value-number the VDEF to the |
| associated VUSE (but not substitute in the whole lattice). */ |
| |
| static inline tree |
| vuse_ssa_val (tree x) |
| { |
| if (!x) |
| return NULL_TREE; |
| |
| do |
| { |
| x = SSA_VAL (x); |
| gcc_assert (x != VN_TOP); |
| } |
| while (SSA_NAME_IN_FREE_LIST (x)); |
| |
| return x; |
| } |
| |
| /* Similar to the above but used as callback for walk_non_aliases_vuses |
| and thus should stop at unvisited VUSE to not walk across region |
| boundaries. */ |
| |
| static tree |
| vuse_valueize (tree vuse) |
| { |
| do |
| { |
| bool visited; |
| vuse = SSA_VAL (vuse, &visited); |
| if (!visited) |
| return NULL_TREE; |
| gcc_assert (vuse != VN_TOP); |
| } |
| while (SSA_NAME_IN_FREE_LIST (vuse)); |
| return vuse; |
| } |
| |
| |
| /* Return the vn_kind the expression computed by the stmt should be |
| associated with. */ |
| |
| enum vn_kind |
| vn_get_stmt_kind (gimple *stmt) |
| { |
| switch (gimple_code (stmt)) |
| { |
| case GIMPLE_CALL: |
| return VN_REFERENCE; |
| case GIMPLE_PHI: |
| return VN_PHI; |
| case GIMPLE_ASSIGN: |
| { |
| enum tree_code code = gimple_assign_rhs_code (stmt); |
| tree rhs1 = gimple_assign_rhs1 (stmt); |
| switch (get_gimple_rhs_class (code)) |
| { |
| case GIMPLE_UNARY_RHS: |
| case GIMPLE_BINARY_RHS: |
| case GIMPLE_TERNARY_RHS: |
| return VN_NARY; |
| case GIMPLE_SINGLE_RHS: |
| switch (TREE_CODE_CLASS (code)) |
| { |
| case tcc_reference: |
| /* VOP-less references can go through unary case. */ |
| if ((code == REALPART_EXPR |
| || code == IMAGPART_EXPR |
| || code == VIEW_CONVERT_EXPR |
| || code == BIT_FIELD_REF) |
| && (TREE_CODE (TREE_OPERAND (rhs1, 0)) == SSA_NAME |
| || is_gimple_min_invariant (TREE_OPERAND (rhs1, 0)))) |
| return VN_NARY; |
| |
| /* Fallthrough. */ |
| case tcc_declaration: |
| return VN_REFERENCE; |
| |
| case tcc_constant: |
| return VN_CONSTANT; |
| |
| default: |
| if (code == ADDR_EXPR) |
| return (is_gimple_min_invariant (rhs1) |
| ? VN_CONSTANT : VN_REFERENCE); |
| else if (code == CONSTRUCTOR) |
| return VN_NARY; |
| return VN_NONE; |
| } |
| default: |
| return VN_NONE; |
| } |
| } |
| default: |
| return VN_NONE; |
| } |
| } |
| |
| /* Lookup a value id for CONSTANT and return it. If it does not |
| exist returns 0. */ |
| |
| unsigned int |
| get_constant_value_id (tree constant) |
| { |
| vn_constant_s **slot; |
| struct vn_constant_s vc; |
| |
| vc.hashcode = vn_hash_constant_with_type (constant); |
| vc.constant = constant; |
| slot = constant_to_value_id->find_slot (&vc, NO_INSERT); |
| if (slot) |
| return (*slot)->value_id; |
| return 0; |
| } |
| |
| /* Lookup a value id for CONSTANT, and if it does not exist, create a |
| new one and return it. If it does exist, return it. */ |
| |
| unsigned int |
| get_or_alloc_constant_value_id (tree constant) |
| { |
| vn_constant_s **slot; |
| struct vn_constant_s vc; |
| vn_constant_t vcp; |
| |
| /* If the hashtable isn't initialized we're not running from PRE and thus |
| do not need value-ids. */ |
| if (!constant_to_value_id) |
| return 0; |
| |
| vc.hashcode = vn_hash_constant_with_type (constant); |
| vc.constant = constant; |
| slot = constant_to_value_id->find_slot (&vc, INSERT); |
| if (*slot) |
| return (*slot)->value_id; |
| |
| vcp = XNEW (struct vn_constant_s); |
| vcp->hashcode = vc.hashcode; |
| vcp->constant = constant; |
| vcp->value_id = get_next_value_id (); |
| *slot = vcp; |
| bitmap_set_bit (constant_value_ids, vcp->value_id); |
| return vcp->value_id; |
| } |
| |
| /* Return true if V is a value id for a constant. */ |
| |
| bool |
| value_id_constant_p (unsigned int v) |
| { |
| return bitmap_bit_p (constant_value_ids, v); |
| } |
| |
| /* Compute the hash for a reference operand VRO1. */ |
| |
| static void |
| vn_reference_op_compute_hash (const vn_reference_op_t vro1, inchash::hash &hstate) |
| { |
| hstate.add_int (vro1->opcode); |
| if (vro1->op0) |
| inchash::add_expr (vro1->op0, hstate); |
| if (vro1->op1) |
| inchash::add_expr (vro1->op1, hstate); |
| if (vro1->op2) |
| inchash::add_expr (vro1->op2, hstate); |
| } |
| |
| /* Compute a hash for the reference operation VR1 and return it. */ |
| |
| static hashval_t |
| vn_reference_compute_hash (const vn_reference_t vr1) |
| { |
| inchash::hash hstate; |
| hashval_t result; |
| int i; |
| vn_reference_op_t vro; |
| poly_int64 off = -1; |
| bool deref = false; |
| |
| FOR_EACH_VEC_ELT (vr1->operands, i, vro) |
| { |
| if (vro->opcode == MEM_REF) |
| deref = true; |
| else if (vro->opcode != ADDR_EXPR) |
| deref = false; |
| if (maybe_ne (vro->off, -1)) |
| { |
| if (known_eq (off, -1)) |
| off = 0; |
| off += vro->off; |
| } |
| else |
| { |
| if (maybe_ne (off, -1) |
| && maybe_ne (off, 0)) |
| hstate.add_poly_int (off); |
| off = -1; |
| if (deref |
| && vro->opcode == ADDR_EXPR) |
| { |
| if (vro->op0) |
| { |
| tree op = TREE_OPERAND (vro->op0, 0); |
| hstate.add_int (TREE_CODE (op)); |
| inchash::add_expr (op, hstate); |
| } |
| } |
| else |
| vn_reference_op_compute_hash (vro, hstate); |
| } |
| } |
| result = hstate.end (); |
| /* ??? We would ICE later if we hash instead of adding that in. */ |
| if (vr1->vuse) |
| result += SSA_NAME_VERSION (vr1->vuse); |
| |
| return result; |
| } |
| |
| /* Return true if reference operations VR1 and VR2 are equivalent. This |
| means they have the same set of operands and vuses. */ |
| |
| bool |
| vn_reference_eq (const_vn_reference_t const vr1, const_vn_reference_t const vr2) |
| { |
| unsigned i, j; |
| |
| /* Early out if this is not a hash collision. */ |
| if (vr1->hashcode != vr2->hashcode) |
| return false; |
| |
| /* The VOP needs to be the same. */ |
| if (vr1->vuse != vr2->vuse) |
| return false; |
| |
| /* If the operands are the same we are done. */ |
| if (vr1->operands == vr2->operands) |
| return true; |
| |
| if (!expressions_equal_p (TYPE_SIZE (vr1->type), TYPE_SIZE (vr2->type))) |
| return false; |
| |
| if (INTEGRAL_TYPE_P (vr1->type) |
| && INTEGRAL_TYPE_P (vr2->type)) |
| { |
| if (TYPE_PRECISION (vr1->type) != TYPE_PRECISION (vr2->type)) |
| return false; |
| } |
| else if (INTEGRAL_TYPE_P (vr1->type) |
| && (TYPE_PRECISION (vr1->type) |
| != TREE_INT_CST_LOW (TYPE_SIZE (vr1->type)))) |
| return false; |
| else if (INTEGRAL_TYPE_P (vr2->type) |
| && (TYPE_PRECISION (vr2->type) |
| != TREE_INT_CST_LOW (TYPE_SIZE (vr2->type)))) |
| return false; |
| |
| i = 0; |
| j = 0; |
| do |
| { |
| poly_int64 off1 = 0, off2 = 0; |
| vn_reference_op_t vro1, vro2; |
| vn_reference_op_s tem1, tem2; |
| bool deref1 = false, deref2 = false; |
| for (; vr1->operands.iterate (i, &vro1); i++) |
| { |
| if (vro1->opcode == MEM_REF) |
| deref1 = true; |
| /* Do not look through a storage order barrier. */ |
| else if (vro1->opcode == VIEW_CONVERT_EXPR && vro1->reverse) |
| return false; |
| if (known_eq (vro1->off, -1)) |
| break; |
| off1 += vro1->off; |
| } |
| for (; vr2->operands.iterate (j, &vro2); j++) |
| { |
| if (vro2->opcode == MEM_REF) |
| deref2 = true; |
| /* Do not look through a storage order barrier. */ |
| else if (vro2->opcode == VIEW_CONVERT_EXPR && vro2->reverse) |
| return false; |
| if (known_eq (vro2->off, -1)) |
| break; |
| off2 += vro2->off; |
| } |
| if (maybe_ne (off1, off2)) |
| return false; |
| if (deref1 && vro1->opcode == ADDR_EXPR) |
| { |
| memset (&tem1, 0, sizeof (tem1)); |
| tem1.op0 = TREE_OPERAND (vro1->op0, 0); |
| tem1.type = TREE_TYPE (tem1.op0); |
| tem1.opcode = TREE_CODE (tem1.op0); |
| vro1 = &tem1; |
| deref1 = false; |
| } |
| if (deref2 && vro2->opcode == ADDR_EXPR) |
| { |
| memset (&tem2, 0, sizeof (tem2)); |
| tem2.op0 = TREE_OPERAND (vro2->op0, 0); |
| tem2.type = TREE_TYPE (tem2.op0); |
| tem2.opcode = TREE_CODE (tem2.op0); |
| vro2 = &tem2; |
| deref2 = false; |
| } |
| if (deref1 != deref2) |
| return false; |
| if (!vn_reference_op_eq (vro1, vro2)) |
| return false; |
| ++j; |
| ++i; |
| } |
| while (vr1->operands.length () != i |
| || vr2->operands.length () != j); |
| |
| return true; |
| } |
| |
| /* Copy the operations present in load/store REF into RESULT, a vector of |
| vn_reference_op_s's. */ |
| |
| static void |
| copy_reference_ops_from_ref (tree ref, vec<vn_reference_op_s> *result) |
| { |
| if (TREE_CODE (ref) == TARGET_MEM_REF) |
| { |
| vn_reference_op_s temp; |
| |
| result->reserve (3); |
| |
| memset (&temp, 0, sizeof (temp)); |
| temp.type = TREE_TYPE (ref); |
| temp.opcode = TREE_CODE (ref); |
| temp.op0 = TMR_INDEX (ref); |
| temp.op1 = TMR_STEP (ref); |
| temp.op2 = TMR_OFFSET (ref); |
| temp.off = -1; |
| temp.clique = MR_DEPENDENCE_CLIQUE (ref); |
| temp.base = MR_DEPENDENCE_BASE (ref); |
| result->quick_push (temp); |
| |
| memset (&temp, 0, sizeof (temp)); |
| temp.type = NULL_TREE; |
| temp.opcode = ERROR_MARK; |
| temp.op0 = TMR_INDEX2 (ref); |
| temp.off = -1; |
| result->quick_push (temp); |
| |
| memset (&temp, 0, sizeof (temp)); |
| temp.type = NULL_TREE; |
| temp.opcode = TREE_CODE (TMR_BASE (ref)); |
| temp.op0 = TMR_BASE (ref); |
| temp.off = -1; |
| result->quick_push (temp); |
| return; |
| } |
| |
| /* For non-calls, store the information that makes up the address. */ |
| tree orig = ref; |
| while (ref) |
| { |
| vn_reference_op_s temp; |
| |
| memset (&temp, 0, sizeof (temp)); |
| temp.type = TREE_TYPE (ref); |
| temp.opcode = TREE_CODE (ref); |
| temp.off = -1; |
| |
| switch (temp.opcode) |
| { |
| case MODIFY_EXPR: |
| temp.op0 = TREE_OPERAND (ref, 1); |
| break; |
| case WITH_SIZE_EXPR: |
| temp.op0 = TREE_OPERAND (ref, 1); |
| temp.off = 0; |
| break; |
| case MEM_REF: |
| /* The base address gets its own vn_reference_op_s structure. */ |
| temp.op0 = TREE_OPERAND (ref, 1); |
| if (!mem_ref_offset (ref).to_shwi (&temp.off)) |
| temp.off = -1; |
| temp.clique = MR_DEPENDENCE_CLIQUE (ref); |
| temp.base = MR_DEPENDENCE_BASE (ref); |
| temp.reverse = REF_REVERSE_STORAGE_ORDER (ref); |
| break; |
| case BIT_FIELD_REF: |
| /* Record bits, position and storage order. */ |
| temp.op0 = TREE_OPERAND (ref, 1); |
| temp.op1 = TREE_OPERAND (ref, 2); |
| if (!multiple_p (bit_field_offset (ref), BITS_PER_UNIT, &temp.off)) |
| temp.off = -1; |
| temp.reverse = REF_REVERSE_STORAGE_ORDER (ref); |
| break; |
| case COMPONENT_REF: |
| /* The field decl is enough to unambiguously specify the field, |
| a matching type is not necessary and a mismatching type |
| is always a spurious difference. */ |
| temp.type = NULL_TREE; |
| temp.op0 = TREE_OPERAND (ref, 1); |
| temp.op1 = TREE_OPERAND (ref, 2); |
| { |
| tree this_offset = component_ref_field_offset (ref); |
| if (this_offset |
| && poly_int_tree_p (this_offset)) |
| { |
| tree bit_offset = DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref, 1)); |
| if (TREE_INT_CST_LOW (bit_offset) % BITS_PER_UNIT == 0) |
| { |
| poly_offset_int off |
| = (wi::to_poly_offset (this_offset) |
| + (wi::to_offset (bit_offset) >> LOG2_BITS_PER_UNIT)); |
| /* Probibit value-numbering zero offset components |
| of addresses the same before the pass folding |
| __builtin_object_size had a chance to run |
| (checking cfun->after_inlining does the |
| trick here). */ |
| if (TREE_CODE (orig) != ADDR_EXPR |
| || maybe_ne (off, 0) |
| || cfun->after_inlining) |
| off.to_shwi (&temp.off); |
| } |
| } |
| } |
| break; |
| case ARRAY_RANGE_REF: |
| case ARRAY_REF: |
| { |
| tree eltype = TREE_TYPE (TREE_TYPE (TREE_OPERAND (ref, 0))); |
| /* Record index as operand. */ |
| temp.op0 = TREE_OPERAND (ref, 1); |
| /* Always record lower bounds and element size. */ |
| temp.op1 = array_ref_low_bound (ref); |
| /* But record element size in units of the type alignment. */ |
| temp.op2 = TREE_OPERAND (ref, 3); |
| temp.align = eltype->type_common.align; |
| if (! temp.op2) |
| temp.op2 = size_binop (EXACT_DIV_EXPR, TYPE_SIZE_UNIT (eltype), |
| size_int (TYPE_ALIGN_UNIT (eltype))); |
| if (poly_int_tree_p (temp.op0) |
| && poly_int_tree_p (temp.op1) |
| && TREE_CODE (temp.op2) == INTEGER_CST) |
| { |
| poly_offset_int off = ((wi::to_poly_offset (temp.op0) |
| - wi::to_poly_offset (temp.op1)) |
| * wi::to_offset (temp.op2) |
| * vn_ref_op_align_unit (&temp)); |
| off.to_shwi (&temp.off); |
| } |
| } |
| break; |
| case VAR_DECL: |
| if (DECL_HARD_REGISTER (ref)) |
| { |
| temp.op0 = ref; |
| break; |
| } |
| /* Fallthru. */ |
| case PARM_DECL: |
| case CONST_DECL: |
| case RESULT_DECL: |
| /* Canonicalize decls to MEM[&decl] which is what we end up with |
| when valueizing MEM[ptr] with ptr = &decl. */ |
| temp.opcode = MEM_REF; |
| temp.op0 = build_int_cst (build_pointer_type (TREE_TYPE (ref)), 0); |
| temp.off = 0; |
| result->safe_push (temp); |
| temp.opcode = ADDR_EXPR; |
| temp.op0 = build1 (ADDR_EXPR, TREE_TYPE (temp.op0), ref); |
| temp.type = TREE_TYPE (temp.op0); |
| temp.off = -1; |
| break; |
| case STRING_CST: |
| case INTEGER_CST: |
| case COMPLEX_CST: |
| case VECTOR_CST: |
| case REAL_CST: |
| case FIXED_CST: |
| case CONSTRUCTOR: |
| case SSA_NAME: |
| temp.op0 = ref; |
| break; |
| case ADDR_EXPR: |
| if (is_gimple_min_invariant (ref)) |
| { |
| temp.op0 = ref; |
| break; |
| } |
| break; |
| /* These are only interesting for their operands, their |
| existence, and their type. They will never be the last |
| ref in the chain of references (IE they require an |
| operand), so we don't have to put anything |
| for op* as it will be handled by the iteration */ |
| case REALPART_EXPR: |
| temp.off = 0; |
| break; |
| case VIEW_CONVERT_EXPR: |
| temp.off = 0; |
| temp.reverse = storage_order_barrier_p (ref); |
| break; |
| case IMAGPART_EXPR: |
| /* This is only interesting for its constant offset. */ |
| temp.off = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (ref))); |
| break; |
| default: |
| gcc_unreachable (); |
| } |
| result->safe_push (temp); |
| |
| if (REFERENCE_CLASS_P (ref) |
| || TREE_CODE (ref) == MODIFY_EXPR |
| || TREE_CODE (ref) == WITH_SIZE_EXPR |
| || (TREE_CODE (ref) == ADDR_EXPR |
| && !is_gimple_min_invariant (ref))) |
| ref = TREE_OPERAND (ref, 0); |
| else |
| ref = NULL_TREE; |
| } |
| } |
| |
| /* Build a alias-oracle reference abstraction in *REF from the vn_reference |
| operands in *OPS, the reference alias set SET and the reference type TYPE. |
| Return true if something useful was produced. */ |
| |
| bool |
| ao_ref_init_from_vn_reference (ao_ref *ref, |
| alias_set_type set, tree type, |
| vec<vn_reference_op_s> ops) |
| { |
| vn_reference_op_t op; |
| unsigned i; |
| tree base = NULL_TREE; |
| tree *op0_p = &base; |
| poly_offset_int offset = 0; |
| poly_offset_int max_size; |
| poly_offset_int size = -1; |
| tree size_tree = NULL_TREE; |
| alias_set_type base_alias_set = -1; |
| |
| /* First get the final access size from just the outermost expression. */ |
| op = &ops[0]; |
| if (op->opcode == COMPONENT_REF) |
| size_tree = DECL_SIZE (op->op0); |
| else if (op->opcode == BIT_FIELD_REF) |
| size_tree = op->op0; |
| else |
| { |
| machine_mode mode = TYPE_MODE (type); |
| if (mode == BLKmode) |
| size_tree = TYPE_SIZE (type); |
| else |
| size = GET_MODE_BITSIZE (mode); |
| } |
| if (size_tree != NULL_TREE |
| && poly_int_tree_p (size_tree)) |
| size = wi::to_poly_offset (size_tree); |
| |
| /* Initially, maxsize is the same as the accessed element size. |
| In the following it will only grow (or become -1). */ |
| max_size = size; |
| |
| /* Compute cumulative bit-offset for nested component-refs and array-refs, |
| and find the ultimate containing object. */ |
| FOR_EACH_VEC_ELT (ops, i, op) |
| { |
| switch (op->opcode) |
| { |
| /* These may be in the reference ops, but we cannot do anything |
| sensible with them here. */ |
| case ADDR_EXPR: |
| /* Apart from ADDR_EXPR arguments to MEM_REF. */ |
| if (base != NULL_TREE |
| && TREE_CODE (base) == MEM_REF |
| && op->op0 |
| && DECL_P (TREE_OPERAND (op->op0, 0))) |
| { |
| vn_reference_op_t pop = &ops[i-1]; |
| base = TREE_OPERAND (op->op0, 0); |
| if (known_eq (pop->off, -1)) |
| { |
| max_size = -1; |
| offset = 0; |
| } |
| else |
| offset += pop->off * BITS_PER_UNIT; |
| op0_p = NULL; |
| break; |
| } |
| /* Fallthru. */ |
| case CALL_EXPR: |
| return false; |
| |
| /* Record the base objects. */ |
| case MEM_REF: |
| base_alias_set = get_deref_alias_set (op->op0); |
| *op0_p = build2 (MEM_REF, op->type, |
| NULL_TREE, op->op0); |
| MR_DEPENDENCE_CLIQUE (*op0_p) = op->clique; |
| MR_DEPENDENCE_BASE (*op0_p) = op->base; |
| op0_p = &TREE_OPERAND (*op0_p, 0); |
| break; |
| |
| case VAR_DECL: |
| case PARM_DECL: |
| case RESULT_DECL: |
| case SSA_NAME: |
| *op0_p = op->op0; |
| op0_p = NULL; |
| break; |
| |
| /* And now the usual component-reference style ops. */ |
| case BIT_FIELD_REF: |
| offset += wi::to_poly_offset (op->op1); |
| break; |
| |
| case COMPONENT_REF: |
| { |
| tree field = op->op0; |
| /* We do not have a complete COMPONENT_REF tree here so we |
| cannot use component_ref_field_offset. Do the interesting |
| parts manually. */ |
| tree this_offset = DECL_FIELD_OFFSET (field); |
| |
| if (op->op1 || !poly_int_tree_p (this_offset)) |
| max_size = -1; |
| else |
| { |
| poly_offset_int woffset = (wi::to_poly_offset (this_offset) |
| << LOG2_BITS_PER_UNIT); |
| woffset += wi::to_offset (DECL_FIELD_BIT_OFFSET (field)); |
| offset += woffset; |
| } |
| break; |
| } |
| |
| case ARRAY_RANGE_REF: |
| case ARRAY_REF: |
| /* We recorded the lower bound and the element size. */ |
| if (!poly_int_tree_p (op->op0) |
| || !poly_int_tree_p (op->op1) |
| || TREE_CODE (op->op2) != INTEGER_CST) |
| max_size = -1; |
| else |
| { |
| poly_offset_int woffset |
| = wi::sext (wi::to_poly_offset (op->op0) |
| - wi::to_poly_offset (op->op1), |
| TYPE_PRECISION (TREE_TYPE (op->op0))); |
| woffset *= wi::to_offset (op->op2) * vn_ref_op_align_unit (op); |
| woffset <<= LOG2_BITS_PER_UNIT; |
| offset += woffset; |
| } |
| break; |
| |
| case REALPART_EXPR: |
| break; |
| |
| case IMAGPART_EXPR: |
| offset += size; |
| break; |
| |
| case VIEW_CONVERT_EXPR: |
| break; |
| |
| case STRING_CST: |
| case INTEGER_CST: |
| case COMPLEX_CST: |
| case VECTOR_CST: |
| case REAL_CST: |
| case CONSTRUCTOR: |
| case CONST_DECL: |
| return false; |
| |
| default: |
| return false; |
| } |
| } |
| |
| if (base == NULL_TREE) |
| return false; |
| |
| ref->ref = NULL_TREE; |
| ref->base = base; |
| ref->ref_alias_set = set; |
| if (base_alias_set != -1) |
| ref->base_alias_set = base_alias_set; |
| else |
| ref->base_alias_set = get_alias_set (base); |
| /* We discount volatiles from value-numbering elsewhere. */ |
| ref->volatile_p = false; |
| |
| if (!size.to_shwi (&ref->size) || maybe_lt (ref->size, 0)) |
| { |
| ref->offset = 0; |
| ref->size = -1; |
| ref->max_size = -1; |
| return true; |
| } |
| |
| if (!offset.to_shwi (&ref->offset)) |
| { |
| ref->offset = 0; |
| ref->max_size = -1; |
| return true; |
| } |
| |
| if (!max_size.to_shwi (&ref->max_size) || maybe_lt (ref->max_size, 0)) |
| ref->max_size = -1; |
| |
| return true; |
| } |
| |
| /* Copy the operations present in load/store/call REF into RESULT, a vector of |
| vn_reference_op_s's. */ |
| |
| static void |
| copy_reference_ops_from_call (gcall *call, |
| vec<vn_reference_op_s> *result) |
| { |
| vn_reference_op_s temp; |
| unsigned i; |
| tree lhs = gimple_call_lhs (call); |
| int lr; |
| |
| /* If 2 calls have a different non-ssa lhs, vdef value numbers should be |
| different. By adding the lhs here in the vector, we ensure that the |
| hashcode is different, guaranteeing a different value number. */ |
| if (lhs && TREE_CODE (lhs) != SSA_NAME) |
| { |
| memset (&temp, 0, sizeof (temp)); |
| temp.opcode = MODIFY_EXPR; |
| temp.type = TREE_TYPE (lhs); |
| temp.op0 = lhs; |
| temp.off = -1; |
| result->safe_push (temp); |
| } |
| |
| /* Copy the type, opcode, function, static chain and EH region, if any. */ |
| memset (&temp, 0, sizeof (temp)); |
| temp.type = gimple_call_fntype (call); |
| temp.opcode = CALL_EXPR; |
| temp.op0 = gimple_call_fn (call); |
| temp.op1 = gimple_call_chain (call); |
| if (stmt_could_throw_p (cfun, call) && (lr = lookup_stmt_eh_lp (call)) > 0) |
| temp.op2 = size_int (lr); |
| temp.off = -1; |
| result->safe_push (temp); |
| |
| /* Copy the call arguments. As they can be references as well, |
| just chain them together. */ |
| for (i = 0; i < gimple_call_num_args (call); ++i) |
| { |
| tree callarg = gimple_call_arg (call, i); |
| copy_reference_ops_from_ref (callarg, result); |
| } |
| } |
| |
| /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates |
| *I_P to point to the last element of the replacement. */ |
| static bool |
| vn_reference_fold_indirect (vec<vn_reference_op_s> *ops, |
| unsigned int *i_p) |
| { |
| unsigned int i = *i_p; |
| vn_reference_op_t op = &(*ops)[i]; |
| vn_reference_op_t mem_op = &(*ops)[i - 1]; |
| tree addr_base; |
| poly_int64 addr_offset = 0; |
| |
| /* The only thing we have to do is from &OBJ.foo.bar add the offset |
| from .foo.bar to the preceding MEM_REF offset and replace the |
| address with &OBJ. */ |
| addr_base = get_addr_base_and_unit_offset (TREE_OPERAND (op->op0, 0), |
| &addr_offset); |
| gcc_checking_assert (addr_base && TREE_CODE (addr_base) != MEM_REF); |
| if (addr_base != TREE_OPERAND (op->op0, 0)) |
| { |
| poly_offset_int off |
| = (poly_offset_int::from (wi::to_poly_wide (mem_op->op0), |
| SIGNED) |
| + addr_offset); |
| mem_op->op0 = wide_int_to_tree (TREE_TYPE (mem_op->op0), off); |
| op->op0 = build_fold_addr_expr (addr_base); |
| if (tree_fits_shwi_p (mem_op->op0)) |
| mem_op->off = tree_to_shwi (mem_op->op0); |
| else |
| mem_op->off = -1; |
| return true; |
| } |
| return false; |
| } |
| |
| /* Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates |
| *I_P to point to the last element of the replacement. */ |
| static bool |
| vn_reference_maybe_forwprop_address (vec<vn_reference_op_s> *ops, |
| unsigned int *i_p) |
| { |
| bool changed = false; |
| vn_reference_op_t op; |
| |
| do |
| { |
| unsigned int i = *i_p; |
| op = &(*ops)[i]; |
| vn_reference_op_t mem_op = &(*ops)[i - 1]; |
| gimple *def_stmt; |
| enum tree_code code; |
| poly_offset_int off; |
| |
| def_stmt = SSA_NAME_DEF_STMT (op->op0); |
| if (!is_gimple_assign (def_stmt)) |
| return changed; |
| |
| code = gimple_assign_rhs_code (def_stmt); |
| if (code != ADDR_EXPR |
| && code != POINTER_PLUS_EXPR) |
| return changed; |
| |
| off = poly_offset_int::from (wi::to_poly_wide (mem_op->op0), SIGNED); |
| |
| /* The only thing we have to do is from &OBJ.foo.bar add the offset |
| from .foo.bar to the preceding MEM_REF offset and replace the |
| address with &OBJ. */ |
| if (code == ADDR_EXPR) |
| { |
| tree addr, addr_base; |
| poly_int64 addr_offset; |
| |
| addr = gimple_assign_rhs1 (def_stmt); |
| addr_base = get_addr_base_and_unit_offset (TREE_OPERAND (addr, 0), |
| &addr_offset); |
| /* If that didn't work because the address isn't invariant propagate |
| the reference tree from the address operation in case the current |
| dereference isn't offsetted. */ |
| if (!addr_base |
| && *i_p == ops->length () - 1 |
| && known_eq (off, 0) |
| /* This makes us disable this transform for PRE where the |
| reference ops might be also used for code insertion which |
| is invalid. */ |
| && default_vn_walk_kind == VN_WALKREWRITE) |
| { |
| auto_vec<vn_reference_op_s, 32> tem; |
| copy_reference_ops_from_ref (TREE_OPERAND (addr, 0), &tem); |
| /* Make sure to preserve TBAA info. The only objects not |
| wrapped in MEM_REFs that can have their address taken are |
| STRING_CSTs. */ |
| if (tem.length () >= 2 |
| && tem[tem.length () - 2].opcode == MEM_REF) |
| { |
| vn_reference_op_t new_mem_op = &tem[tem.length () - 2]; |
| new_mem_op->op0 |
| = wide_int_to_tree (TREE_TYPE (mem_op->op0), |
| wi::to_poly_wide (new_mem_op->op0)); |
| } |
| else |
| gcc_assert (tem.last ().opcode == STRING_CST); |
| ops->pop (); |
| ops->pop (); |
| ops->safe_splice (tem); |
| --*i_p; |
| return true; |
| } |
| if (!addr_base |
| || TREE_CODE (addr_base) != MEM_REF |
| || (TREE_CODE (TREE_OPERAND (addr_base, 0)) == SSA_NAME |
| && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND (addr_base, |
| 0)))) |
| return changed; |
| |
| off += addr_offset; |
| off += mem_ref_offset (addr_base); |
| op->op0 = TREE_OPERAND (addr_base, 0); |
| } |
| else |
| { |
| tree ptr, ptroff; |
| ptr = gimple_assign_rhs1 (def_stmt); |
| ptroff = gimple_assign_rhs2 (def_stmt); |
| if (TREE_CODE (ptr) != SSA_NAME |
| || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ptr) |
| /* Make sure to not endlessly recurse. |
| See gcc.dg/tree-ssa/20040408-1.c for an example. Can easily |
| happen when we value-number a PHI to its backedge value. */ |
| || SSA_VAL (ptr) == op->op0 |
| || !poly_int_tree_p (ptroff)) |
| return changed; |
| |
| off += wi::to_poly_offset (ptroff); |
| op->op0 = ptr; |
| } |
| |
| mem_op->op0 = wide_int_to_tree (TREE_TYPE (mem_op->op0), off); |
| if (tree_fits_shwi_p (mem_op->op0)) |
| mem_op->off = tree_to_shwi (mem_op->op0); |
| else |
| mem_op->off = -1; |
| /* ??? Can end up with endless recursion here!? |
| gcc.c-torture/execute/strcmp-1.c */ |
| if (TREE_CODE (op->op0) == SSA_NAME) |
| op->op0 = SSA_VAL (op->op0); |
| if (TREE_CODE (op->op0) != SSA_NAME) |
| op->opcode = TREE_CODE (op->op0); |
| |
| changed = true; |
| } |
| /* Tail-recurse. */ |
| while (TREE_CODE (op->op0) == SSA_NAME); |
| |
| /* Fold a remaining *&. */ |
| if (TREE_CODE (op->op0) == ADDR_EXPR) |
| vn_reference_fold_indirect (ops, i_p); |
| |
| return changed; |
| } |
| |
| /* Optimize the reference REF to a constant if possible or return |
| NULL_TREE if not. */ |
| |
| tree |
| fully_constant_vn_reference_p (vn_reference_t ref) |
| { |
| vec<vn_reference_op_s> operands = ref->operands; |
| vn_reference_op_t op; |
| |
| /* Try to simplify the translated expression if it is |
| a call to a builtin function with at most two arguments. */ |
| op = &operands[0]; |
| if (op->opcode == CALL_EXPR |
| && TREE_CODE (op->op0) == ADDR_EXPR |
| && TREE_CODE (TREE_OPERAND (op->op0, 0)) == FUNCTION_DECL |
| && fndecl_built_in_p (TREE_OPERAND (op->op0, 0)) |
| && operands.length () >= 2 |
| && operands.length () <= 3) |
| { |
| vn_reference_op_t arg0, arg1 = NULL; |
| bool anyconst = false; |
| arg0 = &operands[1]; |
| if (operands.length () > 2) |
| arg1 = &operands[2]; |
| if (TREE_CODE_CLASS (arg0->opcode) == tcc_constant |
| || (arg0->opcode == ADDR_EXPR |
| && is_gimple_min_invariant (arg0->op0))) |
| anyconst = true; |
| if (arg1 |
| && (TREE_CODE_CLASS (arg1->opcode) == tcc_constant |
| || (arg1->opcode == ADDR_EXPR |
| && is_gimple_min_invariant (arg1->op0)))) |
| anyconst = true; |
| if (anyconst) |
| { |
| tree folded = build_call_expr (TREE_OPERAND (op->op0, 0), |
| arg1 ? 2 : 1, |
| arg0->op0, |
| arg1 ? arg1->op0 : NULL); |
| if (folded |
| && TREE_CODE (folded) == NOP_EXPR) |
| folded = TREE_OPERAND (folded, 0); |
| if (folded |
| && is_gimple_min_invariant (folded)) |
| return folded; |
| } |
| } |
| |
| /* Simplify reads from constants or constant initializers. */ |
| else if (BITS_PER_UNIT == 8 |
| && COMPLETE_TYPE_P (ref->type) |
| && is_gimple_reg_type (ref->type)) |
| { |
| poly_int64 off = 0; |
| HOST_WIDE_INT size; |
| if (INTEGRAL_TYPE_P (ref->type)) |
| size = TYPE_PRECISION (ref->type); |
| else if (tree_fits_shwi_p (TYPE_SIZE (ref->type))) |
| size = tree_to_shwi (TYPE_SIZE (ref->type)); |
| else |
| return NULL_TREE; |
| if (size % BITS_PER_UNIT != 0 |
| || size > MAX_BITSIZE_MODE_ANY_MODE) |
| return NULL_TREE; |
| size /= BITS_PER_UNIT; |
| unsigned i; |
| for (i = 0; i < operands.length (); ++i) |
| { |
| if (TREE_CODE_CLASS (operands[i].opcode) == tcc_constant) |
| { |
| ++i; |
| break; |
| } |
| if (known_eq (operands[i].off, -1)) |
| return NULL_TREE; |
| off += operands[i].off; |
| if (operands[i].opcode == MEM_REF) |
| { |
| ++i; |
| break; |
| } |
| } |
| vn_reference_op_t base = &operands[--i]; |
| tree ctor = error_mark_node; |
| tree decl = NULL_TREE; |
| if (TREE_CODE_CLASS (base->opcode) == tcc_constant) |
| ctor = base->op0; |
| else if (base->opcode == MEM_REF |
| && base[1].opcode == ADDR_EXPR |
| && (TREE_CODE (TREE_OPERAND (base[1].op0, 0)) == VAR_DECL |
| || TREE_CODE (TREE_OPERAND (base[1].op0, 0)) == CONST_DECL |
| || TREE_CODE (TREE_OPERAND (base[1].op0, 0)) == STRING_CST)) |
| { |
| decl = TREE_OPERAND (base[1].op0, 0); |
| if (TREE_CODE (decl) == STRING_CST) |
| ctor = decl; |
| else |
| ctor = ctor_for_folding (decl); |
| } |
| if (ctor == NULL_TREE) |
| return build_zero_cst (ref->type); |
| else if (ctor != error_mark_node) |
| { |
| HOST_WIDE_INT const_off; |
| if (decl) |
| { |
| tree res = fold_ctor_reference (ref->type, ctor, |
| off * BITS_PER_UNIT, |
| size * BITS_PER_UNIT, decl); |
| if (res) |
| { |
| STRIP_USELESS_TYPE_CONVERSION (res); |
| if (is_gimple_min_invariant (res)) |
| return res; |
| } |
| } |
| else if (off.is_constant (&const_off)) |
| { |
| unsigned char buf[MAX_BITSIZE_MODE_ANY_MODE / BITS_PER_UNIT]; |
| int len = native_encode_expr (ctor, buf, size, const_off); |
| if (len > 0) |
| return native_interpret_expr (ref->type, buf, len); |
| } |
| } |
| } |
| |
| return NULL_TREE; |
| } |
| |
| /* Return true if OPS contain a storage order barrier. */ |
| |
| static bool |
| contains_storage_order_barrier_p (vec<vn_reference_op_s> ops) |
| { |
| vn_reference_op_t op; |
| unsigned i; |
| |
| FOR_EACH_VEC_ELT (ops, i, op) |
| if (op->opcode == VIEW_CONVERT_EXPR && op->reverse) |
| return true; |
| |
| return false; |
| } |
| |
| /* Transform any SSA_NAME's in a vector of vn_reference_op_s |
| structures into their value numbers. This is done in-place, and |
| the vector passed in is returned. *VALUEIZED_ANYTHING will specify |
| whether any operands were valueized. */ |
| |
| static vec<vn_reference_op_s> |
| valueize_refs_1 (vec<vn_reference_op_s> orig, bool *valueized_anything, |
| bool with_avail = false) |
| { |
| vn_reference_op_t vro; |
| unsigned int i; |
| |
| *valueized_anything = false; |
| |
| FOR_EACH_VEC_ELT (orig, i, vro) |
| { |
| if (vro->opcode == SSA_NAME |
| || (vro->op0 && TREE_CODE (vro->op0) == SSA_NAME)) |
| { |
| tree tem = with_avail ? vn_valueize (vro->op0) : SSA_VAL (vro->op0); |
| if (tem != vro->op0) |
| { |
| *valueized_anything = true; |
| vro->op0 = tem; |
| } |
| /* If it transforms from an SSA_NAME to a constant, update |
| the opcode. */ |
| if (TREE_CODE (vro->op0) != SSA_NAME && vro->opcode == SSA_NAME) |
| vro->opcode = TREE_CODE (vro->op0); |
| } |
| if (vro->op1 && TREE_CODE (vro->op1) == SSA_NAME) |
| { |
| tree tem = with_avail ? vn_valueize (vro->op1) : SSA_VAL (vro->op1); |
| if (tem != vro->op1) |
| { |
| *valueized_anything = true; |
| vro->op1 = tem; |
| } |
| } |
| if (vro->op2 && TREE_CODE (vro->op2) == SSA_NAME) |
| { |
| tree tem = with_avail ? vn_valueize (vro->op2) : SSA_VAL (vro->op2); |
| if (tem != vro->op2) |
| { |
| *valueized_anything = true; |
| vro->op2 = tem; |
| } |
| } |
| /* If it transforms from an SSA_NAME to an address, fold with |
| a preceding indirect reference. */ |
| if (i > 0 |
| && vro->op0 |
| && TREE_CODE (vro->op0) == ADDR_EXPR |
| && orig[i - 1].opcode == MEM_REF) |
| { |
| if (vn_reference_fold_indirect (&orig, &i)) |
| *valueized_anything = true; |
| } |
| else if (i > 0 |
| && vro->opcode == SSA_NAME |
| && orig[i - 1].opcode == MEM_REF) |
| { |
| if (vn_reference_maybe_forwprop_address (&orig, &i)) |
| *valueized_anything = true; |
| } |
| /* If it transforms a non-constant ARRAY_REF into a constant |
| one, adjust the constant offset. */ |
| else if (vro->opcode == ARRAY_REF |
| && known_eq (vro->off, -1) |
| && poly_int_tree_p (vro->op0) |
| && poly_int_tree_p (vro->op1) |
| && TREE_CODE (vro->op2) == INTEGER_CST) |
| { |
| poly_offset_int off = ((wi::to_poly_offset (vro->op0) |
| - wi::to_poly_offset (vro->op1)) |
| * wi::to_offset (vro->op2) |
| * vn_ref_op_align_unit (vro)); |
| off.to_shwi (&vro->off); |
| } |
| } |
| |
| return orig; |
| } |
| |
| static vec<vn_reference_op_s> |
| valueize_refs (vec<vn_reference_op_s> orig) |
| { |
| bool tem; |
| return valueize_refs_1 (orig, &tem); |
| } |
| |
| static vec<vn_reference_op_s> shared_lookup_references; |
| |
| /* Create a vector of vn_reference_op_s structures from REF, a |
| REFERENCE_CLASS_P tree. The vector is shared among all callers of |
| this function. *VALUEIZED_ANYTHING will specify whether any |
| operands were valueized. */ |
| |
| static vec<vn_reference_op_s> |
| valueize_shared_reference_ops_from_ref (tree ref, bool *valueized_anything) |
| { |
| if (!ref) |
| return vNULL; |
| shared_lookup_references.truncate (0); |
| copy_reference_ops_from_ref (ref, &shared_lookup_references); |
| shared_lookup_references = valueize_refs_1 (shared_lookup_references, |
| valueized_anything); |
| return shared_lookup_references; |
| } |
| |
| /* Create a vector of vn_reference_op_s structures from CALL, a |
| call statement. The vector is shared among all callers of |
| this function. */ |
| |
| static vec<vn_reference_op_s> |
| valueize_shared_reference_ops_from_call (gcall *call) |
| { |
| if (!call) |
| return vNULL; |
| shared_lookup_references.truncate (0); |
| copy_reference_ops_from_call (call, &shared_lookup_references); |
| shared_lookup_references = valueize_refs (shared_lookup_references); |
| return shared_lookup_references; |
| } |
| |
| /* Lookup a SCCVN reference operation VR in the current hash table. |
| Returns the resulting value number if it exists in the hash table, |
| NULL_TREE otherwise. VNRESULT will be filled in with the actual |
| vn_reference_t stored in the hashtable if something is found. */ |
| |
| static tree |
| vn_reference_lookup_1 (vn_reference_t vr, vn_reference_t *vnresult) |
| { |
| vn_reference_s **slot; |
| hashval_t hash; |
| |
| hash = vr->hashcode; |
| slot = valid_info->references->find_slot_with_hash (vr, hash, NO_INSERT); |
| if (slot) |
| { |
| if (vnresult) |
| *vnresult = (vn_reference_t)*slot; |
| return ((vn_reference_t)*slot)->result; |
| } |
| |
| return NULL_TREE; |
| } |
| |
| struct vn_walk_cb_data |
| { |
| vn_walk_cb_data (vn_reference_t vr_, tree *last_vuse_ptr_, |
| vn_lookup_kind vn_walk_kind_, bool tbaa_p_) |
| : vr (vr_), last_vuse_ptr (last_vuse_ptr_), vn_walk_kind (vn_walk_kind_), |
| tbaa_p (tbaa_p_) |
| {} |
| |
| vn_reference_t vr; |
| tree *last_vuse_ptr; |
| vn_lookup_kind vn_walk_kind; |
| bool tbaa_p; |
| }; |
| |
| /* Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_ |
| with the current VUSE and performs the expression lookup. */ |
| |
| static void * |
| vn_reference_lookup_2 (ao_ref *op ATTRIBUTE_UNUSED, tree vuse, void *data_) |
| { |
| vn_walk_cb_data *data = (vn_walk_cb_data *)data_; |
| vn_reference_t vr = data->vr; |
| vn_reference_s **slot; |
| hashval_t hash; |
| |
| if (data->last_vuse_ptr) |
| *data->last_vuse_ptr = vuse; |
| |
| /* Fixup vuse and hash. */ |
| if (vr->vuse) |
| vr->hashcode = vr->hashcode - SSA_NAME_VERSION (vr->vuse); |
| vr->vuse = vuse_ssa_val (vuse); |
| if (vr->vuse) |
| vr->hashcode = vr->hashcode + SSA_NAME_VERSION (vr->vuse); |
| |
| hash = vr->hashcode; |
| slot = valid_info->references->find_slot_with_hash (vr, hash, NO_INSERT); |
| if (slot) |
| return *slot; |
| |
| return NULL; |
| } |
| |
| /* Lookup an existing or insert a new vn_reference entry into the |
| value table for the VUSE, SET, TYPE, OPERANDS reference which |
| has the value VALUE which is either a constant or an SSA name. */ |
| |
| static vn_reference_t |
| vn_reference_lookup_or_insert_for_pieces (tree vuse, |
| alias_set_type set, |
| tree type, |
| vec<vn_reference_op_s, |
| va_heap> operands, |
| tree value) |
| { |
| vn_reference_s vr1; |
| vn_reference_t result; |
| unsigned value_id; |
| vr1.vuse = vuse ? SSA_VAL (vuse) : NULL_TREE; |
| vr1.operands = operands; |
| vr1.type = type; |
| vr1.set = set; |
| vr1.hashcode = vn_reference_compute_hash (&vr1); |
| if (vn_reference_lookup_1 (&vr1, &result)) |
| return result; |
| if (TREE_CODE (value) == SSA_NAME) |
| value_id = VN_INFO (value)->value_id; |
| else |
| value_id = get_or_alloc_constant_value_id (value); |
| return vn_reference_insert_pieces (vuse, set, type, |
| operands.copy (), value, value_id); |
| } |
| |
| /* Return a value-number for RCODE OPS... either by looking up an existing |
| value-number for the simplified result or by inserting the operation if |
| INSERT is true. */ |
| |
| static tree |
| vn_nary_build_or_lookup_1 (gimple_match_op *res_op, bool insert) |
| { |
| tree result = NULL_TREE; |
| /* We will be creating a value number for |
| RCODE (OPS...). |
| So first simplify and lookup this expression to see if it |
| is already available. */ |
| mprts_hook = vn_lookup_simplify_result; |
| bool res = false; |
| switch (TREE_CODE_LENGTH ((tree_code) res_op->code)) |
| { |
| case 1: |
| res = gimple_resimplify1 (NULL, res_op, vn_valueize); |
| break; |
| case 2: |
| res = gimple_resimplify2 (NULL, res_op, vn_valueize); |
| break; |
| case 3: |
| res = gimple_resimplify3 (NULL, res_op, vn_valueize); |
| break; |
| } |
| mprts_hook = NULL; |
| gimple *new_stmt = NULL; |
| if (res |
| && gimple_simplified_result_is_gimple_val (res_op)) |
| { |
| /* The expression is already available. */ |
| result = res_op->ops[0]; |
| /* Valueize it, simplification returns sth in AVAIL only. */ |
| if (TREE_CODE (result) == SSA_NAME) |
| result = SSA_VAL (result); |
| } |
| else |
| { |
| tree val = vn_lookup_simplify_result (res_op); |
| if (!val && insert) |
| { |
| gimple_seq stmts = NULL; |
| result = maybe_push_res_to_seq (res_op, &stmts); |
| if (result) |
| { |
| gcc_assert (gimple_seq_singleton_p (stmts)); |
| new_stmt = gimple_seq_first_stmt (stmts); |
| } |
| } |
| else |
| /* The expression is already available. */ |
| result = val; |
| } |
| if (new_stmt) |
| { |
| /* The expression is not yet available, value-number lhs to |
| the new SSA_NAME we created. */ |
| /* Initialize value-number information properly. */ |
| vn_ssa_aux_t result_info = VN_INFO (result); |
| result_info->valnum = result; |
| result_info->value_id = get_next_value_id (); |
| result_info->visited = 1; |
| gimple_seq_add_stmt_without_update (&VN_INFO (result)->expr, |
| new_stmt); |
| result_info->needs_insertion = true; |
| /* ??? PRE phi-translation inserts NARYs without corresponding |
| SSA name result. Re-use those but set their result according |
| to the stmt we just built. */ |
| vn_nary_op_t nary = NULL; |
| vn_nary_op_lookup_stmt (new_stmt, &nary); |
| if (nary) |
| { |
| gcc_assert (! nary->predicated_values && nary->u.result == NULL_TREE); |
| nary->u.result = gimple_assign_lhs (new_stmt); |
| } |
| /* As all "inserted" statements are singleton SCCs, insert |
| to the valid table. This is strictly needed to |
| avoid re-generating new value SSA_NAMEs for the same |
| expression during SCC iteration over and over (the |
| optimistic table gets cleared after each iteration). |
| We do not need to insert into the optimistic table, as |
| lookups there will fall back to the valid table. */ |
| else |
| { |
| unsigned int length = vn_nary_length_from_stmt (new_stmt); |
| vn_nary_op_t vno1 |
| = alloc_vn_nary_op_noinit (length, &vn_tables_insert_obstack); |
| vno1->value_id = result_info->value_id; |
| vno1->length = length; |
| vno1->predicated_values = 0; |
| vno1->u.result = result; |
| init_vn_nary_op_from_stmt (vno1, new_stmt); |
| vn_nary_op_insert_into (vno1, valid_info->nary, true); |
| /* Also do not link it into the undo chain. */ |
| last_inserted_nary = vno1->next; |
| vno1->next = (vn_nary_op_t)(void *)-1; |
| } |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fprintf (dump_file, "Inserting name "); |
| print_generic_expr (dump_file, result); |
| fprintf (dump_file, " for expression "); |
| print_gimple_expr (dump_file, new_stmt, 0, TDF_SLIM); |
| fprintf (dump_file, "\n"); |
| } |
| } |
| return result; |
| } |
| |
| /* Return a value-number for RCODE OPS... either by looking up an existing |
| value-number for the simplified result or by inserting the operation. */ |
| |
| static tree |
| vn_nary_build_or_lookup (gimple_match_op *res_op) |
| { |
| return vn_nary_build_or_lookup_1 (res_op, true); |
| } |
| |
| /* Try to simplify the expression RCODE OPS... of type TYPE and return |
| its value if present. */ |
| |
| tree |
| vn_nary_simplify (vn_nary_op_t nary) |
| { |
| if (nary->length > gimple_match_op::MAX_NUM_OPS) |
| return NULL_TREE; |
| gimple_match_op op (gimple_match_cond::UNCOND, nary->opcode, |
| nary->type, nary->length); |
| memcpy (op.ops, nary->op, sizeof (tree) * nary->length); |
| return vn_nary_build_or_lookup_1 (&op, false); |
| } |
| |
| /* Elimination engine. */ |
| |
| class eliminate_dom_walker : public dom_walker |
| { |
| public: |
| eliminate_dom_walker (cdi_direction, bitmap); |
| ~eliminate_dom_walker (); |
| |
| virtual edge before_dom_children (basic_block); |
| virtual void after_dom_children (basic_block); |
| |
| virtual tree eliminate_avail (basic_block, tree op); |
| virtual void eliminate_push_avail (basic_block, tree op); |
| tree eliminate_insert (basic_block, gimple_stmt_iterator *gsi, tree val); |
| |
| void eliminate_stmt (basic_block, gimple_stmt_iterator *); |
| |
| unsigned eliminate_cleanup (bool region_p = false); |
| |
| bool do_pre; |
| unsigned int el_todo; |
| unsigned int eliminations; |
| unsigned int insertions; |
| |
| /* SSA names that had their defs inserted by PRE if do_pre. */ |
| bitmap inserted_exprs; |
| |
| /* Blocks with statements that have had their EH properties changed. */ |
| bitmap need_eh_cleanup; |
| |
| /* Blocks with statements that have had their AB properties changed. */ |
| bitmap need_ab_cleanup; |
| |
| /* Local state for the eliminate domwalk. */ |
| auto_vec<gimple *> to_remove; |
| auto_vec<gimple *> to_fixup; |
| auto_vec<tree> avail; |
| auto_vec<tree> avail_stack; |
| }; |
| |
| /* Adaptor to the elimination engine using RPO availability. */ |
| |
| class rpo_elim : public eliminate_dom_walker |
| { |
| public: |
| rpo_elim(basic_block entry_) |
| : eliminate_dom_walker (CDI_DOMINATORS, NULL), entry (entry_) {} |
| ~rpo_elim(); |
| |
| virtual tree eliminate_avail (basic_block, tree op); |
| |
| virtual void eliminate_push_avail (basic_block, tree); |
| |
| basic_block entry; |
| /* Instead of having a local availability lattice for each |
| basic-block and availability at X defined as union of |
| the local availabilities at X and its dominators we're |
| turning this upside down and track availability per |
| value given values are usually made available at very |
| few points (at least one). |
| So we have a value -> vec<location, leader> map where |
| LOCATION is specifying the basic-block LEADER is made |
| available for VALUE. We push to this vector in RPO |
| order thus for iteration we can simply pop the last |
| entries. |
| LOCATION is the basic-block index and LEADER is its |
| SSA name version. */ |
| /* ??? We'd like to use auto_vec here with embedded storage |
| but that doesn't play well until we can provide move |
| constructors and use std::move on hash-table expansion. |
| So for now this is a bit more expensive than necessary. |
| We eventually want to switch to a chaining scheme like |
| for hashtable entries for unwinding which would make |
| making the vector part of the vn_ssa_aux structure possible. */ |
| typedef hash_map<tree, vec<std::pair<int, int> > > rpo_avail_t; |
| rpo_avail_t m_rpo_avail; |
| }; |
| |
| /* Global RPO state for access from hooks. */ |
| static rpo_elim *rpo_avail; |
| basic_block vn_context_bb; |
| |
| /* Callback for walk_non_aliased_vuses. Tries to perform a lookup |
| from the statement defining VUSE and if not successful tries to |
| translate *REFP and VR_ through an aggregate copy at the definition |
| of VUSE. If *DISAMBIGUATE_ONLY is true then do not perform translation |
| of *REF and *VR. If only disambiguation was performed then |
| *DISAMBIGUATE_ONLY is set to true. */ |
| |
| static void * |
| vn_reference_lookup_3 (ao_ref *ref, tree vuse, void *data_, |
| bool *disambiguate_only) |
| { |
| vn_walk_cb_data *data = (vn_walk_cb_data *)data_; |
| vn_reference_t vr = data->vr; |
| gimple *def_stmt = SSA_NAME_DEF_STMT (vuse); |
| tree base = ao_ref_base (ref); |
| HOST_WIDE_INT offseti, maxsizei; |
| static vec<vn_reference_op_s> lhs_ops; |
| ao_ref lhs_ref; |
| bool lhs_ref_ok = false; |
| poly_int64 copy_size; |
| |
| /* First try to disambiguate after value-replacing in the definitions LHS. */ |
| if (is_gimple_assign (def_stmt)) |
| { |
| tree lhs = gimple_assign_lhs (def_stmt); |
| bool valueized_anything = false; |
| /* Avoid re-allocation overhead. */ |
| lhs_ops.truncate (0); |
| basic_block saved_rpo_bb = vn_context_bb; |
| vn_context_bb = gimple_bb (def_stmt); |
| copy_reference_ops_from_ref (lhs, &lhs_ops); |
| lhs_ops = valueize_refs_1 (lhs_ops, &valueized_anything, true); |
| vn_context_bb = saved_rpo_bb; |
| if (valueized_anything) |
| { |
| lhs_ref_ok = ao_ref_init_from_vn_reference (&lhs_ref, |
| get_alias_set (lhs), |
| TREE_TYPE (lhs), lhs_ops); |
| if (lhs_ref_ok |
| && !refs_may_alias_p_1 (ref, &lhs_ref, data->tbaa_p)) |
| { |
| *disambiguate_only = true; |
| return NULL; |
| } |
| } |
| else |
| { |
| ao_ref_init (&lhs_ref, lhs); |
| lhs_ref_ok = true; |
| } |
| |
| /* If we reach a clobbering statement try to skip it and see if |
| we find a VN result with exactly the same value as the |
| possible clobber. In this case we can ignore the clobber |
| and return the found value. */ |
| if (data->vn_walk_kind == VN_WALKREWRITE |
| && is_gimple_reg_type (TREE_TYPE (lhs)) |
| && types_compatible_p (TREE_TYPE (lhs), vr->type) |
| && ref->ref) |
| { |
| tree *saved_last_vuse_ptr = data->last_vuse_ptr; |
| /* Do not update last_vuse_ptr in vn_reference_lookup_2. */ |
| data->last_vuse_ptr = NULL; |
| tree saved_vuse = vr->vuse; |
| hashval_t saved_hashcode = vr->hashcode; |
| void *res = vn_reference_lookup_2 (ref, gimple_vuse (def_stmt), data); |
| /* Need to restore vr->vuse and vr->hashcode. */ |
| vr->vuse = saved_vuse; |
| vr->hashcode = saved_hashcode; |
| data->last_vuse_ptr = saved_last_vuse_ptr; |
| if (res && res != (void *)-1) |
| { |
| vn_reference_t vnresult = (vn_reference_t) res; |
| if (vnresult->result |
| && operand_equal_p (vnresult->result, |
| gimple_assign_rhs1 (def_stmt), 0) |
| /* We have to honor our promise about union type punning |
| and also support arbitrary overlaps with |
| -fno-strict-aliasing. So simply resort to alignment to |
| rule out overlaps. Do this check last because it is |
| quite expensive compared to the hash-lookup above. */ |
| && multiple_p (get_object_alignment (ref->ref), ref->size) |
| && multiple_p (get_object_alignment (lhs), ref->size)) |
| return res; |
| } |
| } |
| } |
| else if (gimple_call_builtin_p (def_stmt, BUILT_IN_NORMAL) |
| && gimple_call_num_args (def_stmt) <= 4) |
| { |
| /* For builtin calls valueize its arguments and call the |
| alias oracle again. Valueization may improve points-to |
| info of pointers and constify size and position arguments. |
| Originally this was motivated by PR61034 which has |
| conditional calls to free falsely clobbering ref because |
| of imprecise points-to info of the argument. */ |
| tree oldargs[4]; |
| bool valueized_anything = false; |
| for (unsigned i = 0; i < gimple_call_num_args (def_stmt); ++i) |
| { |
| oldargs[i] = gimple_call_arg (def_stmt, i); |
| tree val = vn_valueize (oldargs[i]); |
| if (val != oldargs[i]) |
| { |
| gimple_call_set_arg (def_stmt, i, val); |
| valueized_anything = true; |
| } |
| } |
| if (valueized_anything) |
| { |
| bool res = call_may_clobber_ref_p_1 (as_a <gcall *> (def_stmt), |
| ref); |
| for (unsigned i = 0; i < gimple_call_num_args (def_stmt); ++i) |
| gimple_call_set_arg (def_stmt, i, oldargs[i]); |
| if (!res) |
| { |
| *disambiguate_only = true; |
| return NULL; |
| } |
| } |
| } |
| |
| /* If we are looking for redundant stores do not create new hashtable |
| entries from aliasing defs with made up alias-sets. */ |
| if (*disambiguate_only || !data->tbaa_p) |
| return (void *)-1; |
| |
| /* If we cannot constrain the size of the reference we cannot |
| test if anything kills it. */ |
| if (!ref->max_size_known_p ()) |
| return (void *)-1; |
| |
| poly_int64 offset = ref->offset; |
| poly_int64 maxsize = ref->max_size; |
| |
| /* We can't deduce anything useful from clobbers. */ |
| if (gimple_clobber_p (def_stmt)) |
| return (void *)-1; |
| |
| /* def_stmt may-defs *ref. See if we can derive a value for *ref |
| from that definition. |
| 1) Memset. */ |
| if (is_gimple_reg_type (vr->type) |
| && gimple_call_builtin_p (def_stmt, BUILT_IN_MEMSET) |
| && (integer_zerop (gimple_call_arg (def_stmt, 1)) |
| || ((TREE_CODE (gimple_call_arg (def_stmt, 1)) == INTEGER_CST |
| || (INTEGRAL_TYPE_P (vr->type) && known_eq (ref->size, 8))) |
| && CHAR_BIT == 8 && BITS_PER_UNIT == 8 |
| && offset.is_constant (&offseti) |
| && offseti % BITS_PER_UNIT == 0 |
| && multiple_p (ref->size, BITS_PER_UNIT))) |
| && poly_int_tree_p (gimple_call_arg (def_stmt, 2)) |
| && (TREE_CODE (gimple_call_arg (def_stmt, 0)) == ADDR_EXPR |
| || TREE_CODE (gimple_call_arg (def_stmt, 0)) == SSA_NAME)) |
| { |
| tree base2; |
| poly_int64 offset2, size2, maxsize2; |
| bool reverse; |
| tree ref2 = gimple_call_arg (def_stmt, 0); |
| if (TREE_CODE (ref2) == SSA_NAME) |
| { |
| ref2 = SSA_VAL (ref2); |
| if (TREE_CODE (ref2) == SSA_NAME |
| && (TREE_CODE (base) != MEM_REF |
| || TREE_OPERAND (base, 0) != ref2)) |
| { |
| gimple *def_stmt = SSA_NAME_DEF_STMT (ref2); |
| if (gimple_assign_single_p (def_stmt) |
| && gimple_assign_rhs_code (def_stmt) == ADDR_EXPR) |
| ref2 = gimple_assign_rhs1 (def_stmt); |
| } |
| } |
| if (TREE_CODE (ref2) == ADDR_EXPR) |
| { |
| ref2 = TREE_OPERAND (ref2, 0); |
| base2 = get_ref_base_and_extent (ref2, &offset2, &size2, &maxsize2, |
| &reverse); |
| if (!known_size_p (maxsize2) |
| || !known_eq (maxsize2, size2) |
| || !operand_equal_p (base, base2, OEP_ADDRESS_OF)) |
| return (void *)-1; |
| } |
| else if (TREE_CODE (ref2) == SSA_NAME) |
| { |
| poly_int64 soff; |
| if (TREE_CODE (base) != MEM_REF |
| || !(mem_ref_offset (base) << LOG2_BITS_PER_UNIT).to_shwi (&soff)) |
| return (void *)-1; |
| offset += soff; |
| offset2 = 0; |
| if (TREE_OPERAND (base, 0) != ref2) |
| { |
| gimple *def = SSA_NAME_DEF_STMT (ref2); |
| if (is_gimple_assign (def) |
| && gimple_assign_rhs_code (def) == POINTER_PLUS_EXPR |
| && gimple_assign_rhs1 (def) == TREE_OPERAND (base, 0) |
| && poly_int_tree_p (gimple_assign_rhs2 (def)) |
| && (wi::to_poly_offset (gimple_assign_rhs2 (def)) |
| << LOG2_BITS_PER_UNIT).to_shwi (&offset2)) |
| { |
| ref2 = gimple_assign_rhs1 (def); |
| if (TREE_CODE (ref2) == SSA_NAME) |
| ref2 = SSA_VAL (ref2); |
| } |
| else |
| return (void *)-1; |
| } |
| } |
| else |
| return (void *)-1; |
| tree len = gimple_call_arg (def_stmt, 2); |
| if (known_subrange_p (offset, maxsize, offset2, |
| wi::to_poly_offset (len) << LOG2_BITS_PER_UNIT)) |
| { |
| tree val; |
| if (integer_zerop (gimple_call_arg (def_stmt, 1))) |
| val = build_zero_cst (vr->type); |
| else if (INTEGRAL_TYPE_P (vr->type) |
| && known_eq (ref->size, 8)) |
| { |
| gimple_match_op res_op (gimple_match_cond::UNCOND, NOP_EXPR, |
| vr->type, gimple_call_arg (def_stmt, 1)); |
| val = vn_nary_build_or_lookup (&res_op); |
| if (!val |
| || (TREE_CODE (val) == SSA_NAME |
| && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val))) |
| return (void *)-1; |
| } |
| else |
| { |
| unsigned len = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (vr->type)); |
| unsigned char *buf = XALLOCAVEC (unsigned char, len); |
| memset (buf, TREE_INT_CST_LOW (gimple_call_arg (def_stmt, 1)), |
| len); |
| val = native_interpret_expr (vr->type, buf, len); |
| if (!val) |
| return (void *)-1; |
| } |
| return vn_reference_lookup_or_insert_for_pieces |
| (vuse, vr->set, vr->type, vr->operands, val); |
| } |
| } |
| |
| /* 2) Assignment from an empty CONSTRUCTOR. */ |
| else if (is_gimple_reg_type (vr->type) |
| && gimple_assign_single_p (def_stmt) |
| && gimple_assign_rhs_code (def_stmt) == CONSTRUCTOR |
| && CONSTRUCTOR_NELTS (gimple_assign_rhs1 (def_stmt)) == 0) |
| { |
| tree base2; |
| poly_int64 offset2, size2, maxsize2; |
| bool reverse; |
| base2 = get_ref_base_and_extent (gimple_assign_lhs (def_stmt), |
| &offset2, &size2, &maxsize2, &reverse); |
| if (known_size_p (maxsize2) |
| && known_eq (maxsize2, size2) |
| && operand_equal_p (base, base2, 0) |
| && known_subrange_p (offset, maxsize, offset2, size2)) |
| { |
| tree val = build_zero_cst (vr->type); |
| return vn_reference_lookup_or_insert_for_pieces |
| (vuse, vr->set, vr->type, vr->operands, val); |
| } |
| } |
| |
| /* 3) Assignment from a constant. We can use folds native encode/interpret |
| routines to extract the assigned bits. */ |
| else if (known_eq (ref->size, maxsize) |
| && is_gimple_reg_type (vr->type) |
| && !contains_storage_order_barrier_p (vr->operands) |
| && gimple_assign_single_p (def_stmt) |
| && CHAR_BIT == 8 && BITS_PER_UNIT == 8 |
| /* native_encode and native_decode operate on arrays of bytes |
| and so fundamentally need a compile-time size and offset. */ |
| && maxsize.is_constant (&maxsizei) |
| && maxsizei % BITS_PER_UNIT == 0 |
| && offset.is_constant (&offseti) |
| && offseti % BITS_PER_UNIT == 0 |
| && (is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt)) |
| || (TREE_CODE (gimple_assign_rhs1 (def_stmt)) == SSA_NAME |
| && is_gimple_min_invariant (SSA_VAL (gimple_assign_rhs1 (def_stmt)))))) |
| { |
| tree base2; |
| HOST_WIDE_INT offset2, size2; |
| bool reverse; |
| base2 = get_ref_base_and_extent_hwi (gimple_assign_lhs (def_stmt), |
| &offset2, &size2, &reverse); |
| if (base2 |
| && !reverse |
| && size2 % BITS_PER_UNIT == 0 |
| && offset2 % BITS_PER_UNIT == 0 |
| && operand_equal_p (base, base2, 0) |
| && known_subrange_p (offseti, maxsizei, offset2, size2)) |
| { |
| /* We support up to 512-bit values (for V8DFmode). */ |
| unsigned char buffer[64]; |
| int len; |
| |
| tree rhs = gimple_assign_rhs1 (def_stmt); |
| if (TREE_CODE (rhs) == SSA_NAME) |
| rhs = SSA_VAL (rhs); |
| unsigned pad = 0; |
| if (BYTES_BIG_ENDIAN |
| && is_a <scalar_mode> (TYPE_MODE (TREE_TYPE (rhs)))) |
| { |
| /* On big-endian the padding is at the 'front' so |
| just skip the initial bytes. */ |
| fixed_size_mode mode |
| = as_a <fixed_size_mode> (TYPE_MODE (TREE_TYPE (rhs))); |
| pad = GET_MODE_SIZE (mode) - size2 / BITS_PER_UNIT; |
| } |
| len = native_encode_expr (rhs, |
| buffer, sizeof (buffer), |
| ((offseti - offset2) / BITS_PER_UNIT |
| + pad)); |
| if (len > 0 && len * BITS_PER_UNIT >= maxsizei) |
| { |
| tree type = vr->type; |
| /* Make sure to interpret in a type that has a range |
| covering the whole access size. */ |
| if (INTEGRAL_TYPE_P (vr->type) |
| && maxsizei != TYPE_PRECISION (vr->type)) |
| type = build_nonstandard_integer_type (maxsizei, |
| TYPE_UNSIGNED (type)); |
| tree val = native_interpret_expr (type, buffer, |
| maxsizei / BITS_PER_UNIT); |
| /* If we chop off bits because the types precision doesn't |
| match the memory access size this is ok when optimizing |
| reads but not when called from the DSE code during |
| elimination. */ |
| if (val |
| && type != vr->type) |
| { |
| if (! int_fits_type_p (val, vr->type)) |
| val = NULL_TREE; |
| else |
| val = fold_convert (vr->type, val); |
| } |
| |
| if (val) |
| return vn_reference_lookup_or_insert_for_pieces |
| (vuse, vr->set, vr->type, vr->operands, val); |
| } |
| } |
| } |
| |
| /* 4) Assignment from an SSA name which definition we may be able |
| to access pieces from. */ |
| else if (known_eq (ref->size, maxsize) |
| && is_gimple_reg_type (vr->type) |
| && !contains_storage_order_barrier_p (vr->operands) |
| && gimple_assign_single_p (def_stmt) |
| && TREE_CODE (gimple_assign_rhs1 (def_stmt)) == SSA_NAME) |
| { |
| tree base2; |
| poly_int64 offset2, size2, maxsize2; |
| bool reverse; |
| base2 = get_ref_base_and_extent (gimple_assign_lhs (def_stmt), |
| &offset2, &size2, &maxsize2, |
| &reverse); |
| tree def_rhs = gimple_assign_rhs1 (def_stmt); |
| if (!reverse |
| && known_size_p (maxsize2) |
| && known_eq (maxsize2, size2) |
| && operand_equal_p (base, base2, 0) |
| && known_subrange_p (offset, maxsize, offset2, size2) |
| /* ??? We can't handle bitfield precision extracts without |
| either using an alternate type for the BIT_FIELD_REF and |
| then doing a conversion or possibly adjusting the offset |
| according to endianness. */ |
| && (! INTEGRAL_TYPE_P (vr->type) |
| || known_eq (ref->size, TYPE_PRECISION (vr->type))) |
| && multiple_p (ref->size, BITS_PER_UNIT) |
| && (! INTEGRAL_TYPE_P (TREE_TYPE (def_rhs)) |
| || type_has_mode_precision_p (TREE_TYPE (def_rhs)))) |
| { |
| gimple_match_op op (gimple_match_cond::UNCOND, |
| BIT_FIELD_REF, vr->type, |
| vn_valueize (def_rhs), |
| bitsize_int (ref->size), |
| bitsize_int (offset - offset2)); |
| tree val = vn_nary_build_or_lookup (&op); |
| if (val |
| && (TREE_CODE (val) != SSA_NAME |
| || ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val))) |
| { |
| vn_reference_t res = vn_reference_lookup_or_insert_for_pieces |
| (vuse, vr->set, vr->type, vr->operands, val); |
| return res; |
| } |
| } |
| } |
| |
| /* 5) For aggregate copies translate the reference through them if |
| the copy kills ref. */ |
| else if (data->vn_walk_kind == VN_WALKREWRITE |
| && gimple_assign_single_p (def_stmt) |
| && (DECL_P (gimple_assign_rhs1 (def_stmt)) |
| || TREE_CODE (gimple_assign_rhs1 (def_stmt)) == MEM_REF |
| || handled_component_p (gimple_assign_rhs1 (def_stmt)))) |
| { |
| tree base2; |
| int i, j, k; |
| auto_vec<vn_reference_op_s> rhs; |
| vn_reference_op_t vro; |
| ao_ref r; |
| |
| if (!lhs_ref_ok) |
| return (void *)-1; |
| |
| /* See if the assignment kills REF. */ |
| base2 = ao_ref_base (&lhs_ref); |
| if (!lhs_ref.max_size_known_p () |
| || (base != base2 |
| && (TREE_CODE (base) != MEM_REF |
| || TREE_CODE (base2) != MEM_REF |
| || TREE_OPERAND (base, 0) != TREE_OPERAND (base2, 0) |
| || !tree_int_cst_equal (TREE_OPERAND (base, 1), |
| TREE_OPERAND (base2, 1)))) |
| || !stmt_kills_ref_p (def_stmt, ref)) |
| return (void *)-1; |
| |
| /* Find the common base of ref and the lhs. lhs_ops already |
| contains valueized operands for the lhs. */ |
| i = vr->operands.length () - 1; |
| j = lhs_ops.length () - 1; |
| while (j >= 0 && i >= 0 |
| && vn_reference_op_eq (&vr->operands[i], &lhs_ops[j])) |
| { |
| i--; |
| j--; |
| } |
| |
| /* ??? The innermost op should always be a MEM_REF and we already |
| checked that the assignment to the lhs kills vr. Thus for |
| aggregate copies using char[] types the vn_reference_op_eq |
| may fail when comparing types for compatibility. But we really |
| don't care here - further lookups with the rewritten operands |
| will simply fail if we messed up types too badly. */ |
| poly_int64 extra_off = 0; |
| if (j == 0 && i >= 0 |
| && lhs_ops[0].opcode == MEM_REF |
| && maybe_ne (lhs_ops[0].off, -1)) |
| { |
| if (known_eq (lhs_ops[0].off, vr->operands[i].off)) |
| i--, j--; |
| else if (vr->operands[i].opcode == MEM_REF |
| && maybe_ne (vr->operands[i].off, -1)) |
| { |
| extra_off = vr->operands[i].off - lhs_ops[0].off; |
| i--, j--; |
| } |
| } |
| |
| /* i now points to the first additional op. |
| ??? LHS may not be completely contained in VR, one or more |
| VIEW_CONVERT_EXPRs could be in its way. We could at least |
| try handling outermost VIEW_CONVERT_EXPRs. */ |
| if (j != -1) |
| return (void *)-1; |
| |
| /* Punt if the additional ops contain a storage order barrier. */ |
| for (k = i; k >= 0; k--) |
| { |
| vro = &vr->operands[k]; |
| if (vro->opcode == VIEW_CONVERT_EXPR && vro->reverse) |
| return (void *)-1; |
| } |
| |
| /* Now re-write REF to be based on the rhs of the assignment. */ |
| copy_reference_ops_from_ref (gimple_assign_rhs1 (def_stmt), &rhs); |
| |
| /* Apply an extra offset to the inner MEM_REF of the RHS. */ |
| if (maybe_ne (extra_off, 0)) |
| { |
| if (rhs.length () < 2) |
| return (void *)-1; |
| int ix = rhs.length () - 2; |
| if (rhs[ix].opcode != MEM_REF |
| || known_eq (rhs[ix].off, -1)) |
| return (void *)-1; |
| rhs[ix].off += extra_off; |
| rhs[ix].op0 = int_const_binop (PLUS_EXPR, rhs[ix].op0, |
| build_int_cst (TREE_TYPE (rhs[ix].op0), |
| extra_off)); |
| } |
| |
| /* We need to pre-pend vr->operands[0..i] to rhs. */ |
| vec<vn_reference_op_s> old = vr->operands; |
| if (i + 1 + rhs.length () > vr->operands.length ()) |
| vr->operands.safe_grow (i + 1 + rhs.length ()); |
| else |
| vr->operands.truncate (i + 1 + rhs.length ()); |
| FOR_EACH_VEC_ELT (rhs, j, vro) |
| vr->operands[i + 1 + j] = *vro; |
| vr->operands = valueize_refs (vr->operands); |
| if (old == shared_lookup_references) |
| shared_lookup_references = vr->operands; |
| vr->hashcode = vn_reference_compute_hash (vr); |
| |
| /* Try folding the new reference to a constant. */ |
| tree val = fully_constant_vn_reference_p (vr); |
| if (val) |
| return vn_reference_lookup_or_insert_for_pieces |
| (vuse, vr->set, vr->type, vr->operands, val); |
| |
| /* Adjust *ref from the new operands. */ |
| if (!ao_ref_init_from_vn_reference (&r, vr->set, vr->type, vr->operands)) |
| return (void *)-1; |
| /* This can happen with bitfields. */ |
| if (maybe_ne (ref->size, r.size)) |
| return (void *)-1; |
| *ref = r; |
| |
| /* Do not update last seen VUSE after translating. */ |
| data->last_vuse_ptr = NULL; |
| |
| /* Keep looking for the adjusted *REF / VR pair. */ |
| return NULL; |
| } |
| |
| /* 6) For memcpy copies translate the reference through them if |
| the copy kills ref. */ |
| else if (data->vn_walk_kind == VN_WALKREWRITE |
| && is_gimple_reg_type (vr->type) |
| /* ??? Handle BCOPY as well. */ |
| && (gimple_call_builtin_p (def_stmt, BUILT_IN_MEMCPY) |
| || gimple_call_builtin_p (def_stmt, BUILT_IN_MEMPCPY) |
| || gimple_call_builtin_p (def_stmt, BUILT_IN_MEMMOVE)) |
| && (TREE_CODE (gimple_call_arg (def_stmt, 0)) == ADDR_EXPR |
| || TREE_CODE (gimple_call_arg (def_stmt, 0)) == SSA_NAME) |
| && (TREE_CODE (gimple_call_arg (def_stmt, 1)) == ADDR_EXPR |
| || TREE_CODE (gimple_call_arg (def_stmt, 1)) == SSA_NAME) |
| && poly_int_tree_p (gimple_call_arg (def_stmt, 2), ©_size)) |
| { |
| tree lhs, rhs; |
| ao_ref r; |
| poly_int64 rhs_offset, lhs_offset; |
| vn_reference_op_s op; |
| poly_uint64 mem_offset; |
| poly_int64 at, byte_maxsize; |
| |
| /* Only handle non-variable, addressable refs. */ |
| if (maybe_ne (ref->size, maxsize) |
| || !multiple_p (offset, BITS_PER_UNIT, &at) |
| || !multiple_p (maxsize, BITS_PER_UNIT, &byte_maxsize)) |
| return (void *)-1; |
| |
| /* Extract a pointer base and an offset for the destination. */ |
| lhs = gimple_call_arg (def_stmt, 0); |
| lhs_offset = 0; |
| if (TREE_CODE (lhs) == SSA_NAME) |
| { |
| lhs = vn_valueize (lhs); |
| if (TREE_CODE (lhs) == SSA_NAME) |
| { |
| gimple *def_stmt = SSA_NAME_DEF_STMT (lhs); |
| if (gimple_assign_single_p (def_stmt) |
| && gimple_assign_rhs_code (def_stmt) == ADDR_EXPR) |
| lhs = gimple_assign_rhs1 (def_stmt); |
| } |
| } |
| if (TREE_CODE (lhs) == ADDR_EXPR) |
| { |
| tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (lhs, 0), |
| &lhs_offset); |
| if (!tem) |
| return (void *)-1; |
| if (TREE_CODE (tem) == MEM_REF |
| && poly_int_tree_p (TREE_OPERAND (tem, 1), &mem_offset)) |
| { |
| lhs = TREE_OPERAND (tem, 0); |
| if (TREE_CODE (lhs) == SSA_NAME) |
| lhs = vn_valueize (lhs); |
| lhs_offset += mem_offset; |
| } |
| else if (DECL_P (tem)) |
| lhs = build_fold_addr_expr (tem); |
| else |
| return (void *)-1; |
| } |
| if (TREE_CODE (lhs) != SSA_NAME |
| && TREE_CODE (lhs) != ADDR_EXPR) |
| return (void *)-1; |
| |
| /* Extract a pointer base and an offset for the source. */ |
| rhs = gimple_call_arg (def_stmt, 1); |
| rhs_offset = 0; |
| if (TREE_CODE (rhs) == SSA_NAME) |
| rhs = vn_valueize (rhs); |
| if (TREE_CODE (rhs) == ADDR_EXPR) |
| { |
| tree tem = get_addr_base_and_unit_offset (TREE_OPERAND (rhs, 0), |
| &rhs_offset); |
| if (!tem) |
| return (void *)-1; |
| if (TREE_CODE (tem) == MEM_REF |
| && poly_int_tree_p (TREE_OPERAND (tem, 1), &mem_offset)) |
| { |
| rhs = TREE_OPERAND (tem, 0); |
| rhs_offset += mem_offset; |
| } |
| else if (DECL_P (tem) |
| || TREE_CODE (tem) == STRING_CST) |
| rhs = build_fold_addr_expr (tem); |
| else |
| return (void *)-1; |
| } |
| if (TREE_CODE (rhs) != SSA_NAME |
| && TREE_CODE (rhs) != ADDR_EXPR) |
| return (void *)-1; |
| |
| /* The bases of the destination and the references have to agree. */ |
| if (TREE_CODE (base) == MEM_REF) |
| { |
| if (TREE_OPERAND (base, 0) != lhs |
| || !poly_int_tree_p (TREE_OPERAND (base, 1), &mem_offset)) |
| return (void *) -1; |
| at += mem_offset; |
| } |
| else if (!DECL_P (base) |
| || TREE_CODE (lhs) != ADDR_EXPR |
| || TREE_OPERAND (lhs, 0) != base) |
| return (void *)-1; |
| |
| /* If the access is completely outside of the memcpy destination |
| area there is no aliasing. */ |
| if (!ranges_maybe_overlap_p (lhs_offset, copy_size, at, byte_maxsize)) |
| return NULL; |
| /* And the access has to be contained within the memcpy destination. */ |
| if (!known_subrange_p (at, byte_maxsize, lhs_offset, copy_size)) |
| return (void *)-1; |
| |
| /* Make room for 2 operands in the new reference. */ |
| if (vr->operands.length () < 2) |
| { |
| vec<vn_reference_op_s> old = vr->operands; |
| vr->operands.safe_grow_cleared (2); |
| if (old == shared_lookup_references) |
| shared_lookup_references = vr->operands; |
| } |
| else |
| vr->operands.truncate (2); |
| |
| /* The looked-through reference is a simple MEM_REF. */ |
| memset (&op, 0, sizeof (op)); |
| op.type = vr->type; |
| op.opcode = MEM_REF; |
| op.op0 = build_int_cst (ptr_type_node, at - lhs_offset + rhs_offset); |
| op.off = at - lhs_offset + rhs_offset; |
| vr->operands[0] = op; |
| op.type = TREE_TYPE (rhs); |
| op.opcode = TREE_CODE (rhs); |
| op.op0 = rhs; |
| op.off = -1; |
| vr->operands[1] = op; |
| vr->hashcode = vn_reference_compute_hash (vr); |
| |
| /* Try folding the new reference to a constant. */ |
| tree val = fully_constant_vn_reference_p (vr); |
| if (val) |
| return vn_reference_lookup_or_insert_for_pieces |
| (vuse, vr->set, vr->type, vr->operands, val); |
| |
| /* Adjust *ref from the new operands. */ |
| if (!ao_ref_init_from_vn_reference (&r, vr->set, vr->type, vr->operands)) |
| return (void *)-1; |
| /* This can happen with bitfields. */ |
| if (maybe_ne (ref->size, r.size)) |
| return (void *)-1; |
| *ref = r; |
| |
| /* Do not update last seen VUSE after translating. */ |
| data->last_vuse_ptr = NULL; |
| |
| /* Keep looking for the adjusted *REF / VR pair. */ |
| return NULL; |
| } |
| |
| /* Bail out and stop walking. */ |
| return (void *)-1; |
| } |
| |
| /* Return a reference op vector from OP that can be used for |
| vn_reference_lookup_pieces. The caller is responsible for releasing |
| the vector. */ |
| |
| vec<vn_reference_op_s> |
| vn_reference_operands_for_lookup (tree op) |
| { |
| bool valueized; |
| return valueize_shared_reference_ops_from_ref (op, &valueized).copy (); |
| } |
| |
| /* Lookup a reference operation by it's parts, in the current hash table. |
| Returns the resulting value number if it exists in the hash table, |
| NULL_TREE otherwise. VNRESULT will be filled in with the actual |
| vn_reference_t stored in the hashtable if something is found. */ |
| |
| tree |
| vn_reference_lookup_pieces (tree vuse, alias_set_type set, tree type, |
| vec<vn_reference_op_s> operands, |
| vn_reference_t *vnresult, vn_lookup_kind kind) |
| { |
| struct vn_reference_s vr1; |
| vn_reference_t tmp; |
| tree cst; |
| |
| if (!vnresult) |
| vnresult = &tmp; |
| *vnresult = NULL; |
| |
| vr1.vuse = vuse_ssa_val (vuse); |
| shared_lookup_references.truncate (0); |
| shared_lookup_references.safe_grow (operands.length ()); |
| memcpy (shared_lookup_references.address (), |
| operands.address (), |
| sizeof (vn_reference_op_s) |
| * operands.length ()); |
| vr1.operands = operands = shared_lookup_references |
| = valueize_refs (shared_lookup_references); |
| vr1.type = type; |
| vr1.set = set; |
| vr1.hashcode = vn_reference_compute_hash (&vr1); |
| if ((cst = fully_constant_vn_reference_p (&vr1))) |
| return cst; |
| |
| vn_reference_lookup_1 (&vr1, vnresult); |
| if (!*vnresult |
| && kind != VN_NOWALK |
| && vr1.vuse) |
| { |
| ao_ref r; |
| unsigned limit = PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS); |
| vn_walk_cb_data data (&vr1, NULL, kind, true); |
| if (ao_ref_init_from_vn_reference (&r, set, type, vr1.operands)) |
| *vnresult = |
| (vn_reference_t)walk_non_aliased_vuses (&r, vr1.vuse, true, |
| vn_reference_lookup_2, |
| vn_reference_lookup_3, |
| vuse_valueize, limit, &data); |
| gcc_checking_assert (vr1.operands == shared_lookup_references); |
| } |
| |
| if (*vnresult) |
| return (*vnresult)->result; |
| |
| return NULL_TREE; |
| } |
| |
| /* Lookup OP in the current hash table, and return the resulting value |
| number if it exists in the hash table. Return NULL_TREE if it does |
| not exist in the hash table or if the result field of the structure |
| was NULL.. VNRESULT will be filled in with the vn_reference_t |
| stored in the hashtable if one exists. When TBAA_P is false assume |
| we are looking up a store and treat it as having alias-set zero. |
| *LAST_VUSE_PTR will be updated with the VUSE the value lookup succeeded. */ |
| |
| tree |
| vn_reference_lookup (tree op, tree vuse, vn_lookup_kind kind, |
| vn_reference_t *vnresult, bool tbaa_p, tree *last_vuse_ptr) |
| { |
| vec<vn_reference_op_s> operands; |
| struct vn_reference_s vr1; |
| tree cst; |
| bool valuezied_anything; |
| |
| if (vnresult) |
| *vnresult = NULL; |
| |
| vr1.vuse = vuse_ssa_val (vuse); |
| vr1.operands = operands |
| = valueize_shared_reference_ops_from_ref (op, &valuezied_anything); |
| vr1.type = TREE_TYPE (op); |
| vr1.set = get_alias_set (op); |
| vr1.hashcode = vn_reference_compute_hash (&vr1); |
| if ((cst = fully_constant_vn_reference_p (&vr1))) |
| return cst; |
| |
| if (kind != VN_NOWALK |
| && vr1.vuse) |
| { |
| vn_reference_t wvnresult; |
| ao_ref r; |
| unsigned limit = PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS); |
| /* Make sure to use a valueized reference if we valueized anything. |
| Otherwise preserve the full reference for advanced TBAA. */ |
| if (!valuezied_anything |
| || !ao_ref_init_from_vn_reference (&r, vr1.set, vr1.type, |
| vr1.operands)) |
| ao_ref_init (&r, op); |
| vn_walk_cb_data data (&vr1, last_vuse_ptr, kind, tbaa_p); |
| wvnresult = |
| (vn_reference_t)walk_non_aliased_vuses (&r, vr1.vuse, tbaa_p, |
| vn_reference_lookup_2, |
| vn_reference_lookup_3, |
| vuse_valueize, limit, &data); |
| gcc_checking_assert (vr1.operands == shared_lookup_references); |
| if (wvnresult) |
| { |
| if (vnresult) |
| *vnresult = wvnresult; |
| return wvnresult->result; |
| } |
| |
| return NULL_TREE; |
| } |
| |
| return vn_reference_lookup_1 (&vr1, vnresult); |
| } |
| |
| /* Lookup CALL in the current hash table and return the entry in |
| *VNRESULT if found. Populates *VR for the hashtable lookup. */ |
| |
| void |
| vn_reference_lookup_call (gcall *call, vn_reference_t *vnresult, |
| vn_reference_t vr) |
| { |
| if (vnresult) |
| *vnresult = NULL; |
| |
| tree vuse = gimple_vuse (call); |
| |
| vr->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE; |
| vr->operands = valueize_shared_reference_ops_from_call (call); |
| vr->type = gimple_expr_type (call); |
| vr->punned = false; |
| vr->set = 0; |
| vr->hashcode = vn_reference_compute_hash (vr); |
| vn_reference_lookup_1 (vr, vnresult); |
| } |
| |
| /* Insert OP into the current hash table with a value number of RESULT. */ |
| |
| static void |
| vn_reference_insert (tree op, tree result, tree vuse, tree vdef) |
| { |
| vn_reference_s **slot; |
| vn_reference_t vr1; |
| bool tem; |
| |
| vr1 = XOBNEW (&vn_tables_obstack, vn_reference_s); |
| if (TREE_CODE (result) == SSA_NAME) |
| vr1->value_id = VN_INFO (result)->value_id; |
| else |
| vr1->value_id = get_or_alloc_constant_value_id (result); |
| vr1->vuse = vuse_ssa_val (vuse); |
| vr1->operands = valueize_shared_reference_ops_from_ref (op, &tem).copy (); |
| vr1->type = TREE_TYPE (op); |
| vr1->punned = false; |
| vr1->set = get_alias_set (op); |
| vr1->hashcode = vn_reference_compute_hash (vr1); |
| vr1->result = TREE_CODE (result) == SSA_NAME ? SSA_VAL (result) : result; |
| vr1->result_vdef = vdef; |
| |
| slot = valid_info->references->find_slot_with_hash (vr1, vr1->hashcode, |
| INSERT); |
| |
| /* Because IL walking on reference lookup can end up visiting |
| a def that is only to be visited later in iteration order |
| when we are about to make an irreducible region reducible |
| the def can be effectively processed and its ref being inserted |
| by vn_reference_lookup_3 already. So we cannot assert (!*slot) |
| but save a lookup if we deal with already inserted refs here. */ |
| if (*slot) |
| { |
| /* We cannot assert that we have the same value either because |
| when disentangling an irreducible region we may end up visiting |
| a use before the corresponding def. That's a missed optimization |
| only though. See gcc.dg/tree-ssa/pr87126.c for example. */ |
| if (dump_file && (dump_flags & TDF_DETAILS) |
| && !operand_equal_p ((*slot)->result, vr1->result, 0)) |
| { |
| fprintf (dump_file, "Keeping old value "); |
| print_generic_expr (dump_file, (*slot)->result); |
| fprintf (dump_file, " because of collision\n"); |
| } |
| free_reference (vr1); |
| obstack_free (&vn_tables_obstack, vr1); |
| return; |
| } |
| |
| *slot = vr1; |
| vr1->next = last_inserted_ref; |
| last_inserted_ref = vr1; |
| } |
| |
| /* Insert a reference by it's pieces into the current hash table with |
| a value number of RESULT. Return the resulting reference |
| structure we created. */ |
| |
| vn_reference_t |
| vn_reference_insert_pieces (tree vuse, alias_set_type set, tree type, |
| vec<vn_reference_op_s> operands, |
| tree result, unsigned int value_id) |
| |
| { |
| vn_reference_s **slot; |
| vn_reference_t vr1; |
| |
| vr1 = XOBNEW (&vn_tables_obstack, vn_reference_s); |
| vr1->value_id = value_id; |
| vr1->vuse = vuse_ssa_val (vuse); |
| vr1->operands = valueize_refs (operands); |
| vr1->type = type; |
| vr1->punned = false; |
| vr1->set = set; |
| vr1->hashcode = vn_reference_compute_hash (vr1); |
| if (result && TREE_CODE (result) == SSA_NAME) |
| result = SSA_VAL (result); |
| vr1->result = result; |
| |
| slot = valid_info->references->find_slot_with_hash (vr1, vr1->hashcode, |
| INSERT); |
| |
| /* At this point we should have all the things inserted that we have |
| seen before, and we should never try inserting something that |
| already exists. */ |
| gcc_assert (!*slot); |
| |
| *slot = vr1; |
| vr1->next = last_inserted_ref; |
| last_inserted_ref = vr1; |
| return vr1; |
| } |
| |
| /* Compute and return the hash value for nary operation VBO1. */ |
| |
| static hashval_t |
| vn_nary_op_compute_hash (const vn_nary_op_t vno1) |
| { |
| inchash::hash hstate; |
| unsigned i; |
| |
| for (i = 0; i < vno1->length; ++i) |
| if (TREE_CODE (vno1->op[i]) == SSA_NAME) |
| vno1->op[i] = SSA_VAL (vno1->op[i]); |
| |
| if (((vno1->length == 2 |
| && commutative_tree_code (vno1->opcode)) |
| || (vno1->length == 3 |
| && commutative_ternary_tree_code (vno1->opcode))) |
| && tree_swap_operands_p (vno1->op[0], vno1->op[1])) |
| std::swap (vno1->op[0], vno1->op[1]); |
| else if (TREE_CODE_CLASS (vno1->opcode) == tcc_comparison |
| && tree_swap_operands_p (vno1->op[0], vno1->op[1])) |
| { |
| std::swap (vno1->op[0], vno1->op[1]); |
| vno1->opcode = swap_tree_comparison (vno1->opcode); |
| } |
| |
| hstate.add_int (vno1->opcode); |
| for (i = 0; i < vno1->length; ++i) |
| inchash::add_expr (vno1->op[i], hstate); |
| |
| return hstate.end (); |
| } |
| |
| /* Compare nary operations VNO1 and VNO2 and return true if they are |
| equivalent. */ |
| |
| bool |
| vn_nary_op_eq (const_vn_nary_op_t const vno1, const_vn_nary_op_t const vno2) |
| { |
| unsigned i; |
| |
| if (vno1->hashcode != vno2->hashcode) |
| return false; |
| |
| if (vno1->length != vno2->length) |
| return false; |
| |
| if (vno1->opcode != vno2->opcode |
| || !types_compatible_p (vno1->type, vno2->type)) |
| return false; |
| |
| for (i = 0; i < vno1->length; ++i) |
| if (!expressions_equal_p (vno1->op[i], vno2->op[i])) |
| return false; |
| |
| /* BIT_INSERT_EXPR has an implict operand as the type precision |
| of op1. Need to check to make sure they are the same. */ |
| if (vno1->opcode == BIT_INSERT_EXPR |
| && TREE_CODE (vno1->op[1]) == INTEGER_CST |
| && TYPE_PRECISION (TREE_TYPE (vno1->op[1])) |
| != TYPE_PRECISION (TREE_TYPE (vno2->op[1]))) |
| return false; |
| |
| return true; |
| } |
| |
| /* Initialize VNO from the pieces provided. */ |
| |
| static void |
| init_vn_nary_op_from_pieces (vn_nary_op_t vno, unsigned int length, |
| enum tree_code code, tree type, tree *ops) |
| { |
| vno->opcode = code; |
| vno->length = length; |
| vno->type = type; |
| memcpy (&vno->op[0], ops, sizeof (tree) * length); |
| } |
| |
| /* Initialize VNO from OP. */ |
| |
| static void |
| init_vn_nary_op_from_op (vn_nary_op_t vno, tree op) |
| { |
| unsigned i; |
| |
| vno->opcode = TREE_CODE (op); |
| vno->length = TREE_CODE_LENGTH (TREE_CODE (op)); |
| vno->type = TREE_TYPE (op); |
| for (i = 0; i < vno->length; ++i) |
| vno->op[i] = TREE_OPERAND (op, i); |
| } |
| |
| /* Return the number of operands for a vn_nary ops structure from STMT. */ |
| |
| static unsigned int |
| vn_nary_length_from_stmt (gimple *stmt) |
| { |
| switch (gimple_assign_rhs_code (stmt)) |
| { |
| case REALPART_EXPR: |
| case IMAGPART_EXPR: |
| case VIEW_CONVERT_EXPR: |
| return 1; |
| |
| case BIT_FIELD_REF: |
| return 3; |
| |
| case CONSTRUCTOR: |
| return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt)); |
| |
| default: |
| return gimple_num_ops (stmt) - 1; |
| } |
| } |
| |
| /* Initialize VNO from STMT. */ |
| |
| static void |
| init_vn_nary_op_from_stmt (vn_nary_op_t vno, gimple *stmt) |
| { |
| unsigned i; |
| |
| vno->opcode = gimple_assign_rhs_code (stmt); |
| vno->type = gimple_expr_type (stmt); |
| switch (vno->opcode) |
| { |
| case REALPART_EXPR: |
| case IMAGPART_EXPR: |
| case VIEW_CONVERT_EXPR: |
| vno->length = 1; |
| vno->op[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0); |
| break; |
| |
| case BIT_FIELD_REF: |
| vno->length = 3; |
| vno-> |