Static Value-Flow Analysis
Loading...
Searching...
No Matches
SVF::PAGBuilder Class Reference

#include <PAGBuilder.h>

Inheritance diagram for SVF::PAGBuilder:

Public Member Functions

 PAGBuilder ()
 Constructor.
virtual ~PAGBuilder ()
 Destructor.
virtual PAG * build ()
 Start building PAG here.
PAG * getPAG () const
 Return PAG.
void createFunObjVars ()
void initFunObjVar ()
void initialiseNodes ()
 Initialize nodes and edges.
void initialiseBaseObjVars ()
void initialiseValVars ()
void initSVFBasicBlock (const Function *func)
void initDomTree (FunObjVar *func, const Function *f)
void addEdge (NodeID src, NodeID dst, SVFStmt::PEDGEK kind, APOffset offset=0, Instruction *cs=nullptr)
void sanityCheck ()
 Sanity check for PAG.
NodeID getValueNode (const Value *V)
 Get different kinds of node.
NodeID getObjectNode (const Value *V)
 GetObject - Return the object node (stack/global/heap/function) according to a LLVM Value.
NodeID getReturnNode (const FunObjVar *func)
 getReturnNode - Return the node representing the unique return value of a function.
NodeID getVarargNode (const FunObjVar *func)
 getVarargNode - Return the node representing the unique variadic argument of a function.
virtual void visitAllocaInst (AllocaInst &AI)
 Our visit overrides.
void visitPHINode (PHINode &I)
void visitStoreInst (StoreInst &I)
void visitLoadInst (LoadInst &I)
void visitGetElementPtrInst (GetElementPtrInst &I)
void visitCallInst (CallInst &I)
void visitInvokeInst (InvokeInst &II)
void visitCallBrInst (CallBrInst &I)
void visitCallSite (CallBase *cs)
void visitReturnInst (ReturnInst &I)
void visitCastInst (CastInst &I)
void visitSelectInst (SelectInst &I)
void visitExtractValueInst (ExtractValueInst &EVI)
void visitBranchInst (BranchInst &I)
void visitSwitchInst (SwitchInst &I)
 Preserve LLVM switch destinations and case values in BranchStmt.
void visitInsertValueInst (InsertValueInst &I)
void visitBinaryOperator (BinaryOperator &I)
void visitUnaryOperator (UnaryOperator &I)
void visitCmpInst (CmpInst &I)
void visitVAArgInst (VAArgInst &)
void visitVACopyInst (VACopyInst &)
void visitVAEndInst (VAEndInst &)
void visitVAStartInst (VAStartInst &)
void visitFreezeInst (FreezeInst &I)
void visitExtractElementInst (ExtractElementInst &I)
void visitInsertElementInst (InsertElementInst &I)
void visitShuffleVectorInst (ShuffleVectorInst &I)
void visitLandingPadInst (LandingPadInst &I)
void visitResumeInst (ResumeInst &)
 Instruction not that often.
void visitUnreachableInst (UnreachableInst &)
void visitFenceInst (FenceInst &I)
void visitAtomicCmpXchgInst (AtomicCmpXchgInst &I)
void visitAtomicRMWInst (AtomicRMWInst &I)
void visitInstruction (Instruction &)
 Provide base case for our instruction visit.
void updateCallGraph (CallGraph *callgraph)
 connect PAG edges based on callgraph

Protected Member Functions

void visitGlobal ()
 Handle globals including (global variable and functions).
void InitialGlobal (const GlobalVariable *gvar, Constant *C, u32_t offset)
NodeID getGlobalVarField (const GlobalVariable *gvar, u32_t offset, SVFType *tpy)
void processCE (const Value *val)
 Process constant expression.
u32_t inferFieldIdxFromByteOffset (const llvm::GEPOperator *gepOp, DataLayout *dl, AccessPath &ap, APOffset idx)
 Infer field index from byteoffset.
bool computeGepOffset (const User *V, AccessPath &ap)
 Compute offset of a gep instruction or gep constant expression.
const Value * getBaseValueForExtArg (const Value *V)
 Get the base value of (i8* src and i8* dst) for external argument (e.g. memcpy(i8* dst, i8* src, int size)).
void handleDirectCall (CallBase *cs, const Function *F)
 Handle direct call.
void handleIndCall (CallBase *cs)
 Handle indirect call.
virtual const Type * getBaseTypeAndFlattenedFields (const Value *V, std::vector< AccessPath > &fields, const Value *szValue)
 Handle external call.
virtual void addComplexConsForExt (Value *D, Value *S, const Value *sz)
virtual void handleNondetArgStoreAtExtCall (const CallBase *cs, const CallICFGNode *callICFGNode)
virtual void handleExtCall (const CallBase *cs, const Function *callee)
void setCurrentLocation (const Value *val, const BasicBlock *bb)
 Set current basic block in order to keep track of control flow information.
void setCurrentLocation (const Value *val, const SVFBasicBlock *bb)
const Value * getCurrentValue () const
const SVFBasicBlock * getCurrentBB () const
void addGlobalBlackHoleAddrEdge (NodeID node, const ConstantExpr *int2Ptrce)
 Add global black hole Address edge.
NodeID addNullPtrNode ()
 Add NullPtr PAGNode.
NodeID getGepValVar (const Value *val, const AccessPath &ap, const SVFType *elementType)
NodeID getDirectAccessFieldZeroValVar (const Value *ptr, const Type *accessTy)
void setCurrentBBAndValueForPAGEdge (PAGEdge *edge)
void addBlackHoleAddrEdge (NodeID node)
AddrStmt * addAddrEdge (NodeID src, NodeID dst)
 Add Address edge.
AddrStmt * addAddrWithStackArraySz (NodeID src, NodeID dst, llvm::AllocaInst &inst)
 Add Address edge from allocinst with arraysize like "%4 = alloca i8, i64 3".
AddrStmt * addAddrWithHeapSz (NodeID src, NodeID dst, const CallBase *cs)
 Add Address edge from ext call with args like "%5 = call i8* @malloc(i64 noundef 5)".
CopyStmt * addCopyEdge (NodeID src, NodeID dst, CopyStmt::CopyKind kind)
CopyStmt::CopyKind getCopyKind (const Value *val)
void addPhiStmt (NodeID res, NodeID opnd, const ICFGNode *pred)
 Add Copy edge.
void addSelectStmt (NodeID res, NodeID op1, NodeID op2, NodeID cond)
 Add SelectStmt.
void addCmpEdge (NodeID op1, NodeID op2, NodeID dst, u32_t predict)
 Add Copy edge.
void addBinaryOPEdge (NodeID op1, NodeID op2, NodeID dst, u32_t opcode)
 Add Copy edge.
void addUnaryOPEdge (NodeID src, NodeID dst, u32_t opcode)
 Add Unary edge.
void addBranchStmt (NodeID br, NodeID cond, const BranchStmt::SuccAndCondPairVec &succs)
 Add Branch statement.
void addLoadEdge (NodeID src, NodeID dst)
 Add Load edge.
void addStoreEdge (NodeID src, NodeID dst)
 Add Store edge.
void addCallEdge (NodeID src, NodeID dst, const CallICFGNode *cs, const FunEntryICFGNode *entry)
 Add Call edge.
void addRetEdge (NodeID src, NodeID dst, const CallICFGNode *cs, const FunExitICFGNode *exit)
 Add Return edge.
void addGepEdge (NodeID src, NodeID dst, const AccessPath &ap, bool constGep)
 Add Gep edge.
void addNormalGepEdge (NodeID src, NodeID dst, const AccessPath &ap)
 Add Offset(Gep) edge.
void addVariantGepEdge (NodeID src, NodeID dst, const AccessPath &ap)
 Add Variant(Gep) edge.
void addThreadForkEdge (NodeID src, NodeID dst, const CallICFGNode *cs, const FunEntryICFGNode *entry)
 Add Thread fork edge for parameter passing.
void addThreadJoinEdge (NodeID src, NodeID dst, const CallICFGNode *cs, const FunExitICFGNode *exit)
 Add Thread join edge for parameter passing.
AccessPath getAccessPathFromBaseNode (NodeID nodeId)

Private Types

using AggregateField = std::vector<unsigned>
using AggregateFieldKey = std::pair<const Value*, AggregateField>
 Identify a field by its LLVM value and path, rather than by its type alone.
using AggregateReturnFields
 Field paths extracted from each callee's returned aggregate.

Private Member Functions

bool getAggregateFieldOperands (const AggregateFieldKey &field, std::vector< AggregateFieldKey > &operands)
 Describe one field definition without emitting any PAG statements.
bool getAggregateFieldNode (const Value *aggregate, const AggregateField &indices, NodeID &node)
void addExtractedFieldCopy (Instruction &inst)
void initialiseAggregateReturns ()
AggregateReturnFields discoverAggregateReturnFields ()
void createAggregateReturnParams (const Function *fun, const std::set< AggregateField > &fields, const SVFType *pointerType)
void createAggregateCallSlots (const Function *fun, const SVFType *pointerType)
void addAggregateCallFields (const CallInst *call)
void addAggregateReturnStores (ReturnInst &inst)
LLVMModuleSet * llvmModuleSet ()

Static Private Member Functions

static std::optional< AggregateFieldKey > getExtractedField (const Instruction &inst)
 Decode a pointer extraction; unsupported instructions have no field.

Private Attributes

PAG * pag
const SVFBasicBlock * curBB
 Current basic block during PAG construction when visiting the module.
const Value * curVal
 Current Value during PAG construction when visiting the module.
Map< AggregateFieldKey, NodeID > aggregateFieldNodes
 Reuse the same scalar PAG node for repeated requests for a field.
Map< const Function *, std::map< AggregateField, NodeID > > aggregateReturnParams
 Output parameters of each modeled callee, in field-path order.
Map< const CallInst *, std::map< AggregateField, NodeID > > aggregateCallArgs

Friends

class GraphDBSVFIRBuilder

Detailed Description

PAG Builder to create SVF variables and statements and PAG

Definition at line 49 of file PAGBuilder.h.

Member Typedef Documentation

◆ AggregateField

using SVF::PAGBuilder::AggregateField = std::vector<unsigned>
private

Zero-based indices through nested structs, arrays or fixed vector lanes. For {i32, {ptr, ptr}}, {1, 0} selects the first pointer in the inner struct. An empty path denotes a scalar pointer leaf during dependency traversal.

Definition at line 62 of file PAGBuilder.h.

◆ AggregateFieldKey

using SVF::PAGBuilder::AggregateFieldKey = std::pair<const Value*, AggregateField>
private

Identify a field by its LLVM value and path, rather than by its type alone.

Definition at line 64 of file PAGBuilder.h.

◆ AggregateReturnFields

Initial value:
std::unordered_map< Key, Value, Hash, KeyEqual, Allocator > Map
Definition GeneralType.h:56

Field paths extracted from each callee's returned aggregate.

Definition at line 138 of file PAGBuilder.h.

Constructor & Destructor Documentation

◆ PAGBuilder()

SVF::PAGBuilder::PAGBuilder ( )
inline

Constructor.

Definition at line 153 of file PAGBuilder.h.

153 : pag(PAG::getPAG()), curBB(nullptr),curVal(nullptr)
154 {
155 }
const SVFBasicBlock * curBB
Current basic block during PAG construction when visiting the module.
Definition PAGBuilder.h:55
const Value * curVal
Current Value during PAG construction when visiting the module.
Definition PAGBuilder.h:56
static PAG * getPAG(bool buildFromFile=false)
Singleton design here to make sure we only have one instance during any analysis.
Definition PAG.h:121

◆ ~PAGBuilder()

virtual SVF::PAGBuilder::~PAGBuilder ( )
inlinevirtual

Destructor.

Definition at line 157 of file PAGBuilder.h.

158 {
159 }

Member Function Documentation

◆ addAddrEdge()

AddrStmt * SVF::PAGBuilder::addAddrEdge ( NodeID src,
NodeID dst )
inlineprotected

Add Address edge.

Definition at line 406 of file PAGBuilder.h.

407 {
408 if(AddrStmt *edge = pag->addAddrStmt(src, dst))
409 {
411 return edge;
412 }
413 return nullptr;
414 }
void setCurrentBBAndValueForPAGEdge(PAGEdge *edge)

◆ addAddrWithHeapSz()

AddrStmt * SVF::PAGBuilder::addAddrWithHeapSz ( NodeID src,
NodeID dst,
const CallBase * cs )
inlineprotected

Add Address edge from ext call with args like "%5 = call i8* @malloc(i64 noundef 5)".

Definition at line 428 of file PAGBuilder.h.

429 {
430 // get name of called function
431 AddrStmt* edge = addAddrEdge(src, dst);
432
433 llvm::Function* calledFunc = cs->getCalledFunction();
434 std::string functionName;
435 if (calledFunc)
436 {
437 functionName = calledFunc->getName().str();
438 }
439 else
440 {
441 SVFUtil::writeWrnMsg("not support indirect call to add AddrStmt.\n");
442 }
443 if (functionName == "malloc")
444 {
445 if (cs->arg_size() > 0)
446 {
447 const llvm::Value* val = cs->getArgOperand(0);
448 edge->addArrSize(pag->getGNode(getValueNode(val)));
449 }
450 }
451 // Check if the function called is 'calloc' and process its arguments.
452 // e.g. "%5 = call i8* @calloc(1, 8)", edge should add two SVFValue (1 and 8)
453 else if (functionName == "calloc")
454 {
455 if (cs->arg_size() > 1)
456 {
457 edge->addArrSize(
458 pag->getGNode(getValueNode(cs->getArgOperand(0))));
459 edge->addArrSize(
460 pag->getGNode(getValueNode(cs->getArgOperand(1))));
461 }
462 }
463 else
464 {
465 if (cs->arg_size() > 0)
466 {
467 const llvm::Value* val = cs->getArgOperand(0);
468 edge->addArrSize(pag->getGNode(getValueNode(val)));
469 }
470 }
471 return edge;
472 }
AddrStmt * addAddrEdge(NodeID src, NodeID dst)
Add Address edge.
Definition PAGBuilder.h:406
NodeID getValueNode(const Value *V)
Get different kinds of node.
Definition PAGBuilder.h:193
void writeWrnMsg(const std::string &msg)
Writes a message run through wrnMsg.
Definition SVFUtil.cpp:88

◆ addAddrWithStackArraySz()

AddrStmt * SVF::PAGBuilder::addAddrWithStackArraySz ( NodeID src,
NodeID dst,
llvm::AllocaInst & inst )
inlineprotected

Add Address edge from allocinst with arraysize like "%4 = alloca i8, i64 3".

Definition at line 417 of file PAGBuilder.h.

418 {
419 AddrStmt* edge = addAddrEdge(src, dst);
420 if (inst.getArraySize())
421 {
422 edge->addArrSize(pag->getGNode(getValueNode(inst.getArraySize())));
423 }
424 return edge;
425 }

◆ addAggregateCallFields()

void PAGBuilder::addAggregateCallFields ( const CallInst * call)
private

Append the slot addresses of call as actual output arguments and pass each to the callee's output parameter. createAggregateCallSlots has already created the slots, their addresses and the snapshot loads.

Definition at line 1727 of file PAGBuilder.cpp.

1728{
1729 auto found = aggregateCallArgs.find(call);
1730 if (found == aggregateCallArgs.end())
1731 return;
1732 CallICFGNode* callNode = llvmModuleSet()->getCallICFGNode(call);
1733 const FunObjVar* callee = llvmModuleSet()->getFunObjVar(call->getCalledFunction());
1734 FunEntryICFGNode* entry = pag->getICFG()->getFunEntryICFGNode(callee);
1735 const auto& params = aggregateReturnParams.at(call->getCalledFunction());
1736 for (const auto& arg : found->second)
1737 {
1738 pag->addCallSiteArgs(callNode, pag->getValVar(arg.second));
1739 addCallEdge(arg.second, params.at(arg.first), callNode, entry);
1740 }
1741}
const FunObjVar * getFunObjVar(const Function *fun) const
Definition LLVMModule.h:274
CallICFGNode * getCallICFGNode(const Instruction *cs)
get a call node
void addCallEdge(NodeID src, NodeID dst, const CallICFGNode *cs, const FunEntryICFGNode *entry)
Add Call edge.
Definition PAGBuilder.h:577
Map< const CallInst *, std::map< AggregateField, NodeID > > aggregateCallArgs
Definition PAGBuilder.h:135
Map< const Function *, std::map< AggregateField, NodeID > > aggregateReturnParams
Output parameters of each modeled callee, in field-path order.
Definition PAGBuilder.h:131
LLVMModuleSet * llvmModuleSet()
Definition PAGBuilder.h:623

◆ addAggregateReturnStores()

void PAGBuilder::addAggregateReturnStores ( ReturnInst & inst)
private

Store shared field nodes into the callee's output parameters. An unsupported field gets its own fallback; supported siblings keep their shared definitions.

Definition at line 1745 of file PAGBuilder.cpp.

1746{
1747 auto found = aggregateReturnParams.find(inst.getFunction());
1748 if (found == aggregateReturnParams.end() || !inst.getReturnValue())
1749 return;
1750 // Keep each store on its own return path, before the shared function exit.
1751 ICFGNode* location = llvmModuleSet()->getICFGNode(&inst);
1752 for (const auto& field : found->second)
1753 {
1754 NodeID value;
1755 if (!getAggregateFieldNode(inst.getReturnValue(), field.first, value))
1756 {
1757 value = pag->addDummyValNode(NodeIDAllocator::get()->allocateValueId(), location);
1758 addBlackHoleAddrEdge(value);
1759 }
1760 addStoreEdge(value, field.second);
1761 }
1762}
ICFGNode * getICFGNode(const Instruction *inst)
Get a basic block ICFGNode.
static NodeIDAllocator * get(void)
Return (singleton) allocator.
void addStoreEdge(NodeID src, NodeID dst)
Add Store edge.
Definition PAGBuilder.h:565
bool getAggregateFieldNode(const Value *aggregate, const AggregateField &indices, NodeID &node)
void addBlackHoleAddrEdge(NodeID node)
Definition PAGBuilder.h:399
u32_t NodeID
Definition GeneralType.h:76

◆ addBinaryOPEdge()

void SVF::PAGBuilder::addBinaryOPEdge ( NodeID op1,
NodeID op2,
NodeID dst,
u32_t opcode )
inlineprotected

Add Copy edge.

Definition at line 541 of file PAGBuilder.h.

542 {
543 if(BinaryOPStmt *edge = pag->addBinaryOPStmt(op1, op2, dst, opcode))
545 }

◆ addBlackHoleAddrEdge()

void SVF::PAGBuilder::addBlackHoleAddrEdge ( NodeID node)
inlineprotected

Definition at line 399 of file PAGBuilder.h.

400 {
401 if(PAGEdge *edge = pag->addBlackHoleAddrStmt(node))
403 }
SVFStmt PAGEdge
Definition PAGBase.h:41

◆ addBranchStmt()

void SVF::PAGBuilder::addBranchStmt ( NodeID br,
NodeID cond,
const BranchStmt::SuccAndCondPairVec & succs )
inlineprotected

Add Branch statement.

Definition at line 553 of file PAGBuilder.h.

554 {
555 if(BranchStmt *edge = pag->addBranchStmt(br, cond, succs))
557 }

◆ addCallEdge()

void SVF::PAGBuilder::addCallEdge ( NodeID src,
NodeID dst,
const CallICFGNode * cs,
const FunEntryICFGNode * entry )
inlineprotected

Add Call edge.

Definition at line 577 of file PAGBuilder.h.

578 {
579 if (CallPE* edge = pag->addCallPE(src, dst, cs, entry))
581 }

◆ addCmpEdge()

void SVF::PAGBuilder::addCmpEdge ( NodeID op1,
NodeID op2,
NodeID dst,
u32_t predict )
inlineprotected

Add Copy edge.

Definition at line 535 of file PAGBuilder.h.

536 {
537 if(CmpStmt *edge = pag->addCmpStmt(op1, op2, dst, predict))
539 }

◆ addComplexConsForExt()

void PAGBuilder::addComplexConsForExt ( Value * D,
Value * S,
const Value * szValue )
protectedvirtual

Add the load/store constraints and temp. nodes for the complex constraint *D = *S (where D/S may point to structs).

If sz is 0, we will add edges for all fields.

Definition at line 318 of file PAGExtAPI.cpp.

