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

#include <SymbolTableBuilder.h>

Public Member Functions

 SymbolTableBuilder (PAG *pag)
 Constructor.
void buildMemModel ()
 Start building memory model.
u32_t getNumOfElements (const Type *ety)
 Return size of this object based on LLVM value.

Protected Member Functions

void collectSVFTypeInfo (const Value *val)
 collect the syms
void collectSym (const Value *val)
void collectVal (const Value *val)
void collectObj (const Value *val)
void collectRet (const Function *val)
void collectVararg (const Function *val)
void handleGlobalCE (const GlobalVariable *G)
 Handle constant expression.
void handleGlobalInitializerCE (const Constant *C)
void handleCE (const Value *val)
LLVMModuleSet * llvmModuleSet ()
ObjTypeInference * getTypeInference ()
const Type * inferObjType (const Value *startValue)
 Forward collect all possible infer sites starting from a value.
const Type * inferTypeOfHeapObjOrStaticObj (const Instruction *inst)
 Get the reference type of heap/static object from an allocation site.
ObjTypeInfo * createObjTypeInfo (const Value *val)
 Create an objectInfo based on LLVM value.
void initTypeInfo (ObjTypeInfo *typeinfo, const Value *value, const Type *ty)
 Initialize TypeInfo based on LLVM Value.
void analyzeObjType (ObjTypeInfo *typeinfo, const Value *val)
 Analyse types of all flattened fields of this object.
u32_t analyzeHeapObjType (ObjTypeInfo *typeinfo, const Value *val)
 Analyse types of heap and static objects.
void analyzeStaticObjType (ObjTypeInfo *typeinfo, const Value *val)
 Analyse types of heap and static objects.
u32_t analyzeHeapAllocByteSize (const Value *val)
 Analyze byte size of heap alloc function (e.g. malloc/calloc/...).
u32_t getNumOfFlattenElements (const Type *T)
 Number of flattened elements of an array or struct.
StInfo * getOrAddSVFTypeInfo (const Type *T)
 Get a reference to StructInfo.
ObjTypeInfo * createBlkObjTypeInfo (NodeID symId)
ObjTypeInfo * createConstantObjTypeInfo (NodeID symId)

Private Attributes

PAG * pag

Friends

class PAGBuilder

Detailed Description

Definition at line 44 of file SymbolTableBuilder.h.

Constructor & Destructor Documentation

◆ SymbolTableBuilder()

SVF::SymbolTableBuilder::SymbolTableBuilder ( PAG * pag)
inline

Constructor.

Definition at line 52 of file SymbolTableBuilder.h.

52 : pag(pag)
53 {
54 }

Member Function Documentation

◆ analyzeHeapAllocByteSize()

u32_t SymbolTableBuilder::analyzeHeapAllocByteSize ( const Value * val)
protected

Analyze byte size of heap alloc function (e.g. malloc/calloc/...).

Analyze byte size of heap alloc function (e.g. malloc/calloc/...) 1) attribute((annotate("ALLOC_HEAP_RET"), annotate("AllocSize:Arg0"))) void* safe_malloc(unsigned long size). Byte Size is the size(Arg0) 2)__attribute__((annotate("ALLOC_HEAP_RET"), annotate("AllocSize:Arg0*Arg1"))) char* safecalloc(int a, int b) Byte Size is a(Arg0) * b(Arg1) 3)__attribute__((annotate("ALLOC_HEAP_RET"), annotate("UNKNOWN"))) void* __sysv_signal(int a, void *b) Byte Size is Unknown If all required arg values are constant, byte Size is also constant, otherwise return ByteSize 0

Definition at line 734 of file SymbolTableBuilder.cpp.

735{
736 if(const llvm::CallInst* callInst = llvm::dyn_cast<llvm::CallInst>(val))
737 {
738 if (const llvm::Function* calledFunction =
739 callInst->getCalledFunction())
740 {
741 std::vector<const Value*> args;
742 // Heap alloc functions have annoation like "AllocSize:Arg1"
743 for (std::string annotation : llvmModuleSet()->getExtFuncAnnotations(calledFunction))
744 {
745 if (annotation.find("AllocSize:") != std::string::npos)
746 {
747 std::string allocSize = annotation.substr(10);
748 std::stringstream ss(allocSize);
749 std::string token;
750 // Analyaze annotation string and attract Arg list
751 while (std::getline(ss, token, '*'))
752 {
753 if (token.rfind("Arg", 0) == 0)
754 {
755 u32_t argIndex;
756 std::istringstream(token.substr(3)) >> argIndex;
757 if (argIndex < callInst->getNumOperands() - 1)
758 {
759 args.push_back(
760 callInst->getArgOperand(argIndex));
761 }
762 }
763 }
764 }
765 }
766 u64_t product = 1;
767 if (args.size() > 0)
768 {
769 // for annotations like "AllocSize:Arg0*Arg1"
770 for (const llvm::Value* arg : args)
771 {
772 if (const llvm::ConstantInt* constIntArg =
773 llvm::dyn_cast<llvm::ConstantInt>(arg))
774 {
775 // Multiply the constant Value if all Args are const
776 product *= LLVMUtil::getIntegerValue(constIntArg).second;
777 }
778 else
779 {
780 // if Arg list has non-const value, return 0 to indicate it is non const byte size
781 return 0;
782 }
783 }
784 // If all the Args are const, return product
785 return product;
786 }
787 else
788 {
789 // for annotations like "AllocSize:UNKNOWN"
790 return 0;
791 }
792 }
793 }
794 // if it is not CallInst or CallInst has no CalledFunction, return 0 to indicate it is non const byte size
795 return 0;
796}
LLVMModuleSet * llvmModuleSet()
std::pair< s64_t, u64_t > getIntegerValue(const ConstantInt *intValue)
Definition LLVMUtil.h:95
unsigned long long u64_t
Definition GeneralType.h:69
unsigned u32_t
Definition GeneralType.h:67

