[SDA] Don't stop divergence propagation at the IPD.

[simoll]

Summary

This fixes B42473 and B42706.

This patch makes the SDA propagate branch divergence until the end of the RPO traversal. Before, the SyncDependenceAnalysis propagated divergence only until the IPD in rpo order. RPO is incompatible with post dominance in the presence of loops. This made the SDA crash because blocks were missed in the propagation.

[nhaehnle]

This needs a test. It should be possible to extract one from the bug reports?

[foad]

I can confirm that this fixes the original test case that I had, that I reduced into bug 42706, and it doesn't seem to cause any other problems in my other test cases.

[simoll]

Added b42473 r1.ll as a test case (failing assert on missing def at loop header).

[simoll]

Merged commits in preparation for landing

[foad]

Ping! @simoll are you ready to land this now?

[simoll]

@foad Sorry for the delay. Feel free to commit on my behalf (i have been granted commit access but haven't found the time to set it up yet).

lib/Analysis/SyncDependenceAnalysis.cpp

struct DivergencePropagator {
   // divergent loop.
   // @nodeSuccessors is the set of successors of the node (Loop or Terminator)
   // headed by @rootBlock.
   // @parentLoop is the parent loop of the Loop or the loop that contains the
   // Terminator.
   template <typename SuccessorIterable>
   std::unique_ptr<ConstBlockSet>
   computeJoinPoints(const BasicBlock &RootBlock,
-                    SuccessorIterable NodeSuccessors, const Loop *ParentLoop, const BasicBlock * PdBoundBlock) {
+                    SuccessorIterable NodeSuccessors, const Loop *ParentLoop) {
     assert(JoinBlocks);
 
+    LLVM_DEBUG(dbgs() << "SDA:computeJoinPoints. Parent loop: " << (ParentLoop ? ParentLoop->getName() : "<null>") << "\n" );
+
     // bootstrap with branch targets
     for (const auto *SuccBlock : NodeSuccessors) {
       DefMap.emplace(SuccBlock, SuccBlock);
 
       if (ParentLoop && !ParentLoop->contains(SuccBlock)) {
         // immediate loop exit from node.
         ReachedLoopExits.insert(SuccBlock);
-        continue;
       } else {
         // regular successor
         PendingUpdates.insert(SuccBlock);
       }
     }
 
+    LLVM_DEBUG(
+      dbgs() << "SDA: rpo order:\n";
+      for (const auto * RpoBlock : FuncRPOT) {
+        dbgs() << "- " << RpoBlock->getName() << "\n";
+      }
+    );
+
     auto ItBeginRPO = FuncRPOT.begin();
 
     // skip until term (TODO RPOT won't let us start at @term directly)
     for (; *ItBeginRPO != &RootBlock; ++ItBeginRPO) {}
 
     auto ItEndRPO = FuncRPOT.end();
     assert(ItBeginRPO != ItEndRPO);
 
     // propagate definitions at the immediate successors of the node in RPO
     auto ItBlockRPO = ItBeginRPO;
-    while (++ItBlockRPO != ItEndRPO && *ItBlockRPO != PdBoundBlock) {
+    while ((++ItBlockRPO != ItEndRPO) &&
+           !PendingUpdates.empty()) {
       const auto *Block = *ItBlockRPO;
+      LLVM_DEBUG(dbgs() << "SDA::joins. visiting " << Block->getName() << "\n");
 
-      // skip @block if not pending update
+      // skip Block if not pending update
       auto ItPending = PendingUpdates.find(Block);
       if (ItPending == PendingUpdates.end())
         continue;
       PendingUpdates.erase(ItPending);
 
-      // propagate definition at @block to its successors
+      // propagate definition at Block to its successors
       auto ItDef = DefMap.find(Block);
       const auto *DefBlock = ItDef->second;
       assert(DefBlock);
 
       auto *BlockLoop = LI.getLoopFor(Block);
       if (ParentLoop &&
           (ParentLoop != BlockLoop && ParentLoop->contains(BlockLoop))) {
         // if the successor is the header of a nested loop pretend its a
         // single node with the loop's exits as successors
         SmallVector<BasicBlock *, 4> BlockLoopExits;
         BlockLoop->getExitBlocks(BlockLoopExits);
         for (const auto *BlockLoopExit : BlockLoopExits) {
           visitSuccessor(*BlockLoopExit, ParentLoop, *DefBlock);
         }
 
       } else {
         // the successors are either on the same loop level or loop exits
         for (const auto *SuccBlock : successors(Block)) {
           visitSuccessor(*SuccBlock, ParentLoop, *DefBlock);
         }
       }
     }
 
+    LLVM_DEBUG(dbgs() << "SDA::joins. After propagation:\n"; printDefs(dbgs()));
+
     // We need to know the definition at the parent loop header to decide
     // whether the definition at the header is different from the definition at
     // the loop exits, which would indicate a divergent loop exits.
     //
     // A // loop header
     // |
     // B // nested loop header
     // |
     // C -> X (exit from B loop) -..-> (A latch)
     // |
     // D -> back to B (B latch)
     // |
     // proper exit from both loops
     //
-    // D post-dominates B as it is the only proper exit from the "A loop".
-    // If C has a divergent branch, propagation will therefore stop at D.
-    // That implies that B will never receive a definition.
-    // But that definition can only be the same as at D (D itself in thise case)
-    // because all paths to anywhere have to pass through D.
-    //
+    // analyze reached loop exits
+    if (!ReachedLoopExits.empty()) {
       const BasicBlock *ParentLoopHeader =
           ParentLoop ? ParentLoop->getHeader() : nullptr;
-    if (ParentLoop && ParentLoop->contains(PdBoundBlock)) {
-      DefMap[ParentLoopHeader] = DefMap[PdBoundBlock];
-    }
 
-    // analyze reached loop exits
-    if (!ReachedLoopExits.empty()) {
       assert(ParentLoop);
-      const auto *HeaderDefBlock = DefMap[ParentLoopHeader];
+      auto ItHeaderDef = DefMap.find(ParentLoopHeader);
+      const auto *HeaderDefBlock = (ItHeaderDef == DefMap.end()) ? nullptr : ItHeaderDef->second;
+
       LLVM_DEBUG(printDefs(dbgs()));
-      assert(HeaderDefBlock && "no definition in header of carrying loop");
+      assert(HeaderDefBlock && "no definition at header of carrying loop");
 
       for (const auto *ExitBlock : ReachedLoopExits) {
         auto ItExitDef = DefMap.find(ExitBlock);
         assert((ItExitDef != DefMap.end()) &&
                "no reaching def at reachable loop exit");
         if (ItExitDef->second != HeaderDefBlock) {
           JoinBlocks->insert(ExitBlock);
         }
const ConstBlockSet &SyncDependenceAnalysis::join_blocks(const Loop &Loop) {
   }
 
   // already available in cache?
   auto ItCached = CachedLoopExitJoins.find(&Loop);
   if (ItCached != CachedLoopExitJoins.end()) {
     return *ItCached->second;
   }
 
-  // dont propagte beyond the immediate post dom of the loop
-  const auto *PdNode = PDT.getNode(const_cast<BasicBlock *>(Loop.getHeader()));
-  const auto *IpdNode = PdNode->getIDom();
-  const auto *PdBoundBlock = IpdNode ? IpdNode->getBlock() : nullptr;
-  while (PdBoundBlock && Loop.contains(PdBoundBlock)) {
-    IpdNode = IpdNode->getIDom();
-    PdBoundBlock = IpdNode ? IpdNode->getBlock() : nullptr;
-  }
-
   // compute all join points
   DivergencePropagator Propagator{FuncRPOT, DT, PDT, LI};
   auto JoinBlocks = Propagator.computeJoinPoints<const LoopExitVec &>(
-      *Loop.getHeader(), LoopExits, Loop.getParentLoop(), PdBoundBlock);
+      *Loop.getHeader(), LoopExits, Loop.getParentLoop());
 
   auto ItInserted = CachedLoopExitJoins.emplace(&Loop, std::move(JoinBlocks));
   assert(ItInserted.second);
   return *ItInserted.first->second;
 }
 
 const ConstBlockSet &
 SyncDependenceAnalysis::join_blocks(const Instruction &Term) {
   // trivial case
   if (Term.getNumSuccessors() < 1) {
     return EmptyBlockSet;
   }
 
   // already available in cache?
   auto ItCached = CachedBranchJoins.find(&Term);
   if (ItCached != CachedBranchJoins.end())
     return *ItCached->second;
 
-  // dont propagate beyond the immediate post dominator of the branch
-  const auto *PdNode = PDT.getNode(const_cast<BasicBlock *>(Term.getParent()));
-  const auto *IpdNode = PdNode->getIDom();
-  const auto *PdBoundBlock = IpdNode ? IpdNode->getBlock() : nullptr;
-
   // compute all join points
   DivergencePropagator Propagator{FuncRPOT, DT, PDT, LI};
   const auto &TermBlock = *Term.getParent();
   auto JoinBlocks = Propagator.computeJoinPoints<succ_const_range>(
-      TermBlock, successors(Term.getParent()), LI.getLoopFor(&TermBlock), PdBoundBlock);
+      TermBlock, successors(Term.getParent()), LI.getLoopFor(&TermBlock));
 
   auto ItInserted = CachedBranchJoins.emplace(&Term, std::move(JoinBlocks));
   assert(ItInserted.second);
   return *ItInserted.first->second;
 }
 
 } // namespace llvm