[SystemZ] implement shouldCoalesce()

Implement shouldCoalesce() to help regalloc avoid running out of GR128
registers.

If a COPY involving a subreg of a GR128 is coalesced, the live range of the
GR128 virtual register will be extended. If this happens where there are
enough phys-reg clobbers present, regalloc will run out of registers (if
there is not a single GR128 allocatable register available).

This patch tries to allow coalescing only when it can prove that this will be
safe by checking the (local) interval in question.

Review: Ulrich Weigand, Quentin Colombet
https://reviews.llvm.org/D37899
https://bugs.llvm.org/show_bug.cgi?id=34610

llvm-svn: 314516

6 files changed, 90 insertions, 4 deletions

diff --git a/llvm/lib/Target/AMDGPU/SIRegisterInfo.cpp b/llvm/lib/Target/AMDGPU/SIRegisterInfo.cpp
index 7c73f92eed2..a367bd7e129 100644
--- a/llvm/lib/Target/AMDGPU/SIRegisterInfo.cpp
+++ b/llvm/lib/Target/AMDGPU/SIRegisterInfo.cpp
@@ -1474,7 +1474,8 @@ bool SIRegisterInfo::shouldCoalesce(MachineInstr *MI,
                                     unsigned SubReg,
                                     const TargetRegisterClass *DstRC,
                                     unsigned DstSubReg,
-                                    const TargetRegisterClass *NewRC) const {
+                                    const TargetRegisterClass *NewRC,
+                                    LiveIntervals &LIS) const {
   unsigned SrcSize = getRegSizeInBits(*SrcRC);
   unsigned DstSize = getRegSizeInBits(*DstRC);
   unsigned NewSize = getRegSizeInBits(*NewRC);
diff --git a/llvm/lib/Target/AMDGPU/SIRegisterInfo.h b/llvm/lib/Target/AMDGPU/SIRegisterInfo.h
index 65655b79c21..bf814b6974a 100644
--- a/llvm/lib/Target/AMDGPU/SIRegisterInfo.h
+++ b/llvm/lib/Target/AMDGPU/SIRegisterInfo.h
@@ -22,6 +22,7 @@
 
 namespace llvm {
 
+class LiveIntervals;
 class MachineRegisterInfo;
 class SISubtarget;
 class SIMachineFunctionInfo;
@@ -212,7 +213,8 @@ public:
                       unsigned SubReg,
                       const TargetRegisterClass *DstRC,
                       unsigned DstSubReg,
-                      const TargetRegisterClass *NewRC) const override;
+                      const TargetRegisterClass *NewRC,
+                      LiveIntervals &LIS) const override;
 
   unsigned getRegPressureLimit(const TargetRegisterClass *RC,
                                MachineFunction &MF) const override;
diff --git a/llvm/lib/Target/ARM/ARMBaseRegisterInfo.cpp b/llvm/lib/Target/ARM/ARMBaseRegisterInfo.cpp
index 17269268112..bf39aebaf44 100644
--- a/llvm/lib/Target/ARM/ARMBaseRegisterInfo.cpp
+++ b/llvm/lib/Target/ARM/ARMBaseRegisterInfo.cpp
@@ -807,7 +807,8 @@ bool ARMBaseRegisterInfo::shouldCoalesce(MachineInstr *MI,
                                   unsigned SubReg,
                                   const TargetRegisterClass *DstRC,
                                   unsigned DstSubReg,
-                                  const TargetRegisterClass *NewRC) const {
+                                  const TargetRegisterClass *NewRC,
+                                  LiveIntervals &LIS) const {
   auto MBB = MI->getParent();
   auto MF = MBB->getParent();
   const MachineRegisterInfo &MRI = MF->getRegInfo();
diff --git a/llvm/lib/Target/ARM/ARMBaseRegisterInfo.h b/llvm/lib/Target/ARM/ARMBaseRegisterInfo.h
index 2e91d9d4be2..a8e947184ea 100644
--- a/llvm/lib/Target/ARM/ARMBaseRegisterInfo.h
+++ b/llvm/lib/Target/ARM/ARMBaseRegisterInfo.h
@@ -27,6 +27,8 @@
 
 namespace llvm {
 
+class LiveIntervals;
+
 /// Register allocation hints.
 namespace ARMRI {
 
@@ -204,7 +206,8 @@ public:
                       unsigned SubReg,
                       const TargetRegisterClass *DstRC,
                       unsigned DstSubReg,
-                      const TargetRegisterClass *NewRC) const override;
+                      const TargetRegisterClass *NewRC,
+                      LiveIntervals &LIS) const override;
 };
 
 } // end namespace llvm
diff --git a/llvm/lib/Target/SystemZ/SystemZRegisterInfo.cpp b/llvm/lib/Target/SystemZ/SystemZRegisterInfo.cpp
index d14a0fb0b0b..05f93ce5162 100644
--- a/llvm/lib/Target/SystemZ/SystemZRegisterInfo.cpp
+++ b/llvm/lib/Target/SystemZ/SystemZRegisterInfo.cpp
@@ -10,6 +10,7 @@
 #include "SystemZRegisterInfo.h"
 #include "SystemZInstrInfo.h"
 #include "SystemZSubtarget.h"
