diff options
Diffstat (limited to 'llvm/lib/Transforms/Scalar/LoopUnswitch.cpp')
| -rw-r--r-- | llvm/lib/Transforms/Scalar/LoopUnswitch.cpp | 328 |
1 files changed, 149 insertions, 179 deletions
diff --git a/llvm/lib/Transforms/Scalar/LoopUnswitch.cpp b/llvm/lib/Transforms/Scalar/LoopUnswitch.cpp index 915e053704b23..645a89bbd0ff0 100644 --- a/llvm/lib/Transforms/Scalar/LoopUnswitch.cpp +++ b/llvm/lib/Transforms/Scalar/LoopUnswitch.cpp @@ -38,11 +38,11 @@ #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/MemorySSA.h" #include "llvm/Analysis/MemorySSAUpdater.h" +#include "llvm/Analysis/MustExecute.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/IR/Attributes.h" #include "llvm/IR/BasicBlock.h" -#include "llvm/IR/CallSite.h" #include "llvm/IR/Constant.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DerivedTypes.h" @@ -158,7 +158,7 @@ namespace { // Returns true if another unswitching could be done within the cost // threshold. - bool CostAllowsUnswitching(); + bool costAllowsUnswitching(); // Clone all loop-unswitch related loop properties. // Redistribute unswitching quotas. @@ -173,20 +173,20 @@ namespace { AssumptionCache *AC; // Used to check if second loop needs processing after - // RewriteLoopBodyWithConditionConstant rewrites first loop. + // rewriteLoopBodyWithConditionConstant rewrites first loop. std::vector<Loop*> LoopProcessWorklist; LUAnalysisCache BranchesInfo; bool OptimizeForSize; - bool redoLoop = false; + bool RedoLoop = false; - Loop *currentLoop = nullptr; + Loop *CurrentLoop = nullptr; DominatorTree *DT = nullptr; MemorySSA *MSSA = nullptr; std::unique_ptr<MemorySSAUpdater> MSSAU; - BasicBlock *loopHeader = nullptr; - BasicBlock *loopPreheader = nullptr; + BasicBlock *LoopHeader = nullptr; + BasicBlock *LoopPreheader = nullptr; bool SanitizeMemory; SimpleLoopSafetyInfo SafetyInfo; @@ -198,15 +198,15 @@ namespace { // NewBlocks contained cloned copy of basic blocks from LoopBlocks. std::vector<BasicBlock*> NewBlocks; - bool hasBranchDivergence; + bool HasBranchDivergence; public: static char ID; // Pass ID, replacement for typeid - explicit LoopUnswitch(bool Os = false, bool hasBranchDivergence = false) + explicit LoopUnswitch(bool Os = false, bool HasBranchDivergence = false) : LoopPass(ID), OptimizeForSize(Os), - hasBranchDivergence(hasBranchDivergence) { - initializeLoopUnswitchPass(*PassRegistry::getPassRegistry()); + HasBranchDivergence(HasBranchDivergence) { + initializeLoopUnswitchPass(*PassRegistry::getPassRegistry()); } bool runOnLoop(Loop *L, LPPassManager &LPM) override; @@ -223,48 +223,46 @@ namespace { AU.addRequired<MemorySSAWrapperPass>(); AU.addPreserved<MemorySSAWrapperPass>(); } - if (hasBranchDivergence) + if (HasBranchDivergence) AU.addRequired<LegacyDivergenceAnalysis>(); getLoopAnalysisUsage(AU); } private: - void releaseMemory() override { - BranchesInfo.forgetLoop(currentLoop); - } + void releaseMemory() override { BranchesInfo.forgetLoop(CurrentLoop); } void initLoopData() { - loopHeader = currentLoop->getHeader(); - loopPreheader = currentLoop->getLoopPreheader(); + LoopHeader = CurrentLoop->getHeader(); + LoopPreheader = CurrentLoop->getLoopPreheader(); } /// Split all of the edges from inside the loop to their exit blocks. /// Update the appropriate Phi nodes as we do so. - void SplitExitEdges(Loop *L, + void splitExitEdges(Loop *L, const SmallVectorImpl<BasicBlock *> &ExitBlocks); - bool TryTrivialLoopUnswitch(bool &Changed); + bool tryTrivialLoopUnswitch(bool &Changed); - bool UnswitchIfProfitable(Value *LoopCond, Constant *Val, + bool unswitchIfProfitable(Value *LoopCond, Constant *Val, Instruction *TI = nullptr); - void UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val, + void unswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val, BasicBlock *ExitBlock, Instruction *TI); - void UnswitchNontrivialCondition(Value *LIC, Constant *OnVal, Loop *L, + void unswitchNontrivialCondition(Value *LIC, Constant *OnVal, Loop *L, Instruction *TI); - void RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, - Constant *Val, bool isEqual); + void rewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, + Constant *Val, bool IsEqual); - void EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val, + void emitPreheaderBranchOnCondition(Value *LIC, Constant *Val, BasicBlock *TrueDest, BasicBlock *FalseDest, BranchInst *OldBranch, Instruction *TI); - void SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L); + void simplifyCode(std::vector<Instruction *> &Worklist, Loop *L); /// Given that the Invariant is not equal to Val. Simplify instructions /// in the loop. - Value *SimplifyInstructionWithNotEqual(Instruction *Inst, Value *Invariant, + Value *simplifyInstructionWithNotEqual(Instruction *Inst, Value *Invariant, Constant *Val); }; @@ -347,7 +345,7 @@ bool LUAnalysisCache::isUnswitched(const SwitchInst *SI, const Value *V) { return (*CurLoopInstructions)[SI].count(V); } -bool LUAnalysisCache::CostAllowsUnswitching() { +bool LUAnalysisCache::costAllowsUnswitching() { return CurrentLoopProperties->CanBeUnswitchedCount > 0; } @@ -396,8 +394,8 @@ INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass) INITIALIZE_PASS_END(LoopUnswitch, "loop-unswitch", "Unswitch loops", false, false) -Pass *llvm::createLoopUnswitchPass(bool Os, bool hasBranchDivergence) { - return new LoopUnswitch(Os, hasBranchDivergence); +Pass *llvm::createLoopUnswitchPass(bool Os, bool HasBranchDivergence) { + return new LoopUnswitch(Os, HasBranchDivergence); } /// Operator chain lattice. @@ -411,15 +409,15 @@ enum OperatorChain { /// Cond is a condition that occurs in L. If it is invariant in the loop, or has /// an invariant piece, return the invariant. Otherwise, return null. // -/// NOTE: FindLIVLoopCondition will not return a partial LIV by walking up a -/// mixed operator chain, as we can not reliably find a value which will simplify -/// the operator chain. If the chain is AND-only or OR-only, we can use 0 or ~0 -/// to simplify the chain. +/// NOTE: findLIVLoopCondition will not return a partial LIV by walking up a +/// mixed operator chain, as we can not reliably find a value which will +/// simplify the operator chain. If the chain is AND-only or OR-only, we can use +/// 0 or ~0 to simplify the chain. /// /// NOTE: In case a partial LIV and a mixed operator chain, we may be able to /// simplify the condition itself to a loop variant condition, but at the /// cost of creating an entirely new loop. -static Value *FindLIVLoopCondition(Value *Cond, Loop *L, bool &Changed, +static Value *findLIVLoopCondition(Value *Cond, Loop *L, bool &Changed, OperatorChain &ParentChain, DenseMap<Value *, Value *> &Cache, MemorySSAUpdater *MSSAU) { @@ -479,7 +477,7 @@ static Value *FindLIVLoopCondition(Value *Cond, Loop *L, bool &Changed, // If either the left or right side is invariant, we can unswitch on this, // which will cause the branch to go away in one loop and the condition to // simplify in the other one. - if (Value *LHS = FindLIVLoopCondition(BO->getOperand(0), L, Changed, + if (Value *LHS = findLIVLoopCondition(BO->getOperand(0), L, Changed, ParentChain, Cache, MSSAU)) { Cache[Cond] = LHS; return LHS; @@ -487,7 +485,7 @@ static Value *FindLIVLoopCondition(Value *Cond, Loop *L, bool &Changed, // We did not manage to find a partial LIV in operand(0). Backtrack and try // operand(1). ParentChain = NewChain; - if (Value *RHS = FindLIVLoopCondition(BO->getOperand(1), L, Changed, + if (Value *RHS = findLIVLoopCondition(BO->getOperand(1), L, Changed, ParentChain, Cache, MSSAU)) { Cache[Cond] = RHS; return RHS; @@ -503,11 +501,11 @@ static Value *FindLIVLoopCondition(Value *Cond, Loop *L, bool &Changed, /// an invariant piece, return the invariant along with the operator chain type. /// Otherwise, return null. static std::pair<Value *, OperatorChain> -FindLIVLoopCondition(Value *Cond, Loop *L, bool &Changed, +findLIVLoopCondition(Value *Cond, Loop *L, bool &Changed, MemorySSAUpdater *MSSAU) { DenseMap<Value *, Value *> Cache; OperatorChain OpChain = OC_OpChainNone; - Value *FCond = FindLIVLoopCondition(Cond, L, Changed, OpChain, Cache, MSSAU); + Value *FCond = findLIVLoopCondition(Cond, L, Changed, OpChain, Cache, MSSAU); // In case we do find a LIV, it can not be obtained by walking up a mixed // operator chain. @@ -516,22 +514,22 @@ FindLIVLoopCondition(Value *Cond, Loop *L, bool &Changed, return {FCond, OpChain}; } -bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) { +bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPMRef) { if (skipLoop(L)) return false; AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache( *L->getHeader()->getParent()); LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); - LPM = &LPM_Ref; + LPM = &LPMRef; DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); if (EnableMSSALoopDependency) { MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA(); MSSAU = std::make_unique<MemorySSAUpdater>(MSSA); assert(DT && "Cannot update MemorySSA without a valid DomTree."); } - currentLoop = L; - Function *F = currentLoop->getHeader()->getParent(); + CurrentLoop = L; + Function *F = CurrentLoop->getHeader()->getParent(); SanitizeMemory = F->hasFnAttribute(Attribute::SanitizeMemory); if (SanitizeMemory) @@ -542,12 +540,12 @@ bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) { bool Changed = false; do { - assert(currentLoop->isLCSSAForm(*DT)); + assert(CurrentLoop->isLCSSAForm(*DT)); if (MSSA && VerifyMemorySSA) MSSA->verifyMemorySSA(); - redoLoop = false; + RedoLoop = false; Changed |= processCurrentLoop(); - } while(redoLoop); + } while (RedoLoop); if (MSSA && VerifyMemorySSA) MSSA->verifyMemorySSA(); @@ -560,7 +558,7 @@ bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) { bool LoopUnswitch::isUnreachableDueToPreviousUnswitching(BasicBlock *BB) { auto *Node = DT->getNode(BB)->getIDom(); BasicBlock *DomBB = Node->getBlock(); - while (currentLoop->contains(DomBB)) { + while (CurrentLoop->contains(DomBB)) { BranchInst *BInst = dyn_cast<BranchInst>(DomBB->getTerminator()); Node = DT->getNode(DomBB)->getIDom(); @@ -591,7 +589,7 @@ bool LoopUnswitch::isUnreachableDueToPreviousUnswitching(BasicBlock *BB) { /// causing problems. Detail could be found in PR31652. Note if the /// func returns true, it is unsafe. But if it is false, it doesn't mean /// it is necessarily safe. -static bool EqualityPropUnSafe(Value &LoopCond) { +static bool equalityPropUnSafe(Value &LoopCond) { ICmpInst *CI = dyn_cast<ICmpInst>(&LoopCond); if (!CI || !CI->isEquality()) return false; @@ -601,7 +599,7 @@ static bool EqualityPropUnSafe(Value &LoopCond) { if (isa<UndefValue>(LHS) || isa<UndefValue>(RHS)) return true; - auto hasUndefInPHI = [](PHINode &PN) { + auto HasUndefInPHI = [](PHINode &PN) { for (Value *Opd : PN.incoming_values()) { if (isa<UndefValue>(Opd)) return true; @@ -610,10 +608,10 @@ static bool EqualityPropUnSafe(Value &LoopCond) { }; PHINode *LPHI = dyn_cast<PHINode>(LHS); PHINode *RPHI = dyn_cast<PHINode>(RHS); - if ((LPHI && hasUndefInPHI(*LPHI)) || (RPHI && hasUndefInPHI(*RPHI))) + if ((LPHI && HasUndefInPHI(*LPHI)) || (RPHI && HasUndefInPHI(*RPHI))) return true; - auto hasUndefInSelect = [](SelectInst &SI) { + auto HasUndefInSelect = [](SelectInst &SI) { if (isa<UndefValue>(SI.getTrueValue()) || isa<UndefValue>(SI.getFalseValue())) return true; @@ -621,7 +619,7 @@ static bool EqualityPropUnSafe(Value &LoopCond) { }; SelectInst *LSI = dyn_cast<SelectInst>(LHS); SelectInst *RSI = dyn_cast<SelectInst>(RHS); - if ((LSI && hasUndefInSelect(*LSI)) || (RSI && hasUndefInSelect(*RSI))) + if ((LSI && HasUndefInSelect(*LSI)) || (RSI && HasUndefInSelect(*RSI))) return true; return false; } @@ -633,35 +631,36 @@ bool LoopUnswitch::processCurrentLoop() { initLoopData(); // If LoopSimplify was unable to form a preheader, don't do any unswitching. - if (!loopPreheader) + if (!LoopPreheader) return false; // Loops with indirectbr cannot be cloned. - if (!currentLoop->isSafeToClone()) + if (!CurrentLoop->isSafeToClone()) return false; // Without dedicated exits, splitting the exit edge may fail. - if (!currentLoop->hasDedicatedExits()) + if (!CurrentLoop->hasDedicatedExits()) return false; - LLVMContext &Context = loopHeader->getContext(); + LLVMContext &Context = LoopHeader->getContext(); // Analyze loop cost, and stop unswitching if loop content can not be duplicated. if (!BranchesInfo.countLoop( - currentLoop, getAnalysis<TargetTransformInfoWrapperPass>().getTTI( - *currentLoop->getHeader()->getParent()), + CurrentLoop, + getAnalysis<TargetTransformInfoWrapperPass>().getTTI( + *CurrentLoop->getHeader()->getParent()), AC)) return false; // Try trivial unswitch first before loop over other basic blocks in the loop. - if (TryTrivialLoopUnswitch(Changed)) { + if (tryTrivialLoopUnswitch(Changed)) { return true; } // Do not do non-trivial unswitch while optimizing for size. // FIXME: Use Function::hasOptSize(). if (OptimizeForSize || - loopHeader->getParent()->hasFnAttribute(Attribute::OptimizeForSize)) + LoopHeader->getParent()->hasFnAttribute(Attribute::OptimizeForSize)) return false; // Run through the instructions in the loop, keeping track of three things: @@ -680,11 +679,12 @@ bool LoopUnswitch::processCurrentLoop() { SmallVector<IntrinsicInst *, 4> Guards; - for (const auto BB : currentLoop->blocks()) { + for (const auto BB : CurrentLoop->blocks()) { for (auto &I : *BB) { - auto CS = CallSite(&I); - if (!CS) continue; - if (CS.isConvergent()) + auto *CB = dyn_cast<CallBase>(&I); + if (!CB) + continue; + if (CB->isConvergent()) return false; if (auto *II = dyn_cast<InvokeInst>(&I)) if (!II->getUnwindDest()->canSplitPredecessors()) @@ -696,11 +696,11 @@ bool LoopUnswitch::processCurrentLoop() { } for (IntrinsicInst *Guard : Guards) { - Value *LoopCond = FindLIVLoopCondition(Guard->getOperand(0), currentLoop, + Value *LoopCond = findLIVLoopCondition(Guard->getOperand(0), CurrentLoop, Changed, MSSAU.get()) .first; if (LoopCond && - UnswitchIfProfitable(LoopCond, ConstantInt::getTrue(Context))) { + unswitchIfProfitable(LoopCond, ConstantInt::getTrue(Context))) { // NB! Unswitching (if successful) could have erased some of the // instructions in Guards leaving dangling pointers there. This is fine // because we're returning now, and won't look at Guards again. @@ -712,8 +712,9 @@ bool LoopUnswitch::processCurrentLoop() { // Loop over all of the basic blocks in the loop. If we find an interior // block that is branching on a loop-invariant condition, we can unswitch this // loop. - for (Loop::block_iterator I = currentLoop->block_begin(), - E = currentLoop->block_end(); I != E; ++I) { + for (Loop::block_iterator I = CurrentLoop->block_begin(), + E = CurrentLoop->block_end(); + I != E; ++I) { Instruction *TI = (*I)->getTerminator(); // Unswitching on a potentially uninitialized predicate is not @@ -723,7 +724,7 @@ bool LoopUnswitch::processCurrentLoop() { // This is a workaround for the discrepancy between LLVM IR and MSan // semantics. See PR28054 for more details. if (SanitizeMemory && - !SafetyInfo.isGuaranteedToExecute(*TI, DT, currentLoop)) + !SafetyInfo.isGuaranteedToExecute(*TI, DT, CurrentLoop)) continue; if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { @@ -738,11 +739,11 @@ bool LoopUnswitch::processCurrentLoop() { if (BI->isConditional()) { // See if this, or some part of it, is loop invariant. If so, we can // unswitch on it if we desire. - Value *LoopCond = FindLIVLoopCondition(BI->getCondition(), currentLoop, + Value *LoopCond = findLIVLoopCondition(BI->getCondition(), CurrentLoop, Changed, MSSAU.get()) .first; - if (LoopCond && !EqualityPropUnSafe(*LoopCond) && - UnswitchIfProfitable(LoopCond, ConstantInt::getTrue(Context), TI)) { + if (LoopCond && !equalityPropUnSafe(*LoopCond) && + unswitchIfProfitable(LoopCond, ConstantInt::getTrue(Context), TI)) { ++NumBranches; return true; } @@ -752,7 +753,7 @@ bool LoopUnswitch::processCurrentLoop() { Value *LoopCond; OperatorChain OpChain; std::tie(LoopCond, OpChain) = - FindLIVLoopCondition(SC, currentLoop, Changed, MSSAU.get()); + findLIVLoopCondition(SC, CurrentLoop, Changed, MSSAU.get()); unsigned NumCases = SI->getNumCases(); if (LoopCond && NumCases) { @@ -796,7 +797,7 @@ bool LoopUnswitch::processCurrentLoop() { if (!UnswitchVal) continue; - if (UnswitchIfProfitable(LoopCond, UnswitchVal)) { + if (unswitchIfProfitable(LoopCond, UnswitchVal)) { ++NumSwitches; // In case of a full LIV, UnswitchVal is the value we unswitched out. // In case of a partial LIV, we only unswitch when its an AND-chain @@ -812,11 +813,11 @@ bool LoopUnswitch::processCurrentLoop() { for (BasicBlock::iterator BBI = (*I)->begin(), E = (*I)->end(); BBI != E; ++BBI) if (SelectInst *SI = dyn_cast<SelectInst>(BBI)) { - Value *LoopCond = FindLIVLoopCondition(SI->getCondition(), currentLoop, + Value *LoopCond = findLIVLoopCondition(SI->getCondition(), CurrentLoop, Changed, MSSAU.get()) .first; - if (LoopCond && UnswitchIfProfitable(LoopCond, - ConstantInt::getTrue(Context))) { + if (LoopCond && + unswitchIfProfitable(LoopCond, ConstantInt::getTrue(Context))) { ++NumSelects; return true; } @@ -875,62 +876,38 @@ static BasicBlock *isTrivialLoopExitBlock(Loop *L, BasicBlock *BB) { return nullptr; } -/// We have found that we can unswitch currentLoop when LoopCond == Val to +/// We have found that we can unswitch CurrentLoop when LoopCond == Val to /// simplify the loop. If we decide that this is profitable, /// unswitch the loop, reprocess the pieces, then return true. -bool LoopUnswitch::UnswitchIfProfitable(Value *LoopCond, Constant *Val, +bool LoopUnswitch::unswitchIfProfitable(Value *LoopCond, Constant *Val, Instruction *TI) { // Check to see if it would be profitable to unswitch current loop. - if (!BranchesInfo.CostAllowsUnswitching()) { + if (!BranchesInfo.costAllowsUnswitching()) { LLVM_DEBUG(dbgs() << "NOT unswitching loop %" - << currentLoop->getHeader()->getName() + << CurrentLoop->getHeader()->getName() << " at non-trivial condition '" << *Val << "' == " << *LoopCond << "\n" << ". Cost too high.\n"); return false; } - if (hasBranchDivergence && + if (HasBranchDivergence && getAnalysis<LegacyDivergenceAnalysis>().isDivergent(LoopCond)) { LLVM_DEBUG(dbgs() << "NOT unswitching loop %" - << currentLoop->getHeader()->getName() + << CurrentLoop->getHeader()->getName() << " at non-trivial condition '" << *Val << "' == " << *LoopCond << "\n" << ". Condition is divergent.\n"); return false; } - UnswitchNontrivialCondition(LoopCond, Val, currentLoop, TI); + unswitchNontrivialCondition(LoopCond, Val, CurrentLoop, TI); return true; } -/// Recursively clone the specified loop and all of its children, -/// mapping the blocks with the specified map. -static Loop *CloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, - LoopInfo *LI, LPPassManager *LPM) { - Loop &New = *LI->AllocateLoop(); - if (PL) - PL->addChildLoop(&New); - else - LI->addTopLevelLoop(&New); - LPM->addLoop(New); - - // Add all of the blocks in L to the new loop. - for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); - I != E; ++I) - if (LI->getLoopFor(*I) == L) - New.addBasicBlockToLoop(cast<BasicBlock>(VM[*I]), *LI); - - // Add all of the subloops to the new loop. - for (Loop *I : *L) - CloneLoop(I, &New, VM, LI, LPM); - - return &New; -} - /// Emit a conditional branch on two values if LIC == Val, branch to TrueDst, /// otherwise branch to FalseDest. Insert the code immediately before OldBranch /// and remove (but not erase!) it from the function. -void LoopUnswitch::EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val, +void LoopUnswitch::emitPreheaderBranchOnCondition(Value *LIC, Constant *Val, BasicBlock *TrueDest, BasicBlock *FalseDest, BranchInst *OldBranch, @@ -997,11 +974,11 @@ void LoopUnswitch::EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val, /// that doesn't execute its body has no side-effects), unswitch it. This /// doesn't involve any code duplication, just moving the conditional branch /// outside of the loop and updating loop info. -void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val, +void LoopUnswitch::unswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val, BasicBlock *ExitBlock, Instruction *TI) { LLVM_DEBUG(dbgs() << "loop-unswitch: Trivial-Unswitch loop %" - << loopHeader->getName() << " [" << L->getBlocks().size() + << LoopHeader->getName() << " [" << L->getBlocks().size() << " blocks] in Function " << L->getHeader()->getParent()->getName() << " on cond: " << *Val << " == " << *Cond << "\n"); @@ -1011,9 +988,9 @@ void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val, SEWP->getSE().forgetTopmostLoop(L); // First step, split the preheader, so that we know that there is a safe place - // to insert the conditional branch. We will change loopPreheader to have a + // to insert the conditional branch. We will change LoopPreheader to have a // conditional branch on Cond. - BasicBlock *NewPH = SplitEdge(loopPreheader, loopHeader, DT, LI, MSSAU.get()); + BasicBlock *NewPH = SplitEdge(LoopPreheader, LoopHeader, DT, LI, MSSAU.get()); // Now that we have a place to insert the conditional branch, create a place // to branch to: this is the exit block out of the loop that we should @@ -1029,22 +1006,21 @@ void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val, // Okay, now we have a position to branch from and a position to branch to, // insert the new conditional branch. - auto *OldBranch = dyn_cast<BranchInst>(loopPreheader->getTerminator()); + auto *OldBranch = dyn_cast<BranchInst>(LoopPreheader->getTerminator()); assert(OldBranch && "Failed to split the preheader"); - EmitPreheaderBranchOnCondition(Cond, Val, NewExit, NewPH, OldBranch, TI); - LPM->deleteSimpleAnalysisValue(OldBranch, L); + emitPreheaderBranchOnCondition(Cond, Val, NewExit, NewPH, OldBranch, TI); - // EmitPreheaderBranchOnCondition removed the OldBranch from the function. + // emitPreheaderBranchOnCondition removed the OldBranch from the function. // Delete it, as it is no longer needed. delete OldBranch; // We need to reprocess this loop, it could be unswitched again. - redoLoop = true; + RedoLoop = true; // Now that we know that the loop is never entered when this condition is a // particular value, rewrite the loop with this info. We know that this will // at least eliminate the old branch. - RewriteLoopBodyWithConditionConstant(L, Cond, Val, false); + rewriteLoopBodyWithConditionConstant(L, Cond, Val, /*IsEqual=*/false); ++NumTrivial; } @@ -1055,8 +1031,8 @@ void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val, /// produces no code duplications (equivalently, it produces a simpler loop and /// a new empty loop, which gets deleted). Therefore always unswitch trivial /// condition. -bool LoopUnswitch::TryTrivialLoopUnswitch(bool &Changed) { - BasicBlock *CurrentBB = currentLoop->getHeader(); +bool LoopUnswitch::tryTrivialLoopUnswitch(bool &Changed) { + BasicBlock *CurrentBB = CurrentLoop->getHeader(); Instruction *CurrentTerm = CurrentBB->getTerminator(); LLVMContext &Context = CurrentBB->getContext(); @@ -1081,7 +1057,7 @@ bool LoopUnswitch::TryTrivialLoopUnswitch(bool &Changed) { // we can not reach any trivial condition candidates (unfoldable // branch instructions or switch instructions) and no unswitch // can happen. Exit and return false. - if (!currentLoop->contains(CurrentBB) || !Visited.insert(CurrentBB).second) + if (!CurrentLoop->contains(CurrentBB) || !Visited.insert(CurrentBB).second) return false; // Check if this loop will execute any side-effecting instructions (e.g. @@ -1128,7 +1104,7 @@ bool LoopUnswitch::TryTrivialLoopUnswitch(bool &Changed) { if (!BI->isConditional()) return false; - Value *LoopCond = FindLIVLoopCondition(BI->getCondition(), currentLoop, + Value *LoopCond = findLIVLoopCondition(BI->getCondition(), CurrentLoop, Changed, MSSAU.get()) .first; @@ -1141,11 +1117,11 @@ bool LoopUnswitch::TryTrivialLoopUnswitch(bool &Changed) { // exit through a unique exit block without having any // side-effects. If so, determine the value of Cond that causes // it to do this. - if ((LoopExitBB = isTrivialLoopExitBlock(currentLoop, - BI->getSuccessor(0)))) { + if ((LoopExitBB = + isTrivialLoopExitBlock(CurrentLoop, BI->getSuccessor(0)))) { CondVal = ConstantInt::getTrue(Context); - } else if ((LoopExitBB = isTrivialLoopExitBlock(currentLoop, - BI->getSuccessor(1)))) { + } else if ((LoopExitBB = + isTrivialLoopExitBlock(CurrentLoop, BI->getSuccessor(1)))) { CondVal = ConstantInt::getFalse(Context); } @@ -1154,16 +1130,16 @@ bool LoopUnswitch::TryTrivialLoopUnswitch(bool &Changed) { if (!LoopExitBB || isa<PHINode>(LoopExitBB->begin())) return false; // Can't handle this. - if (EqualityPropUnSafe(*LoopCond)) + if (equalityPropUnSafe(*LoopCond)) return false; - UnswitchTrivialCondition(currentLoop, LoopCond, CondVal, LoopExitBB, + unswitchTrivialCondition(CurrentLoop, LoopCond, CondVal, LoopExitBB, CurrentTerm); ++NumBranches; return true; } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurrentTerm)) { // If this isn't switching on an invariant condition, we can't unswitch it. - Value *LoopCond = FindLIVLoopCondition(SI->getCondition(), currentLoop, + Value *LoopCond = findLIVLoopCondition(SI->getCondition(), CurrentLoop, Changed, MSSAU.get()) .first; @@ -1181,7 +1157,7 @@ bool LoopUnswitch::TryTrivialLoopUnswitch(bool &Changed) { for (auto Case : SI->cases()) { BasicBlock *LoopExitCandidate; if ((LoopExitCandidate = - isTrivialLoopExitBlock(currentLoop, Case.getCaseSuccessor()))) { + isTrivialLoopExitBlock(CurrentLoop, Case.getCaseSuccessor()))) { // Okay, we found a trivial case, remember the value that is trivial. ConstantInt *CaseVal = Case.getCaseValue(); @@ -1200,7 +1176,7 @@ bool LoopUnswitch::TryTrivialLoopUnswitch(bool &Changed) { if (!LoopExitBB || isa<PHINode>(LoopExitBB->begin())) return false; // Can't handle this. - UnswitchTrivialCondition(currentLoop, LoopCond, CondVal, LoopExitBB, + unswitchTrivialCondition(CurrentLoop, LoopCond, CondVal, LoopExitBB, nullptr); // We are only unswitching full LIV. @@ -1213,11 +1189,11 @@ bool LoopUnswitch::TryTrivialLoopUnswitch(bool &Changed) { /// Split all of the edges from inside the loop to their exit blocks. /// Update the appropriate Phi nodes as we do so. -void LoopUnswitch::SplitExitEdges(Loop *L, - const SmallVectorImpl<BasicBlock *> &ExitBlocks){ +void LoopUnswitch::splitExitEdges( + Loop *L, const SmallVectorImpl<BasicBlock *> &ExitBlocks) { - for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { - BasicBlock *ExitBlock = ExitBlocks[i]; + for (unsigned I = 0, E = ExitBlocks.size(); I != E; ++I) { + BasicBlock *ExitBlock = ExitBlocks[I]; SmallVector<BasicBlock *, 4> Preds(pred_begin(ExitBlock), pred_end(ExitBlock)); @@ -1231,11 +1207,11 @@ void LoopUnswitch::SplitExitEdges(Loop *L, /// We determined that the loop is profitable to unswitch when LIC equal Val. /// Split it into loop versions and test the condition outside of either loop. /// Return the loops created as Out1/Out2. -void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, +void LoopUnswitch::unswitchNontrivialCondition(Value *LIC, Constant *Val, Loop *L, Instruction *TI) { - Function *F = loopHeader->getParent(); + Function *F = LoopHeader->getParent(); LLVM_DEBUG(dbgs() << "loop-unswitch: Unswitching loop %" - << loopHeader->getName() << " [" << L->getBlocks().size() + << LoopHeader->getName() << " [" << L->getBlocks().size() << " blocks] in Function " << F->getName() << " when '" << *Val << "' == " << *LIC << "\n"); @@ -1253,7 +1229,7 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, // First step, split the preheader and exit blocks, and add these blocks to // the LoopBlocks list. BasicBlock *NewPreheader = - SplitEdge(loopPreheader, loopHeader, DT, LI, MSSAU.get()); + SplitEdge(LoopPreheader, LoopHeader, DT, LI, MSSAU.get()); LoopBlocks.push_back(NewPreheader); // We want the loop to come after the preheader, but before the exit blocks. @@ -1264,7 +1240,7 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, // Split all of the edges from inside the loop to their exit blocks. Update // the appropriate Phi nodes as we do so. - SplitExitEdges(L, ExitBlocks); + splitExitEdges(L, ExitBlocks); // The exit blocks may have been changed due to edge splitting, recompute. ExitBlocks.clear(); @@ -1278,12 +1254,11 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, // the instructions and blocks. NewBlocks.reserve(LoopBlocks.size()); ValueToValueMapTy VMap; - for (unsigned i = 0, e = LoopBlocks.size(); i != e; ++i) { - BasicBlock *NewBB = CloneBasicBlock(LoopBlocks[i], VMap, ".us", F); + for (unsigned I = 0, E = LoopBlocks.size(); I != E; ++I) { + BasicBlock *NewBB = CloneBasicBlock(LoopBlocks[I], VMap, ".us", F); NewBlocks.push_back(NewBB); - VMap[LoopBlocks[i]] = NewBB; // Keep the BB mapping. - LPM->cloneBasicBlockSimpleAnalysis(LoopBlocks[i], NewBB, L); + VMap[LoopBlocks[I]] = NewBB; // Keep the BB mapping. } // Splice the newly inserted blocks into the function right before the @@ -1293,7 +1268,7 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, NewBlocks[0]->getIterator(), F->end()); // Now we create the new Loop object for the versioned loop. - Loop *NewLoop = CloneLoop(L, L->getParentLoop(), VMap, LI, LPM); + Loop *NewLoop = cloneLoop(L, L->getParentLoop(), VMap, LI, LPM); // Recalculate unswitching quota, inherit simplified switches info for NewBB, // Probably clone more loop-unswitch related loop properties. @@ -1306,10 +1281,10 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, ParentLoop->addBasicBlockToLoop(NewBlocks[0], *LI); } - for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { - BasicBlock *NewExit = cast<BasicBlock>(VMap[ExitBlocks[i]]); + for (unsigned EBI = 0, EBE = ExitBlocks.size(); EBI != EBE; ++EBI) { + BasicBlock *NewExit = cast<BasicBlock>(VMap[ExitBlocks[EBI]]); // The new exit block should be in the same loop as the old one. - if (Loop *ExitBBLoop = LI->getLoopFor(ExitBlocks[i])) + if (Loop *ExitBBLoop = LI->getLoopFor(ExitBlocks[EBI])) ExitBBLoop->addBasicBlockToLoop(NewExit, *LI); assert(NewExit->getTerminator()->getNumSuccessors() == 1 && @@ -1319,7 +1294,7 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, // If the successor of the exit block had PHI nodes, add an entry for // NewExit. for (PHINode &PN : ExitSucc->phis()) { - Value *V = PN.getIncomingValueForBlock(ExitBlocks[i]); + Value *V = PN.getIncomingValueForBlock(ExitBlocks[EBI]); ValueToValueMapTy::iterator It = VMap.find(V); if (It != VMap.end()) V = It->second; PN.addIncoming(V, NewExit); @@ -1340,8 +1315,8 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, } // Rewrite the code to refer to itself. - for (unsigned i = 0, e = NewBlocks.size(); i != e; ++i) { - for (Instruction &I : *NewBlocks[i]) { + for (unsigned NBI = 0, NBE = NewBlocks.size(); NBI != NBE; ++NBI) { + for (Instruction &I : *NewBlocks[NBI]) { RemapInstruction(&I, VMap, RF_NoModuleLevelChanges | RF_IgnoreMissingLocals); if (auto *II = dyn_cast<IntrinsicInst>(&I)) @@ -1351,7 +1326,7 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, } // Rewrite the original preheader to select between versions of the loop. - BranchInst *OldBR = cast<BranchInst>(loopPreheader->getTerminator()); + BranchInst *OldBR = cast<BranchInst>(LoopPreheader->getTerminator()); assert(OldBR->isUnconditional() && OldBR->getSuccessor(0) == LoopBlocks[0] && "Preheader splitting did not work correctly!"); @@ -1364,9 +1339,8 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, } // Emit the new branch that selects between the two versions of this loop. - EmitPreheaderBranchOnCondition(LIC, Val, NewBlocks[0], LoopBlocks[0], OldBR, + emitPreheaderBranchOnCondition(LIC, Val, NewBlocks[0], LoopBlocks[0], OldBR, TI); - LPM->deleteSimpleAnalysisValue(OldBR, L); if (MSSAU) { // Update MemoryPhis in Exit blocks. MSSAU->updateExitBlocksForClonedLoop(ExitBlocks, VMap, *DT); @@ -1375,11 +1349,11 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, } // The OldBr was replaced by a new one and removed (but not erased) by - // EmitPreheaderBranchOnCondition. It is no longer needed, so delete it. + // emitPreheaderBranchOnCondition. It is no longer needed, so delete it. delete OldBR; LoopProcessWorklist.push_back(NewLoop); - redoLoop = true; + RedoLoop = true; // Keep a WeakTrackingVH holding onto LIC. If the first call to // RewriteLoopBody @@ -1390,22 +1364,23 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, // Now we rewrite the original code to know that the condition is true and the // new code to know that the condition is false. - RewriteLoopBodyWithConditionConstant(L, LIC, Val, false); + rewriteLoopBodyWithConditionConstant(L, LIC, Val, /*IsEqual=*/false); // It's possible that simplifying one loop could cause the other to be // changed to another value or a constant. If its a constant, don't simplify // it. if (!LoopProcessWorklist.empty() && LoopProcessWorklist.back() == NewLoop && LICHandle && !isa<Constant>(LICHandle)) - RewriteLoopBodyWithConditionConstant(NewLoop, LICHandle, Val, true); + rewriteLoopBodyWithConditionConstant(NewLoop, LICHandle, Val, + /*IsEqual=*/true); if (MSSA && VerifyMemorySSA) MSSA->verifyMemorySSA(); } /// Remove all instances of I from the worklist vector specified. -static void RemoveFromWorklist(Instruction *I, - std::vector<Instruction*> &Worklist) { +static void removeFromWorklist(Instruction *I, + std::vector<Instruction *> &Worklist) { Worklist.erase(std::remove(Worklist.begin(), Worklist.end(), I), Worklist.end()); @@ -1413,7 +1388,7 @@ static void RemoveFromWorklist(Instruction *I, /// When we find that I really equals V, remove I from the /// program, replacing all uses with V and update the worklist. -static void ReplaceUsesOfWith(Instruction *I, Value *V, +static void replaceUsesOfWith(Instruction *I, Value *V, std::vector<Instruction *> &Worklist, Loop *L, LPPassManager *LPM, MemorySSAUpdater *MSSAU) { LLVM_DEBUG(dbgs() << "Replace with '" << *V << "': " << *I << "\n"); @@ -1426,8 +1401,7 @@ static void ReplaceUsesOfWith(Instruction *I, Value *V, // Add users to the worklist which may be simplified now. for (User *U : I->users()) Worklist.push_back(cast<Instruction>(U)); - LPM->deleteSimpleAnalysisValue(I, L); - RemoveFromWorklist(I, Worklist); + removeFromWorklist(I, Worklist); I->replaceAllUsesWith(V); if (!I->mayHaveSideEffects()) { if (MSSAU) @@ -1440,7 +1414,7 @@ static void ReplaceUsesOfWith(Instruction *I, Value *V, /// We know either that the value LIC has the value specified by Val in the /// specified loop, or we know it does NOT have that value. /// Rewrite any uses of LIC or of properties correlated to it. -void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, +void LoopUnswitch::rewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, Constant *Val, bool IsEqual) { assert(!isa<Constant>(LIC) && "Why are we unswitching on a constant?"); @@ -1478,7 +1452,7 @@ void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, for (Instruction *UI : Worklist) UI->replaceUsesOfWith(LIC, Replacement); - SimplifyCode(Worklist, L); + simplifyCode(Worklist, L); return; } @@ -1492,7 +1466,7 @@ void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, // At this point, we know LIC is definitely not Val. Try to use some simple // logic to simplify the user w.r.t. to the context. - if (Value *Replacement = SimplifyInstructionWithNotEqual(UI, LIC, Val)) { + if (Value *Replacement = simplifyInstructionWithNotEqual(UI, LIC, Val)) { if (LI->replacementPreservesLCSSAForm(UI, Replacement)) { // This in-loop instruction has been simplified w.r.t. its context, // i.e. LIC != Val, make sure we propagate its replacement value to @@ -1506,7 +1480,7 @@ void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, } } - // This is a LIC user, push it into the worklist so that SimplifyCode can + // This is a LIC user, push it into the worklist so that simplifyCode can // attempt to simplify it. Worklist.push_back(UI); @@ -1568,7 +1542,7 @@ void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, DT->addNewBlock(Abort, NewSISucc); } - SimplifyCode(Worklist, L); + simplifyCode(Worklist, L); } /// Now that we have simplified some instructions in the loop, walk over it and @@ -1579,7 +1553,7 @@ void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, /// FIXME: When the loop optimizer is more mature, separate this out to a new /// pass. /// -void LoopUnswitch::SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L) { +void LoopUnswitch::simplifyCode(std::vector<Instruction *> &Worklist, Loop *L) { const DataLayout &DL = L->getHeader()->getModule()->getDataLayout(); while (!Worklist.empty()) { Instruction *I = Worklist.back(); @@ -1593,8 +1567,7 @@ void LoopUnswitch::SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L) { for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i))) Worklist.push_back(Use); - LPM->deleteSimpleAnalysisValue(I, L); - RemoveFromWorklist(I, Worklist); + removeFromWorklist(I, Worklist); if (MSSAU) MSSAU->removeMemoryAccess(I); I->eraseFromParent(); @@ -1607,7 +1580,7 @@ void LoopUnswitch::SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L) { // 'false'. TODO: update the domtree properly so we can pass it here. if (Value *V = SimplifyInstruction(I, DL)) if (LI->replacementPreservesLCSSAForm(I, V)) { - ReplaceUsesOfWith(I, V, Worklist, L, LPM, MSSAU.get()); + replaceUsesOfWith(I, V, Worklist, L, LPM, MSSAU.get()); continue; } @@ -1624,9 +1597,7 @@ void LoopUnswitch::SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L) { assert(SinglePred == Pred && "CFG broken"); // Make the LPM and Worklist updates specific to LoopUnswitch. - LPM->deleteSimpleAnalysisValue(BI, L); - RemoveFromWorklist(BI, Worklist); - LPM->deleteSimpleAnalysisValue(Succ, L); + removeFromWorklist(BI, Worklist); auto SuccIt = Succ->begin(); while (PHINode *PN = dyn_cast<PHINode>(SuccIt++)) { for (unsigned It = 0, E = PN->getNumOperands(); It != E; ++It) @@ -1634,8 +1605,7 @@ void LoopUnswitch::SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L) { Worklist.push_back(Use); for (User *U : PN->users()) Worklist.push_back(cast<Instruction>(U)); - LPM->deleteSimpleAnalysisValue(PN, L); - RemoveFromWorklist(PN, Worklist); + removeFromWorklist(PN, Worklist); ++NumSimplify; } // Merge the block and make the remaining analyses updates. @@ -1652,7 +1622,7 @@ void LoopUnswitch::SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L) { /// Simple simplifications we can do given the information that Cond is /// definitely not equal to Val. -Value *LoopUnswitch::SimplifyInstructionWithNotEqual(Instruction *Inst, +Value *LoopUnswitch::simplifyInstructionWithNotEqual(Instruction *Inst, Value *Invariant, Constant *Val) { // icmp eq cond, val -> false |