Index: llvm/include/llvm/Transforms/Scalar/JumpThreading.h =================================================================== --- llvm/include/llvm/Transforms/Scalar/JumpThreading.h +++ llvm/include/llvm/Transforms/Scalar/JumpThreading.h @@ -90,6 +90,8 @@ #endif DenseSet> RecursionSet; + DenseMap BBNumbers; + unsigned BBDupThreshold; // RAII helper for updating the recursion stack. Index: llvm/include/llvm/Transforms/Utils/SSAUpdaterBulk.h =================================================================== --- llvm/include/llvm/Transforms/Utils/SSAUpdaterBulk.h +++ llvm/include/llvm/Transforms/Utils/SSAUpdaterBulk.h @@ -80,11 +80,14 @@ /// the requested uses update. /// /// The function requires dominator tree DT, which is used for computing - /// locations for new phi-nodes insertions. If a nonnull pointer to a vector + /// locations for new phi-nodes insertions, and BBNumbers map to avoid + /// non-determinism in blocks visiting order. If a nonnull pointer to a vector /// InsertedPHIs is passed, all the new phi-nodes will be added to this /// vector. - void RewriteAllUses(DominatorTree *DT, - SmallVectorImpl *InsertedPHIs = nullptr); + void + RewriteAllUses(DominatorTree *DT, + const DenseMap &BBNumbers, + SmallVectorImpl *InsertedPHIs = nullptr); }; } // end namespace llvm Index: llvm/lib/Transforms/Scalar/JumpThreading.cpp =================================================================== --- llvm/lib/Transforms/Scalar/JumpThreading.cpp +++ llvm/lib/Transforms/Scalar/JumpThreading.cpp @@ -66,6 +66,7 @@ #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/Cloning.h" #include "llvm/Transforms/Utils/SSAUpdater.h" +#include "llvm/Transforms/Utils/SSAUpdaterBulk.h" #include "llvm/Transforms/Utils/ValueMapper.h" #include #include @@ -357,6 +358,10 @@ BFI = std::move(BFI_); } + unsigned NextBBNum = 0; + for (auto &BB : F) + BBNumbers[&BB] = NextBBNum++; + // JumpThreading must not processes blocks unreachable from entry. It's a // waste of compute time and can potentially lead to hangs. SmallPtrSet Unreachable; @@ -1997,19 +2002,33 @@ // PHI nodes for NewBB now. AddPHINodeEntriesForMappedBlock(SuccBB, BB, NewBB, ValueMapping); + // Update the terminator of PredBB to jump to NewBB instead of BB. This + // eliminates predecessors from BB, which requires us to simplify any PHI + // nodes in BB. + TerminatorInst *PredTerm = PredBB->getTerminator(); + for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i) + if (PredTerm->getSuccessor(i) == BB) { + BB->removePredecessor(PredBB, true); + PredTerm->setSuccessor(i, NewBB); + } + // If there were values defined in BB that are used outside the block, then we // now have to update all uses of the value to use either the original value, // the cloned value, or some PHI derived value. This can require arbitrary // PHI insertion, of which we are prepared to do, clean these up now. - SSAUpdater SSAUpdate; - SmallVector UsesToRename; + SSAUpdaterBulk SSAUpdate; + for (Instruction &I : *BB) { + SmallVector UsesToRename; + // Scan all uses of this instruction to see if it is used outside of its - // block, and if so, record them in UsesToRename. + // block, and if so, record them in UsesToRename. Also, skip phi operands + // from PredBB - we'll remove them anyway. for (Use &U : I.uses()) { Instruction *User = cast(U.getUser()); if (PHINode *UserPN = dyn_cast(User)) { - if (UserPN->getIncomingBlock(U) == BB) + if (UserPN->getIncomingBlock(U) == BB || + UserPN->getIncomingBlock(U) == PredBB) continue; } else if (User->getParent() == BB) continue; @@ -2020,35 +2039,24 @@ // If there are no uses outside the block, we're done with this instruction. if (UsesToRename.empty()) continue; + unsigned VarNum = SSAUpdate.AddVariable(I.getName(), I.getType()); - DEBUG(dbgs() << "JT: Renaming non-local uses of: " << I << "\n"); - - // We found a use of I outside of BB. Rename all uses of I that are outside - // its block to be uses of the appropriate PHI node etc. See ValuesInBlocks - // with the two values we know. - SSAUpdate.Initialize(I.getType(), I.getName()); - SSAUpdate.AddAvailableValue(BB, &I); - SSAUpdate.AddAvailableValue(NewBB, ValueMapping[&I]); - - while (!UsesToRename.empty()) - SSAUpdate.RewriteUse(*UsesToRename.pop_back_val()); - DEBUG(dbgs() << "\n"); + // We found a use of I outside of BB - we need to rename all uses of I that + // are outside its block to be uses of the appropriate PHI node etc. + SSAUpdate.AddAvailableValue(VarNum, BB, &I); + SSAUpdate.AddAvailableValue(VarNum, NewBB, ValueMapping[&I]); + for (auto *U : UsesToRename) + SSAUpdate.AddUse(VarNum, U); } - // Ok, NewBB is good to go. Update the terminator of PredBB to jump to - // NewBB instead of BB. This eliminates predecessors from BB, which requires - // us to simplify any PHI nodes in BB. - TerminatorInst *PredTerm = PredBB->getTerminator(); - for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i) - if (PredTerm->getSuccessor(i) == BB) { - BB->removePredecessor(PredBB, true); - PredTerm->setSuccessor(i, NewBB); - } - DDT->applyUpdates({{DominatorTree::Insert, NewBB, SuccBB}, {DominatorTree::Insert, PredBB, NewBB}, {DominatorTree::Delete, PredBB, BB}}); + // Apply all updates we queued with DDT and get the updated Dominator Tree. + DominatorTree *DT = &DDT->flush(); + SSAUpdate.RewriteAllUses(DT, BBNumbers); + // At this point, the IR is fully up to date and consistent. Do a quick scan // over the new instructions and zap any that are constants or dead. This // frequently happens because of phi translation. Index: llvm/lib/Transforms/Utils/SSAUpdaterBulk.cpp =================================================================== --- llvm/lib/Transforms/Utils/SSAUpdaterBulk.cpp +++ llvm/lib/Transforms/Utils/SSAUpdaterBulk.cpp @@ -125,8 +125,10 @@ /// Perform all the necessary updates, including new PHI-nodes insertion and the /// requested uses update. -void SSAUpdaterBulk::RewriteAllUses(DominatorTree *DT, - SmallVectorImpl *InsertedPHIs) { +void SSAUpdaterBulk::RewriteAllUses( + DominatorTree *DT, + const DenseMap &BBNumbers, + SmallVectorImpl *InsertedPHIs) { for (auto &R : Rewrites) { // Compute locations for new phi-nodes. // For that we need to initialize DefBlocks from definitions in R.Defines, @@ -151,6 +153,11 @@ IDF.resetLiveInBlocks(); IDF.setLiveInBlocks(LiveInBlocks); IDF.calculate(IDFBlocks); + llvm::sort(IDFBlocks.begin(), IDFBlocks.end(), + [&BBNumbers](const BasicBlock *A, const BasicBlock *B) { + return BBNumbers.lookup(A) < BBNumbers.lookup(B); + }); + // We've computed IDF, now insert new phi-nodes there. SmallVector InsertedPHIsForVar; Index: llvm/unittests/Transforms/Utils/SSAUpdaterBulk.cpp =================================================================== --- llvm/unittests/Transforms/Utils/SSAUpdaterBulk.cpp +++ llvm/unittests/Transforms/Utils/SSAUpdaterBulk.cpp @@ -50,6 +50,11 @@ BasicBlock *FalseBB = BasicBlock::Create(C, "false", F); BasicBlock *MergeBB = BasicBlock::Create(C, "merge", F); + DenseMap BBNumbers; + unsigned NextBBNum = 0; + for (auto &BB : *F) + BBNumbers[&BB] = NextBBNum++; + B.SetInsertPoint(IfBB); B.CreateCondBr(B.getTrue(), TrueBB, FalseBB); @@ -86,7 +91,7 @@ Updater.AddUse(VarNum, &I3->getOperandUse(1)); DominatorTree DT(*F); - Updater.RewriteAllUses(&DT); + Updater.RewriteAllUses(&DT, BBNumbers); // Check how %5 and %6 were rewritten. PHINode *UpdatePhiA = dyn_cast_or_null(I1->getOperand(0)); @@ -136,6 +141,10 @@ BasicBlock *LoopStartBB = BasicBlock::Create(C, "loopstart", F); BasicBlock *LoopMainBB = BasicBlock::Create(C, "loopmain", F); BasicBlock *AfterLoopBB = BasicBlock::Create(C, "afterloop", F); + DenseMap BBNumbers; + unsigned NextBBNum = 0; + for (auto &BB : *F) + BBNumbers[&BB] = NextBBNum++; B.SetInsertPoint(IfBB); Value *AddOp1 = B.CreateAdd(FirstArg, ConstantInt::get(I32Ty, 1)); @@ -178,7 +187,7 @@ // Save all inserted phis into a vector. SmallVector Inserted; DominatorTree DT(*F); - Updater.RewriteAllUses(&DT, &Inserted); + Updater.RewriteAllUses(&DT, BBNumbers, &Inserted); // Only one phi should have been inserted. EXPECT_EQ(Inserted.size(), 1u);