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