2 +----------------------------------------------------------------------+
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 +----------------------------------------------------------------------+
17 #include "hphp/runtime/vm/jit/frame-state.h"
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"
29 FrameState::FrameState(IRUnit
& unit
)
30 : FrameState(unit
, unit
.entry()->front().marker())
34 FrameState::FrameState(IRUnit
& unit
, BCMarker marker
)
35 : FrameState(unit
, marker
.spOff
, marker
.func
)
39 FrameState::FrameState(IRUnit
& unit
, Offset initialSpOffset
, const Func
* func
)
44 , m_spOffset(initialSpOffset
)
45 , m_thisAvailable(false)
46 , m_frameSpansCall(false)
47 , m_locals(func
->numLocals())
53 FrameState::~FrameState() {
56 void FrameState::update(const IRInstruction
* inst
) {
57 if (auto* taken
= inst
->taken()) {
61 auto const opc
= inst
->op();
63 getLocalEffects(inst
, *this);
66 case DefInlineFP
: trackDefInlineFP(inst
); break;
67 case InlineReturn
: trackInlineReturn(inst
); break;
70 m_spValue
= inst
->dst();
71 m_frameSpansCall
= true;
72 // A call pops the ActRec and pushes a return value.
73 m_spOffset
-= kNumActRecCells
;
75 assert(m_spOffset
>= 0);
80 m_spValue
= inst
->dst();
81 m_frameSpansCall
= true;
82 // A CallArray pops the ActRec an array arg and pushes a return value.
83 m_spOffset
-= kNumActRecCells
;
84 assert(m_spOffset
>= 0);
94 m_fpValue
= inst
->dst();
97 case ReDefGeneratorSP
:
98 m_spValue
= inst
->dst();
102 m_spValue
= inst
->dst();
103 m_spOffset
= inst
->extra
<ReDefSP
>()->spOffset
;
108 m_spValue
= inst
->dst();
109 m_spOffset
= inst
->extra
<StackOffset
>()->offset
;
117 case ExceptionBarrier
:
118 m_spValue
= inst
->dst();
122 m_spValue
= inst
->dst();
123 // Push the spilled values but adjust for the popped values
124 int64_t stackAdjustment
= inst
->src(1)->getValInt();
125 m_spOffset
-= stackAdjustment
;
126 m_spOffset
+= spillValueCells(inst
);
131 case CufIterSpillFrame
:
132 m_spValue
= inst
->dst();
133 m_spOffset
+= kNumActRecCells
;
138 m_spValue
= inst
->dst();
139 auto const& extra
= *inst
->extra
<InterpOneData
>();
140 int64_t stackAdjustment
= extra
.cellsPopped
- extra
.cellsPushed
;
141 // push the return value if any and adjust for the popped values
142 m_spOffset
-= stackAdjustment
;
149 m_fpValue
= inst
->dst();
153 m_thisAvailable
= true;
160 if (inst
->modifiesStack()) {
161 m_spValue
= inst
->modifiedStkPtr();
164 // update the CSE table
165 if (m_enableCse
&& inst
->canCSE()) {
169 // if the instruction kills any of its sources, remove them from the
171 if (inst
->killsSources()) {
172 for (int i
= 0; i
< inst
->numSrcs(); ++i
) {
173 if (inst
->killsSource(i
)) {
174 cseKill(inst
->src(i
));
180 void FrameState::getLocalEffects(const IRInstruction
* inst
,
181 LocalStateHook
& hook
) const {
182 auto killIterLocals
= [&](const std::initializer_list
<uint32_t>& ids
) {
183 for (auto id
: ids
) {
184 hook
.setLocalValue(inst
->src(id
)->getValInt(), nullptr);
188 auto killedCallLocals
= false;
189 if ((inst
->is(CallArray
) && inst
->extra
<CallArrayData
>()->destroyLocals
) ||
190 (inst
->is(Call
, CallBuiltin
) && inst
->extra
<CallData
>()->destroyLocals
)) {
192 killedCallLocals
= true;
195 switch (inst
->op()) {
199 killLocalsForCall(hook
, killedCallLocals
);
204 SSATmp
* newRef
= inst
->dst();
205 SSATmp
* prevRef
= inst
->src(0);
206 // update other tracked locals that also contain prevRef
207 updateLocalRefValues(hook
, prevRef
, newRef
);
213 hook
.setLocalValue(inst
->extra
<LocalId
>()->locId
, inst
->src(1));
217 hook
.setLocalValue(inst
->extra
<LdLoc
>()->locId
, inst
->dst());
223 hook
.refineLocalType(inst
->extra
<LocalId
>()->locId
, inst
->typeParam());
227 SSATmp
* newVal
= inst
->dst();
228 SSATmp
* oldVal
= inst
->src(0);
229 refineLocalValues(hook
, oldVal
, newVal
);
235 // kill the locals to which this instruction stores iter's key and value
236 killIterLocals({3, 4});
241 // kill the local to which this instruction stores iter's value
247 // kill the locals to which this instruction stores iter's key and value
248 killIterLocals({2, 3});
253 // kill the local to which this instruction stores iter's value
259 auto const& id
= *inst
->extra
<InterpOneData
>();
260 assert(!id
.smashesAllLocals
|| id
.nChangedLocals
== 0);
261 if (id
.smashesAllLocals
) {
264 auto it
= id
.changedLocals
;
265 auto const end
= it
+ id
.nChangedLocals
;
266 for (; it
!= end
; ++it
) {
268 // If changing the inner type of a boxed local, also drop the
269 // information about inner types for any other boxed locals.
270 if (loc
.type
.isBoxed()) dropLocalRefsInnerTypes(hook
);
271 hook
.setLocalType(loc
.id
, loc
.type
);
280 if (MInstrEffects::supported(inst
)) MInstrEffects::get(inst
, hook
);
283 ///// Support helpers for getLocalEffects /////
284 void FrameState::clearLocals(LocalStateHook
& hook
) const {
285 for (unsigned i
= 0; i
< m_locals
.size(); ++i
) {
286 hook
.setLocalValue(i
, nullptr);
290 void FrameState::refineLocalValues(LocalStateHook
& hook
,
291 SSATmp
* oldVal
, SSATmp
* newVal
) const {
292 assert(newVal
->inst()->is(CheckType
));
293 assert(newVal
->inst()->src(0) == oldVal
);
295 for (unsigned i
= 0, n
= m_locals
.size(); i
< n
; ++i
) {
296 if (m_locals
[i
].value
== oldVal
) {
297 hook
.refineLocalValue(i
, oldVal
, newVal
);
302 void FrameState::forEachFrame(FrameFunc body
) const {
303 body(m_fpValue
, m_spOffset
);
305 // We push each new frame onto the end of m_inlineSavedStates, so walk it
306 // backwards to go from inner frames to outer frames.
307 for (auto it
= m_inlineSavedStates
.rbegin();
308 it
!= m_inlineSavedStates
.rend(); ++it
) {
309 auto const& state
= *it
;
310 body(state
.fpValue
, state
.spOffset
);
315 void FrameState::walkAllInlinedLocals(L body
, bool skipThisFrame
) const {
316 auto doBody
= [&](const LocalVec
& locals
, unsigned inlineIdx
) {
317 for (uint32_t i
= 0, n
= locals
.size(); i
< n
; ++i
) {
318 body(i
, inlineIdx
, locals
[i
]);
322 if (!skipThisFrame
) {
325 for (int i
= 0, n
= m_inlineSavedStates
.size(); i
< n
; ++i
) {
326 doBody(m_inlineSavedStates
[i
].locals
, i
+ 1);
330 void FrameState::forEachLocal(LocalFunc body
) const {
331 walkAllInlinedLocals(
332 [&](uint32_t i
, unsigned inlineIdx
, const LocalState
& local
) {
333 auto* value
= local
.unsafe
? nullptr : local
.value
;
339 * Called to clear out the tracked local values at a call site. Calls kill all
340 * registers, so we don't want to keep locals in registers across calls. We do
341 * continue tracking the types in locals, however.
343 void FrameState::killLocalsForCall(LocalStateHook
& hook
,
344 bool skipThisFrame
) const {
345 walkAllInlinedLocals(
346 [&](uint32_t i
, unsigned inlineIdx
, const LocalState
& local
) {
347 auto* value
= local
.value
;
348 if (local
.unsafe
|| !value
|| value
->inst()->is(DefConst
)) return;
350 hook
.killLocalForCall(i
, inlineIdx
, value
);
356 // This method updates the tracked values and types of all locals that contain
357 // oldRef so that they now contain newRef.
358 // This should only be called for ref/boxed types.
360 void FrameState::updateLocalRefValues(LocalStateHook
& hook
,
361 SSATmp
* oldRef
, SSATmp
* newRef
) const {
362 assert(oldRef
->type().isBoxed());
363 assert(newRef
->type().isBoxed());
365 walkAllInlinedLocals(
366 [&](uint32_t i
, unsigned inlineIdx
, const LocalState
& local
) {
367 if (local
.value
!= oldRef
) return;
369 hook
.updateLocalRefValue(i
, inlineIdx
, oldRef
, newRef
);
374 * This method changes any boxed local into a BoxedInitCell type. It's safe to
375 * assume they're init because you can never have a reference to uninit.
377 void FrameState::dropLocalRefsInnerTypes(LocalStateHook
& hook
) const {
378 walkAllInlinedLocals(
379 [&](uint32_t i
, unsigned inlineIdx
, const LocalState
& local
) {
380 if (local
.type
.isBoxed()) {
381 hook
.dropLocalInnerType(i
, inlineIdx
);
386 ///// Methods for managing and merge block state /////
387 void FrameState::startBlock(Block
* block
) {
388 auto it
= m_snapshots
.find(block
);
389 if (it
!= m_snapshots
.end()) {
391 FTRACE(4, "Loading state for B{}: {}\n", block
->id(), show(*this));
392 m_inlineSavedStates
= it
->second
.inlineSavedStates
;
393 m_snapshots
.erase(it
);
397 void FrameState::finishBlock(Block
* block
) {
398 assert(block
->back().isTerminal() == !block
->next());
400 if (!block
->back().isTerminal()) {
405 FrameState::Snapshot
FrameState::createSnapshot() const {
407 state
.spValue
= m_spValue
;
408 state
.fpValue
= m_fpValue
;
409 state
.curFunc
= m_curFunc
;
410 state
.spOffset
= m_spOffset
;
411 state
.thisAvailable
= m_thisAvailable
;
412 state
.locals
= m_locals
;
413 state
.curMarker
= m_marker
;
414 state
.frameSpansCall
= m_frameSpansCall
;
415 assert(state
.curMarker
.valid());
420 * Save current state for block. If this is the first time saving state for
421 * block, create a new snapshot. Otherwise merge the current state into the
424 void FrameState::save(Block
* block
) {
425 FTRACE(4, "Saving state for B{}: {}\n", block
->id(), show(*this));
426 auto it
= m_snapshots
.find(block
);
427 if (it
!= m_snapshots
.end()) {
429 FTRACE(4, "Merged state: {}\n", show(*this));
431 auto& snapshot
= m_snapshots
[block
] = createSnapshot();
432 snapshot
.inlineSavedStates
= m_inlineSavedStates
;
436 void FrameState::load(Snapshot
& state
) {
437 m_spValue
= state
.spValue
;
438 m_fpValue
= state
.fpValue
;
439 m_spOffset
= state
.spOffset
;
440 m_curFunc
= state
.curFunc
;
441 m_thisAvailable
= state
.thisAvailable
;
442 m_locals
= std::move(state
.locals
);
443 m_marker
= state
.curMarker
;
444 m_frameSpansCall
= m_frameSpansCall
|| state
.frameSpansCall
;
446 // If spValue is null, we merged two different but equivalent values. We
447 // could define a new sp but that would drop a lot of useful information on
448 // the floor. Let's cross this bridge when we reach it.
449 always_assert(m_spValue
&&
450 "Attempted to merge two states with different stack pointers");
454 * Merge current state into state. Frame pointers and stack depth must match.
455 * If the stack pointer tmps are different, clear the tracked value (we can
456 * make a new one, given fp and spOffset).
458 * thisIsAvailable remains true if it's true in both states.
459 * local variable values are preserved if the match in both states.
460 * types are combined using Type::unionOf.
462 void FrameState::merge(Snapshot
& state
) {
463 // cannot merge fp or spOffset state, so assert they match
464 assert(state
.fpValue
== m_fpValue
);
465 assert(state
.spOffset
== m_spOffset
);
466 assert(state
.curFunc
== m_curFunc
);
467 if (state
.spValue
!= m_spValue
) {
468 // we have two different sp definitions but we know they're equal
469 // because spOffset matched.
470 state
.spValue
= nullptr;
472 // this is available iff it's available in both states
473 state
.thisAvailable
&= m_thisAvailable
;
475 assert(m_locals
.size() == state
.locals
.size());
476 for (unsigned i
= 0; i
< m_locals
.size(); ++i
) {
477 auto& local
= state
.locals
[i
];
479 // preserve local values if they're the same in both states,
480 // This would be the place to insert phi nodes (jmps+deflabels) if we want
481 // to avoid clearing state, which triggers a downstream reload.
482 if (local
.value
!= m_locals
[i
].value
) local
.value
= nullptr;
484 local
.type
= Type::unionOf(local
.type
, m_locals
[i
].type
);
485 local
.unsafe
= local
.unsafe
|| m_locals
[i
].unsafe
;
486 local
.written
= local
.written
|| m_locals
[i
].written
;
489 // We should not be merging states that have different hhbc bytecode
491 assert(m_marker
.valid() && state
.curMarker
== m_marker
);
493 // For now, we shouldn't be merging states with different inline states.
494 assert(m_inlineSavedStates
== state
.inlineSavedStates
);
497 void FrameState::trackDefInlineFP(const IRInstruction
* inst
) {
498 auto const target
= inst
->extra
<DefInlineFP
>()->target
;
499 auto const savedSPOff
= inst
->extra
<DefInlineFP
>()->retSPOff
;
500 auto const calleeFP
= inst
->dst();
501 auto const calleeSP
= inst
->src(0);
502 auto const savedSP
= inst
->src(1);
504 // Saved tracebuilder state will include the "return" fp/sp.
505 // Whatever the current fpValue is is good enough, but we have to be
506 // passed in the StkPtr that represents the stack prior to the
507 // ActRec being allocated.
508 m_spOffset
= savedSPOff
;
511 auto const stackValues
= collectStackValues(m_spValue
, m_spOffset
);
512 for (DEBUG_ONLY
auto& val
: stackValues
) {
513 FTRACE(4, " marking caller stack value available: {}\n",
517 m_inlineSavedStates
.emplace_back(createSnapshot());
520 * Set up the callee state.
522 * We set m_thisIsAvailable to true on any object method, because we
523 * just don't inline calls to object methods with a null $this.
525 m_fpValue
= calleeFP
;
526 m_spValue
= calleeSP
;
527 m_thisAvailable
= target
->cls() != nullptr && !target
->isStatic();
529 m_frameSpansCall
= false;
532 m_locals
.resize(target
->numLocals());
535 void FrameState::trackInlineReturn(const IRInstruction
* inst
) {
536 assert(m_inlineSavedStates
.size());
537 assert(m_inlineSavedStates
.back().inlineSavedStates
.empty());
538 load(m_inlineSavedStates
.back());
539 m_inlineSavedStates
.pop_back();
542 CSEHash
* FrameState::cseHashTable(const IRInstruction
* inst
) {
543 return inst
->is(DefConst
) ? &m_unit
.constTable() : &m_cseHash
;
546 void FrameState::cseInsert(const IRInstruction
* inst
) {
547 cseHashTable(inst
)->insert(inst
->dst());
550 void FrameState::cseKill(SSATmp
* src
) {
551 if (src
->inst()->canCSE()) {
552 cseHashTable(src
->inst())->erase(src
);
556 void FrameState::clearCse() {
560 SSATmp
* FrameState::cseLookup(IRInstruction
* inst
,
561 const folly::Optional
<IdomVector
>& idoms
) {
562 auto tmp
= cseHashTable(inst
)->lookup(inst
);
564 // During a reoptimize pass, we need to make sure that any values
565 // we want to reuse for CSE are only reused in blocks dominated by
566 // the block that defines it.
567 if (!dominates(tmp
->inst()->block(), inst
->block(), *idoms
)) {
574 void FrameState::clear() {
577 m_frameSpansCall
= false;
578 m_spValue
= m_fpValue
= nullptr;
580 m_thisAvailable
= false;
581 m_marker
= BCMarker();
583 assert(m_inlineSavedStates
.empty());
586 SSATmp
* FrameState::localValue(uint32_t id
) const {
587 always_assert(id
< m_locals
.size());
588 return m_locals
[id
].unsafe
? nullptr : m_locals
[id
].value
;
591 SSATmp
* FrameState::localValueSource(uint32_t id
) const {
592 always_assert(id
< m_locals
.size());
593 auto const& local
= m_locals
[id
];
595 if (local
.value
) return local
.value
;
596 if (local
.written
) return nullptr;
600 Type
FrameState::localType(uint32_t id
) const {
601 always_assert(id
< m_locals
.size());
602 assert(m_locals
[id
].type
!= Type::None
);
603 return m_locals
[id
].type
;
606 void FrameState::setLocalValue(uint32_t id
, SSATmp
* value
) {
607 always_assert(id
< m_locals
.size());
608 m_locals
[id
].value
= value
;
609 m_locals
[id
].type
= value
? value
->type() : Type::Gen
;
610 m_locals
[id
].written
= true;
611 m_locals
[id
].unsafe
= false;
614 void FrameState::refineLocalValue(uint32_t id
, SSATmp
* oldVal
, SSATmp
* newVal
) {
615 always_assert(id
< m_locals
.size());
616 auto& local
= m_locals
[id
];
617 local
.value
= newVal
;
618 local
.type
= newVal
->type();
621 void FrameState::refineLocalType(uint32_t id
, Type type
) {
622 always_assert(id
< m_locals
.size());
623 auto& local
= m_locals
[id
];
624 assert((type
.maybeBoxed() && local
.type
.maybeBoxed()) ||
625 type
<= m_locals
[id
].type
);
629 void FrameState::setLocalType(uint32_t id
, Type type
) {
630 always_assert(id
< m_locals
.size());
631 m_locals
[id
].value
= nullptr;
632 m_locals
[id
].type
= type
;
633 m_locals
[id
].written
= true;
634 m_locals
[id
].unsafe
= false;
638 * Get a reference to the LocalVec from an inline index. 0 means the current
639 * frame, otherwise it's index (inlineIdx - 1) in m_inlineSavedStates.
641 FrameState::LocalVec
& FrameState::locals(unsigned inlineIdx
) {
642 if (inlineIdx
== 0) {
646 assert(inlineIdx
< m_inlineSavedStates
.size());
647 return m_inlineSavedStates
[inlineIdx
].locals
;
651 void FrameState::killLocalForCall(uint32_t id
, unsigned inlineIdx
,
653 auto& locs
= locals(inlineIdx
);
654 always_assert(id
< locs
.size());
655 locs
[id
].unsafe
= true;
658 void FrameState::updateLocalRefValue(uint32_t id
, unsigned inlineIdx
,
659 SSATmp
* oldRef
, SSATmp
* newRef
) {
660 auto& local
= locals(inlineIdx
)[id
];
661 assert(!local
.unsafe
);
662 assert(local
.value
== oldRef
);
663 local
.value
= newRef
;
664 local
.type
= newRef
->type();
667 void FrameState::dropLocalInnerType(uint32_t id
, unsigned inlineIdx
) {
668 auto& local
= locals(inlineIdx
)[id
];
669 assert(local
.type
.isBoxed());
670 local
.type
= Type::BoxedInitCell
;
673 std::string
show(const FrameState
& state
) {
674 return folly::format("func: {}, bcOff: {}, spOff: {}{}{}",
675 state
.func()->fullName()->data(),
676 state
.marker().bcOff
,
678 state
.thisAvailable() ? ", thisAvailable" : "",
679 state
.frameSpansCall() ? ", frameSpansCall" : ""