+#include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/Target/TargetFrameLowering.h"
@@ -152,6 +153,72 @@ SystemZRegisterInfo::eliminateFrameIndex(MachineBasicBlock::iterator MI,
   MI->getOperand(FIOperandNum + 1).ChangeToImmediate(Offset);
 }
 
+bool SystemZRegisterInfo::shouldCoalesce(MachineInstr *MI,
+                                  const TargetRegisterClass *SrcRC,
+                                  unsigned SubReg,
+                                  const TargetRegisterClass *DstRC,
+                                  unsigned DstSubReg,
+                                  const TargetRegisterClass *NewRC,
+                                  LiveIntervals &LIS) const {
+  assert (MI->isCopy() && "Only expecting COPY instructions");
+
+  // Coalesce anything which is not a COPY involving a subreg to/from GR128.
+  if (!(NewRC->hasSuperClassEq(&SystemZ::GR128BitRegClass) &&
+        (getRegSizeInBits(*SrcRC) <= 64 || getRegSizeInBits(*DstRC) <= 64)))
+    return true;
+
+  // Allow coalescing of a GR128 subreg COPY only if the live ranges are small
+  // and local to one MBB with not too much interferring registers. Otherwise
+  // regalloc may run out of registers.
+
+  unsigned WideOpNo = (getRegSizeInBits(*SrcRC) == 128 ? 1 : 0);
+  unsigned GR128Reg = MI->getOperand(WideOpNo).getReg();
+  unsigned GRNarReg = MI->getOperand((WideOpNo == 1) ? 0 : 1).getReg();
+  LiveInterval &IntGR128 = LIS.getInterval(GR128Reg);
+  LiveInterval &IntGRNar = LIS.getInterval(GRNarReg);
+
+  // Check that the two virtual registers are local to MBB.
+  MachineBasicBlock *MBB = MI->getParent();
+  if (LIS.isLiveInToMBB(IntGR128, MBB) || LIS.isLiveOutOfMBB(IntGR128, MBB) ||
+      LIS.isLiveInToMBB(IntGRNar, MBB) || LIS.isLiveOutOfMBB(IntGRNar, MBB))
+    return false;
+
+  // Find the first and last MIs of the registers.
+  MachineInstr *FirstMI = nullptr, *LastMI = nullptr;
+  if (WideOpNo == 1) {
+    FirstMI = LIS.getInstructionFromIndex(IntGR128.beginIndex());
+    LastMI  = LIS.getInstructionFromIndex(IntGRNar.endIndex());
+  } else {
+    FirstMI = LIS.getInstructionFromIndex(IntGRNar.beginIndex());
+    LastMI  = LIS.getInstructionFromIndex(IntGR128.endIndex());
+  }
+  assert (FirstMI && LastMI && "No instruction from index?");
+
+  // Check if coalescing seems safe by finding the set of clobbered physreg
+  // pairs in the region.
+  BitVector PhysClobbered(getNumRegs());
+  MachineBasicBlock::iterator MII = FirstMI, MEE = LastMI;
+  MEE++;
+  for (; MII != MEE; ++MII) {
+    for (const MachineOperand &MO : MII->operands())
+      if (MO.isReg() && isPhysicalRegister(MO.getReg())) {
+        for (MCSuperRegIterator SI(MO.getReg(), this, true/*IncludeSelf*/);
+             SI.isValid(); ++SI)
+          if (NewRC->contains(*SI)) {
+            PhysClobbered.set(*SI);
+            break;
+          }
+      }
+  }
+
+  // Demand an arbitrary margin of free regs.
+  unsigned const DemandedFreeGR128 = 3;
+  if (PhysClobbered.count() > (NewRC->getNumRegs() - DemandedFreeGR128))
+    return false;
+
+  return true;
+}
+
 unsigned
 SystemZRegisterInfo::getFrameRegister(const MachineFunction &MF) const {
   const SystemZFrameLowering *TFI = getFrameLowering(MF);
diff --git a/llvm/lib/Target/SystemZ/SystemZRegisterInfo.h b/llvm/lib/Target/SystemZ/SystemZRegisterInfo.h
index e41c06c98af..8b690e6da9f 100644
--- a/llvm/lib/Target/SystemZ/SystemZRegisterInfo.h
+++ b/llvm/lib/Target/SystemZ/SystemZRegisterInfo.h
@@ -18,6 +18,8 @@
 
 namespace llvm {
 
+class LiveIntervals;
+
 namespace SystemZ {
 // Return the subreg to use for referring to the even and odd registers
 // in a GR128 pair.  Is32Bit says whether we want a GR32 or GR64.
@@ -59,6 +61,16 @@ public:
   void eliminateFrameIndex(MachineBasicBlock::iterator MI,
                            int SPAdj, unsigned FIOperandNum,
                            RegScavenger *RS) const override;
+
+  /// \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,
+                      LiveIntervals &LIS) const override;
+
   unsigned getFrameRegister(const MachineFunction &MF) const override;
 };