[Loop Rotation] Make default max rotation header size threshold dependent on target CPU

[aturetsk]

Summary

Make default max rotation header size threshold dependent on target CPU through TTI.
Also set the threshold to 2 for Lakemont. Experiments on MCU benchmarks (Dhrystone, Coremark) show that this is the most optimal value for code size and performance.

[aturetsk]

Ping.

[aturetsk]

Ping.

[zzheng]

Minor suggestion to use Optional<unsigned>.

lib/Transforms/Scalar/LoopRotation.cpp

618

if (SpecifiedThreshold.hasValue())
  return *SpecifiedThreshold;
else {
...
}

646–648

Can we take this opportunity to change it to

Optional<unsigned> SpecifiedMaxHeaderSize

[aturetsk]

Use Optional<unsigned>.

[aturetsk]

Hi,
Thanks for the review. I used 'Optional<unsigned>' as suggested.

[echristo]

lib/Target/X86/X86TargetTransformInfo.cpp

1591

Explain the change?

lib/Transforms/Scalar/LoopRotation.cpp

642–643

This all feels awkward. Can you try to rework this a bit?

[aturetsk]

Added a comment in the X86TTIImpl::getLoopRotationDefaultThreshold.

[aturetsk]

Hi Eric,
Thanks for the review.

lib/Target/X86/X86TargetTransformInfo.cpp

1591

Added a comment.

lib/Transforms/Scalar/LoopRotation.cpp

642–643

Do I understand right that you don't like having Optional<> type for the variable which is not a function argument?

Unfortunately we can't use TTI object in the constructor, so we need to keep somehow the information whether the SpecifiedMaxHeaderSize was passed to the createLoopRotate or not until the chooseMaxHeaderSize is called. I see three ways to do that:

1. Use "Optional<unsigned> SpecifiedThreshold" as it is now
2. Use "int SpecifiedThreshold" and '-1' would mean the argument wasn't passed to the createLoopRotate. That's close to what the patch used to be.
3. Use 'unsigned SpecifiedThreshold' and 'bool IsSpecified'. The bool variable would indicate whether the argument was passed to the createLoopRotate or not.

Personally, I prefer the first option. BTW, I saw Optional<> used with class fields in other places (e.g. in lib/Transforms/Scalar/LoopUnrollPass.cpp in LoopUnroll class around the line 785).

[zzheng]

lib/Transforms/Scalar/LoopRotation.cpp

642–643

I think either 1 or 3 will be fine. If we choose 3, we can remove the static unsigned chooseMaxHeaderSize().

