[turbofan] fine grained in-block move 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 17 matching lines @@
   bool operator()(const InstructionOperand& a,
                   const InstructionOperand& b) const {
     return a.CompareCanonicalized(b);
   }
 };
 
 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++) {
     ParallelMove* moves = instr->parallel_moves()[i];
     if (moves == nullptr) continue;
     for (MoveOperands* move : *moves) {
       if (!move->IsRedundant()) return i;
       move->Eliminate();
     }
     moves->clear();  // Clear this redundant move.
   }
   return i;
 }
 
 }  // namespace
 
 
 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);
   }
   for (InstructionBlock* block : code()->instruction_blocks()) {
     if (block->PredecessorCount() <= 1) continue;
     if (!block->IsDeferred()) {
       bool has_only_deferred = true;
       for (RpoNumber& pred_id : block->predecessors()) {
         if (!code()->InstructionBlockAt(pred_id)->IsDeferred()) {
           has_only_deferred = false;
           break;
         }
       }
       // This would pull down common moves. If the moves occur in deferred
       // blocks, and the closest common successor is not deferred, we lose the
       // optimization of just spilling/filling in deferred blocks, when the
       // current block is not deferred.
       if (has_only_deferred) continue;
     }
     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();
   DCHECK(eliminated.empty());
 
   if (!left->empty()) {
     // Modify the right moves in place and collect moves that will be killed by
     // merging the two gaps.
     for (MoveOperands* move : *right) {
       if (move->IsRedundant()) continue;
       MoveOperands* to_eliminate = left->PrepareInsertAfter(move);
       if (to_eliminate != nullptr) eliminated.push_back(to_eliminate);
     }
     // Eliminate dead moves.
     for (MoveOperands* to_eliminate : eliminated) {
       to_eliminate->Eliminate();
     }
     eliminated.clear();
   }
   // Add all possibly modified moves from right side.
   for (MoveOperands* move : *right) {
     if (move->IsRedundant()) continue;
     left->push_back(move);
   }
   // Nuke right.
   right->clear();
   DCHECK(eliminated.empty());
 }
 
+void MoveOptimizer::CompressGaps(Instruction* instruction) {
+  int i = FindFirstNonEmptySlot(instruction);
+  bool has_moves = i <= Instruction::LAST_GAP_POSITION;
+  USE(has_moves);
 
-// Smash all consecutive moves into the left most move slot and accumulate them
-// as much as possible across instructions.
+  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())));
+}
+
 void MoveOptimizer::CompressBlock(InstructionBlock* block) {
-  Instruction* prev_instr = nullptr;
-  for (int index = block->code_start(); index < block->code_end(); ++index) {
+  int first_instr_index = block->first_instruction_index();
+  int last_instr_index = block->last_instruction_index();
+
+  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];
-    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]);
-    }
-
-    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);
+    MigrateMoves(instr, prev_instr);
+    RemoveClobberedDestinations(instr);
+    prev_instr = instr;
   }
 }
 
 
 const Instruction* MoveOptimizer::LastInstruction(
     const InstructionBlock* block) const {
   return code()->instructions()[block->last_instruction_index()];
 }
 
 
@@ skipping 40 matching lines @@
         res.first->second++;
         if (res.first->second == block->PredecessorCount()) {
           correct_counts++;
         }
       }
     }
   }
   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
     // 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.destination;
@@ skipping 22 matching lines @@
           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 {
+  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]);
   }
   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);
       if (it != move_map.end()) {
         if (first_iteration) {
           moves->AddMove(move->source(), move->destination());
         }
         move->Eliminate();
       }
     }
     first_iteration = false;
   }
   // Compress.
   if (!gap_initialized) {
     CompressMoves(instr->parallel_moves()[0], instr->parallel_moves()[1]);
   }
+  CompressBlock(block);
 }
 
 
 namespace {
 
 bool IsSlot(const InstructionOperand& op) {
   return op.IsStackSlot() || op.IsDoubleStackSlot();
 }
 
 
 bool LoadCompare(const MoveOperands* a, const MoveOperands* b) {
   if (!a->source().EqualsCanonicalized(b->source())) {
     return a->source().CompareCanonicalized(b->source());
   }
   if (IsSlot(a->destination()) && !IsSlot(b->destination())) return false;
   if (!IsSlot(a->destination()) && IsSlot(b->destination())) return true;
   return a->destination().CompareCanonicalized(b->destination());
 }
 
 }  // namespace
 
 
 // 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(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);
     }
   }
   if (loads.empty()) return;
   // Group the loads by source, moving the preferred destination to the
   // beginning of the group.
   std::sort(loads.begin(), loads.end(), LoadCompare);
   MoveOperands* group_begin = nullptr;
@@ skipping 11 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