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