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