[ARM] Thumb2: favor R4-R7 over R12/LR in allocation order when opt for minsize

[ostannard]

Summary

For Thumb2, we prefer low regs (costPerUse = 0) to allow narrow encoding. However, current allocation order is like:

R0-R3, R12, LR, R4-R11

As a result, a lot of instructs that use R12/LR will be wide instrs.

This patch changes the allocation order to:

R0-R7, R12, LR, R8-R11

for thumb2 and -Oz.

In most cases, there is no extra push/pop instrs as they will be folded into
existing ones. There might be slight performance impact due to more stack
usage, so we only enable it when opt for min size.

For an embedded application with 83K code, this patch saves 430 bytes (0.5%).

[rengolin]

I'm not sure about this change. I think it makes sense, but I don't think it's done in a way to integrate with the existing code.

I'm adding Quentin (the code owner for the register allocator) to have a more informed opinion.

I'd also expect some benchmarks (speed and size) on a few benchmarks, hopefully in a few thumb2 architectures. A 0.5% code size improvement on "an embedded application" isn't enough, I think.

cheers,
--renato

lib/CodeGen/RegisterClassInfo.cpp

129

I'm not very knowledgeable in this part of the code, but it seems you're destroying everything the above code was trying to do with the RCI order. It looks to me as though you should try to add the logic into the loop above, rather than splitting and discarding.

lib/Target/ARM/ARMBaseRegisterInfo.cpp

58

This option seems unnecessary. I mean, it's good to have it in order to track performance, but this change looks beneficial to all thumb targets. So, unless this brings performance or code size issue for some but not all thumb, I think this should be removed, and make the cost be calculated solely on isThumb2.

[efriedma]

Please repost with llvm-commits on the CC list, so the patch gets sent to the mailing list.

[weimingz]

Sure, I will get more numbers for other benchmarks.

lib/CodeGen/RegisterClassInfo.cpp

129

The code will maintain the original order if two registers have the same priority by using stable_sort: one register has lower CostPerUse, it has higher priority. Otherwise, the caller saved register have higher priority. Everything equal, the original order is kept.

[qcolombet]

lib/CodeGen/RegisterClassInfo.cpp

129

Renato is right, you're doing more that changing the order of the CSRs.
Although this is probably not used in-tree, there is nothing that prevents to set a different cost for each register. Thus a stable sort on the cost per use may give a very different order than the raw order.

For instance, the raw order could well be in terms of cost per use {10, 8, 3, 12, etc.}.

Instead, what I would suggest is:

• Define an alternative order for MF
• Add a callback just to disable the special case for CSR, i.e., the callback you have works, just use it inside the loop not to populate the CSRAlias

[weimingz]

Below are the measurements of text size of benchmarks.
Build flag: "-Oz -mthumb -mcpu=cortex-m3 -fomit-frame-pointer"
Baseline has extra flag: " -mllvm -arm-favor-r4-r7=false"

benchmark	baseline	favor low reg	reduction	reduction (%)
spec2000/ammp	73304	72984	320	0.436538
spec2000/art	8459	8459	0	0
spec2000/bzip2	18771	18739	32	0.170476
spec2000/crafty	133506	133242	264	0.197744
spec2000/eon	217561	217251	310	0.142489
spec2000/equake	11409	11373	36	0.31554
spec2000/gap	267736	267312	424	0.158365
spec2000/gcc	800902	800050	852	0.10638
spec2000/gzip	21563	21515	48	0.222604
spec2000/mcf	5366	5308	58	1.08088
spec2000/mesa	305721	304279	1442	0.471672
spec2000/parser	58571	58459	112	0.191221
spec2000/perlbmk	311020	310724	296	0.0951707
spec2000/twolf	119785	119905	-120	-0.100179
spec2000/vortex	322133	321581	552	0.171358
spec2000/vpr	90682	90570	112	0.123509
coremark	6281	6188	93	1.48066
spec2006/astar	19282	19284	-2	-0.0103724
spec2006/bzip2	33991	33897	94	0.276544
spec2006/dealII	1864927	1861707	3220	0.172661
spec2006/gcc	1835601	1833531	2070	0.11277
spec2006/gobmk	1151212	1149542	1670	0.145065
spec2006/h264ref	335652	335218	434	0.129301
spec2006/hmmer	153025	152693	332	0.216958
spec2006/lbm	7282	7270	12	0.16479
spec2006/libquantum	19926	19888	38	0.190706
spec2006/mcf	5484	5446	38	0.692925
spec2006/milc	64512	64236	276	0.427827
spec2006/namd	154110	153830	280	0.181688
spec2006/omnetpp	429750	429576	174	0.0404887
spec2006/perlbench	603275	602947	328	0.0543699
spec2006/povray	555524	554886	638	0.114847
spec2006/sjeng	86646	86302	344	0.397018
spec2006/soplex	210691	210169	522	0.247756
spec2006/sphinx3	100839	100641	198	0.196353
spec2006/xalancbmk	2819035	2817887	1148	0.0407232

