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     /// canClobberPhysReg - Return true if the spiller is allowed to change the
 131     /// value of the specified stackslot register if it desires.  The specified
 132     /// stack slot must be available in a physreg for this query to make sense.
 133     bool canClobberPhysReg(int SlotOrReMat) const {
 134       assert(SpillSlotsOrReMatsAvailable.count(SlotOrReMat) &&
 135              "Value not available!");
 136       return SpillSlotsOrReMatsAvailable.find(SlotOrReMat)->second & 1;
 137     }
 138
 139     /// disallowClobberPhysReg - Unset the CanClobber bit of the specified
 140     /// stackslot register. The register is still available but is no longer
 141     /// allowed to be modifed.
 142     void disallowClobberPhysReg(unsigned PhysReg);
 143
 144     /// ClobberPhysReg - This is called when the specified physreg changes
 145     /// value.  We use this to invalidate any info about stuff that lives in
 146     /// it and any of its aliases.
 147     void ClobberPhysReg(unsigned PhysReg);
 148
 149     /// ModifyStackSlotOrReMat - This method is called when the value in a stack
 150     /// slot changes.  This removes information about which register the
 151     /// previous value for this slot lives in (as the previous value is dead
 152     /// now).
 153     void ModifyStackSlotOrReMat(int SlotOrReMat);
 154
 155     /// AddAvailableRegsToLiveIn - Availability information is being kept coming
 156     /// into the specified MBB. Add available physical registers as potential
 157     /// live-in's. If they are reused in the MBB, they will be added to the
 158     /// live-in set to make register scavenger and post-allocation scheduler.
 159     void AddAvailableRegsToLiveIn(MachineBasicBlock &MBB, BitVector &RegKills,
 160                                   std::vector<MachineOperand*> &KillOps);
 161   };
 162
 163   // ************************************************************************ //
 164
 165   // ReusedOp - For each reused operand, we keep track of a bit of information,
 166   // in case we need to rollback upon processing a new operand.  See comments
 167   // below.
 168   struct ReusedOp {
 169     // The MachineInstr operand that reused an available value.
 170     unsigned Operand;
 171
 172     // StackSlotOrReMat - The spill slot or remat id of the value being reused.
 173     unsigned StackSlotOrReMat;
 174
 175     // PhysRegReused - The physical register the value was available in.
 176     unsigned PhysRegReused;
 177
 178     // AssignedPhysReg - The physreg that was assigned for use by the reload.
 179     unsigned AssignedPhysReg;
 180
 181     // VirtReg - The virtual register itself.
 182     unsigned VirtReg;
 183
 184     ReusedOp(unsigned o, unsigned ss, unsigned prr, unsigned apr,
 185              unsigned vreg)
 186       : Operand(o), StackSlotOrReMat(ss), PhysRegReused(prr),
 187         AssignedPhysReg(apr), VirtReg(vreg) {}
 188   };
 189
 190   /// ReuseInfo - This maintains a collection of ReuseOp's for each operand that
 191   /// is reused instead of reloaded.
 192   class VISIBILITY_HIDDEN ReuseInfo {
 193     MachineInstr &MI;
 194     std::vector<ReusedOp> Reuses;
 195     BitVector PhysRegsClobbered;
 196   public:
 197     ReuseInfo(MachineInstr &mi, const TargetRegisterInfo *tri) : MI(mi) {
 198       PhysRegsClobbered.resize(tri->getNumRegs());
 199     }
 200
 201     bool hasReuses() const {
 202       return !Reuses.empty();
 203     }
 204
 205     /// addReuse - If we choose to reuse a virtual register that is already
 206     /// available instead of reloading it, remember that we did so.
 207     void addReuse(unsigned OpNo, unsigned StackSlotOrReMat,
 208                   unsigned PhysRegReused, unsigned AssignedPhysReg,
 209                   unsigned VirtReg) {
 210       // If the reload is to the assigned register anyway, no undo will be
 211       // required.
 212       if (PhysRegReused == AssignedPhysReg) return;
 213
 214       // Otherwise, remember this.
 215       Reuses.push_back(ReusedOp(OpNo, StackSlotOrReMat, PhysRegReused,
 216                                 AssignedPhysReg, VirtReg));
 217     }
 218
 219     void markClobbered(unsigned PhysReg) {
 220       PhysRegsClobbered.set(PhysReg);
 221     }
 222
 223     bool isClobbered(unsigned PhysReg) const {
 224       return PhysRegsClobbered.test(PhysReg);
 225     }
 226
 227     /// GetRegForReload - We are about to emit a reload into PhysReg.  If there
 228     /// is some other operand that is using the specified register, either pick
 229     /// a new register to use, or evict the previous reload and use this reg.
 230     unsigned GetRegForReload(unsigned PhysReg, MachineInstr *MI,
 231                              AvailableSpills &Spills,
 232                              std::vector<MachineInstr*> &MaybeDeadStores,
 233                              SmallSet<unsigned, 8> &Rejected,
 234                              BitVector &RegKills,
 235                              std::vector<MachineOperand*> &KillOps,
 236                              VirtRegMap &VRM);
 237
 238     /// GetRegForReload - Helper for the above GetRegForReload(). Add a
 239     /// 'Rejected' set to remember which registers have been considered and
 240     /// rejected for the reload. This avoids infinite looping in case like
 241     /// this:
 242     /// t1 := op t2, t3
 243     /// t2 <- assigned r0 for use by the reload but ended up reuse r1
 244     /// t3 <- assigned r1 for use by the reload but ended up reuse r0
 245     /// t1 <- desires r1
 246     ///       sees r1 is taken by t2, tries t2's reload register r0
 247     ///       sees r0 is taken by t3, tries t3's reload register r1
 248     ///       sees r1 is taken by t2, tries t2's reload register r0 ...
 249     unsigned GetRegForReload(unsigned PhysReg, MachineInstr *MI,
 250                              AvailableSpills &Spills,
 251                              std::vector<MachineInstr*> &MaybeDeadStores,
 252                              BitVector &RegKills,
 253                              std::vector<MachineOperand*> &KillOps,
 254                              VirtRegMap &VRM) {
 255       SmallSet<unsigned, 8> Rejected;
 256       return GetRegForReload(PhysReg, MI, Spills, MaybeDeadStores, Rejected,
 257                              RegKills, KillOps, VRM);
 258     }
 259   };
 260
 261   // ************************************************************************ //
 262
 263   /// LocalSpiller - This spiller does a simple pass over the machine basic
 264   /// block to attempt to keep spills in registers as much as possible for
 265   /// blocks that have low register pressure (the vreg may be spilled due to
 266   /// register pressure in other blocks).
 267   class VISIBILITY_HIDDEN LocalSpiller : public Spiller {
 268     MachineRegisterInfo *RegInfo;
 269     const TargetRegisterInfo *TRI;
 270     const TargetInstrInfo *TII;
 271     DenseMap<MachineInstr*, unsigned> DistanceMap;
 272   public:
 273     bool runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM);
 274   private:
 275     void TransferDeadness(MachineBasicBlock *MBB, unsigned CurDist,
 276                           unsigned Reg, BitVector &RegKills,
 277                           std::vector<MachineOperand*> &KillOps);
 278     bool PrepForUnfoldOpti(MachineBasicBlock &MBB,
 279                            MachineBasicBlock::iterator &MII,
 280                            std::vector<MachineInstr*> &MaybeDeadStores,
 281                            AvailableSpills &Spills, BitVector &RegKills,
 282                            std::vector<MachineOperand*> &KillOps,
 283                            VirtRegMap &VRM);
 284     bool CommuteToFoldReload(MachineBasicBlock &MBB,
 285                              MachineBasicBlock::iterator &MII,
 286                              unsigned VirtReg, unsigned SrcReg, int SS,
 287                              AvailableSpills &Spills,
 288                              BitVector &RegKills,
 289                              std::vector<MachineOperand*> &KillOps,
 290                              const TargetRegisterInfo *TRI,
 291                              VirtRegMap &VRM);
 292     void SpillRegToStackSlot(MachineBasicBlock &MBB,
 293                              MachineBasicBlock::iterator &MII,
 294                              int Idx, unsigned PhysReg, int StackSlot,
 295                              const TargetRegisterClass *RC,
 296                              bool isAvailable, MachineInstr *&LastStore,
 297                              AvailableSpills &Spills,
 298                              SmallSet<MachineInstr*, 4> &ReMatDefs,
 299                              BitVector &RegKills,
 300                              std::vector<MachineOperand*> &KillOps,
 301                              VirtRegMap &VRM);
 302     void RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM,
 303                     AvailableSpills &Spills,
 304                     BitVector &RegKills, std::vector<MachineOperand*> &KillOps);
 305   };
 306 }
 307
 308 #endif