Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 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 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame^] | 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 | |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 85 | MoveOptimizer::MoveOptimizer(Zone* local_zone, InstructionSequence* code) |
| 86 | : local_zone_(local_zone), |
| 87 | code_(code), |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame^] | 88 | to_finalize_(local_zone), |
| 89 | local_vector_(local_zone) {} |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 90 | |
| 91 | |
| 92 | void MoveOptimizer::Run() { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame^] | 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; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 104 | } |
| 105 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame^] | 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; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 111 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame^] | 112 | OptimizeMerge(block); |
| 113 | } |
| 114 | for (Instruction* gap : to_finalize_) { |
| 115 | FinalizeMoves(gap); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 116 | } |
| 117 | } |
| 118 | |
| 119 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame^] | 120 | void MoveOptimizer::CompressMoves(ParallelMove* left, ParallelMove* right) { |
| 121 | if (right == nullptr) return; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 122 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame^] | 123 | MoveOpVector& eliminated = local_vector(); |
| 124 | DCHECK(eliminated.empty()); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 125 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame^] | 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); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 133 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame^] | 134 | // Eliminate dead moves. |
| 135 | for (MoveOperands* to_eliminate : eliminated) { |
| 136 | to_eliminate->Eliminate(); |
| 137 | } |
| 138 | eliminated.clear(); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 139 | } |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 140 | // Add all possibly modified moves from right side. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame^] | 141 | for (MoveOperands* move : *right) { |
| 142 | if (move->IsRedundant()) continue; |
| 143 | left->push_back(move); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 144 | } |
| 145 | // Nuke right. |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame^] | 146 | right->clear(); |
| 147 | DCHECK(eliminated.empty()); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 148 | } |
| 149 | |
| 150 | |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame^] | 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]); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 166 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame^] | 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 | } |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 246 | } |
| 247 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame^] | 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; |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 336 | continue; |
| 337 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame^] | 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(); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 345 | } |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame^] | 346 | loads.clear(); |
Emily Bernier | d0a1eb7 | 2015-03-24 16:35:39 -0400 | [diff] [blame] | 347 | } |
| 348 | |
| 349 | } // namespace compiler |
| 350 | } // namespace internal |
| 351 | } // namespace v8 |