319{
320 assert(D && S);
321 NodeID vnD= getValueNode(D), vnS= getValueNode(S);
322 if(!vnD || !vnS)
323 return;
324
325 std::vector<AccessPath> fields;
326
327 //Get the max possible size of the copy, unless it was provided.
328 std::vector<AccessPath> srcFields;
329 std::vector<AccessPath> dstFields;
330 const Type* stype = getBaseTypeAndFlattenedFields(S, srcFields, szValue);
331 const Type* dtype = getBaseTypeAndFlattenedFields(D, dstFields, szValue);
332 if(srcFields.size() > dstFields.size())
333 fields = dstFields;
334 else
335 fields = srcFields;
336
338 u32_t sz = fields.size();
339
340 if (fields.size() == 1 && (LLVMUtil::isConstDataOrAggData(D) || LLVMUtil::isConstDataOrAggData(S)))
341 {
342 NodeID dummy = pag->addDummyValNode();
343 addLoadEdge(vnD,dummy);
344 addStoreEdge(dummy,vnS);
345 return;
346 }
347
348 const Value* dstBase = getBaseValueForExtArg(D);
349 const Value* srcBase = getBaseValueForExtArg(S);
350 Value* dstFieldBase = LLVMUtil::isObject(dstBase) ? const_cast<Value*>(dstBase) : D;
351 Value* srcFieldBase = LLVMUtil::isObject(srcBase) ? const_cast<Value*>(srcBase) : S;
352 const Type* dstLayoutType = getMemcpyLayoutType(dstBase, dtype);
353 const Type* srcLayoutType = getMemcpyLayoutType(srcBase, stype);
354 const bool hasRemappedGlobalBase =
355 (dstFieldBase != D && SVFUtil::isa<GlobalVariable>(dstFieldBase)) ||
356 (srcFieldBase != S && SVFUtil::isa<GlobalVariable>(srcFieldBase));
357 const bool useByteLayoutMemcpy =
358 hasRemappedGlobalBase || (dstLayoutType != dtype) || (srcLayoutType != stype);
359 if (useByteLayoutMemcpy)
360 {
361 const SVFType* dstSVFType = llvmModuleSet()->getSVFType(dstLayoutType);
362 const SVFType* srcSVFType = llvmModuleSet()->getSVFType(srcLayoutType);
363 std::vector<MemcpyField> dstMemcpyFields = getMemcpyFields(D, dstLayoutType, dstSVFType);
364 std::vector<MemcpyField> srcMemcpyFields = getMemcpyFields(S, srcLayoutType, srcSVFType);
365 if (!dstMemcpyFields.empty() && !srcMemcpyFields.empty())
366 {
367 std::unordered_map<APOffset, MemcpyField> srcFieldsByByteOffset;
368 for (const auto& field : srcMemcpyFields)
369 srcFieldsByByteOffset.emplace(field.byteOffset, field);
370
371 const DataLayout& dl = llvmModuleSet()->getMainLLVMModule()->getDataLayout();
372 APOffset copyBytes = std::min<APOffset>(
373 static_cast<APOffset>(dl.getTypeAllocSize(const_cast<Type*>(dstLayoutType))),
374 static_cast<APOffset>(dl.getTypeAllocSize(const_cast<Type*>(srcLayoutType))));
375 if (szValue && SVFUtil::isa<ConstantInt>(szValue))
376 {
378 copyBytes = std::min(copyBytes, static_cast<APOffset>(szIntVal.first));
379 }
380
381 for (const auto& dstField : dstMemcpyFields)
382 {
383 if (dstField.byteOffset >= copyBytes)
384 continue;
385 auto it = srcFieldsByByteOffset.find(dstField.byteOffset);
386 if (it == srcFieldsByByteOffset.end())
387 continue;
388
389 NodeID dField = getGepValVar(dstFieldBase, dstField.accessPath, dstField.elementType);
390 NodeID sField = getGepValVar(srcFieldBase, it->second.accessPath, it->second.elementType);
391 NodeID dummy = pag->addDummyValNode();
392 addLoadEdge(sField, dummy);
393 addStoreEdge(dummy, dField);
394 }
395 return;
396 }
397 }
398
399 //For each field (i), add (Ti = *S + i) and (*D + i = Ti).
400 for (u32_t index = 0; index < sz; index++)
401 {
402 LLVMModuleSet* llvmmodule = LLVMModuleSet::getLLVMModuleSet();
403 const SVFType* dElementType = pag->getFlatternedElemType(llvmmodule->getSVFType(dtype),
404 fields[index].getConstantStructFldIdx());
405 const SVFType* sElementType = pag->getFlatternedElemType(llvmmodule->getSVFType(stype),
406 fields[index].getConstantStructFldIdx());
407 NodeID dField = getGepValVar(D,fields[index],dElementType);
408 NodeID sField = getGepValVar(S,fields[index],sElementType);
409 NodeID dummy = pag->addDummyValNode();
410 addLoadEdge(sField,dummy);
411 addStoreEdge(dummy,dField);
412 }
413}
int index
Definition cJSON.h:170
Module * getMainLLVMModule() const
Definition LLVMModule.h:373
static LLVMModuleSet * getLLVMModuleSet()
Definition LLVMModule.h:137
SVFType * getSVFType(const Type *T)
Get or create SVFType and typeinfo.
virtual const Type * getBaseTypeAndFlattenedFields(const Value *V, std::vector< AccessPath > &fields, const Value *szValue)
Handle external call.
NodeID getGepValVar(const Value *val, const AccessPath &ap, const SVFType *elementType)
void addLoadEdge(NodeID src, NodeID dst)
Add Load edge.
Definition PAGBuilder.h:559
const Value * getBaseValueForExtArg(const Value *V)
Get the base value of (i8* src and i8* dst) for external argument (e.g. memcpy(i8* dst,...
std::pair< s64_t, u64_t > getIntegerValue(const ConstantInt *intValue)
Definition LLVMUtil.h:95
bool isConstDataOrAggData(const Value *val)
Return true if the value refers to constant data, e.g., i32 0.
Definition LLVMUtil.h:397
bool isObject(const Value *ref)
Return true if this value refers to a object.
Definition LLVMUtil.cpp:61
std::enable_if_t<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type > cast(const Y &Val)
Definition Casting.h:360
LLVM_NODISCARD bool isa(const Y &Val)
Definition Casting.h:241
llvm::DataLayout DataLayout
Definition BasicTypes.h:106
llvm::Type Type
Definition BasicTypes.h:81
s64_t APOffset
Definition GeneralType.h:80
llvm::Value Value
LLVM Basic classes.
Definition BasicTypes.h:80
unsigned u32_t
Definition GeneralType.h:67

◆ addCopyEdge()

CopyStmt * SVF::PAGBuilder::addCopyEdge ( NodeID src,
NodeID dst,
CopyStmt::CopyKind kind )
inlineprotected

Definition at line 474 of file PAGBuilder.h.

475 {
476 if(CopyStmt *edge = pag->addCopyStmt(src, dst, kind))
477 {
479 return edge;
480 }
481 return nullptr;
482 }

◆ addEdge()

void SVF::PAGBuilder::addEdge ( NodeID src,
NodeID dst,
SVFStmt::PEDGEK kind,
APOffset offset = 0,
Instruction * cs = nullptr )

◆ addExtractedFieldCopy()

void PAGBuilder::addExtractedFieldCopy ( Instruction & inst)
private

Copy an extracted pointer from its shared field definition. Unsupported fields keep the existing black-hole fallback.

Definition at line 1793 of file PAGBuilder.cpp.

1794{
1795 NodeID dst = getValueNode(&inst);
1796 const auto field = getExtractedField(inst);
1797 NodeID src;
1798 if (field && getAggregateFieldNode(field->first, field->second, src))
1799 addCopyEdge(src, dst, CopyStmt::COPYVAL);
1800 else
1802}
static std::optional< AggregateFieldKey > getExtractedField(const Instruction &inst)
Decode a pointer extraction; unsupported instructions have no field.
CopyStmt * addCopyEdge(NodeID src, NodeID dst, CopyStmt::CopyKind kind)
Definition PAGBuilder.h:474

◆ addGepEdge()

void SVF::PAGBuilder::addGepEdge ( NodeID src,
NodeID dst,
const AccessPath & ap,
bool constGep )
inlineprotected

Add Gep edge.

Definition at line 589 of file PAGBuilder.h.

590 {
591 if (GepStmt* edge = pag->addGepStmt(src, dst, ap, constGep))
593 }

◆ addGlobalBlackHoleAddrEdge()

void SVF::PAGBuilder::addGlobalBlackHoleAddrEdge ( NodeID node,
const ConstantExpr * int2Ptrce )
inlineprotected

Add global black hole Address edge.

Definition at line 372 of file PAGBuilder.h.

373 {
374 const Value* cval = getCurrentValue();
375 const SVFBasicBlock* cbb = getCurrentBB();
376 setCurrentLocation(int2Ptrce,(SVFBasicBlock*) nullptr);
378 setCurrentLocation(cval,cbb);
379 }
const SVFBasicBlock * getCurrentBB() const
Definition PAGBuilder.h:366
const Value * getCurrentValue() const
Definition PAGBuilder.h:362
void setCurrentLocation(const Value *val, const BasicBlock *bb)
Set current basic block in order to keep track of control flow information.
Definition PAGBuilder.h:352

◆ addLoadEdge()

void SVF::PAGBuilder::addLoadEdge ( NodeID src,
NodeID dst )
inlineprotected

Add Load edge.

Definition at line 559 of file PAGBuilder.h.

560 {
561 if(LoadStmt *edge = pag->addLoadStmt(src, dst))
563 }

◆ addNormalGepEdge()

void SVF::PAGBuilder::addNormalGepEdge ( NodeID src,
NodeID dst,
const AccessPath & ap )
inlineprotected

Add Offset(Gep) edge.

Definition at line 595 of file PAGBuilder.h.

596 {
597 if (GepStmt* edge = pag->addNormalGepStmt(src, dst, ap))
599 }

◆ addNullPtrNode()

NodeID SVF::PAGBuilder::addNullPtrNode ( )
inlineprotected

Add NullPtr PAGNode.

Definition at line 382 of file PAGBuilder.h.

383 {
385 ConstantPointerNull* constNull = ConstantPointerNull::get(PointerType::getUnqual(cxt));
386 NodeID nullPtr = pag->addConstantNullPtrValNode(pag->getNullPtr(), nullptr, llvmModuleSet()->getSVFType(constNull->getType()));
387 llvmModuleSet()->addToSVFVar2LLVMValueMap(constNull, pag->getGNode(pag->getNullPtr()));
388 setCurrentLocation(constNull, (SVFBasicBlock*) nullptr);
389 addBlackHoleAddrEdge(pag->getBlkPtr());
390 return nullPtr;
391 }
void addToSVFVar2LLVMValueMap(const Value *val, SVFValue *svfBaseNode)
LLVMContext & getContext() const
Definition LLVMModule.h:393
llvm::ConstantPointerNull ConstantPointerNull
Definition BasicTypes.h:125
llvm::LLVMContext LLVMContext
Definition BasicTypes.h:72

◆ addPhiStmt()

void SVF::PAGBuilder::addPhiStmt ( NodeID res,
NodeID opnd,
const ICFGNode * pred )
inlineprotected

Add Copy edge.

If we already added this phi node, then skip this adding

Definition at line 522 of file PAGBuilder.h.

523 {
525 if(PhiStmt *edge = pag->addPhiStmt(res,opnd,pred))
527 }

◆ addRetEdge()

void SVF::PAGBuilder::addRetEdge ( NodeID src,
NodeID dst,
const CallICFGNode * cs,
const FunExitICFGNode * exit )
inlineprotected

Add Return edge.

Definition at line 583 of file PAGBuilder.h.

584 {
585 if (RetPE* edge = pag->addRetPE(src, dst, cs, exit))
587 }

◆ addSelectStmt()

void SVF::PAGBuilder::addSelectStmt ( NodeID res,
NodeID op1,
NodeID op2,
NodeID cond )
inlineprotected

Add SelectStmt.

Definition at line 529 of file PAGBuilder.h.

530 {
531 if(SelectStmt *edge = pag->addSelectStmt(res,op1,op2,cond))
533 }

◆ addStoreEdge()

void SVF::PAGBuilder::addStoreEdge ( NodeID src,
NodeID dst )
inlineprotected

Add Store edge.

Definition at line 565 of file PAGBuilder.h.

566 {
567 ICFGNode* node;
569 node = llvmModuleSet()->getICFGNode(
571 else
572 node = nullptr;
573 if (StoreStmt* edge = pag->addStoreStmt(src, dst, node))
575 }
LLVM_NODISCARD std::enable_if_t<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type > dyn_cast(const Y &Val)
Definition Casting.h:405
llvm::Instruction Instruction
Definition BasicTypes.h:85

◆ addThreadForkEdge()

void SVF::PAGBuilder::addThreadForkEdge ( NodeID src,
NodeID dst,
const CallICFGNode * cs,
const FunEntryICFGNode * entry )
inlineprotected

Add Thread fork edge for parameter passing.

Definition at line 607 of file PAGBuilder.h.

608 {
609 if (TDForkPE* edge = pag->addThreadForkPE(src, dst, cs, entry))
611 }

◆ addThreadJoinEdge()

void SVF::PAGBuilder::addThreadJoinEdge ( NodeID src,
NodeID dst,
const CallICFGNode * cs,
const FunExitICFGNode * exit )
inlineprotected

Add Thread join edge for parameter passing.

Definition at line 613 of file PAGBuilder.h.

614 {
615 if (TDJoinPE* edge = pag->addThreadJoinPE(src, dst, cs, exit))
617 }

◆ addUnaryOPEdge()

void SVF::PAGBuilder::addUnaryOPEdge ( NodeID src,
NodeID dst,
u32_t opcode )
inlineprotected

Add Unary edge.

Definition at line 547 of file PAGBuilder.h.

548 {
549 if(UnaryOPStmt *edge = pag->addUnaryOPStmt(src, dst, opcode))
551 }

◆ addVariantGepEdge()

void SVF::PAGBuilder::addVariantGepEdge ( NodeID src,
NodeID dst,
const AccessPath & ap )
inlineprotected

Add Variant(Gep) edge.

Definition at line 601 of file PAGBuilder.h.

602 {
603 if (GepStmt* edge = pag->addVariantGepStmt(src, dst, ap))
605 }

◆ build()

PAG * PAGBuilder::build ( )
virtual

Start building PAG here.

Start building PAG here

build icfg

initial external library information initial PAG nodes

initial PAG edges: // handle globals

build callgraph

handle functions

collect return node of function fun

Return PAG node will not be created for function which can not reach the return instruction due to call to abort(), exit(), etc. In 176.gcc of SPEC 2000, function build_objc_string() from c-lang.c shows an example when fun.doesNotReturn() evaluates to TRUE because of abort().

To be noted, we do not record arguments which are in declared function without body TODO: what about external functions with PAG imported by commandline?

Definition at line 55 of file PAGBuilder.cpp.

56{
57 double startTime = SVFStat::getClk(true);
58
59 DBOUT(DGENERAL, outs() << pasMsg("\t Building PAG ...\n"));
60
61 // If the PAG has been built before, then we return the unique PAG of the program
62 if(pag->getNodeNumAfterPAGBuild() > 1)
63 return pag;
64
65
67
69 ICFGBuilder icfgbuilder;
70 pag->icfg = icfgbuilder.build();
71
80
81
82
84 CallGraphBuilder callGraphBuilder;
85 std::vector<const FunObjVar*> funset;
86 for (const auto& item: llvmModuleSet()->getFunctionSet())
87 {
88 funset.push_back(llvmModuleSet()->getFunObjVar(item));
89 }
90 pag->callGraph = callGraphBuilder.buildPAGCallGraph(funset);
91
92 CHGraph* chg = new CHGraph();
93 CHGBuilder chgbuilder(chg);
94 chgbuilder.buildCHG();
95 pag->setCHG(chg);
96
98 for (Module& M : llvmModuleSet()->getLLVMModules())
99 {
100 for (Module::const_iterator F = M.begin(), E = M.end(); F != E; ++F)
101 {
102 const Function& fun = *F;
103 const FunObjVar* svffun = llvmModuleSet()->getFunObjVar(&fun);
105 if(!fun.isDeclaration())
106 {
112 if (fun.doesNotReturn() == false &&
113 fun.getReturnType()->isVoidTy() == false)
114 {
115 pag->addFunRet(svffun,
116 pag->getValVar(pag->getReturnNode(svffun)));
117 }
118
121 for (Function::const_arg_iterator I = fun.arg_begin(), E = fun.arg_end();
122 I != E; ++I)
123 {
124 setCurrentLocation(&*I,&fun.getEntryBlock());
125 NodeID argValNodeId = llvmModuleSet()->getValueNode(&*I);
126 // if this is the function does not have caller (e.g. main)
127 // or a dead function, shall we create a black hole address edge for it?
128 // it is (1) too conservative, and (2) make FormalParmVFGNode defined at blackhole address PAGEdge.
129 // if(SVFUtil::ArgInNoCallerFunction(&*I)) {
130 // if(I->getType()->isPointerTy())
131 // addBlackHoleAddrEdge(argValNodeId);
132 //}
133 pag->addFunArgs(svffun,pag->getValVar(argValNodeId));
134 }
135 auto returns = aggregateReturnParams.find(&fun);
136 if (returns != aggregateReturnParams.end())
137 for (const auto& field : returns->second)
138 pag->addFunArgs(svffun, pag->getValVar(field.second));
139 }
140 for (Function::const_iterator bit = fun.begin(), ebit = fun.end();
141 bit != ebit; ++bit)
142 {
143 const BasicBlock& bb = *bit;
144 for (BasicBlock::const_iterator it = bb.begin(), eit = bb.end();
145 it != eit; ++it)
146 {
147 const Instruction& inst = *it;
148 setCurrentLocation(&inst,&bb);
149 visit(const_cast<Instruction&>(inst));
150 }
151 }
152 }
153 }
154
155 sanityCheck();
156
157 pag->initialiseCandidatePointers();
158
159 pag->setNodeNumAfterPAGBuild(pag->getTotalNodeNum());
160
161 // dump PAG
163 pag->dump("pag_initial");
164
165 // print to command line of the PAG graph
166 if (Options::PAGPrint())
167 pag->print();
168
169 // dump ICFG
170 if (Options::DumpICFG())
171 pag->getICFG()->dump("icfg_initial");
172
174 {
175 LLVMLoopAnalysis loopAnalysis;
176 loopAnalysis.build(pag->getICFG());
177 }
178
179 // dump PAG as JSON
180 if (!Options::DumpJson().empty())
181 {
182 assert(false && "please implement PAGWriter::writeJsonToPath");
183 }
184
185 double endTime = SVFStat::getClk(true);
186 SVFStat::timeOfBuildingPAG = (endTime - startTime) / TIMEINTERVAL;
187
188 return pag;
189}
#define DBOUT(TYPE, X)
LLVM debug macros, define type of your DBUG model of each pass.
Definition SVFType.h:576
#define TIMEINTERVAL
Definition SVFType.h:604
#define DGENERAL
Definition SVFType.h:582
cJSON * item
Definition cJSON.h:222
CallGraph * buildPAGCallGraph(const std::vector< const FunObjVar * > &funset)
Buidl PAG callgraoh.
virtual void build(ICFG *icfg)
Start from here.
NodeID getValueNode(const Value *V)
static const Option< bool > PAGDotGraph
Definition Options.h:119
static const Option< std::string > DumpJson
Definition Options.h:122
static const Option< bool > PAGPrint
Definition Options.h:125
static const Option< bool > LoopAnalysis
Definition Options.h:234
static const Option< bool > DumpICFG
Definition Options.h:121
void initialiseNodes()
Initialize nodes and edges.
void sanityCheck()
Sanity check for PAG.
void initialiseAggregateReturns()
void visitGlobal()
Handle globals including (global variable and functions).
void createFunObjVars()
static double timeOfBuildingPAG
Definition SVFStat.h:98
static double getClk(bool mark=false)
Definition SVFStat.cpp:52
const FunObjVar * getFunObjVar(const std::string &name)
Definition LLVMUtil.cpp:437
std::string pasMsg(const std::string &msg)
Print each pass/phase message by converting a string into blue string output.
Definition SVFUtil.cpp:121
std::ostream & outs()
Overwrite llvm::outs().
Definition SVFUtil.h:58
llvm::BasicBlock BasicBlock
Definition BasicTypes.h:84
llvm::Function Function
Definition BasicTypes.h:83
llvm::Module Module
Definition BasicTypes.h:82

◆ computeGepOffset()

bool PAGBuilder::computeGepOffset ( const User * V,
AccessPath & ap )
protected

Compute offset of a gep instruction or gep constant expression.

Return the object node offset according to GEP insn (V). Given a gep edge p = q + i, if "i" is a constant then we return its offset size otherwise if "i" is a variable determined by runtime, then it is a variant offset Return TRUE if the offset of this GEP insn is a constant.

Definition at line 632 of file PAGBuilder.cpp.

633{
634 assert(V);
635
636 const llvm::GEPOperator *gepOp = SVFUtil::dyn_cast<const llvm::GEPOperator>(V);
637 DataLayout * dataLayout = getDataLayout(llvmModuleSet()->getMainLLVMModule());
638 llvm::APInt byteOffset(dataLayout->getIndexSizeInBits(gepOp->getPointerAddressSpace()),0,true);
639 if(gepOp && dataLayout && gepOp->accumulateConstantOffset(*dataLayout,byteOffset))
640 {
641 //s32_t bo = byteOffset.getSExtValue();
642 }
643
644 bool isConst = true;
645
646 bool prevPtrOperand = false;
648 gi != ge; ++gi)
649 {
650 const Type* gepTy = *gi;
651 const SVFType* svfGepTy = llvmModuleSet()->getSVFType(gepTy);
652
653 assert((prevPtrOperand && svfGepTy->isPointerTy()) == false &&
654 "Expect no more than one gep operand to be of a pointer type");
655 if(!prevPtrOperand && svfGepTy->isPointerTy()) prevPtrOperand = true;
656 const Value* offsetVal = gi.getOperand();
657 assert(gepTy != offsetVal->getType() && "iteration and operand have the same type?");
658
659 const ArrayType* inferredPtrArrayTy = nullptr;
660 const SVFType* idxGepTy = svfGepTy;
661 if (svfGepTy->isPointerTy() && gepOp->getSourceElementType()->isSingleValueType())
662 {
663 const Type* baseObjType =
664 LLVMModuleSet::getLLVMModuleSet()->getTypeInference()->inferObjType(gepOp->getPointerOperand());
665 if (const auto* arrTy = SVFUtil::dyn_cast<ArrayType>(baseObjType))
666 {
667 if (arrTy->getElementType()->isPointerTy())
668 {
669 inferredPtrArrayTy = arrTy;
670 idxGepTy = llvmModuleSet()->getSVFType(arrTy);
671 }
672 }
673 }
674
675 ap.addOffsetVarAndGepTypePair(getPAG()->getValVar(llvmModuleSet()->getValueNode(offsetVal)), idxGepTy);
676
677 //The int value of the current index operand
678 const ConstantInt* op = SVFUtil::dyn_cast<ConstantInt>(offsetVal);
679
680 // if Options::ModelConsts() is disabled. We will treat whole array as one,
681 // but we can distinguish different field of an array of struct, e.g. s[1].f1 is different from s[0].f2
682 if(const ArrayType* arrTy = SVFUtil::dyn_cast<ArrayType>(gepTy))
683 {
684 if (!Options::ModelArrays() && arrTy->getElementType()->isPointerTy())
685 continue;
686 if(!op || (arrTy->getArrayNumElements() <= (u32_t)LLVMUtil::getIntegerValue(op).first))
687 continue;
689 u32_t offset = pag->getFlattenedElemIdx(llvmModuleSet()->getSVFType(arrTy), idx);
691 }
692 else if (const StructType *ST = SVFUtil::dyn_cast<StructType>(gepTy))
693 {
694 assert(op && "non-const offset accessing a struct");
695 // guard against negative or out-of-bounds struct indices
696 // (e.g. rust hashbrown bucket back-offset: gep { ... }, ptr %p, i64 -1)
697 // a negative i64 wraps to a huge uint64_t that overflows u32_t,
698 // creating an invalid field index that severs points-to tracking
699 uint64_t rawIdx = LLVMUtil::getIntegerValue(op).first;
700 if (rawIdx >= ST->getNumElements())
701 {
702 isConst = false;
703 continue;
704 }
705 APOffset idx = (u32_t)rawIdx;
706 u32_t offset = pag->getFlattenedElemIdx(llvmModuleSet()->getSVFType(ST), idx);
708 }
709 else if (gepTy->isSingleValueType())
710 {
711 if (inferredPtrArrayTy)
712 {
713 if (!op || (inferredPtrArrayTy->getArrayNumElements() <= (u32_t)LLVMUtil::getIntegerValue(op).first))
714 continue;
716 u32_t offset = pag->getFlattenedElemIdx(llvmModuleSet()->getSVFType(inferredPtrArrayTy), idx);
718 continue;
719 }
720 // If it's a non-constant offset access
721 // If its point-to target is struct or array, it's likely an array accessing (%result = gep %struct.A* %a, i32 %non-const-index)
722 // If its point-to target is single value (pointer arithmetic), then it's a variant gep (%result = gep i8* %p, i32 %non-const-index)
723 if(!op && gepTy->isPointerTy() && gepOp->getSourceElementType()->isSingleValueType())
724 {
725 isConst = false;
726 }
727
728 // The actual index
729 //s32_t idx = op->getSExtValue();
730
731 // For pointer arithmetic we ignore the byte offset
732 // consider using inferFieldIdxFromByteOffset(geopOp,dataLayout,ap,idx)?
733 // ap.setFldIdx(ap.getConstantFieldIdx() + inferFieldIdxFromByteOffset(geopOp,idx));
734 }
735 }
736 return isConst;
737}
buffer offset
Definition cJSON.cpp:1113
APOffset getConstantStructFldIdx() const
Get methods.
Definition AccessPath.h:102
void setFldIdx(APOffset idx)
Definition AccessPath.h:106
bool addOffsetVarAndGepTypePair(const ValVar *var, const SVFType *gepIterType)
ObjTypeInference * getTypeInference()
const Type * inferObjType(const Value *var)
get or infer the type of the object pointed by the value
static Option< bool > ModelArrays
Definition Options.h:180
PAG * getPAG() const
Return PAG.
Definition PAGBuilder.h:165
bool isPointerTy() const
Definition SVFType.h:292
static DataLayout * getDataLayout(Module *mod)
Definition LLVMUtil.h:315
llvm::ArrayType ArrayType
Definition BasicTypes.h:93
llvm::StructType StructType
LLVM types.
Definition BasicTypes.h:92
llvm::bridge_gep_iterator bridge_gep_iterator
Definition BasicTypes.h:255
llvm::ConstantInt ConstantInt
Definition BasicTypes.h:123
bridge_gep_iterator bridge_gep_end(const User *GEP)
bridge_gep_iterator bridge_gep_begin(const User *GEP)

◆ createAggregateCallSlots()

void PAGBuilder::createAggregateCallSlots ( const Function * fun,
const SVFType * pointerType )
private

At every call to fun, create a slot, its address and its snapshot for each output parameter (obj, A and V in the aggregate return example). The address is defined at the call, and the snapshot is loaded at the instruction after the call.

Definition at line 1666 of file PAGBuilder.cpp.

1668{
1669 const auto& params = aggregateReturnParams.at(fun);
1670 // LLVM use-list order can change on bitcode reload. Order calls by
1671 // their ICFG IDs so each call receives the same slot IDs on readback.
1672 std::vector<const CallInst*> calls;
1673 for (const User* user : fun->users())
1674 calls.push_back(SVFUtil::cast<CallInst>(user));
1675 std::sort(calls.begin(), calls.end(), [this](const CallInst* lhs,
1676 const CallInst* rhs)
1677 {
1678 return llvmModuleSet()->getCallICFGNode(lhs)->getId() <
1679 llvmModuleSet()->getCallICFGNode(rhs)->getId();
1680 });
1681 const Value* savedValue = curVal;
1682 const SVFBasicBlock* savedBB = curBB;
1683 // Include calls with unused results to keep actual/formal lists aligned.
1684 for (const CallInst* call : calls)
1685 {
1686 std::vector<const Instruction*> next;
1688 assert(next.size() == 1 && "ordinary call must have one continuation");
1689 const Instruction* continuation = next.front();
1690 auto& args = aggregateCallArgs[call];
1691 ICFGNode* callNode = llvmModuleSet()->getCallICFGNode(call);
1692 ICFGNode* resumeNode = llvmModuleSet()->getICFGNode(continuation);
1693 for (const auto& param : params)
1694 {
1695 // DummyObjVar keeps the static slot nonlocal to the callee
1696 // in MemSSA. Later extracts read the SSA snapshot rather
1697 // than the reused slot contents.
1698 NodeID object = pag->addDummyObjNode(pointerType);
1699 pag->getAllFieldsObjVars(object).set(object);
1700 pag->getObjTypeInfo(object)->setNumOfElements(1);
1701 pag->getObjTypeInfo(object)->setByteSizeOfObj(
1702 pointerType->getByteSize());
1703 NodeID address = pag->addDummyValNode(
1704 NodeIDAllocator::get()->allocateValueId(), callNode);
1705 NodeID value = pag->addDummyValNode(
1706 NodeIDAllocator::get()->allocateValueId(), resumeNode);
1707 args.emplace(param.first, address);
1708 // Call fields use the same identity as local aggregate fields.
1709 assert(!aggregateFieldNodes.count({call, param.first}) &&
1710 "call field registered twice");
1711 aggregateFieldNodes.emplace(
1712 AggregateFieldKey{call, param.first}, value);
1713 setCurrentLocation(call, call->getParent());
1714 addAddrEdge(object, address);
1715 // Snapshots must precede field statements at the continuation,
1716 // even when LLVM block order differs from dominance order.
1717 setCurrentLocation(continuation, continuation->getParent());
1718 addLoadEdge(address, value);
1719 }
1720 }
1721 setCurrentLocation(savedValue, savedBB);
1722}
item next
Definition cJSON.cpp:2224
std::pair< const Value *, AggregateField > AggregateFieldKey
Identify a field by its LLVM value and path, rather than by its type alone.
Definition PAGBuilder.h:64
Map< AggregateFieldKey, NodeID > aggregateFieldNodes
Reuse the same scalar PAG node for repeated requests for a field.
Definition PAGBuilder.h:66
u32_t getByteSize() const
Definition SVFType.h:287
void getNextInsts(const Instruction *curInst, std::vector< const Instruction * > &instList)
Get the next instructions following control flow.
Definition LLVMUtil.cpp:585
llvm::CallInst CallInst
Definition BasicTypes.h:148
llvm::User User
Definition BasicTypes.h:143

◆ createAggregateReturnParams()

void PAGBuilder::createAggregateReturnParams ( const Function * fun,
const std::set< AggregateField > & fields,
const SVFType * pointerType )
private

Add one output parameter to fun for each demanded field, in field-path order (out_obj in the aggregate return example). The LLVM signature does not change.

Definition at line 1641 of file PAGBuilder.cpp.

1643{
1644 FunObjVar* svfFun =
1645 const_cast<FunObjVar*>(llvmModuleSet()->getFunObjVar(fun));
1646 const FunEntryICFGNode* entry = pag->getICFG()->getFunEntryICFGNode(svfFun);
1647 auto& params = aggregateReturnParams[fun];
1648 for (const AggregateField& field : fields)
1649 {
1651 pag->addArgValNode(id, svfFun->arg_size(), entry, svfFun, pointerType);
1652 auto* arg = SVFUtil::cast<ArgValVar>(pag->getGNode(id));
1653 svfFun->addArgument(arg);
1654 // Like RetValPN, the synthetic parameter uses its function as a
1655 // diagnostic source; it does not add or replace an LLVM argument.
1657 arg->setName("aggregate_return_" + std::to_string(arg->getArgNo()));
1658 params.emplace(field, id);
1659 }
1660}
u32_t arg_size() const
void addArgument(const ArgValVar *arg)
NodeID allocateValueId(void)
Allocate a value ID as determined by the strategy.
std::vector< unsigned > AggregateField
Definition PAGBuilder.h:62

◆ createFunObjVars()

void PAGBuilder::createFunObjVars ( )

set fun in bb

Definition at line 330 of file PAGBuilder.cpp.

331{
332 std::vector<FunObjVar*> funset;
333 // Iterate over all object symbols in the symbol table
334 for (const auto* fun: llvmModuleSet()->getFunctionSet())
335 {
336 u32_t id = llvmModuleSet()->objSyms()[fun];
337 // Debug output for adding object node
338 DBOUT(DPAGBuild, outs() << "add obj node " << id << "\n");
339
340 // Check if the value is a function and add a function object node
341 pag->addFunObjNode(id, pag->getObjTypeInfo(id), nullptr);
342 llvmModuleSet()->LLVMFun2FunObjVar[fun] = cast<FunObjVar>(pag->getGNode(id));
343
344 FunObjVar *funObjVar = SVFUtil::cast<FunObjVar>(pag->getGNode(id));
345 funset.push_back(funObjVar);
346
347 funObjVar->initFunObjVar(fun->isDeclaration(), LLVMUtil::isIntrinsicFun(fun), fun->hasAddressTaken(),
349 SVFUtil::cast<SVFFunctionType>(llvmModuleSet()->getSVFType(fun->getFunctionType())),
350 new SVFLoopAndDomInfo, nullptr, nullptr,
351 {}, nullptr);
352 BasicBlockGraph* bbGraph = new BasicBlockGraph();
353 funObjVar->setBasicBlockGraph(bbGraph);
354
355
356 for (const BasicBlock& bb : *fun)
357 {
358 llvmModuleSet()->addBasicBlock(funObjVar, &bb);
359 }
360
362 for (auto& bb: *funObjVar->bbGraph)
363 {
364 bb.second->setFun(funObjVar);
365 }
366 llvmModuleSet()->addToSVFVar2LLVMValueMap(fun, pag->getGNode(id));
367 }
368
370}
#define DPAGBuild
Definition SVFType.h:584
void setBasicBlockGraph(BasicBlockGraph *graph)
void initFunObjVar(bool decl, bool intrinc, bool addr, bool uncalled, bool notret, bool vararg, const SVFFunctionType *ft, SVFLoopAndDomInfo *ld, const FunObjVar *real, BasicBlockGraph *bbg, const std::vector< const ArgValVar * > &allarg, const SVFBasicBlock *exit)
BasicBlockGraph * bbGraph
the definition of a function across multiple modules
LLVMFun2FunObjVarMap LLVMFun2FunObjVar
Map an LLVM Function to an SVF Funobjvar.
Definition LLVMModule.h:105
ValueToIDMapTy & objSyms()
Definition LLVMModule.h:219
void addBasicBlock(FunObjVar *fun, const BasicBlock *bb)
Definition LLVMModule.h:239
bool isUncalledFunction(const Function *fun)
whether this is a function without any possible caller?
Definition LLVMUtil.cpp:159
bool isIntrinsicFun(const Function *func)
Definition LLVMUtil.cpp:191
bool functionDoesNotRet(const Function *fun)
Definition LLVMUtil.cpp:124

◆ discoverAggregateReturnFields()

PAGBuilder::AggregateReturnFields PAGBuilder::discoverAggregateReturnFields ( )
private

Find the fields of each callee's returned aggregate that callers extract, such as field {0} of make in the aggregate return example. Paths that getAggregateFieldOperands cannot follow are skipped; getAggregateFieldNode later decides which extracted fields are modeled.

Definition at line 1595 of file PAGBuilder.cpp.

1596{
1597 std::vector<AggregateFieldKey> worklist;
1598 for (Module& module : llvmModuleSet()->getLLVMModules())
1599 for (const Function& fun : module)
1600 for (const BasicBlock& bb : fun)
1601 for (const Instruction& inst : bb)
1602 {
1603 if (auto field = getExtractedField(inst))
1604 worklist.push_back(std::move(*field));
1605 }
1606
1607 // Discover callee demands without materializing local field definitions.
1608 // Calls cross into return operands; other producers use the shared grammar.
1609 AggregateReturnFields demands;
1610 Set<AggregateFieldKey> visited;
1611 while (!worklist.empty())
1612 {
1613 AggregateFieldKey field = std::move(worklist.back());
1614 worklist.pop_back();
1615 if (!visited.insert(field).second || field.second.empty())
1616 continue;
1617 if (const auto* call = SVFUtil::dyn_cast<CallInst>(field.first))
1618 {
1619 const Function* callee = call->getCalledFunction();
1620 if (!canModelAggregateReturn(callee) ||
1621 !demands[callee].insert(field.second).second)
1622 continue;
1623 for (const BasicBlock& bb : *callee)
1624 if (const auto* ret = SVFUtil::dyn_cast<ReturnInst>(bb.getTerminator()))
1625 if (ret->getReturnValue())
1626 worklist.emplace_back(ret->getReturnValue(), field.second);
1627 }
1628 else
1629 {
1630 std::vector<AggregateFieldKey> operands;
1631 if (getAggregateFieldOperands(field, operands))
1632 worklist.insert(worklist.end(), operands.begin(), operands.end());
1633 }
1634 }
1635 return demands;
1636}
static bool canModelAggregateReturn(const Function *fun)
bool getAggregateFieldOperands(const AggregateFieldKey &field, std::vector< AggregateFieldKey > &operands)
Describe one field definition without emitting any PAG statements.
Map< const Function *, std::set< AggregateField > > AggregateReturnFields
Field paths extracted from each callee's returned aggregate.
Definition PAGBuilder.h:138
std::unordered_set< Key, Hash, KeyEqual, Allocator > Set
Definition GeneralType.h:51

◆ getAccessPathFromBaseNode()

AccessPath PAGBuilder::getAccessPathFromBaseNode ( NodeID nodeId)
protected

Get a base SVFVar given a pointer Return the source node of its connected normal gep edge Otherwise return the node id itself s32_t offset : gep offset

if this node is already a base node

Definition at line 2467 of file PAGBuilder.cpp.

2468{
2469 SVFVar* node = pag->getGNode(nodeId);
2472 if(geps.empty())
2473 return AccessPath(0);
2474
2475 assert(geps.size()==1 && "one node can only be connected by at most one gep edge!");
2476 SVFVar::iterator it = geps.begin();
2477 const GepStmt* gepEdge = SVFUtil::cast<GepStmt>(*it);
2478 if(gepEdge->isVariantFieldGep())
2479 return AccessPath(0);
2480 else
2481 return gepEdge->getAccessPath();
2482}
bool isVariantFieldGep() const
Gep statement with a variant field index (pointer arithmetic) for struct field access.
const AccessPath & getAccessPath() const
GenericNode< SVFVar, SVFStmt >::GEdgeSetTy SVFStmtSetTy
SVFStmt::SVFStmtSetTy & getIncomingEdges(SVFStmt::PEDGEK kind)
Edge accessors and checkers.

◆ getAggregateFieldNode()

bool PAGBuilder::getAggregateFieldNode ( const Value * aggregate,
const AggregateField & indices,
NodeID & node )
private

Return the node for (aggregate, indices), reusing cached fields. Unsupported dependencies return false without changing PAG or node.

Here, the field node for (a, {0}) copies p; x copies that node: define ptr @field(ptr p) { a = insertvalue { ptr } poison, ptr p, 0 x = extractvalue { ptr } a, 0 ret ptr x }

Definition at line 1475 of file PAGBuilder.cpp.

1477{
1478 const AggregateFieldKey root{aggregate, indices};
1479 // Discovery order keeps field NodeIDs stable across -write-ander and
1480 // -read-ander runs; Value-pointer hash order can swap their points-to sets.
1481 std::vector<std::pair<AggregateFieldKey, std::vector<AggregateFieldKey>>>
1482 definitions;
1483 Set<AggregateFieldKey> discovered;
1484 std::vector<AggregateFieldKey> worklist{root};
1485 while (!worklist.empty())
1486 {
1487 AggregateFieldKey field = std::move(worklist.back());
1488 worklist.pop_back();
1489 if (aggregateFieldNodes.count(field) ||
1490 !discovered.insert(field).second)
1491 continue;
1492 const Type* type = getAggregateFieldType(field.first->getType(), field.second);
1493 if (!type || !type->isPointerTy())
1494 return false;
1495 definitions.emplace_back(field, std::vector<AggregateFieldKey>());
1496 auto& operands = definitions.back().second;
1497 if (!getAggregateFieldOperands(field, operands))
1498 return false;
1499 worklist.insert(worklist.end(), operands.begin(), operands.end());
1500 }
1501
1502 // Validate the entire dependency graph before changing PAG. Allocate every
1503 // field before wiring definitions, including loop-carried Phi/Select cycles.
1504 for (const auto& definition : definitions)
1505 {
1506 const AggregateFieldKey& field = definition.first;
1507 NodeID id;
1508 if (field.second.empty())
1509 id = getValueNode(field.first);
1510 else if (SVFUtil::isa<Constant>(field.first))
1511 id = getValueNode(definition.second.front().first);
1512 else
1513 {
1514 const auto* producer = SVFUtil::cast<Instruction>(field.first);
1515 const Type* type = getAggregateFieldType(producer->getType(), field.second);
1517 pag->addValNode(id, llvmModuleSet()->getSVFType(type),
1518 llvmModuleSet()->getICFGNode(producer));
1519 llvmModuleSet()->addToSVFVar2LLVMValueMap(producer, pag->getGNode(id));
1520 }
1521 aggregateFieldNodes.emplace(field, id);
1522 }
1523
1524 const Value* savedValue = curVal;
1525 const SVFBasicBlock* savedBB = curBB;
1526 for (const auto& definition : definitions)
1527 {
1528 const AggregateFieldKey& field = definition.first;
1529 if (field.second.empty() || SVFUtil::isa<Constant>(field.first))
1530 continue;
1531 const auto* producer = SVFUtil::cast<Instruction>(field.first);
1532 const auto& operands = definition.second;
1533 NodeID dst = aggregateFieldNodes.at(field);
1534 setCurrentLocation(producer, producer->getParent());
1535 if (const auto* phi = SVFUtil::dyn_cast<PHINode>(producer))
1536 {
1537 for (unsigned i = 0; i < operands.size(); ++i)
1538 addPhiStmt(dst, aggregateFieldNodes.at(operands[i]),
1539 llvmModuleSet()->getICFGNode(phi->getIncomingBlock(i)->getTerminator()));
1540 }
1541 else if (const auto* select = SVFUtil::dyn_cast<SelectInst>(producer))
1542 addSelectStmt(dst, aggregateFieldNodes.at(operands[0]),
1543 aggregateFieldNodes.at(operands[1]), getValueNode(select->getCondition()));
1544 else
1545 addCopyEdge(aggregateFieldNodes.at(operands.front()), dst, CopyStmt::COPYVAL);
1546 }
1547 setCurrentLocation(savedValue, savedBB);
1548 node = aggregateFieldNodes.at(root);
1549 return true;
1550}
static const Type * getAggregateFieldType(const Type *type, const std::vector< unsigned > &indices)
Return the type at a constant aggregate path, including fixed vector lanes.
newitem type
Definition cJSON.cpp:2739
void addSelectStmt(NodeID res, NodeID op1, NodeID op2, NodeID cond)
Add SelectStmt.
Definition PAGBuilder.h:529
void addPhiStmt(NodeID res, NodeID opnd, const ICFGNode *pred)
Add Copy edge.
Definition PAGBuilder.h:522

◆ getAggregateFieldOperands()

bool PAGBuilder::getAggregateFieldOperands ( const AggregateFieldKey & field,
std::vector< AggregateFieldKey > & operands )
private

Describe one field definition without emitting any PAG statements.

Definition at line 1374 of file PAGBuilder.cpp.

1376{
1377 const Value* value = field.first;
1378 const AggregateField& path = field.second;
1379 if (path.empty())
1380 return value->getType()->isPointerTy() && !SVFUtil::isa<ConstantExpr>(value) &&
1382 // insertvalue and insertelement replace one field. For example, in
1383 // %b = insertvalue {ptr, ptr} %a, ptr %q, 1
1384 // field {1} of %b is %q, and field {0} of %b is field {0} of %a.
1385 const Value* original = nullptr;
1386 const Value* inserted = nullptr;
1387 AggregateField insertedPath;
1388 if (const auto* insert = SVFUtil::dyn_cast<InsertValueInst>(value))
1389 {
1390 original = insert->getAggregateOperand();
1391 inserted = insert->getInsertedValueOperand();
1392 insertedPath.assign(insert->idx_begin(), insert->idx_end());
1393 }
1394 else if (const auto* insert = SVFUtil::dyn_cast<InsertElementInst>(value))
1395 {
1396 const auto lane = getFixedVectorLane(insert->getType(),
1397 insert->getOperand(2));
1398 if (!lane)
1399 return false;
1400 original = insert->getOperand(0);
1401 inserted = insert->getOperand(1);
1402 insertedPath = {*lane};
1403 }
1404
1405 if (inserted)
1406 {
1407 const size_t commonLength = std::min(insertedPath.size(), path.size());
1408 if (!std::equal(insertedPath.begin(), insertedPath.begin() + commonLength, path.begin()))
1409 operands.emplace_back(original, path);
1410 else if (insertedPath.size() <= path.size())
1411 operands.emplace_back(inserted,
1412 AggregateField(path.begin() + insertedPath.size(), path.end()));
1413 else
1414 return false;
1415 }
1416 else if (const auto* extract = SVFUtil::dyn_cast<ExtractValueInst>(value))
1417 {
1418 AggregateField outer(extract->idx_begin(), extract->idx_end());
1419 outer.insert(outer.end(), path.begin(), path.end());
1420 operands.emplace_back(extract->getAggregateOperand(), std::move(outer));
1421 }
1422 else if (const auto* phi = SVFUtil::dyn_cast<PHINode>(value))
1423 {
1424 for (const Value* incoming : phi->incoming_values())
1425 operands.emplace_back(incoming, path);
1426 }
1427 else if (const auto* select = SVFUtil::dyn_cast<SelectInst>(value))
1428 {
1429 if (!select->getCondition()->getType()->isIntegerTy(1))
1430 return false;
1431 operands.emplace_back(select->getTrueValue(), path);
1432 operands.emplace_back(select->getFalseValue(), path);
1433 }
1434 else if (const auto* freeze = SVFUtil::dyn_cast<FreezeInst>(value))
1435 operands.emplace_back(freeze->getOperand(0), path);
1436 else if (const auto* shuffle = SVFUtil::dyn_cast<ShuffleVectorInst>(value))
1437 {
1438 const auto* vector = SVFUtil::dyn_cast<llvm::FixedVectorType>(shuffle->getOperand(0)->getType());
1439 if (!vector || path.size() != 1)
1440 return false;
1441 int index = shuffle->getMaskValue(path.front());
1442 if (index < 0)
1443 return false;
1444 unsigned width = vector->getNumElements();
1445 operands.emplace_back(shuffle->getOperand(static_cast<unsigned>(index) / width),
1446 AggregateField{static_cast<unsigned>(index) % width});
1447 }
1448 else if (const auto* constant = SVFUtil::dyn_cast<Constant>(value))
1449 {
1450 for (unsigned index : path)
1451 {
1452 constant = constant->getAggregateElement(index);
1453 if (!constant)
1454 return false;
1455 }
1456 operands.emplace_back(constant, AggregateField{});
1457 }
1458 else
1459 // Aggregate arguments, calls and loads need their own field interfaces.
1460 return false;
1461 return !operands.empty();
1462}
static std::optional< unsigned > getFixedVectorLane(const Type *type, const Value *index)
bool hasValueNode(const Value *V)

◆ getBaseTypeAndFlattenedFields()

const Type * PAGBuilder::getBaseTypeAndFlattenedFields ( const Value * V,
std::vector< AccessPath > & fields,
const Value * szValue )
protectedvirtual

Handle external call.

Find the base type and the max possible offset of an object pointed to by (V).

use user-specified size for this copy operation if the size is a constaint int

MaxFieldLimit == 0 denotes field-insensitive analysis, not an empty memory model. The lower bound of one keeps a representative AccessPath; using zero would drop the memcpy/memset effect entirely.

Unsound scalability trade-off: AccessPaths beyond MaxFieldLimit are omitted, so their external-memory effects are not represented in the PAG.

Definition at line 273 of file PAGExtAPI.cpp.

274{
275 assert(V);
276 const Value* value = getBaseValueForExtArg(V);
278 u32_t numOfElems = pag->getNumOfFlattenElements(LLVMModuleSet::getLLVMModuleSet()->getSVFType(objType));
280 if(szValue && SVFUtil::isa<ConstantInt>(szValue))
281 {
283 numOfElems = (numOfElems > szIntVal.first) ? szIntVal.first : numOfElems;
284 }
291 numOfElems = std::min(numOfElems, std::max(Options::MaxFieldLimit(), u32_t{1}));
292
294 for(u32_t ei = 0; ei < numOfElems; ei++)
295 {
296 AccessPath ls(ei);
297 // make a ConstantInt and create char for the content type due to byte-wise copy
298 const ConstantInt* offset = ConstantInt::get(context, llvm::APInt(32, ei));
299 if (!llvmModuleSet()->hasValueNode(offset))
300 {
301 SymbolTableBuilder builder(pag);
302 builder.collectSym(offset);
304 pag->addConstantIntValNode(id, LLVMUtil::getIntegerValue(offset), nullptr, llvmModuleSet()->getSVFType(offset->getType()));
306 pag->getGNode(id));
307 }
308 ls.addOffsetVarAndGepTypePair(getPAG()->getValVar(llvmModuleSet()->getValueNode(offset)), nullptr);
309 fields.push_back(ls);
310 }
311 return objType;
312}
static const Option< u32_t > MaxFieldLimit
Maximum number of field derivations for an object.
Definition Options.h:34

◆ getBaseValueForExtArg()

const Value * PAGBuilder::getBaseValueForExtArg ( const Value * V)
protected

Get the base value of (i8* src and i8* dst) for external argument (e.g. memcpy(i8* dst, i8* src, int size)).

Example 1:

%0 = getelementptr inbounds struct.outer, struct.inner base, i32 0, i32 0 call void @llvm.memcpy(ptr inner, ptr %0, i64 24, i1 false) The base value for %0 is base. Note: the base is recognized as the base value if the offset (field index) is 0

Example 2: https://github.com/SVF-tools/SVF/issues/1650 https://github.com/SVF-tools/SVF/pull/1652

@i1 = dso_local global struct.inner { i32 0, ptr @f1, ptr @f2 } @n1 = dso_local global struct.outer { i32 0, ptr @i1 }

inner = alloca struct.inner %0 = load ptr, ptr getelementptr inbounds (struct.outer, ptr @n1, i32 0, i32 1) call void @llvm.memcpy(ptr inner, ptr %0, i64 24, i1 false)

The base value for %0 is @i1

Example 3:

@conststruct = internal global <{ [40 x i8], [4 x i8], [4 x i8], [2512 x i8] }> <{ [40 x i8] undef, [4 x i8] zeroinitializer, [4 x i8] undef, [2512 x i8] zeroinitializer }>, align 8

%0 = load ptr, ptr getelementptr inbounds (<{ [40 x i8], [4 x i8], [4 x i8], [2512 x i8] }>, ptr @conststruct, i64 0, i32 0, i64 16)

The base value for %0 is still %0

Definition at line 2094 of file PAGBuilder.cpp.

2095{
2096 const Value* value = stripAllCasts(V);
2097 assert(value && "null ptr?");
2098 auto getGlobalFieldFromByteOffset =
2099 [this](const GlobalVariable* glob, int64_t byteOffset) -> const Value*
2100 {
2101 if (!glob || !glob->hasInitializer())
2102 return nullptr;
2103
2104 auto* initializer = SVFUtil::dyn_cast<ConstantStruct>(glob->getInitializer());
2105 auto* structType = SVFUtil::dyn_cast<StructType>(glob->getValueType());
2106 if (!initializer || !structType)
2107 return nullptr;
2108
2109 DataLayout* dataLayout = getDataLayout(llvmModuleSet()->getMainLLVMModule());
2110 const StructLayout* layout =
2111 dataLayout->getStructLayout(const_cast<StructType*>(structType));
2112 for (u32_t fieldIdx = 0; fieldIdx < initializer->getNumOperands(); ++fieldIdx)
2113 {
2114 if (layout->getElementOffset(fieldIdx) != static_cast<uint64_t>(byteOffset))
2115 continue;
2116 if (auto* ptrValue =
2117 SVFUtil::dyn_cast<llvm::GlobalVariable>(initializer->getOperand(fieldIdx)))
2118 return ptrValue;
2119 return nullptr;
2120 }
2121 return nullptr;
2122 };
2123
2125 {
2126 APOffset totalidx = 0;
2127 for (bridge_gep_iterator gi = bridge_gep_begin(gep), ge = bridge_gep_end(gep); gi != ge; ++gi)
2128 {
2129 if(const ConstantInt* op = SVFUtil::dyn_cast<ConstantInt>(gi.getOperand()))
2130 totalidx += LLVMUtil::getIntegerValue(op).first;
2131 }
2132 if(totalidx == 0 && !SVFUtil::isa<StructType>(value->getType()))
2133 value = gep->getPointerOperand();
2134 }
2135 else if (const LoadInst* load = SVFUtil::dyn_cast<LoadInst>(value))
2136 {
2137 const Value* loadP = load->getPointerOperand();
2139 {
2140 DataLayout* dataLayout = getDataLayout(llvmModuleSet()->getMainLLVMModule());
2141 llvm::APInt byteOffset(dataLayout->getIndexSizeInBits(gep->getPointerAddressSpace()), 0, true);
2142 const bool hasByteOffset = dataLayout && gep->accumulateConstantOffset(*dataLayout, byteOffset);
2143
2144 const Value * pointer_operand = gep->getPointerOperand();
2145 if (auto *glob = SVFUtil::dyn_cast<GlobalVariable>(pointer_operand))
2146 {
2147 if (hasByteOffset)
2148 {
2149 if (const Value* ptrValue = getGlobalFieldFromByteOffset(glob, byteOffset.getSExtValue()))
2150 return ptrValue;
2151 }
2152 }
2153 else if (hasByteOffset && !byteOffset.isNegative() &&
2154 SVFUtil::isa<AllocaInst>(pointer_operand) && load->getType()->isPointerTy())
2155 {
2156 const u64_t offset = byteOffset.getZExtValue();
2157 const u64_t accessBytes = dataLayout->getPointerSize(gep->getPointerAddressSpace());
2158
2159 auto isCoveredByMemcpy = [offset, accessBytes](const CallBase* cs) -> bool
2160 {
2161 if (cs->arg_size() < 3)
2162 return false;
2163
2164 const auto* copySize = SVFUtil::dyn_cast<ConstantInt>(cs->getArgOperand(2));
2165 if (!copySize)
2166 {
2167 return false;
2168 }
2169
2170 const u64_t copyBytes = copySize->getZExtValue();
2171 return copyBytes >= accessBytes && copyBytes - accessBytes >= offset;
2172 };
2173
2174 auto hasInterveningWrite = [load](const Instruction* from) -> bool
2175 {
2176 if (from->getParent() != load->getParent() || !from->comesBefore(load))
2177 return true;
2178
2179 auto it = from->getIterator();
2180 const auto end = load->getIterator();
2181 while (++it != end)
2182 {
2183 if (it->mayWriteToMemory())
2184 return true;
2185 }
2186 return false;
2187 };
2188
2189 for (const auto& use : pointer_operand->users())
2190 {
2191 const auto* cs = SVFUtil::dyn_cast<CallBase>(use);
2192 if (!cs || cs->getParent() != load->getParent() ||
2193 cs->arg_size() < 1 ||
2194 stripAllCasts(cs->getArgOperand(0)) != pointer_operand)
2195 continue;
2196
2197 const Function* calledFun = cs->getCalledFunction();
2198 if (!LLVMUtil::isMemcpyExtFun(calledFun) || !isCoveredByMemcpy(cs) ||
2199 hasInterveningWrite(cs))
2200 continue;
2201
2202 const Value* copiedFrom = getBaseValueForExtArg(cs->getArgOperand(1));
2203 if (const auto* copiedGlob = SVFUtil::dyn_cast<GlobalVariable>(copiedFrom))
2204 {
2205 if (const Value* ptrValue =
2206 getGlobalFieldFromByteOffset(copiedGlob, byteOffset.getSExtValue()))
2207 return ptrValue;
2208 }
2209 }
2210 }
2211 }
2212 }
2213
2214 return value;
2215}
const Value * stripAllCasts(const Value *val)
Strip off the all casts.
Definition LLVMUtil.cpp:251
bool isMemcpyExtFun(const Function *fun)
Definition LLVMUtil.cpp:390
llvm::GlobalVariable GlobalVariable
Definition BasicTypes.h:131
llvm::CallBase CallBase
Definition BasicTypes.h:147
unsigned long long u64_t
Definition GeneralType.h:69
llvm::StructLayout StructLayout
Definition BasicTypes.h:103
llvm::LoadInst LoadInst
Definition BasicTypes.h:150
llvm::GetElementPtrInst GetElementPtrInst
Definition BasicTypes.h:163

◆ getCopyKind()

CopyStmt::CopyKind SVF::PAGBuilder::getCopyKind ( const Value * val)
inlineprotected

Definition at line 484 of file PAGBuilder.h.

485 {
486 // COPYVAL, ZEXT, SEXT, BITCAST, FPTRUNC, FPTOUI, FPTOSI, UITOFP, SITOFP, INTTOPTR, PTRTOINT
487 if (const Instruction* inst = SVFUtil::dyn_cast<Instruction>(val))
488 {
489 switch (inst->getOpcode())
490 {
491 case Instruction::ZExt:
492 return CopyStmt::ZEXT;
493 case Instruction::SExt:
494 return CopyStmt::SEXT;
495 case Instruction::BitCast:
496 return CopyStmt::BITCAST;
497 case Instruction ::Trunc:
498 return CopyStmt::TRUNC;
499 case Instruction::FPTrunc:
500 return CopyStmt::FPTRUNC;
501 case Instruction::FPToUI:
502 return CopyStmt::FPTOUI;
503 case Instruction::FPToSI:
504 return CopyStmt::FPTOSI;
505 case Instruction::UIToFP:
506 return CopyStmt::UITOFP;
507 case Instruction::SIToFP:
508 return CopyStmt::SITOFP;
509 case Instruction::IntToPtr:
510 return CopyStmt::INTTOPTR;
511 case Instruction::PtrToInt:
512 return CopyStmt::PTRTOINT;
513 default:
514 return CopyStmt::COPYVAL;
515 }
516 }
517 assert (false && "Unknown cast inst!");
518 abort();
519 }

◆ getCurrentBB()

const SVFBasicBlock * SVF::PAGBuilder::getCurrentBB ( ) const
inlineprotected

Definition at line 366 of file PAGBuilder.h.

367 {
368 return curBB;
369 }

◆ getCurrentValue()

const Value * SVF::PAGBuilder::getCurrentValue ( ) const
inlineprotected

Definition at line 362 of file PAGBuilder.h.

363 {
364 return curVal;
365 }

◆ getDirectAccessFieldZeroValVar()

NodeID PAGBuilder::getDirectAccessFieldZeroValVar ( const Value * ptr,
const Type * accessTy )
protected

Definition at line 2337 of file PAGBuilder.cpp.

2338{
2340 return 0;
2341
2342 const Type* objTy =
2344 const ArrayType* arrTy = SVFUtil::dyn_cast<ArrayType>(objTy);
2345 if (!arrTy || !arrTy->getElementType()->isPointerTy() ||
2346 arrTy->getElementType() != accessTy)
2347 return 0;
2348
2349 AccessPath ap(0, llvmModuleSet()->getSVFType(arrTy));
2350 return getGepValVar(ptr, ap, llvmModuleSet()->getSVFType(accessTy));
2351}

◆ getExtractedField()

std::optional< PAGBuilder::AggregateFieldKey > PAGBuilder::getExtractedField ( const Instruction & inst)
staticprivate

Decode a pointer extraction; unsupported instructions have no field.

Get the aggregate and field path that a pointer extractvalue, or a pointer extractelement with a constant index, reads. For example, x = extractvalue {ptr, ptr} a, 0 reads field {0} of a.

Definition at line 1769 of file PAGBuilder.cpp.

1770{
1771 if (!inst.getType()->isPointerTy())
1772 return std::nullopt;
1773 if (const auto* extract = SVFUtil::dyn_cast<ExtractValueInst>(&inst))
1774 {
1775 return AggregateFieldKey
1776 {
1777 extract->getAggregateOperand(),
1778 AggregateField(extract->idx_begin(), extract->idx_end())};
1779 }
1780 const auto* extract = SVFUtil::dyn_cast<ExtractElementInst>(&inst);
1781 if (!extract)
1782 return std::nullopt;
1783 const auto lane = getFixedVectorLane(extract->getVectorOperandType(),
1784 extract->getIndexOperand());
1785 if (!lane)
1786 return std::nullopt;
1787 return AggregateFieldKey{extract->getVectorOperand(),
1788 AggregateField{*lane}};
1789}

◆ getGepValVar()

NodeID PAGBuilder::getGepValVar ( const Value * val,
const AccessPath & ap,
const SVFType * elementType )
protected

Add a temp field value node according to base value and offset this node is after the initial node method, it is out of scope of symInfo table

Definition at line 2289 of file PAGBuilder.cpp.

2290{
2291 NodeID base = getValueNode(val);
2292 NodeID gepval = pag->getGepValVar(llvmModuleSet()->getValueNode(curVal), base, ap);
2293 if (gepval==UINT_MAX)
2294 {
2295 assert(((int) UINT_MAX)==-1 && "maximum limit of unsigned int is not -1?");
2296 /*
2297 * getGepValVar can only be called from two places:
2298 * 1. PAGBuilder::addComplexConsForExt to handle external calls
2299 * 2. PAGBuilder::getGlobalVarField to initialize global variable
2300 * so curVal can only be
2301 * 1. Instruction
2302 * 2. GlobalVariable
2303 */
2304 assert(
2305 (SVFUtil::isa<Instruction>(curVal) || SVFUtil::isa<GlobalVariable>(curVal)) && "curVal not an instruction or a globalvariable?");
2306
2307 // We assume every GepValNode and its GepEdge to the baseNode are unique across the whole program
2308 // We preserve the current BB information to restore it after creating the gepNode
2309 const Value* cval = getCurrentValue();
2310 const SVFBasicBlock* cbb = getCurrentBB();
2311 setCurrentLocation(curVal, (SVFBasicBlock*) nullptr);
2312 LLVMModuleSet* llvmmodule = llvmModuleSet();
2313 const ICFGNode* node = nullptr;
2315 {
2316 if (llvmmodule->hasICFGNode(inst))
2317 {
2318 node = llvmmodule->getICFGNode(inst);
2319 }
2320 }
2322 {
2323 // GEP on a global variable: the resulting GepValVar belongs to the global ICFG node.
2324 node = pag->getICFG()->getGlobalICFGNode();
2325 }
2326 NodeID gepNode = pag->addGepValNode(llvmModuleSet()->getValueNode(curVal), cast<ValVar>(pag->getGNode(getValueNode(val))), ap,
2327 NodeIDAllocator::get()->allocateValueId(),
2328 llvmmodule->getSVFType(PointerType::getUnqual(llvmmodule->getContext())), node);
2329 addGepEdge(base, gepNode, ap, true);
2330 setCurrentLocation(cval, cbb);
2331 return gepNode;
2332 }
2333 else
2334 return gepval;
2335}
bool hasICFGNode(const Instruction *inst)
void addGepEdge(NodeID src, NodeID dst, const AccessPath &ap, bool constGep)
Add Gep edge.
Definition PAGBuilder.h:589

◆ getGlobalVarField()

NodeID PAGBuilder::getGlobalVarField ( const GlobalVariable * gvar,
u32_t offset,
SVFType * tpy )
protected

Get the field of the global variable node FIXME:Here we only get the field that actually used in the program We ignore the initialization of global variable field that not used in the program

if we did not find the constant expression in the program, then we need to create a gep node for this field

Definition at line 876 of file PAGBuilder.cpp.

877{
878
879 // if the global variable do not have any field needs to be initialized
880 if (offset == 0 && gvar->getInitializer()->getType()->isSingleValueType())
881 {
882 return getValueNode(gvar);
883 }
886 else
887 {
888 return getGepValVar(gvar, AccessPath(offset), tpy);
889 }
890}

◆ getObjectNode()

NodeID SVF::PAGBuilder::getObjectNode ( const Value * V)
inline

GetObject - Return the object node (stack/global/heap/function) according to a LLVM Value.

Definition at line 203 of file PAGBuilder.h.

204 {
205 return llvmModuleSet()->getObjectNode(V);
206 }
NodeID getObjectNode(const Value *V)

◆ getPAG()

PAG * SVF::PAGBuilder::getPAG ( ) const
inline

Return PAG.

Definition at line 165 of file PAGBuilder.h.

166 {
167 return pag;
168 }

◆ getReturnNode()

NodeID SVF::PAGBuilder::getReturnNode ( const FunObjVar * func)
inline

getReturnNode - Return the node representing the unique return value of a function.

Definition at line 209 of file PAGBuilder.h.

210 {
211 return pag->getReturnNode(func);
212 }

◆ getValueNode()

NodeID SVF::PAGBuilder::getValueNode ( const Value * V)
inline

Get different kinds of node.

Definition at line 193 of file PAGBuilder.h.

194 {
195 // first handle gep edge if val if a constant expression
196 processCE(V);
197
198 // strip off the constant cast and return the value node
199 return llvmModuleSet()->getValueNode(V);
200 }
void processCE(const Value *val)
Process constant expression.

◆ getVarargNode()

NodeID SVF::PAGBuilder::getVarargNode ( const FunObjVar * func)
inline

getVarargNode - Return the node representing the unique variadic argument of a function.

Definition at line 215 of file PAGBuilder.h.

216 {
217 return pag->getVarargNode(func);
218 }

◆ handleDirectCall()

void PAGBuilder::handleDirectCall ( CallBase * cs,
const Function * F )
protected

Handle direct call.

Add the constraints for a direct, non-external call.

FIXME: this assertion should be placed for correct checking except bug program like 188.ammp, 300.twolf

Definition at line 1999 of file PAGBuilder.cpp.

2000{
2001
2002 assert(F);
2003 CallICFGNode* callICFGNode = llvmModuleSet()->getCallICFGNode(cs);
2004 const FunObjVar* svffun = llvmModuleSet()->getFunObjVar(F);
2005 DBOUT(DPAGBuild, outs() << "handle direct call " << LLVMUtil::dumpValue(cs)
2006 << " callee " << F->getName().str() << "\n");
2007
2008 //Only handle the ret.val. if it's used as a ptr.
2009 NodeID dstrec = getValueNode(cs);
2010 //Does it actually return a ptr?
2011 if (!cs->getType()->isVoidTy())
2012 {
2013 NodeID srcret = getReturnNode(svffun);
2014 FunExitICFGNode* exitICFGNode = pag->getICFG()->getFunExitICFGNode(svffun);
2015 addRetEdge(srcret, dstrec,callICFGNode, exitICFGNode);
2016 }
2017 //Iterators for the actual and formal parameters
2018 u32_t itA = 0, ieA = cs->arg_size();
2019 Function::const_arg_iterator itF = F->arg_begin(), ieF = F->arg_end();
2020 //Go through the fixed parameters.
2021 DBOUT(DPAGBuild, outs() << " args:");
2022 for (; itF != ieF; ++itA, ++itF)
2023 {
2024 //Some programs (e.g. Linux kernel) leave unneeded parameters empty.
2025 if (itA == ieA)
2026 {
2027 DBOUT(DPAGBuild, outs() << " !! not enough args\n");
2028 break;
2029 }
2030 const Value* AA = cs->getArgOperand(itA), *FA = &*itF; //current actual/formal arg
2031
2032 DBOUT(DPAGBuild, outs() << "process actual parm "
2033 << LLVMUtil::dumpValue(AA) << "\n");
2034
2035 NodeID dstFA = getValueNode(FA);
2036 NodeID srcAA = getValueNode(AA);
2037 FunEntryICFGNode* entry = pag->getICFG()->getFunEntryICFGNode(svffun);
2038 addCallEdge(srcAA, dstFA, callICFGNode, entry);
2039 }
2040 //Any remaining actual args must be varargs.
2041 if (F->isVarArg())
2042 {
2043 NodeID vaF = getVarargNode(svffun);
2044 DBOUT(DPAGBuild, outs() << "\n varargs:");
2045 for (; itA != ieA; ++itA)
2046 {
2047 const Value* AA = cs->getArgOperand(itA);
2048 NodeID vnAA = getValueNode(AA);
2049 FunEntryICFGNode* entry = pag->getICFG()->getFunEntryICFGNode(svffun);
2050 addCallEdge(vnAA,vaF, callICFGNode,entry);
2051 }
2052 }
2053 if(itA != ieA)
2054 {
2057 writeWrnMsg("too many args to non-vararg func.");
2058 writeWrnMsg("(" + callICFGNode->getSourceLoc() + ")");
2059
2060 }
2061}
const std::string getSourceLoc() const override
Definition ICFGNode.h:571
void addRetEdge(NodeID src, NodeID dst, const CallICFGNode *cs, const FunExitICFGNode *exit)
Add Return edge.
Definition PAGBuilder.h:583
NodeID getVarargNode(const FunObjVar *func)
getVarargNode - Return the node representing the unique variadic argument of a function.
Definition PAGBuilder.h:215
NodeID getReturnNode(const FunObjVar *func)
getReturnNode - Return the node representing the unique return value of a function.
Definition PAGBuilder.h:209
std::string dumpValue(const Value *val)
Definition LLVMUtil.cpp:612

◆ handleExtCall()

void PAGBuilder::handleExtCall ( const CallBase * cs,
const Function * callee )
protectedvirtual

pthread_create has 1 arg. apr_thread_create has 2 arg.

Connect actual parameter to formal parameter of the start routine

handle indirect calls at pthread create APIs e.g., pthread_create(&t1, nullptr, fp, ...); const Value* fun = ThreadAPI::getThreadAPI()->getForkedFun(inst); if(!SVFUtil::isa<Function>(fun)) pag->addIndirectCallsites(cs,pag->getValueNode(fun));

If forkedFun does not pass to spawnee as function type but as void pointer remember to update inter-procedural callgraph/PAG/SVFG etc. when indirect call targets are resolved We don't connect the callgraph here, further investigation is need to handle mod-ref during SVFG construction.

TODO: inter-procedural PAG edges for thread joins

Definition at line 471 of file PAGExtAPI.cpp.

472{
473 const CallICFGNode *callICFGNode = llvmModuleSet()->getCallICFGNode(cs);
474
475 if (hasNondetArgStoreAtExtCall(callICFGNode))
476 {
477 handleNondetArgStoreAtExtCall(cs, callICFGNode);
478 }
479 else if (isHeapAllocExtCallViaRet(callICFGNode))
480 {
481 NodeID val = llvmModuleSet()->getValueNode(cs);
483 addAddrWithHeapSz(obj, val, cs);
484 }
485 else if (isHeapAllocExtCallViaArg(callICFGNode))
486 {
488 Value* arg = cs->getArgOperand(arg_pos);
489 if (cs->getArgOperand(arg_pos)->getType()->isPointerTy())
490 {
491 NodeID vnArg = llvmModuleSet()->getValueNode(arg);
492 NodeID dummy = pag->addDummyValNode();
493 NodeID obj = pag->addDummyObjNode(llvmModuleSet()->getSVFType(cs->getArgOperand(arg_pos)->getType()));
494 if (vnArg && dummy && obj)
495 {
496 addAddrWithHeapSz(obj, dummy, cs);
497 addStoreEdge(dummy, vnArg);
498 }
499 }
500 else
501 {
502 writeWrnMsg("Arg receiving new object must be pointer type");
503 }
504 }
505 else if (llvmModuleSet()->hasExtFuncAnnotation(callee, "STRCAT") ||
506 llvmModuleSet()->hasExtFuncAnnotation(callee, "STRCPY"))
507 {
508 // strcpy/strcat: add only ret = dst. Unlike the memcpy branch below, add no
509 // field copies (addComplexConsForExt), because the copied range depends on
510 // the string contents. AbsExtAPI's strcpy/strcat handlers write dst.
511 if(SVFUtil::isa<PointerType>(cs->getType()))
512 addCopyEdge(getValueNode(cs->getArgOperand(0)), getValueNode(cs), CopyStmt::COPYVAL);
513 }
514 else if (LLVMUtil::isMemcpyExtFun(callee))
515 {
516 // Side-effects similar to void *memcpy(void *dest, const void * src, size_t n)
517 // which copies n characters from memory area 'src' to memory area 'dest'.
518 if(callee->getName().find("iconv") != std::string::npos)
519 addComplexConsForExt(cs->getArgOperand(3), cs->getArgOperand(1), nullptr);
520 else if(callee->getName().find("bcopy") != std::string::npos)
521 addComplexConsForExt(cs->getArgOperand(1), cs->getArgOperand(0), cs->getArgOperand(2));
522 if(cs->arg_size() == 3)
523 addComplexConsForExt(cs->getArgOperand(0), cs->getArgOperand(1), cs->getArgOperand(2));
524 else
525 addComplexConsForExt(cs->getArgOperand(0), cs->getArgOperand(1), nullptr);
526 if(SVFUtil::isa<PointerType>(cs->getType()))
527 addCopyEdge(getValueNode(cs->getArgOperand(0)), getValueNode(cs), CopyStmt::COPYVAL);
528 }
529 else if (llvmModuleSet()->hasExtFuncAnnotation(callee, "STRLEN"))
530 {
531 // strlen(p) and wcslen(p) read characters, not just p's address.
532 // For char s[4]="ABC", represent reads of s[0..3] so a write
533 // to s[1] in a callee can reach this call through the SVFG.
534 std::vector<AccessPath> fields;
535 const Value* arg = cs->getArgOperand(0);
536 const Type* type = getBaseTypeAndFlattenedFields(arg, fields, nullptr);
537 for (const AccessPath& field : fields)
538 {
539 const SVFType* elementType = pag->getFlatternedElemType(
540 llvmModuleSet()->getSVFType(type),
541 field.getConstantStructFldIdx());
542 NodeID address = getGepValVar(arg, field, elementType);
543 addLoadEdge(address, pag->addDummyValNode());
544 }
545 }
546 else if(LLVMUtil::isMemsetExtFun(callee))
547 {
548 // Side-effects similar to memset(void *str, int c, size_t n)
549 // which copies the character c (an unsigned char) to the first n characters of the string pointed to, by the argument str
550 std::vector<AccessPath> dstFields;
551 const Type *dtype = getBaseTypeAndFlattenedFields(cs->getArgOperand(0), dstFields, cs->getArgOperand(2));
552 u32_t sz = dstFields.size();
553 //For each field (i), add store edge *(arg0 + i) = arg1
554 for (u32_t index = 0; index < sz; index++)
555 {
556 LLVMModuleSet* llvmmodule = LLVMModuleSet::getLLVMModuleSet();
557 const SVFType* dElementType = pag->getFlatternedElemType(llvmmodule->getSVFType(dtype),
558 dstFields[index].getConstantStructFldIdx());
559 NodeID dField = getGepValVar(cs->getArgOperand(0), dstFields[index], dElementType);
560 addStoreEdge(getValueNode(cs->getArgOperand(1)),dField);
561 }
562 if(SVFUtil::isa<PointerType>(cs->getType()))
563 addCopyEdge(getValueNode(cs->getArgOperand(0)), getValueNode(cs), CopyStmt::COPYVAL);
564 }
565 else if(callee->getName().compare("dlsym") == 0)
566 {
567 /*
568 Side-effects of void* dlsym( void* handle, const char* funName),
569 Locate the function with the name "funName," then add a "copy" edge between the callsite and that function.
570 dlsym() example:
571 int main() {
572 // Open the shared library
573 void* handle = dlopen("./my_shared_library.so", RTLD_LAZY);
574 // Find the function address
575 void (*myFunctionPtr)() = (void (*)())dlsym(handle, "myFunction");
576 // Call the function
577 myFunctionPtr();
578 }
579 */
580 const Value* src = cs->getArgOperand(1);
582 src = stripConstantCasts(gep->getPointerOperand());
583
584 auto getHookFn = [](const Value* src)->const Function*
585 {
587 return nullptr;
588
589 auto *glob = SVFUtil::cast<GlobalVariable>(src);
590 if (!glob->hasInitializer() || !SVFUtil::isa<ConstantDataArray>(glob->getInitializer()))
591 return nullptr;
592
593 auto *constarray = SVFUtil::cast<ConstantDataArray>(glob->getInitializer());
594 return LLVMUtil::getProgFunction(constarray->getAsCString().str());
595 };
596
597 if (const Function *fn = getHookFn(src))
598 {
599 NodeID srcNode = getValueNode(fn);
601 }
602 }
603 else if(callee->getName().find("_ZSt29_Rb_tree_insert_and_rebalancebPSt18_Rb_tree_node_baseS0_RS_") != std::string::npos)
604 {
605 // The purpose of this function is to insert a new node into the red-black tree and then rebalance the tree to ensure that the red-black tree properties are maintained.
606 assert(cs->arg_size() == 4 && "_Rb_tree_insert_and_rebalance should have 4 arguments.\n");
607
608 // We have vArg3 points to the entry of _Rb_tree_node_base { color; parent; left; right; }.
609 // Now we calculate the offset from base to vArg3
610 NodeID vnArg3 = llvmModuleSet()->getValueNode(cs->getArgOperand(3));
613
614 // We get all flattened fields of base
615 vector<AccessPath> fields = pag->getTypeLocSetsMap(vnArg3).second;
616
617 // We summarize the side effects: arg3->parent = arg1, arg3->left = arg1, arg3->right = arg1
618 // Note that arg0 is aligned with "offset".
619 for (APOffset i = offset + 1; i <= offset + 3; ++i)
620 {
621 if((u32_t)i >= fields.size())
622 break;
623 const SVFType* elementType = pag->getFlatternedElemType(pag->getTypeLocSetsMap(vnArg3).first,
624 fields[i].getConstantStructFldIdx());
625 NodeID vnD = getGepValVar(cs->getArgOperand(3), fields[i], elementType);
626 NodeID vnS = llvmModuleSet()->getValueNode(cs->getArgOperand(1));
627 if(vnD && vnS)
628 addStoreEdge(vnS,vnD);
629 }
630 }
631
632 if (isThreadForkCall(callICFGNode))
633 {
634 const ValVar* valVar = getForkedFun(callICFGNode);
635 if (const FunValVar* funcValVar = SVFUtil::dyn_cast<FunValVar>(valVar))
636 {
637 const FunObjVar* forkedFun = funcValVar->getFunction()->getDefFunForMultipleModule();
638 const SVFVar* actualParm = getActualParmAtForkSite(callICFGNode);
641 assert((forkedFun->arg_size() <= 2) && "Size of formal parameter of start routine should be one");
642 if (forkedFun->arg_size() <= 2 && forkedFun->arg_size() >= 1)
643 {
644 const ArgValVar* formalParm = forkedFun->getArg(0);
646 if (actualParm->isPointer() && formalParm->getType()->isPointerTy())
647 {
648 FunEntryICFGNode *entry = pag->getICFG()->getFunEntryICFGNode(forkedFun);
649 addThreadForkEdge(actualParm->getId(), formalParm->getId(), callICFGNode, entry);
650 }
651 }
652 }
653 else
654 {
659 }
663 }
664
666}
const ArgValVar * getArg(u32_t idx) const
void addThreadForkEdge(NodeID src, NodeID dst, const CallICFGNode *cs, const FunEntryICFGNode *entry)
Add Thread fork edge for parameter passing.
Definition PAGBuilder.h:607
AccessPath getAccessPathFromBaseNode(NodeID nodeId)
AddrStmt * addAddrWithHeapSz(NodeID src, NodeID dst, const CallBase *cs)
Add Address edge from ext call with args like "%5 = call i8* @malloc(i64 noundef 5)".
Definition PAGBuilder.h:428
virtual void addComplexConsForExt(Value *D, Value *S, const Value *sz)
virtual void handleNondetArgStoreAtExtCall(const CallBase *cs, const CallICFGNode *callICFGNode)
NodeID getId() const
Get ID.
Definition SVFValue.h:158
virtual const SVFType * getType() const
Definition SVFValue.h:169
virtual bool isPointer() const
Check if this variable represents a pointer.
const Function * getProgFunction(const std::string &funName)
Get program entry function from module.
Definition LLVMUtil.cpp:41
const Value * stripConstantCasts(const Value *val)
Strip off the constant casts.
Definition LLVMUtil.cpp:220
bool isHeapAllocExtCallViaRet(const Instruction *inst)
Definition LLVMUtil.cpp:645
bool isHeapAllocExtCallViaArg(const Instruction *inst)
Definition LLVMUtil.cpp:660
bool isMemsetExtFun(const Function *fun)
Definition LLVMUtil.cpp:396
u32_t getHeapAllocHoldingArgPosition(const Function *fun)
Definition LLVMUtil.cpp:402
bool isThreadForkCall(const CallICFGNode *inst)
Definition SVFUtil.h:365
const ValVar * getActualParmAtForkSite(const CallICFGNode *cs)
Return sole argument of the thread routine.
Definition SVFUtil.h:413
const ValVar * getForkedFun(const CallICFGNode *inst)
Return thread fork function.
Definition SVFUtil.h:336

◆ handleIndCall()

void PAGBuilder::handleIndCall ( CallBase * cs)
protected

Handle indirect call.

Indirect call is resolved on-the-fly during pointer analysis

Definition at line 2220 of file PAGBuilder.cpp.

2221{
2222 const CallICFGNode* cbn = llvmModuleSet()->getCallICFGNode(cs);
2223 NodeID indFunPtrId = llvmModuleSet()->getValueNode(cs->getCalledOperand());
2224 const_cast<CallICFGNode*>(cbn)->setIndFunPtr(pag->getGNode(indFunPtrId));
2225 pag->addIndirectCallsites(cbn,indFunPtrId);
2226}

◆ handleNondetArgStoreAtExtCall()

void PAGBuilder::handleNondetArgStoreAtExtCall ( const CallBase * cs,
const CallICFGNode * callICFGNode )
protectedvirtual

Definition at line 415 of file PAGExtAPI.cpp.

416{
417 Set<u32_t> storeTopArgs;
418 NodeID src = pag->getBlkPtr();
419 const FunObjVar* extFun = callICFGNode->getCalledFunction();
420 if (extFun)
421 {
422 for (const std::string& annotation :
423 ExtAPI::getExtAPI()->getExtFuncAnnotations(extFun))
424 {
425 u32_t annotatedFormatArg = 0;
426 if (parseScanfFormatArg(annotation, annotatedFormatArg))
427 {
428 if (annotatedFormatArg < cs->arg_size())
429 {
430 src = pag->getBlkPtr();
431 if (!scanfMayStorePointer(cs, annotatedFormatArg))
432 {
433 // scanf("%d", &n) writes a number, not a pointer. Copy BlkPtr
434 // into a non-pointer variable so AE still sees an unknown value.
435 src = pag->addValNode(NodeIDAllocator::get()->allocateValueId(), SVFType::getSVFInt8Type(), callICFGNode);
436 // Keep the call's LLVM value available when printing this variable.
437 llvmModuleSet()->addToSVFVar2LLVMValueMap(cs, pag->getGNode(src));
438 addCopyEdge(pag->getBlkPtr(), src, CopyStmt::COPYVAL);
439 }
440 }
441 continue;
442 }
443
444 u32_t firstArg = 0;
445 if (!parseNondetArgStoreAtExtCall(annotation, firstArg))
446 continue;
447 if (firstArg >= cs->arg_size())
448 continue;
449
450 for (u32_t argIdx = firstArg; argIdx < cs->arg_size(); ++argIdx)
451 storeTopArgs.insert(argIdx);
452 }
453 }
454
455 for (u32_t argIdx : storeTopArgs)
456 {
457 const Value* arg = cs->getArgOperand(argIdx);
458 if (!arg->getType()->isPointerTy())
459 continue;
460
461 const Type* storedType =
463 NodeID dst = getValueNode(arg);
464 if (NodeID fieldZero = getDirectAccessFieldZeroValVar(arg, storedType))
465 dst = fieldZero;
466 if (src && dst)
467 addStoreEdge(src, dst);
468 }
469}
const FunObjVar * getCalledFunction() const
Definition ICFGNode.h:501
static ExtAPI * getExtAPI()
Definition ExtAPI.cpp:43
NodeID getDirectAccessFieldZeroValVar(const Value *ptr, const Type *accessTy)
static SVFType * getSVFInt8Type()
Definition SVFType.h:222

◆ inferFieldIdxFromByteOffset()

u32_t PAGBuilder::inferFieldIdxFromByteOffset ( const llvm::GEPOperator * gepOp,
DataLayout * dl,
AccessPath & ap,
APOffset idx )
protected

Infer field index from byteoffset.

Definition at line 621 of file PAGBuilder.cpp.

622{
623 return 0;
624}

◆ initDomTree()

void PAGBuilder::initDomTree ( FunObjVar * func,
const Function * f )

Definition at line 262 of file PAGBuilder.cpp.

263{
264 if (fun->isDeclaration())
265 return;
266 //process and stored dt & df
269 df.analyze(dt);
270 LoopInfo loopInfo = LoopInfo(dt);
271 PostDominatorTree pdt = PostDominatorTree(const_cast<Function&>(*fun));
272 SVFLoopAndDomInfo* ld = svffun->getLoopAndDomInfo();
273
275 for (DominanceFrontierBase::const_iterator dfIter = df.begin(), eDfIter = df.end(); dfIter != eDfIter; dfIter++)
276 {
277 const BasicBlock* keyBB = dfIter->first;
278 const llvm::SetVector<llvm::BasicBlock* >& domSet = dfIter->second;
279 Set<const SVFBasicBlock*>& valueBasicBlocks = dfBBsMap[llvmModuleSet()->getSVFBasicBlock(keyBB)];
280 for (const BasicBlock* bbValue:domSet)
281 {
282 valueBasicBlocks.insert(llvmModuleSet()->getSVFBasicBlock(bbValue));
283 }
284 }
285 std::vector<const SVFBasicBlock*> reachableBBs;
286 LLVMUtil::getFunReachableBBs(fun, reachableBBs);
287 ld->setReachableBBs(reachableBBs);
288
289 for (Function::const_iterator bit = fun->begin(), beit = fun->end(); bit!=beit; ++bit)
290 {
291 const BasicBlock &bb = *bit;
292 SVFBasicBlock* svfBB = llvmModuleSet()->getSVFBasicBlock(&bb);
293 if (DomTreeNode* dtNode = dt.getNode(&bb))
294 {
295 SVFLoopAndDomInfo::BBSet& bbSet = ld->getDomTreeMap()[svfBB];
296 for (const auto domBB : *dtNode)
297 {
298 const auto* domSVFBB = llvmModuleSet()->getSVFBasicBlock(domBB->getBlock());
299 bbSet.insert(domSVFBB);
300 }
301 }
302
303 if (DomTreeNode* pdtNode = pdt.getNode(&bb))
304 {
305 u32_t level = pdtNode->getLevel();
306 ld->getBBPDomLevel()[svfBB] = level;
307 BasicBlock* idomBB = pdtNode->getIDom()->getBlock();
308 const SVFBasicBlock* idom = idomBB == NULL ? NULL: llvmModuleSet()->getSVFBasicBlock(idomBB);
309 ld->getBB2PIdom()[svfBB] = idom;
310
311 SVFLoopAndDomInfo::BBSet& bbSet = ld->getPostDomTreeMap()[svfBB];
312 for (const auto domBB : *pdtNode)
313 {
314 const auto* domSVFBB = llvmModuleSet()->getSVFBasicBlock(domBB->getBlock());
315 bbSet.insert(domSVFBB);
316 }
317 }
318
319 if (const Loop* loop = loopInfo.getLoopFor(&bb))
320 {
321 for (const BasicBlock* loopBlock : loop->getBlocks())
322 {
323 const SVFBasicBlock* loopbb = llvmModuleSet()->getSVFBasicBlock(loopBlock);
324 ld->addToBB2LoopMap(svfBB, loopbb);
325 }
326 }
327 }
328}
SVFBasicBlock * getSVFBasicBlock(const BasicBlock *bb)
Definition LLVMModule.h:305
DominatorTree & getDomTree(const Function *fun)
const Map< const SVFBasicBlock *, BBSet > & getPostDomTreeMap() const
const Map< const SVFBasicBlock *, BBSet > & getDomFrontierMap() const
Map< const SVFBasicBlock *, BBSet > & getDomTreeMap()
const Map< const SVFBasicBlock *, u32_t > & getBBPDomLevel() const
const Map< const SVFBasicBlock *, const SVFBasicBlock * > & getBB2PIdom() const
void setReachableBBs(BBList &bbs)
Set< const SVFBasicBlock * > BBSet
void addToBB2LoopMap(const SVFBasicBlock *bb, const SVFBasicBlock *loopBB)
#define NULL
Definition extapi.c:5
void getFunReachableBBs(const Function *svfFun, std::vector< const SVFBasicBlock * > &bbs)
Get reachable basic block from function entry.
Definition LLVMUtil.cpp:76
llvm::LoopInfo LoopInfo
Definition BasicTypes.h:142
llvm::DomTreeNode DomTreeNode
Definition BasicTypes.h:135
llvm::PostDominatorTree PostDominatorTree
Definition BasicTypes.h:137
llvm::DominanceFrontier DominanceFrontier
Definition BasicTypes.h:136
llvm::Loop Loop
LLVM Loop.
Definition BasicTypes.h:141
llvm::DominatorTree DominatorTree
LLVM Dominators.
Definition BasicTypes.h:134

◆ initFunObjVar()

void PAGBuilder::initFunObjVar ( )

Function

set realDefFun for all functions

Definition at line 191 of file PAGBuilder.cpp.

192{
193 for (Module& mod : llvmModuleSet()->getLLVMModules())
194 {
196 for (const Function& f : mod.functions())
197 {
198 FunObjVar* svffun = const_cast<FunObjVar*>(llvmModuleSet()->getFunObjVar(&f));
200
201 if (!LLVMUtil::isExtCall(&f))
202 {
203 initDomTree(svffun, &f);
204 }
206 const Function *realfun = llvmModuleSet()->getRealDefFun(&f);
207 svffun->setRelDefFun(realfun == nullptr ? nullptr : llvmModuleSet()->getFunObjVar(realfun));
208 }
209 }
210
211 // Store annotations of functions in extapi.bc
212 for (const auto& pair : llvmModuleSet()->ExtFun2Annotations)
213 {
215 }
216
217}
void setExtFuncAnnotations(const FunObjVar *fun, const std::vector< std::string > &funcAnnotations)
Definition ExtAPI.cpp:199
void setRelDefFun(const FunObjVar *real)
const Function * getRealDefFun(const Function *fun) const
Definition LLVMModule.h:192
void initDomTree(FunObjVar *func, const Function *f)
void initSVFBasicBlock(const Function *func)
bool isExtCall(const Function *fun)
Definition LLVMUtil.cpp:385

◆ InitialGlobal()

void PAGBuilder::InitialGlobal ( const GlobalVariable * gvar,
Constant * C,
u32_t offset )
protected

src should not point to anything yet

Definition at line 903 of file PAGBuilder.cpp.

905{
906 DBOUT(DPAGBuild, outs() << "global " << LLVMUtil::dumpValue(gvar)
907 << " constant initializer: "
908 << LLVMUtil::dumpValue(C) << "\n");
909 if (C->getType()->isSingleValueType())
910 {
911 NodeID src = getValueNode(C);
912 // get the field value if it is available, otherwise we create a dummy field node.
913 setCurrentLocation(gvar, (SVFBasicBlock*) nullptr);
914 NodeID field = getGlobalVarField(gvar, offset, llvmModuleSet()->getSVFType(C->getType()));
915
917 {
918 setCurrentLocation(C, (SVFBasicBlock*) nullptr);
919 addStoreEdge(src, field);
920 }
921 else if (SVFUtil::isa<ConstantExpr>(C))
922 {
923 // add gep edge of C1 itself is a constant expression
924 processCE(C);
925 setCurrentLocation(C, (SVFBasicBlock*) nullptr);
926 addStoreEdge(src, field);
927 }
928 else if (SVFUtil::isa<BlockAddress>(C))
929 {
930 // blockaddress instruction (e.g. i8* blockaddress(@run_vm, %182))
931 // is treated as constant data object for now, see LLVMUtil.h:397, SymbolTableInfo.cpp:674 and PAGBuilder.cpp:183-194
932 processCE(C);
933 setCurrentLocation(C, (SVFBasicBlock*) nullptr);
934 addAddrEdge(pag->getConstantNode(), src);
935 }
936 else
937 {
938 setCurrentLocation(C, (SVFBasicBlock*) nullptr);
939 addStoreEdge(src, field);
941 if (C->getType()->isPtrOrPtrVectorTy() && src != pag->getNullPtr())
942 addCopyEdge(pag->getNullPtr(), src, CopyStmt::COPYVAL);
943 }
944 }
946 {
948 return;
949 for (u32_t i = 0, e = C->getNumOperands(); i != e; i++)
950 {
951 u32_t off = pag->getFlattenedElemIdx(llvmModuleSet()->getSVFType(C->getType()), i);
952 InitialGlobal(gvar, SVFUtil::cast<Constant>(C->getOperand(i)), offset + off);
953 }
954 }
956 {
958 {
960 {
961 for(u32_t i = 0; i < seq->getNumElements(); i++)
962 {
963 u32_t off = pag->getFlattenedElemIdx(llvmModuleSet()->getSVFType(C->getType()), i);
964 Constant* ct = seq->getElementAsConstant(i);
965 InitialGlobal(gvar, ct, offset + off);
966 }
967 }
968 else
969 {
970 assert((SVFUtil::isa<ConstantAggregateZero, UndefValue>(data)) && "Single value type data should have been handled!");
971 }
972 }
973 }
974 else
975 {
976 //TODO:assert(SVFUtil::isa<ConstantVector>(C),"what else do we have");
977 }
978}
static const Option< bool > VtableInPAG
Definition Options.h:209
static Option< bool > ModelConsts
Definition Options.h:179
void InitialGlobal(const GlobalVariable *gvar, Constant *C, u32_t offset)
NodeID getGlobalVarField(const GlobalVariable *gvar, u32_t offset, SVFType *tpy)
bool isValVtbl(const Value *val)
A carefully crafted input such as FakeVTable _ZTV1A = {{nullptr, nullptr}}; can forge a vtable; detec...
Definition CppUtil.cpp:295
llvm::ConstantData ConstantData
Definition BasicTypes.h:114
llvm::Constant Constant
Definition BasicTypes.h:122
llvm::ConstantDataSequential ConstantDataSequential
Definition BasicTypes.h:117

◆ initialiseAggregateReturns()

void PAGBuilder::initialiseAggregateReturns ( )
private

Discover demanded fields and preallocate output parameters, slots and snapshots before visiting instructions. See the aggregate return example in PAGBuilder.h.

Definition at line 1573 of file PAGBuilder.cpp.

1574{
1575 const auto demands = discoverAggregateReturnFields();
1576 const SVFType* pointerType = llvmModuleSet()->getSVFType(
1577 PointerType::getUnqual(llvmModuleSet()->getContext()));
1578 // Serialized points-to sets use NodeIDs. Allocate in function order,
1579 // independent of pointer-keyed hash table iteration.
1580 for (const Function* fun : llvmModuleSet()->getFunctionSet())
1581 {
1582 auto found = demands.find(fun);
1583 if (found == demands.end())
1584 continue;
1585 createAggregateReturnParams(fun, found->second, pointerType);
1586 createAggregateCallSlots(fun, pointerType);
1587 }
1588}
void createAggregateCallSlots(const Function *fun, const SVFType *pointerType)
void createAggregateReturnParams(const Function *fun, const std::set< AggregateField > &fields, const SVFType *pointerType)
AggregateReturnFields discoverAggregateReturnFields()

◆ initialiseBaseObjVars()

void PAGBuilder::initialiseBaseObjVars ( )

Definition at line 372 of file PAGBuilder.cpp.

373{
374 // Iterate over all object symbols in the symbol table
375 for (LLVMModuleSet::ValueToIDMapTy::iterator iter =
376 llvmModuleSet()->objSyms().begin(); iter != llvmModuleSet()->objSyms().end();
377 ++iter)
378 {
379 // Debug output for adding object node
380 DBOUT(DPAGBuild, outs() << "add obj node " << iter->second << "\n");
381
382 // Skip blackhole and constant symbols
383 if(iter->second == pag->blackholeSymID() || iter->second == pag->constantSymID())
384 continue;
385
386 // Get the LLVM value corresponding to the symbol
387 const Value* llvmValue = iter->first;
388
389 const ICFGNode* icfgNode = nullptr;
390 if (const Instruction* inst = SVFUtil::dyn_cast<Instruction>(llvmValue))
391 {
392 if(llvmModuleSet()->hasICFGNode(inst))
393 icfgNode = llvmModuleSet()->getICFGNode(inst);
394 }
395
396 // Check if the value is a function and add a function object node
397 if (SVFUtil::dyn_cast<Function>(llvmValue))
398 {
399 // already one
400 }
401 // Check if the value is a heap object and add a heap object node
402 else if (LLVMUtil::isHeapObj(llvmValue))
403 {
404 NodeID id = llvmModuleSet()->getObjectNode(iter->first);
405 pag->addHeapObjNode(iter->second, pag->getObjTypeInfo(id), icfgNode);
406 }
407 // Check if the value is an alloca instruction and add a stack object node
408 else if (LLVMUtil::isStackObj(llvmValue))
409 {
410 NodeID id = llvmModuleSet()->getObjectNode(iter->first);
411 pag->addStackObjNode(iter->second, pag->getObjTypeInfo(id), icfgNode);
412 }
413 else if (auto fpValue = SVFUtil::dyn_cast<ConstantFP>(llvmValue))
414 {
415 NodeID id = llvmModuleSet()->getObjectNode(iter->first);
416 pag->addConstantFPObjNode(iter->second, pag->getObjTypeInfo(id), LLVMUtil::getDoubleValue(fpValue), icfgNode);
417 }
418 else if (auto intValue = SVFUtil::dyn_cast<ConstantInt>(llvmValue))
419 {
420 NodeID id = llvmModuleSet()->getObjectNode(iter->first);
421 pag->addConstantIntObjNode(iter->second, pag->getObjTypeInfo(id), LLVMUtil::getIntegerValue(intValue), icfgNode);
422 }
423 else if (SVFUtil::isa<ConstantPointerNull>(llvmValue))
424 {
425 NodeID id = llvmModuleSet()->getObjectNode(iter->first);
426 pag->addConstantNullPtrObjNode(iter->second, pag->getObjTypeInfo(id), icfgNode);
427 }
428 else if (SVFUtil::isa<GlobalValue>(llvmValue))
429 {
430 NodeID id = llvmModuleSet()->getObjectNode(iter->first);
431 pag->addGlobalObjNode(iter->second, pag->getObjTypeInfo(id), icfgNode);
432 }
434 {
435 NodeID id = llvmModuleSet()->getObjectNode(iter->first);
436 pag->addConstantDataObjNode(iter->second, pag->getObjTypeInfo(id), icfgNode);
437 }
438 // Add a generic object node for other types of values
439 else
440 {
441 NodeID id = llvmModuleSet()->getObjectNode(iter->first);
442 pag->addObjNode(iter->second, pag->getObjTypeInfo(id), icfgNode);
443 }
444 llvmModuleSet()->addToSVFVar2LLVMValueMap(llvmValue, pag->getGNode(iter->second));
445 }
446
447}
double getDoubleValue(const ConstantFP *fpValue)
Definition LLVMUtil.h:67
bool isHeapObj(const Value *val)
Definition LLVMUtil.cpp:694
bool isStackObj(const Value *val)
Definition LLVMUtil.cpp:716

◆ initialiseNodes()

void PAGBuilder::initialiseNodes ( )

Initialize nodes and edges.

add address edges for constant nodes.

add argvalvar for svffunctions

Definition at line 531 of file PAGBuilder.cpp.

532{
533 DBOUT(DPAGBuild, outs() << "Initialise PAG Nodes ...\n");
534
535
536 pag->addBlackholeObjNode();
537 pag->addConstantObjNode();
538 pag->addBlackholePtrNode();
540
543
544 for (LLVMModuleSet::FunToIDMapTy::iterator iter =
545 llvmModuleSet()->retSyms().begin(); iter != llvmModuleSet()->retSyms().end();
546 ++iter)
547 {
548 const Value* llvmValue = iter->first;
549 // retSyms keys are Function*, not Instruction, so dyn_cast<Instruction> always fails.
550 // RetValPN represents the callee's return value, defined at FunExitICFGNode.
551 // External functions have no exit node, so keep nullptr.
552 const FunObjVar* funObjVar = llvmModuleSet()->getFunObjVar(SVFUtil::cast<Function>(llvmValue));
553 const ICFGNode* icfgNode = funObjVar->isDeclaration() ? nullptr : pag->getICFG()->getFunExitICFGNode(funObjVar);
554 DBOUT(DPAGBuild, outs() << "add ret node " << iter->second << "\n");
555 pag->addRetNode(iter->second,
556 funObjVar,
557 llvmModuleSet()->getSVFType(iter->first->getType()), icfgNode);
558 llvmModuleSet()->addToSVFVar2LLVMValueMap(llvmValue, pag->getGNode(iter->second));
559 pag->returnFunObjSymMap[funObjVar] = iter->second;
560 }
561
562 for (LLVMModuleSet::FunToIDMapTy::iterator iter =
563 llvmModuleSet()->varargSyms().begin();
564 iter != llvmModuleSet()->varargSyms().end(); ++iter)
565 {
566 const Value* llvmValue = iter->first;
567 // varargSyms keys are Function*, not Instruction.
568 // Variadic arguments are received at the function entry point.
569 // External functions have no entry node, so keep nullptr.
570 const FunObjVar* funObjVar = llvmModuleSet()->getFunObjVar(SVFUtil::cast<Function>(llvmValue));
571 const ICFGNode* icfgNode = funObjVar->isDeclaration() ? nullptr : pag->getICFG()->getFunEntryICFGNode(funObjVar);
572 DBOUT(DPAGBuild, outs() << "add vararg node " << iter->second << "\n");
573 pag->addVarargNode(iter->second,
574 funObjVar,
575 llvmModuleSet()->getSVFType(iter->first->getType()), icfgNode);
576 llvmModuleSet()->addToSVFVar2LLVMValueMap(llvmValue, pag->getGNode(iter->second));
577 pag->varargFunObjSymMap[funObjVar] = iter->second;
578 }
579
581 for (LLVMModuleSet::ValueToIDMapTy::iterator iter =
582 llvmModuleSet()->objSyms().begin(); iter != llvmModuleSet()->objSyms().end(); ++iter)
583 {
584 DBOUT(DPAGBuild, outs() << "add address edges for constant node " << iter->second << "\n");
585 const Value* val = iter->first;
586 if (isConstantObjSym(val))
587 {
588 NodeID ptr = llvmModuleSet()->getValueNode(val);
589 if(ptr!= pag->getBlkPtr() && ptr!= pag->getNullPtr())
590 {
591 setCurrentLocation(val, (SVFBasicBlock*) nullptr);
592 addAddrEdge(iter->second, ptr);
593 }
594 }
595 }
596
597 assert(pag->getTotalNodeNum() >= pag->getTotalSymNum()
598 && "not all node have been initialized!!!");
599
601 for (auto& fun: llvmModuleSet()->getFunctionSet())
602 {
603 for (const Argument& arg : fun->args())
604 {
605 const_cast<FunObjVar*>(llvmModuleSet()->getFunObjVar(fun))->addArgument(SVFUtil::cast<ArgValVar>(
606 pag->getGNode(llvmModuleSet()->getValueNode(&arg))));
607 }
608 }
609
610}
bool isDeclaration() const
FunToIDMapTy & retSyms()
Definition LLVMModule.h:281
FunToIDMapTy & varargSyms()
Definition LLVMModule.h:286
NodeID addNullPtrNode()
Add NullPtr PAGNode.
Definition PAGBuilder.h:382
void initialiseBaseObjVars()
void initialiseValVars()
bool isConstantObjSym(const Value *val)
Check whether this value points-to a constant object.
Definition CppUtil.cpp:705
llvm::Argument Argument
Definition BasicTypes.h:146

◆ initialiseValVars()

void PAGBuilder::initialiseValVars ( )

Definition at line 449 of file PAGBuilder.cpp.

450{
451 // Iterate over all value symbols in the symbol table
452 for (LLVMModuleSet::ValueToIDMapTy::iterator iter =
453 llvmModuleSet()->valSyms().begin(); iter != llvmModuleSet()->valSyms().end();
454 ++iter)
455 {
456 // Debug output for adding value node
457 DBOUT(DPAGBuild, outs() << "add val node " << iter->second << "\n");
458
459 // Skip blackhole and null pointer symbols
460 if(iter->second == pag->blkPtrSymID() || iter->second == pag->nullPtrSymID())
461 continue;
462
463 const ICFGNode* icfgNode = nullptr;
464 auto llvmValue = iter->first;
465
466 // Check if the value is a function and get its call graph node
467 if (const Function* func = SVFUtil::dyn_cast<Function>(llvmValue))
468 {
469 pag->addFunValNode(iter->second, icfgNode, llvmModuleSet()->getFunObjVar(func), llvmModuleSet()->getSVFType(llvmValue->getType()));
470 }
471 else if (auto argval = SVFUtil::dyn_cast<Argument>(llvmValue))
472 {
473 // Formal params are defined at FunEntryICFGNode (where CallPE copies actual args).
474 // External (declaration-only) functions have no entry node, so keep nullptr.
475 const FunObjVar* funObj = llvmModuleSet()->getFunObjVar(argval->getParent());
476 const ICFGNode* entryNode = funObj->isDeclaration() ? nullptr : pag->getICFG()->getFunEntryICFGNode(funObj);
477 pag->addArgValNode(
478 iter->second, argval->getArgNo(), entryNode,
479 funObj, llvmModuleSet()->getSVFType(llvmValue->getType()));
480 if (!argval->hasName())
481 pag->getGNode(iter->second)->setName("arg_" + std::to_string(argval->getArgNo()));
482 }
483 else if (auto fpValue = SVFUtil::dyn_cast<ConstantFP>(llvmValue))
484 {
485 pag->addConstantFPValNode(iter->second, LLVMUtil::getDoubleValue(fpValue), icfgNode, llvmModuleSet()->getSVFType(llvmValue->getType()));
486 }
487 else if (auto intValue = SVFUtil::dyn_cast<ConstantInt>(llvmValue))
488 {
489 pag->addConstantIntValNode(iter->second, LLVMUtil::getIntegerValue(intValue), icfgNode, llvmModuleSet()->getSVFType(llvmValue->getType()));
490 }
491 else if (SVFUtil::isa<ConstantPointerNull>(llvmValue))
492 {
493 pag->addConstantNullPtrValNode(iter->second, icfgNode, llvmModuleSet()->getSVFType(llvmValue->getType()));
494 }
495 else if (SVFUtil::isa<GlobalValue>(llvmValue))
496 {
497 // Global variables are defined at the global ICFG node.
498 pag->addGlobalValNode(iter->second, pag->getICFG()->getGlobalICFGNode(),
499 llvmModuleSet()->getSVFType(llvmValue->getType()));
500 }
502 {
503 pag->addConstantDataValNode(iter->second, icfgNode, llvmModuleSet()->getSVFType(llvmValue->getType()));
504 }
505 else if (SVFUtil::isa<InlineAsm>(llvmValue) ||
507 SVFUtil::isa<NoCFIValue>(llvmValue))
508 {
509 pag->addAsmPCValNode(iter->second, llvmModuleSet()->getSVFType(llvmValue->getType()));
510 }
511 else if (const Instruction* inst = SVFUtil::dyn_cast<Instruction>(llvmValue))
512 {
514 pag->addIntrinsicValNode(iter->second, llvmModuleSet()->getSVFType(llvmValue->getType()));
515 else
516 {
517 assert(llvmModuleSet()->hasICFGNode(inst) && "LLVM instruction is not associated with an ICFGNode");
518 icfgNode = llvmModuleSet()->getICFGNode(inst);
519 pag->addValNode(iter->second, llvmModuleSet()->getSVFType(llvmValue->getType()), icfgNode);
520 }
521 }
523 pag->getGNode(iter->second));
524 }
525}
ValueToIDMapTy & valSyms()
Definition LLVMModule.h:214
bool isIntrinsicInst(const Instruction *inst)
Return true if it is an intrinsic instruction.
Definition LLVMUtil.cpp:204

