Index: include/llvm/Transforms/Utils/BasicBlockUtils.h =================================================================== --- include/llvm/Transforms/Utils/BasicBlockUtils.h +++ include/llvm/Transforms/Utils/BasicBlockUtils.h @@ -34,6 +34,8 @@ class LoopInfo; class MDNode; class MemoryDependenceResults; +class MemorySSA; +class MemorySSAUpdater; class ReturnInst; class TargetLibraryInfo; class Value; @@ -58,6 +60,7 @@ /// value indicates success or failure. bool MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT = nullptr, LoopInfo *LI = nullptr, + MemorySSAUpdater *MSSAUpdater = nullptr, MemoryDependenceResults *MemDep = nullptr, DeferredDominance *DDT = nullptr); @@ -84,13 +87,17 @@ struct CriticalEdgeSplittingOptions { DominatorTree *DT; LoopInfo *LI; + MemorySSA *MSSA; + MemorySSAUpdater *MSSAUpdater; bool MergeIdenticalEdges = false; bool DontDeleteUselessPHIs = false; bool PreserveLCSSA = false; CriticalEdgeSplittingOptions(DominatorTree *DT = nullptr, - LoopInfo *LI = nullptr) - : DT(DT), LI(LI) {} + LoopInfo *LI = nullptr, + MemorySSA *MSSA = nullptr, + MemorySSAUpdater *MSSAUpdater = nullptr) + : DT(DT), LI(LI), MSSA(MSSA), MSSAUpdater(MSSAUpdater) {} CriticalEdgeSplittingOptions &setMergeIdenticalEdges() { MergeIdenticalEdges = true; @@ -176,14 +183,18 @@ /// Split the edge connecting specified block. BasicBlock *SplitEdge(BasicBlock *From, BasicBlock *To, - DominatorTree *DT = nullptr, LoopInfo *LI = nullptr); + DominatorTree *DT = nullptr, LoopInfo *LI = nullptr, + MemorySSA *MSSA = nullptr, + MemorySSAUpdater *MSSAUpdater = 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, + MemorySSA *MSSA = nullptr, + MemorySSAUpdater *MSSAUpdater = 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 +214,8 @@ const char *Suffix, DominatorTree *DT = nullptr, LoopInfo *LI = nullptr, + MemorySSA *MSSA = nullptr, + MemorySSAUpdater *MSSAUpdater = nullptr, bool PreserveLCSSA = false); /// This method transforms the landing pad, OrigBB, by introducing two new basic @@ -216,13 +229,12 @@ /// 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, + MemorySSA *MSSA = nullptr, MemorySSAUpdater *MSSAUpdater = 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 Index: lib/Target/AMDGPU/SIAnnotateControlFlow.cpp =================================================================== --- lib/Target/AMDGPU/SIAnnotateControlFlow.cpp +++ lib/Target/AMDGPU/SIAnnotateControlFlow.cpp @@ -372,7 +372,8 @@ Preds.push_back(Pred); } - BB = SplitBlockPredecessors(BB, Preds, "endcf.split", DT, LI, false); + BB = SplitBlockPredecessors(BB, Preds, "endcf.split", DT, LI, nullptr, + nullptr, false); } Value *Exec = popSaved(); Index: lib/Transforms/Scalar/GVN.cpp =================================================================== --- lib/Transforms/Scalar/GVN.cpp +++ lib/Transforms/Scalar/GVN.cpp @@ -2024,7 +2024,7 @@ for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ) { BasicBlock *BB = &*FI++; - bool removedBlock = MergeBlockIntoPredecessor(BB, DT, LI, MD); + bool removedBlock = MergeBlockIntoPredecessor(BB, DT, LI, nullptr, MD); if (removedBlock) ++NumGVNBlocks; Index: lib/Transforms/Scalar/LICM.cpp =================================================================== --- lib/Transforms/Scalar/LICM.cpp +++ lib/Transforms/Scalar/LICM.cpp @@ -907,7 +907,7 @@ "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, 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. Index: lib/Transforms/Scalar/LoopUnswitch.cpp =================================================================== --- lib/Transforms/Scalar/LoopUnswitch.cpp +++ lib/Transforms/Scalar/LoopUnswitch.cpp @@ -1190,8 +1190,8 @@ // 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, - /*PreserveLCSSA*/ true); + SplitBlockPredecessors(ExitBlock, Preds, ".us-lcssa", DT, LI, nullptr, + nullptr, /*PreserveLCSSA*/ true); } } Index: lib/Transforms/Utils/BasicBlockUtils.cpp =================================================================== --- lib/Transforms/Utils/BasicBlockUtils.cpp +++ lib/Transforms/Utils/BasicBlockUtils.cpp @@ -20,6 +20,9 @@ #include "llvm/Analysis/CFG.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/MemoryDependenceAnalysis.h" +#include "llvm/Analysis/MemorySSA.h" +#include "llvm/Analysis/MemorySSAUpdater.h" +#include "llvm/Analysis/Utils/Local.h" #include "llvm/Transforms/Utils/Local.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/CFG.h" @@ -117,6 +120,7 @@ bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT, LoopInfo *LI, + MemorySSAUpdater *MSSAUpdater, MemoryDependenceResults *MemDep, DeferredDominance *DDT) { assert(!(DT && DDT) && "Cannot call with both DT and DDT."); @@ -166,6 +170,10 @@ } } + if (MSSAUpdater) { + MSSAUpdater->moveAllAfterMergeBlocks(BB, PredBB, &*(BB->begin())); + } + // Delete the unconditional branch from the predecessor... PredBB->getInstList().pop_back(); @@ -261,13 +269,15 @@ } BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, DominatorTree *DT, - LoopInfo *LI) { + LoopInfo *LI, MemorySSA *MSSA, + MemorySSAUpdater *MSSAUpdater) { 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, MSSA, MSSAUpdater) + .setPreserveLCSSA())) return LatchTerm->getSuccessor(SuccNum); // If the edge isn't critical, then BB has a single successor or Succ has a @@ -277,14 +287,14 @@ // block. assert(SP == BB && "CFG broken"); SP = nullptr; - return SplitBlock(Succ, &Succ->front(), DT, LI); + return SplitBlock(Succ, &Succ->front(), DT, LI, MSSA, MSSAUpdater); } // 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, MSSA, MSSAUpdater); } unsigned @@ -302,7 +312,8 @@ } BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, - DominatorTree *DT, LoopInfo *LI) { + DominatorTree *DT, LoopInfo *LI, MemorySSA *MSSA, + MemorySSAUpdater *MSSAUpdater) { BasicBlock::iterator SplitIt = SplitPt->getIterator(); while (isa(SplitIt) || SplitIt->isEHPad()) ++SplitIt; @@ -324,6 +335,11 @@ DT->changeImmediateDominator(I, NewNode); } + // Move MemoryAccesses still tracked in Old, but part of New now. + // Update accesses in successor blocks accordingly. + if (MSSA) + MSSAUpdater->moveAllAfterSpliceBlocks(Old, New, &*(New->begin())); + return New; } @@ -331,6 +347,8 @@ static void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB, ArrayRef Preds, DominatorTree *DT, LoopInfo *LI, + MemorySSA *MSSA, + MemorySSAUpdater *MSSAUpdater, bool PreserveLCSSA, bool &HasLoopExit) { // Update dominator tree if available. if (DT) { @@ -343,6 +361,11 @@ } } + // Update MemoryPhis after split if MemorySSA is available + if (MSSA) { + MSSAUpdater->movePhiToNewImmediatePredecessor(OldBB, NewBB); + } + // The rest of the logic is only relevant for updating the loop structures. if (!LI) return; @@ -483,7 +506,9 @@ BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB, ArrayRef Preds, const char *Suffix, DominatorTree *DT, - LoopInfo *LI, bool PreserveLCSSA) { + LoopInfo *LI, MemorySSA *MSSA, + MemorySSAUpdater *MSSAUpdater, + bool PreserveLCSSA) { // Do not attempt to split that which cannot be split. if (!BB->canSplitPredecessors()) return nullptr; @@ -495,7 +520,7 @@ std::string NewName = std::string(Suffix) + ".split-lp"; SplitLandingPadPredecessors(BB, Preds, Suffix, NewName.c_str(), NewBBs, DT, - LI, PreserveLCSSA); + LI, MSSA, MSSAUpdater, PreserveLCSSA); return NewBBs[0]; } @@ -529,8 +554,8 @@ // Update DominatorTree, LoopInfo, and LCCSA analysis information. bool HasLoopExit = false; - UpdateAnalysisInformation(BB, NewBB, Preds, DT, LI, PreserveLCSSA, - HasLoopExit); + UpdateAnalysisInformation(BB, NewBB, Preds, DT, LI, MSSA, MSSAUpdater, + PreserveLCSSA, HasLoopExit); if (!Preds.empty()) { // Update the PHI nodes in BB with the values coming from NewBB. @@ -540,12 +565,11 @@ return NewBB; } -void llvm::SplitLandingPadPredecessors(BasicBlock *OrigBB, - ArrayRef Preds, - const char *Suffix1, const char *Suffix2, - SmallVectorImpl &NewBBs, - DominatorTree *DT, LoopInfo *LI, - bool PreserveLCSSA) { +void llvm::SplitLandingPadPredecessors( + BasicBlock *OrigBB, ArrayRef Preds, const char *Suffix1, + const char *Suffix2, SmallVectorImpl &NewBBs, + DominatorTree *DT, LoopInfo *LI, MemorySSA *MSSA, + MemorySSAUpdater *MSSAUpdater, bool PreserveLCSSA) { assert(OrigBB->isLandingPad() && "Trying to split a non-landing pad!"); // Create a new basic block for OrigBB's predecessors listed in Preds. Insert @@ -570,8 +594,8 @@ } bool HasLoopExit = false; - UpdateAnalysisInformation(OrigBB, NewBB1, Preds, DT, LI, PreserveLCSSA, - HasLoopExit); + UpdateAnalysisInformation(OrigBB, NewBB1, Preds, DT, LI, MSSA, MSSAUpdater, + PreserveLCSSA, HasLoopExit); // Update the PHI nodes in OrigBB with the values coming from NewBB1. UpdatePHINodes(OrigBB, NewBB1, Preds, BI1, HasLoopExit); @@ -606,8 +630,8 @@ // Update DominatorTree, LoopInfo, and LCCSA analysis information. HasLoopExit = false; - UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, DT, LI, - PreserveLCSSA, HasLoopExit); + UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, DT, LI, MSSA, + MSSAUpdater, PreserveLCSSA, HasLoopExit); // Update the PHI nodes in OrigBB with the values coming from NewBB2. UpdatePHINodes(OrigBB, NewBB2, NewBB2Preds, BI2, HasLoopExit); Index: lib/Transforms/Utils/BreakCriticalEdges.cpp =================================================================== --- lib/Transforms/Utils/BreakCriticalEdges.cpp +++ lib/Transforms/Utils/BreakCriticalEdges.cpp @@ -23,6 +23,8 @@ #include "llvm/Analysis/BranchProbabilityInfo.h" #include "llvm/Analysis/CFG.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/MemorySSA.h" +#include "llvm/Analysis/MemorySSAUpdater.h" #include "llvm/IR/CFG.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Instructions.h" @@ -198,6 +200,11 @@ // If we have nothing to update, just return. auto *DT = Options.DT; auto *LI = Options.LI; + auto *MSSA = Options.MSSA; + auto *MSSAUpdater = Options.MSSAUpdater; + if (MSSA) + MSSAUpdater->replacePhiIncomingBlock(DestBB, TIBB, NewBB); + if (!DT && !LI) return NewBB; @@ -282,8 +289,9 @@ } if (!LoopPreds.empty()) { assert(!DestBB->isEHPad() && "We don't split edges to EH pads!"); - BasicBlock *NewExitBB = SplitBlockPredecessors( - DestBB, LoopPreds, "split", DT, LI, Options.PreserveLCSSA); + BasicBlock *NewExitBB = + SplitBlockPredecessors(DestBB, LoopPreds, "split", DT, LI, MSSA, + MSSAUpdater, Options.PreserveLCSSA); if (Options.PreserveLCSSA) createPHIsForSplitLoopExit(LoopPreds, NewExitBB, DestBB); } Index: lib/Transforms/Utils/LoopSimplify.cpp =================================================================== --- lib/Transforms/Utils/LoopSimplify.cpp +++ lib/Transforms/Utils/LoopSimplify.cpp @@ -137,7 +137,7 @@ // Split out the loop pre-header. BasicBlock *PreheaderBB; PreheaderBB = SplitBlockPredecessors(Header, OutsideBlocks, ".preheader", DT, - LI, PreserveLCSSA); + LI, nullptr, nullptr, PreserveLCSSA); if (!PreheaderBB) return nullptr; @@ -250,8 +250,9 @@ if (SE) SE->forgetLoop(L); - BasicBlock *NewBB = SplitBlockPredecessors(Header, OuterLoopPreds, ".outer", - DT, LI, PreserveLCSSA); + BasicBlock *NewBB = + SplitBlockPredecessors(Header, OuterLoopPreds, ".outer", DT, LI, nullptr, + nullptr, PreserveLCSSA); // Make sure that NewBB is put someplace intelligent, which doesn't mess up // code layout too horribly. Index: lib/Transforms/Utils/LoopUnrollRuntime.cpp =================================================================== --- lib/Transforms/Utils/LoopUnrollRuntime.cpp +++ lib/Transforms/Utils/LoopUnrollRuntime.cpp @@ -124,7 +124,7 @@ PrologExitPreds.push_back(PredBB); SplitBlockPredecessors(PrologExit, PrologExitPreds, ".unr-lcssa", DT, LI, - PreserveLCSSA); + nullptr, nullptr, PreserveLCSSA); } // Create a branch around the original loop, which is taken if there are no @@ -143,7 +143,7 @@ // Split the exit to maintain loop canonicalization guarantees SmallVector Preds(predecessors(OriginalLoopLatchExit)); SplitBlockPredecessors(OriginalLoopLatchExit, Preds, ".unr-lcssa", DT, LI, - PreserveLCSSA); + nullptr, nullptr, PreserveLCSSA); // Add the branch to the exit block (around the unrolled loop) B.CreateCondBr(BrLoopExit, OriginalLoopLatchExit, NewPreHeader); InsertPt->eraseFromParent(); @@ -257,7 +257,7 @@ 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, nullptr, PreserveLCSSA); // Add the branch to the exit block (around the unrolling loop) B.CreateCondBr(BrLoopExit, EpilogPreHeader, Exit); @@ -267,8 +267,8 @@ // Split the main loop exit to maintain canonicalization guarantees. SmallVector NewExitPreds{Latch}; - SplitBlockPredecessors(NewExit, NewExitPreds, ".loopexit", DT, LI, - PreserveLCSSA); + SplitBlockPredecessors(NewExit, NewExitPreds, ".loopexit", DT, LI, nullptr, + nullptr, PreserveLCSSA); } /// Create a clone of the blocks in a loop and connect them together. @@ -636,8 +636,8 @@ 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, 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. Index: lib/Transforms/Utils/LoopUtils.cpp =================================================================== --- lib/Transforms/Utils/LoopUtils.cpp +++ lib/Transforms/Utils/LoopUtils.cpp @@ -1172,8 +1172,9 @@ if (IsDedicatedExit) return false; - auto *NewExitBB = SplitBlockPredecessors( - BB, InLoopPredecessors, ".loopexit", DT, LI, PreserveLCSSA); + auto *NewExitBB = + SplitBlockPredecessors(BB, InLoopPredecessors, ".loopexit", DT, LI, + nullptr, nullptr, PreserveLCSSA); if (!NewExitBB) LLVM_DEBUG(