X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FSimpleRegisterCoalescing.h;h=65cf542836dd5a4c18a831def84ec730a07e79db;hb=bcb8c6d09ee426e0f774e3412912f6ae9e5f78dd;hp=0f0d020f79d60be401a12f6184fc2b5e16e9758a;hpb=a461c4d75b66135ff6f3d41b46a08054b8fc1dc8;p=oota-llvm.git diff --git a/lib/CodeGen/SimpleRegisterCoalescing.h b/lib/CodeGen/SimpleRegisterCoalescing.h index 0f0d020f79d..65cf542836d 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. // //===----------------------------------------------------------------------===// // @@ -15,76 +15,59 @@ #define LLVM_CODEGEN_SIMPLE_REGISTER_COALESCING_H #include "llvm/CodeGen/MachineFunctionPass.h" -#include "llvm/CodeGen/LiveInterval.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/RegisterCoalescer.h" #include "llvm/ADT/BitVector.h" -#include "llvm/ADT/IndexedMap.h" namespace llvm { - - class LiveVariables; - class MRegisterInfo; + class SimpleRegisterCoalescing; + class LiveDebugVariables; + class TargetRegisterInfo; class TargetInstrInfo; class VirtRegMap; + class MachineLoopInfo; + + /// CopyRec - Representation for copy instructions in coalescer queue. + /// + struct CopyRec { + MachineInstr *MI; + unsigned LoopDepth; + CopyRec(MachineInstr *mi, unsigned depth) + : MI(mi), LoopDepth(depth) {} + }; 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_; + LiveDebugVariables *ldv_; + const MachineLoopInfo* loopInfo; + AliasAnalysis *AA; - BitVector allocatableRegs_; DenseMap allocatableRCRegs_; - /// r2rMap_ - Map from register to its representative register. + /// JoinedCopies - Keep track of copies eliminated due to coalescing. /// - IndexedMap r2rMap_; - - /// r2rRevMap_ - Reverse of r2rRevMap_, i.e. Map from register to all - /// the registers it represent. - IndexedMap > r2rRevMap_; - - /// JoinedLIs - Keep track which register intervals have been coalesced - /// with other intervals. - BitVector JoinedLIs; + SmallPtrSet JoinedCopies; - /// SubRegIdxes - Keep track of sub-register and indexes. + /// ReMatCopies - Keep track of copies eliminated due to remat. /// - SmallVector, 32> SubRegIdxes; + SmallPtrSet ReMatCopies; - /// JoinedCopies - Keep track of copies eliminated due to coalescing. - /// - SmallPtrSet JoinedCopies; + /// 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) {} - - struct CopyRec { - MachineInstr *MI; - unsigned SrcReg, DstReg; - }; - CopyRec getCopyRec(MachineInstr *MI, unsigned SrcReg, unsigned DstReg) { - CopyRec R; - R.MI = MI; - R.SrcReg = SrcReg; - R.DstReg = DstReg; - return R; + SimpleRegisterCoalescing() : MachineFunctionPass(ID) { + initializeSimpleRegisterCoalescingPass(*PassRegistry::getPassRegistry()); } - struct InstrSlots { - enum { - LOAD = 0, - USE = 1, - DEF = 2, - STORE = 3, - NUM = 4 - }; - }; - + virtual void getAnalysisUsage(AnalysisUsage &AU) const; virtual void releaseMemory(); @@ -93,16 +76,13 @@ namespace llvm { bool coalesceFunction(MachineFunction &mf, RegallocQuery &) { // This runs as an independent pass, so don't do anything. - return(false); - }; + return false; + } /// 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: + private: /// joinIntervals - join compatible live intervals void joinIntervals(); @@ -116,67 +96,92 @@ 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(MachineInstr *CopyMI, unsigned SrcReg, unsigned DstReg, - bool &Again); - - /// JoinIntervals - Attempt to join these two intervals. On failure, this - /// returns false. Otherwise, if one of the intervals being joined is a - /// physreg, this method always canonicalizes DestInt to be it. The output - /// "SrcInt" will not have been modified, so we can use this information - /// below to update aliases. - bool JoinIntervals(LiveInterval &LHS, LiveInterval &RHS, bool &Swapped); - - /// SimpleJoin - Attempt to join the specified interval into this one. The - /// caller of this method must guarantee that the RHS only contains a single - /// value number and that the RHS is not defined by a copy from this - /// interval. This returns false if the intervals are not joinable, or it - /// 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; + bool JoinCopy(CopyRec &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); - bool AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB, - MachineInstr *CopyMI); + /// 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; - /// 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); + /// 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); + + /// 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); + + /// 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); + + /// 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); + + /// 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); /// 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(SlotIndex Start, SlotIndex End, + unsigned Reg, SlotIndex &LastUseIdx) const; - void printRegName(unsigned reg) const; + /// markAsJoined - Remember that CopyMI has already been joined. + void markAsJoined(MachineInstr *CopyMI); }; } // End llvm namespace