[DA] propagate loop live-out values that get used in a branch

[sameerds]

Summary

Values that are uniform within a loop but appear divergent to uses
outside the loop are "tainted" so that such uses are marked
divergent. But if such a use is a branch, then it's divergence needs
to be propagated. The simplest way to do that is to put the branch
back in the main worklist so that it is processed appropriately.

[foad]

llvm/lib/Analysis/DivergenceAnalysis.cpp

111–114

I think it might be cleaner to put this in compute just before the call to updateTerminator. It feels wrong to make updateTerminator non-const, and the relationship between Worklist and DeferredTerminators seems clearer if instructions are removed from them in the same place, in compute. But I'll happily defer to others who are more familiar with this code.

[sameerds]

llvm/lib/Analysis/DivergenceAnalysis.cpp

111–114

Yeah, I was torn between what you describe and what is seen here in the patch. I don't have a strong opinion either way, so I just picked one. In its defense, the current version keeps the "detail" out of compute ... membership in the deferred set is just one of the criteria to decide whether to update the terminator. But I can see why removing the const is not palatable.

One way to balance both sides is to move the erase operation to propagateBranchDivergence, which is where the terminator is marked divergent anyway. This nicely separates the readonly part from the modify part.

[simoll]

You could short cut this by calling propagateBranchDivergence right away instead of using DeferredTerminators (and mark the terminator as divergent). That's in the same spirit as calling pushUsers on a regular instruction since sync dependence is just a different kind of dependence.

[sameerds]

eliminate DeferredTerminators; also a small refactor for readability

[simoll]

LGTM. Thanks!

llvm/lib/Analysis/DivergenceAnalysis.cpp

void DivergenceAnalysis::markDivergent(const Value &DivVal) {
   DivergentValues.insert(&DivVal);
 }
 
 void DivergenceAnalysis::addUniformOverride(const Value &UniVal) {
   UniformOverrides.insert(&UniVal);
 }
 
 bool DivergenceAnalysis::updateTerminator(const Instruction &Term) const {
   if (Term.getNumSuccessors() <= 1)
     return false;
   if (auto *BranchTerm = dyn_cast<BranchInst>(&Term)) {
     assert(BranchTerm->isConditional());
     return isDivergent(*BranchTerm->getCondition());
   }
   if (auto *SwitchTerm = dyn_cast<SwitchInst>(&Term)) {
     return isDivergent(*SwitchTerm->getCondition());
   }
   if (isa<InvokeInst>(Term)) {
     return false; // ignore abnormal executions through landingpad
   }

 bool DivergenceAnalysis::inRegion(const Instruction &I) const {
   return I.getParent() && inRegion(*I.getParent());
 }
 
 bool DivergenceAnalysis::inRegion(const BasicBlock &BB) const {
   return (!RegionLoop && BB.getParent() == &F) || RegionLoop->contains(&BB);
 }
 
+static bool usesLiveOut(const Instruction &I, const Loop *DivLoop) {
+  for (auto &Op : I.operands()) {
+    auto *OpInst = dyn_cast<Instruction>(&Op);
+    if (!OpInst)
+      continue;
+    if (DivLoop->contains(OpInst->getParent()))
+      return true;
+  }
+  return false;
+}
+
 // marks all users of loop-carried values of the loop headed by LoopHeader as
 // divergent
 void DivergenceAnalysis::taintLoopLiveOuts(const BasicBlock &LoopHeader) {
   auto *DivLoop = LI.getLoopFor(&LoopHeader);
   assert(DivLoop && "loopHeader is not actually part of a loop");
 
   SmallVector<BasicBlock *, 8> TaintStack;
   DivLoop->getExitBlocks(TaintStack);
while (!TaintStack.empty()) {
     }
 
     // taint outside users of values carried by DivLoop
     for (auto &I : *UserBlock) {
       if (isAlwaysUniform(I))
         continue;
       if (isDivergent(I))
         continue;
-
-      for (auto &Op : I.operands()) {
-        auto *OpInst = dyn_cast<Instruction>(&Op);
-        if (!OpInst)
-          continue;
-        if (DivLoop->contains(OpInst->getParent())) {
-          markDivergent(I);
-          pushUsers(I);
-          break;
-        }
+      if (!usesLiveOut(I, DivLoop))
+
+      if (I.isTerminator()) {
+        propagateBranchDivergence(I);
+      } else {
       }
     }
 
     // visit all blocks in the dominance region
     for (auto *SuccBlock : successors(UserBlock)) {
       if (!Visited.insert(SuccBlock).second) {
         continue;
       }

llvm/test/Analysis/DivergenceAnalysis/AMDGPU/propagate-loop-live-out.ll

+; RUN: opt -mtriple amdgcn-unknown-amdhsa -analyze -divergence -use-gpu-divergence-analysis %s | FileCheck %s
+
+; CHECK: bb6:
+; CHECK: DIVERGENT:       %.126.i355.i = phi i1 [ false, %bb5 ], [ true, %bb4 ]
+; CHECK: DIVERGENT:       br i1 %.126.i355.i, label %bb7, label %bb8
+
+; Function Attrs: nounwind readnone speculatable
+declare i32 @llvm.amdgcn.workitem.id.x() #0
+
+define protected amdgpu_kernel void @_Z23krnl_GPUITSFitterKerneli() {
+bb0:
+  %i4 = call i32 @llvm.amdgcn.workitem.id.x()
+  %i5 = icmp eq i32 %i4, -1
+  br label %bb1
+
+bb1:                                              ; preds = %bb3, %bb0
+  %lsr.iv = phi i32 [ %i1, %bb3 ], [ 7, %bb0 ]
+  br i1 %i5, label %bb2, label %bb3
+
+bb2:                                              ; preds = %bb1
+  %lsr.iv.next = add nsw i32 %lsr.iv, -1
+  %i14 = icmp eq i32 %lsr.iv.next, 0
+  br label %bb3
+
+bb3:                                              ; preds = %bb2, %bb1
+  %i1 = phi i32 [ %lsr.iv.next, %bb2 ], [ 0, %bb1 ]
+  %i2 = phi i1 [ false, %bb2 ], [ true, %bb1 ]
+  %i3 = phi i1 [ %i14, %bb2 ], [ true, %bb1 ]
+  br i1 %i3, label %bb4, label %bb1
+
+bb4:                                              ; preds = %bb3
+  br i1 %i2, label %bb5, label %bb6
+
+bb5:                                              ; preds = %bb4
+  br label %bb6
+
+bb6:                                              ; preds = %bb5, %bb4
+  %.126.i355.i = phi i1 [ false, %bb5 ], [ true, %bb4 ]
+  br i1 %.126.i355.i, label %bb7, label %bb8
+
+bb7:                                              ; preds = %bb6
+  br label %bb8
+
+bb8:                                              ; preds = %bb7, %bb6
+  ret void
+}
+
+attributes #0 = { nounwind readnone speculatable }