Home | History | Annotate | Download | only in compiler 
      1 // Copyright 2014 the V8 project authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 #include "src/compiler/pipeline.h"
      6 
      7 #include "src/base/platform/elapsed-timer.h"
      8 #include "src/compiler/ast-graph-builder.h"
      9 #include "src/compiler/change-lowering.h"
     10 #include "src/compiler/code-generator.h"
     11 #include "src/compiler/graph-replay.h"
     12 #include "src/compiler/graph-visualizer.h"
     13 #include "src/compiler/instruction.h"
     14 #include "src/compiler/instruction-selector.h"
     15 #include "src/compiler/js-context-specialization.h"
     16 #include "src/compiler/js-generic-lowering.h"
     17 #include "src/compiler/js-inlining.h"
     18 #include "src/compiler/js-typed-lowering.h"
     19 #include "src/compiler/machine-operator-reducer.h"
     20 #include "src/compiler/phi-reducer.h"
     21 #include "src/compiler/register-allocator.h"
     22 #include "src/compiler/schedule.h"
     23 #include "src/compiler/scheduler.h"
     24 #include "src/compiler/simplified-lowering.h"
     25 #include "src/compiler/simplified-operator-reducer.h"
     26 #include "src/compiler/typer.h"
     27 #include "src/compiler/value-numbering-reducer.h"
     28 #include "src/compiler/verifier.h"
     29 #include "src/hydrogen.h"
     30 #include "src/ostreams.h"
     31 #include "src/utils.h"
     32 
     33 namespace v8 {
     34 namespace internal {
     35 namespace compiler {
     36 
     37 class PhaseStats {
     38  public:
     39   enum PhaseKind { CREATE_GRAPH, OPTIMIZATION, CODEGEN };
     40 
     41   PhaseStats(CompilationInfo* info, PhaseKind kind, const char* name)
     42       : info_(info),
     43         kind_(kind),
     44         name_(name),
     45         size_(info->zone()->allocation_size()) {
     46     if (FLAG_turbo_stats) {
     47       timer_.Start();
     48     }
     49   }
     50 
     51   ~PhaseStats() {
     52     if (FLAG_turbo_stats) {
     53       base::TimeDelta delta = timer_.Elapsed();
     54       size_t bytes = info_->zone()->allocation_size() - size_;
     55       HStatistics* stats = info_->isolate()->GetTStatistics();
     56       stats->SaveTiming(name_, delta, static_cast<int>(bytes));
     57 
     58       switch (kind_) {
     59         case CREATE_GRAPH:
     60           stats->IncrementCreateGraph(delta);
     61           break;
     62         case OPTIMIZATION:
     63           stats->IncrementOptimizeGraph(delta);
     64           break;
     65         case CODEGEN:
     66           stats->IncrementGenerateCode(delta);
     67           break;
     68       }
     69     }
     70   }
     71 
     72  private:
     73   CompilationInfo* info_;
     74   PhaseKind kind_;
     75   const char* name_;
     76   size_t size_;
     77   base::ElapsedTimer timer_;
     78 };
     79 
     80 
     81 static inline bool VerifyGraphs() {
     82 #ifdef DEBUG
     83   return true;
     84 #else
     85   return FLAG_turbo_verify;
     86 #endif
     87 }
     88 
     89 
     90 void Pipeline::VerifyAndPrintGraph(Graph* graph, const char* phase) {
     91   if (FLAG_trace_turbo) {
     92     char buffer[256];
     93     Vector<char> filename(buffer, sizeof(buffer));
     94     if (!info_->shared_info().is_null()) {
     95       SmartArrayPointer<char> functionname =
     96           info_->shared_info()->DebugName()->ToCString();
     97       if (strlen(functionname.get()) > 0) {
     98         SNPrintF(filename, "turbo-%s-%s.dot", functionname.get(), phase);
     99       } else {
    100         SNPrintF(filename, "turbo-%p-%s.dot", static_cast<void*>(info_), phase);
    101       }
    102     } else {
    103       SNPrintF(filename, "turbo-none-%s.dot", phase);
    104     }
    105     std::replace(filename.start(), filename.start() + filename.length(), ' ',
    106                  '_');
    107     FILE* file = base::OS::FOpen(filename.start(), "w+");
    108     OFStream of(file);
    109     of << AsDOT(*graph);
    110     fclose(file);
    111 
    112     OFStream os(stdout);
    113     os << "-- " << phase << " graph printed to file " << filename.start()
    114        << "\n";
    115   }
    116   if (VerifyGraphs()) Verifier::Run(graph);
    117 }
    118 
    119 
    120 class AstGraphBuilderWithPositions : public AstGraphBuilder {
    121  public:
    122   explicit AstGraphBuilderWithPositions(CompilationInfo* info, JSGraph* jsgraph,
    123                                         SourcePositionTable* source_positions)
    124       : AstGraphBuilder(info, jsgraph), source_positions_(source_positions) {}
    125 
    126   bool CreateGraph() {
    127     SourcePositionTable::Scope pos(source_positions_,
    128                                    SourcePosition::Unknown());
    129     return AstGraphBuilder::CreateGraph();
    130   }
    131 
    132 #define DEF_VISIT(type)                                               \
    133   virtual void Visit##type(type* node) OVERRIDE {                  \
    134     SourcePositionTable::Scope pos(source_positions_,                 \
    135                                    SourcePosition(node->position())); \
    136     AstGraphBuilder::Visit##type(node);                               \
    137   }
    138   AST_NODE_LIST(DEF_VISIT)
    139 #undef DEF_VISIT
    140 
    141  private:
    142   SourcePositionTable* source_positions_;
    143 };
    144 
    145 
    146 static void TraceSchedule(Schedule* schedule) {
    147   if (!FLAG_trace_turbo) return;
    148   OFStream os(stdout);
    149   os << "-- Schedule --------------------------------------\n" << *schedule;
    150 }
    151 
    152 
    153 Handle<Code> Pipeline::GenerateCode() {
    154   if (info()->function()->dont_optimize_reason() == kTryCatchStatement ||
    155       info()->function()->dont_optimize_reason() == kTryFinallyStatement ||
    156       // TODO(turbofan): Make ES6 for-of work and remove this bailout.
    157       info()->function()->dont_optimize_reason() == kForOfStatement ||
    158       // TODO(turbofan): Make super work and remove this bailout.
    159       info()->function()->dont_optimize_reason() == kSuperReference ||
    160       // TODO(turbofan): Make OSR work and remove this bailout.
    161       info()->is_osr()) {
    162     return Handle<Code>::null();
    163   }
    164 
    165   if (FLAG_turbo_stats) isolate()->GetTStatistics()->Initialize(info_);
    166 
    167   if (FLAG_trace_turbo) {
    168     OFStream os(stdout);
    169     os << "---------------------------------------------------\n"
    170        << "Begin compiling method "
    171        << info()->function()->debug_name()->ToCString().get()
    172        << " using Turbofan" << endl;
    173   }
    174 
    175   // Build the graph.
    176   Graph graph(zone());
    177   SourcePositionTable source_positions(&graph);
    178   source_positions.AddDecorator();
    179   // TODO(turbofan): there is no need to type anything during initial graph
    180   // construction.  This is currently only needed for the node cache, which the
    181   // typer could sweep over later.
    182   Typer typer(zone());
    183   MachineOperatorBuilder machine;
    184   CommonOperatorBuilder common(zone());
    185   JSOperatorBuilder javascript(zone());
    186   JSGraph jsgraph(&graph, &common, &javascript, &typer, &machine);
    187   Node* context_node;
    188   {
    189     PhaseStats graph_builder_stats(info(), PhaseStats::CREATE_GRAPH,
    190                                    "graph builder");
    191     AstGraphBuilderWithPositions graph_builder(info(), &jsgraph,
    192                                                &source_positions);
    193     graph_builder.CreateGraph();
    194     context_node = graph_builder.GetFunctionContext();
    195   }
    196   {
    197     PhaseStats phi_reducer_stats(info(), PhaseStats::CREATE_GRAPH,
    198                                  "phi reduction");
    199     PhiReducer phi_reducer;
    200     GraphReducer graph_reducer(&graph);
    201     graph_reducer.AddReducer(&phi_reducer);
    202     graph_reducer.ReduceGraph();
    203     // TODO(mstarzinger): Running reducer once ought to be enough for everyone.
    204     graph_reducer.ReduceGraph();
    205     graph_reducer.ReduceGraph();
    206   }
    207 
    208   VerifyAndPrintGraph(&graph, "Initial untyped");
    209 
    210   if (info()->is_context_specializing()) {
    211     SourcePositionTable::Scope pos(&source_positions,
    212                                    SourcePosition::Unknown());
    213     // Specialize the code to the context as aggressively as possible.
    214     JSContextSpecializer spec(info(), &jsgraph, context_node);
    215     spec.SpecializeToContext();
    216     VerifyAndPrintGraph(&graph, "Context specialized");
    217   }
    218 
    219   if (info()->is_inlining_enabled()) {
    220     SourcePositionTable::Scope pos(&source_positions,
    221                                    SourcePosition::Unknown());
    222     JSInliner inliner(info(), &jsgraph);
    223     inliner.Inline();
    224     VerifyAndPrintGraph(&graph, "Inlined");
    225   }
    226 
    227   // Print a replay of the initial graph.
    228   if (FLAG_print_turbo_replay) {
    229     GraphReplayPrinter::PrintReplay(&graph);
    230   }
    231 
    232   if (info()->is_typing_enabled()) {
    233     {
    234       // Type the graph.
    235       PhaseStats typer_stats(info(), PhaseStats::CREATE_GRAPH, "typer");
    236       typer.Run(&graph, info()->context());
    237       VerifyAndPrintGraph(&graph, "Typed");
    238     }
    239     // All new nodes must be typed.
    240     typer.DecorateGraph(&graph);
    241     {
    242       // Lower JSOperators where we can determine types.
    243       PhaseStats lowering_stats(info(), PhaseStats::CREATE_GRAPH,
    244                                 "typed lowering");
    245       SourcePositionTable::Scope pos(&source_positions,
    246                                      SourcePosition::Unknown());
    247       JSTypedLowering lowering(&jsgraph);
    248       GraphReducer graph_reducer(&graph);
    249       graph_reducer.AddReducer(&lowering);
    250       graph_reducer.ReduceGraph();
    251 
    252       VerifyAndPrintGraph(&graph, "Lowered typed");
    253     }
    254     {
    255       // Lower simplified operators and insert changes.
    256       PhaseStats lowering_stats(info(), PhaseStats::CREATE_GRAPH,
    257                                 "simplified lowering");
    258       SourcePositionTable::Scope pos(&source_positions,
    259                                      SourcePosition::Unknown());
    260       SimplifiedLowering lowering(&jsgraph);
    261       lowering.LowerAllNodes();
    262 
    263       VerifyAndPrintGraph(&graph, "Lowered simplified");
    264     }
    265     {
    266       // Lower changes that have been inserted before.
    267       PhaseStats lowering_stats(info(), PhaseStats::OPTIMIZATION,
    268                                 "change lowering");
    269       SourcePositionTable::Scope pos(&source_positions,
    270                                      SourcePosition::Unknown());
    271       Linkage linkage(info());
    272       // TODO(turbofan): Value numbering disabled for now.
    273       // ValueNumberingReducer vn_reducer(zone());
    274       SimplifiedOperatorReducer simple_reducer(&jsgraph);
    275       ChangeLowering lowering(&jsgraph, &linkage);
    276       MachineOperatorReducer mach_reducer(&jsgraph);
    277       GraphReducer graph_reducer(&graph);
    278       // TODO(titzer): Figure out if we should run all reducers at once here.
    279       // graph_reducer.AddReducer(&vn_reducer);
    280       graph_reducer.AddReducer(&simple_reducer);
    281       graph_reducer.AddReducer(&lowering);
    282       graph_reducer.AddReducer(&mach_reducer);
    283       graph_reducer.ReduceGraph();
    284 
    285       VerifyAndPrintGraph(&graph, "Lowered changes");
    286     }
    287   }
    288 
    289   Handle<Code> code = Handle<Code>::null();
    290   if (SupportedTarget()) {
    291     {
    292       // Lower any remaining generic JSOperators.
    293       PhaseStats lowering_stats(info(), PhaseStats::CREATE_GRAPH,
    294                                 "generic lowering");
    295       SourcePositionTable::Scope pos(&source_positions,
    296                                      SourcePosition::Unknown());
    297       JSGenericLowering lowering(info(), &jsgraph);
    298       GraphReducer graph_reducer(&graph);
    299       graph_reducer.AddReducer(&lowering);
    300       graph_reducer.ReduceGraph();
    301 
    302       VerifyAndPrintGraph(&graph, "Lowered generic");
    303     }
    304 
    305     {
    306       // Compute a schedule.
    307       Schedule* schedule = ComputeSchedule(&graph);
    308       // Generate optimized code.
    309       PhaseStats codegen_stats(info(), PhaseStats::CODEGEN, "codegen");
    310       Linkage linkage(info());
    311       code = GenerateCode(&linkage, &graph, schedule, &source_positions);
    312       info()->SetCode(code);
    313     }
    314 
    315     // Print optimized code.
    316     v8::internal::CodeGenerator::PrintCode(code, info());
    317   }
    318 
    319   if (FLAG_trace_turbo) {
    320     OFStream os(stdout);
    321     os << "--------------------------------------------------\n"
    322        << "Finished compiling method "
    323        << info()->function()->debug_name()->ToCString().get()
    324        << " using Turbofan" << endl;
    325   }
    326 
    327   return code;
    328 }
    329 
    330 
    331 Schedule* Pipeline::ComputeSchedule(Graph* graph) {
    332   PhaseStats schedule_stats(info(), PhaseStats::CODEGEN, "scheduling");
    333   Schedule* schedule = Scheduler::ComputeSchedule(graph);
    334   TraceSchedule(schedule);
    335   if (VerifyGraphs()) ScheduleVerifier::Run(schedule);
    336   return schedule;
    337 }
    338 
    339 
    340 Handle<Code> Pipeline::GenerateCodeForMachineGraph(Linkage* linkage,
    341                                                    Graph* graph,
    342                                                    Schedule* schedule) {
    343   CHECK(SupportedBackend());
    344   if (schedule == NULL) {
    345     VerifyAndPrintGraph(graph, "Machine");
    346     schedule = ComputeSchedule(graph);
    347   }
    348   TraceSchedule(schedule);
    349 
    350   SourcePositionTable source_positions(graph);
    351   Handle<Code> code = GenerateCode(linkage, graph, schedule, &source_positions);
    352 #if ENABLE_DISASSEMBLER
    353   if (!code.is_null() && FLAG_print_opt_code) {
    354     CodeTracer::Scope tracing_scope(isolate()->GetCodeTracer());
    355     OFStream os(tracing_scope.file());
    356     code->Disassemble("test code", os);
    357   }
    358 #endif
    359   return code;
    360 }
    361 
    362 
    363 Handle<Code> Pipeline::GenerateCode(Linkage* linkage, Graph* graph,
    364                                     Schedule* schedule,
    365                                     SourcePositionTable* source_positions) {
    366   DCHECK_NOT_NULL(graph);
    367   DCHECK_NOT_NULL(linkage);
    368   DCHECK_NOT_NULL(schedule);
    369   CHECK(SupportedBackend());
    370 
    371   InstructionSequence sequence(linkage, graph, schedule);
    372 
    373   // Select and schedule instructions covering the scheduled graph.
    374   {
    375     InstructionSelector selector(&sequence, source_positions);
    376     selector.SelectInstructions();
    377   }
    378 
    379   if (FLAG_trace_turbo) {
    380     OFStream os(stdout);
    381     os << "----- Instruction sequence before register allocation -----\n"
    382        << sequence;
    383   }
    384 
    385   // Allocate registers.
    386   {
    387     int node_count = graph->NodeCount();
    388     if (node_count > UnallocatedOperand::kMaxVirtualRegisters) {
    389       linkage->info()->AbortOptimization(kNotEnoughVirtualRegistersForValues);
    390       return Handle<Code>::null();
    391     }
    392     RegisterAllocator allocator(&sequence);
    393     if (!allocator.Allocate()) {
    394       linkage->info()->AbortOptimization(kNotEnoughVirtualRegistersRegalloc);
    395       return Handle<Code>::null();
    396     }
    397   }
    398 
    399   if (FLAG_trace_turbo) {
    400     OFStream os(stdout);
    401     os << "----- Instruction sequence after register allocation -----\n"
    402        << sequence;
    403   }
    404 
    405   // Generate native sequence.
    406   CodeGenerator generator(&sequence);
    407   return generator.GenerateCode();
    408 }
    409 
    410 
    411 void Pipeline::SetUp() {
    412   InstructionOperand::SetUpCaches();
    413 }
    414 
    415 
    416 void Pipeline::TearDown() {
    417   InstructionOperand::TearDownCaches();
    418 }
    419 
    420 }  // namespace compiler
    421 }  // namespace internal
    422 }  // namespace v8
    423