MachineSink.cpp revision 234353
1193323Sed//===-- MachineSink.cpp - Sinking for machine instructions ----------------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10210299Sed// This pass moves instructions into successor blocks when possible, so that 11198090Srdivacky// they aren't executed on paths where their results aren't needed. 12193323Sed// 13198090Srdivacky// This pass is not intended to be a replacement or a complete alternative 14198090Srdivacky// for an LLVM-IR-level sinking pass. It is only designed to sink simple 15198090Srdivacky// constructs that are not exposed before lowering and instruction selection. 16198090Srdivacky// 17193323Sed//===----------------------------------------------------------------------===// 18193323Sed 19193323Sed#define DEBUG_TYPE "machine-sink" 20193323Sed#include "llvm/CodeGen/Passes.h" 21193323Sed#include "llvm/CodeGen/MachineRegisterInfo.h" 22193323Sed#include "llvm/CodeGen/MachineDominators.h" 23207618Srdivacky#include "llvm/CodeGen/MachineLoopInfo.h" 24198090Srdivacky#include "llvm/Analysis/AliasAnalysis.h" 25193323Sed#include "llvm/Target/TargetRegisterInfo.h" 26193323Sed#include "llvm/Target/TargetInstrInfo.h" 27193323Sed#include "llvm/Target/TargetMachine.h" 28218893Sdim#include "llvm/ADT/SmallSet.h" 29193323Sed#include "llvm/ADT/Statistic.h" 30212904Sdim#include "llvm/Support/CommandLine.h" 31193323Sed#include "llvm/Support/Debug.h" 32198090Srdivacky#include "llvm/Support/raw_ostream.h" 33193323Sedusing namespace llvm; 34193323Sed 35234353Sdimstatic cl::opt<bool> 36212904SdimSplitEdges("machine-sink-split", 37212904Sdim cl::desc("Split critical edges during machine sinking"), 38218893Sdim cl::init(true), cl::Hidden); 39193323Sed 40218893SdimSTATISTIC(NumSunk, "Number of machine instructions sunk"); 41218893SdimSTATISTIC(NumSplit, "Number of critical edges split"); 42218893SdimSTATISTIC(NumCoalesces, "Number of copies coalesced"); 43212904Sdim 44193323Sednamespace { 45198892Srdivacky class MachineSinking : public MachineFunctionPass { 46193323Sed const TargetInstrInfo *TII; 47198090Srdivacky const TargetRegisterInfo *TRI; 48218893Sdim MachineRegisterInfo *MRI; // Machine register information 49198090Srdivacky MachineDominatorTree *DT; // Machine dominator tree 50207618Srdivacky MachineLoopInfo *LI; 51198090Srdivacky AliasAnalysis *AA; 52198090Srdivacky BitVector AllocatableSet; // Which physregs are allocatable? 53193323Sed 54218893Sdim // Remember which edges have been considered for breaking. 55218893Sdim SmallSet<std::pair<MachineBasicBlock*,MachineBasicBlock*>, 8> 56218893Sdim CEBCandidates; 57218893Sdim 58193323Sed public: 59193323Sed static char ID; // Pass identification 60218893Sdim MachineSinking() : MachineFunctionPass(ID) { 61218893Sdim initializeMachineSinkingPass(*PassRegistry::getPassRegistry()); 62218893Sdim } 63210299Sed 64193323Sed virtual bool runOnMachineFunction(MachineFunction &MF); 65210299Sed 66193323Sed virtual void getAnalysisUsage(AnalysisUsage &AU) const { 67198090Srdivacky AU.setPreservesCFG(); 68193323Sed MachineFunctionPass::getAnalysisUsage(AU); 69198090Srdivacky AU.addRequired<AliasAnalysis>(); 70193323Sed AU.addRequired<MachineDominatorTree>(); 71207618Srdivacky AU.addRequired<MachineLoopInfo>(); 72193323Sed AU.addPreserved<MachineDominatorTree>(); 73207618Srdivacky AU.addPreserved<MachineLoopInfo>(); 74193323Sed } 75218893Sdim 76218893Sdim virtual void releaseMemory() { 77218893Sdim CEBCandidates.clear(); 78218893Sdim } 79218893Sdim 80193323Sed private: 81193323Sed bool ProcessBlock(MachineBasicBlock &MBB); 82218893Sdim bool isWorthBreakingCriticalEdge(MachineInstr *MI, 83218893Sdim MachineBasicBlock *From, 84218893Sdim MachineBasicBlock *To); 85218893Sdim MachineBasicBlock *SplitCriticalEdge(MachineInstr *MI, 86218893Sdim MachineBasicBlock *From, 87218893Sdim MachineBasicBlock *To, 88218893Sdim bool BreakPHIEdge); 89193323Sed bool SinkInstruction(MachineInstr *MI, bool &SawStore); 90212904Sdim bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB, 91218893Sdim MachineBasicBlock *DefMBB, 92218893Sdim bool &BreakPHIEdge, bool &LocalUse) const; 93234353Sdim MachineBasicBlock *FindSuccToSinkTo(MachineInstr *MI, MachineBasicBlock *MBB, 94234353Sdim bool &BreakPHIEdge); 95234353Sdim bool isProfitableToSinkTo(unsigned Reg, MachineInstr *MI, 96234353Sdim MachineBasicBlock *MBB, 97234353Sdim MachineBasicBlock *SuccToSinkTo); 98234353Sdim 99218893Sdim bool PerformTrivialForwardCoalescing(MachineInstr *MI, 100218893Sdim MachineBasicBlock *MBB); 101193323Sed }; 102193323Sed} // end anonymous namespace 103210299Sed 104193323Sedchar MachineSinking::ID = 0; 105234353Sdimchar &llvm::MachineSinkingID = MachineSinking::ID; 106218893SdimINITIALIZE_PASS_BEGIN(MachineSinking, "machine-sink", 107218893Sdim "Machine code sinking", false, false) 108218893SdimINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 109218893SdimINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 110218893SdimINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 111218893SdimINITIALIZE_PASS_END(MachineSinking, "machine-sink", 112218893Sdim "Machine code sinking", false, false) 113193323Sed 114218893Sdimbool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr *MI, 115218893Sdim MachineBasicBlock *MBB) { 116218893Sdim if (!MI->isCopy()) 117218893Sdim return false; 118218893Sdim 119218893Sdim unsigned SrcReg = MI->getOperand(1).getReg(); 120218893Sdim unsigned DstReg = MI->getOperand(0).getReg(); 121218893Sdim if (!TargetRegisterInfo::isVirtualRegister(SrcReg) || 122218893Sdim !TargetRegisterInfo::isVirtualRegister(DstReg) || 123218893Sdim !MRI->hasOneNonDBGUse(SrcReg)) 124218893Sdim return false; 125218893Sdim 126218893Sdim const TargetRegisterClass *SRC = MRI->getRegClass(SrcReg); 127218893Sdim const TargetRegisterClass *DRC = MRI->getRegClass(DstReg); 128218893Sdim if (SRC != DRC) 129218893Sdim return false; 130218893Sdim 131218893Sdim MachineInstr *DefMI = MRI->getVRegDef(SrcReg); 132218893Sdim if (DefMI->isCopyLike()) 133218893Sdim return false; 134218893Sdim DEBUG(dbgs() << "Coalescing: " << *DefMI); 135218893Sdim DEBUG(dbgs() << "*** to: " << *MI); 136218893Sdim MRI->replaceRegWith(DstReg, SrcReg); 137218893Sdim MI->eraseFromParent(); 138218893Sdim ++NumCoalesces; 139218893Sdim return true; 140218893Sdim} 141218893Sdim 142193323Sed/// AllUsesDominatedByBlock - Return true if all uses of the specified register 143212904Sdim/// occur in blocks dominated by the specified block. If any use is in the 144212904Sdim/// definition block, then return false since it is never legal to move def 145212904Sdim/// after uses. 146218893Sdimbool 147218893SdimMachineSinking::AllUsesDominatedByBlock(unsigned Reg, 148218893Sdim MachineBasicBlock *MBB, 149218893Sdim MachineBasicBlock *DefMBB, 150218893Sdim bool &BreakPHIEdge, 151218893Sdim bool &LocalUse) const { 152193323Sed assert(TargetRegisterInfo::isVirtualRegister(Reg) && 153193323Sed "Only makes sense for vregs"); 154218893Sdim 155234353Sdim // Ignore debug uses because debug info doesn't affect the code. 156218893Sdim if (MRI->use_nodbg_empty(Reg)) 157218893Sdim return true; 158218893Sdim 159218893Sdim // BreakPHIEdge is true if all the uses are in the successor MBB being sunken 160218893Sdim // into and they are all PHI nodes. In this case, machine-sink must break 161218893Sdim // the critical edge first. e.g. 162218893Sdim // 163218893Sdim // BB#1: derived from LLVM BB %bb4.preheader 164218893Sdim // Predecessors according to CFG: BB#0 165218893Sdim // ... 166218893Sdim // %reg16385<def> = DEC64_32r %reg16437, %EFLAGS<imp-def,dead> 167218893Sdim // ... 168218893Sdim // JE_4 <BB#37>, %EFLAGS<imp-use> 169218893Sdim // Successors according to CFG: BB#37 BB#2 170218893Sdim // 171218893Sdim // BB#2: derived from LLVM BB %bb.nph 172218893Sdim // Predecessors according to CFG: BB#0 BB#1 173218893Sdim // %reg16386<def> = PHI %reg16434, <BB#0>, %reg16385, <BB#1> 174218893Sdim BreakPHIEdge = true; 175210299Sed for (MachineRegisterInfo::use_nodbg_iterator 176218893Sdim I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end(); 177210299Sed I != E; ++I) { 178218893Sdim MachineInstr *UseInst = &*I; 179218893Sdim MachineBasicBlock *UseBlock = UseInst->getParent(); 180218893Sdim if (!(UseBlock == MBB && UseInst->isPHI() && 181218893Sdim UseInst->getOperand(I.getOperandNo()+1).getMBB() == DefMBB)) { 182218893Sdim BreakPHIEdge = false; 183218893Sdim break; 184218893Sdim } 185218893Sdim } 186218893Sdim if (BreakPHIEdge) 187218893Sdim return true; 188218893Sdim 189218893Sdim for (MachineRegisterInfo::use_nodbg_iterator 190218893Sdim I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end(); 191218893Sdim I != E; ++I) { 192193323Sed // Determine the block of the use. 193193323Sed MachineInstr *UseInst = &*I; 194193323Sed MachineBasicBlock *UseBlock = UseInst->getParent(); 195203954Srdivacky if (UseInst->isPHI()) { 196193323Sed // PHI nodes use the operand in the predecessor block, not the block with 197193323Sed // the PHI. 198193323Sed UseBlock = UseInst->getOperand(I.getOperandNo()+1).getMBB(); 199212904Sdim } else if (UseBlock == DefMBB) { 200212904Sdim LocalUse = true; 201212904Sdim return false; 202193323Sed } 203210299Sed 204193323Sed // Check that it dominates. 205193323Sed if (!DT->dominates(MBB, UseBlock)) 206193323Sed return false; 207193323Sed } 208210299Sed 209193323Sed return true; 210193323Sed} 211193323Sed 212193323Sedbool MachineSinking::runOnMachineFunction(MachineFunction &MF) { 213202375Srdivacky DEBUG(dbgs() << "******** Machine Sinking ********\n"); 214210299Sed 215198396Srdivacky const TargetMachine &TM = MF.getTarget(); 216198396Srdivacky TII = TM.getInstrInfo(); 217198396Srdivacky TRI = TM.getRegisterInfo(); 218218893Sdim MRI = &MF.getRegInfo(); 219193323Sed DT = &getAnalysis<MachineDominatorTree>(); 220207618Srdivacky LI = &getAnalysis<MachineLoopInfo>(); 221198090Srdivacky AA = &getAnalysis<AliasAnalysis>(); 222198396Srdivacky AllocatableSet = TRI->getAllocatableSet(MF); 223193323Sed 224193323Sed bool EverMadeChange = false; 225210299Sed 226193323Sed while (1) { 227193323Sed bool MadeChange = false; 228193323Sed 229193323Sed // Process all basic blocks. 230218893Sdim CEBCandidates.clear(); 231210299Sed for (MachineFunction::iterator I = MF.begin(), E = MF.end(); 232193323Sed I != E; ++I) 233193323Sed MadeChange |= ProcessBlock(*I); 234210299Sed 235193323Sed // If this iteration over the code changed anything, keep iterating. 236193323Sed if (!MadeChange) break; 237193323Sed EverMadeChange = true; 238210299Sed } 239193323Sed return EverMadeChange; 240193323Sed} 241193323Sed 242193323Sedbool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) { 243193323Sed // Can't sink anything out of a block that has less than two successors. 244193323Sed if (MBB.succ_size() <= 1 || MBB.empty()) return false; 245193323Sed 246206274Srdivacky // Don't bother sinking code out of unreachable blocks. In addition to being 247210299Sed // unprofitable, it can also lead to infinite looping, because in an 248210299Sed // unreachable loop there may be nowhere to stop. 249206274Srdivacky if (!DT->isReachableFromEntry(&MBB)) return false; 250206274Srdivacky 251193323Sed bool MadeChange = false; 252193323Sed 253193323Sed // Walk the basic block bottom-up. Remember if we saw a store. 254193323Sed MachineBasicBlock::iterator I = MBB.end(); 255193323Sed --I; 256193323Sed bool ProcessedBegin, SawStore = false; 257193323Sed do { 258193323Sed MachineInstr *MI = I; // The instruction to sink. 259210299Sed 260193323Sed // Predecrement I (if it's not begin) so that it isn't invalidated by 261193323Sed // sinking. 262193323Sed ProcessedBegin = I == MBB.begin(); 263193323Sed if (!ProcessedBegin) 264193323Sed --I; 265204792Srdivacky 266204792Srdivacky if (MI->isDebugValue()) 267204792Srdivacky continue; 268204792Srdivacky 269221345Sdim bool Joined = PerformTrivialForwardCoalescing(MI, &MBB); 270221345Sdim if (Joined) { 271221345Sdim MadeChange = true; 272218893Sdim continue; 273221345Sdim } 274218893Sdim 275193323Sed if (SinkInstruction(MI, SawStore)) 276193323Sed ++NumSunk, MadeChange = true; 277210299Sed 278193323Sed // If we just processed the first instruction in the block, we're done. 279193323Sed } while (!ProcessedBegin); 280210299Sed 281193323Sed return MadeChange; 282193323Sed} 283193323Sed 284218893Sdimbool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr *MI, 285218893Sdim MachineBasicBlock *From, 286218893Sdim MachineBasicBlock *To) { 287218893Sdim // FIXME: Need much better heuristics. 288218893Sdim 289218893Sdim // If the pass has already considered breaking this edge (during this pass 290218893Sdim // through the function), then let's go ahead and break it. This means 291218893Sdim // sinking multiple "cheap" instructions into the same block. 292218893Sdim if (!CEBCandidates.insert(std::make_pair(From, To))) 293218893Sdim return true; 294218893Sdim 295234353Sdim if (!MI->isCopy() && !MI->isAsCheapAsAMove()) 296218893Sdim return true; 297218893Sdim 298218893Sdim // MI is cheap, we probably don't want to break the critical edge for it. 299218893Sdim // However, if this would allow some definitions of its source operands 300218893Sdim // to be sunk then it's probably worth it. 301218893Sdim for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 302218893Sdim const MachineOperand &MO = MI->getOperand(i); 303218893Sdim if (!MO.isReg()) continue; 304218893Sdim unsigned Reg = MO.getReg(); 305218893Sdim if (Reg == 0 || !TargetRegisterInfo::isPhysicalRegister(Reg)) 306218893Sdim continue; 307218893Sdim if (MRI->hasOneNonDBGUse(Reg)) 308218893Sdim return true; 309218893Sdim } 310218893Sdim 311218893Sdim return false; 312218893Sdim} 313218893Sdim 314218893SdimMachineBasicBlock *MachineSinking::SplitCriticalEdge(MachineInstr *MI, 315218893Sdim MachineBasicBlock *FromBB, 316218893Sdim MachineBasicBlock *ToBB, 317218893Sdim bool BreakPHIEdge) { 318218893Sdim if (!isWorthBreakingCriticalEdge(MI, FromBB, ToBB)) 319218893Sdim return 0; 320218893Sdim 321212904Sdim // Avoid breaking back edge. From == To means backedge for single BB loop. 322218893Sdim if (!SplitEdges || FromBB == ToBB) 323212904Sdim return 0; 324212904Sdim 325218893Sdim // Check for backedges of more "complex" loops. 326218893Sdim if (LI->getLoopFor(FromBB) == LI->getLoopFor(ToBB) && 327218893Sdim LI->isLoopHeader(ToBB)) 328218893Sdim return 0; 329218893Sdim 330218893Sdim // It's not always legal to break critical edges and sink the computation 331218893Sdim // to the edge. 332218893Sdim // 333218893Sdim // BB#1: 334218893Sdim // v1024 335218893Sdim // Beq BB#3 336218893Sdim // <fallthrough> 337218893Sdim // BB#2: 338218893Sdim // ... no uses of v1024 339218893Sdim // <fallthrough> 340218893Sdim // BB#3: 341218893Sdim // ... 342218893Sdim // = v1024 343218893Sdim // 344218893Sdim // If BB#1 -> BB#3 edge is broken and computation of v1024 is inserted: 345218893Sdim // 346218893Sdim // BB#1: 347218893Sdim // ... 348218893Sdim // Bne BB#2 349218893Sdim // BB#4: 350218893Sdim // v1024 = 351218893Sdim // B BB#3 352218893Sdim // BB#2: 353218893Sdim // ... no uses of v1024 354218893Sdim // <fallthrough> 355218893Sdim // BB#3: 356218893Sdim // ... 357218893Sdim // = v1024 358218893Sdim // 359218893Sdim // This is incorrect since v1024 is not computed along the BB#1->BB#2->BB#3 360218893Sdim // flow. We need to ensure the new basic block where the computation is 361218893Sdim // sunk to dominates all the uses. 362218893Sdim // It's only legal to break critical edge and sink the computation to the 363218893Sdim // new block if all the predecessors of "To", except for "From", are 364218893Sdim // not dominated by "From". Given SSA property, this means these 365218893Sdim // predecessors are dominated by "To". 366218893Sdim // 367218893Sdim // There is no need to do this check if all the uses are PHI nodes. PHI 368218893Sdim // sources are only defined on the specific predecessor edges. 369218893Sdim if (!BreakPHIEdge) { 370212904Sdim for (MachineBasicBlock::pred_iterator PI = ToBB->pred_begin(), 371212904Sdim E = ToBB->pred_end(); PI != E; ++PI) { 372212904Sdim if (*PI == FromBB) 373212904Sdim continue; 374212904Sdim if (!DT->dominates(ToBB, *PI)) 375212904Sdim return 0; 376212904Sdim } 377212904Sdim } 378212904Sdim 379218893Sdim return FromBB->SplitCriticalEdge(ToBB, this); 380212904Sdim} 381212904Sdim 382218893Sdimstatic bool AvoidsSinking(MachineInstr *MI, MachineRegisterInfo *MRI) { 383218893Sdim return MI->isInsertSubreg() || MI->isSubregToReg() || MI->isRegSequence(); 384218893Sdim} 385218893Sdim 386234353Sdim/// collectDebgValues - Scan instructions following MI and collect any 387226633Sdim/// matching DBG_VALUEs. 388234353Sdimstatic void collectDebugValues(MachineInstr *MI, 389226633Sdim SmallVector<MachineInstr *, 2> & DbgValues) { 390226633Sdim DbgValues.clear(); 391226633Sdim if (!MI->getOperand(0).isReg()) 392226633Sdim return; 393226633Sdim 394226633Sdim MachineBasicBlock::iterator DI = MI; ++DI; 395226633Sdim for (MachineBasicBlock::iterator DE = MI->getParent()->end(); 396226633Sdim DI != DE; ++DI) { 397226633Sdim if (!DI->isDebugValue()) 398226633Sdim return; 399226633Sdim if (DI->getOperand(0).isReg() && 400226633Sdim DI->getOperand(0).getReg() == MI->getOperand(0).getReg()) 401226633Sdim DbgValues.push_back(DI); 402226633Sdim } 403226633Sdim} 404226633Sdim 405234353Sdim/// isPostDominatedBy - Return true if A is post dominated by B. 406234353Sdimstatic bool isPostDominatedBy(MachineBasicBlock *A, MachineBasicBlock *B) { 407234353Sdim 408234353Sdim // FIXME - Use real post dominator. 409234353Sdim if (A->succ_size() != 2) 410218893Sdim return false; 411234353Sdim MachineBasicBlock::succ_iterator I = A->succ_begin(); 412234353Sdim if (B == *I) 413234353Sdim ++I; 414234353Sdim MachineBasicBlock *OtherSuccBlock = *I; 415234353Sdim if (OtherSuccBlock->succ_size() != 1 || 416234353Sdim *(OtherSuccBlock->succ_begin()) != B) 417234353Sdim return false; 418218893Sdim 419234353Sdim return true; 420234353Sdim} 421234353Sdim 422234353Sdim/// isProfitableToSinkTo - Return true if it is profitable to sink MI. 423234353Sdimbool MachineSinking::isProfitableToSinkTo(unsigned Reg, MachineInstr *MI, 424234353Sdim MachineBasicBlock *MBB, 425234353Sdim MachineBasicBlock *SuccToSinkTo) { 426234353Sdim assert (MI && "Invalid MachineInstr!"); 427234353Sdim assert (SuccToSinkTo && "Invalid SinkTo Candidate BB"); 428234353Sdim 429234353Sdim if (MBB == SuccToSinkTo) 430193323Sed return false; 431210299Sed 432234353Sdim // It is profitable if SuccToSinkTo does not post dominate current block. 433234353Sdim if (!isPostDominatedBy(MBB, SuccToSinkTo)) 434234353Sdim return true; 435210299Sed 436234353Sdim // Check if only use in post dominated block is PHI instruction. 437234353Sdim bool NonPHIUse = false; 438234353Sdim for (MachineRegisterInfo::use_nodbg_iterator 439234353Sdim I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end(); 440234353Sdim I != E; ++I) { 441234353Sdim MachineInstr *UseInst = &*I; 442234353Sdim MachineBasicBlock *UseBlock = UseInst->getParent(); 443234353Sdim if (UseBlock == SuccToSinkTo && !UseInst->isPHI()) 444234353Sdim NonPHIUse = true; 445234353Sdim } 446234353Sdim if (!NonPHIUse) 447234353Sdim return true; 448234353Sdim 449234353Sdim // If SuccToSinkTo post dominates then also it may be profitable if MI 450234353Sdim // can further profitably sinked into another block in next round. 451234353Sdim bool BreakPHIEdge = false; 452234353Sdim // FIXME - If finding successor is compile time expensive then catch results. 453234353Sdim if (MachineBasicBlock *MBB2 = FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge)) 454234353Sdim return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2); 455234353Sdim 456234353Sdim // If SuccToSinkTo is final destination and it is a post dominator of current 457234353Sdim // block then it is not profitable to sink MI into SuccToSinkTo block. 458234353Sdim return false; 459234353Sdim} 460234353Sdim 461234353Sdim/// FindSuccToSinkTo - Find a successor to sink this instruction to. 462234353SdimMachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI, 463234353Sdim MachineBasicBlock *MBB, 464234353Sdim bool &BreakPHIEdge) { 465234353Sdim 466234353Sdim assert (MI && "Invalid MachineInstr!"); 467234353Sdim assert (MBB && "Invalid MachineBasicBlock!"); 468234353Sdim 469193323Sed // Loop over all the operands of the specified instruction. If there is 470193323Sed // anything we can't handle, bail out. 471210299Sed 472193323Sed // SuccToSinkTo - This is the successor to sink this instruction to, once we 473193323Sed // decide. 474193323Sed MachineBasicBlock *SuccToSinkTo = 0; 475193323Sed for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 476193323Sed const MachineOperand &MO = MI->getOperand(i); 477193323Sed if (!MO.isReg()) continue; // Ignore non-register operands. 478210299Sed 479193323Sed unsigned Reg = MO.getReg(); 480193323Sed if (Reg == 0) continue; 481210299Sed 482193323Sed if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 483198090Srdivacky if (MO.isUse()) { 484198090Srdivacky // If the physreg has no defs anywhere, it's just an ambient register 485198090Srdivacky // and we can freely move its uses. Alternatively, if it's allocatable, 486198090Srdivacky // it could get allocated to something with a def during allocation. 487234353Sdim if (!MRI->isConstantPhysReg(Reg, *MBB->getParent())) 488234353Sdim return NULL; 489198090Srdivacky } else if (!MO.isDead()) { 490198090Srdivacky // A def that isn't dead. We can't move it. 491234353Sdim return NULL; 492198090Srdivacky } 493193323Sed } else { 494193323Sed // Virtual register uses are always safe to sink. 495193323Sed if (MO.isUse()) continue; 496193323Sed 497193323Sed // If it's not safe to move defs of the register class, then abort. 498218893Sdim if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg))) 499234353Sdim return NULL; 500210299Sed 501193323Sed // FIXME: This picks a successor to sink into based on having one 502193323Sed // successor that dominates all the uses. However, there are cases where 503193323Sed // sinking can happen but where the sink point isn't a successor. For 504193323Sed // example: 505210299Sed // 506193323Sed // x = computation 507193323Sed // if () {} else {} 508193323Sed // use x 509210299Sed // 510210299Sed // the instruction could be sunk over the whole diamond for the 511193323Sed // if/then/else (or loop, etc), allowing it to be sunk into other blocks 512193323Sed // after that. 513210299Sed 514193323Sed // Virtual register defs can only be sunk if all their uses are in blocks 515193323Sed // dominated by one of the successors. 516193323Sed if (SuccToSinkTo) { 517193323Sed // If a previous operand picked a block to sink to, then this operand 518193323Sed // must be sinkable to the same block. 519212904Sdim bool LocalUse = false; 520234353Sdim if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB, 521218893Sdim BreakPHIEdge, LocalUse)) 522234353Sdim return NULL; 523210299Sed 524193323Sed continue; 525193323Sed } 526210299Sed 527193323Sed // Otherwise, we should look at all the successors and decide which one 528193323Sed // we should sink to. 529234353Sdim for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), 530234353Sdim E = MBB->succ_end(); SI != E; ++SI) { 531234353Sdim MachineBasicBlock *SuccBlock = *SI; 532212904Sdim bool LocalUse = false; 533234353Sdim if (AllUsesDominatedByBlock(Reg, SuccBlock, MBB, 534218893Sdim BreakPHIEdge, LocalUse)) { 535234353Sdim SuccToSinkTo = SuccBlock; 536193323Sed break; 537193323Sed } 538212904Sdim if (LocalUse) 539212904Sdim // Def is used locally, it's never safe to move this def. 540234353Sdim return NULL; 541193323Sed } 542210299Sed 543193323Sed // If we couldn't find a block to sink to, ignore this instruction. 544193323Sed if (SuccToSinkTo == 0) 545234353Sdim return NULL; 546234353Sdim else if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo)) 547234353Sdim return NULL; 548193323Sed } 549193323Sed } 550210299Sed 551234353Sdim // It is not possible to sink an instruction into its own block. This can 552234353Sdim // happen with loops. 553234353Sdim if (MBB == SuccToSinkTo) 554234353Sdim return NULL; 555193323Sed 556193323Sed // It's not safe to sink instructions to EH landing pad. Control flow into 557193323Sed // landing pad is implicitly defined. 558234353Sdim if (SuccToSinkTo && SuccToSinkTo->isLandingPad()) 559234353Sdim return NULL; 560234353Sdim 561234353Sdim return SuccToSinkTo; 562234353Sdim} 563234353Sdim 564234353Sdim/// SinkInstruction - Determine whether it is safe to sink the specified machine 565234353Sdim/// instruction out of its current block into a successor. 566234353Sdimbool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { 567234353Sdim // Don't sink insert_subreg, subreg_to_reg, reg_sequence. These are meant to 568234353Sdim // be close to the source to make it easier to coalesce. 569234353Sdim if (AvoidsSinking(MI, MRI)) 570193323Sed return false; 571210299Sed 572234353Sdim // Check if it's safe to move the instruction. 573234353Sdim if (!MI->isSafeToMove(TII, AA, SawStore)) 574193323Sed return false; 575210299Sed 576234353Sdim // FIXME: This should include support for sinking instructions within the 577234353Sdim // block they are currently in to shorten the live ranges. We often get 578234353Sdim // instructions sunk into the top of a large block, but it would be better to 579234353Sdim // also sink them down before their first use in the block. This xform has to 580234353Sdim // be careful not to *increase* register pressure though, e.g. sinking 581234353Sdim // "x = y + z" down if it kills y and z would increase the live ranges of y 582234353Sdim // and z and only shrink the live range of x. 583234353Sdim 584234353Sdim bool BreakPHIEdge = false; 585234353Sdim MachineBasicBlock *ParentBlock = MI->getParent(); 586234353Sdim MachineBasicBlock *SuccToSinkTo = FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge); 587234353Sdim 588234353Sdim // If there are no outputs, it must have side-effects. 589234353Sdim if (SuccToSinkTo == 0) 590234353Sdim return false; 591234353Sdim 592234353Sdim 593210299Sed // If the instruction to move defines a dead physical register which is live 594210299Sed // when leaving the basic block, don't move it because it could turn into a 595210299Sed // "zombie" define of that preg. E.g., EFLAGS. (<rdar://problem/8030636>) 596210299Sed for (unsigned I = 0, E = MI->getNumOperands(); I != E; ++I) { 597210299Sed const MachineOperand &MO = MI->getOperand(I); 598210299Sed if (!MO.isReg()) continue; 599210299Sed unsigned Reg = MO.getReg(); 600210299Sed if (Reg == 0 || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 601210299Sed if (SuccToSinkTo->isLiveIn(Reg)) 602210299Sed return false; 603210299Sed } 604210299Sed 605210299Sed DEBUG(dbgs() << "Sink instr " << *MI << "\tinto block " << *SuccToSinkTo); 606210299Sed 607193323Sed // If the block has multiple predecessors, this would introduce computation on 608193323Sed // a path that it doesn't already exist. We could split the critical edge, 609193323Sed // but for now we just punt. 610193323Sed if (SuccToSinkTo->pred_size() > 1) { 611207618Srdivacky // We cannot sink a load across a critical edge - there may be stores in 612207618Srdivacky // other code paths. 613212904Sdim bool TryBreak = false; 614207618Srdivacky bool store = true; 615207618Srdivacky if (!MI->isSafeToMove(TII, AA, store)) { 616212904Sdim DEBUG(dbgs() << " *** NOTE: Won't sink load along critical edge.\n"); 617212904Sdim TryBreak = true; 618207618Srdivacky } 619207618Srdivacky 620207618Srdivacky // We don't want to sink across a critical edge if we don't dominate the 621207618Srdivacky // successor. We could be introducing calculations to new code paths. 622212904Sdim if (!TryBreak && !DT->dominates(ParentBlock, SuccToSinkTo)) { 623212904Sdim DEBUG(dbgs() << " *** NOTE: Critical edge found\n"); 624212904Sdim TryBreak = true; 625207618Srdivacky } 626207618Srdivacky 627207618Srdivacky // Don't sink instructions into a loop. 628212904Sdim if (!TryBreak && LI->isLoopHeader(SuccToSinkTo)) { 629212904Sdim DEBUG(dbgs() << " *** NOTE: Loop header found\n"); 630212904Sdim TryBreak = true; 631207618Srdivacky } 632207618Srdivacky 633207618Srdivacky // Otherwise we are OK with sinking along a critical edge. 634212904Sdim if (!TryBreak) 635212904Sdim DEBUG(dbgs() << "Sinking along critical edge.\n"); 636212904Sdim else { 637218893Sdim MachineBasicBlock *NewSucc = 638218893Sdim SplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, BreakPHIEdge); 639212904Sdim if (!NewSucc) { 640218893Sdim DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to " 641218893Sdim "break critical edge\n"); 642212904Sdim return false; 643212904Sdim } else { 644212904Sdim DEBUG(dbgs() << " *** Splitting critical edge:" 645212904Sdim " BB#" << ParentBlock->getNumber() 646212904Sdim << " -- BB#" << NewSucc->getNumber() 647212904Sdim << " -- BB#" << SuccToSinkTo->getNumber() << '\n'); 648212904Sdim SuccToSinkTo = NewSucc; 649212904Sdim ++NumSplit; 650218893Sdim BreakPHIEdge = false; 651212904Sdim } 652212904Sdim } 653193323Sed } 654210299Sed 655218893Sdim if (BreakPHIEdge) { 656218893Sdim // BreakPHIEdge is true if all the uses are in the successor MBB being 657218893Sdim // sunken into and they are all PHI nodes. In this case, machine-sink must 658218893Sdim // break the critical edge first. 659218893Sdim MachineBasicBlock *NewSucc = SplitCriticalEdge(MI, ParentBlock, 660218893Sdim SuccToSinkTo, BreakPHIEdge); 661218893Sdim if (!NewSucc) { 662218893Sdim DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to " 663218893Sdim "break critical edge\n"); 664218893Sdim return false; 665218893Sdim } 666218893Sdim 667218893Sdim DEBUG(dbgs() << " *** Splitting critical edge:" 668218893Sdim " BB#" << ParentBlock->getNumber() 669218893Sdim << " -- BB#" << NewSucc->getNumber() 670218893Sdim << " -- BB#" << SuccToSinkTo->getNumber() << '\n'); 671218893Sdim SuccToSinkTo = NewSucc; 672218893Sdim ++NumSplit; 673218893Sdim } 674218893Sdim 675210299Sed // Determine where to insert into. Skip phi nodes. 676193323Sed MachineBasicBlock::iterator InsertPos = SuccToSinkTo->begin(); 677203954Srdivacky while (InsertPos != SuccToSinkTo->end() && InsertPos->isPHI()) 678193323Sed ++InsertPos; 679210299Sed 680226633Sdim // collect matching debug values. 681226633Sdim SmallVector<MachineInstr *, 2> DbgValuesToSink; 682226633Sdim collectDebugValues(MI, DbgValuesToSink); 683226633Sdim 684193323Sed // Move the instruction. 685193323Sed SuccToSinkTo->splice(InsertPos, ParentBlock, MI, 686193323Sed ++MachineBasicBlock::iterator(MI)); 687208599Srdivacky 688226633Sdim // Move debug values. 689226633Sdim for (SmallVector<MachineInstr *, 2>::iterator DBI = DbgValuesToSink.begin(), 690226633Sdim DBE = DbgValuesToSink.end(); DBI != DBE; ++DBI) { 691226633Sdim MachineInstr *DbgMI = *DBI; 692226633Sdim SuccToSinkTo->splice(InsertPos, ParentBlock, DbgMI, 693226633Sdim ++MachineBasicBlock::iterator(DbgMI)); 694226633Sdim } 695226633Sdim 696210299Sed // Conservatively, clear any kill flags, since it's possible that they are no 697210299Sed // longer correct. 698208599Srdivacky MI->clearKillInfo(); 699208599Srdivacky 700193323Sed return true; 701193323Sed} 702