X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSimpleRegisterCoalescing.h;h=abe392990d1ce2299dcb48092e9eb5219d6e712f;hb=a29c13086a3add78a3a79f744573fe09eaa9dc88;hp=c3b28956635e5b91fdf446da70feff04cf4be30f;hpb=22f07ffd27d1d721634d502c37267721d2e025cf;p=oota-llvm.git diff --git a/lib/CodeGen/SimpleRegisterCoalescing.h b/lib/CodeGen/SimpleRegisterCoalescing.h index c3b28956635..abe392990d1 100644 --- a/lib/CodeGen/SimpleRegisterCoalescing.h +++ b/lib/CodeGen/SimpleRegisterCoalescing.h @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -25,7 +25,7 @@ namespace llvm { class SimpleRegisterCoalescing; class LiveVariables; - class MRegisterInfo; + class TargetRegisterInfo; class TargetInstrInfo; class VirtRegMap; class MachineLoopInfo; @@ -34,12 +34,10 @@ namespace llvm { /// struct CopyRec { MachineInstr *MI; - unsigned SrcReg, DstReg; unsigned LoopDepth; bool isBackEdge; - CopyRec(MachineInstr *mi, unsigned src, unsigned dst, unsigned depth, - bool be) - : MI(mi), SrcReg(src), DstReg(dst), LoopDepth(depth), isBackEdge(be) {}; + CopyRec(MachineInstr *mi, unsigned depth, bool be) + : MI(mi), LoopDepth(depth), isBackEdge(be) {}; }; template class JoinPriorityQueue; @@ -48,7 +46,7 @@ namespace llvm { /// struct CopyRecSort : public std::binary_function { JoinPriorityQueue *JPQ; - CopyRecSort(JoinPriorityQueue *jpq) : JPQ(jpq) {} + explicit CopyRecSort(JoinPriorityQueue *jpq) : JPQ(jpq) {} CopyRecSort(const CopyRecSort &RHS) : JPQ(RHS.JPQ) {} bool operator()(CopyRec left, CopyRec right) const; }; @@ -61,12 +59,13 @@ namespace llvm { std::priority_queue, SF> Queue; public: - JoinPriorityQueue(SimpleRegisterCoalescing *rc) : Rc(rc), Queue(SF(this)) {} + explicit JoinPriorityQueue(SimpleRegisterCoalescing *rc) + : Rc(rc), Queue(SF(this)) {} bool empty() const { return Queue.empty(); } void push(CopyRec R) { Queue.push(R); } CopyRec pop() { - if (empty()) return CopyRec(0, 0, 0, 0, false); + if (empty()) return CopyRec(0, 0, false); CopyRec R = Queue.top(); Queue.pop(); return R; @@ -79,43 +78,35 @@ namespace llvm { class SimpleRegisterCoalescing : public MachineFunctionPass, public RegisterCoalescer { MachineFunction* mf_; + MachineRegisterInfo* mri_; const TargetMachine* tm_; - const MRegisterInfo* mri_; + const TargetRegisterInfo* tri_; const TargetInstrInfo* tii_; LiveIntervals *li_; - LiveVariables *lv_; const MachineLoopInfo* loopInfo; BitVector allocatableRegs_; DenseMap allocatableRCRegs_; - /// r2rMap_ - Map from register to its representative register. - /// - IndexedMap r2rMap_; - - /// r2rRevMap_ - Reverse of r2rRevMap_, i.e. Map from register to all - /// the registers it represent. - IndexedMap > r2rRevMap_; - /// JoinQueue - A priority queue of copy instructions the coalescer is /// going to process. JoinPriorityQueue *JoinQueue; - /// JoinedLIs - Keep track which register intervals have been coalesced - /// with other intervals. - BitVector JoinedLIs; - - /// SubRegIdxes - Keep track of sub-register and indexes. - /// - SmallVector, 32> SubRegIdxes; - /// 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((intptr_t)&ID) {} + SimpleRegisterCoalescing() : MachineFunctionPass(&ID) {} struct InstrSlots { enum { @@ -141,10 +132,10 @@ namespace llvm { /// getRepIntervalSize - Called from join priority queue sorting function. /// It returns the size of the interval that represent the given register. unsigned getRepIntervalSize(unsigned Reg) { - Reg = rep(Reg); if (!li_->hasInterval(Reg)) return 0; - return li_->getInterval(Reg).getSize(); + return li_->getApproximateInstructionCount(li_->getInterval(Reg)) * + LiveIntervals::InstrSlots::NUM; } /// print - Implement the dump method. @@ -167,7 +158,7 @@ namespace llvm { /// 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(CopyRec TheCopy, bool &Again); + bool JoinCopy(CopyRec &TheCopy, bool &Again); /// JoinIntervals - Attempt to join these two intervals. On failure, this /// returns false. Otherwise, if one of the intervals being joined is a @@ -183,52 +174,110 @@ namespace llvm { /// joins them and returns true. bool SimpleJoin(LiveInterval &LHS, LiveInterval &RHS); - /// Return true if the two specified registers belong to different - /// register classes. The registers may be either phys or virt regs. - bool differingRegisterClasses(unsigned RegA, unsigned RegB) const; - - + /// Return true if the two specified registers belong to different register + /// classes. The registers may be either phys or virt regs. In the + /// case where both registers are virtual registers, it would also returns + /// true by reference the RegB register class in SubRC if it is a subset of + /// RegA's register class. + bool differingRegisterClasses(unsigned RegA, unsigned RegB, + const TargetRegisterClass *&SubRC) const; + + + /// 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(LiveInterval &IntA, LiveInterval &IntB, MachineInstr *CopyMI); - /// AddSubRegIdxPairs - Recursively mark all the registers represented by the - /// specified register as sub-registers. The recursion level is expected to be - /// shallow. - void AddSubRegIdxPairs(unsigned Reg, unsigned SubIdx); - - /// isBackEdgeCopy - Returns true if CopyMI is a back edge copy. + /// 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(LiveInterval &IntA, LiveInterval &IntB, + MachineInstr *CopyMI); + + bool ReMaterializeTrivialDef(LiveInterval &SrcInt, unsigned DstReg, + MachineInstr *CopyMI); + + /// TurnCopyIntoImpDef - If source of the specified copy is an implicit def, + /// turn the copy into an implicit def. + bool TurnCopyIntoImpDef(MachineBasicBlock::iterator &I, + MachineBasicBlock *MBB, + unsigned DstReg, unsigned SrcReg); + + /// CanCoalesceWithImpDef - Returns true if the specified copy instruction + /// from an implicit def to another register can be coalesced away. + bool CanCoalesceWithImpDef(MachineInstr *CopyMI, + LiveInterval &li, LiveInterval &ImpLi) const; + + /// RemoveCopiesFromValNo - The specified value# is defined by an implicit + /// def and it is being removed. Turn all copies from this value# into + /// identity copies so they will be removed. + void RemoveCopiesFromValNo(LiveInterval &li, VNInfo *VNI); + + /// isProfitableToCoalesceToSubRC - Given that register class of DstReg is + /// a subset of the register class of SrcReg, return true if it's profitable + /// to coalesce the two registers. + bool isProfitableToCoalesceToSubRC(unsigned SrcReg, unsigned DstReg, + MachineBasicBlock *MBB); + + /// HasIncompatibleSubRegDefUse - If we are trying to coalesce a virtual + /// register with a physical register, check if any of the virtual register + /// operand is a sub-register use or def. If so, make sure it won't result + /// in an illegal extract_subreg or insert_subreg instruction. + bool HasIncompatibleSubRegDefUse(MachineInstr *CopyMI, + unsigned VirtReg, unsigned PhysReg); + + /// RangeIsDefinedByCopyFromReg - Return true if the specified live range of + /// the specified live interval is defined by a copy from the specified + /// register. + bool RangeIsDefinedByCopyFromReg(LiveInterval &li, LiveRange *LR, + unsigned Reg); + + /// isBackEdgeCopy - Return true if CopyMI is a back edge copy. /// - bool isBackEdgeCopy(MachineInstr *CopyMI, unsigned DstReg); + bool isBackEdgeCopy(MachineInstr *CopyMI, unsigned DstReg) const; + + /// 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(unsigned SrcReg, unsigned DstReg, unsigned SubIdx); + + /// RemoveDeadImpDef - Remove implicit_def instructions which are + /// "re-defining" registers due to insert_subreg coalescing. e.g. + void RemoveDeadImpDef(unsigned Reg, LiveInterval &LI); + + /// RemoveUnnecessaryKills - Remove kill markers that are no longer accurate + /// due to live range lengthening as the result of coalescing. + void RemoveUnnecessaryKills(unsigned Reg, LiveInterval &LI); + + /// ShortenDeadCopyLiveRange - Shorten a live range defined by a dead copy. + /// Return true if live interval is removed. + bool ShortenDeadCopyLiveRange(LiveInterval &li, MachineInstr *CopyMI); + + /// ShortenDeadCopyLiveRange - Shorten a live range as it's artificially + /// extended by a dead copy. Mark the last use (if any) of the val# as kill + /// as ends the live range there. If there isn't another use, then this + /// live range is dead. Return true if live interval is removed. + bool ShortenDeadCopySrcLiveRange(LiveInterval &li, MachineInstr *CopyMI); + + /// 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); /// lastRegisterUse - Returns the last use of the specific register between - /// cycles Start and End. It also returns the use operand by reference. It - /// returns NULL if there are no uses. - MachineInstr *lastRegisterUse(unsigned Start, unsigned End, unsigned Reg, - MachineOperand *&MOU); - - /// findDefOperand - Returns the MachineOperand that is a def of the specific - /// register. It returns NULL if the def is not found. - MachineOperand *findDefOperand(MachineInstr *MI, unsigned Reg); - - /// unsetRegisterKill - Unset IsKill property of all uses of the specific - /// register of the specific instruction. - void unsetRegisterKill(MachineInstr *MI, unsigned Reg); - - /// unsetRegisterKills - Unset IsKill property of all uses of specific register - /// between cycles Start and End. - void unsetRegisterKills(unsigned Start, unsigned End, unsigned Reg); - - /// hasRegisterDef - True if the instruction defines the specific register. - /// - bool hasRegisterDef(MachineInstr *MI, unsigned Reg); - - /// rep - returns the representative of this register - unsigned rep(unsigned Reg) { - unsigned Rep = r2rMap_[Reg]; - if (Rep) - return r2rMap_[Reg] = rep(Rep); - return Reg; - } + /// cycles Start and End or NULL if there are no uses. + MachineOperand *lastRegisterUse(unsigned Start, unsigned End, unsigned Reg, + unsigned &LastUseIdx) const; void printRegName(unsigned reg) const; };