Differential D42417
Re-apply [SCEV] Fix isLoopEntryGuardedByCond usage Authored by skatkov on Jan 23 2018, 5:20 AM.
Details [SCEV] Fix isLoopEntryGuardedByCond usage ScalarEvolution::isKnownPredicate invokes isLoopEntryGuardedByCond without check To bugs additionally fixed:
Diff Detail Event Timeline
Comment Actions Hi Sanjoy, The number of buildbot failures were so big but I remember the following case (if I do not miss anything):
I hope it helps.
Comment Actions I've revisited all usages of this method and think that https://reviews.llvm.org/rL323077 can be reapplied with two changes:
Other places look good: the values coming as parameters there seem to be invariants avaliable on loop entry.
Comment Actions Doing right now.. building will take some time. When I created this test and debugged it, it really failed and isLoopEntryGuardedByCond returned true and select simplified... Comment Actions As I remember the story was as follows: L was outer loop. Something like this but I need to check... Comment Actions $ ~/work/llvm/build/buildDA/bin/opt -indvars ./inner-loop.ll -S | ~/work/llvm/build/buildDA/bin/FileCheck ./inner-loop.ll ^ Comment Actions Sorry, I incorrectly assumed that this was fixing a failed assert so I was looking for a crash. I am able to reproduce the crash after reverting this change but adding back the isAvailableAtLoopEntry assert only. Moreover, I think the assert is sound. Having said that, I think this is a generic bug with how isKnownPredicate handles predicates between add recurrences. What it used to do before your change doesn't make sense to me for three reasons:
So I think the right fix involves doing the following:
Where First(X, L) is defined as "in X replace all add recs with loop L with their initial value" and PostInc(X, L) is defined as "in X replace all add recs with loop L with their post-inc value". We may already have SCEV rewriters that do this. What do you think? Comment Actions I agree in general, just few notions.
Even more, I think it's useful to have a helper function that returns the set of loops on which the current SCEV may depend. These are loops on which its SCEVAddRecs depend on.
It should not be deepest loops, but lowest by domination. For example: for (i1 = 0; i1 != e1; i1++) // L1
for (i2 = 0; i2 != e2; i2++) // L2
...
for (i3 = 0; i3 != e3; i3++) // L3
...If LHS depends on i1, i2 and i3 then L_L should be the loop of i3 (while the deepest is the loop of i2). I think this is how implementation of this method should look like: isKnownPredicate(Pred, LHS, RHS) {
1. Collect set S all loops on which either LHS or RHS depend.
2. If S is non-empty
a. Let PD be the element of S which is dominated by all other elements of S
b. Let E(LHS) be value of LHS on entry of PD.
To get E(LHS), we should just take LHS and replace all AddRecs that are attached to PD on with their entry values.
Define E(RHS) in the same way.
c. Let B(LHS) be value of L on backedge of PD.
To get B(LHS), we should just take LHS and replace all AddRecs that are attached to PD on with their backedge values.
Define B(RHS) in the same way.
d. Note that E(LHS) and E(RHS) are automatically available on entry of PD, so we can assert on that.
e. Return true if isLoopEntryGuardedByCond(Pred, E(LHS), E(RHS)) && isLoopBackedgeGuardedByCond(Pred, B(LHS), B(RHS))
3. Return true if Pred, L, R is known from ranges, splitting etc.
}For my code example above, we have three loops L1, L2, L3 with AddRecs {0,+,1}<L1>, {0,+,1}<L2>, {0,+,1}<L3>. Let for example LHS = {0,+,1}<L1> + {0,+,1}<L3> and RHS = {0,+,1}<L2> + {0,+,1}<L3>. Accodring to the algorithm: isKnownPredicate(Pred, LHS, RHS) {
1. Set S consists of loops L1, L2, L3.
2. S is non-empty.
a. PD is a loop of S which is dominated by all other loops, which happens to be L3.
b. E(LHS) = E({0,+1}<L1> + {0,+,1}<L3>) = ({0,+,1}<L1> + 0. E(RHS) = E({0,+,1}<L2> + {0,+,1}<L3>) = {0,+,1}<L2> + 0.
Hint: We've taken entry value of {0,+1}<L3> because it is depends on L3, and we took all other AddRecs as is because they do not.
c. B(LHS) = B({0,+1}<L1> + {0,+,1}<L3>) = {0,+,1}<L1> + {1,+,1}<L3>. B(RHS) = B({0,+,1}<L2> + {0,+,1}<L3>) = {0,+1}<L2>+ {1,+,1}<L3>.
Hint: We've taken backedge value of {0,+,1}<L3> because it is depends on L3, and we took all other AddRecs as is because they do not.
d. Assert that E(LHS) and E(RHS) are available at entry of L3.
e. Return true if isLoopEntryGuardedByCond(Pred, E(LHS), E(RHS)) && isLoopBackedgeGuardedByCond(Pred, B(LHS), B(RHS))
e. Check ranges etc.How does it sound to you? Comment Actions There already is SCEVInitRewriter. There may a SCEVPostIncRewriter too, but I'm not sure. In any case, it should be easy to write.
Yes, should have been "most dominated". And we can assert that the dominates relation forms a total order on the loops.
SGTM. | ||||||||||||||||||||||||||||||||||||
I think this should be an assert -- if a caller is passing in unavailable SCEVs then it probably has other bugs too which this change will hide.