[GlobalISel] Making MachineCSE runnable in the middle of the GlobalISel

[rtereshin]

Summary

Right now, it is not possible to run MachineCSE in the middle of the
GlobalISel pipeline. Being able to run generic optimizations between the
core passes of GlobalISel was one of the goals of the new ISel framework.
This is the first attempt to do it in a POC manner.

The problem is that MachineCSE pass assumes all register operands have a
register class, which, in GlobalISel context, won't be true until after the
InstructionSelect pass. The reason for this behaviour is that before
replacing one virtual register with another, MachineCSE pass (and most of
the other optimization machine passes) must check if the virtual registers'
constraints have a (sufficiently large) intersection, and constrain the
resulting register appropriately if such intersection exists.

GlobalISel extends the representation of such constraints from just a
register class to a tripple (low-level type, register bank, register
class).

This commit adds MachineRegisterInfo::constrainRegAttrs method that extends
MachineRegisterInfo::constrainRegClass to such a tripple.

The idea is that going forward we should use:

• RegisterBankInfo::constrainGenericRegister within GlobalISel's InstructionSelect pass
• MachineRegisterInfo::constrainRegClass within SelectionDAG ISel and FastISel
• MachineRegisterInfo::constrainRegAttrs everywhere else

regardless the target and instruction selector it uses.

For that reason I tried to keep the performance overhead of
constrainRegAttrs comparing to constrainRegClass at a minimum, hence the
helper method.

[bogner]

include/llvm/CodeGen/MachineRegisterInfo.h

669

Don't repeat the function name in new doc comments. If the resulting inconsistency with the rest of the file bugs you you can feel free to clean up the others in a separate commit.

lib/CodeGen/MachineRegisterInfo.cpp

67–68

Why explicitly mark this inline?

97–101

Should this advice about which functions to call be put in the doc comments somewhere instead/as well?

test/CodeGen/AArch64/GlobalISel/machine-cse-mid-pipeline.mir

3–39

I don't think anything in this test references the IR, so we can probably remove this whole block for readability.

45–49

Don't bother with the registers block (here and below). The constraints are specified inline in the IR anyway, so it isn't necessary unless you're specifying a preferred-register.

[rtereshin]

include/llvm/CodeGen/MachineRegisterInfo.h

669

Okay, thanks! Will remove it.

lib/CodeGen/MachineRegisterInfo.cpp

67–68

It's a non-public helper function only used in 2 places with the only purpose to not repeat getRegClass(Reg) call while falling back to the original version of constrainRegClass. As constrainRegAttrs intends to replace constrainRegClass in most of the places, I don't want to create even an appearance of any unnecessary performance overhead on passes that run after ISel, especially when GlobalISel is not used at all.

97–101

Hm, probably. I'm a bit reluctant to change comments / docs to functions I didn't change though, as it might be considered as "unrelated change". Also, it might be a little too invasive before we actually move everything to constrainRegAttrs, maybe I should make a couple of other machine passes runnable mid-GISel-pipeline, and make it all a separate patch.

What do you think?

test/CodeGen/AArch64/GlobalISel/machine-cse-mid-pipeline.mir

3–39

Oh, interesting. So if just some of the functions are not defined, llc fails with function '<function name>' isn't defined in the provided LLVM IR, but if the entire block is removed it works just fine.

Didn't know that, thanks! Will remove it.

45–49

Great, thanks!

[bogner]

lib/CodeGen/MachineRegisterInfo.cpp

67–68

