LLVM 20.0.0git
PHITransAddr.cpp
Go to the documentation of this file.
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
16#include "llvm/Config/llvm-config.h"
17#include "llvm/IR/Constants.h"
18#include "llvm/IR/Dominators.h"
23using namespace llvm;
24
26 "gvn-add-phi-translation", cl::init(false), cl::Hidden,
27 cl::desc("Enable phi-translation of add instructions"));
28
29static bool canPHITrans(Instruction *Inst) {
30 if (isa<PHINode>(Inst) || isa<GetElementPtrInst>(Inst) || isa<CastInst>(Inst))
31 return true;
32
33 if (Inst->getOpcode() == Instruction::Add &&
34 isa<ConstantInt>(Inst->getOperand(1)))
35 return true;
36
37 return false;
38}
39
40#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
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,
54 // If this is a non-instruction value, there is nothing to do.
55 Instruction *I = dyn_cast<Instruction>(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(InstInputs, I); Entry != InstInputs.end()) {
61 InstInputs.erase(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(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(I->operands(),
76 [&](Value *Op) { return verifySubExpr(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.
83 if (!Addr) return true;
84
85 SmallVector<Instruction*, 8> Tmp(InstInputs.begin(), InstInputs.end());
86
87 if (!verifySubExpr(Addr, 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.
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>(Addr);
108 return !Inst || canPHITrans(Inst);
109}
110
111static void RemoveInstInputs(Value *V,
112 SmallVectorImpl<Instruction*> &InstInputs) {
113 Instruction *I = dyn_cast<Instruction>(V);
114 if (!I) return;
115
116 // If the instruction is in the InstInputs list, remove it.
117 if (auto Entry = find(InstInputs, I); Entry != InstInputs.end()) {
118 InstInputs.erase(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>(Op))
127 RemoveInstInputs(OpInst, InstInputs);
128}
129
130Value *PHITransAddr::translateSubExpr(Value *V, BasicBlock *CurBB,
131 BasicBlock *PredBB,
132 const DominatorTree *DT) {
133 // If this is a non-instruction value, it can't require PHI translation.
134 Instruction *Inst = dyn_cast<Instruction>(V);
135 if (!Inst) return V;
136
137 // Determine whether 'Inst' is an input to our PHI translatable expression.
138 bool isInput = is_contained(InstInputs, 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(find(InstInputs, Inst));
153
154 // If this is a PHI, go ahead and translate it.
155 if (PHINode *PN = dyn_cast<PHINode>(Inst))
156 return addAsInput(PN->getIncomingValueForBlock(PredBB));
157
158 // If this is a non-phi value, and it is analyzable, we can incorporate it
159 // into the expression by making all instruction operands be inputs.
160 if (!canPHITrans(Inst))
161 return nullptr;
162
163 // All instruction operands are now inputs (and of course, they may also be
164 // defined in this block, so they may need to be phi translated themselves.
165 for (Value *Op : Inst->operands())
166 addAsInput(Op);
167 }
168
169 // Ok, it must be an intermediate result (either because it started that way
170 // or because we just incorporated it into the expression). See if its
171 // operands need to be phi translated, and if so, reconstruct it.
172
173 if (CastInst *Cast = dyn_cast<CastInst>(Inst)) {
174 Value *PHIIn = translateSubExpr(Cast->getOperand(0), CurBB, PredBB, DT);
175 if (!PHIIn) return nullptr;
176 if (PHIIn == Cast->getOperand(0))
177 return Cast;
178
179 // Find an available version of this cast.
180
181 // Try to simplify cast first.
182 if (Value *V = simplifyCastInst(Cast->getOpcode(), PHIIn, Cast->getType(),
183 {DL, TLI, DT, AC})) {
184 RemoveInstInputs(PHIIn, InstInputs);
185 return addAsInput(V);
186 }
187
188 // Otherwise we have to see if a casted version of the incoming pointer
189 // is available. If so, we can use it, otherwise we have to fail.
190 for (User *U : PHIIn->users()) {
191 if (CastInst *CastI = dyn_cast<CastInst>(U))
192 if (CastI->getOpcode() == Cast->getOpcode() &&
193 CastI->getType() == Cast->getType() &&
194 (!DT || DT->dominates(CastI->getParent(), PredBB)))
195 return CastI;
196 }
197 return nullptr;
198 }
199
200 // Handle getelementptr with at least one PHI translatable operand.
201 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
203 bool AnyChanged = false;
204 for (Value *Op : GEP->operands()) {
205 Value *GEPOp = translateSubExpr(Op, CurBB, PredBB, DT);
206 if (!GEPOp) return nullptr;
207
208 AnyChanged |= GEPOp != Op;
209 GEPOps.push_back(GEPOp);
210 }
211
212 if (!AnyChanged)
213 return GEP;
214
215 // Simplify the GEP to handle 'gep x, 0' -> x etc.
216 if (Value *V = simplifyGEPInst(GEP->getSourceElementType(), GEPOps[0],
217 ArrayRef<Value *>(GEPOps).slice(1),
218 GEP->getNoWrapFlags(), {DL, TLI, DT, AC})) {
219 for (Value *Op : GEPOps)
220 RemoveInstInputs(Op, InstInputs);
221
222 return addAsInput(V);
223 }
224
225 // Scan to see if we have this GEP available.
226 Value *APHIOp = GEPOps[0];
227 for (User *U : APHIOp->users()) {
228 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U))
229 if (GEPI->getType() == GEP->getType() &&
230 GEPI->getSourceElementType() == GEP->getSourceElementType() &&
231 GEPI->getNumOperands() == GEPOps.size() &&
232 GEPI->getParent()->getParent() == CurBB->getParent() &&
233 (!DT || DT->dominates(GEPI->getParent(), PredBB))) {
234 if (std::equal(GEPOps.begin(), GEPOps.end(), GEPI->op_begin()))
235 return GEPI;
236 }
237 }
238 return nullptr;
239 }
240
241 // Handle add with a constant RHS.
242 if (Inst->getOpcode() == Instruction::Add &&
243 isa<ConstantInt>(Inst->getOperand(1))) {
244 // PHI translate the LHS.
245 Constant *RHS = cast<ConstantInt>(Inst->getOperand(1));
246 bool isNSW = cast<BinaryOperator>(Inst)->hasNoSignedWrap();
247 bool isNUW = cast<BinaryOperator>(Inst)->hasNoUnsignedWrap();
248
249 Value *LHS = translateSubExpr(Inst->getOperand(0), CurBB, PredBB, DT);
250 if (!LHS) return nullptr;
251
252 // If the PHI translated LHS is an add of a constant, fold the immediates.
253 if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(LHS))
254 if (BOp->getOpcode() == Instruction::Add)
255 if (ConstantInt *CI = dyn_cast<ConstantInt>(BOp->getOperand(1))) {
256 LHS = BOp->getOperand(0);
257 RHS = ConstantExpr::getAdd(RHS, CI);
258 isNSW = isNUW = false;
259
260 // If the old 'LHS' was an input, add the new 'LHS' as an input.
261 if (is_contained(InstInputs, BOp)) {
262 RemoveInstInputs(BOp, InstInputs);
263 addAsInput(LHS);
264 }
265 }
266
267 // See if the add simplifies away.
268 if (Value *Res = simplifyAddInst(LHS, RHS, isNSW, isNUW, {DL, TLI, DT, AC})) {
269 // If we simplified the operands, the LHS is no longer an input, but Res
270 // is.
271 RemoveInstInputs(LHS, InstInputs);
272 return addAsInput(Res);
273 }
274
275 // If we didn't modify the add, just return it.
276 if (LHS == Inst->getOperand(0) && RHS == Inst->getOperand(1))
277 return Inst;
278
279 // Otherwise, see if we have this add available somewhere.
280 for (User *U : LHS->users()) {
281 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(U))
282 if (BO->getOpcode() == Instruction::Add &&
283 BO->getOperand(0) == LHS && BO->getOperand(1) == RHS &&
284 BO->getParent()->getParent() == CurBB->getParent() &&
285 (!DT || DT->dominates(BO->getParent(), PredBB)))
286 return BO;
287 }
288
289 return nullptr;
290 }
291
292 // Otherwise, we failed.
293 return nullptr;
294}
295
296/// PHITranslateValue - PHI translate the current address up the CFG from
297/// CurBB to Pred, updating our state to reflect any needed changes. If
298/// 'MustDominate' is true, the translated value must dominate PredBB.
300 const DominatorTree *DT,
301 bool MustDominate) {
302 assert(DT || !MustDominate);
303 assert(verify() && "Invalid PHITransAddr!");
304 if (DT && DT->isReachableFromEntry(PredBB))
305 Addr = translateSubExpr(Addr, CurBB, PredBB, DT);
306 else
307 Addr = nullptr;
308 assert(verify() && "Invalid PHITransAddr!");
309
310 if (MustDominate)
311 // Make sure the value is live in the predecessor.
312 if (Instruction *Inst = dyn_cast_or_null<Instruction>(Addr))
313 if (!DT->dominates(Inst->getParent(), PredBB))
314 Addr = nullptr;
315
316 return Addr;
317}
318
319/// PHITranslateWithInsertion - PHI translate this value into the specified
320/// predecessor block, inserting a computation of the value if it is
321/// unavailable.
322///
323/// All newly created instructions are added to the NewInsts list. This
324/// returns null on failure.
325///
326Value *
328 const DominatorTree &DT,
330 unsigned NISize = NewInsts.size();
331
332 // Attempt to PHI translate with insertion.
333 Addr = insertTranslatedSubExpr(Addr, CurBB, PredBB, DT, NewInsts);
334
335 // If successful, return the new value.
336 if (Addr) return Addr;
337
338 // If not, destroy any intermediate instructions inserted.
339 while (NewInsts.size() != NISize)
340 NewInsts.pop_back_val()->eraseFromParent();
341 return nullptr;
342}
343
344/// insertTranslatedSubExpr - Insert a computation of the PHI translated
345/// version of 'V' for the edge PredBB->CurBB into the end of the PredBB
346/// block. All newly created instructions are added to the NewInsts list.
347/// This returns null on failure.
348///
349Value *PHITransAddr::insertTranslatedSubExpr(
350 Value *InVal, BasicBlock *CurBB, BasicBlock *PredBB,
351 const DominatorTree &DT, SmallVectorImpl<Instruction *> &NewInsts) {
352 // See if we have a version of this value already available and dominating
353 // PredBB. If so, there is no need to insert a new instance of it.
354 PHITransAddr Tmp(InVal, DL, AC);
355 if (Value *Addr =
356 Tmp.translateValue(CurBB, PredBB, &DT, /*MustDominate=*/true))
357 return Addr;
358
359 // We don't need to PHI translate values which aren't instructions.
360 auto *Inst = dyn_cast<Instruction>(InVal);
361 if (!Inst)
362 return nullptr;
363
364 // Handle cast of PHI translatable value.
365 if (CastInst *Cast = dyn_cast<CastInst>(Inst)) {
366 Value *OpVal = insertTranslatedSubExpr(Cast->getOperand(0), CurBB, PredBB,
367 DT, NewInsts);
368 if (!OpVal) return nullptr;
369
370 // Otherwise insert a cast at the end of PredBB.
371 CastInst *New = CastInst::Create(Cast->getOpcode(), OpVal, InVal->getType(),
372 InVal->getName() + ".phi.trans.insert",
373 PredBB->getTerminator()->getIterator());
374 New->setDebugLoc(Inst->getDebugLoc());
375 NewInsts.push_back(New);
376 return New;
377 }
378
379 // Handle getelementptr with at least one PHI operand.
380 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
382 BasicBlock *CurBB = GEP->getParent();
383 for (Value *Op : GEP->operands()) {
384 Value *OpVal = insertTranslatedSubExpr(Op, CurBB, PredBB, DT, NewInsts);
385 if (!OpVal) return nullptr;
386 GEPOps.push_back(OpVal);
387 }
388
390 GEP->getSourceElementType(), GEPOps[0], ArrayRef(GEPOps).slice(1),
391 InVal->getName() + ".phi.trans.insert",
392 PredBB->getTerminator()->getIterator());
393 Result->setDebugLoc(Inst->getDebugLoc());
394 Result->setNoWrapFlags(GEP->getNoWrapFlags());
395 NewInsts.push_back(Result);
396 return Result;
397 }
398
399 // Handle add with a constant RHS.
400 if (EnableAddPhiTranslation && Inst->getOpcode() == Instruction::Add &&
401 isa<ConstantInt>(Inst->getOperand(1))) {
402
403 // FIXME: This code works, but it is unclear that we actually want to insert
404 // a big chain of computation in order to make a value available in a block.
405 // This needs to be evaluated carefully to consider its cost trade offs.
406
407 // PHI translate the LHS.
408 Value *OpVal = insertTranslatedSubExpr(Inst->getOperand(0), CurBB, PredBB,
409 DT, NewInsts);
410 if (OpVal == nullptr)
411 return nullptr;
412
413 BinaryOperator *Res = BinaryOperator::CreateAdd(
414 OpVal, Inst->getOperand(1), InVal->getName() + ".phi.trans.insert",
415 PredBB->getTerminator()->getIterator());
416 Res->setHasNoSignedWrap(cast<BinaryOperator>(Inst)->hasNoSignedWrap());
417 Res->setHasNoUnsignedWrap(cast<BinaryOperator>(Inst)->hasNoUnsignedWrap());
418 NewInsts.push_back(Res);
419 return Res;
420 }
421
422 return nullptr;
423}
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:537
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Hexagon Common GEP
static bool hasNoSignedWrap(BinaryOperator &I)
static bool hasNoUnsignedWrap(BinaryOperator &I)
#define I(x, y, z)
Definition: MD5.cpp:58
static bool isInput(const ArrayRef< StringLiteral > &Prefixes, StringRef Arg)
Definition: OptTable.cpp:151
static void RemoveInstInputs(Value *V, SmallVectorImpl< Instruction * > &InstInputs)
static bool canPHITrans(Instruction *Inst)
static cl::opt< bool > EnableAddPhiTranslation("gvn-add-phi-translation", cl::init(false), cl::Hidden, cl::desc("Enable phi-translation of add instructions"))
static bool verifySubExpr(Value *Expr, SmallVectorImpl< Instruction * > &InstInputs)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Value * RHS
Value * LHS
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
ArrayRef< T > slice(size_t N, size_t M) const
slice(n, m) - Chop off the first N elements of the array, and keep M elements in the array.
Definition: ArrayRef.h:195
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:219
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:239
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:530
static CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass's ...
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2611
This is the shared class of boolean and integer constants.
Definition: Constants.h:81
This is an important base class in LLVM.
Definition: Constant.h:42
This class represents an Operation in the Expression.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Definition: Dominators.cpp:321
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:915
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Definition: Instructions.h:938
void setHasNoUnsignedWrap(bool b=true)
Set or clear the nuw flag on this instruction, which must be an operator which supports this flag.
void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:466
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:274
PHITransAddr - An address value which tracks and handles phi translation.
Definition: PHITransAddr.h:35
Value * translateValue(BasicBlock *CurBB, BasicBlock *PredBB, const DominatorTree *DT, bool MustDominate)
translateValue - PHI translate the current address up the CFG from CurBB to Pred, updating our state ...
void dump() const
bool isPotentiallyPHITranslatable() const
isPotentiallyPHITranslatable - If this needs PHI translation, return true if we have some hope of doi...
bool verify() const
verify - Check internal consistency of this data structure.
Value * translateWithInsertion(BasicBlock *CurBB, BasicBlock *PredBB, const DominatorTree &DT, SmallVectorImpl< Instruction * > &NewInsts)
translateWithInsertion - PHI translate this value into the specified predecessor block,...
bool empty() const
Definition: SmallVector.h:95
size_t size() const
Definition: SmallVector.h:92
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:587
iterator erase(const_iterator CI)
Definition: SmallVector.h:751
void push_back(const T &Elt)
Definition: SmallVector.h:427
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1210
op_range operands()
Definition: User.h:242
Value * getOperand(unsigned i) const
Definition: User.h:169
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
iterator_range< user_iterator > users()
Definition: Value.h:421
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
const ParentTy * getParent() const
Definition: ilist_node.h:32
self_iterator getIterator()
Definition: ilist_node.h:132
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1742
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1722
Value * simplifyGEPInst(Type *SrcTy, Value *Ptr, ArrayRef< Value * > Indices, GEPNoWrapFlags NW, const SimplifyQuery &Q)
Given operands for a GetElementPtrInst, fold the result or return null.
Value * simplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty, const SimplifyQuery &Q)
Given operands for a CastInst, fold the result or return null.
Value * simplifyAddInst(Value *LHS, Value *RHS, bool IsNSW, bool IsNUW, const SimplifyQuery &Q)
Given operands for an Add, fold the result or return null.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
DWARFExpression::Operation Op
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1879