class LoopRotate : public LoopPass {
unsigned SpecifiedThreshold;
bool IsSpecified;
...
LoopRotate(Optional<unsigned> SpecifiedMaxHeaderSize = None)
    : LoopPass(ID) {
  ...
  if (SpecifiedMaxHeaderSize.hasValue())
    SpecifiedThreshold = *SpecifiedMaxHeaderSize;
  else
    SpecifiedThreshold = RotationThreshold;

   IsSpecified = SpecifiedMaxHeaderSize.hasValue() || RotationThreshold.getNumOccurrences() > 0;
}
...

We can even change the if-else above to

SpecifiedThreshold = SpecifiedMaxHeaderSize.hasValue() ?
                                *SpecifiedMaxHeaderSize : RotationThreshold;

as long as it conforms with the coding standard.

Later:

return iterativelyRotateLoop(
    L, IsSpecified ? SpecifiedThreshold : TTI->getLoopRotationDefaultThreshold(), LI, TTI, AC, DT, SE);

[aturetsk]

1. Rebased to the newer trunk.
2. The loop rotation pass has been ported to the new pass manager. Extend this patch for the new version of the pass as well.
3. Use approach #3 (with bool variable keeping information about the createLoopRotatePass argument).

[zzheng]

The patch looks in good shape to me. You can use clang-format to polish indent. See inlined comments.

lib/Transforms/Scalar/LoopRotation.cpp

634

This indent seems weird, is this the result of clang-format?

677

Same indent oddness...

[aturetsk]

All formatting weirdnesses you mentioned are the product of clang-format.
Unless I missed something all the changes were clang-formatted.

[aturetsk]

Ping.

[aturetsk]

Ping.

[aturetsk]

Rebased.

[aturetsk]

Ping.

[aturetsk]

Ping.

[echristo]

This is in my list, I'm trying to fix a bit of the pass before this. It shouldn't be too bad though.

lib/Target/X86/X86TargetTransformInfo.cpp

1591

Can you elaborate? What did you test on, do you know why? Is it just magic or is it based on something about the cpu?

[aturetsk]

OK.

lib/Target/X86/X86TargetTransformInfo.cpp

1591

The positive effect was measured on Spec2000 (code size only, Spec2000 is too large to run on MCU) and Dhrystone (code size and performance). Also tested code size on ULP and code size with performance on Coremark, but there was no effect.
The initial idea was to just improve code size for -Os by reducing the threshold, but since performance on Dhrystone improved as well (both for -Os and -O2), it seems to be a good idea to use a smaller threshold for Lakemont regardless of -O option.
So this is based on mere tuning, no special idea behind it.

[ashlykov]

Hi Eric,
I will manage D18898 patch on behalf of Andrey.
Are you still working on the fix you mentioned above?

In D18898#487239, @echristo wrote:

This is in my list, I'm trying to fix a bit of the pass before this. It shouldn't be too bad though.

[ashlykov]

Hi Eric! Could you please update a status of your mentioned fix?

[ashlykov]

@echristo Ping.

[hfinkel]

include/llvm/Analysis/TargetTransformInfo.h

298

Please explain here what this threshold actually does (I imagine that this is the maximum header size). Unfortunately, LoopRotate barely documents what it does, so we might need to improve that in order for this to make sense.

lib/Target/X86/X86TargetTransformInfo.cpp

1591

If this is something that is useful for a target to tune on a per-model basis, then we should add it to the scheduling model (for example, see LoopMicroOpBufferSize in SchedMachineModel and how that's handled).

We really should understand what is going on, however. Loop rotation uses CodeMetrics to calculate the effective size, but that cost model (TTI.getUserCost) has received very little attention. Also, does lakemont need any kind of scheduling model? It does not seem to have one at all.

include/llvm/Analysis/TargetTransformInfo.h

struct UnrollingPreferences {
     bool Force;
   };
 
   /// \brief 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, UnrollingPreferences &UP) const;
 
+  /// \brief Get target-customized default threshold for loop rotation.
+  unsigned getLoopRotationDefaultThreshold() const;
+
   /// @}
 
   /// \name Scalar Target Information
   /// @{
 
   /// \brief Flags indicating the kind of support for population count.
   ///
   /// Compared to the SW implementation, HW support is supposed to
virtual int getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
                                ArrayRef<Type *> ParamTys) = 0;
   virtual int getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
                                ArrayRef<const Value *> Arguments) = 0;
   virtual int getUserCost(const User *U) = 0;
   virtual bool hasBranchDivergence() = 0;
   virtual bool isSourceOfDivergence(const Value *V) = 0;
   virtual bool isLoweredToCall(const Function *F) = 0;
   virtual void getUnrollingPreferences(Loop *L, UnrollingPreferences &UP) = 0;
+  virtual unsigned getLoopRotationDefaultThreshold() const = 0;
   virtual bool isLegalAddImmediate(int64_t Imm) = 0;
   virtual bool isLegalICmpImmediate(int64_t Imm) = 0;
   virtual bool isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV,
                                      int64_t BaseOffset, bool HasBaseReg,
                                      int64_t Scale,
                                      unsigned AddrSpace) = 0;
   virtual bool isLegalMaskedStore(Type *DataType) = 0;
   virtual bool isLegalMaskedLoad(Type *DataType) = 0;
bool isSourceOfDivergence(const Value *V) override {
     return Impl.isSourceOfDivergence(V);
   }
   bool isLoweredToCall(const Function *F) override {
     return Impl.isLoweredToCall(F);
   }
   void getUnrollingPreferences(Loop *L, UnrollingPreferences &UP) override {
     return Impl.getUnrollingPreferences(L, UP);
   }
+  unsigned getLoopRotationDefaultThreshold() const override {
+    return Impl.getLoopRotationDefaultThreshold();
+  }
   bool isLegalAddImmediate(int64_t Imm) override {
     return Impl.isLegalAddImmediate(Imm);
   }
   bool isLegalICmpImmediate(int64_t Imm) override {
     return Impl.isLegalICmpImmediate(Imm);
   }
   bool isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset,
                              bool HasBaseReg, int64_t Scale,

include/llvm/Analysis/TargetTransformInfoImpl.h

if (Name == "pow" || Name == "powf" || Name == "powl" || Name == "exp2" ||
         Name == "llabs")
       return false;
 
     return true;
   }
 
   void getUnrollingPreferences(Loop *, TTI::UnrollingPreferences &) {}
 