◆ analyzeHeapObjType()

u32_t SymbolTableBuilder::analyzeHeapObjType ( ObjTypeInfo * typeinfo,
const Value * val )
protected

Analyse types of heap and static objects.

Analyse types of heap and static objects

For an C++ class, it can have variant elements depending on the vtable size, Hence we only handle non-cpp-class object, the type of the cpp class is treated as default PointerType

Definition at line 801 of file SymbolTableBuilder.cpp.

802{
804 analyzeObjType(typeinfo, val);
805 const Type* objTy = llvmModuleSet()->getLLVMType(typeinfo->getType());
806 if(SVFUtil::isa<ArrayType>(objTy))
807 return getNumOfElements(objTy);
808 else if(const StructType* st = SVFUtil::dyn_cast<StructType>(objTy))
809 {
813 typeinfo->resetTypeForHeapStaticObj(llvmModuleSet()->getSVFType(
814 llvmModuleSet()->getTypeInference()->ptrType()));
815 else
816 return getNumOfElements(objTy);
817 }
818 return typeinfo->getMaxFieldOffsetLimit();
819}
const Type * getLLVMType(const SVFType *T) const
Get LLVM Type.
void resetTypeForHeapStaticObj(const SVFType *t)
Definition ObjTypeInfo.h:79
u32_t getMaxFieldOffsetLimit()
Get max field offset limit.
const SVFType * getType() const
Get LLVM type.
Definition ObjTypeInfo.h:99
void setFlag(MEMTYPE mask)
Flag for this object type.
ObjTypeInference * getTypeInference()
u32_t getNumOfElements(const Type *ety)
Return size of this object based on LLVM value.
void analyzeObjType(ObjTypeInfo *typeinfo, const Value *val)
Analyse types of all flattened fields of this object.
LLVM_NODISCARD bool isa(const Y &Val)
Definition Casting.h:241
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
bool classTyHasVTable(const StructType *ty)
Definition CppUtil.cpp:602
llvm::Type Type
Definition BasicTypes.h:81
llvm::StructType StructType
LLVM types.
Definition BasicTypes.h:92

◆ analyzeObjType()

void SymbolTableBuilder::analyzeObjType ( ObjTypeInfo * typeinfo,
const Value * val )
protected

Analyse types of all flattened fields of this object.

Analyse types of all flattened fields of this object

Definition at line 693 of file SymbolTableBuilder.cpp.

694{
695 const Type *elemTy = llvmModuleSet()->getLLVMType(typeinfo->getType());
696 // Find the inter nested array element
697 while (const ArrayType* AT = SVFUtil::dyn_cast<ArrayType>(elemTy))
698 {
699 elemTy = AT->getElementType();
701 SVFUtil::cast<GlobalVariable>(val)->hasInitializer() &&
703 SVFUtil::cast<GlobalVariable>(val)->getInitializer()))
705 else
707 }
708 if (SVFUtil::isa<StructType>(elemTy))
709 {
711 SVFUtil::cast<GlobalVariable>(val)->hasInitializer() &&
713 SVFUtil::cast<GlobalVariable>(val)->getInitializer()))
715 else
717 }
718}
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::ArrayType ArrayType
Definition BasicTypes.h:93

◆ analyzeStaticObjType()

void SymbolTableBuilder::analyzeStaticObjType ( ObjTypeInfo * typeinfo,
const Value * val )
protected

Analyse types of heap and static objects.

Analyse types of heap and static objects

Definition at line 824 of file SymbolTableBuilder.cpp.

825{
826 if(const Value* castUse = getFirstUseViaCastInst(val))
827 {
829 analyzeObjType(typeinfo,castUse);
830 }
831 else
832 {
834 }
835}
const Value * getFirstUseViaCastInst(const Value *val)
Definition LLVMUtil.cpp:279
llvm::Value Value
LLVM Basic classes.
Definition BasicTypes.h:80

◆ buildMemModel()

void SymbolTableBuilder::buildMemModel ( )

Start building memory model.

This method identify which is value sym and which is object sym

if (SVFUtil::isa<InlineAsm>(Callee))

Definition at line 80 of file SymbolTableBuilder.cpp.

