[SCEV] Precise trip multiples
authorJoshua Cao <cao.joshua@yahoo.com>
Tue, 11 Apr 2023 06:52:06 +0000 (23:52 -0700)
committerJoshua Cao <cao.joshua@yahoo.com>
Mon, 24 Apr 2023 07:21:59 +0000 (00:21 -0700)
commit027a4c8b96c7f97df8e98b1dac069b956810ab94
tree479b155f6b16fa8840b501adbdc07741f9b963f9
parentda36d1f09901fa5c0e9c0102bbefecbdeedd4ef2
[SCEV] Precise trip multiples

We currently have getMinTrailingZeros(), from which we can get a SCEV's
multiple by computing 1 << MinTrailingZeroes. However, this only gets us
multiples that are a power of 2. This patch introduces a way to get max
constant multiples that are not just a power of 2. The logic is similar
to that of getMinTrailingZeros. getMinTrailingZeros is replaced by
computing the max constant multiple, and counting the number of trailing
bits.

This is applied in two places:

1) Computing unsigned constant ranges. For example, if we have i8
   {10,+,10}<nuw>, we know the max constant it can be is 250.

2) Computing trip multiples as shown in SCEV output. This is useful if
   for example, we are unrolling a loop by a factor of 5, and we know
   the trip multiple is 5, then we don't need a loop epilog.

If the code sees that a SCEV does not have <nuw>, it will fall back to
finding the max multiple that is a power of 2. Multiples that are a
power of 2 will still be a multiple even after the SCEV overflows.

Differential Revision: https://reviews.llvm.org/D141823
llvm/include/llvm/Analysis/ScalarEvolution.h
llvm/lib/Analysis/ScalarEvolution.cpp
llvm/test/Analysis/ScalarEvolution/nsw.ll
llvm/test/Analysis/ScalarEvolution/ranges.ll
llvm/test/Analysis/ScalarEvolution/trip-multiple-guard-info.ll
llvm/test/Analysis/ScalarEvolution/trip-multiple.ll