From 896c8b96c5cf36090b62e5f1ba8ce7e49a4a53e5 Mon Sep 17 00:00:00 2001 From: Richard Guenther Date: Fri, 14 Mar 2008 17:05:48 +0000 Subject: re PR tree-optimization/34172 (Missed store ccp optimization) 2008-03-14 Richard Guenther PR tree-optimization/34172 * tree-flow.h (refs_may_alias_p): Declare. (get_single_def_stmt): Likewise. (get_single_def_stmt_from_phi): Likewise. (get_single_def_stmt_with_phi): Likewise. * tree-dfa.c (refs_may_alias_p): New function. (get_single_def_stmt): Likewise. (get_single_def_stmt_from_phi): Likewise. (get_single_def_stmt_with_phi): Likewise. * tree-ssa-sccvn.c (get_def_ref_stmt_vuses): New function. (vn_reference_lookup_1): New helper function. (vn_reference_lookup): Walk the virtual use-def chain to continue searching for a match if the def does not alias the reference we are looking for. * gcc.dg/tree-ssa/ssa-fre-11.c: New testcase. * gcc.dg/tree-ssa/ssa-fre-12.c: Likewise. * gcc.dg/tree-ssa/ssa-fre-13.c: Likewise. * gcc.dg/tree-ssa/ssa-fre-14.c: Likewise. * gcc.dg/tree-ssa/ssa-fre-15.c: Likewise. * gcc.dg/tree-ssa/20031106-4.c: Remove XFAIL. From-SVN: r133222 --- gcc/tree-dfa.c | 162 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 162 insertions(+) (limited to 'gcc/tree-dfa.c') diff --git a/gcc/tree-dfa.c b/gcc/tree-dfa.c index 346f6f3..3495816 100644 --- a/gcc/tree-dfa.c +++ b/gcc/tree-dfa.c @@ -1046,3 +1046,165 @@ stmt_references_abnormal_ssa_name (tree stmt) return false; } +/* Return true, if the two memory references REF1 and REF2 may alias. */ + +bool +refs_may_alias_p (tree ref1, tree ref2) +{ + tree base1, base2; + HOST_WIDE_INT offset1 = 0, offset2 = 0; + HOST_WIDE_INT size1 = -1, size2 = -1; + HOST_WIDE_INT max_size1 = -1, max_size2 = -1; + + gcc_assert ((SSA_VAR_P (ref1) + || handled_component_p (ref1) + || TREE_CODE (ref1) == INDIRECT_REF) + && (SSA_VAR_P (ref2) + || handled_component_p (ref2) + || TREE_CODE (ref2) == INDIRECT_REF)); + + /* Defer to TBAA if possible. */ + if (flag_strict_aliasing + && !alias_sets_conflict_p (get_alias_set (ref1), get_alias_set (ref2))) + return false; + + /* Decompose the references into their base objects and the access. */ + base1 = ref1; + if (handled_component_p (ref1)) + base1 = get_ref_base_and_extent (ref1, &offset1, &size1, &max_size1); + base2 = ref2; + if (handled_component_p (ref2)) + base2 = get_ref_base_and_extent (ref2, &offset2, &size2, &max_size2); + + /* If both references are based on different variables, they cannot alias. + If both references are based on the same variable, they cannot alias if + if the accesses do not overlap. */ + if (SSA_VAR_P (base1) + && SSA_VAR_P (base2) + && (!operand_equal_p (base1, base2, 0) + || !ranges_overlap_p (offset1, max_size1, offset2, max_size2))) + return false; + + /* If both references are through pointers and both pointers are equal + then they do not alias if the accesses do not overlap. */ + if (TREE_CODE (base1) == INDIRECT_REF + && TREE_CODE (base2) == INDIRECT_REF + && operand_equal_p (TREE_OPERAND (base1, 0), + TREE_OPERAND (base2, 0), 0) + && !ranges_overlap_p (offset1, max_size1, offset2, max_size2)) + return false; + + return true; +} + +/* Given a stmt STMT that references memory, return the single stmt + that is reached by following the VUSE -> VDEF link. Returns + NULL_TREE, if there is no single stmt that defines all VUSEs of + STMT. + Note that for a stmt with a single virtual operand this may return + a PHI node as well. Note that if all VUSEs are default definitions + this function will return an empty statement. */ + +tree +get_single_def_stmt (tree stmt) +{ + tree def_stmt = NULL_TREE; + tree use; + ssa_op_iter iter; + + FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_VIRTUAL_USES) + { + tree tmp = SSA_NAME_DEF_STMT (use); + + /* ??? This is too simplistic for multiple virtual operands + reaching different PHI nodes of the same basic blocks or for + reaching all default definitions. */ + if (def_stmt + && def_stmt != tmp + && !(IS_EMPTY_STMT (def_stmt) + && IS_EMPTY_STMT (tmp))) + return NULL_TREE; + + def_stmt = tmp; + } + + return def_stmt; +} + +/* Given a PHI node of virtual operands, tries to eliminate cyclic + reached definitions if they do not alias REF and returns the + defining statement of the single virtual operand that flows in + from a non-backedge. Returns NULL_TREE if such statement within + the above conditions cannot be found. */ + +tree +get_single_def_stmt_from_phi (tree ref, tree phi) +{ + tree def_arg = NULL_TREE; + int i; + + /* Find the single PHI argument that is not flowing in from a + back edge and verify that the loop-carried definitions do + not alias the reference we look for. */ + for (i = 0; i < PHI_NUM_ARGS (phi); ++i) + { + tree arg = PHI_ARG_DEF (phi, i); + tree def_stmt; + + if (!(PHI_ARG_EDGE (phi, i)->flags & EDGE_DFS_BACK)) + { + /* Multiple non-back edges? Do not try to handle this. */ + if (def_arg) + return NULL_TREE; + def_arg = arg; + continue; + } + + /* Follow the definitions back to the original PHI node. Bail + out once a definition is found that may alias REF. */ + def_stmt = SSA_NAME_DEF_STMT (arg); + do + { + if (TREE_CODE (def_stmt) != GIMPLE_MODIFY_STMT + || refs_may_alias_p (ref, GIMPLE_STMT_OPERAND (def_stmt, 0))) + return NULL_TREE; + /* ??? This will only work, reaching the PHI node again if + there is a single virtual operand on def_stmt. */ + def_stmt = get_single_def_stmt (def_stmt); + if (!def_stmt) + return NULL_TREE; + } + while (def_stmt != phi); + } + + return SSA_NAME_DEF_STMT (def_arg); +} + +/* Return the single reference statement defining all virtual uses + on STMT or NULL_TREE, if there are multiple defining statements. + Take into account only definitions that alias REF if following + back-edges when looking through a loop PHI node. */ + +tree +get_single_def_stmt_with_phi (tree ref, tree stmt) +{ + switch (NUM_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_USES)) + { + case 0: + gcc_unreachable (); + + case 1: + { + tree def_stmt = SSA_NAME_DEF_STMT (SINGLE_SSA_TREE_OPERAND + (stmt, SSA_OP_VIRTUAL_USES)); + /* We can handle lookups over PHI nodes only for a single + virtual operand. */ + if (TREE_CODE (def_stmt) == PHI_NODE) + return get_single_def_stmt_from_phi (ref, def_stmt); + return def_stmt; + } + + default: + return get_single_def_stmt (stmt); + } +} -- cgit v1.1