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