Bug 29944 - should do more loops transformations to enable more biv widening
Summary: should do more loops transformations to enable more biv widening
Status: NEW
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.3.0
: P3 normal
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords: missed-optimization
Depends on:
Blocks: 29842
  Show dependency treegraph
 
Reported: 2006-11-22 19:20 UTC by Jorn Wolfgang Rennecke
Modified: 2019-03-05 09:24 UTC (History)
1 user (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2019-03-05 00:00:00


Attachments
3.4.3 patch (8.34 KB, patch)
2006-11-22 19:23 UTC, Jorn Wolfgang Rennecke
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Jorn Wolfgang Rennecke 2006-11-22 19:20:25 UTC
At the moment, we only do biv (basic induction variable) widening when we
can argue that overflow cuases undefined behaviour, as in:

int
f (int start, int end, int x, int y)
{
  short i;

  for (i = start; i < end; i++)
    x <<= y;
  return x;
}

However, for -ftrapv, we get the wrong result (it doesn't trap in case of
overflow), and for -fwrapv, no biv widening is done.

Likewise, if the biv is unsigned, as in:

int
f (int start, int end, int x, int y)
{
  unsigned short i;

  for (i = start; i < end; i++)
    x <<= y;
  return x;
}

we fail to do any biv widening.

Using suitable loop transformations, biv widening can be done safely without
a change in observable program behaviour.

If a cheap vector addition is available that adds units as wide as the
original biv size, proper updates of a narrow unsigned biv can be obtained
by making sure the biv is properly zero-extended at the loop entry,
and using the vector addition to do the increment.

If no cheap vector addition is available, or if defined operation on a
narrow signed biv is required, biv widening can be done safely by
transforming the loop into two nested loops, where end value of the inner
loop is calculated so that if the biv should overflow, the value of the biv
during the last iteration will be the value prior to the overflow.
The outer loop can then, if required, trap, calculate the new biv
value to archive wrap-around semantics, and continue looping.
Comment 1 Jorn Wolfgang Rennecke 2006-11-22 19:23:28 UTC
Created attachment 12668 [details]
3.4.3 patch

For illustration, this patch implements this optimization in a 3.4.3 based
compiler.

Because the 4.x series uses a completely different infrastructure, we
must re-implement this from scratch.