38 #define ERR_MSG(msg) \
41 SVFUtil::errs() << SVFUtil::errMsg("Error ") << __FILE__ << ':' \
42 << __LINE__ << ": " << (msg) << '\n'; \
44 #define ABORT_MSG(msg) \
50 #define ABORT_IFNOT(condition, msg) \
58 #define WARN_MSG(msg) \
61 SVFUtil::outs() << SVFUtil::wrnMsg("Warning ") << __FILE__ << ':' \
62 << __LINE__ << ": " << msg << '\n'; \
64 #define WARN_IFNOT(condition, msg) \
72 #define WARN_IFNOT(condition, msg)
76 using namespace SVFUtil;
77 using namespace LLVMUtil;
78 using namespace cppUtil;
87 assert(val &&
"value cannot be empty");
88 if (SVFUtil::isa<LoadInst, StoreInst>(val))
90 return llvm::getLoadStoreType(
const_cast<Value *
>(val));
92 else if (
const auto *gepInst = SVFUtil::dyn_cast<GetElementPtrInst>(val))
94 return gepInst->getSourceElementType();
96 else if (
const auto *call = SVFUtil::dyn_cast<CallBase>(val))
98 return call->getFunctionType();
100 else if (
const auto *allocaInst = SVFUtil::dyn_cast<AllocaInst>(val))
102 return allocaInst->getAllocatedType();
104 else if (
const auto *globalValue = SVFUtil::dyn_cast<GlobalValue>(val))
106 return globalValue->getValueType();
119 SVFUtil::cast<Instruction>(val)))
138 if (isAlloc(var))
return fwInferObjType(var);
144 types.insert(fwInferObjType(var));
148 for (
const auto &source: sources)
150 types.insert(fwInferObjType(source));
153 const Type *largestTy = selectLargestSizedType(types);
154 ABORT_IFNOT(largestTy,
"return type cannot be null");
164 if (
const AllocaInst *allocaInst = SVFUtil::dyn_cast<AllocaInst>(var))
169 else if (
const GlobalValue *global = SVFUtil::dyn_cast<GlobalValue>(var))
179 auto tIt = _valueToType.find(var);
180 if (tIt != _valueToType.end())
182 return tIt->second ? tIt->second : defaultType(var);
188 workList.
push({var,
false});
190 while (!workList.
empty())
192 auto curPair = workList.
pop();
193 if (visited.count(curPair))
195 visited.insert(curPair);
196 const Value* curValue = curPair.first;
197 bool canUpdate = curPair.second;
200 auto insertInferSite = [&infersites,
201 &canUpdate](
const Value* infersite)
204 infersites.insert(infersite);
206 auto insertInferSitesOrPushWorklist =
207 [
this, &infersites, &workList, &canUpdate](
const auto& pUser)
209 auto vIt = _valueToInferSites.find(pUser);
212 if (vIt != _valueToInferSites.end())
214 infersites.insert(vIt->second.begin(),
220 if (vIt == _valueToInferSites.end())
221 workList.push({pUser,
false});
224 if (!canUpdate && !_valueToInferSites.count(curValue))
226 workList.
push({curValue,
true});
228 if (
const auto* gepInst =
229 SVFUtil::dyn_cast<GetElementPtrInst>(curValue))
230 insertInferSite(gepInst);
231 for (
const auto it : curValue->users())
233 if (
const auto* loadInst = SVFUtil::dyn_cast<LoadInst>(it))
241 insertInferSite(loadInst);
243 else if (
const auto* storeInst =
244 SVFUtil::dyn_cast<StoreInst>(it))
246 if (storeInst->getPointerOperand() == curValue)
254 insertInferSite(storeInst);
258 for (
const auto nit :
259 storeInst->getPointerOperand()->users())
268 if (SVFUtil::isa<LoadInst>(nit))
269 insertInferSitesOrPushWorklist(nit);
274 if (
const auto* gepInst =
275 SVFUtil::dyn_cast<GetElementPtrInst>(
276 storeInst->getPointerOperand()))
296 const Value* gepBase = gepInst->getPointerOperand();
297 if (
const auto* load =
298 SVFUtil::dyn_cast<LoadInst>(gepBase))
300 for (
const auto loadUse :
301 load->getPointerOperand()->users())
303 if (loadUse == load ||
304 !SVFUtil::isa<LoadInst>(loadUse))
306 for (
const auto gepUse : loadUse->users())
308 if (!SVFUtil::isa<GetElementPtrInst>(
311 for (
const auto loadUse2 :
314 if (SVFUtil::isa<LoadInst>(
317 insertInferSitesOrPushWorklist(
324 else if (
const auto* alloc =
325 SVFUtil::dyn_cast<AllocaInst>(gepBase))
339 for (
const auto gepUse : alloc->users())
341 if (!SVFUtil::isa<GetElementPtrInst>(
344 for (
const auto loadUse2 : gepUse->users())
346 if (SVFUtil::isa<LoadInst>(loadUse2))
348 insertInferSitesOrPushWorklist(
357 else if (
const auto* gepInst =
358 SVFUtil::dyn_cast<GetElementPtrInst>(it))
367 if (gepInst->getPointerOperand() == curValue)
368 insertInferSite(gepInst);
370 else if (
const auto* bitcast =
371 SVFUtil::dyn_cast<BitCastInst>(it))
374 insertInferSitesOrPushWorklist(bitcast);
376 else if (
const auto* phiNode = SVFUtil::dyn_cast<PHINode>(it))
379 insertInferSitesOrPushWorklist(phiNode);
381 else if (
const auto* retInst =
382 SVFUtil::dyn_cast<ReturnInst>(it))
395 for (
const auto callsite : retInst->getFunction()->users())
397 if (
const auto* callBase =
398 SVFUtil::dyn_cast<CallBase>(callsite))
402 if (callBase->getCalledFunction() !=
403 retInst->getFunction())
405 insertInferSitesOrPushWorklist(callBase);
409 else if (
const auto* callBase = SVFUtil::dyn_cast<CallBase>(it))
424 if (SVFUtil::isa<Function>(curValue) &&
425 curValue == callBase->getCalledFunction())
429 if (!callBase->hasArgument(curValue))
431 if (
Function* calleeFunc = callBase->getCalledFunction())
433 u32_t pos = getArgPosInCall(callBase, curValue);
437 if (calleeFunc->isVarArg())
440 for (
auto& I : instructions(calleeFunc))
443 llvm::dyn_cast<llvm::LoadInst>(&I))
446 load->getPointerOperand();
447 if (loadPointer->getName().compare(
450 insertInferSitesOrPushWorklist(load);
455 else if (!calleeFunc->isDeclaration())
457 insertInferSitesOrPushWorklist(
458 calleeFunc->getArg(pos));
466 std::transform(infersites.begin(), infersites.end(),
467 std::inserter(types, types.begin()),
470 _valueToType[curValue] = selectLargestSizedType(types);
473 const Type*
type = _valueToType[var];
476 type = defaultType(var);
477 WARN_MSG(
"Using default type, trace ID is " +
494 auto tIt = _valueToAllocs.find(var);
495 if (tIt != _valueToAllocs.end())
503 workList.
push({var,
false});
504 while (!workList.
empty())
506 auto curPair = workList.
pop();
507 if (visited.count(curPair))
continue;
508 visited.insert(curPair);
509 const Value *curValue = curPair.first;
510 bool canUpdate = curPair.second;
513 auto insertAllocs = [&sources, &canUpdate](
const Value *source)
515 if (canUpdate) sources.insert(source);
517 auto insertAllocsOrPushWorklist = [
this, &sources, &workList, &canUpdate](
const auto &pUser)
519 auto vIt = _valueToAllocs.find(pUser);
522 if (vIt != _valueToAllocs.end())
524 sources.insert(vIt->second.begin(), vIt->second.end());
529 if (vIt == _valueToAllocs.end()) workList.push({pUser,
false});
533 if (!canUpdate && !_valueToAllocs.count(curValue))
535 workList.
push({curValue,
true});
538 if (isAlloc(curValue))
540 insertAllocs(curValue);
542 else if (
const auto *bitCastInst = SVFUtil::dyn_cast<BitCastInst>(curValue))
544 Value *prevVal = bitCastInst->getOperand(0);
545 insertAllocsOrPushWorklist(prevVal);
547 else if (
const auto *phiNode = SVFUtil::dyn_cast<PHINode>(curValue))
549 for (
u32_t i = 0; i < phiNode->getNumOperands(); ++i)
551 insertAllocsOrPushWorklist(phiNode->getOperand(i));
554 else if (
const auto *loadInst = SVFUtil::dyn_cast<LoadInst>(curValue))
556 for (
const auto use: loadInst->getPointerOperand()->users())
558 if (
const StoreInst *storeInst = SVFUtil::dyn_cast<StoreInst>(use))
560 if (storeInst->getPointerOperand() == loadInst->getPointerOperand())
562 insertAllocsOrPushWorklist(storeInst->getValueOperand());
567 else if (
const auto *argument = SVFUtil::dyn_cast<Argument>(curValue))
569 for (
const auto use: argument->getParent()->users())
571 if (
const CallBase *callBase = SVFUtil::dyn_cast<CallBase>(use))
575 if (callBase->getCalledFunction() != argument->getParent())
continue;
576 u32_t pos = argument->getParent()->isVarArg() ? 0 : argument->getArgNo();
577 insertAllocsOrPushWorklist(callBase->getArgOperand(pos));
581 else if (
const auto *callBase = SVFUtil::dyn_cast<CallBase>(curValue))
584 if (
Function *callee = callBase->getCalledFunction())
586 if (!callee->isDeclaration())
591 const Value *pValue = &exitBB->back();
592 const auto *retInst = SVFUtil::dyn_cast<ReturnInst>(pValue);
593 ABORT_IFNOT(retInst && retInst->getReturnValue(),
"not return inst?");
594 insertAllocsOrPushWorklist(retInst->getReturnValue());
622 if (
const Function *func = cs->getCalledFunction())
624 if (func->getName().find(
TYPEMALLOC) != std::string::npos)
626 const Type *objType = fwInferObjType(cs);
628 SVFUtil::dyn_cast<llvm::ConstantInt>(cs->getOperand(1));
629 assert(pInt &&
"the second argument is a integer");
630 u32_t iTyNum = objTyToNumFields(objType);
631 if (iTyNum >= pInt->getZExtValue())
649 u32_t iTyNum = objTyToNumFields(iTy);
661 assert(callBase->hasArgument(arg) &&
"callInst does not have argument arg?");
662 auto it = std::find(callBase->arg_begin(), callBase->arg_end(), arg);
663 assert(it != callBase->arg_end() &&
"Didn't find argument?");
664 return std::distance(callBase->arg_begin(), it);
670 if (objTys.empty())
return nullptr;
673 for (
const Type *ty: objTys)
675 typeSzToTypes[objTyToNumFields(ty)].insert(ty);
677 assert(!typeSzToTypes.empty() &&
"typeSzToTypes cannot be empty");
679 std::tie(std::ignore, largestTypes) = *typeSzToTypes.begin();
680 assert(!largestTypes.empty() &&
"largest element cannot be empty");
681 return *largestTypes.begin();
687 if (SVFUtil::isa<ArrayType>(objTy))
689 else if (
const auto *st = SVFUtil::dyn_cast<StructType>(objTy))
711 auto it = _thisPtrClassNames.find(thisPtr);
712 if (it != _thisPtrClassNames.end())
return it->second;
717 auto addNamesFromFunc = [&names](
const Function *func) ->
void
724 auto addNamesFromCall = [&names, &addNamesFromFunc](
const CallBase *call) ->
void
728 const auto *func = call->getCalledFunction();
730 else addNamesFromFunc(func);
734 for (
const auto &val: bwFindAllocOrClsNameSources(thisPtr))
741 if (val == thisPtr)
continue;
743 if (
const auto *func = SVFUtil::dyn_cast<Function>(val))
746 addNamesFromFunc(func);
752 addNamesFromCall(SVFUtil::cast<CallBase>(val));
754 else if (isAlloc(val))
757 ABORT_IFNOT((SVFUtil::isa<AllocaInst, CallBase, GlobalVariable>(val)),
759 for (
const auto *src : fwFindClsNameSources(val))
761 if (
const auto *func = SVFUtil::dyn_cast<Function>(src)) addNamesFromFunc(func);
762 else if (
const auto *call = SVFUtil::dyn_cast<CallBase>(src)) addNamesFromCall(call);
772 return _thisPtrClassNames[thisPtr] = names;
786 auto tIt = _valueToAllocOrClsNameSources.find(startValue);
787 if (tIt != _valueToAllocOrClsNameSources.end())
795 workList.
push({startValue,
false});
796 while (!workList.
empty())
798 auto curPair = workList.
pop();
799 if (visited.count(curPair))
continue;
800 visited.insert(curPair);
801 const Value *curValue = curPair.first;
802 bool canUpdate = curPair.second;
805 auto insertSource = [&sources, &canUpdate](
const Value *source)
807 if (canUpdate) sources.insert(source);
809 auto insertSourcesOrPushWorklist = [
this, &sources, &workList, &canUpdate](
const auto &pUser)
811 auto vIt = _valueToAllocOrClsNameSources.find(pUser);
814 if (vIt != _valueToAllocOrClsNameSources.end() && !vIt->second.empty())
816 sources.insert(vIt->second.begin(), vIt->second.end());
821 if (vIt == _valueToAllocOrClsNameSources.end()) workList.push({pUser,
false});
825 if (!canUpdate && !_valueToAllocOrClsNameSources.count(curValue))
827 workList.
push({curValue,
true});
831 if (
const auto *inst = SVFUtil::dyn_cast<Instruction>(curValue))
833 if (
const auto *parent = inst->getFunction())
843 insertSource(curValue);
847 if (
const auto *getElementPtrInst = SVFUtil::dyn_cast<GetElementPtrInst>(curValue))
849 insertSourcesOrPushWorklist(getElementPtrInst->getPointerOperand());
851 else if (
const auto *bitCastInst = SVFUtil::dyn_cast<BitCastInst>(curValue))
853 insertSourcesOrPushWorklist(bitCastInst->getOperand(0));
855 else if (
const auto *phiNode = SVFUtil::dyn_cast<PHINode>(curValue))
857 for (
const auto *op : phiNode->operand_values())
859 insertSourcesOrPushWorklist(op);
862 else if (
const auto *loadInst = SVFUtil::dyn_cast<LoadInst>(curValue))
864 for (
const auto *user : loadInst->getPointerOperand()->users())
866 if (
const auto *storeInst = SVFUtil::dyn_cast<StoreInst>(user))
868 if (storeInst->getPointerOperand() == loadInst->getPointerOperand())
870 insertSourcesOrPushWorklist(storeInst->getValueOperand());
875 else if (
const auto *argument = SVFUtil::dyn_cast<Argument>(curValue))
877 for (
const auto *user: argument->getParent()->users())
879 if (
const auto *callBase = SVFUtil::dyn_cast<CallBase>(user))
883 if (callBase->getCalledFunction() != argument->getParent())
continue;
884 u32_t pos = argument->getParent()->isVarArg() ? 0 : argument->getArgNo();
885 insertSourcesOrPushWorklist(callBase->getArgOperand(pos));
889 else if (
const auto *callBase = SVFUtil::dyn_cast<CallBase>(curValue))
892 if (
const auto *callee = callBase->getCalledFunction())
894 if (!callee->isDeclaration())
899 const Value *pValue = &exitBB->back();
900 const auto *retInst = SVFUtil::dyn_cast<ReturnInst>(pValue);
901 ABORT_IFNOT(retInst && retInst->getReturnValue(),
"not return inst?");
902 insertSourcesOrPushWorklist(retInst->getReturnValue());
910 _valueToAllocOrClsNameSources[curValue] = sources;
914 return _valueToAllocOrClsNameSources[startValue];
919 assert(startValue &&
"startValue was null?");
931 auto inferViaCppCall = [&sources](
const CallBase *caller)
938 for (
const auto *user : startValue->users())
940 if (
const auto *caller = SVFUtil::dyn_cast<CallBase>(user))
942 inferViaCppCall(caller);
944 else if (
const auto *bitcast = SVFUtil::dyn_cast<BitCastInst>(user))
946 for (
const auto *cast_user : bitcast->users())
948 if (
const auto *caller = SVFUtil::dyn_cast<CallBase>(cast_user))
950 inferViaCppCall(caller);
const Type * infersiteToType(const Value *val)
const std::string TYPEMALLOC
#define ABORT_IFNOT(condition, msg)
bool push(const Data &data)
SVFFunction * getSVFFunction(const Function *fun) const
LLVMContext & getContext() const
static LLVMModuleSet * getLLVMModuleSet()
LLVMContext & getLLVMCtx()
const Type * selectLargestSizedType(Set< const Type * > &objTys)
select the largest (conservative) type from all types
Set< const Value * > & bwfindAllocOfVar(const Value *var)
backward collect all possible allocation sites (stack, static, heap) of var
u32_t objTyToNumFields(const Type *objTy)
bool isAlloc(const SVF::Value *val)
is allocation (stack, static, heap)
u32_t getArgPosInCall(const CallBase *callBase, const Value *arg)
Set< const Value * > & bwFindAllocOrClsNameSources(const Value *startValue)
Set< std::string > & inferThisPtrClsName(const Value *thisPtr)
get or infer the class names of thisptr
void typeSizeDiffTest(const PointerType *oPTy, const Type *iTy, const Value *val)
const Type * fwInferObjType(const Value *var)
forward infer the type of the object pointed by var
const Type * inferObjType(const Value *var)
get or infer the type of the object pointed by the value
const Type * defaultType(const Value *val)
default type
ObjToClsNameSources _objToClsNameSources
Set< const CallBase * > & fwFindClsNameSources(const Value *startValue)
forward find class name sources starting from an allocation
void validateTypeCheck(const CallBase *cs)
validate type inference
static const Option< u32_t > MaxFieldLimit
Maximum number of field derivations for an object.
const SVFBasicBlock * getExitBB() const
bool isHeapAllocExtCallViaRet(const Instruction *inst)
std::string dumpType(const Type *type)
std::string dumpValueAndDbgInfo(const Value *val)
u32_t getNumOfElements(const Type *ety)
Return size of this object based on LLVM value.
static Type * getPtrElementType(const PointerType *pty)
bool isObject(const Value *ref)
Return true if this value refers to a object.
std::string sucMsg(const std::string &msg)
Returns successful message by converting a string into green string output.
std::string pasMsg(const std::string &msg)
Print each pass/phase message by converting a string into blue string output.
constexpr std::remove_reference< T >::type && move(T &&t) noexcept
std::string errMsg(const std::string &msg)
Print error message by converting a string into red string output.
std::ostream & errs()
Overwrite llvm::errs()
std::ostream & outs()
Overwrite llvm::outs()
std::string extractClsNameFromDynCast(const CallBase *callBase)
extract class name from cpp dyncast function
bool classTyHasVTable(const StructType *ty)
bool isClsNameSource(const Value *val)
Set< std::string > extractClsNamesFromFunc(const Function *foo)
extract class name from the c++ function name, e.g., constructor/destructors
bool isDynCast(const Function *foo)
whether foo is a cpp dyncast function
llvm::BasicBlock BasicBlock
llvm::AllocaInst AllocaInst
std::set< Key, Compare, Allocator > OrderedSet
llvm::GlobalValue GlobalValue
llvm::Value Value
LLVM Basic classes.
llvm::PointerType PointerType
llvm::StoreInst StoreInst
std::map< Key, Value, Compare, Allocator > OrderedMap
std::unordered_set< Key, Hash, KeyEqual, Allocator > Set
llvm::LLVMContext LLVMContext