Static Value-Flow Analysis
Loading...
Searching...
No Matches
Public Types | Public Member Functions | Protected Member Functions | Private Member Functions | Private Attributes | List of all members
SVF::ObjTypeInference Class Reference

#include <ObjTypeInference.h>

Public Types

typedef Set< const Value * > ValueSet
 
typedef Map< const Value *, ValueSetValueToValueSet
 
typedef ValueToValueSet ValueToInferSites
 
typedef ValueToValueSet ValueToSources
 
typedef Map< const Value *, const Type * > ValueToType
 
typedef std::pair< const Value *, boolValueBoolPair
 
typedef Map< const Value *, Set< std::string > > ValueToClassNames
 
typedef Map< const Value *, Set< const CallBase * > > ObjToClsNameSources
 

Public Member Functions

 ObjTypeInference ()=default
 
 ~ObjTypeInference ()=default
 
const TypeinferObjType (const Value *var)
 get or infer the type of the object pointed by the value
 
const TypeinferPointsToType (const Value *var)
 
void validateTypeCheck (const CallBase *cs)
 validate type inference
 
void typeSizeDiffTest (const PointerType *oPTy, const Type *iTy, const Value *val)
 
const TypedefaultType (const Value *val)
 default type
 
const TypeptrType ()
 pointer type
 
const IntegerTypeint8Type ()
 int8 type
 
LLVMContextgetLLVMCtx ()
 
const TypeselectLargestSizedType (Set< const Type * > &objTys)
 select the largest (conservative) type from all types
 
u32_t objTyToNumFields (const Type *objTy)
 
u32_t getArgPosInCall (const CallBase *callBase, const Value *arg)
 
Set< std::string > & inferThisPtrClsName (const Value *thisPtr)
 get or infer the class names of thisptr
 

Protected Member Functions

Set< const Value * > & bwFindAllocOrClsNameSources (const Value *startValue)
 
Set< const CallBase * > & fwFindClsNameSources (const Value *startValue)
 forward find class name sources starting from an allocation
 

Private Member Functions

const TypefwInferObjType (const Value *var)
 forward infer the type of the object pointed by var
 
Set< const Value * > & bwfindAllocOfVar (const Value *var)
 backward collect all possible allocation sites (stack, static, heap) of var
 
bool isAlloc (const SVF::Value *val)
 is allocation (stack, static, heap)
 

Private Attributes

ValueToInferSites _valueToInferSites
 
ValueToType _valueToType
 
ValueToSources _valueToAllocs
 
ValueToClassNames _thisPtrClassNames
 
ValueToSources _valueToAllocOrClsNameSources
 
ObjToClsNameSources _objToClsNameSources
 

Detailed Description

Definition at line 39 of file ObjTypeInference.h.

Member Typedef Documentation

◆ ObjToClsNameSources

Definition at line 50 of file ObjTypeInference.h.

◆ ValueBoolPair

Definition at line 48 of file ObjTypeInference.h.

◆ ValueSet

Definition at line 43 of file ObjTypeInference.h.

◆ ValueToClassNames

Definition at line 49 of file ObjTypeInference.h.

◆ ValueToInferSites

Definition at line 45 of file ObjTypeInference.h.

◆ ValueToSources

Definition at line 46 of file ObjTypeInference.h.

◆ ValueToType

Definition at line 47 of file ObjTypeInference.h.

◆ ValueToValueSet

Definition at line 44 of file ObjTypeInference.h.

Constructor & Destructor Documentation

◆ ObjTypeInference()

SVF::ObjTypeInference::ObjTypeInference ( )
explicitdefault

◆ ~ObjTypeInference()

SVF::ObjTypeInference::~ObjTypeInference ( )
default

Member Function Documentation

◆ bwfindAllocOfVar()

Set< const Value * > & ObjTypeInference::bwfindAllocOfVar ( const Value var)
private

backward collect all possible allocation sites (stack, static, heap) of var

backward collect all possible allocation sites (stack, static, heap) of var

Parameters
var
Returns

Definition at line 533 of file ObjTypeInference.cpp.

