[IndVars] Apply more optimistic SkipLastIter for AND/OR conditions
authorMax Kazantsev <mkazantsev@azul.com>
Tue, 24 Jan 2023 05:17:33 +0000 (12:17 +0700)
committerMax Kazantsev <mkazantsev@azul.com>
Tue, 24 Jan 2023 05:26:22 +0000 (12:26 +0700)
commit602916d2defa95cf4bec76e458be4375dbe70e4a
tree9148e46d8d335fad31e440b16aa7a3f3ea6bc2da
parenta2f71d2732d3fa2700ae2f899fef112955b07af9
[IndVars] Apply more optimistic SkipLastIter for AND/OR conditions

When exit by condition `C1` dominates exit by condition `C2`, and
max symbolic exit count for `C1` matches those for loop, we will
apply more optimistic logic to `C2` by setting `SkipLastIter` for it,
meaning that it will do 1 iteration less because the dominating branch
must exit on the last loop iteration.

But when we have a single exit by condition `C1 & C2`, we cannot
apply the same logic, because there is no dominating condition.

However, if we can prove that the symbolic max exit count of `C1 & C2`
matches those of `C1`, it means that for `C2` we can assume that it
doesn't matter on the last iteration (because the whole thing is `false`
because `C1` must be `false`). Therefore, in this situation, we can handle
`C2` as if it had `SkipLastIter`.

Differential Revision: https://reviews.llvm.org/D139934
Reviewed By: nikic
llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
llvm/test/Transforms/IndVarSimplify/X86/widening-vs-and-elimination.ll
llvm/test/Transforms/IndVarSimplify/turn-to-invariant.ll