Message ID | 1446146302-17002-2-git-send-email-alan.lawrence@arm.com |
---|---|
State | New |
Headers | show |
On 10/29/2015 01:18 PM, Alan Lawrence wrote: > This patch just teaches DOM that ARRAY_REFs can be equivalent to MEM_REFs (with > pointer type to the array element type). > > gcc/ChangeLog: > > * tree-ssa-dom.c (dom_normalize_single_rhs): New. > (dom_normalize_gimple_stmt): New. > (lookup_avail_expr): Call dom_normalize_gimple_stmt. Has this been tested? Do you have tests where it can be shown to make a difference independent of the changes to tree-sra.c? The implementation looks fine, I just want to have some basic tests in the testsuite that show the benefit of this normalization. Similarly for patch #2. Interestingly enough we had code that made that kind of transformation during gimplification eons ago. Presumably it was ripped out at some point because of the differences in aliasing properties. Jeff
On Fri, Oct 30, 2015 at 6:35 AM, Jeff Law <law@redhat.com> wrote: > On 10/29/2015 01:18 PM, Alan Lawrence wrote: >> >> This patch just teaches DOM that ARRAY_REFs can be equivalent to MEM_REFs >> (with >> pointer type to the array element type). >> >> gcc/ChangeLog: >> >> * tree-ssa-dom.c (dom_normalize_single_rhs): New. >> (dom_normalize_gimple_stmt): New. >> (lookup_avail_expr): Call dom_normalize_gimple_stmt. > > Has this been tested? Do you have tests where it can be shown to make a > difference independent of the changes to tree-sra.c? > > The implementation looks fine, I just want to have some basic tests in the > testsuite that show the benefit of this normalization. Err, I think the implementation is extremely wasteful ... > Similarly for patch #2. Interestingly enough we had code that made that kind > of transformation during gimplification eons ago. Presumably it was ripped > out at some point because of the differences in aliasing properties. Please have a look at how SCCVN handles variants of memory references. You might even want to re-use it's copy_reference_ops_from_ref implementation (and reference hashing). Note that SCCVN needs to be able to reconstruct a tree expression from its representation (for PRE) which DOM needs not, so DOM might use a simpler form. The basic idea is to accumulate constant offset handled_components into a "offset component". Thus a[2].i -> (&a)->offset(8 + offsetof(i)) MEM_REF[&a, 8].i -> (&a)->offset(8 + offsetof(i)) for DOM you can probably do the copy_reference_ops_from_ref work on-the-fly for hashing and comparing. The main point will be to forgo with the DOM way of hashing/comparing for memory references. Richard. > > > Jeff
diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c index 38cceff..fca8a80 100644 --- a/gcc/tree-ssa-dom.c +++ b/gcc/tree-ssa-dom.c @@ -1897,6 +1897,72 @@ vuse_eq (ao_ref *, tree vuse1, unsigned int cnt, void *data) return NULL; } +/* Return the normal form of EXPR, the gimple_assign_rhs1 of a GIMPLE_SINGLE_RHS + assignment, or NULL_TREE if EXPR is already in normal form. + The normal form is such that if two expressions normalize to trees that are + operand_equal_p, then dominator optimizations can replace one by the value + produced by the other. + It is not necessary that expressions with equal canonical forms are + equivalent in all other situations, e.g. aliasing. */ + +static tree +dom_normalize_single_rhs (tree expr) +{ + switch (TREE_CODE (expr)) + { + case ARRAY_REF: + { + tree index = TREE_OPERAND (expr, 1); + tree low_bound = array_ref_low_bound (expr); + if (!TREE_CONSTANT (index) || !TREE_CONSTANT (low_bound)) + return NULL_TREE; + + if (! integer_zerop (low_bound)) + index = fold_build2 (MINUS_EXPR, TREE_TYPE (index), index, low_bound); + + tree esz = array_ref_element_size (expr); + gcc_assert (TREE_CONSTANT (esz)); + tree offset = fold_build2 (MULT_EXPR, sizetype, index, esz); + + offset = fold_convert (build_pointer_type (TREE_TYPE (expr)), offset); + + tree base = TREE_OPERAND (expr, 0); + base = build_fold_addr_expr (base); + + return fold_build2 (MEM_REF, TREE_TYPE (expr), base, offset); + } + default: + return NULL_TREE; + } +} + +/* Return the normal form of STMT, or STMT if it is already normalized. */ + +static gimple * +dom_normalize_gimple_stmt (gimple *stmt) +{ + if (gimple_code (stmt) == GIMPLE_ASSIGN) + { + enum tree_code rhs_code = gimple_assign_rhs_code (stmt); + if (get_gimple_rhs_class (rhs_code) == GIMPLE_SINGLE_RHS) + if (tree nrhs = dom_normalize_single_rhs (gimple_assign_rhs1 (stmt))) + { + tree lhs = gimple_assign_lhs (stmt); + /* Exchanged statements, which are never part of the CFG, + can have invalid LHS. */ + gimple *defstmt = 0; + if (TREE_CODE (lhs) == SSA_NAME) + defstmt = SSA_NAME_DEF_STMT (lhs); + gassign *new_stmt = gimple_build_assign (lhs, nrhs); + if (TREE_CODE (lhs) == SSA_NAME) + SSA_NAME_DEF_STMT (lhs) = defstmt; + gimple_set_vuse (new_stmt, gimple_vuse (stmt)); + return new_stmt; + } + } + return stmt; +} + /* Search for an existing instance of STMT in the AVAIL_EXPRS_STACK table. If found, return its LHS. Otherwise insert STMT in the table and return NULL_TREE. @@ -1918,7 +1984,7 @@ lookup_avail_expr (gimple *stmt, bool insert, else lhs = gimple_get_lhs (stmt); - class expr_hash_elt element (stmt, lhs); + class expr_hash_elt element (dom_normalize_gimple_stmt (stmt), lhs); if (dump_file && (dump_flags & TDF_DETAILS)) {