When constant folding x == y take reachability of blocks into account.

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 7507 matching lines @@
 
 ConstantPropagator::ConstantPropagator(
     FlowGraph* graph,
     const GrowableArray<BlockEntryInstr*>& ignored)
     : FlowGraphVisitor(ignored),
       graph_(graph),
       unknown_(Object::unknown_constant()),
       non_constant_(Object::non_constant()),
       reachable_(new(graph->isolate()) BitVector(
           graph->isolate(), graph->preorder().length())),
-      definition_marks_(new(graph->isolate()) BitVector(
+      marked_phis_(new(graph->isolate()) BitVector(
           graph->isolate(), graph->max_virtual_register_number())),
       block_worklist_(),
-      definition_worklist_() {}
+      definition_worklist_(graph, 10) {}
 
 
 void ConstantPropagator::Optimize(FlowGraph* graph) {
   GrowableArray<BlockEntryInstr*> ignored;
   ConstantPropagator cp(graph, ignored);
   cp.Analyze();
   cp.Transform();
 }
 
 
 void ConstantPropagator::OptimizeBranches(FlowGraph* graph) {
   GrowableArray<BlockEntryInstr*> ignored;
   ConstantPropagator cp(graph, ignored);
   cp.Analyze();
   cp.Transform();
   cp.EliminateRedundantBranches();
 }
 
 
 void ConstantPropagator::SetReachable(BlockEntryInstr* block) {
   if (!reachable_->Contains(block->preorder_number())) {
     reachable_->Add(block->preorder_number());
     block_worklist_.Add(block);
   }
 }
 
 
-void ConstantPropagator::SetValue(Definition* definition, const Object& value) {
+bool ConstantPropagator::SetValue(Definition* definition, const Object& value) {
   // We would like to assert we only go up (toward non-constant) in the lattice.
   //
   // ASSERT(IsUnknown(definition->constant_value()) ||
   //        IsNonConstant(value) ||
   //        (definition->constant_value().raw() == value.raw()));
   //
   // But the final disjunct is not true (e.g., mint or double constants are
   // heap-allocated and so not necessarily pointer-equal on each iteration).
   if (definition->constant_value().raw() != value.raw()) {
     definition->constant_value() = value.raw();
     if (definition->input_use_list() != NULL) {
-      ASSERT(definition->HasSSATemp());
-      if (!definition_marks_->Contains(definition->ssa_temp_index())) {
-        definition_worklist_.Add(definition);
-        definition_marks_->Add(definition->ssa_temp_index());
-      }
+      definition_worklist_.Add(definition);
     }
+    return true;
   }
+  return false;
 }
 
 
 // Compute the join of two values in the lattice, assign it to the first.
 void ConstantPropagator::Join(Object* left, const Object& right) {
   // Join(non-constant, X) = non-constant
   // Join(X, unknown)      = X
   if (IsNonConstant(*left) || IsUnknown(right)) return;
 
   // Join(unknown, X)      = X
@@ skipping 145 matching lines @@
 
 
 void ConstantPropagator::VisitCheckArrayBound(CheckArrayBoundInstr* instr) { }
 
 
 void ConstantPropagator::VisitDeoptimize(DeoptimizeInstr* instr) {
   // TODO(vegorov) remove all code after DeoptimizeInstr as dead.
 }
 
 
+Definition* ConstantPropagator::UnwrapPhi(Definition* defn) {
+  if (defn->IsPhi()) {
+    JoinEntryInstr* block = defn->AsPhi()->block();
+
+    Definition* input = NULL;
+    for (intptr_t i = 0; i < defn->InputCount(); ++i) {
+      if (reachable_->Contains(block->PredecessorAt(i)->preorder_number())) {
+        if (input == NULL) {
+          input = defn->InputAt(i)->definition();
+        } else {
+          return defn;
+        }
+      }
+    }
+
+    return input;
+  }
+
+  return defn;
+}
+
+
+void ConstantPropagator::MarkPhi(Definition* phi) {
+  ASSERT(phi->IsPhi());
+  marked_phis_->Add(phi->ssa_temp_index());
+}
+
+
 // --------------------------------------------------------------------------
 // Analysis of definitions.  Compute the constant value.  If it has changed
 // and the definition has input uses, add the definition to the definition
 // worklist so that the used can be processed.
 void ConstantPropagator::VisitPhi(PhiInstr* instr) {
   // Compute the join over all the reachable predecessor values.
   JoinEntryInstr* block = instr->block();
   Object& value = Object::ZoneHandle(I, Unknown());
   for (intptr_t pred_idx = 0; pred_idx < instr->InputCount(); ++pred_idx) {
     if (reachable_->Contains(
             block->PredecessorAt(pred_idx)->preorder_number())) {
       Join(&value,
            instr->InputAt(pred_idx)->definition()->constant_value());
     }
   }
-  SetValue(instr, value);
+  if (!SetValue(instr, value) &&
+      marked_phis_->Contains(instr->ssa_temp_index())) {
+    marked_phis_->Remove(instr->ssa_temp_index());
+    definition_worklist_.Add(instr);
+  }
 }
 
 
 void ConstantPropagator::VisitRedefinition(RedefinitionInstr* instr) {
   SetValue(instr, instr->value()->definition()->constant_value());
 }
 
 
 void ConstantPropagator::VisitParameter(ParameterInstr* instr) {
   SetValue(instr, non_constant_);
@@ skipping 95 matching lines @@
     ASSERT(value.IsBool());
     bool result = Bool::Cast(value).value();
     SetValue(instr,
              Smi::Handle(I, Smi::New(
                  result ? instr->if_true() : instr->if_false())));
   }
 }
 
 
 void ConstantPropagator::VisitStrictCompare(StrictCompareInstr* instr) {
-  const Object& left = instr->left()->definition()->constant_value();
-  const Object& right = instr->right()->definition()->constant_value();
+  Definition* left_defn = instr->left()->definition();
+  Definition* right_defn = instr->right()->definition();
 
-  if (instr->left()->definition() == instr->right()->definition()) {
+  Definition* unwrapped_left_defn = UnwrapPhi(left_defn);
+  Definition* unwrapped_right_defn = UnwrapPhi(right_defn);
+  if (unwrapped_left_defn == unwrapped_right_defn) {
     // Fold x === x, and x !== x to true/false.
     SetValue(instr, Bool::Get(instr->kind() == Token::kEQ_STRICT));
+    if (unwrapped_left_defn != left_defn) {
+      MarkPhi(left_defn);
+    }
+    if (unwrapped_right_defn != right_defn) {
+      MarkPhi(right_defn);
+    }
     return;
   }
 
+  const Object& left = left_defn->constant_value();
+  const Object& right = right_defn->constant_value();
   if (IsNonConstant(left) || IsNonConstant(right)) {
     // TODO(vegorov): incorporate nullability information into the lattice.
     if ((left.IsNull() && instr->right()->Type()->HasDecidableNullability()) ||
         (right.IsNull() && instr->left()->Type()->HasDecidableNullability())) {
       bool result = left.IsNull() ? instr->right()->Type()->IsNull()
                                   : instr->left()->Type()->IsNull();
       if (instr->kind() == Token::kNE_STRICT) {
         result = !result;
       }
       SetValue(instr, Bool::Get(result));
@@ skipping 57 matching lines @@
   }
 }
 
 
 void ConstantPropagator::VisitTestCids(TestCidsInstr* instr) {
   SetValue(instr, non_constant_);
 }
 
 
 void ConstantPropagator::VisitEqualityCompare(EqualityCompareInstr* instr) {
-  const Object& left = instr->left()->definition()->constant_value();
-  const Object& right = instr->right()->definition()->constant_value();
+  Definition* left_defn = instr->left()->definition();
+  Definition* right_defn = instr->right()->definition();
 
-  if (instr->left()->definition() == instr->right()->definition()) {
+  if (RawObject::IsIntegerClassId(instr->operation_cid())) {
     // Fold x == x, and x != x to true/false for numbers comparisons.
-    if (RawObject::IsIntegerClassId(instr->operation_cid())) {
-      return SetValue(instr, Bool::Get(instr->kind() == Token::kEQ));
+    Definition* unwrapped_left_defn = UnwrapPhi(left_defn);
+    Definition* unwrapped_right_defn = UnwrapPhi(right_defn);
+    if (unwrapped_left_defn == unwrapped_right_defn) {
+      // Fold x === x, and x !== x to true/false.
+      SetValue(instr, Bool::Get(instr->kind() == Token::kEQ));
+      if (unwrapped_left_defn != left_defn) {
+        MarkPhi(left_defn);
+      }
+      if (unwrapped_right_defn != right_defn) {
+        MarkPhi(right_defn);
+      }
+      return;
     }
   }
 
+  const Object& left = left_defn->constant_value();
+  const Object& right = right_defn->constant_value();
   if (IsNonConstant(left) || IsNonConstant(right)) {
     SetValue(instr, non_constant_);
   } else if (IsConstant(left) && IsConstant(right)) {
     if (left.IsInteger() && right.IsInteger()) {
       const bool result = CompareIntegers(instr->kind(),
                                           Integer::Cast(left),
                                           Integer::Cast(right));
       SetValue(instr, Bool::Get(result));
     } else if (left.IsString() && right.IsString()) {
       const bool result = String::Cast(left).Equals(String::Cast(right));
@@ skipping 808 matching lines @@
 }
 
 
 void ConstantPropagator::Analyze() {
   GraphEntryInstr* entry = graph_->graph_entry();
   reachable_->Add(entry->preorder_number());
   block_worklist_.Add(entry);
 
   while (true) {
     if (block_worklist_.is_empty()) {
-      if (definition_worklist_.is_empty()) break;
+      if (definition_worklist_.IsEmpty()) break;
       Definition* definition = definition_worklist_.RemoveLast();
-      definition_marks_->Remove(definition->ssa_temp_index());
       Value* use = definition->input_use_list();
       while (use != NULL) {
         use->instruction()->Accept(this);
         use = use->next_use();
       }
     } else {
       BlockEntryInstr* block = block_worklist_.RemoveLast();
       block->Accept(this);
     }
   }
@@ skipping 1202 matching lines @@
 
   // Insert materializations at environment uses.
   for (intptr_t i = 0; i < exits_collector_.exits().length(); i++) {
     CreateMaterializationAt(
         exits_collector_.exits()[i], alloc, *slots);
   }
 }
 
 
 }  // namespace dart