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