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 15 matching lines @@
 DEFINE_FLAG(bool, use_cha, true, "Use class hierarchy analysis.");
 DEFINE_FLAG(bool, load_cse, true, "Use redundant load elimination.");
 DEFINE_FLAG(bool, trace_range_analysis, false, "Trace range analysis progress");
 DEFINE_FLAG(bool, trace_constant_propagation, false,
     "Print constant propagation and useless code elimination.");
 DEFINE_FLAG(bool, array_bounds_check_elimination, true,
     "Eliminate redundant bounds checks.");
 DEFINE_FLAG(int, max_polymorphic_checks, 4,
     "Maximum number of polymorphic check, otherwise it is megamorphic.");
 DEFINE_FLAG(bool, remove_redundant_phis, true, "Remove redundant phis.");
+DEFINE_FLAG(bool, truncating_left_shift, true,
+    "Optimize left shift to truncate if possible");
 
 
 void FlowGraphOptimizer::ApplyICData() {
   VisitBlocks();
 }
 
 
 // Attempts to convert an instance call (IC call) using propagated class-ids,
 // e.g., receiver class id.
 void FlowGraphOptimizer::ApplyClassIds() {
@@ skipping 114 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* AsSmiShiftLeftInstruction(Definition* d) {
+  BinarySmiOpInstr* instr = d->AsBinarySmiOp();
+  if ((instr != NULL) && (instr->op_kind() == Token::kSHL)) {
+    return instr;
+  }
+  return NULL;
+}
+
+
+static bool IsPositiveOrZeroSmiConst(Definition* d) {
+  ConstantInstr* const_instr = d->AsConstant();
+  if ((const_instr != NULL) && (const_instr->value().IsSmi())) {
+    return Smi::Cast(const_instr->value()).Value() >= 0;
+  }
+  return false;
+}
+
+
+void FlowGraphOptimizer::OptimizeLeftShiftBitAndSmiOp(
+    Definition* bit_and_instr,
+    Definition* left_instr,
+    Definition* right_instr) {
+  ASSERT(bit_and_instr != NULL);
+  ASSERT((left_instr != NULL) && (right_instr != NULL));
+
+  // Check for pattern, smi_shift_left must be single-use.
+  bool is_positive_or_zero = IsPositiveOrZeroSmiConst(left_instr);
+  if (!is_positive_or_zero) {
+    is_positive_or_zero = IsPositiveOrZeroSmiConst(right_instr);
+  }
+  if (!is_positive_or_zero) return;
+
+  BinarySmiOpInstr* smi_shift_left = NULL;
+  if (bit_and_instr->InputAt(0)->IsSingleUse()) {
+    smi_shift_left = AsSmiShiftLeftInstruction(left_instr);
+  }
+  if ((smi_shift_left == NULL) && (bit_and_instr->InputAt(1)->IsSingleUse())) {
+    smi_shift_left = AsSmiShiftLeftInstruction(right_instr);
+  }
+  if (smi_shift_left == NULL) return;
+
+  // Pattern recognized.
+  smi_shift_left->set_is_truncating(true);
+  ASSERT(bit_and_instr->IsBinarySmiOp() || bit_and_instr->IsBinaryMintOp());
+  if (bit_and_instr->IsBinaryMintOp()) {
+    // Replace Mint op with Smi op.
+    BinarySmiOpInstr* smi_op = new BinarySmiOpInstr(
+        Token::kBIT_AND,
+        bit_and_instr->AsBinaryMintOp()->instance_call(),
+        new Value(left_instr),
+        new Value(right_instr));
+    bit_and_instr->ReplaceWith(smi_op, current_iterator());
+  }
+}
+
+
+// Optimize (a << b) & c pattern: if c is a positive Smi or zero, then the
+// shift can be a truncating Smi shift-left and result is always Smi.
+void FlowGraphOptimizer::TryOptimizeLeftShiftWithBitAndPattern() {
+  if (!FLAG_truncating_left_shift) return;
+  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()->definition(),
+                                       binop->right()->definition());
+        }
+      } else if (it.Current()->IsBinaryMintOp()) {
+        BinaryMintOpInstr* mintop = it.Current()->AsBinaryMintOp();
+        if (mintop->op_kind() == Token::kBIT_AND) {
+          OptimizeLeftShiftBitAndSmiOp(mintop,
+                                       mintop->left()->definition(),
+                                       mintop->right()->definition());
+        }
+      }
+    }
+    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 313 matching lines @@
   if (ic_data.NumberOfChecks() != 1) return kIllegalCid;
   ASSERT(ic_data.HasOneTarget());
 
   Function& target = Function::Handle();
   intptr_t class_id;
   ic_data.GetOneClassCheckAt(0, &class_id, &target);
   return class_id;
 }
 
 
+void FlowGraphOptimizer::AddCheckSmi(Definition* to_check,
+                                     intptr_t deopt_id,
+                                     Environment* deopt_environment,
+                                     Instruction* insert_before) {
+  if (to_check->Type()->ToCid() != kSmiCid) {
+    InsertBefore(insert_before,
+                 new CheckSmiInstr(new Value(to_check), deopt_id),
+                 deopt_environment,
+                 Definition::kEffect);
+  }
+}
+
+
 void FlowGraphOptimizer::AddCheckClass(Definition* to_check,
                                        const ICData& unary_checks,
                                        intptr_t deopt_id,
                                        Environment* deopt_environment,
                                        Instruction* insert_before) {
   // Type propagation has not run yet, we cannot eliminate the check.
   Instruction* check = NULL;
   if ((unary_checks.NumberOfChecks() == 1) &&
       (unary_checks.GetReceiverClassIdAt(0) == kSmiCid)) {
     check = new CheckSmiInstr(new Value(to_check), deopt_id);
@@ skipping 491 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);
+    AddCheckSmi(left, call->deopt_id(), call->env(), call);
+    AddCheckSmi(right, call->deopt_id(), call->env(), call);
     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 3240 matching lines @@
 
   if (FLAG_trace_constant_propagation) {
     OS::Print("\n==== After constant propagation ====\n");
     FlowGraphPrinter printer(*graph_);
     printer.PrintBlocks();
   }
 }
 
 
 }  // namespace dart