OLD | NEW |
1 // Copyright 2012 the V8 project authors. All rights reserved. | 1 // Copyright 2012 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 1083 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1094 if (!AllocationOk()) return false; | 1094 if (!AllocationOk()) return false; |
1095 PopulatePointerMaps(); | 1095 PopulatePointerMaps(); |
1096 if (has_osr_entry_) ProcessOsrEntry(); | 1096 if (has_osr_entry_) ProcessOsrEntry(); |
1097 ConnectRanges(); | 1097 ConnectRanges(); |
1098 ResolveControlFlow(); | 1098 ResolveControlFlow(); |
1099 return true; | 1099 return true; |
1100 } | 1100 } |
1101 | 1101 |
1102 | 1102 |
1103 void LAllocator::MeetRegisterConstraints() { | 1103 void LAllocator::MeetRegisterConstraints() { |
1104 HPhase phase("L_Register constraints", chunk_); | 1104 LPhase phase("L_Register constraints", chunk_); |
1105 first_artificial_register_ = next_virtual_register_; | 1105 first_artificial_register_ = next_virtual_register_; |
1106 const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); | 1106 const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); |
1107 for (int i = 0; i < blocks->length(); ++i) { | 1107 for (int i = 0; i < blocks->length(); ++i) { |
1108 HBasicBlock* block = blocks->at(i); | 1108 HBasicBlock* block = blocks->at(i); |
1109 MeetRegisterConstraints(block); | 1109 MeetRegisterConstraints(block); |
1110 if (!AllocationOk()) return; | 1110 if (!AllocationOk()) return; |
1111 } | 1111 } |
1112 } | 1112 } |
1113 | 1113 |
1114 | 1114 |
1115 void LAllocator::ResolvePhis() { | 1115 void LAllocator::ResolvePhis() { |
1116 HPhase phase("L_Resolve phis", chunk_); | 1116 LPhase phase("L_Resolve phis", chunk_); |
1117 | 1117 |
1118 // Process the blocks in reverse order. | 1118 // Process the blocks in reverse order. |
1119 const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); | 1119 const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); |
1120 for (int block_id = blocks->length() - 1; block_id >= 0; --block_id) { | 1120 for (int block_id = blocks->length() - 1; block_id >= 0; --block_id) { |
1121 HBasicBlock* block = blocks->at(block_id); | 1121 HBasicBlock* block = blocks->at(block_id); |
1122 ResolvePhis(block); | 1122 ResolvePhis(block); |
1123 } | 1123 } |
1124 } | 1124 } |
1125 | 1125 |
1126 | 1126 |
(...skipping 70 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1197 } | 1197 } |
1198 | 1198 |
1199 | 1199 |
1200 HBasicBlock* LAllocator::GetBlock(LifetimePosition pos) { | 1200 HBasicBlock* LAllocator::GetBlock(LifetimePosition pos) { |
1201 LGap* gap = GapAt(chunk_->NearestGapPos(pos.InstructionIndex())); | 1201 LGap* gap = GapAt(chunk_->NearestGapPos(pos.InstructionIndex())); |
1202 return gap->block(); | 1202 return gap->block(); |
1203 } | 1203 } |
1204 | 1204 |
1205 | 1205 |
1206 void LAllocator::ConnectRanges() { | 1206 void LAllocator::ConnectRanges() { |
1207 HPhase phase("L_Connect ranges", this); | 1207 LPhase phase("L_Connect ranges", this); |
1208 for (int i = 0; i < live_ranges()->length(); ++i) { | 1208 for (int i = 0; i < live_ranges()->length(); ++i) { |
1209 LiveRange* first_range = live_ranges()->at(i); | 1209 LiveRange* first_range = live_ranges()->at(i); |
1210 if (first_range == NULL || first_range->parent() != NULL) continue; | 1210 if (first_range == NULL || first_range->parent() != NULL) continue; |
1211 | 1211 |
1212 LiveRange* second_range = first_range->next(); | 1212 LiveRange* second_range = first_range->next(); |
1213 while (second_range != NULL) { | 1213 while (second_range != NULL) { |
1214 LifetimePosition pos = second_range->Start(); | 1214 LifetimePosition pos = second_range->Start(); |
1215 | 1215 |
1216 if (!second_range->IsSpilled()) { | 1216 if (!second_range->IsSpilled()) { |
1217 // Add gap move if the two live ranges touch and there is no block | 1217 // Add gap move if the two live ranges touch and there is no block |
(...skipping 19 matching lines...) Expand all Loading... |
1237 } | 1237 } |
1238 | 1238 |
1239 | 1239 |
1240 bool LAllocator::CanEagerlyResolveControlFlow(HBasicBlock* block) const { | 1240 bool LAllocator::CanEagerlyResolveControlFlow(HBasicBlock* block) const { |
1241 if (block->predecessors()->length() != 1) return false; | 1241 if (block->predecessors()->length() != 1) return false; |
1242 return block->predecessors()->first()->block_id() == block->block_id() - 1; | 1242 return block->predecessors()->first()->block_id() == block->block_id() - 1; |
1243 } | 1243 } |
1244 | 1244 |
1245 | 1245 |
1246 void LAllocator::ResolveControlFlow() { | 1246 void LAllocator::ResolveControlFlow() { |
1247 HPhase phase("L_Resolve control flow", this); | 1247 LPhase phase("L_Resolve control flow", this); |
1248 const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); | 1248 const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); |
1249 for (int block_id = 1; block_id < blocks->length(); ++block_id) { | 1249 for (int block_id = 1; block_id < blocks->length(); ++block_id) { |
1250 HBasicBlock* block = blocks->at(block_id); | 1250 HBasicBlock* block = blocks->at(block_id); |
1251 if (CanEagerlyResolveControlFlow(block)) continue; | 1251 if (CanEagerlyResolveControlFlow(block)) continue; |
1252 BitVector* live = live_in_sets_[block->block_id()]; | 1252 BitVector* live = live_in_sets_[block->block_id()]; |
1253 BitVector::Iterator iterator(live); | 1253 BitVector::Iterator iterator(live); |
1254 while (!iterator.Done()) { | 1254 while (!iterator.Done()) { |
1255 int operand_index = iterator.Current(); | 1255 int operand_index = iterator.Current(); |
1256 for (int i = 0; i < block->predecessors()->length(); ++i) { | 1256 for (int i = 0; i < block->predecessors()->length(); ++i) { |
1257 HBasicBlock* cur = block->predecessors()->at(i); | 1257 HBasicBlock* cur = block->predecessors()->at(i); |
1258 LiveRange* cur_range = LiveRangeFor(operand_index); | 1258 LiveRange* cur_range = LiveRangeFor(operand_index); |
1259 ResolveControlFlow(cur_range, block, cur); | 1259 ResolveControlFlow(cur_range, block, cur); |
1260 } | 1260 } |
1261 iterator.Advance(); | 1261 iterator.Advance(); |
1262 } | 1262 } |
1263 } | 1263 } |
1264 } | 1264 } |
1265 | 1265 |
1266 | 1266 |
1267 void LAllocator::BuildLiveRanges() { | 1267 void LAllocator::BuildLiveRanges() { |
1268 HPhase phase("L_Build live ranges", this); | 1268 LPhase phase("L_Build live ranges", this); |
1269 InitializeLivenessAnalysis(); | 1269 InitializeLivenessAnalysis(); |
1270 // Process the blocks in reverse order. | 1270 // Process the blocks in reverse order. |
1271 const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); | 1271 const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); |
1272 for (int block_id = blocks->length() - 1; block_id >= 0; --block_id) { | 1272 for (int block_id = blocks->length() - 1; block_id >= 0; --block_id) { |
1273 HBasicBlock* block = blocks->at(block_id); | 1273 HBasicBlock* block = blocks->at(block_id); |
1274 BitVector* live = ComputeLiveOut(block); | 1274 BitVector* live = ComputeLiveOut(block); |
1275 // Initially consider all live_out values live for the entire block. We | 1275 // Initially consider all live_out values live for the entire block. We |
1276 // will shorten these intervals if necessary. | 1276 // will shorten these intervals if necessary. |
1277 AddInitialIntervals(block, live); | 1277 AddInitialIntervals(block, live); |
1278 | 1278 |
(...skipping 91 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1370 for (int i = 0; i < pointer_maps->length(); ++i) { | 1370 for (int i = 0; i < pointer_maps->length(); ++i) { |
1371 LPointerMap* map = pointer_maps->at(i); | 1371 LPointerMap* map = pointer_maps->at(i); |
1372 if (safe_point > map->lithium_position()) return false; | 1372 if (safe_point > map->lithium_position()) return false; |
1373 safe_point = map->lithium_position(); | 1373 safe_point = map->lithium_position(); |
1374 } | 1374 } |
1375 return true; | 1375 return true; |
1376 } | 1376 } |
1377 | 1377 |
1378 | 1378 |
1379 void LAllocator::PopulatePointerMaps() { | 1379 void LAllocator::PopulatePointerMaps() { |
1380 HPhase phase("L_Populate pointer maps", this); | 1380 LPhase phase("L_Populate pointer maps", this); |
1381 const ZoneList<LPointerMap*>* pointer_maps = chunk_->pointer_maps(); | 1381 const ZoneList<LPointerMap*>* pointer_maps = chunk_->pointer_maps(); |
1382 | 1382 |
1383 ASSERT(SafePointsAreInOrder()); | 1383 ASSERT(SafePointsAreInOrder()); |
1384 | 1384 |
1385 // Iterate over all safe point positions and record a pointer | 1385 // Iterate over all safe point positions and record a pointer |
1386 // for all spilled live ranges at this point. | 1386 // for all spilled live ranges at this point. |
1387 int first_safe_point_index = 0; | 1387 int first_safe_point_index = 0; |
1388 int last_range_start = 0; | 1388 int last_range_start = 0; |
1389 for (int range_idx = 0; range_idx < live_ranges()->length(); ++range_idx) { | 1389 for (int range_idx = 0; range_idx < live_ranges()->length(); ++range_idx) { |
1390 LiveRange* range = live_ranges()->at(range_idx); | 1390 LiveRange* range = live_ranges()->at(range_idx); |
(...skipping 98 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1489 } else { | 1489 } else { |
1490 instruction->MarkSpilledRegister(reg_index, spill_operand); | 1490 instruction->MarkSpilledRegister(reg_index, spill_operand); |
1491 } | 1491 } |
1492 } | 1492 } |
1493 } | 1493 } |
1494 } | 1494 } |
1495 } | 1495 } |
1496 | 1496 |
1497 | 1497 |
1498 void LAllocator::AllocateGeneralRegisters() { | 1498 void LAllocator::AllocateGeneralRegisters() { |
1499 HPhase phase("L_Allocate general registers", this); | 1499 LPhase phase("L_Allocate general registers", this); |
1500 num_registers_ = Register::NumAllocatableRegisters(); | 1500 num_registers_ = Register::NumAllocatableRegisters(); |
1501 AllocateRegisters(); | 1501 AllocateRegisters(); |
1502 } | 1502 } |
1503 | 1503 |
1504 | 1504 |
1505 void LAllocator::AllocateDoubleRegisters() { | 1505 void LAllocator::AllocateDoubleRegisters() { |
1506 HPhase phase("L_Allocate double registers", this); | 1506 LPhase phase("L_Allocate double registers", this); |
1507 num_registers_ = DoubleRegister::NumAllocatableRegisters(); | 1507 num_registers_ = DoubleRegister::NumAllocatableRegisters(); |
1508 mode_ = DOUBLE_REGISTERS; | 1508 mode_ = DOUBLE_REGISTERS; |
1509 AllocateRegisters(); | 1509 AllocateRegisters(); |
1510 } | 1510 } |
1511 | 1511 |
1512 | 1512 |
1513 void LAllocator::AllocateRegisters() { | 1513 void LAllocator::AllocateRegisters() { |
1514 ASSERT(unhandled_live_ranges_.is_empty()); | 1514 ASSERT(unhandled_live_ranges_.is_empty()); |
1515 | 1515 |
1516 for (int i = 0; i < live_ranges_.length(); ++i) { | 1516 for (int i = 0; i < live_ranges_.length(); ++i) { |
(...skipping 669 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2186 LiveRange* current = live_ranges()->at(i); | 2186 LiveRange* current = live_ranges()->at(i); |
2187 if (current != NULL) current->Verify(); | 2187 if (current != NULL) current->Verify(); |
2188 } | 2188 } |
2189 } | 2189 } |
2190 | 2190 |
2191 | 2191 |
2192 #endif | 2192 #endif |
2193 | 2193 |
2194 | 2194 |
2195 } } // namespace v8::internal | 2195 } } // namespace v8::internal |
OLD | NEW |