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
33namespace v8 {
34namespace internal {
35namespace compiler {
36
37class 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
81static inline bool VerifyGraphs() {
82#ifdef DEBUG
83  return true;
84#else
85  return FLAG_turbo_verify;
86#endif
87}
88
89
90void 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
120class 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
146static void TraceSchedule(Schedule* schedule) {
147  if (!FLAG_trace_turbo) return;
148  OFStream os(stdout);
149  os << "-- Schedule --------------------------------------\n" << *schedule;
150}
151
152
153Handle<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
331Schedule* 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
340Handle<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
363Handle<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
411void Pipeline::SetUp() {
412  InstructionOperand::SetUpCaches();
413}
414
415
416void Pipeline::TearDown() {
417  InstructionOperand::TearDownCaches();
418}
419
420}  // namespace compiler
421}  // namespace internal
422}  // namespace v8
423