Extend Range analysis to 64-bit range and mint operations

runtime/vm/flow_graph_optimizer.cc

 // Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/flow_graph_optimizer.h"
 
 #include "vm/bit_vector.h"
 #include "vm/cha.h"
 #include "vm/cpu.h"
 #include "vm/dart_entry.h"
@@ skipping 4523 matching lines @@
       : flow_graph_(flow_graph),
         marked_defns_(NULL) { }
 
   // Infer ranges for all values and remove overflow checks from binary smi
   // operations when proven redundant.
   void Analyze();
 
  private:
   // Collect all values that were proven to be smi in smi_values_ array and all
   // CheckSmi instructions in smi_check_ array.
-  void CollectSmiValues();
+  void CollectValues();
 
   // Iterate over smi values and constrain them at branch successors.
   // Additionally constraint values after CheckSmi instructions.
   void InsertConstraints();
 
   // Iterate over uses of the given definition and discover branches that
   // constrain it. Insert appropriate Constraint instructions at true
   // and false successor and rename all dominated uses to refer to a
   // Constraint instead of this definition.
   void InsertConstraintsFor(Definition* defn);
@@ skipping 50 matching lines @@
   // Remove artificial Constraint instructions and replace them with actual
   // unconstrained definitions.
   void RemoveConstraints();
 
   Range* ConstraintRange(Token::Kind op, Definition* boundary);
 
   Isolate* isolate() const { return flow_graph_->isolate(); }
 
   FlowGraph* flow_graph_;
 
-  GrowableArray<Definition*> smi_values_;  // Value that are known to be smi.
-  GrowableArray<CheckSmiInstr*> smi_checks_;  // All CheckSmi instructions.
+  // Value that are known to be smi or mint.
+  GrowableArray<Definition*> values_;
+  // All CheckSmi instructions.
+  GrowableArray<CheckSmiInstr*> smi_checks_;
 
   // All Constraints inserted during InsertConstraints phase. They are treated
   // as smi values.
   GrowableArray<ConstraintInstr*> constraints_;
 
-  // Bitvector for a quick filtering of known smi values.
-  BitVector* smi_definitions_;
+  // Bitvector for a quick filtering of known smi or mint values.
+  BitVector* definitions_;
 
   // Worklist for induction variables analysis.
   GrowableArray<Definition*> worklist_;
   BitVector* marked_defns_;
 
   DISALLOW_COPY_AND_ASSIGN(RangeAnalysis);
 };
 
 
 void RangeAnalysis::Analyze() {
-  CollectSmiValues();
+  CollectValues();
   InsertConstraints();
   InferRanges();
   RemoveConstraints();
 }
 
 
-void RangeAnalysis::CollectSmiValues() {
+void RangeAnalysis::CollectValues() {
   const GrowableArray<Definition*>& initial =
       *flow_graph_->graph_entry()->initial_definitions();
   for (intptr_t i = 0; i < initial.length(); ++i) {
     Definition* current = initial[i];
     if (current->Type()->ToCid() == kSmiCid) {
-      smi_values_.Add(current);
+      values_.Add(current);
+    } else if (current->IsMintDefinition()) {
+      values_.Add(current);
     }
   }
 
   for (BlockIterator block_it = flow_graph_->reverse_postorder_iterator();
        !block_it.Done();
        block_it.Advance()) {
     BlockEntryInstr* block = block_it.Current();
 
 
     if (block->IsGraphEntry() || block->IsCatchBlockEntry()) {
       const GrowableArray<Definition*>& initial = block->IsGraphEntry()
           ? *block->AsGraphEntry()->initial_definitions()
           : *block->AsCatchBlockEntry()->initial_definitions();
       for (intptr_t i = 0; i < initial.length(); ++i) {
         Definition* current = initial[i];
         if (current->Type()->ToCid() == kSmiCid) {
-          smi_values_.Add(current);
+          values_.Add(current);
+        } else if (current->IsMintDefinition()) {
+          values_.Add(current);
         }
       }
     }
 
     JoinEntryInstr* join = block->AsJoinEntry();
     if (join != NULL) {
       for (PhiIterator phi_it(join); !phi_it.Done(); phi_it.Advance()) {
         PhiInstr* current = phi_it.Current();
         if (current->Type()->ToCid() == kSmiCid) {
-          smi_values_.Add(current);
+          values_.Add(current);
         }
       }
     }
 
     for (ForwardInstructionIterator instr_it(block);
          !instr_it.Done();
          instr_it.Advance()) {
       Instruction* current = instr_it.Current();
       Definition* defn = current->AsDefinition();
       if (defn != NULL) {
         if ((defn->Type()->ToCid() == kSmiCid) &&
             (defn->ssa_temp_index() != -1)) {
-          smi_values_.Add(defn);
+          values_.Add(defn);
+        } else if ((defn->IsMintDefinition()) &&
+                   (defn->ssa_temp_index() != -1)) {
+          values_.Add(defn);
         }
       } else if (current->IsCheckSmi()) {
         smi_checks_.Add(current->AsCheckSmi());
       }
     }
   }
 }
 
 
 // Returns true if use is dominated by the given instruction.
@@ skipping 144 matching lines @@
             branch->false_successor());
     // Mark false_constraint an artificial use of boundary. This ensures
     // that constraint's range is recalculated if boundary's range changes.
     if (false_constraint != NULL) {
       false_constraint->AddDependency(boundary);
       false_constraint->set_target(branch->false_successor());
     }
   }
 }
 