534{
535
536 // consult cache
537 auto tIt = _valueToAllocs.find(var);
538 if (tIt != _valueToAllocs.end())
539 {
540 return tIt->second;
541 }
542
543 // simulate the call stack, the second element indicates whether we should update sources for current value
545 Set<ValueBoolPair> visited;
546 workList.push({var, false});
547 while (!workList.empty())
548 {
549 auto curPair = workList.pop();
550 if (visited.count(curPair)) continue;
551 visited.insert(curPair);
552 const Value *curValue = curPair.first;
553 bool canUpdate = curPair.second;
554
555 Set<const Value *> sources;
556 auto insertAllocs = [&sources, &canUpdate](const Value *source)
557 {
558 if (canUpdate) sources.insert(source);
559 };
560 auto insertAllocsOrPushWorklist = [this, &sources, &workList, &canUpdate](const auto &pUser)
561 {
562 auto vIt = _valueToAllocs.find(pUser);
563 if (canUpdate)
564 {
565 if (vIt != _valueToAllocs.end())
566 {
567 sources.insert(vIt->second.begin(), vIt->second.end());
568 }
569 }
570 else
571 {
572 if (vIt == _valueToAllocs.end()) workList.push({pUser, false});
573 }
574 };
575
576 if (!canUpdate && !_valueToAllocs.count(curValue))
577 {
578 workList.push({curValue, true});
579 }
580
581 if (isAlloc(curValue))
582 {
584 }
585 else if (const auto *bitCastInst = SVFUtil::dyn_cast<BitCastInst>(curValue))
586 {
587 Value *prevVal = bitCastInst->getOperand(0);
589 }
590 else if (const auto *phiNode = SVFUtil::dyn_cast<PHINode>(curValue))
591 {
592 for (u32_t i = 0; i < phiNode->getNumOperands(); ++i)
593 {
595 }
596 }
597 else if (const auto *loadInst = SVFUtil::dyn_cast<LoadInst>(curValue))
598 {
599 for (const auto use: loadInst->getPointerOperand()->users())
600 {
601 if (const StoreInst *storeInst = SVFUtil::dyn_cast<StoreInst>(use))
602 {
603 if (storeInst->getPointerOperand() == loadInst->getPointerOperand())
604 {
605 insertAllocsOrPushWorklist(storeInst->getValueOperand());
606 }
607 }
608 }
609 }
610 else if (const auto *argument = SVFUtil::dyn_cast<Argument>(curValue))
611 {
612 for (const auto use: argument->getParent()->users())
613 {
614 if (const CallBase *callBase = SVFUtil::dyn_cast<CallBase>(use))
615 {
616 // skip function as parameter
617 // e.g., call void @foo(%struct.ssl_ctx_st* %9, i32 (i8*, i32, i32, i8*)* @passwd_callback)
618 if (callBase->getCalledFunction() != argument->getParent()) continue;
619 u32_t pos = argument->getParent()->isVarArg() ? 0 : argument->getArgNo();
620 insertAllocsOrPushWorklist(callBase->getArgOperand(pos));
621 }
622 }
623 }
624 else if (const auto *callBase = SVFUtil::dyn_cast<CallBase>(curValue))
625 {
626 ABORT_IFNOT(!callBase->doesNotReturn(), "callbase does not return:" + dumpValueAndDbgInfo(callBase));
627 if (Function *callee = callBase->getCalledFunction())
628 {
629 if (!callee->isDeclaration())
630 {
631
633 const BasicBlock* exitBB = llvmmodule->getFunExitBB(callee);
634 assert (exitBB && "exit bb is not a basic block?");
635 const Value *pValue = &exitBB->back();
636 const auto *retInst = SVFUtil::dyn_cast<ReturnInst>(pValue);
637 ABORT_IFNOT(retInst && retInst->getReturnValue(), "not return inst?");
638 insertAllocsOrPushWorklist(retInst->getReturnValue());
639 }
640 }
641 }
642 if (canUpdate)
643 {
645 }
646 }
648 if (srcs.empty())
649 {
650 WARN_MSG("Cannot find allocation: " + dumpValueAndDbgInfo(var));
651 }
652 return srcs;
653}
unsigned u32_t
Definition CommandLine.h:18
#define ABORT_IFNOT(condition, msg)
#define WARN_MSG(msg)
static LLVMModuleSet * getLLVMModuleSet()
Definition LLVMModule.h:131
ValueToSources _valueToAllocs
bool isAlloc(const SVF::Value *val)
is allocation (stack, static, heap)
std::string dumpValueAndDbgInfo(const Value *val)
Definition LLVMUtil.cpp:622
constexpr std::remove_reference< T >::type && move(T &&t) noexcept
Definition SVFUtil.h:420
llvm::CallBase CallBase
Definition BasicTypes.h:146
llvm::BasicBlock BasicBlock
Definition BasicTypes.h:86
llvm::Function Function
Definition BasicTypes.h:85
llvm::Value Value
LLVM Basic classes.
Definition BasicTypes.h:82
llvm::IRBuilder IRBuilder
Definition BasicTypes.h:74
llvm::StoreInst StoreInst
Definition BasicTypes.h:148

◆ bwFindAllocOrClsNameSources()

Set< const Value * > & ObjTypeInference::bwFindAllocOrClsNameSources ( const Value startValue)
protected

find all possible allocations or class name sources (e.g., constructors/destructors or template functions) starting from a value

find all possible allocations or class name sources (e.g., constructors/destructors or template functions) if we already find class name sources, we don't need to find the allocations and forward find class name sources

Parameters
startValue
Returns

Definition at line 826 of file ObjTypeInference.cpp.

