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