[MachineScheduler / CalcSpillWeights] Try to utilize foldable operands better.

[jonpa]

Summary

This patch was needed to get some tests to pass while working on mischeduling for SystemZ.
On a benchmark suite, this patch also increased "folded stack accesses" from 14528 to 14736.

I am curious to hear what other think about this as I am not myself sure this is necessarily the best
way of achieving these results. To get the regression tests to pass, the heuristic had to be placed
3rd last in the list of the heuristics. However, it may well be that nearly same general results would
could be had if placing it lower down...

• If an instrution has an equivalent instruction that instead of reading a register, reads a memory location, it would be better to spill that register since the reload of it can then be folded.
  
  This patch tries to improve MachineScheduler and CalcSpillWeigths in this direction, by using a new TargetInstrInfo virtual method hasFoldableOperand().
  
  SystemZ has already a map for such instructions (getMemOpcode()), which is used to implement this method.

[atrick]

I have some reservations about adding features to the generic scheduler that are too target specific (since it's easy for targets to provide a custom scheduling strategy). But this seems like a reasonable enough hook to add.

[jonpa]

Since no target other than SystemZ is using this at the moment, I will simply let these changes go in with the main SystemZ scheduler patch (http://reviews.llvm.org/D17260).

include/llvm/CodeGen/MachineScheduler.h

struct MachineSchedPolicy {
   // is true, the scheduler runs in both directions and converges.
   bool OnlyTopDown;
   bool OnlyBottomUp;
 
   // Disable heuristic that tries to fetch nodes from long dependency chains
   // first.
   bool DisableLatencyHeuristic;
 
+  // If true, try to use instructions which can fold a reload of a reg.
+  bool FoldableReloadHeuristic;
+
   MachineSchedPolicy(): ShouldTrackPressure(false), ShouldTrackLaneMasks(false),
-    OnlyTopDown(false), OnlyBottomUp(false), DisableLatencyHeuristic(false) {}
+    OnlyTopDown(false), OnlyBottomUp(false), DisableLatencyHeuristic(false),
+    FoldableReloadHeuristic(false) {}
 };
 
 /// MachineSchedStrategy - Interface to the scheduling algorithm used by
 /// ScheduleDAGMI.
 ///
 /// Initialization sequence:
 ///   initPolicy -> shouldTrackPressure -> initialize(DAG) -> registerRoots
 class MachineSchedStrategy {

 /// scheduling candidates based on TargetSchedModel making it easy to implement
 /// heuristics for either preRA or postRA scheduling.
 class GenericSchedulerBase : public MachineSchedStrategy {
 public:
   /// Represent the type of SchedCandidate found within a single queue.
   /// pickNodeBidirectional depends on these listed by decreasing priority.
   enum CandReason {
     NoCand, PhysRegCopy, RegExcess, RegCritical, Stall, Cluster, Weak, RegMax,
-    ResourceReduce, ResourceDemand, BotHeightReduce, BotPathReduce,
+    ResourceReduce, ResourceDemand, FoldReload, BotHeightReduce, BotPathReduce,
     TopDepthReduce, TopPathReduce, NextDefUse, NodeOrder};
 
 #ifndef NDEBUG
   static const char *getReasonStr(GenericSchedulerBase::CandReason Reason);
 #endif
 
   /// Policy for scheduling the next instruction in the candidate's zone.
   struct CandPolicy {

include/llvm/Target/TargetInstrInfo.h

protected:
   virtual bool
   getInsertSubregLikeInputs(const MachineInstr &MI, unsigned DefIdx,
                             RegSubRegPair &BaseReg,
                             RegSubRegPairAndIdx &InsertedReg) const {
     return false;
   }
 
 public:
+  /// Return true if MI has an equivalent instruction that instead
+  /// reads one source reg from memory. If reg is 0, true is returned
+  /// if such an equivalent instruction exists, but if reg is given a
+  /// check is done that reg is used in the foldable operand.
+  virtual bool hasFoldableOperand(const MachineInstr *MI,
+                                  unsigned reg = 0) const { return false; }
+
   /// unfoldMemoryOperand - Separate a single instruction which folded a load or
   /// a store or a load and a store into two or more instruction. If this is
   /// possible, returns true as well as the new instructions by reference.
   virtual bool unfoldMemoryOperand(MachineFunction &MF, MachineInstr *MI,
                                 unsigned Reg, bool UnfoldLoad, bool UnfoldStore,
                                  SmallVectorImpl<MachineInstr*> &NewMIs) const{
     return false;
   }

lib/CodeGen/CalcSpillWeights.cpp

static bool isRematerializable(const LiveInterval &LI,
   }
   return true;
 }
 
 void
 VirtRegAuxInfo::calculateSpillWeightAndHint(LiveInterval &li) {
   MachineRegisterInfo &mri = MF.getRegInfo();
   const TargetRegisterInfo &tri = *MF.getSubtarget().getRegisterInfo();
+  const TargetInstrInfo &tii = *MF.getSubtarget().getInstrInfo();
   MachineBasicBlock *mbb = nullptr;
   MachineLoop *loop = nullptr;
   bool isExiting = false;
   float totalWeight = 0;
   unsigned numInstr = 0; // Number of instructions using li
   SmallPtrSet<MachineInstr*, 8> visited;
 
   // Find the best physreg hint and the best virtreg hint.
if (Spillable) {
         mbb = mi->getParent();
         loop = Loops.getLoopFor(mbb);
         isExiting = loop ? loop->isLoopExiting(mbb) : false;
       }
 
       // Calculate instr weight.
       bool reads, writes;
       std::tie(reads, writes) = mi->readsWritesVirtualRegister(li.reg);
+      // If mi can be transformed to fold a reload of li.reg, then
+      // weight for reading becomes 0.
+      if (reads && tii.hasFoldableOperand(mi, li.reg))
+        reads = false;
+
       weight = LiveIntervals::getSpillWeight(
         writes, reads, &MBFI, mi);
 
       // Give extra weight to what looks like a loop induction variable update.
       if (writes && isExiting && LIS.isLiveOutOfMBB(li, mbb))
         weight *= 3;
 
       totalWeight += weight;

lib/CodeGen/MachineScheduler.cpp

const char *GenericSchedulerBase::getReasonStr(
   case RegExcess:      return "REG-EXCESS";
   case RegCritical:    return "REG-CRIT  ";
   case Stall:          return "STALL     ";
   case Cluster:        return "CLUSTER   ";
   case Weak:           return "WEAK      ";
   case RegMax:         return "REG-MAX   ";
   case ResourceReduce: return "RES-REDUCE";
   case ResourceDemand: return "RES-DEMAND";
+  case FoldReload:     return "FOLDRELOAD";
   case TopDepthReduce: return "TOP-DEPTH ";
   case TopPathReduce:  return "TOP-PATH  ";
   case BotHeightReduce:return "BOT-HEIGHT";
   case BotPathReduce:  return "BOT-PATH  ";
   case NextDefUse:     return "DEF-USE   ";
   case NodeOrder:      return "ORDER     ";
   };
   llvm_unreachable("Unknown reason!");
else {
     }
     if (tryGreater(TryCand.SU->getDepth(), Cand.SU->getDepth(),
                    TryCand, Cand, GenericSchedulerBase::BotPathReduce))
       return true;
   }
   return false;
 }
 
+static bool tryFoldableReload(GenericSchedulerBase::SchedCandidate &TryCand,
+                              GenericSchedulerBase::SchedCandidate &Cand,
+                              SchedBoundary &Zone,
+                              const TargetInstrInfo *TII) {
+  bool CandReloadFoldable = TII->hasFoldableOperand(Cand.SU->getInstr());
+  bool TryCandReloadFoldable = TII->hasFoldableOperand(TryCand.SU->getInstr());
+
+  if (Zone.isTop()) {
+    if (tryLess(TryCandReloadFoldable, CandReloadFoldable,
+                TryCand, Cand, GenericSchedulerBase::FoldReload))
+      return true;
+  }
+  else {
+    if (tryGreater(TryCandReloadFoldable, CandReloadFoldable,
+                   TryCand, Cand, GenericSchedulerBase::FoldReload))
+      return true;
+  }
+  return false;
+}
+
 static void tracePick(const GenericSchedulerBase::SchedCandidate &Cand,
                       bool IsTop) {
   DEBUG(dbgs() << "Pick " << (IsTop ? "Top " : "Bot ")
         << GenericSchedulerBase::getReasonStr(Cand.Reason) << '\n');
 }
 
 void GenericScheduler::initialize(ScheduleDAGMI *dag) {
   assert(dag->hasVRegLiveness() &&
void GenericScheduler::tryCandidate(SchedCandidate &Cand,
   if (tryLess(TryCand.ResDelta.CritResources, Cand.ResDelta.CritResources,
               TryCand, Cand, ResourceReduce))
     return;
   if (tryGreater(TryCand.ResDelta.DemandedResources,
                  Cand.ResDelta.DemandedResources,
                  TryCand, Cand, ResourceDemand))
     return;
 
+  // Try to put lower in final schedule an instruction that doesn't
+  // mind if a source reg gets spilled, i.e. it can fold a reload of
+  // it. This makes the source operands more likely to be spilled, as
+  // opposed to the def operand.
+  if (RegionPolicy.FoldableReloadHeuristic &&
+      tryFoldableReload(TryCand, Cand, Zone, DAG->TII))
+    return;
+
   // Avoid serializing long latency dependence chains.
   // For acyclic path limited loops, latency was already checked above.
   if (!RegionPolicy.DisableLatencyHeuristic && Cand.Policy.ReduceLatency &&
       !Rem.IsAcyclicLatencyLimited && tryLatency(TryCand, Cand, Zone)) {
     return;
   }
 
   // Prefer immediate defs/users of the last scheduled instruction. This is a

lib/Target/SystemZ/SystemZInstrInfo.h

MachineInstr *foldMemoryOperandImpl(MachineFunction &MF, MachineInstr *MI,
                                       ArrayRef<unsigned> Ops,
                                       MachineBasicBlock::iterator InsertPt,
                                       int FrameIndex) const override;
   MachineInstr *foldMemoryOperandImpl(MachineFunction &MF, MachineInstr *MI,
                                       ArrayRef<unsigned> Ops,
                                       MachineBasicBlock::iterator InsertPt,
                                       MachineInstr *LoadMI) const override;
   bool expandPostRAPseudo(MachineBasicBlock::iterator MBBI) const override;
+  bool hasFoldableOperand(const MachineInstr *MI, unsigned reg = 0) const
+    override;
   bool ReverseBranchCondition(SmallVectorImpl<MachineOperand> &Cond) const
     override;
 
   // Return the SystemZRegisterInfo, which this class owns.
   const SystemZRegisterInfo &getRegisterInfo() const { return RI; }
 
   // Return the size in bytes of MI.
   uint64_t getInstSizeInBytes(const MachineInstr *MI) const;

lib/Target/SystemZ/SystemZInstrInfo.cpp

while (I != MBB.begin()) {
     I = MBB.end();
     ++Count;
   }
 
   return Count;
 }
 
 bool SystemZInstrInfo::
+hasFoldableOperand(const MachineInstr *MI, unsigned reg) const {
+  if (SystemZ::getMemOpcode(MI->getOpcode()) == -1)
+    return false;
+
+  // If MI is mapped to a memory-opcode, it can fold one of its
+  // operands in case that operand register gets spilled. If reg is 0,
+  // we don't know which operand might be spilled, but the mischeduler
+  // TryCandidate() can help things a bit generally by putting MI a
+  // bit lower in final schedule.
+  if (!reg)
+    return true;
+
+  // If reg is given, check if that operand could be folded if placed
+  // on stack. CalcSpillWeights will in this case decrease the cost
+  // estimate for spilling the register.
+  unsigned NumOps = MI->getNumExplicitOperands();
+  const MachineOperand &MO = MI->getOperand(NumOps - 1);
+  return (MO.isReg() && MO.getReg() == reg);
+}
+
+bool SystemZInstrInfo::
 ReverseBranchCondition(SmallVectorImpl<MachineOperand> &Cond) const {
   assert(Cond.size() == 2 && "Invalid condition");
   Cond[1].setImm(Cond[1].getImm() ^ Cond[0].getImm());
   return false;
 }
 
 unsigned
 SystemZInstrInfo::InsertBranch(MachineBasicBlock &MBB, MachineBasicBlock *TBB,
if (MMO->getSize() == Size && !MMO->isVolatile()) {
             .addFrameIndex(FrameIndex)
             .addImm(0)
             .addMemOperand(MMO);
       }
     }
   }
 
   // If the spilled operand is the final one, try to change <INSN>R
-  // into <INSN>.
+  // into <INSN>. TODO: Is it possible to commute instructions here?
   int MemOpcode = SystemZ::getMemOpcode(Opcode);
   if (MemOpcode >= 0) {
     unsigned NumOps = MI->getNumExplicitOperands();
     if (OpNum == NumOps - 1) {
       const MCInstrDesc &MemDesc = get(MemOpcode);
       uint64_t AccessBytes = SystemZII::getAccessSize(MemDesc.TSFlags);
       assert(AccessBytes != 0 && "Size of access should be known");
       assert(AccessBytes <= Size && "Access outside the frame index");

lib/Target/SystemZ/SystemZSubtarget.h

public:
   }
   const SystemZTargetLowering *getTargetLowering() const override {
     return &TLInfo;
   }
   const SelectionDAGTargetInfo *getSelectionDAGInfo() const override {
     return &TSInfo;
   }
 
+  void overrideSchedPolicy(MachineSchedPolicy &Policy,
+                           MachineInstr *begin, MachineInstr *end,
+                           unsigned NumRegionInstrs) const override;
+
   // This is important for reducing register pressure in vector code.
   bool useAA() const override { return true; }
 
   // Automatically generated by tblgen.
   void ParseSubtargetFeatures(StringRef CPU, StringRef FS);
 
   // Return true if the target has the distinct-operands facility.
   bool hasDistinctOps() const { return HasDistinctOps; }

lib/Target/SystemZ/SystemZSubtarget.cpp

 //===-- SystemZSubtarget.cpp - SystemZ subtarget information --------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "SystemZSubtarget.h"
 #include "MCTargetDesc/SystemZMCTargetDesc.h"
 #include "llvm/IR/GlobalValue.h"
+#include "llvm/CodeGen/MachineScheduler.h"
 
 using namespace llvm;
 
+static cl::opt<bool>
+FoldableReloadHeuristic("foldable-reloads", cl::Hidden,
+            cl::desc("Consider reg->memory opcodes during mischeduling"), 
+            cl::init(true));
+
 #define DEBUG_TYPE "systemz-subtarget"
 
 #define GET_SUBTARGETINFO_TARGET_DESC
 #define GET_SUBTARGETINFO_CTOR
 #include "SystemZGenSubtargetInfo.inc"
 
 // Pin the vtable to this file.
 void SystemZSubtarget::anchor() {}
bool SystemZSubtarget::isPC32DBLSymbol(const GlobalValue *GV,
   if (CM == CodeModel::Small)
     return bindsLocally(GV, RM);
 
   // For Medium and above, assume that the symbol is not within the 4GB range.
   // Taking the address of locally-defined text would be OK, but that
   // case isn't easy to detect.
   return false;
 }
+
+void SystemZSubtarget::
+overrideSchedPolicy(MachineSchedPolicy &Policy,
+                    MachineInstr *begin, MachineInstr *end,
+                    unsigned NumRegionInstrs) const
+{
+  // Bidirectional scheduling pre-ra is benefitial according to benchmarks.
+  Policy.OnlyTopDown = false;
+  Policy.OnlyBottomUp = false;
+
+  // Enable heuristic for foldable reloads, i.e. prefer to spill a
+  // register if it is read by an instruction who can fold the reload.
+  Policy.FoldableReloadHeuristic = FoldableReloadHeuristic;
+}