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/Memory.h>
  25 #include <folly/ScopeGuard.h>
  26
  27 #include "hphp/runtime/vm/unit-emitter.h"
  28 #include "hphp/util/struct-log.h"
  29
  30 #include "hphp/hhbbc/analyze.h"
  31 #include "hphp/hhbbc/class-util.h"
  32 #include "hphp/hhbbc/debug.h"
  33 #include "hphp/hhbbc/emit.h"
  34 #include "hphp/hhbbc/func-util.h"
  35 #include "hphp/hhbbc/index.h"
  36 #include "hphp/hhbbc/optimize.h"
  37 #include "hphp/hhbbc/options.h"
  38 #include "hphp/hhbbc/parallel.h"
  39 #include "hphp/hhbbc/parse.h"
  40 #include "hphp/hhbbc/representation.h"
  41 #include "hphp/hhbbc/stats.h"
  42 #include "hphp/hhbbc/type-system.h"
  43 #include "hphp/hhbbc/wide-func.h"
  44
  45 namespace HPHP::HHBBC {
  46
  47 TRACE_SET_MOD(hhbbc);
  48
  49 //////////////////////////////////////////////////////////////////////
  50
  51 namespace {
  52
  53 //////////////////////////////////////////////////////////////////////
  54
  55 const StaticString s_invoke("__invoke");
  56
  57 //////////////////////////////////////////////////////////////////////
  58
  59 enum class AnalyzeMode { NormalPass, ConstPass };
  60 enum class WorkType { Class, Func };
  61
  62 struct WorkItem {
  63   explicit WorkItem(WorkType type, Context ctx)
  64     : type(type)
  65     , ctx(ctx)
  66   {}
  67
  68   bool operator<(const WorkItem& o) const {
  69     return type < o.type ? true :
  70            o.type < type ? false :
  71            ctx < o.ctx;
  72   }
  73
  74   bool operator==(const WorkItem& o) const {
  75     return type == o.type && ctx == o.ctx;
  76   }
  77
  78   WorkType type;
  79   Context ctx;
  80 };
  81
  82 struct WorkResult {
  83   explicit WorkResult(ClassAnalysis cls)
  84     : type(WorkType::Class)
  85     , cls(std::move(cls))
  86   {}
  87
  88   explicit WorkResult(FuncAnalysisResult func)
  89     : type(WorkType::Func)
  90     , func(std::move(func))
  91   {}
  92
  93   WorkResult(WorkResult&& wr) noexcept
  94     : type(wr.type)
  95   {
  96     switch (type) {
  97     case WorkType::Class:
  98       new (&cls) ClassAnalysis(std::move(wr.cls));
  99       break;
 100     case WorkType::Func:
 101       new (&func) FuncAnalysisResult(std::move(wr.func));
 102       break;
 103     }
 104   }
 105
 106   WorkResult& operator=(WorkResult&& o) noexcept {
 107     this->~WorkResult();
 108     switch (o.type) {
 109     case WorkType::Class: new (this) WorkResult(std::move(o.cls)); break;
 110     case WorkType::Func:  new (this) WorkResult(std::move(o.func)); break;
 111     }
 112     return *this;
 113   }
 114
 115   ~WorkResult() {
 116     switch (type) {
 117     case WorkType::Class:
 118       cls.~ClassAnalysis();
 119       break;
 120     case WorkType::Func:
 121       func.~FuncAnalysisResult();
 122       break;
 123     }
 124   }
 125
 126   WorkType type;
 127   union {
 128     ClassAnalysis cls;
 129     FuncAnalysisResult func;
 130   };
 131 };
 132
 133 //////////////////////////////////////////////////////////////////////
 134
 135 template<typename F>
 136 void all_unit_contexts(const php::Unit* u, F&& fun) {
 137   for (auto& c : u->classes) {
 138     for (auto& m : c->methods) {
 139       fun(Context { u, m.get(), c.get()});
 140     }
 141   }
 142   for (auto& f : u->funcs) {
 143     fun(Context { u, f.get() });
 144   }
 145 }
 146
 147 std::vector<Context> const_pass_contexts(const php::Program& program) {
 148   std::vector<Context> ret;
 149   ret.reserve(program.constInits.size());
 150   for (auto func : program.constInits) {
 151     assertx(func);
 152     ret.push_back(Context { func->unit, func, func->cls });
 153   }
 154   return ret;
 155 }
 156
 157 // Return all the WorkItems we'll need to start analyzing this
 158 // program.
 159 std::vector<WorkItem> initial_work(const php::Program& program,
 160                                    AnalyzeMode mode) {
 161   std::vector<WorkItem> ret;
 162
 163   if (mode == AnalyzeMode::ConstPass) {
 164     auto const ctxs = const_pass_contexts(program);
 165     std::transform(begin(ctxs), end(ctxs), std::back_inserter(ret),
 166       [&] (Context ctx) { return WorkItem { WorkType::Func, ctx }; }
 167     );
 168     return ret;
 169   }
 170
 171   for (auto& u : program.units) {
 172     /*
 173      * If we're not doing private property inference, schedule only
 174      * function-at-a-time work items.
 175      */
 176     if (!options.HardPrivatePropInference) {
 177       all_unit_contexts(u.get(), [&] (Context&& c) {
 178           ret.emplace_back(WorkType::Func, std::move(c));
 179         }
 180       );
 181       continue;
 182     }
 183
 184     for (auto& c : u->classes) {
 185       if (c->closureContextCls) {
 186         // For class-at-a-time analysis, closures that are associated
 187         // with a class context are analyzed as part of that context.
 188         continue;
 189       }
 190       if (is_used_trait(*c)) {
 191         for (auto& f : c->methods) {
 192           ret.emplace_back(WorkType::Func,
 193                            Context { u.get(), f.get(), f->cls });
 194         }
 195       } else {
 196         ret.emplace_back(WorkType::Class,
 197                          Context { u.get(), nullptr, c.get() });
 198       }
 199     }
 200     for (auto& f : u->funcs) {
 201       ret.emplace_back(WorkType::Func, Context { u.get(), f.get() });
 202     }
 203   }
 204   return ret;
 205 }
 206
 207 std::vector<Context> opt_prop_type_hints_contexts(const php::Program& program) {
 208   std::vector<Context> ret;
 209   for (auto& u : program.units) {
 210     for (auto& c : u->classes) {
 211       ret.emplace_back(Context { u.get(), nullptr, c.get() });
 212     }
 213   }
 214   return ret;
 215 }
 216
 217 WorkItem work_item_for(const DependencyContext& d, AnalyzeMode mode) {
 218   switch (d.tag()) {
 219     case DependencyContextType::Class: {
 220       auto const cls = (const php::Class*)d.ptr();
 221       assertx(mode != AnalyzeMode::ConstPass &&
 222               options.HardPrivatePropInference &&
 223               !is_used_trait(*cls));
 224       return WorkItem { WorkType::Class, Context { cls->unit, nullptr, cls } };
 225     }
 226     case DependencyContextType::Func: {
 227       auto const func = (const php::Func*)d.ptr();
 228       auto const cls = !func->cls ? nullptr :
 229         func->cls->closureContextCls ?
 230         func->cls->closureContextCls : func->cls;
 231       assertx(!cls ||
 232               mode == AnalyzeMode::ConstPass ||
 233               !options.HardPrivatePropInference ||
 234               is_used_trait(*cls));
 235       return WorkItem { WorkType::Func, Context { func->unit, func, cls } };
 236     }
 237     case DependencyContextType::Prop:
 238     case DependencyContextType::FuncFamily:
 239       // We only record dependencies on these. We don't schedule any
 240       // work on their behalf.
 241       break;
 242   }
 243   always_assert(false);
 244 }
 245
 246 /*
 247  * Algorithm:
 248  *
 249  * Start by running an analyze pass on every class or free function.
 250  * During analysis, information about functions or classes will be
 251  * requested from the Index, which initially won't really know much,
 252  * but will record a dependency.  This part is done in parallel: no
 253  * passes are mutating anything, just reading from the Index.
 254  *
 255  * After a pass, we do a single-threaded "update" step to prepare
 256  * for the next pass: for each function or class that was analyzed,
 257  * note the facts we learned that may aid analyzing other functions
 258  * in the program, and register them in the index.
 259  *
 260  * If any of these facts are more useful than they used to be, add
 261  * all the Contexts that had a dependency on the new information to
 262  * the work list again, in case they can do better based on the new
 263  * fact.  (This only applies to function analysis information right
 264  * now.)
 265  *
 266  * Repeat until the work list is empty.
 267  *
 268  */
 269 void analyze_iteratively(Index& index, php::Program& program,
 270                          AnalyzeMode mode) {
 271   trace_time tracer(mode == AnalyzeMode::ConstPass ?
 272                     "analyze constants" : "analyze iteratively");
 273
 274   // Counters, just for debug printing.
 275   std::atomic<uint32_t> total_funcs{0};
 276   std::atomic<uint32_t> total_classes{0};
 277   auto round = uint32_t{0};
 278
 279   SCOPE_EXIT {
 280     if (Trace::moduleEnabledRelease(Trace::hhbbc_time, 1)) {
 281       Trace::traceRelease("total class visits %u\n", total_classes.load());
 282       Trace::traceRelease("total function visits %u\n", total_funcs.load());
 283     }
 284   };
 285
 286   std::vector<DependencyContextSet> deps_vec{parallel::num_threads};
 287
 288   auto work = initial_work(program, mode);
 289   while (!work.empty()) {
 290     auto results = [&] {
 291       trace_time trace(
 292         "analyzing",
 293         folly::format("round {} -- {} work items", round, work.size()).str()
 294       );
 295       return parallel::map(
 296         work,
 297         // We have a Optional just to keep the result type
 298         // DefaultConstructible.
 299         [&] (const WorkItem& wi) -> Optional<WorkResult> {
 300           switch (wi.type) {
 301           case WorkType::Func: {
 302             ++total_funcs;
 303             auto const wf = php::WideFunc::cns(wi.ctx.func);
 304             auto const ctx = AnalysisContext { wi.ctx.unit, wf, wi.ctx.cls };
 305             return WorkResult { analyze_func(index, ctx, CollectionOpts{}) };
 306           }
 307           case WorkType::Class:
 308             ++total_classes;
 309             return WorkResult { analyze_class(index, wi.ctx) };
 310           }
 311           not_reached();
 312         }
 313       );
 314     }();
 315
 316     ++round;
 317     trace_time update_time("updating");
 318
 319     auto update_func = [&] (FuncAnalysisResult& fa,
 320                             DependencyContextSet& deps) {
 321       SCOPE_ASSERT_DETAIL("update_func") {
 322         return "Updating Func: " + show(fa.ctx);
 323       };
 324       // This const_cast is safe since no two threads update the same Func.
 325       auto func = php::WideFunc::mut(const_cast<php::Func*>(fa.ctx.func));
 326       index.refine_return_info(fa, deps);
 327       index.refine_constants(fa, deps);
 328       update_bytecode(func, std::move(fa.blockUpdates));
 329
 330       if (options.AnalyzePublicStatics && mode == AnalyzeMode::NormalPass) {
 331         index.record_public_static_mutations(
 332           *func,
 333           std::move(fa.publicSPropMutations)
 334         );
 335       }
 336
 337       if (fa.resolvedConstants.size()) {
 338         index.refine_class_constants(fa.ctx, fa.resolvedConstants, deps);
 339       }
 340       for (auto& kv : fa.closureUseTypes) {
 341         assertx(is_closure(*kv.first));
 342         if (index.refine_closure_use_vars(kv.first, kv.second)) {
 343           auto const func = find_method(kv.first, s_invoke.get());
 344           always_assert_flog(
 345             func != nullptr,
 346             "Failed to find __invoke on {} during index update\n",
 347             kv.first->name->data()
 348           );
 349           auto const ctx = Context { func->unit, func, kv.first };
 350           deps.insert(index.dependency_context(ctx));
 351         }
 352       }
 353     };
 354
 355     auto update_class = [&] (ClassAnalysis& ca,
 356                              DependencyContextSet& deps) {
 357       {
 358         SCOPE_ASSERT_DETAIL("update_class") {
 359           return "Updating Class: " + show(ca.ctx);
 360         };
 361         index.refine_private_props(ca.ctx.cls,
 362                                    ca.privateProperties);
 363         index.refine_private_statics(ca.ctx.cls,
 364                                      ca.privateStatics);
 365         index.refine_bad_initial_prop_values(ca.ctx.cls,
 366                                              ca.badPropInitialValues,
 367                                              deps);
 368       }
 369       for (auto& fa : ca.methods)  update_func(fa, deps);
 370       for (auto& fa : ca.closures) update_func(fa, deps);
 371     };
 372
 373     parallel::for_each(
 374       results,
 375       [&] (auto& result, size_t worker) {
 376         assertx(worker < deps_vec.size());
 377         switch (result->type) {
 378           case WorkType::Func:
 379             update_func(result->func, deps_vec[worker]);
 380             break;
 381           case WorkType::Class:
 382             update_class(result->cls, deps_vec[worker]);
 383             break;
 384         }
 385         result.reset();
 386       }
 387     );
 388
 389     {
 390       trace_time _("merging deps");
 391       for (auto& deps : deps_vec) {
 392         if (&deps == &deps_vec[0]) continue;
 393         for (auto& d : deps) deps_vec[0].insert(d);
 394         deps.clear();
 395       }
 396     }
 397
 398     auto& deps = deps_vec[0];
 399
 400     if (options.AnalyzePublicStatics && mode == AnalyzeMode::NormalPass) {
 401       index.refine_public_statics(deps);
 402     }
 403
 404     work.clear();
 405     work.reserve(deps.size());
 406     for (auto& d : deps) work.push_back(work_item_for(d, mode));
 407     deps.clear();
 408   }
 409 }
 410
 411 void prop_type_hint_pass(Index& index, php::Program& program) {
 412   trace_time tracer("optimize prop type-hints");
 413
 414   auto const contexts = opt_prop_type_hints_contexts(program);
 415   parallel::for_each(
 416     contexts,
 417     [&] (Context ctx) { optimize_class_prop_type_hints(index, ctx); }
 418   );
 419
 420   parallel::for_each(
 421     contexts,
 422     [&] (Context ctx) {
 423       index.mark_no_bad_redeclare_props(const_cast<php::Class&>(*ctx.cls));
 424     }
 425   );
 426 }
 427
 428 /*
 429  * Finally, use the results of all these iterations to perform
 430  * optimization.  This reanalyzes every function using our
 431  * now-very-updated Index, and then runs optimize_func with the
 432  * results.
 433  *
 434  * We do this in parallel: all the shared information is queried out
 435  * of the index, and each thread is allowed to modify the bytecode
 436  * for the function it is looking at.
 437  *
 438  * NOTE: currently they can't modify anything other than the
 439  * bytecode/Blocks, because other threads may be doing unlocked
 440  * queries to php::Func and php::Class structures.
 441  */
 442 template<typename F>
 443 void final_pass(Index& index,
 444                 php::Program& program,
 445                 const StatsHolder& stats,
 446                 F emitUnit) {
 447   trace_time final_pass("final pass");
 448   LitstrTable::fini();
 449   LitstrTable::init();
 450   LitstrTable::get().setWriting();
 451   LitarrayTable::fini();
 452   LitarrayTable::init();
 453   LitarrayTable::get().setWriting();
 454   index.freeze();
 455   auto const dump_dir = debug_dump_to();
 456   parallel::for_each(
 457     program.units,
 458     [&] (std::unique_ptr<php::Unit>& unit) {
 459       // optimize_func can remove 86*init methods from classes, so we
 460       // have to save the contexts for now.
 461       std::vector<Context> contexts;
 462       all_unit_contexts(unit.get(), [&] (Context&& ctx) {
 463           contexts.push_back(std::move(ctx));
 464         }
 465       );
 466       for (auto const& context : contexts) {
 467         // This const_cast is safe since no two threads update the same Func.
 468         auto func = php::WideFunc::mut(const_cast<php::Func*>(context.func));
 469         auto const ctx = AnalysisContext { context.unit, func, context.cls };
 470         optimize_func(index, analyze_func(index, ctx, CollectionOpts{}), func);
 471       }
 472       assertx(check(*unit));
 473       state_after("optimize", *unit);
 474       if (!dump_dir.empty()) {
 475         if (Trace::moduleEnabledRelease(Trace::hhbbc_dump, 2)) {
 476           dump_representation(dump_dir, unit.get());
 477         }
 478         dump_index(dump_dir, index, unit.get());
 479       }
 480       collect_stats(stats, index, unit.get());
 481       emitUnit(*unit);
 482     }
 483   );
 484 }
 485
 486 //////////////////////////////////////////////////////////////////////
 487
 488 }
 489
 490 //////////////////////////////////////////////////////////////////////
 491
 492 void UnitEmitterQueue::push(std::unique_ptr<UnitEmitter> ue) {
 493   assertx(!m_done.load(std::memory_order_relaxed));
 494
 495   if (m_repoBuilder) m_repoBuilder->addUnit(*ue);
 496   RepoFileBuilder::EncodedUE encoded{*ue};
 497
 498   {
 499     Lock lock(this);
 500     m_encoded.emplace_back(std::move(encoded));
 501     if (m_storeUnitEmitters) m_ues.emplace_back(std::move(ue));
 502     notify();
 503   }
 504 }
 505
 506 void UnitEmitterQueue::finish() {
 507   assertx(!m_done.load(std::memory_order_relaxed));
 508   Lock lock(this);
 509   m_done.store(true, std::memory_order_relaxed);
 510   notify();
 511 }
 512
 513 Optional<RepoFileBuilder::EncodedUE> UnitEmitterQueue::pop() {
 514   Lock lock(this);
 515   while (m_encoded.empty()) {
 516     if (m_done.load(std::memory_order_relaxed)) return std::nullopt;
 517     wait();
 518   }
 519   assertx(m_encoded.size() > 0);
 520   auto encoded = std::move(m_encoded.front());
 521   m_encoded.pop_front();
 522   return encoded;
 523 }
 524
 525 std::unique_ptr<UnitEmitter> UnitEmitterQueue::popUnitEmitter() {
 526   Lock lock(this);
 527   while (m_ues.empty()) {
 528     if (m_done.load(std::memory_order_relaxed)) return nullptr;
 529     wait();
 530   }
 531   assertx(m_ues.size() > 0);
 532   auto ue = std::move(m_ues.front());
 533   m_ues.pop_front();
 534   return ue;
 535 }
 536
 537 //////////////////////////////////////////////////////////////////////
 538
 539 namespace php {
 540
 541 void ProgramPtr::clear() { delete m_program; }
 542
 543 }
 544
 545 php::ProgramPtr make_program() {
 546   return php::ProgramPtr{ new php::Program };
 547 }
 548
 549 void add_unit_to_program(const UnitEmitter* ue, php::Program& program) {
 550   parse_unit(program, ue);
 551 }
 552
 553 void whole_program(php::ProgramPtr program,
 554                    UnitEmitterQueue& ueq,
 555                    std::unique_ptr<ArrayTypeTable::Builder>& arrTable,
 556                    int num_threads,
 557                    std::promise<void>* arrTableReady) {
 558   StructuredLogEntry sample;
 559   trace_time tracer("whole program");
 560
 561   if (options.TestCompression || RO::EvalHHBBCTestCompression) {
 562     php::testCompression(*program);
 563   }
 564
 565   if (num_threads > 0) {
 566     parallel::num_threads = num_threads;
 567     // Leave 2 threads free for writing UnitEmitters and for cleanup
 568     parallel::final_threads = (num_threads > 2) ? (num_threads - 2) : 1;
 569   }
 570
 571   state_after("parse", *program);
 572
 573   Index index(program.get());
 574   auto stats = allocate_stats();
 575   auto emitUnit = [&] (php::Unit& unit) {
 576     auto ue = emit_unit(index, unit);
 577     if (RuntimeOption::EvalAbortBuildOnVerifyError && !ue->check(false)) {
 578       fprintf(
 579         stderr,
 580         "The optimized unit for %s did not pass verification, "
 581         "bailing because Eval.AbortBuildOnVerifyError is set\n",
 582         ue->m_filepath->data()
 583       );
 584       _Exit(1);
 585     }
 586     ueq.push(std::move(ue));
 587   };
 588
 589   std::thread cleanup_pre;
 590   if (!options.NoOptimizations) {
 591     assertx(check(*program));
 592     prop_type_hint_pass(index, *program);
 593     index.rewrite_default_initial_values(*program);
 594     index.use_class_dependencies(false);
 595     analyze_iteratively(index, *program, AnalyzeMode::ConstPass);
 596     // Defer preresolve type-structures and initializing public static
 597     // property types until after the constant pass, to try to get
 598     // better initial values.
 599     index.preresolve_type_structures(*program);
 600     index.init_public_static_prop_types();
 601     index.preinit_bad_initial_prop_values();
 602     index.use_class_dependencies(options.HardPrivatePropInference);
 603     analyze_iteratively(index, *program, AnalyzeMode::NormalPass);
 604     cleanup_pre = std::thread([&] { index.cleanup_for_final(); });
 605     index.join_iface_vtable_thread();
 606     parallel::num_threads = parallel::final_threads;
 607     final_pass(index, *program, stats, emitUnit);
 608   } else {
 609     debug_dump_program(index, *program);
 610     index.join_iface_vtable_thread();
 611     parallel::for_each(
 612       program->units,
 613       [&] (const std::unique_ptr<php::Unit>& unit) {
 614         collect_stats(stats, index, unit.get());
 615         emitUnit(*unit);
 616       }
 617     );
 618   }
 619
 620   auto num_units = program->units.size();
 621
 622   auto const logging = Trace::moduleEnabledRelease(Trace::hhbbc_time, 1);
 623   // running cleanup_for_emit can take a while... start it as early as
 624   // possible, and run in its own thread.
 625   auto cleanup_post = std::thread([&, program = std::move(program)] () mutable {
 626       auto const enable =
 627         logging && !Trace::moduleEnabledRelease(Trace::hhbbc_time, 1);
 628       Trace::BumpRelease bumper(Trace::hhbbc_time, -1, enable);
 629       index.cleanup_post_emit(std::move(program));
 630     }
 631   );
 632
 633   print_stats(stats);
 634
 635   arrTable = std::move(index.array_table_builder());
 636   if (arrTableReady != nullptr) {
 637     arrTableReady->set_value();
 638   }
 639   ueq.finish();
 640   cleanup_pre.join();
 641   cleanup_post.join();
 642
 643   summarize_memory(sample);
 644   if (num_units >= RuntimeOption::EvalHHBBCMinUnitsToLog) {
 645     // num_units includes systemlib, around 200 units. Only log big builds.
 646     sample.setInt("num_units", num_units);
 647     sample.setInt(tracer.label(), tracer.elapsed_ms());
 648     sample.force_init = true;
 649     StructuredLog::log("hhvm_whole_program", sample);
 650   }
 651 }
 652
 653 //////////////////////////////////////////////////////////////////////
 654
 655 }