Recognize pattern (a << b) & c with c being a positive Smi and allow left shift to truncate the res…

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/flow_graph_builder.h"
 #include "vm/flow_graph_compiler.h"
@@ skipping 149 matching lines @@
 
   const bool with_checks = false;
   PolymorphicInstanceCallInstr* specialized =
       new PolymorphicInstanceCallInstr(call->instance_call(),
                                        ic_data,
                                        with_checks);
   call->ReplaceWith(specialized, current_iterator());
 }
 
 
+static BinarySmiOpInstr* AsSmiLeftShiftInstruction(Value* v) {
+  BinarySmiOpInstr* instr = v->definition()->AsBinarySmiOp();
+  if ((instr != NULL) && (instr->op_kind() == Token::kSHL)) {
+    return instr;
+  }
+  return NULL;
+}
+
+
+Value* AsPositiveSmiConstValue(Value* v) {
+  if (v->BindsToConstant() && v->BoundConstant().IsSmi()) {
+    if (Smi::Cast(v->BoundConstant()).Value() >= 0) {
+      return v;
+    }
+  }
+  return NULL;
+}
+
+
+void FlowGraphOptimizer::OptimizeLeftShiftBitAndSmiOp(
+    Definition* bit_and_instr,
+    Value* left,
+    Value* right) {
+  // Both left and right may have only one use.

[Vyacheslav Egorov (Google), 2013/02/20 00:37:06]

The constant can have many uses it does not invalidate optimization.  You can
add a check here.

[srdjan, 2013/02/21 00:47:17]

Done.

+  if ((left->next_use() != NULL) || (left->previous_use() != NULL)) {
+    return;
+  }
+  if ((right->next_use() != NULL) || (right->previous_use() != NULL)) {
+    return;
+  }

[Vyacheslav Egorov (Google), 2013/02/20 00:37:06]

This does not check for environment uses. I think it will fail on something
like:

class A { foo(x) { print(x & 0xf); } }
class B { foo(x) { print(x); } }

bar (o) {
  o.foo(1 << 32);
} 

final a = new A(), b = new B();
for (var i = 0; i < 10000; i++) bar(a);
bar(b);

(if it does fail on this please add this to test suite).

[srdjan, 2013/02/21 00:47:17]

It fails, thanks. Added to test suite. Punted on fixing it by moving this
optimization before inlining.
We need to figure out how to use environment uses in order to prevent the issue
above.

+  // Check for pattern
+  BinarySmiOpInstr* smi_left_shift = NULL;
+  Value* smi_const = AsPositiveSmiConstValue(left);
+  if (smi_const == NULL) {
+    smi_const = AsPositiveSmiConstValue(right);
+    if (smi_const != NULL) {
+      smi_left_shift = AsSmiLeftShiftInstruction(left);
+    }
+  } else {
+    smi_left_shift = AsSmiLeftShiftInstruction(right);
+  }
+  if ((smi_left_shift == NULL) || (smi_const == NULL)) {
+    // Not the pattern 'BIT_AND with smi-left-shift and smi-constant'.
+    return;
+  }
+  if (bit_and_instr->IsBinarySmiOp()) {
+    smi_left_shift->set_is_truncating(true);
+  } else {
+    ASSERT(bit_and_instr->IsBinaryMintOp());
+    smi_left_shift->set_is_truncating(true);
+    // Replace Mint op with Smi op.
+    BinarySmiOpInstr* smi_op = new BinarySmiOpInstr(
+        Token::kBIT_AND,
+        bit_and_instr->AsBinaryMintOp()->instance_call(),
+        left->Copy(),
+        right->Copy());
+    bit_and_instr->ReplaceWith(smi_op, current_iterator());
+  }
+}
+
+
+// Optimize (a << b) & c pattern: if c is a positive smi, then the
+// shift can be a truncating Smi shift and result is always Smi.
+void FlowGraphOptimizer::TryOptimizeLeftShiftWithBitAndPattern() {
+  ASSERT(current_iterator_ == NULL);
+  for (intptr_t i = 0; i < block_order_.length(); ++i) {
+    BlockEntryInstr* entry = block_order_[i];
+    ForwardInstructionIterator it(entry);
+    current_iterator_ = &it;
+    for (; !it.Done(); it.Advance()) {
+      if (it.Current()->IsBinarySmiOp()) {
+        BinarySmiOpInstr* binop = it.Current()->AsBinarySmiOp();
+        if (binop->op_kind() == Token::kBIT_AND) {
+          OptimizeLeftShiftBitAndSmiOp(binop, binop->left(), binop->right());
+        }
+      } else if (it.Current()->IsBinaryMintOp()) {
+        BinaryMintOpInstr* mintop = it.Current()->AsBinaryMintOp();
+        if (mintop->op_kind() == Token::kBIT_AND) {
+          OptimizeLeftShiftBitAndSmiOp(mintop, mintop->left(), mintop->right());
+        }
+      }
+    }
+    current_iterator_ = NULL;
+  }
+}
+
+
 static void EnsureSSATempIndex(FlowGraph* graph,
                                Definition* defn,
                                Definition* replacement) {
   if ((replacement->ssa_temp_index() == -1) &&
       (defn->ssa_temp_index() != -1)) {
     replacement->set_ssa_temp_index(graph->alloc_ssa_temp_index());
   }
 }
 
 
@@ skipping 4006 matching lines @@
 
   if (FLAG_trace_constant_propagation) {
     OS::Print("\n==== After constant propagation ====\n");
     FlowGraphPrinter printer(*graph_);
     printer.PrintBlocks();
   }
 }
 
 
 }  // namespace dart