[PowerPC] Add profitablilty check for conversion to mtctr loops

[lei]

Summary

Add profitability checks for modifying counted loops to use the mtctr instruction.

The latency of mtctr is only justified if there are more than 4 comparisons that will be removed as a result.

Usually counted loops are formed relatively early and before unrolling, so most low trip count loops often don't survive. However we want to ensure that if they do, we do not mistakenly update them to mtctr loops.

[hfinkel]

test/CodeGen/PowerPC/ctr-minmaxnum.ll

63

Please update the trip counts on these tests so we don't lose coverage.

[lei]

test/CodeGen/PowerPC/ctr-minmaxnum.ll

63

This test case verifies that for short loops with a trip count of 2, we don't generate mtctr for for pwr7+ but we do generate mtctr for bluegene. On power, these short loops are usually unrolled and never make it this far so naturally we don't see mtctr. However now that we put in a check to not use mtctr for short loops, we should not see this instruction anymore even for short loops which were not unrolled previously. As far as I can tell this should be the desired behaviour now. Unless I am missing something, I don't think we are losing any coverage here.

I have added test case below to ensure we still generate the mtctr loops for trip counts >= 4.

[nemanjai]

test/CodeGen/PowerPC/ctr-minmaxnum.ll

63

Well, there are still two open questions here:

• Is this something we want on the A2 cores or would we always want an mtctr?
• can we add a "trip count >= 4" test case for the A2 core as well?

[lei]

Since we are preventing the compiler from converting short loops to ctr loops, updating the ctr-minmaxnum.ll checks to be more restrictive and add default behaviour tests for the A2 core.

[hfinkel]

test/CodeGen/PowerPC/ctr-minmaxnum.ll

63

I'm not entirely sure I understand the premise for doing exactly this in any case. I understand that short loops are generally unrolled (for all cores). However:

• I imagine this is not really optimal for the A2. mtctr has a 6-cycle latency, so the loop would need to be really small in order for that to cause a hazard.
• Even on the POWER cores, is this really a function of a small trip count along, or also having a small loop? You can have a large loop with a small trip count, and will want to do this transformation in order to reduce register pressure within the loop.

In short, I suspect we'll want to restrict this to only some cores, and we'll want to use CodeMetrics to limit this to only do something on small loops. See, for example, ApproximateLoopSize in LoopUnrollPass.cpp.

[lei]

Use CodeMetrics to ensure we are only doing this for small loops with small trip counts.

[hfinkel]

lib/Target/PowerPC/PPCCTRLoops.cpp

495

Please add a comment here that 6 is an approximate latency for the mtctr instruction.

test/CodeGen/PowerPC/ctr-minmaxnum.ll

63

Please increase the trip counts of these loops so they still test what they're supposed to test (i.e. whether we can form a ctr-based loop with these various functions calls in the loop based on our knowledge of how these will be lowered (i.e., some will be lowered using instructions, not actual calls, depending on the enabled target features, enabling us to nevertheless use the ctr-based loop)).

[lei]

Address review comments.

[hfinkel]

LGTM

lib/Target/PowerPC/PPCCTRLoops.cpp

124

Spaces around the =.

[lei]

tc update.

[echristo]

lib/Target/PowerPC/PPCCTRLoops.cpp

124

The initialization here looks a little weird since it's not anywhere else...

[lei]

lib/Target/PowerPC/PPCCTRLoops.cpp

124

Yes, this is not needed. I will remove the initialization prior to committing this patch.

lib/Target/PowerPC/PPCCTRLoops.cpp

 //  - No nested CTR loops.
 //  - No function calls in loops.
 //
 //===----------------------------------------------------------------------===//
 
 #include "PPC.h"
 #include "PPCSubtarget.h"
 #include "PPCTargetMachine.h"
+#include "PPCTargetTransformInfo.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/CodeMetrics.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
+#include "llvm/CodeGen/TargetSchedule.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/InlineAsm.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/ValueHandle.h"

 using namespace llvm;
 
 #define DEBUG_TYPE "ctrloops"
 
 #ifndef NDEBUG
 static cl::opt<int> CTRLoopLimit("ppc-max-ctrloop", cl::Hidden, cl::init(-1));
 #endif
 
