OLD | NEW |
1 // Copyright 2014 the V8 project authors. All rights reserved. | 1 // Copyright 2014 the V8 project authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "src/compiler/linkage.h" | 5 #include "src/compiler/linkage.h" |
6 #include "src/compiler/register-allocator.h" | 6 #include "src/compiler/register-allocator.h" |
7 #include "src/string-stream.h" | 7 #include "src/string-stream.h" |
8 | 8 |
9 namespace v8 { | 9 namespace v8 { |
10 namespace internal { | 10 namespace internal { |
(...skipping 82 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
93 return false; | 93 return false; |
94 } | 94 } |
95 | 95 |
96 | 96 |
97 #endif | 97 #endif |
98 | 98 |
99 | 99 |
100 LiveRange::LiveRange(int id, Zone* zone) | 100 LiveRange::LiveRange(int id, Zone* zone) |
101 : id_(id), | 101 : id_(id), |
102 spilled_(false), | 102 spilled_(false), |
| 103 is_phi_(false), |
| 104 is_non_loop_phi_(false), |
103 kind_(UNALLOCATED_REGISTERS), | 105 kind_(UNALLOCATED_REGISTERS), |
104 assigned_register_(kInvalidAssignment), | 106 assigned_register_(kInvalidAssignment), |
105 last_interval_(NULL), | 107 last_interval_(NULL), |
106 first_interval_(NULL), | 108 first_interval_(NULL), |
107 first_pos_(NULL), | 109 first_pos_(NULL), |
108 parent_(NULL), | 110 parent_(NULL), |
109 next_(NULL), | 111 next_(NULL), |
110 current_interval_(NULL), | 112 current_interval_(NULL), |
111 last_processed_use_(NULL), | 113 last_processed_use_(NULL), |
112 current_hint_operand_(NULL), | 114 current_hint_operand_(NULL), |
(...skipping 1043 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1156 gap->GetOrCreateParallelMove(GapInstruction::START, code_zone()); | 1158 gap->GetOrCreateParallelMove(GapInstruction::START, code_zone()); |
1157 const ZoneList<MoveOperands>* move_operands = move->move_operands(); | 1159 const ZoneList<MoveOperands>* move_operands = move->move_operands(); |
1158 for (int i = 0; i < move_operands->length(); ++i) { | 1160 for (int i = 0; i < move_operands->length(); ++i) { |
1159 MoveOperands* cur = &move_operands->at(i); | 1161 MoveOperands* cur = &move_operands->at(i); |
1160 if (cur->IsIgnored()) continue; | 1162 if (cur->IsIgnored()) continue; |
1161 InstructionOperand* from = cur->source(); | 1163 InstructionOperand* from = cur->source(); |
1162 InstructionOperand* to = cur->destination(); | 1164 InstructionOperand* to = cur->destination(); |
1163 InstructionOperand* hint = to; | 1165 InstructionOperand* hint = to; |
1164 if (to->IsUnallocated()) { | 1166 if (to->IsUnallocated()) { |
1165 int to_vreg = UnallocatedOperand::cast(to)->virtual_register(); | 1167 int to_vreg = UnallocatedOperand::cast(to)->virtual_register(); |
1166 if (live->Contains(to_vreg)) { | 1168 LiveRange* to_range = LiveRangeFor(to_vreg); |
1167 Define(curr_position, to, from); | 1169 if (to_range->is_phi()) { |
1168 live->Remove(to_vreg); | 1170 DCHECK(!FLAG_turbo_delay_ssa_decon); |
| 1171 if (to_range->is_non_loop_phi()) { |
| 1172 hint = to_range->current_hint_operand(); |
| 1173 } |
1169 } else { | 1174 } else { |
1170 cur->Eliminate(); | 1175 if (live->Contains(to_vreg)) { |
1171 continue; | 1176 Define(curr_position, to, from); |
| 1177 live->Remove(to_vreg); |
| 1178 } else { |
| 1179 cur->Eliminate(); |
| 1180 continue; |
| 1181 } |
1172 } | 1182 } |
1173 } else { | 1183 } else { |
1174 Define(curr_position, to, from); | 1184 Define(curr_position, to, from); |
1175 } | 1185 } |
1176 Use(block_start_position, curr_position, from, hint); | 1186 Use(block_start_position, curr_position, from, hint); |
1177 if (from->IsUnallocated()) { | 1187 if (from->IsUnallocated()) { |
1178 live->Add(UnallocatedOperand::cast(from)->virtual_register()); | 1188 live->Add(UnallocatedOperand::cast(from)->virtual_register()); |
1179 } | 1189 } |
1180 } | 1190 } |
1181 } else { | 1191 } else { |
(...skipping 59 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1241 } | 1251 } |
1242 } | 1252 } |
1243 Use(block_start_position, curr_position.InstructionEnd(), temp, NULL); | 1253 Use(block_start_position, curr_position.InstructionEnd(), temp, NULL); |
1244 Define(curr_position, temp, NULL); | 1254 Define(curr_position, temp, NULL); |
1245 } | 1255 } |
1246 } | 1256 } |
1247 } | 1257 } |
1248 } | 1258 } |
1249 | 1259 |
1250 | 1260 |
1251 void RegisterAllocator::ProcessPhis(const InstructionBlock* block) { | 1261 void RegisterAllocator::ResolvePhis(const InstructionBlock* block) { |
1252 for (auto phi : block->phis()) { | 1262 for (auto phi : block->phis()) { |
1253 auto output = phi->output(); | 1263 auto output = phi->output(); |
1254 int phi_vreg = phi->virtual_register(); | 1264 int phi_vreg = phi->virtual_register(); |
| 1265 if (!FLAG_turbo_delay_ssa_decon) { |
| 1266 for (size_t i = 0; i < phi->operands().size(); ++i) { |
| 1267 InstructionBlock* cur_block = |
| 1268 code()->InstructionBlockAt(block->predecessors()[i]); |
| 1269 // The gap move must be added without any special processing as in |
| 1270 // the AddConstraintsGapMove. |
| 1271 code()->AddGapMove(cur_block->last_instruction_index() - 1, |
| 1272 phi->inputs()[i], output); |
| 1273 DCHECK(!InstructionAt(cur_block->last_instruction_index()) |
| 1274 ->HasPointerMap()); |
| 1275 } |
| 1276 } |
1255 LiveRange* live_range = LiveRangeFor(phi_vreg); | 1277 LiveRange* live_range = LiveRangeFor(phi_vreg); |
1256 BlockStartInstruction* block_start = | 1278 BlockStartInstruction* block_start = |
1257 code()->GetBlockStart(block->rpo_number()); | 1279 code()->GetBlockStart(block->rpo_number()); |
1258 block_start->GetOrCreateParallelMove(GapInstruction::BEFORE, code_zone()) | 1280 block_start->GetOrCreateParallelMove(GapInstruction::BEFORE, code_zone()) |
1259 ->AddMove(output, live_range->GetSpillOperand(), code_zone()); | 1281 ->AddMove(output, live_range->GetSpillOperand(), code_zone()); |
1260 live_range->SetSpillStartIndex(block->first_instruction_index()); | 1282 live_range->SetSpillStartIndex(block->first_instruction_index()); |
| 1283 // We use the phi-ness of some nodes in some later heuristics. |
| 1284 live_range->set_is_phi(true); |
| 1285 if (!block->IsLoopHeader()) { |
| 1286 live_range->set_is_non_loop_phi(true); |
| 1287 } |
1261 } | 1288 } |
1262 } | 1289 } |
1263 | 1290 |
1264 | 1291 |
1265 void RegisterAllocator::MeetRegisterConstraints() { | 1292 void RegisterAllocator::MeetRegisterConstraints() { |
1266 for (auto block : code()->instruction_blocks()) { | 1293 for (auto block : code()->instruction_blocks()) { |
1267 ProcessPhis(block); | |
1268 MeetRegisterConstraints(block); | 1294 MeetRegisterConstraints(block); |
1269 } | 1295 } |
1270 } | 1296 } |
1271 | 1297 |
1272 | 1298 |
| 1299 void RegisterAllocator::ResolvePhis() { |
| 1300 // Process the blocks in reverse order. |
| 1301 for (auto i = code()->instruction_blocks().rbegin(); |
| 1302 i != code()->instruction_blocks().rend(); ++i) { |
| 1303 ResolvePhis(*i); |
| 1304 } |
| 1305 } |
| 1306 |
| 1307 |
1273 ParallelMove* RegisterAllocator::GetConnectingParallelMove( | 1308 ParallelMove* RegisterAllocator::GetConnectingParallelMove( |
1274 LifetimePosition pos) { | 1309 LifetimePosition pos) { |
1275 int index = pos.InstructionIndex(); | 1310 int index = pos.InstructionIndex(); |
1276 if (code()->IsGapAt(index)) { | 1311 if (code()->IsGapAt(index)) { |
1277 GapInstruction* gap = code()->GapAt(index); | 1312 GapInstruction* gap = code()->GapAt(index); |
1278 return gap->GetOrCreateParallelMove( | 1313 return gap->GetOrCreateParallelMove( |
1279 pos.IsInstructionStart() ? GapInstruction::START : GapInstruction::END, | 1314 pos.IsInstructionStart() ? GapInstruction::START : GapInstruction::END, |
1280 code_zone()); | 1315 code_zone()); |
1281 } | 1316 } |
1282 int gap_pos = pos.IsInstructionStart() ? (index - 1) : (index + 1); | 1317 int gap_pos = pos.IsInstructionStart() ? (index - 1) : (index + 1); |
(...skipping 184 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1467 }; | 1502 }; |
1468 | 1503 |
1469 } // namespace | 1504 } // namespace |
1470 | 1505 |
1471 | 1506 |
1472 void RegisterAllocator::ResolveControlFlow() { | 1507 void RegisterAllocator::ResolveControlFlow() { |
1473 // Lazily linearize live ranges in memory for fast lookup. | 1508 // Lazily linearize live ranges in memory for fast lookup. |
1474 LiveRangeFinder finder(*this); | 1509 LiveRangeFinder finder(*this); |
1475 for (auto block : code()->instruction_blocks()) { | 1510 for (auto block : code()->instruction_blocks()) { |
1476 if (CanEagerlyResolveControlFlow(block)) continue; | 1511 if (CanEagerlyResolveControlFlow(block)) continue; |
1477 // resolve phis | 1512 if (FLAG_turbo_delay_ssa_decon) { |
1478 for (auto phi : block->phis()) { | 1513 // resolve phis |
1479 auto* block_bound = | 1514 for (auto phi : block->phis()) { |
1480 finder.ArrayFor(phi->virtual_register())->FindSucc(block); | 1515 auto* block_bound = |
1481 auto phi_output = block_bound->range_->CreateAssignedOperand(code_zone()); | 1516 finder.ArrayFor(phi->virtual_register())->FindSucc(block); |
1482 phi->output()->ConvertTo(phi_output->kind(), phi_output->index()); | 1517 auto phi_output = |
1483 size_t pred_index = 0; | 1518 block_bound->range_->CreateAssignedOperand(code_zone()); |
1484 for (auto pred : block->predecessors()) { | 1519 phi->output()->ConvertTo(phi_output->kind(), phi_output->index()); |
1485 const InstructionBlock* pred_block = code()->InstructionBlockAt(pred); | 1520 size_t pred_index = 0; |
1486 auto* pred_bound = | 1521 for (auto pred : block->predecessors()) { |
1487 finder.ArrayFor(phi->operands()[pred_index])->FindPred(pred_block); | 1522 const InstructionBlock* pred_block = code()->InstructionBlockAt(pred); |
1488 auto pred_op = pred_bound->range_->CreateAssignedOperand(code_zone()); | 1523 auto* pred_bound = finder.ArrayFor(phi->operands()[pred_index]) |
1489 phi->inputs()[pred_index] = pred_op; | 1524 ->FindPred(pred_block); |
1490 ResolveControlFlow(block, phi_output, pred_block, pred_op); | 1525 auto pred_op = pred_bound->range_->CreateAssignedOperand(code_zone()); |
1491 pred_index++; | 1526 phi->inputs()[pred_index] = pred_op; |
| 1527 ResolveControlFlow(block, phi_output, pred_block, pred_op); |
| 1528 pred_index++; |
| 1529 } |
1492 } | 1530 } |
1493 } | 1531 } |
1494 BitVector* live = live_in_sets_[block->rpo_number().ToInt()]; | 1532 BitVector* live = live_in_sets_[block->rpo_number().ToInt()]; |
1495 BitVector::Iterator iterator(live); | 1533 BitVector::Iterator iterator(live); |
1496 while (!iterator.Done()) { | 1534 while (!iterator.Done()) { |
1497 auto* array = finder.ArrayFor(iterator.Current()); | 1535 auto* array = finder.ArrayFor(iterator.Current()); |
1498 for (auto pred : block->predecessors()) { | 1536 for (auto pred : block->predecessors()) { |
1499 FindResult result; | 1537 FindResult result; |
1500 const auto* pred_block = code()->InstructionBlockAt(pred); | 1538 const auto* pred_block = code()->InstructionBlockAt(pred); |
1501 array->Find(block, pred_block, &result); | 1539 array->Find(block, pred_block, &result); |
(...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1549 | 1587 |
1550 // Process the instructions in reverse order, generating and killing | 1588 // Process the instructions in reverse order, generating and killing |
1551 // live values. | 1589 // live values. |
1552 ProcessInstructions(block, live); | 1590 ProcessInstructions(block, live); |
1553 // All phi output operands are killed by this block. | 1591 // All phi output operands are killed by this block. |
1554 for (auto phi : block->phis()) { | 1592 for (auto phi : block->phis()) { |
1555 // The live range interval already ends at the first instruction of the | 1593 // The live range interval already ends at the first instruction of the |
1556 // block. | 1594 // block. |
1557 int phi_vreg = phi->virtual_register(); | 1595 int phi_vreg = phi->virtual_register(); |
1558 live->Remove(phi_vreg); | 1596 live->Remove(phi_vreg); |
| 1597 if (!FLAG_turbo_delay_ssa_decon) { |
| 1598 InstructionOperand* hint = NULL; |
| 1599 InstructionOperand* phi_operand = NULL; |
| 1600 GapInstruction* gap = |
| 1601 GetLastGap(code()->InstructionBlockAt(block->predecessors()[0])); |
| 1602 ParallelMove* move = |
| 1603 gap->GetOrCreateParallelMove(GapInstruction::START, code_zone()); |
| 1604 for (int j = 0; j < move->move_operands()->length(); ++j) { |
| 1605 InstructionOperand* to = move->move_operands()->at(j).destination(); |
| 1606 if (to->IsUnallocated() && |
| 1607 UnallocatedOperand::cast(to)->virtual_register() == phi_vreg) { |
| 1608 hint = move->move_operands()->at(j).source(); |
| 1609 phi_operand = to; |
| 1610 break; |
| 1611 } |
| 1612 } |
| 1613 DCHECK(hint != NULL); |
| 1614 LifetimePosition block_start = LifetimePosition::FromInstructionIndex( |
| 1615 block->first_instruction_index()); |
| 1616 Define(block_start, phi_operand, hint); |
| 1617 } |
1559 } | 1618 } |
1560 | 1619 |
1561 // Now live is live_in for this block except not including values live | 1620 // Now live is live_in for this block except not including values live |
1562 // out on backward successor edges. | 1621 // out on backward successor edges. |
1563 live_in_sets_[block_id] = live; | 1622 live_in_sets_[block_id] = live; |
1564 | 1623 |
1565 if (block->IsLoopHeader()) { | 1624 if (block->IsLoopHeader()) { |
1566 // Add a live range stretching from the first loop instruction to the last | 1625 // Add a live range stretching from the first loop instruction to the last |
1567 // for each value live on entry to the header. | 1626 // for each value live on entry to the header. |
1568 BitVector::Iterator iterator(live); | 1627 BitVector::Iterator iterator(live); |
(...skipping 24 matching lines...) Expand all Loading... |
1593 // TODO(bmeurer): This is a horrible hack to make sure that for constant | 1652 // TODO(bmeurer): This is a horrible hack to make sure that for constant |
1594 // live ranges, every use requires the constant to be in a register. | 1653 // live ranges, every use requires the constant to be in a register. |
1595 // Without this hack, all uses with "any" policy would get the constant | 1654 // Without this hack, all uses with "any" policy would get the constant |
1596 // operand assigned. | 1655 // operand assigned. |
1597 LiveRange* range = live_ranges_[i]; | 1656 LiveRange* range = live_ranges_[i]; |
1598 if (range->HasAllocatedSpillOperand() && | 1657 if (range->HasAllocatedSpillOperand() && |
1599 range->GetSpillOperand()->IsConstant()) { | 1658 range->GetSpillOperand()->IsConstant()) { |
1600 for (UsePosition* pos = range->first_pos(); pos != NULL; | 1659 for (UsePosition* pos = range->first_pos(); pos != NULL; |
1601 pos = pos->next_) { | 1660 pos = pos->next_) { |
1602 pos->register_beneficial_ = true; | 1661 pos->register_beneficial_ = true; |
1603 pos->requires_reg_ = true; | 1662 // TODO(dcarney): should the else case assert requires_reg_ == false? |
| 1663 // Can't mark phis as needing a register. |
| 1664 if (!code() |
| 1665 ->InstructionAt(pos->pos().InstructionIndex()) |
| 1666 ->IsGapMoves()) { |
| 1667 pos->requires_reg_ = true; |
| 1668 } |
1604 } | 1669 } |
1605 } | 1670 } |
1606 } | 1671 } |
1607 } | 1672 } |
1608 } | 1673 } |
1609 | 1674 |
1610 | 1675 |
1611 bool RegisterAllocator::ExistsUseWithoutDefinition() { | 1676 bool RegisterAllocator::ExistsUseWithoutDefinition() { |
1612 bool found = false; | 1677 bool found = false; |
1613 BitVector::Iterator iterator(live_in_sets_[0]); | 1678 BitVector::Iterator iterator(live_in_sets_[0]); |
(...skipping 800 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2414 } else { | 2479 } else { |
2415 DCHECK(range->Kind() == GENERAL_REGISTERS); | 2480 DCHECK(range->Kind() == GENERAL_REGISTERS); |
2416 assigned_registers_->Add(reg); | 2481 assigned_registers_->Add(reg); |
2417 } | 2482 } |
2418 range->set_assigned_register(reg, code_zone()); | 2483 range->set_assigned_register(reg, code_zone()); |
2419 } | 2484 } |
2420 | 2485 |
2421 } | 2486 } |
2422 } | 2487 } |
2423 } // namespace v8::internal::compiler | 2488 } // namespace v8::internal::compiler |
OLD | NEW |