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 18774)
+++ runtime/vm/flow_graph_optimizer.cc	(working copy)
@@ -167,6 +167,87 @@
 }
 
 
+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(

[Kevin Millikin (Google), 2013/02/21 12:44:35]

I also think this kind of function is clearer if it takes the definition of left
and right as arguments, not a use of the definition.  Bonuses:

* You don't have to worry about copying or forgetting to copy use list nodes and
other issues of ownership.  Just make a new one!

* AsSmiLeftShiftInstruction and AsPositiveSmiConstValue aren't so bizarre.  As
it is, they coerce a use of a definition into a definition, which is not a
subclass of use of a defintion, so they do not actually fit the "AsXXX" pattern
and that seems warty.

[srdjan, 2013/02/21 21:55:31]

Done.

+    Definition* bit_and_instr,
+    Value* left,
+    Value* right) {
+  // Check for pattern, smi_left_shift value must be single-use.
+  BinarySmiOpInstr* smi_left_shift = NULL;
+  Value* smi_const = AsPositiveSmiConstValue(left);
+  if (smi_const == NULL) {
+    smi_const = AsPositiveSmiConstValue(right);
+    if (left->IsSingleUse() && (smi_const != NULL)) {
+      smi_left_shift = AsSmiLeftShiftInstruction(left);
+    }
+  } else if (right->IsSingleUse()) {
+    smi_left_shift = AsSmiLeftShiftInstruction(right);
+  }
+  if ((smi_left_shift == NULL) || (smi_const == NULL)) {
+    // Not the pattern '(mint,smi)-bit-and with smi-left-shift and smi-const'.
+    return;
+  }
+  // TODO(srdjan): If done post inlining, we must check environment uses.
+  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) {
@@ -954,14 +1035,18 @@
     ASSERT(operands_type == kSmiCid);
     // Insert two smi checks and attach a copy of the original
     // environment because the smi operation can still deoptimize.
-    InsertBefore(call,
-                 new CheckSmiInstr(new Value(left), call->deopt_id()),
-                 call->env(),
-                 Definition::kEffect);
-    InsertBefore(call,
-                 new CheckSmiInstr(new Value(right), call->deopt_id()),
-                 call->env(),
-                 Definition::kEffect);
+    if (left->Type()->ToCid() != kSmiCid) {

[Vyacheslav Egorov (Google), 2013/02/21 14:45:50]

I suggest to create a method that inserts a check:

AddCheckSmi(...)

[srdjan, 2013/02/21 21:55:31]

Done.

+      InsertBefore(call,
+                   new CheckSmiInstr(new Value(left), call->deopt_id()),
+                   call->env(),
+                   Definition::kEffect);
+    }
+    if (right->Type()->ToCid() != kSmiCid) {
+      InsertBefore(call,
+                   new CheckSmiInstr(new Value(right), call->deopt_id()),
+                   call->env(),
+                   Definition::kEffect);
+    }
     if (left->IsConstant() &&
         ((op_kind == Token::kADD) || (op_kind == Token::kMUL))) {
       // Constant should be on the right side.