◆ initSVFBasicBlock()

void PAGBuilder::initSVFBasicBlock ( const Function * func)

set exit block: exit basic block must have no successors and have a return instruction

Definition at line 219 of file PAGBuilder.cpp.

220{
221 FunObjVar *svfFun = const_cast<FunObjVar *>(llvmModuleSet()->getFunObjVar(func));
222 for (Function::const_iterator bit = func->begin(), ebit = func->end(); bit != ebit; ++bit)
223 {
224 const BasicBlock* bb = &*bit;
225 SVFBasicBlock* svfbb = llvmModuleSet()->getSVFBasicBlock(bb);
226 for (succ_const_iterator succ_it = succ_begin(bb); succ_it != succ_end(bb); succ_it++)
227 {
228 const SVFBasicBlock* svf_scc_bb = llvmModuleSet()->getSVFBasicBlock(*succ_it);
229 svfbb->addSuccBasicBlock(svf_scc_bb);
230 }
231 for (const_pred_iterator pred_it = pred_begin(bb); pred_it != pred_end(bb); pred_it++)
232 {
233 const SVFBasicBlock* svf_pred_bb = llvmModuleSet()->getSVFBasicBlock(*pred_it);
234 svfbb->addPredBasicBlock(svf_pred_bb);
235 }
236
238 if (svfbb->getSuccessors().empty())
239 {
241 {
242 assert((LLVMUtil::functionDoesNotRet(func) ||
243 SVFUtil::isa<ReturnInst>(bb->back())) &&
244 "last inst must be return inst");
245 svfFun->setExitBlock(svfbb);
246 }
247 }
248 }
249 // For no return functions, we set the last block as exit BB
250 // This ensures that each function that has definition must have an exit BB
251 if (svfFun->hasBasicBlock() && svfFun->exitBlock == nullptr)
252 {
253 SVFBasicBlock* retBB = const_cast<SVFBasicBlock*>(svfFun->back());
254 assert((LLVMUtil::functionDoesNotRet(func) ||
255 SVFUtil::isa<ReturnInst>(&func->back().back())) &&
256 "last inst must be return inst");
257 svfFun->setExitBlock(retBB);
258 }
259}
const SVFBasicBlock * back() const
const SVFBasicBlock * exitBlock
all formal arguments of this function
void setExitBlock(SVFBasicBlock *bb)
bool hasBasicBlock() const
void addPredBasicBlock(const SVFBasicBlock *pred2)
void addSuccBasicBlock(const SVFBasicBlock *succ2)
std::vector< const SVFBasicBlock * > getSuccessors() const
bool basicBlockHasRetInst(const BasicBlock *bb)
Return true if the function has a return instruction.
Definition LLVMUtil.cpp:110
llvm::const_succ_iterator succ_const_iterator
LLVM Iterators.
Definition BasicTypes.h:274
llvm::const_pred_iterator const_pred_iterator
Definition BasicTypes.h:257

