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