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
7namespace v8 {
8namespace internal {
9namespace compiler {
10
11namespace {
12
13struct MoveKey {
14  InstructionOperand source;
15  InstructionOperand destination;
16};
17
18struct MoveKeyCompare {
19  bool operator()(const MoveKey& a, const MoveKey& b) const {
20    if (a.source.EqualsCanonicalized(b.source)) {
21      return a.destination.CompareCanonicalized(b.destination);
22    }
23    return a.source.CompareCanonicalized(b.source);
24  }
25};
26
27typedef ZoneMap<MoveKey, unsigned, MoveKeyCompare> MoveMap;
28
29class OperandSet {
30 public:
31  explicit OperandSet(ZoneVector<InstructionOperand>* buffer)
32      : set_(buffer), fp_reps_(0) {
33    buffer->clear();
34  }
35
36  void InsertOp(const InstructionOperand& op) {
37    set_->push_back(op);
38
39    if (!kSimpleFPAliasing && op.IsFPRegister())
40      fp_reps_ |= RepBit(LocationOperand::cast(op).representation());
41  }
42
43  bool Contains(const InstructionOperand& op) const {
44    for (const InstructionOperand& elem : *set_) {
45      if (elem.EqualsCanonicalized(op)) return true;
46    }
47    return false;
48  }
49
50  bool ContainsOpOrAlias(const InstructionOperand& op) const {
51    if (Contains(op)) return true;
52
53    if (!kSimpleFPAliasing && op.IsFPRegister()) {
54      // Platforms where FP registers have complex aliasing need extra checks.
55      const LocationOperand& loc = LocationOperand::cast(op);
56      MachineRepresentation rep = loc.representation();
57      // If haven't encountered mixed rep FP registers, skip the extra checks.
58      if (!HasMixedFPReps(fp_reps_ | RepBit(rep))) return false;
59
60      // Check register against aliasing registers of other FP representations.
61      MachineRepresentation other_rep1, other_rep2;
62      switch (rep) {
63        case MachineRepresentation::kFloat32:
64          other_rep1 = MachineRepresentation::kFloat64;
65          other_rep2 = MachineRepresentation::kSimd128;
66          break;
67        case MachineRepresentation::kFloat64:
68          other_rep1 = MachineRepresentation::kFloat32;
69          other_rep2 = MachineRepresentation::kSimd128;
70          break;
71        case MachineRepresentation::kSimd128:
72          other_rep1 = MachineRepresentation::kFloat32;
73          other_rep2 = MachineRepresentation::kFloat64;
74          break;
75        default:
76          UNREACHABLE();
77          break;
78      }
79      const RegisterConfiguration* config = RegisterConfiguration::Turbofan();
80      int base = -1;
81      int aliases =
82          config->GetAliases(rep, loc.register_code(), other_rep1, &base);
83      DCHECK(aliases > 0 || (aliases == 0 && base == -1));
84      while (aliases--) {
85        if (Contains(AllocatedOperand(LocationOperand::REGISTER, other_rep1,
86                                      base + aliases))) {
87          return true;
88        }
89      }
90      aliases = config->GetAliases(rep, loc.register_code(), other_rep2, &base);
91      DCHECK(aliases > 0 || (aliases == 0 && base == -1));
92      while (aliases--) {
93        if (Contains(AllocatedOperand(LocationOperand::REGISTER, other_rep2,
94                                      base + aliases))) {
95          return true;
96        }
97      }
98    }
99    return false;
100  }
101
102 private:
103  static int RepBit(MachineRepresentation rep) {
104    return 1 << static_cast<int>(rep);
105  }
106
107  static bool HasMixedFPReps(int reps) {
108    return reps && !base::bits::IsPowerOfTwo32(reps);
109  }
110
111  ZoneVector<InstructionOperand>* set_;
112  int fp_reps_;
113};
114
115int FindFirstNonEmptySlot(const Instruction* instr) {
116  int i = Instruction::FIRST_GAP_POSITION;
117  for (; i <= Instruction::LAST_GAP_POSITION; i++) {
118    ParallelMove* moves = instr->parallel_moves()[i];
119    if (moves == nullptr) continue;
120    for (MoveOperands* move : *moves) {
121      if (!move->IsRedundant()) return i;
122      move->Eliminate();
123    }
124    moves->clear();  // Clear this redundant move.
125  }
126  return i;
127}
128
129}  // namespace
130
131MoveOptimizer::MoveOptimizer(Zone* local_zone, InstructionSequence* code)
132    : local_zone_(local_zone),
133      code_(code),
134      local_vector_(local_zone),
135      operand_buffer1(local_zone),
136      operand_buffer2(local_zone) {}
137
138void MoveOptimizer::Run() {
139  for (Instruction* instruction : code()->instructions()) {
140    CompressGaps(instruction);
141  }
142  for (InstructionBlock* block : code()->instruction_blocks()) {
143    CompressBlock(block);
144  }
145  for (InstructionBlock* block : code()->instruction_blocks()) {
146    if (block->PredecessorCount() <= 1) continue;
147    if (!block->IsDeferred()) {
148      bool has_only_deferred = true;
149      for (RpoNumber& pred_id : block->predecessors()) {
150        if (!code()->InstructionBlockAt(pred_id)->IsDeferred()) {
151          has_only_deferred = false;
152          break;
153        }
154      }
155      // This would pull down common moves. If the moves occur in deferred
156      // blocks, and the closest common successor is not deferred, we lose the
157      // optimization of just spilling/filling in deferred blocks, when the
158      // current block is not deferred.
159      if (has_only_deferred) continue;
160    }
161    OptimizeMerge(block);
162  }
163  for (Instruction* gap : code()->instructions()) {
164    FinalizeMoves(gap);
165  }
166}
167
168void MoveOptimizer::RemoveClobberedDestinations(Instruction* instruction) {
169  if (instruction->IsCall()) return;
170  ParallelMove* moves = instruction->parallel_moves()[0];
171  if (moves == nullptr) return;
172
173  DCHECK(instruction->parallel_moves()[1] == nullptr ||
174         instruction->parallel_moves()[1]->empty());
175
176  OperandSet outputs(&operand_buffer1);
177  OperandSet inputs(&operand_buffer2);
178
179  // Outputs and temps are treated together as potentially clobbering a
180  // destination operand.
181  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  // Input operands block elisions.
189  for (size_t i = 0; i < instruction->InputCount(); ++i) {
190    inputs.InsertOp(*instruction->InputAt(i));
191  }
192
193  // Elide moves made redundant by the instruction.
194  for (MoveOperands* move : *moves) {
195    if (outputs.ContainsOpOrAlias(move->destination()) &&
196        !inputs.ContainsOpOrAlias(move->destination())) {
197      move->Eliminate();
198    }
199  }
200
201  // The ret instruction makes any assignment before it unnecessary, except for
202  // the one for its input.
203  if (instruction->IsRet() || instruction->IsTailCall()) {
204    for (MoveOperands* move : *moves) {
205      if (!inputs.ContainsOpOrAlias(move->destination())) {
206        move->Eliminate();
207      }
208    }
209  }
210}
211
212void MoveOptimizer::MigrateMoves(Instruction* to, Instruction* from) {
213  if (from->IsCall()) return;
214
215  ParallelMove* from_moves = from->parallel_moves()[0];
216  if (from_moves == nullptr || from_moves->empty()) return;
217
218  OperandSet dst_cant_be(&operand_buffer1);
219  OperandSet src_cant_be(&operand_buffer2);
220
221  // If an operand is an input to the instruction, we cannot move assignments
222  // where it appears on the LHS.
223  for (size_t i = 0; i < from->InputCount(); ++i) {
224    dst_cant_be.InsertOp(*from->InputAt(i));
225  }
226  // If an operand is output to the instruction, we cannot move assignments
227  // where it appears on the RHS, because we would lose its value before the
228  // instruction.
229  // Same for temp operands.
230  // The output can't appear on the LHS because we performed
231  // RemoveClobberedDestinations for the "from" instruction.
232  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  for (MoveOperands* move : *from_moves) {
239    if (move->IsRedundant()) continue;
240    // Assume dest has a value "V". If we have a "dest = y" move, then we can't
241    // move "z = dest", because z would become y rather than "V".
242    // We assume CompressMoves has happened before this, which means we don't
243    // have more than one assignment to dest.
244    src_cant_be.InsertOp(move->destination());
245  }
246
247  ZoneSet<MoveKey, MoveKeyCompare> move_candidates(local_zone());
248  // We start with all the moves that don't have conflicting source or
249  // destination operands are eligible for being moved down.
250  for (MoveOperands* move : *from_moves) {
251    if (move->IsRedundant()) continue;
252    if (!dst_cant_be.ContainsOpOrAlias(move->destination())) {
253      MoveKey key = {move->source(), move->destination()};
254      move_candidates.insert(key);
255    }
256  }
257  if (move_candidates.empty()) return;
258
259  // Stabilize the candidate set.
260  bool changed = false;
261  do {
262    changed = false;
263    for (auto iter = move_candidates.begin(); iter != move_candidates.end();) {
264      auto current = iter;
265      ++iter;
266      InstructionOperand src = current->source;
267      if (src_cant_be.ContainsOpOrAlias(src)) {
268        src_cant_be.InsertOp(current->destination);
269        move_candidates.erase(current);
270        changed = true;
271      }
272    }
273  } while (changed);
274
275  ParallelMove to_move(local_zone());
276  for (MoveOperands* move : *from_moves) {
277    if (move->IsRedundant()) continue;
278    MoveKey key = {move->source(), move->destination()};
279    if (move_candidates.find(key) != move_candidates.end()) {
280      to_move.AddMove(move->source(), move->destination(), code_zone());
281      move->Eliminate();
282    }
283  }
284  if (to_move.empty()) return;
285
286  ParallelMove* dest =
287      to->GetOrCreateParallelMove(Instruction::GapPosition::START, code_zone());
288
289  CompressMoves(&to_move, dest);
290  DCHECK(dest->empty());
291  for (MoveOperands* m : to_move) {
292    dest->push_back(m);
293  }
294}
295
296void MoveOptimizer::CompressMoves(ParallelMove* left, MoveOpVector* right) {
297  if (right == nullptr) return;
298
299  MoveOpVector& eliminated = local_vector();
300  DCHECK(eliminated.empty());
301
302  if (!left->empty()) {
303    // Modify the right moves in place and collect moves that will be killed by
304    // merging the two gaps.
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      to_eliminate->Eliminate();
312    }
313    eliminated.clear();
314  }
315  // Add all possibly modified moves from right side.
316  for (MoveOperands* move : *right) {
317    if (move->IsRedundant()) continue;
318    left->push_back(move);
319  }
320  // Nuke right.
321  right->clear();
322  DCHECK(eliminated.empty());
323}
324
325void MoveOptimizer::CompressGaps(Instruction* instruction) {
326  int i = FindFirstNonEmptySlot(instruction);
327  bool has_moves = i <= Instruction::LAST_GAP_POSITION;
328  USE(has_moves);
329
330  if (i == Instruction::LAST_GAP_POSITION) {
331    std::swap(instruction->parallel_moves()[Instruction::FIRST_GAP_POSITION],
332              instruction->parallel_moves()[Instruction::LAST_GAP_POSITION]);
333  } else if (i == Instruction::FIRST_GAP_POSITION) {
334    CompressMoves(
335        instruction->parallel_moves()[Instruction::FIRST_GAP_POSITION],
336        instruction->parallel_moves()[Instruction::LAST_GAP_POSITION]);
337  }
338  // We either have no moves, or, after swapping or compressing, we have
339  // all the moves in the first gap position, and none in the second/end gap
340  // position.
341  ParallelMove* first =
342      instruction->parallel_moves()[Instruction::FIRST_GAP_POSITION];
343  ParallelMove* last =
344      instruction->parallel_moves()[Instruction::LAST_GAP_POSITION];
345  USE(first);
346  USE(last);
347
348  DCHECK(!has_moves ||
349         (first != nullptr && (last == nullptr || last->empty())));
350}
351
352void MoveOptimizer::CompressBlock(InstructionBlock* block) {
353  int first_instr_index = block->first_instruction_index();
354  int last_instr_index = block->last_instruction_index();
355
356  // Start by removing gap assignments where the output of the subsequent
357  // instruction appears on LHS, as long as they are not needed by its input.
358  Instruction* prev_instr = code()->instructions()[first_instr_index];
359  RemoveClobberedDestinations(prev_instr);
360
361  for (int index = first_instr_index + 1; index <= last_instr_index; ++index) {
362    Instruction* instr = code()->instructions()[index];
363    // Migrate to the gap of prev_instr eligible moves from instr.
364    MigrateMoves(instr, prev_instr);
365    // Remove gap assignments clobbered by instr's output.
366    RemoveClobberedDestinations(instr);
367    prev_instr = instr;
368  }
369}
370
371
372const Instruction* MoveOptimizer::LastInstruction(
373    const InstructionBlock* block) const {
374  return code()->instructions()[block->last_instruction_index()];
375}
376
377
378void MoveOptimizer::OptimizeMerge(InstructionBlock* block) {
379  DCHECK(block->PredecessorCount() > 1);
380  // Ensure that the last instruction in all incoming blocks don't contain
381  // things that would prevent moving gap moves across them.
382  for (RpoNumber& pred_index : block->predecessors()) {
383    const InstructionBlock* pred = code()->InstructionBlockAt(pred_index);
384
385    // If the predecessor has more than one successor, we shouldn't attempt to
386    // move down to this block (one of the successors) any of the gap moves,
387    // because their effect may be necessary to the other successors.
388    if (pred->SuccessorCount() > 1) return;
389
390    const Instruction* last_instr =
391        code()->instructions()[pred->last_instruction_index()];
392    if (last_instr->IsCall()) return;
393    if (last_instr->TempCount() != 0) return;
394    if (last_instr->OutputCount() != 0) return;
395    for (size_t i = 0; i < last_instr->InputCount(); ++i) {
396      const InstructionOperand* op = last_instr->InputAt(i);
397      if (!op->IsConstant() && !op->IsImmediate()) return;
398    }
399  }
400  // TODO(dcarney): pass a ZoneStats down for this?
401  MoveMap move_map(local_zone());
402  size_t correct_counts = 0;
403  // Accumulate set of shared moves.
404  for (RpoNumber& pred_index : block->predecessors()) {
405    const InstructionBlock* pred = code()->InstructionBlockAt(pred_index);
406    const Instruction* instr = LastInstruction(pred);
407    if (instr->parallel_moves()[0] == nullptr ||
408        instr->parallel_moves()[0]->empty()) {
409      return;
410    }
411    for (const MoveOperands* move : *instr->parallel_moves()[0]) {
412      if (move->IsRedundant()) continue;
413      InstructionOperand src = move->source();
414      InstructionOperand dst = move->destination();
415      MoveKey key = {src, dst};
416      auto res = move_map.insert(std::make_pair(key, 1));
417      if (!res.second) {
418        res.first->second++;
419        if (res.first->second == block->PredecessorCount()) {
420          correct_counts++;
421        }
422      }
423    }
424  }
425  if (move_map.empty() || correct_counts == 0) return;
426
427  // Find insertion point.
428  Instruction* instr = code()->instructions()[block->first_instruction_index()];
429
430  if (correct_counts != move_map.size()) {
431    // Moves that are unique to each predecessor won't be pushed to the common
432    // successor.
433    OperandSet conflicting_srcs(&operand_buffer1);
434    for (auto iter = move_map.begin(), end = move_map.end(); iter != end;) {
435      auto current = iter;
436      ++iter;
437      if (current->second != block->PredecessorCount()) {
438        InstructionOperand dest = current->first.destination;
439        // Not all the moves in all the gaps are the same. Maybe some are. If
440        // there are such moves, we could move them, but the destination of the
441        // moves staying behind can't appear as a source of a common move,
442        // because the move staying behind will clobber this destination.
443        conflicting_srcs.InsertOp(dest);
444        move_map.erase(current);
445      }
446    }
447
448    bool changed = false;
449    do {
450      // If a common move can't be pushed to the common successor, then its
451      // destination also can't appear as source to any move being pushed.
452      changed = false;
453      for (auto iter = move_map.begin(), end = move_map.end(); iter != end;) {
454        auto current = iter;
455        ++iter;
456        DCHECK_EQ(block->PredecessorCount(), current->second);
457        if (conflicting_srcs.ContainsOpOrAlias(current->first.source)) {
458          conflicting_srcs.InsertOp(current->first.destination);
459          move_map.erase(current);
460          changed = true;
461        }
462      }
463    } while (changed);
464  }
465
466  if (move_map.empty()) return;
467
468  DCHECK_NOT_NULL(instr);
469  bool gap_initialized = true;
470  if (instr->parallel_moves()[0] != nullptr &&
471      !instr->parallel_moves()[0]->empty()) {
472    // Will compress after insertion.
473    gap_initialized = false;
474    std::swap(instr->parallel_moves()[0], instr->parallel_moves()[1]);
475  }
476  ParallelMove* moves = instr->GetOrCreateParallelMove(
477      static_cast<Instruction::GapPosition>(0), code_zone());
478  // Delete relevant entries in predecessors and move everything to block.
479  bool first_iteration = true;
480  for (RpoNumber& pred_index : block->predecessors()) {
481    const InstructionBlock* pred = code()->InstructionBlockAt(pred_index);
482    for (MoveOperands* move : *LastInstruction(pred)->parallel_moves()[0]) {
483      if (move->IsRedundant()) continue;
484      MoveKey key = {move->source(), move->destination()};
485      auto it = move_map.find(key);
486      if (it != move_map.end()) {
487        if (first_iteration) {
488          moves->AddMove(move->source(), move->destination());
489        }
490        move->Eliminate();
491      }
492    }
493    first_iteration = false;
494  }
495  // Compress.
496  if (!gap_initialized) {
497    CompressMoves(instr->parallel_moves()[0], instr->parallel_moves()[1]);
498  }
499  CompressBlock(block);
500}
501
502
503namespace {
504
505bool IsSlot(const InstructionOperand& op) {
506  return op.IsStackSlot() || op.IsFPStackSlot();
507}
508
509
510bool LoadCompare(const MoveOperands* a, const MoveOperands* b) {
511  if (!a->source().EqualsCanonicalized(b->source())) {
512    return a->source().CompareCanonicalized(b->source());
513  }
514  if (IsSlot(a->destination()) && !IsSlot(b->destination())) return false;
515  if (!IsSlot(a->destination()) && IsSlot(b->destination())) return true;
516  return a->destination().CompareCanonicalized(b->destination());
517}
518
519}  // namespace
520
521
522// Split multiple loads of the same constant or stack slot off into the second
523// slot and keep remaining moves in the first slot.
524void MoveOptimizer::FinalizeMoves(Instruction* instr) {
525  MoveOpVector& loads = local_vector();
526  DCHECK(loads.empty());
527
528  ParallelMove* parallel_moves = instr->parallel_moves()[0];
529  if (parallel_moves == nullptr) return;
530  // Find all the loads.
531  for (MoveOperands* move : *parallel_moves) {
532    if (move->IsRedundant()) continue;
533    if (move->source().IsConstant() || IsSlot(move->source())) {
534      loads.push_back(move);
535    }
536  }
537  if (loads.empty()) return;
538  // Group the loads by source, moving the preferred destination to the
539  // beginning of the group.
540  std::sort(loads.begin(), loads.end(), LoadCompare);
541  MoveOperands* group_begin = nullptr;
542  for (MoveOperands* load : loads) {
543    // New group.
544    if (group_begin == nullptr ||
545        !load->source().EqualsCanonicalized(group_begin->source())) {
546      group_begin = load;
547      continue;
548    }
549    // Nothing to be gained from splitting here.
550    if (IsSlot(group_begin->destination())) continue;
551    // Insert new move into slot 1.
552    ParallelMove* slot_1 = instr->GetOrCreateParallelMove(
553        static_cast<Instruction::GapPosition>(1), code_zone());
554    slot_1->AddMove(group_begin->destination(), load->destination());
555    load->Eliminate();
556  }
557  loads.clear();
558}
559
560}  // namespace compiler
561}  // namespace internal
562}  // namespace v8
563