◆ llvmModuleSet()

LLVMModuleSet * SVF::PAGBuilder::llvmModuleSet ( )
inlineprivate

Definition at line 623 of file PAGBuilder.h.

624 {
626 }

◆ processCE()

void PAGBuilder::processCE ( const Value * val)
protected

Process constant expression.

Handle constant expression, and connect the gep edge

Definition at line 742 of file PAGBuilder.cpp.

743{
744 if (const Constant* ref = SVFUtil::dyn_cast<Constant>(val))
745 {
746 if (const ConstantExpr* gepce = isGepConstantExpr(ref))
747 {
748 DBOUT(DPAGBuild, outs() << "handle gep constant expression "
749 << LLVMUtil::dumpValue(ref) << "\n");
750 const Constant* opnd = gepce->getOperand(0);
751 // handle recursive constant express case (gep (bitcast (gep X 1)) 1)
752 processCE(opnd);
753 auto &GEPOp = llvm::cast<llvm::GEPOperator>(*gepce);
754 Type *pType = GEPOp.getSourceElementType();
755 AccessPath ap(0, llvmModuleSet()->getSVFType(pType));
756 bool constGep = computeGepOffset(gepce, ap);
757 // must invoke pag methods here, otherwise it will be a dead recursion cycle
758 const Value* cval = getCurrentValue();
759 const SVFBasicBlock* cbb = getCurrentBB();
760 setCurrentLocation(gepce, (SVFBasicBlock*) nullptr);
761 /*
762 * The gep edge created are like constexpr (same edge may appear at multiple callsites)
763 * so bb/inst of this edge may be rewritten several times, we treat it as global here.
764 */
765 addGepEdge(llvmModuleSet()->getValueNode(opnd), llvmModuleSet()->getValueNode(gepce), ap, constGep);
766 setCurrentLocation(cval, cbb);
767 }
768 else if (const ConstantExpr* castce = isCastConstantExpr(ref))
769 {
770 DBOUT(DPAGBuild, outs() << "handle cast constant expression "
771 << LLVMUtil::dumpValue(ref) << "\n");
772 const Constant* opnd = castce->getOperand(0);
773 processCE(opnd);
774 const Value* cval = getCurrentValue();
775 const SVFBasicBlock* cbb = getCurrentBB();
776 setCurrentLocation(castce, (SVFBasicBlock*) nullptr);
778 setCurrentLocation(cval, cbb);
779 }
780 else if (const ConstantExpr* selectce = isSelectConstantExpr(ref))
781 {
782 DBOUT(DPAGBuild, outs() << "handle select constant expression "
783 << LLVMUtil::dumpValue(ref) << "\n");
784 const Constant* src1 = selectce->getOperand(1);
785 const Constant* src2 = selectce->getOperand(2);
786 processCE(src1);
787 processCE(src2);
788 const Value* cval = getCurrentValue();
789 const SVFBasicBlock* cbb = getCurrentBB();
790 setCurrentLocation(selectce, (SVFBasicBlock*) nullptr);
791 NodeID cond = llvmModuleSet()->getValueNode(selectce->getOperand(0));
792 NodeID nsrc1 = llvmModuleSet()->getValueNode(src1);
793 NodeID nsrc2 = llvmModuleSet()->getValueNode(src2);
794 NodeID nres = llvmModuleSet()->getValueNode(selectce);
795 addSelectStmt(nres,nsrc1, nsrc2, cond);
796 setCurrentLocation(cval, cbb);
797 }
798 // if we meet a int2ptr, then it points-to black hole
799 else if (const ConstantExpr* int2Ptrce = isInt2PtrConstantExpr(ref))
800 {
801 const Constant* opnd = int2Ptrce->getOperand(0);
802 processCE(opnd);
803 const SVFBasicBlock* cbb = getCurrentBB();
804 const Value* cval = getCurrentValue();
805 setCurrentLocation(int2Ptrce, (SVFBasicBlock*) nullptr);
807 setCurrentLocation(cval, cbb);
808 }
809 else if (const ConstantExpr* ptr2Intce = isPtr2IntConstantExpr(ref))
810 {
811 const Constant* opnd = ptr2Intce->getOperand(0);
812 processCE(opnd);
813 const SVFBasicBlock* cbb = getCurrentBB();
814 const Value* cval = getCurrentValue();
815 setCurrentLocation(ptr2Intce, (SVFBasicBlock*) nullptr);
817 setCurrentLocation(cval, cbb);
818 }
819 else if(isTruncConstantExpr(ref) || isCmpConstantExpr(ref))
820 {
821 // we don't handle trunc and cmp instruction for now
822 const Value* cval = getCurrentValue();
823 const SVFBasicBlock* cbb = getCurrentBB();
824 setCurrentLocation(ref, (SVFBasicBlock*) nullptr);
825 NodeID dst = llvmModuleSet()->getValueNode(ref);
827 setCurrentLocation(cval, cbb);
828 }
829 else if (isBinaryConstantExpr(ref))
830 {
831 // we don't handle binary constant expression like add(x,y) now
832 const Value* cval = getCurrentValue();
833 const SVFBasicBlock* cbb = getCurrentBB();
834 setCurrentLocation(ref, (SVFBasicBlock*) nullptr);
835 NodeID dst = llvmModuleSet()->getValueNode(ref);
837 setCurrentLocation(cval, cbb);
838 }
839 else if (isUnaryConstantExpr(ref))
840 {
841 // we don't handle unary constant expression like fneg(x) now
842 const Value* cval = getCurrentValue();
843 const SVFBasicBlock* cbb = getCurrentBB();
844 setCurrentLocation(ref, (SVFBasicBlock*) nullptr);
845 NodeID dst = llvmModuleSet()->getValueNode(ref);
847 setCurrentLocation(cval, cbb);
848 }
850 {
851 // we don't handle constant aggregate like constant vectors
852 }
853 else if (SVFUtil::isa<BlockAddress>(ref))
854 {
855 // blockaddress instruction (e.g. i8* blockaddress(@run_vm, %182))
856 // is treated as constant data object for now, see LLVMUtil.h:397, SymbolTableInfo.cpp:674 and PAGBuilder.cpp:183-194
857 const Value* cval = getCurrentValue();
858 const SVFBasicBlock* cbb = getCurrentBB();
859 setCurrentLocation(ref, (SVFBasicBlock*) nullptr);
860 NodeID dst = llvmModuleSet()->getValueNode(ref);
861 addAddrEdge(pag->getConstantNode(), dst);
862 setCurrentLocation(cval, cbb);
863 }
864 else
865 {
867 assert(false && "we don't handle all other constant expression for now!");
868 }
869 }
870}
bool computeGepOffset(const User *V, AccessPath &ap)
Compute offset of a gep instruction or gep constant expression.
const ConstantExpr * isBinaryConstantExpr(const Value *val)
Definition LLVMUtil.h:292
const ConstantExpr * isInt2PtrConstantExpr(const Value *val)
Definition LLVMUtil.h:227
const ConstantExpr * isSelectConstantExpr(const Value *val)
Definition LLVMUtil.h:257
const ConstantExpr * isTruncConstantExpr(const Value *val)
Definition LLVMUtil.h:267
const ConstantExpr * isPtr2IntConstantExpr(const Value *val)
Definition LLVMUtil.h:237
const ConstantExpr * isUnaryConstantExpr(const Value *val)
Definition LLVMUtil.h:303
const ConstantExpr * isCastConstantExpr(const Value *val)
Definition LLVMUtil.h:247
const ConstantExpr * isGepConstantExpr(const Value *val)
Return corresponding constant expression, otherwise return nullptr.
Definition LLVMUtil.h:217
const ConstantExpr * isCmpConstantExpr(const Value *val)
Definition LLVMUtil.h:281
llvm::ConstantExpr ConstantExpr
Definition BasicTypes.h:118