+// The latency of mtctr is only justified if there are more than 4
+// comparisons that will be removed as a result.
+static cl::opt<unsigned>
+SmallCTRLoopThreshold("min-ctr-loop-threshold", cl::init(4), cl::Hidden,
+                      cl::desc("Loops with a constant trip count smaller than "
+                               "this value will not use the count register."));
+
 STATISTIC(NumCTRLoops, "Number of loops converted to CTR loops");
 
 namespace llvm {
   void initializePPCCTRLoopsPass(PassRegistry&);
 #ifndef NDEBUG
   void initializePPCCTRLoopsVerifyPass(PassRegistry&);
 #endif
 }
public:
     bool runOnFunction(Function &F) override;
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.addRequired<LoopInfoWrapperPass>();
       AU.addPreserved<LoopInfoWrapperPass>();
       AU.addRequired<DominatorTreeWrapperPass>();
       AU.addPreserved<DominatorTreeWrapperPass>();
       AU.addRequired<ScalarEvolutionWrapperPass>();
+      AU.addRequired<AssumptionCacheTracker>();
+      AU.addRequired<TargetTransformInfoWrapperPass>();
     }
 
   private:
     bool mightUseCTR(BasicBlock *BB);
     bool convertToCTRLoop(Loop *L);
 
   private:
     const PPCTargetMachine *TM;
     const PPCSubtarget *STI;
     const PPCTargetLowering *TLI;
     const DataLayout *DL;
     const TargetLibraryInfo *LibInfo;
+    const TargetTransformInfo *TTI=nullptr;
     LoopInfo *LI;
     ScalarEvolution *SE;
     DominatorTree *DT;
     bool PreserveLCSSA;
+    TargetSchedModel SchedModel;
   };
 
   char PPCCTRLoops::ID = 0;
 #ifndef NDEBUG
   int PPCCTRLoops::Counter = 0;
 #endif
 
 #ifndef NDEBUG
bool PPCCTRLoops::runOnFunction(Function &F) {
 
   TM = &TPC->getTM<PPCTargetMachine>();
   STI = TM->getSubtargetImpl(F);
   TLI = STI->getTargetLowering();
 
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+  TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
   DL = &F.getParent()->getDataLayout();
   auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
   LibInfo = TLIP ? &TLIP->getTLI() : nullptr;
   PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
 
   bool MadeChange = false;
 
   for (LoopInfo::iterator I = LI->begin(), E = LI->end();
#endif
 
     for (Value *Operand : J->operands())
       if (memAddrUsesCTR(*TM, Operand))
         return true;
   }
 
   return false;
 }
-
 bool PPCCTRLoops::convertToCTRLoop(Loop *L) {
   bool MadeChange = false;
 
+  // Do not convert small short loops to CTR loop.
+  unsigned ConstTripCount = SE->getSmallConstantTripCount(L);
+  if (ConstTripCount && ConstTripCount < SmallCTRLoopThreshold) {
+    SmallPtrSet<const Value *, 32> EphValues;
+    auto AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
+        *L->getHeader()->getParent());
+    CodeMetrics::collectEphemeralValues(L, &AC, EphValues);
+    CodeMetrics Metrics;
+    for (BasicBlock *BB : L->blocks())
+      Metrics.analyzeBasicBlock(BB, *TTI, EphValues);
+    if (Metrics.NumInsts < (6 * SchedModel.getIssueWidth()))
+      return false;
+  }
+
   // Process nested loops first.
   for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) {
     MadeChange |= convertToCTRLoop(*I);
     DEBUG(dbgs() << "Nested loop converted\n");
   }
 
   // If a nested loop has been converted, then we can't convert this loop.
   if (MadeChange)

test/CodeGen/PowerPC/ctr-minmaxnum.ll

-; RUN: llc -verify-machineinstrs -mcpu=pwr7 < %s | FileCheck %s
-; RUN: llc -verify-machineinstrs -mcpu=a2q < %s | FileCheck %s --check-prefix=QPX
-target triple = "powerpc64-unknown-linux-gnu"
+; RUN: llc -mtriple=powerpc64-unknown-linux-gnu -verify-machineinstrs -mcpu=pwr7 < %s | FileCheck %s -implicit-check-not=mtctr
+; RUN: llc -mtriple=powerpc64-unknown-linux-gnu -verify-machineinstrs -mcpu=a2q < %s | FileCheck %s --check-prefix=QPX -implicit-check-not=mtctr
 
 declare float @fabsf(float)
 
 declare float @fminf(float, float)
 declare double @fmin(double, double)
 declare float @llvm.minnum.f32(float, float)
 declare double @llvm.minnum.f64(double, double)
 
