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(

[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) {
   if ((replacement->ssa_temp_index() == -1) &&
       (defn->ssa_temp_index() != -1)) {
     replacement->set_ssa_temp_index(graph->alloc_ssa_temp_index());
   }
 }
 
 
@@ skipping 767 matching lines @@
     InsertBefore(call, constant, NULL, Definition::kValue);
     BinarySmiOpInstr* bin_op =
         new BinarySmiOpInstr(Token::kBIT_AND, call,
                              new Value(left),
                              new Value(constant));
     ReplaceCall(call, bin_op);
   } else {
     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.
       Definition* temp = left;
       left = right;
       right = temp;
     }
     BinarySmiOpInstr* bin_op =
         new BinarySmiOpInstr(op_kind, call, new Value(left), new Value(right));
     ReplaceCall(call, bin_op);
@@ skipping 3211 matching lines @@
 
   if (FLAG_trace_constant_propagation) {
     OS::Print("\n==== After constant propagation ====\n");
     FlowGraphPrinter printer(*graph_);
     printer.PrintBlocks();
   }
 }
 
 
 }  // namespace dart