2 +----------------------------------------------------------------------+
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 +----------------------------------------------------------------------+
17 #include "hphp/runtime/vm/jit/ir-builder.h"
21 #include <folly/ScopeGuard.h>
23 #include "hphp/util/trace.h"
24 #include "hphp/runtime/vm/jit/ir-unit.h"
25 #include "hphp/runtime/vm/jit/guard-relaxation.h"
26 #include "hphp/runtime/vm/jit/mutation.h"
27 #include "hphp/runtime/vm/jit/timer.h"
28 #include "hphp/runtime/vm/jit/translator.h"
29 #include "hphp/runtime/vm/jit/print.h"
30 #include "hphp/runtime/vm/jit/punt.h"
31 #include "hphp/runtime/base/rds.h"
32 #include "hphp/runtime/vm/jit/analysis.h"
33 #include "hphp/util/assertions.h"
35 namespace HPHP
{ namespace jit
{
42 //////////////////////////////////////////////////////////////////////
45 const typename
M::mapped_type
& get_required(const M
& m
,
46 typename
M::key_type key
) {
47 auto it
= m
.find(key
);
48 always_assert(it
!= m
.end());
52 SSATmp
* fwdGuardSource(IRInstruction
* inst
) {
53 if (inst
->is(AssertType
, CheckType
)) return inst
->src(0);
55 assert(inst
->is(AssertLoc
, CheckLoc
, AssertStk
, CheckStk
));
60 //////////////////////////////////////////////////////////////////////
64 IRBuilder::IRBuilder(IRUnit
& unit
, BCMarker initMarker
)
66 , m_initialMarker(initMarker
)
67 , m_curMarker(initMarker
)
69 , m_curBlock(m_unit
.entry())
70 , m_constrainGuards(shouldHHIRRelaxGuards())
72 m_state
.setBuilding();
73 if (RuntimeOption::EvalHHIRGenOpts
) {
74 m_enableCse
= false; // CSE is disabled at gen time.
75 m_enableSimplification
= RuntimeOption::EvalHHIRSimplification
;
80 * Returns whether or not the given value might have its type relaxed by guard
81 * relaxation. If tmp is null, only conditions that apply to all values are
84 bool IRBuilder::typeMightRelax(SSATmp
* tmp
/* = nullptr */) const {
85 return shouldConstrainGuards() && jit::typeMightRelax(tmp
);
88 void IRBuilder::appendInstruction(IRInstruction
* inst
) {
89 FTRACE(1, " append {}\n", inst
->toString());
91 if (shouldConstrainGuards()) {
92 // If we're constraining guards, some instructions need certain information
93 // to be recorded in side tables.
94 if (inst
->is(AssertLoc
, CheckLoc
, LdLoc
)) {
95 auto const locId
= inst
->extra
<LocalId
>()->locId
;
96 m_constraints
.typeSrcs
[inst
] = localTypeSources(locId
);
97 if (inst
->is(AssertLoc
, CheckLoc
)) {
98 m_constraints
.prevTypes
[inst
] = localType(locId
, DataTypeGeneric
);
101 if (inst
->is(AssertStk
, CheckStk
, LdStk
)) {
102 auto const offset
= inst
->extra
<IRSPOffsetData
>()->offset
;
103 m_constraints
.typeSrcs
[inst
] = stackTypeSources(offset
);
104 if (inst
->is(AssertStk
, CheckStk
)) {
105 m_constraints
.prevTypes
[inst
] = stackType(offset
, DataTypeGeneric
);
109 // And a LdRef or CheckRefInner automatically constrains the value to be a
110 // boxed cell, specifically.
111 if (inst
->is(LdRef
, CheckRefInner
)) {
112 constrainValue(inst
->src(0), DataTypeSpecific
);
115 // In psuedomains we have to pre-constrain local guards, because we don't
116 // ever actually generate code that will constrain them otherwise.
117 // (Because of the LdLocPseudoMain stuff.)
118 if (inst
->marker().func()->isPseudoMain() &&
119 inst
->is(GuardLoc
, CheckLoc
)) {
120 constrainGuard(inst
, DataTypeSpecific
);
124 auto where
= m_curBlock
->end();
126 // If the block isn't empty, check if we need to create a new block.
127 if (where
!= m_curBlock
->begin()) {
130 auto& prev
= *prevIt
;
132 if (prev
.isBlockEnd()) {
133 assert(where
== m_curBlock
->end());
135 auto oldBlock
= m_curBlock
;
137 // First make the inst's next block, so we can save state to it in
139 m_curBlock
= m_unit
.defBlock();
140 if (!prev
.isTerminal()) {
141 // New block is reachable from old block so link it.
142 prev
.setNext(m_curBlock
);
143 m_curBlock
->setHint(prev
.block()->hint());
146 m_state
.finishBlock(oldBlock
);
148 m_state
.startBlock(m_curBlock
, inst
->marker());
149 where
= m_curBlock
->begin();
151 FTRACE(2, "lazily adding B{}\n", m_curBlock
->id());
156 assert(IMPLIES(inst
->isBlockEnd(), where
== m_curBlock
->end()) &&
157 "Can't insert a BlockEnd instruction in the middle of a block");
158 if (do_assert
&& where
!= m_curBlock
->begin()) {
159 UNUSED
auto prevIt
= where
;
161 assert(!prevIt
->isBlockEnd() &&
162 "Can't append an instruction after a BlockEnd instruction");
165 assert(inst
->marker().valid());
166 if (!inst
->is(Nop
, DefConst
)) {
167 where
= m_curBlock
->insert(where
, inst
);
171 m_state
.update(inst
);
174 if (inst
->isTerminal()) m_state
.finishBlock(m_curBlock
);
177 void IRBuilder::appendBlock(Block
* block
) {
178 m_state
.finishBlock(m_curBlock
);
180 FTRACE(2, "appending B{}\n", block
->id());
181 // Load up the state for the new block.
182 m_state
.startBlock(block
, m_curMarker
);
186 void IRBuilder::setGuardFailBlock(Block
* block
) {
187 m_guardFailBlock
= block
;
190 void IRBuilder::resetGuardFailBlock() {
191 m_guardFailBlock
= nullptr;
194 Block
* IRBuilder::guardFailBlock() const {
195 return m_guardFailBlock
;
198 //////////////////////////////////////////////////////////////////////
200 SSATmp
* IRBuilder::preOptimizeCheckTypeOp(IRInstruction
* inst
, Type oldType
) {
201 auto const typeParam
= inst
->typeParam();
203 if (!oldType
.maybe(typeParam
)) {
204 /* This check will always fail. It's probably due to an incorrect
205 * prediction. Generate a Jmp and return the src. The fact that the type
206 * will be slightly off is ok because all the code after the Jmp is
208 gen(Jmp
, inst
->taken());
209 return fwdGuardSource(inst
);
212 auto const newType
= oldType
& inst
->typeParam();
214 if (oldType
<= newType
) {
215 /* The type of the src is the same or more refined than type, so the guard
217 return fwdGuardSource(inst
);
223 SSATmp
* IRBuilder::preOptimizeCheckType(IRInstruction
* inst
) {
224 return preOptimizeCheckTypeOp(inst
, inst
->src(0)->type());
227 SSATmp
* IRBuilder::preOptimizeCheckStk(IRInstruction
* inst
) {
228 auto const offset
= inst
->extra
<CheckStk
>()->offset
;
230 if (auto const prevValue
= stackValue(offset
, DataTypeGeneric
)) {
231 gen(CheckType
, inst
->typeParam(), inst
->taken(), prevValue
);
232 inst
->convertToNop();
236 return preOptimizeCheckTypeOp(
238 stackType(offset
, DataTypeGeneric
)
242 SSATmp
* IRBuilder::preOptimizeCheckLoc(IRInstruction
* inst
) {
243 auto const locId
= inst
->extra
<CheckLoc
>()->locId
;
245 if (auto const prevValue
= localValue(locId
, DataTypeGeneric
)) {
246 gen(CheckType
, inst
->typeParam(), inst
->taken(), prevValue
);
247 inst
->convertToNop();
251 return preOptimizeCheckTypeOp(
253 localType(locId
, DataTypeGeneric
)
257 SSATmp
* IRBuilder::preOptimizeHintLocInner(IRInstruction
* inst
) {
258 auto const locId
= inst
->extra
<HintLocInner
>()->locId
;
259 if (!(localType(locId
, DataTypeGeneric
) <= Type::BoxedCell
) ||
260 predictedInnerType(locId
).box() <= inst
->typeParam()) {
261 inst
->convertToNop();
267 SSATmp
* IRBuilder::preOptimizeAssertTypeOp(IRInstruction
* inst
,
270 const IRInstruction
* typeSrc
) {
271 ITRACE(3, "preOptimizeAssertTypeOp({}, {}, {}, {})\n",
273 oldVal
? oldVal
->toString() : "nullptr",
274 typeSrc
? typeSrc
->toString() : "nullptr");
275 auto const typeParam
= inst
->typeParam();
277 if (!oldType
.maybe(typeParam
)) {
278 // If both types are boxed this is ok and even expected as a means to
279 // update the hint for the inner type.
280 if (oldType
<= Type::BoxedCell
&&
281 typeParam
<= Type::BoxedCell
) {
285 // We got external information (probably from static analysis) that
286 // conflicts with what we've built up so far. There's no reasonable way to
287 // continue here: we can't properly fatal the request because we can't make
288 // a catch trace or SpillStack without HhbcTranslator, we can't punt on
289 // just this instruction because we might not be in the initial translation
290 // phase, and we can't just plow on forward since we'll probably generate
291 // malformed IR. Since this case is very rare, just punt on the whole trace
292 // so it gets interpreted.
293 TRACE_PUNT("Invalid AssertTypeOp");
296 // Asserting in these situations doesn't add any information.
297 if (typeParam
== Type::Cls
&& oldType
<= Type::Cls
) return inst
->src(0);
298 if (typeParam
== Type::Gen
&& oldType
<= Type::Gen
) return inst
->src(0);
300 auto const newType
= oldType
& typeParam
;
302 if (oldType
<= newType
) {
303 // oldType is at least as good as the new type. Eliminate this
304 // AssertTypeOp, but only if the src type won't relax, or the source value
305 // is another assert that's good enough. We do this to avoid eliminating
306 // apparently redundant assert opcodes that may become useful after prior
307 // guards are relaxed.
308 if (!typeMightRelax(oldVal
) ||
309 (typeSrc
&& typeSrc
->is(AssertType
, AssertLoc
, AssertStk
) &&
310 typeSrc
->typeParam() <= inst
->typeParam())) {
311 return fwdGuardSource(inst
);
314 if (oldType
< newType
) {
315 // This can happen because of limitations in how Type::operator& (used in
316 // refinedType()) handles specialized types: sometimes it returns a Type
317 // that's wider than it could be. It shouldn't affect correctness but it
318 // can cause us to miss out on some perf.
319 ITRACE(1, "Suboptimal AssertTypeOp: refineType({}, {}) -> {} in {}\n",
320 oldType
, typeParam
, newType
, *inst
);
322 // We don't currently support intersecting RepoAuthType::Arrays
323 // (t4473238), so we might be here because oldType and typeParam have
324 // different RATArrays. If that's the case and typeParam provides no
325 // other useful information we can unconditionally eliminate this
326 // instruction: RATArrays never come from guards so we can't miss out on
327 // anything by doing so.
328 if (oldType
< Type::Arr
&&
329 oldType
.arrSpec().type() &&
330 typeParam
< Type::Arr
&&
331 typeParam
.arrSpec().type() &&
332 !typeParam
.arrSpec().kind()) {
333 return fwdGuardSource(inst
);
341 SSATmp
* IRBuilder::preOptimizeAssertType(IRInstruction
* inst
) {
342 auto const src
= inst
->src(0);
343 return preOptimizeAssertTypeOp(inst
, src
->type(), src
, src
->inst());
346 static const IRInstruction
* singleTypeSrcInst(const TypeSourceSet
& typeSrcs
) {
347 if (typeSrcs
.size() == 1) {
348 auto typeSrc
= *typeSrcs
.begin();
349 return typeSrc
.isValue() ? typeSrc
.value
->inst() :
350 typeSrc
.isGuard() ? typeSrc
.guard
:
356 // TODO(#5868904): almost the same as AssertLoc now; combine
357 SSATmp
* IRBuilder::preOptimizeAssertStk(IRInstruction
* inst
) {
358 auto const offset
= inst
->extra
<AssertStk
>()->offset
;
360 if (auto const prevValue
= stackValue(offset
, DataTypeGeneric
)) {
361 gen(AssertType
, inst
->typeParam(), prevValue
);
362 inst
->convertToNop();
366 // If the value has a single type-source instruction, pass it along to
367 // preOptimizeAssertTypeOp, which may be able to use it to optimize away the
369 auto const typeSrcInst
= singleTypeSrcInst(stackTypeSources(offset
));
371 return preOptimizeAssertTypeOp(
373 stackType(offset
, DataTypeGeneric
),
374 stackValue(offset
, DataTypeGeneric
),
379 SSATmp
* IRBuilder::preOptimizeAssertLoc(IRInstruction
* inst
) {
380 auto const locId
= inst
->extra
<AssertLoc
>()->locId
;
382 if (auto const prevValue
= localValue(locId
, DataTypeGeneric
)) {
383 gen(AssertType
, inst
->typeParam(), prevValue
);
384 inst
->convertToNop();
388 // If the local has a single type-source instruction, pass it along
389 // to preOptimizeAssertTypeOp, which may be able to use it to
390 // optimize away the AssertLoc.
391 auto const typeSrcInst
= singleTypeSrcInst(localTypeSources(locId
));
393 return preOptimizeAssertTypeOp(
395 localType(locId
, DataTypeGeneric
),
396 localValue(locId
, DataTypeGeneric
),
401 SSATmp
* IRBuilder::preOptimizeCheckCtxThis(IRInstruction
* inst
) {
402 if (m_state
.thisAvailable()) inst
->convertToNop();
406 SSATmp
* IRBuilder::preOptimizeLdCtx(IRInstruction
* inst
) {
407 auto const fpInst
= inst
->src(0)->inst();
409 // Change LdCtx in static functions to LdCctx, or if we're inlining try to
410 // fish out a constant context.
411 auto const func
= inst
->marker().func();
412 if (func
->isStatic()) {
413 if (fpInst
->is(DefInlineFP
)) {
414 auto const ctx
= fpInst
->extra
<DefInlineFP
>()->ctx
;
415 if (ctx
->isConst(Type::Cls
)) {
416 inst
->convertToNop();
417 return m_unit
.cns(ConstCctx::cctx(ctx
->clsVal()));
421 // ActRec->m_cls of a static function is always a valid class pointer with
422 // the bottom bit set
423 auto const src
= inst
->src(0);
424 inst
->convertToNop();
425 return gen(LdCctx
, src
);
428 if (fpInst
->is(DefInlineFP
)) {
429 // TODO(#5623596): this optimization required for correctness in refcount
431 // check that we haven't nuked the SSATmp
432 if (!m_state
.frameMaySpanCall()) {
433 auto const ctx
= fpInst
->extra
<DefInlineFP
>()->ctx
;
434 if (ctx
->isA(Type::Obj
)) return ctx
;
440 SSATmp
* IRBuilder::preOptimizeDecRefThis(IRInstruction
* inst
) {
442 * If $this is available, convert to an instruction sequence that doesn't
443 * need to test $this is available. (Hopefully we CSE the load, too.)
445 if (thisAvailable()) {
446 auto const ctx
= gen(LdCtx
, m_state
.fp());
447 auto const thiss
= gen(CastCtxThis
, ctx
);
449 inst
->convertToNop();
455 SSATmp
* IRBuilder::preOptimizeLdLoc(IRInstruction
* inst
) {
456 auto const locId
= inst
->extra
<LdLoc
>()->locId
;
457 if (auto tmp
= localValue(locId
, DataTypeGeneric
)) return tmp
;
459 auto const type
= localType(locId
, DataTypeGeneric
);
461 // The types may not be compatible in the presence of unreachable code.
462 // Unreachable code elimination will take care of it later.
463 if (!type
.maybe(inst
->typeParam())) {
464 inst
->setTypeParam(Type::Bottom
);
467 // If FrameStateMgr's type isn't as good as the type param, we're missing
468 // information in the IR.
469 assert(inst
->typeParam() >= type
);
470 inst
->setTypeParam(std::min(type
, inst
->typeParam()));
472 if (typeMightRelax()) return nullptr;
473 if (inst
->typeParam().isConst()) {
474 return m_unit
.cns(inst
->typeParam());
480 SSATmp
* IRBuilder::preOptimizeStLoc(IRInstruction
* inst
) {
481 // Guard relaxation might change the current local type, so don't try to
482 // change to StLocNT until after relaxation happens.
483 if (typeMightRelax()) return nullptr;
485 auto locId
= inst
->extra
<StLoc
>()->locId
;
486 auto const curType
= localType(locId
, DataTypeGeneric
);
487 auto const newType
= inst
->src(1)->type();
490 * There's no need to store the type if it's going to be the same
491 * KindOfFoo. We'll still have to store string types because we
492 * aren't specific about storing KindOfStaticString
493 * vs. KindOfString, and a Type::Null might mean KindOfUninit or
496 auto const bothBoxed
= curType
<= Type::BoxedCell
&&
497 newType
<= Type::BoxedCell
;
498 auto const sameUnboxed
= [&] {
499 auto avoidable
= { Type::Uninit
,
508 for (auto t
: avoidable
) {
509 if (curType
<= t
&& newType
<= t
) return true;
513 if (bothBoxed
|| sameUnboxed()) {
514 inst
->setOpcode(StLocNT
);
520 SSATmp
* IRBuilder::preOptimizeCastStk(IRInstruction
* inst
) {
521 auto const curType
= stackType(
522 inst
->extra
<CastStk
>()->offset
,
525 auto const curVal
= stackValue(
526 inst
->extra
<CastStk
>()->offset
,
529 if (typeMightRelax(curVal
)) return nullptr;
530 if (inst
->typeParam() == Type::NullableObj
&& curType
<= Type::Null
) {
531 // If we're casting Null to NullableObj, we still need to call
532 // tvCastToNullableObjectInPlace. See comment there and t3879280 for
536 if (curType
<= inst
->typeParam()) {
537 inst
->convertToNop();
543 SSATmp
* IRBuilder::preOptimizeCoerceStk(IRInstruction
* inst
) {
544 auto const curType
= stackType(
545 inst
->extra
<CoerceStk
>()->offset
,
548 auto const curVal
= stackValue(
549 inst
->extra
<CoerceStk
>()->offset
,
552 if (typeMightRelax(curVal
)) return nullptr;
553 if (curType
<= inst
->typeParam()) {
554 inst
->convertToNop();
560 SSATmp
* IRBuilder::preOptimizeLdStk(IRInstruction
* inst
) {
561 auto const offset
= inst
->extra
<LdStk
>()->offset
;
562 if (auto tmp
= stackValue(offset
, DataTypeGeneric
)) {
566 // The types may not be compatible in the presence of unreachable code.
567 // Don't try to optimize the code in this case, and just let
568 // unreachable code elimination take care of it later.
569 auto const type
= stackType(offset
, DataTypeGeneric
);
570 if (!type
.maybe(inst
->typeParam())) return nullptr;
571 inst
->setTypeParam(std::min(type
, inst
->typeParam()));
573 if (typeMightRelax()) return nullptr;
574 if (inst
->typeParam().isConst()) {
575 return m_unit
.cns(inst
->typeParam());
581 SSATmp
* IRBuilder::preOptimize(IRInstruction
* inst
) {
582 #define X(op) case op: return preOptimize##op(inst);
583 switch (inst
->op()) {
605 //////////////////////////////////////////////////////////////////////
608 * Performs simplification and CSE on the input instruction. If the input
609 * instruction has a dest, this will return an SSATmp that represents the same
610 * value as dst(0) of the input instruction. If the input instruction has no
611 * dest, this will return nullptr.
613 * The caller never needs to clone or append; all this has been done.
615 SSATmp
* IRBuilder::optimizeInst(IRInstruction
* inst
,
618 const folly::Optional
<IdomVector
>& idoms
) {
619 static DEBUG_ONLY __thread
int instNest
= 0;
620 if (debug
) ++instNest
;
621 SCOPE_EXIT
{ if (debug
) --instNest
; };
622 DEBUG_ONLY
auto indent
= [&] { return std::string(instNest
* 2, ' '); };
624 FTRACE(1, "optimize: {}\n", inst
->toString());
626 auto doCse
= [&] (IRInstruction
* cseInput
) -> SSATmp
* {
627 if (m_enableCse
&& cseInput
->canCSE()) {
628 if (auto const cseResult
= cseLookup(*cseInput
, srcBlock
, idoms
)) {
629 // Found a dominating instruction that can be used instead of input
630 FTRACE(1, " {}cse found: {}\n",
631 indent(), cseResult
->inst()->toString());
633 assert(!cseInput
->consumesReferences());
634 if (cseInput
->producesReference(0)) {
635 // Replace with an IncRef
636 FTRACE(1, " {}cse of refcount-producing instruction\n", indent());
637 gen(IncRef
, cseResult
);
645 auto cloneAndAppendOriginal
= [&] () -> SSATmp
* {
646 if (inst
->op() == Nop
) return nullptr;
647 if (auto cseResult
= doCse(inst
)) {
650 if (doClone
== CloneFlag::Yes
) {
651 inst
= m_unit
.clone(inst
);
653 appendInstruction(inst
);
657 // Since some of these optimizations inspect tracked state, we don't
658 // perform any of them on non-main traces.
659 if (m_savedBlocks
.size() > 0) return cloneAndAppendOriginal();
661 // copy propagation on inst source operands
664 // First pass of IRBuilder optimizations try to replace an
665 // instruction based on tracked state before we do anything else.
666 // May mutate the IRInstruction in place (and return nullptr) or
667 // return an SSATmp*.
668 if (auto const preOpt
= preOptimize(inst
)) {
669 FTRACE(1, " {}preOptimize returned: {}\n",
670 indent(), preOpt
->inst()->toString());
673 if (inst
->op() == Nop
) return cloneAndAppendOriginal();
675 if (!m_enableSimplification
) {
676 return cloneAndAppendOriginal();
679 auto const simpResult
= simplify(m_unit
, inst
, shouldConstrainGuards());
681 // These are the possible outputs:
683 // ([], nullptr): no optimization possible. Use original inst.
685 // ([], non-nullptr): passing through a src. Don't CSE.
687 // ([X, ...], Y): throw away input instruction, append 'X, ...' (CSEing
688 // as we go), return Y.
690 if (!simpResult
.instrs
.empty()) {
691 // New instructions were generated. Append the new ones, filtering out Nops.
692 for (auto* newInst
: simpResult
.instrs
) {
693 assert(!newInst
->isTransient());
694 if (newInst
->op() == Nop
) continue;
696 auto cseResult
= doCse(newInst
);
698 appendInstruction(m_unit
.gen(newInst
->dst(), Mov
,
699 newInst
->marker(), cseResult
));
701 appendInstruction(newInst
);
705 return simpResult
.dst
;
708 // No new instructions were generated. Either simplification didn't do
709 // anything, or we're using some other instruction's dst instead of our own.
711 if (simpResult
.dst
) {
712 // We're using some other instruction's output. Don't append anything, and
714 assert(simpResult
.dst
->inst() != inst
);
715 return simpResult
.dst
;
718 // No simplification happened.
719 return cloneAndAppendOriginal();
722 void IRBuilder::prepareForNextHHBC() {
724 syncedSpLevel() + m_state
.evalStack().size() - m_state
.stackDeficit() ==
727 m_exnStack
= ExnStackState
{
729 m_state
.syncedSpLevel(),
730 m_state
.stackDeficit(),
736 void IRBuilder::exceptionStackBoundary() {
738 * If this assert fires, we're trying to put things on the stack in a catch
739 * trace that the unwinder won't be able to see.
742 syncedSpLevel() + m_state
.evalStack().size() - m_state
.stackDeficit() ==
745 m_exnStack
.spOffset
= m_state
.spOffset();
746 m_exnStack
.syncedSpLevel
= m_state
.syncedSpLevel();
747 m_exnStack
.stackDeficit
= m_state
.stackDeficit();
748 m_exnStack
.evalStack
= m_state
.evalStack();
749 m_exnStack
.sp
= m_state
.sp();
753 * reoptimize() runs a trace through a second pass of IRBuilder
754 * optimizations, like this:
757 * move all blocks to a temporary list.
758 * compute immediate dominators.
759 * for each block in trace order:
760 * if we have a snapshot state for this block:
761 * clear cse entries that don't dominate this block.
762 * use snapshot state.
763 * move all instructions to a temporary list.
764 * for each instruction:
765 * optimizeWork - do CSE and simplify again
767 * append existing instruction and update state.
769 * if the instruction has a result, insert a mov from the
770 * simplified tmp to the original tmp and discard the instruction.
771 * if the last conditional branch was turned into a jump, remove the
772 * fall-through edge to the next block.
774 void IRBuilder::reoptimize() {
775 Timer
_t(Timer::optimize_reoptimize
);
776 FTRACE(5, "ReOptimize:vvvvvvvvvvvvvvvvvvvv\n");
777 SCOPE_EXIT
{ FTRACE(5, "ReOptimize:^^^^^^^^^^^^^^^^^^^^\n"); };
778 always_assert(m_savedBlocks
.empty());
780 if (splitCriticalEdges(m_unit
)) {
781 printUnit(6, m_unit
, "after splitting critical edges for reoptimize");
784 m_state
= FrameStateMgr
{m_initialMarker
};
786 m_enableCse
= RuntimeOption::EvalHHIRCse
;
787 m_enableSimplification
= RuntimeOption::EvalHHIRSimplification
;
788 if (!m_enableCse
&& !m_enableSimplification
) return;
789 setConstrainGuards(false);
791 // We need to use fixed-point for loops, otherwise legacy reoptimize will not
792 // handle the CFG's back-edges correctly.
793 auto const use_fixed_point
= RuntimeOption::EvalJitLoops
;
795 auto blocksIds
= rpoSortCfgWithIds(m_unit
);
796 auto const idoms
= findDominators(m_unit
, blocksIds
);
797 boost::dynamic_bitset
<> reachable(m_unit
.numBlocks());
798 reachable
.set(m_unit
.entry()->id());
800 if (use_fixed_point
) {
801 m_state
.computeFixedPoint(blocksIds
);
803 m_state
.setLegacyReoptimize();
806 for (auto block
: blocksIds
.blocks
) {
807 ITRACE(5, "reoptimize entering block: {}\n", block
->id());
810 // Skip block if it's unreachable.
811 if (!reachable
.test(block
->id())) continue;
813 if (use_fixed_point
) {
814 m_state
.loadBlock(block
);
816 m_state
.startBlock(block
, block
->front().marker());
820 auto nextBlock
= block
->next();
821 auto backMarker
= block
->back().marker();
822 auto instructions
= block
->moveInstrs();
823 assert(block
->empty());
824 while (!instructions
.empty()) {
825 auto* inst
= &instructions
.front();
826 instructions
.pop_front();
828 // optimizeWork below may create new instructions, and will use
829 // m_nextMarker to decide where they are. Use the marker from this
831 assert(inst
->marker().valid());
832 setCurMarker(inst
->marker());
834 auto const tmp
= optimizeInst(inst
, CloneFlag::No
, block
, idoms
);
835 SSATmp
* dst
= inst
->dst(0);
838 // The result of optimization has a different destination than the inst.
839 // Generate a mov(tmp->dst) to get result into dst.
840 assert(inst
->op() != DefLabel
);
841 assert(block
->empty() || !block
->back().isBlockEnd() || inst
->next());
842 auto src
= tmp
->inst()->is(Mov
) ? tmp
->inst()->src(0) : tmp
;
844 // If the last instruction is a guard, insert the mov on the
845 // fall-through edge (inst->next()).
846 auto nextBlk
= inst
->next();
847 nextBlk
->insert(nextBlk
->begin(),
848 m_unit
.gen(dst
, Mov
, inst
->marker(), src
));
850 appendInstruction(m_unit
.gen(dst
, Mov
, inst
->marker(), src
));
854 if (inst
->block() == nullptr && inst
->isBlockEnd()) {
855 // We're not re-adding the block-end instruction. Unset its edges.
856 inst
->setTaken(nullptr);
857 inst
->setNext(nullptr);
861 if (block
->empty() || !block
->back().isBlockEnd()) {
862 // Our block-end instruction was eliminated (most likely a Jmp* converted
863 // to a nop). Replace it with a jump to the next block.
864 appendInstruction(m_unit
.gen(Jmp
, backMarker
, nextBlock
));
866 assert(block
->back().isBlockEnd());
867 if (!block
->back().isTerminal() && !block
->next()) {
868 // We converted the block-end instruction to a different one.
869 // Set its next block appropriately.
870 block
->back().setNext(nextBlock
);
872 // Mark successor blocks as reachable.
873 if (block
->back().next()) reachable
.set(block
->back().next()->id());
874 if (block
->back().taken()) reachable
.set(block
->back().taken()->id());
875 if (!use_fixed_point
) {
876 m_state
.finishBlock(block
);
882 * Returns true iff a guard to constrain was found, and tc was more specific
883 * than the guard's existing constraint. Note that this doesn't necessarily
884 * mean that the guard was constrained: tc.weak might be true.
886 bool IRBuilder::constrainGuard(const IRInstruction
* inst
, TypeConstraint tc
) {
887 if (!shouldConstrainGuards()) return false;
889 auto& guard
= m_constraints
.guards
[inst
];
890 auto newTc
= applyConstraint(guard
, tc
);
891 ITRACE(2, "constrainGuard({}, {}): {} -> {}\n", *inst
, tc
, guard
, newTc
);
894 auto const changed
= guard
!= newTc
;
895 if (!tc
.weak
) guard
= newTc
;
901 * Trace back to the guard that provided the type of val, if
902 * any. Constrain it so its type will not be relaxed beyond the given
903 * DataTypeCategory. Returns true iff one or more guard instructions
906 bool IRBuilder::constrainValue(SSATmp
* const val
, TypeConstraint tc
) {
907 if (!shouldConstrainGuards() || tc
.empty()) return false;
910 ITRACE(1, "constrainValue(nullptr, {}), bailing\n", tc
);
914 ITRACE(1, "constrainValue({}, {})\n", *val
->inst(), tc
);
917 auto inst
= val
->inst();
918 if (inst
->is(LdLoc
, LdStk
)) {
919 // If the value's type source is non-null and not a FramePtr, it's a real
920 // value that was killed by a Call. The value won't be live but it's ok to
921 // use it to track down the guard.
923 always_assert_flog(m_constraints
.typeSrcs
.count(inst
),
924 "No typeSrcs found for {}", *inst
);
926 auto const typeSrcs
= get_required(m_constraints
.typeSrcs
, inst
);
928 bool changed
= false;
929 for (auto typeSrc
: typeSrcs
) {
930 if (typeSrc
.isGuard()) {
931 if (inst
->is(LdLoc
)) {
932 changed
= constrainSlot(inst
->extra
<LdLoc
>()->locId
, typeSrc
,
933 tc
, "constrainValueLoc") || changed
;
935 assert(inst
->is(LdStk
));
936 changed
= constrainSlot(inst
->extra
<LdStk
>()->offset
.offset
, typeSrc
,
937 tc
, "constrainValueStk") || changed
;
940 // Keep chasing down the source of val.
941 assert(typeSrc
.isValue());
942 changed
= constrainValue(typeSrc
.value
, tc
) || changed
;
948 if (inst
->is(AssertType
)) {
949 // Sometimes code in HhbcTranslator asks for a value with DataTypeSpecific
950 // but can tolerate a less specific value. If that happens, there's nothing
952 if (!typeFitsConstraint(val
->type(), tc
)) return false;
954 // If the immutable typeParam fits the constraint, we're done.
955 auto const typeParam
= inst
->typeParam();
956 if (typeFitsConstraint(typeParam
, tc
)) return false;
958 auto const newTc
= relaxConstraint(tc
, typeParam
, inst
->src(0)->type());
959 ITRACE(1, "tracing through {}, orig tc: {}, new tc: {}\n",
961 return constrainValue(inst
->src(0), newTc
);
964 if (inst
->is(CheckType
)) {
965 // Sometimes code in HhbcTranslator asks for a value with DataTypeSpecific
966 // but can tolerate a less specific value. If that happens, there's nothing
968 if (!typeFitsConstraint(val
->type(), tc
)) return false;
970 bool changed
= false;
971 auto const typeParam
= inst
->typeParam();
972 auto const srcType
= inst
->src(0)->type();
974 // Constrain the guard on the CheckType, but first relax the constraint
975 // based on what's known about srcType.
976 auto const guardTc
= relaxConstraint(tc
, srcType
, typeParam
);
977 changed
= constrainGuard(inst
, guardTc
) || changed
;
979 // Relax typeParam with its current constraint. This is used below to
980 // recursively relax the constraint on the source, if needed.
981 auto constraint
= applyConstraint(m_constraints
.guards
[inst
], guardTc
);
982 auto const knownType
= relaxType(typeParam
, constraint
);
984 if (!typeFitsConstraint(knownType
, tc
)) {
985 auto const newTc
= relaxConstraint(tc
, knownType
, srcType
);
986 ITRACE(1, "tracing through {}, orig tc: {}, new tc: {}\n",
988 changed
= constrainValue(inst
->src(0), newTc
) || changed
;
993 if (inst
->isPassthrough()) {
994 return constrainValue(inst
->getPassthroughValue(), tc
);
997 if (inst
->is(DefLabel
)) {
998 auto changed
= false;
1000 for (; dst
< inst
->numDsts(); dst
++) {
1001 if (val
== inst
->dst(dst
)) break;
1003 assert(dst
!= inst
->numDsts());
1004 for (auto& pred
: inst
->block()->preds()) {
1005 assert(pred
.inst()->is(Jmp
));
1006 auto src
= pred
.inst()->src(dst
);
1007 changed
= constrainValue(src
, tc
) || changed
;
1012 // Any instructions not special cased above produce a new value, so
1013 // there's no guard for us to constrain.
1014 ITRACE(2, "value is new in this trace, bailing\n");
1018 bool IRBuilder::constrainLocal(uint32_t locId
,
1020 const std::string
& why
) {
1021 if (!shouldConstrainGuards() || tc
.empty()) return false;
1022 bool changed
= false;
1023 for (auto typeSrc
: localTypeSources(locId
)) {
1024 changed
= constrainSlot(locId
, typeSrc
, tc
, why
+ "Loc") || changed
;
1029 bool IRBuilder::constrainStack(IRSPOffset offset
, TypeConstraint tc
) {
1030 if (!shouldConstrainGuards() || tc
.empty()) return false;
1031 auto changed
= false;
1032 for (auto typeSrc
: stackTypeSources(offset
)) {
1033 changed
= constrainSlot(offset
.offset
, typeSrc
, tc
, "Stk") || changed
;
1038 // Constrains a local or stack slot.
1039 bool IRBuilder::constrainSlot(int32_t idOrOffset
,
1042 const std::string
& why
) {
1043 if (!shouldConstrainGuards() || tc
.empty()) return false;
1045 ITRACE(1, "constrainSlot({}, {}, {}, {})\n",
1046 idOrOffset
, show(typeSrc
), tc
, why
);
1049 if (typeSrc
.isValue()) return constrainValue(typeSrc
.value
, tc
);
1051 assert(typeSrc
.isGuard());
1052 auto const guard
= typeSrc
.guard
;
1054 if (guard
->is(GuardLoc
, GuardStk
)) {
1055 ITRACE(2, "found guard to constrain\n");
1056 return constrainGuard(guard
, tc
);
1059 always_assert(guard
->is(AssertLoc
, CheckLoc
, AssertStk
, CheckStk
));
1061 // If the dest of the Assert/Check doesn't fit tc there's no point in
1063 auto prevType
= get_required(m_constraints
.prevTypes
, guard
);
1064 if (!typeFitsConstraint(prevType
& guard
->typeParam(), tc
)) {
1068 if (guard
->is(AssertLoc
, AssertStk
)) {
1069 // If the immutable typeParam fits the constraint, we're done.
1070 auto const typeParam
= guard
->typeParam();
1071 if (typeFitsConstraint(typeParam
, tc
)) return false;
1073 auto const newTc
= relaxConstraint(tc
, typeParam
, prevType
);
1074 ITRACE(1, "tracing through {}, orig tc: {}, new tc: {}\n",
1076 bool changed
= false;
1077 auto typeSrcs
= get_required(m_constraints
.typeSrcs
, guard
);
1078 for (auto typeSrc
: typeSrcs
) {
1079 changed
= constrainSlot(idOrOffset
, typeSrc
, newTc
, why
) || changed
;
1084 // guard is a CheckLoc or CheckStk.
1085 auto changed
= false;
1086 auto const typeParam
= guard
->typeParam();
1088 // Constrain the guard on the Check instruction, but first relax the
1089 // constraint based on what's known about prevType.
1090 auto const guardTc
= relaxConstraint(tc
, prevType
, typeParam
);
1091 changed
= constrainGuard(guard
, guardTc
) || changed
;
1093 // Relax typeParam with its current constraint. This is used below to
1094 // recursively relax the constraint on the source, if needed.
1095 auto constraint
= applyConstraint(m_constraints
.guards
[guard
], guardTc
);
1096 auto const knownType
= relaxType(typeParam
, constraint
);
1098 if (!typeFitsConstraint(knownType
, tc
)) {
1099 auto const newTc
= relaxConstraint(tc
, knownType
, prevType
);
1100 ITRACE(1, "tracing through {}, orig tc: {}, new tc: {}\n",
1102 auto typeSrcs
= get_required(m_constraints
.typeSrcs
, guard
);
1103 for (auto typeSrc
: typeSrcs
) {
1104 changed
= constrainSlot(idOrOffset
, typeSrc
, newTc
, why
) || changed
;
1110 Type
IRBuilder::localType(uint32_t id
, TypeConstraint tc
) {
1111 constrainLocal(id
, tc
, "localType");
1112 return m_state
.localType(id
);
1115 Type
IRBuilder::predictedInnerType(uint32_t id
) {
1116 auto const ty
= m_state
.predictedLocalType(id
);
1117 assert(ty
<= Type::BoxedCell
);
1118 return ldRefReturn(ty
.unbox());
1121 Type
IRBuilder::stackInnerTypePrediction(IRSPOffset offset
) const {
1122 auto const ty
= m_state
.predictedStackType(offset
);
1123 assert(ty
<= Type::BoxedCell
);
1124 return ldRefReturn(ty
.unbox());
1127 Type
IRBuilder::predictedLocalType(uint32_t id
) {
1128 return m_state
.predictedLocalType(id
);
1131 SSATmp
* IRBuilder::localValue(uint32_t id
, TypeConstraint tc
) {
1132 constrainLocal(id
, tc
, "localValue");
1133 return m_state
.localValue(id
);
1136 SSATmp
* IRBuilder::stackValue(IRSPOffset offset
, TypeConstraint tc
) {
1137 auto const val
= m_state
.stackValue(offset
);
1138 if (val
) constrainValue(val
, tc
);
1142 Type
IRBuilder::stackType(IRSPOffset offset
, TypeConstraint tc
) {
1143 constrainStack(offset
, tc
);
1144 return m_state
.stackType(offset
);
1147 void IRBuilder::setCurMarker(BCMarker newMarker
) {
1148 if (newMarker
== m_curMarker
) return;
1149 FTRACE(2, "IRBuilder changing current marker from {} to {}\n",
1150 m_curMarker
.valid() ? m_curMarker
.show() : "<invalid>",
1152 assert(newMarker
.valid());
1153 m_curMarker
= newMarker
;
1156 bool IRBuilder::startBlock(Block
* block
, const BCMarker
& marker
,
1157 bool isLoopHeader
) {
1159 assert(m_savedBlocks
.empty()); // No bytecode control flow in exits.
1161 if (block
== m_curBlock
) return true;
1163 // Return false if we don't have a state for block. This can happen
1164 // when trying to start a region block that turned out to be unreachable.
1165 if (!m_state
.hasStateFor(block
)) return false;
1167 // There's no reason for us to be starting on the entry block when it's not
1168 // our current block.
1169 always_assert(!block
->isEntry());
1171 auto& lastInst
= m_curBlock
->back();
1172 always_assert(lastInst
.isBlockEnd());
1173 always_assert(lastInst
.isTerminal() || m_curBlock
->next() != nullptr);
1175 m_state
.finishBlock(m_curBlock
);
1178 m_state
.startBlock(m_curBlock
, marker
, isLoopHeader
);
1179 if (sp() == nullptr) gen(DefSP
, StackOffset
{spOffset().offset
}, fp());
1180 always_assert(fp() != nullptr);
1182 FTRACE(2, "IRBuilder switching to block B{}: {}\n", block
->id(),
1187 Block
* IRBuilder::makeBlock(Offset offset
) {
1188 auto it
= m_offsetToBlockMap
.find(offset
);
1189 if (it
== m_offsetToBlockMap
.end()) {
1190 auto* block
= m_unit
.defBlock();
1191 m_offsetToBlockMap
.insert(std::make_pair(offset
, block
));
1197 void IRBuilder::resetOffsetMapping() {
1198 m_offsetToBlockMap
.clear();
1201 bool IRBuilder::hasBlock(Offset offset
) const {
1202 return m_offsetToBlockMap
.count(offset
);
1205 void IRBuilder::setBlock(Offset offset
, Block
* block
) {
1206 assert(!hasBlock(offset
));
1207 m_offsetToBlockMap
[offset
] = block
;
1210 void IRBuilder::pushBlock(BCMarker marker
, Block
* b
) {
1211 FTRACE(2, "IRBuilder saving {}@{} and using {}@{}\n",
1212 m_curBlock
, m_curMarker
.show(), b
, marker
.show());
1215 m_savedBlocks
.push_back(
1216 BlockState
{ m_curBlock
, m_curMarker
, m_exnStack
}
1218 m_state
.pauseBlock(m_curBlock
);
1219 m_state
.startBlock(b
, marker
);
1221 m_curMarker
= marker
;
1224 for (UNUSED
auto const& state
: m_savedBlocks
) {
1225 assert(state
.block
!= b
&&
1226 "Can't push a block that's already in the saved stack");
1231 void IRBuilder::popBlock() {
1232 assert(!m_savedBlocks
.empty());
1234 auto const& top
= m_savedBlocks
.back();
1235 FTRACE(2, "IRBuilder popping {}@{} to restore {}@{}\n",
1236 m_curBlock
, m_curMarker
.show(), top
.block
, top
.marker
.show());
1237 m_state
.finishBlock(m_curBlock
);
1238 m_state
.unpauseBlock(top
.block
);
1239 m_curBlock
= top
.block
;
1240 m_curMarker
= top
.marker
;
1241 m_exnStack
= top
.exnStack
;
1242 m_savedBlocks
.pop_back();
1245 //////////////////////////////////////////////////////////////////////
1247 CSEHash
& IRBuilder::cseHashTable(const IRInstruction
& inst
) {
1248 return inst
.is(DefConst
) ? m_unit
.constTable() : m_cseHash
;
1251 const CSEHash
& IRBuilder::cseHashTable(const IRInstruction
& inst
) const {
1252 return const_cast<IRBuilder
*>(this)->cseHashTable(inst
);
1255 SSATmp
* IRBuilder::cseLookup(const IRInstruction
& inst
,
1256 const Block
* srcBlock
,
1257 const folly::Optional
<IdomVector
>& idoms
) const {
1258 auto tmp
= cseHashTable(inst
).lookup(const_cast<IRInstruction
*>(&inst
));
1260 // During a reoptimize pass, we need to make sure that any values we want
1261 // to reuse for CSE are only reused in blocks dominated by the block that
1263 if (tmp
->inst()->is(DefConst
)) return tmp
;
1264 auto const dom
= findDefiningBlock(tmp
);
1265 if (!dom
|| !dominates(dom
, srcBlock
, *idoms
)) return nullptr;
1270 void IRBuilder::cseUpdate(const IRInstruction
& inst
) {
1271 switch (inst
.op()) {
1281 if (m_enableCse
&& inst
.canCSE()) {
1282 cseHashTable(inst
).insert(inst
.dst());
1284 if (inst
.killsSources()) {
1285 for (auto i
= uint32_t{0}; i
< inst
.numSrcs(); ++i
) {
1286 if (inst
.killsSource(i
) && inst
.src(i
)->inst()->canCSE()) {
1287 cseHashTable(inst
).erase(inst
.src(i
));
1293 //////////////////////////////////////////////////////////////////////