| 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 1006 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1017 } | 1017 } |
| 1018 upper_bound = ApplyConstraints(upper_bound, check); | 1018 upper_bound = ApplyConstraints(upper_bound, check); |
| 1019 range_analysis_->AssignRangesRecursively(upper_bound); | 1019 range_analysis_->AssignRangesRecursively(upper_bound); |
| 1020 | 1020 |
| 1021 // We are going to constrain any symbols participating in + and * operations | 1021 // We are going to constrain any symbols participating in + and * operations |
| 1022 // to guarantee that they are positive. Find all symbols that need | 1022 // to guarantee that they are positive. Find all symbols that need |
| 1023 // constraining. If there is a subtraction subexpression with non-positive | 1023 // constraining. If there is a subtraction subexpression with non-positive |
| 1024 // range give up on generalization for simplicity. | 1024 // range give up on generalization for simplicity. |
| 1025 GrowableArray<Definition*> non_positive_symbols; | 1025 GrowableArray<Definition*> non_positive_symbols; |
| 1026 if (!FindNonPositiveSymbols(&non_positive_symbols, upper_bound)) { | 1026 if (!FindNonPositiveSymbols(&non_positive_symbols, upper_bound)) { |
| 1027 #ifndef PRODUCT |
| 1027 if (FLAG_support_il_printer && FLAG_trace_range_analysis) { | 1028 if (FLAG_support_il_printer && FLAG_trace_range_analysis) { |
| 1028 THR_Print("Failed to generalize %s index to %s" | 1029 THR_Print("Failed to generalize %s index to %s" |
| 1029 " (can't ensure positivity)\n", | 1030 " (can't ensure positivity)\n", |
| 1030 check->ToCString(), | 1031 check->ToCString(), |
| 1031 IndexBoundToCString(upper_bound)); | 1032 IndexBoundToCString(upper_bound)); |
| 1032 } | 1033 } |
| 1034 #endif // !PRODUCT |
| 1033 return; | 1035 return; |
| 1034 } | 1036 } |
| 1035 | 1037 |
| 1036 // Check that we can statically prove that lower bound of the index is | 1038 // Check that we can statically prove that lower bound of the index is |
| 1037 // non-negative under the assumption that all potentially non-positive | 1039 // non-negative under the assumption that all potentially non-positive |
| 1038 // symbols are positive. | 1040 // symbols are positive. |
| 1039 GrowableArray<ConstraintInstr*> positive_constraints( | 1041 GrowableArray<ConstraintInstr*> positive_constraints( |
| 1040 non_positive_symbols.length()); | 1042 non_positive_symbols.length()); |
| 1041 Range* positive_range = new Range( | 1043 Range* positive_range = new Range( |
| 1042 RangeBoundary::FromConstant(0), | 1044 RangeBoundary::FromConstant(0), |
| 1043 RangeBoundary::MaxConstant(RangeBoundary::kRangeBoundarySmi)); | 1045 RangeBoundary::MaxConstant(RangeBoundary::kRangeBoundarySmi)); |
| 1044 for (intptr_t i = 0; i < non_positive_symbols.length(); i++) { | 1046 for (intptr_t i = 0; i < non_positive_symbols.length(); i++) { |
| 1045 Definition* symbol = non_positive_symbols[i]; | 1047 Definition* symbol = non_positive_symbols[i]; |
| 1046 positive_constraints.Add(new ConstraintInstr( | 1048 positive_constraints.Add(new ConstraintInstr( |
| 1047 new Value(symbol), | 1049 new Value(symbol), |
| 1048 positive_range)); | 1050 positive_range)); |
| 1049 } | 1051 } |
| 1050 | 1052 |
| 1051 Definition* lower_bound = | 1053 Definition* lower_bound = |
| 1052 ConstructLowerBound(check->index()->definition(), check); | 1054 ConstructLowerBound(check->index()->definition(), check); |
| 1053 // No need to simplify lower bound before applying constraints as | 1055 // No need to simplify lower bound before applying constraints as |
| 1054 // we are not going to emit it. | 1056 // we are not going to emit it. |
| 1055 lower_bound = ApplyConstraints(lower_bound, check, &positive_constraints); | 1057 lower_bound = ApplyConstraints(lower_bound, check, &positive_constraints); |
| 1056 range_analysis_->AssignRangesRecursively(lower_bound); | 1058 range_analysis_->AssignRangesRecursively(lower_bound); |
| 1057 | 1059 |
| 1058 if (!RangeUtils::IsPositive(lower_bound->range())) { | 1060 if (!RangeUtils::IsPositive(lower_bound->range())) { |
| 1059 // Can't prove that lower bound is positive even with additional checks | 1061 // Can't prove that lower bound is positive even with additional checks |
| 1060 // against potentially non-positive symbols. Give up. | 1062 // against potentially non-positive symbols. Give up. |
| 1063 #ifndef PRODUCT |
| 1061 if (FLAG_support_il_printer && FLAG_trace_range_analysis) { | 1064 if (FLAG_support_il_printer && FLAG_trace_range_analysis) { |
| 1062 THR_Print("Failed to generalize %s index to %s" | 1065 THR_Print("Failed to generalize %s index to %s" |
| 1063 " (lower bound is not positive)\n", | 1066 " (lower bound is not positive)\n", |
| 1064 check->ToCString(), | 1067 check->ToCString(), |
| 1065 IndexBoundToCString(upper_bound)); | 1068 IndexBoundToCString(upper_bound)); |
| 1066 } | 1069 } |
| 1070 #endif // !PRODUCT |
| 1067 return; | 1071 return; |
| 1068 } | 1072 } |
| 1069 | 1073 |
| 1074 #ifndef PRODUCT |
| 1070 if (FLAG_support_il_printer && FLAG_trace_range_analysis) { | 1075 if (FLAG_support_il_printer && FLAG_trace_range_analysis) { |
| 1071 THR_Print("For %s computed index bounds [%s, %s]\n", | 1076 THR_Print("For %s computed index bounds [%s, %s]\n", |
| 1072 check->ToCString(), | 1077 check->ToCString(), |
| 1073 IndexBoundToCString(lower_bound), | 1078 IndexBoundToCString(lower_bound), |
| 1074 IndexBoundToCString(upper_bound)); | 1079 IndexBoundToCString(upper_bound)); |
| 1075 } | 1080 } |
| 1081 #endif // !PRODUCT |
| 1076 | 1082 |
| 1077 // At this point we know that 0 <= index < UpperBound(index) under | 1083 // At this point we know that 0 <= index < UpperBound(index) under |
| 1078 // certain preconditions. Start by emitting this preconditions. | 1084 // certain preconditions. Start by emitting this preconditions. |
| 1079 scheduler_.Start(); | 1085 scheduler_.Start(); |
| 1080 | 1086 |
| 1081 ConstantInstr* max_smi = | 1087 ConstantInstr* max_smi = |
| 1082 flow_graph_->GetConstant(Smi::Handle(Smi::New(Smi::kMaxValue))); | 1088 flow_graph_->GetConstant(Smi::Handle(Smi::New(Smi::kMaxValue))); |
| 1083 for (intptr_t i = 0; i < non_positive_symbols.length(); i++) { | 1089 for (intptr_t i = 0; i < non_positive_symbols.length(); i++) { |
| 1084 CheckArrayBoundInstr* precondition = new CheckArrayBoundInstr( | 1090 CheckArrayBoundInstr* precondition = new CheckArrayBoundInstr( |
| 1085 new Value(max_smi), | 1091 new Value(max_smi), |
| (...skipping 402 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1488 for (intptr_t i = 0; i < defn->InputCount(); i++) { | 1494 for (intptr_t i = 0; i < defn->InputCount(); i++) { |
| 1489 defn->InputAt(i)->set_definition( | 1495 defn->InputAt(i)->set_definition( |
| 1490 ApplyConstraints(defn->InputAt(i)->definition(), | 1496 ApplyConstraints(defn->InputAt(i)->definition(), |
| 1491 post_dominator, | 1497 post_dominator, |
| 1492 constraints)); | 1498 constraints)); |
| 1493 } | 1499 } |
| 1494 | 1500 |
| 1495 return defn; | 1501 return defn; |
| 1496 } | 1502 } |
| 1497 | 1503 |
| 1504 #ifndef PRODUCT |
| 1498 static void PrettyPrintIndexBoundRecursively(BufferFormatter* f, | 1505 static void PrettyPrintIndexBoundRecursively(BufferFormatter* f, |
| 1499 Definition* index_bound) { | 1506 Definition* index_bound) { |
| 1500 BinarySmiOpInstr* binary_op = index_bound->AsBinarySmiOp(); | 1507 BinarySmiOpInstr* binary_op = index_bound->AsBinarySmiOp(); |
| 1501 if (binary_op != NULL) { | 1508 if (binary_op != NULL) { |
| 1502 f->Print("("); | 1509 f->Print("("); |
| 1503 PrettyPrintIndexBoundRecursively(f, binary_op->left()->definition()); | 1510 PrettyPrintIndexBoundRecursively(f, binary_op->left()->definition()); |
| 1504 f->Print(" %s ", Token::Str(binary_op->op_kind())); | 1511 f->Print(" %s ", Token::Str(binary_op->op_kind())); |
| 1505 PrettyPrintIndexBoundRecursively(f, binary_op->right()->definition()); | 1512 PrettyPrintIndexBoundRecursively(f, binary_op->right()->definition()); |
| 1506 f->Print(")"); | 1513 f->Print(")"); |
| 1507 } else if (index_bound->IsConstant()) { | 1514 } else if (index_bound->IsConstant()) { |
| 1508 f->Print("%" Pd "", | 1515 f->Print("%" Pd "", |
| 1509 Smi::Cast(index_bound->AsConstant()->value()).Value()); | 1516 Smi::Cast(index_bound->AsConstant()->value()).Value()); |
| 1510 } else { | 1517 } else { |
| 1511 f->Print("v%" Pd "", index_bound->ssa_temp_index()); | 1518 f->Print("v%" Pd "", index_bound->ssa_temp_index()); |
| 1512 } | 1519 } |
| 1513 f->Print(" {%s}", Range::ToCString(index_bound->range())); | 1520 f->Print(" {%s}", Range::ToCString(index_bound->range())); |
| 1514 } | 1521 } |
| 1515 | 1522 |
| 1516 | 1523 |
| 1517 static const char* IndexBoundToCString(Definition* index_bound) { | 1524 static const char* IndexBoundToCString(Definition* index_bound) { |
| 1518 char buffer[1024]; | 1525 char buffer[1024]; |
| 1519 BufferFormatter f(buffer, sizeof(buffer)); | 1526 BufferFormatter f(buffer, sizeof(buffer)); |
| 1520 PrettyPrintIndexBoundRecursively(&f, index_bound); | 1527 PrettyPrintIndexBoundRecursively(&f, index_bound); |
| 1521 return Thread::Current()->zone()->MakeCopyOfString(buffer); | 1528 return Thread::Current()->zone()->MakeCopyOfString(buffer); |
| 1522 } | 1529 } |
| 1530 #endif // !PRODUCT |
| 1523 | 1531 |
| 1524 RangeAnalysis* range_analysis_; | 1532 RangeAnalysis* range_analysis_; |
| 1525 FlowGraph* flow_graph_; | 1533 FlowGraph* flow_graph_; |
| 1526 Scheduler scheduler_; | 1534 Scheduler scheduler_; |
| 1527 }; | 1535 }; |
| 1528 | 1536 |
| 1529 | 1537 |
| 1530 void RangeAnalysis::EliminateRedundantBoundsChecks() { | 1538 void RangeAnalysis::EliminateRedundantBoundsChecks() { |
| 1531 if (FLAG_array_bounds_check_elimination) { | 1539 if (FLAG_array_bounds_check_elimination) { |
| 1532 const Function& function = flow_graph_->function(); | 1540 const Function& function = flow_graph_->function(); |
| (...skipping 1628 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 3161 } | 3169 } |
| 3162 } while (CanonicalizeMaxBoundary(&max) || | 3170 } while (CanonicalizeMaxBoundary(&max) || |
| 3163 CanonicalizeMinBoundary(&canonical_length)); | 3171 CanonicalizeMinBoundary(&canonical_length)); |
| 3164 | 3172 |
| 3165 // Failed to prove that maximum is bounded with array length. | 3173 // Failed to prove that maximum is bounded with array length. |
| 3166 return false; | 3174 return false; |
| 3167 } | 3175 } |
| 3168 | 3176 |
| 3169 | 3177 |
| 3170 } // namespace dart | 3178 } // namespace dart |
| OLD | NEW |