hphp/compiler/analysis/alias_manager.cpp

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