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 typedef std::pair<InstructionOperand, InstructionOperand> MoveKey;
  14 typedef ZoneMap<MoveKey, unsigned> MoveMap;
  15 typedef ZoneSet<InstructionOperand> OperandSet;
  16
  17
  18 bool GapsCanMoveOver(Instruction* instr) {
  19   DCHECK(!instr->IsGapMoves());
  20   return instr->IsSourcePosition() || instr->IsNop();
  21 }
  22
  23
  24 int FindFirstNonEmptySlot(GapInstruction* gap) {
  25   int i = GapInstruction::FIRST_INNER_POSITION;
  26   for (; i <= GapInstruction::LAST_INNER_POSITION; i++) {
  27     auto move = gap->parallel_moves()[i];
  28     if (move == nullptr) continue;
  29     auto move_ops = move->move_operands();
  30     auto op = move_ops->begin();
  31     for (; op != move_ops->end(); ++op) {
  32       if (!op->IsRedundant()) break;
  33       op->Eliminate();
  34     }
  35     if (op != move_ops->end()) break;  // Found non-redundant move.
  36     move_ops->Rewind(0);               // Clear this redundant move.
  37   }
  38   return i;
  39 }
  40
  41 }  // namepace
  42
  43
  44 MoveOptimizer::MoveOptimizer(Zone* local_zone, InstructionSequence* code)
  45     : local_zone_(local_zone),
  46       code_(code),
  47       to_finalize_(local_zone),
  48       temp_vector_0_(local_zone),
  49       temp_vector_1_(local_zone) {}
  50
  51
  52 void MoveOptimizer::Run() {
  53   for (auto* block : code()->instruction_blocks()) {
  54     CompressBlock(block);
  55   }
  56   for (auto block : code()->instruction_blocks()) {
  57     if (block->PredecessorCount() <= 1) continue;
  58     OptimizeMerge(block);
  59   }
  60   for (auto gap : to_finalize_) {
  61     FinalizeMoves(gap);
  62   }
  63 }
  64
  65
  66 void MoveOptimizer::CompressMoves(MoveOpVector* eliminated, ParallelMove* left,
  67                                   ParallelMove* right) {
  68   DCHECK(eliminated->empty());
  69   auto move_ops = right->move_operands();
  70   if (!left->move_operands()->is_empty()) {
  71     // Modify the right moves in place and collect moves that will be killed by
  72     // merging the two gaps.
  73     for (auto op = move_ops->begin(); op != move_ops->end(); ++op) {
  74       if (op->IsRedundant()) continue;
  75       auto to_eliminate = left->PrepareInsertAfter(op);
  76       if (to_eliminate != nullptr) eliminated->push_back(to_eliminate);
  77     }
  78     // Eliminate dead moves.  Must happen before insertion of new moves as the
  79     // contents of eliminated are pointers into a list.
  80     for (auto to_eliminate : *eliminated) {
  81       to_eliminate->Eliminate();
  82     }
  83     eliminated->clear();
  84   }
  85   // Add all possibly modified moves from right side.
  86   for (auto op = move_ops->begin(); op != move_ops->end(); ++op) {
  87     if (op->IsRedundant()) continue;
  88     left->move_operands()->Add(*op, code_zone());
  89   }
  90   // Nuke right.
  91   move_ops->Rewind(0);
  92 }
  93
  94
  95 // Smash all consecutive moves into the left most move slot and accumulate them
  96 // as much as possible across instructions.
  97 void MoveOptimizer::CompressBlock(InstructionBlock* block) {
  98   auto temp_vector = temp_vector_0();
  99   DCHECK(temp_vector.empty());
 100   GapInstruction* prev_gap = nullptr;
 101   for (int index = block->code_start(); index < block->code_end(); ++index) {
 102     auto instr = code()->instructions()[index];
 103     if (!instr->IsGapMoves()) {
 104       if (GapsCanMoveOver(instr)) continue;
 105       if (prev_gap != nullptr) to_finalize_.push_back(prev_gap);
 106       prev_gap = nullptr;
 107       continue;
 108     }
 109     auto gap = GapInstruction::cast(instr);
 110     int i = FindFirstNonEmptySlot(gap);
 111     // Nothing to do here.
 112     if (i == GapInstruction::LAST_INNER_POSITION + 1) {
 113       if (prev_gap != nullptr) {
 114         // Slide prev_gap down so we always know where to look for it.
 115         std::swap(prev_gap->parallel_moves()[0], gap->parallel_moves()[0]);
 116         prev_gap = gap;
 117       }
 118       continue;
 119     }
 120     // Move the first non-empty gap to position 0.
 121     std::swap(gap->parallel_moves()[0], gap->parallel_moves()[i]);
 122     auto left = gap->parallel_moves()[0];
 123     // Compress everything into position 0.
 124     for (++i; i <= GapInstruction::LAST_INNER_POSITION; ++i) {
 125       auto move = gap->parallel_moves()[i];
 126       if (move == nullptr) continue;
 127       CompressMoves(&temp_vector, left, move);
 128     }
 129     if (prev_gap != nullptr) {
 130       // Smash left into prev_gap, killing left.
 131       auto pred_moves = prev_gap->parallel_moves()[0];
 132       CompressMoves(&temp_vector, pred_moves, left);
 133       // Slide prev_gap down so we always know where to look for it.
 134       std::swap(prev_gap->parallel_moves()[0], gap->parallel_moves()[0]);
 135     }
 136     prev_gap = gap;
 137   }
 138   if (prev_gap != nullptr) to_finalize_.push_back(prev_gap);
 139 }
 140
 141
 142 GapInstruction* MoveOptimizer::LastGap(InstructionBlock* block) {
 143   int gap_index = block->last_instruction_index() - 1;
 144   auto instr = code()->instructions()[gap_index];
 145   return GapInstruction::cast(instr);
 146 }
 147
 148
 149 void MoveOptimizer::OptimizeMerge(InstructionBlock* block) {
 150   DCHECK(block->PredecessorCount() > 1);
 151   // Ensure that the last instruction in all incoming blocks don't contain
 152   // things that would prevent moving gap moves across them.
 153   for (auto pred_index : block->predecessors()) {
 154     auto pred = code()->InstructionBlockAt(pred_index);
 155     auto last_instr = code()->instructions()[pred->last_instruction_index()];
 156     DCHECK(!last_instr->IsGapMoves());
 157     if (last_instr->IsSourcePosition()) continue;
 158     if (last_instr->IsCall()) return;
 159     if (last_instr->TempCount() != 0) return;
 160     if (last_instr->OutputCount() != 0) return;
 161     for (size_t i = 0; i < last_instr->InputCount(); ++i) {
 162       auto op = last_instr->InputAt(i);
 163       if (!op->IsConstant() && !op->IsImmediate()) return;
 164     }
 165   }
 166   // TODO(dcarney): pass a ZonePool down for this?
 167   MoveMap move_map(local_zone());
 168   size_t correct_counts = 0;
 169   // Accumulate set of shared moves.
 170   for (auto pred_index : block->predecessors()) {
 171     auto pred = code()->InstructionBlockAt(pred_index);
 172     auto gap = LastGap(pred);
 173     if (gap->parallel_moves()[0] == nullptr ||
 174         gap->parallel_moves()[0]->move_operands()->is_empty()) {
 175       return;
 176     }
 177     auto move_ops = gap->parallel_moves()[0]->move_operands();
 178     for (auto op = move_ops->begin(); op != move_ops->end(); ++op) {
 179       if (op->IsRedundant()) continue;
 180       auto src = *op->source();
 181       auto dst = *op->destination();
 182       MoveKey key = {src, dst};
 183       auto res = move_map.insert(std::make_pair(key, 1));
 184       if (!res.second) {
 185         res.first->second++;
 186         if (res.first->second == block->PredecessorCount()) {
 187           correct_counts++;
 188         }
 189       }
 190     }
 191   }
 192   if (move_map.empty() || correct_counts != move_map.size()) return;
 193   // Find insertion point.
 194   GapInstruction* gap = nullptr;
 195   for (int i = block->first_instruction_index();
 196        i <= block->last_instruction_index(); ++i) {
 197     auto instr = code()->instructions()[i];
 198     if (instr->IsGapMoves()) {
 199       gap = GapInstruction::cast(instr);
 200       continue;
 201     }
 202     if (!GapsCanMoveOver(instr)) break;
 203   }
 204   DCHECK(gap != nullptr);
 205   bool gap_initialized = true;
 206   if (gap->parallel_moves()[0] == nullptr ||
 207       gap->parallel_moves()[0]->move_operands()->is_empty()) {
 208     to_finalize_.push_back(gap);
 209   } else {
 210     // Will compress after insertion.
 211     gap_initialized = false;
 212     std::swap(gap->parallel_moves()[0], gap->parallel_moves()[1]);
 213   }
 214   auto move = gap->GetOrCreateParallelMove(
 215       static_cast<GapInstruction::InnerPosition>(0), code_zone());
 216   // Delete relevant entries in predecessors and move everything to block.
 217   bool first_iteration = true;
 218   for (auto pred_index : block->predecessors()) {
 219     auto pred = code()->InstructionBlockAt(pred_index);
 220     auto gap = LastGap(pred);
 221     auto move_ops = gap->parallel_moves()[0]->move_operands();
 222     for (auto op = move_ops->begin(); op != move_ops->end(); ++op) {
 223       if (op->IsRedundant()) continue;
 224       MoveKey key = {*op->source(), *op->destination()};
 225       auto it = move_map.find(key);
 226       USE(it);
 227       DCHECK(it != move_map.end());
 228       if (first_iteration) {
 229         move->AddMove(op->source(), op->destination(), code_zone());
 230       }
 231       op->Eliminate();
 232     }
 233     first_iteration = false;
 234   }
 235   // Compress.
 236   if (!gap_initialized) {
 237     CompressMoves(&temp_vector_0(), gap->parallel_moves()[0],
 238                   gap->parallel_moves()[1]);
 239   }
 240 }
 241
 242
 243 // Split multiple loads of the same constant or stack slot off into the second
 244 // slot and keep remaining moves in the first slot.
 245 void MoveOptimizer::FinalizeMoves(GapInstruction* gap) {
 246   auto loads = temp_vector_0();
 247   DCHECK(loads.empty());
 248   auto new_moves = temp_vector_1();
 249   DCHECK(new_moves.empty());
 250   auto move_ops = gap->parallel_moves()[0]->move_operands();
 251   for (auto move = move_ops->begin(); move != move_ops->end(); ++move) {
 252     if (move->IsRedundant()) {
 253       move->Eliminate();
 254       continue;
 255     }
 256     if (!(move->source()->IsConstant() || move->source()->IsStackSlot() ||
 257           move->source()->IsDoubleStackSlot()))
 258       continue;
 259     // Search for existing move to this slot.
 260     MoveOperands* found = nullptr;
 261     for (auto load : loads) {
 262       if (load->source()->Equals(move->source())) {
 263         found = load;
 264         break;
 265       }
 266     }
 267     // Not found so insert.
 268     if (found == nullptr) {
 269       loads.push_back(move);
 270       // Replace source with copy for later use.
 271       auto dest = move->destination();
 272       move->set_destination(
 273           InstructionOperand::New(code_zone(), dest->kind(), dest->index()));
 274       continue;
 275     }
 276     if ((found->destination()->IsStackSlot() ||
 277          found->destination()->IsDoubleStackSlot()) &&
 278         !(move->destination()->IsStackSlot() ||
 279           move->destination()->IsDoubleStackSlot())) {
 280       // Found a better source for this load.  Smash it in place to affect other
 281       // loads that have already been split.
 282       InstructionOperand::Kind found_kind = found->destination()->kind();
 283       int found_index = found->destination()->index();
 284       auto next_dest =
 285           InstructionOperand::New(code_zone(), found_kind, found_index);
 286       auto dest = move->destination();
 287       found->destination()->ConvertTo(dest->kind(), dest->index());
 288       move->set_destination(next_dest);
 289     }
 290     // move from load destination.
 291     move->set_source(found->destination());
 292     new_moves.push_back(move);
 293   }
 294   loads.clear();
 295   if (new_moves.empty()) return;
 296   // Insert all new moves into slot 1.
 297   auto slot_1 = gap->GetOrCreateParallelMove(
 298       static_cast<GapInstruction::InnerPosition>(1), code_zone());
 299   DCHECK(slot_1->move_operands()->is_empty());
 300   slot_1->move_operands()->AddBlock(MoveOperands(nullptr, nullptr),
 301                                     static_cast<int>(new_moves.size()),
 302                                     code_zone());
 303   auto it = slot_1->move_operands()->begin();
 304   for (auto new_move : new_moves) {
 305     std::swap(*new_move, *it);
 306     ++it;
 307   }
 308   DCHECK_EQ(it, slot_1->move_operands()->end());
 309   new_moves.clear();
 310 }
 311
 312 }  // namespace compiler
 313 }  // namespace internal
 314 }  // namespace v8