[HardwareLoops] NFC - move some hardware loop judgement code to a common place for other using

[shchenz]

Summary

Need to get conclusion that whether the loop can be converted to a hardware loop in some previous pass like LSR.

Move some code to structure HardwareLoopInfo, so that other pass can use it. This is a NFC patch.

Whole picture can be found in https://reviews.llvm.org/D63477

[samparker]

LGTM.

llvm/include/llvm/Analysis/TargetTransformInfo.h

 #define LLVM_ANALYSIS_TARGETTRANSFORMINFO_H
 
 #include "llvm/ADT/Optional.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/AtomicOrdering.h"
 #include "llvm/Support/DataTypes.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/ScalarEvolution.h"
+#include "llvm/IR/Dominators.h"
 #include <functional>
 
 namespace llvm {
 
 namespace Intrinsic {
 enum ID : unsigned;
 }
 
struct MemIntrinsicInfo {
   bool IsVolatile = false;
 
   bool isUnordered() const {
     return (Ordering == AtomicOrdering::NotAtomic ||
             Ordering == AtomicOrdering::Unordered) && !IsVolatile;
   }
 };
 
+/// Attributes of a target dependent hardware loop.
+struct HardwareLoopInfo {
+  HardwareLoopInfo() = delete;
+  HardwareLoopInfo(Loop *L) : L(L) {}
+  Loop *L = nullptr;
+  BasicBlock *ExitBlock = nullptr;
+  BranchInst *ExitBranch = nullptr;
+  const SCEV *ExitCount = nullptr;
+  IntegerType *CountType = nullptr;
+  Value *LoopDecrement = nullptr; // Decrement the loop counter by this
+                                  // value in every iteration.
+  bool IsNestingLegal = false;    // Can a hardware loop be a parent to
+                                  // another hardware loop?
+  bool CounterInReg = false;      // Should loop counter be updated in
+                                  // the loop via a phi?
+  bool isHardwareLoopCandidate(ScalarEvolution &SE, LoopInfo &LI,
+                               DominatorTree &DT, bool ForceNestedLoop = false,
+                               bool ForceHardwareLoopPHI = false);
+};
+
 /// This pass provides access to the codegen interfaces that are needed
 /// for IR-level transformations.
 class TargetTransformInfo {
 public:
   /// Construct a TTI object using a type implementing the \c Concept
   /// API below.
   ///
   /// This is used by targets to construct a TTI wrapping their target-specific
public:
   };
 
   /// 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;
 
-  /// Attributes of a target dependent hardware loop.
-  struct HardwareLoopInfo {
-    HardwareLoopInfo()        = delete;
-    HardwareLoopInfo(Loop *L) : L(L) { }
-    Loop *L                   = nullptr;
-    BasicBlock *ExitBlock     = nullptr;
-    BranchInst *ExitBranch    = nullptr;
-    const SCEV *ExitCount     = nullptr;
-    IntegerType *CountType    = nullptr;
-    Value *LoopDecrement      = nullptr;  // Decrement the loop counter by this
-                                          // value in every iteration.
-    bool IsNestingLegal       = false;    // Can a hardware loop be a parent to
-                                          // another hardware loop?
-    bool CounterInReg         = false;    // Should loop counter be updated in
-                                          // the loop via a phi?
-  };
-
   /// Query the target whether it would be profitable to convert the given loop
   /// into a hardware loop.
   bool isHardwareLoopProfitable(Loop *L, ScalarEvolution &SE,
                                 AssumptionCache &AC,
                                 TargetLibraryInfo *LibInfo,
                                 HardwareLoopInfo &HWLoopInfo) const;
 
   /// @}

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

if (Name == "pow" || Name == "powf" || Name == "powl" || Name == "exp2" ||
       return false;
 
     return true;
   }
 
   bool isHardwareLoopProfitable(Loop *L, ScalarEvolution &SE,
                                 AssumptionCache &AC,
                                 TargetLibraryInfo *LibInfo,
-                                TTI::HardwareLoopInfo &HWLoopInfo) {
+                                HardwareLoopInfo &HWLoopInfo) {
     return false;
   }
 
   void getUnrollingPreferences(Loop *, ScalarEvolution &,
                                TTI::UnrollingPreferences &) {}
 
   bool isLegalAddImmediate(int64_t Imm) { return false; }
 

llvm/include/llvm/CodeGen/BasicTTIImpl.h

void getUnrollingPreferences(Loop *L, ScalarEvolution &SE,
     // Set number of instructions optimized when "back edge"
     // becomes "fall through" to default value of 2.
     UP.BEInsns = 2;
   }
 
   bool isHardwareLoopProfitable(Loop *L, ScalarEvolution &SE,
                                 AssumptionCache &AC,
                                 TargetLibraryInfo *LibInfo,
-                                TTI::HardwareLoopInfo &HWLoopInfo) {
+                                HardwareLoopInfo &HWLoopInfo) {
     return BaseT::isHardwareLoopProfitable(L, SE, AC, LibInfo, HWLoopInfo);
   }
 
   int getInstructionLatency(const Instruction *I) {
     if (isa<LoadInst>(I))
       return getST()->getSchedModel().DefaultLoadLatency;
 
     return BaseT::getInstructionLatency(I);

llvm/lib/Analysis/TargetTransformInfo.cpp

 ///
 /// This is used when no target specific information is available.
 struct NoTTIImpl : TargetTransformInfoImplCRTPBase<NoTTIImpl> {
   explicit NoTTIImpl(const DataLayout &DL)
       : TargetTransformInfoImplCRTPBase<NoTTIImpl>(DL) {}
 };
 }
 
+bool HardwareLoopInfo::isHardwareLoopCandidate(ScalarEvolution &SE,
+                                               LoopInfo &LI, DominatorTree &DT,
+                                               bool ForceNestedLoop,
+                                               bool ForceHardwareLoopPHI) {
+  SmallVector<BasicBlock *, 4> ExitingBlocks;
+  L->getExitingBlocks(ExitingBlocks);
+
+  for (SmallVectorImpl<BasicBlock *>::iterator I = ExitingBlocks.begin(),
+                                               IE = ExitingBlocks.end();
+       I != IE; ++I) {
+    BasicBlock *BB = *I;
+
+    // If we pass the updated counter back through a phi, we need to know
+    // which latch the updated value will be coming from.
+    if (!L->isLoopLatch(BB)) {
+      if (ForceHardwareLoopPHI || CounterInReg)
+        continue;
+    }
+
+    const SCEV *EC = SE.getExitCount(L, BB);
+    if (isa<SCEVCouldNotCompute>(EC))
+      continue;
+    if (const SCEVConstant *ConstEC = dyn_cast<SCEVConstant>(EC)) {
+      if (ConstEC->getValue()->isZero())
+        continue;
+    } else if (!SE.isLoopInvariant(EC, L))
+      continue;
+
+    if (SE.getTypeSizeInBits(EC->getType()) > CountType->getBitWidth())
+      continue;
+
+    // If this exiting block is contained in a nested loop, it is not eligible
+    // for insertion of the branch-and-decrement since the inner loop would
+    // end up messing up the value in the CTR.
+    if (!IsNestingLegal && LI.getLoopFor(BB) != L && !ForceNestedLoop)
+      continue;
+
+    // We now have a loop-invariant count of loop iterations (which is not the
+    // constant zero) for which we know that this loop will not exit via this
+    // existing block.
+
+    // We need to make sure that this block will run on every loop iteration.
+    // For this to be true, we must dominate all blocks with backedges. Such
+    // blocks are in-loop predecessors to the header block.
+    bool NotAlways = false;
+    for (pred_iterator PI = pred_begin(L->getHeader()),
+                       PIE = pred_end(L->getHeader());
+         PI != PIE; ++PI) {
+      if (!L->contains(*PI))
+        continue;
+
+      if (!DT.dominates(*I, *PI)) {
+        NotAlways = true;
+        break;
+      }
+    }
+
+    if (NotAlways)
+      continue;
+
+    // Make sure this blocks ends with a conditional branch.
+    Instruction *TI = BB->getTerminator();
+    if (!TI)
+      continue;
+
+    if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
+      if (!BI->isConditional())
+        continue;
+
+      ExitBranch = BI;
+    } else
+      continue;
+
+    // Note that this block may not be the loop latch block, even if the loop
+    // has a latch block.
+    ExitBlock = *I;
+    ExitCount = EC;
+    break;
+  }
+
+  if (!ExitBlock)
+    return false;
+  return true;
+}
+
 TargetTransformInfo::TargetTransformInfo(const DataLayout &DL)
     : TTIImpl(new Model<NoTTIImpl>(NoTTIImpl(DL))) {}
 
 TargetTransformInfo::~TargetTransformInfo() {}
 
 TargetTransformInfo::TargetTransformInfo(TargetTransformInfo &&Arg)
     : TTIImpl(std::move(Arg.TTIImpl)) {}
 

