Static Value-Flow Analysis
Loading...
Searching...
No Matches
ObjTypeInference.cpp
Go to the documentation of this file.
1//===- ObjTypeInference.cpp -- Type inference----------------------------//
2//
3// SVF: Static Value-Flow Analysis
4//
5// Copyright (C) <2013-> <Yulei Sui>
6//
7
8// This program is free software: you can redistribute it and/or modify
9// it under the terms of the GNU Affero General Public License as published by
10// the Free Software Foundation, either version 3 of the License, or
11// (at your option) any later version.
12
13// This program is distributed in the hope that it will be useful,
14// but WITHOUT ANY WARRANTY; without even the implied warranty of
15// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16// GNU Affero General Public License for more details.
17
18// You should have received a copy of the GNU Affero General Public License
19// along with this program. If not, see <http://www.gnu.org/licenses/>.
20//
21//===----------------------------------------------------------------------===//
22
23/*
24 * ObjTypeInference.cpp
25 *
26 * Created by Xiao Cheng on 10/01/24.
27 *
28 */
29
31#include "SVF-LLVM/BasicTypes.h"
32#include "SVF-LLVM/LLVMModule.h"
33#include "SVF-LLVM/LLVMUtil.h"
34#include "SVF-LLVM/CppUtil.h"
35#include "Util/Casting.h"
36
37#define TYPE_DEBUG 0 /* Turn this on if you're debugging type inference */
38#define ERR_MSG(msg) \
39 do \
40 { \
41 SVFUtil::errs() << SVFUtil::errMsg("Error ") << __FILE__ << ':' \
42 << __LINE__ << ": " << (msg) << '\n'; \
43 } while (0)
44#define ABORT_MSG(msg) \
45 do \
46 { \
47 ERR_MSG(msg); \
48 abort(); \
49 } while (0)
50#define ABORT_IFNOT(condition, msg) \
51 do \
52 { \
53 if (!(condition)) \
54 ABORT_MSG(msg); \
55 } while (0)
56
57#if TYPE_DEBUG
58#define WARN_MSG(msg) \
59 do \
60 { \
61 SVFUtil::outs() << SVFUtil::wrnMsg("Warning ") << __FILE__ << ':' \
62 << __LINE__ << ": " << msg << '\n'; \
63 } while (0)
64#define WARN_IFNOT(condition, msg) \
65 do \
66 { \
67 if (!(condition)) \
68 WARN_MSG(msg); \
69 } while (0)
70#else
71#define WARN_MSG(msg)
72#define WARN_IFNOT(condition, msg)
73#endif
74
75using namespace SVF;
76using namespace SVFUtil;
77using namespace LLVMUtil;
78using namespace cppUtil;
79
80// llvm::Value::hasUseList() was added in LLVM 21 alongside the change that
81// stopped instances of ConstantData (e.g. plain integer/float constants)
82// from carrying a use-list at all (see llvm/llvm-project@87f312a, "IR:
83// Remove uselist for constantdata"). On LLVM < 21 the method doesn't exist,
84// but the exact same condition is available through the public
85// isa<ConstantData> check that hasUseList() itself wraps internally.
86#if LLVM_VERSION_MAJOR >= 21
87static inline bool hasUseList(const Value* v)
88{
89 return v->hasUseList();
90}
91#else
92static inline bool hasUseList(const Value* v)
93{
95}
96#endif
97
98
99const std::string TYPEMALLOC = "TYPE_MALLOC";
100
103const Type *infersiteToType(const Value *val)
104{
105 assert(val && "value cannot be empty");
107 {
108 return llvm::getLoadStoreType(const_cast<Value *>(val));
109 }
110 else if (const auto *gepInst = SVFUtil::dyn_cast<GetElementPtrInst>(val))
111 {
112 return gepInst->getSourceElementType();
113 }
114 else if (const auto *call = SVFUtil::dyn_cast<CallBase>(val))
115 {
116 return call->getFunctionType();
117 }
118 else if (const auto *allocaInst = SVFUtil::dyn_cast<AllocaInst>(val))
119 {
120 return allocaInst->getAllocatedType();
121 }
122 else if (const auto *globalValue = SVFUtil::dyn_cast<GlobalValue>(val))
123 {
124 return globalValue->getValueType();
125 }
126 else
127 {
128 ABORT_MSG("unknown value:" + dumpValueAndDbgInfo(val));
129 }
130}
131
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}
142
147
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}
199
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}
221
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
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}
551
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
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
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}
698
700{
701 return LLVMUtil::isObject(val);
702}
703
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}
732
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}
740
741
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}
757
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}
772
773
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}
848
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
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 {
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}
1005
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}
#define ABORT_MSG(msg)
const std::string TYPEMALLOC
const Type * infersiteToType(const Value *val)
#define ABORT_IFNOT(condition, msg)
#define ERR_MSG(msg)
#define WARN_MSG(msg)
static bool hasUseList(const Value *v)
newitem type
Definition cJSON.cpp:2739
const char *const name
Definition cJSON.h:264
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
LLVMContext & getContext() const
Definition LLVMModule.h:393
ValueToInferSites _valueToInferSites
ValueToSources _valueToAllocs
const Type * selectLargestSizedType(Set< const Type * > &objTys)
select the largest (conservative) type from all types
const Type * inferPointsToType(const Value *var)
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)
ValueToClassNames _thisPtrClassNames
Set< std::string > & inferThisPtrClsName(const Value *thisPtr)
get or infer the class names of thisptr
const Type * fwInferObjType(const Value *var)
forward infer the type of the object pointed by var
const IntegerType * int8Type()
int8 type
const Type * ptrType()
pointer type
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
ValueToSources _valueToAllocOrClsNameSources
static const Option< u32_t > MaxFieldLimit
Maximum number of field derivations for an object.
Definition Options.h:34
bool isHeapAllocExtCallViaRet(const Instruction *inst)
Definition LLVMUtil.cpp:645
bool isMemcpyExtFun(const Function *fun)
Definition LLVMUtil.cpp:390
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 dumpValueAndDbgInfo(const Value *val)
Definition LLVMUtil.cpp:634
u32_t getNumOfElements(const Type *ety)
Return size of this object based on LLVM value.
Definition LLVMUtil.cpp:297
bool isObject(const Value *ref)
Return true if this value refers to a object.
Definition LLVMUtil.cpp:61
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::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
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
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
std::string extractClsNameFromDynCast(const CallBase *callBase)
extract class name from cpp dyncast function
Definition CppUtil.cpp:951
bool classTyHasVTable(const StructType *ty)
Definition CppUtil.cpp:602
bool isClsNameSource(const Value *val)
Definition CppUtil.cpp:893
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
for isBitcode
Definition BasicTypes.h:70
std::map< Key, Value, Compare, Allocator > OrderedMap
Definition GeneralType.h:64
llvm::Type Type
Definition BasicTypes.h:81
llvm::CallBase CallBase
Definition BasicTypes.h:147
llvm::BasicBlock BasicBlock
Definition BasicTypes.h:84
llvm::AllocaInst AllocaInst
Definition BasicTypes.h:151
std::set< Key, Compare, Allocator > OrderedSet
Definition GeneralType.h:60
std::unordered_set< Key, Hash, KeyEqual, Allocator > Set
Definition GeneralType.h:51
llvm::Function Function
Definition BasicTypes.h:83
llvm::GlobalValue GlobalValue
Definition BasicTypes.h:86
llvm::Value Value
LLVM Basic classes.
Definition BasicTypes.h:80
llvm::StoreInst StoreInst
Definition BasicTypes.h:149
unsigned u32_t
Definition GeneralType.h:67
llvm::LLVMContext LLVMContext
Definition BasicTypes.h:72