Use range analysis to improve constant propagation.

runtime/vm/intermediate_language.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/intermediate_language.h"
 
 #include "vm/bit_vector.h"
 #include "vm/dart_entry.h"
 #include "vm/flow_graph_allocator.h"
 #include "vm/flow_graph_builder.h"
@@ skipping 10 matching lines @@
 namespace dart {
 
 DEFINE_FLAG(bool, new_identity_spec, true,
     "Use new identity check rules for numbers.");
 DEFINE_FLAG(bool, propagate_ic_data, true,
     "Propagate IC data from unoptimized to optimized IC calls.");
 DECLARE_FLAG(bool, enable_type_checks);
 DECLARE_FLAG(bool, eliminate_type_checks);
 DECLARE_FLAG(int, max_polymorphic_checks);
 DECLARE_FLAG(bool, trace_optimization);
+DECLARE_FLAG(bool, trace_constant_propagation);
 
 Definition::Definition()
     : range_(NULL),
       type_(NULL),
       temp_index_(-1),
       ssa_temp_index_(-1),
       input_use_list_(NULL),
       env_use_list_(NULL),
       use_kind_(kValue),  // Phis and parameters rely on this default.
       constant_value_(Object::ZoneHandle(ConstantPropagator::Unknown())) {
@@ skipping 560 matching lines @@
     UnuseAllInputs();
   }
   set_previous(NULL);
   set_next(NULL);
 }
 
 
 BranchInstr::BranchInstr(ComparisonInstr* comparison, bool is_checked)
     : comparison_(comparison),
       is_checked_(is_checked),
-      constrained_type_(NULL) {
+      constrained_type_(NULL),
+      constant_target_(NULL) {
   for (intptr_t i = comparison->InputCount() - 1; i >= 0; --i) {
     comparison->InputAt(i)->set_instruction(this);
   }
 }
 
 
 void BranchInstr::RawSetInputAt(intptr_t i, Value* value) {
   comparison()->RawSetInputAt(i, value);
 }
 
@@ skipping 1328 matching lines @@
                CanonicalizeMaxBoundary(&canonical_b));
     }
 
     if (max.IsUnknown()) {
       max = RangeBoundary::Min(Range::ConstantMax(value_range),
                                Range::ConstantMax(constraint()));
     }
   }
 
   range_ = new Range(min, max);
+
+  // Mark branches that generate unsatisfiable constraints as constant.
+  if (target() != NULL && range_->IsUnsatisfiable()) {
+    BranchInstr* branch =
+        target()->PredecessorAt(0)->last_instruction()->AsBranch();
+    if (target() == branch->true_successor()) {
+      // True unreachable.
+      if (FLAG_trace_constant_propagation) {
+        OS::Print("Range analysis: True unreachable (B%"Pd")\n",
+                  branch->true_successor()->block_id());
+      }
+      branch->set_constant_target(branch->false_successor());
+    } else {
+      ASSERT(target() == branch->false_successor());
+      // False unreachable.
+      if (FLAG_trace_constant_propagation) {
+        OS::Print("Range analysis: False unreachable (B%"Pd")\n",
+                  branch->false_successor()->block_id());
+      }
+      branch->set_constant_target(branch->true_successor());
+    }
+  }
 }
 
 
 void LoadFieldInstr::InferRange() {
   if ((range_ == NULL) &&
       ((recognized_kind() == MethodRecognizer::kObjectArrayLength) ||
        (recognized_kind() == MethodRecognizer::kImmutableArrayLength))) {
     range_ = new Range(RangeBoundary::FromConstant(0),
                        RangeBoundary::FromConstant(Array::kMaxElements));
     return;
@@ skipping 215 matching lines @@
 
 
 // Inclusive.
 bool Range::IsWithin(intptr_t min_int, intptr_t max_int) const {
   if (min().LowerBound().value() < min_int) return false;
   if (max().UpperBound().value() > max_int) return false;
   return true;
 }
 
 
+bool Range::IsUnsatisfiable() const {
+  // Constant case: For example [0, -1].
+  if (Range::ConstantMin(this).value() > Range::ConstantMax(this).value()) {
+    return true;
+  }
+  // Symbol case: For example [v+1, v].
+  if (DependOnSameSymbol(min(), max()) && min().offset() > max().offset()) {
+    return true;
+  }
+  return false;
+}
+
+
 bool CheckArrayBoundInstr::IsFixedLengthArrayType(intptr_t cid) {
   return LoadFieldInstr::IsFixedLengthArrayCid(cid);
 }
 
 
 bool CheckArrayBoundInstr::IsRedundant(RangeBoundary length) {
   // Check that array has an immutable length.
   if (!IsFixedLengthArrayType(array_type())) {
     return false;
   }
@@ skipping 135 matching lines @@
     default:
       UNREACHABLE();
   }
   return kPowRuntimeEntry;
 }
 
 
 #undef __
 
 }  // namespace dart