Merge sin(a), cos(a) into one instruction. TODO: Implement for ARM and MIPS.

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 237 matching lines @@
         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;
+void FlowGraphOptimizer::AppendLoadIndexedForMerged(Definition* instr,
+                                                    intptr_t ix,
+                                                    intptr_t cid) {
+  const intptr_t index_scale = FlowGraphCompiler::ElementSizeFor(cid);
   ConstantInstr* index_instr = new ConstantInstr(Smi::Handle(Smi::New(ix)));
-  flow_graph->InsertAfter(instr, index_instr, NULL, Definition::kValue);
+  flow_graph()->InsertAfter(instr, index_instr, NULL, Definition::kValue);
   LoadIndexedInstr* load = new LoadIndexedInstr(new Value(instr),
                                                 new Value(index_instr),
                                                 index_scale,
-                                                kArrayCid,
+                                                cid,
                                                 Isolate::kNoDeoptId);
   instr->ReplaceUsesWith(load);
-  flow_graph->InsertAfter(index_instr, load, NULL, Definition::kValue);
+  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.
+      // Instruction 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];
       // 'other_binop' can be NULL if it was already merged.
       if ((other_binop != NULL) &&
           (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_);
+        const intptr_t curr_result_ix =
+            (curr_instr->op_kind() == Token::kTRUNCDIV) ? 0 : 1;
+        AppendLoadIndexedForMerged(curr_instr, curr_result_ix, kArrayCid);
+        const intptr_t other_result_ix =

[Florian Schneider, 2013/12/03 14:12:04]

Equivalent, but shorter:

const intptr_t other_result_ix = (curr_result_ix == 0) ? 1 : 0;

or even just flip the LSB:

const intptr_t other_result_ix = curr_result_ix ^ 1;

+            (other_binop->op_kind() == Token::kTRUNCDIV) ? 0 : 1;
+        AppendLoadIndexedForMerged(other_binop, other_result_ix, kArrayCid);
 
         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();
       }
     }
   }
 }
 
 
+void FlowGraphOptimizer::TryMergeMathUnary(
+    GrowableArray<MathUnaryInstr*>* merge_candidates) {
+  if (!FlowGraphCompiler::SupportsSinCos()) {
+    return;
+  }
+  if (merge_candidates->length() < 2) {
+    // Need at least a SIN and a COS.
+    return;
+  }
+  for (intptr_t i = 0; i < merge_candidates->length(); i++) {
+    MathUnaryInstr* curr_instr = (*merge_candidates)[i];
+    if (curr_instr == NULL) {
+      // Instruction was merged already.
+      continue;
+    }
+    ASSERT((curr_instr->kind() == MethodRecognizer::kMathSin) ||
+           (curr_instr->kind() == MethodRecognizer::kMathCos));
+    // Check if there is sin/cos binop with same inputs.
+    const intptr_t other_kind =
+        (curr_instr->kind() == MethodRecognizer::kMathSin) ?
+            MethodRecognizer::kMathCos : MethodRecognizer::kMathSin;
+    Definition* def = curr_instr->value()->definition();
+    for (intptr_t k = i + 1; k < merge_candidates->length(); k++) {
+      MathUnaryInstr* other_op = (*merge_candidates)[k];
+      // 'other_op' can be NULL if it was already merged.
+      if ((other_op != NULL) && (other_op->kind() == other_kind) &&
+          (other_op->value()->definition() == def)) {
+        (*merge_candidates)[k] = NULL;  // Clear it.
+        // Append a LoadIndexed behind SIN and COS.
+        const intptr_t curr_result_ix =
+            (curr_instr->kind() == MethodRecognizer::kMathSin) ? 0 : 1;
+        AppendLoadIndexedForMerged(
+            curr_instr, curr_result_ix, kTypedDataFloat64ArrayCid);
+        const intptr_t other_result_ix =
+            (other_op->kind() == MethodRecognizer::kMathSin) ? 0 : 1;

[Florian Schneider, 2013/12/03 14:12:04]

Equivalent, but shorter:

const intptr_t other_result_ix = (curr_result_ix == 0) ? 1 : 0;

[srdjan, 2013/12/03 18:10:01]

I used to have that, but found it harder to read.  Factored the code out so that
it is linked with the code generation.

+        AppendLoadIndexedForMerged(
+            other_op, other_result_ix, kTypedDataFloat64ArrayCid);
+        ZoneGrowableArray<Value*>* args = new ZoneGrowableArray<Value*>(2);

[Florian Schneider, 2013/12/03 14:12:04]

s/2/1/

because only one argument is added below.

[srdjan, 2013/12/03 18:10:01]

Done.

+        args->Add(new Value(curr_instr->value()->definition()));
+
+        // Replace with TruncDivMod.
+        MergedMathInstr* div_mod = new MergedMathInstr(
+            args,
+            curr_instr->DeoptimizationTarget(),
+            MergedMathInstr::kSinCos);
+        curr_instr->ReplaceWith(div_mod, current_iterator());
+        other_op->ReplaceUsesWith(div_mod);
+        other_op->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.
 // Merging occurs only per basic-block.
 void FlowGraphOptimizer::TryOptimizePatterns() {
   if (!FLAG_truncating_left_shift) return;
   ASSERT(current_iterator_ == NULL);
-  GrowableArray<BinarySmiOpInstr*> for_merge;
+  GrowableArray<BinarySmiOpInstr*> div_mod_merge;
+  GrowableArray<MathUnaryInstr*> sin_cos_merge;
   for (intptr_t i = 0; i < block_order_.length(); ++i) {
     // Merging only per basic-block.
-    for_merge.Clear();
+    div_mod_merge.Clear();
+    sin_cos_merge.Clear();
     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)) {
-          for_merge.Add(binop);
+          div_mod_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());
         }
+      } else if (it.Current()->IsMathUnary()) {
+        MathUnaryInstr* math_unary = it.Current()->AsMathUnary();
+        if ((math_unary->kind() == MethodRecognizer::kMathSin) ||
+            (math_unary->kind() == MethodRecognizer::kMathCos)) {
+          sin_cos_merge.Add(math_unary);
+        }
       }
     }
-    TryMergeTruncDivMod(&for_merge);
+    TryMergeTruncDivMod(&div_mod_merge);
+    TryMergeMathUnary(&sin_cos_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 7592 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