◆ sanityCheck()

void PAGBuilder::sanityCheck ( )

Sanity check for PAG.

Definition at line 2263 of file PAGBuilder.cpp.

2264{
2265 for (PAG::iterator nIter = pag->begin(); nIter != pag->end(); ++nIter)
2266 {
2267 (void) pag->getGNode(nIter->first);
2268 //TODO::
2269 // (1) every source(root) node of a pag tree should be object node
2270 // if a node has no incoming edge, but has outgoing edges
2271 // then it has to be an object node.
2272 // (2) make sure every variable should be initialized
2273 // otherwise it causes the a null pointer, the aliasing relation may not be captured
2274 // when loading a pointer value should make sure
2275 // some value has been store into this pointer before
2276 // q = load p, some value should stored into p first like store w p;
2277 // (3) make sure PAGNode should not have a const expr value (pointer should have unique def)
2278 // (4) look closely into addComplexConsForExt, make sure program locations(e.g.,inst bb)
2279 // are set correctly for dummy gepval node
2280 // (5) reduce unnecessary copy edge (const casts) and ensure correctness.
2281 }
2282}
IDToNodeMapTy::iterator iterator

◆ setCurrentBBAndValueForPAGEdge()

void PAGBuilder::setCurrentBBAndValueForPAGEdge ( PAGEdge * edge)
protected

