[AArch64][GlobalISel] Add heuristics for localizing G_CONSTANT.

[aemerson]

Summary

This adds similar heuristics to G_GLOBAL_VALUE, querying the cost of
materializing a specific constant in code size. Doing so prevents us from
sinking constants which require multiple instructions to generate into
use blocks.

Code size savings on CTMark -Os:

Program                                       size.__text
                                              before         after           diff
ClamAV/clamscan                               381940.00      382052.00       0.0%
lencod/lencod                                 428408.00      428428.00       0.0%
SPASS/SPASS                                   411868.00      411876.00       0.0%
kimwitu++/kc                                  449944.00      449944.00       0.0%
Bullet/bullet                                 463588.00      463556.00      -0.0%
sqlite3/sqlite3                               284696.00      284668.00      -0.0%
consumer-typeset/consumer-typeset             414492.00      414424.00      -0.0%
7zip/7zip-benchmark                           595244.00      594972.00      -0.0%
mafft/pairlocalalign                          247512.00      247368.00      -0.1%
tramp3d-v4/tramp3d-v4                         372884.00      372044.00      -0.2%
Geomean difference                               -0.0%

[paquette]

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

20778

This seems like it could be a helper function in MachineRegisterInfo

(or there should be some sort of helper in STLExtras for testing if a range is at most some #elts long)

llvm/test/CodeGen/AArch64/GlobalISel/localizer-arm64-tti.ll

117

this looks like it tests the

if (RematCost == 2)
  return 2U;

path right?

what about the other two possible values for RematCost?

[aemerson]

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

20778

Good idea.

llvm/test/CodeGen/AArch64/GlobalISel/localizer-arm64-tti.ll

117

A cost of 1 is already tested by other localizer tests. That corresponds to a constant being materializable in a single instruction, which we always localize. I'll add a test for the case of cost > 2.

[tschuett]

llvm/lib/CodeGen/MachineRegisterInfo.cpp

427

You could remove the braces.

[paquette]

LGTM

llvm/include/llvm/CodeGen/MachineRegisterInfo.h

public:
   /// use of the specified register.
   bool hasOneNonDBGUse(Register RegNo) const;
 
   /// hasOneNonDBGUse - Return true if there is exactly one non-Debug
   /// instruction using the specified register. Said instruction may have
   /// multiple uses.
   bool hasOneNonDBGUser(Register RegNo) const;
 
+
+  /// hasAtMostUses - Return true if the given register has at most \p MaxUsers
+  /// non-debug user instructions.
+  bool hasAtMostUserInstrs(Register Reg, unsigned MaxUsers) const;
+
   /// replaceRegWith - Replace all instances of FromReg with ToReg in the
   /// machine function.  This is like llvm-level X->replaceAllUsesWith(Y),
   /// except that it also changes any definitions of the register as well.
   ///
   /// Note that it is usually necessary to first constrain ToReg's register
   /// class and register bank to match the FromReg constraints using one of the
   /// methods:
   ///

llvm/lib/CodeGen/MachineRegisterInfo.cpp

 bool MachineRegisterInfo::hasOneNonDBGUse(Register RegNo) const {
   return hasSingleElement(use_nodbg_operands(RegNo));
 }
 
 bool MachineRegisterInfo::hasOneNonDBGUser(Register RegNo) const {
   return hasSingleElement(use_nodbg_instructions(RegNo));
 }
 
+bool MachineRegisterInfo::hasAtMostUserInstrs(Register Reg,
+                                              unsigned MaxUsers) const {
+  unsigned NumUsers = 0;
+  auto UI = use_instr_nodbg_begin(Reg), UE = use_instr_nodbg_end();
+  for (; UI != UE && NumUsers < MaxUsers; ++UI)
+    NumUsers++;
+  // If we haven't reached the end yet then there are more than MaxUses users.
+  return UI == UE;
+}
+
 /// clearKillFlags - Iterate over all the uses of the given register and
 /// clear the kill flag from the MachineOperand. This function is used by
 /// optimization passes which extend register lifetimes and need only
 /// preserve conservative kill flag information.
 void MachineRegisterInfo::clearKillFlags(Register Reg) const {
   for (MachineOperand &MO : use_operands(Reg))
     MO.setIsKill(false);
 }

llvm/lib/CodeGen/TargetLoweringBase.cpp

if (RematCost == 2)
       return 2U;
 
     // Remat is too expensive, only sink if there's one user.
     if (RematCost > 2)
       return 1U;
     llvm_unreachable("Unexpected remat cost");
   };
 
