[Bug tree-optimization/29944] New: should do more loops transformations to enable more biv widening

["amylaar at gcc dot gnu dot org" <gcc-bugzilla@gcc.gnu.org>]

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.


-- 
           Summary: should do more loops transformations to enable more biv
                    widening
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: amylaar at gcc dot gnu dot org
OtherBugsDependingO 29842
             nThis:


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=29944