move-optimizer.cc 19 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 14 15 16
struct MoveKey {
  InstructionOperand source;
  InstructionOperand destination;
};
17 18 19

struct MoveKeyCompare {
  bool operator()(const MoveKey& a, const MoveKey& b) const {
20 21
    if (a.source.EqualsCanonicalized(b.source)) {
      return a.destination.CompareCanonicalized(b.destination);
22
    }
23
    return a.source.CompareCanonicalized(b.source);
24 25 26 27
  }
};

typedef ZoneMap<MoveKey, unsigned, MoveKeyCompare> MoveMap;
28

29 30
class OperandSet {
 public:
31 32 33 34
  explicit OperandSet(ZoneVector<InstructionOperand>* buffer)
      : set_(buffer), fp_reps_(0) {
    buffer->clear();
  }
35 36

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

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

43 44 45 46 47 48 49
  bool Contains(const InstructionOperand& op) const {
    for (const InstructionOperand& elem : *set_) {
      if (elem.EqualsCanonicalized(op)) return true;
    }
    return false;
  }

50
  bool ContainsOpOrAlias(const InstructionOperand& op) const {
51
    if (Contains(op)) return true;
52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78

    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;
      }
79
      const RegisterConfiguration* config = RegisterConfiguration::Default();
80 81 82 83 84
      int base = -1;
      int aliases =
          config->GetAliases(rep, loc.register_code(), other_rep1, &base);
      DCHECK(aliases > 0 || (aliases == 0 && base == -1));
      while (aliases--) {
85 86
        if (Contains(AllocatedOperand(LocationOperand::REGISTER, other_rep1,
                                      base + aliases))) {
87
          return true;
88
        }
89 90 91 92
      }
      aliases = config->GetAliases(rep, loc.register_code(), other_rep2, &base);
      DCHECK(aliases > 0 || (aliases == 0 && base == -1));
      while (aliases--) {
93 94
        if (Contains(AllocatedOperand(LocationOperand::REGISTER, other_rep2,
                                      base + aliases))) {
95
          return true;
96
        }
97 98 99 100 101 102 103 104 105 106 107
      }
    }
    return false;
  }

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

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

111
  ZoneVector<InstructionOperand>* set_;
112 113
  int fp_reps_;
};
114

mtrofin's avatar
mtrofin committed
115
int FindFirstNonEmptySlot(const Instruction* instr) {
116 117
  int i = Instruction::FIRST_GAP_POSITION;
  for (; i <= Instruction::LAST_GAP_POSITION; i++) {
mtrofin's avatar
mtrofin committed
118
    ParallelMove* moves = instr->parallel_moves()[i];
119
    if (moves == nullptr) continue;
mtrofin's avatar
mtrofin committed
120
    for (MoveOperands* move : *moves) {
121 122
      if (!move->IsRedundant()) return i;
      move->Eliminate();
123
    }
124
    moves->clear();  // Clear this redundant move.
125 126 127 128
  }
  return i;
}

129
}  // namespace
130 131 132 133

MoveOptimizer::MoveOptimizer(Zone* local_zone, InstructionSequence* code)
    : local_zone_(local_zone),
      code_(code),
134 135 136
      local_vector_(local_zone),
      operand_buffer1(local_zone),
      operand_buffer2(local_zone) {}
137 138

void MoveOptimizer::Run() {
139 140 141
  for (Instruction* instruction : code()->instructions()) {
    CompressGaps(instruction);
  }
142
  for (InstructionBlock* block : code()->instruction_blocks()) {
143 144
    CompressBlock(block);
  }
145
  for (InstructionBlock* block : code()->instruction_blocks()) {
146
    if (block->PredecessorCount() <= 1) continue;
147 148
    if (!block->IsDeferred()) {
      bool has_only_deferred = true;
mtrofin's avatar
mtrofin committed
149
      for (RpoNumber& pred_id : block->predecessors()) {
150 151 152 153
        if (!code()->InstructionBlockAt(pred_id)->IsDeferred()) {
          has_only_deferred = false;
          break;
        }
154
      }
155 156 157 158 159
      // 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;
160
    }
161 162
    OptimizeMerge(block);
  }
163
  for (Instruction* gap : code()->instructions()) {
164 165 166 167
    FinalizeMoves(gap);
  }
}

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

173 174 175
  DCHECK(instruction->parallel_moves()[1] == nullptr ||
         instruction->parallel_moves()[1]->empty());

176 177
  OperandSet outputs(&operand_buffer1);
  OperandSet inputs(&operand_buffer2);
178 179 180 181

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

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

  // Elide moves made redundant by the instruction.
  for (MoveOperands* move : *moves) {
195 196
    if (outputs.ContainsOpOrAlias(move->destination()) &&
        !inputs.ContainsOpOrAlias(move->destination())) {
197 198 199 200 201 202
      move->Eliminate();
    }
  }

  // The ret instruction makes any assignment before it unnecessary, except for
  // the one for its input.