827{
828
829 // consult cache
832 {
833 return tIt->second;
834 }
835
836 // simulate the call stack, the second element indicates whether we should update sources for current value
838 Set<ValueBoolPair> visited;
839 workList.push({startValue, false});
840 while (!workList.empty())
841 {
842 auto curPair = workList.pop();
843 if (visited.count(curPair)) continue;
844 visited.insert(curPair);
845 const Value *curValue = curPair.first;
846 bool canUpdate = curPair.second;
847
848 Set<const Value *> sources;
849 auto insertSource = [&sources, &canUpdate](const Value *source)
850 {
851 if (canUpdate) sources.insert(source);
852 };
853 auto insertSourcesOrPushWorklist = [this, &sources, &workList, &canUpdate](const auto &pUser)
854 {
856 if (canUpdate)
857 {
858 if (vIt != _valueToAllocOrClsNameSources.end() && !vIt->second.empty())
859 {
860 sources.insert(vIt->second.begin(), vIt->second.end());
861 }
862 }
863 else
864 {
865 if (vIt == _valueToAllocOrClsNameSources.end()) workList.push({pUser, false});
866 }
867 };
868
870 {
871 workList.push({curValue, true});
872 }
873
874 // If current value is an instruction inside a constructor/destructor/template, use it as a source
875 if (const auto *inst = SVFUtil::dyn_cast<Instruction>(curValue))
876 {
877 if (const auto *parent = inst->getFunction())
878 {
880 }
881 }
882
883 // If the current value is an object (global, heap, stack, etc) or name source (constructor/destructor,
884 // a C++ dynamic cast, or a template function), use it as a source
886 {
888 }
889
890 // Explore the current value further depending on the type of the value; use cached values if possible
891 if (const auto *getElementPtrInst = SVFUtil::dyn_cast<GetElementPtrInst>(curValue))
892 {
894 }
895 else if (const auto *bitCastInst = SVFUtil::dyn_cast<BitCastInst>(curValue))
896 {
898 }
899 else if (const auto *phiNode = SVFUtil::dyn_cast<PHINode>(curValue))
900 {
901 for (const auto *op : phiNode->operand_values())
902 {
904 }
905 }
906 else if (const auto *loadInst = SVFUtil::dyn_cast<LoadInst>(curValue))
907 {
908 for (const auto *user : loadInst->getPointerOperand()->users())
909 {
910 if (const auto *storeInst = SVFUtil::dyn_cast<StoreInst>(user))
911 {
912 if (storeInst->getPointerOperand() == loadInst->getPointerOperand())
913 {
914 insertSourcesOrPushWorklist(storeInst->getValueOperand());
915 }
916 }
917 }
918 }
919 else if (const auto *argument = SVFUtil::dyn_cast<Argument>(curValue))
920 {
921 for (const auto *user: argument->getParent()->users())
922 {
923 if (const auto *callBase = SVFUtil::dyn_cast<CallBase>(user))
924 {
925 // skip function as parameter
926 // e.g., call void @foo(%struct.ssl_ctx_st* %9, i32 (i8*, i32, i32, i8*)* @passwd_callback)
927 if (callBase->getCalledFunction() != argument->getParent()) continue;
928 u32_t pos = argument->getParent()->isVarArg() ? 0 : argument->getArgNo();
930 }
931 }
932 }
933 else if (const auto *callBase = SVFUtil::dyn_cast<CallBase>(curValue))
934 {
935 ABORT_IFNOT(!callBase->doesNotReturn(), "callbase does not return:" + dumpValueAndDbgInfo(callBase));
936 if (const auto *callee = callBase->getCalledFunction())
937 {
938 if (!callee->isDeclaration())
939 {
941 const BasicBlock* exitBB = llvmmodule->getFunExitBB(callee);
942 assert (exitBB && "exit bb is not a basic block?");
943 const Value *pValue = &exitBB->back();
944 const auto *retInst = SVFUtil::dyn_cast<ReturnInst>(pValue);
945 ABORT_IFNOT(retInst && retInst->getReturnValue(), "not return inst?");
946 insertSourcesOrPushWorklist(retInst->getReturnValue());
947 }
948 }
949 }
950
951 // If updating is allowed; store the gathered sources as sources for the current value in the cache
952 if (canUpdate)
953 {
955 }
956 }
957
959}
ValueToSources _valueToAllocOrClsNameSources
bool isClsNameSource(const Value *val)
Definition CppUtil.cpp:860

◆ defaultType()

const Type * ObjTypeInference::defaultType ( const Value val)

default type

Definition at line 114 of file ObjTypeInference.cpp.

115{
116 ABORT_IFNOT(val, "val cannot be null");
117 // heap has a default type of 8-bit integer type
118 if (SVFUtil::isa<Instruction>(val) && LLVMUtil::isHeapAllocExtCallViaRet(
119 SVFUtil::cast<Instruction>(val)))
120 return int8Type();
121 // otherwise we return a pointer type in the default address space
122 return ptrType();
123}
const IntegerType * int8Type()
int8 type
const Type * ptrType()
pointer type
bool isHeapAllocExtCallViaRet(const Instruction *inst)
Definition LLVMUtil.cpp:633

◆ fwFindClsNameSources()

Set< const CallBase * > & ObjTypeInference::fwFindClsNameSources ( const Value startValue)
protected

forward find class name sources starting from an allocation

Definition at line 961 of file ObjTypeInference.cpp.

962{
963 assert(startValue && "startValue was null?");
964
965 // consult cache
967 if (tIt != _objToClsNameSources.end())
968 {
969 return tIt->second;
970 }
971
972 Set<const CallBase *> sources;
973
974 // Lambda for adding a callee to the sources iff it is a constructor/destructor/template/dyncast
975 auto inferViaCppCall = [&sources](const CallBase *caller)
976 {
977 if (!caller) return;
978 if (isClsNameSource(caller)) sources.insert(caller);
979 };
980
981 // Find all calls of starting val (or through cast); add as potential source iff applicable
982 for (const auto *user : startValue->users())
983 {
984 if (const auto *caller = SVFUtil::dyn_cast<CallBase>(user))
985 {
987 }
988 else if (const auto *bitcast = SVFUtil::dyn_cast<BitCastInst>(user))
989 {
990 for (const auto *cast_user : bitcast->users())
991 {
992 if (const auto *caller = SVFUtil::dyn_cast<CallBase>(cast_user))
993 {
995 }
996 }
997 }
998 }
999
1000 // Store sources in cache for starting value & return the found sources
1002}
ObjToClsNameSources _objToClsNameSources

