MachineSink.cpp revision 7c30304c7ba25fbae52d4db2f5ae230ba2475288
1//===-- MachineSink.cpp - Sinking for machine instructions ----------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This pass moves instructions into successor blocks when possible, so that 11// they aren't executed on paths where their results aren't needed. 12// 13// This pass is not intended to be a replacement or a complete alternative 14// for an LLVM-IR-level sinking pass. It is only designed to sink simple 15// constructs that are not exposed before lowering and instruction selection. 16// 17//===----------------------------------------------------------------------===// 18 19#define DEBUG_TYPE "machine-sink" 20#include "llvm/CodeGen/Passes.h" 21#include "llvm/CodeGen/MachineRegisterInfo.h" 22#include "llvm/CodeGen/MachineDominators.h" 23#include "llvm/CodeGen/MachineLoopInfo.h" 24#include "llvm/Analysis/AliasAnalysis.h" 25#include "llvm/Target/TargetRegisterInfo.h" 26#include "llvm/Target/TargetInstrInfo.h" 27#include "llvm/Target/TargetMachine.h" 28#include "llvm/ADT/SmallSet.h" 29#include "llvm/ADT/Statistic.h" 30#include "llvm/Support/CommandLine.h" 31#include "llvm/Support/Debug.h" 32#include "llvm/Support/raw_ostream.h" 33using namespace llvm; 34 35static cl::opt<bool> 36SplitEdges("machine-sink-split", 37 cl::desc("Split critical edges during machine sinking"), 38 cl::init(false), cl::Hidden); 39static cl::opt<unsigned> 40SplitLimit("split-limit", 41 cl::init(~0u), cl::Hidden); 42 43STATISTIC(NumSunk, "Number of machine instructions sunk"); 44STATISTIC(NumSplit, "Number of critical edges split"); 45STATISTIC(NumCoalesces, "Number of copies coalesced"); 46 47namespace { 48 class MachineSinking : public MachineFunctionPass { 49 const TargetInstrInfo *TII; 50 const TargetRegisterInfo *TRI; 51 MachineRegisterInfo *MRI; // Machine register information 52 MachineDominatorTree *DT; // Machine dominator tree 53 MachineLoopInfo *LI; 54 AliasAnalysis *AA; 55 BitVector AllocatableSet; // Which physregs are allocatable? 56 57 // Remember which edges have been considered for breaking. 58 SmallSet<std::pair<MachineBasicBlock*,MachineBasicBlock*>, 8> 59 CEBCandidates; 60 61 public: 62 static char ID; // Pass identification 63 MachineSinking() : MachineFunctionPass(ID) {} 64 65 virtual bool runOnMachineFunction(MachineFunction &MF); 66 67 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 68 AU.setPreservesCFG(); 69 MachineFunctionPass::getAnalysisUsage(AU); 70 AU.addRequired<AliasAnalysis>(); 71 AU.addRequired<MachineDominatorTree>(); 72 AU.addRequired<MachineLoopInfo>(); 73 AU.addPreserved<MachineDominatorTree>(); 74 AU.addPreserved<MachineLoopInfo>(); 75 } 76 77 virtual void releaseMemory() { 78 CEBCandidates.clear(); 79 } 80 81 private: 82 bool ProcessBlock(MachineBasicBlock &MBB); 83 bool isWorthBreakingCriticalEdge(MachineInstr *MI, 84 MachineBasicBlock *From, 85 MachineBasicBlock *To); 86 MachineBasicBlock *SplitCriticalEdge(MachineInstr *MI, 87 MachineBasicBlock *From, 88 MachineBasicBlock *To, 89 bool AllPHIUse); 90 bool SinkInstruction(MachineInstr *MI, bool &SawStore); 91 bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB, 92 MachineBasicBlock *DefMBB, 93 bool &AllPHIUse, bool &LocalUse) const; 94 bool PerformTrivialForwardCoalescing(MachineInstr *MI, 95 MachineBasicBlock *MBB); 96 }; 97} // end anonymous namespace 98 99char MachineSinking::ID = 0; 100INITIALIZE_PASS(MachineSinking, "machine-sink", 101 "Machine code sinking", false, false); 102 103FunctionPass *llvm::createMachineSinkingPass() { return new MachineSinking(); } 104 105bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr *MI, 106 MachineBasicBlock *MBB) { 107 if (!MI->isCopy()) 108 return false; 109 110 unsigned SrcReg = MI->getOperand(1).getReg(); 111 unsigned DstReg = MI->getOperand(0).getReg(); 112 if (!TargetRegisterInfo::isVirtualRegister(SrcReg) || 113 !TargetRegisterInfo::isVirtualRegister(DstReg) || 114 !MRI->hasOneNonDBGUse(SrcReg)) 115 return false; 116 117 const TargetRegisterClass *SRC = MRI->getRegClass(SrcReg); 118 const TargetRegisterClass *DRC = MRI->getRegClass(DstReg); 119 if (SRC != DRC) 120 return false; 121 122 MachineInstr *DefMI = MRI->getVRegDef(SrcReg); 123 if (DefMI->isCopyLike()) 124 return false; 125 DEBUG(dbgs() << "Coalescing: " << *DefMI); 126 DEBUG(dbgs() << "*** to: " << *MI); 127 MRI->replaceRegWith(DstReg, SrcReg); 128 MI->eraseFromParent(); 129 ++NumCoalesces; 130 return true; 131} 132 133/// AllUsesDominatedByBlock - Return true if all uses of the specified register 134/// occur in blocks dominated by the specified block. If any use is in the 135/// definition block, then return false since it is never legal to move def 136/// after uses. 137bool 138MachineSinking::AllUsesDominatedByBlock(unsigned Reg, 139 MachineBasicBlock *MBB, 140 MachineBasicBlock *DefMBB, 141 bool &AllPHIUse, bool &LocalUse) const { 142 assert(TargetRegisterInfo::isVirtualRegister(Reg) && 143 "Only makes sense for vregs"); 144 145 if (MRI->use_nodbg_empty(Reg)) 146 return true; 147 148 // Ignoring debug uses is necessary so debug info doesn't affect the code. 149 // This may leave a referencing dbg_value in the original block, before 150 // the definition of the vreg. Dwarf generator handles this although the 151 // user might not get the right info at runtime. 152 153 // PHI is in the successor BB. e.g. 154 // BB#1: derived from LLVM BB %bb4.preheader 155 // Predecessors according to CFG: BB#0 156 // ... 157 // %reg16385<def> = DEC64_32r %reg16437, %EFLAGS<imp-def,dead> 158 // ... 159 // JE_4 <BB#37>, %EFLAGS<imp-use> 160 // Successors according to CFG: BB#37 BB#2 161 // 162 // BB#2: derived from LLVM BB %bb.nph 163 // Predecessors according to CFG: BB#0 BB#1 164 // %reg16386<def> = PHI %reg16434, <BB#0>, %reg16385, <BB#1> 165 // 166 // Machine sink should break the critical edge first. 167 AllPHIUse = true; 168 for (MachineRegisterInfo::use_nodbg_iterator 169 I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end(); 170 I != E; ++I) { 171 MachineInstr *UseInst = &*I; 172 MachineBasicBlock *UseBlock = UseInst->getParent(); 173 if (!(UseBlock == MBB && UseInst->isPHI() && 174 UseInst->getOperand(I.getOperandNo()+1).getMBB() == DefMBB)) { 175 AllPHIUse = false; 176 break; 177 } 178 } 179 if (AllPHIUse) 180 return true; 181 182 for (MachineRegisterInfo::use_nodbg_iterator 183 I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end(); 184 I != E; ++I) { 185 // Determine the block of the use. 186 MachineInstr *UseInst = &*I; 187 MachineBasicBlock *UseBlock = UseInst->getParent(); 188 if (UseInst->isPHI()) { 189 // PHI nodes use the operand in the predecessor block, not the block with 190 // the PHI. 191 UseBlock = UseInst->getOperand(I.getOperandNo()+1).getMBB(); 192 } else if (UseBlock == DefMBB) { 193 LocalUse = true; 194 return false; 195 } 196 197 // Check that it dominates. 198 if (!DT->dominates(MBB, UseBlock)) 199 return false; 200 } 201 202 return true; 203} 204 205bool MachineSinking::runOnMachineFunction(MachineFunction &MF) { 206 DEBUG(dbgs() << "******** Machine Sinking ********\n"); 207 208 const TargetMachine &TM = MF.getTarget(); 209 TII = TM.getInstrInfo(); 210 TRI = TM.getRegisterInfo(); 211 MRI = &MF.getRegInfo(); 212 DT = &getAnalysis<MachineDominatorTree>(); 213 LI = &getAnalysis<MachineLoopInfo>(); 214 AA = &getAnalysis<AliasAnalysis>(); 215 AllocatableSet = TRI->getAllocatableSet(MF); 216 217 bool EverMadeChange = false; 218 219 while (1) { 220 bool MadeChange = false; 221 222 // Process all basic blocks. 223 CEBCandidates.clear(); 224 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); 225 I != E; ++I) 226 MadeChange |= ProcessBlock(*I); 227 228 // If this iteration over the code changed anything, keep iterating. 229 if (!MadeChange) break; 230 EverMadeChange = true; 231 } 232 return EverMadeChange; 233} 234 235bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) { 236 // Can't sink anything out of a block that has less than two successors. 237 if (MBB.succ_size() <= 1 || MBB.empty()) return false; 238 239 // Don't bother sinking code out of unreachable blocks. In addition to being 240 // unprofitable, it can also lead to infinite looping, because in an 241 // unreachable loop there may be nowhere to stop. 242 if (!DT->isReachableFromEntry(&MBB)) return false; 243 244 bool MadeChange = false; 245 246 // Walk the basic block bottom-up. Remember if we saw a store. 247 MachineBasicBlock::iterator I = MBB.end(); 248 --I; 249 bool ProcessedBegin, SawStore = false; 250 do { 251 MachineInstr *MI = I; // The instruction to sink. 252 253 // Predecrement I (if it's not begin) so that it isn't invalidated by 254 // sinking. 255 ProcessedBegin = I == MBB.begin(); 256 if (!ProcessedBegin) 257 --I; 258 259 if (MI->isDebugValue()) 260 continue; 261 262 if (PerformTrivialForwardCoalescing(MI, &MBB)) 263 continue; 264 265 if (SinkInstruction(MI, SawStore)) 266 ++NumSunk, MadeChange = true; 267 268 // If we just processed the first instruction in the block, we're done. 269 } while (!ProcessedBegin); 270 271 return MadeChange; 272} 273 274bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr *MI, 275 MachineBasicBlock *From, 276 MachineBasicBlock *To) { 277 // FIXME: Need much better heuristics. 278 279 // If the pass has already considered breaking this edge (during this pass 280 // through the function), then let's go ahead and break it. This means 281 // sinking multiple "cheap" instructions into the same block. 282 if (!CEBCandidates.insert(std::make_pair(From, To))) 283 return true; 284 285 if (!(MI->isCopyLike() || MI->getDesc().isAsCheapAsAMove())) 286 return true; 287 288 // MI is cheap, we probably don't want to break the critical edge for it. 289 // However, if this would allow some definitions of its source operands 290 // to be sunk then it's probably worth it. 291 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 292 const MachineOperand &MO = MI->getOperand(i); 293 if (!MO.isReg()) continue; 294 unsigned Reg = MO.getReg(); 295 if (Reg == 0 || !TargetRegisterInfo::isPhysicalRegister(Reg)) 296 continue; 297 if (MRI->hasOneNonDBGUse(Reg)) 298 return true; 299 } 300 301 return false; 302} 303 304MachineBasicBlock *MachineSinking::SplitCriticalEdge(MachineInstr *MI, 305 MachineBasicBlock *FromBB, 306 MachineBasicBlock *ToBB, 307 bool AllPHIUse) { 308 if (!isWorthBreakingCriticalEdge(MI, FromBB, ToBB)) 309 return 0; 310 311 // Avoid breaking back edge. From == To means backedge for single BB loop. 312 if (!SplitEdges || NumSplit == SplitLimit || FromBB == ToBB) 313 return 0; 314 315 // Check for backedges of more "complex" loops. 316 if (LI->getLoopFor(FromBB) == LI->getLoopFor(ToBB) && 317 LI->isLoopHeader(ToBB)) 318 return 0; 319 320 // It's not always legal to break critical edges and sink the computation 321 // to the edge. 322 // 323 // BB#1: 324 // v1024 325 // Beq BB#3 326 // <fallthrough> 327 // BB#2: 328 // ... no uses of v1024 329 // <fallthrough> 330 // BB#3: 331 // ... 332 // = v1024 333 // 334 // If BB#1 -> BB#3 edge is broken and computation of v1024 is inserted: 335 // 336 // BB#1: 337 // ... 338 // Bne BB#2 339 // BB#4: 340 // v1024 = 341 // B BB#3 342 // BB#2: 343 // ... no uses of v1024 344 // <fallthrough> 345 // BB#3: 346 // ... 347 // = v1024 348 // 349 // This is incorrect since v1024 is not computed along the BB#1->BB#2->BB#3 350 // flow. We need to ensure the new basic block where the computation is 351 // sunk to dominates all the uses. 352 // It's only legal to break critical edge and sink the computation to the 353 // new block if all the predecessors of "To", except for "From", are 354 // not dominated by "From". Given SSA property, this means these 355 // predecessors are dominated by "To". 356 // 357 // There is no need to do this check if all the uses are PHI nodes. PHI 358 // sources are only defined on the specific predecessor edges. 359 if (!AllPHIUse) { 360 for (MachineBasicBlock::pred_iterator PI = ToBB->pred_begin(), 361 E = ToBB->pred_end(); PI != E; ++PI) { 362 if (*PI == FromBB) 363 continue; 364 if (!DT->dominates(ToBB, *PI)) 365 return 0; 366 } 367 } 368 369 return FromBB->SplitCriticalEdge(ToBB, this); 370} 371 372/// SinkInstruction - Determine whether it is safe to sink the specified machine 373/// instruction out of its current block into a successor. 374bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { 375 // Check if it's safe to move the instruction. 376 if (!MI->isSafeToMove(TII, AA, SawStore)) 377 return false; 378 379 // FIXME: This should include support for sinking instructions within the 380 // block they are currently in to shorten the live ranges. We often get 381 // instructions sunk into the top of a large block, but it would be better to 382 // also sink them down before their first use in the block. This xform has to 383 // be careful not to *increase* register pressure though, e.g. sinking 384 // "x = y + z" down if it kills y and z would increase the live ranges of y 385 // and z and only shrink the live range of x. 386 387 // Loop over all the operands of the specified instruction. If there is 388 // anything we can't handle, bail out. 389 MachineBasicBlock *ParentBlock = MI->getParent(); 390 391 // SuccToSinkTo - This is the successor to sink this instruction to, once we 392 // decide. 393 MachineBasicBlock *SuccToSinkTo = 0; 394 395 bool AllPHIUse = false; 396 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 397 const MachineOperand &MO = MI->getOperand(i); 398 if (!MO.isReg()) continue; // Ignore non-register operands. 399 400 unsigned Reg = MO.getReg(); 401 if (Reg == 0) continue; 402 403 if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 404 if (MO.isUse()) { 405 // If the physreg has no defs anywhere, it's just an ambient register 406 // and we can freely move its uses. Alternatively, if it's allocatable, 407 // it could get allocated to something with a def during allocation. 408 if (!MRI->def_empty(Reg)) 409 return false; 410 411 if (AllocatableSet.test(Reg)) 412 return false; 413 414 // Check for a def among the register's aliases too. 415 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) { 416 unsigned AliasReg = *Alias; 417 if (!MRI->def_empty(AliasReg)) 418 return false; 419 420 if (AllocatableSet.test(AliasReg)) 421 return false; 422 } 423 } else if (!MO.isDead()) { 424 // A def that isn't dead. We can't move it. 425 return false; 426 } 427 } else { 428 // Virtual register uses are always safe to sink. 429 if (MO.isUse()) continue; 430 431 // If it's not safe to move defs of the register class, then abort. 432 if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg))) 433 return false; 434 435 // FIXME: This picks a successor to sink into based on having one 436 // successor that dominates all the uses. However, there are cases where 437 // sinking can happen but where the sink point isn't a successor. For 438 // example: 439 // 440 // x = computation 441 // if () {} else {} 442 // use x 443 // 444 // the instruction could be sunk over the whole diamond for the 445 // if/then/else (or loop, etc), allowing it to be sunk into other blocks 446 // after that. 447 448 // Virtual register defs can only be sunk if all their uses are in blocks 449 // dominated by one of the successors. 450 if (SuccToSinkTo) { 451 // If a previous operand picked a block to sink to, then this operand 452 // must be sinkable to the same block. 453 bool LocalUse = false; 454 if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, ParentBlock, 455 AllPHIUse, LocalUse)) 456 return false; 457 458 continue; 459 } 460 461 // Otherwise, we should look at all the successors and decide which one 462 // we should sink to. 463 for (MachineBasicBlock::succ_iterator SI = ParentBlock->succ_begin(), 464 E = ParentBlock->succ_end(); SI != E; ++SI) { 465 bool LocalUse = false; 466 if (AllUsesDominatedByBlock(Reg, *SI, ParentBlock, 467 AllPHIUse, LocalUse)) { 468 SuccToSinkTo = *SI; 469 break; 470 } 471 if (LocalUse) 472 // Def is used locally, it's never safe to move this def. 473 return false; 474 } 475 476 // If we couldn't find a block to sink to, ignore this instruction. 477 if (SuccToSinkTo == 0) 478 return false; 479 } 480 } 481 482 // If there are no outputs, it must have side-effects. 483 if (SuccToSinkTo == 0) 484 return false; 485 486 // It's not safe to sink instructions to EH landing pad. Control flow into 487 // landing pad is implicitly defined. 488 if (SuccToSinkTo->isLandingPad()) 489 return false; 490 491 // It is not possible to sink an instruction into its own block. This can 492 // happen with loops. 493 if (MI->getParent() == SuccToSinkTo) 494 return false; 495 496 // If the instruction to move defines a dead physical register which is live 497 // when leaving the basic block, don't move it because it could turn into a 498 // "zombie" define of that preg. E.g., EFLAGS. (<rdar://problem/8030636>) 499 for (unsigned I = 0, E = MI->getNumOperands(); I != E; ++I) { 500 const MachineOperand &MO = MI->getOperand(I); 501 if (!MO.isReg()) continue; 502 unsigned Reg = MO.getReg(); 503 if (Reg == 0 || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 504 if (SuccToSinkTo->isLiveIn(Reg)) 505 return false; 506 } 507 508 DEBUG(dbgs() << "Sink instr " << *MI << "\tinto block " << *SuccToSinkTo); 509 510 // If the block has multiple predecessors, this would introduce computation on 511 // a path that it doesn't already exist. We could split the critical edge, 512 // but for now we just punt. 513 if (SuccToSinkTo->pred_size() > 1) { 514 // We cannot sink a load across a critical edge - there may be stores in 515 // other code paths. 516 bool TryBreak = false; 517 bool store = true; 518 if (!MI->isSafeToMove(TII, AA, store)) { 519 DEBUG(dbgs() << " *** NOTE: Won't sink load along critical edge.\n"); 520 TryBreak = true; 521 } 522 523 // We don't want to sink across a critical edge if we don't dominate the 524 // successor. We could be introducing calculations to new code paths. 525 if (!TryBreak && !DT->dominates(ParentBlock, SuccToSinkTo)) { 526 DEBUG(dbgs() << " *** NOTE: Critical edge found\n"); 527 TryBreak = true; 528 } 529 530 // Don't sink instructions into a loop. 531 if (!TryBreak && LI->isLoopHeader(SuccToSinkTo)) { 532 DEBUG(dbgs() << " *** NOTE: Loop header found\n"); 533 TryBreak = true; 534 } 535 536 // Otherwise we are OK with sinking along a critical edge. 537 if (!TryBreak) 538 DEBUG(dbgs() << "Sinking along critical edge.\n"); 539 else { 540 MachineBasicBlock *NewSucc = 541 SplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, AllPHIUse); 542 if (!NewSucc) { 543 DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to " 544 "break critical edge\n"); 545 return false; 546 } else { 547 DEBUG(dbgs() << " *** Splitting critical edge:" 548 " BB#" << ParentBlock->getNumber() 549 << " -- BB#" << NewSucc->getNumber() 550 << " -- BB#" << SuccToSinkTo->getNumber() << '\n'); 551 SuccToSinkTo = NewSucc; 552 ++NumSplit; 553 } 554 } 555 } 556 557 if (AllPHIUse) { 558 if (NumSplit == SplitLimit) 559 return false; 560 MachineBasicBlock *NewSucc = SplitCriticalEdge(MI, ParentBlock, 561 SuccToSinkTo, AllPHIUse); 562 if (!NewSucc) { 563 DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to " 564 "break critical edge\n"); 565 return false; 566 } 567 568 DEBUG(dbgs() << " *** Splitting critical edge:" 569 " BB#" << ParentBlock->getNumber() 570 << " -- BB#" << NewSucc->getNumber() 571 << " -- BB#" << SuccToSinkTo->getNumber() << '\n'); 572 SuccToSinkTo = NewSucc; 573 ++NumSplit; 574 } 575 576 // Determine where to insert into. Skip phi nodes. 577 MachineBasicBlock::iterator InsertPos = SuccToSinkTo->begin(); 578 while (InsertPos != SuccToSinkTo->end() && InsertPos->isPHI()) 579 ++InsertPos; 580 581 // Move the instruction. 582 SuccToSinkTo->splice(InsertPos, ParentBlock, MI, 583 ++MachineBasicBlock::iterator(MI)); 584 585 // Conservatively, clear any kill flags, since it's possible that they are no 586 // longer correct. 587 MI->clearKillInfo(); 588 589 return true; 590} 591