MachineSink.cpp revision 36b56886974eae4f9c5ebc96befd3e7bfe5de338
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/ADT/SmallSet.h" 22#include "llvm/ADT/Statistic.h" 23#include "llvm/Analysis/AliasAnalysis.h" 24#include "llvm/CodeGen/MachineDominators.h" 25#include "llvm/CodeGen/MachineLoopInfo.h" 26#include "llvm/CodeGen/MachineRegisterInfo.h" 27#include "llvm/Support/CommandLine.h" 28#include "llvm/Support/Debug.h" 29#include "llvm/Support/raw_ostream.h" 30#include "llvm/Target/TargetInstrInfo.h" 31#include "llvm/Target/TargetMachine.h" 32#include "llvm/Target/TargetRegisterInfo.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(true), cl::Hidden); 39 40STATISTIC(NumSunk, "Number of machine instructions sunk"); 41STATISTIC(NumSplit, "Number of critical edges split"); 42STATISTIC(NumCoalesces, "Number of copies coalesced"); 43 44namespace { 45 class MachineSinking : public MachineFunctionPass { 46 const TargetInstrInfo *TII; 47 const TargetRegisterInfo *TRI; 48 MachineRegisterInfo *MRI; // Machine register information 49 MachineDominatorTree *DT; // Machine dominator tree 50 MachineLoopInfo *LI; 51 AliasAnalysis *AA; 52 53 // Remember which edges have been considered for breaking. 54 SmallSet<std::pair<MachineBasicBlock*,MachineBasicBlock*>, 8> 55 CEBCandidates; 56 57 public: 58 static char ID; // Pass identification 59 MachineSinking() : MachineFunctionPass(ID) { 60 initializeMachineSinkingPass(*PassRegistry::getPassRegistry()); 61 } 62 63 bool runOnMachineFunction(MachineFunction &MF) override; 64 65 void getAnalysisUsage(AnalysisUsage &AU) const override { 66 AU.setPreservesCFG(); 67 MachineFunctionPass::getAnalysisUsage(AU); 68 AU.addRequired<AliasAnalysis>(); 69 AU.addRequired<MachineDominatorTree>(); 70 AU.addRequired<MachineLoopInfo>(); 71 AU.addPreserved<MachineDominatorTree>(); 72 AU.addPreserved<MachineLoopInfo>(); 73 } 74 75 void releaseMemory() override { 76 CEBCandidates.clear(); 77 } 78 79 private: 80 bool ProcessBlock(MachineBasicBlock &MBB); 81 bool isWorthBreakingCriticalEdge(MachineInstr *MI, 82 MachineBasicBlock *From, 83 MachineBasicBlock *To); 84 MachineBasicBlock *SplitCriticalEdge(MachineInstr *MI, 85 MachineBasicBlock *From, 86 MachineBasicBlock *To, 87 bool BreakPHIEdge); 88 bool SinkInstruction(MachineInstr *MI, bool &SawStore); 89 bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB, 90 MachineBasicBlock *DefMBB, 91 bool &BreakPHIEdge, bool &LocalUse) const; 92 MachineBasicBlock *FindSuccToSinkTo(MachineInstr *MI, MachineBasicBlock *MBB, 93 bool &BreakPHIEdge); 94 bool isProfitableToSinkTo(unsigned Reg, MachineInstr *MI, 95 MachineBasicBlock *MBB, 96 MachineBasicBlock *SuccToSinkTo); 97 98 bool PerformTrivialForwardCoalescing(MachineInstr *MI, 99 MachineBasicBlock *MBB); 100 }; 101} // end anonymous namespace 102 103char MachineSinking::ID = 0; 104char &llvm::MachineSinkingID = MachineSinking::ID; 105INITIALIZE_PASS_BEGIN(MachineSinking, "machine-sink", 106 "Machine code sinking", false, false) 107INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 108INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 109INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 110INITIALIZE_PASS_END(MachineSinking, "machine-sink", 111 "Machine code sinking", false, false) 112 113bool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr *MI, 114 MachineBasicBlock *MBB) { 115 if (!MI->isCopy()) 116 return false; 117 118 unsigned SrcReg = MI->getOperand(1).getReg(); 119 unsigned DstReg = MI->getOperand(0).getReg(); 120 if (!TargetRegisterInfo::isVirtualRegister(SrcReg) || 121 !TargetRegisterInfo::isVirtualRegister(DstReg) || 122 !MRI->hasOneNonDBGUse(SrcReg)) 123 return false; 124 125 const TargetRegisterClass *SRC = MRI->getRegClass(SrcReg); 126 const TargetRegisterClass *DRC = MRI->getRegClass(DstReg); 127 if (SRC != DRC) 128 return false; 129 130 MachineInstr *DefMI = MRI->getVRegDef(SrcReg); 131 if (DefMI->isCopyLike()) 132 return false; 133 DEBUG(dbgs() << "Coalescing: " << *DefMI); 134 DEBUG(dbgs() << "*** to: " << *MI); 135 MRI->replaceRegWith(DstReg, SrcReg); 136 MI->eraseFromParent(); 137 ++NumCoalesces; 138 return true; 139} 140 141/// AllUsesDominatedByBlock - Return true if all uses of the specified register 142/// occur in blocks dominated by the specified block. If any use is in the 143/// definition block, then return false since it is never legal to move def 144/// after uses. 145bool 146MachineSinking::AllUsesDominatedByBlock(unsigned Reg, 147 MachineBasicBlock *MBB, 148 MachineBasicBlock *DefMBB, 149 bool &BreakPHIEdge, 150 bool &LocalUse) const { 151 assert(TargetRegisterInfo::isVirtualRegister(Reg) && 152 "Only makes sense for vregs"); 153 154 // Ignore debug uses because debug info doesn't affect the code. 155 if (MRI->use_nodbg_empty(Reg)) 156 return true; 157 158 // BreakPHIEdge is true if all the uses are in the successor MBB being sunken 159 // into and they are all PHI nodes. In this case, machine-sink must break 160 // the critical edge first. e.g. 161 // 162 // BB#1: derived from LLVM BB %bb4.preheader 163 // Predecessors according to CFG: BB#0 164 // ... 165 // %reg16385<def> = DEC64_32r %reg16437, %EFLAGS<imp-def,dead> 166 // ... 167 // JE_4 <BB#37>, %EFLAGS<imp-use> 168 // Successors according to CFG: BB#37 BB#2 169 // 170 // BB#2: derived from LLVM BB %bb.nph 171 // Predecessors according to CFG: BB#0 BB#1 172 // %reg16386<def> = PHI %reg16434, <BB#0>, %reg16385, <BB#1> 173 BreakPHIEdge = true; 174 for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) { 175 MachineInstr *UseInst = MO.getParent(); 176 unsigned OpNo = &MO - &UseInst->getOperand(0); 177 MachineBasicBlock *UseBlock = UseInst->getParent(); 178 if (!(UseBlock == MBB && UseInst->isPHI() && 179 UseInst->getOperand(OpNo+1).getMBB() == DefMBB)) { 180 BreakPHIEdge = false; 181 break; 182 } 183 } 184 if (BreakPHIEdge) 185 return true; 186 187 for (MachineOperand &MO : MRI->use_nodbg_operands(Reg)) { 188 // Determine the block of the use. 189 MachineInstr *UseInst = MO.getParent(); 190 unsigned OpNo = &MO - &UseInst->getOperand(0); 191 MachineBasicBlock *UseBlock = UseInst->getParent(); 192 if (UseInst->isPHI()) { 193 // PHI nodes use the operand in the predecessor block, not the block with 194 // the PHI. 195 UseBlock = UseInst->getOperand(OpNo+1).getMBB(); 196 } else if (UseBlock == DefMBB) { 197 LocalUse = true; 198 return false; 199 } 200 201 // Check that it dominates. 202 if (!DT->dominates(MBB, UseBlock)) 203 return false; 204 } 205 206 return true; 207} 208 209bool MachineSinking::runOnMachineFunction(MachineFunction &MF) { 210 if (skipOptnoneFunction(*MF.getFunction())) 211 return false; 212 213 DEBUG(dbgs() << "******** Machine Sinking ********\n"); 214 215 const TargetMachine &TM = MF.getTarget(); 216 TII = TM.getInstrInfo(); 217 TRI = TM.getRegisterInfo(); 218 MRI = &MF.getRegInfo(); 219 DT = &getAnalysis<MachineDominatorTree>(); 220 LI = &getAnalysis<MachineLoopInfo>(); 221 AA = &getAnalysis<AliasAnalysis>(); 222 223 bool EverMadeChange = false; 224 225 while (1) { 226 bool MadeChange = false; 227 228 // Process all basic blocks. 229 CEBCandidates.clear(); 230 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); 231 I != E; ++I) 232 MadeChange |= ProcessBlock(*I); 233 234 // If this iteration over the code changed anything, keep iterating. 235 if (!MadeChange) break; 236 EverMadeChange = true; 237 } 238 return EverMadeChange; 239} 240 241bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) { 242 // Can't sink anything out of a block that has less than two successors. 243 if (MBB.succ_size() <= 1 || MBB.empty()) return false; 244 245 // Don't bother sinking code out of unreachable blocks. In addition to being 246 // unprofitable, it can also lead to infinite looping, because in an 247 // unreachable loop there may be nowhere to stop. 248 if (!DT->isReachableFromEntry(&MBB)) return false; 249 250 bool MadeChange = false; 251 252 // Walk the basic block bottom-up. Remember if we saw a store. 253 MachineBasicBlock::iterator I = MBB.end(); 254 --I; 255 bool ProcessedBegin, SawStore = false; 256 do { 257 MachineInstr *MI = I; // The instruction to sink. 258 259 // Predecrement I (if it's not begin) so that it isn't invalidated by 260 // sinking. 261 ProcessedBegin = I == MBB.begin(); 262 if (!ProcessedBegin) 263 --I; 264 265 if (MI->isDebugValue()) 266 continue; 267 268 bool Joined = PerformTrivialForwardCoalescing(MI, &MBB); 269 if (Joined) { 270 MadeChange = true; 271 continue; 272 } 273 274 if (SinkInstruction(MI, SawStore)) 275 ++NumSunk, MadeChange = true; 276 277 // If we just processed the first instruction in the block, we're done. 278 } while (!ProcessedBegin); 279 280 return MadeChange; 281} 282 283bool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr *MI, 284 MachineBasicBlock *From, 285 MachineBasicBlock *To) { 286 // FIXME: Need much better heuristics. 287 288 // If the pass has already considered breaking this edge (during this pass 289 // through the function), then let's go ahead and break it. This means 290 // sinking multiple "cheap" instructions into the same block. 291 if (!CEBCandidates.insert(std::make_pair(From, To))) 292 return true; 293 294 if (!MI->isCopy() && !MI->isAsCheapAsAMove()) 295 return true; 296 297 // MI is cheap, we probably don't want to break the critical edge for it. 298 // However, if this would allow some definitions of its source operands 299 // to be sunk then it's probably worth it. 300 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 301 const MachineOperand &MO = MI->getOperand(i); 302 if (!MO.isReg() || !MO.isUse()) 303 continue; 304 unsigned Reg = MO.getReg(); 305 if (Reg == 0) 306 continue; 307 308 // We don't move live definitions of physical registers, 309 // so sinking their uses won't enable any opportunities. 310 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 311 continue; 312 313 // If this instruction is the only user of a virtual register, 314 // check if breaking the edge will enable sinking 315 // both this instruction and the defining instruction. 316 if (MRI->hasOneNonDBGUse(Reg)) { 317 // If the definition resides in same MBB, 318 // claim it's likely we can sink these together. 319 // If definition resides elsewhere, we aren't 320 // blocking it from being sunk so don't break the edge. 321 MachineInstr *DefMI = MRI->getVRegDef(Reg); 322 if (DefMI->getParent() == MI->getParent()) 323 return true; 324 } 325 } 326 327 return false; 328} 329 330MachineBasicBlock *MachineSinking::SplitCriticalEdge(MachineInstr *MI, 331 MachineBasicBlock *FromBB, 332 MachineBasicBlock *ToBB, 333 bool BreakPHIEdge) { 334 if (!isWorthBreakingCriticalEdge(MI, FromBB, ToBB)) 335 return 0; 336 337 // Avoid breaking back edge. From == To means backedge for single BB loop. 338 if (!SplitEdges || FromBB == ToBB) 339 return 0; 340 341 // Check for backedges of more "complex" loops. 342 if (LI->getLoopFor(FromBB) == LI->getLoopFor(ToBB) && 343 LI->isLoopHeader(ToBB)) 344 return 0; 345 346 // It's not always legal to break critical edges and sink the computation 347 // to the edge. 348 // 349 // BB#1: 350 // v1024 351 // Beq BB#3 352 // <fallthrough> 353 // BB#2: 354 // ... no uses of v1024 355 // <fallthrough> 356 // BB#3: 357 // ... 358 // = v1024 359 // 360 // If BB#1 -> BB#3 edge is broken and computation of v1024 is inserted: 361 // 362 // BB#1: 363 // ... 364 // Bne BB#2 365 // BB#4: 366 // v1024 = 367 // B BB#3 368 // BB#2: 369 // ... no uses of v1024 370 // <fallthrough> 371 // BB#3: 372 // ... 373 // = v1024 374 // 375 // This is incorrect since v1024 is not computed along the BB#1->BB#2->BB#3 376 // flow. We need to ensure the new basic block where the computation is 377 // sunk to dominates all the uses. 378 // It's only legal to break critical edge and sink the computation to the 379 // new block if all the predecessors of "To", except for "From", are 380 // not dominated by "From". Given SSA property, this means these 381 // predecessors are dominated by "To". 382 // 383 // There is no need to do this check if all the uses are PHI nodes. PHI 384 // sources are only defined on the specific predecessor edges. 385 if (!BreakPHIEdge) { 386 for (MachineBasicBlock::pred_iterator PI = ToBB->pred_begin(), 387 E = ToBB->pred_end(); PI != E; ++PI) { 388 if (*PI == FromBB) 389 continue; 390 if (!DT->dominates(ToBB, *PI)) 391 return 0; 392 } 393 } 394 395 return FromBB->SplitCriticalEdge(ToBB, this); 396} 397 398static bool AvoidsSinking(MachineInstr *MI, MachineRegisterInfo *MRI) { 399 return MI->isInsertSubreg() || MI->isSubregToReg() || MI->isRegSequence(); 400} 401 402/// collectDebgValues - Scan instructions following MI and collect any 403/// matching DBG_VALUEs. 404static void collectDebugValues(MachineInstr *MI, 405 SmallVectorImpl<MachineInstr *> &DbgValues) { 406 DbgValues.clear(); 407 if (!MI->getOperand(0).isReg()) 408 return; 409 410 MachineBasicBlock::iterator DI = MI; ++DI; 411 for (MachineBasicBlock::iterator DE = MI->getParent()->end(); 412 DI != DE; ++DI) { 413 if (!DI->isDebugValue()) 414 return; 415 if (DI->getOperand(0).isReg() && 416 DI->getOperand(0).getReg() == MI->getOperand(0).getReg()) 417 DbgValues.push_back(DI); 418 } 419} 420 421/// isPostDominatedBy - Return true if A is post dominated by B. 422static bool isPostDominatedBy(MachineBasicBlock *A, MachineBasicBlock *B) { 423 424 // FIXME - Use real post dominator. 425 if (A->succ_size() != 2) 426 return false; 427 MachineBasicBlock::succ_iterator I = A->succ_begin(); 428 if (B == *I) 429 ++I; 430 MachineBasicBlock *OtherSuccBlock = *I; 431 if (OtherSuccBlock->succ_size() != 1 || 432 *(OtherSuccBlock->succ_begin()) != B) 433 return false; 434 435 return true; 436} 437 438/// isProfitableToSinkTo - Return true if it is profitable to sink MI. 439bool MachineSinking::isProfitableToSinkTo(unsigned Reg, MachineInstr *MI, 440 MachineBasicBlock *MBB, 441 MachineBasicBlock *SuccToSinkTo) { 442 assert (MI && "Invalid MachineInstr!"); 443 assert (SuccToSinkTo && "Invalid SinkTo Candidate BB"); 444 445 if (MBB == SuccToSinkTo) 446 return false; 447 448 // It is profitable if SuccToSinkTo does not post dominate current block. 449 if (!isPostDominatedBy(MBB, SuccToSinkTo)) 450 return true; 451 452 // Check if only use in post dominated block is PHI instruction. 453 bool NonPHIUse = false; 454 for (MachineInstr &UseInst : MRI->use_nodbg_instructions(Reg)) { 455 MachineBasicBlock *UseBlock = UseInst.getParent(); 456 if (UseBlock == SuccToSinkTo && !UseInst.isPHI()) 457 NonPHIUse = true; 458 } 459 if (!NonPHIUse) 460 return true; 461 462 // If SuccToSinkTo post dominates then also it may be profitable if MI 463 // can further profitably sinked into another block in next round. 464 bool BreakPHIEdge = false; 465 // FIXME - If finding successor is compile time expensive then catch results. 466 if (MachineBasicBlock *MBB2 = FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge)) 467 return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2); 468 469 // If SuccToSinkTo is final destination and it is a post dominator of current 470 // block then it is not profitable to sink MI into SuccToSinkTo block. 471 return false; 472} 473 474/// FindSuccToSinkTo - Find a successor to sink this instruction to. 475MachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI, 476 MachineBasicBlock *MBB, 477 bool &BreakPHIEdge) { 478 479 assert (MI && "Invalid MachineInstr!"); 480 assert (MBB && "Invalid MachineBasicBlock!"); 481 482 // Loop over all the operands of the specified instruction. If there is 483 // anything we can't handle, bail out. 484 485 // SuccToSinkTo - This is the successor to sink this instruction to, once we 486 // decide. 487 MachineBasicBlock *SuccToSinkTo = 0; 488 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 489 const MachineOperand &MO = MI->getOperand(i); 490 if (!MO.isReg()) continue; // Ignore non-register operands. 491 492 unsigned Reg = MO.getReg(); 493 if (Reg == 0) continue; 494 495 if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 496 if (MO.isUse()) { 497 // If the physreg has no defs anywhere, it's just an ambient register 498 // and we can freely move its uses. Alternatively, if it's allocatable, 499 // it could get allocated to something with a def during allocation. 500 if (!MRI->isConstantPhysReg(Reg, *MBB->getParent())) 501 return NULL; 502 } else if (!MO.isDead()) { 503 // A def that isn't dead. We can't move it. 504 return NULL; 505 } 506 } else { 507 // Virtual register uses are always safe to sink. 508 if (MO.isUse()) continue; 509 510 // If it's not safe to move defs of the register class, then abort. 511 if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg))) 512 return NULL; 513 514 // FIXME: This picks a successor to sink into based on having one 515 // successor that dominates all the uses. However, there are cases where 516 // sinking can happen but where the sink point isn't a successor. For 517 // example: 518 // 519 // x = computation 520 // if () {} else {} 521 // use x 522 // 523 // the instruction could be sunk over the whole diamond for the 524 // if/then/else (or loop, etc), allowing it to be sunk into other blocks 525 // after that. 526 527 // Virtual register defs can only be sunk if all their uses are in blocks 528 // dominated by one of the successors. 529 if (SuccToSinkTo) { 530 // If a previous operand picked a block to sink to, then this operand 531 // must be sinkable to the same block. 532 bool LocalUse = false; 533 if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB, 534 BreakPHIEdge, LocalUse)) 535 return NULL; 536 537 continue; 538 } 539 540 // Otherwise, we should look at all the successors and decide which one 541 // we should sink to. 542 // We give successors with smaller loop depth higher priority. 543 SmallVector<MachineBasicBlock*, 4> Succs(MBB->succ_begin(), MBB->succ_end()); 544 // Sort Successors according to their loop depth. 545 std::stable_sort( 546 Succs.begin(), Succs.end(), 547 [this](const MachineBasicBlock *LHS, const MachineBasicBlock *RHS) { 548 return LI->getLoopDepth(LHS) < LI->getLoopDepth(RHS); 549 }); 550 for (SmallVectorImpl<MachineBasicBlock *>::iterator SI = Succs.begin(), 551 E = Succs.end(); SI != E; ++SI) { 552 MachineBasicBlock *SuccBlock = *SI; 553 bool LocalUse = false; 554 if (AllUsesDominatedByBlock(Reg, SuccBlock, MBB, 555 BreakPHIEdge, LocalUse)) { 556 SuccToSinkTo = SuccBlock; 557 break; 558 } 559 if (LocalUse) 560 // Def is used locally, it's never safe to move this def. 561 return NULL; 562 } 563 564 // If we couldn't find a block to sink to, ignore this instruction. 565 if (SuccToSinkTo == 0) 566 return NULL; 567 else if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo)) 568 return NULL; 569 } 570 } 571 572 // It is not possible to sink an instruction into its own block. This can 573 // happen with loops. 574 if (MBB == SuccToSinkTo) 575 return NULL; 576 577 // It's not safe to sink instructions to EH landing pad. Control flow into 578 // landing pad is implicitly defined. 579 if (SuccToSinkTo && SuccToSinkTo->isLandingPad()) 580 return NULL; 581 582 return SuccToSinkTo; 583} 584 585/// SinkInstruction - Determine whether it is safe to sink the specified machine 586/// instruction out of its current block into a successor. 587bool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { 588 // Don't sink insert_subreg, subreg_to_reg, reg_sequence. These are meant to 589 // be close to the source to make it easier to coalesce. 590 if (AvoidsSinking(MI, MRI)) 591 return false; 592 593 // Check if it's safe to move the instruction. 594 if (!MI->isSafeToMove(TII, AA, SawStore)) 595 return false; 596 597 // FIXME: This should include support for sinking instructions within the 598 // block they are currently in to shorten the live ranges. We often get 599 // instructions sunk into the top of a large block, but it would be better to 600 // also sink them down before their first use in the block. This xform has to 601 // be careful not to *increase* register pressure though, e.g. sinking 602 // "x = y + z" down if it kills y and z would increase the live ranges of y 603 // and z and only shrink the live range of x. 604 605 bool BreakPHIEdge = false; 606 MachineBasicBlock *ParentBlock = MI->getParent(); 607 MachineBasicBlock *SuccToSinkTo = FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge); 608 609 // If there are no outputs, it must have side-effects. 610 if (SuccToSinkTo == 0) 611 return false; 612 613 614 // If the instruction to move defines a dead physical register which is live 615 // when leaving the basic block, don't move it because it could turn into a 616 // "zombie" define of that preg. E.g., EFLAGS. (<rdar://problem/8030636>) 617 for (unsigned I = 0, E = MI->getNumOperands(); I != E; ++I) { 618 const MachineOperand &MO = MI->getOperand(I); 619 if (!MO.isReg()) continue; 620 unsigned Reg = MO.getReg(); 621 if (Reg == 0 || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 622 if (SuccToSinkTo->isLiveIn(Reg)) 623 return false; 624 } 625 626 DEBUG(dbgs() << "Sink instr " << *MI << "\tinto block " << *SuccToSinkTo); 627 628 // If the block has multiple predecessors, this is a critical edge. 629 // Decide if we can sink along it or need to break the edge. 630 if (SuccToSinkTo->pred_size() > 1) { 631 // We cannot sink a load across a critical edge - there may be stores in 632 // other code paths. 633 bool TryBreak = false; 634 bool store = true; 635 if (!MI->isSafeToMove(TII, AA, store)) { 636 DEBUG(dbgs() << " *** NOTE: Won't sink load along critical edge.\n"); 637 TryBreak = true; 638 } 639 640 // We don't want to sink across a critical edge if we don't dominate the 641 // successor. We could be introducing calculations to new code paths. 642 if (!TryBreak && !DT->dominates(ParentBlock, SuccToSinkTo)) { 643 DEBUG(dbgs() << " *** NOTE: Critical edge found\n"); 644 TryBreak = true; 645 } 646 647 // Don't sink instructions into a loop. 648 if (!TryBreak && LI->isLoopHeader(SuccToSinkTo)) { 649 DEBUG(dbgs() << " *** NOTE: Loop header found\n"); 650 TryBreak = true; 651 } 652 653 // Otherwise we are OK with sinking along a critical edge. 654 if (!TryBreak) 655 DEBUG(dbgs() << "Sinking along critical edge.\n"); 656 else { 657 MachineBasicBlock *NewSucc = 658 SplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, BreakPHIEdge); 659 if (!NewSucc) { 660 DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to " 661 "break critical edge\n"); 662 return false; 663 } else { 664 DEBUG(dbgs() << " *** Splitting critical edge:" 665 " BB#" << ParentBlock->getNumber() 666 << " -- BB#" << NewSucc->getNumber() 667 << " -- BB#" << SuccToSinkTo->getNumber() << '\n'); 668 SuccToSinkTo = NewSucc; 669 ++NumSplit; 670 BreakPHIEdge = false; 671 } 672 } 673 } 674 675 if (BreakPHIEdge) { 676 // BreakPHIEdge is true if all the uses are in the successor MBB being 677 // sunken into and they are all PHI nodes. In this case, machine-sink must 678 // break the critical edge first. 679 MachineBasicBlock *NewSucc = SplitCriticalEdge(MI, ParentBlock, 680 SuccToSinkTo, BreakPHIEdge); 681 if (!NewSucc) { 682 DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to " 683 "break critical edge\n"); 684 return false; 685 } 686 687 DEBUG(dbgs() << " *** Splitting critical edge:" 688 " BB#" << ParentBlock->getNumber() 689 << " -- BB#" << NewSucc->getNumber() 690 << " -- BB#" << SuccToSinkTo->getNumber() << '\n'); 691 SuccToSinkTo = NewSucc; 692 ++NumSplit; 693 } 694 695 // Determine where to insert into. Skip phi nodes. 696 MachineBasicBlock::iterator InsertPos = SuccToSinkTo->begin(); 697 while (InsertPos != SuccToSinkTo->end() && InsertPos->isPHI()) 698 ++InsertPos; 699 700 // collect matching debug values. 701 SmallVector<MachineInstr *, 2> DbgValuesToSink; 702 collectDebugValues(MI, DbgValuesToSink); 703 704 // Move the instruction. 705 SuccToSinkTo->splice(InsertPos, ParentBlock, MI, 706 ++MachineBasicBlock::iterator(MI)); 707 708 // Move debug values. 709 for (SmallVectorImpl<MachineInstr *>::iterator DBI = DbgValuesToSink.begin(), 710 DBE = DbgValuesToSink.end(); DBI != DBE; ++DBI) { 711 MachineInstr *DbgMI = *DBI; 712 SuccToSinkTo->splice(InsertPos, ParentBlock, DbgMI, 713 ++MachineBasicBlock::iterator(DbgMI)); 714 } 715 716 // Conservatively, clear any kill flags, since it's possible that they are no 717 // longer correct. 718 MI->clearKillInfo(); 719 720 return true; 721} 722