[SSAUpdaterBulk] Sort blocks in IDF to avoid non-determinism.

[mzolotukhin]

Summary

IDF does not guarantee that returned basic blocks are sorted in any
order, and to avoid non-determinism we need to sort them. To sort basic
blocks we need to enumerate them first, and this patch adds such
enumeration into JumpThreading pass.

[mzolotukhin]

Hi,

This patch includes two pieces: fixing non-determinism in SSAUpdaterBulk and enabling it in JumpThreading. When approved, I'll commit them separately, but I included them both here for convenience. The fix for SSAUpdaterBulk requires basic-block enumeration, which should be passed from the SSAUpdaterBulk user, and thus it incurs the corresponding changes in JumpThreading. I'm not a big fan of an extra parameter in RewriteAllUses function and will be happy to discuss alternative, but for now I followed an example from MemorySSA. What do you think?

Thanks,
Michael

[davide]

llvm/lib/Transforms/Scalar/JumpThreading.cpp

361–364

Do you need to number also unreachable blocks? You could skip them, I think.

[mzolotukhin]

llvm/lib/Transforms/Scalar/JumpThreading.cpp

361–364

That's true, they shouldn't be in IDF.

[davide]

llvm/lib/Transforms/Scalar/JumpThreading.cpp

361–364

To be more clear (sorry if I wasn't), few lines later you already have a walk of the blocks in function order, so you can piggy back on that to value number non-unreachable blocks (as you're querying the dominator for reachability anyway.

[mzolotukhin]

llvm/lib/Transforms/Scalar/JumpThreading.cpp

361–364

No, I got this:) I will change that before committing.

[• dberlin]

IDF does not guarantee that returned basic blocks are sorted in any
order,

1. It looks like, in theory, this is true, but could easily be solved in IDF.
2. Given that, if this is a thing pretty much all clients of idf will have to handle, should we just sort the output of IDF?

The solution in IDF should just be changing domtreenodepair to a tuple, with the last item being domtreenode->getDFSNumIn()

That should provide a unique and guaranteed ordering for IDF.

To explain why:

1. IDF uses a priority queue as an overall worklist
2. It current uses "DT node level" as the priority key (which is not unique per dt node).
3. The other worklist is a vector where order of items depends only on order of dom tree siblings (and pq processing order overall)
4. The output is a vector which depends on pq processing order and dom tree sibling order

So, outside of pq ordering, everything else is inserted in the same order each time by using vectors and walking the linked list of siblings in the dom tree (which should be the same each time).

Thus, any non-determinism must come from the non-unique orderings for DT node level keys (IE two dt nodes can have the same key)

Adding the DFS in number (which also depends only on domtree visitation ordering) should cause it to have unique keys for each element in the pq, as long as as the dom tree creation itself is not non-deterministic (which it shouldn't be, or we're screwed in a lot of anyway).

Once it has unique keys in the pq, it should place everything on the vectors in the same order each time.

[mzolotukhin]

The solution in IDF should just be changing domtreenodepair to a tuple, with the last item being domtreenode->getDFSNumIn()

Just to make sure I understand you correctly: we need to change pair<DomTreeNode *, unsigned> to tuple<DomTreeNode *, unsigned, unsigned> and use the second and third elements as keys for the priority queue (i.e. we will need to implement a compare function for it, which will look at RootLevel first and at DfsNumber second if RootLevels are the same). Is it what you meant?

Michael

[• dberlin]

In D46564#1090834, @mzolotukhin wrote:

The solution in IDF should just be changing domtreenodepair to a tuple, with the last item being domtreenode->getDFSNumIn()

Just to make sure I understand you correctly: we need to change pair<DomTreeNode *, unsigned> to tuple<DomTreeNode *, unsigned, unsigned> and use the second and third elements as keys for the priority queue (i.e. we will need to implement a compare function for it, which will look at RootLevel first and at DfsNumber second if RootLevels are the same). Is it what you meant?

Michael

Correct. I updated my earlier comment online so it is hopefully more clear now)
You actually could just use pair<DomTreeNode *, pair<unsigned, unsigned>> and it should work only having to change the two lines pushing onto pq, though it's uglier in the abstract
Either way, you should also call DT->updateDFSNumbers() at the beginning of IDF::calculate to ensure DFS numbers are up to date.

