[PATCH PR41488]Recognize more induction variables by simplifying PEELED chrec in scalar evolution

[Richard Biener]

On Thu, Dec 12, 2013 at 6:55 AM, bin.cheng <bin.cheng@arm.com> wrote:
>
>
>> -----Original Message-----
>> From: Richard Biener [mailto:richard.guenther@gmail.com]
>> Sent: Wednesday, December 11, 2013 6:04 PM
>> To: Jakub Jelinek
>> Cc: Bin.Cheng; Jeff Law; Bin Cheng; gcc-patches List
>> Subject: Re: [PATCH PR41488]Recognize more induction variables by
>> simplifying PEELED chrec in scalar evolution
>>
>> On Wed, Dec 11, 2013 at 9:50 AM, Jakub Jelinek <jakub@redhat.com> wrote:
>> > On Wed, Dec 11, 2013 at 04:31:55PM +0800, Bin.Cheng wrote:
>> >> Thank both of you for being patient on this patch.
>> >> I went through the documentation quickly and realized that I have to
>> >> modify pointer-map structure to make it recognized by GC (maybe more
>> >
>> > Changing pointer_map at this point is IMHO not appropriate.
>> >
>> >> work suggested by Jakub).  It seems I shouldn't include that task in
>> >> this patch at this stage 3, I am thinking just call free_affine*
>> >> function in the place it is created for SCEV.  Of course, that makes
>> >> it more expensive.
>> >
>> > Perhaps you could call free_affine_expand_cache say from
>> > analyze_scalar_evolution, that is the innermost enclosing exported API
>> > that indirectly calls your new code, but it seems it is also called
>> > recursively from analyze_scalar_evolution_1 or functions it calls.
>> > So maybe you'd need to rename analyze_scalar_evolution to
>> > analyze_scalar_evolution_2 and adjust some calls to
>> > analyze_scalar_evolution to the latter in tree-scalar-evolution.c, and
>> > add analyze_scalar_evolution wrapper that calls
>> analyze_scalar_evolution_2 and free_affine_expand_cache.
>> > Whether this would work depends on detailed analysis of the
>> > tree-scalar-evolution.c callgraph, there are tons of functions, most
>> > of them static, and the question is if there is a single non-static
>> > (or at most a few of them) function that cover all calls to your new
>> > code in the static functions it (indirectly) calls, i.e. if there
>> > isn't any other external entry point that might call your new code
>> > without doing free_affine_expand_cache afterwards.
>> >
>> > If you can find that, I'd say it would be the safest thing to do.
>> > But let's see what say Richard thinks about it too.
>>
>> I think keeping the SCEV cache live over multiple passes is fragile (we do
> re-
>> use SSA names and passes do not appropriately call scev_reset[_htab] in
> all
>> cases).
>>
>> With fixing that the easiest approach is to associate a affine-expand
> cache
>> with the scev info.
>>
>> Without that there isn't a very good solution other than discarding the
> cache
>> after each expansion at the point you use it.  The SCEV cache should
>> effectively make most of the affine expansion caching moot (but you can
> try
>> instrumenting that to verify it).
>>
>> That is, I suggest to try freeing the cache right after the second
>> tree_to_aff_combination_expand.
>>
>> Btw,
>>
>> +  /* 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))
>>
>> you don't need aff_combination_to_tree, simply check
>>
>>  aff1.n == 0 && aff1.offset.is_zero ()
>>
>> (you may want to add aff_combination_zero_p or even
>> aff_combination_equal_p)
>
> Hi,
> This is the new version patch with bug 59445 fixed and calling free_affine
> stuff just after it is used.  I also added aff_combination_zero_p as
> suggested.
> The change in add_old_iv_candidates is unnecessary now, since the previous
> version patch triggered the assertion, I just leave it here as an additional
> check.
>
> At last, apology that I missed java in bootstrap before.
>
> Bootstrap and test on x86/x86_64,  arm is still ongoing.  Is it OK if tests
> pass.

Ok.

Thanks,
Richard.

> Thanks,
> bin
>
> 2013-12-12  Bin Cheng  <bin.cheng@arm.com>
>
>         PR tree-optimization/58296
>         PR tree-optimization/41488
>         * tree-scalar-evolution.c: Include necessary header files.
>         (simplify_peeled_chrec): New function.
>         (analyze_evolution_in_loop): New static variable.
>         Call simplify_peeled_chrec.
>         * tree-ssa-loop-ivopts.c (mark_bivs): Don't mark peeled IV as biv.
>         (add_old_iv_candidates): Don't add candidate for peeled IV.
>         * tree-affine.h (aff_combination_zero_p): New function.
>
> gcc/testsuite/ChangeLog
> 2013-12-12  Bin Cheng  <bin.cheng@arm.com>
>
>         PR tree-optimization/58296
>         PR tree-optimization/41488
>         * gcc.dg/tree-ssa/scev-7.c: New test.
>         * gcc.dg/pr41488.c: New test.
>         * g++.dg/pr59445.C: New test.