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