[IRCE] Smarter detection of empty ranges using SCEV
authorMax Kazantsev <max.kazantsev@azul.com>
Wed, 25 Oct 2017 06:10:02 +0000 (06:10 +0000)
committerMax Kazantsev <max.kazantsev@azul.com>
Wed, 25 Oct 2017 06:10:02 +0000 (06:10 +0000)
commit4332a943bc33fe5e933dda939be43c406fb97eaa
tree15cc1031958efe5a968efccd8ea507eb228f500d
parentf0123607700a275c07f975a1cc0cb317fb3efc5b
[IRCE] Smarter detection of empty ranges using SCEV

For a SCEV range, this patch replaces the naive emptiness check for SCEV ranges
which looks like `Begin == End` with a SCEV check. The range is guaranteed to be
empty of `Begin >= End`. We should filter such ranges out and do not try to perform
IRCE for them.

For example, we can get such range when intersecting range `[A, B)` and `[C, D)`
where `A < B < C < D`. The resulting range is `[max(A, C), min(B, D)) = [C, B)`.
This range is empty, but its `Begin` does not match with `End`.

Making IRCE for an empty range is basically safe but unprofitable because we
never actually get into the main loop where the range checks are supposed to
be eliminated. This patch uses SCEV mechanisms to treat loops with proved
`Begin >= End` as empty.

Differential Revision: https://reviews.llvm.org/D39082

llvm-svn: 316550
llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
llvm/test/Transforms/IRCE/clamp.ll
llvm/test/Transforms/IRCE/empty_ranges.ll [new file with mode: 0644]