Home | History | Annotate | Download | only in compiler 
      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 
     15 struct MoveKeyCompare {
     16   bool operator()(const MoveKey& a, const MoveKey& b) const {
     17     if (a.first.EqualsCanonicalized(b.first)) {
     18       return a.second.CompareCanonicalized(b.second);
     19     }
     20     return a.first.CompareCanonicalized(b.first);
     21   }
     22 };
     23 
     24 struct OperandCompare {
     25   bool operator()(const InstructionOperand& a,
     26                   const InstructionOperand& b) const {
     27     return a.CompareCanonicalized(b);
     28   }
     29 };
     30 
     31 typedef ZoneMap<MoveKey, unsigned, MoveKeyCompare> MoveMap;
     32 typedef ZoneSet<InstructionOperand, CompareOperandModuloType> OperandSet;
     33 
     34 
     35 bool GapsCanMoveOver(Instruction* instr, Zone* zone) {
     36   if (instr->IsNop()) return true;
     37   if (instr->ClobbersTemps() || instr->ClobbersRegisters() ||
     38       instr->ClobbersDoubleRegisters()) {
     39     return false;
     40   }
     41   if (instr->arch_opcode() != ArchOpcode::kArchNop) return false;
     42 
     43   ZoneSet<InstructionOperand, OperandCompare> operands(zone);
     44   for (size_t i = 0; i < instr->InputCount(); ++i) {
     45     operands.insert(*instr->InputAt(i));
     46   }
     47   for (size_t i = 0; i < instr->OutputCount(); ++i) {
     48     operands.insert(*instr->OutputAt(i));
     49   }
     50   for (size_t i = 0; i < instr->TempCount(); ++i) {
     51     operands.insert(*instr->TempAt(i));
     52   }
     53   for (int i = Instruction::GapPosition::FIRST_GAP_POSITION;
     54        i <= Instruction::GapPosition::LAST_GAP_POSITION; ++i) {
     55     ParallelMove* moves = instr->parallel_moves()[i];
     56     if (moves == nullptr) continue;
     57     for (MoveOperands* move : *moves) {
     58       if (operands.count(move->source()) > 0 ||
     59           operands.count(move->destination()) > 0) {
     60         return false;
     61       }
     62     }
     63   }
     64   return true;
     65 }
     66 
     67 
     68 int FindFirstNonEmptySlot(const Instruction* instr) {
     69   int i = Instruction::FIRST_GAP_POSITION;
     70   for (; i <= Instruction::LAST_GAP_POSITION; i++) {
     71     ParallelMove* moves = instr->parallel_moves()[i];
     72     if (moves == nullptr) continue;
     73     for (MoveOperands* move : *moves) {
     74       if (!move->IsRedundant()) return i;
     75       move->Eliminate();
     76     }
     77     moves->clear();  // Clear this redundant move.
     78   }
     79   return i;
     80 }
     81 
     82 }  // namespace
     83 
     84 
     85 MoveOptimizer::MoveOptimizer(Zone* local_zone, InstructionSequence* code)
     86     : local_zone_(local_zone),
     87       code_(code),
     88       to_finalize_(local_zone),
     89       local_vector_(local_zone) {}
     90 
     91 
     92 void MoveOptimizer::Run() {
     93   for (InstructionBlock* block : code()->instruction_blocks()) {
     94     CompressBlock(block);
     95   }
     96   for (InstructionBlock* block : code()->instruction_blocks()) {
     97     if (block->PredecessorCount() <= 1) continue;
     98     if (!block->IsDeferred()) {
     99       bool has_only_deferred = true;
    100       for (RpoNumber& pred_id : block->predecessors()) {
    101         if (!code()->InstructionBlockAt(pred_id)->IsDeferred()) {
    102           has_only_deferred = false;
    103           break;
    104         }
    105       }
    106       // This would pull down common moves. If the moves occur in deferred
    107       // blocks, and the closest common successor is not deferred, we lose the
    108       // optimization of just spilling/filling in deferred blocks, when the
    109       // current block is not deferred.
    110       if (has_only_deferred) continue;
    111     }
    112     OptimizeMerge(block);
    113   }
    114   for (Instruction* gap : to_finalize_) {
    115     FinalizeMoves(gap);
    116   }
    117 }
    118 
    119 
    120 void MoveOptimizer::CompressMoves(ParallelMove* left, ParallelMove* right) {
    121   if (right == nullptr) return;
    122 
    123   MoveOpVector& eliminated = local_vector();
    124   DCHECK(eliminated.empty());
    125 
    126   if (!left->empty()) {
    127     // Modify the right moves in place and collect moves that will be killed by
    128     // merging the two gaps.
    129     for (MoveOperands* move : *right) {
    130       if (move->IsRedundant()) continue;
    131       MoveOperands* to_eliminate = left->PrepareInsertAfter(move);
    132       if (to_eliminate != nullptr) eliminated.push_back(to_eliminate);
    133     }
    134     // Eliminate dead moves.
    135     for (MoveOperands* to_eliminate : eliminated) {
    136       to_eliminate->Eliminate();
    137     }
    138     eliminated.clear();
    139   }
    140   // Add all possibly modified moves from right side.
    141   for (MoveOperands* move : *right) {
    142     if (move->IsRedundant()) continue;
    143     left->push_back(move);
    144   }
    145   // Nuke right.
    146   right->clear();
    147   DCHECK(eliminated.empty());
    148 }
    149 
    150 
    151 // Smash all consecutive moves into the left most move slot and accumulate them
    152 // as much as possible across instructions.
    153 void MoveOptimizer::CompressBlock(InstructionBlock* block) {
    154   Instruction* prev_instr = nullptr;
    155   for (int index = block->code_start(); index < block->code_end(); ++index) {
    156     Instruction* instr = code()->instructions()[index];
    157     int i = FindFirstNonEmptySlot(instr);
    158     bool has_moves = i <= Instruction::LAST_GAP_POSITION;
    159 
    160     if (i == Instruction::LAST_GAP_POSITION) {
    161       std::swap(instr->parallel_moves()[Instruction::FIRST_GAP_POSITION],
    162                 instr->parallel_moves()[Instruction::LAST_GAP_POSITION]);
    163     } else if (i == Instruction::FIRST_GAP_POSITION) {
    164       CompressMoves(instr->parallel_moves()[Instruction::FIRST_GAP_POSITION],
    165                     instr->parallel_moves()[Instruction::LAST_GAP_POSITION]);
    166     }
    167     // We either have no moves, or, after swapping or compressing, we have
    168     // all the moves in the first gap position, and none in the second/end gap
    169     // position.
    170     ParallelMove* first =
    171         instr->parallel_moves()[Instruction::FIRST_GAP_POSITION];
    172     ParallelMove* last =
    173         instr->parallel_moves()[Instruction::LAST_GAP_POSITION];
    174     USE(last);
    175 
    176     DCHECK(!has_moves ||
    177            (first != nullptr && (last == nullptr || last->empty())));
    178 
    179     if (prev_instr != nullptr) {
    180       if (has_moves) {
    181         // Smash first into prev_instr, killing left.
    182         ParallelMove* pred_moves = prev_instr->parallel_moves()[0];
    183         CompressMoves(pred_moves, first);
    184       }
    185       // Slide prev_instr down so we always know where to look for it.
    186       std::swap(prev_instr->parallel_moves()[0], instr->parallel_moves()[0]);
    187     }
    188 
    189     prev_instr = instr->parallel_moves()[0] == nullptr ? nullptr : instr;
    190     if (GapsCanMoveOver(instr, local_zone())) continue;
    191     if (prev_instr != nullptr) {
    192       to_finalize_.push_back(prev_instr);
    193       prev_instr = nullptr;
    194     }
    195   }
    196   if (prev_instr != nullptr) {
    197     to_finalize_.push_back(prev_instr);
    198   }
    199 }
    200 
    201 
    202 const Instruction* MoveOptimizer::LastInstruction(
    203     const InstructionBlock* block) const {
    204   return code()->instructions()[block->last_instruction_index()];
    205 }
    206 
    207 
    208 void MoveOptimizer::OptimizeMerge(InstructionBlock* block) {
    209   DCHECK(block->PredecessorCount() > 1);
    210   // Ensure that the last instruction in all incoming blocks don't contain
    211   // things that would prevent moving gap moves across them.
    212   for (RpoNumber& pred_index : block->predecessors()) {
    213     const InstructionBlock* pred = code()->InstructionBlockAt(pred_index);
    214     const Instruction* last_instr =
    215         code()->instructions()[pred->last_instruction_index()];
    216     if (last_instr->IsCall()) return;
    217     if (last_instr->TempCount() != 0) return;
    218     if (last_instr->OutputCount() != 0) return;
    219     for (size_t i = 0; i < last_instr->InputCount(); ++i) {
    220       const InstructionOperand* op = last_instr->InputAt(i);
    221       if (!op->IsConstant() && !op->IsImmediate()) return;
    222     }
    223   }
    224   // TODO(dcarney): pass a ZonePool down for this?
    225   MoveMap move_map(local_zone());
    226   size_t correct_counts = 0;
    227   // Accumulate set of shared moves.
    228   for (RpoNumber& pred_index : block->predecessors()) {
    229     const InstructionBlock* pred = code()->InstructionBlockAt(pred_index);
    230     const Instruction* instr = LastInstruction(pred);
    231     if (instr->parallel_moves()[0] == nullptr ||
    232         instr->parallel_moves()[0]->empty()) {
    233       return;
    234     }
    235     for (const MoveOperands* move : *instr->parallel_moves()[0]) {
    236       if (move->IsRedundant()) continue;
    237       InstructionOperand src = move->source();
    238       InstructionOperand dst = move->destination();
    239       MoveKey key = {src, dst};
    240       auto res = move_map.insert(std::make_pair(key, 1));
    241       if (!res.second) {
    242         res.first->second++;
    243         if (res.first->second == block->PredecessorCount()) {
    244           correct_counts++;
    245         }
    246       }
    247     }
    248   }
    249   if (move_map.empty() || correct_counts != move_map.size()) return;
    250   // Find insertion point.
    251   Instruction* instr = nullptr;
    252   for (int i = block->first_instruction_index();
    253        i <= block->last_instruction_index(); ++i) {
    254     instr = code()->instructions()[i];
    255     if (!GapsCanMoveOver(instr, local_zone()) || !instr->AreMovesRedundant())
    256       break;
    257   }
    258   DCHECK_NOT_NULL(instr);
    259   bool gap_initialized = true;
    260   if (instr->parallel_moves()[0] == nullptr ||
    261       instr->parallel_moves()[0]->empty()) {
    262     to_finalize_.push_back(instr);
    263   } else {
    264     // Will compress after insertion.
    265     gap_initialized = false;
    266     std::swap(instr->parallel_moves()[0], instr->parallel_moves()[1]);
    267   }
    268   ParallelMove* moves = instr->GetOrCreateParallelMove(
    269       static_cast<Instruction::GapPosition>(0), code_zone());
    270   // Delete relevant entries in predecessors and move everything to block.
    271   bool first_iteration = true;
    272   for (RpoNumber& pred_index : block->predecessors()) {
    273     const InstructionBlock* pred = code()->InstructionBlockAt(pred_index);
    274     for (MoveOperands* move : *LastInstruction(pred)->parallel_moves()[0]) {
    275       if (move->IsRedundant()) continue;
    276       MoveKey key = {move->source(), move->destination()};
    277       auto it = move_map.find(key);
    278       USE(it);
    279       DCHECK(it != move_map.end());
    280       if (first_iteration) {
    281         moves->AddMove(move->source(), move->destination());
    282       }
    283       move->Eliminate();
    284     }
    285     first_iteration = false;
    286   }
    287   // Compress.
    288   if (!gap_initialized) {
    289     CompressMoves(instr->parallel_moves()[0], instr->parallel_moves()[1]);
    290   }
    291 }
    292 
    293 
    294 namespace {
    295 
    296 bool IsSlot(const InstructionOperand& op) {
    297   return op.IsStackSlot() || op.IsDoubleStackSlot();
    298 }
    299 
    300 
    301 bool LoadCompare(const MoveOperands* a, const MoveOperands* b) {
    302   if (!a->source().EqualsCanonicalized(b->source())) {
    303     return a->source().CompareCanonicalized(b->source());
    304   }
    305   if (IsSlot(a->destination()) && !IsSlot(b->destination())) return false;
    306   if (!IsSlot(a->destination()) && IsSlot(b->destination())) return true;
    307   return a->destination().CompareCanonicalized(b->destination());
    308 }
    309 
    310 }  // namespace
    311 
    312 
    313 // Split multiple loads of the same constant or stack slot off into the second
    314 // slot and keep remaining moves in the first slot.
    315 void MoveOptimizer::FinalizeMoves(Instruction* instr) {
    316   MoveOpVector& loads = local_vector();
    317   DCHECK(loads.empty());
    318 
    319   // Find all the loads.
    320   for (MoveOperands* move : *instr->parallel_moves()[0]) {
    321     if (move->IsRedundant()) continue;
    322     if (move->source().IsConstant() || IsSlot(move->source())) {
    323       loads.push_back(move);
    324     }
    325   }
    326   if (loads.empty()) return;
    327   // Group the loads by source, moving the preferred destination to the
    328   // beginning of the group.
    329   std::sort(loads.begin(), loads.end(), LoadCompare);
    330   MoveOperands* group_begin = nullptr;
    331   for (MoveOperands* load : loads) {
    332     // New group.
    333     if (group_begin == nullptr ||
    334         !load->source().EqualsCanonicalized(group_begin->source())) {
    335       group_begin = load;
    336       continue;
    337     }
    338     // Nothing to be gained from splitting here.
    339     if (IsSlot(group_begin->destination())) continue;
    340     // Insert new move into slot 1.
    341     ParallelMove* slot_1 = instr->GetOrCreateParallelMove(
    342         static_cast<Instruction::GapPosition>(1), code_zone());
    343     slot_1->AddMove(group_begin->destination(), load->destination());
    344     load->Eliminate();
    345   }
    346   loads.clear();
    347 }
    348 
    349 }  // namespace compiler
    350 }  // namespace internal
    351 }  // namespace v8
    352