On 8 September 2015 at 20:27, Sanjoy Das <san...@playingwithpointers.com> wrote:
> sanjoy added a comment. > > 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 agree it's probably O(n!) instead of infinite, but that's slow enough. 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. > Both tests are protected by there being exactly one latch in the loop (we exit early if there's not one latch). I'm not sure what makes the LoopContinuePredicate check safer?
_______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
