| 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 |