?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
More fixing lint: various conversion constructors in compiler/
[hiphop-php.git] / hphp / compiler / analysis / alias_manager.cpp
blob1d1de4212a8d48c977cf5b300491187f96f2c59d
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 +----------------------------------------------------------------------+
15 */
16
17 #include <compiler/analysis/analysis_result.h>
18 #include <compiler/analysis/function_scope.h>
19 #include <compiler/expression/expression.h>
20 #include <compiler/expression/assignment_expression.h>
21 #include <compiler/expression/array_element_expression.h>
22 #include <compiler/expression/list_assignment.h>
23 #include <compiler/expression/binary_op_expression.h>
24 #include <compiler/expression/unary_op_expression.h>
25 #include <compiler/expression/qop_expression.h>
26 #include <compiler/expression/simple_variable.h>
27 #include <compiler/expression/scalar_expression.h>
28 #include <compiler/expression/simple_function_call.h>
29 #include <compiler/expression/array_element_expression.h>
30 #include <compiler/expression/object_property_expression.h>
31 #include <compiler/expression/object_method_expression.h>
32 #include <compiler/expression/parameter_expression.h>
33 #include <compiler/expression/expression_list.h>
34 #include <compiler/expression/expression.h>
35 #include <compiler/expression/include_expression.h>
36 #include <compiler/expression/closure_expression.h>
37 #include <compiler/statement/statement.h>
38 #include <compiler/statement/statement_list.h>
39 #include <compiler/statement/catch_statement.h>
40 #include <compiler/statement/method_statement.h>
41 #include <compiler/statement/block_statement.h>
42 #include <compiler/statement/if_statement.h>
43 #include <compiler/statement/if_branch_statement.h>
44 #include <compiler/statement/switch_statement.h>
45 #include <compiler/statement/break_statement.h>
46 #include <compiler/statement/return_statement.h>
47 #include <compiler/statement/loop_statement.h>
48 #include <compiler/statement/foreach_statement.h>
49 #include <compiler/statement/for_statement.h>
50 #include <compiler/statement/while_statement.h>
51 #include <compiler/statement/do_statement.h>
52 #include <compiler/statement/exp_statement.h>
53 #include <compiler/statement/echo_statement.h>
54 #include <compiler/statement/try_statement.h>
55 #include <compiler/statement/global_statement.h>
56 #include <compiler/statement/static_statement.h>
57 #include <compiler/analysis/alias_manager.h>
58 #include <compiler/analysis/control_flow.h>
59 #include <compiler/analysis/variable_table.h>
60 #include <compiler/analysis/data_flow.h>
61 #include <compiler/analysis/dictionary.h>
62 #include <compiler/analysis/expr_dict.h>
63 #include <compiler/analysis/live_dict.h>
64 #include <compiler/analysis/ref_dict.h>
65
66 #include <util/parser/hphp.tab.hpp>
67 #include <util/parser/location.h>
68 #include <util/util.h>
69
70 #define spc(T,p) boost::static_pointer_cast<T>(p)
71 #define dpc(T,p) boost::dynamic_pointer_cast<T>(p)
72
73 using namespace HPHP;
74 using std::string;
75
76 ///////////////////////////////////////////////////////////////////////////////
77
78 AliasManager::AliasManager(int opt) :
79 m_bucketList(0), m_nextID(1), m_changes(0), m_replaced(0),
80 m_wildRefs(false), m_nrvoFix(0), m_inCall(0), m_inlineAsExpr(true),
81 m_noAdd(false), m_preOpt(opt<0), m_postOpt(opt>0),
82 m_cleared(false), m_inPseudoMain(false), m_genAttrs(false),
83 m_hasDeadStore(false), m_hasChainRoot(false),
84 m_hasTypeAssertions(false), m_graph(0), m_exprIdx(-1) {
85 }
86
87 AliasManager::~AliasManager() {
88 delete m_graph;
89 }
90
91 bool AliasManager::parseOptimizations(const std::string &optimizations,
92 std::string &errs)
93 {
94 size_t pos = 0;
95 while ((pos = optimizations.find_first_not_of(" ,", pos)) !=
96 string::npos) {
97 size_t end = optimizations.find_first_of(" ,", pos);
98 string opt = optimizations.substr(pos, end - pos);
99 bool val = true;
100 if (opt.substr(0, 3) == "no-") {
101 val = false;
102 opt = opt.substr(3);
103 }
104
105 if (opt == "deadcode") {
106 Option::EliminateDeadCode = val;
107 } else if (opt == "localcopy") {
108 Option::LocalCopyProp = val;
109 } else if (opt == "copyprop") {
110 Option::CopyProp = val;
111 } else if (opt == "string") {
112 Option::StringLoopOpts = val;
113 } else if (opt == "inline") {
114 Option::AutoInline = val ? 1 : -1;
115 } else if (opt == "cflow") {
116 Option::ControlFlow = val;
117 } else if (opt == "coalesce") {
118 Option::VariableCoalescing = val;
119 } else if (val && (opt == "all" || opt == "none")) {
120 val = opt == "all";
121 Option::EliminateDeadCode = val;
122 Option::LocalCopyProp = val;
123 Option::AutoInline = val ? 1 : -1;
124 Option::ControlFlow = val;
125 Option::CopyProp = val;
126 } else {
127 errs = "Unknown optimization: " + opt;
128 return false;
129 }
130
131 if (end == string::npos) {
132 break;
133 }
134 pos = end;
135 }
136
137 return true;
138 }
139
140 ExpressionPtr BucketMapEntry::find(ExpressionPtr e) {
141 ExpressionPtrList::iterator it = m_exprs.begin();
142 while (it != m_exprs.end()) {
143 ExpressionPtr c = *it;
144 if (e->canonCompare(c)) {
145 return c;
146 }
147 ++it;
148 }
149
150 return ExpressionPtr();
151 }
152
153 void BucketMapEntry::add(ExpressionPtr e) {
154 m_exprs.push_back(e);
155 m_num++;
156 }
157
158 void BucketMapEntry::clear() {
159 m_stack.resize(0);
160 m_exprs.resize(0);
161 m_num = 0;
162 }
163
164 void BucketMapEntry::beginScope() {
165 m_stack.push_back(m_num);
166 }
167
168 void BucketMapEntry::endScope() {
169 resetScope();
170 if (m_stack.size()) {
171 m_stack.pop_back();
172 }
173 }
174
175 void BucketMapEntry::resetScope() {
176 if (!m_stack.size()) {
177 m_exprs.empty();
178 m_num = 0;
179 } else {
180 m_num = m_stack.back();
181 always_assert(m_exprs.size() >= m_num);
182 m_exprs.resize(m_num);
183 }
184 }
185
186 bool BucketMapEntry::isSubLast(ExpressionPtr e) {
187 ExpressionPtrList::reverse_iterator it = rbegin(), end = rend();
188 while (it != end) {
189 ExpressionPtr t = *it++;
190 if (t == e) return true;
191 if (t->hasSubExpr(e)) return true;
192 if (t->is(Expression::KindOfSimpleVariable)) continue;
193 if (!t->is(Expression::KindOfScalarExpression)) break;
194 ScalarExpressionPtr se = spc(ScalarExpression, t);
195 const std::string &s = se->getString();
196 if (s != "begin" && s != "end") break;
197 }
198 return false;
199 }
200
201 void BucketMapEntry::stash(size_t from, ExpressionPtrList &to) {
202 ExpressionPtrList::iterator it = m_exprs.begin(), end = m_exprs.end();
203 m_num = from;
204 while (from--) {
205 always_assert(it != end);
206 ++it;
207 }
208 while (it != end) {
209 ExpressionPtr t = *it;
210
211 to.insert(to.end(), t);
212 it = m_exprs.erase(it);
213 }
214 }
215
216 void BucketMapEntry::import(ExpressionPtrList &from) {
217 m_num += from.size();
218 m_exprs.splice(m_exprs.end(), from);
219 }
220
221 void AliasManager::add(BucketMapEntry &em, ExpressionPtr e) {
222 if (!m_noAdd) em.add(e);
223 if (!m_genAttrs) e->setCanonID(m_nextID++);
224 }
225
226 bool AliasManager::insertForDict(ExpressionPtr e) {
227 ExpressionPtr c = getCanonical(e);
228 if (c == e) return true;
229 e->setCanonID(c->getCanonID());
230 return false;
231 }
232
233 ExpressionPtr AliasManager::getCanonical(ExpressionPtr e) {
234 unsigned val = (e->getCanonHash() % MaxBuckets);
235
236 BucketMapEntry &em = m_bucketMap[val];
237 em.link(m_bucketList);
238
239 ExpressionPtr c = em.find(e);
240
241 if (!c) {
242 add(em, e);
243 c = e;
244 if (!m_genAttrs) e->setCanonPtr(ExpressionPtr());
245 } else if (!m_genAttrs) {
246 e->setCanonID(c->getCanonID());
247 e->setCanonPtr(c);
248 }
249
250 return c;
251 }
252
253 void AliasManager::clear() {
254 m_accessList.clear();
255 m_bucketMap.clear();
256 m_bucketList = 0;
257 m_stack.resize(0);
258 m_cleared = true;
259 }
260
261 void AliasManager::beginScope() {
262 if (m_noAdd) return;
263 ExpressionPtr e(new ScalarExpression(BlockScopePtr(), LocationPtr(),
264 T_STRING, string("begin")));
265 m_accessList.add(e);
266 m_stack.push_back(CondStackElem(m_accessList.size()));
267 m_accessList.beginScope();
268 if (BucketMapEntry *tail = m_bucketList) {
269 BucketMapEntry *bm = tail;
270 do {
271 bm->beginScope();
272 } while ((bm = bm->next()) != tail);
273 }
274 }
275
276 void AliasManager::mergeScope() {
277 if (m_noAdd) return;
278 if (m_stack.size()) {
279 CondStackElem &cs = m_stack.back();
280 BucketMapEntry &bm = m_accessList;
281 bm.stash(cs.m_size, cs.m_exprs);
282 } else {
283 clear();
284 }
285 }
286
287 void AliasManager::endScope() {
288 if (m_noAdd) return;
289 mergeScope();
290
291 m_accessList.endScope();
292 if (BucketMapEntry *tail = m_bucketList) {
293 BucketMapEntry *bm = tail;
294 do {
295 bm->endScope();
296 } while ((bm = bm->next()) != tail);
297 }
298
299 if (m_stack.size()) {
300 CondStackElem &cs = m_stack.back();
301 BucketMapEntry &bm = m_accessList;
302 bm.import(cs.m_exprs);
303 ExpressionPtr
304 e(new ScalarExpression(BlockScopePtr(), LocationPtr(),
305 T_STRING, string("end")));
306 bm.add(e);
307 m_stack.pop_back();
308 }
309 }
310
311 void AliasManager::resetScope() {
312 if (m_noAdd) return;
313 mergeScope();
314 m_accessList.resetScope();
315 if (BucketMapEntry *tail = m_bucketList) {
316 BucketMapEntry *bm = tail;
317 do {
318 bm->resetScope();
319 } while ((bm = bm->next()) != tail);
320 }
321 }
322
323 void AliasManager::dumpAccessChain() {
324 BucketMapEntry &lvs = m_accessList;
325 ExpressionPtrList::reverse_iterator it = lvs.rbegin(), end = lvs.rend();
326
327 if (isInExpression()) {
328 std::cout << "m_exprIdx: " << m_exprIdx << std::endl;
329 std::cout << "parent: "; m_exprParent->dumpNode(0, m_arp);
330 } else {
331 std::cout << "Not in expression" << std::endl;
332 }
333
334 while (it != end) {
335 ExpressionPtr e = *it;
336 e->dump(0, m_arp);
337 ++it;
338 }
339 }
340
341 bool AliasManager::couldBeAliased(SimpleVariablePtr sv) {
342 if (m_wildRefs) return true;
343 if (!sv->couldBeAliased()) return false;
344 if (m_inPseudoMain) return true;
345 int context = sv->getContext();
346 if ((context & Expression::Declaration) ==
347 Expression::Declaration /* global declaration */ ||
348 (context & Expression::RefAssignmentLHS) ||
349 (context & (Expression::LValue|Expression::UnsetContext)) ==
350 (Expression::LValue|Expression::UnsetContext)) {
351 /*
352 All of these are effectively reference assignments, so the only
353 thing that interferes is an exact match.
354 */
355 return false;
356 }
357 return true;
358 }
359
360 static bool canonCompare(ExpressionPtr e1, ExpressionPtr e2) {
361 return
362 e1->hasContext(Expression::ExistContext) ==
363 e2->hasContext(Expression::ExistContext) &&
364 e1->canonCompare(e2);
365 }
366
367 static bool compareArrays(ArrayElementExpressionPtr e1,
368 ArrayElementExpressionPtr e2) {
369 if (!e1->getOffset() || !e2->getOffset() ||
370 e1->getOffset()->getCanonID() != e2->getOffset()->getCanonID()) {
371 return false;
372 }
373 always_assert(e1->getOffset()->getCanonID() != 0);
374
375 if (e1->getVariable()->getCanonID() == e2->getVariable()->getCanonID() &&
376 e1->getVariable()->getCanonID() != 0) {
377 return true;
378 }
379
380 if (e1->getVariable()->getCanonLVal() == e2->getVariable() ||
381 e2->getVariable()->getCanonLVal() == e1->getVariable()) {
382 return true;
383 }
384
385 return false;
386 }
387
388 int AliasManager::testAccesses(ExpressionPtr e1, ExpressionPtr e2,
389 bool forLval /* = false */) {
390 Expression::KindOf k1 = e1->getKindOf(), k2 = e2->getKindOf();
391 while (true) {
392 switch (k1) {
393 case Expression::KindOfConstantExpression:
394 if (canonCompare(e1, e2)) return SameAccess;
395 switch (k2) {
396 case Expression::KindOfObjectMethodExpression:
397 case Expression::KindOfDynamicFunctionCall:
398 case Expression::KindOfSimpleFunctionCall:
399 case Expression::KindOfNewObjectExpression:
400 return InterfAccess;
401 default:
402 return DisjointAccess;
403 }
404 break;
405
406 case Expression::KindOfArrayElementExpression:
407 if (k2 == Expression::KindOfSimpleVariable ||
408 k2 == Expression::KindOfDynamicVariable ||
409 k2 == Expression::KindOfConstantExpression) {
410 break;
411 }
412
413 if (canonCompare(e1, e2)) return SameAccess;
414
415 if (k2 != Expression::KindOfArrayElementExpression) {
416 if (forLval && !e1->hasContext(Expression::LValue)) {
417 return DisjointAccess;
418 }
419 return InterfAccess;
420 }
421
422 {
423 ArrayElementExpressionPtr p1(spc(ArrayElementExpression, e1));
424 ArrayElementExpressionPtr p2(spc(ArrayElementExpression, e2));
425 if (compareArrays(p1, p2)) return SameAccess;
426
427 if (!forLval) return InterfAccess;
428
429 // forLval alias checking
430
431 // e1 and e2 are both array elements, where e2 is testing
432 // against e1 (e1 is ahead in the chain)
433
434 if (!p2->getVariable()->is(Expression::KindOfSimpleVariable)) {
435 return InterfAccess;
436 }
437 SimpleVariablePtr sv2(spc(SimpleVariable, p2->getVariable()));
438 if (couldBeAliased(sv2)) return InterfAccess;
439
440 // e2 looks like ($a[...]) now, and $a is not referenced
441 // so the only way e1 would interfere (in an lvalue sense)
442 // is if e1 looked also like ($a[...])
443
444 if (!p1->getVariable()->is(Expression::KindOfSimpleVariable)) {
445 if (p1->getVariable()->is(Expression::KindOfDynamicVariable)) {
446 return InterfAccess;
447 }
448 return DisjointAccess;
449 }
450 SimpleVariablePtr sv1(spc(SimpleVariable, p1->getVariable()));
451
452 // make sure the variables refer to the same thing by chasing
453 // the canon ptr
454 ExpressionPtr p(sv2->getCanonLVal());
455 while (p && p != sv1) p = p->getCanonLVal();
456 if (!p) return DisjointAccess;
457
458 // make sure the offsets refer to the same *value* by comparing
459 // canon ids
460 if (!p1->getOffset() || !p2->getOffset()) return InterfAccess;
461 return p1->getOffset()->getCanonID() == p2->getOffset()->getCanonID() ?
462 SameAccess : InterfAccess;
463 }
464
465 case Expression::KindOfStaticMemberExpression:
466 if (k2 == Expression::KindOfSimpleVariable ||
467 k2 == Expression::KindOfConstantExpression) {
468 break;
469 }
470 return canonCompare(e1, e2) ?
471 SameAccess : InterfAccess;
472
473 case Expression::KindOfObjectPropertyExpression:
474 if (k2 == Expression::KindOfSimpleVariable ||
475 k2 == Expression::KindOfConstantExpression) {
476 break;
477 }
478 return InterfAccess;
479
480 case Expression::KindOfDynamicVariable:
481 if (k2 == Expression::KindOfSimpleVariable ||
482 k2 == Expression::KindOfConstantExpression) {
483 break;
484 }
485
486 return canonCompare(e1, e2) ?
487 SameAccess : InterfAccess;
488
489 case Expression::KindOfSimpleVariable:
490 {
491 if (k2 == Expression::KindOfConstantExpression) {
492 return DisjointAccess;
493 }
494 SimpleVariablePtr sv1 = spc(SimpleVariable, e1);
495 switch (k2) {
496 case Expression::KindOfSimpleVariable:
497 {
498 SimpleVariablePtr sv2 = spc(SimpleVariable, e2);
499 if (sv1->getName() == sv2->getName()) {
500 if (sv1->SimpleVariable::isThis() &&
501 sv1->hasContext(Expression::ObjectContext) !=
502 sv2->hasContext(Expression::ObjectContext) &&
503 m_variables->getAttribute(
504 VariableTable::ContainsLDynamicVariable)) {
505 /*
506 * $this not in object context may not be the same as
507 * $this in object context if there have been writes
508 * through a variable table
509 */
510 return InterfAccess;
511 }
512 return SameAccess;
513 }
514
515 if (couldBeAliased(sv1) && couldBeAliased(sv2)) {
516 return InterfAccess;
517 }
518 }
519 return DisjointAccess;
520
521 case Expression::KindOfDynamicVariable:
522 return InterfAccess;
523
524 case Expression::KindOfArrayElementExpression:
525 if (couldBeAliased(sv1)) {
526 return InterfAccess;
527 }
528 return DisjointAccess;
529
530 case Expression::KindOfSimpleFunctionCall: {
531 SimpleFunctionCallPtr call(spc(SimpleFunctionCall, e2));
532 if (call->readsLocals() || call->writesLocals()) {
533 return InterfAccess;
534 }
535 goto def;
536 }
537 case Expression::KindOfIncludeExpression: {
538 return InterfAccess;
539 }
540 case Expression::KindOfStaticMemberExpression:
541 case Expression::KindOfObjectPropertyExpression:
542 default: def:
543 if (couldBeAliased(sv1)) {
544 return InterfAccess;
545 }
546 return DisjointAccess;
547 }
548 // mustnt get here (we would loop forever).
549 assert(false);
550 }
551 case Expression::KindOfSimpleFunctionCall:
552 case Expression::KindOfIncludeExpression:
553 if (k2 == Expression::KindOfSimpleVariable) {
554 break;
555 }
556 default:
557 return InterfAccess;
558 }
559
560 ExpressionPtr t = e1;
561 e1 = e2;
562 e2 = t;
563 k1 = k2;
564 k2 = e2->getKindOf();
565 }
566 }
567
568 static bool isReadOnlyAccess(ExpressionPtr e) {
569 if (e->getContext() & (Expression::UnsetContext|
570 Expression::RefValue|
571 Expression::RefParameter|
572 Expression::LValue)) {
573 return false;
574 }
575 switch (e->getKindOf()) {
576 case Expression::KindOfConstantExpression:
577 case Expression::KindOfSimpleVariable:
578 case Expression::KindOfArrayElementExpression:
579 case Expression::KindOfDynamicVariable:
580 return true;
581 default:
582 return false;
583 }
584 }
585
586 static void updateDepthAndFlags(ExpressionPtr e, int &depth, int &flags) {
587 ScalarExpressionPtr se = spc(ScalarExpression, e);
588 const std::string &s = se->getString();
589 if (s == "begin") {
590 depth--;
591 } else if (s == "end") {
592 depth++;
593 } else if (s == "io") {
594 flags |= Expression::IOEffect;
595 } else {
596 not_reached();
597 }
598 }
599
600 void AliasManager::cleanRefs(ExpressionPtr e,
601 ExpressionPtrList::reverse_iterator it,
602 ExpressionPtrList::reverse_iterator &end,
603 int depth) {
604 if (e->is(Expression::KindOfAssignmentExpression) ||
605 e->is(Expression::KindOfBinaryOpExpression) ||
606 e->is(Expression::KindOfUnaryOpExpression)) {
607 ExpressionPtr var = e->getStoreVariable();
608 if (var->is(Expression::KindOfSimpleVariable) &&
609 !(var->getContext() & Expression::RefAssignmentLHS)) {
610 SimpleVariablePtr sv(spc(SimpleVariable, var));
611 if (sv->getSymbol() && sv->getSymbol()->isReferenced()) {
612 /*
613 Suppose we have:
614 $t = &$q;
615 $t = 0;
616 return $q;
617
618 The $q from the return interferes with "$t = 0;", so we
619 remove "$t = 0" from the list (meaning that we /wont/ kill it).
620 But $q does not interfere with "$t = &$q". So when we remove
621 "$t = 0", we also have to remove any reference assignments
622 to $t.
623 */
624 int effects = 0;
625 bool pIsLoad = false;
626 ++it;
627 while (it != end) {
628 ExpressionPtr p = *it;
629 if (p->is(Expression::KindOfScalarExpression)) {
630 checkInterf(var, p, pIsLoad, depth, effects);
631 if (depth < 0) return;
632 } else if (p->is(Expression::KindOfAssignmentExpression) ||
633 (p->is(Expression::KindOfSimpleVariable) &&
634 (p->hasAllContext(Expression::Declaration) ||
635 p->hasAllContext(Expression::LValue |
636 Expression::UnsetContext)))) {
637 if (checkInterf(var, p, pIsLoad, depth, effects) == SameAccess) {
638 m_accessList.erase(it, end);
639 continue;
640 }
641 }
642 ++it;
643 }
644 }
645 }
646 }
647 }
648
649 void AliasManager::cleanInterf(ExpressionPtr load,
650 ExpressionPtrList::reverse_iterator it,
651 ExpressionPtrList::reverse_iterator &end,
652 int depth) {
653 while (it != end) {
654 ExpressionPtr e = *it;
655 bool eIsLoad = false;
656 int effects = 0;
657 int a = checkInterf(load, e, eIsLoad, depth, effects);
658 if (a != DisjointAccess) {
659 if (a == NotAccess) {
660 if (depth < 0) return;
661 } else if (!eIsLoad && !dpc(FunctionCall, e)) {
662 cleanRefs(e, it, end, depth);
663 m_accessList.erase(it, end);
664 continue;
665 }
666 }
667 ++it;
668 }
669 }
670
671 bool AliasManager::okToKill(ExpressionPtr ep, bool killRef) {
672 if (ep && ep->isNoRemove()) return false;
673 if (ep && ep->is(Expression::KindOfSimpleVariable)) {
674 return spc(SimpleVariable, ep)->canKill(killRef);
675 }
676 return false;
677 }
678
679 static int getOpForAssignmentOp(int op) {
680 switch (op) {
681 case T_PLUS_EQUAL: return '+';
682 case T_MINUS_EQUAL: return '-';
683 case T_MUL_EQUAL: return '*';
684 case T_DIV_EQUAL: return '/';
685 case T_CONCAT_EQUAL: return '.';
686 case T_MOD_EQUAL: return '%';
687 case T_AND_EQUAL: return '&';
688 case T_OR_EQUAL: return '|';
689 case T_XOR_EQUAL: return '^';
690 case T_SL_EQUAL: return T_SL;
691 case T_SR_EQUAL: return T_SR;
692 default: return 0;
693 }
694 }
695
696 void AliasManager::killLocals() {
697 BucketMapEntry &lvs = m_accessList;
698 ExpressionPtrList::reverse_iterator it = lvs.rbegin(), end = lvs.rend();
699 int effects = 0;
700 int depth = 0;
701 int emask = (Expression::IOEffect |
702 Expression::CanThrow |
703 Expression::AccessorEffect |
704 Expression::OtherEffect);
705
706 while (it != end) {
707 ExpressionPtr e = *it;
708 switch (e->getKindOf()) {
709 case Expression::KindOfScalarExpression:
710 updateDepthAndFlags(e, depth, effects);
711 if (depth < 0) {
712 it = end;
713 continue;
714 }
715 break;
716
717 case Expression::KindOfListAssignment:
718 if (!(effects & emask)) {
719 ListAssignmentPtr la = spc(ListAssignment, e);
720 ExpressionList &lhs = *la->getVariables().get();
721 for (int i = lhs.getCount(); i--; ) {
722 if (okToKill(lhs[i], false)) {
723 lhs[i].reset();
724 }
725 }
726 }
727 goto kill_it;
728
729 case Expression::KindOfAssignmentExpression:
730 if (!(effects & emask)) {
731 AssignmentExpressionPtr ae(spc(AssignmentExpression, e));
732 if (okToKill(ae->getVariable(),
733 ae->getValue()->getContext() & Expression::RefValue)) {
734 e->setContext(Expression::DeadStore);
735 m_replaced++;
736 }
737 }
738 cleanRefs(e, it, end, depth);
739 goto kill_it;
740
741 case Expression::KindOfBinaryOpExpression:
742 if (!(effects & emask) &&
743 getOpForAssignmentOp(spc(BinaryOpExpression, e)->getOp())) {
744 if (okToKill(spc(BinaryOpExpression, e)->getExp1(), false)) {
745 e->setContext(Expression::DeadStore);
746 m_replaced++;
747 ++it;
748 continue;
749 }
750 }
751 cleanInterf(spc(BinaryOpExpression, e)->getExp1(), ++it, end, depth);
752 continue;
753
754 case Expression::KindOfUnaryOpExpression:
755 cleanInterf(spc(UnaryOpExpression, e)->getExpression(),
756 ++it, end, depth);
757 continue;
758
759 case Expression::KindOfSimpleVariable:
760 case Expression::KindOfObjectPropertyExpression:
761 case Expression::KindOfDynamicVariable:
762 case Expression::KindOfArrayElementExpression:
763 case Expression::KindOfStaticMemberExpression:
764 if (e->hasAllContext(Expression::LValue | Expression::UnsetContext) ||
765 e->hasAllContext(Expression::Declaration)) {
766 if (!(effects & emask) && okToKill(e, true)) {
767 bool ok = (m_postOpt || !e->is(Expression::KindOfSimpleVariable));
768 if (!ok) {
769 Symbol *sym = spc(SimpleVariable,e)->getSymbol();
770 ok =
771 !sym ||
772 (sym->isGlobal() && !e->hasContext(Expression::UnsetContext)) ||
773 (!sym->isNeeded() && !sym->isUsed());
774 }
775 if (ok) {
776 e->setReplacement(e->makeConstant(m_arp, "null"));
777 m_replaced++;
778 }
779 } else {
780 effects |= Expression::UnknownEffect;
781 }
782 goto kill_it;
783 }
784 cleanInterf(e, ++it, end, depth);
785 continue;
786
787 default: kill_it:
788 lvs.erase(it, end);
789 effects |= e->getContainedEffects();
790 continue;
791 }
792
793 effects |= e->getContainedEffects();
794 ++it;
795 }
796 }
797
798 int AliasManager::checkInterf(ExpressionPtr rv, ExpressionPtr e,
799 bool &isLoad, int &depth, int &effects,
800 bool forLval /* = false */) {
801 isLoad = true;
802 switch (e->getKindOf()) {
803 case Expression::KindOfScalarExpression:
804 {
805 updateDepthAndFlags(e, depth, effects);
806 return NotAccess;
807 }
808
809 case Expression::KindOfObjectMethodExpression:
810 case Expression::KindOfDynamicFunctionCall:
811 case Expression::KindOfSimpleFunctionCall:
812 case Expression::KindOfNewObjectExpression:
813 case Expression::KindOfIncludeExpression:
814 isLoad = false;
815 return testAccesses(rv, e, forLval);
816
817 case Expression::KindOfListAssignment: {
818 isLoad = false;
819 ListAssignmentPtr la = spc(ListAssignment, e);
820 ExpressionList &lhs = *la->getVariables().get();
821 for (int i = lhs.getCount(); i--; ) {
822 ExpressionPtr ep = lhs[i];
823 if (ep) {
824 if (ep->is(Expression::KindOfListAssignment)) {
825 if (checkInterf(rv, ep, isLoad, depth, effects, forLval) !=
826 DisjointAccess) {
827 return InterfAccess;
828 }
829 } else if (testAccesses(ep, rv, forLval) != DisjointAccess) {
830 return InterfAccess;
831 }
832 }
833 }
834 break;
835 }
836
837 case Expression::KindOfObjectPropertyExpression:
838 case Expression::KindOfConstantExpression:
839 case Expression::KindOfSimpleVariable:
840 case Expression::KindOfDynamicVariable:
841 case Expression::KindOfArrayElementExpression:
842 case Expression::KindOfStaticMemberExpression: {
843 int m = e->getContext() &
844 (Expression::LValue|
845 Expression::Declaration|
846 Expression::UnsetContext);
847 isLoad = !(m & Expression::LValue) || m == Expression::LValue;
848 return testAccesses(e, rv, forLval);
849 }
850
851 case Expression::KindOfAssignmentExpression:
852 case Expression::KindOfBinaryOpExpression:
853 case Expression::KindOfUnaryOpExpression: {
854 isLoad = false;
855 ExpressionPtr var = e->getStoreVariable();
856 int access = testAccesses(var, rv, forLval);
857 if (access == SameAccess) {
858 // An assignment to something that might be visible from
859 // another scope, and that might contain an object, could
860 // end up with some other value (due to a destructor running)
861 // than the rhs.
862 if (var->getKindOf() != Expression::KindOfSimpleVariable) {
863 return InterfAccess;
864 }
865 SimpleVariablePtr sv = static_pointer_cast<SimpleVariable>(var);
866 if (sv->couldBeAliased() &&
867 (sv->isNeededValid() ? sv->isNeeded() :
868 !sv->getSymbol() || sv->getSymbol()->isNeeded())) {
869 return InterfAccess;
870 }
871 }
872 return access;
873 }
874
875 default:
876 not_reached();
877 }
878
879 return DisjointAccess;
880 }
881
882 int AliasManager::checkAnyInterf(ExpressionPtr e1, ExpressionPtr e2,
883 bool &isLoad, int &depth, int &effects,
884 bool forLval /* = false */) {
885 switch (e1->getKindOf()) {
886 case Expression::KindOfListAssignment: {
887 ListAssignmentPtr la = spc(ListAssignment, e1);
888 ExpressionList &lhs = *la->getVariables().get();
889 for (int i = lhs.getCount(); i--; ) {
890 ExpressionPtr ep = lhs[i];
891 if (ep && checkAnyInterf(ep, e2, isLoad, depth, effects, forLval) !=
892 DisjointAccess) {
893 isLoad = false;
894 return InterfAccess;
895 }
896 }
897 return DisjointAccess;
898 }
899 case Expression::KindOfAssignmentExpression:
900 case Expression::KindOfBinaryOpExpression:
901 case Expression::KindOfUnaryOpExpression:
902 e1 = e1->getStoreVariable();
903 if (!e1 || !e1->hasContext(Expression::OprLValue)) return DisjointAccess;
904 break;
905 default:
906 break;
907 }
908
909 return checkInterf(e1, e2, isLoad, depth, effects, forLval);
910 }
911
912 int AliasManager::findInterf0(
913 ExpressionPtr rv, bool isLoad,
914 ExpressionPtr &rep,
915 ExpressionPtrList::reverse_iterator begin,
916 ExpressionPtrList::reverse_iterator end,
917 int *flags /* = 0 */,
918 bool allowLval /* = false */, bool forLval /* = false */,
919 int depth /* = 0 */, int min_depth /* = 0 */,
920 int max_depth /* = 0 */) {
921
922 rep.reset();
923 ExpressionPtrList::reverse_iterator it = begin;
924
925 bool unset_simple = !isLoad &&
926 rv->hasAllContext(Expression::UnsetContext | Expression::LValue) &&
927 rv->is(Expression::KindOfSimpleVariable) &&
928 (!m_inPseudoMain || spc(SimpleVariable, rv)->isHidden());
929
930 bool hasStash = false;
931 ExpressionPtrList::reverse_iterator stash;
932 int stash_depth = 0, stash_min_depth = 0, stash_max_depth = 0;
933
934 for (; it != end; ++it) {
935 ExpressionPtr e = *it;
936 if (e->getContext() & Expression::DeadStore) continue;
937 bool eIsLoad = false;
938 int effects = 0;
939 int a = checkInterf(rv, e, eIsLoad, depth, effects, forLval);
940 if (a != DisjointAccess) {
941 if (a == NotAccess) {
942 if (effects & Expression::IOEffect) {
943 int effect = rv->getLocalEffects();
944 if (effect & (Expression::IOEffect|
945 Expression::CanThrow|
946 Expression::AccessorEffect|
947 Expression::OtherEffect)) {
948 return InterfAccess;
949 }
950 } else if (depth < min_depth) {
951 min_depth = depth;
952 } else if (depth > max_depth) {
953 max_depth = depth;
954 }
955 } else {
956 if (a == InterfAccess &&
957 rv->is(Expression::KindOfArrayElementExpression) &&
958 e->hasContext(Expression::AccessContext)) {
959 ExpressionPtr t = rv;
960 do {
961 t = spc(ArrayElementExpression, t)->getVariable();
962 if (t == e) break;
963 } while (t->is(Expression::KindOfArrayElementExpression));
964 if (t == e) continue;
965 }
966 if (unset_simple) {
967 if (a == InterfAccess) {
968 if (!rep) {
969 rep = e;
970 }
971 continue;
972 } else if (a == SameAccess && rep) {
973 if (!e->is(Expression::KindOfSimpleVariable) ||
974 !e->hasAllContext(Expression::UnsetContext |
975 Expression::LValue)) {
976 return InterfAccess;
977 }
978 }
979 }
980 if (a == SameAccess) {
981 if (flags) {
982 *flags = 0;
983 if (depth > min_depth) *flags |= NoCopyProp;
984 if (min_depth < 0) *flags |= NoDeadStore;
985 } else if (isLoad) {
986 // The value of an earlier load is available
987 // if it dominates this one
988 if (depth > min_depth) {
989 a = InterfAccess;
990 }
991 } else {
992 // The assignment definitely hits the load
993 // if it post-dominates it.
994 if (min_depth < 0) {
995 a = InterfAccess;
996 }
997 }
998 }
999 if (a != SameAccess && eIsLoad && isLoad && isReadOnlyAccess(e)) {
1000 if (!hasStash && !forLval && allowLval) {
1001 // stash the state away so we can pick up here if we need to
1002 hasStash = true;
1003 stash = it;
1004 stash_depth = depth;
1005 stash_min_depth = min_depth;
1006 stash_max_depth = max_depth;
1007 }
1008 continue;
1009 }
1010 rep = e;
1011 if (!forLval && allowLval && a != SameAccess) {
1012 if (hasStash) {
1013 return findInterf0(
1014 rv, isLoad, rep,
1015 stash, end, flags, allowLval, true,
1016 stash_depth, stash_min_depth,
1017 stash_max_depth);
1018 }
1019 forLval = true;
1020 // try this node again
1021 --it;
1022 continue;
1023 }
1024 if (a == SameAccess && forLval) a = SameLValueAccess;
1025 return a;
1026 }
1027 }
1028 }
1029
1030 if (hasStash) {
1031 assert(allowLval);
1032 return findInterf0(
1033 rv, isLoad, rep,
1034 stash, end, flags, allowLval, true,
1035 stash_depth, stash_min_depth,
1036 stash_max_depth);
1037 }
1038
1039 return DisjointAccess;
1040 }
1041
1042 int AliasManager::findInterf(ExpressionPtr rv, bool isLoad,
1043 ExpressionPtr &rep, int *flags /* = 0 */,
1044 bool allowLval /* = false */) {
1045 BucketMapEntry &lvs = m_accessList;
1046 return findInterf0(rv, isLoad, rep, lvs.rbegin(), lvs.rend(),
1047 flags, allowLval);
1048 }
1049
1050 ExpressionPtr AliasManager::canonicalizeNonNull(ExpressionPtr e) {
1051 ExpressionPtr r = canonicalizeNode(e);
1052 return r ? r : e;
1053 }
1054
1055 ExpressionPtr AliasManager::canonicalizeRecurNonNull(ExpressionPtr e) {
1056 ExpressionPtr r = canonicalizeRecur(e);
1057 return r ? r : e;
1058 }
1059
1060 static bool sameExpr(ExpressionPtr e1, ExpressionPtr e2) {
1061 if (e1 == e2) return true;
1062 while (true) {
1063 e2 = e2->getCanonPtr();
1064 if (!e2) break;
1065 if (e2 == e1) return true;
1066 }
1067 return false;
1068 }
1069
1070 void AliasManager::setCanonPtrForArrayCSE(
1071 ExpressionPtr e,
1072 ExpressionPtr rep) {
1073 assert(e);
1074 assert(rep);
1075 if (e->is(Expression::KindOfArrayElementExpression)) {
1076 // e is an array access in rvalue context,
1077 // need to switch on rep
1078 ExpressionPtr rep0;
1079 switch (rep->getKindOf()) {
1080 case Expression::KindOfAssignmentExpression:
1081 case Expression::KindOfBinaryOpExpression:
1082 case Expression::KindOfUnaryOpExpression:
1083 rep0 = rep->getStoreVariable();
1084 break;
1085 case Expression::KindOfListAssignment:
1086 // TODO: IMPLEMENT
1087 assert(false);
1088 break;
1089 default:
1090 rep0 = rep;
1091 break;
1092 }
1093 if (rep0 && rep0->is(Expression::KindOfArrayElementExpression)) {
1094 e->setCanonPtr(rep0);
1095 ExpressionPtr match(e->getNextCanonCsePtr());
1096 if (match && !match->isChainRoot()) {
1097 ExpressionPtr matchNext(match->getNextCanonCsePtr());
1098 if (!matchNext) {
1099 // make match a new CSE chain root
1100 match->setChainRoot();
1101 m_hasChainRoot = true;
1102 }
1103 }
1104 }
1105 }
1106 }
1107
1108 void AliasManager::processAccessChain(ExpressionPtr e) {
1109 if (!e) return;
1110 if (!e->is(Expression::KindOfObjectPropertyExpression) &&
1111 !e->is(Expression::KindOfArrayElementExpression)) {
1112 return;
1113 }
1114 for (int i = 0, n = e->getKidCount(); i < n; ++i) {
1115 ExpressionPtr kid(e->getNthExpr(i));
1116 if (kid && kid->hasContext(Expression::AccessContext)) {
1117 processAccessChain(kid);
1118 ExpressionPtr rep(canonicalizeNode(kid, true));
1119 if (rep) {
1120 e->setNthKid(i, rep);
1121 e->recomputeEffects();
1122 setChanged();
1123 }
1124 break;
1125 }
1126 }
1127 }
1128
1129 void AliasManager::processAccessChainLA(ListAssignmentPtr la) {
1130 ExpressionList &lhs = *la->getVariables().get();
1131 for (int i = lhs.getCount(); i--; ) {
1132 ExpressionPtr ep = lhs[i];
1133 if (ep) {
1134 if (ep->is(Expression::KindOfListAssignment)) {
1135 processAccessChainLA(spc(ListAssignment, ep));
1136 } else {
1137 processAccessChain(ep);
1138 add(m_accessList, ep);
1139 }
1140 }
1141 }
1142 }
1143
1144 ExpressionPtr AliasManager::canonicalizeNode(
1145 ExpressionPtr e, bool doAccessChains /* = false */) {
1146 if (e->isVisited()) return ExpressionPtr();
1147 if ((e->getContext() & (Expression::AssignmentLHS|
1148 Expression::OprLValue)) ||
1149 (!doAccessChains && e->hasContext(Expression::AccessContext))) {
1150 ExpressionPtr ret;
1151 if (!m_noAdd) {
1152 if (m_preOpt) ret = e->preOptimize(m_arp);
1153 if (m_postOpt) ret = e->postOptimize(m_arp);
1154 if (ret) {
1155 return canonicalizeRecurNonNull(ret);
1156 }
1157 }
1158 e->setCanonPtr(ExpressionPtr());
1159 e->setCanonID(0);
1160 return ExpressionPtr();
1161 }
1162
1163 ExpressionPtr var;
1164 switch (e->getKindOf()) {
1165 case Expression::KindOfAssignmentExpression: {
1166 case Expression::KindOfBinaryOpExpression:
1167 case Expression::KindOfUnaryOpExpression:
1168 ExpressionPtr var = e->getStoreVariable();
1169 if (var && var->getContext() & (Expression::AssignmentLHS|
1170 Expression::OprLValue)) {
1171 processAccessChain(var);
1172 }
1173 break;
1174 }
1175 case Expression::KindOfListAssignment:
1176 processAccessChainLA(spc(ListAssignment,e));
1177 break;
1178 default:
1179 break;
1180 }
1181
1182 ExpressionPtr ret;
1183 if (!m_noAdd && !doAccessChains) {
1184 if (m_preOpt) ret = e->preOptimize(m_arp);
1185 if (m_postOpt) ret = e->postOptimize(m_arp);
1186 if (ret) {
1187 return canonicalizeRecurNonNull(ret);
1188 }
1189 }
1190
1191 e->setVisited();
1192 e->clearLocalExprAltered();
1193 e->setCanonPtr(ExpressionPtr());
1194 e->clearChainRoot();
1195 e->setCanonID(0);
1196
1197 switch (e->getKindOf()) {
1198 case Expression::KindOfObjectMethodExpression:
1199 case Expression::KindOfDynamicFunctionCall:
1200 case Expression::KindOfSimpleFunctionCall:
1201 case Expression::KindOfNewObjectExpression:
1202 case Expression::KindOfIncludeExpression:
1203 case Expression::KindOfListAssignment:
1204 markAllLocalExprAltered(e);
1205 add(m_accessList, e);
1206 break;
1207
1208 case Expression::KindOfAssignmentExpression: {
1209 AssignmentExpressionPtr ae = spc(AssignmentExpression,e);
1210 if (e->hasContext(Expression::DeadStore)) {
1211 e->recomputeEffects();
1212 return ae->replaceValue(ae->getValue());
1213 }
1214 markAllLocalExprAltered(ae->getVariable());
1215 ExpressionPtr rep;
1216 int interf = findInterf(ae->getVariable(), false, rep);
1217 if (interf == SameAccess) {
1218 switch (rep->getKindOf()) {
1219 case Expression::KindOfAssignmentExpression: {
1220 AssignmentExpressionPtr a = spc(AssignmentExpression, rep);
1221 rep = a->getVariable();
1222 if (Option::EliminateDeadCode) {
1223 ExpressionPtr value = a->getValue();
1224 if (value->getContext() & Expression::RefValue) {
1225 break;
1226 }
1227 if (!Expression::CheckNeeded(a->getVariable(), value) ||
1228 m_accessList.isSubLast(a) ||
1229 (value->isTemporary() && m_expr->hasSubExpr(a))) {
1230 a->setReplacement(value);
1231 m_replaced++;
1232 }
1233 }
1234 break;
1235 }
1236 case Expression::KindOfBinaryOpExpression: {
1237 BinaryOpExpressionPtr b = spc(BinaryOpExpression, rep);
1238 if (Option::EliminateDeadCode) {
1239 bool ok = b->getActualType() &&
1240 b->getActualType()->isNoObjectInvolved();
1241 if (!ok) {
1242 switch (b->getOp()) {
1243 case T_PLUS_EQUAL:
1244 // could be Array
1245 break;
1246 case T_MINUS_EQUAL:
1247 case T_MUL_EQUAL:
1248 case T_DIV_EQUAL:
1249 case T_CONCAT_EQUAL:
1250 case T_MOD_EQUAL:
1251 case T_AND_EQUAL:
1252 case T_OR_EQUAL:
1253 case T_XOR_EQUAL:
1254 case T_SL_EQUAL:
1255 case T_SR_EQUAL:
1256 ok = true;
1257 break;
1258 }
1259 }
1260 if (ok) {
1261 ExpressionPtr rhs = b->getExp2()->clone();
1262 ExpressionPtr lhs = b->getExp1()->clone();
1263 lhs->clearContext();
1264
1265 b->setReplacement(
1266 ExpressionPtr(new BinaryOpExpression(
1267 b->getScope(), b->getLocation(),
1268 lhs, rhs, getOpForAssignmentOp(b->getOp()))));
1269 m_replaced++;
1270 }
1271 }
1272 rep = b->getExp1();
1273 break;
1274 }
1275 case Expression::KindOfUnaryOpExpression: {
1276 UnaryOpExpressionPtr u = spc(UnaryOpExpression, rep);
1277 if (Option::EliminateDeadCode) {
1278 if (u->getActualType() && u->getActualType()->isInteger()) {
1279 ExpressionPtr val = u->getExpression()->clone();
1280 val->clearContext();
1281 if (u->getFront()) {
1282 ExpressionPtr inc
1283 (new ScalarExpression(u->getScope(), u->getLocation(),
1284 T_LNUMBER, string("1")));
1285
1286 val = ExpressionPtr(
1287 new BinaryOpExpression(u->getScope(), u->getLocation(),
1288 val, inc,
1289 u->getOp() == T_INC ? '+' : '-'));
1290
1291 }
1292
1293 u->setReplacement(val);
1294 m_replaced++;
1295 }
1296 rep = u->getExpression();
1297 }
1298 break;
1299 }
1300 default:
1301 break;
1302 }
1303 always_assert(rep->getKindOf() == ae->getVariable()->getKindOf());
1304 ae->getVariable()->setCanonID(rep->getCanonID());
1305 } else {
1306 ae->getVariable()->setCanonID(m_nextID++);
1307 }
1308 add(m_accessList, e);
1309 break;
1310 }
1311
1312 case Expression::KindOfArrayElementExpression:
1313 case Expression::KindOfObjectPropertyExpression:
1314 if (!e->hasContext(Expression::AccessContext)) {
1315 processAccessChain(e);
1316 }
1317 case Expression::KindOfSimpleVariable:
1318 case Expression::KindOfDynamicVariable:
1319 case Expression::KindOfStaticMemberExpression:
1320 if (e->hasContext(Expression::UnsetContext) &&
1321 e->hasContext(Expression::LValue)) {
1322 markAllLocalExprAltered(e);
1323 if (Option::EliminateDeadCode) {
1324 ExpressionPtr rep;
1325 int interf = findInterf(e, false, rep);
1326 if (interf == SameAccess) {
1327 if (rep->getKindOf() == e->getKindOf()) {
1328 // if we hit a previous unset of the same thing
1329 // we can delete this one
1330 if (rep->hasContext(Expression::UnsetContext) &&
1331 rep->hasContext(Expression::LValue)) {
1332 return canonicalizeRecurNonNull(e->makeConstant(m_arp, "null"));
1333 }
1334 } else {
1335 switch (rep->getKindOf()) {
1336 case Expression::KindOfAssignmentExpression:
1337 {
1338 /*
1339 Handling unset of a variable which hasnt been
1340 used since it was last assigned
1341 */
1342 if (!e->is(Expression::KindOfSimpleVariable)) {
1343 break;
1344 }
1345
1346 AssignmentExpressionPtr a = spc(AssignmentExpression, rep);
1347
1348 always_assert(
1349 a->getVariable()->is(Expression::KindOfSimpleVariable));
1350 SimpleVariablePtr variable =
1351 spc(SimpleVariable, a->getVariable());
1352 if (variable->couldBeAliased()) {
1353 break;
1354 }
1355
1356 ExpressionPtr value = a->getValue();
1357 if (value->getContext() & Expression::RefValue) {
1358 break;
1359 }
1360 if (!Expression::CheckNeeded(a->getVariable(), value) ||
1361 m_accessList.isSubLast(a) ||
1362 (value->isTemporary() && m_expr->hasSubExpr(a))) {
1363 rep->setReplacement(value);
1364 m_replaced++;
1365 } else {
1366 ExpressionPtr last = value;
1367 while (last->is(Expression::KindOfAssignmentExpression)) {
1368 last = spc(AssignmentExpression, last)->getValue();
1369 }
1370 if (!last->isScalar()) {
1371 ExpressionPtr cur = value;
1372 while (cur) {
1373 ExpressionPtr rhs = cur;
1374 ExpressionPtr next;
1375 if (cur->is(Expression::KindOfAssignmentExpression)) {
1376 rhs = spc(AssignmentExpression, cur)->getVariable();
1377 next = spc(AssignmentExpression, cur)->getValue();
1378 } else {
1379 next.reset();
1380 }
1381 if (!rhs->hasEffect()) {
1382 m_noAdd = true;
1383 ExpressionPtr v = rhs->clone();
1384 v->clearContext();
1385 v = canonicalizeRecurNonNull(v);
1386 m_noAdd = false;
1387 while (v->getCanonPtr() && v->getCanonPtr() != last) {
1388 v = v->getCanonPtr();
1389 }
1390 if (v->getCanonPtr()) {
1391 if (a->isUnused() && rhs == value) {
1392 value = value->replaceValue(
1393 canonicalizeRecurNonNull(
1394 value->makeConstant(m_arp, "null")));
1395 a->setValue(value);
1396 a->recomputeEffects();
1397 setChanged();
1398 } else {
1399 ExpressionListPtr el(
1400 new ExpressionList(
1401 a->getScope(), a->getLocation(),
1402 ExpressionList::ListKindWrapped));
1403 a = spc(AssignmentExpression, a->clone());
1404 el->addElement(a);
1405 el->addElement(a->getValue());
1406 a->setValue(value->makeConstant(m_arp, "null"));
1407 rep->setReplacement(el);
1408 m_replaced++;
1409 }
1410 break;
1411 }
1412 }
1413 cur = next;
1414 }
1415 }
1416 }
1417 }
1418 default:
1419 break;
1420 }
1421 }
1422 }
1423 }
1424 add(m_accessList, e);
1425 break;
1426 }
1427 // Fall through
1428 case Expression::KindOfConstantExpression: {
1429 /*
1430 Expressions with AccessContext need to be taken care of
1431 by processAccessChain(), which adds the entire access chain
1432 to the access list after all its side effects have taken place.
1433 In the case of assignment, or binary op assignment, its added
1434 after the rhs has been fully processed too.
1435 */
1436 bool doArrayCSE = Option::ArrayAccessIdempotent && m_postOpt;
1437 if (e->hasContext(Expression::AccessContext)) {
1438 always_assert(doAccessChains);
1439 if (e->getContext() & (Expression::LValue|
1440 Expression::RefValue|
1441 Expression::RefParameter|
1442 Expression::DeepReference|
1443 Expression::UnsetContext)) {
1444 ExpressionPtr rep;
1445 int interf =
1446 findInterf(e, true, rep, nullptr, doArrayCSE);
1447 add(m_accessList, e);
1448 if (interf == SameAccess) {
1449 if (e->getKindOf() == rep->getKindOf()) {
1450 // e->setCanonID(rep->getCanonID());
1451 } else if (rep->is(Expression::KindOfBinaryOpExpression) ||
1452 rep->is(Expression::KindOfUnaryOpExpression)) {
1453 break;
1454 } else if (rep->is(Expression::KindOfAssignmentExpression)) {
1455 //e->setCanonID(
1456 // spc(AssignmentExpression, rep)->getVariable()->getCanonID());
1457 do {
1458 rep = spc(AssignmentExpression, rep)->getValue();
1459 } while (rep->is(Expression::KindOfAssignmentExpression));
1460 }
1461 e->setCanonPtr(rep);
1462 } else if (interf == SameLValueAccess) {
1463 setCanonPtrForArrayCSE(e, rep);
1464 } else if (interf == InterfAccess && rep &&
1465 rep->is(Expression::KindOfAssignmentExpression) &&
1466 (e->is(Expression::KindOfSimpleVariable) ||
1467 e->is(Expression::KindOfArrayElementExpression))) {
1468 ExpressionPtr val = rep;
1469 do {
1470 val = spc(AssignmentExpression, val)->getValue();
1471 } while (val->is(Expression::KindOfAssignmentExpression));
1472 if (!val->isScalar()) break;
1473 ExpressionPtr var = spc(AssignmentExpression, rep)->getVariable();
1474 while (var->is(Expression::KindOfArrayElementExpression)) {
1475 var = spc(ArrayElementExpression, var)->getVariable();
1476 if (var->getKindOf() == e->getKindOf()) {
1477 if (var->is(Expression::KindOfSimpleVariable)) {
1478 if (canonCompare(var, e)) {
1479 e->setCanonPtr(var);
1480 break;
1481 }
1482 } else {
1483 ArrayElementExpressionPtr a1(
1484 spc(ArrayElementExpression, e));
1485 ArrayElementExpressionPtr a2(
1486 spc(ArrayElementExpression, var));
1487 if (compareArrays(a1, a2)) {
1488 e->setCanonPtr(var);
1489 break;
1490 }
1491 }
1492
1493 }
1494 }
1495 }
1496 break;
1497 }
1498 }
1499 if (!(e->getContext() & (Expression::LValue|
1500 Expression::RefValue|
1501 Expression::RefParameter|
1502 Expression::DeepReference|
1503 Expression::UnsetContext))) {
1504 ExpressionPtr rep;
1505 int interf =
1506 findInterf(e, true, rep, nullptr, doArrayCSE);
1507 if (!m_inPseudoMain && interf == DisjointAccess && !m_cleared &&
1508 e->is(Expression::KindOfSimpleVariable) &&
1509 !e->isThis()) {
1510 Symbol *s = spc(SimpleVariable, e)->getSymbol();
1511 if (s && !s->isParameter() && !s->isGeneratorParameter() &&
1512 !s->isClosureVar()) {
1513 rep = e->makeConstant(m_arp, "null");
1514 Compiler::Error(Compiler::UseUndeclaredVariable, e);
1515 if (m_variables->getAttribute(VariableTable::ContainsCompact)) {
1516 rep = ExpressionPtr(
1517 new UnaryOpExpression(e->getScope(), e->getLocation(),
1518 rep, T_UNSET_CAST, true));
1519 }
1520 return e->replaceValue(canonicalizeRecurNonNull(rep));
1521 }
1522 }
1523 if (interf == SameAccess) {
1524 if (rep->getKindOf() == e->getKindOf()) {
1525 if (rep->hasContext(Expression::UnsetContext) &&
1526 rep->hasContext(Expression::LValue) &&
1527 !rep->is(Expression::KindOfConstantExpression)) {
1528 return e->replaceValue(
1529 canonicalizeRecurNonNull(e->makeConstant(m_arp, "null")));
1530 }
1531 add(m_accessList, e);
1532 e->setCanonID(rep->getCanonID());
1533 e->setCanonPtr(rep);
1534 if (doArrayCSE) setCanonPtrForArrayCSE(e, rep);
1535 return ExpressionPtr();
1536 }
1537 if (Option::LocalCopyProp &&
1538 rep->getKindOf() == Expression::KindOfAssignmentExpression) {
1539 AssignmentExpressionPtr ae = spc(AssignmentExpression,rep);
1540 ExpressionPtr cur = ae->getValue(), last = cur;
1541 while (last->is(Expression::KindOfAssignmentExpression)) {
1542 last = spc(AssignmentExpression, last)->getValue();
1543 }
1544 if (last->isScalar()) {
1545 last = last->clone();
1546 getCanonical(last);
1547 return last;
1548 }
1549 while (cur) {
1550 ExpressionPtr rhs = cur;
1551 ExpressionPtr next;
1552 if (cur->is(Expression::KindOfAssignmentExpression)) {
1553 rhs = spc(AssignmentExpression, cur)->getVariable();
1554 next = spc(AssignmentExpression, cur)->getValue();
1555 } else {
1556 next.reset();
1557 }
1558 if (rhs->is(Expression::KindOfSimpleVariable)) {
1559 rhs = rhs->clone();
1560 rhs->clearContext();
1561 ExpressionPtr orig;
1562 int i = findInterf(rhs, true, orig);
1563 if (i == SameAccess &&
1564 (sameExpr(cur, orig) || (next && sameExpr(next, orig)))) {
1565 e->recomputeEffects();
1566 return e->replaceValue(canonicalizeRecurNonNull(rhs));
1567 }
1568 }
1569 cur = next;
1570 }
1571 if (!m_inCall &&
1572 !last->is(Expression::KindOfYieldExpression) &&
1573 ae->isUnused() && m_accessList.isLast(ae) &&
1574 !e->hasAnyContext(Expression::AccessContext |
1575 Expression::ObjectContext |
1576 Expression::ExistContext |
1577 Expression::UnsetContext)) {
1578 rep = ae->clone();
1579 ae->setContext(Expression::DeadStore);
1580 ae->setValue(ae->makeConstant(m_arp, "null"));
1581 ae->setVariable(ae->makeConstant(m_arp, "null"));
1582 e->recomputeEffects();
1583 m_replaced++;
1584 return e->replaceValue(canonicalizeRecurNonNull(rep));
1585 }
1586 e->setCanonPtr(last);
1587 }
1588 } else if (interf == SameLValueAccess) {
1589 setCanonPtrForArrayCSE(e, rep);
1590 }
1591 }
1592 add(m_accessList, e);
1593 break;
1594 }
1595
1596 case Expression::KindOfBinaryOpExpression: {
1597 BinaryOpExpressionPtr bop = spc(BinaryOpExpression, e);
1598 int rop = getOpForAssignmentOp(bop->getOp());
1599 if (bop->hasContext(Expression::DeadStore)) {
1600 always_assert(rop);
1601 ExpressionPtr rhs = bop->getExp2();
1602 ExpressionPtr lhs = bop->getExp1();
1603 lhs->clearContext();
1604 e->recomputeEffects();
1605 return bop->replaceValue(
1606 canonicalizeNonNull(ExpressionPtr(
1607 new BinaryOpExpression(
1608 bop->getScope(), bop->getLocation(),
1609 lhs, rhs, rop))));
1610 }
1611 if (rop) {
1612 markAllLocalExprAltered(bop);
1613 ExpressionPtr lhs = bop->getExp1();
1614 ExpressionPtr alt;
1615 int flags = 0;
1616 int interf = findInterf(lhs, true, alt, &flags);
1617 if (interf == SameAccess && !(flags & NoCopyProp)) {
1618 switch (alt->getKindOf()) {
1619 case Expression::KindOfAssignmentExpression: {
1620 ExpressionPtr op0 = spc(AssignmentExpression,alt)->getValue();
1621 if (op0->isScalar()) {
1622 ExpressionPtr op1 = bop->getExp2();
1623 ExpressionPtr rhs(
1624 (new BinaryOpExpression(e->getScope(), e->getLocation(),
1625 op0->clone(), op1->clone(), rop)));
1626
1627 lhs = lhs->clone();
1628 lhs->clearContext(Expression::OprLValue);
1629 return e->replaceValue(
1630 canonicalizeRecurNonNull(
1631 ExpressionPtr(new AssignmentExpression(
1632 e->getScope(), e->getLocation(),
1633 lhs, rhs, false))));
1634 }
1635 alt = spc(AssignmentExpression,alt)->getVariable();
1636 break;
1637 }
1638 case Expression::KindOfBinaryOpExpression: {
1639 BinaryOpExpressionPtr b2(spc(BinaryOpExpression, alt));
1640 if (!(flags & NoDeadStore) && b2->getOp() == bop->getOp()) {
1641 switch (rop) {
1642 case '-':
1643 rop = '+';
1644 break;
1645 case '+':
1646 case '*':
1647 case '.':
1648 case '&':
1649 case '|':
1650 case '^':
1651 break;
1652 default:
1653 rop = 0;
1654 break;
1655 }
1656 if (rop) {
1657 ExpressionPtr op0 = b2->getExp2();
1658 bool ok = op0->isScalar();
1659 if (!ok && !op0->hasEffect()) {
1660 m_noAdd = true;
1661 ExpressionPtr v = op0->clone();
1662 v->clearContext();
1663 v = canonicalizeRecurNonNull(v);
1664 m_noAdd = false;
1665 while (v->getCanonPtr() && v->getCanonPtr() != op0) {
1666 v = v->getCanonPtr();
1667 }
1668 ok = v->getCanonPtr();
1669 }
1670 if (ok) {
1671 b2->setContext(Expression::DeadStore);
1672 ExpressionPtr r(new BinaryOpExpression(
1673 bop->getScope(), bop->getLocation(),
1674 op0->clone(), bop->getExp2(),
1675 rop));
1676 ExpressionPtr b(new BinaryOpExpression(
1677 bop->getScope(), bop->getLocation(),
1678 lhs, r, bop->getOp()));
1679 return e->replaceValue(canonicalizeRecurNonNull(b));
1680 }
1681 }
1682 }
1683 alt = spc(BinaryOpExpression,alt)->getExp1();
1684 break;
1685 }
1686 case Expression::KindOfUnaryOpExpression:
1687 alt = spc(UnaryOpExpression,alt)->getExpression();
1688 break;
1689 default:
1690 break;
1691 }
1692 always_assert(alt->getKindOf() == lhs->getKindOf());
1693 lhs->setCanonID(alt->getCanonID());
1694 } else {
1695 lhs->setCanonID(m_nextID++);
1696 }
1697 add(m_accessList, e);
1698 } else {
1699 getCanonical(e);
1700 }
1701 break;
1702 }
1703
1704 case Expression::KindOfUnaryOpExpression: {
1705 UnaryOpExpressionPtr uop = spc(UnaryOpExpression, e);
1706 switch (uop->getOp()) {
1707 case T_INC:
1708 case T_DEC:
1709 {
1710 markAllLocalExprAltered(e);
1711 ExpressionPtr alt;
1712 int interf = findInterf(uop->getExpression(), true, alt);
1713 if (interf == SameAccess) {
1714 switch (alt->getKindOf()) {
1715 case Expression::KindOfAssignmentExpression:
1716 case Expression::KindOfBinaryOpExpression:
1717 case Expression::KindOfUnaryOpExpression:
1718 alt = alt->getStoreVariable();
1719 break;
1720 default:
1721 break;
1722 }
1723 always_assert(alt->getKindOf() == uop->getExpression()->getKindOf());
1724 uop->getExpression()->setCanonID(alt->getCanonID());
1725 } else {
1726 uop->getExpression()->setCanonID(m_nextID++);
1727 }
1728 }
1729 add(m_accessList, e);
1730 break;
1731 default:
1732 getCanonical(e);
1733 break;
1734 }
1735 break;
1736 }
1737
1738 case Expression::KindOfExpressionList:
1739 if (e->hasContext(Expression::UnsetContext) &&
1740 spc(ExpressionList, e)->getListKind() ==
1741 ExpressionList::ListKindParam) {
1742 ExpressionListPtr el = spc(ExpressionList, e);
1743 for (int i = el->getCount(); i--; ) {
1744 if ((*el)[i]->isScalar()) {
1745 el->removeElement(i);
1746 }
1747 }
1748 }
1749 // Fall through
1750 default:
1751 getCanonical(e);
1752 break;
1753 }
1754
1755 return ExpressionPtr();
1756 }
1757
1758 void AliasManager::canonicalizeKid(ConstructPtr c, ExpressionPtr kid, int i) {
1759 assert(c->getNthKid(i) == kid);
1760
1761 if (kid) {
1762 StatementPtr sp(dpc(Statement, c));
1763 if (sp) beginInExpression(sp, kid);
1764 kid = canonicalizeRecur(kid);
1765 if (kid) {
1766 c->setNthKid(i, kid);
1767 c->recomputeEffects();
1768 setChanged();
1769 }
1770 if (sp) {
1771 endInExpression(sp);
1772 ExpressionPtr kid0(dpc(Expression, c->getNthKid(i)));
1773 assert(kid0);
1774 kid0->computeLocalExprAltered();
1775 }
1776 }
1777 }
1778
1779 int AliasManager::canonicalizeKid(ConstructPtr c, ConstructPtr kid, int i) {
1780 assert(c->getNthKid(i) == kid);
1781
1782 int ret = FallThrough;
1783 if (kid) {
1784 ExpressionPtr e = dpc(Expression, kid);
1785 if (e) {
1786 canonicalizeKid(c, e, i);
1787 } else {
1788 StatementPtr s = dpc(Statement, kid);
1789 s = canonicalizeRecur(s, ret);
1790 if (s) {
1791 c->setNthKid(i, s);
1792 c->recomputeEffects();
1793 setChanged();
1794 }
1795 }
1796 }
1797 return ret;
1798 }
1799
1800 ExpressionPtr AliasManager::canonicalizeRecur(ExpressionPtr e) {
1801 if (e->isVisited()) return ExpressionPtr();
1802 if (ExpressionPtr rep = e->fetchReplacement()) {
1803 if (e->getContainedEffects() != rep->getContainedEffects()) {
1804 e->recomputeEffects();
1805 }
1806 return canonicalizeRecurNonNull(e->replaceValue(rep));
1807 }
1808
1809 bool delayVars = true;
1810 bool pushStack = false;
1811 bool inCall = false;
1812 bool setInCall = true;
1813
1814 switch (e->getKindOf()) {
1815 case Expression::KindOfQOpExpression: {
1816 QOpExpressionPtr qe(spc(QOpExpression, e));
1817 canonicalizeKid(e, qe->getCondition(), 0);
1818 beginScope();
1819 if (ExpressionPtr e1 = qe->getYes()) {
1820 canonicalizeKid(e, e1, 1);
1821 resetScope();
1822 }
1823 canonicalizeKid(e, qe->getNo(), 2);
1824 endScope();
1825 return canonicalizeNode(e);
1826 }
1827 case Expression::KindOfBinaryOpExpression: {
1828 BinaryOpExpressionPtr binop(spc(BinaryOpExpression, e));
1829 if (binop->isShortCircuitOperator()) {
1830 canonicalizeKid(e, binop->getExp1(), 0);
1831 beginScope();
1832 canonicalizeKid(e, binop->getExp2(), 1);
1833 endScope();
1834 return canonicalizeNode(e);
1835 }
1836 break;
1837 }
1838 case Expression::KindOfExpressionList:
1839 delayVars = false;
1840 break;
1841
1842 case Expression::KindOfSimpleFunctionCall:
1843 case Expression::KindOfNewObjectExpression:
1844 case Expression::KindOfDynamicFunctionCall:
1845 inCall = setInCall;
1846 case Expression::KindOfObjectMethodExpression:
1847 delayVars = false;
1848 // fall through
1849 pushStack = m_accessList.size() > 0;
1850 break;
1851
1852 default:
1853 break;
1854 }
1855
1856 ExpressionPtr aBack;
1857 if (pushStack) {
1858 aBack = m_accessList.back();
1859 assert(aBack);
1860 }
1861
1862 int n = e->getKidCount();
1863 if (n < 2) delayVars = false;
1864 if (e->is(Expression::KindOfAssignmentExpression)) delayVars = false;
1865
1866 m_inCall += inCall;
1867 for (int j = delayVars ? 0 : 1; j < 2; j++) {
1868 for (int i = 0; i < n; i++) {
1869 if (ExpressionPtr kid = e->getNthExpr(i)) {
1870 /*
1871 php doesnt evaluate simple variables at the point they are seen
1872 except in function parameters and function "addresses".
1873 So in a case like:
1874 $a + ($a = 5)
1875 the first $a is evaluated after the assignment. But in:
1876 ($a + 1) + ($a = 5)
1877 the first $a is evaluated before the assignment.
1878 To deal with this, if we're not dealing with a parameter list, and
1879 there's more than one child node, we do two passes, and process the
1880 simple variables on the second pass.
1881 */
1882 if (delayVars) {
1883 bool stash = !kid->is(Expression::KindOfSimpleVariable) ||
1884 spc(SimpleVariable, kid)->getAlwaysStash();
1885 if (stash == j) continue;
1886 }
1887 canonicalizeKid(e, kid, i);
1888 }
1889 }
1890 }
1891
1892 if (pushStack) m_exprBeginStack.push_back(aBack);
1893 ExpressionPtr ret(canonicalizeNode(e));
1894 if (pushStack) m_exprBeginStack.pop_back();
1895 m_inCall -= inCall;
1896 return ret;
1897 }
1898
1899 StatementPtr AliasManager::canonicalizeRecur(StatementPtr s, int &ret) {
1900 ret = FallThrough;
1901 if (!s || s->isVisited()) return StatementPtr();
1902
1903 // Dont handle nested functions
1904 // they will be dealt with by another
1905 // top level call to optimize
1906 if (FunctionWalker::SkipRecurse(s)) return StatementPtr();
1907
1908 Statement::KindOf stype = s->getKindOf();
1909 int start = 0;
1910 int nkid = s->getKidCount();
1911
1912 switch (stype) {
1913 case Statement::KindOfUseTraitStatement:
1914 case Statement::KindOfTraitPrecStatement:
1915 case Statement::KindOfTraitAliasStatement:
1916 return StatementPtr();
1917 case Statement::KindOfStaticStatement:
1918 clear();
1919 ret = Converge;
1920 break;
1921 case Statement::KindOfClassVariable:
1922 clear();
1923 ret = Branch;
1924 case Statement::KindOfClassConstant:
1925 case Statement::KindOfGlobalStatement:
1926 case Statement::KindOfUnsetStatement:
1927 case Statement::KindOfExpStatement:
1928 case Statement::KindOfStatementList:
1929 case Statement::KindOfBlockStatement:
1930 // No special action, just execute
1931 // and fall through
1932 break;
1933
1934 case Statement::KindOfIfStatement: {
1935 IfStatementPtr is = spc(IfStatement, s);
1936 StatementListPtr iflist = is->getIfBranches();
1937 if (iflist) {
1938 for (int i = 0, n = iflist->getKidCount(); i < n; i++) {
1939 IfBranchStatementPtr ifstmt = spc(IfBranchStatement, (*iflist)[i]);
1940 canonicalizeKid(ifstmt, ifstmt->getCondition(), 0);
1941 if (!i) beginScope();
1942 beginScope();
1943 canonicalizeKid(ifstmt, ifstmt->getStmt(), 1);
1944 endScope();
1945 if (i+1 < n) resetScope();
1946 }
1947 endScope();
1948 }
1949 ret = FallThrough;
1950 start = nkid;
1951 break;
1952 }
1953
1954 case Statement::KindOfIfBranchStatement:
1955 always_assert(0);
1956 break;
1957
1958 case Statement::KindOfForStatement: {
1959 ForStatementPtr fs(spc(ForStatement, s));
1960 canonicalizeKid(s, fs->getInitExp(), 0);
1961 clear();
1962 canonicalizeKid(s, fs->getCondExp(), 1);
1963 canonicalizeKid(s, fs->getBody(), 2);
1964 clear();
1965 canonicalizeKid(s, fs->getIncExp(), 3);
1966 ret = Converge;
1967 start = nkid;
1968 break;
1969 }
1970 case Statement::KindOfWhileStatement:
1971 case Statement::KindOfDoStatement:
1972 case Statement::KindOfForEachStatement:
1973 clear();
1974 ret = Converge;
1975 break;
1976
1977 case Statement::KindOfSwitchStatement: {
1978 SwitchStatementPtr ss(spc(SwitchStatement, s));
1979 canonicalizeKid(s, ss->getExp(), 0);
1980 clear();
1981 start = 1;
1982 ret = Converge;
1983 break;
1984 }
1985 case Statement::KindOfCaseStatement:
1986 case Statement::KindOfLabelStatement:
1987 clear();
1988 break;
1989
1990 case Statement::KindOfReturnStatement: {
1991 ReturnStatementPtr rs(spc(ReturnStatement, s));
1992 canonicalizeKid(s, rs->getRetExp(), 0);
1993 killLocals();
1994 ret = FallThrough;
1995 start = nkid;
1996 break;
1997 }
1998 case Statement::KindOfBreakStatement:
1999 case Statement::KindOfContinueStatement:
2000 case Statement::KindOfGotoStatement:
2001 ret = Branch;
2002 break;
2003
2004 case Statement::KindOfTryStatement: {
2005 TryStatementPtr trs(spc(TryStatement, s));
2006 beginScope();
2007 canonicalizeKid(s, trs->getBody(), 0);
2008 endScope();
2009 clear();
2010 canonicalizeKid(s, trs->getCatches(), 1);
2011 if (trs->getFinally()) {
2012 clear();
2013 canonicalizeKid(s, trs->getFinally(), 2);
2014 }
2015 ret = Converge;
2016 start = nkid;
2017 break;
2018 }
2019
2020 case Statement::KindOfFinallyStatement: {
2021 break;
2022 }
2023
2024 case Statement::KindOfTypedefStatement:
2025 break;
2026
2027 case Statement::KindOfCatchStatement:
2028 clear();
2029 ret = Converge;
2030 break;
2031
2032 case Statement::KindOfThrowStatement:
2033 ret = Branch;
2034 break;
2035
2036 case Statement::KindOfEchoStatement:
2037 {
2038 EchoStatementPtr es(spc(EchoStatement, s));
2039 ExpressionListPtr exprs = es->getExpressionList();
2040 for (int i = 0; i < exprs->getCount(); i++) {
2041 ExpressionPtr kid(exprs->getNthExpr(i));
2042 beginInExpression(es, kid);
2043 canonicalizeKid(exprs, kid, i);
2044 endInExpression(es);
2045 kid->computeLocalExprAltered();
2046 ExpressionPtr e(new ScalarExpression(BlockScopePtr(), LocationPtr(),
2047 T_STRING, string("io")));
2048 add(m_accessList, e);
2049 }
2050 ret = FallThrough;
2051 start = nkid;
2052 break;
2053 }
2054
2055 default:
2056 not_reached();
2057 }
2058
2059 for (int i = start; i < nkid; i++) {
2060 ConstructPtr cp = s->getNthKid(i);
2061 if (!cp) {
2062 continue;
2063 }
2064 int action = canonicalizeKid(s, cp, i);
2065 switch (action) {
2066 case FallThrough:
2067 case CondBranch:
2068 break;
2069 case Branch:
2070 clear();
2071 break;
2072 case Converge:
2073 clear();
2074 break;
2075 }
2076 }
2077
2078 s->setVisited();
2079 StatementPtr rep;
2080 if (m_preOpt) rep = s->preOptimize(m_arp);
2081 if (m_postOpt) rep = s->postOptimize(m_arp);
2082 if (rep) {
2083 s = canonicalizeRecur(rep, ret);
2084 return s ? s : rep;
2085 }
2086 return StatementPtr();
2087 }
2088
2089 int AliasManager::collectAliasInfoRecur(ConstructPtr cs, bool unused) {
2090 if (!cs) {
2091 return 0;
2092 }
2093
2094 cs->clearVisited();
2095
2096 StatementPtr s = dpc(Statement, cs);
2097 if (s) {
2098 switch (s->getKindOf()) {
2099 case Statement::KindOfFunctionStatement:
2100 case Statement::KindOfMethodStatement:
2101 case Statement::KindOfClassStatement:
2102 case Statement::KindOfInterfaceStatement:
2103 m_inlineAsExpr = false;
2104 return 0;
2105 default:
2106 break;
2107 }
2108 }
2109
2110 int nkid = cs->getKidCount();
2111 int kidCost = 0;
2112 for (int i = 0; i < nkid; i++) {
2113 ConstructPtr kid = cs->getNthKid(i);
2114 if (kid) {
2115 kidCost += collectAliasInfoRecur(kid, cs->kidUnused(i));
2116 }
2117 }
2118
2119 if (s) {
2120 bool inlineOk = false;
2121 Statement::KindOf skind = s->getKindOf();
2122 switch (skind) {
2123 case Statement::KindOfGlobalStatement:
2124 case Statement::KindOfStaticStatement:
2125 {
2126 ExpressionListPtr vars = (skind == Statement::KindOfGlobalStatement)
2127 ? spc(GlobalStatement, s)->getVars()
2128 : spc(StaticStatement, s)->getVars();
2129
2130 for (int i = 0, n = vars->getCount(); i < n; i++) {
2131 ExpressionPtr e = (*vars)[i];
2132 if (AssignmentExpressionPtr ae = dpc(AssignmentExpression, e)) {
2133 e = ae->getVariable();
2134 }
2135 if (SimpleVariablePtr sv = dpc(SimpleVariable, e)) {
2136 if (Symbol *sym = sv->getSymbol()) {
2137 sym->setReferenced();
2138 sym->setReseated();
2139 if (skind == Statement::KindOfGlobalStatement) {
2140 sym->setGlobal();
2141 } else if (!m_variables->isPseudoMainTable()) {
2142 m_variables->addStaticVariable(sym, m_arp);
2143 }
2144 }
2145 }
2146 }
2147 break;
2148 }
2149 case Statement::KindOfExpStatement:
2150 case Statement::KindOfStatementList:
2151 inlineOk = true;
2152 break;
2153 case Statement::KindOfCatchStatement:
2154 {
2155 CatchStatementPtr c(spc(CatchStatement, s));
2156 if (c->getVariable()->isThis()) {
2157 // Since catching $this results in re-assignment to $this, forcing
2158 // a variable table is the easiest way to force v_this to exist as
2159 // a local variable in the current scope. While this is clearly
2160 // not optimal, I don't believe there is a compelling reason to
2161 // optimize for this case.
2162 m_variables->setAttribute(VariableTable::ContainsLDynamicVariable);
2163 }
2164 }
2165 break;
2166 case Statement::KindOfReturnStatement:
2167 inlineOk = true;
2168 if (m_nrvoFix >= 0) {
2169 ExpressionPtr e = spc(ReturnStatement, s)->getRetExp();
2170 if (!e || !e->is(Expression::KindOfSimpleVariable)) {
2171 m_nrvoFix = -1;
2172 } else {
2173 SimpleVariablePtr sv = spc(SimpleVariable, e);
2174 const std::string &n = sv->getName();
2175 if (!m_nrvoFix) {
2176 m_returnVar = n;
2177 m_nrvoFix = 1;
2178 } else if (m_returnVar != n) {
2179 m_nrvoFix = -1;
2180 }
2181 }
2182 }
2183 break;
2184 case Statement::KindOfForEachStatement: {
2185 ForEachStatementPtr fs(static_pointer_cast<ForEachStatement>(s));
2186 SimpleVariablePtr name = dpc(SimpleVariable, fs->getNameExp());
2187 if (name) {
2188 Symbol *sym = name->getSymbol();
2189 sym->setNeeded();
2190 }
2191 SimpleVariablePtr value = dpc(SimpleVariable, fs->getValueExp());
2192 if (value) {
2193 Symbol *sym = value->getSymbol();
2194 sym->setNeeded();
2195 }
2196 break;
2197 }
2198 default:
2199 break;
2200 }
2201 if (!inlineOk) {
2202 m_inlineAsExpr = false;
2203 }
2204 } else {
2205 ExpressionPtr e = spc(Expression, cs);
2206 if (e->isNoRemove()) m_hasTypeAssertions = true;
2207 if (e->getContext() & Expression::DeadStore) m_hasDeadStore = true;
2208 e->setCanonID(0);
2209 if (!kidCost) {
2210 if (!nkid) {
2211 if (e->is(Expression::KindOfSimpleVariable)) {
2212 if (!e->isThis()) {
2213 Symbol *sym = spc(SimpleVariable, e)->getSymbol();
2214 if (!sym || !sym->isParameter()) kidCost = 1;
2215 }
2216 } else if (!e->isScalar()) {
2217 kidCost = 1;
2218 }
2219 } else if (e->getLocalEffects() & ~Expression::AccessorEffect) {
2220 kidCost = 1;
2221 }
2222 } else if (!e->is(Expression::KindOfExpressionList)) {
2223 ++kidCost;
2224 }
2225 e->setUnused(unused);
2226 int context = e->getContext();
2227 int ekind = e->getKindOf();
2228 switch (ekind) {
2229 case Expression::KindOfAssignmentExpression:
2230 {
2231 AssignmentExpressionPtr ae = spc(AssignmentExpression, e);
2232 ExpressionPtr var = ae->getVariable();
2233 ExpressionPtr val = ae->getValue();
2234 if (var->is(Expression::KindOfSimpleVariable)) {
2235 if (val->getContext() & Expression::RefValue) {
2236 if (Symbol *sym = spc(SimpleVariable, var)->getSymbol()) {
2237 sym->setReferenced();
2238 sym->setReseated();
2239 sym->setUsed();
2240 }
2241 } else {
2242 Expression::CheckNeeded(var, val);
2243 }
2244 }
2245 }
2246 break;
2247 case Expression::KindOfListAssignment:
2248 {
2249 ListAssignmentPtr la = spc(ListAssignment, e);
2250 ExpressionListPtr vars = la->getVariables();
2251 for (int i = vars->getCount(); i--; ) {
2252 ExpressionPtr v = (*vars)[i];
2253 if (v && v->is(Expression::KindOfSimpleVariable)) {
2254 SimpleVariablePtr sv = spc(SimpleVariable, v);
2255 if (Symbol *sym = spc(SimpleVariable, v)->getSymbol()) {
2256 sym->setNeeded();
2257 }
2258 }
2259 }
2260 }
2261 break;
2262 case Expression::KindOfSimpleVariable:
2263 {
2264 SimpleVariablePtr sv(spc(SimpleVariable, e));
2265 if (Symbol *sym = sv->getSymbol()) {
2266 bool ref = (context & (Expression::RefValue|
2267 Expression::RefAssignmentLHS)) ||
2268 sym->isRefClosureVar();
2269 if (ref) {
2270 sym->setReferenced();
2271 }
2272 bool unset = ((context & Expression::UnsetContext) &&
2273 (context & Expression::LValue));
2274 if (sv->isThis()) {
2275 sv->getFunctionScope()->setContainsThis();
2276 if (!e->hasContext(Expression::ObjectContext)) {
2277 sv->getFunctionScope()->setContainsBareThis(true, ref || unset);
2278 } else if (m_graph) {
2279 int &id = m_gidMap["v:this"];
2280 if (!id) id = m_gidMap.size();
2281 e->setCanonID(id);
2282 }
2283 } else if (m_graph) {
2284 m_objMap[sym->getName()] = sv;
2285 }
2286 if (unset) {
2287 sym->setReseated();
2288 }
2289 if (!(context & (Expression::AssignmentLHS |
2290 Expression::UnsetContext))) {
2291 sym->setUsed();
2292 }
2293 }
2294 }
2295 break;
2296 case Expression::KindOfDynamicVariable:
2297 m_variables->setAttribute(VariableTable::ContainsDynamicVariable);
2298 if (context & (Expression::RefValue|
2299 Expression::LValue)) {
2300 m_variables->setAttribute(VariableTable::ContainsLDynamicVariable);
2301 if (context & Expression::RefValue) {
2302 m_wildRefs = true;
2303 }
2304 }
2305 break;
2306 case Expression::KindOfIncludeExpression:
2307 {
2308 IncludeExpressionPtr inc(spc(IncludeExpression, e));
2309 m_variables->setAttribute(VariableTable::ContainsLDynamicVariable);
2310 }
2311 break;
2312 case Expression::KindOfArrayElementExpression:
2313 {
2314 int n = 1;
2315 while (n < 10 &&
2316 e->is(Expression::KindOfArrayElementExpression)) {
2317 e = spc(ArrayElementExpression, e)->getVariable();
2318 }
2319 if (e->is(Expression::KindOfSimpleVariable)) {
2320 if (Symbol *sym = spc(SimpleVariable, e)->getSymbol()) {
2321 if (context & Expression::RefValue) {
2322 sym->setReferenced();
2323 }
2324 sym->setUsed(); // need this for UnsetContext
2325 }
2326 }
2327 }
2328 break;
2329 case Expression::KindOfObjectPropertyExpression:
2330 {
2331 ExpressionPtr obj = spc(ObjectPropertyExpression, e)->getObject();
2332 if (obj->is(Expression::KindOfSimpleVariable)) {
2333 if (Symbol *sym = spc(SimpleVariable, obj)->getSymbol()) {
2334 if (context & Expression::RefValue) {
2335 sym->setReferenced();
2336 }
2337 sym->setUsed(); // need this for UnsetContext
2338 }
2339 }
2340 }
2341 break;
2342 case Expression::KindOfSimpleFunctionCall:
2343 {
2344 SimpleFunctionCallPtr sfc(spc(SimpleFunctionCall, e));
2345 if (sfc->getName() == "hphp_create_continuation") {
2346 m_inlineAsExpr = false;
2347 }
2348 sfc->updateVtFlags();
2349 }
2350 case Expression::KindOfDynamicFunctionCall:
2351 case Expression::KindOfClassConstantExpression:
2352 case Expression::KindOfStaticMemberExpression:
2353 case Expression::KindOfNewObjectExpression: {
2354 StaticClassName *p = dynamic_cast<StaticClassName*>(e.get());
2355 always_assert(p);
2356 bool useLSB = false;
2357 if (p->isStatic()) {
2358 useLSB = true;
2359 } else if (ekind == Expression::KindOfDynamicFunctionCall) {
2360 if ((p->getClassName().empty() && !p->getClass()) ||
2361 p->isParent() || p->isSelf()) {
2362 useLSB = true;
2363 }
2364 }
2365 if (useLSB) {
2366 m_scope->getContainingFunction()->setNextLSB(true);
2367 }
2368 if (m_graph) {
2369 const std::string &name = p->getClassName();
2370 if (!name.empty()) {
2371 int &id = m_gidMap[name];
2372 if (!id) id = m_gidMap.size();
2373 e->setCanonID(id);
2374 }
2375 }
2376 break;
2377 }
2378 case Expression::KindOfClosureExpression:
2379 // currently disable inlining for scopes with closure
2380 // expressions. TODO: revisit this later
2381 m_inlineAsExpr = false;
2382 break;
2383 case Expression::KindOfUnaryOpExpression:
2384 if (Option::EnableEval > Option::NoEval && spc(UnaryOpExpression, e)->
2385 getOp() == T_EVAL) {
2386 m_variables->setAttribute(VariableTable::ContainsLDynamicVariable);
2387 }
2388 break;
2389
2390 case Expression::KindOfBinaryOpExpression: {
2391 BinaryOpExpressionPtr b(spc(BinaryOpExpression, e));
2392 if (b->getOp() == T_INSTANCEOF) {
2393 ExpressionPtr s = b->getExp2();
2394 if (s->is(Expression::KindOfScalarExpression)) {
2395 ScalarExpressionPtr scalar(spc(ScalarExpression, s));
2396 if (!scalar->isQuoted() && scalar->getString() == "static") {
2397 m_scope->getContainingFunction()->setNextLSB(true);
2398 }
2399 }
2400 } else if (unused && b->isShortCircuitOperator()) {
2401 b->getExp2()->setUnused(true);
2402 }
2403 break;
2404 }
2405 case Expression::KindOfQOpExpression: {
2406 QOpExpressionPtr q(spc(QOpExpression, e));
2407 if (unused) {
2408 if (ExpressionPtr t1 = q->getYes()) t1->setUnused(true);
2409 q->getNo()->setUnused(true);
2410 }
2411 break;
2412 }
2413 default:
2414 break;
2415 }
2416 }
2417 return kidCost;
2418 }
2419
2420 void AliasManager::gatherInfo(AnalysisResultConstPtr ar, MethodStatementPtr m) {
2421 m_arp = ar;
2422 FunctionScopeRawPtr func = m->getFunctionScope();
2423 m_scope = func;
2424 m_variables = func->getVariables();
2425 m_variables->clearUsed();
2426 m_inPseudoMain = func->inPseudoMain();
2427
2428 if (ExpressionListPtr pPtr = m->getParams()) {
2429 ExpressionList &params = *pPtr;
2430 for (int i = params.getCount(); i--; ) {
2431 ParameterExpressionPtr p = spc(ParameterExpression, params[i]);
2432 if (Symbol *sym = m_variables->getSymbol(p->getName())) {
2433 if (sym->isCallTimeRef() || p->isRef()) {
2434 sym->setReferenced();
2435 }
2436 }
2437 }
2438 }
2439 if (ExpressionListPtr useVars = func->getClosureVars()) {
2440 for (int i = 0; i < useVars->getCount(); i++) {
2441 ParameterExpressionPtr p = dpc(ParameterExpression, (*useVars)[i]);
2442 assert(p);
2443 if (Symbol *sym = m_variables->getSymbol(p->getName())) {
2444 if (p->isRef()) {
2445 sym->setReferenced();
2446 sym->setUsed();
2447 }
2448 }
2449 }
2450 }
2451
2452 if (!m_inPseudoMain) {
2453 m_variables->clearAttribute(VariableTable::ContainsLDynamicVariable);
2454 m_variables->clearAttribute(VariableTable::ContainsDynamicVariable);
2455 m_variables->clearAttribute(VariableTable::ContainsCompact);
2456 m_variables->clearAttribute(VariableTable::ContainsExtract);
2457 }
2458
2459 func->setContainsThis(false);
2460 func->setContainsBareThis(false);
2461 func->setInlineSameContext(false);
2462 func->setNextLSB(false);
2463
2464 int i, nkid = m->getKidCount(), cost = 0;
2465 for (i = 0; i < nkid; i++) {
2466 ConstructPtr cp(m->getNthKid(i));
2467 int c = collectAliasInfoRecur(cp, false);
2468 if (cp == m->getStmts()) cost = c;
2469 }
2470
2471 if (m_inlineAsExpr) {
2472 if (cost > Option::AutoInline ||
2473 func->isVariableArgument() ||
2474 m_variables->getAttribute(VariableTable::ContainsDynamicVariable) ||
2475 m_variables->getAttribute(VariableTable::ContainsExtract) ||
2476 m_variables->getAttribute(VariableTable::ContainsCompact) ||
2477 m_variables->getAttribute(VariableTable::ContainsGetDefinedVars)) {
2478 m_inlineAsExpr = false;
2479 }
2480 }
2481 func->setInlineAsExpr(m_inlineAsExpr);
2482
2483 if (!func->nextLSB()) {
2484 if (func->usesLSB()) {
2485 func->clearUsesLSB();
2486 m_changes = true;
2487 }
2488 } else {
2489 func->setInlineSameContext(true);
2490 }
2491 }
2492
2493 static void markAvailable(ExpressionRawPtr e) {
2494 if (e->is(Expression::KindOfSimpleVariable)) {
2495 SimpleVariableRawPtr sv(spc(SimpleVariable,e));
2496 sv->setGuarded();
2497 sv->setNonNull();
2498 } else {
2499 StaticClassName *scn = dynamic_cast<StaticClassName*>(e.get());
2500 always_assert(scn);
2501 scn->setPresent();
2502 }
2503 }
2504
2505 class TypeAssertionInserter {
2506 public:
2507 explicit TypeAssertionInserter(AnalysisResultConstPtr ar) :
2508 m_ar(ar), m_changed(false) {
2509 BuildAssertionMap();
2510 }
2511 bool walk(StatementPtr stmt) {
2512 m_changed = false;
2513 createTypeAssertions(stmt);
2514 return m_changed;
2515 }
2516 private:
2517
2518 #define CONSTRUCT_PARAMS(from) \
2519 (from)->getScope(), (from)->getLocation()
2520
2521 AnalysisResultConstPtr m_ar;
2522 bool m_changed;
2523
2524 typedef std::pair<int, TypePtr> PosType;
2525 typedef hphp_hash_map<string, PosType, string_hash>
2526 StringPosTypeMap;
2527 typedef hphp_hash_map<string, SimpleVariablePtr, string_hash>
2528 StringVarMap;
2529
2530 static StringPosTypeMap s_type_assertion_map;
2531 static Mutex s_type_assertion_map_mutex;
2532
2533 static void BuildAssertionMap();
2534
2535 ExpressionPtr createTypeAssertionsForKids(ExpressionPtr parent,
2536 int startIdx,
2537 bool &passStmt,
2538 bool &negate) {
2539 ExpressionPtr rep;
2540 for (int i = startIdx; i < parent->getKidCount(); i++) {
2541 rep = createTypeAssertions(parent->getNthExpr(i), passStmt, negate);
2542 }
2543 return rep;
2544 }
2545
2546 void replaceExpression(
2547 ConstructPtr parent, ExpressionPtr rep, ExpressionPtr old, int kid) {
2548 assert(parent);
2549 assert(parent->getKidCount() > kid);
2550 assert(parent->getNthKid(kid) == old);
2551
2552 if (!rep) return;
2553
2554 rep->setActualType(old->getActualType());
2555 rep->setExpectedType(old->getExpectedType());
2556 rep->setImplementedType(old->getImplementedType());
2557 old->replaceValue(rep);
2558
2559 parent->setNthKid(kid, rep);
2560 m_changed = true;
2561 }
2562
2563 void replaceExpression(ExpressionPtr parent, ExpressionPtr rep, int kid) {
2564 replaceExpression(parent, rep, parent->getNthExpr(kid), kid);
2565 }
2566
2567 // returns the rep node for target, after the insertion
2568 ExpressionPtr insertTypeAssertion(ExpressionPtr assertion,
2569 ExpressionPtr target) {
2570 assert(assertion);
2571 assert(target);
2572 assert(assertion->is(Expression::KindOfSimpleVariable) ||
2573 assertion->is(Expression::KindOfExpressionList));
2574 assert(assertion->isNoRemove());
2575
2576 if (ExpressionListPtr el = dpc(ExpressionList, target)) {
2577 if (el->getListKind() == ExpressionList::ListKindComma) {
2578 assert(assertion->is(Expression::KindOfSimpleVariable));
2579 el->insertElement(assertion, el->getCount() - 1);
2580 return ExpressionPtr();
2581 }
2582 }
2583
2584 if (ExpressionListPtr el = dpc(ExpressionList, assertion)) {
2585 ExpressionListPtr el0 = spc(ExpressionList, el->clone());
2586 el0->insertElement(target, el0->getCount());
2587 return el0;
2588 }
2589
2590 ExpressionListPtr el(
2591 new ExpressionList(
2592 CONSTRUCT_PARAMS(target),
2593 ExpressionList::ListKindComma));
2594 if (target->isUnused()) {
2595 el->setUnused(true);
2596 }
2597 el->addElement(assertion);
2598 el->addElement(target);
2599 el->setNoRemove(); // since it contains an assertion
2600 return el;
2601 }
2602
2603 ExpressionPtr newTypeAssertion(ExpressionPtr base, TypePtr t) {
2604 assert(base->is(Expression::KindOfSimpleVariable));
2605 ExpressionPtr assertion(base->clone());
2606 assertion->setAssertedType(t);
2607 assertion->setNoRemove();
2608 return assertion;
2609 }
2610
2611 ExpressionPtr newInstanceOfAssertion(
2612 ExpressionPtr obj, ExpressionPtr clsName) {
2613 SimpleVariablePtr sv(extractAssertableVariable(obj));
2614 ScalarExpressionPtr se(dpc(ScalarExpression, clsName));
2615 if (sv && se) {
2616 const string &s = se->getLiteralString();
2617 if (s.empty()) return ExpressionPtr();
2618 TypePtr o(Type::CreateObjectType(Util::toLower(s)));
2619
2620 // don't do specific type assertions for unknown classes
2621 ClassScopePtr cscope(o->getClass(m_ar, sv->getScope()));
2622 if (!cscope) return newTypeAssertion(sv, Type::Object);
2623
2624 // don't do type assertions for interfaces, since
2625 // user classes don't necessarily extend the interface class
2626 // in C++
2627 if (cscope->isInterface()) {
2628 return newTypeAssertion(sv, Type::Object);
2629 }
2630
2631 // also don't do type assertions for derived by dynamic
2632 // classes, since these classes will be DynamicObjectData
2633 // instances at runtime (so we cannot emit a fast pointer cast
2634 // safely)
2635 if (cscope->derivedByDynamic()) {
2636 return newTypeAssertion(sv, Type::Object);
2637 }
2638
2639 return newTypeAssertion(sv, o);
2640 }
2641 return ExpressionPtr();
2642 }
2643
2644 SimpleVariablePtr extractAssertableVariable(ExpressionPtr e) {
2645 assert(e);
2646 switch (e->getKindOf()) {
2647 case Expression::KindOfSimpleVariable:
2648 return spc(SimpleVariable, e);
2649 case Expression::KindOfAssignmentExpression:
2650 {
2651 AssignmentExpressionPtr ae(spc(AssignmentExpression, e));
2652 return extractAssertableVariable(ae->getVariable());
2653 }
2654 default:
2655 break;
2656 }
2657 return SimpleVariablePtr();
2658 }
2659
2660 ExpressionPtr orAssertions(
2661 SimpleVariablePtr lhs,
2662 SimpleVariablePtr rhs) {
2663 assert(lhs && lhs->isNoRemove() && lhs->getAssertedType());
2664 assert(rhs && rhs->isNoRemove() && rhs->getAssertedType());
2665 assert(lhs->getName() == rhs->getName());
2666 TypePtr u(
2667 Type::Union(m_ar, lhs->getAssertedType(), rhs->getAssertedType()));
2668 ExpressionPtr lhs0(lhs->clone());
2669 lhs0->setAssertedType(u);
2670 return lhs0;
2671 }
2672
2673 ExpressionPtr andAssertions(
2674 SimpleVariablePtr lhs,
2675 SimpleVariablePtr rhs) {
2676 assert(lhs && lhs->isNoRemove() && lhs->getAssertedType());
2677 assert(rhs && rhs->isNoRemove() && rhs->getAssertedType());
2678 assert(lhs->getName() == rhs->getName());
2679 TypePtr i(
2680 Type::Intersection(
2681 m_ar, lhs->getAssertedType(), rhs->getAssertedType()));
2682 ExpressionPtr lhs0(lhs->clone());
2683 lhs0->setAssertedType(i);
2684 return lhs0;
2685 }
2686
2687 ExpressionPtr orAssertions(ExpressionPtr lhs, ExpressionPtr rhs) {
2688 if (!lhs || !rhs) return ExpressionPtr();
2689
2690 assert(lhs->is(Expression::KindOfSimpleVariable) ||
2691 lhs->is(Expression::KindOfExpressionList));
2692 assert(rhs->is(Expression::KindOfSimpleVariable) ||
2693 rhs->is(Expression::KindOfExpressionList));
2694
2695 if (lhs->is(Expression::KindOfSimpleVariable) &&
2696 rhs->is(Expression::KindOfSimpleVariable) &&
2697 spc(SimpleVariable, lhs)->getName() ==
2698 spc(SimpleVariable, rhs)->getName()) {
2699 return orAssertions(
2700 spc(SimpleVariable, lhs),
2701 spc(SimpleVariable, rhs));
2702 }
2703
2704 return ExpressionPtr();
2705 }
2706
2707 bool isAllScalar(ExpressionListPtr ep, int startIdx) {
2708 assert(ep && ep->getListKind() == ExpressionList::ListKindParam);
2709 for (int i = startIdx; i < ep->getCount(); i++) {
2710 ExpressionPtr c((*ep)[i]);
2711 if (c && !c->isScalar()) return false;
2712 }
2713 return true;
2714 }
2715
2716 ExpressionPtr createTypeAssertions(ExpressionPtr from,
2717 bool &passStmt,
2718 bool &negate) {
2719 passStmt = false;
2720 negate = false;
2721 if (!from) return ExpressionPtr();
2722 int startIdx = 0;
2723 bool useKidValue = true;
2724 switch (from->getKindOf()) {
2725 case Expression::KindOfExpressionList:
2726 {
2727 ExpressionListPtr p(spc(ExpressionList, from));
2728 switch (p->getListKind()) {
2729 case ExpressionList::ListKindComma:
2730 return createTypeAssertions(p->listValue(), passStmt, negate);
2731 default:
2732 break;
2733 }
2734 }
2735 break;
2736 case Expression::KindOfSimpleFunctionCall:
2737 {
2738 SimpleFunctionCallPtr p(spc(SimpleFunctionCall, from));
2739 ExpressionListPtr ep(p->getParams());
2740 StringPosTypeMap::const_iterator it(
2741 s_type_assertion_map.find(p->getName()));
2742 if (it != s_type_assertion_map.end()) {
2743 int pos = it->second.first;
2744 TypePtr t(it->second.second);
2745 if (ep->getCount() - 1 >= pos && isAllScalar(ep, pos + 1)) {
2746 ExpressionPtr a0((*ep)[pos]);
2747 if (a0) {
2748 SimpleVariablePtr sv(extractAssertableVariable(a0));
2749 if (sv) {
2750 bool passStmt;
2751 bool negate;
2752 createTypeAssertionsForKids(from, 2, passStmt, negate);
2753 return newTypeAssertion(sv, t);
2754 }
2755 }
2756 }
2757 } else if (p->getName() == "is_a" &&
2758 (ep->getCount() >= 2 && isAllScalar(ep, 1))) {
2759 // special case is_a
2760 bool passStmt;
2761 bool negate;
2762 createTypeAssertionsForKids(from, 2, passStmt, negate);
2763 return newInstanceOfAssertion((*ep)[0], (*ep)[1]);
2764 }
2765 startIdx = 2; // params
2766 }
2767 break;
2768 case Expression::KindOfQOpExpression:
2769 {
2770 QOpExpressionPtr qop(spc(QOpExpression, from));
2771 bool passStmt;
2772 bool negateChild;
2773 ExpressionPtr lAfter(
2774 createTypeAssertions(
2775 qop->getCondition(),
2776 passStmt,
2777 negateChild));
2778 if (lAfter) {
2779 if (negateChild || qop->getYes()) {
2780 replaceExpression(
2781 qop,
2782 insertTypeAssertion(
2783 lAfter,
2784 !negateChild ? qop->getYes() : qop->getNo()),
2785 !negateChild ? 1 : 2);
2786 }
2787 }
2788 startIdx = 1; // yes expr
2789 useKidValue = false;
2790 }
2791 break;
2792 case Expression::KindOfBinaryOpExpression:
2793 {
2794 BinaryOpExpressionPtr binop(spc(BinaryOpExpression, from));
2795 switch (binop->getOp()) {
2796 case T_LOGICAL_AND:
2797 case T_BOOLEAN_AND:
2798 {
2799 // we cannot push the LHS assertion into the expr
2800 // past the RHS assertion, since the RHS assertion could
2801 // have changed the LHS assertion. for example:
2802 //
2803 // if (is_array($x) && ($x = 5)) { stmt1; }
2804 //
2805 // All we can do is to push the LHS assertion into the beginning
2806 // of the RHS assertion, and then return the RHS assertion. We
2807 // would need more analysis to do more (eg copy prop of
2808 // assertions)
2809 bool passStmt;
2810 bool negateChild;
2811 ExpressionPtr lhsAfter(
2812 createTypeAssertions(
2813 binop->getExp1(),
2814 passStmt,
2815 negateChild));
2816 if (lhsAfter && !negateChild) {
2817 replaceExpression(
2818 binop,
2819 insertTypeAssertion(lhsAfter, binop->getExp2()),
2820 1);
2821 }
2822 ExpressionPtr rhsAfter(
2823 createTypeAssertions(
2824 binop->getExp2(),
2825 passStmt,
2826 negateChild));
2827 return negateChild ? ExpressionPtr() : rhsAfter;
2828 }
2829 case T_LOGICAL_OR:
2830 case T_BOOLEAN_OR:
2831 {
2832 bool passStmt;
2833 bool negateChild1;
2834 bool negateChild2;
2835 ExpressionPtr lhsAfter(
2836 createTypeAssertions(
2837 binop->getExp1(),
2838 passStmt,
2839 negateChild1));
2840 ExpressionPtr rhsAfter(
2841 createTypeAssertions(
2842 binop->getExp2(),
2843 passStmt,
2844 negateChild2));
2845 if (lhsAfter && rhsAfter && !negateChild1 && !negateChild2) {
2846 return orAssertions(lhsAfter, rhsAfter);
2847 }
2848 return ExpressionPtr();
2849 }
2850 case T_INSTANCEOF:
2851 {
2852 ExpressionPtr r(newInstanceOfAssertion(
2853 binop->getExp1(), binop->getExp2()));
2854 if (r) return r;
2855 }
2856 }
2857 }
2858 break;
2859 case Expression::KindOfUnaryOpExpression:
2860 {
2861 UnaryOpExpressionPtr unop(spc(UnaryOpExpression, from));
2862 switch (unop->getOp()) {
2863 case '!':
2864 {
2865 bool passStmt;
2866 ExpressionPtr after(
2867 createTypeAssertions(
2868 unop->getExpression(), passStmt, negate));
2869 negate = !negate;
2870 return after;
2871 }
2872 default:
2873 // do the default behavior
2874 break;
2875 }
2876 }
2877 break;
2878 case Expression::KindOfAssignmentExpression:
2879 {
2880 // handle $x = (type) $x explicitly,
2881 // since our current type inference will not be
2882 // able to deal with it optimally
2883 AssignmentExpressionPtr ap(spc(AssignmentExpression, from));
2884 SimpleVariablePtr sv(dpc(SimpleVariable, ap->getVariable()));
2885 UnaryOpExpressionPtr uop(dpc(UnaryOpExpression, ap->getValue()));
2886 if (sv && uop) {
2887 TypePtr castType(uop->getCastType());
2888 if (castType) {
2889 if (SimpleVariablePtr sv0 =
2890 dpc(SimpleVariable, uop->getExpression())) {
2891 if (sv->getName() == sv0->getName()) {
2892 passStmt = true;
2893 return newTypeAssertion(sv, castType);
2894 }
2895 }
2896 }
2897 }
2898 useKidValue = false;
2899 }
2900 break;
2901 default:
2902 break;
2903 }
2904 ExpressionPtr result(
2905 createTypeAssertionsForKids(from, startIdx, passStmt, negate));
2906 return useKidValue ? result : ExpressionPtr();
2907 }
2908
2909 void insertTypeAssertion(
2910 ExpressionPtr assertion,
2911 StatementPtr stmt,
2912 int idx = 0) {
2913 if (!stmt) return;
2914
2915 m_changed = true;
2916 switch (stmt->getKindOf()) {
2917 case Statement::KindOfBlockStatement:
2918 {
2919 BlockStatementPtr blockPtr(spc(BlockStatement, stmt));
2920 insertTypeAssertion(assertion, blockPtr->getStmts());
2921 }
2922 break;
2923 case Statement::KindOfStatementList:
2924 {
2925 StatementListPtr slistPtr(spc(StatementList, stmt));
2926 slistPtr->insertElement(
2927 ExpStatementPtr(
2928 new ExpStatement(
2929 CONSTRUCT_PARAMS(slistPtr), assertion)),
2930 idx);
2931 }
2932 break;
2933 case Statement::KindOfExpStatement:
2934 {
2935 ExpStatementPtr es(spc(ExpStatement, stmt));
2936 ExpressionPtr rep(
2937 insertTypeAssertion(assertion, es->getExpression()));
2938 replaceExpression(es, rep, es->getExpression(), 0);
2939 }
2940 break;
2941 case Statement::KindOfReturnStatement:
2942 {
2943 ReturnStatementPtr rs(spc(ReturnStatement, stmt));
2944 if (rs->hasRetExp()) {
2945 ExpressionPtr rep(
2946 insertTypeAssertion(assertion, rs->getRetExp()));
2947 replaceExpression(rs, rep, rs->getRetExp(), 0);
2948 }
2949 }
2950 break;
2951 case Statement::KindOfBreakStatement:
2952 {
2953 BreakStatementPtr bs(spc(BreakStatement, stmt));
2954 if (bs->getExp()) {
2955 ExpressionPtr rep(
2956 insertTypeAssertion(assertion, bs->getExp()));
2957 replaceExpression(bs, rep, bs->getExp(), 0);
2958 }
2959 }
2960 default:
2961 // this is something like a continue statement,
2962 // in which case we don't do anything
2963 break;
2964 }
2965 }
2966
2967 ExpressionPtr createTypeAssertions(StatementPtr e) {
2968 if (!e) return ExpressionPtr();
2969 if (FunctionWalker::SkipRecurse(e)) return ExpressionPtr();
2970
2971 ExpressionPtr loopCond;
2972 StatementPtr loopBody;
2973 std::vector<ExpressionPtr> needed;
2974 switch (e->getKindOf()) {
2975 case Statement::KindOfIfStatement:
2976 {
2977 IfStatementPtr ifStmt(spc(IfStatement, e));
2978 StatementListPtr branches(ifStmt->getIfBranches());
2979 if (branches) {
2980 for (int i = 0; i < branches->getCount(); i++) {
2981 IfBranchStatementPtr branch(
2982 dpc(IfBranchStatement, (*branches)[i]));
2983 assert(branch);
2984 if (branch->getCondition()) {
2985 bool passStmt;
2986 bool negate;
2987 ExpressionPtr after(
2988 createTypeAssertions(
2989 branch->getCondition(), passStmt, negate));
2990 if (after) {
2991 if (!negate) {
2992 insertTypeAssertion(after, branch->getStmt());
2993 } else {
2994 // insert into the next branch:
2995 // * if a condition exists, put it in the condition.
2996 // * if there is no condition, put it in the body.
2997 // * if this is the last branch, create a branch after
2998 // with no condition, and put it in the body.
2999
3000 if (i < branches->getCount() - 1) {
3001 IfBranchStatementPtr nextBranch(
3002 dpc(IfBranchStatement, (*branches)[i + 1]));
3003 assert(nextBranch);
3004 if (nextBranch->getCondition()) {
3005 ExpressionPtr old(nextBranch->getCondition());
3006 replaceExpression(
3007 nextBranch,
3008 insertTypeAssertion(after, old),
3009 old,
3010 0);
3011 } else {
3012 // next branch must be the last branch
3013 assert(i + 1 == branches->getCount() - 1);
3014 insertTypeAssertion(after, nextBranch->getStmt());
3015 }
3016 } else {
3017 ExpStatementPtr newExpStmt(
3018 new ExpStatement(
3019 CONSTRUCT_PARAMS(branch),
3020 after));
3021
3022 IfBranchStatementPtr newBranch(
3023 new IfBranchStatement(
3024 CONSTRUCT_PARAMS(branch),
3025 ExpressionPtr(), newExpStmt));
3026
3027 branches->addElement(newBranch);
3028 break;
3029 }
3030 }
3031 }
3032 }
3033 }
3034 for (int i = 0; i < branches->getCount(); i++) {
3035 IfBranchStatementPtr branch(
3036 dpc(IfBranchStatement, (*branches)[i]));
3037 assert(branch);
3038 if (branch->getStmt()) {
3039 createTypeAssertions(branch->getStmt());
3040 }
3041 }
3042 }
3043 }
3044 return ExpressionPtr();
3045 case Statement::KindOfForStatement: {
3046 ForStatementPtr fs(static_pointer_cast<ForStatement>(e));
3047 loopCond = fs->getCondExp();
3048 loopBody = fs->getBody();
3049 needed.push_back(fs->getInitExp());
3050 needed.push_back(fs->getIncExp());
3051 goto loop_stmt;
3052 }
3053 case Statement::KindOfWhileStatement: {
3054 WhileStatementPtr ws(static_pointer_cast<WhileStatement>(e));
3055 loopCond = ws->getCondExp();
3056 loopBody = ws->getBody();
3057 goto loop_stmt;
3058 }
3059 case Statement::KindOfDoStatement: {
3060 DoStatementPtr ds(static_pointer_cast<DoStatement>(e));
3061 loopCond = ds->getCondExp();
3062 loopBody = ds->getBody();
3063 }
3064
3065 loop_stmt:
3066 {
3067 if (loopCond) {
3068 bool passStmt;
3069 bool negate;
3070 ExpressionPtr after(createTypeAssertions(loopCond, passStmt, negate));
3071 if (after && !negate) {
3072 insertTypeAssertion(after, loopBody);
3073 }
3074 }
3075 for (auto it = needed.begin(); it != needed.end(); ++it) {
3076 ExpressionPtr k(dpc(Expression, *it));
3077 if (k) {
3078 bool passStmt;
3079 bool negate;
3080 createTypeAssertions(k, passStmt, negate);
3081 }
3082 }
3083 createTypeAssertions(loopBody);
3084 }
3085 return ExpressionPtr();
3086 case Statement::KindOfStatementList:
3087 {
3088 StatementListPtr slist(spc(StatementList, e));
3089 int i = 0;
3090 while (i < slist->getCount()) {
3091 ExpressionPtr next(createTypeAssertions((*slist)[i]));
3092 if (next) {
3093 insertTypeAssertion(next, slist, i + 1);
3094 i += 2; // skip over the inserted node
3095 } else {
3096 i++;
3097 }
3098 }
3099 }
3100 return ExpressionPtr();
3101 case Statement::KindOfExpStatement:
3102 {
3103 ExpStatementPtr es(dpc(ExpStatement, e));
3104 bool passStmt;
3105 bool negate;
3106 ExpressionPtr after(
3107 createTypeAssertions(es->getExpression(), passStmt, negate));
3108 return passStmt && !negate ? after : ExpressionPtr();
3109 }
3110 default:
3111 break;
3112 }
3113 for (int i = 0; i < e->getKidCount(); i++) {
3114 ConstructPtr kid(e->getNthKid(i));
3115 if (!kid) continue;
3116 if (StatementPtr s = dpc(Statement, kid)) {
3117 createTypeAssertions(s);
3118 } else if (ExpressionPtr e = dpc(Expression, kid)) {
3119 bool passStmt;
3120 bool negate;
3121 createTypeAssertions(e, passStmt, negate);
3122 } else {
3123 assert(false);
3124 }
3125 }
3126 return ExpressionPtr();
3127 }
3128
3129 };
3130
3131 TypeAssertionInserter::StringPosTypeMap
3132 TypeAssertionInserter::s_type_assertion_map;
3133 Mutex
3134 TypeAssertionInserter::s_type_assertion_map_mutex;
3135
3136 void TypeAssertionInserter::BuildAssertionMap() {
3137 Lock lock(s_type_assertion_map_mutex);
3138 if (s_type_assertion_map.empty()) {
3139 s_type_assertion_map["is_array"] = PosType(0, Type::Array);
3140 s_type_assertion_map["is_string"] = PosType(0, Type::String);
3141 s_type_assertion_map["is_object"] = PosType(0, Type::Object);
3142
3143 s_type_assertion_map["is_int"] = PosType(0, Type::Int64);
3144 s_type_assertion_map["is_integer"] = PosType(0, Type::Int64);
3145 s_type_assertion_map["is_long"] = PosType(0, Type::Int64);
3146
3147 s_type_assertion_map["is_double"] = PosType(0, Type::Double);
3148 s_type_assertion_map["is_float"] = PosType(0, Type::Double);
3149 s_type_assertion_map["is_real"] = PosType(0, Type::Double);
3150
3151 s_type_assertion_map["is_bool"] = PosType(0, Type::Boolean);
3152
3153 s_type_assertion_map["is_numeric"] = PosType(0, Type::Numeric);
3154
3155 s_type_assertion_map["in_array"] = PosType(1, Type::Array);
3156
3157 // even though the PHP docs say that in PHP 5.3, this function
3158 // only accepts an array for the search, Zend PHP 5.3 still
3159 // accepts objects. Quite a bummer.
3160 s_type_assertion_map["array_key_exists"] =
3161 PosType(1,
3162 TypePtr(
3163 new Type(
3164 (Type::KindOf)(Type::KindOfArray|Type::KindOfObject))));
3165 }
3166 }
3167
3168 class TypeAssertionRemover {
3169 public:
3170 TypeAssertionRemover() : m_changed(false) {}
3171 bool walk(StatementPtr stmt) {
3172 m_changed = false;
3173 removeTypeAssertions(stmt);
3174 return m_changed;
3175 }
3176 private:
3177
3178 bool m_changed;
3179
3180 void safeRepValue(ConstructPtr parent, int i,
3181 ExpressionPtr orig, ExpressionPtr rep) {
3182 if (orig == rep) return;
3183 m_changed = true;
3184 return parent->setNthKid(i, orig->replaceValue(rep));
3185 }
3186
3187 void safeRepValue(ConstructPtr parent, int i,
3188 ConstructPtr orig, ConstructPtr rep) {
3189 if (orig == rep) return;
3190 m_changed = true;
3191 return parent->setNthKid(i, rep);
3192 }
3193
3194 /**
3195 * Returns the replacement node for from
3196 */
3197 ConstructPtr removeTypeAssertions(ConstructPtr from) {
3198 if (!from) return ConstructPtr();
3199 if (StatementPtr s = dpc(Statement, from)) {
3200 return removeTypeAssertions(s);
3201 } else if (ExpressionPtr e = dpc(Expression, from)) {
3202 return removeTypeAssertions(e);
3203 } else {
3204 assert(false);
3205 return ConstructPtr();
3206 }
3207 }
3208
3209 ExpressionPtr restoreExpType(ExpressionPtr orig, ExpressionPtr rep) {
3210 rep->setExpectedType(orig->getExpectedType());
3211 return rep;
3212 }
3213
3214 ExpressionPtr removeTypeAssertions(ExpressionPtr from) {
3215 if (!from) return ExpressionPtr();
3216 switch (from->getKindOf()) {
3217 case Expression::KindOfExpressionList:
3218 {
3219 ExpressionListPtr p(spc(ExpressionList, from));
3220 if (p->getListKind() ==
3221 ExpressionList::ListKindComma) {
3222 for (int i = 0; i < p->getCount(); i++) {
3223 ExpressionPtr c((*p)[i]);
3224 ExpressionPtr rep(removeTypeAssertions(c));
3225 if (!rep) p->removeElement(i--);
3226 else safeRepValue(p, i, c, rep);
3227 }
3228 if (p->isNoRemove()) {
3229 if (p->getCount() == 0) return ExpressionPtr();
3230 if (p->getCount() == 1) return restoreExpType(p, (*p)[0]);
3231 }
3232 }
3233 }
3234 break;
3235 case Expression::KindOfSimpleVariable:
3236 if (from->isNoRemove()) return ExpressionPtr();
3237 break;
3238 default:
3239 break;
3240 }
3241 for (int i = 0; i < from->getKidCount(); i++) {
3242 ExpressionPtr c(from->getNthExpr(i));
3243 ExpressionPtr rep(removeTypeAssertions(c));
3244 safeRepValue(from, i, c, rep);
3245 }
3246 return from;
3247 }
3248
3249 StatementPtr removeTypeAssertions(StatementPtr from) {
3250 if (!from) return from;
3251 if (FunctionWalker::SkipRecurse(from)) return from;
3252
3253 switch (from->getKindOf()) {
3254 case Statement::KindOfExpStatement:
3255 {
3256 ExpStatementPtr p(spc(ExpStatement, from));
3257 ExpressionPtr rep(removeTypeAssertions(p->getExpression()));
3258 if (!rep) return StatementPtr();
3259 else safeRepValue(p, 0, p->getExpression(), rep);
3260 }
3261 break;
3262 case Statement::KindOfStatementList:
3263 {
3264 StatementListPtr p(spc(StatementList, from));
3265 for (int i = 0; i < p->getKidCount(); i++) {
3266 StatementPtr s((*p)[i]);
3267 StatementPtr rep(removeTypeAssertions(s));
3268 if (!rep) p->removeElement(i--);
3269 else safeRepValue(from, i, s, rep);
3270 }
3271 }
3272 break;
3273 default:
3274 {
3275 for (int i = 0; i < from->getKidCount(); i++) {
3276 ConstructPtr c(from->getNthKid(i));
3277 ConstructPtr rep(removeTypeAssertions(c));
3278 safeRepValue(from, i, c, rep);
3279 }
3280 }
3281 break;
3282 }
3283 return from;
3284 }
3285
3286 };
3287
3288 static bool isNewResult(ExpressionPtr e) {
3289 if (!e) return false;
3290 if (e->is(Expression::KindOfNewObjectExpression)) return true;
3291 if (e->is(Expression::KindOfAssignmentExpression)) {
3292 return isNewResult(spc(AssignmentExpression, e)->getValue());
3293 }
3294 if (e->is(Expression::KindOfExpressionList)) {
3295 return isNewResult(spc(ExpressionList, e)->listValue());
3296 }
3297 return false;
3298 }
3299
3300 class ConstructTagger : public DataFlowWalker {
3301 public:
3302 ConstructTagger(ControlFlowGraph *g,
3303 std::map<std::string,int> &gidMap) :
3304 DataFlowWalker(g), m_gidMap(gidMap) {}
3305
3306 void walk(MethodStatementPtr m) {
3307 DataFlowWalker::walk(*this);
3308 ControlBlock *b = m_graph.getDfBlock(1);
3309 std::map<std::string,int>::iterator it = m_gidMap.find("v:this");
3310 if (m->getOrigGeneratorFunc()) {
3311 BitOps::set(m_gidMap.size(), b->getRow(DataFlow::PRefIn),
3312 BitOps::Bits(-1));
3313 BitOps::set(m_gidMap.size(), b->getRow(DataFlow::PInitIn),
3314 BitOps::Bits(-1));
3315 } else {
3316 if (it != m_gidMap.end() && it->second) {
3317 b->setBit(DataFlow::PRefIn, it->second);
3318 b->setBit(DataFlow::PInitIn, it->second);
3319 }
3320 updateParamInfo(m->getParams(), Option::HardTypeHints);
3321 updateParamInfo(m->getFunctionScope()->getClosureVars(), false);
3322 }
3323 }
3324
3325 void updateParamInfo(ExpressionListPtr el, bool useDefaults) {
3326 if (!el) return;
3327 ControlBlock *b = m_graph.getDfBlock(1);
3328 for (int i = el->getCount(); i--; ) {
3329 ParameterExpressionPtr p =
3330 static_pointer_cast<ParameterExpression>((*el)[i]);
3331 std::map<std::string,int>::iterator it =
3332 m_gidMap.find("v:" + p->getName());
3333 if (it != m_gidMap.end() && it->second) {
3334 if (useDefaults && p->hasTypeHint() && !p->defaultValue()) {
3335 b->setBit(DataFlow::AvailIn, it->second);
3336 }
3337 b->setBit(DataFlow::PRefIn, it->second);
3338 b->setBit(DataFlow::PInitIn, it->second);
3339 }
3340 }
3341 }
3342
3343 void processAccess(ExpressionPtr e) {
3344 int id = e->getCanonID();
3345 if (id) {
3346 if (e->isThis() && e->getAssertedType()) {
3347 markAvailable(e);
3348 }
3349 if (m_block->getBit(DataFlow::Available, id)) {
3350 markAvailable(e);
3351 e->clearAnticipated();
3352 } else {
3353 m_block->setBit(DataFlow::Available, id);
3354 e->setAnticipated();
3355 }
3356 } else {
3357 bool set = true, maybeRef = true;
3358 SimpleVariablePtr sv;
3359 if (e->is(Expression::KindOfSimpleVariable)) {
3360 sv = spc(SimpleVariable, e);
3361 set = (e->isThis() && e->hasContext(Expression::ObjectContext));
3362 if (e->getAssertedType()) {
3363 markAvailable(sv);
3364 set = true;
3365 }
3366 } else {
3367 if (e->is(Expression::KindOfObjectMethodExpression)) {
3368 ExpressionPtr a(spc(ObjectMethodExpression, e)->getObject());
3369 while (true) {
3370 if (a->is(Expression::KindOfObjectPropertyExpression)) {
3371 a = spc(ObjectPropertyExpression, a)->getObject();
3372 } else if (a->is(Expression::KindOfArrayElementExpression)) {
3373 a = spc(ArrayElementExpression, a)->getVariable();
3374 } else if (a->is(Expression::KindOfAssignmentExpression)) {
3375 a = spc(AssignmentExpression, a)->getValue();
3376 } else if (a->is(Expression::KindOfExpressionList)) {
3377 a = spc(ExpressionList, a)->listValue();
3378 } else {
3379 break;
3380 }
3381 }
3382 if (a->is(Expression::KindOfSimpleVariable)) {
3383 sv = spc(SimpleVariable, a);
3384 }
3385 } else if (e->is(Expression::KindOfObjectPropertyExpression)) {
3386 ObjectPropertyExpressionPtr op(spc(ObjectPropertyExpression, e));
3387 if (op->getObject()->is(Expression::KindOfSimpleVariable)) {
3388 sv = spc(SimpleVariable, op->getObject());
3389 set = false;
3390 }
3391 } else if (e->is(Expression::KindOfAssignmentExpression)) {
3392 AssignmentExpressionPtr ae(spc(AssignmentExpression, e));
3393 if (ae->getVariable()->is(Expression::KindOfSimpleVariable)) {
3394 sv = spc(SimpleVariable, ae->getVariable());
3395 set = isNewResult(ae->getValue());
3396 if (!sv->couldBeAliased() &&
3397 (ae->getValue()->isScalar() ||
3398 (ae->getValue()->getActualType() &&
3399 ae->getValue()->getActualType()->getKindOf() <
3400 Type::KindOfString))) {
3401 maybeRef = false;
3402 }
3403 }
3404 }
3405 if (sv && sv->isThis()) sv.reset();
3406 }
3407 if (sv) {
3408 id = m_gidMap["v:" + sv->getName()];
3409 if (id) {
3410 if (sv == e) {
3411 sv->clearAnticipated();
3412 if (m_block->getBit(DataFlow::Killed, id)) {
3413 sv->setKilled();
3414 } else {
3415 sv->clearKilled();
3416 }
3417 if (m_block->getBit(DataFlow::Referenced, id)) {
3418 sv->setRefCounted();
3419 sv->setKilled();
3420 }
3421 if (m_block->getBit(DataFlow::Inited, id)) {
3422 sv->setInited();
3423 sv->setKilled();
3424 }
3425 if (sv->hasAllContext(Expression::UnsetContext|
3426 Expression::LValue)) {
3427 m_block->setBit(DataFlow::Available, id, false);
3428 m_block->setBit(DataFlow::Altered, id, true);
3429 m_block->setBit(DataFlow::Killed, id, true);
3430 m_block->setBit(DataFlow::Referenced, id, false);
3431 m_block->setBit(DataFlow::Inited, id, false);
3432 return;
3433 }
3434 bool ref = sv->hasAnyContext(Expression::RefValue|
3435 Expression::InvokeArgument|
3436 Expression::DeepReference|
3437 Expression::DeepAssignmentLHS|
3438 Expression::DeepOprLValue);
3439
3440 bool mod =
3441 sv->hasAllContext(Expression::Declaration) ||
3442 sv->hasAnyContext(Expression::AssignmentLHS|
3443 Expression::OprLValue) ||
3444 (!ref && sv->hasContext(Expression::LValue));
3445
3446 if (mod) {
3447 m_block->setBit(DataFlow::Available, id, false);
3448 m_block->setBit(DataFlow::Altered, id, true);
3449 }
3450 if (mod || ref) {
3451 m_block->setBit(DataFlow::Referenced, id, true);
3452 m_block->setBit(DataFlow::Inited, id, true);
3453 bool kill = true;
3454
3455 if (!mod) {
3456 if (TypePtr act = sv->getActualType()) {
3457 if (sv->hasContext(Expression::ObjectContext)) {
3458 if (act->is(Type::KindOfObject)) kill = false;
3459 } else if (sv->hasContext(Expression::AccessContext)) {
3460 if (act->is(Type::KindOfArray)) kill = false;
3461 }
3462 }
3463 }
3464 if (kill) {
3465 m_block->setBit(DataFlow::Killed, id, true);
3466 return;
3467 }
3468 }
3469
3470 if (!sv->couldBeAliased()) {
3471 if (m_block->getBit(DataFlow::Available, id)) {
3472 markAvailable(sv);
3473 } else {
3474 if (!m_block->getBit(DataFlow::Altered, id)) {
3475 sv->setAnticipated();
3476 }
3477 if (set && !sv->hasAnyContext(Expression::ExistContext|
3478 Expression::UnsetContext)) {
3479 m_block->setBit(DataFlow::Available, id, true);
3480 }
3481 }
3482 }
3483 } else {
3484 if (!maybeRef) {
3485 assert(m_block->getBit(DataFlow::Killed, id));
3486 m_block->setBit(DataFlow::Referenced, id, false);
3487 }
3488 if (set && !sv->hasAnyContext(Expression::ExistContext|
3489 Expression::UnsetContext)) {
3490 m_block->setBit(DataFlow::Available, id, true);
3491 }
3492 }
3493 }
3494 }
3495 }
3496 }
3497
3498 int after(ConstructRawPtr cp) {
3499 if (ReturnStatementPtr rs = dynamic_pointer_cast<ReturnStatement>(cp)) {
3500 int id = m_gidMap["v:this"];
3501 if (id && m_block->getBit(DataFlow::Available, id)) {
3502 cp->setGuarded();
3503 }
3504 }
3505 return DataFlowWalker::after(cp);
3506 }
3507 private:
3508 std::map<std::string,int> &m_gidMap;
3509 };
3510
3511 class ConstructMarker : public DataFlowWalker {
3512 public:
3513 ConstructMarker(ControlFlowGraph *g, std::map<std::string,int> &gidMap) :
3514 DataFlowWalker(g), m_gidMap(gidMap),
3515 m_top(g->getMethod()->getStmts()) {}
3516
3517 void walk() {
3518 DataFlowWalker::walk(*this);
3519 }
3520
3521 void processAccess(ExpressionPtr e) {
3522 int id = e->getCanonID();
3523 if (!id && e->is(Expression::KindOfSimpleVariable) &&
3524 (e->isAnticipated() || !e->isKilled())) {
3525 id = m_gidMap["v:" + static_pointer_cast<SimpleVariable>(e)->getName()];
3526 }
3527 if (id) {
3528 if (!m_block->getDfn()) return;
3529 if (e->isAnticipated() && m_block->getBit(DataFlow::AvailIn, id)) {
3530 markAvailable(e);
3531 }
3532 if (e->is(Expression::KindOfSimpleVariable) && !e->isKilled()) {
3533 if (m_block->getBit(DataFlow::PRefIn, id)) {
3534 e->setRefCounted();
3535 } else {
3536 e->clearRefCounted();
3537 }
3538 if (m_block->getBit(DataFlow::PInitIn, id)) {
3539 e->setInited();
3540 } else {
3541 e->clearInited();
3542 }
3543 }
3544 }
3545 }
3546
3547 int after(ConstructRawPtr cp) {
3548 if (cp == m_top ||
3549 static_pointer_cast<Statement>(cp)->is(
3550 Statement::KindOfReturnStatement)) {
3551 if (m_block->getDfn()) {
3552 int id = m_gidMap["v:this"];
3553 if (id && m_block->getBit(DataFlow::AvailOut, id)) {
3554 cp->setGuarded();
3555 }
3556 }
3557 }
3558
3559 if (auto rs = dynamic_pointer_cast<ReturnStatement>(cp)) {
3560 std::vector<std::string> lnames;
3561 VariableTableConstPtr vars = cp->getFunctionScope()->getVariables();
3562 vars->getLocalVariableNames(lnames);
3563 for (auto& l : lnames) {
3564 int id = m_gidMap["v:" + l];
3565 if (id && !m_block->getBit(DataFlow::PInitOut, id)) {
3566 rs->addNonRefcounted(l);
3567 } else {
3568 auto sym = vars->getSymbol(l);
3569 auto dt = vars->getFinalType(l)->getDataType();
3570 if (!sym->isStatic()
3571 && !IS_REFCOUNTED_TYPE(dt) && dt != KindOfUnknown) {
3572 rs->addNonRefcounted(l);
3573 }
3574 }
3575 }
3576 }
3577
3578 return DataFlowWalker::after(cp);
3579 }
3580 private:
3581 std::map<std::string,int> &m_gidMap;
3582 ConstructPtr m_top;
3583 };
3584
3585 class Propagater : public ControlFlowGraphWalker {
3586 public:
3587 Propagater(ControlFlowGraph *g, ExprDict &d, bool doTypeProp) :
3588 ControlFlowGraphWalker(g), m_dict(d),
3589 m_changed(false), m_doTypeProp(doTypeProp) {}
3590
3591 bool walk() { ControlFlowGraphWalker::walk(*this); return m_changed; }
3592 int afterEach(ConstructRawPtr p, int i, ConstructPtr kid) {
3593 if (ExpressionRawPtr e = boost::dynamic_pointer_cast<Expression>(kid)) {
3594 if (e->isTypeAssertion()) return WalkContinue; // nothing to do
3595
3596 bool safeForProp =
3597 e->isAnticipated() &&
3598 !(e->getContext() & (Expression::LValue|
3599 Expression::OprLValue|
3600 Expression::AssignmentLHS|
3601 Expression::RefValue|
3602 Expression::UnsetContext|
3603 Expression::DeepReference));
3604 if (safeForProp) {
3605 if (ExpressionPtr rep = m_dict.propagate(e)) {
3606 m_changed = true;
3607 rep = e->replaceValue(rep->clone());
3608 p->setNthKid(i, rep);
3609 return WalkContinue;
3610 }
3611 }
3612
3613 if (m_doTypeProp && e->isAnticipated()) {
3614 TypePtr t = m_dict.propagateType(e);
3615 if (!t) return WalkContinue;
3616 if (safeForProp ||
3617 // $x[0] = ... where $x is not referenced
3618 // should be allowed to grab the type assertion
3619 // if it is an array assertion
3620 (t->is(Type::KindOfArray) &&
3621 e->is(Expression::KindOfSimpleVariable) &&
3622 e->hasContext(Expression::AccessContext) &&
3623 !spc(SimpleVariable, e)->couldBeAliased())) {
3624 e->setAssertedType(t);
3625 }
3626 }
3627 }
3628
3629 return WalkContinue;
3630 }
3631
3632 void beforeBlock(ControlBlock *b) {
3633 m_dict.beforePropagate(b);
3634 }
3635 private:
3636 ExprDict &m_dict;
3637 bool m_changed;
3638 bool m_doTypeProp;
3639 };
3640
3641 void AliasManager::doFinal(MethodStatementPtr m) {
3642 FunctionScopeRawPtr func = m->getFunctionScope();
3643 if (func->isRefReturn()) {
3644 m_nrvoFix = -1;
3645 } else if (m_nrvoFix > 0) {
3646 Symbol *sym = m_variables->getSymbol(m_returnVar);
3647 if (sym && !sym->isParameter() &&
3648 (m_wildRefs || sym->isReferenced() ||
3649 ((sym->isGlobal() || sym->isStatic()) &&
3650 m_variables->needLocalCopy(sym)))) {
3651 // do nothing
3652 } else {
3653 m_nrvoFix = -1;
3654 }
3655 }
3656
3657 func->setNRVOFix(m_nrvoFix > 0);
3658
3659 if (Option::StringLoopOpts && !m_wildRefs) {
3660 stringOptsRecur(m->getStmts());
3661 }
3662 }
3663
3664 void AliasManager::performReferencedAndNeededAnalysis(MethodStatementPtr m) {
3665 always_assert(m_graph != nullptr);
3666
3667 // bail out for pseudomain context
3668 if (m->getScope()->inPseudoMain()) return;
3669
3670 RefDict rd(*this);
3671 rd.build(m);
3672 AttributeTagger<RefDict> rt(m_graph, rd);
3673 RefDictWalker rdw(m_graph);
3674
3675 // referenced analysis
3676 rd.updateParams();
3677 rt.walk();
3678 DataFlow::ComputePartialReferenced(*m_graph);
3679 rdw.walk();
3680
3681 rd.togglePass();
3682 rdw.togglePass();
3683
3684 // needed analysis
3685 rd.updateParams();
3686 rt.walk();
3687 DataFlow::ComputePartialNeeded(*m_graph);
3688 rdw.walk();
3689 }
3690
3691 int AliasManager::copyProp(MethodStatementPtr m) {
3692 if (m_graph == nullptr) createCFG(m);
3693
3694 performReferencedAndNeededAnalysis(m);
3695
3696 ExprDict ed(*this);
3697 m_genAttrs = true;
3698 ed.build(m);
3699 AttributeTagger<ExprDict> at(m_graph, ed);
3700 at.walk();
3701 m_genAttrs = false;
3702
3703 DataFlow::ComputeAvailable(*m_graph);
3704 DataFlow::ComputeAnticipated(*m_graph);
3705
3706 if (Option::DumpAst) m_graph->dump(m_arp);
3707
3708 Propagater prop(m_graph, ed, m_preOpt);
3709 bool ret = prop.walk();
3710 deleteCFG();
3711 return ret;
3712 }
3713
3714 void AliasManager::deleteCFG() {
3715 assert(m_graph != nullptr);
3716 delete m_graph;
3717 m_graph = nullptr;
3718 }
3719
3720 void AliasManager::createCFG(MethodStatementPtr m) {
3721 assert(m_graph == nullptr);
3722 m_graph = ControlFlowGraph::buildControlFlow(m);
3723 }
3724
3725 void AliasManager::insertTypeAssertions(AnalysisResultConstPtr ar,
3726 MethodStatementPtr m) {
3727 TypeAssertionInserter i(ar);
3728 i.walk(m->getStmts());
3729
3730 if (Option::ControlFlow && Option::DumpAst) {
3731 if (m_graph != nullptr) deleteCFG();
3732 createCFG(m);
3733 printf("-------- BEGIN INSERTED -----------\n");
3734 m_graph->dump(m_arp);
3735 printf("-------- END INSERTED -----------\n");
3736 deleteCFG();
3737 }
3738 }
3739
3740 void AliasManager::removeTypeAssertions(AnalysisResultConstPtr ar,
3741 MethodStatementPtr m) {
3742 TypeAssertionRemover r;
3743 r.walk(m->getStmts());
3744
3745 if (Option::ControlFlow && Option::DumpAst) {
3746 if (m_graph != nullptr) deleteCFG();
3747 createCFG(m);
3748 printf("-------- BEGIN REMOVED -----------\n");
3749 m_graph->dump(m_arp);
3750 printf("-------- END REMOVED -----------\n");
3751 deleteCFG();
3752 }
3753 }
3754
3755 int AliasManager::optimize(AnalysisResultConstPtr ar, MethodStatementPtr m) {
3756 m_hasTypeAssertions = false;
3757 gatherInfo(ar, m);
3758
3759 bool runCanon = Option::LocalCopyProp || Option::EliminateDeadCode;
3760
3761 if (runCanon && m_preOpt) {
3762 if (m_hasTypeAssertions) removeTypeAssertions(ar, m);
3763 insertTypeAssertions(ar, m);
3764 }
3765
3766 if (runCanon && m_postOpt && m_hasTypeAssertions) {
3767 removeTypeAssertions(ar, m);
3768 }
3769
3770 if (!m_hasDeadStore && Option::CopyProp) {
3771 if (copyProp(m)) return 1;
3772 }
3773
3774 if (m_graph != nullptr) deleteCFG();
3775
3776 m_hasChainRoot = false;
3777
3778 if (runCanon) {
3779 for (int i = 0, nkid = m->getKidCount(); i < nkid; i++) {
3780 if (i) {
3781 clear();
3782 m_cleared = false;
3783 }
3784 canonicalizeKid(m, m->getNthKid(i), i);
3785 killLocals();
3786 }
3787
3788 if (m_hasChainRoot && m_postOpt) {
3789 // need to do possible invalidation for label statements
3790 invalidateChainRoots(m->getStmts());
3791 }
3792 }
3793
3794 if (!m_replaced && !m_changes && m_postOpt && !Option::ControlFlow) {
3795 doFinal(m);
3796 }
3797
3798 return m_replaced ? -1 : m_changes ? 1 : 0;
3799 }
3800
3801 void AliasManager::finalSetup(AnalysisResultConstPtr ar, MethodStatementPtr m) {
3802 if (Option::ControlFlow) {
3803 m_graph = ControlFlowGraph::buildControlFlow(m);
3804 }
3805
3806 gatherInfo(ar, m);
3807 if (m_graph) {
3808 if (!m_inPseudoMain &&
3809 !m_variables->getAttribute(VariableTable::ContainsLDynamicVariable)) {
3810 for (std::map<string,SimpleVariablePtr>::iterator it =
3811 m_objMap.begin(), end = m_objMap.end(); it != end; ++it) {
3812 SimpleVariablePtr sv = it->second;
3813 const Symbol *sym = sv->getSymbol();
3814 int &id = m_gidMap["v:"+sym->getName()];
3815 assert(!id);
3816 id = m_gidMap.size();
3817 }
3818 }
3819
3820 {
3821 static int rows[] = {
3822 DataFlow::Available, DataFlow::Altered,
3823 DataFlow::Inited, DataFlow::Referenced, DataFlow::Killed,
3824 DataFlow::AvailIn, DataFlow::AvailOut,
3825 DataFlow::PInitIn, DataFlow::PInitOut,
3826 DataFlow::PRefIn, DataFlow::PRefOut
3827 };
3828 m_graph->allocateDataFlow(m_gidMap.size()+1,
3829 sizeof(rows)/sizeof(rows[0]), rows);
3830 }
3831
3832 ConstructTagger ct(m_graph, m_gidMap);
3833 ct.walk(m);
3834
3835 DataFlow::ComputeAvailable(*m_graph);
3836 DataFlow::ComputePartialReferenced(*m_graph);
3837 DataFlow::ComputePartialInited(*m_graph);
3838
3839 ConstructMarker cm(m_graph, m_gidMap);
3840 cm.walk();
3841
3842 if (Option::VariableCoalescing &&
3843 !m_inPseudoMain &&
3844 !m_variables->getAttribute(VariableTable::ContainsDynamicVariable)) {
3845
3846 performReferencedAndNeededAnalysis(m);
3847
3848 LiveDict ld(*this);
3849 m_genAttrs = true;
3850 ld.build(m);
3851 AttributeTagger<LiveDict> lt(m_graph, ld);
3852 lt.walk();
3853 ld.updateParams();
3854 m_genAttrs = false;
3855 DataFlow::ComputePartialAvailable(*m_graph);
3856 DataFlow::ComputePartialAnticipated(*m_graph);
3857 DataFlow::ComputeUsed(*m_graph);
3858 DataFlow::ComputePartialDying(*m_graph);
3859
3860 if (Option::DumpAst) m_graph->dump(ar);
3861
3862 ld.buildConflicts();
3863 if (ld.color(Type::Variant) ||
3864 ld.color(Type::String) ||
3865 ld.color(Type::Numeric) ||
3866 ld.color(Type::Primitive)) {
3867 ld.coalesce(m);
3868 }
3869 ld.shrinkWrap();
3870 }
3871
3872 if (Option::DumpAst) m_graph->dump(ar);
3873
3874 delete m_graph;
3875 m_graph = 0;
3876 }
3877 doFinal(m);
3878 }
3879
3880 void AliasManager::invalidateChainRoots(StatementPtr s) {
3881 if (!s) return;
3882 if (FunctionWalker::SkipRecurse(s)) return;
3883 switch (s->getKindOf()) {
3884 case Statement::KindOfStatementList:
3885 {
3886 StatementListPtr slist(spc(StatementList, s));
3887 // start from the last statement -
3888 // if we find a child stmt with
3889 // a reachable label, we must invalidate
3890 // all statements before
3891 bool disable = false;
3892 for (int i = s->getKidCount(); i--; ) {
3893 StatementPtr kid((*slist)[i]);
3894 invalidateChainRoots(kid);
3895 if (!disable && kid->hasReachableLabel()) {
3896 disable = true;
3897 }
3898 if (disable) disableCSE(kid);
3899 }
3900 }
3901 break;
3902 case Statement::KindOfDoStatement:
3903 {
3904 // need to disable CSE in the top level body
3905 // otherwise we'd have to declare all CSE temps like:
3906 // declare_temps;
3907 // do { ... } while (cond);
3908 DoStatementPtr ds(static_pointer_cast<DoStatement>(s));
3909 disableCSE(ds->getBody());
3910 }
3911 // fall through
3912 default:
3913 for (int i = s->getKidCount(); i--; ) {
3914 invalidateChainRoots(s->getNthStmt(i));
3915 }
3916 break;
3917 }
3918 }
3919
3920 void AliasManager::nullSafeDisableCSE(StatementPtr parent, ExpressionPtr kid) {
3921 assert(parent);
3922 if (!kid) return;
3923 kid->disableCSE();
3924 }
3925
3926 void AliasManager::disableCSE(StatementPtr s) {
3927 if (!s) return;
3928 switch (s->getKindOf()) {
3929 case Statement::KindOfIfBranchStatement: {
3930 IfBranchStatementPtr is(static_pointer_cast<IfBranchStatement>(s));
3931 nullSafeDisableCSE(s, is->getCondition());
3932 break;
3933 }
3934 case Statement::KindOfSwitchStatement: {
3935 SwitchStatementPtr ss(static_pointer_cast<SwitchStatement>(s));
3936 nullSafeDisableCSE(s, ss->getExp());
3937 break;
3938 }
3939 case Statement::KindOfForStatement: {
3940 ForStatementPtr fs(static_pointer_cast<ForStatement>(s));
3941 nullSafeDisableCSE(s, fs->getInitExp());
3942 nullSafeDisableCSE(s, fs->getCondExp());
3943 nullSafeDisableCSE(s, fs->getIncExp());
3944 break;
3945 }
3946 case Statement::KindOfForEachStatement: {
3947 ForEachStatementPtr fs(static_pointer_cast<ForEachStatement>(s));
3948 nullSafeDisableCSE(s, fs->getArrayExp());
3949 nullSafeDisableCSE(s, fs->getNameExp());
3950 nullSafeDisableCSE(s, fs->getValueExp());
3951 break;
3952 }
3953 case Statement::KindOfWhileStatement: {
3954 WhileStatementPtr ws(static_pointer_cast<WhileStatement>(s));
3955 nullSafeDisableCSE(s, ws->getCondExp());
3956 break;
3957 }
3958 case Statement::KindOfDoStatement: {
3959 DoStatementPtr ds(static_pointer_cast<DoStatement>(s));
3960 nullSafeDisableCSE(s, ds->getCondExp());
3961 break;
3962 }
3963 default:
3964 for (int i = s->getKidCount(); i--; ) {
3965 ConstructPtr c(s->getNthKid(i));
3966 if (StatementPtr skid = dpc(Statement, c)) {
3967 disableCSE(skid);
3968 } else {
3969 nullSafeDisableCSE(s, dpc(Expression, c));
3970 }
3971 }
3972 break;
3973 }
3974 }
3975
3976 AliasManager::LoopInfo::LoopInfo(StatementPtr s) :
3977 m_stmt(s), m_valid(!s->is(Statement::KindOfSwitchStatement)) {
3978 }
3979
3980 void AliasManager::pushStringScope(StatementPtr s) {
3981 m_loopInfo.push_back(LoopInfo(s));
3982 if (LoopStatementPtr cur = dpc(LoopStatement,s)) {
3983 cur->clearStringBufs();
3984 }
3985 }
3986
3987 void AliasManager::popStringScope(StatementPtr s) {
3988 size_t sz = m_loopInfo.size();
3989 always_assert(sz);
3990 LoopInfo &li1 = m_loopInfo.back();
3991 always_assert(li1.m_stmt == s);
3992 if (li1.m_candidates.size() && li1.m_valid) {
3993 for (unsigned i = li1.m_inner.size(); i--; ) {
3994 if (LoopStatementPtr inner = dpc(LoopStatement, li1.m_inner[i])) {
3995 for (StringSet::iterator it = li1.m_candidates.begin(),
3996 end = li1.m_candidates.end(); it != end; ++it) {
3997 inner->removeStringBuf(*it);
3998 }
3999 }
4000 }
4001
4002 if (LoopStatementPtr cur = dpc(LoopStatement, li1.m_stmt)) {
4003 for (StringSet::iterator it = li1.m_candidates.begin(),
4004 end = li1.m_candidates.end(); it != end; ++it) {
4005 cur->addStringBuf(*it);
4006 }
4007 }
4008 }
4009
4010 if (sz > 1) {
4011 LoopInfo &li2 = m_loopInfo[sz-2];
4012 if (li1.m_candidates.size()) {
4013 for (StringSet::iterator it = li1.m_candidates.begin(),
4014 end = li1.m_candidates.end(); it != end; ++it) {
4015 if (li2.m_excluded.find(*it) == li2.m_excluded.end()) {
4016 li2.m_candidates.insert(*it);
4017 }
4018 }
4019 li2.m_inner.push_back(s);
4020 }
4021 for (StringSet::iterator it = li1.m_excluded.begin(),
4022 end = li1.m_excluded.end(); it != end; ++it) {
4023 li2.m_excluded.insert(*it);
4024 li2.m_candidates.erase(*it);
4025 }
4026 for (unsigned i = li1.m_inner.size(); i--; ) {
4027 if (LoopStatementPtr inner = dpc(LoopStatement, li1.m_inner[i])) {
4028 if (inner->numStringBufs()) {
4029 li2.m_inner.push_back(inner);
4030 }
4031 }
4032 }
4033 }
4034
4035 m_loopInfo.pop_back();
4036 }
4037
4038 void AliasManager::stringOptsRecur(ExpressionPtr e, bool ok) {
4039 if (!e) return;
4040 if (!m_loopInfo.size()) return;
4041 Expression::KindOf etype = e->getKindOf();
4042 switch (etype) {
4043 case Expression::KindOfBinaryOpExpression:
4044 {
4045 BinaryOpExpressionPtr b(spc(BinaryOpExpression,e));
4046 stringOptsRecur(b->getExp2(), false);
4047 if (ok && b->getOp() == T_CONCAT_EQUAL) {
4048 ExpressionPtr var = b->getExp1();
4049 if (var->is(Expression::KindOfSimpleVariable)) {
4050 SimpleVariablePtr s(spc(SimpleVariable,var));
4051 if (!s->couldBeAliased()) {
4052 LoopInfo &li = m_loopInfo.back();
4053 if (li.m_excluded.find(s->getName()) ==
4054 li.m_excluded.end()) {
4055 li.m_candidates.insert(s->getName());
4056 return;
4057 }
4058 }
4059 }
4060 }
4061 stringOptsRecur(b->getExp1(), false);
4062 }
4063 return;
4064 case Expression::KindOfExpressionList:
4065 {
4066 ExpressionListPtr el(spc(ExpressionList,e));
4067 if (el->getListKind() != ExpressionList::ListKindParam) {
4068 int n = el->getCount();
4069 int chk = el->getListKind() == ExpressionList::ListKindLeft ?
4070 0 : n - 1;
4071 for (int i = 0; i < n; i++) {
4072 stringOptsRecur((*el)[i], i != chk || ok);
4073 }
4074 return;
4075 }
4076 break;
4077 }
4078 case Expression::KindOfSimpleVariable:
4079 {
4080 SimpleVariablePtr s(spc(SimpleVariable,e));
4081 LoopInfo &li = m_loopInfo.back();
4082 li.m_excluded.insert(s->getName());
4083 li.m_candidates.erase(s->getName());
4084 return;
4085 }
4086 default:
4087 break;
4088 }
4089
4090 for (int i = 0, n = e->getKidCount(); i < n; i++) {
4091 stringOptsRecur(e->getNthExpr(i), false);
4092 }
4093 }
4094
4095 void AliasManager::stringOptsRecur(StatementPtr s) {
4096 if (!s) return;
4097
4098 // Dont handle nested functions
4099 // they will be dealt with by another
4100 // top level call
4101 if (FunctionWalker::SkipRecurse(s)) return;
4102
4103 bool pop = false;
4104 Statement::KindOf stype = s->getKindOf();
4105 switch (stype) {
4106 case Statement::KindOfSwitchStatement:
4107 if (m_loopInfo.size()) {
4108 pushStringScope(s);
4109 pop = true;
4110 }
4111 break;
4112
4113 case Statement::KindOfForStatement: {
4114 ForStatementPtr fs = spc(ForStatement, s);
4115 stringOptsRecur(fs->getInitExp(), true);
4116 pushStringScope(s);
4117 stringOptsRecur(fs->getCondExp(), false);
4118 stringOptsRecur(fs->getBody());
4119 stringOptsRecur(fs->getIncExp(), true);
4120 popStringScope(s);
4121 return;
4122 }
4123 case Statement::KindOfWhileStatement: {
4124 WhileStatementPtr ws = spc(WhileStatement, s);
4125 pushStringScope(s);
4126 stringOptsRecur(ws->getCondExp(), false);
4127 stringOptsRecur(ws->getBody());
4128 popStringScope(s);
4129 return;
4130 }
4131 case Statement::KindOfDoStatement: {
4132 DoStatementPtr ds = spc(DoStatement, s);
4133 pushStringScope(s);
4134 stringOptsRecur(ds->getBody());
4135 stringOptsRecur(ds->getCondExp(), false);
4136 popStringScope(s);
4137 return;
4138 }
4139 case Statement::KindOfForEachStatement: {
4140 ForEachStatementPtr fs = spc(ForEachStatement, s);
4141 stringOptsRecur(fs->getArrayExp(), false);
4142 stringOptsRecur(fs->getNameExp(), false);
4143 stringOptsRecur(fs->getValueExp(), false);
4144 pushStringScope(s);
4145 stringOptsRecur(fs->getBody());
4146 popStringScope(s);
4147 return;
4148 }
4149 case Statement::KindOfExpStatement:
4150 stringOptsRecur(spc(ExpStatement,s)->getExpression(), true);
4151 return;
4152
4153 case Statement::KindOfBreakStatement:
4154 {
4155 BreakStatementPtr b = spc(BreakStatement, s);
4156 int64_t depth = b->getDepth();
4157 if (depth != 1) {
4158 int64_t s = m_loopInfo.size() - 1;
4159 if (s >= 0) {
4160 if (!depth || depth > s) depth = s;
4161 while (depth--) {
4162 m_loopInfo[s - depth].m_valid = false;
4163 }
4164 }
4165 }
4166 }
4167 break;
4168
4169 default:
4170 break;
4171 }
4172
4173 int nkid = s->getKidCount();
4174 for (int i = 0; i < nkid; i++) {
4175 ConstructPtr cp = s->getNthKid(i);
4176 if (!cp) {
4177 continue;
4178 }
4179 if (StatementPtr skid = dpc(Statement, cp)) {
4180 stringOptsRecur(skid);
4181 } else {
4182 stringOptsRecur(spc(Expression, cp), false);
4183 }
4184 }
4185 if (pop) {
4186 popStringScope(s);
4187 }
4188 }
4189
4190 void AliasManager::beginInExpression(StatementPtr parent, ExpressionPtr kid) {
4191 assert(parent);
4192 if (m_exprIdx == -1) {
4193 assert(!m_exprParent);
4194 m_exprIdx = m_accessList.size();
4195 m_exprParent = parent;
4196 m_expr = kid;
4197 }
4198 }
4199
4200 void AliasManager::endInExpression(StatementPtr requestor) {
4201 assert(requestor);
4202 if (m_exprIdx != -1) {
4203 assert(m_exprIdx >= 0 && m_exprParent);
4204 if (requestor == m_exprParent) {
4205 m_exprIdx = -1;
4206 m_exprParent.reset();
4207 m_expr.reset();
4208 }
4209 }
4210 }
4211
4212 void AliasManager::markAllLocalExprAltered(ExpressionPtr e) {
4213 if (!m_postOpt) return;
4214 assert(isInExpression());
4215 assert(m_exprIdx <= (int)m_accessList.size());
4216 e->setLocalExprAltered();
4217 ExpressionPtrList::reverse_iterator it(m_accessList.rbegin());
4218 int curIdx = m_accessList.size() - 1;
4219 bool found = m_exprBeginStack.empty();
4220 for (; curIdx >= m_exprIdx; --curIdx, ++it) {
4221 ExpressionPtr p(*it);
4222 if (!found && p == m_exprBeginStack.back()) {
4223 found = true;
4224 }
4225 if (found) {
4226 bool isLoad; int depth, effects;
4227 int interf = checkAnyInterf(e, p, isLoad, depth, effects);
4228 if (interf == InterfAccess ||
4229 interf == SameAccess) {
4230 p->setLocalExprAltered();
4231 }
4232 }
4233 }
4234 }