[SCEV] Allow negative steps for LT exit count computation for unsigned comparisons

This bit of code is incredibly suspicious. It allows fully unknown (but potentially negative) steps, but not steps

[SCEV] Allow negative steps for LT exit count computation for unsigned comparisons

This bit of code is incredibly suspicious. It allows fully unknown (but potentially negative) steps, but not steps known to be negative. The comment about scev flag inference is worrying, but also not correct to my knowledge.

At best, this might be covering up some related miscompile. However, there's no test in tree for it, the review history doesn't include obvious motivation, and the C++ example doesn't appear to give wrong results when hand translated to IR. I think it's time to remove this and see what falls out.

During review, there were concerns raised about the correctness of the corresponding signed case. This change was deliberately narrowed to the unsigned case which has been auditted and appears correct for negative values. We need to get back to the known-negative signed case, but that'll be a future patch if nothing falls out from this one.

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

show more ...

[ScalarEvolution] Fix pointer/int confusion in howManyLessThans.

In general, howManyLessThans doesn't really want to work with pointers
at all; the result is an integer, and the operands of the icmp

[ScalarEvolution] Fix pointer/int confusion in howManyLessThans.

In general, howManyLessThans doesn't really want to work with pointers
at all; the result is an integer, and the operands of the icmp are
effectively integers. However, isLoopEntryGuardedByCond doesn't like
extra ptrtoint casts, so the arguments to isLoopEntryGuardedByCond need
to be computed without those casts.

Somehow, the values got mixed up with the recent howManyLessThans
improvements; fix the confused values, and add a better comment to
explain what's happening.

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

show more ...

[SCEV] Move getIndexExpressionsFromGEP to delinearize [NFC]

[SCEV] Simplify findExistingSCEVInCache interface [NFC]

We were returning a tuple when all but one caller only cared about one piece of the return value. That one caller can inline the complexity,

[SCEV] Simplify findExistingSCEVInCache interface [NFC]

We were returning a tuple when all but one caller only cared about one piece of the return value. That one caller can inline the complexity, and we can simplify all other uses.

show more ...

Move delinearization logic out of SCEV [NFC]

None of this logic has anything to do with SCEV's internals, it just uses the existing public APIs. As a result, we can move the code from ScalarEvoluti

Move delinearization logic out of SCEV [NFC]

None of this logic has anything to do with SCEV's internals, it just uses the existing public APIs. As a result, we can move the code from ScalarEvolution.cpp/hpp to Delinearization.cpp/hpp with only minor changes.

This was discussed in advance on today's loop opt call. It turned out to be easy as hoped.

show more ...

