1 //===-- SimpleRegisterCoalescing.h - Register Coalescing --------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a simple register copy coalescing phase.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_CODEGEN_SIMPLE_REGISTER_COALESCING_H
15 #define LLVM_CODEGEN_SIMPLE_REGISTER_COALESCING_H
17 #include "llvm/CodeGen/MachineFunctionPass.h"
18 #include "llvm/CodeGen/LiveInterval.h"
19 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
20 #include "llvm/CodeGen/RegisterCoalescer.h"
21 #include "llvm/ADT/BitVector.h"
22 #include "llvm/ADT/IndexedMap.h"
26 class SimpleRegisterCoalescing;
29 class TargetInstrInfo;
31 class MachineLoopInfo;
33 /// CopyRec - Representation for copy instructions in coalescer queue.
37 unsigned SrcReg, DstReg;
40 CopyRec(MachineInstr *mi, unsigned src, unsigned dst, unsigned depth,
42 : MI(mi), SrcReg(src), DstReg(dst), LoopDepth(depth), isBackEdge(be) {};
45 template<class SF> class JoinPriorityQueue;
47 /// CopyRecSort - Sorting function for coalescer queue.
49 struct CopyRecSort : public std::binary_function<CopyRec,CopyRec,bool> {
50 JoinPriorityQueue<CopyRecSort> *JPQ;
51 explicit CopyRecSort(JoinPriorityQueue<CopyRecSort> *jpq) : JPQ(jpq) {}
52 CopyRecSort(const CopyRecSort &RHS) : JPQ(RHS.JPQ) {}
53 bool operator()(CopyRec left, CopyRec right) const;
56 /// JoinQueue - A priority queue of copy instructions the coalescer is
59 class JoinPriorityQueue {
60 SimpleRegisterCoalescing *Rc;
61 std::priority_queue<CopyRec, std::vector<CopyRec>, SF> Queue;
64 explicit JoinPriorityQueue(SimpleRegisterCoalescing *rc)
65 : Rc(rc), Queue(SF(this)) {}
67 bool empty() const { return Queue.empty(); }
68 void push(CopyRec R) { Queue.push(R); }
70 if (empty()) return CopyRec(0, 0, 0, 0, false);
71 CopyRec R = Queue.top();
76 // Callbacks to SimpleRegisterCoalescing.
77 unsigned getRepIntervalSize(unsigned Reg);
80 class SimpleRegisterCoalescing : public MachineFunctionPass,
81 public RegisterCoalescer {
83 const TargetMachine* tm_;
84 const MRegisterInfo* mri_;
85 const TargetInstrInfo* tii_;
88 const MachineLoopInfo* loopInfo;
90 BitVector allocatableRegs_;
91 DenseMap<const TargetRegisterClass*, BitVector> allocatableRCRegs_;
93 /// r2rMap_ - Map from register to its representative register.
95 IndexedMap<unsigned> r2rMap_;
97 /// r2rRevMap_ - Reverse of r2rRevMap_, i.e. Map from register to all
98 /// the registers it represent.
99 IndexedMap<std::vector<unsigned> > r2rRevMap_;
101 /// JoinQueue - A priority queue of copy instructions the coalescer is
102 /// going to process.
103 JoinPriorityQueue<CopyRecSort> *JoinQueue;
105 /// JoinedLIs - Keep track which register intervals have been coalesced
106 /// with other intervals.
109 /// SubRegIdxes - Keep track of sub-register and indexes.
111 SmallVector<std::pair<unsigned, unsigned>, 32> SubRegIdxes;
113 /// JoinedCopies - Keep track of copies eliminated due to coalescing.
115 SmallPtrSet<MachineInstr*, 32> JoinedCopies;
118 static char ID; // Pass identifcation, replacement for typeid
119 SimpleRegisterCoalescing() : MachineFunctionPass((intptr_t)&ID) {}
131 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
132 virtual void releaseMemory();
134 /// runOnMachineFunction - pass entry point
135 virtual bool runOnMachineFunction(MachineFunction&);
137 bool coalesceFunction(MachineFunction &mf, RegallocQuery &) {
138 // This runs as an independent pass, so don't do anything.
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) {
146 if (!li_->hasInterval(Reg))
148 return li_->getInterval(Reg).getSize();
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 {
158 /// joinIntervals - join compatible live intervals
159 void joinIntervals();
161 /// CopyCoalesceInMBB - Coalesce copies in the specified MBB, putting
162 /// copies that cannot yet be coalesced into the "TryAgain" list.
163 void CopyCoalesceInMBB(MachineBasicBlock *MBB,
164 std::vector<CopyRec> &TryAgain);
166 /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg,
167 /// which are the src/dst of the copy instruction CopyMI. This returns true
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'.
171 bool JoinCopy(CopyRec TheCopy, bool &Again);
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.
178 bool JoinIntervals(LiveInterval &LHS, LiveInterval &RHS, bool &Swapped);
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);
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;
192 bool AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB,
193 MachineInstr *CopyMI);
195 /// AddSubRegIdxPairs - Recursively mark all the registers represented by the
196 /// specified register as sub-registers. The recursion level is expected to be
198 void AddSubRegIdxPairs(unsigned Reg, unsigned SubIdx);
200 /// isBackEdgeCopy - Returns true if CopyMI is a back edge copy.
202 bool isBackEdgeCopy(MachineInstr *CopyMI, unsigned DstReg);
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.
207 MachineInstr *lastRegisterUse(unsigned Start, unsigned End, unsigned Reg,
208 MachineOperand *&MOU);
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);
214 /// unsetRegisterKill - Unset IsKill property of all uses of the specific
215 /// register of the specific instruction.
216 void unsetRegisterKill(MachineInstr *MI, unsigned Reg);
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);
222 /// hasRegisterDef - True if the instruction defines the specific register.
224 bool hasRegisterDef(MachineInstr *MI, unsigned Reg);
226 /// rep - returns the representative of this register
227 unsigned rep(unsigned Reg) {
228 unsigned Rep = r2rMap_[Reg];
230 return r2rMap_[Reg] = rep(Rep);
234 void printRegName(unsigned reg) const;
237 } // End llvm namespace