-  // Helper to walk through uses and terminate if we've reached a limit. Saves
-  // us spending time traversing uses if all we want to know is if it's >= min.
-  auto isUsesAtMost = [&](unsigned Reg, unsigned MaxUses) {
-    unsigned NumUses = 0;
-    auto UI = MRI.use_instr_nodbg_begin(Reg), UE = MRI.use_instr_nodbg_end();
-    for (; UI != UE && NumUses < MaxUses; ++UI) {
-      NumUses++;
-    }
-    // If we haven't reached the end yet then there are more than MaxUses users.
-    return UI == UE;
-  };
-
   switch (MI.getOpcode()) {
   default:
     return false;
   // Constants-like instructions should be close to their users.
   // We don't want long live-ranges for them.
   case TargetOpcode::G_CONSTANT:
   case TargetOpcode::G_FCONSTANT:
   case TargetOpcode::G_FRAME_INDEX:
   case TargetOpcode::G_INTTOPTR:
     return true;
   case TargetOpcode::G_GLOBAL_VALUE: {
     unsigned RematCost = TTI->getGISelRematGlobalCost();
     Register Reg = MI.getOperand(0).getReg();
     unsigned MaxUses = maxUses(RematCost);
     if (MaxUses == UINT_MAX)
       return true; // Remats are "free" so always localize.
-    bool B = isUsesAtMost(Reg, MaxUses);
-    return B;
+    return MRI.hasAtMostUserInstrs(Reg, MaxUses);
   }
   }
 }

llvm/lib/Target/AArch64/AArch64ISelLowering.cpp

 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/Analysis/ObjCARCUtil.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/VectorUtils.h"
 #include "llvm/CodeGen/Analysis.h"
 #include "llvm/CodeGen/CallingConvLower.h"
 #include "llvm/CodeGen/ISDOpcodes.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstr.h"

 #include "llvm/IR/Value.h"
 #include "llvm/MC/MCRegisterInfo.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CodeGen.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/InstructionCost.h"
 #include "llvm/Support/KnownBits.h"
 #include "llvm/Support/MachineValueType.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetOptions.h"
 #include <algorithm>
 #include <bitset>
void AArch64TargetLowering::finalizeLowering(MachineFunction &MF) const {
   // FIXME: It may be worthwhile having a specific interface for this rather
   // than doing it here in finalizeLowering.
   if (MFI.hasStackProtectorIndex()) {
     for (unsigned int i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) {
       if (MFI.getStackID(i) == TargetStackID::ScalableVector &&
           MFI.getObjectSSPLayout(i) != MachineFrameInfo::SSPLK_None) {
         MFI.setStackID(MFI.getStackProtectorIndex(),
                        TargetStackID::ScalableVector);
         MFI.setObjectAlignment(MFI.getStackProtectorIndex(), Align(16));
         break;
       }
     }
   }
   MFI.computeMaxCallFrameSize(MF);
   TargetLoweringBase::finalizeLowering(MF);
 }
 
 // Unlike X86, we let frame lowering assign offsets to all catch objects.
 bool AArch64TargetLowering::needsFixedCatchObjects() const {
   return false;
 }
 
 bool AArch64TargetLowering::shouldLocalize(
     const MachineInstr &MI, const TargetTransformInfo *TTI) const {
+  auto &MF = *MI.getMF();
+  auto &MRI = MF.getRegInfo();
+  auto maxUses = [](unsigned RematCost) {
+    // A cost of 1 means remats are basically free.
+    if (RematCost == 1)
+      return UINT_MAX;
+    if (RematCost == 2)
+      return 2U;
+
+    // Remat is too expensive, only sink if there's one user.
+    if (RematCost > 2)
+      return 1U;
+    llvm_unreachable("Unexpected remat cost");
+  };
+
   switch (MI.getOpcode()) {
   case TargetOpcode::G_GLOBAL_VALUE: {
     // On Darwin, TLS global vars get selected into function calls, which
     // we don't want localized, as they can get moved into the middle of a
     // another call sequence.
     const GlobalValue &GV = *MI.getOperand(1).getGlobal();
     if (GV.isThreadLocal() && Subtarget->isTargetMachO())
       return false;
     break;
   }
+  case TargetOpcode::G_CONSTANT: {
+    auto *CI = MI.getOperand(1).getCImm();
+    APInt Imm = CI->getValue();
+    InstructionCost Cost = TTI->getIntImmCost(
+        Imm, CI->getType(), TargetTransformInfo::TCK_CodeSize);
+    assert(Cost.isValid() && "Expected a valid imm cost");
+
+    unsigned RematCost = *Cost.getValue();
+    Register Reg = MI.getOperand(0).getReg();
+    unsigned MaxUses = maxUses(RematCost);
+    return MRI.hasAtMostUserInstrs(Reg, MaxUses);
+  }
   // If we legalized G_GLOBAL_VALUE into ADRP + G_ADD_LOW, mark both as being
   // localizable.
   case AArch64::ADRP:
   case AArch64::G_ADD_LOW:
     return true;
   default:
     break;
   }

llvm/test/CodeGen/AArch64/GlobalISel/localizer-arm64-tti.ll

if.then:
   %tls = load i32, i32* @tls_gv, align 4
   store i32 %tls, i32* @var2, align 4
   br label %if.end
 
 if.end:
   ret i32 0
 }
 
