From 509e2e953b0981a66cb58a45cb5a3070dff5fed5 Mon Sep 17 00:00:00 2001
From: Jingyue Wu <jingyue@google.com>
Date: Fri, 18 Dec 2015 21:44:26 +0000
Subject: [PATCH] [DivergenceAnalysis] fix a bug in computing influence regions

Fixes PR25864



git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@256036 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Analysis/DivergenceAnalysis.cpp           | 26 ++++++++++++++-----
 .../DivergenceAnalysis/NVPTX/diverge.ll       | 23 +++++++++++++++-
 2 files changed, 41 insertions(+), 8 deletions(-)

diff --git a/lib/Analysis/DivergenceAnalysis.cpp b/lib/Analysis/DivergenceAnalysis.cpp
index 93a288858ba..5ae6d74130a 100644
--- a/lib/Analysis/DivergenceAnalysis.cpp
+++ b/lib/Analysis/DivergenceAnalysis.cpp
@@ -96,7 +96,7 @@ private:
   // A helper function that explores sync dependents of TI.
   void exploreSyncDependency(TerminatorInst *TI);
   // Computes the influence region from Start to End. This region includes all
-  // basic blocks on any path from Start to End.
+  // basic blocks on any simple path from Start to End.
   void computeInfluenceRegion(BasicBlock *Start, BasicBlock *End,
                               DenseSet<BasicBlock *> &InfluenceRegion);
   // Finds all users of I that are outside the influence region, and add these
@@ -198,21 +198,33 @@ void DivergencePropagator::findUsersOutsideInfluenceRegion(
   }
 }
 
+// A helper function for computeInfluenceRegion that adds successors of "ThisBB"
+// to the influence region.
+static void
+addSuccessorsToInfluenceRegion(BasicBlock *ThisBB, BasicBlock *End,
+                               DenseSet<BasicBlock *> &InfluenceRegion,
+                               std::vector<BasicBlock *> &InfluenceStack) {
+  for (BasicBlock *Succ : successors(ThisBB)) {
+    if (Succ != End && InfluenceRegion.insert(Succ).second)
+      InfluenceStack.push_back(Succ);
+  }
+}
+
 void DivergencePropagator::computeInfluenceRegion(
     BasicBlock *Start, BasicBlock *End,
     DenseSet<BasicBlock *> &InfluenceRegion) {
   assert(PDT.properlyDominates(End, Start) &&
          "End does not properly dominate Start");
+
+  // The influence region starts from the end of "Start" to the beginning of
+  // "End". Therefore, "Start" should not be in the region unless "Start" is in
+  // a loop that doesn't contain "End".
   std::vector<BasicBlock *> InfluenceStack;
-  InfluenceStack.push_back(Start);
-  InfluenceRegion.insert(Start);
+  addSuccessorsToInfluenceRegion(Start, End, InfluenceRegion, InfluenceStack);
   while (!InfluenceStack.empty()) {
     BasicBlock *BB = InfluenceStack.back();
     InfluenceStack.pop_back();
-    for (BasicBlock *Succ : successors(BB)) {
-      if (End != Succ && InfluenceRegion.insert(Succ).second)
-        InfluenceStack.push_back(Succ);
-    }
+    addSuccessorsToInfluenceRegion(BB, End, InfluenceRegion, InfluenceStack);
   }
 }
 
diff --git a/test/Analysis/DivergenceAnalysis/NVPTX/diverge.ll b/test/Analysis/DivergenceAnalysis/NVPTX/diverge.ll
index 9dd3d557f8c..fc63038e77c 100644
--- a/test/Analysis/DivergenceAnalysis/NVPTX/diverge.ll
+++ b/test/Analysis/DivergenceAnalysis/NVPTX/diverge.ll
@@ -185,14 +185,35 @@ else:
   ret i32 1
 }
 
+; Verifies sync-dependence is computed correctly in the absense of loops.
+define i32 @sync_no_loop(i32 %arg) {
+entry:
+  %0 = add i32 %arg, 1
+  %tid = call i32 @llvm.nvvm.read.ptx.sreg.tid.x()
+  %1 = icmp sge i32 %tid, 10
+  br i1 %1, label %bb1, label %bb2
+
+bb1:
+  br label %bb3
+
+bb2:
+  br label %bb3
+
+bb3:
+  %2 = add i32 %0, 2
+  ; CHECK-NOT: DIVERGENT: %2
+  ret i32 %2
+}
+
 declare i32 @llvm.nvvm.read.ptx.sreg.tid.x()
 declare i32 @llvm.nvvm.read.ptx.sreg.tid.y()
 declare i32 @llvm.nvvm.read.ptx.sreg.tid.z()
 declare i32 @llvm.ptx.read.laneid()
 
-!nvvm.annotations = !{!0, !1, !2, !3, !4}
+!nvvm.annotations = !{!0, !1, !2, !3, !4, !5}
 !0 = !{i32 (i32, i32, i32)* @no_diverge, !"kernel", i32 1}
 !1 = !{i32 (i32, i32)* @sync, !"kernel", i32 1}
 !2 = !{i32 (i32, i32, i32)* @mixed, !"kernel", i32 1}
 !3 = !{i32 ()* @loop, !"kernel", i32 1}
 !4 = !{i32 (i1)* @unstructured_loop, !"kernel", i32 1}
+!5 = !{i32 (i32)* @sync_no_loop, !"kernel", i32 1}
-- 
2.34.1