[SCEV] Search operand tree for scope bound when inferring flags from IR

When checking to see if we can apply IR flags to a SCEV, we need to identify a bound on the defining scope of the SCEV to be p

[SCEV] Search operand tree for scope bound when inferring flags from IR

When checking to see if we can apply IR flags to a SCEV, we need to identify a bound on the defining scope of the SCEV to be produced. We'd previously added support for a couple SCEVExpr types which trivially imply bounds, but hadn't handled types such as umax where the bounds come from the bounds of the operands. This does the obvious thing, and recurses through operands searching for a tighter bound on the defining scope.

I'm honestly surprised by how little this seems to mater on existing tests, but it's worth doing for completeness sake alone.

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

show more ...

[SCEV] Avoid unnecessary domination checks (NFC)

When determining the defining scope, avoid repeatedly querying
dominationg against the function entry instruction. This ends up
begin a very common c

[SCEV] Avoid unnecessary domination checks (NFC)

When determining the defining scope, avoid repeatedly querying
dominationg against the function entry instruction. This ends up
begin a very common case that we can handle more efficiently.

show more ...

[scev] minor style improvement [nfc]

[SCEV] Infer flags from add/gep in any block

This patch removes a compile time restriction from isSCEVExprNeverPoison. We've strengthened our ability to reason about flags on scopes other than addre

[SCEV] Infer flags from add/gep in any block

This patch removes a compile time restriction from isSCEVExprNeverPoison. We've strengthened our ability to reason about flags on scopes other than addrecs, and this bailout prevents us from using it. The comment is also suspect as well in that we're in the middle of constructing a SCEV for I. As such, we're going to visit all operands *anyways*.

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

show more ...

[SCEV] Don't check if propagation safe if there are no flags (NFC)

If there are no nowrap flags, then we don't need to determine
whether propagating flags is safe -- it will make no difference.

[SCEV] Tweak the algorithm for figuring out if flags must apply to a SCEV [mostly-NFC]

Behavior wise, this patch should be mostly NFC. The only behavior difference known is that on the isSCEVExprNe

[SCEV] Tweak the algorithm for figuring out if flags must apply to a SCEV [mostly-NFC]

Behavior wise, this patch should be mostly NFC. The only behavior difference known is that on the isSCEVExprNeverPoison path we'll consider a bound imposed by the SCEVable operands (if any).

Algorithmically, it's an invert of the existing code. Previously, we checked for each operand if we could find a bound, then checked for must-execute given that bound. With the patch, we use dominance to refine the innermost bound, then check must execute once. The interesting case is when we have multiple unknowns within a single basic block. While both dominance and must-execute are worst-case linear walks within the block, only dominance is cached. As such, refining based on dominance should be more efficient.

show more ...

[APInt] Stop using soft-deprecated constructors and methods in llvm. NFC.

Stop using APInt constructors and methods that were soft-deprecated in
D109483. This fixes all the uses I found in llvm, exc

[APInt] Stop using soft-deprecated constructors and methods in llvm. NFC.

Stop using APInt constructors and methods that were soft-deprecated in
D109483. This fixes all the uses I found in llvm, except for the APInt
unit tests which should still test the deprecated methods.

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

show more ...

[SCEV] Cap the number of instructions scanned when infering flags

This addresses a comment from review on D109845. The concern was raised that an unbounded scan would be expensive. Long term plan

[SCEV] Cap the number of instructions scanned when infering flags

This addresses a comment from review on D109845. The concern was raised that an unbounded scan would be expensive. Long term plan is to cache this search - likely reusing the existing mechanism for loop side effects - but let's be simple and conservative for now.

show more ...

[SCEV] Use trivial bound on defining scope of all SCEVs when computing flags

This addresses a comment from review on D109845. Even for SCEVs which we can't find true bounds without recursing throug

[SCEV] Use trivial bound on defining scope of all SCEVs when computing flags

This addresses a comment from review on D109845. Even for SCEVs which we can't find true bounds without recursing through operands, entry to the function forms a trivial upper bound. In some cases, this trivial bound is enough to prove safety of flag inference.

show more ...

[SCEV] Use full logic when infering flags on add and gep

This is a followon to D109845. With that landed, we will have fixed all known instances of pr51817, and can thus start inferring flags more a

[SCEV] Use full logic when infering flags on add and gep

This is a followon to D109845. With that landed, we will have fixed all known instances of pr51817, and can thus start inferring flags more aggressively with greatly reduced risk of miscompiles. This patch simply applies the same inference logic used in that patch to our other major flag inference path.

