hphp/hhbbc/whole-program.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/hhbbc.h"
  17
  18 #include <vector>
  19 #include <algorithm>
  20 #include <atomic>
  21 #include <memory>
  22 #include <set>
  23
  24 #include <folly/AtomicLinkedList.h>
  25 #include <folly/Memory.h>
  26 #include <folly/ScopeGuard.h>
  27
  28 #ifdef HHVM_FACEBOOK
  29 #include <strobelight/strobemeta/strobemeta_frames.h>
  30 #else
  31 #define SET_FRAME_METADATA(...)
  32 #endif
  33
  34 #include "hphp/runtime/vm/repo-global-data.h"
  35 #include "hphp/runtime/vm/unit-emitter.h"
  36
  37 #include "hphp/hhbbc/analyze.h"
  38 #include "hphp/hhbbc/class-util.h"
  39 #include "hphp/hhbbc/debug.h"
  40 #include "hphp/hhbbc/emit.h"
  41 #include "hphp/hhbbc/func-util.h"
  42 #include "hphp/hhbbc/index.h"
  43 #include "hphp/hhbbc/optimize.h"
  44 #include "hphp/hhbbc/options.h"
  45 #include "hphp/hhbbc/options-util.h"
  46 #include "hphp/hhbbc/parallel.h"
  47 #include "hphp/hhbbc/parse.h"
  48 #include "hphp/hhbbc/representation.h"
  49 #include "hphp/hhbbc/stats.h"
  50 #include "hphp/hhbbc/type-system.h"
  51 #include "hphp/hhbbc/wide-func.h"
  52
  53 #include "hphp/util/extern-worker.h"
  54 #include "hphp/util/struct-log.h"
  55
  56 namespace HPHP {
  57
  58 using namespace extern_worker;
  59 namespace coro = folly::coro;
  60
  61 namespace HHBBC {
  62
  63 TRACE_SET_MOD(hhbbc);
  64
  65 //////////////////////////////////////////////////////////////////////
  66
  67 namespace {
  68
  69 //////////////////////////////////////////////////////////////////////
  70
  71 const StaticString s_invoke("__invoke");
  72
  73 //////////////////////////////////////////////////////////////////////
  74
  75 enum class WorkType { Class, Func };
  76
  77 struct WorkItem {
  78   explicit WorkItem(WorkType type, Context ctx)
  79     : type(type)
  80     , ctx(ctx)
  81   {}
  82
  83   WorkType type;
  84   Context ctx;
  85 };
  86
  87 struct WorkResult {
  88   explicit WorkResult(ClassAnalysis cls)
  89     : type(WorkType::Class)
  90     , cls(std::move(cls))
  91   {}
  92
  93   explicit WorkResult(FuncAnalysisResult func)
  94     : type(WorkType::Func)
  95     , func(std::move(func))
  96   {}
  97
  98   WorkResult(WorkResult&& wr) noexcept
  99     : type(wr.type)
 100   {
 101     switch (type) {
 102     case WorkType::Class:
 103       new (&cls) ClassAnalysis(std::move(wr.cls));
 104       break;
 105     case WorkType::Func:
 106       new (&func) FuncAnalysisResult(std::move(wr.func));
 107       break;
 108     }
 109   }
 110
 111   WorkResult& operator=(WorkResult&& o) noexcept {
 112     this->~WorkResult();
 113     switch (o.type) {
 114     case WorkType::Class: new (this) WorkResult(std::move(o.cls)); break;
 115     case WorkType::Func:  new (this) WorkResult(std::move(o.func)); break;
 116     }
 117     return *this;
 118   }
 119
 120   ~WorkResult() {
 121     switch (type) {
 122     case WorkType::Class:
 123       cls.~ClassAnalysis();
 124       break;
 125     case WorkType::Func:
 126       func.~FuncAnalysisResult();
 127       break;
 128     }
 129   }
 130
 131   WorkType type;
 132   union {
 133     ClassAnalysis cls;
 134     FuncAnalysisResult func;
 135   };
 136 };
 137
 138 //////////////////////////////////////////////////////////////////////
 139
 140 std::vector<Context> all_unit_contexts(const Index& index,
 141                                        const php::Unit& u) {
 142   std::vector<Context> ret;
 143   index.for_each_unit_class(
 144     u,
 145     [&] (const php::Class& c) {
 146       for (auto const& m : c.methods) {
 147         ret.emplace_back(Context { u.filename, m.get(), &c });
 148       }
 149     }
 150   );
 151   index.for_each_unit_func(
 152     u,
 153     [&] (const php::Func& f) { ret.emplace_back(Context { u.filename, &f }); }
 154   );
 155   return ret;
 156 }
 157
 158 // Return all the WorkItems we'll need to start analyzing this
 159 // program.
 160 std::vector<WorkItem> initial_work(const Index& index) {
 161   std::vector<WorkItem> ret;
 162
 163   auto const& program = index.program();
 164   for (auto const& c : program.classes) {
 165     assertx(!c->closureContextCls);
 166     if (is_used_trait(*c)) {
 167       for (auto const& f : c->methods) {
 168         ret.emplace_back(
 169           WorkType::Func,
 170           Context { c->unit, f.get(), f->cls }
 171         );
 172       }
 173     } else {
 174       ret.emplace_back(
 175         WorkType::Class,
 176         Context { c->unit, nullptr, c.get() }
 177       );
 178     }
 179   }
 180   for (auto const& f : program.funcs) {
 181     ret.emplace_back(
 182       WorkType::Func,
 183       Context { f->unit, f.get() }
 184     );
 185   }
 186   return ret;
 187 }
 188
 189 WorkItem work_item_for(const DependencyContext& d,
 190                        const Index& index) {
 191   switch (d.tag()) {
 192     case DependencyContextType::Class: {
 193       auto const cls = (const php::Class*)d.ptr();
 194       assertx(!is_used_trait(*cls));
 195       return WorkItem {
 196         WorkType::Class,
 197         Context { cls->unit, nullptr, cls }
 198       };
 199     }
 200     case DependencyContextType::Func: {
 201       auto const func = (const php::Func*)d.ptr();
 202       auto const cls = func->cls
 203         ? index.lookup_closure_context(*func->cls)
 204         : nullptr;
 205       assertx(!cls || is_used_trait(*cls));
 206       return WorkItem {
 207         WorkType::Func,
 208         Context { func->unit, func, cls }
 209       };
 210     }
 211     case DependencyContextType::Prop:
 212     case DependencyContextType::FuncFamily:
 213       // We only record dependencies on these. We don't schedule any
 214       // work on their behalf.
 215       break;
 216   }
 217   always_assert(false);
 218 }
 219
 220 /*
 221  * Algorithm:
 222  *
 223  * Start by running an analyze pass on every class or free function.
 224  * During analysis, information about functions or classes will be
 225  * requested from the Index, which initially won't really know much,
 226  * but will record a dependency.  This part is done in parallel: no
 227  * passes are mutating anything, just reading from the Index.
 228  *
 229  * After a pass, we do a single-threaded "update" step to prepare
 230  * for the next pass: for each function or class that was analyzed,
 231  * note the facts we learned that may aid analyzing other functions
 232  * in the program, and register them in the index.
 233  *
 234  * If any of these facts are more useful than they used to be, add
 235  * all the Contexts that had a dependency on the new information to
 236  * the work list again, in case they can do better based on the new
 237  * fact.  (This only applies to function analysis information right
 238  * now.)
 239  *
 240  * Repeat until the work list is empty.
 241  *
 242  */
 243 void analyze_iteratively(Index& index) {
 244   trace_time tracer("analyze iteratively", index.sample());
 245
 246   // Counters, just for debug printing.
 247   std::atomic<uint32_t> total_funcs{0};
 248   std::atomic<uint32_t> total_classes{0};
 249   auto round = uint32_t{0};
 250
 251   SCOPE_EXIT {
 252     if (Trace::moduleEnabledRelease(Trace::hhbbc_time, 1)) {
 253       Trace::traceRelease("total class visits %u\n", total_classes.load());
 254       Trace::traceRelease("total function visits %u\n", total_funcs.load());
 255     }
 256   };
 257
 258   std::vector<DependencyContextSet> deps_vec{parallel::num_threads};
 259
 260   auto work = initial_work(index);
 261   while (!work.empty()) {
 262     auto results = [&] {
 263       trace_time trace(
 264         "analyzing",
 265         folly::sformat("round {} -- {} work items", round, work.size())
 266       );
 267       return parallel::map(
 268         work,
 269         // We have a Optional just to keep the result type
 270         // DefaultConstructible.
 271         [&] (const WorkItem& wi) -> Optional<WorkResult> {
 272           SET_FRAME_METADATA(wi.ctx.unit->toCppString());
 273           switch (wi.type) {
 274           case WorkType::Func: {
 275             ++total_funcs;
 276             auto const wf = php::WideFunc::cns(wi.ctx.func);
 277             auto const ctx = AnalysisContext { wi.ctx.unit, wf, wi.ctx.cls };
 278             IndexAdaptor adaptor{ index };
 279             return WorkResult { analyze_func(adaptor, ctx, CollectionOpts{}) };
 280           }
 281           case WorkType::Class: {
 282             ++total_classes;
 283             IndexAdaptor adaptor{ index };
 284             return WorkResult { analyze_class(adaptor, wi.ctx) };
 285           }
 286           }
 287           not_reached();
 288         }
 289       );
 290     }();
 291
 292     ++round;
 293     trace_time update_time("updating");
 294
 295     auto const update_func = [&] (FuncAnalysisResult& fa,
 296                                   DependencyContextSet& deps) {
 297       SCOPE_ASSERT_DETAIL("update_func") {
 298         return "Updating Func: " + show(fa.ctx);
 299       };
 300       // This const_cast is safe since no two threads update the same Func.
 301       auto func = php::WideFunc::mut(const_cast<php::Func*>(fa.ctx.func));
 302       index.refine_return_info(fa, deps);
 303       index.refine_constants(fa, deps);
 304       update_bytecode(func, std::move(fa.blockUpdates));
 305
 306       index.record_public_static_mutations(
 307         *func,
 308         std::move(fa.publicSPropMutations)
 309       );
 310
 311       if (auto const l = fa.resolvedInitializers.left()) {
 312         index.refine_class_constants(fa.ctx, *l, deps);
 313       } else if (auto const r = fa.resolvedInitializers.right()) {
 314         index.update_prop_initial_values(fa.ctx, *r, deps);
 315       }
 316
 317       for (auto const& [cls, vars] : fa.closureUseTypes) {
 318         assertx(is_closure(*cls));
 319         if (index.refine_closure_use_vars(cls, vars)) {
 320           auto const func = find_method(cls, s_invoke.get());
 321           always_assert_flog(
 322             func != nullptr,
 323             "Failed to find __invoke on {} during index update\n",
 324             cls->name
 325           );
 326           auto const ctx =
 327             Context { func->unit, func, cls };
 328           deps.insert(index.dependency_context(ctx));
 329         }
 330       }
 331     };
 332
 333     auto const update_class = [&] (ClassAnalysis& ca,
 334                                    DependencyContextSet& deps) {
 335       {
 336         SCOPE_ASSERT_DETAIL("update_class") {
 337           return "Updating Class: " + show(ca.ctx);
 338         };
 339         index.refine_private_props(ca.ctx.cls,
 340                                    ca.privateProperties);
 341         index.refine_private_statics(ca.ctx.cls,
 342                                      ca.privateStatics);
 343         index.update_prop_initial_values(ca.ctx, ca.resolvedProps, deps);
 344       }
 345       for (auto& fa : ca.methods)  update_func(fa, deps);
 346       for (auto& fa : ca.closures) update_func(fa, deps);
 347     };
 348
 349     parallel::for_each(
 350       results,
 351       [&] (auto& result, size_t worker) {
 352         assertx(worker < deps_vec.size());
 353         switch (result->type) {
 354           case WorkType::Func:
 355             update_func(result->func, deps_vec[worker]);
 356             break;
 357           case WorkType::Class:
 358             update_class(result->cls, deps_vec[worker]);
 359             break;
 360         }
 361         result.reset();
 362       }
 363     );
 364
 365     {
 366       trace_time _("merging deps");
 367       for (auto& deps : deps_vec) {
 368         if (&deps == &deps_vec[0]) continue;
 369         for (auto& d : deps) deps_vec[0].insert(d);
 370         deps.clear();
 371       }
 372     }
 373
 374     auto& deps = deps_vec[0];
 375
 376     index.refine_public_statics(deps);
 377
 378     work.clear();
 379     work.reserve(deps.size());
 380     for (auto& d : deps) work.emplace_back(work_item_for(d, index));
 381     deps.clear();
 382   }
 383 }
 384
 385 /*
 386  * Finally, use the results of all these iterations to perform
 387  * optimization.  This reanalyzes every function using our
 388  * now-very-updated Index, and then runs optimize_func with the
 389  * results.
 390  *
 391  * We do this in parallel: all the shared information is queried out
 392  * of the index, and each thread is allowed to modify the bytecode
 393  * for the function it is looking at.
 394  *
 395  * NOTE: currently they can't modify anything other than the
 396  * bytecode/Blocks, because other threads may be doing unlocked
 397  * queries to php::Func and php::Class structures.
 398  */
 399 template<typename F>
 400 void final_pass(Index& index,
 401                 const StatsHolder& stats,
 402                 F emitUnit) {
 403   trace_time final_pass("final pass", index.sample());
 404   index.freeze();
 405   auto const dump_dir = debug_dump_to();
 406   parallel::for_each(
 407     index.program().units,
 408     [&] (const std::unique_ptr<php::Unit>& unit) {
 409       SET_FRAME_METADATA(unit->filename->toCppString());
 410       // optimize_func can remove 86*init methods from classes, so we
 411       // have to save the contexts for now.
 412       for (auto const& context : all_unit_contexts(index, *unit)) {
 413         // This const_cast is safe since no two threads update the same Func.
 414         auto func = php::WideFunc::mut(const_cast<php::Func*>(context.func));
 415         auto const ctx = AnalysisContext { context.unit, func, context.cls };
 416         IndexAdaptor adaptor{ index };
 417         optimize_func(index, analyze_func(adaptor, ctx, CollectionOpts{}), func);
 418       }
 419       state_after("optimize", *unit, index);
 420       if (!dump_dir.empty()) {
 421         if (Trace::moduleEnabledRelease(Trace::hhbbc_dump, 2)) {
 422           dump_representation(dump_dir, index, *unit);
 423         }
 424         dump_index(dump_dir, index, *unit);
 425       }
 426       collect_stats(stats, index, *unit);
 427       emitUnit(*unit);
 428     }
 429   );
 430 }
 431
 432 //////////////////////////////////////////////////////////////////////
 433
 434 // Extern-worker job to analyze constants
 435
 436 struct AnalyzeConstantsJob {
 437   static std::string name() { return "hhbbc-analyze-constants"; }
 438   static void init(const Config& config) {
 439     process_init(config.o, config.gd, false);
 440     AnalysisIndex::start();
 441   }
 442   static void fini() { AnalysisIndex::stop(); }
 443
 444   template<typename T> using V = Variadic<T>;
 445   template<typename T> using VU = V<std::unique_ptr<T>>;
 446
 447   using Output = AnalysisIndex::Output;
 448
 449   static Output run(VU<php::Class> classes,
 450                     VU<php::Func> funcs,
 451                     VU<php::Unit> units,
 452                     VU<php::ClassBytecode> clsBC,
 453                     VU<php::FuncBytecode> funcBC,
 454                     V<AnalysisIndexCInfo> cinfos,
 455                     V<AnalysisIndexFInfo> finfos,
 456                     V<AnalysisIndexMInfo> minfos,
 457                     VU<php::Class> depClasses,
 458                     VU<php::Func> depFuncs,
 459                     VU<php::Unit> depUnits,
 460                     AnalysisInput::Meta meta) {
 461     // AnalysisIndex ctor will initialize the worklist appropriately.
 462     AnalysisWorklist worklist;
 463     AnalysisIndex index{
 464       worklist,
 465       std::move(classes.vals),
 466       std::move(funcs.vals),
 467       std::move(units.vals),
 468       std::move(clsBC.vals),
 469       std::move(funcBC.vals),
 470       std::move(cinfos.vals),
 471       std::move(finfos.vals),
 472       std::move(minfos.vals),
 473       std::move(depClasses.vals),
 474       std::move(depFuncs.vals),
 475       std::move(depUnits.vals),
 476       std::move(meta),
 477       AnalysisIndex::Mode::Constants
 478     };
 479
 480     // Keep processing work until we reach a fixed-point (nothing new
 481     // gets put on the worklist).
 482     while (process(index, worklist)) {}
 483     // Freeze the index. Nothing is allowed to update the index after
 484     // this. This will also re-load the worklist with all of the
 485     // classes which will end up in the output.
 486     index.freeze();
 487     // Now do a pass through the original work items again. Now that
 488     // the index is frozen, we'll gather up any dependencies from the
 489     // analysis. Since we already reached a fixed point, this should
 490     // not cause any updates (and if it does, we'll assert).
 491     while (process(index, worklist)) {}
 492     // Everything is analyzed and dependencies are recorded. Turn the
 493     // index data into AnalysisIndex::Output and return it from this
 494     // job.
 495     return index.finish();
 496   }
 497
 498 private:
 499   // Analyze the work item at the front of the worklist (returning
 500   // false if the list is empty).
 501   static bool process(AnalysisIndex& index,
 502                       AnalysisWorklist& worklist) {
 503     auto const w = worklist.next();
 504     if (auto const c = w.cls()) {
 505       update(analyze(*c, index), index);
 506     } else if (auto const f = w.func()) {
 507       update(analyze(*f, index), index);
 508     } else if (auto const u = w.unit()) {
 509       update(analyze(*u, index), index);
 510     } else {
 511       return false;
 512     }
 513     return true;
 514   }
 515
 516   static FuncAnalysisResult analyze(const php::Func& f,
 517                                     const AnalysisIndex& index) {
 518     auto const wf = php::WideFunc::cns(&f);
 519     AnalysisContext ctx{ f.unit, wf, f.cls };
 520     return analyze_func(AnalysisIndexAdaptor{ index }, ctx, CollectionOpts{});
 521   }
 522
 523   static ClassAnalysis analyze(const php::Class& c,
 524                                const AnalysisIndex& index) {
 525     return analyze_class_constants(
 526       AnalysisIndexAdaptor { index },
 527       Context { c.unit, nullptr, &c }
 528     );
 529   }
 530
 531   static UnitAnalysis analyze(const php::Unit& u, const AnalysisIndex& index) {
 532     return analyze_unit(index, Context { u.filename, nullptr, nullptr });
 533   }
 534
 535   static void update(FuncAnalysisResult fa, AnalysisIndex& index) {
 536     SCOPE_ASSERT_DETAIL("update func") {
 537       return "Updating Func: " + show(fa.ctx);
 538     };
 539
 540     auto const UNUSED bump =
 541       trace_bump(fa.ctx, Trace::hhbbc, Trace::hhbbc_cfg, Trace::hhbbc_index);
 542     AnalysisIndexAdaptor adaptor{index};
 543     ContextPusher _{adaptor, fa.ctx};
 544     index.refine_return_info(fa);
 545     index.refine_constants(fa);
 546     index.refine_class_constants(fa);
 547     index.update_prop_initial_values(fa);
 548     index.update_bytecode(fa);
 549   }
 550
 551   static void update(ClassAnalysis ca, AnalysisIndex& index) {
 552     SCOPE_ASSERT_DETAIL("update class") {
 553       return "Updating Class: " + show(ca.ctx);
 554     };
 555
 556     {
 557       auto const UNUSED bump =
 558         trace_bump(ca.ctx, Trace::hhbbc, Trace::hhbbc_cfg, Trace::hhbbc_index);
 559       AnalysisIndexAdaptor adaptor{index};
 560       ContextPusher _{adaptor, ca.ctx};
 561       index.update_type_consts(ca);
 562     }
 563     for (auto& fa : ca.methods)  update(std::move(fa), index);
 564     for (auto& fa : ca.closures) update(std::move(fa), index);
 565   }
 566
 567   static void update(UnitAnalysis ua, AnalysisIndex& index) {
 568     SCOPE_ASSERT_DETAIL("update unit") {
 569       return "Updating Unit: " + show(ua.ctx);
 570     };
 571     AnalysisIndexAdaptor adaptor{index};
 572     ContextPusher _{adaptor, ua.ctx};
 573     index.update_type_aliases(ua);
 574   }
 575 };
 576
 577 Job<AnalyzeConstantsJob> s_analyzeConstantsJob;
 578
 579 void analyze_constants(Index& index) {
 580   trace_time tracer{"analyze constants", index.sample()};
 581
 582   constexpr size_t kBucketSize = 2000;
 583   constexpr size_t kMaxBucketSize = 30000;
 584
 585   using namespace folly::gen;
 586
 587   // We'll only process classes with 86*init functions or top-level
 588   // 86cinits.
 589   AnalysisScheduler scheduler{index};
 590   for (auto const cls : index.classes_with_86inits()) {
 591     scheduler.registerClass(cls);
 592   }
 593   for (auto const func : index.constant_init_funcs()) {
 594     scheduler.registerFunc(func);
 595   }
 596   for (auto const unit : index.units_with_type_aliases()) {
 597     scheduler.registerUnit(unit);
 598   }
 599
 600   auto const run = [&] (AnalysisInput input) -> coro::Task<void> {
 601     co_await coro::co_reschedule_on_current_executor;
 602
 603     if (input.empty()) co_return;
 604
 605     Client::ExecMetadata metadata{
 606       .job_key = folly::sformat("analyze constants {}", input.key())
 607     };
 608
 609     auto [inputMeta, config] = co_await coro::collectAll(
 610       index.client().store(input.takeMeta()),
 611       index.configRef().getCopy()
 612     );
 613
 614     // Run the job
 615     auto outputs = co_await index.client().exec(
 616       s_analyzeConstantsJob,
 617       std::move(config),
 618       singleton_vec(input.toTuple(std::move(inputMeta))),
 619       std::move(metadata)
 620     );
 621     always_assert(outputs.size() == 1);
 622     auto& [clsRefs, funcRefs, unitRefs,
 623            clsBCRefs, funcBCRefs,
 624            cinfoRefs, finfoRefs,
 625            minfoRefs, metaRef] = outputs[0];
 626
 627     auto meta = co_await index.client().load(std::move(metaRef));
 628
 629     auto classNames = input.classNames();
 630     auto cinfoNames = input.cinfoNames();
 631     auto minfoNames = input.minfoNames();
 632     always_assert(clsRefs.size() == classNames.size());
 633     always_assert(clsBCRefs.size() == classNames.size());
 634     always_assert(cinfoRefs.size() == cinfoNames.size());
 635     always_assert(minfoRefs.size() == minfoNames.size());
 636     always_assert(meta.classDeps.size() == classNames.size());
 637
 638     auto funcNames = from(input.funcNames())
 639       | filter([&] (SString n) { return !meta.removedFuncs.count(n); })
 640       | as<std::vector>();
 641     always_assert(funcRefs.size() == funcNames.size());
 642     always_assert(funcBCRefs.size() == funcNames.size());
 643     always_assert(finfoRefs.size() == funcNames.size());
 644     always_assert(meta.funcDeps.size() == funcNames.size());
 645
 646     auto unitNames = input.unitNames();
 647     always_assert(unitRefs.size() == unitNames.size());
 648
 649     // Inform the scheduler
 650     scheduler.record(
 651       AnalysisOutput{
 652         std::move(classNames),
 653         std::move(cinfoNames),
 654         std::move(minfoNames),
 655         std::move(clsRefs),
 656         std::move(clsBCRefs),
 657         std::move(cinfoRefs),
 658         std::move(funcNames),
 659         std::move(funcRefs),
 660         std::move(funcBCRefs),
 661         std::move(finfoRefs),
 662         std::move(minfoRefs),
 663         std::move(unitNames),
 664         std::move(unitRefs),
 665         std::move(meta)
 666       }
 667     );
 668     co_return;
 669   };
 670
 671   size_t round{0};
 672   while (auto const workItems = scheduler.workItems()) {
 673     trace_time trace{
 674       "analyze constants round",
 675       folly::sformat("round {} -- {} work items", round, workItems)
 676     };
 677     // Get the work buckets from the scheduler.
 678     auto const work = [&] {
 679       trace_time trace2{
 680         "analyze constants schedule",
 681         folly::sformat("round {}", round)
 682       };
 683       trace2.ignore_client_stats();
 684       return scheduler.schedule(kBucketSize, kMaxBucketSize);
 685     }();
 686     // Work shouldn't be empty because we add non-zero work items this
 687     // round.
 688     assertx(!work.empty());
 689
 690     {
 691       // Process the work buckets in individual analyze constants
 692       // jobs. These will record their results as each one finishes.
 693       trace_time trace2{
 694         "analyze constants run",
 695         folly::sformat("round {}", round)
 696       };
 697       trace2.ignore_client_stats();
 698       coro::blockingWait(coro::collectAllRange(
 699         from(work)
 700           | move
 701           | map([&] (AnalysisInput input) {
 702               return run(std::move(input)).scheduleOn(index.executor().sticky());
 703             })
 704           | as<std::vector>()
 705       ));
 706     }
 707
 708     {
 709       // All the jobs recorded their results in the scheduler. Now let
 710       // the scheduler know that all jobs are done, so it can
 711       // determine what needs to be run in the next round.
 712       trace_time trace2{
 713         "analyze constants deps",
 714         folly::sformat("round {}", round)
 715       };
 716       trace2.ignore_client_stats();
 717       scheduler.recordingDone();
 718       ++round;
 719     }
 720   }
 721 }
 722
 723 //////////////////////////////////////////////////////////////////////
 724
 725 }
 726
 727 //////////////////////////////////////////////////////////////////////
 728
 729 struct WholeProgramInput::Key::Impl {
 730   enum class Type {
 731     None,
 732     Fail,
 733     Unit,
 734     Func,
 735     FuncBytecode,
 736     Class,
 737     ClassBytecode
 738   };
 739
 740   using UnresolvedTypes =
 741     hphp_fast_set<SString, string_data_hash, string_data_tsame>;
 742
 743   struct FailInfo {
 744     LSString message;
 745     template <typename SerDe> void serde(SerDe& sd) { sd(message); }
 746   };
 747   struct UnitInfo {
 748     LSString name;
 749     std::vector<TypeMapping> typeMappings;
 750     std::vector<std::pair<SString, bool>> constants;
 751     template <typename SerDe> void serde(SerDe& sd) {
 752       sd(name)
 753         (typeMappings)
 754         (constants)
 755         ;
 756     }
 757   };
 758   struct FuncInfo {
 759     LSString name;
 760     LSString unit;
 761     bool methCaller;
 762     UnresolvedTypes unresolvedTypes;
 763     template <typename SerDe> void serde(SerDe& sd) {
 764       sd(name)
 765         (unit)
 766         (methCaller)
 767         (unresolvedTypes, string_data_lt_type{})
 768         ;
 769     }
 770   };
 771   struct FuncBytecodeInfo {
 772     LSString name;
 773     LSString unit;
 774     bool methCaller;
 775     template <typename SerDe> void serde(SerDe& sd) {
 776       sd(name)(unit)(methCaller);
 777     }
 778   };
 779   struct ClassInfo {
 780     LSString name;
 781     LSString context;
 782     LSString unit;
 783     std::vector<SString> closures;
 784     std::vector<SString> dependencies;
 785     bool has86init;
 786     Optional<TypeMapping> typeMapping;
 787     UnresolvedTypes unresolvedTypes;
 788     template <typename SerDe> void serde(SerDe& sd) {
 789       sd(name)
 790         (context)
 791         (unit)
 792         (closures)
 793         (dependencies)
 794         (has86init)
 795         (typeMapping)
 796         (unresolvedTypes, string_data_lt_type{})
 797         ;
 798     }
 799   };
 800   struct ClassBytecodeInfo {
 801     LSString name;
 802     template <typename SerDe> void serde(SerDe& sd) {
 803       sd(name);
 804     }
 805   };
 806
 807   Type type;
 808   union {
 809     FailInfo fail;
 810     UnitInfo unit;
 811     FuncInfo func;
 812     FuncBytecodeInfo funcBC;
 813     ClassInfo cls;
 814     ClassBytecodeInfo clsBC;
 815   };
 816
 817   Impl() : type{Type::None} {}
 818
 819   explicit Impl(FailInfo i)  : type{Type::Fail},  fail{std::move(i)} {}
 820   explicit Impl(UnitInfo i)  : type{Type::Unit},  unit{std::move(i)} {}
 821   explicit Impl(FuncInfo i)  : type{Type::Func},  func{std::move(i)} {}
 822   explicit Impl(ClassInfo i) : type{Type::Class}, cls{std::move(i)}  {}
 823   explicit Impl(FuncBytecodeInfo i)
 824     : type{Type::FuncBytecode}, funcBC{std::move(i)} {}
 825   explicit Impl(ClassBytecodeInfo i)
 826     : type{Type::ClassBytecode}, clsBC{std::move(i)} {}
 827
 828   Impl(const Impl&) = delete;
 829   Impl(Impl&&) = delete;
 830   Impl& operator=(const Impl&) = delete;
 831   Impl& operator=(Impl&&) = delete;
 832
 833   void destroyInfo() {
 834     switch (type) {
 835       case Type::None:  break;
 836       case Type::Fail:  fail.~FailInfo();  break;
 837       case Type::Unit:  unit.~UnitInfo();  break;
 838       case Type::Func:  func.~FuncInfo();  break;
 839       case Type::Class: cls.~ClassInfo();  break;
 840       case Type::FuncBytecode:
 841         funcBC.~FuncBytecodeInfo();
 842         break;
 843       case Type::ClassBytecode:
 844         clsBC.~ClassBytecodeInfo();
 845         break;
 846     }
 847   }
 848
 849   ~Impl() { destroyInfo(); }
 850
 851   template <typename SerDe> void serde(SerDe& sd) {
 852     if constexpr (SerDe::deserializing) {
 853       destroyInfo();
 854       sd(type);
 855       switch (type) {
 856         case Type::None:  break;
 857         case Type::Fail:  new (&fail) FailInfo();  break;
 858         case Type::Unit:  new (&unit) UnitInfo();  break;
 859         case Type::Func:  new (&func) FuncInfo();  break;
 860         case Type::Class: new (&cls)  ClassInfo(); break;
 861         case Type::FuncBytecode:
 862           new (&funcBC) FuncBytecodeInfo();
 863           break;
 864         case Type::ClassBytecode:
 865           new (&clsBC) ClassBytecodeInfo();
 866           break;
 867       }
 868     } else {
 869       sd(type);
 870     }
 871
 872     switch (type) {
 873       case Type::None:  break;
 874       case Type::Fail:  sd(fail); break;
 875       case Type::Unit:  sd(unit); break;
 876       case Type::Func:  sd(func); break;
 877       case Type::Class: sd(cls);  break;
 878       case Type::FuncBytecode:
 879         sd(funcBC);
 880         break;
 881       case Type::ClassBytecode:
 882         sd(clsBC);
 883         break;
 884     }
 885   }
 886 };
 887
 888 struct WholeProgramInput::Value::Impl {
 889   std::unique_ptr<php::Func> func;
 890   std::unique_ptr<php::Class> cls;
 891   std::unique_ptr<php::Unit> unit;
 892   std::unique_ptr<php::FuncBytecode> funcBC;
 893   std::unique_ptr<php::ClassBytecode> clsBC;
 894
 895   explicit Impl(std::nullptr_t) {}
 896   explicit Impl(std::unique_ptr<php::Func> func) : func{std::move(func)} {}
 897   explicit Impl(std::unique_ptr<php::Class> cls) : cls{std::move(cls)} {}
 898   explicit Impl(std::unique_ptr<php::Unit> unit) : unit{std::move(unit)} {}
 899   explicit Impl(std::unique_ptr<php::FuncBytecode> b)  : funcBC{std::move(b)} {}
 900   explicit Impl(std::unique_ptr<php::ClassBytecode> b) : clsBC{std::move(b)} {}
 901 };
 902
 903 struct WholeProgramInput::Impl {
 904   folly::AtomicLinkedList<std::pair<Key, Ref<Value>>> values;
 905 };
 906
 907 WholeProgramInput::WholeProgramInput() : m_impl{new Impl} {}
 908
 909 void WholeProgramInput::add(Key k, extern_worker::Ref<Value> v) {
 910   assertx(m_impl);
 911   m_impl->values.insertHead(std::make_pair(std::move(k), std::move(v)));
 912 }
 913
 914 std::vector<std::pair<WholeProgramInput::Key, WholeProgramInput::Value>>
 915 WholeProgramInput::make(std::unique_ptr<UnitEmitter> ue) {
 916   assertx(ue);
 917
 918   auto parsed = parse_unit(*ue);
 919
 920   std::vector<std::pair<Key, Value>> out;
 921
 922   using KeyI = Key::Impl;
 923   using ValueI = Value::Impl;
 924
 925   auto const add = [&] (auto k, auto v) {
 926     Key key;
 927     Value value;
 928     key.m_impl.reset(new KeyI{std::move(k)});
 929     value.m_impl.reset(new ValueI{std::move(v)});
 930     out.emplace_back(std::move(key), std::move(value));
 931   };
 932
 933   auto const addType =
 934     [&] (KeyI::UnresolvedTypes& u,
 935          const TypeConstraint& tc,
 936          const php::Class* cls = nullptr,
 937          const TypeIntersectionConstraint* ubs = nullptr) {
 938     // Skip names which match the current class name. We don't need to
 939     // report these as it's implicit.
 940     if (tc.isUnresolved() && (!cls || !cls->name->tsame(tc.typeName()))) {
 941       u.emplace(tc.typeName());
 942     }
 943     if (!ubs) return;
 944     for (auto const& ub : ubs->m_constraints) {
 945       if (ub.isUnresolved() && (!cls || !cls->name->tsame(ub.typeName()))) {
 946         u.emplace(ub.typeName());
 947       }
 948     }
 949   };
 950
 951   auto const addFuncTypes = [&] (KeyI::UnresolvedTypes& u,
 952                                  const php::Func& f,
 953                                  const php::Class* cls = nullptr) {
 954     for (auto const& p : f.params) {
 955       addType(u, p.typeConstraint, cls, &p.upperBounds);
 956     }
 957     addType(u, f.retTypeConstraint, cls, &f.returnUBs);
 958   };
 959
 960   if (parsed.unit) {
 961     if (auto const& fi = parsed.unit->fatalInfo) {
 962       auto const msg = makeStaticString(fi->fatalMsg);
 963       if (!fi->fatalLoc) {
 964         add(KeyI::FailInfo{msg}, nullptr);
 965         return out;
 966       }
 967     }
 968
 969     KeyI::UnitInfo info{parsed.unit->filename};
 970     for (auto const& typeAlias : parsed.unit->typeAliases) {
 971       info.typeMappings.emplace_back(
 972         TypeMapping{
 973           typeAlias->name,
 974           nullptr,
 975           typeAlias->value,
 976           true
 977         }
 978       );
 979     }
 980     for (auto const& cns : parsed.unit->constants) {
 981       info.constants.emplace_back(
 982         cns->name,
 983         type(cns->val) == KindOfUninit
 984       );
 985     }
 986     add(std::move(info), std::move(parsed.unit));
 987   }
 988
 989   auto const onCls = [&] (std::unique_ptr<php::Class>& c,
 990                           php::ClassBytecode& bc,
 991                           KeyI::UnresolvedTypes& types,
 992                           std::vector<SString>& deps,
 993                           bool& has86init) {
 994     assertx(IMPLIES(is_closure(*c), c->methods.size() == 1));
 995
 996     for (auto& m : c->methods) {
 997       addFuncTypes(types, *m, c.get());
 998       bc.methodBCs.emplace_back(m->name, std::move(m->rawBlocks));
 999       assertx(IMPLIES(is_closure(*c), !is_86init_func(*m)));
1000       has86init |= is_86init_func(*m);
1001     }
1002     for (auto const& p : c->properties) {
1003       addType(types, p.typeConstraint, c.get(), &p.ubs);
1004     }
1005
1006     auto const d = Index::Input::makeDeps(*c);
1007     deps.insert(end(deps), begin(d), end(d));
1008
1009     assertx(IMPLIES(is_closure(*c), !(c->attrs & AttrEnum)));
1010   };
1011
1012   for (auto& c : parsed.classes) {
1013     auto const name = c->name;
1014     auto const declFunc = c->closureDeclFunc;
1015     auto const unit = c->unit;
1016
1017     assertx(IMPLIES(is_closure(*c), !c->closureContextCls));
1018     assertx(IMPLIES(is_closure(*c), declFunc));
1019
1020     auto has86init = false;
1021     php::ClassBytecode bc{name};
1022     KeyI::UnresolvedTypes types;
1023     std::vector<SString> deps;
1024     std::vector<SString> closures;
1025
1026     onCls(c, bc, types, deps, has86init);
1027     for (auto& clo : c->closures) {
1028       assertx(is_closure(*clo));
1029       onCls(clo, bc, types, deps, has86init);
1030       closures.emplace_back(clo->name);
1031     }
1032
1033     Optional<TypeMapping> typeMapping;
1034     if (c->attrs & AttrEnum) {
1035       assertx(!is_closure(*c));
1036       auto tc = c->enumBaseTy;
1037       assertx(!tc.isNullable());
1038       addType(types, tc, nullptr);
1039       if (tc.isMixed()) tc.setType(AnnotType::ArrayKey);
1040       typeMapping.emplace(TypeMapping{c->name, c->name, tc, false});
1041     }
1042
1043     std::sort(begin(deps), end(deps), string_data_lt_type{});
1044     deps.erase(
1045       std::unique(begin(deps), end(deps), string_data_tsame{}),
1046       end(deps)
1047     );
1048
1049     std::sort(begin(closures), end(closures), string_data_lt_type{});
1050
1051     add(
1052       KeyI::ClassBytecodeInfo{name},
1053       std::make_unique<php::ClassBytecode>(std::move(bc))
1054     );
1055     add(
1056       KeyI::ClassInfo{
1057         name,
1058         declFunc,
1059         unit,
1060         std::move(closures),
1061         std::move(deps),
1062         has86init,
1063         std::move(typeMapping),
1064         std::move(types)
1065       },
1066       std::move(c)
1067     );
1068   }
1069
1070   for (auto& f : parsed.funcs) {
1071     auto const name = f->name;
1072     auto const unit = f->unit;
1073     auto const methCaller = bool(f->attrs & AttrIsMethCaller);
1074
1075     KeyI::UnresolvedTypes types;
1076     addFuncTypes(types, *f);
1077
1078     add(
1079       KeyI::FuncBytecodeInfo{name, unit, methCaller},
1080       std::make_unique<php::FuncBytecode>(name, std::move(f->rawBlocks))
1081     );
1082     add(
1083       KeyI::FuncInfo{name, unit, methCaller, std::move(types)},
1084       std::move(f)
1085     );
1086   }
1087   return out;
1088 }
1089
1090 void WholeProgramInput::Key::serde(BlobEncoder& sd) const {
1091   assertx(m_impl);
1092   sd(*m_impl);
1093 }
1094
1095 void WholeProgramInput::Key::serde(BlobDecoder& sd) {
1096   m_impl.reset(new Impl());
1097   sd(*m_impl);
1098 }
1099
1100 void WholeProgramInput::Value::serde(BlobEncoder& sd) const {
1101   assertx(m_impl);
1102   assertx(
1103     (bool)m_impl->func + (bool)m_impl->cls + (bool)m_impl->unit +
1104     (bool)m_impl->funcBC + (bool)m_impl->clsBC <= 1
1105   );
1106   if (m_impl->func) {
1107     sd(m_impl->func, nullptr);
1108   } else if (m_impl->cls) {
1109     sd(m_impl->cls);
1110   } else if (m_impl->unit) {
1111     sd(m_impl->unit);
1112   } else if (m_impl->funcBC) {
1113     sd(m_impl->funcBC);
1114   } else if (m_impl->clsBC) {
1115     sd(m_impl->clsBC);
1116   }
1117 }
1118
1119 void WholeProgramInput::Key::Deleter::operator()(Impl* i) const {
1120   delete i;
1121 }
1122 void WholeProgramInput::Value::Deleter::operator()(Impl* i) const {
1123   delete i;
1124 }
1125 void WholeProgramInput::Deleter::operator()(Impl* i) const {
1126   delete i;
1127 }
1128
1129 //////////////////////////////////////////////////////////////////////
1130
1131 namespace {
1132
1133 Index::Input make_index_input(WholeProgramInput input) {
1134   Index::Input out;
1135
1136   using WPI = WholeProgramInput;
1137   using Key = WPI::Key::Impl;
1138
1139   input.m_impl->values.sweep(
1140     [&] (std::pair<WPI::Key, Ref<WPI::Value>>&& p) {
1141       switch (p.first.m_impl->type) {
1142         case Key::Type::None:
1143           break;
1144         case Key::Type::Fail:
1145           // An unit which failed the verifier. This causes us
1146           // to exit immediately with an error.
1147           fprintf(stderr, "%s", p.first.m_impl->fail.message->data());
1148           _Exit(HPHP_EXIT_FAILURE);
1149           break;
1150         case Key::Type::Class:
1151           out.classes.emplace_back(
1152             Index::Input::ClassMeta{
1153               p.second.cast<std::unique_ptr<php::Class>>(),
1154               p.first.m_impl->cls.name,
1155               std::move(p.first.m_impl->cls.dependencies),
1156               p.first.m_impl->cls.context,
1157               std::move(p.first.m_impl->cls.closures),
1158               p.first.m_impl->cls.unit,
1159               p.first.m_impl->cls.has86init,
1160               std::move(p.first.m_impl->cls.typeMapping),
1161               std::vector<SString>{
1162                 begin(p.first.m_impl->cls.unresolvedTypes),
1163                 end(p.first.m_impl->cls.unresolvedTypes)
1164               }
1165             }
1166           );
1167           break;
1168         case Key::Type::Func:
1169           out.funcs.emplace_back(
1170             Index::Input::FuncMeta{
1171               p.second.cast<std::unique_ptr<php::Func>>(),
1172               p.first.m_impl->func.name,
1173               p.first.m_impl->func.unit,
1174               p.first.m_impl->func.methCaller,
1175               std::vector<SString>{
1176                 begin(p.first.m_impl->func.unresolvedTypes),
1177                 end(p.first.m_impl->func.unresolvedTypes)
1178               }
1179             }
1180           );
1181           break;
1182         case Key::Type::Unit:
1183           out.units.emplace_back(
1184             Index::Input::UnitMeta{
1185               p.second.cast<std::unique_ptr<php::Unit>>(),
1186               p.first.m_impl->unit.name,
1187               std::move(p.first.m_impl->unit.typeMappings),
1188               std::move(p.first.m_impl->unit.constants)
1189             }
1190           );
1191           break;
1192         case Key::Type::FuncBytecode:
1193           out.funcBC.emplace_back(
1194             Index::Input::FuncBytecodeMeta{
1195               p.second.cast<std::unique_ptr<php::FuncBytecode>>(),
1196               p.first.m_impl->funcBC.name,
1197               p.first.m_impl->funcBC.unit,
1198               p.first.m_impl->funcBC.methCaller
1199             }
1200           );
1201           break;
1202         case Key::Type::ClassBytecode:
1203           out.classBC.emplace_back(
1204             Index::Input::ClassBytecodeMeta{
1205               p.second.cast<std::unique_ptr<php::ClassBytecode>>(),
1206               p.first.m_impl->clsBC.name
1207             }
1208           );
1209           break;
1210       }
1211     }
1212   );
1213
1214   return out;
1215 }
1216
1217 //////////////////////////////////////////////////////////////////////
1218
1219 }
1220
1221 //////////////////////////////////////////////////////////////////////
1222
1223 void whole_program(WholeProgramInput inputs,
1224                    Config config,
1225                    std::unique_ptr<TicketExecutor> executor,
1226                    std::unique_ptr<Client> client,
1227                    const EmitCallback& callback,
1228                    DisposeCallback dispose,
1229                    StructuredLogEntry* sample,
1230                    int num_threads) {
1231   trace_time tracer("whole program", sample);
1232
1233   if (sample) {
1234     sample->setInt("hhbbc_thread_count", executor->numThreads());
1235   }
1236
1237   if (num_threads > 0) {
1238     parallel::num_threads = num_threads;
1239     // Leave a thread free for cleanup
1240     parallel::final_threads = (num_threads > 1) ? (num_threads - 1) : 1;
1241   }
1242
1243   Index index{
1244     make_index_input(std::move(inputs)),
1245     std::move(config),
1246     std::move(executor),
1247     std::move(client),
1248     std::move(dispose),
1249     sample
1250   };
1251
1252   analyze_constants(index);
1253   index.make_local();
1254
1255   auto stats = allocate_stats();
1256   auto const emitUnit = [&] (php::Unit& unit) {
1257     auto ue = emit_unit(index, unit);
1258     if (RO::EvalAbortBuildOnVerifyError && !ue->check(false)) {
1259       fprintf(
1260         stderr,
1261         "The optimized unit for %s did not pass verification, "
1262         "bailing because Eval.AbortBuildOnVerifyError is set\n",
1263         ue->m_filepath->data()
1264       );
1265       _Exit(HPHP_EXIT_FAILURE);
1266     }
1267     callback(std::move(ue));
1268   };
1269
1270   assertx(check(index.program()));
1271
1272   // Defer preresolve type-structures and initializing public static
1273   // property types until after the constant pass, to try to get
1274   // better initial values.
1275   index.use_class_dependencies(false);
1276   index.preresolve_type_structures();
1277   index.use_class_dependencies(true);
1278   analyze_iteratively(index);
1279   auto cleanup_for_final = std::thread([&] { index.cleanup_for_final(); });
1280   parallel::num_threads = parallel::final_threads;
1281   final_pass(index, stats, emitUnit);
1282   cleanup_for_final.join();
1283
1284   print_stats(stats);
1285
1286   if (sample) {
1287     sample->setInt("hhbbc_num_units", index.program().units.size());
1288     sample->setInt("hhbbc_num_classes", index.program().classes.size());
1289     sample->setInt("hhbbc_num_funcs", index.program().funcs.size());
1290   }
1291
1292   index.cleanup_post_emit();
1293   summarize_memory(sample);
1294 }
1295
1296 //////////////////////////////////////////////////////////////////////
1297
1298 }}