Disable loop unrolling in loop vectorization pass when VF is 1 on x86

[wmi]

Summary

The patch is to fix the problem described in https://llvm.org/bugs/show_bug.cgi?id=23217

Loop unrolling in loop vectorization pass has two kinds of benefits: 1. For loop which needs to be both vectorized and unrolled, the unrolling integrated with loop vectorization pass can generate less prologue/epilogue code. 2. unrolling in loop vectorization generates memory boundary check for unrolled loop version, which is useful for better scheduling on some architectures.

However, for x86, its performance is not very sensitive to compile time scheduling. So unrolling in loop vectorization when VF==1 will introduce extra cost of overflow check, memory boundary check and sometimes extra prologue/epilogue code when regular unroller will unroll the loop another time. These are harmful for performance on x86.

The patch disabled unrolling in loop vectorization pass when VF==1 on x86 architecture, by setting MaxInterleaveFactor to 1.

Performance neutral for spec2000. Google internal benchmarks: detection improved by 5% on sandybridge and 9% on westmere, saw improved by 1.5% on both platforms.

[rengolin]

Hi Wei,

The example you have shown would produce bad vectorized code on any architecture, I don't think anything you said (multiple unrolling and prologue loops) would make much difference on other archs. Maybe you're trying to fix a global problem locally, and creating some unnecessary constraints for the cases that do work.

However, your performance improvements are really impressive, so I think we ought to check other archs, and maybe try to detect the problematic case on a generic level?

cheers,
--renato

[hfinkel]

In D9515#166600, @rengolin wrote:

Hi Wei,

The example you have shown would produce bad vectorized code on any architecture, I don't think anything you said (multiple unrolling and prologue loops) would make much difference on other archs. Maybe you're trying to fix a global problem locally, and creating some unnecessary constraints for the cases that do work.

However, your performance improvements are really impressive, so I think we ought to check other archs, and maybe try to detect the problematic case on a generic level?

The problem is fairly generic, but does need per-target tuning. The problem is that interleaving can be quite beneficial for VF == 1 for in-order chips with fairly-long pipelines (especially for floating point). But on those architectures, you end up unrolling a lot to get good performance. On X86, the constraints are different. On X86 we can't unroll a lot (in some sense), because you're unrolling to fill the loop-stream detectors's associated dispatch buffer, and there is a large performance cliff if you make the loop not fit into the buffer. This all unrolling is minor and the extra prologues really hurt a lot.

This LGTM.

cheers,
--renato

[rengolin]

ok, cheers!

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

public:
   unsigned getNumberOfRegisters(bool Vector) const;
 
   /// \return The width of the largest scalar or vector register type.
   unsigned getRegisterBitWidth(bool Vector) 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() const;
+  unsigned getMaxInterleaveFactor(unsigned VF) const;
 
   /// \return The expected cost of arithmetic ops, such as mul, xor, fsub, etc.
   unsigned
   getArithmeticInstrCost(unsigned Opcode, Type *Ty,
                          OperandValueKind Opd1Info = OK_AnyValue,
                          OperandValueKind Opd2Info = OK_AnyValue,
                          OperandValueProperties Opd1PropInfo = OP_None,
                          OperandValueProperties Opd2PropInfo = OP_None) const;
public:
   virtual unsigned getFPOpCost(Type *Ty) = 0;
   virtual unsigned getIntImmCost(const APInt &Imm, Type *Ty) = 0;
   virtual unsigned getIntImmCost(unsigned Opc, unsigned Idx, const APInt &Imm,
                                  Type *Ty) = 0;
   virtual unsigned 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 getMaxInterleaveFactor() = 0;
+  virtual unsigned getMaxInterleaveFactor(unsigned VF) = 0;
   virtual unsigned
   getArithmeticInstrCost(unsigned Opcode, Type *Ty, OperandValueKind Opd1Info,
                          OperandValueKind Opd2Info,
                          OperandValueProperties Opd1PropInfo,
                          OperandValueProperties Opd2PropInfo) = 0;
   virtual unsigned getShuffleCost(ShuffleKind Kind, Type *Tp, int Index,
                                   Type *SubTp) = 0;
   virtual unsigned getCastInstrCost(unsigned Opcode, Type *Dst, Type *Src) = 0;
unsigned getIntImmCost(Intrinsic::ID IID, unsigned Idx, const APInt &Imm,
     return Impl.getIntImmCost(IID, Idx, Imm, Ty);
   }
   unsigned getNumberOfRegisters(bool Vector) override {
     return Impl.getNumberOfRegisters(Vector);
   }
   unsigned getRegisterBitWidth(bool Vector) override {
     return Impl.getRegisterBitWidth(Vector);
   }
