Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(85)

Side by Side Diff: runtime/vm/flow_graph_range_analysis.cc

Issue 1678203002: Remove more feature in product mode (Closed) Base URL: git@github.com:dart-lang/sdk.git@master
Patch Set: Created 4 years, 10 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
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
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
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
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
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
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
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
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
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
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
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
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698