OLD | NEW |
1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 #include "vm/flow_graph_optimizer.h" | 5 #include "vm/flow_graph_optimizer.h" |
6 | 6 |
7 #include "vm/bit_vector.h" | 7 #include "vm/bit_vector.h" |
8 #include "vm/cha.h" | 8 #include "vm/cha.h" |
9 #include "vm/cpu.h" | 9 #include "vm/cpu.h" |
10 #include "vm/dart_entry.h" | 10 #include "vm/dart_entry.h" |
(...skipping 4607 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
4618 instr->RemoveEnvironment(); | 4618 instr->RemoveEnvironment(); |
4619 ReplaceCall(instr, store); | 4619 ReplaceCall(instr, store); |
4620 return true; | 4620 return true; |
4621 } | 4621 } |
4622 | 4622 |
4623 | 4623 |
4624 #if defined(TARGET_ARCH_ARM) || defined(TARGET_ARCH_IA32) | 4624 #if defined(TARGET_ARCH_ARM) || defined(TARGET_ARCH_IA32) |
4625 // Smi widening pass is only meaningful on platforms where Smi | 4625 // Smi widening pass is only meaningful on platforms where Smi |
4626 // is smaller than 32bit. For now only support it on ARM and ia32. | 4626 // is smaller than 32bit. For now only support it on ARM and ia32. |
4627 | 4627 |
4628 class DefinitionWorklist { | 4628 class DefinitionWorklist : public ValueObject { |
4629 public: | 4629 public: |
4630 DefinitionWorklist(FlowGraph* flow_graph, | 4630 DefinitionWorklist(FlowGraph* flow_graph, |
4631 intptr_t initial_capacity) | 4631 intptr_t initial_capacity) |
4632 : defs_(initial_capacity), | 4632 : defs_(initial_capacity), |
4633 contains_(new BitVector(flow_graph->current_ssa_temp_index())) { | 4633 contains_vector_(new BitVector(flow_graph->current_ssa_temp_index())) { |
4634 } | 4634 } |
4635 | 4635 |
4636 void Add(Definition* defn) { | 4636 void Add(Definition* defn) { |
4637 if (!Contains(defn)) { | 4637 if (!Contains(defn)) { |
4638 defs_.Add(defn); | 4638 defs_.Add(defn); |
4639 contains_->Add(defn->ssa_temp_index()); | 4639 contains_vector_->Add(defn->ssa_temp_index()); |
4640 } | 4640 } |
4641 } | 4641 } |
4642 | 4642 |
4643 bool Contains(Definition* defn) const { | 4643 bool Contains(Definition* defn) const { |
4644 return (defn->ssa_temp_index() >= 0) && | 4644 return (defn->ssa_temp_index() >= 0) && |
4645 contains_->Contains(defn->ssa_temp_index()); | 4645 contains_vector_->Contains(defn->ssa_temp_index()); |
4646 } | 4646 } |
4647 | 4647 |
4648 const GrowableArray<Definition*>& definitions() const { return defs_; } | 4648 const GrowableArray<Definition*>& definitions() const { return defs_; } |
4649 BitVector* contains() const { return contains_; } | 4649 BitVector* contains_vector() const { return contains_vector_; } |
4650 | 4650 |
4651 void Clear() { | 4651 void Clear() { |
4652 defs_.TruncateTo(0); | 4652 defs_.TruncateTo(0); |
4653 contains_->Clear(); | 4653 contains_vector_->Clear(); |
4654 } | 4654 } |
4655 | 4655 |
4656 private: | 4656 private: |
4657 GrowableArray<Definition*> defs_; | 4657 GrowableArray<Definition*> defs_; |
4658 BitVector* contains_; | 4658 BitVector* contains_vector_; |
4659 }; | 4659 }; |
4660 | 4660 |
4661 | 4661 |
4662 static bool CanBeWidened(BinarySmiOpInstr* smi_op) { | 4662 static bool CanBeWidened(BinarySmiOpInstr* smi_op) { |
4663 return BinaryInt32OpInstr::IsSupported(smi_op->op_kind(), | 4663 return BinaryInt32OpInstr::IsSupported(smi_op->op_kind(), |
4664 smi_op->left(), | 4664 smi_op->left(), |
4665 smi_op->right()); | 4665 smi_op->right()); |
4666 } | 4666 } |
4667 | 4667 |
4668 | 4668 |
(...skipping 18 matching lines...) Expand all Loading... |
4687 | 4687 |
4688 // Step 1. Collect all instructions that potentially benefit from widening of | 4688 // Step 1. Collect all instructions that potentially benefit from widening of |
4689 // their operands (or their result) into int32 range. | 4689 // their operands (or their result) into int32 range. |
4690 for (BlockIterator block_it = flow_graph_->reverse_postorder_iterator(); | 4690 for (BlockIterator block_it = flow_graph_->reverse_postorder_iterator(); |
4691 !block_it.Done(); | 4691 !block_it.Done(); |
4692 block_it.Advance()) { | 4692 block_it.Advance()) { |
4693 for (ForwardInstructionIterator instr_it(block_it.Current()); | 4693 for (ForwardInstructionIterator instr_it(block_it.Current()); |
4694 !instr_it.Done(); | 4694 !instr_it.Done(); |
4695 instr_it.Advance()) { | 4695 instr_it.Advance()) { |
4696 BinarySmiOpInstr* smi_op = instr_it.Current()->AsBinarySmiOp(); | 4696 BinarySmiOpInstr* smi_op = instr_it.Current()->AsBinarySmiOp(); |
4697 if (smi_op != NULL && | 4697 if ((smi_op != NULL) && |
4698 BenefitsFromWidening(smi_op) && | 4698 BenefitsFromWidening(smi_op) && |
4699 CanBeWidened(smi_op)) { | 4699 CanBeWidened(smi_op)) { |
4700 candidates.Add(smi_op); | 4700 candidates.Add(smi_op); |
4701 } | 4701 } |
4702 } | 4702 } |
4703 } | 4703 } |
4704 | 4704 |
4705 if (candidates.length() == 0) { | 4705 if (candidates.is_empty()) { |
4706 return; | 4706 return; |
4707 } | 4707 } |
4708 | 4708 |
4709 // Step 2. For each block in the graph compute which loop it belongs to. | 4709 // Step 2. For each block in the graph compute which loop it belongs to. |
4710 // We will use this information later during computation of the widening's | 4710 // We will use this information later during computation of the widening's |
4711 // gain: we are going to assume that only conversion occuring inside the | 4711 // gain: we are going to assume that only conversion occuring inside the |
4712 // same loop should be counted against the gain, all other conversions | 4712 // same loop should be counted against the gain, all other conversions |
4713 // can be hoisted and thus cost nothing compared to the loop cost itself. | 4713 // can be hoisted and thus cost nothing compared to the loop cost itself. |
4714 const ZoneGrowableArray<BlockEntryInstr*>& loop_headers = | 4714 const ZoneGrowableArray<BlockEntryInstr*>& loop_headers = |
4715 flow_graph()->loop_headers(); | 4715 flow_graph()->loop_headers(); |
4716 | 4716 |
4717 GrowableArray<intptr_t> loops(flow_graph_->preorder().length()); | 4717 GrowableArray<intptr_t> loops(flow_graph_->preorder().length()); |
4718 for (intptr_t i = 0; i < flow_graph_->preorder().length(); i++) { | 4718 for (intptr_t i = 0; i < flow_graph_->preorder().length(); i++) { |
4719 loops.Add(-1); | 4719 loops.Add(-1); |
4720 } | 4720 } |
4721 | 4721 |
4722 for (intptr_t loop_id = 0; loop_id < loop_headers.length(); ++loop_id) { | 4722 for (intptr_t loop_id = 0; loop_id < loop_headers.length(); ++loop_id) { |
4723 for (BitVector::Iterator loop_it(loop_headers[loop_id]->loop_info()); | 4723 for (BitVector::Iterator loop_it(loop_headers[loop_id]->loop_info()); |
4724 !loop_it.Done(); | 4724 !loop_it.Done(); |
4725 loop_it.Advance()) { | 4725 loop_it.Advance()) { |
(...skipping 44 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
4770 } | 4770 } |
4771 | 4771 |
4772 const intptr_t defn_loop = loops[defn->GetBlock()->preorder_number()]; | 4772 const intptr_t defn_loop = loops[defn->GetBlock()->preorder_number()]; |
4773 | 4773 |
4774 // Process all inputs. | 4774 // Process all inputs. |
4775 for (intptr_t k = 0; k < defn->InputCount(); k++) { | 4775 for (intptr_t k = 0; k < defn->InputCount(); k++) { |
4776 Definition* input = defn->InputAt(k)->definition(); | 4776 Definition* input = defn->InputAt(k)->definition(); |
4777 if (input->IsBinarySmiOp() && | 4777 if (input->IsBinarySmiOp() && |
4778 CanBeWidened(input->AsBinarySmiOp())) { | 4778 CanBeWidened(input->AsBinarySmiOp())) { |
4779 worklist.Add(input); | 4779 worklist.Add(input); |
4780 } else if (input->IsPhi() && input->Type()->ToCid() == kSmiCid) { | 4780 } else if (input->IsPhi() && (input->Type()->ToCid() == kSmiCid)) { |
4781 worklist.Add(input); | 4781 worklist.Add(input); |
4782 } else if (input->IsBinaryMintOp()) { | 4782 } else if (input->IsBinaryMintOp()) { |
4783 // Mint operation produces untagged result. We avoid tagging. | 4783 // Mint operation produces untagged result. We avoid tagging. |
4784 gain++; | 4784 gain++; |
4785 if (FLAG_trace_smi_widening) { | 4785 if (FLAG_trace_smi_widening) { |
4786 OS::Print("^ [%" Pd "] (i) %s\n", gain, input->ToCString()); | 4786 OS::Print("^ [%" Pd "] (i) %s\n", gain, input->ToCString()); |
4787 } | 4787 } |
4788 } else if (defn_loop == loops[input->GetBlock()->preorder_number()] && | 4788 } else if (defn_loop == loops[input->GetBlock()->preorder_number()] && |
4789 (input->Type()->ToCid() == kSmiCid)) { | 4789 (input->Type()->ToCid() == kSmiCid)) { |
4790 // Input comes from the same loop, is known to be smi and requires | 4790 // Input comes from the same loop, is known to be smi and requires |
(...skipping 46 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
4837 gain--; | 4837 gain--; |
4838 if (FLAG_trace_smi_widening) { | 4838 if (FLAG_trace_smi_widening) { |
4839 OS::Print("v [%" Pd "] (u) %s\n", | 4839 OS::Print("v [%" Pd "] (u) %s\n", |
4840 gain, | 4840 gain, |
4841 use->instruction()->ToCString()); | 4841 use->instruction()->ToCString()); |
4842 } | 4842 } |
4843 } | 4843 } |
4844 } | 4844 } |
4845 } | 4845 } |
4846 | 4846 |
4847 processed->AddAll(worklist.contains()); | 4847 processed->AddAll(worklist.contains_vector()); |
4848 | 4848 |
4849 if (FLAG_trace_smi_widening) { | 4849 if (FLAG_trace_smi_widening) { |
4850 OS::Print("~ %s gain %" Pd "\n", op->ToCString(), gain); | 4850 OS::Print("~ %s gain %" Pd "\n", op->ToCString(), gain); |
4851 } | 4851 } |
4852 | 4852 |
4853 if (gain > 0) { | 4853 if (gain > 0) { |
4854 // We have positive gain from widening. Convert all BinarySmiOpInstr into | 4854 // We have positive gain from widening. Convert all BinarySmiOpInstr into |
4855 // BinaryInt32OpInstr and set representation of all phis to kUnboxedInt32. | 4855 // BinaryInt32OpInstr and set representation of all phis to kUnboxedInt32. |
4856 for (intptr_t j = 0; j < worklist.definitions().length(); j++) { | 4856 for (intptr_t j = 0; j < worklist.definitions().length(); j++) { |
4857 Definition* defn = worklist.definitions()[j]; | 4857 Definition* defn = worklist.definitions()[j]; |
(...skipping 5101 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
9959 | 9959 |
9960 // Insert materializations at environment uses. | 9960 // Insert materializations at environment uses. |
9961 for (intptr_t i = 0; i < exits_collector_.exits().length(); i++) { | 9961 for (intptr_t i = 0; i < exits_collector_.exits().length(); i++) { |
9962 CreateMaterializationAt( | 9962 CreateMaterializationAt( |
9963 exits_collector_.exits()[i], alloc, alloc->cls(), *slots); | 9963 exits_collector_.exits()[i], alloc, alloc->cls(), *slots); |
9964 } | 9964 } |
9965 } | 9965 } |
9966 | 9966 |
9967 | 9967 |
9968 } // namespace dart | 9968 } // namespace dart |
OLD | NEW |