[RFC] [TargetTransformInfo] Introduce isRegisterRich, it returns true if the target architecture is register-rich.

[etherzhhb]

Summary

Currently in the llvm middle-end, we disable some optimizations because we worry about the register pressure, (e.g. GVNHoist and ArgumentPromotion).

However, in the architecture that are register-rich, e.g. FPGAs, we do not need to worry about the register pressure at all. For these architecures, we may want to optimization the LLVM IR without worrying about the register pressure.

I suggest that we introduce a hook in the TargetTransformInfo to tell if the current target architecture is register-rich or not. With this hook, we can enable the optimizations that increase register pressure in case the current architecture is register-rich.

One problem for introducing this hook: we are not able to test it (in the public buildbot) without an register-rich target architecture in LLVM trunk, and unfortunately, we do not have one today.

To address this problem, I propose to add a command line option to enable the register-rich mode such that we can test the corresponding code path as well.

[kparzysz]

There is already a function getNumberOfRegisters. Would it be enough to return some large number from it?

[etherzhhb]

Implement isRegisterRich based on getNumberOfRegisters, and introduce a threshold to tell when the number of registers if big enough to be considered as "register-rich". Also include the usage of the isRegisterRich function in GVNHoist

[etherzhhb]

In D42191#979132, @kparzysz wrote:

There is already a function getNumberOfRegisters. Would it be enough to return some large number from it?

Yes, I think getNumberOfRegisters is sufficient. But instead of comparing getNumberOfRegisters with a large number in every passes, maybe we could introduce a function in TargetTransformInfo to do the comparison?

[hfinkel]

In part, it looks like you're looking to modify heuristics that prevent increased spilling around calls. I can imagine that, in general, architectures with lots of registers suffer from less of that, but that's really a statement about the ABI of the call, not the architecture itself.

Also, are you targeting FPGAs? Maybe this is better phrased in terms of architectures that don't have physical registers (we already have backend targets that have only virtual registers), because lacking physical registers, I can imagine register pressure being much less concerning. Arbitrary hoisting might not be great for FPGA HLS either, because of increased routing pressure and the like, but if we imagine that the backend can sink when useful, then maybe we're just making a statement about being reliant on that?

lib/Transforms/Scalar/GVNHoist.cpp

1044–1045

Update this comment?

1100–1104

Would you want to modify this check too?

1128–1129

Is this comment accurate? I don't see why this is talking about calls here when calls are handled in the block above.

[etherzhhb]

In D42191#979308, @hfinkel wrote:

In part, it looks like you're looking to modify heuristics that prevent increased spilling around calls. I can imagine that, in general, architectures with lots of registers suffer from less of that, but that's really a statement about the ABI of the call, not the architecture itself.

The original motivation is about hoisting the GEP, in general I want to GVN the gep like:

bb0:
idx0 = i + 2
g0 = gep A, idx0
br bb2

bb1:
idx1 = i + 2
g1 = gep A, idx1
br bb2

bb2:
g = phi [g0, bb0]; [g1, bb1]

In this example, g1 and g2 is not GVNed because our concern about the register pressure (or address mode?).

Also, are you targeting FPGAs?

Yes

Maybe this is better phrased in terms of architectures that don't have physical registers (we already have backend targets that have only virtual registers), because lacking physical registers, I can imagine register pressure being much less concerning.
Arbitrary hoisting might not be great for FPGA HLS either, because of increased routing pressure and the like,

Not sure the place and route pressure, but too much registers may still have a negative impact on FPGAs.

but if we imagine that the backend can sink when useful, then maybe we're just making a statement about being reliant on that?

Yes.

I am thinking maybe some of the LLVM IR passes could provide a mode that run without the concern of physical constraints like register pressure, and simplify the dataflow of the LLVM IR as much as possible.

I am trying to identify the actual physical constraints that prevents simplification like GVN from happening, and try to make these constraints more explicit and provide a hook to relax these constraints if possible.

lib/Transforms/Scalar/GVNHoist.cpp

1044–1045

Yes

1100–1104

yes

1128–1129

I guess it is about the address mode since it is related to GEP

[etherzhhb]

Address Hal's comment

[etherzhhb]

Fix typo

include/llvm/Analysis/TargetTransformInfo.h

public:
   /// \brief Additional properties of an operand's values.
   enum OperandValueProperties { OP_None = 0, OP_PowerOf2 = 1 };
 
   /// \return The number of scalar or vector registers that the target has.
   /// If 'Vectors' is true, it returns the number of vector registers. If it is
   /// set to false, it returns the number of scalar registers.
   unsigned getNumberOfRegisters(bool Vector) const;
 
+  static const unsigned RegisterRichThreshold = 8192;
+
+  /// \brief Return true if the target architecture is register-rich
+  bool isRegisterRich() const {
+    return getNumberOfRegisters(false) > RegisterRichThreshold;
+  }
+
   /// \return The width of the largest scalar or vector register type.
   unsigned getRegisterBitWidth(bool Vector) const;
 
   /// \return The width of the smallest vector register type.
   unsigned getMinVectorRegisterBitWidth() const;
 
   /// \return True if it should be considered for address type promotion.
   /// \p AllowPromotionWithoutCommonHeader Set true if promoting \p I is

