TwoAddressInstructionPass.cpp revision 296417
1193323Sed//===-- TwoAddressInstructionPass.cpp - Two-Address instruction pass ------===// 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// 10193323Sed// This file implements the TwoAddress instruction pass which is used 11193323Sed// by most register allocators. Two-Address instructions are rewritten 12193323Sed// from: 13193323Sed// 14193323Sed// A = B op C 15193323Sed// 16193323Sed// to: 17193323Sed// 18193323Sed// A = B 19193323Sed// A op= C 20193323Sed// 21193323Sed// Note that if a register allocator chooses to use this pass, that it 22193323Sed// has to be capable of handling the non-SSA nature of these rewritten 23193323Sed// virtual registers. 24193323Sed// 25193323Sed// It is also worth noting that the duplicate operand of the two 26193323Sed// address instruction is removed. 27193323Sed// 28193323Sed//===----------------------------------------------------------------------===// 29193323Sed 30193323Sed#include "llvm/CodeGen/Passes.h" 31249423Sdim#include "llvm/ADT/BitVector.h" 32249423Sdim#include "llvm/ADT/DenseMap.h" 33249423Sdim#include "llvm/ADT/STLExtras.h" 34249423Sdim#include "llvm/ADT/SmallSet.h" 35249423Sdim#include "llvm/ADT/Statistic.h" 36249423Sdim#include "llvm/Analysis/AliasAnalysis.h" 37239462Sdim#include "llvm/CodeGen/LiveIntervalAnalysis.h" 38193323Sed#include "llvm/CodeGen/LiveVariables.h" 39193323Sed#include "llvm/CodeGen/MachineFunctionPass.h" 40193323Sed#include "llvm/CodeGen/MachineInstr.h" 41210299Sed#include "llvm/CodeGen/MachineInstrBuilder.h" 42193323Sed#include "llvm/CodeGen/MachineRegisterInfo.h" 43249423Sdim#include "llvm/IR/Function.h" 44234353Sdim#include "llvm/MC/MCInstrItineraries.h" 45251662Sdim#include "llvm/Support/CommandLine.h" 46249423Sdim#include "llvm/Support/Debug.h" 47249423Sdim#include "llvm/Support/ErrorHandling.h" 48288943Sdim#include "llvm/Support/raw_ostream.h" 49193323Sed#include "llvm/Target/TargetInstrInfo.h" 50193323Sed#include "llvm/Target/TargetMachine.h" 51249423Sdim#include "llvm/Target/TargetRegisterInfo.h" 52280031Sdim#include "llvm/Target/TargetSubtargetInfo.h" 53193323Sedusing namespace llvm; 54193323Sed 55276479Sdim#define DEBUG_TYPE "twoaddrinstr" 56276479Sdim 57193323SedSTATISTIC(NumTwoAddressInstrs, "Number of two-address instructions"); 58193323SedSTATISTIC(NumCommuted , "Number of instructions commuted to coalesce"); 59193323SedSTATISTIC(NumAggrCommuted , "Number of instructions aggressively commuted"); 60193323SedSTATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address"); 61193323SedSTATISTIC(Num3AddrSunk, "Number of 3-address instructions sunk"); 62234353SdimSTATISTIC(NumReSchedUps, "Number of instructions re-scheduled up"); 63234353SdimSTATISTIC(NumReSchedDowns, "Number of instructions re-scheduled down"); 64193323Sed 65251662Sdim// Temporary flag to disable rescheduling. 66251662Sdimstatic cl::opt<bool> 67251662SdimEnableRescheduling("twoaddr-reschedule", 68251662Sdim cl::desc("Coalesce copies by rescheduling (default=true)"), 69251662Sdim cl::init(true), cl::Hidden); 70251662Sdim 71193323Sednamespace { 72243830Sdimclass TwoAddressInstructionPass : public MachineFunctionPass { 73243830Sdim MachineFunction *MF; 74243830Sdim const TargetInstrInfo *TII; 75243830Sdim const TargetRegisterInfo *TRI; 76243830Sdim const InstrItineraryData *InstrItins; 77243830Sdim MachineRegisterInfo *MRI; 78243830Sdim LiveVariables *LV; 79243830Sdim LiveIntervals *LIS; 80243830Sdim AliasAnalysis *AA; 81243830Sdim CodeGenOpt::Level OptLevel; 82193323Sed 83243830Sdim // The current basic block being processed. 84243830Sdim MachineBasicBlock *MBB; 85193323Sed 86296417Sdim // Keep track the distance of a MI from the start of the current basic block. 87243830Sdim DenseMap<MachineInstr*, unsigned> DistanceMap; 88193323Sed 89243830Sdim // Set of already processed instructions in the current block. 90243830Sdim SmallPtrSet<MachineInstr*, 8> Processed; 91193323Sed 92296417Sdim // A map from virtual registers to physical registers which are likely targets 93296417Sdim // to be coalesced to due to copies from physical registers to virtual 94296417Sdim // registers. e.g. v1024 = move r0. 95243830Sdim DenseMap<unsigned, unsigned> SrcRegMap; 96208599Srdivacky 97296417Sdim // A map from virtual registers to physical registers which are likely targets 98296417Sdim // to be coalesced to due to copies to physical registers from virtual 99296417Sdim // registers. e.g. r1 = move v1024. 100243830Sdim DenseMap<unsigned, unsigned> DstRegMap; 101193323Sed 102243830Sdim bool sink3AddrInstruction(MachineInstr *MI, unsigned Reg, 103243830Sdim MachineBasicBlock::iterator OldPos); 104193323Sed 105288943Sdim bool isRevCopyChain(unsigned FromReg, unsigned ToReg, int Maxlen); 106288943Sdim 107243830Sdim bool noUseAfterLastDef(unsigned Reg, unsigned Dist, unsigned &LastDef); 108193323Sed 109243830Sdim bool isProfitableToCommute(unsigned regA, unsigned regB, unsigned regC, 110243830Sdim MachineInstr *MI, unsigned Dist); 111193323Sed 112296417Sdim bool commuteInstruction(MachineInstr *MI, 113296417Sdim unsigned RegBIdx, unsigned RegCIdx, unsigned Dist); 114193323Sed 115243830Sdim bool isProfitableToConv3Addr(unsigned RegA, unsigned RegB); 116234353Sdim 117243830Sdim bool convertInstTo3Addr(MachineBasicBlock::iterator &mi, 118243830Sdim MachineBasicBlock::iterator &nmi, 119243830Sdim unsigned RegA, unsigned RegB, unsigned Dist); 120234353Sdim 121243830Sdim bool isDefTooClose(unsigned Reg, unsigned Dist, MachineInstr *MI); 122198090Srdivacky 123243830Sdim bool rescheduleMIBelowKill(MachineBasicBlock::iterator &mi, 124243830Sdim MachineBasicBlock::iterator &nmi, 125243830Sdim unsigned Reg); 126243830Sdim bool rescheduleKillAboveMI(MachineBasicBlock::iterator &mi, 127243830Sdim MachineBasicBlock::iterator &nmi, 128243830Sdim unsigned Reg); 129221345Sdim 130243830Sdim bool tryInstructionTransform(MachineBasicBlock::iterator &mi, 131243830Sdim MachineBasicBlock::iterator &nmi, 132243830Sdim unsigned SrcIdx, unsigned DstIdx, 133249423Sdim unsigned Dist, bool shouldOnlyCommute); 134198090Srdivacky 135296417Sdim bool tryInstructionCommute(MachineInstr *MI, 136296417Sdim unsigned DstOpIdx, 137296417Sdim unsigned BaseOpIdx, 138296417Sdim bool BaseOpKilled, 139296417Sdim unsigned Dist); 140243830Sdim void scanUses(unsigned DstReg); 141239462Sdim 142243830Sdim void processCopy(MachineInstr *MI); 143208599Srdivacky 144243830Sdim typedef SmallVector<std::pair<unsigned, unsigned>, 4> TiedPairList; 145243830Sdim typedef SmallDenseMap<unsigned, TiedPairList> TiedOperandMap; 146243830Sdim bool collectTiedOperands(MachineInstr *MI, TiedOperandMap&); 147243830Sdim void processTiedPairs(MachineInstr *MI, TiedPairList&, unsigned &Dist); 148249423Sdim void eliminateRegSequence(MachineBasicBlock::iterator&); 149208599Srdivacky 150243830Sdimpublic: 151243830Sdim static char ID; // Pass identification, replacement for typeid 152243830Sdim TwoAddressInstructionPass() : MachineFunctionPass(ID) { 153243830Sdim initializeTwoAddressInstructionPassPass(*PassRegistry::getPassRegistry()); 154243830Sdim } 155193323Sed 156276479Sdim void getAnalysisUsage(AnalysisUsage &AU) const override { 157243830Sdim AU.setPreservesCFG(); 158296417Sdim AU.addRequired<AAResultsWrapperPass>(); 159243830Sdim AU.addPreserved<LiveVariables>(); 160243830Sdim AU.addPreserved<SlotIndexes>(); 161243830Sdim AU.addPreserved<LiveIntervals>(); 162243830Sdim AU.addPreservedID(MachineLoopInfoID); 163243830Sdim AU.addPreservedID(MachineDominatorsID); 164243830Sdim MachineFunctionPass::getAnalysisUsage(AU); 165243830Sdim } 166193323Sed 167296417Sdim /// Pass entry point. 168276479Sdim bool runOnMachineFunction(MachineFunction&) override; 169243830Sdim}; 170243830Sdim} // end anonymous namespace 171243830Sdim 172193323Sedchar TwoAddressInstructionPass::ID = 0; 173218893SdimINITIALIZE_PASS_BEGIN(TwoAddressInstructionPass, "twoaddressinstruction", 174218893Sdim "Two-Address instruction pass", false, false) 175296417SdimINITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) 176218893SdimINITIALIZE_PASS_END(TwoAddressInstructionPass, "twoaddressinstruction", 177218893Sdim "Two-Address instruction pass", false, false) 178193323Sed 179212904Sdimchar &llvm::TwoAddressInstructionPassID = TwoAddressInstructionPass::ID; 180193323Sed 181249423Sdimstatic bool isPlainlyKilled(MachineInstr *MI, unsigned Reg, LiveIntervals *LIS); 182249423Sdim 183296417Sdim/// A two-address instruction has been converted to a three-address instruction 184296417Sdim/// to avoid clobbering a register. Try to sink it past the instruction that 185296417Sdim/// would kill the above mentioned register to reduce register pressure. 186243830Sdimbool TwoAddressInstructionPass:: 187243830Sdimsink3AddrInstruction(MachineInstr *MI, unsigned SavedReg, 188243830Sdim MachineBasicBlock::iterator OldPos) { 189226633Sdim // FIXME: Shouldn't we be trying to do this before we three-addressify the 190226633Sdim // instruction? After this transformation is done, we no longer need 191226633Sdim // the instruction to be in three-address form. 192226633Sdim 193193323Sed // Check if it's safe to move this instruction. 194193323Sed bool SeenStore = true; // Be conservative. 195288943Sdim if (!MI->isSafeToMove(AA, SeenStore)) 196193323Sed return false; 197193323Sed 198193323Sed unsigned DefReg = 0; 199193323Sed SmallSet<unsigned, 4> UseRegs; 200193323Sed 201296417Sdim for (const MachineOperand &MO : MI->operands()) { 202193323Sed if (!MO.isReg()) 203193323Sed continue; 204193323Sed unsigned MOReg = MO.getReg(); 205193323Sed if (!MOReg) 206193323Sed continue; 207193323Sed if (MO.isUse() && MOReg != SavedReg) 208193323Sed UseRegs.insert(MO.getReg()); 209193323Sed if (!MO.isDef()) 210193323Sed continue; 211193323Sed if (MO.isImplicit()) 212193323Sed // Don't try to move it if it implicitly defines a register. 213193323Sed return false; 214193323Sed if (DefReg) 215193323Sed // For now, don't move any instructions that define multiple registers. 216193323Sed return false; 217193323Sed DefReg = MO.getReg(); 218193323Sed } 219193323Sed 220193323Sed // Find the instruction that kills SavedReg. 221276479Sdim MachineInstr *KillMI = nullptr; 222249423Sdim if (LIS) { 223249423Sdim LiveInterval &LI = LIS->getInterval(SavedReg); 224249423Sdim assert(LI.end() != LI.begin() && 225249423Sdim "Reg should not have empty live interval."); 226249423Sdim 227249423Sdim SlotIndex MBBEndIdx = LIS->getMBBEndIdx(MBB).getPrevSlot(); 228249423Sdim LiveInterval::const_iterator I = LI.find(MBBEndIdx); 229249423Sdim if (I != LI.end() && I->start < MBBEndIdx) 230249423Sdim return false; 231249423Sdim 232249423Sdim --I; 233249423Sdim KillMI = LIS->getInstructionFromIndex(I->end); 234193323Sed } 235249423Sdim if (!KillMI) { 236296417Sdim for (MachineOperand &UseMO : MRI->use_nodbg_operands(SavedReg)) { 237249423Sdim if (!UseMO.isKill()) 238249423Sdim continue; 239249423Sdim KillMI = UseMO.getParent(); 240249423Sdim break; 241249423Sdim } 242249423Sdim } 243193323Sed 244226633Sdim // If we find the instruction that kills SavedReg, and it is in an 245226633Sdim // appropriate location, we can try to sink the current instruction 246226633Sdim // past it. 247226633Sdim if (!KillMI || KillMI->getParent() != MBB || KillMI == MI || 248239462Sdim KillMI == OldPos || KillMI->isTerminator()) 249193323Sed return false; 250193323Sed 251193323Sed // If any of the definitions are used by another instruction between the 252193323Sed // position and the kill use, then it's not safe to sink it. 253234353Sdim // 254193323Sed // FIXME: This can be sped up if there is an easy way to query whether an 255193323Sed // instruction is before or after another instruction. Then we can use 256193323Sed // MachineRegisterInfo def / use instead. 257276479Sdim MachineOperand *KillMO = nullptr; 258193323Sed MachineBasicBlock::iterator KillPos = KillMI; 259193323Sed ++KillPos; 260193323Sed 261193323Sed unsigned NumVisited = 0; 262276479Sdim for (MachineBasicBlock::iterator I = std::next(OldPos); I != KillPos; ++I) { 263193323Sed MachineInstr *OtherMI = I; 264203954Srdivacky // DBG_VALUE cannot be counted against the limit. 265203954Srdivacky if (OtherMI->isDebugValue()) 266203954Srdivacky continue; 267193323Sed if (NumVisited > 30) // FIXME: Arbitrary limit to reduce compile time cost. 268193323Sed return false; 269193323Sed ++NumVisited; 270193323Sed for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) { 271193323Sed MachineOperand &MO = OtherMI->getOperand(i); 272193323Sed if (!MO.isReg()) 273193323Sed continue; 274193323Sed unsigned MOReg = MO.getReg(); 275193323Sed if (!MOReg) 276193323Sed continue; 277193323Sed if (DefReg == MOReg) 278193323Sed return false; 279193323Sed 280249423Sdim if (MO.isKill() || (LIS && isPlainlyKilled(OtherMI, MOReg, LIS))) { 281193323Sed if (OtherMI == KillMI && MOReg == SavedReg) 282193323Sed // Save the operand that kills the register. We want to unset the kill 283193323Sed // marker if we can sink MI past it. 284193323Sed KillMO = &MO; 285193323Sed else if (UseRegs.count(MOReg)) 286193323Sed // One of the uses is killed before the destination. 287193323Sed return false; 288193323Sed } 289193323Sed } 290193323Sed } 291239462Sdim assert(KillMO && "Didn't find kill"); 292193323Sed 293249423Sdim if (!LIS) { 294249423Sdim // Update kill and LV information. 295249423Sdim KillMO->setIsKill(false); 296249423Sdim KillMO = MI->findRegisterUseOperand(SavedReg, false, TRI); 297249423Sdim KillMO->setIsKill(true); 298234353Sdim 299249423Sdim if (LV) 300249423Sdim LV->replaceKillInstruction(SavedReg, KillMI, MI); 301249423Sdim } 302193323Sed 303193323Sed // Move instruction to its destination. 304193323Sed MBB->remove(MI); 305193323Sed MBB->insert(KillPos, MI); 306193323Sed 307239462Sdim if (LIS) 308239462Sdim LIS->handleMove(MI); 309239462Sdim 310193323Sed ++Num3AddrSunk; 311193323Sed return true; 312193323Sed} 313193323Sed 314296417Sdim/// Return the MachineInstr* if it is the single def of the Reg in current BB. 315288943Sdimstatic MachineInstr *getSingleDef(unsigned Reg, MachineBasicBlock *BB, 316288943Sdim const MachineRegisterInfo *MRI) { 317288943Sdim MachineInstr *Ret = nullptr; 318288943Sdim for (MachineInstr &DefMI : MRI->def_instructions(Reg)) { 319288943Sdim if (DefMI.getParent() != BB || DefMI.isDebugValue()) 320288943Sdim continue; 321288943Sdim if (!Ret) 322288943Sdim Ret = &DefMI; 323288943Sdim else if (Ret != &DefMI) 324288943Sdim return nullptr; 325288943Sdim } 326288943Sdim return Ret; 327288943Sdim} 328288943Sdim 329288943Sdim/// Check if there is a reversed copy chain from FromReg to ToReg: 330288943Sdim/// %Tmp1 = copy %Tmp2; 331288943Sdim/// %FromReg = copy %Tmp1; 332288943Sdim/// %ToReg = add %FromReg ... 333288943Sdim/// %Tmp2 = copy %ToReg; 334288943Sdim/// MaxLen specifies the maximum length of the copy chain the func 335288943Sdim/// can walk through. 336288943Sdimbool TwoAddressInstructionPass::isRevCopyChain(unsigned FromReg, unsigned ToReg, 337288943Sdim int Maxlen) { 338288943Sdim unsigned TmpReg = FromReg; 339288943Sdim for (int i = 0; i < Maxlen; i++) { 340288943Sdim MachineInstr *Def = getSingleDef(TmpReg, MBB, MRI); 341288943Sdim if (!Def || !Def->isCopy()) 342288943Sdim return false; 343288943Sdim 344288943Sdim TmpReg = Def->getOperand(1).getReg(); 345288943Sdim 346288943Sdim if (TmpReg == ToReg) 347288943Sdim return true; 348288943Sdim } 349288943Sdim return false; 350288943Sdim} 351288943Sdim 352296417Sdim/// Return true if there are no intervening uses between the last instruction 353296417Sdim/// in the MBB that defines the specified register and the two-address 354296417Sdim/// instruction which is being processed. It also returns the last def location 355296417Sdim/// by reference. 356243830Sdimbool TwoAddressInstructionPass::noUseAfterLastDef(unsigned Reg, unsigned Dist, 357243830Sdim unsigned &LastDef) { 358193323Sed LastDef = 0; 359193323Sed unsigned LastUse = Dist; 360276479Sdim for (MachineOperand &MO : MRI->reg_operands(Reg)) { 361193323Sed MachineInstr *MI = MO.getParent(); 362203954Srdivacky if (MI->getParent() != MBB || MI->isDebugValue()) 363193323Sed continue; 364193323Sed DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI); 365193323Sed if (DI == DistanceMap.end()) 366193323Sed continue; 367193323Sed if (MO.isUse() && DI->second < LastUse) 368193323Sed LastUse = DI->second; 369193323Sed if (MO.isDef() && DI->second > LastDef) 370193323Sed LastDef = DI->second; 371193323Sed } 372193323Sed 373193323Sed return !(LastUse > LastDef && LastUse < Dist); 374193323Sed} 375193323Sed 376296417Sdim/// Return true if the specified MI is a copy instruction or an extract_subreg 377296417Sdim/// instruction. It also returns the source and destination registers and 378296417Sdim/// whether they are physical registers by reference. 379193323Sedstatic bool isCopyToReg(MachineInstr &MI, const TargetInstrInfo *TII, 380193323Sed unsigned &SrcReg, unsigned &DstReg, 381193323Sed bool &IsSrcPhys, bool &IsDstPhys) { 382193323Sed SrcReg = 0; 383193323Sed DstReg = 0; 384212904Sdim if (MI.isCopy()) { 385212904Sdim DstReg = MI.getOperand(0).getReg(); 386212904Sdim SrcReg = MI.getOperand(1).getReg(); 387212904Sdim } else if (MI.isInsertSubreg() || MI.isSubregToReg()) { 388212904Sdim DstReg = MI.getOperand(0).getReg(); 389212904Sdim SrcReg = MI.getOperand(2).getReg(); 390212904Sdim } else 391212904Sdim return false; 392193323Sed 393212904Sdim IsSrcPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg); 394212904Sdim IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); 395212904Sdim return true; 396193323Sed} 397193323Sed 398296417Sdim/// Test if the given register value, which is used by the 399296417Sdim/// given instruction, is killed by the given instruction. 400249423Sdimstatic bool isPlainlyKilled(MachineInstr *MI, unsigned Reg, 401249423Sdim LiveIntervals *LIS) { 402249423Sdim if (LIS && TargetRegisterInfo::isVirtualRegister(Reg) && 403249423Sdim !LIS->isNotInMIMap(MI)) { 404249423Sdim // FIXME: Sometimes tryInstructionTransform() will add instructions and 405249423Sdim // test whether they can be folded before keeping them. In this case it 406249423Sdim // sets a kill before recursively calling tryInstructionTransform() again. 407249423Sdim // If there is no interval available, we assume that this instruction is 408249423Sdim // one of those. A kill flag is manually inserted on the operand so the 409249423Sdim // check below will handle it. 410249423Sdim LiveInterval &LI = LIS->getInterval(Reg); 411249423Sdim // This is to match the kill flag version where undefs don't have kill 412249423Sdim // flags. 413249423Sdim if (!LI.hasAtLeastOneValue()) 414249423Sdim return false; 415249423Sdim 416249423Sdim SlotIndex useIdx = LIS->getInstructionIndex(MI); 417249423Sdim LiveInterval::const_iterator I = LI.find(useIdx); 418249423Sdim assert(I != LI.end() && "Reg must be live-in to use."); 419249423Sdim return !I->end.isBlock() && SlotIndex::isSameInstr(I->end, useIdx); 420249423Sdim } 421249423Sdim 422249423Sdim return MI->killsRegister(Reg); 423249423Sdim} 424249423Sdim 425296417Sdim/// Test if the given register value, which is used by the given 426193323Sed/// instruction, is killed by the given instruction. This looks through 427193323Sed/// coalescable copies to see if the original value is potentially not killed. 428193323Sed/// 429193323Sed/// For example, in this code: 430193323Sed/// 431193323Sed/// %reg1034 = copy %reg1024 432193323Sed/// %reg1035 = copy %reg1025<kill> 433193323Sed/// %reg1036 = add %reg1034<kill>, %reg1035<kill> 434193323Sed/// 435193323Sed/// %reg1034 is not considered to be killed, since it is copied from a 436193323Sed/// register which is not killed. Treating it as not killed lets the 437193323Sed/// normal heuristics commute the (two-address) add, which lets 438193323Sed/// coalescing eliminate the extra copy. 439193323Sed/// 440249423Sdim/// If allowFalsePositives is true then likely kills are treated as kills even 441249423Sdim/// if it can't be proven that they are kills. 442193323Sedstatic bool isKilled(MachineInstr &MI, unsigned Reg, 443193323Sed const MachineRegisterInfo *MRI, 444249423Sdim const TargetInstrInfo *TII, 445249423Sdim LiveIntervals *LIS, 446249423Sdim bool allowFalsePositives) { 447193323Sed MachineInstr *DefMI = &MI; 448193323Sed for (;;) { 449249423Sdim // All uses of physical registers are likely to be kills. 450249423Sdim if (TargetRegisterInfo::isPhysicalRegister(Reg) && 451249423Sdim (allowFalsePositives || MRI->hasOneUse(Reg))) 452249423Sdim return true; 453249423Sdim if (!isPlainlyKilled(DefMI, Reg, LIS)) 454193323Sed return false; 455193323Sed if (TargetRegisterInfo::isPhysicalRegister(Reg)) 456193323Sed return true; 457193323Sed MachineRegisterInfo::def_iterator Begin = MRI->def_begin(Reg); 458193323Sed // If there are multiple defs, we can't do a simple analysis, so just 459193323Sed // go with what the kill flag says. 460276479Sdim if (std::next(Begin) != MRI->def_end()) 461193323Sed return true; 462276479Sdim DefMI = Begin->getParent(); 463193323Sed bool IsSrcPhys, IsDstPhys; 464193323Sed unsigned SrcReg, DstReg; 465193323Sed // If the def is something other than a copy, then it isn't going to 466193323Sed // be coalesced, so follow the kill flag. 467193323Sed if (!isCopyToReg(*DefMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) 468193323Sed return true; 469193323Sed Reg = SrcReg; 470193323Sed } 471193323Sed} 472193323Sed 473296417Sdim/// Return true if the specified MI uses the specified register as a two-address 474296417Sdim/// use. If so, return the destination register by reference. 475193323Sedstatic bool isTwoAddrUse(MachineInstr &MI, unsigned Reg, unsigned &DstReg) { 476251662Sdim for (unsigned i = 0, NumOps = MI.getNumOperands(); i != NumOps; ++i) { 477193323Sed const MachineOperand &MO = MI.getOperand(i); 478193323Sed if (!MO.isReg() || !MO.isUse() || MO.getReg() != Reg) 479193323Sed continue; 480193323Sed unsigned ti; 481193323Sed if (MI.isRegTiedToDefOperand(i, &ti)) { 482193323Sed DstReg = MI.getOperand(ti).getReg(); 483193323Sed return true; 484193323Sed } 485193323Sed } 486193323Sed return false; 487193323Sed} 488193323Sed 489296417Sdim/// Given a register, if has a single in-basic block use, return the use 490296417Sdim/// instruction if it's a copy or a two-address use. 491193323Sedstatic 492193323SedMachineInstr *findOnlyInterestingUse(unsigned Reg, MachineBasicBlock *MBB, 493193323Sed MachineRegisterInfo *MRI, 494193323Sed const TargetInstrInfo *TII, 495193323Sed bool &IsCopy, 496193323Sed unsigned &DstReg, bool &IsDstPhys) { 497204792Srdivacky if (!MRI->hasOneNonDBGUse(Reg)) 498204792Srdivacky // None or more than one use. 499276479Sdim return nullptr; 500276479Sdim MachineInstr &UseMI = *MRI->use_instr_nodbg_begin(Reg); 501193323Sed if (UseMI.getParent() != MBB) 502276479Sdim return nullptr; 503193323Sed unsigned SrcReg; 504193323Sed bool IsSrcPhys; 505193323Sed if (isCopyToReg(UseMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) { 506193323Sed IsCopy = true; 507193323Sed return &UseMI; 508193323Sed } 509193323Sed IsDstPhys = false; 510193323Sed if (isTwoAddrUse(UseMI, Reg, DstReg)) { 511193323Sed IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); 512193323Sed return &UseMI; 513193323Sed } 514276479Sdim return nullptr; 515193323Sed} 516193323Sed 517296417Sdim/// Return the physical register the specified virtual register might be mapped 518296417Sdim/// to. 519193323Sedstatic unsigned 520193323SedgetMappedReg(unsigned Reg, DenseMap<unsigned, unsigned> &RegMap) { 521193323Sed while (TargetRegisterInfo::isVirtualRegister(Reg)) { 522193323Sed DenseMap<unsigned, unsigned>::iterator SI = RegMap.find(Reg); 523193323Sed if (SI == RegMap.end()) 524193323Sed return 0; 525193323Sed Reg = SI->second; 526193323Sed } 527193323Sed if (TargetRegisterInfo::isPhysicalRegister(Reg)) 528193323Sed return Reg; 529193323Sed return 0; 530193323Sed} 531193323Sed 532296417Sdim/// Return true if the two registers are equal or aliased. 533193323Sedstatic bool 534193323SedregsAreCompatible(unsigned RegA, unsigned RegB, const TargetRegisterInfo *TRI) { 535193323Sed if (RegA == RegB) 536193323Sed return true; 537193323Sed if (!RegA || !RegB) 538193323Sed return false; 539193323Sed return TRI->regsOverlap(RegA, RegB); 540193323Sed} 541193323Sed 542193323Sed 543296417Sdim/// Return true if it's potentially profitable to commute the two-address 544296417Sdim/// instruction that's being processed. 545193323Sedbool 546243830SdimTwoAddressInstructionPass:: 547243830SdimisProfitableToCommute(unsigned regA, unsigned regB, unsigned regC, 548243830Sdim MachineInstr *MI, unsigned Dist) { 549234353Sdim if (OptLevel == CodeGenOpt::None) 550234353Sdim return false; 551234353Sdim 552193323Sed // Determine if it's profitable to commute this two address instruction. In 553193323Sed // general, we want no uses between this instruction and the definition of 554193323Sed // the two-address register. 555193323Sed // e.g. 556193323Sed // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1 557193323Sed // %reg1029<def> = MOV8rr %reg1028 558193323Sed // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead> 559193323Sed // insert => %reg1030<def> = MOV8rr %reg1028 560193323Sed // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead> 561193323Sed // In this case, it might not be possible to coalesce the second MOV8rr 562193323Sed // instruction if the first one is coalesced. So it would be profitable to 563193323Sed // commute it: 564193323Sed // %reg1028<def> = EXTRACT_SUBREG %reg1027<kill>, 1 565193323Sed // %reg1029<def> = MOV8rr %reg1028 566193323Sed // %reg1029<def> = SHR8ri %reg1029, 7, %EFLAGS<imp-def,dead> 567193323Sed // insert => %reg1030<def> = MOV8rr %reg1029 568234353Sdim // %reg1030<def> = ADD8rr %reg1029<kill>, %reg1028<kill>, %EFLAGS<imp-def,dead> 569193323Sed 570249423Sdim if (!isPlainlyKilled(MI, regC, LIS)) 571193323Sed return false; 572193323Sed 573193323Sed // Ok, we have something like: 574193323Sed // %reg1030<def> = ADD8rr %reg1028<kill>, %reg1029<kill>, %EFLAGS<imp-def,dead> 575193323Sed // let's see if it's worth commuting it. 576193323Sed 577193323Sed // Look for situations like this: 578193323Sed // %reg1024<def> = MOV r1 579193323Sed // %reg1025<def> = MOV r0 580193323Sed // %reg1026<def> = ADD %reg1024, %reg1025 581193323Sed // r0 = MOV %reg1026 582193323Sed // Commute the ADD to hopefully eliminate an otherwise unavoidable copy. 583239462Sdim unsigned ToRegA = getMappedReg(regA, DstRegMap); 584239462Sdim if (ToRegA) { 585239462Sdim unsigned FromRegB = getMappedReg(regB, SrcRegMap); 586239462Sdim unsigned FromRegC = getMappedReg(regC, SrcRegMap); 587280031Sdim bool CompB = FromRegB && regsAreCompatible(FromRegB, ToRegA, TRI); 588280031Sdim bool CompC = FromRegC && regsAreCompatible(FromRegC, ToRegA, TRI); 589280031Sdim 590280031Sdim // Compute if any of the following are true: 591280031Sdim // -RegB is not tied to a register and RegC is compatible with RegA. 592280031Sdim // -RegB is tied to the wrong physical register, but RegC is. 593280031Sdim // -RegB is tied to the wrong physical register, and RegC isn't tied. 594280031Sdim if ((!FromRegB && CompC) || (FromRegB && !CompB && (!FromRegC || CompC))) 595280031Sdim return true; 596280031Sdim // Don't compute if any of the following are true: 597280031Sdim // -RegC is not tied to a register and RegB is compatible with RegA. 598280031Sdim // -RegC is tied to the wrong physical register, but RegB is. 599280031Sdim // -RegC is tied to the wrong physical register, and RegB isn't tied. 600280031Sdim if ((!FromRegC && CompB) || (FromRegC && !CompC && (!FromRegB || CompB))) 601280031Sdim return false; 602239462Sdim } 603193323Sed 604193323Sed // If there is a use of regC between its last def (could be livein) and this 605193323Sed // instruction, then bail. 606193323Sed unsigned LastDefC = 0; 607243830Sdim if (!noUseAfterLastDef(regC, Dist, LastDefC)) 608193323Sed return false; 609193323Sed 610193323Sed // If there is a use of regB between its last def (could be livein) and this 611193323Sed // instruction, then go ahead and make this transformation. 612193323Sed unsigned LastDefB = 0; 613243830Sdim if (!noUseAfterLastDef(regB, Dist, LastDefB)) 614193323Sed return true; 615193323Sed 616288943Sdim // Look for situation like this: 617288943Sdim // %reg101 = MOV %reg100 618288943Sdim // %reg102 = ... 619288943Sdim // %reg103 = ADD %reg102, %reg101 620288943Sdim // ... = %reg103 ... 621288943Sdim // %reg100 = MOV %reg103 622288943Sdim // If there is a reversed copy chain from reg101 to reg103, commute the ADD 623288943Sdim // to eliminate an otherwise unavoidable copy. 624288943Sdim // FIXME: 625288943Sdim // We can extend the logic further: If an pair of operands in an insn has 626288943Sdim // been merged, the insn could be regarded as a virtual copy, and the virtual 627288943Sdim // copy could also be used to construct a copy chain. 628288943Sdim // To more generally minimize register copies, ideally the logic of two addr 629288943Sdim // instruction pass should be integrated with register allocation pass where 630288943Sdim // interference graph is available. 631288943Sdim if (isRevCopyChain(regC, regA, 3)) 632288943Sdim return true; 633288943Sdim 634288943Sdim if (isRevCopyChain(regB, regA, 3)) 635288943Sdim return false; 636288943Sdim 637193323Sed // Since there are no intervening uses for both registers, then commute 638193323Sed // if the def of regC is closer. Its live interval is shorter. 639193323Sed return LastDefB && LastDefC && LastDefC > LastDefB; 640193323Sed} 641193323Sed 642296417Sdim/// Commute a two-address instruction and update the basic block, distance map, 643296417Sdim/// and live variables if needed. Return true if it is successful. 644296417Sdimbool TwoAddressInstructionPass::commuteInstruction(MachineInstr *MI, 645296417Sdim unsigned RegBIdx, 646296417Sdim unsigned RegCIdx, 647296417Sdim unsigned Dist) { 648296417Sdim unsigned RegC = MI->getOperand(RegCIdx).getReg(); 649202375Srdivacky DEBUG(dbgs() << "2addr: COMMUTING : " << *MI); 650296417Sdim MachineInstr *NewMI = TII->commuteInstruction(MI, false, RegBIdx, RegCIdx); 651193323Sed 652276479Sdim if (NewMI == nullptr) { 653202375Srdivacky DEBUG(dbgs() << "2addr: COMMUTING FAILED!\n"); 654193323Sed return false; 655193323Sed } 656193323Sed 657202375Srdivacky DEBUG(dbgs() << "2addr: COMMUTED TO: " << *NewMI); 658249423Sdim assert(NewMI == MI && 659249423Sdim "TargetInstrInfo::commuteInstruction() should not return a new " 660249423Sdim "instruction unless it was requested."); 661193323Sed 662193323Sed // Update source register map. 663193323Sed unsigned FromRegC = getMappedReg(RegC, SrcRegMap); 664193323Sed if (FromRegC) { 665193323Sed unsigned RegA = MI->getOperand(0).getReg(); 666193323Sed SrcRegMap[RegA] = FromRegC; 667193323Sed } 668193323Sed 669193323Sed return true; 670193323Sed} 671193323Sed 672296417Sdim/// Return true if it is profitable to convert the given 2-address instruction 673296417Sdim/// to a 3-address one. 674193323Sedbool 675221345SdimTwoAddressInstructionPass::isProfitableToConv3Addr(unsigned RegA,unsigned RegB){ 676193323Sed // Look for situations like this: 677193323Sed // %reg1024<def> = MOV r1 678193323Sed // %reg1025<def> = MOV r0 679193323Sed // %reg1026<def> = ADD %reg1024, %reg1025 680193323Sed // r2 = MOV %reg1026 681193323Sed // Turn ADD into a 3-address instruction to avoid a copy. 682221345Sdim unsigned FromRegB = getMappedReg(RegB, SrcRegMap); 683221345Sdim if (!FromRegB) 684221345Sdim return false; 685193323Sed unsigned ToRegA = getMappedReg(RegA, DstRegMap); 686221345Sdim return (ToRegA && !regsAreCompatible(FromRegB, ToRegA, TRI)); 687193323Sed} 688193323Sed 689296417Sdim/// Convert the specified two-address instruction into a three address one. 690296417Sdim/// Return true if this transformation was successful. 691193323Sedbool 692243830SdimTwoAddressInstructionPass::convertInstTo3Addr(MachineBasicBlock::iterator &mi, 693193323Sed MachineBasicBlock::iterator &nmi, 694218893Sdim unsigned RegA, unsigned RegB, 695218893Sdim unsigned Dist) { 696243830Sdim // FIXME: Why does convertToThreeAddress() need an iterator reference? 697296417Sdim MachineFunction::iterator MFI = MBB->getIterator(); 698243830Sdim MachineInstr *NewMI = TII->convertToThreeAddress(MFI, mi, LV); 699296417Sdim assert(MBB->getIterator() == MFI && 700296417Sdim "convertToThreeAddress changed iterator reference"); 701243830Sdim if (!NewMI) 702243830Sdim return false; 703193323Sed 704243830Sdim DEBUG(dbgs() << "2addr: CONVERTING 2-ADDR: " << *mi); 705243830Sdim DEBUG(dbgs() << "2addr: TO 3-ADDR: " << *NewMI); 706243830Sdim bool Sunk = false; 707239462Sdim 708249423Sdim if (LIS) 709249423Sdim LIS->ReplaceMachineInstrInMaps(mi, NewMI); 710193323Sed 711243830Sdim if (NewMI->findRegisterUseOperand(RegB, false, TRI)) 712243830Sdim // FIXME: Temporary workaround. If the new instruction doesn't 713243830Sdim // uses RegB, convertToThreeAddress must have created more 714243830Sdim // then one instruction. 715243830Sdim Sunk = sink3AddrInstruction(NewMI, RegB, mi); 716193323Sed 717243830Sdim MBB->erase(mi); // Nuke the old inst. 718218893Sdim 719243830Sdim if (!Sunk) { 720243830Sdim DistanceMap.insert(std::make_pair(NewMI, Dist)); 721243830Sdim mi = NewMI; 722276479Sdim nmi = std::next(mi); 723193323Sed } 724193323Sed 725243830Sdim // Update source and destination register maps. 726243830Sdim SrcRegMap.erase(RegA); 727243830Sdim DstRegMap.erase(RegB); 728243830Sdim return true; 729193323Sed} 730193323Sed 731296417Sdim/// Scan forward recursively for only uses, update maps if the use is a copy or 732296417Sdim/// a two-address instruction. 733221345Sdimvoid 734243830SdimTwoAddressInstructionPass::scanUses(unsigned DstReg) { 735221345Sdim SmallVector<unsigned, 4> VirtRegPairs; 736221345Sdim bool IsDstPhys; 737221345Sdim bool IsCopy = false; 738221345Sdim unsigned NewReg = 0; 739221345Sdim unsigned Reg = DstReg; 740221345Sdim while (MachineInstr *UseMI = findOnlyInterestingUse(Reg, MBB, MRI, TII,IsCopy, 741221345Sdim NewReg, IsDstPhys)) { 742280031Sdim if (IsCopy && !Processed.insert(UseMI).second) 743221345Sdim break; 744221345Sdim 745221345Sdim DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UseMI); 746221345Sdim if (DI != DistanceMap.end()) 747221345Sdim // Earlier in the same MBB.Reached via a back edge. 748221345Sdim break; 749221345Sdim 750221345Sdim if (IsDstPhys) { 751221345Sdim VirtRegPairs.push_back(NewReg); 752221345Sdim break; 753221345Sdim } 754221345Sdim bool isNew = SrcRegMap.insert(std::make_pair(NewReg, Reg)).second; 755221345Sdim if (!isNew) 756221345Sdim assert(SrcRegMap[NewReg] == Reg && "Can't map to two src registers!"); 757221345Sdim VirtRegPairs.push_back(NewReg); 758221345Sdim Reg = NewReg; 759221345Sdim } 760221345Sdim 761221345Sdim if (!VirtRegPairs.empty()) { 762221345Sdim unsigned ToReg = VirtRegPairs.back(); 763221345Sdim VirtRegPairs.pop_back(); 764221345Sdim while (!VirtRegPairs.empty()) { 765221345Sdim unsigned FromReg = VirtRegPairs.back(); 766221345Sdim VirtRegPairs.pop_back(); 767221345Sdim bool isNew = DstRegMap.insert(std::make_pair(FromReg, ToReg)).second; 768221345Sdim if (!isNew) 769221345Sdim assert(DstRegMap[FromReg] == ToReg &&"Can't map to two dst registers!"); 770221345Sdim ToReg = FromReg; 771221345Sdim } 772221345Sdim bool isNew = DstRegMap.insert(std::make_pair(DstReg, ToReg)).second; 773221345Sdim if (!isNew) 774221345Sdim assert(DstRegMap[DstReg] == ToReg && "Can't map to two dst registers!"); 775221345Sdim } 776221345Sdim} 777221345Sdim 778296417Sdim/// If the specified instruction is not yet processed, process it if it's a 779296417Sdim/// copy. For a copy instruction, we find the physical registers the 780193323Sed/// source and destination registers might be mapped to. These are kept in 781193323Sed/// point-to maps used to determine future optimizations. e.g. 782193323Sed/// v1024 = mov r0 783193323Sed/// v1025 = mov r1 784193323Sed/// v1026 = add v1024, v1025 785193323Sed/// r1 = mov r1026 786193323Sed/// If 'add' is a two-address instruction, v1024, v1026 are both potentially 787193323Sed/// coalesced to r0 (from the input side). v1025 is mapped to r1. v1026 is 788193323Sed/// potentially joined with r1 on the output side. It's worthwhile to commute 789193323Sed/// 'add' to eliminate a copy. 790243830Sdimvoid TwoAddressInstructionPass::processCopy(MachineInstr *MI) { 791193323Sed if (Processed.count(MI)) 792193323Sed return; 793193323Sed 794193323Sed bool IsSrcPhys, IsDstPhys; 795193323Sed unsigned SrcReg, DstReg; 796193323Sed if (!isCopyToReg(*MI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) 797193323Sed return; 798193323Sed 799193323Sed if (IsDstPhys && !IsSrcPhys) 800193323Sed DstRegMap.insert(std::make_pair(SrcReg, DstReg)); 801193323Sed else if (!IsDstPhys && IsSrcPhys) { 802193323Sed bool isNew = SrcRegMap.insert(std::make_pair(DstReg, SrcReg)).second; 803193323Sed if (!isNew) 804193323Sed assert(SrcRegMap[DstReg] == SrcReg && 805193323Sed "Can't map to two src physical registers!"); 806193323Sed 807243830Sdim scanUses(DstReg); 808193323Sed } 809193323Sed 810193323Sed Processed.insert(MI); 811221345Sdim return; 812193323Sed} 813193323Sed 814296417Sdim/// If there is one more local instruction that reads 'Reg' and it kills 'Reg, 815296417Sdim/// consider moving the instruction below the kill instruction in order to 816296417Sdim/// eliminate the need for the copy. 817243830Sdimbool TwoAddressInstructionPass:: 818243830SdimrescheduleMIBelowKill(MachineBasicBlock::iterator &mi, 819243830Sdim MachineBasicBlock::iterator &nmi, 820243830Sdim unsigned Reg) { 821249423Sdim // Bail immediately if we don't have LV or LIS available. We use them to find 822249423Sdim // kills efficiently. 823249423Sdim if (!LV && !LIS) 824239462Sdim return false; 825239462Sdim 826234353Sdim MachineInstr *MI = &*mi; 827234353Sdim DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI); 828234353Sdim if (DI == DistanceMap.end()) 829234353Sdim // Must be created from unfolded load. Don't waste time trying this. 830234353Sdim return false; 831234353Sdim 832276479Sdim MachineInstr *KillMI = nullptr; 833249423Sdim if (LIS) { 834249423Sdim LiveInterval &LI = LIS->getInterval(Reg); 835249423Sdim assert(LI.end() != LI.begin() && 836249423Sdim "Reg should not have empty live interval."); 837249423Sdim 838249423Sdim SlotIndex MBBEndIdx = LIS->getMBBEndIdx(MBB).getPrevSlot(); 839249423Sdim LiveInterval::const_iterator I = LI.find(MBBEndIdx); 840249423Sdim if (I != LI.end() && I->start < MBBEndIdx) 841249423Sdim return false; 842249423Sdim 843249423Sdim --I; 844249423Sdim KillMI = LIS->getInstructionFromIndex(I->end); 845249423Sdim } else { 846249423Sdim KillMI = LV->getVarInfo(Reg).findKill(MBB); 847249423Sdim } 848239462Sdim if (!KillMI || MI == KillMI || KillMI->isCopy() || KillMI->isCopyLike()) 849234353Sdim // Don't mess with copies, they may be coalesced later. 850234353Sdim return false; 851234353Sdim 852234353Sdim if (KillMI->hasUnmodeledSideEffects() || KillMI->isCall() || 853234353Sdim KillMI->isBranch() || KillMI->isTerminator()) 854234353Sdim // Don't move pass calls, etc. 855234353Sdim return false; 856234353Sdim 857234353Sdim unsigned DstReg; 858234353Sdim if (isTwoAddrUse(*KillMI, Reg, DstReg)) 859234353Sdim return false; 860234353Sdim 861234353Sdim bool SeenStore = true; 862288943Sdim if (!MI->isSafeToMove(AA, SeenStore)) 863234353Sdim return false; 864234353Sdim 865234353Sdim if (TII->getInstrLatency(InstrItins, MI) > 1) 866234353Sdim // FIXME: Needs more sophisticated heuristics. 867234353Sdim return false; 868234353Sdim 869234353Sdim SmallSet<unsigned, 2> Uses; 870234353Sdim SmallSet<unsigned, 2> Kills; 871234353Sdim SmallSet<unsigned, 2> Defs; 872296417Sdim for (const MachineOperand &MO : MI->operands()) { 873234353Sdim if (!MO.isReg()) 874234353Sdim continue; 875234353Sdim unsigned MOReg = MO.getReg(); 876234353Sdim if (!MOReg) 877234353Sdim continue; 878234353Sdim if (MO.isDef()) 879234353Sdim Defs.insert(MOReg); 880234353Sdim else { 881234353Sdim Uses.insert(MOReg); 882249423Sdim if (MOReg != Reg && (MO.isKill() || 883249423Sdim (LIS && isPlainlyKilled(MI, MOReg, LIS)))) 884234353Sdim Kills.insert(MOReg); 885234353Sdim } 886234353Sdim } 887234353Sdim 888234353Sdim // Move the copies connected to MI down as well. 889249423Sdim MachineBasicBlock::iterator Begin = MI; 890276479Sdim MachineBasicBlock::iterator AfterMI = std::next(Begin); 891249423Sdim 892249423Sdim MachineBasicBlock::iterator End = AfterMI; 893249423Sdim while (End->isCopy() && Defs.count(End->getOperand(1).getReg())) { 894249423Sdim Defs.insert(End->getOperand(0).getReg()); 895249423Sdim ++End; 896234353Sdim } 897234353Sdim 898234353Sdim // Check if the reschedule will not break depedencies. 899234353Sdim unsigned NumVisited = 0; 900234353Sdim MachineBasicBlock::iterator KillPos = KillMI; 901234353Sdim ++KillPos; 902249423Sdim for (MachineBasicBlock::iterator I = End; I != KillPos; ++I) { 903234353Sdim MachineInstr *OtherMI = I; 904234353Sdim // DBG_VALUE cannot be counted against the limit. 905234353Sdim if (OtherMI->isDebugValue()) 906234353Sdim continue; 907234353Sdim if (NumVisited > 10) // FIXME: Arbitrary limit to reduce compile time cost. 908234353Sdim return false; 909234353Sdim ++NumVisited; 910234353Sdim if (OtherMI->hasUnmodeledSideEffects() || OtherMI->isCall() || 911234353Sdim OtherMI->isBranch() || OtherMI->isTerminator()) 912234353Sdim // Don't move pass calls, etc. 913234353Sdim return false; 914296417Sdim for (const MachineOperand &MO : OtherMI->operands()) { 915234353Sdim if (!MO.isReg()) 916234353Sdim continue; 917234353Sdim unsigned MOReg = MO.getReg(); 918234353Sdim if (!MOReg) 919234353Sdim continue; 920234353Sdim if (MO.isDef()) { 921234353Sdim if (Uses.count(MOReg)) 922234353Sdim // Physical register use would be clobbered. 923234353Sdim return false; 924234353Sdim if (!MO.isDead() && Defs.count(MOReg)) 925234353Sdim // May clobber a physical register def. 926234353Sdim // FIXME: This may be too conservative. It's ok if the instruction 927234353Sdim // is sunken completely below the use. 928234353Sdim return false; 929234353Sdim } else { 930234353Sdim if (Defs.count(MOReg)) 931234353Sdim return false; 932249423Sdim bool isKill = MO.isKill() || 933249423Sdim (LIS && isPlainlyKilled(OtherMI, MOReg, LIS)); 934234353Sdim if (MOReg != Reg && 935249423Sdim ((isKill && Uses.count(MOReg)) || Kills.count(MOReg))) 936234353Sdim // Don't want to extend other live ranges and update kills. 937234353Sdim return false; 938249423Sdim if (MOReg == Reg && !isKill) 939239462Sdim // We can't schedule across a use of the register in question. 940239462Sdim return false; 941239462Sdim // Ensure that if this is register in question, its the kill we expect. 942239462Sdim assert((MOReg != Reg || OtherMI == KillMI) && 943239462Sdim "Found multiple kills of a register in a basic block"); 944234353Sdim } 945234353Sdim } 946234353Sdim } 947234353Sdim 948234353Sdim // Move debug info as well. 949276479Sdim while (Begin != MBB->begin() && std::prev(Begin)->isDebugValue()) 950249423Sdim --Begin; 951234353Sdim 952249423Sdim nmi = End; 953249423Sdim MachineBasicBlock::iterator InsertPos = KillPos; 954249423Sdim if (LIS) { 955249423Sdim // We have to move the copies first so that the MBB is still well-formed 956249423Sdim // when calling handleMove(). 957249423Sdim for (MachineBasicBlock::iterator MBBI = AfterMI; MBBI != End;) { 958249423Sdim MachineInstr *CopyMI = MBBI; 959249423Sdim ++MBBI; 960249423Sdim MBB->splice(InsertPos, MBB, CopyMI); 961249423Sdim LIS->handleMove(CopyMI); 962249423Sdim InsertPos = CopyMI; 963249423Sdim } 964276479Sdim End = std::next(MachineBasicBlock::iterator(MI)); 965249423Sdim } 966249423Sdim 967234353Sdim // Copies following MI may have been moved as well. 968249423Sdim MBB->splice(InsertPos, MBB, Begin, End); 969234353Sdim DistanceMap.erase(DI); 970234353Sdim 971239462Sdim // Update live variables 972249423Sdim if (LIS) { 973239462Sdim LIS->handleMove(MI); 974249423Sdim } else { 975249423Sdim LV->removeVirtualRegisterKilled(Reg, KillMI); 976249423Sdim LV->addVirtualRegisterKilled(Reg, MI); 977249423Sdim } 978234353Sdim 979239462Sdim DEBUG(dbgs() << "\trescheduled below kill: " << *KillMI); 980234353Sdim return true; 981234353Sdim} 982234353Sdim 983296417Sdim/// Return true if the re-scheduling will put the given instruction too close 984296417Sdim/// to the defs of its register dependencies. 985234353Sdimbool TwoAddressInstructionPass::isDefTooClose(unsigned Reg, unsigned Dist, 986243830Sdim MachineInstr *MI) { 987276479Sdim for (MachineInstr &DefMI : MRI->def_instructions(Reg)) { 988276479Sdim if (DefMI.getParent() != MBB || DefMI.isCopy() || DefMI.isCopyLike()) 989234353Sdim continue; 990276479Sdim if (&DefMI == MI) 991234353Sdim return true; // MI is defining something KillMI uses 992276479Sdim DenseMap<MachineInstr*, unsigned>::iterator DDI = DistanceMap.find(&DefMI); 993234353Sdim if (DDI == DistanceMap.end()) 994234353Sdim return true; // Below MI 995234353Sdim unsigned DefDist = DDI->second; 996234353Sdim assert(Dist > DefDist && "Visited def already?"); 997276479Sdim if (TII->getInstrLatency(InstrItins, &DefMI) > (Dist - DefDist)) 998234353Sdim return true; 999234353Sdim } 1000234353Sdim return false; 1001234353Sdim} 1002234353Sdim 1003296417Sdim/// If there is one more local instruction that reads 'Reg' and it kills 'Reg, 1004296417Sdim/// consider moving the kill instruction above the current two-address 1005296417Sdim/// instruction in order to eliminate the need for the copy. 1006243830Sdimbool TwoAddressInstructionPass:: 1007243830SdimrescheduleKillAboveMI(MachineBasicBlock::iterator &mi, 1008243830Sdim MachineBasicBlock::iterator &nmi, 1009243830Sdim unsigned Reg) { 1010249423Sdim // Bail immediately if we don't have LV or LIS available. We use them to find 1011249423Sdim // kills efficiently. 1012249423Sdim if (!LV && !LIS) 1013239462Sdim return false; 1014239462Sdim 1015234353Sdim MachineInstr *MI = &*mi; 1016234353Sdim DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(MI); 1017234353Sdim if (DI == DistanceMap.end()) 1018234353Sdim // Must be created from unfolded load. Don't waste time trying this. 1019234353Sdim return false; 1020234353Sdim 1021276479Sdim MachineInstr *KillMI = nullptr; 1022249423Sdim if (LIS) { 1023249423Sdim LiveInterval &LI = LIS->getInterval(Reg); 1024249423Sdim assert(LI.end() != LI.begin() && 1025249423Sdim "Reg should not have empty live interval."); 1026249423Sdim 1027249423Sdim SlotIndex MBBEndIdx = LIS->getMBBEndIdx(MBB).getPrevSlot(); 1028249423Sdim LiveInterval::const_iterator I = LI.find(MBBEndIdx); 1029249423Sdim if (I != LI.end() && I->start < MBBEndIdx) 1030249423Sdim return false; 1031249423Sdim 1032249423Sdim --I; 1033249423Sdim KillMI = LIS->getInstructionFromIndex(I->end); 1034249423Sdim } else { 1035249423Sdim KillMI = LV->getVarInfo(Reg).findKill(MBB); 1036249423Sdim } 1037239462Sdim if (!KillMI || MI == KillMI || KillMI->isCopy() || KillMI->isCopyLike()) 1038234353Sdim // Don't mess with copies, they may be coalesced later. 1039234353Sdim return false; 1040234353Sdim 1041234353Sdim unsigned DstReg; 1042234353Sdim if (isTwoAddrUse(*KillMI, Reg, DstReg)) 1043234353Sdim return false; 1044234353Sdim 1045234353Sdim bool SeenStore = true; 1046288943Sdim if (!KillMI->isSafeToMove(AA, SeenStore)) 1047234353Sdim return false; 1048234353Sdim 1049234353Sdim SmallSet<unsigned, 2> Uses; 1050234353Sdim SmallSet<unsigned, 2> Kills; 1051234353Sdim SmallSet<unsigned, 2> Defs; 1052234353Sdim SmallSet<unsigned, 2> LiveDefs; 1053296417Sdim for (const MachineOperand &MO : KillMI->operands()) { 1054234353Sdim if (!MO.isReg()) 1055234353Sdim continue; 1056234353Sdim unsigned MOReg = MO.getReg(); 1057234353Sdim if (MO.isUse()) { 1058234353Sdim if (!MOReg) 1059234353Sdim continue; 1060243830Sdim if (isDefTooClose(MOReg, DI->second, MI)) 1061234353Sdim return false; 1062249423Sdim bool isKill = MO.isKill() || (LIS && isPlainlyKilled(KillMI, MOReg, LIS)); 1063249423Sdim if (MOReg == Reg && !isKill) 1064239462Sdim return false; 1065234353Sdim Uses.insert(MOReg); 1066249423Sdim if (isKill && MOReg != Reg) 1067234353Sdim Kills.insert(MOReg); 1068234353Sdim } else if (TargetRegisterInfo::isPhysicalRegister(MOReg)) { 1069234353Sdim Defs.insert(MOReg); 1070234353Sdim if (!MO.isDead()) 1071234353Sdim LiveDefs.insert(MOReg); 1072234353Sdim } 1073234353Sdim } 1074234353Sdim 1075234353Sdim // Check if the reschedule will not break depedencies. 1076234353Sdim unsigned NumVisited = 0; 1077234353Sdim MachineBasicBlock::iterator KillPos = KillMI; 1078234353Sdim for (MachineBasicBlock::iterator I = mi; I != KillPos; ++I) { 1079234353Sdim MachineInstr *OtherMI = I; 1080234353Sdim // DBG_VALUE cannot be counted against the limit. 1081234353Sdim if (OtherMI->isDebugValue()) 1082234353Sdim continue; 1083234353Sdim if (NumVisited > 10) // FIXME: Arbitrary limit to reduce compile time cost. 1084234353Sdim return false; 1085234353Sdim ++NumVisited; 1086234353Sdim if (OtherMI->hasUnmodeledSideEffects() || OtherMI->isCall() || 1087234353Sdim OtherMI->isBranch() || OtherMI->isTerminator()) 1088234353Sdim // Don't move pass calls, etc. 1089234353Sdim return false; 1090234353Sdim SmallVector<unsigned, 2> OtherDefs; 1091296417Sdim for (const MachineOperand &MO : OtherMI->operands()) { 1092234353Sdim if (!MO.isReg()) 1093234353Sdim continue; 1094234353Sdim unsigned MOReg = MO.getReg(); 1095234353Sdim if (!MOReg) 1096234353Sdim continue; 1097234353Sdim if (MO.isUse()) { 1098234353Sdim if (Defs.count(MOReg)) 1099234353Sdim // Moving KillMI can clobber the physical register if the def has 1100234353Sdim // not been seen. 1101234353Sdim return false; 1102234353Sdim if (Kills.count(MOReg)) 1103234353Sdim // Don't want to extend other live ranges and update kills. 1104234353Sdim return false; 1105249423Sdim if (OtherMI != MI && MOReg == Reg && 1106249423Sdim !(MO.isKill() || (LIS && isPlainlyKilled(OtherMI, MOReg, LIS)))) 1107239462Sdim // We can't schedule across a use of the register in question. 1108239462Sdim return false; 1109234353Sdim } else { 1110234353Sdim OtherDefs.push_back(MOReg); 1111234353Sdim } 1112234353Sdim } 1113234353Sdim 1114234353Sdim for (unsigned i = 0, e = OtherDefs.size(); i != e; ++i) { 1115234353Sdim unsigned MOReg = OtherDefs[i]; 1116234353Sdim if (Uses.count(MOReg)) 1117234353Sdim return false; 1118234353Sdim if (TargetRegisterInfo::isPhysicalRegister(MOReg) && 1119234353Sdim LiveDefs.count(MOReg)) 1120234353Sdim return false; 1121234353Sdim // Physical register def is seen. 1122234353Sdim Defs.erase(MOReg); 1123234353Sdim } 1124234353Sdim } 1125234353Sdim 1126234353Sdim // Move the old kill above MI, don't forget to move debug info as well. 1127234353Sdim MachineBasicBlock::iterator InsertPos = mi; 1128276479Sdim while (InsertPos != MBB->begin() && std::prev(InsertPos)->isDebugValue()) 1129234353Sdim --InsertPos; 1130234353Sdim MachineBasicBlock::iterator From = KillMI; 1131276479Sdim MachineBasicBlock::iterator To = std::next(From); 1132276479Sdim while (std::prev(From)->isDebugValue()) 1133234353Sdim --From; 1134234353Sdim MBB->splice(InsertPos, MBB, From, To); 1135234353Sdim 1136276479Sdim nmi = std::prev(InsertPos); // Backtrack so we process the moved instr. 1137234353Sdim DistanceMap.erase(DI); 1138234353Sdim 1139239462Sdim // Update live variables 1140249423Sdim if (LIS) { 1141239462Sdim LIS->handleMove(KillMI); 1142249423Sdim } else { 1143249423Sdim LV->removeVirtualRegisterKilled(Reg, KillMI); 1144249423Sdim LV->addVirtualRegisterKilled(Reg, MI); 1145249423Sdim } 1146239462Sdim 1147239462Sdim DEBUG(dbgs() << "\trescheduled kill: " << *KillMI); 1148234353Sdim return true; 1149234353Sdim} 1150234353Sdim 1151296417Sdim/// Tries to commute the operand 'BaseOpIdx' and some other operand in the 1152296417Sdim/// given machine instruction to improve opportunities for coalescing and 1153296417Sdim/// elimination of a register to register copy. 1154296417Sdim/// 1155296417Sdim/// 'DstOpIdx' specifies the index of MI def operand. 1156296417Sdim/// 'BaseOpKilled' specifies if the register associated with 'BaseOpIdx' 1157296417Sdim/// operand is killed by the given instruction. 1158296417Sdim/// The 'Dist' arguments provides the distance of MI from the start of the 1159296417Sdim/// current basic block and it is used to determine if it is profitable 1160296417Sdim/// to commute operands in the instruction. 1161296417Sdim/// 1162296417Sdim/// Returns true if the transformation happened. Otherwise, returns false. 1163296417Sdimbool TwoAddressInstructionPass::tryInstructionCommute(MachineInstr *MI, 1164296417Sdim unsigned DstOpIdx, 1165296417Sdim unsigned BaseOpIdx, 1166296417Sdim bool BaseOpKilled, 1167296417Sdim unsigned Dist) { 1168296417Sdim unsigned DstOpReg = MI->getOperand(DstOpIdx).getReg(); 1169296417Sdim unsigned BaseOpReg = MI->getOperand(BaseOpIdx).getReg(); 1170296417Sdim unsigned OpsNum = MI->getDesc().getNumOperands(); 1171296417Sdim unsigned OtherOpIdx = MI->getDesc().getNumDefs(); 1172296417Sdim for (; OtherOpIdx < OpsNum; OtherOpIdx++) { 1173296417Sdim // The call of findCommutedOpIndices below only checks if BaseOpIdx 1174296417Sdim // and OtherOpIdx are commutable, it does not really search for 1175296417Sdim // other commutable operands and does not change the values of passed 1176296417Sdim // variables. 1177296417Sdim if (OtherOpIdx == BaseOpIdx || 1178296417Sdim !TII->findCommutedOpIndices(MI, BaseOpIdx, OtherOpIdx)) 1179296417Sdim continue; 1180296417Sdim 1181296417Sdim unsigned OtherOpReg = MI->getOperand(OtherOpIdx).getReg(); 1182296417Sdim bool AggressiveCommute = false; 1183296417Sdim 1184296417Sdim // If OtherOp dies but BaseOp does not, swap the OtherOp and BaseOp 1185296417Sdim // operands. This makes the live ranges of DstOp and OtherOp joinable. 1186296417Sdim bool DoCommute = 1187296417Sdim !BaseOpKilled && isKilled(*MI, OtherOpReg, MRI, TII, LIS, false); 1188296417Sdim 1189296417Sdim if (!DoCommute && 1190296417Sdim isProfitableToCommute(DstOpReg, BaseOpReg, OtherOpReg, MI, Dist)) { 1191296417Sdim DoCommute = true; 1192296417Sdim AggressiveCommute = true; 1193296417Sdim } 1194296417Sdim 1195296417Sdim // If it's profitable to commute, try to do so. 1196296417Sdim if (DoCommute && commuteInstruction(MI, BaseOpIdx, OtherOpIdx, Dist)) { 1197296417Sdim ++NumCommuted; 1198296417Sdim if (AggressiveCommute) 1199296417Sdim ++NumAggrCommuted; 1200296417Sdim return true; 1201296417Sdim } 1202296417Sdim } 1203296417Sdim return false; 1204296417Sdim} 1205296417Sdim 1206296417Sdim/// For the case where an instruction has a single pair of tied register 1207296417Sdim/// operands, attempt some transformations that may either eliminate the tied 1208296417Sdim/// operands or improve the opportunities for coalescing away the register copy. 1209296417Sdim/// Returns true if no copy needs to be inserted to untie mi's operands 1210296417Sdim/// (either because they were untied, or because mi was rescheduled, and will 1211296417Sdim/// be visited again later). If the shouldOnlyCommute flag is true, only 1212296417Sdim/// instruction commutation is attempted. 1213198090Srdivackybool TwoAddressInstructionPass:: 1214243830SdimtryInstructionTransform(MachineBasicBlock::iterator &mi, 1215198090Srdivacky MachineBasicBlock::iterator &nmi, 1216249423Sdim unsigned SrcIdx, unsigned DstIdx, 1217249423Sdim unsigned Dist, bool shouldOnlyCommute) { 1218234353Sdim if (OptLevel == CodeGenOpt::None) 1219234353Sdim return false; 1220198090Srdivacky 1221234353Sdim MachineInstr &MI = *mi; 1222234353Sdim unsigned regA = MI.getOperand(DstIdx).getReg(); 1223234353Sdim unsigned regB = MI.getOperand(SrcIdx).getReg(); 1224234353Sdim 1225198090Srdivacky assert(TargetRegisterInfo::isVirtualRegister(regB) && 1226198090Srdivacky "cannot make instruction into two-address form"); 1227249423Sdim bool regBKilled = isKilled(MI, regB, MRI, TII, LIS, true); 1228198090Srdivacky 1229239462Sdim if (TargetRegisterInfo::isVirtualRegister(regA)) 1230243830Sdim scanUses(regA); 1231239462Sdim 1232296417Sdim bool Commuted = tryInstructionCommute(&MI, DstIdx, SrcIdx, regBKilled, Dist); 1233198090Srdivacky 1234288943Sdim // If the instruction is convertible to 3 Addr, instead 1235288943Sdim // of returning try 3 Addr transformation aggresively and 1236288943Sdim // use this variable to check later. Because it might be better. 1237288943Sdim // For example, we can just use `leal (%rsi,%rdi), %eax` and `ret` 1238288943Sdim // instead of the following code. 1239296417Sdim // addl %esi, %edi 1240296417Sdim // movl %edi, %eax 1241288943Sdim // ret 1242296417Sdim if (Commuted && !MI.isConvertibleTo3Addr()) 1243296417Sdim return false; 1244288943Sdim 1245249423Sdim if (shouldOnlyCommute) 1246249423Sdim return false; 1247249423Sdim 1248234353Sdim // If there is one more use of regB later in the same MBB, consider 1249234353Sdim // re-schedule this MI below it. 1250288943Sdim if (!Commuted && EnableRescheduling && rescheduleMIBelowKill(mi, nmi, regB)) { 1251234353Sdim ++NumReSchedDowns; 1252234353Sdim return true; 1253234353Sdim } 1254234353Sdim 1255296417Sdim // If we commuted, regB may have changed so we should re-sample it to avoid 1256296417Sdim // confusing the three address conversion below. 1257296417Sdim if (Commuted) { 1258296417Sdim regB = MI.getOperand(SrcIdx).getReg(); 1259296417Sdim regBKilled = isKilled(MI, regB, MRI, TII, LIS, true); 1260296417Sdim } 1261296417Sdim 1262234353Sdim if (MI.isConvertibleTo3Addr()) { 1263198090Srdivacky // This instruction is potentially convertible to a true 1264198090Srdivacky // three-address instruction. Check if it is profitable. 1265221345Sdim if (!regBKilled || isProfitableToConv3Addr(regA, regB)) { 1266198090Srdivacky // Try to convert it. 1267243830Sdim if (convertInstTo3Addr(mi, nmi, regA, regB, Dist)) { 1268198090Srdivacky ++NumConvertedTo3Addr; 1269198090Srdivacky return true; // Done with this instruction. 1270198090Srdivacky } 1271198090Srdivacky } 1272198090Srdivacky } 1273210299Sed 1274288943Sdim // Return if it is commuted but 3 addr conversion is failed. 1275288943Sdim if (Commuted) 1276288943Sdim return false; 1277288943Sdim 1278234353Sdim // If there is one more use of regB later in the same MBB, consider 1279234353Sdim // re-schedule it before this MI if it's legal. 1280251662Sdim if (EnableRescheduling && rescheduleKillAboveMI(mi, nmi, regB)) { 1281234353Sdim ++NumReSchedUps; 1282234353Sdim return true; 1283234353Sdim } 1284234353Sdim 1285210299Sed // If this is an instruction with a load folded into it, try unfolding 1286210299Sed // the load, e.g. avoid this: 1287210299Sed // movq %rdx, %rcx 1288210299Sed // addq (%rax), %rcx 1289210299Sed // in favor of this: 1290210299Sed // movq (%rax), %rcx 1291210299Sed // addq %rdx, %rcx 1292210299Sed // because it's preferable to schedule a load than a register copy. 1293234353Sdim if (MI.mayLoad() && !regBKilled) { 1294210299Sed // Determine if a load can be unfolded. 1295210299Sed unsigned LoadRegIndex; 1296210299Sed unsigned NewOpc = 1297234353Sdim TII->getOpcodeAfterMemoryUnfold(MI.getOpcode(), 1298210299Sed /*UnfoldLoad=*/true, 1299210299Sed /*UnfoldStore=*/false, 1300210299Sed &LoadRegIndex); 1301210299Sed if (NewOpc != 0) { 1302224145Sdim const MCInstrDesc &UnfoldMCID = TII->get(NewOpc); 1303224145Sdim if (UnfoldMCID.getNumDefs() == 1) { 1304210299Sed // Unfold the load. 1305234353Sdim DEBUG(dbgs() << "2addr: UNFOLDING: " << MI); 1306210299Sed const TargetRegisterClass *RC = 1307239462Sdim TRI->getAllocatableClass( 1308239462Sdim TII->getRegClass(UnfoldMCID, LoadRegIndex, TRI, *MF)); 1309210299Sed unsigned Reg = MRI->createVirtualRegister(RC); 1310210299Sed SmallVector<MachineInstr *, 2> NewMIs; 1311239462Sdim if (!TII->unfoldMemoryOperand(*MF, &MI, Reg, 1312210299Sed /*UnfoldLoad=*/true,/*UnfoldStore=*/false, 1313210299Sed NewMIs)) { 1314210299Sed DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n"); 1315210299Sed return false; 1316210299Sed } 1317210299Sed assert(NewMIs.size() == 2 && 1318210299Sed "Unfolded a load into multiple instructions!"); 1319210299Sed // The load was previously folded, so this is the only use. 1320210299Sed NewMIs[1]->addRegisterKilled(Reg, TRI); 1321210299Sed 1322210299Sed // Tentatively insert the instructions into the block so that they 1323210299Sed // look "normal" to the transformation logic. 1324243830Sdim MBB->insert(mi, NewMIs[0]); 1325243830Sdim MBB->insert(mi, NewMIs[1]); 1326210299Sed 1327210299Sed DEBUG(dbgs() << "2addr: NEW LOAD: " << *NewMIs[0] 1328210299Sed << "2addr: NEW INST: " << *NewMIs[1]); 1329210299Sed 1330210299Sed // Transform the instruction, now that it no longer has a load. 1331210299Sed unsigned NewDstIdx = NewMIs[1]->findRegisterDefOperandIdx(regA); 1332210299Sed unsigned NewSrcIdx = NewMIs[1]->findRegisterUseOperandIdx(regB); 1333210299Sed MachineBasicBlock::iterator NewMI = NewMIs[1]; 1334249423Sdim bool TransformResult = 1335249423Sdim tryInstructionTransform(NewMI, mi, NewSrcIdx, NewDstIdx, Dist, true); 1336249423Sdim (void)TransformResult; 1337249423Sdim assert(!TransformResult && 1338249423Sdim "tryInstructionTransform() should return false."); 1339249423Sdim if (NewMIs[1]->getOperand(NewSrcIdx).isKill()) { 1340210299Sed // Success, or at least we made an improvement. Keep the unfolded 1341210299Sed // instructions and discard the original. 1342210299Sed if (LV) { 1343234353Sdim for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 1344234353Sdim MachineOperand &MO = MI.getOperand(i); 1345234353Sdim if (MO.isReg() && 1346210299Sed TargetRegisterInfo::isVirtualRegister(MO.getReg())) { 1347210299Sed if (MO.isUse()) { 1348210299Sed if (MO.isKill()) { 1349210299Sed if (NewMIs[0]->killsRegister(MO.getReg())) 1350234353Sdim LV->replaceKillInstruction(MO.getReg(), &MI, NewMIs[0]); 1351210299Sed else { 1352210299Sed assert(NewMIs[1]->killsRegister(MO.getReg()) && 1353210299Sed "Kill missing after load unfold!"); 1354234353Sdim LV->replaceKillInstruction(MO.getReg(), &MI, NewMIs[1]); 1355210299Sed } 1356210299Sed } 1357234353Sdim } else if (LV->removeVirtualRegisterDead(MO.getReg(), &MI)) { 1358210299Sed if (NewMIs[1]->registerDefIsDead(MO.getReg())) 1359210299Sed LV->addVirtualRegisterDead(MO.getReg(), NewMIs[1]); 1360210299Sed else { 1361210299Sed assert(NewMIs[0]->registerDefIsDead(MO.getReg()) && 1362210299Sed "Dead flag missing after load unfold!"); 1363210299Sed LV->addVirtualRegisterDead(MO.getReg(), NewMIs[0]); 1364210299Sed } 1365210299Sed } 1366210299Sed } 1367210299Sed } 1368210299Sed LV->addVirtualRegisterKilled(Reg, NewMIs[1]); 1369210299Sed } 1370249423Sdim 1371249423Sdim SmallVector<unsigned, 4> OrigRegs; 1372249423Sdim if (LIS) { 1373296417Sdim for (const MachineOperand &MO : MI.operands()) { 1374296417Sdim if (MO.isReg()) 1375296417Sdim OrigRegs.push_back(MO.getReg()); 1376249423Sdim } 1377249423Sdim } 1378249423Sdim 1379234353Sdim MI.eraseFromParent(); 1380249423Sdim 1381249423Sdim // Update LiveIntervals. 1382249423Sdim if (LIS) { 1383249423Sdim MachineBasicBlock::iterator Begin(NewMIs[0]); 1384249423Sdim MachineBasicBlock::iterator End(NewMIs[1]); 1385249423Sdim LIS->repairIntervalsInRange(MBB, Begin, End, OrigRegs); 1386249423Sdim } 1387249423Sdim 1388210299Sed mi = NewMIs[1]; 1389210299Sed } else { 1390210299Sed // Transforming didn't eliminate the tie and didn't lead to an 1391210299Sed // improvement. Clean up the unfolded instructions and keep the 1392210299Sed // original. 1393210299Sed DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n"); 1394210299Sed NewMIs[0]->eraseFromParent(); 1395210299Sed NewMIs[1]->eraseFromParent(); 1396210299Sed } 1397210299Sed } 1398210299Sed } 1399210299Sed } 1400210299Sed 1401198090Srdivacky return false; 1402198090Srdivacky} 1403198090Srdivacky 1404239462Sdim// Collect tied operands of MI that need to be handled. 1405239462Sdim// Rewrite trivial cases immediately. 1406239462Sdim// Return true if any tied operands where found, including the trivial ones. 1407239462Sdimbool TwoAddressInstructionPass:: 1408239462SdimcollectTiedOperands(MachineInstr *MI, TiedOperandMap &TiedOperands) { 1409239462Sdim const MCInstrDesc &MCID = MI->getDesc(); 1410239462Sdim bool AnyOps = false; 1411243830Sdim unsigned NumOps = MI->getNumOperands(); 1412239462Sdim 1413239462Sdim for (unsigned SrcIdx = 0; SrcIdx < NumOps; ++SrcIdx) { 1414239462Sdim unsigned DstIdx = 0; 1415239462Sdim if (!MI->isRegTiedToDefOperand(SrcIdx, &DstIdx)) 1416239462Sdim continue; 1417239462Sdim AnyOps = true; 1418239462Sdim MachineOperand &SrcMO = MI->getOperand(SrcIdx); 1419239462Sdim MachineOperand &DstMO = MI->getOperand(DstIdx); 1420239462Sdim unsigned SrcReg = SrcMO.getReg(); 1421239462Sdim unsigned DstReg = DstMO.getReg(); 1422239462Sdim // Tied constraint already satisfied? 1423239462Sdim if (SrcReg == DstReg) 1424239462Sdim continue; 1425239462Sdim 1426239462Sdim assert(SrcReg && SrcMO.isUse() && "two address instruction invalid"); 1427239462Sdim 1428239462Sdim // Deal with <undef> uses immediately - simply rewrite the src operand. 1429276479Sdim if (SrcMO.isUndef() && !DstMO.getSubReg()) { 1430239462Sdim // Constrain the DstReg register class if required. 1431239462Sdim if (TargetRegisterInfo::isVirtualRegister(DstReg)) 1432239462Sdim if (const TargetRegisterClass *RC = TII->getRegClass(MCID, SrcIdx, 1433239462Sdim TRI, *MF)) 1434239462Sdim MRI->constrainRegClass(DstReg, RC); 1435239462Sdim SrcMO.setReg(DstReg); 1436276479Sdim SrcMO.setSubReg(0); 1437239462Sdim DEBUG(dbgs() << "\t\trewrite undef:\t" << *MI); 1438239462Sdim continue; 1439239462Sdim } 1440239462Sdim TiedOperands[SrcReg].push_back(std::make_pair(SrcIdx, DstIdx)); 1441239462Sdim } 1442239462Sdim return AnyOps; 1443239462Sdim} 1444239462Sdim 1445239462Sdim// Process a list of tied MI operands that all use the same source register. 1446239462Sdim// The tied pairs are of the form (SrcIdx, DstIdx). 1447239462Sdimvoid 1448239462SdimTwoAddressInstructionPass::processTiedPairs(MachineInstr *MI, 1449239462Sdim TiedPairList &TiedPairs, 1450239462Sdim unsigned &Dist) { 1451239462Sdim bool IsEarlyClobber = false; 1452249423Sdim for (unsigned tpi = 0, tpe = TiedPairs.size(); tpi != tpe; ++tpi) { 1453249423Sdim const MachineOperand &DstMO = MI->getOperand(TiedPairs[tpi].second); 1454249423Sdim IsEarlyClobber |= DstMO.isEarlyClobber(); 1455249423Sdim } 1456249423Sdim 1457239462Sdim bool RemovedKillFlag = false; 1458239462Sdim bool AllUsesCopied = true; 1459239462Sdim unsigned LastCopiedReg = 0; 1460249423Sdim SlotIndex LastCopyIdx; 1461239462Sdim unsigned RegB = 0; 1462276479Sdim unsigned SubRegB = 0; 1463239462Sdim for (unsigned tpi = 0, tpe = TiedPairs.size(); tpi != tpe; ++tpi) { 1464239462Sdim unsigned SrcIdx = TiedPairs[tpi].first; 1465239462Sdim unsigned DstIdx = TiedPairs[tpi].second; 1466239462Sdim 1467239462Sdim const MachineOperand &DstMO = MI->getOperand(DstIdx); 1468239462Sdim unsigned RegA = DstMO.getReg(); 1469239462Sdim 1470239462Sdim // Grab RegB from the instruction because it may have changed if the 1471239462Sdim // instruction was commuted. 1472239462Sdim RegB = MI->getOperand(SrcIdx).getReg(); 1473276479Sdim SubRegB = MI->getOperand(SrcIdx).getSubReg(); 1474239462Sdim 1475239462Sdim if (RegA == RegB) { 1476239462Sdim // The register is tied to multiple destinations (or else we would 1477239462Sdim // not have continued this far), but this use of the register 1478239462Sdim // already matches the tied destination. Leave it. 1479239462Sdim AllUsesCopied = false; 1480239462Sdim continue; 1481239462Sdim } 1482239462Sdim LastCopiedReg = RegA; 1483239462Sdim 1484239462Sdim assert(TargetRegisterInfo::isVirtualRegister(RegB) && 1485239462Sdim "cannot make instruction into two-address form"); 1486239462Sdim 1487239462Sdim#ifndef NDEBUG 1488239462Sdim // First, verify that we don't have a use of "a" in the instruction 1489239462Sdim // (a = b + a for example) because our transformation will not 1490239462Sdim // work. This should never occur because we are in SSA form. 1491239462Sdim for (unsigned i = 0; i != MI->getNumOperands(); ++i) 1492239462Sdim assert(i == DstIdx || 1493239462Sdim !MI->getOperand(i).isReg() || 1494239462Sdim MI->getOperand(i).getReg() != RegA); 1495239462Sdim#endif 1496239462Sdim 1497239462Sdim // Emit a copy. 1498276479Sdim MachineInstrBuilder MIB = BuildMI(*MI->getParent(), MI, MI->getDebugLoc(), 1499276479Sdim TII->get(TargetOpcode::COPY), RegA); 1500276479Sdim // If this operand is folding a truncation, the truncation now moves to the 1501276479Sdim // copy so that the register classes remain valid for the operands. 1502276479Sdim MIB.addReg(RegB, 0, SubRegB); 1503276479Sdim const TargetRegisterClass *RC = MRI->getRegClass(RegB); 1504276479Sdim if (SubRegB) { 1505276479Sdim if (TargetRegisterInfo::isVirtualRegister(RegA)) { 1506276479Sdim assert(TRI->getMatchingSuperRegClass(RC, MRI->getRegClass(RegA), 1507276479Sdim SubRegB) && 1508276479Sdim "tied subregister must be a truncation"); 1509276479Sdim // The superreg class will not be used to constrain the subreg class. 1510276479Sdim RC = nullptr; 1511276479Sdim } 1512276479Sdim else { 1513276479Sdim assert(TRI->getMatchingSuperReg(RegA, SubRegB, MRI->getRegClass(RegB)) 1514276479Sdim && "tied subregister must be a truncation"); 1515276479Sdim } 1516276479Sdim } 1517239462Sdim 1518239462Sdim // Update DistanceMap. 1519239462Sdim MachineBasicBlock::iterator PrevMI = MI; 1520239462Sdim --PrevMI; 1521239462Sdim DistanceMap.insert(std::make_pair(PrevMI, Dist)); 1522239462Sdim DistanceMap[MI] = ++Dist; 1523239462Sdim 1524249423Sdim if (LIS) { 1525249423Sdim LastCopyIdx = LIS->InsertMachineInstrInMaps(PrevMI).getRegSlot(); 1526239462Sdim 1527249423Sdim if (TargetRegisterInfo::isVirtualRegister(RegA)) { 1528249423Sdim LiveInterval &LI = LIS->getInterval(RegA); 1529249423Sdim VNInfo *VNI = LI.getNextValue(LastCopyIdx, LIS->getVNInfoAllocator()); 1530249423Sdim SlotIndex endIdx = 1531249423Sdim LIS->getInstructionIndex(MI).getRegSlot(IsEarlyClobber); 1532261991Sdim LI.addSegment(LiveInterval::Segment(LastCopyIdx, endIdx, VNI)); 1533249423Sdim } 1534249423Sdim } 1535249423Sdim 1536276479Sdim DEBUG(dbgs() << "\t\tprepend:\t" << *MIB); 1537239462Sdim 1538239462Sdim MachineOperand &MO = MI->getOperand(SrcIdx); 1539239462Sdim assert(MO.isReg() && MO.getReg() == RegB && MO.isUse() && 1540239462Sdim "inconsistent operand info for 2-reg pass"); 1541239462Sdim if (MO.isKill()) { 1542239462Sdim MO.setIsKill(false); 1543239462Sdim RemovedKillFlag = true; 1544239462Sdim } 1545239462Sdim 1546239462Sdim // Make sure regA is a legal regclass for the SrcIdx operand. 1547239462Sdim if (TargetRegisterInfo::isVirtualRegister(RegA) && 1548239462Sdim TargetRegisterInfo::isVirtualRegister(RegB)) 1549276479Sdim MRI->constrainRegClass(RegA, RC); 1550239462Sdim MO.setReg(RegA); 1551276479Sdim // The getMatchingSuper asserts guarantee that the register class projected 1552276479Sdim // by SubRegB is compatible with RegA with no subregister. So regardless of 1553276479Sdim // whether the dest oper writes a subreg, the source oper should not. 1554276479Sdim MO.setSubReg(0); 1555239462Sdim 1556239462Sdim // Propagate SrcRegMap. 1557239462Sdim SrcRegMap[RegA] = RegB; 1558239462Sdim } 1559239462Sdim 1560239462Sdim if (AllUsesCopied) { 1561239462Sdim if (!IsEarlyClobber) { 1562239462Sdim // Replace other (un-tied) uses of regB with LastCopiedReg. 1563296417Sdim for (MachineOperand &MO : MI->operands()) { 1564276479Sdim if (MO.isReg() && MO.getReg() == RegB && MO.getSubReg() == SubRegB && 1565276479Sdim MO.isUse()) { 1566239462Sdim if (MO.isKill()) { 1567239462Sdim MO.setIsKill(false); 1568239462Sdim RemovedKillFlag = true; 1569239462Sdim } 1570239462Sdim MO.setReg(LastCopiedReg); 1571276479Sdim MO.setSubReg(0); 1572239462Sdim } 1573239462Sdim } 1574239462Sdim } 1575239462Sdim 1576239462Sdim // Update live variables for regB. 1577239462Sdim if (RemovedKillFlag && LV && LV->getVarInfo(RegB).removeKill(MI)) { 1578239462Sdim MachineBasicBlock::iterator PrevMI = MI; 1579239462Sdim --PrevMI; 1580239462Sdim LV->addVirtualRegisterKilled(RegB, PrevMI); 1581239462Sdim } 1582239462Sdim 1583249423Sdim // Update LiveIntervals. 1584249423Sdim if (LIS) { 1585249423Sdim LiveInterval &LI = LIS->getInterval(RegB); 1586249423Sdim SlotIndex MIIdx = LIS->getInstructionIndex(MI); 1587249423Sdim LiveInterval::const_iterator I = LI.find(MIIdx); 1588249423Sdim assert(I != LI.end() && "RegB must be live-in to use."); 1589249423Sdim 1590249423Sdim SlotIndex UseIdx = MIIdx.getRegSlot(IsEarlyClobber); 1591249423Sdim if (I->end == UseIdx) 1592261991Sdim LI.removeSegment(LastCopyIdx, UseIdx); 1593249423Sdim } 1594249423Sdim 1595239462Sdim } else if (RemovedKillFlag) { 1596239462Sdim // Some tied uses of regB matched their destination registers, so 1597239462Sdim // regB is still used in this instruction, but a kill flag was 1598239462Sdim // removed from a different tied use of regB, so now we need to add 1599239462Sdim // a kill flag to one of the remaining uses of regB. 1600296417Sdim for (MachineOperand &MO : MI->operands()) { 1601239462Sdim if (MO.isReg() && MO.getReg() == RegB && MO.isUse()) { 1602239462Sdim MO.setIsKill(true); 1603239462Sdim break; 1604239462Sdim } 1605239462Sdim } 1606239462Sdim } 1607239462Sdim} 1608239462Sdim 1609296417Sdim/// Reduce two-address instructions to two operands. 1610239462Sdimbool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &Func) { 1611239462Sdim MF = &Func; 1612239462Sdim const TargetMachine &TM = MF->getTarget(); 1613239462Sdim MRI = &MF->getRegInfo(); 1614288943Sdim TII = MF->getSubtarget().getInstrInfo(); 1615288943Sdim TRI = MF->getSubtarget().getRegisterInfo(); 1616288943Sdim InstrItins = MF->getSubtarget().getInstrItineraryData(); 1617193323Sed LV = getAnalysisIfAvailable<LiveVariables>(); 1618239462Sdim LIS = getAnalysisIfAvailable<LiveIntervals>(); 1619296417Sdim AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); 1620234353Sdim OptLevel = TM.getOptLevel(); 1621193323Sed 1622193323Sed bool MadeChange = false; 1623193323Sed 1624202375Srdivacky DEBUG(dbgs() << "********** REWRITING TWO-ADDR INSTRS **********\n"); 1625234353Sdim DEBUG(dbgs() << "********** Function: " 1626243830Sdim << MF->getName() << '\n'); 1627193323Sed 1628226633Sdim // This pass takes the function out of SSA form. 1629226633Sdim MRI->leaveSSA(); 1630226633Sdim 1631239462Sdim TiedOperandMap TiedOperands; 1632243830Sdim for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end(); 1633243830Sdim MBBI != MBBE; ++MBBI) { 1634296417Sdim MBB = &*MBBI; 1635193323Sed unsigned Dist = 0; 1636193323Sed DistanceMap.clear(); 1637193323Sed SrcRegMap.clear(); 1638193323Sed DstRegMap.clear(); 1639193323Sed Processed.clear(); 1640243830Sdim for (MachineBasicBlock::iterator mi = MBB->begin(), me = MBB->end(); 1641193323Sed mi != me; ) { 1642276479Sdim MachineBasicBlock::iterator nmi = std::next(mi); 1643203954Srdivacky if (mi->isDebugValue()) { 1644203954Srdivacky mi = nmi; 1645203954Srdivacky continue; 1646203954Srdivacky } 1647206083Srdivacky 1648249423Sdim // Expand REG_SEQUENCE instructions. This will position mi at the first 1649249423Sdim // expanded instruction. 1650208599Srdivacky if (mi->isRegSequence()) 1651249423Sdim eliminateRegSequence(mi); 1652208599Srdivacky 1653193323Sed DistanceMap.insert(std::make_pair(mi, ++Dist)); 1654193323Sed 1655243830Sdim processCopy(&*mi); 1656193323Sed 1657198090Srdivacky // First scan through all the tied register uses in this instruction 1658198090Srdivacky // and record a list of pairs of tied operands for each register. 1659239462Sdim if (!collectTiedOperands(mi, TiedOperands)) { 1660239462Sdim mi = nmi; 1661239462Sdim continue; 1662198090Srdivacky } 1663193323Sed 1664239462Sdim ++NumTwoAddressInstrs; 1665239462Sdim MadeChange = true; 1666239462Sdim DEBUG(dbgs() << '\t' << *mi); 1667193323Sed 1668239462Sdim // If the instruction has a single pair of tied operands, try some 1669239462Sdim // transformations that may either eliminate the tied operands or 1670239462Sdim // improve the opportunities for coalescing away the register copy. 1671239462Sdim if (TiedOperands.size() == 1) { 1672261991Sdim SmallVectorImpl<std::pair<unsigned, unsigned> > &TiedPairs 1673239462Sdim = TiedOperands.begin()->second; 1674239462Sdim if (TiedPairs.size() == 1) { 1675198090Srdivacky unsigned SrcIdx = TiedPairs[0].first; 1676198090Srdivacky unsigned DstIdx = TiedPairs[0].second; 1677239462Sdim unsigned SrcReg = mi->getOperand(SrcIdx).getReg(); 1678239462Sdim unsigned DstReg = mi->getOperand(DstIdx).getReg(); 1679239462Sdim if (SrcReg != DstReg && 1680249423Sdim tryInstructionTransform(mi, nmi, SrcIdx, DstIdx, Dist, false)) { 1681296417Sdim // The tied operands have been eliminated or shifted further down 1682296417Sdim // the block to ease elimination. Continue processing with 'nmi'. 1683239462Sdim TiedOperands.clear(); 1684239462Sdim mi = nmi; 1685198090Srdivacky continue; 1686198090Srdivacky } 1687198090Srdivacky } 1688239462Sdim } 1689193323Sed 1690239462Sdim // Now iterate over the information collected above. 1691296417Sdim for (auto &TO : TiedOperands) { 1692296417Sdim processTiedPairs(mi, TO.second, Dist); 1693202375Srdivacky DEBUG(dbgs() << "\t\trewrite to:\t" << *mi); 1694239462Sdim } 1695193323Sed 1696239462Sdim // Rewrite INSERT_SUBREG as COPY now that we no longer need SSA form. 1697239462Sdim if (mi->isInsertSubreg()) { 1698239462Sdim // From %reg = INSERT_SUBREG %reg, %subreg, subidx 1699239462Sdim // To %reg:subidx = COPY %subreg 1700239462Sdim unsigned SubIdx = mi->getOperand(3).getImm(); 1701239462Sdim mi->RemoveOperand(3); 1702239462Sdim assert(mi->getOperand(0).getSubReg() == 0 && "Unexpected subreg idx"); 1703239462Sdim mi->getOperand(0).setSubReg(SubIdx); 1704239462Sdim mi->getOperand(0).setIsUndef(mi->getOperand(1).isUndef()); 1705239462Sdim mi->RemoveOperand(1); 1706239462Sdim mi->setDesc(TII->get(TargetOpcode::COPY)); 1707239462Sdim DEBUG(dbgs() << "\t\tconvert to:\t" << *mi); 1708210299Sed } 1709210299Sed 1710198090Srdivacky // Clear TiedOperands here instead of at the top of the loop 1711198090Srdivacky // since most instructions do not have tied operands. 1712198090Srdivacky TiedOperands.clear(); 1713193323Sed mi = nmi; 1714193323Sed } 1715193323Sed } 1716193323Sed 1717249423Sdim if (LIS) 1718249423Sdim MF->verify(this, "After two-address instruction pass"); 1719208599Srdivacky 1720193323Sed return MadeChange; 1721193323Sed} 1722208599Srdivacky 1723249423Sdim/// Eliminate a REG_SEQUENCE instruction as part of the de-ssa process. 1724249423Sdim/// 1725249423Sdim/// The instruction is turned into a sequence of sub-register copies: 1726249423Sdim/// 1727249423Sdim/// %dst = REG_SEQUENCE %v1, ssub0, %v2, ssub1 1728249423Sdim/// 1729249423Sdim/// Becomes: 1730249423Sdim/// 1731249423Sdim/// %dst:ssub0<def,undef> = COPY %v1 1732249423Sdim/// %dst:ssub1<def> = COPY %v2 1733249423Sdim/// 1734249423Sdimvoid TwoAddressInstructionPass:: 1735249423SdimeliminateRegSequence(MachineBasicBlock::iterator &MBBI) { 1736249423Sdim MachineInstr *MI = MBBI; 1737249423Sdim unsigned DstReg = MI->getOperand(0).getReg(); 1738249423Sdim if (MI->getOperand(0).getSubReg() || 1739249423Sdim TargetRegisterInfo::isPhysicalRegister(DstReg) || 1740249423Sdim !(MI->getNumOperands() & 1)) { 1741249423Sdim DEBUG(dbgs() << "Illegal REG_SEQUENCE instruction:" << *MI); 1742276479Sdim llvm_unreachable(nullptr); 1743208599Srdivacky } 1744208599Srdivacky 1745249423Sdim SmallVector<unsigned, 4> OrigRegs; 1746249423Sdim if (LIS) { 1747249423Sdim OrigRegs.push_back(MI->getOperand(0).getReg()); 1748249423Sdim for (unsigned i = 1, e = MI->getNumOperands(); i < e; i += 2) 1749249423Sdim OrigRegs.push_back(MI->getOperand(i).getReg()); 1750249423Sdim } 1751234353Sdim 1752249423Sdim bool DefEmitted = false; 1753249423Sdim for (unsigned i = 1, e = MI->getNumOperands(); i < e; i += 2) { 1754249423Sdim MachineOperand &UseMO = MI->getOperand(i); 1755249423Sdim unsigned SrcReg = UseMO.getReg(); 1756249423Sdim unsigned SubIdx = MI->getOperand(i+1).getImm(); 1757249423Sdim // Nothing needs to be inserted for <undef> operands. 1758249423Sdim if (UseMO.isUndef()) 1759249423Sdim continue; 1760234353Sdim 1761249423Sdim // Defer any kill flag to the last operand using SrcReg. Otherwise, we 1762249423Sdim // might insert a COPY that uses SrcReg after is was killed. 1763249423Sdim bool isKill = UseMO.isKill(); 1764249423Sdim if (isKill) 1765249423Sdim for (unsigned j = i + 2; j < e; j += 2) 1766249423Sdim if (MI->getOperand(j).getReg() == SrcReg) { 1767249423Sdim MI->getOperand(j).setIsKill(); 1768249423Sdim UseMO.setIsKill(false); 1769249423Sdim isKill = false; 1770249423Sdim break; 1771249423Sdim } 1772208599Srdivacky 1773249423Sdim // Insert the sub-register copy. 1774249423Sdim MachineInstr *CopyMI = BuildMI(*MI->getParent(), MI, MI->getDebugLoc(), 1775249423Sdim TII->get(TargetOpcode::COPY)) 1776249423Sdim .addReg(DstReg, RegState::Define, SubIdx) 1777249423Sdim .addOperand(UseMO); 1778208599Srdivacky 1779249423Sdim // The first def needs an <undef> flag because there is no live register 1780249423Sdim // before it. 1781249423Sdim if (!DefEmitted) { 1782249423Sdim CopyMI->getOperand(0).setIsUndef(true); 1783249423Sdim // Return an iterator pointing to the first inserted instr. 1784249423Sdim MBBI = CopyMI; 1785208599Srdivacky } 1786249423Sdim DefEmitted = true; 1787208599Srdivacky 1788249423Sdim // Update LiveVariables' kill info. 1789249423Sdim if (LV && isKill && !TargetRegisterInfo::isPhysicalRegister(SrcReg)) 1790249423Sdim LV->replaceKillInstruction(SrcReg, MI, CopyMI); 1791208599Srdivacky 1792249423Sdim DEBUG(dbgs() << "Inserted: " << *CopyMI); 1793249423Sdim } 1794208599Srdivacky 1795249423Sdim MachineBasicBlock::iterator EndMBBI = 1796276479Sdim std::next(MachineBasicBlock::iterator(MI)); 1797208599Srdivacky 1798249423Sdim if (!DefEmitted) { 1799249423Sdim DEBUG(dbgs() << "Turned: " << *MI << " into an IMPLICIT_DEF"); 1800249423Sdim MI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF)); 1801249423Sdim for (int j = MI->getNumOperands() - 1, ee = 0; j > ee; --j) 1802249423Sdim MI->RemoveOperand(j); 1803249423Sdim } else { 1804249423Sdim DEBUG(dbgs() << "Eliminated: " << *MI); 1805249423Sdim MI->eraseFromParent(); 1806208599Srdivacky } 1807208599Srdivacky 1808249423Sdim // Udpate LiveIntervals. 1809249423Sdim if (LIS) 1810249423Sdim LIS->repairIntervalsInRange(MBB, MBBI, EndMBBI, OrigRegs); 1811208599Srdivacky} 1812