[weimingz]

ping?

[rengolin]

Hi Weiming,

Sorry for the delay. I have two major points with this approach:

1. We're basically selecting different patterns based on different flags by crossing too many wires (table-gen reg definition, sub-target feature, command line option, optimisation flags). Dynamically changing with command line options is going to be harder to test and reproduce user bugs.
2. The benchmark numbers for code size reduction aren't still really *that* encouraging.

Ultimately, having a simple ARM/Thumb1/2 set would be as far as I'd go.

@qcolombet is there some prior art for that kind of fiddling? By looking at the other register files, the most that happens is things like "is64bit", in the same way we have "isThumb1".

cheers,
--renato

[ostannard]

• Rebase onto trunk.
• Move all controlling conditions into ARMSubtarget
• Remove command-line option (the only reason to disable this is benchmarking it)
• Simplify test with inline asm, should be more robust

This is giving me ~0.1% code size reduction on SPEC2006 (comparing -Oz without this patch to -Oz with it), and ~0.25% reduction on 8 mbed-os examples.

[jmolloy]

llvm/include/llvm/CodeGen/TargetSubtargetInfo.h

295 ↗

(On Diff #207525)

All virtual functions should have a docstring.

llvm/lib/CodeGen/RegisterClassInfo.cpp

118 ↗

(On Diff #207525)

Although you're not using it here, it seems to me very natural for such a callback to take the PhysReg too.

[ostannard]

llvm/lib/CodeGen/RegisterClassInfo.cpp

118 ↗

(On Diff #207525)

I'd rather not add extra code which we don't currently have a use for. That can easily be done later if it does turn out to be useful.

[ostannard]

• Added doc string
• Remembered to git-add the test this time

[jmolloy]

llvm/lib/CodeGen/RegisterClassInfo.cpp

118 ↗

(On Diff #207525)

I agree with the principle and would usually advocate for it. But in this case the SubtargetInfo API is a public API that is used by out-of-tree targets. Having a sensible API that isn't overfit to the current in-tree targets when it's ~zero cost is something we should aim for, IMO.

[ostannard]

• Add a PhysReg parameter to ignoreCSRForAllocationOrder
• Check that the register is a GPR in the ARM implementation. The other register classes have the callee-saved regs last, so this doesn't make any difference to the generated code, but might avoid surprising behaviour in the future.

[jmolloy]

LGTM, thanks for the change Oliver!

[ostannard]

Committed https://reviews.llvm.org/rL365014

include/llvm/Target/TargetRegisterInfo.h

if (!IdxA)
       return LaneMask;
     return reverseComposeSubRegIndexLaneMaskImpl(IdxA, LaneMask);
   }
 
   /// Debugging helper: dump register in human readable form to dbgs() stream.
   static void dumpReg(unsigned Reg, unsigned SubRegIndex = 0,
                       const TargetRegisterInfo* TRI = nullptr);
 
+  /// Returns true if perUseCost weights over CSR/non-CSR when computing
+  //  the preferred allocation order.
+  virtual bool costPerUseOverridesCSR(const MachineFunction &MF) const {
+    return false;
+  }
+
 protected:
   /// Overridden by TableGen in targets that have sub-registers.
   virtual unsigned composeSubRegIndicesImpl(unsigned, unsigned) const {
     llvm_unreachable("Target has no sub-registers");
   }
 
   /// Overridden by TableGen in targets that have sub-registers.
   virtual LaneBitmask

lib/CodeGen/RegisterClassInfo.cpp

for (unsigned i = 0, e = CSRAlias.size(); i != e; ++i) {
     unsigned PhysReg = CSRAlias[i];
     unsigned Cost = TRI->getCostPerUse(PhysReg);
     if (Cost != LastCost)
       LastCostChange = N;
     RCI.Order[N++] = PhysReg;
     LastCost = Cost;
   }
 
+  if (TRI->costPerUseOverridesCSR(*MF)) {
+    // If cost per use outweights CSR in deciding allocation order, we reorder
+    // RCI.order by: 1) costPerUse 2) CSR or not 3) the existing relative
+    // order (using stable_sort to get this).
+    std::stable_sort(&RCI.Order[0], &RCI.Order[N],
+                     [&](const MCPhysReg &a, const MCPhysReg &b) -> bool {
+                       auto CostA = TRI->getCostPerUse(a);
+                       auto CostB = TRI->getCostPerUse(b);
+                       if (CostA != CostB)
+                         return CostA < CostB;
+                       // If one is CSR and the other is not, use non-CSR first.
+                       if (!CSRNum[a] != !CSRNum[b])
+                         return !CSRNum[a];
+                       return false;
+                     });
+  }
+
   // Register allocator stress test.  Clip register class to N registers.
   if (StressRA && RCI.NumRegs > StressRA)
     RCI.NumRegs = StressRA;
 
   // Check if RC is a proper sub-class.
   if (const TargetRegisterClass *Super =
           TRI->getLargestLegalSuperClass(RC, *MF))
     if (Super != RC && getNumAllocatableRegs(Super) > RCI.NumRegs)

lib/Target/ARM/ARMBaseRegisterInfo.h

public:
 
   /// \brief SrcRC and DstRC will be morphed into NewRC if this returns true
   bool shouldCoalesce(MachineInstr *MI,
                       const TargetRegisterClass *SrcRC,
                       unsigned SubReg,
                       const TargetRegisterClass *DstRC,
                       unsigned DstSubReg,
                       const TargetRegisterClass *NewRC) const override;
+
+  bool costPerUseOverridesCSR(const MachineFunction &MF) const override;
 };
 
 } // end namespace llvm
 
 #endif // LLVM_LIB_TARGET_ARM_ARMBASEREGISTERINFO_H

lib/Target/ARM/ARMBaseRegisterInfo.cpp

 
 #define DEBUG_TYPE "arm-register-info"
 
 #define GET_REGINFO_TARGET_DESC
 #include "ARMGenRegisterInfo.inc"
 
 using namespace llvm;
 
+static cl::opt<bool> FavorLowRegOverR12LR("arm-favor-r4-r7", cl::Hidden,
+                                          cl::desc("favor r4-r7 over r12, lr"));
+
 ARMBaseRegisterInfo::ARMBaseRegisterInfo()
     : ARMGenRegisterInfo(ARM::LR, 0, 0, ARM::PC) {}
 
 static unsigned getFramePointerReg(const ARMSubtarget &STI) {
   return STI.useR7AsFramePointer() ? ARM::R7 : ARM::R11;
 }
 
 const MCPhysReg*
bool ARMBaseRegisterInfo::shouldCoalesce(MachineInstr *MI,
   unsigned SizeMultiplier = MBB->size()/100;
   SizeMultiplier = SizeMultiplier ? SizeMultiplier : 1;
   if (It->second < NewRCWeight.WeightLimit * SizeMultiplier) {
     It->second += NewRCWeight.RegWeight;
     return true;
   }
   return false;
 }
+
+bool ARMBaseRegisterInfo::costPerUseOverridesCSR(
+    const MachineFunction &MF) const {
+  // To minimize code size in Thumb2, we prefer the usage of low regs (lower
+  // cost per use) so we can  use narrow encoding. By default, caller-saved
+  // registers (e.g. lr, r12) are always  allocated first, regardless of
+  // their cost per use. When optForMinSize, we prefer the low regs even if
+  // they are CSR because usually push/pop can be folded into existing ones.
+  return MF.getSubtarget<ARMSubtarget>().isThumb2() &&
+         (FavorLowRegOverR12LR.getNumOccurrences()
+              ? FavorLowRegOverR12LR
+              : MF.getFunction()->optForMinSize());
+}

test/CodeGen/ARM/favor-low-reg-for-Osize.ll

+; REQUIRES: asserts
+; RUN: llc -debug-only=regalloc < %s 2>&1 | FileCheck %s --check-prefix=CHECK --check-prefix=LowRegFirst
+; RUN: llc -debug-only=regalloc -arm-favor-r4-r7=false  < %s 2>&1 | FileCheck %s --check-prefix=CHECK --check-prefix=CallerSavedRegFirst
+
+target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n8:16:32-S64"
+target triple = "thumbv7m--linux-gnueabi"
+
+%struct.ContextType = type { i8*, i8*, i8*, i8*, i32 }
+;CHECK-LowRegFirst:         AllocationOrder(GPR) = [ %R0 %R1 %R2 %R3 %R4 %R5 %R6 %R7 %R12 %LR %R8 %R9 %R10 %R11 ]
+;CHECK-CallerSavedRegFirst: AllocationOrder(GPR) = [ %R0 %R1 %R2 %R3 %R12 %LR %R4 %R5 %R6 %R7 %R8 %R9 %R10 %R11 ]
+
+; Function Attrs: minsize norecurse nounwind optsize
+define void @test(%struct.ContextType* nocapture readonly %pContext) local_unnamed_addr #0 {
+entry:
+;CHECK-LABEL: test
+
+;CHECK-LowRegFirst-NOT: ldr{{.*}}.w
+;CHECK-LowRegFirst-NOT: str{{.*}}.w
+
+;CHECK-CallerSavedRegFirst: ldr{{.*}}.w lr,
+;CHECK-CallerSavedRegFirst: ldr{{.*}}.w r12
+;CHECK-CallerSavedRegFirst: str{{.*}}.w r12
+
+  %Src1 = getelementptr inbounds %struct.ContextType, %struct.ContextType* %pContext, i32 0, i32 0
+  %0 = load i8*, i8** %Src1, align 4
+  %Len = getelementptr inbounds %struct.ContextType, %struct.ContextType* %pContext, i32 0, i32 4
+  %1 = load i32, i32* %Len, align 4
+  %Dst = getelementptr inbounds %struct.ContextType, %struct.ContextType* %pContext, i32 0, i32 2
+  %2 = load i8*, i8** %Dst, align 4
+  %arrayidx = getelementptr inbounds i8, i8* %0, i32 24
+  %3 = bitcast i8* %arrayidx to i32*
+  %4 = load i32, i32* %3, align 4
+  %arrayidx2 = getelementptr inbounds i8, i8* %0, i32 18
+  %5 = bitcast i8* %arrayidx2 to i16*
+  %6 = load i16, i16* %5, align 2
+  %arrayidx3 = getelementptr inbounds i8, i8* %0, i32 16
+  %7 = bitcast i8* %arrayidx3 to i16*
+  %8 = load i16, i16* %7, align 2
+  %arrayidx4 = getelementptr inbounds i8, i8* %0, i32 12
+  %9 = bitcast i8* %arrayidx4 to i32*
+  %10 = load i32, i32* %9, align 4
+  %arrayidx5 = getelementptr inbounds i8, i8* %0, i32 2
+  %11 = bitcast i8* %arrayidx5 to i16*
+  %12 = load i16, i16* %11, align 2
+  %add = add i32 %1, 24
+  %arrayidx6 = getelementptr inbounds i8, i8* %2, i32 %add
+  %13 = bitcast i8* %arrayidx6 to i32*
+  store i32 %4, i32* %13, align 4
+  %add7 = add i32 %1, 18
+  %arrayidx8 = getelementptr inbounds i8, i8* %2, i32 %add7
+  %14 = bitcast i8* %arrayidx8 to i16*
+  store i16 %6, i16* %14, align 2
+  %add9 = add i32 %1, 16
+  %arrayidx10 = getelementptr inbounds i8, i8* %2, i32 %add9
+  %15 = bitcast i8* %arrayidx10 to i16*
+  store i16 %8, i16* %15, align 2
+  %add11 = add i32 %1, 12
+  %arrayidx12 = getelementptr inbounds i8, i8* %2, i32 %add11
+  %16 = bitcast i8* %arrayidx12 to i32*
+  store i32 %10, i32* %16, align 4
+  %add13 = add i32 %1, 2
+  %arrayidx14 = getelementptr inbounds i8, i8* %2, i32 %add13
+  %17 = bitcast i8* %arrayidx14 to i16*
+  store i16 %12, i16* %17, align 2
+  ret void
+}
+
+attributes #0 = { minsize norecurse nounwind optsize "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="cortex-m3" "target-features"="+hwdiv" "unsafe-fp-math"="false" "use-soft-float"="false" }

