CbC/CbC_llvm: lib/CodeGen/PeepholeOptimizer.cpp comparison

comparison lib/CodeGen/PeepholeOptimizer.cpp @ 95:afa8332a0e37 LLVM3.8

LLVM 3.8

author	Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
date	Tue, 13 Oct 2015 17:48:58 +0900
parents	60c9769439b8
children	7d135dc70f03

comparison

equal deleted inserted replaced

-:f3e34b893a5f
+:afa8332a0e37
 //     "sub" with "subs" and eliminate the "cmp" instruction.
 //
 // - 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
 //     a single use.
 //
 // - Optimize Copies and Bitcast (more generally, target specific copies):
 //
 //     Rewrite copies and bitcasts to avoid cross register bank copies
 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
 #include <utility>
 using namespace llvm;
 cl::desc("Disable the peephole optimizer"));
 static cl::opt<bool>
 DisableAdvCopyOpt("disable-adv-copy-opt", cl::Hidden, cl::init(false),
 cl::desc("Disable advanced 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");
 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");
 namespace {
+class ValueTrackerResult;
 class PeepholeOptimizer : public MachineFunctionPass {
 const TargetInstrInfo *TII;
 const TargetRegisterInfo *TRI;
 MachineRegisterInfo   *MRI;
 MachineDominatorTree  *DT;  // Machine dominator tree
 AU.addRequired<MachineDominatorTree>();
 AU.addPreserved<MachineDominatorTree>();
 }
 }
+/// \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,
 SmallPtrSetImpl<MachineInstr*> &LocalMIs);
 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 CopiedFromRegs 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> &CopiedFromRegs,
+DenseMap<unsigned, MachineInstr*> &CopyMIs);
 bool isLoadFoldable(MachineInstr *MI,
 SmallSet<unsigned, 16> &FoldAsLoadDefCandidates);
 /// \brief Check whether \p MI is understood by the register coalescer
 /// but may require some rewriting.
 bool isUncoalescableCopy(const MachineInstr &MI) {
 return MI.isBitcast() ||
 (!DisableAdvCopyOpt &&
 (MI.isRegSequenceLike() || MI.isInsertSubregLike() ||
 MI.isExtractSubregLike()));
+}
+};
+/// \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.
 /// tracking.
 const TargetInstrInfo *TII;
 /// \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.
 /// \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
 Reg = Def->getOperand(DefIdx).getReg();
 }
 /// \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
+/// \return A ValueTrackerResult containing a set of registers
-/// that contain the tracked value.
+/// and sub registers with tracked values. A ValueTrackerResult with
-/// \note The sub register index returned in \p SrcSubReg must be used
+/// an empty set of registers means no source was found.
-/// on \p SrcReg to access the actual value.
+ValueTrackerResult getNextSource();
-/// \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);
 /// \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.
 }
 }
 if (ExtendLife && !ExtendedUses.empty())
 // Extend the liveness of the extension result.
