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 { 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 27 typedef ZoneMap<MoveKey, unsigned, MoveKeyCompare> MoveMap; 28 29 class 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 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 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 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 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 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 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 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 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 372 const Instruction* MoveOptimizer::LastInstruction( 373 const InstructionBlock* block) const { 374 return code()->instructions()[block->last_instruction_index()]; 375 } 376 377 378 void 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 503 namespace { 504 505 bool IsSlot(const InstructionOperand& op) { 506 return op.IsStackSlot() || op.IsFPStackSlot(); 507 } 508 509 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. 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