hphp/hhbbc/optimize.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present 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 #include "hphp/hhbbc/optimize.h"
  17
  18 #include <vector>
  19 #include <string>
  20 #include <utility>
  21 #include <algorithm>
  22 #include <cassert>
  23 #include <bitset>
  24
  25 #include <boost/dynamic_bitset.hpp>
  26
  27 #include <folly/Optional.h>
  28 #include <folly/gen/Base.h>
  29 #include <folly/gen/String.h>
  30
  31 #include "hphp/util/trace.h"
  32 #include "hphp/util/match.h"
  33
  34 #include "hphp/runtime/vm/hhbc.h"
  35 #include "hphp/runtime/base/datatype.h"
  36
  37 #include "hphp/hhbbc/hhbbc.h"
  38 #include "hphp/hhbbc/analyze.h"
  39 #include "hphp/hhbbc/cfg.h"
  40 #include "hphp/hhbbc/cfg-opts.h"
  41 #include "hphp/hhbbc/dce.h"
  42 #include "hphp/hhbbc/func-util.h"
  43 #include "hphp/hhbbc/interp.h"
  44 #include "hphp/hhbbc/interp-internal.h"
  45 #include "hphp/hhbbc/interp-state.h"
  46 #include "hphp/hhbbc/misc.h"
  47 #include "hphp/hhbbc/options-util.h"
  48 #include "hphp/hhbbc/representation.h"
  49 #include "hphp/hhbbc/type-system.h"
  50 #include "hphp/hhbbc/unit-util.h"
  51
  52 namespace HPHP { namespace HHBBC {
  53
  54 //////////////////////////////////////////////////////////////////////
  55
  56 namespace {
  57
  58 //////////////////////////////////////////////////////////////////////
  59
  60 /*
  61  * For filtering assertions, some opcodes are considered to have no
  62  * use for a stack input assertion.
  63  *
  64  * For now this is restricted to opcodes that do literally nothing.
  65  */
  66 bool ignoresStackInput(Op op) {
  67   switch (op) {
  68   case Op::UGetCUNop:
  69   case Op::CGetCUNop:
  70   case Op::PopU:
  71     return true;
  72   default:
  73     return false;
  74   }
  75   not_reached();
  76 }
  77
  78 template<class TyBC, class ArgType>
  79 folly::Optional<Bytecode> makeAssert(ArrayTypeTable::Builder& arrTable,
  80                                      ArgType arg,
  81                                      Type t) {
  82   if (t.subtypeOf(BBottom)) return folly::none;
  83   auto const rat = make_repo_type(arrTable, t);
  84   using T = RepoAuthType::Tag;
  85   if (options.FilterAssertions) {
  86     // Gen and InitGen don't add any useful information, so leave them
  87     // out entirely.
  88     if (rat == RepoAuthType{T::Gen})     return folly::none;
  89     if (rat == RepoAuthType{T::InitGen}) return folly::none;
  90   }
  91   return Bytecode { TyBC { arg, rat } };
  92 }
  93
  94 template<class Gen>
  95 void insert_assertions_step(ArrayTypeTable::Builder& arrTable,
  96                             const php::Func& func,
  97                             const Bytecode& bcode,
  98                             const State& state,
  99                             std::bitset<kMaxTrackedLocals> mayReadLocalSet,
 100                             std::vector<uint8_t> obviousStackOutputs,
 101                             Gen gen) {
 102   if (state.unreachable) return;
 103
 104   for (LocalId i = 0; i < state.locals.size(); ++i) {
 105     if (func.locals[i].killed) continue;
 106     if (options.FilterAssertions) {
 107       // Do not emit assertions for untracked locals.
 108       if (i >= mayReadLocalSet.size()) break;
 109       if (!mayReadLocalSet.test(i)) continue;
 110     }
 111     auto const realT = state.locals[i];
 112     auto const op = makeAssert<bc::AssertRATL>(arrTable, i, realT);
 113     if (op) gen(*op);
 114   }
 115
 116   if (!options.InsertStackAssertions) return;
 117
 118   assert(obviousStackOutputs.size() == state.stack.size());
 119
 120   auto const assert_stack = [&] (size_t idx) {
 121     assert(idx < state.stack.size());
 122     if (obviousStackOutputs[state.stack.size() - idx - 1]) return;
 123     if (ignoresStackInput(bcode.op)) return;
 124     auto const realT = state.stack[state.stack.size() - idx - 1].type;
 125     auto const flav  = stack_flav(realT);
 126
 127     if (options.FilterAssertions && !realT.strictSubtypeOf(flav)) {
 128       return;
 129     }
 130
 131     auto const op =
 132       makeAssert<bc::AssertRATStk>(
 133         arrTable,
 134         static_cast<uint32_t>(idx),
 135         realT
 136       );
 137     if (op) gen(*op);
 138   };
 139
 140   /*
 141    * This doesn't need to account for ActRecs on the fpiStack, because
 142    * no instruction in an FPI region can ever consume a stack value
 143    * from above the pre-live ActRec.
 144    */
 145   for (auto i = size_t{0}; i < bcode.numPop(); ++i) assert_stack(i);
 146
 147   // The base instructions are special in that they don't pop anything, but do
 148   // read from the stack. We want type assertions on the stack slots they'll
 149   // read.
 150   switch (bcode.op) {
 151     case Op::BaseC:       assert_stack(bcode.BaseC.arg1);       break;
 152     case Op::BaseGC:      assert_stack(bcode.BaseGC.arg1);      break;
 153     case Op::BaseSC:      assert_stack(bcode.BaseSC.arg1);      break;
 154     case Op::Dim: {
 155       switch (bcode.Dim.mkey.mcode) {
 156         case MEC: case MPC:
 157           assert_stack(bcode.Dim.mkey.idx);
 158           break;
 159         case MW:  case MEL: case MPL: case MEI:
 160         case MET: case MPT: case MQT:
 161           break;
 162       }
 163     }
 164     default:                                                    break;
 165   }
 166 }
 167
 168 /*
 169  * When filter assertions is on, we use this to avoid putting stack
 170  * assertions on some "obvious" instructions.
 171  *
 172  * These are instructions that push an output type that is always the
 173  * same, i.e. where an AssertT is never going to add information.
 174  * (E.g. "Int 3" obviously pushes an Int, and the JIT has no trouble
 175  * figuring that out, so there's no reason to assert about it.)
 176  *
 177  * TODO(#3676101): It turns out many hhbc opcodes have known output
 178  * types---there are some super polymorphic ones, but many always do
 179  * bools or objects, etc.  We might consider making stack flavors have
 180  * subtypes and adding this to the opcode table.
 181  */
 182 bool hasObviousStackOutput(const Bytecode& op, const Interp& interp) {
 183   // Generally consider CGetL obvious because if we knew the type of the local,
 184   // we'll assert that right before the CGetL.
 185   auto cgetlObvious = [&] (LocalId l, int idx) {
 186     return !interp.state.locals[l].couldBe(BRef) ||
 187       !interp.state.stack[interp.state.stack.size() - idx - 1].
 188          type.strictSubtypeOf(TInitCell);
 189   };
 190   switch (op.op) {
 191   case Op::Null:
 192   case Op::NullUninit:
 193   case Op::True:
 194   case Op::False:
 195   case Op::Int:
 196   case Op::Double:
 197   case Op::String:
 198   case Op::Array:
 199   case Op::Dict:
 200   case Op::Vec:
 201   case Op::Keyset:
 202   case Op::NewArray:
 203   case Op::NewDArray:
 204   case Op::NewDictArray:
 205   case Op::NewPackedArray:
 206   case Op::NewVArray:
 207   case Op::NewStructArray:
 208   case Op::NewStructDArray:
 209   case Op::NewStructDict:
 210   case Op::NewVecArray:
 211   case Op::NewKeysetArray:
 212   case Op::AddNewElemC:
 213   case Op::NewCol:
 214   case Op::NewPair:
 215   case Op::ClsRefName:
 216   case Op::File:
 217   case Op::Dir:
 218   case Op::Concat:
 219   case Op::ConcatN:
 220   case Op::Not:
 221   case Op::Xor:
 222   case Op::Same:
 223   case Op::NSame:
 224   case Op::Eq:
 225   case Op::Neq:
 226   case Op::Lt:
 227   case Op::Gt:
 228   case Op::Lte:
 229   case Op::Gte:
 230   case Op::Cmp:
 231   case Op::Shl:
 232   case Op::Shr:
 233   case Op::CastBool:
 234   case Op::CastInt:
 235   case Op::CastDouble:
 236   case Op::CastString:
 237   case Op::CastArray:
 238   case Op::CastObject:
 239   case Op::CastDict:
 240   case Op::CastVec:
 241   case Op::CastKeyset:
 242   case Op::CastVArray:
 243   case Op::CastDArray:
 244   case Op::DblAsBits:
 245   case Op::InstanceOfD:
 246   case Op::IsLateBoundCls:
 247   case Op::IsTypeStructC:
 248   case Op::CombineAndResolveTypeStruct:
 249   case Op::RecordReifiedGeneric:
 250   case Op::ReifiedName:
 251   case Op::InstanceOf:
 252   case Op::Print:
 253   case Op::Exit:
 254   case Op::AKExists:
 255   case Op::IssetL:
 256   case Op::IssetG:
 257   case Op::IssetS:
 258   case Op::EmptyL:
 259   case Op::EmptyG:
 260   case Op::EmptyS:
 261   case Op::IsTypeC:
 262   case Op::IsTypeL:
 263   case Op::OODeclExists:
 264   case Op::AliasCls:
 265     return true;
 266
 267   case Op::This:
 268   case Op::BareThis:
 269     if (auto tt = thisType(interp.index, interp.ctx)) {
 270       auto t = interp.state.stack.back().type;
 271       if (is_opt(t)) t = unopt(std::move(t));
 272       return !t.strictSubtypeOf(*tt);
 273     }
 274     return true;
 275
 276   case Op::CGetL:
 277     return cgetlObvious(op.CGetL.loc1, 0);
 278   case Op::CGetQuietL:
 279     return cgetlObvious(op.CGetQuietL.loc1, 0);
 280   case Op::CUGetL:
 281     return cgetlObvious(op.CUGetL.loc1, 0);
 282   case Op::CGetL2:
 283     return cgetlObvious(op.CGetL2.loc1, 1);
 284   case Op::PushL:
 285     return cgetlObvious(op.PushL.loc1, 0);
 286
 287   // The output of SetL is obvious if you know what its input is
 288   // (which we'll assert if we know).
 289   case Op::SetL:
 290     return true;
 291
 292   // The output of SetM isn't quite as obvious as SetL, but the jit
 293   // can work it out from the input just as well as hhbbc (if not better).
 294   case Op::SetM:
 295     return true;
 296
 297   default:
 298     return false;
 299   }
 300 }
 301
 302 void insert_assertions(const Index& index,
 303                        const FuncAnalysis& ainfo,
 304                        CollectedInfo& collect,
 305                        BlockId bid,
 306                        State state) {
 307   BytecodeVec newBCs;
 308   auto& cblk = ainfo.ctx.func->blocks[bid];
 309   newBCs.reserve(cblk->hhbcs.size());
 310
 311   auto& arrTable = *index.array_table_builder();
 312   auto const ctx = ainfo.ctx;
 313
 314   std::vector<uint8_t> obviousStackOutputs(state.stack.size(), false);
 315
 316   auto interp = Interp { index, ctx, collect, bid, cblk.get(), state };
 317   for (auto& op : cblk->hhbcs) {
 318     FTRACE(2, "  == {}\n", show(ctx.func, op));
 319
 320     auto gen = [&] (const Bytecode& newb) {
 321       newBCs.push_back(newb);
 322       newBCs.back().srcLoc = op.srcLoc;
 323       FTRACE(2, "   + {}\n", show(ctx.func, newBCs.back()));
 324     };
 325
 326     if (state.unreachable) {
 327       if (cblk->fallthrough != NoBlockId) {
 328         auto const blk = cblk.mutate();
 329         blk->fallthrough = NoBlockId;
 330       }
 331       if (!(instrFlags(op.op) & TF)) {
 332         gen(bc::BreakTraceHint {});
 333         gen(bc::String { s_unreachable.get() });
 334         gen(bc::Fatal { FatalOp::Runtime });
 335       }
 336       break;
 337     }
 338
 339     auto const preState = state;
 340     auto const flags    = step(interp, op);
 341
 342     insert_assertions_step(
 343       arrTable,
 344       *ctx.func,
 345       op,
 346       preState,
 347       flags.mayReadLocalSet,
 348       obviousStackOutputs,
 349       gen
 350     );
 351
 352     if (op.op == Op::CGetL2) {
 353       obviousStackOutputs.emplace(obviousStackOutputs.end() - 1,
 354                                   hasObviousStackOutput(op, interp));
 355     } else {
 356       for (int i = 0; i < op.numPop(); i++) {
 357         obviousStackOutputs.pop_back();
 358       }
 359       for (auto i = op.numPush(); i--; ) {
 360         obviousStackOutputs.emplace_back(hasObviousStackOutput(op, interp));
 361       }
 362     }
 363
 364     gen(op);
 365   }
 366
 367   if (cblk->hhbcs != newBCs) cblk.mutate()->hhbcs = std::move(newBCs);
 368 }
 369
 370 bool persistence_check(const php::Func* const func) {
 371   auto bid = func->mainEntry;
 372   while (bid != NoBlockId) {
 373     auto const& blk = func->blocks[bid];
 374     for (auto& op : blk->hhbcs) {
 375       switch (op.op) {
 376         case Op::Nop:
 377         case Op::DefCls:
 378         case Op::DefClsNop:
 379         case Op::DefCns:
 380         case Op::DefTypeAlias:
 381         case Op::Null:
 382         case Op::True:
 383         case Op::False:
 384         case Op::Int:
 385         case Op::Double:
 386         case Op::String:
 387         case Op::Vec:
 388         case Op::Dict:
 389         case Op::Keyset:
 390         case Op::Array:
 391           continue;
 392         case Op::PopC:
 393           // Not strictly no-side effects, but as long as the rest of
 394           // the unit is limited to the above, we're fine (and we expect
 395           // one following a DefCns).
 396           continue;
 397         case Op::RetC:
 398           continue;
 399         default:
 400           return false;
 401       }
 402     }
 403     bid = blk->fallthrough;
 404   }
 405   return true;
 406 }
 407
 408 //////////////////////////////////////////////////////////////////////
 409
 410 template<class Gen>
 411 bool propagate_constants(const Bytecode& op, State& state, Gen gen) {
 412   auto const numPop  = op.numPop();
 413   auto const numPush = op.numPush();
 414   auto const stkSize = state.stack.size();
 415   constexpr auto numCells = 4;
 416   Cell constVals[numCells];
 417
 418   // All outputs of the instruction must have constant types for this
 419   // to be allowed.
 420   for (auto i = size_t{0}; i < numPush; ++i) {
 421     auto const& ty = state.stack[stkSize - i - 1].type;
 422     if (i < numCells) {
 423       auto const v = tv(ty);
 424       if (!v) return false;
 425       constVals[i] = *v;
 426     } else if (!is_scalar(ty)) {
 427       return false;
 428     }
 429   }
 430
 431   auto const slot = visit(op, ReadClsRefSlotVisitor{});
 432   if (slot != NoClsRefSlotId) gen(bc::DiscardClsRef { slot });
 433
 434   // Pop the inputs, and push the constants.
 435   for (auto i = size_t{0}; i < numPop; ++i) {
 436     switch (op.popFlavor(i)) {
 437     case Flavor::C:  gen(bc::PopC {}); break;
 438     case Flavor::V:  gen(bc::PopV {}); break;
 439     case Flavor::U:  not_reached();    break;
 440     case Flavor::CU:
 441       // We only support C's for CU right now.
 442       gen(bc::PopC {});
 443       break;
 444     case Flavor::CV: not_reached();    break;
 445     case Flavor::CVU:
 446       // Note that we only support C's for CVU so far (this only comes up with
 447       // FCallBuiltin)---we'll fail the verifier if something changes to send
 448       // V's or U's through here.
 449       gen(bc::PopC {});
 450       break;
 451     }
 452   }
 453
 454   for (auto i = size_t{0}; i < numPush; ++i) {
 455     auto const v = i < numCells ?
 456       constVals[i] : *tv(state.stack[stkSize - i - 1].type);
 457     gen(gen_constant(v));
 458     state.stack[stkSize - i - 1].type = from_cell(v);
 459   }
 460
 461   return true;
 462 }
 463
 464 bool propagate_constants(const Bytecode& bc, State& state,
 465                          BytecodeVec& out) {
 466   return propagate_constants(bc, state, [&] (const Bytecode& bc) {
 467       out.push_back(bc);
 468     });
 469 }
 470
 471 //////////////////////////////////////////////////////////////////////
 472
 473 /*
 474  * Create a block similar to another block (but with no bytecode in it yet).
 475  */
 476 BlockId make_block(php::Func* func,
 477                    const php::Block* srcBlk) {
 478   FTRACE(1, " ++ new block {}\n", func->blocks.size());
 479
 480   auto newBlk           = copy_ptr<php::Block>{php::Block{}};
 481   auto const blk        = newBlk.mutate();
 482   blk->exnNodeId        = srcBlk->exnNodeId;
 483   blk->throwExit        = srcBlk->throwExit;
 484   auto const bid        = func->blocks.size();
 485   func->blocks.push_back(std::move(newBlk));
 486
 487   return bid;
 488 }
 489
 490 BlockId make_fatal_block(php::Func* func,
 491                          const php::Block* srcBlk) {
 492   auto bid = make_block(func, srcBlk);
 493   auto const blk = func->blocks[bid].mutate();
 494   auto const srcLoc = srcBlk->hhbcs.back().srcLoc;
 495   blk->hhbcs = {
 496     bc_with_loc(srcLoc, bc::String { s_unreachable.get() }),
 497     bc_with_loc(srcLoc, bc::Fatal { FatalOp::Runtime })
 498   };
 499   blk->fallthrough = NoBlockId;
 500   blk->throwExit = NoBlockId;
 501   blk->exnNodeId = NoExnNodeId;
 502   return bid;
 503 }
 504
 505 void sync_ainfo(BlockId bid, FuncAnalysis& ainfo, const State& state) {
 506   assertx(ainfo.bdata.size() == bid);
 507   assertx(bid + 1 == ainfo.ctx.func->blocks.size());
 508
 509   ainfo.rpoBlocks.push_back(bid);
 510   ainfo.bdata.push_back(FuncAnalysis::BlockData {
 511     static_cast<uint32_t>(ainfo.rpoBlocks.size() - 1),
 512     state
 513   });
 514 }
 515
 516 /*
 517  * Create a block similar to another block (but with no bytecode in it yet).
 518  */
 519 BlockId make_block(FuncAnalysis& ainfo,
 520                    const php::Block* srcBlk,
 521                    const State& state) {
 522   auto const bid = make_block(ainfo.ctx.func, srcBlk);
 523   sync_ainfo(bid, ainfo, state);
 524   return bid;
 525 }
 526
 527 BlockId make_fatal_block(FuncAnalysis& ainfo,
 528                          const php::Block* srcBlk,
 529                          const State& state) {
 530   auto bid = make_fatal_block(ainfo.ctx.func, srcBlk);
 531   sync_ainfo(bid, ainfo, state);
 532   return bid;
 533 }
 534
 535 //////////////////////////////////////////////////////////////////////
 536
 537 template<class BlockContainer, class AInfo, class Fun>
 538 void visit_blocks_impl(const char* what,
 539                        const Index& index,
 540                        AInfo& ainfo,
 541                        CollectedInfo& collect,
 542                        const BlockContainer& rpoBlocks,
 543                        Fun&& fun) {
 544
 545   BlockId curBlk = NoBlockId;
 546   SCOPE_ASSERT_DETAIL(what) {
 547     if (curBlk == NoBlockId) return std::string{"\nNo block processed\n"};
 548     return folly::sformat(
 549         "block #{}\nin-{}", curBlk,
 550         state_string(*ainfo.ctx.func, ainfo.bdata[curBlk].stateIn, collect)
 551     );
 552   };
 553
 554   FTRACE(1, "|---- {}\n", what);
 555   for (auto const bid : rpoBlocks) {
 556     curBlk = bid;
 557     FTRACE(2, "block #{}\n", bid);
 558     auto const& state = ainfo.bdata[bid].stateIn;
 559     if (!state.initialized) {
 560       FTRACE(2, "   unreachable\n");
 561       continue;
 562     }
 563     // TODO(#3732260): this should probably spend an extra interp pass
 564     // in debug builds to check that no transformation to the bytecode
 565     // was made that changes the block output state.
 566     fun(index, ainfo, collect, bid, state);
 567   }
 568   assert(check(*ainfo.ctx.func));
 569 }
 570
 571 template<class Fun>
 572 void visit_blocks_mutable(const char* what,
 573                           const Index& index,
 574                           FuncAnalysis& ainfo,
 575                           CollectedInfo& collect,
 576                           Fun&& fun) {
 577   // Make a copy of the block list so it can be mutated by the visitor.
 578   auto const blocksCopy = ainfo.rpoBlocks;
 579   visit_blocks_impl(what, index, ainfo, collect,
 580                     blocksCopy, std::forward<Fun>(fun));
 581 }
 582
 583 template<class Fun>
 584 void visit_blocks(const char* what,
 585                   const Index& index,
 586                   const FuncAnalysis& ainfo,
 587                   CollectedInfo& collect,
 588                   Fun&& fun) {
 589   visit_blocks_impl(what, index, ainfo, collect,
 590                     ainfo.rpoBlocks, std::forward<Fun>(fun));
 591 }
 592
 593 //////////////////////////////////////////////////////////////////////
 594
 595 IterId iterFromInit(const php::Func& func, BlockId initBlock) {
 596   auto const& op = func.blocks[initBlock]->hhbcs.back();
 597   if (op.op == Op::IterInit)   return op.IterInit.iter1;
 598   if (op.op == Op::IterInitK)  return op.IterInitK.iter1;
 599   if (op.op == Op::LIterInit)  return op.LIterInit.iter1;
 600   if (op.op == Op::LIterInitK) return op.LIterInitK.iter1;
 601   always_assert(false);
 602 }
 603
 604 /*
 605  * Attempt to convert normal iterators into liters. In order for an iterator to
 606  * be converted to a liter, the following needs to be true:
 607  *
 608  * - The iterator is initialized with the value in a local at exactly one block.
 609  *
 610  * - That same local is not modified on all possible paths from the
 611  *   initialization to every usage of that iterator.
 612  *
 613  * The first condition is actually more restrictive than necessary, but
 614  * enforcing that the iterator is initialized at exactly one place simplifies
 615  * the bookkeeping and is always true with how we currently emit bytecode.
 616  */
 617
 618 struct OptimizeIterState {
 619   void operator()(const Index& index,
 620                   const FuncAnalysis& ainfo,
 621                   CollectedInfo& collect,
 622                   BlockId bid,
 623                   State state) {
 624     auto const ctx = ainfo.ctx;
 625     auto const blk = ctx.func->blocks[bid].get();
 626     auto interp = Interp { index, ctx, collect, bid, blk, state };
 627     for (uint32_t opIdx = 0; opIdx < blk->hhbcs.size(); ++opIdx) {
 628       // If we've already determined that nothing is eligible, we can just stop.
 629       if (!eligible.any()) break;
 630
 631       auto const& op = blk->hhbcs[opIdx];
 632       FTRACE(2, "  == {}\n", show(ctx.func, op));
 633
 634       if (state.unreachable) break;
 635
 636       // At every op, we check the known state of all live iterators and mark it
 637       // as ineligible as necessary.
 638       for (IterId it = 0; it < state.iters.size(); ++it) {
 639         match<void>(
 640           state.iters[it],
 641           []  (DeadIter) {},
 642           [&] (const LiveIter& ti) {
 643             FTRACE(4, "   iter {: <2}  :: {}\n",
 644                    it, show(*ctx.func, state.iters[it]));
 645             // The init block is unknown. This can only happen if there's more
 646             // than one block where this iterator was initialized. This makes
 647             // tracking the iteration loop ambiguous, and can't happen with how
 648             // we currently emit bytecode, so just pessimize everything.
 649             if (ti.initBlock == NoBlockId) {
 650               FTRACE(2, "   - pessimize all\n");
 651               eligible.clear();
 652               return;
 653             }
 654             // Otherwise, if the iterator doesn't have an equivalent local,
 655             // either it was never initialized with a local to begin with, or
 656             // that local got changed within the loop. Either way, this
 657             // iteration loop isn't eligible.
 658             if (eligible[ti.initBlock] && ti.baseLocal == NoLocalId) {
 659               FTRACE(2, "   - blk:{} ineligible\n", ti.initBlock);
 660               eligible[ti.initBlock] = false;
 661             }
 662           }
 663         );
 664       }
 665
 666       auto const fixupForInit = [&] {
 667         auto const base = topStkLocal(state);
 668         if (base == NoLocalId && eligible[bid]) {
 669           FTRACE(2, "   - blk:{} ineligible\n", bid);
 670           eligible[bid] = false;
 671         }
 672         fixups.emplace_back(Fixup{bid, opIdx, bid, base});
 673         FTRACE(2, "   + fixup ({})\n", fixups.back().show(*ctx.func));
 674       };
 675
 676       auto const fixupFromState = [&] (IterId it) {
 677         match<void>(
 678           state.iters[it],
 679           []  (DeadIter) {},
 680           [&] (const LiveIter& ti) {
 681             if (ti.initBlock != NoBlockId) {
 682               assertx(iterFromInit(*ctx.func, ti.initBlock) == it);
 683               fixups.emplace_back(
 684                 Fixup{bid, opIdx, ti.initBlock, ti.baseLocal}
 685               );
 686               FTRACE(2, "   + fixup ({})\n", fixups.back().show(*ctx.func));
 687             }
 688           }
 689         );
 690       };
 691
 692       // Record a fixup for this iteration op. This iteration loop may not be
 693       // ultimately eligible, but we'll check that before actually doing the
 694       // transformation.
 695       switch (op.op) {
 696         case Op::IterInit:
 697         case Op::IterInitK:
 698           assertx(opIdx == blk->hhbcs.size() - 1);
 699           fixupForInit();
 700           break;
 701         case Op::IterNext:
 702           fixupFromState(op.IterNext.iter1);
 703           break;
 704         case Op::IterNextK:
 705           fixupFromState(op.IterNextK.iter1);
 706           break;
 707         case Op::IterFree:
 708           fixupFromState(op.IterFree.iter1);
 709           break;
 710         case Op::IterBreak:
 711           for (auto const& it : op.IterBreak.iterTab) {
 712             if (it.kind == KindOfIter) fixupFromState(it.id);
 713           }
 714           break;
 715         default:
 716           break;
 717       }
 718
 719       step(interp, op);
 720     }
 721   }
 722
 723   // We identify iteration loops by the block of the initialization op (which we
 724   // enforce is exactly one block). A fixup describes a transformation to an
 725   // iteration instruction which must be applied only if its associated loop is
 726   // eligible.
 727   struct Fixup {
 728     BlockId block; // Block of the op
 729     uint32_t op;   // Index into the block of the op
 730     BlockId init;  // Block of the loop's initializer
 731     LocalId base;  // Invariant base of the iterator
 732
 733     std::string show(const php::Func& f) const {
 734       return folly::sformat(
 735         "blk:{},{},blk:{},{}",
 736         block, op, init,
 737         base != NoLocalId ? local_string(f, base) : "-"
 738       );
 739     }
 740   };
 741   std::vector<Fixup> fixups;
 742   // All of the associated iterator operations within an iterator loop can be
 743   // optimized to liter if the iterator's initialization block is eligible.
 744   boost::dynamic_bitset<> eligible;
 745 };
 746
 747 void optimize_iterators(const Index& index,
 748                         const FuncAnalysis& ainfo,
 749                         CollectedInfo& collect) {
 750   auto const func = ainfo.ctx.func;
 751   // Quick exit. If there's no iterators, or if no associated local survives to
 752   // the end of the iterator, there's nothing to do.
 753   if (!func->numIters || !ainfo.hasInvariantIterBase) return;
 754
 755   OptimizeIterState state;
 756   // Everything starts out as eligible. We'll remove initialization blocks as we
 757   // go.
 758   state.eligible.resize(func->blocks.size(), true);
 759
 760   // Visit all the blocks and build up the fixup state.
 761   visit_blocks("optimize_iterators", index, ainfo, collect, state);
 762   if (!state.eligible.any()) return;
 763
 764   FTRACE(2, "Rewrites:\n");
 765   for (auto const& fixup : state.fixups) {
 766     auto& cblk = func->blocks[fixup.block];
 767     auto const& op = cblk->hhbcs[fixup.op];
 768
 769     if (!state.eligible[fixup.init]) {
 770       // This iteration loop isn't eligible, so don't apply the fixup
 771       FTRACE(2, "   * ({}): {}\n", fixup.show(*func), show(func, op));
 772       continue;
 773     }
 774
 775     BytecodeVec newOps;
 776     assertx(fixup.base != NoLocalId);
 777
 778     // Rewrite the iteration op to its liter equivalent:
 779     switch (op.op) {
 780       case Op::IterInit:
 781         newOps = {
 782           bc_with_loc(op.srcLoc, bc::PopC {}),
 783           bc_with_loc(
 784             op.srcLoc,
 785             bc::LIterInit {
 786               op.IterInit.iter1,
 787               fixup.base,
 788               op.IterInit.target2,
 789               op.IterInit.loc3
 790             }
 791           )
 792         };
 793         break;
 794       case Op::IterInitK:
 795         newOps = {
 796           bc_with_loc(op.srcLoc, bc::PopC {}),
 797           bc_with_loc(
 798             op.srcLoc,
 799             bc::LIterInitK {
 800               op.IterInitK.iter1,
 801               fixup.base,
 802               op.IterInitK.target2,
 803               op.IterInitK.loc3,
 804               op.IterInitK.loc4
 805             }
 806           )
 807         };
 808         break;
 809       case Op::IterNext:
 810         newOps = {
 811           bc_with_loc(
 812             op.srcLoc,
 813             bc::LIterNext {
 814               op.IterNext.iter1,
 815               fixup.base,
 816               op.IterNext.target2,
 817               op.IterNext.loc3
 818             }
 819           )
 820         };
 821         break;
 822       case Op::IterNextK:
 823         newOps = {
 824           bc_with_loc(
 825             op.srcLoc,
 826             bc::LIterNextK {
 827               op.IterNextK.iter1,
 828               fixup.base,
 829               op.IterNextK.target2,
 830               op.IterNextK.loc3,
 831               op.IterNextK.loc4
 832             }
 833           )
 834         };
 835         break;
 836       case Op::IterFree:
 837         newOps = {
 838           bc_with_loc(
 839             op.srcLoc,
 840             bc::LIterFree { op.IterFree.iter1, fixup.base }
 841           )
 842         };
 843         break;
 844       case Op::IterBreak: {
 845         auto const iter = iterFromInit(*func, fixup.init);
 846         newOps = { op };
 847         for (auto& it : newOps.back().IterBreak.iterTab) {
 848           if (it.id == iter) {
 849             assertx(it.kind == KindOfIter);
 850             it.kind = KindOfLIter;
 851             it.local = fixup.base;
 852           }
 853         }
 854         break;
 855       }
 856       default:
 857         always_assert(false);
 858     }
 859
 860     FTRACE(
 861       2, "   ({}): {} ==> {}\n",
 862       fixup.show(*func), show(func, op),
 863       [&] {
 864         using namespace folly::gen;
 865         return from(newOps)
 866           | map([&] (const Bytecode& bc) { return show(func, bc); })
 867           | unsplit<std::string>(",");
 868       }()
 869     );
 870
 871     auto const blk = cblk.mutate();
 872     blk->hhbcs.erase(blk->hhbcs.begin() + fixup.op);
 873     blk->hhbcs.insert(blk->hhbcs.begin() + fixup.op,
 874                       newOps.begin(), newOps.end());
 875   }
 876
 877   FTRACE(10, "{}", show(*func));
 878 }
 879
 880 //////////////////////////////////////////////////////////////////////
 881
 882 /*
 883  * Use the information in the index to resolve a type-constraint to its
 884  * underlying type, if possible.
 885  */
 886 void fixTypeConstraint(const Index& index, TypeConstraint& tc) {
 887   if (!tc.isCheckable() || !tc.isObject() || tc.isResolved()) return;
 888
 889   if (interface_supports_non_objects(tc.typeName())) return;
 890   auto const resolved = index.resolve_type_name(tc.typeName());
 891
 892   assertx(!RuntimeOption::EvalHackArrDVArrs ||
 893           (resolved.type != AnnotType::VArray &&
 894            resolved.type != AnnotType::DArray));
 895
 896   if (resolved.type == AnnotType::Object) {
 897     if (!resolved.value || !resolved.value->resolved()) return;
 898     // Can't resolve if it resolves to a magic interface. If we mark it as
 899     // resolved, we'll think its an object and not do the special magic
 900     // interface checks at runtime.
 901     if (interface_supports_non_objects(resolved.value->name())) return;
 902     if (!resolved.value->couldHaveMockedDerivedClass()) tc.setNoMockObjects();
 903   }
 904
 905   tc.resolveType(resolved.type, tc.isNullable() || resolved.nullable);
 906   FTRACE(1, "Retype tc {} -> {}\n", tc.typeName(), tc.displayName());
 907 }
 908
 909 //////////////////////////////////////////////////////////////////////
 910
 911 void do_optimize(const Index& index, FuncAnalysis&& ainfo, bool isFinal) {
 912   FTRACE(2, "{:-^70} {}\n", "Optimize Func", ainfo.ctx.func->name);
 913
 914   bool again;
 915   folly::Optional<CollectedInfo> collect;
 916
 917   collect.emplace(
 918     index, ainfo.ctx, nullptr,
 919     CollectionOpts{}, &ainfo
 920   );
 921
 922   update_bytecode(ainfo.ctx.func, std::move(ainfo.blockUpdates));
 923   optimize_iterators(index, ainfo, *collect);
 924
 925   do {
 926     again = false;
 927     FTRACE(10, "{}", show(*ainfo.ctx.func));
 928     /*
 929      * Note: it's useful to do dead block removal before DCE, so it can remove
 930      * code relating to the branch to the dead block.
 931      */
 932     remove_unreachable_blocks(ainfo);
 933
 934     if (options.LocalDCE) {
 935       visit_blocks("local DCE", index, ainfo, *collect, local_dce);
 936     }
 937     if (options.GlobalDCE) {
 938       if (global_dce(index, ainfo)) again = true;
 939       if (control_flow_opts(ainfo)) again = true;
 940       assert(check(*ainfo.ctx.func));
 941       /*
 942        * Global DCE can change types of locals across blocks.  See
 943        * dce.cpp for an explanation.
 944        *
 945        * We need to perform a final type analysis before we do
 946        * anything else.
 947        */
 948       ainfo = analyze_func(index, ainfo.ctx, CollectionOpts{});
 949       update_bytecode(ainfo.ctx.func, std::move(ainfo.blockUpdates));
 950       collect.emplace(
 951         index, ainfo.ctx, nullptr,
 952         CollectionOpts{}, &ainfo
 953       );
 954     }
 955
 956     // If we merged blocks, there could be new optimization opportunities
 957   } while (again);
 958
 959   if (!isFinal) return;
 960
 961   auto const func = ainfo.ctx.func;
 962   if (func->name == s_86pinit.get() ||
 963       func->name == s_86sinit.get() ||
 964       func->name == s_86linit.get()) {
 965     auto const& blk = *func->blocks[func->mainEntry];
 966     if (blk.hhbcs.size() == 2 &&
 967         blk.hhbcs[0].op == Op::Null &&
 968         blk.hhbcs[1].op == Op::RetC) {
 969       FTRACE(2, "Erasing {}::{}\n", func->cls->name, func->name);
 970       func->cls->methods.erase(
 971         std::find_if(func->cls->methods.begin(),
 972                      func->cls->methods.end(),
 973                      [&](const std::unique_ptr<php::Func>& f) {
 974                        return f.get() == func;
 975                      }));
 976       return;
 977     }
 978   }
 979
 980   attrSetter(func->attrs,
 981              is_pseudomain(func) ||
 982              func->attrs & AttrInterceptable ||
 983              ainfo.mayUseVV,
 984              AttrMayUseVV);
 985
 986   if (options.InsertAssertions) {
 987     visit_blocks("insert assertions", index, ainfo, *collect,
 988                  insert_assertions);
 989   }
 990
 991   for (auto& p : func->params) fixTypeConstraint(index, p.typeConstraint);
 992
 993   if (RuntimeOption::EvalCheckReturnTypeHints >= 3) {
 994     fixTypeConstraint(index, func->retTypeConstraint);
 995   }
 996 }
 997
 998 //////////////////////////////////////////////////////////////////////
 999
1000 }
1001
1002 //////////////////////////////////////////////////////////////////////
1003
1004 Bytecode gen_constant(const Cell& cell) {
1005   switch (cell.m_type) {
1006     case KindOfUninit:
1007       return bc::NullUninit {};
1008     case KindOfNull:
1009       return bc::Null {};
1010     case KindOfBoolean:
1011       if (cell.m_data.num) {
1012         return bc::True {};
1013       } else {
1014         return bc::False {};
1015       }
1016     case KindOfInt64:
1017       return bc::Int { cell.m_data.num };
1018     case KindOfDouble:
1019       return bc::Double { cell.m_data.dbl };
1020     case KindOfString:
1021       assert(cell.m_data.pstr->isStatic());
1022     case KindOfPersistentString:
1023       return bc::String { cell.m_data.pstr };
1024     case KindOfVec:
1025       assert(cell.m_data.parr->isStatic());
1026     case KindOfPersistentVec:
1027       assert(cell.m_data.parr->isVecArray());
1028       return bc::Vec { cell.m_data.parr };
1029     case KindOfDict:
1030       assert(cell.m_data.parr->isStatic());
1031     case KindOfPersistentDict:
1032       assert(cell.m_data.parr->isDict());
1033       return bc::Dict { cell.m_data.parr };
1034     case KindOfKeyset:
1035       assert(cell.m_data.parr->isStatic());
1036     case KindOfPersistentKeyset:
1037       assert(cell.m_data.parr->isKeyset());
1038       return bc::Keyset { cell.m_data.parr };
1039     case KindOfShape:
1040     case KindOfPersistentShape:
1041       not_implemented();
1042     case KindOfArray:
1043       assert(cell.m_data.parr->isStatic());
1044     case KindOfPersistentArray:
1045       assert(cell.m_data.parr->isPHPArray());
1046       return bc::Array { cell.m_data.parr };
1047
1048     case KindOfRef:
1049     case KindOfResource:
1050     case KindOfObject:
1051     case KindOfFunc:
1052     case KindOfClass:
1053     case KindOfClsMeth:
1054     case KindOfRecord: // TODO(arnabde)
1055       always_assert(0 && "invalid constant in propagate_constants");
1056   }
1057   not_reached();
1058 }
1059
1060 void optimize_func(const Index& index, FuncAnalysis&& ainfo, bool isFinal) {
1061   auto const bump = trace_bump_for(ainfo.ctx.cls, ainfo.ctx.func);
1062
1063   SCOPE_ASSERT_DETAIL("optimize_func") {
1064     return "Optimizing:" + show(ainfo.ctx);
1065   };
1066
1067   Trace::Bump bumper1{Trace::hhbbc, bump};
1068   Trace::Bump bumper2{Trace::hhbbc_cfg, bump};
1069   Trace::Bump bumper3{Trace::hhbbc_dce, bump};
1070   do_optimize(index, std::move(ainfo), isFinal);
1071 }
1072
1073 void update_bytecode(
1074     php::Func* func,
1075     CompactVector<std::pair<BlockId, BlockUpdateInfo>>&& blockUpdates) {
1076
1077   for (auto& ent : blockUpdates) {
1078     auto blk = func->blocks[ent.first].mutate();
1079     auto const srcLoc = blk->hhbcs.front().srcLoc;
1080     if (!ent.second.unchangedBcs) {
1081       if (ent.second.replacedBcs.size()) {
1082         blk->hhbcs = std::move(ent.second.replacedBcs);
1083       } else {
1084         blk->hhbcs = { bc_with_loc(blk->hhbcs.front().srcLoc, bc::Nop {}) };
1085       }
1086     } else {
1087       blk->hhbcs.erase(blk->hhbcs.begin() + ent.second.unchangedBcs,
1088                        blk->hhbcs.end());
1089       blk->hhbcs.reserve(blk->hhbcs.size() + ent.second.replacedBcs.size());
1090       for (auto& bc : ent.second.replacedBcs) {
1091         blk->hhbcs.push_back(std::move(bc));
1092       }
1093     }
1094     if (blk->hhbcs.empty()) {
1095       blk->hhbcs.push_back(bc_with_loc(srcLoc, bc::Nop {}));
1096     }
1097     auto fatal_block = NoBlockId;
1098     auto fatal = [&] {
1099       if (fatal_block == NoBlockId) fatal_block = make_fatal_block(func, blk);
1100       return fatal_block;
1101     };
1102     blk->fallthrough = ent.second.fallthrough;
1103     auto hasCf = false;
1104     forEachTakenEdge(blk->hhbcs.back(),
1105                      [&] (BlockId& bid) {
1106                        hasCf = true;
1107                        if (bid == NoBlockId) bid = fatal();
1108                      });
1109     if (blk->fallthrough == NoBlockId &&
1110         !(instrFlags(blk->hhbcs.back().op) & TF)) {
1111       if (hasCf) {
1112         blk->fallthrough = fatal();
1113       } else {
1114         blk->hhbcs.push_back(bc::BreakTraceHint {});
1115         blk->hhbcs.push_back(bc::String { s_unreachable.get() });
1116         blk->hhbcs.push_back(bc::Fatal { FatalOp::Runtime });
1117       }
1118     }
1119   }
1120   blockUpdates.clear();
1121
1122   if (is_pseudomain(func) &&
1123       func->unit->persistent.load(std::memory_order_relaxed)) {
1124     func->unit->persistent_pseudomain.store(
1125       persistence_check(func), std::memory_order_relaxed
1126     );
1127   }
1128 }
1129
1130 //////////////////////////////////////////////////////////////////////
1131
1132 void optimize_class_prop_type_hints(const Index& index, Context ctx) {
1133   assertx(!ctx.func);
1134   auto const bump = trace_bump_for(ctx.cls, nullptr);
1135   Trace::Bump bumper{Trace::hhbbc, bump};
1136   for (auto& prop : ctx.cls->properties) {
1137     fixTypeConstraint(
1138       index,
1139       const_cast<TypeConstraint&>(prop.typeConstraint)
1140     );
1141   }
1142 }
1143
1144 //////////////////////////////////////////////////////////////////////
1145
1146 }}