Merge (x & y) == 0 pattern to emit a single test instruction.

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 589 matching lines @@
   set_previous(NULL);
   set_next(NULL);
 }
 
 
 BranchInstr::BranchInstr(ComparisonInstr* comparison, bool is_checked)
     : comparison_(comparison),
       is_checked_(is_checked),
       constrained_type_(NULL),
       constant_target_(NULL) {
+  ASSERT(comparison->env() == 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);
 }
 
 
 // A misleadingly named function for use in template functions that replace
 // both definitions with definitions and branch comparisons with
 // comparisons.  In the branch case, leave the branch intact and replace its
 // comparison with a new comparison not currently in the graph.
 void BranchInstr::ReplaceWith(ComparisonInstr* other,
                               ForwardInstructionIterator* ignored) {
   SetComparison(other);
 }
 
 
-void BranchInstr::SetComparison(ComparisonInstr* comp) {
-  for (intptr_t i = comp->InputCount() - 1; i >= 0; --i) {
-    Value* input = comp->InputAt(i);
+void BranchInstr::SetComparison(ComparisonInstr* new_comparison) {
+  for (intptr_t i = new_comparison->InputCount() - 1; i >= 0; --i) {
+    Value* input = new_comparison->InputAt(i);
     input->definition()->AddInputUse(input);
     input->set_instruction(this);
   }
   // There should be no need to copy or unuse an environment.
   ASSERT(comparison()->env() == NULL);
+  ASSERT(new_comparison->env() == NULL);
   // Remove the current comparison's input uses.
   comparison()->UnuseAllInputs();
-  ASSERT(!comp->HasUses());
-  comparison_ = comp;
+  ASSERT(!new_comparison->HasUses());
+  comparison_ = new_comparison;
 }
 
 
 // ==== Postorder graph traversal.
 static bool IsMarked(BlockEntryInstr* block,
                      GrowableArray<BlockEntryInstr*>* preorder) {
   // Detect that a block has been visited as part of the current
   // DiscoverBlocks (we can call DiscoverBlocks multiple times).  The block
   // will be 'marked' by (1) having a preorder number in the range of the
   // preorder array and (2) being in the preorder array at that index.
@@ skipping 573 matching lines @@
     ConstantInstr* null_constant = new ConstantInstr(Object::ZoneHandle());
     // It is ok to insert instructions before the current during
     // forward iteration.
     optimizer->InsertBefore(this, null_constant, NULL, Definition::kValue);
     instantiator_type_arguments()->BindTo(null_constant);
   }
   return this;
 }
 
 
+// Recognize the bpattern (a & b) == 0 where left is a bitwise and operation
+// and right is a constant 0.
+static bool RecognizeTestPattern(Value* left, Value* right) {
+  if (!right->BindsToConstant()) {
+    return false;
+  }
+
+  const Object& value = right->BoundConstant();
+  if (!value.IsSmi() || (Smi::Cast(value).Value() != 0)) {
+    return false;
+  }
+
+  Definition* left_defn = left->definition();
+  return left_defn->IsBinarySmiOp() &&
+      (left_defn->AsBinarySmiOp()->op_kind() == Token::kBIT_AND) &&
+      left_defn->HasOnlyUse(left);
+}
+
+
 Instruction* BranchInstr::Canonicalize(FlowGraphOptimizer* optimizer) {
   // Only handle strict-compares.
   if (comparison()->IsStrictCompare()) {
     Definition* replacement = comparison()->Canonicalize(optimizer);
     if ((replacement == comparison()) || (replacement == NULL)) {
       return this;
     }
     ComparisonInstr* comp = replacement->AsComparison();
     if ((comp == NULL) || comp->CanDeoptimize()) {
       return this;
     }
 
     // Check that comparison is not serving as a pending deoptimization target
     // for conversions.
     for (intptr_t i = 0; i < comp->InputCount(); i++) {
       if (comp->RequiredInputRepresentation(i) !=
           comp->InputAt(i)->definition()->representation()) {
         return this;
       }
     }
 
     // Replace the comparison if the replacement is used at this branch,
     // and has exactly one use.
     Value* use = comp->input_use_list();
     if ((use->instruction() == this) && comp->HasOnlyUse(use)) {
       RemoveEnvironment();
       InheritDeoptTarget(comp);
 
+      comp->RemoveEnvironment();
       comp->RemoveFromGraph();
       SetComparison(comp);
       if (FLAG_trace_optimization) {
         OS::Print("Merging comparison v%"Pd"\n", comp->ssa_temp_index());
       }
       // Clear the comparison's temp index and ssa temp index since the
       // value of the comparison is not used outside the branch anymore.
       ASSERT(comp->input_use_list() == NULL);
       comp->ClearSSATempIndex();
       comp->ClearTempIndex();
     }
+  } else if (comparison()->IsSmiEquality()) {
+    BinarySmiOpInstr* bit_and = NULL;
+    if (RecognizeTestPattern(comparison()->left(), comparison()->right())) {
+      bit_and = comparison()->left()->definition()->AsBinarySmiOp();
+    } else if (RecognizeTestPattern(comparison()->right(),
+                                    comparison()->left())) {
+      bit_and = comparison()->right()->definition()->AsBinarySmiOp();
+    }
+
+    if (bit_and != NULL) {
+      TestSmiInstr* test = new TestSmiInstr(comparison()->kind(),
+                                            bit_and->left()->Copy(),
+                                            bit_and->right()->Copy());
+      ASSERT(!CanDeoptimize());
+      InheritDeoptTarget(bit_and);
+      RemoveEnvironment();
+      SetComparison(test);
+      bit_and->RemoveFromGraph();
+    }
   }
   return this;
 }
 
 
 Definition* StrictCompareInstr::Canonicalize(FlowGraphOptimizer* optimizer) {
   if (!right()->BindsToConstant()) {
     return this;
   }
   const Object& right_constant = right()->BoundConstant();
@@ skipping 1103 matching lines @@
     default:
       UNREACHABLE();
   }
   return kPowRuntimeEntry;
 }
 
 
 #undef __
 
 }  // namespace dart