[LoopVersioning] Add a check to see if the input loop is in LCSSA form (#116443)

Loop Optimizations expect the input loop to be in LCSSA form. But it
seems that LoopVersioning doesn't have any chec

[LoopVersioning] Add a check to see if the input loop is in LCSSA form (#116443)

Loop Optimizations expect the input loop to be in LCSSA form. But it
seems that LoopVersioning doesn't have any check to see if the loop is
actually in LCSSA form. As a result, if we give it a loop which is not
in LCSSA form but still correct semantically, the resulting
transformation fails to pass through verifier pass with the following
error.

Instruction does not dominate all uses!
%inc = add nsw i16 undef, 1
store i16 %inc, ptr @c, align 1

As the loop is not in LCSSA form, LoopVersioning's transformations leads
to invalid IR! As some instructions do not dominate all their uses.

This patch checks if a loop is in LCSSA form, if not it will call
formLCSSARecursively on the loop before passing it to LoopVersioning.

Fixes: #36998

show more ...

[Loops] Use forgetLcssaPhiWithNewPredecessor() in more places

Use the more aggressive invalidation method in a number of places
that add incoming values to lcssa phi nodes. It is likely that
it's po

[Loops] Use forgetLcssaPhiWithNewPredecessor() in more places

Use the more aggressive invalidation method in a number of places
that add incoming values to lcssa phi nodes. It is likely that
it's possible to construct cases with incorrect SCEV preservation
similar to https://github.com/llvm/llvm-project/issues/109333 for
these.

show more ...

[Transforms] Construct SmallVector with ArrayRef (NFC) (#101851)

[IR] Add getDataLayout() helpers to BasicBlock and Instruction (#96902)

This is a helper to avoid writing `getModule()->getDataLayout()`. I
regularly try to use this method only to remember it does

[IR] Add getDataLayout() helpers to BasicBlock and Instruction (#96902)

This is a helper to avoid writing `getModule()->getDataLayout()`. I
regularly try to use this method only to remember it doesn't exist...

`getModule()->getDataLayout()` is also a common (the most common?)
reason why code has to include the Module.h header.

show more ...

[NFC][RemoveDIs] Prefer iterator-insertion over instructions

Continuing the patch series to get rid of debug intrinsics [0], instruction
insertion needs to be done with iterators rather than instruc

[NFC][RemoveDIs] Prefer iterator-insertion over instructions

Continuing the patch series to get rid of debug intrinsics [0], instruction
insertion needs to be done with iterators rather than instruction pointers,
so that we can communicate information in the iterator class. This patch
adds an iterator-taking insertBefore method and converts various call sites
to take iterators. These are all sites where such debug-info needs to be
preserved so that a stage2 clang can be built identically; it's likely that
many more will need to be changed in the future.

At this stage, this is just changing the spelling of a few operations,
which will eventually become signifiant once the debug-info bearing
iterator is used.

[0] https://discourse.llvm.org/t/rfc-instruction-api-changes-needed-to-eliminate-debug-intrinsics-from-ir/68939

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

show more ...

Remove several no longer needed includes. NFCI

Mostly removing includes of InitializePasses.h and Pass.h in
passes that no longer has support for the legacy PM.

[Transforms] Apply fixes from performance-for-range-copy (NFC)

[LoopVersioning] Remove legacy pass

Following recent changes to remove non-core features of the legacy PM/optimization pipeline.

[LoopVersioning,LLE] Clear LoopAccessInfoManager after making changes.

Loop versioning changes the control-flow, which may impact SCEVs cached
by for other loops in LoopAccessInfoManager. Clear the

[LoopVersioning,LLE] Clear LoopAccessInfoManager after making changes.

Loop versioning changes the control-flow, which may impact SCEVs cached
by for other loops in LoopAccessInfoManager. Clear the manager after
making changes.

Fixes #57825.

Depends on D134609.

Reviewed By: aeubanks

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

show more ...

[LAA] Pass LoopAccessInfoManager instead of GetLAA function.

Use LoopAccessInfoManager directly instead of various GetLAA lambdas.

Depends on D134608.

Reviewed By: aeubanks

Differential Revision:

[LAA] Pass LoopAccessInfoManager instead of GetLAA function.

Use LoopAccessInfoManager directly instead of various GetLAA lambdas.

Depends on D134608.

Reviewed By: aeubanks

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

show more ...

[LAA] Change to function analysis for new PM.

At the moment, LoopAccessAnalysis is a loop analysis for the new pass
manager. The issue with that is that LAI caches SCEV expressions and
modifications

[LAA] Change to function analysis for new PM.

At the moment, LoopAccessAnalysis is a loop analysis for the new pass
manager. The issue with that is that LAI caches SCEV expressions and
modifications in a loop may impact SCEV expressions in other loops, but
we do not have a convenient way to invalidate LAI for other loops
withing a loop pipeline.

To avoid this issue, turn it into a function analysis which returns a
manager object that keeps track of the individual LAI objects per loop.

Fixes #50940.

Fixes #51669.

Reviewed By: aeubanks

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

show more ...

[LoopVersioning] Invalidate SCEV for phi if new values are added.

After 20d798bd47ec5191d, SCEV looks through PHIs with a single incoming
value. This means adding a new incoming value may change the

[LoopVersioning] Invalidate SCEV for phi if new values are added.

After 20d798bd47ec5191d, SCEV looks through PHIs with a single incoming
value. This means adding a new incoming value may change the SCEV for a
phi. Add missing invalidation when an existing PHI is reused during
LoopVersioning. New incoming values will be added later from the
versioned loop.

Similar issues have been fixed by also adding missing invalidation.

Fixes #57825.

Note that the test case unfortunately requires running loop-vectorize
followed by loop-load-elimination, which does the actual versioning. I
don't think it is possible to reproduce the failure without that
combination.

show more ...

[PSE] Remove assumption that top level predicate is union from public interface [NFC*]

Note that this doesn't actually cause the top level predicate to become a non-union just yet.

The * above come

[PSE] Remove assumption that top level predicate is union from public interface [NFC*]

Note that this doesn't actually cause the top level predicate to become a non-union just yet.

The * above comes from a case in the LoopVectorizer where a predicate which is later proven no longer blocks vectorization due to a change from checking if predicates exists to whether the predicate is possibly false.

show more ...

[Transforms] Use default member initialization in LoopVersioning (NFC)

[LoopVersioning] Use IRBuilder for OR simplification.

Revert "[LoopVersioning] Allow versionLoop to create plain branch inst when no runtime check is specified"

This reverts commit fbf6c8ac1589a4be68ee549257f1d528937ac582.

[LoopVersioning] Allow versionLoop to create plain branch inst when no runtime check is specified

After this function call, the LLVM IR would look like the following:

```
if (true)
/* NonVersione

[LoopVersioning] Allow versionLoop to create plain branch inst when no runtime check is specified

After this function call, the LLVM IR would look like the following:

```
if (true)
/* NonVersionedLoop */
else
/* VersionedLoop */
```

Reviewed By: Whitney

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

show more ...

[LoopUtils] Simplify addRuntimeCheck to return a single value.

This simplifies the return value of addRuntimeCheck from a pair of
instructions to a single `Value *`.

The existing users of addRuntim

[LoopUtils] Simplify addRuntimeCheck to return a single value.

This simplifies the return value of addRuntimeCheck from a pair of
instructions to a single `Value *`.

The existing users of addRuntimeChecks were ignoring the first element
of the pair, hence there is not reason to track FirstInst and return
it.

Additionally all users of addRuntimeChecks use the second returned
`Instruction *` just as `Value *`, so there is no need to return an
`Instruction *`. Therefore there is no need to create a redundant
dummy `and X, true` instruction any longer.

Effectively this change should not impact the generated code because the
redundant AND will be folded by later optimizations. But it is easy to
avoid creating it in the first place and it allows more accurately
estimating the cost of the runtime checks.

show more ...

[BPI] Keep BPI available in loop passes through LoopStandardAnalysisResults

This is analogous to D86156 (which preserves "lossy" BFI in loop
passes). Lossy means that the analysis preserved may not

[BPI] Keep BPI available in loop passes through LoopStandardAnalysisResults

This is analogous to D86156 (which preserves "lossy" BFI in loop
passes). Lossy means that the analysis preserved may not be up to date
with regards to new blocks that are added in loop passes, but BPI will
not contain stale pointers to basic blocks that are deleted by the loop
passes.

This is achieved through BasicBlockCallbackVH in BPI, which calls
eraseBlock that updates the data structures in BPI whenever a basic
block is deleted.

This patch does not have any changes in the upstream pipeline, since
none of the loop passes in the pipeline use BPI currently.
However, since BPI wasn't previously preserved in loop passes, the loop
predication pass was invoking BPI *on the entire
function* every time it ran in an LPM. This caused massive compile time
in our downstream LPM invocation which contained loop predication.

See updated test with an invocation of a loop-pipeline containing loop
predication and -debug-pass turned ON.

Reviewed-By: asbirlea, modimo
Differential Revision: https://reviews.llvm.org/D110438

show more ...

[MemorySSA] Remove unnecessary MSSA dependencies

LoopLoadElimination, LoopVersioning and LoopVectorize currently
fetch MemorySSA when construction LoopAccessAnalysis. However,
LoopAccessAnalysis doe

[MemorySSA] Remove unnecessary MSSA dependencies

LoopLoadElimination, LoopVersioning and LoopVectorize currently
fetch MemorySSA when construction LoopAccessAnalysis. However,
LoopAccessAnalysis does not actually use MemorySSA and we can pass
nullptr instead.

This saves one MemorySSA calculation in the default pipeline, and
thus improves compile-time.

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

show more ...

[LoopVersion] Move an assert [nfc-ish]

Revert "[LV] Unconditionally branch from middle to scalar preheader if the scalar loop must execute (try 3)"

This reverts commit 6d3e3ae8a9ca10e063d541a959f4fe4cdb003dba.

Still seeing PPC build bot

Revert "[LV] Unconditionally branch from middle to scalar preheader if the scalar loop must execute (try 3)"

This reverts commit 6d3e3ae8a9ca10e063d541a959f4fe4cdb003dba.

Still seeing PPC build bot failures, and one arm self host bot failing. I'm officially stumped, and need help from a bot owner to reduce.

show more ...

[LV] Unconditionally branch from middle to scalar preheader if the scalar loop must execute (try 3)

Resubmit after fixing test/Transforms/LoopVectorize/ARM/mve-gather-scatter-tailpred.ll

Previous c

[LV] Unconditionally branch from middle to scalar preheader if the scalar loop must execute (try 3)

Resubmit after fixing test/Transforms/LoopVectorize/ARM/mve-gather-scatter-tailpred.ll

Previous commit message...

This is a resubmit of 3e5ce4 (which was reverted by 7fe41ac). The original commit caused a PPC build bot failure we never really got to the bottom of. I can't reproduce the issue, and the bot owner was non-responsive. In the meantime, we stumbled across an issue which seems possibly related, and worked around a latent bug in 80e8025. My best guess is that the original patch exposed that latent issue at higher frequency, but it really is just a guess.

Original commit message follows...

If we know that the scalar epilogue is required to run, modify the CFG to end the middle block with an unconditional branch to scalar preheader. This is instead of a conditional branch to either the preheader or the exit block.

The motivation to do this is to support multiple exit blocks. Specifically, the current structure forces us to identify immediate dominators and *which* exit block to branch from in the middle terminator. For the multiple exit case - where we know require scalar will hold - these questions are ill formed.

This is the last change needed to support multiple exit loops, but since the diffs are already large enough, I'm going to land this, and then enable separately. You can think of this as being NFCIish prep work, but the changes are a bit too involved for me to feel comfortable tagging the review that way.

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

show more ...

Revert "[LV] Unconditionally branch from middle to scalar preheader if the scalar loop must execute"

This reverts commit c23ce54b36b1a52eb280ea1d59802b56d6dd9800. I apparently missed some newly add

Revert "[LV] Unconditionally branch from middle to scalar preheader if the scalar loop must execute"

This reverts commit c23ce54b36b1a52eb280ea1d59802b56d6dd9800. I apparently missed some newly added non-x86 tests.

show more ...

[LV] Unconditionally branch from middle to scalar preheader if the scalar loop must execute

This is a resubmit of 3e5ce4 (which was reverted by 7fe41ac). The original commit caused a PPC build bot

[LV] Unconditionally branch from middle to scalar preheader if the scalar loop must execute

This is a resubmit of 3e5ce4 (which was reverted by 7fe41ac). The original commit caused a PPC build bot failure we never really got to the bottom of. I can't reproduce the issue, and the bot owner was non-responsive. In the meantime, we stumbled across an issue which seems possibly related, and worked around a latent bug in 80e8025. My best guess is that the original patch exposed that latent issue at higher frequency, but it really is just a guess.

Original commit message follows...

If we know that the scalar epilogue is required to run, modify the CFG to end the middle block with an unconditional branch to scalar preheader. This is instead of a conditional branch to either the preheader or the exit block.

The motivation to do this is to support multiple exit blocks. Specifically, the current structure forces us to identify immediate dominators and *which* exit block to branch from in the middle terminator. For the multiple exit case - where we know require scalar will hold - these questions are ill formed.

This is the last change needed to support multiple exit loops, but since the diffs are already large enough, I'm going to land this, and then enable separately. You can think of this as being NFCIish prep work, but the changes are a bit too involved for me to feel comfortable tagging the review that way.

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

show more ...