[SCEV] Fix unsound reasoning in howManyLessThans
authorPhilip Reames <listmail@philipreames.com>
Thu, 15 Jul 2021 17:25:06 +0000 (10:25 -0700)
committerPhilip Reames <listmail@philipreames.com>
Thu, 15 Jul 2021 17:32:47 +0000 (10:32 -0700)
commita99d420a937bd7792739767c8bed6d189a444c54
tree63a5239da6a01f898f6a79d379ab3bd2e7fd60f2
parent4628ff4c31b72a62346defee32b8dec9b9adef93
[SCEV] Fix unsound reasoning in howManyLessThans

This is split from D105216, it handles only a subset of the cases in that patch.

Specifically, the issue being fixed is that the code incorrectly assumed that (Start-Stide) < End implied that the backedge was taken at least once. This is not true when e.g. Start = 4, Stride = 2, and End = 3. Note that we often do produce the right backedge taken count despite the flawed reasoning.

The fix chosen here is to use an alternate form of uceil (ceiling of unsigned divide) lowering which is safe when max(RHS,Start) > Start - Stride.  (Note that signedness of both max expression and comparison depend on the signedness of the comparison being analyzed, and that overflow in the Start - Stride expression is allowed.)  Note that this is weaker than proving the backedge is taken because it allows start - stride < end < start.  Some cases which can't be proven safe are sent down the generic path, and we do end up generating less optimal expressions in a few cases.

Credit for coming up with the approach goes entirely to Eli.  I just split it off, tweaked the comments a bit, and did some additional testing.

Differential Revision: https://reviews.llvm.org/D105942
llvm/lib/Analysis/ScalarEvolution.cpp
llvm/test/Analysis/ScalarEvolution/2008-11-18-Stride2.ll
llvm/test/Analysis/ScalarEvolution/trip-count-unknown-stride.ll
llvm/test/Transforms/LoopReroll/nonconst_lb.ll