[LoopVectorize][AArch64] Enable ordered reductions by default for AArch64

[david-arm]

Summary

I have added a new TTI interface called enableOrderedReductions() that
controls whether or not ordered reductions should be enabled for a
given target. By default this returns false, whereas for AArch64 it
returns true and we rely upon the cost model to make sensible
vectorisation choices. It is still possible to override the new TTI
interface by setting the command line flag:

-force-ordered-reductions=true|false

I have added a new RUN line to show that we use ordered reductions by
default for SVE and Neon:

Transforms/LoopVectorize/AArch64/strict-fadd.ll
Transforms/LoopVectorize/AArch64/scalable-strict-fadd.ll

[david-arm]

I wonder if this might be something of interest for other targets, not just AArch64?

[dmgreen]

Do you have any performance results?

[david-arm]

• Changed the patch to only enable strict (ordered) reductions for AArch64 when SVE is enabled.

[david-arm]

Hi @dmgreen, we've decided for now to only enable this by default for AArch64 when SVE is enabled as this is lower risk. We are currently still collecting performance data for the fixed-width vectorisation case when SVE is enabled.

[david-arm]

In D106653#2907824, @david-arm wrote:

Hi @dmgreen, we've decided for now to only enable this by default for AArch64 when SVE is enabled as this is lower risk. We are currently still collecting performance data for the fixed-width vectorisation case when SVE is enabled.

Sorry, that should really be "collecting performance data for the fixed-width vectorisation case when strict reductions are forced".

[dmgreen]

What do you mean by "lower risk"? Do you have performance numbers for SVE? Or is the cost so high that in practice they are never generated?

[sdesmalen]

In D106653#2909467, @dmgreen wrote:

What do you mean by "lower risk"? Do you have performance numbers for SVE? Or is the cost so high that in practice they are never generated?

The end-goal is to enable strict reductions by default for all targets so that buildbots guard the functionality and hopefully give some performance benefit as well. The cost-model must be conservative enough to avoid any regressions, but still let through loops where there is an obvious benefit. At that point, we can start tuning the cost-model to let through more cases when that helps performance.

Our other motivation is around making LLVM 13 an experimental compiler for VLA auto-vectorization. We specifically want to enable strict reductions by default in LLVM 13 for vector-length-agnostic SVE, because this is a new vectorization capability which SVE can handle. The cost-model doesn't really matter too much at this point, because VLA auto-vec is experimental and little effort has yet been made to improve code-quality, so it's unlikely that strict-reductions will make a dent.

To achieve our end-goal of enabling strict reductions by default for all targets, we can do that in stages:

1. Enable it by default for VLA SVE (this patch)

We can enable it because performance doesn't really matter. It would mean this patch needs to be updated to (temporarily) give a high/invalid cost for ordered reductions when the type is a FixedVectorType, so that we don't accidentally introduce any regressions for e.g. -mcpu=a64fx when -scalable-vectorization=on|preferred is not specified.

2. Enable it by default for AArch64.

We have performed SPEC2K6 measurements where we can see that the cost-model holds up and where performance across the board is similar or better, with only very minor regressions (<1%). We want to do a bit more benchmarking (such as measuring on different AArch64 machines) to present numbers we're confident about.

3. Enable it by default for other targets.

This will require measurements on targets other than AArch64.

Does that sound like a sensible approach?

[dmgreen]

Turning this on sounds good, so long as we do our due-diligence and check it's OK performance wise. I just did some experiments and it seemed fine-ish, but they were only very small exampled run on a A510 and A710. So long as there was more than a single real vector operation, the benefits started overcoming the overheads.

A couple of high level comments though:

• I'm not a fan of -march=arm8-a+sve working differently to -march=armv8-a for non-sve related code. i.e "hasSVE" shouldn't be the trigger for allowing NEON inorder reductions, if they do not have anything to do with SVE. We should consider just jumping to step 2 and enabling it for all aarch64, so long as the performance results look OK and we are careful about regressions of course.
• It seems that the cost is so high under SVE that they will never be generated in practice. This suggests that enabling them will have little effect for either testing or performance.

[david-arm]

• Enabled ordered reductions by default for AArch64.
• Rebase.

[spatel]

llvm/test/Transforms/LoopVectorize/AArch64/scalable-strict-fadd.ll

5

