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