David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 1 | //===-- SimpleRegisterCoalescing.h - Register Coalescing --------*- C++ -*-===// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Chris Lattner | 4ee451d | 2007-12-29 20:36:04 +0000 | [diff] [blame^] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This file implements a simple register copy coalescing phase. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
| 14 | #ifndef LLVM_CODEGEN_SIMPLE_REGISTER_COALESCING_H |
| 15 | #define LLVM_CODEGEN_SIMPLE_REGISTER_COALESCING_H |
| 16 | |
| 17 | #include "llvm/CodeGen/MachineFunctionPass.h" |
| 18 | #include "llvm/CodeGen/LiveInterval.h" |
| 19 | #include "llvm/CodeGen/LiveIntervalAnalysis.h" |
David Greene | 2c17c4d | 2007-09-06 16:18:45 +0000 | [diff] [blame] | 20 | #include "llvm/CodeGen/RegisterCoalescer.h" |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 21 | #include "llvm/ADT/BitVector.h" |
| 22 | #include "llvm/ADT/IndexedMap.h" |
Evan Cheng | 8fc9a10 | 2007-11-06 08:52:21 +0000 | [diff] [blame] | 23 | #include <queue> |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 24 | |
| 25 | namespace llvm { |
Evan Cheng | 8fc9a10 | 2007-11-06 08:52:21 +0000 | [diff] [blame] | 26 | class SimpleRegisterCoalescing; |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 27 | class LiveVariables; |
| 28 | class MRegisterInfo; |
| 29 | class TargetInstrInfo; |
| 30 | class VirtRegMap; |
Evan Cheng | 22f07ff | 2007-12-11 02:09:15 +0000 | [diff] [blame] | 31 | class MachineLoopInfo; |
Evan Cheng | 8fc9a10 | 2007-11-06 08:52:21 +0000 | [diff] [blame] | 32 | |
| 33 | /// CopyRec - Representation for copy instructions in coalescer queue. |
| 34 | /// |
| 35 | struct CopyRec { |
| 36 | MachineInstr *MI; |
| 37 | unsigned SrcReg, DstReg; |
| 38 | unsigned LoopDepth; |
| 39 | bool isBackEdge; |
| 40 | CopyRec(MachineInstr *mi, unsigned src, unsigned dst, unsigned depth, |
| 41 | bool be) |
| 42 | : MI(mi), SrcReg(src), DstReg(dst), LoopDepth(depth), isBackEdge(be) {}; |
| 43 | }; |
| 44 | |
| 45 | template<class SF> class JoinPriorityQueue; |
| 46 | |
| 47 | /// CopyRecSort - Sorting function for coalescer queue. |
| 48 | /// |
| 49 | struct CopyRecSort : public std::binary_function<CopyRec,CopyRec,bool> { |
| 50 | JoinPriorityQueue<CopyRecSort> *JPQ; |
Dan Gohman | ded2b0d | 2007-12-14 15:41:34 +0000 | [diff] [blame] | 51 | explicit CopyRecSort(JoinPriorityQueue<CopyRecSort> *jpq) : JPQ(jpq) {} |
Evan Cheng | 8fc9a10 | 2007-11-06 08:52:21 +0000 | [diff] [blame] | 52 | CopyRecSort(const CopyRecSort &RHS) : JPQ(RHS.JPQ) {} |
| 53 | bool operator()(CopyRec left, CopyRec right) const; |
| 54 | }; |
| 55 | |
| 56 | /// JoinQueue - A priority queue of copy instructions the coalescer is |
| 57 | /// going to process. |
| 58 | template<class SF> |
| 59 | class JoinPriorityQueue { |
| 60 | SimpleRegisterCoalescing *Rc; |
| 61 | std::priority_queue<CopyRec, std::vector<CopyRec>, SF> Queue; |
| 62 | |
| 63 | public: |
Dan Gohman | ded2b0d | 2007-12-14 15:41:34 +0000 | [diff] [blame] | 64 | explicit JoinPriorityQueue(SimpleRegisterCoalescing *rc) |
| 65 | : Rc(rc), Queue(SF(this)) {} |
Evan Cheng | 8fc9a10 | 2007-11-06 08:52:21 +0000 | [diff] [blame] | 66 | |
| 67 | bool empty() const { return Queue.empty(); } |
| 68 | void push(CopyRec R) { Queue.push(R); } |
| 69 | CopyRec pop() { |
| 70 | if (empty()) return CopyRec(0, 0, 0, 0, false); |
| 71 | CopyRec R = Queue.top(); |
| 72 | Queue.pop(); |
| 73 | return R; |
| 74 | } |
| 75 | |
| 76 | // Callbacks to SimpleRegisterCoalescing. |
| 77 | unsigned getRepIntervalSize(unsigned Reg); |
| 78 | }; |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 79 | |
David Greene | 2c17c4d | 2007-09-06 16:18:45 +0000 | [diff] [blame] | 80 | class SimpleRegisterCoalescing : public MachineFunctionPass, |
| 81 | public RegisterCoalescer { |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 82 | MachineFunction* mf_; |
| 83 | const TargetMachine* tm_; |
| 84 | const MRegisterInfo* mri_; |
| 85 | const TargetInstrInfo* tii_; |
| 86 | LiveIntervals *li_; |
| 87 | LiveVariables *lv_; |
Evan Cheng | 22f07ff | 2007-12-11 02:09:15 +0000 | [diff] [blame] | 88 | const MachineLoopInfo* loopInfo; |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 89 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 90 | BitVector allocatableRegs_; |
| 91 | DenseMap<const TargetRegisterClass*, BitVector> allocatableRCRegs_; |
| 92 | |
Evan Cheng | 4ae31a5 | 2007-10-18 07:49:59 +0000 | [diff] [blame] | 93 | /// r2rMap_ - Map from register to its representative register. |
| 94 | /// |
| 95 | IndexedMap<unsigned> r2rMap_; |
| 96 | |
| 97 | /// r2rRevMap_ - Reverse of r2rRevMap_, i.e. Map from register to all |
| 98 | /// the registers it represent. |
| 99 | IndexedMap<std::vector<unsigned> > r2rRevMap_; |
| 100 | |
Evan Cheng | 8fc9a10 | 2007-11-06 08:52:21 +0000 | [diff] [blame] | 101 | /// JoinQueue - A priority queue of copy instructions the coalescer is |
| 102 | /// going to process. |
| 103 | JoinPriorityQueue<CopyRecSort> *JoinQueue; |
| 104 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 105 | /// JoinedLIs - Keep track which register intervals have been coalesced |
| 106 | /// with other intervals. |
| 107 | BitVector JoinedLIs; |
| 108 | |
Evan Cheng | 4ae31a5 | 2007-10-18 07:49:59 +0000 | [diff] [blame] | 109 | /// SubRegIdxes - Keep track of sub-register and indexes. |
Evan Cheng | 32dfbea | 2007-10-12 08:50:34 +0000 | [diff] [blame] | 110 | /// |
Evan Cheng | 4ae31a5 | 2007-10-18 07:49:59 +0000 | [diff] [blame] | 111 | SmallVector<std::pair<unsigned, unsigned>, 32> SubRegIdxes; |
Evan Cheng | 32dfbea | 2007-10-12 08:50:34 +0000 | [diff] [blame] | 112 | |
Evan Cheng | a461c4d | 2007-11-05 17:41:38 +0000 | [diff] [blame] | 113 | /// JoinedCopies - Keep track of copies eliminated due to coalescing. |
| 114 | /// |
| 115 | SmallPtrSet<MachineInstr*, 32> JoinedCopies; |
| 116 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 117 | public: |
| 118 | static char ID; // Pass identifcation, replacement for typeid |
Dan Gohman | 81975f6 | 2007-08-27 14:50:10 +0000 | [diff] [blame] | 119 | SimpleRegisterCoalescing() : MachineFunctionPass((intptr_t)&ID) {} |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 120 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 121 | struct InstrSlots { |
| 122 | enum { |
| 123 | LOAD = 0, |
| 124 | USE = 1, |
| 125 | DEF = 2, |
| 126 | STORE = 3, |
| 127 | NUM = 4 |
| 128 | }; |
| 129 | }; |
| 130 | |
| 131 | virtual void getAnalysisUsage(AnalysisUsage &AU) const; |
| 132 | virtual void releaseMemory(); |
| 133 | |
| 134 | /// runOnMachineFunction - pass entry point |
| 135 | virtual bool runOnMachineFunction(MachineFunction&); |
| 136 | |
David Greene | 2c17c4d | 2007-09-06 16:18:45 +0000 | [diff] [blame] | 137 | bool coalesceFunction(MachineFunction &mf, RegallocQuery &) { |
| 138 | // This runs as an independent pass, so don't do anything. |
Evan Cheng | 8fc9a10 | 2007-11-06 08:52:21 +0000 | [diff] [blame] | 139 | return false; |
David Greene | 2c17c4d | 2007-09-06 16:18:45 +0000 | [diff] [blame] | 140 | }; |
| 141 | |
Evan Cheng | 8fc9a10 | 2007-11-06 08:52:21 +0000 | [diff] [blame] | 142 | /// getRepIntervalSize - Called from join priority queue sorting function. |
| 143 | /// It returns the size of the interval that represent the given register. |
| 144 | unsigned getRepIntervalSize(unsigned Reg) { |
| 145 | Reg = rep(Reg); |
| 146 | if (!li_->hasInterval(Reg)) |
| 147 | return 0; |
| 148 | return li_->getInterval(Reg).getSize(); |
| 149 | } |
| 150 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 151 | /// print - Implement the dump method. |
| 152 | virtual void print(std::ostream &O, const Module* = 0) const; |
| 153 | void print(std::ostream *O, const Module* M = 0) const { |
| 154 | if (O) print(*O, M); |
| 155 | } |
| 156 | |
Evan Cheng | 8fc9a10 | 2007-11-06 08:52:21 +0000 | [diff] [blame] | 157 | private: |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 158 | /// joinIntervals - join compatible live intervals |
| 159 | void joinIntervals(); |
| 160 | |
Gabor Greif | b0954b1 | 2007-07-09 12:20:30 +0000 | [diff] [blame] | 161 | /// CopyCoalesceInMBB - Coalesce copies in the specified MBB, putting |
Gabor Greif | e510b3a | 2007-07-09 12:00:59 +0000 | [diff] [blame] | 162 | /// copies that cannot yet be coalesced into the "TryAgain" list. |
| 163 | void CopyCoalesceInMBB(MachineBasicBlock *MBB, |
Evan Cheng | 8b0b874 | 2007-10-16 08:04:24 +0000 | [diff] [blame] | 164 | std::vector<CopyRec> &TryAgain); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 165 | |
| 166 | /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, |
| 167 | /// which are the src/dst of the copy instruction CopyMI. This returns true |
Evan Cheng | 0547bab | 2007-11-01 06:22:48 +0000 | [diff] [blame] | 168 | /// if the copy was successfully coalesced away. If it is not currently |
| 169 | /// possible to coalesce this interval, but it may be possible if other |
| 170 | /// things get coalesced, then it returns true by reference in 'Again'. |
Evan Cheng | 8fc9a10 | 2007-11-06 08:52:21 +0000 | [diff] [blame] | 171 | bool JoinCopy(CopyRec TheCopy, bool &Again); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 172 | |
| 173 | /// JoinIntervals - Attempt to join these two intervals. On failure, this |
| 174 | /// returns false. Otherwise, if one of the intervals being joined is a |
| 175 | /// physreg, this method always canonicalizes DestInt to be it. The output |
| 176 | /// "SrcInt" will not have been modified, so we can use this information |
| 177 | /// below to update aliases. |
Evan Cheng | 1a66f0a | 2007-08-28 08:28:51 +0000 | [diff] [blame] | 178 | bool JoinIntervals(LiveInterval &LHS, LiveInterval &RHS, bool &Swapped); |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 179 | |
| 180 | /// SimpleJoin - Attempt to join the specified interval into this one. The |
| 181 | /// caller of this method must guarantee that the RHS only contains a single |
| 182 | /// value number and that the RHS is not defined by a copy from this |
| 183 | /// interval. This returns false if the intervals are not joinable, or it |
| 184 | /// joins them and returns true. |
| 185 | bool SimpleJoin(LiveInterval &LHS, LiveInterval &RHS); |
| 186 | |
| 187 | /// Return true if the two specified registers belong to different |
| 188 | /// register classes. The registers may be either phys or virt regs. |
| 189 | bool differingRegisterClasses(unsigned RegA, unsigned RegB) const; |
| 190 | |
| 191 | |
| 192 | bool AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB, |
| 193 | MachineInstr *CopyMI); |
| 194 | |
Evan Cheng | 4ae31a5 | 2007-10-18 07:49:59 +0000 | [diff] [blame] | 195 | /// AddSubRegIdxPairs - Recursively mark all the registers represented by the |
| 196 | /// specified register as sub-registers. The recursion level is expected to be |
| 197 | /// shallow. |
| 198 | void AddSubRegIdxPairs(unsigned Reg, unsigned SubIdx); |
| 199 | |
Evan Cheng | 8fc9a10 | 2007-11-06 08:52:21 +0000 | [diff] [blame] | 200 | /// isBackEdgeCopy - Returns true if CopyMI is a back edge copy. |
| 201 | /// |
| 202 | bool isBackEdgeCopy(MachineInstr *CopyMI, unsigned DstReg); |
| 203 | |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 204 | /// lastRegisterUse - Returns the last use of the specific register between |
| 205 | /// cycles Start and End. It also returns the use operand by reference. It |
| 206 | /// returns NULL if there are no uses. |
Evan Cheng | 4ae31a5 | 2007-10-18 07:49:59 +0000 | [diff] [blame] | 207 | MachineInstr *lastRegisterUse(unsigned Start, unsigned End, unsigned Reg, |
David Greene | 2513330 | 2007-06-08 17:18:56 +0000 | [diff] [blame] | 208 | MachineOperand *&MOU); |
| 209 | |
| 210 | /// findDefOperand - Returns the MachineOperand that is a def of the specific |
| 211 | /// register. It returns NULL if the def is not found. |
| 212 | MachineOperand *findDefOperand(MachineInstr *MI, unsigned Reg); |
| 213 | |
| 214 | /// unsetRegisterKill - Unset IsKill property of all uses of the specific |
| 215 | /// register of the specific instruction. |
| 216 | void unsetRegisterKill(MachineInstr *MI, unsigned Reg); |
| 217 | |
| 218 | /// unsetRegisterKills - Unset IsKill property of all uses of specific register |
| 219 | /// between cycles Start and End. |
| 220 | void unsetRegisterKills(unsigned Start, unsigned End, unsigned Reg); |
| 221 | |
| 222 | /// hasRegisterDef - True if the instruction defines the specific register. |
| 223 | /// |
| 224 | bool hasRegisterDef(MachineInstr *MI, unsigned Reg); |
| 225 | |
| 226 | /// rep - returns the representative of this register |
| 227 | unsigned rep(unsigned Reg) { |
| 228 | unsigned Rep = r2rMap_[Reg]; |
| 229 | if (Rep) |
| 230 | return r2rMap_[Reg] = rep(Rep); |
| 231 | return Reg; |
| 232 | } |
| 233 | |
| 234 | void printRegName(unsigned reg) const; |
| 235 | }; |
| 236 | |
| 237 | } // End llvm namespace |
| 238 | |
| 239 | #endif |