We can still do much better here (on both paths), but this is our first step.

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

show more ...

[SCEV] Correctly propagate nowrap flags across scopes when folding invariant add through addrec

This fixes a violation of the wrap flag rules introduced in c4048d8f. This is an alternate fix to D106

[SCEV] Correctly propagate nowrap flags across scopes when folding invariant add through addrec

This fixes a violation of the wrap flag rules introduced in c4048d8f. This is an alternate fix to D106852.

The basic problem being fixed is that we infer a set of flags which is valid at some inner scope S1 (usually by correctly propagating them from IR), and then (incorrectly) extend them to a SCEV in scope S2 where S1 != S2. This is not in general safe per the wrap flags semantics recently defined.

In this patch, I include a simple inference step to handle the case where we can prove that S2 is the preheader of the loop S1, and that entry into S2 implies execution of S1. See the code for a more detailed explanation.

One worry I have with this patch is that I might be over-fitting what shows up in tests - and thus hiding negative impact we'd see in the real world. My best defense is that the rule used here very closely follows the one used to propagate the flags from IR to the inner add to start with, and thus if one is reasonable, so probably is the other. Curious what others think about that piece.

The test diffs are roughly as expected. Mostly analysis only, with two transform changes. Oddly, the result looks better in the loop-idiom test, and I don't understand the PPC output enough to have tell. Nothing terrible looking though. (For context, without the scope inference peephole, the test delta includes a couple of vectorization tests. Again, not super concerning, but slightly more so.)

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

show more ...

[SCEV] Split isSCEVExprNeverPoison reasoning explicitly into scope and mustexecute parts [NFC]

Inspired by the needs to D111001 and D109845. The seperation of concerns also amakes it easier to reas

[SCEV] Split isSCEVExprNeverPoison reasoning explicitly into scope and mustexecute parts [NFC]

Inspired by the needs to D111001 and D109845. The seperation of concerns also amakes it easier to reason about correctness and completeness.

show more ...

[SCEV] Stop blindly propagating flags from inbound geps to SCEV nodes

This fixes a violation of the wrap flag rules introduced in c4048d8f. This was also noted in the (very old) PR23527.

The issue

[SCEV] Stop blindly propagating flags from inbound geps to SCEV nodes

This fixes a violation of the wrap flag rules introduced in c4048d8f. This was also noted in the (very old) PR23527.

The issue being fixed is that we assume the inbound flag on any GEP assumes that all users of *any* gep (or add) which happens to map to that SCEV would also be UB if the (other) gep overflowed. That's simply not true.

In terms of the test diffs, I don't see anything seriously problematic. The lost flags are expected (given the semantic restriction on when its legal to tag the SCEV), and there are several cases where the previously inferred flags are unsound per the new semantics.

The only common trend I noticed when looking at the deltas is that by not considering branch on poison as immediate UB in ValueTracking, we do miss a few cases we could reclaim. We may be able to claw some of these back with the follow ideas mentioned in PR51817.

It's worth noting that most of the changes are analysis result only changes. The two transform changes are pretty minimal. In one case, we miss the opportunity to infer a nuw (correctly). In the other, we fail to fold an exit and produce a loop invariant form instead. This one is probably over-reduced as the program appears to be undefined in practice, and neither before or after exploits that.

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

show more ...

[SCEV] Remove invariant requirement from isSCEVExprNeverPoison

This code is attempting to prove that I must execute if we enter the defining scope of the SCEV which will be created from I. In the ca

[SCEV] Remove invariant requirement from isSCEVExprNeverPoison

This code is attempting to prove that I must execute if we enter the defining scope of the SCEV which will be created from I. In the case where it found a defining addrec scope, it had a rather odd restriction that all of the other operands must be loop invariant in that addrec's loop.

As near as I can tell here, we really only need a upper bound on the defining scope. If we can prove the stronger property, then we must also have proven the property on the exact defining scope as well.

In practice, the actual effect of this change is narrow. The compile time restriction at the top of the routine basically limits us to I being an arithmetic in some loop L with both an addrec operand in L, and a unknown operands in L. Possible to demonstrate, but the main value of the change is removing unneeded code.

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

show more ...

[SCEV] Modernize code style of isSCEVExprNeverPoison [NFC]

Use for-range and all_of to make code easier to read in advance of other changes.

Revert "Recommit "[SCEV] Look through single value PHIs." (take 2)"

This reverts commit 764d9aa97905f202385b4f25f8d234630b4feef3.

