This is the mail archive of the
mailing list for the GCC project.
Re: Infering that the condition of a for loop is initially true?
- From: Jeff Law <law at redhat dot com>
- To: Niels Möller <nisse at lysator dot liu dot se>, gcc at gcc dot gnu dot org
- Date: Thu, 14 Sep 2017 16:07:34 -0600
- Subject: Re: Infering that the condition of a for loop is initially true?
- Authentication-results: sourceware.org; auth=none
- Authentication-results: ext-mx07.extmail.prod.ext.phx2.redhat.com; dmarc=none (p=none dis=none) header.from=redhat.com
- Authentication-results: ext-mx07.extmail.prod.ext.phx2.redhat.com; spf=fail smtp.mailfrom=law at redhat dot com
- Dmarc-filter: OpenDMARC Filter v1.3.2 mx1.redhat.com 7ABB0C04B30E
- References: <firstname.lastname@example.org>
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
> 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
> 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
> 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.