| /* SCC value numbering for trees |
| Copyright (C) 2006-2017 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 "alloc-pool.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-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. |
| */ |
| |
| |
| static tree *last_vuse_ptr; |
| static vn_lookup_kind vn_walk_kind; |
| static vn_lookup_kind default_vn_walk_kind; |
| bitmap const_parms; |
| |
| /* 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 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 : pointer_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 *); |
| static inline void remove (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 vn_phi_eq (vp1, vp2); |
| } |
| |
| /* Free a phi operation structure VP. */ |
| |
| inline void |
| vn_phi_hasher::remove (vn_phi_s *phi) |
| { |
| phi->phiargs.release (); |
| } |
| |
| 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 : pointer_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 *); |
| static inline void remove (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 vn_reference_eq (v, c); |
| } |
| |
| inline void |
| vn_reference_hasher::remove (vn_reference_s *v) |
| { |
| free_reference (v); |
| } |
| |
| typedef hash_table<vn_reference_hasher> vn_reference_table_type; |
| typedef vn_reference_table_type::iterator vn_reference_iterator_type; |
| |
| |
| /* The set of hashtables and alloc_pool's for their items. */ |
| |
| typedef struct vn_tables_s |
| { |
| vn_nary_op_table_type *nary; |
| vn_phi_table_type *phis; |
| vn_reference_table_type *references; |
| struct obstack nary_obstack; |
| object_allocator<vn_phi_s> *phis_pool; |
| object_allocator<vn_reference_s> *references_pool; |
| } *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; |
| |
| |
| /* Valid hashtables storing information we have proven to be |
| correct. */ |
| |
| static vn_tables_t valid_info; |
| |
| /* Optimistic hashtables storing information we are making assumptions about |
| during iterations. */ |
| |
| static vn_tables_t optimistic_info; |
| |
| /* Pointer to the set of hashtables that is currently being used. |
| Should always point to either the optimistic_info, or the |
| valid_info. */ |
| |
| static vn_tables_t current_info; |
| |
| |
| /* Reverse post order index for each basic block. */ |
| |
| static int *rpo_numbers; |
| |
| #define SSA_VAL(x) (VN_INFO ((x))->valnum) |
| |
| /* 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 |
| { |
| tree tem = SSA_VAL (x); |
| /* stmt walking can walk over a backedge and reach code we didn't |
| value-number yet. */ |
| if (tem == VN_TOP) |
| return x; |
| x = tem; |
| } |
| while (SSA_NAME_IN_FREE_LIST (x)); |
| |
| return x; |
| } |
| |
| /* 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; |
| |
| /* Next DFS number and the stack for strongly connected component |
| detection. */ |
| |
| static unsigned int next_dfs_num; |
| static vec<tree> sccstack; |
| |
| |
| |
| /* 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. */ |
| |
| static vec<vn_ssa_aux_t> vn_ssa_aux_table; |
| static struct obstack vn_ssa_aux_obstack; |
| |
| /* Return whether there is value numbering information for a given SSA name. */ |
| |
| bool |
| has_VN_INFO (tree name) |
| { |
| if (SSA_NAME_VERSION (name) < vn_ssa_aux_table.length ()) |
| return vn_ssa_aux_table[SSA_NAME_VERSION (name)] != NULL; |
| return false; |
| } |
| |
| /* Return the value numbering information for a given SSA name. */ |
| |
| vn_ssa_aux_t |
| VN_INFO (tree name) |
| { |
| vn_ssa_aux_t res = vn_ssa_aux_table[SSA_NAME_VERSION (name)]; |
| gcc_checking_assert (res); |
| return res; |
| } |
| |
| /* Set the value numbering info for a given SSA name to a given |
| value. */ |
| |
| static inline void |
| VN_INFO_SET (tree name, vn_ssa_aux_t value) |
| { |
| vn_ssa_aux_table[SSA_NAME_VERSION (name)] = value; |
| } |
| |
| /* Initialize the value numbering info for a given SSA name. |
| This should be called just once for every SSA name. */ |
| |
| vn_ssa_aux_t |
| VN_INFO_GET (tree name) |
| { |
| vn_ssa_aux_t newinfo; |
| |
| gcc_assert (SSA_NAME_VERSION (name) >= vn_ssa_aux_table.length () |
| || vn_ssa_aux_table[SSA_NAME_VERSION (name)] == NULL); |
| newinfo = XOBNEW (&vn_ssa_aux_obstack, struct vn_ssa_aux); |
| memset (newinfo, 0, sizeof (struct vn_ssa_aux)); |
| if (SSA_NAME_VERSION (name) >= vn_ssa_aux_table.length ()) |
| vn_ssa_aux_table.safe_grow_cleared (SSA_NAME_VERSION (name) + 1); |
| vn_ssa_aux_table[SSA_NAME_VERSION (name)] = newinfo; |
| return newinfo; |
| } |
| |
| |
| /* 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) |
| 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; |
| |
| 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; |
| HOST_WIDE_INT 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 (vro->off != -1) |
| { |
| if (off == -1) |
| off = 0; |
| off += vro->off; |
| } |
| else |
| { |
| if (off != -1 |
| && off != 0) |
| hstate.add_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 |
| { |
| HOST_WIDE_INT 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 (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 (vro2->off == -1) |
| break; |
| off2 += vro2->off; |
| } |
| if (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); |
| { |
| offset_int off = mem_ref_offset (ref); |
| if (wi::fits_shwi_p (off)) |
| temp.off = off.to_shwi (); |
| } |
| 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 (tree_fits_shwi_p (TREE_OPERAND (ref, 2))) |
| { |
| HOST_WIDE_INT off = tree_to_shwi (TREE_OPERAND (ref, 2)); |
| if (off % BITS_PER_UNIT == 0) |
| temp.off = off / BITS_PER_UNIT; |
| } |
| 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 |
| && TREE_CODE (this_offset) == INTEGER_CST) |
| { |
| tree bit_offset = DECL_FIELD_BIT_OFFSET (TREE_OPERAND (ref, 1)); |
| if (TREE_INT_CST_LOW (bit_offset) % BITS_PER_UNIT == 0) |
| { |
| offset_int off |
| = (wi::to_offset (this_offset) |
| + (wi::to_offset (bit_offset) >> LOG2_BITS_PER_UNIT)); |
| if (wi::fits_shwi_p (off) |
| /* 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). */ |
| && (TREE_CODE (orig) != ADDR_EXPR |
| || off != 0 |
| || cfun->after_inlining)) |
| temp.off = off.to_shwi (); |
| } |
| } |
| } |
| 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 (TREE_CODE (temp.op0) == INTEGER_CST |
| && TREE_CODE (temp.op1) == INTEGER_CST |
| && TREE_CODE (temp.op2) == INTEGER_CST) |
| { |
| offset_int off = ((wi::to_offset (temp.op0) |
| - wi::to_offset (temp.op1)) |
| * wi::to_offset (temp.op2) |
| * vn_ref_op_align_unit (&temp)); |
| if (wi::fits_shwi_p (off)) |
| temp.off = off.to_shwi(); |
| } |
| } |
| 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; |
| offset_int offset = 0; |
| offset_int max_size; |
| 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 = int (GET_MODE_BITSIZE (mode)); |
| } |
| if (size_tree != NULL_TREE |
| && TREE_CODE (size_tree) == INTEGER_CST) |
| size = wi::to_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 (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_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 || TREE_CODE (this_offset) != INTEGER_CST) |
| max_size = -1; |
| else |
| { |
| offset_int woffset = (wi::to_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 (TREE_CODE (op->op0) != INTEGER_CST |
| || TREE_CODE (op->op1) != INTEGER_CST |
| || TREE_CODE (op->op2) != INTEGER_CST) |
| max_size = -1; |
| else |
| { |
| offset_int woffset |
| = wi::sext (wi::to_offset (op->op0) - wi::to_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 (!wi::fits_shwi_p (size) || wi::neg_p (size)) |
| { |
| ref->offset = 0; |
| ref->size = -1; |
| ref->max_size = -1; |
| return true; |
| } |
| |
| ref->size = size.to_shwi (); |
| |
| if (!wi::fits_shwi_p (offset)) |
| { |
| ref->offset = 0; |
| ref->max_size = -1; |
| return true; |
| } |
| |
| ref->offset = offset.to_shwi (); |
| |
| if (!wi::fits_shwi_p (max_size) || wi::neg_p (max_size)) |
| ref->max_size = -1; |
| else |
| ref->max_size = max_size.to_shwi (); |
| |
| 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_return_type (call); |
| temp.opcode = CALL_EXPR; |
| temp.op0 = gimple_call_fn (call); |
| temp.op1 = gimple_call_chain (call); |
| if (stmt_could_throw_p (call) && (lr = lookup_stmt_eh_lp (call)) > 0) |
| temp.op2 = size_int (lr); |
| temp.off = -1; |
| if (gimple_call_with_bounds_p (call)) |
| temp.with_bounds = 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; |
| HOST_WIDE_INT 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)) |
| { |
| offset_int off = offset_int::from (wi::to_wide (mem_op->op0), SIGNED); |
| off += 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) |
| { |
| unsigned int i = *i_p; |
| vn_reference_op_t op = &(*ops)[i]; |
| vn_reference_op_t mem_op = &(*ops)[i - 1]; |
| gimple *def_stmt; |
| enum tree_code code; |
| offset_int off; |
| |
| def_stmt = SSA_NAME_DEF_STMT (op->op0); |
| if (!is_gimple_assign (def_stmt)) |
| return false; |
| |
| code = gimple_assign_rhs_code (def_stmt); |
| if (code != ADDR_EXPR |
| && code != POINTER_PLUS_EXPR) |
| return false; |
| |
| off = offset_int::from (wi::to_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; |
| HOST_WIDE_INT 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 |
| && 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_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) |
| return false; |
| |
| 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 |
| || TREE_CODE (ptroff) != INTEGER_CST) |
| return false; |
| |
| off += wi::to_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; |
| 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); |
| |
| /* And recurse. */ |
| if (TREE_CODE (op->op0) == SSA_NAME) |
| vn_reference_maybe_forwprop_address (ops, i_p); |
| else if (TREE_CODE (op->op0) == ADDR_EXPR) |
| vn_reference_fold_indirect (ops, i_p); |
| return true; |
| } |
| |
| /* 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 |
| && DECL_BUILT_IN (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 |
| && is_gimple_reg_type (ref->type) |
| && (!INTEGRAL_TYPE_P (ref->type) |
| || TYPE_PRECISION (ref->type) % BITS_PER_UNIT == 0)) |
| { |
| HOST_WIDE_INT off = 0; |
| HOST_WIDE_INT size; |
| if (INTEGRAL_TYPE_P (ref->type)) |
| size = TYPE_PRECISION (ref->type); |
| else |
| size = tree_to_shwi (TYPE_SIZE (ref->type)); |
| 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 (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) |
| { |
| 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 |
| { |
| unsigned char buf[MAX_BITSIZE_MODE_ANY_MODE / BITS_PER_UNIT]; |
| int len = native_encode_expr (ctor, buf, size, 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) |
| { |
| 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 = 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 = 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 = 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 |
| && vro->off == -1 |
| && TREE_CODE (vro->op0) == INTEGER_CST |
| && TREE_CODE (vro->op1) == INTEGER_CST |
| && TREE_CODE (vro->op2) == INTEGER_CST) |
| { |
| offset_int off = ((wi::to_offset (vro->op0) |
| - wi::to_offset (vro->op1)) |
| * wi::to_offset (vro->op2) |
| * vn_ref_op_align_unit (vro)); |
| if (wi::fits_shwi_p (off)) |
| vro->off = off.to_shwi (); |
| } |
| } |
| |
| 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 = current_info->references->find_slot_with_hash (vr, hash, NO_INSERT); |
| if (!slot && current_info == optimistic_info) |
| 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; |
| } |
| |
| /* 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, |
| unsigned int cnt, void *vr_) |
| { |
| vn_reference_t vr = (vn_reference_t)vr_; |
| vn_reference_s **slot; |
| hashval_t hash; |
| |
| /* This bounds the stmt walks we perform on reference lookups |
| to O(1) instead of O(N) where N is the number of dominating |
| stores. */ |
| if (cnt > (unsigned) PARAM_VALUE (PARAM_SCCVN_MAX_ALIAS_QUERIES_PER_ACCESS)) |
| return (void *)-1; |
| |
| if (last_vuse_ptr) |
| *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 = current_info->references->find_slot_with_hash (vr, hash, NO_INSERT); |
| if (!slot && current_info == optimistic_info) |
| 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; |
| 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); |
| } |
| |
| static vn_nary_op_t vn_nary_op_insert_stmt (gimple *stmt, tree result); |
| static unsigned mprts_hook_cnt; |
| |
| /* Hook for maybe_push_res_to_seq, lookup the expression in the VN tables. */ |
| |
| static tree |
| vn_lookup_simplify_result (code_helper rcode, tree type, tree *ops_) |
| { |
| if (!rcode.is_tree_code ()) |
| return NULL_TREE; |
| tree *ops = ops_; |
| unsigned int length = TREE_CODE_LENGTH ((tree_code) rcode); |
| if (rcode == CONSTRUCTOR |
| /* ??? We're arriving here with SCCVNs view, decomposed CONSTRUCTOR |
| and GIMPLEs / match-and-simplifies, CONSTRUCTOR as GENERIC tree. */ |
| && TREE_CODE (ops_[0]) == CONSTRUCTOR) |
| { |
| length = CONSTRUCTOR_NELTS (ops_[0]); |
| ops = XALLOCAVEC (tree, length); |
| for (unsigned i = 0; i < length; ++i) |
| ops[i] = CONSTRUCTOR_ELT (ops_[0], i)->value; |
| } |
| vn_nary_op_t vnresult = NULL; |
| tree res = vn_nary_op_lookup_pieces (length, (tree_code) rcode, |
| type, ops, &vnresult); |
| /* We can end up endlessly recursing simplifications if the lookup above |
| presents us with a def-use chain that mirrors the original simplification. |
| See PR80887 for an example. Limit successful lookup artificially |
| to 10 times if we are called as mprts_hook. */ |
| if (res |
| && mprts_hook |
| && --mprts_hook_cnt == 0) |
| { |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| fprintf (dump_file, "Resetting mprts_hook after too many " |
| "invocations.\n"); |
| mprts_hook = NULL; |
| } |
| return res; |
| } |
| |
| /* 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 (code_helper rcode, tree type, tree *ops, |
| 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; |
| mprts_hook_cnt = 9; |
| bool res = false; |
| switch (TREE_CODE_LENGTH ((tree_code) rcode)) |
| { |
| case 1: |
| res = gimple_resimplify1 (NULL, &rcode, type, ops, vn_valueize); |
| break; |
| case 2: |
| res = gimple_resimplify2 (NULL, &rcode, type, ops, vn_valueize); |
| break; |
| case 3: |
| res = gimple_resimplify3 (NULL, &rcode, type, ops, vn_valueize); |
| break; |
| } |
| mprts_hook = NULL; |
| gimple *new_stmt = NULL; |
| if (res |
| && gimple_simplified_result_is_gimple_val (rcode, ops)) |
| /* The expression is already available. */ |
| result = ops[0]; |
| else |
| { |
| tree val = vn_lookup_simplify_result (rcode, type, ops); |
| if (!val && insert) |
| { |
| gimple_seq stmts = NULL; |
| result = maybe_push_res_to_seq (rcode, type, ops, &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_INFO_GET (result)->valnum = result; |
| VN_INFO (result)->value_id = get_next_value_id (); |
| gimple_seq_add_stmt_without_update (&VN_INFO (result)->expr, |
| new_stmt); |
| VN_INFO (result)->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->result == NULL_TREE); |
| nary->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 if (current_info == optimistic_info) |
| { |
| current_info = valid_info; |
| vn_nary_op_insert_stmt (new_stmt, result); |
| current_info = optimistic_info; |
| } |
| else |
| vn_nary_op_insert_stmt (new_stmt, result); |
| 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 (code_helper rcode, tree type, tree *ops) |
| { |
| return vn_nary_build_or_lookup_1 (rcode, type, ops, 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 > 3) |
| return NULL_TREE; |
| tree ops[3]; |
| memcpy (ops, nary->op, sizeof (tree) * nary->length); |
| return vn_nary_build_or_lookup_1 (nary->opcode, nary->type, ops, false); |
| } |
| |
| |
| /* 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 *vr_, |
| bool *disambiguate_only) |
| { |
| vn_reference_t vr = (vn_reference_t)vr_; |
| gimple *def_stmt = SSA_NAME_DEF_STMT (vuse); |
| tree base = ao_ref_base (ref); |
| HOST_WIDE_INT offset, maxsize; |
| static vec<vn_reference_op_s> lhs_ops; |
| ao_ref lhs_ref; |
| bool lhs_ref_ok = false; |
| |
| /* If the reference is based on a parameter that was determined as |
| pointing to readonly memory it doesn't change. */ |
| if (TREE_CODE (base) == MEM_REF |
| && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME |
| && SSA_NAME_IS_DEFAULT_DEF (TREE_OPERAND (base, 0)) |
| && bitmap_bit_p (const_parms, |
| SSA_NAME_VERSION (TREE_OPERAND (base, 0)))) |
| { |
| *disambiguate_only = true; |
| return NULL; |
| } |
| |
| /* 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); |
| copy_reference_ops_from_ref (lhs, &lhs_ops); |
| lhs_ops = valueize_refs_1 (lhs_ops, &valueized_anything); |
| 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, true)) |
| { |
| *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. |
| Note that we don't need to worry about partial overlapping |
| accesses as we then can use TBAA to disambiguate against the |
| clobbering statement when looking up a load (thus the |
| VN_WALKREWRITE guard). */ |
| if (vn_walk_kind == VN_WALKREWRITE |
| && is_gimple_reg_type (TREE_TYPE (lhs)) |
| && types_compatible_p (TREE_TYPE (lhs), vr->type)) |
| { |
| tree *saved_last_vuse_ptr = last_vuse_ptr; |
| /* Do not update last_vuse_ptr in vn_reference_lookup_2. */ |
| 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), 0, vr); |
| /* Need to restore vr->vuse and vr->hashcode. */ |
| vr->vuse = saved_vuse; |
| vr->hashcode = saved_hashcode; |
| 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)) |
| 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 (*disambiguate_only) |
| return (void *)-1; |
| |
| offset = ref->offset; |
| maxsize = ref->max_size; |
| |
| /* If we cannot constrain the size of the reference we cannot |
| test if anything kills it. */ |
| if (maxsize == -1) |
| return (void *)-1; |
| |
| /* 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_fits_uhwi_p (gimple_call_arg (def_stmt, 2)) |
| && TREE_CODE (gimple_call_arg (def_stmt, 0)) == ADDR_EXPR) |
| { |
| tree ref2 = TREE_OPERAND (gimple_call_arg (def_stmt, 0), 0); |
| tree base2; |
| HOST_WIDE_INT offset2, size2, maxsize2; |
| bool reverse; |
| base2 = get_ref_base_and_extent (ref2, &offset2, &size2, &maxsize2, |
| &reverse); |
| size2 = tree_to_uhwi (gimple_call_arg (def_stmt, 2)) * 8; |
| if ((unsigned HOST_WIDE_INT)size2 / 8 |
| == tree_to_uhwi (gimple_call_arg (def_stmt, 2)) |
| && maxsize2 != -1 |
| && operand_equal_p (base, base2, 0) |
| && offset2 <= offset |
| && offset2 + size2 >= offset + maxsize) |
| { |
| tree val = build_zero_cst (vr->type); |
| 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; |
| HOST_WIDE_INT offset2, size2, maxsize2; |
| bool reverse; |
| base2 = get_ref_base_and_extent (gimple_assign_lhs (def_stmt), |
| &offset2, &size2, &maxsize2, &reverse); |
| if (maxsize2 != -1 |
| && operand_equal_p (base, base2, 0) |
| && offset2 <= offset |
| && offset2 + size2 >= offset + maxsize) |
| { |
| 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 (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 |
| && maxsize % BITS_PER_UNIT == 0 |
| && offset % 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, maxsize2; |
| bool reverse; |
| base2 = get_ref_base_and_extent (gimple_assign_lhs (def_stmt), |
| &offset2, &size2, &maxsize2, &reverse); |
| if (!reverse |
| && maxsize2 != -1 |
| && maxsize2 == size2 |
| && size2 % BITS_PER_UNIT == 0 |
| && offset2 % BITS_PER_UNIT == 0 |
| && operand_equal_p (base, base2, 0) |
| && offset2 <= offset |
| && offset2 + size2 >= offset + maxsize) |
| { |
| /* 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); |
| len = native_encode_expr (gimple_assign_rhs1 (def_stmt), |
| buffer, sizeof (buffer)); |
| if (len > 0) |
| { |
| 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) |
| && ref->size != TYPE_PRECISION (vr->type)) |
| type = build_nonstandard_integer_type (ref->size, |
| TYPE_UNSIGNED (type)); |
| tree val = native_interpret_expr (type, |
| buffer |
| + ((offset - offset2) |
| / BITS_PER_UNIT), |
| ref->size / 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 (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; |
| HOST_WIDE_INT offset2, size2, maxsize2; |
| bool reverse; |
| base2 = get_ref_base_and_extent (gimple_assign_lhs (def_stmt), |
| &offset2, &size2, &maxsize2, |
| &reverse); |
| if (!reverse |
| && maxsize2 != -1 |
| && maxsize2 == size2 |
| && operand_equal_p (base, base2, 0) |
| && offset2 <= offset |
| && offset2 + size2 >= offset + maxsize |
| /* ??? 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) |
| || ref->size == TYPE_PRECISION (vr->type)) |
| && ref->size % BITS_PER_UNIT == 0) |
| { |
| code_helper rcode = BIT_FIELD_REF; |
| tree ops[3]; |
| ops[0] = SSA_VAL (gimple_assign_rhs1 (def_stmt)); |
| ops[1] = bitsize_int (ref->size); |
| ops[2] = bitsize_int (offset - offset2); |
| tree val = vn_nary_build_or_lookup (rcode, vr->type, ops); |
| 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 (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; |
| HOST_WIDE_INT maxsize2; |
| 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); |
| maxsize2 = lhs_ref.max_size; |
| if (maxsize2 == -1 |
| || (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. */ |
| HOST_WIDE_INT extra_off = 0; |
| if (j == 0 && i >= 0 |
| && lhs_ops[0].opcode == MEM_REF |
| && lhs_ops[0].off != -1) |
| { |
| if (lhs_ops[0].off == vr->operands[i].off) |
| i--, j--; |
| else if (vr->operands[i].opcode == MEM_REF |
| && 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 (extra_off != 0) |
| { |
| if (rhs.length () < 2 |
| || rhs[0].opcode != MEM_REF |
| || rhs[0].off == -1) |
| return (void *)-1; |
| rhs[0].off += extra_off; |
| rhs[0].op0 = int_const_binop (PLUS_EXPR, rhs[0].op0, |
| build_int_cst (TREE_TYPE (rhs[0].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 (ref->size != r.size) |
| return (void *)-1; |
| *ref = r; |
| |
| /* Do not update last seen VUSE after translating. */ |
| 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 (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) |
| && tree_fits_uhwi_p (gimple_call_arg (def_stmt, 2))) |
| { |
| tree lhs, rhs; |
| ao_ref r; |
| HOST_WIDE_INT rhs_offset, copy_size, lhs_offset; |
| vn_reference_op_s op; |
| HOST_WIDE_INT at; |
| |
| /* Only handle non-variable, addressable refs. */ |
| if (ref->size != maxsize |
| || offset % BITS_PER_UNIT != 0 |
| || ref->size % BITS_PER_UNIT != 0) |
| 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 = SSA_VAL (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 |
| && tree_fits_uhwi_p (TREE_OPERAND (tem, 1))) |
| { |
| lhs = TREE_OPERAND (tem, 0); |
| if (TREE_CODE (lhs) == SSA_NAME) |
| lhs = SSA_VAL (lhs); |
| lhs_offset += tree_to_uhwi (TREE_OPERAND (tem, 1)); |
| } |
| 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 = SSA_VAL (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 |
| && tree_fits_uhwi_p (TREE_OPERAND (tem, 1))) |
| { |
| rhs = TREE_OPERAND (tem, 0); |
| rhs_offset += tree_to_uhwi (TREE_OPERAND (tem, 1)); |
| } |
| 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; |
| |
| copy_size = tree_to_uhwi (gimple_call_arg (def_stmt, 2)); |
| |
| /* The bases of the destination and the references have to agree. */ |
| if ((TREE_CODE (base) != MEM_REF |
| && !DECL_P (base)) |
| || (TREE_CODE (base) == MEM_REF |
| && (TREE_OPERAND (base, 0) != lhs |
| || !tree_fits_uhwi_p (TREE_OPERAND (base, 1)))) |
| || (DECL_P (base) |
| && (TREE_CODE (lhs) != ADDR_EXPR |
| || TREE_OPERAND (lhs, 0) != base))) |
| return (void *)-1; |
| |
| at = offset / BITS_PER_UNIT; |
| if (TREE_CODE (base) == MEM_REF) |
| at += tree_to_uhwi (TREE_OPERAND (base, 1)); |
| /* If the access is completely outside of the memcpy destination |
| area there is no aliasing. */ |
| if (lhs_offset >= at + maxsize / BITS_PER_UNIT |
| || lhs_offset + copy_size <= at) |
| return NULL; |
| /* And the access has to be contained within the memcpy destination. */ |
| if (lhs_offset > at |
| || lhs_offset + copy_size < at + maxsize / BITS_PER_UNIT) |
| 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 (ref->size != r.size) |
| return (void *)-1; |
| *ref = r; |
| |
| /* Do not update last seen VUSE after translating. */ |
| 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; |
| vn_walk_kind = kind; |
| if (ao_ref_init_from_vn_reference (&r, set, type, vr1.operands)) |
| *vnresult = |
| (vn_reference_t)walk_non_aliased_vuses (&r, vr1.vuse, |
| vn_reference_lookup_2, |
| vn_reference_lookup_3, |
| vuse_ssa_val, &vr1); |
| 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. */ |
| |
| tree |
| vn_reference_lookup (tree op, tree vuse, vn_lookup_kind kind, |
| vn_reference_t *vnresult, bool tbaa_p) |
| { |
| 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 = tbaa_p ? get_alias_set (op) : 0; |
| 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; |
| /* 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); |
| if (! tbaa_p) |
| r.ref_alias_set = r.base_alias_set = 0; |
| vn_walk_kind = kind; |
| wvnresult = |
| (vn_reference_t)walk_non_aliased_vuses (&r, vr1.vuse, |
| vn_reference_lookup_2, |
| vn_reference_lookup_3, |
| vuse_ssa_val, &vr1); |
| 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->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, and return the resulting reference structure we created. */ |
| |
| static vn_reference_t |
| vn_reference_insert (tree op, tree result, tree vuse, tree vdef) |
| { |
| vn_reference_s **slot; |
| vn_reference_t vr1; |
| bool tem; |
| |
| vr1 = current_info->references_pool->allocate (); |
| 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) : NULL_TREE; |
| vr1->operands = valueize_shared_reference_ops_from_ref (op, &tem).copy (); |
| vr1->type = TREE_TYPE (op); |
| 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 = current_info->references->find_slot_with_hash (vr1, vr1->hashcode, |
| INSERT); |
| |
| /* Because we lookup stores using vuses, and value number failures |
| using the vdefs (see visit_reference_op_store for how and why), |
| it's possible that on failure we may try to insert an already |
| inserted store. This is not wrong, there is no ssa name for a |
| store that we could use as a differentiator anyway. Thus, unlike |
| the other lookup functions, you cannot gcc_assert (!*slot) |
| here. */ |
| |
| /* But free the old slot in case of a collision. */ |
| if (*slot) |
| free_reference (*slot); |
| |
| *slot = vr1; |
| return 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 = current_info->references_pool->allocate (); |
| vr1->value_id = value_id; |
| vr1->vuse = vuse ? SSA_VAL (vuse) : NULL_TREE; |
| vr1->operands = valueize_refs (operands); |
| vr1->type = type; |
| 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 = current_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); |
| if (*slot) |
| free_reference (*slot); |
| |
| *slot = 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->op[0] = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0); |
| vno->op[1] = TREE_OPERAND (gimple_assign_rhs1 (stmt), 1); |
| vno->op[2] = TREE_OPERAND (gimple_assign_rhs1 (stmt), 2); |
| break; |
| |
| case CONSTRUCTOR: |
| vno->length = CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt)); |
| for (i = 0; i < vno->length; ++i) |
| vno->op[i] = CONSTRUCTOR_ELT (gimple_assign_rhs1 (stmt), i)->value; |
| break; |
| |
| default: |
| gcc_checking_assert (!gimple_assign_single_p (stmt)); |
| vno->length = gimple_num_ops (stmt) - 1; |
| for (i = 0; i < vno->length; ++i) |
| vno->op[i] = gimple_op (stmt, i + 1); |
| } |
| } |
| |
| /* Compute the hashcode for VNO and look for it in the hash table; |
| 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 operation is NULL. VNRESULT will contain the |
| vn_nary_op_t from the hashtable if it exists. */ |
| |
| static tree |
| vn_nary_op_lookup_1 (vn_nary_op_t vno, vn_nary_op_t *vnresult) |
| { |
| vn_nary_op_s **slot; |
| |
| if (vnresult) |
| *vnresult = NULL; |
| |
| vno->hashcode = vn_nary_op_compute_hash (vno); |
| slot = current_info->nary->find_slot_with_hash (vno, vno->hashcode, |
| NO_INSERT); |
| if (!slot && current_info == optimistic_info) |
| slot = valid_info->nary->find_slot_with_hash (vno, vno->hashcode, |
| NO_INSERT); |
| if (!slot) |
| return NULL_TREE; |
| if (vnresult) |
| *vnresult = *slot; |
| return (*slot)->result; |
| } |
| |
| /* Lookup a n-ary operation by its pieces 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 operation |
| is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable |
| if it exists. */ |
| |
| tree |
| vn_nary_op_lookup_pieces (unsigned int length, enum tree_code code, |
| tree type, tree *ops, vn_nary_op_t *vnresult) |
| { |
| vn_nary_op_t vno1 = XALLOCAVAR (struct vn_nary_op_s, |
| sizeof_vn_nary_op (length)); |
| init_vn_nary_op_from_pieces (vno1, length, code, type, ops); |
| return vn_nary_op_lookup_1 (vno1, vnresult); |
| } |
| |
| /* 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 operation |
| is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable |
| if it exists. */ |
| |
| tree |
| vn_nary_op_lookup (tree op, vn_nary_op_t *vnresult) |
| { |
| vn_nary_op_t vno1 |
| = XALLOCAVAR (struct vn_nary_op_s, |
| sizeof_vn_nary_op (TREE_CODE_LENGTH (TREE_CODE (op)))); |
| init_vn_nary_op_from_op (vno1, op); |
| return vn_nary_op_lookup_1 (vno1, vnresult); |
| } |
| |
| /* Lookup the rhs of STMT 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. VNRESULT will contain the |
| vn_nary_op_t from the hashtable if it exists. */ |
| |
| tree |
| vn_nary_op_lookup_stmt (gimple *stmt, vn_nary_op_t *vnresult) |
| { |
| vn_nary_op_t vno1 |
| = XALLOCAVAR (struct vn_nary_op_s, |
| sizeof_vn_nary_op (vn_nary_length_from_stmt (stmt))); |
| init_vn_nary_op_from_stmt (vno1, stmt); |
| return vn_nary_op_lookup_1 (vno1, vnresult); |
| } |
| |
| /* Allocate a vn_nary_op_t with LENGTH operands on STACK. */ |
| |
| static vn_nary_op_t |
| alloc_vn_nary_op_noinit (unsigned int length, struct obstack *stack) |
| { |
| return (vn_nary_op_t) obstack_alloc (stack, sizeof_vn_nary_op (length)); |
| } |
| |
| /* Allocate and initialize a vn_nary_op_t on CURRENT_INFO's |
| obstack. */ |
| |
| static vn_nary_op_t |
| alloc_vn_nary_op (unsigned int length, tree result, unsigned int value_id) |
| { |
| vn_nary_op_t vno1 = alloc_vn_nary_op_noinit (length, |
| ¤t_info->nary_obstack); |
| |
| vno1->value_id = value_id; |
| vno1->length = length; |
| vno1->result = result; |
| |
| return vno1; |
| } |
| |
| /* Insert VNO into TABLE. If COMPUTE_HASH is true, then compute |
| VNO->HASHCODE first. */ |
| |
| static vn_nary_op_t |
| vn_nary_op_insert_into (vn_nary_op_t vno, vn_nary_op_table_type *table, |
| bool compute_hash) |
| { |
| vn_nary_op_s **slot; |
| |
| if (compute_hash) |
| vno->hashcode = vn_nary_op_compute_hash (vno); |
| |
| slot = table->find_slot_with_hash (vno, vno->hashcode, INSERT); |
| /* While we do not want to insert things twice it's awkward to |
| avoid it in the case where visit_nary_op pattern-matches stuff |
| and ends up simplifying the replacement to itself. We then |
| get two inserts, one from visit_nary_op and one from |
| vn_nary_build_or_lookup. |
| So allow inserts with the same value number. */ |
| if (*slot && (*slot)->result == vno->result) |
| return *slot; |
| |
| gcc_assert (!*slot); |
| |
| *slot = vno; |
| return vno; |
| } |
| |
| /* Insert a n-ary operation into the current hash table using it's |
| pieces. Return the vn_nary_op_t structure we created and put in |
| the hashtable. */ |
| |
| vn_nary_op_t |
| vn_nary_op_insert_pieces (unsigned int length, enum tree_code code, |
| tree type, tree *ops, |
| tree result, unsigned int value_id) |
| { |
| vn_nary_op_t vno1 = alloc_vn_nary_op (length, result, value_id); |
| init_vn_nary_op_from_pieces (vno1, length, code, type, ops); |
| return vn_nary_op_insert_into (vno1, current_info->nary, true); |
| } |
| |
| /* Insert OP into the current hash table with a value number of |
| RESULT. Return the vn_nary_op_t structure we created and put in |
| the hashtable. */ |
| |
| vn_nary_op_t |
| vn_nary_op_insert (tree op, tree result) |
| { |
| unsigned length = TREE_CODE_LENGTH (TREE_CODE (op)); |
| vn_nary_op_t vno1; |
| |
| vno1 = alloc_vn_nary_op (length, result, VN_INFO (result)->value_id); |
| init_vn_nary_op_from_op (vno1, op); |
| return vn_nary_op_insert_into (vno1, current_info->nary, true); |
| } |
| |
| /* Insert the rhs of STMT into the current hash table with a value number of |
| RESULT. */ |
| |
| static vn_nary_op_t |
| vn_nary_op_insert_stmt (gimple *stmt, tree result) |
| { |
| vn_nary_op_t vno1 |
| = alloc_vn_nary_op (vn_nary_length_from_stmt (stmt), |
| result, VN_INFO (result)->value_id); |
| init_vn_nary_op_from_stmt (vno1, stmt); |
| return vn_nary_op_insert_into (vno1, current_info->nary, true); |
| } |
| |
| /* Compute a hashcode for PHI operation VP1 and return it. */ |
| |
| static inline hashval_t |
| vn_phi_compute_hash (vn_phi_t vp1) |
| { |
| inchash::hash hstate (vp1->phiargs.length () > 2 |
| ? vp1->block->index : vp1->phiargs.length ()); |
| tree phi1op; |
| tree type; |
| edge e; |
| edge_iterator ei; |
| |
| /* If all PHI arguments are constants we need to distinguish |
| the PHI node via its type. */ |
| type = vp1->type; |
| hstate.merge_hash (vn_hash_type (type)); |
| |
| FOR_EACH_EDGE (e, ei, vp1->block->preds) |
| { |
| /* Don't hash backedge values they need to be handled as VN_TOP |
| for optimistic value-numbering. */ |
| if (e->flags & EDGE_DFS_BACK) |
| continue; |
| |
| phi1op = vp1->phiargs[e->dest_idx]; |
| if (phi1op == VN_TOP) |
| continue; |
| inchash::add_expr (phi1op, hstate); |
| } |
| |
| return hstate.end (); |
| } |
| |
| |
| /* Return true if COND1 and COND2 represent the same condition, set |
| *INVERTED_P if one needs to be inverted to make it the same as |
| the other. */ |
| |
| static bool |
| cond_stmts_equal_p (gcond *cond1, tree lhs1, tree rhs1, |
| gcond *cond2, tree lhs2, tree rhs2, bool *inverted_p) |
| { |
| enum tree_code code1 = gimple_cond_code (cond1); |
| enum tree_code code2 = gimple_cond_code (cond2); |
| |
| *inverted_p = false; |
| if (code1 == code2) |
| ; |
| else if (code1 == swap_tree_comparison (code2)) |
| std::swap (lhs2, rhs2); |
| else if (code1 == invert_tree_comparison (code2, HONOR_NANS (lhs2))) |
| *inverted_p = true; |
| else if (code1 == invert_tree_comparison |
| (swap_tree_comparison (code2), HONOR_NANS (lhs2))) |
| { |
| std::swap (lhs2, rhs2); |
| *inverted_p = true; |
| } |
| else |
| return false; |
| |
| return ((expressions_equal_p (lhs1, lhs2) |
| && expressions_equal_p (rhs1, rhs2)) |
| || (commutative_tree_code (code1) |
| && expressions_equal_p (lhs1, rhs2) |
| && expressions_equal_p (rhs1, lhs2))); |
| } |
| |
| /* Compare two phi entries for equality, ignoring VN_TOP arguments. */ |
| |
| static int |
| vn_phi_eq (const_vn_phi_t const vp1, const_vn_phi_t const vp2) |
| { |
| if (vp1->hashcode != vp2->hashcode) |
| return false; |
| |
| if (vp1->block != vp2->block) |
| { |
| if (vp1->phiargs.length () != vp2->phiargs.length ()) |
| return false; |
| |
| switch (vp1->phiargs.length ()) |
| { |
| case 1: |
| /* Single-arg PHIs are just copies. */ |
| break; |
| |
| case 2: |
| { |
| /* Rule out backedges into the PHI. */ |
| if (vp1->block |