2 +----------------------------------------------------------------------+
4 +----------------------------------------------------------------------+
5 | Copyright (c) 2010- 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/php7/cfg.h"
19 #include "hphp/php7/compiler.h"
20 #include "hphp/util/match.h"
22 #include <boost/variant.hpp>
24 namespace HPHP
{ namespace php7
{
29 : m_entry(makeBlock())
30 , m_continuation(m_entry
) {
34 CFG::CFG(std::initializer_list
<Bytecode
> list
)
35 : m_entry(makeBlock())
36 , m_continuation(m_entry
) {
37 for (const auto& bc
: list
) {
42 CFG::CFG(LinkTarget target
)
43 : m_entry(makeBlock())
44 , m_continuation(nullptr) {
45 m_unresolvedLinks
.push_back({m_entry
, target
});
48 Block
* CFG::makeBlock() {
49 m_blocks
.push_back(std::make_unique
<Block
>());
50 auto blk
= m_blocks
.back().get();
55 void CFG::merge(CFG cfg
) {
56 for (auto& blk
: cfg
.m_blocks
) {
58 m_blocks
.emplace_back(std::move(blk
));
60 // copy defined labels from cfg
61 for (const auto& label
: cfg
.m_labels
) {
62 // if we already had a label with this name, we have a problem!
63 if (m_labels
.count(label
.first
) > 0) {
64 panic("CFG defines duplicate label " + label
.first
);
66 link(label
.first
, label
.second
);
68 // copy unresolved links from cfg
69 for (auto& linkage
: cfg
.m_unresolvedLinks
) {
70 if (auto labelTarget
= boost::get
<LabelTarget
>(&linkage
.target
)) {
71 auto iter
= m_labels
.find(labelTarget
->name
);
73 if (iter
!= m_labels
.end()) {
74 linkage
.trampoline
->exit(Jmp
{iter
->second
});
78 // if we couldn't resolve this link, add it to ours
79 m_unresolvedLinks
.push_back(std::move(linkage
));
82 // add top regions from cfg to ours
83 for (auto& region
: cfg
.m_topRegions
) {
84 m_topRegions
.emplace_back(std::move(region
));
87 m_maxId
+= cfg
.m_maxId
;
90 CFG
&& CFG::then(CFG cfg
) {
91 if (!m_continuation
) {
92 m_continuation
= cfg
.m_continuation
;
93 merge(std::move(cfg
));
96 m_continuation
->exit(Jmp
{cfg
.m_entry
});
97 m_continuation
= cfg
.m_continuation
;
98 merge(std::move(cfg
));
102 CFG
&& CFG::then(const std::string
& label
) {
103 return then(CFG(LabelTarget
{label
}));
106 CFG
&& CFG::thenJmp(Block
* target
) {
107 if (!m_continuation
) {
111 m_continuation
->exit(Jmp
{target
});
112 m_continuation
= nullptr;
116 CFG
&& CFG::thenExitRaw(ExitOp eo
) {
117 if (!m_continuation
) {
121 m_continuation
->exit(eo
);
125 CFG
&& CFG::then(Bytecode bc
) {
126 if (!m_continuation
) {
130 if (m_continuation
->exited
) {
131 auto next
= makeBlock();
134 return continueFrom(next
);
136 m_continuation
->emit(bc
);
142 CFG
&& CFG::branchZ(CFG cfg
) {
143 thenExitRaw(JmpZ
{cfg
.m_entry
});
144 merge(std::move(cfg
));
147 CFG
&& CFG::branchZ(const std::string
& label
) {
148 return branchZ(CFG(LabelTarget
{label
}));
151 CFG
&& CFG::branchNZ(CFG cfg
) {
152 thenExitRaw(JmpNZ
{cfg
.m_entry
});
153 merge(std::move(cfg
));
156 CFG
&& CFG::branchNZ(const std::string
& label
) {
157 return branchNZ(CFG(LabelTarget
{label
}));
160 CFG
&& CFG::continueFrom(Block
* blk
) {
161 m_continuation
= blk
;
165 CFG
&& CFG::switchUnbounded(std::vector
<CFG
> exits
) {
166 std::vector
<Block
*> jmpVector
;
167 for (auto& cfg
: exits
) {
168 jmpVector
.push_back(cfg
.m_entry
);
169 merge(std::move(cfg
));
171 thenExitRaw(Switch
{SwitchKind::Unbounded
, 0, jmpVector
});
172 m_continuation
= nullptr;
176 CFG
&& CFG::then(LinkTarget target
) {
177 return then(CFG(target
));
180 CFG
&& CFG::thenThrow() {
181 return thenExitRaw(Throw
{});
184 CFG
&& CFG::thenReturn(Flavor flavor
) {
185 return then(ReturnTarget
{flavor
});
188 CFG
&& CFG::thenContinue() {
189 return then(LoopTarget::Continue
);
192 CFG
&& CFG::thenBreak() {
193 return then(LoopTarget::Break
);
196 CFG
&& CFG::thenLabel(const std::string
& name
) {
197 return then(LabelTarget
{name
});
200 CFG
&& CFG::link(const std::string
& name
, Block
* dest
) {
201 m_labels
.insert({name
, dest
});
203 resolveLinks([&](Linkage
& link
) -> Block
* {
204 if (link
.target
== LinkTarget
{LabelTarget
{name
}}) {
213 CFG
&& CFG::strip(const std::string
& name
) {
214 m_labels
.erase(name
);
218 CFG
&& CFG::replace(const std::string
& label
, CFG cfg
) {
219 link(label
, cfg
.m_entry
);
221 merge(std::move(cfg
));
225 CFG
&& CFG::makeExitsReal() {
226 // we must avoid creating a new block for any exit since this would change
227 // the region that we, e.g. throw from
228 for (auto& linkage
: m_unresolvedLinks
) {
229 auto trampoline
= linkage
.trampoline
;
230 match
<void>(linkage
.target
,
231 [&](const ReturnTarget
& ret
) {
232 switch (ret
.flavor
) {
234 trampoline
->exit(RetC
{});
237 trampoline
->exit(RetV
{});
240 panic("bad return flavor");
243 [&](const LoopTarget
& loopTarget
) {
246 throw LanguageException(
247 "'break' not in the 'loop' or 'switch' context"
250 throw LanguageException(
251 "'continue' not in the 'loop' or 'switch' context"
254 panic("bad loop target");
256 [&](const LabelTarget
& label
) {
257 panic("unresolved label" + label
.name
);
261 m_unresolvedLinks
.clear();
265 CFG
&& CFG::linkLoop(CFG breakTarget
, CFG continueTarget
) {
266 resolveLinks([&](Linkage
& link
) -> Block
* {
267 if (auto loopTarget
= boost::get
<LoopTarget
>(&link
.target
)) {
268 switch(*loopTarget
) {
270 return breakTarget
.m_entry
;
272 return continueTarget
.m_entry
;
278 merge(std::move(breakTarget
));
279 merge(std::move(continueTarget
));
284 CFG
&& CFG::addExnHandler(CFG handler
) {
285 // create a region and put all our blocks in it
286 auto protRegion
= std::make_unique
<Region
>(Region::Kind::Protected
);
287 protRegion
->handler
= handler
.m_entry
;
288 inRegion(std::move(protRegion
));
290 auto cont
= makeBlock();
293 .inRegion(std::make_unique
<Region
>(Region::Kind::Catch
)));
296 return continueFrom(cont
);
299 /* The idea here is that, since PHP allows pretty arbitrary actions inside a
300 * finally block, since it tracks finally guards at runtime--and HHVM doesn't,
301 * we need to do some pretty crazy gymnastics here to make everything work in
302 * the most general case
304 * We solve this problem by intercepting every exit from the region in the try
305 * and turn them into jumps to the finally guard--before they jump, they set a
306 * local to an integer code--the handler continues to a switch that takes this
307 * code and uses it to resume execution in the correct place
309 * Also worth noting is that we set the guard using a catch handler--*not* a
310 * fault funclet. This is mostly since HHVM doesn't allow returns from a fault
311 * funclet, only throwing a new exception or unwinding further.
313 * It might be worthwhile later to check if there's unusual exits from the
314 * finally guard and/or the try region, and if there aren't, we can get rid of
315 * some of this garbage
317 CFG
&& CFG::addFinallyGuard(CFG guard
) {
318 // these will be the exits from the finally guard's switch
319 std::vector
<CFG
> exits
;
321 UniqueLocal exitCode
;
323 // there's one exit for exceptions, which corresponds to an entry from catch
324 UniqueLocal exnLocal
;
331 }).thenJmp(guard
.m_entry
));
332 exits
.push_back(CFG(CGetL
{exnLocal
}).thenThrow());
334 // every exit from the region is a linkage, so we intercept them all by
335 // creating a new trampoline block that jumps to the finally handler
336 // before exiting in the way it normally would
337 for (auto& linkage
: m_unresolvedLinks
) {
338 auto trampoline
= linkage
.trampoline
;
341 match
<void>(linkage
.target
,
342 // for returns, put the relevant value in a local and restore
343 // it before continuing
344 [&](const ReturnTarget
& ret
) {
346 switch (ret
.flavor
) {
348 trampoline
->emit(SetL
{tmp
});
349 trampoline
->emit(PopC
{});
350 muxExit
.then(CGetL
{tmp
});
353 trampoline
->emit(BindL
{tmp
});
354 trampoline
->emit(PopV
{});
355 muxExit
.then(VGetL
{tmp
});
358 panic("bad return flavor");
360 muxExit
.thenReturn(ret
.flavor
);
362 // for other exits, there's no extra value associated with this exit
363 [&](const LoopTarget
& loopTarget
) { },
364 [&](const LabelTarget
& label
) { }
367 // for all exits, we allocate a code and put this in a local, then jump
368 // to the finally guard
369 trampoline
->emit(Int
{idx
++});
370 trampoline
->emit(SetL
{exitCode
});
371 trampoline
->emit(PopC
{});
372 trampoline
->exit(Jmp
{guard
.m_entry
});
374 // we create a new trampoline block for this linkage and jump to it as one
375 // of the switch exits
376 auto newTrampoline
= makeBlock();
377 exits
.push_back(muxExit
378 .thenJmp(newTrampoline
));
379 linkage
.trampoline
= newTrampoline
;
382 // the last exit simply continues execution
383 Block
* cont
= makeBlock();
384 exits
.push_back(CFG().thenJmp(cont
));
386 then(SetL
{exitCode
});
388 // execute the finally guard
389 then(std::move(guard
));
390 // then switch based on the exit code local
391 then(CGetL
{exitCode
});
392 switchUnbounded(std::move(exits
));
394 return continueFrom(cont
);
397 CFG
&& CFG::inRegion(std::unique_ptr
<Region
> reg
) {
398 // place any blocks without a region in this region
399 for (auto& blk
: m_blocks
) {
401 blk
->region
= reg
.get();
404 // place all top regions in this region
405 for (auto& r
: m_topRegions
) {
406 reg
->addChild(std::move(r
));
408 // the only top region is now reg
409 m_topRegions
.clear();
410 m_topRegions
.push_back(std::move(reg
));
416 /* Find all blocks this exit can target */
417 std::vector
<Block
*> exitOpTargets(const ExitOp
& exit
) {
418 std::vector
<Block
*> targets
;
421 [&](const Jmp
& j
) { targets
.push_back(j
.imm1
); },
422 [&](const JmpNS
& j
) { targets
.push_back(j
.imm1
); },
423 [&](const JmpZ
& j
) { targets
.push_back(j
.imm1
); },
424 [&](const JmpNZ
& j
) { targets
.push_back(j
.imm1
); },
425 [&](const Switch
& s
) {
426 targets
.insert(targets
.end(), s
.imm3
.begin(), s
.imm3
.end());
428 [&](const SSwitch
& s
) {
429 const StringOffsetVector
& sov
= s
.imm1
;
430 for (const auto& pair
: sov
.branches
) {
431 targets
.push_back(pair
.second
);
433 targets
.push_back(sov
.defaultBranch
);
435 [&](const RetC
& /*r*/) {},
436 [&](const RetV
& /*r*/) {},
437 [&](const Unwind
& /*u*/) {},
438 [&](const Throw
& /*t*/) {},
439 [&](const Fatal
& /*t*/) {}
445 /* Compute the regions you have to enter to move from prev to next
447 * E.g if regions are nested like this:
448 * (A (B (C) (D)) (E))
449 * enteredRegions(A, E) -> [E]
450 * enteredRegions(A, D) -> [B, D]
451 * enteredRegions(nullptr, C) -> [A, B, C]
453 * prev may be null, in which case this returns all ancestors of next */
454 std::vector
<Region
*> enteredRegions(Region
* prev
, Region
* next
) {
455 std::vector
<Region
*> entered
;
457 while (next
!= prev
) {
458 entered
.push_back(next
);
462 std::reverse(entered
.begin(), entered
.end());
469 void CFG::visit(CFGVisitor
&& visitor
) const {
470 std::unordered_set
<Block
*> visited
;
471 std::unordered_set
<Block
*> encountered
;
472 std::unordered_set
<Block
*> finished
;
473 std::deque
<Block
*> breadcrumbs
;
475 auto region
= m_entry
->region
;
476 breadcrumbs
.push_front(m_entry
);
477 encountered
.insert(m_entry
);
479 while (region
|| !breadcrumbs
.empty()) {
480 // find the next block in breadcrumbs that is still in the current region
481 // or to the next fault funclet if we're not in any region
482 auto iter
= std::find_if(breadcrumbs
.begin(), breadcrumbs
.end(),
484 return region
->containsBlock(blk
);
487 // our only paths are out of the current region, so leave this region
488 // and enter its catch handler, if it has one
489 if (iter
== breadcrumbs
.end()) {
490 switch (region
->kind
) {
491 case Region::Kind::Protected
:
492 assert(region
->handler
->region
->kind
== Region::Kind::Catch
);
493 assert(region
->handler
->region
->parent
== region
->parent
);
494 visitor
.beginCatch();
495 if (0 == encountered
.count(region
->handler
)) {
496 breadcrumbs
.push_front(region
->handler
);
497 encountered
.insert(region
->handler
);
499 region
= region
->handler
->region
;
501 case Region::Kind::Catch
:
503 region
= region
->parent
;
505 case Region::Kind::Entry
:
506 region
= region
->parent
;
513 if (visited
.count(blk
)) {
514 finished
.insert(blk
);
515 breadcrumbs
.erase(iter
);
519 // if we enter regions, make sure to let the visitor know
520 for (const auto& reg
: enteredRegions(region
, blk
->region
)) {
522 case Region::Kind::Protected
:
525 case Region::Kind::Catch
:
526 case Region::Kind::Entry
:
531 region
= blk
->region
;
535 // add all of the exit targets to the queue
536 const auto& exits
= blk
->exits
;
537 for (auto riter
= exits
.rbegin(); riter
!= exits
.rend(); riter
++) {
538 for (Block
* child
: exitOpTargets(*riter
)) {
539 if (0 == encountered
.count(child
)) {
540 breadcrumbs
.push_front(child
);
541 encountered
.insert(child
);
542 visitor
.tree_edge(blk
, child
);
543 } else if (finished
.count(child
)) {
544 visitor
.edge(blk
, child
);
546 visitor
.back_edge(blk
, child
);
553 std::vector
<Block
*> Block::exitTargets() const {
554 std::vector
<Block
*> allTargets
;
555 for (const auto& exit
: exits
) {
556 auto targets
= exitOpTargets(exit
);
566 }} // namespace HPHP::php7