hphp/runtime/vm/jit/frame-state.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-2016 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_JIT_FRAME_STATE_H_
  18 #define incl_HPHP_JIT_FRAME_STATE_H_
  19
  20 #include "hphp/runtime/vm/jit/cfg.h"
  21 #include "hphp/runtime/vm/jit/state-vector.h"
  22 #include "hphp/runtime/vm/jit/type-source.h"
  23
  24 #include <boost/dynamic_bitset.hpp>
  25 #include <folly/Optional.h>
  26
  27 #include <memory>
  28 #include <vector>
  29
  30 namespace HPHP {
  31
  32 struct Func;
  33
  34 namespace jit {
  35
  36 struct BlocksWithIds;
  37 struct IRInstruction;
  38 struct SSATmp;
  39
  40 //////////////////////////////////////////////////////////////////////
  41
  42 struct FPIInfo {
  43   SSATmp* returnSP;
  44   FPInvOffset returnSPOff; // return's logical sp offset; stkptr might differ
  45   SSATmp* ctx;
  46   Op fpushOpc; // bytecode for FPush*
  47   const Func* func;
  48   bool interp;
  49   bool spansCall;
  50 };
  51
  52 //////////////////////////////////////////////////////////////////////
  53
  54 /*
  55  * SlotState stores information about either a local variable or a stack slot
  56  * in the current function, for FrameState.  LocalState and StackState are the
  57  * concrete versions of this struct, which differ only by the default type they
  58  * use.
  59  */
  60 template<bool Stack>
  61 struct SlotState {
  62   static constexpr Type default_type() {
  63     return Stack ? TStkElem : TGen;
  64   }
  65
  66   /*
  67    * The current value of the or stack slot.
  68    */
  69   SSATmp* value{nullptr};
  70
  71   /*
  72    * The current type of the local or stack slot.  We may have a
  73    * tracked type even if we don't have an available value.  This
  74    * happens across PHP-level calls, for example, or at some joint
  75    * points where we couldn't find the same available value for all
  76    * incoming edges.  However, whenever we have a value, the type of
  77    * the SSATmp must match this `type' field.
  78    */
  79   Type type{default_type()};
  80
  81   /*
  82    * Prediction for the type of a local or stack slot, if it's boxed or if
  83    * we're in a pseudomain.  Otherwise it will be the same as `type'.
  84    *
  85    * Invariants:
  86    *   always a subtype of `type'
  87    */
  88   Type predictedType{default_type()};
  89
  90   /*
  91    * The sources of the currently known type. They may be values. If the value
  92    * is unavailable, we won't hold onto it in the value field, but we'll keep
  93    * it around in typeSrcs for guard relaxation.
  94    */
  95   TypeSourceSet typeSrcs{};
  96
  97   /*
  98    * Whether or not the local or stack element may have changed since
  99    * the entry of the unit.  This is only used for post-conditions.
 100    */
 101   bool maybeChanged{false};
 102 };
 103
 104 using LocalState = SlotState<false>;
 105 using StackState = SlotState<true>;
 106
 107 //////////////////////////////////////////////////////////////////////
 108
 109 /*
 110  * State related to a particular frame.  These state structures are stored in a
 111  * stack, that we push and pop as we enter and leave inlined frames.
 112  */
 113 struct FrameState {
 114   /*
 115    * Current Func, VM stack pointer, VM frame pointer, offset between sp and
 116    * fp, and bytecode position.
 117    */
 118   const Func* curFunc;
 119   SSATmp* fpValue{nullptr};
 120
 121   /*
 122    * Tracking of in-memory state of the evaluation stack.
 123    */
 124   SSATmp* spValue{nullptr};
 125   FPInvOffset spOffset;   // delta from vmfp to spvalue
 126
 127   /*
 128    * Here we keep track of the raw pointer value of the member base register,
 129    * the type of the pointer, as well as the value it points to, which we often
 130    * know after simple base operations like BaseH or BaseL. These are used for
 131    * some gen-time load elimination to preserve important information about the
 132    * base.
 133    */
 134   struct {
 135     SSATmp* ptr{nullptr};
 136     Type ptrType{TPtrToGen};
 137     SSATmp* value{nullptr};
 138
 139     void reset() {
 140       ptr = nullptr;
 141       ptrType = TPtrToGen;
 142       value = nullptr;
 143     }
 144   } mbase;
 145
 146   /*
 147    * Tracks whether we will need to ratchet tvRef and tvRef2 after emitting an
 148    * intermediate member instruction.
 149    */
 150   bool needRatchet{false};
 151
 152   /*
 153    * m_thisAvailable tracks whether the current frame is known to have a
 154    * non-null $this pointer.
 155    */
 156   bool thisAvailable{false};
 157
 158   /*
 159    * frameMaySpan is true iff a Call instruction has been seen on any path
 160    * since the definition of the current frame pointer.
 161    */
 162   bool frameMaySpanCall{false};
 163
 164   /*
 165    * syncedSpLevel indicates the depth of the in-memory eval stack.
 166    */
 167   FPInvOffset syncedSpLevel{0};
 168
 169   /*
 170    * stackModified is reset to false by exceptionStackBoundary() and set to
 171    * true by anything that modifies the eval stack. It's used to verify that
 172    * the stack is not modified between the beginning of a bytecode's
 173    * translation and creation of any catch traces, unless
 174    * exceptionStackBoundary() is explicitly called.
 175    */
 176   bool stackModified{false};
 177
 178   /*
 179    * The FPI stack is used for inlining---when we start inlining at an FCall,
 180    * we look in here to find a definition of the StkPtr,offset that can be used
 181    * after the inlined callee "returns".
 182    */
 183   jit::deque<FPIInfo> fpiStack;
 184
 185   /*
 186    * The values in the eval stack in memory, either above or below the current
 187    * spValue pointer.  These are indexed relative to the base of the eval stack
 188    * for the whole function.
 189    */
 190   jit::vector<StackState> stack;
 191
 192   /*
 193    * Vector of local variable inforation; sized for numLocals on the curFunc
 194    * (if the state is initialized).
 195    */
 196   jit::vector<LocalState> locals;
 197
 198   /*
 199    * Predicted types for values that lived in a local or stack slot at one
 200    * point. Used to preserve predictions for values that move between different
 201    * slots.
 202    */
 203   jit::hash_map<SSATmp*, Type> predictedTypes;
 204 };
 205
 206 //////////////////////////////////////////////////////////////////////
 207
 208 /*
 209  * FrameStateMgr tracks state about the VM stack frame in the function currently
 210  * being translated. It is responsible for both storing the state and updating
 211  * it appropriately as instructions and blocks are processed.
 212  *
 213  * The types of state tracked by FrameStateMgr include:
 214  *
 215  *   - value availability for values stored in locals, or the $this pointer
 216  *
 217  *      Used for value propagation.
 218  *
 219  *   - local types and values
 220  *
 221  *      We track the current view of these types as we link in new instructions
 222  *      that mutate them.
 223  *
 224  *   - current frame and stack pointers
 225  *
 226  *   - current function and bytecode offset
 227  */
 228 struct FrameStateMgr final {
 229   explicit FrameStateMgr(BCMarker);
 230
 231   FrameStateMgr(const FrameStateMgr&) = delete;
 232   FrameStateMgr(FrameStateMgr&&) = default;
 233   FrameStateMgr& operator=(const FrameStateMgr&) = delete;
 234   FrameStateMgr& operator=(FrameStateMgr&&) = default;
 235
 236   /*
 237    * Update state by computing the effects of an instruction.
 238    */
 239   void update(const IRInstruction*);
 240
 241   /////////////////////////////////////////////////////////////////////////////
 242   // Per-block state.
 243
 244   /*
 245    * Whether we have state saved for the given block.
 246    */
 247   bool hasStateFor(Block*) const;
 248
 249   /*
 250    * Starts tracking state for a block and reloads any previously saved state.
 251    *
 252    * `hasUnprocessedPred' is set to indicate that the given block has a
 253    * predecessor in the region that might not yet be linked into the IR CFG.
 254    */
 255   void startBlock(Block* b, bool hasUnprocessedPred);
 256
 257   /*
 258    * Finish tracking state for a block and save the current state to any
 259    * successors.
 260    *
 261    * Returns true iff the out-state for the block has changed.
 262    */
 263   bool finishBlock(Block*);
 264
 265   /*
 266    * Save current state of a block so we can resume processing it after working
 267    * on another.
 268    *
 269    * Leaves the current state for this FrameStateMgr untouched: if you
 270    * startBlock something new it'll keep using it.  Right now we rely on this
 271    * for exit and catch traces (relevant: TODO(#4323657)).
 272    */
 273   void pauseBlock(Block*);
 274
 275   /*
 276    * Resumes processing a block that was stopped by pauseBlock.
 277    */
 278   void unpauseBlock(Block*);
 279
 280   /*
 281    * Returns the post-conditions associated with `exitBlock'
 282    */
 283   const PostConditions& postConds(Block* exitBlock) const;
 284
 285   /*
 286    * set an override for the next fpi regions fpushOp
 287    */
 288   void setFPushOverride(Op op)          { m_fpushOverride = op; }
 289   bool hasFPushOverride() const         { return m_fpushOverride.hasValue(); }
 290   /////////////////////////////////////////////////////////////////////////////
 291
 292   /*
 293    * FrameState accessors.
 294    *
 295    * In the presence of inlining, these return state for the most-inlined
 296    * frame.
 297    */
 298   const Func* func()              const { return cur().curFunc; }
 299   SSATmp*     fp()                const { return cur().fpValue; }
 300   SSATmp*     sp()                const { return cur().spValue; }
 301   FPInvOffset spOffset()          const { return cur().spOffset; }
 302   SSATmp*     memberBasePtr()     const { return cur().mbase.ptr; }
 303   Type        memberBasePtrType() const { return cur().mbase.ptrType; }
 304   SSATmp*     memberBaseValue()   const { return cur().mbase.value; }
 305   bool        needRatchet()       const { return cur().needRatchet; }
 306   bool        thisAvailable()     const { return cur().thisAvailable; }
 307   bool        frameMaySpanCall()  const { return cur().frameMaySpanCall; }
 308   FPInvOffset syncedSpLevel()     const { return cur().syncedSpLevel; }
 309   bool        stackModified()     const { return cur().stackModified; }
 310   const jit::deque<FPIInfo>& fpiStack() const { return cur().fpiStack; }
 311
 312   /*
 313    * FrameState modifiers.
 314    *
 315    * In the presence of inlining, these modify state for the most-inlined
 316    * frame.
 317    */
 318   void setMemberBaseValue(SSATmp* base) { cur().mbase.value = base; }
 319   void setNeedRatchet(bool b)           { cur().needRatchet = b; }
 320   void setThisAvailable()               { cur().thisAvailable = true; }
 321   void resetStackModified()             { cur().stackModified = false; }
 322   void setSyncedSpLevel(FPInvOffset o)  { cur().syncedSpLevel = o; }
 323   void incSyncedSpLevel(int32_t n = 1)  { cur().syncedSpLevel += n; }
 324   void decSyncedSpLevel(int32_t n = 1)  { cur().syncedSpLevel -= n; }
 325   /*
 326    * Current inlining depth (not including the toplevel frame).
 327    */
 328   unsigned inlineDepth() const { return m_stack.size() - 1; }
 329
 330   /*
 331    * Return the SlotState for local `id' or stack element at `off' in the
 332    * most-inlined frame.
 333    */
 334   const LocalState& local(uint32_t id) const;
 335   const StackState& stack(IRSPOffset off) const;
 336
 337   /*
 338    * Update the `predictedType' in the SlotState for the given local variable
 339    * or stack value.
 340    */
 341   void refineLocalPredictedType(uint32_t id, Type type);
 342   void refineStackPredictedType(IRSPOffset, Type);
 343
 344 private:
 345   struct BlockState {
 346     jit::vector<FrameState> in;
 347     folly::Optional<jit::vector<FrameState>> paused;
 348   };
 349
 350 private:
 351   bool checkInvariants() const;
 352   bool save(Block*);
 353   jit::vector<LocalState>& locals(unsigned inlineIdx);
 354   void trackDefInlineFP(const IRInstruction* inst);
 355   void trackInlineReturn();
 356   void clearForUnprocessedPred();
 357   StackState& stackState(IRSPOffset offset);
 358   const StackState& stackState(IRSPOffset offset) const;
 359   void collectPostConds(Block* exitBlock);
 360   void updateMInstr(const IRInstruction*);
 361   void refinePredictedTmpType(SSATmp*, Type);
 362
 363 private:
 364   FrameState& cur() {
 365     assertx(!m_stack.empty());
 366     return m_stack.back();
 367   }
 368   const FrameState& cur() const {
 369     return const_cast<FrameStateMgr*>(this)->cur();
 370   }
 371
 372   template<bool Stack>
 373   void syncPrediction(SlotState<Stack>&);
 374
 375   /*
 376    * refine(Local|Stack)Type() are used when the value of a slot hasn't changed
 377    * but we have more information about its type, from a guard or type assert.
 378    *
 379    * set(Local|Stack)Type() are used to change the type of a slot when we have
 380    * a brand new type because the value might have changed. These operations
 381    * clear the typeSrcs of the slot, so new type may not be derived from the
 382    * old type in any way.
 383    *
 384    * widen(Local|Stack)Type() are used to change the type of a slot, as a
 385    * result of an operation that might change the value. These operations
 386    * preserve the typeSrcs of the slot, so the new type may be derived from the
 387    * old type.
 388    */
 389 private: // local tracking helpers
 390   void setLocalValue(uint32_t id, SSATmp* value);
 391   void refineLocalValues(SSATmp* oldVal, SSATmp* newVal);
 392   void dropLocalRefsInnerTypes();
 393   void killLocalsForCall(bool);
 394   void refineLocalType(uint32_t id, Type type, TypeSource typeSrc);
 395   void setLocalPredictedType(uint32_t id, Type type);
 396   void setLocalType(uint32_t id, Type type);
 397   void widenLocalType(uint32_t id, Type type);
 398   void setBoxedLocalPrediction(uint32_t id, Type type);
 399   void updateLocalRefPredictions(SSATmp*, SSATmp*);
 400   void setLocalTypeSource(uint32_t id, TypeSource typeSrc);
 401   void clearLocals();
 402
 403 private: // stack tracking helpers
 404   void setStackValue(IRSPOffset, SSATmp*);
 405   void setStackType(IRSPOffset, Type);
 406   void widenStackType(IRSPOffset, Type);
 407   void refineStackValues(SSATmp* oldval, SSATmp* newVal);
 408   void refineStackType(IRSPOffset, Type, TypeSource typeSrc);
 409   void clearStackForCall();
 410   void setBoxedStkPrediction(IRSPOffset, Type type);
 411   void spillFrameStack(IRSPOffset, FPInvOffset, const IRInstruction*);
 412
 413 private:
 414   /*
 415    * Stack of states.  We push and pop frames as we enter and leave inlined
 416    * calls.
 417    */
 418   jit::vector<FrameState> m_stack;
 419
 420   /*
 421    * Saved snapshots of the incoming and outgoing state of blocks.
 422    */
 423   jit::hash_map<Block*,BlockState> m_states;
 424
 425   /*
 426    * Post-conditions for exit blocks.
 427    */
 428   jit::hash_map<Block*,PostConditions> m_exitPostConds;
 429
 430   /*
 431    * Override for the current fpush* bytecode so we can convert bytecodes
 432    * to php calls.
 433    */
 434   folly::Optional<Op> m_fpushOverride;
 435 };
 436
 437 //////////////////////////////////////////////////////////////////////
 438
 439 /*
 440  * Debug stringification.
 441  */
 442 std::string show(const FrameStateMgr&);
 443
 444 //////////////////////////////////////////////////////////////////////
 445
 446 }}
 447
 448 #endif