We assume every GepValVar and its GepStmt are unique across whole program

Only the return-value Phi merges at the shared function exit. Aggregate field stores, fallback addresses and a snapshot load before an immediate return belong to the individual return instruction.

CallPE is placed at FunEntryICFGNode (phi-like merging of actual params)

CallPE is phi-like at FunEntryICFGNode. Collect it on each CallCFGEdge whose call site appears as an operand, so the edge knows which params are passed.

Definition at line 2367 of file PAGBuilder.cpp.

2368{
2369 if (PAG::pagReadFromTXT())
2370 return;
2371
2372 assert(curVal && "current Val is nullptr?");
2373 edge->setBB(curBB!=nullptr ? curBB : nullptr);
2374 edge->setValue(pag->getGNode(llvmModuleSet()->getValueNode(curVal)));
2375 ICFGNode* icfgNode = pag->getICFG()->getGlobalICFGNode();
2376 LLVMModuleSet* llvmMS = llvmModuleSet();
2378 {
2379 const FunObjVar* srcFun = edge->getSrcNode()->getFunction();
2380 const FunObjVar* dstFun = edge->getDstNode()->getFunction();
2381 if(srcFun!=nullptr && !SVFUtil::isa<RetPE>(edge) && !SVFUtil::isa<FunValVar>(edge->getSrcNode()) && !SVFUtil::isa<FunObjVar>(edge->getSrcNode()))
2382 {
2383 assert(srcFun==llvmMS->getFunObjVar(curInst->getFunction()) && "SrcNode of the PAGEdge not in the same function?");
2384 }
2385 if(dstFun!=nullptr && !SVFUtil::isa<CallPE>(edge) && !SVFUtil::isa<RetValPN>(edge->getDstNode()))
2386 {
2387 assert(dstFun==llvmMS->getFunObjVar(curInst->getFunction()) && "DstNode of the PAGEdge not in the same function?");
2388 }
2389
2392 assert(curBB && "instruction does not have a basic block??");
2393
2398 {
2399 icfgNode = pag->getICFG()->getFunExitICFGNode(llvmMS->getFunObjVar(curInst->getFunction()));
2400 }
2401 else if(const CallPE* callPE = SVFUtil::dyn_cast<CallPE>(edge))
2402 {
2404 icfgNode = const_cast<FunEntryICFGNode*>(callPE->getFunEntryICFGNode());
2405 }
2406 else if(SVFUtil::isa<RetPE>(edge))
2407 {
2408 icfgNode = llvmMS->getRetICFGNode(SVFUtil::cast<Instruction>(curInst));
2409 }
2410 else
2411 {
2412 icfgNode = llvmMS->getICFGNode(SVFUtil::cast<Instruction>(curInst));
2413 }
2414 }
2415 else if (const Argument* arg = SVFUtil::dyn_cast<Argument>(curVal))
2416 {
2417 assert(curBB && (curBB->getParent()->getEntryBlock() == curBB));
2418 icfgNode = pag->getICFG()->getFunEntryICFGNode(
2419 llvmModuleSet()->getFunObjVar(SVFUtil::cast<Function>(arg->getParent())));
2420 }
2421 else if (SVFUtil::isa<Constant>(curVal) ||
2424 {
2425 if (!curBB)
2426 pag->addGlobalPAGEdge(edge);
2427 else
2428 {
2429 icfgNode = const_cast<ICFGNode*>(curBB->front());
2430 }
2431 }
2432 else
2433 {
2434 assert(false && "what else value can we have?");
2435 }
2436
2437 pag->addToSVFStmtList(icfgNode,edge);
2438 icfgNode->addSVFStmt(edge);
2439 if(const CallPE* callPE = SVFUtil::dyn_cast<CallPE>(edge))
2440 {
2443 FunEntryICFGNode* entryNode = const_cast<FunEntryICFGNode*>(callPE->getFunEntryICFGNode());
2444 for(u32_t i = 0; i < callPE->getOpVarNum(); i++)
2445 {
2446 CallICFGNode* callNode = const_cast<CallICFGNode*>(callPE->getOpCallICFGNode(i));
2447 if(ICFGEdge* icfgEdge = pag->getICFG()->hasInterICFGEdge(callNode, entryNode, ICFGEdge::CallCF))
2448 SVFUtil::cast<CallCFGEdge>(icfgEdge)->addCallPE(callPE);
2449 }
2450 }
2451 else if(const RetPE* retPE = SVFUtil::dyn_cast<RetPE>(edge))
2452 {
2453 RetICFGNode* retNode = const_cast<RetICFGNode*>(retPE->getCallSite()->getRetICFGNode());
2454 FunExitICFGNode* exitNode = const_cast<FunExitICFGNode*>(retPE->getFunExitICFGNode());
2455 if(ICFGEdge* edge = pag->getICFG()->hasInterICFGEdge(exitNode, retNode, ICFGEdge::RetCF))
2456 SVFUtil::cast<RetCFGEdge>(edge)->addRetPE(retPE);
2457 }
2458}
NodeType * getSrcNode() const
NodeType * getDstNode() const
void addSVFStmt(const SVFStmt *edge)
Definition ICFGNode.h:111
RetICFGNode * getRetICFGNode(const Instruction *cs)
get a return node
static bool pagReadFromTXT()
Definition PAG.h:281
void setBB(const SVFBasicBlock *bb)
void setValue(const SVFVar *val)
Get/set methods for llvm instruction.
virtual const FunObjVar * getFunction() const
Get containing function, or null for globals/constants.

◆ setCurrentLocation() [1/2]

void SVF::PAGBuilder::setCurrentLocation ( const Value * val,
const BasicBlock * bb )
inlineprotected

Set current basic block in order to keep track of control flow information.

Definition at line 352 of file PAGBuilder.h.

353 {
354 curBB = (bb == nullptr? nullptr : llvmModuleSet()->getSVFBasicBlock(bb));
355 curVal = (val == nullptr ? nullptr: val);
356 }

◆ setCurrentLocation() [2/2]

void SVF::PAGBuilder::setCurrentLocation ( const Value * val,
const SVFBasicBlock * bb )
inlineprotected

Definition at line 357 of file PAGBuilder.h.

358 {
359 curBB = bb;
360 curVal = val;
361 }

◆ updateCallGraph()

void PAGBuilder::updateCallGraph ( CallGraph * callgraph)

connect PAG edges based on callgraph

Definition at line 2228 of file PAGBuilder.cpp.

2229{
2230 CallGraph::CallEdgeMap::const_iterator iter = callgraph->getIndCallMap().begin();
2231 CallGraph::CallEdgeMap::const_iterator eiter = callgraph->getIndCallMap().end();
2232 for (; iter != eiter; iter++)
2233 {
2234 const CallICFGNode* callBlock = iter->first;
2235 const CallBase* callbase = SVFUtil::cast<CallBase>(llvmModuleSet()->getLLVMValue(callBlock));
2236 assert(callBlock->isIndirectCall() && "this is not an indirect call?");
2237 const CallGraph::FunctionSet& functions = iter->second;
2238 for (CallGraph::FunctionSet::const_iterator func_iter = functions.begin(); func_iter != functions.end(); func_iter++)
2239 {
2240 const Function* callee = SVFUtil::cast<Function>(llvmModuleSet()->getLLVMValue(*func_iter));
2241
2242 if (isExtCall(*func_iter))
2243 {
2244 setCurrentLocation(callee, callee->empty() ? nullptr : &callee->getEntryBlock());
2245 handleExtCall(callbase, callee);
2246 }
2247 else
2248 {
2249 setCurrentLocation(llvmModuleSet()->getLLVMValue(callBlock), callBlock->getBB());
2250 handleDirectCall(const_cast<CallBase*>(callbase), callee);
2251 }
2252 }
2253 }
2254
2255 // dump PAG
2257 pag->dump("pag_final");
2258}
CallEdgeMap & getIndCallMap()
Get callees from an indirect callsite.
Definition CallGraph.h:331
Set< const FunObjVar * > FunctionSet
Definition CallGraph.h:247
bool isIndirectCall() const
Return true if this is an indirect call.
Definition ICFGNode.h:465
virtual const SVFBasicBlock * getBB() const
Return the basic block of this ICFGNode.
Definition ICFGNode.h:81
virtual void handleExtCall(const CallBase *cs, const Function *callee)
void handleDirectCall(CallBase *cs, const Function *F)
Handle direct call.

◆ visitAllocaInst()

void PAGBuilder::visitAllocaInst ( AllocaInst & inst)
virtual

Our visit overrides.

Visit alloca instructions Add edge V (dst) <– O (src), V here is a value node on PAG, O is object node on PAG

Definition at line 1037 of file PAGBuilder.cpp.

1038{
1039
1040 // AllocaInst should always be a pointer type
1041 assert(SVFUtil::isa<PointerType>(inst.getType()));
1042
1044 outs() << "process alloca " << LLVMUtil::dumpValue(&inst) << "\n");
1045 NodeID dst = getValueNode(&inst);
1046
1047 NodeID src = getObjectNode(&inst);
1048
1049 addAddrWithStackArraySz(src, dst, inst);
1050
1051}
NodeID getObjectNode(const Value *V)
GetObject - Return the object node (stack/global/heap/function) according to a LLVM Value.
Definition PAGBuilder.h:203
AddrStmt * addAddrWithStackArraySz(NodeID src, NodeID dst, llvm::AllocaInst &inst)
Add Address edge from allocinst with arraysize like "%4 = alloca i8, i64 3".
Definition PAGBuilder.h:417

