X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FCodeGen%2FRegisterCoalescer.cpp;h=7739d64b45f8d37f65113750fc2032b977d04a14;hp=f0a4b28306fe421ad691aa35c78a4710dcf76bc6;hb=fdec461fa2fb048febec7b394c84b4e8b20f49cc;hpb=54d3aa15376e74ed9e16b376dfd8bd63520a002d diff --git a/lib/CodeGen/RegisterCoalescer.cpp b/lib/CodeGen/RegisterCoalescer.cpp index f0a4b28306f..7739d64b45f 100644 --- a/lib/CodeGen/RegisterCoalescer.cpp +++ b/lib/CodeGen/RegisterCoalescer.cpp @@ -13,9 +13,7 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "regalloc" #include "RegisterCoalescer.h" -#include "llvm/ADT/OwningPtr.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/Statistic.h" @@ -43,6 +41,8 @@ #include using namespace llvm; +#define DEBUG_TYPE "regalloc" + STATISTIC(numJoins , "Number of interval joins performed"); STATISTIC(numCrossRCs , "Number of cross class joins performed"); STATISTIC(numCommutes , "Number of instruction commuting performed"); @@ -57,12 +57,16 @@ EnableJoining("join-liveintervals", cl::desc("Coalesce copies (default=true)"), cl::init(true)); -// Temporary flag to test critical edge unsplitting. +static cl::opt UseTerminalRule("terminal-rule", + cl::desc("Apply the terminal rule"), + cl::init(false), cl::Hidden); + +/// Temporary flag to test critical edge unsplitting. static cl::opt EnableJoinSplits("join-splitedges", cl::desc("Coalesce copies on split edges (default=subtarget)"), cl::Hidden); -// Temporary flag to test global copy optimization. +/// Temporary flag to test global copy optimization. static cl::opt EnableGlobalCopies("join-globalcopies", cl::desc("Coalesce copies that span blocks (default=subtarget)"), @@ -86,6 +90,14 @@ namespace { AliasAnalysis *AA; RegisterClassInfo RegClassInfo; + /// A LaneMask to remember on which subregister live ranges we need to call + /// shrinkToUses() later. + LaneBitmask ShrinkMask; + + /// True if the main range of the currently coalesced intervals should be + /// checked for smaller live intervals. + bool ShrinkMainRange; + /// \brief True if the coalescer should aggressively coalesce global copies /// in favor of keeping local copies. bool JoinGlobalCopies; @@ -94,11 +106,11 @@ namespace { /// blocks exclusively containing copies. bool JoinSplitEdges; - /// WorkList - Copy instructions yet to be coalesced. + /// Copy instructions yet to be coalesced. SmallVector WorkList; SmallVector LocalWorkList; - /// ErasedInstrs - Set of instruction pointers that have been erased, and + /// Set of instruction pointers that have been erased, and /// that may be present in WorkList. SmallPtrSet ErasedInstrs; @@ -111,32 +123,31 @@ namespace { /// Recursively eliminate dead defs in DeadDefs. void eliminateDeadDefs(); - /// LiveRangeEdit callback. - void LRE_WillEraseInstruction(MachineInstr *MI); + /// LiveRangeEdit callback for eliminateDeadDefs(). + void LRE_WillEraseInstruction(MachineInstr *MI) override; - /// coalesceLocals - coalesce the LocalWorkList. + /// Coalesce the LocalWorkList. void coalesceLocals(); - /// joinAllIntervals - join compatible live intervals + /// Join compatible live intervals void joinAllIntervals(); - /// copyCoalesceInMBB - Coalesce copies in the specified MBB, putting + /// Coalesce copies in the specified MBB, putting /// copies that cannot yet be coalesced into WorkList. void copyCoalesceInMBB(MachineBasicBlock *MBB); - /// copyCoalesceWorkList - Try to coalesce all copies in CurrList. Return - /// true if any progress was made. + /// Tries to coalesce all copies in CurrList. Returns true if any progress + /// was made. bool copyCoalesceWorkList(MutableArrayRef CurrList); - /// joinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, - /// which are the src/dst of the copy instruction CopyMI. This returns - /// true if the copy was successfully coalesced away. If it is not - /// currently possible to coalesce this interval, but it may be possible if - /// other things get coalesced, then it returns true by reference in - /// 'Again'. + /// Attempt to join intervals corresponding to SrcReg/DstReg, which are the + /// src/dst of the copy instruction CopyMI. This returns true if the copy + /// was successfully coalesced away. If it is not currently possible to + /// coalesce this interval, but it may be possible if other things get + /// coalesced, then it returns true by reference in 'Again'. bool joinCopy(MachineInstr *TheCopy, bool &Again); - /// joinIntervals - Attempt to join these two intervals. On failure, this + /// Attempt to join these two intervals. On failure, this /// returns false. The output "SrcInt" will not have been modified, so we /// can use this information below to update aliases. bool joinIntervals(CoalescerPair &CP); @@ -147,58 +158,101 @@ namespace { /// Attempt joining with a reserved physreg. bool joinReservedPhysReg(CoalescerPair &CP); - /// adjustCopiesBackFrom - We found a non-trivially-coalescable copy. If - /// the source value number is defined by a copy from the destination reg - /// see if we can merge these two destination reg valno# into a single - /// value number, eliminating a copy. + /// Add the LiveRange @p ToMerge as a subregister liverange of @p LI. + /// Subranges in @p LI which only partially interfere with the desired + /// LaneMask are split as necessary. @p LaneMask are the lanes that + /// @p ToMerge will occupy in the coalescer register. @p LI has its subrange + /// lanemasks already adjusted to the coalesced register. + /// @returns false if live range conflicts couldn't get resolved. + bool mergeSubRangeInto(LiveInterval &LI, const LiveRange &ToMerge, + LaneBitmask LaneMask, CoalescerPair &CP); + + /// Join the liveranges of two subregisters. Joins @p RRange into + /// @p LRange, @p RRange may be invalid afterwards. + /// @returns false if live range conflicts couldn't get resolved. + bool joinSubRegRanges(LiveRange &LRange, LiveRange &RRange, + LaneBitmask LaneMask, const CoalescerPair &CP); + + /// We found a non-trivially-coalescable copy. If the source value number is + /// defined by a copy from the destination reg see if we can merge these two + /// destination reg valno# into a single value number, eliminating a copy. + /// This returns true if an interval was modified. bool adjustCopiesBackFrom(const CoalescerPair &CP, MachineInstr *CopyMI); - /// hasOtherReachingDefs - Return true if there are definitions of IntB + /// Return true if there are definitions of IntB /// other than BValNo val# that can reach uses of AValno val# of IntA. bool hasOtherReachingDefs(LiveInterval &IntA, LiveInterval &IntB, VNInfo *AValNo, VNInfo *BValNo); - /// removeCopyByCommutingDef - We found a non-trivially-coalescable copy. + /// We found a non-trivially-coalescable copy. /// If the source value number is defined by a commutable instruction and /// its other operand is coalesced to the copy dest register, see if we /// can transform the copy into a noop by commuting the definition. + /// This returns true if an interval was modified. bool removeCopyByCommutingDef(const CoalescerPair &CP,MachineInstr *CopyMI); - /// reMaterializeTrivialDef - If the source of a copy is defined by a + /// If the source of a copy is defined by a /// trivial computation, replace the copy by rematerialize the definition. - bool reMaterializeTrivialDef(CoalescerPair &CP, MachineInstr *CopyMI, + bool reMaterializeTrivialDef(const CoalescerPair &CP, MachineInstr *CopyMI, bool &IsDefCopy); - /// canJoinPhys - Return true if a physreg copy should be joined. + /// Return true if a copy involving a physreg should be joined. bool canJoinPhys(const CoalescerPair &CP); - /// updateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and - /// update the subregister number if it is not zero. If DstReg is a - /// physical register and the existing subregister number of the def / use - /// being updated is not zero, make sure to set it to the correct physical - /// subregister. + /// Replace all defs and uses of SrcReg to DstReg and update the subregister + /// number if it is not zero. If DstReg is a physical register and the + /// existing subregister number of the def / use being updated is not zero, + /// make sure to set it to the correct physical subregister. void updateRegDefsUses(unsigned SrcReg, unsigned DstReg, unsigned SubIdx); - /// eliminateUndefCopy - Handle copies of undef values. - bool eliminateUndefCopy(MachineInstr *CopyMI, const CoalescerPair &CP); + /// Handle copies of undef values. + /// Returns true if @p CopyMI was a copy of an undef value and eliminated. + bool eliminateUndefCopy(MachineInstr *CopyMI); + + /// Check whether or not we should apply the terminal rule on the + /// destination (Dst) of \p Copy. + /// When the terminal rule applies, Copy is not profitable to + /// coalesce. + /// Dst is terminal if it has exactly one affinity (Dst, Src) and + /// at least one interference (Dst, Dst2). If Dst is terminal, the + /// terminal rule consists in checking that at least one of + /// interfering node, say Dst2, has an affinity of equal or greater + /// weight with Src. + /// In that case, Dst2 and Dst will not be able to be both coalesced + /// with Src. Since Dst2 exposes more coalescing opportunities than + /// Dst, we can drop \p Copy. + bool applyTerminalRule(const MachineInstr &Copy) const; + + /// Wrapper method for \see LiveIntervals::shrinkToUses. + /// This method does the proper fixing of the live-ranges when the afore + /// mentioned method returns true. + void shrinkToUses(LiveInterval *LI, + SmallVectorImpl *Dead = nullptr) { + if (LIS->shrinkToUses(LI, Dead)) { + /// Check whether or not \p LI is composed by multiple connected + /// components and if that is the case, fix that. + SmallVector SplitLIs; + LIS->splitSeparateComponents(*LI, SplitLIs); + } + } public: - static char ID; // Class identification, replacement for typeinfo + static char ID; ///< Class identification, replacement for typeinfo RegisterCoalescer() : MachineFunctionPass(ID) { initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry()); } - virtual void getAnalysisUsage(AnalysisUsage &AU) const; + void getAnalysisUsage(AnalysisUsage &AU) const override; - virtual void releaseMemory(); + void releaseMemory() override; - /// runOnMachineFunction - pass entry point - virtual bool runOnMachineFunction(MachineFunction&); + /// This is the pass entry point. + bool runOnMachineFunction(MachineFunction&) override; - /// print - Implement the dump method. - virtual void print(raw_ostream &O, const Module* = 0) const; + /// Implement the dump method. + void print(raw_ostream &O, const Module* = nullptr) const override; }; -} /// end anonymous namespace +} // end anonymous namespace char &llvm::RegisterCoalescerID = RegisterCoalescer::ID; @@ -207,7 +261,7 @@ INITIALIZE_PASS_BEGIN(RegisterCoalescer, "simple-register-coalescing", INITIALIZE_PASS_DEPENDENCY(LiveIntervals) INITIALIZE_PASS_DEPENDENCY(SlotIndexes) INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) -INITIALIZE_AG_DEPENDENCY(AliasAnalysis) +INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) INITIALIZE_PASS_END(RegisterCoalescer, "simple-register-coalescing", "Simple Register Coalescing", false, false) @@ -232,18 +286,17 @@ static bool isMoveInstr(const TargetRegisterInfo &tri, const MachineInstr *MI, return true; } -// Return true if this block should be vacated by the coalescer to eliminate -// branches. The important cases to handle in the coalescer are critical edges -// split during phi elimination which contain only copies. Simple blocks that -// contain non-branches should also be vacated, but this can be handled by an -// earlier pass similar to early if-conversion. +/// Return true if this block should be vacated by the coalescer to eliminate +/// branches. The important cases to handle in the coalescer are critical edges +/// split during phi elimination which contain only copies. Simple blocks that +/// contain non-branches should also be vacated, but this can be handled by an +/// earlier pass similar to early if-conversion. static bool isSplitEdge(const MachineBasicBlock *MBB) { if (MBB->pred_size() != 1 || MBB->succ_size() != 1) return false; - for (MachineBasicBlock::const_iterator MII = MBB->begin(), E = MBB->end(); - MII != E; ++MII) { - if (!MII->isCopyLike() && !MII->isUnconditionalBranch()) + for (const auto &MI : *MBB) { + if (!MI.isCopyLike() && !MI.isUnconditionalBranch()) return false; } return true; @@ -252,7 +305,7 @@ static bool isSplitEdge(const MachineBasicBlock *MBB) { bool CoalescerPair::setRegisters(const MachineInstr *MI) { SrcReg = DstReg = 0; SrcIdx = DstIdx = 0; - NewRC = 0; + NewRC = nullptr; Flipped = CrossClass = false; unsigned Src, Dst, SrcSub, DstSub; @@ -283,7 +336,6 @@ bool CoalescerPair::setRegisters(const MachineInstr *MI) { if (SrcSub) { Dst = TRI.getMatchingSuperReg(Dst, SrcSub, MRI.getRegClass(Src)); if (!Dst) return false; - SrcSub = 0; } else if (!MRI.getRegClass(Src)->contains(Dst)) { return false; } @@ -387,7 +439,7 @@ bool CoalescerPair::isCoalescable(const MachineInstr *MI) const { void RegisterCoalescer::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesCFG(); - AU.addRequired(); + AU.addRequired(); AU.addRequired(); AU.addPreserved(); AU.addPreserved(); @@ -399,30 +451,15 @@ void RegisterCoalescer::getAnalysisUsage(AnalysisUsage &AU) const { void RegisterCoalescer::eliminateDeadDefs() { SmallVector NewRegs; - LiveRangeEdit(0, NewRegs, *MF, *LIS, 0, this).eliminateDeadDefs(DeadDefs); + LiveRangeEdit(nullptr, NewRegs, *MF, *LIS, + nullptr, this).eliminateDeadDefs(DeadDefs); } -// Callback from eliminateDeadDefs(). void RegisterCoalescer::LRE_WillEraseInstruction(MachineInstr *MI) { // MI may be in WorkList. Make sure we don't visit it. ErasedInstrs.insert(MI); } -/// adjustCopiesBackFrom - We found a non-trivially-coalescable copy with IntA -/// being the source and IntB being the dest, thus this defines a value number -/// in IntB. If the source value number (in IntA) is defined by a copy from B, -/// see if we can merge these two pieces of B into a single value number, -/// eliminating a copy. For example: -/// -/// A3 = B0 -/// ... -/// B1 = A3 <- this copy -/// -/// In this case, B0 can be extended to where the B1 copy lives, allowing the B1 -/// value number to be replaced with B0 (which simplifies the B liveinterval). -/// -/// This returns true if an interval was modified. -/// bool RegisterCoalescer::adjustCopiesBackFrom(const CoalescerPair &CP, MachineInstr *CopyMI) { assert(!CP.isPartial() && "This doesn't work for partial copies."); @@ -434,6 +471,20 @@ bool RegisterCoalescer::adjustCopiesBackFrom(const CoalescerPair &CP, LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg()); SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(); + // We have a non-trivially-coalescable copy with IntA being the source and + // IntB being the dest, thus this defines a value number in IntB. If the + // source value number (in IntA) is defined by a copy from B, see if we can + // merge these two pieces of B into a single value number, eliminating a copy. + // For example: + // + // A3 = B0 + // ... + // B1 = A3 <- this copy + // + // In this case, B0 can be extended to where the B1 copy lives, allowing the + // B1 value number to be replaced with B0 (which simplifies the B + // liveinterval). + // BValNo is a value number in B that is defined by a copy from A. 'B1' in // the example above. LiveInterval::iterator BS = IntB.FindSegmentContaining(CopyIdx); @@ -493,6 +544,16 @@ bool RegisterCoalescer::adjustCopiesBackFrom(const CoalescerPair &CP, // Okay, merge "B1" into the same value number as "B0". if (BValNo != ValS->valno) IntB.MergeValueNumberInto(BValNo, ValS->valno); + + // Do the same for the subregister segments. + for (LiveInterval::SubRange &S : IntB.subranges()) { + VNInfo *SubBValNo = S.getVNInfoAt(CopyIdx); + S.addSegment(LiveInterval::Segment(FillerStart, FillerEnd, SubBValNo)); + VNInfo *SubValSNo = S.getVNInfoAt(AValNo->def.getPrevSlot()); + if (SubBValNo != SubValSNo) + S.MergeValueNumberInto(SubBValNo, SubValSNo); + } + DEBUG(dbgs() << " result = " << IntB << '\n'); // If the source instruction was killing the source register before the @@ -507,14 +568,12 @@ bool RegisterCoalescer::adjustCopiesBackFrom(const CoalescerPair &CP, // will also add the isKill marker. CopyMI->substituteRegister(IntA.reg, IntB.reg, 0, *TRI); if (AS->end == CopyIdx) - LIS->shrinkToUses(&IntA); + shrinkToUses(&IntA); ++numExtends; return true; } -/// hasOtherReachingDefs - Return true if there are definitions of IntB -/// other than BValNo val# that can reach uses of AValno val# of IntA. bool RegisterCoalescer::hasOtherReachingDefs(LiveInterval &IntA, LiveInterval &IntB, VNInfo *AValNo, @@ -524,69 +583,75 @@ bool RegisterCoalescer::hasOtherReachingDefs(LiveInterval &IntA, if (LIS->hasPHIKill(IntA, AValNo)) return true; - for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); - AI != AE; ++AI) { - if (AI->valno != AValNo) continue; + for (LiveRange::Segment &ASeg : IntA.segments) { + if (ASeg.valno != AValNo) continue; LiveInterval::iterator BI = - std::upper_bound(IntB.begin(), IntB.end(), AI->start); + std::upper_bound(IntB.begin(), IntB.end(), ASeg.start); if (BI != IntB.begin()) --BI; - for (; BI != IntB.end() && AI->end >= BI->start; ++BI) { + for (; BI != IntB.end() && ASeg.end >= BI->start; ++BI) { if (BI->valno == BValNo) continue; - if (BI->start <= AI->start && BI->end > AI->start) + if (BI->start <= ASeg.start && BI->end > ASeg.start) return true; - if (BI->start > AI->start && BI->start < AI->end) + if (BI->start > ASeg.start && BI->start < ASeg.end) return true; } } return false; } -/// removeCopyByCommutingDef - We found a non-trivially-coalescable copy with -/// IntA being the source and IntB being the dest, thus this defines a value -/// number in IntB. If the source value number (in IntA) is defined by a -/// commutable instruction and its other operand is coalesced to the copy dest -/// register, see if we can transform the copy into a noop by commuting the -/// definition. For example, -/// -/// A3 = op A2 B0 -/// ... -/// B1 = A3 <- this copy -/// ... -/// = op A3 <- more uses -/// -/// ==> -/// -/// B2 = op B0 A2 -/// ... -/// B1 = B2 <- now an identify copy -/// ... -/// = op B2 <- more uses -/// -/// This returns true if an interval was modified. -/// +/// Copy segements with value number @p SrcValNo from liverange @p Src to live +/// range @Dst and use value number @p DstValNo there. +static void addSegmentsWithValNo(LiveRange &Dst, VNInfo *DstValNo, + const LiveRange &Src, const VNInfo *SrcValNo) +{ + for (const LiveRange::Segment &S : Src.segments) { + if (S.valno != SrcValNo) + continue; + Dst.addSegment(LiveRange::Segment(S.start, S.end, DstValNo)); + } +} + bool RegisterCoalescer::removeCopyByCommutingDef(const CoalescerPair &CP, MachineInstr *CopyMI) { - assert (!CP.isPhys()); - - SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(); + assert(!CP.isPhys()); LiveInterval &IntA = - LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg()); + LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg()); LiveInterval &IntB = - LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg()); + LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg()); + + // We found a non-trivially-coalescable copy with IntA being the source and + // IntB being the dest, thus this defines a value number in IntB. If the + // source value number (in IntA) is defined by a commutable instruction and + // its other operand is coalesced to the copy dest register, see if we can + // transform the copy into a noop by commuting the definition. For example, + // + // A3 = op A2 B0 + // ... + // B1 = A3 <- this copy + // ... + // = op A3 <- more uses + // + // ==> + // + // B2 = op B0 A2 + // ... + // B1 = B2 <- now an identity copy + // ... + // = op B2 <- more uses // BValNo is a value number in B that is defined by a copy from A. 'B1' in // the example above. + SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(); VNInfo *BValNo = IntB.getVNInfoAt(CopyIdx); - if (!BValNo || BValNo->def != CopyIdx) - return false; + assert(BValNo != nullptr && BValNo->def == CopyIdx); // AValNo is the value number in A that defines the copy, A3 in the example. VNInfo *AValNo = IntA.getVNInfoAt(CopyIdx.getRegSlot(true)); - assert(AValNo && "COPY source not live"); - if (AValNo->isPHIDef() || AValNo->isUnused()) + assert(AValNo && !AValNo->isUnused() && "COPY source not live"); + if (AValNo->isPHIDef()) return false; MachineInstr *DefMI = LIS->getInstructionFromIndex(AValNo->def); if (!DefMI) @@ -600,14 +665,18 @@ bool RegisterCoalescer::removeCopyByCommutingDef(const CoalescerPair &CP, unsigned UseOpIdx; if (!DefMI->isRegTiedToUseOperand(DefIdx, &UseOpIdx)) return false; - unsigned Op1, Op2, NewDstIdx; - if (!TII->findCommutedOpIndices(DefMI, Op1, Op2)) - return false; - if (Op1 == UseOpIdx) - NewDstIdx = Op2; - else if (Op2 == UseOpIdx) - NewDstIdx = Op1; - else + + // FIXME: The code below tries to commute 'UseOpIdx' operand with some other + // commutable operand which is expressed by 'CommuteAnyOperandIndex'value + // passed to the method. That _other_ operand is chosen by + // the findCommutedOpIndices() method. + // + // That is obviously an area for improvement in case of instructions having + // more than 2 operands. For example, if some instruction has 3 commutable + // operands then all possible variants (i.e. op#1<->op#2, op#1<->op#3, + // op#2<->op#3) of commute transformation should be considered/tried here. + unsigned NewDstIdx = TargetInstrInfo::CommuteAnyOperandIndex; + if (!TII->findCommutedOpIndices(DefMI, UseOpIdx, NewDstIdx)) return false; MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx); @@ -622,16 +691,15 @@ bool RegisterCoalescer::removeCopyByCommutingDef(const CoalescerPair &CP, // If some of the uses of IntA.reg is already coalesced away, return false. // It's not possible to determine whether it's safe to perform the coalescing. - for (MachineRegisterInfo::use_nodbg_iterator UI = - MRI->use_nodbg_begin(IntA.reg), - UE = MRI->use_nodbg_end(); UI != UE; ++UI) { - MachineInstr *UseMI = &*UI; + for (MachineOperand &MO : MRI->use_nodbg_operands(IntA.reg)) { + MachineInstr *UseMI = MO.getParent(); + unsigned OpNo = &MO - &UseMI->getOperand(0); SlotIndex UseIdx = LIS->getInstructionIndex(UseMI); LiveInterval::iterator US = IntA.FindSegmentContaining(UseIdx); if (US == IntA.end() || US->valno != AValNo) continue; // If this use is tied to a def, we can't rewrite the register. - if (UseMI->isRegTiedToDefOperand(UI.getOperandNo())) + if (UseMI->isRegTiedToDefOperand(OpNo)) return false; } @@ -641,7 +709,8 @@ bool RegisterCoalescer::removeCopyByCommutingDef(const CoalescerPair &CP, // At this point we have decided that it is legal to do this // transformation. Start by commuting the instruction. MachineBasicBlock *MBB = DefMI->getParent(); - MachineInstr *NewMI = TII->commuteInstruction(DefMI); + MachineInstr *NewMI = + TII->commuteInstruction(DefMI, false, UseOpIdx, NewDstIdx); if (!NewMI) return false; if (TargetRegisterInfo::isVirtualRegister(IntA.reg) && @@ -654,8 +723,6 @@ bool RegisterCoalescer::removeCopyByCommutingDef(const CoalescerPair &CP, MBB->insert(Pos, NewMI); MBB->erase(DefMI); } - unsigned OpIdx = NewMI->findRegisterUseOperandIdx(IntA.reg, false); - NewMI->getOperand(OpIdx).setIsKill(); // If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g. // A = or A, B @@ -668,10 +735,13 @@ bool RegisterCoalescer::removeCopyByCommutingDef(const CoalescerPair &CP, // Update uses of IntA of the specific Val# with IntB. for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(IntA.reg), - UE = MRI->use_end(); UI != UE;) { - MachineOperand &UseMO = UI.getOperand(); - MachineInstr *UseMI = &*UI; + UE = MRI->use_end(); + UI != UE; /* ++UI is below because of possible MI removal */) { + MachineOperand &UseMO = *UI; ++UI; + if (UseMO.isUndef()) + continue; + MachineInstr *UseMI = UseMO.getParent(); if (UseMI->isDebugValue()) { // FIXME These don't have an instruction index. Not clear we have enough // info to decide whether to do this replacement or not. For now do it. @@ -680,7 +750,8 @@ bool RegisterCoalescer::removeCopyByCommutingDef(const CoalescerPair &CP, } SlotIndex UseIdx = LIS->getInstructionIndex(UseMI).getRegSlot(true); LiveInterval::iterator US = IntA.FindSegmentContaining(UseIdx); - if (US == IntA.end() || US->valno != AValNo) + assert(US != IntA.end() && "Use must be live"); + if (US->valno != AValNo) continue; // Kill flags are no longer accurate. They are recomputed after RA. UseMO.setIsKill(false); @@ -704,7 +775,16 @@ bool RegisterCoalescer::removeCopyByCommutingDef(const CoalescerPair &CP, continue; DEBUG(dbgs() << "\t\tnoop: " << DefIdx << '\t' << *UseMI); assert(DVNI->def == DefIdx); - BValNo = IntB.MergeValueNumberInto(BValNo, DVNI); + BValNo = IntB.MergeValueNumberInto(DVNI, BValNo); + for (LiveInterval::SubRange &S : IntB.subranges()) { + VNInfo *SubDVNI = S.getVNInfoAt(DefIdx); + if (!SubDVNI) + continue; + VNInfo *SubBValNo = S.getVNInfoAt(CopyIdx); + assert(SubBValNo->def == CopyIdx); + S.MergeValueNumberInto(SubDVNI, SubBValNo); + } + ErasedInstrs.insert(UseMI); LIS->RemoveMachineInstrFromMaps(UseMI); UseMI->eraseFromParent(); @@ -712,24 +792,84 @@ bool RegisterCoalescer::removeCopyByCommutingDef(const CoalescerPair &CP, // Extend BValNo by merging in IntA live segments of AValNo. Val# definition // is updated. - VNInfo *ValNo = BValNo; - ValNo->def = AValNo->def; - for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); - AI != AE; ++AI) { - if (AI->valno != AValNo) continue; - IntB.addSegment(LiveInterval::Segment(AI->start, AI->end, ValNo)); + BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator(); + if (IntB.hasSubRanges()) { + if (!IntA.hasSubRanges()) { + LaneBitmask Mask = MRI->getMaxLaneMaskForVReg(IntA.reg); + IntA.createSubRangeFrom(Allocator, Mask, IntA); + } + SlotIndex AIdx = CopyIdx.getRegSlot(true); + for (LiveInterval::SubRange &SA : IntA.subranges()) { + VNInfo *ASubValNo = SA.getVNInfoAt(AIdx); + assert(ASubValNo != nullptr); + + LaneBitmask AMask = SA.LaneMask; + for (LiveInterval::SubRange &SB : IntB.subranges()) { + LaneBitmask BMask = SB.LaneMask; + LaneBitmask Common = BMask & AMask; + if (Common == 0) + continue; + + DEBUG( dbgs() << "\t\tCopy_Merge " << PrintLaneMask(BMask) + << " into " << PrintLaneMask(Common) << '\n'); + LaneBitmask BRest = BMask & ~AMask; + LiveInterval::SubRange *CommonRange; + if (BRest != 0) { + SB.LaneMask = BRest; + DEBUG(dbgs() << "\t\tReduce Lane to " << PrintLaneMask(BRest) + << '\n'); + // Duplicate SubRange for newly merged common stuff. + CommonRange = IntB.createSubRangeFrom(Allocator, Common, SB); + } else { + // We van reuse the L SubRange. + SB.LaneMask = Common; + CommonRange = &SB; + } + LiveRange RangeCopy(SB, Allocator); + + VNInfo *BSubValNo = CommonRange->getVNInfoAt(CopyIdx); + assert(BSubValNo->def == CopyIdx); + BSubValNo->def = ASubValNo->def; + addSegmentsWithValNo(*CommonRange, BSubValNo, SA, ASubValNo); + AMask &= ~BMask; + } + if (AMask != 0) { + DEBUG(dbgs() << "\t\tNew Lane " << PrintLaneMask(AMask) << '\n'); + LiveRange *NewRange = IntB.createSubRange(Allocator, AMask); + VNInfo *BSubValNo = NewRange->getNextValue(CopyIdx, Allocator); + addSegmentsWithValNo(*NewRange, BSubValNo, SA, ASubValNo); + } + } } + + BValNo->def = AValNo->def; + addSegmentsWithValNo(IntB, BValNo, IntA, AValNo); DEBUG(dbgs() << "\t\textended: " << IntB << '\n'); - IntA.removeValNo(AValNo); + LIS->removeVRegDefAt(IntA, AValNo->def); + DEBUG(dbgs() << "\t\ttrimmed: " << IntA << '\n'); ++numCommutes; return true; } -/// reMaterializeTrivialDef - If the source of a copy is defined by a trivial -/// computation, replace the copy by rematerialize the definition. -bool RegisterCoalescer::reMaterializeTrivialDef(CoalescerPair &CP, +/// Returns true if @p MI defines the full vreg @p Reg, as opposed to just +/// defining a subregister. +static bool definesFullReg(const MachineInstr &MI, unsigned Reg) { + assert(!TargetRegisterInfo::isPhysicalRegister(Reg) && + "This code cannot handle physreg aliasing"); + for (const MachineOperand &Op : MI.operands()) { + if (!Op.isReg() || !Op.isDef() || Op.getReg() != Reg) + continue; + // Return true if we define the full register or don't care about the value + // inside other subregisters. + if (Op.getSubReg() == 0 || Op.isUndef()) + return true; + } + return false; +} + +bool RegisterCoalescer::reMaterializeTrivialDef(const CoalescerPair &CP, MachineInstr *CopyMI, bool &IsDefCopy) { IsDefCopy = false; @@ -753,12 +893,14 @@ bool RegisterCoalescer::reMaterializeTrivialDef(CoalescerPair &CP, IsDefCopy = true; return false; } - if (!DefMI->isAsCheapAsAMove()) + if (!TII->isAsCheapAsAMove(DefMI)) return false; if (!TII->isTriviallyReMaterializable(DefMI, AA)) return false; + if (!definesFullReg(*DefMI, SrcReg)) + return false; bool SawStore = false; - if (!DefMI->isSafeToMove(TII, AA, SawStore)) + if (!DefMI->isSafeToMove(AA, SawStore)) return false; const MCInstrDesc &MCID = DefMI->getDesc(); if (MCID.getNumDefs() != 1) @@ -769,6 +911,14 @@ bool RegisterCoalescer::reMaterializeTrivialDef(CoalescerPair &CP, if (DstOperand.getSubReg() && !DstOperand.isUndef()) return false; + // If both SrcIdx and DstIdx are set, correct rematerialization would widen + // the register substantially (beyond both source and dest size). This is bad + // for performance since it can cascade through a function, introducing many + // extra spills and fills (e.g. ARM can easily end up copying QQQQPR registers + // around after a few subreg copies). + if (SrcIdx && DstIdx) + return false; + const TargetRegisterClass *DefRC = TII->getRegClass(MCID, 0, TRI, *MF); if (!DefMI->isImplicitDef()) { if (TargetRegisterInfo::isPhysicalRegister(DstReg)) { @@ -793,9 +943,31 @@ bool RegisterCoalescer::reMaterializeTrivialDef(CoalescerPair &CP, MachineBasicBlock *MBB = CopyMI->getParent(); MachineBasicBlock::iterator MII = - llvm::next(MachineBasicBlock::iterator(CopyMI)); + std::next(MachineBasicBlock::iterator(CopyMI)); TII->reMaterialize(*MBB, MII, DstReg, SrcIdx, DefMI, *TRI); - MachineInstr *NewMI = prior(MII); + MachineInstr *NewMI = std::prev(MII); + + // In a situation like the following: + // %vreg0:subreg = instr ; DefMI, subreg = DstIdx + // %vreg1 = copy %vreg0:subreg ; CopyMI, SrcIdx = 0 + // instead of widening %vreg1 to the register class of %vreg0 simply do: + // %vreg1 = instr + const TargetRegisterClass *NewRC = CP.getNewRC(); + if (DstIdx != 0) { + MachineOperand &DefMO = NewMI->getOperand(0); + if (DefMO.getSubReg() == DstIdx) { + assert(SrcIdx == 0 && CP.isFlipped() + && "Shouldn't have SrcIdx+DstIdx at this point"); + const TargetRegisterClass *DstRC = MRI->getRegClass(DstReg); + const TargetRegisterClass *CommonRC = + TRI->getCommonSubClass(DefRC, DstRC); + if (CommonRC != nullptr) { + NewRC = CommonRC; + DstIdx = 0; + DefMO.setSubReg(0); + } + } + } LIS->ReplaceMachineInstrInMaps(CopyMI, NewMI); CopyMI->eraseFromParent(); @@ -808,17 +980,25 @@ bool RegisterCoalescer::reMaterializeTrivialDef(CoalescerPair &CP, for (unsigned i = NewMI->getDesc().getNumOperands(), e = NewMI->getNumOperands(); i != e; ++i) { MachineOperand &MO = NewMI->getOperand(i); - if (MO.isReg()) { - assert(MO.isDef() && MO.isImplicit() && MO.isDead() && + if (MO.isReg() && MO.isDef()) { + assert(MO.isImplicit() && MO.isDead() && TargetRegisterInfo::isPhysicalRegister(MO.getReg())); NewMIImplDefs.push_back(MO.getReg()); } } if (TargetRegisterInfo::isVirtualRegister(DstReg)) { - MRI->setRegClass(DstReg, CP.getNewRC()); - unsigned NewIdx = NewMI->getOperand(0).getSubReg(); + + if (DefRC != nullptr) { + if (NewIdx) + NewRC = TRI->getMatchingSuperRegClass(NewRC, DefRC, NewIdx); + else + NewRC = TRI->getCommonSubClass(NewRC, DefRC); + assert(NewRC && "subreg chosen for remat incompatible with instruction"); + } + MRI->setRegClass(DstReg, NewRC); + updateRegDefsUses(DstReg, DstReg, DstIdx); NewMI->getOperand(0).setSubReg(NewIdx); } else if (NewMI->getOperand(0).getReg() != CopyDstReg) { @@ -831,6 +1011,27 @@ bool RegisterCoalescer::reMaterializeTrivialDef(CoalescerPair &CP, true /*IsDef*/, true /*IsImp*/, false /*IsKill*/)); + // Record small dead def live-ranges for all the subregisters + // of the destination register. + // Otherwise, variables that live through may miss some + // interferences, thus creating invalid allocation. + // E.g., i386 code: + // vreg1 = somedef ; vreg1 GR8 + // vreg2 = remat ; vreg2 GR32 + // CL = COPY vreg2.sub_8bit + // = somedef vreg1 ; vreg1 GR8 + // => + // vreg1 = somedef ; vreg1 GR8 + // ECX = remat ; CL + // = somedef vreg1 ; vreg1 GR8 + // vreg1 will see the inteferences with CL but not with CH since + // no live-ranges would have been created for ECX. + // Fix that! + SlotIndex NewMIIdx = LIS->getInstructionIndex(NewMI); + for (MCRegUnitIterator Units(NewMI->getOperand(0).getReg(), TRI); + Units.isValid(); ++Units) + if (LiveRange *LR = LIS->getCachedRegUnit(*Units)) + LR->createDeadDef(NewMIIdx.getRegSlot(), LIS->getVNInfoAllocator()); } if (NewMI->getOperand(0).getSubReg()) @@ -862,81 +1063,127 @@ bool RegisterCoalescer::reMaterializeTrivialDef(CoalescerPair &CP, ++NumReMats; // The source interval can become smaller because we removed a use. - LIS->shrinkToUses(&SrcInt, &DeadDefs); - if (!DeadDefs.empty()) + shrinkToUses(&SrcInt, &DeadDefs); + if (!DeadDefs.empty()) { + // If the virtual SrcReg is completely eliminated, update all DBG_VALUEs + // to describe DstReg instead. + for (MachineOperand &UseMO : MRI->use_operands(SrcReg)) { + MachineInstr *UseMI = UseMO.getParent(); + if (UseMI->isDebugValue()) { + UseMO.setReg(DstReg); + DEBUG(dbgs() << "\t\tupdated: " << *UseMI); + } + } eliminateDeadDefs(); + } return true; } -/// eliminateUndefCopy - ProcessImpicitDefs may leave some copies of -/// values, it only removes local variables. When we have a copy like: -/// -/// %vreg1 = COPY %vreg2 -/// -/// We delete the copy and remove the corresponding value number from %vreg1. -/// Any uses of that value number are marked as . -bool RegisterCoalescer::eliminateUndefCopy(MachineInstr *CopyMI, - const CoalescerPair &CP) { +bool RegisterCoalescer::eliminateUndefCopy(MachineInstr *CopyMI) { + // ProcessImpicitDefs may leave some copies of values, it only removes + // local variables. When we have a copy like: + // + // %vreg1 = COPY %vreg2 + // + // We delete the copy and remove the corresponding value number from %vreg1. + // Any uses of that value number are marked as . + + // Note that we do not query CoalescerPair here but redo isMoveInstr as the + // CoalescerPair may have a new register class with adjusted subreg indices + // at this point. + unsigned SrcReg, DstReg, SrcSubIdx, DstSubIdx; + isMoveInstr(*TRI, CopyMI, SrcReg, DstReg, SrcSubIdx, DstSubIdx); + SlotIndex Idx = LIS->getInstructionIndex(CopyMI); - LiveInterval *SrcInt = &LIS->getInterval(CP.getSrcReg()); - if (SrcInt->liveAt(Idx)) - return false; - LiveInterval *DstInt = &LIS->getInterval(CP.getDstReg()); - if (DstInt->liveAt(Idx)) + const LiveInterval &SrcLI = LIS->getInterval(SrcReg); + // CopyMI is undef iff SrcReg is not live before the instruction. + if (SrcSubIdx != 0 && SrcLI.hasSubRanges()) { + LaneBitmask SrcMask = TRI->getSubRegIndexLaneMask(SrcSubIdx); + for (const LiveInterval::SubRange &SR : SrcLI.subranges()) { + if ((SR.LaneMask & SrcMask) == 0) + continue; + if (SR.liveAt(Idx)) + return false; + } + } else if (SrcLI.liveAt(Idx)) return false; - // No intervals are live-in to CopyMI - it is undef. - if (CP.isFlipped()) - DstInt = SrcInt; - SrcInt = 0; - - VNInfo *DeadVNI = DstInt->getVNInfoAt(Idx.getRegSlot()); - assert(DeadVNI && "No value defined in DstInt"); - DstInt->removeValNo(DeadVNI); - - // Find new undef uses. - for (MachineRegisterInfo::reg_nodbg_iterator - I = MRI->reg_nodbg_begin(DstInt->reg), E = MRI->reg_nodbg_end(); - I != E; ++I) { - MachineOperand &MO = I.getOperand(); - if (MO.isDef() || MO.isUndef()) + DEBUG(dbgs() << "\tEliminating copy of value\n"); + + // Remove any DstReg segments starting at the instruction. + LiveInterval &DstLI = LIS->getInterval(DstReg); + SlotIndex RegIndex = Idx.getRegSlot(); + // Remove value or merge with previous one in case of a subregister def. + if (VNInfo *PrevVNI = DstLI.getVNInfoAt(Idx)) { + VNInfo *VNI = DstLI.getVNInfoAt(RegIndex); + DstLI.MergeValueNumberInto(VNI, PrevVNI); + + // The affected subregister segments can be removed. + LaneBitmask DstMask = TRI->getSubRegIndexLaneMask(DstSubIdx); + for (LiveInterval::SubRange &SR : DstLI.subranges()) { + if ((SR.LaneMask & DstMask) == 0) + continue; + + VNInfo *SVNI = SR.getVNInfoAt(RegIndex); + assert(SVNI != nullptr && SlotIndex::isSameInstr(SVNI->def, RegIndex)); + SR.removeValNo(SVNI); + } + DstLI.removeEmptySubRanges(); + } else + LIS->removeVRegDefAt(DstLI, RegIndex); + + // Mark uses as undef. + for (MachineOperand &MO : MRI->reg_nodbg_operands(DstReg)) { + if (MO.isDef() /*|| MO.isUndef()*/) continue; - MachineInstr *MI = MO.getParent(); - SlotIndex Idx = LIS->getInstructionIndex(MI); - if (DstInt->liveAt(Idx)) + const MachineInstr &MI = *MO.getParent(); + SlotIndex UseIdx = LIS->getInstructionIndex(&MI); + LaneBitmask UseMask = TRI->getSubRegIndexLaneMask(MO.getSubReg()); + bool isLive; + if (UseMask != ~0u && DstLI.hasSubRanges()) { + isLive = false; + for (const LiveInterval::SubRange &SR : DstLI.subranges()) { + if ((SR.LaneMask & UseMask) == 0) + continue; + if (SR.liveAt(UseIdx)) { + isLive = true; + break; + } + } + } else + isLive = DstLI.liveAt(UseIdx); + if (isLive) continue; MO.setIsUndef(true); - DEBUG(dbgs() << "\tnew undef: " << Idx << '\t' << *MI); + DEBUG(dbgs() << "\tnew undef: " << UseIdx << '\t' << MI); } return true; } -/// updateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and -/// update the subregister number if it is not zero. If DstReg is a -/// physical register and the existing subregister number of the def / use -/// being updated is not zero, make sure to set it to the correct physical -/// subregister. void RegisterCoalescer::updateRegDefsUses(unsigned SrcReg, unsigned DstReg, unsigned SubIdx) { bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); - LiveInterval *DstInt = DstIsPhys ? 0 : &LIS->getInterval(DstReg); + LiveInterval *DstInt = DstIsPhys ? nullptr : &LIS->getInterval(DstReg); SmallPtrSet Visited; - for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(SrcReg); - MachineInstr *UseMI = I.skipInstruction();) { + for (MachineRegisterInfo::reg_instr_iterator + I = MRI->reg_instr_begin(SrcReg), E = MRI->reg_instr_end(); + I != E; ) { + MachineInstr *UseMI = &*(I++); + // Each instruction can only be rewritten once because sub-register // composition is not always idempotent. When SrcReg != DstReg, rewriting // the UseMI operands removes them from the SrcReg use-def chain, but when // SrcReg is DstReg we could encounter UseMI twice if it has multiple // operands mentioning the virtual register. - if (SrcReg == DstReg && !Visited.insert(UseMI)) + if (SrcReg == DstReg && !Visited.insert(UseMI).second) continue; SmallVector Ops; bool Reads, Writes; - tie(Reads, Writes) = UseMI->readsWritesVirtualRegister(SrcReg, &Ops); + std::tie(Reads, Writes) = UseMI->readsWritesVirtualRegister(SrcReg, &Ops); // If SrcReg wasn't read, it may still be the case that DstReg is live-in // because SrcReg is a sub-register. @@ -953,6 +1200,40 @@ void RegisterCoalescer::updateRegDefsUses(unsigned SrcReg, if (SubIdx && MO.isDef()) MO.setIsUndef(!Reads); + // A subreg use of a partially undef (super) register may be a complete + // undef use now and then has to be marked that way. + if (SubIdx != 0 && MO.isUse() && MRI->shouldTrackSubRegLiveness(DstReg)) { + if (!DstInt->hasSubRanges()) { + BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator(); + LaneBitmask Mask = MRI->getMaxLaneMaskForVReg(DstInt->reg); + DstInt->createSubRangeFrom(Allocator, Mask, *DstInt); + } + LaneBitmask Mask = TRI->getSubRegIndexLaneMask(SubIdx); + bool IsUndef = true; + SlotIndex MIIdx = UseMI->isDebugValue() + ? LIS->getSlotIndexes()->getIndexBefore(UseMI) + : LIS->getInstructionIndex(UseMI); + SlotIndex UseIdx = MIIdx.getRegSlot(true); + for (LiveInterval::SubRange &S : DstInt->subranges()) { + if ((S.LaneMask & Mask) == 0) + continue; + if (S.liveAt(UseIdx)) { + IsUndef = false; + break; + } + } + if (IsUndef) { + MO.setIsUndef(true); + // We found out some subregister use is actually reading an undefined + // value. In some cases the whole vreg has become undefined at this + // point so we have to potentially shrink the main range if the + // use was ending a live segment there. + LiveQueryResult Q = DstInt->Query(MIIdx); + if (Q.valueOut() == nullptr) + ShrinkMainRange = true; + } + } + if (DstIsPhys) MO.substPhysReg(DstReg, *TRI); else @@ -968,29 +1249,23 @@ void RegisterCoalescer::updateRegDefsUses(unsigned SrcReg, } } -/// canJoinPhys - Return true if a copy involving a physreg should be joined. bool RegisterCoalescer::canJoinPhys(const CoalescerPair &CP) { - /// Always join simple intervals that are defined by a single copy from a - /// reserved register. This doesn't increase register pressure, so it is - /// always beneficial. + // Always join simple intervals that are defined by a single copy from a + // reserved register. This doesn't increase register pressure, so it is + // always beneficial. if (!MRI->isReserved(CP.getDstReg())) { DEBUG(dbgs() << "\tCan only merge into reserved registers.\n"); return false; } LiveInterval &JoinVInt = LIS->getInterval(CP.getSrcReg()); - if (CP.isFlipped() && JoinVInt.containsOneValue()) + if (JoinVInt.containsOneValue()) return true; - DEBUG(dbgs() << "\tCannot join defs into reserved register.\n"); + DEBUG(dbgs() << "\tCannot join complex intervals into reserved register.\n"); return false; } -/// joinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, -/// which are the src/dst of the copy instruction CopyMI. This returns true -/// if the copy was successfully coalesced away. If it is not currently -/// possible to coalesce this interval, but it may be possible if other -/// things get coalesced, then it returns true by reference in 'Again'. bool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) { Again = false; @@ -1002,6 +1277,22 @@ bool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) { return false; } + if (CP.getNewRC()) { + auto SrcRC = MRI->getRegClass(CP.getSrcReg()); + auto DstRC = MRI->getRegClass(CP.getDstReg()); + unsigned SrcIdx = CP.getSrcIdx(); + unsigned DstIdx = CP.getDstIdx(); + if (CP.isFlipped()) { + std::swap(SrcIdx, DstIdx); + std::swap(SrcRC, DstRC); + } + if (!TRI->shouldCoalesce(CopyMI, SrcRC, SrcIdx, DstRC, DstIdx, + CP.getNewRC())) { + DEBUG(dbgs() << "\tSubtarget bailed on coalescing.\n"); + return false; + } + } + // Dead code elimination. This really should be handled by MachineDCE, but // sometimes dead copies slip through, and we can't generate invalid live // ranges. @@ -1013,8 +1304,7 @@ bool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) { } // Eliminate undefs. - if (!CP.isPhys() && eliminateUndefCopy(CopyMI, CP)) { - DEBUG(dbgs() << "\tEliminated copy of value.\n"); + if (!CP.isPhys() && eliminateUndefCopy(CopyMI)) { LIS->RemoveMachineInstrFromMaps(CopyMI); CopyMI->eraseFromParent(); return false; // Not coalescable. @@ -1026,12 +1316,22 @@ bool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) { if (CP.getSrcReg() == CP.getDstReg()) { LiveInterval &LI = LIS->getInterval(CP.getSrcReg()); DEBUG(dbgs() << "\tCopy already coalesced: " << LI << '\n'); - LiveQueryResult LRQ = LI.Query(LIS->getInstructionIndex(CopyMI)); + const SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI); + LiveQueryResult LRQ = LI.Query(CopyIdx); if (VNInfo *DefVNI = LRQ.valueDefined()) { VNInfo *ReadVNI = LRQ.valueIn(); assert(ReadVNI && "No value before copy and no flag."); assert(ReadVNI != DefVNI && "Cannot read and define the same value."); LI.MergeValueNumberInto(DefVNI, ReadVNI); + + // Process subregister liveranges. + for (LiveInterval::SubRange &S : LI.subranges()) { + LiveQueryResult SLRQ = S.Query(CopyIdx); + if (VNInfo *SDefVNI = SLRQ.valueDefined()) { + VNInfo *SReadVNI = SLRQ.valueIn(); + S.MergeValueNumberInto(SDefVNI, SReadVNI); + } + } DEBUG(dbgs() << "\tMerged values: " << LI << '\n'); } LIS->RemoveMachineInstrFromMaps(CopyMI); @@ -1055,9 +1355,14 @@ bool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) { return false; } } else { + // When possible, let DstReg be the larger interval. + if (!CP.isPartial() && LIS->getInterval(CP.getSrcReg()).size() > + LIS->getInterval(CP.getDstReg()).size()) + CP.flip(); + DEBUG({ - dbgs() << "\tConsidering merging to " << CP.getNewRC()->getName() - << " with "; + dbgs() << "\tConsidering merging to " + << TRI->getRegClassName(CP.getNewRC()) << " with "; if (CP.getDstIdx() && CP.getSrcIdx()) dbgs() << PrintReg(CP.getDstReg()) << " in " << TRI->getSubRegIndexName(CP.getDstIdx()) << " and " @@ -1067,13 +1372,11 @@ bool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) { dbgs() << PrintReg(CP.getSrcReg(), TRI) << " in " << PrintReg(CP.getDstReg(), TRI, CP.getSrcIdx()) << '\n'; }); - - // When possible, let DstReg be the larger interval. - if (!CP.isPartial() && LIS->getInterval(CP.getSrcReg()).size() > - LIS->getInterval(CP.getDstReg()).size()) - CP.flip(); } + ShrinkMask = 0; + ShrinkMainRange = false; + // Okay, attempt to join these two intervals. On failure, this returns false. // Otherwise, if one of the intervals being joined is a physreg, this method // always canonicalizes DstInt to be it. The output "SrcInt" will not have @@ -1128,15 +1431,34 @@ bool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) { updateRegDefsUses(CP.getDstReg(), CP.getDstReg(), CP.getDstIdx()); updateRegDefsUses(CP.getSrcReg(), CP.getDstReg(), CP.getSrcIdx()); + // Shrink subregister ranges if necessary. + if (ShrinkMask != 0) { + LiveInterval &LI = LIS->getInterval(CP.getDstReg()); + for (LiveInterval::SubRange &S : LI.subranges()) { + if ((S.LaneMask & ShrinkMask) == 0) + continue; + DEBUG(dbgs() << "Shrink LaneUses (Lane " << PrintLaneMask(S.LaneMask) + << ")\n"); + LIS->shrinkToUses(S, LI.reg); + } + LI.removeEmptySubRanges(); + } + if (ShrinkMainRange) { + LiveInterval &LI = LIS->getInterval(CP.getDstReg()); + shrinkToUses(&LI); + } + // SrcReg is guaranteed to be the register whose live interval that is // being merged. LIS->removeInterval(CP.getSrcReg()); // Update regalloc hint. - TRI->UpdateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *MF); + TRI->updateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *MF); DEBUG({ - dbgs() << "\tJoined. Result = "; + dbgs() << "\tSuccess: " << PrintReg(CP.getSrcReg(), TRI, CP.getSrcIdx()) + << " -> " << PrintReg(CP.getDstReg(), TRI, CP.getDstIdx()) << '\n'; + dbgs() << "\tResult = "; if (CP.isPhys()) dbgs() << PrintReg(CP.getDstReg(), TRI); else @@ -1148,24 +1470,23 @@ bool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) { return true; } -/// Attempt joining with a reserved physreg. bool RegisterCoalescer::joinReservedPhysReg(CoalescerPair &CP) { + unsigned DstReg = CP.getDstReg(); assert(CP.isPhys() && "Must be a physreg copy"); - assert(MRI->isReserved(CP.getDstReg()) && "Not a reserved register"); + assert(MRI->isReserved(DstReg) && "Not a reserved register"); LiveInterval &RHS = LIS->getInterval(CP.getSrcReg()); DEBUG(dbgs() << "\t\tRHS = " << RHS << '\n'); - assert(CP.isFlipped() && RHS.containsOneValue() && - "Invalid join with reserved register"); + assert(RHS.containsOneValue() && "Invalid join with reserved register"); // Optimization for reserved registers like ESP. We can only merge with a - // reserved physreg if RHS has a single value that is a copy of CP.DstReg(). + // reserved physreg if RHS has a single value that is a copy of DstReg. // The live range of the reserved register will look like a set of dead defs // - we don't properly track the live range of reserved registers. // Deny any overlapping intervals. This depends on all the reserved // register live ranges to look like dead defs. - for (MCRegUnitIterator UI(CP.getDstReg(), TRI); UI.isValid(); ++UI) + for (MCRegUnitIterator UI(DstReg, TRI); UI.isValid(); ++UI) if (RHS.overlaps(LIS->getRegUnit(*UI))) { DEBUG(dbgs() << "\t\tInterference: " << PrintRegUnit(*UI, TRI) << '\n'); return false; @@ -1177,7 +1498,54 @@ bool RegisterCoalescer::joinReservedPhysReg(CoalescerPair &CP) { // defs are there. // Delete the identity copy. - MachineInstr *CopyMI = MRI->getVRegDef(RHS.reg); + MachineInstr *CopyMI; + if (CP.isFlipped()) { + CopyMI = MRI->getVRegDef(RHS.reg); + } else { + if (!MRI->hasOneNonDBGUse(RHS.reg)) { + DEBUG(dbgs() << "\t\tMultiple vreg uses!\n"); + return false; + } + + MachineInstr *DestMI = MRI->getVRegDef(RHS.reg); + CopyMI = &*MRI->use_instr_nodbg_begin(RHS.reg); + const SlotIndex CopyRegIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(); + const SlotIndex DestRegIdx = LIS->getInstructionIndex(DestMI).getRegSlot(); + + // We checked above that there are no interfering defs of the physical + // register. However, for this case, where we intent to move up the def of + // the physical register, we also need to check for interfering uses. + SlotIndexes *Indexes = LIS->getSlotIndexes(); + for (SlotIndex SI = Indexes->getNextNonNullIndex(DestRegIdx); + SI != CopyRegIdx; SI = Indexes->getNextNonNullIndex(SI)) { + MachineInstr *MI = LIS->getInstructionFromIndex(SI); + if (MI->readsRegister(DstReg, TRI)) { + DEBUG(dbgs() << "\t\tInterference (read): " << *MI); + return false; + } + + // We must also check for clobbers caused by regmasks. + for (const auto &MO : MI->operands()) { + if (MO.isRegMask() && MO.clobbersPhysReg(DstReg)) { + DEBUG(dbgs() << "\t\tInterference (regmask clobber): " << *MI); + return false; + } + } + } + + // We're going to remove the copy which defines a physical reserved + // register, so remove its valno, etc. + DEBUG(dbgs() << "\t\tRemoving phys reg def of " << DstReg << " at " + << CopyRegIdx << "\n"); + + LIS->removePhysRegDefAt(DstReg, CopyRegIdx); + // Create a new dead def at the new def location. + for (MCRegUnitIterator UI(DstReg, TRI); UI.isValid(); ++UI) { + LiveRange &LR = LIS->getRegUnit(*UI); + LR.createDeadDef(DestRegIdx, LIS->getVNInfoAllocator()); + } + } + LIS->RemoveMachineInstrFromMaps(CopyMI); CopyMI->eraseFromParent(); @@ -1254,15 +1622,29 @@ bool RegisterCoalescer::joinReservedPhysReg(CoalescerPair &CP) { namespace { /// Track information about values in a single virtual register about to be /// joined. Objects of this class are always created in pairs - one for each -/// side of the CoalescerPair. +/// side of the CoalescerPair (or one for each lane of a side of the coalescer +/// pair) class JoinVals { - LiveInterval &LI; - - // Location of this register in the final joined register. - // Either CP.DstIdx or CP.SrcIdx. - unsigned SubIdx; - - // Values that will be present in the final live range. + /// Live range we work on. + LiveRange &LR; + /// (Main) register we work on. + const unsigned Reg; + + /// Reg (and therefore the values in this liverange) will end up as + /// subregister SubIdx in the coalesced register. Either CP.DstIdx or + /// CP.SrcIdx. + const unsigned SubIdx; + /// The LaneMask that this liverange will occupy the coalesced register. May + /// be smaller than the lanemask produced by SubIdx when merging subranges. + const LaneBitmask LaneMask; + + /// This is true when joining sub register ranges, false when joining main + /// ranges. + const bool SubRangeJoin; + /// Whether the current LiveInterval tracks subregister liveness. + const bool TrackSubRegLiveness; + + /// Values that will be present in the final live range. SmallVectorImpl &NewVNInfo; const CoalescerPair &CP; @@ -1270,108 +1652,153 @@ class JoinVals { SlotIndexes *Indexes; const TargetRegisterInfo *TRI; - // Value number assignments. Maps value numbers in LI to entries in NewVNInfo. - // This is suitable for passing to LiveInterval::join(). + /// Value number assignments. Maps value numbers in LI to entries in + /// NewVNInfo. This is suitable for passing to LiveInterval::join(). SmallVector Assignments; - // Conflict resolution for overlapping values. + /// Conflict resolution for overlapping values. enum ConflictResolution { - // No overlap, simply keep this value. + /// No overlap, simply keep this value. CR_Keep, - // Merge this value into OtherVNI and erase the defining instruction. - // Used for IMPLICIT_DEF, coalescable copies, and copies from external - // values. + /// Merge this value into OtherVNI and erase the defining instruction. + /// Used for IMPLICIT_DEF, coalescable copies, and copies from external + /// values. CR_Erase, - // Merge this value into OtherVNI but keep the defining instruction. - // This is for the special case where OtherVNI is defined by the same - // instruction. + /// Merge this value into OtherVNI but keep the defining instruction. + /// This is for the special case where OtherVNI is defined by the same + /// instruction. CR_Merge, - // Keep this value, and have it replace OtherVNI where possible. This - // complicates value mapping since OtherVNI maps to two different values - // before and after this def. - // Used when clobbering undefined or dead lanes. + /// Keep this value, and have it replace OtherVNI where possible. This + /// complicates value mapping since OtherVNI maps to two different values + /// before and after this def. + /// Used when clobbering undefined or dead lanes. CR_Replace, - // Unresolved conflict. Visit later when all values have been mapped. + /// Unresolved conflict. Visit later when all values have been mapped. CR_Unresolved, - // Unresolvable conflict. Abort the join. + /// Unresolvable conflict. Abort the join. CR_Impossible }; - // Per-value info for LI. The lane bit masks are all relative to the final - // joined register, so they can be compared directly between SrcReg and - // DstReg. + /// Per-value info for LI. The lane bit masks are all relative to the final + /// joined register, so they can be compared directly between SrcReg and + /// DstReg. struct Val { ConflictResolution Resolution; - // Lanes written by this def, 0 for unanalyzed values. - unsigned WriteLanes; + /// Lanes written by this def, 0 for unanalyzed values. + LaneBitmask WriteLanes; - // Lanes with defined values in this register. Other lanes are undef and - // safe to clobber. - unsigned ValidLanes; + /// Lanes with defined values in this register. Other lanes are undef and + /// safe to clobber. + LaneBitmask ValidLanes; - // Value in LI being redefined by this def. + /// Value in LI being redefined by this def. VNInfo *RedefVNI; - // Value in the other live range that overlaps this def, if any. + /// Value in the other live range that overlaps this def, if any. VNInfo *OtherVNI; - // Is this value an IMPLICIT_DEF that can be erased? - // - // IMPLICIT_DEF values should only exist at the end of a basic block that - // is a predecessor to a phi-value. These IMPLICIT_DEF instructions can be - // safely erased if they are overlapping a live value in the other live - // interval. - // - // Weird control flow graphs and incomplete PHI handling in - // ProcessImplicitDefs can very rarely create IMPLICIT_DEF values with - // longer live ranges. Such IMPLICIT_DEF values should be treated like - // normal values. + /// Is this value an IMPLICIT_DEF that can be erased? + /// + /// IMPLICIT_DEF values should only exist at the end of a basic block that + /// is a predecessor to a phi-value. These IMPLICIT_DEF instructions can be + /// safely erased if they are overlapping a live value in the other live + /// interval. + /// + /// Weird control flow graphs and incomplete PHI handling in + /// ProcessImplicitDefs can very rarely create IMPLICIT_DEF values with + /// longer live ranges. Such IMPLICIT_DEF values should be treated like + /// normal values. bool ErasableImplicitDef; - // True when the live range of this value will be pruned because of an - // overlapping CR_Replace value in the other live range. + /// True when the live range of this value will be pruned because of an + /// overlapping CR_Replace value in the other live range. bool Pruned; - // True once Pruned above has been computed. + /// True once Pruned above has been computed. bool PrunedComputed; Val() : Resolution(CR_Keep), WriteLanes(0), ValidLanes(0), - RedefVNI(0), OtherVNI(0), ErasableImplicitDef(false), + RedefVNI(nullptr), OtherVNI(nullptr), ErasableImplicitDef(false), Pruned(false), PrunedComputed(false) {} bool isAnalyzed() const { return WriteLanes != 0; } }; - // One entry per value number in LI. + /// One entry per value number in LI. SmallVector Vals; - unsigned computeWriteLanes(const MachineInstr *DefMI, bool &Redef); - VNInfo *stripCopies(VNInfo *VNI); + /// Compute the bitmask of lanes actually written by DefMI. + /// Set Redef if there are any partial register definitions that depend on the + /// previous value of the register. + LaneBitmask computeWriteLanes(const MachineInstr *DefMI, bool &Redef) const; + + /// Find the ultimate value that VNI was copied from. + std::pair followCopyChain(const VNInfo *VNI) const; + + bool valuesIdentical(VNInfo *Val0, VNInfo *Val1, const JoinVals &Other) const; + + /// Analyze ValNo in this live range, and set all fields of Vals[ValNo]. + /// Return a conflict resolution when possible, but leave the hard cases as + /// CR_Unresolved. + /// Recursively calls computeAssignment() on this and Other, guaranteeing that + /// both OtherVNI and RedefVNI have been analyzed and mapped before returning. + /// The recursion always goes upwards in the dominator tree, making loops + /// impossible. ConflictResolution analyzeValue(unsigned ValNo, JoinVals &Other); + + /// Compute the value assignment for ValNo in RI. + /// This may be called recursively by analyzeValue(), but never for a ValNo on + /// the stack. void computeAssignment(unsigned ValNo, JoinVals &Other); - bool taintExtent(unsigned, unsigned, JoinVals&, - SmallVectorImpl >&); - bool usesLanes(MachineInstr *MI, unsigned, unsigned, unsigned); + + /// Assuming ValNo is going to clobber some valid lanes in Other.LR, compute + /// the extent of the tainted lanes in the block. + /// + /// Multiple values in Other.LR can be affected since partial redefinitions + /// can preserve previously tainted lanes. + /// + /// 1 %dst = VLOAD <-- Define all lanes in %dst + /// 2 %src = FOO <-- ValNo to be joined with %dst:ssub0 + /// 3 %dst:ssub1 = BAR <-- Partial redef doesn't clear taint in ssub0 + /// 4 %dst:ssub0 = COPY %src <-- Conflict resolved, ssub0 wasn't read + /// + /// For each ValNo in Other that is affected, add an (EndIndex, TaintedLanes) + /// entry to TaintedVals. + /// + /// Returns false if the tainted lanes extend beyond the basic block. + bool taintExtent(unsigned, LaneBitmask, JoinVals&, + SmallVectorImpl >&); + + /// Return true if MI uses any of the given Lanes from Reg. + /// This does not include partial redefinitions of Reg. + bool usesLanes(const MachineInstr *MI, unsigned, unsigned, LaneBitmask) const; + + /// Determine if ValNo is a copy of a value number in LR or Other.LR that will + /// be pruned: + /// + /// %dst = COPY %src + /// %src = COPY %dst <-- This value to be pruned. + /// %dst = COPY %src <-- This value is a copy of a pruned value. bool isPrunedValue(unsigned ValNo, JoinVals &Other); public: - JoinVals(LiveInterval &li, unsigned subIdx, - SmallVectorImpl &newVNInfo, - const CoalescerPair &cp, - LiveIntervals *lis, - const TargetRegisterInfo *tri) - : LI(li), SubIdx(subIdx), NewVNInfo(newVNInfo), CP(cp), LIS(lis), - Indexes(LIS->getSlotIndexes()), TRI(tri), - Assignments(LI.getNumValNums(), -1), Vals(LI.getNumValNums()) + JoinVals(LiveRange &LR, unsigned Reg, unsigned SubIdx, LaneBitmask LaneMask, + SmallVectorImpl &newVNInfo, const CoalescerPair &cp, + LiveIntervals *lis, const TargetRegisterInfo *TRI, bool SubRangeJoin, + bool TrackSubRegLiveness) + : LR(LR), Reg(Reg), SubIdx(SubIdx), LaneMask(LaneMask), + SubRangeJoin(SubRangeJoin), TrackSubRegLiveness(TrackSubRegLiveness), + NewVNInfo(newVNInfo), CP(cp), LIS(lis), Indexes(LIS->getSlotIndexes()), + TRI(TRI), Assignments(LR.getNumValNums(), -1), Vals(LR.getNumValNums()) {} - /// Analyze defs in LI and compute a value mapping in NewVNInfo. + /// Analyze defs in LR and compute a value mapping in NewVNInfo. /// Returns false if any conflicts were impossible to resolve. bool mapValues(JoinVals &Other); @@ -1379,118 +1806,174 @@ public: /// Returns false if any conflicts were impossible to resolve. bool resolveConflicts(JoinVals &Other); - /// Prune the live range of values in Other.LI where they would conflict with - /// CR_Replace values in LI. Collect end points for restoring the live range + /// Prune the live range of values in Other.LR where they would conflict with + /// CR_Replace values in LR. Collect end points for restoring the live range /// after joining. - void pruneValues(JoinVals &Other, SmallVectorImpl &EndPoints); + void pruneValues(JoinVals &Other, SmallVectorImpl &EndPoints, + bool changeInstrs); + + /// Removes subranges starting at copies that get removed. This sometimes + /// happens when undefined subranges are copied around. These ranges contain + /// no useful information and can be removed. + void pruneSubRegValues(LiveInterval &LI, LaneBitmask &ShrinkMask); /// Erase any machine instructions that have been coalesced away. /// Add erased instructions to ErasedInstrs. /// Add foreign virtual registers to ShrinkRegs if their live range ended at /// the erased instrs. - void eraseInstrs(SmallPtrSet &ErasedInstrs, + void eraseInstrs(SmallPtrSetImpl &ErasedInstrs, SmallVectorImpl &ShrinkRegs); + /// Remove liverange defs at places where implicit defs will be removed. + void removeImplicitDefs(); + /// Get the value assignments suitable for passing to LiveInterval::join. const int *getAssignments() const { return Assignments.data(); } }; } // end anonymous namespace -/// Compute the bitmask of lanes actually written by DefMI. -/// Set Redef if there are any partial register definitions that depend on the -/// previous value of the register. -unsigned JoinVals::computeWriteLanes(const MachineInstr *DefMI, bool &Redef) { - unsigned L = 0; - for (ConstMIOperands MO(DefMI); MO.isValid(); ++MO) { - if (!MO->isReg() || MO->getReg() != LI.reg || !MO->isDef()) +LaneBitmask JoinVals::computeWriteLanes(const MachineInstr *DefMI, bool &Redef) + const { + LaneBitmask L = 0; + for (const MachineOperand &MO : DefMI->operands()) { + if (!MO.isReg() || MO.getReg() != Reg || !MO.isDef()) continue; L |= TRI->getSubRegIndexLaneMask( - TRI->composeSubRegIndices(SubIdx, MO->getSubReg())); - if (MO->readsReg()) + TRI->composeSubRegIndices(SubIdx, MO.getSubReg())); + if (MO.readsReg()) Redef = true; } return L; } -/// Find the ultimate value that VNI was copied from. -VNInfo *JoinVals::stripCopies(VNInfo *VNI) { +std::pair JoinVals::followCopyChain( + const VNInfo *VNI) const { + unsigned Reg = this->Reg; + while (!VNI->isPHIDef()) { - MachineInstr *MI = Indexes->getInstructionFromIndex(VNI->def); + SlotIndex Def = VNI->def; + MachineInstr *MI = Indexes->getInstructionFromIndex(Def); assert(MI && "No defining instruction"); if (!MI->isFullCopy()) + return std::make_pair(VNI, Reg); + unsigned SrcReg = MI->getOperand(1).getReg(); + if (!TargetRegisterInfo::isVirtualRegister(SrcReg)) + return std::make_pair(VNI, Reg); + + const LiveInterval &LI = LIS->getInterval(SrcReg); + const VNInfo *ValueIn; + // No subrange involved. + if (!SubRangeJoin || !LI.hasSubRanges()) { + LiveQueryResult LRQ = LI.Query(Def); + ValueIn = LRQ.valueIn(); + } else { + // Query subranges. Pick the first matching one. + ValueIn = nullptr; + for (const LiveInterval::SubRange &S : LI.subranges()) { + // Transform lanemask to a mask in the joined live interval. + LaneBitmask SMask = TRI->composeSubRegIndexLaneMask(SubIdx, S.LaneMask); + if ((SMask & LaneMask) == 0) + continue; + LiveQueryResult LRQ = S.Query(Def); + ValueIn = LRQ.valueIn(); + break; + } + } + if (ValueIn == nullptr) break; - unsigned Reg = MI->getOperand(1).getReg(); - if (!TargetRegisterInfo::isVirtualRegister(Reg)) - break; - LiveQueryResult LRQ = LIS->getInterval(Reg).Query(VNI->def); - if (!LRQ.valueIn()) - break; - VNI = LRQ.valueIn(); + VNI = ValueIn; + Reg = SrcReg; } - return VNI; + return std::make_pair(VNI, Reg); +} + +bool JoinVals::valuesIdentical(VNInfo *Value0, VNInfo *Value1, + const JoinVals &Other) const { + const VNInfo *Orig0; + unsigned Reg0; + std::tie(Orig0, Reg0) = followCopyChain(Value0); + if (Orig0 == Value1) + return true; + + const VNInfo *Orig1; + unsigned Reg1; + std::tie(Orig1, Reg1) = Other.followCopyChain(Value1); + + // The values are equal if they are defined at the same place and use the + // same register. Note that we cannot compare VNInfos directly as some of + // them might be from a copy created in mergeSubRangeInto() while the other + // is from the original LiveInterval. + return Orig0->def == Orig1->def && Reg0 == Reg1; } -/// Analyze ValNo in this live range, and set all fields of Vals[ValNo]. -/// Return a conflict resolution when possible, but leave the hard cases as -/// CR_Unresolved. -/// Recursively calls computeAssignment() on this and Other, guaranteeing that -/// both OtherVNI and RedefVNI have been analyzed and mapped before returning. -/// The recursion always goes upwards in the dominator tree, making loops -/// impossible. JoinVals::ConflictResolution JoinVals::analyzeValue(unsigned ValNo, JoinVals &Other) { Val &V = Vals[ValNo]; assert(!V.isAnalyzed() && "Value has already been analyzed!"); - VNInfo *VNI = LI.getValNumInfo(ValNo); + VNInfo *VNI = LR.getValNumInfo(ValNo); if (VNI->isUnused()) { V.WriteLanes = ~0u; return CR_Keep; } // Get the instruction defining this value, compute the lanes written. - const MachineInstr *DefMI = 0; + const MachineInstr *DefMI = nullptr; if (VNI->isPHIDef()) { // Conservatively assume that all lanes in a PHI are valid. - V.ValidLanes = V.WriteLanes = TRI->getSubRegIndexLaneMask(SubIdx); + LaneBitmask Lanes = SubRangeJoin ? 1 : TRI->getSubRegIndexLaneMask(SubIdx); + V.ValidLanes = V.WriteLanes = Lanes; } else { DefMI = Indexes->getInstructionFromIndex(VNI->def); - bool Redef = false; - V.ValidLanes = V.WriteLanes = computeWriteLanes(DefMI, Redef); - - // If this is a read-modify-write instruction, there may be more valid - // lanes than the ones written by this instruction. - // This only covers partial redef operands. DefMI may have normal use - // operands reading the register. They don't contribute valid lanes. - // - // This adds ssub1 to the set of valid lanes in %src: - // - // %src:ssub1 = FOO - // - // This leaves only ssub1 valid, making any other lanes undef: - // - // %src:ssub1 = FOO %src:ssub2 - // - // The flag on the def operand means that old lane values are - // not important. - if (Redef) { - V.RedefVNI = LI.Query(VNI->def).valueIn(); - assert(V.RedefVNI && "Instruction is reading nonexistent value"); - computeAssignment(V.RedefVNI->id, Other); - V.ValidLanes |= Vals[V.RedefVNI->id].ValidLanes; - } + assert(DefMI != nullptr); + if (SubRangeJoin) { + // We don't care about the lanes when joining subregister ranges. + V.WriteLanes = V.ValidLanes = 1; + if (DefMI->isImplicitDef()) { + V.ValidLanes = 0; + V.ErasableImplicitDef = true; + } + } else { + bool Redef = false; + V.ValidLanes = V.WriteLanes = computeWriteLanes(DefMI, Redef); + + // If this is a read-modify-write instruction, there may be more valid + // lanes than the ones written by this instruction. + // This only covers partial redef operands. DefMI may have normal use + // operands reading the register. They don't contribute valid lanes. + // + // This adds ssub1 to the set of valid lanes in %src: + // + // %src:ssub1 = FOO + // + // This leaves only ssub1 valid, making any other lanes undef: + // + // %src:ssub1 = FOO %src:ssub2 + // + // The flag on the def operand means that old lane values are + // not important. + if (Redef) { + V.RedefVNI = LR.Query(VNI->def).valueIn(); + assert((TrackSubRegLiveness || V.RedefVNI) && + "Instruction is reading nonexistent value"); + if (V.RedefVNI != nullptr) { + computeAssignment(V.RedefVNI->id, Other); + V.ValidLanes |= Vals[V.RedefVNI->id].ValidLanes; + } + } - // An IMPLICIT_DEF writes undef values. - if (DefMI->isImplicitDef()) { - // We normally expect IMPLICIT_DEF values to be live only until the end - // of their block. If the value is really live longer and gets pruned in - // another block, this flag is cleared again. - V.ErasableImplicitDef = true; - V.ValidLanes &= ~V.WriteLanes; + // An IMPLICIT_DEF writes undef values. + if (DefMI->isImplicitDef()) { + // We normally expect IMPLICIT_DEF values to be live only until the end + // of their block. If the value is really live longer and gets pruned in + // another block, this flag is cleared again. + V.ErasableImplicitDef = true; + V.ValidLanes &= ~V.WriteLanes; + } } } // Find the value in Other that overlaps VNI->def, if any. - LiveQueryResult OtherLRQ = Other.LI.Query(VNI->def); + LiveQueryResult OtherLRQ = Other.LR.Query(VNI->def); // It is possible that both values are defined by the same instruction, or // the values are PHIs defined in the same block. When that happens, the two @@ -1560,8 +2043,14 @@ JoinVals::analyzeValue(unsigned ValNo, JoinVals &Other) { return CR_Replace; // Check for simple erasable conflicts. - if (DefMI->isImplicitDef()) + if (DefMI->isImplicitDef()) { + // We need the def for the subregister if there is nothing else live at the + // subrange at this point. + if (TrackSubRegLiveness + && (V.WriteLanes & (OtherV.ValidLanes | OtherV.WriteLanes)) == 0) + return CR_Replace; return CR_Erase; + } // Include the non-conflict where DefMI is a coalescable copy that kills // OtherVNI. We still want the copy erased and value numbers merged. @@ -1582,8 +2071,8 @@ JoinVals::analyzeValue(unsigned ValNo, JoinVals &Other) { // %other = COPY %ext // %this = COPY %ext <-- Erase this copy // - if (DefMI->isFullCopy() && !CP.isPartial() && - stripCopies(VNI) == stripCopies(V.OtherVNI)) + if (DefMI->isFullCopy() && !CP.isPartial() + && valuesIdentical(VNI, V.OtherVNI, Other)) return CR_Erase; // If the lanes written by this instruction were all undef in OtherVNI, it is @@ -1618,7 +2107,7 @@ JoinVals::analyzeValue(unsigned ValNo, JoinVals &Other) { // VNI is clobbering live lanes in OtherVNI, but there is still the // possibility that no instructions actually read the clobbered lanes. // If we're clobbering all the lanes in OtherVNI, at least one must be read. - // Otherwise Other.LI wouldn't be live here. + // Otherwise Other.RI wouldn't be live here. if ((TRI->getSubRegIndexLaneMask(Other.SubIdx) & ~V.WriteLanes) == 0) return CR_Impossible; @@ -1639,9 +2128,6 @@ JoinVals::analyzeValue(unsigned ValNo, JoinVals &Other) { return CR_Unresolved; } -/// Compute the value assignment for ValNo in LI. -/// This may be called recursively by analyzeValue(), but never for a ValNo on -/// the stack. void JoinVals::computeAssignment(unsigned ValNo, JoinVals &Other) { Val &V = Vals[ValNo]; if (V.isAnalyzed()) { @@ -1657,73 +2143,64 @@ void JoinVals::computeAssignment(unsigned ValNo, JoinVals &Other) { assert(V.OtherVNI && "OtherVNI not assigned, can't merge."); assert(Other.Vals[V.OtherVNI->id].isAnalyzed() && "Missing recursion"); Assignments[ValNo] = Other.Assignments[V.OtherVNI->id]; - DEBUG(dbgs() << "\t\tmerge " << PrintReg(LI.reg) << ':' << ValNo << '@' - << LI.getValNumInfo(ValNo)->def << " into " - << PrintReg(Other.LI.reg) << ':' << V.OtherVNI->id << '@' + DEBUG(dbgs() << "\t\tmerge " << PrintReg(Reg) << ':' << ValNo << '@' + << LR.getValNumInfo(ValNo)->def << " into " + << PrintReg(Other.Reg) << ':' << V.OtherVNI->id << '@' << V.OtherVNI->def << " --> @" << NewVNInfo[Assignments[ValNo]]->def << '\n'); break; case CR_Replace: - case CR_Unresolved: + case CR_Unresolved: { // The other value is going to be pruned if this join is successful. assert(V.OtherVNI && "OtherVNI not assigned, can't prune"); - Other.Vals[V.OtherVNI->id].Pruned = true; + Val &OtherV = Other.Vals[V.OtherVNI->id]; + // We cannot erase an IMPLICIT_DEF if we don't have valid values for all + // its lanes. + if ((OtherV.WriteLanes & ~V.ValidLanes) != 0 && TrackSubRegLiveness) + OtherV.ErasableImplicitDef = false; + OtherV.Pruned = true; + } // Fall through. default: // This value number needs to go in the final joined live range. Assignments[ValNo] = NewVNInfo.size(); - NewVNInfo.push_back(LI.getValNumInfo(ValNo)); + NewVNInfo.push_back(LR.getValNumInfo(ValNo)); break; } } bool JoinVals::mapValues(JoinVals &Other) { - for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) { + for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) { computeAssignment(i, Other); if (Vals[i].Resolution == CR_Impossible) { - DEBUG(dbgs() << "\t\tinterference at " << PrintReg(LI.reg) << ':' << i - << '@' << LI.getValNumInfo(i)->def << '\n'); + DEBUG(dbgs() << "\t\tinterference at " << PrintReg(Reg) << ':' << i + << '@' << LR.getValNumInfo(i)->def << '\n'); return false; } } return true; } -/// Assuming ValNo is going to clobber some valid lanes in Other.LI, compute -/// the extent of the tainted lanes in the block. -/// -/// Multiple values in Other.LI can be affected since partial redefinitions can -/// preserve previously tainted lanes. -/// -/// 1 %dst = VLOAD <-- Define all lanes in %dst -/// 2 %src = FOO <-- ValNo to be joined with %dst:ssub0 -/// 3 %dst:ssub1 = BAR <-- Partial redef doesn't clear taint in ssub0 -/// 4 %dst:ssub0 = COPY %src <-- Conflict resolved, ssub0 wasn't read -/// -/// For each ValNo in Other that is affected, add an (EndIndex, TaintedLanes) -/// entry to TaintedVals. -/// -/// Returns false if the tainted lanes extend beyond the basic block. bool JoinVals:: -taintExtent(unsigned ValNo, unsigned TaintedLanes, JoinVals &Other, - SmallVectorImpl > &TaintExtent) { - VNInfo *VNI = LI.getValNumInfo(ValNo); +taintExtent(unsigned ValNo, LaneBitmask TaintedLanes, JoinVals &Other, + SmallVectorImpl > &TaintExtent) { + VNInfo *VNI = LR.getValNumInfo(ValNo); MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def); SlotIndex MBBEnd = Indexes->getMBBEndIdx(MBB); - // Scan Other.LI from VNI.def to MBBEnd. - LiveInterval::iterator OtherI = Other.LI.find(VNI->def); - assert(OtherI != Other.LI.end() && "No conflict?"); + // Scan Other.LR from VNI.def to MBBEnd. + LiveInterval::iterator OtherI = Other.LR.find(VNI->def); + assert(OtherI != Other.LR.end() && "No conflict?"); do { // OtherI is pointing to a tainted value. Abort the join if the tainted // lanes escape the block. SlotIndex End = OtherI->end; if (End >= MBBEnd) { - DEBUG(dbgs() << "\t\ttaints global " << PrintReg(Other.LI.reg) << ':' + DEBUG(dbgs() << "\t\ttaints global " << PrintReg(Other.Reg) << ':' << OtherI->valno->id << '@' << OtherI->start << '\n'); return false; } - DEBUG(dbgs() << "\t\ttaints local " << PrintReg(Other.LI.reg) << ':' + DEBUG(dbgs() << "\t\ttaints local " << PrintReg(Other.Reg) << ':' << OtherI->valno->id << '@' << OtherI->start << " to " << End << '\n'); // A dead def is not a problem. @@ -1732,7 +2209,7 @@ taintExtent(unsigned ValNo, unsigned TaintedLanes, JoinVals &Other, TaintExtent.push_back(std::make_pair(End, TaintedLanes)); // Check for another def in the MBB. - if (++OtherI == Other.LI.end() || OtherI->start >= MBBEnd) + if (++OtherI == Other.LR.end() || OtherI->start >= MBBEnd) break; // Lanes written by the new def are no longer tainted. @@ -1744,42 +2221,43 @@ taintExtent(unsigned ValNo, unsigned TaintedLanes, JoinVals &Other, return true; } -/// Return true if MI uses any of the given Lanes from Reg. -/// This does not include partial redefinitions of Reg. -bool JoinVals::usesLanes(MachineInstr *MI, unsigned Reg, unsigned SubIdx, - unsigned Lanes) { +bool JoinVals::usesLanes(const MachineInstr *MI, unsigned Reg, unsigned SubIdx, + LaneBitmask Lanes) const { if (MI->isDebugValue()) return false; - for (ConstMIOperands MO(MI); MO.isValid(); ++MO) { - if (!MO->isReg() || MO->isDef() || MO->getReg() != Reg) + for (const MachineOperand &MO : MI->operands()) { + if (!MO.isReg() || MO.isDef() || MO.getReg() != Reg) continue; - if (!MO->readsReg()) + if (!MO.readsReg()) continue; if (Lanes & TRI->getSubRegIndexLaneMask( - TRI->composeSubRegIndices(SubIdx, MO->getSubReg()))) + TRI->composeSubRegIndices(SubIdx, MO.getSubReg()))) return true; } return false; } bool JoinVals::resolveConflicts(JoinVals &Other) { - for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) { + for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) { Val &V = Vals[i]; assert (V.Resolution != CR_Impossible && "Unresolvable conflict"); if (V.Resolution != CR_Unresolved) continue; - DEBUG(dbgs() << "\t\tconflict at " << PrintReg(LI.reg) << ':' << i - << '@' << LI.getValNumInfo(i)->def << '\n'); + DEBUG(dbgs() << "\t\tconflict at " << PrintReg(Reg) << ':' << i + << '@' << LR.getValNumInfo(i)->def << '\n'); + if (SubRangeJoin) + return false; + ++NumLaneConflicts; assert(V.OtherVNI && "Inconsistent conflict resolution."); - VNInfo *VNI = LI.getValNumInfo(i); + VNInfo *VNI = LR.getValNumInfo(i); const Val &OtherV = Other.Vals[V.OtherVNI->id]; // VNI is known to clobber some lanes in OtherVNI. If we go ahead with the // join, those lanes will be tainted with a wrong value. Get the extent of // the tainted lanes. - unsigned TaintedLanes = V.WriteLanes & OtherV.ValidLanes; - SmallVector, 8> TaintExtent; + LaneBitmask TaintedLanes = V.WriteLanes & OtherV.ValidLanes; + SmallVector, 8> TaintExtent; if (!taintExtent(i, TaintedLanes, Other, TaintExtent)) // Tainted lanes would extend beyond the basic block. return false; @@ -1802,7 +2280,7 @@ bool JoinVals::resolveConflicts(JoinVals &Other) { unsigned TaintNum = 0; for(;;) { assert(MI != MBB->end() && "Bad LastMI"); - if (usesLanes(MI, Other.LI.reg, Other.SubIdx, TaintedLanes)) { + if (usesLanes(MI, Other.Reg, Other.SubIdx, TaintedLanes)) { DEBUG(dbgs() << "\t\ttainted lanes used by: " << *MI); return false; } @@ -1824,13 +2302,6 @@ bool JoinVals::resolveConflicts(JoinVals &Other) { return true; } -// Determine if ValNo is a copy of a value number in LI or Other.LI that will -// be pruned: -// -// %dst = COPY %src -// %src = COPY %dst <-- This value to be pruned. -// %dst = COPY %src <-- This value is a copy of a pruned value. -// bool JoinVals::isPrunedValue(unsigned ValNo, JoinVals &Other) { Val &V = Vals[ValNo]; if (V.Pruned || V.PrunedComputed) @@ -1847,15 +2318,16 @@ bool JoinVals::isPrunedValue(unsigned ValNo, JoinVals &Other) { } void JoinVals::pruneValues(JoinVals &Other, - SmallVectorImpl &EndPoints) { - for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) { - SlotIndex Def = LI.getValNumInfo(i)->def; + SmallVectorImpl &EndPoints, + bool changeInstrs) { + for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) { + SlotIndex Def = LR.getValNumInfo(i)->def; switch (Vals[i].Resolution) { case CR_Keep: break; case CR_Replace: { - // This value takes precedence over the value in Other.LI. - LIS->pruneValue(&Other.LI, Def, &EndPoints); + // This value takes precedence over the value in Other.LR. + LIS->pruneValue(Other.LR, Def, &EndPoints); // Check if we're replacing an IMPLICIT_DEF value. The IMPLICIT_DEF // instructions are only inserted to provide a live-out value for PHI // predecessors, so the instruction should simply go away once its value @@ -1864,34 +2336,37 @@ void JoinVals::pruneValues(JoinVals &Other, bool EraseImpDef = OtherV.ErasableImplicitDef && OtherV.Resolution == CR_Keep; if (!Def.isBlock()) { - // Remove flags. This def is now a partial redef. - // Also remove flags since the joined live range will - // continue past this instruction. - for (MIOperands MO(Indexes->getInstructionFromIndex(Def)); - MO.isValid(); ++MO) - if (MO->isReg() && MO->isDef() && MO->getReg() == LI.reg) { - MO->setIsUndef(EraseImpDef); - MO->setIsDead(false); + if (changeInstrs) { + // Remove flags. This def is now a partial redef. + // Also remove flags since the joined live range will + // continue past this instruction. + for (MachineOperand &MO : + Indexes->getInstructionFromIndex(Def)->operands()) { + if (MO.isReg() && MO.isDef() && MO.getReg() == Reg) { + MO.setIsUndef(EraseImpDef); + MO.setIsDead(false); + } } + } // This value will reach instructions below, but we need to make sure // the live range also reaches the instruction at Def. if (!EraseImpDef) EndPoints.push_back(Def); } - DEBUG(dbgs() << "\t\tpruned " << PrintReg(Other.LI.reg) << " at " << Def - << ": " << Other.LI << '\n'); + DEBUG(dbgs() << "\t\tpruned " << PrintReg(Other.Reg) << " at " << Def + << ": " << Other.LR << '\n'); break; } case CR_Erase: case CR_Merge: if (isPrunedValue(i, Other)) { - // This value is ultimately a copy of a pruned value in LI or Other.LI. + // This value is ultimately a copy of a pruned value in LR or Other.LR. // We can no longer trust the value mapping computed by // computeAssignment(), the value that was originally copied could have // been replaced. - LIS->pruneValue(&LI, Def, &EndPoints); - DEBUG(dbgs() << "\t\tpruned all of " << PrintReg(LI.reg) << " at " - << Def << ": " << LI << '\n'); + LIS->pruneValue(LR, Def, &EndPoints); + DEBUG(dbgs() << "\t\tpruned all of " << PrintReg(Reg) << " at " + << Def << ": " << LR << '\n'); } break; case CR_Unresolved: @@ -1901,25 +2376,77 @@ void JoinVals::pruneValues(JoinVals &Other, } } -void JoinVals::eraseInstrs(SmallPtrSet &ErasedInstrs, +void JoinVals::pruneSubRegValues(LiveInterval &LI, LaneBitmask &ShrinkMask) +{ + // Look for values being erased. + bool DidPrune = false; + for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) { + if (Vals[i].Resolution != CR_Erase) + continue; + + // Check subranges at the point where the copy will be removed. + SlotIndex Def = LR.getValNumInfo(i)->def; + for (LiveInterval::SubRange &S : LI.subranges()) { + LiveQueryResult Q = S.Query(Def); + + // If a subrange starts at the copy then an undefined value has been + // copied and we must remove that subrange value as well. + VNInfo *ValueOut = Q.valueOutOrDead(); + if (ValueOut != nullptr && Q.valueIn() == nullptr) { + DEBUG(dbgs() << "\t\tPrune sublane " << PrintLaneMask(S.LaneMask) + << " at " << Def << "\n"); + LIS->pruneValue(S, Def, nullptr); + DidPrune = true; + // Mark value number as unused. + ValueOut->markUnused(); + continue; + } + // If a subrange ends at the copy, then a value was copied but only + // partially used later. Shrink the subregister range appropriately. + if (Q.valueIn() != nullptr && Q.valueOut() == nullptr) { + DEBUG(dbgs() << "\t\tDead uses at sublane " << PrintLaneMask(S.LaneMask) + << " at " << Def << "\n"); + ShrinkMask |= S.LaneMask; + } + } + } + if (DidPrune) + LI.removeEmptySubRanges(); +} + +void JoinVals::removeImplicitDefs() { + for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) { + Val &V = Vals[i]; + if (V.Resolution != CR_Keep || !V.ErasableImplicitDef || !V.Pruned) + continue; + + VNInfo *VNI = LR.getValNumInfo(i); + VNI->markUnused(); + LR.removeValNo(VNI); + } +} + +void JoinVals::eraseInstrs(SmallPtrSetImpl &ErasedInstrs, SmallVectorImpl &ShrinkRegs) { - for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) { + for (unsigned i = 0, e = LR.getNumValNums(); i != e; ++i) { // Get the def location before markUnused() below invalidates it. - SlotIndex Def = LI.getValNumInfo(i)->def; + SlotIndex Def = LR.getValNumInfo(i)->def; switch (Vals[i].Resolution) { - case CR_Keep: + case CR_Keep: { // If an IMPLICIT_DEF value is pruned, it doesn't serve a purpose any // longer. The IMPLICIT_DEF instructions are only inserted by // PHIElimination to guarantee that all PHI predecessors have a value. if (!Vals[i].ErasableImplicitDef || !Vals[i].Pruned) break; - // Remove value number i from LI. Note that this VNInfo is still present - // in NewVNInfo, so it will appear as an unused value number in the final - // joined interval. - LI.getValNumInfo(i)->markUnused(); - LI.removeValNo(LI.getValNumInfo(i)); - DEBUG(dbgs() << "\t\tremoved " << i << '@' << Def << ": " << LI << '\n'); + // Remove value number i from LR. + VNInfo *VNI = LR.getValNumInfo(i); + LR.removeValNo(VNI); + // Note that this VNInfo is reused and still referenced in NewVNInfo, + // make it appear like an unused value number. + VNI->markUnused(); + DEBUG(dbgs() << "\t\tremoved " << i << '@' << Def << ": " << LR << '\n'); // FALL THROUGH. + } case CR_Erase: { MachineInstr *MI = Indexes->getInstructionFromIndex(Def); @@ -1942,12 +2469,111 @@ void JoinVals::eraseInstrs(SmallPtrSet &ErasedInstrs, } } +bool RegisterCoalescer::joinSubRegRanges(LiveRange &LRange, LiveRange &RRange, + LaneBitmask LaneMask, + const CoalescerPair &CP) { + SmallVector NewVNInfo; + JoinVals RHSVals(RRange, CP.getSrcReg(), CP.getSrcIdx(), LaneMask, + NewVNInfo, CP, LIS, TRI, true, true); + JoinVals LHSVals(LRange, CP.getDstReg(), CP.getDstIdx(), LaneMask, + NewVNInfo, CP, LIS, TRI, true, true); + + // Compute NewVNInfo and resolve conflicts (see also joinVirtRegs()) + // We should be able to resolve all conflicts here as we could successfully do + // it on the mainrange already. There is however a problem when multiple + // ranges get mapped to the "overflow" lane mask bit which creates unexpected + // interferences. + if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals)) { + DEBUG(dbgs() << "*** Couldn't join subrange!\n"); + return false; + } + if (!LHSVals.resolveConflicts(RHSVals) || + !RHSVals.resolveConflicts(LHSVals)) { + DEBUG(dbgs() << "*** Couldn't join subrange!\n"); + return false; + } + + // The merging algorithm in LiveInterval::join() can't handle conflicting + // value mappings, so we need to remove any live ranges that overlap a + // CR_Replace resolution. Collect a set of end points that can be used to + // restore the live range after joining. + SmallVector EndPoints; + LHSVals.pruneValues(RHSVals, EndPoints, false); + RHSVals.pruneValues(LHSVals, EndPoints, false); + + LHSVals.removeImplicitDefs(); + RHSVals.removeImplicitDefs(); + + LRange.verify(); + RRange.verify(); + + // Join RRange into LHS. + LRange.join(RRange, LHSVals.getAssignments(), RHSVals.getAssignments(), + NewVNInfo); + + DEBUG(dbgs() << "\t\tjoined lanes: " << LRange << "\n"); + if (EndPoints.empty()) + return true; + + // Recompute the parts of the live range we had to remove because of + // CR_Replace conflicts. + DEBUG(dbgs() << "\t\trestoring liveness to " << EndPoints.size() + << " points: " << LRange << '\n'); + LIS->extendToIndices(LRange, EndPoints); + return true; +} + +bool RegisterCoalescer::mergeSubRangeInto(LiveInterval &LI, + const LiveRange &ToMerge, + LaneBitmask LaneMask, + CoalescerPair &CP) { + BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator(); + for (LiveInterval::SubRange &R : LI.subranges()) { + LaneBitmask RMask = R.LaneMask; + // LaneMask of subregisters common to subrange R and ToMerge. + LaneBitmask Common = RMask & LaneMask; + // There is nothing to do without common subregs. + if (Common == 0) + continue; + + DEBUG(dbgs() << "\t\tCopy+Merge " << PrintLaneMask(RMask) << " into " + << PrintLaneMask(Common) << '\n'); + // LaneMask of subregisters contained in the R range but not in ToMerge, + // they have to split into their own subrange. + LaneBitmask LRest = RMask & ~LaneMask; + LiveInterval::SubRange *CommonRange; + if (LRest != 0) { + R.LaneMask = LRest; + DEBUG(dbgs() << "\t\tReduce Lane to " << PrintLaneMask(LRest) << '\n'); + // Duplicate SubRange for newly merged common stuff. + CommonRange = LI.createSubRangeFrom(Allocator, Common, R); + } else { + // Reuse the existing range. + R.LaneMask = Common; + CommonRange = &R; + } + LiveRange RangeCopy(ToMerge, Allocator); + if (!joinSubRegRanges(*CommonRange, RangeCopy, Common, CP)) + return false; + LaneMask &= ~RMask; + } + + if (LaneMask != 0) { + DEBUG(dbgs() << "\t\tNew Lane " << PrintLaneMask(LaneMask) << '\n'); + LI.createSubRangeFrom(Allocator, LaneMask, ToMerge); + } + return true; +} + bool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP) { SmallVector NewVNInfo; LiveInterval &RHS = LIS->getInterval(CP.getSrcReg()); LiveInterval &LHS = LIS->getInterval(CP.getDstReg()); - JoinVals RHSVals(RHS, CP.getSrcIdx(), NewVNInfo, CP, LIS, TRI); - JoinVals LHSVals(LHS, CP.getDstIdx(), NewVNInfo, CP, LIS, TRI); + bool TrackSubRegLiveness = MRI->shouldTrackSubRegLiveness(*CP.getNewRC()); + JoinVals RHSVals(RHS, CP.getSrcReg(), CP.getSrcIdx(), 0, NewVNInfo, CP, LIS, + TRI, false, TrackSubRegLiveness); + JoinVals LHSVals(LHS, CP.getDstReg(), CP.getDstIdx(), 0, NewVNInfo, CP, LIS, + TRI, false, TrackSubRegLiveness); DEBUG(dbgs() << "\t\tRHS = " << RHS << "\n\t\tLHS = " << LHS @@ -1963,14 +2589,74 @@ bool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP) { return false; // All clear, the live ranges can be merged. + if (RHS.hasSubRanges() || LHS.hasSubRanges()) { + BumpPtrAllocator &Allocator = LIS->getVNInfoAllocator(); + + // Transform lanemasks from the LHS to masks in the coalesced register and + // create initial subranges if necessary. + unsigned DstIdx = CP.getDstIdx(); + if (!LHS.hasSubRanges()) { + LaneBitmask Mask = DstIdx == 0 ? CP.getNewRC()->getLaneMask() + : TRI->getSubRegIndexLaneMask(DstIdx); + // LHS must support subregs or we wouldn't be in this codepath. + assert(Mask != 0); + LHS.createSubRangeFrom(Allocator, Mask, LHS); + } else if (DstIdx != 0) { + // Transform LHS lanemasks to new register class if necessary. + for (LiveInterval::SubRange &R : LHS.subranges()) { + LaneBitmask Mask = TRI->composeSubRegIndexLaneMask(DstIdx, R.LaneMask); + R.LaneMask = Mask; + } + } + DEBUG(dbgs() << "\t\tLHST = " << PrintReg(CP.getDstReg()) + << ' ' << LHS << '\n'); + + // Determine lanemasks of RHS in the coalesced register and merge subranges. + unsigned SrcIdx = CP.getSrcIdx(); + bool Abort = false; + if (!RHS.hasSubRanges()) { + LaneBitmask Mask = SrcIdx == 0 ? CP.getNewRC()->getLaneMask() + : TRI->getSubRegIndexLaneMask(SrcIdx); + if (!mergeSubRangeInto(LHS, RHS, Mask, CP)) + Abort = true; + } else { + // Pair up subranges and merge. + for (LiveInterval::SubRange &R : RHS.subranges()) { + LaneBitmask Mask = TRI->composeSubRegIndexLaneMask(SrcIdx, R.LaneMask); + if (!mergeSubRangeInto(LHS, R, Mask, CP)) { + Abort = true; + break; + } + } + } + if (Abort) { + // This shouldn't have happened :-( + // However we are aware of at least one existing problem where we + // can't merge subranges when multiple ranges end up in the + // "overflow bit" 32. As a workaround we drop all subregister ranges + // which means we loose some precision but are back to a well defined + // state. + assert(TargetRegisterInfo::isImpreciseLaneMask( + CP.getNewRC()->getLaneMask()) + && "SubRange merge should only fail when merging into bit 32."); + DEBUG(dbgs() << "\tSubrange join aborted!\n"); + LHS.clearSubRanges(); + RHS.clearSubRanges(); + } else { + DEBUG(dbgs() << "\tJoined SubRanges " << LHS << "\n"); + + LHSVals.pruneSubRegValues(LHS, ShrinkMask); + RHSVals.pruneSubRegValues(LHS, ShrinkMask); + } + } // The merging algorithm in LiveInterval::join() can't handle conflicting // value mappings, so we need to remove any live ranges that overlap a // CR_Replace resolution. Collect a set of end points that can be used to // restore the live range after joining. SmallVector EndPoints; - LHSVals.pruneValues(RHSVals, EndPoints); - RHSVals.pruneValues(LHSVals, EndPoints); + LHSVals.pruneValues(RHSVals, EndPoints, true); + RHSVals.pruneValues(LHSVals, EndPoints, true); // Erase COPY and IMPLICIT_DEF instructions. This may cause some external // registers to require trimming. @@ -1978,7 +2664,7 @@ bool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP) { LHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs); RHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs); while (!ShrinkRegs.empty()) - LIS->shrinkToUses(&LIS->getInterval(ShrinkRegs.pop_back_val())); + shrinkToUses(&LIS->getInterval(ShrinkRegs.pop_back_val())); // Join RHS into LHS. LHS.join(RHS, LHSVals.getAssignments(), RHSVals.getAssignments(), NewVNInfo); @@ -1989,25 +2675,23 @@ bool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP) { MRI->clearKillFlags(LHS.reg); MRI->clearKillFlags(RHS.reg); - if (EndPoints.empty()) - return true; + if (!EndPoints.empty()) { + // Recompute the parts of the live range we had to remove because of + // CR_Replace conflicts. + DEBUG(dbgs() << "\t\trestoring liveness to " << EndPoints.size() + << " points: " << LHS << '\n'); + LIS->extendToIndices((LiveRange&)LHS, EndPoints); + } - // Recompute the parts of the live range we had to remove because of - // CR_Replace conflicts. - DEBUG(dbgs() << "\t\trestoring liveness to " << EndPoints.size() - << " points: " << LHS << '\n'); - LIS->extendToIndices(LHS, EndPoints); return true; } -/// joinIntervals - Attempt to join these two intervals. On failure, this -/// returns false. bool RegisterCoalescer::joinIntervals(CoalescerPair &CP) { return CP.isPhys() ? joinReservedPhysReg(CP) : joinVirtRegs(CP); } namespace { -// Information concerning MBB coalescing priority. +/// Information concerning MBB coalescing priority. struct MBBPriorityInfo { MachineBasicBlock *MBB; unsigned Depth; @@ -2018,10 +2702,10 @@ struct MBBPriorityInfo { }; } -// C-style comparator that sorts first based on the loop depth of the basic -// block (the unsigned), and then on the MBB number. -// -// EnableGlobalCopies assumes that the primary sort key is loop depth. +/// C-style comparator that sorts first based on the loop depth of the basic +/// block (the unsigned), and then on the MBB number. +/// +/// EnableGlobalCopies assumes that the primary sort key is loop depth. static int compareMBBPriority(const MBBPriorityInfo *LHS, const MBBPriorityInfo *RHS) { // Deeper loops first @@ -2061,8 +2745,6 @@ static bool isLocalCopy(MachineInstr *Copy, const LiveIntervals *LIS) { || LIS->intervalIsInOneMBB(LIS->getInterval(DstReg)); } -// Try joining WorkList copies starting from index From. -// Null out any successful joins. bool RegisterCoalescer:: copyCoalesceWorkList(MutableArrayRef CurrList) { bool Progress = false; @@ -2072,18 +2754,76 @@ copyCoalesceWorkList(MutableArrayRef CurrList) { // Skip instruction pointers that have already been erased, for example by // dead code elimination. if (ErasedInstrs.erase(CurrList[i])) { - CurrList[i] = 0; + CurrList[i] = nullptr; continue; } bool Again = false; bool Success = joinCopy(CurrList[i], Again); Progress |= Success; if (Success || !Again) - CurrList[i] = 0; + CurrList[i] = nullptr; } return Progress; } +/// Check if DstReg is a terminal node. +/// I.e., it does not have any affinity other than \p Copy. +static bool isTerminalReg(unsigned DstReg, const MachineInstr &Copy, + const MachineRegisterInfo *MRI) { + assert(Copy.isCopyLike()); + // Check if the destination of this copy as any other affinity. + for (const MachineInstr &MI : MRI->reg_nodbg_instructions(DstReg)) + if (&MI != &Copy && MI.isCopyLike()) + return false; + return true; +} + +bool RegisterCoalescer::applyTerminalRule(const MachineInstr &Copy) const { + assert(Copy.isCopyLike()); + if (!UseTerminalRule) + return false; + unsigned DstReg, DstSubReg, SrcReg, SrcSubReg; + isMoveInstr(*TRI, &Copy, SrcReg, DstReg, SrcSubReg, DstSubReg); + // Check if the destination of this copy has any other affinity. + if (TargetRegisterInfo::isPhysicalRegister(DstReg) || + // If SrcReg is a physical register, the copy won't be coalesced. + // Ignoring it may have other side effect (like missing + // rematerialization). So keep it. + TargetRegisterInfo::isPhysicalRegister(SrcReg) || + !isTerminalReg(DstReg, Copy, MRI)) + return false; + + // DstReg is a terminal node. Check if it interferes with any other + // copy involving SrcReg. + const MachineBasicBlock *OrigBB = Copy.getParent(); + const LiveInterval &DstLI = LIS->getInterval(DstReg); + for (const MachineInstr &MI : MRI->reg_nodbg_instructions(SrcReg)) { + // Technically we should check if the weight of the new copy is + // interesting compared to the other one and update the weight + // of the copies accordingly. However, this would only work if + // we would gather all the copies first then coalesce, whereas + // right now we interleave both actions. + // For now, just consider the copies that are in the same block. + if (&MI == &Copy || !MI.isCopyLike() || MI.getParent() != OrigBB) + continue; + unsigned OtherReg, OtherSubReg, OtherSrcReg, OtherSrcSubReg; + isMoveInstr(*TRI, &Copy, OtherSrcReg, OtherReg, OtherSrcSubReg, + OtherSubReg); + if (OtherReg == SrcReg) + OtherReg = OtherSrcReg; + // Check if OtherReg is a non-terminal. + if (TargetRegisterInfo::isPhysicalRegister(OtherReg) || + isTerminalReg(OtherReg, MI, MRI)) + continue; + // Check that OtherReg interfere with DstReg. + if (LIS->getInterval(OtherReg).overlaps(DstLI)) { + DEBUG(dbgs() << "Apply terminal rule for: " << PrintReg(DstReg) << '\n'); + return true; + } + } + return false; +} + void RegisterCoalescer::copyCoalesceInMBB(MachineBasicBlock *MBB) { DEBUG(dbgs() << MBB->getName() << ":\n"); @@ -2092,6 +2832,8 @@ RegisterCoalescer::copyCoalesceInMBB(MachineBasicBlock *MBB) { // yet, it might invalidate the iterator. const unsigned PrevSize = WorkList.size(); if (JoinGlobalCopies) { + SmallVector LocalTerminals; + SmallVector GlobalTerminals; // Coalesce copies bottom-up to coalesce local defs before local uses. They // are not inherently easier to resolve, but slightly preferable until we // have local live range splitting. In particular this is required by @@ -2100,17 +2842,35 @@ RegisterCoalescer::copyCoalesceInMBB(MachineBasicBlock *MBB) { MII != E; ++MII) { if (!MII->isCopyLike()) continue; - if (isLocalCopy(&(*MII), LIS)) - LocalWorkList.push_back(&(*MII)); - else - WorkList.push_back(&(*MII)); + bool ApplyTerminalRule = applyTerminalRule(*MII); + if (isLocalCopy(&(*MII), LIS)) { + if (ApplyTerminalRule) + LocalTerminals.push_back(&(*MII)); + else + LocalWorkList.push_back(&(*MII)); + } else { + if (ApplyTerminalRule) + GlobalTerminals.push_back(&(*MII)); + else + WorkList.push_back(&(*MII)); + } } + // Append the copies evicted by the terminal rule at the end of the list. + LocalWorkList.append(LocalTerminals.begin(), LocalTerminals.end()); + WorkList.append(GlobalTerminals.begin(), GlobalTerminals.end()); } else { + SmallVector Terminals; for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end(); MII != E; ++MII) - if (MII->isCopyLike()) - WorkList.push_back(MII); + if (MII->isCopyLike()) { + if (applyTerminalRule(*MII)) + Terminals.push_back(&(*MII)); + else + WorkList.push_back(MII); + } + // Append the copies evicted by the terminal rule at the end of the list. + WorkList.append(Terminals.begin(), Terminals.end()); } // Try coalescing the collected copies immediately, and remove the nulls. // This prevents the WorkList from getting too large since most copies are @@ -2119,7 +2879,7 @@ RegisterCoalescer::copyCoalesceInMBB(MachineBasicBlock *MBB) { CurrList(WorkList.begin() + PrevSize, WorkList.end()); if (copyCoalesceWorkList(CurrList)) WorkList.erase(std::remove(WorkList.begin() + PrevSize, WorkList.end(), - (MachineInstr*)0), WorkList.end()); + (MachineInstr*)nullptr), WorkList.end()); } void RegisterCoalescer::coalesceLocals() { @@ -2138,7 +2898,7 @@ void RegisterCoalescer::joinAllIntervals() { std::vector MBBs; MBBs.reserve(MF->size()); for (MachineFunction::iterator I = MF->begin(), E = MF->end();I != E;++I){ - MachineBasicBlock *MBB = I; + MachineBasicBlock *MBB = &*I; MBBs.push_back(MBBPriorityInfo(MBB, Loops->getLoopDepth(MBB), JoinSplitEdges && isSplitEdge(MBB))); } @@ -2173,15 +2933,14 @@ bool RegisterCoalescer::runOnMachineFunction(MachineFunction &fn) { MF = &fn; MRI = &fn.getRegInfo(); TM = &fn.getTarget(); - TRI = TM->getRegisterInfo(); - TII = TM->getInstrInfo(); + const TargetSubtargetInfo &STI = fn.getSubtarget(); + TRI = STI.getRegisterInfo(); + TII = STI.getInstrInfo(); LIS = &getAnalysis(); - AA = &getAnalysis(); + AA = &getAnalysis().getAAResults(); Loops = &getAnalysis(); - - const TargetSubtargetInfo &ST = TM->getSubtarget(); if (EnableGlobalCopies == cl::BOU_UNSET) - JoinGlobalCopies = ST.useMachineScheduler(); + JoinGlobalCopies = STI.enableJoinGlobalCopies(); else JoinGlobalCopies = (EnableGlobalCopies == cl::BOU_TRUE); @@ -2213,9 +2972,24 @@ bool RegisterCoalescer::runOnMachineFunction(MachineFunction &fn) { unsigned Reg = InflateRegs[i]; if (MRI->reg_nodbg_empty(Reg)) continue; - if (MRI->recomputeRegClass(Reg, *TM)) { + if (MRI->recomputeRegClass(Reg)) { DEBUG(dbgs() << PrintReg(Reg) << " inflated to " - << MRI->getRegClass(Reg)->getName() << '\n'); + << TRI->getRegClassName(MRI->getRegClass(Reg)) << '\n'); + LiveInterval &LI = LIS->getInterval(Reg); + LaneBitmask MaxMask = MRI->getMaxLaneMaskForVReg(Reg); + if (MaxMask == 0) { + // If the inflated register class does not support subregisters anymore + // remove the subranges. + LI.clearSubRanges(); + } else { +#ifndef NDEBUG + // If subranges are still supported, then the same subregs should still + // be supported. + for (LiveInterval::SubRange &S : LI.subranges()) { + assert ((S.LaneMask & ~MaxMask) == 0); + } +#endif + } ++NumInflated; } } @@ -2226,7 +3000,6 @@ bool RegisterCoalescer::runOnMachineFunction(MachineFunction &fn) { return true; } -/// print - Implement the dump method. void RegisterCoalescer::print(raw_ostream &O, const Module* m) const { LIS->print(O, m); }