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" 21249423Sdim#include "llvm/ADT/SmallSet.h" 22249423Sdim#include "llvm/ADT/Statistic.h" 23249423Sdim#include "llvm/Analysis/AliasAnalysis.h" 24193323Sed#include "llvm/CodeGen/MachineDominators.h" 25207618Srdivacky#include "llvm/CodeGen/MachineLoopInfo.h" 26249423Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 27212904Sdim#include "llvm/Support/CommandLine.h" 28193323Sed#include "llvm/Support/Debug.h" 29198090Srdivacky#include "llvm/Support/raw_ostream.h" 30249423Sdim#include "llvm/Target/TargetInstrInfo.h" 31249423Sdim#include "llvm/Target/TargetMachine.h" 32249423Sdim#include "llvm/Target/TargetRegisterInfo.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; 52193323Sed 53218893Sdim // Remember which edges have been considered for breaking. 54218893Sdim SmallSet<std::pair<MachineBasicBlock*,MachineBasicBlock*>, 8> 55218893Sdim CEBCandidates; 56218893Sdim 57193323Sed public: 58193323Sed static char ID; // Pass identification 59218893Sdim MachineSinking() : MachineFunctionPass(ID) { 60218893Sdim initializeMachineSinkingPass(*PassRegistry::getPassRegistry()); 61218893Sdim } 62210299Sed 63193323Sed virtual bool runOnMachineFunction(MachineFunction &MF); 64210299Sed 65193323Sed virtual void getAnalysisUsage(AnalysisUsage &AU) const { 66198090Srdivacky AU.setPreservesCFG(); 67193323Sed MachineFunctionPass::getAnalysisUsage(AU); 68198090Srdivacky AU.addRequired<AliasAnalysis>(); 69193323Sed AU.addRequired<MachineDominatorTree>(); 70207618Srdivacky AU.addRequired<MachineLoopInfo>(); 71193323Sed AU.addPreserved<MachineDominatorTree>(); 72207618Srdivacky AU.addPreserved<MachineLoopInfo>(); 73193323Sed } 74218893Sdim 75218893Sdim virtual void releaseMemory() { 76218893Sdim CEBCandidates.clear(); 77218893Sdim } 78218893Sdim 79193323Sed private: 80193323Sed bool ProcessBlock(MachineBasicBlock &MBB); 81218893Sdim bool isWorthBreakingCriticalEdge(MachineInstr *MI, 82218893Sdim MachineBasicBlock *From, 83218893Sdim MachineBasicBlock *To); 84218893Sdim MachineBasicBlock *SplitCriticalEdge(MachineInstr *MI, 85218893Sdim MachineBasicBlock *From, 86218893Sdim MachineBasicBlock *To, 87218893Sdim bool BreakPHIEdge); 88193323Sed bool SinkInstruction(MachineInstr *MI, bool &SawStore); 89212904Sdim bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB, 90218893Sdim MachineBasicBlock *DefMBB, 91218893Sdim bool &BreakPHIEdge, bool &LocalUse) const; 92234353Sdim MachineBasicBlock *FindSuccToSinkTo(MachineInstr *MI, MachineBasicBlock *MBB, 93234353Sdim bool &BreakPHIEdge); 94234353Sdim bool isProfitableToSinkTo(unsigned Reg, MachineInstr *MI, 95234353Sdim MachineBasicBlock *MBB, 96234353Sdim MachineBasicBlock *SuccToSinkTo); 97234353Sdim 98218893Sdim bool PerformTrivialForwardCoalescing(MachineInstr *MI, 99218893Sdim MachineBasicBlock *MBB); 100193323Sed }; 101239462Sdim 102239462Sdim // SuccessorSorter - Sort Successors according to their loop depth. 103239462Sdim struct SuccessorSorter { 104239462Sdim SuccessorSorter(MachineLoopInfo *LoopInfo) : LI(LoopInfo) {} 105239462Sdim bool operator()(const MachineBasicBlock *LHS, 106239462Sdim const MachineBasicBlock *RHS) const { 107239462Sdim return LI->getLoopDepth(LHS) < LI->getLoopDepth(RHS); 108239462Sdim } 109239462Sdim MachineLoopInfo *LI; 110239462Sdim }; 111193323Sed} // end anonymous namespace 112210299Sed 113193323Sedchar MachineSinking::ID = 0; 114234353Sdimchar &llvm::MachineSinkingID = MachineSinking::ID; 115218893SdimINITIALIZE_PASS_BEGIN(MachineSinking, "machine-sink", 116218893Sdim "Machine code sinking", false, false) 117218893SdimINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 118218893SdimINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 119218893SdimINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 120218893SdimINITIALIZE_PASS_END(MachineSinking, "machine-sink", 121218893Sdim "Machine code sinking", false, false) 122193323Sed 123218893Sdimbool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr *MI, 124218893Sdim MachineBasicBlock *MBB) { 125218893Sdim if (!MI->isCopy()) 126218893Sdim return false; 127218893Sdim 128218893Sdim unsigned SrcReg = MI->getOperand(1).getReg(); 129218893Sdim unsigned DstReg = MI->getOperand(0).getReg(); 130218893Sdim if (!TargetRegisterInfo::isVirtualRegister(SrcReg) || 131218893Sdim !TargetRegisterInfo::isVirtualRegister(DstReg) || 132218893Sdim !MRI->hasOneNonDBGUse(SrcReg)) 133218893Sdim return false; 134218893Sdim 135218893Sdim const TargetRegisterClass *SRC = MRI->getRegClass(SrcReg); 136218893Sdim const TargetRegisterClass *DRC = MRI->getRegClass(DstReg); 137218893Sdim if (SRC != DRC) 138218893Sdim return false; 139218893Sdim 140218893Sdim MachineInstr *DefMI = MRI->getVRegDef(SrcReg); 141218893Sdim if (DefMI->isCopyLike()) 142218893Sdim return false; 143218893Sdim DEBUG(dbgs() << "Coalescing: " << *DefMI); 144218893Sdim DEBUG(dbgs() << "*** to: " << *MI); 145218893Sdim MRI->replaceRegWith(DstReg, SrcReg); 146218893Sdim MI->eraseFromParent(); 147218893Sdim ++NumCoalesces; 148218893Sdim return true; 149218893Sdim} 150218893Sdim 151193323Sed/// AllUsesDominatedByBlock - Return true if all uses of the specified register 152212904Sdim/// occur in blocks dominated by the specified block. If any use is in the 153212904Sdim/// definition block, then return false since it is never legal to move def 154212904Sdim/// after uses. 155218893Sdimbool 156218893SdimMachineSinking::AllUsesDominatedByBlock(unsigned Reg, 157218893Sdim MachineBasicBlock *MBB, 158218893Sdim MachineBasicBlock *DefMBB, 159218893Sdim bool &BreakPHIEdge, 160218893Sdim bool &LocalUse) const { 161193323Sed assert(TargetRegisterInfo::isVirtualRegister(Reg) && 162193323Sed "Only makes sense for vregs"); 163218893Sdim 164234353Sdim // Ignore debug uses because debug info doesn't affect the code. 165218893Sdim if (MRI->use_nodbg_empty(Reg)) 166218893Sdim return true; 167218893Sdim 168218893Sdim // BreakPHIEdge is true if all the uses are in the successor MBB being sunken 169218893Sdim // into and they are all PHI nodes. In this case, machine-sink must break 170218893Sdim // the critical edge first. e.g. 171218893Sdim // 172218893Sdim // BB#1: derived from LLVM BB %bb4.preheader 173218893Sdim // Predecessors according to CFG: BB#0 174218893Sdim // ... 175218893Sdim // %reg16385<def> = DEC64_32r %reg16437, %EFLAGS<imp-def,dead> 176218893Sdim // ... 177218893Sdim // JE_4 <BB#37>, %EFLAGS<imp-use> 178218893Sdim // Successors according to CFG: BB#37 BB#2 179218893Sdim // 180218893Sdim // BB#2: derived from LLVM BB %bb.nph 181218893Sdim // Predecessors according to CFG: BB#0 BB#1 182218893Sdim // %reg16386<def> = PHI %reg16434, <BB#0>, %reg16385, <BB#1> 183218893Sdim BreakPHIEdge = true; 184210299Sed for (MachineRegisterInfo::use_nodbg_iterator 185218893Sdim I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end(); 186210299Sed I != E; ++I) { 187218893Sdim MachineInstr *UseInst = &*I; 188218893Sdim MachineBasicBlock *UseBlock = UseInst->getParent(); 189218893Sdim if (!(UseBlock == MBB && UseInst->isPHI() && 190218893Sdim UseInst->getOperand(I.getOperandNo()+1).getMBB() == DefMBB)) { 191218893Sdim BreakPHIEdge = false; 192218893Sdim break; 193218893Sdim } 194218893Sdim } 195218893Sdim if (BreakPHIEdge) 196218893Sdim return true; 197218893Sdim 198218893Sdim for (MachineRegisterInfo::use_nodbg_iterator 199218893Sdim I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end(); 200218893Sdim I != E; ++I) { 201193323Sed // Determine the block of the use. 202193323Sed MachineInstr *UseInst = &*I; 203193323Sed MachineBasicBlock *UseBlock = UseInst->getParent(); 204203954Srdivacky if (UseInst->isPHI()) { 205193323Sed // PHI nodes use the operand in the predecessor block, not the block with 206193323Sed // the PHI. 207193323Sed UseBlock = UseInst->getOperand(I.getOperandNo()+1).getMBB(); 208212904Sdim } else if (UseBlock == DefMBB) { 209212904Sdim LocalUse = true; 210212904Sdim return false; 211193323Sed } 212210299Sed 213193323Sed // Check that it dominates. 214193323Sed if (!DT->dominates(MBB, UseBlock)) 215193323Sed return false; 216193323Sed } 217210299Sed 218193323Sed return true; 219193323Sed} 220193323Sed 221193323Sedbool MachineSinking::runOnMachineFunction(MachineFunction &MF) { 222202375Srdivacky DEBUG(dbgs() << "******** Machine Sinking ********\n"); 223210299Sed 224198396Srdivacky const TargetMachine &TM = MF.getTarget(); 225198396Srdivacky TII = TM.getInstrInfo(); 226198396Srdivacky TRI = TM.getRegisterInfo(); 227218893Sdim MRI = &MF.getRegInfo(); 228193323Sed DT = &getAnalysis<MachineDominatorTree>(); 229207618Srdivacky LI = &getAnalysis<MachineLoopInfo>(); 230198090Srdivacky AA = &getAnalysis<AliasAnalysis>(); 231193323Sed 232193323Sed bool EverMadeChange = false; 233210299Sed 234193323Sed while (1) { 235193323Sed bool MadeChange = false; 236193323Sed 237193323Sed // Process all basic blocks. 238218893Sdim CEBCandidates.clear(); 239210299Sed for (MachineFunction::iterator I = MF.begin(), E = MF.end(); 240193323Sed I != E; ++I) 241193323Sed MadeChange |= ProcessBlock(*I); 242210299Sed 243193323Sed // If this iteration over the code changed anything, keep iterating. 244193323Sed if (!MadeChange) break; 245193323Sed EverMadeChange = true; 246210299Sed } 247193323Sed return EverMadeChange; 248193323Sed} 249193323Sed 250193323Sedbool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) { 251193323Sed // Can't sink anything out of a block that has less than two successors. 252193323Sed if (MBB.succ_size() <= 1 || MBB.empty()) return false; 253193323Sed 254206274Srdivacky // Don't bother sinking code out of unreachable blocks. In addition to being 255210299Sed // unprofitable, it can also lead to infinite looping, because in an 256210299Sed // unreachable loop there may be nowhere to stop. 257206274Srdivacky if (!DT->isReachableFromEntry(&MBB)) return false; 258206274Srdivacky 259193323Sed bool MadeChange = false; 260193323Sed 261193323Sed // Walk the basic block bottom-up. Remember if we saw a store. 262193323Sed MachineBasicBlock::iterator I = MBB.end(); 263193323Sed --I; 264193323Sed bool ProcessedBegin, SawStore = false; 265193323Sed do { 266193323Sed MachineInstr *MI = I; // The instruction to sink. 267210299Sed 268193323Sed // Predecrement I (if it's not begin) so that it isn't invalidated by 269193323Sed // sinking. 270193323Sed ProcessedBegin = I == MBB.begin(); 271193323Sed if (!ProcessedBegin) 272193323Sed --I; 273204792Srdivacky 274204792Srdivacky if (MI->isDebugValue()) 275204792Srdivacky continue; 276204792Srdivacky 277221345Sdim bool Joined = PerformTrivialForwardCoalescing(MI, &MBB); 278221345Sdim if (Joined) { 279221345Sdim MadeChange = true; 280218893Sdim continue; 281221345Sdim } 282218893Sdim 283193323Sed if (SinkInstruction(MI, SawStore)) 284193323Sed ++NumSunk, MadeChange = true; 285210299Sed 286193323Sed // If we just processed the first instruction in the block, we're done. 287193323Sed } while (!ProcessedBegin); 288210299Sed 289193323Sed return MadeChange; 290193323Sed} 291193323Sed 292218893Sdimbool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr *MI, 293218893Sdim MachineBasicBlock *From, 294218893Sdim MachineBasicBlock *To) { 295218893Sdim // FIXME: Need much better heuristics. 296218893Sdim 297218893Sdim // If the pass has already considered breaking this edge (during this pass 298218893Sdim // through the function), then let's go ahead and break it. This means 299218893Sdim // sinking multiple "cheap" instructions into the same block. 300218893Sdim if (!CEBCandidates.insert(std::make_pair(From, To))) 301218893Sdim return true; 302218893Sdim 303234353Sdim if (!MI->isCopy() && !MI->isAsCheapAsAMove()) 304218893Sdim return true; 305218893Sdim 306218893Sdim // MI is cheap, we probably don't want to break the critical edge for it. 307218893Sdim // However, if this would allow some definitions of its source operands 308218893Sdim // to be sunk then it's probably worth it. 309218893Sdim for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 310218893Sdim const MachineOperand &MO = MI->getOperand(i); 311263508Sdim if (!MO.isReg() || !MO.isUse()) 312263508Sdim continue; 313218893Sdim unsigned Reg = MO.getReg(); 314263508Sdim if (Reg == 0) 315218893Sdim continue; 316263508Sdim 317263508Sdim // We don't move live definitions of physical registers, 318263508Sdim // so sinking their uses won't enable any opportunities. 319263508Sdim if (TargetRegisterInfo::isPhysicalRegister(Reg)) 320263508Sdim continue; 321263508Sdim 322263508Sdim // If this instruction is the only user of a virtual register, 323263508Sdim // check if breaking the edge will enable sinking 324263508Sdim // both this instruction and the defining instruction. 325263508Sdim if (MRI->hasOneNonDBGUse(Reg)) { 326263508Sdim // If the definition resides in same MBB, 327263508Sdim // claim it's likely we can sink these together. 328263508Sdim // If definition resides elsewhere, we aren't 329263508Sdim // blocking it from being sunk so don't break the edge. 330263508Sdim MachineInstr *DefMI = MRI->getVRegDef(Reg); 331263508Sdim if (DefMI->getParent() == MI->getParent()) 332263508Sdim return true; 333263508Sdim } 334218893Sdim } 335218893Sdim 336218893Sdim return false; 337218893Sdim} 338218893Sdim 339218893SdimMachineBasicBlock *MachineSinking::SplitCriticalEdge(MachineInstr *MI, 340218893Sdim MachineBasicBlock *FromBB, 341218893Sdim MachineBasicBlock *ToBB, 342218893Sdim bool BreakPHIEdge) { 343218893Sdim if (!isWorthBreakingCriticalEdge(MI, FromBB, ToBB)) 344218893Sdim return 0; 345218893Sdim 346212904Sdim // Avoid breaking back edge. From == To means backedge for single BB loop. 347218893Sdim if (!SplitEdges || FromBB == ToBB) 348212904Sdim return 0; 349212904Sdim 350218893Sdim // Check for backedges of more "complex" loops. 351218893Sdim if (LI->getLoopFor(FromBB) == LI->getLoopFor(ToBB) && 352218893Sdim LI->isLoopHeader(ToBB)) 353218893Sdim return 0; 354218893Sdim 355218893Sdim // It's not always legal to break critical edges and sink the computation 356218893Sdim // to the edge. 357218893Sdim // 358218893Sdim // BB#1: 359218893Sdim // v1024 360218893Sdim // Beq BB#3 361218893Sdim // <fallthrough> 362218893Sdim // BB#2: 363218893Sdim // ... no uses of v1024 364218893Sdim // <fallthrough> 365218893Sdim // BB#3: 366218893Sdim // ... 367218893Sdim // = v1024 368218893Sdim // 369218893Sdim // If BB#1 -> BB#3 edge is broken and computation of v1024 is inserted: 370218893Sdim // 371218893Sdim // BB#1: 372218893Sdim // ... 373218893Sdim // Bne BB#2 374218893Sdim // BB#4: 375218893Sdim // v1024 = 376218893Sdim // B BB#3 377218893Sdim // BB#2: 378218893Sdim // ... no uses of v1024 379218893Sdim // <fallthrough> 380218893Sdim // BB#3: 381218893Sdim // ... 382218893Sdim // = v1024 383218893Sdim // 384218893Sdim // This is incorrect since v1024 is not computed along the BB#1->BB#2->BB#3 385218893Sdim // flow. We need to ensure the new basic block where the computation is 386218893Sdim // sunk to dominates all the uses. 387218893Sdim // It's only legal to break critical edge and sink the computation to the 388218893Sdim // new block if all the predecessors of "To", except for "From", are 389218893Sdim // not dominated by "From". Given SSA property, this means these 390218893Sdim // predecessors are dominated by "To". 391218893Sdim // 392218893Sdim // There is no need to do this check if all the uses are PHI nodes. PHI 393218893Sdim // sources are only defined on the specific predecessor edges. 394218893Sdim if (!BreakPHIEdge) { 395212904Sdim for (MachineBasicBlock::pred_iterator PI = ToBB->pred_begin(), 396212904Sdim E = ToBB->pred_end(); PI != E; ++PI) { 397212904Sdim if (*PI == FromBB) 398212904Sdim continue; 399212904Sdim if (!DT->dominates(ToBB, *PI)) 400212904Sdim return 0; 401212904Sdim } 402212904Sdim } 403212904Sdim 404218893Sdim return FromBB->SplitCriticalEdge(ToBB, this); 405212904Sdim} 406212904Sdim 407218893Sdimstatic bool AvoidsSinking(MachineInstr *MI, MachineRegisterInfo *MRI) { 408218893Sdim return MI->isInsertSubreg() || MI->isSubregToReg() || MI->isRegSequence(); 409218893Sdim} 410218893Sdim 411234353Sdim/// collectDebgValues - Scan instructions following MI and collect any 412226633Sdim/// matching DBG_VALUEs. 413234353Sdimstatic void collectDebugValues(MachineInstr *MI, 414263508Sdim SmallVectorImpl<MachineInstr *> &DbgValues) { 415226633Sdim DbgValues.clear(); 416226633Sdim if (!MI->getOperand(0).isReg()) 417226633Sdim return; 418226633Sdim 419226633Sdim MachineBasicBlock::iterator DI = MI; ++DI; 420226633Sdim for (MachineBasicBlock::iterator DE = MI->getParent()->end(); 421226633Sdim DI != DE; ++DI) { 422226633Sdim if (!DI->isDebugValue()) 423226633Sdim return; 424226633Sdim if (DI->getOperand(0).isReg() && 425226633Sdim DI->getOperand(0).getReg() == MI->getOperand(0).getReg()) 426226633Sdim DbgValues.push_back(DI); 427226633Sdim } 428226633Sdim} 429226633Sdim 430234353Sdim/// isPostDominatedBy - Return true if A is post dominated by B. 431234353Sdimstatic bool isPostDominatedBy(MachineBasicBlock *A, MachineBasicBlock *B) { 432234353Sdim 433234353Sdim // FIXME - Use real post dominator. 434234353Sdim if (A->succ_size() != 2) 435218893Sdim return false; 436234353Sdim MachineBasicBlock::succ_iterator I = A->succ_begin(); 437234353Sdim if (B == *I) 438234353Sdim ++I; 439234353Sdim MachineBasicBlock *OtherSuccBlock = *I; 440234353Sdim if (OtherSuccBlock->succ_size() != 1 || 441234353Sdim *(OtherSuccBlock->succ_begin()) != B) 442234353Sdim return false; 443218893Sdim 444234353Sdim return true; 445234353Sdim} 446234353Sdim 447234353Sdim/// isProfitableToSinkTo - Return true if it is profitable to sink MI. 448234353Sdimbool MachineSinking::isProfitableToSinkTo(unsigned Reg, MachineInstr *MI, 449234353Sdim MachineBasicBlock *MBB, 450234353Sdim MachineBasicBlock *SuccToSinkTo) { 451234353Sdim assert (MI && "Invalid MachineInstr!"); 452234353Sdim assert (SuccToSinkTo && "Invalid SinkTo Candidate BB"); 453234353Sdim 454234353Sdim if (MBB == SuccToSinkTo) 455193323Sed return false; 456210299Sed 457234353Sdim // It is profitable if SuccToSinkTo does not post dominate current block. 458234353Sdim if (!isPostDominatedBy(MBB, SuccToSinkTo)) 459234353Sdim return true; 460210299Sed 461234353Sdim // Check if only use in post dominated block is PHI instruction. 462234353Sdim bool NonPHIUse = false; 463234353Sdim for (MachineRegisterInfo::use_nodbg_iterator 464234353Sdim I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end(); 465234353Sdim I != E; ++I) { 466234353Sdim MachineInstr *UseInst = &*I; 467234353Sdim MachineBasicBlock *UseBlock = UseInst->getParent(); 468234353Sdim if (UseBlock == SuccToSinkTo && !UseInst->isPHI()) 469234353Sdim NonPHIUse = true; 470234353Sdim } 471234353Sdim if (!NonPHIUse) 472234353Sdim return true; 473234353Sdim 474234353Sdim // If SuccToSinkTo post dominates then also it may be profitable if MI 475234353Sdim // can further profitably sinked into another block in next round. 476234353Sdim bool BreakPHIEdge = false; 477234353Sdim // FIXME - If finding successor is compile time expensive then catch results. 478234353Sdim if (MachineBasicBlock *MBB2 = FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge)) 479234353Sdim return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2); 480234353Sdim 481234353Sdim // If SuccToSinkTo is final destination and it is a post dominator of current 482234353Sdim // block then it is not profitable to sink MI into SuccToSinkTo block. 483234353Sdim return false; 484234353Sdim} 485234353Sdim 486234353Sdim/// FindSuccToSinkTo - Find a successor to sink this instruction to. 487234353SdimMachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI, 488234353Sdim MachineBasicBlock *MBB, 489234353Sdim bool &BreakPHIEdge) { 490234353Sdim 491234353Sdim assert (MI && "Invalid MachineInstr!"); 492234353Sdim assert (MBB && "Invalid MachineBasicBlock!"); 493234353Sdim 494193323Sed // Loop over all the operands of the specified instruction. If there is 495193323Sed // anything we can't handle, bail out. 496210299Sed 497193323Sed // SuccToSinkTo - This is the successor to sink this instruction to, once we 498193323Sed // decide. 499193323Sed MachineBasicBlock *SuccToSinkTo = 0; 500193323Sed for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 501193323Sed const MachineOperand &MO = MI->getOperand(i); 502193323Sed if (!MO.isReg()) continue; // Ignore non-register operands. 503210299Sed 504193323Sed unsigned Reg = MO.getReg(); 505193323Sed if (Reg == 0) continue; 506210299Sed 507193323Sed if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 508198090Srdivacky if (MO.isUse()) { 509198090Srdivacky // If the physreg has no defs anywhere, it's just an ambient register 510198090Srdivacky // and we can freely move its uses. Alternatively, if it's allocatable, 511198090Srdivacky // it could get allocated to something with a def during allocation. 512234353Sdim if (!MRI->isConstantPhysReg(Reg, *MBB->getParent())) 513234353Sdim return NULL; 514198090Srdivacky } else if (!MO.isDead()) { 515198090Srdivacky // A def that isn't dead. We can't move it. 516234353Sdim return NULL; 517198090Srdivacky } 518193323Sed } else { 519193323Sed // Virtual register uses are always safe to sink. 520193323Sed if (MO.isUse()) continue; 521193323Sed 522193323Sed // If it's not safe to move defs of the register class, then abort. 523218893Sdim if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg))) 524234353Sdim return NULL; 525210299Sed 526193323Sed // FIXME: This picks a successor to sink into based on having one 527193323Sed // successor that dominates all the uses. However, there are cases where 528193323Sed // sinking can happen but where the sink point isn't a successor. For 529193323Sed // example: 530210299Sed // 531193323Sed // x = computation 532193323Sed // if () {} else {} 533193323Sed // use x 534210299Sed // 535210299Sed // the instruction could be sunk over the whole diamond for the 536193323Sed // if/then/else (or loop, etc), allowing it to be sunk into other blocks 537193323Sed // after that. 538210299Sed 539193323Sed // Virtual register defs can only be sunk if all their uses are in blocks 540193323Sed // dominated by one of the successors. 541193323Sed if (SuccToSinkTo) { 542193323Sed // If a previous operand picked a block to sink to, then this operand 543193323Sed // must be sinkable to the same block. 544212904Sdim bool LocalUse = false; 545234353Sdim if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB, 546218893Sdim BreakPHIEdge, LocalUse)) 547234353Sdim return NULL; 548210299Sed 549193323Sed continue; 550193323Sed } 551210299Sed 552193323Sed // Otherwise, we should look at all the successors and decide which one 553193323Sed // we should sink to. 554239462Sdim // We give successors with smaller loop depth higher priority. 555239462Sdim SmallVector<MachineBasicBlock*, 4> Succs(MBB->succ_begin(), MBB->succ_end()); 556239462Sdim std::stable_sort(Succs.begin(), Succs.end(), SuccessorSorter(LI)); 557263508Sdim for (SmallVectorImpl<MachineBasicBlock *>::iterator SI = Succs.begin(), 558263508Sdim E = Succs.end(); SI != E; ++SI) { 559234353Sdim MachineBasicBlock *SuccBlock = *SI; 560212904Sdim bool LocalUse = false; 561234353Sdim if (AllUsesDominatedByBlock(Reg, SuccBlock, MBB, 562218893Sdim BreakPHIEdge, LocalUse)) { 563234353Sdim SuccToSinkTo = SuccBlock; 564193323Sed break; 565193323Sed } 566212904Sdim if (LocalUse) 567212904Sdim // Def is used locally, it's never safe to move this def. 568234353Sdim return NULL; 569193323Sed } 570210299Sed 571193323Sed // If we couldn't find a block to sink to, ignore this instruction. 572193323Sed if (SuccToSinkTo == 0) 573234353Sdim return NULL; 574234353Sdim else if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo)) 575234353Sdim return NULL; 576193323Sed } 577193323Sed } 578210299Sed 579234353Sdim // It is not possible to sink an instruction into its own block. This can 580234353Sdim // happen with loops. 581234353Sdim if (MBB == SuccToSinkTo) 582234353Sdim return NULL; 583193323Sed 584193323Sed // It's not safe to sink instructions to EH landing pad. Control flow into 585193323Sed // landing pad is implicitly defined. 586234353Sdim if (SuccToSinkTo && SuccToSinkTo->isLandingPad()) 587234353Sdim return NULL; 588234353Sdim 589234353Sdim return SuccToSinkTo; 590234353Sdim} 591234353Sdim 592234353Sdim/// SinkInstruction - Determine whether it is safe to sink the specified machine 593234353Sdim/// instruction out of its current block into a successor. 594234353Sdimbool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { 595234353Sdim // Don't sink insert_subreg, subreg_to_reg, reg_sequence. These are meant to 596234353Sdim // be close to the source to make it easier to coalesce. 597234353Sdim if (AvoidsSinking(MI, MRI)) 598193323Sed return false; 599210299Sed 600234353Sdim // Check if it's safe to move the instruction. 601234353Sdim if (!MI->isSafeToMove(TII, AA, SawStore)) 602193323Sed return false; 603210299Sed 604234353Sdim // FIXME: This should include support for sinking instructions within the 605234353Sdim // block they are currently in to shorten the live ranges. We often get 606234353Sdim // instructions sunk into the top of a large block, but it would be better to 607234353Sdim // also sink them down before their first use in the block. This xform has to 608234353Sdim // be careful not to *increase* register pressure though, e.g. sinking 609234353Sdim // "x = y + z" down if it kills y and z would increase the live ranges of y 610234353Sdim // and z and only shrink the live range of x. 611234353Sdim 612234353Sdim bool BreakPHIEdge = false; 613234353Sdim MachineBasicBlock *ParentBlock = MI->getParent(); 614234353Sdim MachineBasicBlock *SuccToSinkTo = FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge); 615234353Sdim 616234353Sdim // If there are no outputs, it must have side-effects. 617234353Sdim if (SuccToSinkTo == 0) 618234353Sdim return false; 619234353Sdim 620234353Sdim 621210299Sed // If the instruction to move defines a dead physical register which is live 622210299Sed // when leaving the basic block, don't move it because it could turn into a 623210299Sed // "zombie" define of that preg. E.g., EFLAGS. (<rdar://problem/8030636>) 624210299Sed for (unsigned I = 0, E = MI->getNumOperands(); I != E; ++I) { 625210299Sed const MachineOperand &MO = MI->getOperand(I); 626210299Sed if (!MO.isReg()) continue; 627210299Sed unsigned Reg = MO.getReg(); 628210299Sed if (Reg == 0 || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 629210299Sed if (SuccToSinkTo->isLiveIn(Reg)) 630210299Sed return false; 631210299Sed } 632210299Sed 633210299Sed DEBUG(dbgs() << "Sink instr " << *MI << "\tinto block " << *SuccToSinkTo); 634210299Sed 635263508Sdim // If the block has multiple predecessors, this is a critical edge. 636263508Sdim // Decide if we can sink along it or need to break the edge. 637193323Sed if (SuccToSinkTo->pred_size() > 1) { 638207618Srdivacky // We cannot sink a load across a critical edge - there may be stores in 639207618Srdivacky // other code paths. 640212904Sdim bool TryBreak = false; 641207618Srdivacky bool store = true; 642207618Srdivacky if (!MI->isSafeToMove(TII, AA, store)) { 643212904Sdim DEBUG(dbgs() << " *** NOTE: Won't sink load along critical edge.\n"); 644212904Sdim TryBreak = true; 645207618Srdivacky } 646207618Srdivacky 647207618Srdivacky // We don't want to sink across a critical edge if we don't dominate the 648207618Srdivacky // successor. We could be introducing calculations to new code paths. 649212904Sdim if (!TryBreak && !DT->dominates(ParentBlock, SuccToSinkTo)) { 650212904Sdim DEBUG(dbgs() << " *** NOTE: Critical edge found\n"); 651212904Sdim TryBreak = true; 652207618Srdivacky } 653207618Srdivacky 654207618Srdivacky // Don't sink instructions into a loop. 655212904Sdim if (!TryBreak && LI->isLoopHeader(SuccToSinkTo)) { 656212904Sdim DEBUG(dbgs() << " *** NOTE: Loop header found\n"); 657212904Sdim TryBreak = true; 658207618Srdivacky } 659207618Srdivacky 660207618Srdivacky // Otherwise we are OK with sinking along a critical edge. 661212904Sdim if (!TryBreak) 662212904Sdim DEBUG(dbgs() << "Sinking along critical edge.\n"); 663212904Sdim else { 664218893Sdim MachineBasicBlock *NewSucc = 665218893Sdim SplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, BreakPHIEdge); 666212904Sdim if (!NewSucc) { 667218893Sdim DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to " 668218893Sdim "break critical edge\n"); 669212904Sdim return false; 670212904Sdim } else { 671212904Sdim DEBUG(dbgs() << " *** Splitting critical edge:" 672212904Sdim " BB#" << ParentBlock->getNumber() 673212904Sdim << " -- BB#" << NewSucc->getNumber() 674212904Sdim << " -- BB#" << SuccToSinkTo->getNumber() << '\n'); 675212904Sdim SuccToSinkTo = NewSucc; 676212904Sdim ++NumSplit; 677218893Sdim BreakPHIEdge = false; 678212904Sdim } 679212904Sdim } 680193323Sed } 681210299Sed 682218893Sdim if (BreakPHIEdge) { 683218893Sdim // BreakPHIEdge is true if all the uses are in the successor MBB being 684218893Sdim // sunken into and they are all PHI nodes. In this case, machine-sink must 685218893Sdim // break the critical edge first. 686218893Sdim MachineBasicBlock *NewSucc = SplitCriticalEdge(MI, ParentBlock, 687218893Sdim SuccToSinkTo, BreakPHIEdge); 688218893Sdim if (!NewSucc) { 689218893Sdim DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to " 690218893Sdim "break critical edge\n"); 691218893Sdim return false; 692218893Sdim } 693218893Sdim 694218893Sdim DEBUG(dbgs() << " *** Splitting critical edge:" 695218893Sdim " BB#" << ParentBlock->getNumber() 696218893Sdim << " -- BB#" << NewSucc->getNumber() 697218893Sdim << " -- BB#" << SuccToSinkTo->getNumber() << '\n'); 698218893Sdim SuccToSinkTo = NewSucc; 699218893Sdim ++NumSplit; 700218893Sdim } 701218893Sdim 702210299Sed // Determine where to insert into. Skip phi nodes. 703193323Sed MachineBasicBlock::iterator InsertPos = SuccToSinkTo->begin(); 704203954Srdivacky while (InsertPos != SuccToSinkTo->end() && InsertPos->isPHI()) 705193323Sed ++InsertPos; 706210299Sed 707226633Sdim // collect matching debug values. 708226633Sdim SmallVector<MachineInstr *, 2> DbgValuesToSink; 709226633Sdim collectDebugValues(MI, DbgValuesToSink); 710226633Sdim 711193323Sed // Move the instruction. 712193323Sed SuccToSinkTo->splice(InsertPos, ParentBlock, MI, 713193323Sed ++MachineBasicBlock::iterator(MI)); 714208599Srdivacky 715226633Sdim // Move debug values. 716263508Sdim for (SmallVectorImpl<MachineInstr *>::iterator DBI = DbgValuesToSink.begin(), 717226633Sdim DBE = DbgValuesToSink.end(); DBI != DBE; ++DBI) { 718226633Sdim MachineInstr *DbgMI = *DBI; 719226633Sdim SuccToSinkTo->splice(InsertPos, ParentBlock, DbgMI, 720226633Sdim ++MachineBasicBlock::iterator(DbgMI)); 721226633Sdim } 722226633Sdim 723210299Sed // Conservatively, clear any kill flags, since it's possible that they are no 724210299Sed // longer correct. 725208599Srdivacky MI->clearKillInfo(); 726208599Srdivacky 727193323Sed return true; 728193323Sed} 729