1 //===-- RegisterCoalescer.h - Register Coalescing Interface ------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file contains the abstract interface for register coalescers, 11 // allowing them to interact with and query register allocators. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "RegisterClassInfo.h" 16 #include "llvm/Support/IncludeFile.h" 17 #include "llvm/CodeGen/LiveInterval.h" 18 #include "llvm/ADT/SmallPtrSet.h" 19 20 #ifndef LLVM_CODEGEN_REGISTER_COALESCER_H 21 #define LLVM_CODEGEN_REGISTER_COALESCER_H 22 23 namespace llvm { 24 25 class MachineFunction; 26 class RegallocQuery; 27 class AnalysisUsage; 28 class MachineInstr; 29 class TargetRegisterInfo; 30 class TargetRegisterClass; 31 class TargetInstrInfo; 32 class LiveDebugVariables; 33 class VirtRegMap; 34 class MachineLoopInfo; 35 36 class CoalescerPair; 37 38 /// An abstract interface for register coalescers. Coalescers must 39 /// implement this interface to be part of the coalescer analysis 40 /// group. 41 class RegisterCoalescer : public MachineFunctionPass { 42 MachineFunction* mf_; 43 MachineRegisterInfo* mri_; 44 const TargetMachine* tm_; 45 const TargetRegisterInfo* tri_; 46 const TargetInstrInfo* tii_; 47 LiveIntervals *li_; 48 LiveDebugVariables *ldv_; 49 const MachineLoopInfo* loopInfo; 50 AliasAnalysis *AA; 51 RegisterClassInfo RegClassInfo; 52 53 /// JoinedCopies - Keep track of copies eliminated due to coalescing. 54 /// 55 SmallPtrSet<MachineInstr*, 32> JoinedCopies; 56 57 /// ReMatCopies - Keep track of copies eliminated due to remat. 58 /// 59 SmallPtrSet<MachineInstr*, 32> ReMatCopies; 60 61 /// ReMatDefs - Keep track of definition instructions which have 62 /// been remat'ed. 63 SmallPtrSet<MachineInstr*, 8> ReMatDefs; 64 65 /// joinIntervals - join compatible live intervals 66 void joinIntervals(); 67 68 /// CopyCoalesceInMBB - Coalesce copies in the specified MBB, putting 69 /// copies that cannot yet be coalesced into the "TryAgain" list. 70 void CopyCoalesceInMBB(MachineBasicBlock *MBB, 71 std::vector<MachineInstr*> &TryAgain); 72 73 /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, 74 /// which are the src/dst of the copy instruction CopyMI. This returns true 75 /// if the copy was successfully coalesced away. If it is not currently 76 /// possible to coalesce this interval, but it may be possible if other 77 /// things get coalesced, then it returns true by reference in 'Again'. 78 bool JoinCopy(MachineInstr *TheCopy, bool &Again); 79 80 /// JoinIntervals - Attempt to join these two intervals. On failure, this 81 /// returns false. The output "SrcInt" will not have been modified, so we can 82 /// use this information below to update aliases. 83 bool JoinIntervals(CoalescerPair &CP); 84 85 /// AdjustCopiesBackFrom - We found a non-trivially-coalescable copy. If 86 /// the source value number is defined by a copy from the destination reg 87 /// see if we can merge these two destination reg valno# into a single 88 /// value number, eliminating a copy. 89 bool AdjustCopiesBackFrom(const CoalescerPair &CP, MachineInstr *CopyMI); 90 91 /// HasOtherReachingDefs - Return true if there are definitions of IntB 92 /// other than BValNo val# that can reach uses of AValno val# of IntA. 93 bool HasOtherReachingDefs(LiveInterval &IntA, LiveInterval &IntB, 94 VNInfo *AValNo, VNInfo *BValNo); 95 96 /// RemoveCopyByCommutingDef - We found a non-trivially-coalescable copy. 97 /// If the source value number is defined by a commutable instruction and 98 /// its other operand is coalesced to the copy dest register, see if we 99 /// can transform the copy into a noop by commuting the definition. 100 bool RemoveCopyByCommutingDef(const CoalescerPair &CP,MachineInstr *CopyMI); 101 102 /// ReMaterializeTrivialDef - If the source of a copy is defined by a trivial 103 /// computation, replace the copy by rematerialize the definition. 104 /// If PreserveSrcInt is true, make sure SrcInt is valid after the call. 105 bool ReMaterializeTrivialDef(LiveInterval &SrcInt, bool PreserveSrcInt, 106 unsigned DstReg, unsigned DstSubIdx, 107 MachineInstr *CopyMI); 108 109 /// shouldJoinPhys - Return true if a physreg copy should be joined. 110 bool shouldJoinPhys(CoalescerPair &CP); 111 112 /// isWinToJoinCrossClass - Return true if it's profitable to coalesce 113 /// two virtual registers from different register classes. 114 bool isWinToJoinCrossClass(unsigned SrcReg, 115 unsigned DstReg, 116 const TargetRegisterClass *SrcRC, 117 const TargetRegisterClass *DstRC, 118 const TargetRegisterClass *NewRC); 119 120 /// UpdateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and 121 /// update the subregister number if it is not zero. If DstReg is a 122 /// physical register and the existing subregister number of the def / use 123 /// being updated is not zero, make sure to set it to the correct physical 124 /// subregister. 125 void UpdateRegDefsUses(const CoalescerPair &CP); 126 127 /// RemoveDeadDef - If a def of a live interval is now determined dead, 128 /// remove the val# it defines. If the live interval becomes empty, remove 129 /// it as well. 130 bool RemoveDeadDef(LiveInterval &li, MachineInstr *DefMI); 131 132 /// RemoveCopyFlag - If DstReg is no longer defined by CopyMI, clear the 133 /// VNInfo copy flag for DstReg and all aliases. 134 void RemoveCopyFlag(unsigned DstReg, const MachineInstr *CopyMI); 135 136 /// markAsJoined - Remember that CopyMI has already been joined. 137 void markAsJoined(MachineInstr *CopyMI); 138 139 public: 140 static char ID; // Class identification, replacement for typeinfo 141 RegisterCoalescer() : MachineFunctionPass(ID) { 142 initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry()); 143 } 144 145 /// Register allocators must call this from their own 146 /// getAnalysisUsage to cover the case where the coalescer is not 147 /// a Pass in the proper sense and isn't managed by PassManager. 148 /// PassManager needs to know which analyses to make available and 149 /// which to invalidate when running the register allocator or any 150 /// pass that might call coalescing. The long-term solution is to 151 /// allow hierarchies of PassManagers. 152 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 153 154 virtual void releaseMemory(); 155 156 /// runOnMachineFunction - pass entry point 157 virtual bool runOnMachineFunction(MachineFunction&); 158 159 /// print - Implement the dump method. 160 virtual void print(raw_ostream &O, const Module* = 0) const; 161 }; 162 163 /// CoalescerPair - A helper class for register coalescers. When deciding if 164 /// two registers can be coalesced, CoalescerPair can determine if a copy 165 /// instruction would become an identity copy after coalescing. 166 class CoalescerPair { 167 const TargetInstrInfo &tii_; 168 const TargetRegisterInfo &tri_; 169 170 /// dstReg_ - The register that will be left after coalescing. It can be a 171 /// virtual or physical register. 172 unsigned dstReg_; 173 174 /// srcReg_ - the virtual register that will be coalesced into dstReg. 175 unsigned srcReg_; 176 177 /// subReg_ - The subregister index of srcReg in dstReg_. It is possible the 178 /// coalesce srcReg_ into a subreg of the larger dstReg_ when dstReg_ is a 179 /// virtual register. 180 unsigned subIdx_; 181 182 /// partial_ - True when the original copy was a partial subregister copy. 183 bool partial_; 184 185 /// crossClass_ - True when both regs are virtual, and newRC is constrained. 186 bool crossClass_; 187 188 /// flipped_ - True when DstReg and SrcReg are reversed from the oriignal copy 189 /// instruction. 190 bool flipped_; 191 192 /// newRC_ - The register class of the coalesced register, or NULL if dstReg_ 193 /// is a physreg. 194 const TargetRegisterClass *newRC_; 195 196 public: 197 CoalescerPair(const TargetInstrInfo &tii, const TargetRegisterInfo &tri) 198 : tii_(tii), tri_(tri), dstReg_(0), srcReg_(0), subIdx_(0), 199 partial_(false), crossClass_(false), flipped_(false), newRC_(0) {} 200 201 /// setRegisters - set registers to match the copy instruction MI. Return 202 /// false if MI is not a coalescable copy instruction. 203 bool setRegisters(const MachineInstr*); 204 205 /// flip - Swap srcReg_ and dstReg_. Return false if swapping is impossible 206 /// because dstReg_ is a physical register, or subIdx_ is set. 207 bool flip(); 208 209 /// isCoalescable - Return true if MI is a copy instruction that will become 210 /// an identity copy after coalescing. 211 bool isCoalescable(const MachineInstr*) const; 212 213 /// isPhys - Return true if DstReg is a physical register. 214 bool isPhys() const { return !newRC_; } 215 216 /// isPartial - Return true if the original copy instruction did not copy the 217 /// full register, but was a subreg operation. 218 bool isPartial() const { return partial_; } 219 220 /// isCrossClass - Return true if DstReg is virtual and NewRC is a smaller register class than DstReg's. 221 bool isCrossClass() const { return crossClass_; } 222 223 /// isFlipped - Return true when getSrcReg is the register being defined by 224 /// the original copy instruction. 225 bool isFlipped() const { return flipped_; } 226 227 /// getDstReg - Return the register (virtual or physical) that will remain 228 /// after coalescing. 229 unsigned getDstReg() const { return dstReg_; } 230 231 /// getSrcReg - Return the virtual register that will be coalesced away. 232 unsigned getSrcReg() const { return srcReg_; } 233 234 /// getSubIdx - Return the subregister index in DstReg that SrcReg will be 235 /// coalesced into, or 0. 236 unsigned getSubIdx() const { return subIdx_; } 237 238 /// getNewRC - Return the register class of the coalesced register. 239 const TargetRegisterClass *getNewRC() const { return newRC_; } 240 }; 241 } // End llvm namespace 242 243 #endif 244
