Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(382)

Side by Side Diff: runtime/vm/flow_graph_allocator.cc

Issue 11956004: Fix vm code base so that it can be built for --arch=simarm (no snapshot yet). (Closed) Base URL: http://dart.googlecode.com/svn/branches/bleeding_edge/dart/
Patch Set: Created 7 years, 11 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
OLDNEW
1 // Copyright (c) 2012, 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"
11 #include "vm/flow_graph_compiler.h" 11 #include "vm/flow_graph_compiler.h"
(...skipping 53 matching lines...) Expand 10 before | Expand all | Expand 10 after
65 reaching_defs_(flow_graph), 65 reaching_defs_(flow_graph),
66 mint_values_(NULL), 66 mint_values_(NULL),
67 block_order_(flow_graph.reverse_postorder()), 67 block_order_(flow_graph.reverse_postorder()),
68 postorder_(flow_graph.postorder()), 68 postorder_(flow_graph.postorder()),
69 live_out_(block_order_.length()), 69 live_out_(block_order_.length()),
70 kill_(block_order_.length()), 70 kill_(block_order_.length()),
71 live_in_(block_order_.length()), 71 live_in_(block_order_.length()),
72 vreg_count_(flow_graph.max_virtual_register_number()), 72 vreg_count_(flow_graph.max_virtual_register_number()),
73 live_ranges_(flow_graph.max_virtual_register_number()), 73 live_ranges_(flow_graph.max_virtual_register_number()),
74 cpu_regs_(), 74 cpu_regs_(),
75 xmm_regs_(), 75 fpu_regs_(),
76 blocked_cpu_registers_(), 76 blocked_cpu_registers_(),
77 blocked_xmm_registers_(), 77 blocked_fpu_registers_(),
78 cpu_spill_slot_count_(0) { 78 cpu_spill_slot_count_(0) {
79 for (intptr_t i = 0; i < vreg_count_; i++) live_ranges_.Add(NULL); 79 for (intptr_t i = 0; i < vreg_count_; i++) live_ranges_.Add(NULL);
80 80
81 blocked_cpu_registers_[CTX] = true; 81 blocked_cpu_registers_[CTX] = true;
82 if (TMP != kNoRegister) { 82 if (TMP != kNoRegister) {
83 blocked_cpu_registers_[TMP] = true; 83 blocked_cpu_registers_[TMP] = true;
84 } 84 }
85 blocked_cpu_registers_[SPREG] = true; 85 blocked_cpu_registers_[SPREG] = true;
86 blocked_cpu_registers_[FPREG] = true; 86 blocked_cpu_registers_[FPREG] = true;
87 87
88 // XMM0 is used as scratch by optimized code and parallel move resolver. 88 // FpuTMP is used as scratch by optimized code and parallel move resolver.
89 blocked_xmm_registers_[XMM0] = true; 89 blocked_fpu_registers_[FpuTMP] = true;
90 } 90 }
91 91
92 92
93 // Remove environments from the instructions which can't deoptimize. 93 // Remove environments from the instructions which can't deoptimize.
94 // Replace dead phis uses with null values in environments. 94 // Replace dead phis uses with null values in environments.
95 void FlowGraphAllocator::EliminateEnvironmentUses() { 95 void FlowGraphAllocator::EliminateEnvironmentUses() {
96 ConstantInstr* constant_null = 96 ConstantInstr* constant_null =
97 postorder_.Last()->AsGraphEntry()->constant_null(); 97 postorder_.Last()->AsGraphEntry()->constant_null();
98 for (intptr_t i = 0; i < block_order_.length(); ++i) { 98 for (intptr_t i = 0; i < block_order_.length(); ++i) {
99 BlockEntryInstr* block = block_order_[i]; 99 BlockEntryInstr* block = block_order_[i];
(...skipping 342 matching lines...) Expand 10 before | Expand all | Expand 10 after
442 blocking_ranges[loc.register_code()]->AddUseInterval(from, to); 442 blocking_ranges[loc.register_code()]->AddUseInterval(from, to);
443 } 443 }
444 444
445 445
446 // Block location from the start of the instruction to its end. 446 // Block location from the start of the instruction to its end.
447 void FlowGraphAllocator::BlockLocation(Location loc, 447 void FlowGraphAllocator::BlockLocation(Location loc,
448 intptr_t from, 448 intptr_t from,
449 intptr_t to) { 449 intptr_t to) {
450 if (loc.IsRegister()) { 450 if (loc.IsRegister()) {
451 BlockRegisterLocation(loc, from, to, blocked_cpu_registers_, cpu_regs_); 451 BlockRegisterLocation(loc, from, to, blocked_cpu_registers_, cpu_regs_);
452 } else if (loc.IsXmmRegister()) { 452 } else if (loc.IsFpuRegister()) {
453 BlockRegisterLocation(loc, from, to, blocked_xmm_registers_, xmm_regs_); 453 BlockRegisterLocation(loc, from, to, blocked_fpu_registers_, fpu_regs_);
454 } else { 454 } else {
455 UNREACHABLE(); 455 UNREACHABLE();
456 } 456 }
457 } 457 }
458 458
459 459
460 void LiveRange::Print() { 460 void LiveRange::Print() {
461 if (first_use_interval() == NULL) { 461 if (first_use_interval() == NULL) {
462 return; 462 return;
463 } 463 }
(...skipping 158 matching lines...) Expand 10 before | Expand all | Expand 10 after
622 ConvertAllUses(range); 622 ConvertAllUses(range);
623 623
624 if (defn->IsParameter() && flow_graph_.num_copied_params() > 0) { 624 if (defn->IsParameter() && flow_graph_.num_copied_params() > 0) {
625 MarkAsObjectAtSafepoints(range); 625 MarkAsObjectAtSafepoints(range);
626 } 626 }
627 } 627 }
628 } 628 }
629 629
630 630
631 static Location::Kind RegisterKindFromPolicy(Location loc) { 631 static Location::Kind RegisterKindFromPolicy(Location loc) {
632 if (loc.policy() == Location::kRequiresXmmRegister) { 632 if (loc.policy() == Location::kRequiresFpuRegister) {
633 return Location::kXmmRegister; 633 return Location::kFpuRegister;
634 } else { 634 } else {
635 return Location::kRegister; 635 return Location::kRegister;
636 } 636 }
637 } 637 }
638 638
639 639
640 static Location::Kind RegisterKindForResult(Instruction* instr) { 640 static Location::Kind RegisterKindForResult(Instruction* instr) {
641 if ((instr->representation() == kUnboxedDouble) || 641 if ((instr->representation() == kUnboxedDouble) ||
642 (instr->representation() == kUnboxedMint)) { 642 (instr->representation() == kUnboxedMint)) {
643 return Location::kXmmRegister; 643 return Location::kFpuRegister;
644 } else { 644 } else {
645 return Location::kRegister; 645 return Location::kRegister;
646 } 646 }
647 } 647 }
648 648
649 649
650 // 650 //
651 // When describing shape of live ranges in comments below we are going to use 651 // When describing shape of live ranges in comments below we are going to use
652 // the following notation: 652 // the following notation:
653 // 653 //
(...skipping 317 matching lines...) Expand 10 before | Expand all | Expand 10 after
971 // i i' 971 // i i'
972 // [--) 972 // [--)
973 // 973 //
974 // The stack bitmap describes the position i. 974 // The stack bitmap describes the position i.
975 for (intptr_t reg = 0; reg < kNumberOfCpuRegisters; reg++) { 975 for (intptr_t reg = 0; reg < kNumberOfCpuRegisters; reg++) {
976 BlockLocation(Location::RegisterLocation(static_cast<Register>(reg)), 976 BlockLocation(Location::RegisterLocation(static_cast<Register>(reg)),
977 pos, 977 pos,
978 pos + 1); 978 pos + 1);
979 } 979 }
980 980
981 for (intptr_t reg = 0; reg < kNumberOfXmmRegisters; reg++) { 981 for (intptr_t reg = 0; reg < kNumberOfFpuRegisters; reg++) {
982 Location::Representation ignored = Location::kDouble; 982 Location::Representation ignored = Location::kDouble;
983 BlockLocation( 983 BlockLocation(
984 Location::XmmRegisterLocation(static_cast<XmmRegister>(reg), ignored), 984 Location::FpuRegisterLocation(static_cast<FpuRegister>(reg), ignored),
985 pos, 985 pos,
986 pos + 1); 986 pos + 1);
987 } 987 }
988 988
989 989
990 #if defined(DEBUG) 990 #if defined(DEBUG)
991 // Verify that temps, inputs and output were specified as fixed 991 // Verify that temps, inputs and output were specified as fixed
992 // locations. Every register is blocked now so attempt to 992 // locations. Every register is blocked now so attempt to
993 // allocate will not succeed. 993 // allocate will not succeed.
994 for (intptr_t j = 0; j < locs->temp_count(); j++) { 994 for (intptr_t j = 0; j < locs->temp_count(); j++) {
(...skipping 67 matching lines...) Expand 10 before | Expand all | Expand 10 after
1062 range->AddHintedUse(pos + 1, move->dest_slot(), out); 1062 range->AddHintedUse(pos + 1, move->dest_slot(), out);
1063 } else if (output_same_as_first_input) { 1063 } else if (output_same_as_first_input) {
1064 // Output register will contain a value of the first input at instruction's 1064 // Output register will contain a value of the first input at instruction's
1065 // start. Expected shape of live ranges: 1065 // start. Expected shape of live ranges:
1066 // 1066 //
1067 // i i' 1067 // i i'
1068 // input #0 --* 1068 // input #0 --*
1069 // output [---- 1069 // output [----
1070 // 1070 //
1071 ASSERT(locs->in(0).Equals(Location::RequiresRegister()) || 1071 ASSERT(locs->in(0).Equals(Location::RequiresRegister()) ||
1072 locs->in(0).Equals(Location::RequiresXmmRegister())); 1072 locs->in(0).Equals(Location::RequiresFpuRegister()));
1073 1073
1074 // Create move that will copy value between input and output. 1074 // Create move that will copy value between input and output.
1075 locs->set_out(Location::RequiresRegister()); 1075 locs->set_out(Location::RequiresRegister());
1076 MoveOperands* move = AddMoveAt(pos, 1076 MoveOperands* move = AddMoveAt(pos,
1077 Location::RequiresRegister(), 1077 Location::RequiresRegister(),
1078 Location::Any()); 1078 Location::Any());
1079 1079
1080 // Add uses to the live range of the input. 1080 // Add uses to the live range of the input.
1081 Definition* input = current->InputAt(0)->definition(); 1081 Definition* input = current->InputAt(0)->definition();
1082 LiveRange* input_range = 1082 LiveRange* input_range =
(...skipping 14 matching lines...) Expand all
1097 interference_set->Add(input->ssa_temp_index()); 1097 interference_set->Add(input->ssa_temp_index());
1098 } 1098 }
1099 } else { 1099 } else {
1100 // Normal unallocated location that requires a register. Expected shape of 1100 // Normal unallocated location that requires a register. Expected shape of
1101 // live range: 1101 // live range:
1102 // 1102 //
1103 // i i' 1103 // i i'
1104 // output [------- 1104 // output [-------
1105 // 1105 //
1106 ASSERT(locs->out().Equals(Location::RequiresRegister()) || 1106 ASSERT(locs->out().Equals(Location::RequiresRegister()) ||
1107 locs->out().Equals(Location::RequiresXmmRegister())); 1107 locs->out().Equals(Location::RequiresFpuRegister()));
1108 1108
1109 // Shorten live range to the point of definition and add use to be filled by 1109 // Shorten live range to the point of definition and add use to be filled by
1110 // allocator. 1110 // allocator.
1111 range->DefineAt(pos); 1111 range->DefineAt(pos);
1112 range->AddUse(pos, out); 1112 range->AddUse(pos, out);
1113 } 1113 }
1114 1114
1115 AssignSafepoints(range); 1115 AssignSafepoints(range);
1116 CompleteRange(range, RegisterKindForResult(current)); 1116 CompleteRange(range, RegisterKindForResult(current));
1117 } 1117 }
(...skipping 190 matching lines...) Expand 10 before | Expand all | Expand 10 after
1308 } 1308 }
1309 1309
1310 1310
1311 UsePosition* AllocationFinger::FirstRegisterUse(intptr_t after) { 1311 UsePosition* AllocationFinger::FirstRegisterUse(intptr_t after) {
1312 for (UsePosition* use = FirstUseAfter(first_register_use_, after); 1312 for (UsePosition* use = FirstUseAfter(first_register_use_, after);
1313 use != NULL; 1313 use != NULL;
1314 use = use->next()) { 1314 use = use->next()) {
1315 Location* loc = use->location_slot(); 1315 Location* loc = use->location_slot();
1316 if (loc->IsUnallocated() && 1316 if (loc->IsUnallocated() &&
1317 ((loc->policy() == Location::kRequiresRegister) || 1317 ((loc->policy() == Location::kRequiresRegister) ||
1318 (loc->policy() == Location::kRequiresXmmRegister))) { 1318 (loc->policy() == Location::kRequiresFpuRegister))) {
1319 first_register_use_ = use; 1319 first_register_use_ = use;
1320 return use; 1320 return use;
1321 } 1321 }
1322 } 1322 }
1323 return NULL; 1323 return NULL;
1324 } 1324 }
1325 1325
1326 1326
1327 UsePosition* AllocationFinger::FirstRegisterBeneficialUse(intptr_t after) { 1327 UsePosition* AllocationFinger::FirstRegisterBeneficialUse(intptr_t after) {
1328 for (UsePosition* use = FirstUseAfter(first_register_beneficial_use_, after); 1328 for (UsePosition* use = FirstUseAfter(first_register_beneficial_use_, after);
(...skipping 412 matching lines...) Expand 10 before | Expand all | Expand 10 after
1741 1741
1742 // We have a very good candidate (either hinted to us or completely free). 1742 // We have a very good candidate (either hinted to us or completely free).
1743 // If we are in a loop try to reduce number of moves on the back edge by 1743 // If we are in a loop try to reduce number of moves on the back edge by
1744 // searching for a candidate that does not interfere with phis on the back 1744 // searching for a candidate that does not interfere with phis on the back
1745 // edge. 1745 // edge.
1746 BlockInfo* loop_header = BlockInfoAt(unallocated->Start())->loop_header(); 1746 BlockInfo* loop_header = BlockInfoAt(unallocated->Start())->loop_header();
1747 if ((unallocated->vreg() >= 0) && 1747 if ((unallocated->vreg() >= 0) &&
1748 (loop_header != NULL) && 1748 (loop_header != NULL) &&
1749 (free_until >= loop_header->last_block()->end_pos()) && 1749 (free_until >= loop_header->last_block()->end_pos()) &&
1750 loop_header->backedge_interference()->Contains(unallocated->vreg())) { 1750 loop_header->backedge_interference()->Contains(unallocated->vreg())) {
1751 ASSERT(static_cast<intptr_t>(kNumberOfXmmRegisters) <= 1751 ASSERT(static_cast<intptr_t>(kNumberOfFpuRegisters) <=
1752 kNumberOfCpuRegisters); 1752 kNumberOfCpuRegisters);
1753 bool used_on_backedge[kNumberOfCpuRegisters] = { false }; 1753 bool used_on_backedge[kNumberOfCpuRegisters] = { false };
1754 1754
1755 for (PhiIterator it(loop_header->entry()->AsJoinEntry()); 1755 for (PhiIterator it(loop_header->entry()->AsJoinEntry());
1756 !it.Done(); 1756 !it.Done();
1757 it.Advance()) { 1757 it.Advance()) {
1758 PhiInstr* phi = it.Current(); 1758 PhiInstr* phi = it.Current();
1759 if (phi->is_alive()) { 1759 if (phi->is_alive()) {
1760 const intptr_t phi_vreg = phi->ssa_temp_index(); 1760 const intptr_t phi_vreg = phi->ssa_temp_index();
1761 LiveRange* range = GetLiveRange(phi_vreg); 1761 LiveRange* range = GetLiveRange(phi_vreg);
(...skipping 430 matching lines...) Expand 10 before | Expand all | Expand 10 after
2192 AddToSortedListOfRanges(&unallocated_, range); 2192 AddToSortedListOfRanges(&unallocated_, range);
2193 } 2193 }
2194 2194
2195 2195
2196 void FlowGraphAllocator::CompleteRange(LiveRange* range, Location::Kind kind) { 2196 void FlowGraphAllocator::CompleteRange(LiveRange* range, Location::Kind kind) {
2197 switch (kind) { 2197 switch (kind) {
2198 case Location::kRegister: 2198 case Location::kRegister:
2199 AddToSortedListOfRanges(&unallocated_cpu_, range); 2199 AddToSortedListOfRanges(&unallocated_cpu_, range);
2200 break; 2200 break;
2201 2201
2202 case Location::kXmmRegister: 2202 case Location::kFpuRegister:
2203 AddToSortedListOfRanges(&unallocated_xmm_, range); 2203 AddToSortedListOfRanges(&unallocated_xmm_, range);
2204 break; 2204 break;
2205 2205
2206 default: 2206 default:
2207 UNREACHABLE(); 2207 UNREACHABLE();
2208 } 2208 }
2209 } 2209 }
2210 2210
2211 2211
2212 #if defined(DEBUG) 2212 #if defined(DEBUG)
(...skipping 263 matching lines...) Expand 10 before | Expand all | Expand 10 after
2476 PrepareForAllocation(Location::kRegister, 2476 PrepareForAllocation(Location::kRegister,
2477 kNumberOfCpuRegisters, 2477 kNumberOfCpuRegisters,
2478 unallocated_cpu_, 2478 unallocated_cpu_,
2479 cpu_regs_, 2479 cpu_regs_,
2480 blocked_cpu_registers_); 2480 blocked_cpu_registers_);
2481 AllocateUnallocatedRanges(); 2481 AllocateUnallocatedRanges();
2482 2482
2483 cpu_spill_slot_count_ = spill_slots_.length(); 2483 cpu_spill_slot_count_ = spill_slots_.length();
2484 spill_slots_.Clear(); 2484 spill_slots_.Clear();
2485 2485
2486 PrepareForAllocation(Location::kXmmRegister, 2486 PrepareForAllocation(Location::kFpuRegister,
2487 kNumberOfXmmRegisters, 2487 kNumberOfFpuRegisters,
2488 unallocated_xmm_, 2488 unallocated_xmm_,
2489 xmm_regs_, 2489 fpu_regs_,
2490 blocked_xmm_registers_); 2490 blocked_fpu_registers_);
2491 AllocateUnallocatedRanges(); 2491 AllocateUnallocatedRanges();
2492 2492
2493 ResolveControlFlow(); 2493 ResolveControlFlow();
2494 2494
2495 GraphEntryInstr* entry = block_order_[0]->AsGraphEntry(); 2495 GraphEntryInstr* entry = block_order_[0]->AsGraphEntry();
2496 ASSERT(entry != NULL); 2496 ASSERT(entry != NULL);
2497 intptr_t double_spill_slot_count = 2497 intptr_t double_spill_slot_count =
2498 spill_slots_.length() * kDoubleSpillSlotFactor; 2498 spill_slots_.length() * kDoubleSpillSlotFactor;
2499 entry->set_spill_slot_count(cpu_spill_slot_count_ + double_spill_slot_count); 2499 entry->set_spill_slot_count(cpu_spill_slot_count_ + double_spill_slot_count);
2500 2500
2501 if (FLAG_print_ssa_liveranges) { 2501 if (FLAG_print_ssa_liveranges) {
2502 const Function& function = flow_graph_.parsed_function().function(); 2502 const Function& function = flow_graph_.parsed_function().function();
2503 2503
2504 OS::Print("-- [after ssa allocator] ranges [%s] ---------\n", 2504 OS::Print("-- [after ssa allocator] ranges [%s] ---------\n",
2505 function.ToFullyQualifiedCString()); 2505 function.ToFullyQualifiedCString());
2506 PrintLiveRanges(); 2506 PrintLiveRanges();
2507 OS::Print("----------------------------------------------\n"); 2507 OS::Print("----------------------------------------------\n");
2508 2508
2509 OS::Print("-- [after ssa allocator] ir [%s] -------------\n", 2509 OS::Print("-- [after ssa allocator] ir [%s] -------------\n",
2510 function.ToFullyQualifiedCString()); 2510 function.ToFullyQualifiedCString());
2511 FlowGraphPrinter printer(flow_graph_, true); 2511 FlowGraphPrinter printer(flow_graph_, true);
2512 printer.PrintBlocks(); 2512 printer.PrintBlocks();
2513 OS::Print("----------------------------------------------\n"); 2513 OS::Print("----------------------------------------------\n");
2514 } 2514 }
2515 } 2515 }
2516 2516
2517 2517
2518 } // namespace dart 2518 } // namespace dart
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698