Remove preOptimize step from hphpc
[hiphop-php.git] / hphp / php7 / cfg.cpp
blobf1851bc39545470de3a03149d8fb86bb162a7551
1 /*
2 +----------------------------------------------------------------------+
3 | HipHop for PHP |
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 {
26 using namespace bc;
28 CFG::CFG(Bytecode bc)
29 : m_entry(makeBlock())
30 , m_continuation(m_entry) {
31 then(bc);
34 CFG::CFG(std::initializer_list<Bytecode> list)
35 : m_entry(makeBlock())
36 , m_continuation(m_entry) {
37 for (const auto& bc : list) {
38 then(bc);
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();
51 blk->id = m_maxId++;
52 return blk;
55 void CFG::merge(CFG cfg) {
56 for (auto& blk : cfg.m_blocks) {
57 blk->id += m_maxId;
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});
75 continue;
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));
94 return self();
96 m_continuation->exit(Jmp{cfg.m_entry});
97 m_continuation = cfg.m_continuation;
98 merge(std::move(cfg));
99 return self();
102 CFG&& CFG::then(const std::string& label) {
103 return then(CFG(LabelTarget{label}));
106 CFG&& CFG::thenJmp(Block* target) {
107 if (!m_continuation) {
108 return self();
111 m_continuation->exit(Jmp{target});
112 m_continuation = nullptr;
113 return self();
116 CFG&& CFG::thenExitRaw(ExitOp eo) {
117 if (!m_continuation) {
118 return self();
121 m_continuation->exit(eo);
122 return self();
125 CFG&& CFG::then(Bytecode bc) {
126 if (!m_continuation) {
127 return self();
130 if (m_continuation->exited) {
131 auto next = makeBlock();
132 next->emit(bc);
133 thenJmp(next);
134 return continueFrom(next);
135 } else {
136 m_continuation->emit(bc);
139 return self();
142 CFG&& CFG::branchZ(CFG cfg) {
143 thenExitRaw(JmpZ{cfg.m_entry});
144 merge(std::move(cfg));
145 return self();
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));
154 return self();
156 CFG&& CFG::branchNZ(const std::string& label) {
157 return branchNZ(CFG(LabelTarget{label}));
160 CFG&& CFG::continueFrom(Block* blk) {
161 m_continuation = blk;
162 return self();
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;
173 return self();
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}}) {
205 return dest;
207 return nullptr;
210 return self();
213 CFG&& CFG::strip(const std::string& name) {
214 m_labels.erase(name);
215 return self();
218 CFG&& CFG::replace(const std::string& label, CFG cfg) {
219 link(label, cfg.m_entry);
220 strip(label);
221 merge(std::move(cfg));
222 return self();
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) {
233 case Cell:
234 trampoline->exit(RetC{});
235 break;
236 case Ref:
237 trampoline->exit(RetV{});
238 break;
239 default:
240 panic("bad return flavor");
243 [&](const LoopTarget& loopTarget) {
244 switch(loopTarget) {
245 case Break:
246 throw LanguageException(
247 "'break' not in the 'loop' or 'switch' context"
249 case Continue:
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();
262 return self();
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) {
269 case Break:
270 return breakTarget.m_entry;
271 case Continue:
272 return continueTarget.m_entry;
275 return nullptr;
278 merge(std::move(breakTarget));
279 merge(std::move(continueTarget));
281 return self();
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();
291 merge(handler
292 .thenJmp(cont)
293 .inRegion(std::make_unique<Region>(Region::Kind::Catch)));
294 thenJmp(cont);
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;
320 auto idx = 0;
321 UniqueLocal exitCode;
323 // there's one exit for exceptions, which corresponds to an entry from catch
324 UniqueLocal exnLocal;
325 addExnHandler(CFG({
326 SetL{exnLocal},
327 PopC{},
328 Int{idx++},
329 SetL{exitCode},
330 PopC{}
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;
339 CFG muxExit;
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) {
345 UniqueLocal tmp;
346 switch (ret.flavor) {
347 case Cell:
348 trampoline->emit(SetL{tmp});
349 trampoline->emit(PopC{});
350 muxExit.then(CGetL{tmp});
351 break;
352 case Ref:
353 trampoline->emit(BindL{tmp});
354 trampoline->emit(PopV{});
355 muxExit.then(VGetL{tmp});
356 break;
357 default:
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));
385 then(Int{idx++});
386 then(SetL{exitCode});
387 then(PopC{});
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) {
400 if (!blk->region) {
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));
411 return self();
414 namespace {
416 /* Find all blocks this exit can target */
417 std::vector<Block*> exitOpTargets(const ExitOp& exit) {
418 std::vector<Block*> targets;
420 match<void>(exit,
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*/) {}
442 return targets;
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);
459 next = next->parent;
462 std::reverse(entered.begin(), entered.end());
464 return entered;
467 } // namespace
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(),
483 [&](Block* blk) {
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;
500 break;
501 case Region::Kind::Catch:
502 visitor.endRegion();
503 region = region->parent;
504 break;
505 case Region::Kind::Entry:
506 region = region->parent;
507 break;
509 continue;
512 auto blk = *iter;
513 if (visited.count(blk)) {
514 finished.insert(blk);
515 breadcrumbs.erase(iter);
516 continue;
519 // if we enter regions, make sure to let the visitor know
520 for (const auto& reg : enteredRegions(region, blk->region)) {
521 switch (reg->kind) {
522 case Region::Kind::Protected:
523 visitor.beginTry();
524 break;
525 case Region::Kind::Catch:
526 case Region::Kind::Entry:
527 break;
531 region = blk->region;
532 visitor.block(blk);
533 visited.insert(blk);
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);
545 } else {
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);
557 allTargets.insert(
558 allTargets.end(),
559 targets.begin(),
560 targets.end()
563 return allTargets;
566 }} // namespace HPHP::php7