◆ visitAtomicCmpXchgInst()

void SVF::PAGBuilder::visitAtomicCmpXchgInst ( AtomicCmpXchgInst & I)
inline

Definition at line 296 of file PAGBuilder.h.

297 {
299 }

◆ visitAtomicRMWInst()

void SVF::PAGBuilder::visitAtomicRMWInst ( AtomicRMWInst & I)
inline

Definition at line 300 of file PAGBuilder.h.

301 {
303 }

◆ visitBinaryOperator()

void PAGBuilder::visitBinaryOperator ( BinaryOperator & inst)

Visit Binary Operator

Definition at line 1177 of file PAGBuilder.cpp.

1178{
1179 NodeID dst = getValueNode(&inst);
1180 assert(inst.getNumOperands() == 2 && "not two operands for BinaryOperator?");
1181 Value* op1 = inst.getOperand(0);
1182 NodeID op1Node = getValueNode(op1);
1183 Value* op2 = inst.getOperand(1);
1184 NodeID op2Node = getValueNode(op2);
1185 u32_t opcode = inst.getOpcode();
1186 addBinaryOPEdge(op1Node, op2Node, dst, opcode);
1187}
void addBinaryOPEdge(NodeID op1, NodeID op2, NodeID dst, u32_t opcode)
Add Copy edge.
Definition PAGBuilder.h:541

◆ visitBranchInst()

void PAGBuilder::visitBranchInst ( BranchInst & inst)

Branch and switch instructions are treated as UnaryOP br cmp label if.then, label if.else

set conditional svf var

Definition at line 1843 of file PAGBuilder.cpp.

1844{
1845 NodeID brinst = getValueNode(&inst);
1846 NodeID cond;
1847 if (inst.isConditional())
1848 cond = getValueNode(inst.getCondition());
1849 else
1850 cond = pag->getNullPtr();
1851
1852 assert(inst.getNumSuccessors() <= 2 && "if/else has more than two branches?");
1853
1855 std::vector<const Instruction*> nextInsts;
1856 LLVMUtil::getNextInsts(&inst, nextInsts);
1857 u32_t branchID = 0;
1858 for (const Instruction* succInst : nextInsts)
1859 {
1860 assert(branchID <= 1 && "if/else has more than two branches?");
1861 const ICFGNode* icfgNode = llvmModuleSet()->getICFGNode(succInst);
1862 successors.push_back(std::make_pair(icfgNode, 1-branchID));
1863 branchID++;
1864 }
1865 addBranchStmt(brinst, cond, successors);
1867 if (inst.isConditional())
1868 {
1869 for (auto& edge : llvmModuleSet()->getICFGNode(&inst)->getOutEdges())
1870 {
1871 if (IntraCFGEdge* intraEdge = SVFUtil::dyn_cast<IntraCFGEdge>(edge))
1872 {
1873 intraEdge->setConditionVar(pag->getGNode(cond));
1874 }
1875 }
1876 }
1877}
std::vector< std::pair< const ICFGNode *, s64_t > > SuccAndCondPairVec
void addBranchStmt(NodeID br, NodeID cond, const BranchStmt::SuccAndCondPairVec &succs)
Add Branch statement.
Definition PAGBuilder.h:553

◆ visitCallBrInst()

void PAGBuilder::visitCallBrInst ( CallBrInst & I)

Definition at line 1245 of file PAGBuilder.cpp.

1246{
1247 visitCallSite(&i);
1248}
void visitCallSite(CallBase *cs)

◆ visitCallInst()

void PAGBuilder::visitCallInst ( CallInst & I)

Definition at line 1235 of file PAGBuilder.cpp.

1236{
1237 visitCallSite(&i);
1238}

◆ visitCallSite()

void PAGBuilder::visitCallSite ( CallBase * cs)

Collect callsite arguments and returns

Definition at line 1253 of file PAGBuilder.cpp.

1254{
1255
1256 // skip llvm intrinsics
1257 if(isIntrinsicInst(cs))
1258 return;
1259
1261 outs() << "process callsite " << LLVMUtil::dumpValue(cs) << "\n");
1262
1263 CallICFGNode* callBlockNode = llvmModuleSet()->getCallICFGNode(cs);
1264 RetICFGNode* retBlockNode = llvmModuleSet()->getRetICFGNode(cs);
1265
1266 pag->addCallSite(callBlockNode);
1267
1269 for (u32_t i = 0; i < cs->arg_size(); i++)
1270 pag->addCallSiteArgs(
1271 callBlockNode,
1272 pag->getValVar(getValueNode(cs->getArgOperand(i))));
1273
1274 if(!cs->getType()->isVoidTy())
1275 pag->addCallSiteRets(retBlockNode,pag->getValVar(getValueNode(cs)));
1276
1277 if (const auto* call = SVFUtil::dyn_cast<CallInst>(cs))
1279
1280 if (callBlockNode->isVirtualCall())
1281 {
1282 const Value* value = cppUtil::getVCallVtblPtr(cs);
1283 callBlockNode->setVtablePtr(pag->getGNode(getValueNode(value)));
1284 }
1285 if (const Function *callee = LLVMUtil::getCallee(cs))
1286 {
1287 if (LLVMUtil::isExtCall(callee))
1288 {
1289 handleExtCall(cs, callee);
1290 }
1291 else
1292 {
1293 handleDirectCall(cs, callee);
1294 }
1295 }
1296 else
1297 {
1298 //If the callee was not identified as a function (null F), this is indirect.
1299 handleIndCall(cs);
1300 }
1301}
bool isVirtualCall() const
Definition ICFGNode.h:510
void setVtablePtr(SVFVar *v)
Definition ICFGNode.h:515
void addAggregateCallFields(const CallInst *call)
void handleIndCall(CallBase *cs)
Handle indirect call.
const Function * getCallee(const CallBase *cs)
Definition LLVMUtil.h:110
const Value * getVCallVtblPtr(const CallBase *cs)
Definition CppUtil.cpp:570

◆ visitCastInst()

void PAGBuilder::visitCastInst ( CastInst & I)

Definition at line 1162 of file PAGBuilder.cpp.

1163{
1164
1166 outs() << "process cast " << LLVMUtil::dumpValue(&inst) << "\n");
1167 NodeID dst = getValueNode(&inst);
1168
1169 const Value* opnd = inst.getOperand(0);
1170 NodeID src = getValueNode(opnd);
1171 addCopyEdge(src, dst, getCopyKind(&inst));
1172}
CopyStmt::CopyKind getCopyKind(const Value *val)
Definition PAGBuilder.h:484