(I didn't look to see if there was another always up to date unique number here, i just know this one works :P)

[mzolotukhin]

Thanks, Daniel! A fix for IDF was posted for review in D46646. If that fix is accepted, we should no longer need the current patch. Also, we should be able to remove blocks sorting from MemorySSA.

Michael

llvm/include/llvm/Transforms/Scalar/JumpThreading.h

class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> {
   bool HasGuards = false;
 #ifdef NDEBUG
   SmallPtrSet<const BasicBlock *, 16> LoopHeaders;
 #else
   SmallSet<AssertingVH<const BasicBlock>, 16> LoopHeaders;
 #endif
   DenseSet<std::pair<Value *, BasicBlock *>> RecursionSet;
 
+  DenseMap<const BasicBlock *, unsigned int> BBNumbers;
+
   unsigned BBDupThreshold;
 
   // RAII helper for updating the recursion stack.
   struct RecursionSetRemover {
     DenseSet<std::pair<Value *, BasicBlock *>> &TheSet;
     std::pair<Value *, BasicBlock *> ThePair;
 
     RecursionSetRemover(DenseSet<std::pair<Value *, BasicBlock *>> &S,

llvm/include/llvm/Transforms/Utils/SSAUpdaterBulk.h

public:
   /// Return true if the SSAUpdater already has a value for the specified
   /// variable in the specified block.
   bool HasValueForBlock(unsigned Var, BasicBlock *BB);
 
   /// Perform all the necessary updates, including new PHI-nodes insertion and
   /// 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<PHINode *> *InsertedPHIs = nullptr);
+  void
+  RewriteAllUses(DominatorTree *DT,
+                 const DenseMap<const BasicBlock *, unsigned int> &BBNumbers,
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_SSAUPDATERBULK_H

llvm/lib/Transforms/Scalar/JumpThreading.cpp

 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.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 "llvm/Transforms/Utils/SSAUpdater.h"
+#include "llvm/Transforms/Utils/SSAUpdaterBulk.h"
 #include "llvm/Transforms/Utils/ValueMapper.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <iterator>
 #include <memory>
 #include <utility>
bool JumpThreadingPass::runImpl(Function &F, TargetLibraryInfo *TLI_,
   auto *GuardDecl = F.getParent()->getFunction(
       Intrinsic::getName(Intrinsic::experimental_guard));
   HasGuards = GuardDecl && !GuardDecl->use_empty();
   if (HasProfileData) {
     BPI = std::move(BPI_);
     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<BasicBlock *, 16> Unreachable;
   DominatorTree &DT = DDT->flush();
   for (auto &BB : F)
     if (!DT.isReachableFromEntry(&BB))
       Unreachable.insert(&BB);
 
bool JumpThreadingPass::ThreadEdge(BasicBlock *BB,
   // an unconditional jump to SuccBB.  Insert the unconditional jump.
   BranchInst *NewBI = BranchInst::Create(SuccBB, NewBB);
   NewBI->setDebugLoc(BB->getTerminator()->getDebugLoc());
 
   // Check to see if SuccBB has PHI nodes. If so, we need to add entries to the
   // 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<Use*, 16> UsesToRename;
+  SSAUpdaterBulk SSAUpdate;
+
   for (Instruction &I : *BB) {
+    SmallVector<Use*, 16> 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<Instruction>(U.getUser());
       if (PHINode *UserPN = dyn_cast<PHINode>(User)) {
-        if (UserPN->getIncomingBlock(U) == BB)
+        if (UserPN->getIncomingBlock(U) == BB ||
+            UserPN->getIncomingBlock(U) == PredBB)
           continue;
       } else if (User->getParent() == BB)
         continue;
 
       UsesToRename.push_back(&U);
     }
 
     // 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");
-  }
-
-  // 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);
-    }
+    // 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);
 
   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.
   SimplifyInstructionsInBlock(NewBB, TLI);
 
   // Update the edge weight from BB to SuccBB, which should be less than before.
   UpdateBlockFreqAndEdgeWeight(PredBB, BB, NewBB, SuccBB);
 

llvm/lib/Transforms/Utils/SSAUpdaterBulk.cpp

for (BasicBlock *P : PredCache.get(BB)) {
       // Otherwise it is, add to the worklist.
       LiveInBlockWorklist.push_back(P);
     }
   }
 }
 
 /// Perform all the necessary updates, including new PHI-nodes insertion and the
 /// requested uses update.
-void SSAUpdaterBulk::RewriteAllUses(DominatorTree *DT,
-                                    SmallVectorImpl<PHINode *> *InsertedPHIs) {
+void SSAUpdaterBulk::RewriteAllUses(
+    DominatorTree *DT,
+    const DenseMap<const BasicBlock *, unsigned int> &BBNumbers,
   for (auto &R : Rewrites) {
     // Compute locations for new phi-nodes.
     // For that we need to initialize DefBlocks from definitions in R.Defines,
     // UsingBlocks from uses in R.Uses, then compute LiveInBlocks, and then use
     // this set for computing iterated dominance frontier (IDF).
     // The IDF blocks are the blocks where we need to insert new phi-nodes.
     ForwardIDFCalculator IDF(*DT);
     DEBUG(dbgs() << "SSAUpdater: rewriting " << R.Uses.size() << " use(s)\n");
 
     SmallPtrSet<BasicBlock *, 2> DefBlocks;
     for (auto &Def : R.Defines)
       DefBlocks.insert(Def.first);
     IDF.setDefiningBlocks(DefBlocks);
 
     SmallPtrSet<BasicBlock *, 2> UsingBlocks;
     for (Use *U : R.Uses)
       UsingBlocks.insert(getUserBB(U));
 
     SmallVector<BasicBlock *, 32> IDFBlocks;
     SmallPtrSet<BasicBlock *, 32> LiveInBlocks;
     ComputeLiveInBlocks(UsingBlocks, DefBlocks, LiveInBlocks, PredCache);
     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<PHINode *, 4> InsertedPHIsForVar;
     for (auto *FrontierBB : IDFBlocks) {
       IRBuilder<> B(FrontierBB, FrontierBB->begin());
       PHINode *PN = B.CreatePHI(R.Ty, 0, R.Name);
       R.Defines[FrontierBB] = PN;
       InsertedPHIsForVar.push_back(PN);

llvm/unittests/Transforms/Utils/SSAUpdaterBulk.cpp

TEST(SSAUpdaterBulk, SimpleMerge) {
   //     %7 = add i32 %2, %4
   //     %8 = sub i32 %2, %4
   Argument *FirstArg = &*(F->arg_begin());
   BasicBlock *IfBB = BasicBlock::Create(C, "if", F);
   BasicBlock *TrueBB = BasicBlock::Create(C, "true", F);
   BasicBlock *FalseBB = BasicBlock::Create(C, "false", F);
   BasicBlock *MergeBB = BasicBlock::Create(C, "merge", F);
 
+  DenseMap<const BasicBlock *, unsigned int> BBNumbers;
+  unsigned NextBBNum = 0;
+  for (auto &BB : *F)
+    BBNumbers[&BB] = NextBBNum++;
+
   B.SetInsertPoint(IfBB);
   B.CreateCondBr(B.getTrue(), TrueBB, FalseBB);
 
   B.SetInsertPoint(TrueBB);
   Value *AddOp1 = B.CreateAdd(FirstArg, ConstantInt::get(I32Ty, 1));
   Value *SubOp1 = B.CreateSub(FirstArg, ConstantInt::get(I32Ty, 2));
   B.CreateBr(MergeBB);
 
TEST(SSAUpdaterBulk, SimpleMerge) {
 
   VarNum = Updater.AddVariable("b", I32Ty);
   Updater.AddAvailableValue(VarNum, TrueBB, SubOp1);
   Updater.AddAvailableValue(VarNum, FalseBB, SubOp2);
   Updater.AddUse(VarNum, &I3->getOperandUse(0));
   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<PHINode>(I1->getOperand(0));
   EXPECT_NE(UpdatePhiA, nullptr);
   EXPECT_EQ(UpdatePhiA->getIncomingValueForBlock(TrueBB), AddOp1);
   EXPECT_EQ(UpdatePhiA->getIncomingValueForBlock(FalseBB), AddOp2);
   EXPECT_EQ(UpdatePhiA, dyn_cast_or_null<PHINode>(I1->getOperand(0)));
 
TEST(SSAUpdaterBulk, Irreducible) {
   //     afterloop:
   //       %4 = add i32 %2, 4
   //       ret i32 %0
   Argument *FirstArg = &*F->arg_begin();
   BasicBlock *IfBB = BasicBlock::Create(C, "if", F);
   BasicBlock *LoopStartBB = BasicBlock::Create(C, "loopstart", F);
   BasicBlock *LoopMainBB = BasicBlock::Create(C, "loopmain", F);
   BasicBlock *AfterLoopBB = BasicBlock::Create(C, "afterloop", F);
+  DenseMap<const BasicBlock *, unsigned int> BBNumbers;
+  unsigned NextBBNum = 0;
+  for (auto &BB : *F)
+    BBNumbers[&BB] = NextBBNum++;
 
   B.SetInsertPoint(IfBB);
   Value *AddOp1 = B.CreateAdd(FirstArg, ConstantInt::get(I32Ty, 1));
   B.CreateCondBr(B.getTrue(), LoopMainBB, LoopStartBB);
 
   B.SetInsertPoint(LoopStartBB);
   Value *AddOp2 = B.CreateAdd(FirstArg, ConstantInt::get(I32Ty, 2));
   B.CreateBr(LoopMainBB);
TEST(SSAUpdaterBulk, Irreducible) {
   // Add use in the return instruction.
   VarNum = Updater.AddVariable("a", I32Ty);
   Updater.AddAvailableValue(VarNum, &F->getEntryBlock(), FirstArg);
   Updater.AddUse(VarNum, &Return->getOperandUse(0));
 
   // Save all inserted phis into a vector.
   SmallVector<PHINode *, 8> 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);
 
   // I1 and Return should use the same values as they used before.
   EXPECT_EQ(I1->getOperand(0), AddOp1);
   EXPECT_EQ(Return->getOperand(0), FirstArg);
 
   // I2 should use the new phi.
   PHINode *UpdatePhi = dyn_cast_or_null<PHINode>(I2->getOperand(0));
   EXPECT_NE(UpdatePhi, nullptr);
   EXPECT_EQ(UpdatePhi->getIncomingValueForBlock(LoopStartBB), AddOp2);
   EXPECT_EQ(UpdatePhi->getIncomingValueForBlock(IfBB), UndefValue::get(I32Ty));
 }