[turbofan] optimize moves into merges

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 {
 
 namespace {
 
+typedef std::pair<InstructionOperand, InstructionOperand> MoveKey;
+typedef ZoneMap<MoveKey, unsigned> MoveMap;
+typedef ZoneSet<InstructionOperand> OperandSet;
+
+
 bool GapsCanMoveOver(Instruction* instr) {
   DCHECK(!instr->IsGapMoves());
   return instr->IsSourcePosition() || instr->IsNop();
 }
 
 
 int FindFirstNonEmptySlot(GapInstruction* gap) {
   int i = GapInstruction::FIRST_INNER_POSITION;
   for (; i <= GapInstruction::LAST_INNER_POSITION; i++) {
     auto move = gap->parallel_moves()[i];
@@ skipping 18 matching lines @@
       code_(code),
       to_finalize_(local_zone),
       temp_vector_0_(local_zone),
       temp_vector_1_(local_zone) {}
 
 
 void MoveOptimizer::Run() {
   for (auto* block : code()->instruction_blocks()) {
     CompressBlock(block);
   }
+  for (auto block : code()->instruction_blocks()) {
+    if (block->PredecessorCount() <= 1) continue;
+    OptimizeMerge(block);
+  }
   for (auto gap : to_finalize_) {
     FinalizeMoves(gap);
   }
 }
 
 
 void MoveOptimizer::CompressMoves(MoveOpVector* eliminated, ParallelMove* left,
                                   ParallelMove* right) {
   DCHECK(eliminated->empty());
   auto move_ops = right->move_operands();
@@ skipping 62 matching lines @@
       CompressMoves(&temp_vector, pred_moves, left);
       // Slide prev_gap down so we always know where to look for it.
       std::swap(prev_gap->parallel_moves()[0], gap->parallel_moves()[0]);
     }
     prev_gap = gap;
   }
   if (prev_gap != nullptr) to_finalize_.push_back(prev_gap);
 }
 
 
+GapInstruction* MoveOptimizer::LastGap(InstructionBlock* block) {
+  int gap_index = block->last_instruction_index() - 1;
+  auto instr = code()->instructions()[gap_index];
+  return GapInstruction::cast(instr);
+}
+
+
+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 (auto pred_index : block->predecessors()) {
+    auto pred = code()->InstructionBlockAt(pred_index);
+    auto last_instr = code()->instructions()[pred->last_instruction_index()];
+    DCHECK(!last_instr->IsGapMoves());
+    if (last_instr->IsSourcePosition()) continue;
+    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) {
+      auto op = last_instr->InputAt(i);
+      if (!op->IsConstant() && !op->IsImmediate()) return;
+    }
+  }
+  // TODO(dcarney): pass a ZonePool down for this?
+  MoveMap move_map(local_zone());
+  size_t correct_counts = 0;
+  // Accumulate set of shared moves.
+  for (auto pred_index : block->predecessors()) {
+    auto pred = code()->InstructionBlockAt(pred_index);
+    auto gap = LastGap(pred);
+    if (gap->parallel_moves()[0] == nullptr ||
+        gap->parallel_moves()[0]->move_operands()->is_empty()) {
+      return;
+    }
+    auto move_ops = gap->parallel_moves()[0]->move_operands();
+    for (auto op = move_ops->begin(); op != move_ops->end(); ++op) {
+      if (op->IsRedundant()) continue;
+      auto src = *op->source();
+      auto dst = *op->destination();
+      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;
+  // Find insertion point.
+  GapInstruction* gap = nullptr;
+  for (int i = block->first_instruction_index();
+       i <= block->last_instruction_index(); ++i) {
+    auto instr = code()->instructions()[i];
+    if (instr->IsGapMoves()) {
+      gap = GapInstruction::cast(instr);
+      continue;
+    }
+    if (!GapsCanMoveOver(instr)) break;
+  }
+  DCHECK(gap != nullptr);
+  bool gap_initialized = true;
+  if (gap->parallel_moves()[0] == nullptr ||
+      gap->parallel_moves()[0]->move_operands()->is_empty()) {
+    to_finalize_.push_back(gap);
+  } else {
+    // Will compress after insertion.
+    gap_initialized = false;
+    std::swap(gap->parallel_moves()[0], gap->parallel_moves()[1]);
+  }
+  auto move = gap->GetOrCreateParallelMove(
+      static_cast<GapInstruction::InnerPosition>(0), code_zone());
+  // Delete relevant entries in predecessors and move everything to block.
+  bool first_iteration = true;
+  for (auto pred_index : block->predecessors()) {
+    auto pred = code()->InstructionBlockAt(pred_index);
+    auto gap = LastGap(pred);

[brucedawson, 2015/04/06 18:05:31]

This line of code is worrisome because it shadows the 'gap' variable declared on
line 194. There is *probably* not a bug here, but I can't be sure -- the
references to 'gap' on line 237 and 238 make me wonder whether the assignment on
line 220 is supposed to affect them or not.

Regardless of whether or not there is a bug, I think it is worth changing the
variable name to avoid the ambiguity, if only to make the code less confusing
for future readers.

This was found as a new warning by the VC++ /analyze builder.

The warning disappeared for a few days which is why it is now reported as being
'new'.

Bug 427616 is the catch-all bug for bugs/changes related to /analyze.

+    auto move_ops = gap->parallel_moves()[0]->move_operands();
+    for (auto op = move_ops->begin(); op != move_ops->end(); ++op) {
+      if (op->IsRedundant()) continue;
+      MoveKey key = {*op->source(), *op->destination()};
+      auto it = move_map.find(key);
+      USE(it);
+      DCHECK(it != move_map.end());
+      if (first_iteration) {
+        move->AddMove(op->source(), op->destination(), code_zone());
+      }
+      op->Eliminate();
+    }
+    first_iteration = false;
+  }
+  // Compress.
+  if (!gap_initialized) {
+    CompressMoves(&temp_vector_0(), gap->parallel_moves()[0],
+                  gap->parallel_moves()[1]);
+  }
+}
+
+
 // Split multiple loads of the same constant or stack slot off into the second
 // slot and keep remaining moves in the first slot.
 void MoveOptimizer::FinalizeMoves(GapInstruction* gap) {
   auto loads = temp_vector_0();
   DCHECK(loads.empty());
   auto new_moves = temp_vector_1();
   DCHECK(new_moves.empty());
   auto move_ops = gap->parallel_moves()[0]->move_operands();
   for (auto move = move_ops->begin(); move != move_ops->end(); ++move) {
     if (move->IsRedundant()) {
@@ skipping 52 matching lines @@
     std::swap(*new_move, *it);
     ++it;
   }
   DCHECK_EQ(it, slot_1->move_operands()->end());
   new_moves.clear();
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8