X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FTwoAddressInstructionPass.cpp;h=c6bae2434586935f4ca959fc2d15ccd9fc932052;hb=71afbb96dc077e1b12b37baa311a67d8ab094c1c;hp=300be0e40bad9583ea4953746c149b0156e71c55;hpb=4ba844388c586ee40871a52dc9d6eab883fde1b7;p=oota-llvm.git diff --git a/lib/CodeGen/TwoAddressInstructionPass.cpp b/lib/CodeGen/TwoAddressInstructionPass.cpp index 300be0e40ba..c6bae243458 100644 --- a/lib/CodeGen/TwoAddressInstructionPass.cpp +++ b/lib/CodeGen/TwoAddressInstructionPass.cpp @@ -27,7 +27,6 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "twoaddrinstr" #include "llvm/CodeGen/Passes.h" #include "llvm/ADT/BitVector.h" #include "llvm/ADT/DenseMap.h" @@ -46,11 +45,15 @@ #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Target/TargetSubtargetInfo.h" using namespace llvm; +#define DEBUG_TYPE "twoaddrinstr" + STATISTIC(NumTwoAddressInstrs, "Number of two-address instructions"); STATISTIC(NumCommuted , "Number of instructions commuted to coalesce"); STATISTIC(NumAggrCommuted , "Number of instructions aggressively commuted"); @@ -80,33 +83,34 @@ class TwoAddressInstructionPass : public MachineFunctionPass { // The current basic block being processed. MachineBasicBlock *MBB; - // DistanceMap - Keep track the distance of a MI from the start of the - // current basic block. + // Keep track the distance of a MI from the start of the current basic block. DenseMap DistanceMap; // Set of already processed instructions in the current block. SmallPtrSet Processed; - // SrcRegMap - A map from virtual registers to physical registers which are - // likely targets to be coalesced to due to copies from physical registers to - // virtual registers. e.g. v1024 = move r0. + // A map from virtual registers to physical registers which are likely targets + // to be coalesced to due to copies from physical registers to virtual + // registers. e.g. v1024 = move r0. DenseMap SrcRegMap; - // DstRegMap - A map from virtual registers to physical registers which are - // likely targets to be coalesced to due to copies to physical registers from - // virtual registers. e.g. r1 = move v1024. + // A map from virtual registers to physical registers which are likely targets + // to be coalesced to due to copies to physical registers from virtual + // registers. e.g. r1 = move v1024. DenseMap DstRegMap; bool sink3AddrInstruction(MachineInstr *MI, unsigned Reg, MachineBasicBlock::iterator OldPos); + bool isRevCopyChain(unsigned FromReg, unsigned ToReg, int Maxlen); + bool noUseAfterLastDef(unsigned Reg, unsigned Dist, unsigned &LastDef); bool isProfitableToCommute(unsigned regA, unsigned regB, unsigned regC, MachineInstr *MI, unsigned Dist); - bool commuteInstruction(MachineBasicBlock::iterator &mi, - unsigned RegB, unsigned RegC, unsigned Dist); + bool commuteInstruction(MachineInstr *MI, + unsigned RegBIdx, unsigned RegCIdx, unsigned Dist); bool isProfitableToConv3Addr(unsigned RegA, unsigned RegB); @@ -128,6 +132,11 @@ class TwoAddressInstructionPass : public MachineFunctionPass { unsigned SrcIdx, unsigned DstIdx, unsigned Dist, bool shouldOnlyCommute); + bool tryInstructionCommute(MachineInstr *MI, + unsigned DstOpIdx, + unsigned BaseOpIdx, + bool BaseOpKilled, + unsigned Dist); void scanUses(unsigned DstReg); void processCopy(MachineInstr *MI); @@ -146,7 +155,7 @@ public: void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesCFG(); - AU.addRequired(); + AU.addRequired(); AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); @@ -155,7 +164,7 @@ public: MachineFunctionPass::getAnalysisUsage(AU); } - /// runOnMachineFunction - Pass entry point. + /// Pass entry point. bool runOnMachineFunction(MachineFunction&) override; }; } // end anonymous namespace @@ -163,7 +172,7 @@ public: char TwoAddressInstructionPass::ID = 0; INITIALIZE_PASS_BEGIN(TwoAddressInstructionPass, "twoaddressinstruction", "Two-Address instruction pass", false, false) -INITIALIZE_AG_DEPENDENCY(AliasAnalysis) +INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) INITIALIZE_PASS_END(TwoAddressInstructionPass, "twoaddressinstruction", "Two-Address instruction pass", false, false) @@ -171,10 +180,9 @@ char &llvm::TwoAddressInstructionPassID = TwoAddressInstructionPass::ID; static bool isPlainlyKilled(MachineInstr *MI, unsigned Reg, LiveIntervals *LIS); -/// sink3AddrInstruction - A two-address instruction has been converted to a -/// three-address instruction to avoid clobbering a register. Try to sink it -/// past the instruction that would kill the above mentioned register to reduce -/// register pressure. +/// A two-address instruction has been converted to a three-address instruction +/// to avoid clobbering a register. Try to sink it past the instruction that +/// would kill the above mentioned register to reduce register pressure. bool TwoAddressInstructionPass:: sink3AddrInstruction(MachineInstr *MI, unsigned SavedReg, MachineBasicBlock::iterator OldPos) { @@ -184,14 +192,13 @@ sink3AddrInstruction(MachineInstr *MI, unsigned SavedReg, // Check if it's safe to move this instruction. bool SeenStore = true; // Be conservative. - if (!MI->isSafeToMove(TII, AA, SeenStore)) + if (!MI->isSafeToMove(AA, SeenStore)) return false; unsigned DefReg = 0; SmallSet UseRegs; - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - const MachineOperand &MO = MI->getOperand(i); + for (const MachineOperand &MO : MI->operands()) { if (!MO.isReg()) continue; unsigned MOReg = MO.getReg(); @@ -226,10 +233,7 @@ sink3AddrInstruction(MachineInstr *MI, unsigned SavedReg, KillMI = LIS->getInstructionFromIndex(I->end); } if (!KillMI) { - for (MachineRegisterInfo::use_nodbg_iterator - UI = MRI->use_nodbg_begin(SavedReg), - UE = MRI->use_nodbg_end(); UI != UE; ++UI) { - MachineOperand &UseMO = *UI; + for (MachineOperand &UseMO : MRI->use_nodbg_operands(SavedReg)) { if (!UseMO.isKill()) continue; KillMI = UseMO.getParent(); @@ -307,10 +311,48 @@ sink3AddrInstruction(MachineInstr *MI, unsigned SavedReg, return true; } -/// noUseAfterLastDef - Return true if there are no intervening uses between the -/// last instruction in the MBB that defines the specified register and the -/// two-address instruction which is being processed. It also returns the last -/// def location by reference +/// Return the MachineInstr* if it is the single def of the Reg in current BB. +static MachineInstr *getSingleDef(unsigned Reg, MachineBasicBlock *BB, + const MachineRegisterInfo *MRI) { + MachineInstr *Ret = nullptr; + for (MachineInstr &DefMI : MRI->def_instructions(Reg)) { + if (DefMI.getParent() != BB || DefMI.isDebugValue()) + continue; + if (!Ret) + Ret = &DefMI; + else if (Ret != &DefMI) + return nullptr; + } + return Ret; +} + +/// Check if there is a reversed copy chain from FromReg to ToReg: +/// %Tmp1 = copy %Tmp2; +/// %FromReg = copy %Tmp1; +/// %ToReg = add %FromReg ... +/// %Tmp2 = copy %ToReg; +/// MaxLen specifies the maximum length of the copy chain the func +/// can walk through. +bool TwoAddressInstructionPass::isRevCopyChain(unsigned FromReg, unsigned ToReg, + int Maxlen) { + unsigned TmpReg = FromReg; + for (int i = 0; i < Maxlen; i++) { + MachineInstr *Def = getSingleDef(TmpReg, MBB, MRI); + if (!Def || !Def->isCopy()) + return false; + + TmpReg = Def->getOperand(1).getReg(); + + if (TmpReg == ToReg) + return true; + } + return false; +} + +/// Return true if there are no intervening uses between the last instruction +/// in the MBB that defines the specified register and the two-address +/// instruction which is being processed. It also returns the last def location +/// by reference. bool TwoAddressInstructionPass::noUseAfterLastDef(unsigned Reg, unsigned Dist, unsigned &LastDef) { LastDef = 0; @@ -331,9 +373,9 @@ bool TwoAddressInstructionPass::noUseAfterLastDef(unsigned Reg, unsigned Dist, return !(LastUse > LastDef && LastUse < Dist); } -/// isCopyToReg - Return true if the specified MI is a copy instruction or -/// a extract_subreg instruction. It also returns the source and destination -/// registers and whether they are physical registers by reference. +/// Return true if the specified MI is a copy instruction or an extract_subreg +/// instruction. It also returns the source and destination registers and +/// whether they are physical registers by reference. static bool isCopyToReg(MachineInstr &MI, const TargetInstrInfo *TII, unsigned &SrcReg, unsigned &DstReg, bool &IsSrcPhys, bool &IsDstPhys) { @@ -353,8 +395,8 @@ static bool isCopyToReg(MachineInstr &MI, const TargetInstrInfo *TII, return true; } -/// isPLainlyKilled - Test if the given register value, which is used by the -// given instruction, is killed by the given instruction. +/// Test if the given register value, which is used by the +/// given instruction, is killed by the given instruction. static bool isPlainlyKilled(MachineInstr *MI, unsigned Reg, LiveIntervals *LIS) { if (LIS && TargetRegisterInfo::isVirtualRegister(Reg) && @@ -380,7 +422,7 @@ static bool isPlainlyKilled(MachineInstr *MI, unsigned Reg, return MI->killsRegister(Reg); } -/// isKilled - Test if the given register value, which is used by the given +/// Test if the given register value, which is used by the given /// instruction, is killed by the given instruction. This looks through /// coalescable copies to see if the original value is potentially not killed. /// @@ -428,8 +470,8 @@ 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. +/// 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) { for (unsigned i = 0, NumOps = MI.getNumOperands(); i != NumOps; ++i) { const MachineOperand &MO = MI.getOperand(i); @@ -444,8 +486,8 @@ static bool isTwoAddrUse(MachineInstr &MI, unsigned Reg, unsigned &DstReg) { return false; } -/// 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. +/// 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 MachineInstr *findOnlyInterestingUse(unsigned Reg, MachineBasicBlock *MBB, MachineRegisterInfo *MRI, @@ -472,8 +514,8 @@ MachineInstr *findOnlyInterestingUse(unsigned Reg, MachineBasicBlock *MBB, return nullptr; } -/// getMappedReg - Return the physical register the specified virtual register -/// might be mapped to. +/// Return the physical register the specified virtual register might be mapped +/// to. static unsigned getMappedReg(unsigned Reg, DenseMap &RegMap) { while (TargetRegisterInfo::isVirtualRegister(Reg)) { @@ -487,8 +529,7 @@ getMappedReg(unsigned Reg, DenseMap &RegMap) { return 0; } -/// regsAreCompatible - Return true if the two registers are equal or aliased. -/// +/// Return true if the two registers are equal or aliased. static bool regsAreCompatible(unsigned RegA, unsigned RegB, const TargetRegisterInfo *TRI) { if (RegA == RegB) @@ -499,8 +540,8 @@ regsAreCompatible(unsigned RegA, unsigned RegB, const TargetRegisterInfo *TRI) { } -/// isProfitableToCommute - Return true if it's potentially profitable to commute -/// the two-address instruction that's being processed. +/// Return true if it's potentially profitable to commute the two-address +/// instruction that's being processed. bool TwoAddressInstructionPass:: isProfitableToCommute(unsigned regA, unsigned regB, unsigned regC, @@ -543,10 +584,21 @@ isProfitableToCommute(unsigned regA, unsigned regB, unsigned regC, if (ToRegA) { unsigned FromRegB = getMappedReg(regB, SrcRegMap); unsigned FromRegC = getMappedReg(regC, SrcRegMap); - bool BComp = !FromRegB || regsAreCompatible(FromRegB, ToRegA, TRI); - bool CComp = !FromRegC || regsAreCompatible(FromRegC, ToRegA, TRI); - if (BComp != CComp) - return !BComp && CComp; + bool CompB = FromRegB && regsAreCompatible(FromRegB, ToRegA, TRI); + bool CompC = FromRegC && regsAreCompatible(FromRegC, ToRegA, TRI); + + // Compute if any of the following are true: + // -RegB is not tied to a register and RegC is compatible with RegA. + // -RegB is tied to the wrong physical register, but RegC is. + // -RegB is tied to the wrong physical register, and RegC isn't tied. + if ((!FromRegB && CompC) || (FromRegB && !CompB && (!FromRegC || CompC))) + return true; + // Don't compute if any of the following are true: + // -RegC is not tied to a register and RegB is compatible with RegA. + // -RegC is tied to the wrong physical register, but RegB is. + // -RegC is tied to the wrong physical register, and RegB isn't tied. + if ((!FromRegC && CompB) || (FromRegC && !CompC && (!FromRegB || CompB))) + return false; } // If there is a use of regC between its last def (could be livein) and this @@ -561,20 +613,41 @@ isProfitableToCommute(unsigned regA, unsigned regB, unsigned regC, if (!noUseAfterLastDef(regB, Dist, LastDefB)) return true; + // Look for situation like this: + // %reg101 = MOV %reg100 + // %reg102 = ... + // %reg103 = ADD %reg102, %reg101 + // ... = %reg103 ... + // %reg100 = MOV %reg103 + // If there is a reversed copy chain from reg101 to reg103, commute the ADD + // to eliminate an otherwise unavoidable copy. + // FIXME: + // We can extend the logic further: If an pair of operands in an insn has + // been merged, the insn could be regarded as a virtual copy, and the virtual + // copy could also be used to construct a copy chain. + // To more generally minimize register copies, ideally the logic of two addr + // instruction pass should be integrated with register allocation pass where + // interference graph is available. + if (isRevCopyChain(regC, regA, 3)) + return true; + + if (isRevCopyChain(regB, regA, 3)) + return false; + // Since there are no intervening uses for both registers, then commute // if the def of regC is closer. Its live interval is shorter. return LastDefB && LastDefC && LastDefC > LastDefB; } -/// commuteInstruction - Commute a two-address instruction and update the basic -/// block, distance map, and live variables if needed. Return true if it is -/// successful. -bool TwoAddressInstructionPass:: -commuteInstruction(MachineBasicBlock::iterator &mi, - unsigned RegB, unsigned RegC, unsigned Dist) { - MachineInstr *MI = mi; +/// Commute a two-address instruction and update the basic block, distance map, +/// and live variables if needed. Return true if it is successful. +bool TwoAddressInstructionPass::commuteInstruction(MachineInstr *MI, + unsigned RegBIdx, + unsigned RegCIdx, + unsigned Dist) { + unsigned RegC = MI->getOperand(RegCIdx).getReg(); DEBUG(dbgs() << "2addr: COMMUTING : " << *MI); - MachineInstr *NewMI = TII->commuteInstruction(MI); + MachineInstr *NewMI = TII->commuteInstruction(MI, false, RegBIdx, RegCIdx); if (NewMI == nullptr) { DEBUG(dbgs() << "2addr: COMMUTING FAILED!\n"); @@ -596,8 +669,8 @@ commuteInstruction(MachineBasicBlock::iterator &mi, return true; } -/// isProfitableToConv3Addr - Return true if it is profitable to convert the -/// given 2-address instruction to a 3-address one. +/// Return true if it is profitable to convert the given 2-address instruction +/// to a 3-address one. bool TwoAddressInstructionPass::isProfitableToConv3Addr(unsigned RegA,unsigned RegB){ // Look for situations like this: @@ -613,17 +686,18 @@ TwoAddressInstructionPass::isProfitableToConv3Addr(unsigned RegA,unsigned RegB){ return (ToRegA && !regsAreCompatible(FromRegB, ToRegA, TRI)); } -/// convertInstTo3Addr - Convert the specified two-address instruction into a -/// three address one. Return true if this transformation was successful. +/// Convert the specified two-address instruction into a three address one. +/// Return true if this transformation was successful. bool TwoAddressInstructionPass::convertInstTo3Addr(MachineBasicBlock::iterator &mi, MachineBasicBlock::iterator &nmi, unsigned RegA, unsigned RegB, unsigned Dist) { // FIXME: Why does convertToThreeAddress() need an iterator reference? - MachineFunction::iterator MFI = MBB; + MachineFunction::iterator MFI = MBB->getIterator(); MachineInstr *NewMI = TII->convertToThreeAddress(MFI, mi, LV); - assert(MBB == MFI && "convertToThreeAddress changed iterator reference"); + assert(MBB->getIterator() == MFI && + "convertToThreeAddress changed iterator reference"); if (!NewMI) return false; @@ -654,8 +728,8 @@ TwoAddressInstructionPass::convertInstTo3Addr(MachineBasicBlock::iterator &mi, return true; } -/// scanUses - Scan forward recursively for only uses, update maps if the use -/// is a copy or a two-address instruction. +/// Scan forward recursively for only uses, update maps if the use is a copy or +/// a two-address instruction. void TwoAddressInstructionPass::scanUses(unsigned DstReg) { SmallVector VirtRegPairs; @@ -665,7 +739,7 @@ TwoAddressInstructionPass::scanUses(unsigned DstReg) { unsigned Reg = DstReg; while (MachineInstr *UseMI = findOnlyInterestingUse(Reg, MBB, MRI, TII,IsCopy, NewReg, IsDstPhys)) { - if (IsCopy && !Processed.insert(UseMI)) + if (IsCopy && !Processed.insert(UseMI).second) break; DenseMap::iterator DI = DistanceMap.find(UseMI); @@ -701,8 +775,8 @@ TwoAddressInstructionPass::scanUses(unsigned DstReg) { } } -/// 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 +/// 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 /// point-to maps used to determine future optimizations. e.g. /// v1024 = mov r0 @@ -737,9 +811,9 @@ void TwoAddressInstructionPass::processCopy(MachineInstr *MI) { return; } -/// 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. +/// 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::iterator &mi, MachineBasicBlock::iterator &nmi, @@ -785,7 +859,7 @@ rescheduleMIBelowKill(MachineBasicBlock::iterator &mi, return false; bool SeenStore = true; - if (!MI->isSafeToMove(TII, AA, SeenStore)) + if (!MI->isSafeToMove(AA, SeenStore)) return false; if (TII->getInstrLatency(InstrItins, MI) > 1) @@ -795,8 +869,7 @@ rescheduleMIBelowKill(MachineBasicBlock::iterator &mi, SmallSet Uses; SmallSet Kills; SmallSet Defs; - for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { - const MachineOperand &MO = MI->getOperand(i); + for (const MachineOperand &MO : MI->operands()) { if (!MO.isReg()) continue; unsigned MOReg = MO.getReg(); @@ -838,8 +911,7 @@ rescheduleMIBelowKill(MachineBasicBlock::iterator &mi, 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); + for (const MachineOperand &MO : OtherMI->operands()) { if (!MO.isReg()) continue; unsigned MOReg = MO.getReg(); @@ -908,8 +980,8 @@ rescheduleMIBelowKill(MachineBasicBlock::iterator &mi, return true; } -/// isDefTooClose - Return true if the re-scheduling will put the given -/// instruction too close to the defs of its register dependencies. +/// 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) { for (MachineInstr &DefMI : MRI->def_instructions(Reg)) { @@ -928,10 +1000,9 @@ bool TwoAddressInstructionPass::isDefTooClose(unsigned Reg, unsigned Dist, 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. +/// 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::iterator &mi, MachineBasicBlock::iterator &nmi, @@ -972,15 +1043,14 @@ rescheduleKillAboveMI(MachineBasicBlock::iterator &mi, return false; bool SeenStore = true; - if (!KillMI->isSafeToMove(TII, AA, SeenStore)) + if (!KillMI->isSafeToMove(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); + for (const MachineOperand &MO : KillMI->operands()) { if (!MO.isReg()) continue; unsigned MOReg = MO.getReg(); @@ -1018,8 +1088,7 @@ rescheduleKillAboveMI(MachineBasicBlock::iterator &mi, // 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); + for (const MachineOperand &MO : OtherMI->operands()) { if (!MO.isReg()) continue; unsigned MOReg = MO.getReg(); @@ -1079,13 +1148,68 @@ rescheduleKillAboveMI(MachineBasicBlock::iterator &mi, 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 no copy needs to be -/// inserted to untie mi's operands (either because they were untied, or -/// because mi was rescheduled, and will be visited again later). If the -/// shouldOnlyCommute flag is true, only instruction commutation is attempted. +/// Tries to commute the operand 'BaseOpIdx' and some other operand in the +/// given machine instruction to improve opportunities for coalescing and +/// elimination of a register to register copy. +/// +/// 'DstOpIdx' specifies the index of MI def operand. +/// 'BaseOpKilled' specifies if the register associated with 'BaseOpIdx' +/// operand is killed by the given instruction. +/// The 'Dist' arguments provides the distance of MI from the start of the +/// current basic block and it is used to determine if it is profitable +/// to commute operands in the instruction. +/// +/// Returns true if the transformation happened. Otherwise, returns false. +bool TwoAddressInstructionPass::tryInstructionCommute(MachineInstr *MI, + unsigned DstOpIdx, + unsigned BaseOpIdx, + bool BaseOpKilled, + unsigned Dist) { + unsigned DstOpReg = MI->getOperand(DstOpIdx).getReg(); + unsigned BaseOpReg = MI->getOperand(BaseOpIdx).getReg(); + unsigned OpsNum = MI->getDesc().getNumOperands(); + unsigned OtherOpIdx = MI->getDesc().getNumDefs(); + for (; OtherOpIdx < OpsNum; OtherOpIdx++) { + // The call of findCommutedOpIndices below only checks if BaseOpIdx + // and OtherOpIdx are commutable, it does not really search for + // other commutable operands and does not change the values of passed + // variables. + if (OtherOpIdx == BaseOpIdx || + !TII->findCommutedOpIndices(MI, BaseOpIdx, OtherOpIdx)) + continue; + + unsigned OtherOpReg = MI->getOperand(OtherOpIdx).getReg(); + bool AggressiveCommute = false; + + // If OtherOp dies but BaseOp does not, swap the OtherOp and BaseOp + // operands. This makes the live ranges of DstOp and OtherOp joinable. + bool DoCommute = + !BaseOpKilled && isKilled(*MI, OtherOpReg, MRI, TII, LIS, false); + + if (!DoCommute && + isProfitableToCommute(DstOpReg, BaseOpReg, OtherOpReg, MI, Dist)) { + DoCommute = true; + AggressiveCommute = true; + } + + // If it's profitable to commute, try to do so. + if (DoCommute && commuteInstruction(MI, BaseOpIdx, OtherOpIdx, Dist)) { + ++NumCommuted; + if (AggressiveCommute) + ++NumAggrCommuted; + return true; + } + } + return false; +} + +/// 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 no copy needs to be inserted to untie mi's operands +/// (either because they were untied, or because mi was rescheduled, and will +/// be visited again later). If the shouldOnlyCommute flag is true, only +/// instruction commutation is attempted. bool TwoAddressInstructionPass:: tryInstructionTransform(MachineBasicBlock::iterator &mi, MachineBasicBlock::iterator &nmi, @@ -1105,50 +1229,36 @@ tryInstructionTransform(MachineBasicBlock::iterator &mi, if (TargetRegisterInfo::isVirtualRegister(regA)) scanUses(regA); - // 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, LIS, false)) - // 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(regA, regB, regC, &MI, Dist)) { - TryCommute = true; - AggressiveCommute = true; - } - } - } - - // If it's profitable to commute, try to do so. - if (TryCommute && commuteInstruction(mi, regB, regC, Dist)) { - ++NumCommuted; - if (AggressiveCommute) - ++NumAggrCommuted; + bool Commuted = tryInstructionCommute(&MI, DstIdx, SrcIdx, regBKilled, Dist); + + // If the instruction is convertible to 3 Addr, instead + // of returning try 3 Addr transformation aggresively and + // use this variable to check later. Because it might be better. + // For example, we can just use `leal (%rsi,%rdi), %eax` and `ret` + // instead of the following code. + // addl %esi, %edi + // movl %edi, %eax + // ret + if (Commuted && !MI.isConvertibleTo3Addr()) return false; - } if (shouldOnlyCommute) return false; // If there is one more use of regB later in the same MBB, consider // re-schedule this MI below it. - if (EnableRescheduling && rescheduleMIBelowKill(mi, nmi, regB)) { + if (!Commuted && EnableRescheduling && rescheduleMIBelowKill(mi, nmi, regB)) { ++NumReSchedDowns; return true; } + // If we commuted, regB may have changed so we should re-sample it to avoid + // confusing the three address conversion below. + if (Commuted) { + regB = MI.getOperand(SrcIdx).getReg(); + regBKilled = isKilled(MI, regB, MRI, TII, LIS, true); + } + if (MI.isConvertibleTo3Addr()) { // This instruction is potentially convertible to a true // three-address instruction. Check if it is profitable. @@ -1161,6 +1271,10 @@ tryInstructionTransform(MachineBasicBlock::iterator &mi, } } + // Return if it is commuted but 3 addr conversion is failed. + if (Commuted) + return false; + // 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 (EnableRescheduling && rescheduleKillAboveMI(mi, nmi, regB)) { @@ -1256,10 +1370,9 @@ tryInstructionTransform(MachineBasicBlock::iterator &mi, SmallVector OrigRegs; if (LIS) { - for (MachineInstr::const_mop_iterator MOI = MI.operands_begin(), - MOE = MI.operands_end(); MOI != MOE; ++MOI) { - if (MOI->isReg()) - OrigRegs.push_back(MOI->getReg()); + for (const MachineOperand &MO : MI.operands()) { + if (MO.isReg()) + OrigRegs.push_back(MO.getReg()); } } @@ -1444,12 +1557,10 @@ TwoAddressInstructionPass::processTiedPairs(MachineInstr *MI, SrcRegMap[RegA] = RegB; } - 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); + for (MachineOperand &MO : MI->operands()) { if (MO.isReg() && MO.getReg() == RegB && MO.getSubReg() == SubRegB && MO.isUse()) { if (MO.isKill()) { @@ -1486,8 +1597,7 @@ TwoAddressInstructionPass::processTiedPairs(MachineInstr *MI, // 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) { - MachineOperand &MO = MI->getOperand(i); + for (MachineOperand &MO : MI->operands()) { if (MO.isReg() && MO.getReg() == RegB && MO.isUse()) { MO.setIsKill(true); break; @@ -1496,18 +1606,17 @@ TwoAddressInstructionPass::processTiedPairs(MachineInstr *MI, } } -/// runOnMachineFunction - Reduce two-address instructions to two operands. -/// +/// Reduce two-address instructions to two operands. bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &Func) { MF = &Func; const TargetMachine &TM = MF->getTarget(); MRI = &MF->getRegInfo(); - TII = TM.getInstrInfo(); - TRI = TM.getRegisterInfo(); - InstrItins = TM.getInstrItineraryData(); + TII = MF->getSubtarget().getInstrInfo(); + TRI = MF->getSubtarget().getRegisterInfo(); + InstrItins = MF->getSubtarget().getInstrItineraryData(); LV = getAnalysisIfAvailable(); LIS = getAnalysisIfAvailable(); - AA = &getAnalysis(); + AA = &getAnalysis().getAAResults(); OptLevel = TM.getOptLevel(); bool MadeChange = false; @@ -1522,7 +1631,7 @@ bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &Func) { TiedOperandMap TiedOperands; for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end(); MBBI != MBBE; ++MBBI) { - MBB = MBBI; + MBB = &*MBBI; unsigned Dist = 0; DistanceMap.clear(); SrcRegMap.clear(); @@ -1569,8 +1678,8 @@ bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &Func) { unsigned DstReg = mi->getOperand(DstIdx).getReg(); if (SrcReg != DstReg && tryInstructionTransform(mi, nmi, SrcIdx, DstIdx, Dist, false)) { - // The tied operands have been eliminated or shifted further down the - // block to ease elimination. Continue processing with 'nmi'. + // The tied operands have been eliminated or shifted further down + // the block to ease elimination. Continue processing with 'nmi'. TiedOperands.clear(); mi = nmi; continue; @@ -1579,9 +1688,8 @@ bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &Func) { } // Now iterate over the information collected above. - for (TiedOperandMap::iterator OI = TiedOperands.begin(), - OE = TiedOperands.end(); OI != OE; ++OI) { - processTiedPairs(mi, OI->second, Dist); + for (auto &TO : TiedOperands) { + processTiedPairs(mi, TO.second, Dist); DEBUG(dbgs() << "\t\trewrite to:\t" << *mi); }