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

Index: runtime/vm/flow_graph_optimizer.cc
===================================================================
--- runtime/vm/flow_graph_optimizer.cc	(revision 18705)
+++ runtime/vm/flow_graph_optimizer.cc	(working copy)
@@ -167,6 +167,93 @@
 }
 
 
+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) {