loop_body:
   %2 = icmp eq i64 %1, 2
   br i1 %2, label %loop_exit, label %loop_body
 
 loop_exit:
   ret void
 }
 
 ; CHECK-LABEL: test1:
-; CHECK-NOT: mtctr
 ; CHECK: bl fminf
+; CHECK-NOT: bl fminf
+; CHECK: blr
 
 define void @test1v(<4 x float> %f, <4 x float>* %fp) {
 entry:
   br label %loop_body
 
 loop_body:
   %invar_address.dim.0.01 = phi i64 [ 0, %entry ], [ %1, %loop_body ]
   %0 = call <4 x float> @llvm.minnum.v4f32(<4 x float> %f, <4 x float> <float 1.0, float 1.0, float 1.0, float 1.0>)
   store <4 x float> %0, <4 x float>* %fp, align 16
   %1 = add i64 %invar_address.dim.0.01, 1
   %2 = icmp eq i64 %1, 2
   br i1 %2, label %loop_exit, label %loop_body
 
 loop_exit:
   ret void
 }
 
 ; CHECK-LABEL: test1v:
-; CHECK-NOT: mtctr
 ; CHECK: bl fminf
+; CHECK: bl fminf
+; CHECK: bl fminf
+; CHECK: bl fminf
+; CHECK-NOT: bl fminf
+; CHECK: blr
 
 ; QPX-LABEL: test1v:
-; QPX: mtctr
 ; QPX-NOT: bl fminf
 ; QPX: blr
 
 define void @test1a(float %f, float* %fp) {
 entry:
   br label %loop_body
 
 loop_body:
   %invar_address.dim.0.01 = phi i64 [ 0, %entry ], [ %1, %loop_body ]
   %0 = call float @fminf(float %f, float 1.0) readnone
   store float %0, float* %fp, align 4
   %1 = add i64 %invar_address.dim.0.01, 1
   %2 = icmp eq i64 %1, 2
   br i1 %2, label %loop_exit, label %loop_body
 
 loop_exit:
   ret void
 }
 
 ; CHECK-LABEL: test1a:
-; CHECK-NOT: mtctr
 ; CHECK: bl fminf
+; CHECK-NOT: bl fminf
+; CHECK: blr
 
 define void @test2(float %f, float* %fp) {
 entry:
   br label %loop_body
 
 loop_body:
   %invar_address.dim.0.01 = phi i64 [ 0, %entry ], [ %1, %loop_body ]
   %0 = call float @llvm.maxnum.f32(float %f, float 1.0)
   store float %0, float* %fp, align 4
   %1 = add i64 %invar_address.dim.0.01, 1
   %2 = icmp eq i64 %1, 2
   br i1 %2, label %loop_exit, label %loop_body
 
 loop_exit:
   ret void
 }
 
 ; CHECK-LABEL: test2:
-; CHECK-NOT: mtctr
 ; CHECK: bl fmaxf
+; CHECK-NOT: bl fmaxf
+; CHECK: blr
 
 define void @test2v(<4 x double> %f, <4 x double>* %fp) {
 entry:
   br label %loop_body
 
 loop_body:
   %invar_address.dim.0.01 = phi i64 [ 0, %entry ], [ %1, %loop_body ]
   %0 = call <4 x double> @llvm.maxnum.v4f64(<4 x double> %f, <4 x double> <double 1.0, double 1.0, double 1.0, double 1.0>)
   store <4 x double> %0, <4 x double>* %fp, align 16
   %1 = add i64 %invar_address.dim.0.01, 1
   %2 = icmp eq i64 %1, 2
   br i1 %2, label %loop_exit, label %loop_body
 
 loop_exit:
   ret void
 }
 
 ; CHECK-LABEL: test2v:
-; CHECK-NOT: mtctr
 ; CHECK: bl fmax
