public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug tree-optimization/29944]  New: should do more loops transformations to enable more biv widening
@ 2006-11-22 19:20 amylaar at gcc dot gnu dot org
  2006-11-22 19:23 ` [Bug tree-optimization/29944] " amylaar at gcc dot gnu dot org
  0 siblings, 1 reply; 2+ messages in thread
From: amylaar at gcc dot gnu dot org @ 2006-11-22 19:20 UTC (permalink / raw)
  To: gcc-bugs

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


^ permalink raw reply	[flat|nested] 2+ messages in thread

* [Bug tree-optimization/29944] should do more loops transformations to enable more biv widening
  2006-11-22 19:20 [Bug tree-optimization/29944] New: should do more loops transformations to enable more biv widening amylaar at gcc dot gnu dot org
@ 2006-11-22 19:23 ` amylaar at gcc dot gnu dot org
  0 siblings, 0 replies; 2+ messages in thread
From: amylaar at gcc dot gnu dot org @ 2006-11-22 19:23 UTC (permalink / raw)
  To: gcc-bugs



------- Comment #1 from amylaar at gcc dot gnu dot org  2006-11-22 19:23 -------
Created an attachment (id=12668)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=12668&action=view)
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.


-- 


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


^ permalink raw reply	[flat|nested] 2+ messages in thread

end of thread, other threads:[~2006-11-22 19:23 UTC | newest]

Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2006-11-22 19:20 [Bug tree-optimization/29944] New: should do more loops transformations to enable more biv widening amylaar at gcc dot gnu dot org
2006-11-22 19:23 ` [Bug tree-optimization/29944] " amylaar at gcc dot gnu dot org

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).