lib/CodeGen/Spiller.h

   1 //===-- llvm/CodeGen/Spiller.h - Spiller -*- C++ -*------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #ifndef LLVM_CODEGEN_SPILLER_H
  11 #define LLVM_CODEGEN_SPILLER_H
  12
  13 #include "llvm/Target/TargetRegisterInfo.h"
  14 #include "llvm/ADT/BitVector.h"
  15 #include "llvm/ADT/IndexedMap.h"
  16 #include "llvm/ADT/SmallPtrSet.h"
  17 #include "llvm/ADT/SmallVector.h"
  18 #include "llvm/Support/Streams.h"
  19 #include "llvm/Function.h"
  20 #include "llvm/CodeGen/MachineFrameInfo.h"
  21 #include "llvm/CodeGen/MachineFunction.h"
  22 #include "llvm/CodeGen/MachineInstrBuilder.h"
  23 #include "llvm/CodeGen/MachineRegisterInfo.h"
  24 #include "llvm/Target/TargetMachine.h"
  25 #include "llvm/Target/TargetInstrInfo.h"
  26 #include "llvm/Support/CommandLine.h"
  27 #include "llvm/Support/Compiler.h"
  28 #include "llvm/Support/Debug.h"
  29 #include "llvm/ADT/BitVector.h"
  30 #include "llvm/ADT/DenseMap.h"
  31 #include "llvm/ADT/DepthFirstIterator.h"
  32 #include "llvm/ADT/Statistic.h"
  33 #include "llvm/ADT/STLExtras.h"
  34 #include "llvm/ADT/SmallSet.h"
  35 #include "VirtRegMap.h"
  36 #include <map>
  37
  38 namespace llvm {
  39
  40   /// Spiller interface: Implementations of this interface assign spilled
  41   /// virtual registers to stack slots, rewriting the code.
  42   struct Spiller {
  43     virtual ~Spiller();
  44     virtual bool runOnMachineFunction(MachineFunction &MF,
  45                                       VirtRegMap &VRM) = 0;
  46   };
  47
  48   /// createSpiller - Create an return a spiller object, as specified on the
  49   /// command line.
  50   Spiller* createSpiller();
  51
  52   // ************************************************************************ //
  53
  54   // Simple Spiller Implementation
  55   struct VISIBILITY_HIDDEN SimpleSpiller : public Spiller {
  56     bool runOnMachineFunction(MachineFunction& mf, VirtRegMap &VRM);
  57   };
  58
  59   // ************************************************************************ //
  60
  61   /// AvailableSpills - As the local spiller is scanning and rewriting an MBB
  62   /// from top down, keep track of which spills slots or remat are available in
  63   /// each register.
  64   ///
  65   /// Note that not all physregs are created equal here.  In particular, some
  66   /// physregs are reloads that we are allowed to clobber or ignore at any time.
  67   /// Other physregs are values that the register allocated program is using
  68   /// that we cannot CHANGE, but we can read if we like.  We keep track of this
  69   /// on a per-stack-slot / remat id basis as the low bit in the value of the
  70   /// SpillSlotsAvailable entries.  The predicate 'canClobberPhysReg()' checks
  71   /// this bit and addAvailable sets it if.
  72   class VISIBILITY_HIDDEN AvailableSpills {
  73     const TargetRegisterInfo *TRI;
  74     const TargetInstrInfo *TII;
  75
  76     // SpillSlotsOrReMatsAvailable - This map keeps track of all of the spilled
  77     // or remat'ed virtual register values that are still available, due to
  78     // being loaded or stored to, but not invalidated yet.
  79     std::map<int, unsigned> SpillSlotsOrReMatsAvailable;
  80
  81     // PhysRegsAvailable - This is the inverse of SpillSlotsOrReMatsAvailable,
  82     // indicating which stack slot values are currently held by a physreg.  This
  83     // is used to invalidate entries in SpillSlotsOrReMatsAvailable when a
  84     // physreg is modified.
  85     std::multimap<unsigned, int> PhysRegsAvailable;
  86
  87     void disallowClobberPhysRegOnly(unsigned PhysReg);
  88
  89     void ClobberPhysRegOnly(unsigned PhysReg);
  90   public:
  91     AvailableSpills(const TargetRegisterInfo *tri, const TargetInstrInfo *tii)
  92       : TRI(tri), TII(tii) {
  93     }
  94
  95     /// clear - Reset the state.
  96     void clear() {
  97       SpillSlotsOrReMatsAvailable.clear();
  98       PhysRegsAvailable.clear();
  99     }
 100
 101     const TargetRegisterInfo *getRegInfo() const { return TRI; }
 102
 103     /// getSpillSlotOrReMatPhysReg - If the specified stack slot or remat is
 104     /// available in a  physical register, return that PhysReg, otherwise
 105     /// return 0.
 106     unsigned getSpillSlotOrReMatPhysReg(int Slot) const {
 107       std::map<int, unsigned>::const_iterator I =
 108         SpillSlotsOrReMatsAvailable.find(Slot);
 109       if (I != SpillSlotsOrReMatsAvailable.end()) {
 110         return I->second >> 1;  // Remove the CanClobber bit.
 111       }
 112       return 0;
 113     }
 114
 115     /// addAvailable - Mark that the specified stack slot / remat is available
 116     /// in the specified physreg.  If CanClobber is true, the physreg can be
 117     /// modified at any time without changing the semantics of the program.
 118     void addAvailable(int SlotOrReMat, unsigned Reg, bool CanClobber = true) {
 119       // If this stack slot is thought to be available in some other physreg,
 120       // remove its record.
 121       ModifyStackSlotOrReMat(SlotOrReMat);
 122
 123       PhysRegsAvailable.insert(std::make_pair(Reg, SlotOrReMat));
 124       SpillSlotsOrReMatsAvailable[SlotOrReMat]= (Reg << 1) |
 125                                                 (unsigned)CanClobber;
 126
 127       if (SlotOrReMat > VirtRegMap::MAX_STACK_SLOT)
 128         DOUT << "Remembering RM#" << SlotOrReMat-VirtRegMap::MAX_STACK_SLOT-1;
 129       else
 130         DOUT << "Remembering SS#" << SlotOrReMat;
 131       DOUT << " in physreg " << TRI->getName(Reg) << "\n";
 132     }
 133
 134     /// canClobberPhysReg - Return true if the spiller is allowed to change the
 135     /// value of the specified stackslot register if it desires.  The specified
 136     /// stack slot must be available in a physreg for this query to make sense.
 137     bool canClobberPhysReg(int SlotOrReMat) const {
 138       assert(SpillSlotsOrReMatsAvailable.count(SlotOrReMat) &&
 139              "Value not available!");
 140       return SpillSlotsOrReMatsAvailable.find(SlotOrReMat)->second & 1;
 141     }
 142
 143     /// disallowClobberPhysReg - Unset the CanClobber bit of the specified
 144     /// stackslot register. The register is still available but is no longer
 145     /// allowed to be modifed.
 146     void disallowClobberPhysReg(unsigned PhysReg);
 147
 148     /// ClobberPhysReg - This is called when the specified physreg changes
 149     /// value.  We use this to invalidate any info about stuff that lives in
 150     /// it and any of its aliases.
 151     void ClobberPhysReg(unsigned PhysReg);
 152
 153     /// ModifyStackSlotOrReMat - This method is called when the value in a stack
 154     /// slot changes.  This removes information about which register the
 155     /// previous value for this slot lives in (as the previous value is dead
 156     /// now).
 157     void ModifyStackSlotOrReMat(int SlotOrReMat);
 158
 159     /// AddAvailableRegsToLiveIn - Availability information is being kept coming
 160     /// into the specified MBB. Add available physical registers as potential
 161     /// live-in's. If they are reused in the MBB, they will be added to the
 162     /// live-in set to make register scavenger and post-allocation scheduler.
 163     void AddAvailableRegsToLiveIn(MachineBasicBlock &MBB, BitVector &RegKills,
 164                                   std::vector<MachineOperand*> &KillOps);
 165   };
 166
 167   // ************************************************************************ //
 168
 169   // ReusedOp - For each reused operand, we keep track of a bit of information,
 170   // in case we need to rollback upon processing a new operand.  See comments
 171   // below.
 172   struct ReusedOp {
 173     // The MachineInstr operand that reused an available value.
 174     unsigned Operand;
 175
 176     // StackSlotOrReMat - The spill slot or remat id of the value being reused.
 177     unsigned StackSlotOrReMat;
 178
 179     // PhysRegReused - The physical register the value was available in.
 180     unsigned PhysRegReused;
 181
 182     // AssignedPhysReg - The physreg that was assigned for use by the reload.
 183     unsigned AssignedPhysReg;
 184
 185     // VirtReg - The virtual register itself.
 186     unsigned VirtReg;
 187
 188     ReusedOp(unsigned o, unsigned ss, unsigned prr, unsigned apr,
 189              unsigned vreg)
 190       : Operand(o), StackSlotOrReMat(ss), PhysRegReused(prr),
 191         AssignedPhysReg(apr), VirtReg(vreg) {}
 192   };
 193
 194   /// ReuseInfo - This maintains a collection of ReuseOp's for each operand that
 195   /// is reused instead of reloaded.
 196   class VISIBILITY_HIDDEN ReuseInfo {
 197     MachineInstr &MI;
 198     std::vector<ReusedOp> Reuses;
 199     BitVector PhysRegsClobbered;
 200   public:
 201     ReuseInfo(MachineInstr &mi, const TargetRegisterInfo *tri) : MI(mi) {
 202       PhysRegsClobbered.resize(tri->getNumRegs());
 203     }
 204
 205     bool hasReuses() const {
 206       return !Reuses.empty();
 207     }
 208
 209     /// addReuse - If we choose to reuse a virtual register that is already
 210     /// available instead of reloading it, remember that we did so.
 211     void addReuse(unsigned OpNo, unsigned StackSlotOrReMat,
 212                   unsigned PhysRegReused, unsigned AssignedPhysReg,
 213                   unsigned VirtReg) {
 214       // If the reload is to the assigned register anyway, no undo will be
 215       // required.
 216       if (PhysRegReused == AssignedPhysReg) return;
 217
 218       // Otherwise, remember this.
 219       Reuses.push_back(ReusedOp(OpNo, StackSlotOrReMat, PhysRegReused,
 220                                 AssignedPhysReg, VirtReg));
 221     }
 222
 223     void markClobbered(unsigned PhysReg) {
 224       PhysRegsClobbered.set(PhysReg);
 225     }
 226
 227     bool isClobbered(unsigned PhysReg) const {
 228       return PhysRegsClobbered.test(PhysReg);
 229     }
 230
 231     /// GetRegForReload - We are about to emit a reload into PhysReg.  If there
 232     /// is some other operand that is using the specified register, either pick
 233     /// a new register to use, or evict the previous reload and use this reg.
 234     unsigned GetRegForReload(unsigned PhysReg, MachineInstr *MI,
 235                              AvailableSpills &Spills,
 236                              std::vector<MachineInstr*> &MaybeDeadStores,
 237                              SmallSet<unsigned, 8> &Rejected,
 238                              BitVector &RegKills,
 239                              std::vector<MachineOperand*> &KillOps,
 240                              VirtRegMap &VRM);
 241
 242     /// GetRegForReload - Helper for the above GetRegForReload(). Add a
 243     /// 'Rejected' set to remember which registers have been considered and
 244     /// rejected for the reload. This avoids infinite looping in case like
 245     /// this:
 246     /// t1 := op t2, t3
 247     /// t2 <- assigned r0 for use by the reload but ended up reuse r1
 248     /// t3 <- assigned r1 for use by the reload but ended up reuse r0
 249     /// t1 <- desires r1
 250     ///       sees r1 is taken by t2, tries t2's reload register r0
 251     ///       sees r0 is taken by t3, tries t3's reload register r1
 252     ///       sees r1 is taken by t2, tries t2's reload register r0 ...
 253     unsigned GetRegForReload(unsigned PhysReg, MachineInstr *MI,
 254                              AvailableSpills &Spills,
 255                              std::vector<MachineInstr*> &MaybeDeadStores,
 256                              BitVector &RegKills,
 257                              std::vector<MachineOperand*> &KillOps,
 258                              VirtRegMap &VRM) {
 259       SmallSet<unsigned, 8> Rejected;
 260       return GetRegForReload(PhysReg, MI, Spills, MaybeDeadStores, Rejected,
 261                              RegKills, KillOps, VRM);
 262     }
 263   };
 264
 265   // ************************************************************************ //
 266
 267   /// LocalSpiller - This spiller does a simple pass over the machine basic
 268   /// block to attempt to keep spills in registers as much as possible for
 269   /// blocks that have low register pressure (the vreg may be spilled due to
 270   /// register pressure in other blocks).
 271   class VISIBILITY_HIDDEN LocalSpiller : public Spiller {
 272     MachineRegisterInfo *RegInfo;
 273     const TargetRegisterInfo *TRI;
 274     const TargetInstrInfo *TII;
 275     DenseMap<MachineInstr*, unsigned> DistanceMap;
 276   public:
 277     bool runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM);
 278   private:
 279     void TransferDeadness(MachineBasicBlock *MBB, unsigned CurDist,
 280                           unsigned Reg, BitVector &RegKills,
 281                           std::vector<MachineOperand*> &KillOps);
 282     bool PrepForUnfoldOpti(MachineBasicBlock &MBB,
 283                            MachineBasicBlock::iterator &MII,
 284                            std::vector<MachineInstr*> &MaybeDeadStores,
 285                            AvailableSpills &Spills, BitVector &RegKills,
 286                            std::vector<MachineOperand*> &KillOps,
 287                            VirtRegMap &VRM);
 288     bool CommuteToFoldReload(MachineBasicBlock &MBB,
 289                              MachineBasicBlock::iterator &MII,
 290                              unsigned VirtReg, unsigned SrcReg, int SS,
 291                              AvailableSpills &Spills,
 292                              BitVector &RegKills,
 293                              std::vector<MachineOperand*> &KillOps,
 294                              const TargetRegisterInfo *TRI,
 295                              VirtRegMap &VRM);
 296     void SpillRegToStackSlot(MachineBasicBlock &MBB,
 297                              MachineBasicBlock::iterator &MII,
 298                              int Idx, unsigned PhysReg, int StackSlot,
 299                              const TargetRegisterClass *RC,
 300                              bool isAvailable, MachineInstr *&LastStore,
 301                              AvailableSpills &Spills,
 302                              SmallSet<MachineInstr*, 4> &ReMatDefs,
 303                              BitVector &RegKills,
 304                              std::vector<MachineOperand*> &KillOps,
 305                              VirtRegMap &VRM);
 306     void RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM,
 307                     AvailableSpills &Spills,
 308                     BitVector &RegKills, std::vector<MachineOperand*> &KillOps);
 309   };
 310 }
 311
 312 #endif