move-optimizer.cc 10.8 KB
Newer Older
1 2 3 4 5 6 7 8 9 10
// 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 {

11
namespace {
12

13
typedef std::pair<InstructionOperand, InstructionOperand> MoveKey;
14 15 16

struct MoveKeyCompare {
  bool operator()(const MoveKey& a, const MoveKey& b) const {
17 18
    if (a.first.EqualsCanonicalized(b.first)) {
      return a.second.CompareCanonicalized(b.second);
19
    }
20
    return a.first.CompareCanonicalized(b.first);
21 22 23
  }
};

24 25 26 27 28 29 30
struct OperandCompare {
  bool operator()(const InstructionOperand& a,
                  const InstructionOperand& b) const {
    return a.CompareCanonicalized(b);
  }
};

31 32
typedef ZoneMap<MoveKey, unsigned, MoveKeyCompare> MoveMap;
typedef ZoneSet<InstructionOperand, CompareOperandModuloType> OperandSet;
33 34


35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
bool GapsCanMoveOver(Instruction* instr, Zone* zone) {
  if (instr->IsNop()) return true;
  if (instr->ClobbersTemps() || instr->ClobbersRegisters() ||
      instr->ClobbersDoubleRegisters()) {
    return false;
  }
  if (instr->arch_opcode() != ArchOpcode::kArchNop) return false;

  ZoneSet<InstructionOperand, OperandCompare> operands(zone);
  for (size_t i = 0; i < instr->InputCount(); ++i) {
    operands.insert(*instr->InputAt(i));
  }
  for (size_t i = 0; i < instr->OutputCount(); ++i) {
    operands.insert(*instr->OutputAt(i));
  }
  for (size_t i = 0; i < instr->TempCount(); ++i) {
    operands.insert(*instr->TempAt(i));
  }
  for (int i = Instruction::GapPosition::FIRST_GAP_POSITION;
       i <= Instruction::GapPosition::LAST_GAP_POSITION; ++i) {
    ParallelMove* moves = instr->parallel_moves()[i];
    if (moves == nullptr) continue;
    for (MoveOperands* move : *moves) {
      if (operands.count(move->source()) > 0 ||
          operands.count(move->destination()) > 0) {
        return false;
      }
    }
  }
  return true;
}
66 67


68 69 70
int FindFirstNonEmptySlot(Instruction* instr) {
  int i = Instruction::FIRST_GAP_POSITION;
  for (; i <= Instruction::LAST_GAP_POSITION; i++) {
71 72 73 74 75
    auto moves = instr->parallel_moves()[i];
    if (moves == nullptr) continue;
    for (auto move : *moves) {
      if (!move->IsRedundant()) return i;
      move->Eliminate();
76
    }
77
    moves->clear();  // Clear this redundant move.
78 79 80 81
  }
  return i;
}

82
}  // namespace
83 84 85 86 87 88 89 90 91 92 93 94 95 96


MoveOptimizer::MoveOptimizer(Zone* local_zone, InstructionSequence* code)
    : local_zone_(local_zone),
      code_(code),
      to_finalize_(local_zone),
      temp_vector_0_(local_zone),
      temp_vector_1_(local_zone) {}


void MoveOptimizer::Run() {
  for (auto* block : code()->instruction_blocks()) {
    CompressBlock(block);
  }
97 98
  for (auto block : code()->instruction_blocks()) {
    if (block->PredecessorCount() <= 1) continue;
99 100 101 102 103 104 105 106 107 108 109
    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.
    if (has_only_deferred) continue;
110 111
    OptimizeMerge(block);
  }
112 113 114 115 116 117
  for (auto gap : to_finalize_) {
    FinalizeMoves(gap);
  }
}


118 119 120
void MoveOptimizer::CompressMoves(MoveOpVector* eliminated, ParallelMove* left,
                                  ParallelMove* right) {
  DCHECK(eliminated->empty());
121
  if (!left->empty()) {
122 123
    // Modify the right moves in place and collect moves that will be killed by
    // merging the two gaps.
124 125 126
    for (auto move : *right) {
      if (move->IsRedundant()) continue;
      auto to_eliminate = left->PrepareInsertAfter(move);
127
      if (to_eliminate != nullptr) eliminated->push_back(to_eliminate);
128
    }
129
    // Eliminate dead moves.
130 131 132 133
    for (auto to_eliminate : *eliminated) {
      to_eliminate->Eliminate();
    }
    eliminated->clear();
134 135
  }
  // Add all possibly modified moves from right side.
136 137 138
  for (auto move : *right) {
    if (move->IsRedundant()) continue;
    left->push_back(move);
139 140
  }
  // Nuke right.
141
  right->clear();
142 143 144
}


145 146 147 148 149
// Smash all consecutive moves into the left most move slot and accumulate them
// as much as possible across instructions.
void MoveOptimizer::CompressBlock(InstructionBlock* block) {
  auto temp_vector = temp_vector_0();
  DCHECK(temp_vector.empty());
150
  Instruction* prev_instr = nullptr;
151 152
  for (int index = block->code_start(); index < block->code_end(); ++index) {
    auto instr = code()->instructions()[index];
153 154 155 156 157 158 159 160 161 162 163 164 165 166 167
    int i = FindFirstNonEmptySlot(instr);
    if (i <= Instruction::LAST_GAP_POSITION) {
      // Move the first non-empty gap to position 0.
      std::swap(instr->parallel_moves()[0], instr->parallel_moves()[i]);
      auto left = instr->parallel_moves()[0];
      // Compress everything into position 0.
      for (++i; i <= Instruction::LAST_GAP_POSITION; ++i) {
        auto move = instr->parallel_moves()[i];
        if (move == nullptr) continue;
        CompressMoves(&temp_vector, left, move);
      }
      if (prev_instr != nullptr) {
        // Smash left into prev_instr, killing left.
        auto pred_moves = prev_instr->parallel_moves()[0];
        CompressMoves(&temp_vector, pred_moves, left);
168 169
      }
    }
170 171 172
    if (prev_instr != nullptr) {
      // Slide prev_instr down so we always know where to look for it.
      std::swap(prev_instr->parallel_moves()[0], instr->parallel_moves()[0]);
173
    }
174
    prev_instr = instr->parallel_moves()[0] == nullptr ? nullptr : instr;
175
    if (GapsCanMoveOver(instr, local_zone())) continue;
176 177 178
    if (prev_instr != nullptr) {
      to_finalize_.push_back(prev_instr);
      prev_instr = nullptr;
179 180
    }
  }
181 182 183
  if (prev_instr != nullptr) {
    to_finalize_.push_back(prev_instr);
  }
184 185 186
}