[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

[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

show more ...

[SCEV] Further clarify comments regarding UB and zero stride

Follow on to D109029. I realized we had no mention of mustprogrress in the comment (as it prexisted mustprogress in the codebase). In the

[SCEV] Further clarify comments regarding UB and zero stride

Follow on to D109029. I realized we had no mention of mustprogrress in the comment (as it prexisted mustprogress in the codebase). In the process of adding it, I tweaked the preconditions into something I think is more clear. Note that mustprogress is checked in the code.

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

show more ...

[Analysis, Target, Transforms] Construct SmallVector with iterator ranges (NFC)

[SCEV] Fix applyLoopGuards() with range check idiom (PR51760)

Due to a typo, this replaced %x with umax(C1, umin(C2, %x + C3))
rather than umax(C1, umin(C2, %x)). This didn't make a difference
for t

[SCEV] Fix applyLoopGuards() with range check idiom (PR51760)

Due to a typo, this replaced %x with umax(C1, umin(C2, %x + C3))
rather than umax(C1, umin(C2, %x)). This didn't make a difference
for the existing tests, because the result is only used for range
calculation, and %x will usually have an unknown starting range,
and the additional offset keeps it unknown. However, if %x already
has a known range, we may compute a result range that is too
small.

show more ...

Revert "snapshot - do not push"

This reverts commit 91f4655d9273ecefab1b7f0ea26d44f5de6fd0af.

This wasn't intented to be pushed, sorry.

snapshot - do not push

[SCEV] Clarify requirements for zero-stride to be UB

There's a silent bug in our reasoning about zero strides. We assume that having a single static exit implies that if that exit is not taken, then

[SCEV] Clarify requirements for zero-stride to be UB

There's a silent bug in our reasoning about zero strides. We assume that having a single static exit implies that if that exit is not taken, then the loop must be infinite. This ignores the potential for abnormal exits via exceptions. Consider the following example:

for (uint_8 i = 0; i < 1; i += 0) {
throw_on_thousandth_call();
}

Our reasoning is such that we'd conclude this loop can't take the backedge as that would lead to a (presumed) infinite loop.

In practice, this is a silent bug because the loopIsFiniteByAssumption returns false strictly more often than the loopHaNoAbnormalExits property. We could reasonable want to change that in the future, so fixing the codeflow now is worthwhile.

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

show more ...

[SCEV] If max BTC is zero, then so is the exact BTC [2 of 2]

This extends D108921 into a generic rule applied to constructing ExitLimits along all paths. The remaining paths (primarily howFarToZero)

[SCEV] If max BTC is zero, then so is the exact BTC [2 of 2]

This extends D108921 into a generic rule applied to constructing ExitLimits along all paths. The remaining paths (primarily howFarToZero) don't have the same reasoning about UB sensitivity as the howManyLessThan ones did. Instead, the remain cause for max counts being more precise than exact counts is that we apply context sensitive loop guards on the max path, and not on the exact path. That choice is mildly suspect, but out of scope of this patch.

The MVETailPredication.cpp change deserves a bit of explanation. We were previously figuring out that two SCEVs happened to be equal because the happened to be identical. When we optimized one with context sensitive information, but not the other, we lost the ability to prove them equal. So, cover this case by subtracting and then applying loop guards again. Without this, we see changes in test/CodeGen/Thumb2/mve-blockplacement.ll

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

show more ...

[SCEV] If max BTC is zero, then so is the exact BTC [1 of N]

This patch is specifically the howManyLessThan case. There will be a couple of followon patches for other codepaths.

The subtle bit is

[SCEV] If max BTC is zero, then so is the exact BTC [1 of N]

This patch is specifically the howManyLessThan case. There will be a couple of followon patches for other codepaths.

The subtle bit is explaining why the two codepaths have a difference while both are correct. The test case with modifications is a good example, so let's discuss in terms of it.
* The previous exact bounds for this example of (-126 + (126 smax %n))<nsw> can evaluate to either 0 or 1. Both are "correct" results, but only one of them results in a well defined loop. If %n were 127 (the only possible value producing a trip count of 1), then the loop must execute undefined behavior. As a result, we can ignore the TC computed when %n is 127. All other values produce 0.
* The max taken count computation uses the limit (i.e. the maximum value END can be without resulting in UB) to restrict the bound computation. As a result, it returns 0 which is also correct.

WARNING: The logic above only holds for a single exit loop. The current logic for max trip count would be incorrect for multiple exit loops, except that we never call computeMaxBECountForLT except when we can prove either a) no overflow occurs in this IV before exit, or b) this is the sole exit.

An alternate approach here would be to add the limit logic to the symbolic path. I haven't played with this extensively, but I'm hesitant because a) the term is optional and b) I'm not sure it'll reliably simplify away. As such, the resulting code quality from expansion might actually get worse.

This was noticed while trying to figure out why D108848 wasn't NFC, but is otherwise standalone.

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

show more ...

[SCEVExpander] Reuse removePointerBase() for canonical addrecs

ExposePointerBase() in SCEVExpander implements basically the same
functionality as removePointerBase() in SCEV, so reuse it.

The SCEVE

[SCEVExpander] Reuse removePointerBase() for canonical addrecs

ExposePointerBase() in SCEVExpander implements basically the same
functionality as removePointerBase() in SCEV, so reuse it.

