Re: [PATCH GCC]Improve bound information in loop niter analysis

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

Thanks for all your reviews.

On Fri, Aug 14, 2015 at 4:17 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Tue, Jul 28, 2015 at 11:36 AM, Bin Cheng <bin.cheng@arm.com> wrote:
>> Hi,
>> Loop niter computes inaccurate bound information for different loops.  This
>> patch is to improve it by using loop initial condition in
>> determine_value_range.  Generally, loop niter is computed by subtracting
>> start var from end var in loop exit condition.  Moreover, loop bound is
>> computed using value range information of both start and end variables.
>> Basic idea of this patch is to check if loop initial condition implies more
>> range information for both start/end variables.  If yes, we refine range
>> information and use that to compute loop bound.
>> With this improvement, more accurate loop bound information is computed for
>> test cases added by this patch.
>
> +      c0 = fold_convert (type, c0);
> +      c1 = fold_convert (type, c1);
> +
> +      if (operand_equal_p (var, c0, 0))
>
> I believe if c0 is not already of type type operand-equal_p will never succeed.
It's quite specific case targeting comparison between var and it's
range bounds.  Given c0 is in form of "var + offc0", then the
comparison "var + offc0 != range bounds" doesn't have any useful
information.  Maybe useless type conversion can be handled here
though, it might be even corner case.

>
> (side-note: we should get rid of the GMP use, that's expensive and now we
> have wide-int available which should do the trick as well)
>
> +         /* Case of comparing with the bounds of the type.  */
> +         if (TYPE_MIN_VALUE (type)
> +             && operand_equal_p (c1, TYPE_MIN_VALUE (type), 0))
> +           cmp = GT_EXPR;
> +         if (TYPE_MAX_VALUE (type)
> +             && operand_equal_p (c1, TYPE_MAX_VALUE (type), 0))
> +           cmp = LT_EXPR;
>
> don't use TYPE_MIN/MAX_VALUE.  Instead use the types precision
> and all wide_int operations (see match.pd wi::max_value use).
Done.

>
> +  else if (!operand_equal_p (var, varc0, 0))
> +    goto end_2;
>
> ick - goto.  We need sth like a auto_mpz class with a destructor.
Label end_2 removed.

>
> struct auto_mpz
> {
>   auto_mpz () { mpz_init (m_val); }
>   ~auto_mpz () { mpz_clear (m_val); }
>   mpz& operator() { return m_val; }
>   mpz m_val;
> };
>
>> Is it OK?
>
> I see the code follows existing practice in niter analysis even though
> my overall plan was to transition its copying of value-range related
> optimizations to use VRP infrastructure.
Yes, I think it's easy to push it to VRP infrastructure.  Actually
from the name of the function, it's more vrp related.  For now, the
function is called only by bound_difference, not so many as vrp
queries.  We need cache facility in vrp otherwise it would be
expensive.

>
> I'm still ok with improving the existing code on the basis that I won't
> get to that for GCC 6.
>
> So - ok with the TYPE_MIN/MAX_VALUE change suggested above.
>
> Refactoring with auto_mpz welcome.
That will be an independent patch, so I skipped it in this one.

New version attached.  Bootstrap and test on x86_64.

Thanks,
bin
>
> Thanks,
> RIchard.
>
>> Thanks,
>> bin
>>
>> 2015-07-28  Bin Cheng  <bin.cheng@arm.com>
>>
>>         * tree-ssa-loop-niter.c (refine_value_range_using_guard): New.
>>         (determine_value_range): Call refine_value_range_using_guard for
>>         each loop initial condition to improve value range.
>>
>> gcc/testsuite/ChangeLog
>> 2015-07-28  Bin Cheng  <bin.cheng@arm.com>
>>
>>         * gcc.dg/tree-ssa/loop-bound-1.c: New test.
>>         * gcc.dg/tree-ssa/loop-bound-3.c: New test.
>>         * gcc.dg/tree-ssa/loop-bound-5.c: New test.

Attachment: improve-loop-bound-analysis-20150817.txt
Description: Text document