| OLD | NEW |
| 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file |
| 2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
| 3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
| 4 | 4 |
| 5 #include "vm/compiler.h" | 5 #include "vm/compiler.h" |
| 6 | 6 |
| 7 #include "vm/assembler.h" | 7 #include "vm/assembler.h" |
| 8 | 8 |
| 9 #include "vm/ast_printer.h" | 9 #include "vm/ast_printer.h" |
| 10 #include "vm/block_scheduler.h" | 10 #include "vm/block_scheduler.h" |
| (...skipping 301 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 312 if (reorder_blocks) { | 312 if (reorder_blocks) { |
| 313 block_scheduler.AssignEdgeWeights(); | 313 block_scheduler.AssignEdgeWeights(); |
| 314 } | 314 } |
| 315 | 315 |
| 316 if (optimized) { | 316 if (optimized) { |
| 317 TimerScope timer(FLAG_compiler_stats, | 317 TimerScope timer(FLAG_compiler_stats, |
| 318 &CompilerStats::ssa_timer, | 318 &CompilerStats::ssa_timer, |
| 319 isolate); | 319 isolate); |
| 320 // Transform to SSA (virtual register 0 and no inlining arguments). | 320 // Transform to SSA (virtual register 0 and no inlining arguments). |
| 321 flow_graph->ComputeSSA(0, NULL); | 321 flow_graph->ComputeSSA(0, NULL); |
| 322 ASSERT(flow_graph->VerifyUseLists()); | 322 DEBUG_ASSERT(flow_graph->VerifyUseLists()); |
| 323 if (FLAG_print_flow_graph || FLAG_print_flow_graph_optimized) { | 323 if (FLAG_print_flow_graph || FLAG_print_flow_graph_optimized) { |
| 324 FlowGraphPrinter::PrintGraph("After SSA", flow_graph); | 324 FlowGraphPrinter::PrintGraph("After SSA", flow_graph); |
| 325 } | 325 } |
| 326 } | 326 } |
| 327 | 327 |
| 328 // Collect all instance fields that are loaded in the graph and | 328 // Collect all instance fields that are loaded in the graph and |
| 329 // have non-generic type feedback attached to them that can | 329 // have non-generic type feedback attached to them that can |
| 330 // potentially affect optimizations. | 330 // potentially affect optimizations. |
| 331 if (optimized) { | 331 if (optimized) { |
| 332 TimerScope timer(FLAG_compiler_stats, | 332 TimerScope timer(FLAG_compiler_stats, |
| 333 &CompilerStats::graphoptimizer_timer, | 333 &CompilerStats::graphoptimizer_timer, |
| 334 isolate); | 334 isolate); |
| 335 | 335 |
| 336 FlowGraphOptimizer optimizer(flow_graph); | 336 FlowGraphOptimizer optimizer(flow_graph); |
| 337 optimizer.ApplyICData(); | 337 optimizer.ApplyICData(); |
| 338 ASSERT(flow_graph->VerifyUseLists()); | 338 DEBUG_ASSERT(flow_graph->VerifyUseLists()); |
| 339 | 339 |
| 340 // Optimize (a << b) & c patterns, merge operations. | 340 // Optimize (a << b) & c patterns, merge operations. |
| 341 // Run early in order to have more opportunity to optimize left shifts. | 341 // Run early in order to have more opportunity to optimize left shifts. |
| 342 optimizer.TryOptimizePatterns(); | 342 optimizer.TryOptimizePatterns(); |
| 343 ASSERT(flow_graph->VerifyUseLists()); | 343 DEBUG_ASSERT(flow_graph->VerifyUseLists()); |
| 344 | 344 |
| 345 // Inlining (mutates the flow graph) | 345 // Inlining (mutates the flow graph) |
| 346 if (FLAG_use_inlining) { | 346 if (FLAG_use_inlining) { |
| 347 TimerScope timer(FLAG_compiler_stats, | 347 TimerScope timer(FLAG_compiler_stats, |
| 348 &CompilerStats::graphinliner_timer); | 348 &CompilerStats::graphinliner_timer); |
| 349 // Propagate types to create more inlining opportunities. | 349 // Propagate types to create more inlining opportunities. |
| 350 FlowGraphTypePropagator::Propagate(flow_graph); | 350 FlowGraphTypePropagator::Propagate(flow_graph); |
| 351 ASSERT(flow_graph->VerifyUseLists()); | 351 DEBUG_ASSERT(flow_graph->VerifyUseLists()); |
| 352 | 352 |
| 353 // Use propagated class-ids to create more inlining opportunities. | 353 // Use propagated class-ids to create more inlining opportunities. |
| 354 optimizer.ApplyClassIds(); | 354 optimizer.ApplyClassIds(); |
| 355 ASSERT(flow_graph->VerifyUseLists()); | 355 DEBUG_ASSERT(flow_graph->VerifyUseLists()); |
| 356 | 356 |
| 357 FlowGraphInliner inliner(flow_graph); | 357 FlowGraphInliner inliner(flow_graph); |
| 358 inliner.Inline(); | 358 inliner.Inline(); |
| 359 // Use lists are maintained and validated by the inliner. | 359 // Use lists are maintained and validated by the inliner. |
| 360 ASSERT(flow_graph->VerifyUseLists()); | 360 DEBUG_ASSERT(flow_graph->VerifyUseLists()); |
| 361 } | 361 } |
| 362 | 362 |
| 363 // Propagate types and eliminate more type tests. | 363 // Propagate types and eliminate more type tests. |
| 364 FlowGraphTypePropagator::Propagate(flow_graph); | 364 FlowGraphTypePropagator::Propagate(flow_graph); |
| 365 ASSERT(flow_graph->VerifyUseLists()); | 365 DEBUG_ASSERT(flow_graph->VerifyUseLists()); |
| 366 | 366 |
| 367 // Use propagated class-ids to optimize further. | 367 // Use propagated class-ids to optimize further. |
| 368 optimizer.ApplyClassIds(); | 368 optimizer.ApplyClassIds(); |
| 369 ASSERT(flow_graph->VerifyUseLists()); | 369 DEBUG_ASSERT(flow_graph->VerifyUseLists()); |
| 370 | 370 |
| 371 // Propagate types for potentially newly added instructions by | 371 // Propagate types for potentially newly added instructions by |
| 372 // ApplyClassIds(). Must occur before canonicalization. | 372 // ApplyClassIds(). Must occur before canonicalization. |
| 373 FlowGraphTypePropagator::Propagate(flow_graph); | 373 FlowGraphTypePropagator::Propagate(flow_graph); |
| 374 ASSERT(flow_graph->VerifyUseLists()); | 374 DEBUG_ASSERT(flow_graph->VerifyUseLists()); |
| 375 | 375 |
| 376 // Do optimizations that depend on the propagated type information. | 376 // Do optimizations that depend on the propagated type information. |
| 377 if (optimizer.Canonicalize()) { | 377 if (optimizer.Canonicalize()) { |
| 378 // Invoke Canonicalize twice in order to fully canonicalize patterns | 378 // Invoke Canonicalize twice in order to fully canonicalize patterns |
| 379 // like "if (a & const == 0) { }". | 379 // like "if (a & const == 0) { }". |
| 380 optimizer.Canonicalize(); | 380 optimizer.Canonicalize(); |
| 381 } | 381 } |
| 382 ASSERT(flow_graph->VerifyUseLists()); | 382 DEBUG_ASSERT(flow_graph->VerifyUseLists()); |
| 383 | 383 |
| 384 BranchSimplifier::Simplify(flow_graph); | 384 BranchSimplifier::Simplify(flow_graph); |
| 385 ASSERT(flow_graph->VerifyUseLists()); | 385 DEBUG_ASSERT(flow_graph->VerifyUseLists()); |
| 386 | 386 |
| 387 IfConverter::Simplify(flow_graph); | 387 IfConverter::Simplify(flow_graph); |
| 388 ASSERT(flow_graph->VerifyUseLists()); | 388 DEBUG_ASSERT(flow_graph->VerifyUseLists()); |
| 389 | 389 |
| 390 if (FLAG_constant_propagation) { | 390 if (FLAG_constant_propagation) { |
| 391 ConstantPropagator::Optimize(flow_graph); | 391 ConstantPropagator::Optimize(flow_graph); |
| 392 ASSERT(flow_graph->VerifyUseLists()); | 392 DEBUG_ASSERT(flow_graph->VerifyUseLists()); |
| 393 // A canonicalization pass to remove e.g. smi checks on smi constants. | 393 // A canonicalization pass to remove e.g. smi checks on smi constants. |
| 394 optimizer.Canonicalize(); | 394 optimizer.Canonicalize(); |
| 395 ASSERT(flow_graph->VerifyUseLists()); | 395 DEBUG_ASSERT(flow_graph->VerifyUseLists()); |
| 396 // Canonicalization introduced more opportunities for constant | 396 // Canonicalization introduced more opportunities for constant |
| 397 // propagation. | 397 // propagation. |
| 398 ConstantPropagator::Optimize(flow_graph); | 398 ConstantPropagator::Optimize(flow_graph); |
| 399 ASSERT(flow_graph->VerifyUseLists()); | 399 DEBUG_ASSERT(flow_graph->VerifyUseLists()); |
| 400 } | 400 } |
| 401 | 401 |
| 402 // Propagate types and eliminate even more type tests. | 402 // Propagate types and eliminate even more type tests. |
| 403 // Recompute types after constant propagation to infer more precise | 403 // Recompute types after constant propagation to infer more precise |
| 404 // types for uses that were previously reached by now eliminated phis. | 404 // types for uses that were previously reached by now eliminated phis. |
| 405 FlowGraphTypePropagator::Propagate(flow_graph); | 405 FlowGraphTypePropagator::Propagate(flow_graph); |
| 406 ASSERT(flow_graph->VerifyUseLists()); | 406 DEBUG_ASSERT(flow_graph->VerifyUseLists()); |
| 407 | 407 |
| 408 // Unbox doubles. Performed after constant propagation to minimize | 408 // Unbox doubles. Performed after constant propagation to minimize |
| 409 // interference from phis merging double values and tagged | 409 // interference from phis merging double values and tagged |
| 410 // values coming from dead paths. | 410 // values coming from dead paths. |
| 411 optimizer.SelectRepresentations(); | 411 optimizer.SelectRepresentations(); |
| 412 ASSERT(flow_graph->VerifyUseLists()); | 412 DEBUG_ASSERT(flow_graph->VerifyUseLists()); |
| 413 | 413 |
| 414 if (FLAG_common_subexpression_elimination || | 414 if (FLAG_common_subexpression_elimination || |
| 415 FLAG_loop_invariant_code_motion) { | 415 FLAG_loop_invariant_code_motion) { |
| 416 flow_graph->ComputeBlockEffects(); | 416 flow_graph->ComputeBlockEffects(); |
| 417 } | 417 } |
| 418 | 418 |
| 419 if (FLAG_common_subexpression_elimination) { | 419 if (FLAG_common_subexpression_elimination) { |
| 420 if (DominatorBasedCSE::Optimize(flow_graph)) { | 420 if (DominatorBasedCSE::Optimize(flow_graph)) { |
| 421 ASSERT(flow_graph->VerifyUseLists()); | 421 DEBUG_ASSERT(flow_graph->VerifyUseLists()); |
| 422 // Do another round of CSE to take secondary effects into account: | 422 // Do another round of CSE to take secondary effects into account: |
| 423 // e.g. when eliminating dependent loads (a.x[0] + a.x[0]) | 423 // e.g. when eliminating dependent loads (a.x[0] + a.x[0]) |
| 424 // TODO(fschneider): Change to a one-pass optimization pass. | 424 // TODO(fschneider): Change to a one-pass optimization pass. |
| 425 DominatorBasedCSE::Optimize(flow_graph); | 425 DominatorBasedCSE::Optimize(flow_graph); |
| 426 ASSERT(flow_graph->VerifyUseLists()); | 426 DEBUG_ASSERT(flow_graph->VerifyUseLists()); |
| 427 } | 427 } |
| 428 } | 428 } |
| 429 | 429 |
| 430 // Run loop-invariant code motion right after load elimination since it | 430 // Run loop-invariant code motion right after load elimination since it |
| 431 // depends on the numbering of loads from the previous load-elimination. | 431 // depends on the numbering of loads from the previous load-elimination. |
| 432 if (FLAG_loop_invariant_code_motion) { | 432 if (FLAG_loop_invariant_code_motion) { |
| 433 LICM licm(flow_graph); | 433 LICM licm(flow_graph); |
| 434 licm.Optimize(); | 434 licm.Optimize(); |
| 435 ASSERT(flow_graph->VerifyUseLists()); | 435 DEBUG_ASSERT(flow_graph->VerifyUseLists()); |
| 436 } | 436 } |
| 437 flow_graph->RemoveRedefinitions(); | 437 flow_graph->RemoveRedefinitions(); |
| 438 | 438 |
| 439 // Optimize (a << b) & c patterns, merge operations. | 439 // Optimize (a << b) & c patterns, merge operations. |
| 440 // Run after CSE in order to have more opportunity to merge | 440 // Run after CSE in order to have more opportunity to merge |
| 441 // instructions that have same inputs. | 441 // instructions that have same inputs. |
| 442 optimizer.TryOptimizePatterns(); | 442 optimizer.TryOptimizePatterns(); |
| 443 ASSERT(flow_graph->VerifyUseLists()); | 443 DEBUG_ASSERT(flow_graph->VerifyUseLists()); |
| 444 | 444 |
| 445 DeadStoreElimination::Optimize(flow_graph); | 445 DeadStoreElimination::Optimize(flow_graph); |
| 446 | 446 |
| 447 if (FLAG_range_analysis) { | 447 if (FLAG_range_analysis) { |
| 448 // Propagate types after store-load-forwarding. Some phis may have | 448 // Propagate types after store-load-forwarding. Some phis may have |
| 449 // become smi phis that can be processed by range analysis. | 449 // become smi phis that can be processed by range analysis. |
| 450 FlowGraphTypePropagator::Propagate(flow_graph); | 450 FlowGraphTypePropagator::Propagate(flow_graph); |
| 451 ASSERT(flow_graph->VerifyUseLists()); | 451 DEBUG_ASSERT(flow_graph->VerifyUseLists()); |
| 452 | 452 |
| 453 // We have to perform range analysis after LICM because it | 453 // We have to perform range analysis after LICM because it |
| 454 // optimistically moves CheckSmi through phis into loop preheaders | 454 // optimistically moves CheckSmi through phis into loop preheaders |
| 455 // making some phis smi. | 455 // making some phis smi. |
| 456 optimizer.InferSmiRanges(); | 456 optimizer.InferSmiRanges(); |
| 457 ASSERT(flow_graph->VerifyUseLists()); | 457 DEBUG_ASSERT(flow_graph->VerifyUseLists()); |
| 458 } | 458 } |
| 459 | 459 |
| 460 if (FLAG_constant_propagation) { | 460 if (FLAG_constant_propagation) { |
| 461 // Constant propagation can use information from range analysis to | 461 // Constant propagation can use information from range analysis to |
| 462 // find unreachable branch targets and eliminate branches that have | 462 // find unreachable branch targets and eliminate branches that have |
| 463 // the same true- and false-target. | 463 // the same true- and false-target. |
| 464 ConstantPropagator::OptimizeBranches(flow_graph); | 464 ConstantPropagator::OptimizeBranches(flow_graph); |
| 465 ASSERT(flow_graph->VerifyUseLists()); | 465 DEBUG_ASSERT(flow_graph->VerifyUseLists()); |
| 466 } | 466 } |
| 467 | 467 |
| 468 // Recompute types after code movement was done to ensure correct | 468 // Recompute types after code movement was done to ensure correct |
| 469 // reaching types for hoisted values. | 469 // reaching types for hoisted values. |
| 470 FlowGraphTypePropagator::Propagate(flow_graph); | 470 FlowGraphTypePropagator::Propagate(flow_graph); |
| 471 ASSERT(flow_graph->VerifyUseLists()); | 471 DEBUG_ASSERT(flow_graph->VerifyUseLists()); |
| 472 | 472 |
| 473 // Optimize try-blocks. | 473 // Optimize try-blocks. |
| 474 TryCatchAnalyzer::Optimize(flow_graph); | 474 TryCatchAnalyzer::Optimize(flow_graph); |
| 475 | 475 |
| 476 // Detach environments from the instructions that can't deoptimize. | 476 // Detach environments from the instructions that can't deoptimize. |
| 477 // Do it before we attempt to perform allocation sinking to minimize | 477 // Do it before we attempt to perform allocation sinking to minimize |
| 478 // amount of materializations it has to perform. | 478 // amount of materializations it has to perform. |
| 479 optimizer.EliminateEnvironments(); | 479 optimizer.EliminateEnvironments(); |
| 480 | 480 |
| 481 DeadCodeElimination::EliminateDeadPhis(flow_graph); | 481 DeadCodeElimination::EliminateDeadPhis(flow_graph); |
| 482 ASSERT(flow_graph->VerifyUseLists()); | 482 DEBUG_ASSERT(flow_graph->VerifyUseLists()); |
| 483 | 483 |
| 484 // Attempt to sink allocations of temporary non-escaping objects to | 484 // Attempt to sink allocations of temporary non-escaping objects to |
| 485 // the deoptimization path. | 485 // the deoptimization path. |
| 486 AllocationSinking* sinking = NULL; | 486 AllocationSinking* sinking = NULL; |
| 487 if (FLAG_allocation_sinking && | 487 if (FLAG_allocation_sinking && |
| 488 (flow_graph->graph_entry()->SuccessorCount() == 1)) { | 488 (flow_graph->graph_entry()->SuccessorCount() == 1)) { |
| 489 // TODO(fschneider): Support allocation sinking with try-catch. | 489 // TODO(fschneider): Support allocation sinking with try-catch. |
| 490 sinking = new AllocationSinking(flow_graph); | 490 sinking = new AllocationSinking(flow_graph); |
| 491 sinking->Optimize(); | 491 sinking->Optimize(); |
| 492 } | 492 } |
| 493 ASSERT(flow_graph->VerifyUseLists()); | 493 DEBUG_ASSERT(flow_graph->VerifyUseLists()); |
| 494 | 494 |
| 495 // Ensure that all phis inserted by optimization passes have consistent | 495 // Ensure that all phis inserted by optimization passes have consistent |
| 496 // representations. | 496 // representations. |
| 497 optimizer.SelectRepresentations(); | 497 optimizer.SelectRepresentations(); |
| 498 | 498 |
| 499 if (optimizer.Canonicalize()) { | 499 if (optimizer.Canonicalize()) { |
| 500 // To fully remove redundant boxing (e.g. BoxDouble used only in | 500 // To fully remove redundant boxing (e.g. BoxDouble used only in |
| 501 // environments and UnboxDouble instructions) instruction we | 501 // environments and UnboxDouble instructions) instruction we |
| 502 // first need to replace all their uses and then fold them away. | 502 // first need to replace all their uses and then fold them away. |
| 503 // For now we just repeat Canonicalize twice to do that. | 503 // For now we just repeat Canonicalize twice to do that. |
| 504 // TODO(vegorov): implement a separate representation folding pass. | 504 // TODO(vegorov): implement a separate representation folding pass. |
| 505 optimizer.Canonicalize(); | 505 optimizer.Canonicalize(); |
| 506 } | 506 } |
| 507 ASSERT(flow_graph->VerifyUseLists()); | 507 DEBUG_ASSERT(flow_graph->VerifyUseLists()); |
| 508 | 508 |
| 509 if (sinking != NULL) { | 509 if (sinking != NULL) { |
| 510 // Remove all MaterializeObject instructions inserted by allocation | 510 // Remove all MaterializeObject instructions inserted by allocation |
| 511 // sinking from the flow graph and let them float on the side | 511 // sinking from the flow graph and let them float on the side |
| 512 // referenced only from environments. Register allocator will consider | 512 // referenced only from environments. Register allocator will consider |
| 513 // them as part of a deoptimization environment. | 513 // them as part of a deoptimization environment. |
| 514 sinking->DetachMaterializations(); | 514 sinking->DetachMaterializations(); |
| 515 } | 515 } |
| 516 | 516 |
| 517 // Compute and store graph informations (call & instruction counts) | 517 // Compute and store graph informations (call & instruction counts) |
| (...skipping 459 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 977 const Object& result = | 977 const Object& result = |
| 978 Object::Handle(isolate->object_store()->sticky_error()); | 978 Object::Handle(isolate->object_store()->sticky_error()); |
| 979 isolate->object_store()->clear_sticky_error(); | 979 isolate->object_store()->clear_sticky_error(); |
| 980 return result.raw(); | 980 return result.raw(); |
| 981 } | 981 } |
| 982 UNREACHABLE(); | 982 UNREACHABLE(); |
| 983 return Object::null(); | 983 return Object::null(); |
| 984 } | 984 } |
| 985 | 985 |
| 986 } // namespace dart | 986 } // namespace dart |
| OLD | NEW |