Sure. It might be clearer to just make this a static function (you'll have to pass in the MachineRegisterInfo, obviously). Then the compiler will see that it's only used twice and do the inlining without the hint.

97–101

I don't think updating doc comments of existing functions to reflect how they relate to a new function is unrelated at all - I'd actually argue that it makes the reason for the change in wording more clear.

test/CodeGen/AArch64/GlobalISel/machine-cse-mid-pipeline.mir

3–39

Yep, if there's no function block at all the parser will make up synthetic functions.

[rtereshin]

lib/CodeGen/MachineRegisterInfo.cpp

67–68

Agreed

97–101

All right, I'll update the doc comments instead

[bogner]

LGTM

[bogner]

Roman asked me to commit this for him off-thread. It's r322805.

Thanks Roman!

[rtereshin]

r322805

include/llvm/CodeGen/GlobalISel/RegisterBankInfo.h

virtual unsigned copyCost(const RegisterBank &A, const RegisterBank &B,
     return &A != &B;
   }
 
   /// Constrain the (possibly generic) virtual register \p Reg to \p RC.
   ///
   /// \pre \p Reg is a virtual register that either has a bank or a class.
   /// \returns The constrained register class, or nullptr if there is none.
   /// \note This is a generic variant of MachineRegisterInfo::constrainRegClass
+  /// \note Use MachineRegisterInfo::constrainRegAttrs instead for any non-isel
+  /// purpose, including non-select passes of GlobalISel
   static const TargetRegisterClass *
   constrainGenericRegister(unsigned Reg, const TargetRegisterClass &RC,
                            MachineRegisterInfo &MRI);
 
   /// Identifier used when the related instruction mapping instance
   /// is generated by target independent code.
   /// Make sure not to use that identifier to avoid possible collision.
   static const unsigned DefaultMappingID;

include/llvm/CodeGen/MachineRegisterInfo.h

public:
   /// instruction using the specified register.
   bool hasOneNonDBGUse(unsigned RegNo) 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 to match the FromReg constraints using:
+  /// class and register bank to match the FromReg constraints using one of the
+  /// methods:
   ///
   ///   constrainRegClass(ToReg, getRegClass(FromReg))
+  ///   constrainRegAttrs(ToReg, FromReg)
+  ///   RegisterBankInfo::constrainGenericRegister(ToReg,
+  ///       *MRI.getRegClass(FromReg), MRI)
   ///
-  /// That function will return NULL if the virtual registers have incompatible
-  /// constraints.
+  /// These functions will return a falsy result if the virtual registers have
+  /// incompatible constraints.
   ///
   /// Note that if ToReg is a physical register the function will replace and
   /// apply sub registers to ToReg in order to obtain a final/proper physical
   /// register.
   void replaceRegWith(unsigned FromReg, unsigned ToReg);
 
   /// getVRegDef - Return the machine instr that defines the specified virtual
   /// register or null if none is found.  This assumes that the code is in SSA
public:
   }
 
   /// constrainRegClass - Constrain the register class of the specified virtual
   /// register to be a common subclass of RC and the current register class,
   /// but only if the new class has at least MinNumRegs registers.  Return the
   /// new register class, or NULL if no such class exists.
   /// This should only be used when the constraint is known to be trivial, like
   /// GR32 -> GR32_NOSP. Beware of increasing register pressure.
+  ///
+  /// \note Assumes that the register has a register class assigned.
+  /// Use RegisterBankInfo::constrainGenericRegister in GlobalISel's
+  /// InstructionSelect pass and constrainRegAttrs in every other pass,
+  /// including non-select passes of GlobalISel, instead.
   const TargetRegisterClass *constrainRegClass(unsigned Reg,
                                                const TargetRegisterClass *RC,
                                                unsigned MinNumRegs = 0);
 
+  /// Constrain the register class or the register bank of the virtual register
+  /// \p Reg to be a common subclass and a common bank of both registers
+  /// provided respectively. Do nothing if any of the attributes (classes,
+  /// banks, or low-level types) of the registers are deemed incompatible, or if
+  /// the resulting register will have a class smaller than before and of size
+  /// less than \p MinNumRegs. Return true if such register attributes exist,
+  /// false otherwise.
+  ///
+  /// \note Assumes that each register has either a low-level type or a class
+  /// assigned, but not both. Use this method instead of constrainRegClass and
+  /// RegisterBankInfo::constrainGenericRegister everywhere but SelectionDAG
+  /// ISel / FastISel and GlobalISel's InstructionSelect pass respectively.
+  bool constrainRegAttrs(unsigned Reg, unsigned ConstrainingReg,
+                         unsigned MinNumRegs = 0);
+
   /// recomputeRegClass - Try to find a legal super-class of Reg's register
   /// class that still satisfies the constraints from the instructions using
   /// Reg.  Returns true if Reg was upgraded.
   ///
   /// This method can be used after constraints have been removed from a
   /// virtual register, for example after removing instructions or splitting
   /// the live range.
   bool recomputeRegClass(unsigned Reg);

