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