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

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-2014 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_RUNTIME_VM_JIT_FRAME_STATE_H_
  18 #define incl_HPHP_RUNTIME_VM_JIT_FRAME_STATE_H_
  19
  20 #include <boost/dynamic_bitset.hpp>
  21 #include <memory>
  22 #include <vector>
  23
  24 #include <folly/Optional.h>
  25
  26 #include "hphp/runtime/vm/jit/state-vector.h"
  27 #include "hphp/runtime/vm/jit/type-source.h"
  28 #include "hphp/runtime/vm/jit/local-effects.h"
  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 EvalStack {
  43   explicit EvalStack() {}
  44
  45   void push(SSATmp* tmp) {
  46     m_vector.push_back(tmp);
  47   }
  48
  49   SSATmp* pop() {
  50     if (m_vector.size() == 0) {
  51       return nullptr;
  52     }
  53     SSATmp* tmp = m_vector.back();
  54     m_vector.pop_back();
  55     return tmp;
  56   }
  57
  58   SSATmp* top(uint32_t offset = 0) const {
  59     if (offset >= m_vector.size()) {
  60       return nullptr;
  61     }
  62     uint32_t index = m_vector.size() - 1 - offset;
  63     return m_vector[index];
  64   }
  65
  66   void replace(uint32_t offset, SSATmp* tmp) {
  67     assert(offset < m_vector.size());
  68     uint32_t index = m_vector.size() - 1 - offset;
  69     m_vector[index] = tmp;
  70   }
  71
  72   bool empty() const { return m_vector.empty(); }
  73   int  size()  const { return m_vector.size(); }
  74   void clear()       { m_vector.clear(); }
  75
  76   void swap(jit::vector<SSATmp*>& vector) {
  77     m_vector.swap(vector);
  78   }
  79
  80 private:
  81   jit::vector<SSATmp*> m_vector;
  82 };
  83
  84 //////////////////////////////////////////////////////////////////////
  85
  86 /*
  87  * SlotState stores information about either a local variable or a stack slot
  88  * in the current function, for FrameState.  LocalState and StackState are the
  89  * concrete versions of this struct, which differ only by the default type they
  90  * use.
  91  */
  92 template<bool Stack>
  93 struct SlotState {
  94   /*
  95    * The current value of the or stack slot.
  96    */
  97   SSATmp* value{nullptr};
  98
  99   /*
 100    * The current type of the local or stack slot.  We may have a tracked type
 101    * even if we don't have an available value.  This happens across PHP-level
 102    * calls, for example, or at some joint points where we couldn't find the
 103    * same available value for all incoming edges.
 104    */
 105   Type type{Stack ? Type::StkElem : Type::Gen};
 106
 107   /*
 108    * Prediction for the type of a local or stack slot, if it's boxed or if
 109    * we're in a pseudomain.  Otherwise it will be the same as `type'.
 110    *
 111    * Invariants:
 112    *   always a subtype of `type'
 113    */
 114   Type predictedType{Stack ? Type::StkElem : Type::Gen};
 115
 116   /*
 117    * The sources of the currently known type. They may be values. If the value
 118    * is unavailable, we won't hold onto it in the value field, but we'll keep
 119    * it around in typeSrcs for guard relaxation.
 120    */
 121   TypeSourceSet typeSrcs;
 122 };
 123
 124 using LocalState = SlotState<false>;
 125 using StackState = SlotState<true>;
 126
 127 //////////////////////////////////////////////////////////////////////
 128
 129 /*
 130  * State related to a particular frame.  These state structures are stored in a
 131  * stack, that we push and pop as we enter and leave inlined frames.
 132  */
 133 struct FrameState {
 134   /*
 135    * Current Func, VM stack pointer, VM frame pointer, offset between sp and
 136    * fp, and bytecode position.
 137    */
 138   const Func* curFunc;
 139   SSATmp* fpValue{nullptr};
 140
 141   /*
 142    * m_thisAvailable tracks whether the current frame is known to have a
 143    * non-null $this pointer.
 144    */
 145   bool thisAvailable{false};
 146
 147   /*
 148    * Tracking of the not-in-memory state of the virtual execution stack:
 149    *
 150    *   During HhbcTranslator's run over the bytecode, these stacks contain
 151    *   SSATmp values representing the execution stack state since the last
 152    *   spillStack() call.
 153    *
 154    *   The EvalStack contains cells that need to be spilled in order to
 155    *   materialize the stack.
 156    *
 157    *   stackDeficit represents the number of cells we've popped off the virtual
 158    *   stack since the last sync.
 159    *
 160    *   syncedSpLevel indicates the depth that has been spilled to memory.
 161    *
 162    * TODO(#5868851): these fields just dangle meaninglessly when FrameState is
 163    * being used in LegacyReoptimize mode.
 164    */
 165   uint32_t stackDeficit{0};
 166   EvalStack evalStack;
 167   FPAbsOffset syncedSpLevel{0};
 168
 169   /*
 170    * Tracking of in-memory state of the evaluation stack.
 171    */
 172   SSATmp* spValue{nullptr};
 173   FPAbsOffset spOffset;   // delta from vmfp to spvalue
 174
 175   /*
 176    * The values in the eval stack that are already in memory, either above or
 177    * below the current spValue pointer.  These are indexed relative to the base
 178    * of the eval stack for the whole function.
 179    */
 180   jit::vector<StackState> memoryStack;
 181
 182   /*
 183    * Vector of local variable inforation; sized for numLocals on the curFunc
 184    * (if the state is initialized).
 185    */
 186   jit::vector<LocalState> locals;
 187
 188   /*
 189    * frameMaySpan is true iff a Call instruction has been seen on any path
 190    * since the definition of the current frame pointer.
 191    */
 192   bool frameMaySpanCall{false};
 193 };
 194
 195 //////////////////////////////////////////////////////////////////////
 196
 197 /*
 198  * FrameStateMgr tracks state about the VM stack frame in the function currently
 199  * being translated. It is responsible for both storing the state and updating
 200  * it appropriately as instructions and blocks are processed.
 201  *
 202  * The types of state tracked by FrameStateMgr include:
 203  *
 204  *   - value availability for values stored in locals, or the $this pointer
 205  *
 206  *      Used for value propagation.
 207  *
 208  *   - local types and values
 209  *
 210  *      We track the current view of these types as we link in new instructions
 211  *      that mutate them.
 212  *
 213  *   - current frame and stack pointers
 214  *
 215  *   - current function and bytecode offset
 216  */
 217 struct FrameStateMgr final : private LocalStateHook {
 218   explicit FrameStateMgr(BCMarker);
 219
 220   FrameStateMgr(const FrameStateMgr&) = delete;
 221   FrameStateMgr(FrameStateMgr&&) = default;
 222   FrameStateMgr& operator=(const FrameStateMgr&) = delete;
 223   FrameStateMgr& operator=(FrameStateMgr&&) = default;
 224
 225   /*
 226    * Put the FrameStateMgr in building mode.  This function must be called
 227    * after constructing a FrameStateMgr before you start updating it, unless
 228    * you're using it for fixed point mode.
 229    */
 230   void setBuilding() { m_status = Status::Building; }
 231
 232   /*
 233    * Tell the FrameStateMgr we're doing reoptimize without being aware of all
 234    * types of control flow.
 235    */
 236   void setLegacyReoptimize() { m_status = Status::LegacyReoptimize; }
 237
 238   /*
 239    * Update state by computing the effects of an instruction.
 240    *
 241    * Returns true iff the state for the instruction's taken edge is changed.
 242    */
 243   bool update(const IRInstruction*);
 244
 245   /*
 246    * Whether we have state saved for the given block.
 247    */
 248   bool hasStateFor(Block*) const;
 249
 250   /*
 251    * Starts tracking state for a block and reloads any previously saved
 252    * state. Can set local values to null if hitting a block with an
 253    * unprocessed predecessor, so we pass in an optional LocalStateHook. The
 254    * isLoopHeader parameter is used during initial IR generation to indicate
 255    * that the given block has a predecessor in the region that might not yet
 256    * be linked into the IR cfg.
 257    */
 258   void startBlock(Block* b, BCMarker marker, bool isLoopHeader = false);
 259
 260   /*
 261    * Finish tracking state for a block and save the current state to
 262    * any successors.
 263    *
 264    * Returns true iff the out-state for the block has changed.
 265    */
 266   bool finishBlock(Block*);
 267
 268   /*
 269    * Save current state of a block so we can resume processing it after working
 270    * on another.
 271    *
 272    * Leaves the current state for this FrameStateMgr untouched: if you
 273    * startBlock something new it'll keep using it.  Right now we rely on this
 274    * for exit and catch traces (relevant: TODO(#4323657)).
 275    */
 276   void pauseBlock(Block*);
 277
 278   /*
 279    * Resumes processing a block that was stopped by pauseBlock.
 280    */
 281   void unpauseBlock(Block*);
 282
 283   /*
 284    * Clear state associated with the given block.
 285    */
 286   void clearBlock(Block*);
 287
 288   /*
 289    * Iterates through a control-flow graph, until a fixed-point is
 290    * reached. Must be called before this FrameStateMgr has any state.
 291    */
 292   void computeFixedPoint(const BlocksWithIds&);
 293
 294   /*
 295    * Loads the in-state for a block. Requires that the block has already been
 296    * processed. Intended to be used after computing the fixed-point of a CFG.
 297    */
 298   void loadBlock(Block*);
 299
 300   /*
 301    * Returns the post-conditions associated with the given exit block.
 302    */
 303   const PostConditions& postConds(Block*) const;
 304
 305   const Func* func() const { return cur().curFunc; }
 306   FPAbsOffset spOffset() const { return cur().spOffset; }
 307   SSATmp* sp() const { return cur().spValue; }
 308   SSATmp* fp() const { return cur().fpValue; }
 309   bool thisAvailable() const { return cur().thisAvailable; }
 310   void setThisAvailable() { cur().thisAvailable = true; }
 311   bool frameMaySpanCall() const { return cur().frameMaySpanCall; }
 312   unsigned inlineDepth() const { return m_stack.size() - 1; }
 313   uint32_t stackDeficit() const { return cur().stackDeficit; }
 314   void incStackDeficit() { cur().stackDeficit++; }
 315   void clearStackDeficit() { cur().stackDeficit = 0; }
 316   void setStackDeficit(uint32_t d) { cur().stackDeficit = d; }
 317   EvalStack& evalStack() { return cur().evalStack; }
 318   FPAbsOffset syncedSpLevel() const { return cur().syncedSpLevel; }
 319   void syncEvalStack();
 320
 321   Type localType(uint32_t id) const;
 322   Type predictedLocalType(uint32_t id) const;
 323   SSATmp* localValue(uint32_t id) const;
 324   TypeSourceSet localTypeSources(uint32_t id) const;
 325
 326   Type stackType(IRSPOffset) const;
 327   Type predictedStackType(IRSPOffset) const;
 328   SSATmp* stackValue(IRSPOffset) const;
 329   TypeSourceSet stackTypeSources(IRSPOffset) const;
 330
 331   /*
 332    * Call a function with const access to the LocalState& for each local we're
 333    * tracking.
 334    */
 335   void walkAllInlinedLocals(
 336     const std::function<void (uint32_t, unsigned, const LocalState&)>& body,
 337     bool skipThisFrame) const;
 338
 339   /*
 340    * Call `func' with all non-null tracked local values, including callers if
 341    * this is an inlined frame.
 342    */
 343   void forEachLocalValue(const std::function<void (SSATmp*)>& func) const;
 344
 345 private:
 346   struct BlockState {
 347     jit::vector<FrameState> in;
 348     folly::Optional<jit::vector<FrameState>> paused;
 349   };
 350
 351   enum class Status : uint8_t {
 352     /*
 353      * Status we have after initially being created.
 354      */
 355     None,
 356
 357     /*
 358      * Changes when we propagate state to taken blocks.  This status is used
 359      * during IR generation time.
 360      */
 361     Building,
 362
 363     /*
 364      * Changes how we handle predecessors we haven't visited yet.  This state
 365      * means we're doing computeFixedPoint() still.
 366      */
 367     RunningFixedPoint,
 368
 369     /*
 370      * Stops us from merging new state to blocks.  The computeFixedPoint call
 371      * has finished, and blocks may be inspected with that information, but we
 372      * don't need to propagate anything anywhere anymore.
 373      */
 374     FinishedFixedPoint,
 375
 376     /*
 377      * We're doing a reoptimize that's not based on a fixed-point computation.
 378      */
 379     LegacyReoptimize,
 380   };
 381
 382 private:
 383   bool checkInvariants() const;
 384   bool save(Block*);
 385   jit::vector<LocalState>& locals(unsigned inlineIdx);
 386   void trackDefInlineFP(const IRInstruction* inst);
 387   void trackInlineReturn();
 388   void loopHeaderClear(BCMarker);
 389   StackState& stackState(IRSPOffset offset);
 390   const StackState& stackState(IRSPOffset offset) const;
 391   void collectPostConds(Block* exitBlock);
 392
 393 private:
 394   FrameState& cur() {
 395     assert(!m_stack.empty());
 396     return m_stack.back();
 397   }
 398   const FrameState& cur() const {
 399     return const_cast<FrameStateMgr*>(this)->cur();
 400   }
 401
 402 private: // LocalStateHook overrides
 403   void setLocalValue(uint32_t id, SSATmp* value) override;
 404   void refineLocalValues(SSATmp* oldVal, SSATmp* newVal) override;
 405   void dropLocalRefsInnerTypes() override;
 406   void killLocalsForCall(bool) override;
 407   void refineLocalType(uint32_t id, Type type, TypeSource typeSrc) override;
 408   void predictLocalType(uint32_t id, Type type) override;
 409   void setLocalType(uint32_t id, Type type) override;
 410   void setBoxedLocalPrediction(uint32_t id, Type type) override;
 411   void updateLocalRefPredictions(SSATmp*, SSATmp*) override;
 412   void setLocalTypeSource(uint32_t id, TypeSource typeSrc) override;
 413   void clearLocals() override;
 414
 415 private: // stack tracking helpers
 416   void setStackValue(IRSPOffset, SSATmp*);
 417   void setStackType(IRSPOffset, Type);
 418   void refineStackValues(SSATmp* oldval, SSATmp* newVal);
 419   void refineStackType(IRSPOffset, Type, TypeSource typeSrc);
 420   void clearStackForCall();
 421   void setBoxedStkPrediction(IRSPOffset, Type type);
 422   void spillFrameStack(IRSPOffset);
 423
 424 private:
 425   Status m_status{Status::None};
 426
 427   /*
 428    * Stack of states.  We push and pop frames as we enter and leave inlined
 429    * calls.
 430    */
 431   jit::vector<FrameState> m_stack;
 432
 433   /*
 434    * Saved snapshots of the incoming and outgoing state of blocks.
 435    */
 436   jit::hash_map<Block*,BlockState> m_states;
 437
 438   /*
 439    * Post-conditions for exit blocks.
 440    */
 441   jit::hash_map<Block*,PostConditions> m_exitPostConds;
 442 };
 443
 444 //////////////////////////////////////////////////////////////////////
 445
 446 /*
 447  * Debug stringification.
 448  */
 449 std::string show(const FrameStateMgr&);
 450
 451 //////////////////////////////////////////////////////////////////////
 452
 453 } }
 454
 455 #endif