+define i32 @imm_cost_too_large_cost_of_2() {
+  ; CHECK-LABEL: name: imm_cost_too_large_cost_of_2
+  ; CHECK: bb.1.entry:
+  ; CHECK-NEXT:   successors: %bb.2(0x40000000), %bb.4(0x40000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[C:%[0-9]+]]:gpr(s32) = G_CONSTANT i32 -2228259
+  ; CHECK-NEXT:   [[GV:%[0-9]+]]:gpr(p0) = G_GLOBAL_VALUE @var2
+  ; CHECK-NEXT:   [[GV1:%[0-9]+]]:gpr(p0) = G_GLOBAL_VALUE @var3
+  ; CHECK-NEXT:   [[C1:%[0-9]+]]:gpr(s32) = G_CONSTANT i32 0
+  ; CHECK-NEXT:   [[GV2:%[0-9]+]]:gpr(p0) = G_GLOBAL_VALUE @var1
+  ; CHECK-NEXT:   [[LOAD:%[0-9]+]]:gpr(s32) = G_LOAD [[GV2]](p0) :: (dereferenceable load (s32) from @var1)
+  ; CHECK-NEXT:   [[C2:%[0-9]+]]:gpr(s32) = G_CONSTANT i32 1
+  ; CHECK-NEXT:   [[ICMP:%[0-9]+]]:gpr(s32) = G_ICMP intpred(ne), [[LOAD]](s32), [[C2]]
+  ; CHECK-NEXT:   [[AND:%[0-9]+]]:gpr(s32) = G_AND [[ICMP]], [[C2]]
+  ; CHECK-NEXT:   G_BRCOND [[AND]](s32), %bb.4
+  ; CHECK-NEXT:   G_BR %bb.2
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.2.if.then:
+  ; CHECK-NEXT:   successors: %bb.3(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[GV3:%[0-9]+]]:gpr(p0) = G_GLOBAL_VALUE @var2
+  ; CHECK-NEXT:   G_STORE [[C]](s32), [[GV3]](p0) :: (store (s32) into @var2)
+  ; CHECK-NEXT:   G_BR %bb.3
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.3.if.then2:
+  ; CHECK-NEXT:   successors: %bb.4(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[GV4:%[0-9]+]]:gpr(p0) = G_GLOBAL_VALUE @var1
+  ; CHECK-NEXT:   G_STORE [[C]](s32), [[GV4]](p0) :: (store (s32) into @var1)
+  ; CHECK-NEXT:   G_BR %bb.4
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.4.if.end:
+  ; CHECK-NEXT:   [[GV5:%[0-9]+]]:gpr(p0) = G_GLOBAL_VALUE @var3
+  ; CHECK-NEXT:   G_STORE [[C]](s32), [[GV5]](p0) :: (store (s32) into @var3)
+  ; CHECK-NEXT:   [[C3:%[0-9]+]]:gpr(s32) = G_CONSTANT i32 0
+  ; CHECK-NEXT:   $w0 = COPY [[C3]](s32)
+  ; CHECK-NEXT:   RET_ReallyLR implicit $w0
+entry:
+  %0 = load i32, i32* @var1, align 4
+  %cst1 = bitcast i32 -2228259 to i32
+  %cmp = icmp eq i32 %0, 1
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  store i32 %cst1, i32* @var2
+  br label %if.then2
+
+if.then2:
+  store i32 %cst1, i32* @var1
+  br label %if.end
+
+if.end:
+  store i32 %cst1, i32* @var3
+  ret i32 0
+}
+
+define i64 @imm_cost_too_large_cost_of_4() {
+  ; CHECK-LABEL: name: imm_cost_too_large_cost_of_4
+  ; CHECK: bb.1.entry:
+  ; CHECK-NEXT:   successors: %bb.2(0x40000000), %bb.4(0x40000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[C:%[0-9]+]]:gpr(s64) = G_CONSTANT i64 -2228259
+  ; CHECK-NEXT:   [[GV:%[0-9]+]]:gpr(p0) = G_GLOBAL_VALUE @var2_64
+  ; CHECK-NEXT:   [[GV1:%[0-9]+]]:gpr(p0) = G_GLOBAL_VALUE @var3_64
+  ; CHECK-NEXT:   [[C1:%[0-9]+]]:gpr(s64) = G_CONSTANT i64 0
+  ; CHECK-NEXT:   [[GV2:%[0-9]+]]:gpr(p0) = G_GLOBAL_VALUE @var1_64
+  ; CHECK-NEXT:   [[LOAD:%[0-9]+]]:gpr(s64) = G_LOAD [[GV2]](p0) :: (dereferenceable load (s64) from @var1_64, align 4)
+  ; CHECK-NEXT:   [[C2:%[0-9]+]]:gpr(s64) = G_CONSTANT i64 1
+  ; CHECK-NEXT:   [[ICMP:%[0-9]+]]:gpr(s32) = G_ICMP intpred(ne), [[LOAD]](s64), [[C2]]
+  ; CHECK-NEXT:   [[C3:%[0-9]+]]:gpr(s32) = G_CONSTANT i32 1
+  ; CHECK-NEXT:   [[AND:%[0-9]+]]:gpr(s32) = G_AND [[ICMP]], [[C3]]
+  ; CHECK-NEXT:   G_BRCOND [[AND]](s32), %bb.4
+  ; CHECK-NEXT:   G_BR %bb.2
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.2.if.then:
+  ; CHECK-NEXT:   successors: %bb.3(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[GV3:%[0-9]+]]:gpr(p0) = G_GLOBAL_VALUE @var2_64
+  ; CHECK-NEXT:   G_STORE [[C]](s64), [[GV3]](p0) :: (store (s64) into @var2_64)
+  ; CHECK-NEXT:   G_BR %bb.3
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.3.if.then2:
+  ; CHECK-NEXT:   successors: %bb.4(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[GV4:%[0-9]+]]:gpr(p0) = G_GLOBAL_VALUE @var1_64
+  ; CHECK-NEXT:   G_STORE [[C]](s64), [[GV4]](p0) :: (store (s64) into @var1_64)
+  ; CHECK-NEXT:   G_BR %bb.4
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.4.if.end:
+  ; CHECK-NEXT:   [[GV5:%[0-9]+]]:gpr(p0) = G_GLOBAL_VALUE @var3_64
+  ; CHECK-NEXT:   G_STORE [[C]](s64), [[GV5]](p0) :: (store (s64) into @var3_64)
+  ; CHECK-NEXT:   [[C4:%[0-9]+]]:gpr(s64) = G_CONSTANT i64 0
+  ; CHECK-NEXT:   $x0 = COPY [[C4]](s64)
+  ; CHECK-NEXT:   RET_ReallyLR implicit $x0
+entry:
+  %0 = load i64, i64* @var1_64, align 4
+  %cst1 = bitcast i64 -2228259 to i64
+  %cmp = icmp eq i64 %0, 1
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:
+  store i64 %cst1, i64* @var2_64
+  br label %if.then2
+
+if.then2:
+  store i64 %cst1, i64* @var1_64
+  br label %if.end
+
+if.end:
+  store i64 %cst1, i64* @var3_64
+  ret i64 0
+}
+
+@var1_64 = common global i64 0, align 4
+@var2_64 = common global i64 0, align 4
+@var3_64 = common global i64 0, align 4