X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FRegisterCoalescer.h;h=472c48377fefddd5029ee6ffb5ab549e9c531e67;hb=5c75af6eb72bd74bc35f46e5037dd5646e04f3b6;hp=739a4c3711020d10ca7d1e9de482fdccf5ace204;hpb=b0efa94fb63d55c7aa5eb3c7c23d39a763036c24;p=oota-llvm.git diff --git a/lib/CodeGen/RegisterCoalescer.h b/lib/CodeGen/RegisterCoalescer.h index 739a4c37110..472c48377fe 100644 --- a/lib/CodeGen/RegisterCoalescer.h +++ b/lib/CodeGen/RegisterCoalescer.h @@ -12,196 +12,60 @@ // //===----------------------------------------------------------------------===// -#include "RegisterClassInfo.h" -#include "llvm/Support/IncludeFile.h" -#include "llvm/CodeGen/LiveInterval.h" -#include "llvm/ADT/SmallPtrSet.h" - #ifndef LLVM_CODEGEN_REGISTER_COALESCER_H #define LLVM_CODEGEN_REGISTER_COALESCER_H namespace llvm { - class MachineFunction; - class RegallocQuery; - class AnalysisUsage; class MachineInstr; class TargetRegisterInfo; class TargetRegisterClass; class TargetInstrInfo; - class SimpleRegisterCoalescing; - class LiveDebugVariables; - class VirtRegMap; - class MachineLoopInfo; - - /// An abstract interface for register coalescers. Coalescers must - /// implement this interface to be part of the coalescer analysis - /// group. - class RegisterCoalescer { - public: - static char ID; // Class identification, replacement for typeinfo - RegisterCoalescer() {} - virtual ~RegisterCoalescer(); // We want to be subclassed - - /// Run the coalescer on this function, providing interference - /// data to query. Return whether we removed any copies. - virtual bool coalesceFunction(MachineFunction &mf, - RegallocQuery &ifd) = 0; - - /// Reset state. Can be used to allow a coalescer run by - /// PassManager to be run again by the register allocator. - virtual void reset(MachineFunction &mf) {} - - /// Register allocators must call this from their own - /// getAnalysisUsage to cover the case where the coalescer is not - /// a Pass in the proper sense and isn't managed by PassManager. - /// PassManager needs to know which analyses to make available and - /// which to invalidate when running the register allocator or any - /// pass that might call coalescing. The long-term solution is to - /// allow hierarchies of PassManagers. - virtual void getAnalysisUsage(AnalysisUsage &AU) const {} - }; - - /// An abstract interface for register allocators to interact with - /// coalescers - /// - /// Example: - /// - /// This is simply an example of how to use the RegallocQuery - /// interface. It is not meant to be used in production. - /// - /// class LinearScanRegallocQuery : public RegallocQuery { - /// private: - /// const LiveIntervals \&li; - /// - /// public: - /// LinearScanRegallocQuery(LiveIntervals &intervals) - /// : li(intervals) {} - /// - /// /// This is pretty slow and conservative, but since linear scan - /// /// allocation doesn't pre-compute interference information it's - /// /// the best we can do. Coalescers are always free to ignore this - /// /// and implement their own discovery strategy. See - /// /// SimpleRegisterCoalescing for an example. - /// void getInterferences(IntervalSet &interferences, - /// const LiveInterval &a) const { - /// for(LiveIntervals::const_iterator iv = li.begin(), - /// ivend = li.end(); - /// iv != ivend; - /// ++iv) { - /// if (interfere(a, iv->second)) { - /// interferences.insert(&iv->second); - /// } - /// } - /// } - /// - /// /// This is *really* slow and stupid. See above. - /// int getNumberOfInterferences(const LiveInterval &a) const { - /// IntervalSet intervals; - /// getInterferences(intervals, a); - /// return intervals.size(); - /// } - /// }; - /// - /// In the allocator: - /// - /// RegisterCoalescer &coalescer = getAnalysis(); - /// - /// // We don't reset the coalescer so if it's already been run this - /// // takes almost no time. - /// LinearScanRegallocQuery ifd(*li_); - /// coalescer.coalesceFunction(fn, ifd); - /// - class RegallocQuery { - public: - typedef SmallPtrSet IntervalSet; - - virtual ~RegallocQuery() {} - - /// Return whether two live ranges interfere. - virtual bool interfere(const LiveInterval &a, - const LiveInterval &b) const { - // A naive test - return a.overlaps(b); - } - - /// Return the set of intervals that interfere with this one. - virtual void getInterferences(IntervalSet &interferences, - const LiveInterval &a) const = 0; - - /// This can often be cheaper than actually returning the - /// interferences. - virtual int getNumberOfInterferences(const LiveInterval &a) const = 0; - - /// Make any data structure updates necessary to reflect - /// coalescing or other modifications. - virtual void updateDataForMerge(const LiveInterval &a, - const LiveInterval &b, - const MachineInstr ©) {} - - /// Allow the register allocator to communicate when it doesn't - /// want a copy coalesced. This may be due to assumptions made by - /// the allocator about various invariants and so this question is - /// a matter of legality, not performance. Performance decisions - /// about which copies to coalesce should be made by the - /// coalescer. - virtual bool isLegalToCoalesce(const MachineInstr &inst) const { - return true; - } - }; - /// CoalescerPair - A helper class for register coalescers. When deciding if /// two registers can be coalesced, CoalescerPair can determine if a copy /// instruction would become an identity copy after coalescing. class CoalescerPair { - const TargetInstrInfo &tii_; - const TargetRegisterInfo &tri_; + const TargetInstrInfo &TII; + const TargetRegisterInfo &TRI; - /// dstReg_ - The register that will be left after coalescing. It can be a + /// DstReg - The register that will be left after coalescing. It can be a /// virtual or physical register. - unsigned dstReg_; + unsigned DstReg; - /// srcReg_ - the virtual register that will be coalesced into dstReg. - unsigned srcReg_; + /// SrcReg - the virtual register that will be coalesced into dstReg. + unsigned SrcReg; - /// subReg_ - The subregister index of srcReg in dstReg_. It is possible the - /// coalesce srcReg_ into a subreg of the larger dstReg_ when dstReg_ is a + /// subReg_ - The subregister index of srcReg in DstReg. It is possible the + /// coalesce SrcReg into a subreg of the larger DstReg when DstReg is a /// virtual register. - unsigned subIdx_; + unsigned SubIdx; - /// partial_ - True when the original copy was a partial subregister copy. - bool partial_; + /// Partial - True when the original copy was a partial subregister copy. + bool Partial; - /// crossClass_ - True when both regs are virtual, and newRC is constrained. - bool crossClass_; + /// CrossClass - True when both regs are virtual, and newRC is constrained. + bool CrossClass; - /// flipped_ - True when DstReg and SrcReg are reversed from the oriignal copy - /// instruction. - bool flipped_; + /// Flipped - True when DstReg and SrcReg are reversed from the oriignal + /// copy instruction. + bool Flipped; - /// newRC_ - The register class of the coalesced register, or NULL if dstReg_ + /// NewRC - The register class of the coalesced register, or NULL if DstReg /// is a physreg. - const TargetRegisterClass *newRC_; - - /// compose - Compose subreg indices a and b, either may be 0. - unsigned compose(unsigned, unsigned) const; - - /// isMoveInstr - Return true if MI is a move or subreg instruction. - bool isMoveInstr(const MachineInstr *MI, unsigned &Src, unsigned &Dst, - unsigned &SrcSub, unsigned &DstSub) const; + const TargetRegisterClass *NewRC; public: CoalescerPair(const TargetInstrInfo &tii, const TargetRegisterInfo &tri) - : tii_(tii), tri_(tri), dstReg_(0), srcReg_(0), subIdx_(0), - partial_(false), crossClass_(false), flipped_(false), newRC_(0) {} + : TII(tii), TRI(tri), DstReg(0), SrcReg(0), SubIdx(0), + Partial(false), CrossClass(false), Flipped(false), NewRC(0) {} /// setRegisters - set registers to match the copy instruction MI. Return /// false if MI is not a coalescable copy instruction. bool setRegisters(const MachineInstr*); - /// flip - Swap srcReg_ and dstReg_. Return false if swapping is impossible - /// because dstReg_ is a physical register, or subIdx_ is set. + /// flip - Swap SrcReg and DstReg. Return false if swapping is impossible + /// because DstReg is a physical register, or SubIdx is set. bool flip(); /// isCoalescable - Return true if MI is a copy instruction that will become @@ -209,162 +73,34 @@ namespace llvm { bool isCoalescable(const MachineInstr*) const; /// isPhys - Return true if DstReg is a physical register. - bool isPhys() const { return !newRC_; } + bool isPhys() const { return !NewRC; } - /// isPartial - Return true if the original copy instruction did not copy the - /// full register, but was a subreg operation. - bool isPartial() const { return partial_; } + /// isPartial - Return true if the original copy instruction did not copy + /// the full register, but was a subreg operation. + bool isPartial() const { return Partial; } - /// isCrossClass - Return true if DstReg is virtual and NewRC is a smaller register class than DstReg's. - bool isCrossClass() const { return crossClass_; } + /// isCrossClass - Return true if DstReg is virtual and NewRC is a smaller + /// register class than DstReg's. + bool isCrossClass() const { return CrossClass; } /// isFlipped - Return true when getSrcReg is the register being defined by /// the original copy instruction. - bool isFlipped() const { return flipped_; } + bool isFlipped() const { return Flipped; } /// getDstReg - Return the register (virtual or physical) that will remain /// after coalescing. - unsigned getDstReg() const { return dstReg_; } + unsigned getDstReg() const { return DstReg; } /// getSrcReg - Return the virtual register that will be coalesced away. - unsigned getSrcReg() const { return srcReg_; } + unsigned getSrcReg() const { return SrcReg; } /// getSubIdx - Return the subregister index in DstReg that SrcReg will be /// coalesced into, or 0. - unsigned getSubIdx() const { return subIdx_; } + unsigned getSubIdx() const { return SubIdx; } /// getNewRC - Return the register class of the coalesced register. - const TargetRegisterClass *getNewRC() const { return newRC_; } - }; - - class SimpleRegisterCoalescing : public MachineFunctionPass, - public RegisterCoalescer { - MachineFunction* mf_; - MachineRegisterInfo* mri_; - const TargetMachine* tm_; - const TargetRegisterInfo* tri_; - const TargetInstrInfo* tii_; - LiveIntervals *li_; - LiveDebugVariables *ldv_; - const MachineLoopInfo* loopInfo; - AliasAnalysis *AA; - RegisterClassInfo RegClassInfo; - - /// JoinedCopies - Keep track of copies eliminated due to coalescing. - /// - SmallPtrSet JoinedCopies; - - /// ReMatCopies - Keep track of copies eliminated due to remat. - /// - SmallPtrSet ReMatCopies; - - /// ReMatDefs - Keep track of definition instructions which have - /// been remat'ed. - SmallPtrSet ReMatDefs; - - public: - static char ID; // Pass identifcation, replacement for typeid - SimpleRegisterCoalescing() : MachineFunctionPass(ID) { - initializeSimpleRegisterCoalescingPass(*PassRegistry::getPassRegistry()); - } - - virtual void getAnalysisUsage(AnalysisUsage &AU) const; - virtual void releaseMemory(); - - /// runOnMachineFunction - pass entry point - virtual bool runOnMachineFunction(MachineFunction&); - - bool coalesceFunction(MachineFunction &mf, RegallocQuery &) { - // This runs as an independent pass, so don't do anything. - return false; - } - - /// print - Implement the dump method. - virtual void print(raw_ostream &O, const Module* = 0) const; - - private: - /// joinIntervals - join compatible live intervals - void joinIntervals(); - - /// CopyCoalesceInMBB - Coalesce copies in the specified MBB, putting - /// copies that cannot yet be coalesced into the "TryAgain" list. - void CopyCoalesceInMBB(MachineBasicBlock *MBB, - std::vector &TryAgain); - - /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, - /// which are the src/dst of the copy instruction CopyMI. This returns true - /// if the copy was successfully coalesced away. If it is not currently - /// possible to coalesce this interval, but it may be possible if other - /// things get coalesced, then it returns true by reference in 'Again'. - bool JoinCopy(MachineInstr *TheCopy, bool &Again); - - /// JoinIntervals - Attempt to join these two intervals. On failure, this - /// returns false. The output "SrcInt" will not have been modified, so we can - /// use this information below to update aliases. - bool JoinIntervals(CoalescerPair &CP); - - /// AdjustCopiesBackFrom - We found a non-trivially-coalescable copy. If - /// the source value number is defined by a copy from the destination reg - /// see if we can merge these two destination reg valno# into a single - /// value number, eliminating a copy. - bool AdjustCopiesBackFrom(const CoalescerPair &CP, MachineInstr *CopyMI); - - /// HasOtherReachingDefs - Return true if there are definitions of IntB - /// other than BValNo val# that can reach uses of AValno val# of IntA. - bool HasOtherReachingDefs(LiveInterval &IntA, LiveInterval &IntB, - VNInfo *AValNo, VNInfo *BValNo); - - /// RemoveCopyByCommutingDef - We found a non-trivially-coalescable copy. - /// If the source value number is defined by a commutable instruction and - /// its other operand is coalesced to the copy dest register, see if we - /// can transform the copy into a noop by commuting the definition. - bool RemoveCopyByCommutingDef(const CoalescerPair &CP,MachineInstr *CopyMI); - - /// ReMaterializeTrivialDef - If the source of a copy is defined by a trivial - /// computation, replace the copy by rematerialize the definition. - /// If PreserveSrcInt is true, make sure SrcInt is valid after the call. - bool ReMaterializeTrivialDef(LiveInterval &SrcInt, bool PreserveSrcInt, - unsigned DstReg, unsigned DstSubIdx, - MachineInstr *CopyMI); - - /// shouldJoinPhys - Return true if a physreg copy should be joined. - bool shouldJoinPhys(CoalescerPair &CP); - - /// isWinToJoinCrossClass - Return true if it's profitable to coalesce - /// two virtual registers from different register classes. - bool isWinToJoinCrossClass(unsigned SrcReg, - unsigned DstReg, - const TargetRegisterClass *SrcRC, - const TargetRegisterClass *DstRC, - const TargetRegisterClass *NewRC); - - /// UpdateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and - /// update the subregister number if it is not zero. If DstReg is a - /// physical register and the existing subregister number of the def / use - /// being updated is not zero, make sure to set it to the correct physical - /// subregister. - void UpdateRegDefsUses(const CoalescerPair &CP); - - /// RemoveDeadDef - If a def of a live interval is now determined dead, - /// remove the val# it defines. If the live interval becomes empty, remove - /// it as well. - bool RemoveDeadDef(LiveInterval &li, MachineInstr *DefMI); - - /// RemoveCopyFlag - If DstReg is no longer defined by CopyMI, clear the - /// VNInfo copy flag for DstReg and all aliases. - void RemoveCopyFlag(unsigned DstReg, const MachineInstr *CopyMI); - - /// markAsJoined - Remember that CopyMI has already been joined. - void markAsJoined(MachineInstr *CopyMI); + const TargetRegisterClass *getNewRC() const { return NewRC; } }; } // End llvm namespace -// Because of the way .a files work, we must force the SimpleRC -// implementation to be pulled in if the RegisterCoalescing header is -// included. Otherwise we run the risk of RegisterCoalescing being -// used, but the default implementation not being linked into the tool -// that uses it. -FORCE_DEFINING_FILE_TO_BE_LINKED(RegisterCoalescer) -FORCE_DEFINING_FILE_TO_BE_LINKED(SimpleRegisterCoalescing) - #endif