X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FTransforms%2FScalar%2FLoopUnswitch.cpp;h=e21d41ac0a37b0cc825d6108a0b7f646a647cd0f;hp=977c53a3bc6327046fb53d31c9eaf8bddfef26b9;hb=cd52a7a381a73c53ec4ef517ad87f19808cb1a28;hpb=facdfc67815a9e8a67170568dd2dd1439006cd27 diff --git a/lib/Transforms/Scalar/LoopUnswitch.cpp b/lib/Transforms/Scalar/LoopUnswitch.cpp index 977c53a3bc6..e21d41ac0a3 100644 --- a/lib/Transforms/Scalar/LoopUnswitch.cpp +++ b/lib/Transforms/Scalar/LoopUnswitch.cpp @@ -30,6 +30,7 @@ #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/CodeMetrics.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/LoopInfo.h" @@ -41,6 +42,8 @@ #include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" #include "llvm/IR/Instructions.h" +#include "llvm/IR/Module.h" +#include "llvm/IR/MDBuilder.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" @@ -103,7 +106,8 @@ namespace { // Analyze loop. Check its size, calculate is it possible to unswitch // it. Returns true if we can unswitch this loop. - bool countLoop(const Loop *L, const TargetTransformInfo &TTI); + bool countLoop(const Loop *L, const TargetTransformInfo &TTI, + AssumptionCache *AC); // Clean all data related to given loop. void forgetLoop(const Loop *L); @@ -126,6 +130,7 @@ namespace { class LoopUnswitch : public LoopPass { LoopInfo *LI; // Loop information LPPassManager *LPM; + AssumptionCache *AC; // LoopProcessWorklist - Used to check if second loop needs processing // after RewriteLoopBodyWithConditionConstant rewrites first loop. @@ -164,15 +169,16 @@ namespace { /// loop preheaders be inserted into the CFG. /// void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired(); AU.addRequiredID(LoopSimplifyID); AU.addPreservedID(LoopSimplifyID); - AU.addRequired(); - AU.addPreserved(); + AU.addRequired(); + AU.addPreserved(); AU.addRequiredID(LCSSAID); AU.addPreservedID(LCSSAID); AU.addPreserved(); AU.addPreserved(); - AU.addRequired(); + AU.addRequired(); } private: @@ -190,10 +196,12 @@ namespace { /// Update the appropriate Phi nodes as we do so. void SplitExitEdges(Loop *L, const SmallVectorImpl &ExitBlocks); - bool UnswitchIfProfitable(Value *LoopCond, Constant *Val); + bool UnswitchIfProfitable(Value *LoopCond, Constant *Val, + TerminatorInst *TI = nullptr); void UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val, - BasicBlock *ExitBlock); - void UnswitchNontrivialCondition(Value *LIC, Constant *OnVal, Loop *L); + BasicBlock *ExitBlock, TerminatorInst *TI); + void UnswitchNontrivialCondition(Value *LIC, Constant *OnVal, Loop *L, + TerminatorInst *TI); void RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, Constant *Val, bool isEqual); @@ -201,7 +209,8 @@ namespace { void EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val, BasicBlock *TrueDest, BasicBlock *FalseDest, - Instruction *InsertPt); + Instruction *InsertPt, + TerminatorInst *TI); void SimplifyCode(std::vector &Worklist, Loop *L); bool IsTrivialUnswitchCondition(Value *Cond, Constant **Val = nullptr, @@ -212,7 +221,8 @@ namespace { // Analyze loop. Check its size, calculate is it possible to unswitch // it. Returns true if we can unswitch this loop. -bool LUAnalysisCache::countLoop(const Loop *L, const TargetTransformInfo &TTI) { +bool LUAnalysisCache::countLoop(const Loop *L, const TargetTransformInfo &TTI, + AssumptionCache *AC) { LoopPropsMapIt PropsIt; bool Inserted; @@ -229,13 +239,16 @@ bool LUAnalysisCache::countLoop(const Loop *L, const TargetTransformInfo &TTI) { // large numbers of branches which cause loop unswitching to go crazy. // This is a very ad-hoc heuristic. + SmallPtrSet EphValues; + CodeMetrics::collectEphemeralValues(L, AC, EphValues); + // FIXME: This is overly conservative because it does not take into // consideration code simplification opportunities and code that can // be shared by the resultant unswitched loops. CodeMetrics Metrics; for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); I != E; ++I) - Metrics.analyzeBasicBlock(*I, TTI); + Metrics.analyzeBasicBlock(*I, TTI, EphValues); Props.SizeEstimation = std::min(Metrics.NumInsts, Metrics.NumBlocks * 5); Props.CanBeUnswitchedCount = MaxSize / (Props.SizeEstimation); @@ -325,9 +338,10 @@ void LUAnalysisCache::cloneData(const Loop *NewLoop, const Loop *OldLoop, char LoopUnswitch::ID = 0; INITIALIZE_PASS_BEGIN(LoopUnswitch, "loop-unswitch", "Unswitch loops", false, false) -INITIALIZE_AG_DEPENDENCY(TargetTransformInfo) +INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) INITIALIZE_PASS_DEPENDENCY(LoopSimplify) -INITIALIZE_PASS_DEPENDENCY(LoopInfo) +INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(LCSSA) INITIALIZE_PASS_END(LoopUnswitch, "loop-unswitch", "Unswitch loops", false, false) @@ -376,7 +390,9 @@ bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) { if (skipOptnoneFunction(L)) return false; - LI = &getAnalysis(); + AC = &getAnalysis().getAssumptionCache( + *L->getHeader()->getParent()); + LI = &getAnalysis().getLoopInfo(); LPM = &LPM_Ref; DominatorTreeWrapperPass *DTWP = getAnalysisIfAvailable(); @@ -421,7 +437,10 @@ bool LoopUnswitch::processCurrentLoop() { // Probably we reach the quota of branches for this loop. If so // stop unswitching. - if (!BranchesInfo.countLoop(currentLoop, getAnalysis())) + if (!BranchesInfo.countLoop( + currentLoop, getAnalysis().getTTI( + *currentLoop->getHeader()->getParent()), + AC)) return false; // Loop over all of the basic blocks in the loop. If we find an interior @@ -438,8 +457,8 @@ bool LoopUnswitch::processCurrentLoop() { // unswitch on it if we desire. Value *LoopCond = FindLIVLoopCondition(BI->getCondition(), currentLoop, Changed); - if (LoopCond && UnswitchIfProfitable(LoopCond, - ConstantInt::getTrue(Context))) { + if (LoopCond && + UnswitchIfProfitable(LoopCond, ConstantInt::getTrue(Context), TI)) { ++NumBranches; return true; } @@ -628,7 +647,8 @@ bool LoopUnswitch::IsTrivialUnswitchCondition(Value *Cond, Constant **Val, /// UnswitchIfProfitable - 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, + TerminatorInst *TI) { Function *F = loopHeader->getParent(); Constant *CondVal = nullptr; BasicBlock *ExitBlock = nullptr; @@ -636,19 +656,17 @@ bool LoopUnswitch::UnswitchIfProfitable(Value *LoopCond, Constant *Val) { if (IsTrivialUnswitchCondition(LoopCond, &CondVal, &ExitBlock)) { // If the condition is trivial, always unswitch. There is no code growth // for this case. - UnswitchTrivialCondition(currentLoop, LoopCond, CondVal, ExitBlock); + UnswitchTrivialCondition(currentLoop, LoopCond, CondVal, ExitBlock, TI); return true; } // Check to see if it would be profitable to unswitch current loop. // Do not do non-trivial unswitch while optimizing for size. - if (OptimizeForSize || - F->getAttributes().hasAttribute(AttributeSet::FunctionIndex, - Attribute::OptimizeForSize)) + if (OptimizeForSize || F->hasFnAttribute(Attribute::OptimizeForSize)) return false; - UnswitchNontrivialCondition(LoopCond, Val, currentLoop); + UnswitchNontrivialCondition(LoopCond, Val, currentLoop, TI); return true; } @@ -663,7 +681,7 @@ static Loop *CloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); I != E; ++I) if (LI->getLoopFor(*I) == L) - New->addBasicBlockToLoop(cast(VM[*I]), LI->getBase()); + New->addBasicBlockToLoop(cast(VM[*I]), *LI); // Add all of the subloops to the new loop. for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) @@ -672,30 +690,71 @@ static Loop *CloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, return New; } +static void copyMetadata(Instruction *DstInst, const Instruction *SrcInst, + bool Swapped) { + if (!SrcInst || !SrcInst->hasMetadata()) + return; + + SmallVector, 4> MDs; + SrcInst->getAllMetadata(MDs); + for (auto &MD : MDs) { + switch (MD.first) { + default: + break; + case LLVMContext::MD_prof: + if (Swapped && MD.second->getNumOperands() == 3 && + isa(MD.second->getOperand(0))) { + MDString *MDName = cast(MD.second->getOperand(0)); + if (MDName->getString() == "branch_weights") { + auto *ValT = cast_or_null( + MD.second->getOperand(1))->getValue(); + auto *ValF = cast_or_null( + MD.second->getOperand(2))->getValue(); + assert(ValT && ValF && "Invalid Operands of branch_weights"); + auto NewMD = + MDBuilder(DstInst->getParent()->getContext()) + .createBranchWeights(cast(ValF)->getZExtValue(), + cast(ValT)->getZExtValue()); + MD.second = NewMD; + } + } + // fallthrough. + case LLVMContext::MD_dbg: + DstInst->setMetadata(MD.first, MD.second); + } + } +} + /// EmitPreheaderBranchOnCondition - Emit a conditional branch on two values /// if LIC == Val, branch to TrueDst, otherwise branch to FalseDest. Insert the /// code immediately before InsertPt. void LoopUnswitch::EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val, BasicBlock *TrueDest, BasicBlock *FalseDest, - Instruction *InsertPt) { + Instruction *InsertPt, + TerminatorInst *TI) { // Insert a conditional branch on LIC to the two preheaders. The original // code is the true version and the new code is the false version. Value *BranchVal = LIC; + bool Swapped = false; if (!isa(Val) || Val->getType() != Type::getInt1Ty(LIC->getContext())) BranchVal = new ICmpInst(InsertPt, ICmpInst::ICMP_EQ, LIC, Val); - else if (Val != ConstantInt::getTrue(Val->getContext())) + else if (Val != ConstantInt::getTrue(Val->getContext())) { // We want to enter the new loop when the condition is true. std::swap(TrueDest, FalseDest); + Swapped = true; + } // Insert the new branch. BranchInst *BI = BranchInst::Create(TrueDest, FalseDest, BranchVal, InsertPt); + copyMetadata(BI, TI, Swapped); // If either edge is critical, split it. This helps preserve LoopSimplify // form for enclosing loops. - SplitCriticalEdge(BI, 0, this, false, false, true); - SplitCriticalEdge(BI, 1, this, false, false, true); + auto Options = CriticalEdgeSplittingOptions(DT, LI).setPreserveLCSSA(); + SplitCriticalEdge(BI, 0, Options); + SplitCriticalEdge(BI, 1, Options); } /// UnswitchTrivialCondition - Given a loop that has a trivial unswitchable @@ -703,18 +762,19 @@ void LoopUnswitch::EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val, /// where the path through the loop 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, - BasicBlock *ExitBlock) { +void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val, + BasicBlock *ExitBlock, + TerminatorInst *TI) { DEBUG(dbgs() << "loop-unswitch: Trivial-Unswitch loop %" - << loopHeader->getName() << " [" << L->getBlocks().size() - << " blocks] in Function " << L->getHeader()->getParent()->getName() - << " on cond: " << *Val << " == " << *Cond << "\n"); + << loopHeader->getName() << " [" << L->getBlocks().size() + << " blocks] in Function " + << L->getHeader()->getParent()->getName() << " on cond: " << *Val + << " == " << *Cond << "\n"); // 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 // conditional branch on Cond. - BasicBlock *NewPH = SplitEdge(loopPreheader, loopHeader, this); + BasicBlock *NewPH = SplitEdge(loopPreheader, loopHeader, DT, LI); // 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 @@ -725,12 +785,12 @@ void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond, // without actually branching to it (the exit block should be dominated by the // loop header, not the preheader). assert(!L->contains(ExitBlock) && "Exit block is in the loop?"); - BasicBlock *NewExit = SplitBlock(ExitBlock, ExitBlock->begin(), this); + BasicBlock *NewExit = SplitBlock(ExitBlock, ExitBlock->begin(), DT, LI); // Okay, now we have a position to branch from and a position to branch to, // insert the new conditional branch. EmitPreheaderBranchOnCondition(Cond, Val, NewExit, NewPH, - loopPreheader->getTerminator()); + loopPreheader->getTerminator(), TI); LPM->deleteSimpleAnalysisValue(loopPreheader->getTerminator(), L); loopPreheader->getTerminator()->eraseFromParent(); @@ -756,13 +816,9 @@ void LoopUnswitch::SplitExitEdges(Loop *L, // Although SplitBlockPredecessors doesn't preserve loop-simplify in // general, if we call it on all predecessors of all exits then it does. - if (!ExitBlock->isLandingPad()) { - SplitBlockPredecessors(ExitBlock, Preds, ".us-lcssa", this); - } else { - SmallVector NewBBs; - SplitLandingPadPredecessors(ExitBlock, Preds, ".us-lcssa", ".us-lcssa", - this, NewBBs); - } + SplitBlockPredecessors(ExitBlock, Preds, ".us-lcssa", + /*AliasAnalysis*/ nullptr, DT, LI, + /*PreserveLCSSA*/ true); } } @@ -770,7 +826,7 @@ void LoopUnswitch::SplitExitEdges(Loop *L, /// 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, - Loop *L) { + Loop *L, TerminatorInst *TI) { Function *F = loopHeader->getParent(); DEBUG(dbgs() << "loop-unswitch: Unswitching loop %" << loopHeader->getName() << " [" << L->getBlocks().size() @@ -785,7 +841,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, this); + BasicBlock *NewPreheader = SplitEdge(loopPreheader, loopHeader, DT, LI); LoopBlocks.push_back(NewPreheader); // We want the loop to come after the preheader, but before the exit blocks. @@ -823,6 +879,10 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, F->getBasicBlockList().splice(NewPreheader, F->getBasicBlockList(), NewBlocks[0], F->end()); + // FIXME: We could register any cloned assumptions instead of clearing the + // whole function's cache. + AC->clear(); + // Now we create the new Loop object for the versioned loop. Loop *NewLoop = CloneLoop(L, L->getParentLoop(), VMap, LI, LPM); @@ -834,14 +894,14 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, if (ParentLoop) { // Make sure to add the cloned preheader and exit blocks to the parent loop // as well. - ParentLoop->addBasicBlockToLoop(NewBlocks[0], LI->getBase()); + ParentLoop->addBasicBlockToLoop(NewBlocks[0], *LI); } for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { BasicBlock *NewExit = cast(VMap[ExitBlocks[i]]); // The new exit block should be in the same loop as the old one. if (Loop *ExitBBLoop = LI->getLoopFor(ExitBlocks[i])) - ExitBBLoop->addBasicBlockToLoop(NewExit, LI->getBase()); + ExitBBLoop->addBasicBlockToLoop(NewExit, *LI); assert(NewExit->getTerminator()->getNumSuccessors() == 1 && "Exit block should have been split to have one successor!"); @@ -883,7 +943,8 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, "Preheader splitting did not work correctly!"); // 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); OldBR->eraseFromParent(); @@ -1027,7 +1088,7 @@ void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, // and hooked up so as to preserve the loop structure, because // trying to update it is complicated. So instead we preserve the // loop structure and put the block on a dead code path. - SplitEdge(Switch, SISucc, this); + SplitEdge(Switch, SISucc, DT, LI); // Compute the successors instead of relying on the return value // of SplitEdge, since it may have split the switch successor // after PHI nodes. @@ -1069,6 +1130,7 @@ void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, /// pass. /// void LoopUnswitch::SimplifyCode(std::vector &Worklist, Loop *L) { + const DataLayout &DL = L->getHeader()->getModule()->getDataLayout(); while (!Worklist.empty()) { Instruction *I = Worklist.back(); Worklist.pop_back(); @@ -1091,7 +1153,7 @@ void LoopUnswitch::SimplifyCode(std::vector &Worklist, Loop *L) { // See if instruction simplification can hack this up. This is common for // things like "select false, X, Y" after unswitching made the condition be // 'false'. TODO: update the domtree properly so we can pass it here. - if (Value *V = SimplifyInstruction(I)) + if (Value *V = SimplifyInstruction(I, DL)) if (LI->replacementPreservesLCSSAForm(I, V)) { ReplaceUsesOfWith(I, V, Worklist, L, LPM); continue;