◆ fwInferObjType()

const Type * ObjTypeInference::fwInferObjType ( const Value var)
private

forward infer the type of the object pointed by var

forward infer the type of the object pointed by var

Parameters
var

Definition at line 205 of file ObjTypeInference.cpp.

206{
207 if (const AllocaInst *allocaInst = SVFUtil::dyn_cast<AllocaInst>(var))
208 {
209 // stack object
211 }
212 else if (const GlobalValue *global = SVFUtil::dyn_cast<GlobalValue>(var))
213 {
214 // global object
215 return infersiteToType(global);
216 }
217 else
218 {
219 // for heap or static object, we forward infer its type
220
221 // consult cache
222 auto tIt = _valueToType.find(var);
223 if (tIt != _valueToType.end())
224 {
225 return tIt->second ? tIt->second : defaultType(var);
226 }
227
228 // simulate the call stack, the second element indicates whether we should update valueTypes for current value
230 Set<ValueBoolPair> visited;
231 workList.push({var, false});
232
233 while (!workList.empty())
234 {
235 auto curPair = workList.pop();
236 if (visited.count(curPair))
237 continue;
238 visited.insert(curPair);
239 const Value* curValue = curPair.first;
240 bool canUpdate = curPair.second;
242
244 &canUpdate](const Value* infersite)
245 {
246 if (canUpdate)
247 infersites.insert(infersite);
248 };
250 [this, &infersites, &workList, &canUpdate](const auto& pUser)
251 {
252 auto vIt = _valueToInferSites.find(pUser);
253 if (canUpdate)
254 {
255 if (vIt != _valueToInferSites.end())
256 {
257 infersites.insert(vIt->second.begin(),
258 vIt->second.end());
259 }
260 }
261 else
262 {
263 if (vIt == _valueToInferSites.end())
264 workList.push({pUser, false});
265 }
266 };
267 if (!canUpdate && !_valueToInferSites.count(curValue))
268 {
269 workList.push({curValue, true});
270 }
271 if (const auto* gepInst =
272 SVFUtil::dyn_cast<GetElementPtrInst>(curValue))
274 for (const auto it : curValue->users())
275 {
276 if (const auto* loadInst = SVFUtil::dyn_cast<LoadInst>(it))
277 {
278 /*
279 * infer based on load, e.g.,
280 %call = call i8* malloc()
281 %1 = bitcast i8* %call to %struct.MyStruct*
282 %q = load %struct.MyStruct, %struct.MyStruct* %1
283 */
285 }
286 else if (const auto* storeInst =
287 SVFUtil::dyn_cast<StoreInst>(it))
288 {
289 if (storeInst->getPointerOperand() == curValue)
290 {
291 /*
292 * infer based on store (pointer operand), e.g.,
293 %call = call i8* malloc()
294 %1 = bitcast i8* %call to %struct.MyStruct*
295 store %struct.MyStruct .., %struct.MyStruct* %1
296 */
298 }
299 else
300 {
301 for (const auto nit :
303 {
304 /*
305 * propagate across store (value operand) and load
306 %call = call i8* malloc()
307 store i8* %call, i8** %p
308 %q = load i8*, i8** %p
309 ..infer based on %q..
310 */
311 if (SVFUtil::isa<LoadInst>(nit))
313 }
314 /*
315 * infer based on store (value operand) <- gep (result element)
316 */
317 if (const auto* gepInst =
318 SVFUtil::dyn_cast<GetElementPtrInst>(
319 storeInst->getPointerOperand()))
320 {
321 /*
322 %call1 = call i8* @TYPE_MALLOC(i32 noundef 16, i32
323 noundef 2), !dbg !39 %2 = bitcast i8* %call1 to
324 %struct.MyStruct*, !dbg !41 %3 = load
325 %struct.MyStruct*, %struct.MyStruct** %p, align 8,
326 !dbg !42 %next = getelementptr inbounds
327 %struct.MyStruct, %struct.MyStruct* %3, i32 0, i32
328 1, !dbg !43 store %struct.MyStruct* %2,
329 %struct.MyStruct** %next, align 8, !dbg !44 %5 =
330 load %struct.MyStruct*, %struct.MyStruct** %p,
331 align 8, !dbg !48 %next3 = getelementptr inbounds
332 %struct.MyStruct, %struct.MyStruct* %5, i32 0, i32
333 1, !dbg !49 %6 = load %struct.MyStruct*,
334 %struct.MyStruct** %next3, align 8, !dbg !49 infer
335 site -> %f1 = getelementptr inbounds
336 %struct.MyStruct, %struct.MyStruct* %6, i32 0, i32
337 0, !dbg !50
338 */
339 const Value* gepBase = gepInst->getPointerOperand();
340 if (const auto* load =
341 SVFUtil::dyn_cast<LoadInst>(gepBase))
342 {
343 for (const auto loadUse :
344 load->getPointerOperand()->users())
345 {
346 if (loadUse == load ||
347 !SVFUtil::isa<LoadInst>(loadUse))
348 continue;
349 for (const auto gepUse : loadUse->users())
350 {
351 if (!SVFUtil::isa<GetElementPtrInst>(
352 gepUse))
353 continue;
354 for (const auto loadUse2 :
355 gepUse->users())
356 {
357 if (SVFUtil::isa<LoadInst>(
358 loadUse2))
359 {
361 loadUse2);
362 }
363 }
364 }
365 }
366 }
367 else if (const auto* alloc =
368 SVFUtil::dyn_cast<AllocaInst>(gepBase))
369 {
370 /*
371 %2 = alloca %struct.ll, align 8
372 store i32 0, ptr %1, align 4
373 %3 = call noalias noundef nonnull ptr
374 @_Znwm(i64 noundef 16) #2 %4 = getelementptr
375 inbounds %struct.ll, ptr %2, i32 0, i32 1
376 store ptr %3, ptr %4, align 8
377 %5 = getelementptr inbounds %struct.ll, ptr
378 %2, i32 0, i32 1 %6 = load ptr, ptr %5, align
379 8 %7 = getelementptr inbounds %struct.ll, ptr
380 %6, i32 0, i32 0
381 */
382 for (const auto gepUse : alloc->users())
383 {
384 if (!SVFUtil::isa<GetElementPtrInst>(
385 gepUse))
386 continue;
387 for (const auto loadUse2 : gepUse->users())
388 {
389 if (SVFUtil::isa<LoadInst>(loadUse2))
390 {
392 loadUse2);
393 }
394 }
395 }
396 }
397 }
398 }
399 }
400 else if (const auto* gepInst =
401 SVFUtil::dyn_cast<GetElementPtrInst>(it))
402 {
403 /*
404 * infer based on gep (pointer operand)
405 %call = call i8* malloc()
406 %1 = bitcast i8* %call to %struct.MyStruct*
407 %next = getelementptr inbounds %struct.MyStruct,
408 %struct.MyStruct* %1, i32 0..
409 */
410 if (gepInst->getPointerOperand() == curValue)
412 }
413 else if (const auto* bitcast =
414 SVFUtil::dyn_cast<BitCastInst>(it))
415 {
416 // continue on bitcast
418 }
419 else if (const auto* phiNode = SVFUtil::dyn_cast<PHINode>(it))
420 {
421 // continue on bitcast
423 }
424 else if (const auto* retInst =
425 SVFUtil::dyn_cast<ReturnInst>(it))
426 {
427 /*
428 * propagate from return to caller
429 Function Attrs: noinline nounwind optnone uwtable
430 define dso_local i8* @malloc_wrapper() #0 !dbg !22 {
431 entry:
432 %call = call i8* @malloc(i32 noundef 16), !dbg !25
433 ret i8* %call, !dbg !26
434 }
435 %call = call i8* @malloc_wrapper()
436 ..infer based on %call..
437 */
438 for (const auto callsite : retInst->getFunction()->users())
439 {
440 if (const auto* callBase =
441 SVFUtil::dyn_cast<CallBase>(callsite))
442 {
443 // skip function as parameter
444 // e.g., call void @foo(%struct.ssl_ctx_st* %9, i32 (i8*, i32, i32, i8*)* @passwd_callback)
445 if (callBase->getCalledFunction() !=
446 retInst->getFunction())
447 continue;
449 }
450 }
451 }
452 else if (const auto* callBase = SVFUtil::dyn_cast<CallBase>(it))
453 {
454 /*
455 * propagate from callsite to callee
456 %call = call i8* @malloc(i32 noundef 16)
457 %0 = bitcast i8* %call to %struct.Node*, !dbg !43
458 call void @foo(%struct.Node* noundef %0), !dbg !45
459
460 define dso_local void @foo(%struct.Node* noundef %param)
461 #0 !dbg !22 {...}
462 ..infer based on the formal param %param..
463 */
464 // skip global function value -> callsite
465 // e.g., def @foo() -> call @foo()
466 // we don't skip function as parameter, e.g., def @foo() -> call @bar(..., @foo)
467 if (SVFUtil::isa<Function>(curValue) &&
468 curValue == callBase->getCalledFunction())
469 continue;
470 // skip indirect call
471 // e.g., %0 = ... -> call %0(...)
472 if (!callBase->hasArgument(curValue))
473 continue;
474 if (Function* calleeFunc = callBase->getCalledFunction())
475 {
477 // for varargs function, we cannot directly get the value-flow between actual and formal args e.g., consider the following vararg function @callee 1: call void @callee(%arg) 2: define dso_local i32 @callee(...) #0 !dbg !17 { 3: ....... 4: %5 = load i32, ptr %vaarg.addr, align 4, !dbg !55 5: .......
478 // 6: }
479 // it is challenging to precisely identify the forward value-flow of %arg (Line 2) because the function definition of callee (Line 2) does not have any formal args related to the actual arg %arg therefore we track all possible instructions like ``load i32, ptr %vaarg.addr''
480 if (calleeFunc->isVarArg())
481 {
482 // conservatively track all var args
483 for (auto& I : instructions(calleeFunc))
484 {
485 if (auto* load =
486 llvm::dyn_cast<llvm::LoadInst>(&I))
487 {
488 llvm::Value* loadPointer =
489 load->getPointerOperand();
490 if (loadPointer->getName().compare(
491 "vaarg.addr") == 0)
492 {
494 }
495 }
496 }
497 }
498 else if (!calleeFunc->isDeclaration())
499 {
501 calleeFunc->getArg(pos));
502 }
503 }
504 }
505 }
506 if (canUpdate)
507 {
509 std::transform(infersites.begin(), infersites.end(),
510 std::inserter(types, types.begin()),
514 }
515 }
516 const Type* type = _valueToType[var];
517 if (type == nullptr)
518 {
520 WARN_MSG("Using default type, trace ID is " +
521 std::to_string(traceId) + ":" + dumpValueAndDbgInfo(var));
522 }
523 ABORT_IFNOT(type, "type cannot be a null ptr");
524 return type;
525 }
526}
const Type * infersiteToType(const Value *val)
newitem type
Definition cJSON.cpp:2739
ValueToInferSites _valueToInferSites
const Type * selectLargestSizedType(Set< const Type * > &objTys)
select the largest (conservative) type from all types
u32_t getArgPosInCall(const CallBase *callBase, const Value *arg)
const Type * defaultType(const Value *val)
default type
llvm::Type Type
Definition BasicTypes.h:83
llvm::AllocaInst AllocaInst
Definition BasicTypes.h:150
llvm::GlobalValue GlobalValue
Definition BasicTypes.h:88

