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