Drive-by comment (checking my understanding) - we could add this RUN line with --check-prefix=CHECK-NOT-VECTORIZED as a preliminary commit and then update only the prefix to show the change in behavior with this patch?

[david-arm]

llvm/test/Transforms/LoopVectorize/AArch64/scalable-strict-fadd.ll

5

That sounds like a good idea! I'll commit a one line patch to do this and then rebase.

[david-arm]

• Rebase.

[david-arm]

Hi @dmgreen, so I have run SPEC2006 on a neoverse-n1 9 times without my patch and 9 times with when building with -O3, then compared the averages. Here is a summary of the results showing a few outliers (slowest at the top, fastest at the bottom):

Benchmark | Percentage Runtime Change (<0 = faster with ordered reductions)

453.povray: 0.3
464.h264ref: 0.1
462.libquantum: 0
...
450.soplex: -0.95
429.mcf: -1.22
482.sphinx3: -1.27
471.omnetpp: -1.51

Geometric mean: -0.45

Overall it looks like this slightly faster with ordered reductions enabled by default for AArch64.

[david-arm]

• Just spotted a bug in enableOrderedReductions and fixed it. This was fixed in the patch I was using for performance testing. :)

[dmgreen]

The numbers look good to me. With D108292 this LGTM. Thanks.

[pcc]

Hi David, it looks like this change caused an assertion failure. Can you please take a look?

> cat test.i
int a;
double b, c;
void d() {
  for (; a; a++) {
    b += c;
    c = a;
  }
}
> clang -O2 test.i --target=aarch64-linux
clang: ../llvm/lib/Transforms/Vectorize/VPlanValue.h:186: llvm::Value *llvm::VPValue::getLiveInIRValue(): Assertion `!getDef() && "VPValue is not a live-in; it is defined by a VPDef inside a VPlan"' failed.

[fhahn]

In D106653#2957702, @pcc wrote:

Hi David, it looks like this change caused an assertion failure. Can you please take a look?

> cat test.i
int a;
double b, c;
void d() {
  for (; a; a++) {
    b += c;
    c = a;
  }
}
> clang -O2 test.i --target=aarch64-linux
clang: ../llvm/lib/Transforms/Vectorize/VPlanValue.h:186: llvm::Value *llvm::VPValue::getLiveInIRValue(): Assertion `!getDef() && "VPValue is not a live-in; it is defined by a VPDef inside a VPlan"' failed.

Thanks for the report! I have a suspicion of what may be going wrong here. I'll revert the patch while I take a look.

[fhahn]

I recommitted the patch in d024a01511c1 after fixing the issue causing the revert in 9baed023b4b5

[david-arm]

In D106653#2959661, @fhahn wrote:

I recommitted the patch in d024a01511c1 after fixing the issue causing the revert in 9baed023b4b5

Hi @fhahn, thanks a lot for fixing this! I was on holiday Monday and Tuesday, only just saw the fallout now. :)

llvm/include/llvm/Analysis/TargetTransformInfo.h

public:
   /// Return true if the target supports masked gather.
   bool isLegalMaskedGather(Type *DataType, Align Alignment) const;
 
   /// Return true if the target supports masked compress store.
   bool isLegalMaskedCompressStore(Type *DataType) const;
   /// Return true if the target supports masked expand load.
   bool isLegalMaskedExpandLoad(Type *DataType) const;
 
+  /// Return true if we should be enabling ordered reductions for the target.
+  bool enableOrderedReductions() const;
+
   /// Return true if the target has a unified operation to calculate division
   /// and remainder. If so, the additional implicit multiplication and
   /// subtraction required to calculate a remainder from division are free. This
   /// can enable more aggressive transformations for division and remainder than
   /// would typically be allowed using throughput or size cost models.
   bool hasDivRemOp(Type *DataType, bool IsSigned) const;
 
   /// Return true if the given instruction (assumed to be a memory access
public:
   virtual bool isLegalMaskedStore(Type *DataType, Align Alignment) = 0;
   virtual bool isLegalMaskedLoad(Type *DataType, Align Alignment) = 0;
   virtual bool isLegalNTStore(Type *DataType, Align Alignment) = 0;
   virtual bool isLegalNTLoad(Type *DataType, Align Alignment) = 0;
   virtual bool isLegalMaskedScatter(Type *DataType, Align Alignment) = 0;
   virtual bool isLegalMaskedGather(Type *DataType, Align Alignment) = 0;
   virtual bool isLegalMaskedCompressStore(Type *DataType) = 0;
   virtual bool isLegalMaskedExpandLoad(Type *DataType) = 0;