lib/CodeGen/MachineCSE.cpp

for (MachineOperand &MO : MI->operands()) {
     // MO.substVirtReg(SrcReg, SrcSubReg, *TRI);
     //
     // The 2-addr pass has been updated to handle coalesced subregs. However,
     // some machine-specific code still can't handle it.
     // To handle it properly we also need a way find a constrained subregister
     // class given a super-reg class and subreg index.
     if (DefMI->getOperand(1).getSubReg())
       continue;
-    const TargetRegisterClass *RC = MRI->getRegClass(Reg);
-    if (!MRI->constrainRegClass(SrcReg, RC))
+    if (!MRI->constrainRegAttrs(SrcReg, Reg))
       continue;
     DEBUG(dbgs() << "Coalescing: " << *DefMI);
     DEBUG(dbgs() << "***     to: " << *MI);
     // Propagate SrcReg of copies to MI.
     MO.setReg(SrcReg);
     MRI->clearKillFlags(SrcReg);
     // Coalesce single use copies.
     if (OnlyOneUse) {
for (unsigned i = 0, e = MI->getNumOperands(); NumDefs && i != e; ++i) {
              "Do not CSE physical register defs!");
 
       if (!isProfitableToCSE(NewReg, OldReg, CSMI, MI)) {
         DEBUG(dbgs() << "*** Not profitable, avoid CSE!\n");
         DoCSE = false;
         break;
       }
 
-      // Don't perform CSE if the result of the old instruction cannot exist
-      // within the register class of the new instruction.
-      const TargetRegisterClass *OldRC = MRI->getRegClass(OldReg);
-      if (!MRI->constrainRegClass(NewReg, OldRC)) {
-        DEBUG(dbgs() << "*** Not the same register class, avoid CSE!\n");
+      // Don't perform CSE if the result of the new instruction cannot exist
+      // within the constraints (register class, bank, or low-level type) of
+      // the old instruction.
+      if (!MRI->constrainRegAttrs(NewReg, OldReg)) {
+        DEBUG(dbgs() << "*** Not the same register constraints, avoid CSE!\n");
         DoCSE = false;
         break;
       }
 
       CSEPairs.push_back(std::make_pair(OldReg, NewReg));
       --NumDefs;
     }
 

lib/CodeGen/MachineRegisterInfo.cpp

MachineRegisterInfo::setRegClass(unsigned Reg, const TargetRegisterClass *RC) {
   assert(RC && RC->isAllocatable() && "Invalid RC for virtual register");
   VRegInfo[Reg].first = RC;
 }
 
 void MachineRegisterInfo::setRegBank(unsigned Reg,
                                      const RegisterBank &RegBank) {
   VRegInfo[Reg].first = &RegBank;
 }
 
-const TargetRegisterClass *
-MachineRegisterInfo::constrainRegClass(unsigned Reg,
-                                       const TargetRegisterClass *RC,
-                                       unsigned MinNumRegs) {
-  const TargetRegisterClass *OldRC = getRegClass(Reg);
+static const TargetRegisterClass *
+constrainRegClass(MachineRegisterInfo &MRI, unsigned Reg,
+                  const TargetRegisterClass *OldRC,
+                  const TargetRegisterClass *RC, unsigned MinNumRegs) {
   if (OldRC == RC)
     return RC;
   const TargetRegisterClass *NewRC =
-    getTargetRegisterInfo()->getCommonSubClass(OldRC, RC);
+      MRI.getTargetRegisterInfo()->getCommonSubClass(OldRC, RC);
   if (!NewRC || NewRC == OldRC)
     return NewRC;
   if (NewRC->getNumRegs() < MinNumRegs)
     return nullptr;
-  setRegClass(Reg, NewRC);
+  MRI.setRegClass(Reg, NewRC);
   return NewRC;
 }
 
+const TargetRegisterClass *
+MachineRegisterInfo::constrainRegClass(unsigned Reg,
+                                       const TargetRegisterClass *RC,
+                                       unsigned MinNumRegs) {
+  return ::constrainRegClass(*this, Reg, getRegClass(Reg), RC, MinNumRegs);
+}
+
+bool
+MachineRegisterInfo::constrainRegAttrs(unsigned Reg,
+                                       unsigned ConstrainingReg,
+                                       unsigned MinNumRegs) {
+  auto const *OldRC = getRegClassOrNull(Reg);
+  auto const *RC = getRegClassOrNull(ConstrainingReg);
+  // A virtual register at any point must have either a low-level type
+  // or a class assigned, but not both. The only exception is the internals of
+  // GlobalISel's instruction selection pass, which is allowed to temporarily
+  // introduce registers with types and classes both.
+  assert((OldRC || getType(Reg).isValid()) && "Reg has neither class nor type");
+  assert((!OldRC || !getType(Reg).isValid()) && "Reg has class and type both");
+  assert((RC || getType(ConstrainingReg).isValid()) &&
+         "ConstrainingReg has neither class nor type");
+  assert((!RC || !getType(ConstrainingReg).isValid()) &&
+         "ConstrainingReg has class and type both");
+  if (OldRC && RC)
+    return ::constrainRegClass(*this, Reg, OldRC, RC, MinNumRegs);
+  // If one of the virtual registers is generic (used in generic machine
+  // instructions, has a low-level type, doesn't have a class), and the other is
+  // concrete (used in target specific instructions, doesn't have a low-level
+  // type, has a class), we can not unify them.
+  if (OldRC || RC)
+    return false;
+  // At this point, both registers are guaranteed to have a valid low-level
+  // type, and they must agree.
+  if (getType(Reg) != getType(ConstrainingReg))
+    return false;
+  auto const *OldRB = getRegBankOrNull(Reg);
+  auto const *RB = getRegBankOrNull(ConstrainingReg);
+  if (OldRB)
+    return !RB || RB == OldRB;
+  if (RB)
+    setRegBank(Reg, *RB);
+  return true;
+}
+
 bool
 MachineRegisterInfo::recomputeRegClass(unsigned Reg) {
   const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
   const TargetRegisterClass *OldRC = getRegClass(Reg);
   const TargetRegisterClass *NewRC =
       getTargetRegisterInfo()->getLargestLegalSuperClass(OldRC, *MF);
 
   // Stop early if there is no room to grow.

test/CodeGen/AArch64/GlobalISel/machine-cse-mid-pipeline.mir

+# RUN: llc -run-pass machine-cse -global-isel -verify-machineinstrs -mtriple aarch64-apple-ios %s -o - | FileCheck %s
+---
+name:            irtranslated
+legalized:       false
+regBankSelected: false
+selected:        false
+body:             |
+  ; CHECK-LABEL: name: irtranslated
+  ; CHECK:      %[[ONE:[0-9]+]]:_(s32) = G_CONSTANT i32 1
+  ; CHECK-NEXT: %[[TWO:[0-9]+]]:_(s32) = G_ADD %[[ONE]], %[[ONE]]
+  ; CHECK-NEXT: %[[SUM:[0-9]+]]:_(s32) = G_ADD %[[TWO]], %[[TWO]]
+  ; CHECK-NEXT: %[[RET:[wx][0-9]+]] = COPY %[[SUM]](s32)
+  ; CHECK-NEXT: RET_ReallyLR implicit %[[RET]]
+  bb.0:
+    %0:_(s32) = G_CONSTANT i32 1
+    %1:_(s32) = G_ADD %0, %0
+    %2:_(s32) = G_ADD %0, %0
+    %3:_(s32) = G_ADD %1, %2
+    %w0 = COPY %3(s32)
+    RET_ReallyLR implicit %w0
+...
+---
+name:            regbankselected
+legalized:       true
+regBankSelected: true
+selected:        false
+body:             |
+  ; CHECK-LABEL: name: regbankselected
+  ; CHECK:      %[[ONE:[0-9]+]]:gpr(s32) = G_CONSTANT i32 1
+  ; CHECK-NEXT: %[[TWO:[0-9]+]]:gpr(s32) = G_ADD %[[ONE]], %[[ONE]]
+  ; CHECK-NEXT: %[[SUM:[0-9]+]]:gpr(s32) = G_ADD %[[TWO]], %[[TWO]]
+  ; CHECK-NEXT: %[[RET:[wx][0-9]+]] = COPY %[[SUM]](s32)
+  ; CHECK-NEXT: RET_ReallyLR implicit %[[RET]]
+  bb.0:
+    %0:gpr(s32) = G_CONSTANT i32 1
+    %1:gpr(s32) = G_ADD %0, %0
+    %2:gpr(s32) = G_ADD %0, %0
+    %3:gpr(s32) = G_ADD %1, %2
+    %w0 = COPY %3(s32)
+    RET_ReallyLR implicit %w0
+...
+---
+name:            legalized
+legalized:       true
+regBankSelected: false
+selected:        false
+body:             |
+  ; CHECK-LABEL: name: legalized
+  ; CHECK:      %[[ONE:[0-9]+]]:_(s32) = G_CONSTANT i32 1
+  ; CHECK-NEXT: %[[TWO:[0-9]+]]:gpr(s32) = G_ADD %[[ONE]], %[[ONE]]
+  ; CHECK-NEXT: %[[SUM:[0-9]+]]:_(s32) = G_ADD %[[TWO]], %[[TWO]]
+  ; CHECK-NEXT: %[[RET:[wx][0-9]+]] = COPY %[[SUM]](s32)
+  ; CHECK-NEXT: RET_ReallyLR implicit %[[RET]]
+  bb.0:
+    %0:_(s32) = G_CONSTANT i32 1
+    %1:_(s32) = G_ADD %0, %0
+    %2:gpr(s32) = G_ADD %0, %0
+    %3:_(s32) = G_ADD %1, %2
+    %w0 = COPY %3(s32)
+    RET_ReallyLR implicit %w0
+...
+---
+name:            legalized_sym
+legalized:       true
+regBankSelected: false
+selected:        false
+body:             |
+  ; CHECK-LABEL: name: legalized_sym
+  ; CHECK:      %[[ONE:[0-9]+]]:_(s32) = G_CONSTANT i32 1
+  ; CHECK-NEXT: %[[TWO:[0-9]+]]:gpr(s32) = G_ADD %[[ONE]], %[[ONE]]
+  ; CHECK-NEXT: %[[SUM:[0-9]+]]:_(s32) = G_ADD %[[TWO]], %[[TWO]]
+  ; CHECK-NEXT: %[[RET:[wx][0-9]+]] = COPY %[[SUM]](s32)
+  ; CHECK-NEXT: RET_ReallyLR implicit %[[RET]]
+  bb.0:
+    %0:_(s32) = G_CONSTANT i32 1
+    %1:gpr(s32) = G_ADD %0, %0
+    %2:_(s32) = G_ADD %0, %0
+    %3:_(s32) = G_ADD %1, %2
+    %w0 = COPY %3(s32)
+    RET_ReallyLR implicit %w0
+...
+---
+name:            int_extensions
+alignment:       2
+legalized:       false
+regBankSelected: false
+selected:        false
+body:             |
+  ; CHECK-LABEL: name: int_extensions
+  ; CHECK:      %[[ONE:[0-9]+]]:_(s8) = G_CONSTANT i8 1
+  ; CHECK-NEXT: %[[S16:[0-9]+]]:_(s16) = G_SEXT %[[ONE]](s8)
+  ; CHECK-NEXT: %[[S32:[0-9]+]]:_(s32) = G_SEXT %[[ONE]](s8)
+  ; CHECK-NEXT: %[[S16_Z64:[0-9]+]]:_(s64) = G_ZEXT %[[S16]](s16)
+  ; CHECK-NEXT: %[[S32_Z64:[0-9]+]]:_(s64) = G_ZEXT %[[S32]](s32)
+  ; CHECK-NEXT: %[[SUM:[0-9]+]]:_(s64) = G_ADD %[[S16_Z64]], %[[S32_Z64]]
+  ; CHECK-NEXT: %[[RET:[wx][0-9]+]] = COPY %[[SUM]](s64)
+  ; CHECK-NEXT: RET_ReallyLR implicit %[[RET]]
+  bb.0.entry:
+    %0:_(s8) = G_CONSTANT i8 1
+    %1:_(s16) = G_SEXT %0(s8)
+    %2:_(s32) = G_SEXT %0(s8)
+    %3:_(s64) = G_ZEXT %1(s16)
+    %4:_(s64) = G_ZEXT %2(s32)
+    %5:_(s64) = G_ADD %3, %4
+    %x0 = COPY %5(s64)
+    RET_ReallyLR implicit %x0
+...
+---
+name:            generic
+legalized:       true
+regBankSelected: false
+selected:        false
+body:             |
+  ; CHECK-LABEL: name: generic
+  ; CHECK:      %[[SG:[0-9]+]]:_(s32) = G_ADD %{{[0-9]+}}, %{{[0-9]+}}
+  ; CHECK-NEXT: %{{[0-9]+}}:_(s32) = G_ADD %[[SG]], %[[SG]]
+  bb.0:
+    %0:_(s32) = COPY %w0
+    %1:_(s32) = COPY %w1
+    %2:_(s32) = G_ADD %0, %1
+    %3:_(s32) = COPY %2(s32)
+    %4:_(s32) = G_ADD %3, %3
+    %w0 = COPY %4(s32)
+    RET_ReallyLR implicit %w0
+...
+---
+name:            generic_to_concrete_copy
+legalized:       true
+regBankSelected: false
+selected:        false
+body:             |
+  ; CHECK-LABEL: name: generic_to_concrete_copy
+  ; CHECK:      %[[S1:[0-9]+]]:_(s32) = G_ADD %{{[0-9]+}}, %{{[0-9]+}}
+  ; CHECK-NEXT: %[[S2:[0-9]+]]:gpr32 = COPY %[[S1]](s32)
+  ; CHECK-NEXT: %{{[0-9]+}}:gpr32 = ADDWrr %[[S2]], %[[S2]]
+  bb.0:
+    %0:_(s32) = COPY %w0
+    %1:_(s32) = COPY %w1
+    %2:_(s32) = G_ADD %0, %1
+    %3:gpr32 = COPY %2(s32)
+    %4:gpr32 = ADDWrr %3, %3
+    %w0 = COPY %4
+    RET_ReallyLR implicit %w0
+...
+---
+name:            concrete_to_generic_copy
+legalized:       true
+regBankSelected: false
+selected:        false
+body:             |
+  ; CHECK-LABEL: name: concrete_to_generic_copy
+  ; CHECK:      %[[S1:[0-9]+]]:gpr32 = ADDWrr %{{[0-9]+}}, %{{[0-9]+}}
+  ; CHECK-NEXT: %[[S2:[0-9]+]]:_(s32) = COPY %[[S1]]
+  ; CHECK-NEXT: %{{[0-9]+}}:_(s32) = G_ADD %[[S2]], %[[S2]]
+  bb.0:
+    %0:gpr32 = COPY %w0
+    %1:gpr32 = COPY %w1
+    %2:gpr32 = ADDWrr %0, %1
+    %3:_(s32) = COPY %2
+    %4:_(s32) = G_ADD %3, %3
+    %w0 = COPY %4(s32)
+    RET_ReallyLR implicit %w0
+...
+---
+name:            concrete
+legalized:       true
+regBankSelected: false
+selected:        false
+body:             |
+  ; CHECK-LABEL: name: concrete
+  ; CHECK:      %[[SC:[0-9]+]]:gpr32 = ADDWrr %{{[0-9]+}}, %{{[0-9]+}}
+  ; CHECK-NEXT: %{{[0-9]+}}:gpr32 = ADDWrr %[[SC]], %[[SC]]
+  bb.0:
+    %0:gpr32 = COPY %w0
+    %1:gpr32 = COPY %w1
+    %2:gpr32 = ADDWrr %0, %1
+    %3:gpr32 = COPY %2
+    %4:gpr32 = ADDWrr %3, %3
+    %w0 = COPY %4
+    RET_ReallyLR implicit %w0
+...