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"
16#include "llvm/CodeGen/MachineInstr.h"
17#include "llvm/CodeGen/MachineInstrBuilder.h"
18#include "llvm/CodeGen/MachineRegisterInfo.h"
19#include "llvm/Target/TargetInstrInfo.h"
20#include "llvm/Target/TargetMachine.h"
21#include "llvm/Target/TargetRegisterInfo.h"
22#include "llvm/ADT/DenseMap.h"
23#include "llvm/ADT/SmallVector.h"
24#include "llvm/Support/Debug.h"
25#include "llvm/Support/ErrorHandling.h"
26#include "llvm/Support/raw_ostream.h"
27using namespace llvm;
28
29typedef DenseMap<MachineBasicBlock*, unsigned> AvailableValsTy;
30typedef std::vector<std::pair<MachineBasicBlock*, unsigned> >
31 IncomingPredInfoTy;
32
33static AvailableValsTy &getAvailableVals(void *AV) {
34 return *static_cast<AvailableValsTy*>(AV);
35}
36
37static IncomingPredInfoTy &getIncomingPredInfo(void *IPI) {
38 return *static_cast<IncomingPredInfoTy*>(IPI);
39}
40
41
42MachineSSAUpdater::MachineSSAUpdater(MachineFunction &MF,
43 SmallVectorImpl<MachineInstr*> *NewPHI)
44 : AV(0), IPI(0), InsertedPHIs(NewPHI) {
45 TII = MF.getTarget().getInstrInfo();
46 MRI = &MF.getRegInfo();
47}
48
49MachineSSAUpdater::~MachineSSAUpdater() {
50 delete &getAvailableVals(AV);
51 delete &getIncomingPredInfo(IPI);
52}
53
54/// Initialize - Reset this object to get ready for a new set of SSA
55/// updates. ProtoValue is the value used to name PHI nodes.
56void MachineSSAUpdater::Initialize(unsigned V) {
57 if (AV == 0)
58 AV = new AvailableValsTy();
59 else
60 getAvailableVals(AV).clear();
61
62 if (IPI == 0)
63 IPI = new IncomingPredInfoTy();
64 else
65 getIncomingPredInfo(IPI).clear();
66
67 VR = V;
68 VRC = MRI->getRegClass(VR);
69}
70
71/// HasValueForBlock - Return true if the MachineSSAUpdater already has a value for
72/// the specified block.
73bool MachineSSAUpdater::HasValueForBlock(MachineBasicBlock *BB) const {
74 return getAvailableVals(AV).count(BB);
75}
76
77/// AddAvailableValue - Indicate that a rewritten value is available in the
78/// specified block with the specified value.
79void MachineSSAUpdater::AddAvailableValue(MachineBasicBlock *BB, unsigned V) {
80 getAvailableVals(AV)[BB] = V;
81}
82
83/// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is
84/// live at the end of the specified block.
85unsigned MachineSSAUpdater::GetValueAtEndOfBlock(MachineBasicBlock *BB) {
86 return GetValueAtEndOfBlockInternal(BB);
87}
88
89static
90unsigned LookForIdenticalPHI(MachineBasicBlock *BB,
91 SmallVector<std::pair<MachineBasicBlock*, unsigned>, 8> &PredValues) {
92 if (BB->empty())
93 return 0;
94
95 MachineBasicBlock::iterator I = BB->front();
96 if (!I->isPHI())
97 return 0;
98
99 AvailableValsTy AVals;
100 for (unsigned i = 0, e = PredValues.size(); i != e; ++i)
101 AVals[PredValues[i].first] = PredValues[i].second;
102 while (I != BB->end() && I->isPHI()) {
103 bool Same = true;
104 for (unsigned i = 1, e = I->getNumOperands(); i != e; i += 2) {
105 unsigned SrcReg = I->getOperand(i).getReg();
106 MachineBasicBlock *SrcBB = I->getOperand(i+1).getMBB();
107 if (AVals[SrcBB] != SrcReg) {
108 Same = false;
109 break;
110 }
111 }
112 if (Same)
113 return I->getOperand(0).getReg();
114 ++I;
115 }
116 return 0;
117}
118
119/// InsertNewDef - Insert an empty PHI or IMPLICIT_DEF instruction which define
120/// a value of the given register class at the start of the specified basic
121/// block. It returns the virtual register defined by the instruction.
122static
123MachineInstr *InsertNewDef(unsigned Opcode,
124 MachineBasicBlock *BB, MachineBasicBlock::iterator I,
125 const TargetRegisterClass *RC,
126 MachineRegisterInfo *MRI, const TargetInstrInfo *TII) {
127 unsigned NewVR = MRI->createVirtualRegister(RC);
| 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"
16#include "llvm/CodeGen/MachineInstr.h"
17#include "llvm/CodeGen/MachineInstrBuilder.h"
18#include "llvm/CodeGen/MachineRegisterInfo.h"
19#include "llvm/Target/TargetInstrInfo.h"
20#include "llvm/Target/TargetMachine.h"
21#include "llvm/Target/TargetRegisterInfo.h"
22#include "llvm/ADT/DenseMap.h"
23#include "llvm/ADT/SmallVector.h"
24#include "llvm/Support/Debug.h"
25#include "llvm/Support/ErrorHandling.h"
26#include "llvm/Support/raw_ostream.h"
27using namespace llvm;
28
29typedef DenseMap<MachineBasicBlock*, unsigned> AvailableValsTy;
30typedef std::vector<std::pair<MachineBasicBlock*, unsigned> >
31 IncomingPredInfoTy;
32
33static AvailableValsTy &getAvailableVals(void *AV) {
34 return *static_cast<AvailableValsTy*>(AV);
35}
36
37static IncomingPredInfoTy &getIncomingPredInfo(void *IPI) {
38 return *static_cast<IncomingPredInfoTy*>(IPI);
39}
40
41
42MachineSSAUpdater::MachineSSAUpdater(MachineFunction &MF,
43 SmallVectorImpl<MachineInstr*> *NewPHI)
44 : AV(0), IPI(0), InsertedPHIs(NewPHI) {
45 TII = MF.getTarget().getInstrInfo();
46 MRI = &MF.getRegInfo();
47}
48
49MachineSSAUpdater::~MachineSSAUpdater() {
50 delete &getAvailableVals(AV);
51 delete &getIncomingPredInfo(IPI);
52}
53
54/// Initialize - Reset this object to get ready for a new set of SSA
55/// updates. ProtoValue is the value used to name PHI nodes.
56void MachineSSAUpdater::Initialize(unsigned V) {
57 if (AV == 0)
58 AV = new AvailableValsTy();
59 else
60 getAvailableVals(AV).clear();
61
62 if (IPI == 0)
63 IPI = new IncomingPredInfoTy();
64 else
65 getIncomingPredInfo(IPI).clear();
66
67 VR = V;
68 VRC = MRI->getRegClass(VR);
69}
70
71/// HasValueForBlock - Return true if the MachineSSAUpdater already has a value for
72/// the specified block.
73bool MachineSSAUpdater::HasValueForBlock(MachineBasicBlock *BB) const {
74 return getAvailableVals(AV).count(BB);
75}
76
77/// AddAvailableValue - Indicate that a rewritten value is available in the
78/// specified block with the specified value.
79void MachineSSAUpdater::AddAvailableValue(MachineBasicBlock *BB, unsigned V) {
80 getAvailableVals(AV)[BB] = V;
81}
82
83/// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is
84/// live at the end of the specified block.
85unsigned MachineSSAUpdater::GetValueAtEndOfBlock(MachineBasicBlock *BB) {
86 return GetValueAtEndOfBlockInternal(BB);
87}
88
89static
90unsigned LookForIdenticalPHI(MachineBasicBlock *BB,
91 SmallVector<std::pair<MachineBasicBlock*, unsigned>, 8> &PredValues) {
92 if (BB->empty())
93 return 0;
94
95 MachineBasicBlock::iterator I = BB->front();
96 if (!I->isPHI())
97 return 0;
98
99 AvailableValsTy AVals;
100 for (unsigned i = 0, e = PredValues.size(); i != e; ++i)
101 AVals[PredValues[i].first] = PredValues[i].second;
102 while (I != BB->end() && I->isPHI()) {
103 bool Same = true;
104 for (unsigned i = 1, e = I->getNumOperands(); i != e; i += 2) {
105 unsigned SrcReg = I->getOperand(i).getReg();
106 MachineBasicBlock *SrcBB = I->getOperand(i+1).getMBB();
107 if (AVals[SrcBB] != SrcReg) {
108 Same = false;
109 break;
110 }
111 }
112 if (Same)
113 return I->getOperand(0).getReg();
114 ++I;
115 }
116 return 0;
117}
118
119/// InsertNewDef - Insert an empty PHI or IMPLICIT_DEF instruction which define
120/// a value of the given register class at the start of the specified basic
121/// block. It returns the virtual register defined by the instruction.
122static
123MachineInstr *InsertNewDef(unsigned Opcode,
124 MachineBasicBlock *BB, MachineBasicBlock::iterator I,
125 const TargetRegisterClass *RC,
126 MachineRegisterInfo *MRI, const TargetInstrInfo *TII) {
127 unsigned NewVR = MRI->createVirtualRegister(RC);
|
129}
130
131/// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that
132/// is live in the middle of the specified block.
133///
134/// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one
135/// important case: if there is a definition of the rewritten value after the
136/// 'use' in BB. Consider code like this:
137///
138/// X1 = ...
139/// SomeBB:
140/// use(X)
141/// X2 = ...
142/// br Cond, SomeBB, OutBB
143///
144/// In this case, there are two values (X1 and X2) added to the AvailableVals
145/// set by the client of the rewriter, and those values are both live out of
146/// their respective blocks. However, the use of X happens in the *middle* of
147/// a block. Because of this, we need to insert a new PHI node in SomeBB to
148/// merge the appropriate values, and this value isn't live out of the block.
149///
150unsigned MachineSSAUpdater::GetValueInMiddleOfBlock(MachineBasicBlock *BB) {
151 // If there is no definition of the renamed variable in this block, just use
152 // GetValueAtEndOfBlock to do our work.
153 if (!getAvailableVals(AV).count(BB))
154 return GetValueAtEndOfBlockInternal(BB);
155
156 // If there are no predecessors, just return undef.
157 if (BB->pred_empty()) {
158 // Insert an implicit_def to represent an undef value.
159 MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF,
160 BB, BB->getFirstTerminator(),
161 VRC, MRI, TII);
162 return NewDef->getOperand(0).getReg();
163 }
164
165 // Otherwise, we have the hard case. Get the live-in values for each
166 // predecessor.
167 SmallVector<std::pair<MachineBasicBlock*, unsigned>, 8> PredValues;
168 unsigned SingularValue = 0;
169
170 bool isFirstPred = true;
171 for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(),
172 E = BB->pred_end(); PI != E; ++PI) {
173 MachineBasicBlock *PredBB = *PI;
174 unsigned PredVal = GetValueAtEndOfBlockInternal(PredBB);
175 PredValues.push_back(std::make_pair(PredBB, PredVal));
176
177 // Compute SingularValue.
178 if (isFirstPred) {
179 SingularValue = PredVal;
180 isFirstPred = false;
181 } else if (PredVal != SingularValue)
182 SingularValue = 0;
183 }
184
185 // Otherwise, if all the merged values are the same, just use it.
186 if (SingularValue != 0)
187 return SingularValue;
188
189 // If an identical PHI is already in BB, just reuse it.
190 unsigned DupPHI = LookForIdenticalPHI(BB, PredValues);
191 if (DupPHI)
192 return DupPHI;
193
194 // Otherwise, we do need a PHI: insert one now.
195 MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->front();
196 MachineInstr *InsertedPHI = InsertNewDef(TargetOpcode::PHI, BB,
197 Loc, VRC, MRI, TII);
198
199 // Fill in all the predecessors of the PHI.
200 MachineInstrBuilder MIB(InsertedPHI);
201 for (unsigned i = 0, e = PredValues.size(); i != e; ++i)
202 MIB.addReg(PredValues[i].second).addMBB(PredValues[i].first);
203
204 // See if the PHI node can be merged to a single value. This can happen in
205 // loop cases when we get a PHI of itself and one other value.
206 if (unsigned ConstVal = InsertedPHI->isConstantValuePHI()) {
207 InsertedPHI->eraseFromParent();
208 return ConstVal;
209 }
210
211 // If the client wants to know about all new instructions, tell it.
212 if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI);
213
214 DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n");
215 return InsertedPHI->getOperand(0).getReg();
216}
217
218static
219MachineBasicBlock *findCorrespondingPred(const MachineInstr *MI,
220 MachineOperand *U) {
221 for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) {
222 if (&MI->getOperand(i) == U)
223 return MI->getOperand(i+1).getMBB();
224 }
225
226 llvm_unreachable("MachineOperand::getParent() failure?");
227 return 0;
228}
229
230/// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes,
231/// which use their value in the corresponding predecessor.
232void MachineSSAUpdater::RewriteUse(MachineOperand &U) {
233 MachineInstr *UseMI = U.getParent();
234 unsigned NewVR = 0;
235 if (UseMI->isPHI()) {
236 MachineBasicBlock *SourceBB = findCorrespondingPred(UseMI, &U);
237 NewVR = GetValueAtEndOfBlockInternal(SourceBB);
238 } else {
239 NewVR = GetValueInMiddleOfBlock(UseMI->getParent());
240 }
241
242 U.setReg(NewVR);
243}
244
245void MachineSSAUpdater::ReplaceRegWith(unsigned OldReg, unsigned NewReg) {
246 MRI->replaceRegWith(OldReg, NewReg);
247
248 AvailableValsTy &AvailableVals = getAvailableVals(AV);
249 for (DenseMap<MachineBasicBlock*, unsigned>::iterator
250 I = AvailableVals.begin(), E = AvailableVals.end(); I != E; ++I)
251 if (I->second == OldReg)
252 I->second = NewReg;
253}
254
255/// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry
256/// for the specified BB and if so, return it. If not, construct SSA form by
257/// walking predecessors inserting PHI nodes as needed until we get to a block
258/// where the value is available.
259///
260unsigned MachineSSAUpdater::GetValueAtEndOfBlockInternal(MachineBasicBlock *BB){
261 AvailableValsTy &AvailableVals = getAvailableVals(AV);
262
263 // Query AvailableVals by doing an insertion of null.
264 std::pair<AvailableValsTy::iterator, bool> InsertRes =
265 AvailableVals.insert(std::make_pair(BB, 0));
266
267 // Handle the case when the insertion fails because we have already seen BB.
268 if (!InsertRes.second) {
269 // If the insertion failed, there are two cases. The first case is that the
270 // value is already available for the specified block. If we get this, just
271 // return the value.
272 if (InsertRes.first->second != 0)
273 return InsertRes.first->second;
274
275 // Otherwise, if the value we find is null, then this is the value is not
276 // known but it is being computed elsewhere in our recursion. This means
277 // that we have a cycle. Handle this by inserting a PHI node and returning
278 // it. When we get back to the first instance of the recursion we will fill
279 // in the PHI node.
280 MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->front();
281 MachineInstr *NewPHI = InsertNewDef(TargetOpcode::PHI, BB, Loc,
282 VRC, MRI,TII);
283 unsigned NewVR = NewPHI->getOperand(0).getReg();
284 InsertRes.first->second = NewVR;
285 return NewVR;
286 }
287
288 // If there are no predecessors, then we must have found an unreachable block
289 // just return 'undef'. Since there are no predecessors, InsertRes must not
290 // be invalidated.
291 if (BB->pred_empty()) {
292 // Insert an implicit_def to represent an undef value.
293 MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF,
294 BB, BB->getFirstTerminator(),
295 VRC, MRI, TII);
296 return InsertRes.first->second = NewDef->getOperand(0).getReg();
297 }
298
299 // Okay, the value isn't in the map and we just inserted a null in the entry
300 // to indicate that we're processing the block. Since we have no idea what
301 // value is in this block, we have to recurse through our predecessors.
302 //
303 // While we're walking our predecessors, we keep track of them in a vector,
304 // then insert a PHI node in the end if we actually need one. We could use a
305 // smallvector here, but that would take a lot of stack space for every level
306 // of the recursion, just use IncomingPredInfo as an explicit stack.
307 IncomingPredInfoTy &IncomingPredInfo = getIncomingPredInfo(IPI);
308 unsigned FirstPredInfoEntry = IncomingPredInfo.size();
309
310 // As we're walking the predecessors, keep track of whether they are all
311 // producing the same value. If so, this value will capture it, if not, it
312 // will get reset to null. We distinguish the no-predecessor case explicitly
313 // below.
314 unsigned SingularValue = 0;
315 bool isFirstPred = true;
316 for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(),
317 E = BB->pred_end(); PI != E; ++PI) {
318 MachineBasicBlock *PredBB = *PI;
319 unsigned PredVal = GetValueAtEndOfBlockInternal(PredBB);
320 IncomingPredInfo.push_back(std::make_pair(PredBB, PredVal));
321
322 // Compute SingularValue.
323 if (isFirstPred) {
324 SingularValue = PredVal;
325 isFirstPred = false;
326 } else if (PredVal != SingularValue)
327 SingularValue = 0;
328 }
329
330 /// Look up BB's entry in AvailableVals. 'InsertRes' may be invalidated. If
331 /// this block is involved in a loop, a no-entry PHI node will have been
332 /// inserted as InsertedVal. Otherwise, we'll still have the null we inserted
333 /// above.
334 unsigned &InsertedVal = AvailableVals[BB];
335
336 // If all the predecessor values are the same then we don't need to insert a
337 // PHI. This is the simple and common case.
338 if (SingularValue) {
339 // If a PHI node got inserted, replace it with the singlar value and delete
340 // it.
341 if (InsertedVal) {
342 MachineInstr *OldVal = MRI->getVRegDef(InsertedVal);
343 // Be careful about dead loops. These RAUW's also update InsertedVal.
344 assert(InsertedVal != SingularValue && "Dead loop?");
345 ReplaceRegWith(InsertedVal, SingularValue);
346 OldVal->eraseFromParent();
347 }
348
349 InsertedVal = SingularValue;
350
351 // Drop the entries we added in IncomingPredInfo to restore the stack.
352 IncomingPredInfo.erase(IncomingPredInfo.begin()+FirstPredInfoEntry,
353 IncomingPredInfo.end());
354 return InsertedVal;
355 }
356
357
358 // Otherwise, we do need a PHI: insert one now if we don't already have one.
359 MachineInstr *InsertedPHI;
360 if (InsertedVal == 0) {
361 MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->front();
362 InsertedPHI = InsertNewDef(TargetOpcode::PHI, BB, Loc,
363 VRC, MRI, TII);
364 InsertedVal = InsertedPHI->getOperand(0).getReg();
365 } else {
366 InsertedPHI = MRI->getVRegDef(InsertedVal);
367 }
368
369 // Fill in all the predecessors of the PHI.
370 MachineInstrBuilder MIB(InsertedPHI);
371 for (IncomingPredInfoTy::iterator I =
372 IncomingPredInfo.begin()+FirstPredInfoEntry,
373 E = IncomingPredInfo.end(); I != E; ++I)
374 MIB.addReg(I->second).addMBB(I->first);
375
376 // Drop the entries we added in IncomingPredInfo to restore the stack.
377 IncomingPredInfo.erase(IncomingPredInfo.begin()+FirstPredInfoEntry,
378 IncomingPredInfo.end());
379
380 // See if the PHI node can be merged to a single value. This can happen in
381 // loop cases when we get a PHI of itself and one other value.
382 if (unsigned ConstVal = InsertedPHI->isConstantValuePHI()) {
383 MRI->replaceRegWith(InsertedVal, ConstVal);
384 InsertedPHI->eraseFromParent();
385 InsertedVal = ConstVal;
386 } else {
387 DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n");
388
389 // If the client wants to know about all new instructions, tell it.
390 if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI);
391 }
392
393 return InsertedVal;
394}
| 129}
130
131/// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that
132/// is live in the middle of the specified block.
133///
134/// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one
135/// important case: if there is a definition of the rewritten value after the
136/// 'use' in BB. Consider code like this:
137///
138/// X1 = ...
139/// SomeBB:
140/// use(X)
141/// X2 = ...
142/// br Cond, SomeBB, OutBB
143///
144/// In this case, there are two values (X1 and X2) added to the AvailableVals
145/// set by the client of the rewriter, and those values are both live out of
146/// their respective blocks. However, the use of X happens in the *middle* of
147/// a block. Because of this, we need to insert a new PHI node in SomeBB to
148/// merge the appropriate values, and this value isn't live out of the block.
149///
150unsigned MachineSSAUpdater::GetValueInMiddleOfBlock(MachineBasicBlock *BB) {
151 // If there is no definition of the renamed variable in this block, just use
152 // GetValueAtEndOfBlock to do our work.
153 if (!getAvailableVals(AV).count(BB))
154 return GetValueAtEndOfBlockInternal(BB);
155
156 // If there are no predecessors, just return undef.
157 if (BB->pred_empty()) {
158 // Insert an implicit_def to represent an undef value.
159 MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF,
160 BB, BB->getFirstTerminator(),
161 VRC, MRI, TII);
162 return NewDef->getOperand(0).getReg();
163 }
164
165 // Otherwise, we have the hard case. Get the live-in values for each
166 // predecessor.
167 SmallVector<std::pair<MachineBasicBlock*, unsigned>, 8> PredValues;
168 unsigned SingularValue = 0;
169
170 bool isFirstPred = true;
171 for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(),
172 E = BB->pred_end(); PI != E; ++PI) {
173 MachineBasicBlock *PredBB = *PI;
174 unsigned PredVal = GetValueAtEndOfBlockInternal(PredBB);
175 PredValues.push_back(std::make_pair(PredBB, PredVal));
176
177 // Compute SingularValue.
178 if (isFirstPred) {
179 SingularValue = PredVal;
180 isFirstPred = false;
181 } else if (PredVal != SingularValue)
182 SingularValue = 0;
183 }
184
185 // Otherwise, if all the merged values are the same, just use it.
186 if (SingularValue != 0)
187 return SingularValue;
188
189 // If an identical PHI is already in BB, just reuse it.
190 unsigned DupPHI = LookForIdenticalPHI(BB, PredValues);
191 if (DupPHI)
192 return DupPHI;
193
194 // Otherwise, we do need a PHI: insert one now.
195 MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->front();
196 MachineInstr *InsertedPHI = InsertNewDef(TargetOpcode::PHI, BB,
197 Loc, VRC, MRI, TII);
198
199 // Fill in all the predecessors of the PHI.
200 MachineInstrBuilder MIB(InsertedPHI);
201 for (unsigned i = 0, e = PredValues.size(); i != e; ++i)
202 MIB.addReg(PredValues[i].second).addMBB(PredValues[i].first);
203
204 // See if the PHI node can be merged to a single value. This can happen in
205 // loop cases when we get a PHI of itself and one other value.
206 if (unsigned ConstVal = InsertedPHI->isConstantValuePHI()) {
207 InsertedPHI->eraseFromParent();
208 return ConstVal;
209 }
210
211 // If the client wants to know about all new instructions, tell it.
212 if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI);
213
214 DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n");
215 return InsertedPHI->getOperand(0).getReg();
216}
217
218static
219MachineBasicBlock *findCorrespondingPred(const MachineInstr *MI,
220 MachineOperand *U) {
221 for (unsigned i = 1, e = MI->getNumOperands(); i != e; i += 2) {
222 if (&MI->getOperand(i) == U)
223 return MI->getOperand(i+1).getMBB();
224 }
225
226 llvm_unreachable("MachineOperand::getParent() failure?");
227 return 0;
228}
229
230/// RewriteUse - Rewrite a use of the symbolic value. This handles PHI nodes,
231/// which use their value in the corresponding predecessor.
232void MachineSSAUpdater::RewriteUse(MachineOperand &U) {
233 MachineInstr *UseMI = U.getParent();
234 unsigned NewVR = 0;
235 if (UseMI->isPHI()) {
236 MachineBasicBlock *SourceBB = findCorrespondingPred(UseMI, &U);
237 NewVR = GetValueAtEndOfBlockInternal(SourceBB);
238 } else {
239 NewVR = GetValueInMiddleOfBlock(UseMI->getParent());
240 }
241
242 U.setReg(NewVR);
243}
244
245void MachineSSAUpdater::ReplaceRegWith(unsigned OldReg, unsigned NewReg) {
246 MRI->replaceRegWith(OldReg, NewReg);
247
248 AvailableValsTy &AvailableVals = getAvailableVals(AV);
249 for (DenseMap<MachineBasicBlock*, unsigned>::iterator
250 I = AvailableVals.begin(), E = AvailableVals.end(); I != E; ++I)
251 if (I->second == OldReg)
252 I->second = NewReg;
253}
254
255/// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry
256/// for the specified BB and if so, return it. If not, construct SSA form by
257/// walking predecessors inserting PHI nodes as needed until we get to a block
258/// where the value is available.
259///
260unsigned MachineSSAUpdater::GetValueAtEndOfBlockInternal(MachineBasicBlock *BB){
261 AvailableValsTy &AvailableVals = getAvailableVals(AV);
262
263 // Query AvailableVals by doing an insertion of null.
264 std::pair<AvailableValsTy::iterator, bool> InsertRes =
265 AvailableVals.insert(std::make_pair(BB, 0));
266
267 // Handle the case when the insertion fails because we have already seen BB.
268 if (!InsertRes.second) {
269 // If the insertion failed, there are two cases. The first case is that the
270 // value is already available for the specified block. If we get this, just
271 // return the value.
272 if (InsertRes.first->second != 0)
273 return InsertRes.first->second;
274
275 // Otherwise, if the value we find is null, then this is the value is not
276 // known but it is being computed elsewhere in our recursion. This means
277 // that we have a cycle. Handle this by inserting a PHI node and returning
278 // it. When we get back to the first instance of the recursion we will fill
279 // in the PHI node.
280 MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->front();
281 MachineInstr *NewPHI = InsertNewDef(TargetOpcode::PHI, BB, Loc,
282 VRC, MRI,TII);
283 unsigned NewVR = NewPHI->getOperand(0).getReg();
284 InsertRes.first->second = NewVR;
285 return NewVR;
286 }
287
288 // If there are no predecessors, then we must have found an unreachable block
289 // just return 'undef'. Since there are no predecessors, InsertRes must not
290 // be invalidated.
291 if (BB->pred_empty()) {
292 // Insert an implicit_def to represent an undef value.
293 MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF,
294 BB, BB->getFirstTerminator(),
295 VRC, MRI, TII);
296 return InsertRes.first->second = NewDef->getOperand(0).getReg();
297 }
298
299 // Okay, the value isn't in the map and we just inserted a null in the entry
300 // to indicate that we're processing the block. Since we have no idea what
301 // value is in this block, we have to recurse through our predecessors.
302 //
303 // While we're walking our predecessors, we keep track of them in a vector,
304 // then insert a PHI node in the end if we actually need one. We could use a
305 // smallvector here, but that would take a lot of stack space for every level
306 // of the recursion, just use IncomingPredInfo as an explicit stack.
307 IncomingPredInfoTy &IncomingPredInfo = getIncomingPredInfo(IPI);
308 unsigned FirstPredInfoEntry = IncomingPredInfo.size();
309
310 // As we're walking the predecessors, keep track of whether they are all
311 // producing the same value. If so, this value will capture it, if not, it
312 // will get reset to null. We distinguish the no-predecessor case explicitly
313 // below.
314 unsigned SingularValue = 0;
315 bool isFirstPred = true;
316 for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(),
317 E = BB->pred_end(); PI != E; ++PI) {
318 MachineBasicBlock *PredBB = *PI;
319 unsigned PredVal = GetValueAtEndOfBlockInternal(PredBB);
320 IncomingPredInfo.push_back(std::make_pair(PredBB, PredVal));
321
322 // Compute SingularValue.
323 if (isFirstPred) {
324 SingularValue = PredVal;
325 isFirstPred = false;
326 } else if (PredVal != SingularValue)
327 SingularValue = 0;
328 }
329
330 /// Look up BB's entry in AvailableVals. 'InsertRes' may be invalidated. If
331 /// this block is involved in a loop, a no-entry PHI node will have been
332 /// inserted as InsertedVal. Otherwise, we'll still have the null we inserted
333 /// above.
334 unsigned &InsertedVal = AvailableVals[BB];
335
336 // If all the predecessor values are the same then we don't need to insert a
337 // PHI. This is the simple and common case.
338 if (SingularValue) {
339 // If a PHI node got inserted, replace it with the singlar value and delete
340 // it.
341 if (InsertedVal) {
342 MachineInstr *OldVal = MRI->getVRegDef(InsertedVal);
343 // Be careful about dead loops. These RAUW's also update InsertedVal.
344 assert(InsertedVal != SingularValue && "Dead loop?");
345 ReplaceRegWith(InsertedVal, SingularValue);
346 OldVal->eraseFromParent();
347 }
348
349 InsertedVal = SingularValue;
350
351 // Drop the entries we added in IncomingPredInfo to restore the stack.
352 IncomingPredInfo.erase(IncomingPredInfo.begin()+FirstPredInfoEntry,
353 IncomingPredInfo.end());
354 return InsertedVal;
355 }
356
357
358 // Otherwise, we do need a PHI: insert one now if we don't already have one.
359 MachineInstr *InsertedPHI;
360 if (InsertedVal == 0) {
361 MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->front();
362 InsertedPHI = InsertNewDef(TargetOpcode::PHI, BB, Loc,
363 VRC, MRI, TII);
364 InsertedVal = InsertedPHI->getOperand(0).getReg();
365 } else {
366 InsertedPHI = MRI->getVRegDef(InsertedVal);
367 }
368
369 // Fill in all the predecessors of the PHI.
370 MachineInstrBuilder MIB(InsertedPHI);
371 for (IncomingPredInfoTy::iterator I =
372 IncomingPredInfo.begin()+FirstPredInfoEntry,
373 E = IncomingPredInfo.end(); I != E; ++I)
374 MIB.addReg(I->second).addMBB(I->first);
375
376 // Drop the entries we added in IncomingPredInfo to restore the stack.
377 IncomingPredInfo.erase(IncomingPredInfo.begin()+FirstPredInfoEntry,
378 IncomingPredInfo.end());
379
380 // See if the PHI node can be merged to a single value. This can happen in
381 // loop cases when we get a PHI of itself and one other value.
382 if (unsigned ConstVal = InsertedPHI->isConstantValuePHI()) {
383 MRI->replaceRegWith(InsertedVal, ConstVal);
384 InsertedPHI->eraseFromParent();
385 InsertedVal = ConstVal;
386 } else {
387 DEBUG(dbgs() << " Inserted PHI: " << *InsertedPHI << "\n");
388
389 // If the client wants to know about all new instructions, tell it.
390 if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI);
391 }
392
393 return InsertedVal;
394}
|