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