StructurizeCFG: Test for branch divergence correctly

[nhaehnle]

Summary

This fixes cases like the new test @nonuniform. In that test, %cc itself
is a uniform value; however, when reading it after the end of the loop in
basic block %if, its value is effectively non-uniform.

This problem was encountered in
https://bugs.freedesktop.org/show_bug.cgi?id=103743; however, this change
in itself is not sufficient to fix that bug, as there is another issue
in the AMDGPU backend.

Change-Id: I32bbffece4a32f686fab54964dae1a5dd72949d4

[arsenm]

lib/Transforms/Scalar/StructurizeCFG.cpp

253 ↗

(On Diff #124542)

I think the flag should override the pass argument if explicitly specified. I think other passes do something like if .getNumOccurrences() > 0 use the flag ...

test/Transforms/StructurizeCFG/uniform-regions.ll

1 ↗

(On Diff #124542)

The -mtriple should be dropped. If it's needed, you should create an AMDGPU specific test subdirectory in StructurizeCFG

[alex-t]

In general looks correct to me. You definitely should check the branch itself - not the condition.
In your case (divergent loop-exit) branch itself is divergent because of the control dependency.

include/llvm/Analysis/DivergenceAnalysis.h

40 ↗

(On Diff #124542)

Comment is not necessary. By definition:

instruction produces uniform result if and only if all it's operands are uniform and all the branches it control depend of are uniform.

This comment assume that the person who uses Divergence Analysis has no idea of what it is.

46 ↗

(On Diff #124542)

Same as above

test/Transforms/StructurizeCFG/uniform-regions.ll

34 ↗

(On Diff #124542)

This is misleading. I can guess that using %v in the comparison means that branch condition is divergent.
Nevertheless, I think that it's more clear if you explicitly use the divergent definition for %v.
like:

%v = call i32 @llvm.amdgcn.workitem.id.x()

[nhaehnle]

Address review comments:

• command line flag can also force-disable
• move uniform-region.ll test into AMDGPU subdirectory
• use llvm.amdgcn.workitem.id.x

[arsenm]

test/Transforms/StructurizeCFG/AMDGPU/uniform-regions.ll

1 ↗

(On Diff #131600)

I think we should start using update_test_checks for any structurer tests

[nhaehnle]

Use update_test_checks

[nhaehnle]

include/llvm/Analysis/DivergenceAnalysis.h

40 ↗

(On Diff #124542)

Strongly disagree. This is the header/interface file, and the definition you cite appears nowhere in the code, so the comment is valuable. To elaborate:

This comment assume that the person who uses Divergence Analysis has no idea of what it is.

Kind of, though I would rather say: the comment assumes that the person who uses DivergenceAnalysis has no experience with it, and that is entirely fair. Actually, I'd say the mere existence of this patch is evidence that the comment makes sense.

You see, this patch fixes a bug in StructurizeCFG, which only uses divergence analysis optionally, and may be used by targets where divergence is not an issue. So it is entirely reasonable that a person who has no experience at all with DivergenceAnalysis would work on StructurizeCFG in a way that happens to touch how it interacts with DivergenceAnalysis. This comment serves as a warning to someone like that.

lib/Transforms/Scalar/StructurizeCFG.cpp

253 ↗

(On Diff #124542)

Done.

test/Transforms/StructurizeCFG/AMDGPU/uniform-regions.ll

1 ↗

(On Diff #131600)

Done

test/Transforms/StructurizeCFG/uniform-regions.ll

1 ↗

(On Diff #124542)

Done.

34 ↗

(On Diff #124542)

Done.

[alex-t]

include/llvm/Analysis/DivergenceAnalysis.h

40 ↗

(On Diff #124542)

This problem may occur in case the value that is defined uniformly in a loop is used outside the loop in another block that is control dependent of the divergent loop exit branch. The value itself it is still uniform.
But the value that is produced by the user is divergent because of the divergent control dependency. So DivergentAnalysis is correct. The problem is in misunderstanding of what is control dependencies in the context of divergence.

I'd give same example as in https://reviews.llvm.org/D40547

%tid = call i32 @llvm.amdgcn.workitem.id.x()

for.body:

%val = add i32 %val, 1 <== definition of %val is uniform
%cmp = icmp gt i64 %tid, %arg1
br i1 %cmp, label %for.end, label %for.body <== loop exit condition is divergent
for.end:

%result = add i32 %val, %x <== each thread will have different %val here. So the %result is divergent but %val is still uniform

Anyway it is not a serious issue. I just want to explain what I meant.

[nhaehnle]

Finally got time to get back to this. Can I get a review on this please?

[spatel]

I'm not sure if it was this change or something else, but the optnone test is not stable on my system (testing with llc built from r325923):

$ ./llvm-lit ../../llvm/test/CodeGen/AMDGPU/control-flow-optnone.ll 
-- Testing: 1 tests, 1 threads --
PASS: LLVM :: CodeGen/AMDGPU/control-flow-optnone.ll (1 of 1)
Testing Time: 0.11s
  Expected Passes    : 1
$ ./llvm-lit ../../llvm/test/CodeGen/AMDGPU/control-flow-optnone.ll 
-- Testing: 1 tests, 1 threads --
FAIL: LLVM :: CodeGen/AMDGPU/control-flow-optnone.ll (1 of 1)
Testing Time: 0.11s
********************
Failing Tests (1):
    LLVM :: CodeGen/AMDGPU/control-flow-optnone.ll

I also got blame mail from a bot about this test failing for what would seem to be an unrelated change:
http://lab.llvm.org:8011/builders/clang-ppc64be-linux-multistage/builds/7201

[nhaehnle]

Yes, it's this change. It's subtle, DivergenceAnalysis has always ended up with dangling pointers, but prior to this change it happened to not matter because we never queried newly created values. This change ended up querying newly created values, and the results differed depending on whether the new allocations happened to reuse the dangling pointers. I uploaded a new version of this change as D43743.

llvm/trunk/include/llvm/Analysis/DivergenceAnalysis.h

public:
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
   bool runOnFunction(Function &F) override;
 
   // Print all divergent branches in the function.
   void print(raw_ostream &OS, const Module *) const override;
 
-  // Returns true if V is divergent.
+  // Returns true if V is divergent at its definition.
+  //
+  // Even if this function returns false, V may still be divergent when used
+  // in a different basic block.
   bool isDivergent(const Value *V) const { return DivergentValues.count(V); }
 
   // Returns true if V is uniform/non-divergent.
+  //
+  // Even if this function returns true, V may still be divergent when used
+  // in a different basic block.
   bool isUniform(const Value *V) const { return !isDivergent(V); }
 
 private:
   // Stores all divergent values.
   DenseSet<const Value *> DivergentValues;
 };
 } // End llvm namespace

llvm/trunk/lib/Transforms/Scalar/StructurizeCFG.cpp

 
 #define DEBUG_TYPE "structurizecfg"
 
 // The name for newly created blocks.
 static const char *const FlowBlockName = "Flow";
 
 namespace {
 
+static cl::opt<bool> ForceSkipUniformRegions(
+  "structurizecfg-skip-uniform-regions",
+  cl::Hidden,
+  cl::desc("Force whether the StructurizeCFG pass skips uniform regions"),
+  cl::init(false));
+
 // Definition of the complex types used in this pass.
 
 using BBValuePair = std::pair<BasicBlock *, Value *>;
 
 using RNVector = SmallVector<RegionNode *, 8>;
 using BBVector = SmallVector<BasicBlock *, 8>;
 using BranchVector = SmallVector<BranchInst *, 8>;
 using BBValueVector = SmallVector<BBValuePair, 2>;
class StructurizeCFG : public RegionPass {
 
   void createFlow();
 
   void rebuildSSA();
 
 public:
   static char ID;
 
-  explicit StructurizeCFG(bool SkipUniformRegions = false)
-      : RegionPass(ID), SkipUniformRegions(SkipUniformRegions) {
+  explicit StructurizeCFG(bool SkipUniformRegions_ = false)
+      : RegionPass(ID),
+        SkipUniformRegions(SkipUniformRegions_) {
+    if (ForceSkipUniformRegions.getNumOccurrences())
+      SkipUniformRegions = ForceSkipUniformRegions.getValue();
     initializeStructurizeCFGPass(*PassRegistry::getPassRegistry());
   }
 
   bool doInitialization(Region *R, RGPassManager &RGM) override;
 
   bool runOnRegion(Region *R, RGPassManager &RGM) override;
 
   StringRef getPassName() const override { return "Structurize control flow"; }

 
 static bool hasOnlyUniformBranches(const Region *R,
                                    const DivergenceAnalysis &DA) {
   for (const BasicBlock *BB : R->blocks()) {
     const BranchInst *Br = dyn_cast<BranchInst>(BB->getTerminator());
     if (!Br || !Br->isConditional())
       continue;
 
-    if (!DA.isUniform(Br->getCondition()))
+    if (!DA.isUniform(Br))
       return false;
     DEBUG(dbgs() << "BB: " << BB->getName() << " has uniform terminator\n");
   }
   return true;
 }
 
 /// \brief Run the transformation for each region found
 bool StructurizeCFG::runOnRegion(Region *R, RGPassManager &RGM) {

llvm/trunk/test/CodeGen/AMDGPU/control-flow-optnone.ll

 ; GCN: s_branch
 
 ; GCN-DAG: v_cmp_lt_i32
 ; GCN-DAG: v_cmp_gt_i32
 ; GCN: s_and_b64
 ; GCN: s_mov_b64 exec
 
 ; GCN: s_or_b64 exec, exec
-; GCN: v_cmp_eq_u32
-; GCN: s_cbranch_vccnz
+; GCN: s_cmp_eq_u32
+; GCN: s_cbranch_scc1
 ; GCN-NEXT: s_branch
 define amdgpu_kernel void @copytoreg_divergent_brcond(i32 %arg, i32 %arg1, i32 %arg2) #0 {
 bb:
   %tmp = tail call i32 @llvm.amdgcn.workitem.id.x()
   %tmp3 = zext i32 %tmp to i64
   %tmp5 = add i64 %tmp3, undef
   %tmp6 = trunc i64 %tmp5 to i32
   %tmp7 = mul nsw i32 %tmp6, %arg2

llvm/trunk/test/Transforms/StructurizeCFG/AMDGPU/uniform-regions.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -mtriple=amdgcn-- -S -o - -structurizecfg -structurizecfg-skip-uniform-regions < %s | FileCheck %s
+
+define amdgpu_cs void @uniform(i32 inreg %v) {
+; CHECK-LABEL: @uniform(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CC:%.*]] = icmp eq i32 [[V:%.*]], 0
+; CHECK-NEXT:    br i1 [[CC]], label [[IF:%.*]], label [[END:%.*]], !structurizecfg.uniform !0
+; CHECK:       if:
+; CHECK-NEXT:    br label [[END]], !structurizecfg.uniform !0
+; CHECK:       end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cc = icmp eq i32 %v, 0
+  br i1 %cc, label %if, label %end
+
+if:
+  br label %end
+
+end:
+  ret void
+}
+
+define amdgpu_cs void @nonuniform(i32 addrspace(2)* %ptr) {
+; CHECK-LABEL: @nonuniform(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[TMP0:%.*]], [[FLOW:%.*]] ]
+; CHECK-NEXT:    [[CC:%.*]] = icmp ult i32 [[I]], 4
+; CHECK-NEXT:    br i1 [[CC]], label [[MID_LOOP:%.*]], label [[FLOW]]
+; CHECK:       mid.loop:
+; CHECK-NEXT:    [[V:%.*]] = call i32 @llvm.amdgcn.workitem.id.x()
+; CHECK-NEXT:    [[CC2:%.*]] = icmp eq i32 [[V]], 0
+; CHECK-NEXT:    br i1 [[CC2]], label [[END_LOOP:%.*]], label [[FLOW1:%.*]]
+; CHECK:       Flow:
+; CHECK-NEXT:    [[TMP0]] = phi i32 [ [[TMP2:%.*]], [[FLOW1]] ], [ undef, [[FOR_BODY]] ]
+; CHECK-NEXT:    [[TMP1:%.*]] = phi i1 [ [[TMP3:%.*]], [[FLOW1]] ], [ true, [[FOR_BODY]] ]
+; CHECK-NEXT:    br i1 [[TMP1]], label [[FOR_END:%.*]], label [[FOR_BODY]]
+; CHECK:       end.loop:
+; CHECK-NEXT:    [[I_INC:%.*]] = add i32 [[I]], 1
+; CHECK-NEXT:    br label [[FLOW1]]
+; CHECK:       Flow1:
+; CHECK-NEXT:    [[TMP2]] = phi i32 [ [[I_INC]], [[END_LOOP]] ], [ undef, [[MID_LOOP]] ]
+; CHECK-NEXT:    [[TMP3]] = phi i1 [ false, [[END_LOOP]] ], [ true, [[MID_LOOP]] ]
+; CHECK-NEXT:    br label [[FLOW]]
+; CHECK:       for.end:
+; CHECK-NEXT:    br i1 [[CC]], label [[IF:%.*]], label [[END:%.*]]
+; CHECK:       if:
+; CHECK-NEXT:    br label [[END]]
+; CHECK:       end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %for.body
+
+for.body:
+  %i = phi i32 [0, %entry], [%i.inc, %end.loop]
+  %cc = icmp ult i32 %i, 4
+  br i1 %cc, label %mid.loop, label %for.end
+
+mid.loop:
+  %v = call i32 @llvm.amdgcn.workitem.id.x()
+  %cc2 = icmp eq i32 %v, 0
+  br i1 %cc2, label %end.loop, label %for.end
+
+end.loop:
+  %i.inc = add i32 %i, 1
+  br label %for.body
+
+for.end:
+  br i1 %cc, label %if, label %end
+
+if:
+  br label %end
+
+end:
+  ret void
+}
+
+declare i32 @llvm.amdgcn.workitem.id.x()