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

#include <ObjTypeInference.h>

Public Types

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

Public Member Functions

 ObjTypeInference ()=default
 ~ObjTypeInference ()=default
const Type * inferObjType (const Value *var)
 get or infer the type of the object pointed by the value
const Type * inferPointsToType (const Value *var)
void validateTypeCheck (const CallBase *cs)
 validate type inference
const Type * defaultType (const Value *val)
 default type
const Type * ptrType ()
 pointer type
const IntegerType * int8Type ()
 int8 type
LLVMContext & getLLVMCtx ()
const Type * selectLargestSizedType (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 Type * fwInferObjType (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

typedef std::pair<const Value *, bool> SVF::ObjTypeInference::ValueBoolPair

Definition at line 48 of file ObjTypeInference.h.

◆ ValueSet

Definition at line 43 of file ObjTypeInference.h.

◆ ValueToClassNames

typedef Map<const Value *, Set<std::string> > SVF::ObjTypeInference::ValueToClassNames

Definition at line 49 of file ObjTypeInference.h.

◆ ValueToInferSites

◆ ValueToSources

◆ ValueToType

typedef Map<const Value *, const Type *> SVF::ObjTypeInference::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 557 of file ObjTypeInference.cpp.

558{
559
560 // consult cache
561 auto tIt = _valueToAllocs.find(var);
562 if (tIt != _valueToAllocs.end())
563 {
564 return tIt->second;
565 }
566
567 // simulate the call stack, the second element indicates whether we should update sources for current value
568 FILOWorkList<ValueBoolPair> workList;
569 Set<ValueBoolPair> visited;
570 workList.push({var, false});
571 while (!workList.empty())
572 {
573 auto curPair = workList.pop();
574 if (visited.count(curPair)) continue;
575 visited.insert(curPair);
576 const Value *curValue = curPair.first;
577 bool canUpdate = curPair.second;
578
579 Set<const Value *> sources;
580 auto insertAllocs = [&sources, &canUpdate](const Value *source)
581 {
582 if (canUpdate) sources.insert(source);
583 };
584 auto insertAllocsOrPushWorklist = [this, &sources, &workList, &canUpdate](const auto &pUser)
585 {
586 auto vIt = _valueToAllocs.find(pUser);
587 if (canUpdate)
588 {
589 if (vIt != _valueToAllocs.end())
590 {
591 sources.insert(vIt->second.begin(), vIt->second.end());
592 }
593 }
594 else
595 {
596 if (vIt == _valueToAllocs.end()) workList.push({pUser, false});
597 }
598 };
599
600 if (!canUpdate && !_valueToAllocs.count(curValue))
601 {
602 workList.push({curValue, true});
603 }
604
605 if (isAlloc(curValue))
606 {
607 insertAllocs(curValue);
608 }
609 else if (const auto *bitCastInst = SVFUtil::dyn_cast<BitCastInst>(curValue))
610 {
611 Value *prevVal = bitCastInst->getOperand(0);
612 insertAllocsOrPushWorklist(prevVal);
613 }
614 else if (const auto *phiNode = SVFUtil::dyn_cast<PHINode>(curValue))
615 {
616 for (u32_t i = 0; i < phiNode->getNumOperands(); ++i)
617 {
618 insertAllocsOrPushWorklist(phiNode->getOperand(i));
619 }
620 }
621 else if (const auto *loadInst = SVFUtil::dyn_cast<LoadInst>(curValue))
622 {
623 // Skip a load through a constant pointer such as `poison` below: no store writes
624 // through it, so there is nothing to follow, and LLVM 21 keeps no use list for
625 // constants, so users() would assert.
626 // %p = load ptr, ptr poison
627 // %q = getelementptr inbounds i8, ptr %p, i64 8
628 const Value* ptr = loadInst->getPointerOperand();
629 if (hasUseList(ptr))
630 {
631 for (const auto use: ptr->users())
632 {
633 if (const StoreInst *storeInst = SVFUtil::dyn_cast<StoreInst>(use))
634 {
635 if (storeInst->getPointerOperand() == loadInst->getPointerOperand())
636 {
637 insertAllocsOrPushWorklist(storeInst->getValueOperand());
638 }
639 }
640 }
641 }
642 }
643 else if (const auto *argument = SVFUtil::dyn_cast<Argument>(curValue))
644 {
645 for (const auto use: argument->getParent()->users())
646 {
647 if (const CallBase *callBase = SVFUtil::dyn_cast<CallBase>(use))
648 {
649 // skip function as parameter
650 // e.g., call void @foo(%struct.ssl_ctx_st* %9, i32 (i8*, i32, i32, i8*)* @passwd_callback)
651 if (callBase->getCalledFunction() != argument->getParent()) continue;
652 u32_t pos = argument->getParent()->isVarArg() ? 0 : argument->getArgNo();
653 insertAllocsOrPushWorklist(callBase->getArgOperand(pos));
654 }
655 }
656 }
657 else if (const auto *callBase = SVFUtil::dyn_cast<CallBase>(curValue))
658 {
659 // A noreturn call yields no value, so skip it, e.g.:
660 // declare void @exit(i32) noreturn
661 // define ptr @stub() noreturn {
662 // call void @exit(i32 1)
663 // unreachable
664 // }
665 // %p = call ptr @stub()
666 // %q = getelementptr inbounds i8, ptr %p, i64 4
667 const Function *callee =
668 callBase->doesNotReturn() ? nullptr : callBase->getCalledFunction();
669 if (callee)
670 {
671 if (!callee->isDeclaration())
672 {
673
674 LLVMModuleSet* llvmmodule = LLVMModuleSet::getLLVMModuleSet();
675 const BasicBlock* exitBB = llvmmodule->getFunExitBB(callee);
676 assert (exitBB && "exit bb is not a basic block?");
677 const Value *pValue = &exitBB->back();
678 // The callee may end without a return value, e.g. @stub above without
679 // noreturn (as before optimisation).
680 const auto *retInst = SVFUtil::dyn_cast<ReturnInst>(pValue);
681 if (retInst && retInst->getReturnValue())
682 insertAllocsOrPushWorklist(retInst->getReturnValue());
683 }
684 }
685 }
686 if (canUpdate)
687 {
688 _valueToAllocs[curValue] = SVFUtil::move(sources);
689 }
690 }
692 if (srcs.empty())
693 {
694 WARN_MSG("Cannot find allocation: " + dumpValueAndDbgInfo(var));
695 }
696 return srcs;
697}
#define WARN_MSG(msg)
static bool hasUseList(const Value *v)
bool empty() const
Definition WorkList.h:267
bool push(const Data &data)
Definition WorkList.h:286
static LLVMModuleSet * getLLVMModuleSet()
Definition LLVMModule.h:137
const BasicBlock * getFunExitBB(const Function *fun) const
Definition LLVMModule.h:185
ValueToSources _valueToAllocs
bool isAlloc(const SVF::Value *val)
is allocation (stack, static, heap)
std::string dumpValueAndDbgInfo(const Value *val)
Definition LLVMUtil.cpp:634
constexpr std::remove_reference< T >::type && move(T &&t) noexcept
Definition SVFUtil.h:425
LLVM_NODISCARD std::enable_if_t<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type > dyn_cast(const Y &Val)
Definition Casting.h:405
llvm::CallBase CallBase
Definition BasicTypes.h:147
llvm::BasicBlock BasicBlock
Definition BasicTypes.h:84
std::unordered_set< Key, Hash, KeyEqual, Allocator > Set
Definition GeneralType.h:51
llvm::Function Function
Definition BasicTypes.h:83
llvm::Value Value
LLVM Basic classes.
Definition BasicTypes.h:80
llvm::StoreInst StoreInst
Definition BasicTypes.h:149
unsigned u32_t
Definition GeneralType.h:67

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

857{
858
859 // consult cache
860 auto tIt = _valueToAllocOrClsNameSources.find(startValue);
861 if (tIt != _valueToAllocOrClsNameSources.end())
862 {
863 return tIt->second;
864 }
865
866 // simulate the call stack, the second element indicates whether we should update sources for current value
867 FILOWorkList<ValueBoolPair> workList;
868 Set<ValueBoolPair> visited;
869 workList.push({startValue, false});
870 while (!workList.empty())
871 {
872 auto curPair = workList.pop();
873 if (visited.count(curPair)) continue;
874 visited.insert(curPair);
875 const Value *curValue = curPair.first;
876 bool canUpdate = curPair.second;
877
878 Set<const Value *> sources;
879 auto insertSource = [&sources, &canUpdate](const Value *source)
880 {
881 if (canUpdate) sources.insert(source);
882 };
883 auto insertSourcesOrPushWorklist = [this, &sources, &workList, &canUpdate](const auto &pUser)
884 {
885 auto vIt = _valueToAllocOrClsNameSources.find(pUser);
886 if (canUpdate)
887 {
888 if (vIt != _valueToAllocOrClsNameSources.end() && !vIt->second.empty())
889 {
890 sources.insert(vIt->second.begin(), vIt->second.end());
891 }
892 }
893 else
894 {
895 if (vIt == _valueToAllocOrClsNameSources.end()) workList.push({pUser, false});
896 }
897 };
898
899 if (!canUpdate && !_valueToAllocOrClsNameSources.count(curValue))
900 {
901 workList.push({curValue, true});
902 }
903
904 // If current value is an instruction inside a constructor/destructor/template, use it as a source
905 if (const auto *inst = SVFUtil::dyn_cast<Instruction>(curValue))
906 {
907 if (const auto *parent = inst->getFunction())
908 {
909 if (isClsNameSource(parent)) insertSource(parent);
910 }
911 }
912
913 // If the current value is an object (global, heap, stack, etc) or name source (constructor/destructor,
914 // a C++ dynamic cast, or a template function), use it as a source
915 if (isAlloc(curValue) || isClsNameSource(curValue))
916 {
917 insertSource(curValue);
918 }
919
920 // Explore the current value further depending on the type of the value; use cached values if possible
921 if (const auto *getElementPtrInst = SVFUtil::dyn_cast<GetElementPtrInst>(curValue))
922 {
923 insertSourcesOrPushWorklist(getElementPtrInst->getPointerOperand());
924 }
925 else if (const auto *bitCastInst = SVFUtil::dyn_cast<BitCastInst>(curValue))
926 {
927 insertSourcesOrPushWorklist(bitCastInst->getOperand(0));
928 }
929 else if (const auto *phiNode = SVFUtil::dyn_cast<PHINode>(curValue))
930 {
931 for (const auto *op : phiNode->operand_values())
932 {
933 insertSourcesOrPushWorklist(op);
934 }
935 }
936 else if (const auto *loadInst = SVFUtil::dyn_cast<LoadInst>(curValue))
937 {
938 const Value* ptr = loadInst->getPointerOperand();
939 if (hasUseList(ptr))
940 {
941 for (const auto *user : ptr->users())
942 {
943 if (const auto *storeInst = SVFUtil::dyn_cast<StoreInst>(user))
944 {
945 if (storeInst->getPointerOperand() == loadInst->getPointerOperand())
946 {
947 insertSourcesOrPushWorklist(storeInst->getValueOperand());
948 }
949 }
950 }
951 }
952 }
953 else if (const auto *argument = SVFUtil::dyn_cast<Argument>(curValue))
954 {
955 for (const auto *user: argument->getParent()->users())
956 {
957 if (const auto *callBase = SVFUtil::dyn_cast<CallBase>(user))
958 {
959 // skip function as parameter
960 // e.g., call void @foo(%struct.ssl_ctx_st* %9, i32 (i8*, i32, i32, i8*)* @passwd_callback)
961 if (callBase->getCalledFunction() != argument->getParent()) continue;
962 u32_t pos = argument->getParent()->isVarArg() ? 0 : argument->getArgNo();
963 insertSourcesOrPushWorklist(callBase->getArgOperand(pos));
964 }
965 }
966 }
967 else if (const auto *callBase = SVFUtil::dyn_cast<CallBase>(curValue))
968 {
969 // A noreturn call yields no value, so skip it, e.g.:
970 // declare void @exit(i32) noreturn
971 // define ptr @stub() noreturn {
972 // call void @exit(i32 1)
973 // unreachable
974 // }
975 // %p = call ptr @stub()
976 // %q = getelementptr inbounds i8, ptr %p, i64 4
977 const Function *callee =
978 callBase->doesNotReturn() ? nullptr : callBase->getCalledFunction();
979 if (callee)
980 {
981 if (!callee->isDeclaration())
982 {
983 LLVMModuleSet* llvmmodule = LLVMModuleSet::getLLVMModuleSet();
984 const BasicBlock* exitBB = llvmmodule->getFunExitBB(callee);
985 assert (exitBB && "exit bb is not a basic block?");
986 const Value *pValue = &exitBB->back();
987 // The callee may end without a return value, e.g. @stub above without
988 // noreturn (as before optimisation).
989 const auto *retInst = SVFUtil::dyn_cast<ReturnInst>(pValue);
990 if (retInst && retInst->getReturnValue())
991 insertSourcesOrPushWorklist(retInst->getReturnValue());
992 }
993 }
994 }
995
996 // If updating is allowed; store the gathered sources as sources for the current value in the cache
997 if (canUpdate)
998 {
999 _valueToAllocOrClsNameSources[curValue] = sources;
1000 }
1001 }
1002
1003 return _valueToAllocOrClsNameSources[startValue];
1004}
ValueToSources _valueToAllocOrClsNameSources
bool isClsNameSource(const Value *val)
Definition CppUtil.cpp:893

◆ defaultType()

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

default type

Definition at line 132 of file ObjTypeInference.cpp.

133{
134 ABORT_IFNOT(val, "val cannot be null");
135 // heap has a default type of 8-bit integer type
138 return int8Type();
139 // otherwise we return a pointer type in the default address space
140 return ptrType();
141}
#define ABORT_IFNOT(condition, msg)
const IntegerType * int8Type()
int8 type
const Type * ptrType()
pointer type
bool isHeapAllocExtCallViaRet(const Instruction *inst)
Definition LLVMUtil.cpp:645
std::enable_if_t<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type > cast(const Y &Val)
Definition Casting.h:360
LLVM_NODISCARD bool isa(const Y &Val)
Definition Casting.h:241

◆ fwFindClsNameSources()

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

forward find class name sources starting from an allocation

Definition at line 1006 of file ObjTypeInference.cpp.

1007{
1008 assert(startValue && "startValue was null?");
1009
1010 // consult cache
1011 auto tIt = _objToClsNameSources.find(startValue);
1012 if (tIt != _objToClsNameSources.end())
1013 {
1014 return tIt->second;
1015 }
1016
1017 Set<const CallBase *> sources;
1018
1019 // Lambda for adding a callee to the sources iff it is a constructor/destructor/template/dyncast
1020 auto inferViaCppCall = [&sources](const CallBase *caller)
1021 {
1022 if (!caller) return;
1023 if (isClsNameSource(caller)) sources.insert(caller);
1024 };
1025
1026 // Find all calls of starting val (or through cast); add as potential source iff applicable
1027 for (const auto *user : startValue->users())
1028 {
1029 if (const auto *caller = SVFUtil::dyn_cast<CallBase>(user))
1030 {
1031 inferViaCppCall(caller);
1032 }
1033 else if (const auto *bitcast = SVFUtil::dyn_cast<BitCastInst>(user))
1034 {
1035 for (const auto *cast_user : bitcast->users())
1036 {
1037 if (const auto *caller = SVFUtil::dyn_cast<CallBase>(cast_user))
1038 {
1039 inferViaCppCall(caller);
1040 }
1041 }
1042 }
1043 }
1044
1045 // Store sources in cache for starting value & return the found sources
1046 return _objToClsNameSources[startValue] = SVFUtil::move(sources);
1047}
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 226 of file ObjTypeInference.cpp.

227{
228 if (const AllocaInst *allocaInst = SVFUtil::dyn_cast<AllocaInst>(var))
229 {
230 // stack object
231 return infersiteToType(allocaInst);
232 }
233 else if (const GlobalValue *global = SVFUtil::dyn_cast<GlobalValue>(var))
234 {
235 // global object
236 return infersiteToType(global);
237 }
238 else
239 {
240 // for heap or static object, we forward infer its type
241
242 // consult cache
243 auto tIt = _valueToType.find(var);
244 if (tIt != _valueToType.end())
245 {
246 return tIt->second ? tIt->second : defaultType(var);
247 }
248
249 // simulate the call stack, the second element indicates whether we should update valueTypes for current value
250 FILOWorkList<ValueBoolPair> workList;
251 Set<ValueBoolPair> visited;
252 workList.push({var, false});
253
254 while (!workList.empty())
255 {
256 auto curPair = workList.pop();
257 if (visited.count(curPair))
258 continue;
259 visited.insert(curPair);
260 const Value* curValue = curPair.first;
261 bool canUpdate = curPair.second;
262 Set<const Value*> infersites;
263
264 auto insertInferSite = [&infersites,
265 &canUpdate](const Value* infersite)
266 {
267 if (canUpdate)
268 infersites.insert(infersite);
269 };
270 auto insertInferSitesOrPushWorklist =
271 [this, &infersites, &workList, &canUpdate](const auto& pUser)
272 {
273 auto vIt = _valueToInferSites.find(pUser);
274 if (canUpdate)
275 {
276 if (vIt != _valueToInferSites.end())
277 {
278 infersites.insert(vIt->second.begin(),
279 vIt->second.end());
280 }
281 }
282 else
283 {
284 if (vIt == _valueToInferSites.end())
285 workList.push({pUser, false});
286 }
287 };
288 if (!canUpdate && !_valueToInferSites.count(curValue))
289 {
290 workList.push({curValue, true});
291 }
292 if (const auto* gepInst =
294 insertInferSite(gepInst);
295 // hasUseList() was removed from Value's public API in LLVM 18-20; use
296 // the version-portable compat shim defined above instead.
297 if (!hasUseList(curValue)) continue;
298 for (const auto it : curValue->users())
299 {
300 if (const auto* loadInst = SVFUtil::dyn_cast<LoadInst>(it))
301 {
302 /*
303 * infer based on load, e.g.,
304 %call = call i8* malloc()
305 %1 = bitcast i8* %call to %struct.MyStruct*
306 %q = load %struct.MyStruct, %struct.MyStruct* %1
307 */
308 insertInferSite(loadInst);
309 }
310 else if (const auto* storeInst =
312 {
313 if (storeInst->getPointerOperand() == curValue)
314 {
315 /*
316 * infer based on store (pointer operand), e.g.,
317 %call = call i8* malloc()
318 %1 = bitcast i8* %call to %struct.MyStruct*
319 store %struct.MyStruct .., %struct.MyStruct* %1
320 */
321 insertInferSite(storeInst);
322 }
323 else if (hasUseList(storeInst->getPointerOperand()))
324 {
325 for (const auto nit :
326 storeInst->getPointerOperand()->users())
327 {
328 /*
329 * propagate across store (value operand) and load
330 %call = call i8* malloc()
331 store i8* %call, i8** %p
332 %q = load i8*, i8** %p
333 ..infer based on %q..
334 */
335 if (SVFUtil::isa<LoadInst>(nit))
336 insertInferSitesOrPushWorklist(nit);
337 }
338 /*
339 * infer based on store (value operand) <- gep (result element)
340 */
341 if (const auto* gepInst =
343 storeInst->getPointerOperand()))
344 {
345 /*
346 %call1 = call i8* @TYPE_MALLOC(i32 noundef 16, i32
347 noundef 2), !dbg !39 %2 = bitcast i8* %call1 to
348 %struct.MyStruct*, !dbg !41 %3 = load
349 %struct.MyStruct*, %struct.MyStruct** %p, align 8,
350 !dbg !42 %next = getelementptr inbounds
351 %struct.MyStruct, %struct.MyStruct* %3, i32 0, i32
352 1, !dbg !43 store %struct.MyStruct* %2,
353 %struct.MyStruct** %next, align 8, !dbg !44 %5 =
354 load %struct.MyStruct*, %struct.MyStruct** %p,
355 align 8, !dbg !48 %next3 = getelementptr inbounds
356 %struct.MyStruct, %struct.MyStruct* %5, i32 0, i32
357 1, !dbg !49 %6 = load %struct.MyStruct*,
358 %struct.MyStruct** %next3, align 8, !dbg !49 infer
359 site -> %f1 = getelementptr inbounds
360 %struct.MyStruct, %struct.MyStruct* %6, i32 0, i32
361 0, !dbg !50
362 */
363 const Value* gepBase = gepInst->getPointerOperand();
364 const auto* load = SVFUtil::dyn_cast<LoadInst>(gepBase);
365 if (load && hasUseList(load->getPointerOperand()))
366 {
367 for (const auto loadUse :
368 load->getPointerOperand()->users())
369 {
370 if (loadUse == load ||
371 !SVFUtil::isa<LoadInst>(loadUse))
372 continue;
373 for (const auto gepUse : loadUse->users())
374 {
376 gepUse))
377 continue;
378 for (const auto loadUse2 :
379 gepUse->users())
380 {
382 loadUse2))
383 {
384 insertInferSitesOrPushWorklist(
385 loadUse2);
386 }
387 }
388 }
389 }
390 }
391 else if (const auto* alloc =
393 {
394 /*
395 %2 = alloca %struct.ll, align 8
396 store i32 0, ptr %1, align 4
397 %3 = call noalias noundef nonnull ptr
398 @_Znwm(i64 noundef 16) #2 %4 = getelementptr
399 inbounds %struct.ll, ptr %2, i32 0, i32 1
400 store ptr %3, ptr %4, align 8
401 %5 = getelementptr inbounds %struct.ll, ptr
402 %2, i32 0, i32 1 %6 = load ptr, ptr %5, align
403 8 %7 = getelementptr inbounds %struct.ll, ptr
404 %6, i32 0, i32 0
405 */
406 for (const auto gepUse : alloc->users())
407 {
409 gepUse))
410 continue;
411 for (const auto loadUse2 : gepUse->users())
412 {
413 if (SVFUtil::isa<LoadInst>(loadUse2))
414 {
415 insertInferSitesOrPushWorklist(
416 loadUse2);
417 }
418 }
419 }
420 }
421 }
422 }
423 }
424 else if (const auto* gepInst =
426 {
427 /*
428 * infer based on gep (pointer operand)
429 %call = call i8* malloc()
430 %1 = bitcast i8* %call to %struct.MyStruct*
431 %next = getelementptr inbounds %struct.MyStruct,
432 %struct.MyStruct* %1, i32 0..
433 */
434 if (gepInst->getPointerOperand() == curValue)
435 insertInferSite(gepInst);
436 }
437 else if (const auto* bitcast =
439 {
440 // continue on bitcast
441 insertInferSitesOrPushWorklist(bitcast);
442 }
443 else if (const auto* phiNode = SVFUtil::dyn_cast<PHINode>(it))
444 {
445 // continue on bitcast
446 insertInferSitesOrPushWorklist(phiNode);
447 }
448 else if (const auto* retInst =
450 {
451 /*
452 * propagate from return to caller
453 Function Attrs: noinline nounwind optnone uwtable
454 define dso_local i8* @malloc_wrapper() #0 !dbg !22 {
455 entry:
456 %call = call i8* @malloc(i32 noundef 16), !dbg !25
457 ret i8* %call, !dbg !26
458 }
459 %call = call i8* @malloc_wrapper()
460 ..infer based on %call..
461 */
462 for (const auto callsite : retInst->getFunction()->users())
463 {
464 if (const auto* callBase =
466 {
467 // skip function as parameter
468 // e.g., call void @foo(%struct.ssl_ctx_st* %9, i32 (i8*, i32, i32, i8*)* @passwd_callback)
469 if (callBase->getCalledFunction() !=
470 retInst->getFunction())
471 continue;
472 insertInferSitesOrPushWorklist(callBase);
473 }
474 }
475 }
476 else if (const auto* callBase = SVFUtil::dyn_cast<CallBase>(it))
477 {
478 /*
479 * propagate from callsite to callee
480 %call = call i8* @malloc(i32 noundef 16)
481 %0 = bitcast i8* %call to %struct.Node*, !dbg !43
482 call void @foo(%struct.Node* noundef %0), !dbg !45
483
484 define dso_local void @foo(%struct.Node* noundef %param)
485 #0 !dbg !22 {...}
486 ..infer based on the formal param %param..
487 */
488 // skip global function value -> callsite
489 // e.g., def @foo() -> call @foo()
490 // we don't skip function as parameter, e.g., def @foo() -> call @bar(..., @foo)
491 if (SVFUtil::isa<Function>(curValue) &&
492 curValue == callBase->getCalledFunction())
493 continue;
494 // skip indirect call
495 // e.g., %0 = ... -> call %0(...)
496 if (!callBase->hasArgument(curValue))
497 continue;
498 if (Function* calleeFunc = callBase->getCalledFunction())
499 {
500 u32_t pos = getArgPosInCall(callBase, curValue);
501 // 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: .......
502 // 6: }
503 // 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''
504 if (calleeFunc->isVarArg())
505 {
506 // conservatively track all var args
507 for (auto& I : instructions(calleeFunc))
508 {
509 if (auto* load =
510 llvm::dyn_cast<llvm::LoadInst>(&I))
511 {
512 llvm::Value* loadPointer =
513 load->getPointerOperand();
514 if (loadPointer->getName().compare(
515 "vaarg.addr") == 0)
516 {
517 insertInferSitesOrPushWorklist(load);
518 }
519 }
520 }
521 }
522 else if (!calleeFunc->isDeclaration())
523 {
524 insertInferSitesOrPushWorklist(
525 calleeFunc->getArg(pos));
526 }
527 }
528 }
529 }
530 if (canUpdate)
531 {
532 Set<const Type*> types;
533 std::transform(infersites.begin(), infersites.end(),
534 std::inserter(types, types.begin()),
536 _valueToInferSites[curValue] = SVFUtil::move(infersites);
537 _valueToType[curValue] = selectLargestSizedType(types);
538 }
539 }
540 const Type* type = _valueToType[var];
541 if (type == nullptr)
542 {
543 type = defaultType(var);
544 WARN_MSG("Using default type, trace ID is " +
545 std::to_string(traceId) + ":" + dumpValueAndDbgInfo(var));
546 }
547 ABORT_IFNOT(type, "type cannot be a null ptr");
548 return type;
549 }
550}
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:81
llvm::AllocaInst AllocaInst
Definition BasicTypes.h:151
llvm::GlobalValue GlobalValue
Definition BasicTypes.h:86

◆ getArgPosInCall()

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

Definition at line 733 of file ObjTypeInference.cpp.

734{
735 assert(callBase->hasArgument(arg) && "callInst does not have argument arg?");
736 auto it = std::find(callBase->arg_begin(), callBase->arg_end(), arg);
737 assert(it != callBase->arg_end() && "Didn't find argument?");
738 return std::distance(callBase->arg_begin(), it);
739}

◆ getLLVMCtx()

LLVMContext & ObjTypeInference::getLLVMCtx ( )

Definition at line 143 of file ObjTypeInference.cpp.

144{
146}
LLVMContext & getContext() const
Definition LLVMModule.h:393

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

155{
156 const Type* res = inferPointsToType(var);
157 // infer type by leveraging the type alignment of src and dst in memcpy
158 // for example,
159 //
160 // %tmp = alloca %struct.outer
161 // %inner_v = alloca %struct.inner
162 // %ptr = getelementptr inbounds %struct.outer, ptr %tmp, i32 0, i32 1, !dbg !38
163 // %0 = load ptr, ptr %ptr, align 8, !dbg !38
164 // call void @llvm.memcpy.p0.p0.i64(ptr %inner_v, ptr %0, i64 24, i1 false)
165 //
166 // It is difficult to infer the type of %0 without deep alias analysis,
167 // but we can infer the obj type of %0 based on that of %inner_v.
168 if (res == defaultType(var))
169 {
170 // hasUseList() was removed from Value's public API in LLVM 18-20; use
171 // the version-portable compat shim defined above instead.
172 if (!hasUseList(var)) return res;
173 for (const auto& use: var->users())
174 {
175 if (const CallBase* cs = SVFUtil::dyn_cast<CallBase>(use))
176 {
177 if (const Function* calledFun = cs->getCalledFunction())
178 if (LLVMUtil::isMemcpyExtFun(calledFun))
179 {
180 assert(cs->getNumOperands() > 1 && "arguments should be greater than 1");
181 const Value* dst = cs->getArgOperand(0);
182 const Value* src = cs->getArgOperand(1);
183 if(calledFun->getName().find("iconv") != std::string::npos)
184 {
185 if(var == cs->getArgOperand(0))
186 return res;
187 dst = cs->getArgOperand(3), src = cs->getArgOperand(1);
188 }
189
190 if (var == dst) return inferPointsToType(src);
191 else if (var == src) return inferPointsToType(dst);
192 else ABORT_MSG("invalid memcpy call");
193 }
194 }
195 }
196 }
197 return res;
198}
#define ABORT_MSG(msg)
const Type * inferPointsToType(const Value *var)
bool isMemcpyExtFun(const Function *fun)
Definition LLVMUtil.cpp:390

◆ inferPointsToType()

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

Definition at line 200 of file ObjTypeInference.cpp.

201{
202 if (isAlloc(var)) return fwInferObjType(var);
203 Set<const Value *> &sources = bwFindAllocOfVar(var);
204 Set<const Type *> types;
205 if (sources.empty())
206 {
207 // cannot find allocation, try to fw infer starting from var
208 types.insert(fwInferObjType(var));
209 }
210 else
211 {
212 for (const auto &source: sources)
213 {
214 types.insert(fwInferObjType(source));
215 }
216 }
217 const Type *largestTy = selectLargestSizedType(types);
218 ABORT_IFNOT(largestTy, "return type cannot be null");
219 return largestTy;
220}
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 783 of file ObjTypeInference.cpp.

784{
785 auto it = _thisPtrClassNames.find(thisPtr);
786 if (it != _thisPtrClassNames.end()) return it->second;
787
788 Set<std::string> names;
789
790 // Lambda for checking a function is a valid name source & extracting a class name from it
791 auto addNamesFromFunc = [&names](const Function *func) -> void
792 {
793 ABORT_IFNOT(isClsNameSource(func), "Func is invalid class name source: " + dumpValueAndDbgInfo(func));
794 for (const auto &name : extractClsNamesFromFunc(func)) names.insert(name);
795 };
796
797// Lambda for getting callee & extracting class name for calls to constructors/destructors/template funcs
798 auto addNamesFromCall = [&names, &addNamesFromFunc](const CallBase *call) -> void
799 {
800 ABORT_IFNOT(isClsNameSource(call), "Call is invalid class name source: " + dumpValueAndDbgInfo(call));
801
802 const auto *func = call->getCalledFunction();
803 if (isDynCast(func)) names.insert(extractClsNameFromDynCast(call));
804 else addNamesFromFunc(func);
805 };
806
807// Walk backwards to find all valid source sites for the pointer (e.g. stack/global/heap variables)
808 for (const auto &val: bwFindAllocOrClsNameSources(thisPtr))
809 {
810 // A source site is either a constructor/destructor/template function from which the class name can be
811 // extracted; a call to a C++ constructor/destructor/template function from which the class name can be
812 // extracted; or an allocation site of an object (i.e. a stack/global/heap variable), from which a
813 // forward walk can be performed to find calls to C++ constructor/destructor/template functions from
814 // which the class' name can then be extracted; skip starting pointer
815 if (val == thisPtr) continue;
816
817 if (const auto *func = SVFUtil::dyn_cast<Function>(val))
818 {
819 // Constructor/destructor/template func; extract name from func directly
820 addNamesFromFunc(func);
821 }
822 else if (isClsNameSource(val))
823 {
824 // Call to constructor/destructor/template func; get callee; extract name from callee
825 ABORT_IFNOT(SVFUtil::isa<CallBase>(val), "Call source site is not a callbase: " + dumpValueAndDbgInfo(val));
826 addNamesFromCall(SVFUtil::cast<CallBase>(val));
827 }
828 else if (isAlloc(val))
829 {
830 // Stack/global/heap allocation site; walk forward; find constructor/destructor/template calls
832 "Alloc site source is not a stack/heap/global variable: " + dumpValueAndDbgInfo(val));
833 for (const auto *src : fwFindClsNameSources(val))
834 {
835 if (const auto *func = SVFUtil::dyn_cast<Function>(src)) addNamesFromFunc(func);
836 else if (const auto *call = SVFUtil::dyn_cast<CallBase>(src)) addNamesFromCall(call);
837 else ABORT_MSG("Source site from forward walk is invalid: " + dumpValueAndDbgInfo(src));
838 }
839 }
840 else
841 {
842 ERR_MSG("Unsupported source type found:" + dumpValueAndDbgInfo(val));
843 }
844 }
845
846 return _thisPtrClassNames[thisPtr] = names;
847}
#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:951
Set< std::string > extractClsNamesFromFunc(const Function *foo)
extract class name from the c++ function name, e.g., constructor/destructors
Definition CppUtil.cpp:739
bool isDynCast(const Function *foo)
whether foo is a cpp dyncast function
Definition CppUtil.cpp:941

◆ int8Type()

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

int8 type

Definition at line 87 of file ObjTypeInference.h.

88 {
89 return Type::getInt8Ty(getLLVMCtx());
90 }

◆ isAlloc()

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

is allocation (stack, static, heap)

Definition at line 699 of file ObjTypeInference.cpp.

700{
701 return LLVMUtil::isObject(val);
702}
bool isObject(const Value *ref)
Return true if this value refers to a object.
Definition LLVMUtil.cpp:61

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

759{
761 if (SVFUtil::isa<ArrayType>(objTy))
762 num = getNumOfElements(objTy);
763 else if (const auto *st = SVFUtil::dyn_cast<StructType>(objTy))
764 {
767 if (!classTyHasVTable(st))
768 num = getNumOfElements(st);
769 }
770 return num;
771}
static const Option< u32_t > MaxFieldLimit
Maximum number of field derivations for an object.
Definition Options.h:34
u32_t getNumOfElements(const Type *ety)
Return size of this object based on LLVM value.
Definition LLVMUtil.cpp:297
bool classTyHasVTable(const StructType *ty)
Definition CppUtil.cpp:602

◆ ptrType()

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

pointer type

Definition at line 81 of file ObjTypeInference.h.

82 {
83 return PointerType::getUnqual(getLLVMCtx());
84 }

◆ selectLargestSizedType()

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

select the largest (conservative) type from all types

Definition at line 742 of file ObjTypeInference.cpp.

743{
744 if (objTys.empty()) return nullptr;
745 // map type size to types from with key in descending order
746 OrderedMap<u32_t, OrderedSet<const Type *>, std::greater<int>> typeSzToTypes;
747 for (const Type *ty: objTys)
748 {
749 typeSzToTypes[objTyToNumFields(ty)].insert(ty);
750 }
751 assert(!typeSzToTypes.empty() && "typeSzToTypes cannot be empty");
752 OrderedSet<const Type *> largestTypes;
753 std::tie(std::ignore, largestTypes) = *typeSzToTypes.begin();
754 assert(!largestTypes.empty() && "largest element cannot be empty");
755 return *largestTypes.begin();
756}
u32_t objTyToNumFields(const Type *objTy)
std::map< Key, Value, Compare, Allocator > OrderedMap
Definition GeneralType.h:64
std::set< Key, Compare, Allocator > OrderedSet
Definition GeneralType.h:60

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

709{
710 if (const Function *func = cs->getCalledFunction())
711 {
712 if (func->getName().find(TYPEMALLOC) != std::string::npos)
713 {
714 const Type *objType = fwInferObjType(cs);
715 const auto *pInt =
716 SVFUtil::dyn_cast<llvm::ConstantInt>(cs->getOperand(1));
717 assert(pInt && "the second argument is a integer");
718 u32_t iTyNum = objTyToNumFields(objType);
719 if (iTyNum >= LLVMUtil::getIntegerValue(pInt).second)
720 SVFUtil::outs() << SVFUtil::sucMsg("\t SUCCESS :") << dumpValueAndDbgInfo(cs)
721 << SVFUtil::pasMsg(" TYPE: ")
722 << dumpType(objType) << "\n";
723 else
724 {
725 SVFUtil::errs() << SVFUtil::errMsg("\t FAILURE :") << ":" << dumpValueAndDbgInfo(cs) << " TYPE: "
726 << dumpType(objType) << "\n";
727 abort();
728 }
729 }
730 }
731}
const std::string TYPEMALLOC
std::string dumpType(const Type *type)
Definition LLVMUtil.cpp:623
std::pair< s64_t, u64_t > getIntegerValue(const ConstantInt *intValue)
Definition LLVMUtil.h:95
std::string sucMsg(const std::string &msg)
Returns successful message by converting a string into green string output.
Definition SVFUtil.cpp:75
std::string pasMsg(const std::string &msg)
Print each pass/phase message by converting a string into blue string output.
Definition SVFUtil.cpp:121
std::string errMsg(const std::string &msg)
Print error message by converting a string into red string output.
Definition SVFUtil.cpp:98
std::ostream & errs()
Overwrite llvm::errs().
Definition SVFUtil.h:64
std::ostream & outs()
Overwrite llvm::outs().
Definition SVFUtil.h:58

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: