Page MenuHomePhabricator

ScalarEvolution assume hanging bugfix
ClosedPublic

Authored by Prazek on Sep 8 2015, 7:54 PM.

Details

Diff Detail

Event Timeline

Prazek updated this revision to Diff 34291.Sep 8 2015, 7:54 PM
Prazek retitled this revision from to ScalarEvolution assume hanging bugfix.
Prazek updated this object.
Prazek added reviewers: rsmith, nlewycky.
Prazek added a subscriber: cfe-commits.
nlewycky added inline comments.Sep 8 2015, 8:01 PM
lib/Analysis/ScalarEvolution.cpp
6980

What is it about this check which is a problem? Or put another way, why is this not okay but the call to isImpliedCond on line 6956 is fine? The problem is recursion through isImpliedCond->getSCEV->..., right?

Prazek added inline comments.Sep 8 2015, 8:11 PM
lib/Analysis/ScalarEvolution.cpp
6980

The problem is that the check wasn't covering assume loop which caused big hang.

Stacktrace looked more like this
(isImpliedCond -> getZeroExtendExpr -> isLoopBackedgeGuardedByCond) x much

nlewycky added inline comments.Sep 8 2015, 8:12 PM
lib/Analysis/ScalarEvolution.cpp
6980

Does the code from 6953 to 6959 need to move below this check too? Is there another bug here?

sanjoy added a comment.Sep 8 2015, 8:27 PM

I don't think this is an infinite loop (Piotr, can you please verify
this?), it is probably an O(n!) recursion where n == number of the
assumptions.

ScalarEvolution::isImpliedCond already guards for infinite loops via
MarkPendingLoopPredicate. However, if you have

assume_0()
assume_1()
assume_2()
assume_3()

then the recursive call to isImpliedCond(assume_2, X) may end up
calling isImpliedCond(assume_1, Y) and that may end up calling
isImpliedCond(assume_0, Y) and that may end up calling
isImpliedCond(assume_3, Y). This way, even though we're protected
against full on infinite recursion, we'll still explore all 4! = 24
possibilities.

I think the check with LoopContinuePredicate is fine since it only
calls isImpliedCond if there is exactly one latch in the loop. This
means that the above n! possibility is really only a 1! = 1
possibility for LoopContinuePredicate.

But this from memory, so please double check.

I checked it, it is of course not infinite. I am not sure about n! in case of assumes. I having 10 or 20 assumes will not make it slow. @rsmith was helping me with it, and he thinks that for assumes it is O(n^2), because results are memorized.

So it this case, 1000 assumes is enough to make difference

lib/Analysis/ScalarEvolution.cpp
6980

I don't think so. I think the results are memorized, so calling sImpliedCond in 6956 will not cause lag.

I used "hanging out" in the meaning of being very slow, not sure if it is right word for it.

majnemer edited subscribers, added: llvm-commits; removed: cfe-commits.Sep 8 2015, 10:45 PM
majnemer added a subscriber: majnemer.

-cfe-commits
+llvm-commits

sanjoy added a comment.Sep 9 2015, 1:23 AM

I checked it, it is of course not infinite. I am not sure about n! in case of assumes. I having 10 or 20 assumes will not make it slow. @rsmith was helping me with it, and he thinks that for assumes it is O(n^2), because results are memorized.

I think @rsmith is right -- in this case the complexity is O(n^2). I thought I had an example where it was O(n!), but I cannot come with anything concrete right now.

Do you mind also changing O(n!) time complexity to O(n^2) time complexity in the comment?

Prazek added a comment.Sep 9 2015, 9:26 AM

I am not sure if it will be correct - the comment was related to loop after assumes loop, and I am not sure if this one is different

rsmith edited edge metadata.Sep 9 2015, 11:30 AM

I think @rsmith is right -- in this case the complexity is O(n^2). I thought I had an example where it was O(n!), but I cannot come with anything concrete right now.

Our initial analysis of the 'assume' problem appeared to be O(n!), but we don't have a reduced testcase for that. The cycle there was isLoopBackedgeGuardedByCond -> isImpliedCond -> getZeroExtendExpr -> isLoopBackedgeGuardedByCond. In the testcase in this patch, getZeroExtendExpr memoizes its result, but there are paths through it that do not appear to do so (in particular, the isLoopBackedgeGuardedByCond test in the isKnownPositive / isKnownNegative cases can lead to a return with no memoization of the getZeroExtendExpr result).

I could easily believe there are testcases for both loops that lead to O(n!) performance. (If not, we are emitting /vastly/ too many assumes...)

Prazek added a comment.Sep 9 2015, 1:16 PM

LGTM someone?

Prazek accepted this revision.Sep 9 2015, 1:29 PM
Prazek added a reviewer: Prazek.

(accepted by Nick Lewycky in mail)
LGTM.

This revision is now accepted and ready to land.Sep 9 2015, 1:29 PM
Prazek closed this revision.Sep 9 2015, 1:49 PM