[SCEV] Use no-self-wrap flags infered from exit structure to compute trip count
authorPhilip Reames <listmail@philipreames.com>
Tue, 7 Sep 2021 23:58:18 +0000 (16:58 -0700)
committerPhilip Reames <listmail@philipreames.com>
Wed, 8 Sep 2021 00:00:02 +0000 (17:00 -0700)
commit6cdca906c79fb4e0eae940f11d585c1b08358104
treef21341ec0ae84ac11ce4de3fa7b5e45ff1a8f6fc
parent6b53817e713ca02415e710e5c7b0d2a643d93889
[SCEV] Use no-self-wrap flags infered from exit structure to compute trip count

The basic problem being solved is that we largely give up when encountering a trip count involving an IV which is not an addrec. We will fall back to the brute force constant eval, but that doesn't have the information about the fact that we can't cycle back through the same set of values.

There's a high level design question of whether this is the right place to handle this, and if not, where that place is. The major alternative here would be to return a conservative upper bound, and then rely on two invocations of indvars to add the facts to the narrow IV, and then reconstruct SCEV. (I have not implemented the alternative and am not 100% sure this would work out.) That's arguably more in line with existing code, but I find this substantially easier to reason about.  During review, no one expressed a strong opinion, so we went with this one.

Differential Revision: D108651
llvm/lib/Analysis/ScalarEvolution.cpp
llvm/test/Analysis/ScalarEvolution/trip-count-implied-addrec.ll