1 | //===- PHITransAddr.cpp - PHI Translation for Addresses -------------------===// |
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 PHITransAddr class. |
10 | // |
11 | //===----------------------------------------------------------------------===// |
12 | |
13 | #include "llvm/Analysis/PHITransAddr.h" |
14 | #include "llvm/Analysis/InstructionSimplify.h" |
15 | #include "llvm/Analysis/ValueTracking.h" |
16 | #include "llvm/Config/llvm-config.h" |
17 | #include "llvm/IR/Constants.h" |
18 | #include "llvm/IR/Dominators.h" |
19 | #include "llvm/IR/Instructions.h" |
20 | #include "llvm/Support/ErrorHandling.h" |
21 | #include "llvm/Support/raw_ostream.h" |
22 | using namespace llvm; |
23 | |
24 | static cl::opt<bool> EnableAddPhiTranslation( |
25 | "gvn-add-phi-translation" , cl::init(Val: false), cl::Hidden, |
26 | cl::desc("Enable phi-translation of add instructions" )); |
27 | |
28 | static bool canPHITrans(Instruction *Inst) { |
29 | if (isa<PHINode>(Val: Inst) || isa<GetElementPtrInst>(Val: Inst) || isa<CastInst>(Val: Inst)) |
30 | return true; |
31 | |
32 | if (Inst->getOpcode() == Instruction::Add && |
33 | isa<ConstantInt>(Val: Inst->getOperand(i: 1))) |
34 | return true; |
35 | |
36 | return false; |
37 | } |
38 | |
39 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
40 | LLVM_DUMP_METHOD void PHITransAddr::dump() const { |
41 | if (!Addr) { |
42 | dbgs() << "PHITransAddr: null\n" ; |
43 | return; |
44 | } |
45 | dbgs() << "PHITransAddr: " << *Addr << "\n" ; |
46 | for (unsigned i = 0, e = InstInputs.size(); i != e; ++i) |
47 | dbgs() << " Input #" << i << " is " << *InstInputs[i] << "\n" ; |
48 | } |
49 | #endif |
50 | |
51 | static bool verifySubExpr(Value *Expr, |
52 | SmallVectorImpl<Instruction *> &InstInputs) { |
53 | // If this is a non-instruction value, there is nothing to do. |
54 | Instruction *I = dyn_cast<Instruction>(Val: Expr); |
55 | if (!I) return true; |
56 | |
57 | // If it's an instruction, it is either in Tmp or its operands recursively |
58 | // are. |
59 | if (auto Entry = find(Range&: InstInputs, Val: I); Entry != InstInputs.end()) { |
60 | InstInputs.erase(CI: Entry); |
61 | return true; |
62 | } |
63 | |
64 | // If it isn't in the InstInputs list it is a subexpr incorporated into the |
65 | // address. Validate that it is phi translatable. |
66 | if (!canPHITrans(Inst: I)) { |
67 | errs() << "Instruction in PHITransAddr is not phi-translatable:\n" ; |
68 | errs() << *I << '\n'; |
69 | llvm_unreachable("Either something is missing from InstInputs or " |
70 | "canPHITrans is wrong." ); |
71 | } |
72 | |
73 | // Validate the operands of the instruction. |
74 | return all_of(Range: I->operands(), |
75 | P: [&](Value *Op) { return verifySubExpr(Expr: Op, InstInputs); }); |
76 | } |
77 | |
78 | /// verify - Check internal consistency of this data structure. If the |
79 | /// structure is valid, it returns true. If invalid, it prints errors and |
80 | /// returns false. |
81 | bool PHITransAddr::verify() const { |
82 | if (!Addr) return true; |
83 | |
84 | SmallVector<Instruction*, 8> Tmp(InstInputs.begin(), InstInputs.end()); |
85 | |
86 | if (!verifySubExpr(Expr: Addr, InstInputs&: Tmp)) |
87 | return false; |
88 | |
89 | if (!Tmp.empty()) { |
90 | errs() << "PHITransAddr contains extra instructions:\n" ; |
91 | for (unsigned i = 0, e = InstInputs.size(); i != e; ++i) |
92 | errs() << " InstInput #" << i << " is " << *InstInputs[i] << "\n" ; |
93 | llvm_unreachable("This is unexpected." ); |
94 | } |
95 | |
96 | // a-ok. |
97 | return true; |
98 | } |
99 | |
100 | /// isPotentiallyPHITranslatable - If this needs PHI translation, return true |
101 | /// if we have some hope of doing it. This should be used as a filter to |
102 | /// avoid calling PHITranslateValue in hopeless situations. |
103 | bool PHITransAddr::isPotentiallyPHITranslatable() const { |
104 | // If the input value is not an instruction, or if it is not defined in CurBB, |
105 | // then we don't need to phi translate it. |
106 | Instruction *Inst = dyn_cast<Instruction>(Val: Addr); |
107 | return !Inst || canPHITrans(Inst); |
108 | } |
109 | |
110 | static void RemoveInstInputs(Value *V, |
111 | SmallVectorImpl<Instruction*> &InstInputs) { |
112 | Instruction *I = dyn_cast<Instruction>(Val: V); |
113 | if (!I) return; |
114 | |
115 | // If the instruction is in the InstInputs list, remove it. |
116 | if (auto Entry = find(Range&: InstInputs, Val: I); Entry != InstInputs.end()) { |
117 | InstInputs.erase(CI: Entry); |
118 | return; |
119 | } |
120 | |
121 | assert(!isa<PHINode>(I) && "Error, removing something that isn't an input" ); |
122 | |
123 | // Otherwise, it must have instruction inputs itself. Zap them recursively. |
124 | for (Value *Op : I->operands()) |
125 | if (Instruction *OpInst = dyn_cast<Instruction>(Val: Op)) |
126 | RemoveInstInputs(V: OpInst, InstInputs); |
127 | } |
128 | |
129 | Value *PHITransAddr::translateSubExpr(Value *V, BasicBlock *CurBB, |
130 | BasicBlock *PredBB, |
131 | const DominatorTree *DT) { |
132 | // If this is a non-instruction value, it can't require PHI translation. |
133 | Instruction *Inst = dyn_cast<Instruction>(Val: V); |
134 | if (!Inst) return V; |
135 | |
136 | // Determine whether 'Inst' is an input to our PHI translatable expression. |
137 | bool isInput = is_contained(Range&: InstInputs, Element: Inst); |
138 | |
139 | // Handle inputs instructions if needed. |
140 | if (isInput) { |
141 | if (Inst->getParent() != CurBB) { |
142 | // If it is an input defined in a different block, then it remains an |
143 | // input. |
144 | return Inst; |
145 | } |
146 | |
147 | // If 'Inst' is defined in this block and is an input that needs to be phi |
148 | // translated, we need to incorporate the value into the expression or fail. |
149 | |
150 | // In either case, the instruction itself isn't an input any longer. |
151 | InstInputs.erase(CI: find(Range&: InstInputs, Val: Inst)); |
152 | |
153 | // If this is a PHI, go ahead and translate it. |
154 | if (PHINode *PN = dyn_cast<PHINode>(Val: Inst)) |
155 | return addAsInput(V: PN->getIncomingValueForBlock(BB: PredBB)); |
156 | |
157 | // If this is a non-phi value, and it is analyzable, we can incorporate it |
158 | // into the expression by making all instruction operands be inputs. |
159 | if (!canPHITrans(Inst)) |
160 | return nullptr; |
161 | |
162 | // All instruction operands are now inputs (and of course, they may also be |
163 | // defined in this block, so they may need to be phi translated themselves. |
164 | for (Value *Op : Inst->operands()) |
165 | addAsInput(V: Op); |
166 | } |
167 | |
168 | // Ok, it must be an intermediate result (either because it started that way |
169 | // or because we just incorporated it into the expression). See if its |
170 | // operands need to be phi translated, and if so, reconstruct it. |
171 | |
172 | if (CastInst *Cast = dyn_cast<CastInst>(Val: Inst)) { |
173 | Value *PHIIn = translateSubExpr(V: Cast->getOperand(i_nocapture: 0), CurBB, PredBB, DT); |
174 | if (!PHIIn) return nullptr; |
175 | if (PHIIn == Cast->getOperand(i_nocapture: 0)) |
176 | return Cast; |
177 | |
178 | // Find an available version of this cast. |
179 | |
180 | // Try to simplify cast first. |
181 | if (Value *V = simplifyCastInst(CastOpc: Cast->getOpcode(), Op: PHIIn, Ty: Cast->getType(), |
182 | Q: {DL, TLI, DT, AC})) { |
183 | RemoveInstInputs(V: PHIIn, InstInputs); |
184 | return addAsInput(V); |
185 | } |
186 | |
187 | // Otherwise we have to see if a casted version of the incoming pointer |
188 | // is available. If so, we can use it, otherwise we have to fail. |
189 | for (User *U : PHIIn->users()) { |
190 | if (CastInst *CastI = dyn_cast<CastInst>(Val: U)) |
191 | if (CastI->getOpcode() == Cast->getOpcode() && |
192 | CastI->getType() == Cast->getType() && |
193 | (!DT || DT->dominates(A: CastI->getParent(), B: PredBB))) |
194 | return CastI; |
195 | } |
196 | return nullptr; |
197 | } |
198 | |
199 | // Handle getelementptr with at least one PHI translatable operand. |
200 | if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Val: Inst)) { |
201 | SmallVector<Value*, 8> GEPOps; |
202 | bool AnyChanged = false; |
203 | for (Value *Op : GEP->operands()) { |
204 | Value *GEPOp = translateSubExpr(V: Op, CurBB, PredBB, DT); |
205 | if (!GEPOp) return nullptr; |
206 | |
207 | AnyChanged |= GEPOp != Op; |
208 | GEPOps.push_back(Elt: GEPOp); |
209 | } |
210 | |
211 | if (!AnyChanged) |
212 | return GEP; |
213 | |
214 | // Simplify the GEP to handle 'gep x, 0' -> x etc. |
215 | if (Value *V = simplifyGEPInst(SrcTy: GEP->getSourceElementType(), Ptr: GEPOps[0], |
216 | Indices: ArrayRef<Value *>(GEPOps).slice(N: 1), |
217 | InBounds: GEP->isInBounds(), Q: {DL, TLI, DT, AC})) { |
218 | for (unsigned i = 0, e = GEPOps.size(); i != e; ++i) |
219 | RemoveInstInputs(V: GEPOps[i], InstInputs); |
220 | |
221 | return addAsInput(V); |
222 | } |
223 | |
224 | // Scan to see if we have this GEP available. |
225 | Value *APHIOp = GEPOps[0]; |
226 | for (User *U : APHIOp->users()) { |
227 | if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(Val: U)) |
228 | if (GEPI->getType() == GEP->getType() && |
229 | GEPI->getSourceElementType() == GEP->getSourceElementType() && |
230 | GEPI->getNumOperands() == GEPOps.size() && |
231 | GEPI->getParent()->getParent() == CurBB->getParent() && |
232 | (!DT || DT->dominates(A: GEPI->getParent(), B: PredBB))) { |
233 | if (std::equal(first1: GEPOps.begin(), last1: GEPOps.end(), first2: GEPI->op_begin())) |
234 | return GEPI; |
235 | } |
236 | } |
237 | return nullptr; |
238 | } |
239 | |
240 | // Handle add with a constant RHS. |
241 | if (Inst->getOpcode() == Instruction::Add && |
242 | isa<ConstantInt>(Val: Inst->getOperand(i: 1))) { |
243 | // PHI translate the LHS. |
244 | Constant *RHS = cast<ConstantInt>(Val: Inst->getOperand(i: 1)); |
245 | bool isNSW = cast<BinaryOperator>(Val: Inst)->hasNoSignedWrap(); |
246 | bool isNUW = cast<BinaryOperator>(Val: Inst)->hasNoUnsignedWrap(); |
247 | |
248 | Value *LHS = translateSubExpr(V: Inst->getOperand(i: 0), CurBB, PredBB, DT); |
249 | if (!LHS) return nullptr; |
250 | |
251 | // If the PHI translated LHS is an add of a constant, fold the immediates. |
252 | if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(Val: LHS)) |
253 | if (BOp->getOpcode() == Instruction::Add) |
254 | if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: BOp->getOperand(i_nocapture: 1))) { |
255 | LHS = BOp->getOperand(i_nocapture: 0); |
256 | RHS = ConstantExpr::getAdd(C1: RHS, C2: CI); |
257 | isNSW = isNUW = false; |
258 | |
259 | // If the old 'LHS' was an input, add the new 'LHS' as an input. |
260 | if (is_contained(Range&: InstInputs, Element: BOp)) { |
261 | RemoveInstInputs(V: BOp, InstInputs); |
262 | addAsInput(V: LHS); |
263 | } |
264 | } |
265 | |
266 | // See if the add simplifies away. |
267 | if (Value *Res = simplifyAddInst(LHS, RHS, IsNSW: isNSW, IsNUW: isNUW, Q: {DL, TLI, DT, AC})) { |
268 | // If we simplified the operands, the LHS is no longer an input, but Res |
269 | // is. |
270 | RemoveInstInputs(V: LHS, InstInputs); |
271 | return addAsInput(V: Res); |
272 | } |
273 | |
274 | // If we didn't modify the add, just return it. |
275 | if (LHS == Inst->getOperand(i: 0) && RHS == Inst->getOperand(i: 1)) |
276 | return Inst; |
277 | |
278 | // Otherwise, see if we have this add available somewhere. |
279 | for (User *U : LHS->users()) { |
280 | if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Val: U)) |
281 | if (BO->getOpcode() == Instruction::Add && |
282 | BO->getOperand(i_nocapture: 0) == LHS && BO->getOperand(i_nocapture: 1) == RHS && |
283 | BO->getParent()->getParent() == CurBB->getParent() && |
284 | (!DT || DT->dominates(A: BO->getParent(), B: PredBB))) |
285 | return BO; |
286 | } |
287 | |
288 | return nullptr; |
289 | } |
290 | |
291 | // Otherwise, we failed. |
292 | return nullptr; |
293 | } |
294 | |
295 | /// PHITranslateValue - PHI translate the current address up the CFG from |
296 | /// CurBB to Pred, updating our state to reflect any needed changes. If |
297 | /// 'MustDominate' is true, the translated value must dominate PredBB. |
298 | Value *PHITransAddr::translateValue(BasicBlock *CurBB, BasicBlock *PredBB, |
299 | const DominatorTree *DT, |
300 | bool MustDominate) { |
301 | assert(DT || !MustDominate); |
302 | assert(verify() && "Invalid PHITransAddr!" ); |
303 | if (DT && DT->isReachableFromEntry(A: PredBB)) |
304 | Addr = translateSubExpr(V: Addr, CurBB, PredBB, DT); |
305 | else |
306 | Addr = nullptr; |
307 | assert(verify() && "Invalid PHITransAddr!" ); |
308 | |
309 | if (MustDominate) |
310 | // Make sure the value is live in the predecessor. |
311 | if (Instruction *Inst = dyn_cast_or_null<Instruction>(Val: Addr)) |
312 | if (!DT->dominates(A: Inst->getParent(), B: PredBB)) |
313 | Addr = nullptr; |
314 | |
315 | return Addr; |
316 | } |
317 | |
318 | /// PHITranslateWithInsertion - PHI translate this value into the specified |
319 | /// predecessor block, inserting a computation of the value if it is |
320 | /// unavailable. |
321 | /// |
322 | /// All newly created instructions are added to the NewInsts list. This |
323 | /// returns null on failure. |
324 | /// |
325 | Value * |
326 | PHITransAddr::translateWithInsertion(BasicBlock *CurBB, BasicBlock *PredBB, |
327 | const DominatorTree &DT, |
328 | SmallVectorImpl<Instruction *> &NewInsts) { |
329 | unsigned NISize = NewInsts.size(); |
330 | |
331 | // Attempt to PHI translate with insertion. |
332 | Addr = insertTranslatedSubExpr(InVal: Addr, CurBB, PredBB, DT, NewInsts); |
333 | |
334 | // If successful, return the new value. |
335 | if (Addr) return Addr; |
336 | |
337 | // If not, destroy any intermediate instructions inserted. |
338 | while (NewInsts.size() != NISize) |
339 | NewInsts.pop_back_val()->eraseFromParent(); |
340 | return nullptr; |
341 | } |
342 | |
343 | /// insertTranslatedSubExpr - Insert a computation of the PHI translated |
344 | /// version of 'V' for the edge PredBB->CurBB into the end of the PredBB |
345 | /// block. All newly created instructions are added to the NewInsts list. |
346 | /// This returns null on failure. |
347 | /// |
348 | Value *PHITransAddr::insertTranslatedSubExpr( |
349 | Value *InVal, BasicBlock *CurBB, BasicBlock *PredBB, |
350 | const DominatorTree &DT, SmallVectorImpl<Instruction *> &NewInsts) { |
351 | // See if we have a version of this value already available and dominating |
352 | // PredBB. If so, there is no need to insert a new instance of it. |
353 | PHITransAddr Tmp(InVal, DL, AC); |
354 | if (Value *Addr = |
355 | Tmp.translateValue(CurBB, PredBB, DT: &DT, /*MustDominate=*/true)) |
356 | return Addr; |
357 | |
358 | // We don't need to PHI translate values which aren't instructions. |
359 | auto *Inst = dyn_cast<Instruction>(Val: InVal); |
360 | if (!Inst) |
361 | return nullptr; |
362 | |
363 | // Handle cast of PHI translatable value. |
364 | if (CastInst *Cast = dyn_cast<CastInst>(Val: Inst)) { |
365 | Value *OpVal = insertTranslatedSubExpr(InVal: Cast->getOperand(i_nocapture: 0), CurBB, PredBB, |
366 | DT, NewInsts); |
367 | if (!OpVal) return nullptr; |
368 | |
369 | // Otherwise insert a cast at the end of PredBB. |
370 | CastInst *New = CastInst::Create(Cast->getOpcode(), S: OpVal, Ty: InVal->getType(), |
371 | Name: InVal->getName() + ".phi.trans.insert" , |
372 | InsertBefore: PredBB->getTerminator()); |
373 | New->setDebugLoc(Inst->getDebugLoc()); |
374 | NewInsts.push_back(Elt: New); |
375 | return New; |
376 | } |
377 | |
378 | // Handle getelementptr with at least one PHI operand. |
379 | if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Val: Inst)) { |
380 | SmallVector<Value*, 8> GEPOps; |
381 | BasicBlock *CurBB = GEP->getParent(); |
382 | for (Value *Op : GEP->operands()) { |
383 | Value *OpVal = insertTranslatedSubExpr(InVal: Op, CurBB, PredBB, DT, NewInsts); |
384 | if (!OpVal) return nullptr; |
385 | GEPOps.push_back(Elt: OpVal); |
386 | } |
387 | |
388 | GetElementPtrInst *Result = GetElementPtrInst::Create( |
389 | PointeeType: GEP->getSourceElementType(), Ptr: GEPOps[0], IdxList: ArrayRef(GEPOps).slice(N: 1), |
390 | NameStr: InVal->getName() + ".phi.trans.insert" , InsertBefore: PredBB->getTerminator()); |
391 | Result->setDebugLoc(Inst->getDebugLoc()); |
392 | Result->setIsInBounds(GEP->isInBounds()); |
393 | NewInsts.push_back(Elt: Result); |
394 | return Result; |
395 | } |
396 | |
397 | // Handle add with a constant RHS. |
398 | if (EnableAddPhiTranslation && Inst->getOpcode() == Instruction::Add && |
399 | isa<ConstantInt>(Val: Inst->getOperand(i: 1))) { |
400 | |
401 | // FIXME: This code works, but it is unclear that we actually want to insert |
402 | // a big chain of computation in order to make a value available in a block. |
403 | // This needs to be evaluated carefully to consider its cost trade offs. |
404 | |
405 | // PHI translate the LHS. |
406 | Value *OpVal = insertTranslatedSubExpr(InVal: Inst->getOperand(i: 0), CurBB, PredBB, |
407 | DT, NewInsts); |
408 | if (OpVal == nullptr) |
409 | return nullptr; |
410 | |
411 | BinaryOperator *Res = BinaryOperator::CreateAdd(V1: OpVal, V2: Inst->getOperand(i: 1), |
412 | Name: InVal->getName()+".phi.trans.insert" , |
413 | I: PredBB->getTerminator()); |
414 | Res->setHasNoSignedWrap(cast<BinaryOperator>(Val: Inst)->hasNoSignedWrap()); |
415 | Res->setHasNoUnsignedWrap(cast<BinaryOperator>(Val: Inst)->hasNoUnsignedWrap()); |
416 | NewInsts.push_back(Elt: Res); |
417 | return Res; |
418 | } |
419 | |
420 | return nullptr; |
421 | } |
422 | |