-std::copy(ExtendedUses.begin(), ExtendedUses.end(),
+Uses.append(ExtendedUses.begin(), ExtendedUses.end());
-std::back_inserter(Uses));
 // Now replace all uses.
 bool Changed = false;
 if (!Uses.empty()) {
 SmallPtrSet<MachineBasicBlock*, 4> PHIBBs;
 // generated
 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
+/// When true is returned, the \p RewriteMap can be used by the client to
-/// register number and sub-register index of the new source.
+/// 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;
+SmallVector<TargetInstrInfo::RegSubRegPair, 4> SrcToLook;
-unsigned Src;
+TargetInstrInfo::RegSubRegPair CurSrcPair(Reg, SubReg);
-unsigned SrcSubReg;
+SrcToLook.push_back(CurSrcPair);
-bool ShouldRewrite = false;
+unsigned PHICount = 0;
-// Follow the chain of copies until we reach the top of the use-def chain
+while (!SrcToLook.empty() && PHICount < RewritePHILimit) {
-// or find a more suitable source.
+TargetInstrInfo::RegSubRegPair Pair = SrcToLook.pop_back_val();
-ValueTracker ValTracker(Reg, DefSubReg, *MRI, !DisableAdvCopyOpt, TII);
+// As explained above, do not handle physical registers
-do {
+if (TargetRegisterInfo::isPhysicalRegister(Pair.Reg))
-unsigned CopySrcReg, CopySrcSubReg;
+return false;
-if (!ValTracker.getNextSource(CopySrcReg, CopySrcSubReg))
-break;
+CurSrcPair = Pair;
-Src = CopySrcReg;
+ValueTracker ValTracker(CurSrcPair.Reg, CurSrcPair.SubReg, *MRI,
-SrcSubReg = CopySrcSubReg;
+!DisableAdvCopyOpt, TII);
+ValueTrackerResult Res;
-// Do not extend the live-ranges of physical registers as they add
+bool ShouldRewrite = false;
-// constraints to the register allocator.
-// Moreover, if we want to extend the live-range of a physical register,
+do {
-// unlike SSA virtual register, we will have to check that they are not
+// Follow the chain of copies until we reach the top of the use-def chain
-// redefine before the related use.
+// or find a more suitable source.
-if (TargetRegisterInfo::isPhysicalRegister(Src))
+Res = ValTracker.getNextSource();
-break;
+if (!Res.isValid())
+break;
-const TargetRegisterClass *SrcRC = MRI->getRegClass(Src);
+// Insert the Def -> Use entry for the recently found source.
-// If this source does not incur a cross register bank copy, use it.
+ValueTrackerResult CurSrcRes = RewriteMap.lookup(CurSrcPair);
-ShouldRewrite = shareSameRegisterFile(*TRI, DefRC, DefSubReg, SrcRC,
+if (CurSrcRes.isValid()) {
-SrcSubReg);
+assert(CurSrcRes == Res && "ValueTrackerResult found must match");
-} while (!ShouldRewrite);
+// 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;
+}
+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;
+}
 // If we did not find a more suitable source, there is nothing to optimize.
-if (!ShouldRewrite || Src == Reg)
+if (CurSrcPair.Reg == Reg)
 return false;
-Reg = Src;
-SubReg = SrcSubReg;
 return true;
+}
+/// \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 {
 /// \brief Helper class to rewrite the arguments of a copy-like instruction.
 class CopyRewriter {
 /// the only source this instruction has:
 /// (SrcReg, SrcSubReg) = (src, srcSubIdx).
 /// 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.
 /// 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
+// If CurrentSrcIdx == 1, this means this function has already been called
-// called once. CopyLike has one defintiion and one argument, thus,
+// once. CopyLike has one definition and one argument, thus, there is
-// there is nothing else to rewrite.
+// nothing else to rewrite.
 if (!CopyLike.isCopy() || CurrentSrcIdx == 1)
 return false;
 // This is the first call to getNextRewritableSource.
 // Move the CurrentSrcIdx to remember that we made that call.
 CurrentSrcIdx = 1;
 return true;
 }
 /// \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;
 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<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.
 class InsertSubregRewriter : public CopyRewriter {
 // We want to track something that is compatible with the
 // 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;
 }
 bool RewriteCurrentSource(unsigned NewReg, unsigned NewSubReg) override {
 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, bails out.
+// If we have to compose sub-register indices, bail out.
 if (MOExtractedReg.getSubReg())
 return false;
 SrcSubReg = CopyLike.getOperand(2).getImm();
 if (CurrentSrcIdx >= CopyLike.getNumOperands())
 return false;
 }
 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;
 // We want to track something that is compatible with the related
 // partial definition.
 TrackSubReg = CopyLike.getOperand(CurrentSrcIdx + 1).getImm();
 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;
 }
 bool RewriteCurrentSource(unsigned NewReg, unsigned NewSubReg) override {
 // We cannot rewrite out of bound operands.
 /// \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) {
+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;
 case TargetOpcode::COPY:
 return new CopyRewriter(MI);
 /// class.
 /// Two register classes are considered to be compatible if they share
 /// 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.
 bool PeepholeOptimizer::optimizeCoalescableCopy(MachineInstr *MI) {
 assert(MI && isCoalescableCopy(*MI) && "Invalid argument");
 if (TargetRegisterInfo::isPhysicalRegister(MODef.getReg()))
 return false;
 bool Changed = false;
 // Get the right rewriter for the current copy.
-std::unique_ptr<CopyRewriter> CpyRewriter(getCopyRewriter(*MI, *TII));
+std::unique_ptr<CopyRewriter> CpyRewriter(getCopyRewriter(*MI, *TII, *MRI));
-// If none exists, bails out.
+// 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;
+// Keep track of PHI nodes and its incoming edges when looking for sources.
-unsigned NewSubReg = TrackSubReg;
+RewriteMapTy RewriteMap;
-// Try to find a more suitable source.
+// Try to find a more suitable source. If we failed to do so, or get the
-// If we failed to do so, or get the actual source,
+// actual source, move to the next source.
-// move to the next source.
+if (!findNextSource(TrackReg, TrackSubReg, RewriteMap))
-if (!findNextSource(NewSrc, NewSubReg) || SrcReg == NewSrc)
 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;
 }
 }
 // TODO: We could have a clean-up method to tidy the instruction.
 // E.g., v0 = INSERT_SUBREG v1, v1.sub0, sub0
 // => v0 = COPY v1
 // Currently we haven't seen motivating example for that and we
 // want to avoid untested code.
