[AMDGPU] Increase max iterations count to analyze complete unroll

[dfukalov]

Summary

In some cases inner loops may not get boosts so try to analyze them deeper.

[dfukalov]

fixing lint message

[rampitec]

llvm/test/Transforms/LoopUnroll/AMDGPU/unroll-analyze-small-loops.ll

8

Please run opt -instnamer on the test.

[dfukalov]

test updated as requested

[rampitec]

LGTM

[arsenm]

llvm/lib/Target/AMDGPU/AMDGPUTargetTransformInfo.cpp

82

Spelling Analize

[dfukalov]

fixed spelling

llvm/include/llvm/Analysis/TargetTransformInfo.h

struct UnrollingPreferences {
     /// If the value is true the peeling cost model can decide to peel only
     /// some iterations and in this case it will set this to false.
     bool PeelProfiledIterations;
     /// Threshold for unroll and jam, for inner loop size. The 'Threshold'
     /// value above is used during unroll and jam for the outer loop size.
     /// This value is used in the same manner to limit the size of the inner
     /// loop.
     unsigned UnrollAndJamInnerLoopThreshold;
+    /// Don't allow loop unrolling to simulate more than this number of
+    /// iterations when checking full unroll profitability
+    unsigned MaxIterationsCountToAnalyze;
   };
 
   /// Get target-customized preferences for the generic loop unrolling
   /// transformation. The caller will initialize UP with the current
   /// target-independent defaults.
   void getUnrollingPreferences(Loop *L, ScalarEvolution &,
                                UnrollingPreferences &UP) const;
 

llvm/lib/Target/AMDGPU/AMDGPUTargetTransformInfo.cpp

static cl::opt<bool> UnrollRuntimeLocal(
   cl::desc("Allow runtime unroll for AMDGPU if local memory used in a loop"),
   cl::init(true), cl::Hidden);
 
 static cl::opt<bool> UseLegacyDA(
   "amdgpu-use-legacy-divergence-analysis",
   cl::desc("Enable legacy divergence analysis for AMDGPU"),
   cl::init(false), cl::Hidden);
 
+static cl::opt<unsigned> UnrollMaxBlockToAnalyze(
+    "amdgpu-unroll-max-block-to-analyze",
+    cl::desc("Inner loop block size threshold to analyze in unroll for AMDGPU"),
+    cl::init(20), cl::Hidden);
+
 static bool dependsOnLocalPhi(const Loop *L, const Value *Cond,
                               unsigned Depth = 0) {
   const Instruction *I = dyn_cast<Instruction>(Cond);
   if (!I)
     return false;
 
   for (const Value *V : I->operand_values()) {
     if (!L->contains(I))
for (const Instruction &I : *BB) {
       // programs way too big.
       UP.Threshold = Threshold;
       LLVM_DEBUG(dbgs() << "Set unroll threshold " << Threshold
                         << " for loop:\n"
                         << *L << " due to " << *GEP << '\n');
       if (UP.Threshold >= MaxBoost)
         return;
     }
+
+    // If we got a GEP in a small BB from inner loop then increase max trip
+    // count to analyze for better estimation cost in unroll
+    if (L->empty() && BB->size() < UnrollMaxBlockToAnalyze)
+      UP.MaxIterationsCountToAnalyze = 32;
   }
 }
 
 unsigned GCNTTIImpl::getHardwareNumberOfRegisters(bool Vec) const {
   // The concept of vector registers doesn't really exist. Some packed vector
   // operations operate on the normal 32-bit registers.
   return 256;
 }

llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp

TargetTransformInfo::UnrollingPreferences llvm::gatherUnrollingPreferences(
   UP.AllowExpensiveTripCount = false;
   UP.Force = false;
   UP.UpperBound = false;
   UP.AllowPeeling = true;
   UP.AllowLoopNestsPeeling = false;
   UP.UnrollAndJam = false;
   UP.PeelProfiledIterations = true;
   UP.UnrollAndJamInnerLoopThreshold = 60;
+  UP.MaxIterationsCountToAnalyze = UnrollMaxIterationsCountToAnalyze;
 
   // Override with any target specific settings
   TTI.getUnrollingPreferences(L, SE, UP);
 
   // Apply size attributes
   bool OptForSize = L->getHeader()->getParent()->hasOptSize() ||
                     llvm::shouldOptimizeForSize(L->getHeader(), PSI, BFI,
                                                 PGSOQueryType::IRPass);
TargetTransformInfo::UnrollingPreferences llvm::gatherUnrollingPreferences(
   if (UnrollMaxUpperBound == 0)
     UP.UpperBound = false;
   if (UnrollAllowPeeling.getNumOccurrences() > 0)
     UP.AllowPeeling = UnrollAllowPeeling;
   if (UnrollAllowLoopNestsPeeling.getNumOccurrences() > 0)
     UP.AllowLoopNestsPeeling = UnrollAllowLoopNestsPeeling;
   if (UnrollUnrollRemainder.getNumOccurrences() > 0)
     UP.UnrollRemainder = UnrollUnrollRemainder;
+  if (UnrollMaxIterationsCountToAnalyze.getNumOccurrences() > 0)
+    UP.MaxIterationsCountToAnalyze = UnrollMaxIterationsCountToAnalyze;
 
   // Apply user values provided by argument
   if (UserThreshold.hasValue()) {
     UP.Threshold = *UserThreshold;
     UP.PartialThreshold = *UserThreshold;
   }
   if (UserCount.hasValue())
     UP.Count = *UserCount;

 /// given iteration its condition would be resolved to true, we won't add up the
 /// cost of the 'false'-block).
 /// \returns Optional value, holding the RolledDynamicCost and UnrolledCost. If
 /// the analysis failed (no benefits expected from the unrolling, or the loop is
 /// too big to analyze), the returned value is None.
 static Optional<EstimatedUnrollCost> analyzeLoopUnrollCost(
     const Loop *L, unsigned TripCount, DominatorTree &DT, ScalarEvolution &SE,
     const SmallPtrSetImpl<const Value *> &EphValues,
-    const TargetTransformInfo &TTI, unsigned MaxUnrolledLoopSize) {
+    const TargetTransformInfo &TTI, unsigned MaxUnrolledLoopSize,
+    unsigned MaxIterationsCountToAnalyze) {
   // We want to be able to scale offsets by the trip count and add more offsets
   // to them without checking for overflows, and we already don't want to
   // analyze *massive* trip counts, so we force the max to be reasonably small.
-  assert(UnrollMaxIterationsCountToAnalyze <
+  assert(MaxIterationsCountToAnalyze <
              (unsigned)(std::numeric_limits<int>::max() / 2) &&
          "The unroll iterations max is too large!");
 
   // Only analyze inner loops. We can't properly estimate cost of nested loops
   // and we won't visit inner loops again anyway.
   if (!L->empty())
     return None;
 
   // Don't simulate loops with a big or unknown tripcount
-  if (!UnrollMaxIterationsCountToAnalyze || !TripCount ||
-      TripCount > UnrollMaxIterationsCountToAnalyze)
+  if (!TripCount || TripCount > MaxIterationsCountToAnalyze)
     return None;
 
   SmallSetVector<BasicBlock *, 16> BBWorklist;
   SmallSetVector<std::pair<BasicBlock *, BasicBlock *>, 4> ExitWorklist;
   DenseMap<Value *, Constant *> SimplifiedValues;
   SmallVector<std::pair<Value *, Constant *>, 4> SimplifiedInputValues;
 
   // The estimated cost of the unrolled form of the loop. We try to estimate
if (getUnrolledLoopSize(LoopSize, UP) < UP.Threshold) {
       TripMultiple = UP.UpperBound ? 1 : TripMultiple;
       return ExplicitUnroll;
     } else {
       // The loop isn't that small, but we still can fully unroll it if that
       // helps to remove a significant number of instructions.
       // To check that, run additional analysis on the loop.
       if (Optional<EstimatedUnrollCost> Cost = analyzeLoopUnrollCost(
               L, FullUnrollTripCount, DT, SE, EphValues, TTI,
-              UP.Threshold * UP.MaxPercentThresholdBoost / 100)) {
+              UP.Threshold * UP.MaxPercentThresholdBoost / 100,
+              UP.MaxIterationsCountToAnalyze)) {
         unsigned Boost =
             getFullUnrollBoostingFactor(*Cost, UP.MaxPercentThresholdBoost);
         if (Cost->UnrolledCost < UP.Threshold * Boost / 100) {
           UseUpperBound = (FullUnrollMaxTripCount == FullUnrollTripCount);
           TripCount = FullUnrollTripCount;
           TripMultiple = UP.UpperBound ? 1 : TripMultiple;
           return ExplicitUnroll;
         }

llvm/test/Transforms/LoopUnroll/AMDGPU/unroll-analyze-small-loops.ll

+; RUN: opt -S -mtriple=amdgcn-unknown-amdhsa -loop-unroll -unroll-threshold=150 < %s | FileCheck %s
+
+; Test that max iterations count to analyze (specific for the target)
+; is enough to make the inner loop completely unrolled
+define hidden void @foo(float addrspace(1)* %ptrG, float addrspace(3)* %ptrL, i32 %A, i32 %A2, i32 %M) {
+bb:
+  br label %bb2
+
+bb2:                                              ; preds = %bb7, %bb
+  %i = phi i32 [ 0, %bb ], [ %i8, %bb7 ]
+  br label %bb4
+
+bb3:                                              ; preds = %bb7
+  ret void
+
+bb4:                                              ; preds = %bb10, %bb2
+  %i5 = phi i32 [ 0, %bb2 ], [ %i11, %bb10 ]
+  %i6 = add nuw nsw i32 %i5, %i
+  br label %for.body
+
+bb7:                                              ; preds = %bb10
+  %i8 = add nuw nsw i32 %i, 1
+  %i9 = icmp eq i32 %i8, 8
+  br i1 %i9, label %bb3, label %bb2
+
+bb10:                                             ; preds = %for.body
+  %i11 = add nuw nsw i32 %i5, 1
+  %cmpj = icmp ult i32 %i11, 8
+  br i1 %cmpj, label %bb7, label %bb4
+
+; CHECK: for.body:
+; CHECK-NOT: %phi = phi {{.*}}
+for.body:                                         ; preds = %for.body, %bb4
+  %phi = phi i32 [ 0, %bb4 ], [ %k, %for.body ]
+  %mul = shl nuw nsw i32 %phi, 5
+  %add1 = add i32 %A, %mul
+  %add2 = add i32 %add1, %M
+  %arrayidx = getelementptr inbounds float, float addrspace(3)* %ptrL, i32 %add2
+  %bc = bitcast float addrspace(3)* %arrayidx to i32 addrspace(3)*
+  %ld = load i32, i32 addrspace(3)* %bc, align 4
+  %mul2 = shl nuw nsw i32 %phi, 3
+  %add3 = add nuw nsw i32 %mul2, %A2
+  %arrayidx2 = getelementptr inbounds float, float addrspace(1)* %ptrG, i32 %add3
+  %bc2 = bitcast float addrspace(1)* %arrayidx2 to i32 addrspace(1)*
+  store i32 %ld, i32 addrspace(1)* %bc2, align 4
+  %k = add nuw nsw i32 %phi, 1
+  %cmpk = icmp ult i32 %k, 32
+  br i1 %cmpk, label %for.body, label %bb10
+}