[Spill2Reg][4/9] Added x86 profitability model.

[vporpo]

Summary

This is a simple model for checking when Spill2Reg is profitable in x86.
It walks through instructions in the proximity of the spill or reload and
counts the number of memory and vector instructions. If the count of
memory instructions is greater than a threshold and the count of vector
instructions less than a threshold, then we consider it to be profitable.

[vporpo]

Rebased.

[Carrot]

llvm/include/llvm/CodeGen/TargetInstrInfo.h

2041

Use the same format as the messages in other callback functions.

2050

same

2059

same

llvm/lib/Target/X86/X86InstrInfo.cpp

82

'the'

87

Be consistent with other description.

9736

Instead of checking register size, can you check if MO.getReg() belongs to any vector register class explicitly?

9790

I don't understand this statement. Kill flag means the last use of a register, but DstReg will be used to move the value back to integer register.

[vporpo]

Addressed comments.

[vporpo]

The profitability function now checks a radius around the instruction and the mem threshold is now a percentage.

[vporpo]

Using Spill2RegVecInstrsThreshold == 0 as a reserved value that returns true.

[vporpo]

Rebased.

llvm/include/llvm/CodeGen/TargetInstrInfo.h

public:
   virtual const TargetRegisterClass *
   getVectorRegisterClassForSpill2Reg(const TargetRegisterInfo *TRI,
                                      Register SpilledReg) const {
     llvm_unreachable(
         "Target didn't implement "
         "TargetInstrInfo::createVirtualVectorRegisterForSpillToReg!");
   }
 
+  /// \Returns true if it is profitable to perform spill2reg on \p MI.
+  virtual bool isSpill2RegProfitable(const MachineInstr *MI,
+                                     const TargetRegisterInfo *TRI,
+                                     const MachineRegisterInfo *MRI) const {
+    llvm_unreachable(
+        "Target didn't implement TargetInstrInfo::isSpill2RegProfitable!");
+  }
+
+  /// Inserts \p SrcReg into the first lane of \p DstReg.
+  virtual MachineInstr *
+  spill2RegInsertToVectorReg(Register DstReg, Register SrcReg,
+                             int OperationBits, MachineBasicBlock *MBB,
+                             MachineBasicBlock::iterator InsertBeforeIt,
+                             const TargetRegisterInfo *TRI) const {
+    llvm_unreachable(
+        "Target didn't implement TargetInstrInfo::spill2RegInsertToVectorReg!");
+  }
+
+  /// Extracts the first lane of \p SrcReg into \p DstReg.
+  virtual MachineInstr *
+  spill2RegExtractFromVectorReg(Register DstReg, Register SrcReg,
+                                int OperationBits, MachineBasicBlock *InsertMBB,
+                                MachineBasicBlock::iterator InsertBeforeIt,
+                                const TargetRegisterInfo *TRI) const {
+    llvm_unreachable("Target didn't implement "
+                     "TargetInstrInfo::spill2RegExtractFromVectorReg!");
+  }
+
 private:
   mutable std::unique_ptr<MIRFormatter> Formatter;
   unsigned CallFrameSetupOpcode, CallFrameDestroyOpcode;
   unsigned CatchRetOpcode;
   unsigned ReturnOpcode;
 };
 
 /// Provide DenseMapInfo for TargetInstrInfo::RegSubRegPair.

llvm/lib/Target/X86/X86InstrInfo.h

private:
   bool isLegalToSpill2Reg(Register Reg, const TargetRegisterInfo *TRI,
                           const MachineRegisterInfo *MRI) const override;
 
   bool targetSupportsSpill2Reg(const TargetSubtargetInfo *STI) const override;
 
   const TargetRegisterClass *
   getVectorRegisterClassForSpill2Reg(const TargetRegisterInfo *TRI,
                                      Register SpilledReg) const override;
+
+  bool isSpill2RegProfitable(const MachineInstr *MI,
+                             const TargetRegisterInfo *TRI,
+                             const MachineRegisterInfo *MRI) const override;
+
+  MachineInstr *
+  spill2RegInsertToVectorReg(Register DstReg, Register SrcReg,
+                             int OperationBits, MachineBasicBlock *MBB,
+                             MachineBasicBlock::iterator InsertBeforeIt,
+                             const TargetRegisterInfo *TRI) const override;
+
+  MachineInstr *
+  spill2RegExtractFromVectorReg(Register DstReg, Register SrcReg,
+                                int OperationBits, MachineBasicBlock *InsertMBB,
+                                MachineBasicBlock::iterator InsertBeforeIt,
+                                const TargetRegisterInfo *TRI) const override;
 };
 
 } // namespace llvm
 
 #endif

llvm/lib/Target/X86/X86InstrInfo.cpp

PartialRegUpdateClearance("partial-reg-update-clearance",
                                    "register update"),
                           cl::init(64), cl::Hidden);
 static cl::opt<unsigned>
 UndefRegClearance("undef-reg-clearance",
                   cl::desc("How many idle instructions we would like before "
                            "certain undef register reads"),
                   cl::init(128), cl::Hidden);
 
+// A value of 2 was empirically found to work with Skylake.
+static cl::opt<int> Spill2RegMemInstrsThreshold(
+    "spill2reg-mem-instrs", cl::Hidden, cl::init(80),
+    cl::desc("Apply spill2reg if we find at least this much percentage of "
+             "memory nstrs within the explored distance."));
+
+static cl::opt<int> Spill2RegVecInstrsThreshold(
+    "spill2reg-vec-instrs", cl::Hidden, cl::init(1),
+    cl::desc("Apply spill2reg if we find fewer than this many vector instrs "
+             "within the explored distance."));
+
+static cl::opt<int> Spill2RegExplorationDst(
+    "spill2reg-exploration-distance", cl::Hidden, cl::init(4),
+    cl::desc("When checking for profitability, explore nearby instructions "
+             "at this maximum distance."));
 
 // Pin the vtable to this file.
 void X86InstrInfo::anchor() {}
 
 X86InstrInfo::X86InstrInfo(X86Subtarget &STI)
     : X86GenInstrInfo((STI.isTarget64BitLP64() ? X86::ADJCALLSTACKDOWN64
                                                : X86::ADJCALLSTACKDOWN32),
                       (STI.isTarget64BitLP64() ? X86::ADJCALLSTACKUP64

 const TargetRegisterClass *
 X86InstrInfo::getVectorRegisterClassForSpill2Reg(const TargetRegisterInfo *TRI,
                                                  Register SpilledReg) const {
   const TargetRegisterClass *VecRegClass =
       TRI->getRegClass(X86::VR128RegClassID);
   return VecRegClass;
 }
 
+bool X86InstrInfo::isSpill2RegProfitable(const MachineInstr *MI,
+                                         const TargetRegisterInfo *TRI,
+                                         const MachineRegisterInfo *MRI) const {
+  auto IsVecMO = [TRI, MI](const MachineOperand &MO) {
+    const MachineFunction *MF = MI->getParent()->getParent();
+    if (MO.isReg() && MO.getReg().isPhysical()) {
+      for (auto ClassID :
+           {X86::VR128RegClassID, X86::VR256RegClassID, X86::VR512RegClassID})
+        if (TRI->getRegClass(ClassID)->contains(MO.getReg()))
+          return true;
+    }
+    if (MO.isFI()) {
+      const unsigned MinVecBits =
+          TRI->getRegSizeInBits(*TRI->getRegClass(X86::VR128RegClassID));
+      if (MF->getFrameInfo().getObjectSize(MO.getIndex()) >= MinVecBits)
+        return true;
+    }
+    return false;
+  };
+
+  /// \Returns the previous instruction, skipping debug instrs.
+  auto GetPrevNonDebug = [](const MachineInstr *MI) {
+    do {
+      MI = MI->getPrevNode();
+    } while (MI != nullptr && MI->isDebugInstr());
+    return MI;
+  };
+  /// \Returns the next instruction, skipping debug instrs.
+  auto GetNextNonDebug = [](const MachineInstr *MI) {
+    do {
+      MI = MI->getNextNode();
+    } while (MI != nullptr && MI->isDebugInstr());
+    return MI;
+  };
+
+  // This is a simple heuristic. We count the number of memory and vector
+  // instructions both above and below `MI` with a radius of
+  // Spill2RegExplorationDst, and check against threshold values.
+  int CntMem = 0;
+  int CntAll = 0;
+  int CntVec = 0;
+  const MachineInstr *TopMI = MI;
+  const MachineInstr *BotMI = GetNextNonDebug(MI);
+  for (int Radius = 0, MaxRadius = Spill2RegExplorationDst;
+       (TopMI != nullptr || BotMI != nullptr) && Radius < MaxRadius; ++Radius) {
+    if (TopMI != nullptr && !TopMI->memoperands_empty())
+      ++CntMem;
+    if (BotMI != nullptr && !BotMI->memoperands_empty())
+      ++CntMem;
+    if (TopMI != nullptr && llvm::any_of(TopMI->operands(), IsVecMO))
+      ++CntVec;
+    if (BotMI != nullptr && llvm::any_of(BotMI->operands(), IsVecMO))
+      ++CntVec;
+
+    if (TopMI != nullptr) {
+      TopMI = GetPrevNonDebug(TopMI);
+      ++CntAll;
+    }
+    if (BotMI != nullptr) {
+      BotMI = GetNextNonDebug(BotMI);
+      ++CntAll;
+    }
+  }
+  // Return false if exploration ended early because we reached the end of BB.
+  if (Spill2RegMemInstrsThreshold != 0 && CntAll < 2 * Spill2RegExplorationDst)
+    return false;
+  // Else check against the thresholds.
+  bool MemHeuristic = Spill2RegMemInstrsThreshold == 0 ||
+                      (CntMem * 100) / CntAll >= Spill2RegMemInstrsThreshold;
+  bool VecHeuristic =
+      Spill2RegVecInstrsThreshold == 0 || CntVec < Spill2RegVecInstrsThreshold;
+  return MemHeuristic && VecHeuristic;
+}
+
+static unsigned getInsertOrExtractOpcode(unsigned Bits, bool Insert) {
+  switch (Bits) {
+  case 32:
+    return Insert ? X86::MOVDI2PDIrr : X86::MOVPDI2DIrr;
+  case 64:
+    return Insert ? X86::MOV64toPQIrr : X86::MOVPQIto64rr;
+  default:
+    llvm_unreachable("Unsupported bits");
+  }
+}
+
+MachineInstr *X86InstrInfo::spill2RegInsertToVectorReg(
+    Register DstReg, Register SrcReg, int OperationBits, MachineBasicBlock *MBB,
+    MachineBasicBlock::iterator InsertBeforeIt,
+    const TargetRegisterInfo *TRI) const {
+  DebugLoc DL;
+  unsigned InsertOpcode =
+      getInsertOrExtractOpcode(OperationBits, true /*insert*/);
+  const MCInstrDesc &InsertMCID = get(InsertOpcode);
+  MachineInstr *InsertMI =
+      BuildMI(*MBB, InsertBeforeIt, DL, InsertMCID, DstReg).addReg(SrcReg);
+  return InsertMI;
+}
+
+MachineInstr *X86InstrInfo::spill2RegExtractFromVectorReg(
+    Register DstReg, Register SrcReg, int OperationBits,
+    MachineBasicBlock *InsertMBB, MachineBasicBlock::iterator InsertBeforeIt,
+    const TargetRegisterInfo *TRI) const {
+  DebugLoc DL;
+  unsigned ExtractOpcode =
+      getInsertOrExtractOpcode(OperationBits, false /*extract*/);
+  const MCInstrDesc &ExtractMCID = get(ExtractOpcode);
+  MachineInstr *ExtractMI =
+      BuildMI(*InsertMBB, InsertBeforeIt, DL, ExtractMCID, DstReg)
+          .addReg(SrcReg);
+  return ExtractMI;
+}
+
 #define GET_INSTRINFO_HELPERS
 #include "X86GenInstrInfo.inc"