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