Merge TRUNCDIV and MOD into TRUNCDIV_MOD single operation.

runtime/vm/flow_graph_optimizer.cc

Index: runtime/vm/flow_graph_optimizer.cc
===================================================================
--- runtime/vm/flow_graph_optimizer.cc	(revision 30236)
+++ runtime/vm/flow_graph_optimizer.cc	(working copy)
@@ -251,9 +251,82 @@
 }
 
 
+// Used bye TryMergeDivMod.
+// Inserts a load-indexed instruction between a TRUNC_DIV or MOD instruction,
+// and the usin instruction. This is an intermediate step before merging

[regis, 2013/11/14 01:33:20]

usin -> using ?
merging period

[srdjan, 2013/11/20 21:41:47]

Done.

+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;

[Florian Schneider, 2013/11/14 10:17:44]

Does work correctly for this example where one operation does not dominate the
other?

var d = ??
var x;
if (expr)
  x = d % 10
else
  x = d ~/ 10

[srdjan, 2013/11/20 21:41:47]

It does not, you are right. Implemented it differently.

+//
+// 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 DIVMOD replaces first
+// instructon (TRUNCDIV or MOD) encountered.

[Florian Schneider, 2013/11/14 10:17:44]

typo: instruction

[srdjan, 2013/11/20 21:41:47]

Done.

+void FlowGraphOptimizer::TryMergeDivMod(BinarySmiOpInstr* curr_instr) {
+  ASSERT((curr_instr->op_kind() == Token::kTRUNCDIV) ||
+         (curr_instr->op_kind() == Token::kMOD));
+  // Check if there is kMOD/kTRUNDIC 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();
+  GrowableArray<BinarySmiOpInstr*> to_replace;
+  for (Value::Iterator it(left_def->input_use_list());
+       !it.Done();
+       it.Advance()) {
+    Instruction* other_instr = it.Current()->instruction();
+    if (other_instr->IsBinarySmiOp() &&
+        (other_instr->AsBinarySmiOp()->op_kind() == other_kind)) {
+      BinarySmiOpInstr* other_binop = other_instr->AsBinarySmiOp();
+      if ((other_binop->left()->definition() == left_def) &&
+          (other_binop->right()->definition() == right_def)) {
+        // Append a LoadIndexed behind TRUNC_DIV and MOD.
+        DivModAppendLoadIndexed(curr_instr, flow_graph_);
+        DivModAppendLoadIndexed(other_binop, flow_graph_);
+
+        // Replace with DivMod.
+        BinarySmiOpInstr* div_mod = new BinarySmiOpInstr(
+            Token::kTRUNCDIVMOD,
+            new Value(curr_instr->left()->definition()),
+            new Value(curr_instr->right()->definition()),
+            curr_instr->deopt_id());
+        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);
   for (intptr_t i = 0; i < block_order_.length(); ++i) {
@@ -267,6 +340,9 @@
           OptimizeLeftShiftBitAndSmiOp(binop,
                                        binop->left()->definition(),
                                        binop->right()->definition());
+        } else if ((binop->op_kind() == Token::kTRUNCDIV)||
+                   (binop->op_kind() == Token::kMOD)) {
+          TryMergeDivMod(binop);
         }
       } else if (it.Current()->IsBinaryMintOp()) {
         BinaryMintOpInstr* mintop = it.Current()->AsBinaryMintOp();
@@ -6726,6 +6802,10 @@
         case Token::kDIV:
           SetValue(instr, non_constant_);
           break;
+        case Token::kTRUNCDIVMOD:
+        case Token::kTRUNCDIVREM:
+          SetValue(instr, non_constant_);
+          break;
         default:
           UNREACHABLE();
       }