> -----Original Message-----
> From: Bin.Cheng [mailto:amker.ch...@gmail.com]
> Sent: Monday, December 09, 2013 1:15 PM
> To: Jeff Law
> Cc: Bin Cheng; gcc-patches List
> Subject: Re: [PATCH PR41488]Recognize more induction variables by
> simplifying PEELED chrec in scalar evolution
>
> On Mon, Dec 9, 2013 at 12:00 PM, Jeff Law <l...@redhat.com> wrote:
> > On 12/06/13 19:44, Bin.Cheng wrote:
> >>>
> >>> Right. Based on reading the archives, it looks like this stuff
> >>> is/was generated by PRE. I also suspect jump threading can create
> >>> them. There was talk of throttling PRE to leave things in a form
> >>> that the IV analysis could more easily digest, but I'm not sure if
> >>> that was ever completed.
> >>
> >>
> >> Also could just because it is coded in that way, just as the case I
> >> added in patch. I found real examples from ggc-page.c in GCC.
> >> But it's always good to cleanup input of an optimization, I presume
> >> that's why Richard tried to move IVOPT later before.
> >
> > Certainly. That possibility was mentioned as well in either 41488 or
> > elsewhere in my research.
> >
> >
> >>>
> >>> I assume tree_to_aff_combination_expand is relatively expensive,
> >>> thus the two approaches, one which avoids
> tree_to_aff_combination_expand.
> >>
> >> Considering the dump of case in the patch:
> >
> > [ snip ]
> > So it's also a case using the affine stuff gets you get a simpler
> > interface to express the value in terms you may be able match.
> Yeah.
>
> >
> >
> >>
> >> Another question, is it acceptable to add an parameter for
> >> tree_to_aff_combination_expand to limit the number of recursive call
> >> for it? Thus we don't need to expand to leaf node every time.
> >
> > If there's a compelling reason to limit the recursion, then I'd think
> > such a parameter would be reasonable.
> Not for now. Just come up this idea given that some recent patches also
use
> the interface to get back trace information and it's expensive. Maybe
> Richard have some comment here too.
>
> >
> >
> >
> >>
> >>>
> >>>
> >>> In add_old_iv_candidates, is it the case that the only time
> >>> SSA_NAME_DEF_STMT (def) is another PHI node is when it's one of
> >>> these affine
> >>
> >>
> >> I suppose. Actually IVOPT make an assert on IP_ORIGINAL candidates
> >> in function rewrite_use_nonlinear_expr, like:
> >
> > Well, the reason I ask is after your patch we'd be ignoring anything
> > where SSA_NAME_DEF_STMT (def) is a PHI node and not a PEELED_CHREC.
> I
> > want to make sure there aren't other expected cases where
> > SSA_NAME_DEF_STMT (def) is a PHI that we'd want to call
> add_candidate_1 for.
> >
> > It sounds like there aren't other cases you'd expect to see here where
> > SSA_NAME_DEF_STMT (defFFF) is a PHI.
> Yes.
>
> >
> >
> >> IVOPT adds original cand and tries to keep it the original IV is
> >> because it does have an updating statement. For IVs picked up by
> >> this patch, it doesn't have stepping statement, so no need/way to
> >> leaving it untouched. It will be represented by candidates for IVs
> >> from which it is peeled.
> >
> > Understood. Thanks for clarifying. The patch is fine for the trunk.
> Thanks very much for reviewing. Since Sebastian hasn't added any
> comments, I will change the patch as suggested by Richard before, then
> retest it, and check in the new version if it's ok.
>
Hi,
This is the new version patch computing the difference in tree affine then
comparing against integer_zero_node.
Bootstrap and test on current upstream. I will commit it if there is no
other objection.
Thanks,
bin
> >
> > jeff
>
>
>
> --
> Best Regards.
Index: gcc/tree-scalar-evolution.c
===================================================================
--- gcc/tree-scalar-evolution.c (revision 205688)
+++ gcc/tree-scalar-evolution.c (working copy)
@@ -280,6 +280,8 @@ along with GCC; see the file COPYING3. If not see
#include "tree-ssa.h"
#include "cfgloop.h"
#include "tree-chrec.h"
+#include "pointer-set.h"
+#include "tree-affine.h"
#include "tree-scalar-evolution.h"
#include "dumpfile.h"
#include "params.h"
@@ -1380,7 +1382,67 @@ follow_ssa_edge (struct loop *loop, gimple def, gi
}
+/* Pointer map used when simplifying PEELED_CHREC into POLYNOMIAL_CHREC. */
+static pointer_map_t *peeled_chrec_map;
+/* Simplify PEELED_CHREC represented by (init_cond, arg) in LOOP.
+ Handle below case and return the corresponding POLYNOMIAL_CHREC:
+
+ # i_17 = PHI <i_13(5), 0(3)>
+ # _20 = PHI <_5(5), start_4(D)(3)>
+ ...
+ i_13 = i_17 + 1;
+ _5 = start_4(D) + i_13;
+
+ Though variable _20 appears as a PEELED_CHREC in the form of
+ (start_4, _5)_LOOP, it's a POLYNOMIAL_CHREC like {start_4, 1}_LOOP.
+
+ See PR41488. */
+
+static tree
+simplify_peeled_chrec (struct loop *loop, tree arg, tree init_cond)
+{
+ aff_tree aff1, aff2;
+ tree ev, left, right, type, step_val;
+
+ ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, arg));
+ if (ev == NULL_TREE || TREE_CODE (ev) != POLYNOMIAL_CHREC)
+ return chrec_dont_know;
+
+ left = CHREC_LEFT (ev);
+ right = CHREC_RIGHT (ev);
+ type = TREE_TYPE (left);
+ step_val = chrec_fold_plus (type, init_cond, right);
+
+ /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
+ if "left" equals to "init + right". */
+ if (operand_equal_p (left, step_val, 0))
+ {
+ if (dump_file && (dump_flags & TDF_SCEV))
+ fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
+
+ return build_polynomial_chrec (loop->num, init_cond, right);
+ }
+
+ /* Try harder to check if they are equal. */
+ tree_to_aff_combination_expand (left, type, &aff1, &peeled_chrec_map);
+ tree_to_aff_combination_expand (step_val, type, &aff2, &peeled_chrec_map);
+ aff_combination_scale (&aff2, double_int_minus_one);
+ aff_combination_add (&aff1, &aff2);
+ left = fold_convert (type, aff_combination_to_tree (&aff1));
+
+ /* Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP
+ if "left" equals to "init + right". */
+ if (operand_equal_p (left, integer_zero_node, 0))
+ {
+ if (dump_file && (dump_flags & TDF_SCEV))
+ fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
+
+ return build_polynomial_chrec (loop->num, init_cond, right);
+ }
+ return chrec_dont_know;
+}
+
/* Given a LOOP_PHI_NODE, this function determines the evolution
function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. */
@@ -1392,6 +1454,7 @@ analyze_evolution_in_loop (gimple loop_phi_node,
tree evolution_function = chrec_not_analyzed_yet;
struct loop *loop = loop_containing_stmt (loop_phi_node);
basic_block bb;
+ static bool simplify_peeled_chrec_p = true;
if (dump_file && (dump_flags & TDF_SCEV))
{
@@ -1442,7 +1505,19 @@ analyze_evolution_in_loop (gimple loop_phi_node,
all the other iterations it has the value of ARG.
For the moment, PEELED_CHREC nodes are not built. */
if (res != t_true)
- ev_fn = chrec_dont_know;
+ {
+ ev_fn = chrec_dont_know;
+ /* Try to recognize POLYNOMIAL_CHREC which appears in
+ the form of PEELED_CHREC, but guard the process with
+ a bool variable to keep the analyzer from infinite
+ recurrence for real PEELED_RECs. */
+ if (simplify_peeled_chrec_p && TREE_CODE (arg) == SSA_NAME)
+ {
+ simplify_peeled_chrec_p = false;
+ ev_fn = simplify_peeled_chrec (loop, arg, init_cond);
+ simplify_peeled_chrec_p = true;
+ }
+ }
/* When there are multiple back edges of the loop (which in fact never
happens currently, but nevertheless), merge their evolutions. */
@@ -3086,6 +3161,8 @@ scev_initialize (void)
initialize_scalar_evolutions_analyzer ();
+ peeled_chrec_map = pointer_map_create ();
+
FOR_EACH_LOOP (loop, 0)
{
loop->nb_iterations = NULL_TREE;
@@ -3122,6 +3199,12 @@ scev_reset (void)
scev_reset_htab ();
+ if (peeled_chrec_map)
+ {
+ pointer_map_destroy (peeled_chrec_map);
+ peeled_chrec_map = NULL;
+ }
+
if (!current_loops)
return;
@@ -3209,6 +3292,11 @@ scev_finalize (void)
return;
htab_delete (scalar_evolution_info);
scalar_evolution_info = NULL;
+ if (peeled_chrec_map)
+ {
+ pointer_map_destroy (peeled_chrec_map);
+ peeled_chrec_map = NULL;
+ }
}
/* Returns true if the expression EXPR is considered to be too expensive
Index: gcc/testsuite/gcc.dg/tree-ssa/scev-7.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/scev-7.c (revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/scev-7.c (revision 0)
@@ -0,0 +1,18 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-sccp-scev" } */
+
+struct struct_t
+{
+ int* data;
+};
+
+void foo (struct struct_t* sp, int start, int end)
+{
+ int i;
+
+ for (i = 1000; i+start > end; i--)
+ sp->data[i+start] = 0;
+}
+
+/* { dg-final { scan-tree-dump-times "Simplify PEELED_CHREC into
POLYNOMIAL_CHREC" 1 "sccp" } } */
+/* { dg-final { cleanup-tree-dump "sccp" } } */
Index: gcc/testsuite/gcc.dg/pr41488.c
===================================================================
--- gcc/testsuite/gcc.dg/pr41488.c (revision 0)
+++ gcc/testsuite/gcc.dg/pr41488.c (revision 0)
@@ -0,0 +1,18 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-sccp-scev" } */
+
+struct struct_t
+{
+ int* data;
+};
+
+void foo (struct struct_t* sp, int start, int end)
+{
+ int i;
+
+ for (i = 0; i+start < end; i++)
+ sp->data[i+start] = 0;
+}
+
+/* { dg-final { scan-tree-dump-times "Simplify PEELED_CHREC into
POLYNOMIAL_CHREC" 1 "sccp" } } */
+/* { dg-final { cleanup-tree-dump "sccp" } } */
Index: gcc/tree-ssa-loop-ivopts.c
===================================================================
--- gcc/tree-ssa-loop-ivopts.c (revision 205688)
+++ gcc/tree-ssa-loop-ivopts.c (working copy)
@@ -2526,11 +2526,19 @@ add_old_iv_candidates (struct ivopts_data *data, s
/* Additionally record the possibility of leaving the original iv
untouched. */
def = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (data->current_loop));
- cand = add_candidate_1 (data,
- iv->base, iv->step, true, IP_ORIGINAL, NULL,
- SSA_NAME_DEF_STMT (def));
- cand->var_before = iv->ssa_name;
- cand->var_after = def;
+ /* Don't add candidate if it's from another PHI node because
+ it's an affine iv appearing in the form of PEELED_CHREC. */
+ phi = SSA_NAME_DEF_STMT (def);
+ if (gimple_code (phi) != GIMPLE_PHI)
+ {
+ cand = add_candidate_1 (data,
+ iv->base, iv->step, true, IP_ORIGINAL, NULL,
+ SSA_NAME_DEF_STMT (def));
+ cand->var_before = iv->ssa_name;
+ cand->var_after = def;
+ }
+ else
+ gcc_assert (gimple_bb (phi) == data->current_loop->header);
}
}