+; CHECK: bl fmax
+; CHECK: bl fmax
+; CHECK: bl fmax
+; CHECK-NOT: bl fmax
+; CHECK: blr
 
 ; QPX-LABEL: test2v:
-; QPX: mtctr
 ; QPX-NOT: bl fmax
 ; QPX: blr
 
 define void @test2a(float %f, float* %fp) {
 entry:
   br label %loop_body
 
 loop_body:
   %invar_address.dim.0.01 = phi i64 [ 0, %entry ], [ %1, %loop_body ]
   %0 = call float @fmaxf(float %f, float 1.0) readnone
   store float %0, float* %fp, align 4
   %1 = add i64 %invar_address.dim.0.01, 1
   %2 = icmp eq i64 %1, 2
   br i1 %2, label %loop_exit, label %loop_body
 
 loop_exit:
   ret void
 }
 
 ; CHECK-LABEL: test2a:
-; CHECK-NOT: mtctr
 ; CHECK: bl fmaxf
+; CHECK-NOT: bl fmaxf
+; CHECK: blr
 
 define void @test3(double %f, double* %fp) {
 entry:
   br label %loop_body
 
 loop_body:
   %invar_address.dim.0.01 = phi i64 [ 0, %entry ], [ %1, %loop_body ]
   %0 = call double @llvm.minnum.f64(double %f, double 1.0)
   store double %0, double* %fp, align 8
   %1 = add i64 %invar_address.dim.0.01, 1
   %2 = icmp eq i64 %1, 2
   br i1 %2, label %loop_exit, label %loop_body
 
 loop_exit:
   ret void
 }
 
 ; CHECK-LABEL: test3:
-; CHECK-NOT: mtctr
 ; CHECK: bl fmin
+; CHECK-NOT: bl fmin
+; CHECK: blr
 
 define void @test3a(double %f, double* %fp) {
 entry:
   br label %loop_body
 
 loop_body:
   %invar_address.dim.0.01 = phi i64 [ 0, %entry ], [ %1, %loop_body ]
   %0 = call double @fmin(double %f, double 1.0) readnone
   store double %0, double* %fp, align 8
   %1 = add i64 %invar_address.dim.0.01, 1
   %2 = icmp eq i64 %1, 2
   br i1 %2, label %loop_exit, label %loop_body
 
 loop_exit:
   ret void
 }
 
 ; CHECK-LABEL: test3a:
-; CHECK-NOT: mtctr
 ; CHECK: bl fmin
+; CHECK-NOT: bl fmin
+; CHECK: blr
 
 define void @test4(double %f, double* %fp) {
 entry:
   br label %loop_body
 
 loop_body:
   %invar_address.dim.0.01 = phi i64 [ 0, %entry ], [ %1, %loop_body ]
   %0 = call double @llvm.maxnum.f64(double %f, double 1.0)
   store double %0, double* %fp, align 8
   %1 = add i64 %invar_address.dim.0.01, 1
   %2 = icmp eq i64 %1, 2
   br i1 %2, label %loop_exit, label %loop_body
 
 loop_exit:
   ret void
 }
 
 ; CHECK-LABEL: test4:
-; CHECK-NOT: mtctr
 ; CHECK: bl fmax
+; CHECK-NOT: bl fmax
+; CHECK: blr
 
 define void @test4a(double %f, double* %fp) {
 entry:
   br label %loop_body
 
 loop_body:
   %invar_address.dim.0.01 = phi i64 [ 0, %entry ], [ %1, %loop_body ]
   %0 = call double @fmax(double %f, double 1.0) readnone
   store double %0, double* %fp, align 8
   %1 = add i64 %invar_address.dim.0.01, 1
   %2 = icmp eq i64 %1, 2
   br i1 %2, label %loop_exit, label %loop_body
 
 loop_exit:
   ret void
 }
 
 ; CHECK-LABEL: test4a:
-; CHECK-NOT: mtctr
 ; CHECK: bl fmax
+; CHECK-NOT: bl fmax
+; CHECK: blr
 

test/CodeGen/PowerPC/ctrloop-shortLoops.ll

