This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


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.

> 
> 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.


> 
> 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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]