Static Value-Flow Analysis
|
#include <SVFIRBuilder.h>
Protected Member Functions | |
void | visitGlobal (SVFModule *svfModule) |
Handle globals including (global variable and functions) More... | |
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. More... | |
u32_t | inferFieldIdxFromByteOffset (const llvm::GEPOperator *gepOp, DataLayout *dl, AccessPath &ap, APOffset idx) |
Infer field index from byteoffset. More... | |
bool | computeGepOffset (const User *V, AccessPath &ap) |
Compute offset of a gep instruction or gep constant expression. More... | |
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)) More... | |
void | handleDirectCall (CallBase *cs, const Function *F) |
Handle direct call. More... | |
void | handleIndCall (CallBase *cs) |
Handle indirect call. More... | |
virtual const Type * | getBaseTypeAndFlattenedFields (const Value *V, std::vector< AccessPath > &fields, const Value *szValue) |
Handle external call. More... | |
virtual void | addComplexConsForExt (Value *D, Value *S, const Value *sz) |
virtual void | handleExtCall (const CallBase *cs, const SVFFunction *svfCallee) |
void | setCurrentLocation (const Value *val, const BasicBlock *bb) |
Set current basic block in order to keep track of control flow information. More... | |
void | setCurrentLocation (const SVFValue *val, const SVFBasicBlock *bb) |
const SVFValue * | getCurrentValue () const |
const SVFBasicBlock * | getCurrentBB () const |
void | addGlobalBlackHoleAddrEdge (NodeID node, const ConstantExpr *int2Ptrce) |
Add global black hole Address edge. More... | |
NodeID | addNullPtrNode () |
Add NullPtr PAGNode. More... | |
NodeID | getGepValVar (const Value *val, const AccessPath &ap, const SVFType *elementType) |
void | setCurrentBBAndValueForPAGEdge (PAGEdge *edge) |
void | addBlackHoleAddrEdge (NodeID node) |
AddrStmt * | addAddrEdge (NodeID src, NodeID dst) |
Add Address edge. More... | |
AddrStmt * | addAddrWithStackArraySz (NodeID src, NodeID dst, llvm::AllocaInst &inst) |
Add Address edge from allocinst with arraysize like "%4 = alloca i8, i64 3". More... | |
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)". More... | |
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. More... | |
void | addSelectStmt (NodeID res, NodeID op1, NodeID op2, NodeID cond) |
Add SelectStmt. More... | |
void | addCmpEdge (NodeID op1, NodeID op2, NodeID dst, u32_t predict) |
Add Copy edge. More... | |
void | addBinaryOPEdge (NodeID op1, NodeID op2, NodeID dst, u32_t opcode) |
Add Copy edge. More... | |
void | addUnaryOPEdge (NodeID src, NodeID dst, u32_t opcode) |
Add Unary edge. More... | |
void | addBranchStmt (NodeID br, NodeID cond, const BranchStmt::SuccAndCondPairVec &succs) |
Add Branch statement. More... | |
void | addLoadEdge (NodeID src, NodeID dst) |
Add Load edge. More... | |
void | addStoreEdge (NodeID src, NodeID dst) |
Add Store edge. More... | |
void | addCallEdge (NodeID src, NodeID dst, const CallICFGNode *cs, const FunEntryICFGNode *entry) |
Add Call edge. More... | |
void | addRetEdge (NodeID src, NodeID dst, const CallICFGNode *cs, const FunExitICFGNode *exit) |
Add Return edge. More... | |
void | addGepEdge (NodeID src, NodeID dst, const AccessPath &ap, bool constGep) |
Add Gep edge. More... | |
void | addNormalGepEdge (NodeID src, NodeID dst, const AccessPath &ap) |
Add Offset(Gep) edge. More... | |
void | addVariantGepEdge (NodeID src, NodeID dst, const AccessPath &ap) |
Add Variant(Gep) edge. More... | |
void | addThreadForkEdge (NodeID src, NodeID dst, const CallICFGNode *cs, const FunEntryICFGNode *entry) |
Add Thread fork edge for parameter passing. More... | |
void | addThreadJoinEdge (NodeID src, NodeID dst, const CallICFGNode *cs, const FunExitICFGNode *exit) |
Add Thread join edge for parameter passing. More... | |
AccessPath | getAccessPathFromBaseNode (NodeID nodeId) |
Private Member Functions | |
LLVMModuleSet * | llvmModuleSet () |
Private Attributes | |
SVFIR * | pag |
SVFModule * | svfModule |
const SVFBasicBlock * | curBB |
Current basic block during SVFIR construction when visiting the module. More... | |
const SVFValue * | curVal |
Current Value during SVFIR construction when visiting the module. More... | |
SVFIR Builder to create SVF variables and statements and PAG
Definition at line 46 of file SVFIRBuilder.h.
|
inline |
Constructor.
Definition at line 57 of file SVFIRBuilder.h.
|
inlinevirtual |
Add Address edge.
Definition at line 292 of file SVFIRBuilder.h.
|
inlineprotected |
Add Address edge from ext call with args like "%5 = call i8* @malloc(i64 noundef 5)".
Definition at line 315 of file SVFIRBuilder.h.
|
inlineprotected |
Add Address edge from allocinst with arraysize like "%4 = alloca i8, i64 3".
Definition at line 303 of file SVFIRBuilder.h.
|
inlineprotected |
Add Copy edge.
Definition at line 427 of file SVFIRBuilder.h.
|
inlineprotected |
Definition at line 285 of file SVFIRBuilder.h.
|
inlineprotected |
Add Branch statement.
Definition at line 439 of file SVFIRBuilder.h.
|
inlineprotected |
Add Call edge.
Definition at line 463 of file SVFIRBuilder.h.
|
inlineprotected |
Add Copy edge.
Definition at line 421 of file SVFIRBuilder.h.
|
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 78 of file SVFIRExtAPI.cpp.
|
inlineprotected |
Definition at line 361 of file SVFIRBuilder.h.
void SVF::SVFIRBuilder::addEdge | ( | NodeID | src, |
NodeID | dst, | ||
SVFStmt::PEDGEK | kind, | ||
APOffset | offset = 0 , |
||
Instruction * | cs = nullptr |
||
) |
|
inlineprotected |
Add Gep edge.
Definition at line 475 of file SVFIRBuilder.h.
|
inlineprotected |
Add global black hole Address edge.
Definition at line 261 of file SVFIRBuilder.h.
Add Load edge.
Definition at line 445 of file SVFIRBuilder.h.
|
inlineprotected |
Add Offset(Gep) edge.
Definition at line 481 of file SVFIRBuilder.h.
|
inlineprotected |
Add NullPtr PAGNode.
Definition at line 271 of file SVFIRBuilder.h.
|
inlineprotected |
Add Copy edge.
If we already added this phi node, then skip this adding
Definition at line 408 of file SVFIRBuilder.h.
|
inlineprotected |
Add Return edge.
Definition at line 469 of file SVFIRBuilder.h.
|
inlineprotected |
Add SelectStmt.
Definition at line 415 of file SVFIRBuilder.h.
Add Store edge.
Definition at line 451 of file SVFIRBuilder.h.
|
inlineprotected |
Add Thread fork edge for parameter passing.
Definition at line 493 of file SVFIRBuilder.h.
|
inlineprotected |
Add Thread join edge for parameter passing.
Definition at line 499 of file SVFIRBuilder.h.
Add Unary edge.
Definition at line 433 of file SVFIRBuilder.h.
|
inlineprotected |
Add Variant(Gep) edge.
Definition at line 487 of file SVFIRBuilder.h.
|
virtual |
Start building SVFIR here.
Start building SVFIR here
initial external library information initial SVFIR nodes
initial SVFIR edges: // handle globals
handle functions
collect return node of function fun
Return SVFIR 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 SVFIR imported by commandline?
Definition at line 54 of file SVFIRBuilder.cpp.
|
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 299 of file SVFIRBuilder.cpp.
|
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 1390 of file SVFIRBuilder.cpp.
|
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
Definition at line 43 of file SVFIRExtAPI.cpp.
Get the base value of (i8* src and i8* dst) for external argument (e.g. memcpy(i8* dst, i8* src, int size))
Definition at line 1163 of file SVFIRBuilder.cpp.
|
inlineprotected |
Definition at line 371 of file SVFIRBuilder.h.
|
inlineprotected |
Definition at line 255 of file SVFIRBuilder.h.
|
inlineprotected |
Definition at line 251 of file SVFIRBuilder.h.
|
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 1254 of file SVFIRBuilder.cpp.
|
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 504 of file SVFIRBuilder.cpp.
GetObject - Return the object node (stack/global/heap/function) according to a LLVM Value.
Definition at line 98 of file SVFIRBuilder.h.
|
inline |
|
inline |
getReturnNode - Return the node representing the unique return value of a function.
Definition at line 105 of file SVFIRBuilder.h.
Get different kinds of node.
Definition at line 87 of file SVFIRBuilder.h.
|
inline |
getVarargNode - Return the node representing the unique variadic argument of a function.
Definition at line 111 of file SVFIRBuilder.h.
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 1100 of file SVFIRBuilder.cpp.
|
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/SVFIR/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 SVFIR edges for thread joins
Definition at line 124 of file SVFIRExtAPI.cpp.
|
protected |
Handle indirect call.
Indirect call is resolved on-the-fly during pointer analysis
Definition at line 1184 of file SVFIRBuilder.cpp.
|
protected |
Infer field index from byteoffset.
Definition at line 288 of file SVFIRBuilder.cpp.
|
protected |
src should not point to anything yet
Definition at line 531 of file SVFIRBuilder.cpp.
void SVFIRBuilder::initialiseNodes | ( | ) |
Initialize nodes and edges.
add address edges for constant nodes.
Definition at line 200 of file SVFIRBuilder.cpp.
|
inlineprivate |
Definition at line 509 of file SVFIRBuilder.h.
|
protected |
Process constant expression.
Handle constant expression, and connect the gep edge
Definition at line 373 of file SVFIRBuilder.cpp.
void SVFIRBuilder::sanityCheck | ( | ) |
Sanity check for SVFIR.
Definition at line 1228 of file SVFIRBuilder.cpp.
|
protected |
We assume every GepValVar and its GepStmt are unique across whole program
We will have one unique function exit ICFGNode for all returns
Definition at line 1302 of file SVFIRBuilder.cpp.
|
inlineprotected |
Definition at line 246 of file SVFIRBuilder.h.
|
inlineprotected |
Set current basic block in order to keep track of control flow information.
Definition at line 241 of file SVFIRBuilder.h.
void SVFIRBuilder::updateCallGraph | ( | PTACallGraph * | callgraph | ) |
connect PAG edges based on callgraph
Definition at line 1192 of file SVFIRBuilder.cpp.
|
virtual |
Our visit overrides.
Visit alloca instructions Add edge V (dst) <– O (src), V here is a value node on SVFIR, O is object node on SVFIR
Definition at line 662 of file SVFIRBuilder.cpp.
|
inline |
Definition at line 186 of file SVFIRBuilder.h.
|
inline |
Definition at line 190 of file SVFIRBuilder.h.
void SVFIRBuilder::visitBinaryOperator | ( | BinaryOperator & | inst | ) |
Visit Binary Operator
Definition at line 777 of file SVFIRBuilder.cpp.
void SVFIRBuilder::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 955 of file SVFIRBuilder.cpp.
void SVFIRBuilder::visitCallBrInst | ( | CallBrInst & | I | ) |
Definition at line 844 of file SVFIRBuilder.cpp.
void SVFIRBuilder::visitCallInst | ( | CallInst & | I | ) |
Definition at line 834 of file SVFIRBuilder.cpp.
void SVFIRBuilder::visitCallSite | ( | CallBase * | cs | ) |
Collect callsite arguments and returns
Definition at line 852 of file SVFIRBuilder.cpp.
void SVFIRBuilder::visitCastInst | ( | CastInst & | I | ) |
Definition at line 763 of file SVFIRBuilder.cpp.
void SVFIRBuilder::visitCmpInst | ( | CmpInst & | inst | ) |
Visit compare instruction
Definition at line 805 of file SVFIRBuilder.cpp.
void SVFIRBuilder::visitExtractElementInst | ( | ExtractElementInst & | inst | ) |
The �extractelement� instruction extracts a single scalar element from a vector at a specified index. TODO: for now we just assume the pointer after extraction points to blackhole The first operand of an �extractelement� instruction is a value of vector type. The second operand is an index indicating the position from which to extract the element.
<result> = extractelement <4 x i32> vec, i32 0 ; yields i32
Definition at line 945 of file SVFIRBuilder.cpp.
void SVFIRBuilder::visitExtractValueInst | ( | ExtractValueInst & | inst | ) |
visit extract value instructions for structures in registers TODO: for now we just assume the pointer after extraction points to blackhole for example %24 = extractvalue { i32, struct.s_hash* } call34, 0 %24 is a pointer points to first field of a register value call34 however we can not create call34 as an memory object, as it is register value. Is that necessary treat extract value as getelementptr instruction later to get more precise results?
Definition at line 931 of file SVFIRBuilder.cpp.
|
inline |
Definition at line 182 of file SVFIRBuilder.h.
void SVFIRBuilder::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 1085 of file SVFIRBuilder.cpp.
void SVFIRBuilder::visitGetElementPtrInst | ( | GetElementPtrInst & | inst | ) |
Visit getelementptr instructions
Definition at line 737 of file SVFIRBuilder.cpp.
|
protected |
Handle globals including (global variable and functions)
Visit global variables for building SVFIR
initialize global variable
initialize global functions
Definition at line 609 of file SVFIRBuilder.cpp.
|
inline |
Definition at line 162 of file SVFIRBuilder.h.
|
inline |
Definition at line 136 of file SVFIRBuilder.h.
|
inline |
Provide base case for our instruction visit.
Definition at line 196 of file SVFIRBuilder.h.
void SVFIRBuilder::visitInvokeInst | ( | InvokeInst & | II | ) |
Definition at line 839 of file SVFIRBuilder.cpp.
|
inline |
Definition at line 170 of file SVFIRBuilder.h.
void SVFIRBuilder::visitLoadInst | ( | LoadInst & | I | ) |
Definition at line 705 of file SVFIRBuilder.cpp.
void SVFIRBuilder::visitPHINode | ( | PHINode & | inst | ) |
Visit phi instructions
Definition at line 680 of file SVFIRBuilder.cpp.
|
inline |
void SVFIRBuilder::visitReturnInst | ( | ReturnInst & | inst | ) |
Visit return instructions of a function
Definition at line 902 of file SVFIRBuilder.cpp.
void SVFIRBuilder::visitSelectInst | ( | SelectInst & | inst | ) |
Visit select instructions
Two operands have same incoming basic block, both are the current BB
Definition at line 821 of file SVFIRBuilder.cpp.
|
inline |
Definition at line 166 of file SVFIRBuilder.h.
void SVFIRBuilder::visitStoreInst | ( | StoreInst & | inst | ) |
Visit store instructions
Definition at line 719 of file SVFIRBuilder.cpp.
void SVFIRBuilder::visitSwitchInst | ( | SwitchInst & | inst | ) |
The following implementation follows ICFGBuilder::processFunBody.
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 For larger number, we preserve case value just -1 now see more: https://github.com/SVF-tools/SVF/pull/992
branch condition value
default case is set to -1;
set conditional svf var
Definition at line 1037 of file SVFIRBuilder.cpp.
void SVFIRBuilder::visitUnaryOperator | ( | UnaryOperator & | inst | ) |
Visit Unary Operator
Definition at line 792 of file SVFIRBuilder.cpp.
|
inline |
Definition at line 179 of file SVFIRBuilder.h.
void SVFIRBuilder::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 1073 of file SVFIRBuilder.cpp.
|
inline |
Definition at line 151 of file SVFIRBuilder.h.
|
inline |
Definition at line 152 of file SVFIRBuilder.h.
|
inline |
Definition at line 153 of file SVFIRBuilder.h.
|
private |
Current basic block during SVFIR construction when visiting the module.
Definition at line 52 of file SVFIRBuilder.h.
|
private |
Current Value during SVFIR construction when visiting the module.
Definition at line 53 of file SVFIRBuilder.h.
|
private |
Definition at line 50 of file SVFIRBuilder.h.
|
private |
Definition at line 51 of file SVFIRBuilder.h.