1c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner//===-- MachineSink.cpp - Sinking for machine instructions ----------------===// 2c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner// 3c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner// The LLVM Compiler Infrastructure 4c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner// 5c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner// This file is distributed under the University of Illinois Open Source 6c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner// License. See LICENSE.TXT for details. 7c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner// 8c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner//===----------------------------------------------------------------------===// 9c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner// 1005c68374c1c73599a0b7044ad09fb4827d128ec5Bill Wendling// This pass moves instructions into successor blocks when possible, so that 11a5225add0d748bd6396f3e4e77669a8996d9ececDan Gohman// they aren't executed on paths where their results aren't needed. 12a5225add0d748bd6396f3e4e77669a8996d9ececDan Gohman// 13a5225add0d748bd6396f3e4e77669a8996d9ececDan Gohman// This pass is not intended to be a replacement or a complete alternative 14a5225add0d748bd6396f3e4e77669a8996d9ececDan Gohman// for an LLVM-IR-level sinking pass. It is only designed to sink simple 15a5225add0d748bd6396f3e4e77669a8996d9ececDan Gohman// constructs that are not exposed before lowering and instruction selection. 16c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner// 17c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner//===----------------------------------------------------------------------===// 18c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner 19c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner#define DEBUG_TYPE "machine-sink" 20c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner#include "llvm/CodeGen/Passes.h" 21c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner#include "llvm/CodeGen/MachineRegisterInfo.h" 22c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner#include "llvm/CodeGen/MachineDominators.h" 23626f3d7a57f4f2a46880331fdacce259195213efJakob Stoklund Olesen#include "llvm/CodeGen/MachineLoopInfo.h" 24a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman#include "llvm/Analysis/AliasAnalysis.h" 256f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman#include "llvm/Target/TargetRegisterInfo.h" 26c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner#include "llvm/Target/TargetInstrInfo.h" 27c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner#include "llvm/Target/TargetMachine.h" 286edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng#include "llvm/ADT/SmallSet.h" 29c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner#include "llvm/ADT/Statistic.h" 304dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng#include "llvm/Support/CommandLine.h" 31c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner#include "llvm/Support/Debug.h" 321e973aae79476d003b58dc430d81f964c2ea5853Bill Wendling#include "llvm/Support/raw_ostream.h" 33c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattnerusing namespace llvm; 34c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner 351df91b0e54bc62f8fc7a06a4f75220e40aa2dfe0Andrew Trickstatic cl::opt<bool> 364dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan ChengSplitEdges("machine-sink-split", 374dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng cl::desc("Split critical edges during machine sinking"), 3844be1a8d661cfab0cc3d11b0dd158271b2d2ca04Evan Cheng cl::init(true), cl::Hidden); 394dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng 406edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan ChengSTATISTIC(NumSunk, "Number of machine instructions sunk"); 416edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan ChengSTATISTIC(NumSplit, "Number of critical edges split"); 426edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan ChengSTATISTIC(NumCoalesces, "Number of copies coalesced"); 43c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner 44c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattnernamespace { 456726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky class MachineSinking : public MachineFunctionPass { 46c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner const TargetInstrInfo *TII; 4719778e7558bc161b87920c5be9cc01bb84a08de2Dan Gohman const TargetRegisterInfo *TRI; 486edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng MachineRegisterInfo *MRI; // Machine register information 49a5225add0d748bd6396f3e4e77669a8996d9ececDan Gohman MachineDominatorTree *DT; // Machine dominator tree 50626f3d7a57f4f2a46880331fdacce259195213efJakob Stoklund Olesen MachineLoopInfo *LI; 51a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman AliasAnalysis *AA; 5245094e34bcbb133aa0bbe55710e25369df0e02edDan Gohman BitVector AllocatableSet; // Which physregs are allocatable? 53c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner 546edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // Remember which edges have been considered for breaking. 556edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng SmallSet<std::pair<MachineBasicBlock*,MachineBasicBlock*>, 8> 566edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng CEBCandidates; 576edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng 58c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner public: 59c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner static char ID; // Pass identification 60081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson MachineSinking() : MachineFunctionPass(ID) { 61081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeMachineSinkingPass(*PassRegistry::getPassRegistry()); 62081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 636ee358b4eb92298357687cb460dde8e26678aca2Jim Grosbach 64c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner virtual bool runOnMachineFunction(MachineFunction &MF); 656ee358b4eb92298357687cb460dde8e26678aca2Jim Grosbach 66c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 67845012e6d31799c7fbd1193fa1af8ee2d12e9231Dan Gohman AU.setPreservesCFG(); 68c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner MachineFunctionPass::getAnalysisUsage(AU); 69a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman AU.addRequired<AliasAnalysis>(); 70c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner AU.addRequired<MachineDominatorTree>(); 71626f3d7a57f4f2a46880331fdacce259195213efJakob Stoklund Olesen AU.addRequired<MachineLoopInfo>(); 72c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner AU.addPreserved<MachineDominatorTree>(); 73626f3d7a57f4f2a46880331fdacce259195213efJakob Stoklund Olesen AU.addPreserved<MachineLoopInfo>(); 74c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner } 756edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng 766edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng virtual void releaseMemory() { 776edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng CEBCandidates.clear(); 786edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng } 796edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng 80c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner private: 81c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner bool ProcessBlock(MachineBasicBlock &MBB); 826edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng bool isWorthBreakingCriticalEdge(MachineInstr *MI, 836edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng MachineBasicBlock *From, 846edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng MachineBasicBlock *To); 856edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng MachineBasicBlock *SplitCriticalEdge(MachineInstr *MI, 866edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng MachineBasicBlock *From, 876edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng MachineBasicBlock *To, 887af6dc47a552d0d7d09752ad2e747d3973125b48Evan Cheng bool BreakPHIEdge); 89aad193a7e9f8eb4b558e16c2b54c31dee54f5f1eChris Lattner bool SinkInstruction(MachineInstr *MI, bool &SawStore); 90c3439ad63f4d145ca7357b7918bd72dfde8213d3Evan Cheng bool AllUsesDominatedByBlock(unsigned Reg, MachineBasicBlock *MBB, 916edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng MachineBasicBlock *DefMBB, 927af6dc47a552d0d7d09752ad2e747d3973125b48Evan Cheng bool &BreakPHIEdge, bool &LocalUse) const; 935211134fbd35bf0befc60888860010b23c27ee5aDevang Patel MachineBasicBlock *FindSuccToSinkTo(MachineInstr *MI, MachineBasicBlock *MBB, 945211134fbd35bf0befc60888860010b23c27ee5aDevang Patel bool &BreakPHIEdge); 951df91b0e54bc62f8fc7a06a4f75220e40aa2dfe0Andrew Trick bool isProfitableToSinkTo(unsigned Reg, MachineInstr *MI, 965211134fbd35bf0befc60888860010b23c27ee5aDevang Patel MachineBasicBlock *MBB, 975211134fbd35bf0befc60888860010b23c27ee5aDevang Patel MachineBasicBlock *SuccToSinkTo); 98e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel 996edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng bool PerformTrivialForwardCoalescing(MachineInstr *MI, 1006edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng MachineBasicBlock *MBB); 101c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner }; 10253b59d1d974184657edfd22779e0bb3653d164ecManman Ren 10353b59d1d974184657edfd22779e0bb3653d164ecManman Ren // SuccessorSorter - Sort Successors according to their loop depth. 10453b59d1d974184657edfd22779e0bb3653d164ecManman Ren struct SuccessorSorter { 10553b59d1d974184657edfd22779e0bb3653d164ecManman Ren SuccessorSorter(MachineLoopInfo *LoopInfo) : LI(LoopInfo) {} 10653b59d1d974184657edfd22779e0bb3653d164ecManman Ren bool operator()(const MachineBasicBlock *LHS, 10753b59d1d974184657edfd22779e0bb3653d164ecManman Ren const MachineBasicBlock *RHS) const { 10853b59d1d974184657edfd22779e0bb3653d164ecManman Ren return LI->getLoopDepth(LHS) < LI->getLoopDepth(RHS); 10953b59d1d974184657edfd22779e0bb3653d164ecManman Ren } 11053b59d1d974184657edfd22779e0bb3653d164ecManman Ren MachineLoopInfo *LI; 11153b59d1d974184657edfd22779e0bb3653d164ecManman Ren }; 112c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner} // end anonymous namespace 1136ee358b4eb92298357687cb460dde8e26678aca2Jim Grosbach 114844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar MachineSinking::ID = 0; 1151dd8c8560d45d36a8e507cd014352f1d313f9f9eAndrew Trickchar &llvm::MachineSinkingID = MachineSinking::ID; 1162ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(MachineSinking, "machine-sink", 1172ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson "Machine code sinking", false, false) 1182ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 1192ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 1202ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 1212ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(MachineSinking, "machine-sink", 122ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Machine code sinking", false, false) 123c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner 1246edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Chengbool MachineSinking::PerformTrivialForwardCoalescing(MachineInstr *MI, 1256edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng MachineBasicBlock *MBB) { 1266edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng if (!MI->isCopy()) 1276edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng return false; 1286edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng 1296edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng unsigned SrcReg = MI->getOperand(1).getReg(); 1306edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng unsigned DstReg = MI->getOperand(0).getReg(); 1316edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng if (!TargetRegisterInfo::isVirtualRegister(SrcReg) || 1326edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng !TargetRegisterInfo::isVirtualRegister(DstReg) || 1336edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng !MRI->hasOneNonDBGUse(SrcReg)) 1346edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng return false; 1356edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng 1366edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng const TargetRegisterClass *SRC = MRI->getRegClass(SrcReg); 1376edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng const TargetRegisterClass *DRC = MRI->getRegClass(DstReg); 1386edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng if (SRC != DRC) 1396edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng return false; 1406edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng 1416edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng MachineInstr *DefMI = MRI->getVRegDef(SrcReg); 1426edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng if (DefMI->isCopyLike()) 1436edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng return false; 1446edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng DEBUG(dbgs() << "Coalescing: " << *DefMI); 1456edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng DEBUG(dbgs() << "*** to: " << *MI); 1466edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng MRI->replaceRegWith(DstReg, SrcReg); 1476edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng MI->eraseFromParent(); 1486edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng ++NumCoalesces; 1496edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng return true; 1506edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng} 1516edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng 152c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner/// AllUsesDominatedByBlock - Return true if all uses of the specified register 153c3439ad63f4d145ca7357b7918bd72dfde8213d3Evan Cheng/// occur in blocks dominated by the specified block. If any use is in the 154c3439ad63f4d145ca7357b7918bd72dfde8213d3Evan Cheng/// definition block, then return false since it is never legal to move def 155c3439ad63f4d145ca7357b7918bd72dfde8213d3Evan Cheng/// after uses. 1566edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Chengbool 1576edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan ChengMachineSinking::AllUsesDominatedByBlock(unsigned Reg, 1586edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng MachineBasicBlock *MBB, 1596edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng MachineBasicBlock *DefMBB, 1607af6dc47a552d0d7d09752ad2e747d3973125b48Evan Cheng bool &BreakPHIEdge, 1617af6dc47a552d0d7d09752ad2e747d3973125b48Evan Cheng bool &LocalUse) const { 1626f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman assert(TargetRegisterInfo::isVirtualRegister(Reg) && 1636f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman "Only makes sense for vregs"); 1642399786b279b6db7077ac36020153714530365dfEvan Cheng 165f5b9a74f0a13afe3b7a8388be81e4062b63e4c30Devang Patel // Ignore debug uses because debug info doesn't affect the code. 1662399786b279b6db7077ac36020153714530365dfEvan Cheng if (MRI->use_nodbg_empty(Reg)) 1672399786b279b6db7077ac36020153714530365dfEvan Cheng return true; 1682399786b279b6db7077ac36020153714530365dfEvan Cheng 1697af6dc47a552d0d7d09752ad2e747d3973125b48Evan Cheng // BreakPHIEdge is true if all the uses are in the successor MBB being sunken 1707af6dc47a552d0d7d09752ad2e747d3973125b48Evan Cheng // into and they are all PHI nodes. In this case, machine-sink must break 1717af6dc47a552d0d7d09752ad2e747d3973125b48Evan Cheng // the critical edge first. e.g. 1727af6dc47a552d0d7d09752ad2e747d3973125b48Evan Cheng // 1732399786b279b6db7077ac36020153714530365dfEvan Cheng // BB#1: derived from LLVM BB %bb4.preheader 1742399786b279b6db7077ac36020153714530365dfEvan Cheng // Predecessors according to CFG: BB#0 1752399786b279b6db7077ac36020153714530365dfEvan Cheng // ... 1762399786b279b6db7077ac36020153714530365dfEvan Cheng // %reg16385<def> = DEC64_32r %reg16437, %EFLAGS<imp-def,dead> 1772399786b279b6db7077ac36020153714530365dfEvan Cheng // ... 1782399786b279b6db7077ac36020153714530365dfEvan Cheng // JE_4 <BB#37>, %EFLAGS<imp-use> 1792399786b279b6db7077ac36020153714530365dfEvan Cheng // Successors according to CFG: BB#37 BB#2 1802399786b279b6db7077ac36020153714530365dfEvan Cheng // 1812399786b279b6db7077ac36020153714530365dfEvan Cheng // BB#2: derived from LLVM BB %bb.nph 1822399786b279b6db7077ac36020153714530365dfEvan Cheng // Predecessors according to CFG: BB#0 BB#1 1832399786b279b6db7077ac36020153714530365dfEvan Cheng // %reg16386<def> = PHI %reg16434, <BB#0>, %reg16385, <BB#1> 1847af6dc47a552d0d7d09752ad2e747d3973125b48Evan Cheng BreakPHIEdge = true; 18505c68374c1c73599a0b7044ad09fb4827d128ec5Bill Wendling for (MachineRegisterInfo::use_nodbg_iterator 1866edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end(); 18705c68374c1c73599a0b7044ad09fb4827d128ec5Bill Wendling I != E; ++I) { 188c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner MachineInstr *UseInst = &*I; 189c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner MachineBasicBlock *UseBlock = UseInst->getParent(); 1902399786b279b6db7077ac36020153714530365dfEvan Cheng if (!(UseBlock == MBB && UseInst->isPHI() && 1912399786b279b6db7077ac36020153714530365dfEvan Cheng UseInst->getOperand(I.getOperandNo()+1).getMBB() == DefMBB)) { 1927af6dc47a552d0d7d09752ad2e747d3973125b48Evan Cheng BreakPHIEdge = false; 1932399786b279b6db7077ac36020153714530365dfEvan Cheng break; 1942399786b279b6db7077ac36020153714530365dfEvan Cheng } 1952399786b279b6db7077ac36020153714530365dfEvan Cheng } 1967af6dc47a552d0d7d09752ad2e747d3973125b48Evan Cheng if (BreakPHIEdge) 1972399786b279b6db7077ac36020153714530365dfEvan Cheng return true; 19805c68374c1c73599a0b7044ad09fb4827d128ec5Bill Wendling 1992399786b279b6db7077ac36020153714530365dfEvan Cheng for (MachineRegisterInfo::use_nodbg_iterator 2002399786b279b6db7077ac36020153714530365dfEvan Cheng I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end(); 2012399786b279b6db7077ac36020153714530365dfEvan Cheng I != E; ++I) { 2022399786b279b6db7077ac36020153714530365dfEvan Cheng // Determine the block of the use. 2032399786b279b6db7077ac36020153714530365dfEvan Cheng MachineInstr *UseInst = &*I; 2042399786b279b6db7077ac36020153714530365dfEvan Cheng MachineBasicBlock *UseBlock = UseInst->getParent(); 2052399786b279b6db7077ac36020153714530365dfEvan Cheng if (UseInst->isPHI()) { 206c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner // PHI nodes use the operand in the predecessor block, not the block with 207c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner // the PHI. 208c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner UseBlock = UseInst->getOperand(I.getOperandNo()+1).getMBB(); 209e5e7946018844978d0ac09fdb35998a53b43ad34Evan Cheng } else if (UseBlock == DefMBB) { 210e5e7946018844978d0ac09fdb35998a53b43ad34Evan Cheng LocalUse = true; 211e5e7946018844978d0ac09fdb35998a53b43ad34Evan Cheng return false; 212c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner } 21305c68374c1c73599a0b7044ad09fb4827d128ec5Bill Wendling 214c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner // Check that it dominates. 215c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner if (!DT->dominates(MBB, UseBlock)) 216c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner return false; 217c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner } 21805c68374c1c73599a0b7044ad09fb4827d128ec5Bill Wendling 219c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner return true; 220c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner} 221c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner 222c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattnerbool MachineSinking::runOnMachineFunction(MachineFunction &MF) { 223c19a9cdfac813360bcedd374df6fcd0a3dc12252David Greene DEBUG(dbgs() << "******** Machine Sinking ********\n"); 2246ee358b4eb92298357687cb460dde8e26678aca2Jim Grosbach 2254e9785ed8ad34f01ccb459796d85a56600ed592bDan Gohman const TargetMachine &TM = MF.getTarget(); 2264e9785ed8ad34f01ccb459796d85a56600ed592bDan Gohman TII = TM.getInstrInfo(); 2274e9785ed8ad34f01ccb459796d85a56600ed592bDan Gohman TRI = TM.getRegisterInfo(); 2286edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng MRI = &MF.getRegInfo(); 229c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner DT = &getAnalysis<MachineDominatorTree>(); 230626f3d7a57f4f2a46880331fdacce259195213efJakob Stoklund Olesen LI = &getAnalysis<MachineLoopInfo>(); 231a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman AA = &getAnalysis<AliasAnalysis>(); 2324e9785ed8ad34f01ccb459796d85a56600ed592bDan Gohman AllocatableSet = TRI->getAllocatableSet(MF); 233c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner 234c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner bool EverMadeChange = false; 2356ee358b4eb92298357687cb460dde8e26678aca2Jim Grosbach 236c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner while (1) { 237c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner bool MadeChange = false; 238c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner 239c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner // Process all basic blocks. 2406edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng CEBCandidates.clear(); 2416ee358b4eb92298357687cb460dde8e26678aca2Jim Grosbach for (MachineFunction::iterator I = MF.begin(), E = MF.end(); 242c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner I != E; ++I) 243c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner MadeChange |= ProcessBlock(*I); 2446ee358b4eb92298357687cb460dde8e26678aca2Jim Grosbach 245c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner // If this iteration over the code changed anything, keep iterating. 246c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner if (!MadeChange) break; 247c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner EverMadeChange = true; 2486ee358b4eb92298357687cb460dde8e26678aca2Jim Grosbach } 249c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner return EverMadeChange; 250c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner} 251c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner 252c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattnerbool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) { 253c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner // Can't sink anything out of a block that has less than two successors. 254296185c264a47cadd52c8d3290a54837cc32cbe5Chris Lattner if (MBB.succ_size() <= 1 || MBB.empty()) return false; 255296185c264a47cadd52c8d3290a54837cc32cbe5Chris Lattner 256c4ae94dee8c9a07334de7ffd85c45893208cca77Dan Gohman // Don't bother sinking code out of unreachable blocks. In addition to being 2576ee358b4eb92298357687cb460dde8e26678aca2Jim Grosbach // unprofitable, it can also lead to infinite looping, because in an 2586ee358b4eb92298357687cb460dde8e26678aca2Jim Grosbach // unreachable loop there may be nowhere to stop. 259c4ae94dee8c9a07334de7ffd85c45893208cca77Dan Gohman if (!DT->isReachableFromEntry(&MBB)) return false; 260c4ae94dee8c9a07334de7ffd85c45893208cca77Dan Gohman 261296185c264a47cadd52c8d3290a54837cc32cbe5Chris Lattner bool MadeChange = false; 262296185c264a47cadd52c8d3290a54837cc32cbe5Chris Lattner 263aad193a7e9f8eb4b558e16c2b54c31dee54f5f1eChris Lattner // Walk the basic block bottom-up. Remember if we saw a store. 264296185c264a47cadd52c8d3290a54837cc32cbe5Chris Lattner MachineBasicBlock::iterator I = MBB.end(); 265296185c264a47cadd52c8d3290a54837cc32cbe5Chris Lattner --I; 266296185c264a47cadd52c8d3290a54837cc32cbe5Chris Lattner bool ProcessedBegin, SawStore = false; 267296185c264a47cadd52c8d3290a54837cc32cbe5Chris Lattner do { 268296185c264a47cadd52c8d3290a54837cc32cbe5Chris Lattner MachineInstr *MI = I; // The instruction to sink. 2696ee358b4eb92298357687cb460dde8e26678aca2Jim Grosbach 270296185c264a47cadd52c8d3290a54837cc32cbe5Chris Lattner // Predecrement I (if it's not begin) so that it isn't invalidated by 271296185c264a47cadd52c8d3290a54837cc32cbe5Chris Lattner // sinking. 272296185c264a47cadd52c8d3290a54837cc32cbe5Chris Lattner ProcessedBegin = I == MBB.begin(); 273296185c264a47cadd52c8d3290a54837cc32cbe5Chris Lattner if (!ProcessedBegin) 274296185c264a47cadd52c8d3290a54837cc32cbe5Chris Lattner --I; 275b0812f114b83a32c4b90a4b553c7177c557558b5Dale Johannesen 276b0812f114b83a32c4b90a4b553c7177c557558b5Dale Johannesen if (MI->isDebugValue()) 277b0812f114b83a32c4b90a4b553c7177c557558b5Dale Johannesen continue; 278b0812f114b83a32c4b90a4b553c7177c557558b5Dale Johannesen 279cfea985f5319991fcb1feac3e66f645da4a0b507Evan Cheng bool Joined = PerformTrivialForwardCoalescing(MI, &MBB); 280cfea985f5319991fcb1feac3e66f645da4a0b507Evan Cheng if (Joined) { 281cfea985f5319991fcb1feac3e66f645da4a0b507Evan Cheng MadeChange = true; 2826edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng continue; 283cfea985f5319991fcb1feac3e66f645da4a0b507Evan Cheng } 2846edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng 285296185c264a47cadd52c8d3290a54837cc32cbe5Chris Lattner if (SinkInstruction(MI, SawStore)) 286296185c264a47cadd52c8d3290a54837cc32cbe5Chris Lattner ++NumSunk, MadeChange = true; 2876ee358b4eb92298357687cb460dde8e26678aca2Jim Grosbach 288296185c264a47cadd52c8d3290a54837cc32cbe5Chris Lattner // If we just processed the first instruction in the block, we're done. 289296185c264a47cadd52c8d3290a54837cc32cbe5Chris Lattner } while (!ProcessedBegin); 2906ee358b4eb92298357687cb460dde8e26678aca2Jim Grosbach 291c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner return MadeChange; 292c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner} 293c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner 2946edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Chengbool MachineSinking::isWorthBreakingCriticalEdge(MachineInstr *MI, 2956edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng MachineBasicBlock *From, 2966edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng MachineBasicBlock *To) { 2976edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // FIXME: Need much better heuristics. 2986edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng 2996edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // If the pass has already considered breaking this edge (during this pass 3006edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // through the function), then let's go ahead and break it. This means 3016edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // sinking multiple "cheap" instructions into the same block. 3026edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng if (!CEBCandidates.insert(std::make_pair(From, To))) 3036edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng return true; 3046edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng 3055a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (!MI->isCopy() && !MI->isAsCheapAsAMove()) 3066edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng return true; 3076edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng 3086edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // MI is cheap, we probably don't want to break the critical edge for it. 3096edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // However, if this would allow some definitions of its source operands 3106edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // to be sunk then it's probably worth it. 3116edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 3126edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng const MachineOperand &MO = MI->getOperand(i); 3136edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng if (!MO.isReg()) continue; 3146edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng unsigned Reg = MO.getReg(); 3156edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng if (Reg == 0 || !TargetRegisterInfo::isPhysicalRegister(Reg)) 3166edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng continue; 3176edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng if (MRI->hasOneNonDBGUse(Reg)) 3186edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng return true; 3196edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng } 3206edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng 3216edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng return false; 3226edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng} 3236edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng 3246edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan ChengMachineBasicBlock *MachineSinking::SplitCriticalEdge(MachineInstr *MI, 3256edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng MachineBasicBlock *FromBB, 3266edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng MachineBasicBlock *ToBB, 3277af6dc47a552d0d7d09752ad2e747d3973125b48Evan Cheng bool BreakPHIEdge) { 3286edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng if (!isWorthBreakingCriticalEdge(MI, FromBB, ToBB)) 3296edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng return 0; 3306edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng 3314dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng // Avoid breaking back edge. From == To means backedge for single BB loop. 33244be1a8d661cfab0cc3d11b0dd158271b2d2ca04Evan Cheng if (!SplitEdges || FromBB == ToBB) 3334dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng return 0; 3344dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng 3356edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // Check for backedges of more "complex" loops. 3366edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng if (LI->getLoopFor(FromBB) == LI->getLoopFor(ToBB) && 3376edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng LI->isLoopHeader(ToBB)) 3386edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng return 0; 3396edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng 3406edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // It's not always legal to break critical edges and sink the computation 3416edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // to the edge. 3426edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // 3436edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // BB#1: 3446edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // v1024 3456edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // Beq BB#3 3466edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // <fallthrough> 3476edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // BB#2: 3486edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // ... no uses of v1024 3496edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // <fallthrough> 3506edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // BB#3: 3516edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // ... 3526edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // = v1024 3536edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // 3546edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // If BB#1 -> BB#3 edge is broken and computation of v1024 is inserted: 3556edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // 3566edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // BB#1: 3576edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // ... 3586edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // Bne BB#2 3596edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // BB#4: 3606edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // v1024 = 3616edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // B BB#3 3626edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // BB#2: 3636edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // ... no uses of v1024 3646edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // <fallthrough> 3656edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // BB#3: 3666edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // ... 3676edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // = v1024 3686edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // 3696edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // This is incorrect since v1024 is not computed along the BB#1->BB#2->BB#3 3706edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // flow. We need to ensure the new basic block where the computation is 3716edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // sunk to dominates all the uses. 3726edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // It's only legal to break critical edge and sink the computation to the 3736edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // new block if all the predecessors of "To", except for "From", are 3746edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // not dominated by "From". Given SSA property, this means these 3756edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // predecessors are dominated by "To". 3766edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // 3776edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // There is no need to do this check if all the uses are PHI nodes. PHI 3786edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng // sources are only defined on the specific predecessor edges. 3797af6dc47a552d0d7d09752ad2e747d3973125b48Evan Cheng if (!BreakPHIEdge) { 3804dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng for (MachineBasicBlock::pred_iterator PI = ToBB->pred_begin(), 3814dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng E = ToBB->pred_end(); PI != E; ++PI) { 3824dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng if (*PI == FromBB) 3834dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng continue; 3844dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng if (!DT->dominates(ToBB, *PI)) 3854dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng return 0; 3864dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng } 3874dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng } 3884dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng 3896edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng return FromBB->SplitCriticalEdge(ToBB, this); 3904dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng} 3914dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng 392b0cdf8a4466d02c66c84b6b30953709fa9225a30Evan Chengstatic bool AvoidsSinking(MachineInstr *MI, MachineRegisterInfo *MRI) { 393b0cdf8a4466d02c66c84b6b30953709fa9225a30Evan Cheng return MI->isInsertSubreg() || MI->isSubregToReg() || MI->isRegSequence(); 394b0cdf8a4466d02c66c84b6b30953709fa9225a30Evan Cheng} 395b0cdf8a4466d02c66c84b6b30953709fa9225a30Evan Cheng 3961df91b0e54bc62f8fc7a06a4f75220e40aa2dfe0Andrew Trick/// collectDebgValues - Scan instructions following MI and collect any 397541a81cc2bb8b66960e788b1d8441536354b79b8Devang Patel/// matching DBG_VALUEs. 3981df91b0e54bc62f8fc7a06a4f75220e40aa2dfe0Andrew Trickstatic void collectDebugValues(MachineInstr *MI, 399541a81cc2bb8b66960e788b1d8441536354b79b8Devang Patel SmallVector<MachineInstr *, 2> & DbgValues) { 400541a81cc2bb8b66960e788b1d8441536354b79b8Devang Patel DbgValues.clear(); 401541a81cc2bb8b66960e788b1d8441536354b79b8Devang Patel if (!MI->getOperand(0).isReg()) 402541a81cc2bb8b66960e788b1d8441536354b79b8Devang Patel return; 403541a81cc2bb8b66960e788b1d8441536354b79b8Devang Patel 404541a81cc2bb8b66960e788b1d8441536354b79b8Devang Patel MachineBasicBlock::iterator DI = MI; ++DI; 405541a81cc2bb8b66960e788b1d8441536354b79b8Devang Patel for (MachineBasicBlock::iterator DE = MI->getParent()->end(); 406541a81cc2bb8b66960e788b1d8441536354b79b8Devang Patel DI != DE; ++DI) { 407541a81cc2bb8b66960e788b1d8441536354b79b8Devang Patel if (!DI->isDebugValue()) 408541a81cc2bb8b66960e788b1d8441536354b79b8Devang Patel return; 409541a81cc2bb8b66960e788b1d8441536354b79b8Devang Patel if (DI->getOperand(0).isReg() && 410541a81cc2bb8b66960e788b1d8441536354b79b8Devang Patel DI->getOperand(0).getReg() == MI->getOperand(0).getReg()) 411541a81cc2bb8b66960e788b1d8441536354b79b8Devang Patel DbgValues.push_back(DI); 412541a81cc2bb8b66960e788b1d8441536354b79b8Devang Patel } 413541a81cc2bb8b66960e788b1d8441536354b79b8Devang Patel} 414541a81cc2bb8b66960e788b1d8441536354b79b8Devang Patel 4155211134fbd35bf0befc60888860010b23c27ee5aDevang Patel/// isPostDominatedBy - Return true if A is post dominated by B. 4165211134fbd35bf0befc60888860010b23c27ee5aDevang Patelstatic bool isPostDominatedBy(MachineBasicBlock *A, MachineBasicBlock *B) { 4175211134fbd35bf0befc60888860010b23c27ee5aDevang Patel 4185211134fbd35bf0befc60888860010b23c27ee5aDevang Patel // FIXME - Use real post dominator. 4195211134fbd35bf0befc60888860010b23c27ee5aDevang Patel if (A->succ_size() != 2) 4205211134fbd35bf0befc60888860010b23c27ee5aDevang Patel return false; 4215211134fbd35bf0befc60888860010b23c27ee5aDevang Patel MachineBasicBlock::succ_iterator I = A->succ_begin(); 4225211134fbd35bf0befc60888860010b23c27ee5aDevang Patel if (B == *I) 4235211134fbd35bf0befc60888860010b23c27ee5aDevang Patel ++I; 4245211134fbd35bf0befc60888860010b23c27ee5aDevang Patel MachineBasicBlock *OtherSuccBlock = *I; 4255211134fbd35bf0befc60888860010b23c27ee5aDevang Patel if (OtherSuccBlock->succ_size() != 1 || 4265211134fbd35bf0befc60888860010b23c27ee5aDevang Patel *(OtherSuccBlock->succ_begin()) != B) 4275211134fbd35bf0befc60888860010b23c27ee5aDevang Patel return false; 4285211134fbd35bf0befc60888860010b23c27ee5aDevang Patel 4295211134fbd35bf0befc60888860010b23c27ee5aDevang Patel return true; 4305211134fbd35bf0befc60888860010b23c27ee5aDevang Patel} 4315211134fbd35bf0befc60888860010b23c27ee5aDevang Patel 4325211134fbd35bf0befc60888860010b23c27ee5aDevang Patel/// isProfitableToSinkTo - Return true if it is profitable to sink MI. 4331df91b0e54bc62f8fc7a06a4f75220e40aa2dfe0Andrew Trickbool MachineSinking::isProfitableToSinkTo(unsigned Reg, MachineInstr *MI, 4345211134fbd35bf0befc60888860010b23c27ee5aDevang Patel MachineBasicBlock *MBB, 4355211134fbd35bf0befc60888860010b23c27ee5aDevang Patel MachineBasicBlock *SuccToSinkTo) { 4365211134fbd35bf0befc60888860010b23c27ee5aDevang Patel assert (MI && "Invalid MachineInstr!"); 4375211134fbd35bf0befc60888860010b23c27ee5aDevang Patel assert (SuccToSinkTo && "Invalid SinkTo Candidate BB"); 4385211134fbd35bf0befc60888860010b23c27ee5aDevang Patel 4395211134fbd35bf0befc60888860010b23c27ee5aDevang Patel if (MBB == SuccToSinkTo) 4405211134fbd35bf0befc60888860010b23c27ee5aDevang Patel return false; 4415211134fbd35bf0befc60888860010b23c27ee5aDevang Patel 4425211134fbd35bf0befc60888860010b23c27ee5aDevang Patel // It is profitable if SuccToSinkTo does not post dominate current block. 4435211134fbd35bf0befc60888860010b23c27ee5aDevang Patel if (!isPostDominatedBy(MBB, SuccToSinkTo)) 4445211134fbd35bf0befc60888860010b23c27ee5aDevang Patel return true; 4455211134fbd35bf0befc60888860010b23c27ee5aDevang Patel 4465211134fbd35bf0befc60888860010b23c27ee5aDevang Patel // Check if only use in post dominated block is PHI instruction. 4475211134fbd35bf0befc60888860010b23c27ee5aDevang Patel bool NonPHIUse = false; 4485211134fbd35bf0befc60888860010b23c27ee5aDevang Patel for (MachineRegisterInfo::use_nodbg_iterator 4495211134fbd35bf0befc60888860010b23c27ee5aDevang Patel I = MRI->use_nodbg_begin(Reg), E = MRI->use_nodbg_end(); 4505211134fbd35bf0befc60888860010b23c27ee5aDevang Patel I != E; ++I) { 4515211134fbd35bf0befc60888860010b23c27ee5aDevang Patel MachineInstr *UseInst = &*I; 4525211134fbd35bf0befc60888860010b23c27ee5aDevang Patel MachineBasicBlock *UseBlock = UseInst->getParent(); 4535211134fbd35bf0befc60888860010b23c27ee5aDevang Patel if (UseBlock == SuccToSinkTo && !UseInst->isPHI()) 4545211134fbd35bf0befc60888860010b23c27ee5aDevang Patel NonPHIUse = true; 4555211134fbd35bf0befc60888860010b23c27ee5aDevang Patel } 4565211134fbd35bf0befc60888860010b23c27ee5aDevang Patel if (!NonPHIUse) 4575211134fbd35bf0befc60888860010b23c27ee5aDevang Patel return true; 4585211134fbd35bf0befc60888860010b23c27ee5aDevang Patel 4595211134fbd35bf0befc60888860010b23c27ee5aDevang Patel // If SuccToSinkTo post dominates then also it may be profitable if MI 4605211134fbd35bf0befc60888860010b23c27ee5aDevang Patel // can further profitably sinked into another block in next round. 4615211134fbd35bf0befc60888860010b23c27ee5aDevang Patel bool BreakPHIEdge = false; 4625211134fbd35bf0befc60888860010b23c27ee5aDevang Patel // FIXME - If finding successor is compile time expensive then catch results. 4635211134fbd35bf0befc60888860010b23c27ee5aDevang Patel if (MachineBasicBlock *MBB2 = FindSuccToSinkTo(MI, SuccToSinkTo, BreakPHIEdge)) 4645211134fbd35bf0befc60888860010b23c27ee5aDevang Patel return isProfitableToSinkTo(Reg, MI, SuccToSinkTo, MBB2); 4655211134fbd35bf0befc60888860010b23c27ee5aDevang Patel 4665211134fbd35bf0befc60888860010b23c27ee5aDevang Patel // If SuccToSinkTo is final destination and it is a post dominator of current 4675211134fbd35bf0befc60888860010b23c27ee5aDevang Patel // block then it is not profitable to sink MI into SuccToSinkTo block. 4685211134fbd35bf0befc60888860010b23c27ee5aDevang Patel return false; 4695211134fbd35bf0befc60888860010b23c27ee5aDevang Patel} 4705211134fbd35bf0befc60888860010b23c27ee5aDevang Patel 471e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel/// FindSuccToSinkTo - Find a successor to sink this instruction to. 472e265bcf1a609c81c197971cd392e98a12d97162dDevang PatelMachineBasicBlock *MachineSinking::FindSuccToSinkTo(MachineInstr *MI, 4735211134fbd35bf0befc60888860010b23c27ee5aDevang Patel MachineBasicBlock *MBB, 4745211134fbd35bf0befc60888860010b23c27ee5aDevang Patel bool &BreakPHIEdge) { 4755211134fbd35bf0befc60888860010b23c27ee5aDevang Patel 4765211134fbd35bf0befc60888860010b23c27ee5aDevang Patel assert (MI && "Invalid MachineInstr!"); 4775211134fbd35bf0befc60888860010b23c27ee5aDevang Patel assert (MBB && "Invalid MachineBasicBlock!"); 4786ee358b4eb92298357687cb460dde8e26678aca2Jim Grosbach 479c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner // Loop over all the operands of the specified instruction. If there is 480c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner // anything we can't handle, bail out. 4816ee358b4eb92298357687cb460dde8e26678aca2Jim Grosbach 482c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner // SuccToSinkTo - This is the successor to sink this instruction to, once we 483c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner // decide. 484c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner MachineBasicBlock *SuccToSinkTo = 0; 485c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 486c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner const MachineOperand &MO = MI->getOperand(i); 487d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg()) continue; // Ignore non-register operands. 4886ee358b4eb92298357687cb460dde8e26678aca2Jim Grosbach 489c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner unsigned Reg = MO.getReg(); 490c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner if (Reg == 0) continue; 4916ee358b4eb92298357687cb460dde8e26678aca2Jim Grosbach 4926f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 49319778e7558bc161b87920c5be9cc01bb84a08de2Dan Gohman if (MO.isUse()) { 49419778e7558bc161b87920c5be9cc01bb84a08de2Dan Gohman // If the physreg has no defs anywhere, it's just an ambient register 49545094e34bcbb133aa0bbe55710e25369df0e02edDan Gohman // and we can freely move its uses. Alternatively, if it's allocatable, 49645094e34bcbb133aa0bbe55710e25369df0e02edDan Gohman // it could get allocated to something with a def during allocation. 497c035c940a656f34a58ebe22fcc5f9b2a7d8e97fbJakob Stoklund Olesen if (!MRI->isConstantPhysReg(Reg, *MBB->getParent())) 498e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel return NULL; 499730c07e50d03be3d64fd4d808c590e6890d32178Bill Wendling } else if (!MO.isDead()) { 500730c07e50d03be3d64fd4d808c590e6890d32178Bill Wendling // A def that isn't dead. We can't move it. 501e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel return NULL; 50219778e7558bc161b87920c5be9cc01bb84a08de2Dan Gohman } 503c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner } else { 504c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner // Virtual register uses are always safe to sink. 505c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner if (MO.isUse()) continue; 506b6f5417edb8ad11e06d3a6527e452945e5349a97Evan Cheng 507b6f5417edb8ad11e06d3a6527e452945e5349a97Evan Cheng // If it's not safe to move defs of the register class, then abort. 5086edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg))) 509e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel return NULL; 5106ee358b4eb92298357687cb460dde8e26678aca2Jim Grosbach 511e430e1c07278d28f58fd94bac508469b8c1d1933Chris Lattner // FIXME: This picks a successor to sink into based on having one 512e430e1c07278d28f58fd94bac508469b8c1d1933Chris Lattner // successor that dominates all the uses. However, there are cases where 513e430e1c07278d28f58fd94bac508469b8c1d1933Chris Lattner // sinking can happen but where the sink point isn't a successor. For 514e430e1c07278d28f58fd94bac508469b8c1d1933Chris Lattner // example: 5156ee358b4eb92298357687cb460dde8e26678aca2Jim Grosbach // 516e430e1c07278d28f58fd94bac508469b8c1d1933Chris Lattner // x = computation 517e430e1c07278d28f58fd94bac508469b8c1d1933Chris Lattner // if () {} else {} 518e430e1c07278d28f58fd94bac508469b8c1d1933Chris Lattner // use x 5196ee358b4eb92298357687cb460dde8e26678aca2Jim Grosbach // 52005c68374c1c73599a0b7044ad09fb4827d128ec5Bill Wendling // the instruction could be sunk over the whole diamond for the 521e430e1c07278d28f58fd94bac508469b8c1d1933Chris Lattner // if/then/else (or loop, etc), allowing it to be sunk into other blocks 522e430e1c07278d28f58fd94bac508469b8c1d1933Chris Lattner // after that. 5236ee358b4eb92298357687cb460dde8e26678aca2Jim Grosbach 524c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner // Virtual register defs can only be sunk if all their uses are in blocks 525c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner // dominated by one of the successors. 526c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner if (SuccToSinkTo) { 527c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner // If a previous operand picked a block to sink to, then this operand 528c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner // must be sinkable to the same block. 529e5e7946018844978d0ac09fdb35998a53b43ad34Evan Cheng bool LocalUse = false; 5305211134fbd35bf0befc60888860010b23c27ee5aDevang Patel if (!AllUsesDominatedByBlock(Reg, SuccToSinkTo, MBB, 5317af6dc47a552d0d7d09752ad2e747d3973125b48Evan Cheng BreakPHIEdge, LocalUse)) 532e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel return NULL; 53305c68374c1c73599a0b7044ad09fb4827d128ec5Bill Wendling 534c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner continue; 535c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner } 5366ee358b4eb92298357687cb460dde8e26678aca2Jim Grosbach 537c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner // Otherwise, we should look at all the successors and decide which one 538c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner // we should sink to. 53953b59d1d974184657edfd22779e0bb3653d164ecManman Ren // We give successors with smaller loop depth higher priority. 54053b59d1d974184657edfd22779e0bb3653d164ecManman Ren SmallVector<MachineBasicBlock*, 4> Succs(MBB->succ_begin(), MBB->succ_end()); 541f99efdf3290b438a2cd74304e4299d50bce2b397Manman Ren std::stable_sort(Succs.begin(), Succs.end(), SuccessorSorter(LI)); 54253b59d1d974184657edfd22779e0bb3653d164ecManman Ren for (SmallVector<MachineBasicBlock*, 4>::iterator SI = Succs.begin(), 54353b59d1d974184657edfd22779e0bb3653d164ecManman Ren E = Succs.end(); SI != E; ++SI) { 5445211134fbd35bf0befc60888860010b23c27ee5aDevang Patel MachineBasicBlock *SuccBlock = *SI; 545e5e7946018844978d0ac09fdb35998a53b43ad34Evan Cheng bool LocalUse = false; 5465211134fbd35bf0befc60888860010b23c27ee5aDevang Patel if (AllUsesDominatedByBlock(Reg, SuccBlock, MBB, 5477af6dc47a552d0d7d09752ad2e747d3973125b48Evan Cheng BreakPHIEdge, LocalUse)) { 548cf405ba7a6e9448b753d9b72940059530c70ea90Devang Patel SuccToSinkTo = SuccBlock; 549c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner break; 550c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner } 551c3439ad63f4d145ca7357b7918bd72dfde8213d3Evan Cheng if (LocalUse) 552c3439ad63f4d145ca7357b7918bd72dfde8213d3Evan Cheng // Def is used locally, it's never safe to move this def. 553e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel return NULL; 554c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner } 5556ee358b4eb92298357687cb460dde8e26678aca2Jim Grosbach 556c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner // If we couldn't find a block to sink to, ignore this instruction. 557c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner if (SuccToSinkTo == 0) 558e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel return NULL; 5595211134fbd35bf0befc60888860010b23c27ee5aDevang Patel else if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo)) 5605211134fbd35bf0befc60888860010b23c27ee5aDevang Patel return NULL; 561c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner } 562c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner } 5637f7f0902a640c26e9ce70b5869fc7de3b8b27918Devang Patel 5647f7f0902a640c26e9ce70b5869fc7de3b8b27918Devang Patel // It is not possible to sink an instruction into its own block. This can 5657f7f0902a640c26e9ce70b5869fc7de3b8b27918Devang Patel // happen with loops. 5665211134fbd35bf0befc60888860010b23c27ee5aDevang Patel if (MBB == SuccToSinkTo) 5677f7f0902a640c26e9ce70b5869fc7de3b8b27918Devang Patel return NULL; 5687f7f0902a640c26e9ce70b5869fc7de3b8b27918Devang Patel 5697f7f0902a640c26e9ce70b5869fc7de3b8b27918Devang Patel // It's not safe to sink instructions to EH landing pad. Control flow into 5707f7f0902a640c26e9ce70b5869fc7de3b8b27918Devang Patel // landing pad is implicitly defined. 5717f7f0902a640c26e9ce70b5869fc7de3b8b27918Devang Patel if (SuccToSinkTo && SuccToSinkTo->isLandingPad()) 5727f7f0902a640c26e9ce70b5869fc7de3b8b27918Devang Patel return NULL; 5737f7f0902a640c26e9ce70b5869fc7de3b8b27918Devang Patel 574e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel return SuccToSinkTo; 575e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel} 576e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel 577e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel/// SinkInstruction - Determine whether it is safe to sink the specified machine 578e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel/// instruction out of its current block into a successor. 579e265bcf1a609c81c197971cd392e98a12d97162dDevang Patelbool MachineSinking::SinkInstruction(MachineInstr *MI, bool &SawStore) { 580e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel // Don't sink insert_subreg, subreg_to_reg, reg_sequence. These are meant to 581e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel // be close to the source to make it easier to coalesce. 582e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel if (AvoidsSinking(MI, MRI)) 583e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel return false; 584e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel 585e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel // Check if it's safe to move the instruction. 586e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel if (!MI->isSafeToMove(TII, AA, SawStore)) 587e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel return false; 588e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel 589e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel // FIXME: This should include support for sinking instructions within the 590e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel // block they are currently in to shorten the live ranges. We often get 591e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel // instructions sunk into the top of a large block, but it would be better to 592e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel // also sink them down before their first use in the block. This xform has to 593e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel // be careful not to *increase* register pressure though, e.g. sinking 594e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel // "x = y + z" down if it kills y and z would increase the live ranges of y 595e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel // and z and only shrink the live range of x. 596e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel 597e265bcf1a609c81c197971cd392e98a12d97162dDevang Patel bool BreakPHIEdge = false; 5985211134fbd35bf0befc60888860010b23c27ee5aDevang Patel MachineBasicBlock *ParentBlock = MI->getParent(); 5995211134fbd35bf0befc60888860010b23c27ee5aDevang Patel MachineBasicBlock *SuccToSinkTo = FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge); 6006ee358b4eb92298357687cb460dde8e26678aca2Jim Grosbach 6019bb459b55411c45175e599f6f421b7a57060ee57Chris Lattner // If there are no outputs, it must have side-effects. 6029bb459b55411c45175e599f6f421b7a57060ee57Chris Lattner if (SuccToSinkTo == 0) 6039bb459b55411c45175e599f6f421b7a57060ee57Chris Lattner return false; 604b599979ab591a6f4557337a4190153094725ef45Evan Cheng 605869d60d39d579b2051a8e34f460de72f071c2172Bill Wendling 606d24c9d5f91442f893bebc2ea8d5ee845bc8b77a9Daniel Dunbar // If the instruction to move defines a dead physical register which is live 607d24c9d5f91442f893bebc2ea8d5ee845bc8b77a9Daniel Dunbar // when leaving the basic block, don't move it because it could turn into a 608d24c9d5f91442f893bebc2ea8d5ee845bc8b77a9Daniel Dunbar // "zombie" define of that preg. E.g., EFLAGS. (<rdar://problem/8030636>) 609730c07e50d03be3d64fd4d808c590e6890d32178Bill Wendling for (unsigned I = 0, E = MI->getNumOperands(); I != E; ++I) { 610730c07e50d03be3d64fd4d808c590e6890d32178Bill Wendling const MachineOperand &MO = MI->getOperand(I); 611730c07e50d03be3d64fd4d808c590e6890d32178Bill Wendling if (!MO.isReg()) continue; 612730c07e50d03be3d64fd4d808c590e6890d32178Bill Wendling unsigned Reg = MO.getReg(); 613730c07e50d03be3d64fd4d808c590e6890d32178Bill Wendling if (Reg == 0 || !TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 614730c07e50d03be3d64fd4d808c590e6890d32178Bill Wendling if (SuccToSinkTo->isLiveIn(Reg)) 615869d60d39d579b2051a8e34f460de72f071c2172Bill Wendling return false; 616730c07e50d03be3d64fd4d808c590e6890d32178Bill Wendling } 617869d60d39d579b2051a8e34f460de72f071c2172Bill Wendling 61805c68374c1c73599a0b7044ad09fb4827d128ec5Bill Wendling DEBUG(dbgs() << "Sink instr " << *MI << "\tinto block " << *SuccToSinkTo); 61905c68374c1c73599a0b7044ad09fb4827d128ec5Bill Wendling 620c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner // If the block has multiple predecessors, this would introduce computation on 621c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner // a path that it doesn't already exist. We could split the critical edge, 622c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner // but for now we just punt. 623c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner if (SuccToSinkTo->pred_size() > 1) { 6248d17160e2cf9a1645b4b06b0cd575aef6195b108Jakob Stoklund Olesen // We cannot sink a load across a critical edge - there may be stores in 6258d17160e2cf9a1645b4b06b0cd575aef6195b108Jakob Stoklund Olesen // other code paths. 6264dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng bool TryBreak = false; 6278d17160e2cf9a1645b4b06b0cd575aef6195b108Jakob Stoklund Olesen bool store = true; 6288d17160e2cf9a1645b4b06b0cd575aef6195b108Jakob Stoklund Olesen if (!MI->isSafeToMove(TII, AA, store)) { 629f942c13af8187415e59e82e0bc92420c6fd59009Evan Cheng DEBUG(dbgs() << " *** NOTE: Won't sink load along critical edge.\n"); 6304dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng TryBreak = true; 6318d17160e2cf9a1645b4b06b0cd575aef6195b108Jakob Stoklund Olesen } 6328d17160e2cf9a1645b4b06b0cd575aef6195b108Jakob Stoklund Olesen 6338d17160e2cf9a1645b4b06b0cd575aef6195b108Jakob Stoklund Olesen // We don't want to sink across a critical edge if we don't dominate the 6348d17160e2cf9a1645b4b06b0cd575aef6195b108Jakob Stoklund Olesen // successor. We could be introducing calculations to new code paths. 6354dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng if (!TryBreak && !DT->dominates(ParentBlock, SuccToSinkTo)) { 636f942c13af8187415e59e82e0bc92420c6fd59009Evan Cheng DEBUG(dbgs() << " *** NOTE: Critical edge found\n"); 6374dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng TryBreak = true; 6388d17160e2cf9a1645b4b06b0cd575aef6195b108Jakob Stoklund Olesen } 6398d17160e2cf9a1645b4b06b0cd575aef6195b108Jakob Stoklund Olesen 640626f3d7a57f4f2a46880331fdacce259195213efJakob Stoklund Olesen // Don't sink instructions into a loop. 6414dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng if (!TryBreak && LI->isLoopHeader(SuccToSinkTo)) { 642f942c13af8187415e59e82e0bc92420c6fd59009Evan Cheng DEBUG(dbgs() << " *** NOTE: Loop header found\n"); 6434dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng TryBreak = true; 644626f3d7a57f4f2a46880331fdacce259195213efJakob Stoklund Olesen } 645626f3d7a57f4f2a46880331fdacce259195213efJakob Stoklund Olesen 6468d17160e2cf9a1645b4b06b0cd575aef6195b108Jakob Stoklund Olesen // Otherwise we are OK with sinking along a critical edge. 6474dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng if (!TryBreak) 6484dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng DEBUG(dbgs() << "Sinking along critical edge.\n"); 6494dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng else { 6506edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng MachineBasicBlock *NewSucc = 6517af6dc47a552d0d7d09752ad2e747d3973125b48Evan Cheng SplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, BreakPHIEdge); 6524dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng if (!NewSucc) { 6536edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to " 6546edb0eac87a6e46b89de3ad5d8e39c41969e2a54Evan Cheng "break critical edge\n"); 6554dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng return false; 6564dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng } else { 657f942c13af8187415e59e82e0bc92420c6fd59009Evan Cheng DEBUG(dbgs() << " *** Splitting critical edge:" 6584dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng " BB#" << ParentBlock->getNumber() 6594dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng << " -- BB#" << NewSucc->getNumber() 6604dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng << " -- BB#" << SuccToSinkTo->getNumber() << '\n'); 6614dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng SuccToSinkTo = NewSucc; 6624dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng ++NumSplit; 6637af6dc47a552d0d7d09752ad2e747d3973125b48Evan Cheng BreakPHIEdge = false; 6644dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng } 6654dc301a7c5fc8e18e7773f8e0d2c495ae1cc44f7Evan Cheng } 666c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner } 6676ee358b4eb92298357687cb460dde8e26678aca2Jim Grosbach 6687af6dc47a552d0d7d09752ad2e747d3973125b48Evan Cheng if (BreakPHIEdge) { 6697af6dc47a552d0d7d09752ad2e747d3973125b48Evan Cheng // BreakPHIEdge is true if all the uses are in the successor MBB being 6707af6dc47a552d0d7d09752ad2e747d3973125b48Evan Cheng // sunken into and they are all PHI nodes. In this case, machine-sink must 6717af6dc47a552d0d7d09752ad2e747d3973125b48Evan Cheng // break the critical edge first. 6722399786b279b6db7077ac36020153714530365dfEvan Cheng MachineBasicBlock *NewSucc = SplitCriticalEdge(MI, ParentBlock, 6737af6dc47a552d0d7d09752ad2e747d3973125b48Evan Cheng SuccToSinkTo, BreakPHIEdge); 6742399786b279b6db7077ac36020153714530365dfEvan Cheng if (!NewSucc) { 6752399786b279b6db7077ac36020153714530365dfEvan Cheng DEBUG(dbgs() << " *** PUNTING: Not legal or profitable to " 6762399786b279b6db7077ac36020153714530365dfEvan Cheng "break critical edge\n"); 6772399786b279b6db7077ac36020153714530365dfEvan Cheng return false; 6782399786b279b6db7077ac36020153714530365dfEvan Cheng } 6792399786b279b6db7077ac36020153714530365dfEvan Cheng 6802399786b279b6db7077ac36020153714530365dfEvan Cheng DEBUG(dbgs() << " *** Splitting critical edge:" 6812399786b279b6db7077ac36020153714530365dfEvan Cheng " BB#" << ParentBlock->getNumber() 6822399786b279b6db7077ac36020153714530365dfEvan Cheng << " -- BB#" << NewSucc->getNumber() 6832399786b279b6db7077ac36020153714530365dfEvan Cheng << " -- BB#" << SuccToSinkTo->getNumber() << '\n'); 6842399786b279b6db7077ac36020153714530365dfEvan Cheng SuccToSinkTo = NewSucc; 6852399786b279b6db7077ac36020153714530365dfEvan Cheng ++NumSplit; 6862399786b279b6db7077ac36020153714530365dfEvan Cheng } 6872399786b279b6db7077ac36020153714530365dfEvan Cheng 68805c68374c1c73599a0b7044ad09fb4827d128ec5Bill Wendling // Determine where to insert into. Skip phi nodes. 689c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner MachineBasicBlock::iterator InsertPos = SuccToSinkTo->begin(); 6902399786b279b6db7077ac36020153714530365dfEvan Cheng while (InsertPos != SuccToSinkTo->end() && InsertPos->isPHI()) 691c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner ++InsertPos; 6926ee358b4eb92298357687cb460dde8e26678aca2Jim Grosbach 693541a81cc2bb8b66960e788b1d8441536354b79b8Devang Patel // collect matching debug values. 694541a81cc2bb8b66960e788b1d8441536354b79b8Devang Patel SmallVector<MachineInstr *, 2> DbgValuesToSink; 695541a81cc2bb8b66960e788b1d8441536354b79b8Devang Patel collectDebugValues(MI, DbgValuesToSink); 696541a81cc2bb8b66960e788b1d8441536354b79b8Devang Patel 697c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner // Move the instruction. 698c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner SuccToSinkTo->splice(InsertPos, ParentBlock, MI, 699c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner ++MachineBasicBlock::iterator(MI)); 700e6cd757e6800b9b94a6459ec148c0624c4f2e3c1Dan Gohman 701541a81cc2bb8b66960e788b1d8441536354b79b8Devang Patel // Move debug values. 702541a81cc2bb8b66960e788b1d8441536354b79b8Devang Patel for (SmallVector<MachineInstr *, 2>::iterator DBI = DbgValuesToSink.begin(), 703541a81cc2bb8b66960e788b1d8441536354b79b8Devang Patel DBE = DbgValuesToSink.end(); DBI != DBE; ++DBI) { 704541a81cc2bb8b66960e788b1d8441536354b79b8Devang Patel MachineInstr *DbgMI = *DBI; 705541a81cc2bb8b66960e788b1d8441536354b79b8Devang Patel SuccToSinkTo->splice(InsertPos, ParentBlock, DbgMI, 706541a81cc2bb8b66960e788b1d8441536354b79b8Devang Patel ++MachineBasicBlock::iterator(DbgMI)); 707541a81cc2bb8b66960e788b1d8441536354b79b8Devang Patel } 708541a81cc2bb8b66960e788b1d8441536354b79b8Devang Patel 70905c68374c1c73599a0b7044ad09fb4827d128ec5Bill Wendling // Conservatively, clear any kill flags, since it's possible that they are no 71005c68374c1c73599a0b7044ad09fb4827d128ec5Bill Wendling // longer correct. 711e6cd757e6800b9b94a6459ec148c0624c4f2e3c1Dan Gohman MI->clearKillInfo(); 712e6cd757e6800b9b94a6459ec148c0624c4f2e3c1Dan Gohman 713c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner return true; 714c4ce73f666e7ab9a270982a575101df8aa6160d3Chris Lattner} 715