]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
1 | //===- MachineSSAUpdater.cpp - Unstructured SSA Update Tool ---------------===// |
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 implements the MachineSSAUpdater class. It's based on SSAUpdater | |
11 | // class in lib/Transforms/Utils. | |
12 | // | |
13 | //===----------------------------------------------------------------------===// | |
14 | ||
15 | #include "llvm/CodeGen/MachineSSAUpdater.h" | |
970d7e83 LB |
16 | #include "llvm/ADT/DenseMap.h" |
17 | #include "llvm/ADT/SmallVector.h" | |
223e47cc LB |
18 | #include "llvm/CodeGen/MachineInstr.h" |
19 | #include "llvm/CodeGen/MachineInstrBuilder.h" | |
20 | #include "llvm/CodeGen/MachineRegisterInfo.h" | |
223e47cc LB |
21 | #include "llvm/Support/AlignOf.h" |
22 | #include "llvm/Support/Allocator.h" | |
23 | #include "llvm/Support/Debug.h" | |
24 | #include "llvm/Support/ErrorHandling.h" | |
25 | #include "llvm/Support/raw_ostream.h" | |
970d7e83 | 26 | #include "llvm/Target/TargetInstrInfo.h" |
970d7e83 | 27 | #include "llvm/Target/TargetRegisterInfo.h" |
1a4d82fc | 28 | #include "llvm/Target/TargetSubtargetInfo.h" |
223e47cc LB |
29 | #include "llvm/Transforms/Utils/SSAUpdaterImpl.h" |
30 | using namespace llvm; | |
31 | ||
1a4d82fc JJ |
32 | #define DEBUG_TYPE "machine-ssaupdater" |
33 | ||
223e47cc LB |
34 | typedef DenseMap<MachineBasicBlock*, unsigned> AvailableValsTy; |
35 | static AvailableValsTy &getAvailableVals(void *AV) { | |
36 | return *static_cast<AvailableValsTy*>(AV); | |
37 | } | |
38 | ||
39 | MachineSSAUpdater::MachineSSAUpdater(MachineFunction &MF, | |
40 | SmallVectorImpl<MachineInstr*> *NewPHI) | |
1a4d82fc JJ |
41 | : AV(nullptr), InsertedPHIs(NewPHI) { |
42 | TII = MF.getSubtarget().getInstrInfo(); | |
223e47cc LB |
43 | MRI = &MF.getRegInfo(); |
44 | } | |
45 | ||
46 | MachineSSAUpdater::~MachineSSAUpdater() { | |
47 | delete static_cast<AvailableValsTy*>(AV); | |
48 | } | |
49 | ||
50 | /// Initialize - Reset this object to get ready for a new set of SSA | |
51 | /// updates. ProtoValue is the value used to name PHI nodes. | |
52 | void MachineSSAUpdater::Initialize(unsigned V) { | |
1a4d82fc | 53 | if (!AV) |
223e47cc LB |
54 | AV = new AvailableValsTy(); |
55 | else | |
56 | getAvailableVals(AV).clear(); | |
57 | ||
58 | VR = V; | |
59 | VRC = MRI->getRegClass(VR); | |
60 | } | |
61 | ||
62 | /// HasValueForBlock - Return true if the MachineSSAUpdater already has a value for | |
63 | /// the specified block. | |
64 | bool MachineSSAUpdater::HasValueForBlock(MachineBasicBlock *BB) const { | |
65 | return getAvailableVals(AV).count(BB); | |
66 | } | |
67 | ||
68 | /// AddAvailableValue - Indicate that a rewritten value is available in the | |
69 | /// specified block with the specified value. | |
70 | void MachineSSAUpdater::AddAvailableValue(MachineBasicBlock *BB, unsigned V) { | |
71 | getAvailableVals(AV)[BB] = V; | |
72 | } | |
73 | ||
74 | /// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is | |
75 | /// live at the end of the specified block. | |
76 | unsigned MachineSSAUpdater::GetValueAtEndOfBlock(MachineBasicBlock *BB) { | |
77 | return GetValueAtEndOfBlockInternal(BB); | |
78 | } | |
79 | ||
80 | static | |
81 | unsigned LookForIdenticalPHI(MachineBasicBlock *BB, | |
1a4d82fc | 82 | SmallVectorImpl<std::pair<MachineBasicBlock*, unsigned> > &PredValues) { |
223e47cc LB |
83 | if (BB->empty()) |
84 | return 0; | |
85 | ||
86 | MachineBasicBlock::iterator I = BB->begin(); | |
87 | if (!I->isPHI()) | |
88 | return 0; | |
89 | ||
90 | AvailableValsTy AVals; | |
91 | for (unsigned i = 0, e = PredValues.size(); i != e; ++i) | |
92 | AVals[PredValues[i].first] = PredValues[i].second; | |
93 | while (I != BB->end() && I->isPHI()) { | |
94 | bool Same = true; | |
95 | for (unsigned i = 1, e = I->getNumOperands(); i != e; i += 2) { | |
96 | unsigned SrcReg = I->getOperand(i).getReg(); | |
97 | MachineBasicBlock *SrcBB = I->getOperand(i+1).getMBB(); | |
98 | if (AVals[SrcBB] != SrcReg) { | |
99 | Same = false; | |
100 | break; | |
101 | } | |
102 | } | |
103 | if (Same) | |
104 | return I->getOperand(0).getReg(); | |
105 | ++I; | |
106 | } | |
107 | return 0; | |
108 | } | |
109 | ||
110 | /// InsertNewDef - Insert an empty PHI or IMPLICIT_DEF instruction which define | |
111 | /// a value of the given register class at the start of the specified basic | |
112 | /// block. It returns the virtual register defined by the instruction. | |
113 | static | |
970d7e83 | 114 | MachineInstrBuilder InsertNewDef(unsigned Opcode, |
223e47cc LB |
115 | MachineBasicBlock *BB, MachineBasicBlock::iterator I, |
116 | const TargetRegisterClass *RC, | |
117 | MachineRegisterInfo *MRI, | |
118 | const TargetInstrInfo *TII) { | |
119 | unsigned NewVR = MRI->createVirtualRegister(RC); | |
120 | return BuildMI(*BB, I, DebugLoc(), TII->get(Opcode), NewVR); | |
121 | } | |
122 | ||
123 | /// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that | |
124 | /// is live in the middle of the specified block. | |
125 | /// | |
126 | /// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one | |
127 | /// important case: if there is a definition of the rewritten value after the | |
128 | /// 'use' in BB. Consider code like this: | |
129 | /// | |
130 | /// X1 = ... | |
131 | /// SomeBB: | |
132 | /// use(X) | |
133 | /// X2 = ... | |
134 | /// br Cond, SomeBB, OutBB | |
135 | /// | |
136 | /// In this case, there are two values (X1 and X2) added to the AvailableVals | |
137 | /// set by the client of the rewriter, and those values are both live out of | |
138 | /// their respective blocks. However, the use of X happens in the *middle* of | |
139 | /// a block. Because of this, we need to insert a new PHI node in SomeBB to | |
140 | /// merge the appropriate values, and this value isn't live out of the block. | |
141 | /// | |
142 | unsigned MachineSSAUpdater::GetValueInMiddleOfBlock(MachineBasicBlock *BB) { | |
143 | // If there is no definition of the renamed variable in this block, just use | |
144 | // GetValueAtEndOfBlock to do our work. | |
145 | if (!HasValueForBlock(BB)) | |
146 | return GetValueAtEndOfBlockInternal(BB); | |
147 | ||
148 | // If there are no predecessors, just return undef. | |
149 | if (BB->pred_empty()) { | |
150 | // Insert an implicit_def to represent an undef value. | |
151 | MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF, | |
152 | BB, BB->getFirstTerminator(), | |
153 | VRC, MRI, TII); | |
154 | return NewDef->getOperand(0).getReg(); | |
155 | } | |
156 | ||
157 | // Otherwise, we have the hard case. Get the live-in values for each | |
158 | // predecessor. | |
159 | SmallVector<std::pair<MachineBasicBlock*, unsigned>, 8> PredValues; | |
160 | unsigned SingularValue = 0; | |
161 | ||
162 | bool isFirstPred = true; | |
163 | for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(), | |
164 | E = BB->pred_end(); PI != E; ++PI) { | |
165 | MachineBasicBlock *PredBB = *PI; | |
166 | unsigned PredVal = GetValueAtEndOfBlockInternal(PredBB); | |
167 | PredValues.push_back(std::make_pair(PredBB, PredVal)); | |
168 | ||
169 | // Compute SingularValue. | |
170 | if (isFirstPred) { | |
171 | SingularValue = PredVal; | |
172 | isFirstPred = false; | |
173 | } else if (PredVal != SingularValue) | |
174 | SingularValue = 0; | |
175 | } | |
176 | ||
177 | // Otherwise, if all the merged values are the same, just use it. | |
178 | if (SingularValue != 0) | |
179 | return SingularValue; | |
180 | ||
181 | // If an identical PHI is already in BB, just reuse it. | |
182 | unsigned DupPHI = LookForIdenticalPHI(BB, PredValues); | |
183 | if (DupPHI) | |
184 | return DupPHI; | |
185 | ||
186 | // Otherwise, we do need a PHI: insert one now. | |
187 | MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->begin(); | |
970d7e83 LB |
188 | MachineInstrBuilder InsertedPHI = InsertNewDef(TargetOpcode::PHI, BB, |
189 | Loc, VRC, MRI, TII); | |
223e47cc LB |
190 | |
191 | // Fill in all the predecessors of the PHI. | |
223e47cc | 192 | for (unsigned i = 0, e = PredValues.size(); i != e; ++i) |
970d7e83 | 193 | InsertedPHI.addReg(PredValues[i].second).addMBB(PredValues[i].first); |
223e47cc LB |
194 | |
195 | // See if the PHI node can be merged to a single value. This can happen in | |
196 | // loop cases when we get a PHI of itself and one other value. | |
197 | if (unsigned ConstVal = InsertedPHI->isConstantValuePHI()) { | |
198 | InsertedPHI->eraseFromParent(); | |
199 | return ConstVal; | |
200 | } | |
201 | ||
202 | // If the client wants to know about all new instructions, tell it. | |
203 | if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI); | |
204 | ||
205 | DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n"); | |
206 | return InsertedPHI->getOperand(0).getReg(); | |
207 | } | |
208 | ||
209 | static | |
210 | MachineBasicBlock *findCorrespondingPred(const MachineInstr *MI, | |
211 | MachineOperand *U) { | |
212 | for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) { | |
213 | if (&MI->getOperand(i) == U) | |
214 | return MI->getOperand(i+1).getMBB(); | |
215 | } | |
216 | ||
217 | llvm_unreachable("MachineOperand::getParent() failure?"); | |
218 | } | |
219 | ||
220 | /// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes, | |
221 | /// which use their value in the corresponding predecessor. | |
222 | void MachineSSAUpdater::RewriteUse(MachineOperand &U) { | |
223 | MachineInstr *UseMI = U.getParent(); | |
224 | unsigned NewVR = 0; | |
225 | if (UseMI->isPHI()) { | |
226 | MachineBasicBlock *SourceBB = findCorrespondingPred(UseMI, &U); | |
227 | NewVR = GetValueAtEndOfBlockInternal(SourceBB); | |
228 | } else { | |
229 | NewVR = GetValueInMiddleOfBlock(UseMI->getParent()); | |
230 | } | |
231 | ||
232 | U.setReg(NewVR); | |
233 | } | |
234 | ||
223e47cc LB |
235 | /// SSAUpdaterTraits<MachineSSAUpdater> - Traits for the SSAUpdaterImpl |
236 | /// template, specialized for MachineSSAUpdater. | |
237 | namespace llvm { | |
238 | template<> | |
239 | class SSAUpdaterTraits<MachineSSAUpdater> { | |
240 | public: | |
241 | typedef MachineBasicBlock BlkT; | |
242 | typedef unsigned ValT; | |
243 | typedef MachineInstr PhiT; | |
244 | ||
245 | typedef MachineBasicBlock::succ_iterator BlkSucc_iterator; | |
246 | static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return BB->succ_begin(); } | |
247 | static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return BB->succ_end(); } | |
248 | ||
249 | /// Iterator for PHI operands. | |
250 | class PHI_iterator { | |
251 | private: | |
252 | MachineInstr *PHI; | |
253 | unsigned idx; | |
254 | ||
255 | public: | |
256 | explicit PHI_iterator(MachineInstr *P) // begin iterator | |
257 | : PHI(P), idx(1) {} | |
258 | PHI_iterator(MachineInstr *P, bool) // end iterator | |
259 | : PHI(P), idx(PHI->getNumOperands()) {} | |
260 | ||
261 | PHI_iterator &operator++() { idx += 2; return *this; } | |
262 | bool operator==(const PHI_iterator& x) const { return idx == x.idx; } | |
263 | bool operator!=(const PHI_iterator& x) const { return !operator==(x); } | |
264 | unsigned getIncomingValue() { return PHI->getOperand(idx).getReg(); } | |
265 | MachineBasicBlock *getIncomingBlock() { | |
266 | return PHI->getOperand(idx+1).getMBB(); | |
267 | } | |
268 | }; | |
269 | static inline PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); } | |
270 | static inline PHI_iterator PHI_end(PhiT *PHI) { | |
271 | return PHI_iterator(PHI, true); | |
272 | } | |
273 | ||
274 | /// FindPredecessorBlocks - Put the predecessors of BB into the Preds | |
275 | /// vector. | |
276 | static void FindPredecessorBlocks(MachineBasicBlock *BB, | |
277 | SmallVectorImpl<MachineBasicBlock*> *Preds){ | |
278 | for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(), | |
279 | E = BB->pred_end(); PI != E; ++PI) | |
280 | Preds->push_back(*PI); | |
281 | } | |
282 | ||
283 | /// GetUndefVal - Create an IMPLICIT_DEF instruction with a new register. | |
284 | /// Add it into the specified block and return the register. | |
285 | static unsigned GetUndefVal(MachineBasicBlock *BB, | |
286 | MachineSSAUpdater *Updater) { | |
287 | // Insert an implicit_def to represent an undef value. | |
288 | MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF, | |
289 | BB, BB->getFirstTerminator(), | |
290 | Updater->VRC, Updater->MRI, | |
291 | Updater->TII); | |
292 | return NewDef->getOperand(0).getReg(); | |
293 | } | |
294 | ||
295 | /// CreateEmptyPHI - Create a PHI instruction that defines a new register. | |
296 | /// Add it into the specified block and return the register. | |
297 | static unsigned CreateEmptyPHI(MachineBasicBlock *BB, unsigned NumPreds, | |
298 | MachineSSAUpdater *Updater) { | |
299 | MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->begin(); | |
300 | MachineInstr *PHI = InsertNewDef(TargetOpcode::PHI, BB, Loc, | |
301 | Updater->VRC, Updater->MRI, | |
302 | Updater->TII); | |
303 | return PHI->getOperand(0).getReg(); | |
304 | } | |
305 | ||
306 | /// AddPHIOperand - Add the specified value as an operand of the PHI for | |
307 | /// the specified predecessor block. | |
308 | static void AddPHIOperand(MachineInstr *PHI, unsigned Val, | |
309 | MachineBasicBlock *Pred) { | |
970d7e83 | 310 | MachineInstrBuilder(*Pred->getParent(), PHI).addReg(Val).addMBB(Pred); |
223e47cc LB |
311 | } |
312 | ||
313 | /// InstrIsPHI - Check if an instruction is a PHI. | |
314 | /// | |
315 | static MachineInstr *InstrIsPHI(MachineInstr *I) { | |
316 | if (I && I->isPHI()) | |
317 | return I; | |
1a4d82fc | 318 | return nullptr; |
223e47cc LB |
319 | } |
320 | ||
321 | /// ValueIsPHI - Check if the instruction that defines the specified register | |
322 | /// is a PHI instruction. | |
323 | static MachineInstr *ValueIsPHI(unsigned Val, MachineSSAUpdater *Updater) { | |
324 | return InstrIsPHI(Updater->MRI->getVRegDef(Val)); | |
325 | } | |
326 | ||
327 | /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source | |
328 | /// operands, i.e., it was just added. | |
329 | static MachineInstr *ValueIsNewPHI(unsigned Val, MachineSSAUpdater *Updater) { | |
330 | MachineInstr *PHI = ValueIsPHI(Val, Updater); | |
331 | if (PHI && PHI->getNumOperands() <= 1) | |
332 | return PHI; | |
1a4d82fc | 333 | return nullptr; |
223e47cc LB |
334 | } |
335 | ||
336 | /// GetPHIValue - For the specified PHI instruction, return the register | |
337 | /// that it defines. | |
338 | static unsigned GetPHIValue(MachineInstr *PHI) { | |
339 | return PHI->getOperand(0).getReg(); | |
340 | } | |
341 | }; | |
342 | ||
343 | } // End llvm namespace | |
344 | ||
345 | /// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry | |
346 | /// for the specified BB and if so, return it. If not, construct SSA form by | |
347 | /// first calculating the required placement of PHIs and then inserting new | |
348 | /// PHIs where needed. | |
349 | unsigned MachineSSAUpdater::GetValueAtEndOfBlockInternal(MachineBasicBlock *BB){ | |
350 | AvailableValsTy &AvailableVals = getAvailableVals(AV); | |
351 | if (unsigned V = AvailableVals[BB]) | |
352 | return V; | |
353 | ||
354 | SSAUpdaterImpl<MachineSSAUpdater> Impl(this, &AvailableVals, InsertedPHIs); | |
355 | return Impl.GetValue(BB); | |
356 | } |