ExprEngine.cpp 117 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488248924902491249224932494249524962497249824992500250125022503250425052506250725082509251025112512251325142515251625172518251925202521252225232524252525262527252825292530253125322533253425352536253725382539254025412542254325442545254625472548254925502551255225532554255525562557255825592560256125622563256425652566256725682569257025712572257325742575257625772578257925802581258225832584258525862587258825892590259125922593259425952596259725982599260026012602260326042605260626072608260926102611261226132614261526162617261826192620262126222623262426252626262726282629263026312632263326342635263626372638263926402641264226432644264526462647264826492650265126522653265426552656265726582659266026612662266326642665266626672668266926702671267226732674267526762677267826792680268126822683268426852686268726882689269026912692269326942695269626972698269927002701270227032704270527062707270827092710271127122713271427152716271727182719272027212722272327242725272627272728272927302731273227332734273527362737273827392740274127422743274427452746274727482749275027512752275327542755275627572758275927602761276227632764276527662767276827692770277127722773277427752776277727782779278027812782278327842785278627872788278927902791279227932794279527962797279827992800280128022803280428052806280728082809281028112812281328142815281628172818281928202821282228232824282528262827282828292830283128322833283428352836283728382839284028412842284328442845284628472848284928502851285228532854285528562857285828592860286128622863286428652866286728682869287028712872287328742875287628772878287928802881288228832884288528862887288828892890289128922893289428952896289728982899290029012902290329042905290629072908290929102911291229132914291529162917291829192920292129222923292429252926292729282929293029312932293329342935293629372938293929402941294229432944294529462947294829492950295129522953295429552956295729582959296029612962296329642965296629672968296929702971297229732974297529762977297829792980298129822983298429852986298729882989299029912992299329942995299629972998299930003001300230033004300530063007300830093010301130123013301430153016301730183019302030213022302330243025302630273028302930303031303230333034303530363037303830393040304130423043304430453046304730483049305030513052305330543055305630573058305930603061306230633064306530663067306830693070307130723073307430753076307730783079308030813082308330843085308630873088308930903091309230933094309530963097309830993100310131023103310431053106310731083109311031113112311331143115311631173118311931203121312231233124312531263127312831293130313131323133313431353136313731383139314031413142314331443145314631473148314931503151315231533154315531563157315831593160
  1. //===- ExprEngine.cpp - Path-Sensitive Expression-Level Dataflow ----------===//
  2. //
  3. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
  4. // See https://llvm.org/LICENSE.txt for license information.
  5. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
  6. //
  7. //===----------------------------------------------------------------------===//
  8. //
  9. // This file defines a meta-engine for path-sensitive dataflow analysis that
  10. // is built on GREngine, but provides the boilerplate to execute transfer
  11. // functions and build the ExplodedGraph at the expression level.
  12. //
  13. //===----------------------------------------------------------------------===//
  14. #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
  15. #include "PrettyStackTraceLocationContext.h"
  16. #include "clang/AST/ASTContext.h"
  17. #include "clang/AST/Decl.h"
  18. #include "clang/AST/DeclBase.h"
  19. #include "clang/AST/DeclCXX.h"
  20. #include "clang/AST/DeclObjC.h"
  21. #include "clang/AST/Expr.h"
  22. #include "clang/AST/ExprCXX.h"
  23. #include "clang/AST/ExprObjC.h"
  24. #include "clang/AST/ParentMap.h"
  25. #include "clang/AST/PrettyPrinter.h"
  26. #include "clang/AST/Stmt.h"
  27. #include "clang/AST/StmtCXX.h"
  28. #include "clang/AST/StmtObjC.h"
  29. #include "clang/AST/Type.h"
  30. #include "clang/Analysis/AnalysisDeclContext.h"
  31. #include "clang/Analysis/CFG.h"
  32. #include "clang/Analysis/ConstructionContext.h"
  33. #include "clang/Analysis/ProgramPoint.h"
  34. #include "clang/Basic/IdentifierTable.h"
  35. #include "clang/Basic/JsonSupport.h"
  36. #include "clang/Basic/LLVM.h"
  37. #include "clang/Basic/LangOptions.h"
  38. #include "clang/Basic/PrettyStackTrace.h"
  39. #include "clang/Basic/SourceLocation.h"
  40. #include "clang/Basic/SourceManager.h"
  41. #include "clang/Basic/Specifiers.h"
  42. #include "clang/StaticAnalyzer/Core/AnalyzerOptions.h"
  43. #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
  44. #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
  45. #include "clang/StaticAnalyzer/Core/CheckerManager.h"
  46. #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
  47. #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
  48. #include "clang/StaticAnalyzer/Core/PathSensitive/ConstraintManager.h"
  49. #include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h"
  50. #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
  51. #include "clang/StaticAnalyzer/Core/PathSensitive/LoopUnrolling.h"
  52. #include "clang/StaticAnalyzer/Core/PathSensitive/LoopWidening.h"
  53. #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
  54. #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
  55. #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
  56. #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
  57. #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
  58. #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
  59. #include "clang/StaticAnalyzer/Core/PathSensitive/Store.h"
  60. #include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
  61. #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
  62. #include "llvm/ADT/APSInt.h"
  63. #include "llvm/ADT/DenseMap.h"
  64. #include "llvm/ADT/ImmutableMap.h"
  65. #include "llvm/ADT/ImmutableSet.h"
  66. #include "llvm/ADT/Optional.h"
  67. #include "llvm/ADT/SmallVector.h"
  68. #include "llvm/ADT/Statistic.h"
  69. #include "llvm/Support/Casting.h"
  70. #include "llvm/Support/Compiler.h"
  71. #include "llvm/Support/DOTGraphTraits.h"
  72. #include "llvm/Support/ErrorHandling.h"
  73. #include "llvm/Support/GraphWriter.h"
  74. #include "llvm/Support/SaveAndRestore.h"
  75. #include "llvm/Support/raw_ostream.h"
  76. #include <cassert>
  77. #include <cstdint>
  78. #include <memory>
  79. #include <string>
  80. #include <tuple>
  81. #include <utility>
  82. #include <vector>
  83. using namespace clang;
  84. using namespace ento;
  85. #define DEBUG_TYPE "ExprEngine"
  86. STATISTIC(NumRemoveDeadBindings,
  87. "The # of times RemoveDeadBindings is called");
  88. STATISTIC(NumMaxBlockCountReached,
  89. "The # of aborted paths due to reaching the maximum block count in "
  90. "a top level function");
  91. STATISTIC(NumMaxBlockCountReachedInInlined,
  92. "The # of aborted paths due to reaching the maximum block count in "
  93. "an inlined function");
  94. STATISTIC(NumTimesRetriedWithoutInlining,
  95. "The # of times we re-evaluated a call without inlining");
  96. //===----------------------------------------------------------------------===//
  97. // Internal program state traits.
  98. //===----------------------------------------------------------------------===//
  99. namespace {
  100. // When modeling a C++ constructor, for a variety of reasons we need to track
  101. // the location of the object for the duration of its ConstructionContext.
  102. // ObjectsUnderConstruction maps statements within the construction context
  103. // to the object's location, so that on every such statement the location
  104. // could have been retrieved.
  105. /// ConstructedObjectKey is used for being able to find the path-sensitive
  106. /// memory region of a freshly constructed object while modeling the AST node
  107. /// that syntactically represents the object that is being constructed.
  108. /// Semantics of such nodes may sometimes require access to the region that's
  109. /// not otherwise present in the program state, or to the very fact that
  110. /// the construction context was present and contained references to these
  111. /// AST nodes.
  112. class ConstructedObjectKey {
  113. typedef std::pair<ConstructionContextItem, const LocationContext *>
  114. ConstructedObjectKeyImpl;
  115. const ConstructedObjectKeyImpl Impl;
  116. const void *getAnyASTNodePtr() const {
  117. if (const Stmt *S = getItem().getStmtOrNull())
  118. return S;
  119. else
  120. return getItem().getCXXCtorInitializer();
  121. }
  122. public:
  123. explicit ConstructedObjectKey(const ConstructionContextItem &Item,
  124. const LocationContext *LC)
  125. : Impl(Item, LC) {}
  126. const ConstructionContextItem &getItem() const { return Impl.first; }
  127. const LocationContext *getLocationContext() const { return Impl.second; }
  128. ASTContext &getASTContext() const {
  129. return getLocationContext()->getDecl()->getASTContext();
  130. }
  131. void printJson(llvm::raw_ostream &Out, PrinterHelper *Helper,
  132. PrintingPolicy &PP) const {
  133. const Stmt *S = getItem().getStmtOrNull();
  134. const CXXCtorInitializer *I = nullptr;
  135. if (!S)
  136. I = getItem().getCXXCtorInitializer();
  137. if (S)
  138. Out << "\"stmt_id\": " << S->getID(getASTContext());
  139. else
  140. Out << "\"init_id\": " << I->getID(getASTContext());
  141. // Kind
  142. Out << ", \"kind\": \"" << getItem().getKindAsString()
  143. << "\", \"argument_index\": ";
  144. if (getItem().getKind() == ConstructionContextItem::ArgumentKind)
  145. Out << getItem().getIndex();
  146. else
  147. Out << "null";
  148. // Pretty-print
  149. Out << ", \"pretty\": ";
  150. if (S) {
  151. S->printJson(Out, Helper, PP, /*AddQuotes=*/true);
  152. } else {
  153. Out << '\"' << I->getAnyMember()->getNameAsString() << '\"';
  154. }
  155. }
  156. void Profile(llvm::FoldingSetNodeID &ID) const {
  157. ID.Add(Impl.first);
  158. ID.AddPointer(Impl.second);
  159. }
  160. bool operator==(const ConstructedObjectKey &RHS) const {
  161. return Impl == RHS.Impl;
  162. }
  163. bool operator<(const ConstructedObjectKey &RHS) const {
  164. return Impl < RHS.Impl;
  165. }
  166. };
  167. } // namespace
  168. typedef llvm::ImmutableMap<ConstructedObjectKey, SVal>
  169. ObjectsUnderConstructionMap;
  170. REGISTER_TRAIT_WITH_PROGRAMSTATE(ObjectsUnderConstruction,
  171. ObjectsUnderConstructionMap)
  172. //===----------------------------------------------------------------------===//
  173. // Engine construction and deletion.
  174. //===----------------------------------------------------------------------===//
  175. static const char* TagProviderName = "ExprEngine";
  176. ExprEngine::ExprEngine(cross_tu::CrossTranslationUnitContext &CTU,
  177. AnalysisManager &mgr,
  178. SetOfConstDecls *VisitedCalleesIn,
  179. FunctionSummariesTy *FS,
  180. InliningModes HowToInlineIn)
  181. : CTU(CTU), AMgr(mgr),
  182. AnalysisDeclContexts(mgr.getAnalysisDeclContextManager()),
  183. Engine(*this, FS, mgr.getAnalyzerOptions()), G(Engine.getGraph()),
  184. StateMgr(getContext(), mgr.getStoreManagerCreator(),
  185. mgr.getConstraintManagerCreator(), G.getAllocator(),
  186. this),
  187. SymMgr(StateMgr.getSymbolManager()),
  188. MRMgr(StateMgr.getRegionManager()),
  189. svalBuilder(StateMgr.getSValBuilder()),
  190. ObjCNoRet(mgr.getASTContext()),
  191. BR(mgr, *this),
  192. VisitedCallees(VisitedCalleesIn),
  193. HowToInline(HowToInlineIn)
  194. {
  195. unsigned TrimInterval = mgr.options.GraphTrimInterval;
  196. if (TrimInterval != 0) {
  197. // Enable eager node reclamation when constructing the ExplodedGraph.
  198. G.enableNodeReclamation(TrimInterval);
  199. }
  200. }
  201. //===----------------------------------------------------------------------===//
  202. // Utility methods.
  203. //===----------------------------------------------------------------------===//
  204. ProgramStateRef ExprEngine::getInitialState(const LocationContext *InitLoc) {
  205. ProgramStateRef state = StateMgr.getInitialState(InitLoc);
  206. const Decl *D = InitLoc->getDecl();
  207. // Preconditions.
  208. // FIXME: It would be nice if we had a more general mechanism to add
  209. // such preconditions. Some day.
  210. do {
  211. if (const auto *FD = dyn_cast<FunctionDecl>(D)) {
  212. // Precondition: the first argument of 'main' is an integer guaranteed
  213. // to be > 0.
  214. const IdentifierInfo *II = FD->getIdentifier();
  215. if (!II || !(II->getName() == "main" && FD->getNumParams() > 0))
  216. break;
  217. const ParmVarDecl *PD = FD->getParamDecl(0);
  218. QualType T = PD->getType();
  219. const auto *BT = dyn_cast<BuiltinType>(T);
  220. if (!BT || !BT->isInteger())
  221. break;
  222. const MemRegion *R = state->getRegion(PD, InitLoc);
  223. if (!R)
  224. break;
  225. SVal V = state->getSVal(loc::MemRegionVal(R));
  226. SVal Constraint_untested = evalBinOp(state, BO_GT, V,
  227. svalBuilder.makeZeroVal(T),
  228. svalBuilder.getConditionType());
  229. Optional<DefinedOrUnknownSVal> Constraint =
  230. Constraint_untested.getAs<DefinedOrUnknownSVal>();
  231. if (!Constraint)
  232. break;
  233. if (ProgramStateRef newState = state->assume(*Constraint, true))
  234. state = newState;
  235. }
  236. break;
  237. }
  238. while (false);
  239. if (const auto *MD = dyn_cast<ObjCMethodDecl>(D)) {
  240. // Precondition: 'self' is always non-null upon entry to an Objective-C
  241. // method.
  242. const ImplicitParamDecl *SelfD = MD->getSelfDecl();
  243. const MemRegion *R = state->getRegion(SelfD, InitLoc);
  244. SVal V = state->getSVal(loc::MemRegionVal(R));
  245. if (Optional<Loc> LV = V.getAs<Loc>()) {
  246. // Assume that the pointer value in 'self' is non-null.
  247. state = state->assume(*LV, true);
  248. assert(state && "'self' cannot be null");
  249. }
  250. }
  251. if (const auto *MD = dyn_cast<CXXMethodDecl>(D)) {
  252. if (!MD->isStatic()) {
  253. // Precondition: 'this' is always non-null upon entry to the
  254. // top-level function. This is our starting assumption for
  255. // analyzing an "open" program.
  256. const StackFrameContext *SFC = InitLoc->getStackFrame();
  257. if (SFC->getParent() == nullptr) {
  258. loc::MemRegionVal L = svalBuilder.getCXXThis(MD, SFC);
  259. SVal V = state->getSVal(L);
  260. if (Optional<Loc> LV = V.getAs<Loc>()) {
  261. state = state->assume(*LV, true);
  262. assert(state && "'this' cannot be null");
  263. }
  264. }
  265. }
  266. }
  267. return state;
  268. }
  269. ProgramStateRef ExprEngine::createTemporaryRegionIfNeeded(
  270. ProgramStateRef State, const LocationContext *LC,
  271. const Expr *InitWithAdjustments, const Expr *Result,
  272. const SubRegion **OutRegionWithAdjustments) {
  273. // FIXME: This function is a hack that works around the quirky AST
  274. // we're often having with respect to C++ temporaries. If only we modelled
  275. // the actual execution order of statements properly in the CFG,
  276. // all the hassle with adjustments would not be necessary,
  277. // and perhaps the whole function would be removed.
  278. SVal InitValWithAdjustments = State->getSVal(InitWithAdjustments, LC);
  279. if (!Result) {
  280. // If we don't have an explicit result expression, we're in "if needed"
  281. // mode. Only create a region if the current value is a NonLoc.
  282. if (!InitValWithAdjustments.getAs<NonLoc>()) {
  283. if (OutRegionWithAdjustments)
  284. *OutRegionWithAdjustments = nullptr;
  285. return State;
  286. }
  287. Result = InitWithAdjustments;
  288. } else {
  289. // We need to create a region no matter what. For sanity, make sure we don't
  290. // try to stuff a Loc into a non-pointer temporary region.
  291. assert(!InitValWithAdjustments.getAs<Loc>() ||
  292. Loc::isLocType(Result->getType()) ||
  293. Result->getType()->isMemberPointerType());
  294. }
  295. ProgramStateManager &StateMgr = State->getStateManager();
  296. MemRegionManager &MRMgr = StateMgr.getRegionManager();
  297. StoreManager &StoreMgr = StateMgr.getStoreManager();
  298. // MaterializeTemporaryExpr may appear out of place, after a few field and
  299. // base-class accesses have been made to the object, even though semantically
  300. // it is the whole object that gets materialized and lifetime-extended.
  301. //
  302. // For example:
  303. //
  304. // `-MaterializeTemporaryExpr
  305. // `-MemberExpr
  306. // `-CXXTemporaryObjectExpr
  307. //
  308. // instead of the more natural
  309. //
  310. // `-MemberExpr
  311. // `-MaterializeTemporaryExpr
  312. // `-CXXTemporaryObjectExpr
  313. //
  314. // Use the usual methods for obtaining the expression of the base object,
  315. // and record the adjustments that we need to make to obtain the sub-object
  316. // that the whole expression 'Ex' refers to. This trick is usual,
  317. // in the sense that CodeGen takes a similar route.
  318. SmallVector<const Expr *, 2> CommaLHSs;
  319. SmallVector<SubobjectAdjustment, 2> Adjustments;
  320. const Expr *Init = InitWithAdjustments->skipRValueSubobjectAdjustments(
  321. CommaLHSs, Adjustments);
  322. // Take the region for Init, i.e. for the whole object. If we do not remember
  323. // the region in which the object originally was constructed, come up with
  324. // a new temporary region out of thin air and copy the contents of the object
  325. // (which are currently present in the Environment, because Init is an rvalue)
  326. // into that region. This is not correct, but it is better than nothing.
  327. const TypedValueRegion *TR = nullptr;
  328. if (const auto *MT = dyn_cast<MaterializeTemporaryExpr>(Result)) {
  329. if (Optional<SVal> V = getObjectUnderConstruction(State, MT, LC)) {
  330. State = finishObjectConstruction(State, MT, LC);
  331. State = State->BindExpr(Result, LC, *V);
  332. return State;
  333. } else {
  334. StorageDuration SD = MT->getStorageDuration();
  335. // If this object is bound to a reference with static storage duration, we
  336. // put it in a different region to prevent "address leakage" warnings.
  337. if (SD == SD_Static || SD == SD_Thread) {
  338. TR = MRMgr.getCXXStaticTempObjectRegion(Init);
  339. } else {
  340. TR = MRMgr.getCXXTempObjectRegion(Init, LC);
  341. }
  342. }
  343. } else {
  344. TR = MRMgr.getCXXTempObjectRegion(Init, LC);
  345. }
  346. SVal Reg = loc::MemRegionVal(TR);
  347. SVal BaseReg = Reg;
  348. // Make the necessary adjustments to obtain the sub-object.
  349. for (auto I = Adjustments.rbegin(), E = Adjustments.rend(); I != E; ++I) {
  350. const SubobjectAdjustment &Adj = *I;
  351. switch (Adj.Kind) {
  352. case SubobjectAdjustment::DerivedToBaseAdjustment:
  353. Reg = StoreMgr.evalDerivedToBase(Reg, Adj.DerivedToBase.BasePath);
  354. break;
  355. case SubobjectAdjustment::FieldAdjustment:
  356. Reg = StoreMgr.getLValueField(Adj.Field, Reg);
  357. break;
  358. case SubobjectAdjustment::MemberPointerAdjustment:
  359. // FIXME: Unimplemented.
  360. State = State->invalidateRegions(Reg, InitWithAdjustments,
  361. currBldrCtx->blockCount(), LC, true,
  362. nullptr, nullptr, nullptr);
  363. return State;
  364. }
  365. }
  366. // What remains is to copy the value of the object to the new region.
  367. // FIXME: In other words, what we should always do is copy value of the
  368. // Init expression (which corresponds to the bigger object) to the whole
  369. // temporary region TR. However, this value is often no longer present
  370. // in the Environment. If it has disappeared, we instead invalidate TR.
  371. // Still, what we can do is assign the value of expression Ex (which
  372. // corresponds to the sub-object) to the TR's sub-region Reg. At least,
  373. // values inside Reg would be correct.
  374. SVal InitVal = State->getSVal(Init, LC);
  375. if (InitVal.isUnknown()) {
  376. InitVal = getSValBuilder().conjureSymbolVal(Result, LC, Init->getType(),
  377. currBldrCtx->blockCount());
  378. State = State->bindLoc(BaseReg.castAs<Loc>(), InitVal, LC, false);
  379. // Then we'd need to take the value that certainly exists and bind it
  380. // over.
  381. if (InitValWithAdjustments.isUnknown()) {
  382. // Try to recover some path sensitivity in case we couldn't
  383. // compute the value.
  384. InitValWithAdjustments = getSValBuilder().conjureSymbolVal(
  385. Result, LC, InitWithAdjustments->getType(),
  386. currBldrCtx->blockCount());
  387. }
  388. State =
  389. State->bindLoc(Reg.castAs<Loc>(), InitValWithAdjustments, LC, false);
  390. } else {
  391. State = State->bindLoc(BaseReg.castAs<Loc>(), InitVal, LC, false);
  392. }
  393. // The result expression would now point to the correct sub-region of the
  394. // newly created temporary region. Do this last in order to getSVal of Init
  395. // correctly in case (Result == Init).
  396. if (Result->isGLValue()) {
  397. State = State->BindExpr(Result, LC, Reg);
  398. } else {
  399. State = State->BindExpr(Result, LC, InitValWithAdjustments);
  400. }
  401. // Notify checkers once for two bindLoc()s.
  402. State = processRegionChange(State, TR, LC);
  403. if (OutRegionWithAdjustments)
  404. *OutRegionWithAdjustments = cast<SubRegion>(Reg.getAsRegion());
  405. return State;
  406. }
  407. ProgramStateRef
  408. ExprEngine::addObjectUnderConstruction(ProgramStateRef State,
  409. const ConstructionContextItem &Item,
  410. const LocationContext *LC, SVal V) {
  411. ConstructedObjectKey Key(Item, LC->getStackFrame());
  412. // FIXME: Currently the state might already contain the marker due to
  413. // incorrect handling of temporaries bound to default parameters.
  414. assert(!State->get<ObjectsUnderConstruction>(Key) ||
  415. Key.getItem().getKind() ==
  416. ConstructionContextItem::TemporaryDestructorKind);
  417. return State->set<ObjectsUnderConstruction>(Key, V);
  418. }
  419. Optional<SVal>
  420. ExprEngine::getObjectUnderConstruction(ProgramStateRef State,
  421. const ConstructionContextItem &Item,
  422. const LocationContext *LC) {
  423. ConstructedObjectKey Key(Item, LC->getStackFrame());
  424. return Optional<SVal>::create(State->get<ObjectsUnderConstruction>(Key));
  425. }
  426. ProgramStateRef
  427. ExprEngine::finishObjectConstruction(ProgramStateRef State,
  428. const ConstructionContextItem &Item,
  429. const LocationContext *LC) {
  430. ConstructedObjectKey Key(Item, LC->getStackFrame());
  431. assert(State->contains<ObjectsUnderConstruction>(Key));
  432. return State->remove<ObjectsUnderConstruction>(Key);
  433. }
  434. ProgramStateRef ExprEngine::elideDestructor(ProgramStateRef State,
  435. const CXXBindTemporaryExpr *BTE,
  436. const LocationContext *LC) {
  437. ConstructedObjectKey Key({BTE, /*IsElided=*/true}, LC);
  438. // FIXME: Currently the state might already contain the marker due to
  439. // incorrect handling of temporaries bound to default parameters.
  440. return State->set<ObjectsUnderConstruction>(Key, UnknownVal());
  441. }
  442. ProgramStateRef
  443. ExprEngine::cleanupElidedDestructor(ProgramStateRef State,
  444. const CXXBindTemporaryExpr *BTE,
  445. const LocationContext *LC) {
  446. ConstructedObjectKey Key({BTE, /*IsElided=*/true}, LC);
  447. assert(State->contains<ObjectsUnderConstruction>(Key));
  448. return State->remove<ObjectsUnderConstruction>(Key);
  449. }
  450. bool ExprEngine::isDestructorElided(ProgramStateRef State,
  451. const CXXBindTemporaryExpr *BTE,
  452. const LocationContext *LC) {
  453. ConstructedObjectKey Key({BTE, /*IsElided=*/true}, LC);
  454. return State->contains<ObjectsUnderConstruction>(Key);
  455. }
  456. bool ExprEngine::areAllObjectsFullyConstructed(ProgramStateRef State,
  457. const LocationContext *FromLC,
  458. const LocationContext *ToLC) {
  459. const LocationContext *LC = FromLC;
  460. while (LC != ToLC) {
  461. assert(LC && "ToLC must be a parent of FromLC!");
  462. for (auto I : State->get<ObjectsUnderConstruction>())
  463. if (I.first.getLocationContext() == LC)
  464. return false;
  465. LC = LC->getParent();
  466. }
  467. return true;
  468. }
  469. //===----------------------------------------------------------------------===//
  470. // Top-level transfer function logic (Dispatcher).
  471. //===----------------------------------------------------------------------===//
  472. /// evalAssume - Called by ConstraintManager. Used to call checker-specific
  473. /// logic for handling assumptions on symbolic values.
  474. ProgramStateRef ExprEngine::processAssume(ProgramStateRef state,
  475. SVal cond, bool assumption) {
  476. return getCheckerManager().runCheckersForEvalAssume(state, cond, assumption);
  477. }
  478. ProgramStateRef
  479. ExprEngine::processRegionChanges(ProgramStateRef state,
  480. const InvalidatedSymbols *invalidated,
  481. ArrayRef<const MemRegion *> Explicits,
  482. ArrayRef<const MemRegion *> Regions,
  483. const LocationContext *LCtx,
  484. const CallEvent *Call) {
  485. return getCheckerManager().runCheckersForRegionChanges(state, invalidated,
  486. Explicits, Regions,
  487. LCtx, Call);
  488. }
  489. static void
  490. printObjectsUnderConstructionJson(raw_ostream &Out, ProgramStateRef State,
  491. const char *NL, const LocationContext *LCtx,
  492. unsigned int Space = 0, bool IsDot = false) {
  493. PrintingPolicy PP =
  494. LCtx->getAnalysisDeclContext()->getASTContext().getPrintingPolicy();
  495. ++Space;
  496. bool HasItem = false;
  497. // Store the last key.
  498. const ConstructedObjectKey *LastKey = nullptr;
  499. for (const auto &I : State->get<ObjectsUnderConstruction>()) {
  500. const ConstructedObjectKey &Key = I.first;
  501. if (Key.getLocationContext() != LCtx)
  502. continue;
  503. if (!HasItem) {
  504. Out << "[" << NL;
  505. HasItem = true;
  506. }
  507. LastKey = &Key;
  508. }
  509. for (const auto &I : State->get<ObjectsUnderConstruction>()) {
  510. const ConstructedObjectKey &Key = I.first;
  511. SVal Value = I.second;
  512. if (Key.getLocationContext() != LCtx)
  513. continue;
  514. Indent(Out, Space, IsDot) << "{ ";
  515. Key.printJson(Out, nullptr, PP);
  516. Out << ", \"value\": \"" << Value << "\" }";
  517. if (&Key != LastKey)
  518. Out << ',';
  519. Out << NL;
  520. }
  521. if (HasItem)
  522. Indent(Out, --Space, IsDot) << ']'; // End of "location_context".
  523. else {
  524. Out << "null ";
  525. }
  526. }
  527. void ExprEngine::printJson(raw_ostream &Out, ProgramStateRef State,
  528. const LocationContext *LCtx, const char *NL,
  529. unsigned int Space, bool IsDot) const {
  530. Indent(Out, Space, IsDot) << "\"constructing_objects\": ";
  531. if (LCtx && !State->get<ObjectsUnderConstruction>().isEmpty()) {
  532. ++Space;
  533. Out << '[' << NL;
  534. LCtx->printJson(Out, NL, Space, IsDot, [&](const LocationContext *LC) {
  535. printObjectsUnderConstructionJson(Out, State, NL, LC, Space, IsDot);
  536. });
  537. --Space;
  538. Indent(Out, Space, IsDot) << "]," << NL; // End of "constructing_objects".
  539. } else {
  540. Out << "null," << NL;
  541. }
  542. getCheckerManager().runCheckersForPrintStateJson(Out, State, NL, Space,
  543. IsDot);
  544. }
  545. void ExprEngine::processEndWorklist() {
  546. getCheckerManager().runCheckersForEndAnalysis(G, BR, *this);
  547. }
  548. void ExprEngine::processCFGElement(const CFGElement E, ExplodedNode *Pred,
  549. unsigned StmtIdx, NodeBuilderContext *Ctx) {
  550. PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
  551. currStmtIdx = StmtIdx;
  552. currBldrCtx = Ctx;
  553. switch (E.getKind()) {
  554. case CFGElement::Statement:
  555. case CFGElement::Constructor:
  556. case CFGElement::CXXRecordTypedCall:
  557. ProcessStmt(E.castAs<CFGStmt>().getStmt(), Pred);
  558. return;
  559. case CFGElement::Initializer:
  560. ProcessInitializer(E.castAs<CFGInitializer>(), Pred);
  561. return;
  562. case CFGElement::NewAllocator:
  563. ProcessNewAllocator(E.castAs<CFGNewAllocator>().getAllocatorExpr(),
  564. Pred);
  565. return;
  566. case CFGElement::AutomaticObjectDtor:
  567. case CFGElement::DeleteDtor:
  568. case CFGElement::BaseDtor:
  569. case CFGElement::MemberDtor:
  570. case CFGElement::TemporaryDtor:
  571. ProcessImplicitDtor(E.castAs<CFGImplicitDtor>(), Pred);
  572. return;
  573. case CFGElement::LoopExit:
  574. ProcessLoopExit(E.castAs<CFGLoopExit>().getLoopStmt(), Pred);
  575. return;
  576. case CFGElement::LifetimeEnds:
  577. case CFGElement::ScopeBegin:
  578. case CFGElement::ScopeEnd:
  579. return;
  580. }
  581. }
  582. static bool shouldRemoveDeadBindings(AnalysisManager &AMgr,
  583. const Stmt *S,
  584. const ExplodedNode *Pred,
  585. const LocationContext *LC) {
  586. // Are we never purging state values?
  587. if (AMgr.options.AnalysisPurgeOpt == PurgeNone)
  588. return false;
  589. // Is this the beginning of a basic block?
  590. if (Pred->getLocation().getAs<BlockEntrance>())
  591. return true;
  592. // Is this on a non-expression?
  593. if (!isa<Expr>(S))
  594. return true;
  595. // Run before processing a call.
  596. if (CallEvent::isCallStmt(S))
  597. return true;
  598. // Is this an expression that is consumed by another expression? If so,
  599. // postpone cleaning out the state.
  600. ParentMap &PM = LC->getAnalysisDeclContext()->getParentMap();
  601. return !PM.isConsumedExpr(cast<Expr>(S));
  602. }
  603. void ExprEngine::removeDead(ExplodedNode *Pred, ExplodedNodeSet &Out,
  604. const Stmt *ReferenceStmt,
  605. const LocationContext *LC,
  606. const Stmt *DiagnosticStmt,
  607. ProgramPoint::Kind K) {
  608. assert((K == ProgramPoint::PreStmtPurgeDeadSymbolsKind ||
  609. ReferenceStmt == nullptr || isa<ReturnStmt>(ReferenceStmt))
  610. && "PostStmt is not generally supported by the SymbolReaper yet");
  611. assert(LC && "Must pass the current (or expiring) LocationContext");
  612. if (!DiagnosticStmt) {
  613. DiagnosticStmt = ReferenceStmt;
  614. assert(DiagnosticStmt && "Required for clearing a LocationContext");
  615. }
  616. NumRemoveDeadBindings++;
  617. ProgramStateRef CleanedState = Pred->getState();
  618. // LC is the location context being destroyed, but SymbolReaper wants a
  619. // location context that is still live. (If this is the top-level stack
  620. // frame, this will be null.)
  621. if (!ReferenceStmt) {
  622. assert(K == ProgramPoint::PostStmtPurgeDeadSymbolsKind &&
  623. "Use PostStmtPurgeDeadSymbolsKind for clearing a LocationContext");
  624. LC = LC->getParent();
  625. }
  626. const StackFrameContext *SFC = LC ? LC->getStackFrame() : nullptr;
  627. SymbolReaper SymReaper(SFC, ReferenceStmt, SymMgr, getStoreManager());
  628. for (auto I : CleanedState->get<ObjectsUnderConstruction>()) {
  629. if (SymbolRef Sym = I.second.getAsSymbol())
  630. SymReaper.markLive(Sym);
  631. if (const MemRegion *MR = I.second.getAsRegion())
  632. SymReaper.markLive(MR);
  633. }
  634. getCheckerManager().runCheckersForLiveSymbols(CleanedState, SymReaper);
  635. // Create a state in which dead bindings are removed from the environment
  636. // and the store. TODO: The function should just return new env and store,
  637. // not a new state.
  638. CleanedState = StateMgr.removeDeadBindings(CleanedState, SFC, SymReaper);
  639. // Process any special transfer function for dead symbols.
  640. // A tag to track convenience transitions, which can be removed at cleanup.
  641. static SimpleProgramPointTag cleanupTag(TagProviderName, "Clean Node");
  642. // Call checkers with the non-cleaned state so that they could query the
  643. // values of the soon to be dead symbols.
  644. ExplodedNodeSet CheckedSet;
  645. getCheckerManager().runCheckersForDeadSymbols(CheckedSet, Pred, SymReaper,
  646. DiagnosticStmt, *this, K);
  647. // For each node in CheckedSet, generate CleanedNodes that have the
  648. // environment, the store, and the constraints cleaned up but have the
  649. // user-supplied states as the predecessors.
  650. StmtNodeBuilder Bldr(CheckedSet, Out, *currBldrCtx);
  651. for (const auto I : CheckedSet) {
  652. ProgramStateRef CheckerState = I->getState();
  653. // The constraint manager has not been cleaned up yet, so clean up now.
  654. CheckerState =
  655. getConstraintManager().removeDeadBindings(CheckerState, SymReaper);
  656. assert(StateMgr.haveEqualEnvironments(CheckerState, Pred->getState()) &&
  657. "Checkers are not allowed to modify the Environment as a part of "
  658. "checkDeadSymbols processing.");
  659. assert(StateMgr.haveEqualStores(CheckerState, Pred->getState()) &&
  660. "Checkers are not allowed to modify the Store as a part of "
  661. "checkDeadSymbols processing.");
  662. // Create a state based on CleanedState with CheckerState GDM and
  663. // generate a transition to that state.
  664. ProgramStateRef CleanedCheckerSt =
  665. StateMgr.getPersistentStateWithGDM(CleanedState, CheckerState);
  666. Bldr.generateNode(DiagnosticStmt, I, CleanedCheckerSt, &cleanupTag, K);
  667. }
  668. }
  669. void ExprEngine::ProcessStmt(const Stmt *currStmt, ExplodedNode *Pred) {
  670. // Reclaim any unnecessary nodes in the ExplodedGraph.
  671. G.reclaimRecentlyAllocatedNodes();
  672. PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
  673. currStmt->getBeginLoc(),
  674. "Error evaluating statement");
  675. // Remove dead bindings and symbols.
  676. ExplodedNodeSet CleanedStates;
  677. if (shouldRemoveDeadBindings(AMgr, currStmt, Pred,
  678. Pred->getLocationContext())) {
  679. removeDead(Pred, CleanedStates, currStmt,
  680. Pred->getLocationContext());
  681. } else
  682. CleanedStates.Add(Pred);
  683. // Visit the statement.
  684. ExplodedNodeSet Dst;
  685. for (const auto I : CleanedStates) {
  686. ExplodedNodeSet DstI;
  687. // Visit the statement.
  688. Visit(currStmt, I, DstI);
  689. Dst.insert(DstI);
  690. }
  691. // Enqueue the new nodes onto the work list.
  692. Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
  693. }
  694. void ExprEngine::ProcessLoopExit(const Stmt* S, ExplodedNode *Pred) {
  695. PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
  696. S->getBeginLoc(),
  697. "Error evaluating end of the loop");
  698. ExplodedNodeSet Dst;
  699. Dst.Add(Pred);
  700. NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
  701. ProgramStateRef NewState = Pred->getState();
  702. if(AMgr.options.ShouldUnrollLoops)
  703. NewState = processLoopEnd(S, NewState);
  704. LoopExit PP(S, Pred->getLocationContext());
  705. Bldr.generateNode(PP, NewState, Pred);
  706. // Enqueue the new nodes onto the work list.
  707. Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
  708. }
  709. void ExprEngine::ProcessInitializer(const CFGInitializer CFGInit,
  710. ExplodedNode *Pred) {
  711. const CXXCtorInitializer *BMI = CFGInit.getInitializer();
  712. const Expr *Init = BMI->getInit()->IgnoreImplicit();
  713. const LocationContext *LC = Pred->getLocationContext();
  714. PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
  715. BMI->getSourceLocation(),
  716. "Error evaluating initializer");
  717. // We don't clean up dead bindings here.
  718. const auto *stackFrame = cast<StackFrameContext>(Pred->getLocationContext());
  719. const auto *decl = cast<CXXConstructorDecl>(stackFrame->getDecl());
  720. ProgramStateRef State = Pred->getState();
  721. SVal thisVal = State->getSVal(svalBuilder.getCXXThis(decl, stackFrame));
  722. ExplodedNodeSet Tmp;
  723. SVal FieldLoc;
  724. // Evaluate the initializer, if necessary
  725. if (BMI->isAnyMemberInitializer()) {
  726. // Constructors build the object directly in the field,
  727. // but non-objects must be copied in from the initializer.
  728. if (getObjectUnderConstruction(State, BMI, LC)) {
  729. // The field was directly constructed, so there is no need to bind.
  730. // But we still need to stop tracking the object under construction.
  731. State = finishObjectConstruction(State, BMI, LC);
  732. NodeBuilder Bldr(Pred, Tmp, *currBldrCtx);
  733. PostStore PS(Init, LC, /*Loc*/ nullptr, /*tag*/ nullptr);
  734. Bldr.generateNode(PS, State, Pred);
  735. } else {
  736. const ValueDecl *Field;
  737. if (BMI->isIndirectMemberInitializer()) {
  738. Field = BMI->getIndirectMember();
  739. FieldLoc = State->getLValue(BMI->getIndirectMember(), thisVal);
  740. } else {
  741. Field = BMI->getMember();
  742. FieldLoc = State->getLValue(BMI->getMember(), thisVal);
  743. }
  744. SVal InitVal;
  745. if (Init->getType()->isArrayType()) {
  746. // Handle arrays of trivial type. We can represent this with a
  747. // primitive load/copy from the base array region.
  748. const ArraySubscriptExpr *ASE;
  749. while ((ASE = dyn_cast<ArraySubscriptExpr>(Init)))
  750. Init = ASE->getBase()->IgnoreImplicit();
  751. SVal LValue = State->getSVal(Init, stackFrame);
  752. if (!Field->getType()->isReferenceType())
  753. if (Optional<Loc> LValueLoc = LValue.getAs<Loc>())
  754. InitVal = State->getSVal(*LValueLoc);
  755. // If we fail to get the value for some reason, use a symbolic value.
  756. if (InitVal.isUnknownOrUndef()) {
  757. SValBuilder &SVB = getSValBuilder();
  758. InitVal = SVB.conjureSymbolVal(BMI->getInit(), stackFrame,
  759. Field->getType(),
  760. currBldrCtx->blockCount());
  761. }
  762. } else {
  763. InitVal = State->getSVal(BMI->getInit(), stackFrame);
  764. }
  765. PostInitializer PP(BMI, FieldLoc.getAsRegion(), stackFrame);
  766. evalBind(Tmp, Init, Pred, FieldLoc, InitVal, /*isInit=*/true, &PP);
  767. }
  768. } else {
  769. assert(BMI->isBaseInitializer() || BMI->isDelegatingInitializer());
  770. Tmp.insert(Pred);
  771. // We already did all the work when visiting the CXXConstructExpr.
  772. }
  773. // Construct PostInitializer nodes whether the state changed or not,
  774. // so that the diagnostics don't get confused.
  775. PostInitializer PP(BMI, FieldLoc.getAsRegion(), stackFrame);
  776. ExplodedNodeSet Dst;
  777. NodeBuilder Bldr(Tmp, Dst, *currBldrCtx);
  778. for (const auto I : Tmp) {
  779. ProgramStateRef State = I->getState();
  780. Bldr.generateNode(PP, State, I);
  781. }
  782. // Enqueue the new nodes onto the work list.
  783. Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
  784. }
  785. void ExprEngine::ProcessImplicitDtor(const CFGImplicitDtor D,
  786. ExplodedNode *Pred) {
  787. ExplodedNodeSet Dst;
  788. switch (D.getKind()) {
  789. case CFGElement::AutomaticObjectDtor:
  790. ProcessAutomaticObjDtor(D.castAs<CFGAutomaticObjDtor>(), Pred, Dst);
  791. break;
  792. case CFGElement::BaseDtor:
  793. ProcessBaseDtor(D.castAs<CFGBaseDtor>(), Pred, Dst);
  794. break;
  795. case CFGElement::MemberDtor:
  796. ProcessMemberDtor(D.castAs<CFGMemberDtor>(), Pred, Dst);
  797. break;
  798. case CFGElement::TemporaryDtor:
  799. ProcessTemporaryDtor(D.castAs<CFGTemporaryDtor>(), Pred, Dst);
  800. break;
  801. case CFGElement::DeleteDtor:
  802. ProcessDeleteDtor(D.castAs<CFGDeleteDtor>(), Pred, Dst);
  803. break;
  804. default:
  805. llvm_unreachable("Unexpected dtor kind.");
  806. }
  807. // Enqueue the new nodes onto the work list.
  808. Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
  809. }
  810. void ExprEngine::ProcessNewAllocator(const CXXNewExpr *NE,
  811. ExplodedNode *Pred) {
  812. ExplodedNodeSet Dst;
  813. AnalysisManager &AMgr = getAnalysisManager();
  814. AnalyzerOptions &Opts = AMgr.options;
  815. // TODO: We're not evaluating allocators for all cases just yet as
  816. // we're not handling the return value correctly, which causes false
  817. // positives when the alpha.cplusplus.NewDeleteLeaks check is on.
  818. if (Opts.MayInlineCXXAllocator)
  819. VisitCXXNewAllocatorCall(NE, Pred, Dst);
  820. else {
  821. NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
  822. const LocationContext *LCtx = Pred->getLocationContext();
  823. PostImplicitCall PP(NE->getOperatorNew(), NE->getBeginLoc(), LCtx);
  824. Bldr.generateNode(PP, Pred->getState(), Pred);
  825. }
  826. Engine.enqueue(Dst, currBldrCtx->getBlock(), currStmtIdx);
  827. }
  828. void ExprEngine::ProcessAutomaticObjDtor(const CFGAutomaticObjDtor Dtor,
  829. ExplodedNode *Pred,
  830. ExplodedNodeSet &Dst) {
  831. const VarDecl *varDecl = Dtor.getVarDecl();
  832. QualType varType = varDecl->getType();
  833. ProgramStateRef state = Pred->getState();
  834. SVal dest = state->getLValue(varDecl, Pred->getLocationContext());
  835. const MemRegion *Region = dest.castAs<loc::MemRegionVal>().getRegion();
  836. if (varType->isReferenceType()) {
  837. const MemRegion *ValueRegion = state->getSVal(Region).getAsRegion();
  838. if (!ValueRegion) {
  839. // FIXME: This should not happen. The language guarantees a presence
  840. // of a valid initializer here, so the reference shall not be undefined.
  841. // It seems that we're calling destructors over variables that
  842. // were not initialized yet.
  843. return;
  844. }
  845. Region = ValueRegion->getBaseRegion();
  846. varType = cast<TypedValueRegion>(Region)->getValueType();
  847. }
  848. // FIXME: We need to run the same destructor on every element of the array.
  849. // This workaround will just run the first destructor (which will still
  850. // invalidate the entire array).
  851. EvalCallOptions CallOpts;
  852. Region = makeZeroElementRegion(state, loc::MemRegionVal(Region), varType,
  853. CallOpts.IsArrayCtorOrDtor).getAsRegion();
  854. VisitCXXDestructor(varType, Region, Dtor.getTriggerStmt(),
  855. /*IsBase=*/false, Pred, Dst, CallOpts);
  856. }
  857. void ExprEngine::ProcessDeleteDtor(const CFGDeleteDtor Dtor,
  858. ExplodedNode *Pred,
  859. ExplodedNodeSet &Dst) {
  860. ProgramStateRef State = Pred->getState();
  861. const LocationContext *LCtx = Pred->getLocationContext();
  862. const CXXDeleteExpr *DE = Dtor.getDeleteExpr();
  863. const Stmt *Arg = DE->getArgument();
  864. QualType DTy = DE->getDestroyedType();
  865. SVal ArgVal = State->getSVal(Arg, LCtx);
  866. // If the argument to delete is known to be a null value,
  867. // don't run destructor.
  868. if (State->isNull(ArgVal).isConstrainedTrue()) {
  869. QualType BTy = getContext().getBaseElementType(DTy);
  870. const CXXRecordDecl *RD = BTy->getAsCXXRecordDecl();
  871. const CXXDestructorDecl *Dtor = RD->getDestructor();
  872. PostImplicitCall PP(Dtor, DE->getBeginLoc(), LCtx);
  873. NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
  874. Bldr.generateNode(PP, Pred->getState(), Pred);
  875. return;
  876. }
  877. EvalCallOptions CallOpts;
  878. const MemRegion *ArgR = ArgVal.getAsRegion();
  879. if (DE->isArrayForm()) {
  880. // FIXME: We need to run the same destructor on every element of the array.
  881. // This workaround will just run the first destructor (which will still
  882. // invalidate the entire array).
  883. CallOpts.IsArrayCtorOrDtor = true;
  884. // Yes, it may even be a multi-dimensional array.
  885. while (const auto *AT = getContext().getAsArrayType(DTy))
  886. DTy = AT->getElementType();
  887. if (ArgR)
  888. ArgR = getStoreManager().GetElementZeroRegion(cast<SubRegion>(ArgR), DTy);
  889. }
  890. VisitCXXDestructor(DTy, ArgR, DE, /*IsBase=*/false, Pred, Dst, CallOpts);
  891. }
  892. void ExprEngine::ProcessBaseDtor(const CFGBaseDtor D,
  893. ExplodedNode *Pred, ExplodedNodeSet &Dst) {
  894. const LocationContext *LCtx = Pred->getLocationContext();
  895. const auto *CurDtor = cast<CXXDestructorDecl>(LCtx->getDecl());
  896. Loc ThisPtr = getSValBuilder().getCXXThis(CurDtor,
  897. LCtx->getStackFrame());
  898. SVal ThisVal = Pred->getState()->getSVal(ThisPtr);
  899. // Create the base object region.
  900. const CXXBaseSpecifier *Base = D.getBaseSpecifier();
  901. QualType BaseTy = Base->getType();
  902. SVal BaseVal = getStoreManager().evalDerivedToBase(ThisVal, BaseTy,
  903. Base->isVirtual());
  904. EvalCallOptions CallOpts;
  905. VisitCXXDestructor(BaseTy, BaseVal.getAsRegion(), CurDtor->getBody(),
  906. /*IsBase=*/true, Pred, Dst, CallOpts);
  907. }
  908. void ExprEngine::ProcessMemberDtor(const CFGMemberDtor D,
  909. ExplodedNode *Pred, ExplodedNodeSet &Dst) {
  910. const FieldDecl *Member = D.getFieldDecl();
  911. QualType T = Member->getType();
  912. ProgramStateRef State = Pred->getState();
  913. const LocationContext *LCtx = Pred->getLocationContext();
  914. const auto *CurDtor = cast<CXXDestructorDecl>(LCtx->getDecl());
  915. Loc ThisStorageLoc =
  916. getSValBuilder().getCXXThis(CurDtor, LCtx->getStackFrame());
  917. Loc ThisLoc = State->getSVal(ThisStorageLoc).castAs<Loc>();
  918. SVal FieldVal = State->getLValue(Member, ThisLoc);
  919. // FIXME: We need to run the same destructor on every element of the array.
  920. // This workaround will just run the first destructor (which will still
  921. // invalidate the entire array).
  922. EvalCallOptions CallOpts;
  923. FieldVal = makeZeroElementRegion(State, FieldVal, T,
  924. CallOpts.IsArrayCtorOrDtor);
  925. VisitCXXDestructor(T, FieldVal.getAsRegion(), CurDtor->getBody(),
  926. /*IsBase=*/false, Pred, Dst, CallOpts);
  927. }
  928. void ExprEngine::ProcessTemporaryDtor(const CFGTemporaryDtor D,
  929. ExplodedNode *Pred,
  930. ExplodedNodeSet &Dst) {
  931. const CXXBindTemporaryExpr *BTE = D.getBindTemporaryExpr();
  932. ProgramStateRef State = Pred->getState();
  933. const LocationContext *LC = Pred->getLocationContext();
  934. const MemRegion *MR = nullptr;
  935. if (Optional<SVal> V =
  936. getObjectUnderConstruction(State, D.getBindTemporaryExpr(),
  937. Pred->getLocationContext())) {
  938. // FIXME: Currently we insert temporary destructors for default parameters,
  939. // but we don't insert the constructors, so the entry in
  940. // ObjectsUnderConstruction may be missing.
  941. State = finishObjectConstruction(State, D.getBindTemporaryExpr(),
  942. Pred->getLocationContext());
  943. MR = V->getAsRegion();
  944. }
  945. // If copy elision has occurred, and the constructor corresponding to the
  946. // destructor was elided, we need to skip the destructor as well.
  947. if (isDestructorElided(State, BTE, LC)) {
  948. State = cleanupElidedDestructor(State, BTE, LC);
  949. NodeBuilder Bldr(Pred, Dst, *currBldrCtx);
  950. PostImplicitCall PP(D.getDestructorDecl(getContext()),
  951. D.getBindTemporaryExpr()->getBeginLoc(),
  952. Pred->getLocationContext());
  953. Bldr.generateNode(PP, State, Pred);
  954. return;
  955. }
  956. ExplodedNodeSet CleanDtorState;
  957. StmtNodeBuilder StmtBldr(Pred, CleanDtorState, *currBldrCtx);
  958. StmtBldr.generateNode(D.getBindTemporaryExpr(), Pred, State);
  959. QualType T = D.getBindTemporaryExpr()->getSubExpr()->getType();
  960. // FIXME: Currently CleanDtorState can be empty here due to temporaries being
  961. // bound to default parameters.
  962. assert(CleanDtorState.size() <= 1);
  963. ExplodedNode *CleanPred =
  964. CleanDtorState.empty() ? Pred : *CleanDtorState.begin();
  965. EvalCallOptions CallOpts;
  966. CallOpts.IsTemporaryCtorOrDtor = true;
  967. if (!MR) {
  968. // If we have no MR, we still need to unwrap the array to avoid destroying
  969. // the whole array at once. Regardless, we'd eventually need to model array
  970. // destructors properly, element-by-element.
  971. while (const ArrayType *AT = getContext().getAsArrayType(T)) {
  972. T = AT->getElementType();
  973. CallOpts.IsArrayCtorOrDtor = true;
  974. }
  975. } else {
  976. // We'd eventually need to makeZeroElementRegion() trick here,
  977. // but for now we don't have the respective construction contexts,
  978. // so MR would always be null in this case. Do nothing for now.
  979. }
  980. VisitCXXDestructor(T, MR, D.getBindTemporaryExpr(),
  981. /*IsBase=*/false, CleanPred, Dst, CallOpts);
  982. }
  983. void ExprEngine::processCleanupTemporaryBranch(const CXXBindTemporaryExpr *BTE,
  984. NodeBuilderContext &BldCtx,
  985. ExplodedNode *Pred,
  986. ExplodedNodeSet &Dst,
  987. const CFGBlock *DstT,
  988. const CFGBlock *DstF) {
  989. BranchNodeBuilder TempDtorBuilder(Pred, Dst, BldCtx, DstT, DstF);
  990. ProgramStateRef State = Pred->getState();
  991. const LocationContext *LC = Pred->getLocationContext();
  992. if (getObjectUnderConstruction(State, BTE, LC)) {
  993. TempDtorBuilder.markInfeasible(false);
  994. TempDtorBuilder.generateNode(State, true, Pred);
  995. } else {
  996. TempDtorBuilder.markInfeasible(true);
  997. TempDtorBuilder.generateNode(State, false, Pred);
  998. }
  999. }
  1000. void ExprEngine::VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *BTE,
  1001. ExplodedNodeSet &PreVisit,
  1002. ExplodedNodeSet &Dst) {
  1003. // This is a fallback solution in case we didn't have a construction
  1004. // context when we were constructing the temporary. Otherwise the map should
  1005. // have been populated there.
  1006. if (!getAnalysisManager().options.ShouldIncludeTemporaryDtorsInCFG) {
  1007. // In case we don't have temporary destructors in the CFG, do not mark
  1008. // the initialization - we would otherwise never clean it up.
  1009. Dst = PreVisit;
  1010. return;
  1011. }
  1012. StmtNodeBuilder StmtBldr(PreVisit, Dst, *currBldrCtx);
  1013. for (ExplodedNode *Node : PreVisit) {
  1014. ProgramStateRef State = Node->getState();
  1015. const LocationContext *LC = Node->getLocationContext();
  1016. if (!getObjectUnderConstruction(State, BTE, LC)) {
  1017. // FIXME: Currently the state might also already contain the marker due to
  1018. // incorrect handling of temporaries bound to default parameters; for
  1019. // those, we currently skip the CXXBindTemporaryExpr but rely on adding
  1020. // temporary destructor nodes.
  1021. State = addObjectUnderConstruction(State, BTE, LC, UnknownVal());
  1022. }
  1023. StmtBldr.generateNode(BTE, Node, State);
  1024. }
  1025. }
  1026. ProgramStateRef ExprEngine::escapeValue(ProgramStateRef State, SVal V,
  1027. PointerEscapeKind K) const {
  1028. class CollectReachableSymbolsCallback final : public SymbolVisitor {
  1029. InvalidatedSymbols Symbols;
  1030. public:
  1031. explicit CollectReachableSymbolsCallback(ProgramStateRef) {}
  1032. const InvalidatedSymbols &getSymbols() const { return Symbols; }
  1033. bool VisitSymbol(SymbolRef Sym) override {
  1034. Symbols.insert(Sym);
  1035. return true;
  1036. }
  1037. };
  1038. const CollectReachableSymbolsCallback &Scanner =
  1039. State->scanReachableSymbols<CollectReachableSymbolsCallback>(V);
  1040. return getCheckerManager().runCheckersForPointerEscape(
  1041. State, Scanner.getSymbols(), /*CallEvent*/ nullptr, K, nullptr);
  1042. }
  1043. void ExprEngine::Visit(const Stmt *S, ExplodedNode *Pred,
  1044. ExplodedNodeSet &DstTop) {
  1045. PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
  1046. S->getBeginLoc(), "Error evaluating statement");
  1047. ExplodedNodeSet Dst;
  1048. StmtNodeBuilder Bldr(Pred, DstTop, *currBldrCtx);
  1049. assert(!isa<Expr>(S) || S == cast<Expr>(S)->IgnoreParens());
  1050. switch (S->getStmtClass()) {
  1051. // C++, OpenMP and ARC stuff we don't support yet.
  1052. case Expr::ObjCIndirectCopyRestoreExprClass:
  1053. case Stmt::CXXDependentScopeMemberExprClass:
  1054. case Stmt::CXXInheritedCtorInitExprClass:
  1055. case Stmt::CXXTryStmtClass:
  1056. case Stmt::CXXTypeidExprClass:
  1057. case Stmt::CXXUuidofExprClass:
  1058. case Stmt::CXXFoldExprClass:
  1059. case Stmt::MSPropertyRefExprClass:
  1060. case Stmt::MSPropertySubscriptExprClass:
  1061. case Stmt::CXXUnresolvedConstructExprClass:
  1062. case Stmt::DependentScopeDeclRefExprClass:
  1063. case Stmt::ArrayTypeTraitExprClass:
  1064. case Stmt::ExpressionTraitExprClass:
  1065. case Stmt::UnresolvedLookupExprClass:
  1066. case Stmt::UnresolvedMemberExprClass:
  1067. case Stmt::TypoExprClass:
  1068. case Stmt::CXXNoexceptExprClass:
  1069. case Stmt::PackExpansionExprClass:
  1070. case Stmt::SubstNonTypeTemplateParmPackExprClass:
  1071. case Stmt::FunctionParmPackExprClass:
  1072. case Stmt::CoroutineBodyStmtClass:
  1073. case Stmt::CoawaitExprClass:
  1074. case Stmt::DependentCoawaitExprClass:
  1075. case Stmt::CoreturnStmtClass:
  1076. case Stmt::CoyieldExprClass:
  1077. case Stmt::SEHTryStmtClass:
  1078. case Stmt::SEHExceptStmtClass:
  1079. case Stmt::SEHLeaveStmtClass:
  1080. case Stmt::SEHFinallyStmtClass:
  1081. case Stmt::OMPParallelDirectiveClass:
  1082. case Stmt::OMPSimdDirectiveClass:
  1083. case Stmt::OMPForDirectiveClass:
  1084. case Stmt::OMPForSimdDirectiveClass:
  1085. case Stmt::OMPSectionsDirectiveClass:
  1086. case Stmt::OMPSectionDirectiveClass:
  1087. case Stmt::OMPSingleDirectiveClass:
  1088. case Stmt::OMPMasterDirectiveClass:
  1089. case Stmt::OMPCriticalDirectiveClass:
  1090. case Stmt::OMPParallelForDirectiveClass:
  1091. case Stmt::OMPParallelForSimdDirectiveClass:
  1092. case Stmt::OMPParallelSectionsDirectiveClass:
  1093. case Stmt::OMPTaskDirectiveClass:
  1094. case Stmt::OMPTaskyieldDirectiveClass:
  1095. case Stmt::OMPBarrierDirectiveClass:
  1096. case Stmt::OMPTaskwaitDirectiveClass:
  1097. case Stmt::OMPTaskgroupDirectiveClass:
  1098. case Stmt::OMPFlushDirectiveClass:
  1099. case Stmt::OMPOrderedDirectiveClass:
  1100. case Stmt::OMPAtomicDirectiveClass:
  1101. case Stmt::OMPTargetDirectiveClass:
  1102. case Stmt::OMPTargetDataDirectiveClass:
  1103. case Stmt::OMPTargetEnterDataDirectiveClass:
  1104. case Stmt::OMPTargetExitDataDirectiveClass:
  1105. case Stmt::OMPTargetParallelDirectiveClass:
  1106. case Stmt::OMPTargetParallelForDirectiveClass:
  1107. case Stmt::OMPTargetUpdateDirectiveClass:
  1108. case Stmt::OMPTeamsDirectiveClass:
  1109. case Stmt::OMPCancellationPointDirectiveClass:
  1110. case Stmt::OMPCancelDirectiveClass:
  1111. case Stmt::OMPTaskLoopDirectiveClass:
  1112. case Stmt::OMPTaskLoopSimdDirectiveClass:
  1113. case Stmt::OMPMasterTaskLoopDirectiveClass:
  1114. case Stmt::OMPMasterTaskLoopSimdDirectiveClass:
  1115. case Stmt::OMPParallelMasterTaskLoopDirectiveClass:
  1116. case Stmt::OMPDistributeDirectiveClass:
  1117. case Stmt::OMPDistributeParallelForDirectiveClass:
  1118. case Stmt::OMPDistributeParallelForSimdDirectiveClass:
  1119. case Stmt::OMPDistributeSimdDirectiveClass:
  1120. case Stmt::OMPTargetParallelForSimdDirectiveClass:
  1121. case Stmt::OMPTargetSimdDirectiveClass:
  1122. case Stmt::OMPTeamsDistributeDirectiveClass:
  1123. case Stmt::OMPTeamsDistributeSimdDirectiveClass:
  1124. case Stmt::OMPTeamsDistributeParallelForSimdDirectiveClass:
  1125. case Stmt::OMPTeamsDistributeParallelForDirectiveClass:
  1126. case Stmt::OMPTargetTeamsDirectiveClass:
  1127. case Stmt::OMPTargetTeamsDistributeDirectiveClass:
  1128. case Stmt::OMPTargetTeamsDistributeParallelForDirectiveClass:
  1129. case Stmt::OMPTargetTeamsDistributeParallelForSimdDirectiveClass:
  1130. case Stmt::OMPTargetTeamsDistributeSimdDirectiveClass:
  1131. case Stmt::CapturedStmtClass: {
  1132. const ExplodedNode *node = Bldr.generateSink(S, Pred, Pred->getState());
  1133. Engine.addAbortedBlock(node, currBldrCtx->getBlock());
  1134. break;
  1135. }
  1136. case Stmt::ParenExprClass:
  1137. llvm_unreachable("ParenExprs already handled.");
  1138. case Stmt::GenericSelectionExprClass:
  1139. llvm_unreachable("GenericSelectionExprs already handled.");
  1140. // Cases that should never be evaluated simply because they shouldn't
  1141. // appear in the CFG.
  1142. case Stmt::BreakStmtClass:
  1143. case Stmt::CaseStmtClass:
  1144. case Stmt::CompoundStmtClass:
  1145. case Stmt::ContinueStmtClass:
  1146. case Stmt::CXXForRangeStmtClass:
  1147. case Stmt::DefaultStmtClass:
  1148. case Stmt::DoStmtClass:
  1149. case Stmt::ForStmtClass:
  1150. case Stmt::GotoStmtClass:
  1151. case Stmt::IfStmtClass:
  1152. case Stmt::IndirectGotoStmtClass:
  1153. case Stmt::LabelStmtClass:
  1154. case Stmt::NoStmtClass:
  1155. case Stmt::NullStmtClass:
  1156. case Stmt::SwitchStmtClass:
  1157. case Stmt::WhileStmtClass:
  1158. case Expr::MSDependentExistsStmtClass:
  1159. llvm_unreachable("Stmt should not be in analyzer evaluation loop");
  1160. case Stmt::ObjCSubscriptRefExprClass:
  1161. case Stmt::ObjCPropertyRefExprClass:
  1162. llvm_unreachable("These are handled by PseudoObjectExpr");
  1163. case Stmt::GNUNullExprClass: {
  1164. // GNU __null is a pointer-width integer, not an actual pointer.
  1165. ProgramStateRef state = Pred->getState();
  1166. state = state->BindExpr(S, Pred->getLocationContext(),
  1167. svalBuilder.makeIntValWithPtrWidth(0, false));
  1168. Bldr.generateNode(S, Pred, state);
  1169. break;
  1170. }
  1171. case Stmt::ObjCAtSynchronizedStmtClass:
  1172. Bldr.takeNodes(Pred);
  1173. VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S), Pred, Dst);
  1174. Bldr.addNodes(Dst);
  1175. break;
  1176. case Expr::ConstantExprClass:
  1177. case Stmt::ExprWithCleanupsClass:
  1178. // Handled due to fully linearised CFG.
  1179. break;
  1180. case Stmt::CXXBindTemporaryExprClass: {
  1181. Bldr.takeNodes(Pred);
  1182. ExplodedNodeSet PreVisit;
  1183. getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
  1184. ExplodedNodeSet Next;
  1185. VisitCXXBindTemporaryExpr(cast<CXXBindTemporaryExpr>(S), PreVisit, Next);
  1186. getCheckerManager().runCheckersForPostStmt(Dst, Next, S, *this);
  1187. Bldr.addNodes(Dst);
  1188. break;
  1189. }
  1190. // Cases not handled yet; but will handle some day.
  1191. case Stmt::DesignatedInitExprClass:
  1192. case Stmt::DesignatedInitUpdateExprClass:
  1193. case Stmt::ArrayInitLoopExprClass:
  1194. case Stmt::ArrayInitIndexExprClass:
  1195. case Stmt::ExtVectorElementExprClass:
  1196. case Stmt::ImaginaryLiteralClass:
  1197. case Stmt::ObjCAtCatchStmtClass:
  1198. case Stmt::ObjCAtFinallyStmtClass:
  1199. case Stmt::ObjCAtTryStmtClass:
  1200. case Stmt::ObjCAutoreleasePoolStmtClass:
  1201. case Stmt::ObjCEncodeExprClass:
  1202. case Stmt::ObjCIsaExprClass:
  1203. case Stmt::ObjCProtocolExprClass:
  1204. case Stmt::ObjCSelectorExprClass:
  1205. case Stmt::ParenListExprClass:
  1206. case Stmt::ShuffleVectorExprClass:
  1207. case Stmt::ConvertVectorExprClass:
  1208. case Stmt::VAArgExprClass:
  1209. case Stmt::CUDAKernelCallExprClass:
  1210. case Stmt::OpaqueValueExprClass:
  1211. case Stmt::AsTypeExprClass:
  1212. case Stmt::ConceptSpecializationExprClass:
  1213. case Stmt::CXXRewrittenBinaryOperatorClass:
  1214. // Fall through.
  1215. // Cases we intentionally don't evaluate, since they don't need
  1216. // to be explicitly evaluated.
  1217. case Stmt::PredefinedExprClass:
  1218. case Stmt::AddrLabelExprClass:
  1219. case Stmt::AttributedStmtClass:
  1220. case Stmt::IntegerLiteralClass:
  1221. case Stmt::FixedPointLiteralClass:
  1222. case Stmt::CharacterLiteralClass:
  1223. case Stmt::ImplicitValueInitExprClass:
  1224. case Stmt::CXXScalarValueInitExprClass:
  1225. case Stmt::CXXBoolLiteralExprClass:
  1226. case Stmt::ObjCBoolLiteralExprClass:
  1227. case Stmt::ObjCAvailabilityCheckExprClass:
  1228. case Stmt::FloatingLiteralClass:
  1229. case Stmt::NoInitExprClass:
  1230. case Stmt::SizeOfPackExprClass:
  1231. case Stmt::StringLiteralClass:
  1232. case Stmt::SourceLocExprClass:
  1233. case Stmt::ObjCStringLiteralClass:
  1234. case Stmt::CXXPseudoDestructorExprClass:
  1235. case Stmt::SubstNonTypeTemplateParmExprClass:
  1236. case Stmt::CXXNullPtrLiteralExprClass:
  1237. case Stmt::OMPArraySectionExprClass:
  1238. case Stmt::TypeTraitExprClass: {
  1239. Bldr.takeNodes(Pred);
  1240. ExplodedNodeSet preVisit;
  1241. getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this);
  1242. getCheckerManager().runCheckersForPostStmt(Dst, preVisit, S, *this);
  1243. Bldr.addNodes(Dst);
  1244. break;
  1245. }
  1246. case Stmt::CXXDefaultArgExprClass:
  1247. case Stmt::CXXDefaultInitExprClass: {
  1248. Bldr.takeNodes(Pred);
  1249. ExplodedNodeSet PreVisit;
  1250. getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
  1251. ExplodedNodeSet Tmp;
  1252. StmtNodeBuilder Bldr2(PreVisit, Tmp, *currBldrCtx);
  1253. const Expr *ArgE;
  1254. if (const auto *DefE = dyn_cast<CXXDefaultArgExpr>(S))
  1255. ArgE = DefE->getExpr();
  1256. else if (const auto *DefE = dyn_cast<CXXDefaultInitExpr>(S))
  1257. ArgE = DefE->getExpr();
  1258. else
  1259. llvm_unreachable("unknown constant wrapper kind");
  1260. bool IsTemporary = false;
  1261. if (const auto *MTE = dyn_cast<MaterializeTemporaryExpr>(ArgE)) {
  1262. ArgE = MTE->GetTemporaryExpr();
  1263. IsTemporary = true;
  1264. }
  1265. Optional<SVal> ConstantVal = svalBuilder.getConstantVal(ArgE);
  1266. if (!ConstantVal)
  1267. ConstantVal = UnknownVal();
  1268. const LocationContext *LCtx = Pred->getLocationContext();
  1269. for (const auto I : PreVisit) {
  1270. ProgramStateRef State = I->getState();
  1271. State = State->BindExpr(S, LCtx, *ConstantVal);
  1272. if (IsTemporary)
  1273. State = createTemporaryRegionIfNeeded(State, LCtx,
  1274. cast<Expr>(S),
  1275. cast<Expr>(S));
  1276. Bldr2.generateNode(S, I, State);
  1277. }
  1278. getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this);
  1279. Bldr.addNodes(Dst);
  1280. break;
  1281. }
  1282. // Cases we evaluate as opaque expressions, conjuring a symbol.
  1283. case Stmt::CXXStdInitializerListExprClass:
  1284. case Expr::ObjCArrayLiteralClass:
  1285. case Expr::ObjCDictionaryLiteralClass:
  1286. case Expr::ObjCBoxedExprClass: {
  1287. Bldr.takeNodes(Pred);
  1288. ExplodedNodeSet preVisit;
  1289. getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this);
  1290. ExplodedNodeSet Tmp;
  1291. StmtNodeBuilder Bldr2(preVisit, Tmp, *currBldrCtx);
  1292. const auto *Ex = cast<Expr>(S);
  1293. QualType resultType = Ex->getType();
  1294. for (const auto N : preVisit) {
  1295. const LocationContext *LCtx = N->getLocationContext();
  1296. SVal result = svalBuilder.conjureSymbolVal(nullptr, Ex, LCtx,
  1297. resultType,
  1298. currBldrCtx->blockCount());
  1299. ProgramStateRef State = N->getState()->BindExpr(Ex, LCtx, result);
  1300. // Escape pointers passed into the list, unless it's an ObjC boxed
  1301. // expression which is not a boxable C structure.
  1302. if (!(isa<ObjCBoxedExpr>(Ex) &&
  1303. !cast<ObjCBoxedExpr>(Ex)->getSubExpr()
  1304. ->getType()->isRecordType()))
  1305. for (auto Child : Ex->children()) {
  1306. assert(Child);
  1307. SVal Val = State->getSVal(Child, LCtx);
  1308. State = escapeValue(State, Val, PSK_EscapeOther);
  1309. }
  1310. Bldr2.generateNode(S, N, State);
  1311. }
  1312. getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this);
  1313. Bldr.addNodes(Dst);
  1314. break;
  1315. }
  1316. case Stmt::ArraySubscriptExprClass:
  1317. Bldr.takeNodes(Pred);
  1318. VisitArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Pred, Dst);
  1319. Bldr.addNodes(Dst);
  1320. break;
  1321. case Stmt::GCCAsmStmtClass:
  1322. Bldr.takeNodes(Pred);
  1323. VisitGCCAsmStmt(cast<GCCAsmStmt>(S), Pred, Dst);
  1324. Bldr.addNodes(Dst);
  1325. break;
  1326. case Stmt::MSAsmStmtClass:
  1327. Bldr.takeNodes(Pred);
  1328. VisitMSAsmStmt(cast<MSAsmStmt>(S), Pred, Dst);
  1329. Bldr.addNodes(Dst);
  1330. break;
  1331. case Stmt::BlockExprClass:
  1332. Bldr.takeNodes(Pred);
  1333. VisitBlockExpr(cast<BlockExpr>(S), Pred, Dst);
  1334. Bldr.addNodes(Dst);
  1335. break;
  1336. case Stmt::LambdaExprClass:
  1337. if (AMgr.options.ShouldInlineLambdas) {
  1338. Bldr.takeNodes(Pred);
  1339. VisitLambdaExpr(cast<LambdaExpr>(S), Pred, Dst);
  1340. Bldr.addNodes(Dst);
  1341. } else {
  1342. const ExplodedNode *node = Bldr.generateSink(S, Pred, Pred->getState());
  1343. Engine.addAbortedBlock(node, currBldrCtx->getBlock());
  1344. }
  1345. break;
  1346. case Stmt::BinaryOperatorClass: {
  1347. const auto *B = cast<BinaryOperator>(S);
  1348. if (B->isLogicalOp()) {
  1349. Bldr.takeNodes(Pred);
  1350. VisitLogicalExpr(B, Pred, Dst);
  1351. Bldr.addNodes(Dst);
  1352. break;
  1353. }
  1354. else if (B->getOpcode() == BO_Comma) {
  1355. ProgramStateRef state = Pred->getState();
  1356. Bldr.generateNode(B, Pred,
  1357. state->BindExpr(B, Pred->getLocationContext(),
  1358. state->getSVal(B->getRHS(),
  1359. Pred->getLocationContext())));
  1360. break;
  1361. }
  1362. Bldr.takeNodes(Pred);
  1363. if (AMgr.options.ShouldEagerlyAssume &&
  1364. (B->isRelationalOp() || B->isEqualityOp())) {
  1365. ExplodedNodeSet Tmp;
  1366. VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Tmp);
  1367. evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, cast<Expr>(S));
  1368. }
  1369. else
  1370. VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
  1371. Bldr.addNodes(Dst);
  1372. break;
  1373. }
  1374. case Stmt::CXXOperatorCallExprClass: {
  1375. const auto *OCE = cast<CXXOperatorCallExpr>(S);
  1376. // For instance method operators, make sure the 'this' argument has a
  1377. // valid region.
  1378. const Decl *Callee = OCE->getCalleeDecl();
  1379. if (const auto *MD = dyn_cast_or_null<CXXMethodDecl>(Callee)) {
  1380. if (MD->isInstance()) {
  1381. ProgramStateRef State = Pred->getState();
  1382. const LocationContext *LCtx = Pred->getLocationContext();
  1383. ProgramStateRef NewState =
  1384. createTemporaryRegionIfNeeded(State, LCtx, OCE->getArg(0));
  1385. if (NewState != State) {
  1386. Pred = Bldr.generateNode(OCE, Pred, NewState, /*tag=*/nullptr,
  1387. ProgramPoint::PreStmtKind);
  1388. // Did we cache out?
  1389. if (!Pred)
  1390. break;
  1391. }
  1392. }
  1393. }
  1394. // FALLTHROUGH
  1395. LLVM_FALLTHROUGH;
  1396. }
  1397. case Stmt::CallExprClass:
  1398. case Stmt::CXXMemberCallExprClass:
  1399. case Stmt::UserDefinedLiteralClass:
  1400. Bldr.takeNodes(Pred);
  1401. VisitCallExpr(cast<CallExpr>(S), Pred, Dst);
  1402. Bldr.addNodes(Dst);
  1403. break;
  1404. case Stmt::CXXCatchStmtClass:
  1405. Bldr.takeNodes(Pred);
  1406. VisitCXXCatchStmt(cast<CXXCatchStmt>(S), Pred, Dst);
  1407. Bldr.addNodes(Dst);
  1408. break;
  1409. case Stmt::CXXTemporaryObjectExprClass:
  1410. case Stmt::CXXConstructExprClass:
  1411. Bldr.takeNodes(Pred);
  1412. VisitCXXConstructExpr(cast<CXXConstructExpr>(S), Pred, Dst);
  1413. Bldr.addNodes(Dst);
  1414. break;
  1415. case Stmt::CXXNewExprClass: {
  1416. Bldr.takeNodes(Pred);
  1417. ExplodedNodeSet PreVisit;
  1418. getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
  1419. ExplodedNodeSet PostVisit;
  1420. for (const auto i : PreVisit)
  1421. VisitCXXNewExpr(cast<CXXNewExpr>(S), i, PostVisit);
  1422. getCheckerManager().runCheckersForPostStmt(Dst, PostVisit, S, *this);
  1423. Bldr.addNodes(Dst);
  1424. break;
  1425. }
  1426. case Stmt::CXXDeleteExprClass: {
  1427. Bldr.takeNodes(Pred);
  1428. ExplodedNodeSet PreVisit;
  1429. const auto *CDE = cast<CXXDeleteExpr>(S);
  1430. getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
  1431. for (const auto i : PreVisit)
  1432. VisitCXXDeleteExpr(CDE, i, Dst);
  1433. Bldr.addNodes(Dst);
  1434. break;
  1435. }
  1436. // FIXME: ChooseExpr is really a constant. We need to fix
  1437. // the CFG do not model them as explicit control-flow.
  1438. case Stmt::ChooseExprClass: { // __builtin_choose_expr
  1439. Bldr.takeNodes(Pred);
  1440. const auto *C = cast<ChooseExpr>(S);
  1441. VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst);
  1442. Bldr.addNodes(Dst);
  1443. break;
  1444. }
  1445. case Stmt::CompoundAssignOperatorClass:
  1446. Bldr.takeNodes(Pred);
  1447. VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
  1448. Bldr.addNodes(Dst);
  1449. break;
  1450. case Stmt::CompoundLiteralExprClass:
  1451. Bldr.takeNodes(Pred);
  1452. VisitCompoundLiteralExpr(cast<CompoundLiteralExpr>(S), Pred, Dst);
  1453. Bldr.addNodes(Dst);
  1454. break;
  1455. case Stmt::BinaryConditionalOperatorClass:
  1456. case Stmt::ConditionalOperatorClass: { // '?' operator
  1457. Bldr.takeNodes(Pred);
  1458. const auto *C = cast<AbstractConditionalOperator>(S);
  1459. VisitGuardedExpr(C, C->getTrueExpr(), C->getFalseExpr(), Pred, Dst);
  1460. Bldr.addNodes(Dst);
  1461. break;
  1462. }
  1463. case Stmt::CXXThisExprClass:
  1464. Bldr.takeNodes(Pred);
  1465. VisitCXXThisExpr(cast<CXXThisExpr>(S), Pred, Dst);
  1466. Bldr.addNodes(Dst);
  1467. break;
  1468. case Stmt::DeclRefExprClass: {
  1469. Bldr.takeNodes(Pred);
  1470. const auto *DE = cast<DeclRefExpr>(S);
  1471. VisitCommonDeclRefExpr(DE, DE->getDecl(), Pred, Dst);
  1472. Bldr.addNodes(Dst);
  1473. break;
  1474. }
  1475. case Stmt::DeclStmtClass:
  1476. Bldr.takeNodes(Pred);
  1477. VisitDeclStmt(cast<DeclStmt>(S), Pred, Dst);
  1478. Bldr.addNodes(Dst);
  1479. break;
  1480. case Stmt::ImplicitCastExprClass:
  1481. case Stmt::CStyleCastExprClass:
  1482. case Stmt::CXXStaticCastExprClass:
  1483. case Stmt::CXXDynamicCastExprClass:
  1484. case Stmt::CXXReinterpretCastExprClass:
  1485. case Stmt::CXXConstCastExprClass:
  1486. case Stmt::CXXFunctionalCastExprClass:
  1487. case Stmt::BuiltinBitCastExprClass:
  1488. case Stmt::ObjCBridgedCastExprClass: {
  1489. Bldr.takeNodes(Pred);
  1490. const auto *C = cast<CastExpr>(S);
  1491. ExplodedNodeSet dstExpr;
  1492. VisitCast(C, C->getSubExpr(), Pred, dstExpr);
  1493. // Handle the postvisit checks.
  1494. getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, C, *this);
  1495. Bldr.addNodes(Dst);
  1496. break;
  1497. }
  1498. case Expr::MaterializeTemporaryExprClass: {
  1499. Bldr.takeNodes(Pred);
  1500. const auto *MTE = cast<MaterializeTemporaryExpr>(S);
  1501. ExplodedNodeSet dstPrevisit;
  1502. getCheckerManager().runCheckersForPreStmt(dstPrevisit, Pred, MTE, *this);
  1503. ExplodedNodeSet dstExpr;
  1504. for (const auto i : dstPrevisit)
  1505. CreateCXXTemporaryObject(MTE, i, dstExpr);
  1506. getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, MTE, *this);
  1507. Bldr.addNodes(Dst);
  1508. break;
  1509. }
  1510. case Stmt::InitListExprClass:
  1511. Bldr.takeNodes(Pred);
  1512. VisitInitListExpr(cast<InitListExpr>(S), Pred, Dst);
  1513. Bldr.addNodes(Dst);
  1514. break;
  1515. case Stmt::MemberExprClass:
  1516. Bldr.takeNodes(Pred);
  1517. VisitMemberExpr(cast<MemberExpr>(S), Pred, Dst);
  1518. Bldr.addNodes(Dst);
  1519. break;
  1520. case Stmt::AtomicExprClass:
  1521. Bldr.takeNodes(Pred);
  1522. VisitAtomicExpr(cast<AtomicExpr>(S), Pred, Dst);
  1523. Bldr.addNodes(Dst);
  1524. break;
  1525. case Stmt::ObjCIvarRefExprClass:
  1526. Bldr.takeNodes(Pred);
  1527. VisitLvalObjCIvarRefExpr(cast<ObjCIvarRefExpr>(S), Pred, Dst);
  1528. Bldr.addNodes(Dst);
  1529. break;
  1530. case Stmt::ObjCForCollectionStmtClass:
  1531. Bldr.takeNodes(Pred);
  1532. VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S), Pred, Dst);
  1533. Bldr.addNodes(Dst);
  1534. break;
  1535. case Stmt::ObjCMessageExprClass:
  1536. Bldr.takeNodes(Pred);
  1537. VisitObjCMessage(cast<ObjCMessageExpr>(S), Pred, Dst);
  1538. Bldr.addNodes(Dst);
  1539. break;
  1540. case Stmt::ObjCAtThrowStmtClass:
  1541. case Stmt::CXXThrowExprClass:
  1542. // FIXME: This is not complete. We basically treat @throw as
  1543. // an abort.
  1544. Bldr.generateSink(S, Pred, Pred->getState());
  1545. break;
  1546. case Stmt::ReturnStmtClass:
  1547. Bldr.takeNodes(Pred);
  1548. VisitReturnStmt(cast<ReturnStmt>(S), Pred, Dst);
  1549. Bldr.addNodes(Dst);
  1550. break;
  1551. case Stmt::OffsetOfExprClass: {
  1552. Bldr.takeNodes(Pred);
  1553. ExplodedNodeSet PreVisit;
  1554. getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
  1555. ExplodedNodeSet PostVisit;
  1556. for (const auto Node : PreVisit)
  1557. VisitOffsetOfExpr(cast<OffsetOfExpr>(S), Node, PostVisit);
  1558. getCheckerManager().runCheckersForPostStmt(Dst, PostVisit, S, *this);
  1559. Bldr.addNodes(Dst);
  1560. break;
  1561. }
  1562. case Stmt::UnaryExprOrTypeTraitExprClass:
  1563. Bldr.takeNodes(Pred);
  1564. VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S),
  1565. Pred, Dst);
  1566. Bldr.addNodes(Dst);
  1567. break;
  1568. case Stmt::StmtExprClass: {
  1569. const auto *SE = cast<StmtExpr>(S);
  1570. if (SE->getSubStmt()->body_empty()) {
  1571. // Empty statement expression.
  1572. assert(SE->getType() == getContext().VoidTy
  1573. && "Empty statement expression must have void type.");
  1574. break;
  1575. }
  1576. if (const auto *LastExpr =
  1577. dyn_cast<Expr>(*SE->getSubStmt()->body_rbegin())) {
  1578. ProgramStateRef state = Pred->getState();
  1579. Bldr.generateNode(SE, Pred,
  1580. state->BindExpr(SE, Pred->getLocationContext(),
  1581. state->getSVal(LastExpr,
  1582. Pred->getLocationContext())));
  1583. }
  1584. break;
  1585. }
  1586. case Stmt::UnaryOperatorClass: {
  1587. Bldr.takeNodes(Pred);
  1588. const auto *U = cast<UnaryOperator>(S);
  1589. if (AMgr.options.ShouldEagerlyAssume && (U->getOpcode() == UO_LNot)) {
  1590. ExplodedNodeSet Tmp;
  1591. VisitUnaryOperator(U, Pred, Tmp);
  1592. evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, U);
  1593. }
  1594. else
  1595. VisitUnaryOperator(U, Pred, Dst);
  1596. Bldr.addNodes(Dst);
  1597. break;
  1598. }
  1599. case Stmt::PseudoObjectExprClass: {
  1600. Bldr.takeNodes(Pred);
  1601. ProgramStateRef state = Pred->getState();
  1602. const auto *PE = cast<PseudoObjectExpr>(S);
  1603. if (const Expr *Result = PE->getResultExpr()) {
  1604. SVal V = state->getSVal(Result, Pred->getLocationContext());
  1605. Bldr.generateNode(S, Pred,
  1606. state->BindExpr(S, Pred->getLocationContext(), V));
  1607. }
  1608. else
  1609. Bldr.generateNode(S, Pred,
  1610. state->BindExpr(S, Pred->getLocationContext(),
  1611. UnknownVal()));
  1612. Bldr.addNodes(Dst);
  1613. break;
  1614. }
  1615. }
  1616. }
  1617. bool ExprEngine::replayWithoutInlining(ExplodedNode *N,
  1618. const LocationContext *CalleeLC) {
  1619. const StackFrameContext *CalleeSF = CalleeLC->getStackFrame();
  1620. const StackFrameContext *CallerSF = CalleeSF->getParent()->getStackFrame();
  1621. assert(CalleeSF && CallerSF);
  1622. ExplodedNode *BeforeProcessingCall = nullptr;
  1623. const Stmt *CE = CalleeSF->getCallSite();
  1624. // Find the first node before we started processing the call expression.
  1625. while (N) {
  1626. ProgramPoint L = N->getLocation();
  1627. BeforeProcessingCall = N;
  1628. N = N->pred_empty() ? nullptr : *(N->pred_begin());
  1629. // Skip the nodes corresponding to the inlined code.
  1630. if (L.getStackFrame() != CallerSF)
  1631. continue;
  1632. // We reached the caller. Find the node right before we started
  1633. // processing the call.
  1634. if (L.isPurgeKind())
  1635. continue;
  1636. if (L.getAs<PreImplicitCall>())
  1637. continue;
  1638. if (L.getAs<CallEnter>())
  1639. continue;
  1640. if (Optional<StmtPoint> SP = L.getAs<StmtPoint>())
  1641. if (SP->getStmt() == CE)
  1642. continue;
  1643. break;
  1644. }
  1645. if (!BeforeProcessingCall)
  1646. return false;
  1647. // TODO: Clean up the unneeded nodes.
  1648. // Build an Epsilon node from which we will restart the analyzes.
  1649. // Note that CE is permitted to be NULL!
  1650. ProgramPoint NewNodeLoc =
  1651. EpsilonPoint(BeforeProcessingCall->getLocationContext(), CE);
  1652. // Add the special flag to GDM to signal retrying with no inlining.
  1653. // Note, changing the state ensures that we are not going to cache out.
  1654. ProgramStateRef NewNodeState = BeforeProcessingCall->getState();
  1655. NewNodeState =
  1656. NewNodeState->set<ReplayWithoutInlining>(const_cast<Stmt *>(CE));
  1657. // Make the new node a successor of BeforeProcessingCall.
  1658. bool IsNew = false;
  1659. ExplodedNode *NewNode = G.getNode(NewNodeLoc, NewNodeState, false, &IsNew);
  1660. // We cached out at this point. Caching out is common due to us backtracking
  1661. // from the inlined function, which might spawn several paths.
  1662. if (!IsNew)
  1663. return true;
  1664. NewNode->addPredecessor(BeforeProcessingCall, G);
  1665. // Add the new node to the work list.
  1666. Engine.enqueueStmtNode(NewNode, CalleeSF->getCallSiteBlock(),
  1667. CalleeSF->getIndex());
  1668. NumTimesRetriedWithoutInlining++;
  1669. return true;
  1670. }
  1671. /// Block entrance. (Update counters).
  1672. void ExprEngine::processCFGBlockEntrance(const BlockEdge &L,
  1673. NodeBuilderWithSinks &nodeBuilder,
  1674. ExplodedNode *Pred) {
  1675. PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
  1676. // If we reach a loop which has a known bound (and meets
  1677. // other constraints) then consider completely unrolling it.
  1678. if(AMgr.options.ShouldUnrollLoops) {
  1679. unsigned maxBlockVisitOnPath = AMgr.options.maxBlockVisitOnPath;
  1680. const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminatorStmt();
  1681. if (Term) {
  1682. ProgramStateRef NewState = updateLoopStack(Term, AMgr.getASTContext(),
  1683. Pred, maxBlockVisitOnPath);
  1684. if (NewState != Pred->getState()) {
  1685. ExplodedNode *UpdatedNode = nodeBuilder.generateNode(NewState, Pred);
  1686. if (!UpdatedNode)
  1687. return;
  1688. Pred = UpdatedNode;
  1689. }
  1690. }
  1691. // Is we are inside an unrolled loop then no need the check the counters.
  1692. if(isUnrolledState(Pred->getState()))
  1693. return;
  1694. }
  1695. // If this block is terminated by a loop and it has already been visited the
  1696. // maximum number of times, widen the loop.
  1697. unsigned int BlockCount = nodeBuilder.getContext().blockCount();
  1698. if (BlockCount == AMgr.options.maxBlockVisitOnPath - 1 &&
  1699. AMgr.options.ShouldWidenLoops) {
  1700. const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminatorStmt();
  1701. if (!(Term &&
  1702. (isa<ForStmt>(Term) || isa<WhileStmt>(Term) || isa<DoStmt>(Term))))
  1703. return;
  1704. // Widen.
  1705. const LocationContext *LCtx = Pred->getLocationContext();
  1706. ProgramStateRef WidenedState =
  1707. getWidenedLoopState(Pred->getState(), LCtx, BlockCount, Term);
  1708. nodeBuilder.generateNode(WidenedState, Pred);
  1709. return;
  1710. }
  1711. // FIXME: Refactor this into a checker.
  1712. if (BlockCount >= AMgr.options.maxBlockVisitOnPath) {
  1713. static SimpleProgramPointTag tag(TagProviderName, "Block count exceeded");
  1714. const ExplodedNode *Sink =
  1715. nodeBuilder.generateSink(Pred->getState(), Pred, &tag);
  1716. // Check if we stopped at the top level function or not.
  1717. // Root node should have the location context of the top most function.
  1718. const LocationContext *CalleeLC = Pred->getLocation().getLocationContext();
  1719. const LocationContext *CalleeSF = CalleeLC->getStackFrame();
  1720. const LocationContext *RootLC =
  1721. (*G.roots_begin())->getLocation().getLocationContext();
  1722. if (RootLC->getStackFrame() != CalleeSF) {
  1723. Engine.FunctionSummaries->markReachedMaxBlockCount(CalleeSF->getDecl());
  1724. // Re-run the call evaluation without inlining it, by storing the
  1725. // no-inlining policy in the state and enqueuing the new work item on
  1726. // the list. Replay should almost never fail. Use the stats to catch it
  1727. // if it does.
  1728. if ((!AMgr.options.NoRetryExhausted &&
  1729. replayWithoutInlining(Pred, CalleeLC)))
  1730. return;
  1731. NumMaxBlockCountReachedInInlined++;
  1732. } else
  1733. NumMaxBlockCountReached++;
  1734. // Make sink nodes as exhausted(for stats) only if retry failed.
  1735. Engine.blocksExhausted.push_back(std::make_pair(L, Sink));
  1736. }
  1737. }
  1738. //===----------------------------------------------------------------------===//
  1739. // Branch processing.
  1740. //===----------------------------------------------------------------------===//
  1741. /// RecoverCastedSymbol - A helper function for ProcessBranch that is used
  1742. /// to try to recover some path-sensitivity for casts of symbolic
  1743. /// integers that promote their values (which are currently not tracked well).
  1744. /// This function returns the SVal bound to Condition->IgnoreCasts if all the
  1745. // cast(s) did was sign-extend the original value.
  1746. static SVal RecoverCastedSymbol(ProgramStateRef state,
  1747. const Stmt *Condition,
  1748. const LocationContext *LCtx,
  1749. ASTContext &Ctx) {
  1750. const auto *Ex = dyn_cast<Expr>(Condition);
  1751. if (!Ex)
  1752. return UnknownVal();
  1753. uint64_t bits = 0;
  1754. bool bitsInit = false;
  1755. while (const auto *CE = dyn_cast<CastExpr>(Ex)) {
  1756. QualType T = CE->getType();
  1757. if (!T->isIntegralOrEnumerationType())
  1758. return UnknownVal();
  1759. uint64_t newBits = Ctx.getTypeSize(T);
  1760. if (!bitsInit || newBits < bits) {
  1761. bitsInit = true;
  1762. bits = newBits;
  1763. }
  1764. Ex = CE->getSubExpr();
  1765. }
  1766. // We reached a non-cast. Is it a symbolic value?
  1767. QualType T = Ex->getType();
  1768. if (!bitsInit || !T->isIntegralOrEnumerationType() ||
  1769. Ctx.getTypeSize(T) > bits)
  1770. return UnknownVal();
  1771. return state->getSVal(Ex, LCtx);
  1772. }
  1773. #ifndef NDEBUG
  1774. static const Stmt *getRightmostLeaf(const Stmt *Condition) {
  1775. while (Condition) {
  1776. const auto *BO = dyn_cast<BinaryOperator>(Condition);
  1777. if (!BO || !BO->isLogicalOp()) {
  1778. return Condition;
  1779. }
  1780. Condition = BO->getRHS()->IgnoreParens();
  1781. }
  1782. return nullptr;
  1783. }
  1784. #endif
  1785. // Returns the condition the branch at the end of 'B' depends on and whose value
  1786. // has been evaluated within 'B'.
  1787. // In most cases, the terminator condition of 'B' will be evaluated fully in
  1788. // the last statement of 'B'; in those cases, the resolved condition is the
  1789. // given 'Condition'.
  1790. // If the condition of the branch is a logical binary operator tree, the CFG is
  1791. // optimized: in that case, we know that the expression formed by all but the
  1792. // rightmost leaf of the logical binary operator tree must be true, and thus
  1793. // the branch condition is at this point equivalent to the truth value of that
  1794. // rightmost leaf; the CFG block thus only evaluates this rightmost leaf
  1795. // expression in its final statement. As the full condition in that case was
  1796. // not evaluated, and is thus not in the SVal cache, we need to use that leaf
  1797. // expression to evaluate the truth value of the condition in the current state
  1798. // space.
  1799. static const Stmt *ResolveCondition(const Stmt *Condition,
  1800. const CFGBlock *B) {
  1801. if (const auto *Ex = dyn_cast<Expr>(Condition))
  1802. Condition = Ex->IgnoreParens();
  1803. const auto *BO = dyn_cast<BinaryOperator>(Condition);
  1804. if (!BO || !BO->isLogicalOp())
  1805. return Condition;
  1806. assert(B->getTerminator().isStmtBranch() &&
  1807. "Other kinds of branches are handled separately!");
  1808. // For logical operations, we still have the case where some branches
  1809. // use the traditional "merge" approach and others sink the branch
  1810. // directly into the basic blocks representing the logical operation.
  1811. // We need to distinguish between those two cases here.
  1812. // The invariants are still shifting, but it is possible that the
  1813. // last element in a CFGBlock is not a CFGStmt. Look for the last
  1814. // CFGStmt as the value of the condition.
  1815. CFGBlock::const_reverse_iterator I = B->rbegin(), E = B->rend();
  1816. for (; I != E; ++I) {
  1817. CFGElement Elem = *I;
  1818. Optional<CFGStmt> CS = Elem.getAs<CFGStmt>();
  1819. if (!CS)
  1820. continue;
  1821. const Stmt *LastStmt = CS->getStmt();
  1822. assert(LastStmt == Condition || LastStmt == getRightmostLeaf(Condition));
  1823. return LastStmt;
  1824. }
  1825. llvm_unreachable("could not resolve condition");
  1826. }
  1827. void ExprEngine::processBranch(const Stmt *Condition,
  1828. NodeBuilderContext& BldCtx,
  1829. ExplodedNode *Pred,
  1830. ExplodedNodeSet &Dst,
  1831. const CFGBlock *DstT,
  1832. const CFGBlock *DstF) {
  1833. assert((!Condition || !isa<CXXBindTemporaryExpr>(Condition)) &&
  1834. "CXXBindTemporaryExprs are handled by processBindTemporary.");
  1835. const LocationContext *LCtx = Pred->getLocationContext();
  1836. PrettyStackTraceLocationContext StackCrashInfo(LCtx);
  1837. currBldrCtx = &BldCtx;
  1838. // Check for NULL conditions; e.g. "for(;;)"
  1839. if (!Condition) {
  1840. BranchNodeBuilder NullCondBldr(Pred, Dst, BldCtx, DstT, DstF);
  1841. NullCondBldr.markInfeasible(false);
  1842. NullCondBldr.generateNode(Pred->getState(), true, Pred);
  1843. return;
  1844. }
  1845. if (const auto *Ex = dyn_cast<Expr>(Condition))
  1846. Condition = Ex->IgnoreParens();
  1847. Condition = ResolveCondition(Condition, BldCtx.getBlock());
  1848. PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
  1849. Condition->getBeginLoc(),
  1850. "Error evaluating branch");
  1851. ExplodedNodeSet CheckersOutSet;
  1852. getCheckerManager().runCheckersForBranchCondition(Condition, CheckersOutSet,
  1853. Pred, *this);
  1854. // We generated only sinks.
  1855. if (CheckersOutSet.empty())
  1856. return;
  1857. BranchNodeBuilder builder(CheckersOutSet, Dst, BldCtx, DstT, DstF);
  1858. for (const auto PredI : CheckersOutSet) {
  1859. if (PredI->isSink())
  1860. continue;
  1861. ProgramStateRef PrevState = PredI->getState();
  1862. SVal X = PrevState->getSVal(Condition, PredI->getLocationContext());
  1863. if (X.isUnknownOrUndef()) {
  1864. // Give it a chance to recover from unknown.
  1865. if (const auto *Ex = dyn_cast<Expr>(Condition)) {
  1866. if (Ex->getType()->isIntegralOrEnumerationType()) {
  1867. // Try to recover some path-sensitivity. Right now casts of symbolic
  1868. // integers that promote their values are currently not tracked well.
  1869. // If 'Condition' is such an expression, try and recover the
  1870. // underlying value and use that instead.
  1871. SVal recovered = RecoverCastedSymbol(PrevState, Condition,
  1872. PredI->getLocationContext(),
  1873. getContext());
  1874. if (!recovered.isUnknown()) {
  1875. X = recovered;
  1876. }
  1877. }
  1878. }
  1879. }
  1880. // If the condition is still unknown, give up.
  1881. if (X.isUnknownOrUndef()) {
  1882. builder.generateNode(PrevState, true, PredI);
  1883. builder.generateNode(PrevState, false, PredI);
  1884. continue;
  1885. }
  1886. DefinedSVal V = X.castAs<DefinedSVal>();
  1887. ProgramStateRef StTrue, StFalse;
  1888. std::tie(StTrue, StFalse) = PrevState->assume(V);
  1889. // Process the true branch.
  1890. if (builder.isFeasible(true)) {
  1891. if (StTrue)
  1892. builder.generateNode(StTrue, true, PredI);
  1893. else
  1894. builder.markInfeasible(true);
  1895. }
  1896. // Process the false branch.
  1897. if (builder.isFeasible(false)) {
  1898. if (StFalse)
  1899. builder.generateNode(StFalse, false, PredI);
  1900. else
  1901. builder.markInfeasible(false);
  1902. }
  1903. }
  1904. currBldrCtx = nullptr;
  1905. }
  1906. /// The GDM component containing the set of global variables which have been
  1907. /// previously initialized with explicit initializers.
  1908. REGISTER_TRAIT_WITH_PROGRAMSTATE(InitializedGlobalsSet,
  1909. llvm::ImmutableSet<const VarDecl *>)
  1910. void ExprEngine::processStaticInitializer(const DeclStmt *DS,
  1911. NodeBuilderContext &BuilderCtx,
  1912. ExplodedNode *Pred,
  1913. ExplodedNodeSet &Dst,
  1914. const CFGBlock *DstT,
  1915. const CFGBlock *DstF) {
  1916. PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
  1917. currBldrCtx = &BuilderCtx;
  1918. const auto *VD = cast<VarDecl>(DS->getSingleDecl());
  1919. ProgramStateRef state = Pred->getState();
  1920. bool initHasRun = state->contains<InitializedGlobalsSet>(VD);
  1921. BranchNodeBuilder builder(Pred, Dst, BuilderCtx, DstT, DstF);
  1922. if (!initHasRun) {
  1923. state = state->add<InitializedGlobalsSet>(VD);
  1924. }
  1925. builder.generateNode(state, initHasRun, Pred);
  1926. builder.markInfeasible(!initHasRun);
  1927. currBldrCtx = nullptr;
  1928. }
  1929. /// processIndirectGoto - Called by CoreEngine. Used to generate successor
  1930. /// nodes by processing the 'effects' of a computed goto jump.
  1931. void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) {
  1932. ProgramStateRef state = builder.getState();
  1933. SVal V = state->getSVal(builder.getTarget(), builder.getLocationContext());
  1934. // Three possibilities:
  1935. //
  1936. // (1) We know the computed label.
  1937. // (2) The label is NULL (or some other constant), or Undefined.
  1938. // (3) We have no clue about the label. Dispatch to all targets.
  1939. //
  1940. using iterator = IndirectGotoNodeBuilder::iterator;
  1941. if (Optional<loc::GotoLabel> LV = V.getAs<loc::GotoLabel>()) {
  1942. const LabelDecl *L = LV->getLabel();
  1943. for (iterator I = builder.begin(), E = builder.end(); I != E; ++I) {
  1944. if (I.getLabel() == L) {
  1945. builder.generateNode(I, state);
  1946. return;
  1947. }
  1948. }
  1949. llvm_unreachable("No block with label.");
  1950. }
  1951. if (V.getAs<loc::ConcreteInt>() || V.getAs<UndefinedVal>()) {
  1952. // Dispatch to the first target and mark it as a sink.
  1953. //ExplodedNode* N = builder.generateNode(builder.begin(), state, true);
  1954. // FIXME: add checker visit.
  1955. // UndefBranches.insert(N);
  1956. return;
  1957. }
  1958. // This is really a catch-all. We don't support symbolics yet.
  1959. // FIXME: Implement dispatch for symbolic pointers.
  1960. for (iterator I = builder.begin(), E = builder.end(); I != E; ++I)
  1961. builder.generateNode(I, state);
  1962. }
  1963. void ExprEngine::processBeginOfFunction(NodeBuilderContext &BC,
  1964. ExplodedNode *Pred,
  1965. ExplodedNodeSet &Dst,
  1966. const BlockEdge &L) {
  1967. SaveAndRestore<const NodeBuilderContext *> NodeContextRAII(currBldrCtx, &BC);
  1968. getCheckerManager().runCheckersForBeginFunction(Dst, L, Pred, *this);
  1969. }
  1970. /// ProcessEndPath - Called by CoreEngine. Used to generate end-of-path
  1971. /// nodes when the control reaches the end of a function.
  1972. void ExprEngine::processEndOfFunction(NodeBuilderContext& BC,
  1973. ExplodedNode *Pred,
  1974. const ReturnStmt *RS) {
  1975. ProgramStateRef State = Pred->getState();
  1976. if (!Pred->getStackFrame()->inTopFrame())
  1977. State = finishArgumentConstruction(
  1978. State, *getStateManager().getCallEventManager().getCaller(
  1979. Pred->getStackFrame(), Pred->getState()));
  1980. // FIXME: We currently cannot assert that temporaries are clear, because
  1981. // lifetime extended temporaries are not always modelled correctly. In some
  1982. // cases when we materialize the temporary, we do
  1983. // createTemporaryRegionIfNeeded(), and the region changes, and also the
  1984. // respective destructor becomes automatic from temporary. So for now clean up
  1985. // the state manually before asserting. Ideally, this braced block of code
  1986. // should go away.
  1987. {
  1988. const LocationContext *FromLC = Pred->getLocationContext();
  1989. const LocationContext *ToLC = FromLC->getStackFrame()->getParent();
  1990. const LocationContext *LC = FromLC;
  1991. while (LC != ToLC) {
  1992. assert(LC && "ToLC must be a parent of FromLC!");
  1993. for (auto I : State->get<ObjectsUnderConstruction>())
  1994. if (I.first.getLocationContext() == LC) {
  1995. // The comment above only pardons us for not cleaning up a
  1996. // temporary destructor. If any other statements are found here,
  1997. // it must be a separate problem.
  1998. assert(I.first.getItem().getKind() ==
  1999. ConstructionContextItem::TemporaryDestructorKind ||
  2000. I.first.getItem().getKind() ==
  2001. ConstructionContextItem::ElidedDestructorKind);
  2002. State = State->remove<ObjectsUnderConstruction>(I.first);
  2003. }
  2004. LC = LC->getParent();
  2005. }
  2006. }
  2007. // Perform the transition with cleanups.
  2008. if (State != Pred->getState()) {
  2009. ExplodedNodeSet PostCleanup;
  2010. NodeBuilder Bldr(Pred, PostCleanup, BC);
  2011. Pred = Bldr.generateNode(Pred->getLocation(), State, Pred);
  2012. if (!Pred) {
  2013. // The node with clean temporaries already exists. We might have reached
  2014. // it on a path on which we initialize different temporaries.
  2015. return;
  2016. }
  2017. }
  2018. assert(areAllObjectsFullyConstructed(Pred->getState(),
  2019. Pred->getLocationContext(),
  2020. Pred->getStackFrame()->getParent()));
  2021. PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
  2022. ExplodedNodeSet Dst;
  2023. if (Pred->getLocationContext()->inTopFrame()) {
  2024. // Remove dead symbols.
  2025. ExplodedNodeSet AfterRemovedDead;
  2026. removeDeadOnEndOfFunction(BC, Pred, AfterRemovedDead);
  2027. // Notify checkers.
  2028. for (const auto I : AfterRemovedDead)
  2029. getCheckerManager().runCheckersForEndFunction(BC, Dst, I, *this, RS);
  2030. } else {
  2031. getCheckerManager().runCheckersForEndFunction(BC, Dst, Pred, *this, RS);
  2032. }
  2033. Engine.enqueueEndOfFunction(Dst, RS);
  2034. }
  2035. /// ProcessSwitch - Called by CoreEngine. Used to generate successor
  2036. /// nodes by processing the 'effects' of a switch statement.
  2037. void ExprEngine::processSwitch(SwitchNodeBuilder& builder) {
  2038. using iterator = SwitchNodeBuilder::iterator;
  2039. ProgramStateRef state = builder.getState();
  2040. const Expr *CondE = builder.getCondition();
  2041. SVal CondV_untested = state->getSVal(CondE, builder.getLocationContext());
  2042. if (CondV_untested.isUndef()) {
  2043. //ExplodedNode* N = builder.generateDefaultCaseNode(state, true);
  2044. // FIXME: add checker
  2045. //UndefBranches.insert(N);
  2046. return;
  2047. }
  2048. DefinedOrUnknownSVal CondV = CondV_untested.castAs<DefinedOrUnknownSVal>();
  2049. ProgramStateRef DefaultSt = state;
  2050. iterator I = builder.begin(), EI = builder.end();
  2051. bool defaultIsFeasible = I == EI;
  2052. for ( ; I != EI; ++I) {
  2053. // Successor may be pruned out during CFG construction.
  2054. if (!I.getBlock())
  2055. continue;
  2056. const CaseStmt *Case = I.getCase();
  2057. // Evaluate the LHS of the case value.
  2058. llvm::APSInt V1 = Case->getLHS()->EvaluateKnownConstInt(getContext());
  2059. assert(V1.getBitWidth() == getContext().getIntWidth(CondE->getType()));
  2060. // Get the RHS of the case, if it exists.
  2061. llvm::APSInt V2;
  2062. if (const Expr *E = Case->getRHS())
  2063. V2 = E->EvaluateKnownConstInt(getContext());
  2064. else
  2065. V2 = V1;
  2066. ProgramStateRef StateCase;
  2067. if (Optional<NonLoc> NL = CondV.getAs<NonLoc>())
  2068. std::tie(StateCase, DefaultSt) =
  2069. DefaultSt->assumeInclusiveRange(*NL, V1, V2);
  2070. else // UnknownVal
  2071. StateCase = DefaultSt;
  2072. if (StateCase)
  2073. builder.generateCaseStmtNode(I, StateCase);
  2074. // Now "assume" that the case doesn't match. Add this state
  2075. // to the default state (if it is feasible).
  2076. if (DefaultSt)
  2077. defaultIsFeasible = true;
  2078. else {
  2079. defaultIsFeasible = false;
  2080. break;
  2081. }
  2082. }
  2083. if (!defaultIsFeasible)
  2084. return;
  2085. // If we have switch(enum value), the default branch is not
  2086. // feasible if all of the enum constants not covered by 'case:' statements
  2087. // are not feasible values for the switch condition.
  2088. //
  2089. // Note that this isn't as accurate as it could be. Even if there isn't
  2090. // a case for a particular enum value as long as that enum value isn't
  2091. // feasible then it shouldn't be considered for making 'default:' reachable.
  2092. const SwitchStmt *SS = builder.getSwitch();
  2093. const Expr *CondExpr = SS->getCond()->IgnoreParenImpCasts();
  2094. if (CondExpr->getType()->getAs<EnumType>()) {
  2095. if (SS->isAllEnumCasesCovered())
  2096. return;
  2097. }
  2098. builder.generateDefaultCaseNode(DefaultSt);
  2099. }
  2100. //===----------------------------------------------------------------------===//
  2101. // Transfer functions: Loads and stores.
  2102. //===----------------------------------------------------------------------===//
  2103. void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D,
  2104. ExplodedNode *Pred,
  2105. ExplodedNodeSet &Dst) {
  2106. StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
  2107. ProgramStateRef state = Pred->getState();
  2108. const LocationContext *LCtx = Pred->getLocationContext();
  2109. if (const auto *VD = dyn_cast<VarDecl>(D)) {
  2110. // C permits "extern void v", and if you cast the address to a valid type,
  2111. // you can even do things with it. We simply pretend
  2112. assert(Ex->isGLValue() || VD->getType()->isVoidType());
  2113. const LocationContext *LocCtxt = Pred->getLocationContext();
  2114. const Decl *D = LocCtxt->getDecl();
  2115. const auto *MD = dyn_cast_or_null<CXXMethodDecl>(D);
  2116. const auto *DeclRefEx = dyn_cast<DeclRefExpr>(Ex);
  2117. Optional<std::pair<SVal, QualType>> VInfo;
  2118. if (AMgr.options.ShouldInlineLambdas && DeclRefEx &&
  2119. DeclRefEx->refersToEnclosingVariableOrCapture() && MD &&
  2120. MD->getParent()->isLambda()) {
  2121. // Lookup the field of the lambda.
  2122. const CXXRecordDecl *CXXRec = MD->getParent();
  2123. llvm::DenseMap<const VarDecl *, FieldDecl *> LambdaCaptureFields;
  2124. FieldDecl *LambdaThisCaptureField;
  2125. CXXRec->getCaptureFields(LambdaCaptureFields, LambdaThisCaptureField);
  2126. // Sema follows a sequence of complex rules to determine whether the
  2127. // variable should be captured.
  2128. if (const FieldDecl *FD = LambdaCaptureFields[VD]) {
  2129. Loc CXXThis =
  2130. svalBuilder.getCXXThis(MD, LocCtxt->getStackFrame());
  2131. SVal CXXThisVal = state->getSVal(CXXThis);
  2132. VInfo = std::make_pair(state->getLValue(FD, CXXThisVal), FD->getType());
  2133. }
  2134. }
  2135. if (!VInfo)
  2136. VInfo = std::make_pair(state->getLValue(VD, LocCtxt), VD->getType());
  2137. SVal V = VInfo->first;
  2138. bool IsReference = VInfo->second->isReferenceType();
  2139. // For references, the 'lvalue' is the pointer address stored in the
  2140. // reference region.
  2141. if (IsReference) {
  2142. if (const MemRegion *R = V.getAsRegion())
  2143. V = state->getSVal(R);
  2144. else
  2145. V = UnknownVal();
  2146. }
  2147. Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr,
  2148. ProgramPoint::PostLValueKind);
  2149. return;
  2150. }
  2151. if (const auto *ED = dyn_cast<EnumConstantDecl>(D)) {
  2152. assert(!Ex->isGLValue());
  2153. SVal V = svalBuilder.makeIntVal(ED->getInitVal());
  2154. Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V));
  2155. return;
  2156. }
  2157. if (const auto *FD = dyn_cast<FunctionDecl>(D)) {
  2158. SVal V = svalBuilder.getFunctionPointer(FD);
  2159. Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr,
  2160. ProgramPoint::PostLValueKind);
  2161. return;
  2162. }
  2163. if (isa<FieldDecl>(D) || isa<IndirectFieldDecl>(D)) {
  2164. // FIXME: Compute lvalue of field pointers-to-member.
  2165. // Right now we just use a non-null void pointer, so that it gives proper
  2166. // results in boolean contexts.
  2167. // FIXME: Maybe delegate this to the surrounding operator&.
  2168. // Note how this expression is lvalue, however pointer-to-member is NonLoc.
  2169. SVal V = svalBuilder.conjureSymbolVal(Ex, LCtx, getContext().VoidPtrTy,
  2170. currBldrCtx->blockCount());
  2171. state = state->assume(V.castAs<DefinedOrUnknownSVal>(), true);
  2172. Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr,
  2173. ProgramPoint::PostLValueKind);
  2174. return;
  2175. }
  2176. if (isa<BindingDecl>(D)) {
  2177. // FIXME: proper support for bound declarations.
  2178. // For now, let's just prevent crashing.
  2179. return;
  2180. }
  2181. llvm_unreachable("Support for this Decl not implemented.");
  2182. }
  2183. /// VisitArraySubscriptExpr - Transfer function for array accesses
  2184. void ExprEngine::VisitArraySubscriptExpr(const ArraySubscriptExpr *A,
  2185. ExplodedNode *Pred,
  2186. ExplodedNodeSet &Dst){
  2187. const Expr *Base = A->getBase()->IgnoreParens();
  2188. const Expr *Idx = A->getIdx()->IgnoreParens();
  2189. ExplodedNodeSet CheckerPreStmt;
  2190. getCheckerManager().runCheckersForPreStmt(CheckerPreStmt, Pred, A, *this);
  2191. ExplodedNodeSet EvalSet;
  2192. StmtNodeBuilder Bldr(CheckerPreStmt, EvalSet, *currBldrCtx);
  2193. bool IsVectorType = A->getBase()->getType()->isVectorType();
  2194. // The "like" case is for situations where C standard prohibits the type to
  2195. // be an lvalue, e.g. taking the address of a subscript of an expression of
  2196. // type "void *".
  2197. bool IsGLValueLike = A->isGLValue() ||
  2198. (A->getType().isCForbiddenLValueType() && !AMgr.getLangOpts().CPlusPlus);
  2199. for (auto *Node : CheckerPreStmt) {
  2200. const LocationContext *LCtx = Node->getLocationContext();
  2201. ProgramStateRef state = Node->getState();
  2202. if (IsGLValueLike) {
  2203. QualType T = A->getType();
  2204. // One of the forbidden LValue types! We still need to have sensible
  2205. // symbolic locations to represent this stuff. Note that arithmetic on
  2206. // void pointers is a GCC extension.
  2207. if (T->isVoidType())
  2208. T = getContext().CharTy;
  2209. SVal V = state->getLValue(T,
  2210. state->getSVal(Idx, LCtx),
  2211. state->getSVal(Base, LCtx));
  2212. Bldr.generateNode(A, Node, state->BindExpr(A, LCtx, V), nullptr,
  2213. ProgramPoint::PostLValueKind);
  2214. } else if (IsVectorType) {
  2215. // FIXME: non-glvalue vector reads are not modelled.
  2216. Bldr.generateNode(A, Node, state, nullptr);
  2217. } else {
  2218. llvm_unreachable("Array subscript should be an lValue when not \
  2219. a vector and not a forbidden lvalue type");
  2220. }
  2221. }
  2222. getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, A, *this);
  2223. }
  2224. /// VisitMemberExpr - Transfer function for member expressions.
  2225. void ExprEngine::VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred,
  2226. ExplodedNodeSet &Dst) {
  2227. // FIXME: Prechecks eventually go in ::Visit().
  2228. ExplodedNodeSet CheckedSet;
  2229. getCheckerManager().runCheckersForPreStmt(CheckedSet, Pred, M, *this);
  2230. ExplodedNodeSet EvalSet;
  2231. ValueDecl *Member = M->getMemberDecl();
  2232. // Handle static member variables and enum constants accessed via
  2233. // member syntax.
  2234. if (isa<VarDecl>(Member) || isa<EnumConstantDecl>(Member)) {
  2235. for (const auto I : CheckedSet)
  2236. VisitCommonDeclRefExpr(M, Member, I, EvalSet);
  2237. } else {
  2238. StmtNodeBuilder Bldr(CheckedSet, EvalSet, *currBldrCtx);
  2239. ExplodedNodeSet Tmp;
  2240. for (const auto I : CheckedSet) {
  2241. ProgramStateRef state = I->getState();
  2242. const LocationContext *LCtx = I->getLocationContext();
  2243. Expr *BaseExpr = M->getBase();
  2244. // Handle C++ method calls.
  2245. if (const auto *MD = dyn_cast<CXXMethodDecl>(Member)) {
  2246. if (MD->isInstance())
  2247. state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr);
  2248. SVal MDVal = svalBuilder.getFunctionPointer(MD);
  2249. state = state->BindExpr(M, LCtx, MDVal);
  2250. Bldr.generateNode(M, I, state);
  2251. continue;
  2252. }
  2253. // Handle regular struct fields / member variables.
  2254. const SubRegion *MR = nullptr;
  2255. state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr,
  2256. /*Result=*/nullptr,
  2257. /*OutRegionWithAdjustments=*/&MR);
  2258. SVal baseExprVal =
  2259. MR ? loc::MemRegionVal(MR) : state->getSVal(BaseExpr, LCtx);
  2260. const auto *field = cast<FieldDecl>(Member);
  2261. SVal L = state->getLValue(field, baseExprVal);
  2262. if (M->isGLValue() || M->getType()->isArrayType()) {
  2263. // We special-case rvalues of array type because the analyzer cannot
  2264. // reason about them, since we expect all regions to be wrapped in Locs.
  2265. // We instead treat these as lvalues and assume that they will decay to
  2266. // pointers as soon as they are used.
  2267. if (!M->isGLValue()) {
  2268. assert(M->getType()->isArrayType());
  2269. const auto *PE =
  2270. dyn_cast<ImplicitCastExpr>(I->getParentMap().getParentIgnoreParens(M));
  2271. if (!PE || PE->getCastKind() != CK_ArrayToPointerDecay) {
  2272. llvm_unreachable("should always be wrapped in ArrayToPointerDecay");
  2273. }
  2274. }
  2275. if (field->getType()->isReferenceType()) {
  2276. if (const MemRegion *R = L.getAsRegion())
  2277. L = state->getSVal(R);
  2278. else
  2279. L = UnknownVal();
  2280. }
  2281. Bldr.generateNode(M, I, state->BindExpr(M, LCtx, L), nullptr,
  2282. ProgramPoint::PostLValueKind);
  2283. } else {
  2284. Bldr.takeNodes(I);
  2285. evalLoad(Tmp, M, M, I, state, L);
  2286. Bldr.addNodes(Tmp);
  2287. }
  2288. }
  2289. }
  2290. getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, M, *this);
  2291. }
  2292. void ExprEngine::VisitAtomicExpr(const AtomicExpr *AE, ExplodedNode *Pred,
  2293. ExplodedNodeSet &Dst) {
  2294. ExplodedNodeSet AfterPreSet;
  2295. getCheckerManager().runCheckersForPreStmt(AfterPreSet, Pred, AE, *this);
  2296. // For now, treat all the arguments to C11 atomics as escaping.
  2297. // FIXME: Ideally we should model the behavior of the atomics precisely here.
  2298. ExplodedNodeSet AfterInvalidateSet;
  2299. StmtNodeBuilder Bldr(AfterPreSet, AfterInvalidateSet, *currBldrCtx);
  2300. for (const auto I : AfterPreSet) {
  2301. ProgramStateRef State = I->getState();
  2302. const LocationContext *LCtx = I->getLocationContext();
  2303. SmallVector<SVal, 8> ValuesToInvalidate;
  2304. for (unsigned SI = 0, Count = AE->getNumSubExprs(); SI != Count; SI++) {
  2305. const Expr *SubExpr = AE->getSubExprs()[SI];
  2306. SVal SubExprVal = State->getSVal(SubExpr, LCtx);
  2307. ValuesToInvalidate.push_back(SubExprVal);
  2308. }
  2309. State = State->invalidateRegions(ValuesToInvalidate, AE,
  2310. currBldrCtx->blockCount(),
  2311. LCtx,
  2312. /*CausedByPointerEscape*/true,
  2313. /*Symbols=*/nullptr);
  2314. SVal ResultVal = UnknownVal();
  2315. State = State->BindExpr(AE, LCtx, ResultVal);
  2316. Bldr.generateNode(AE, I, State, nullptr,
  2317. ProgramPoint::PostStmtKind);
  2318. }
  2319. getCheckerManager().runCheckersForPostStmt(Dst, AfterInvalidateSet, AE, *this);
  2320. }
  2321. // A value escapes in four possible cases:
  2322. // (1) We are binding to something that is not a memory region.
  2323. // (2) We are binding to a MemRegion that does not have stack storage.
  2324. // (3) We are binding to a top-level parameter region with a non-trivial
  2325. // destructor. We won't see the destructor during analysis, but it's there.
  2326. // (4) We are binding to a MemRegion with stack storage that the store
  2327. // does not understand.
  2328. ProgramStateRef
  2329. ExprEngine::processPointerEscapedOnBind(ProgramStateRef State, SVal Loc,
  2330. SVal Val, const LocationContext *LCtx) {
  2331. // Cases (1) and (2).
  2332. const MemRegion *MR = Loc.getAsRegion();
  2333. if (!MR || !MR->hasStackStorage())
  2334. return escapeValue(State, Val, PSK_EscapeOnBind);
  2335. // Case (3).
  2336. if (const auto *VR = dyn_cast<VarRegion>(MR->getBaseRegion()))
  2337. if (VR->hasStackParametersStorage() && VR->getStackFrame()->inTopFrame())
  2338. if (const auto *RD = VR->getValueType()->getAsCXXRecordDecl())
  2339. if (!RD->hasTrivialDestructor())
  2340. return escapeValue(State, Val, PSK_EscapeOnBind);
  2341. // Case (4): in order to test that, generate a new state with the binding
  2342. // added. If it is the same state, then it escapes (since the store cannot
  2343. // represent the binding).
  2344. // Do this only if we know that the store is not supposed to generate the
  2345. // same state.
  2346. SVal StoredVal = State->getSVal(MR);
  2347. if (StoredVal != Val)
  2348. if (State == (State->bindLoc(loc::MemRegionVal(MR), Val, LCtx)))
  2349. return escapeValue(State, Val, PSK_EscapeOnBind);
  2350. return State;
  2351. }
  2352. ProgramStateRef
  2353. ExprEngine::notifyCheckersOfPointerEscape(ProgramStateRef State,
  2354. const InvalidatedSymbols *Invalidated,
  2355. ArrayRef<const MemRegion *> ExplicitRegions,
  2356. const CallEvent *Call,
  2357. RegionAndSymbolInvalidationTraits &ITraits) {
  2358. if (!Invalidated || Invalidated->empty())
  2359. return State;
  2360. if (!Call)
  2361. return getCheckerManager().runCheckersForPointerEscape(State,
  2362. *Invalidated,
  2363. nullptr,
  2364. PSK_EscapeOther,
  2365. &ITraits);
  2366. // If the symbols were invalidated by a call, we want to find out which ones
  2367. // were invalidated directly due to being arguments to the call.
  2368. InvalidatedSymbols SymbolsDirectlyInvalidated;
  2369. for (const auto I : ExplicitRegions) {
  2370. if (const SymbolicRegion *R = I->StripCasts()->getAs<SymbolicRegion>())
  2371. SymbolsDirectlyInvalidated.insert(R->getSymbol());
  2372. }
  2373. InvalidatedSymbols SymbolsIndirectlyInvalidated;
  2374. for (const auto &sym : *Invalidated) {
  2375. if (SymbolsDirectlyInvalidated.count(sym))
  2376. continue;
  2377. SymbolsIndirectlyInvalidated.insert(sym);
  2378. }
  2379. if (!SymbolsDirectlyInvalidated.empty())
  2380. State = getCheckerManager().runCheckersForPointerEscape(State,
  2381. SymbolsDirectlyInvalidated, Call, PSK_DirectEscapeOnCall, &ITraits);
  2382. // Notify about the symbols that get indirectly invalidated by the call.
  2383. if (!SymbolsIndirectlyInvalidated.empty())
  2384. State = getCheckerManager().runCheckersForPointerEscape(State,
  2385. SymbolsIndirectlyInvalidated, Call, PSK_IndirectEscapeOnCall, &ITraits);
  2386. return State;
  2387. }
  2388. /// evalBind - Handle the semantics of binding a value to a specific location.
  2389. /// This method is used by evalStore and (soon) VisitDeclStmt, and others.
  2390. void ExprEngine::evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE,
  2391. ExplodedNode *Pred,
  2392. SVal location, SVal Val,
  2393. bool atDeclInit, const ProgramPoint *PP) {
  2394. const LocationContext *LC = Pred->getLocationContext();
  2395. PostStmt PS(StoreE, LC);
  2396. if (!PP)
  2397. PP = &PS;
  2398. // Do a previsit of the bind.
  2399. ExplodedNodeSet CheckedSet;
  2400. getCheckerManager().runCheckersForBind(CheckedSet, Pred, location, Val,
  2401. StoreE, *this, *PP);
  2402. StmtNodeBuilder Bldr(CheckedSet, Dst, *currBldrCtx);
  2403. // If the location is not a 'Loc', it will already be handled by
  2404. // the checkers. There is nothing left to do.
  2405. if (!location.getAs<Loc>()) {
  2406. const ProgramPoint L = PostStore(StoreE, LC, /*Loc*/nullptr,
  2407. /*tag*/nullptr);
  2408. ProgramStateRef state = Pred->getState();
  2409. state = processPointerEscapedOnBind(state, location, Val, LC);
  2410. Bldr.generateNode(L, state, Pred);
  2411. return;
  2412. }
  2413. for (const auto PredI : CheckedSet) {
  2414. ProgramStateRef state = PredI->getState();
  2415. state = processPointerEscapedOnBind(state, location, Val, LC);
  2416. // When binding the value, pass on the hint that this is a initialization.
  2417. // For initializations, we do not need to inform clients of region
  2418. // changes.
  2419. state = state->bindLoc(location.castAs<Loc>(),
  2420. Val, LC, /* notifyChanges = */ !atDeclInit);
  2421. const MemRegion *LocReg = nullptr;
  2422. if (Optional<loc::MemRegionVal> LocRegVal =
  2423. location.getAs<loc::MemRegionVal>()) {
  2424. LocReg = LocRegVal->getRegion();
  2425. }
  2426. const ProgramPoint L = PostStore(StoreE, LC, LocReg, nullptr);
  2427. Bldr.generateNode(L, state, PredI);
  2428. }
  2429. }
  2430. /// evalStore - Handle the semantics of a store via an assignment.
  2431. /// @param Dst The node set to store generated state nodes
  2432. /// @param AssignE The assignment expression if the store happens in an
  2433. /// assignment.
  2434. /// @param LocationE The location expression that is stored to.
  2435. /// @param state The current simulation state
  2436. /// @param location The location to store the value
  2437. /// @param Val The value to be stored
  2438. void ExprEngine::evalStore(ExplodedNodeSet &Dst, const Expr *AssignE,
  2439. const Expr *LocationE,
  2440. ExplodedNode *Pred,
  2441. ProgramStateRef state, SVal location, SVal Val,
  2442. const ProgramPointTag *tag) {
  2443. // Proceed with the store. We use AssignE as the anchor for the PostStore
  2444. // ProgramPoint if it is non-NULL, and LocationE otherwise.
  2445. const Expr *StoreE = AssignE ? AssignE : LocationE;
  2446. // Evaluate the location (checks for bad dereferences).
  2447. ExplodedNodeSet Tmp;
  2448. evalLocation(Tmp, AssignE, LocationE, Pred, state, location, false);
  2449. if (Tmp.empty())
  2450. return;
  2451. if (location.isUndef())
  2452. return;
  2453. for (const auto I : Tmp)
  2454. evalBind(Dst, StoreE, I, location, Val, false);
  2455. }
  2456. void ExprEngine::evalLoad(ExplodedNodeSet &Dst,
  2457. const Expr *NodeEx,
  2458. const Expr *BoundEx,
  2459. ExplodedNode *Pred,
  2460. ProgramStateRef state,
  2461. SVal location,
  2462. const ProgramPointTag *tag,
  2463. QualType LoadTy) {
  2464. assert(!location.getAs<NonLoc>() && "location cannot be a NonLoc.");
  2465. assert(NodeEx);
  2466. assert(BoundEx);
  2467. // Evaluate the location (checks for bad dereferences).
  2468. ExplodedNodeSet Tmp;
  2469. evalLocation(Tmp, NodeEx, BoundEx, Pred, state, location, true);
  2470. if (Tmp.empty())
  2471. return;
  2472. StmtNodeBuilder Bldr(Tmp, Dst, *currBldrCtx);
  2473. if (location.isUndef())
  2474. return;
  2475. // Proceed with the load.
  2476. for (const auto I : Tmp) {
  2477. state = I->getState();
  2478. const LocationContext *LCtx = I->getLocationContext();
  2479. SVal V = UnknownVal();
  2480. if (location.isValid()) {
  2481. if (LoadTy.isNull())
  2482. LoadTy = BoundEx->getType();
  2483. V = state->getSVal(location.castAs<Loc>(), LoadTy);
  2484. }
  2485. Bldr.generateNode(NodeEx, I, state->BindExpr(BoundEx, LCtx, V), tag,
  2486. ProgramPoint::PostLoadKind);
  2487. }
  2488. }
  2489. void ExprEngine::evalLocation(ExplodedNodeSet &Dst,
  2490. const Stmt *NodeEx,
  2491. const Stmt *BoundEx,
  2492. ExplodedNode *Pred,
  2493. ProgramStateRef state,
  2494. SVal location,
  2495. bool isLoad) {
  2496. StmtNodeBuilder BldrTop(Pred, Dst, *currBldrCtx);
  2497. // Early checks for performance reason.
  2498. if (location.isUnknown()) {
  2499. return;
  2500. }
  2501. ExplodedNodeSet Src;
  2502. BldrTop.takeNodes(Pred);
  2503. StmtNodeBuilder Bldr(Pred, Src, *currBldrCtx);
  2504. if (Pred->getState() != state) {
  2505. // Associate this new state with an ExplodedNode.
  2506. // FIXME: If I pass null tag, the graph is incorrect, e.g for
  2507. // int *p;
  2508. // p = 0;
  2509. // *p = 0xDEADBEEF;
  2510. // "p = 0" is not noted as "Null pointer value stored to 'p'" but
  2511. // instead "int *p" is noted as
  2512. // "Variable 'p' initialized to a null pointer value"
  2513. static SimpleProgramPointTag tag(TagProviderName, "Location");
  2514. Bldr.generateNode(NodeEx, Pred, state, &tag);
  2515. }
  2516. ExplodedNodeSet Tmp;
  2517. getCheckerManager().runCheckersForLocation(Tmp, Src, location, isLoad,
  2518. NodeEx, BoundEx, *this);
  2519. BldrTop.addNodes(Tmp);
  2520. }
  2521. std::pair<const ProgramPointTag *, const ProgramPointTag*>
  2522. ExprEngine::geteagerlyAssumeBinOpBifurcationTags() {
  2523. static SimpleProgramPointTag
  2524. eagerlyAssumeBinOpBifurcationTrue(TagProviderName,
  2525. "Eagerly Assume True"),
  2526. eagerlyAssumeBinOpBifurcationFalse(TagProviderName,
  2527. "Eagerly Assume False");
  2528. return std::make_pair(&eagerlyAssumeBinOpBifurcationTrue,
  2529. &eagerlyAssumeBinOpBifurcationFalse);
  2530. }
  2531. void ExprEngine::evalEagerlyAssumeBinOpBifurcation(ExplodedNodeSet &Dst,
  2532. ExplodedNodeSet &Src,
  2533. const Expr *Ex) {
  2534. StmtNodeBuilder Bldr(Src, Dst, *currBldrCtx);
  2535. for (const auto Pred : Src) {
  2536. // Test if the previous node was as the same expression. This can happen
  2537. // when the expression fails to evaluate to anything meaningful and
  2538. // (as an optimization) we don't generate a node.
  2539. ProgramPoint P = Pred->getLocation();
  2540. if (!P.getAs<PostStmt>() || P.castAs<PostStmt>().getStmt() != Ex) {
  2541. continue;
  2542. }
  2543. ProgramStateRef state = Pred->getState();
  2544. SVal V = state->getSVal(Ex, Pred->getLocationContext());
  2545. Optional<nonloc::SymbolVal> SEV = V.getAs<nonloc::SymbolVal>();
  2546. if (SEV && SEV->isExpression()) {
  2547. const std::pair<const ProgramPointTag *, const ProgramPointTag*> &tags =
  2548. geteagerlyAssumeBinOpBifurcationTags();
  2549. ProgramStateRef StateTrue, StateFalse;
  2550. std::tie(StateTrue, StateFalse) = state->assume(*SEV);
  2551. // First assume that the condition is true.
  2552. if (StateTrue) {
  2553. SVal Val = svalBuilder.makeIntVal(1U, Ex->getType());
  2554. StateTrue = StateTrue->BindExpr(Ex, Pred->getLocationContext(), Val);
  2555. Bldr.generateNode(Ex, Pred, StateTrue, tags.first);
  2556. }
  2557. // Next, assume that the condition is false.
  2558. if (StateFalse) {
  2559. SVal Val = svalBuilder.makeIntVal(0U, Ex->getType());
  2560. StateFalse = StateFalse->BindExpr(Ex, Pred->getLocationContext(), Val);
  2561. Bldr.generateNode(Ex, Pred, StateFalse, tags.second);
  2562. }
  2563. }
  2564. }
  2565. }
  2566. void ExprEngine::VisitGCCAsmStmt(const GCCAsmStmt *A, ExplodedNode *Pred,
  2567. ExplodedNodeSet &Dst) {
  2568. StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
  2569. // We have processed both the inputs and the outputs. All of the outputs
  2570. // should evaluate to Locs. Nuke all of their values.
  2571. // FIXME: Some day in the future it would be nice to allow a "plug-in"
  2572. // which interprets the inline asm and stores proper results in the
  2573. // outputs.
  2574. ProgramStateRef state = Pred->getState();
  2575. for (const Expr *O : A->outputs()) {
  2576. SVal X = state->getSVal(O, Pred->getLocationContext());
  2577. assert(!X.getAs<NonLoc>()); // Should be an Lval, or unknown, undef.
  2578. if (Optional<Loc> LV = X.getAs<Loc>())
  2579. state = state->bindLoc(*LV, UnknownVal(), Pred->getLocationContext());
  2580. }
  2581. Bldr.generateNode(A, Pred, state);
  2582. }
  2583. void ExprEngine::VisitMSAsmStmt(const MSAsmStmt *A, ExplodedNode *Pred,
  2584. ExplodedNodeSet &Dst) {
  2585. StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
  2586. Bldr.generateNode(A, Pred, Pred->getState());
  2587. }
  2588. //===----------------------------------------------------------------------===//
  2589. // Visualization.
  2590. //===----------------------------------------------------------------------===//
  2591. #ifndef NDEBUG
  2592. namespace llvm {
  2593. template<>
  2594. struct DOTGraphTraits<ExplodedGraph*> : public DefaultDOTGraphTraits {
  2595. DOTGraphTraits (bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
  2596. static bool nodeHasBugReport(const ExplodedNode *N) {
  2597. BugReporter &BR = static_cast<ExprEngine &>(
  2598. N->getState()->getStateManager().getOwningEngine()).getBugReporter();
  2599. const auto EQClasses =
  2600. llvm::make_range(BR.EQClasses_begin(), BR.EQClasses_end());
  2601. for (const auto &EQ : EQClasses) {
  2602. for (const auto &I : EQ.getReports()) {
  2603. const auto *PR = dyn_cast<PathSensitiveBugReport>(I.get());
  2604. if (!PR)
  2605. continue;
  2606. const ExplodedNode *EN = PR->getErrorNode();
  2607. if (EN->getState() == N->getState() &&
  2608. EN->getLocation() == N->getLocation())
  2609. return true;
  2610. }
  2611. }
  2612. return false;
  2613. }
  2614. /// \p PreCallback: callback before break.
  2615. /// \p PostCallback: callback after break.
  2616. /// \p Stop: stop iteration if returns {@code true}
  2617. /// \return Whether {@code Stop} ever returned {@code true}.
  2618. static bool traverseHiddenNodes(
  2619. const ExplodedNode *N,
  2620. llvm::function_ref<void(const ExplodedNode *)> PreCallback,
  2621. llvm::function_ref<void(const ExplodedNode *)> PostCallback,
  2622. llvm::function_ref<bool(const ExplodedNode *)> Stop) {
  2623. while (true) {
  2624. PreCallback(N);
  2625. if (Stop(N))
  2626. return true;
  2627. if (N->succ_size() != 1 || !isNodeHidden(N->getFirstSucc()))
  2628. break;
  2629. PostCallback(N);
  2630. N = N->getFirstSucc();
  2631. }
  2632. return false;
  2633. }
  2634. static bool isNodeHidden(const ExplodedNode *N) {
  2635. return N->isTrivial();
  2636. }
  2637. static std::string getNodeLabel(const ExplodedNode *N, ExplodedGraph *G){
  2638. std::string Buf;
  2639. llvm::raw_string_ostream Out(Buf);
  2640. const bool IsDot = true;
  2641. const unsigned int Space = 1;
  2642. ProgramStateRef State = N->getState();
  2643. Out << "{ \"state_id\": " << State->getID()
  2644. << ",\\l";
  2645. Indent(Out, Space, IsDot) << "\"program_points\": [\\l";
  2646. // Dump program point for all the previously skipped nodes.
  2647. traverseHiddenNodes(
  2648. N,
  2649. [&](const ExplodedNode *OtherNode) {
  2650. Indent(Out, Space + 1, IsDot) << "{ ";
  2651. OtherNode->getLocation().printJson(Out, /*NL=*/"\\l");
  2652. Out << ", \"tag\": ";
  2653. if (const ProgramPointTag *Tag = OtherNode->getLocation().getTag())
  2654. Out << '\"' << Tag->getTagDescription() << "\"";
  2655. else
  2656. Out << "null";
  2657. Out << ", \"node_id\": " << OtherNode->getID() <<
  2658. ", \"is_sink\": " << OtherNode->isSink() <<
  2659. ", \"has_report\": " << nodeHasBugReport(OtherNode) << " }";
  2660. },
  2661. // Adds a comma and a new-line between each program point.
  2662. [&](const ExplodedNode *) { Out << ",\\l"; },
  2663. [&](const ExplodedNode *) { return false; });
  2664. Out << "\\l"; // Adds a new-line to the last program point.
  2665. Indent(Out, Space, IsDot) << "],\\l";
  2666. State->printDOT(Out, N->getLocationContext(), Space);
  2667. Out << "\\l}\\l";
  2668. return Out.str();
  2669. }
  2670. };
  2671. } // namespace llvm
  2672. #endif
  2673. void ExprEngine::ViewGraph(bool trim) {
  2674. #ifndef NDEBUG
  2675. std::string Filename = DumpGraph(trim);
  2676. llvm::DisplayGraph(Filename, false, llvm::GraphProgram::DOT);
  2677. #endif
  2678. llvm::errs() << "Warning: viewing graph requires assertions" << "\n";
  2679. }
  2680. void ExprEngine::ViewGraph(ArrayRef<const ExplodedNode*> Nodes) {
  2681. #ifndef NDEBUG
  2682. std::string Filename = DumpGraph(Nodes);
  2683. llvm::DisplayGraph(Filename, false, llvm::GraphProgram::DOT);
  2684. #endif
  2685. llvm::errs() << "Warning: viewing graph requires assertions" << "\n";
  2686. }
  2687. std::string ExprEngine::DumpGraph(bool trim, StringRef Filename) {
  2688. #ifndef NDEBUG
  2689. if (trim) {
  2690. std::vector<const ExplodedNode *> Src;
  2691. // Iterate through the reports and get their nodes.
  2692. for (BugReporter::EQClasses_iterator
  2693. EI = BR.EQClasses_begin(), EE = BR.EQClasses_end(); EI != EE; ++EI) {
  2694. const auto *R =
  2695. dyn_cast<PathSensitiveBugReport>(EI->getReports()[0].get());
  2696. if (!R)
  2697. continue;
  2698. const auto *N = const_cast<ExplodedNode *>(R->getErrorNode());
  2699. Src.push_back(N);
  2700. }
  2701. return DumpGraph(Src, Filename);
  2702. } else {
  2703. return llvm::WriteGraph(&G, "ExprEngine", /*ShortNames=*/false,
  2704. /*Title=*/"Exploded Graph", /*Filename=*/Filename);
  2705. }
  2706. #endif
  2707. llvm::errs() << "Warning: dumping graph requires assertions" << "\n";
  2708. return "";
  2709. }
  2710. std::string ExprEngine::DumpGraph(ArrayRef<const ExplodedNode*> Nodes,
  2711. StringRef Filename) {
  2712. #ifndef NDEBUG
  2713. std::unique_ptr<ExplodedGraph> TrimmedG(G.trim(Nodes));
  2714. if (!TrimmedG.get()) {
  2715. llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n";
  2716. } else {
  2717. return llvm::WriteGraph(TrimmedG.get(), "TrimmedExprEngine",
  2718. /*ShortNames=*/false,
  2719. /*Title=*/"Trimmed Exploded Graph",
  2720. /*Filename=*/Filename);
  2721. }
  2722. #endif
  2723. llvm::errs() << "Warning: dumping graph requires assertions" << "\n";
  2724. return "";
  2725. }
  2726. void *ProgramStateTrait<ReplayWithoutInlining>::GDMIndex() {
  2727. static int index = 0;
  2728. return &index;
  2729. }