llvm/lib/CodeGen/HardwareLoops.cpp

void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.addRequired<TargetTransformInfoWrapperPass>();
     }
 
     // Try to convert the given Loop into a hardware loop.
     bool TryConvertLoop(Loop *L);
 
     // Given that the target believes the loop to be profitable, try to
     // convert it.
-    bool TryConvertLoop(TTI::HardwareLoopInfo &HWLoopInfo);
+    bool TryConvertLoop(HardwareLoopInfo &HWLoopInfo);
 
   private:
     ScalarEvolution *SE = nullptr;
     LoopInfo *LI = nullptr;
     const DataLayout *DL = nullptr;
     const TargetTransformInfo *TTI = nullptr;
     DominatorTree *DT = nullptr;
     bool PreserveLCSSA = false;
class HardwareLoop {
     // loop_decrement_reg.
     PHINode *InsertPHICounter(Value *NumElts, Value *EltsRem);
 
     // Create a new cmp, that checks the returned value of loop_decrement*,
     // and update the exit branch to use it.
     void UpdateBranch(Value *EltsRem);
 
   public:
-    HardwareLoop(TTI::HardwareLoopInfo &Info, ScalarEvolution &SE,
+    HardwareLoop(HardwareLoopInfo &Info, ScalarEvolution &SE,
                  const DataLayout &DL) :
       SE(SE), DL(DL), L(Info.L), M(L->getHeader()->getModule()),
       ExitCount(Info.ExitCount),
       CountType(Info.CountType),
       ExitBranch(Info.ExitBranch),
       LoopDecrement(Info.LoopDecrement),
       UsePHICounter(Info.CounterInReg) { }
 
if (TryConvertLoop(*I))
       return true; // Stop search.
 
   // Bail out if the loop has irreducible control flow.
   LoopBlocksRPO RPOT(L);
   RPOT.perform(LI);
   if (containsIrreducibleCFG<const BasicBlock *>(RPOT, *LI))
     return false;
 
-  TTI::HardwareLoopInfo HWLoopInfo(L);
+  HardwareLoopInfo HWLoopInfo(L);
   if (TTI->isHardwareLoopProfitable(L, *SE, *AC, LibInfo, HWLoopInfo) ||
       ForceHardwareLoops) {
 
     // Allow overriding of the counter width and loop decrement value.
     if (CounterBitWidth.getNumOccurrences())
       HWLoopInfo.CountType =
         IntegerType::get(M->getContext(), CounterBitWidth);
 
     if (LoopDecrement.getNumOccurrences())
       HWLoopInfo.LoopDecrement =
         ConstantInt::get(HWLoopInfo.CountType, LoopDecrement);
 
     MadeChange |= TryConvertLoop(HWLoopInfo);
     return MadeChange && (!HWLoopInfo.IsNestingLegal && !ForceNestedLoop);
   }
 
   return false;
 }
 
-bool HardwareLoops::TryConvertLoop(TTI::HardwareLoopInfo &HWLoopInfo) {
+bool HardwareLoops::TryConvertLoop(HardwareLoopInfo &HWLoopInfo) {
 
   Loop *L = HWLoopInfo.L;
   LLVM_DEBUG(dbgs() << "HWLoops: Try to convert profitable loop: " << *L);
 
-  SmallVector<BasicBlock*, 4> ExitingBlocks;
-  L->getExitingBlocks(ExitingBlocks);
-
-  for (SmallVectorImpl<BasicBlock *>::iterator I = ExitingBlocks.begin(),
-       IE = ExitingBlocks.end(); I != IE; ++I) {
-    BasicBlock *BB = *I;
-
-    // If we pass the updated counter back through a phi, we need to know
-    // which latch the updated value will be coming from.
-    if (!L->isLoopLatch(BB)) {
-      if ((ForceHardwareLoopPHI.getNumOccurrences() && ForceHardwareLoopPHI) ||
-          HWLoopInfo.CounterInReg)
-        continue;
-    }
-
-    const SCEV *EC = SE->getExitCount(L, BB);
-    if (isa<SCEVCouldNotCompute>(EC))
-      continue;
-    if (const SCEVConstant *ConstEC = dyn_cast<SCEVConstant>(EC)) {
-      if (ConstEC->getValue()->isZero())
-        continue;
-    } else if (!SE->isLoopInvariant(EC, L))
-      continue;
-
-    if (SE->getTypeSizeInBits(EC->getType()) >
-        HWLoopInfo.CountType->getBitWidth())
-      continue;
-
-    // If this exiting block is contained in a nested loop, it is not eligible
-    // for insertion of the branch-and-decrement since the inner loop would
-    // end up messing up the value in the CTR.
-    if (!HWLoopInfo.IsNestingLegal && LI->getLoopFor(BB) != L &&
-        !ForceNestedLoop)
-      continue;
-
-    // We now have a loop-invariant count of loop iterations (which is not the
-    // constant zero) for which we know that this loop will not exit via this
-    // existing block.
-
-    // We need to make sure that this block will run on every loop iteration.
-    // For this to be true, we must dominate all blocks with backedges. Such
-    // blocks are in-loop predecessors to the header block.
-    bool NotAlways = false;
-    for (pred_iterator PI = pred_begin(L->getHeader()),
-         PIE = pred_end(L->getHeader()); PI != PIE; ++PI) {
-      if (!L->contains(*PI))
-        continue;
-
-      if (!DT->dominates(*I, *PI)) {
-        NotAlways = true;
-        break;
-      }
-    }
-
-    if (NotAlways)
-      continue;
-
-    // Make sure this blocks ends with a conditional branch.
-    Instruction *TI = BB->getTerminator();
-    if (!TI)
-      continue;
-
-    if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
-      if (!BI->isConditional())
-        continue;
-
-      HWLoopInfo.ExitBranch = BI;
-    } else
-      continue;
-
-    // Note that this block may not be the loop latch block, even if the loop
-    // has a latch block.
-    HWLoopInfo.ExitBlock = *I;
-    HWLoopInfo.ExitCount = EC;
-    break;
-  }
-
-  if (!HWLoopInfo.ExitBlock)
+  if (!HWLoopInfo.isHardwareLoopCandidate(*SE, *LI, *DT, ForceNestedLoop,
+                                          ForceHardwareLoopPHI))
     return false;
 
+  assert(
+      (HWLoopInfo.ExitBlock && HWLoopInfo.ExitBranch && HWLoopInfo.ExitCount) &&
+      "Hardware Loop must have set exit info.");
+
   BasicBlock *Preheader = L->getLoopPreheader();
 
   // If we don't have a preheader, then insert one.
   if (!Preheader)
     Preheader = InsertPreheaderForLoop(L, DT, LI, nullptr, PreserveLCSSA);
   if (!Preheader)
     return false;
 

llvm/lib/Target/ARM/ARMTargetTransformInfo.h

int getInterleavedMemoryOpCost(unsigned Opcode, Type *VecTy, unsigned Factor,
                                  unsigned AddressSpace,
                                  bool UseMaskForCond = false,
                                  bool UseMaskForGaps = false);
 
   bool isLoweredToCall(const Function *F);
   bool isHardwareLoopProfitable(Loop *L, ScalarEvolution &SE,
                                 AssumptionCache &AC,
                                 TargetLibraryInfo *LibInfo,
-                                TTI::HardwareLoopInfo &HWLoopInfo);
+                                HardwareLoopInfo &HWLoopInfo);
 
