[SCEVExpander] Attempt to reinfer flags dropped due to CSE (#72431)

LSR uses SCEVExpander to generate induction formulas. The expander
internally tries to reuse existing IR expressions. To do that,

[SCEVExpander] Attempt to reinfer flags dropped due to CSE (#72431)

LSR uses SCEVExpander to generate induction formulas. The expander
internally tries to reuse existing IR expressions. To do that, it needs
to strip any poison generating flags (nsw, nuw, exact, nneg, etc..)
which may not be valid for the newly added users.

This is conservatively correct, but has the effect that LSR will strip
nneg flags on zext instructions involved in trip counts in loop
preheaders. To avoid this, this patch adjusts the expanded to reinfer
the flags on the CSE candidate if legal for all possible users.

This should fix the regression reported in
https://github.com/llvm/llvm-project/issues/71200.

This should arguably be done inside canReuseInstruction instead, but
doing it outside is more conservative compile time wise. Both
canReuseInstruction and isGuaranteedNotToBePoison walk operand lists, so
right now we are performing work which is roughly O(N^2) in the size of
the operand graph. We should fix that before making the per operand step
more expensive. My tenative plan is to land this, and then rework the
code to sink the logic into more core interfaces.

show more ...

[LoopPredication] Fix the LoopPredication by feezing the result of predication.

LoopPredication introduces the use of possibly posion value in branch (guard)
instruction, so to avoid introducing und

[LoopPredication] Fix the LoopPredication by feezing the result of predication.

LoopPredication introduces the use of possibly posion value in branch (guard)
instruction, so to avoid introducing undefined behavior it should be frozen.

Reviewed By: mkazantsev
Differential Revision: https://reviews.llvm.org/D146685

show more ...

[LoopPredication] Convert tests to opaque pointers (NFC)

[NFC] Port all LoopPredication tests to `-passes=` syntax

[LoopPredication] Insert assumes of conditions of predicated guards

As LoopPredication performs non-equivalent transforms removing some
checks from loops, other passes may not be able to perform tra

[LoopPredication] Insert assumes of conditions of predicated guards

As LoopPredication performs non-equivalent transforms removing some
checks from loops, other passes may not be able to perform transforms
they'd be able to do if the checks were left in loops.

This patch makes LoopPredication insert assumes of the replaced
conditions either after a guard call or in the true block of
widenable condition branch.

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

show more ...

[SCEVExpander] Drop poison generating flags when reusing instructions

The basic problem we have is that we're trying to reuse an instruction which is mapped to some SCEV. Since we can have multiple

[SCEVExpander] Drop poison generating flags when reusing instructions

The basic problem we have is that we're trying to reuse an instruction which is mapped to some SCEV. Since we can have multiple such instructions (potentially with different flags), this is analogous to our need to drop flags when performing CSE. A trivial implementation would simply drop flags on any instruction we decided to reuse, and that would be correct.

This patch is almost that trivial patch except that we preserve flags on the reused instruction when existing users would imply UB on overflow already. Adding new users can, at most, refine this program to one which doesn't execute UB which is valid.

In practice, this fixes two conceptual problems with the previous code: 1) a binop could have been canonicalized into a form with different opcode or operands, or 2) the inbounds GEP case which was simply unhandled.

