X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FTwoAddressInstructionPass.cpp;h=24b8bc2048a7d4b6f4035a3dc82096625cf4f541;hb=948a44458c2965e6c2924bbd47c4d41bda0d78f0;hp=d8871f98ac785ead706d2cf2247b8504626789a7;hpb=d4034b2825a2a030893593327d67ca12b4e8a249;p=oota-llvm.git diff --git a/lib/CodeGen/TwoAddressInstructionPass.cpp b/lib/CodeGen/TwoAddressInstructionPass.cpp index d8871f98ac7..24b8bc2048a 100644 --- a/lib/CodeGen/TwoAddressInstructionPass.cpp +++ b/lib/CodeGen/TwoAddressInstructionPass.cpp @@ -33,13 +33,16 @@ #include "llvm/CodeGen/LiveVariables.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstr.h" +#include "llvm/CodeGen/MachineInstrBuilder.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/MC/MCInstrItineraries.h" #include "llvm/Target/TargetRegisterInfo.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetOptions.h" -#include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" #include "llvm/ADT/BitVector.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallSet.h" @@ -54,14 +57,18 @@ STATISTIC(NumConvertedTo3Addr, "Number of instructions promoted to 3-address"); STATISTIC(Num3AddrSunk, "Number of 3-address instructions sunk"); STATISTIC(NumReMats, "Number of instructions re-materialized"); STATISTIC(NumDeletes, "Number of dead instructions deleted"); +STATISTIC(NumReSchedUps, "Number of instructions re-scheduled up"); +STATISTIC(NumReSchedDowns, "Number of instructions re-scheduled down"); namespace { - class VISIBILITY_HIDDEN TwoAddressInstructionPass - : public MachineFunctionPass { + class TwoAddressInstructionPass : public MachineFunctionPass { const TargetInstrInfo *TII; const TargetRegisterInfo *TRI; + const InstrItineraryData *InstrItins; MachineRegisterInfo *MRI; LiveVariables *LV; + AliasAnalysis *AA; + CodeGenOpt::Level OptLevel; // DistanceMap - Keep track the distance of a MI from the start of the // current basic block. @@ -77,6 +84,10 @@ namespace { // registers from virtual registers. e.g. r1 = move v1024. DenseMap DstRegMap; + /// RegSequences - Keep track the list of REG_SEQUENCE instructions seen + /// during the initial walk of the machine function. + SmallVector RegSequences; + bool Sink3AddrInstruction(MachineBasicBlock *MBB, MachineInstr *MI, unsigned Reg, MachineBasicBlock::iterator OldPos); @@ -99,29 +110,65 @@ namespace { MachineFunction::iterator &mbbi, unsigned RegB, unsigned RegC, unsigned Dist); - bool isProfitableToConv3Addr(unsigned RegA); + bool isProfitableToConv3Addr(unsigned RegA, unsigned RegB); bool ConvertInstTo3Addr(MachineBasicBlock::iterator &mi, MachineBasicBlock::iterator &nmi, MachineFunction::iterator &mbbi, - unsigned RegB, unsigned Dist); + unsigned RegA, unsigned RegB, unsigned Dist); + + typedef std::pair, MachineInstr*> NewKill; + bool canUpdateDeletedKills(SmallVector &Kills, + SmallVector &NewKills, + MachineBasicBlock *MBB, unsigned Dist); + bool DeleteUnusedInstr(MachineBasicBlock::iterator &mi, + MachineBasicBlock::iterator &nmi, + MachineFunction::iterator &mbbi, unsigned Dist); + + bool isDefTooClose(unsigned Reg, unsigned Dist, + MachineInstr *MI, MachineBasicBlock *MBB); + + bool RescheduleMIBelowKill(MachineBasicBlock *MBB, + MachineBasicBlock::iterator &mi, + MachineBasicBlock::iterator &nmi, + unsigned Reg); + bool RescheduleKillAboveMI(MachineBasicBlock *MBB, + MachineBasicBlock::iterator &mi, + MachineBasicBlock::iterator &nmi, + unsigned Reg); + + bool TryInstructionTransform(MachineBasicBlock::iterator &mi, + MachineBasicBlock::iterator &nmi, + MachineFunction::iterator &mbbi, + unsigned SrcIdx, unsigned DstIdx, + unsigned Dist, + SmallPtrSet &Processed); + + void ScanUses(unsigned DstReg, MachineBasicBlock *MBB, + SmallPtrSet &Processed); void ProcessCopy(MachineInstr *MI, MachineBasicBlock *MBB, SmallPtrSet &Processed); + void CoalesceExtSubRegs(SmallVector &Srcs, unsigned DstReg); + + /// EliminateRegSequences - Eliminate REG_SEQUENCE instructions as part + /// of the de-ssa process. This replaces sources of REG_SEQUENCE as + /// sub-register references of the register defined by REG_SEQUENCE. + bool EliminateRegSequences(); + public: static char ID; // Pass identification, replacement for typeid - TwoAddressInstructionPass() : MachineFunctionPass(&ID) {} + TwoAddressInstructionPass() : MachineFunctionPass(ID) { + initializeTwoAddressInstructionPassPass(*PassRegistry::getPassRegistry()); + } virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesCFG(); + AU.addRequired(); AU.addPreserved(); AU.addPreservedID(MachineLoopInfoID); AU.addPreservedID(MachineDominatorsID); - if (StrongPHIElim) - AU.addPreservedID(StrongPHIEliminationID); - else - AU.addPreservedID(PHIEliminationID); MachineFunctionPass::getAnalysisUsage(AU); } @@ -131,10 +178,13 @@ namespace { } char TwoAddressInstructionPass::ID = 0; -static RegisterPass -X("twoaddressinstruction", "Two-Address instruction pass"); +INITIALIZE_PASS_BEGIN(TwoAddressInstructionPass, "twoaddressinstruction", + "Two-Address instruction pass", false, false) +INITIALIZE_AG_DEPENDENCY(AliasAnalysis) +INITIALIZE_PASS_END(TwoAddressInstructionPass, "twoaddressinstruction", + "Two-Address instruction pass", false, false) -const PassInfo *const llvm::TwoAddressInstructionPassID = &X; +char &llvm::TwoAddressInstructionPassID = TwoAddressInstructionPass::ID; /// Sink3AddrInstruction - A two-address instruction has been converted to a /// three-address instruction to avoid clobbering a register. Try to sink it @@ -143,9 +193,13 @@ const PassInfo *const llvm::TwoAddressInstructionPassID = &X; bool TwoAddressInstructionPass::Sink3AddrInstruction(MachineBasicBlock *MBB, MachineInstr *MI, unsigned SavedReg, MachineBasicBlock::iterator OldPos) { + // FIXME: Shouldn't we be trying to do this before we three-addressify the + // instruction? After this transformation is done, we no longer need + // the instruction to be in three-address form. + // Check if it's safe to move this instruction. bool SeenStore = true; // Be conservative. - if (!MI->isSafeToMove(TII, SeenStore)) + if (!MI->isSafeToMove(TII, AA, SeenStore)) return false; unsigned DefReg = 0; @@ -173,8 +227,9 @@ bool TwoAddressInstructionPass::Sink3AddrInstruction(MachineBasicBlock *MBB, // Find the instruction that kills SavedReg. MachineInstr *KillMI = NULL; - for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(SavedReg), - UE = MRI->use_end(); UI != UE; ++UI) { + for (MachineRegisterInfo::use_nodbg_iterator + UI = MRI->use_nodbg_begin(SavedReg), + UE = MRI->use_nodbg_end(); UI != UE; ++UI) { MachineOperand &UseMO = UI.getOperand(); if (!UseMO.isKill()) continue; @@ -182,12 +237,16 @@ bool TwoAddressInstructionPass::Sink3AddrInstruction(MachineBasicBlock *MBB, break; } - if (!KillMI || KillMI->getParent() != MBB || KillMI == MI) + // If we find the instruction that kills SavedReg, and it is in an + // appropriate location, we can try to sink the current instruction + // past it. + if (!KillMI || KillMI->getParent() != MBB || KillMI == MI || + KillMI->isTerminator()) return false; // If any of the definitions are used by another instruction between the // position and the kill use, then it's not safe to sink it. - // + // // FIXME: This can be sped up if there is an easy way to query whether an // instruction is before or after another instruction. Then we can use // MachineRegisterInfo def / use instead. @@ -196,8 +255,11 @@ bool TwoAddressInstructionPass::Sink3AddrInstruction(MachineBasicBlock *MBB, ++KillPos; unsigned NumVisited = 0; - for (MachineBasicBlock::iterator I = next(OldPos); I != KillPos; ++I) { + for (MachineBasicBlock::iterator I = llvm::next(OldPos); I != KillPos; ++I) { MachineInstr *OtherMI = I; + // DBG_VALUE cannot be counted against the limit. + if (OtherMI->isDebugValue()) + continue; if (NumVisited > 30) // FIXME: Arbitrary limit to reduce compile time cost. return false; ++NumVisited; @@ -227,7 +289,7 @@ bool TwoAddressInstructionPass::Sink3AddrInstruction(MachineBasicBlock *MBB, KillMO->setIsKill(false); KillMO = MI->findRegisterUseOperand(SavedReg, false, TRI); KillMO->setIsKill(true); - + if (LV) LV->replaceKillInstruction(SavedReg, KillMI, MI); @@ -242,8 +304,8 @@ bool TwoAddressInstructionPass::Sink3AddrInstruction(MachineBasicBlock *MBB, /// isTwoAddrUse - Return true if the specified MI is using the specified /// register as a two-address operand. static bool isTwoAddrUse(MachineInstr *UseMI, unsigned Reg) { - const TargetInstrDesc &TID = UseMI->getDesc(); - for (unsigned i = 0, e = TID.getNumOperands(); i != e; ++i) { + const MCInstrDesc &MCID = UseMI->getDesc(); + for (unsigned i = 0, e = MCID.getNumOperands(); i != e; ++i) { MachineOperand &MO = UseMI->getOperand(i); if (MO.isReg() && MO.getReg() == Reg && (MO.isDef() || UseMI->isRegTiedToDefOperand(i))) @@ -262,8 +324,8 @@ TwoAddressInstructionPass::isProfitableToReMat(unsigned Reg, MachineInstr *MI, MachineInstr *DefMI, MachineBasicBlock *MBB, unsigned Loc) { bool OtherUse = false; - for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg), - UE = MRI->use_end(); UI != UE; ++UI) { + for (MachineRegisterInfo::use_nodbg_iterator UI = MRI->use_nodbg_begin(Reg), + UE = MRI->use_nodbg_end(); UI != UE; ++UI) { MachineOperand &UseMO = UI.getOperand(); MachineInstr *UseMI = UseMO.getParent(); MachineBasicBlock *UseMBB = UseMI->getParent(); @@ -273,7 +335,7 @@ TwoAddressInstructionPass::isProfitableToReMat(unsigned Reg, continue; // Current use. OtherUse = true; // There is at least one other use in the MBB that will clobber the - // register. + // register. if (isTwoAddrUse(UseMI, Reg)) return true; } @@ -301,7 +363,7 @@ bool TwoAddressInstructionPass::NoUseAfterLastDef(unsigned Reg, E = MRI->reg_end(); I != E; ++I) { MachineOperand &MO = I.getOperand(); MachineInstr *MI = MO.getParent(); - if (MI->getParent() != MBB) + if (MI->getParent() != MBB || MI->isDebugValue()) continue; DenseMap::iterator DI = DistanceMap.find(MI); if (DI == DistanceMap.end()) @@ -324,7 +386,7 @@ MachineInstr *TwoAddressInstructionPass::FindLastUseInMBB(unsigned Reg, E = MRI->reg_end(); I != E; ++I) { MachineOperand &MO = I.getOperand(); MachineInstr *MI = MO.getParent(); - if (MI->getParent() != MBB) + if (MI->getParent() != MBB || MI->isDebugValue()) continue; DenseMap::iterator DI = DistanceMap.find(MI); if (DI == DistanceMap.end()) @@ -348,26 +410,18 @@ static bool isCopyToReg(MachineInstr &MI, const TargetInstrInfo *TII, bool &IsSrcPhys, bool &IsDstPhys) { SrcReg = 0; DstReg = 0; - unsigned SrcSubIdx, DstSubIdx; - if (!TII->isMoveInstr(MI, SrcReg, DstReg, SrcSubIdx, DstSubIdx)) { - if (MI.getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) { - DstReg = MI.getOperand(0).getReg(); - SrcReg = MI.getOperand(1).getReg(); - } else if (MI.getOpcode() == TargetInstrInfo::INSERT_SUBREG) { - DstReg = MI.getOperand(0).getReg(); - SrcReg = MI.getOperand(2).getReg(); - } else if (MI.getOpcode() == TargetInstrInfo::SUBREG_TO_REG) { - DstReg = MI.getOperand(0).getReg(); - SrcReg = MI.getOperand(2).getReg(); - } - } - - if (DstReg) { - IsSrcPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg); - IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); - return true; - } - return false; + if (MI.isCopy()) { + DstReg = MI.getOperand(0).getReg(); + SrcReg = MI.getOperand(1).getReg(); + } else if (MI.isInsertSubreg() || MI.isSubregToReg()) { + DstReg = MI.getOperand(0).getReg(); + SrcReg = MI.getOperand(2).getReg(); + } else + return false; + + IsSrcPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg); + IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); + return true; } /// isKilled - Test if the given register value, which is used by the given @@ -397,7 +451,7 @@ static bool isKilled(MachineInstr &MI, unsigned Reg, MachineRegisterInfo::def_iterator Begin = MRI->def_begin(Reg); // If there are multiple defs, we can't do a simple analysis, so just // go with what the kill flag says. - if (next(Begin) != MRI->def_end()) + if (llvm::next(Begin) != MRI->def_end()) return true; DefMI = &*Begin; bool IsSrcPhys, IsDstPhys; @@ -413,9 +467,9 @@ static bool isKilled(MachineInstr &MI, unsigned Reg, /// isTwoAddrUse - Return true if the specified MI uses the specified register /// as a two-address use. If so, return the destination register by reference. static bool isTwoAddrUse(MachineInstr &MI, unsigned Reg, unsigned &DstReg) { - const TargetInstrDesc &TID = MI.getDesc(); - unsigned NumOps = (MI.getOpcode() == TargetInstrInfo::INLINEASM) - ? MI.getNumOperands() : TID.getNumOperands(); + const MCInstrDesc &MCID = MI.getDesc(); + unsigned NumOps = MI.isInlineAsm() + ? MI.getNumOperands() : MCID.getNumOperands(); for (unsigned i = 0; i != NumOps; ++i) { const MachineOperand &MO = MI.getOperand(i); if (!MO.isReg() || !MO.isUse() || MO.getReg() != Reg) @@ -429,6 +483,32 @@ static bool isTwoAddrUse(MachineInstr &MI, unsigned Reg, unsigned &DstReg) { return false; } +/// findLocalKill - Look for an instruction below MI in the MBB that kills the +/// specified register. Returns null if there are any other Reg use between the +/// instructions. +static +MachineInstr *findLocalKill(unsigned Reg, MachineBasicBlock *MBB, + MachineInstr *MI, MachineRegisterInfo *MRI, + DenseMap &DistanceMap) { + MachineInstr *KillMI = 0; + for (MachineRegisterInfo::use_nodbg_iterator + UI = MRI->use_nodbg_begin(Reg), + UE = MRI->use_nodbg_end(); UI != UE; ++UI) { + MachineInstr *UseMI = &*UI; + if (UseMI == MI || UseMI->getParent() != MBB) + continue; + if (DistanceMap.count(UseMI)) + continue; + if (!UI.getOperand().isKill()) + return 0; + if (KillMI) + return 0; // -O0 kill markers cannot be trusted? + KillMI = UseMI; + } + + return KillMI; +} + /// findOnlyInterestingUse - Given a register, if has a single in-basic block /// use, return the use instruction if it's a copy or a two-address use. static @@ -437,13 +517,10 @@ MachineInstr *findOnlyInterestingUse(unsigned Reg, MachineBasicBlock *MBB, const TargetInstrInfo *TII, bool &IsCopy, unsigned &DstReg, bool &IsDstPhys) { - MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg); - if (UI == MRI->use_end()) - return 0; - MachineInstr &UseMI = *UI; - if (++UI != MRI->use_end()) - // More than one use. + if (!MRI->hasOneNonDBGUse(Reg)) + // None or more than one use. return 0; + MachineInstr &UseMI = *MRI->use_nodbg_begin(Reg); if (UseMI.getParent() != MBB) return 0; unsigned SrcReg; @@ -493,6 +570,9 @@ bool TwoAddressInstructionPass::isProfitableToCommute(unsigned regB, unsigned regC, MachineInstr *MI, MachineBasicBlock *MBB, unsigned Dist) { + if (OptLevel == CodeGenOpt::None) + return false; + // Determine if it's profitable to commute this two address instruction. In // general, we want no uses between this instruction and the definition of // the two-address register. @@ -509,7 +589,7 @@ TwoAddressInstructionPass::isProfitableToCommute(unsigned regB, unsigned regC, // %reg1029 = MOV8rr %reg1028 // %reg1029 = SHR8ri %reg1029, 7, %EFLAGS // insert => %reg1030 = MOV8rr %reg1029 - // %reg1030 = ADD8rr %reg1029, %reg1028, %EFLAGS + // %reg1030 = ADD8rr %reg1029, %reg1028, %EFLAGS if (!MI->killsRegister(regC)) return false; @@ -528,8 +608,9 @@ TwoAddressInstructionPass::isProfitableToCommute(unsigned regB, unsigned regC, unsigned FromRegC = getMappedReg(regC, SrcRegMap); unsigned ToRegB = getMappedReg(regB, DstRegMap); unsigned ToRegC = getMappedReg(regC, DstRegMap); - if (!regsAreCompatible(FromRegB, ToRegB, TRI) && - (regsAreCompatible(FromRegB, ToRegC, TRI) || + if ((FromRegB && ToRegB && !regsAreCompatible(FromRegB, ToRegB, TRI)) && + ((!FromRegC && !ToRegC) || + regsAreCompatible(FromRegB, ToRegC, TRI) || regsAreCompatible(FromRegC, ToRegB, TRI))) return true; @@ -558,15 +639,15 @@ TwoAddressInstructionPass::CommuteInstruction(MachineBasicBlock::iterator &mi, MachineFunction::iterator &mbbi, unsigned RegB, unsigned RegC, unsigned Dist) { MachineInstr *MI = mi; - DEBUG(errs() << "2addr: COMMUTING : " << *MI); + DEBUG(dbgs() << "2addr: COMMUTING : " << *MI); MachineInstr *NewMI = TII->commuteInstruction(MI); if (NewMI == 0) { - DEBUG(errs() << "2addr: COMMUTING FAILED!\n"); + DEBUG(dbgs() << "2addr: COMMUTING FAILED!\n"); return false; } - DEBUG(errs() << "2addr: COMMUTED TO: " << *NewMI); + DEBUG(dbgs() << "2addr: COMMUTED TO: " << *NewMI); // If the instruction changed to commute it, update livevar. if (NewMI != MI) { if (LV) @@ -592,16 +673,18 @@ TwoAddressInstructionPass::CommuteInstruction(MachineBasicBlock::iterator &mi, /// isProfitableToConv3Addr - Return true if it is profitable to convert the /// given 2-address instruction to a 3-address one. bool -TwoAddressInstructionPass::isProfitableToConv3Addr(unsigned RegA) { +TwoAddressInstructionPass::isProfitableToConv3Addr(unsigned RegA,unsigned RegB){ // Look for situations like this: // %reg1024 = MOV r1 // %reg1025 = MOV r0 // %reg1026 = ADD %reg1024, %reg1025 // r2 = MOV %reg1026 // Turn ADD into a 3-address instruction to avoid a copy. - unsigned FromRegA = getMappedReg(RegA, SrcRegMap); + unsigned FromRegB = getMappedReg(RegB, SrcRegMap); + if (!FromRegB) + return false; unsigned ToRegA = getMappedReg(RegA, DstRegMap); - return (FromRegA && ToRegA && !regsAreCompatible(FromRegA, ToRegA, TRI)); + return (ToRegA && !regsAreCompatible(FromRegB, ToRegA, TRI)); } /// ConvertInstTo3Addr - Convert the specified two-address instruction into a @@ -610,11 +693,12 @@ bool TwoAddressInstructionPass::ConvertInstTo3Addr(MachineBasicBlock::iterator &mi, MachineBasicBlock::iterator &nmi, MachineFunction::iterator &mbbi, - unsigned RegB, unsigned Dist) { + unsigned RegA, unsigned RegB, + unsigned Dist) { MachineInstr *NewMI = TII->convertToThreeAddress(mbbi, mi, LV); if (NewMI) { - DEBUG(errs() << "2addr: CONVERTING 2-ADDR: " << *mi); - DEBUG(errs() << "2addr: TO 3-ADDR: " << *NewMI); + DEBUG(dbgs() << "2addr: CONVERTING 2-ADDR: " << *mi); + DEBUG(dbgs() << "2addr: TO 3-ADDR: " << *NewMI); bool Sunk = false; if (NewMI->findRegisterUseOperand(RegB, false, TRI)) @@ -628,14 +712,66 @@ TwoAddressInstructionPass::ConvertInstTo3Addr(MachineBasicBlock::iterator &mi, if (!Sunk) { DistanceMap.insert(std::make_pair(NewMI, Dist)); mi = NewMI; - nmi = next(mi); + nmi = llvm::next(mi); } + + // Update source and destination register maps. + SrcRegMap.erase(RegA); + DstRegMap.erase(RegB); return true; } return false; } +/// ScanUses - Scan forward recursively for only uses, update maps if the use +/// is a copy or a two-address instruction. +void +TwoAddressInstructionPass::ScanUses(unsigned DstReg, MachineBasicBlock *MBB, + SmallPtrSet &Processed) { + SmallVector VirtRegPairs; + bool IsDstPhys; + bool IsCopy = false; + unsigned NewReg = 0; + unsigned Reg = DstReg; + while (MachineInstr *UseMI = findOnlyInterestingUse(Reg, MBB, MRI, TII,IsCopy, + NewReg, IsDstPhys)) { + if (IsCopy && !Processed.insert(UseMI)) + break; + + DenseMap::iterator DI = DistanceMap.find(UseMI); + if (DI != DistanceMap.end()) + // Earlier in the same MBB.Reached via a back edge. + break; + + if (IsDstPhys) { + VirtRegPairs.push_back(NewReg); + break; + } + bool isNew = SrcRegMap.insert(std::make_pair(NewReg, Reg)).second; + if (!isNew) + assert(SrcRegMap[NewReg] == Reg && "Can't map to two src registers!"); + VirtRegPairs.push_back(NewReg); + Reg = NewReg; + } + + if (!VirtRegPairs.empty()) { + unsigned ToReg = VirtRegPairs.back(); + VirtRegPairs.pop_back(); + while (!VirtRegPairs.empty()) { + unsigned FromReg = VirtRegPairs.back(); + VirtRegPairs.pop_back(); + bool isNew = DstRegMap.insert(std::make_pair(FromReg, ToReg)).second; + if (!isNew) + assert(DstRegMap[FromReg] == ToReg &&"Can't map to two dst registers!"); + ToReg = FromReg; + } + bool isNew = DstRegMap.insert(std::make_pair(DstReg, ToReg)).second; + if (!isNew) + assert(DstRegMap[DstReg] == ToReg && "Can't map to two dst registers!"); + } +} + /// ProcessCopy - If the specified instruction is not yet processed, process it /// if it's a copy. For a copy instruction, we find the physical registers the /// source and destination registers might be mapped to. These are kept in @@ -667,60 +803,21 @@ void TwoAddressInstructionPass::ProcessCopy(MachineInstr *MI, assert(SrcRegMap[DstReg] == SrcReg && "Can't map to two src physical registers!"); - SmallVector VirtRegPairs; - bool IsCopy = false; - unsigned NewReg = 0; - while (MachineInstr *UseMI = findOnlyInterestingUse(DstReg, MBB, MRI,TII, - IsCopy, NewReg, IsDstPhys)) { - if (IsCopy) { - if (!Processed.insert(UseMI)) - break; - } - - DenseMap::iterator DI = DistanceMap.find(UseMI); - if (DI != DistanceMap.end()) - // Earlier in the same MBB.Reached via a back edge. - break; - - if (IsDstPhys) { - VirtRegPairs.push_back(NewReg); - break; - } - bool isNew = SrcRegMap.insert(std::make_pair(NewReg, DstReg)).second; - if (!isNew) - assert(SrcRegMap[NewReg] == DstReg && - "Can't map to two src physical registers!"); - VirtRegPairs.push_back(NewReg); - DstReg = NewReg; - } - - if (!VirtRegPairs.empty()) { - unsigned ToReg = VirtRegPairs.back(); - VirtRegPairs.pop_back(); - while (!VirtRegPairs.empty()) { - unsigned FromReg = VirtRegPairs.back(); - VirtRegPairs.pop_back(); - bool isNew = DstRegMap.insert(std::make_pair(FromReg, ToReg)).second; - if (!isNew) - assert(DstRegMap[FromReg] == ToReg && - "Can't map to two dst physical registers!"); - ToReg = FromReg; - } - } + ScanUses(DstReg, MBB, Processed); } Processed.insert(MI); + return; } /// isSafeToDelete - If the specified instruction does not produce any side /// effects and all of its defs are dead, then it's safe to delete. -static bool isSafeToDelete(MachineInstr *MI, unsigned Reg, +static bool isSafeToDelete(MachineInstr *MI, const TargetInstrInfo *TII, SmallVector &Kills) { - const TargetInstrDesc &TID = MI->getDesc(); - if (TID.mayStore() || TID.isCall()) + if (MI->mayStore() || MI->isCall()) return false; - if (TID.isTerminator() || TID.hasUnmodeledSideEffects()) + if (MI->isTerminator() || MI->hasUnmodeledSideEffects()) return false; for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { @@ -729,32 +826,585 @@ static bool isSafeToDelete(MachineInstr *MI, unsigned Reg, continue; if (MO.isDef() && !MO.isDead()) return false; - if (MO.isUse() && MO.getReg() != Reg && MO.isKill()) + if (MO.isUse() && MO.isKill()) Kills.push_back(MO.getReg()); } + return true; +} + +/// canUpdateDeletedKills - Check if all the registers listed in Kills are +/// killed by instructions in MBB preceding the current instruction at +/// position Dist. If so, return true and record information about the +/// preceding kills in NewKills. +bool TwoAddressInstructionPass:: +canUpdateDeletedKills(SmallVector &Kills, + SmallVector &NewKills, + MachineBasicBlock *MBB, unsigned Dist) { + while (!Kills.empty()) { + unsigned Kill = Kills.back(); + Kills.pop_back(); + if (TargetRegisterInfo::isPhysicalRegister(Kill)) + return false; + + MachineInstr *LastKill = FindLastUseInMBB(Kill, MBB, Dist); + if (!LastKill) + return false; + + bool isModRef = LastKill->definesRegister(Kill); + NewKills.push_back(std::make_pair(std::make_pair(Kill, isModRef), + LastKill)); + } + return true; +} + +/// DeleteUnusedInstr - If an instruction with a tied register operand can +/// be safely deleted, just delete it. +bool +TwoAddressInstructionPass::DeleteUnusedInstr(MachineBasicBlock::iterator &mi, + MachineBasicBlock::iterator &nmi, + MachineFunction::iterator &mbbi, + unsigned Dist) { + // Check if the instruction has no side effects and if all its defs are dead. + SmallVector Kills; + if (!isSafeToDelete(mi, TII, Kills)) + return false; + + // If this instruction kills some virtual registers, we need to + // update the kill information. If it's not possible to do so, + // then bail out. + SmallVector NewKills; + if (!canUpdateDeletedKills(Kills, NewKills, &*mbbi, Dist)) + return false; + + if (LV) { + while (!NewKills.empty()) { + MachineInstr *NewKill = NewKills.back().second; + unsigned Kill = NewKills.back().first.first; + bool isDead = NewKills.back().first.second; + NewKills.pop_back(); + if (LV->removeVirtualRegisterKilled(Kill, mi)) { + if (isDead) + LV->addVirtualRegisterDead(Kill, NewKill); + else + LV->addVirtualRegisterKilled(Kill, NewKill); + } + } + } + + mbbi->erase(mi); // Nuke the old inst. + mi = nmi; + return true; +} + +/// RescheduleMIBelowKill - If there is one more local instruction that reads +/// 'Reg' and it kills 'Reg, consider moving the instruction below the kill +/// instruction in order to eliminate the need for the copy. +bool +TwoAddressInstructionPass::RescheduleMIBelowKill(MachineBasicBlock *MBB, + MachineBasicBlock::iterator &mi, + MachineBasicBlock::iterator &nmi, + unsigned Reg) { + MachineInstr *MI = &*mi; + DenseMap::iterator DI = DistanceMap.find(MI); + if (DI == DistanceMap.end()) + // Must be created from unfolded load. Don't waste time trying this. + return false; + + MachineInstr *KillMI = findLocalKill(Reg, MBB, mi, MRI, DistanceMap); + if (!KillMI || KillMI->isCopy() || KillMI->isCopyLike()) + // Don't mess with copies, they may be coalesced later. + return false; + + if (KillMI->hasUnmodeledSideEffects() || KillMI->isCall() || + KillMI->isBranch() || KillMI->isTerminator()) + // Don't move pass calls, etc. + return false; + + unsigned DstReg; + if (isTwoAddrUse(*KillMI, Reg, DstReg)) + return false; + + bool SeenStore = true; + if (!MI->isSafeToMove(TII, AA, SeenStore)) + return false; + + if (TII->getInstrLatency(InstrItins, MI) > 1) + // FIXME: Needs more sophisticated heuristics. + return false; + + SmallSet Uses; + SmallSet Kills; + SmallSet Defs; + for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { + const MachineOperand &MO = MI->getOperand(i); + if (!MO.isReg()) + continue; + unsigned MOReg = MO.getReg(); + if (!MOReg) + continue; + if (MO.isDef()) + Defs.insert(MOReg); + else { + Uses.insert(MOReg); + if (MO.isKill() && MOReg != Reg) + Kills.insert(MOReg); + } + } + + // Move the copies connected to MI down as well. + MachineBasicBlock::iterator From = MI; + MachineBasicBlock::iterator To = llvm::next(From); + while (To->isCopy() && Defs.count(To->getOperand(1).getReg())) { + Defs.insert(To->getOperand(0).getReg()); + ++To; + } + + // Check if the reschedule will not break depedencies. + unsigned NumVisited = 0; + MachineBasicBlock::iterator KillPos = KillMI; + ++KillPos; + for (MachineBasicBlock::iterator I = To; I != KillPos; ++I) { + MachineInstr *OtherMI = I; + // DBG_VALUE cannot be counted against the limit. + if (OtherMI->isDebugValue()) + continue; + if (NumVisited > 10) // FIXME: Arbitrary limit to reduce compile time cost. + return false; + ++NumVisited; + if (OtherMI->hasUnmodeledSideEffects() || OtherMI->isCall() || + OtherMI->isBranch() || OtherMI->isTerminator()) + // Don't move pass calls, etc. + return false; + for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) { + const MachineOperand &MO = OtherMI->getOperand(i); + if (!MO.isReg()) + continue; + unsigned MOReg = MO.getReg(); + if (!MOReg) + continue; + if (MO.isDef()) { + if (Uses.count(MOReg)) + // Physical register use would be clobbered. + return false; + if (!MO.isDead() && Defs.count(MOReg)) + // May clobber a physical register def. + // FIXME: This may be too conservative. It's ok if the instruction + // is sunken completely below the use. + return false; + } else { + if (Defs.count(MOReg)) + return false; + if (MOReg != Reg && + ((MO.isKill() && Uses.count(MOReg)) || Kills.count(MOReg))) + // Don't want to extend other live ranges and update kills. + return false; + } + } + } + + // Move debug info as well. + while (From != MBB->begin() && llvm::prior(From)->isDebugValue()) + --From; + + // Copies following MI may have been moved as well. + nmi = To; + MBB->splice(KillPos, MBB, From, To); + DistanceMap.erase(DI); + + if (LV) { + // Update live variables + LV->removeVirtualRegisterKilled(Reg, KillMI); + LV->addVirtualRegisterKilled(Reg, MI); + } else { + for (unsigned i = 0, e = KillMI->getNumOperands(); i != e; ++i) { + MachineOperand &MO = KillMI->getOperand(i); + if (!MO.isReg() || !MO.isUse() || MO.getReg() != Reg) + continue; + MO.setIsKill(false); + } + MI->addRegisterKilled(Reg, 0); + } + + return true; +} + +/// isDefTooClose - Return true if the re-scheduling will put the given +/// instruction too close to the defs of its register dependencies. +bool TwoAddressInstructionPass::isDefTooClose(unsigned Reg, unsigned Dist, + MachineInstr *MI, + MachineBasicBlock *MBB) { + for (MachineRegisterInfo::def_iterator DI = MRI->def_begin(Reg), + DE = MRI->def_end(); DI != DE; ++DI) { + MachineInstr *DefMI = &*DI; + if (DefMI->getParent() != MBB || DefMI->isCopy() || DefMI->isCopyLike()) + continue; + if (DefMI == MI) + return true; // MI is defining something KillMI uses + DenseMap::iterator DDI = DistanceMap.find(DefMI); + if (DDI == DistanceMap.end()) + return true; // Below MI + unsigned DefDist = DDI->second; + assert(Dist > DefDist && "Visited def already?"); + if (TII->getInstrLatency(InstrItins, DefMI) > (int)(Dist - DefDist)) + return true; + } + return false; +} + +/// RescheduleKillAboveMI - If there is one more local instruction that reads +/// 'Reg' and it kills 'Reg, consider moving the kill instruction above the +/// current two-address instruction in order to eliminate the need for the +/// copy. +bool +TwoAddressInstructionPass::RescheduleKillAboveMI(MachineBasicBlock *MBB, + MachineBasicBlock::iterator &mi, + MachineBasicBlock::iterator &nmi, + unsigned Reg) { + MachineInstr *MI = &*mi; + DenseMap::iterator DI = DistanceMap.find(MI); + if (DI == DistanceMap.end()) + // Must be created from unfolded load. Don't waste time trying this. + return false; + + MachineInstr *KillMI = findLocalKill(Reg, MBB, mi, MRI, DistanceMap); + if (!KillMI || KillMI->isCopy() || KillMI->isCopyLike()) + // Don't mess with copies, they may be coalesced later. + return false; + + unsigned DstReg; + if (isTwoAddrUse(*KillMI, Reg, DstReg)) + return false; + + bool SeenStore = true; + if (!KillMI->isSafeToMove(TII, AA, SeenStore)) + return false; + + SmallSet Uses; + SmallSet Kills; + SmallSet Defs; + SmallSet LiveDefs; + for (unsigned i = 0, e = KillMI->getNumOperands(); i != e; ++i) { + const MachineOperand &MO = KillMI->getOperand(i); + if (!MO.isReg()) + continue; + unsigned MOReg = MO.getReg(); + if (MO.isUse()) { + if (!MOReg) + continue; + if (isDefTooClose(MOReg, DI->second, MI, MBB)) + return false; + Uses.insert(MOReg); + if (MO.isKill() && MOReg != Reg) + Kills.insert(MOReg); + } else if (TargetRegisterInfo::isPhysicalRegister(MOReg)) { + Defs.insert(MOReg); + if (!MO.isDead()) + LiveDefs.insert(MOReg); + } + } + + // Check if the reschedule will not break depedencies. + unsigned NumVisited = 0; + MachineBasicBlock::iterator KillPos = KillMI; + for (MachineBasicBlock::iterator I = mi; I != KillPos; ++I) { + MachineInstr *OtherMI = I; + // DBG_VALUE cannot be counted against the limit. + if (OtherMI->isDebugValue()) + continue; + if (NumVisited > 10) // FIXME: Arbitrary limit to reduce compile time cost. + return false; + ++NumVisited; + if (OtherMI->hasUnmodeledSideEffects() || OtherMI->isCall() || + OtherMI->isBranch() || OtherMI->isTerminator()) + // Don't move pass calls, etc. + return false; + SmallVector OtherDefs; + for (unsigned i = 0, e = OtherMI->getNumOperands(); i != e; ++i) { + const MachineOperand &MO = OtherMI->getOperand(i); + if (!MO.isReg()) + continue; + unsigned MOReg = MO.getReg(); + if (!MOReg) + continue; + if (MO.isUse()) { + if (Defs.count(MOReg)) + // Moving KillMI can clobber the physical register if the def has + // not been seen. + return false; + if (Kills.count(MOReg)) + // Don't want to extend other live ranges and update kills. + return false; + } else { + OtherDefs.push_back(MOReg); + } + } + + for (unsigned i = 0, e = OtherDefs.size(); i != e; ++i) { + unsigned MOReg = OtherDefs[i]; + if (Uses.count(MOReg)) + return false; + if (TargetRegisterInfo::isPhysicalRegister(MOReg) && + LiveDefs.count(MOReg)) + return false; + // Physical register def is seen. + Defs.erase(MOReg); + } + } + // Move the old kill above MI, don't forget to move debug info as well. + MachineBasicBlock::iterator InsertPos = mi; + while (InsertPos != MBB->begin() && llvm::prior(InsertPos)->isDebugValue()) + --InsertPos; + MachineBasicBlock::iterator From = KillMI; + MachineBasicBlock::iterator To = llvm::next(From); + while (llvm::prior(From)->isDebugValue()) + --From; + MBB->splice(InsertPos, MBB, From, To); + + nmi = llvm::prior(InsertPos); // Backtrack so we process the moved instr. + DistanceMap.erase(DI); + + if (LV) { + // Update live variables + LV->removeVirtualRegisterKilled(Reg, KillMI); + LV->addVirtualRegisterKilled(Reg, MI); + } else { + for (unsigned i = 0, e = KillMI->getNumOperands(); i != e; ++i) { + MachineOperand &MO = KillMI->getOperand(i); + if (!MO.isReg() || !MO.isUse() || MO.getReg() != Reg) + continue; + MO.setIsKill(false); + } + MI->addRegisterKilled(Reg, 0); + } return true; } +/// TryInstructionTransform - For the case where an instruction has a single +/// pair of tied register operands, attempt some transformations that may +/// either eliminate the tied operands or improve the opportunities for +/// coalescing away the register copy. Returns true if the tied operands +/// are eliminated altogether. +bool TwoAddressInstructionPass:: +TryInstructionTransform(MachineBasicBlock::iterator &mi, + MachineBasicBlock::iterator &nmi, + MachineFunction::iterator &mbbi, + unsigned SrcIdx, unsigned DstIdx, unsigned Dist, + SmallPtrSet &Processed) { + if (OptLevel == CodeGenOpt::None) + return false; + + MachineInstr &MI = *mi; + unsigned regA = MI.getOperand(DstIdx).getReg(); + unsigned regB = MI.getOperand(SrcIdx).getReg(); + + assert(TargetRegisterInfo::isVirtualRegister(regB) && + "cannot make instruction into two-address form"); + + // If regA is dead and the instruction can be deleted, just delete + // it so it doesn't clobber regB. + bool regBKilled = isKilled(MI, regB, MRI, TII); + if (!regBKilled && MI.getOperand(DstIdx).isDead() && + DeleteUnusedInstr(mi, nmi, mbbi, Dist)) { + ++NumDeletes; + return true; // Done with this instruction. + } + + // Check if it is profitable to commute the operands. + unsigned SrcOp1, SrcOp2; + unsigned regC = 0; + unsigned regCIdx = ~0U; + bool TryCommute = false; + bool AggressiveCommute = false; + if (MI.isCommutable() && MI.getNumOperands() >= 3 && + TII->findCommutedOpIndices(&MI, SrcOp1, SrcOp2)) { + if (SrcIdx == SrcOp1) + regCIdx = SrcOp2; + else if (SrcIdx == SrcOp2) + regCIdx = SrcOp1; + + if (regCIdx != ~0U) { + regC = MI.getOperand(regCIdx).getReg(); + if (!regBKilled && isKilled(MI, regC, MRI, TII)) + // If C dies but B does not, swap the B and C operands. + // This makes the live ranges of A and C joinable. + TryCommute = true; + else if (isProfitableToCommute(regB, regC, &MI, mbbi, Dist)) { + TryCommute = true; + AggressiveCommute = true; + } + } + } + + // If it's profitable to commute, try to do so. + if (TryCommute && CommuteInstruction(mi, mbbi, regB, regC, Dist)) { + ++NumCommuted; + if (AggressiveCommute) + ++NumAggrCommuted; + return false; + } + + // If there is one more use of regB later in the same MBB, consider + // re-schedule this MI below it. + if (RescheduleMIBelowKill(mbbi, mi, nmi, regB)) { + ++NumReSchedDowns; + return true; + } + + if (TargetRegisterInfo::isVirtualRegister(regA)) + ScanUses(regA, &*mbbi, Processed); + + if (MI.isConvertibleTo3Addr()) { + // This instruction is potentially convertible to a true + // three-address instruction. Check if it is profitable. + if (!regBKilled || isProfitableToConv3Addr(regA, regB)) { + // Try to convert it. + if (ConvertInstTo3Addr(mi, nmi, mbbi, regA, regB, Dist)) { + ++NumConvertedTo3Addr; + return true; // Done with this instruction. + } + } + } + + // If there is one more use of regB later in the same MBB, consider + // re-schedule it before this MI if it's legal. + if (RescheduleKillAboveMI(mbbi, mi, nmi, regB)) { + ++NumReSchedUps; + return true; + } + + // If this is an instruction with a load folded into it, try unfolding + // the load, e.g. avoid this: + // movq %rdx, %rcx + // addq (%rax), %rcx + // in favor of this: + // movq (%rax), %rcx + // addq %rdx, %rcx + // because it's preferable to schedule a load than a register copy. + if (MI.mayLoad() && !regBKilled) { + // Determine if a load can be unfolded. + unsigned LoadRegIndex; + unsigned NewOpc = + TII->getOpcodeAfterMemoryUnfold(MI.getOpcode(), + /*UnfoldLoad=*/true, + /*UnfoldStore=*/false, + &LoadRegIndex); + if (NewOpc != 0) { + const MCInstrDesc &UnfoldMCID = TII->get(NewOpc); + if (UnfoldMCID.getNumDefs() == 1) { + MachineFunction &MF = *mbbi->getParent(); + + // Unfold the load. + DEBUG(dbgs() << "2addr: UNFOLDING: " << MI); + const TargetRegisterClass *RC = + TII->getRegClass(UnfoldMCID, LoadRegIndex, TRI); + unsigned Reg = MRI->createVirtualRegister(RC); + SmallVector NewMIs; + if (!TII->unfoldMemoryOperand(MF, &MI, Reg, + /*UnfoldLoad=*/true,/*UnfoldStore=*/false, + NewMIs)) { + DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n"); + return false; + } + assert(NewMIs.size() == 2 && + "Unfolded a load into multiple instructions!"); + // The load was previously folded, so this is the only use. + NewMIs[1]->addRegisterKilled(Reg, TRI); + + // Tentatively insert the instructions into the block so that they + // look "normal" to the transformation logic. + mbbi->insert(mi, NewMIs[0]); + mbbi->insert(mi, NewMIs[1]); + + DEBUG(dbgs() << "2addr: NEW LOAD: " << *NewMIs[0] + << "2addr: NEW INST: " << *NewMIs[1]); + + // Transform the instruction, now that it no longer has a load. + unsigned NewDstIdx = NewMIs[1]->findRegisterDefOperandIdx(regA); + unsigned NewSrcIdx = NewMIs[1]->findRegisterUseOperandIdx(regB); + MachineBasicBlock::iterator NewMI = NewMIs[1]; + bool TransformSuccess = + TryInstructionTransform(NewMI, mi, mbbi, + NewSrcIdx, NewDstIdx, Dist, Processed); + if (TransformSuccess || + NewMIs[1]->getOperand(NewSrcIdx).isKill()) { + // Success, or at least we made an improvement. Keep the unfolded + // instructions and discard the original. + if (LV) { + for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { + MachineOperand &MO = MI.getOperand(i); + if (MO.isReg() && + TargetRegisterInfo::isVirtualRegister(MO.getReg())) { + if (MO.isUse()) { + if (MO.isKill()) { + if (NewMIs[0]->killsRegister(MO.getReg())) + LV->replaceKillInstruction(MO.getReg(), &MI, NewMIs[0]); + else { + assert(NewMIs[1]->killsRegister(MO.getReg()) && + "Kill missing after load unfold!"); + LV->replaceKillInstruction(MO.getReg(), &MI, NewMIs[1]); + } + } + } else if (LV->removeVirtualRegisterDead(MO.getReg(), &MI)) { + if (NewMIs[1]->registerDefIsDead(MO.getReg())) + LV->addVirtualRegisterDead(MO.getReg(), NewMIs[1]); + else { + assert(NewMIs[0]->registerDefIsDead(MO.getReg()) && + "Dead flag missing after load unfold!"); + LV->addVirtualRegisterDead(MO.getReg(), NewMIs[0]); + } + } + } + } + LV->addVirtualRegisterKilled(Reg, NewMIs[1]); + } + MI.eraseFromParent(); + mi = NewMIs[1]; + if (TransformSuccess) + return true; + } else { + // Transforming didn't eliminate the tie and didn't lead to an + // improvement. Clean up the unfolded instructions and keep the + // original. + DEBUG(dbgs() << "2addr: ABANDONING UNFOLD\n"); + NewMIs[0]->eraseFromParent(); + NewMIs[1]->eraseFromParent(); + } + } + } + } + + return false; +} + /// runOnMachineFunction - Reduce two-address instructions to two operands. /// bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) { - DEBUG(errs() << "Machine Function\n"); + DEBUG(dbgs() << "Machine Function\n"); const TargetMachine &TM = MF.getTarget(); MRI = &MF.getRegInfo(); TII = TM.getInstrInfo(); TRI = TM.getRegisterInfo(); + InstrItins = TM.getInstrItineraryData(); LV = getAnalysisIfAvailable(); + AA = &getAnalysis(); + OptLevel = TM.getOptLevel(); bool MadeChange = false; - DEBUG(errs() << "********** REWRITING TWO-ADDR INSTRS **********\n"); - DEBUG(errs() << "********** Function: " + DEBUG(dbgs() << "********** REWRITING TWO-ADDR INSTRS **********\n"); + DEBUG(dbgs() << "********** Function: " << MF.getFunction()->getName() << '\n'); + // This pass takes the function out of SSA form. + MRI->leaveSSA(); + // ReMatRegs - Keep track of the registers whose def's are remat'ed. - BitVector ReMatRegs; - ReMatRegs.resize(MRI->getLastVirtReg()+1); + BitVector ReMatRegs(MRI->getNumVirtRegs()); + + typedef DenseMap, 4> > + TiedOperandMap; + TiedOperandMap TiedOperands(4); SmallPtrSet Processed; for (MachineFunction::iterator mbbi = MF.begin(), mbbe = MF.end(); @@ -766,201 +1416,125 @@ bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) { Processed.clear(); for (MachineBasicBlock::iterator mi = mbbi->begin(), me = mbbi->end(); mi != me; ) { - MachineBasicBlock::iterator nmi = next(mi); - const TargetInstrDesc &TID = mi->getDesc(); + MachineBasicBlock::iterator nmi = llvm::next(mi); + if (mi->isDebugValue()) { + mi = nmi; + continue; + } + + // Remember REG_SEQUENCE instructions, we'll deal with them later. + if (mi->isRegSequence()) + RegSequences.push_back(&*mi); + + const MCInstrDesc &MCID = mi->getDesc(); bool FirstTied = true; DistanceMap.insert(std::make_pair(mi, ++Dist)); ProcessCopy(&*mi, &*mbbi, Processed); - unsigned NumOps = (mi->getOpcode() == TargetInstrInfo::INLINEASM) - ? mi->getNumOperands() : TID.getNumOperands(); - for (unsigned si = 0; si < NumOps; ++si) { - unsigned ti = 0; - if (!mi->isRegTiedToDefOperand(si, &ti)) + // First scan through all the tied register uses in this instruction + // and record a list of pairs of tied operands for each register. + unsigned NumOps = mi->isInlineAsm() + ? mi->getNumOperands() : MCID.getNumOperands(); + for (unsigned SrcIdx = 0; SrcIdx < NumOps; ++SrcIdx) { + unsigned DstIdx = 0; + if (!mi->isRegTiedToDefOperand(SrcIdx, &DstIdx)) continue; if (FirstTied) { + FirstTied = false; ++NumTwoAddressInstrs; - DEBUG(errs() << '\t' << *mi); + DEBUG(dbgs() << '\t' << *mi); } - FirstTied = false; + assert(mi->getOperand(SrcIdx).isReg() && + mi->getOperand(SrcIdx).getReg() && + mi->getOperand(SrcIdx).isUse() && + "two address instruction invalid"); - assert(mi->getOperand(si).isReg() && mi->getOperand(si).getReg() && - mi->getOperand(si).isUse() && "two address instruction invalid"); + unsigned regB = mi->getOperand(SrcIdx).getReg(); + TiedOperands[regB].push_back(std::make_pair(SrcIdx, DstIdx)); + } + + // Now iterate over the information collected above. + for (TiedOperandMap::iterator OI = TiedOperands.begin(), + OE = TiedOperands.end(); OI != OE; ++OI) { + SmallVector, 4> &TiedPairs = OI->second; + + // If the instruction has a single pair of tied operands, try some + // transformations that may either eliminate the tied operands or + // improve the opportunities for coalescing away the register copy. + if (TiedOperands.size() == 1 && TiedPairs.size() == 1) { + unsigned SrcIdx = TiedPairs[0].first; + unsigned DstIdx = TiedPairs[0].second; + + // If the registers are already equal, nothing needs to be done. + if (mi->getOperand(SrcIdx).getReg() == + mi->getOperand(DstIdx).getReg()) + break; // Done with this instruction. + + if (TryInstructionTransform(mi, nmi, mbbi, SrcIdx, DstIdx, Dist, + Processed)) + break; // The tied operands have been eliminated. + } - // If the two operands are the same we just remove the use - // and mark the def as def&use, otherwise we have to insert a copy. - if (mi->getOperand(ti).getReg() != mi->getOperand(si).getReg()) { - // Rewrite: - // a = b op c - // to: - // a = b - // a = a op c - unsigned regA = mi->getOperand(ti).getReg(); - unsigned regB = mi->getOperand(si).getReg(); - unsigned regASubIdx = mi->getOperand(ti).getSubReg(); + bool IsEarlyClobber = false; + bool RemovedKillFlag = false; + bool AllUsesCopied = true; + unsigned LastCopiedReg = 0; + unsigned regB = OI->first; + for (unsigned tpi = 0, tpe = TiedPairs.size(); tpi != tpe; ++tpi) { + unsigned SrcIdx = TiedPairs[tpi].first; + unsigned DstIdx = TiedPairs[tpi].second; + + const MachineOperand &DstMO = mi->getOperand(DstIdx); + unsigned regA = DstMO.getReg(); + IsEarlyClobber |= DstMO.isEarlyClobber(); + + // Grab regB from the instruction because it may have changed if the + // instruction was commuted. + regB = mi->getOperand(SrcIdx).getReg(); + + if (regA == regB) { + // The register is tied to multiple destinations (or else we would + // not have continued this far), but this use of the register + // already matches the tied destination. Leave it. + AllUsesCopied = false; + continue; + } + LastCopiedReg = regA; assert(TargetRegisterInfo::isVirtualRegister(regB) && "cannot make instruction into two-address form"); #ifndef NDEBUG - // First, verify that we don't have a use of a in the instruction (a = - // b + a for example) because our transformation will not work. This - // should never occur because we are in SSA form. + // First, verify that we don't have a use of "a" in the instruction + // (a = b + a for example) because our transformation will not + // work. This should never occur because we are in SSA form. for (unsigned i = 0; i != mi->getNumOperands(); ++i) - assert(i == ti || + assert(i == DstIdx || !mi->getOperand(i).isReg() || mi->getOperand(i).getReg() != regA); #endif - // If this instruction is not the killing user of B, see if we can - // rearrange the code to make it so. Making it the killing user will - // allow us to coalesce A and B together, eliminating the copy we are - // about to insert. - if (!isKilled(*mi, regB, MRI, TII)) { - // If regA is dead and the instruction can be deleted, just delete - // it so it doesn't clobber regB. - SmallVector Kills; - if (mi->getOperand(ti).isDead() && - isSafeToDelete(mi, regB, TII, Kills)) { - SmallVector - ,MachineInstr*>, 4> NewKills; - bool ReallySafe = true; - // If this instruction kills some virtual registers, we need - // update the kill information. If it's not possible to do so, - // then bail out. - while (!Kills.empty()) { - unsigned Kill = Kills.back(); - Kills.pop_back(); - if (TargetRegisterInfo::isPhysicalRegister(Kill)) { - ReallySafe = false; - break; - } - MachineInstr *LastKill = FindLastUseInMBB(Kill, &*mbbi, Dist); - if (LastKill) { - bool isModRef = LastKill->modifiesRegister(Kill); - NewKills.push_back(std::make_pair(std::make_pair(Kill,isModRef), - LastKill)); - } else { - ReallySafe = false; - break; - } - } - - if (ReallySafe) { - if (LV) { - while (!NewKills.empty()) { - MachineInstr *NewKill = NewKills.back().second; - unsigned Kill = NewKills.back().first.first; - bool isDead = NewKills.back().first.second; - NewKills.pop_back(); - if (LV->removeVirtualRegisterKilled(Kill, mi)) { - if (isDead) - LV->addVirtualRegisterDead(Kill, NewKill); - else - LV->addVirtualRegisterKilled(Kill, NewKill); - } - } - } - - // We're really going to nuke the old inst. If regB was marked - // as a kill we need to update its Kills list. - if (mi->getOperand(si).isKill()) - LV->removeVirtualRegisterKilled(regB, mi); - - mbbi->erase(mi); // Nuke the old inst. - mi = nmi; - ++NumDeletes; - break; // Done with this instruction. - } - } - - // If this instruction is commutative, check to see if C dies. If - // so, swap the B and C operands. This makes the live ranges of A - // and C joinable. - // FIXME: This code also works for A := B op C instructions. - unsigned SrcOp1, SrcOp2; - if (TID.isCommutable() && mi->getNumOperands() >= 3 && - TII->findCommutedOpIndices(mi, SrcOp1, SrcOp2)) { - unsigned regC = 0; - if (si == SrcOp1) - regC = mi->getOperand(SrcOp2).getReg(); - else if (si == SrcOp2) - regC = mi->getOperand(SrcOp1).getReg(); - if (isKilled(*mi, regC, MRI, TII)) { - if (CommuteInstruction(mi, mbbi, regB, regC, Dist)) { - ++NumCommuted; - regB = regC; - goto InstructionRearranged; - } - } - } - - // If this instruction is potentially convertible to a true - // three-address instruction, - if (TID.isConvertibleTo3Addr()) { - // FIXME: This assumes there are no more operands which are tied - // to another register. -#ifndef NDEBUG - for (unsigned i = si + 1, e = TID.getNumOperands(); i < e; ++i) - assert(TID.getOperandConstraint(i, TOI::TIED_TO) == -1); -#endif - - if (ConvertInstTo3Addr(mi, nmi, mbbi, regB, Dist)) { - ++NumConvertedTo3Addr; - break; // Done with this instruction. - } - } - } - - // If it's profitable to commute the instruction, do so. - unsigned SrcOp1, SrcOp2; - if (TID.isCommutable() && mi->getNumOperands() >= 3 && - TII->findCommutedOpIndices(mi, SrcOp1, SrcOp2)) { - unsigned regC = 0; - if (si == SrcOp1) - regC = mi->getOperand(SrcOp2).getReg(); - else if (si == SrcOp2) - regC = mi->getOperand(SrcOp1).getReg(); - - if (regC && isProfitableToCommute(regB, regC, mi, mbbi, Dist)) - if (CommuteInstruction(mi, mbbi, regB, regC, Dist)) { - ++NumAggrCommuted; - ++NumCommuted; - regB = regC; - goto InstructionRearranged; - } - } - - // If it's profitable to convert the 2-address instruction to a - // 3-address one, do so. - if (TID.isConvertibleTo3Addr() && isProfitableToConv3Addr(regA)) { - if (ConvertInstTo3Addr(mi, nmi, mbbi, regB, Dist)) { - ++NumConvertedTo3Addr; - break; // Done with this instruction. - } - } - - InstructionRearranged: - const TargetRegisterClass* rc = MRI->getRegClass(regB); + // Emit a copy or rematerialize the definition. + const TargetRegisterClass *rc = MRI->getRegClass(regB); MachineInstr *DefMI = MRI->getVRegDef(regB); // If it's safe and profitable, remat the definition instead of // copying it. if (DefMI && - DefMI->getDesc().isAsCheapAsAMove() && - DefMI->isSafeToReMat(TII, regB) && + DefMI->isAsCheapAsAMove() && + DefMI->isSafeToReMat(TII, AA, regB) && isProfitableToReMat(regB, rc, mi, DefMI, mbbi, Dist)){ - DEBUG(errs() << "2addr: REMATTING : " << *DefMI << "\n"); - TII->reMaterialize(*mbbi, mi, regA, regASubIdx, DefMI); - ReMatRegs.set(regB); + DEBUG(dbgs() << "2addr: REMATTING : " << *DefMI << "\n"); + unsigned regASubIdx = mi->getOperand(DstIdx).getSubReg(); + TII->reMaterialize(*mbbi, mi, regA, regASubIdx, DefMI, *TRI); + ReMatRegs.set(TargetRegisterInfo::virtReg2Index(regB)); ++NumReMats; } else { - bool Emitted = TII->copyRegToReg(*mbbi, mi, regA, regB, rc, rc); - (void)Emitted; - assert(Emitted && "Unable to issue a copy instruction!\n"); + BuildMI(*mbbi, mi, mi->getDebugLoc(), TII->get(TargetOpcode::COPY), + regA).addReg(regB); } MachineBasicBlock::iterator prevMI = prior(mi); @@ -968,45 +1542,400 @@ bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &MF) { DistanceMap.insert(std::make_pair(prevMI, Dist)); DistanceMap[mi] = ++Dist; - // Update live variables for regB. - if (LV) { - if (LV->removeVirtualRegisterKilled(regB, mi)) - LV->addVirtualRegisterKilled(regB, prevMI); + DEBUG(dbgs() << "\t\tprepend:\t" << *prevMI); - if (LV->removeVirtualRegisterDead(regB, mi)) - LV->addVirtualRegisterDead(regB, prevMI); + MachineOperand &MO = mi->getOperand(SrcIdx); + assert(MO.isReg() && MO.getReg() == regB && MO.isUse() && + "inconsistent operand info for 2-reg pass"); + if (MO.isKill()) { + MO.setIsKill(false); + RemovedKillFlag = true; } + MO.setReg(regA); + } - DEBUG(errs() << "\t\tprepend:\t" << *prevMI); - - // Replace all occurences of regB with regA. + if (AllUsesCopied) { + if (!IsEarlyClobber) { + // Replace other (un-tied) uses of regB with LastCopiedReg. + for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) { + MachineOperand &MO = mi->getOperand(i); + if (MO.isReg() && MO.getReg() == regB && MO.isUse()) { + if (MO.isKill()) { + MO.setIsKill(false); + RemovedKillFlag = true; + } + MO.setReg(LastCopiedReg); + } + } + } + + // Update live variables for regB. + if (RemovedKillFlag && LV && LV->getVarInfo(regB).removeKill(mi)) + LV->addVirtualRegisterKilled(regB, prior(mi)); + + } else if (RemovedKillFlag) { + // Some tied uses of regB matched their destination registers, so + // regB is still used in this instruction, but a kill flag was + // removed from a different tied use of regB, so now we need to add + // a kill flag to one of the remaining uses of regB. for (unsigned i = 0, e = mi->getNumOperands(); i != e; ++i) { - if (mi->getOperand(i).isReg() && - mi->getOperand(i).getReg() == regB) - mi->getOperand(i).setReg(regA); + MachineOperand &MO = mi->getOperand(i); + if (MO.isReg() && MO.getReg() == regB && MO.isUse()) { + MO.setIsKill(true); + break; + } } + } - assert(mi->getOperand(ti).isDef() && mi->getOperand(si).isUse()); - mi->getOperand(ti).setReg(mi->getOperand(si).getReg()); - MadeChange = true; + // Schedule the source copy / remat inserted to form two-address + // instruction. FIXME: Does it matter the distance map may not be + // accurate after it's scheduled? + TII->scheduleTwoAddrSource(prior(mi), mi, *TRI); - DEBUG(errs() << "\t\trewrite to:\t" << *mi); - } + MadeChange = true; + + DEBUG(dbgs() << "\t\trewrite to:\t" << *mi); } + // Rewrite INSERT_SUBREG as COPY now that we no longer need SSA form. + if (mi->isInsertSubreg()) { + // From %reg = INSERT_SUBREG %reg, %subreg, subidx + // To %reg:subidx = COPY %subreg + unsigned SubIdx = mi->getOperand(3).getImm(); + mi->RemoveOperand(3); + assert(mi->getOperand(0).getSubReg() == 0 && "Unexpected subreg idx"); + mi->getOperand(0).setSubReg(SubIdx); + mi->RemoveOperand(1); + mi->setDesc(TII->get(TargetOpcode::COPY)); + DEBUG(dbgs() << "\t\tconvert to:\t" << *mi); + } + + // Clear TiedOperands here instead of at the top of the loop + // since most instructions do not have tied operands. + TiedOperands.clear(); mi = nmi; } } // Some remat'ed instructions are dead. - int VReg = ReMatRegs.find_first(); - while (VReg != -1) { - if (MRI->use_empty(VReg)) { + for (int i = ReMatRegs.find_first(); i != -1; i = ReMatRegs.find_next(i)) { + unsigned VReg = TargetRegisterInfo::index2VirtReg(i); + if (MRI->use_nodbg_empty(VReg)) { MachineInstr *DefMI = MRI->getVRegDef(VReg); DefMI->eraseFromParent(); } - VReg = ReMatRegs.find_next(VReg); } + // Eliminate REG_SEQUENCE instructions. Their whole purpose was to preseve + // SSA form. It's now safe to de-SSA. + MadeChange |= EliminateRegSequences(); + return MadeChange; } + +static void UpdateRegSequenceSrcs(unsigned SrcReg, + unsigned DstReg, unsigned SubIdx, + MachineRegisterInfo *MRI, + const TargetRegisterInfo &TRI) { + for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(SrcReg), + RE = MRI->reg_end(); RI != RE; ) { + MachineOperand &MO = RI.getOperand(); + ++RI; + MO.substVirtReg(DstReg, SubIdx, TRI); + } +} + +// Find the first def of Reg, assuming they are all in the same basic block. +static MachineInstr *findFirstDef(unsigned Reg, MachineRegisterInfo *MRI) { + SmallPtrSet Defs; + MachineInstr *First = 0; + for (MachineRegisterInfo::def_iterator RI = MRI->def_begin(Reg); + MachineInstr *MI = RI.skipInstruction(); Defs.insert(MI)) + First = MI; + if (!First) + return 0; + + MachineBasicBlock *MBB = First->getParent(); + MachineBasicBlock::iterator A = First, B = First; + bool Moving; + do { + Moving = false; + if (A != MBB->begin()) { + Moving = true; + --A; + if (Defs.erase(A)) First = A; + } + if (B != MBB->end()) { + Defs.erase(B); + ++B; + Moving = true; + } + } while (Moving && !Defs.empty()); + assert(Defs.empty() && "Instructions outside basic block!"); + return First; +} + +/// CoalesceExtSubRegs - If a number of sources of the REG_SEQUENCE are +/// EXTRACT_SUBREG from the same register and to the same virtual register +/// with different sub-register indices, attempt to combine the +/// EXTRACT_SUBREGs and pre-coalesce them. e.g. +/// %reg1026 = VLDMQ %reg1025, 260, pred:14, pred:%reg0 +/// %reg1029:6 = EXTRACT_SUBREG %reg1026, 6 +/// %reg1029:5 = EXTRACT_SUBREG %reg1026, 5 +/// Since D subregs 5, 6 can combine to a Q register, we can coalesce +/// reg1026 to reg1029. +void +TwoAddressInstructionPass::CoalesceExtSubRegs(SmallVector &Srcs, + unsigned DstReg) { + SmallSet Seen; + for (unsigned i = 0, e = Srcs.size(); i != e; ++i) { + unsigned SrcReg = Srcs[i]; + if (!Seen.insert(SrcReg)) + continue; + + // Check that the instructions are all in the same basic block. + MachineInstr *SrcDefMI = MRI->getVRegDef(SrcReg); + MachineInstr *DstDefMI = MRI->getVRegDef(DstReg); + if (SrcDefMI->getParent() != DstDefMI->getParent()) + continue; + + // If there are no other uses than copies which feed into + // the reg_sequence, then we might be able to coalesce them. + bool CanCoalesce = true; + SmallVector SrcSubIndices, DstSubIndices; + for (MachineRegisterInfo::use_nodbg_iterator + UI = MRI->use_nodbg_begin(SrcReg), + UE = MRI->use_nodbg_end(); UI != UE; ++UI) { + MachineInstr *UseMI = &*UI; + if (!UseMI->isCopy() || UseMI->getOperand(0).getReg() != DstReg) { + CanCoalesce = false; + break; + } + SrcSubIndices.push_back(UseMI->getOperand(1).getSubReg()); + DstSubIndices.push_back(UseMI->getOperand(0).getSubReg()); + } + + if (!CanCoalesce || SrcSubIndices.size() < 2) + continue; + + // Check that the source subregisters can be combined. + std::sort(SrcSubIndices.begin(), SrcSubIndices.end()); + unsigned NewSrcSubIdx = 0; + if (!TRI->canCombineSubRegIndices(MRI->getRegClass(SrcReg), SrcSubIndices, + NewSrcSubIdx)) + continue; + + // Check that the destination subregisters can also be combined. + std::sort(DstSubIndices.begin(), DstSubIndices.end()); + unsigned NewDstSubIdx = 0; + if (!TRI->canCombineSubRegIndices(MRI->getRegClass(DstReg), DstSubIndices, + NewDstSubIdx)) + continue; + + // If neither source nor destination can be combined to the full register, + // just give up. This could be improved if it ever matters. + if (NewSrcSubIdx != 0 && NewDstSubIdx != 0) + continue; + + // Now that we know that all the uses are extract_subregs and that those + // subregs can somehow be combined, scan all the extract_subregs again to + // make sure the subregs are in the right order and can be composed. + MachineInstr *SomeMI = 0; + CanCoalesce = true; + for (MachineRegisterInfo::use_nodbg_iterator + UI = MRI->use_nodbg_begin(SrcReg), + UE = MRI->use_nodbg_end(); UI != UE; ++UI) { + MachineInstr *UseMI = &*UI; + assert(UseMI->isCopy()); + unsigned DstSubIdx = UseMI->getOperand(0).getSubReg(); + unsigned SrcSubIdx = UseMI->getOperand(1).getSubReg(); + assert(DstSubIdx != 0 && "missing subreg from RegSequence elimination"); + if ((NewDstSubIdx == 0 && + TRI->composeSubRegIndices(NewSrcSubIdx, DstSubIdx) != SrcSubIdx) || + (NewSrcSubIdx == 0 && + TRI->composeSubRegIndices(NewDstSubIdx, SrcSubIdx) != DstSubIdx)) { + CanCoalesce = false; + break; + } + // Keep track of one of the uses. Preferably the first one which has a + // flag. + if (!SomeMI || UseMI->getOperand(0).isUndef()) + SomeMI = UseMI; + } + if (!CanCoalesce) + continue; + + // Insert a copy to replace the original. + MachineInstr *CopyMI = BuildMI(*SomeMI->getParent(), SomeMI, + SomeMI->getDebugLoc(), + TII->get(TargetOpcode::COPY)) + .addReg(DstReg, RegState::Define | + getUndefRegState(SomeMI->getOperand(0).isUndef()), + NewDstSubIdx) + .addReg(SrcReg, 0, NewSrcSubIdx); + + // Remove all the old extract instructions. + for (MachineRegisterInfo::use_nodbg_iterator + UI = MRI->use_nodbg_begin(SrcReg), + UE = MRI->use_nodbg_end(); UI != UE; ) { + MachineInstr *UseMI = &*UI; + ++UI; + if (UseMI == CopyMI) + continue; + assert(UseMI->isCopy()); + // Move any kills to the new copy or extract instruction. + if (UseMI->getOperand(1).isKill()) { + CopyMI->getOperand(1).setIsKill(); + if (LV) + // Update live variables + LV->replaceKillInstruction(SrcReg, UseMI, &*CopyMI); + } + UseMI->eraseFromParent(); + } + } +} + +static bool HasOtherRegSequenceUses(unsigned Reg, MachineInstr *RegSeq, + MachineRegisterInfo *MRI) { + for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg), + UE = MRI->use_end(); UI != UE; ++UI) { + MachineInstr *UseMI = &*UI; + if (UseMI != RegSeq && UseMI->isRegSequence()) + return true; + } + return false; +} + +/// EliminateRegSequences - Eliminate REG_SEQUENCE instructions as part +/// of the de-ssa process. This replaces sources of REG_SEQUENCE as +/// sub-register references of the register defined by REG_SEQUENCE. e.g. +/// +/// %reg1029, %reg1030 = VLD1q16 %reg1024, ... +/// %reg1031 = REG_SEQUENCE %reg1029, 5, %reg1030, 6 +/// => +/// %reg1031:5, %reg1031:6 = VLD1q16 %reg1024, ... +bool TwoAddressInstructionPass::EliminateRegSequences() { + if (RegSequences.empty()) + return false; + + for (unsigned i = 0, e = RegSequences.size(); i != e; ++i) { + MachineInstr *MI = RegSequences[i]; + unsigned DstReg = MI->getOperand(0).getReg(); + if (MI->getOperand(0).getSubReg() || + TargetRegisterInfo::isPhysicalRegister(DstReg) || + !(MI->getNumOperands() & 1)) { + DEBUG(dbgs() << "Illegal REG_SEQUENCE instruction:" << *MI); + llvm_unreachable(0); + } + + bool IsImpDef = true; + SmallVector RealSrcs; + SmallSet Seen; + for (unsigned i = 1, e = MI->getNumOperands(); i < e; i += 2) { + unsigned SrcReg = MI->getOperand(i).getReg(); + unsigned SubIdx = MI->getOperand(i+1).getImm(); + // DefMI of NULL means the value does not have a vreg in this block + // i.e., its a physical register or a subreg. + // In either case we force a copy to be generated. + MachineInstr *DefMI = NULL; + if (!MI->getOperand(i).getSubReg() && + !TargetRegisterInfo::isPhysicalRegister(SrcReg)) { + DefMI = MRI->getVRegDef(SrcReg); + } + + if (DefMI && DefMI->isImplicitDef()) { + DefMI->eraseFromParent(); + continue; + } + IsImpDef = false; + + // Remember COPY sources. These might be candidate for coalescing. + if (DefMI && DefMI->isCopy() && DefMI->getOperand(1).getSubReg()) + RealSrcs.push_back(DefMI->getOperand(1).getReg()); + + bool isKill = MI->getOperand(i).isKill(); + if (!DefMI || !Seen.insert(SrcReg) || + MI->getParent() != DefMI->getParent() || + !isKill || HasOtherRegSequenceUses(SrcReg, MI, MRI) || + !TRI->getMatchingSuperRegClass(MRI->getRegClass(DstReg), + MRI->getRegClass(SrcReg), SubIdx)) { + // REG_SEQUENCE cannot have duplicated operands, add a copy. + // Also add an copy if the source is live-in the block. We don't want + // to end up with a partial-redef of a livein, e.g. + // BB0: + // reg1051:10 = + // ... + // BB1: + // ... = reg1051:10 + // BB2: + // reg1051:9 = + // LiveIntervalAnalysis won't like it. + // + // If the REG_SEQUENCE doesn't kill its source, keeping live variables + // correctly up to date becomes very difficult. Insert a copy. + + // Defer any kill flag to the last operand using SrcReg. Otherwise, we + // might insert a COPY that uses SrcReg after is was killed. + if (isKill) + for (unsigned j = i + 2; j < e; j += 2) + if (MI->getOperand(j).getReg() == SrcReg) { + MI->getOperand(j).setIsKill(); + isKill = false; + break; + } + + MachineBasicBlock::iterator InsertLoc = MI; + MachineInstr *CopyMI = BuildMI(*MI->getParent(), InsertLoc, + MI->getDebugLoc(), TII->get(TargetOpcode::COPY)) + .addReg(DstReg, RegState::Define, SubIdx) + .addReg(SrcReg, getKillRegState(isKill)); + MI->getOperand(i).setReg(0); + if (LV && isKill && !TargetRegisterInfo::isPhysicalRegister(SrcReg)) + LV->replaceKillInstruction(SrcReg, MI, CopyMI); + DEBUG(dbgs() << "Inserted: " << *CopyMI); + } + } + + for (unsigned i = 1, e = MI->getNumOperands(); i < e; i += 2) { + unsigned SrcReg = MI->getOperand(i).getReg(); + if (!SrcReg) continue; + unsigned SubIdx = MI->getOperand(i+1).getImm(); + UpdateRegSequenceSrcs(SrcReg, DstReg, SubIdx, MRI, *TRI); + } + + // Set flags on the first DstReg def in the basic block. + // It marks the beginning of the live range. All the other defs are + // read-modify-write. + if (MachineInstr *Def = findFirstDef(DstReg, MRI)) { + for (unsigned i = 0, e = Def->getNumOperands(); i != e; ++i) { + MachineOperand &MO = Def->getOperand(i); + if (MO.isReg() && MO.isDef() && MO.getReg() == DstReg) + MO.setIsUndef(); + } + // Make sure there is a full non-subreg imp-def operand on the + // instruction. This shouldn't be necessary, but it seems that at least + // RAFast requires it. + Def->addRegisterDefined(DstReg, TRI); + DEBUG(dbgs() << "First def: " << *Def); + } + + if (IsImpDef) { + DEBUG(dbgs() << "Turned: " << *MI << " into an IMPLICIT_DEF"); + MI->setDesc(TII->get(TargetOpcode::IMPLICIT_DEF)); + for (int j = MI->getNumOperands() - 1, ee = 0; j > ee; --j) + MI->RemoveOperand(j); + } else { + DEBUG(dbgs() << "Eliminated: " << *MI); + MI->eraseFromParent(); + } + + // Try coalescing some EXTRACT_SUBREG instructions. This can create + // INSERT_SUBREG instructions that must have flags added by + // LiveIntervalAnalysis, so only run it when LiveVariables is available. + if (LV) + CoalesceExtSubRegs(RealSrcs, DstReg); + } + + RegSequences.clear(); + return true; +}