[LoopDataPrefetch/Aarch64] Allow selective prefetching of large-strided accesses

[anemet]

Summary

And use this TTI for Cyclone. As it was explained in the original RFC
(http://thread.gmane.org/gmane.comp.compilers.llvm.devel/92758), the HW
prefetcher work up to 2KB strides.

I am also adding tests for this and the previous change (D17943):

• Cyclone prefetching accesses with a large stride
• Cyclone not prefetching accesses with a small stride
• Generic Aarch64 subtarget not prefetching either

[t.p.northover]

This looks reasonable to me.

Tim.

llvm/trunk/include/llvm/Analysis/TargetTransformInfo.h

public:
 
   /// \return The size of a cache line in bytes.
   unsigned getCacheLineSize() const;
 
   /// \return How much before a load we should place the prefetch instruction.
   /// This is currently measured in number of instructions.
   unsigned getPrefetchDistance() const;
 
+  /// \return Some HW prefetchers can handle accesses up to a certain constant
+  /// stride.  This is the minimum stride in bytes where it makes sense to start
+  /// adding SW prefetches.  The default is 1, i.e. prefetch with any stride.
+  unsigned getMinPrefetchStride() const;
+
   /// \return The maximum interleave factor that any transform should try to
   /// perform for this target. This number depends on the level of parallelism
   /// and the number of execution units in the CPU.
   unsigned getMaxInterleaveFactor(unsigned VF) const;
 
   /// \return The expected cost of arithmetic ops, such as mul, xor, fsub, etc.
   int getArithmeticInstrCost(
       unsigned Opcode, Type *Ty, OperandValueKind Opd1Info = OK_AnyValue,
public:
   virtual int getIntImmCost(unsigned Opc, unsigned Idx, const APInt &Imm,
                             Type *Ty) = 0;
   virtual int getIntImmCost(Intrinsic::ID IID, unsigned Idx, const APInt &Imm,
                             Type *Ty) = 0;
   virtual unsigned getNumberOfRegisters(bool Vector) = 0;
   virtual unsigned getRegisterBitWidth(bool Vector) = 0;
   virtual unsigned getCacheLineSize() = 0;
   virtual unsigned getPrefetchDistance() = 0;
+  virtual unsigned getMinPrefetchStride() = 0;
   virtual unsigned getMaxInterleaveFactor(unsigned VF) = 0;
   virtual unsigned
   getArithmeticInstrCost(unsigned Opcode, Type *Ty, OperandValueKind Opd1Info,
                          OperandValueKind Opd2Info,
                          OperandValueProperties Opd1PropInfo,
                          OperandValueProperties Opd2PropInfo) = 0;
   virtual int getShuffleCost(ShuffleKind Kind, Type *Tp, int Index,
                              Type *SubTp) = 0;
public:
   }
   unsigned getRegisterBitWidth(bool Vector) override {
     return Impl.getRegisterBitWidth(Vector);
   }
   unsigned getCacheLineSize() override {
     return Impl.getCacheLineSize();
   }
   unsigned getPrefetchDistance() override { return Impl.getPrefetchDistance(); }
+  unsigned getMinPrefetchStride() override {
+    return Impl.getMinPrefetchStride();
+  }
   unsigned getMaxInterleaveFactor(unsigned VF) override {
     return Impl.getMaxInterleaveFactor(VF);
   }
   unsigned
   getArithmeticInstrCost(unsigned Opcode, Type *Ty, OperandValueKind Opd1Info,
                          OperandValueKind Opd2Info,
                          OperandValueProperties Opd1PropInfo,
                          OperandValueProperties Opd2PropInfo) override {

llvm/trunk/include/llvm/Analysis/TargetTransformInfoImpl.h

public:
   unsigned getNumberOfRegisters(bool Vector) { return 8; }
 
   unsigned getRegisterBitWidth(bool Vector) { return 32; }
 
   unsigned getCacheLineSize() { return 0; }
 
   unsigned getPrefetchDistance() { return 0; }
 
+  unsigned getMinPrefetchStride() { return 1; }
+
   unsigned getMaxInterleaveFactor(unsigned VF) { return 1; }
 
   unsigned getArithmeticInstrCost(unsigned Opcode, Type *Ty,
                                   TTI::OperandValueKind Opd1Info,
                                   TTI::OperandValueKind Opd2Info,
                                   TTI::OperandValueProperties Opd1PropInfo,
                                   TTI::OperandValueProperties Opd2PropInfo) {
     return 1;

llvm/trunk/lib/Analysis/TargetTransformInfo.cpp

 unsigned TargetTransformInfo::getCacheLineSize() const {
   return TTIImpl->getCacheLineSize();
 }
 
 unsigned TargetTransformInfo::getPrefetchDistance() const {
   return TTIImpl->getPrefetchDistance();
 }
 
+unsigned TargetTransformInfo::getMinPrefetchStride() const {
+  return TTIImpl->getMinPrefetchStride();
+}
+
 unsigned TargetTransformInfo::getMaxInterleaveFactor(unsigned VF) const {
   return TTIImpl->getMaxInterleaveFactor(VF);
 }
 
 int TargetTransformInfo::getArithmeticInstrCost(
     unsigned Opcode, Type *Ty, OperandValueKind Opd1Info,
     OperandValueKind Opd2Info, OperandValueProperties Opd1PropInfo,
     OperandValueProperties Opd2PropInfo) const {

llvm/trunk/lib/Target/AArch64/AArch64TargetTransformInfo.h

public:
 
   int getInterleavedMemoryOpCost(unsigned Opcode, Type *VecTy, unsigned Factor,
                                  ArrayRef<unsigned> Indices, unsigned Alignment,
                                  unsigned AddressSpace);
 
   unsigned getCacheLineSize();
 
   unsigned getPrefetchDistance();
+
+  unsigned getMinPrefetchStride();
   /// @}
 };
 
 } // end namespace llvm
 
 #endif

llvm/trunk/lib/Target/AArch64/AArch64TargetTransformInfo.cpp

 
 #define DEBUG_TYPE "aarch64tti"
 
 static cl::opt<unsigned> CyclonePrefetchDistance(
     "cyclone-prefetch-distance",
     cl::desc("Number of instructions to prefetch ahead for Cyclone"),
     cl::init(280), cl::Hidden);
 
+// The HW prefetcher handles accesses with strides up to 2KB.
+static cl::opt<unsigned> CycloneMinPrefetchStride(
+    "cyclone-min-prefetch-stride",
+    cl::desc("Min stride to add prefetches for Cyclone"),
+    cl::init(2048), cl::Hidden);
+
 /// \brief Calculate the cost of materializing a 64-bit value. This helper
 /// method might only calculate a fraction of a larger immediate. Therefore it
 /// is valid to return a cost of ZERO.
 int AArch64TTIImpl::getIntImmCost(int64_t Val) {
   // Check if the immediate can be encoded within an instruction.
   if (Val == 0 || AArch64_AM::isLogicalImmediate(Val, 64))
     return 0;
 
unsigned AArch64TTIImpl::getCacheLineSize() {
   return BaseT::getCacheLineSize();
 }
 
 unsigned AArch64TTIImpl::getPrefetchDistance() {
   if (ST->isCyclone())
     return CyclonePrefetchDistance;
   return BaseT::getPrefetchDistance();
 }
+
+unsigned AArch64TTIImpl::getMinPrefetchStride() {
+  if (ST->isCyclone())
+    return CycloneMinPrefetchStride;
+  return BaseT::getMinPrefetchStride();
+}

llvm/trunk/lib/Transforms/Scalar/LoopDataPrefetch.cpp

void getAnalysisUsage(AnalysisUsage &AU) const override {
       // this pass changes nothing).
       // AU.addPreserved<ScalarEvolutionWrapperPass>();
       AU.addRequired<TargetTransformInfoWrapperPass>();
     }
 
     bool runOnFunction(Function &F) override;
     bool runOnLoop(Loop *L);
 
+    /// \brief Check if the the stride of the accesses is large enough to
+    /// warrant a prefetch.
+    bool isStrideLargeEnough(const SCEVAddRecExpr *AR);
+
   private:
     AssumptionCache *AC;
     LoopInfo *LI;
     ScalarEvolution *SE;
     const TargetTransformInfo *TTI;
     const DataLayout *DL;
   };
 }
 
 char LoopDataPrefetch::ID = 0;
 INITIALIZE_PASS_BEGIN(LoopDataPrefetch, "loop-data-prefetch",
                       "Loop Data Prefetch", false, false)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 INITIALIZE_PASS_END(LoopDataPrefetch, "loop-data-prefetch",
                     "Loop Data Prefetch", false, false)
 
 FunctionPass *llvm::createLoopDataPrefetchPass() { return new LoopDataPrefetch(); }
 
+bool LoopDataPrefetch::isStrideLargeEnough(const SCEVAddRecExpr *AR) {
+  unsigned TargetMinStride = TTI->getMinPrefetchStride();
+  // No need to check if any stride goes.
+  if (TargetMinStride <= 1)
+    return true;
+
+  const auto *ConstStride = dyn_cast<SCEVConstant>(AR->getStepRecurrence(*SE));
+  // If MinStride is set, don't prefetch unless we can ensure that stride is
+  // larger.
+  if (!ConstStride)
+    return false;
+
+  unsigned AbsStride = std::abs(ConstStride->getAPInt().getSExtValue());
+  return TargetMinStride <= AbsStride;
+}
+
 bool LoopDataPrefetch::runOnFunction(Function &F) {
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
   DL = &F.getParent()->getDataLayout();
   AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
   TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
 
   // If PrefetchDistance is not set, don't run the pass.  This gives an
for (BasicBlock::iterator J = (*I)->begin(), JE = (*I)->end();
       if (L->isLoopInvariant(PtrValue))
         continue;
 
       const SCEV *LSCEV = SE->getSCEV(PtrValue);
       const SCEVAddRecExpr *LSCEVAddRec = dyn_cast<SCEVAddRecExpr>(LSCEV);
       if (!LSCEVAddRec)
         continue;
 
+      // Check if the the stride of the accesses is large enough to warrant a
+      // prefetch.
+      if (!isStrideLargeEnough(LSCEVAddRec))
+        continue;
+
       // We don't want to double prefetch individual cache lines. If this load
       // is known to be within one cache line of some other load that has
       // already been prefetched, then don't prefetch this one as well.
       bool DupPref = false;
       for (SmallVector<std::pair<Instruction *, const SCEVAddRecExpr *>,
              16>::iterator K = PrefLoads.begin(), KE = PrefLoads.end();
            K != KE; ++K) {
         const SCEV *PtrDiff = SE->getMinusSCEV(LSCEVAddRec, K->second);

llvm/trunk/test/Transforms/LoopDataPrefetch/AArch64/large-stride.ll

+; RUN: opt -mcpu=cyclone -mtriple=arm64-apple-ios -loop-data-prefetch -S < %s | FileCheck %s --check-prefix=LARGE_PREFETCH --check-prefix=ALL
+; RUN: opt -mcpu=generic -mtriple=arm64-apple-ios -loop-data-prefetch -S < %s | FileCheck %s --check-prefix=NO_LARGE_PREFETCH --check-prefix=ALL
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-n32:64-S128"
+
+; ALL-LABEL: @small_stride(
+define void @small_stride(double* nocapture %a, double* nocapture readonly %b) {
+entry:
+  br label %for.body
+
+; ALL: for.body:
+for.body:                                         ; preds = %for.body, %entry
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %arrayidx = getelementptr inbounds double, double* %b, i64 %indvars.iv
+; ALL-NOT: call void @llvm.prefetch
+  %0 = load double, double* %arrayidx, align 8
+  %add = fadd double %0, 1.000000e+00
+  %arrayidx2 = getelementptr inbounds double, double* %a, i64 %indvars.iv
+  store double %add, double* %arrayidx2, align 8
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, 1600
+  br i1 %exitcond, label %for.end, label %for.body
+
+; ALL: for.end:
+for.end:                                          ; preds = %for.body
+  ret void
+}
+
+; ALL-LABEL: @large_stride(
+define void @large_stride(double* nocapture %a, double* nocapture readonly %b) {
+entry:
+  br label %for.body
+
+; ALL: for.body:
+for.body:                                         ; preds = %for.body, %entry
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %arrayidx = getelementptr inbounds double, double* %b, i64 %indvars.iv
+; LARGE_PREFETCH: call void @llvm.prefetch
+; NO_LARGE_PREFETCH-NOT: call void @llvm.prefetch
+  %0 = load double, double* %arrayidx, align 8
+  %add = fadd double %0, 1.000000e+00
+  %arrayidx2 = getelementptr inbounds double, double* %a, i64 %indvars.iv
+  store double %add, double* %arrayidx2, align 8
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 300
+  %exitcond = icmp eq i64 %indvars.iv.next, 160000
+  br i1 %exitcond, label %for.end, label %for.body
+
+; ALL: for.end:
+for.end:                                          ; preds = %for.body
+  ret void
+}

llvm/trunk/test/Transforms/LoopDataPrefetch/AArch64/lit.local.cfg

+config.suffixes = ['.ll']
+
+if not 'AArch64' in config.root.targets:
+    config.unsupported = True