[Spill2Reg][3/9] Code generation part 1.

[vporpo]

Summary

This adds the main structure of the code generation phase of Spill2Reg.
Iterate through the spills/reloads collected earlier and generate the
new instructions.

[vporpo]

Rebased

[Carrot]

llvm/include/llvm/CodeGen/TargetInstrInfo.h

2029

For different sized registers we may spill to different vector register class. For example on ARM with NEON, 32 bit value can be spilled to S registers, 64 bit value can be spilled to D registers.

2032

Other functions use ! instead of ().

[vporpo]

llvm/include/llvm/CodeGen/TargetInstrInfo.h

2029

I added an additional argument to this function to pass the hard register being spilled, such that each target can decide which vector register class to use.

[vporpo]

Addressed comments.

[vporpo]

Rebased.

llvm/include/llvm/CodeGen/TargetInstrInfo.h

virtual bool isLegalToSpill2Reg(Register Reg, const TargetRegisterInfo *TRI,
     llvm_unreachable(
         "Target didn't implement TargetInstrInfo::isLegalToSpill2Reg!");
   }
 
   virtual bool targetSupportsSpill2Reg(const TargetSubtargetInfo *STI) const {
     return false;
   }
 
+  virtual const TargetRegisterClass *
+  getVectorRegisterClassForSpill2Reg(const TargetRegisterInfo *TRI,
+                                     Register SpilledReg) const {
+    llvm_unreachable(
+        "Target didn't implement "
+        "TargetInstrInfo::createVirtualVectorRegisterForSpillToReg!");
+  }
+
 private:
   mutable std::unique_ptr<MIRFormatter> Formatter;
   unsigned CallFrameSetupOpcode, CallFrameDestroyOpcode;
   unsigned CatchRetOpcode;
   unsigned ReturnOpcode;
 };
 
 /// Provide DenseMapInfo for TargetInstrInfo::RegSubRegPair.

llvm/lib/CodeGen/Spill2Reg.cpp

 /// \file This file implements Spill2Reg, an optimization which selectively
 /// replaces spills/reloads to/from the stack with register copies to/from the
 /// vector register file. This works even on targets where load/stores have
 /// similar latency to register copies because it can free up memory units which
 /// helps avoid back-end stalls.
 ///
 //===----------------------------------------------------------------------===//
 
+#include "AllocationOrder.h"
+#include "llvm/CodeGen/LiveRegUnits.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/TargetInstrInfo.h"
 #include "llvm/CodeGen/TargetRegisterInfo.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Support/CommandLine.h"
#endif
     Register getSpilledReg() const { return Spills.front().MO->getReg(); }
 #ifndef NDEBUG
     LLVM_DUMP_METHOD void dump() const;
 #endif
   };
   /// Look for candidates for spill2reg. These candidates are in places with
   /// high memory unit contention. Fills in StackSlotData.
   void collectSpillsAndReloads();
+  /// \Returns if \p MI is profitable to apply spill-to-reg by checking whether
+  /// this would remove pipeline bubbles.
+  bool isProfitable(const MachineInstr *MI) const;
+  /// \Returns true if any stack-based spill/reload in \p Entry is profitable
+  /// to replace with a reg-based spill/reload.
+  bool allAccessesProfitable(const StackSlotDataEntry &Entry) const;
+  /// Look for a free physical register in \p LRU of reg class \p RegClass.
+  llvm::Optional<MCRegister>
+  tryGetFreePhysicalReg(const TargetRegisterClass *RegClass,
+                        const LiveRegUnits &LRU);
+  /// Helper for generateCode(). It eplaces stack spills or reloads with movs
+  /// to \p LI.reg().
+  void replaceStackWithReg(StackSlotDataEntry &Entry, Register VectorReg);
+  /// Updates \p LRU with the liveness of physical registers around the spills
+  /// and reloads in \p Entry.
+  void calculateLiveRegs(StackSlotDataEntry &Entry, LiveRegUnits &LRU);
   /// Replace spills to stack with spills to registers (same for reloads).
   void generateCode();
   /// Cleanup data structures once the pass is finished.
   void cleanup();
   /// The main entry point for this pass.
   bool run();
 
   /// Map from a stack slot to the corresponding spills and reloads.
   DenseMap<int, StackSlotDataEntry> StackSlotData;
 
   MachineFunction *MF = nullptr;
   MachineRegisterInfo *MRI = nullptr;
   MachineFrameInfo *MFI = nullptr;
   const TargetInstrInfo *TII = nullptr;
   const TargetRegisterInfo *TRI = nullptr;
+  RegisterClassInfo RegClassInfo;
 };
 
 } // namespace
 
 void Spill2Reg::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesCFG();
   MachineFunctionPass::getAnalysisUsage(AU);
 }
