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/flow_graph_allocator.h" | 5 #include "vm/flow_graph_allocator.h" |
6 | 6 |
7 #include "vm/bit_vector.h" | 7 #include "vm/bit_vector.h" |
8 #include "vm/intermediate_language.h" | 8 #include "vm/intermediate_language.h" |
9 #include "vm/il_printer.h" | 9 #include "vm/il_printer.h" |
10 #include "vm/flow_graph_builder.h" | 10 #include "vm/flow_graph_builder.h" |
11 #include "vm/flow_graph_compiler.h" | 11 #include "vm/flow_graph_compiler.h" |
| 12 #include "vm/parser.h" |
12 | 13 |
13 namespace dart { | 14 namespace dart { |
14 | 15 |
15 DEFINE_FLAG(bool, print_ssa_liveness, false, | 16 DEFINE_FLAG(bool, print_ssa_liveness, false, |
16 "Print liveness for ssa variables."); | 17 "Print liveness for ssa variables."); |
17 DEFINE_FLAG(bool, trace_ssa_allocator, false, | 18 DEFINE_FLAG(bool, trace_ssa_allocator, false, |
18 "Trace register allocation over SSA."); | 19 "Trace register allocation over SSA."); |
19 | 20 |
20 #ifdef DEBUG | 21 #ifdef DEBUG |
21 #define TRACE_ALLOC(m) do { \ | 22 #define TRACE_ALLOC(m) do { \ |
(...skipping 110 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
132 BlockEntryInstr* pred = block->PredecessorAt(k); | 133 BlockEntryInstr* pred = block->PredecessorAt(k); |
133 const intptr_t use = val->AsUse()->definition()->ssa_temp_index(); | 134 const intptr_t use = val->AsUse()->definition()->ssa_temp_index(); |
134 live_out_[pred->postorder_number()]->Add(use); | 135 live_out_[pred->postorder_number()]->Add(use); |
135 } | 136 } |
136 } | 137 } |
137 } | 138 } |
138 } | 139 } |
139 } | 140 } |
140 } | 141 } |
141 | 142 |
| 143 // Process incoming parameters. |
| 144 GraphEntryInstr* graph_entry = postorder_[block_count - 1]->AsGraphEntry(); |
| 145 for (intptr_t i = 0; i < graph_entry->start_env()->values().length(); i++) { |
| 146 Value* val = graph_entry->start_env()->values()[i]; |
| 147 if (val->IsUse()) { |
| 148 const intptr_t vreg = val->AsUse()->definition()->ssa_temp_index(); |
| 149 kill_[0]->Add(vreg); |
| 150 live_in_[0]->Remove(vreg); |
| 151 } |
| 152 } |
| 153 |
142 // Update initial live_in sets to match live_out sets. Has to be | 154 // Update initial live_in sets to match live_out sets. Has to be |
143 // done in a separate path because of backwards branches. | 155 // done in a separate path because of backwards branches. |
144 for (intptr_t i = 0; i < block_count; i++) { | 156 for (intptr_t i = 0; i < block_count; i++) { |
145 UpdateLiveIn(*postorder_[i]); | 157 UpdateLiveIn(*postorder_[i]); |
146 } | 158 } |
147 } | 159 } |
148 | 160 |
149 | 161 |
150 bool FlowGraphAllocator::UpdateLiveOut(const BlockEntryInstr& instr) { | 162 bool FlowGraphAllocator::UpdateLiveOut(const BlockEntryInstr& instr) { |
151 BitVector* live_out = live_out_[instr.postorder_number()]; | 163 BitVector* live_out = live_out_[instr.postorder_number()]; |
(...skipping 237 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
389 while (current != block) { | 401 while (current != block) { |
390 // Skip parallel moves that we insert while processing instructions. | 402 // Skip parallel moves that we insert while processing instructions. |
391 if (!current->IsParallelMove()) { | 403 if (!current->IsParallelMove()) { |
392 ProcessOneInstruction(block, current); | 404 ProcessOneInstruction(block, current); |
393 } | 405 } |
394 current = current->previous(); | 406 current = current->previous(); |
395 } | 407 } |
396 | 408 |
397 ConnectIncomingPhiMoves(block); | 409 ConnectIncomingPhiMoves(block); |
398 } | 410 } |
| 411 |
| 412 // Process incoming parameters. |
| 413 const intptr_t fixed_parameters_count = |
| 414 builder_->parsed_function().function().num_fixed_parameters(); |
| 415 |
| 416 GraphEntryInstr* graph_entry = postorder_[block_count - 1]->AsGraphEntry(); |
| 417 for (intptr_t i = 0; i < graph_entry->start_env()->values().length(); i++) { |
| 418 Value* val = graph_entry->start_env()->values()[i]; |
| 419 if (val->IsUse()) { |
| 420 ParameterInstr* param = val->AsUse()->definition()->AsParameter(); |
| 421 |
| 422 LiveRange* range = GetLiveRange(param->ssa_temp_index()); |
| 423 range->AddUseInterval(graph_entry->start_pos(), graph_entry->end_pos()); |
| 424 range->DefineAt(graph_entry->start_pos()); |
| 425 |
| 426 // Slot index for the rightmost parameter is -1. |
| 427 const intptr_t slot_index = param->index() - fixed_parameters_count; |
| 428 range->set_assigned_location(Location::StackSlot(slot_index)); |
| 429 |
| 430 range->finger()->Initialize(range); |
| 431 UsePosition* use = range->finger()->FirstRegisterBeneficialUse( |
| 432 graph_entry->start_pos()); |
| 433 if (use != NULL) { |
| 434 LiveRange* tail = SplitBetween(range, |
| 435 graph_entry->start_pos(), |
| 436 use->pos()); |
| 437 AddToUnallocated(tail); |
| 438 } |
| 439 ConvertAllUses(range); |
| 440 } |
| 441 } |
399 } | 442 } |
400 | 443 |
401 // | 444 // |
402 // When describing shape of live ranges in comments below we are going to use | 445 // When describing shape of live ranges in comments below we are going to use |
403 // the following notation: | 446 // the following notation: |
404 // | 447 // |
405 // B block entry | 448 // B block entry |
406 // g goto instruction | 449 // g goto instruction |
407 // m parallel move | 450 // m parallel move |
408 // i any other instruction | 451 // i any other instruction |
(...skipping 131 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
540 const intptr_t pos = current->lifetime_position(); | 583 const intptr_t pos = current->lifetime_position(); |
541 ASSERT(IsInstructionPosition(pos)); | 584 ASSERT(IsInstructionPosition(pos)); |
542 | 585 |
543 LocationSummary* locs = current->locs(); | 586 LocationSummary* locs = current->locs(); |
544 | 587 |
545 // TODO(vegorov): number of inputs must match number of input locations. | 588 // TODO(vegorov): number of inputs must match number of input locations. |
546 if (locs->input_count() != current->InputCount()) { | 589 if (locs->input_count() != current->InputCount()) { |
547 builder_->Bailout("ssa allocator: number of input locations mismatch"); | 590 builder_->Bailout("ssa allocator: number of input locations mismatch"); |
548 } | 591 } |
549 | 592 |
| 593 // Normalize same-as-first-input output if input is specified as |
| 594 // fixed register. |
| 595 if (locs->out().IsUnallocated() && |
| 596 (locs->out().policy() == Location::kSameAsFirstInput) && |
| 597 (locs->in(0).IsRegister())) { |
| 598 locs->set_out(locs->in(0)); |
| 599 } |
| 600 |
550 const bool output_same_as_first_input = | 601 const bool output_same_as_first_input = |
551 locs->out().IsUnallocated() && | 602 locs->out().IsUnallocated() && |
552 (locs->out().policy() == Location::kSameAsFirstInput); | 603 (locs->out().policy() == Location::kSameAsFirstInput); |
553 | 604 |
554 // Add uses from the deoptimization environment. | 605 // Add uses from the deoptimization environment. |
555 if (current->env() != NULL) { | 606 if (current->env() != NULL) { |
556 // Any value mentioned in the deoptimization environment should survive | 607 // Any value mentioned in the deoptimization environment should survive |
557 // until the end of instruction but it does not need to be in the register. | 608 // until the end of instruction but it does not need to be in the register. |
558 // Expected shape of live range: | 609 // Expected shape of live range: |
559 // | 610 // |
(...skipping 528 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1088 return i; | 1139 return i; |
1089 } | 1140 } |
1090 } | 1141 } |
1091 spill_slots_.Add(0); | 1142 spill_slots_.Add(0); |
1092 return spill_slots_.length() - 1; | 1143 return spill_slots_.length() - 1; |
1093 } | 1144 } |
1094 | 1145 |
1095 | 1146 |
1096 void FlowGraphAllocator::Spill(LiveRange* range) { | 1147 void FlowGraphAllocator::Spill(LiveRange* range) { |
1097 const intptr_t spill_index = AllocateSpillSlotFor(range); | 1148 const intptr_t spill_index = AllocateSpillSlotFor(range); |
1098 ASSERT(spill_slots_[spill_index] < range->Start()); | 1149 ASSERT(spill_slots_[spill_index] <= range->Start()); |
1099 spill_slots_[spill_index] = range->End(); | 1150 spill_slots_[spill_index] = range->End(); |
1100 range->set_assigned_location(Location::SpillSlot(spill_index)); | 1151 range->set_assigned_location(Location::StackSlot(spill_index)); |
1101 ConvertAllUses(range); | 1152 ConvertAllUses(range); |
1102 } | 1153 } |
1103 | 1154 |
1104 | 1155 |
1105 intptr_t FlowGraphAllocator::FirstIntersectionWithAllocated( | 1156 intptr_t FlowGraphAllocator::FirstIntersectionWithAllocated( |
1106 Register reg, LiveRange* unallocated) { | 1157 Register reg, LiveRange* unallocated) { |
1107 intptr_t intersection = kMaxPosition; | 1158 intptr_t intersection = kMaxPosition; |
1108 for (intptr_t i = 0; i < cpu_regs_[reg].length(); i++) { | 1159 for (intptr_t i = 0; i < cpu_regs_[reg].length(); i++) { |
1109 LiveRange* allocated = cpu_regs_[reg][i]; | 1160 LiveRange* allocated = cpu_regs_[reg][i]; |
1110 if (allocated == NULL) continue; | 1161 if (allocated == NULL) continue; |
(...skipping 457 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1568 LiveRange* range = GetLiveRange(it.Current()); | 1619 LiveRange* range = GetLiveRange(it.Current()); |
1569 for (intptr_t j = 0; j < block->PredecessorCount(); j++) { | 1620 for (intptr_t j = 0; j < block->PredecessorCount(); j++) { |
1570 ConnectSplitSiblings(range, block->PredecessorAt(j), block); | 1621 ConnectSplitSiblings(range, block->PredecessorAt(j), block); |
1571 } | 1622 } |
1572 } | 1623 } |
1573 } | 1624 } |
1574 } | 1625 } |
1575 | 1626 |
1576 | 1627 |
1577 void FlowGraphAllocator::AllocateRegisters() { | 1628 void FlowGraphAllocator::AllocateRegisters() { |
1578 GraphEntryInstr* entry = block_order_[0]->AsGraphEntry(); | |
1579 ASSERT(entry != NULL); | |
1580 | |
1581 for (intptr_t i = 0; i < entry->start_env()->values().length(); i++) { | |
1582 if (entry->start_env()->values()[i]->IsUse()) { | |
1583 builder_->Bailout("ssa allocator: unsupported start environment"); | |
1584 } | |
1585 } | |
1586 | |
1587 AnalyzeLiveness(); | 1629 AnalyzeLiveness(); |
1588 | 1630 |
1589 BuildLiveRanges(); | 1631 BuildLiveRanges(); |
1590 | 1632 |
1591 if (FLAG_print_ssa_liveness) { | 1633 if (FLAG_print_ssa_liveness) { |
1592 DumpLiveness(); | 1634 DumpLiveness(); |
1593 } | 1635 } |
1594 | 1636 |
1595 if (FLAG_trace_ssa_allocator) { | 1637 if (FLAG_trace_ssa_allocator) { |
1596 PrintLiveRanges(); | 1638 PrintLiveRanges(); |
1597 } | 1639 } |
1598 | 1640 |
1599 AllocateCPURegisters(); | 1641 AllocateCPURegisters(); |
1600 | 1642 |
1601 ResolveControlFlow(); | 1643 ResolveControlFlow(); |
1602 | 1644 |
| 1645 GraphEntryInstr* entry = block_order_[0]->AsGraphEntry(); |
| 1646 ASSERT(entry != NULL); |
| 1647 entry->set_spill_slot_count(spill_slots_.length()); |
| 1648 |
1603 if (FLAG_trace_ssa_allocator) { | 1649 if (FLAG_trace_ssa_allocator) { |
1604 OS::Print("-- ir after allocation -------------------------\n"); | 1650 OS::Print("-- ir after allocation -------------------------\n"); |
1605 FlowGraphPrinter printer(Function::Handle(), block_order_, true); | 1651 FlowGraphPrinter printer(Function::Handle(), block_order_, true); |
1606 printer.PrintBlocks(); | 1652 printer.PrintBlocks(); |
1607 } | 1653 } |
1608 } | 1654 } |
1609 | 1655 |
1610 | 1656 |
1611 } // namespace dart | 1657 } // namespace dart |
OLD | NEW |