+  virtual bool enableOrderedReductions() = 0;
   virtual bool hasDivRemOp(Type *DataType, bool IsSigned) = 0;
   virtual bool hasVolatileVariant(Instruction *I, unsigned AddrSpace) = 0;
   virtual bool prefersVectorizedAddressing() = 0;
   virtual InstructionCost getScalingFactorCost(Type *Ty, GlobalValue *BaseGV,
                                                int64_t BaseOffset,
                                                bool HasBaseReg, int64_t Scale,
                                                unsigned AddrSpace) = 0;
   virtual bool LSRWithInstrQueries() = 0;
bool isLegalMaskedGather(Type *DataType, Align Alignment) override {
     return Impl.isLegalMaskedGather(DataType, Alignment);
   }
   bool isLegalMaskedCompressStore(Type *DataType) override {
     return Impl.isLegalMaskedCompressStore(DataType);
   }
   bool isLegalMaskedExpandLoad(Type *DataType) override {
     return Impl.isLegalMaskedExpandLoad(DataType);
   }
+  bool enableOrderedReductions() override {
+    return Impl.enableOrderedReductions();
+  }
   bool hasDivRemOp(Type *DataType, bool IsSigned) override {
     return Impl.hasDivRemOp(DataType, IsSigned);
   }
   bool hasVolatileVariant(Instruction *I, unsigned AddrSpace) override {
     return Impl.hasVolatileVariant(I, AddrSpace);
   }
   bool prefersVectorizedAddressing() override {
     return Impl.prefersVectorizedAddressing();

llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

public:
   bool isLegalMaskedGather(Type *DataType, Align Alignment) const {
     return false;
   }
 
   bool isLegalMaskedCompressStore(Type *DataType) const { return false; }
 
   bool isLegalMaskedExpandLoad(Type *DataType) const { return false; }
 
+  bool enableOrderedReductions() const { return false; }
+
   bool hasDivRemOp(Type *DataType, bool IsSigned) const { return false; }
 
   bool hasVolatileVariant(Instruction *I, unsigned AddrSpace) const {
     return false;
   }
 
   bool prefersVectorizedAddressing() const { return true; }
 

llvm/lib/Analysis/TargetTransformInfo.cpp

 bool TargetTransformInfo::isLegalMaskedCompressStore(Type *DataType) const {
   return TTIImpl->isLegalMaskedCompressStore(DataType);
 }
 
 bool TargetTransformInfo::isLegalMaskedExpandLoad(Type *DataType) const {
   return TTIImpl->isLegalMaskedExpandLoad(DataType);
 }
 
+bool TargetTransformInfo::enableOrderedReductions() const {
+  return TTIImpl->enableOrderedReductions();
+}
+
 bool TargetTransformInfo::hasDivRemOp(Type *DataType, bool IsSigned) const {
   return TTIImpl->hasDivRemOp(DataType, IsSigned);
 }
 
 bool TargetTransformInfo::hasVolatileVariant(Instruction *I,
                                              unsigned AddrSpace) const {
   return TTIImpl->hasVolatileVariant(I, AddrSpace);
 }

llvm/lib/Target/AArch64/AArch64TargetTransformInfo.h

if (auto *DataTypeVTy = dyn_cast<VectorType>(DataType)) {
           cast<FixedVectorType>(DataTypeVTy)->getNumElements();
       unsigned EltSize = DataTypeVTy->getElementType()->getScalarSizeInBits();
       return NumElements > 1 && isPowerOf2_64(NumElements) && EltSize >= 8 &&
              EltSize <= 128 && isPowerOf2_64(EltSize);
     }
     return BaseT::isLegalNTStore(DataType, Alignment);
   }
 