◆ getArgPosInCall()

u32_t ObjTypeInference::getArgPosInCall ( const CallBase callBase,
const Value arg 
)

Definition at line 703 of file ObjTypeInference.cpp.

704{
705 assert(callBase->hasArgument(arg) && "callInst does not have argument arg?");
706 auto it = std::find(callBase->arg_begin(), callBase->arg_end(), arg);
707 assert(it != callBase->arg_end() && "Didn't find argument?");
708 return std::distance(callBase->arg_begin(), it);
709}

◆ getLLVMCtx()

LLVMContext & ObjTypeInference::getLLVMCtx ( )

Definition at line 125 of file ObjTypeInference.cpp.

126{
128}
LLVMContext & getContext() const
Definition LLVMModule.h:381

◆ inferObjType()

const Type * ObjTypeInference::inferObjType ( const Value var)

get or infer the type of the object pointed by the value

get or infer the type of the object pointed by var if the start value is a source (alloc/global, heap, static), call fwInferObjType if not, find allocations and then forward get or infer types

Parameters
val

Definition at line 136 of file ObjTypeInference.cpp.

137{
138 const Type* res = inferPointsToType(var);
139 // infer type by leveraging the type alignment of src and dst in memcpy
140 // for example,
141 //
142 // %tmp = alloca %struct.outer
143 // %inner_v = alloca %struct.inner
144 // %ptr = getelementptr inbounds %struct.outer, ptr %tmp, i32 0, i32 1, !dbg !38
145 // %0 = load ptr, ptr %ptr, align 8, !dbg !38
146 // call void @llvm.memcpy.p0.p0.i64(ptr %inner_v, ptr %0, i64 24, i1 false)
147 //
148 // It is difficult to infer the type of %0 without deep alias analysis,
149 // but we can infer the obj type of %0 based on that of %inner_v.
150 if (res == defaultType(var))
151 {
152 for (const auto& use: var->users())
153 {
154 if (const CallBase* cs = SVFUtil::dyn_cast<CallBase>(use))
155 {
156 if (const Function* calledFun = cs->getCalledFunction())
158 {
159 assert(cs->getNumOperands() > 1 && "arguments should be greater than 1");
160 const Value* dst = cs->getArgOperand(0);
161 const Value* src = cs->getArgOperand(1);
162 if(calledFun->getName().find("iconv") != std::string::npos)
163 {
164 if(var == cs->getArgOperand(0))
165 return res;
166 dst = cs->getArgOperand(3), src = cs->getArgOperand(1);
167 }
168
169 if (var == dst) return inferPointsToType(src);
170 else if (var == src) return inferPointsToType(dst);
171 else ABORT_MSG("invalid memcpy call");
172 }
173 }
174 }
175 }
176 return res;
177}
#define ABORT_MSG(msg)
const Type * inferPointsToType(const Value *var)
bool isMemcpyExtFun(const Function *fun)
Definition LLVMUtil.cpp:388

