OLD | NEW |
1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2014, 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_range_analysis.h" | 5 #include "vm/flow_graph_range_analysis.h" |
6 | 6 |
7 #include "vm/bit_vector.h" | 7 #include "vm/bit_vector.h" |
8 #include "vm/il_printer.h" | 8 #include "vm/il_printer.h" |
9 | 9 |
10 namespace dart { | 10 namespace dart { |
(...skipping 166 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
177 | 177 |
178 JoinEntryInstr* join = block->AsJoinEntry(); | 178 JoinEntryInstr* join = block->AsJoinEntry(); |
179 if (join != NULL && join->loop_info() != NULL) { | 179 if (join != NULL && join->loop_info() != NULL) { |
180 loop_variables.Clear(); | 180 loop_variables.Clear(); |
181 | 181 |
182 for (PhiIterator phi_it(join); !phi_it.Done(); phi_it.Advance()) { | 182 for (PhiIterator phi_it(join); !phi_it.Done(); phi_it.Advance()) { |
183 PhiInstr* current = phi_it.Current(); | 183 PhiInstr* current = phi_it.Current(); |
184 | 184 |
185 InductionVariableInfo* info = DetectSimpleInductionVariable(current); | 185 InductionVariableInfo* info = DetectSimpleInductionVariable(current); |
186 if (info != NULL) { | 186 if (info != NULL) { |
187 if (FLAG_trace_range_analysis) { | 187 if (FLAG_support_il_printer && FLAG_trace_range_analysis) { |
188 THR_Print("Simple loop variable: %s bound <%s>\n", | 188 THR_Print("Simple loop variable: %s bound <%s>\n", |
189 current->ToCString(), | 189 current->ToCString(), |
190 info->limit() != NULL ? | 190 info->limit() != NULL ? |
191 info->limit()->ToCString() : "?"); | 191 info->limit()->ToCString() : "?"); |
192 } | 192 } |
193 | 193 |
194 loop_variables.Add(info); | 194 loop_variables.Add(info); |
195 } | 195 } |
196 } | 196 } |
197 } | 197 } |
(...skipping 489 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
687 if (op == WIDEN) { | 687 if (op == WIDEN) { |
688 range = Range(WidenMin(defn->range(), &range, size), | 688 range = Range(WidenMin(defn->range(), &range, size), |
689 WidenMax(defn->range(), &range, size)); | 689 WidenMax(defn->range(), &range, size)); |
690 } else if (op == NARROW) { | 690 } else if (op == NARROW) { |
691 range = Range(NarrowMin(defn->range(), &range, size), | 691 range = Range(NarrowMin(defn->range(), &range, size), |
692 NarrowMax(defn->range(), &range, size)); | 692 NarrowMax(defn->range(), &range, size)); |
693 } | 693 } |
694 } | 694 } |
695 | 695 |
696 if (!range.Equals(defn->range())) { | 696 if (!range.Equals(defn->range())) { |
697 if (FLAG_trace_range_analysis) { | 697 if (FLAG_support_il_printer && FLAG_trace_range_analysis) { |
698 THR_Print("%c [%" Pd "] %s: %s => %s\n", | 698 THR_Print("%c [%" Pd "] %s: %s => %s\n", |
699 OpPrefix(op), | 699 OpPrefix(op), |
700 iteration, | 700 iteration, |
701 defn->ToCString(), | 701 defn->ToCString(), |
702 Range::ToCString(defn->range()), | 702 Range::ToCString(defn->range()), |
703 Range::ToCString(&range)); | 703 Range::ToCString(&range)); |
704 } | 704 } |
705 defn->set_range(range); | 705 defn->set_range(range); |
706 return true; | 706 return true; |
707 } | 707 } |
(...skipping 282 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
990 : range_analysis_(range_analysis), | 990 : range_analysis_(range_analysis), |
991 flow_graph_(flow_graph), | 991 flow_graph_(flow_graph), |
992 scheduler_(flow_graph) { } | 992 scheduler_(flow_graph) { } |
993 | 993 |
994 void TryGeneralize(CheckArrayBoundInstr* check, | 994 void TryGeneralize(CheckArrayBoundInstr* check, |
995 const RangeBoundary& array_length) { | 995 const RangeBoundary& array_length) { |
996 Definition* upper_bound = | 996 Definition* upper_bound = |
997 ConstructUpperBound(check->index()->definition(), check); | 997 ConstructUpperBound(check->index()->definition(), check); |
998 if (upper_bound == UnwrapConstraint(check->index()->definition())) { | 998 if (upper_bound == UnwrapConstraint(check->index()->definition())) { |
999 // Unable to construct upper bound for the index. | 999 // Unable to construct upper bound for the index. |
1000 if (FLAG_trace_range_analysis) { | 1000 if (FLAG_support_il_printer && FLAG_trace_range_analysis) { |
1001 THR_Print("Failed to construct upper bound for %s index\n", | 1001 THR_Print("Failed to construct upper bound for %s index\n", |
1002 check->ToCString()); | 1002 check->ToCString()); |
1003 } | 1003 } |
1004 return; | 1004 return; |
1005 } | 1005 } |
1006 | 1006 |
1007 // Re-associate subexpressions inside upper_bound to collect all constants | 1007 // Re-associate subexpressions inside upper_bound to collect all constants |
1008 // together. This will expose more redundancies when we are going to emit | 1008 // together. This will expose more redundancies when we are going to emit |
1009 // upper bound through scheduler. | 1009 // upper bound through scheduler. |
1010 if (!Simplify(&upper_bound, NULL)) { | 1010 if (!Simplify(&upper_bound, NULL)) { |
1011 if (FLAG_trace_range_analysis) { | 1011 if (FLAG_support_il_printer && FLAG_trace_range_analysis) { |
1012 THR_Print("Failed to simplify upper bound for %s index\n", | 1012 THR_Print("Failed to simplify upper bound for %s index\n", |
1013 check->ToCString()); | 1013 check->ToCString()); |
1014 } | 1014 } |
1015 return; | 1015 return; |
1016 } | 1016 } |
1017 upper_bound = ApplyConstraints(upper_bound, check); | 1017 upper_bound = ApplyConstraints(upper_bound, check); |
1018 range_analysis_->AssignRangesRecursively(upper_bound); | 1018 range_analysis_->AssignRangesRecursively(upper_bound); |
1019 | 1019 |
1020 // We are going to constrain any symbols participating in + and * operations | 1020 // We are going to constrain any symbols participating in + and * operations |
1021 // to guarantee that they are positive. Find all symbols that need | 1021 // to guarantee that they are positive. Find all symbols that need |
1022 // constraining. If there is a subtraction subexpression with non-positive | 1022 // constraining. If there is a subtraction subexpression with non-positive |
1023 // range give up on generalization for simplicity. | 1023 // range give up on generalization for simplicity. |
1024 GrowableArray<Definition*> non_positive_symbols; | 1024 GrowableArray<Definition*> non_positive_symbols; |
1025 if (!FindNonPositiveSymbols(&non_positive_symbols, upper_bound)) { | 1025 if (!FindNonPositiveSymbols(&non_positive_symbols, upper_bound)) { |
1026 if (FLAG_trace_range_analysis) { | 1026 if (FLAG_support_il_printer && FLAG_trace_range_analysis) { |
1027 THR_Print("Failed to generalize %s index to %s" | 1027 THR_Print("Failed to generalize %s index to %s" |
1028 " (can't ensure positivity)\n", | 1028 " (can't ensure positivity)\n", |
1029 check->ToCString(), | 1029 check->ToCString(), |
1030 IndexBoundToCString(upper_bound)); | 1030 IndexBoundToCString(upper_bound)); |
1031 } | 1031 } |
1032 return; | 1032 return; |
1033 } | 1033 } |
1034 | 1034 |
1035 // Check that we can statically prove that lower bound of the index is | 1035 // Check that we can statically prove that lower bound of the index is |
1036 // non-negative under the assumption that all potentially non-positive | 1036 // non-negative under the assumption that all potentially non-positive |
(...skipping 13 matching lines...) Expand all Loading... |
1050 Definition* lower_bound = | 1050 Definition* lower_bound = |
1051 ConstructLowerBound(check->index()->definition(), check); | 1051 ConstructLowerBound(check->index()->definition(), check); |
1052 // No need to simplify lower bound before applying constraints as | 1052 // No need to simplify lower bound before applying constraints as |
1053 // we are not going to emit it. | 1053 // we are not going to emit it. |
1054 lower_bound = ApplyConstraints(lower_bound, check, &positive_constraints); | 1054 lower_bound = ApplyConstraints(lower_bound, check, &positive_constraints); |
1055 range_analysis_->AssignRangesRecursively(lower_bound); | 1055 range_analysis_->AssignRangesRecursively(lower_bound); |
1056 | 1056 |
1057 if (!RangeUtils::IsPositive(lower_bound->range())) { | 1057 if (!RangeUtils::IsPositive(lower_bound->range())) { |
1058 // Can't prove that lower bound is positive even with additional checks | 1058 // Can't prove that lower bound is positive even with additional checks |
1059 // against potentially non-positive symbols. Give up. | 1059 // against potentially non-positive symbols. Give up. |
1060 if (FLAG_trace_range_analysis) { | 1060 if (FLAG_support_il_printer && FLAG_trace_range_analysis) { |
1061 THR_Print("Failed to generalize %s index to %s" | 1061 THR_Print("Failed to generalize %s index to %s" |
1062 " (lower bound is not positive)\n", | 1062 " (lower bound is not positive)\n", |
1063 check->ToCString(), | 1063 check->ToCString(), |
1064 IndexBoundToCString(upper_bound)); | 1064 IndexBoundToCString(upper_bound)); |
1065 } | 1065 } |
1066 return; | 1066 return; |
1067 } | 1067 } |
1068 | 1068 |
1069 if (FLAG_trace_range_analysis) { | 1069 if (FLAG_support_il_printer && FLAG_trace_range_analysis) { |
1070 THR_Print("For %s computed index bounds [%s, %s]\n", | 1070 THR_Print("For %s computed index bounds [%s, %s]\n", |
1071 check->ToCString(), | 1071 check->ToCString(), |
1072 IndexBoundToCString(lower_bound), | 1072 IndexBoundToCString(lower_bound), |
1073 IndexBoundToCString(upper_bound)); | 1073 IndexBoundToCString(upper_bound)); |
1074 } | 1074 } |
1075 | 1075 |
1076 // At this point we know that 0 <= index < UpperBound(index) under | 1076 // At this point we know that 0 <= index < UpperBound(index) under |
1077 // certain preconditions. Start by emitting this preconditions. | 1077 // certain preconditions. Start by emitting this preconditions. |
1078 scheduler_.Start(); | 1078 scheduler_.Start(); |
1079 | 1079 |
(...skipping 586 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1666 | 1666 |
1667 | 1667 |
1668 void IntegerInstructionSelector::Select() { | 1668 void IntegerInstructionSelector::Select() { |
1669 if (FLAG_trace_integer_ir_selection) { | 1669 if (FLAG_trace_integer_ir_selection) { |
1670 THR_Print("---- starting integer ir selection -------\n"); | 1670 THR_Print("---- starting integer ir selection -------\n"); |
1671 } | 1671 } |
1672 FindPotentialUint32Definitions(); | 1672 FindPotentialUint32Definitions(); |
1673 FindUint32NarrowingDefinitions(); | 1673 FindUint32NarrowingDefinitions(); |
1674 Propagate(); | 1674 Propagate(); |
1675 ReplaceInstructions(); | 1675 ReplaceInstructions(); |
1676 if (FLAG_trace_integer_ir_selection) { | 1676 if (FLAG_support_il_printer && FLAG_trace_integer_ir_selection) { |
1677 THR_Print("---- after integer ir selection -------\n"); | 1677 THR_Print("---- after integer ir selection -------\n"); |
1678 FlowGraphPrinter printer(*flow_graph_); | 1678 FlowGraphPrinter printer(*flow_graph_); |
1679 printer.PrintBlocks(); | 1679 printer.PrintBlocks(); |
1680 } | 1680 } |
1681 } | 1681 } |
1682 | 1682 |
1683 | 1683 |
1684 bool IntegerInstructionSelector::IsPotentialUint32Definition(Definition* def) { | 1684 bool IntegerInstructionSelector::IsPotentialUint32Definition(Definition* def) { |
1685 // TODO(johnmccutchan): Consider Smi operations, to avoid unnecessary tagging | 1685 // TODO(johnmccutchan): Consider Smi operations, to avoid unnecessary tagging |
1686 // & untagged of intermediate results. | 1686 // & untagged of intermediate results. |
(...skipping 16 matching lines...) Expand all Loading... |
1703 block_it.Advance()) { | 1703 block_it.Advance()) { |
1704 BlockEntryInstr* block = block_it.Current(); | 1704 BlockEntryInstr* block = block_it.Current(); |
1705 | 1705 |
1706 for (ForwardInstructionIterator instr_it(block); | 1706 for (ForwardInstructionIterator instr_it(block); |
1707 !instr_it.Done(); | 1707 !instr_it.Done(); |
1708 instr_it.Advance()) { | 1708 instr_it.Advance()) { |
1709 Instruction* current = instr_it.Current(); | 1709 Instruction* current = instr_it.Current(); |
1710 Definition* defn = current->AsDefinition(); | 1710 Definition* defn = current->AsDefinition(); |
1711 if ((defn != NULL) && defn->HasSSATemp()) { | 1711 if ((defn != NULL) && defn->HasSSATemp()) { |
1712 if (IsPotentialUint32Definition(defn)) { | 1712 if (IsPotentialUint32Definition(defn)) { |
1713 if (FLAG_trace_integer_ir_selection) { | 1713 if (FLAG_support_il_printer && FLAG_trace_integer_ir_selection) { |
1714 THR_Print("Adding %s\n", current->ToCString()); | 1714 THR_Print("Adding %s\n", current->ToCString()); |
1715 } | 1715 } |
1716 potential_uint32_defs_.Add(defn); | 1716 potential_uint32_defs_.Add(defn); |
1717 } | 1717 } |
1718 } | 1718 } |
1719 } | 1719 } |
1720 } | 1720 } |
1721 } | 1721 } |
1722 | 1722 |
1723 | 1723 |
(...skipping 20 matching lines...) Expand all Loading... |
1744 | 1744 |
1745 void IntegerInstructionSelector::FindUint32NarrowingDefinitions() { | 1745 void IntegerInstructionSelector::FindUint32NarrowingDefinitions() { |
1746 ASSERT(selected_uint32_defs_ != NULL); | 1746 ASSERT(selected_uint32_defs_ != NULL); |
1747 if (FLAG_trace_integer_ir_selection) { | 1747 if (FLAG_trace_integer_ir_selection) { |
1748 THR_Print("++++ Selecting Uint32 definitions:\n"); | 1748 THR_Print("++++ Selecting Uint32 definitions:\n"); |
1749 THR_Print("++++ Initial set:\n"); | 1749 THR_Print("++++ Initial set:\n"); |
1750 } | 1750 } |
1751 for (intptr_t i = 0; i < potential_uint32_defs_.length(); i++) { | 1751 for (intptr_t i = 0; i < potential_uint32_defs_.length(); i++) { |
1752 Definition* defn = potential_uint32_defs_[i]; | 1752 Definition* defn = potential_uint32_defs_[i]; |
1753 if (IsUint32NarrowingDefinition(defn)) { | 1753 if (IsUint32NarrowingDefinition(defn)) { |
1754 if (FLAG_trace_integer_ir_selection) { | 1754 if (FLAG_support_il_printer && FLAG_trace_integer_ir_selection) { |
1755 THR_Print("Adding %s\n", defn->ToCString()); | 1755 THR_Print("Adding %s\n", defn->ToCString()); |
1756 } | 1756 } |
1757 selected_uint32_defs_->Add(defn->ssa_temp_index()); | 1757 selected_uint32_defs_->Add(defn->ssa_temp_index()); |
1758 } | 1758 } |
1759 } | 1759 } |
1760 } | 1760 } |
1761 | 1761 |
1762 | 1762 |
1763 bool IntegerInstructionSelector::AllUsesAreUint32Narrowing(Value* list_head) { | 1763 bool IntegerInstructionSelector::AllUsesAreUint32Narrowing(Value* list_head) { |
1764 for (Value::Iterator it(list_head); | 1764 for (Value::Iterator it(list_head); |
(...skipping 54 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1819 Definition* defn = potential_uint32_defs_[i]; | 1819 Definition* defn = potential_uint32_defs_[i]; |
1820 if (selected_uint32_defs_->Contains(defn->ssa_temp_index())) { | 1820 if (selected_uint32_defs_->Contains(defn->ssa_temp_index())) { |
1821 // Already marked as a candidate, skip. | 1821 // Already marked as a candidate, skip. |
1822 continue; | 1822 continue; |
1823 } | 1823 } |
1824 if (defn->IsConstant()) { | 1824 if (defn->IsConstant()) { |
1825 // Skip constants. | 1825 // Skip constants. |
1826 continue; | 1826 continue; |
1827 } | 1827 } |
1828 if (CanBecomeUint32(defn)) { | 1828 if (CanBecomeUint32(defn)) { |
1829 if (FLAG_trace_integer_ir_selection) { | 1829 if (FLAG_support_il_printer && FLAG_trace_integer_ir_selection) { |
1830 THR_Print("Adding %s\n", defn->ToCString()); | 1830 THR_Print("Adding %s\n", defn->ToCString()); |
1831 } | 1831 } |
1832 // Found a new candidate. | 1832 // Found a new candidate. |
1833 selected_uint32_defs_->Add(defn->ssa_temp_index()); | 1833 selected_uint32_defs_->Add(defn->ssa_temp_index()); |
1834 // Haven't reached fixed point yet. | 1834 // Haven't reached fixed point yet. |
1835 changed = true; | 1835 changed = true; |
1836 } | 1836 } |
1837 } | 1837 } |
1838 } | 1838 } |
1839 if (FLAG_trace_integer_ir_selection) { | 1839 if (FLAG_trace_integer_ir_selection) { |
(...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1887 THR_Print("++++ Replacing instructions:\n"); | 1887 THR_Print("++++ Replacing instructions:\n"); |
1888 } | 1888 } |
1889 for (intptr_t i = 0; i < potential_uint32_defs_.length(); i++) { | 1889 for (intptr_t i = 0; i < potential_uint32_defs_.length(); i++) { |
1890 Definition* defn = potential_uint32_defs_[i]; | 1890 Definition* defn = potential_uint32_defs_[i]; |
1891 if (!selected_uint32_defs_->Contains(defn->ssa_temp_index())) { | 1891 if (!selected_uint32_defs_->Contains(defn->ssa_temp_index())) { |
1892 // Not a candidate. | 1892 // Not a candidate. |
1893 continue; | 1893 continue; |
1894 } | 1894 } |
1895 Definition* replacement = ConstructReplacementFor(defn); | 1895 Definition* replacement = ConstructReplacementFor(defn); |
1896 ASSERT(replacement != NULL); | 1896 ASSERT(replacement != NULL); |
1897 if (FLAG_trace_integer_ir_selection) { | 1897 if (FLAG_support_il_printer && FLAG_trace_integer_ir_selection) { |
1898 THR_Print("Replacing %s with %s\n", defn->ToCString(), | 1898 THR_Print("Replacing %s with %s\n", defn->ToCString(), |
1899 replacement->ToCString()); | 1899 replacement->ToCString()); |
1900 } | 1900 } |
1901 if (!Range::IsUnknown(defn->range())) { | 1901 if (!Range::IsUnknown(defn->range())) { |
1902 replacement->set_range(*defn->range()); | 1902 replacement->set_range(*defn->range()); |
1903 } | 1903 } |
1904 defn->ReplaceWith(replacement, NULL); | 1904 defn->ReplaceWith(replacement, NULL); |
1905 ASSERT(flow_graph_->VerifyUseLists()); | 1905 ASSERT(flow_graph_->VerifyUseLists()); |
1906 } | 1906 } |
1907 } | 1907 } |
(...skipping 1250 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3158 } | 3158 } |
3159 } while (CanonicalizeMaxBoundary(&max) || | 3159 } while (CanonicalizeMaxBoundary(&max) || |
3160 CanonicalizeMinBoundary(&canonical_length)); | 3160 CanonicalizeMinBoundary(&canonical_length)); |
3161 | 3161 |
3162 // Failed to prove that maximum is bounded with array length. | 3162 // Failed to prove that maximum is bounded with array length. |
3163 return false; | 3163 return false; |
3164 } | 3164 } |
3165 | 3165 |
3166 | 3166 |
3167 } // namespace dart | 3167 } // namespace dart |
OLD | NEW |