187 188
Instruction* MoveOptimizer::LastInstruction(InstructionBlock* block) {
  return code()->instructions()[block->last_instruction_index()];
189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212
}


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 (auto pred_index : block->predecessors()) {
    auto pred = code()->InstructionBlockAt(pred_index);
    auto 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) {
      auto 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 (auto pred_index : block->predecessors()) {
    auto pred = code()->InstructionBlockAt(pred_index);
213 214
    auto instr = LastInstruction(pred);
    if (instr->parallel_moves()[0] == nullptr ||
215
        instr->parallel_moves()[0]->empty()) {
216 217
      return;
    }
218 219 220 221
    for (auto move : *instr->parallel_moves()[0]) {
      if (move->IsRedundant()) continue;
      auto src = move->source();
      auto dst = move->destination();
222 223 224 225 226 227 228 229 230 231 232 233
      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 != move_map.size()) return;
  // Find insertion point.
234
  Instruction* instr = nullptr;
235 236
  for (int i = block->first_instruction_index();
       i <= block->last_instruction_index(); ++i) {
237
    instr = code()->instructions()[i];
238 239
    if (!GapsCanMoveOver(instr, local_zone()) || !instr->AreMovesRedundant())
      break;
240
  }
241
  DCHECK(instr != nullptr);
242
  bool gap_initialized = true;
243
  if (instr->parallel_moves()[0] == nullptr ||
244
      instr->parallel_moves()[0]->empty()) {
245
    to_finalize_.push_back(instr);
246 247 248
  } else {
    // Will compress after insertion.
    gap_initialized = false;
249
    std::swap(instr->parallel_moves()[0], instr->parallel_moves()[1]);
250
  }
251
  auto moves = instr->GetOrCreateParallelMove(
252
      static_cast<Instruction::GapPosition>(0), code_zone());
253 254 255 256
  // Delete relevant entries in predecessors and move everything to block.
  bool first_iteration = true;
  for (auto pred_index : block->predecessors()) {
    auto pred = code()->InstructionBlockAt(pred_index);
257 258 259
    for (auto move : *LastInstruction(pred)->parallel_moves()[0]) {
      if (move->IsRedundant()) continue;
      MoveKey key = {move->source(), move->destination()};
260 261 262 263
      auto it = move_map.find(key);
      USE(it);
      DCHECK(it != move_map.end());
      if (first_iteration) {
264
        moves->AddMove(move->source(), move->destination());
265
      }
266
      move->Eliminate();
267 268 269 270 271
    }
    first_iteration = false;
  }
  // Compress.
  if (!gap_initialized) {
272 273
    CompressMoves(&temp_vector_0(), instr->parallel_moves()[0],
                  instr->parallel_moves()[1]);
274 275 276 277
  }
}


278 279 280 281 282 283 284 285
namespace {

bool IsSlot(const InstructionOperand& op) {
  return op.IsStackSlot() || op.IsDoubleStackSlot();
}


bool LoadCompare(const MoveOperands* a, const MoveOperands* b) {
286 287
  if (!a->source().EqualsCanonicalized(b->source())) {
    return a->source().CompareCanonicalized(b->source());
288
  }
289 290
  if (IsSlot(a->destination()) && !IsSlot(b->destination())) return false;
  if (!IsSlot(a->destination()) && IsSlot(b->destination())) return true;
291
  return a->destination().CompareCanonicalized(b->destination());
292 293 294 295 296
}

}  // namespace


297 298
// Split multiple loads of the same constant or stack slot off into the second
// slot and keep remaining moves in the first slot.
299
void MoveOptimizer::FinalizeMoves(Instruction* instr) {
300 301
  auto loads = temp_vector_0();
  DCHECK(loads.empty());
302 303 304 305
  // Find all the loads.
  for (auto move : *instr->parallel_moves()[0]) {
    if (move->IsRedundant()) continue;
    if (move->source().IsConstant() || IsSlot(move->source())) {
306
      loads.push_back(move);
307
    }
308 309 310 311 312 313 314 315
  }
  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 (auto load : loads) {
    // New group.
316
    if (group_begin == nullptr ||
317
        !load->source().EqualsCanonicalized(group_begin->source())) {
318 319
      group_begin = load;
      continue;
320
    }
321 322 323 324 325 326 327
    // Nothing to be gained from splitting here.
    if (IsSlot(group_begin->destination())) continue;
    // Insert new move into slot 1.
    auto slot_1 = instr->GetOrCreateParallelMove(
        static_cast<Instruction::GapPosition>(1), code_zone());
    slot_1->AddMove(group_begin->destination(), load->destination());
    load->Eliminate();
328
  }
329
  loads.clear();
330 331 332 333 334
}

}  // namespace compiler
}  // namespace internal
}  // namespace v8