Re: Infering that the condition of a for loop is initially true?

[Richard Biener <richard dot guenther at gmail dot com>]

On Fri, Sep 15, 2017 at 12:07 AM, Jeff Law <law@redhat.com> wrote:
> On 09/14/2017 01:28 PM, Niels Möller wrote:
>> This is more of a question than a bug report, so I'm trying to send it
>> to the list rather than filing a bugzilla issue.
>>
>> I think it's quite common to write for- and while-loops where the
>> condition is always initially true. A simple example might be
>>
>> double average (const double *a, size_t n)
>> {
>>   double sum;
>>   size_t i;
>>
>>   assert (n > 0);
>>   for (i = 0, sum = 0; i < n; i++)
>>     sum += a[i];
>>   return sum / n;
>> }
>>
>> The programmer could do the microptimization to rewrite it as a
>> do-while-loop instead. It would be nice if gcc could infer that the
>> condition is initially true, and convert to a do-while loop
>> automatically.
>>
>> Converting to a do-while-loop should produce slightly better code,
>> omitting the typical jump to enter the loop at the end where the
>> condition is checked. It would also make analysis of where variables are
>> written more accurate, which is my main concern at the moment.
>>
>> My questions are:
>>
>> 1. Does gcc attempt to do this optimization?
> Yes.  It happens as a side effect of jump threading and there are also
> dedicated passes to rotate the loop.

The loop header copying does this.

>>
>> 2. If it does, how often does it succeed on loops in real programs?
> Often.  The net benefit is actually small though and sometimes this kind
> of loop rotation can impede vectorization.

Most loop optimizers do not deal well with loops that may not execute
or rather they do not handle number of iterations being computed as
"n or zero".  The vectorizer is an exception to this as it will simply
version the loop with the extra condition(s).

>
>>
>> 3. Can I help the compiler to do that inference?
> In general, I'd advise against it.  You end up with ugly code which
> works with specific versions of the compiler, but which needs regular
> tweaking as the internal implementations of various optimizers change
> over time.
>
>
>>
>> The code I had some trouble with is at
>> https://git.lysator.liu.se/nettle/nettle/blob/master/ecc-mod.c. A
>> simplified version with only the interesting code path would be
>>
>> void
>> ecc_mod (mp_size_t mn, mp_size_t bn, mp_limb_t *rp)
>> {
>>   mp_limb_t hi;
>>   mp_size_t sn = mn - bn;
>>   mp_size_t rn = 2*mn;
>>
>>   assert (bn < mn);
>>
>>   while (rn >= 2 * mn - bn)
> In this particular case (ignoring the assert), what you want is better
> jump threading exploiting range propagation.   But you have to be real
> careful here due to the potential overflow.
>
> I'd have to have a self-contained example to dig into what's really
> going on, but my suspicion is either overflow or fairly weak range data
> and simplification due to the symbolic ranges.
>
> Jeff
>