[LLVM][Uniformity] Fix error causing assert on some irreducible control flow

[AlexM]

Summary

As the test case demonstrates, it is possible for a block to be identified as a
join point while not being the header of a reducible cycle. To address this,
when searching for the outermost cycle made divergent by branch outside it, we
first check for an irreducible outermost cycle before checking if the parent is
reducible.

[AlexM]

cleanup test case

[sameerds]

llvm/include/llvm/ADT/GenericUniformityImpl.h

950

We shouldn't remove the assert. Instead, this whole "if block" should be moved after the while loop below.

The reasoning is like this: When divergent paths enter an irreducible cycle, we assume that everything inside the cycle is divergent. But the way ModifiedPO works, every block inside the cycle gets marked as a join block. This is okay, because the exits get labelled as themselves which allows the traversal to find actual joins outside (or beyond) the cycle.

So when we want to check a join block inside a cycle C relative to a divergent branch outside of C, we should first check if there is an irreducible parent of C that does not contain the branch. If there is such a parent, then whether C is reducible is not relevant. If there is no irreducible parent, then we can check if C is reducible.

Returning early like the current code, by just checking the parent cycle looks like a bug because it fails to return the irreducible parent as the "cycle made divergent". But other join blocks in the irreducible parent will cause it to be eventually reported, so it's okay.

[AlexM]

Address comment; move if below while loop.

[AlexM]

Okay, makes sense. I've updated as suggested.

[sameerds]

Can you please reword the change description? Rather than talking about the code in terms of if/while, it's more helpful to talk about what is happening. For example, "we should first check for an irreducible outermost cycle before checking if the parent is reducible".

[AlexM]

Okay, I've updated the description, @sameerds could you please submit this on my behalf?

[sameerds]

@AlexM FYI: submitted a different fix in the same location: 4d081560cd3b6ac114aee15f50480dd978b55a44

llvm/include/llvm/ADT/GenericUniformityImpl.h

static const CycleT *getExtDivCycle(const CycleT *Cycle,
                                     const BlockT *DivTermBlock,
                                     const BlockT *JoinBlock) {
   assert(Cycle);
   assert(Cycle->contains(JoinBlock));
 
   if (Cycle->contains(DivTermBlock))
     return nullptr;
 
-  if (Cycle->isReducible()) {
-    assert(Cycle->getHeader() == JoinBlock);
-    return nullptr;
-  }
-
   const auto *Parent = Cycle->getParentCycle();
   while (Parent && !Parent->contains(DivTermBlock)) {
     // If the join is inside a child, then the parent must be
     // irreducible. The only join in a reducible cyle is its own
     // header.
     assert(!Parent->isReducible());
     Cycle = Parent;
     Parent = Cycle->getParentCycle();
   }
 
+  if (Cycle->isReducible()) {
+    assert(Cycle->getHeader() == JoinBlock);
+    return nullptr;
+  }
+
   LLVM_DEBUG(dbgs() << "cycle made divergent by external branch\n");
   return Cycle;
 }
 
 /// Return the outermost cycle made divergent by branch inside it.
 ///
 /// This checks the "diverged entry" criterion defined in the
 /// docs/ConvergenceAnalysis.html.

llvm/test/Analysis/UniformityAnalysis/NVPTX/non-header-join.ll

+; RUN: opt %s -passes='print<uniformity>' -disable-output 2>&1 | FileCheck %s
+
+target datalayout = "e-i64:64-v16:16-v32:32-n16:32:64"
+target triple = "nvptx64-nvidia-cuda"
+
+; CHECK: CYCLES ASSSUMED DIVERGENT:
+; CHECK-NEXT: depth=1: entries(if.end16 for.cond1) for.body4
+
+define void @foo(i1 %b) {
+entry:
+  br i1 %b, label %if.then, label %if.end16
+
+if.then:                                          ; preds = %entry
+  br label %for.cond1
+
+for.cond1:                                        ; preds = %if.end16, %for.body4, %if.then
+  br i1 false, label %for.body4, label %if.end16
+
+for.body4:                                        ; preds = %for.cond1
+  br label %for.cond1
+
+if.end16:                                         ; preds = %for.cond1, %entry
+  br label %for.cond1
+}