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,
 601                         CoroLatch& latch) -> coro::Task<void> {
 602     auto guard = folly::makeGuard([&] { latch.count_down(); });
 603
 604     co_await coro::co_reschedule_on_current_executor;
 605
 606     if (input.empty()) co_return;
 607
 608     Client::ExecMetadata metadata{
 609       .job_key = folly::sformat("analyze constants {}", input.key())
 610     };
 611
 612     auto [inputMeta, config] = co_await coro::collectAll(
 613       index.client().store(input.takeMeta()),
 614       index.configRef().getCopy()
 615     );
 616
 617     auto classNames = input.classNames();
 618     auto cinfoNames = input.cinfoNames();
 619     auto minfoNames = input.minfoNames();
 620     auto funcNames = input.funcNames();
 621     auto unitNames = input.unitNames();
 622     auto tuple = input.toTuple(std::move(inputMeta));
 623
 624     // Signal we're done touching the Index.
 625     guard.dismiss();
 626     latch.count_down();
 627
 628     auto outputs = co_await index.client().exec(
 629       s_analyzeConstantsJob,
 630       std::move(config),
 631       singleton_vec(std::move(tuple)),
 632       std::move(metadata)
 633     );
 634
 635     // Run the job
 636     always_assert(outputs.size() == 1);
 637     auto& [clsRefs, funcRefs, unitRefs,
 638            clsBCRefs, funcBCRefs,
 639            cinfoRefs, finfoRefs,
 640            minfoRefs, metaRef] = outputs[0];
 641
 642     // We cannot call scheduler.record below until all co-routines have called
 643     // input.toTuple (record modifies the Index and toTuple reads from it), so
 644     // block here until the latch is cleared. Technically we only need to wait
 645     // on this before scheduler.record, but by doing this before the load, we
 646     // avoid blocking while holding onto a lot of memory.
 647     co_await latch.wait();
 648
 649     auto meta = co_await index.client().load(std::move(metaRef));
 650
 651     funcNames.erase(
 652       std::remove_if(
 653         begin(funcNames),
 654         end(funcNames),
 655         [&] (SString n) { return meta.removedFuncs.count(n); }
 656       ),
 657       end(funcNames)
 658     );
 659
 660     always_assert(clsRefs.size() == classNames.size());
 661     always_assert(clsBCRefs.size() == classNames.size());
 662     always_assert(cinfoRefs.size() == cinfoNames.size());
 663     always_assert(minfoRefs.size() == minfoNames.size());
 664     always_assert(meta.classDeps.size() == classNames.size());
 665     always_assert(funcRefs.size() == funcNames.size());
 666     always_assert(funcBCRefs.size() == funcNames.size());
 667     always_assert(finfoRefs.size() == funcNames.size());
 668     always_assert(meta.funcDeps.size() == funcNames.size());
 669     always_assert(unitRefs.size() == unitNames.size());
 670
 671     // Inform the scheduler
 672     scheduler.record(
 673       AnalysisOutput{
 674         std::move(classNames),
 675         std::move(cinfoNames),
 676         std::move(minfoNames),
 677         std::move(clsRefs),
 678         std::move(clsBCRefs),
 679         std::move(cinfoRefs),
 680         std::move(funcNames),
 681         std::move(funcRefs),
 682         std::move(funcBCRefs),
 683         std::move(finfoRefs),
 684         std::move(minfoRefs),
 685         std::move(unitNames),
 686         std::move(unitRefs),
 687         std::move(meta)
 688       }
 689     );
 690     co_return;
 691   };
 692
 693   size_t round{0};
 694   while (auto const workItems = scheduler.workItems()) {
 695     trace_time trace{
 696       "analyze constants round",
 697       folly::sformat("round {} -- {} work items", round, workItems)
 698     };
 699     // Get the work buckets from the scheduler.
 700     auto work = [&] {
 701       trace_time trace2{
 702         "analyze constants schedule",
 703         folly::sformat("round {}", round)
 704       };
 705       trace2.ignore_client_stats();
 706       return scheduler.schedule(kBucketSize, kMaxBucketSize);
 707     }();
 708     // Work shouldn't be empty because we add non-zero work items this
 709     // round.
 710     assertx(!work.empty());
 711
 712     {
 713       // Process the work buckets in individual analyze constants
 714       // jobs. These will record their results as each one finishes.
 715       trace_time trace2{
 716         "analyze constants run",
 717         folly::sformat("round {}", round)
 718       };
 719       trace2.ignore_client_stats();
 720
 721       CoroLatch latch{work.size()};
 722       coro::blockingWait(coro::collectAllRange(
 723         from(work)
 724           | move
 725           | map([&] (AnalysisInput&& input) {
 726               return run(std::move(input), latch)
 727                 .scheduleOn(index.executor().sticky());
 728             })
 729           | as<std::vector>()
 730       ));
 731     }
 732
 733     {
 734       // All the jobs recorded their results in the scheduler. Now let
 735       // the scheduler know that all jobs are done, so it can
 736       // determine what needs to be run in the next round.
 737       trace_time trace2{
 738         "analyze constants deps",
 739         folly::sformat("round {}", round)
 740       };
 741       trace2.ignore_client_stats();
 742       scheduler.recordingDone();
 743       ++round;
 744     }
 745   }
 746 }
 747
 748 //////////////////////////////////////////////////////////////////////
 749
 750 }
 751
 752 //////////////////////////////////////////////////////////////////////
 753
 754 struct WholeProgramInput::Key::Impl {
 755   enum class Type {
 756     None,
 757     Fail,
 758     Unit,
 759     Func,
 760     FuncBytecode,
 761     Class,
 762     ClassBytecode
 763   };
 764
 765   using UnresolvedTypes =
 766     hphp_fast_set<SString, string_data_hash, string_data_tsame>;
 767
 768   struct FailInfo {
 769     LSString message;
 770     template <typename SerDe> void serde(SerDe& sd) { sd(message); }
 771   };
 772   struct UnitInfo {
 773     LSString name;
 774     std::vector<TypeMapping> typeMappings;
 775     std::vector<std::pair<SString, bool>> constants;
 776     template <typename SerDe> void serde(SerDe& sd) {
 777       sd(name)
 778         (typeMappings)
 779         (constants)
 780         ;
 781     }
 782   };
 783   struct FuncInfo {
 784     LSString name;
 785     LSString unit;
 786     bool methCaller;
 787     UnresolvedTypes unresolvedTypes;
 788     template <typename SerDe> void serde(SerDe& sd) {
 789       sd(name)
 790         (unit)
 791         (methCaller)
 792         (unresolvedTypes, string_data_lt_type{})
 793         ;
 794     }
 795   };
 796   struct FuncBytecodeInfo {
 797     LSString name;
 798     LSString unit;
 799     bool methCaller;
 800     template <typename SerDe> void serde(SerDe& sd) {
 801       sd(name)(unit)(methCaller);
 802     }
 803   };
 804   struct ClassInfo {
 805     LSString name;
 806     LSString context;
 807     LSString unit;
 808     std::vector<SString> closures;
 809     std::vector<SString> dependencies;
 810     bool has86init;
 811     Optional<TypeMapping> typeMapping;
 812     UnresolvedTypes unresolvedTypes;
 813     template <typename SerDe> void serde(SerDe& sd) {
 814       sd(name)
 815         (context)
 816         (unit)
 817         (closures)
 818         (dependencies)
 819         (has86init)
 820         (typeMapping)
 821         (unresolvedTypes, string_data_lt_type{})
 822         ;
 823     }
 824   };
 825   struct ClassBytecodeInfo {
 826     LSString name;
 827     template <typename SerDe> void serde(SerDe& sd) {
 828       sd(name);
 829     }
 830   };
 831
 832   Type type;
 833   union {
 834     FailInfo fail;
 835     UnitInfo unit;
 836     FuncInfo func;
 837     FuncBytecodeInfo funcBC;
 838     ClassInfo cls;
 839     ClassBytecodeInfo clsBC;
 840   };
 841
 842   Impl() : type{Type::None} {}
 843
 844   explicit Impl(FailInfo i)  : type{Type::Fail},  fail{std::move(i)} {}
 845   explicit Impl(UnitInfo i)  : type{Type::Unit},  unit{std::move(i)} {}
 846   explicit Impl(FuncInfo i)  : type{Type::Func},  func{std::move(i)} {}
 847   explicit Impl(ClassInfo i) : type{Type::Class}, cls{std::move(i)}  {}
 848   explicit Impl(FuncBytecodeInfo i)
 849     : type{Type::FuncBytecode}, funcBC{std::move(i)} {}
 850   explicit Impl(ClassBytecodeInfo i)
 851     : type{Type::ClassBytecode}, clsBC{std::move(i)} {}
 852
 853   Impl(const Impl&) = delete;
 854   Impl(Impl&&) = delete;
 855   Impl& operator=(const Impl&) = delete;
 856   Impl& operator=(Impl&&) = delete;
 857
 858   void destroyInfo() {
 859     switch (type) {
 860       case Type::None:  break;
 861       case Type::Fail:  fail.~FailInfo();  break;
 862       case Type::Unit:  unit.~UnitInfo();  break;
 863       case Type::Func:  func.~FuncInfo();  break;
 864       case Type::Class: cls.~ClassInfo();  break;
 865       case Type::FuncBytecode:
 866         funcBC.~FuncBytecodeInfo();
 867         break;
 868       case Type::ClassBytecode:
 869         clsBC.~ClassBytecodeInfo();
 870         break;
 871     }
 872   }
 873
 874   ~Impl() { destroyInfo(); }
 875
 876   template <typename SerDe> void serde(SerDe& sd) {
 877     if constexpr (SerDe::deserializing) {
 878       destroyInfo();
 879       sd(type);
 880       switch (type) {
 881         case Type::None:  break;
 882         case Type::Fail:  new (&fail) FailInfo();  break;
 883         case Type::Unit:  new (&unit) UnitInfo();  break;
 884         case Type::Func:  new (&func) FuncInfo();  break;
 885         case Type::Class: new (&cls)  ClassInfo(); break;
 886         case Type::FuncBytecode:
 887           new (&funcBC) FuncBytecodeInfo();
 888           break;
 889         case Type::ClassBytecode:
 890           new (&clsBC) ClassBytecodeInfo();
 891           break;
 892       }
 893     } else {
 894       sd(type);
 895     }
 896
 897     switch (type) {
 898       case Type::None:  break;
 899       case Type::Fail:  sd(fail); break;
 900       case Type::Unit:  sd(unit); break;
 901       case Type::Func:  sd(func); break;
 902       case Type::Class: sd(cls);  break;
 903       case Type::FuncBytecode:
 904         sd(funcBC);
 905         break;
 906       case Type::ClassBytecode:
 907         sd(clsBC);
 908         break;
 909     }
 910   }
 911 };
 912
 913 struct WholeProgramInput::Value::Impl {
 914   std::unique_ptr<php::Func> func;
 915   std::unique_ptr<php::Class> cls;
 916   std::unique_ptr<php::Unit> unit;
 917   std::unique_ptr<php::FuncBytecode> funcBC;
 918   std::unique_ptr<php::ClassBytecode> clsBC;
 919
 920   explicit Impl(std::nullptr_t) {}
 921   explicit Impl(std::unique_ptr<php::Func> func) : func{std::move(func)} {}
 922   explicit Impl(std::unique_ptr<php::Class> cls) : cls{std::move(cls)} {}
 923   explicit Impl(std::unique_ptr<php::Unit> unit) : unit{std::move(unit)} {}
 924   explicit Impl(std::unique_ptr<php::FuncBytecode> b)  : funcBC{std::move(b)} {}
 925   explicit Impl(std::unique_ptr<php::ClassBytecode> b) : clsBC{std::move(b)} {}
 926 };
 927
 928 struct WholeProgramInput::Impl {
 929   folly::AtomicLinkedList<std::pair<Key, Ref<Value>>> values;
 930 };
 931
 932 WholeProgramInput::WholeProgramInput() : m_impl{new Impl} {}
 933
 934 void WholeProgramInput::add(Key k, extern_worker::Ref<Value> v) {
 935   assertx(m_impl);
 936   m_impl->values.insertHead(std::make_pair(std::move(k), std::move(v)));
 937 }
 938
 939 std::vector<std::pair<WholeProgramInput::Key, WholeProgramInput::Value>>
 940 WholeProgramInput::make(std::unique_ptr<UnitEmitter> ue) {
 941   assertx(ue);
 942
 943   auto parsed = parse_unit(*ue);
 944
 945   std::vector<std::pair<Key, Value>> out;
 946
 947   using KeyI = Key::Impl;
 948   using ValueI = Value::Impl;
 949
 950   auto const add = [&] (auto k, auto v) {
 951     Key key;
 952     Value value;
 953     key.m_impl.reset(new KeyI{std::move(k)});
 954     value.m_impl.reset(new ValueI{std::move(v)});
 955     out.emplace_back(std::move(key), std::move(value));
 956   };
 957
 958   auto const addType =
 959     [&] (KeyI::UnresolvedTypes& u,
 960          const folly::Range<const TypeConstraint*>& tcs,
 961          const php::Class* cls = nullptr) {
 962     // Skip names which match the current class name. We don't need to
 963     // report these as it's implicit.
 964     for (auto const& tc : tcs) {
 965       if (tc.isUnresolved() && (!cls || !cls->name->tsame(tc.typeName()))) {
 966         u.emplace(tc.typeName());
 967       }
 968     }
 969   };
 970
 971   auto const addFuncTypes = [&] (KeyI::UnresolvedTypes& u,
 972                                  const php::Func& f,
 973                                  const php::Class* cls = nullptr) {
 974     for (auto const& p : f.params) {
 975       addType(u, p.typeConstraints.range(), cls);
 976     }
 977     addType(u, f.retTypeConstraints.range(), cls);
 978   };
 979
 980   if (parsed.unit) {
 981     if (auto const& fi = parsed.unit->fatalInfo) {
 982       auto const msg = makeStaticString(fi->fatalMsg);
 983       if (!fi->fatalLoc) {
 984         add(KeyI::FailInfo{msg}, nullptr);
 985         return out;
 986       }
 987     }
 988
 989     KeyI::UnitInfo info{parsed.unit->filename};
 990     for (auto const& typeAlias : parsed.unit->typeAliases) {
 991       info.typeMappings.emplace_back(
 992         TypeMapping{
 993           typeAlias->name,
 994           typeAlias->value,
 995           true,
 996           false
 997         }
 998       );
 999     }
1000     for (auto const& cns : parsed.unit->constants) {
1001       info.constants.emplace_back(
1002         cns->name,
1003         type(cns->val) == KindOfUninit
1004       );
1005     }
1006     add(std::move(info), std::move(parsed.unit));
1007   }
1008
1009   auto const onCls = [&] (std::unique_ptr<php::Class>& c,
1010                           php::ClassBytecode& bc,
1011                           KeyI::UnresolvedTypes& types,
1012                           std::vector<SString>& deps,
1013                           bool& has86init) {
1014     assertx(IMPLIES(is_closure(*c), c->methods.size() == 1));
1015
1016     for (auto& m : c->methods) {
1017       addFuncTypes(types, *m, c.get());
1018       bc.methodBCs.emplace_back(m->name, std::move(m->rawBlocks));
1019       assertx(IMPLIES(is_closure(*c), !is_86init_func(*m)));
1020       has86init |= is_86init_func(*m);
1021     }
1022     for (auto const& p : c->properties) {
1023       addType(types, p.typeConstraints.range(), c.get());
1024     }
1025
1026     auto const d = Index::Input::makeDeps(*c);
1027     deps.insert(end(deps), begin(d), end(d));
1028
1029     assertx(IMPLIES(is_closure(*c), !(c->attrs & AttrEnum)));
1030   };
1031
1032   for (auto& c : parsed.classes) {
1033     auto const name = c->name;
1034     auto const declFunc = c->closureDeclFunc;
1035     auto const unit = c->unit;
1036
1037     assertx(IMPLIES(is_closure(*c), !c->closureContextCls));
1038     assertx(IMPLIES(is_closure(*c), declFunc));
1039
1040     auto has86init = false;
1041     php::ClassBytecode bc{name};
1042     KeyI::UnresolvedTypes types;
1043     std::vector<SString> deps;
1044     std::vector<SString> closures;
1045
1046     onCls(c, bc, types, deps, has86init);
1047     for (auto& clo : c->closures) {
1048       assertx(is_closure(*clo));
1049       onCls(clo, bc, types, deps, has86init);
1050       closures.emplace_back(clo->name);
1051     }
1052
1053     Optional<TypeMapping> typeMapping;
1054     if (c->attrs & AttrEnum) {
1055       assertx(!is_closure(*c));
1056       auto tc = c->enumBaseTy;
1057       assertx(!tc.isNullable());
1058       addType(types, folly::Range<const TypeConstraint*>(&tc, &tc + 1), nullptr);
1059       if (tc.isMixed()) tc.setType(AnnotType::ArrayKey);
1060       typeMapping.emplace(TypeMapping{c->name, tc, false, true});
1061     }
1062
1063     std::sort(begin(deps), end(deps), string_data_lt_type{});
1064     deps.erase(
1065       std::unique(begin(deps), end(deps), string_data_tsame{}),
1066       end(deps)
1067     );
1068
1069     std::sort(begin(closures), end(closures), string_data_lt_type{});
1070
1071     add(
1072       KeyI::ClassBytecodeInfo{name},
1073       std::make_unique<php::ClassBytecode>(std::move(bc))
1074     );
1075     add(
1076       KeyI::ClassInfo{
1077         name,
1078         declFunc,
1079         unit,
1080         std::move(closures),
1081         std::move(deps),
1082         has86init,
1083         std::move(typeMapping),
1084         std::move(types)
1085       },
1086       std::move(c)
1087     );
1088   }
1089
1090   for (auto& f : parsed.funcs) {
1091     auto const name = f->name;
1092     auto const unit = f->unit;
1093     auto const methCaller = bool(f->attrs & AttrIsMethCaller);
1094
1095     KeyI::UnresolvedTypes types;
1096     addFuncTypes(types, *f);
1097
1098     add(
1099       KeyI::FuncBytecodeInfo{name, unit, methCaller},
1100       std::make_unique<php::FuncBytecode>(name, std::move(f->rawBlocks))
1101     );
1102     add(
1103       KeyI::FuncInfo{name, unit, methCaller, std::move(types)},
1104       std::move(f)
1105     );
1106   }
1107   return out;
1108 }
1109
1110 void WholeProgramInput::Key::serde(BlobEncoder& sd) const {
1111   assertx(m_impl);
1112   sd(*m_impl);
1113 }
1114
1115 void WholeProgramInput::Key::serde(BlobDecoder& sd) {
1116   m_impl.reset(new Impl());
1117   sd(*m_impl);
1118 }
1119
1120 void WholeProgramInput::Value::serde(BlobEncoder& sd) const {
1121   assertx(m_impl);
1122   assertx(
1123     (bool)m_impl->func + (bool)m_impl->cls + (bool)m_impl->unit +
1124     (bool)m_impl->funcBC + (bool)m_impl->clsBC <= 1
1125   );
1126   if (m_impl->func) {
1127     sd(m_impl->func, nullptr);
1128   } else if (m_impl->cls) {
1129     sd(m_impl->cls);
1130   } else if (m_impl->unit) {
1131     sd(m_impl->unit);
1132   } else if (m_impl->funcBC) {
1133     sd(m_impl->funcBC);
1134   } else if (m_impl->clsBC) {
1135     sd(m_impl->clsBC);
1136   }
1137 }
1138
1139 void WholeProgramInput::Key::Deleter::operator()(Impl* i) const {
1140   delete i;
1141 }
1142 void WholeProgramInput::Value::Deleter::operator()(Impl* i) const {
1143   delete i;
1144 }
1145 void WholeProgramInput::Deleter::operator()(Impl* i) const {
1146   delete i;
1147 }
1148
1149 //////////////////////////////////////////////////////////////////////
1150
1151 namespace {
1152
1153 Index::Input make_index_input(WholeProgramInput input) {
1154   Index::Input out;
1155
1156   using WPI = WholeProgramInput;
1157   using Key = WPI::Key::Impl;
1158
1159   input.m_impl->values.sweep(
1160     [&] (std::pair<WPI::Key, Ref<WPI::Value>>&& p) {
1161       switch (p.first.m_impl->type) {
1162         case Key::Type::None:
1163           break;
1164         case Key::Type::Fail:
1165           // An unit which failed the verifier. This causes us
1166           // to exit immediately with an error.
1167           fprintf(stderr, "%s", p.first.m_impl->fail.message->data());
1168           _Exit(HPHP_EXIT_FAILURE);
1169           break;
1170         case Key::Type::Class:
1171           out.classes.emplace_back(
1172             Index::Input::ClassMeta{
1173               p.second.cast<std::unique_ptr<php::Class>>(),
1174               p.first.m_impl->cls.name,
1175               std::move(p.first.m_impl->cls.dependencies),
1176               p.first.m_impl->cls.context,
1177               std::move(p.first.m_impl->cls.closures),
1178               p.first.m_impl->cls.unit,
1179               p.first.m_impl->cls.has86init,
1180               std::move(p.first.m_impl->cls.typeMapping),
1181               std::vector<SString>{
1182                 begin(p.first.m_impl->cls.unresolvedTypes),
1183                 end(p.first.m_impl->cls.unresolvedTypes)
1184               }
1185             }
1186           );
1187           break;
1188         case Key::Type::Func:
1189           out.funcs.emplace_back(
1190             Index::Input::FuncMeta{
1191               p.second.cast<std::unique_ptr<php::Func>>(),
1192               p.first.m_impl->func.name,
1193               p.first.m_impl->func.unit,
1194               p.first.m_impl->func.methCaller,
1195               std::vector<SString>{
1196                 begin(p.first.m_impl->func.unresolvedTypes),
1197                 end(p.first.m_impl->func.unresolvedTypes)
1198               }
1199             }
1200           );
1201           break;
1202         case Key::Type::Unit:
1203           out.units.emplace_back(
1204             Index::Input::UnitMeta{
1205               p.second.cast<std::unique_ptr<php::Unit>>(),
1206               p.first.m_impl->unit.name,
1207               std::move(p.first.m_impl->unit.typeMappings),
1208               std::move(p.first.m_impl->unit.constants)
1209             }
1210           );
1211           break;
1212         case Key::Type::FuncBytecode:
1213           out.funcBC.emplace_back(
1214             Index::Input::FuncBytecodeMeta{
1215               p.second.cast<std::unique_ptr<php::FuncBytecode>>(),
1216               p.first.m_impl->funcBC.name,
1217               p.first.m_impl->funcBC.unit,
1218               p.first.m_impl->funcBC.methCaller
1219             }
1220           );
1221           break;
1222         case Key::Type::ClassBytecode:
1223           out.classBC.emplace_back(
1224             Index::Input::ClassBytecodeMeta{
1225               p.second.cast<std::unique_ptr<php::ClassBytecode>>(),
1226               p.first.m_impl->clsBC.name
1227             }
1228           );
1229           break;
1230       }
1231     }
1232   );
1233
1234   return out;
1235 }
1236
1237 //////////////////////////////////////////////////////////////////////
1238
1239 }
1240
1241 //////////////////////////////////////////////////////////////////////
1242
1243 void whole_program(WholeProgramInput inputs,
1244                    Config config,
1245                    std::unique_ptr<TicketExecutor> executor,
1246                    std::unique_ptr<Client> client,
1247                    const EmitCallback& callback,
1248                    DisposeCallback dispose,
1249                    StructuredLogEntry* sample,
1250                    int num_threads) {
1251   trace_time tracer("whole program", sample);
1252
1253   if (sample) {
1254     sample->setInt("hhbbc_thread_count", executor->numThreads());
1255   }
1256
1257   if (num_threads > 0) {
1258     parallel::num_threads = num_threads;
1259     // Leave a thread free for cleanup
1260     parallel::final_threads = (num_threads > 1) ? (num_threads - 1) : 1;
1261   }
1262
1263   Index index{
1264     make_index_input(std::move(inputs)),
1265     std::move(config),
1266     std::move(executor),
1267     std::move(client),
1268     std::move(dispose),
1269     sample
1270   };
1271
1272   analyze_constants(index);
1273   index.make_local();
1274
1275   auto stats = allocate_stats();
1276   auto const emitUnit = [&] (php::Unit& unit) {
1277     auto ue = emit_unit(index, unit);
1278     if (Cfg::Eval::AbortBuildOnVerifyError && !ue->check(false)) {
1279       fprintf(
1280         stderr,
1281         "The optimized unit for %s did not pass verification, "
1282         "bailing because Eval.AbortBuildOnVerifyError is set\n",
1283         ue->m_filepath->data()
1284       );
1285       _Exit(HPHP_EXIT_FAILURE);
1286     }
1287     callback(std::move(ue));
1288   };
1289
1290   assertx(check(index.program()));
1291
1292   // Defer preresolve type-structures and initializing public static
1293   // property types until after the constant pass, to try to get
1294   // better initial values.
1295   index.use_class_dependencies(false);
1296   index.preresolve_type_structures();
1297   index.use_class_dependencies(true);
1298   analyze_iteratively(index);
1299   auto cleanup_for_final = std::thread([&] { index.cleanup_for_final(); });
1300   parallel::num_threads = parallel::final_threads;
1301   final_pass(index, stats, emitUnit);
1302   cleanup_for_final.join();
1303
1304   print_stats(stats);
1305
1306   if (sample) {
1307     sample->setInt("hhbbc_num_units", index.program().units.size());
1308     sample->setInt("hhbbc_num_classes", index.program().classes.size());
1309     sample->setInt("hhbbc_num_funcs", index.program().funcs.size());
1310   }
1311
1312   index.cleanup_post_emit();
1313   summarize_memory(sample);
1314 }
1315
1316 //////////////////////////////////////////////////////////////////////
1317
1318 }}