///===- SimpleLoopUnswitch.cpp - Hoist loop-invariant control flow ---------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// #include "llvm/Transforms/Scalar/SimpleLoopUnswitch.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/Sequence.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/Twine.h" #include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/BlockFrequencyInfo.h" #include "llvm/Analysis/CFG.h" #include "llvm/Analysis/CodeMetrics.h" #include "llvm/Analysis/DomTreeUpdater.h" #include "llvm/Analysis/GuardUtils.h" #include "llvm/Analysis/LoopAnalysisManager.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/LoopIterator.h" #include "llvm/Analysis/MemorySSA.h" #include "llvm/Analysis/MemorySSAUpdater.h" #include "llvm/Analysis/MustExecute.h" #include "llvm/Analysis/ProfileSummaryInfo.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/Constant.h" #include "llvm/IR/Constants.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" #include "llvm/IR/IRBuilder.h" #include "llvm/IR/InstrTypes.h" #include "llvm/IR/Instruction.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Module.h" #include "llvm/IR/PatternMatch.h" #include "llvm/IR/ProfDataUtils.h" #include "llvm/IR/Use.h" #include "llvm/IR/Value.h" #include "llvm/Support/Casting.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/GenericDomTree.h" #include "llvm/Support/InstructionCost.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Scalar/LoopPassManager.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/Cloning.h" #include "llvm/Transforms/Utils/Local.h" #include "llvm/Transforms/Utils/LoopUtils.h" #include "llvm/Transforms/Utils/ValueMapper.h" #include <algorithm> #include <cassert> #include <iterator> #include <numeric> #include <optional> #include <utility> #define DEBUG_TYPE … usingnamespacellvm; usingnamespacellvm::PatternMatch; STATISTIC(NumBranches, "Number of branches unswitched"); STATISTIC(NumSwitches, "Number of switches unswitched"); STATISTIC(NumSelects, "Number of selects turned into branches for unswitching"); STATISTIC(NumGuards, "Number of guards turned into branches for unswitching"); STATISTIC(NumTrivial, "Number of unswitches that are trivial"); STATISTIC( NumCostMultiplierSkipped, "Number of unswitch candidates that had their cost multiplier skipped"); STATISTIC(NumInvariantConditionsInjected, "Number of invariant conditions injected and unswitched"); static cl::opt<bool> EnableNonTrivialUnswitch( "enable-nontrivial-unswitch", cl::init(false), cl::Hidden, cl::desc("Forcibly enables non-trivial loop unswitching rather than " "following the configuration passed into the pass.")); static cl::opt<int> UnswitchThreshold("unswitch-threshold", cl::init(50), cl::Hidden, cl::desc("The cost threshold for unswitching a loop.")); static cl::opt<bool> EnableUnswitchCostMultiplier( "enable-unswitch-cost-multiplier", cl::init(true), cl::Hidden, cl::desc("Enable unswitch cost multiplier that prohibits exponential " "explosion in nontrivial unswitch.")); static cl::opt<int> UnswitchSiblingsToplevelDiv( "unswitch-siblings-toplevel-div", cl::init(2), cl::Hidden, cl::desc("Toplevel siblings divisor for cost multiplier.")); static cl::opt<int> UnswitchNumInitialUnscaledCandidates( "unswitch-num-initial-unscaled-candidates", cl::init(8), cl::Hidden, cl::desc("Number of unswitch candidates that are ignored when calculating " "cost multiplier.")); static cl::opt<bool> UnswitchGuards( "simple-loop-unswitch-guards", cl::init(true), cl::Hidden, cl::desc("If enabled, simple loop unswitching will also consider " "llvm.experimental.guard intrinsics as unswitch candidates.")); static cl::opt<bool> DropNonTrivialImplicitNullChecks( "simple-loop-unswitch-drop-non-trivial-implicit-null-checks", cl::init(false), cl::Hidden, cl::desc("If enabled, drop make.implicit metadata in unswitched implicit " "null checks to save time analyzing if we can keep it.")); static cl::opt<unsigned> MSSAThreshold("simple-loop-unswitch-memoryssa-threshold", cl::desc("Max number of memory uses to explore during " "partial unswitching analysis"), cl::init(100), cl::Hidden); static cl::opt<bool> FreezeLoopUnswitchCond( "freeze-loop-unswitch-cond", cl::init(true), cl::Hidden, cl::desc("If enabled, the freeze instruction will be added to condition " "of loop unswitch to prevent miscompilation.")); static cl::opt<bool> InjectInvariantConditions( "simple-loop-unswitch-inject-invariant-conditions", cl::Hidden, cl::desc("Whether we should inject new invariants and unswitch them to " "eliminate some existing (non-invariant) conditions."), cl::init(true)); static cl::opt<unsigned> InjectInvariantConditionHotnesThreshold( "simple-loop-unswitch-inject-invariant-condition-hotness-threshold", cl::Hidden, cl::desc("Only try to inject loop invariant conditions and " "unswitch on them to eliminate branches that are " "not-taken 1/<this option> times or less."), cl::init(16)); AnalysisKey ShouldRunExtraSimpleLoopUnswitch::Key; namespace { struct CompareDesc { … }; struct InjectedInvariant { … }; struct NonTrivialUnswitchCandidate { … }; } // end anonymous namespace. // Helper to skip (select x, true, false), which matches both a logical AND and // OR and can confuse code that tries to determine if \p Cond is either a // logical AND or OR but not both. static Value *skipTrivialSelect(Value *Cond) { … } /// Collect all of the loop invariant input values transitively used by the /// homogeneous instruction graph from a given root. /// /// This essentially walks from a root recursively through loop variant operands /// which have perform the same logical operation (AND or OR) and finds all /// inputs which are loop invariant. For some operations these can be /// re-associated and unswitched out of the loop entirely. static TinyPtrVector<Value *> collectHomogenousInstGraphLoopInvariants(const Loop &L, Instruction &Root, const LoopInfo &LI) { … } static void replaceLoopInvariantUses(const Loop &L, Value *Invariant, Constant &Replacement) { … } /// Check that all the LCSSA PHI nodes in the loop exit block have trivial /// incoming values along this edge. static bool areLoopExitPHIsLoopInvariant(const Loop &L, const BasicBlock &ExitingBB, const BasicBlock &ExitBB) { … } /// Copy a set of loop invariant values \p ToDuplicate and insert them at the /// end of \p BB and conditionally branch on the copied condition. We only /// branch on a single value. static void buildPartialUnswitchConditionalBranch( BasicBlock &BB, ArrayRef<Value *> Invariants, bool Direction, BasicBlock &UnswitchedSucc, BasicBlock &NormalSucc, bool InsertFreeze, const Instruction *I, AssumptionCache *AC, const DominatorTree &DT) { … } /// Copy a set of loop invariant values, and conditionally branch on them. static void buildPartialInvariantUnswitchConditionalBranch( BasicBlock &BB, ArrayRef<Value *> ToDuplicate, bool Direction, BasicBlock &UnswitchedSucc, BasicBlock &NormalSucc, Loop &L, MemorySSAUpdater *MSSAU) { … } /// Rewrite the PHI nodes in an unswitched loop exit basic block. /// /// Requires that the loop exit and unswitched basic block are the same, and /// that the exiting block was a unique predecessor of that block. Rewrites the /// PHI nodes in that block such that what were LCSSA PHI nodes become trivial /// PHI nodes from the old preheader that now contains the unswitched /// terminator. static void rewritePHINodesForUnswitchedExitBlock(BasicBlock &UnswitchedBB, BasicBlock &OldExitingBB, BasicBlock &OldPH) { … } /// Rewrite the PHI nodes in the loop exit basic block and the split off /// unswitched block. /// /// Because the exit block remains an exit from the loop, this rewrites the /// LCSSA PHI nodes in it to remove the unswitched edge and introduces PHI /// nodes into the unswitched basic block to select between the value in the /// old preheader and the loop exit. static void rewritePHINodesForExitAndUnswitchedBlocks(BasicBlock &ExitBB, BasicBlock &UnswitchedBB, BasicBlock &OldExitingBB, BasicBlock &OldPH, bool FullUnswitch) { … } /// Hoist the current loop up to the innermost loop containing a remaining exit. /// /// Because we've removed an exit from the loop, we may have changed the set of /// loops reachable and need to move the current loop up the loop nest or even /// to an entirely separate nest. static void hoistLoopToNewParent(Loop &L, BasicBlock &Preheader, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU, ScalarEvolution *SE) { … } // Return the top-most loop containing ExitBB and having ExitBB as exiting block // or the loop containing ExitBB, if there is no parent loop containing ExitBB // as exiting block. static Loop *getTopMostExitingLoop(const BasicBlock *ExitBB, const LoopInfo &LI) { … } /// Unswitch a trivial branch if the condition is loop invariant. /// /// This routine should only be called when loop code leading to the branch has /// been validated as trivial (no side effects). This routine checks if the /// condition is invariant and one of the successors is a loop exit. This /// allows us to unswitch without duplicating the loop, making it trivial. /// /// If this routine fails to unswitch the branch it returns false. /// /// If the branch can be unswitched, this routine splits the preheader and /// hoists the branch above that split. Preserves loop simplified form /// (splitting the exit block as necessary). It simplifies the branch within /// the loop to an unconditional branch but doesn't remove it entirely. Further /// cleanup can be done with some simplifycfg like pass. /// /// If `SE` is not null, it will be updated based on the potential loop SCEVs /// invalidated by this. static bool unswitchTrivialBranch(Loop &L, BranchInst &BI, DominatorTree &DT, LoopInfo &LI, ScalarEvolution *SE, MemorySSAUpdater *MSSAU) { … } /// Unswitch a trivial switch if the condition is loop invariant. /// /// This routine should only be called when loop code leading to the switch has /// been validated as trivial (no side effects). This routine checks if the /// condition is invariant and that at least one of the successors is a loop /// exit. This allows us to unswitch without duplicating the loop, making it /// trivial. /// /// If this routine fails to unswitch the switch it returns false. /// /// If the switch can be unswitched, this routine splits the preheader and /// copies the switch above that split. If the default case is one of the /// exiting cases, it copies the non-exiting cases and points them at the new /// preheader. If the default case is not exiting, it copies the exiting cases /// and points the default at the preheader. It preserves loop simplified form /// (splitting the exit blocks as necessary). It simplifies the switch within /// the loop by removing now-dead cases. If the default case is one of those /// unswitched, it replaces its destination with a new basic block containing /// only unreachable. Such basic blocks, while technically loop exits, are not /// considered for unswitching so this is a stable transform and the same /// switch will not be revisited. If after unswitching there is only a single /// in-loop successor, the switch is further simplified to an unconditional /// branch. Still more cleanup can be done with some simplifycfg like pass. /// /// If `SE` is not null, it will be updated based on the potential loop SCEVs /// invalidated by this. static bool unswitchTrivialSwitch(Loop &L, SwitchInst &SI, DominatorTree &DT, LoopInfo &LI, ScalarEvolution *SE, MemorySSAUpdater *MSSAU) { … } /// This routine scans the loop to find a branch or switch which occurs before /// any side effects occur. These can potentially be unswitched without /// duplicating the loop. If a branch or switch is successfully unswitched the /// scanning continues to see if subsequent branches or switches have become /// trivial. Once all trivial candidates have been unswitched, this routine /// returns. /// /// The return value indicates whether anything was unswitched (and therefore /// changed). /// /// If `SE` is not null, it will be updated based on the potential loop SCEVs /// invalidated by this. static bool unswitchAllTrivialConditions(Loop &L, DominatorTree &DT, LoopInfo &LI, ScalarEvolution *SE, MemorySSAUpdater *MSSAU) { … } /// Build the cloned blocks for an unswitched copy of the given loop. /// /// The cloned blocks are inserted before the loop preheader (`LoopPH`) and /// after the split block (`SplitBB`) that will be used to select between the /// cloned and original loop. /// /// This routine handles cloning all of the necessary loop blocks and exit /// blocks including rewriting their instructions and the relevant PHI nodes. /// Any loop blocks or exit blocks which are dominated by a different successor /// than the one for this clone of the loop blocks can be trivially skipped. We /// use the `DominatingSucc` map to determine whether a block satisfies that /// property with a simple map lookup. /// /// It also correctly creates the unconditional branch in the cloned /// unswitched parent block to only point at the unswitched successor. /// /// This does not handle most of the necessary updates to `LoopInfo`. Only exit /// block splitting is correctly reflected in `LoopInfo`, essentially all of /// the cloned blocks (and their loops) are left without full `LoopInfo` /// updates. This also doesn't fully update `DominatorTree`. It adds the cloned /// blocks to them but doesn't create the cloned `DominatorTree` structure and /// instead the caller must recompute an accurate DT. It *does* correctly /// update the `AssumptionCache` provided in `AC`. static BasicBlock *buildClonedLoopBlocks( Loop &L, BasicBlock *LoopPH, BasicBlock *SplitBB, ArrayRef<BasicBlock *> ExitBlocks, BasicBlock *ParentBB, BasicBlock *UnswitchedSuccBB, BasicBlock *ContinueSuccBB, const SmallDenseMap<BasicBlock *, BasicBlock *, 16> &DominatingSucc, ValueToValueMapTy &VMap, SmallVectorImpl<DominatorTree::UpdateType> &DTUpdates, AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU, ScalarEvolution *SE) { … } /// Recursively clone the specified loop and all of its children. /// /// The target parent loop for the clone should be provided, or can be null if /// the clone is a top-level loop. While cloning, all the blocks are mapped /// with the provided value map. The entire original loop must be present in /// the value map. The cloned loop is returned. static Loop *cloneLoopNest(Loop &OrigRootL, Loop *RootParentL, const ValueToValueMapTy &VMap, LoopInfo &LI) { … } /// Build the cloned loops of an original loop from unswitching. /// /// Because unswitching simplifies the CFG of the loop, this isn't a trivial /// operation. We need to re-verify that there even is a loop (as the backedge /// may not have been cloned), and even if there are remaining backedges the /// backedge set may be different. However, we know that each child loop is /// undisturbed, we only need to find where to place each child loop within /// either any parent loop or within a cloned version of the original loop. /// /// Because child loops may end up cloned outside of any cloned version of the /// original loop, multiple cloned sibling loops may be created. All of them /// are returned so that the newly introduced loop nest roots can be /// identified. static void buildClonedLoops(Loop &OrigL, ArrayRef<BasicBlock *> ExitBlocks, const ValueToValueMapTy &VMap, LoopInfo &LI, SmallVectorImpl<Loop *> &NonChildClonedLoops) { … } static void deleteDeadClonedBlocks(Loop &L, ArrayRef<BasicBlock *> ExitBlocks, ArrayRef<std::unique_ptr<ValueToValueMapTy>> VMaps, DominatorTree &DT, MemorySSAUpdater *MSSAU) { … } static void deleteDeadBlocksFromLoop(Loop &L, SmallVectorImpl<BasicBlock *> &ExitBlocks, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU, ScalarEvolution *SE, LPMUpdater &LoopUpdater) { … } /// Recompute the set of blocks in a loop after unswitching. /// /// This walks from the original headers predecessors to rebuild the loop. We /// take advantage of the fact that new blocks can't have been added, and so we /// filter by the original loop's blocks. This also handles potentially /// unreachable code that we don't want to explore but might be found examining /// the predecessors of the header. /// /// If the original loop is no longer a loop, this will return an empty set. If /// it remains a loop, all the blocks within it will be added to the set /// (including those blocks in inner loops). static SmallPtrSet<const BasicBlock *, 16> recomputeLoopBlockSet(Loop &L, LoopInfo &LI) { … } /// Rebuild a loop after unswitching removes some subset of blocks and edges. /// /// The removal may have removed some child loops entirely but cannot have /// disturbed any remaining child loops. However, they may need to be hoisted /// to the parent loop (or to be top-level loops). The original loop may be /// completely removed. /// /// The sibling loops resulting from this update are returned. If the original /// loop remains a valid loop, it will be the first entry in this list with all /// of the newly sibling loops following it. /// /// Returns true if the loop remains a loop after unswitching, and false if it /// is no longer a loop after unswitching (and should not continue to be /// referenced). static bool rebuildLoopAfterUnswitch(Loop &L, ArrayRef<BasicBlock *> ExitBlocks, LoopInfo &LI, SmallVectorImpl<Loop *> &HoistedLoops, ScalarEvolution *SE) { … } /// Helper to visit a dominator subtree, invoking a callable on each node. /// /// Returning false at any point will stop walking past that node of the tree. template <typename CallableT> void visitDomSubTree(DominatorTree &DT, BasicBlock *BB, CallableT Callable) { … } void postUnswitch(Loop &L, LPMUpdater &U, StringRef LoopName, bool CurrentLoopValid, bool PartiallyInvariant, bool InjectedCondition, ArrayRef<Loop *> NewLoops) { … } static void unswitchNontrivialInvariants( Loop &L, Instruction &TI, ArrayRef<Value *> Invariants, IVConditionInfo &PartialIVInfo, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, ScalarEvolution *SE, MemorySSAUpdater *MSSAU, LPMUpdater &LoopUpdater, bool InsertFreeze, bool InjectedCondition) { … } /// Recursively compute the cost of a dominator subtree based on the per-block /// cost map provided. /// /// The recursive computation is memozied into the provided DT-indexed cost map /// to allow querying it for most nodes in the domtree without it becoming /// quadratic. static InstructionCost computeDomSubtreeCost( DomTreeNode &N, const SmallDenseMap<BasicBlock *, InstructionCost, 4> &BBCostMap, SmallDenseMap<DomTreeNode *, InstructionCost, 4> &DTCostMap) { … } /// Turns a select instruction into implicit control flow branch, /// making the following replacement: /// /// head: /// --code before select-- /// select %cond, %trueval, %falseval /// --code after select-- /// /// into /// /// head: /// --code before select-- /// br i1 %cond, label %then, label %tail /// /// then: /// br %tail /// /// tail: /// phi [ %trueval, %then ], [ %falseval, %head] /// unreachable /// /// It also makes all relevant DT and LI updates, so that all structures are in /// valid state after this transform. static BranchInst *turnSelectIntoBranch(SelectInst *SI, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU, AssumptionCache *AC) { … } /// Turns a llvm.experimental.guard intrinsic into implicit control flow branch, /// making the following replacement: /// /// --code before guard-- /// call void (i1, ...) @llvm.experimental.guard(i1 %cond) [ "deopt"() ] /// --code after guard-- /// /// into /// /// --code before guard-- /// br i1 %cond, label %guarded, label %deopt /// /// guarded: /// --code after guard-- /// /// deopt: /// call void (i1, ...) @llvm.experimental.guard(i1 false) [ "deopt"() ] /// unreachable /// /// It also makes all relevant DT and LI updates, so that all structures are in /// valid state after this transform. static BranchInst *turnGuardIntoBranch(IntrinsicInst *GI, Loop &L, DominatorTree &DT, LoopInfo &LI, MemorySSAUpdater *MSSAU) { … } /// Cost multiplier is a way to limit potentially exponential behavior /// of loop-unswitch. Cost is multipied in proportion of 2^number of unswitch /// candidates available. Also accounting for the number of "sibling" loops with /// the idea to account for previous unswitches that already happened on this /// cluster of loops. There was an attempt to keep this formula simple, /// just enough to limit the worst case behavior. Even if it is not that simple /// now it is still not an attempt to provide a detailed heuristic size /// prediction. /// /// TODO: Make a proper accounting of "explosion" effect for all kinds of /// unswitch candidates, making adequate predictions instead of wild guesses. /// That requires knowing not just the number of "remaining" candidates but /// also costs of unswitching for each of these candidates. static int CalculateUnswitchCostMultiplier( const Instruction &TI, const Loop &L, const LoopInfo &LI, const DominatorTree &DT, ArrayRef<NonTrivialUnswitchCandidate> UnswitchCandidates) { … } static bool collectUnswitchCandidates( SmallVectorImpl<NonTrivialUnswitchCandidate> &UnswitchCandidates, IVConditionInfo &PartialIVInfo, Instruction *&PartialIVCondBranch, const Loop &L, const LoopInfo &LI, AAResults &AA, const MemorySSAUpdater *MSSAU) { … } /// Tries to canonicalize condition described by: /// /// br (LHS pred RHS), label IfTrue, label IfFalse /// /// into its equivalent where `Pred` is something that we support for injected /// invariants (so far it is limited to ult), LHS in canonicalized form is /// non-invariant and RHS is an invariant. static void canonicalizeForInvariantConditionInjection( ICmpInst::Predicate &Pred, Value *&LHS, Value *&RHS, BasicBlock *&IfTrue, BasicBlock *&IfFalse, const Loop &L) { … } /// Returns true, if predicate described by ( \p Pred, \p LHS, \p RHS ) /// succeeding into blocks ( \p IfTrue, \p IfFalse) can be optimized by /// injecting a loop-invariant condition. static bool shouldTryInjectInvariantCondition( const ICmpInst::Predicate Pred, const Value *LHS, const Value *RHS, const BasicBlock *IfTrue, const BasicBlock *IfFalse, const Loop &L) { … } /// Returns true, if metadata on \p BI allows us to optimize branching into \p /// TakenSucc via injection of invariant conditions. The branch should be not /// enough and not previously unswitched, the information about this comes from /// the metadata. bool shouldTryInjectBasingOnMetadata(const BranchInst *BI, const BasicBlock *TakenSucc) { … } /// Materialize pending invariant condition of the given candidate into IR. The /// injected loop-invariant condition implies the original loop-variant branch /// condition, so the materialization turns /// /// loop_block: /// ... /// br i1 %variant_cond, label InLoopSucc, label OutOfLoopSucc /// /// into /// /// preheader: /// %invariant_cond = LHS pred RHS /// ... /// loop_block: /// br i1 %invariant_cond, label InLoopSucc, label OriginalCheck /// OriginalCheck: /// br i1 %variant_cond, label InLoopSucc, label OutOfLoopSucc /// ... static NonTrivialUnswitchCandidate injectPendingInvariantConditions(NonTrivialUnswitchCandidate Candidate, Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, MemorySSAUpdater *MSSAU) { … } /// Given chain of loop branch conditions looking like: /// br (Variant < Invariant1) /// br (Variant < Invariant2) /// br (Variant < Invariant3) /// ... /// collect set of invariant conditions on which we want to unswitch, which /// look like: /// Invariant1 <= Invariant2 /// Invariant2 <= Invariant3 /// ... /// Though they might not immediately exist in the IR, we can still inject them. static bool insertCandidatesWithPendingInjections( SmallVectorImpl<NonTrivialUnswitchCandidate> &UnswitchCandidates, Loop &L, ICmpInst::Predicate Pred, ArrayRef<CompareDesc> Compares, const DominatorTree &DT) { … } /// Collect unswitch candidates by invariant conditions that are not immediately /// present in the loop. However, they can be injected into the code if we /// decide it's profitable. /// An example of such conditions is following: /// /// for (...) { /// x = load ... /// if (! x <u C1) break; /// if (! x <u C2) break; /// <do something> /// } /// /// We can unswitch by condition "C1 <=u C2". If that is true, then "x <u C1 <= /// C2" automatically implies "x <u C2", so we can get rid of one of /// loop-variant checks in unswitched loop version. static bool collectUnswitchCandidatesWithInjections( SmallVectorImpl<NonTrivialUnswitchCandidate> &UnswitchCandidates, IVConditionInfo &PartialIVInfo, Instruction *&PartialIVCondBranch, Loop &L, const DominatorTree &DT, const LoopInfo &LI, AAResults &AA, const MemorySSAUpdater *MSSAU) { … } static bool isSafeForNoNTrivialUnswitching(Loop &L, LoopInfo &LI) { … } static NonTrivialUnswitchCandidate findBestNonTrivialUnswitchCandidate( ArrayRef<NonTrivialUnswitchCandidate> UnswitchCandidates, const Loop &L, const DominatorTree &DT, const LoopInfo &LI, AssumptionCache &AC, const TargetTransformInfo &TTI, const IVConditionInfo &PartialIVInfo) { … } // Insert a freeze on an unswitched branch if all is true: // 1. freeze-loop-unswitch-cond option is true // 2. The branch may not execute in the loop pre-transformation. If a branch may // not execute and could cause UB, it would always cause UB if it is hoisted outside // of the loop. Insert a freeze to prevent this case. // 3. The branch condition may be poison or undef static bool shouldInsertFreeze(Loop &L, Instruction &TI, DominatorTree &DT, AssumptionCache &AC) { … } static bool unswitchBestCondition(Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, AAResults &AA, TargetTransformInfo &TTI, ScalarEvolution *SE, MemorySSAUpdater *MSSAU, LPMUpdater &LoopUpdater) { … } /// Unswitch control flow predicated on loop invariant conditions. /// /// This first hoists all branches or switches which are trivial (IE, do not /// require duplicating any part of the loop) out of the loop body. It then /// looks at other loop invariant control flows and tries to unswitch those as /// well by cloning the loop if the result is small enough. /// /// The `DT`, `LI`, `AC`, `AA`, `TTI` parameters are required analyses that are /// also updated based on the unswitch. The `MSSA` analysis is also updated if /// valid (i.e. its use is enabled). /// /// If either `NonTrivial` is true or the flag `EnableNonTrivialUnswitch` is /// true, we will attempt to do non-trivial unswitching as well as trivial /// unswitching. /// /// The `postUnswitch` function will be run after unswitching is complete /// with information on whether or not the provided loop remains a loop and /// a list of new sibling loops created. /// /// If `SE` is non-null, we will update that analysis based on the unswitching /// done. static bool unswitchLoop(Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, AAResults &AA, TargetTransformInfo &TTI, bool Trivial, bool NonTrivial, ScalarEvolution *SE, MemorySSAUpdater *MSSAU, ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI, LPMUpdater &LoopUpdater) { … } PreservedAnalyses SimpleLoopUnswitchPass::run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U) { … } void SimpleLoopUnswitchPass::printPipeline( raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) { … }
Codebase Browser
llvm