src/v8/src/compiler/pipeline.cc

   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