Merge TRUNCDIV and MOD into TRUNCDIV_MOD single operation.

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 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) {
     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 ((binop->op_kind() == Token::kTRUNCDIV)||
+                   (binop->op_kind() == Token::kMOD)) {
+          TryMergeDivMod(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());
         }
       }
     }
@@ skipping 6439 matching lines @@
           Instance& result = Integer::ZoneHandle(
               left_int.BitOp(op_kind, right_int));
           result = result.CheckAndCanonicalize(NULL);
           ASSERT(!result.IsNull());
           SetValue(instr, result);
           break;
         }
         case Token::kDIV:
           SetValue(instr, non_constant_);
           break;
+        case Token::kTRUNCDIVMOD:
+        case Token::kTRUNCDIVREM:
+          SetValue(instr, non_constant_);
+          break;
         default:
           UNREACHABLE();
       }
     } else {
       // TODO(kmillikin): support other types.
       SetValue(instr, non_constant_);
     }
   }
 }
 
@@ skipping 1173 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