[ScalarEvolution] Handle <= and >= in non infinite loops
authorWilliam S. Moses <gh@wsmoses.com>
Tue, 25 Jan 2022 01:02:53 +0000 (20:02 -0500)
committerWilliam S. Moses <gh@wsmoses.com>
Fri, 28 Jan 2022 22:41:08 +0000 (17:41 -0500)
commit99d2582164c4bc8f10c3e3c20dd3690243ad49ba
tree9caffa8a3dc09812cba11c68977963a3da8972f2
parent354ec4af749ccd910a1cffc5e9cce2bb93239b9b
[ScalarEvolution] Handle <= and >= in non infinite loops

Extend scalar evolution to handle >= and <= if a loop is known to be finite and the induction variable guards the condition. Specifically, with these assumptions lhs <= rhs is equivalent to lhs < rhs + 1 and lhs >= rhs to lhs > rhs -1.

In the case of lhs <= rhs, this is true since the only case these are not equivalent
is when rhs == unsigned/signed intmax, which would have resulted in an infinite loop.

In the case of lhs >= rhs, this is true since the only case these are not equivalent
is when rhs == unsigned/signed intmin, which would again have resulted in an infinite loop.

Reviewed By: lebedev.ri

Differential Revision: https://reviews.llvm.org/D118090
llvm/include/llvm/Analysis/ScalarEvolution.h
llvm/lib/Analysis/ScalarEvolution.cpp
llvm/test/Analysis/ScalarEvolution/finite-trip-count.ll [new file with mode: 0644]