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

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-2013 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 #include "hphp/runtime/vm/jit/frame-state.h"
  18
  19 #include "hphp/util/trace.h"
  20 #include "hphp/runtime/vm/jit/ir-instruction.h"
  21 #include "hphp/runtime/vm/jit/simplifier.h"
  22 #include "hphp/runtime/vm/jit/ssa-tmp.h"
  23
  24 TRACE_SET_MOD(hhir);
  25
  26 namespace HPHP {
  27 namespace JIT {
  28
  29 FrameState::FrameState(IRUnit& unit)
  30   : FrameState(unit, unit.main()->front()->front().marker())
  31 {
  32 }
  33
  34 FrameState::FrameState(IRUnit& unit, BCMarker marker)
  35   : FrameState(unit, marker.spOff, marker.func)
  36 {
  37 }
  38
  39 FrameState::FrameState(IRUnit& unit, Offset initialSpOffset, const Func* func)
  40   : m_unit(unit)
  41   , m_curFunc(func)
  42   , m_spValue(nullptr)
  43   , m_fpValue(nullptr)
  44   , m_spOffset(initialSpOffset)
  45   , m_thisAvailable(false)
  46   , m_frameSpansCall(false)
  47   , m_hasFPAnchor(false)
  48   , m_locals(func->numLocals())
  49   , m_enableCse(false)
  50   , m_snapshots()
  51 {
  52 }
  53
  54 FrameState::~FrameState() {
  55 }
  56
  57 void FrameState::update(const IRInstruction* inst) {
  58   if (auto* taken = inst->taken()) {
  59     save(taken);
  60   }
  61
  62   auto const opc = inst->op();
  63
  64   getLocalEffects(inst, *this);
  65
  66   switch (opc) {
  67   case DefInlineFP:    trackDefInlineFP(inst);  break;
  68   case InlineReturn:   trackInlineReturn(inst); break;
  69
  70   case InlineFPAnchor: m_hasFPAnchor = true;  break;
  71
  72   case Call:
  73     m_spValue = inst->dst();
  74     m_frameSpansCall = true;
  75     // A call pops the ActRec and pushes a return value.
  76     m_spOffset -= kNumActRecCells;
  77     m_spOffset += 1;
  78     assert(m_spOffset >= 0);
  79     clearCse();
  80     break;
  81
  82   case CallArray:
  83     m_spValue = inst->dst();
  84     m_frameSpansCall = true;
  85     // A CallArray pops the ActRec an array arg and pushes a return value.
  86     m_spOffset -= kNumActRecCells;
  87     assert(m_spOffset >= 0);
  88     clearCse();
  89     break;
  90
  91   case ContEnter:
  92     clearCse();
  93     break;
  94
  95   case DefFP:
  96   case FreeActRec:
  97     m_fpValue = inst->dst();
  98     break;
  99
 100   case ReDefGeneratorSP:
 101     m_spValue = inst->dst();
 102     break;
 103
 104   case ReDefSP:
 105     m_spValue = inst->dst();
 106     m_spOffset = inst->extra<ReDefSP>()->offset;
 107     break;
 108
 109   case DefInlineSP:
 110   case DefSP:
 111     m_spValue = inst->dst();
 112     m_spOffset = inst->extra<StackOffset>()->offset;
 113     break;
 114
 115   case AssertStk:
 116   case AssertStkVal:
 117   case CastStk:
 118   case CoerceStk:
 119   case CheckStk:
 120   case GuardStk:
 121   case ExceptionBarrier:
 122     m_spValue = inst->dst();
 123     break;
 124
 125   case SpillStack: {
 126     m_spValue = inst->dst();
 127     // Push the spilled values but adjust for the popped values
 128     int64_t stackAdjustment = inst->src(1)->getValInt();
 129     m_spOffset -= stackAdjustment;
 130     m_spOffset += spillValueCells(inst);
 131     break;
 132   }
 133
 134   case SpillFrame:
 135   case CufIterSpillFrame:
 136     m_spValue = inst->dst();
 137     m_spOffset += kNumActRecCells;
 138     break;
 139
 140   case InterpOne:
 141   case InterpOneCF: {
 142     m_spValue = inst->dst();
 143     auto const& extra = *inst->extra<InterpOneData>();
 144     int64_t stackAdjustment = extra.cellsPopped - extra.cellsPushed;
 145     // push the return value if any and adjust for the popped values
 146     m_spOffset -= stackAdjustment;
 147     break;
 148   }
 149
 150   case AssertLoc:
 151   case GuardLoc:
 152   case CheckLoc:
 153     m_fpValue = inst->dst();
 154     break;
 155
 156   case LdThis:
 157     m_thisAvailable = true;
 158     break;
 159
 160   default:
 161     break;
 162   }
 163
 164   if (inst->modifiesStack()) {
 165     m_spValue = inst->modifiedStkPtr();
 166   }
 167
 168   // update the CSE table
 169   if (m_enableCse && inst->canCSE()) {
 170     cseInsert(inst);
 171   }
 172
 173   // if the instruction kills any of its sources, remove them from the
 174   // CSE table
 175   if (inst->killsSources()) {
 176     for (int i = 0; i < inst->numSrcs(); ++i) {
 177       if (inst->killsSource(i)) {
 178         cseKill(inst->src(i));
 179       }
 180     }
 181   }
 182 }
 183
 184 void FrameState::getLocalEffects(const IRInstruction* inst,
 185                                  LocalStateHook& hook) const {
 186   auto killIterLocals = [&](const std::initializer_list<uint32_t>& ids) {
 187     for (auto id : ids) {
 188       hook.setLocalValue(inst->src(id)->getValInt(), nullptr);
 189     }
 190   };
 191
 192   auto killedCallLocals = false;
 193   if ((inst->is(CallArray) && inst->extra<CallArrayData>()->destroyLocals) ||
 194       (inst->is(Call, CallBuiltin) && inst->extra<CallData>()->destroyLocals)) {
 195     clearLocals(hook);
 196     killedCallLocals = true;
 197   }
 198
 199   switch (inst->op()) {
 200     case Call:
 201     case CallArray:
 202     case ContEnter:
 203       killLocalsForCall(hook, killedCallLocals);
 204       break;
 205
 206     case StRefNT:
 207     case StRef: {
 208       SSATmp* newRef = inst->dst();
 209       SSATmp* prevRef = inst->src(0);
 210       // update other tracked locals that also contain prevRef
 211       updateLocalRefValues(hook, prevRef, newRef);
 212       break;
 213     }
 214
 215     case StLocNT:
 216     case StLoc:
 217       hook.setLocalValue(inst->extra<LocalId>()->locId, inst->src(1));
 218       break;
 219
 220     case LdLoc:
 221       hook.setLocalValue(inst->extra<LdLoc>()->locId, inst->dst());
 222       break;
 223
 224     case AssertLoc:
 225     case GuardLoc:
 226     case CheckLoc:
 227       hook.refineLocalType(inst->extra<LocalId>()->locId, inst->typeParam());
 228       break;
 229
 230     case OverrideLocVal: {
 231       auto const locId = inst->extra<LocalId>()->locId;
 232       hook.setLocalValue(locId, inst->src(1));
 233       break;
 234     }
 235
 236     case CheckType: {
 237       SSATmp* newVal = inst->dst();
 238       SSATmp* oldVal = inst->src(0);
 239       refineLocalValues(hook, oldVal, newVal);
 240       break;
 241     }
 242
 243     case IterInitK:
 244     case WIterInitK:
 245       // kill the locals to which this instruction stores iter's key and value
 246       killIterLocals({3, 4});
 247       break;
 248
 249     case IterInit:
 250     case WIterInit:
 251       // kill the local to which this instruction stores iter's value
 252       killIterLocals({3});
 253       break;
 254
 255     case IterNextK:
 256     case WIterNextK:
 257       // kill the locals to which this instruction stores iter's key and value
 258       killIterLocals({2, 3});
 259       break;
 260
 261     case IterNext:
 262     case WIterNext:
 263       // kill the local to which this instruction stores iter's value
 264       killIterLocals({2});
 265       break;
 266
 267     case InterpOne:
 268     case InterpOneCF: {
 269       auto const& id = *inst->extra<InterpOneData>();
 270       assert(!id.smashesAllLocals || id.nChangedLocals == 0);
 271       if (id.smashesAllLocals) {
 272         clearLocals(hook);
 273       } else {
 274         auto it = id.changedLocals;
 275         auto const end = it + id.nChangedLocals;
 276         for (; it != end; ++it) {
 277           auto& loc = *it;
 278           // If changing the inner type of a boxed local, also drop the
 279           // information about inner types for any other boxed locals.
 280           if (loc.type.isBoxed()) dropLocalRefsInnerTypes(hook);
 281           hook.setLocalType(loc.id, loc.type);
 282         }
 283       }
 284       break;
 285     }
 286     default:
 287       break;
 288   }
 289
 290   if (MInstrEffects::supported(inst)) MInstrEffects::get(inst, hook);
 291 }
 292
 293 ///// Support helpers for getLocalEffects /////
 294 void FrameState::clearLocals(LocalStateHook& hook) const {
 295   for (unsigned i = 0; i < m_locals.size(); ++i) {
 296     hook.setLocalValue(i, nullptr);
 297   }
 298 }
 299
 300 void FrameState::refineLocalValues(LocalStateHook& hook,
 301                                    SSATmp* oldVal, SSATmp* newVal) const {
 302   assert(newVal->inst()->is(CheckType));
 303   assert(newVal->inst()->src(0) == oldVal);
 304
 305   for (unsigned i = 0, n = m_locals.size(); i < n; ++i) {
 306     if (m_locals[i].value == oldVal) {
 307       hook.refineLocalValue(i, newVal);
 308     }
 309   }
 310 }
 311
 312 template<typename L>
 313 void FrameState::walkAllInlinedLocals(L body, bool skipThisFrame) const {
 314   auto doBody = [&](const LocalVec& locals, unsigned inlineIdx) {
 315     for (uint32_t i = 0, n = locals.size(); i < n; ++i) {
 316       body(i, inlineIdx, locals[i]);
 317     }
 318   };
 319
 320   if (!skipThisFrame) {
 321     doBody(m_locals, 0);
 322   }
 323   for (int i = 0, n = m_inlineSavedStates.size(); i < n; ++i) {
 324     doBody(m_inlineSavedStates[i].locals, i + 1);
 325   }
 326 }
 327
 328 void FrameState::forEachLocal(LocalFunc body) const {
 329   walkAllInlinedLocals(
 330   [&](uint32_t i, unsigned inlineIdx, const LocalState& local) {
 331     auto* value = local.unsafe ? nullptr : local.value;
 332     body(i, value);
 333   });
 334 }
 335
 336 /**
 337  * Called to clear out the tracked local values at a call site.  Calls kill all
 338  * registers, so we don't want to keep locals in registers across calls. We do
 339  * continue tracking the types in locals, however.
 340  */
 341 void FrameState::killLocalsForCall(LocalStateHook& hook,
 342                                    bool skipThisFrame) const {
 343   walkAllInlinedLocals(
 344   [&](uint32_t i, unsigned inlineIdx, const LocalState& local) {
 345     auto* value = local.value;
 346     if (local.unsafe || !value || value->inst()->is(DefConst)) return;
 347
 348     hook.killLocalForCall(i, inlineIdx, value);
 349   },
 350   skipThisFrame);
 351 }
 352
 353 //
 354 // This method updates the tracked values and types of all locals that contain
 355 // oldRef so that they now contain newRef.
 356 // This should only be called for ref/boxed types.
 357 //
 358 void FrameState::updateLocalRefValues(LocalStateHook& hook,
 359                                       SSATmp* oldRef, SSATmp* newRef) const {
 360   assert(oldRef->type().isBoxed());
 361   assert(newRef->type().isBoxed());
 362
 363   walkAllInlinedLocals(
 364   [&](uint32_t i, unsigned inlineIdx, const LocalState& local) {
 365     if (local.value != oldRef) return;
 366
 367     hook.updateLocalRefValue(i, inlineIdx, oldRef, newRef);
 368   });
 369 }
 370
 371 /**
 372  * This method changes any boxed local into a BoxedInitCell type. It's safe to
 373  * assume they're init because you can never have a reference to uninit.
 374  */
 375 void FrameState::dropLocalRefsInnerTypes(LocalStateHook& hook) const {
 376   walkAllInlinedLocals(
 377   [&](uint32_t i, unsigned inlineIdx, const LocalState& local) {
 378     if (local.type.isBoxed()) {
 379       hook.dropLocalInnerType(i, inlineIdx);
 380     }
 381   });
 382 }
 383
 384 ///// Methods for managing and merge block state /////
 385 void FrameState::startBlock(Block* block) {
 386   auto it = m_snapshots.find(block);
 387   if (it != m_snapshots.end()) {
 388     load(it->second);
 389     m_inlineSavedStates = it->second.inlineSavedStates;
 390     m_snapshots.erase(it);
 391   }
 392 }
 393
 394 void FrameState::finishBlock(Block* block) {
 395   assert(block->back().isTerminal() == !block->next());
 396
 397   if (!block->back().isTerminal()) {
 398     save(block->next());
 399   }
 400 }
 401
 402 FrameState::Snapshot FrameState::createSnapshot() const {
 403   Snapshot state;
 404   state.spValue = m_spValue;
 405   state.fpValue = m_fpValue;
 406   state.curFunc = m_curFunc;
 407   state.spOffset = m_spOffset;
 408   state.thisAvailable = m_thisAvailable;
 409   state.locals = m_locals;
 410   state.curMarker = m_marker;
 411   state.frameSpansCall = m_frameSpansCall;
 412   state.needsFPAnchor = m_hasFPAnchor;
 413   assert(state.curMarker.valid());
 414   return state;
 415 }
 416
 417 /*
 418  * Save current state for block.  If this is the first time saving state for
 419  * block, create a new snapshot.  Otherwise merge the current state into the
 420  * existing snapshot.
 421  */
 422 void FrameState::save(Block* block) {
 423   auto it = m_snapshots.find(block);
 424   if (it != m_snapshots.end()) {
 425     merge(it->second);
 426   } else {
 427     auto& snapshot = m_snapshots[block] = createSnapshot();
 428     snapshot.inlineSavedStates = m_inlineSavedStates;
 429   }
 430 }
 431
 432 void FrameState::load(Snapshot& state) {
 433   m_spValue = state.spValue;
 434   m_fpValue = state.fpValue;
 435   m_spOffset = state.spOffset;
 436   m_curFunc = state.curFunc;
 437   m_thisAvailable = state.thisAvailable;
 438   m_locals = std::move(state.locals);
 439   m_marker = state.curMarker;
 440   m_hasFPAnchor = state.needsFPAnchor;
 441   m_frameSpansCall = m_frameSpansCall || state.frameSpansCall;
 442
 443   // If spValue is null, we merged two different but equivalent values. We
 444   // could define a new sp but that would drop a lot of useful information on
 445   // the floor. Let's cross this bridge when we reach it.
 446   always_assert(m_spValue &&
 447                 "Attempted to merge two states with different stack pointers");
 448 }
 449
 450 /*
 451  * Merge current state into state.  Frame pointers and stack depth must match.
 452  * If the stack pointer tmps are different, clear the tracked value (we can
 453  * make a new one, given fp and spOffset).
 454  *
 455  * thisIsAvailable remains true if it's true in both states.
 456  * local variable values are preserved if the match in both states.
 457  * types are combined using Type::unionOf.
 458  */
 459 void FrameState::merge(Snapshot& state) {
 460   // cannot merge fp or spOffset state, so assert they match
 461   assert(state.fpValue == m_fpValue);
 462   assert(state.spOffset == m_spOffset);
 463   assert(state.curFunc == m_curFunc);
 464   if (state.spValue != m_spValue) {
 465     // we have two different sp definitions but we know they're equal
 466     // because spOffset matched.
 467     state.spValue = nullptr;
 468   }
 469   // this is available iff it's available in both states
 470   state.thisAvailable &= m_thisAvailable;
 471
 472   assert(m_locals.size() == state.locals.size());
 473   for (unsigned i = 0; i < m_locals.size(); ++i) {
 474     auto& local = state.locals[i];
 475
 476     // preserve local values if they're the same in both states,
 477     // This would be the place to insert phi nodes (jmps+deflabels) if we want
 478     // to avoid clearing state, which triggers a downstream reload.
 479     if (local.value != m_locals[i].value) local.value = nullptr;
 480
 481     local.type = Type::unionOf(local.type, m_locals[i].type);
 482     local.unsafe = local.unsafe || m_locals[i].unsafe;
 483     local.written = local.written || m_locals[i].written;
 484   }
 485
 486   // We should not be merging states that have different hhbc bytecode
 487   // boundaries.
 488   assert(m_marker.valid() && state.curMarker == m_marker);
 489
 490   // For now, we shouldn't be merging states with different inline states.
 491   assert(m_inlineSavedStates == state.inlineSavedStates);
 492 }
 493
 494 void FrameState::trackDefInlineFP(const IRInstruction* inst) {
 495   auto const target     = inst->extra<DefInlineFP>()->target;
 496   auto const savedSPOff = inst->extra<DefInlineFP>()->retSPOff;
 497   auto const calleeFP   = inst->dst();
 498   auto const calleeSP   = inst->src(0);
 499   auto const savedSP    = inst->src(1);
 500
 501   // Saved tracebuilder state will include the "return" fp/sp.
 502   // Whatever the current fpValue is is good enough, but we have to be
 503   // passed in the StkPtr that represents the stack prior to the
 504   // ActRec being allocated.
 505   m_spOffset = savedSPOff;
 506   m_spValue = savedSP;
 507
 508   auto const stackValues = collectStackValues(m_spValue, m_spOffset);
 509   for (DEBUG_ONLY auto& val : stackValues) {
 510     FTRACE(4, "    marking caller stack value available: {}\n",
 511            val->toString());
 512   }
 513
 514   m_inlineSavedStates.emplace_back(createSnapshot());
 515
 516   /*
 517    * Set up the callee state.
 518    *
 519    * We set m_thisIsAvailable to true on any object method, because we
 520    * just don't inline calls to object methods with a null $this.
 521    */
 522   m_fpValue         = calleeFP;
 523   m_spValue         = calleeSP;
 524   m_thisAvailable   = target->cls() != nullptr && !target->isStatic();
 525   m_curFunc         = target;
 526   m_frameSpansCall  = false;
 527   m_hasFPAnchor     = false;
 528
 529   m_locals.clear();
 530   m_locals.resize(target->numLocals());
 531 }
 532
 533 void FrameState::trackInlineReturn(const IRInstruction* inst) {
 534   assert(m_inlineSavedStates.size());
 535   assert(m_inlineSavedStates.back().inlineSavedStates.empty());
 536   load(m_inlineSavedStates.back());
 537   m_inlineSavedStates.pop_back();
 538 }
 539
 540 bool FrameState::needsFPAnchor(IRInstruction* inst) const {
 541   return m_inlineSavedStates.size() && !m_hasFPAnchor &&
 542     (inst->isNative() || inst->mayRaiseError());
 543 }
 544
 545 CSEHash* FrameState::cseHashTable(const IRInstruction* inst) {
 546   return inst->is(DefConst) ? &m_unit.constTable() : &m_cseHash;
 547 }
 548
 549 void FrameState::cseInsert(const IRInstruction* inst) {
 550   cseHashTable(inst)->insert(inst->dst());
 551 }
 552
 553 void FrameState::cseKill(SSATmp* src) {
 554   if (src->inst()->canCSE()) {
 555     cseHashTable(src->inst())->erase(src);
 556   }
 557 }
 558
 559 void FrameState::clearCse() {
 560   m_cseHash.clear();
 561 }
 562
 563 SSATmp* FrameState::cseLookup(IRInstruction* inst,
 564                                 const folly::Optional<IdomVector>& idoms) {
 565   auto tmp = cseHashTable(inst)->lookup(inst);
 566   if (tmp && idoms) {
 567     // During a reoptimize pass, we need to make sure that any values
 568     // we want to reuse for CSE are only reused in blocks dominated by
 569     // the block that defines it.
 570     if (!dominates(tmp->inst()->block(), inst->block(), *idoms)) {
 571       return nullptr;
 572     }
 573   }
 574   return tmp;
 575 }
 576
 577 void FrameState::clear() {
 578   clearCse();
 579   clearLocals(*this);
 580   m_frameSpansCall = false;
 581   m_hasFPAnchor = false;
 582   m_spValue = m_fpValue = nullptr;
 583   m_spOffset = 0;
 584   m_thisAvailable = false;
 585   m_marker = BCMarker();
 586   m_snapshots.clear();
 587   assert(m_inlineSavedStates.empty());
 588 }
 589
 590 SSATmp* FrameState::localValue(uint32_t id) const {
 591   always_assert(id < m_locals.size());
 592   return m_locals[id].unsafe ? nullptr : m_locals[id].value;
 593 }
 594
 595 SSATmp* FrameState::localValueSource(uint32_t id) const {
 596   always_assert(id < m_locals.size());
 597   auto const& local = m_locals[id];
 598
 599   if (local.value) return local.value;
 600   if (local.written) return nullptr;
 601   return fp();
 602 }
 603
 604 Type FrameState::localType(uint32_t id) const {
 605   always_assert(id < m_locals.size());
 606   assert(m_locals[id].type != Type::None);
 607   return m_locals[id].type;
 608 }
 609
 610 void FrameState::setLocalValue(uint32_t id, SSATmp* value) {
 611   always_assert(id < m_locals.size());
 612   m_locals[id].value = value;
 613   m_locals[id].type = value ? value->type() : Type::Gen;
 614   m_locals[id].written = true;
 615   m_locals[id].unsafe = false;
 616 }
 617
 618 void FrameState::refineLocalValue(uint32_t id, SSATmp* value) {
 619   always_assert(id < m_locals.size());
 620   auto& local = m_locals[id];
 621   local.value = value;
 622   local.type = value->type();
 623 }
 624
 625 void FrameState::refineLocalType(uint32_t id, Type type) {
 626   always_assert(id < m_locals.size());
 627   assert(type <= m_locals[id].type);
 628   m_locals[id].type = type;
 629 }
 630
 631 void FrameState::setLocalType(uint32_t id, Type type) {
 632   always_assert(id < m_locals.size());
 633   m_locals[id].value = nullptr;
 634   m_locals[id].type = type;
 635   m_locals[id].written = true;
 636   m_locals[id].unsafe = false;
 637 }
 638
 639 /*
 640  * Get a reference to the LocalVec from an inline index. 0 means the current
 641  * frame, otherwise it's index (inlineIdx - 1) in m_inlineSavedStates.
 642  */
 643 FrameState::LocalVec& FrameState::locals(unsigned inlineIdx) {
 644   if (inlineIdx == 0) {
 645     return m_locals;
 646   } else {
 647     --inlineIdx;
 648     assert(inlineIdx < m_inlineSavedStates.size());
 649     return m_inlineSavedStates[inlineIdx].locals;
 650   }
 651 }
 652
 653 void FrameState::killLocalForCall(uint32_t id, unsigned inlineIdx,
 654                                   SSATmp* val) {
 655   auto& locs = locals(inlineIdx);
 656   always_assert(id < locs.size());
 657   locs[id].unsafe = true;
 658 }
 659
 660 void FrameState::updateLocalRefValue(uint32_t id, unsigned inlineIdx,
 661                                      SSATmp* oldRef, SSATmp* newRef) {
 662   auto& local = locals(inlineIdx)[id];
 663   assert(!local.unsafe);
 664   assert(local.value == oldRef);
 665   local.value = newRef;
 666   local.type  = newRef->type();
 667 }
 668
 669 void FrameState::dropLocalInnerType(uint32_t id, unsigned inlineIdx) {
 670   auto& local = locals(inlineIdx)[id];
 671   assert(local.type.isBoxed());
 672   local.type = Type::BoxedInitCell;
 673 }
 674
 675 } }