X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSimpleRegisterCoalescing.h;h=f668064ab08eb81af462766ce14885a7101699fc;hb=3b131d7cc4dc4bbb329c136705b37dc255995fbd;hp=cce5cebd9e6f1bc1a164aff86245fd2c70fd75d1;hpb=8c08d8c77c45d4721e7d3ef746cca9e39b28e379;p=oota-llvm.git diff --git a/lib/CodeGen/SimpleRegisterCoalescing.h b/lib/CodeGen/SimpleRegisterCoalescing.h index cce5cebd9e6..f668064ab08 100644 --- a/lib/CodeGen/SimpleRegisterCoalescing.h +++ b/lib/CodeGen/SimpleRegisterCoalescing.h @@ -18,7 +18,6 @@ #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/RegisterCoalescer.h" #include "llvm/ADT/BitVector.h" -#include namespace llvm { class SimpleRegisterCoalescing; @@ -33,44 +32,8 @@ namespace llvm { struct CopyRec { MachineInstr *MI; unsigned LoopDepth; - bool isBackEdge; - CopyRec(MachineInstr *mi, unsigned depth, bool be) - : MI(mi), LoopDepth(depth), isBackEdge(be) {}; - }; - - template class JoinPriorityQueue; - - /// CopyRecSort - Sorting function for coalescer queue. - /// - struct CopyRecSort : public std::binary_function { - JoinPriorityQueue *JPQ; - explicit CopyRecSort(JoinPriorityQueue *jpq) : JPQ(jpq) {} - CopyRecSort(const CopyRecSort &RHS) : JPQ(RHS.JPQ) {} - bool operator()(CopyRec left, CopyRec right) const; - }; - - /// JoinQueue - A priority queue of copy instructions the coalescer is - /// going to process. - template - class JoinPriorityQueue { - SimpleRegisterCoalescing *Rc; - std::priority_queue, SF> Queue; - - public: - 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, false); - CopyRec R = Queue.top(); - Queue.pop(); - return R; - } - - // Callbacks to SimpleRegisterCoalescing. - unsigned getRepIntervalSize(unsigned Reg); + CopyRec(MachineInstr *mi, unsigned depth) + : MI(mi), LoopDepth(depth) {} }; class SimpleRegisterCoalescing : public MachineFunctionPass, @@ -82,14 +45,11 @@ namespace llvm { const TargetInstrInfo* tii_; LiveIntervals *li_; const MachineLoopInfo* loopInfo; + AliasAnalysis *AA; BitVector allocatableRegs_; DenseMap allocatableRCRegs_; - /// JoinQueue - A priority queue of copy instructions the coalescer is - /// going to process. - JoinPriorityQueue *JoinQueue; - /// JoinedCopies - Keep track of copies eliminated due to coalescing. /// SmallPtrSet JoinedCopies; @@ -125,22 +85,10 @@ namespace llvm { bool coalesceFunction(MachineFunction &mf, RegallocQuery &) { // This runs as an independent pass, so don't do anything. return false; - }; - - /// getRepIntervalSize - Called from join priority queue sorting function. - /// It returns the size of the interval that represent the given register. - unsigned getRepIntervalSize(unsigned Reg) { - if (!li_->hasInterval(Reg)) - return 0; - return li_->getApproximateInstructionCount(li_->getInterval(Reg)) * - LiveIntervals::InstrSlots::NUM; } /// print - Implement the dump method. - virtual void print(std::ostream &O, const Module* = 0) const; - void print(std::ostream *O, const Module* M = 0) const { - if (O) print(*O, M); - } + virtual void print(raw_ostream &O, const Module* = 0) const; private: /// joinIntervals - join compatible live intervals @@ -176,7 +124,6 @@ namespace llvm { /// classes. The registers may be either phys or virt regs. bool differingRegisterClasses(unsigned RegA, unsigned RegB) 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 @@ -196,24 +143,39 @@ namespace llvm { bool RemoveCopyByCommutingDef(LiveInterval &IntA, LiveInterval &IntB, MachineInstr *CopyMI); - bool ReMaterializeTrivialDef(LiveInterval &SrcInt, unsigned DstReg, - MachineInstr *CopyMI); + /// TrimLiveIntervalToLastUse - If there is a last use in the same basic + /// block as the copy instruction, trim the ive interval to the last use + /// and return true. + bool TrimLiveIntervalToLastUse(SlotIndex CopyIdx, + MachineBasicBlock *CopyMBB, + LiveInterval &li, const LiveRange *LR); - /// 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); + /// ReMaterializeTrivialDef - If the source of a copy is defined by a trivial + /// computation, replace the copy by rematerialize the definition. + bool ReMaterializeTrivialDef(LiveInterval &SrcInt, unsigned DstReg, + unsigned DstSubIdx, MachineInstr *CopyMI); /// 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); + /// TurnCopiesFromValNoToImpDefs - The specified value# is defined by an + /// implicit_def and it is being removed. Turn all copies from this value# + /// into implicit_defs. + void TurnCopiesFromValNoToImpDefs(LiveInterval &li, VNInfo *VNI); + + /// isWinToJoinVRWithSrcPhysReg - Return true if it's worth while to join a + /// a virtual destination register with physical source register. + bool isWinToJoinVRWithSrcPhysReg(MachineInstr *CopyMI, + MachineBasicBlock *CopyMBB, + LiveInterval &DstInt, LiveInterval &SrcInt); + + /// isWinToJoinVRWithDstPhysReg - Return true if it's worth while to join a + /// copy from a virtual source register to a physical destination register. + bool isWinToJoinVRWithDstPhysReg(MachineInstr *CopyMI, + MachineBasicBlock *CopyMBB, + LiveInterval &DstInt, LiveInterval &SrcInt); /// isWinToJoinCrossClass - Return true if it's profitable to coalesce /// two virtual registers from different register classes. @@ -239,16 +201,18 @@ namespace llvm { bool CanJoinInsertSubRegToPhysReg(unsigned DstReg, unsigned SrcReg, unsigned SubIdx, unsigned &RealDstReg); + /// ValueLiveAt - Return true if the LiveRange pointed to by the given + /// iterator, or any subsequent range with the same value number, + /// is live at the given point. + bool ValueLiveAt(LiveInterval::iterator LRItr, LiveInterval::iterator LREnd, + SlotIndex defPoint) const; + /// 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) 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 @@ -256,10 +220,6 @@ namespace llvm { /// 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); @@ -281,8 +241,8 @@ namespace llvm { /// lastRegisterUse - Returns the last use of the specific register between /// cycles Start and End or NULL if there are no uses. - MachineOperand *lastRegisterUse(unsigned Start, unsigned End, unsigned Reg, - unsigned &LastUseIdx) const; + MachineOperand *lastRegisterUse(SlotIndex Start, SlotIndex End, + unsigned Reg, SlotIndex &LastUseIdx) const; void printRegName(unsigned reg) const; };