aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Transforms/Utils/LoopVersioning.cpp
AgeCommit message (Collapse)AuthorFilesLines
2025-09-09[LoopUtils] Simplify expanded RT-checks (#157518)Ramkumar Ramachandra1-0/+2
Follow up on 528b13d ([SCEVExp] Add helper to clean up dead instructions after expansion.) to hoist the SCEVExapnder::eraseDeadInstructions call from LoopVectorize into the LoopUtils APIs add[Diff]RuntimeChecks, so that other callers (LoopDistribute and LoopVersioning) can benefit from the patch.
2025-04-15[LoopVer] Add function to get the alias_scope/noalias metadata (NFC).Florian Hahn1-13/+22
Split out logic to get noalias/alias_scope metadata to separate function in LoopVersioning. This will be used to migrate away from annotateInstWithNoAlias in LV.
2024-12-16[LoopVersioning] Add a check to see if the input loop is in LCSSA form (#116443)Vedant Paranjape1-0/+4
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
2024-09-23[Loops] Use forgetLcssaPhiWithNewPredecessor() in more placesNikita Popov1-1/+1
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.
2024-08-03[Transforms] Construct SmallVector with ArrayRef (NFC) (#101851)Kazu Hirata1-4/+2
2024-06-27[IR] Add getDataLayout() helpers to BasicBlock and Instruction (#96902)Nikita Popov1-3/+3
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.
2023-09-11[NFC][RemoveDIs] Prefer iterator-insertion over instructionsJeremy Morse1-2/+2
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
2023-04-17Remove several no longer needed includes. NFCIBjorn Pettersson1-1/+0
Mostly removing includes of InitializePasses.h and Pass.h in passes that no longer has support for the legacy PM.
2023-04-16[Transforms] Apply fixes from performance-for-range-copy (NFC)Kazu Hirata1-1/+1
2023-02-14[LoopVersioning] Remove legacy passFangrui Song1-51/+2
Following recent changes to remove non-core features of the legacy PM/optimization pipeline.
2022-10-04[LoopVersioning,LLE] Clear LoopAccessInfoManager after making changes.Florian Hahn1-0/+1
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
2022-10-04[LAA] Pass LoopAccessInfoManager instead of GetLAA function.Florian Hahn1-14/+7
Use LoopAccessInfoManager directly instead of various GetLAA lambdas. Depends on D134608. Reviewed By: aeubanks Differential Revision: https://reviews.llvm.org/D134609
2022-10-01[LAA] Change to function analysis for new PM.Florian Hahn1-8/+2
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
2022-09-23[LoopVersioning] Invalidate SCEV for phi if new values are added.Florian Hahn1-1/+3
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.
2022-02-10[PSE] Remove assumption that top level predicate is union from public ↵Philip Reames1-2/+2
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.
2022-02-06[Transforms] Use default member initialization in LoopVersioning (NFC)Kazu Hirata1-2/+1
2022-01-27[LoopVersioning] Use IRBuilder for OR simplification.Florian Hahn1-11/+10
2021-12-16Revert "[LoopVersioning] Allow versionLoop to create plain branch inst when ↵eopXD1-13/+7
no runtime check is specified" This reverts commit fbf6c8ac1589a4be68ee549257f1d528937ac582.
2021-12-16[LoopVersioning] Allow versionLoop to create plain branch inst when no ↵Yueh-Ting Chen1-7/+13
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
2021-10-18[LoopUtils] Simplify addRuntimeCheck to return a single value.Florian Hahn1-4/+3
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.
2021-09-30[BPI] Keep BPI available in loop passes through LoopStandardAnalysisResultsAnna Thomas1-2/+2
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
2021-08-16[MemorySSA] Remove unnecessary MSSA dependenciesNikita Popov1-5/+2
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
2021-07-06[LoopVersion] Move an assert [nfc-ish]Philip Reames1-1/+1
2021-05-17Revert "[LV] Unconditionally branch from middle to scalar preheader if the ↵Philip Reames1-1/+1
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.
2021-05-17[LV] Unconditionally branch from middle to scalar preheader if the scalar ↵Philip Reames1-1/+1
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
2021-05-17Revert "[LV] Unconditionally branch from middle to scalar preheader if the ↵Philip Reames1-1/+1
scalar loop must execute" This reverts commit c23ce54b36b1a52eb280ea1d59802b56d6dd9800. I apparently missed some newly added non-x86 tests.
2021-05-17[LV] Unconditionally branch from middle to scalar preheader if the scalar ↵Philip Reames1-1/+1
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
2021-02-05Revert "[LV] Unconditionally branch from middle to scalar preheader if the ↵Adrian Kuegel1-1/+1
scalar loop must execute" This reverts commit 3e5ce49e5371ce4feadbf97dd5c2b652d9db3d1d. Tests started failing on PPC, for example: http://lab.llvm.org:8011/#/builders/105/builds/5569
2021-02-04[LV] Unconditionally branch from middle to scalar preheader if the scalar ↵Philip Reames1-1/+1
loop must execute 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 NFCI-ish prep work, but the changes are a bit too involved for me to feel comfortable tagging the change that way. Differential Revision: https://reviews.llvm.org/D94892
2021-01-27[LoopUtils] Pass SCEVExpander instead SE to addRuntimeChecks.Florian Hahn1-3/+6
This gives the user control over which expander to use, which in turn allows the user to decide what to do with the expanded instructions. Used in D75980. Reviewed By: lebedev.ri Differential Revision: https://reviews.llvm.org/D94295
2021-01-12[LV] Weaken spuriously strong assert in LoopVersioningPhilip Reames1-1/+1
LoopVectorize uses some utilities on LoopVersioning, but doesn't actually use it for, you know, versioning. As a result, the precondition LoopVersioning expects is too strong for this user. At the moment, LoopVectorize supports any loop with a unique exit block, so check the same precondition here. Really, the whole class structure here is a mess. We should separate the actual versioning from the metadata updates, but that's a bigger problem.
2020-12-27[LV] Set up branch from middle block earlier.Florian Hahn1-1/+3
Previously the branch from the middle block to the scalar preheader & exit was being set-up at the end of skeleton creation in completeLoopSkeleton. Inserting SCEV or runtime checks may result in LCSSA phis being created, if they are required. Adjusting branches afterwards may break those PHIs. To avoid this, we can instead create the branch from the middle block to the exit after we created the middle block, so we have the final CFG before potentially adjusting/creating PHIs. This fixes a crash for the included test case. For the non-crashing case, this is almost a NFC with respect to the generated code. The only change is the order of the predecessors of the involved branch targets. Note an assertion was moved from LoopVersioning() to LoopVersioning::versionLoop. Adjusting the branches means loop-simplify form may be broken before constructing LoopVersioning. But LV only uses LoopVersioning to annotate the loop instructions with !noalias metadata, which does not require loop-simplify form. This is a fix for an existing issue uncovered by D93317.
2020-12-17[NFC] Reduce include files dependency and AA header cleanup (part 2).dfukalov1-1/+0
Continuing work started in https://reviews.llvm.org/D92489: Removed a bunch of includes from "AliasAnalysis.h" and "LoopPassManager.h". Reviewed By: RKSimon Differential Revision: https://reviews.llvm.org/D92852
2020-12-14[LAA] Relax restrictions on early exits in loop structurePhilip Reames1-1/+4
his is a preparation patch for supporting multiple exits in the loop vectorizer, by itself it should be mostly NFC. This patch moves the loop structure checks from LAA to their respective consumers (where duplicates don't already exist). Moving the checks does end up changing some of the optimization warnings and debug output slightly, but nothing that appears to be a regression. Why do this? Well, after auditing the code, I can't actually find anything in LAA itself which relies on having all instructions within a loop execute an equal number of times. This patch simply makes this explicit so that if one consumer - say LV in the near future (hopefully) - wants to handle a broader class of loops, it can do so. Differential Revision: https://reviews.llvm.org/D92066
2020-10-24[LoopVersioning] Form dedicated exits for versioned loop to preserve ↵TaWeiTu1-0/+5
simplify form The exit blocks of the versioned and non-versioned loops are not dedicated and thus the two loops are not in simplify form. Insert dummy exit blocks after loop versioning with `formDedicatedExits()` to preserve the simplify form for subsequence passes. Reviewed By: aeubanks Differential Revision: https://reviews.llvm.org/D89569
2020-10-15[LoopVersion] Unify SCEVChecks and alias check handling (NFC).Florian Hahn1-19/+10
This is an initial cleanup of the way LoopVersioning interacts with LAA. Currently LoopVersioning has 2 ways of initializing things: 1. Passing LAI and passing UseLAIChecks = true 2. Passing UseLAIChecks = false, followed by calling setSCEVChecks and setAliasChecks. Both ways of initializing lead to the same result and the duplication seems more complicated than necessary. This patch removes the UseLAIChecks flag from the constructor and the setSCEVChecks & setAliasChecks helpers and move initialization exclusively to the constructor. This simplifies things, by providing a single way to initialize LoopVersioning and reducing duplication. Reviewed By: Meinersbur, lebedev.ri Differential Revision: https://reviews.llvm.org/D84406
2020-09-22[LoopInfo] empty() -> isInnermost(), add isOutermost()Stefanos Baziotis1-1/+1
Differential Revision: https://reviews.llvm.org/D82895
2020-09-15[BFI] Make BFI information available through loop passes inside ↵Wenlei He1-1/+2
LoopStandardAnalysisResults ~~D65060 uncovered that trying to use BFI in loop passes can lead to non-deterministic behavior when blocks are re-used while retaining old BFI data.~~ ~~To make sure BFI is preserved through loop passes a Value Handle (VH) callback is registered on blocks themselves. When a block is freed it now also wipes out the accompanying BFI entry such that stale BFI data can no longer persist resolving the determinism issue. ~~ ~~An optimistic approach would be to incrementally update BFI information throughout the loop passes rather than only invalidating them on removed blocks. The issues with that are:~~ ~~1. It is not clear how BFI information should be incrementally updated: If a block is duplicated does its BFI information come with? How about if it's split/modified/moved around? ~~ ~~2. Assuming we can address these problems the implementation here will be a massive undertaking. ~~ ~~There's a known need of BFI in LICM analysis which requires correct but not incrementally updated BFI data. A follow-up change can register BFI in all loop passes so this preserved but potentially lossy data is available to any loop pass that wants it.~~ See: D75341 for an identical implementation of preserving BFI via VH callbacks. The previous statements do still apply but this change no longer has to be in this diff because it's already upstream 😄 . This diff also moves BFI to be a part of LoopStandardAnalysisResults since the previous method using getCachedResults now (correctly!) statically asserts (D72893) that this data isn't static through the loop passes. Testing Ninja check Reviewed By: asbirlea, nikic Differential Revision: https://reviews.llvm.org/D86156
2020-08-03Fix layering violation Transforms/Utils -> ScalarArthur Eubanks1-1/+3
Introduced in D85063.
2020-08-03[NewPM][LoopVersioning] Port LoopVersioning to NPMArthur Eubanks1-35/+72
Reviewed By: ychen, fhahn Differential Revision: https://reviews.llvm.org/D85063
2020-05-20[SCEV] Move ScalarEvolutionExpander.cpp to Transforms/Utils (NFC).Florian Hahn1-1/+1
SCEVExpander modifies the underlying function so it is more suitable in Transforms/Utils, rather than Analysis. This allows using other transform utils in SCEVExpander. This patch was originally committed as b8a3c34eee06, but broke the modules build, as LoopAccessAnalysis was using the Expander. The code-gen part of LAA was moved to lib/Transforms recently, so this patch can be landed again. Reviewers: sanjoy.google, efriedma, reames Reviewed By: sanjoy.google Differential Revision: https://reviews.llvm.org/D71537
2020-05-10[LAA] Move runtime-check generation to Transforms/Utils/loopUtils (NFC)Florian Hahn1-1/+3
Currently LAA's uses of ScalarEvolutionExpander blocks moving the expander from Analysis to Transforms. Conceptually the expander does not fit into Analysis (it is only used for code generation) and runtime-check generation also seems to be better suited as a transformation utility. Reviewers: Ayal, anemet Reviewed By: Ayal Differential Revision: https://reviews.llvm.org/D78460
2020-04-30[LoopVersioning] Update setAliasChecks to take ArrayRef argument (NFC).Florian Hahn1-3/+3
This cleanup was suggested as part of D78458.
2020-04-28[LAA] Move CheckingPtrGroup/PointerCheck outside class (NFC).Florian Hahn1-3/+2
This allows forward declarations of PointerCheck, which in turn reduce the number of times LoopAccessAnalysis needs to be included. Ultimately this helps with moving runtime check generation to Transforms/Utils/LoopUtils.h, without having to include it there. Reviewers: anemet, Ayal Reviewed By: Ayal Differential Revision: https://reviews.llvm.org/D78458
2020-01-04Revert "[SCEV] Move ScalarEvolutionExpander.cpp to Transforms/Utils (NFC)."Florian Hahn1-1/+1
This reverts commit 51ef53f3bd23559203fe9af82ff2facbfedc1db3, as it breaks some bots.
2020-01-04[SCEV] Move ScalarEvolutionExpander.cpp to Transforms/Utils (NFC).Florian Hahn1-1/+1
SCEVExpander modifies the underlying function so it is more suitable in Transforms/Utils, rather than Analysis. This allows using other transform utils in SCEVExpander. Reviewers: sanjoy.google, efriedma, reames Reviewed By: sanjoy.google Differential Revision: https://reviews.llvm.org/D71537
2019-11-14Add missing includes needed to prune LLVMContext.h include, NFCReid Kleckner1-0/+1
These are a pre-requisite to removing #include "llvm/Support/Options.h" from LLVMContext.h: https://reviews.llvm.org/D70280
2019-11-13Sink all InitializePasses.h includesReid Kleckner1-0/+1
This file lists every pass in LLVM, and is included by Pass.h, which is very popular. Every time we add, remove, or rename a pass in LLVM, it caused lots of recompilation. I found this fact by looking at this table, which is sorted by the number of times a file was changed over the last 100,000 git commits multiplied by the number of object files that depend on it in the current checkout: recompiles touches affected_files header 342380 95 3604 llvm/include/llvm/ADT/STLExtras.h 314730 234 1345 llvm/include/llvm/InitializePasses.h 307036 118 2602 llvm/include/llvm/ADT/APInt.h 213049 59 3611 llvm/include/llvm/Support/MathExtras.h 170422 47 3626 llvm/include/llvm/Support/Compiler.h 162225 45 3605 llvm/include/llvm/ADT/Optional.h 158319 63 2513 llvm/include/llvm/ADT/Triple.h 140322 39 3598 llvm/include/llvm/ADT/StringRef.h 137647 59 2333 llvm/include/llvm/Support/Error.h 131619 73 1803 llvm/include/llvm/Support/FileSystem.h Before this change, touching InitializePasses.h would cause 1345 files to recompile. After this change, touching it only causes 550 compiles in an incremental rebuild. Reviewers: bkramer, asbirlea, bollu, jdoerfert Differential Revision: https://reviews.llvm.org/D70211
2019-09-13[BasicBlockUtils] Add optional BBName argument, in line with BB:splitBasicBlockFlorian Hahn1-2/+2
Reviewers: spatel, asbirlea, craig.topper Reviewed By: asbirlea Differential Revision: https://reviews.llvm.org/D67521 llvm-svn: 371819
2019-06-12LoopVersioning: Respect convergentMatt Arsenault1-2/+3
This changes the standalone pass only. Arguably the utility class itself should assert there are no convergent calls. However, a target pass with additional context may still be able to version a loop if all of the dynamic conditions are sufficiently uniform. llvm-svn: 363165