diff options
Diffstat (limited to 'contrib/llvm/lib/CodeGen/PeepholeOptimizer.cpp')
| -rw-r--r-- | contrib/llvm/lib/CodeGen/PeepholeOptimizer.cpp | 1017 |
1 files changed, 750 insertions, 267 deletions
diff --git a/contrib/llvm/lib/CodeGen/PeepholeOptimizer.cpp b/contrib/llvm/lib/CodeGen/PeepholeOptimizer.cpp index ebe05e3..52b42b6 100644 --- a/contrib/llvm/lib/CodeGen/PeepholeOptimizer.cpp +++ b/contrib/llvm/lib/CodeGen/PeepholeOptimizer.cpp @@ -43,7 +43,7 @@ // - Optimize Loads: // // Loads that can be folded into a later instruction. A load is foldable -// if it loads to virtual registers and the virtual register defined has +// if it loads to virtual registers and the virtual register defined has // a single use. // // - Optimize Copies and Bitcast (more generally, target specific copies): @@ -98,6 +98,16 @@ static cl::opt<bool> DisableAdvCopyOpt("disable-adv-copy-opt", cl::Hidden, cl::init(false), cl::desc("Disable advanced copy optimization")); +static cl::opt<bool> DisableNAPhysCopyOpt( + "disable-non-allocatable-phys-copy-opt", cl::Hidden, cl::init(false), + cl::desc("Disable non-allocatable physical register copy optimization")); + +// Limit the number of PHI instructions to process +// in PeepholeOptimizer::getNextSource. +static cl::opt<unsigned> RewritePHILimit( + "rewrite-phi-limit", cl::Hidden, cl::init(10), + cl::desc("Limit the length of PHI chains to lookup")); + STATISTIC(NumReuse, "Number of extension results reused"); STATISTIC(NumCmps, "Number of compares eliminated"); STATISTIC(NumImmFold, "Number of move immediate folded"); @@ -105,8 +115,11 @@ 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"); namespace { + class ValueTrackerResult; + class PeepholeOptimizer : public MachineFunctionPass { const TargetInstrInfo *TII; const TargetRegisterInfo *TRI; @@ -130,6 +143,10 @@ namespace { } } + /// \brief Track Def -> Use info used for rewriting copies. + typedef SmallDenseMap<TargetInstrInfo::RegSubRegPair, ValueTrackerResult> + RewriteMapTy; + private: bool optimizeCmpInstr(MachineInstr *MI, MachineBasicBlock *MBB); bool optimizeExtInstr(MachineInstr *MI, MachineBasicBlock *MBB, @@ -137,17 +154,38 @@ namespace { bool optimizeSelect(MachineInstr *MI, SmallPtrSetImpl<MachineInstr *> &LocalMIs); bool optimizeCondBranch(MachineInstr *MI); - bool optimizeCopyOrBitcast(MachineInstr *MI); bool optimizeCoalescableCopy(MachineInstr *MI); bool optimizeUncoalescableCopy(MachineInstr *MI, SmallPtrSetImpl<MachineInstr *> &LocalMIs); - bool findNextSource(unsigned &Reg, unsigned &SubReg); + bool findNextSource(unsigned Reg, unsigned SubReg, + RewriteMapTy &RewriteMap); bool isMoveImmediate(MachineInstr *MI, SmallSet<unsigned, 4> &ImmDefRegs, DenseMap<unsigned, MachineInstr*> &ImmDefMIs); bool foldImmediate(MachineInstr *MI, MachineBasicBlock *MBB, SmallSet<unsigned, 4> &ImmDefRegs, DenseMap<unsigned, MachineInstr*> &ImmDefMIs); + + /// \brief If copy instruction \p MI is a virtual register copy, track it in + /// 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, + SmallSet<unsigned, 4> &CopySrcRegs, + DenseMap<unsigned, MachineInstr *> &CopyMIs); + + /// \brief 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 + /// register copy, track it in the \p NAPhysToVirtMIs map. If this + /// 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, + DenseMap<unsigned, MachineInstr *> &NAPhysToVirtMIs); + bool isLoadFoldable(MachineInstr *MI, SmallSet<unsigned, 16> &FoldAsLoadDefCandidates); @@ -171,6 +209,69 @@ namespace { } }; + /// \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. + class ValueTrackerResult { + private: + /// Track all sources found by one ValueTracker query. + SmallVector<TargetInstrInfo::RegSubRegPair, 2> RegSrcs; + + /// Instruction using the sources in 'RegSrcs'. + const MachineInstr *Inst; + + public: + ValueTrackerResult() : Inst(nullptr) {} + ValueTrackerResult(unsigned Reg, unsigned SubReg) : Inst(nullptr) { + addSource(Reg, SubReg); + } + + bool isValid() const { return getNumSources() > 0; } + + void setInst(const MachineInstr *I) { Inst = I; } + const MachineInstr *getInst() const { return Inst; } + + void clear() { + RegSrcs.clear(); + Inst = nullptr; + } + + void addSource(unsigned SrcReg, unsigned SrcSubReg) { + RegSrcs.push_back(TargetInstrInfo::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); + } + + int getNumSources() const { return RegSrcs.size(); } + + unsigned getSrcReg(int Idx) const { + assert(Idx < getNumSources() && "Reg source out of index"); + return RegSrcs[Idx].Reg; + } + + unsigned getSrcSubReg(int Idx) const { + assert(Idx < getNumSources() && "SubReg source out of index"); + return RegSrcs[Idx].SubReg; + } + + bool operator==(const ValueTrackerResult &Other) { + if (Other.getInst() != getInst()) + return false; + + if (Other.getNumSources() != getNumSources()) + return false; + + for (int i = 0, e = Other.getNumSources(); i != e; ++i) + if (Other.getSrcReg(i) != getSrcReg(i) || + Other.getSrcSubReg(i) != getSrcSubReg(i)) + return false; + return true; + } + }; + /// \brief Helper class to track the possible sources of a value defined by /// a (chain of) copy related instructions. /// Given a definition (instruction and definition index), this class @@ -213,23 +314,25 @@ namespace { /// \brief Dispatcher to the right underlying implementation of /// getNextSource. - bool getNextSourceImpl(unsigned &SrcReg, unsigned &SrcSubReg); + ValueTrackerResult getNextSourceImpl(); /// \brief Specialized version of getNextSource for Copy instructions. - bool getNextSourceFromCopy(unsigned &SrcReg, unsigned &SrcSubReg); + ValueTrackerResult getNextSourceFromCopy(); /// \brief Specialized version of getNextSource for Bitcast instructions. - bool getNextSourceFromBitcast(unsigned &SrcReg, unsigned &SrcSubReg); + ValueTrackerResult getNextSourceFromBitcast(); /// \brief Specialized version of getNextSource for RegSequence /// instructions. - bool getNextSourceFromRegSequence(unsigned &SrcReg, unsigned &SrcSubReg); + ValueTrackerResult getNextSourceFromRegSequence(); /// \brief Specialized version of getNextSource for InsertSubreg /// instructions. - bool getNextSourceFromInsertSubreg(unsigned &SrcReg, unsigned &SrcSubReg); + ValueTrackerResult getNextSourceFromInsertSubreg(); /// \brief Specialized version of getNextSource for ExtractSubreg /// instructions. - bool getNextSourceFromExtractSubreg(unsigned &SrcReg, unsigned &SrcSubReg); + ValueTrackerResult getNextSourceFromExtractSubreg(); /// \brief Specialized version of getNextSource for SubregToReg /// instructions. - bool getNextSourceFromSubregToReg(unsigned &SrcReg, unsigned &SrcSubReg); + ValueTrackerResult getNextSourceFromSubregToReg(); + /// \brief Specialized version of getNextSource for PHI instructions. + ValueTrackerResult getNextSourceFromPHI(); public: /// \brief Create a ValueTracker instance for the value defined by \p Reg. @@ -276,16 +379,10 @@ namespace { /// \brief Following the use-def chain, get the next available source /// for the tracked value. - /// When the returned value is not nullptr, \p SrcReg gives the register - /// that contain the tracked value. - /// \note The sub register index returned in \p SrcSubReg must be used - /// on \p SrcReg to access the actual value. - /// \return Unless the returned value is nullptr (i.e., no source found), - /// \p SrcReg gives the register of the next source used in the returned - /// instruction and \p SrcSubReg the sub-register index to be used on that - /// source to get the tracked value. When nullptr is returned, no - /// alternative source has been found. - const MachineInstr *getNextSource(unsigned &SrcReg, unsigned &SrcSubReg); + /// \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. @@ -303,11 +400,10 @@ INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) INITIALIZE_PASS_END(PeepholeOptimizer, "peephole-opts", "Peephole Optimizations", false, false) -/// optimizeExtInstr - 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 source value is preserved as a sub-register of the -/// result, then replace all reachable uses of the source with the subreg of the -/// result. +/// 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 +/// source value is preserved as a sub-register of the result, then replace all +/// reachable uses of the source with the subreg of the result. /// /// Do not generate an EXTRACT that is used only in a debug use, as this changes /// the code. Since this code does not currently share EXTRACTs, just ignore all @@ -458,10 +554,10 @@ optimizeExtInstr(MachineInstr *MI, MachineBasicBlock *MBB, return Changed; } -/// optimizeCmpInstr - If the instruction is a compare and the previous -/// instruction it's comparing against all ready 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. +/// If the instruction is a compare and the previous instruction it's comparing +/// 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) { // If this instruction is a comparison against zero and isn't comparing a @@ -506,88 +602,138 @@ bool PeepholeOptimizer::optimizeCondBranch(MachineInstr *MI) { return TII->optimizeCondBranch(MI); } -/// \brief Check if the registers defined by the pair (RegisterClass, SubReg) -/// share the same register file. -static bool shareSameRegisterFile(const TargetRegisterInfo &TRI, - const TargetRegisterClass *DefRC, - unsigned DefSubReg, - const TargetRegisterClass *SrcRC, - unsigned SrcSubReg) { - // Same register class. - if (DefRC == SrcRC) - return true; - - // Both operands are sub registers. Check if they share a register class. - unsigned SrcIdx, DefIdx; - if (SrcSubReg && DefSubReg) - return TRI.getCommonSuperRegClass(SrcRC, SrcSubReg, DefRC, DefSubReg, - SrcIdx, DefIdx) != nullptr; - // At most one of the register is a sub register, make it Src to avoid - // duplicating the test. - if (!SrcSubReg) { - std::swap(DefSubReg, SrcSubReg); - std::swap(DefRC, SrcRC); - } - - // One of the register is a sub register, check if we can get a superclass. - if (SrcSubReg) - return TRI.getMatchingSuperRegClass(SrcRC, DefRC, SrcSubReg) != nullptr; - // Plain copy. - return TRI.getCommonSubClass(DefRC, SrcRC) != nullptr; -} - /// \brief Try to find the next source that share the same register file /// for the value defined by \p Reg and \p SubReg. -/// When true is returned, \p Reg and \p SubReg are updated with the -/// register number and sub-register index of the new source. +/// When true is returned, the \p RewriteMap can be used by the client to +/// retrieve all Def -> Use along the way up to the next source. Any found +/// Use that is not itself a key for another entry, is the next source to +/// use. During the search for the next source, multiple sources can be found +/// given multiple incoming sources of a PHI instruction. In this case, we +/// look in each PHI source for the next source; all found next sources must +/// 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(unsigned Reg, unsigned SubReg, + 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. if (TargetRegisterInfo::isPhysicalRegister(Reg)) return false; - const TargetRegisterClass *DefRC = MRI->getRegClass(Reg); - unsigned DefSubReg = SubReg; - - unsigned Src; - unsigned SrcSubReg; - bool ShouldRewrite = false; - - // Follow the chain of copies until we reach the top of the use-def chain - // or find a more suitable source. - ValueTracker ValTracker(Reg, DefSubReg, *MRI, !DisableAdvCopyOpt, TII); - do { - unsigned CopySrcReg, CopySrcSubReg; - if (!ValTracker.getNextSource(CopySrcReg, CopySrcSubReg)) - break; - Src = CopySrcReg; - SrcSubReg = CopySrcSubReg; - - // 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, we will have to check that they are not - // redefine before the related use. - if (TargetRegisterInfo::isPhysicalRegister(Src)) - break; - const TargetRegisterClass *SrcRC = MRI->getRegClass(Src); + SmallVector<TargetInstrInfo::RegSubRegPair, 4> SrcToLook; + TargetInstrInfo::RegSubRegPair CurSrcPair(Reg, SubReg); + SrcToLook.push_back(CurSrcPair); + + unsigned PHICount = 0; + while (!SrcToLook.empty() && PHICount < RewritePHILimit) { + TargetInstrInfo::RegSubRegPair Pair = SrcToLook.pop_back_val(); + // As explained above, do not handle physical registers + if (TargetRegisterInfo::isPhysicalRegister(Pair.Reg)) + return false; - // If this source does not incur a cross register bank copy, use it. - ShouldRewrite = shareSameRegisterFile(*TRI, DefRC, DefSubReg, SrcRC, - SrcSubReg); - } while (!ShouldRewrite); + CurSrcPair = Pair; + ValueTracker ValTracker(CurSrcPair.Reg, CurSrcPair.SubReg, *MRI, + !DisableAdvCopyOpt, TII); + ValueTrackerResult Res; + bool ShouldRewrite = false; + + do { + // Follow the chain of copies until we reach the top of the use-def chain + // or find a more suitable source. + Res = ValTracker.getNextSource(); + if (!Res.isValid()) + break; + + // Insert the Def -> Use entry for the recently found source. + ValueTrackerResult CurSrcRes = RewriteMap.lookup(CurSrcPair); + if (CurSrcRes.isValid()) { + assert(CurSrcRes == Res && "ValueTrackerResult found must match"); + // An existent entry with multiple sources is a PHI cycle we must avoid. + // Otherwise it's an entry with a valid next source we already found. + if (CurSrcRes.getNumSources() > 1) { + DEBUG(dbgs() << "findNextSource: found PHI cycle, aborting...\n"); + return false; + } + break; + } + RewriteMap.insert(std::make_pair(CurSrcPair, Res)); + + // ValueTrackerResult usually have one source unless it's the result from + // a PHI instruction. Add the found PHI edges to be looked up further. + unsigned NumSrcs = Res.getNumSources(); + if (NumSrcs > 1) { + PHICount++; + for (unsigned i = 0; i < NumSrcs; ++i) + SrcToLook.push_back(TargetInstrInfo::RegSubRegPair( + Res.getSrcReg(i), Res.getSrcSubReg(i))); + break; + } - // If we did not find a more suitable source, there is nothing to optimize. - if (!ShouldRewrite || Src == Reg) + CurSrcPair.Reg = Res.getSrcReg(0); + CurSrcPair.SubReg = Res.getSrcSubReg(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, + // we will have to check that they aren't redefine before the related use. + if (TargetRegisterInfo::isPhysicalRegister(CurSrcPair.Reg)) + return false; + + const TargetRegisterClass *SrcRC = MRI->getRegClass(CurSrcPair.Reg); + ShouldRewrite = TRI->shouldRewriteCopySrc(DefRC, SubReg, SrcRC, + CurSrcPair.SubReg); + } while (!ShouldRewrite); + + // Continue looking for new sources... + if (Res.isValid()) + continue; + + // Do not continue searching for a new source if the there's at least + // one use-def which cannot be rewritten. + if (!ShouldRewrite) + return false; + } + + if (PHICount >= RewritePHILimit) { + DEBUG(dbgs() << "findNextSource: PHI limit reached\n"); return false; + } - Reg = Src; - SubReg = SrcSubReg; - return true; + // If we did not find a more suitable source, there is nothing to optimize. + return CurSrcPair.Reg != Reg; +} + +/// \brief Insert a PHI instruction with incoming edges \p SrcRegs that are +/// guaranteed to have the same register class. This is necessary whenever we +/// 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<TargetInstrInfo::RegSubRegPair> &SrcRegs, + MachineInstr *OrigPHI) { + assert(!SrcRegs.empty() && "No sources to create a PHI instruction?"); + + const TargetRegisterClass *NewRC = MRI->getRegClass(SrcRegs[0].Reg); + 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) { + MIB.addReg(RegPair.Reg, 0, RegPair.SubReg); + 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); + MBBOpIdx += 2; + } + + return MIB; } namespace { @@ -624,7 +770,7 @@ public: /// This source defines the whole definition, i.e., /// (TrackReg, TrackSubReg) = (dst, dstSubIdx). /// - /// The second and subsequent calls will return false, has there is only one + /// 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. @@ -632,9 +778,9 @@ public: 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 defintiion and one argument, thus, - // there is nothing else to rewrite. + // 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) return false; // This is the first call to getNextRewritableSource. @@ -653,7 +799,7 @@ public: /// \brief Rewrite the current source with \p NewReg and \p NewSubReg /// if possible. - /// \return True if the rewritting was possible, false otherwise. + /// \return True if the rewriting was possible, false otherwise. virtual bool RewriteCurrentSource(unsigned NewReg, unsigned NewSubReg) { if (!CopyLike.isCopy() || CurrentSrcIdx != 1) return false; @@ -662,6 +808,157 @@ public: 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<TargetInstrInfo::RegSubRegPair, 4> 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<MachineInstr *>(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 (1); + + 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; + /// The number of defs in the bitcast + unsigned NumDefs; + +public: + UncoalescableRewriter(MachineInstr &MI, const TargetInstrInfo &TII, + MachineRegisterInfo &MRI) + : CopyRewriter(MI), TII(TII), MRI(MRI) { + NumDefs = MI.getDesc().getNumDefs(); + } + + /// \brief Get the next rewritable def source (TrackReg, TrackSubReg) + /// 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 { + // Find the next non-dead definition and continue from there. + if (CurrentSrcIdx == NumDefs) + return false; + + while (CopyLike.getOperand(CurrentSrcIdx).isDead()) { + ++CurrentSrcIdx; + if (CurrentSrcIdx == NumDefs) + return false; + } + + // What we track are the alternative sources of the definition. + const MachineOperand &MODef = CopyLike.getOperand(CurrentSrcIdx); + TrackReg = MODef.getReg(); + TrackSubReg = 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; + } }; /// \brief Specialized rewriter for INSERT_SUBREG instruction. @@ -699,7 +996,7 @@ public: // partial definition. TrackReg = MODef.getReg(); if (MODef.getSubReg()) - // Bails if we have to compose sub-register indices. + // Bail if we have to compose sub-register indices. return false; TrackSubReg = (unsigned)CopyLike.getOperand(3).getImm(); return true; @@ -740,7 +1037,7 @@ public: CurrentSrcIdx = 1; const MachineOperand &MOExtractedReg = CopyLike.getOperand(1); SrcReg = MOExtractedReg.getReg(); - // If we have to compose sub-register indices, bails out. + // If we have to compose sub-register indices, bail out. if (MOExtractedReg.getSubReg()) return false; @@ -818,7 +1115,7 @@ public: } const MachineOperand &MOInsertedReg = CopyLike.getOperand(CurrentSrcIdx); SrcReg = MOInsertedReg.getReg(); - // If we have to compose sub-register indices, bails out. + // If we have to compose sub-register indices, bail out. if ((SrcSubReg = MOInsertedReg.getSubReg())) return false; @@ -828,7 +1125,7 @@ public: const MachineOperand &MODef = CopyLike.getOperand(0); TrackReg = MODef.getReg(); - // If we have to compose sub-registers, bails. + // If we have to compose sub-registers, bail. return MODef.getSubReg() == 0; } @@ -850,7 +1147,13 @@ public: /// \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) { + const TargetInstrInfo &TII, + MachineRegisterInfo &MRI) { + // Handle uncoalescable copy-like instructions. + if (MI.isBitcast() || (MI.isRegSequenceLike() || MI.isInsertSubregLike() || + MI.isExtractSubregLike())) + return new UncoalescableRewriter(MI, TII, MRI); + switch (MI.getOpcode()) { default: return nullptr; @@ -874,7 +1177,7 @@ static CopyRewriter *getCopyRewriter(MachineInstr &MI, /// the same register bank. /// New copies issued by this optimization are register allocator /// friendly. This optimization does not remove any copy as it may -/// overconstraint the register allocator, but replaces some operands +/// overconstrain the register allocator, but replaces some operands /// when possible. /// \pre isCoalescableCopy(*MI) is true. /// \return True, when \p MI has been rewritten. False otherwise. @@ -889,25 +1192,33 @@ bool PeepholeOptimizer::optimizeCoalescableCopy(MachineInstr *MI) { bool Changed = false; // Get the right rewriter for the current copy. - std::unique_ptr<CopyRewriter> CpyRewriter(getCopyRewriter(*MI, *TII)); - // If none exists, bails out. + std::unique_ptr<CopyRewriter> CpyRewriter(getCopyRewriter(*MI, *TII, *MRI)); + // If none exists, bail out. if (!CpyRewriter) return false; // Rewrite each rewritable source. unsigned SrcReg, SrcSubReg, TrackReg, TrackSubReg; while (CpyRewriter->getNextRewritableSource(SrcReg, SrcSubReg, TrackReg, TrackSubReg)) { - unsigned NewSrc = TrackReg; - unsigned NewSubReg = TrackSubReg; - // Try to find a more suitable source. - // If we failed to do so, or get the actual source, - // move to the next source. - if (!findNextSource(NewSrc, NewSubReg) || SrcReg == NewSrc) + // Keep track of PHI nodes and its incoming edges when looking for sources. + RewriteMapTy RewriteMap; + // Try to find a more suitable source. If we failed to do so, or get the + // actual source, move to the next source. + if (!findNextSource(TrackReg, TrackSubReg, RewriteMap)) + continue; + + // Get the new source to rewrite. TODO: Only enable handling of multiple + // sources (PHIs) once we have a motivating example and testcases for it. + TargetInstrInfo::RegSubRegPair TrackPair(TrackReg, TrackSubReg); + TargetInstrInfo::RegSubRegPair NewSrc = CpyRewriter->getNewSource( + MRI, TII, TrackPair, RewriteMap, false /* multiple sources */); + if (SrcReg == NewSrc.Reg || NewSrc.Reg == 0) continue; + // Rewrite source. - if (CpyRewriter->RewriteCurrentSource(NewSrc, NewSubReg)) { + if (CpyRewriter->RewriteCurrentSource(NewSrc.Reg, NewSrc.SubReg)) { // We may have extended the live-range of NewSrc, account for that. - MRI->clearKillFlags(NewSrc); + MRI->clearKillFlags(NewSrc.Reg); Changed = true; } } @@ -936,61 +1247,53 @@ bool PeepholeOptimizer::optimizeUncoalescableCopy( assert(MI && isUncoalescableCopy(*MI) && "Invalid argument"); // Check if we can rewrite all the values defined by this instruction. - SmallVector< - std::pair<TargetInstrInfo::RegSubRegPair, TargetInstrInfo::RegSubRegPair>, - 4> RewritePairs; - for (const MachineOperand &MODef : MI->defs()) { - if (MODef.isDead()) - // We can ignore those. - continue; + SmallVector<TargetInstrInfo::RegSubRegPair, 4> RewritePairs; + // Get the right rewriter for the current copy. + std::unique_ptr<CopyRewriter> CpyRewriter(getCopyRewriter(*MI, *TII, *MRI)); + // If none exists, bail out. + if (!CpyRewriter) + return false; + // Rewrite each rewritable source by generating new COPYs. This works + // differently from optimizeCoalescableCopy since it first makes sure that all + // definitions can be rewritten. + RewriteMapTy RewriteMap; + unsigned Reg, SubReg, CopyDefReg, CopyDefSubReg; + while (CpyRewriter->getNextRewritableSource(Reg, SubReg, CopyDefReg, + CopyDefSubReg)) { // If a physical register is here, this is probably for a good reason. // Do not rewrite that. - if (TargetRegisterInfo::isPhysicalRegister(MODef.getReg())) + if (TargetRegisterInfo::isPhysicalRegister(CopyDefReg)) return false; // If we do not know how to rewrite this definition, there is no point // in trying to kill this instruction. - TargetInstrInfo::RegSubRegPair Def(MODef.getReg(), MODef.getSubReg()); - TargetInstrInfo::RegSubRegPair Src = Def; - if (!findNextSource(Src.Reg, Src.SubReg)) + TargetInstrInfo::RegSubRegPair Def(CopyDefReg, CopyDefSubReg); + if (!findNextSource(Def.Reg, Def.SubReg, RewriteMap)) return false; - RewritePairs.push_back(std::make_pair(Def, Src)); + + RewritePairs.push_back(Def); } + // The change is possible for all defs, do it. - for (const auto &PairDefSrc : RewritePairs) { - const auto &Def = PairDefSrc.first; - const auto &Src = PairDefSrc.second; + for (const auto &Def : RewritePairs) { // Rewrite the "copy" in a way the register coalescer understands. - assert(!TargetRegisterInfo::isPhysicalRegister(Def.Reg) && - "We do not rewrite physical registers"); - const TargetRegisterClass *DefRC = MRI->getRegClass(Def.Reg); - unsigned NewVR = MRI->createVirtualRegister(DefRC); - MachineInstr *NewCopy = BuildMI(*MI->getParent(), MI, MI->getDebugLoc(), - TII->get(TargetOpcode::COPY), - NewVR).addReg(Src.Reg, 0, Src.SubReg); - NewCopy->getOperand(0).setSubReg(Def.SubReg); - if (Def.SubReg) - NewCopy->getOperand(0).setIsUndef(); + MachineInstr *NewCopy = CpyRewriter->RewriteSource(Def, RewriteMap); + assert(NewCopy && "Should be able to always generate a new copy"); LocalMIs.insert(NewCopy); - MRI->replaceRegWith(Def.Reg, NewVR); - MRI->clearKillFlags(NewVR); - // We extended the lifetime of Src. - // Clear the kill flags to account for that. - MRI->clearKillFlags(Src.Reg); } + // MI is now dead. MI->eraseFromParent(); ++NumUncoalescableCopies; return true; } -/// isLoadFoldable - Check whether MI is a candidate for folding into a later -/// instruction. We only fold loads to virtual registers and the virtual -/// register defined has a single use. +/// Check whether MI is a candidate for folding into a later instruction. +/// We only fold loads to virtual registers and the virtual register defined +/// has a single use. bool PeepholeOptimizer::isLoadFoldable( - MachineInstr *MI, - SmallSet<unsigned, 16> &FoldAsLoadDefCandidates) { + MachineInstr *MI, SmallSet<unsigned, 16> &FoldAsLoadDefCandidates) { if (!MI->canFoldAsLoad() || !MI->mayLoad()) return false; const MCInstrDesc &MCID = MI->getDesc(); @@ -1010,9 +1313,9 @@ bool PeepholeOptimizer::isLoadFoldable( return false; } -bool PeepholeOptimizer::isMoveImmediate(MachineInstr *MI, - SmallSet<unsigned, 4> &ImmDefRegs, - DenseMap<unsigned, MachineInstr*> &ImmDefMIs) { +bool PeepholeOptimizer::isMoveImmediate( + MachineInstr *MI, SmallSet<unsigned, 4> &ImmDefRegs, + DenseMap<unsigned, MachineInstr *> &ImmDefMIs) { const MCInstrDesc &MCID = MI->getDesc(); if (!MI->isMoveImmediate()) return false; @@ -1028,23 +1331,26 @@ bool PeepholeOptimizer::isMoveImmediate(MachineInstr *MI, return false; } -/// foldImmediate - Try folding register operands that are defined by move -/// immediate instructions, i.e. a trivial constant folding optimization, if +/// Try folding register operands that are defined by move immediate +/// instructions, i.e. a trivial constant folding optimization, if /// and only if the def and use are in the same BB. -bool PeepholeOptimizer::foldImmediate(MachineInstr *MI, MachineBasicBlock *MBB, - SmallSet<unsigned, 4> &ImmDefRegs, - DenseMap<unsigned, MachineInstr*> &ImmDefMIs) { +bool PeepholeOptimizer::foldImmediate( + MachineInstr *MI, MachineBasicBlock *MBB, SmallSet<unsigned, 4> &ImmDefRegs, + DenseMap<unsigned, MachineInstr *> &ImmDefMIs) { for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) { MachineOperand &MO = MI->getOperand(i); if (!MO.isReg() || MO.isDef()) continue; + // Ignore dead implicit defs. + if (MO.isImplicit() && MO.isDead()) + continue; unsigned Reg = MO.getReg(); if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue; if (ImmDefRegs.count(Reg) == 0) continue; DenseMap<unsigned, MachineInstr*>::iterator II = ImmDefMIs.find(Reg); - assert(II != ImmDefMIs.end()); + assert(II != ImmDefMIs.end() && "couldn't find immediate definition"); if (TII->FoldImmediate(MI, II->second, Reg, MRI)) { ++NumImmFold; return true; @@ -1053,6 +1359,117 @@ bool PeepholeOptimizer::foldImmediate(MachineInstr *MI, MachineBasicBlock *MBB, return false; } +// FIXME: This is very simple and misses some cases which should be handled when +// motivating examples are found. +// +// The copy rewriting logic should look at uses as well as defs and be able to +// eliminate copies across blocks. +// +// Later copies that are subregister extracts will also not be eliminated since +// only the first copy is considered. +// +// e.g. +// %vreg1 = COPY %vreg0 +// %vreg2 = COPY %vreg0:sub1 +// +// Should replace %vreg2 uses with %vreg1:sub1 +bool PeepholeOptimizer::foldRedundantCopy( + MachineInstr *MI, SmallSet<unsigned, 4> &CopySrcRegs, + DenseMap<unsigned, MachineInstr *> &CopyMIs) { + assert(MI->isCopy() && "expected a COPY machine instruction"); + + unsigned SrcReg = MI->getOperand(1).getReg(); + if (!TargetRegisterInfo::isVirtualRegister(SrcReg)) + return false; + + unsigned DstReg = MI->getOperand(0).getReg(); + if (!TargetRegisterInfo::isVirtualRegister(DstReg)) + return false; + + if (CopySrcRegs.insert(SrcReg).second) { + // First copy of this reg seen. + CopyMIs.insert(std::make_pair(SrcReg, MI)); + return false; + } + + MachineInstr *PrevCopy = CopyMIs.find(SrcReg)->second; + + unsigned SrcSubReg = MI->getOperand(1).getSubReg(); + unsigned PrevSrcSubReg = PrevCopy->getOperand(1).getSubReg(); + + // Can't replace different subregister extracts. + if (SrcSubReg != PrevSrcSubReg) + return false; + + unsigned PrevDstReg = PrevCopy->getOperand(0).getReg(); + + // Only replace if the copy register class is the same. + // + // TODO: If we have multiple copies to different register classes, we may want + // to track multiple copies of the same source register. + if (MRI->getRegClass(DstReg) != MRI->getRegClass(PrevDstReg)) + return false; + + MRI->replaceRegWith(DstReg, PrevDstReg); + + // Lifetime of the previous copy has been extended. + MRI->clearKillFlags(PrevDstReg); + return true; +} + +bool PeepholeOptimizer::isNAPhysCopy(unsigned Reg) { + return TargetRegisterInfo::isPhysicalRegister(Reg) && + !MRI->isAllocatable(Reg); +} + +bool PeepholeOptimizer::foldRedundantNAPhysCopy( + MachineInstr *MI, DenseMap<unsigned, MachineInstr *> &NAPhysToVirtMIs) { + assert(MI->isCopy() && "expected a COPY machine instruction"); + + if (DisableNAPhysCopyOpt) + return false; + + unsigned DstReg = MI->getOperand(0).getReg(); + unsigned SrcReg = MI->getOperand(1).getReg(); + if (isNAPhysCopy(SrcReg) && TargetRegisterInfo::isVirtualRegister(DstReg)) { + // %vreg = COPY %PHYSREG + // Avoid using a datastructure which can track multiple live non-allocatable + // phys->virt copies since LLVM doesn't seem to do this. + NAPhysToVirtMIs.insert({SrcReg, MI}); + return false; + } + + if (!(TargetRegisterInfo::isVirtualRegister(SrcReg) && isNAPhysCopy(DstReg))) + return false; + + // %PHYSREG = COPY %vreg + auto PrevCopy = NAPhysToVirtMIs.find(DstReg); + if (PrevCopy == NAPhysToVirtMIs.end()) { + // We can't remove the copy: there was an intervening clobber of the + // non-allocatable physical register after the copy to virtual. + DEBUG(dbgs() << "NAPhysCopy: intervening clobber forbids erasing " << *MI + << '\n'); + return false; + } + + unsigned PrevDstReg = PrevCopy->second->getOperand(0).getReg(); + if (PrevDstReg == SrcReg) { + // Remove the virt->phys copy: we saw the virtual register definition, and + // the non-allocatable physical register's state hasn't changed since then. + DEBUG(dbgs() << "NAPhysCopy: erasing " << *MI << '\n'); + ++NumNAPhysCopies; + return true; + } + + // Potential missed optimization opportunity: we saw a different virtual + // register get a copy of the non-allocatable physical register, and we only + // track one such copy. Avoid getting confused by this new non-allocatable + // physical register definition, and remove it from the tracked copies. + DEBUG(dbgs() << "NAPhysCopy: missed opportunity " << *MI << '\n'); + NAPhysToVirtMIs.erase(PrevCopy); + return false; +} + bool PeepholeOptimizer::runOnMachineFunction(MachineFunction &MF) { if (skipOptnoneFunction(*MF.getFunction())) return false; @@ -1070,9 +1487,7 @@ bool PeepholeOptimizer::runOnMachineFunction(MachineFunction &MF) { bool Changed = false; - for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) { - MachineBasicBlock *MBB = &*I; - + for (MachineBasicBlock &MBB : MF) { bool SeenMoveImm = false; // During this forward scan, at some point it needs to answer the question @@ -1086,8 +1501,19 @@ bool PeepholeOptimizer::runOnMachineFunction(MachineFunction &MF) { DenseMap<unsigned, MachineInstr*> ImmDefMIs; SmallSet<unsigned, 16> FoldAsLoadDefCandidates; - for (MachineBasicBlock::iterator - MII = I->begin(), MIE = I->end(); MII != MIE; ) { + // Track when a non-allocatable physical register is copied to a virtual + // register so that useless moves can be removed. + // + // %PHYSREG is the map index; MI is the last valid `%vreg = COPY %PHYSREG` + // without any intervening re-definition of %PHYSREG. + DenseMap<unsigned, MachineInstr *> NAPhysToVirtMIs; + + // Set of virtual registers that are copied from. + SmallSet<unsigned, 4> CopySrcRegs; + DenseMap<unsigned, MachineInstr *> CopySrcMIs; + + for (MachineBasicBlock::iterator MII = MBB.begin(), MIE = MBB.end(); + MII != MIE; ) { MachineInstr *MI = &*MII; // We may be erasing MI below, increment MII now. ++MII; @@ -1097,20 +1523,60 @@ bool PeepholeOptimizer::runOnMachineFunction(MachineFunction &MF) { if (MI->isDebugValue()) continue; - // If there exists an instruction which belongs to the following - // categories, we will discard the load candidates. - if (MI->isPosition() || MI->isPHI() || MI->isImplicitDef() || - MI->isKill() || MI->isInlineAsm() || - MI->hasUnmodeledSideEffects()) { + // If we run into an instruction we can't fold across, discard + // the load candidates. + if (MI->isLoadFoldBarrier()) FoldAsLoadDefCandidates.clear(); + + if (MI->isPosition() || MI->isPHI()) + continue; + + if (!MI->isCopy()) { + for (const auto &Op : MI->operands()) { + // Visit all operands: definitions can be implicit or explicit. + if (Op.isReg()) { + unsigned Reg = Op.getReg(); + if (Op.isDef() && isNAPhysCopy(Reg)) { + const auto &Def = NAPhysToVirtMIs.find(Reg); + if (Def != NAPhysToVirtMIs.end()) { + // A new definition of the non-allocatable physical register + // invalidates previous copies. + DEBUG(dbgs() << "NAPhysCopy: invalidating because of " << *MI + << '\n'); + NAPhysToVirtMIs.erase(Def); + } + } + } else if (Op.isRegMask()) { + const uint32_t *RegMask = Op.getRegMask(); + for (auto &RegMI : NAPhysToVirtMIs) { + unsigned Def = RegMI.first; + if (MachineOperand::clobbersPhysReg(RegMask, Def)) { + DEBUG(dbgs() << "NAPhysCopy: invalidating because of " << *MI + << '\n'); + NAPhysToVirtMIs.erase(Def); + } + } + } + } + } + + if (MI->isImplicitDef() || MI->isKill()) + continue; + + if (MI->isInlineAsm() || MI->hasUnmodeledSideEffects()) { + // Blow away all non-allocatable physical registers knowledge since we + // don't know what's correct anymore. + // + // FIXME: handle explicit asm clobbers. + DEBUG(dbgs() << "NAPhysCopy: blowing away all info due to " << *MI + << '\n'); + NAPhysToVirtMIs.clear(); continue; } - if (MI->mayStore() || MI->isCall()) - FoldAsLoadDefCandidates.clear(); if ((isUncoalescableCopy(*MI) && optimizeUncoalescableCopy(MI, LocalMIs)) || - (MI->isCompare() && optimizeCmpInstr(MI, MBB)) || + (MI->isCompare() && optimizeCmpInstr(MI, &MBB)) || (MI->isSelect() && optimizeSelect(MI, LocalMIs))) { // MI is deleted. LocalMIs.erase(MI); @@ -1129,17 +1595,26 @@ bool PeepholeOptimizer::runOnMachineFunction(MachineFunction &MF) { continue; } + if (MI->isCopy() && + (foldRedundantCopy(MI, CopySrcRegs, CopySrcMIs) || + foldRedundantNAPhysCopy(MI, NAPhysToVirtMIs))) { + LocalMIs.erase(MI); + MI->eraseFromParent(); + Changed = true; + continue; + } + if (isMoveImmediate(MI, ImmDefRegs, ImmDefMIs)) { SeenMoveImm = true; } else { - Changed |= optimizeExtInstr(MI, MBB, LocalMIs); + Changed |= optimizeExtInstr(MI, &MBB, LocalMIs); // optimizeExtInstr might have created new instructions after MI // and before the already incremented MII. Adjust MII so that the // next iteration sees the new instructions. MII = MI; ++MII; if (SeenMoveImm) - Changed |= foldImmediate(MI, MBB, ImmDefRegs, ImmDefMIs); + Changed |= foldImmediate(MI, &MBB, ImmDefRegs, ImmDefMIs); } // Check whether MI is a load candidate for folding into a later @@ -1190,8 +1665,7 @@ bool PeepholeOptimizer::runOnMachineFunction(MachineFunction &MF) { return Changed; } -bool ValueTracker::getNextSourceFromCopy(unsigned &SrcReg, - unsigned &SrcSubReg) { +ValueTrackerResult ValueTracker::getNextSourceFromCopy() { assert(Def->isCopy() && "Invalid definition"); // Copy instruction are supposed to be: Def = Src. // If someone breaks this assumption, bad things will happen everywhere. @@ -1199,30 +1673,27 @@ bool ValueTracker::getNextSourceFromCopy(unsigned &SrcReg, if (Def->getOperand(DefIdx).getSubReg() != DefSubReg) // If we look for a different subreg, it means we want a subreg of src. - // Bails as we do not support composing subreg yet. - return false; + // Bails as we do not support composing subregs yet. + return ValueTrackerResult(); // Otherwise, we want the whole source. const MachineOperand &Src = Def->getOperand(1); - SrcReg = Src.getReg(); - SrcSubReg = Src.getSubReg(); - return true; + return ValueTrackerResult(Src.getReg(), Src.getSubReg()); } -bool ValueTracker::getNextSourceFromBitcast(unsigned &SrcReg, - unsigned &SrcSubReg) { +ValueTrackerResult ValueTracker::getNextSourceFromBitcast() { assert(Def->isBitcast() && "Invalid definition"); // Bail if there are effects that a plain copy will not expose. if (Def->hasUnmodeledSideEffects()) - return false; + return ValueTrackerResult(); // Bitcasts with more than one def are not supported. if (Def->getDesc().getNumDefs() != 1) - return false; + return ValueTrackerResult(); if (Def->getOperand(DefIdx).getSubReg() != DefSubReg) // If we look for a different subreg, it means we want a subreg of the src. - // Bails as we do not support composing subreg yet. - return false; + // Bails as we do not support composing subregs yet. + return ValueTrackerResult(); unsigned SrcIdx = Def->getNumOperands(); for (unsigned OpIdx = DefIdx + 1, EndOpIdx = SrcIdx; OpIdx != EndOpIdx; @@ -1230,25 +1701,25 @@ bool ValueTracker::getNextSourceFromBitcast(unsigned &SrcReg, const MachineOperand &MO = Def->getOperand(OpIdx); if (!MO.isReg() || !MO.getReg()) continue; + // Ignore dead implicit defs. + if (MO.isImplicit() && MO.isDead()) + continue; assert(!MO.isDef() && "We should have skipped all the definitions by now"); if (SrcIdx != EndOpIdx) // Multiple sources? - return false; + return ValueTrackerResult(); SrcIdx = OpIdx; } const MachineOperand &Src = Def->getOperand(SrcIdx); - SrcReg = Src.getReg(); - SrcSubReg = Src.getSubReg(); - return true; + return ValueTrackerResult(Src.getReg(), Src.getSubReg()); } -bool ValueTracker::getNextSourceFromRegSequence(unsigned &SrcReg, - unsigned &SrcSubReg) { +ValueTrackerResult ValueTracker::getNextSourceFromRegSequence() { assert((Def->isRegSequence() || Def->isRegSequenceLike()) && "Invalid definition"); if (Def->getOperand(DefIdx).getSubReg()) - // If we are composing subreg, bails out. + // If we are composing subregs, bail out. // The case we are checking is Def.<subreg> = REG_SEQUENCE. // This should almost never happen as the SSA property is tracked at // the register level (as opposed to the subreg level). @@ -1262,16 +1733,16 @@ bool ValueTracker::getNextSourceFromRegSequence(unsigned &SrcReg, // have this case. // If we can ascertain (or force) that this never happens, we could // turn that into an assertion. - return false; + return ValueTrackerResult(); if (!TII) // We could handle the REG_SEQUENCE here, but we do not want to // duplicate the code from the generic TII. - return false; + return ValueTrackerResult(); SmallVector<TargetInstrInfo::RegSubRegPairAndIdx, 8> RegSeqInputRegs; if (!TII->getRegSequenceInputs(*Def, DefIdx, RegSeqInputRegs)) - return false; + return ValueTrackerResult(); // We are looking at: // Def = REG_SEQUENCE v0, sub0, v1, sub1, ... @@ -1279,41 +1750,38 @@ bool ValueTracker::getNextSourceFromRegSequence(unsigned &SrcReg, for (auto &RegSeqInput : RegSeqInputRegs) { if (RegSeqInput.SubIdx == DefSubReg) { if (RegSeqInput.SubReg) - // Bails if we have to compose sub registers. - return false; + // Bail if we have to compose sub registers. + return ValueTrackerResult(); - SrcReg = RegSeqInput.Reg; - SrcSubReg = RegSeqInput.SubReg; - return true; + return ValueTrackerResult(RegSeqInput.Reg, RegSeqInput.SubReg); } } // If the subreg we are tracking is super-defined by another subreg, // we could follow this value. However, this would require to compose // the subreg and we do not do that for now. - return false; + return ValueTrackerResult(); } -bool ValueTracker::getNextSourceFromInsertSubreg(unsigned &SrcReg, - unsigned &SrcSubReg) { +ValueTrackerResult ValueTracker::getNextSourceFromInsertSubreg() { assert((Def->isInsertSubreg() || Def->isInsertSubregLike()) && "Invalid definition"); if (Def->getOperand(DefIdx).getSubReg()) - // If we are composing subreg, bails out. + // If we are composing subreg, bail out. // Same remark as getNextSourceFromRegSequence. // I.e., this may be turned into an assert. - return false; + return ValueTrackerResult(); if (!TII) // We could handle the REG_SEQUENCE here, but we do not want to // duplicate the code from the generic TII. - return false; + return ValueTrackerResult(); TargetInstrInfo::RegSubRegPair BaseReg; TargetInstrInfo::RegSubRegPairAndIdx InsertedReg; if (!TII->getInsertSubregInputs(*Def, DefIdx, BaseReg, InsertedReg)) - return false; + return ValueTrackerResult(); // We are looking at: // Def = INSERT_SUBREG v0, v1, sub1 @@ -1323,9 +1791,7 @@ bool ValueTracker::getNextSourceFromInsertSubreg(unsigned &SrcReg, // #1 Check if the inserted register matches the required sub index. if (InsertedReg.SubIdx == DefSubReg) { - SrcReg = InsertedReg.Reg; - SrcSubReg = InsertedReg.SubReg; - return true; + return ValueTrackerResult(InsertedReg.Reg, InsertedReg.SubReg); } // #2 Otherwise, if the sub register we are looking for is not partial // defined by the inserted element, we can look through the main @@ -1333,10 +1799,10 @@ bool ValueTracker::getNextSourceFromInsertSubreg(unsigned &SrcReg, const MachineOperand &MODef = Def->getOperand(DefIdx); // If the result register (Def) and the base register (v0) do not // have the same register class or if we have to compose - // subregisters, bails out. + // subregisters, bail out. if (MRI.getRegClass(MODef.getReg()) != MRI.getRegClass(BaseReg.Reg) || BaseReg.SubReg) - return false; + return ValueTrackerResult(); // Get the TRI and check if the inserted sub-register overlaps with the // sub-register we are tracking. @@ -1344,121 +1810,138 @@ bool ValueTracker::getNextSourceFromInsertSubreg(unsigned &SrcReg, if (!TRI || (TRI->getSubRegIndexLaneMask(DefSubReg) & TRI->getSubRegIndexLaneMask(InsertedReg.SubIdx)) != 0) - return false; + return ValueTrackerResult(); // At this point, the value is available in v0 via the same subreg // we used for Def. - SrcReg = BaseReg.Reg; - SrcSubReg = DefSubReg; - return true; + return ValueTrackerResult(BaseReg.Reg, DefSubReg); } -bool ValueTracker::getNextSourceFromExtractSubreg(unsigned &SrcReg, - unsigned &SrcSubReg) { +ValueTrackerResult ValueTracker::getNextSourceFromExtractSubreg() { assert((Def->isExtractSubreg() || Def->isExtractSubregLike()) && "Invalid definition"); // We are looking at: // Def = EXTRACT_SUBREG v0, sub0 - // Bails if we have to compose sub registers. + // Bail if we have to compose sub registers. // Indeed, if DefSubReg != 0, we would have to compose it with sub0. if (DefSubReg) - return false; + return ValueTrackerResult(); if (!TII) // We could handle the EXTRACT_SUBREG here, but we do not want to // duplicate the code from the generic TII. - return false; + return ValueTrackerResult(); TargetInstrInfo::RegSubRegPairAndIdx ExtractSubregInputReg; if (!TII->getExtractSubregInputs(*Def, DefIdx, ExtractSubregInputReg)) - return false; + return ValueTrackerResult(); - // Bails if we have to compose sub registers. + // Bail if we have to compose sub registers. // Likewise, if v0.subreg != 0, we would have to compose v0.subreg with sub0. if (ExtractSubregInputReg.SubReg) - return false; + return ValueTrackerResult(); // Otherwise, the value is available in the v0.sub0. - SrcReg = ExtractSubregInputReg.Reg; - SrcSubReg = ExtractSubregInputReg.SubIdx; - return true; + return ValueTrackerResult(ExtractSubregInputReg.Reg, + ExtractSubregInputReg.SubIdx); } -bool ValueTracker::getNextSourceFromSubregToReg(unsigned &SrcReg, - unsigned &SrcSubReg) { +ValueTrackerResult ValueTracker::getNextSourceFromSubregToReg() { assert(Def->isSubregToReg() && "Invalid definition"); // We are looking at: // Def = SUBREG_TO_REG Imm, v0, sub0 - // Bails if we have to compose sub registers. + // Bail if we have to compose sub registers. // If DefSubReg != sub0, we would have to check that all the bits // we track are included in sub0 and if yes, we would have to // determine the right subreg in v0. if (DefSubReg != Def->getOperand(3).getImm()) - return false; - // Bails if we have to compose sub registers. + return ValueTrackerResult(); + // Bail if we have to compose sub registers. // Likewise, if v0.subreg != 0, we would have to compose it with sub0. if (Def->getOperand(2).getSubReg()) - return false; + return ValueTrackerResult(); - SrcReg = Def->getOperand(2).getReg(); - SrcSubReg = Def->getOperand(3).getImm(); - return true; + return ValueTrackerResult(Def->getOperand(2).getReg(), + Def->getOperand(3).getImm()); +} + +/// \brief Explore each PHI incoming operand and return its sources +ValueTrackerResult ValueTracker::getNextSourceFromPHI() { + assert(Def->isPHI() && "Invalid definition"); + ValueTrackerResult Res; + + // If we look for a different subreg, bail as we do not support composing + // subregs yet. + if (Def->getOperand(0).getSubReg() != DefSubReg) + return ValueTrackerResult(); + + // Return all register sources for PHI instructions. + for (unsigned i = 1, e = Def->getNumOperands(); i < e; i += 2) { + auto &MO = Def->getOperand(i); + assert(MO.isReg() && "Invalid PHI instruction"); + Res.addSource(MO.getReg(), MO.getSubReg()); + } + + return Res; } -bool ValueTracker::getNextSourceImpl(unsigned &SrcReg, unsigned &SrcSubReg) { +ValueTrackerResult ValueTracker::getNextSourceImpl() { assert(Def && "This method needs a valid definition"); assert( (DefIdx < Def->getDesc().getNumDefs() || Def->getDesc().isVariadic()) && Def->getOperand(DefIdx).isDef() && "Invalid DefIdx"); if (Def->isCopy()) - return getNextSourceFromCopy(SrcReg, SrcSubReg); + return getNextSourceFromCopy(); if (Def->isBitcast()) - return getNextSourceFromBitcast(SrcReg, SrcSubReg); + return getNextSourceFromBitcast(); // All the remaining cases involve "complex" instructions. - // Bails if we did not ask for the advanced tracking. + // Bail if we did not ask for the advanced tracking. if (!UseAdvancedTracking) - return false; + return ValueTrackerResult(); if (Def->isRegSequence() || Def->isRegSequenceLike()) - return getNextSourceFromRegSequence(SrcReg, SrcSubReg); + return getNextSourceFromRegSequence(); if (Def->isInsertSubreg() || Def->isInsertSubregLike()) - return getNextSourceFromInsertSubreg(SrcReg, SrcSubReg); + return getNextSourceFromInsertSubreg(); if (Def->isExtractSubreg() || Def->isExtractSubregLike()) - return getNextSourceFromExtractSubreg(SrcReg, SrcSubReg); + return getNextSourceFromExtractSubreg(); if (Def->isSubregToReg()) - return getNextSourceFromSubregToReg(SrcReg, SrcSubReg); - return false; + return getNextSourceFromSubregToReg(); + if (Def->isPHI()) + return getNextSourceFromPHI(); + return ValueTrackerResult(); } -const MachineInstr *ValueTracker::getNextSource(unsigned &SrcReg, - unsigned &SrcSubReg) { +ValueTrackerResult ValueTracker::getNextSource() { // If we reach a point where we cannot move up in the use-def chain, // there is nothing we can get. if (!Def) - return nullptr; + return ValueTrackerResult(); - const MachineInstr *PrevDef = nullptr; - // Try to find the next source. - if (getNextSourceImpl(SrcReg, SrcSubReg)) { + ValueTrackerResult Res = getNextSourceImpl(); + if (Res.isValid()) { // Update definition, definition index, and subregister for the // next call of getNextSource. // Update the current register. - Reg = SrcReg; - // Update the return value before moving up in the use-def chain. - PrevDef = Def; + bool OneRegSrc = Res.getNumSources() == 1; + if (OneRegSrc) + Reg = Res.getSrcReg(0); + // Update the result before moving up in the use-def chain + // with the instruction containing the last found sources. + Res.setInst(Def); + // If we can still move up in the use-def chain, move to the next - // defintion. - if (!TargetRegisterInfo::isPhysicalRegister(Reg)) { + // definition. + if (!TargetRegisterInfo::isPhysicalRegister(Reg) && OneRegSrc) { Def = MRI.getVRegDef(Reg); DefIdx = MRI.def_begin(Reg).getOperandNo(); - DefSubReg = SrcSubReg; - return PrevDef; + DefSubReg = Res.getSrcSubReg(0); + return Res; } } // If we end up here, this means we will not be able to find another source - // for the next iteration. - // Make sure any new call to getNextSource bails out early by cutting the - // use-def chain. + // for the next iteration. Make sure any new call to getNextSource bails out + // early by cutting the use-def chain. Def = nullptr; - return PrevDef; + return Res; } |
