Re: [PATCH GCC]Improve loop bound info by simplifying conversions in iv base

["Bin.Cheng" <amker dot cheng at gmail dot com>]

On Fri, Aug 14, 2015 at 4:28 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Tue, Jul 28, 2015 at 11:38 AM, Bin Cheng <bin.cheng@arm.com> wrote:
>> Hi,
>> For now, SCEV may compute iv base in the form of "(signed T)((unsigned
>> T)base + step))".  This complicates other optimizations/analysis depending
>> on SCEV because it's hard to dive into type conversions.  For many cases,
>> such type conversions can be simplified with additional range information
>> implied by loop initial conditions.  This patch does such simplification.
>> With simplified iv base, loop niter analysis can compute more accurate bound
>> information since sensible value range can be derived for "base+step".  For
>> example, accurate loop bound&may_be_zero information is computed for cases
>> added by this patch.
>> The code is actually borrowed from loop_exits_before_overflow.  Moreover,
>> with simplified iv base, the second case handled in that function now
>> becomes the first case.  I didn't remove that part of code because it may(?)
>> still be visited in scev analysis itself and simple_iv isn't an interface
>> for that.
>>
>> Is it OK?
>
> It looks quite special given it only handles a very specific pattern.  Did you
> do any larger collecting of statistics on how many times this triggers,
> esp. how many times simplify_using_initial_conditions succeeds and
> how many times not?  This function is somewhat expensive.
Yes, this is corner case targeting induction variables of small signed
types, just like added test cases.  We need to convert it to unsigned,
do the stepping, and convert back.  I collected statistics for gcc
bootstrap and spec2k6.  The function is called about 400-500 times in
both case.  About 45% of calls succeeded in bootstrap, while only ~3%
succeeded in spec2k6.

I will prepare a new version patch if you think it's worthwhile in
terms of compilation cost and benefit.

Thanks,
bin
>
> +      || !operand_equal_p (iv->step,
> +                          fold_convert (type,
> +                                        TREE_OPERAND (e, 1)), 0))
>
> operand_equal_p can handle sign-differences in integer constants,
> no need to fold_convert here.  Also if you know that you are comparing
> integer constants please use tree_int_cst_equal_p.
>
> +      extreme = lower_bound_in_type (type, type);
>
> that's a strange function to call here (with two same types).  Looks like
> just wide_int_to_tree (type, wi::max/min_value (type)).
>
> +  extreme = fold_build2 (MINUS_EXPR, type, extreme, iv->step);
>
> so as iv->step is an INTEGER_CST please do this whole thing using
> wide_ints and only build trees here:
>
> +  e = fold_build2 (code, boolean_type_node, base, extreme);
>
> Thanks,
> Richard.
>
>> Thanks,
>> bin
>>
>> 2015-07-28  Bin Cheng  <bin.cheng@arm.com>
>>
>>         * tree-ssa-loop-niter.c (tree_simplify_using_condition): Export
>>         the interface.
>>         * tree-ssa-loop-niter.h (tree_simplify_using_condition): Declare.
>>         * tree-scalar-evolution.c (simple_iv): Simplify type conversions
>>         in iv base using loop initial conditions.
>>
>> gcc/testsuite/ChangeLog
>> 2015-07-28  Bin Cheng  <bin.cheng@arm.com>
>>
>>         * gcc.dg/tree-ssa/loop-bound-2.c: New test.
>>         * gcc.dg/tree-ssa/loop-bound-4.c: New test.
>>         * gcc.dg/tree-ssa/loop-bound-6.c: New test.