test/CodeGen/ARM/fold-stack-adjust.ll

 ; Disable shrink-wrapping on the first test otherwise we wouldn't
 ; exerce the path for PR18136.
-; RUN: llc -mtriple=thumbv7-apple-none-macho < %s -enable-shrink-wrap=false | FileCheck %s
+; RUN: llc -mtriple=thumbv7-apple-none-macho -arm-favor-r4-r7=false < %s -enable-shrink-wrap=false | FileCheck %s
 ; RUN: llc -mtriple=thumbv6m-apple-none-macho -disable-fp-elim < %s | FileCheck %s --check-prefix=CHECK-T1
-; RUN: llc -mtriple=thumbv7-apple-darwin-ios -disable-fp-elim < %s | FileCheck %s --check-prefix=CHECK-IOS
-; RUN: llc -mtriple=thumbv7--linux-gnueabi -disable-fp-elim < %s | FileCheck %s --check-prefix=CHECK-LINUX
+; RUN: llc -mtriple=thumbv7-apple-darwin-ios -disable-fp-elim -arm-favor-r4-r7=false < %s | FileCheck %s --check-prefix=CHECK-IOS
+; RUN: llc -mtriple=thumbv7--linux-gnueabi -disable-fp-elim -arm-favor-r4-r7=false < %s | FileCheck %s --check-prefix=CHECK-LINUX
 
 
 declare void @bar(i8*)
 
 %bigVec = type [2 x double]
 
 @var = global %bigVec zeroinitializer