Index: llvm/trunk/include/llvm/Transforms/Utils/BasicBlockUtils.h =================================================================== --- llvm/trunk/include/llvm/Transforms/Utils/BasicBlockUtils.h +++ llvm/trunk/include/llvm/Transforms/Utils/BasicBlockUtils.h @@ -35,6 +35,7 @@ class LoopInfo; class MDNode; class MemoryDependenceResults; +class MemorySSAUpdater; class ReturnInst; class TargetLibraryInfo; class Value; @@ -59,6 +60,7 @@ /// 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 @@ 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 @@ /// 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 @@ 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 @@ /// 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 Index: llvm/trunk/lib/Target/AMDGPU/SIAnnotateControlFlow.cpp =================================================================== --- llvm/trunk/lib/Target/AMDGPU/SIAnnotateControlFlow.cpp +++ llvm/trunk/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, + false); } Value *Exec = popSaved(); Index: llvm/trunk/lib/Transforms/Scalar/GVN.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/GVN.cpp +++ llvm/trunk/lib/Transforms/Scalar/GVN.cpp @@ -1992,7 +1992,7 @@ 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; Index: llvm/trunk/lib/Transforms/Scalar/LICM.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/LICM.cpp +++ llvm/trunk/lib/Transforms/Scalar/LICM.cpp @@ -962,7 +962,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, 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: llvm/trunk/lib/Transforms/Scalar/LoopUnswitch.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/LoopUnswitch.cpp +++ llvm/trunk/lib/Transforms/Scalar/LoopUnswitch.cpp @@ -1190,7 +1190,7 @@ // 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); } } Index: llvm/trunk/lib/Transforms/Utils/BasicBlockUtils.cpp =================================================================== --- llvm/trunk/lib/Transforms/Utils/BasicBlockUtils.cpp +++ llvm/trunk/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::MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU, - LoopInfo *LI, + LoopInfo *LI, MemorySSAUpdater *MSSAU, MemoryDependenceResults *MemDep) { - if (BB->hasAddressTaken()) return false; @@ -171,6 +171,9 @@ } } + if (MSSAU) + MSSAU->moveAllAfterMergeBlocks(BB, PredBB, &*(BB->begin())); + // Delete the unconditional branch from the predecessor... PredBB->getInstList().pop_back(); @@ -263,13 +266,14 @@ } 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 @@ // 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 @@ } 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 @@ 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 @@ 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 @@ } } + // 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 @@ 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 @@ 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 @@ // 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 @@ 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 @@ } 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 @@ // 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. Index: llvm/trunk/lib/Transforms/Utils/BreakCriticalEdges.cpp =================================================================== --- llvm/trunk/lib/Transforms/Utils/BreakCriticalEdges.cpp +++ llvm/trunk/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 @@ // 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 @@ 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); } Index: llvm/trunk/lib/Transforms/Utils/LoopSimplify.cpp =================================================================== --- llvm/trunk/lib/Transforms/Utils/LoopSimplify.cpp +++ llvm/trunk/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, PreserveLCSSA); if (!PreheaderBB) return nullptr; @@ -251,7 +251,7 @@ 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. Index: llvm/trunk/lib/Transforms/Utils/LoopUnrollRuntime.cpp =================================================================== --- llvm/trunk/lib/Transforms/Utils/LoopUnrollRuntime.cpp +++ llvm/trunk/lib/Transforms/Utils/LoopUnrollRuntime.cpp @@ -124,7 +124,7 @@ 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 @@ // 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 @@ 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 @@ // 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 @@ 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. Index: llvm/trunk/lib/Transforms/Utils/LoopUtils.cpp =================================================================== --- llvm/trunk/lib/Transforms/Utils/LoopUtils.cpp +++ llvm/trunk/lib/Transforms/Utils/LoopUtils.cpp @@ -1174,7 +1174,7 @@ return false; auto *NewExitBB = SplitBlockPredecessors( - BB, InLoopPredecessors, ".loopexit", DT, LI, PreserveLCSSA); + BB, InLoopPredecessors, ".loopexit", DT, LI, nullptr, PreserveLCSSA); if (!NewExitBB) LLVM_DEBUG(