◆ inferPointsToType()

const Type * ObjTypeInference::inferPointsToType ( const Value var)

Definition at line 179 of file ObjTypeInference.cpp.

180{
181 if (isAlloc(var)) return fwInferObjType(var);
184 if (sources.empty())
185 {
186 // cannot find allocation, try to fw infer starting from var
187 types.insert(fwInferObjType(var));
188 }
189 else
190 {
191 for (const auto &source: sources)
192 {
193 types.insert(fwInferObjType(source));
194 }
195 }
197 ABORT_IFNOT(largestTy, "return type cannot be null");
198 return largestTy;
199}
Set< const Value * > & bwfindAllocOfVar(const Value *var)
backward collect all possible allocation sites (stack, static, heap) of var
const Type * fwInferObjType(const Value *var)
forward infer the type of the object pointed by var

◆ inferThisPtrClsName()

Set< std::string > & ObjTypeInference::inferThisPtrClsName ( const Value thisPtr)

get or infer the class names of thisptr

get or infer the class names of thisptr; starting from :param:thisPtr, will walk backwards to find all potential sources for the class name. Valid sources include global or stack variables, heap allocations, or C++ dynamic casts/constructors/destructors. If the source site is a global/stack/heap variable, find the corresponding constructor/destructor to extract the class' name from (since the type of the variable is not reliable but the demangled name is)

