src/compiler/move-optimizer.cc - v8/v8 - Git at Google

 // 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 {

 struct MoveKey {
   InstructionOperand source;
   InstructionOperand destination;
 };

 struct MoveKeyCompare {
   bool operator()(const MoveKey& a, const MoveKey& b) const {
     if (a.source.EqualsCanonicalized(b.source)) {
       return a.destination.CompareCanonicalized(b.destination);
     }
     return a.source.CompareCanonicalized(b.source);
   }
 };

 typedef ZoneMap<MoveKey, unsigned, MoveKeyCompare> MoveMap;
 typedef ZoneSet<InstructionOperand, CompareOperandModuloType> OperandSet;

 bool Blocks(const OperandSet& set, const InstructionOperand& operand) {
   if (set.find(operand) != set.end()) return true;
   // Only FP registers on archs with non-simple aliasing need extra checks.
   if (!operand.IsFPRegister() || kSimpleFPAliasing) return false;

   // Check operand against operands of other FP types for interference.
   const LocationOperand& loc = LocationOperand::cast(operand);
   MachineRepresentation rep = loc.representation();
   MachineRepresentation other_rep1, other_rep2;
   switch (rep) {
     case MachineRepresentation::kFloat32:
       other_rep1 = MachineRepresentation::kFloat64;
       other_rep2 = MachineRepresentation::kSimd128;
       break;
     case MachineRepresentation::kFloat64:
       other_rep1 = MachineRepresentation::kFloat32;
       other_rep2 = MachineRepresentation::kSimd128;
       break;
     case MachineRepresentation::kSimd128:
       other_rep1 = MachineRepresentation::kFloat32;
       other_rep2 = MachineRepresentation::kFloat64;
       break;
     default:
       UNREACHABLE();
       break;
   }
   const RegisterConfiguration* config = RegisterConfiguration::Turbofan();
   int base = -1;
   int aliases = config->GetAliases(rep, loc.register_code(), other_rep1, &base);
   DCHECK(aliases > 0 || (aliases == 0 && base == -1));
   while (aliases--) {
     if (set.find(LocationOperand(loc.kind(), loc.location_kind(), other_rep1,
                                  base + aliases)) != set.end())
       return true;
   }
   aliases = config->GetAliases(rep, loc.register_code(), other_rep2, &base);
   DCHECK(aliases > 0 || (aliases == 0 && base == -1));
   while (aliases--) {
     if (set.find(LocationOperand(loc.kind(), loc.location_kind(), other_rep2,
                                  base + aliases)) != set.end())
       return true;
   }
   return false;
 }

 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),
       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 : code()->instructions()) {
     FinalizeMoves(gap);
   }
 }

 void MoveOptimizer::RemoveClobberedDestinations(Instruction* instruction) {
   if (instruction->IsCall()) return;
   ParallelMove* moves = instruction->parallel_moves()[0];
   if (moves == nullptr) return;

   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();
     }
   }

   // The ret instruction makes any assignment before it unnecessary, except for
   // the one 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;

   OperandSet dst_cant_be(local_zone());
   OperandSet src_cant_be(local_zone());

   // If an operand is an input to the instruction, we cannot move assignments
   // where it appears on the LHS.
   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.
   // The output can't appear on the LHS because we performed
   // RemoveClobberedDestinations for the "from" instruction.
   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_moves) {
     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".
     // We assume CompressMoves has happened before this, which means we don't
     // have more than one assignment to dest.
     src_cant_be.insert(move->destination());
   }

   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 (!Blocks(dst_cant_be, move->destination())) {
       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 (Blocks(src_cant_be, src)) {
         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);

   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) {
   int first_instr_index = block->first_instruction_index();
   int last_instr_index = block->last_instruction_index();

   // Start by removing gap assignments where the output of the subsequent
   // instruction appears on LHS, as long as they are not needed by its input.
   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];
     // Migrate to the gap of prev_instr eligible moves from instr.
     MigrateMoves(instr, prev_instr);
     // Remove gap assignments clobbered by instr's output.
     RemoveClobberedDestinations(instr);
     prev_instr = instr;
   }
 }


 const Instruction* MoveOptimizer::LastInstruction(
     const InstructionBlock* block) const {
   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;
     }
   }
   // TODO(dcarney): pass a ZonePool down for this?
   MoveMap move_map(local_zone());
   size_t correct_counts = 0;
   // Accumulate set of shared moves.
   for (RpoNumber& pred_index : block->predecessors()) {
     const InstructionBlock* pred = code()->InstructionBlockAt(pred_index);
     const Instruction* instr = LastInstruction(pred);
     if (instr->parallel_moves()[0] == nullptr ||
         instr->parallel_moves()[0]->empty()) {
       return;
     }
     for (const MoveOperands* move : *instr->parallel_moves()[0]) {
       if (move->IsRedundant()) continue;
       InstructionOperand src = move->source();
       InstructionOperand dst = move->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 == 0) return;

   // Find insertion point.
   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;
         // 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.source) !=
             conflicting_srcs.end()) {
           conflicting_srcs.insert(current->first.destination);
           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()) {
     // 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 : *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;
   for (MoveOperands* load : loads) {
     // New group.
     if (group_begin == nullptr ||
         !load->source().EqualsCanonicalized(group_begin->source())) {
       group_begin = load;
       continue;
     }
     // Nothing to be gained from splitting here.
     if (IsSlot(group_begin->destination())) continue;
     // Insert new move into slot 1.
     ParallelMove* slot_1 = instr->GetOrCreateParallelMove(
         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
	// 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 {

	struct MoveKey {
	InstructionOperand source;
	InstructionOperand destination;
	};

	struct MoveKeyCompare {
	bool operator()(const MoveKey& a, const MoveKey& b) const {
	if (a.source.EqualsCanonicalized(b.source)) {
	return a.destination.CompareCanonicalized(b.destination);
	}
	return a.source.CompareCanonicalized(b.source);
	}
	};

	typedef ZoneMap<MoveKey, unsigned, MoveKeyCompare> MoveMap;
	typedef ZoneSet<InstructionOperand, CompareOperandModuloType> OperandSet;

	bool Blocks(const OperandSet& set, const InstructionOperand& operand) {
	if (set.find(operand) != set.end()) return true;
	// Only FP registers on archs with non-simple aliasing need extra checks.
	if (!operand.IsFPRegister() \|\| kSimpleFPAliasing) return false;

	// Check operand against operands of other FP types for interference.
	const LocationOperand& loc = LocationOperand::cast(operand);
	MachineRepresentation rep = loc.representation();
	MachineRepresentation other_rep1, other_rep2;
	switch (rep) {
	case MachineRepresentation::kFloat32:
	other_rep1 = MachineRepresentation::kFloat64;
	other_rep2 = MachineRepresentation::kSimd128;
	break;
	case MachineRepresentation::kFloat64:
	other_rep1 = MachineRepresentation::kFloat32;
	other_rep2 = MachineRepresentation::kSimd128;
	break;
	case MachineRepresentation::kSimd128:
	other_rep1 = MachineRepresentation::kFloat32;
	other_rep2 = MachineRepresentation::kFloat64;
	break;
	default:
	UNREACHABLE();
	break;
	}
	const RegisterConfiguration* config = RegisterConfiguration::Turbofan();
	int base = -1;
	int aliases = config->GetAliases(rep, loc.register_code(), other_rep1, &base);
	DCHECK(aliases > 0 \|\| (aliases == 0 && base == -1));
	while (aliases--) {
	if (set.find(LocationOperand(loc.kind(), loc.location_kind(), other_rep1,
	base + aliases)) != set.end())
	return true;
	}
	aliases = config->GetAliases(rep, loc.register_code(), other_rep2, &base);
	DCHECK(aliases > 0 \|\| (aliases == 0 && base == -1));
	while (aliases--) {
	if (set.find(LocationOperand(loc.kind(), loc.location_kind(), other_rep2,
	base + aliases)) != set.end())
	return true;
	}
	return false;
	}

	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),
	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 : code()->instructions()) {
	FinalizeMoves(gap);
	}
	}

	void MoveOptimizer::RemoveClobberedDestinations(Instruction* instruction) {
	if (instruction->IsCall()) return;
	ParallelMove* moves = instruction->parallel_moves()[0];
	if (moves == nullptr) return;

	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();
	}
	}

	// The ret instruction makes any assignment before it unnecessary, except for
	// the one 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;

	OperandSet dst_cant_be(local_zone());
	OperandSet src_cant_be(local_zone());

	// If an operand is an input to the instruction, we cannot move assignments
	// where it appears on the LHS.
	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.
	// The output can't appear on the LHS because we performed
	// RemoveClobberedDestinations for the "from" instruction.
	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_moves) {
	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".
	// We assume CompressMoves has happened before this, which means we don't
	// have more than one assignment to dest.
	src_cant_be.insert(move->destination());
	}

	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 (!Blocks(dst_cant_be, move->destination())) {
	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 (Blocks(src_cant_be, src)) {
	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);

	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) {
	int first_instr_index = block->first_instruction_index();
	int last_instr_index = block->last_instruction_index();

	// Start by removing gap assignments where the output of the subsequent
	// instruction appears on LHS, as long as they are not needed by its input.
	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];
	// Migrate to the gap of prev_instr eligible moves from instr.
	MigrateMoves(instr, prev_instr);
	// Remove gap assignments clobbered by instr's output.
	RemoveClobberedDestinations(instr);
	prev_instr = instr;
	}
	}


	const Instruction* MoveOptimizer::LastInstruction(
	const InstructionBlock* block) const {
	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;
	}
	}
	// TODO(dcarney): pass a ZonePool down for this?
	MoveMap move_map(local_zone());
	size_t correct_counts = 0;
	// Accumulate set of shared moves.
	for (RpoNumber& pred_index : block->predecessors()) {
	const InstructionBlock* pred = code()->InstructionBlockAt(pred_index);
	const Instruction* instr = LastInstruction(pred);
	if (instr->parallel_moves()[0] == nullptr \|\|
	instr->parallel_moves()[0]->empty()) {
	return;
	}
	for (const MoveOperands* move : *instr->parallel_moves()[0]) {
	if (move->IsRedundant()) continue;
	InstructionOperand src = move->source();
	InstructionOperand dst = move->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 == 0) return;

	// Find insertion point.
	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;
	// 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.source) !=
	conflicting_srcs.end()) {
	conflicting_srcs.insert(current->first.destination);
	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()) {
	// 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 : *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;
	for (MoveOperands* load : loads) {
	// New group.
	if (group_begin == nullptr \|\|
	!load->source().EqualsCanonicalized(group_begin->source())) {
	group_begin = load;
	continue;
	}
	// Nothing to be gained from splitting here.
	if (IsSlot(group_begin->destination())) continue;
	// Insert new move into slot 1.
	ParallelMove* slot_1 = instr->GetOrCreateParallelMove(
	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