dart::BoundsCheckGeneralizer Class Reference

Public Member Functions
	BoundsCheckGeneralizer (RangeAnalysis *range_analysis, FlowGraph *flow_graph)
void	TryGeneralize (CheckArrayBoundInstr *check)

Static Public Member Functions
static void	RemoveGeneralizedCheck (CheckArrayBoundInstr *check)

Detailed Description

Definition at line 743 of file range_analysis.cc.

Constructor & Destructor Documentation

BoundsCheckGeneralizer()

dart::BoundsCheckGeneralizer::BoundsCheckGeneralizer ( RangeAnalysis *  range_analysis, FlowGraph *  flow_graph  )

inline

Definition at line 745 of file range_analysis.cc.

      : range_analysis_(range_analysis),
        flow_graph_(flow_graph),
        scheduler_(flow_graph) {}

Member Function Documentation

RemoveGeneralizedCheck()

static void dart::BoundsCheckGeneralizer::RemoveGeneralizedCheck ( CheckArrayBoundInstr *  check )

inlinestatic

Definition at line 886 of file range_analysis.cc.

                                                                  {
    BinarySmiOpInstr* binary_op = check->index()->definition()->AsBinarySmiOp();
    if (binary_op != nullptr) {
      binary_op->set_can_overflow(false);
    }
    check->ReplaceUsesWith(check->index()->definition());
    check->RemoveFromGraph();
  }

TryGeneralize()

void dart::BoundsCheckGeneralizer::TryGeneralize ( CheckArrayBoundInstr *  check )

inline

Definition at line 750 of file range_analysis.cc.

                                                  {
    Definition* upper_bound =
        ConstructUpperBound(check->index()->definition(), check);
    if (upper_bound == UnwrapConstraint(check->index()->definition())) {
      // Unable to construct upper bound for the index.
      if (FLAG_support_il_printer && FLAG_trace_range_analysis) {
        THR_Print("Failed to construct upper bound for %s index\n",
                  check->ToCString());
      }
      return;
    }
 
    // Re-associate subexpressions inside upper_bound to collect all constants
    // together. This will expose more redundancies when we are going to emit
    // upper bound through scheduler.
    if (!Simplify(&upper_bound, nullptr)) {
      if (FLAG_support_il_printer && FLAG_trace_range_analysis) {
        THR_Print("Failed to simplify upper bound for %s index\n",
                  check->ToCString());
      }
      return;
    }
    upper_bound = ApplyConstraints(upper_bound, check);
    range_analysis_->AssignRangesRecursively(upper_bound);
 
    // We are going to constrain any symbols participating in + and * operations
    // to guarantee that they are positive. Find all symbols that need
    // constraining. If there is a subtraction subexpression with non-positive
    // range give up on generalization for simplicity.
    GrowableArray<Definition*> non_positive_symbols;
    if (!FindNonPositiveSymbols(&non_positive_symbols, upper_bound)) {
#ifndef PRODUCT
      if (FLAG_support_il_printer && FLAG_trace_range_analysis) {
        THR_Print(
            "Failed to generalize %s index to %s"
            " (can't ensure positivity)\n",
            check->ToCString(), IndexBoundToCString(upper_bound));
      }
#endif  // !PRODUCT
      return;
    }
 
    // Check that we can statically prove that lower bound of the index is
    // non-negative under the assumption that all potentially non-positive
    // symbols are positive.
    GrowableArray<ConstraintInstr*> positive_constraints(
        non_positive_symbols.length());
    Range* positive_range =
        new Range(RangeBoundary::FromConstant(0),
                  RangeBoundary::MaxConstant(RangeBoundary::kRangeBoundarySmi));
    for (intptr_t i = 0; i < non_positive_symbols.length(); i++) {
      Definition* symbol = non_positive_symbols[i];
      positive_constraints.Add(
          new ConstraintInstr(new Value(symbol), positive_range));
    }
 
    Definition* lower_bound =
        ConstructLowerBound(check->index()->definition(), check);
    // No need to simplify lower bound before applying constraints as
    // we are not going to emit it.
    lower_bound = ApplyConstraints(lower_bound, check, &positive_constraints);
    range_analysis_->AssignRangesRecursively(lower_bound);
 
    if (!RangeUtils::IsPositive(lower_bound->range())) {
// Can't prove that lower bound is positive even with additional checks
// against potentially non-positive symbols. Give up.
#ifndef PRODUCT
      if (FLAG_support_il_printer && FLAG_trace_range_analysis) {
        THR_Print(
            "Failed to generalize %s index to %s"
            " (lower bound is not positive)\n",
            check->ToCString(), IndexBoundToCString(upper_bound));
      }
#endif  // !PRODUCT
      return;
    }
 
#ifndef PRODUCT
    if (FLAG_support_il_printer && FLAG_trace_range_analysis) {
      THR_Print("For %s computed index bounds [%s, %s]\n", check->ToCString(),
                IndexBoundToCString(lower_bound),
                IndexBoundToCString(upper_bound));
    }
#endif  // !PRODUCT
 
    // At this point we know that 0 <= index < UpperBound(index) under
    // certain preconditions. Start by emitting this preconditions.
    scheduler_.Start();
 
    // AOT should only see non-deopting GenericCheckBound.
    ASSERT(!CompilerState::Current().is_aot());
 
    ConstantInstr* max_smi = flow_graph_->GetConstant(
        Smi::Handle(Smi::New(compiler::target::kSmiMax)));
    for (intptr_t i = 0; i < non_positive_symbols.length(); i++) {
      CheckArrayBoundInstr* precondition = new CheckArrayBoundInstr(
          new Value(max_smi), new Value(non_positive_symbols[i]),
          DeoptId::kNone);
      precondition->mark_generalized();
      precondition = scheduler_.Emit(precondition, check);
      if (precondition == nullptr) {
        if (FLAG_trace_range_analysis) {
          THR_Print("  => failed to insert positivity constraint\n");
        }
        scheduler_.Rollback();
        return;
      }
    }
 
    CheckArrayBoundInstr* new_check = new CheckArrayBoundInstr(
        new Value(UnwrapConstraint(check->length()->definition())),
        new Value(upper_bound), DeoptId::kNone);
    new_check->mark_generalized();
    if (new_check->IsRedundant()) {
      if (FLAG_trace_range_analysis) {
        THR_Print("  => generalized check is redundant\n");
      }
      RemoveGeneralizedCheck(check);
      return;
    }
 
    new_check = scheduler_.Emit(new_check, check);
    if (new_check != nullptr) {
      if (FLAG_trace_range_analysis) {
        THR_Print("  => generalized check was hoisted into B%" Pd "\n",
                  new_check->GetBlock()->block_id());
      }
      RemoveGeneralizedCheck(check);
    } else {
      if (FLAG_trace_range_analysis) {
        THR_Print("  => generalized check can't be hoisted\n");
      }
      scheduler_.Rollback();
    }
  }

---

The documentation for this class was generated from the following file:

• third_party/dart-lang/sdk/runtime/vm/compiler/backend/range_analysis.cc