-NumRewrittenCopies += Changed == true;
+NumRewrittenCopies += Changed;
 return Changed;
 }
 /// \brief Optimize copy-like instructions to create
 /// register coalescer friendly instruction.
 bool PeepholeOptimizer::optimizeUncoalescableCopy(
 MachineInstr *MI, SmallPtrSetImpl<MachineInstr *> &LocalMIs) {
 assert(MI && isUncoalescableCopy(*MI) && "Invalid argument");
 // Check if we can rewrite all the values defined by this instruction.
-SmallVector<
+SmallVector<TargetInstrInfo::RegSubRegPair, 4> RewritePairs;
-std::pair<TargetInstrInfo::RegSubRegPair, TargetInstrInfo::RegSubRegPair>,
+// Get the right rewriter for the current copy.
-4> RewritePairs;
+std::unique_ptr<CopyRewriter> CpyRewriter(getCopyRewriter(*MI, *TII, *MRI));
-for (const MachineOperand &MODef : MI->defs()) {
+// If none exists, bail out.
-if (MODef.isDead())
+if (!CpyRewriter)
-// We can ignore those.
+return false;
-continue;
+// 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 Def(CopyDefReg, CopyDefSubReg);
-TargetInstrInfo::RegSubRegPair Src = Def;
+if (!findNextSource(Def.Reg, Def.SubReg, RewriteMap))
-if (!findNextSource(Src.Reg, Src.SubReg))
 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) {
+for (const auto &Def : RewritePairs) {
-const auto &Def = PairDefSrc.first;
-const auto &Src = PairDefSrc.second;
 // Rewrite the "copy" in a way the register coalescer understands.
-assert(!TargetRegisterInfo::isPhysicalRegister(Def.Reg) &&
+MachineInstr *NewCopy = CpyRewriter->RewriteSource(Def, RewriteMap);
-"We do not rewrite physical registers");
+assert(NewCopy && "Should be able to always generate a new copy");
-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();
 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;
 }
 }
 }
 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());
