Go to the documentation of this file.
15 #ifndef LLVM_LIB_ANALYSIS_CFLGRAPH_H
16 #define LLVM_LIB_ANALYSIS_CFLGRAPH_H
74 std::vector<NodeInfo> Levels;
78 auto NumLevels = Levels.size();
79 if (NumLevels >
Level)
81 Levels.resize(
Level + 1);
102 NodeInfo *getNode(
Node N) {
103 auto Itr = ValueImpls.
find(
N.Val);
104 if (Itr == ValueImpls.
end() || Itr->
second.getNumLevels() <=
N.DerefLevel)
106 return &Itr->
second.getNodeInfoAtLevel(
N.DerefLevel);
114 auto &ValInfo = ValueImpls[
N.Val];
115 auto Changed = ValInfo.addNodeToLevel(
N.DerefLevel);
116 ValInfo.getNodeInfoAtLevel(
N.DerefLevel).Attr |= Attr;
121 auto *
Info = getNode(
N);
127 auto *FromInfo = getNode(
From);
128 assert(FromInfo !=
nullptr);
129 auto *ToInfo = getNode(To);
130 assert(ToInfo !=
nullptr);
132 FromInfo->Edges.push_back(
Edge{To, Offset});
133 ToInfo->ReverseEdges.push_back(
Edge{
From, Offset});
137 auto Itr = ValueImpls.
find(
N.Val);
138 if (Itr == ValueImpls.
end() || Itr->
second.getNumLevels() <=
N.DerefLevel)
140 return &Itr->
second.getNodeInfoAtLevel(
N.DerefLevel);
144 auto *
Info = getNode(
N);
150 return make_range<const_value_iterator>(ValueImpls.
begin(),
174 class GetEdgesVisitor :
public InstVisitor<GetEdgesVisitor, void> {
185 return CE->getOpcode() != Instruction::ICmp &&
186 CE->getOpcode() != Instruction::FCmp;
191 static bool getPossibleTargets(
CallBase &Call,
193 if (
auto *Fn = Call.getCalledFunction()) {
194 Output.push_back(Fn);
206 if (
auto GVal = dyn_cast<GlobalValue>(Val)) {
210 }
else if (
auto CExpr = dyn_cast<ConstantExpr>(Val)) {
211 if (hasUsefulEdges(CExpr)) {
213 visitConstantExpr(CExpr);
257 ReturnValues(
Builder.ReturnedValues) {}
265 if (RetVal->getType()->isPointerTy()) {
267 ReturnValues.push_back(RetVal);
282 void visitCastInst(
CastInst &Inst) {
284 addAssignEdge(Src, &Inst);
291 addAssignEdge(Src, &Inst);
297 addAssignEdge(Op1, &Inst);
298 addAssignEdge(Op2, &Inst);
303 addAssignEdge(Src, &Inst);
309 addStoreEdge(Val, Ptr);
315 addStoreEdge(Val, Ptr);
318 void visitPHINode(
PHINode &Inst) {
320 addAssignEdge(Val, &Inst);
331 addAssignEdge(
Op, &GEPOp, Offset);
335 auto *GEPOp = cast<GEPOperator>(&Inst);
351 void visitAllocaInst(
AllocaInst &Inst) { addNode(&Inst); }
353 void visitLoadInst(
LoadInst &Inst) {
356 addLoadEdge(Ptr, Val);
362 addStoreEdge(Val, Ptr);
378 static bool isFunctionExternal(
Function *Fn) {
382 bool tryInterproceduralAnalysis(
CallBase &Call,
390 for (
auto *Fn : Fns) {
391 if (isFunctionExternal(Fn) || Fn->
isVarArg())
395 if (!
AA.getAliasSummary(*Fn))
399 for (
auto *Fn : Fns) {
400 auto Summary =
AA.getAliasSummary(*Fn);
401 assert(Summary !=
nullptr);
403 auto &RetParamRelations = Summary->RetParamRelations;
404 for (
auto &Relation : RetParamRelations) {
406 if (IRelation.hasValue()) {
407 Graph.
addNode(IRelation->From);
409 Graph.
addEdge(IRelation->From, IRelation->To);
413 auto &RetParamAttributes = Summary->RetParamAttributes;
414 for (
auto &
Attribute : RetParamAttributes) {
416 if (IAttr.hasValue())
417 Graph.
addNode(IAttr->IValue, IAttr->Attr);
424 void visitCallBase(
CallBase &Call) {
426 for (
Value *V : Call.args())
427 if (V->getType()->isPointerTy())
429 if (Call.getType()->isPointerTy())
443 if (getPossibleTargets(Call, Targets))
444 if (tryInterproceduralAnalysis(Call, Targets))
451 if (!Call.onlyReadsMemory())
452 for (
Value *V : Call.args()) {
453 if (V->getType()->isPointerTy()) {
463 if (Call.getType()->isPointerTy()) {
464 auto *Fn = Call.getCalledFunction();
479 addLoadEdge(Ptr, Val);
485 addAssignEdge(Vec, &Inst);
486 addStoreEdge(Val, &Inst);
500 addAssignEdge(Agg, &Inst);
501 addStoreEdge(Val, &Inst);
506 addLoadEdge(Ptr, &Inst);
512 addAssignEdge(From1, &Inst);
513 addAssignEdge(From2, &Inst);
517 switch (CE->getOpcode()) {
518 case Instruction::GetElementPtr: {
519 auto GEPOp = cast<GEPOperator>(CE);
524 case Instruction::PtrToInt: {
529 case Instruction::IntToPtr: {
534 case Instruction::BitCast:
535 case Instruction::AddrSpaceCast:
536 case Instruction::Trunc:
537 case Instruction::ZExt:
538 case Instruction::SExt:
539 case Instruction::FPExt:
540 case Instruction::FPTrunc:
541 case Instruction::UIToFP:
542 case Instruction::SIToFP:
543 case Instruction::FPToUI:
544 case Instruction::FPToSI: {
545 addAssignEdge(CE->getOperand(0), CE);
550 addAssignEdge(CE->getOperand(1), CE);
551 addAssignEdge(CE->getOperand(2), CE);
555 case Instruction::InsertElement:
556 case Instruction::InsertValue: {
557 addAssignEdge(CE->getOperand(0), CE);
558 addStoreEdge(CE->getOperand(1), CE);
562 case Instruction::ExtractElement:
563 case Instruction::ExtractValue: {
564 addLoadEdge(CE->getOperand(0), CE);
569 case Instruction::FAdd:
570 case Instruction::Sub:
571 case Instruction::FSub:
573 case Instruction::FMul:
574 case Instruction::UDiv:
575 case Instruction::SDiv:
576 case Instruction::FDiv:
577 case Instruction::URem:
578 case Instruction::SRem:
579 case Instruction::FRem:
580 case Instruction::And:
581 case Instruction::Or:
582 case Instruction::Xor:
583 case Instruction::Shl:
584 case Instruction::LShr:
585 case Instruction::AShr:
586 case Instruction::ICmp:
587 case Instruction::FCmp:
588 case Instruction::ShuffleVector: {
589 addAssignEdge(CE->getOperand(0), CE);
590 addAssignEdge(CE->getOperand(1), CE);
594 case Instruction::FNeg: {
595 addAssignEdge(CE->getOperand(0), CE);
611 !isa<InvokeInst>(Inst) &&
612 !isa<ReturnInst>(Inst);
613 return !isa<CmpInst>(Inst) && !isa<FenceInst>(Inst) &&
614 !IsNonInvokeRetTerminator;
618 if (
Arg.getType()->isPointerTy()) {
619 Graph.addNode(InstantiatedValue{&
Arg, 0},
632 void addInstructionToGraph(GetEdgesVisitor &Visitor, Instruction &Inst) {
633 if (!hasUsefulEdges(&Inst))
641 void buildGraphFrom(Function &Fn) {
642 GetEdgesVisitor Visitor(*
this, Fn.getParent()->getDataLayout());
644 for (
auto &Bb : Fn.getBasicBlockList())
645 for (
auto &Inst : Bb.getInstList())
646 addInstructionToGraph(Visitor, Inst);
648 for (
auto &
Arg : Fn.args())
649 addArgumentToGraph(
Arg);
660 return ReturnedValues;
667 #endif // LLVM_LIB_ANALYSIS_CFLGRAPH_H
The Program Expression Graph (PEG) of CFL analysis CFLGraph is auxiliary data structure used by CFL-b...
bool isTerminator() const
This class represents an incoming formal argument to a Function.
This is an optimization pass for GlobalISel generic memory operations.
const NodeInfo * getNode(Node N) const
Return a value (possibly void), from a function.
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
op_range incoming_values()
A parsed version of the target data layout string in and methods for querying it.
bool isPointerTy() const
True if this is an instance of PointerType.
Optional< InstantiatedAttr > instantiateExternalAttribute(ExternalAttribute EAttr, CallBase &Call)
Value * getReturnValue() const
Convenience accessor. Returns null if there is no return value.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
The landingpad instruction holds all of the information necessary to generate correct exception handl...
int64_t getSExtValue() const
Get sign extended value.
void addAttr(Node N, AliasAttrs Attr)
AliasAttrs attrFor(Node N) const
A builder class used to create CFLGraph instance from a given function The CFL-AA that uses this buil...
const Value * getFalseValue() const
bool addNode(Node N, AliasAttrs Attr=AliasAttrs())
Value * getPointerOperand()
Value * getPointerOperand()
DenseMapIterator< Value *, ValueInfo, DenseMapInfo< Value * >, llvm::detail::DenseMapPair< Value *, ValueInfo >, true > const_iterator
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
Value * getValueOperand()
bool hasExactDefinition() const
Return true if this global has an exact defintion.
Value * getNewValOperand()
Value * getPointerOperand()
std::vector< Edge > EdgeList
This instruction inserts a single (scalar) element into a VectorType value.
Analysis containing CSE Info
AliasAttrs getAttrEscaped()
AttrEscaped represent whether the said pointer comes from a known source but escapes to the unknown w...
Optional< InstantiatedRelation > instantiateExternalRelation(ExternalRelation ERelation, CallBase &Call)
An instruction for storing to memory.
NodeInfo & getNodeInfoAtLevel(unsigned Level)
const CFLGraph & getCFLGraph() const
AliasAttrs getAttrUnknown()
AttrUnknown represent whether the said pointer comes from a source not known to alias analyses (such ...
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
const Value * getTrueValue() const
void addEdge(Node From, Node To, int64_t Offset=0)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
const SmallVector< Value *, 4 > & getReturnValues() const
This class represents the LLVM 'select' instruction.
Class for arbitrary precision integers.
static const int64_t UnknownOffset
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Type * getType() const
All values are typed, get the type of this value.
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This class represents a cast from a pointer to an integer.
Base class for instruction visitors.
This is the base class for all instructions that perform data casts.
AliasAttrs getAttrCaller()
AttrCaller represent whether the said pointer comes from a source not known to the current function b...
const NodeInfo & getNodeInfoAtLevel(unsigned Level) const
An instruction for reading from memory.
an instruction that atomically reads a memory location, combines it with another value,...
block Block Frequency Analysis
iterator_range< const_value_iterator > value_mappings() const
AliasAttrs getGlobalOrArgAttrFromValue(const Value &Val)
AttrGlobal represent whether the said pointer is a global value.
unsigned getPointerAddressSpace() const
Method to return the address space of the pointer operand.
bool returnDoesNotAlias() const
Determine if the parameter or return value is marked with NoAlias attribute.
A constant value that is initialized with an expression using other constant values.
This is the result of instantiating InterfaceValue at a particular call.
bool accumulateConstantOffset(const DataLayout &DL, APInt &Offset, function_ref< bool(Value &, APInt &)> ExternalAnalysis=nullptr) const
Accumulate the constant address offset of this GEP if possible.
Value * getPointerOperand()
Provides information about what library functions are available for the current target.
iterator find(const KeyT &Val)
This class represents a cast from an integer to a pointer.
bool isVarArg() const
isVarArg - Return true if this function takes a variable number of arguments.
This instruction constructs a fixed permutation of two input vectors.
Value * getPointerOperand()
This class represents a freeze function that returns random concrete value if an operand is either a ...
std::bitset< NumAliasAttrs > AliasAttrs
These are attributes that an alias analysis can use to mark certain special properties of a given poi...
A range adaptor for a pair of iterators.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
BlockVerifier::State From
an instruction to allocate memory on the stack
Value * getOperand(unsigned i) const
This instruction inserts a struct field of array element value into an aggregate value.
static const unsigned MaxSupportedArgsInSummary
The maximum number of arguments we can put into a summary.
unsigned getNumLevels() const
LLVM Value Representation.
An instruction that atomically checks whether a specified value is in a memory location,...
bool isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI)
Tests if a value is a call or invoke to a library function that allocates memory similar to malloc or...
const CallInst * isFreeCall(const Value *I, const TargetLibraryInfo *TLI)
isFreeCall - Returns non-null if the value is a call to the builtin free()
CFLGraphBuilder(CFLAA &Analysis, const TargetLibraryInfo &TLI, Function &Fn)
bool addNodeToLevel(unsigned Level)