bool Spill2Reg::runOnMachineFunction(MachineFunction &MFn) {
   MRI = &MF->getRegInfo();
   MFI = &MF->getFrameInfo();
   TII = MF->getSubtarget().getInstrInfo();
   TRI = MF->getSubtarget().getRegisterInfo();
   // Enable only if the target supports the appropriate vector instruction set.
   if (!TII->targetSupportsSpill2Reg(&MF->getSubtarget()))
     return false;
 
+  RegClassInfo.runOnMachineFunction(MFn);
+
   return run();
 }
 
 char Spill2Reg::ID = 0;
 
 char &llvm::Spill2RegID = Spill2Reg::ID;
 
 void Spill2Reg::collectSpillsAndReloads() {
for (MachineInstr &MI : MBB) {
             auto &Entry = StackSlotData[StackSlot];
             Entry.Disable = true;
           }
       }
     }
   }
 }
 
-void Spill2Reg::generateCode() { llvm_unreachable("Unimplemented"); }
+bool Spill2Reg::isProfitable(const MachineInstr *MI) const {
+  // TODO: Unimplemented.
+  return true;
+}
+
+bool Spill2Reg::allAccessesProfitable(const StackSlotDataEntry &Entry) const {
+  auto IsProfitable = [this](const auto &MID) { return isProfitable(MID.MI); };
+  return llvm::all_of(Entry.Spills, IsProfitable) &&
+         llvm::all_of(Entry.Reloads, IsProfitable);
+}
+
+llvm::Optional<MCRegister>
+Spill2Reg::tryGetFreePhysicalReg(const TargetRegisterClass *RegClass,
+                                 const LiveRegUnits &LRU) {
+  auto Order = RegClassInfo.getOrder(RegClass);
+  for (auto I = Order.begin(), E = Order.end(); I != E; ++I) {
+    MCRegister PhysVectorReg = *I;
+    if (LRU.available(PhysVectorReg))
+      return PhysVectorReg;
+  }
+  return None;
+}
+
+// Replace stack-based spills/reloads with register-based ones.
+void Spill2Reg::replaceStackWithReg(StackSlotDataEntry &Entry,
+                                    Register VectorReg) {
+  // TODO: Unimplemented
+}
+
+void Spill2Reg::calculateLiveRegs(StackSlotDataEntry &Entry,
+                                  LiveRegUnits &LRU) {
+  // TODO: Unimplemented
+}
+
+void Spill2Reg::generateCode() {
+  for (auto &Pair : StackSlotData) {
+    StackSlotDataEntry &Entry = Pair.second;
+    // Skip if this stack slot was disabled during data collection.
+    if (Entry.Disable)
+      continue;
+
+    // We decide to spill2reg if any of the spills/reloads are in a hotspot.
+    if (!allAccessesProfitable(Entry))
+      continue;
+
+    // Calculate liveness for Entry.
+    LiveRegUnits LRU(*TRI);
+    calculateLiveRegs(Entry, LRU);
+
+    // Look for a physical register that in LRU.
+    llvm::Optional<MCRegister> PhysVectorRegOpt = tryGetFreePhysicalReg(
+        TII->getVectorRegisterClassForSpill2Reg(TRI, Entry.getSpilledReg()),
+        LRU);
+    if (!PhysVectorRegOpt)
+      continue;
+
+    // Replace stack accesses with register accesses.
+    replaceStackWithReg(Entry, *PhysVectorRegOpt);
+  }
+}
 
 void Spill2Reg::cleanup() { StackSlotData.clear(); }
 
 bool Spill2Reg::run() {
   // Walk over each instruction in the code keeping track of the processor's
   // port pressure and look for memory unit hot-spots.
   collectSpillsAndReloads();
 

llvm/lib/Target/X86/X86InstrInfo.h

bool isRedundantFlagInstr(const MachineInstr &FlagI, Register SrcReg,
                             Register SrcReg2, int64_t ImmMask, int64_t ImmValue,
                             const MachineInstr &OI, bool *IsSwapped,
                             int64_t *ImmDelta) const;
 
   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;
 };
 
 } // namespace llvm
 
 #endif

llvm/lib/Target/X86/X86InstrInfo.cpp

 }
 
 bool X86InstrInfo::targetSupportsSpill2Reg(
     const TargetSubtargetInfo *STI) const {
   const X86Subtarget *X86STI = static_cast<const X86Subtarget *>(STI);
   return X86STI->hasSSE41();
 }
 
+const TargetRegisterClass *
+X86InstrInfo::getVectorRegisterClassForSpill2Reg(const TargetRegisterInfo *TRI,
+                                                 Register SpilledReg) const {
+  const TargetRegisterClass *VecRegClass =
+      TRI->getRegClass(X86::VR128RegClassID);
+  return VecRegClass;
+}
+
 #define GET_INSTRINFO_HELPERS
 #include "X86GenInstrInfo.inc"