+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::runOnMachineFunction(MachineFunction &MF) {
 if (skipOptnoneFunction(*MF.getFunction()))
 return false;
 DEBUG(dbgs() << "********** PEEPHOLE OPTIMIZER **********\n");
 SmallPtrSet<MachineInstr*, 16> LocalMIs;
 SmallSet<unsigned, 4> ImmDefRegs;
 DenseMap<unsigned, MachineInstr*> ImmDefMIs;
 SmallSet<unsigned, 16> FoldAsLoadDefCandidates;
+// Set of virtual registers that are copied from.
+SmallSet<unsigned, 4> CopySrcRegs;
+DenseMap<unsigned, MachineInstr *> CopySrcMIs;
 for (MachineBasicBlock::iterator
 MII = I->begin(), MIE = I->end(); MII != MIE; ) {
 MachineInstr *MI = &*MII;
 // We may be erasing MI below, increment MII now.
 ++MII;
 // Skip debug values. They should not affect this peephole optimization.
 if (MI->isDebugValue())
 continue;
-// If there exists an instruction which belongs to the following
+// If we run into an instruction we can't fold across, discard
-// categories, we will discard the load candidates.
+// the load candidates.
+if (MI->isLoadFoldBarrier())
+FoldAsLoadDefCandidates.clear();
 if (MI->isPosition() || MI->isPHI() || MI->isImplicitDef() ||
 MI->isKill() || MI->isInlineAsm() ||
-MI->hasUnmodeledSideEffects()) {
+MI->hasUnmodeledSideEffects())
-FoldAsLoadDefCandidates.clear();
 continue;
-}
-if (MI->mayStore() || MI->isCall())
-FoldAsLoadDefCandidates.clear();
 if ((isUncoalescableCopy(*MI) &&
 optimizeUncoalescableCopy(MI, LocalMIs)) ||
 (MI->isCompare() && optimizeCmpInstr(MI, MBB)) ||
 (MI->isSelect() && optimizeSelect(MI, LocalMIs))) {
 continue;
 }
 if (isCoalescableCopy(*MI) && optimizeCoalescableCopy(MI)) {
 // MI is just rewritten.
+Changed = true;
+continue;
+}
+if (MI->isCopy() && foldRedundantCopy(MI, CopySrcRegs, CopySrcMIs)) {
+LocalMIs.erase(MI);
+MI->eraseFromParent();
 Changed = true;
 continue;
 }
 if (isMoveImmediate(MI, ImmDefRegs, ImmDefMIs)) {
 }
 return Changed;
 }
