[turbofan] fine grained move operand merge optimization

src/compiler/move-optimizer.cc

 // Copyright 2014 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/compiler/move-optimizer.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
 
@@ skipping 193 matching lines @@
   return code()->instructions()[block->last_instruction_index()];
 }
 
 
 void MoveOptimizer::OptimizeMerge(InstructionBlock* block) {
   DCHECK(block->PredecessorCount() > 1);
   // Ensure that the last instruction in all incoming blocks don't contain
   // things that would prevent moving gap moves across them.
   for (RpoNumber& pred_index : block->predecessors()) {
     const InstructionBlock* pred = code()->InstructionBlockAt(pred_index);
+
+    // If the predecessor has more than one successor, we shouldn't attempt to
+    // move down to this block (one of the successors) any of the gap moves,
+    // because their effect may be necessary to the other successors.
+    if (pred->SuccessorCount() > 1) return;
+
     const Instruction* last_instr =
         code()->instructions()[pred->last_instruction_index()];
     if (last_instr->IsCall()) return;
     if (last_instr->TempCount() != 0) return;
     if (last_instr->OutputCount() != 0) return;
     for (size_t i = 0; i < last_instr->InputCount(); ++i) {
       const InstructionOperand* op = last_instr->InputAt(i);
       if (!op->IsConstant() && !op->IsImmediate()) return;
     }
   }
@@ skipping 15 matching lines @@
       MoveKey key = {src, dst};
       auto res = move_map.insert(std::make_pair(key, 1));
       if (!res.second) {
         res.first->second++;
         if (res.first->second == block->PredecessorCount()) {
           correct_counts++;
         }
       }
     }
   }
-  if (move_map.empty() || correct_counts != move_map.size()) return;
+  if (move_map.empty() || correct_counts == 0) return;
+
   // Find insertion point.
   Instruction* instr = nullptr;
   for (int i = block->first_instruction_index();
        i <= block->last_instruction_index(); ++i) {
     instr = code()->instructions()[i];
-    if (!GapsCanMoveOver(instr, local_zone()) || !instr->AreMovesRedundant())
+    if (correct_counts != move_map.size() ||
+        !GapsCanMoveOver(instr, local_zone()) || !instr->AreMovesRedundant())
       break;
   }
   DCHECK_NOT_NULL(instr);
+
+  if (correct_counts != move_map.size()) {
+    // Moves that are unique to each predecessor won't be pushed to the common
+    // successor.
+    OperandSet conflicting_srcs(local_zone());
+    for (auto iter = move_map.begin(), end = move_map.end(); iter != end;) {
+      auto current = iter;
+      ++iter;
+      if (current->second != block->PredecessorCount()) {
+        InstructionOperand dest = current->first.second;
+        // Not all the moves in all the gaps are the same. Maybe some are. If
+        // there are such moves, we could move them, but the destination of the
+        // moves staying behind can't appear as a source of a common move,
+        // because the move staying behind will clobber this destination.
+        conflicting_srcs.insert(dest);
+        move_map.erase(current);
+      }
+    }
+
+    bool changed = false;
+    do {
+      // If a common move can't be pushed to the common successor, then its
+      // destination also can't appear as source to any move being pushed.
+      changed = false;
+      for (auto iter = move_map.begin(), end = move_map.end(); iter != end;) {
+        auto current = iter;
+        ++iter;
+        DCHECK_EQ(block->PredecessorCount(), current->second);
+        if (conflicting_srcs.find(current->first.first) !=
+            conflicting_srcs.end()) {
+          conflicting_srcs.insert(current->first.second);
+          move_map.erase(current);
+          changed = true;
+        }
+      }
+    } while (changed);
+  }
+
+  if (move_map.empty()) return;
+
+  DCHECK_NOT_NULL(instr);
   bool gap_initialized = true;
   if (instr->parallel_moves()[0] == nullptr ||
       instr->parallel_moves()[0]->empty()) {
     to_finalize_.push_back(instr);
   } else {
     // Will compress after insertion.
     gap_initialized = false;
     std::swap(instr->parallel_moves()[0], instr->parallel_moves()[1]);
   }
   ParallelMove* moves = instr->GetOrCreateParallelMove(
       static_cast<Instruction::GapPosition>(0), code_zone());
   // Delete relevant entries in predecessors and move everything to block.
   bool first_iteration = true;
   for (RpoNumber& pred_index : block->predecessors()) {
     const InstructionBlock* pred = code()->InstructionBlockAt(pred_index);
     for (MoveOperands* move : *LastInstruction(pred)->parallel_moves()[0]) {
       if (move->IsRedundant()) continue;
       MoveKey key = {move->source(), move->destination()};
       auto it = move_map.find(key);
-      USE(it);
-      DCHECK(it != move_map.end());
-      if (first_iteration) {
-        moves->AddMove(move->source(), move->destination());
+      if (it != move_map.end()) {
+        if (first_iteration) {
+          moves->AddMove(move->source(), move->destination());
+        }
+        move->Eliminate();
       }
-      move->Eliminate();
     }
     first_iteration = false;
   }
   // Compress.
   if (!gap_initialized) {
     CompressMoves(instr->parallel_moves()[0], instr->parallel_moves()[1]);
   }
 }
 
 
@@ skipping 48 matching lines @@
         static_cast<Instruction::GapPosition>(1), code_zone());
     slot_1->AddMove(group_begin->destination(), load->destination());
     load->Eliminate();
   }
   loads.clear();
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8