203
  if (instruction->IsRet() || instruction->IsTailCall()) {
204
    for (MoveOperands* move : *moves) {
205
      if (!inputs.ContainsOpOrAlias(move->destination())) {
206 207 208 209 210 211 212 213 214 215 216 217
        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;

218 219
  OperandSet dst_cant_be(&operand_buffer1);
  OperandSet src_cant_be(&operand_buffer2);
220 221 222 223

  // 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) {
224
    dst_cant_be.InsertOp(*from->InputAt(i));
225 226 227 228 229 230 231 232
  }
  // 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) {
233
    src_cant_be.InsertOp(*from->OutputAt(i));
234 235
  }
  for (size_t i = 0; i < from->TempCount(); ++i) {
236
    src_cant_be.InsertOp(*from->TempAt(i));
237 238 239 240 241 242 243
  }
  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.
244
    src_cant_be.InsertOp(move->destination());
245 246 247 248 249 250 251
  }

  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;
252
    if (!dst_cant_be.ContainsOpOrAlias(move->destination())) {
253 254 255 256 257 258 259 260 261 262 263 264 265 266
      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;
267 268
      if (src_cant_be.ContainsOpOrAlias(src)) {
        src_cant_be.InsertOp(current->destination);
269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296
        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) {
297 298
  if (right == nullptr) return;

299 300 301
  MoveOpVector& eliminated = local_vector();
  DCHECK(eliminated.empty());

302
  if (!left->empty()) {
303 304
    // Modify the right moves in place and collect moves that will be killed by
    // merging the two gaps.
mtrofin's avatar
mtrofin committed
305
    for (MoveOperands* move : *right) {
306
      if (move->IsRedundant()) continue;
307
      left->PrepareInsertAfter(move, &eliminated);
308
    }
309
    // Eliminate dead moves.
310
    for (MoveOperands* to_eliminate : eliminated) {
311 312
      to_eliminate->Eliminate();
    }
313
    eliminated.clear();
314 315
  }
  // Add all possibly modified moves from right side.
mtrofin's avatar
mtrofin committed
316
  for (MoveOperands* move : *right) {
317 318
    if (move->IsRedundant()) continue;
    left->push_back(move);
319 320
  }
  // Nuke right.
321
  right->clear();
322
  DCHECK(eliminated.empty());
323 324
}

325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350
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())));
}
351

352
void MoveOptimizer::CompressBlock(InstructionBlock* block) {
353 354
  int first_instr_index = block->first_instruction_index();
  int last_instr_index = block->last_instruction_index();
355

356 357 358 359 360 361 362 363 364 365 366 367
  // 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;
368
  }
369 370 371
}


mtrofin's avatar
mtrofin committed
372 373
const Instruction* MoveOptimizer::LastInstruction(
    const InstructionBlock* block) const {
374
  return code()->instructions()[block->last_instruction_index()];
375 376 377 378
}


void MoveOptimizer::OptimizeMerge(InstructionBlock* block) {
379
  DCHECK_LT(1, block->PredecessorCount());
380 381
  // Ensure that the last instruction in all incoming blocks don't contain
  // things that would prevent moving gap moves across them.
mtrofin's avatar
mtrofin committed
382 383
  for (RpoNumber& pred_index : block->predecessors()) {
    const InstructionBlock* pred = code()->InstructionBlockAt(pred_index);
384 385 386 387 388 389

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

mtrofin's avatar
mtrofin committed
390 391
    const Instruction* last_instr =
        code()->instructions()[pred->last_instruction_index()];
392 393 394 395
    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) {
mtrofin's avatar
mtrofin committed
396
      const InstructionOperand* op = last_instr->InputAt(i);
397 398 399
      if (!op->IsConstant() && !op->IsImmediate()) return;
    }
  }
400
  // TODO(dcarney): pass a ZoneStats down for this?
401 402 403
  MoveMap move_map(local_zone());
  size_t correct_counts = 0;
  // Accumulate set of shared moves.
mtrofin's avatar
mtrofin committed
404 405 406
  for (RpoNumber& pred_index : block->predecessors()) {
    const InstructionBlock* pred = code()->InstructionBlockAt(pred_index);
    const Instruction* instr = LastInstruction(pred);
407
    if (instr->parallel_moves()[0] == nullptr ||
408
        instr->parallel_moves()[0]->empty()) {
409 410
      return;
    }
mtrofin's avatar
mtrofin committed
411
    for (const MoveOperands* move : *instr->parallel_moves()[0]) {
412
      if (move->IsRedundant()) continue;
mtrofin's avatar
mtrofin committed
413 414
      InstructionOperand src = move->source();
      InstructionOperand dst = move->destination();
415 416 417 418 419 420 421 422 423 424
      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++;
        }
      }
    }
  }
