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
PhaseStats(CompilationInfo * info,PhaseKind kind,const char * name)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
~PhaseStats()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
VerifyGraphs()81 static inline bool VerifyGraphs() {
82 #ifdef DEBUG
83 return true;
84 #else
85 return FLAG_turbo_verify;
86 #endif
87 }
88
89
VerifyAndPrintGraph(Graph * graph,const char * phase)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:
AstGraphBuilderWithPositions(CompilationInfo * info,JSGraph * jsgraph,SourcePositionTable * source_positions)122 explicit AstGraphBuilderWithPositions(CompilationInfo* info, JSGraph* jsgraph,
123 SourcePositionTable* source_positions)
124 : AstGraphBuilder(info, jsgraph), source_positions_(source_positions) {}
125
CreateGraph()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
TraceSchedule(Schedule * schedule)146 static void TraceSchedule(Schedule* schedule) {
147 if (!FLAG_trace_turbo) return;
148 OFStream os(stdout);
149 os << "-- Schedule --------------------------------------\n" << *schedule;
150 }
151
152
GenerateCode()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
ComputeSchedule(Graph * graph)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
GenerateCodeForMachineGraph(Linkage * linkage,Graph * graph,Schedule * schedule)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
GenerateCode(Linkage * linkage,Graph * graph,Schedule * schedule,SourcePositionTable * source_positions)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
SetUp()411 void Pipeline::SetUp() {
412 InstructionOperand::SetUpCaches();
413 }
414
415
TearDown()416 void Pipeline::TearDown() {
417 InstructionOperand::TearDownCaches();
418 }
419
420 } // namespace compiler
421 } // namespace internal
422 } // namespace v8
423