1 //===-- SimpleRegisterCoalescing.h - Register Coalescing --------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source 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"
28 class TargetInstrInfo;
31 class SimpleRegisterCoalescing : public MachineFunctionPass,
32 public RegisterCoalescer {
34 const TargetMachine* tm_;
35 const MRegisterInfo* mri_;
36 const TargetInstrInfo* tii_;
40 BitVector allocatableRegs_;
41 DenseMap<const TargetRegisterClass*, BitVector> allocatableRCRegs_;
43 /// r2rMap_ - Map from register to its representative register.
45 IndexedMap<unsigned> r2rMap_;
47 /// r2rRevMap_ - Reverse of r2rRevMap_, i.e. Map from register to all
48 /// the registers it represent.
49 IndexedMap<std::vector<unsigned> > r2rRevMap_;
51 /// JoinedLIs - Keep track which register intervals have been coalesced
52 /// with other intervals.
55 /// SubRegIdxes - Keep track of sub-register and indexes.
57 SmallVector<std::pair<unsigned, unsigned>, 32> SubRegIdxes;
59 /// JoinedCopies - Keep track of copies eliminated due to coalescing.
61 SmallPtrSet<MachineInstr*, 32> JoinedCopies;
64 static char ID; // Pass identifcation, replacement for typeid
65 SimpleRegisterCoalescing() : MachineFunctionPass((intptr_t)&ID) {}
69 unsigned SrcReg, DstReg;
71 CopyRec getCopyRec(MachineInstr *MI, unsigned SrcReg, unsigned DstReg) {
88 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
89 virtual void releaseMemory();
91 /// runOnMachineFunction - pass entry point
92 virtual bool runOnMachineFunction(MachineFunction&);
94 bool coalesceFunction(MachineFunction &mf, RegallocQuery &) {
95 // This runs as an independent pass, so don't do anything.
99 /// print - Implement the dump method.
100 virtual void print(std::ostream &O, const Module* = 0) const;
101 void print(std::ostream *O, const Module* M = 0) const {
106 /// joinIntervals - join compatible live intervals
107 void joinIntervals();
109 /// CopyCoalesceInMBB - Coalesce copies in the specified MBB, putting
110 /// copies that cannot yet be coalesced into the "TryAgain" list.
111 void CopyCoalesceInMBB(MachineBasicBlock *MBB,
112 std::vector<CopyRec> &TryAgain);
114 /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg,
115 /// which are the src/dst of the copy instruction CopyMI. This returns true
116 /// if the copy was successfully coalesced away. If it is not currently
117 /// possible to coalesce this interval, but it may be possible if other
118 /// things get coalesced, then it returns true by reference in 'Again'.
119 bool JoinCopy(MachineInstr *CopyMI, unsigned SrcReg, unsigned DstReg,
122 /// JoinIntervals - Attempt to join these two intervals. On failure, this
123 /// returns false. Otherwise, if one of the intervals being joined is a
124 /// physreg, this method always canonicalizes DestInt to be it. The output
125 /// "SrcInt" will not have been modified, so we can use this information
126 /// below to update aliases.
127 bool JoinIntervals(LiveInterval &LHS, LiveInterval &RHS, bool &Swapped);
129 /// SimpleJoin - Attempt to join the specified interval into this one. The
130 /// caller of this method must guarantee that the RHS only contains a single
131 /// value number and that the RHS is not defined by a copy from this
132 /// interval. This returns false if the intervals are not joinable, or it
133 /// joins them and returns true.
134 bool SimpleJoin(LiveInterval &LHS, LiveInterval &RHS);
136 /// Return true if the two specified registers belong to different
137 /// register classes. The registers may be either phys or virt regs.
138 bool differingRegisterClasses(unsigned RegA, unsigned RegB) const;
141 bool AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB,
142 MachineInstr *CopyMI);
144 /// AddSubRegIdxPairs - Recursively mark all the registers represented by the
145 /// specified register as sub-registers. The recursion level is expected to be
147 void AddSubRegIdxPairs(unsigned Reg, unsigned SubIdx);
149 /// lastRegisterUse - Returns the last use of the specific register between
150 /// cycles Start and End. It also returns the use operand by reference. It
151 /// returns NULL if there are no uses.
152 MachineInstr *lastRegisterUse(unsigned Start, unsigned End, unsigned Reg,
153 MachineOperand *&MOU);
155 /// findDefOperand - Returns the MachineOperand that is a def of the specific
156 /// register. It returns NULL if the def is not found.
157 MachineOperand *findDefOperand(MachineInstr *MI, unsigned Reg);
159 /// unsetRegisterKill - Unset IsKill property of all uses of the specific
160 /// register of the specific instruction.
161 void unsetRegisterKill(MachineInstr *MI, unsigned Reg);
163 /// unsetRegisterKills - Unset IsKill property of all uses of specific register
164 /// between cycles Start and End.
165 void unsetRegisterKills(unsigned Start, unsigned End, unsigned Reg);
167 /// hasRegisterDef - True if the instruction defines the specific register.
169 bool hasRegisterDef(MachineInstr *MI, unsigned Reg);
171 /// rep - returns the representative of this register
172 unsigned rep(unsigned Reg) {
173 unsigned Rep = r2rMap_[Reg];
175 return r2rMap_[Reg] = rep(Rep);
179 void printRegName(unsigned reg) const;
182 } // End llvm namespace