OLD | NEW |
1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2013, 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.h" | 10 #include "vm/flow_graph.h" |
(...skipping 592 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
603 slot_index -= flow_graph_.num_non_copied_params(); | 603 slot_index -= flow_graph_.num_non_copied_params(); |
604 | 604 |
605 range->set_assigned_location(Location::StackSlot(slot_index)); | 605 range->set_assigned_location(Location::StackSlot(slot_index)); |
606 range->set_spill_slot(Location::StackSlot(slot_index)); | 606 range->set_spill_slot(Location::StackSlot(slot_index)); |
607 } else { | 607 } else { |
608 ConstantInstr* constant = defn->AsConstant(); | 608 ConstantInstr* constant = defn->AsConstant(); |
609 ASSERT(constant != NULL); | 609 ASSERT(constant != NULL); |
610 range->set_assigned_location(Location::Constant(constant->value())); | 610 range->set_assigned_location(Location::Constant(constant->value())); |
611 range->set_spill_slot(Location::Constant(constant->value())); | 611 range->set_spill_slot(Location::Constant(constant->value())); |
612 } | 612 } |
613 AssignSafepoints(range); | 613 AssignSafepoints(defn, range); |
614 range->finger()->Initialize(range); | 614 range->finger()->Initialize(range); |
615 UsePosition* use = | 615 UsePosition* use = |
616 range->finger()->FirstRegisterBeneficialUse(block->start_pos()); | 616 range->finger()->FirstRegisterBeneficialUse(block->start_pos()); |
617 if (use != NULL) { | 617 if (use != NULL) { |
618 LiveRange* tail = | 618 LiveRange* tail = |
619 SplitBetween(range, block->start_pos(), use->pos()); | 619 SplitBetween(range, block->start_pos(), use->pos()); |
620 // Parameters and constants are tagged, so allocated to CPU registers. | 620 // Parameters and constants are tagged, so allocated to CPU registers. |
621 CompleteRange(tail, Location::kRegister); | 621 CompleteRange(tail, Location::kRegister); |
622 } | 622 } |
623 ConvertAllUses(range); | 623 ConvertAllUses(range); |
(...skipping 152 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
776 GotoInstr* goto_instr = pred->last_instruction()->AsGoto(); | 776 GotoInstr* goto_instr = pred->last_instruction()->AsGoto(); |
777 ASSERT((goto_instr != NULL) && (goto_instr->HasParallelMove())); | 777 ASSERT((goto_instr != NULL) && (goto_instr->HasParallelMove())); |
778 MoveOperands* move = | 778 MoveOperands* move = |
779 goto_instr->parallel_move()->MoveOperandsAt(move_idx); | 779 goto_instr->parallel_move()->MoveOperandsAt(move_idx); |
780 move->set_dest(Location::PrefersRegister()); | 780 move->set_dest(Location::PrefersRegister()); |
781 range->AddUse(pos, move->dest_slot()); | 781 range->AddUse(pos, move->dest_slot()); |
782 } | 782 } |
783 | 783 |
784 // All phi resolution moves are connected. Phi's live range is | 784 // All phi resolution moves are connected. Phi's live range is |
785 // complete. | 785 // complete. |
786 AssignSafepoints(range); | 786 AssignSafepoints(phi, range); |
787 | 787 |
788 CompleteRange(range, RegisterKindForResult(phi)); | 788 CompleteRange(range, RegisterKindForResult(phi)); |
789 | 789 |
790 move_idx++; | 790 move_idx++; |
791 } | 791 } |
792 } | 792 } |
793 | 793 |
794 | 794 |
795 void FlowGraphAllocator::ProcessEnvironmentUses(BlockEntryInstr* block, | 795 void FlowGraphAllocator::ProcessEnvironmentUses(BlockEntryInstr* block, |
796 Instruction* current) { | 796 Instruction* current) { |
(...skipping 190 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
987 range->AddUseInterval(block->start_pos(), pos + 1); | 987 range->AddUseInterval(block->start_pos(), pos + 1); |
988 range->AddUse(pos + 1, in_ref); | 988 range->AddUse(pos + 1, in_ref); |
989 } | 989 } |
990 } else { | 990 } else { |
991 ASSERT(in_ref->IsConstant()); | 991 ASSERT(in_ref->IsConstant()); |
992 } | 992 } |
993 } | 993 } |
994 | 994 |
995 | 995 |
996 void FlowGraphAllocator::ProcessOneOutput(BlockEntryInstr* block, | 996 void FlowGraphAllocator::ProcessOneOutput(BlockEntryInstr* block, |
997 Instruction* current, | |
998 intptr_t pos, | 997 intptr_t pos, |
999 Location* out, | 998 Location* out, |
1000 Definition* def, | 999 Definition* def, |
1001 intptr_t vreg, | 1000 intptr_t vreg, |
1002 bool output_same_as_first_input, | 1001 bool output_same_as_first_input, |
1003 Location* in_ref, | 1002 Location* in_ref, |
1004 Definition* input, | 1003 Definition* input, |
1005 intptr_t input_vreg, | 1004 intptr_t input_vreg, |
1006 BitVector* interference_set) { | 1005 BitVector* interference_set) { |
1007 ASSERT(out != NULL); | 1006 ASSERT(out != NULL); |
(...skipping 88 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1096 // | 1095 // |
1097 ASSERT(out->Equals(Location::RequiresRegister()) || | 1096 ASSERT(out->Equals(Location::RequiresRegister()) || |
1098 out->Equals(Location::RequiresFpuRegister())); | 1097 out->Equals(Location::RequiresFpuRegister())); |
1099 | 1098 |
1100 // Shorten live range to the point of definition and add use to be filled by | 1099 // Shorten live range to the point of definition and add use to be filled by |
1101 // allocator. | 1100 // allocator. |
1102 range->DefineAt(pos); | 1101 range->DefineAt(pos); |
1103 range->AddUse(pos, out); | 1102 range->AddUse(pos, out); |
1104 } | 1103 } |
1105 | 1104 |
1106 AssignSafepoints(range); | 1105 AssignSafepoints(def, range); |
1107 CompleteRange(range, RegisterKindForResult(current)); | 1106 CompleteRange(range, RegisterKindForResult(def)); |
1108 } | 1107 } |
1109 | 1108 |
1110 | 1109 |
1111 // Create and update live ranges corresponding to instruction's inputs, | 1110 // Create and update live ranges corresponding to instruction's inputs, |
1112 // temporaries and output. | 1111 // temporaries and output. |
1113 void FlowGraphAllocator::ProcessOneInstruction(BlockEntryInstr* block, | 1112 void FlowGraphAllocator::ProcessOneInstruction(BlockEntryInstr* block, |
1114 Instruction* current, | 1113 Instruction* current, |
1115 BitVector* interference_set) { | 1114 BitVector* interference_set) { |
1116 LocationSummary* locs = current->locs(); | 1115 LocationSummary* locs = current->locs(); |
1117 | 1116 |
(...skipping 176 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1294 if (out->IsPairLocation()) { | 1293 if (out->IsPairLocation()) { |
1295 ASSERT(def->HasPairRepresentation()); | 1294 ASSERT(def->HasPairRepresentation()); |
1296 PairLocation* pair = out->AsPairLocation(); | 1295 PairLocation* pair = out->AsPairLocation(); |
1297 if (output_same_as_first_input) { | 1296 if (output_same_as_first_input) { |
1298 ASSERT(locs->in_slot(0)->IsPairLocation()); | 1297 ASSERT(locs->in_slot(0)->IsPairLocation()); |
1299 PairLocation* in_pair = locs->in_slot(0)->AsPairLocation(); | 1298 PairLocation* in_pair = locs->in_slot(0)->AsPairLocation(); |
1300 Definition* input = current->InputAt(0)->definition(); | 1299 Definition* input = current->InputAt(0)->definition(); |
1301 ASSERT(input->HasPairRepresentation()); | 1300 ASSERT(input->HasPairRepresentation()); |
1302 // Each element of the pair is assigned it's own virtual register number | 1301 // Each element of the pair is assigned it's own virtual register number |
1303 // and is allocated its own LiveRange. | 1302 // and is allocated its own LiveRange. |
1304 ProcessOneOutput(block, current, pos, // BlockEntry, Instruction, seq. | 1303 ProcessOneOutput(block, pos, // BlockEntry, seq. |
1305 pair->SlotAt(0), def, // (output) Location, Definition. | 1304 pair->SlotAt(0), def, // (output) Location, Definition. |
1306 def->ssa_temp_index(), // (output) virtual register. | 1305 def->ssa_temp_index(), // (output) virtual register. |
1307 true, // output mapped to first input. | 1306 true, // output mapped to first input. |
1308 in_pair->SlotAt(0), input, // (input) Location, Def. | 1307 in_pair->SlotAt(0), input, // (input) Location, Def. |
1309 input->ssa_temp_index(), // (input) virtual register. | 1308 input->ssa_temp_index(), // (input) virtual register. |
1310 interference_set); | 1309 interference_set); |
1311 ProcessOneOutput(block, current, pos, | 1310 ProcessOneOutput(block, pos, |
1312 pair->SlotAt(1), def, | 1311 pair->SlotAt(1), def, |
1313 ToSecondPairVreg(def->ssa_temp_index()), | 1312 ToSecondPairVreg(def->ssa_temp_index()), |
1314 true, | 1313 true, |
1315 in_pair->SlotAt(1), input, | 1314 in_pair->SlotAt(1), input, |
1316 ToSecondPairVreg(input->ssa_temp_index()), | 1315 ToSecondPairVreg(input->ssa_temp_index()), |
1317 interference_set); | 1316 interference_set); |
1318 } else { | 1317 } else { |
1319 // Each element of the pair is assigned it's own virtual register number | 1318 // Each element of the pair is assigned it's own virtual register number |
1320 // and is allocated its own LiveRange. | 1319 // and is allocated its own LiveRange. |
1321 ProcessOneOutput(block, current, pos, | 1320 ProcessOneOutput(block, pos, |
1322 pair->SlotAt(0), def, | 1321 pair->SlotAt(0), def, |
1323 def->ssa_temp_index(), | 1322 def->ssa_temp_index(), |
1324 false, // output is not mapped to first input. | 1323 false, // output is not mapped to first input. |
1325 NULL, NULL, -1, // First input not needed. | 1324 NULL, NULL, -1, // First input not needed. |
1326 interference_set); | 1325 interference_set); |
1327 ProcessOneOutput(block, current, pos, | 1326 ProcessOneOutput(block, pos, |
1328 pair->SlotAt(1), def, | 1327 pair->SlotAt(1), def, |
1329 ToSecondPairVreg(def->ssa_temp_index()), | 1328 ToSecondPairVreg(def->ssa_temp_index()), |
1330 false, | 1329 false, |
1331 NULL, NULL, -1, | 1330 NULL, NULL, -1, |
1332 interference_set); | 1331 interference_set); |
1333 } | 1332 } |
1334 } else { | 1333 } else { |
1335 if (output_same_as_first_input) { | 1334 if (output_same_as_first_input) { |
1336 Location* in_ref = locs->in_slot(0); | 1335 Location* in_ref = locs->in_slot(0); |
1337 Definition* input = current->InputAt(0)->definition(); | 1336 Definition* input = current->InputAt(0)->definition(); |
1338 ASSERT(!in_ref->IsPairLocation()); | 1337 ASSERT(!in_ref->IsPairLocation()); |
1339 ProcessOneOutput(block, current, pos, // BlockEntry, Instruction, seq. | 1338 ProcessOneOutput(block, pos, // BlockEntry, Instruction, seq. |
1340 out, def, // (output) Location, Definition. | 1339 out, def, // (output) Location, Definition. |
1341 def->ssa_temp_index(), // (output) virtual register. | 1340 def->ssa_temp_index(), // (output) virtual register. |
1342 true, // output mapped to first input. | 1341 true, // output mapped to first input. |
1343 in_ref, input, // (input) Location, Def. | 1342 in_ref, input, // (input) Location, Def. |
1344 input->ssa_temp_index(), // (input) virtual register. | 1343 input->ssa_temp_index(), // (input) virtual register. |
1345 interference_set); | 1344 interference_set); |
1346 } else { | 1345 } else { |
1347 ProcessOneOutput(block, current, pos, | 1346 ProcessOneOutput(block, pos, |
1348 out, def, | 1347 out, def, |
1349 def->ssa_temp_index(), | 1348 def->ssa_temp_index(), |
1350 false, // output is not mapped to first input. | 1349 false, // output is not mapped to first input. |
1351 NULL, NULL, -1, // First input not needed. | 1350 NULL, NULL, -1, // First input not needed. |
1352 interference_set); | 1351 interference_set); |
1353 } | 1352 } |
1354 } | 1353 } |
1355 } | 1354 } |
1356 | 1355 |
1357 | 1356 |
(...skipping 1098 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2456 interval = interval->next()) { | 2455 interval = interval->next()) { |
2457 if (interval->Contains(pos)) { | 2456 if (interval->Contains(pos)) { |
2458 return true; | 2457 return true; |
2459 } | 2458 } |
2460 } | 2459 } |
2461 | 2460 |
2462 return false; | 2461 return false; |
2463 } | 2462 } |
2464 | 2463 |
2465 | 2464 |
2466 void FlowGraphAllocator::AssignSafepoints(LiveRange* range) { | 2465 void FlowGraphAllocator::AssignSafepoints(Definition* defn, |
| 2466 LiveRange* range) { |
2467 for (intptr_t i = safepoints_.length() - 1; i >= 0; i--) { | 2467 for (intptr_t i = safepoints_.length() - 1; i >= 0; i--) { |
2468 Instruction* instr = safepoints_[i]; | 2468 Instruction* safepoint_instr = safepoints_[i]; |
| 2469 if (safepoint_instr == defn) { |
| 2470 // The value is not live until after the definition is fully executed, |
| 2471 // don't assign the safepoint inside the definition itself to |
| 2472 // definition's liverange. |
| 2473 continue; |
| 2474 } |
2469 | 2475 |
2470 const intptr_t pos = instr->lifetime_position(); | 2476 const intptr_t pos = safepoint_instr->lifetime_position(); |
2471 if (range->End() <= pos) break; | 2477 if (range->End() <= pos) break; |
2472 | 2478 |
2473 if (range->Contains(pos)) range->AddSafepoint(pos, instr->locs()); | 2479 if (range->Contains(pos)) { |
| 2480 range->AddSafepoint(pos, safepoint_instr->locs()); |
| 2481 } |
2474 } | 2482 } |
2475 } | 2483 } |
2476 | 2484 |
2477 | 2485 |
2478 static inline bool ShouldBeAllocatedBefore(LiveRange* a, LiveRange* b) { | 2486 static inline bool ShouldBeAllocatedBefore(LiveRange* a, LiveRange* b) { |
2479 // TODO(vegorov): consider first hint position when ordering live ranges. | 2487 // TODO(vegorov): consider first hint position when ordering live ranges. |
2480 return a->Start() <= b->Start(); | 2488 return a->Start() <= b->Start(); |
2481 } | 2489 } |
2482 | 2490 |
2483 | 2491 |
(...skipping 392 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2876 OS::Print("-- [after ssa allocator] ir [%s] -------------\n", | 2884 OS::Print("-- [after ssa allocator] ir [%s] -------------\n", |
2877 function.ToFullyQualifiedCString()); | 2885 function.ToFullyQualifiedCString()); |
2878 FlowGraphPrinter printer(flow_graph_, true); | 2886 FlowGraphPrinter printer(flow_graph_, true); |
2879 printer.PrintBlocks(); | 2887 printer.PrintBlocks(); |
2880 OS::Print("----------------------------------------------\n"); | 2888 OS::Print("----------------------------------------------\n"); |
2881 } | 2889 } |
2882 } | 2890 } |
2883 | 2891 |
2884 | 2892 |
2885 } // namespace dart | 2893 } // namespace dart |
OLD | NEW |