Parameters
thisPtr
Returns
a set of all possible type names that :param:thisPtr could point to

Definition at line 753 of file ObjTypeInference.cpp.

754{
755 auto it = _thisPtrClassNames.find(thisPtr);
756 if (it != _thisPtrClassNames.end()) return it->second;
757
759
760 // Lambda for checking a function is a valid name source & extracting a class name from it
761 auto addNamesFromFunc = [&names](const Function *func) -> void
762 {
763 ABORT_IFNOT(isClsNameSource(func), "Func is invalid class name source: " + dumpValueAndDbgInfo(func));
764 for (const auto &name : extractClsNamesFromFunc(func)) names.insert(name);
765 };
766
767 // Lambda for getting callee & extracting class name for calls to constructors/destructors/template funcs
768 auto addNamesFromCall = [&names, &addNamesFromFunc](const CallBase *call) -> void
769 {
770 ABORT_IFNOT(isClsNameSource(call), "Call is invalid class name source: " + dumpValueAndDbgInfo(call));
771
772 const auto *func = call->getCalledFunction();
773 if (isDynCast(func)) names.insert(extractClsNameFromDynCast(call));
775 };
776
777 // Walk backwards to find all valid source sites for the pointer (e.g. stack/global/heap variables)
778 for (const auto &val: bwFindAllocOrClsNameSources(thisPtr))
779 {
780 // A source site is either a constructor/destructor/template function from which the class name can be
781 // extracted; a call to a C++ constructor/destructor/template function from which the class name can be
782 // extracted; or an allocation site of an object (i.e. a stack/global/heap variable), from which a
783 // forward walk can be performed to find calls to C++ constructor/destructor/template functions from
784 // which the class' name can then be extracted; skip starting pointer
785 if (val == thisPtr) continue;
786
787 if (const auto *func = SVFUtil::dyn_cast<Function>(val))
788 {
789 // Constructor/destructor/template func; extract name from func directly
791 }
792 else if (isClsNameSource(val))
793 {
794 // Call to constructor/destructor/template func; get callee; extract name from callee
795 ABORT_IFNOT(SVFUtil::isa<CallBase>(val), "Call source site is not a callbase: " + dumpValueAndDbgInfo(val));
796 addNamesFromCall(SVFUtil::cast<CallBase>(val));
797 }
798 else if (isAlloc(val))
799 {
800 // Stack/global/heap allocation site; walk forward; find constructor/destructor/template calls
801 ABORT_IFNOT((SVFUtil::isa<AllocaInst, CallBase, GlobalVariable>(val)),
802 "Alloc site source is not a stack/heap/global variable: " + dumpValueAndDbgInfo(val));
803 for (const auto *src : fwFindClsNameSources(val))
804 {
805 if (const auto *func = SVFUtil::dyn_cast<Function>(src)) addNamesFromFunc(func);
806 else if (const auto *call = SVFUtil::dyn_cast<CallBase>(src)) addNamesFromCall(call);
807 else ABORT_MSG("Source site from forward walk is invalid: " + dumpValueAndDbgInfo(src));
808 }
809 }
810 else
811 {
812 ERR_MSG("Unsupported source type found:" + dumpValueAndDbgInfo(val));
813 }
814 }
815
817}
#define ERR_MSG(msg)
const char *const name
Definition cJSON.h:264
Set< const Value * > & bwFindAllocOrClsNameSources(const Value *startValue)
ValueToClassNames _thisPtrClassNames
Set< const CallBase * > & fwFindClsNameSources(const Value *startValue)
forward find class name sources starting from an allocation
std::string extractClsNameFromDynCast(const CallBase *callBase)
extract class name from cpp dyncast function
Definition CppUtil.cpp:918
Set< std::string > extractClsNamesFromFunc(const Function *foo)
extract class name from the c++ function name, e.g., constructor/destructors
Definition CppUtil.cpp:706
bool isDynCast(const Function *foo)
whether foo is a cpp dyncast function
Definition CppUtil.cpp:908

◆ int8Type()

const IntegerType * SVF::ObjTypeInference::int8Type ( )
inline

int8 type

Definition at line 89 of file ObjTypeInference.h.

90 {
91 return Type::getInt8Ty(getLLVMCtx());
92 }

◆ isAlloc()

bool ObjTypeInference::isAlloc ( const SVF::Value val)
private

is allocation (stack, static, heap)

Definition at line 655 of file ObjTypeInference.cpp.

656{
657 return LLVMUtil::isObject(val);
658}
bool isObject(const Value *ref)
Return true if this value refers to a object.
Definition LLVMUtil.cpp:59

◆ objTyToNumFields()

u32_t ObjTypeInference::objTyToNumFields ( const Type objTy)

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 728 of file ObjTypeInference.cpp.