+; RUN: llc < %s -mtriple=powerpc64le-unknown-linux-gnu -verify-machineinstrs -mcpu=pwr8 | FileCheck %s
+; RUN: llc < %s -mtriple=powerpc64le-unknown-linux-gnu -verify-machineinstrs -mcpu=a2q | FileCheck %s
+
+; Verify that we do NOT generate the mtctr instruction for loop trip counts < 4
+; The latency of the mtctr is only justified if there are more than 4 comparisons that are removed as a result.
+
+@a = common local_unnamed_addr global i32 0, align 4
+@arr = common local_unnamed_addr global [5 x i32] zeroinitializer, align 4
+
+; Function Attrs: norecurse nounwind readonly
+define signext i32 @testTripCount2(i32 signext %a) {
+
+; CHECK-LABEL: testTripCount2:
+; CHECK-NOT: mtctr
+; CHECK: blr
+
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body
+  ret i32 %add
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 1, %entry ], [ %indvars.iv.next, %for.body ]
+  %Sum.05 = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  %arrayidx = getelementptr inbounds [5 x i32], [5 x i32]* @arr, i64 0, i64 %indvars.iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %add = add nsw i32 %0, %Sum.05
+  %indvars.iv.next = add nsw i64 %indvars.iv, -1
+  %tobool = icmp eq i64 %indvars.iv, 0
+  br i1 %tobool, label %for.cond.cleanup, label %for.body
+}
+
+; Function Attrs: norecurse nounwind readonly
+define signext i32 @testTripCount3(i32 signext %a) {
+
+; CHECK-LABEL: testTripCount3:
+; CHECK-NOT: mtctr
+; CHECK: blr
+
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body
+  ret i32 %add
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 2, %entry ], [ %indvars.iv.next, %for.body ]
+  %Sum.05 = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  %arrayidx = getelementptr inbounds [5 x i32], [5 x i32]* @arr, i64 0, i64 %indvars.iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %add = add nsw i32 %0, %Sum.05
+  %indvars.iv.next = add nsw i64 %indvars.iv, -1
+  %tobool = icmp eq i64 %indvars.iv, 0
+  br i1 %tobool, label %for.cond.cleanup, label %for.body
+}
+
+; Function Attrs: norecurse nounwind readonly
+
+define signext i32 @testTripCount4(i32 signext %a) {
+
+; CHECK-LABEL: testTripCount4:
+; CHECK: mtctr
+; CHECK: bdnz
+
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body
+  ret i32 %add
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ 3, %entry ], [ %indvars.iv.next, %for.body ]
+  %Sum.05 = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  %arrayidx = getelementptr inbounds [5 x i32], [5 x i32]* @arr, i64 0, i64 %indvars.iv
+  %0 = load i32, i32* %arrayidx, align 4
+  %add = add nsw i32 %0, %Sum.05
+  %indvars.iv.next = add nsw i64 %indvars.iv, -1
+  %tobool = icmp eq i64 %indvars.iv, 0
+  br i1 %tobool, label %for.cond.cleanup, label %for.body
+}
+
+; Function Attrs: norecurse nounwind
+define signext i32 @testTripCount2NonSmallLoop() {
+
+; CHECK-LABEL: testTripCount2NonSmallLoop:
+; CHECK: mtctr
+; CHECK: blr
+
+entry:
+  %.pre = load i32, i32* @a, align 4
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %if.end
+  %0 = phi i32 [ %.pre, %entry ], [ %1, %if.end ]
+  %dec4 = phi i32 [ 1, %entry ], [ %dec, %if.end ]
+  %b.03 = phi i8 [ 0, %entry ], [ %b.1, %if.end ]
+  %tobool1 = icmp eq i32 %0, 0
+  br i1 %tobool1, label %if.end, label %if.then
+
+if.then:                                          ; preds = %for.body
+  store i32 2, i32* @a, align 4
+  br label %if.end
+
+if.end:                                           ; preds = %for.body, %if.then
+  %1 = phi i32 [ 2, %if.then ], [ 0, %for.body ]
+  %b.1 = phi i8 [ 2, %if.then ], [ %b.03, %for.body ]
+  %dec = add nsw i32 %dec4, -1
+  %tobool = icmp eq i32 %dec4, 0
+  br i1 %tobool, label %for.end, label %for.body
+
+for.end:                                          ; preds = %if.end
+  %conv = zext i8 %b.1 to i32
+  ret i32 %conv
+}
+