deps/v8/src/compiler/move-optimizer.cc

   1 // Copyright 2014 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "src/compiler/move-optimizer.h"
   6
   7 namespace v8 {
   8 namespace internal {
   9 namespace compiler {
  10
  11 namespace {
  12
  13 MoveOperands* PrepareInsertAfter(ParallelMove* left, MoveOperands* move,
  14                                  Zone* zone) {
  15   auto move_ops = left->move_operands();
  16   MoveOperands* replacement = nullptr;
  17   MoveOperands* to_eliminate = nullptr;
  18   for (auto curr = move_ops->begin(); curr != move_ops->end(); ++curr) {
  19     if (curr->IsEliminated()) continue;
  20     if (curr->destination()->Equals(move->source())) {
  21       DCHECK(!replacement);
  22       replacement = curr;
  23       if (to_eliminate != nullptr) break;
  24     } else if (curr->destination()->Equals(move->destination())) {
  25       DCHECK(!to_eliminate);
  26       to_eliminate = curr;
  27       if (replacement != nullptr) break;
  28     }
  29   }
  30   DCHECK(!(replacement == to_eliminate && replacement != nullptr));
  31   if (replacement != nullptr) {
  32     auto new_source = InstructionOperand::New(
  33         zone, replacement->source()->kind(), replacement->source()->index());
  34     move->set_source(new_source);
  35   }
  36   return to_eliminate;
  37 }
  38
  39
  40 bool GapsCanMoveOver(Instruction* instr) {
  41   DCHECK(!instr->IsGapMoves());
  42   return instr->IsSourcePosition() || instr->IsNop();
  43 }
  44
  45
  46 int FindFirstNonEmptySlot(GapInstruction* gap) {
  47   int i = GapInstruction::FIRST_INNER_POSITION;
  48   for (; i <= GapInstruction::LAST_INNER_POSITION; i++) {
  49     auto move = gap->parallel_moves()[i];
  50     if (move == nullptr) continue;
  51     auto move_ops = move->move_operands();
  52     auto op = move_ops->begin();
  53     for (; op != move_ops->end(); ++op) {
  54       if (!op->IsRedundant()) break;
  55       op->Eliminate();
  56     }
  57     if (op != move_ops->end()) break;  // Found non-redundant move.
  58     move_ops->Rewind(0);               // Clear this redundant move.
  59   }
  60   return i;
  61 }
  62
  63 }  // namepace
  64
  65
  66 MoveOptimizer::MoveOptimizer(Zone* local_zone, InstructionSequence* code)
  67     : local_zone_(local_zone),
  68       code_(code),
  69       to_finalize_(local_zone),
  70       temp_vector_0_(local_zone),
  71       temp_vector_1_(local_zone) {}
  72
  73
  74 void MoveOptimizer::Run() {
  75   for (auto* block : code()->instruction_blocks()) {
  76     CompressBlock(block);
  77   }
  78   for (auto gap : to_finalize_) {
  79     FinalizeMoves(gap);
  80   }
  81 }
  82
  83
  84 void MoveOptimizer::CompressMoves(MoveOpVector* eliminated, ParallelMove* left,
  85                                   ParallelMove* right) {
  86   DCHECK(eliminated->empty());
  87   auto move_ops = right->move_operands();
  88   if (!left->move_operands()->is_empty()) {
  89     // Modify the right moves in place and collect moves that will be killed by
  90     // merging the two gaps.
  91     for (auto op = move_ops->begin(); op != move_ops->end(); ++op) {
  92       if (op->IsRedundant()) continue;
  93       MoveOperands* to_eliminate = PrepareInsertAfter(left, op, code_zone());
  94       if (to_eliminate != nullptr) eliminated->push_back(to_eliminate);
  95     }
  96     // Eliminate dead moves.  Must happen before insertion of new moves as the
  97     // contents of eliminated are pointers into a list.
  98     for (auto to_eliminate : *eliminated) {
  99       to_eliminate->Eliminate();
 100     }
 101     eliminated->clear();
 102   }
 103   // Add all possibly modified moves from right side.
 104   for (auto op = move_ops->begin(); op != move_ops->end(); ++op) {
 105     if (op->IsRedundant()) continue;
 106     left->move_operands()->Add(*op, code_zone());
 107   }
 108   // Nuke right.
 109   move_ops->Rewind(0);
 110 }
 111
 112
 113 // Smash all consecutive moves into the left most move slot and accumulate them
 114 // as much as possible across instructions.
 115 void MoveOptimizer::CompressBlock(InstructionBlock* block) {
 116   auto temp_vector = temp_vector_0();
 117   DCHECK(temp_vector.empty());
 118   GapInstruction* prev_gap = nullptr;
 119   for (int index = block->code_start(); index < block->code_end(); ++index) {
 120     auto instr = code()->instructions()[index];
 121     if (!instr->IsGapMoves()) {
 122       if (GapsCanMoveOver(instr)) continue;
 123       if (prev_gap != nullptr) to_finalize_.push_back(prev_gap);
 124       prev_gap = nullptr;
 125       continue;
 126     }
 127     auto gap = GapInstruction::cast(instr);
 128     int i = FindFirstNonEmptySlot(gap);
 129     // Nothing to do here.
 130     if (i == GapInstruction::LAST_INNER_POSITION + 1) {
 131       if (prev_gap != nullptr) {
 132         // Slide prev_gap down so we always know where to look for it.
 133         std::swap(prev_gap->parallel_moves()[0], gap->parallel_moves()[0]);
 134         prev_gap = gap;
 135       }
 136       continue;
 137     }
 138     // Move the first non-empty gap to position 0.
 139     std::swap(gap->parallel_moves()[0], gap->parallel_moves()[i]);
 140     auto left = gap->parallel_moves()[0];
 141     // Compress everything into position 0.
 142     for (++i; i <= GapInstruction::LAST_INNER_POSITION; ++i) {
 143       auto move = gap->parallel_moves()[i];
 144       if (move == nullptr) continue;
 145       CompressMoves(&temp_vector, left, move);
 146     }
 147     if (prev_gap != nullptr) {
 148       // Smash left into prev_gap, killing left.
 149       auto pred_moves = prev_gap->parallel_moves()[0];
 150       CompressMoves(&temp_vector, pred_moves, left);
 151       // Slide prev_gap down so we always know where to look for it.
 152       std::swap(prev_gap->parallel_moves()[0], gap->parallel_moves()[0]);
 153     }
 154     prev_gap = gap;
 155   }
 156   if (prev_gap != nullptr) to_finalize_.push_back(prev_gap);
 157 }
 158
 159
 160 // Split multiple loads of the same constant or stack slot off into the second
 161 // slot and keep remaining moves in the first slot.
 162 void MoveOptimizer::FinalizeMoves(GapInstruction* gap) {
 163   auto loads = temp_vector_0();
 164   DCHECK(loads.empty());
 165   auto new_moves = temp_vector_1();
 166   DCHECK(new_moves.empty());
 167   auto move_ops = gap->parallel_moves()[0]->move_operands();
 168   for (auto move = move_ops->begin(); move != move_ops->end(); ++move) {
 169     if (move->IsRedundant()) {
 170       move->Eliminate();
 171       continue;
 172     }
 173     if (!(move->source()->IsConstant() || move->source()->IsStackSlot() ||
 174           move->source()->IsDoubleStackSlot()))
 175       continue;
 176     // Search for existing move to this slot.
 177     MoveOperands* found = nullptr;
 178     for (auto load : loads) {
 179       if (load->source()->Equals(move->source())) {
 180         found = load;
 181         break;
 182       }
 183     }
 184     // Not found so insert.
 185     if (found == nullptr) {
 186       loads.push_back(move);
 187       // Replace source with copy for later use.
 188       auto dest = move->destination();
 189       move->set_destination(
 190           InstructionOperand::New(code_zone(), dest->kind(), dest->index()));
 191       continue;
 192     }
 193     if ((found->destination()->IsStackSlot() ||
 194          found->destination()->IsDoubleStackSlot()) &&
 195         !(move->destination()->IsStackSlot() ||
 196           move->destination()->IsDoubleStackSlot())) {
 197       // Found a better source for this load.  Smash it in place to affect other
 198       // loads that have already been split.
 199       InstructionOperand::Kind found_kind = found->destination()->kind();
 200       int found_index = found->destination()->index();
 201       auto next_dest =
 202           InstructionOperand::New(code_zone(), found_kind, found_index);
 203       auto dest = move->destination();
 204       found->destination()->ConvertTo(dest->kind(), dest->index());
 205       move->set_destination(next_dest);
 206     }
 207     // move from load destination.
 208     move->set_source(found->destination());
 209     new_moves.push_back(move);
 210   }
 211   loads.clear();
 212   if (new_moves.empty()) return;
 213   // Insert all new moves into slot 1.
 214   auto slot_1 = gap->GetOrCreateParallelMove(
 215       static_cast<GapInstruction::InnerPosition>(1), code_zone());
 216   DCHECK(slot_1->move_operands()->is_empty());
 217   slot_1->move_operands()->AddBlock(MoveOperands(nullptr, nullptr),
 218                                     static_cast<int>(new_moves.size()),
 219                                     code_zone());
 220   auto it = slot_1->move_operands()->begin();
 221   for (auto new_move : new_moves) {
 222     std::swap(*new_move, *it);
 223     ++it;
 224   }
 225   DCHECK_EQ(it, slot_1->move_operands()->end());
 226   new_moves.clear();
 227 }
 228
 229 }  // namespace compiler
 230 }  // namespace internal
 231 }  // namespace v8