• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 struct MoveKey {
14   InstructionOperand source;
15   InstructionOperand destination;
16 };
17 
18 struct MoveKeyCompare {
operator ()v8::internal::compiler::__anondb3047930111::MoveKeyCompare19   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 
27 typedef ZoneMap<MoveKey, unsigned, MoveKeyCompare> MoveMap;
28 
29 class OperandSet {
30  public:
OperandSet(ZoneVector<InstructionOperand> * buffer)31   explicit OperandSet(ZoneVector<InstructionOperand>* buffer)
32       : set_(buffer), fp_reps_(0) {
33     buffer->clear();
34   }
35 
InsertOp(const InstructionOperand & op)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 
Contains(const InstructionOperand & op) const43   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 
ContainsOpOrAlias(const InstructionOperand & op) const50   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::Default();
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:
RepBit(MachineRepresentation rep)103   static int RepBit(MachineRepresentation rep) {
104     return 1 << static_cast<int>(rep);
105   }
106 
HasMixedFPReps(int reps)107   static bool HasMixedFPReps(int reps) {
108     return reps && !base::bits::IsPowerOfTwo(reps);
109   }
110 
111   ZoneVector<InstructionOperand>* set_;
112   int fp_reps_;
113 };
114 
FindFirstNonEmptySlot(const Instruction * instr)115 int 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 
MoveOptimizer(Zone * local_zone,InstructionSequence * code)131 MoveOptimizer::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 
Run()138 void 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 
RemoveClobberedDestinations(Instruction * instruction)168 void 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 
MigrateMoves(Instruction * to,Instruction * from)212 void 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 
CompressMoves(ParallelMove * left,MoveOpVector * right)296 void 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 
CompressGaps(Instruction * instruction)325 void 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 
CompressBlock(InstructionBlock * block)352 void 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 
LastInstruction(const InstructionBlock * block) const372 const Instruction* MoveOptimizer::LastInstruction(
373     const InstructionBlock* block) const {
374   return code()->instructions()[block->last_instruction_index()];
375 }
376 
377 
OptimizeMerge(InstructionBlock * block)378 void MoveOptimizer::OptimizeMerge(InstructionBlock* block) {
379   DCHECK_LT(1, block->PredecessorCount());
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 
503 namespace {
504 
IsSlot(const InstructionOperand & op)505 bool IsSlot(const InstructionOperand& op) {
506   return op.IsStackSlot() || op.IsFPStackSlot();
507 }
508 
509 
LoadCompare(const MoveOperands * a,const MoveOperands * b)510 bool 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.
FinalizeMoves(Instruction * instr)524 void 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