81{
83
84 // Pointer #0 always represents the null pointer.
85 assert(pag->totalSymNum++ == PAGBase::NullPtr && "Something changed!");
86
87 // Pointer #1 always represents the pointer points-to black hole.
88 assert(pag->totalSymNum++ == PAGBase::BlkPtr && "Something changed!");
89
90 // Object #2 is black hole the object that may point to any object
91 assert(pag->totalSymNum++ == PAGBase::BlackHole && "Something changed!");
93
94 // Object #3 always represents the unique constant of a program (merging all constants if Options::ModelConsts is disabled)
95 assert(pag->totalSymNum++ == PAGBase::ConstantObj && "Something changed!");
97
98 for (Module &M : llvmModuleSet()->getLLVMModules())
99 {
100 // Add symbols for all the globals .
101 for (const GlobalVariable& gv : M.globals())
102 {
103 collectSym(&gv);
104 }
105
106 // Add symbols for all the global aliases
107 for (const GlobalAlias& ga : M.aliases())
108 {
109 collectSym(&ga);
110 collectSym(ga.getAliasee());
111 }
112
113 // Add symbols for all of the functions and the instructions in them.
114 for (const Function& fun : M.functions())
115 {
116 collectSym(&fun);
117 collectRet(&fun);
118 if (fun.getFunctionType()->isVarArg())
119 collectVararg(&fun);
120
121 // Add symbols for all formal parameters.
122 for (const Argument& arg : fun.args())
123 {
124 collectSym(&arg);
125 }
126
127 // collect and create symbols inside the function body
128 for (const Instruction& inst : instructions(fun))
129 {
130 collectSym(&inst);
131
132 // initialization for some special instructions
133 //{@
134 if (const StoreInst* st = SVFUtil::dyn_cast<StoreInst>(&inst))
135 {
136 collectSym(st->getPointerOperand());
137 collectSym(st->getValueOperand());
138 }
139 else if (const LoadInst* ld =
141 {
142 collectSym(ld->getPointerOperand());
143 }
144 else if (const AllocaInst* alloc =
146 {
147 collectSym(alloc->getArraySize());
148 }
149 else if (const PHINode* phi = SVFUtil::dyn_cast<PHINode>(&inst))
150 {
151 for (u32_t i = 0; i < phi->getNumIncomingValues(); ++i)
152 {
153 collectSym(phi->getIncomingValue(i));
154 }
155 }
156 else if (const GetElementPtrInst* gep =
158 {
159 collectSym(gep->getPointerOperand());
160 for (u32_t i = 0; i < gep->getNumOperands(); ++i)
161 {
162 collectSym(gep->getOperand(i));
163 }
164 }
165 else if (const SelectInst* sel =
167 {
168 collectSym(sel->getTrueValue());
169 collectSym(sel->getFalseValue());
170 collectSym(sel->getCondition());
171 }
172 else if (const BinaryOperator* binary =
174 {
175 for (u32_t i = 0; i < binary->getNumOperands(); i++)
176 collectSym(binary->getOperand(i));
177 }
178 else if (const UnaryOperator* unary =
180 {
181 for (u32_t i = 0; i < unary->getNumOperands(); i++)
182 collectSym(unary->getOperand(i));
183 }
184 else if (const CmpInst* cmp = SVFUtil::dyn_cast<CmpInst>(&inst))
185 {
186 for (u32_t i = 0; i < cmp->getNumOperands(); i++)
187 collectSym(cmp->getOperand(i));
188 }
189 else if (const CastInst* cast =
191 {
192 collectSym(cast->getOperand(0));
193 }
194 else if (const ReturnInst* ret =
196 {
197 if (ret->getReturnValue())
198 collectSym(ret->getReturnValue());
199 }
200 else if (const BranchInst* br =
202 {
203 Value* opnd = br->isConditional() ? br->getCondition() : br->getOperand(0);
204 collectSym(opnd);
205 }
206 else if (const SwitchInst* sw =
208 {
209 collectSym(sw->getCondition());
210 }
211 else if (const FreezeInst* fz = SVFUtil::dyn_cast<FreezeInst>(&inst))
212 {
213
214 for (u32_t i = 0; i < fz->getNumOperands(); i++)
215 {
216 Value* opnd = inst.getOperand(i);
217 collectSym(opnd);
218 }
219 }
220 else if (isNonInstricCallSite(&inst))
221 {
222
223 const CallBase* cs = LLVMUtil::getLLVMCallSite(&inst);
224 for (u32_t i = 0; i < cs->arg_size(); i++)
225 {
226 collectSym(cs->getArgOperand(i));
227 }
228 // Calls to inline asm need to be added as well because the
229 // callee isn't referenced anywhere else.
230 const Value* Callee = cs->getCalledOperand();
231 collectSym(Callee);
232
233 // TODO handle inlineAsm
236 {
238 }
239 }
241 }
242 }
243 }
244
245 pag->totalSymNum = NodeIDAllocator::get()->endSymbolAllocation();
247 {
249 }
250}
static NodeIDAllocator * get(void)
Return (singleton) allocator.
NodeID endSymbolAllocation(void)
Notify the allocator that all symbols have had IDs allocated.
void validateTypeCheck(const CallBase *cs)
validate type inference
static const Option< bool > EnableTypeCheck
Definition Options.h:129
static const Option< bool > SymTabPrint
Definition Options.h:182
void collectRet(const Function *val)
ObjTypeInfo * createBlkObjTypeInfo(NodeID symId)
ObjTypeInfo * createConstantObjTypeInfo(NodeID symId)
void collectSym(const Value *val)
void collectVararg(const Function *val)
const CallBase * getLLVMCallSite(const Value *value)
Return LLVM callsite given a value.
Definition LLVMUtil.h:104
bool isNonInstricCallSite(const Instruction *inst)
Whether an instruction is a callsite in the application code, excluding llvm intrinsic calls.
Definition LLVMUtil.cpp:732
void increaseStackSize()
Increase the stack size limit.
Definition SVFUtil.cpp:249
llvm::GlobalVariable GlobalVariable
Definition BasicTypes.h:131
llvm::GlobalAlias GlobalAlias
Definition BasicTypes.h:129
llvm::CallBase CallBase
Definition BasicTypes.h:147
llvm::UnaryOperator UnaryOperator
Definition BasicTypes.h:181
llvm::AllocaInst AllocaInst
Definition BasicTypes.h:151
llvm::SwitchInst SwitchInst
Definition BasicTypes.h:156
llvm::Argument Argument
Definition BasicTypes.h:146
llvm::LoadInst LoadInst
Definition BasicTypes.h:150
llvm::CmpInst CmpInst
Definition BasicTypes.h:160
llvm::Function Function
Definition BasicTypes.h:83
llvm::Instruction Instruction
Definition BasicTypes.h:85
llvm::CastInst CastInst
Definition BasicTypes.h:159
llvm::FreezeInst FreezeInst
Definition BasicTypes.h:170
llvm::Module Module
Definition BasicTypes.h:82
llvm::BinaryOperator BinaryOperator
Definition BasicTypes.h:180
llvm::StoreInst StoreInst
Definition BasicTypes.h:149
llvm::SelectInst SelectInst
Definition BasicTypes.h:175
llvm::GetElementPtrInst GetElementPtrInst
Definition BasicTypes.h:163
llvm::ReturnInst ReturnInst
Definition BasicTypes.h:158
llvm::PHINode PHINode
Definition BasicTypes.h:166
llvm::BranchInst BranchInst
Definition BasicTypes.h:155

◆ collectObj()

void SymbolTableBuilder::collectObj ( const Value * val)
protected

Get memory object sym, if not available create a new one

Definition at line 330 of file SymbolTableBuilder.cpp.

331{
332 val = LLVMUtil::getGlobalRep(val);
333 LLVMModuleSet::ValueToIDMapTy::iterator iter = llvmModuleSet()->objSymMap.find(val);
334 if (iter == llvmModuleSet()->objSymMap.end())
335 {
336 // if the object pointed by the pointer is a constant data (e.g., i32 0) or a global constant object (e.g. string)
337 // then we treat them as one ConstantObj
338 // the IR features can't be modelled, like Blockaddress still maps to the ConstantObj
339 const bool mcUnmodelled = isConstDataOrAggData(val) && val->getType()->isPointerTy();
340 if (isConstantObjSym(val) && (!Options::ModelConsts() || mcUnmodelled))
341 {
342 llvmModuleSet()->objSymMap.insert(std::make_pair(val, pag->constantSymID()));
343 }
344 // otherwise, we will create an object for each abstract memory location
345 else
346 {
347 // create obj sym and sym type
349 llvmModuleSet()->objSymMap.insert(std::make_pair(val, id));
351 outs() << "create a new obj sym " << id << "\n");
352
353 // create a memory object
354 ObjTypeInfo* ti = createObjTypeInfo(val);
355 assert(pag->objTypeInfoMap.find(id) == pag->objTypeInfoMap.end());
356 pag->objTypeInfoMap[id] = ti;
357 }
358 }
359}
#define DBOUT(TYPE, X)
LLVM debug macros, define type of your DBUG model of each pass.
Definition SVFType.h:576
#define DMemModel
Definition SVFType.h:585
ValueToIDMapTy objSymMap
map a obj reference to its sym id
Definition LLVMModule.h:121
NodeID allocateObjectId(void)
Allocate an object ID as determined by the strategy.
static Option< bool > ModelConsts
Definition Options.h:179
ObjTypeInfo * createObjTypeInfo(const Value *val)
Create an objectInfo based on LLVM value.
bool isConstantObjSym(const Value *val)
Check whether this value points-to a constant object.
Definition CppUtil.cpp:705
bool isConstDataOrAggData(const Value *val)
Return true if the value refers to constant data, e.g., i32 0.
Definition LLVMUtil.h:397
const Value * getGlobalRep(const Value *val)
find the unique defined global across multiple modules
Definition LLVMUtil.cpp:441
std::ostream & outs()
Overwrite llvm::outs().
Definition SVFUtil.h:58
u32_t NodeID
Definition GeneralType.h:76

◆ collectRet()

void SymbolTableBuilder::collectRet ( const Function * val)
protected

Create unique return sym, if not available create a new one

Definition at line 364 of file SymbolTableBuilder.cpp.

365{
366
367 LLVMModuleSet::FunToIDMapTy::iterator iter =
368 llvmModuleSet()->returnSymMap.find(val);
369 if (iter == llvmModuleSet()->returnSymMap.end())
370 {
372 llvmModuleSet()->returnSymMap.insert(std::make_pair(val, id));
373 DBOUT(DMemModel, outs() << "create a return sym " << id << "\n");
374 }
375}
FunToIDMapTy returnSymMap
return map
Definition LLVMModule.h:122
NodeID allocateValueId(void)
Allocate a value ID as determined by the strategy.

◆ collectSVFTypeInfo()

void SymbolTableBuilder::collectSVFTypeInfo ( const Value * val)
protected

collect the syms

Definition at line 252 of file SymbolTableBuilder.cpp.

253{
254 Type *valType = val->getType();
255 (void)getOrAddSVFTypeInfo(valType);
257 {
261 gi != ge; ++gi)
262 {
263 const Type* gepTy = *gi;
264 (void)getOrAddSVFTypeInfo(gepTy);
265 }
266 }
267}
StInfo * getOrAddSVFTypeInfo(const Type *T)
Get a reference to StructInfo.
const ConstantExpr * isGepConstantExpr(const Value *val)
Return corresponding constant expression, otherwise return nullptr.
Definition LLVMUtil.h:217
llvm::bridge_gep_iterator bridge_gep_iterator
Definition BasicTypes.h:255
bridge_gep_iterator bridge_gep_end(const User *GEP)
bridge_gep_iterator bridge_gep_begin(const User *GEP)

◆ collectSym()

void SymbolTableBuilder::collectSym ( const Value * val)
protected

Collect symbols, including value and object syms

Definition at line 272 of file SymbolTableBuilder.cpp.

273{
274
275 //TODO: filter the non-pointer type // if (!SVFUtil::isa<PointerType>(val->getType())) return;
276
278 outs() << "collect sym from ##" << LLVMUtil::dumpValue(val) << "\n");
279 //TODO handle constant expression value here??
280 handleCE(val);
281
282 // create a value sym
283 collectVal(val);
284
287
288 // create an object If it is a heap, stack, global, function.
289 if (isObject(val))
290 {
291 collectObj(val);
292 }
293}
void collectSVFTypeInfo(const Value *val)
collect the syms
void collectObj(const Value *val)
void collectVal(const Value *val)
void handleCE(const Value *val)
bool isObject(const Value *ref)
Return true if this value refers to a object.
Definition LLVMUtil.cpp:61
std::string dumpValue(const Value *val)
Definition LLVMUtil.cpp:612

◆ collectVal()

void SymbolTableBuilder::collectVal ( const Value * val)
protected

Get value sym, if not available create a new one

handle global constant expression here

Definition at line 298 of file SymbolTableBuilder.cpp.

299{
300 // collect and record special sym here
301 if (
305 )
306 {
307 return;
308 }
309
310 LLVMModuleSet::ValueToIDMapTy::iterator iter = llvmModuleSet()->valSymMap.find(val);
311 if (iter == llvmModuleSet()->valSymMap.end())
312 {
313 // create val sym and sym type
315 llvmModuleSet()->valSymMap.insert(std::make_pair(val, id));
317 outs() << "create a new value sym " << id << "\n");
319 if (const GlobalVariable* globalVar = SVFUtil::dyn_cast<GlobalVariable>(val))
320 handleGlobalCE(globalVar);
321 }
322
323 if (isConstantObjSym(val))
324 collectObj(val);
325}
ValueToIDMapTy valSymMap
map a value to its sym id
Definition LLVMModule.h:120
void handleGlobalCE(const GlobalVariable *G)
Handle constant expression.
bool isNullPtrSym(const Value *val)
Check whether this value is a black hole.
Definition LLVMUtil.h:139
bool isBlackholeSym(const Value *val)
Check whether this value is a black hole.
Definition LLVMUtil.h:133

◆ collectVararg()

void SymbolTableBuilder::collectVararg ( const Function * val)
protected

Create vararg sym, if not available create a new one

Definition at line 380 of file SymbolTableBuilder.cpp.

381{
382 LLVMModuleSet::FunToIDMapTy::iterator iter =
383 llvmModuleSet()->varargSymMap.find(val);
384 if (iter == llvmModuleSet()->varargSymMap.end())
385 {
387 llvmModuleSet()->varargSymMap.insert(std::make_pair(val, id));
388 DBOUT(DMemModel, outs() << "create a vararg sym " << id << "\n");
389 }
390}
FunToIDMapTy varargSymMap
vararg map
Definition LLVMModule.h:123

◆ createBlkObjTypeInfo()

ObjTypeInfo * SymbolTableBuilder::createBlkObjTypeInfo ( NodeID symId)
protected

Definition at line 46 of file SymbolTableBuilder.cpp.

47{
48 assert(pag->isBlkObj(symId));
49 LLVMModuleSet* llvmset = llvmModuleSet();
50 if (pag->objTypeInfoMap.find(symId)==pag->objTypeInfoMap.end())
51 {
52 ObjTypeInfo* ti = pag->createObjTypeInfo(llvmset->getSVFType(
53 IntegerType::get(llvmset->getContext(), 32)));
54 ti->setNumOfElements(0);
55 pag->objTypeInfoMap[symId] = ti;
56 }
57 ObjTypeInfo* ti = pag->objTypeInfoMap[symId];
58 return ti;
59}
SVFType * getSVFType(const Type *T)
Get or create SVFType and typeinfo.
LLVMContext & getContext() const
Definition LLVMModule.h:393
void setNumOfElements(u32_t num)
Set the number of elements of this object.

◆ createConstantObjTypeInfo()

ObjTypeInfo * SymbolTableBuilder::createConstantObjTypeInfo ( NodeID symId)
protected

Definition at line 61 of file SymbolTableBuilder.cpp.

62{
63 assert(PAGBase::isConstantSym(symId));
64 LLVMModuleSet* llvmset = llvmModuleSet();
65 if (pag->objTypeInfoMap.find(symId)==pag->objTypeInfoMap.end())
66 {
67 ObjTypeInfo* ti = pag->createObjTypeInfo(
68 llvmset->getSVFType(IntegerType::get(llvmset->getContext(), 32)));
69 ti->setNumOfElements(0);
70 pag->objTypeInfoMap[symId] = ti;
71 }
72 ObjTypeInfo* ti = pag->objTypeInfoMap[symId];
73 return ti;
74}
static bool isConstantSym(NodeID id)
Definition PAGBase.h:172

◆ createObjTypeInfo()

ObjTypeInfo * SymbolTableBuilder::createObjTypeInfo ( const Value * val)
protected

Create an objectInfo based on LLVM value.

Definition at line 624 of file SymbolTableBuilder.cpp.

625{
626 const Type* objTy = nullptr;
627
629
630 // We consider two types of objects:
631 // (1) A heap/static object from a callsite
632 if (I && isNonInstricCallSite(I))
633 {
635 }
636 // (2) Other objects (e.g., alloca, global, etc.)
637 else
638 {
639 if (SVFUtil::isa<PointerType>(val->getType()))
640 {
641 if (const AllocaInst *allocaInst = SVFUtil::dyn_cast<AllocaInst>(val))
642 {
643 // get the type of the allocated memory
644 // e.g., for `%retval = alloca i64, align 4`, we return i64
645 objTy = allocaInst->getAllocatedType();
646 }
647 else if (const GlobalValue *global = SVFUtil::dyn_cast<GlobalValue>(val))
648 {
649 // get the pointee type of the global pointer (begins with @ symbol in llvm)
650 objTy = global->getValueType();
651 }
652 else
653 {
654 SVFUtil::errs() << dumpValueAndDbgInfo(val) << "\n";
655 assert(false && "not an allocation or global?");
656 }
657 }
658 }
659
660 if (objTy)
661 {
662 (void) getOrAddSVFTypeInfo(objTy);
663 ObjTypeInfo* typeInfo = new ObjTypeInfo(
664 llvmModuleSet()->getSVFType(objTy),
666 initTypeInfo(typeInfo,val, objTy);
667 return typeInfo;
668 }
669 else
670 {
671 writeWrnMsg("try to create an object with a non-pointer type.");
672 writeWrnMsg(val->getName().str());
673 writeWrnMsg("(" + getSourceLoc(val) + ")");
674 if (isConstantObjSym(val))
675 {
676 ObjTypeInfo* typeInfo = new ObjTypeInfo(
677 llvmModuleSet()->getSVFType(val->getType()),
678 0);
679 initTypeInfo(typeInfo,val, val->getType());
680 return typeInfo;
681 }
682 else
683 {
684 assert(false && "Memory object must be either (1) held by a pointer-typed ref value or (2) a constant value (e.g., 10).");
685 abort();
686 }
687 }
688}
static const Option< u32_t > MaxFieldLimit
Maximum number of field derivations for an object.
Definition Options.h:34
const Type * inferTypeOfHeapObjOrStaticObj(const Instruction *inst)
Get the reference type of heap/static object from an allocation site.
void initTypeInfo(ObjTypeInfo *typeinfo, const Value *value, const Type *ty)
Initialize TypeInfo based on LLVM Value.
std::string dumpValueAndDbgInfo(const Value *val)
Definition LLVMUtil.cpp:634
const std::string getSourceLoc(const Value *val)
Definition LLVMUtil.cpp:454
std::ostream & errs()
Overwrite llvm::errs().
Definition SVFUtil.h:64
void writeWrnMsg(const std::string &msg)
Writes a message run through wrnMsg.
Definition SVFUtil.cpp:88
llvm::GlobalValue GlobalValue
Definition BasicTypes.h:86

◆ getNumOfElements()

u32_t SymbolTableBuilder::getNumOfElements ( const Type * ety)

Return size of this object based on LLVM value.

Return size of this Object

Definition at line 932 of file SymbolTableBuilder.cpp.

933{
934 assert(ety && "type is null?");
935 u32_t numOfFields = 1;
937 {
938 numOfFields = getNumOfFlattenElements(ety);
939 }
940 return numOfFields;
941}
u32_t getNumOfFlattenElements(const Type *T)
Number of flattened elements of an array or struct.

◆ getNumOfFlattenElements()

u32_t SymbolTableBuilder::getNumOfFlattenElements ( const Type * T)
protected

Number of flattened elements of an array or struct.

Get a reference to the components of struct_info. Number of flattened elements of an array or struct

Definition at line 944 of file SymbolTableBuilder.cpp.

945{
948 else
950}
static Option< bool > ModelArrays
Definition Options.h:180
u32_t getNumOfFlattenElements() const
Return number of elements after flattening (including array elements).
Definition SVFType.h:164
u32_t getNumOfFlattenFields() const
Return the number of fields after flattening (ignoring array elements).
Definition SVFType.h:170

◆ getOrAddSVFTypeInfo()

StInfo * SymbolTableBuilder::getOrAddSVFTypeInfo ( const Type * T)
protected

Get a reference to StructInfo.

Definition at line 952 of file SymbolTableBuilder.cpp.

953{
954 return llvmModuleSet()->getSVFType(T)->getTypeInfo();
955}
StInfo * getTypeInfo()
Definition SVFType.h:273

◆ getTypeInference()

ObjTypeInference * SymbolTableBuilder::getTypeInference ( )
protected

Definition at line 574 of file SymbolTableBuilder.cpp.

575{
577}
ObjTypeInference * getTypeInference()

◆ handleCE()

void SymbolTableBuilder::handleCE ( const Value * val)
protected

Handle constant expression

Definition at line 395 of file SymbolTableBuilder.cpp.

396{
397 if (const Constant* ref = SVFUtil::dyn_cast<Constant>(val))
398 {
399 if (const ConstantExpr* ce = isGepConstantExpr(ref))
400 {
401 DBOUT(DMemModelCE, outs() << "handle constant expression "
402 << LLVMUtil::dumpValue(ref) << "\n");
403 collectVal(ce);
404
405 // handle the recursive constant express case
406 // like (gep (bitcast (gep X 1)) 1); the inner gep is ce->getOperand(0)
407 for (u32_t i = 0; i < ce->getNumOperands(); ++i)
408 {
409 collectVal(ce->getOperand(i));
410 handleCE(ce->getOperand(i));
411 }
412 }
413 else if (const ConstantExpr* ce = isCastConstantExpr(ref))
414 {
415 DBOUT(DMemModelCE, outs() << "handle constant expression "
416 << LLVMUtil::dumpValue(ref) << "\n");
417 collectVal(ce);
418 collectVal(ce->getOperand(0));
419 // handle the recursive constant express case
420 // like (gep (bitcast (gep X 1)) 1); the inner gep is ce->getOperand(0)
421 handleCE(ce->getOperand(0));
422 }
423 else if (const ConstantExpr* ce = isSelectConstantExpr(ref))
424 {
425 DBOUT(DMemModelCE, outs() << "handle constant expression "
426 << LLVMUtil::dumpValue(ref) << "\n");
427 collectVal(ce);
428 collectVal(ce->getOperand(0));
429 collectVal(ce->getOperand(1));
430 collectVal(ce->getOperand(2));
431 // handle the recursive constant express case
432 // like (gep (bitcast (gep X 1)) 1); the inner gep is ce->getOperand(0)
433 handleCE(ce->getOperand(0));
434 handleCE(ce->getOperand(1));
435 handleCE(ce->getOperand(2));
436 }
437 // if we meet a int2ptr, then it points-to black hole
438 else if (const ConstantExpr* int2Ptrce = isInt2PtrConstantExpr(ref))
439 {
440 collectVal(int2Ptrce);
441 const Constant* opnd = int2Ptrce->getOperand(0);
442 handleCE(opnd);
443 }
444 else if (const ConstantExpr* ptr2Intce = isPtr2IntConstantExpr(ref))
445 {
446 collectVal(ptr2Intce);
447 const Constant* opnd = ptr2Intce->getOperand(0);
448 handleCE(opnd);
449 }
450 else if (isTruncConstantExpr(ref) || isCmpConstantExpr(ref))
451 {
452 collectVal(ref);
453 }
454 else if (isBinaryConstantExpr(ref))
455 {
456 collectVal(ref);
457 }
458 else if (isUnaryConstantExpr(ref))
459 {
460 // we don't handle unary constant expression like fneg(x) now
461 collectVal(ref);
462 }
464 {
465 // we don't handle constant aggregate like constant vectors
466 collectVal(ref);
467 }
468 else
469 {
470 assert(!SVFUtil::isa<ConstantExpr>(val) &&
471 "we don't handle all other constant expression for now!");
472 collectVal(ref);
473 }
474 }
475}
#define DMemModelCE
Definition SVFType.h:586
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 * isCmpConstantExpr(const Value *val)
Definition LLVMUtil.h:281
llvm::Constant Constant
Definition BasicTypes.h:122
llvm::ConstantExpr ConstantExpr
Definition BasicTypes.h:118

◆ handleGlobalCE()

void SymbolTableBuilder::handleGlobalCE ( const GlobalVariable * G)
protected

Handle constant expression.

Handle global constant expression

Definition at line 480 of file SymbolTableBuilder.cpp.

481{
482 assert(G);
483
484 //The type this global points to
485 const Type* T = G->getValueType();
486 bool is_array = 0;
487 //An array is considered a single variable of its type.
488 while (const ArrayType* AT = SVFUtil::dyn_cast<ArrayType>(T))
489 {
490 T = AT->getElementType();
491 is_array = true;
492 }
493
495 {
496 //A struct may be used in constant GEP expr.
497 for (const User* user : G->users())
498 {
499 handleCE(user);
500 }
501 }
502 else if (is_array)
503 {
504 for (const User* user : G->users())
505 {
506 handleCE(user);
507 }
508 }
509
510 if (G->hasInitializer())
511 {
512 handleGlobalInitializerCE(G->getInitializer());
513 }
514}
void handleGlobalInitializerCE(const Constant *C)
llvm::User User
Definition BasicTypes.h:143

◆ handleGlobalInitializerCE()

void SymbolTableBuilder::handleGlobalInitializerCE ( const Constant * C)
protected

Handle global variable initialization

Definition at line 519 of file SymbolTableBuilder.cpp.

520{
521
522 if (C->getType()->isSingleValueType())
523 {
525 {
526 handleCE(E);
527 }
528 else
529 {
530 collectVal(C);
531 }
532 }
533 else if (SVFUtil::isa<ConstantArray>(C))
534 {
535 for (u32_t i = 0, e = C->getNumOperands(); i != e; i++)
536 {
538 }
539 }
541 {
542 for (u32_t i = 0, e = C->getNumOperands(); i != e; i++)
543 {
545 }
546 }
547 else if(const ConstantData* data = SVFUtil::dyn_cast<ConstantData>(C))
548 {
550 {
551 if (const ConstantDataSequential* seq =
553 {
554 for(u32_t i = 0; i < seq->getNumElements(); i++)
555 {
556 const Constant* ct = seq->getElementAsConstant(i);
558 }
559 }
560 else
561 {
562 assert(
564 "Single value type data should have been handled!");
565 }
566 }
567 }
568 else
569 {
570 //TODO:assert(SVFUtil::isa<ConstantVector>(C),"what else do we have");
571 }
572}
llvm::ConstantData ConstantData
Definition BasicTypes.h:114
llvm::ConstantDataSequential ConstantDataSequential
Definition BasicTypes.h:117

◆ inferObjType()

const Type * SymbolTableBuilder::inferObjType ( const Value * startValue)
protected

Forward collect all possible infer sites starting from a value.

Definition at line 580 of file SymbolTableBuilder.cpp.

581{
582 return getTypeInference()->inferObjType(startValue);
583}
const Type * inferObjType(const Value *var)
get or infer the type of the object pointed by the value

◆ inferTypeOfHeapObjOrStaticObj()

const Type * SymbolTableBuilder::inferTypeOfHeapObjOrStaticObj ( const Instruction * inst)
protected

Get the reference type of heap/static object from an allocation site.

Return the type of the object from a heap allocation

Definition at line 588 of file SymbolTableBuilder.cpp.

589{
590 const Value* startValue = inst;
591 const PointerType *originalPType = SVFUtil::dyn_cast<PointerType>(inst->getType());
592 const Type* inferedType = nullptr;
593 assert(originalPType && "empty type?");
595 {
596 if(const Value* v = getFirstUseViaCastInst(inst))
597 {
598 if (const PointerType *newTy = SVFUtil::dyn_cast<PointerType>(v->getType()))
599 {
600 originalPType = newTy;
601 }
602 }
603 inferedType = inferObjType(startValue);
604 }
606 {
607 const CallBase* cs = LLVMUtil::getLLVMCallSite(inst);
608 u32_t arg_pos = LLVMUtil::getHeapAllocHoldingArgPosition(cs->getCalledFunction());
609 const Value* arg = cs->getArgOperand(arg_pos);
610 originalPType = SVFUtil::dyn_cast<PointerType>(arg->getType());
611 inferedType = inferObjType(startValue = arg);
612 }
613 else
614 {
615 assert( false && "not a heap allocation instruction?");
616 }
617
618 return inferedType;
619}
const Type * inferObjType(const Value *startValue)
Forward collect all possible infer sites starting from a value.
bool isHeapAllocExtCallViaRet(const Instruction *inst)
Definition LLVMUtil.cpp:645
bool isHeapAllocExtCallViaArg(const Instruction *inst)
Definition LLVMUtil.cpp:660
u32_t getHeapAllocHoldingArgPosition(const Function *fun)
Definition LLVMUtil.cpp:402
llvm::PointerType PointerType
Definition BasicTypes.h:94

◆ initTypeInfo()

void SymbolTableBuilder::initTypeInfo ( ObjTypeInfo * typeinfo,
const Value * val,
const Type * objTy )
protected

Initialize TypeInfo based on LLVM Value.

Initialize the type info of an object

if val is AllocaInst, byteSize is Type's LLVM ByteSize * ArraySize e.g. alloc i32, 10. byteSize is 4 (i32's size) * 10 (ArraySize) = 40

This is for alloca <ty> <NumElements>. For example, alloca i64 3 allocates 3 i64 on the stack (objSize=3) In most cases, NumElements is not specified in the instruction, which means there is only one element (objSize=1).

if ArraySize is not constant, byteSize is not static determined.

if val is GlobalVar, byteSize is Type's LLVM ByteSize All GlobalVariable must have constant size

if val is heap alloc

Definition at line 840 of file SymbolTableBuilder.cpp.

842{
843
844 u32_t elemNum = 1;
845 // init byteSize = 0, If byteSize is changed in the following process,
846 // it means that ObjTypeInfo has a Constant Byte Size
847 u32_t byteSize = 0;
848 // Global variable
849 // if val is Function Obj, byteSize is not set
850 if (SVFUtil::isa<Function>(val))
851 {
853 analyzeObjType(typeinfo,val);
854 elemNum = 0;
855 }
858 else if(const AllocaInst* allocaInst = SVFUtil::dyn_cast<AllocaInst>(val))
859 {
861 analyzeObjType(typeinfo,val);
864 if(const ConstantInt* sz = SVFUtil::dyn_cast<ConstantInt>(allocaInst->getArraySize()))
865 {
866 elemNum = LLVMUtil::getIntegerValue(sz).second * getNumOfElements(objTy);
867 byteSize = LLVMUtil::getIntegerValue(sz).second * typeinfo->getType()->getByteSize();
868 }
870 else
871 {
872 elemNum = getNumOfElements(objTy);
873 byteSize = 0;
874 }
875 }
878 else if(SVFUtil::isa<GlobalVariable>(val))
879 {
881 if(isConstantObjSym(val))
883 analyzeObjType(typeinfo,val);
884 elemNum = getNumOfElements(objTy);
885 byteSize = typeinfo->getType()->getByteSize();
886 }
888 else if (SVFUtil::isa<Instruction>(val) &&
891 {
892 elemNum = analyzeHeapObjType(typeinfo,val);
893 // analyze heap alloc like (malloc/calloc/...), the alloc functions have
894 // annotation like "AllocSize:Arg1". Please refer to extapi.c.
895 // e.g. calloc(4, 10), annotation is "AllocSize:Arg0*Arg1",
896 // it means byteSize = 4 (Arg0) * 10 (Arg1) = 40
897 byteSize = analyzeHeapAllocByteSize(val);
898 }
899 else if(ArgInProgEntryFunction(val))
900 {
901 analyzeStaticObjType(typeinfo,val);
902 // user input data, label its field as infinite here
903 elemNum = typeinfo->getMaxFieldOffsetLimit();
904 byteSize = typeinfo->getType()->getByteSize();
905 }
907 {
909 elemNum = getNumOfFlattenElements(val->getType());
910 byteSize = typeinfo->getType()->getByteSize();
911 }
912 else
913 {
914 assert("what other object do we have??");
915 abort();
916 }
917
918 // Reset maxOffsetLimit if it is over the total fieldNum of this object
919 if(typeinfo->getMaxFieldOffsetLimit() > elemNum)
920 typeinfo->setNumOfElements(elemNum);
921
922 // set ByteSize. If ByteSize > 0, this typeinfo has constant type.
923 // If ByteSize == 0, this typeinfo has 1) zero byte 2) non-const byte size
924 // If ByteSize>MaxFieldLimit, set MaxFieldLimit to the byteSize;
925 byteSize = Options::MaxFieldLimit() > byteSize? byteSize: Options::MaxFieldLimit();
926 typeinfo->setByteSizeOfObj(byteSize);
927}
void setByteSizeOfObj(u32_t size)
Set the byte size of this object.
u32_t getByteSize() const
Definition SVFType.h:287
u32_t analyzeHeapObjType(ObjTypeInfo *typeinfo, const Value *val)
Analyse types of heap and static objects.
u32_t analyzeHeapAllocByteSize(const Value *val)
Analyze byte size of heap alloc function (e.g. malloc/calloc/...).
void analyzeStaticObjType(ObjTypeInfo *typeinfo, const Value *val)
Analyse types of heap and static objects.
bool isHeapAllocExtCall(const Instruction *inst)
Definition LLVMUtil.h:425
bool ArgInProgEntryFunction(const Value *val)
Return true if this is an argument of a program entry function (e.g. main).
Definition LLVMUtil.h:166
llvm::ConstantInt ConstantInt
Definition BasicTypes.h:123

◆ llvmModuleSet()

LLVMModuleSet * SVF::SymbolTableBuilder::llvmModuleSet ( )
inlineprotected

Definition at line 87 of file SymbolTableBuilder.h.

88 {
90 }
static LLVMModuleSet * getLLVMModuleSet()
Definition LLVMModule.h:137

◆ PAGBuilder

friend class PAGBuilder
friend

Definition at line 46 of file SymbolTableBuilder.h.

Member Data Documentation

◆ pag

PAG* SVF::SymbolTableBuilder::pag
private

Definition at line 48 of file SymbolTableBuilder.h.


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