[LV] Improve register pressure estimate at high VFs

[peterwaller-arm]

Summary

Previously, getRegUsageForType was implemented using
getTypeLegalizationCost. getRegUsageForType is used by the loop
vectorizer to estimate the register pressure caused by using a vector
type. However, getTypeLegalizationCost currently only appears to
understand splitting and not scalarization, so significantly
underestimates the register requirements.

Instead, use getNumRegisters, which understands when scalarization
can occur (via computeRegisterProperties).

This was discovered while investigating D118979 (Set maximum VF with
shouldMaximizeVectorBandwidth), where under fixed-length 512-bit SVE the
loop vectorizer previously ends up costing an v128i1 as 2 v64i*
registers where it actually occupies 128 i32 registers.

I'm sending this patch early for comment, I'm still doing some sanity checking
with LNT. I note that getRegisterClassForType appears to return VectorRC even
though the type in question (large vNi1 types) end up occupying scalar
registers. That might be worth fixing too.

[paulwalker-arm]

llvm/include/llvm/CodeGen/BasicTTIImpl.h

385

I lack some historical knowledge here but I agree it does look like the current implementation is answering the wrong question here.

Assuming others agree with the intent of the change I'm thinking the function definition should also be changed. Returning InstructionCost seems wrong and likely just the result of the original call to getTypeLegalizationCost(). I think unsigned is more representative of the function's intent.

[peterwaller-arm]

• Address Paul's suggestion: make getRegUsageForType return unsigned and simplify.

[peterwaller-arm]

llvm/test/Transforms/LoopVectorize/AArch64/i1-reg-usage.ll

36

I took a look at making this report the correct RC in D125956.

[sdesmalen]

This change looks right to me.

I do think there is a related issue exposed by your test. The cost-model for the PHI node is not accurate, because it suggests the cost of the PHI itself is 0 but because the copy is being scalarized in CopyToReg/CopyFromReg the cost is actually really high. Perhaps we can update getCFInstrCost with some checks to see if the vector type requires Promotion + Splitting and if so, return a scalarization cost for the PHI node instead. We can also just fix the codegen itself of course, but I suspect that may be more work.

[dmgreen]

I think for the case of D118979 it makes sense to prevent maximizing the vector bandwidth for fixed-length sve. The larger vectors will already be wide enough and as far as I understand they don't benefit from the wider types in the same way that NEON does.

It sounds like this will be useful in either case though. The same thing could potentially happen with 128xi1 types. And it looks like it is used in the interleaving factor calculations.

llvm/test/Transforms/LoopVectorize/AArch64/i1-reg-usage.ll

15

I don't think this need the target-feature=+neon

[peterwaller-arm]

• Remove target-features test attribute per review and rebase.

I'm in the process of final-check-and-submit now, but may get interrupted.

[sylvestre.ledru]

it introduced a regression here:

https://github.com/llvm/llvm-project/issues/56374

[peterwaller-arm]

In D125918#3628323, @sylvestre.ledru wrote:

it introduced a regression here:

https://github.com/llvm/llvm-project/issues/56374

Thanks for the report, should be fixed in rGc146af3f469adde04f7adb126e7d7b7b7047c88c, please ping again if not, I don't have gcc-6 to hand to test with.

llvm/include/llvm/CodeGen/BasicTTIImpl.h

public:
 
   bool useAA() const { return getST()->useAA(); }
 
   bool isTypeLegal(Type *Ty) {
     EVT VT = getTLI()->getValueType(DL, Ty);
     return getTLI()->isTypeLegal(VT);
   }
 
   InstructionCost getRegUsageForType(Type *Ty) {
-    InstructionCost Val = getTLI()->getTypeLegalizationCost(DL, Ty).first;
-    assert(Val >= 0 && "Negative cost!");
-    return Val;
+    EVT ETy = getTLI()->getValueType(DL, Ty);
+    return getTLI()->getNumRegisters(Ty->getContext(), ETy);
   }
 
   InstructionCost getGEPCost(Type *PointeeType, const Value *Ptr,
                              ArrayRef<const Value *> Operands,
                              TTI::TargetCostKind CostKind) {
     return BaseT::getGEPCost(PointeeType, Ptr, Operands, CostKind);
   }
 

llvm/test/Transforms/LoopVectorize/AArch64/i1-reg-usage.ll

