[IRCE] Relax restrictions on IRCE's latch exit count
authorMax Kazantsev <mkazantsev@azul.com>
Thu, 13 Apr 2023 08:43:24 +0000 (15:43 +0700)
committerMax Kazantsev <mkazantsev@azul.com>
Thu, 13 Apr 2023 09:00:19 +0000 (16:00 +0700)
commit2124505fe4c9ff85173c5ca3b14810f698436239
treebb2eb5b81edc0c488e4ddaeefe8a71a20cc3aade
parentba482dde664d392cc5b30bbf468802d9e9c01b0b
[IRCE] Relax restrictions on IRCE's latch exit count

It seems that existing logic is too strict about latch block exit count.
It is required to be computable, however it is not used in any computations,
and effectively the only thing it is used for is to get the type of computed
exit count.

Sometimes the exit count for latch block is not known, but the loop is still
finite because of other exits, and safe bounds are still computable. In this case,
we miss an opportunity to apply IRCE.
We could instead use a more relaxed version - max symbolic exit count, which,
if exists, is enough to say that the loop is finite, and its type should be good enough.

There is a subtlety with type: we do not support latch count type wider than range
check type. Because of that, we want to have the narrowest type available. So if it
can be computed from latch block immediately, take it. Otherwise, take whatever whole
loop provides and hope that it's type isn't too wide.

Differential Revision: https://reviews.llvm.org/D147910
Reviewed By: danilaml
llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
llvm/test/Transforms/IRCE/stride_more_than_1.ll