This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH][PING] SCCVN alias oracle
- From: Richard Guenther <rguenther at suse dot de>
- To: gcc-patches at gcc dot gnu dot org
- Cc: dnovillo at google dot com
- Date: Fri, 14 Mar 2008 15:21:22 +0100 (CET)
- Subject: [PATCH][PING] SCCVN alias oracle
This patch adds an alias oracle to SCCVN (I stripped out all unrelated
parts that were either committed or are unnecessary for the SCCVN part
and moved generic functions to tree-dfa.c).
Bootstrapped and tested on x86_64-unknown-linux-gnu. Ok for trunk?
Thanks,
Richard.
2008-03-14 Richard Guenther <rguenther@suse.de>
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-7.c: New testcase.
* gcc.dg/tree-ssa/ssa-fre-8.c: Likewise.
* gcc.dg/tree-ssa/ssa-fre-9.c: Likewise.
* gcc.dg/tree-ssa/ssa-fre-10.c: Likewise.
* gcc.dg/tree-ssa/ssa-fre-11.c: Likewise.
* gcc.dg/tree-ssa/20031106-4.c: Remove XFAIL.
Index: trunk/gcc/tree-ssa-sccvn.c
===================================================================
*** trunk.orig/gcc/tree-ssa-sccvn.c 2008-03-14 13:24:42.000000000 +0100
--- trunk/gcc/tree-ssa-sccvn.c 2008-03-14 14:18:36.000000000 +0100
*************** valueize_vuses (VEC (tree, gc) *orig)
*** 646,651 ****
--- 646,719 ----
return orig;
}
+ /* Return the single reference statement defining all virtual uses
+ in VUSES or NULL_TREE, if there are multiple defining statements.
+ Take into account only definitions that alias REF if following
+ back-edges. */
+
+ static tree
+ get_def_ref_stmt_vuses (tree ref, VEC (tree, gc) *vuses)
+ {
+ tree def_stmt, vuse;
+ unsigned int i;
+
+ gcc_assert (VEC_length (tree, vuses) >= 1);
+
+ def_stmt = SSA_NAME_DEF_STMT (VEC_index (tree, vuses, 0));
+ if (TREE_CODE (def_stmt) == PHI_NODE)
+ {
+ /* We can only handle lookups over PHI nodes for a single
+ virtual operand. */
+ if (VEC_length (tree, vuses) == 1)
+ {
+ def_stmt = get_single_def_stmt_from_phi (ref, def_stmt);
+ goto cont;
+ }
+ else
+ return NULL_TREE;
+ }
+
+ /* Verify each VUSE reaches the same defining stmt. */
+ for (i = 1; VEC_iterate (tree, vuses, i, vuse); ++i)
+ {
+ tree tmp = SSA_NAME_DEF_STMT (vuse);
+ if (tmp != def_stmt)
+ return NULL_TREE;
+ }
+
+ /* Now see if the definition aliases ref, and loop until it does. */
+ cont:
+ while (def_stmt
+ && TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT
+ && !get_call_expr_in (def_stmt)
+ && !refs_may_alias_p (ref, GIMPLE_STMT_OPERAND (def_stmt, 0)))
+ def_stmt = get_single_def_stmt_with_phi (ref, def_stmt);
+
+ return def_stmt;
+ }
+
+ /* 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. */
+
+ static tree
+ vn_reference_lookup_1 (vn_reference_t vr)
+ {
+ void **slot;
+ hashval_t hash;
+
+ hash = vr->hashcode;
+ slot = htab_find_slot_with_hash (current_info->references, vr,
+ hash, NO_INSERT);
+ if (!slot && current_info == optimistic_info)
+ slot = htab_find_slot_with_hash (valid_info->references, vr,
+ hash, NO_INSERT);
+ if (slot)
+ return ((vn_reference_t)*slot)->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. */
*************** valueize_vuses (VEC (tree, gc) *orig)
*** 653,673 ****
tree
vn_reference_lookup (tree op, VEC (tree, gc) *vuses)
{
- void **slot;
struct vn_reference_s vr1;
vr1.vuses = valueize_vuses (vuses);
vr1.operands = valueize_refs (shared_reference_ops_from_ref (op));
vr1.hashcode = vn_reference_compute_hash (&vr1);
! slot = htab_find_slot_with_hash (current_info->references, &vr1, vr1.hashcode,
! NO_INSERT);
! if (!slot && current_info == optimistic_info)
! slot = htab_find_slot_with_hash (valid_info->references, &vr1, vr1.hashcode,
! NO_INSERT);
! if (!slot)
! return NULL_TREE;
! return ((vn_reference_t)*slot)->result;
}
/* Insert OP into the current hash table with a value number of
--- 721,754 ----
tree
vn_reference_lookup (tree op, VEC (tree, gc) *vuses)
{
struct vn_reference_s vr1;
+ tree result, def_stmt;
vr1.vuses = valueize_vuses (vuses);
vr1.operands = valueize_refs (shared_reference_ops_from_ref (op));
vr1.hashcode = vn_reference_compute_hash (&vr1);
! result = vn_reference_lookup_1 (&vr1);
!
! /* If there is a single defining statement for all virtual uses, we can
! use that, following virtual use-def chains. */
! if (!result
! && vr1.vuses
! && VEC_length (tree, vr1.vuses) >= 1
! && (def_stmt = get_def_ref_stmt_vuses (op, vr1.vuses))
! && TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT
! /* If there is a call involved, op must be assumed to
! be clobbered. */
! && !get_call_expr_in (def_stmt))
! {
! /* We are now at an aliasing definition for the vuses we want to
! look up. Re-do the lookup with the vdefs for this stmt. */
! vdefs_to_vec (def_stmt, &vuses);
! vr1.vuses = valueize_vuses (vuses);
! vr1.hashcode = vn_reference_compute_hash (&vr1);
! result = vn_reference_lookup_1 (&vr1);
! }
! return result;
}
/* Insert OP into the current hash table with a value number of
Index: trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-7.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-7.c 2008-03-14 13:33:05.000000000 +0100
***************
*** 0 ****
--- 1,26 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fdump-tree-fre-details" } */
+
+ struct
+ {
+ int x;
+ int y;
+ } S[100];
+
+ int z[100];
+
+ int
+ foo (int y)
+ {
+ int x;
+
+ S[5].x = 4;
+ S[5].y = 0;
+
+ x = S[5].x;
+
+ return (x);
+ }
+
+ /* { dg-final { scan-tree-dump "Replaced S\\\[5\\\].x with 4" "fre" } } */
+ /* { dg-final { cleanup-tree-dump "fre" } } */
Index: trunk/gcc/testsuite/gcc.dg/tree-ssa/20031106-4.c
===================================================================
*** trunk.orig/gcc/testsuite/gcc.dg/tree-ssa/20031106-4.c 2008-03-03 15:21:28.000000000 +0100
--- trunk/gcc/testsuite/gcc.dg/tree-ssa/20031106-4.c 2008-03-14 13:33:05.000000000 +0100
*************** void foo (struct s* r)
*** 26,30 ****
}
/* There should be no link_error calls. */
! /* { dg-final { scan-tree-dump-times "link_error" 0 "optimized" { xfail *-*-* } } } */
/* { dg-final { cleanup-tree-dump "optimized" } } */
--- 26,30 ----
}
/* There should be no link_error calls. */
! /* { dg-final { scan-tree-dump-times "link_error" 0 "optimized" } } */
/* { dg-final { cleanup-tree-dump "optimized" } } */
Index: trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-8.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-8.c 2008-03-14 13:33:05.000000000 +0100
***************
*** 0 ****
--- 1,26 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fdump-tree-fre-details" } */
+
+ struct
+ {
+ int x;
+ int y;
+ } S[100];
+
+ int z[100];
+
+ int
+ foo (int y)
+ {
+ int x;
+
+ S[5].x = 4;
+ S[5].y = 0;
+
+ x = S[5].x;
+
+ return (x);
+ }
+
+ /* { dg-final { scan-tree-dump "Replaced S\\\[5\\\].x with 4" "fre" } } */
+ /* { dg-final { cleanup-tree-dump "fre" } } */
Index: trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-10.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-10.c 2008-03-14 13:33:05.000000000 +0100
***************
*** 0 ****
--- 1,29 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fstrict-aliasing -fno-tree-sra --param max-aliased-vops=0 --param max-fields-for-field-sensitive=0 -fdump-tree-fre-details" } */
+
+ /* Should be optimized, propagating &a into (*p)[i] with parameters
+ --param max-aliased-vops=0 --param max-fields-for-field-sensitive=0
+ which means max 1 VOP per stmt and no SFTs. */
+
+ /* For this testcase we need TBAA to work. */
+
+ struct Foo
+ {
+ void *data;
+ int size;
+ };
+ void foo(double (*q)[4], struct Foo *tmp1)
+ {
+ double a[4];
+ int i;
+ tmp1->data = &a;
+ tmp1->size = 4;
+ for (i=0; i<4; ++i)
+ {
+ double (*p)[4] = tmp1->data;
+ (*p)[i] = (*q)[i];
+ }
+ }
+
+ /* { dg-final { scan-tree-dump "Replaced .* with &a" "fre" } } */
+ /* { dg-final { cleanup-tree-dump "fre" } } */
Index: trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-9.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-9.c 2008-03-14 13:33:05.000000000 +0100
***************
*** 0 ****
--- 1,31 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fno-tree-sra --param max-aliased-vops=0 --param max-fields-for-field-sensitive=0 -fdump-tree-fre-details" } */
+
+ /* Should be optimized, propagating &a into (*p)[i] with parameters
+ --param max-aliased-vops=0 --param max-fields-for-field-sensitive=0
+ which means max 1 VOP per stmt and no SFTs. */
+
+ struct Foo
+ {
+ void *data;
+ double size;
+ };
+ void foo(double (*q)[4])
+ {
+ struct Foo tmp1;
+ double a[4];
+ int i;
+ tmp1.data = &a;
+ tmp1.size = 4;
+ for (i=0; i<4; ++i)
+ {
+ double (*p)[4] = tmp1.data;
+ (*p)[i] = (*q)[i];
+ /* We want a PHI for the VOP for accessing tmp1.data, so place
+ this store to tmp1 here. */
+ tmp1.size -= 1.0;
+ }
+ }
+
+ /* { dg-final { scan-tree-dump "Replaced .* with &a" "fre" } } */
+ /* { dg-final { cleanup-tree-dump "fre" } } */
Index: trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-11.c
===================================================================
*** /dev/null 1970-01-01 00:00:00.000000000 +0000
--- trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-11.c 2008-03-14 13:33:05.000000000 +0100
***************
*** 0 ****
--- 1,30 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fno-tree-sra --param max-aliased-vops=0 --param max-fields-for-field-sensitive=0 -fdump-tree-fre-details" } */
+
+ /* Should be optimized, propagating &a into (*p)[i] with parameters
+ --param max-aliased-vops=0 --param max-fields-for-field-sensitive=0
+ which means max 1 VOP per stmt and no SFTs. */
+
+ struct Foo
+ {
+ void *data;
+ double size;
+ };
+ void foo(double (*q)[4])
+ {
+ struct Foo tmp1;
+ double a[4];
+ int i;
+ tmp1.data = &a;
+ for (i=0; i<4; ++i)
+ {
+ double (*p)[4] = tmp1.data;
+ (*p)[i] = (*q)[i];
+ /* We want a PHI for the VOP for accessing tmp1.data, so place
+ this store to tmp1 here. */
+ tmp1.size -= 1.0;
+ }
+ }
+
+ /* { dg-final { scan-tree-dump "Replaced" "fre" } } */
+ /* { dg-final { cleanup-tree-dump "fre" } } */
Index: trunk/gcc/tree-dfa.c
===================================================================
*** trunk.orig/gcc/tree-dfa.c 2008-03-14 14:08:31.000000000 +0100
--- trunk/gcc/tree-dfa.c 2008-03-14 14:17:34.000000000 +0100
*************** stmt_references_abnormal_ssa_name (tree
*** 1046,1048 ****
--- 1046,1203 ----
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;
+
+ /* 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);
+ }
+ }
Index: trunk/gcc/tree-flow.h
===================================================================
*** trunk.orig/gcc/tree-flow.h 2008-03-12 14:46:55.000000000 +0100
--- trunk/gcc/tree-flow.h 2008-03-14 14:18:13.000000000 +0100
*************** extern tree make_rename_temp (tree, cons
*** 824,829 ****
--- 824,833 ----
extern void set_default_def (tree, tree);
extern tree gimple_default_def (struct function *, tree);
extern bool stmt_references_abnormal_ssa_name (tree);
+ extern bool refs_may_alias_p (tree, tree);
+ extern tree get_single_def_stmt (tree);
+ extern tree get_single_def_stmt_from_phi (tree, tree);
+ extern tree get_single_def_stmt_with_phi (tree, tree);
/* In tree-phinodes.c */
extern void reserve_phi_args_for_new_edge (basic_block);