[AMDGPU] Unroll more to eliminate phis and conditions

[rampitec]

Summary

Increase threshold to unroll a loop which contains an "if" statement
whose condition defined by a PHI belonging to the loop. This may help
to eliminate if region and potentially even PHI itself, saving on
both divergence and registers used for the PHI.

Add a small bonus for each of such "if" statements.

[efriedma]

See also https://reviews.llvm.org/D21720

[rampitec]

Renamed variable

[rampitec]

Added CHECK-LABEL to the test

[vpykhtin]

LGTM.

lib/Target/AMDGPU/AMDGPUTargetTransformInfo.cpp

49

you can decrease nesting by using early exit here.

[rampitec]

Use early exit as suggested.

lib/Target/AMDGPU/AMDGPUTargetTransformInfo.cpp

 #include "llvm/Target/TargetLowering.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "AMDGPUtti"
 
 static cl::opt<unsigned> UnrollThresholdPrivate(
   "amdgpu-unroll-threshold-private",
   cl::desc("Unroll threshold for AMDGPU if private memory used in a loop"),
-  cl::init(2000), cl::Hidden);
+  cl::init(2500), cl::Hidden);
 
 static cl::opt<unsigned> UnrollThresholdLocal(
   "amdgpu-unroll-threshold-local",
   cl::desc("Unroll threshold for AMDGPU if local memory used in a loop"),
   cl::init(1000), cl::Hidden);
 
+static cl::opt<unsigned> UnrollThresholdIf(
+  "amdgpu-unroll-threshold-if",
+  cl::desc("Unroll threshold increment for AMDGPU for each if statement inside loop"),
+  cl::init(150), cl::Hidden);
+
+static bool dependsOnLocalPhi(const Loop *L, const Value *Cond,
+                              unsigned MaxDepth = 0) {
+  if (const Instruction *I = dyn_cast<Instruction>(Cond)) {
+    for (const Value *V : I->operand_values()) {
+      if (!L->contains(I))
+        continue;
+      if (const PHINode *PHI = dyn_cast<PHINode>(V)) {
+        if (none_of(L->getSubLoops(), [PHI](const Loop* SubLoop) {
+                    return SubLoop->contains(PHI); }))
+          return true;
+      } else if (MaxDepth < 10 && dependsOnLocalPhi(L, V, MaxDepth+1))
+        return true;
+    }
+  }
+  return false;
+}
+
 void AMDGPUTTIImpl::getUnrollingPreferences(Loop *L,
                                             TTI::UnrollingPreferences &UP) {
   UP.Threshold = 300; // Twice the default.
   UP.MaxCount = UINT_MAX;
   UP.Partial = true;
 
   // TODO: Do we want runtime unrolling?
 
   // Maximum alloca size than can fit registers. Reserve 16 registers.
   const unsigned MaxAlloca = (256 - 16) * 4;
   unsigned ThresholdPrivate = UnrollThresholdPrivate;
   unsigned ThresholdLocal = UnrollThresholdLocal;
   unsigned MaxBoost = std::max(ThresholdPrivate, ThresholdLocal);
   AMDGPUAS ASST = ST->getAMDGPUAS();
   for (const BasicBlock *BB : L->getBlocks()) {
     const DataLayout &DL = BB->getModule()->getDataLayout();
     unsigned LocalGEPsSeen = 0;
 
+    if (any_of(L->getSubLoops(), [BB](const Loop* SubLoop) {
+               return SubLoop->contains(BB); }))
+        continue; // Block belongs to an inner loop.
+
     for (const Instruction &I : *BB) {
+
+      // Unroll a loop which contains an "if" statement whose condition
+      // defined by a PHI belonging to the loop. This may help to eliminate
+      // if region and potentially even PHI itself, saving on both divergence
+      // and registers used for the PHI.
+      // Add a small bonus for each of such "if" statements.
+      if (const BranchInst *Br = dyn_cast<BranchInst>(&I)) {
+        if (UP.Threshold < MaxBoost && Br->isConditional()) {
+          if (L->isLoopExiting(Br->getSuccessor(0)) ||
+              L->isLoopExiting(Br->getSuccessor(1)))
+            continue;
+          if (dependsOnLocalPhi(L, Br->getCondition())) {
+            UP.Threshold += UnrollThresholdIf;
+            DEBUG(dbgs() << "Set unroll threshold " << UP.Threshold
+                         << " for loop:\n" << *L << " due to " << *Br << '\n');
+            if (UP.Threshold >= MaxBoost)
+              return;
+          }
+        }
+        continue;
+      }
+
       const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&I);
       if (!GEP)
         continue;
 
       unsigned AS = GEP->getAddressSpace();
       unsigned Threshold = 0;
       if (AS == ASST.PRIVATE_ADDRESS)
         Threshold = ThresholdPrivate;
for (const Instruction &I : *BB) {
       // We also want to have more unrolling for local memory to let ds
       // instructions with different offsets combine.
       //
       // Don't use the maximum allowed value here as it will make some
       // programs way too big.
       UP.Threshold = Threshold;
       DEBUG(dbgs() << "Set unroll threshold " << Threshold << " for loop:\n"
                    << *L << " due to " << *GEP << '\n');
-      if (UP.Threshold == MaxBoost)
+      if (UP.Threshold >= MaxBoost)
         return;
     }
   }
 }
 
 unsigned AMDGPUTTIImpl::getNumberOfRegisters(bool Vec) {
   if (Vec)
     return 0;

test/CodeGen/AMDGPU/unroll.ll

 loop.inc:
   %inc = add i32 %counter, 1
   %cond = icmp sge i32 %counter, 128
   br i1 %cond, label  %exit, label %loop.header
 
 exit:
   ret void
 }
+
+; Check that a loop with if inside completely unrolled to eliminate phi and if
+
+; CHECK: entry:
+; CHECK-NEXT: getelementptr
+; CHECK-NEXT: store
+; CHECK-NEXT: getelementptr
+; CHECK-NEXT: store
+; CHECK-NOT: br
+define amdgpu_kernel void @unroll_for_if(i32* %a) {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.inc
+  %i1 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %and = and i32 %i1, 1
+  %tobool = icmp eq i32 %and, 0
+  br i1 %tobool, label %for.inc, label %if.then
+
+if.then:                                          ; preds = %for.body
+  %0 = sext i32 %i1 to i64
+  %arrayidx = getelementptr inbounds i32, i32* %a, i64 %0
+  store i32 0, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body, %if.then
+  %inc = add nuw nsw i32 %i1, 1
+  %cmp = icmp ult i32 %inc, 48
+  br i1 %cmp, label %for.body, label %for.end
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}