X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FCodeGen%2FTwoAddressInstructionPass.cpp;h=1b4fe705eb85a35eef5763873ac4ab0c32d113a4;hp=26c5fe4dcba9c576be07cd6fadbd49d8e9ec8a23;hb=49c8f7512a37b53bf459e51241935ab4ab67ef38;hpb=cc6137e30b40ddf3cdbbb6ebbe01e5b5c76da2e2 diff --git a/lib/CodeGen/TwoAddressInstructionPass.cpp b/lib/CodeGen/TwoAddressInstructionPass.cpp index 26c5fe4dcba..1b4fe705eb8 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" @@ -43,14 +42,18 @@ #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/IR/Function.h" #include "llvm/MC/MCInstrItineraries.h" +#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/TargetOptions.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"); @@ -59,6 +62,12 @@ STATISTIC(Num3AddrSunk, "Number of 3-address instructions sunk"); STATISTIC(NumReSchedUps, "Number of instructions re-scheduled up"); STATISTIC(NumReSchedDowns, "Number of instructions re-scheduled down"); +// Temporary flag to disable rescheduling. +static cl::opt +EnableRescheduling("twoaddr-reschedule", + cl::desc("Coalesce copies by rescheduling (default=true)"), + cl::init(true), cl::Hidden); + namespace { class TwoAddressInstructionPass : public MachineFunctionPass { MachineFunction *MF; @@ -94,13 +103,15 @@ class TwoAddressInstructionPass : public MachineFunctionPass { 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); @@ -122,6 +133,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); @@ -138,9 +154,9 @@ public: initializeTwoAddressInstructionPassPass(*PassRegistry::getPassRegistry()); } - virtual void getAnalysisUsage(AnalysisUsage &AU) const { + void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesCFG(); - AU.addRequired(); + AU.addRequired(); AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); @@ -150,14 +166,14 @@ public: } /// runOnMachineFunction - Pass entry point. - bool runOnMachineFunction(MachineFunction&); + bool runOnMachineFunction(MachineFunction&) override; }; } // end anonymous namespace 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) @@ -178,7 +194,7 @@ 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; @@ -205,7 +221,7 @@ sink3AddrInstruction(MachineInstr *MI, unsigned SavedReg, } // Find the instruction that kills SavedReg. - MachineInstr *KillMI = NULL; + MachineInstr *KillMI = nullptr; if (LIS) { LiveInterval &LI = LIS->getInterval(SavedReg); assert(LI.end() != LI.begin() && @@ -223,7 +239,7 @@ sink3AddrInstruction(MachineInstr *MI, unsigned SavedReg, for (MachineRegisterInfo::use_nodbg_iterator UI = MRI->use_nodbg_begin(SavedReg), UE = MRI->use_nodbg_end(); UI != UE; ++UI) { - MachineOperand &UseMO = UI.getOperand(); + MachineOperand &UseMO = *UI; if (!UseMO.isKill()) continue; KillMI = UseMO.getParent(); @@ -244,12 +260,12 @@ sink3AddrInstruction(MachineInstr *MI, unsigned SavedReg, // 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. - MachineOperand *KillMO = NULL; + MachineOperand *KillMO = nullptr; MachineBasicBlock::iterator KillPos = KillMI; ++KillPos; unsigned NumVisited = 0; - for (MachineBasicBlock::iterator I = llvm::next(OldPos); I != KillPos; ++I) { + for (MachineBasicBlock::iterator I = std::next(OldPos); I != KillPos; ++I) { MachineInstr *OtherMI = I; // DBG_VALUE cannot be counted against the limit. if (OtherMI->isDebugValue()) @@ -301,6 +317,45 @@ sink3AddrInstruction(MachineInstr *MI, unsigned SavedReg, return true; } +/// getSingleDef -- 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; +} + /// 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 @@ -309,9 +364,7 @@ bool TwoAddressInstructionPass::noUseAfterLastDef(unsigned Reg, unsigned Dist, unsigned &LastDef) { LastDef = 0; unsigned LastUse = Dist; - for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(Reg), - E = MRI->reg_end(); I != E; ++I) { - MachineOperand &MO = I.getOperand(); + for (MachineOperand &MO : MRI->reg_operands(Reg)) { MachineInstr *MI = MO.getParent(); if (MI->getParent() != MBB || MI->isDebugValue()) continue; @@ -411,9 +464,9 @@ 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 (llvm::next(Begin) != MRI->def_end()) + if (std::next(Begin) != MRI->def_end()) return true; - DefMI = &*Begin; + DefMI = Begin->getParent(); bool IsSrcPhys, IsDstPhys; unsigned SrcReg, DstReg; // If the def is something other than a copy, then it isn't going to @@ -427,10 +480,7 @@ 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 MCInstrDesc &MCID = MI.getDesc(); - unsigned NumOps = MI.isInlineAsm() - ? MI.getNumOperands() : MCID.getNumOperands(); - for (unsigned i = 0; i != NumOps; ++i) { + for (unsigned i = 0, NumOps = MI.getNumOperands(); i != NumOps; ++i) { const MachineOperand &MO = MI.getOperand(i); if (!MO.isReg() || !MO.isUse() || MO.getReg() != Reg) continue; @@ -453,10 +503,10 @@ MachineInstr *findOnlyInterestingUse(unsigned Reg, MachineBasicBlock *MBB, unsigned &DstReg, bool &IsDstPhys) { if (!MRI->hasOneNonDBGUse(Reg)) // None or more than one use. - return 0; - MachineInstr &UseMI = *MRI->use_nodbg_begin(Reg); + return nullptr; + MachineInstr &UseMI = *MRI->use_instr_nodbg_begin(Reg); if (UseMI.getParent() != MBB) - return 0; + return nullptr; unsigned SrcReg; bool IsSrcPhys; if (isCopyToReg(UseMI, TII, SrcReg, DstReg, IsSrcPhys, IsDstPhys)) { @@ -468,7 +518,7 @@ MachineInstr *findOnlyInterestingUse(unsigned Reg, MachineBasicBlock *MBB, IsDstPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); return &UseMI; } - return 0; + return nullptr; } /// getMappedReg - Return the physical register the specified virtual register @@ -542,10 +592,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 @@ -560,6 +621,27 @@ 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; @@ -568,14 +650,15 @@ isProfitableToCommute(unsigned regA, unsigned regB, unsigned regC, /// 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; +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 == 0) { + if (NewMI == nullptr) { DEBUG(dbgs() << "2addr: COMMUTING FAILED!\n"); return false; } @@ -644,7 +727,7 @@ TwoAddressInstructionPass::convertInstTo3Addr(MachineBasicBlock::iterator &mi, if (!Sunk) { DistanceMap.insert(std::make_pair(NewMI, Dist)); mi = NewMI; - nmi = llvm::next(mi); + nmi = std::next(mi); } // Update source and destination register maps. @@ -664,7 +747,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); @@ -754,7 +837,7 @@ rescheduleMIBelowKill(MachineBasicBlock::iterator &mi, // Must be created from unfolded load. Don't waste time trying this. return false; - MachineInstr *KillMI = 0; + MachineInstr *KillMI = nullptr; if (LIS) { LiveInterval &LI = LIS->getInterval(Reg); assert(LI.end() != LI.begin() && @@ -784,7 +867,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) @@ -813,7 +896,7 @@ rescheduleMIBelowKill(MachineBasicBlock::iterator &mi, // Move the copies connected to MI down as well. MachineBasicBlock::iterator Begin = MI; - MachineBasicBlock::iterator AfterMI = llvm::next(Begin); + MachineBasicBlock::iterator AfterMI = std::next(Begin); MachineBasicBlock::iterator End = AfterMI; while (End->isCopy() && Defs.count(End->getOperand(1).getReg())) { @@ -873,7 +956,7 @@ rescheduleMIBelowKill(MachineBasicBlock::iterator &mi, } // Move debug info as well. - while (Begin != MBB->begin() && llvm::prior(Begin)->isDebugValue()) + while (Begin != MBB->begin() && std::prev(Begin)->isDebugValue()) --Begin; nmi = End; @@ -888,7 +971,7 @@ rescheduleMIBelowKill(MachineBasicBlock::iterator &mi, LIS->handleMove(CopyMI); InsertPos = CopyMI; } - End = llvm::next(MachineBasicBlock::iterator(MI)); + End = std::next(MachineBasicBlock::iterator(MI)); } // Copies following MI may have been moved as well. @@ -911,19 +994,17 @@ rescheduleMIBelowKill(MachineBasicBlock::iterator &mi, /// instruction too close to the defs of its register dependencies. bool TwoAddressInstructionPass::isDefTooClose(unsigned Reg, unsigned Dist, MachineInstr *MI) { - 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()) + for (MachineInstr &DefMI : MRI->def_instructions(Reg)) { + if (DefMI.getParent() != MBB || DefMI.isCopy() || DefMI.isCopyLike()) continue; - if (DefMI == MI) + if (&DefMI == MI) return true; // MI is defining something KillMI uses - DenseMap::iterator DDI = DistanceMap.find(DefMI); + 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) > (Dist - DefDist)) + if (TII->getInstrLatency(InstrItins, &DefMI) > (Dist - DefDist)) return true; } return false; @@ -948,7 +1029,7 @@ rescheduleKillAboveMI(MachineBasicBlock::iterator &mi, // Must be created from unfolded load. Don't waste time trying this. return false; - MachineInstr *KillMI = 0; + MachineInstr *KillMI = nullptr; if (LIS) { LiveInterval &LI = LIS->getInterval(Reg); assert(LI.end() != LI.begin() && @@ -973,7 +1054,7 @@ rescheduleKillAboveMI(MachineBasicBlock::iterator &mi, return false; bool SeenStore = true; - if (!KillMI->isSafeToMove(TII, AA, SeenStore)) + if (!KillMI->isSafeToMove(AA, SeenStore)) return false; SmallSet Uses; @@ -1057,15 +1138,15 @@ rescheduleKillAboveMI(MachineBasicBlock::iterator &mi, // 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()) + while (InsertPos != MBB->begin() && std::prev(InsertPos)->isDebugValue()) --InsertPos; MachineBasicBlock::iterator From = KillMI; - MachineBasicBlock::iterator To = llvm::next(From); - while (llvm::prior(From)->isDebugValue()) + MachineBasicBlock::iterator To = std::next(From); + while (std::prev(From)->isDebugValue()) --From; MBB->splice(InsertPos, MBB, From, To); - nmi = llvm::prior(InsertPos); // Backtrack so we process the moved instr. + nmi = std::prev(InsertPos); // Backtrack so we process the moved instr. DistanceMap.erase(DI); // Update live variables @@ -1080,6 +1161,61 @@ rescheduleKillAboveMI(MachineBasicBlock::iterator &mi, return true; } +/// 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 searches 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; +} + /// 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 @@ -1106,50 +1242,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 (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. @@ -1162,9 +1284,13 @@ 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 (rescheduleKillAboveMI(mi, nmi, regB)) { + if (EnableRescheduling && rescheduleKillAboveMI(mi, nmi, regB)) { ++NumReSchedUps; return true; } @@ -1314,13 +1440,14 @@ collectTiedOperands(MachineInstr *MI, TiedOperandMap &TiedOperands) { assert(SrcReg && SrcMO.isUse() && "two address instruction invalid"); // Deal with uses immediately - simply rewrite the src operand. - if (SrcMO.isUndef()) { + if (SrcMO.isUndef() && !DstMO.getSubReg()) { // Constrain the DstReg register class if required. if (TargetRegisterInfo::isVirtualRegister(DstReg)) if (const TargetRegisterClass *RC = TII->getRegClass(MCID, SrcIdx, TRI, *MF)) MRI->constrainRegClass(DstReg, RC); SrcMO.setReg(DstReg); + SrcMO.setSubReg(0); DEBUG(dbgs() << "\t\trewrite undef:\t" << *MI); continue; } @@ -1346,6 +1473,7 @@ TwoAddressInstructionPass::processTiedPairs(MachineInstr *MI, unsigned LastCopiedReg = 0; SlotIndex LastCopyIdx; unsigned RegB = 0; + unsigned SubRegB = 0; for (unsigned tpi = 0, tpe = TiedPairs.size(); tpi != tpe; ++tpi) { unsigned SrcIdx = TiedPairs[tpi].first; unsigned DstIdx = TiedPairs[tpi].second; @@ -1356,6 +1484,7 @@ TwoAddressInstructionPass::processTiedPairs(MachineInstr *MI, // Grab RegB from the instruction because it may have changed if the // instruction was commuted. RegB = MI->getOperand(SrcIdx).getReg(); + SubRegB = MI->getOperand(SrcIdx).getSubReg(); if (RegA == RegB) { // The register is tied to multiple destinations (or else we would @@ -1380,8 +1509,25 @@ TwoAddressInstructionPass::processTiedPairs(MachineInstr *MI, #endif // Emit a copy. - BuildMI(*MI->getParent(), MI, MI->getDebugLoc(), - TII->get(TargetOpcode::COPY), RegA).addReg(RegB); + MachineInstrBuilder MIB = BuildMI(*MI->getParent(), MI, MI->getDebugLoc(), + TII->get(TargetOpcode::COPY), RegA); + // If this operand is folding a truncation, the truncation now moves to the + // copy so that the register classes remain valid for the operands. + MIB.addReg(RegB, 0, SubRegB); + const TargetRegisterClass *RC = MRI->getRegClass(RegB); + if (SubRegB) { + if (TargetRegisterInfo::isVirtualRegister(RegA)) { + assert(TRI->getMatchingSuperRegClass(RC, MRI->getRegClass(RegA), + SubRegB) && + "tied subregister must be a truncation"); + // The superreg class will not be used to constrain the subreg class. + RC = nullptr; + } + else { + assert(TRI->getMatchingSuperReg(RegA, SubRegB, MRI->getRegClass(RegB)) + && "tied subregister must be a truncation"); + } + } // Update DistanceMap. MachineBasicBlock::iterator PrevMI = MI; @@ -1397,11 +1543,11 @@ TwoAddressInstructionPass::processTiedPairs(MachineInstr *MI, VNInfo *VNI = LI.getNextValue(LastCopyIdx, LIS->getVNInfoAllocator()); SlotIndex endIdx = LIS->getInstructionIndex(MI).getRegSlot(IsEarlyClobber); - LI.addRange(LiveRange(LastCopyIdx, endIdx, VNI)); + LI.addSegment(LiveInterval::Segment(LastCopyIdx, endIdx, VNI)); } } - DEBUG(dbgs() << "\t\tprepend:\t" << *PrevMI); + DEBUG(dbgs() << "\t\tprepend:\t" << *MIB); MachineOperand &MO = MI->getOperand(SrcIdx); assert(MO.isReg() && MO.getReg() == RegB && MO.isUse() && @@ -1414,26 +1560,30 @@ TwoAddressInstructionPass::processTiedPairs(MachineInstr *MI, // Make sure regA is a legal regclass for the SrcIdx operand. if (TargetRegisterInfo::isVirtualRegister(RegA) && TargetRegisterInfo::isVirtualRegister(RegB)) - MRI->constrainRegClass(RegA, MRI->getRegClass(RegB)); - + MRI->constrainRegClass(RegA, RC); MO.setReg(RegA); + // The getMatchingSuper asserts guarantee that the register class projected + // by SubRegB is compatible with RegA with no subregister. So regardless of + // whether the dest oper writes a subreg, the source oper should not. + MO.setSubReg(0); // Propagate SrcRegMap. 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); - if (MO.isReg() && MO.getReg() == RegB && MO.isUse()) { + if (MO.isReg() && MO.getReg() == RegB && MO.getSubReg() == SubRegB && + MO.isUse()) { if (MO.isKill()) { MO.setIsKill(false); RemovedKillFlag = true; } MO.setReg(LastCopiedReg); + MO.setSubReg(0); } } } @@ -1454,7 +1604,7 @@ TwoAddressInstructionPass::processTiedPairs(MachineInstr *MI, SlotIndex UseIdx = MIIdx.getRegSlot(IsEarlyClobber); if (I->end == UseIdx) - LI.removeRange(LastCopyIdx, UseIdx); + LI.removeSegment(LastCopyIdx, UseIdx); } } else if (RemovedKillFlag) { @@ -1478,12 +1628,12 @@ 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; @@ -1506,7 +1656,7 @@ bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &Func) { Processed.clear(); for (MachineBasicBlock::iterator mi = MBB->begin(), me = MBB->end(); mi != me; ) { - MachineBasicBlock::iterator nmi = llvm::next(mi); + MachineBasicBlock::iterator nmi = std::next(mi); if (mi->isDebugValue()) { mi = nmi; continue; @@ -1536,7 +1686,7 @@ bool TwoAddressInstructionPass::runOnMachineFunction(MachineFunction &Func) { // transformations that may either eliminate the tied operands or // improve the opportunities for coalescing away the register copy. if (TiedOperands.size() == 1) { - SmallVector, 4> &TiedPairs + SmallVectorImpl > &TiedPairs = TiedOperands.begin()->second; if (TiedPairs.size() == 1) { unsigned SrcIdx = TiedPairs[0].first; @@ -1545,8 +1695,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; @@ -1607,7 +1757,7 @@ eliminateRegSequence(MachineBasicBlock::iterator &MBBI) { TargetRegisterInfo::isPhysicalRegister(DstReg) || !(MI->getNumOperands() & 1)) { DEBUG(dbgs() << "Illegal REG_SEQUENCE instruction:" << *MI); - llvm_unreachable(0); + llvm_unreachable(nullptr); } SmallVector OrigRegs; @@ -1661,7 +1811,7 @@ eliminateRegSequence(MachineBasicBlock::iterator &MBBI) { } MachineBasicBlock::iterator EndMBBI = - llvm::next(MachineBasicBlock::iterator(MI)); + std::next(MachineBasicBlock::iterator(MI)); if (!DefEmitted) { DEBUG(dbgs() << "Turned: " << *MI << " into an IMPLICIT_DEF");