include/llvm/Analysis/TargetTransformInfoImpl.h

unsigned getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
     case Intrinsic::coro_suspend:
     case Intrinsic::coro_param:
     case Intrinsic::coro_subfn_addr:
       // These intrinsics don't actually represent code after lowering.
       return TTI::TCC_Free;
     }
   }
 
+  bool isRegisterRich() { return false; }
+
   bool hasBranchDivergence() { return false; }
 
   bool isSourceOfDivergence(const Value *V) { return false; }
 
   bool isAlwaysUniform(const Value *V) { return false; }
 
   unsigned getFlatAddressSpace () {
     return -1;

lib/Target/FPGA/FPGATargetTransformInfo.h

public:
   int getCallCost(const Function *F, int NumArgs);
   int getCallCost(const Function *F, ArrayRef<const Value *> Arguments);
   //unsigned getInliningThresholdMultiplier();
   int getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
                        ArrayRef<Type *> ParamTys);
   int getIntrinsicCost(Intrinsic::ID IID, Type *RetTy,
                        ArrayRef<const Value *> Arguments);
   int getUserCost(const User *U, ArrayRef<const Value *> Operands);
+  bool isRegisterRich();
   bool hasBranchDivergence();
   bool isSourceOfDivergence(const Value *V);
   // bool isLoweredToCall(const Function *F);
   void getUnrollingPreferences(Loop *L, ScalarEvolution &SE,
                                TTI::UnrollingPreferences &UP);
   bool isLegalAddImmediate(int64_t Imm);
   bool isLegalICmpImmediate(int64_t Imm);
   // bool isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV, int64_t

lib/Target/FPGA/FPGATargetTransformInfo.cpp

 //===----------------------------------------------------------------------===//
 //
 // FPGA spmd/simt execution.
 //
 //===----------------------------------------------------------------------===//
 
 bool FPGATTIImpl::hasBranchDivergence() { return true; }
 
