From owner-svn-src-stable-11@freebsd.org Sun May 20 16:03:22 2018 Return-Path: Delivered-To: svn-src-stable-11@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 3EBE3EE54ED; Sun, 20 May 2018 16:03:22 +0000 (UTC) (envelope-from dim@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client CN "mxrelay.nyi.freebsd.org", Issuer "Let's Encrypt Authority X3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id D4D048470C; Sun, 20 May 2018 16:03:21 +0000 (UTC) (envelope-from dim@FreeBSD.org) Received: from repo.freebsd.org (repo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id B1776188B8; Sun, 20 May 2018 16:03:21 +0000 (UTC) (envelope-from dim@FreeBSD.org) Received: from repo.freebsd.org ([127.0.1.37]) by repo.freebsd.org (8.15.2/8.15.2) with ESMTP id w4KG3LTL019344; Sun, 20 May 2018 16:03:21 GMT (envelope-from dim@FreeBSD.org) Received: (from dim@localhost) by repo.freebsd.org (8.15.2/8.15.2/Submit) id w4KG3LFc019343; Sun, 20 May 2018 16:03:21 GMT (envelope-from dim@FreeBSD.org) Message-Id: <201805201603.w4KG3LFc019343@repo.freebsd.org> X-Authentication-Warning: repo.freebsd.org: dim set sender to dim@FreeBSD.org using -f From: Dimitry Andric Date: Sun, 20 May 2018 16:03:21 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-stable@freebsd.org, svn-src-stable-11@freebsd.org Subject: svn commit: r333926 - stable/11/contrib/llvm/lib/CodeGen X-SVN-Group: stable-11 X-SVN-Commit-Author: dim X-SVN-Commit-Paths: stable/11/contrib/llvm/lib/CodeGen X-SVN-Commit-Revision: 333926 X-SVN-Commit-Repository: base MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-stable-11@freebsd.org X-Mailman-Version: 2.1.26 Precedence: list List-Id: SVN commit messages for only the 11-stable src tree List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 20 May 2018 16:03:22 -0000 Author: dim Date: Sun May 20 16:03:21 2018 New Revision: 333926 URL: https://svnweb.freebsd.org/changeset/base/333926 Log: MFC r333715: Pull in r322325 from upstream llvm trunk (by Matthias Braun): PeepholeOpt cleanup/refactor; NFC - Less unnecessary use of `auto` - Add early `using RegSubRegPair(AndIdx) =` to avoid countless `TargetInstrInfo::` qualifications. - Use references instead of pointers where possible. - Remove unused parameters. - Rewrite the CopyRewriter class hierarchy: - Pull out uncoalescable copy rewriting functionality into PeepholeOptimizer class. - Use an abstract base class to make it clear that rewriters are independent. - Remove unnecessary \brief in doxygen comments. - Remove unused constructor and method from ValueTracker. - Replace UseAdvancedTracking of ValueTracker with DisableAdvCopyOpt use. Even though upstream marked this as "No Functional Change", it does contain some functional changes, and these fix a compiler hang for one particular source file in the devel/godot port. Approved by: re (kib) PR: 228261 Modified: stable/11/contrib/llvm/lib/CodeGen/PeepholeOptimizer.cpp Directory Properties: stable/11/ (props changed) Modified: stable/11/contrib/llvm/lib/CodeGen/PeepholeOptimizer.cpp ============================================================================== --- stable/11/contrib/llvm/lib/CodeGen/PeepholeOptimizer.cpp Sun May 20 14:21:20 2018 (r333925) +++ stable/11/contrib/llvm/lib/CodeGen/PeepholeOptimizer.cpp Sun May 20 16:03:21 2018 (r333926) @@ -98,6 +98,8 @@ #include using namespace llvm; +using RegSubRegPair = TargetInstrInfo::RegSubRegPair; +using RegSubRegPairAndIdx = TargetInstrInfo::RegSubRegPairAndIdx; #define DEBUG_TYPE "peephole-opt" @@ -110,6 +112,9 @@ static cl::opt DisablePeephole("disable-peephole", cl::Hidden, cl::init(false), cl::desc("Disable the peephole optimizer")); +/// Specifiy whether or not the value tracking looks through +/// complex instructions. When this is true, the value tracker +/// bails on everything that is not a copy or a bitcast. static cl::opt DisableAdvCopyOpt("disable-adv-copy-opt", cl::Hidden, cl::init(false), cl::desc("Disable advanced copy optimization")); @@ -132,11 +137,11 @@ static cl::opt MaxRecurrenceChain( "of commuting operands")); -STATISTIC(NumReuse, "Number of extension results reused"); -STATISTIC(NumCmps, "Number of compares eliminated"); -STATISTIC(NumImmFold, "Number of move immediate folded"); -STATISTIC(NumLoadFold, "Number of loads folded"); -STATISTIC(NumSelects, "Number of selects optimized"); +STATISTIC(NumReuse, "Number of extension results reused"); +STATISTIC(NumCmps, "Number of compares eliminated"); +STATISTIC(NumImmFold, "Number of move immediate folded"); +STATISTIC(NumLoadFold, "Number of loads folded"); +STATISTIC(NumSelects, "Number of selects optimized"); STATISTIC(NumUncoalescableCopies, "Number of uncoalescable copies optimized"); STATISTIC(NumRewrittenCopies, "Number of copies rewritten"); STATISTIC(NumNAPhysCopies, "Number of non-allocatable physical copies removed"); @@ -149,9 +154,9 @@ namespace { class PeepholeOptimizer : public MachineFunctionPass { const TargetInstrInfo *TII; const TargetRegisterInfo *TRI; - MachineRegisterInfo *MRI; - MachineDominatorTree *DT; // Machine dominator tree - MachineLoopInfo *MLI; + MachineRegisterInfo *MRI; + MachineDominatorTree *DT; // Machine dominator tree + MachineLoopInfo *MLI; public: static char ID; // Pass identification @@ -173,31 +178,28 @@ namespace { } } - /// \brief Track Def -> Use info used for rewriting copies. - using RewriteMapTy = - SmallDenseMap; + /// Track Def -> Use info used for rewriting copies. + using RewriteMapTy = SmallDenseMap; - /// \brief Sequence of instructions that formulate recurrence cycle. + /// Sequence of instructions that formulate recurrence cycle. using RecurrenceCycle = SmallVector; private: - bool optimizeCmpInstr(MachineInstr *MI, MachineBasicBlock *MBB); - bool optimizeExtInstr(MachineInstr *MI, MachineBasicBlock *MBB, + bool optimizeCmpInstr(MachineInstr &MI); + bool optimizeExtInstr(MachineInstr &MI, MachineBasicBlock &MBB, SmallPtrSetImpl &LocalMIs); - bool optimizeSelect(MachineInstr *MI, + bool optimizeSelect(MachineInstr &MI, SmallPtrSetImpl &LocalMIs); - bool optimizeCondBranch(MachineInstr *MI); - bool optimizeCoalescableCopy(MachineInstr *MI); - bool optimizeUncoalescableCopy(MachineInstr *MI, + bool optimizeCondBranch(MachineInstr &MI); + bool optimizeCoalescableCopy(MachineInstr &MI); + bool optimizeUncoalescableCopy(MachineInstr &MI, SmallPtrSetImpl &LocalMIs); bool optimizeRecurrence(MachineInstr &PHI); - bool findNextSource(unsigned Reg, unsigned SubReg, - RewriteMapTy &RewriteMap); - bool isMoveImmediate(MachineInstr *MI, + bool findNextSource(RegSubRegPair RegSubReg, RewriteMapTy &RewriteMap); + bool isMoveImmediate(MachineInstr &MI, SmallSet &ImmDefRegs, DenseMap &ImmDefMIs); - bool foldImmediate(MachineInstr *MI, MachineBasicBlock *MBB, - SmallSet &ImmDefRegs, + bool foldImmediate(MachineInstr &MI, SmallSet &ImmDefRegs, DenseMap &ImmDefMIs); /// \brief Finds recurrence cycles, but only ones that formulated around @@ -212,11 +214,11 @@ namespace { /// the set \p CopySrcRegs and \p CopyMIs. If this virtual register was /// previously seen as a copy, replace the uses of this copy with the /// previously seen copy's destination register. - bool foldRedundantCopy(MachineInstr *MI, + bool foldRedundantCopy(MachineInstr &MI, SmallSet &CopySrcRegs, DenseMap &CopyMIs); - /// \brief Is the register \p Reg a non-allocatable physical register? + /// Is the register \p Reg a non-allocatable physical register? bool isNAPhysCopy(unsigned Reg); /// \brief If copy instruction \p MI is a non-allocatable virtual<->physical @@ -224,11 +226,10 @@ namespace { /// non-allocatable physical register was previously copied to a virtual /// registered and hasn't been clobbered, the virt->phys copy can be /// deleted. - bool foldRedundantNAPhysCopy( - MachineInstr *MI, + bool foldRedundantNAPhysCopy(MachineInstr &MI, DenseMap &NAPhysToVirtMIs); - bool isLoadFoldable(MachineInstr *MI, + bool isLoadFoldable(MachineInstr &MI, SmallSet &FoldAsLoadDefCandidates); /// \brief Check whether \p MI is understood by the register coalescer @@ -249,10 +250,13 @@ namespace { (MI.isRegSequenceLike() || MI.isInsertSubregLike() || MI.isExtractSubregLike())); } + + MachineInstr &rewriteSource(MachineInstr &CopyLike, + RegSubRegPair Def, RewriteMapTy &RewriteMap); }; - /// \brief Helper class to hold instructions that are inside recurrence - /// cycles. The recurrence cycle is formulated around 1) a def operand and its + /// Helper class to hold instructions that are inside recurrence cycles. + /// The recurrence cycle is formulated around 1) a def operand and its /// tied use operand, or 2) a def operand and a use operand that is commutable /// with another use operand which is tied to the def operand. In the latter /// case, index of the tied use operand and the commutable use operand are @@ -273,13 +277,13 @@ namespace { Optional CommutePair; }; - /// \brief Helper class to hold a reply for ValueTracker queries. Contains the - /// returned sources for a given search and the instructions where the sources - /// were tracked from. + /// Helper class to hold a reply for ValueTracker queries. + /// Contains the returned sources for a given search and the instructions + /// where the sources were tracked from. class ValueTrackerResult { private: /// Track all sources found by one ValueTracker query. - SmallVector RegSrcs; + SmallVector RegSrcs; /// Instruction using the sources in 'RegSrcs'. const MachineInstr *Inst = nullptr; @@ -302,16 +306,20 @@ namespace { } void addSource(unsigned SrcReg, unsigned SrcSubReg) { - RegSrcs.push_back(TargetInstrInfo::RegSubRegPair(SrcReg, SrcSubReg)); + RegSrcs.push_back(RegSubRegPair(SrcReg, SrcSubReg)); } void setSource(int Idx, unsigned SrcReg, unsigned SrcSubReg) { assert(Idx < getNumSources() && "Reg pair source out of index"); - RegSrcs[Idx] = TargetInstrInfo::RegSubRegPair(SrcReg, SrcSubReg); + RegSrcs[Idx] = RegSubRegPair(SrcReg, SrcSubReg); } int getNumSources() const { return RegSrcs.size(); } + RegSubRegPair getSrc(int Idx) const { + return RegSrcs[Idx]; + } + unsigned getSrcReg(int Idx) const { assert(Idx < getNumSources() && "Reg source out of index"); return RegSrcs[Idx].Reg; @@ -367,59 +375,41 @@ namespace { /// The register where the value can be found. unsigned Reg; - /// Specifiy whether or not the value tracking looks through - /// complex instructions. When this is false, the value tracker - /// bails on everything that is not a copy or a bitcast. - /// - /// Note: This could have been implemented as a specialized version of - /// the ValueTracker class but that would have complicated the code of - /// the users of this class. - bool UseAdvancedTracking; - /// MachineRegisterInfo used to perform tracking. const MachineRegisterInfo &MRI; - /// Optional TargetInstrInfo used to perform some complex - /// tracking. + /// Optional TargetInstrInfo used to perform some complex tracking. const TargetInstrInfo *TII; - /// \brief Dispatcher to the right underlying implementation of - /// getNextSource. + /// Dispatcher to the right underlying implementation of getNextSource. ValueTrackerResult getNextSourceImpl(); - /// \brief Specialized version of getNextSource for Copy instructions. + /// Specialized version of getNextSource for Copy instructions. ValueTrackerResult getNextSourceFromCopy(); - /// \brief Specialized version of getNextSource for Bitcast instructions. + /// Specialized version of getNextSource for Bitcast instructions. ValueTrackerResult getNextSourceFromBitcast(); - /// \brief Specialized version of getNextSource for RegSequence - /// instructions. + /// Specialized version of getNextSource for RegSequence instructions. ValueTrackerResult getNextSourceFromRegSequence(); - /// \brief Specialized version of getNextSource for InsertSubreg - /// instructions. + /// Specialized version of getNextSource for InsertSubreg instructions. ValueTrackerResult getNextSourceFromInsertSubreg(); - /// \brief Specialized version of getNextSource for ExtractSubreg - /// instructions. + /// Specialized version of getNextSource for ExtractSubreg instructions. ValueTrackerResult getNextSourceFromExtractSubreg(); - /// \brief Specialized version of getNextSource for SubregToReg - /// instructions. + /// Specialized version of getNextSource for SubregToReg instructions. ValueTrackerResult getNextSourceFromSubregToReg(); - /// \brief Specialized version of getNextSource for PHI instructions. + /// Specialized version of getNextSource for PHI instructions. ValueTrackerResult getNextSourceFromPHI(); public: - /// \brief Create a ValueTracker instance for the value defined by \p Reg. + /// Create a ValueTracker instance for the value defined by \p Reg. /// \p DefSubReg represents the sub register index the value tracker will /// track. It does not need to match the sub register index used in the /// definition of \p Reg. - /// \p UseAdvancedTracking specifies whether or not the value tracker looks - /// through complex instructions. By default (false), it handles only copy - /// and bitcast instructions. /// If \p Reg is a physical register, a value tracker constructed with /// this constructor will not find any alternative source. /// Indeed, when \p Reg is a physical register that constructor does not @@ -427,46 +417,20 @@ namespace { /// Use the next constructor to track a physical register. ValueTracker(unsigned Reg, unsigned DefSubReg, const MachineRegisterInfo &MRI, - bool UseAdvancedTracking = false, const TargetInstrInfo *TII = nullptr) - : DefSubReg(DefSubReg), Reg(Reg), - UseAdvancedTracking(UseAdvancedTracking), MRI(MRI), TII(TII) { + : DefSubReg(DefSubReg), Reg(Reg), MRI(MRI), TII(TII) { if (!TargetRegisterInfo::isPhysicalRegister(Reg)) { Def = MRI.getVRegDef(Reg); DefIdx = MRI.def_begin(Reg).getOperandNo(); } } - /// \brief Create a ValueTracker instance for the value defined by - /// the pair \p MI, \p DefIdx. - /// Unlike the other constructor, the value tracker produced by this one - /// may be able to find a new source when the definition is a physical - /// register. - /// This could be useful to rewrite target specific instructions into - /// generic copy instructions. - ValueTracker(const MachineInstr &MI, unsigned DefIdx, unsigned DefSubReg, - const MachineRegisterInfo &MRI, - bool UseAdvancedTracking = false, - const TargetInstrInfo *TII = nullptr) - : Def(&MI), DefIdx(DefIdx), DefSubReg(DefSubReg), - UseAdvancedTracking(UseAdvancedTracking), MRI(MRI), TII(TII) { - assert(DefIdx < Def->getDesc().getNumDefs() && - Def->getOperand(DefIdx).isReg() && "Invalid definition"); - Reg = Def->getOperand(DefIdx).getReg(); - } - /// \brief Following the use-def chain, get the next available source /// for the tracked value. /// \return A ValueTrackerResult containing a set of registers /// and sub registers with tracked values. A ValueTrackerResult with /// an empty set of registers means no source was found. ValueTrackerResult getNextSource(); - - /// \brief Get the last register where the initial value can be found. - /// Initially this is the register of the definition. - /// Then, after each successful call to getNextSource, this is the - /// register of the last source. - unsigned getReg() const { return Reg; } }; } // end anonymous namespace @@ -476,11 +440,11 @@ char PeepholeOptimizer::ID = 0; char &llvm::PeepholeOptimizerID = PeepholeOptimizer::ID; INITIALIZE_PASS_BEGIN(PeepholeOptimizer, DEBUG_TYPE, - "Peephole Optimizations", false, false) + "Peephole Optimizations", false, false) INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) INITIALIZE_PASS_END(PeepholeOptimizer, DEBUG_TYPE, - "Peephole Optimizations", false, false) + "Peephole Optimizations", false, false) /// If instruction is a copy-like instruction, i.e. it reads a single register /// and writes a single register and it does not modify the source, and if the @@ -491,10 +455,10 @@ INITIALIZE_PASS_END(PeepholeOptimizer, DEBUG_TYPE, /// the code. Since this code does not currently share EXTRACTs, just ignore all /// debug uses. bool PeepholeOptimizer:: -optimizeExtInstr(MachineInstr *MI, MachineBasicBlock *MBB, +optimizeExtInstr(MachineInstr &MI, MachineBasicBlock &MBB, SmallPtrSetImpl &LocalMIs) { unsigned SrcReg, DstReg, SubIdx; - if (!TII->isCoalescableExtInstr(*MI, SrcReg, DstReg, SubIdx)) + if (!TII->isCoalescableExtInstr(MI, SrcReg, DstReg, SubIdx)) return false; if (TargetRegisterInfo::isPhysicalRegister(DstReg) || @@ -535,7 +499,7 @@ optimizeExtInstr(MachineInstr *MI, MachineBasicBlock * bool ExtendLife = true; for (MachineOperand &UseMO : MRI->use_nodbg_operands(SrcReg)) { MachineInstr *UseMI = UseMO.getParent(); - if (UseMI == MI) + if (UseMI == &MI) continue; if (UseMI->isPHI()) { @@ -568,7 +532,7 @@ optimizeExtInstr(MachineInstr *MI, MachineBasicBlock * continue; MachineBasicBlock *UseMBB = UseMI->getParent(); - if (UseMBB == MBB) { + if (UseMBB == &MBB) { // Local uses that come after the extension. if (!LocalMIs.count(UseMI)) Uses.push_back(&UseMO); @@ -576,7 +540,7 @@ optimizeExtInstr(MachineInstr *MI, MachineBasicBlock * // Non-local uses where the result of the extension is used. Always // replace these unless it's a PHI. Uses.push_back(&UseMO); - } else if (Aggressive && DT->dominates(MBB, UseMBB)) { + } else if (Aggressive && DT->dominates(&MBB, UseMBB)) { // We may want to extend the live range of the extension result in order // to replace these uses. ExtendedUses.push_back(&UseMO); @@ -640,19 +604,18 @@ optimizeExtInstr(MachineInstr *MI, MachineBasicBlock * /// against already sets (or could be modified to set) the same flag as the /// compare, then we can remove the comparison and use the flag from the /// previous instruction. -bool PeepholeOptimizer::optimizeCmpInstr(MachineInstr *MI, - MachineBasicBlock *MBB) { +bool PeepholeOptimizer::optimizeCmpInstr(MachineInstr &MI) { // If this instruction is a comparison against zero and isn't comparing a // physical register, we can try to optimize it. unsigned SrcReg, SrcReg2; int CmpMask, CmpValue; - if (!TII->analyzeCompare(*MI, SrcReg, SrcReg2, CmpMask, CmpValue) || + if (!TII->analyzeCompare(MI, SrcReg, SrcReg2, CmpMask, CmpValue) || TargetRegisterInfo::isPhysicalRegister(SrcReg) || (SrcReg2 != 0 && TargetRegisterInfo::isPhysicalRegister(SrcReg2))) return false; // Attempt to optimize the comparison instruction. - if (TII->optimizeCompareInstr(*MI, SrcReg, SrcReg2, CmpMask, CmpValue, MRI)) { + if (TII->optimizeCompareInstr(MI, SrcReg, SrcReg2, CmpMask, CmpValue, MRI)) { ++NumCmps; return true; } @@ -661,27 +624,26 @@ bool PeepholeOptimizer::optimizeCmpInstr(MachineInstr } /// Optimize a select instruction. -bool PeepholeOptimizer::optimizeSelect(MachineInstr *MI, +bool PeepholeOptimizer::optimizeSelect(MachineInstr &MI, SmallPtrSetImpl &LocalMIs) { unsigned TrueOp = 0; unsigned FalseOp = 0; bool Optimizable = false; SmallVector Cond; - if (TII->analyzeSelect(*MI, Cond, TrueOp, FalseOp, Optimizable)) + if (TII->analyzeSelect(MI, Cond, TrueOp, FalseOp, Optimizable)) return false; if (!Optimizable) return false; - if (!TII->optimizeSelect(*MI, LocalMIs)) + if (!TII->optimizeSelect(MI, LocalMIs)) return false; - MI->eraseFromParent(); + MI.eraseFromParent(); ++NumSelects; return true; } -/// \brief Check if a simpler conditional branch can be -/// generated -bool PeepholeOptimizer::optimizeCondBranch(MachineInstr *MI) { - return TII->optimizeCondBranch(*MI); +/// Check if a simpler conditional branch can be generated. +bool PeepholeOptimizer::optimizeCondBranch(MachineInstr &MI) { + return TII->optimizeCondBranch(MI); } /// \brief Try to find the next source that share the same register file @@ -695,30 +657,29 @@ bool PeepholeOptimizer::optimizeCondBranch(MachineInst /// share the same register file as \p Reg and \p SubReg. The client should /// then be capable to rewrite all intermediate PHIs to get the next source. /// \return False if no alternative sources are available. True otherwise. -bool PeepholeOptimizer::findNextSource(unsigned Reg, unsigned SubReg, +bool PeepholeOptimizer::findNextSource(RegSubRegPair RegSubReg, RewriteMapTy &RewriteMap) { // Do not try to find a new source for a physical register. // So far we do not have any motivating example for doing that. // Thus, instead of maintaining untested code, we will revisit that if // that changes at some point. + unsigned Reg = RegSubReg.Reg; if (TargetRegisterInfo::isPhysicalRegister(Reg)) return false; const TargetRegisterClass *DefRC = MRI->getRegClass(Reg); - SmallVector SrcToLook; - TargetInstrInfo::RegSubRegPair CurSrcPair(Reg, SubReg); + SmallVector SrcToLook; + RegSubRegPair CurSrcPair = RegSubReg; SrcToLook.push_back(CurSrcPair); unsigned PHICount = 0; - while (!SrcToLook.empty() && PHICount < RewritePHILimit) { - TargetInstrInfo::RegSubRegPair Pair = SrcToLook.pop_back_val(); + do { + CurSrcPair = SrcToLook.pop_back_val(); // As explained above, do not handle physical registers - if (TargetRegisterInfo::isPhysicalRegister(Pair.Reg)) + if (TargetRegisterInfo::isPhysicalRegister(CurSrcPair.Reg)) return false; - CurSrcPair = Pair; - ValueTracker ValTracker(CurSrcPair.Reg, CurSrcPair.SubReg, *MRI, - !DisableAdvCopyOpt, TII); + ValueTracker ValTracker(CurSrcPair.Reg, CurSrcPair.SubReg, *MRI, TII); // Follow the chain of copies until we find a more suitable source, a phi // or have to abort. @@ -747,14 +708,17 @@ bool PeepholeOptimizer::findNextSource(unsigned Reg, u unsigned NumSrcs = Res.getNumSources(); if (NumSrcs > 1) { PHICount++; + if (PHICount >= RewritePHILimit) { + DEBUG(dbgs() << "findNextSource: PHI limit reached\n"); + return false; + } + for (unsigned i = 0; i < NumSrcs; ++i) - SrcToLook.push_back(TargetInstrInfo::RegSubRegPair( - Res.getSrcReg(i), Res.getSrcSubReg(i))); + SrcToLook.push_back(Res.getSrc(i)); break; } - CurSrcPair.Reg = Res.getSrcReg(0); - CurSrcPair.SubReg = Res.getSrcSubReg(0); + CurSrcPair = Res.getSrc(0); // Do not extend the live-ranges of physical registers as they add // constraints to the register allocator. Moreover, if we want to extend // the live-range of a physical register, unlike SSA virtual register, @@ -764,7 +728,8 @@ bool PeepholeOptimizer::findNextSource(unsigned Reg, u // Keep following the chain if the value isn't any better yet. const TargetRegisterClass *SrcRC = MRI->getRegClass(CurSrcPair.Reg); - if (!TRI->shouldRewriteCopySrc(DefRC, SubReg, SrcRC, CurSrcPair.SubReg)) + if (!TRI->shouldRewriteCopySrc(DefRC, RegSubReg.SubReg, SrcRC, + CurSrcPair.SubReg)) continue; // We currently cannot deal with subreg operands on PHI instructions @@ -775,7 +740,7 @@ bool PeepholeOptimizer::findNextSource(unsigned Reg, u // We found a suitable source, and are done with this chain. break; } - } + } while (!SrcToLook.empty()); // If we did not find a more suitable source, there is nothing to optimize. return CurSrcPair.Reg != Reg; @@ -786,54 +751,50 @@ bool PeepholeOptimizer::findNextSource(unsigned Reg, u /// successfully traverse a PHI instruction and find suitable sources coming /// from its edges. By inserting a new PHI, we provide a rewritten PHI def /// suitable to be used in a new COPY instruction. -static MachineInstr * -insertPHI(MachineRegisterInfo *MRI, const TargetInstrInfo *TII, - const SmallVectorImpl &SrcRegs, - MachineInstr *OrigPHI) { +static MachineInstr & +insertPHI(MachineRegisterInfo &MRI, const TargetInstrInfo &TII, + const SmallVectorImpl &SrcRegs, + MachineInstr &OrigPHI) { assert(!SrcRegs.empty() && "No sources to create a PHI instruction?"); - const TargetRegisterClass *NewRC = MRI->getRegClass(SrcRegs[0].Reg); + const TargetRegisterClass *NewRC = MRI.getRegClass(SrcRegs[0].Reg); // NewRC is only correct if no subregisters are involved. findNextSource() // should have rejected those cases already. assert(SrcRegs[0].SubReg == 0 && "should not have subreg operand"); - unsigned NewVR = MRI->createVirtualRegister(NewRC); - MachineBasicBlock *MBB = OrigPHI->getParent(); - MachineInstrBuilder MIB = BuildMI(*MBB, OrigPHI, OrigPHI->getDebugLoc(), - TII->get(TargetOpcode::PHI), NewVR); + unsigned NewVR = MRI.createVirtualRegister(NewRC); + MachineBasicBlock *MBB = OrigPHI.getParent(); + MachineInstrBuilder MIB = BuildMI(*MBB, &OrigPHI, OrigPHI.getDebugLoc(), + TII.get(TargetOpcode::PHI), NewVR); unsigned MBBOpIdx = 2; - for (auto RegPair : SrcRegs) { + for (const RegSubRegPair &RegPair : SrcRegs) { MIB.addReg(RegPair.Reg, 0, RegPair.SubReg); - MIB.addMBB(OrigPHI->getOperand(MBBOpIdx).getMBB()); + MIB.addMBB(OrigPHI.getOperand(MBBOpIdx).getMBB()); // Since we're extended the lifetime of RegPair.Reg, clear the // kill flags to account for that and make RegPair.Reg reaches // the new PHI. - MRI->clearKillFlags(RegPair.Reg); + MRI.clearKillFlags(RegPair.Reg); MBBOpIdx += 2; } - return MIB; + return *MIB; } namespace { -/// \brief Helper class to rewrite the arguments of a copy-like instruction. -class CopyRewriter { +/// Interface to query instructions amenable to copy rewriting. +class Rewriter { protected: - /// The copy-like instruction. MachineInstr &CopyLike; - - /// The index of the source being rewritten. - unsigned CurrentSrcIdx = 0; - + unsigned CurrentSrcIdx = 0; ///< The index of the source being rewritten. public: - CopyRewriter(MachineInstr &MI) : CopyLike(MI) {} - virtual ~CopyRewriter() = default; + Rewriter(MachineInstr &CopyLike) : CopyLike(CopyLike) {} + virtual ~Rewriter() {} /// \brief Get the next rewritable source (SrcReg, SrcSubReg) and - /// the related value that it affects (TrackReg, TrackSubReg). + /// the related value that it affects (DstReg, DstSubReg). /// A source is considered rewritable if its register class and the - /// register class of the related TrackReg may not be register + /// register class of the related DstReg may not be register /// coalescer friendly. In other words, given a copy-like instruction /// not all the arguments may be returned at rewritable source, since /// some arguments are none to be register coalescer friendly. @@ -848,137 +809,72 @@ class CopyRewriter { (public) /// the only source this instruction has: /// (SrcReg, SrcSubReg) = (src, srcSubIdx). /// This source defines the whole definition, i.e., - /// (TrackReg, TrackSubReg) = (dst, dstSubIdx). + /// (DstReg, DstSubReg) = (dst, dstSubIdx). /// /// The second and subsequent calls will return false, as there is only one /// rewritable source. /// /// \return True if a rewritable source has been found, false otherwise. /// The output arguments are valid if and only if true is returned. - virtual bool getNextRewritableSource(unsigned &SrcReg, unsigned &SrcSubReg, - unsigned &TrackReg, - unsigned &TrackSubReg) { - // If CurrentSrcIdx == 1, this means this function has already been called - // once. CopyLike has one definition and one argument, thus, there is - // nothing else to rewrite. - if (!CopyLike.isCopy() || CurrentSrcIdx == 1) + virtual bool getNextRewritableSource(RegSubRegPair &Src, + RegSubRegPair &Dst) = 0; + + /// Rewrite the current source with \p NewReg and \p NewSubReg if possible. + /// \return True if the rewriting was possible, false otherwise. + virtual bool RewriteCurrentSource(unsigned NewReg, unsigned NewSubReg) = 0; +}; + +/// Rewriter for COPY instructions. +class CopyRewriter : public Rewriter { +public: + CopyRewriter(MachineInstr &MI) : Rewriter(MI) { + assert(MI.isCopy() && "Expected copy instruction"); + } + virtual ~CopyRewriter() = default; + + bool getNextRewritableSource(RegSubRegPair &Src, + RegSubRegPair &Dst) override { + // CurrentSrcIdx > 0 means this function has already been called. + if (CurrentSrcIdx > 0) return false; // This is the first call to getNextRewritableSource. // Move the CurrentSrcIdx to remember that we made that call. CurrentSrcIdx = 1; // The rewritable source is the argument. const MachineOperand &MOSrc = CopyLike.getOperand(1); - SrcReg = MOSrc.getReg(); - SrcSubReg = MOSrc.getSubReg(); + Src = RegSubRegPair(MOSrc.getReg(), MOSrc.getSubReg()); // What we track are the alternative sources of the definition. const MachineOperand &MODef = CopyLike.getOperand(0); - TrackReg = MODef.getReg(); - TrackSubReg = MODef.getSubReg(); + Dst = RegSubRegPair(MODef.getReg(), MODef.getSubReg()); return true; } - /// \brief Rewrite the current source with \p NewReg and \p NewSubReg - /// if possible. - /// \return True if the rewriting was possible, false otherwise. - virtual bool RewriteCurrentSource(unsigned NewReg, unsigned NewSubReg) { - if (!CopyLike.isCopy() || CurrentSrcIdx != 1) + bool RewriteCurrentSource(unsigned NewReg, unsigned NewSubReg) override { + if (CurrentSrcIdx != 1) return false; MachineOperand &MOSrc = CopyLike.getOperand(CurrentSrcIdx); MOSrc.setReg(NewReg); MOSrc.setSubReg(NewSubReg); return true; } - - /// \brief Given a \p Def.Reg and Def.SubReg pair, use \p RewriteMap to find - /// the new source to use for rewrite. If \p HandleMultipleSources is true and - /// multiple sources for a given \p Def are found along the way, we found a - /// PHI instructions that needs to be rewritten. - /// TODO: HandleMultipleSources should be removed once we test PHI handling - /// with coalescable copies. - TargetInstrInfo::RegSubRegPair - getNewSource(MachineRegisterInfo *MRI, const TargetInstrInfo *TII, - TargetInstrInfo::RegSubRegPair Def, - PeepholeOptimizer::RewriteMapTy &RewriteMap, - bool HandleMultipleSources = true) { - TargetInstrInfo::RegSubRegPair LookupSrc(Def.Reg, Def.SubReg); - do { - ValueTrackerResult Res = RewriteMap.lookup(LookupSrc); - // If there are no entries on the map, LookupSrc is the new source. - if (!Res.isValid()) - return LookupSrc; - - // There's only one source for this definition, keep searching... - unsigned NumSrcs = Res.getNumSources(); - if (NumSrcs == 1) { - LookupSrc.Reg = Res.getSrcReg(0); - LookupSrc.SubReg = Res.getSrcSubReg(0); - continue; - } - - // TODO: Remove once multiple srcs w/ coalescable copies are supported. - if (!HandleMultipleSources) - break; - - // Multiple sources, recurse into each source to find a new source - // for it. Then, rewrite the PHI accordingly to its new edges. - SmallVector NewPHISrcs; - for (unsigned i = 0; i < NumSrcs; ++i) { - TargetInstrInfo::RegSubRegPair PHISrc(Res.getSrcReg(i), - Res.getSrcSubReg(i)); - NewPHISrcs.push_back( - getNewSource(MRI, TII, PHISrc, RewriteMap, HandleMultipleSources)); - } - - // Build the new PHI node and return its def register as the new source. - MachineInstr *OrigPHI = const_cast(Res.getInst()); - MachineInstr *NewPHI = insertPHI(MRI, TII, NewPHISrcs, OrigPHI); - DEBUG(dbgs() << "-- getNewSource\n"); - DEBUG(dbgs() << " Replacing: " << *OrigPHI); - DEBUG(dbgs() << " With: " << *NewPHI); - const MachineOperand &MODef = NewPHI->getOperand(0); - return TargetInstrInfo::RegSubRegPair(MODef.getReg(), MODef.getSubReg()); - - } while (true); - - return TargetInstrInfo::RegSubRegPair(0, 0); - } - - /// \brief Rewrite the source found through \p Def, by using the \p RewriteMap - /// and create a new COPY instruction. More info about RewriteMap in - /// PeepholeOptimizer::findNextSource. Right now this is only used to handle - /// Uncoalescable copies, since they are copy like instructions that aren't - /// recognized by the register allocator. - virtual MachineInstr * - RewriteSource(TargetInstrInfo::RegSubRegPair Def, - PeepholeOptimizer::RewriteMapTy &RewriteMap) { - return nullptr; - } }; /// \brief Helper class to rewrite uncoalescable copy like instructions /// into new COPY (coalescable friendly) instructions. -class UncoalescableRewriter : public CopyRewriter { -protected: - const TargetInstrInfo &TII; - MachineRegisterInfo &MRI; +class UncoalescableRewriter : public Rewriter { + unsigned NumDefs; ///< Number of defs in the bitcast. - /// The number of defs in the bitcast - unsigned NumDefs; - public: - UncoalescableRewriter(MachineInstr &MI, const TargetInstrInfo &TII, - MachineRegisterInfo &MRI) - : CopyRewriter(MI), TII(TII), MRI(MRI) { + UncoalescableRewriter(MachineInstr &MI) : Rewriter(MI) { NumDefs = MI.getDesc().getNumDefs(); } - /// \brief Get the next rewritable def source (TrackReg, TrackSubReg) + /// \see See Rewriter::getNextRewritableSource() /// All such sources need to be considered rewritable in order to /// rewrite a uncoalescable copy-like instruction. This method return /// each definition that must be checked if rewritable. - bool getNextRewritableSource(unsigned &SrcReg, unsigned &SrcSubReg, - unsigned &TrackReg, - unsigned &TrackSubReg) override { + bool getNextRewritableSource(RegSubRegPair &Src, + RegSubRegPair &Dst) override { // Find the next non-dead definition and continue from there. if (CurrentSrcIdx == NumDefs) return false; @@ -990,64 +886,27 @@ class UncoalescableRewriter : public CopyRewriter { (p } // What we track are the alternative sources of the definition. + Src = RegSubRegPair(0, 0); const MachineOperand &MODef = CopyLike.getOperand(CurrentSrcIdx); - TrackReg = MODef.getReg(); - TrackSubReg = MODef.getSubReg(); + Dst = RegSubRegPair(MODef.getReg(), MODef.getSubReg()); CurrentSrcIdx++; return true; } - /// \brief Rewrite the source found through \p Def, by using the \p RewriteMap - /// and create a new COPY instruction. More info about RewriteMap in - /// PeepholeOptimizer::findNextSource. Right now this is only used to handle - /// Uncoalescable copies, since they are copy like instructions that aren't - /// recognized by the register allocator. - MachineInstr * - RewriteSource(TargetInstrInfo::RegSubRegPair Def, - PeepholeOptimizer::RewriteMapTy &RewriteMap) override { - assert(!TargetRegisterInfo::isPhysicalRegister(Def.Reg) && - "We do not rewrite physical registers"); - - // Find the new source to use in the COPY rewrite. - TargetInstrInfo::RegSubRegPair NewSrc = - getNewSource(&MRI, &TII, Def, RewriteMap); - - // Insert the COPY. - const TargetRegisterClass *DefRC = MRI.getRegClass(Def.Reg); - unsigned NewVR = MRI.createVirtualRegister(DefRC); - - MachineInstr *NewCopy = - BuildMI(*CopyLike.getParent(), &CopyLike, CopyLike.getDebugLoc(), - TII.get(TargetOpcode::COPY), NewVR) - .addReg(NewSrc.Reg, 0, NewSrc.SubReg); - - NewCopy->getOperand(0).setSubReg(Def.SubReg); - if (Def.SubReg) - NewCopy->getOperand(0).setIsUndef(); - - DEBUG(dbgs() << "-- RewriteSource\n"); - DEBUG(dbgs() << " Replacing: " << CopyLike); - DEBUG(dbgs() << " With: " << *NewCopy); - MRI.replaceRegWith(Def.Reg, NewVR); - MRI.clearKillFlags(NewVR); - - // We extended the lifetime of NewSrc.Reg, clear the kill flags to - // account for that. - MRI.clearKillFlags(NewSrc.Reg); - - return NewCopy; + bool RewriteCurrentSource(unsigned NewReg, unsigned NewSubReg) override { + return false; } }; -/// \brief Specialized rewriter for INSERT_SUBREG instruction. -class InsertSubregRewriter : public CopyRewriter { +/// Specialized rewriter for INSERT_SUBREG instruction. +class InsertSubregRewriter : public Rewriter { public: - InsertSubregRewriter(MachineInstr &MI) : CopyRewriter(MI) { + InsertSubregRewriter(MachineInstr &MI) : Rewriter(MI) { assert(MI.isInsertSubreg() && "Invalid instruction"); } - /// \brief See CopyRewriter::getNextRewritableSource. + /// \see See Rewriter::getNextRewritableSource() /// Here CopyLike has the following form: /// dst = INSERT_SUBREG Src1, Src2.src2SubIdx, subIdx. /// Src1 has the same register class has dst, hence, there is @@ -1055,29 +914,27 @@ class InsertSubregRewriter : public CopyRewriter { (pu /// Src2.src2SubIdx, may not be register coalescer friendly. /// Therefore, the first call to this method returns: /// (SrcReg, SrcSubReg) = (Src2, src2SubIdx). - /// (TrackReg, TrackSubReg) = (dst, subIdx). + /// (DstReg, DstSubReg) = (dst, subIdx). /// /// Subsequence calls will return false. - bool getNextRewritableSource(unsigned &SrcReg, unsigned &SrcSubReg, - unsigned &TrackReg, - unsigned &TrackSubReg) override { + bool getNextRewritableSource(RegSubRegPair &Src, + RegSubRegPair &Dst) override { // If we already get the only source we can rewrite, return false. if (CurrentSrcIdx == 2) return false; // We are looking at v2 = INSERT_SUBREG v0, v1, sub0. CurrentSrcIdx = 2; const MachineOperand &MOInsertedReg = CopyLike.getOperand(2); - SrcReg = MOInsertedReg.getReg(); - SrcSubReg = MOInsertedReg.getSubReg(); + Src = RegSubRegPair(MOInsertedReg.getReg(), MOInsertedReg.getSubReg()); const MachineOperand &MODef = CopyLike.getOperand(0); // We want to track something that is compatible with the // partial definition. - TrackReg = MODef.getReg(); if (MODef.getSubReg()) // Bail if we have to compose sub-register indices. return false; - TrackSubReg = (unsigned)CopyLike.getOperand(3).getImm(); + Dst = RegSubRegPair(MODef.getReg(), + (unsigned)CopyLike.getOperand(3).getImm()); return true; } @@ -1092,41 +949,39 @@ class InsertSubregRewriter : public CopyRewriter { (pu } }; -/// \brief Specialized rewriter for EXTRACT_SUBREG instruction. -class ExtractSubregRewriter : public CopyRewriter { +/// Specialized rewriter for EXTRACT_SUBREG instruction. +class ExtractSubregRewriter : public Rewriter { const TargetInstrInfo &TII; public: ExtractSubregRewriter(MachineInstr &MI, const TargetInstrInfo &TII) - : CopyRewriter(MI), TII(TII) { + : Rewriter(MI), TII(TII) { assert(MI.isExtractSubreg() && "Invalid instruction"); } - /// \brief See CopyRewriter::getNextRewritableSource. + /// \see Rewriter::getNextRewritableSource() /// Here CopyLike has the following form: /// dst.dstSubIdx = EXTRACT_SUBREG Src, subIdx. /// There is only one rewritable source: Src.subIdx, /// which defines dst.dstSubIdx. - bool getNextRewritableSource(unsigned &SrcReg, unsigned &SrcSubReg, - unsigned &TrackReg, - unsigned &TrackSubReg) override { + bool getNextRewritableSource(RegSubRegPair &Src, + RegSubRegPair &Dst) override { // If we already get the only source we can rewrite, return false. if (CurrentSrcIdx == 1) return false; // We are looking at v1 = EXTRACT_SUBREG v0, sub0. CurrentSrcIdx = 1; const MachineOperand &MOExtractedReg = CopyLike.getOperand(1); - SrcReg = MOExtractedReg.getReg(); // If we have to compose sub-register indices, bail out. if (MOExtractedReg.getSubReg()) return false; - SrcSubReg = CopyLike.getOperand(2).getImm(); + Src = RegSubRegPair(MOExtractedReg.getReg(), + CopyLike.getOperand(2).getImm()); // We want to track something that is compatible with the definition. const MachineOperand &MODef = CopyLike.getOperand(0); - TrackReg = MODef.getReg(); - TrackSubReg = MODef.getSubReg(); + Dst = RegSubRegPair(MODef.getReg(), MODef.getSubReg()); return true; } @@ -1156,14 +1011,14 @@ class ExtractSubregRewriter : public CopyRewriter { (p } }; -/// \brief Specialized rewriter for REG_SEQUENCE instruction. -class RegSequenceRewriter : public CopyRewriter { +/// Specialized rewriter for REG_SEQUENCE instruction. +class RegSequenceRewriter : public Rewriter { public: - RegSequenceRewriter(MachineInstr &MI) : CopyRewriter(MI) { + RegSequenceRewriter(MachineInstr &MI) : Rewriter(MI) { assert(MI.isRegSequence() && "Invalid instruction"); } - /// \brief See CopyRewriter::getNextRewritableSource. + /// \see Rewriter::getNextRewritableSource() /// Here CopyLike has the following form: /// dst = REG_SEQUENCE Src1.src1SubIdx, subIdx1, Src2.src2SubIdx, subIdx2. /// Each call will return a different source, walking all the available @@ -1171,17 +1026,16 @@ class RegSequenceRewriter : public CopyRewriter { (pub /// /// The first call returns: /// (SrcReg, SrcSubReg) = (Src1, src1SubIdx). - /// (TrackReg, TrackSubReg) = (dst, subIdx1). + /// (DstReg, DstSubReg) = (dst, subIdx1). /// /// The second call returns: /// (SrcReg, SrcSubReg) = (Src2, src2SubIdx). - /// (TrackReg, TrackSubReg) = (dst, subIdx2). + /// (DstReg, DstSubReg) = (dst, subIdx2). /// /// And so on, until all the sources have been traversed, then /// it returns false. - bool getNextRewritableSource(unsigned &SrcReg, unsigned &SrcSubReg, - unsigned &TrackReg, - unsigned &TrackSubReg) override { + bool getNextRewritableSource(RegSubRegPair &Src, + RegSubRegPair &Dst) override { // We are looking at v0 = REG_SEQUENCE v1, sub1, v2, sub2, etc. // If this is the first call, move to the first argument. @@ -1194,17 +1048,17 @@ class RegSequenceRewriter : public CopyRewriter { (pub return false; } const MachineOperand &MOInsertedReg = CopyLike.getOperand(CurrentSrcIdx); - SrcReg = MOInsertedReg.getReg(); + Src.Reg = MOInsertedReg.getReg(); // If we have to compose sub-register indices, bail out. - if ((SrcSubReg = MOInsertedReg.getSubReg())) + if ((Src.SubReg = MOInsertedReg.getSubReg())) return false; // We want to track something that is compatible with the related // partial definition. - TrackSubReg = CopyLike.getOperand(CurrentSrcIdx + 1).getImm(); + Dst.SubReg = CopyLike.getOperand(CurrentSrcIdx + 1).getImm(); const MachineOperand &MODef = CopyLike.getOperand(0); - TrackReg = MODef.getReg(); + Dst.Reg = MODef.getReg(); // If we have to compose sub-registers, bail. return MODef.getSubReg() == 0; } @@ -1224,16 +1078,14 @@ class RegSequenceRewriter : public CopyRewriter { (pub } // end anonymous namespace -/// \brief Get the appropriated CopyRewriter for \p MI. -/// \return A pointer to a dynamically allocated CopyRewriter or nullptr -/// if no rewriter works for \p MI. -static CopyRewriter *getCopyRewriter(MachineInstr &MI, - const TargetInstrInfo &TII, - MachineRegisterInfo &MRI) { +/// Get the appropriated Rewriter for \p MI. +/// \return A pointer to a dynamically allocated Rewriter or nullptr if no +/// rewriter works for \p MI. +static Rewriter *getCopyRewriter(MachineInstr &MI, const TargetInstrInfo &TII) { // Handle uncoalescable copy-like instructions. - if (MI.isBitcast() || (MI.isRegSequenceLike() || MI.isInsertSubregLike() || - MI.isExtractSubregLike())) - return new UncoalescableRewriter(MI, TII, MRI); + if (MI.isBitcast() || MI.isRegSequenceLike() || MI.isInsertSubregLike() || + MI.isExtractSubregLike()) + return new UncoalescableRewriter(MI); switch (MI.getOpcode()) { default: @@ -1247,53 +1099,102 @@ static CopyRewriter *getCopyRewriter(MachineInstr &MI, case TargetOpcode::REG_SEQUENCE: return new RegSequenceRewriter(MI); } - llvm_unreachable(nullptr); } -/// \brief Optimize generic copy instructions to avoid cross -/// register bank copy. The optimization looks through a chain of -/// copies and tries to find a source that has a compatible register -/// class. -/// Two register classes are considered to be compatible if they share -/// the same register bank. +/// \brief Given a \p Def.Reg and Def.SubReg pair, use \p RewriteMap to find +/// the new source to use for rewrite. If \p HandleMultipleSources is true and +/// multiple sources for a given \p Def are found along the way, we found a +/// PHI instructions that needs to be rewritten. +/// TODO: HandleMultipleSources should be removed once we test PHI handling +/// with coalescable copies. *** DIFF OUTPUT TRUNCATED AT 1000 LINES ***