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 1087 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1098 if (!AllocationOk()) return false; | 1098 if (!AllocationOk()) return false; |
1099 PopulatePointerMaps(); | 1099 PopulatePointerMaps(); |
1100 if (has_osr_entry_) ProcessOsrEntry(); | 1100 if (has_osr_entry_) ProcessOsrEntry(); |
1101 ConnectRanges(); | 1101 ConnectRanges(); |
1102 ResolveControlFlow(); | 1102 ResolveControlFlow(); |
1103 return true; | 1103 return true; |
1104 } | 1104 } |
1105 | 1105 |
1106 | 1106 |
1107 void LAllocator::MeetRegisterConstraints() { | 1107 void LAllocator::MeetRegisterConstraints() { |
1108 HPhase phase("L Register constraints", chunk_); | 1108 HPhase phase("L_Register constraints", chunk_); |
1109 first_artificial_register_ = next_virtual_register_; | 1109 first_artificial_register_ = next_virtual_register_; |
1110 const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); | 1110 const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); |
1111 for (int i = 0; i < blocks->length(); ++i) { | 1111 for (int i = 0; i < blocks->length(); ++i) { |
1112 HBasicBlock* block = blocks->at(i); | 1112 HBasicBlock* block = blocks->at(i); |
1113 MeetRegisterConstraints(block); | 1113 MeetRegisterConstraints(block); |
1114 if (!AllocationOk()) return; | 1114 if (!AllocationOk()) return; |
1115 } | 1115 } |
1116 } | 1116 } |
1117 | 1117 |
1118 | 1118 |
1119 void LAllocator::ResolvePhis() { | 1119 void LAllocator::ResolvePhis() { |
1120 HPhase phase("L Resolve phis", chunk_); | 1120 HPhase phase("L_Resolve phis", chunk_); |
1121 | 1121 |
1122 // Process the blocks in reverse order. | 1122 // Process the blocks in reverse order. |
1123 const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); | 1123 const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); |
1124 for (int block_id = blocks->length() - 1; block_id >= 0; --block_id) { | 1124 for (int block_id = blocks->length() - 1; block_id >= 0; --block_id) { |
1125 HBasicBlock* block = blocks->at(block_id); | 1125 HBasicBlock* block = blocks->at(block_id); |
1126 ResolvePhis(block); | 1126 ResolvePhis(block); |
1127 } | 1127 } |
1128 } | 1128 } |
1129 | 1129 |
1130 | 1130 |
(...skipping 69 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1200 } | 1200 } |
1201 | 1201 |
1202 | 1202 |
1203 HBasicBlock* LAllocator::GetBlock(LifetimePosition pos) { | 1203 HBasicBlock* LAllocator::GetBlock(LifetimePosition pos) { |
1204 LGap* gap = GapAt(chunk_->NearestGapPos(pos.InstructionIndex())); | 1204 LGap* gap = GapAt(chunk_->NearestGapPos(pos.InstructionIndex())); |
1205 return gap->block(); | 1205 return gap->block(); |
1206 } | 1206 } |
1207 | 1207 |
1208 | 1208 |
1209 void LAllocator::ConnectRanges() { | 1209 void LAllocator::ConnectRanges() { |
1210 HPhase phase("L Connect ranges", this); | 1210 HPhase phase("L_Connect ranges", this); |
1211 for (int i = 0; i < live_ranges()->length(); ++i) { | 1211 for (int i = 0; i < live_ranges()->length(); ++i) { |
1212 LiveRange* first_range = live_ranges()->at(i); | 1212 LiveRange* first_range = live_ranges()->at(i); |
1213 if (first_range == NULL || first_range->parent() != NULL) continue; | 1213 if (first_range == NULL || first_range->parent() != NULL) continue; |
1214 | 1214 |
1215 LiveRange* second_range = first_range->next(); | 1215 LiveRange* second_range = first_range->next(); |
1216 while (second_range != NULL) { | 1216 while (second_range != NULL) { |
1217 LifetimePosition pos = second_range->Start(); | 1217 LifetimePosition pos = second_range->Start(); |
1218 | 1218 |
1219 if (!second_range->IsSpilled()) { | 1219 if (!second_range->IsSpilled()) { |
1220 // Add gap move if the two live ranges touch and there is no block | 1220 // Add gap move if the two live ranges touch and there is no block |
(...skipping 19 matching lines...) Expand all Loading... |
1240 } | 1240 } |
1241 | 1241 |
1242 | 1242 |
1243 bool LAllocator::CanEagerlyResolveControlFlow(HBasicBlock* block) const { | 1243 bool LAllocator::CanEagerlyResolveControlFlow(HBasicBlock* block) const { |
1244 if (block->predecessors()->length() != 1) return false; | 1244 if (block->predecessors()->length() != 1) return false; |
1245 return block->predecessors()->first()->block_id() == block->block_id() - 1; | 1245 return block->predecessors()->first()->block_id() == block->block_id() - 1; |
1246 } | 1246 } |
1247 | 1247 |
1248 | 1248 |
1249 void LAllocator::ResolveControlFlow() { | 1249 void LAllocator::ResolveControlFlow() { |
1250 HPhase phase("L Resolve control flow", this); | 1250 HPhase phase("L_Resolve control flow", this); |
1251 const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); | 1251 const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); |
1252 for (int block_id = 1; block_id < blocks->length(); ++block_id) { | 1252 for (int block_id = 1; block_id < blocks->length(); ++block_id) { |
1253 HBasicBlock* block = blocks->at(block_id); | 1253 HBasicBlock* block = blocks->at(block_id); |
1254 if (CanEagerlyResolveControlFlow(block)) continue; | 1254 if (CanEagerlyResolveControlFlow(block)) continue; |
1255 BitVector* live = live_in_sets_[block->block_id()]; | 1255 BitVector* live = live_in_sets_[block->block_id()]; |
1256 BitVector::Iterator iterator(live); | 1256 BitVector::Iterator iterator(live); |
1257 while (!iterator.Done()) { | 1257 while (!iterator.Done()) { |
1258 int operand_index = iterator.Current(); | 1258 int operand_index = iterator.Current(); |
1259 for (int i = 0; i < block->predecessors()->length(); ++i) { | 1259 for (int i = 0; i < block->predecessors()->length(); ++i) { |
1260 HBasicBlock* cur = block->predecessors()->at(i); | 1260 HBasicBlock* cur = block->predecessors()->at(i); |
1261 LiveRange* cur_range = LiveRangeFor(operand_index); | 1261 LiveRange* cur_range = LiveRangeFor(operand_index); |
1262 ResolveControlFlow(cur_range, block, cur); | 1262 ResolveControlFlow(cur_range, block, cur); |
1263 } | 1263 } |
1264 iterator.Advance(); | 1264 iterator.Advance(); |
1265 } | 1265 } |
1266 } | 1266 } |
1267 } | 1267 } |
1268 | 1268 |
1269 | 1269 |
1270 void LAllocator::BuildLiveRanges() { | 1270 void LAllocator::BuildLiveRanges() { |
1271 HPhase phase("L Build live ranges", this); | 1271 HPhase phase("L_Build live ranges", this); |
1272 InitializeLivenessAnalysis(); | 1272 InitializeLivenessAnalysis(); |
1273 // Process the blocks in reverse order. | 1273 // Process the blocks in reverse order. |
1274 const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); | 1274 const ZoneList<HBasicBlock*>* blocks = graph_->blocks(); |
1275 for (int block_id = blocks->length() - 1; block_id >= 0; --block_id) { | 1275 for (int block_id = blocks->length() - 1; block_id >= 0; --block_id) { |
1276 HBasicBlock* block = blocks->at(block_id); | 1276 HBasicBlock* block = blocks->at(block_id); |
1277 BitVector* live = ComputeLiveOut(block); | 1277 BitVector* live = ComputeLiveOut(block); |
1278 // Initially consider all live_out values live for the entire block. We | 1278 // Initially consider all live_out values live for the entire block. We |
1279 // will shorten these intervals if necessary. | 1279 // will shorten these intervals if necessary. |
1280 AddInitialIntervals(block, live); | 1280 AddInitialIntervals(block, live); |
1281 | 1281 |
(...skipping 84 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1366 for (int i = 0; i < pointer_maps->length(); ++i) { | 1366 for (int i = 0; i < pointer_maps->length(); ++i) { |
1367 LPointerMap* map = pointer_maps->at(i); | 1367 LPointerMap* map = pointer_maps->at(i); |
1368 if (safe_point > map->lithium_position()) return false; | 1368 if (safe_point > map->lithium_position()) return false; |
1369 safe_point = map->lithium_position(); | 1369 safe_point = map->lithium_position(); |
1370 } | 1370 } |
1371 return true; | 1371 return true; |
1372 } | 1372 } |
1373 | 1373 |
1374 | 1374 |
1375 void LAllocator::PopulatePointerMaps() { | 1375 void LAllocator::PopulatePointerMaps() { |
1376 HPhase phase("L Populate pointer maps", this); | 1376 HPhase phase("L_Populate pointer maps", this); |
1377 const ZoneList<LPointerMap*>* pointer_maps = chunk_->pointer_maps(); | 1377 const ZoneList<LPointerMap*>* pointer_maps = chunk_->pointer_maps(); |
1378 | 1378 |
1379 ASSERT(SafePointsAreInOrder()); | 1379 ASSERT(SafePointsAreInOrder()); |
1380 | 1380 |
1381 // Iterate over all safe point positions and record a pointer | 1381 // Iterate over all safe point positions and record a pointer |
1382 // for all spilled live ranges at this point. | 1382 // for all spilled live ranges at this point. |
1383 int first_safe_point_index = 0; | 1383 int first_safe_point_index = 0; |
1384 int last_range_start = 0; | 1384 int last_range_start = 0; |
1385 for (int range_idx = 0; range_idx < live_ranges()->length(); ++range_idx) { | 1385 for (int range_idx = 0; range_idx < live_ranges()->length(); ++range_idx) { |
1386 LiveRange* range = live_ranges()->at(range_idx); | 1386 LiveRange* range = live_ranges()->at(range_idx); |
(...skipping 98 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1485 } else { | 1485 } else { |
1486 instruction->MarkSpilledRegister(reg_index, spill_operand); | 1486 instruction->MarkSpilledRegister(reg_index, spill_operand); |
1487 } | 1487 } |
1488 } | 1488 } |
1489 } | 1489 } |
1490 } | 1490 } |
1491 } | 1491 } |
1492 | 1492 |
1493 | 1493 |
1494 void LAllocator::AllocateGeneralRegisters() { | 1494 void LAllocator::AllocateGeneralRegisters() { |
1495 HPhase phase("L Allocate general registers", this); | 1495 HPhase phase("L_Allocate general registers", this); |
1496 num_registers_ = Register::kNumAllocatableRegisters; | 1496 num_registers_ = Register::kNumAllocatableRegisters; |
1497 AllocateRegisters(); | 1497 AllocateRegisters(); |
1498 } | 1498 } |
1499 | 1499 |
1500 | 1500 |
1501 void LAllocator::AllocateDoubleRegisters() { | 1501 void LAllocator::AllocateDoubleRegisters() { |
1502 HPhase phase("L Allocate double registers", this); | 1502 HPhase phase("L_Allocate double registers", this); |
1503 num_registers_ = DoubleRegister::kNumAllocatableRegisters; | 1503 num_registers_ = DoubleRegister::kNumAllocatableRegisters; |
1504 mode_ = DOUBLE_REGISTERS; | 1504 mode_ = DOUBLE_REGISTERS; |
1505 AllocateRegisters(); | 1505 AllocateRegisters(); |
1506 } | 1506 } |
1507 | 1507 |
1508 | 1508 |
1509 void LAllocator::AllocateRegisters() { | 1509 void LAllocator::AllocateRegisters() { |
1510 ASSERT(unhandled_live_ranges_.is_empty()); | 1510 ASSERT(unhandled_live_ranges_.is_empty()); |
1511 | 1511 |
1512 for (int i = 0; i < live_ranges_.length(); ++i) { | 1512 for (int i = 0; i < live_ranges_.length(); ++i) { |
(...skipping 619 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2132 LiveRange* current = live_ranges()->at(i); | 2132 LiveRange* current = live_ranges()->at(i); |
2133 if (current != NULL) current->Verify(); | 2133 if (current != NULL) current->Verify(); |
2134 } | 2134 } |
2135 } | 2135 } |
2136 | 2136 |
2137 | 2137 |
2138 #endif | 2138 #endif |
2139 | 2139 |
2140 | 2140 |
2141 } } // namespace v8::internal | 2141 } } // namespace v8::internal |
OLD | NEW |