hphp/runtime/vm/translator/hopt/linearscan.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010- Facebook, Inc. (http://www.facebook.com)         |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #ifndef incl_HPHP_VM_LINEAR_SCAN_H_
  18 #define incl_HPHP_VM_LINEAR_SCAN_H_
  19
  20 #include "hphp/runtime/vm/translator/hopt/state_vector.h"
  21 #include "hphp/runtime/vm/translator/physreg.h"
  22 #include "hphp/runtime/vm/translator/abi-x64.h"
  23
  24 namespace HPHP {  namespace JIT {
  25
  26 class Trace;
  27 class IRFactory;
  28
  29 // This value must be consistent with the number of pre-allocated
  30 // bytes for spill locations in __enterTCHelper in translator-x64.cpp.
  31 // Be careful when changing this value.
  32 const int NumPreAllocatedSpillLocs = 64;
  33
  34 struct UseInfo {
  35   UseInfo() : lastUse(0), count(0) {}
  36   uint32_t lastUse; // linear id of last use
  37   uint32_t count;   // number of uses
  38 };
  39
  40 typedef StateVector<IRInstruction, uint32_t> LinearIdVector;
  41 typedef StateVector<SSATmp, UseInfo> UsesVector;
  42
  43 struct LifetimeInfo {
  44   explicit LifetimeInfo(const IRFactory* factory)
  45     : linear(factory, 0), uses(factory, UseInfo()) {
  46   }
  47   explicit LifetimeInfo(const LinearIdVector& linear,
  48                         const UsesVector& uses)
  49     : linear(linear), uses(uses) {
  50   }
  51   explicit LifetimeInfo(LinearIdVector&& linear,
  52                         UsesVector&& uses)
  53     : linear(linear), uses(uses) {
  54   }
  55
  56   LinearIdVector linear; // linear id of each instruction
  57   UsesVector uses;       // last use id and use count of each tmp
  58 };
  59
  60 // Information about one spilled value.
  61 struct SpillInfo {
  62   explicit SpillInfo(uint32_t v) : m_val(v) {
  63     assert(isValid());
  64   }
  65
  66   // Return logical slot number
  67   uint32_t slot() const {
  68     assert(isValid());
  69     return m_val;
  70   }
  71
  72   bool isValid() const {
  73     return int(m_val) != int(Transl::InvalidReg);
  74   }
  75
  76   // return the offset from RSP for this slot; takes into account
  77   // the native stack layout.
  78   int offset() const;
  79
  80 private:
  81   uint32_t m_val;
  82 };
  83
  84 // Register allocation info about one SSATmp
  85 class RegisterInfo {
  86   enum { kMaxNumRegs = 2 };
  87
  88 public:
  89   RegisterInfo()
  90       : m_isSpilled(false)
  91       , m_fullXMM(false) {
  92     m_regs[0] = m_regs[1] = Transl::InvalidReg;
  93   }
  94
  95   /*
  96    * Returns whether or not a given register index is allocated to a
  97    * register, or returns false if it is spilled.
  98    *
  99    * Right now, we only spill both at the same time and only Spill and
 100    * Reload instructions need to deal with SSATmps that are spilled.
 101    */
 102   bool hasReg(uint32_t i = 0) const {
 103     return !m_isSpilled && m_regs[i] != Transl::InvalidReg;
 104   }
 105
 106   /*
 107    * The number of regs actually allocated to this SSATmp.  This might
 108    * end up fewer than numNeededRegs if the SSATmp isn't really
 109    * being used.
 110    */
 111   int numAllocatedRegs() const;
 112
 113   /*
 114    * Access to allocated registers.
 115    *
 116    * Returns InvalidReg for slots that aren't allocated.
 117    */
 118   PhysReg getReg() const {
 119     assert(!m_isSpilled);
 120     return m_regs[0];
 121   }
 122
 123   PhysReg getReg(uint32_t i) const {
 124     assert(!m_isSpilled);
 125     return m_regs[i];
 126   }
 127
 128   void setReg(PhysReg reg, uint32_t i) {
 129     assert(!m_isSpilled);
 130     m_regs[i] = reg;
 131   }
 132
 133   /*
 134    * Used when the SSATmp needs two 64-bit registers and got assigned
 135    * one 128-bit XMM register.
 136    */
 137   void setRegFullXMM(PhysReg reg) {
 138     assert(reg.isXMM());
 139     assert(!m_isSpilled);
 140     m_regs[0] = reg;
 141     m_fullXMM = true;
 142   }
 143
 144   bool spilled() const {
 145     return m_isSpilled;
 146   }
 147
 148   /*
 149    * Returns whether the SSATmp needed 2 regs and was allocated to a
 150    * whole 128-bit XMM register.
 151    */
 152   bool isFullXMM() const {
 153     return m_fullXMM;
 154   }
 155
 156   /* Returns the set of registers in this RegisterInfo */
 157   RegSet getRegs() const;
 158
 159   /*
 160    * Returns information about how to spill/fill a SSATmp.
 161    *
 162    * These functions are only valid if this SSATmp is being spilled or
 163    * filled.  In all normal instructions (i.e. other than Spill and
 164    * Reload), SSATmps are assigned registers instead of spill
 165    * locations.
 166    */
 167   void setSpillInfo(int i, SpillInfo si) {
 168     assert(si.isValid());
 169     m_spillInfo[i] = si;
 170     m_isSpilled = true;
 171   }
 172
 173   SpillInfo getSpillInfo(int idx) const {
 174     assert(m_isSpilled);
 175     return m_spillInfo[idx];
 176   }
 177
 178 private:
 179   bool m_isSpilled;
 180   bool m_fullXMM;
 181   union {
 182     PhysReg m_regs[kMaxNumRegs];
 183     SpillInfo m_spillInfo[kMaxNumRegs];
 184   };
 185 };
 186
 187 struct RegAllocInfo {
 188   explicit RegAllocInfo(const IRFactory* factory)
 189     : m_regs(factory, RegisterInfo()) {}
 190   RegAllocInfo(const RegAllocInfo& other) : m_regs(other.m_regs) {}
 191   RegAllocInfo(RegAllocInfo&& other) : m_regs(other.m_regs) {}
 192   RegisterInfo& operator[](const SSATmp* k) { return m_regs[k]; }
 193   RegisterInfo& operator[](const SSATmp& k) { return m_regs[k]; }
 194   const RegisterInfo& operator[](const SSATmp* k) const { return m_regs[k]; }
 195   const RegisterInfo& operator[](const SSATmp& k) const { return m_regs[k]; }
 196 private:
 197   StateVector<SSATmp, RegisterInfo> m_regs;
 198 };
 199
 200 inline std::ostream& operator<<(std::ostream& os, SpillInfo si) {
 201   os << "spill[" << si.slot() << "]";
 202   return os;
 203 }
 204
 205 /*
 206  * The main entry point for register allocation.  Called prior to code
 207  * generation.
 208  */
 209 RegAllocInfo allocRegsForTrace(Trace*, IRFactory*, LifetimeInfo* = nullptr);
 210
 211 // Native stack layout:
 212 // |               |
 213 // +---------------+
 214 // |               |  <-- spill[5..]
 215 // | pre allocated |  <-- spill[4]
 216 // |  (16 slots)   |  <-- spill[3]
 217 // +---------------+
 218 // |  return addr  |
 219 // +---------------+
 220 //
 221 // We need to increase spill indexes by 1 to avoid overwriting the
 222 // return address.
 223
 224 /*
 225  * compute the offset from RSP for a logical spill slot.  Given a logical
 226  * slot number, return a byte offset from RSP, taking into account the layout
 227  * above.  LinearScan punts if any extra spill locations would be required,
 228  * so all we really need to do is adjust for the return address and scale
 229  * by the machine word size.
 230  */
 231 inline int SpillInfo::offset() const {
 232   return (m_val + 1) * sizeof(uint64_t);
 233 }
 234
 235 }}
 236
 237 #endif