+bool FPGATTIImpl::isRegisterRich() { return true; }
+
 static bool IsKernelFunction(const Function &F) {
   return F.getCallingConv() == CallingConv::SPIR_KERNEL;
 }
 
 static bool readsLocalId(const IntrinsicInst *II) {
   switch (II->getIntrinsicID()) {
   default:
     return false;

lib/Transforms/Scalar/GVNHoist.cpp

 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/IteratedDominanceFrontier.h"
 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/PostDominators.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstrTypes.h"

 }
 
 // This pass hoists common computations across branches sharing common
 // dominator. The primary goal is to reduce the code size, and in some
 // cases reduce critical path (by exposing more ILP).
 class GVNHoist {
 public:
   GVNHoist(DominatorTree *DT, PostDominatorTree *PDT, AliasAnalysis *AA,
-           MemoryDependenceResults *MD, MemorySSA *MSSA)
-      : DT(DT), PDT(PDT), AA(AA), MD(MD), MSSA(MSSA),
+           MemoryDependenceResults *MD, MemorySSA *MSSA,
+           TargetTransformInfo &TTI)
+      : DT(DT), PDT(PDT), AA(AA), MD(MD), MSSA(MSSA), TTI(TTI),
         MSSAUpdater(llvm::make_unique<MemorySSAUpdater>(MSSA)) {}
 
   bool run(Function &F) {
     NumFuncArgs = F.arg_size();
     VN.setDomTree(DT);
     VN.setAliasAnalysis(AA);
     VN.setMemDep(MD);
     bool Res = false;

 
 private:
   GVN::ValueTable VN;
   DominatorTree *DT;
   PostDominatorTree *PDT;
   AliasAnalysis *AA;
   MemoryDependenceResults *MD;
   MemorySSA *MSSA;
+  TargetTransformInfo &TTI;
   std::unique_ptr<MemorySSAUpdater> MSSAUpdater;
   DenseMap<const Value *, unsigned> DFSNumber;
   BBSideEffectsSet BBSideEffects;
   DenseSet<const BasicBlock *> HoistBarrier;
   SmallVector<BasicBlock *, 32> IDFBlocks;
   unsigned NumFuncArgs;
-  const bool HoistingGeps = false;
 
   enum InsKind { Unknown, Scalar, Load, Store };
 
   // Return true when there are exception handling in BB.
   bool hasEH(const BasicBlock *BB) {
     auto It = BBSideEffects.find(BB);
     if (It != BBSideEffects.end())
       return It->second;
for (const HoistingPointInfo &HP : HPL) {
       } else {
         // When we do not find Repl in HoistPt, select the first in the list
         // and move it to HoistPt.
         Repl = InstructionsToHoist.front();
 
         // We can move Repl in HoistPt only when all operands are available.
         // The order in which hoistings are done may influence the availability
         // of operands.
         if (!allOperandsAvailable(Repl, DestBB)) {
-          // When HoistingGeps there is nothing more we can do to make the
-          // operands available: just continue.
-          if (HoistingGeps)
+          // If the target is register-rich, we should had already hoist the GEP
+          // if possible. We we do not need to further call
+          // makeGepOperandsAvailable to copy the GEPs
+          if (TTI.isRegisterRich())
             continue;
 
           // When not HoistingGeps we need to copy the GEPs.
           if (!makeGepOperandsAvailable(Repl, DestBB, InstructionsToHoist))
             continue;
         }
 
         // Move the instruction at the end of HoistPt.
for (BasicBlock *BB : depth_first(&F.getEntryBlock())) {
       int InstructionNb = 0;
       for (Instruction &I1 : *BB) {
         // If I1 cannot guarantee progress, subsequent instructions
         // in BB cannot be hoisted anyways.
         if (!isGuaranteedToTransferExecutionToSuccessor(&I1)) {
           HoistBarrier.insert(BB);
           break;
         }
-        // Only hoist the first instructions in BB up to MaxDepthInBB. Hoisting
-        // deeper may increase the register pressure and compilation time.
-        if (MaxDepthInBB != -1 && InstructionNb++ >= MaxDepthInBB)
+        // If we concern about the register pressure, we only hoist the first
+        // instructions in BB up to MaxDepthInBB. Hoisting deeper may increase
+        // the register pressure and compilation time.
+        if (!TTI.isRegisterRich() &&
+            MaxDepthInBB != -1 && InstructionNb++ >= MaxDepthInBB)
           break;
 
         // Do not value number terminator instructions.
         if (isa<TerminatorInst>(&I1))
           break;
 
         if (auto *Load = dyn_cast<LoadInst>(&I1))
           LI.insert(Load, VN);
         else if (auto *Store = dyn_cast<StoreInst>(&I1))
           SI.insert(Store, VN);
         else if (auto *Call = dyn_cast<CallInst>(&I1)) {
           if (auto *Intr = dyn_cast<IntrinsicInst>(Call)) {
             if (isa<DbgInfoIntrinsic>(Intr) ||
                 Intr->getIntrinsicID() == Intrinsic::assume ||
                 Intr->getIntrinsicID() == Intrinsic::sideeffect)
               continue;
           }
           if (Call->mayHaveSideEffects())
             break;
 
           if (Call->isConvergent())
             break;
 
           CI.insert(Call, VN);
-        } else if (HoistingGeps || !isa<GetElementPtrInst>(&I1))
-          // Do not hoist scalars past calls that may write to memory because
-          // that could result in spills later. geps are handled separately.
-          // TODO: We can relax this for targets like AArch64 as they have more
-          // registers than X86.
+        } else if (TTI.isRegisterRich() || !isa<GetElementPtrInst>(&I1))
+          // Do not hoist gep if the we concern about the register pressure.
+          // In that case, we only hoist gep if we can hoist the load/store
           II.insert(&I1, VN);
       }
     }
 
     HoistingPointList HPL;
     computeInsertionPoints(II.getVNTable(), HPL, InsKind::Scalar);
     computeInsertionPoints(LI.getVNTable(), HPL, InsKind::Load);
     computeInsertionPoints(SI.getVNTable(), HPL, InsKind::Store);
public:
   bool runOnFunction(Function &F) override {
     if (skipFunction(F))
       return false;
     auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
     auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
     auto &MD = getAnalysis<MemoryDependenceWrapperPass>().getMemDep();
     auto &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA();
+    auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
 
-    GVNHoist G(&DT, &PDT, &AA, &MD, &MSSA);
+    GVNHoist G(&DT, &PDT, &AA, &MD, &MSSA, TTI);
     return G.run(F);
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<TargetTransformInfoWrapperPass>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<PostDominatorTreeWrapperPass>();
     AU.addRequired<AAResultsWrapperPass>();
     AU.addRequired<MemoryDependenceWrapperPass>();
     AU.addRequired<MemorySSAWrapperPass>();
     AU.addPreserved<DominatorTreeWrapperPass>();
     AU.addPreserved<MemorySSAWrapperPass>();
     AU.addPreserved<GlobalsAAWrapperPass>();
   }
 };
 
 } // end namespace llvm
 
 PreservedAnalyses GVNHoistPass::run(Function &F, FunctionAnalysisManager &AM) {
   DominatorTree &DT = AM.getResult<DominatorTreeAnalysis>(F);
   PostDominatorTree &PDT = AM.getResult<PostDominatorTreeAnalysis>(F);
   AliasAnalysis &AA = AM.getResult<AAManager>(F);
   MemoryDependenceResults &MD = AM.getResult<MemoryDependenceAnalysis>(F);
   MemorySSA &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
-  GVNHoist G(&DT, &PDT, &AA, &MD, &MSSA);
+  TargetTransformInfo &TTI = AM.getResult<TargetIRAnalysis>(F);
+  GVNHoist G(&DT, &PDT, &AA, &MD, &MSSA, TTI);
   if (!G.run(F))
     return PreservedAnalyses::all();
 
   PreservedAnalyses PA;
   PA.preserve<DominatorTreeAnalysis>();
   PA.preserve<MemorySSAAnalysis>();
   PA.preserve<GlobalsAA>();
   return PA;