-  unsigned getMaxInterleaveFactor() override {
-    return Impl.getMaxInterleaveFactor();
+  unsigned getMaxInterleaveFactor(unsigned VF) override {
+    return Impl.getMaxInterleaveFactor(VF);
   }
   unsigned
   getArithmeticInstrCost(unsigned Opcode, Type *Ty, OperandValueKind Opd1Info,
                          OperandValueKind Opd2Info,
                          OperandValueProperties Opd1PropInfo,
                          OperandValueProperties Opd2PropInfo) override {
     return Impl.getArithmeticInstrCost(Opcode, Ty, Opd1Info, Opd2Info,
                                        Opd1PropInfo, Opd2PropInfo);

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

unsigned getIntImmCost(Intrinsic::ID IID, unsigned Idx, const APInt &Imm,
                          Type *Ty) {
     return TTI::TCC_Free;
   }
 
   unsigned getNumberOfRegisters(bool Vector) { return 8; }
 
   unsigned getRegisterBitWidth(bool Vector) { return 32; }
 
-  unsigned getMaxInterleaveFactor() { 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/include/llvm/CodeGen/BasicTTIImpl.h

public:
 
   /// \name Vector TTI Implementations
   /// @{
 
   unsigned getNumberOfRegisters(bool Vector) { return 1; }
 
   unsigned getRegisterBitWidth(bool Vector) { return 32; }
 
-  unsigned getMaxInterleaveFactor() { return 1; }
+  unsigned getMaxInterleaveFactor(unsigned VF) { return 1; }
 
   unsigned getArithmeticInstrCost(
       unsigned Opcode, Type *Ty,
       TTI::OperandValueKind Opd1Info = TTI::OK_AnyValue,
       TTI::OperandValueKind Opd2Info = TTI::OK_AnyValue,
       TTI::OperandValueProperties Opd1PropInfo = TTI::OP_None,
       TTI::OperandValueProperties Opd2PropInfo = TTI::OP_None) {
     // Check if any of the operands are vector operands.

llvm/trunk/lib/Analysis/TargetTransformInfo.cpp

 unsigned TargetTransformInfo::getNumberOfRegisters(bool Vector) const {
   return TTIImpl->getNumberOfRegisters(Vector);
 }
 
 unsigned TargetTransformInfo::getRegisterBitWidth(bool Vector) const {
   return TTIImpl->getRegisterBitWidth(Vector);
 }
 
-unsigned TargetTransformInfo::getMaxInterleaveFactor() const {
-  return TTIImpl->getMaxInterleaveFactor();
+unsigned TargetTransformInfo::getMaxInterleaveFactor(unsigned VF) const {
+  return TTIImpl->getMaxInterleaveFactor(VF);
 }
 
 unsigned TargetTransformInfo::getArithmeticInstrCost(
     unsigned Opcode, Type *Ty, OperandValueKind Opd1Info,
     OperandValueKind Opd2Info, OperandValueProperties Opd1PropInfo,
     OperandValueProperties Opd2PropInfo) const {
   return TTIImpl->getArithmeticInstrCost(Opcode, Ty, Opd1Info, Opd2Info,
                                          Opd1PropInfo, Opd2PropInfo);

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

unsigned getRegisterBitWidth(bool Vector) {
     if (Vector) {
       if (ST->hasNEON())
         return 128;
       return 0;
     }
     return 64;
   }
 
-  unsigned getMaxInterleaveFactor();
+  unsigned getMaxInterleaveFactor(unsigned VF);
 
   unsigned getCastInstrCost(unsigned Opcode, Type *Dst, Type *Src);
 
   unsigned getVectorInstrCost(unsigned Opcode, Type *Val, unsigned Index);
 
   unsigned getArithmeticInstrCost(
       unsigned Opcode, Type *Ty,
       TTI::OperandValueKind Opd1Info = TTI::OK_AnyValue,

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

if (!I->isVectorTy())
       continue;
     if (I->getScalarSizeInBits() * I->getVectorNumElements() == 128)
       Cost += getMemoryOpCost(Instruction::Store, I, 128, 0) +
         getMemoryOpCost(Instruction::Load, I, 128, 0);
   }
   return Cost;
 }
 
-unsigned AArch64TTIImpl::getMaxInterleaveFactor() {
+unsigned AArch64TTIImpl::getMaxInterleaveFactor(unsigned VF) {
   if (ST->isCortexA57())
     return 4;
   return 2;
 }
 
 void AArch64TTIImpl::getUnrollingPreferences(Loop *L,
                                              TTI::UnrollingPreferences &UP) {
   // Enable partial unrolling and runtime unrolling.

llvm/trunk/lib/Target/ARM/ARMTargetTransformInfo.h

if (Vector) {
       if (ST->hasNEON())
         return 128;
       return 0;
     }
 
     return 32;
   }
 
-  unsigned getMaxInterleaveFactor() {
+  unsigned getMaxInterleaveFactor(unsigned VF) {
     // These are out of order CPUs:
     if (ST->isCortexA15() || ST->isSwift())
       return 2;
     return 1;
   }
 
   unsigned getShuffleCost(TTI::ShuffleKind Kind, Type *Tp, int Index,
                           Type *SubTp);

llvm/trunk/lib/Target/PowerPC/PPCTargetTransformInfo.h

public:
   /// @}
 
   /// \name Vector TTI Implementations
   /// @{
 
   bool enableAggressiveInterleaving(bool LoopHasReductions);
   unsigned getNumberOfRegisters(bool Vector);
   unsigned getRegisterBitWidth(bool Vector);
-  unsigned getMaxInterleaveFactor();
+  unsigned getMaxInterleaveFactor(unsigned VF);
   unsigned getArithmeticInstrCost(
       unsigned Opcode, Type *Ty,
       TTI::OperandValueKind Opd1Info = TTI::OK_AnyValue,
       TTI::OperandValueKind Opd2Info = TTI::OK_AnyValue,
       TTI::OperandValueProperties Opd1PropInfo = TTI::OP_None,
       TTI::OperandValueProperties Opd2PropInfo = TTI::OP_None);
   unsigned getShuffleCost(TTI::ShuffleKind Kind, Type *Tp, int Index,
                           Type *SubTp);

llvm/trunk/lib/Target/PowerPC/PPCTargetTransformInfo.cpp

unsigned PPCTTIImpl::getRegisterBitWidth(bool Vector) {
   }
 
   if (ST->isPPC64())
     return 64;
   return 32;
 
 }
 
-unsigned PPCTTIImpl::getMaxInterleaveFactor() {
+unsigned PPCTTIImpl::getMaxInterleaveFactor(unsigned VF) {
   unsigned Directive = ST->getDarwinDirective();
   // The 440 has no SIMD support, but floating-point instructions
   // have a 5-cycle latency, so unroll by 5x for latency hiding.
   if (Directive == PPC::DIR_440)
     return 5;
 
   // The A2 has no SIMD support, but floating-point instructions
   // have a 6-cycle latency, so unroll by 6x for latency hiding.

llvm/trunk/lib/Target/R600/AMDGPUTargetTransformInfo.h

public:
 
   TTI::PopcntSupportKind getPopcntSupport(unsigned TyWidth) {
     assert(isPowerOf2_32(TyWidth) && "Ty width must be power of 2");
     return ST->hasBCNT(TyWidth) ? TTI::PSK_FastHardware : TTI::PSK_Software;
   }
 
   unsigned getNumberOfRegisters(bool Vector);
   unsigned getRegisterBitWidth(bool Vector);
-  unsigned getMaxInterleaveFactor();
+  unsigned getMaxInterleaveFactor(unsigned VF);
 };
 
 } // end namespace llvm
 
 #endif

llvm/trunk/lib/Target/R600/AMDGPUTargetTransformInfo.cpp

unsigned AMDGPUTTIImpl::getNumberOfRegisters(bool Vec) {
   if (ST->getGeneration() >= AMDGPUSubtarget::SOUTHERN_ISLANDS)
     return 256;
 
   return 4 * 128; // XXX - 4 channels. Should these count as vector instead?
 }
 
 unsigned AMDGPUTTIImpl::getRegisterBitWidth(bool) { return 32; }
 
-unsigned AMDGPUTTIImpl::getMaxInterleaveFactor() {
+unsigned AMDGPUTTIImpl::getMaxInterleaveFactor(unsigned VF) {
   // Semi-arbitrary large amount.
   return 64;
 }

llvm/trunk/lib/Target/X86/X86TargetTransformInfo.h

public:
 
   /// @}
 
   /// \name Vector TTI Implementations
   /// @{
 
   unsigned getNumberOfRegisters(bool Vector);
   unsigned getRegisterBitWidth(bool Vector);
-  unsigned getMaxInterleaveFactor();
+  unsigned getMaxInterleaveFactor(unsigned VF);
   unsigned getArithmeticInstrCost(
       unsigned Opcode, Type *Ty,
       TTI::OperandValueKind Opd1Info = TTI::OK_AnyValue,
       TTI::OperandValueKind Opd2Info = TTI::OK_AnyValue,
       TTI::OperandValueProperties Opd1PropInfo = TTI::OP_None,
       TTI::OperandValueProperties Opd2PropInfo = TTI::OP_None);
   unsigned getShuffleCost(TTI::ShuffleKind Kind, Type *Tp, int Index,
                           Type *SubTp);

llvm/trunk/lib/Target/X86/X86TargetTransformInfo.cpp

unsigned X86TTIImpl::getRegisterBitWidth(bool Vector) {
   }
 
   if (ST->is64Bit())
     return 64;
   return 32;
 
 }
 
-unsigned X86TTIImpl::getMaxInterleaveFactor() {
+unsigned X86TTIImpl::getMaxInterleaveFactor(unsigned VF) {
+  // If the loop will not be vectorized, don't interleave the loop.
+  // Let regular unroll to unroll the loop, which saves the overflow
+  // check and memory check cost.
+  if (VF == 1)
+    return 1;
+
   if (ST->isAtom())
     return 1;
 
   // Sandybridge and Haswell have multiple execution ports and pipelined
   // vector units.
   if (ST->hasAVX())
     return 4;
 

llvm/trunk/lib/Transforms/Vectorize/LoopVectorize.cpp

unsigned UF = PowerOf2Floor((TargetNumRegisters - R.LoopInvariantRegs) /
                               R.MaxLocalUsers);
 
   // Don't count the induction variable as unrolled.
   if (EnableIndVarRegisterHeur)
     UF = PowerOf2Floor((TargetNumRegisters - R.LoopInvariantRegs - 1) /
                        std::max(1U, (R.MaxLocalUsers - 1)));
 
   // Clamp the unroll factor ranges to reasonable factors.
-  unsigned MaxInterleaveSize = TTI.getMaxInterleaveFactor();
+  unsigned MaxInterleaveSize = TTI.getMaxInterleaveFactor(VF);
 
   // Check if the user has overridden the unroll max.
   if (VF == 1) {
     if (ForceTargetMaxScalarInterleaveFactor.getNumOccurrences() > 0)
       MaxInterleaveSize = ForceTargetMaxScalarInterleaveFactor;
   } else {
     if (ForceTargetMaxVectorInterleaveFactor.getNumOccurrences() > 0)
       MaxInterleaveSize = ForceTargetMaxVectorInterleaveFactor;

llvm/trunk/test/Transforms/LoopVectorize/X86/unroll-small-loops.ll

 ; But this is a good small loop to unroll as we don't know of a bound on its
 ; trip count.
 ;
 ; CHECK-VECTOR-LABEL: @bar(
 ; CHECK-VECTOR: store <4 x i32>
 ; CHECK-VECTOR: store <4 x i32>
 ; CHECK-VECTOR: ret
 ;
+; For x86, loop unroll in loop vectorizer is disabled when VF==1.
+;
 ; CHECK-SCALAR-LABEL: @bar(
 ; CHECK-SCALAR: store i32
-; CHECK-SCALAR: store i32
+; CHECK-SCALAR-NOT: store i32
 ; CHECK-SCALAR: ret
 define i32 @bar(i32* nocapture %A, i32 %n) nounwind uwtable ssp {
   %1 = icmp sgt i32 %n, 0
   br i1 %1, label %.lr.ph, label %._crit_edge
 
 .lr.ph:                                           ; preds = %0, %.lr.ph
   %indvars.iv = phi i64 [ %indvars.iv.next, %.lr.ph ], [ 0, %0 ]
   %2 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv

llvm/trunk/test/Transforms/LoopVectorize/unroll.ll

+; This test makes sure that loop will not be unrolled in vectorization if VF computed
+; equals to 1.
+; RUN: opt < %s -loop-vectorize -S | FileCheck %s
+
+; Make sure there are no geps being merged.
+; CHECK-LABEL: @foo(
+; CHECK: getelementptr
+; CHECK-NOT: getelementptr
+
+@N = common global i32 0, align 4
+@a = common global [1000 x i32] zeroinitializer, align 16
+
+define void @foo() #0 {
+entry:
+  %0 = load i32, i32* @N, align 4
+  %cmp5 = icmp sgt i32 %0, 0
+  br i1 %cmp5, label %for.body.lr.ph, label %for.end
+
+for.body.lr.ph:                                   ; preds = %entry
+  %conv = sext i32 %0 to i64
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.lr.ph, %for.body
+  %i.06 = phi i64 [ 0, %for.body.lr.ph ], [ %inc, %for.body ]
+  %mul = mul nuw nsw i64 %i.06, 7
+  %arrayidx = getelementptr inbounds [1000 x i32], [1000 x i32]* @a, i64 0, i64 %mul
+  store i32 3, i32* %arrayidx, align 4
+  %inc = add nuw nsw i64 %i.06, 1
+  %cmp = icmp slt i64 %inc, %conv
+  br i1 %cmp, label %for.body, label %for.end.loopexit
+
+for.end.loopexit:                                 ; preds = %for.body
+  br label %for.end
+
+for.end:                                          ; preds = %for.end.loopexit, %entry
+  ret void
+}