+  unsigned getLoopRotationDefaultThreshold() const { return 16; }
+
   bool isLegalAddImmediate(int64_t Imm) { return false; }
 
   bool isLegalICmpImmediate(int64_t Imm) { return false; }
 
   bool isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV, int64_t BaseOffset,
                              bool HasBaseReg, int64_t Scale,
                              unsigned AddrSpace) {
     // Guess that only reg and reg+reg addressing is allowed. This heuristic is

include/llvm/CodeGen/BasicTTIImpl.h

for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); I != E;
         }
     }
 
     // Enable runtime and partial unrolling up to the specified size.
     UP.Partial = UP.Runtime = true;
     UP.PartialThreshold = UP.PartialOptSizeThreshold = MaxOps;
   }
 
+  unsigned getLoopRotationDefaultThreshold() const { return 16; }
+
   /// @}
 
   /// \name Vector TTI Implementations
   /// @{
 
   unsigned getNumberOfRegisters(bool Vector) { return Vector ? 0 : 1; }
 
   unsigned getRegisterBitWidth(bool Vector) { return 32; }

include/llvm/Transforms/Scalar.h

 // This header file defines prototypes for accessor functions that expose passes
 // in the Scalar transformations library.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_SCALAR_H
 #define LLVM_TRANSFORMS_SCALAR_H
 
