Fix convergence issues in range analysis.

runtime/vm/flow_graph_optimizer.cc

 // Copyright (c) 2012, 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/flow_graph_builder.h"
 #include "vm/hash_map.h"
 #include "vm/il_printer.h"
 #include "vm/intermediate_language.h"
 #include "vm/object_store.h"
 #include "vm/parser.h"
 #include "vm/scopes.h"
 #include "vm/symbols.h"
 
 namespace dart {
 
 DECLARE_FLAG(bool, eliminate_type_checks);
 DECLARE_FLAG(bool, enable_type_checks);
 DEFINE_FLAG(bool, trace_optimization, false, "Print optimization details.");
 DECLARE_FLAG(bool, trace_type_check_elimination);
 DEFINE_FLAG(bool, use_cha, true, "Use class hierarchy analysis.");
 DEFINE_FLAG(bool, load_cse, true, "Use redundant load elimination.");
+DEFINE_FLAG(bool, trace_range_analysis, false, "Trace range analysis progress");
 
 void FlowGraphOptimizer::ApplyICData() {
   VisitBlocks();
 }
 
 
 static void ReplaceCurrentInstruction(ForwardInstructionIterator* it,
                                       Instruction* current,
                                       Instruction* replacement) {
   if ((replacement != NULL) && current->IsDefinition()) {
@@ skipping 1196 matching lines @@
 
   // Replace uses of the definition def that are dominated by instruction dom
   // with uses of other definition.
   void RenameDominatedUses(Definition* def,
                            Instruction* dom,
                            Definition* other);
 
   // Propagate range information until fix-point is reached.
   void InferRanges();
 
+  void ProcessWorklist(Definition::RangeOperator op);
+
   // Walk the dominator tree, initialize ranges for smi values and place them
   // to the worklist.
   void InitializeRangesRecursive(BlockEntryInstr* block);
 
   // Remove artificial Constraint instructions and replace them with actual
   // unconstrained definitions.
   void RemoveConstraints();
 
   void CreateWorklists();
 
   void AddToWorklist(Definition* value) {
     const intptr_t index = value->ssa_temp_index();
-    if (!in_inactive_worklist_->Contains(index)) {
-      in_inactive_worklist_->Add(index);
-      inactive_worklist_->Add(value);
+    if (!in_worklist_->Contains(index)) {
+      in_worklist_->Add(index);
+      worklist_.Add(value);
     }
   }
 
   bool IsWorklistEmpty() const {
-    return active_worklist_->is_empty();
+    return worklist_.is_empty();
+  }
+
+  Definition* RemoveLastFromWorklist() {
+    Definition* defn = worklist_.Last();
+    worklist_.RemoveLast();
+    ASSERT(in_worklist_->Contains(defn->ssa_temp_index()));
+    in_worklist_->Remove(defn->ssa_temp_index());
+    return defn;
   }
 
   void SwapWorklists();
 
   FlowGraph* flow_graph_;
 
   GrowableArray<Definition*> smi_values_;  // Value that are known to be smi.
   GrowableArray<CheckSmiInstr*> smi_checks_;  // All CheckSmi instructions.
 
   // 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_;
 
-  // Worklists using during range propagation.
-  ZoneGrowableArray<Definition*>* active_worklist_;
-  ZoneGrowableArray<Definition*>* inactive_worklist_;
-  BitVector* in_inactive_worklist_;
+  // Worklist used during range propagation.
+  GrowableArray<Definition*> worklist_;
+  BitVector* in_worklist_;
 
   DISALLOW_COPY_AND_ASSIGN(RangeAnalysis);
 };
 
 
 void RangeAnalysis::Analyze() {
   CollectSmiValues();
   InsertConstraints();
   InferRanges();
   RemoveConstraints();
@@ skipping 235 matching lines @@
 
   for (intptr_t i = 0; i < smi_values_.length(); i++) {
     InsertConstraintsFor(smi_values_[i]);
   }
 }
 
 
 void RangeAnalysis::InitializeRangesRecursive(BlockEntryInstr* block) {
   JoinEntryInstr* join = block->AsJoinEntry();
   if ((join != NULL) && (join->phis() != NULL)) {
     for (intptr_t i = 0; i < join->phis()->length(); ++i) {

[Florian Schneider, 2012/09/24 11:29:59]

Use PhiIterator here?

       PhiInstr* phi = (*join->phis())[i];
       if (phi == NULL) continue;
       if (smi_definitions_->Contains(phi->ssa_temp_index())) {
-        phi->InferRange();
+        phi->InferRange(Definition::kRangeInit);
         AddToWorklist(phi);
       }
     }
   }
 
   for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
     Definition* defn = it.Current()->AsDefinition();
     if ((defn != NULL) &&
         (defn->ssa_temp_index() != -1) &&
         smi_definitions_->Contains(defn->ssa_temp_index())) {
-      defn->InferRange();
+      defn->InferRange(Definition::kRangeInit);
       AddToWorklist(defn);
     }
   }
 
   for (intptr_t i = 0; i < block->dominated_blocks().length(); ++i) {
     InitializeRangesRecursive(block->dominated_blocks()[i]);
   }
 }
 
 
 void RangeAnalysis::CreateWorklists() {
-  active_worklist_ = new ZoneGrowableArray<Definition*>(10);
-  inactive_worklist_ = new ZoneGrowableArray<Definition*>(10);
-  in_inactive_worklist_ = new BitVector(
+  in_worklist_ = new BitVector(
       flow_graph_->current_ssa_temp_index());

[Florian Schneider, 2012/09/24 11:29:59]

Does it fit into the previous line?

 }
 
 
-void RangeAnalysis::SwapWorklists() {
-  ZoneGrowableArray<Definition*>* temp = active_worklist_;
-  active_worklist_ = inactive_worklist_;
-  inactive_worklist_ = temp;
-  inactive_worklist_->Clear();
-  in_inactive_worklist_->Clear();
+void RangeAnalysis::ProcessWorklist(Definition::RangeOperator op) {
+  // Iterate until fix point is reached.
+  while (!IsWorklistEmpty()) {
+    Definition* defn = RemoveLastFromWorklist();
+    if (FLAG_trace_range_analysis) {
+      OS::Print("infering range for v%"Pd" %s\n",
+                defn->ssa_temp_index(),
+                Range::ToCString(defn->range()));
+    }
+    if (defn->InferRange(op)) {  // Update the range.
+      if (FLAG_trace_range_analysis) {
+        OS::Print("  changed to %s\n", Range::ToCString(defn->range()));
+      }
+      // Range change. Place all uses to the worklist.
+      for (Value* use = defn->input_use_list();
+           use != NULL;
+           use = use->next_use()) {
+        Definition* use_defn = use->instruction()->AsDefinition();
+        if ((use_defn != NULL) &&
+            (use_defn->ssa_temp_index() != -1) &&
+            smi_definitions_->Contains(use_defn->ssa_temp_index())) {
+          AddToWorklist(use_defn);
+        }
+      }
+    }
+  }
 }
 
 
 void RangeAnalysis::InferRanges() {
   CreateWorklists();
 
   // Initialize bitvector for quick filtering of smi values.
   smi_definitions_ = new 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());
   }
   for (intptr_t i = 0; i < constraints_.length(); i++) {
     smi_definitions_->Add(constraints_[i]->ssa_temp_index());
   }
 
   // Infer initial values of ranges.
   InitializeRangesRecursive(flow_graph_->graph_entry());
 
-  // Active worklist is empty, inactive now contains all smi values.
-  SwapWorklists();
-
-  // Iterate until fix point is reached.
-  while (!IsWorklistEmpty()) {
-    for (intptr_t i = 0; i < active_worklist_->length(); i++) {
-      Definition* defn = (*active_worklist_)[i];
-      if (defn->InferRange()) {  // Update the range.
-        // Range change. Place all uses to the worklist.
-        for (Value* use = defn->input_use_list();
-             use != NULL;
-             use = use->next_use()) {
-          Definition* use_defn = use->instruction()->AsDefinition();
-          if ((use_defn != NULL) &&
-              (use_defn->ssa_temp_index() != -1) &&
-              smi_definitions_->Contains(use_defn->ssa_temp_index())) {
-            AddToWorklist(use_defn);
-          }
+  for (intptr_t i = 0; i < smi_values_.length(); i++) {
+    if (smi_values_[i]->IsPhi() &&
+        smi_values_[i]->InferRange(Definition::kRangeInit)) {
+      Definition* defn = smi_values_[i];
+      for (Value* use = defn->input_use_list();
+           use != NULL;
+           use = use->next_use()) {
+        Definition* use_defn = use->instruction()->AsDefinition();
+        if ((use_defn != NULL) &&
+            (use_defn->ssa_temp_index() != -1) &&
+            smi_definitions_->Contains(use_defn->ssa_temp_index())) {
+          AddToWorklist(use_defn);
         }
       }
     }
+  }
 
-    // Active worklist has been processed. Inactive contains all values which
-    // can be affected by changed ranges.
-    SwapWorklists();
+  if (FLAG_trace_range_analysis) {
+    OS::Print("---- after initialization -------\n");
+    FlowGraphPrinter printer(*flow_graph_);
+    printer.PrintBlocks();
+  }
+
+  if (FLAG_trace_range_analysis) {
+    OS::Print("---- widening ---------\n");
+  }
+  ProcessWorklist(Definition::kRangeWiden);
+
+  if (FLAG_trace_range_analysis) {
+    OS::Print("---- after widening -------\n");
+    FlowGraphPrinter printer(*flow_graph_);
+    printer.PrintBlocks();
+  }
+
+  for (intptr_t i = 0; i < smi_values_.length(); i++) {

[Florian Schneider, 2012/09/24 11:29:59]

I assume that you only add phis here because only phis can change their range in
the widening pass. Please add a comment.

+    if (smi_values_[i]->IsPhi()) AddToWorklist(smi_values_[i]);
+  }
+
+  if (FLAG_trace_range_analysis) {
+    OS::Print("---- narrowing ---------\n");
+  }
+  ProcessWorklist(Definition::kRangeNarrow);
+
+  if (FLAG_trace_range_analysis) {
+    OS::Print("---- after narrowing -------\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()) {
@@ skipping 1309 matching lines @@
        it.Advance()) {
     JoinEntryInstr* join = it.Current()->AsJoinEntry();
     if (join != NULL) join->EliminateUnreachablePhiInputs();
   }
 
   graph_->ComputeUseLists();
 }
 
 
 }  // namespace dart