From ab6f84f7633f269114aaf02adfb38ec28f69167c Mon Sep 17 00:00:00 2001 From: Alina Sbirlea Date: Tue, 21 Aug 2018 23:32:03 +0000 Subject: [PATCH] Update MemorySSA in BasicBlockUtils. Summary: Extend BasicBlocksUtils to update MemorySSA. Subscribers: sanjoy, arsenm, nhaehnle, jlebar, Prazek, llvm-commits Differential Revision: https://reviews.llvm.org/D45300 llvm-svn: 340365 --- .../llvm/Transforms/Utils/BasicBlockUtils.h | 27 ++++++++------ llvm/lib/Target/AMDGPU/SIAnnotateControlFlow.cpp | 3 +- llvm/lib/Transforms/Scalar/GVN.cpp | 2 +- llvm/lib/Transforms/Scalar/LICM.cpp | 2 +- llvm/lib/Transforms/Scalar/LoopUnswitch.cpp | 2 +- llvm/lib/Transforms/Utils/BasicBlockUtils.cpp | 43 +++++++++++++++------- llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp | 7 +++- llvm/lib/Transforms/Utils/LoopSimplify.cpp | 4 +- llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp | 12 +++--- llvm/lib/Transforms/Utils/LoopUtils.cpp | 2 +- 10 files changed, 66 insertions(+), 38 deletions(-) diff --git a/llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h b/llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h index 63b5e6c..dee1541 100644 --- a/llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h +++ b/llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h @@ -35,6 +35,7 @@ class Instruction; class LoopInfo; class MDNode; class MemoryDependenceResults; +class MemorySSAUpdater; class ReturnInst; class TargetLibraryInfo; class Value; @@ -59,6 +60,7 @@ bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI = nullptr); /// value indicates success or failure. bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU = nullptr, LoopInfo *LI = nullptr, + MemorySSAUpdater *MSSAU = nullptr, MemoryDependenceResults *MemDep = nullptr); /// Replace all uses of an instruction (specified by BI) with a value, then @@ -84,13 +86,15 @@ void ReplaceInstWithInst(Instruction *From, Instruction *To); struct CriticalEdgeSplittingOptions { DominatorTree *DT; LoopInfo *LI; + MemorySSAUpdater *MSSAU; bool MergeIdenticalEdges = false; bool DontDeleteUselessPHIs = false; bool PreserveLCSSA = false; CriticalEdgeSplittingOptions(DominatorTree *DT = nullptr, - LoopInfo *LI = nullptr) - : DT(DT), LI(LI) {} + LoopInfo *LI = nullptr, + MemorySSAUpdater *MSSAU = nullptr) + : DT(DT), LI(LI), MSSAU(MSSAU) {} CriticalEdgeSplittingOptions &setMergeIdenticalEdges() { MergeIdenticalEdges = true; @@ -176,14 +180,16 @@ unsigned SplitAllCriticalEdges(Function &F, /// Split the edge connecting specified block. BasicBlock *SplitEdge(BasicBlock *From, BasicBlock *To, - DominatorTree *DT = nullptr, LoopInfo *LI = nullptr); + DominatorTree *DT = nullptr, LoopInfo *LI = nullptr, + MemorySSAUpdater *MSSAU = nullptr); /// Split the specified block at the specified instruction - everything before /// SplitPt stays in Old and everything starting with SplitPt moves to a new /// block. The two blocks are joined by an unconditional branch and the loop /// info is updated. BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt, - DominatorTree *DT = nullptr, LoopInfo *LI = nullptr); + DominatorTree *DT = nullptr, LoopInfo *LI = nullptr, + MemorySSAUpdater *MSSAU = nullptr); /// This method introduces at least one new basic block into the function and /// moves some of the predecessors of BB to be predecessors of the new block. @@ -203,6 +209,7 @@ BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef Preds, const char *Suffix, DominatorTree *DT = nullptr, LoopInfo *LI = nullptr, + MemorySSAUpdater *MSSAU = nullptr, bool PreserveLCSSA = false); /// This method transforms the landing pad, OrigBB, by introducing two new basic @@ -216,13 +223,11 @@ BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef Preds, /// no other analyses. In particular, it does not preserve LoopSimplify /// (because it's complicated to handle the case where one of the edges being /// split is an exit of a loop with other exits). -void SplitLandingPadPredecessors(BasicBlock *OrigBB, - ArrayRef Preds, - const char *Suffix, const char *Suffix2, - SmallVectorImpl &NewBBs, - DominatorTree *DT = nullptr, - LoopInfo *LI = nullptr, - bool PreserveLCSSA = false); +void SplitLandingPadPredecessors( + BasicBlock *OrigBB, ArrayRef Preds, const char *Suffix, + const char *Suffix2, SmallVectorImpl &NewBBs, + DominatorTree *DT = nullptr, LoopInfo *LI = nullptr, + MemorySSAUpdater *MSSAU = nullptr, bool PreserveLCSSA = false); /// This method duplicates the specified return instruction into a predecessor /// which ends in an unconditional branch. If the return instruction returns a diff --git a/llvm/lib/Target/AMDGPU/SIAnnotateControlFlow.cpp b/llvm/lib/Target/AMDGPU/SIAnnotateControlFlow.cpp index 74f1bd8f..a23e102 100644 --- a/llvm/lib/Target/AMDGPU/SIAnnotateControlFlow.cpp +++ b/llvm/lib/Target/AMDGPU/SIAnnotateControlFlow.cpp @@ -372,7 +372,8 @@ void SIAnnotateControlFlow::closeControlFlow(BasicBlock *BB) { Preds.push_back(Pred); } - BB = SplitBlockPredecessors(BB, Preds, "endcf.split", DT, LI, false); + BB = SplitBlockPredecessors(BB, Preds, "endcf.split", DT, LI, nullptr, + false); } Value *Exec = popSaved(); diff --git a/llvm/lib/Transforms/Scalar/GVN.cpp b/llvm/lib/Transforms/Scalar/GVN.cpp index 3e36943..a790db3 100644 --- a/llvm/lib/Transforms/Scalar/GVN.cpp +++ b/llvm/lib/Transforms/Scalar/GVN.cpp @@ -1992,7 +1992,7 @@ bool GVN::runImpl(Function &F, AssumptionCache &RunAC, DominatorTree &RunDT, for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ) { BasicBlock *BB = &*FI++; - bool removedBlock = MergeBlockIntoPredecessor(BB, &DTU, LI, MD); + bool removedBlock = MergeBlockIntoPredecessor(BB, &DTU, LI, nullptr, MD); if (removedBlock) ++NumGVNBlocks; diff --git a/llvm/lib/Transforms/Scalar/LICM.cpp b/llvm/lib/Transforms/Scalar/LICM.cpp index 136e60b..da750d0 100644 --- a/llvm/lib/Transforms/Scalar/LICM.cpp +++ b/llvm/lib/Transforms/Scalar/LICM.cpp @@ -962,7 +962,7 @@ static void splitPredecessorsOfLoopExit(PHINode *PN, DominatorTree *DT, "Expect all predecessors are in the loop"); if (PN->getBasicBlockIndex(PredBB) >= 0) { BasicBlock *NewPred = SplitBlockPredecessors( - ExitBB, PredBB, ".split.loop.exit", DT, LI, true); + ExitBB, PredBB, ".split.loop.exit", DT, LI, nullptr, true); // Since we do not allow splitting EH-block with BlockColors in // canSplitPredecessors(), we can simply assign predecessor's color to // the new block. diff --git a/llvm/lib/Transforms/Scalar/LoopUnswitch.cpp b/llvm/lib/Transforms/Scalar/LoopUnswitch.cpp index 45889bf..7169aed 100644 --- a/llvm/lib/Transforms/Scalar/LoopUnswitch.cpp +++ b/llvm/lib/Transforms/Scalar/LoopUnswitch.cpp @@ -1190,7 +1190,7 @@ 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. - SplitBlockPredecessors(ExitBlock, Preds, ".us-lcssa", DT, LI, + SplitBlockPredecessors(ExitBlock, Preds, ".us-lcssa", DT, LI, nullptr, /*PreserveLCSSA*/ true); } } diff --git a/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp b/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp index 94f37da..d1b9cb6 100644 --- a/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp +++ b/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp @@ -20,6 +20,7 @@ #include "llvm/Analysis/CFG.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/MemoryDependenceAnalysis.h" +#include "llvm/Analysis/MemorySSAUpdater.h" #include "llvm/Analysis/PostDominators.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/CFG.h" @@ -123,9 +124,8 @@ bool llvm::DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI) { } bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU, - LoopInfo *LI, + LoopInfo *LI, MemorySSAUpdater *MSSAU, MemoryDependenceResults *MemDep) { - if (BB->hasAddressTaken()) return false; @@ -171,6 +171,9 @@ bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU, } } + if (MSSAU) + MSSAU->moveAllAfterMergeBlocks(BB, PredBB, &*(BB->begin())); + // Delete the unconditional branch from the predecessor... PredBB->getInstList().pop_back(); @@ -263,13 +266,14 @@ void llvm::ReplaceInstWithInst(Instruction *From, Instruction *To) { } BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, DominatorTree *DT, - LoopInfo *LI) { + LoopInfo *LI, MemorySSAUpdater *MSSAU) { unsigned SuccNum = GetSuccessorNumber(BB, Succ); // If this is a critical edge, let SplitCriticalEdge do it. TerminatorInst *LatchTerm = BB->getTerminator(); - if (SplitCriticalEdge(LatchTerm, SuccNum, CriticalEdgeSplittingOptions(DT, LI) - .setPreserveLCSSA())) + if (SplitCriticalEdge( + LatchTerm, SuccNum, + CriticalEdgeSplittingOptions(DT, LI, MSSAU).setPreserveLCSSA())) return LatchTerm->getSuccessor(SuccNum); // If the edge isn't critical, then BB has a single successor or Succ has a @@ -279,14 +283,14 @@ BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, DominatorTree *DT, // block. assert(SP == BB && "CFG broken"); SP = nullptr; - return SplitBlock(Succ, &Succ->front(), DT, LI); + return SplitBlock(Succ, &Succ->front(), DT, LI, MSSAU); } // Otherwise, if BB has a single successor, split it at the bottom of the // block. assert(BB->getTerminator()->getNumSuccessors() == 1 && "Should have a single succ!"); - return SplitBlock(BB, BB->getTerminator(), DT, LI); + return SplitBlock(BB, BB->getTerminator(), DT, LI, MSSAU); } unsigned @@ -304,7 +308,8 @@ llvm::SplitAllCriticalEdges(Function &F, } BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, - DominatorTree *DT, LoopInfo *LI) { + DominatorTree *DT, LoopInfo *LI, + MemorySSAUpdater *MSSAU) { BasicBlock::iterator SplitIt = SplitPt->getIterator(); while (isa(SplitIt) || SplitIt->isEHPad()) ++SplitIt; @@ -326,6 +331,11 @@ BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, DT->changeImmediateDominator(I, NewNode); } + // Move MemoryAccesses still tracked in Old, but part of New now. + // Update accesses in successor blocks accordingly. + if (MSSAU) + MSSAU->moveAllAfterSpliceBlocks(Old, New, &*(New->begin())); + return New; } @@ -333,6 +343,7 @@ BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, static void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB, ArrayRef Preds, DominatorTree *DT, LoopInfo *LI, + MemorySSAUpdater *MSSAU, bool PreserveLCSSA, bool &HasLoopExit) { // Update dominator tree if available. if (DT) { @@ -345,6 +356,10 @@ static void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB, } } + // Update MemoryPhis after split if MemorySSA is available + if (MSSAU) + MSSAU->wireOldPredecessorsToNewImmediatePredecessor(OldBB, NewBB, Preds); + // The rest of the logic is only relevant for updating the loop structures. if (!LI) return; @@ -485,7 +500,8 @@ static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB, BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, ArrayRef Preds, const char *Suffix, DominatorTree *DT, - LoopInfo *LI, bool PreserveLCSSA) { + LoopInfo *LI, MemorySSAUpdater *MSSAU, + bool PreserveLCSSA) { // Do not attempt to split that which cannot be split. if (!BB->canSplitPredecessors()) return nullptr; @@ -497,7 +513,7 @@ BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, std::string NewName = std::string(Suffix) + ".split-lp"; SplitLandingPadPredecessors(BB, Preds, Suffix, NewName.c_str(), NewBBs, DT, - LI, PreserveLCSSA); + LI, MSSAU, PreserveLCSSA); return NewBBs[0]; } @@ -531,7 +547,7 @@ BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, // Update DominatorTree, LoopInfo, and LCCSA analysis information. bool HasLoopExit = false; - UpdateAnalysisInformation(BB, NewBB, Preds, DT, LI, PreserveLCSSA, + UpdateAnalysisInformation(BB, NewBB, Preds, DT, LI, MSSAU, PreserveLCSSA, HasLoopExit); if (!Preds.empty()) { @@ -547,6 +563,7 @@ void llvm::SplitLandingPadPredecessors(BasicBlock *OrigBB, const char *Suffix1, const char *Suffix2, SmallVectorImpl &NewBBs, DominatorTree *DT, LoopInfo *LI, + MemorySSAUpdater *MSSAU, bool PreserveLCSSA) { assert(OrigBB->isLandingPad() && "Trying to split a non-landing pad!"); @@ -572,7 +589,7 @@ void llvm::SplitLandingPadPredecessors(BasicBlock *OrigBB, } bool HasLoopExit = false; - UpdateAnalysisInformation(OrigBB, NewBB1, Preds, DT, LI, PreserveLCSSA, + UpdateAnalysisInformation(OrigBB, NewBB1, Preds, DT, LI, MSSAU, PreserveLCSSA, HasLoopExit); // Update the PHI nodes in OrigBB with the values coming from NewBB1. @@ -608,7 +625,7 @@ void llvm::SplitLandingPadPredecessors(BasicBlock *OrigBB, // Update DominatorTree, LoopInfo, and LCCSA analysis information. HasLoopExit = false; - UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, DT, LI, + UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, DT, LI, MSSAU, PreserveLCSSA, HasLoopExit); // Update the PHI nodes in OrigBB with the values coming from NewBB2. diff --git a/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp b/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp index 3e30c27..3c3c9315 100644 --- a/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp +++ b/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp @@ -23,6 +23,7 @@ #include "llvm/Analysis/BranchProbabilityInfo.h" #include "llvm/Analysis/CFG.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/MemorySSAUpdater.h" #include "llvm/IR/CFG.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Instructions.h" @@ -198,6 +199,10 @@ llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, // If we have nothing to update, just return. auto *DT = Options.DT; auto *LI = Options.LI; + auto *MSSAU = Options.MSSAU; + if (MSSAU) + MSSAU->wireOldPredecessorsToNewImmediatePredecessor(DestBB, NewBB, {TIBB}); + if (!DT && !LI) return NewBB; @@ -283,7 +288,7 @@ llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, if (!LoopPreds.empty()) { assert(!DestBB->isEHPad() && "We don't split edges to EH pads!"); BasicBlock *NewExitBB = SplitBlockPredecessors( - DestBB, LoopPreds, "split", DT, LI, Options.PreserveLCSSA); + DestBB, LoopPreds, "split", DT, LI, MSSAU, Options.PreserveLCSSA); if (Options.PreserveLCSSA) createPHIsForSplitLoopExit(LoopPreds, NewExitBB, DestBB); } diff --git a/llvm/lib/Transforms/Utils/LoopSimplify.cpp b/llvm/lib/Transforms/Utils/LoopSimplify.cpp index 970494e..fc59caf 100644 --- a/llvm/lib/Transforms/Utils/LoopSimplify.cpp +++ b/llvm/lib/Transforms/Utils/LoopSimplify.cpp @@ -137,7 +137,7 @@ BasicBlock *llvm::InsertPreheaderForLoop(Loop *L, DominatorTree *DT, // Split out the loop pre-header. BasicBlock *PreheaderBB; PreheaderBB = SplitBlockPredecessors(Header, OutsideBlocks, ".preheader", DT, - LI, PreserveLCSSA); + LI, nullptr, PreserveLCSSA); if (!PreheaderBB) return nullptr; @@ -251,7 +251,7 @@ static Loop *separateNestedLoop(Loop *L, BasicBlock *Preheader, SE->forgetLoop(L); BasicBlock *NewBB = SplitBlockPredecessors(Header, OuterLoopPreds, ".outer", - DT, LI, PreserveLCSSA); + DT, LI, nullptr, PreserveLCSSA); // Make sure that NewBB is put someplace intelligent, which doesn't mess up // code layout too horribly. diff --git a/llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp b/llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp index 0057b4b..ce078ab 100644 --- a/llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp +++ b/llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp @@ -124,7 +124,7 @@ static void ConnectProlog(Loop *L, Value *BECount, unsigned Count, PrologExitPreds.push_back(PredBB); SplitBlockPredecessors(PrologExit, PrologExitPreds, ".unr-lcssa", DT, LI, - PreserveLCSSA); + nullptr, PreserveLCSSA); } // Create a branch around the original loop, which is taken if there are no @@ -143,7 +143,7 @@ static void ConnectProlog(Loop *L, Value *BECount, unsigned Count, // Split the exit to maintain loop canonicalization guarantees SmallVector Preds(predecessors(OriginalLoopLatchExit)); SplitBlockPredecessors(OriginalLoopLatchExit, Preds, ".unr-lcssa", DT, LI, - PreserveLCSSA); + nullptr, PreserveLCSSA); // Add the branch to the exit block (around the unrolled loop) B.CreateCondBr(BrLoopExit, OriginalLoopLatchExit, NewPreHeader); InsertPt->eraseFromParent(); @@ -257,7 +257,7 @@ static void ConnectEpilog(Loop *L, Value *ModVal, BasicBlock *NewExit, assert(Exit && "Loop must have a single exit block only"); // Split the epilogue exit to maintain loop canonicalization guarantees SmallVector Preds(predecessors(Exit)); - SplitBlockPredecessors(Exit, Preds, ".epilog-lcssa", DT, LI, + SplitBlockPredecessors(Exit, Preds, ".epilog-lcssa", DT, LI, nullptr, PreserveLCSSA); // Add the branch to the exit block (around the unrolling loop) B.CreateCondBr(BrLoopExit, EpilogPreHeader, Exit); @@ -267,7 +267,7 @@ static void ConnectEpilog(Loop *L, Value *ModVal, BasicBlock *NewExit, // Split the main loop exit to maintain canonicalization guarantees. SmallVector NewExitPreds{Latch}; - SplitBlockPredecessors(NewExit, NewExitPreds, ".loopexit", DT, LI, + SplitBlockPredecessors(NewExit, NewExitPreds, ".loopexit", DT, LI, nullptr, PreserveLCSSA); } @@ -636,8 +636,8 @@ bool llvm::UnrollRuntimeLoopRemainder(Loop *L, unsigned Count, NewPreHeader->setName(PreHeader->getName() + ".new"); // Split LatchExit to create phi nodes from branch above. SmallVector Preds(predecessors(LatchExit)); - NewExit = SplitBlockPredecessors(LatchExit, Preds, ".unr-lcssa", - DT, LI, PreserveLCSSA); + NewExit = SplitBlockPredecessors(LatchExit, Preds, ".unr-lcssa", DT, LI, + nullptr, PreserveLCSSA); // NewExit gets its DebugLoc from LatchExit, which is not part of the // original Loop. // Fix this by setting Loop's DebugLoc to NewExit. diff --git a/llvm/lib/Transforms/Utils/LoopUtils.cpp b/llvm/lib/Transforms/Utils/LoopUtils.cpp index 3560a49..c267086 100644 --- a/llvm/lib/Transforms/Utils/LoopUtils.cpp +++ b/llvm/lib/Transforms/Utils/LoopUtils.cpp @@ -1174,7 +1174,7 @@ bool llvm::formDedicatedExitBlocks(Loop *L, DominatorTree *DT, LoopInfo *LI, return false; auto *NewExitBB = SplitBlockPredecessors( - BB, InLoopPredecessors, ".loopexit", DT, LI, PreserveLCSSA); + BB, InLoopPredecessors, ".loopexit", DT, LI, nullptr, PreserveLCSSA); if (!NewExitBB) LLVM_DEBUG( -- 2.7.4