This patch exposed a few additional cases where SCEV expressions ar

Revert "Recommit "[SCEV] Look through single value PHIs." (take 2)"

This reverts commit 764d9aa97905f202385b4f25f8d234630b4feef3.

This patch exposed a few additional cases where SCEV expressions are not
properly invalidated.

See PR52024, PR52023.

show more ...

Recommit "[SCEV] Look through single value PHIs." (take 2)

This reverts commit 8fdac7cb7abbeeaed016ef9eb7a087458e41e33f.

The issue causing the revert has been fixed a while ago in 60b852092c98.

Or

Recommit "[SCEV] Look through single value PHIs." (take 2)

This reverts commit 8fdac7cb7abbeeaed016ef9eb7a087458e41e33f.

The issue causing the revert has been fixed a while ago in 60b852092c98.

Original message:

Now that SCEVExpander can preserve LCSSA form,
we do not have to worry about LCSSA form when
trying to look through PHIs. SCEVExpander will take
care of inserting LCSSA PHI nodes as required.

This increases precision of the analysis in some cases.

Reviewed By: mkazantsev, bmahjour

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

show more ...

[SCEV] Use isAvailableAtLoopEntry in the asserts

This is what is supposed to be there.

[SCEV] Add some asserts on availability of arguments of isLoopEntryGuardedByCond

The logic in howManyLessThans is fishy. It first checks invariance of
RHS, and then uses OrigRHS as argument for isLo

[SCEV] Add some asserts on availability of arguments of isLoopEntryGuardedByCond

The logic in howManyLessThans is fishy. It first checks invariance of
RHS, and then uses OrigRHS as argument for isLoopEntryGuardedByCond, which
is, strictly saying, a different thing. We are seeing a very rare intermittent
failure of availability checks, and it looks like this precondition is
sometimes broken. Before we can figure out what's going on, adding asserts
that all involved values that may possibly to to isLoopEntryGuardedByCond
are available at loop entry.

If either of these asserts fails (OrigRHS is the most likely suspect), it
means that the logic here is flawed.

show more ...

[SCEV] Generalize implication when signedness of FoundPred doesn't matter

The implication logic for two values that are both negative or non-negative
says that it doesn't matter whether their predic

[SCEV] Generalize implication when signedness of FoundPred doesn't matter

The implication logic for two values that are both negative or non-negative
says that it doesn't matter whether their predicate is signed and unsigned,
but only flips unsigned into signed for further inference. This patch adds
support for flipping a signed predicate into unsigned as well.

Differential Revision: https://reviews.llvm.org/D109959
Reviewed By: nikic

show more ...

[NFC] Rename Context->CtxI in SCEV for uniformity reasons

[SCEV] Support negative values in signed/unsigned predicate reasoning

There is a piece of logic that uses the fact that signed and unsigned
versions of the same predicate are equivalent when both va

[SCEV] Support negative values in signed/unsigned predicate reasoning

There is a piece of logic that uses the fact that signed and unsigned
versions of the same predicate are equivalent when both values are
non-negative. It's also true when both of them are negative.

Differential Revision: https://reviews.llvm.org/D109957
Reviewed By: nikic

show more ...

[SCEV] (udiv X, Y) * Y is always NUW

Motivated by the removal done in D109782. This implements the correct flag part generically.

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

[SCEV] Stop applying contextual flags in applyLoopGuards

This fixes a violation of the wrap flag rules introduced in c4048d8f. As noted in the original review, the NUW is legal to infer from the str

[SCEV] Stop applying contextual flags in applyLoopGuards

This fixes a violation of the wrap flag rules introduced in c4048d8f. As noted in the original review, the NUW is legal to infer from the structure of the replacee, but a) there's no test coverage, and b) this should be done generically for all multiplies.

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

show more ...

[ScalarEvolution] Add an additional bailout to avoid NOT of pointer.

It's possible in some cases for the LHS to be a pointer where the RHS is not. This isn't directly possible for an icmp, but the a

[ScalarEvolution] Add an additional bailout to avoid NOT of pointer.

It's possible in some cases for the LHS to be a pointer where the RHS is not. This isn't directly possible for an icmp, but the analysis mixes up operands of different icmp expressions in some cases.

This does not include a test case as the smallest reduced case we've managed is extremely fragile and unlikely to test anything meaningful in the long term.

Also add an assertion to getNotSCEV() to make tracking down this sort of issue a bit easier in the future.

Fixes https://bugs.llvm.org/show_bug.cgi?id=51787 .

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

show more ...