RegisterCoalescer.h revision ca08dcc4834341e44abf02b92a67ac7d1a708e1d
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 23namespace 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 /// An abstract interface for register allocators to interact with 164 /// coalescers 165 /// 166 /// Example: 167 /// 168 /// This is simply an example of how to use the RegallocQuery 169 /// interface. It is not meant to be used in production. 170 /// 171 /// class LinearScanRegallocQuery : public RegallocQuery { 172 /// private: 173 /// const LiveIntervals \&li; 174 /// 175 /// public: 176 /// LinearScanRegallocQuery(LiveIntervals &intervals) 177 /// : li(intervals) {} 178 /// 179 /// /// This is pretty slow and conservative, but since linear scan 180 /// /// allocation doesn't pre-compute interference information it's 181 /// /// the best we can do. Coalescers are always free to ignore this 182 /// /// and implement their own discovery strategy. See 183 /// /// RegisterCoalescer for an example. 184 /// void getInterferences(IntervalSet &interferences, 185 /// const LiveInterval &a) const { 186 /// for(LiveIntervals::const_iterator iv = li.begin(), 187 /// ivend = li.end(); 188 /// iv != ivend; 189 /// ++iv) { 190 /// if (interfere(a, iv->second)) { 191 /// interferences.insert(&iv->second); 192 /// } 193 /// } 194 /// } 195 /// 196 /// /// This is *really* slow and stupid. See above. 197 /// int getNumberOfInterferences(const LiveInterval &a) const { 198 /// IntervalSet intervals; 199 /// getInterferences(intervals, a); 200 /// return intervals.size(); 201 /// } 202 /// }; 203 /// 204 /// In the allocator: 205 /// 206 /// RegisterCoalescer &coalescer = getAnalysis<RegisterCoalescer>(); 207 /// 208 /// // We don't reset the coalescer so if it's already been run this 209 /// // takes almost no time. 210 /// LinearScanRegallocQuery ifd(*li_); 211 /// 212 class RegallocQuery { 213 public: 214 typedef SmallPtrSet<const LiveInterval *, 8> IntervalSet; 215 216 virtual ~RegallocQuery() {} 217 218 /// Return whether two live ranges interfere. 219 virtual bool interfere(const LiveInterval &a, 220 const LiveInterval &b) const { 221 // A naive test 222 return a.overlaps(b); 223 } 224 225 /// Return the set of intervals that interfere with this one. 226 virtual void getInterferences(IntervalSet &interferences, 227 const LiveInterval &a) const = 0; 228 229 /// This can often be cheaper than actually returning the 230 /// interferences. 231 virtual int getNumberOfInterferences(const LiveInterval &a) const = 0; 232 233 /// Make any data structure updates necessary to reflect 234 /// coalescing or other modifications. 235 virtual void updateDataForMerge(const LiveInterval &a, 236 const LiveInterval &b, 237 const MachineInstr ©) {} 238 239 /// Allow the register allocator to communicate when it doesn't 240 /// want a copy coalesced. This may be due to assumptions made by 241 /// the allocator about various invariants and so this question is 242 /// a matter of legality, not performance. Performance decisions 243 /// about which copies to coalesce should be made by the 244 /// coalescer. 245 virtual bool isLegalToCoalesce(const MachineInstr &inst) const { 246 return true; 247 } 248 }; 249 250 251 /// CoalescerPair - A helper class for register coalescers. When deciding if 252 /// two registers can be coalesced, CoalescerPair can determine if a copy 253 /// instruction would become an identity copy after coalescing. 254 class CoalescerPair { 255 const TargetInstrInfo &tii_; 256 const TargetRegisterInfo &tri_; 257 258 /// dstReg_ - The register that will be left after coalescing. It can be a 259 /// virtual or physical register. 260 unsigned dstReg_; 261 262 /// srcReg_ - the virtual register that will be coalesced into dstReg. 263 unsigned srcReg_; 264 265 /// subReg_ - The subregister index of srcReg in dstReg_. It is possible the 266 /// coalesce srcReg_ into a subreg of the larger dstReg_ when dstReg_ is a 267 /// virtual register. 268 unsigned subIdx_; 269 270 /// partial_ - True when the original copy was a partial subregister copy. 271 bool partial_; 272 273 /// crossClass_ - True when both regs are virtual, and newRC is constrained. 274 bool crossClass_; 275 276 /// flipped_ - True when DstReg and SrcReg are reversed from the oriignal copy 277 /// instruction. 278 bool flipped_; 279 280 /// newRC_ - The register class of the coalesced register, or NULL if dstReg_ 281 /// is a physreg. 282 const TargetRegisterClass *newRC_; 283 284 /// compose - Compose subreg indices a and b, either may be 0. 285 unsigned compose(unsigned, unsigned) const; 286 287 /// isMoveInstr - Return true if MI is a move or subreg instruction. 288 bool isMoveInstr(const MachineInstr *MI, unsigned &Src, unsigned &Dst, 289 unsigned &SrcSub, unsigned &DstSub) const; 290 291 public: 292 CoalescerPair(const TargetInstrInfo &tii, const TargetRegisterInfo &tri) 293 : tii_(tii), tri_(tri), dstReg_(0), srcReg_(0), subIdx_(0), 294 partial_(false), crossClass_(false), flipped_(false), newRC_(0) {} 295 296 /// setRegisters - set registers to match the copy instruction MI. Return 297 /// false if MI is not a coalescable copy instruction. 298 bool setRegisters(const MachineInstr*); 299 300 /// flip - Swap srcReg_ and dstReg_. Return false if swapping is impossible 301 /// because dstReg_ is a physical register, or subIdx_ is set. 302 bool flip(); 303 304 /// isCoalescable - Return true if MI is a copy instruction that will become 305 /// an identity copy after coalescing. 306 bool isCoalescable(const MachineInstr*) const; 307 308 /// isPhys - Return true if DstReg is a physical register. 309 bool isPhys() const { return !newRC_; } 310 311 /// isPartial - Return true if the original copy instruction did not copy the 312 /// full register, but was a subreg operation. 313 bool isPartial() const { return partial_; } 314 315 /// isCrossClass - Return true if DstReg is virtual and NewRC is a smaller register class than DstReg's. 316 bool isCrossClass() const { return crossClass_; } 317 318 /// isFlipped - Return true when getSrcReg is the register being defined by 319 /// the original copy instruction. 320 bool isFlipped() const { return flipped_; } 321 322 /// getDstReg - Return the register (virtual or physical) that will remain 323 /// after coalescing. 324 unsigned getDstReg() const { return dstReg_; } 325 326 /// getSrcReg - Return the virtual register that will be coalesced away. 327 unsigned getSrcReg() const { return srcReg_; } 328 329 /// getSubIdx - Return the subregister index in DstReg that SrcReg will be 330 /// coalesced into, or 0. 331 unsigned getSubIdx() const { return subIdx_; } 332 333 /// getNewRC - Return the register class of the coalesced register. 334 const TargetRegisterClass *getNewRC() const { return newRC_; } 335 }; 336} // End llvm namespace 337 338#endif 339