On the test changes, most are pretty straight forward. We loose some flags (in some cases, they'd have been dropped on the next CSE pass anyways). The one that took me the longest to understand was the ashr-expansion test. What's happening there is that we're considering reuse of the mul, previously we disallowed it entirely, now we allow it with no flags. The surrounding diffs are all effects of generating the same mul with a different operand order, and then doing simple DCE.

The loss of the inbounds is unfortunate, but even there, we can recover most of those once we actually treat branch-on-poison as immediate UB.

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

show more ...

Revert rest of `IRBuilderBase`'s short-circuiting folds

Upon further investigation and discussion,
this is actually the opposite direction from what we should be taking,
and this direction wouldn't

Revert rest of `IRBuilderBase`'s short-circuiting folds

Upon further investigation and discussion,
this is actually the opposite direction from what we should be taking,
and this direction wouldn't solve the motivational problem anyway.

Additionally, some more (polly) tests have escaped being updated.
So, let's just take a step back here.

This reverts commit f3190dedeef9da2109ea57e4cb372f295ff53b88.
This reverts commit 749581d21f2b3f53e4fca4eb8728c942d646893b.
This reverts commit f3df87d57e096143670e0fd396e81d43393a2dd2.
This reverts commit ab1dbcecd6f0969976fafd62af34730436ad5944.

show more ...

[IR] `IRBuilderBase::CreateAnd()`: short-circuit `x & 0` --> `0`

https://alive2.llvm.org/ce/z/YzPhSb

Refs. https://reviews.llvm.org/D109368#3089809

[IR] `IRBuilderBase::CreateAnd()`: fix short-circuiting for constant on LHS

Refs. https://reviews.llvm.org/D109368#3089809

[NFC] Re-autogenerate check lines in some tests to ease of future update

[LoopPredication] Preserve MemorySSA

Since LICM has now unconditionally moved to MemorySSA based form, all
passes that run in same LPM as LICM need to preserve MemorySSA (i.e. our
downstream pipeli

[LoopPredication] Preserve MemorySSA

Since LICM has now unconditionally moved to MemorySSA based form, all
passes that run in same LPM as LICM need to preserve MemorySSA (i.e. our
downstream pipeline).

Added loop-mssa to all tests and perform -verify-memoryssa within
LoopPredication itself.

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

show more ...

[LoopPred] Extend LFTR normalization to the inverse EQ case

A while back, I added support for NE latches formed by LFTR. I didn't think that quite through, as LFTR will also produce the inverse EQ

[LoopPred] Extend LFTR normalization to the inverse EQ case

A while back, I added support for NE latches formed by LFTR. I didn't think that quite through, as LFTR will also produce the inverse EQ form for some loops and I hadn't handled that. This change just adds handling for that case as well.

llvm-svn: 365419

show more ...

Revert "[IRBuilder] Fold consistently for or/and whether constant is LHS or RHS"

This reverts commit r365260 which broke the following tests:

Clang :: CodeGenCXX/cfi-mfcall.cpp
Clang :: Cod

Revert "[IRBuilder] Fold consistently for or/and whether constant is LHS or RHS"

This reverts commit r365260 which broke the following tests:

Clang :: CodeGenCXX/cfi-mfcall.cpp
Clang :: CodeGenObjC/ubsan-nullability.m
LLVM :: Transforms/LoopVectorize/AArch64/pr36032.ll

llvm-svn: 365284

show more ...

[IRBuilder] Fold consistently for or/and whether constant is LHS or RHS

Without this, we have the unfortunate property that tests are dependent on the order of operads passed the CreateOr and Create

[IRBuilder] Fold consistently for or/and whether constant is LHS or RHS

Without this, we have the unfortunate property that tests are dependent on the order of operads passed the CreateOr and CreateAnd functions. In actual usage, we'd promptly optimize them away, but it made tests slightly more verbose than they should have been.

llvm-svn: 365260

show more ...

[LoopPred] Fix a bug in unconditional latch bailout introduced in r362284

This is a really silly bug that even a simple test w/an unconditional latch would have caught. I tried to guard against the

[LoopPred] Fix a bug in unconditional latch bailout introduced in r362284

This is a really silly bug that even a simple test w/an unconditional latch would have caught. I tried to guard against the case, but put it in the wrong if check. Oops.

llvm-svn: 362727

show more ...

[LoopPred] Handle a subset of NE comparison based latches

At the moment, LoopPredication completely bails out if it sees a latch of the form:
%cmp = icmp ne %iv, %N
br i1 %cmp, label %loop, label %e

[LoopPred] Handle a subset of NE comparison based latches

At the moment, LoopPredication completely bails out if it sees a latch of the form:
%cmp = icmp ne %iv, %N
br i1 %cmp, label %loop, label %exit
OR
%cmp = icmp ne %iv.next, %NPlus1
br i1 %cmp, label %loop, label %exit

This is unfortunate since this is exactly the form that LFTR likes to produce. So, go ahead and recognize simple cases where we can.

For pre-increment loops, we leverage the fact that LFTR likes canonical counters (i.e. those starting at zero) and a (presumed) range fact on RHS to discharge the check trivially.

For post-increment forms, the key insight is in remembering that LFTR had to insert a (N+1) for the RHS. CVP can hopefully prove that add nsw/nuw (if there's appropriate range on N to start with). This leaves us both with the post-inc IV and the RHS involving an nsw/nuw add, and SCEV can discharge that with no problem.

This does still need to be extended to handle non-one steps, or other harder patterns of variable (but range restricted) starting values. That'll come later.

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

llvm-svn: 362282

show more ...

[Tests] Better represent the postinc form produced by LFTR in LoopPred tests

llvm-svn: 362270

[Tests] Add ne icmp tests w/preinc forms for LoopPredication

Turns out this is substaintially easier to match then the post increment form, so let's start there.

llvm-svn: 362260

[Tests] Add tests for loop predication of loops w/ne latch conditions

llvm-svn: 362244

[LoopPredication] Allow predication of loop invariant computations (within the loop)

The purpose of this patch is to eliminate a pass ordering dependence between LoopPredication and LICM. To underst

[LoopPredication] Allow predication of loop invariant computations (within the loop)

The purpose of this patch is to eliminate a pass ordering dependence between LoopPredication and LICM. To understand the purpose, consider the following snippet of code inside some loop 'L' with IV 'i'
A = _a.length;
guard (i < A)
a = _a[i]
B = _b.length;
guard (i < B);
b = _b[i];
...
Z = _z.length;
guard (i < Z)
z = _z[i]
accum += a + b + ... + z;

Today, we need LICM to hoist the length loads, LoopPredication to make the guards loop invariant, and TrivialUnswitch to eliminate the loop invariant guard to establish must execute for the next length load. Today, if we can't prove speculation safety, we'd have to iterate these three passes 26 times to reduce this example down to the minimal form.

Using the fact that the array lengths are known to be invariant, we can short circuit this iteration. By forming the loop invariant form of all the guards at once, we remove the need for LoopPredication from the iterative cycle. At the moment, we'd still have to iterate LICM and TrivialUnswitch; we'll leave that part for later.

As a secondary benefit, this allows LoopPred to expose peeling oppurtunities in a much more obvious manner. See the udiv test changes as an example. If the udiv was not hoistable (i.e. we couldn't prove speculation safety) this would be an example where peeling becomes obviously profitable whereas it wasn't before.

A couple of subtleties in the implementation:
- SCEV's isSafeToExpand guarantees speculation safety (i.e. let's us expand at a new point). It is not a precondition for expansion if we know the SCEV corresponds to a Value which dominates the requested expansion point.
- SCEV's isLoopInvariant returns true for expressions which compute the same value across all iterations executed, regardless of where the original Value is located. (i.e. it can be in the loop) This implies we have a speculation burden to prove before expanding them outside loops.
- invariant_loads and AA->pointsToConstantMemory are two cases that SCEV currently does not handle, but meets the SCEV definition of invariance. I plan to sink this part into SCEV once this has baked for a bit.

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

llvm-svn: 358684

show more ...

Revert "Temporarily Revert "Add basic loop fusion pass.""

The reversion apparently deleted the test/Transforms directory.

Will be re-reverting again.

llvm-svn: 358552

[LoopPred] Hoist and of predicated checks where legal

If we have multiple range checks which can be predicated, hoist the and of the results outside the loop. This minorly cleans up the resulting I

[LoopPred] Hoist and of predicated checks where legal

If we have multiple range checks which can be predicated, hoist the and of the results outside the loop. This minorly cleans up the resulting IR, but the main motivation is as a building block for D60093.

llvm-svn: 358419

show more ...

[LoopPred] Be uniform about proving generated conditions

We'd been optimizing the case where the predicate was obviously true, do the same for the false case. Mostly just for completeness sake, but

[LoopPred] Be uniform about proving generated conditions

We'd been optimizing the case where the predicate was obviously true, do the same for the false case. Mostly just for completeness sake, but also may improve compile time in loops which will exit through the guard. Such loops are presumed rare in fastpath code, but may be present down untaken paths, so optimizing for them is still useful.

llvm-svn: 357408

show more ...

[LoopPred] Delete the old condition expressions if unused

LoopPredication was replacing the original condition, but leaving the instructions to compute the old conditions around. This would get cle

[LoopPred] Delete the old condition expressions if unused

LoopPredication was replacing the original condition, but leaving the instructions to compute the old conditions around. This would get cleaned up by other passes of course, but we might as well do it eagerly. That also makes the test output less confusing.

llvm-svn: 357406

show more ...

[Tests] Autogen all the LoopPredication tests

I'm about to make some changes to the pass which cause widespread - but uninteresting - test diffs. Prepare the tests for easy updating.

llvm-svn: 357

[Tests] Autogen all the LoopPredication tests

I'm about to make some changes to the pass which cause widespread - but uninteresting - test diffs. Prepare the tests for easy updating.

llvm-svn: 357404

show more ...