Merge TRUNCDIV and MOD into one instruction. Icorporated feedback from CL https://codereview.chromi…

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/dart_entry.h"
 #include "vm/flow_graph_builder.h"
@@ skipping 233 matching lines @@
     BinarySmiOpInstr* smi_op = new BinarySmiOpInstr(
         Token::kBIT_AND,
         new Value(left_instr),
         new Value(right_instr),
         Isolate::kNoDeoptId);  // BIT_AND cannot deoptimize.
     bit_and_instr->ReplaceWith(smi_op, current_iterator());
   }
 }
 
 
+
+// Used by TryMergeDivMod.
+// Inserts a load-indexed instruction between a TRUNCDIV or MOD instruction,
+// and the using instruction. This is an intermediate step before merging.
+static void DivModAppendLoadIndexed(BinarySmiOpInstr* instr,
+                                    FlowGraph* flow_graph) {
+  const intptr_t index_scale = FlowGraphCompiler::ElementSizeFor(kArrayCid);
+  const intptr_t ix = (instr->op_kind() == Token::kTRUNCDIV) ? 0 : 1;
+  ConstantInstr* index_instr = new ConstantInstr(Smi::Handle(Smi::New(ix)));
+  flow_graph->InsertAfter(instr, index_instr, NULL, Definition::kValue);
+  LoadIndexedInstr* load = new LoadIndexedInstr(new Value(instr),
+                                                new Value(index_instr),
+                                                index_scale,
+                                                kArrayCid,
+                                                Isolate::kNoDeoptId);
+  instr->ReplaceUsesWith(load);
+  flow_graph->InsertAfter(index_instr, load, NULL, Definition::kValue);
+}
+
+
+// Dart:
+//  var x = d % 10;
+//  var y = d ~/ 10;
+//  var z = x + y;
+//
+// IL:
+//  v4 <- %(v2, v3)
+//  v5 <- ~/(v2, v3)
+//  v6 <- +(v4, v5)
+//
+// IL optimized:
+//  v4 <- DIVMOD(v2, v3);
+//  v5 <- LoadIndexed(v4, 0); // ~/ result
+//  v6 <- LoadIndexed(v4, 1); // % result
+//  v7 <- +(v5, v6)
+// Because of the environment it is important that merged instruction replaces
+// first original instruction encountered.
+void FlowGraphOptimizer::TryMergeTruncDivMod(
+    GrowableArray<BinarySmiOpInstr*>* merge_candidates) {
+  if (merge_candidates->length() < 2) {
+    // Need at least a TRUNCDIV and a MOD.
+    return;
+  }
+  for (intptr_t i = 0; i < merge_candidates->length(); i++) {
+    BinarySmiOpInstr* curr_instr = (*merge_candidates)[i];
+    if (curr_instr == NULL) {
+      // Instructions was merged already.
+      continue;
+    }
+    ASSERT((curr_instr->op_kind() == Token::kTRUNCDIV) ||
+           (curr_instr->op_kind() == Token::kMOD));
+    // Check if there is kMOD/kTRUNDIV binop with same inputs.
+    const intptr_t other_kind = (curr_instr->op_kind() == Token::kTRUNCDIV) ?
+        Token::kMOD : Token::kTRUNCDIV;
+    Definition* left_def = curr_instr->left()->definition();
+    Definition* right_def = curr_instr->right()->definition();
+    for (intptr_t k = i + 1; k < merge_candidates->length(); k++) {
+      BinarySmiOpInstr* other_binop = (*merge_candidates)[k];

[Florian Schneider, 2013/11/21 11:15:41]

Can ohter_binop ever be NULL? I'm thinking of the case where there are 3 or more
merge candidates. Please add a test for these case as well:
3 candidates merged into 1 DIVMOD
4 or more candidates merged into 2 DIVMOD 

[srdjan, 2013/11/21 17:32:44]

Indeed it can.. fixed. Added tests as suggested

+      if ((other_binop->op_kind() == other_kind) &&
+          (other_binop->left()->definition() == left_def) &&
+          (other_binop->right()->definition() == right_def)) {
+        (*merge_candidates)[k] = NULL;  // Clear it.
+        // Append a LoadIndexed behind TRUNC_DIV and MOD.
+        DivModAppendLoadIndexed(curr_instr, flow_graph_);
+        DivModAppendLoadIndexed(other_binop, flow_graph_);
+
+        ZoneGrowableArray<Value*>* args = new ZoneGrowableArray<Value*>(2);
+        args->Add(new Value(curr_instr->left()->definition()));
+        args->Add(new Value(curr_instr->right()->definition()));
+
+        // Replace with TruncDivMod.
+        MergedMathInstr* div_mod = new MergedMathInstr(
+            args,
+            curr_instr->deopt_id(),
+            MergedMathInstr::kTruncDivMod);
+        curr_instr->ReplaceWith(div_mod, current_iterator());
+        other_binop->ReplaceUsesWith(div_mod);
+        other_binop->RemoveFromGraph();
+      }
+    }
+  }
+}
+
+
 // 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() {