425 426
  if (move_map.empty() || correct_counts == 0) return;

427
  // Find insertion point.
428
  Instruction* instr = code()->instructions()[block->first_instruction_index()];
429 430 431 432

  if (correct_counts != move_map.size()) {
    // Moves that are unique to each predecessor won't be pushed to the common
    // successor.
433
    OperandSet conflicting_srcs(&operand_buffer1);
434 435 436 437
    for (auto iter = move_map.begin(), end = move_map.end(); iter != end;) {
      auto current = iter;
      ++iter;
      if (current->second != block->PredecessorCount()) {
438
        InstructionOperand dest = current->first.destination;
439 440 441 442
        // 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.
443
        conflicting_srcs.InsertOp(dest);
444 445 446 447 448 449 450 451 452 453 454 455 456
        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);
457 458
        if (conflicting_srcs.ContainsOpOrAlias(current->first.source)) {
          conflicting_srcs.InsertOp(current->first.destination);
459 460 461 462 463 464 465 466 467
          move_map.erase(current);
          changed = true;
        }
      }
    } while (changed);
  }

  if (move_map.empty()) return;

468
  DCHECK_NOT_NULL(instr);
469
  bool gap_initialized = true;
470 471
  if (instr->parallel_moves()[0] != nullptr &&
      !instr->parallel_moves()[0]->empty()) {
472 473
    // Will compress after insertion.
    gap_initialized = false;
474
    std::swap(instr->parallel_moves()[0], instr->parallel_moves()[1]);
475
  }
mtrofin's avatar
mtrofin committed
476
  ParallelMove* moves = instr->GetOrCreateParallelMove(
477
      static_cast<Instruction::GapPosition>(0), code_zone());
478 479
  // Delete relevant entries in predecessors and move everything to block.
  bool first_iteration = true;
mtrofin's avatar
mtrofin committed
480 481 482
  for (RpoNumber& pred_index : block->predecessors()) {
    const InstructionBlock* pred = code()->InstructionBlockAt(pred_index);
    for (MoveOperands* move : *LastInstruction(pred)->parallel_moves()[0]) {
483 484
      if (move->IsRedundant()) continue;
      MoveKey key = {move->source(), move->destination()};
485
      auto it = move_map.find(key);
486 487 488 489 490
      if (it != move_map.end()) {
        if (first_iteration) {
          moves->AddMove(move->source(), move->destination());
        }
        move->Eliminate();
491 492 493 494 495 496
      }
    }
    first_iteration = false;
  }
  // Compress.
  if (!gap_initialized) {
497
    CompressMoves(instr->parallel_moves()[0], instr->parallel_moves()[1]);
498
  }
499
  CompressBlock(block);
500 501 502
}


503 504 505
namespace {

bool IsSlot(const InstructionOperand& op) {
506
  return op.IsStackSlot() || op.IsFPStackSlot();
507 508 509 510
}


bool LoadCompare(const MoveOperands* a, const MoveOperands* b) {
511 512
  if (!a->source().EqualsCanonicalized(b->source())) {
    return a->source().CompareCanonicalized(b->source());
513
  }
514 515
  if (IsSlot(a->destination()) && !IsSlot(b->destination())) return false;
  if (!IsSlot(a->destination()) && IsSlot(b->destination())) return true;
516
  return a->destination().CompareCanonicalized(b->destination());
517 518 519 520 521
}

}  // namespace


522 523
// Split multiple loads of the same constant or stack slot off into the second
// slot and keep remaining moves in the first slot.
524
void MoveOptimizer::FinalizeMoves(Instruction* instr) {
525
  MoveOpVector& loads = local_vector();
526
  DCHECK(loads.empty());
527

528 529
  ParallelMove* parallel_moves = instr->parallel_moves()[0];
  if (parallel_moves == nullptr) return;
530
  // Find all the loads.
531
  for (MoveOperands* move : *parallel_moves) {
532 533
    if (move->IsRedundant()) continue;
    if (move->source().IsConstant() || IsSlot(move->source())) {
534
      loads.push_back(move);
535
    }
536 537 538 539 540 541
  }
  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;
mtrofin's avatar
mtrofin committed
542
  for (MoveOperands* load : loads) {
543
    // New group.
544
    if (group_begin == nullptr ||
545
        !load->source().EqualsCanonicalized(group_begin->source())) {
546 547
      group_begin = load;
      continue;
548
    }
549 550 551
    // Nothing to be gained from splitting here.
    if (IsSlot(group_begin->destination())) continue;
    // Insert new move into slot 1.
mtrofin's avatar
mtrofin committed
552
    ParallelMove* slot_1 = instr->GetOrCreateParallelMove(
553 554 555
        static_cast<Instruction::GapPosition>(1), code_zone());
    slot_1->AddMove(group_begin->destination(), load->destination());
    load->Eliminate();
556
  }
557
  loads.clear();
558 559 560 561 562
}

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