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 "AnalysisOptions.h"
15#include "llvm/Analysis/InstructionSimplify.h"
16#include "llvm/Analysis/Loads.h"
17#include "llvm/Analysis/ValueTracking.h"
18#include "llvm/Config/llvm-config.h"
19#include "llvm/IR/Constants.h"
20#include "llvm/IR/Dominators.h"
21#include "llvm/IR/Instructions.h"
22#include "llvm/IR/PatternMatch.h"
23#include "llvm/Support/ErrorHandling.h"
24#include "llvm/Support/raw_ostream.h"
25using namespace llvm;
26using namespace llvm::PatternMatch;
27
28static 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)
40LLVM_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
51static 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.
81bool 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.
103bool 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
110static 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
129Value *PHITransAddr::translateSubExpr(Value *V, BasicBlock *CurBB,
130 BasicBlock *PredBB,
131 const DominatorTree *DT, Value *Cond,
132 bool CondVal) {
133 // If this is a non-instruction value, it can't require PHI translation.
134 Instruction *Inst = dyn_cast<Instruction>(Val: V);
135 if (!Inst) return V;
136
137 // Determine whether 'Inst' is an input to our PHI translatable expression.
138 bool isInput = is_contained(Range&: InstInputs, Element: Inst);
139
140 // Handle inputs instructions if needed.
141 if (isInput) {
142 if (Inst->getParent() != CurBB) {
143 // If it is an input defined in a different block, then it remains an
144 // input.
145 return Inst;
146 }
147
148 // If 'Inst' is defined in this block and is an input that needs to be phi
149 // translated, we need to incorporate the value into the expression or fail.
150
151 // In either case, the instruction itself isn't an input any longer.
152 InstInputs.erase(CI: find(Range&: InstInputs, Val: Inst));
153
154 // If this is a PHI, go ahead and translate it.
155 if (PHINode *PN = dyn_cast<PHINode>(Val: Inst)) {
156 Value *Incoming = PN->getIncomingValueForBlock(BB: PredBB);
157 // If the incoming value on this edge is a select on the condition we are
158 // resolving, fold it to the requested side. This is what lets us obtain
159 // the two distinct addresses referenced by a select-dependent load along
160 // a backedge (e.g. min/max idioms).
161 if (Cond)
162 if (auto *SI = dyn_cast<SelectInst>(Val: Incoming))
163 if (SI->getCondition() == Cond)
164 return addAsInput(V: CondVal ? SI->getTrueValue()
165 : SI->getFalseValue());
166 return addAsInput(V: Incoming);
167 }
168
169 // If this is a non-phi value, and it is analyzable, we can incorporate it
170 // into the expression by making all instruction operands be inputs.
171 if (!canPHITrans(Inst))
172 return nullptr;
173
174 // All instruction operands are now inputs (and of course, they may also be
175 // defined in this block, so they may need to be phi translated themselves.
176 for (Value *Op : Inst->operands())
177 addAsInput(V: Op);
178 }
179
180 // Ok, it must be an intermediate result (either because it started that way
181 // or because we just incorporated it into the expression). See if its
182 // operands need to be phi translated, and if so, reconstruct it.
183
184 if (CastInst *Cast = dyn_cast<CastInst>(Val: Inst)) {
185 Value *PHIIn =
186 translateSubExpr(V: Cast->getOperand(i_nocapture: 0), CurBB, PredBB, DT, Cond, CondVal);
187 if (!PHIIn) return nullptr;
188 if (PHIIn == Cast->getOperand(i_nocapture: 0))
189 return Cast;
190
191 // Find an available version of this cast.
192
193 // Try to simplify cast first.
194 if (Value *V = simplifyCastInst(CastOpc: Cast->getOpcode(), Op: PHIIn, Ty: Cast->getType(),
195 Q: {DL, TLI, DT, AC})) {
196 RemoveInstInputs(V: PHIIn, InstInputs);
197 return addAsInput(V);
198 }
199
200 // Otherwise we have to see if a casted version of the incoming pointer
201 // is available. If so, we can use it, otherwise we have to fail. Don't
202 // scan the use list of a constant: ConstantData has no use list, and
203 // other constants may be used from different functions, whose blocks are
204 // not in this function's DominatorTree.
205 if (!isa<Constant>(Val: PHIIn)) {
206 for (User *U : PHIIn->users()) {
207 if (CastInst *CastI = dyn_cast<CastInst>(Val: U))
208 if (CastI->getOpcode() == Cast->getOpcode() &&
209 CastI->getType() == Cast->getType() &&
210 (!DT || DT->dominates(A: CastI->getParent(), B: PredBB)))
211 return CastI;
212 }
213 }
214 return nullptr;
215 }
216
217 // Handle getelementptr with at least one PHI translatable operand.
218 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Val: Inst)) {
219 SmallVector<Value*, 8> GEPOps;
220 bool AnyChanged = false;
221 for (Value *Op : GEP->operands()) {
222 Value *GEPOp = translateSubExpr(V: Op, CurBB, PredBB, DT, Cond, CondVal);
223 if (!GEPOp) return nullptr;
224
225 AnyChanged |= GEPOp != Op;
226 GEPOps.push_back(Elt: GEPOp);
227 }
228
229 if (!AnyChanged)
230 return GEP;
231
232 // Simplify the GEP to handle 'gep x, 0' -> x etc.
233 if (Value *V = simplifyGEPInst(SrcTy: GEP->getSourceElementType(), Ptr: GEPOps[0],
234 Indices: ArrayRef<Value *>(GEPOps).slice(N: 1),
235 NW: GEP->getNoWrapFlags(), Q: {DL, TLI, DT, AC})) {
236 for (Value *Op : GEPOps)
237 RemoveInstInputs(V: Op, InstInputs);
238
239 return addAsInput(V);
240 }
241
242 // Scan to see if we have this GEP available.
243 Value *APHIOp = GEPOps[0];
244 if (isa<ConstantData>(Val: APHIOp))
245 return nullptr;
246
247 for (User *U : APHIOp->users()) {
248 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(Val: U))
249 if (GEPI->getType() == GEP->getType() &&
250 GEPI->getSourceElementType() == GEP->getSourceElementType() &&
251 GEPI->getNumOperands() == GEPOps.size() &&
252 GEPI->getParent()->getParent() == CurBB->getParent() &&
253 (!DT || DT->dominates(A: GEPI->getParent(), B: PredBB))) {
254 if (std::equal(first1: GEPOps.begin(), last1: GEPOps.end(), first2: GEPI->op_begin()))
255 return GEPI;
256 }
257 }
258 return nullptr;
259 }
260
261 // Handle add with a constant RHS.
262 if (Inst->getOpcode() == Instruction::Add &&
263 isa<ConstantInt>(Val: Inst->getOperand(i: 1))) {
264 // PHI translate the LHS.
265 Constant *RHS = cast<ConstantInt>(Val: Inst->getOperand(i: 1));
266 bool isNSW = cast<BinaryOperator>(Val: Inst)->hasNoSignedWrap();
267 bool isNUW = cast<BinaryOperator>(Val: Inst)->hasNoUnsignedWrap();
268
269 Value *LHS =
270 translateSubExpr(V: Inst->getOperand(i: 0), CurBB, PredBB, DT, Cond, CondVal);
271 if (!LHS) return nullptr;
272
273 // If the PHI translated LHS is an add of a constant, fold the immediates.
274 if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(Val: LHS))
275 if (BOp->getOpcode() == Instruction::Add)
276 if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: BOp->getOperand(i_nocapture: 1))) {
277 LHS = BOp->getOperand(i_nocapture: 0);
278 RHS = ConstantExpr::getAdd(C1: RHS, C2: CI);
279 isNSW = isNUW = false;
280
281 // If the old 'LHS' was an input, add the new 'LHS' as an input.
282 if (is_contained(Range&: InstInputs, Element: BOp)) {
283 RemoveInstInputs(V: BOp, InstInputs);
284 addAsInput(V: LHS);
285 }
286 }
287
288 // See if the add simplifies away.
289 if (Value *Res = simplifyAddInst(LHS, RHS, IsNSW: isNSW, IsNUW: isNUW, Q: {DL, TLI, DT, AC})) {
290 // If we simplified the operands, the LHS is no longer an input, but Res
291 // is.
292 RemoveInstInputs(V: LHS, InstInputs);
293 return addAsInput(V: Res);
294 }
295
296 // If we didn't modify the add, just return it.
297 if (LHS == Inst->getOperand(i: 0) && RHS == Inst->getOperand(i: 1))
298 return Inst;
299
300 // Otherwise, see if we have this add available somewhere.
301 for (User *U : LHS->users()) {
302 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Val: U))
303 if (BO->getOpcode() == Instruction::Add &&
304 BO->getOperand(i_nocapture: 0) == LHS && BO->getOperand(i_nocapture: 1) == RHS &&
305 BO->getParent()->getParent() == CurBB->getParent() &&
306 (!DT || DT->dominates(A: BO->getParent(), B: PredBB)))
307 return BO;
308 }
309
310 return nullptr;
311 }
312
313 // Otherwise, we failed.
314 return nullptr;
315}
316
317/// PHITranslateValue - PHI translate the current address up the CFG from
318/// CurBB to Pred, updating our state to reflect any needed changes. If
319/// 'MustDominate' is true, the translated value must dominate PredBB.
320Value *PHITransAddr::translateValue(BasicBlock *CurBB, BasicBlock *PredBB,
321 const DominatorTree *DT,
322 bool MustDominate) {
323 assert(DT || !MustDominate);
324 assert(verify() && "Invalid PHITransAddr!");
325 if (DT && DT->isReachableFromEntry(A: PredBB))
326 Addr = translateSubExpr(V: Addr, CurBB, PredBB, DT);
327 else
328 Addr = nullptr;
329 assert(verify() && "Invalid PHITransAddr!");
330
331 if (MustDominate)
332 // Make sure the value is live in the predecessor.
333 if (Instruction *Inst = dyn_cast_or_null<Instruction>(Val: Addr))
334 if (!DT->dominates(A: Inst->getParent(), B: PredBB))
335 Addr = nullptr;
336
337 return Addr;
338}
339
340SelectAddr::SelectAddrs PHITransAddr::translateValue(BasicBlock *CurBB,
341 BasicBlock *PredBB,
342 const DominatorTree *DT,
343 Value *Cond) {
344 assert(Cond && "expected a non-null select condition");
345 assert(verify() && "Invalid PHITransAddr!");
346
347 if (!DT || !DT->isReachableFromEntry(A: PredBB))
348 return {nullptr, nullptr};
349
350 auto TranslateSide = [&](bool CondVal) -> Value * {
351 // Work on a copy so that the original address state is preserved and the
352 // other side can be translated independently.
353 PHITransAddr Tmp(*this);
354 if (Value *V =
355 Tmp.translateSubExpr(V: Tmp.Addr, CurBB, PredBB, DT, Cond, CondVal))
356 return V;
357 // A syntactic match misses addresses built from a differently shaped GEP
358 // chain. Compare decomposed offsets instead.
359 return findAvailableSelectArmAddr(Cond, CurBB, PredBB, DT, CondVal);
360 };
361
362 return {TranslateSide(/*CondVal=*/true), TranslateSide(/*CondVal=*/false)};
363}
364
365Value *PHITransAddr::findAvailableSelectArmAddr(Value *Cond, BasicBlock *CurBB,
366 BasicBlock *PredBB,
367 const DominatorTree *DT,
368 bool CondVal) const {
369 assert(DT && "Select-arm translation requires a dominator tree.");
370 LinearExpression Target = decomposeLinearExpression(DL, Ptr: Addr);
371 Value *Base = Target.BasePtr;
372 if (!Target.Index || !Base->hasUseList())
373 return nullptr;
374 if (auto *BaseI = dyn_cast<Instruction>(Val: Base);
375 BaseI && BaseI->getParent() == CurBB)
376 return nullptr;
377
378 // Translate the index along the edge and fold its constant addends into the
379 // offset. GEP offset arithmetic wraps, so no-wrap flags are not required.
380 PHITransAddr IndexAddr(Target.Index, DL, AC);
381 Value *Index = IndexAddr.translateSubExpr(V: Target.Index, CurBB, PredBB, DT,
382 Cond, CondVal);
383 if (!Index)
384 return nullptr;
385 Value *X;
386 const APInt *C;
387 while (match(V: Index, P: m_AddLike(L: m_Value(V&: X), R: m_APInt(Res&: C)))) {
388 Target.Offset += Target.Scale * *C;
389 Index = X;
390 }
391 Target.Index = Index;
392
393 // Look for an available GEP chain over the same base with an equal linear
394 // expression.
395 static constexpr unsigned MaxGEPsToVisit = 32;
396 unsigned NumScanned = 0;
397 SmallVector<Value *, 8> Worklist = {Base};
398 while (!Worklist.empty()) {
399 Value *Ptr = Worklist.pop_back_val();
400 for (User *U : Ptr->users()) {
401 auto *GEPI = dyn_cast<GetElementPtrInst>(Val: U);
402 // Skip vector GEPs: decomposeLinearExpression requires a scalar pointer.
403 if (!GEPI || GEPI->getType() != Addr->getType() ||
404 GEPI->getFunction() != CurBB->getParent() ||
405 !DT->dominates(A: GEPI->getParent(), B: PredBB))
406 continue;
407 if (++NumScanned > MaxGEPsToVisit)
408 return nullptr;
409 LinearExpression E = decomposeLinearExpression(DL, Ptr: GEPI);
410 if (E.BasePtr == Base && E.Index == Target.Index &&
411 E.Scale == Target.Scale && E.Offset == Target.Offset)
412 return GEPI;
413 Worklist.push_back(Elt: GEPI);
414 }
415 }
416 return nullptr;
417}
418
419SelectInst *PHITransAddr::getSelect() const {
420 for (Instruction *I : InstInputs)
421 if (auto *SI = dyn_cast<SelectInst>(Val: I))
422 return SI;
423 return nullptr;
424}
425
426/// PHITranslateWithInsertion - PHI translate this value into the specified
427/// predecessor block, inserting a computation of the value if it is
428/// unavailable.
429///
430/// All newly created instructions are added to the NewInsts list. This
431/// returns null on failure.
432///
433Value *
434PHITransAddr::translateWithInsertion(BasicBlock *CurBB, BasicBlock *PredBB,
435 const DominatorTree &DT,
436 SmallVectorImpl<Instruction *> &NewInsts) {
437 unsigned NISize = NewInsts.size();
438
439 // Attempt to PHI translate with insertion.
440 Addr = insertTranslatedSubExpr(InVal: Addr, CurBB, PredBB, DT, NewInsts);
441
442 // If successful, return the new value.
443 if (Addr) return Addr;
444
445 // If not, destroy any intermediate instructions inserted.
446 while (NewInsts.size() != NISize)
447 NewInsts.pop_back_val()->eraseFromParent();
448 return nullptr;
449}
450
451/// insertTranslatedSubExpr - Insert a computation of the PHI translated
452/// version of 'V' for the edge PredBB->CurBB into the end of the PredBB
453/// block. All newly created instructions are added to the NewInsts list.
454/// This returns null on failure.
455///
456Value *PHITransAddr::insertTranslatedSubExpr(
457 Value *InVal, BasicBlock *CurBB, BasicBlock *PredBB,
458 const DominatorTree &DT, SmallVectorImpl<Instruction *> &NewInsts) {
459 // See if we have a version of this value already available and dominating
460 // PredBB. If so, there is no need to insert a new instance of it.
461 PHITransAddr Tmp(InVal, DL, AC);
462 if (Value *Addr =
463 Tmp.translateValue(CurBB, PredBB, DT: &DT, /*MustDominate=*/true))
464 return Addr;
465
466 // We don't need to PHI translate values which aren't instructions.
467 auto *Inst = dyn_cast<Instruction>(Val: InVal);
468 if (!Inst)
469 return nullptr;
470
471 // Handle cast of PHI translatable value.
472 if (CastInst *Cast = dyn_cast<CastInst>(Val: Inst)) {
473 Value *OpVal = insertTranslatedSubExpr(InVal: Cast->getOperand(i_nocapture: 0), CurBB, PredBB,
474 DT, NewInsts);
475 if (!OpVal) return nullptr;
476
477 // Otherwise insert a cast at the end of PredBB.
478 CastInst *New = CastInst::Create(Cast->getOpcode(), S: OpVal, Ty: InVal->getType(),
479 Name: InVal->getName() + ".phi.trans.insert",
480 InsertBefore: PredBB->getTerminator()->getIterator());
481 New->setDebugLoc(Inst->getDebugLoc());
482 NewInsts.push_back(Elt: New);
483 return New;
484 }
485
486 // Handle getelementptr with at least one PHI operand.
487 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Val: Inst)) {
488 SmallVector<Value*, 8> GEPOps;
489 BasicBlock *CurBB = GEP->getParent();
490 for (Value *Op : GEP->operands()) {
491 Value *OpVal = insertTranslatedSubExpr(InVal: Op, CurBB, PredBB, DT, NewInsts);
492 if (!OpVal) return nullptr;
493 GEPOps.push_back(Elt: OpVal);
494 }
495
496 GetElementPtrInst *Result = GetElementPtrInst::Create(
497 PointeeType: GEP->getSourceElementType(), Ptr: GEPOps[0], IdxList: ArrayRef(GEPOps).slice(N: 1),
498 NameStr: InVal->getName() + ".phi.trans.insert",
499 InsertBefore: PredBB->getTerminator()->getIterator());
500 Result->setDebugLoc(Inst->getDebugLoc());
501 Result->setNoWrapFlags(GEP->getNoWrapFlags());
502 NewInsts.push_back(Elt: Result);
503 return Result;
504 }
505
506 // Handle add with a constant RHS.
507 if (Inst->getOpcode() == Instruction::Add &&
508 isa<ConstantInt>(Val: Inst->getOperand(i: 1)) &&
509 getAnalysisOptions(C: Inst->getContext()).gvn_add_phi_translation) {
510
511 // FIXME: This code works, but it is unclear that we actually want to insert
512 // a big chain of computation in order to make a value available in a block.
513 // This needs to be evaluated carefully to consider its cost trade offs.
514
515 // PHI translate the LHS.
516 Value *OpVal = insertTranslatedSubExpr(InVal: Inst->getOperand(i: 0), CurBB, PredBB,
517 DT, NewInsts);
518 if (OpVal == nullptr)
519 return nullptr;
520
521 BinaryOperator *Res = BinaryOperator::CreateAdd(
522 V1: OpVal, V2: Inst->getOperand(i: 1), Name: InVal->getName() + ".phi.trans.insert",
523 InsertBefore: PredBB->getTerminator()->getIterator());
524 Res->setHasNoSignedWrap(cast<BinaryOperator>(Val: Inst)->hasNoSignedWrap());
525 Res->setHasNoUnsignedWrap(cast<BinaryOperator>(Val: Inst)->hasNoUnsignedWrap());
526 NewInsts.push_back(Elt: Res);
527 return Res;
528 }
529
530 return nullptr;
531}
532