src/v8/src/compiler/move-optimizer.cc - cobalt - 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;

 class OperandSet {
  public:
   explicit OperandSet(ZoneVector<InstructionOperand>* buffer)
       : set_(buffer), fp_reps_(0) {
     buffer->clear();
   }

   void InsertOp(const InstructionOperand& op) {
     set_->push_back(op);

     if (!kSimpleFPAliasing && op.IsFPRegister())
       fp_reps_ |= RepBit(LocationOperand::cast(op).representation());
   }

   bool Contains(const InstructionOperand& op) const {
     for (const InstructionOperand& elem : *set_) {
       if (elem.EqualsCanonicalized(op)) return true;
     }
     return false;
   }

   bool ContainsOpOrAlias(const InstructionOperand& op) const {
     if (Contains(op)) return true;

     if (!kSimpleFPAliasing && op.IsFPRegister()) {
       // Platforms where FP registers have complex aliasing need extra checks.
       const LocationOperand& loc = LocationOperand::cast(op);
       MachineRepresentation rep = loc.representation();
       // If haven't encountered mixed rep FP registers, skip the extra checks.
       if (!HasMixedFPReps(fp_reps_ | RepBit(rep))) return false;

       // Check register against aliasing registers of other FP representations.
       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::Default();
       int base = -1;
       int aliases =
           config->GetAliases(rep, loc.register_code(), other_rep1, &base);
       DCHECK(aliases > 0 || (aliases == 0 && base == -1));
       while (aliases--) {
         if (Contains(AllocatedOperand(LocationOperand::REGISTER, other_rep1,
                                       base + aliases))) {
           return true;
         }
       }
       aliases = config->GetAliases(rep, loc.register_code(), other_rep2, &base);
       DCHECK(aliases > 0 || (aliases == 0 && base == -1));
       while (aliases--) {
         if (Contains(AllocatedOperand(LocationOperand::REGISTER, other_rep2,
                                       base + aliases))) {
           return true;
         }
       }
     }
     return false;
   }

  private:
   static int RepBit(MachineRepresentation rep) {
     return 1 << static_cast<int>(rep);
   }

   static bool HasMixedFPReps(int reps) {
     return reps && !base::bits::IsPowerOfTwo(reps);
   }

   ZoneVector<InstructionOperand>* set_;
   int fp_reps_;
 };

 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),
       operand_buffer1(local_zone),
       operand_buffer2(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(&operand_buffer1);
   OperandSet inputs(&operand_buffer2);

   // Outputs and temps are treated together as potentially clobbering a
   // destination operand.
   for (size_t i = 0; i < instruction->OutputCount(); ++i) {
     outputs.InsertOp(*instruction->OutputAt(i));
   }
   for (size_t i = 0; i < instruction->TempCount(); ++i) {
     outputs.InsertOp(*instruction->TempAt(i));
   }

   // Input operands block elisions.
   for (size_t i = 0; i < instruction->InputCount(); ++i) {
     inputs.InsertOp(*instruction->InputAt(i));
   }

   // Elide moves made redundant by the instruction.
   for (MoveOperands* move : *moves) {
     if (outputs.ContainsOpOrAlias(move->destination()) &&
         !inputs.ContainsOpOrAlias(move->destination())) {
       move->Eliminate();
     }
   }

   // The ret instruction makes any assignment before it unnecessary, except for
   // the one for its input.
   if (instruction->IsRet() || instruction->IsTailCall()) {
     for (MoveOperands* move : *moves) {
       if (!inputs.ContainsOpOrAlias(move->destination())) {
         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(&operand_buffer1);
   OperandSet src_cant_be(&operand_buffer2);

   // 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.InsertOp(*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.InsertOp(*from->OutputAt(i));
   }
   for (size_t i = 0; i < from->TempCount(); ++i) {
     src_cant_be.InsertOp(*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.InsertOp(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 (!dst_cant_be.ContainsOpOrAlias(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 (src_cant_be.ContainsOpOrAlias(src)) {
         src_cant_be.InsertOp(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;
       left->PrepareInsertAfter(move, &eliminated);
     }
     // 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_LT(1, block->PredecessorCount());
   // 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 ZoneStats 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(&operand_buffer1);
     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.InsertOp(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.ContainsOpOrAlias(current->first.source)) {
           conflicting_srcs.InsertOp(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.IsFPStackSlot();
 }


 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;

	class OperandSet {
	public:
	explicit OperandSet(ZoneVector<InstructionOperand>* buffer)
	: set_(buffer), fp_reps_(0) {
	buffer->clear();
	}

	void InsertOp(const InstructionOperand& op) {
	set_->push_back(op);

	if (!kSimpleFPAliasing && op.IsFPRegister())
	fp_reps_ \|= RepBit(LocationOperand::cast(op).representation());
	}

	bool Contains(const InstructionOperand& op) const {
	for (const InstructionOperand& elem : *set_) {
	if (elem.EqualsCanonicalized(op)) return true;
	}
	return false;
	}

	bool ContainsOpOrAlias(const InstructionOperand& op) const {
	if (Contains(op)) return true;

	if (!kSimpleFPAliasing && op.IsFPRegister()) {
	// Platforms where FP registers have complex aliasing need extra checks.
	const LocationOperand& loc = LocationOperand::cast(op);
	MachineRepresentation rep = loc.representation();
	// If haven't encountered mixed rep FP registers, skip the extra checks.
	if (!HasMixedFPReps(fp_reps_ \| RepBit(rep))) return false;

	// Check register against aliasing registers of other FP representations.
	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::Default();
	int base = -1;
	int aliases =
	config->GetAliases(rep, loc.register_code(), other_rep1, &base);
	DCHECK(aliases > 0 \|\| (aliases == 0 && base == -1));
	while (aliases--) {
	if (Contains(AllocatedOperand(LocationOperand::REGISTER, other_rep1,
	base + aliases))) {
	return true;
	}
	}
	aliases = config->GetAliases(rep, loc.register_code(), other_rep2, &base);
	DCHECK(aliases > 0 \|\| (aliases == 0 && base == -1));
	while (aliases--) {
	if (Contains(AllocatedOperand(LocationOperand::REGISTER, other_rep2,
	base + aliases))) {
	return true;
	}
	}
	}
	return false;
	}

	private:
	static int RepBit(MachineRepresentation rep) {
	return 1 << static_cast<int>(rep);
	}

	static bool HasMixedFPReps(int reps) {
	return reps && !base::bits::IsPowerOfTwo(reps);
	}

	ZoneVector<InstructionOperand>* set_;
	int fp_reps_;
	};

	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),
	operand_buffer1(local_zone),
	operand_buffer2(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(&operand_buffer1);
	OperandSet inputs(&operand_buffer2);

	// Outputs and temps are treated together as potentially clobbering a
	// destination operand.
	for (size_t i = 0; i < instruction->OutputCount(); ++i) {
	outputs.InsertOp(*instruction->OutputAt(i));
	}
	for (size_t i = 0; i < instruction->TempCount(); ++i) {
	outputs.InsertOp(*instruction->TempAt(i));
	}

	// Input operands block elisions.
	for (size_t i = 0; i < instruction->InputCount(); ++i) {
	inputs.InsertOp(*instruction->InputAt(i));
	}

	// Elide moves made redundant by the instruction.
	for (MoveOperands* move : *moves) {
	if (outputs.ContainsOpOrAlias(move->destination()) &&
	!inputs.ContainsOpOrAlias(move->destination())) {
	move->Eliminate();
	}
	}

	// The ret instruction makes any assignment before it unnecessary, except for
	// the one for its input.
	if (instruction->IsRet() \|\| instruction->IsTailCall()) {
	for (MoveOperands* move : *moves) {
	if (!inputs.ContainsOpOrAlias(move->destination())) {
	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(&operand_buffer1);
	OperandSet src_cant_be(&operand_buffer2);

	// 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.InsertOp(*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.InsertOp(*from->OutputAt(i));
	}
	for (size_t i = 0; i < from->TempCount(); ++i) {
	src_cant_be.InsertOp(*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.InsertOp(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 (!dst_cant_be.ContainsOpOrAlias(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 (src_cant_be.ContainsOpOrAlias(src)) {
	src_cant_be.InsertOp(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;
	left->PrepareInsertAfter(move, &eliminated);
	}
	// 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_LT(1, block->PredecessorCount());
	// 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 ZoneStats 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(&operand_buffer1);
	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.InsertOp(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.ContainsOpOrAlias(current->first.source)) {
	conflicting_srcs.InsertOp(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.IsFPStackSlot();
	}


	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