1//===- PHITransAddr.cpp - PHI Translation for Addresses -------------------===//
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
7//===----------------------------------------------------------------------===//
9// This file implements the PHITransAddr class.
11//===----------------------------------------------------------------------===//
16#include "llvm/Config/llvm-config.h"
27 cl::desc(
"Enable phi-translation of add instructions"));
33 if (Inst->
getOpcode() == Instruction::Add &&
40#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
43 dbgs() <<
"PHITransAddr: null\n";
46 dbgs() <<
"PHITransAddr: " << *Addr <<
"\n";
47 for (
unsigned i = 0, e = InstInputs.size(); i != e; ++i)
48 dbgs() <<
" Input #" << i <<
" is " << *InstInputs[i] <<
"\n";
54 // If this is a non-instruction value, there is nothing to do.
58 // If it's an instruction, it is either in Tmp or its operands recursively
60 if (
auto Entry =
find(InstInputs,
I); Entry != InstInputs.
end()) {
61 InstInputs.
erase(Entry);
65 // If it isn't in the InstInputs list it is a subexpr incorporated into the
66 // address. Validate that it is phi translatable.
68 errs() <<
"Instruction in PHITransAddr is not phi-translatable:\n";
71 "canPHITrans is wrong.");
74 // Validate the operands of the instruction.
76 [&](
Value *
Op) { return verifySubExpr(Op, InstInputs); });
79/// verify - Check internal consistency of this data structure. If the
80/// structure is valid, it returns true. If invalid, it prints errors and
83 if (!Addr)
return true;
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";
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.
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);
124 // Otherwise, it must have instruction inputs itself. Zap them recursively.
133 // If this is a non-instruction value, it can't require PHI translation.
137 // Determine whether 'Inst' is an input to our PHI translatable expression.
140 // Handle inputs instructions if needed.
143 // If it is an input defined in a different block, then it remains an
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.
151 // In either case, the instruction itself isn't an input any longer.
152 InstInputs.erase(
find(InstInputs, Inst));
154 // If this is a PHI, go ahead and translate it.
156 return addAsInput(PN->getIncomingValueForBlock(PredBB));
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.
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.
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.
174 Value *PHIIn = translateSubExpr(Cast->getOperand(0), CurBB, PredBB, DT);
175 if (!PHIIn)
return nullptr;
176 if (PHIIn == Cast->getOperand(0))
179 // Find an available version of this cast.
181 // Try to simplify cast first.
183 {DL, TLI, DT, AC})) {
185 return addAsInput(V);
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()) {
192 if (CastI->getOpcode() == Cast->getOpcode() &&
193 CastI->getType() == Cast->getType() &&
194 (!DT || DT->
dominates(CastI->getParent(), PredBB)))
200 // Handle getelementptr with at least one PHI translatable operand.
202 SmallVector<Value*, 8> GEPOps;
203 bool AnyChanged =
false;
205 Value *GEPOp = translateSubExpr(
Op, CurBB, PredBB, DT);
206 if (!GEPOp)
return nullptr;
208 AnyChanged |= GEPOp !=
Op;
215 // Simplify the GEP to handle 'gep x, 0' -> x etc.
218 GEP->getNoWrapFlags(), {DL, TLI, DT, AC})) {
222 return addAsInput(V);
225 // Scan to see if we have this GEP available.
226 Value *APHIOp = GEPOps[0];
230 for (User *U : APHIOp->
users()) {
232 if (GEPI->getType() ==
GEP->getType() &&
233 GEPI->getSourceElementType() ==
GEP->getSourceElementType() &&
234 GEPI->getNumOperands() == GEPOps.
size() &&
235 GEPI->getParent()->getParent() == CurBB->
getParent() &&
236 (!DT || DT->
dominates(GEPI->getParent(), PredBB))) {
237 if (std::equal(GEPOps.
begin(), GEPOps.
end(), GEPI->op_begin()))
244 // Handle add with a constant RHS.
245 if (Inst->
getOpcode() == Instruction::Add &&
247 // PHI translate the LHS.
253 if (!
LHS)
return nullptr;
255 // If the PHI translated LHS is an add of a constant, fold the immediates.
257 if (BOp->getOpcode() == Instruction::Add)
259 LHS = BOp->getOperand(0);
261 isNSW = isNUW =
false;
263 // If the old 'LHS' was an input, add the new 'LHS' as an input.
270 // See if the add simplifies away.
272 // If we simplified the operands, the LHS is no longer an input, but Res
275 return addAsInput(Res);
278 // If we didn't modify the add, just return it.
282 // Otherwise, see if we have this add available somewhere.
285 if (BO->getOpcode() == Instruction::Add &&
286 BO->getOperand(0) ==
LHS && BO->getOperand(1) ==
RHS &&
287 BO->getParent()->getParent() == CurBB->
getParent() &&
288 (!DT || DT->
dominates(BO->getParent(), PredBB)))
295 // Otherwise, we failed.
299/// PHITranslateValue - PHI translate the current address up the CFG from
300/// CurBB to Pred, updating our state to reflect any needed changes. If
301/// 'MustDominate' is true, the translated value must dominate PredBB.
305 assert(DT || !MustDominate);
308 Addr = translateSubExpr(Addr, CurBB, PredBB, DT);
314 // Make sure the value is live in the predecessor.
322/// PHITranslateWithInsertion - PHI translate this value into the specified
323/// predecessor block, inserting a computation of the value if it is
326/// All newly created instructions are added to the NewInsts list. This
327/// returns null on failure.
333 unsigned NISize = NewInsts.
size();
335 // Attempt to PHI translate with insertion.
336 Addr = insertTranslatedSubExpr(Addr, CurBB, PredBB, DT, NewInsts);
338 // If successful, return the new value.
339 if (Addr)
return Addr;
341 // If not, destroy any intermediate instructions inserted.
342 while (NewInsts.
size() != NISize)
347/// insertTranslatedSubExpr - Insert a computation of the PHI translated
348/// version of 'V' for the edge PredBB->CurBB into the end of the PredBB
349/// block. All newly created instructions are added to the NewInsts list.
350/// This returns null on failure.
352Value *PHITransAddr::insertTranslatedSubExpr(
355 // See if we have a version of this value already available and dominating
356 // PredBB. If so, there is no need to insert a new instance of it.
359 Tmp.translateValue(CurBB, PredBB, &DT,
/*MustDominate=*/true))
362 // We don't need to PHI translate values which aren't instructions.
367 // Handle cast of PHI translatable value.
369 Value *OpVal = insertTranslatedSubExpr(Cast->getOperand(0), CurBB, PredBB,
371 if (!OpVal)
return nullptr;
373 // Otherwise insert a cast at the end of PredBB.
375 InVal->
getName() +
".phi.trans.insert",
382 // Handle getelementptr with at least one PHI operand.
387 Value *OpVal = insertTranslatedSubExpr(
Op, CurBB, PredBB, DT, NewInsts);
388 if (!OpVal)
return nullptr;
393 GEP->getSourceElementType(), GEPOps[0],
ArrayRef(GEPOps).slice(1),
394 InVal->
getName() +
".phi.trans.insert",
397 Result->setNoWrapFlags(
GEP->getNoWrapFlags());
402 // Handle add with a constant RHS.
406 // FIXME: This code works, but it is unclear that we actually want to insert
407 // a big chain of computation in order to make a value available in a block.
408 // This needs to be evaluated carefully to consider its cost trade offs.
410 // PHI translate the LHS.
411 Value *OpVal = insertTranslatedSubExpr(Inst->
getOperand(0), CurBB, PredBB,
413 if (OpVal ==
nullptr)
416 BinaryOperator *Res = BinaryOperator::CreateAdd(
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static bool hasNoSignedWrap(BinaryOperator &I)
static bool hasNoUnsignedWrap(BinaryOperator &I)
static bool isInput(const ArrayRef< StringRef > &Prefixes, StringRef Arg)
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)
LLVM Basic Block Representation.
const Function * getParent() const
Return the enclosing method, or null if none.
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...
This is the base class for all instructions that perform data casts.
static LLVM_ABI 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 LLVM_ABI Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
LLVM_ABI bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
LLVM_ABI void setHasNoUnsignedWrap(bool b=true)
Set or clear the nuw flag on this instruction, which must be an operator which supports this flag.
LLVM_ABI 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.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
PHITransAddr - An address value which tracks and handles phi translation.
LLVM_ABI 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 ...
LLVM_ABI void dump() const
LLVM_ABI bool isPotentiallyPHITranslatable() const
isPotentiallyPHITranslatable - If this needs PHI translation, return true if we have some hope of doi...
LLVM_ABI bool verify() const
verify - Check internal consistency of this data structure.
LLVM_ABI Value * translateWithInsertion(BasicBlock *CurBB, BasicBlock *PredBB, const DominatorTree &DT, SmallVectorImpl< Instruction * > &NewInsts)
translateWithInsertion - PHI translate this value into the specified predecessor block,...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
iterator erase(const_iterator CI)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
iterator_range< user_iterator > users()
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
const ParentTy * getParent() const
self_iterator getIterator()
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
initializer< Ty > init(const Ty &Val)
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
FunctionAddr VTableAddr Value
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI 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.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI Value * simplifyCastInst(unsigned CastOpc, Value *Op, Type *Ty, const SimplifyQuery &Q)
Given operands for a CastInst, fold the result or return null.
LLVM_ABI Value * simplifyAddInst(Value *LHS, Value *RHS, bool IsNSW, bool IsNUW, const SimplifyQuery &Q)
Given operands for an Add, fold the result or return null.
auto dyn_cast_or_null(const Y &Val)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
LLVM_ABI raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
DWARFExpression::Operation Op
ArrayRef(const T &OneElt) -> ArrayRef< T >
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.