◆ visitCmpInst()

void PAGBuilder::visitCmpInst ( CmpInst & inst)

Visit compare instruction

Definition at line 1205 of file PAGBuilder.cpp.

1206{
1207 NodeID dst = getValueNode(&inst);
1208 assert(inst.getNumOperands() == 2 && "not two operands for compare instruction?");
1209 Value* op1 = inst.getOperand(0);
1210 NodeID op1Node = getValueNode(op1);
1211 Value* op2 = inst.getOperand(1);
1212 NodeID op2Node = getValueNode(op2);
1213 u32_t predicate = inst.getPredicate();
1214 addCmpEdge(op1Node, op2Node, dst, predicate);
1215}
void addCmpEdge(NodeID op1, NodeID op2, NodeID dst, u32_t predict)
Add Copy edge.
Definition PAGBuilder.h:535

◆ visitExtractElementInst()

void PAGBuilder::visitExtractElementInst ( ExtractElementInst & inst)

Extract a constant pointer lane using the same field model as extractvalue. For example: a = insertelement <2 x ptr> poison, ptr p, i32 0 b = insertelement <2 x ptr> poison, ptr q, i32 0 s = select i1 cond, <2 x ptr> a, <2 x ptr> b r = extractelement <2 x ptr> s, i32 0

Lane 0 is AggregateField{0}: its copies and conditional SelectStmt are defined at a, b and s, then this visitor copies the lane into r. Dynamic indices, scalable vectors and unsupported lane definitions keep the existing fallback.

Definition at line 1834 of file PAGBuilder.cpp.

1835{
1837}
void addExtractedFieldCopy(Instruction &inst)

◆ visitExtractValueInst()

void PAGBuilder::visitExtractValueInst ( ExtractValueInst & inst)

Extract a pointer from a register aggregate using its shared field definition. For example: a = insertvalue {ptr} poison, ptr p, 0 b = insertvalue {ptr} poison, ptr q, 0 s = select i1 cond, {ptr} a, {ptr} b r = extractvalue {ptr} s, 0

getAggregateFieldNode(s, {0}, field) creates field copies at a and b and a SelectStmt with cond at s. This visitor adds one CopyStmt from field to r. Further extracts of s's field 0 reuse that definition. Unsupported fields keep the existing black-hole fallback.

Definition at line 1817 of file PAGBuilder.cpp.

1818{
1820}

◆ visitFenceInst()

void SVF::PAGBuilder::visitFenceInst ( FenceInst & I)
inline

Definition at line 292 of file PAGBuilder.h.

293 {
295 }

◆ visitFreezeInst()

void PAGBuilder::visitFreezeInst ( FreezeInst & inst)

<result> = freeze ty <val> If <val> is undef or poison, ‘freeze’ returns an arbitrary, but fixed value of type ty Otherwise, this instruction is a no-op and returns the input <val>

<result> = freeze ty <val> If <val> is undef or poison, ‘freeze’ returns an arbitrary, but fixed value of type ty Otherwise, this instruction is a no-op and returns the input <val> For now, we assume <val> is never a poison or undef.

Definition at line 1984 of file PAGBuilder.cpp.

1985{
1986 NodeID dst = getValueNode(&inst);
1987 for (u32_t i = 0; i < inst.getNumOperands(); i++)
1988 {
1989 Value* opnd = inst.getOperand(i);
1990 NodeID src = getValueNode(opnd);
1991 addCopyEdge(src, dst, CopyStmt::COPYVAL);
1992 }
1993}

◆ visitGetElementPtrInst()

void PAGBuilder::visitGetElementPtrInst ( GetElementPtrInst & inst)

Visit getelementptr instructions

Definition at line 1122 of file PAGBuilder.cpp.

1123{
1124
1125 NodeID dst = getValueNode(&inst);
1126 // GetElementPtrInst should always be a pointer or a vector contains pointers
1127 // for now we don't handle vector type here
1128 if(SVFUtil::isa<VectorType>(inst.getType()))
1129 {
1131 return;
1132 }
1133
1134 assert(SVFUtil::isa<PointerType>(inst.getType()));
1135
1137 outs() << "process gep " << LLVMUtil::dumpValue(&inst) << "\n");
1138
1139 NodeID src = getValueNode(inst.getPointerOperand());
1140
1141 AccessPath ap(0, llvmModuleSet()->getSVFType(inst.getSourceElementType()));
1142 bool constGep = computeGepOffset(&inst, ap);
1143 if (constGep && ap.getConstantStructFldIdx() == 0 && !Options::ModelArrays())
1144 {
1145 const Type* baseObjType =
1146 LLVMModuleSet::getLLVMModuleSet()->getTypeInference()->inferObjType(inst.getPointerOperand());
1147 if (const auto* arrTy = SVFUtil::dyn_cast<ArrayType>(baseObjType))
1148 {
1149 if (arrTy->getElementType()->isPointerTy())
1150 {
1151 addCopyEdge(src, dst, CopyStmt::COPYVAL);
1152 return;
1153 }
1154 }
1155 }
1156 addGepEdge(src, dst, ap, constGep);
1157}

◆ visitGlobal()

void PAGBuilder::visitGlobal ( )
protected

Handle globals including (global variable and functions).

Visit global variables for building PAG

initialize global variable

initialize global functions

Definition at line 983 of file PAGBuilder.cpp.

984{
985
987 for (Module &M : llvmModuleSet()->getLLVMModules())
988 {
989 for (Module::global_iterator I = M.global_begin(), E = M.global_end(); I != E; ++I)
990 {
991 GlobalVariable *gvar = &*I;
992 NodeID idx = getValueNode(gvar);
993 NodeID obj = getObjectNode(gvar);
994
995 setCurrentLocation(gvar, (SVFBasicBlock*) nullptr);
996 addAddrEdge(obj, idx);
997
998 if (gvar->hasInitializer())
999 {
1000 Constant *C = gvar->getInitializer();
1001 DBOUT(DPAGBuild, outs() << "add global var node "
1002 << LLVMUtil::dumpValue(gvar) << "\n");
1003 InitialGlobal(gvar, C, 0);
1004 }
1005 }
1006
1007
1009 for (Module::const_iterator I = M.begin(), E = M.end(); I != E; ++I)
1010 {
1011 const Function* fun = &*I;
1012 NodeID idx = getValueNode(fun);
1013 NodeID obj = getObjectNode(fun);
1014
1015 DBOUT(DPAGBuild, outs() << "add global function node " << fun->getName().str() << "\n");
1016 setCurrentLocation(fun, (SVFBasicBlock*) nullptr);
1017 addAddrEdge(obj, idx);
1018 }
1019
1020 // Handle global aliases (due to linkage of multiple bc files), e.g., @x = internal alias @y. We need to add a copy from y to x.
1021 for (Module::alias_iterator I = M.alias_begin(), E = M.alias_end(); I != E; I++)
1022 {
1023 const GlobalAlias* alias = &*I;
1024 NodeID dst = llvmModuleSet()->getValueNode(alias);
1025 NodeID src = llvmModuleSet()->getValueNode(alias->getAliasee());
1026 processCE(alias->getAliasee());
1027 setCurrentLocation(alias, (SVFBasicBlock*) nullptr);
1028 addCopyEdge(src, dst, CopyStmt::COPYVAL);
1029 }
1030 }
1031}
llvm::GlobalAlias GlobalAlias
Definition BasicTypes.h:129

◆ visitInsertElementInst()

void SVF::PAGBuilder::visitInsertElementInst ( InsertElementInst & I)
inline

Keep the whole vector defined for full-SVFG consumers. getAggregateFieldNode models supported pointer lanes separately; those definitions do not read this fallback.

Definition at line 272 of file PAGBuilder.h.

273 {
275 }

◆ visitInsertValueInst()

void SVF::PAGBuilder::visitInsertValueInst ( InsertValueInst & I)
inline

Keep the whole aggregate defined for full-SVFG consumers. getAggregateFieldNode models demanded pointer fields separately; those definitions do not read this fallback.

Definition at line 243 of file PAGBuilder.h.

244 {
246 }

◆ visitInstruction()

void SVF::PAGBuilder::visitInstruction ( Instruction & )
inline

Provide base case for our instruction visit.

Definition at line 306 of file PAGBuilder.h.

307 {
308 // If a new instruction is added to LLVM that we don't handle.
309 // TODO: ignore here:
310 }

◆ visitInvokeInst()

void PAGBuilder::visitInvokeInst ( InvokeInst & II)

Definition at line 1240 of file PAGBuilder.cpp.

1241{
1242 visitCallSite(&i);
1243}

◆ visitLandingPadInst()

void SVF::PAGBuilder::visitLandingPadInst ( LandingPadInst & I)
inline

Definition at line 280 of file PAGBuilder.h.

281 {
283 }

◆ visitLoadInst()

void PAGBuilder::visitLoadInst ( LoadInst & I)

Definition at line 1082 of file PAGBuilder.cpp.

1083{
1085 outs() << "process load " << LLVMUtil::dumpValue(&inst) << "\n");
1086
1087 NodeID dst = getValueNode(&inst);
1088
1089 NodeID src = getValueNode(inst.getPointerOperand());
1090 const Type* loadedTy = inst.getType();
1091 if (NodeID fieldZero = getDirectAccessFieldZeroValVar(inst.getPointerOperand(), loadedTy))
1092 src = fieldZero;
1093
1094 addLoadEdge(src, dst);
1095}

◆ visitPHINode()

void PAGBuilder::visitPHINode ( PHINode & inst)

Visit phi instructions

Definition at line 1056 of file PAGBuilder.cpp.

1057{
1058
1060 outs() << "process phi " << LLVMUtil::dumpValue(&inst) << "\n");
1061
1062 NodeID dst = getValueNode(&inst);
1063
1064 for (u32_t i = 0; i < inst.getNumIncomingValues(); ++i)
1065 {
1066 const Value* val = inst.getIncomingValue(i);
1067 const Instruction* incomingInst = SVFUtil::dyn_cast<Instruction>(val);
1068 bool matched = (incomingInst == nullptr ||
1069 incomingInst->getFunction() == inst.getFunction());
1070 (void) matched; // Suppress warning of unused variable under release build
1071 assert(matched && "incomingInst's Function incorrect");
1072 const Instruction* predInst = &inst.getIncomingBlock(i)->back();
1073 const ICFGNode* icfgNode = llvmModuleSet()->getICFGNode(predInst);
1074 NodeID src = getValueNode(val);
1075 addPhiStmt(dst,src,icfgNode);
1076 }
1077}

◆ visitResumeInst()

void SVF::PAGBuilder::visitResumeInst ( ResumeInst & )
inline

Instruction not that often.

Definition at line 286 of file PAGBuilder.h.

287 {
288 }

◆ visitReturnInst()

void PAGBuilder::visitReturnInst ( ReturnInst & inst)

Visit return instructions of a function

Definition at line 1306 of file PAGBuilder.cpp.

1307{
1308
1309 // ReturnInst itself should always not be a pointer type
1310 assert(!SVFUtil::isa<PointerType>(inst.getType()));
1311
1313 outs() << "process return " << LLVMUtil::dumpValue(&inst) << "\n");
1314
1316
1317 if(Value* src = inst.getReturnValue())
1318 {
1319 const FunObjVar *F = llvmModuleSet()->getFunObjVar(inst.getParent()->getParent());
1320
1321 NodeID rnF = getReturnNode(F);
1322 NodeID vnS = getValueNode(src);
1323 const ICFGNode* icfgNode = llvmModuleSet()->getICFGNode(&inst);
1324 //vnS may be null if src is a null ptr
1325 addPhiStmt(rnF,vnS,icfgNode);
1326 }
1327}
void addAggregateReturnStores(ReturnInst &inst)

◆ visitSelectInst()

void PAGBuilder::visitSelectInst ( SelectInst & inst)

Visit select instructions

Two operands have same incoming basic block, both are the current BB

Definition at line 1221 of file PAGBuilder.cpp.

1222{
1223
1225 outs() << "process select " << LLVMUtil::dumpValue(&inst) << "\n");
1226
1227 NodeID dst = getValueNode(&inst);
1228 NodeID src1 = getValueNode(inst.getTrueValue());
1229 NodeID src2 = getValueNode(inst.getFalseValue());
1230 NodeID cond = getValueNode(inst.getCondition());
1232 addSelectStmt(dst,src1,src2, cond);
1233}

◆ visitShuffleVectorInst()

void SVF::PAGBuilder::visitShuffleVectorInst ( ShuffleVectorInst & I)
inline

Definition at line 276 of file PAGBuilder.h.

277 {
279 }

◆ visitStoreInst()

void PAGBuilder::visitStoreInst ( StoreInst & inst)

Visit store instructions

Definition at line 1100 of file PAGBuilder.cpp.

1101{
1102 // StoreInst itself should always not be a pointer type
1103 assert(!SVFUtil::isa<PointerType>(inst.getType()));
1104
1106 outs() << "process store " << LLVMUtil::dumpValue(&inst) << "\n");
1107
1108 NodeID dst = getValueNode(inst.getPointerOperand());
1109 const Type* storedTy = inst.getValueOperand()->getType();
1110 if (NodeID fieldZero = getDirectAccessFieldZeroValVar(inst.getPointerOperand(), storedTy))
1111 dst = fieldZero;
1112
1113 NodeID src = getValueNode(inst.getValueOperand());
1114
1115 addStoreEdge(src, dst);
1116
1117}

◆ visitSwitchInst()

void PAGBuilder::visitSwitchInst ( SwitchInst & inst)

Preserve LLVM switch destinations and case values in BranchStmt.

See more: https://github.com/SVF-tools/SVF/pull/1191

Given the code:

switch (a) { case 0: printf("0\n"); break; case 1: case 2: case 3: printf("a >=1 && a <= 3\n"); break; case 4: case 6: case 7: printf("a >= 4 && a <=7\n"); break; default: printf("a < 0 || a > 7"); break; }

Generate the IR:

switch i32 %0, label sw.default [ i32 0, label sw.bb i32 1, label sw.bb1 i32 2, label sw.bb1 i32 3, label sw.bb1 i32 4, label sw.bb3 i32 6, label sw.bb3 i32 7, label sw.bb3 ]

We can get every case basic block and related case value: [ {sw.default, -1}, {sw.bb, 0}, {sw.bb1, 1}, {sw.bb1, 2}, {sw.bb1, 3}, {sw.bb3, 4}, {sw.bb3, 6}, {sw.bb3, 7}, ] Note: default case value is nullptr

set conditional svf var

Definition at line 1922 of file PAGBuilder.cpp.

1923{
1924 NodeID brinst = getValueNode(&inst);
1925 NodeID cond = getValueNode(inst.getCondition());
1926
1928 std::vector<const Instruction*> nextInsts;
1929 // Resolve each LLVM successor to its first non-intrinsic instruction.
1930 LLVMUtil::getNextInsts(&inst, nextInsts);
1931
1932 // Record default first and -1 is the getSuccessorCondValue(default iter, usually 0)
1933 successors.emplace_back(llvmModuleSet()->getICFGNode(nextInsts.front()), -1);
1934
1935 // switch (x) {
1936 // case 1:
1937 // case 2: work(); break;
1938 // default: other(); break;
1939 // }
1940 // Both cases jump to the same call instruction, work(). Keep two records
1941 // for that call's ICFG node: one with case value 1, one with case value 2.
1942 // findCaseDest() returns nullptr for a block shared by multiple cases.
1943 // Read the value from each case, not from its destination block.
1944 for (const auto& switchCase : inst.cases())
1945 {
1946 const ConstantInt* condVal = switchCase.getCaseValue();
1947 s64_t val = -1;
1948 if (condVal->getBitWidth() <= 64)
1949 val = LLVMUtil::getIntegerValue(condVal).first;
1950 // In the example, both cases resolve to the same call to work().
1951 const Instruction* succInst = nextInsts[switchCase.getSuccessorIndex()];
1952 const ICFGNode* icfgNode = llvmModuleSet()->getICFGNode(succInst);
1953 successors.push_back(std::make_pair(icfgNode, val));
1954 }
1955 addBranchStmt(brinst, cond, successors);
1957 for (auto& edge : llvmModuleSet()->getICFGNode(&inst)->getOutEdges())
1958 {
1959 if (IntraCFGEdge* intraEdge = SVFUtil::dyn_cast<IntraCFGEdge>(edge))
1960 {
1961 intraEdge->setConditionVar(pag->getGNode(cond));
1962 }
1963 }
1964}
signed long long s64_t
Definition GeneralType.h:70

◆ visitUnaryOperator()

void PAGBuilder::visitUnaryOperator ( UnaryOperator & inst)

Visit Unary Operator

Definition at line 1192 of file PAGBuilder.cpp.

1193{
1194 NodeID dst = getValueNode(&inst);
1195 assert(inst.getNumOperands() == 1 && "not one operand for Unary instruction?");
1196 Value* opnd = inst.getOperand(0);
1197 NodeID src = getValueNode(opnd);
1198 u32_t opcode = inst.getOpcode();
1199 addUnaryOPEdge(src, dst, opcode);
1200}
void addUnaryOPEdge(NodeID src, NodeID dst, u32_t opcode)
Add Unary edge.
Definition PAGBuilder.h:547

◆ visitUnreachableInst()

void SVF::PAGBuilder::visitUnreachableInst ( UnreachableInst & )
inline

Definition at line 289 of file PAGBuilder.h.

290 {
291 }

◆ visitVAArgInst()

void PAGBuilder::visitVAArgInst ( VAArgInst & inst)

TODO: var arguments need to be handled. https://llvm.org/docs/LangRef.html#id1911

ap = alloca struct.va_list ap2 = bitcast struct.va_list* ap to i8* ; Read a single integer argument from ap2 tmp = va_arg i8* ap2, i32 (VAArgInst) TODO: for now, create a copy edge from ap2 to tmp, we assume here tmp should point to the n-th argument of the var_args

Definition at line 1972 of file PAGBuilder.cpp.

1973{
1974 NodeID dst = getValueNode(&inst);
1975 Value* opnd = inst.getPointerOperand();
1976 NodeID src = getValueNode(opnd);
1977 addCopyEdge(src, dst, CopyStmt::COPYVAL);
1978}

◆ visitVACopyInst()

void SVF::PAGBuilder::visitVACopyInst ( VACopyInst & )
inline

Definition at line 258 of file PAGBuilder.h.

258{}

◆ visitVAEndInst()

void SVF::PAGBuilder::visitVAEndInst ( VAEndInst & )
inline

Definition at line 259 of file PAGBuilder.h.

259{}

◆ visitVAStartInst()

void SVF::PAGBuilder::visitVAStartInst ( VAStartInst & )
inline

Definition at line 260 of file PAGBuilder.h.

260{}

◆ GraphDBSVFIRBuilder

friend class GraphDBSVFIRBuilder
friend

Definition at line 51 of file PAGBuilder.h.

Member Data Documentation

◆ aggregateCallArgs

Map<const CallInst*, std::map<AggregateField, NodeID> > SVF::PAGBuilder::aggregateCallArgs
private

Slot addresses that each call to a modeled callee passes as output arguments, in field-path order, including calls with unused results. visitCallSite appends them after the call's ordinary arguments.

Definition at line 135 of file PAGBuilder.h.

◆ aggregateFieldNodes

Map<AggregateFieldKey, NodeID> SVF::PAGBuilder::aggregateFieldNodes
private

Reuse the same scalar PAG node for repeated requests for a field.

Definition at line 66 of file PAGBuilder.h.

◆ aggregateReturnParams

Map<const Function*, std::map<AggregateField, NodeID> > SVF::PAGBuilder::aggregateReturnParams
private

Output parameters of each modeled callee, in field-path order.

Carry a pointer field from a returned aggregate to its extraction. C example (Clang 21, x86-64 Linux, -O1; noinline preserves the call): struct Pair { int *first, *second; }; attribute((noinline)) struct Pair make(int *p, int *q) { return (struct Pair){p, q}; } int *first(int *p, int *q) { struct Pair a = make(p, q); return a.first; } Corresponding LLVM IR (names simplified, attributes omitted): define {ptr, ptr} @make(ptr p, ptr q) { r0 = insertvalue {ptr, ptr} poison, ptr p, 0 r1 = insertvalue {ptr, ptr} r0, ptr q, 1 ret {ptr, ptr} r1 } define ptr @first(ptr p, ptr q) { a = tail call {ptr, ptr} @make(ptr p, ptr q) x = extractvalue {ptr, ptr} a, 0 ret ptr x } Only field {0} is extracted. For this call, the field uses three distinct PAG nodes: obj: a pointer-sized DummyObjVar, called the return slot. This is synthetic storage, not the Pair object or an LLVM alloca. A: a DummyValVar pointing to obj, passed to make. V: a DummyValVar holding the pointer loaded from obj after the call; later uses read V without reloading obj. Each static callsite has its own obj/A/V for each demanded field. make also gets a synthetic output ArgValVar, named out_obj below. Using symbolic node names, the field transport is shown below; ordinary argument/return edges and whole-aggregate fallback edges are omitted: first's call: A = Addr(obj) make's entry: CallPE(A, out_obj) make's r0: F0 = Copy(p) make's r1: F1 = Copy(F0) make's return: Store(F1, out_obj) first's x: V = Load(A); x = Copy(V) insertvalue creates a new aggregate: r0 = {p, poison}, r1 = {p, q}. The second insertion preserves field {0}. F0 models (r0, {0}) and F1 models (r1, {0}); field {1} is not extracted here, so it needs no separate field node. The snapshot load precedes the extraction copy at the same continuation. aggregateReturnParams[make][{0}] holds out_obj. aggregateCallArgs[a][{0}] holds A, and aggregateFieldNodes[(a, {0})] holds V. obj, Addr(obj) and Load(A) are created before instructions are visited; V is loaded at x, the instruction after the call. All calls to make append their own A to match out_obj, even with unused results. More demanded fields follow field-path order. These additions affect only PAG; the LLVM signatures above do not change.

Definition at line 131 of file PAGBuilder.h.

◆ curBB

const SVFBasicBlock* SVF::PAGBuilder::curBB
private

Current basic block during PAG construction when visiting the module.

Definition at line 55 of file PAGBuilder.h.

◆ curVal

const Value* SVF::PAGBuilder::curVal
private

Current Value during PAG construction when visiting the module.

Definition at line 56 of file PAGBuilder.h.

◆ pag

PAG* SVF::PAGBuilder::pag
private

Definition at line 54 of file PAGBuilder.h.


The documentation for this class was generated from the following files: