[IndVars] Improve handling of multi-exit loops with known symbolic counts
authorMax Kazantsev <mkazantsev@azul.com>
Tue, 24 Jan 2023 05:46:48 +0000 (12:46 +0700)
committerMax Kazantsev <mkazantsev@azul.com>
Tue, 24 Jan 2023 05:46:48 +0000 (12:46 +0700)
commit932ae48c273c590449649ed3cc7b752511a85665
tree2858db3a679f25f96144fd83bc3987851799deca
parent602916d2defa95cf4bec76e458be4375dbe70e4a
[IndVars] Improve handling of multi-exit loops with known symbolic counts

This patch does two things, both related to support of multi-exit loops with
many exits that have known symbolic max exit count. They can theoretically
go independently, but I don't know how to write a test showing separate
impact.

Part 1: `SkipLastIter` can be set to `true` not when a particular exit has exit
count same as the whole loop (and therefore it must exit on the last iteration),
but when the aggregate of first few exits has umin same as whole loop exit count.
It means that it's not known which of them will exit exactly, but one of them will.

Part 2: when `SkipLastIter` is set, and exit count is `umin(a, b, c)`, instead of
`umin(a, b, c) - 1` use `umin(a - 1, b - 1, c - 1)`. We don't care about overflows
here, but the further logic knows how to deal with umin by element, but the
`SCEVAddExpr` node will confuse it.

Differential Revision: https://reviews.llvm.org/D141361
Reviewed By: nikic
llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
llvm/test/Transforms/IndVarSimplify/turn-to-invariant.ll