   void getUnrollingPreferences(Loop *L, ScalarEvolution &SE,
                                TTI::UnrollingPreferences &UP);
 
   bool shouldBuildLookupTablesForConstant(Constant *C) const {
     // In the ROPI and RWPI relocation models we can't have pointers to global
     // variables or functions in constant data, so don't convert switches to
     // lookup tables if any of the values would need relocation.

llvm/lib/Target/ARM/ARMTargetTransformInfo.cpp

bool ARMTTIImpl::isLoweredToCall(const Function *F) {
   }
 
   return BaseT::isLoweredToCall(F);
 }
 
 bool ARMTTIImpl::isHardwareLoopProfitable(Loop *L, ScalarEvolution &SE,
                                           AssumptionCache &AC,
                                           TargetLibraryInfo *LibInfo,
-                                          TTI::HardwareLoopInfo &HWLoopInfo) {
+                                          HardwareLoopInfo &HWLoopInfo) {
   // Low-overhead branches are only supported in the 'low-overhead branch'
   // extension of v8.1-m.
   if (!ST->hasLOB() || DisableLowOverheadLoops)
     return false;
 
   if (!SE.hasLoopInvariantBackedgeTakenCount(L))
     return false;
 

llvm/lib/Target/PowerPC/PPCTargetTransformInfo.h

int getIntImmCost(Intrinsic::ID IID, unsigned Idx, const APInt &Imm,
                     Type *Ty);
 
   unsigned getUserCost(const User *U, ArrayRef<const Value *> Operands);
 
   TTI::PopcntSupportKind getPopcntSupport(unsigned TyWidth);
   bool isHardwareLoopProfitable(Loop *L, ScalarEvolution &SE,
                                 AssumptionCache &AC,
                                 TargetLibraryInfo *LibInfo,
-                                TTI::HardwareLoopInfo &HWLoopInfo);
+                                HardwareLoopInfo &HWLoopInfo);
   void getUnrollingPreferences(Loop *L, ScalarEvolution &SE,
                                TTI::UnrollingPreferences &UP);
 
   /// @}
 
   /// \name Vector TTI Implementations
   /// @{
   bool useColdCCForColdCall(Function &F);

llvm/lib/Target/PowerPC/PPCTargetTransformInfo.cpp

#endif
   }
 
   return false;
 }
 
 bool PPCTTIImpl::isHardwareLoopProfitable(Loop *L, ScalarEvolution &SE,
                                           AssumptionCache &AC,
                                           TargetLibraryInfo *LibInfo,
-                                          TTI::HardwareLoopInfo &HWLoopInfo) {
+                                          HardwareLoopInfo &HWLoopInfo) {
   const PPCTargetMachine &TM = ST->getTargetMachine();
   TargetSchedModel SchedModel;
   SchedModel.init(ST);
 
   // Do not convert small short loops to CTR loop.
   unsigned ConstTripCount = SE.getSmallConstantTripCount(L);
   if (ConstTripCount && ConstTripCount < SmallCTRLoopThreshold) {
     SmallPtrSet<const Value *, 32> EphValues;