+
 void RangeAnalysis::InsertConstraintsFor(Definition* defn) {
   for (Value* use = defn->input_use_list();
        use != NULL;
        use = use->next_use()) {
     if (use->instruction()->IsBranch()) {
       ConstrainValueAfterBranch(defn, use);
     } else if (use->instruction()->IsCheckArrayBound()) {
       ConstrainValueAfterCheckArrayBound(
           defn,
           use->instruction()->AsCheckArrayBound(),
@@ skipping 18 matching lines @@
         RangeBoundary::FromDefinition(index, 1),
         RangeBoundary::MaxSmi());
   }
   InsertConstraintFor(defn, constraint_range, check);
 }
 
 
 void RangeAnalysis::InsertConstraints() {
   for (intptr_t i = 0; i < smi_checks_.length(); i++) {
     CheckSmiInstr* check = smi_checks_[i];
-    InsertConstraintFor(check->value()->definition(), Range::Unknown(), check);
+    ConstraintInstr* constraint =
+        InsertConstraintFor(check->value()->definition(),
+                            Range::UnknownSmi(),
+                            check);
+    if (constraint == NULL) {
+      // No constraint was needed.
+      continue;
+    }
+    // Mark the constraint's value's reaching type as smi.
+    CompileType* smi_compile_type =
+        ZoneCompileType::Wrap(CompileType::FromCid(kSmiCid));
+    constraint->value()->SetReachingType(smi_compile_type);
   }
 
-  for (intptr_t i = 0; i < smi_values_.length(); i++) {
-    InsertConstraintsFor(smi_values_[i]);
+  for (intptr_t i = 0; i < values_.length(); i++) {
+    InsertConstraintsFor(values_[i]);
   }
 
   for (intptr_t i = 0; i < constraints_.length(); i++) {
     InsertConstraintsFor(constraints_[i]);
   }
 }
 
 
 void RangeAnalysis::ResetWorklist() {
   if (marked_defns_ == NULL) {
@@ skipping 17 matching lines @@
   }
 }
 
 
 RangeAnalysis::Direction RangeAnalysis::ToDirection(Value* val) {
   if (val->BindsToConstant()) {
     return (Smi::Cast(val->BoundConstant()).Value() >= 0) ? kPositive
                                                           : kNegative;
   } else if (val->definition()->range() != NULL) {
     Range* range = val->definition()->range();
-    if (Range::ConstantMin(range).value() >= 0) {
+    if (Range::ConstantMin(range).ConstantValue() >= 0) {
       return kPositive;
-    } else if (Range::ConstantMax(range).value() <= 0) {
+    } else if (Range::ConstantMax(range).ConstantValue() <= 0) {
       return kNegative;
     }
   }
   return kUnknown;
 }
 
 
 Range* RangeAnalysis::InferInductionVariableRange(JoinEntryInstr* loop_header,
                                                   PhiInstr* var) {
   BitVector* loop_info = loop_header->loop_info();
@@ skipping 77 matching lines @@
     case kPositive:
       return new(I) Range(RangeBoundary::FromDefinition(initial_value),
                           RangeBoundary::MaxSmi());
 
     case kNegative:
       return new(I) Range(RangeBoundary::MinSmi(),
                           RangeBoundary::FromDefinition(initial_value));
 
     case kUnknown:
     case kBoth:
-      return Range::Unknown();
+      return Range::UnknownSmi();
   }
 
   UNREACHABLE();
   return NULL;
 }
 
 
 void RangeAnalysis::InferRangesRecursive(BlockEntryInstr* block) {
   JoinEntryInstr* join = block->AsJoinEntry();
   if (join != NULL) {
     const bool is_loop_header = (join->loop_info() != NULL);
     for (PhiIterator it(join); !it.Done(); it.Advance()) {
       PhiInstr* phi = it.Current();
-      if (smi_definitions_->Contains(phi->ssa_temp_index())) {
+      if (definitions_->Contains(phi->ssa_temp_index())) {
         if (is_loop_header) {
           // Try recognizing simple induction variables.
           Range* range = InferInductionVariableRange(join, phi);
           if (range != NULL) {
             phi->range_ = range;
             continue;
           }
         }
 
         phi->InferRange();
       }
     }
   }
 
   for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
     Instruction* current = it.Current();
 
     Definition* defn = current->AsDefinition();
     if ((defn != NULL) &&
         (defn->ssa_temp_index() != -1) &&
-        smi_definitions_->Contains(defn->ssa_temp_index())) {
+        definitions_->Contains(defn->ssa_temp_index())) {
       defn->InferRange();
     } else if (FLAG_array_bounds_check_elimination &&
                current->IsCheckArrayBound()) {
       CheckArrayBoundInstr* check = current->AsCheckArrayBound();
       RangeBoundary array_length =
           RangeBoundary::FromDefinition(check->length()->definition());
       if (check->IsRedundant(array_length)) {
         it.RemoveCurrentFromGraph();
       }
     }
   }
 
   for (intptr_t i = 0; i < block->dominated_blocks().length(); ++i) {
     InferRangesRecursive(block->dominated_blocks()[i]);
   }
 }
 
 
 void RangeAnalysis::InferRanges() {
-  // Initialize bitvector for quick filtering of smi values.
-  smi_definitions_ = new(I) BitVector(flow_graph_->current_ssa_temp_index());
-  for (intptr_t i = 0; i < smi_values_.length(); i++) {
-    smi_definitions_->Add(smi_values_[i]->ssa_temp_index());
+  if (FLAG_trace_range_analysis) {
+    OS::Print("---- before range analysis -------\n");
+    FlowGraphPrinter printer(*flow_graph_);
+    printer.PrintBlocks();
+  }
+  // Initialize bitvector for quick filtering of int values.
+  definitions_ =
+      new(I) BitVector(flow_graph_->current_ssa_temp_index());
+  for (intptr_t i = 0; i < values_.length(); i++) {
+    definitions_->Add(values_[i]->ssa_temp_index());
   }
   for (intptr_t i = 0; i < constraints_.length(); i++) {
-    smi_definitions_->Add(constraints_[i]->ssa_temp_index());
+    definitions_->Add(constraints_[i]->ssa_temp_index());
   }
 
   // Infer initial values of ranges.
   const GrowableArray<Definition*>& initial =
       *flow_graph_->graph_entry()->initial_definitions();
   for (intptr_t i = 0; i < initial.length(); ++i) {
     Definition* definition = initial[i];
-    if (smi_definitions_->Contains(definition->ssa_temp_index())) {
+    if (definitions_->Contains(definition->ssa_temp_index())) {
       definition->InferRange();
     }
   }
   InferRangesRecursive(flow_graph_->graph_entry());
 
   if (FLAG_trace_range_analysis) {
     OS::Print("---- after range analysis -------\n");
     FlowGraphPrinter printer(*flow_graph_);
     printer.PrintBlocks();
   }
 }
 
 
 void RangeAnalysis::RemoveConstraints() {
   for (intptr_t i = 0; i < constraints_.length(); i++) {
     Definition* def = constraints_[i]->value()->definition();
     // Some constraints might be constraining constraints. Unwind the chain of
     // constraints until we reach the actual definition.
     while (def->IsConstraint()) {
       def = def->AsConstraint()->value()->definition();
     }
     constraints_[i]->ReplaceUsesWith(def);
     constraints_[i]->RemoveFromGraph();
   }
 }
 
 
-void FlowGraphOptimizer::InferSmiRanges() {
+void FlowGraphOptimizer::InferIntRanges() {
   RangeAnalysis range_analysis(flow_graph_);
   range_analysis.Analyze();
 }
 
 
 void TryCatchAnalyzer::Optimize(FlowGraph* flow_graph) {
   // For every catch-block: Iterate over all call instructions inside the
   // corresponding try-block and figure out for each environment value if it
   // is the same constant at all calls. If yes, replace the initial definition
   // at the catch-entry with this constant.
@@ skipping 4663 matching lines @@
   }
 
   // Insert materializations at environment uses.
   for (intptr_t i = 0; i < exits.length(); i++) {
     CreateMaterializationAt(exits[i], alloc, alloc->cls(), *slots);
   }
 }
 
 
 }  // namespace dart