Page MenuHomePhabricator

[LoopReroll] Introduce the concept of DAGRootSets.

Authored by jmolloy on Feb 5 2015, 8:09 AM.



A DAGRootSet models an induction variable being used in a rerollable
loop. For example:

x[i*3+0] = y1
x[i*3+1] = y2
x[i*3+2] = y3

Base instruction -> i*3
                /    |     \
            ST[y1]  +1     +2  <-- Roots
                     |      |
                   ST[y2] ST[y3]

There may be multiple DAGRootSets, for example:

x[i*2+0] = ...   (1)
x[i*2+1] = ...   (1)
x[i*2+4] = ...   (2)
x[i*2+5] = ...   (2)
x[(i+1234)*2+5678] = ... (3)
x[(i+1234)*2+5679] = ... (3)

This concept is similar to the "Scale" member used previously, but allows
multiple independent sets of roots based off the same induction variable.

Diff Detail


Event Timeline

jmolloy updated this revision to Diff 19406.Feb 5 2015, 8:09 AM
jmolloy retitled this revision from to [LoopReroll] Introduce the concept of DAGRootSets..
jmolloy updated this object.
jmolloy edited the test plan for this revision. (Show Details)
jmolloy added a reviewer: hfinkel.
jmolloy set the repository for this revision to rL LLVM.
jmolloy added a subscriber: Unknown Object (MLST).
hfinkel added inline comments.Feb 6 2015, 1:53 PM

Please also explain here how the loop will be rerolled (by adding multiple induction variables to the rerolled loop, one for each DAGRootSet).


Please add a comment here explaining how this is used (which I gather is to prune the search space when looking for arithmetic expressions on the induction variables).


IIRC, you need to adjust where the loop starts once you reroll it (and how validation works, etc. because your iteration space now starts at some negative number instead of zero).


Please add a comment explaining the algebra here.

You're comparing:

ADR_next == Roots[Last] + (Roots[0] - ADR)

which is:

ADR + ADR_step == Roots[Last] + Roots[0] - ADR

which is:
2*ADR + ADR_step == Roots[Last] + Roots[0]
which I don't understand.

Why don't you compare ADR->getStepRecurrence() to SE->getMinusSCEV(SE->getSCEV(V.Roots[LastIdx]), SE->getSCEV(V.Roots[0])) (or something like that)?

jmolloy updated this revision to Diff 19586.Feb 9 2015, 8:54 AM

Updated to address all of Hal's comments.

jmolloy updated this revision to Diff 19680.Feb 10 2015, 7:25 AM

Slight update - be less conservative.

hfinkel accepted this revision.Feb 10 2015, 8:30 AM
hfinkel edited edge metadata.

LGTM, thanks!

This revision is now accepted and ready to land.Feb 10 2015, 8:30 AM
jmolloy closed this revision.Feb 11 2015, 1:22 AM