DivergenceAnalysis: Fix crash with unreachable blocks

[arsenm]

Summary

Unreachable blocks may not be in the dominator tree, so don't crash on them.

[jingyue]

Thanks! I completely missed this case :(

lib/Analysis/DivergenceAnalysis.cpp

143

s/BBNode/ThisNode/

There are InfluenceBB and InfluenceNode below, so we'd better be explicit.

189

This seems unnecessary. ThisBB is guaranteed reachable according to the check you added above. InfluenceBB is guaranteed to dominate ThisBB, so it must be reachable too.

If you agree, maybe change this if to an assert.

[arsenm]

lib/Analysis/DivergenceAnalysis.cpp

189

I hit the first one, and then hit another crash here

[jingyue]

lib/Analysis/DivergenceAnalysis.cpp

189

Looking at your code more, the first check PDT.getNode doesn't really guard against unreachable basic blocks. You may want to use DT.getNode() or DT.isReachableFromEntry (I prefer the latter because it's more explicit) there. Then, I believe the second check here is unnecessary.

[arsenm]

Check isReachableFromEntry

[arsenm]

r268001

lib/Analysis/DivergenceAnalysis.cpp

void DivergencePropagator::exploreSyncDependency(TerminatorInst *TI) {
   // patterns. For example,
   //
   // if (tid < 5)
   //   a1 = 1;
   // else
   //   a2 = 2;
   // a = phi(a1, a2); // sync dependent on (tid < 5)
   BasicBlock *ThisBB = TI->getParent();
-  BasicBlock *IPostDom = PDT.getNode(ThisBB)->getIDom()->getBlock();
+
+  // Unreachable blocks may not be in the dominator tree.
+  DomTreeNode *BBNode = PDT.getNode(ThisBB);
+  if (!BBNode)
+    return;
+
+  BasicBlock *IPostDom = BBNode->getIDom()->getBlock();
   if (IPostDom == nullptr)
     return;
 
   for (auto I = IPostDom->begin(); isa<PHINode>(I); ++I) {
     // A PHINode is uniform if it returns the same value no matter which path is
     // taken.
     if (!cast<PHINode>(I)->hasConstantOrUndefValue() && DV.insert(&*I).second)
       Worklist.push_back(&*I);
void DivergencePropagator::exploreSyncDependency(TerminatorInst *TI) {
   // An insight that can speed up the search process is that all the in-region
   // values that are used outside must dominate TI. Therefore, instead of
   // searching every basic blocks in the influence region, we search all the
   // dominators of TI until it is outside the influence region.
   BasicBlock *InfluencedBB = ThisBB;
   while (InfluenceRegion.count(InfluencedBB)) {
     for (auto &I : *InfluencedBB)
       findUsersOutsideInfluenceRegion(I, InfluenceRegion);
-    DomTreeNode *IDomNode = DT.getNode(InfluencedBB)->getIDom();
+
+    DomTreeNode *InfluenceNode = DT.getNode(InfluencedBB);
+    if (!InfluenceNode)
+      break;
+
+    DomTreeNode *IDomNode = InfluenceNode->getIDom();
     if (IDomNode == nullptr)
       break;
     InfluencedBB = IDomNode->getBlock();
   }
 }
 
 void DivergencePropagator::findUsersOutsideInfluenceRegion(
     Instruction &I, const DenseSet<BasicBlock *> &InfluenceRegion) {

test/Analysis/DivergenceAnalysis/AMDGPU/unreachable-loop-block.ll

+; RUN: opt %s -mtriple amdgcn-- -analyze -divergence | FileCheck %s
+
+; CHECK: DIVERGENT:  %tmp = cmpxchg volatile
+define void @divergence_analysis_null_idom(i32 %tidx) #0 {
+entry:
+  unreachable
+
+unreachable_loop:                                        ; preds = %do.body.i, %if.then11
+  %tmp = cmpxchg volatile i32 addrspace(1)* null, i32 0, i32 0 seq_cst seq_cst
+  %cmp.i = extractvalue { i32, i1 } %tmp, 1
+  br i1 %cmp.i, label %unreachable_loop, label %end
+
+end:                                      ; preds = %do.body.i51, %atomicAdd_g_f.exit
+  unreachable
+}
+
+attributes #0 = { norecurse nounwind }