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