From b5797b659f879474b4081c4e1a00e955c38a4dcb Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Sun, 18 Jan 2015 09:21:15 +0000 Subject: [PATCH] [PM] Pull the analyses used for another utility routine into its API rather than relying on the pass object. This one is a bit annoying, but will pay off. First, supporting this one will make the next one much easier, and for utilities like LoopSimplify, this is moving them (slowly) closer to not having to pass the pass object around throughout their APIs. llvm-svn: 226396 --- .../llvm/Transforms/Utils/BasicBlockUtils.h | 8 +- llvm/lib/Transforms/Scalar/JumpThreading.cpp | 6 +- llvm/lib/Transforms/Scalar/LoopUnswitch.cpp | 4 +- llvm/lib/Transforms/Utils/BasicBlockUtils.cpp | 96 ++++++++++++---------- llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp | 15 ++-- llvm/lib/Transforms/Utils/LoopSimplify.cpp | 27 ++++-- llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp | 13 ++- 7 files changed, 104 insertions(+), 65 deletions(-) diff --git a/llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h b/llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h index eb0edb7..a9b6b39 100644 --- a/llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h +++ b/llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h @@ -168,8 +168,12 @@ BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt, /// complicated to handle the case where one of the edges being split /// is an exit of a loop with other exits). /// -BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef Preds, - const char *Suffix, Pass *P = nullptr); +BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef Preds, + const char *Suffix, + AliasAnalysis *AA = nullptr, + DominatorTree *DT = nullptr, + LoopInfo *LI = nullptr, + bool PreserveLCSSA = false); /// SplitLandingPadPredecessors - This method transforms the landing pad, /// OrigBB, by introducing two new basic blocks into the function. One of those diff --git a/llvm/lib/Transforms/Scalar/JumpThreading.cpp b/llvm/lib/Transforms/Scalar/JumpThreading.cpp index 273a997..c263ef4 100644 --- a/llvm/lib/Transforms/Scalar/JumpThreading.cpp +++ b/llvm/lib/Transforms/Scalar/JumpThreading.cpp @@ -993,7 +993,7 @@ bool JumpThreading::SimplifyPartiallyRedundantLoad(LoadInst *LI) { // Split them out to their own block. UnavailablePred = - SplitBlockPredecessors(LoadBB, PredsToSplit, "thread-pre-split", this); + SplitBlockPredecessors(LoadBB, PredsToSplit, "thread-pre-split"); } // If the value isn't available in all predecessors, then there will be @@ -1418,7 +1418,7 @@ bool JumpThreading::ThreadEdge(BasicBlock *BB, else { DEBUG(dbgs() << " Factoring out " << PredBBs.size() << " common predecessors.\n"); - PredBB = SplitBlockPredecessors(BB, PredBBs, ".thr_comm", this); + PredBB = SplitBlockPredecessors(BB, PredBBs, ".thr_comm"); } // And finally, do it! @@ -1561,7 +1561,7 @@ bool JumpThreading::DuplicateCondBranchOnPHIIntoPred(BasicBlock *BB, else { DEBUG(dbgs() << " Factoring out " << PredBBs.size() << " common predecessors.\n"); - PredBB = SplitBlockPredecessors(BB, PredBBs, ".thr_comm", this); + PredBB = SplitBlockPredecessors(BB, PredBBs, ".thr_comm"); } // Okay, we decided to do this! Clone all the instructions in BB onto the end diff --git a/llvm/lib/Transforms/Scalar/LoopUnswitch.cpp b/llvm/lib/Transforms/Scalar/LoopUnswitch.cpp index 0ff6e01..cf80244 100644 --- a/llvm/lib/Transforms/Scalar/LoopUnswitch.cpp +++ b/llvm/lib/Transforms/Scalar/LoopUnswitch.cpp @@ -769,7 +769,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); + SplitBlockPredecessors(ExitBlock, Preds, ".us-lcssa", + /*AliasAnalysis*/ nullptr, DT, LI, + /*PreserveLCSSA*/ true); } else { SmallVector NewBBs; SplitLandingPadPredecessors(ExitBlock, Preds, ".us-lcssa", ".us-lcssa", diff --git a/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp b/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp index 2fb5461..c680788 100644 --- a/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp +++ b/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp @@ -312,46 +312,46 @@ BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, /// analysis information. static void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB, ArrayRef Preds, - Pass *P, bool &HasLoopExit) { - if (!P) return; + DominatorTree *DT, LoopInfo *LI, + bool PreserveLCSSA, bool &HasLoopExit) { + // Update dominator tree if available. + if (DT) + DT->splitBlock(NewBB); - auto *LIWP = P->getAnalysisIfAvailable(); - LoopInfo *LI = LIWP ? &LIWP->getLoopInfo() : nullptr; - Loop *L = LI ? LI->getLoopFor(OldBB) : nullptr; + // The rest of the logic is only relevant for updating the loop structures. + if (!LI) + return; + + Loop *L = LI->getLoopFor(OldBB); // If we need to preserve loop analyses, collect some information about how // this split will affect loops. bool IsLoopEntry = !!L; bool SplitMakesNewLoopHeader = false; - if (LI) { - bool PreserveLCSSA = P->mustPreserveAnalysisID(LCSSAID); - for (ArrayRef::iterator - i = Preds.begin(), e = Preds.end(); i != e; ++i) { - BasicBlock *Pred = *i; - - // If we need to preserve LCSSA, determine if any of the preds is a loop - // exit. - if (PreserveLCSSA) - if (Loop *PL = LI->getLoopFor(Pred)) - if (!PL->contains(OldBB)) - HasLoopExit = true; - - // If we need to preserve LoopInfo, note whether any of the preds crosses - // an interesting loop boundary. - if (!L) continue; - if (L->contains(Pred)) - IsLoopEntry = false; - else - SplitMakesNewLoopHeader = true; - } + for (ArrayRef::iterator i = Preds.begin(), e = Preds.end(); + i != e; ++i) { + BasicBlock *Pred = *i; + + // If we need to preserve LCSSA, determine if any of the preds is a loop + // exit. + if (PreserveLCSSA) + if (Loop *PL = LI->getLoopFor(Pred)) + if (!PL->contains(OldBB)) + HasLoopExit = true; + + // If we need to preserve LoopInfo, note whether any of the preds crosses + // an interesting loop boundary. + if (!L) + continue; + if (L->contains(Pred)) + IsLoopEntry = false; + else + SplitMakesNewLoopHeader = true; } - // Update dominator tree if available. - if (DominatorTreeWrapperPass *DTWP = - P->getAnalysisIfAvailable()) - DTWP->getDomTree().splitBlock(NewBB); - - if (!L) return; + // Unless we have a loop for OldBB, nothing else to do here. + if (!L) + return; if (IsLoopEntry) { // Add the new block to the nearest enclosing loop (and not an adjacent @@ -388,10 +388,9 @@ static void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB, /// UpdatePHINodes - Update the PHI nodes in OrigBB to include the values coming /// from NewBB. This also updates AliasAnalysis, if available. static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB, - ArrayRef Preds, BranchInst *BI, - Pass *P, bool HasLoopExit) { + ArrayRef Preds, BranchInst *BI, + AliasAnalysis *AA, bool HasLoopExit) { // Otherwise, create a new PHI node in NewBB for each PHI node in OrigBB. - AliasAnalysis *AA = P ? P->getAnalysisIfAvailable() : nullptr; SmallPtrSet PredSet(Preds.begin(), Preds.end()); for (BasicBlock::iterator I = OrigBB->begin(); isa(I); ) { PHINode *PN = cast(I++); @@ -468,8 +467,10 @@ static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB, /// of the edges being split is an exit of a loop with other exits). /// BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, - ArrayRef Preds, - const char *Suffix, Pass *P) { + ArrayRef Preds, + const char *Suffix, AliasAnalysis *AA, + DominatorTree *DT, LoopInfo *LI, + bool PreserveLCSSA) { // Create new basic block, insert right before the original block. BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), BB->getName()+Suffix, BB->getParent(), BB); @@ -500,10 +501,11 @@ BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, // Update DominatorTree, LoopInfo, and LCCSA analysis information. bool HasLoopExit = false; - UpdateAnalysisInformation(BB, NewBB, Preds, P, HasLoopExit); + UpdateAnalysisInformation(BB, NewBB, Preds, DT, LI, PreserveLCSSA, + HasLoopExit); // Update the PHI nodes in BB with the values coming from NewBB. - UpdatePHINodes(BB, NewBB, Preds, BI, P, HasLoopExit); + UpdatePHINodes(BB, NewBB, Preds, BI, AA, HasLoopExit); return NewBB; } @@ -548,11 +550,18 @@ void llvm::SplitLandingPadPredecessors(BasicBlock *OrigBB, } // Update DominatorTree, LoopInfo, and LCCSA analysis information. + auto *DTWP = P->getAnalysisIfAvailable(); + auto *DT = DTWP ? &DTWP->getDomTree() : nullptr; + auto *LIWP = P->getAnalysisIfAvailable(); + auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr; + bool PreserveLCSSA = P->mustPreserveAnalysisID(LCSSAID); bool HasLoopExit = false; - UpdateAnalysisInformation(OrigBB, NewBB1, Preds, P, HasLoopExit); + UpdateAnalysisInformation(OrigBB, NewBB1, Preds, DT, LI, PreserveLCSSA, + HasLoopExit); // Update the PHI nodes in OrigBB with the values coming from NewBB1. - UpdatePHINodes(OrigBB, NewBB1, Preds, BI1, P, HasLoopExit); + AliasAnalysis *AA = P ? P->getAnalysisIfAvailable() : nullptr; + UpdatePHINodes(OrigBB, NewBB1, Preds, BI1, AA, HasLoopExit); // Move the remaining edges from OrigBB to point to NewBB2. SmallVector NewBB2Preds; @@ -584,10 +593,11 @@ void llvm::SplitLandingPadPredecessors(BasicBlock *OrigBB, // Update DominatorTree, LoopInfo, and LCCSA analysis information. HasLoopExit = false; - UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, P, HasLoopExit); + UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, DT, LI, + PreserveLCSSA, HasLoopExit); // Update the PHI nodes in OrigBB with the values coming from NewBB2. - UpdatePHINodes(OrigBB, NewBB2, NewBB2Preds, BI2, P, HasLoopExit); + UpdatePHINodes(OrigBB, NewBB2, NewBB2Preds, BI2, AA, HasLoopExit); } LandingPadInst *LPad = OrigBB->getLandingPadInst(); diff --git a/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp b/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp index 0e4c704..f8c7f6a 100644 --- a/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp +++ b/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp @@ -18,6 +18,7 @@ #include "llvm/Transforms/Scalar.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/CFG.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/IR/CFG.h" @@ -196,11 +197,14 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, // If we don't have a pass object, we can't update anything... if (!P) return NewBB; + + auto *AA = P->getAnalysisIfAvailable(); DominatorTreeWrapperPass *DTWP = P->getAnalysisIfAvailable(); DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr; auto *LIWP = P->getAnalysisIfAvailable(); LoopInfo *LI = LIWP ? &LIWP->getLoopInfo() : nullptr; + bool PreserveLCSSA = P->mustPreserveAnalysisID(LCSSAID); // If we have nothing to update, just return. if (!DT && !LI) @@ -295,7 +299,7 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, "Split point for loop exit is contained in loop!"); // Update LCSSA form in the newly created exit block. - if (P->mustPreserveAnalysisID(LCSSAID)) + if (PreserveLCSSA) createPHIsForSplitLoopExit(TIBB, NewBB, DestBB); // The only that we can break LoopSimplify form by splitting a critical @@ -323,9 +327,9 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, if (!LoopPreds.empty()) { assert(!DestBB->isLandingPad() && "We don't split edges to landing pads!"); - BasicBlock *NewExitBB = - SplitBlockPredecessors(DestBB, LoopPreds, "split", P); - if (P->mustPreserveAnalysisID(LCSSAID)) + BasicBlock *NewExitBB = SplitBlockPredecessors( + DestBB, LoopPreds, "split", AA, DT, LI, PreserveLCSSA); + if (PreserveLCSSA) createPHIsForSplitLoopExit(LoopPreds, NewExitBB, DestBB); } } @@ -333,8 +337,7 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, // available, which means that all predecessors of loop exit blocks // are within the loop. Without LoopSimplify form, it would be // necessary to insert a new phi. - assert((!P->mustPreserveAnalysisID(LCSSAID) || - P->mustPreserveAnalysisID(LoopSimplifyID)) && + assert((!PreserveLCSSA || P->mustPreserveAnalysisID(LoopSimplifyID)) && "SplitCriticalEdge doesn't know how to update LCCSA form " "without LoopSimplify!"); } diff --git a/llvm/lib/Transforms/Utils/LoopSimplify.cpp b/llvm/lib/Transforms/Utils/LoopSimplify.cpp index 4c7b5c6..926c3a7 100644 --- a/llvm/lib/Transforms/Utils/LoopSimplify.cpp +++ b/llvm/lib/Transforms/Utils/LoopSimplify.cpp @@ -113,6 +113,14 @@ static void placeSplitBlockCarefully(BasicBlock *NewBB, BasicBlock *llvm::InsertPreheaderForLoop(Loop *L, Pass *PP) { BasicBlock *Header = L->getHeader(); + // Get analyses that we try to update. + auto *AA = PP->getAnalysisIfAvailable(); + auto *DTWP = PP->getAnalysisIfAvailable(); + auto *DT = DTWP ? &DTWP->getDomTree() : nullptr; + auto *LIWP = PP->getAnalysisIfAvailable(); + auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr; + bool PreserveLCSSA = PP->mustPreserveAnalysisID(LCSSAID); + // Compute the set of predecessors of the loop that are not in the loop. SmallVector OutsideBlocks; for (pred_iterator PI = pred_begin(Header), PE = pred_end(Header); @@ -133,7 +141,7 @@ BasicBlock *llvm::InsertPreheaderForLoop(Loop *L, Pass *PP) { BasicBlock *PreheaderBB; if (!Header->isLandingPad()) { PreheaderBB = SplitBlockPredecessors(Header, OutsideBlocks, ".preheader", - PP); + AA, DT, LI, PreserveLCSSA); } else { SmallVector NewBBs; SplitLandingPadPredecessors(Header, OutsideBlocks, ".preheader", @@ -157,7 +165,9 @@ BasicBlock *llvm::InsertPreheaderForLoop(Loop *L, Pass *PP) { /// /// This method is used to split exit blocks that have predecessors outside of /// the loop. -static BasicBlock *rewriteLoopExitBlock(Loop *L, BasicBlock *Exit, Pass *PP) { +static BasicBlock *rewriteLoopExitBlock(Loop *L, BasicBlock *Exit, + AliasAnalysis *AA, DominatorTree *DT, + LoopInfo *LI, Pass *PP) { SmallVector LoopBlocks; for (pred_iterator I = pred_begin(Exit), E = pred_end(Exit); I != E; ++I) { BasicBlock *P = *I; @@ -172,6 +182,8 @@ static BasicBlock *rewriteLoopExitBlock(Loop *L, BasicBlock *Exit, Pass *PP) { assert(!LoopBlocks.empty() && "No edges coming in from outside the loop?"); BasicBlock *NewExitBB = nullptr; + bool PreserveLCSSA = PP->mustPreserveAnalysisID(LCSSAID); + if (Exit->isLandingPad()) { SmallVector NewBBs; SplitLandingPadPredecessors(Exit, LoopBlocks, @@ -179,7 +191,8 @@ static BasicBlock *rewriteLoopExitBlock(Loop *L, BasicBlock *Exit, Pass *PP) { PP, NewBBs); NewExitBB = NewBBs[0]; } else { - NewExitBB = SplitBlockPredecessors(Exit, LoopBlocks, ".loopexit", PP); + NewExitBB = SplitBlockPredecessors(Exit, LoopBlocks, ".loopexit", AA, DT, + LI, PreserveLCSSA); } DEBUG(dbgs() << "LoopSimplify: Creating dedicated exit block " @@ -287,9 +300,11 @@ static Loop *separateNestedLoop(Loop *L, BasicBlock *Preheader, if (SE) SE->forgetLoop(L); + bool PreserveLCSSA = PP->mustPreserveAnalysisID(LCSSAID); + BasicBlock *Header = L->getHeader(); - BasicBlock *NewBB = - SplitBlockPredecessors(Header, OuterLoopPreds, ".outer", PP); + BasicBlock *NewBB = SplitBlockPredecessors(Header, OuterLoopPreds, ".outer", + AA, DT, LI, PreserveLCSSA); // Make sure that NewBB is put someplace intelligent, which doesn't mess up // code layout too horribly. @@ -567,7 +582,7 @@ ReprocessLoop: // Must be exactly this loop: no subloops, parent loops, or non-loop preds // allowed. if (!L->contains(*PI)) { - if (rewriteLoopExitBlock(L, ExitBlock, PP)) { + if (rewriteLoopExitBlock(L, ExitBlock, AA, DT, LI, PP)) { ++NumInserted; Changed = true; } diff --git a/llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp b/llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp index dff756e..82b4f09 100644 --- a/llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp +++ b/llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp @@ -23,6 +23,7 @@ #include "llvm/Transforms/Utils/UnrollLoop.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/LoopIterator.h" #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/ScalarEvolution.h" @@ -32,6 +33,7 @@ #include "llvm/IR/Metadata.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Scalar.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/Cloning.h" #include @@ -59,7 +61,8 @@ STATISTIC(NumRuntimeUnrolled, static void ConnectProlog(Loop *L, Value *TripCount, unsigned Count, BasicBlock *LastPrologBB, BasicBlock *PrologEnd, BasicBlock *OrigPH, BasicBlock *NewPH, - ValueToValueMapTy &VMap, Pass *P) { + ValueToValueMapTy &VMap, AliasAnalysis *AA, + DominatorTree *DT, LoopInfo *LI, Pass *P) { BasicBlock *Latch = L->getLoopLatch(); assert(Latch && "Loop must have a latch"); @@ -117,7 +120,8 @@ static void ConnectProlog(Loop *L, Value *TripCount, unsigned Count, // Split the exit to maintain loop canonicalization guarantees SmallVector Preds(pred_begin(Exit), pred_end(Exit)); if (!Exit->isLandingPad()) { - SplitBlockPredecessors(Exit, Preds, ".unr-lcssa", P); + SplitBlockPredecessors(Exit, Preds, ".unr-lcssa", AA, DT, LI, + P->mustPreserveAnalysisID(LCSSAID)); } else { SmallVector NewBBs; SplitLandingPadPredecessors(Exit, Preds, ".unr1-lcssa", ".unr2-lcssa", @@ -317,7 +321,8 @@ bool llvm::UnrollRuntimeLoopProlog(Loop *L, unsigned Count, LoopInfo *LI, if (Loop *ParentLoop = L->getParentLoop()) SE->forgetLoop(ParentLoop); - // Grab the dominator tree so we can preserve it. + // Grab analyses that we preserve. + auto *AA = LPM->getAnalysisIfAvailable(); auto *DTWP = LPM->getAnalysisIfAvailable(); auto *DT = DTWP ? &DTWP->getDomTree() : nullptr; @@ -397,7 +402,7 @@ bool llvm::UnrollRuntimeLoopProlog(Loop *L, unsigned Count, LoopInfo *LI, // PHI functions. BasicBlock *LastLoopBB = cast(VMap[Latch]); ConnectProlog(L, TripCount, Count, LastLoopBB, PEnd, PH, NewPH, VMap, - LPM->getAsPass()); + AA, DT, LI, LPM->getAsPass()); NumRuntimeUnrolled++; return true; } -- 2.7.4