+; RUN: opt -loop-vectorize -debug-only=loop-vectorize -disable-output 2>&1 < %s | FileCheck %s
+; REQUIRES: asserts
+
+target triple = "aarch64"
+
+; Test that shows how many registers the loop vectorizer thinks an illegal <VF x i1> will consume.
+
+; CHECK-LABEL: LV: Checking a loop in 'or_reduction_neon' from <stdin>
+; CHECK: LV(REG): VF = 32
+; CHECK-NEXT: LV(REG): Found max usage: 2 item
+; CHECK-NEXT: LV(REG): RegisterClass: Generic::VectorRC, 72 registers
+; CHECK-NEXT: LV(REG): RegisterClass: Generic::ScalarRC, 1 registers
+
+define i1 @or_reduction_neon(i32 %arg, ptr %ptr) "target-features"="+neon" {
+entry:
+  br label %loop
+exit:
+  ret i1 %reduction_next
+loop:
+  %induction = phi i32 [ 0, %entry ], [ %induction_next, %loop ]
+  %reduction = phi i1 [ 0, %entry ], [ %reduction_next, %loop ]
+  %gep = getelementptr inbounds i32, ptr %ptr, i32 %induction
+  %loaded = load i32, ptr %gep
+  %i1 = icmp eq i32 %loaded, %induction
+  %reduction_next = or i1 %i1, %reduction
+  %induction_next = add nuw i32 %induction, 1
+  %cond = icmp eq i32 %induction_next, %arg
+  br i1 %cond, label %exit, label %loop, !llvm.loop !32
+}
+
+; CHECK-LABEL: LV: Checking a loop in 'or_reduction_sve'
+; CHECK: LV(REG): VF = 64
+; CHECK-NEXT: LV(REG): Found max usage: 2 item
+; CHECK-NEXT: LV(REG): RegisterClass: Generic::VectorRC, 136 registers
+; CHECK-NEXT: LV(REG): RegisterClass: Generic::ScalarRC, 1 registers
+
+define i1 @or_reduction_sve(i32 %arg, ptr %ptr) vscale_range(2,2) "target-features"="+sve" {
+entry:
+  br label %loop
+exit:
+  ret i1 %reduction_next
+loop:
+  %induction = phi i32 [ 0, %entry ], [ %induction_next, %loop ]
+  %reduction = phi i1 [ true, %entry ], [ %reduction_next, %loop ]
+  %gep = getelementptr inbounds i32, ptr %ptr, i32 %induction
+  %loaded = load i32, ptr %gep
+  %i1 = icmp eq i32 %loaded, %induction
+  %reduction_next = or i1 %i1, %reduction
+  %induction_next = add nuw i32 %induction, 1
+  %cond = icmp eq i32 %induction_next, %arg
+  br i1 %cond, label %exit, label %loop, !llvm.loop !64
+}
+
+!32 = distinct !{!32, !33}
+!33 = !{!"llvm.loop.vectorize.width", i32 32}
+!64 = distinct !{!64, !65}
+!65 = !{!"llvm.loop.vectorize.width", i32 64}

llvm/test/Transforms/LoopVectorize/X86/i1-reg-usage.ll

+; RUN: opt -loop-vectorize -debug-only=loop-vectorize -disable-output 2>&1 < %s | FileCheck %s
+; REQUIRES: asserts
+
+target triple = "x86_64"
+
+; Test that shows how many registers the loop vectorizer thinks an illegal <VF x i1> will consume.
+
+; CHECK-LABEL: LV: Checking a loop in 'or_reduction_avx' from <stdin>
+; CHECK: LV(REG): VF = 64
+; CHECK-NEXT: LV(REG): Found max usage: 2 item
+; CHECK-NEXT: LV(REG): RegisterClass: Generic::VectorRC, 136 registers
+; CHECK-NEXT: LV(REG): RegisterClass: Generic::ScalarRC, 1 registers
+
+define i1 @or_reduction_avx(i32 %arg, ptr %ptr) "target-features"="+avx" {
+entry:
+  br label %loop
+exit:
+  ret i1 %reduction_next
+loop:
+  %induction = phi i32 [ 0, %entry ], [ %induction_next, %loop ]
+  %reduction = phi i1 [ 0, %entry ], [ %reduction_next, %loop ]
+  %gep = getelementptr inbounds i32, ptr %ptr, i32 %induction
+  %loaded = load i32, ptr %gep
+  %i1 = icmp eq i32 %loaded, %induction
+  %reduction_next = or i1 %i1, %reduction
+  %induction_next = add nuw i32 %induction, 1
+  %cond = icmp eq i32 %induction_next, %arg
+  br i1 %cond, label %exit, label %loop, !llvm.loop !64
+}
+
+!64 = distinct !{!64, !65}
+!65 = !{!"llvm.loop.vectorize.width", i32 64}