Bug 35272 - Loop distribution fails to distribute
Summary: Loop distribution fails to distribute
Status: NEW
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.4.0
: P3 enhancement
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords: missed-optimization
: 43428 (view as bug list)
Depends on:
Blocks: vectorizer
  Show dependency tree / graph
 
Reported: 2008-02-21 06:41 UTC by Ira Rosen
Modified: 2021-12-28 05:24 UTC (History)
4 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2021-12-27 00:00:00

Attachments
Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this bug.
Description Ira Rosen 2008-02-21 06:41:31 UTC 
Loop distribution (from the patch http://gcc.gnu.org/ml/gcc-patches/2007-12/msg00215.html) fails to distribute the following loop:

for (i = 2; i <= n; ++i)
 {
   a[i] += c[i] * d[i];
   b[i] = a[i] + d[i] + b[i - 1];
 }

dumping "FIXME: Loop 1 not distributed: failed to build the RDG."

(After distribution the first loop will be vectorizable).
Comment 1 Richard Biener 2012-12-05 09:45:24 UTC 
On trunk we would distribute a variant with a[i] = c[i] ... if the partitions
would not be fused because of having similar memory accesses.  With the
reduction in place we only form a single useful partition because of the
dependences.

Thus, confirmed (we can build the RDG now), for

  _5 = a[i_19];
  _6 = c[i_19];
  _7 = d[i_19];
  _8 = _6 * _7;
  _9 = _5 + _8;
  a[i_19] = _9;
  _11 = _7 + _9;
  _12 = i_19 + -1;
  _13 = b[_12];
  _14 = _11 + _13;
  b[i_19] = _14;

we'd have to use a[i_19] in the loop storing to b but instead we
only try re-compute it via retaining

  _5 = a[i_19];
  _6 = c[i_19];
  _7 = d[i_19];
  _8 = _6 * _7;
  _9 = _5 + _8;

which of course does not work (a[i_19] is not available).
Comment 2 Richard Biener 2012-12-05 09:51:09 UTC 
*** Bug 43428 has been marked as a duplicate of this bug. ***