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 1413 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1424 private: | 1424 private: |
1425 GVNFlagSet CollectSideEffectsOnPathsToDominatedBlock( | 1425 GVNFlagSet CollectSideEffectsOnPathsToDominatedBlock( |
1426 HBasicBlock* dominator, | 1426 HBasicBlock* dominator, |
1427 HBasicBlock* dominated); | 1427 HBasicBlock* dominated); |
1428 void AnalyzeBlock(HBasicBlock* block, HValueMap* map); | 1428 void AnalyzeBlock(HBasicBlock* block, HValueMap* map); |
1429 void ComputeBlockSideEffects(); | 1429 void ComputeBlockSideEffects(); |
1430 void LoopInvariantCodeMotion(); | 1430 void LoopInvariantCodeMotion(); |
1431 void ProcessLoopBlock(HBasicBlock* block, | 1431 void ProcessLoopBlock(HBasicBlock* block, |
1432 HBasicBlock* before_loop, | 1432 HBasicBlock* before_loop, |
1433 GVNFlagSet loop_kills, | 1433 GVNFlagSet loop_kills, |
1434 GVNFlagSet* accumulated_first_time_depends); | 1434 GVNFlagSet* accumulated_first_time_depends, |
| 1435 GVNFlagSet* accumulated_first_time_changes); |
1435 bool AllowCodeMotion(); | 1436 bool AllowCodeMotion(); |
1436 bool ShouldMove(HInstruction* instr, HBasicBlock* loop_header); | 1437 bool ShouldMove(HInstruction* instr, HBasicBlock* loop_header); |
1437 | 1438 |
1438 HGraph* graph() { return graph_; } | 1439 HGraph* graph() { return graph_; } |
1439 CompilationInfo* info() { return info_; } | 1440 CompilationInfo* info() { return info_; } |
1440 Zone* zone() { return graph_->zone(); } | 1441 Zone* zone() { return graph_->zone(); } |
1441 | 1442 |
1442 HGraph* graph_; | 1443 HGraph* graph_; |
1443 CompilationInfo* info_; | 1444 CompilationInfo* info_; |
1444 bool removed_side_effects_; | 1445 bool removed_side_effects_; |
(...skipping 60 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1505 void HGlobalValueNumberer::LoopInvariantCodeMotion() { | 1506 void HGlobalValueNumberer::LoopInvariantCodeMotion() { |
1506 for (int i = graph_->blocks()->length() - 1; i >= 0; --i) { | 1507 for (int i = graph_->blocks()->length() - 1; i >= 0; --i) { |
1507 HBasicBlock* block = graph_->blocks()->at(i); | 1508 HBasicBlock* block = graph_->blocks()->at(i); |
1508 if (block->IsLoopHeader()) { | 1509 if (block->IsLoopHeader()) { |
1509 GVNFlagSet side_effects = loop_side_effects_[block->block_id()]; | 1510 GVNFlagSet side_effects = loop_side_effects_[block->block_id()]; |
1510 TraceGVN("Try loop invariant motion for block B%d effects=0x%x\n", | 1511 TraceGVN("Try loop invariant motion for block B%d effects=0x%x\n", |
1511 block->block_id(), | 1512 block->block_id(), |
1512 side_effects.ToIntegral()); | 1513 side_effects.ToIntegral()); |
1513 | 1514 |
1514 GVNFlagSet accumulated_first_time_depends; | 1515 GVNFlagSet accumulated_first_time_depends; |
| 1516 GVNFlagSet accumulated_first_time_changes; |
1515 HBasicBlock* last = block->loop_information()->GetLastBackEdge(); | 1517 HBasicBlock* last = block->loop_information()->GetLastBackEdge(); |
1516 for (int j = block->block_id(); j <= last->block_id(); ++j) { | 1518 for (int j = block->block_id(); j <= last->block_id(); ++j) { |
1517 ProcessLoopBlock(graph_->blocks()->at(j), block, side_effects, | 1519 ProcessLoopBlock(graph_->blocks()->at(j), block, side_effects, |
1518 &accumulated_first_time_depends); | 1520 &accumulated_first_time_depends, |
| 1521 &accumulated_first_time_changes); |
1519 } | 1522 } |
1520 } | 1523 } |
1521 } | 1524 } |
1522 } | 1525 } |
1523 | 1526 |
1524 | 1527 |
1525 void HGlobalValueNumberer::ProcessLoopBlock( | 1528 void HGlobalValueNumberer::ProcessLoopBlock( |
1526 HBasicBlock* block, | 1529 HBasicBlock* block, |
1527 HBasicBlock* loop_header, | 1530 HBasicBlock* loop_header, |
1528 GVNFlagSet loop_kills, | 1531 GVNFlagSet loop_kills, |
1529 GVNFlagSet* accumulated_first_time_depends) { | 1532 GVNFlagSet* first_time_depends, |
| 1533 GVNFlagSet* first_time_changes) { |
1530 HBasicBlock* pre_header = loop_header->predecessors()->at(0); | 1534 HBasicBlock* pre_header = loop_header->predecessors()->at(0); |
1531 GVNFlagSet depends_flags = HValue::ConvertChangesToDependsFlags(loop_kills); | 1535 GVNFlagSet depends_flags = HValue::ConvertChangesToDependsFlags(loop_kills); |
1532 TraceGVN("Loop invariant motion for B%d depends_flags=0x%x\n", | 1536 TraceGVN("Loop invariant motion for B%d depends_flags=0x%x\n", |
1533 block->block_id(), | 1537 block->block_id(), |
1534 depends_flags.ToIntegral()); | 1538 depends_flags.ToIntegral()); |
1535 HInstruction* instr = block->first(); | 1539 HInstruction* instr = block->first(); |
1536 while (instr != NULL) { | 1540 while (instr != NULL) { |
1537 HInstruction* next = instr->next(); | 1541 HInstruction* next = instr->next(); |
1538 bool hoisted = false; | 1542 bool hoisted = false; |
1539 if (instr->CheckFlag(HValue::kUseGVN)) { | 1543 if (instr->CheckFlag(HValue::kUseGVN)) { |
1540 TraceGVN("Checking instruction %d (%s) instruction GVN flags 0x%X, " | 1544 TraceGVN("Checking instruction %d (%s) instruction GVN flags 0x%X, " |
1541 "loop kills 0x%X\n", | 1545 "loop kills 0x%X\n", |
1542 instr->id(), | 1546 instr->id(), |
1543 instr->Mnemonic(), | 1547 instr->Mnemonic(), |
1544 instr->gvn_flags().ToIntegral(), | 1548 instr->gvn_flags().ToIntegral(), |
1545 depends_flags.ToIntegral()); | 1549 depends_flags.ToIntegral()); |
1546 bool can_hoist = !instr->gvn_flags().ContainsAnyOf(depends_flags); | 1550 bool can_hoist = !instr->gvn_flags().ContainsAnyOf(depends_flags); |
1547 if (!can_hoist && instr->IsTransitionElementsKind()) { | 1551 if (instr->IsTransitionElementsKind()) { |
1548 // It's only possible to hoist one time side effects if there are no | 1552 // It's possible to hoist transitions out of a loop as long as the |
1549 // dependencies on their changes from the loop header to the current | 1553 // hoisting wouldn't move the transition past a DependsOn of one of it's |
1550 // instruction. | 1554 // changes or any instructions that might change an objects map or |
1551 GVNFlagSet converted_changes = | 1555 // elements contents. |
1552 HValue::ConvertChangesToDependsFlags(instr->ChangesFlags()); | 1556 GVNFlagSet changes = instr->ChangesFlags(); |
1553 TraceGVN("Checking dependencies on one-time instruction %d (%s) " | 1557 GVNFlagSet hoist_depends_blockers = |
1554 "converted changes 0x%X, accumulated depends 0x%X\n", | 1558 HValue::ConvertChangesToDependsFlags(changes); |
| 1559 // In addition to not hoisting transitions above other instructions that |
| 1560 // change dependencies that the transition changes, it must not be |
| 1561 // hoisted above map changes and stores to an elements backing store |
| 1562 // that the transition might change. |
| 1563 GVNFlagSet hoist_change_blockers = changes; |
| 1564 hoist_change_blockers.Add(kChangesMaps); |
| 1565 HTransitionElementsKind* trans = HTransitionElementsKind::cast(instr); |
| 1566 if (trans->original_map()->has_fast_double_elements()) { |
| 1567 hoist_change_blockers.Add(kChangesDoubleArrayElements); |
| 1568 } |
| 1569 if (trans->transitioned_map()->has_fast_double_elements()) { |
| 1570 hoist_change_blockers.Add(kChangesArrayElements); |
| 1571 } |
| 1572 TraceGVN("Checking dependencies on HTransitionElementsKind %d (%s) " |
| 1573 "hoist depends blockers 0x%X, hoist change blockers 0x%X, " |
| 1574 "accumulated depends 0x%X, accumulated changes 0x%X\n", |
1555 instr->id(), | 1575 instr->id(), |
1556 instr->Mnemonic(), | 1576 instr->Mnemonic(), |
1557 converted_changes.ToIntegral(), | 1577 hoist_depends_blockers.ToIntegral(), |
1558 accumulated_first_time_depends->ToIntegral()); | 1578 hoist_change_blockers.ToIntegral(), |
1559 // It's possible to hoist one-time side effects from the current loop | 1579 first_time_depends->ToIntegral(), |
1560 // loop only if they dominate all of the successor blocks in the same | 1580 first_time_changes->ToIntegral()); |
1561 // loop and there are not any instructions that have Changes/DependsOn | 1581 // It's possible to hoist transition from the current loop loop only if |
1562 // that intervene between it and the beginning of the loop header. | 1582 // they dominate all of the successor blocks in the same loop and there |
| 1583 // are not any instructions that have Changes/DependsOn that intervene |
| 1584 // between it and the beginning of the loop header. |
1563 bool in_nested_loop = block != loop_header && | 1585 bool in_nested_loop = block != loop_header && |
1564 ((block->parent_loop_header() != loop_header) || | 1586 ((block->parent_loop_header() != loop_header) || |
1565 block->IsLoopHeader()); | 1587 block->IsLoopHeader()); |
1566 can_hoist = !in_nested_loop && | 1588 can_hoist = !in_nested_loop && |
1567 block->IsLoopSuccessorDominator() && | 1589 block->IsLoopSuccessorDominator() && |
1568 !accumulated_first_time_depends->ContainsAnyOf(converted_changes); | 1590 !first_time_depends->ContainsAnyOf(hoist_depends_blockers) && |
| 1591 !first_time_changes->ContainsAnyOf(hoist_change_blockers); |
1569 } | 1592 } |
1570 | 1593 |
1571 if (can_hoist) { | 1594 if (can_hoist) { |
1572 bool inputs_loop_invariant = true; | 1595 bool inputs_loop_invariant = true; |
1573 for (int i = 0; i < instr->OperandCount(); ++i) { | 1596 for (int i = 0; i < instr->OperandCount(); ++i) { |
1574 if (instr->OperandAt(i)->IsDefinedAfter(pre_header)) { | 1597 if (instr->OperandAt(i)->IsDefinedAfter(pre_header)) { |
1575 inputs_loop_invariant = false; | 1598 inputs_loop_invariant = false; |
1576 } | 1599 } |
1577 } | 1600 } |
1578 | 1601 |
1579 if (inputs_loop_invariant && ShouldMove(instr, loop_header)) { | 1602 if (inputs_loop_invariant && ShouldMove(instr, loop_header)) { |
1580 TraceGVN("Hoisting loop invariant instruction %d\n", instr->id()); | 1603 TraceGVN("Hoisting loop invariant instruction %d\n", instr->id()); |
1581 // Move the instruction out of the loop. | 1604 // Move the instruction out of the loop. |
1582 instr->Unlink(); | 1605 instr->Unlink(); |
1583 instr->InsertBefore(pre_header->end()); | 1606 instr->InsertBefore(pre_header->end()); |
1584 if (instr->HasSideEffects()) removed_side_effects_ = true; | 1607 if (instr->HasSideEffects()) removed_side_effects_ = true; |
1585 hoisted = true; | 1608 hoisted = true; |
1586 } | 1609 } |
1587 } | 1610 } |
1588 } | 1611 } |
1589 if (!hoisted) { | 1612 if (!hoisted) { |
1590 // If an instruction is not hoisted, we have to account for its side | 1613 // If an instruction is not hoisted, we have to account for its side |
1591 // effects when hoisting later HTransitionElementsKind instructions. | 1614 // effects when hoisting later HTransitionElementsKind instructions. |
1592 accumulated_first_time_depends->Add(instr->DependsOnFlags()); | 1615 first_time_depends->Add(instr->DependsOnFlags()); |
1593 GVNFlagSet converted_changes = | 1616 first_time_changes->Add(instr->ChangesFlags()); |
1594 HValue::ConvertChangesToDependsFlags(instr->SideEffectFlags()); | |
1595 accumulated_first_time_depends->Add(converted_changes); | |
1596 } | 1617 } |
1597 instr = next; | 1618 instr = next; |
1598 } | 1619 } |
1599 } | 1620 } |
1600 | 1621 |
1601 | 1622 |
1602 bool HGlobalValueNumberer::AllowCodeMotion() { | 1623 bool HGlobalValueNumberer::AllowCodeMotion() { |
1603 return info()->shared_info()->opt_count() + 1 < Compiler::kDefaultMaxOptCount; | 1624 return info()->shared_info()->opt_count() + 1 < Compiler::kDefaultMaxOptCount; |
1604 } | 1625 } |
1605 | 1626 |
(...skipping 2841 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
4447 map->FindTransitionedMap(&possible_transitioned_maps); | 4468 map->FindTransitionedMap(&possible_transitioned_maps); |
4448 transition_target.Add(transitioned_map); | 4469 transition_target.Add(transitioned_map); |
4449 } | 4470 } |
4450 | 4471 |
4451 int num_untransitionable_maps = 0; | 4472 int num_untransitionable_maps = 0; |
4452 Handle<Map> untransitionable_map; | 4473 Handle<Map> untransitionable_map; |
4453 for (int i = 0; i < maps->length(); ++i) { | 4474 for (int i = 0; i < maps->length(); ++i) { |
4454 Handle<Map> map = maps->at(i); | 4475 Handle<Map> map = maps->at(i); |
4455 ASSERT(map->IsMap()); | 4476 ASSERT(map->IsMap()); |
4456 if (!transition_target.at(i).is_null()) { | 4477 if (!transition_target.at(i).is_null()) { |
4457 object = AddInstruction(new(zone()) HTransitionElementsKind( | 4478 AddInstruction(new(zone()) HTransitionElementsKind( |
4458 object, map, transition_target.at(i))); | 4479 object, map, transition_target.at(i))); |
4459 } else { | 4480 } else { |
4460 type_todo[map->elements_kind()] = true; | 4481 type_todo[map->elements_kind()] = true; |
4461 if (map->elements_kind() >= FIRST_EXTERNAL_ARRAY_ELEMENTS_KIND) { | 4482 if (map->elements_kind() >= FIRST_EXTERNAL_ARRAY_ELEMENTS_KIND) { |
4462 todo_external_array = true; | 4483 todo_external_array = true; |
4463 } | 4484 } |
4464 num_untransitionable_maps++; | 4485 num_untransitionable_maps++; |
4465 untransitionable_map = map; | 4486 untransitionable_map = map; |
4466 } | 4487 } |
4467 } | 4488 } |
(...skipping 3239 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
7707 } | 7728 } |
7708 } | 7729 } |
7709 | 7730 |
7710 #ifdef DEBUG | 7731 #ifdef DEBUG |
7711 if (graph_ != NULL) graph_->Verify(false); // No full verify. | 7732 if (graph_ != NULL) graph_->Verify(false); // No full verify. |
7712 if (allocator_ != NULL) allocator_->Verify(); | 7733 if (allocator_ != NULL) allocator_->Verify(); |
7713 #endif | 7734 #endif |
7714 } | 7735 } |
7715 | 7736 |
7716 } } // namespace v8::internal | 7737 } } // namespace v8::internal |
OLD | NEW |