[SDA] Bug fix: Use IPD outside the loop as divergence bound

[simoll]

Summary

The immediate post dominator of the loop header may be part of the divergent loop.
Since this /was/ the divergence propagation bound the SDA would not detect joins of divergent paths outside the loop.

[simoll]

Adding more DA users as subscribers

[simoll]

Ping. This is a bug fix for the SDA.

[nhaehnle]

Oh wow. That's an important fix indeed :) LGTM

lib/Analysis/SyncDependenceAnalysis.cpp

200

Spurious whitespace

223–224

Here as well.

[simoll]

NFC. Stripped empty lines.

If this looks ok, feel free to commit (i do not have commit access. Who should i ask to get it, btw?).

[nhaehnle]

Committed. I believe the procedure for SVN access is still that you send Chris Lattner an email to ask about it.

lib/Analysis/SyncDependenceAnalysis.cpp

void visitSuccessor(const BasicBlock &SuccBlock, const Loop *ParentLoop,
     auto ItLastDef = DefMap.find(&SuccBlock);
     if (ItLastDef == DefMap.end()) {
       addPending(SuccBlock, DefBlock);
       return;
     }
 
     // a join of at least two definitions
     if (ItLastDef->second != &DefBlock) {
       // do we know this join already?
       if (!JoinBlocks->insert(&SuccBlock).second)
         return;
 
       // update the definition
       addPending(SuccBlock, SuccBlock);
     }
   }
 
   // find all blocks reachable by two disjoint paths from @rootTerm.
   // This method works for both divergent terminators and loops with
   // divergent exits.
   // @rootBlock is either the block containing the branch or the header of the
   // 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) {
+                    SuccessorIterable NodeSuccessors, const Loop *ParentLoop, const BasicBlock * PdBoundBlock) {
     assert(JoinBlocks);
 
-    // immediate post dominator (no join block beyond that block)
-    const auto *PdNode = PDT.getNode(const_cast<BasicBlock *>(&RootBlock));
-    const auto *IpdNode = PdNode->getIDom();
-    const auto *PdBoundBlock = IpdNode ? IpdNode->getBlock() : nullptr;
-
     // 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 {
const ConstBlockSet &SyncDependenceAnalysis::join_blocks(const Loop &Loop) {
   LoopExitVec LoopExits;
   Loop.getExitBlocks(LoopExits);
   if (LoopExits.size() < 1) {
     return EmptyBlockSet;
   }
 
   // already available in cache?
   auto ItCached = CachedLoopExitJoins.find(&Loop);
-  if (ItCached != CachedLoopExitJoins.end())
+  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());
+      *Loop.getHeader(), LoopExits, Loop.getParentLoop(), PdBoundBlock);
 
   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));
+      TermBlock, successors(Term.getParent()), LI.getLoopFor(&TermBlock), PdBoundBlock);
 
   auto ItInserted = CachedBranchJoins.emplace(&Term, std::move(JoinBlocks));
   assert(ItInserted.second);
   return *ItInserted.first->second;
 }
 
 } // namespace llvm

test/Analysis/DivergenceAnalysis/AMDGPU/hidden_diverge.ll

 ; CHECK: DIVERGENT: %phi.var.hidden = phi i32
   br label %merge
 merge:
   %phi.ipd = phi i32 [ %a, %B ], [ %b, %C ]
 ; CHECK: DIVERGENT: %phi.ipd = phi i32
   ret void
 }
 
+define amdgpu_kernel void @hidden_loop_ipd(i32 %n, i32 %a, i32 %b) #0 {
+; CHECK-LABEL: Printing analysis 'Legacy Divergence Analysis' for function 'hidden_loop_ipd'
+entry:
+  %tid = call i32 @llvm.amdgcn.workitem.id.x()
+  %cond.var = icmp slt i32 %tid, 0
+; CHECK: DIVERGENT: %cond.var = icmp
+  %cond.uni = icmp slt i32 %n, 0
+; CHECK-NOT: DIVERGENT: %cond.uni = icmp
+  br label %for.header
+for.header:
+  br i1 %cond.var, label %A, label %B
+A:
+  br label %C
+B:
+  br label %C
+C:
+  br i1 %cond.uni, label %E, label %D
+D:
+  br i1 %cond.var, label %for.header, label %F
+
+E:
+  %e.lcssa.uni = phi i32 [ 0, %C ]
+; CHECK-NOT: DIVERGENT: %e.lcssa.uni = phi i32
+  br label %G
+
+F:
+  %f.lcssa.uni = phi i32 [ 1, %D ]
+; CHECK-NOT: DIVERGENT: %f.lcssa.uni = phi i32
+  br label %G
+
+G:
+  %g.join.var = phi i32 [ %e.lcssa.uni, %E ], [ %f.lcssa.uni, %F ]
+; CHECK: DIVERGENT: %g.join.var = phi i32
+  ret void
+}
+
+
 declare i32 @llvm.amdgcn.workitem.id.x() #0
 
 attributes #0 = { nounwind readnone }