-bool ValueTracker::getNextSourceFromCopy(unsigned &SrcReg,
+ValueTrackerResult ValueTracker::getNextSourceFromCopy() {
-unsigned &SrcSubReg) {
 assert(Def->isCopy() && "Invalid definition");
 // Copy instruction are supposed to be: Def = Src.
 // If someone breaks this assumption, bad things will happen everywhere.
 assert(Def->getNumOperands() == 2 && "Invalid number of operands");
 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.
+// Bails as we do not support composing subregs yet.
-return false;
+return ValueTrackerResult();
 // Otherwise, we want the whole source.
 const MachineOperand &Src = Def->getOperand(1);
-SrcReg = Src.getReg();
+return ValueTrackerResult(Src.getReg(), Src.getSubReg());
-SrcSubReg = Src.getSubReg();
+}
-return true;
-}
+ValueTrackerResult ValueTracker::getNextSourceFromBitcast() {
-bool ValueTracker::getNextSourceFromBitcast(unsigned &SrcReg,
-unsigned &SrcSubReg) {
 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.
+// Bails as we do not support composing subregs yet.
-return false;
+return ValueTrackerResult();
 unsigned SrcIdx = Def->getNumOperands();
 for (unsigned OpIdx = DefIdx + 1, EndOpIdx = SrcIdx; OpIdx != EndOpIdx;
 ++OpIdx) {
 const MachineOperand &MO = Def->getOperand(OpIdx);
 if (!MO.isReg() || !MO.getReg())
 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();
+return ValueTrackerResult(Src.getReg(), Src.getSubReg());
-SrcSubReg = Src.getSubReg();
+}
-return true;
-}
+ValueTrackerResult ValueTracker::getNextSourceFromRegSequence() {
-bool ValueTracker::getNextSourceFromRegSequence(unsigned &SrcReg,
-unsigned &SrcSubReg) {
 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).
 // I.e.,
 // Def.sub0 =
 // However, some code could theoretically generates a single
 // Def.sub0 (i.e, not defining the other subregs) and we would
 // 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, ...
 // Check if one of the operand defines the subreg we are interested in.
 for (auto &RegSeqInput : RegSeqInputRegs) {
 if (RegSeqInput.SubIdx == DefSubReg) {
 if (RegSeqInput.SubReg)
-// Bails if we have to compose sub registers.
+// Bail if we have to compose sub registers.
-return false;
+return ValueTrackerResult();
-SrcReg = RegSeqInput.Reg;
+return ValueTrackerResult(RegSeqInput.Reg, RegSeqInput.SubReg);
-SrcSubReg = RegSeqInput.SubReg;
-return true;
 }
 }
 // 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,
+ValueTrackerResult ValueTracker::getNextSourceFromInsertSubreg() {
-unsigned &SrcSubReg) {
 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
 // There are two cases:
 // 1. DefSubReg == sub1, get v1.
 // 2. DefSubReg != sub1, the value may be available through v0.
 // #1 Check if the inserted register matches the required sub index.
 if (InsertedReg.SubIdx == DefSubReg) {
-SrcReg = InsertedReg.Reg;
+return ValueTrackerResult(InsertedReg.Reg, InsertedReg.SubReg);
-SrcSubReg = InsertedReg.SubReg;
-return true;
 }
 // #2 Otherwise, if the sub register we are looking for is not partial
 // defined by the inserted element, we can look through the main
 // register (v0).
 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.
 const TargetRegisterInfo *TRI = MRI.getTargetRegisterInfo();
 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;
+return ValueTrackerResult(BaseReg.Reg, DefSubReg);
-SrcSubReg = DefSubReg;
+}
-return true;
-}
+ValueTrackerResult ValueTracker::getNextSourceFromExtractSubreg() {
-bool ValueTracker::getNextSourceFromExtractSubreg(unsigned &SrcReg,
-unsigned &SrcSubReg) {
 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;
+return ValueTrackerResult(ExtractSubregInputReg.Reg, ExtractSubregInputReg.SubIdx);
-SrcSubReg = ExtractSubregInputReg.SubIdx;
+}
-return true;
-}
+ValueTrackerResult ValueTracker::getNextSourceFromSubregToReg() {
-bool ValueTracker::getNextSourceFromSubregToReg(unsigned &SrcReg,
-unsigned &SrcSubReg) {
 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;
+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 it with sub0.
 if (Def->getOperand(2).getSubReg())
-return false;
+return ValueTrackerResult();
-SrcReg = Def->getOperand(2).getReg();
+return ValueTrackerResult(Def->getOperand(2).getReg(),
-SrcSubReg = Def->getOperand(3).getImm();
+Def->getOperand(3).getImm());
-return true;
+}
-}
+/// \brief Explore each PHI incoming operand and return its sources
-bool ValueTracker::getNextSourceImpl(unsigned &SrcReg, unsigned &SrcSubReg) {
+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;
+}
+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 getNextSourceFromSubregToReg();
-return false;
+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;
+ValueTrackerResult Res = getNextSourceImpl();
-// Try to find the next source.
+if (Res.isValid()) {
-if (getNextSourceImpl(SrcReg, SrcSubReg)) {
 // Update definition, definition index, and subregister for the
 // next call of getNextSource.
 // Update the current register.
-Reg = SrcReg;
+bool OneRegSrc = Res.getNumSources() == 1;
-// Update the return value before moving up in the use-def chain.
+if (OneRegSrc)
-PrevDef = Def;
+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.
+// definition.
-if (!TargetRegisterInfo::isPhysicalRegister(Reg)) {
+if (!TargetRegisterInfo::isPhysicalRegister(Reg) && OneRegSrc) {
 Def = MRI.getVRegDef(Reg);
 DefIdx = MRI.def_begin(Reg).getOperandNo();
-DefSubReg = SrcSubReg;
+DefSubReg = Res.getSrcSubReg(0);
-return PrevDef;
+return Res;
 }
 }
 // If we end up here, this means we will not be able to find another source
-// for the next iteration.
+// for the next iteration. Make sure any new call to getNextSource bails out
-// Make sure any new call to getNextSource bails out early by cutting the
+// early by cutting the use-def chain.
-// use-def chain.
 Def = nullptr;
-return PrevDef;
+return Res;
 }

Mercurial > hg > CbC > CbC_llvm

comparison lib/CodeGen/PeepholeOptimizer.cpp @ 95:afa8332a0e37 LLVM3.8