[turbofan] fine grained in-block move optimization

src/compiler/move-optimizer.cc

Index: src/compiler/move-optimizer.cc
diff --git a/src/compiler/move-optimizer.cc b/src/compiler/move-optimizer.cc
index 132ac02f423a2d03d069af28c6e3f3f79e9eefa3..53b87bc4b8062df616b59aa311e0fa1d623d486f 100644
--- a/src/compiler/move-optimizer.cc
+++ b/src/compiler/move-optimizer.cc
@@ -35,39 +35,6 @@ typedef ZoneMap<MoveKey, unsigned, MoveKeyCompare> MoveMap;
 typedef ZoneSet<InstructionOperand, CompareOperandModuloType> OperandSet;
 
 
-bool GapsCanMoveOver(Instruction* instr, Zone* zone) {
-  if (instr->IsNop()) return true;
-  if (instr->ClobbersTemps() || instr->ClobbersRegisters() ||
-      instr->ClobbersDoubleRegisters()) {
-    return false;
-  }
-  if (instr->arch_opcode() != ArchOpcode::kArchNop) return false;
-
-  ZoneSet<InstructionOperand, OperandCompare> operands(zone);
-  for (size_t i = 0; i < instr->InputCount(); ++i) {
-    operands.insert(*instr->InputAt(i));
-  }
-  for (size_t i = 0; i < instr->OutputCount(); ++i) {
-    operands.insert(*instr->OutputAt(i));
-  }
-  for (size_t i = 0; i < instr->TempCount(); ++i) {
-    operands.insert(*instr->TempAt(i));
-  }
-  for (int i = Instruction::GapPosition::FIRST_GAP_POSITION;
-       i <= Instruction::GapPosition::LAST_GAP_POSITION; ++i) {
-    ParallelMove* moves = instr->parallel_moves()[i];
-    if (moves == nullptr) continue;
-    for (MoveOperands* move : *moves) {
-      if (operands.count(move->source()) > 0 ||
-          operands.count(move->destination()) > 0) {
-        return false;
-      }
-    }
-  }
-  return true;
-}
-
-
 int FindFirstNonEmptySlot(const Instruction* instr) {
   int i = Instruction::FIRST_GAP_POSITION;
   for (; i <= Instruction::LAST_GAP_POSITION; i++) {
@@ -88,11 +55,13 @@ int FindFirstNonEmptySlot(const Instruction* instr) {
 MoveOptimizer::MoveOptimizer(Zone* local_zone, InstructionSequence* code)
     : local_zone_(local_zone),
       code_(code),
-      to_finalize_(local_zone),
       local_vector_(local_zone) {}
 
 
 void MoveOptimizer::Run() {
+  for (Instruction* instruction : code()->instructions()) {
+    CompressGaps(instruction);
+  }
   for (InstructionBlock* block : code()->instruction_blocks()) {
     CompressBlock(block);
   }
@@ -114,13 +83,136 @@ void MoveOptimizer::Run() {
     }
     OptimizeMerge(block);
   }
-  for (Instruction* gap : to_finalize_) {
+  for (Instruction* gap : code()->instructions()) {
     FinalizeMoves(gap);
   }
 }
 
+void MoveOptimizer::RemoveClobberedDestinations(Instruction* instruction) {
+  if (instruction->IsCall()) return;
+  ParallelMove* moves = instruction->parallel_moves()[0];
+  if (moves == nullptr) return;
 
-void MoveOptimizer::CompressMoves(ParallelMove* left, ParallelMove* right) {
+  DCHECK(instruction->parallel_moves()[1] == nullptr ||
+         instruction->parallel_moves()[1]->empty());
+
+  OperandSet outputs(local_zone());
+  OperandSet inputs(local_zone());
+
+  // Outputs and temps are treated together as potentially clobbering a
+  // destination operand.
+  for (size_t i = 0; i < instruction->OutputCount(); ++i) {
+    outputs.insert(*instruction->OutputAt(i));
+  }
+  for (size_t i = 0; i < instruction->TempCount(); ++i) {
+    outputs.insert(*instruction->TempAt(i));
+  }
+
+  // Input operands block elisions.
+  for (size_t i = 0; i < instruction->InputCount(); ++i) {
+    inputs.insert(*instruction->InputAt(i));
+  }
+
+  // Elide moves made redundant by the instruction.
+  for (MoveOperands* move : *moves) {
+    if (outputs.find(move->destination()) != outputs.end() &&
+        inputs.find(move->destination()) == inputs.end()) {
+      move->Eliminate();
+    }
+  }
+
+  // ret makes any assignment before it unnecessary, except for the one

[Jarin, 2016/02/03 05:25:17]

Nit: Start comments with capital letters, please. (Here and below.)

[Mircea Trofin, 2016/02/04 05:23:31]

Done.

+  // for its input.
+  if (instruction->opcode() == ArchOpcode::kArchRet) {
+    for (MoveOperands* move : *moves) {
+      if (inputs.find(move->destination()) == inputs.end()) {
+        move->Eliminate();
+      }
+    }
+  }
+}
+
+void MoveOptimizer::MigrateMoves(Instruction* to, Instruction* from) {
+  if (from->IsCall()) return;
+
+  ParallelMove* from_moves = from->parallel_moves()[0];
+  if (from_moves == nullptr || from_moves->empty()) return;
+
+  ZoneSet<InstructionOperand, OperandCompare> dst_cant_be(local_zone());
+  ZoneSet<InstructionOperand, OperandCompare> src_cant_be(local_zone());
+
+  // if an operand is an input to the instruction, we cannot move assignments
+  // where it appears on the LHS

[Jarin, 2016/02/03 05:25:17]

Nit: Dot at the end of sentences. (Here and below.)

[Mircea Trofin, 2016/02/04 05:23:31]

Done.

+  for (size_t i = 0; i < from->InputCount(); ++i) {
+    dst_cant_be.insert(*from->InputAt(i));
+  }
+  // if an operand is output to the instruction, we cannot move assignments
+  // where it appears on the RHS, because we would lose its value before the
+  // instruction.
+  // Same for temp operands.

[Jarin, 2016/02/03 05:25:17]

I do not understand why it is still ok to move assignments where the output
appears on LHS. Would not we then end up with different value in the
destination?

I suppose it should not happen that output overwrites previous move, but still
sounds dangerous.

[Mircea Trofin, 2016/02/04 05:23:32]

It's because we first perform RemoveClobberedDestinations first. Added a
comment. 

I could also factor a bit the code in RemoveClobberedDestinations and add a
DCHECK in MigrateMoves, but may be overkill?

+  for (size_t i = 0; i < from->OutputCount(); ++i) {
+    src_cant_be.insert(*from->OutputAt(i));
+  }
+  for (size_t i = 0; i < from->TempCount(); ++i) {
+    src_cant_be.insert(*from->TempAt(i));
+  }
+  for (MoveOperands* move : *from->parallel_moves()[0]) {

[Jarin, 2016/02/03 05:25:17]

from->parallel_moves[0] ==> from_moves

[Mircea Trofin, 2016/02/04 05:23:32]

Done.

+    if (move->IsRedundant()) continue;
+    // assume dest has a value "V". If we have a "dest = y" move, then we can't
+    // move "z = dest", because z would become y rather than "V"
+    src_cant_be.insert(move->destination());

[Jarin, 2016/02/03 05:25:18]

Again, would not it be also bad to swap "dest = y" with "dest = z"?

[Mircea Trofin, 2016/02/04 05:23:31]

By this stage, we did CompressMoves which takes care of that. Added comment.

+  }
+
+  ZoneSet<MoveKey, MoveKeyCompare> move_candidates(local_zone());
+  // We start with all the moves that don't have conflicting source or
+  // destination operands are eligible for being moved down.
+  for (MoveOperands* move : *from_moves) {
+    if (move->IsRedundant()) continue;
+    if (dst_cant_be.find(move->destination()) == dst_cant_be.end()) {
+      MoveKey key = {move->source(), move->destination()};
+      move_candidates.insert(key);
+    }
+  }
+  if (move_candidates.empty()) return;
+
+  // Stabilize the candidate set.
+  bool changed = false;
+  do {
+    changed = false;
+    for (auto iter = move_candidates.begin(); iter != move_candidates.end();) {
+      auto current = iter;
+      ++iter;
+      InstructionOperand src = current->source;
+      if (src_cant_be.find(src) != src_cant_be.end()) {
+        src_cant_be.insert(current->destination);
+        move_candidates.erase(current);
+        changed = true;
+      }
+    }
+  } while (changed);
+
+  ParallelMove to_move(local_zone());
+  for (MoveOperands* move : *from_moves) {
+    if (move->IsRedundant()) continue;
+    MoveKey key = {move->source(), move->destination()};
+    if (move_candidates.find(key) != move_candidates.end()) {
+      to_move.AddMove(move->source(), move->destination(), code_zone());
+      move->Eliminate();
+    }
+  }
+  if (to_move.empty()) return;
+
+  ParallelMove* dest =
+      to->GetOrCreateParallelMove(Instruction::GapPosition::START, code_zone());
+
+  CompressMoves(&to_move, dest);
+  DCHECK(dest->empty());
+  for (MoveOperands* m : to_move) {
+    dest->push_back(m);
+  }
+}
+
+void MoveOptimizer::CompressMoves(ParallelMove* left, MoveOpVector* right) {
   if (right == nullptr) return;
 
   MoveOpVector& eliminated = local_vector();
@@ -150,54 +242,45 @@ void MoveOptimizer::CompressMoves(ParallelMove* left, ParallelMove* right) {
   DCHECK(eliminated.empty());
 }
 
+void MoveOptimizer::CompressGaps(Instruction* instruction) {
+  int i = FindFirstNonEmptySlot(instruction);
+  bool has_moves = i <= Instruction::LAST_GAP_POSITION;
+  USE(has_moves);
+
+  if (i == Instruction::LAST_GAP_POSITION) {
+    std::swap(instruction->parallel_moves()[Instruction::FIRST_GAP_POSITION],
+              instruction->parallel_moves()[Instruction::LAST_GAP_POSITION]);
+  } else if (i == Instruction::FIRST_GAP_POSITION) {
+    CompressMoves(
+        instruction->parallel_moves()[Instruction::FIRST_GAP_POSITION],
+        instruction->parallel_moves()[Instruction::LAST_GAP_POSITION]);
+  }
+  // We either have no moves, or, after swapping or compressing, we have
+  // all the moves in the first gap position, and none in the second/end gap
+  // position.
+  ParallelMove* first =
+      instruction->parallel_moves()[Instruction::FIRST_GAP_POSITION];
+  ParallelMove* last =
+      instruction->parallel_moves()[Instruction::LAST_GAP_POSITION];
+  USE(first);
+  USE(last);
+
+  DCHECK(!has_moves ||
+         (first != nullptr && (last == nullptr || last->empty())));
+}
 
-// Smash all consecutive moves into the left most move slot and accumulate them
-// as much as possible across instructions.
 void MoveOptimizer::CompressBlock(InstructionBlock* block) {
-  Instruction* prev_instr = nullptr;
-  for (int index = block->code_start(); index < block->code_end(); ++index) {
-    Instruction* instr = code()->instructions()[index];
-    int i = FindFirstNonEmptySlot(instr);
-    bool has_moves = i <= Instruction::LAST_GAP_POSITION;
-
-    if (i == Instruction::LAST_GAP_POSITION) {
-      std::swap(instr->parallel_moves()[Instruction::FIRST_GAP_POSITION],
-                instr->parallel_moves()[Instruction::LAST_GAP_POSITION]);
-    } else if (i == Instruction::FIRST_GAP_POSITION) {
-      CompressMoves(instr->parallel_moves()[Instruction::FIRST_GAP_POSITION],
-                    instr->parallel_moves()[Instruction::LAST_GAP_POSITION]);
-    }
-    // We either have no moves, or, after swapping or compressing, we have
-    // all the moves in the first gap position, and none in the second/end gap
-    // position.
-    ParallelMove* first =
-        instr->parallel_moves()[Instruction::FIRST_GAP_POSITION];
-    ParallelMove* last =
-        instr->parallel_moves()[Instruction::LAST_GAP_POSITION];
-    USE(last);
-
-    DCHECK(!has_moves ||
-           (first != nullptr && (last == nullptr || last->empty())));
-
-    if (prev_instr != nullptr) {
-      if (has_moves) {
-        // Smash first into prev_instr, killing left.
-        ParallelMove* pred_moves = prev_instr->parallel_moves()[0];
-        CompressMoves(pred_moves, first);
-      }
-      // Slide prev_instr down so we always know where to look for it.
-      std::swap(prev_instr->parallel_moves()[0], instr->parallel_moves()[0]);
-    }
+  int first_instr_index = block->first_instruction_index();
+  int last_instr_index = block->last_instruction_index();
 
-    prev_instr = instr->parallel_moves()[0] == nullptr ? nullptr : instr;
-    if (GapsCanMoveOver(instr, local_zone())) continue;
-    if (prev_instr != nullptr) {
-      to_finalize_.push_back(prev_instr);
-      prev_instr = nullptr;
-    }
-  }
-  if (prev_instr != nullptr) {
-    to_finalize_.push_back(prev_instr);
+  Instruction* prev_instr = code()->instructions()[first_instr_index];
+  RemoveClobberedDestinations(prev_instr);
+
+  for (int index = first_instr_index + 1; index <= last_instr_index; ++index) {
+    Instruction* instr = code()->instructions()[index];
+    MigrateMoves(instr, prev_instr);
+    RemoveClobberedDestinations(instr);
+    prev_instr = instr;
   }
 }
 
@@ -258,15 +341,7 @@ void MoveOptimizer::OptimizeMerge(InstructionBlock* block) {
   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 (correct_counts != move_map.size() ||
-        !GapsCanMoveOver(instr, local_zone()) || !instr->AreMovesRedundant())
-      break;
-  }
-  DCHECK_NOT_NULL(instr);
+  Instruction* instr = code()->instructions()[block->first_instruction_index()];
 
   if (correct_counts != move_map.size()) {
     // Moves that are unique to each predecessor won't be pushed to the common
@@ -309,10 +384,8 @@ void MoveOptimizer::OptimizeMerge(InstructionBlock* block) {
 
   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 {
+  if (instr->parallel_moves()[0] != nullptr &&
+      !instr->parallel_moves()[0]->empty()) {
     // Will compress after insertion.
     gap_initialized = false;
     std::swap(instr->parallel_moves()[0], instr->parallel_moves()[1]);
@@ -340,6 +413,7 @@ void MoveOptimizer::OptimizeMerge(InstructionBlock* block) {
   if (!gap_initialized) {
     CompressMoves(instr->parallel_moves()[0], instr->parallel_moves()[1]);
   }
+  CompressBlock(block);
 }
 
 
@@ -368,8 +442,10 @@ void MoveOptimizer::FinalizeMoves(Instruction* instr) {
   MoveOpVector& loads = local_vector();
   DCHECK(loads.empty());
 
+  ParallelMove* parallel_moves = instr->parallel_moves()[0];
+  if (parallel_moves == nullptr) return;
   // Find all the loads.
-  for (MoveOperands* move : *instr->parallel_moves()[0]) {
+  for (MoveOperands* move : *parallel_moves) {
     if (move->IsRedundant()) continue;
     if (move->source().IsConstant() || IsSlot(move->source())) {
       loads.push_back(move);