729{
731 if (SVFUtil::isa<ArrayType>(objTy))
733 else if (const auto *st = SVFUtil::dyn_cast<StructType>(objTy))
734 {
737 if (!classTyHasVTable(st))
739 }
740 return num;
741}
static const Option< u32_t > MaxFieldLimit
Maximum number of field derivations for an object.
Definition Options.h:35
u32_t getNumOfElements(const Type *ety)
Return size of this object based on LLVM value.
Definition LLVMUtil.cpp:295
bool classTyHasVTable(const StructType *ty)
Definition CppUtil.cpp:569

◆ ptrType()

const Type * SVF::ObjTypeInference::ptrType ( )
inline

pointer type

Definition at line 83 of file ObjTypeInference.h.

84 {
85 return PointerType::getUnqual(getLLVMCtx());
86 }

◆ selectLargestSizedType()

const Type * ObjTypeInference::selectLargestSizedType ( Set< const Type * > &  objTys)

select the largest (conservative) type from all types

Definition at line 712 of file ObjTypeInference.cpp.

713{
714 if (objTys.empty()) return nullptr;
715 // map type size to types from with key in descending order
717 for (const Type *ty: objTys)
718 {
720 }
721 assert(!typeSzToTypes.empty() && "typeSzToTypes cannot be empty");
723 std::tie(std::ignore, largestTypes) = *typeSzToTypes.begin();
724 assert(!largestTypes.empty() && "largest element cannot be empty");
725 return *largestTypes.begin();
726}
u32_t objTyToNumFields(const Type *objTy)

◆ typeSizeDiffTest()

void ObjTypeInference::typeSizeDiffTest ( const PointerType oPTy,
const Type iTy,
const Value val 
)

Definition at line 689 of file ObjTypeInference.cpp.

690{
691#if TYPE_DEBUG
695 {
696 ERR_MSG("original type is:" + dumpType(oTy));
697 ERR_MSG("infered type is:" + dumpType(iTy));
698 ABORT_MSG("wrong type, trace ID is " + std::to_string(traceId) + ":" + dumpValueAndDbgInfo(val));
699 }
700#endif
701}
std::string dumpType(const Type *type)
Definition LLVMUtil.cpp:611
static Type * getPtrElementType(const PointerType *pty)
Definition LLVMUtil.h:130

◆ validateTypeCheck()

void ObjTypeInference::validateTypeCheck ( const CallBase cs)

validate type inference

validate type inference

Parameters
cs: stub malloc function with element number label

Definition at line 664 of file ObjTypeInference.cpp.

665{
666 if (const Function *func = cs->getCalledFunction())
667 {
668 if (func->getName().find(TYPEMALLOC) != std::string::npos)
669 {
670 const Type *objType = fwInferObjType(cs);
671 const auto *pInt =
672 SVFUtil::dyn_cast<llvm::ConstantInt>(cs->getOperand(1));
673 assert(pInt && "the second argument is a integer");
676 SVFUtil::outs() << SVFUtil::sucMsg("\t SUCCESS :") << dumpValueAndDbgInfo(cs)
677 << SVFUtil::pasMsg(" TYPE: ")
678 << dumpType(objType) << "\n";
679 else
680 {
681 SVFUtil::errs() << SVFUtil::errMsg("\t FAILURE :") << ":" << dumpValueAndDbgInfo(cs) << " TYPE: "
682 << dumpType(objType) << "\n";
683 abort();
684 }
685 }
686 }
687}
const std::string TYPEMALLOC
std::pair< s64_t, u64_t > getIntegerValue(const ConstantInt *intValue)
Definition LLVMUtil.h:82
std::string sucMsg(const std::string &msg)
Returns successful message by converting a string into green string output.
Definition SVFUtil.cpp:55
std::string pasMsg(const std::string &msg)
Print each pass/phase message by converting a string into blue string output.
Definition SVFUtil.cpp:101
std::string errMsg(const std::string &msg)
Print error message by converting a string into red string output.
Definition SVFUtil.cpp:78
std::ostream & errs()
Overwrite llvm::errs()
Definition SVFUtil.h:58
std::ostream & outs()
Overwrite llvm::outs()
Definition SVFUtil.h:52

Member Data Documentation

◆ _objToClsNameSources

ObjToClsNameSources SVF::ObjTypeInference::_objToClsNameSources
private

Definition at line 59 of file ObjTypeInference.h.

◆ _thisPtrClassNames

ValueToClassNames SVF::ObjTypeInference::_thisPtrClassNames
private

Definition at line 57 of file ObjTypeInference.h.

◆ _valueToAllocOrClsNameSources

ValueToSources SVF::ObjTypeInference::_valueToAllocOrClsNameSources
private

Definition at line 58 of file ObjTypeInference.h.

◆ _valueToAllocs

ValueToSources SVF::ObjTypeInference::_valueToAllocs
private

Definition at line 56 of file ObjTypeInference.h.

◆ _valueToInferSites

ValueToInferSites SVF::ObjTypeInference::_valueToInferSites
private

Definition at line 54 of file ObjTypeInference.h.

◆ _valueToType

ValueToType SVF::ObjTypeInference::_valueToType
private

Definition at line 55 of file ObjTypeInference.h.


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