+void FlowGraphOptimizer::TryOptimizePatterns() {
   if (!FLAG_truncating_left_shift) return;
   ASSERT(current_iterator_ == NULL);
+  GrowableArray<BinarySmiOpInstr*> for_merge;
   for (intptr_t i = 0; i < block_order_.length(); ++i) {
+    for_merge.Clear();

[Florian Schneider, 2013/11/21 11:15:41]

Maybe add a comment here or in TryMergeTruncDivMod that merging works on a
per-basic block basis.

[srdjan, 2013/11/21 17:32:44]

Done.

     BlockEntryInstr* entry = block_order_[i];
     ForwardInstructionIterator it(entry);
     current_iterator_ = ⁢
     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 ((binop->op_kind() == Token::kTRUNCDIV) ||
+                   (binop->op_kind() == Token::kMOD)) {
+          for_merge.Add(binop);
         }
       } 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());
         }
       }
     }
+    TryMergeTruncDivMod(&for_merge);
     current_iterator_ = NULL;
   }
 }
 
 
 static void EnsureSSATempIndex(FlowGraph* graph,
                                Definition* defn,
                                Definition* replacement) {
   if ((replacement->ssa_temp_index() == -1) &&
       (defn->ssa_temp_index() != -1)) {
@@ skipping 6533 matching lines @@
   SetValue(instr, non_constant_);
 }
 
 
 void ConstantPropagator::VisitInvokeMathCFunction(
     InvokeMathCFunctionInstr* instr) {
   // TODO(kmillikin): Handle conversion.
   SetValue(instr, non_constant_);
 }
 
+
+void ConstantPropagator::VisitMergedMath(MergedMathInstr* instr) {
+  // TODO(kmillikin): Handle conversion.

[srdjan, 2013/11/20 22:23:28]

Just standard boiler-plate :-).

[Florian Schneider, 2013/11/21 11:15:41]

The comment still does not make sense since this is not a conversion.

[srdjan, 2013/11/21 17:32:44]

  // TODO(srdjan): Handle merged instruction.

+  SetValue(instr, non_constant_);
+}
+
+
 void ConstantPropagator::VisitConstant(ConstantInstr* instr) {
   SetValue(instr, instr->value());
 }
 
 
 void ConstantPropagator::VisitConstraint(ConstraintInstr* instr) {
   // Should not be used outside of range analysis.
   UNREACHABLE();
 }
 
@@ skipping 1069 matching lines @@
   }
 
   // Insert materializations at environment uses.
   for (intptr_t i = 0; i < exits.length(); i++) {
     CreateMaterializationAt(exits[i], alloc, alloc->cls(), *fields);
   }
 }
 
 
 }  // namespace dart