Bug 32806 - Missing optimization to remove backward dependencies
Summary: Missing optimization to remove backward dependencies
Status: NEW
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.3.0
: P3 enhancement
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords: missed-optimization
Depends on:
Blocks:
 
Reported: 2007-07-18 09:58 UTC by Ira Rosen
Modified: 2007-07-19 18:09 UTC (History)
2 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2007-07-19 18:07:11


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Ira Rosen 2007-07-18 09:58:32 UTC
for (i=0; i<N; i++)
{
  D[i] = A[i] + Y;
  A[i+1] = B[i] + X;
}

Even though, this loop contains a backward-carried dependence between A[i+1] and A[i], it is vectorizable  - the stmts of the loop should be interchanged to get:

for (i=0; i<N; i++)
{
  A[i+1] = B[i] + X;
  D[i] = A[i] + Y;
}

which will be vectorizable once the pacth in PR 32377 (comment #14) is committed. 

The interchange is possible since there is no loop-independent dependence between the stmts. This requires working with a dependence graph when vectorizing, or have a separate optimization before the vectorizer to take care of this.

Ira
Comment 1 Richard Biener 2007-07-19 18:07:11 UTC
Confirmed.