Re: [PING] [PATCH] Optional alternative base_expr in finding basis for CAND_REFs

[Yufeng Zhang]

On 12/05/13 13:21, Bill Schmidt wrote:
On Thu, 2013-12-05 at 12:02 +0000, Yufeng Zhang wrote:
On 12/04/13 13:08, Bill Schmidt wrote:
On Wed, 2013-12-04 at 11:26 +0100, Richard Biener wrote:
[snip]

I'm not sure what you're suggesting that he use get_inner_reference on
at this point.  At the point where the affine machinery is invoked, the
memory reference was already expanded with get_inner_reference, and
there was no basis involving the SSA name produced as the base.  The
affine machinery is invoked on that SSA name to see if it is hiding
another base.  There's no additional memory reference to use
get_inner_reference on, just potentially some pointer arithmetic.

That said, if we have real compile-time issues, we should hold off on
this patch for this release.

Yufeng, please time some reasonably large benchmarks (some version of
SPECint or similar) and report back here before the patch goes in.

I've got some build time data for SPEC2Kint.

On x86_64 the -O3 builds take about 4m7.5s with or without the patch
(consistent over 3 samples).  The difference of the -O3 build time on
arm cortex-a15 is also within 2 seconds.

The bootstrapping time on x86_64 is 134m48.040s without the patch and
134m46.889s with the patch; this data is preliminary as I only sampled
once, but the difference of the bootstrapping time on arm cortex-a15 is
also within 5 seconds.

I can further time SPEC2006int if necessary.

I've also prepared a patch to further reduce the number of calls to
tree-affine expansion, by checking whether or not the passed-in BASE in
get_alternative_base () is simply an SSA_NAME of a declared variable.
Please see the inlined patch below.

Thanks,
Yufeng


diff --git a/gcc/gimple-ssa-strength-reduction.c
b/gcc/gimple-ssa-strength-reduction.c
index 26502c3..2984f06 100644
--- a/gcc/gimple-ssa-strength-reduction.c
+++ b/gcc/gimple-ssa-strength-reduction.c
@@ -437,13 +437,22 @@ get_alternative_base (tree base)

     if (result == NULL)
       {
-      tree expr;
-      aff_tree aff;
+      tree expr = NULL;
+      gimple def = NULL;

-      tree_to_aff_combination_expand (base, TREE_TYPE (base),
-&aff,&name_expansions);
-      aff.offset = tree_to_double_int (integer_zero_node);
-      expr = aff_combination_to_tree (&aff);
+      if (TREE_CODE (base) == SSA_NAME)
+     def = SSA_NAME_DEF_STMT (base);
+
+      /* Avoid calling expensive tree-affine expansion if BASE
+         is just an SSA_NAME of, e.g. a para_decl.  */
+      if (!def || (is_gimple_assign (def)&&  gimple_assign_lhs (def) ==
base))

Well, that just isn't right.  !def indicates you have a parameter, so
why call tree_to_aff_combination_expand in that case?  Just forget this
addition and check for flag_expensive_optimizations as Richard suggested
in another branch of this thread.

I thought every SSA_NAME has its DEF_STMT, at least in the cases which I 
checked they are GIMPLE_NOPs; that's why I used !def to check for cases 
where BASE is not an SSA_NAME (bad programming habit I guess).

Anyway, I'll leave out this addition.

Previous version of the patch is ok with this change, and with a comment
added that we should eliminate this backtracking with better forward
analysis in a future release.

Thanks.  The following inlined diff is the incremental change.

Thanks again for your review and help.

Regards,
Yufeng


diff --git a/gcc/gimple-ssa-strength-reduction.c 
b/gcc/gimple-ssa-strength-reduction.c
index 26502c3..f406794 100644
--- a/gcc/gimple-ssa-strength-reduction.c
+++ b/gcc/gimple-ssa-strength-reduction.c
@@ -428,7 +428,10 @@ static struct pointer_map_t *alt_base_map;

 /* Given BASE, use the tree affine combiniation facilities to
    find the underlying tree expression for BASE, with any
-   immediate offset excluded.  */
+   immediate offset excluded.
+
+   N.B. we should eliminate this backtracking with better forward
+   analysis in a future release.  */

 static tree
 get_alternative_base (tree base)
@@ -556,7 +559,7 @@ find_basis_for_candidate (slsr_cand_t c)
        }
     }

-  if (!basis && c->kind == CAND_REF)
+  if (flag_expensive_optimizations && !basis && c->kind == CAND_REF)
     {
       tree alt_base_expr = get_alternative_base (c->base_expr);
       if (alt_base_expr)
@@ -641,7 +644,7 @@ alloc_cand_and_find_basis (enum cand_kind kind, 
gimple gs, tree base,
     c->basis = find_basis_for_candidate (c);

   record_potential_basis (c, base);
-  if (kind == CAND_REF)
+  if (flag_expensive_optimizations && kind == CAND_REF)
     {
       tree alt_base = get_alternative_base (base);
       if (alt_base)