The SCEVExpander code assumes that the pointer operand on adds is
the last one -- I'm not sure that always holds. As such this might
not be strictly NFC.

show more ...

[SCEV] Assert unique pointer base (NFC)

Add expressions can contain at most one pointer operand nowadays,
assert that in getPointerBase() and removePointerBase().

[SCEV] Infer nuw from nw for addrecs

This was previously committed in 914836b, and reverted due to confusion on the status of the review.

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

Revert "[SCEV] Infer nsw/nuw from nw for addrecs"

This reverts commit 914836b1c8b36d4a317ef6c233746f6ec37b57a5. Further comments on review came up after initial approval. Reverting while addressin

Revert "[SCEV] Infer nsw/nuw from nw for addrecs"

This reverts commit 914836b1c8b36d4a317ef6c233746f6ec37b57a5. Further comments on review came up after initial approval. Reverting while addressing.

show more ...

[SCEV] Infer nsw/nuw from nw for addrecs

If we no an addrec doesn't self-wrap, the increment is strictly positive, and the start value is the smallest representable value, then we know that the corr

[SCEV] Infer nsw/nuw from nw for addrecs

If we no an addrec doesn't self-wrap, the increment is strictly positive, and the start value is the smallest representable value, then we know that the corresponding wrap type can not occur.

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

show more ...

[SCEV] Add a hasFlags utility to improve readability [NFC]

Revert "[SCEV] Remove premature assert. PR46786"

Since then, the SCEV pointer handling as been improved,
so the assertion should now hold.

This reverts commit b96114c1e1fc4448ea966bce013706359aee3f

Revert "[SCEV] Remove premature assert. PR46786"

Since then, the SCEV pointer handling as been improved,
so the assertion should now hold.

This reverts commit b96114c1e1fc4448ea966bce013706359aee3fa9,
relanding the assertion from commit 141e845da5dda6743a09f858b4aec0133a931453.

show more ...

[SCEV] Add a comment about invariant in howManyLessThans

[IR] Consider non-willreturn as side effect (PR50511)

This adjusts mayHaveSideEffect() to return true for !willReturn()
instructions. Just like other side-effects, non-willreturn calls
(aka "diverge

[IR] Consider non-willreturn as side effect (PR50511)

This adjusts mayHaveSideEffect() to return true for !willReturn()
instructions. Just like other side-effects, non-willreturn calls
(aka "divergence") cannot be removed and cannot be reordered relative
to other side effects. This fixes a number of bugs where
non-willreturn calls are either incorrectly dropped or moved. In
particular, it also fixes the last open problem in
https://bugs.llvm.org/show_bug.cgi?id=50511.

I performed a cursory review of all current mayHaveSideEffect()
uses, which convinced me that these are indeed the desired default
semantics. Places that do not want to consider non-willreturn as a
sideeffect generally do not want mayHaveSideEffect() semantics at
all. I identified two such cases, which are addressed by D106591
and D106742. Finally, there is a use in SCEV for which we don't
really have an appropriate API right now -- what it wants is
basically "would this be considered forward progress". I've just
spelled out the previous semantics there.

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

show more ...

Style tweaks for SCEV's computeMaxBECountForLT [NFC]

[SCEV] Fix bug involving zero step and non-invariant RHS in trip count logic

Eli pointed out the issue when reviewing D104140. The max trip count logic makes an assumption that the value of IV chang

[SCEV] Fix bug involving zero step and non-invariant RHS in trip count logic

Eli pointed out the issue when reviewing D104140. The max trip count logic makes an assumption that the value of IV changes. When the step is zero, the nowrap fact becomes trivial, and thus there's nothing preventing the loop from being nearly infinite. (The "nearly" part is because mustprogress may disallow an infinite loop while still allowing 999999999 iterations before RHS happens to allow an exit.)

This is very difficult to see in practice. You need a means to produce a loop varying RHS in a mustprogress loop which doesn't allow the loop to be infinite. In most cases, LICM or SCEV are smart enough to remove the loop varying expressions.

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

show more ...