+#include "llvm/ADT/Optional.h"
 #include <functional>
 
 namespace llvm {
 
 class BasicBlockPass;
 class Function;
 class FunctionPass;
 class ModulePass;

 // LoopReroll - This pass is a simple loop rerolling pass.
 //
 Pass *createLoopRerollPass();
 
 //===----------------------------------------------------------------------===//
 //
 // LoopRotate - This pass is a simple loop rotating pass.
 //
-Pass *createLoopRotatePass(int MaxHeaderSize = -1);
+Pass *createLoopRotatePass(Optional<unsigned> MaxHeaderSize = None);
 
 //===----------------------------------------------------------------------===//
 //
 // LoopIdiom - This pass recognizes and replaces idioms in loops.
 //
 Pass *createLoopIdiomPass();
 
 //===----------------------------------------------------------------------===//

lib/Analysis/TargetTransformInfo.cpp

bool TargetTransformInfo::isLoweredToCall(const Function *F) const {
   return TTIImpl->isLoweredToCall(F);
 }
 
 void TargetTransformInfo::getUnrollingPreferences(
     Loop *L, UnrollingPreferences &UP) const {
   return TTIImpl->getUnrollingPreferences(L, UP);
 }
 
+unsigned TargetTransformInfo::getLoopRotationDefaultThreshold() const {
+  return TTIImpl->getLoopRotationDefaultThreshold();
+}
+
 bool TargetTransformInfo::isLegalAddImmediate(int64_t Imm) const {
   return TTIImpl->isLegalAddImmediate(Imm);
 }
 
 bool TargetTransformInfo::isLegalICmpImmediate(int64_t Imm) const {
   return TTIImpl->isLegalICmpImmediate(Imm);
 }
 

lib/Target/X86/X86TargetTransformInfo.h

X86TTIImpl(const X86TTIImpl &Arg)
       : BaseT(static_cast<const BaseT &>(Arg)), ST(Arg.ST), TLI(Arg.TLI) {}
   X86TTIImpl(X86TTIImpl &&Arg)
       : BaseT(std::move(static_cast<BaseT &>(Arg))), ST(std::move(Arg.ST)),
         TLI(std::move(Arg.TLI)) {}
 
   /// \name Scalar TTI Implementations
   /// @{
   TTI::PopcntSupportKind getPopcntSupport(unsigned TyWidth);
+  unsigned getLoopRotationDefaultThreshold() const;
 
   /// @}
 
   /// \name Vector TTI Implementations
   /// @{
 
   unsigned getNumberOfRegisters(bool Vector);
   unsigned getRegisterBitWidth(bool Vector);

lib/Target/X86/X86TargetTransformInfo.cpp

bool X86TTIImpl::areInlineCompatible(const Function *Caller,
   const FeatureBitset &CalleeBits =
       TM.getSubtargetImpl(*Callee)->getFeatureBits();
 
   // FIXME: This is likely too limiting as it will include subtarget features
   // that we might not care about for inlining, but it is conservatively
   // correct.
   return (CallerBits & CalleeBits) == CalleeBits;
 }
+
+unsigned X86TTIImpl::getLoopRotationDefaultThreshold() const {
+  // The loop rotation threshold equal to 2 shows the best performance and code
+  // size results on the benchmarks for Lakemont. For other CPUs use the default
+  // threshold.
+  return ST->getCPU() == "lakemont" ? 2 : 16;
+}

lib/Transforms/IPO/PassManagerBuilder.cpp

void PassManagerBuilder::addFunctionSimplificationPasses(
   // Combine silly seq's
   addInstructionCombiningPass(MPM);
   addExtensionsToPM(EP_Peephole, MPM);
 
   MPM.add(createTailCallEliminationPass()); // Eliminate tail calls
   MPM.add(createCFGSimplificationPass());     // Merge & remove BBs
   MPM.add(createReassociatePass());           // Reassociate expressions
   // Rotate Loop - disable header duplication at -Oz
-  MPM.add(createLoopRotatePass(SizeLevel == 2 ? 0 : -1));
+  MPM.add(createLoopRotatePass(SizeLevel == 2 ? Optional<unsigned>(0) : None));
   MPM.add(createLICMPass());                  // Hoist loop invariants
   MPM.add(createLoopUnswitchPass(SizeLevel || OptLevel < 3));
   MPM.add(createCFGSimplificationPass());
   addInstructionCombiningPass(MPM);
   MPM.add(createIndVarSimplifyPass());        // Canonicalize indvars
   MPM.add(createLoopIdiomPass());             // Recognize idioms like memset.
   MPM.add(createLoopDeletionPass());          // Delete dead loops
   if (EnableLoopInterchange) {
void PassManagerBuilder::populateModulePassManager(
   if (RunFloat2Int)
     MPM.add(createFloat2IntPass());
 
   addExtensionsToPM(EP_VectorizerStart, MPM);
 
   // Re-rotate loops in all our loop nests. These may have fallout out of
   // rotated form due to GVN or other transformations, and the vectorizer relies
   // on the rotated form. Disable header duplication at -Oz.
-  MPM.add(createLoopRotatePass(SizeLevel == 2 ? 0 : -1));
+  MPM.add(createLoopRotatePass(SizeLevel == 2 ? Optional<unsigned>(0) : None));
 
   // Distribute loops to allow partial vectorization.  I.e. isolate dependences
   // into separate loop that would otherwise inhibit vectorization.  This is
   // currently only performed for loops marked with the metadata
   // llvm.loop.distribute=true or when -enable-loop-distribute is specified.
   MPM.add(createLoopDistributePass(/*ProcessAllLoopsByDefault=*/false));
 
   MPM.add(createLoopVectorizePass(DisableUnrollLoops, LoopVectorize));

lib/Transforms/Scalar/LoopRotation.cpp

 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 #include "llvm/Transforms/Utils/SSAUpdater.h"
 #include "llvm/Transforms/Utils/ValueMapper.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-rotate"
 
-static cl::opt<unsigned> DefaultRotationThreshold(
+static cl::opt<unsigned> RotationThreshold(
     "rotation-max-header-size", cl::init(16), cl::Hidden,
-    cl::desc("The default maximum header size for automatic loop rotation"));
+    cl::desc("The maximum header size for automatic loop rotation"));
 
 STATISTIC(NumRotated, "Number of loops rotated");
 
 /// A simple loop rotation transformation.
 class LoopRotate {
   const unsigned MaxHeaderSize;
   LoopInfo *LI;
   const TargetTransformInfo *TTI;
bool LoopRotate::processLoop(Loop *L) {
 
   return MadeChange;
 }
 
 LoopRotatePass::LoopRotatePass() {}
 
 PreservedAnalyses LoopRotatePass::run(Loop &L, AnalysisManager<Loop> &AM) {
   auto &FAM = AM.getResult<FunctionAnalysisManagerLoopProxy>(L).getManager();
   Function *F = L.getHeader()->getParent();
 
   auto *LI = FAM.getCachedResult<LoopAnalysis>(*F);
   const auto *TTI = FAM.getCachedResult<TargetIRAnalysis>(*F);
   auto *AC = FAM.getCachedResult<AssumptionAnalysis>(*F);
   assert((LI && TTI && AC) && "Analyses for loop rotation not available");
 
   // Optional analyses.
   auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(*F);
   auto *SE = FAM.getCachedResult<ScalarEvolutionAnalysis>(*F);
-  LoopRotate LR(DefaultRotationThreshold, LI, TTI, AC, DT, SE);
+  LoopRotate LR(RotationThreshold.getNumOccurrences() == 0
+                    ? TTI->getLoopRotationDefaultThreshold()
+                    : RotationThreshold,
+                LI, TTI, AC, DT, SE);
 
   bool Changed = LR.processLoop(&L);
   if (!Changed)
     return PreservedAnalyses::all();
   return getLoopPassPreservedAnalyses();
 }
 
 namespace {
 
 class LoopRotateLegacyPass : public LoopPass {
   unsigned MaxHeaderSize;
+  bool UseDefaultMHS;
 
 public:
   static char ID; // Pass ID, replacement for typeid
-  LoopRotateLegacyPass(int SpecifiedMaxHeaderSize = -1) : LoopPass(ID) {
+  LoopRotateLegacyPass(Optional<unsigned> SpecifiedMaxHeaderSize = None)
+      : LoopPass(ID) {
     initializeLoopRotateLegacyPassPass(*PassRegistry::getPassRegistry());
-    if (SpecifiedMaxHeaderSize == -1)
-      MaxHeaderSize = DefaultRotationThreshold;
-    else
-      MaxHeaderSize = unsigned(SpecifiedMaxHeaderSize);
+
+    MaxHeaderSize = SpecifiedMaxHeaderSize.hasValue() ? *SpecifiedMaxHeaderSize
+                                                      : RotationThreshold;
+    UseDefaultMHS = !SpecifiedMaxHeaderSize.hasValue() &&
+                    RotationThreshold.getNumOccurrences() == 0;
   }
 
   // LCSSA form makes instruction renaming easier.
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<AssumptionCacheTracker>();
     AU.addRequired<TargetTransformInfoWrapperPass>();
     getLoopAnalysisUsage(AU);
   }
 
   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
     if (skipLoop(L))
       return false;
     Function &F = *L->getHeader()->getParent();
 
     auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     const auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
     auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
     auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
     auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
     auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
     auto *SE = SEWP ? &SEWP->getSE() : nullptr;
-    LoopRotate LR(MaxHeaderSize, LI, TTI, AC, DT, SE);
+    LoopRotate LR(UseDefaultMHS ? TTI->getLoopRotationDefaultThreshold()
+                                : MaxHeaderSize,
+                  LI, TTI, AC, DT, SE);
     return LR.processLoop(L);
   }
 };
 }
 
 char LoopRotateLegacyPass::ID = 0;
 INITIALIZE_PASS_BEGIN(LoopRotateLegacyPass, "loop-rotate", "Rotate Loops",
                       false, false)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 INITIALIZE_PASS_END(LoopRotateLegacyPass, "loop-rotate", "Rotate Loops", false,
                     false)
 
-Pass *llvm::createLoopRotatePass(int MaxHeaderSize) {
+Pass *llvm::createLoopRotatePass(Optional<unsigned> MaxHeaderSize) {
   return new LoopRotateLegacyPass(MaxHeaderSize);
 }

test/Transforms/LoopRotate/target-default.ll

+; REQUIRES: asserts
+; RUN: opt < %s -march=x86 -mcpu=pentium -S -loop-rotate -debug -debug-only=loop-rotate 2>&1 | FileCheck %s -check-prefix=PENTIUM
+; RUN: opt < %s -march=x86 -mcpu=lakemont -S -loop-rotate -debug -debug-only=loop-rotate 2>&1 | FileCheck %s -check-prefix=LMT
+; RUN: opt < %s -march=x86 -mcpu=pentium -S -loop-rotate -rotation-max-header-size=0 -debug -debug-only=loop-rotate 2>&1 | FileCheck %s -check-prefix=PENTIUM-OPT
+; RUN: opt < %s -march=x86 -mcpu=lakemont -S -loop-rotate -rotation-max-header-size=16 -debug -debug-only=loop-rotate 2>&1 | FileCheck %s -check-prefix=LMT-OPT
+
+; Loop should be rotated for Pentium but not for Lakemont.
+; PENTIUM: rotating Loop at depth 1
+; LMT-NOT: rotating Loop at depth 1
+
+; Specification of -rotation-max-header-size should suppress default
+; target threshold.
+; PENTIUM-OPT-NOT: rotating Loop at depth 1
+; LMT-OPT: rotating Loop at depth 1
+
+target triple = "i386-unknown-linux-gnu"
+
+declare void @use(i32*, i32)
+
+define void @test(i32* %x, i32 %y) {
+entry:
+  br label %for.cond
+
+for.cond:
+  %x.addr.0 = phi i32* [ %x, %entry ], [ %incdec.ptr, %for.body ]
+  %0 = load i32, i32* %x.addr.0, align 4
+  %cmp = icmp sgt i32 %0, 0
+  %cmp1 = icmp sgt i32 %y, 0
+  %or.cond = and i1 %cmp, %cmp1
+  br i1 %or.cond, label %for.body, label %for.end
+
+for.body:
+  tail call void @use(i32* %x.addr.0, i32 %y)
+  %incdec.ptr = getelementptr inbounds i32, i32* %x.addr.0, i64 1
+  br label %for.cond
+
+for.end:
+  ret void
+}