+  bool enableOrderedReductions() const { true; }
+
   InstructionCost getInterleavedMemoryOpCost(
       unsigned Opcode, Type *VecTy, unsigned Factor, ArrayRef<unsigned> Indices,
       Align Alignment, unsigned AddressSpace,
       TTI::TargetCostKind CostKind = TTI::TCK_SizeAndLatency,
       bool UseMaskForCond = false, bool UseMaskForGaps = false);
 
   bool
   shouldConsiderAddressTypePromotion(const Instruction &I,

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

cl::desc("The maximum interleave count to use when interleaving a scalar "
              "reduction in a nested loop."));
 
 static cl::opt<bool>
     PreferInLoopReductions("prefer-inloop-reductions", cl::init(false),
                            cl::Hidden,
                            cl::desc("Prefer in-loop vector reductions, "
                                     "overriding the targets preference."));
 
-cl::opt<bool> ForceOrderedReductions(
+static cl::opt<bool> ForceOrderedReductions(
     "force-ordered-reductions", cl::init(false), cl::Hidden,
     cl::desc("Enable the vectorisation of loops with in-order (strict) "
              "FP reductions"));
 
 static cl::opt<bool> PreferPredicatedReductionSelect(
     "prefer-predicated-reduction-select", cl::init(false), cl::Hidden,
     cl::desc(
         "Prefer predicating a reduction operation over an after loop select."));
public:
   /// outside. In loop reductions are collected into InLoopReductionChains.
   void collectInLoopReductions();
 
   /// Returns true if we should use strict in-order reductions for the given
   /// RdxDesc. This is true if the -enable-strict-reductions flag is passed,
   /// the IsOrdered flag of RdxDesc is set and we do not allow reordering
   /// of FP operations.
   bool useOrderedReductions(const RecurrenceDescriptor &RdxDesc) {
-    return ForceOrderedReductions && !Hints->allowReordering() &&
-           RdxDesc.isOrdered();
+    return !Hints->allowReordering() && RdxDesc.isOrdered();
   }
 
   /// \returns The smallest bitwidth each instruction can be represented with.
   /// The vector equivalents of these instructions should be truncated to this
   /// type.
   const MapVector<Instruction *, uint64_t> &getMinimalBitwidths() const {
     return MinBWs;
   }
const RecurrenceDescriptor &RdxDesc =
       Legal->getReductionVars()[cast<PHINode>(ReductionPhi)];
 
   InstructionCost BaseCost = TTI.getArithmeticReductionCost(
       RdxDesc.getOpcode(), VectorTy, RdxDesc.getFastMathFlags(), CostKind);
 
   // If we're using ordered reductions then we can just return the base cost
   // here, since getArithmeticReductionCost calculates the full ordered
   // reduction cost when FP reassociation is not allowed.
-  if (useOrderedReductions(RdxDesc))
+  if (useOrderedReductions(RdxDesc)) {
     return BaseCost;
+  }
 
   // Get the operand that was not the reduction chain and match it to one of the
   // patterns, returning the better cost if it is found.
   Instruction *RedOp = RetI->getOperand(1) == LastChain
                            ? dyn_cast<Instruction>(RetI->getOperand(0))
                            : dyn_cast<Instruction>(RetI->getOperand(1));
 
   VectorTy = VectorType::get(I->getOperand(0)->getType(), VectorTy);
if (Hints.isPotentiallyUnsafe() &&
     reportVectorizationFailure(
         "Potentially unsafe FP op prevents vectorization",
         "loop not vectorized due to unsafe FP support.",
         "UnsafeFP", ORE, L);
     Hints.emitRemarkWithHints();
     return false;
   }
 
-  if (!LVL.canVectorizeFPMath(ForceOrderedReductions)) {
+  bool AllowOrderedReductions;
+  // If the flag is set, use that instead and override the TTI behaviour.
+  if (ForceOrderedReductions.getNumOccurrences() > 0)
+    AllowOrderedReductions = ForceOrderedReductions;
+  else
+    AllowOrderedReductions = TTI->enableOrderedReductions();
+  if (!LVL.canVectorizeFPMath(AllowOrderedReductions)) {
     ORE->emit([&]() {
       auto *ExactFPMathInst = Requirements.getExactFPInst();
       return OptimizationRemarkAnalysisFPCommute(DEBUG_TYPE, "CantReorderFPOps",
                                                  ExactFPMathInst->getDebugLoc(),
                                                  ExactFPMathInst->getParent())
              << "loop not vectorized: cannot prove it is safe to reorder "
                 "floating-point operations";
     });

llvm/test/Transforms/LoopVectorize/AArch64/scalable-strict-fadd.ll

 ; RUN: opt < %s -loop-vectorize -scalable-vectorization=on -mtriple aarch64-unknown-linux-gnu -mattr=+sve -force-ordered-reductions=false -hints-allow-reordering=false -S 2>%t | FileCheck %s --check-prefix=CHECK-NOT-VECTORIZED
 ; RUN: opt < %s -loop-vectorize -scalable-vectorization=on -mtriple aarch64-unknown-linux-gnu -mattr=+sve -force-ordered-reductions=false -hints-allow-reordering=true  -S 2>%t | FileCheck %s --check-prefix=CHECK-UNORDERED
 ; RUN: opt < %s -loop-vectorize -scalable-vectorization=on -mtriple aarch64-unknown-linux-gnu -mattr=+sve -force-ordered-reductions=true  -hints-allow-reordering=false -S 2>%t | FileCheck %s --check-prefix=CHECK-ORDERED
 ; RUN: opt < %s -loop-vectorize -scalable-vectorization=on -mtriple aarch64-unknown-linux-gnu -mattr=+sve -force-ordered-reductions=true  -hints-allow-reordering=true  -S 2>%t | FileCheck %s --check-prefix=CHECK-UNORDERED
+; RUN: opt < %s -loop-vectorize -scalable-vectorization=on -mtriple aarch64-unknown-linux-gnu -mattr=+sve -hints-allow-reordering=false  -S 2>%t | FileCheck %s --check-prefix=CHECK-ORDERED
 
 define float @fadd_strict(float* noalias nocapture readonly %a, i64 %n) {
 ; CHECK-ORDERED-LABEL: @fadd_strict
 ; CHECK-ORDERED: vector.body:
 ; CHECK-ORDERED: %[[VEC_PHI:.*]] = phi float [ 0.000000e+00, %vector.ph ], [ %[[RDX:.*]], %vector.body ]
 ; CHECK-ORDERED: %[[LOAD:.*]] = load <vscale x 8 x float>, <vscale x 8 x float>*
 ; CHECK-ORDERED: %[[RDX]] = call float @llvm.vector.reduce.fadd.nxv8f32(float %[[VEC_PHI]], <vscale x 8 x float> %[[LOAD]])
 ; CHECK-ORDERED: for.end

llvm/test/Transforms/LoopVectorize/AArch64/strict-fadd.ll

 ; RUN: opt < %s -loop-vectorize -mtriple aarch64-unknown-linux-gnu -force-ordered-reductions=false -hints-allow-reordering=false -S 2>%t | FileCheck %s --check-prefix=CHECK-NOT-VECTORIZED
 ; RUN: opt < %s -loop-vectorize -mtriple aarch64-unknown-linux-gnu -force-ordered-reductions=false -hints-allow-reordering=true  -S 2>%t | FileCheck %s --check-prefix=CHECK-UNORDERED
 ; RUN: opt < %s -loop-vectorize -mtriple aarch64-unknown-linux-gnu -force-ordered-reductions=true  -hints-allow-reordering=false -S 2>%t | FileCheck %s --check-prefix=CHECK-ORDERED
 ; RUN: opt < %s -loop-vectorize -mtriple aarch64-unknown-linux-gnu -force-ordered-reductions=true  -hints-allow-reordering=true  -S 2>%t | FileCheck %s --check-prefix=CHECK-UNORDERED
+; RUN: opt < %s -loop-vectorize -mtriple aarch64-unknown-linux-gnu -hints-allow-reordering=false -S 2>%t | FileCheck %s --check-prefix=CHECK-ORDERED
 
 define float @fadd_strict(float* noalias nocapture readonly %a, i64 %n) {
 ; CHECK-ORDERED-LABEL: @fadd_strict
 ; CHECK-ORDERED: vector.body:
 ; CHECK-ORDERED: %[[VEC_PHI:.*]] = phi float [ 0.000000e+00, %vector.ph ], [ %[[RDX:.*]], %vector.body ]
 ; CHECK-ORDERED: %[[LOAD:.*]] = load <8 x float>, <8 x float>*
 ; CHECK-ORDERED: %[[RDX]] = call float @llvm.vector.reduce.fadd.v8f32(float %[[VEC_PHI]], <8 x float> %[[LOAD]])
 ; CHECK-ORDERED: for.end