ExprEngine.cpp 117 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463246424652466246724682469247024712472247324742475247624772478247924802481248224832484248524862487248824892490249124922493249424952496249724982499250025012502250325042505250625072508250925102511251225132514251525162517251825192520252125222523252425252526252725282529253025312532253325342535253625372538253925402541254225432544254525462547254825492550255125522553255425552556255725582559256025612562256325642565256625672568256925702571257225732574257525762577257825792580258125822583258425852586258725882589259025912592259325942595259625972598259926002601260226032604260526062607260826092610261126122613261426152616261726182619262026212622262326242625262626272628262926302631263226332634263526362637263826392640264126422643264426452646264726482649265026512652265326542655265626572658265926602661266226632664266526662667266826692670267126722673267426752676267726782679268026812682268326842685268626872688268926902691269226932694269526962697269826992700270127022703270427052706270727082709271027112712271327142715271627172718271927202721272227232724272527262727272827292730273127322733273427352736273727382739274027412742274327442745274627472748274927502751275227532754275527562757275827592760276127622763276427652766276727682769277027712772277327742775277627772778277927802781278227832784278527862787278827892790279127922793279427952796279727982799280028012802280328042805280628072808280928102811281228132814281528162817281828192820282128222823282428252826282728282829283028312832283328342835283628372838283928402841284228432844284528462847284828492850285128522853285428552856285728582859286028612862286328642865286628672868286928702871287228732874287528762877287828792880288128822883288428852886288728882889289028912892289328942895289628972898289929002901290229032904290529062907290829092910291129122913291429152916291729182919292029212922292329242925292629272928292929302931293229332934293529362937293829392940294129422943294429452946294729482949295029512952295329542955295629572958295929602961296229632964296529662967296829692970297129722973297429752976297729782979298029812982298329842985298629872988298929902991299229932994299529962997299829993000300130023003300430053006300730083009301030113012301330143015301630173018301930203021302230233024302530263027302830293030303130323033303430353036303730383039304030413042304330443045304630473048304930503051305230533054305530563057305830593060306130623063306430653066306730683069307030713072307330743075307630773078307930803081308230833084308530863087308830893090309130923093309430953096309730983099310031013102310331043105310631073108310931103111311231133114311531163117311831193120312131223123312431253126312731283129313031313132313331343135313631373138313931403141314231433144314531463147314831493150315131523153315431553156315731583159316031613162316331643165316631673168316931703171317231733174317531763177
  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::OMPDistributeDirectiveClass:
  1115. case Stmt::OMPDistributeParallelForDirectiveClass:
  1116. case Stmt::OMPDistributeParallelForSimdDirectiveClass:
  1117. case Stmt::OMPDistributeSimdDirectiveClass:
  1118. case Stmt::OMPTargetParallelForSimdDirectiveClass:
  1119. case Stmt::OMPTargetSimdDirectiveClass:
  1120. case Stmt::OMPTeamsDistributeDirectiveClass:
  1121. case Stmt::OMPTeamsDistributeSimdDirectiveClass:
  1122. case Stmt::OMPTeamsDistributeParallelForSimdDirectiveClass:
  1123. case Stmt::OMPTeamsDistributeParallelForDirectiveClass:
  1124. case Stmt::OMPTargetTeamsDirectiveClass:
  1125. case Stmt::OMPTargetTeamsDistributeDirectiveClass:
  1126. case Stmt::OMPTargetTeamsDistributeParallelForDirectiveClass:
  1127. case Stmt::OMPTargetTeamsDistributeParallelForSimdDirectiveClass:
  1128. case Stmt::OMPTargetTeamsDistributeSimdDirectiveClass:
  1129. case Stmt::CapturedStmtClass: {
  1130. const ExplodedNode *node = Bldr.generateSink(S, Pred, Pred->getState());
  1131. Engine.addAbortedBlock(node, currBldrCtx->getBlock());
  1132. break;
  1133. }
  1134. case Stmt::ParenExprClass:
  1135. llvm_unreachable("ParenExprs already handled.");
  1136. case Stmt::GenericSelectionExprClass:
  1137. llvm_unreachable("GenericSelectionExprs already handled.");
  1138. // Cases that should never be evaluated simply because they shouldn't
  1139. // appear in the CFG.
  1140. case Stmt::BreakStmtClass:
  1141. case Stmt::CaseStmtClass:
  1142. case Stmt::CompoundStmtClass:
  1143. case Stmt::ContinueStmtClass:
  1144. case Stmt::CXXForRangeStmtClass:
  1145. case Stmt::DefaultStmtClass:
  1146. case Stmt::DoStmtClass:
  1147. case Stmt::ForStmtClass:
  1148. case Stmt::GotoStmtClass:
  1149. case Stmt::IfStmtClass:
  1150. case Stmt::IndirectGotoStmtClass:
  1151. case Stmt::LabelStmtClass:
  1152. case Stmt::NoStmtClass:
  1153. case Stmt::NullStmtClass:
  1154. case Stmt::SwitchStmtClass:
  1155. case Stmt::WhileStmtClass:
  1156. case Expr::MSDependentExistsStmtClass:
  1157. llvm_unreachable("Stmt should not be in analyzer evaluation loop");
  1158. case Stmt::ObjCSubscriptRefExprClass:
  1159. case Stmt::ObjCPropertyRefExprClass:
  1160. llvm_unreachable("These are handled by PseudoObjectExpr");
  1161. case Stmt::GNUNullExprClass: {
  1162. // GNU __null is a pointer-width integer, not an actual pointer.
  1163. ProgramStateRef state = Pred->getState();
  1164. state = state->BindExpr(S, Pred->getLocationContext(),
  1165. svalBuilder.makeIntValWithPtrWidth(0, false));
  1166. Bldr.generateNode(S, Pred, state);
  1167. break;
  1168. }
  1169. case Stmt::ObjCAtSynchronizedStmtClass:
  1170. Bldr.takeNodes(Pred);
  1171. VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S), Pred, Dst);
  1172. Bldr.addNodes(Dst);
  1173. break;
  1174. case Expr::ConstantExprClass:
  1175. case Stmt::ExprWithCleanupsClass:
  1176. // Handled due to fully linearised CFG.
  1177. break;
  1178. case Stmt::CXXBindTemporaryExprClass: {
  1179. Bldr.takeNodes(Pred);
  1180. ExplodedNodeSet PreVisit;
  1181. getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
  1182. ExplodedNodeSet Next;
  1183. VisitCXXBindTemporaryExpr(cast<CXXBindTemporaryExpr>(S), PreVisit, Next);
  1184. getCheckerManager().runCheckersForPostStmt(Dst, Next, S, *this);
  1185. Bldr.addNodes(Dst);
  1186. break;
  1187. }
  1188. // Cases not handled yet; but will handle some day.
  1189. case Stmt::DesignatedInitExprClass:
  1190. case Stmt::DesignatedInitUpdateExprClass:
  1191. case Stmt::ArrayInitLoopExprClass:
  1192. case Stmt::ArrayInitIndexExprClass:
  1193. case Stmt::ExtVectorElementExprClass:
  1194. case Stmt::ImaginaryLiteralClass:
  1195. case Stmt::ObjCAtCatchStmtClass:
  1196. case Stmt::ObjCAtFinallyStmtClass:
  1197. case Stmt::ObjCAtTryStmtClass:
  1198. case Stmt::ObjCAutoreleasePoolStmtClass:
  1199. case Stmt::ObjCEncodeExprClass:
  1200. case Stmt::ObjCIsaExprClass:
  1201. case Stmt::ObjCProtocolExprClass:
  1202. case Stmt::ObjCSelectorExprClass:
  1203. case Stmt::ParenListExprClass:
  1204. case Stmt::ShuffleVectorExprClass:
  1205. case Stmt::ConvertVectorExprClass:
  1206. case Stmt::VAArgExprClass:
  1207. case Stmt::CUDAKernelCallExprClass:
  1208. case Stmt::OpaqueValueExprClass:
  1209. case Stmt::AsTypeExprClass:
  1210. // Fall through.
  1211. // Cases we intentionally don't evaluate, since they don't need
  1212. // to be explicitly evaluated.
  1213. case Stmt::PredefinedExprClass:
  1214. case Stmt::AddrLabelExprClass:
  1215. case Stmt::AttributedStmtClass:
  1216. case Stmt::IntegerLiteralClass:
  1217. case Stmt::FixedPointLiteralClass:
  1218. case Stmt::CharacterLiteralClass:
  1219. case Stmt::ImplicitValueInitExprClass:
  1220. case Stmt::CXXScalarValueInitExprClass:
  1221. case Stmt::CXXBoolLiteralExprClass:
  1222. case Stmt::ObjCBoolLiteralExprClass:
  1223. case Stmt::ObjCAvailabilityCheckExprClass:
  1224. case Stmt::FloatingLiteralClass:
  1225. case Stmt::NoInitExprClass:
  1226. case Stmt::SizeOfPackExprClass:
  1227. case Stmt::StringLiteralClass:
  1228. case Stmt::SourceLocExprClass:
  1229. case Stmt::ObjCStringLiteralClass:
  1230. case Stmt::CXXPseudoDestructorExprClass:
  1231. case Stmt::SubstNonTypeTemplateParmExprClass:
  1232. case Stmt::CXXNullPtrLiteralExprClass:
  1233. case Stmt::OMPArraySectionExprClass:
  1234. case Stmt::TypeTraitExprClass: {
  1235. Bldr.takeNodes(Pred);
  1236. ExplodedNodeSet preVisit;
  1237. getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this);
  1238. getCheckerManager().runCheckersForPostStmt(Dst, preVisit, S, *this);
  1239. Bldr.addNodes(Dst);
  1240. break;
  1241. }
  1242. case Stmt::CXXDefaultArgExprClass:
  1243. case Stmt::CXXDefaultInitExprClass: {
  1244. Bldr.takeNodes(Pred);
  1245. ExplodedNodeSet PreVisit;
  1246. getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
  1247. ExplodedNodeSet Tmp;
  1248. StmtNodeBuilder Bldr2(PreVisit, Tmp, *currBldrCtx);
  1249. const Expr *ArgE;
  1250. if (const auto *DefE = dyn_cast<CXXDefaultArgExpr>(S))
  1251. ArgE = DefE->getExpr();
  1252. else if (const auto *DefE = dyn_cast<CXXDefaultInitExpr>(S))
  1253. ArgE = DefE->getExpr();
  1254. else
  1255. llvm_unreachable("unknown constant wrapper kind");
  1256. bool IsTemporary = false;
  1257. if (const auto *MTE = dyn_cast<MaterializeTemporaryExpr>(ArgE)) {
  1258. ArgE = MTE->GetTemporaryExpr();
  1259. IsTemporary = true;
  1260. }
  1261. Optional<SVal> ConstantVal = svalBuilder.getConstantVal(ArgE);
  1262. if (!ConstantVal)
  1263. ConstantVal = UnknownVal();
  1264. const LocationContext *LCtx = Pred->getLocationContext();
  1265. for (const auto I : PreVisit) {
  1266. ProgramStateRef State = I->getState();
  1267. State = State->BindExpr(S, LCtx, *ConstantVal);
  1268. if (IsTemporary)
  1269. State = createTemporaryRegionIfNeeded(State, LCtx,
  1270. cast<Expr>(S),
  1271. cast<Expr>(S));
  1272. Bldr2.generateNode(S, I, State);
  1273. }
  1274. getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this);
  1275. Bldr.addNodes(Dst);
  1276. break;
  1277. }
  1278. // Cases we evaluate as opaque expressions, conjuring a symbol.
  1279. case Stmt::CXXStdInitializerListExprClass:
  1280. case Expr::ObjCArrayLiteralClass:
  1281. case Expr::ObjCDictionaryLiteralClass:
  1282. case Expr::ObjCBoxedExprClass: {
  1283. Bldr.takeNodes(Pred);
  1284. ExplodedNodeSet preVisit;
  1285. getCheckerManager().runCheckersForPreStmt(preVisit, Pred, S, *this);
  1286. ExplodedNodeSet Tmp;
  1287. StmtNodeBuilder Bldr2(preVisit, Tmp, *currBldrCtx);
  1288. const auto *Ex = cast<Expr>(S);
  1289. QualType resultType = Ex->getType();
  1290. for (const auto N : preVisit) {
  1291. const LocationContext *LCtx = N->getLocationContext();
  1292. SVal result = svalBuilder.conjureSymbolVal(nullptr, Ex, LCtx,
  1293. resultType,
  1294. currBldrCtx->blockCount());
  1295. ProgramStateRef State = N->getState()->BindExpr(Ex, LCtx, result);
  1296. // Escape pointers passed into the list, unless it's an ObjC boxed
  1297. // expression which is not a boxable C structure.
  1298. if (!(isa<ObjCBoxedExpr>(Ex) &&
  1299. !cast<ObjCBoxedExpr>(Ex)->getSubExpr()
  1300. ->getType()->isRecordType()))
  1301. for (auto Child : Ex->children()) {
  1302. assert(Child);
  1303. SVal Val = State->getSVal(Child, LCtx);
  1304. State = escapeValue(State, Val, PSK_EscapeOther);
  1305. }
  1306. Bldr2.generateNode(S, N, State);
  1307. }
  1308. getCheckerManager().runCheckersForPostStmt(Dst, Tmp, S, *this);
  1309. Bldr.addNodes(Dst);
  1310. break;
  1311. }
  1312. case Stmt::ArraySubscriptExprClass:
  1313. Bldr.takeNodes(Pred);
  1314. VisitArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Pred, Dst);
  1315. Bldr.addNodes(Dst);
  1316. break;
  1317. case Stmt::GCCAsmStmtClass:
  1318. Bldr.takeNodes(Pred);
  1319. VisitGCCAsmStmt(cast<GCCAsmStmt>(S), Pred, Dst);
  1320. Bldr.addNodes(Dst);
  1321. break;
  1322. case Stmt::MSAsmStmtClass:
  1323. Bldr.takeNodes(Pred);
  1324. VisitMSAsmStmt(cast<MSAsmStmt>(S), Pred, Dst);
  1325. Bldr.addNodes(Dst);
  1326. break;
  1327. case Stmt::BlockExprClass:
  1328. Bldr.takeNodes(Pred);
  1329. VisitBlockExpr(cast<BlockExpr>(S), Pred, Dst);
  1330. Bldr.addNodes(Dst);
  1331. break;
  1332. case Stmt::LambdaExprClass:
  1333. if (AMgr.options.ShouldInlineLambdas) {
  1334. Bldr.takeNodes(Pred);
  1335. VisitLambdaExpr(cast<LambdaExpr>(S), Pred, Dst);
  1336. Bldr.addNodes(Dst);
  1337. } else {
  1338. const ExplodedNode *node = Bldr.generateSink(S, Pred, Pred->getState());
  1339. Engine.addAbortedBlock(node, currBldrCtx->getBlock());
  1340. }
  1341. break;
  1342. case Stmt::BinaryOperatorClass: {
  1343. const auto *B = cast<BinaryOperator>(S);
  1344. if (B->isLogicalOp()) {
  1345. Bldr.takeNodes(Pred);
  1346. VisitLogicalExpr(B, Pred, Dst);
  1347. Bldr.addNodes(Dst);
  1348. break;
  1349. }
  1350. else if (B->getOpcode() == BO_Comma) {
  1351. ProgramStateRef state = Pred->getState();
  1352. Bldr.generateNode(B, Pred,
  1353. state->BindExpr(B, Pred->getLocationContext(),
  1354. state->getSVal(B->getRHS(),
  1355. Pred->getLocationContext())));
  1356. break;
  1357. }
  1358. Bldr.takeNodes(Pred);
  1359. if (AMgr.options.ShouldEagerlyAssume &&
  1360. (B->isRelationalOp() || B->isEqualityOp())) {
  1361. ExplodedNodeSet Tmp;
  1362. VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Tmp);
  1363. evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, cast<Expr>(S));
  1364. }
  1365. else
  1366. VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
  1367. Bldr.addNodes(Dst);
  1368. break;
  1369. }
  1370. case Stmt::CXXOperatorCallExprClass: {
  1371. const auto *OCE = cast<CXXOperatorCallExpr>(S);
  1372. // For instance method operators, make sure the 'this' argument has a
  1373. // valid region.
  1374. const Decl *Callee = OCE->getCalleeDecl();
  1375. if (const auto *MD = dyn_cast_or_null<CXXMethodDecl>(Callee)) {
  1376. if (MD->isInstance()) {
  1377. ProgramStateRef State = Pred->getState();
  1378. const LocationContext *LCtx = Pred->getLocationContext();
  1379. ProgramStateRef NewState =
  1380. createTemporaryRegionIfNeeded(State, LCtx, OCE->getArg(0));
  1381. if (NewState != State) {
  1382. Pred = Bldr.generateNode(OCE, Pred, NewState, /*tag=*/nullptr,
  1383. ProgramPoint::PreStmtKind);
  1384. // Did we cache out?
  1385. if (!Pred)
  1386. break;
  1387. }
  1388. }
  1389. }
  1390. // FALLTHROUGH
  1391. LLVM_FALLTHROUGH;
  1392. }
  1393. case Stmt::CallExprClass:
  1394. case Stmt::CXXMemberCallExprClass:
  1395. case Stmt::UserDefinedLiteralClass:
  1396. Bldr.takeNodes(Pred);
  1397. VisitCallExpr(cast<CallExpr>(S), Pred, Dst);
  1398. Bldr.addNodes(Dst);
  1399. break;
  1400. case Stmt::CXXCatchStmtClass:
  1401. Bldr.takeNodes(Pred);
  1402. VisitCXXCatchStmt(cast<CXXCatchStmt>(S), Pred, Dst);
  1403. Bldr.addNodes(Dst);
  1404. break;
  1405. case Stmt::CXXTemporaryObjectExprClass:
  1406. case Stmt::CXXConstructExprClass:
  1407. Bldr.takeNodes(Pred);
  1408. VisitCXXConstructExpr(cast<CXXConstructExpr>(S), Pred, Dst);
  1409. Bldr.addNodes(Dst);
  1410. break;
  1411. case Stmt::CXXNewExprClass: {
  1412. Bldr.takeNodes(Pred);
  1413. ExplodedNodeSet PreVisit;
  1414. getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
  1415. ExplodedNodeSet PostVisit;
  1416. for (const auto i : PreVisit)
  1417. VisitCXXNewExpr(cast<CXXNewExpr>(S), i, PostVisit);
  1418. getCheckerManager().runCheckersForPostStmt(Dst, PostVisit, S, *this);
  1419. Bldr.addNodes(Dst);
  1420. break;
  1421. }
  1422. case Stmt::CXXDeleteExprClass: {
  1423. Bldr.takeNodes(Pred);
  1424. ExplodedNodeSet PreVisit;
  1425. const auto *CDE = cast<CXXDeleteExpr>(S);
  1426. getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
  1427. for (const auto i : PreVisit)
  1428. VisitCXXDeleteExpr(CDE, i, Dst);
  1429. Bldr.addNodes(Dst);
  1430. break;
  1431. }
  1432. // FIXME: ChooseExpr is really a constant. We need to fix
  1433. // the CFG do not model them as explicit control-flow.
  1434. case Stmt::ChooseExprClass: { // __builtin_choose_expr
  1435. Bldr.takeNodes(Pred);
  1436. const auto *C = cast<ChooseExpr>(S);
  1437. VisitGuardedExpr(C, C->getLHS(), C->getRHS(), Pred, Dst);
  1438. Bldr.addNodes(Dst);
  1439. break;
  1440. }
  1441. case Stmt::CompoundAssignOperatorClass:
  1442. Bldr.takeNodes(Pred);
  1443. VisitBinaryOperator(cast<BinaryOperator>(S), Pred, Dst);
  1444. Bldr.addNodes(Dst);
  1445. break;
  1446. case Stmt::CompoundLiteralExprClass:
  1447. Bldr.takeNodes(Pred);
  1448. VisitCompoundLiteralExpr(cast<CompoundLiteralExpr>(S), Pred, Dst);
  1449. Bldr.addNodes(Dst);
  1450. break;
  1451. case Stmt::BinaryConditionalOperatorClass:
  1452. case Stmt::ConditionalOperatorClass: { // '?' operator
  1453. Bldr.takeNodes(Pred);
  1454. const auto *C = cast<AbstractConditionalOperator>(S);
  1455. VisitGuardedExpr(C, C->getTrueExpr(), C->getFalseExpr(), Pred, Dst);
  1456. Bldr.addNodes(Dst);
  1457. break;
  1458. }
  1459. case Stmt::CXXThisExprClass:
  1460. Bldr.takeNodes(Pred);
  1461. VisitCXXThisExpr(cast<CXXThisExpr>(S), Pred, Dst);
  1462. Bldr.addNodes(Dst);
  1463. break;
  1464. case Stmt::DeclRefExprClass: {
  1465. Bldr.takeNodes(Pred);
  1466. const auto *DE = cast<DeclRefExpr>(S);
  1467. VisitCommonDeclRefExpr(DE, DE->getDecl(), Pred, Dst);
  1468. Bldr.addNodes(Dst);
  1469. break;
  1470. }
  1471. case Stmt::DeclStmtClass:
  1472. Bldr.takeNodes(Pred);
  1473. VisitDeclStmt(cast<DeclStmt>(S), Pred, Dst);
  1474. Bldr.addNodes(Dst);
  1475. break;
  1476. case Stmt::ImplicitCastExprClass:
  1477. case Stmt::CStyleCastExprClass:
  1478. case Stmt::CXXStaticCastExprClass:
  1479. case Stmt::CXXDynamicCastExprClass:
  1480. case Stmt::CXXReinterpretCastExprClass:
  1481. case Stmt::CXXConstCastExprClass:
  1482. case Stmt::CXXFunctionalCastExprClass:
  1483. case Stmt::BuiltinBitCastExprClass:
  1484. case Stmt::ObjCBridgedCastExprClass: {
  1485. Bldr.takeNodes(Pred);
  1486. const auto *C = cast<CastExpr>(S);
  1487. ExplodedNodeSet dstExpr;
  1488. VisitCast(C, C->getSubExpr(), Pred, dstExpr);
  1489. // Handle the postvisit checks.
  1490. getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, C, *this);
  1491. Bldr.addNodes(Dst);
  1492. break;
  1493. }
  1494. case Expr::MaterializeTemporaryExprClass: {
  1495. Bldr.takeNodes(Pred);
  1496. const auto *MTE = cast<MaterializeTemporaryExpr>(S);
  1497. ExplodedNodeSet dstPrevisit;
  1498. getCheckerManager().runCheckersForPreStmt(dstPrevisit, Pred, MTE, *this);
  1499. ExplodedNodeSet dstExpr;
  1500. for (const auto i : dstPrevisit)
  1501. CreateCXXTemporaryObject(MTE, i, dstExpr);
  1502. getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, MTE, *this);
  1503. Bldr.addNodes(Dst);
  1504. break;
  1505. }
  1506. case Stmt::InitListExprClass:
  1507. Bldr.takeNodes(Pred);
  1508. VisitInitListExpr(cast<InitListExpr>(S), Pred, Dst);
  1509. Bldr.addNodes(Dst);
  1510. break;
  1511. case Stmt::MemberExprClass:
  1512. Bldr.takeNodes(Pred);
  1513. VisitMemberExpr(cast<MemberExpr>(S), Pred, Dst);
  1514. Bldr.addNodes(Dst);
  1515. break;
  1516. case Stmt::AtomicExprClass:
  1517. Bldr.takeNodes(Pred);
  1518. VisitAtomicExpr(cast<AtomicExpr>(S), Pred, Dst);
  1519. Bldr.addNodes(Dst);
  1520. break;
  1521. case Stmt::ObjCIvarRefExprClass:
  1522. Bldr.takeNodes(Pred);
  1523. VisitLvalObjCIvarRefExpr(cast<ObjCIvarRefExpr>(S), Pred, Dst);
  1524. Bldr.addNodes(Dst);
  1525. break;
  1526. case Stmt::ObjCForCollectionStmtClass:
  1527. Bldr.takeNodes(Pred);
  1528. VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S), Pred, Dst);
  1529. Bldr.addNodes(Dst);
  1530. break;
  1531. case Stmt::ObjCMessageExprClass:
  1532. Bldr.takeNodes(Pred);
  1533. VisitObjCMessage(cast<ObjCMessageExpr>(S), Pred, Dst);
  1534. Bldr.addNodes(Dst);
  1535. break;
  1536. case Stmt::ObjCAtThrowStmtClass:
  1537. case Stmt::CXXThrowExprClass:
  1538. // FIXME: This is not complete. We basically treat @throw as
  1539. // an abort.
  1540. Bldr.generateSink(S, Pred, Pred->getState());
  1541. break;
  1542. case Stmt::ReturnStmtClass:
  1543. Bldr.takeNodes(Pred);
  1544. VisitReturnStmt(cast<ReturnStmt>(S), Pred, Dst);
  1545. Bldr.addNodes(Dst);
  1546. break;
  1547. case Stmt::OffsetOfExprClass: {
  1548. Bldr.takeNodes(Pred);
  1549. ExplodedNodeSet PreVisit;
  1550. getCheckerManager().runCheckersForPreStmt(PreVisit, Pred, S, *this);
  1551. ExplodedNodeSet PostVisit;
  1552. for (const auto Node : PreVisit)
  1553. VisitOffsetOfExpr(cast<OffsetOfExpr>(S), Node, PostVisit);
  1554. getCheckerManager().runCheckersForPostStmt(Dst, PostVisit, S, *this);
  1555. Bldr.addNodes(Dst);
  1556. break;
  1557. }
  1558. case Stmt::UnaryExprOrTypeTraitExprClass:
  1559. Bldr.takeNodes(Pred);
  1560. VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S),
  1561. Pred, Dst);
  1562. Bldr.addNodes(Dst);
  1563. break;
  1564. case Stmt::StmtExprClass: {
  1565. const auto *SE = cast<StmtExpr>(S);
  1566. if (SE->getSubStmt()->body_empty()) {
  1567. // Empty statement expression.
  1568. assert(SE->getType() == getContext().VoidTy
  1569. && "Empty statement expression must have void type.");
  1570. break;
  1571. }
  1572. if (const auto *LastExpr =
  1573. dyn_cast<Expr>(*SE->getSubStmt()->body_rbegin())) {
  1574. ProgramStateRef state = Pred->getState();
  1575. Bldr.generateNode(SE, Pred,
  1576. state->BindExpr(SE, Pred->getLocationContext(),
  1577. state->getSVal(LastExpr,
  1578. Pred->getLocationContext())));
  1579. }
  1580. break;
  1581. }
  1582. case Stmt::UnaryOperatorClass: {
  1583. Bldr.takeNodes(Pred);
  1584. const auto *U = cast<UnaryOperator>(S);
  1585. if (AMgr.options.ShouldEagerlyAssume && (U->getOpcode() == UO_LNot)) {
  1586. ExplodedNodeSet Tmp;
  1587. VisitUnaryOperator(U, Pred, Tmp);
  1588. evalEagerlyAssumeBinOpBifurcation(Dst, Tmp, U);
  1589. }
  1590. else
  1591. VisitUnaryOperator(U, Pred, Dst);
  1592. Bldr.addNodes(Dst);
  1593. break;
  1594. }
  1595. case Stmt::PseudoObjectExprClass: {
  1596. Bldr.takeNodes(Pred);
  1597. ProgramStateRef state = Pred->getState();
  1598. const auto *PE = cast<PseudoObjectExpr>(S);
  1599. if (const Expr *Result = PE->getResultExpr()) {
  1600. SVal V = state->getSVal(Result, Pred->getLocationContext());
  1601. Bldr.generateNode(S, Pred,
  1602. state->BindExpr(S, Pred->getLocationContext(), V));
  1603. }
  1604. else
  1605. Bldr.generateNode(S, Pred,
  1606. state->BindExpr(S, Pred->getLocationContext(),
  1607. UnknownVal()));
  1608. Bldr.addNodes(Dst);
  1609. break;
  1610. }
  1611. }
  1612. }
  1613. bool ExprEngine::replayWithoutInlining(ExplodedNode *N,
  1614. const LocationContext *CalleeLC) {
  1615. const StackFrameContext *CalleeSF = CalleeLC->getStackFrame();
  1616. const StackFrameContext *CallerSF = CalleeSF->getParent()->getStackFrame();
  1617. assert(CalleeSF && CallerSF);
  1618. ExplodedNode *BeforeProcessingCall = nullptr;
  1619. const Stmt *CE = CalleeSF->getCallSite();
  1620. // Find the first node before we started processing the call expression.
  1621. while (N) {
  1622. ProgramPoint L = N->getLocation();
  1623. BeforeProcessingCall = N;
  1624. N = N->pred_empty() ? nullptr : *(N->pred_begin());
  1625. // Skip the nodes corresponding to the inlined code.
  1626. if (L.getStackFrame() != CallerSF)
  1627. continue;
  1628. // We reached the caller. Find the node right before we started
  1629. // processing the call.
  1630. if (L.isPurgeKind())
  1631. continue;
  1632. if (L.getAs<PreImplicitCall>())
  1633. continue;
  1634. if (L.getAs<CallEnter>())
  1635. continue;
  1636. if (Optional<StmtPoint> SP = L.getAs<StmtPoint>())
  1637. if (SP->getStmt() == CE)
  1638. continue;
  1639. break;
  1640. }
  1641. if (!BeforeProcessingCall)
  1642. return false;
  1643. // TODO: Clean up the unneeded nodes.
  1644. // Build an Epsilon node from which we will restart the analyzes.
  1645. // Note that CE is permitted to be NULL!
  1646. ProgramPoint NewNodeLoc =
  1647. EpsilonPoint(BeforeProcessingCall->getLocationContext(), CE);
  1648. // Add the special flag to GDM to signal retrying with no inlining.
  1649. // Note, changing the state ensures that we are not going to cache out.
  1650. ProgramStateRef NewNodeState = BeforeProcessingCall->getState();
  1651. NewNodeState =
  1652. NewNodeState->set<ReplayWithoutInlining>(const_cast<Stmt *>(CE));
  1653. // Make the new node a successor of BeforeProcessingCall.
  1654. bool IsNew = false;
  1655. ExplodedNode *NewNode = G.getNode(NewNodeLoc, NewNodeState, false, &IsNew);
  1656. // We cached out at this point. Caching out is common due to us backtracking
  1657. // from the inlined function, which might spawn several paths.
  1658. if (!IsNew)
  1659. return true;
  1660. NewNode->addPredecessor(BeforeProcessingCall, G);
  1661. // Add the new node to the work list.
  1662. Engine.enqueueStmtNode(NewNode, CalleeSF->getCallSiteBlock(),
  1663. CalleeSF->getIndex());
  1664. NumTimesRetriedWithoutInlining++;
  1665. return true;
  1666. }
  1667. /// Block entrance. (Update counters).
  1668. void ExprEngine::processCFGBlockEntrance(const BlockEdge &L,
  1669. NodeBuilderWithSinks &nodeBuilder,
  1670. ExplodedNode *Pred) {
  1671. PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
  1672. // If we reach a loop which has a known bound (and meets
  1673. // other constraints) then consider completely unrolling it.
  1674. if(AMgr.options.ShouldUnrollLoops) {
  1675. unsigned maxBlockVisitOnPath = AMgr.options.maxBlockVisitOnPath;
  1676. const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminatorStmt();
  1677. if (Term) {
  1678. ProgramStateRef NewState = updateLoopStack(Term, AMgr.getASTContext(),
  1679. Pred, maxBlockVisitOnPath);
  1680. if (NewState != Pred->getState()) {
  1681. ExplodedNode *UpdatedNode = nodeBuilder.generateNode(NewState, Pred);
  1682. if (!UpdatedNode)
  1683. return;
  1684. Pred = UpdatedNode;
  1685. }
  1686. }
  1687. // Is we are inside an unrolled loop then no need the check the counters.
  1688. if(isUnrolledState(Pred->getState()))
  1689. return;
  1690. }
  1691. // If this block is terminated by a loop and it has already been visited the
  1692. // maximum number of times, widen the loop.
  1693. unsigned int BlockCount = nodeBuilder.getContext().blockCount();
  1694. if (BlockCount == AMgr.options.maxBlockVisitOnPath - 1 &&
  1695. AMgr.options.ShouldWidenLoops) {
  1696. const Stmt *Term = nodeBuilder.getContext().getBlock()->getTerminatorStmt();
  1697. if (!(Term &&
  1698. (isa<ForStmt>(Term) || isa<WhileStmt>(Term) || isa<DoStmt>(Term))))
  1699. return;
  1700. // Widen.
  1701. const LocationContext *LCtx = Pred->getLocationContext();
  1702. ProgramStateRef WidenedState =
  1703. getWidenedLoopState(Pred->getState(), LCtx, BlockCount, Term);
  1704. nodeBuilder.generateNode(WidenedState, Pred);
  1705. return;
  1706. }
  1707. // FIXME: Refactor this into a checker.
  1708. if (BlockCount >= AMgr.options.maxBlockVisitOnPath) {
  1709. static SimpleProgramPointTag tag(TagProviderName, "Block count exceeded");
  1710. const ExplodedNode *Sink =
  1711. nodeBuilder.generateSink(Pred->getState(), Pred, &tag);
  1712. // Check if we stopped at the top level function or not.
  1713. // Root node should have the location context of the top most function.
  1714. const LocationContext *CalleeLC = Pred->getLocation().getLocationContext();
  1715. const LocationContext *CalleeSF = CalleeLC->getStackFrame();
  1716. const LocationContext *RootLC =
  1717. (*G.roots_begin())->getLocation().getLocationContext();
  1718. if (RootLC->getStackFrame() != CalleeSF) {
  1719. Engine.FunctionSummaries->markReachedMaxBlockCount(CalleeSF->getDecl());
  1720. // Re-run the call evaluation without inlining it, by storing the
  1721. // no-inlining policy in the state and enqueuing the new work item on
  1722. // the list. Replay should almost never fail. Use the stats to catch it
  1723. // if it does.
  1724. if ((!AMgr.options.NoRetryExhausted &&
  1725. replayWithoutInlining(Pred, CalleeLC)))
  1726. return;
  1727. NumMaxBlockCountReachedInInlined++;
  1728. } else
  1729. NumMaxBlockCountReached++;
  1730. // Make sink nodes as exhausted(for stats) only if retry failed.
  1731. Engine.blocksExhausted.push_back(std::make_pair(L, Sink));
  1732. }
  1733. }
  1734. //===----------------------------------------------------------------------===//
  1735. // Branch processing.
  1736. //===----------------------------------------------------------------------===//
  1737. /// RecoverCastedSymbol - A helper function for ProcessBranch that is used
  1738. /// to try to recover some path-sensitivity for casts of symbolic
  1739. /// integers that promote their values (which are currently not tracked well).
  1740. /// This function returns the SVal bound to Condition->IgnoreCasts if all the
  1741. // cast(s) did was sign-extend the original value.
  1742. static SVal RecoverCastedSymbol(ProgramStateRef state,
  1743. const Stmt *Condition,
  1744. const LocationContext *LCtx,
  1745. ASTContext &Ctx) {
  1746. const auto *Ex = dyn_cast<Expr>(Condition);
  1747. if (!Ex)
  1748. return UnknownVal();
  1749. uint64_t bits = 0;
  1750. bool bitsInit = false;
  1751. while (const auto *CE = dyn_cast<CastExpr>(Ex)) {
  1752. QualType T = CE->getType();
  1753. if (!T->isIntegralOrEnumerationType())
  1754. return UnknownVal();
  1755. uint64_t newBits = Ctx.getTypeSize(T);
  1756. if (!bitsInit || newBits < bits) {
  1757. bitsInit = true;
  1758. bits = newBits;
  1759. }
  1760. Ex = CE->getSubExpr();
  1761. }
  1762. // We reached a non-cast. Is it a symbolic value?
  1763. QualType T = Ex->getType();
  1764. if (!bitsInit || !T->isIntegralOrEnumerationType() ||
  1765. Ctx.getTypeSize(T) > bits)
  1766. return UnknownVal();
  1767. return state->getSVal(Ex, LCtx);
  1768. }
  1769. #ifndef NDEBUG
  1770. static const Stmt *getRightmostLeaf(const Stmt *Condition) {
  1771. while (Condition) {
  1772. const auto *BO = dyn_cast<BinaryOperator>(Condition);
  1773. if (!BO || !BO->isLogicalOp()) {
  1774. return Condition;
  1775. }
  1776. Condition = BO->getRHS()->IgnoreParens();
  1777. }
  1778. return nullptr;
  1779. }
  1780. #endif
  1781. // Returns the condition the branch at the end of 'B' depends on and whose value
  1782. // has been evaluated within 'B'.
  1783. // In most cases, the terminator condition of 'B' will be evaluated fully in
  1784. // the last statement of 'B'; in those cases, the resolved condition is the
  1785. // given 'Condition'.
  1786. // If the condition of the branch is a logical binary operator tree, the CFG is
  1787. // optimized: in that case, we know that the expression formed by all but the
  1788. // rightmost leaf of the logical binary operator tree must be true, and thus
  1789. // the branch condition is at this point equivalent to the truth value of that
  1790. // rightmost leaf; the CFG block thus only evaluates this rightmost leaf
  1791. // expression in its final statement. As the full condition in that case was
  1792. // not evaluated, and is thus not in the SVal cache, we need to use that leaf
  1793. // expression to evaluate the truth value of the condition in the current state
  1794. // space.
  1795. static const Stmt *ResolveCondition(const Stmt *Condition,
  1796. const CFGBlock *B) {
  1797. if (const auto *Ex = dyn_cast<Expr>(Condition))
  1798. Condition = Ex->IgnoreParens();
  1799. const auto *BO = dyn_cast<BinaryOperator>(Condition);
  1800. if (!BO || !BO->isLogicalOp())
  1801. return Condition;
  1802. assert(B->getTerminator().isStmtBranch() &&
  1803. "Other kinds of branches are handled separately!");
  1804. // For logical operations, we still have the case where some branches
  1805. // use the traditional "merge" approach and others sink the branch
  1806. // directly into the basic blocks representing the logical operation.
  1807. // We need to distinguish between those two cases here.
  1808. // The invariants are still shifting, but it is possible that the
  1809. // last element in a CFGBlock is not a CFGStmt. Look for the last
  1810. // CFGStmt as the value of the condition.
  1811. CFGBlock::const_reverse_iterator I = B->rbegin(), E = B->rend();
  1812. for (; I != E; ++I) {
  1813. CFGElement Elem = *I;
  1814. Optional<CFGStmt> CS = Elem.getAs<CFGStmt>();
  1815. if (!CS)
  1816. continue;
  1817. const Stmt *LastStmt = CS->getStmt();
  1818. assert(LastStmt == Condition || LastStmt == getRightmostLeaf(Condition));
  1819. return LastStmt;
  1820. }
  1821. llvm_unreachable("could not resolve condition");
  1822. }
  1823. void ExprEngine::processBranch(const Stmt *Condition,
  1824. NodeBuilderContext& BldCtx,
  1825. ExplodedNode *Pred,
  1826. ExplodedNodeSet &Dst,
  1827. const CFGBlock *DstT,
  1828. const CFGBlock *DstF) {
  1829. assert((!Condition || !isa<CXXBindTemporaryExpr>(Condition)) &&
  1830. "CXXBindTemporaryExprs are handled by processBindTemporary.");
  1831. const LocationContext *LCtx = Pred->getLocationContext();
  1832. PrettyStackTraceLocationContext StackCrashInfo(LCtx);
  1833. currBldrCtx = &BldCtx;
  1834. // Check for NULL conditions; e.g. "for(;;)"
  1835. if (!Condition) {
  1836. BranchNodeBuilder NullCondBldr(Pred, Dst, BldCtx, DstT, DstF);
  1837. NullCondBldr.markInfeasible(false);
  1838. NullCondBldr.generateNode(Pred->getState(), true, Pred);
  1839. return;
  1840. }
  1841. if (const auto *Ex = dyn_cast<Expr>(Condition))
  1842. Condition = Ex->IgnoreParens();
  1843. Condition = ResolveCondition(Condition, BldCtx.getBlock());
  1844. PrettyStackTraceLoc CrashInfo(getContext().getSourceManager(),
  1845. Condition->getBeginLoc(),
  1846. "Error evaluating branch");
  1847. ExplodedNodeSet CheckersOutSet;
  1848. getCheckerManager().runCheckersForBranchCondition(Condition, CheckersOutSet,
  1849. Pred, *this);
  1850. // We generated only sinks.
  1851. if (CheckersOutSet.empty())
  1852. return;
  1853. BranchNodeBuilder builder(CheckersOutSet, Dst, BldCtx, DstT, DstF);
  1854. for (const auto PredI : CheckersOutSet) {
  1855. if (PredI->isSink())
  1856. continue;
  1857. ProgramStateRef PrevState = PredI->getState();
  1858. SVal X = PrevState->getSVal(Condition, PredI->getLocationContext());
  1859. if (X.isUnknownOrUndef()) {
  1860. // Give it a chance to recover from unknown.
  1861. if (const auto *Ex = dyn_cast<Expr>(Condition)) {
  1862. if (Ex->getType()->isIntegralOrEnumerationType()) {
  1863. // Try to recover some path-sensitivity. Right now casts of symbolic
  1864. // integers that promote their values are currently not tracked well.
  1865. // If 'Condition' is such an expression, try and recover the
  1866. // underlying value and use that instead.
  1867. SVal recovered = RecoverCastedSymbol(PrevState, Condition,
  1868. PredI->getLocationContext(),
  1869. getContext());
  1870. if (!recovered.isUnknown()) {
  1871. X = recovered;
  1872. }
  1873. }
  1874. }
  1875. }
  1876. // If the condition is still unknown, give up.
  1877. if (X.isUnknownOrUndef()) {
  1878. builder.generateNode(PrevState, true, PredI);
  1879. builder.generateNode(PrevState, false, PredI);
  1880. continue;
  1881. }
  1882. DefinedSVal V = X.castAs<DefinedSVal>();
  1883. ProgramStateRef StTrue, StFalse;
  1884. std::tie(StTrue, StFalse) = PrevState->assume(V);
  1885. // Process the true branch.
  1886. if (builder.isFeasible(true)) {
  1887. if (StTrue)
  1888. builder.generateNode(StTrue, true, PredI);
  1889. else
  1890. builder.markInfeasible(true);
  1891. }
  1892. // Process the false branch.
  1893. if (builder.isFeasible(false)) {
  1894. if (StFalse)
  1895. builder.generateNode(StFalse, false, PredI);
  1896. else
  1897. builder.markInfeasible(false);
  1898. }
  1899. }
  1900. currBldrCtx = nullptr;
  1901. }
  1902. /// The GDM component containing the set of global variables which have been
  1903. /// previously initialized with explicit initializers.
  1904. REGISTER_TRAIT_WITH_PROGRAMSTATE(InitializedGlobalsSet,
  1905. llvm::ImmutableSet<const VarDecl *>)
  1906. void ExprEngine::processStaticInitializer(const DeclStmt *DS,
  1907. NodeBuilderContext &BuilderCtx,
  1908. ExplodedNode *Pred,
  1909. ExplodedNodeSet &Dst,
  1910. const CFGBlock *DstT,
  1911. const CFGBlock *DstF) {
  1912. PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
  1913. currBldrCtx = &BuilderCtx;
  1914. const auto *VD = cast<VarDecl>(DS->getSingleDecl());
  1915. ProgramStateRef state = Pred->getState();
  1916. bool initHasRun = state->contains<InitializedGlobalsSet>(VD);
  1917. BranchNodeBuilder builder(Pred, Dst, BuilderCtx, DstT, DstF);
  1918. if (!initHasRun) {
  1919. state = state->add<InitializedGlobalsSet>(VD);
  1920. }
  1921. builder.generateNode(state, initHasRun, Pred);
  1922. builder.markInfeasible(!initHasRun);
  1923. currBldrCtx = nullptr;
  1924. }
  1925. /// processIndirectGoto - Called by CoreEngine. Used to generate successor
  1926. /// nodes by processing the 'effects' of a computed goto jump.
  1927. void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) {
  1928. ProgramStateRef state = builder.getState();
  1929. SVal V = state->getSVal(builder.getTarget(), builder.getLocationContext());
  1930. // Three possibilities:
  1931. //
  1932. // (1) We know the computed label.
  1933. // (2) The label is NULL (or some other constant), or Undefined.
  1934. // (3) We have no clue about the label. Dispatch to all targets.
  1935. //
  1936. using iterator = IndirectGotoNodeBuilder::iterator;
  1937. if (Optional<loc::GotoLabel> LV = V.getAs<loc::GotoLabel>()) {
  1938. const LabelDecl *L = LV->getLabel();
  1939. for (iterator I = builder.begin(), E = builder.end(); I != E; ++I) {
  1940. if (I.getLabel() == L) {
  1941. builder.generateNode(I, state);
  1942. return;
  1943. }
  1944. }
  1945. llvm_unreachable("No block with label.");
  1946. }
  1947. if (V.getAs<loc::ConcreteInt>() || V.getAs<UndefinedVal>()) {
  1948. // Dispatch to the first target and mark it as a sink.
  1949. //ExplodedNode* N = builder.generateNode(builder.begin(), state, true);
  1950. // FIXME: add checker visit.
  1951. // UndefBranches.insert(N);
  1952. return;
  1953. }
  1954. // This is really a catch-all. We don't support symbolics yet.
  1955. // FIXME: Implement dispatch for symbolic pointers.
  1956. for (iterator I = builder.begin(), E = builder.end(); I != E; ++I)
  1957. builder.generateNode(I, state);
  1958. }
  1959. void ExprEngine::processBeginOfFunction(NodeBuilderContext &BC,
  1960. ExplodedNode *Pred,
  1961. ExplodedNodeSet &Dst,
  1962. const BlockEdge &L) {
  1963. SaveAndRestore<const NodeBuilderContext *> NodeContextRAII(currBldrCtx, &BC);
  1964. getCheckerManager().runCheckersForBeginFunction(Dst, L, Pred, *this);
  1965. }
  1966. /// ProcessEndPath - Called by CoreEngine. Used to generate end-of-path
  1967. /// nodes when the control reaches the end of a function.
  1968. void ExprEngine::processEndOfFunction(NodeBuilderContext& BC,
  1969. ExplodedNode *Pred,
  1970. const ReturnStmt *RS) {
  1971. ProgramStateRef State = Pred->getState();
  1972. if (!Pred->getStackFrame()->inTopFrame())
  1973. State = finishArgumentConstruction(
  1974. State, *getStateManager().getCallEventManager().getCaller(
  1975. Pred->getStackFrame(), Pred->getState()));
  1976. // FIXME: We currently cannot assert that temporaries are clear, because
  1977. // lifetime extended temporaries are not always modelled correctly. In some
  1978. // cases when we materialize the temporary, we do
  1979. // createTemporaryRegionIfNeeded(), and the region changes, and also the
  1980. // respective destructor becomes automatic from temporary. So for now clean up
  1981. // the state manually before asserting. Ideally, this braced block of code
  1982. // should go away.
  1983. {
  1984. const LocationContext *FromLC = Pred->getLocationContext();
  1985. const LocationContext *ToLC = FromLC->getStackFrame()->getParent();
  1986. const LocationContext *LC = FromLC;
  1987. while (LC != ToLC) {
  1988. assert(LC && "ToLC must be a parent of FromLC!");
  1989. for (auto I : State->get<ObjectsUnderConstruction>())
  1990. if (I.first.getLocationContext() == LC) {
  1991. // The comment above only pardons us for not cleaning up a
  1992. // temporary destructor. If any other statements are found here,
  1993. // it must be a separate problem.
  1994. assert(I.first.getItem().getKind() ==
  1995. ConstructionContextItem::TemporaryDestructorKind ||
  1996. I.first.getItem().getKind() ==
  1997. ConstructionContextItem::ElidedDestructorKind);
  1998. State = State->remove<ObjectsUnderConstruction>(I.first);
  1999. }
  2000. LC = LC->getParent();
  2001. }
  2002. }
  2003. // Perform the transition with cleanups.
  2004. if (State != Pred->getState()) {
  2005. ExplodedNodeSet PostCleanup;
  2006. NodeBuilder Bldr(Pred, PostCleanup, BC);
  2007. Pred = Bldr.generateNode(Pred->getLocation(), State, Pred);
  2008. if (!Pred) {
  2009. // The node with clean temporaries already exists. We might have reached
  2010. // it on a path on which we initialize different temporaries.
  2011. return;
  2012. }
  2013. }
  2014. assert(areAllObjectsFullyConstructed(Pred->getState(),
  2015. Pred->getLocationContext(),
  2016. Pred->getStackFrame()->getParent()));
  2017. PrettyStackTraceLocationContext CrashInfo(Pred->getLocationContext());
  2018. ExplodedNodeSet Dst;
  2019. if (Pred->getLocationContext()->inTopFrame()) {
  2020. // Remove dead symbols.
  2021. ExplodedNodeSet AfterRemovedDead;
  2022. removeDeadOnEndOfFunction(BC, Pred, AfterRemovedDead);
  2023. // Notify checkers.
  2024. for (const auto I : AfterRemovedDead)
  2025. getCheckerManager().runCheckersForEndFunction(BC, Dst, I, *this, RS);
  2026. } else {
  2027. getCheckerManager().runCheckersForEndFunction(BC, Dst, Pred, *this, RS);
  2028. }
  2029. Engine.enqueueEndOfFunction(Dst, RS);
  2030. }
  2031. /// ProcessSwitch - Called by CoreEngine. Used to generate successor
  2032. /// nodes by processing the 'effects' of a switch statement.
  2033. void ExprEngine::processSwitch(SwitchNodeBuilder& builder) {
  2034. using iterator = SwitchNodeBuilder::iterator;
  2035. ProgramStateRef state = builder.getState();
  2036. const Expr *CondE = builder.getCondition();
  2037. SVal CondV_untested = state->getSVal(CondE, builder.getLocationContext());
  2038. if (CondV_untested.isUndef()) {
  2039. //ExplodedNode* N = builder.generateDefaultCaseNode(state, true);
  2040. // FIXME: add checker
  2041. //UndefBranches.insert(N);
  2042. return;
  2043. }
  2044. DefinedOrUnknownSVal CondV = CondV_untested.castAs<DefinedOrUnknownSVal>();
  2045. ProgramStateRef DefaultSt = state;
  2046. iterator I = builder.begin(), EI = builder.end();
  2047. bool defaultIsFeasible = I == EI;
  2048. for ( ; I != EI; ++I) {
  2049. // Successor may be pruned out during CFG construction.
  2050. if (!I.getBlock())
  2051. continue;
  2052. const CaseStmt *Case = I.getCase();
  2053. // Evaluate the LHS of the case value.
  2054. llvm::APSInt V1 = Case->getLHS()->EvaluateKnownConstInt(getContext());
  2055. assert(V1.getBitWidth() == getContext().getIntWidth(CondE->getType()));
  2056. // Get the RHS of the case, if it exists.
  2057. llvm::APSInt V2;
  2058. if (const Expr *E = Case->getRHS())
  2059. V2 = E->EvaluateKnownConstInt(getContext());
  2060. else
  2061. V2 = V1;
  2062. ProgramStateRef StateCase;
  2063. if (Optional<NonLoc> NL = CondV.getAs<NonLoc>())
  2064. std::tie(StateCase, DefaultSt) =
  2065. DefaultSt->assumeInclusiveRange(*NL, V1, V2);
  2066. else // UnknownVal
  2067. StateCase = DefaultSt;
  2068. if (StateCase)
  2069. builder.generateCaseStmtNode(I, StateCase);
  2070. // Now "assume" that the case doesn't match. Add this state
  2071. // to the default state (if it is feasible).
  2072. if (DefaultSt)
  2073. defaultIsFeasible = true;
  2074. else {
  2075. defaultIsFeasible = false;
  2076. break;
  2077. }
  2078. }
  2079. if (!defaultIsFeasible)
  2080. return;
  2081. // If we have switch(enum value), the default branch is not
  2082. // feasible if all of the enum constants not covered by 'case:' statements
  2083. // are not feasible values for the switch condition.
  2084. //
  2085. // Note that this isn't as accurate as it could be. Even if there isn't
  2086. // a case for a particular enum value as long as that enum value isn't
  2087. // feasible then it shouldn't be considered for making 'default:' reachable.
  2088. const SwitchStmt *SS = builder.getSwitch();
  2089. const Expr *CondExpr = SS->getCond()->IgnoreParenImpCasts();
  2090. if (CondExpr->getType()->getAs<EnumType>()) {
  2091. if (SS->isAllEnumCasesCovered())
  2092. return;
  2093. }
  2094. builder.generateDefaultCaseNode(DefaultSt);
  2095. }
  2096. //===----------------------------------------------------------------------===//
  2097. // Transfer functions: Loads and stores.
  2098. //===----------------------------------------------------------------------===//
  2099. void ExprEngine::VisitCommonDeclRefExpr(const Expr *Ex, const NamedDecl *D,
  2100. ExplodedNode *Pred,
  2101. ExplodedNodeSet &Dst) {
  2102. StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
  2103. ProgramStateRef state = Pred->getState();
  2104. const LocationContext *LCtx = Pred->getLocationContext();
  2105. if (const auto *VD = dyn_cast<VarDecl>(D)) {
  2106. // C permits "extern void v", and if you cast the address to a valid type,
  2107. // you can even do things with it. We simply pretend
  2108. assert(Ex->isGLValue() || VD->getType()->isVoidType());
  2109. const LocationContext *LocCtxt = Pred->getLocationContext();
  2110. const Decl *D = LocCtxt->getDecl();
  2111. const auto *MD = dyn_cast_or_null<CXXMethodDecl>(D);
  2112. const auto *DeclRefEx = dyn_cast<DeclRefExpr>(Ex);
  2113. Optional<std::pair<SVal, QualType>> VInfo;
  2114. if (AMgr.options.ShouldInlineLambdas && DeclRefEx &&
  2115. DeclRefEx->refersToEnclosingVariableOrCapture() && MD &&
  2116. MD->getParent()->isLambda()) {
  2117. // Lookup the field of the lambda.
  2118. const CXXRecordDecl *CXXRec = MD->getParent();
  2119. llvm::DenseMap<const VarDecl *, FieldDecl *> LambdaCaptureFields;
  2120. FieldDecl *LambdaThisCaptureField;
  2121. CXXRec->getCaptureFields(LambdaCaptureFields, LambdaThisCaptureField);
  2122. // Sema follows a sequence of complex rules to determine whether the
  2123. // variable should be captured.
  2124. if (const FieldDecl *FD = LambdaCaptureFields[VD]) {
  2125. Loc CXXThis =
  2126. svalBuilder.getCXXThis(MD, LocCtxt->getStackFrame());
  2127. SVal CXXThisVal = state->getSVal(CXXThis);
  2128. VInfo = std::make_pair(state->getLValue(FD, CXXThisVal), FD->getType());
  2129. }
  2130. }
  2131. if (!VInfo)
  2132. VInfo = std::make_pair(state->getLValue(VD, LocCtxt), VD->getType());
  2133. SVal V = VInfo->first;
  2134. bool IsReference = VInfo->second->isReferenceType();
  2135. // For references, the 'lvalue' is the pointer address stored in the
  2136. // reference region.
  2137. if (IsReference) {
  2138. if (const MemRegion *R = V.getAsRegion())
  2139. V = state->getSVal(R);
  2140. else
  2141. V = UnknownVal();
  2142. }
  2143. Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr,
  2144. ProgramPoint::PostLValueKind);
  2145. return;
  2146. }
  2147. if (const auto *ED = dyn_cast<EnumConstantDecl>(D)) {
  2148. assert(!Ex->isGLValue());
  2149. SVal V = svalBuilder.makeIntVal(ED->getInitVal());
  2150. Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V));
  2151. return;
  2152. }
  2153. if (const auto *FD = dyn_cast<FunctionDecl>(D)) {
  2154. SVal V = svalBuilder.getFunctionPointer(FD);
  2155. Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr,
  2156. ProgramPoint::PostLValueKind);
  2157. return;
  2158. }
  2159. if (isa<FieldDecl>(D) || isa<IndirectFieldDecl>(D)) {
  2160. // FIXME: Compute lvalue of field pointers-to-member.
  2161. // Right now we just use a non-null void pointer, so that it gives proper
  2162. // results in boolean contexts.
  2163. // FIXME: Maybe delegate this to the surrounding operator&.
  2164. // Note how this expression is lvalue, however pointer-to-member is NonLoc.
  2165. SVal V = svalBuilder.conjureSymbolVal(Ex, LCtx, getContext().VoidPtrTy,
  2166. currBldrCtx->blockCount());
  2167. state = state->assume(V.castAs<DefinedOrUnknownSVal>(), true);
  2168. Bldr.generateNode(Ex, Pred, state->BindExpr(Ex, LCtx, V), nullptr,
  2169. ProgramPoint::PostLValueKind);
  2170. return;
  2171. }
  2172. if (isa<BindingDecl>(D)) {
  2173. // FIXME: proper support for bound declarations.
  2174. // For now, let's just prevent crashing.
  2175. return;
  2176. }
  2177. llvm_unreachable("Support for this Decl not implemented.");
  2178. }
  2179. /// VisitArraySubscriptExpr - Transfer function for array accesses
  2180. void ExprEngine::VisitArraySubscriptExpr(const ArraySubscriptExpr *A,
  2181. ExplodedNode *Pred,
  2182. ExplodedNodeSet &Dst){
  2183. const Expr *Base = A->getBase()->IgnoreParens();
  2184. const Expr *Idx = A->getIdx()->IgnoreParens();
  2185. ExplodedNodeSet CheckerPreStmt;
  2186. getCheckerManager().runCheckersForPreStmt(CheckerPreStmt, Pred, A, *this);
  2187. ExplodedNodeSet EvalSet;
  2188. StmtNodeBuilder Bldr(CheckerPreStmt, EvalSet, *currBldrCtx);
  2189. bool IsVectorType = A->getBase()->getType()->isVectorType();
  2190. // The "like" case is for situations where C standard prohibits the type to
  2191. // be an lvalue, e.g. taking the address of a subscript of an expression of
  2192. // type "void *".
  2193. bool IsGLValueLike = A->isGLValue() ||
  2194. (A->getType().isCForbiddenLValueType() && !AMgr.getLangOpts().CPlusPlus);
  2195. for (auto *Node : CheckerPreStmt) {
  2196. const LocationContext *LCtx = Node->getLocationContext();
  2197. ProgramStateRef state = Node->getState();
  2198. if (IsGLValueLike) {
  2199. QualType T = A->getType();
  2200. // One of the forbidden LValue types! We still need to have sensible
  2201. // symbolic locations to represent this stuff. Note that arithmetic on
  2202. // void pointers is a GCC extension.
  2203. if (T->isVoidType())
  2204. T = getContext().CharTy;
  2205. SVal V = state->getLValue(T,
  2206. state->getSVal(Idx, LCtx),
  2207. state->getSVal(Base, LCtx));
  2208. Bldr.generateNode(A, Node, state->BindExpr(A, LCtx, V), nullptr,
  2209. ProgramPoint::PostLValueKind);
  2210. } else if (IsVectorType) {
  2211. // FIXME: non-glvalue vector reads are not modelled.
  2212. Bldr.generateNode(A, Node, state, nullptr);
  2213. } else {
  2214. llvm_unreachable("Array subscript should be an lValue when not \
  2215. a vector and not a forbidden lvalue type");
  2216. }
  2217. }
  2218. getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, A, *this);
  2219. }
  2220. /// VisitMemberExpr - Transfer function for member expressions.
  2221. void ExprEngine::VisitMemberExpr(const MemberExpr *M, ExplodedNode *Pred,
  2222. ExplodedNodeSet &Dst) {
  2223. // FIXME: Prechecks eventually go in ::Visit().
  2224. ExplodedNodeSet CheckedSet;
  2225. getCheckerManager().runCheckersForPreStmt(CheckedSet, Pred, M, *this);
  2226. ExplodedNodeSet EvalSet;
  2227. ValueDecl *Member = M->getMemberDecl();
  2228. // Handle static member variables and enum constants accessed via
  2229. // member syntax.
  2230. if (isa<VarDecl>(Member) || isa<EnumConstantDecl>(Member)) {
  2231. for (const auto I : CheckedSet)
  2232. VisitCommonDeclRefExpr(M, Member, I, EvalSet);
  2233. } else {
  2234. StmtNodeBuilder Bldr(CheckedSet, EvalSet, *currBldrCtx);
  2235. ExplodedNodeSet Tmp;
  2236. for (const auto I : CheckedSet) {
  2237. ProgramStateRef state = I->getState();
  2238. const LocationContext *LCtx = I->getLocationContext();
  2239. Expr *BaseExpr = M->getBase();
  2240. // Handle C++ method calls.
  2241. if (const auto *MD = dyn_cast<CXXMethodDecl>(Member)) {
  2242. if (MD->isInstance())
  2243. state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr);
  2244. SVal MDVal = svalBuilder.getFunctionPointer(MD);
  2245. state = state->BindExpr(M, LCtx, MDVal);
  2246. Bldr.generateNode(M, I, state);
  2247. continue;
  2248. }
  2249. // Handle regular struct fields / member variables.
  2250. const SubRegion *MR = nullptr;
  2251. state = createTemporaryRegionIfNeeded(state, LCtx, BaseExpr,
  2252. /*Result=*/nullptr,
  2253. /*OutRegionWithAdjustments=*/&MR);
  2254. SVal baseExprVal =
  2255. MR ? loc::MemRegionVal(MR) : state->getSVal(BaseExpr, LCtx);
  2256. const auto *field = cast<FieldDecl>(Member);
  2257. SVal L = state->getLValue(field, baseExprVal);
  2258. if (M->isGLValue() || M->getType()->isArrayType()) {
  2259. // We special-case rvalues of array type because the analyzer cannot
  2260. // reason about them, since we expect all regions to be wrapped in Locs.
  2261. // We instead treat these as lvalues and assume that they will decay to
  2262. // pointers as soon as they are used.
  2263. if (!M->isGLValue()) {
  2264. assert(M->getType()->isArrayType());
  2265. const auto *PE =
  2266. dyn_cast<ImplicitCastExpr>(I->getParentMap().getParentIgnoreParens(M));
  2267. if (!PE || PE->getCastKind() != CK_ArrayToPointerDecay) {
  2268. llvm_unreachable("should always be wrapped in ArrayToPointerDecay");
  2269. }
  2270. }
  2271. if (field->getType()->isReferenceType()) {
  2272. if (const MemRegion *R = L.getAsRegion())
  2273. L = state->getSVal(R);
  2274. else
  2275. L = UnknownVal();
  2276. }
  2277. Bldr.generateNode(M, I, state->BindExpr(M, LCtx, L), nullptr,
  2278. ProgramPoint::PostLValueKind);
  2279. } else {
  2280. Bldr.takeNodes(I);
  2281. evalLoad(Tmp, M, M, I, state, L);
  2282. Bldr.addNodes(Tmp);
  2283. }
  2284. }
  2285. }
  2286. getCheckerManager().runCheckersForPostStmt(Dst, EvalSet, M, *this);
  2287. }
  2288. void ExprEngine::VisitAtomicExpr(const AtomicExpr *AE, ExplodedNode *Pred,
  2289. ExplodedNodeSet &Dst) {
  2290. ExplodedNodeSet AfterPreSet;
  2291. getCheckerManager().runCheckersForPreStmt(AfterPreSet, Pred, AE, *this);
  2292. // For now, treat all the arguments to C11 atomics as escaping.
  2293. // FIXME: Ideally we should model the behavior of the atomics precisely here.
  2294. ExplodedNodeSet AfterInvalidateSet;
  2295. StmtNodeBuilder Bldr(AfterPreSet, AfterInvalidateSet, *currBldrCtx);
  2296. for (const auto I : AfterPreSet) {
  2297. ProgramStateRef State = I->getState();
  2298. const LocationContext *LCtx = I->getLocationContext();
  2299. SmallVector<SVal, 8> ValuesToInvalidate;
  2300. for (unsigned SI = 0, Count = AE->getNumSubExprs(); SI != Count; SI++) {
  2301. const Expr *SubExpr = AE->getSubExprs()[SI];
  2302. SVal SubExprVal = State->getSVal(SubExpr, LCtx);
  2303. ValuesToInvalidate.push_back(SubExprVal);
  2304. }
  2305. State = State->invalidateRegions(ValuesToInvalidate, AE,
  2306. currBldrCtx->blockCount(),
  2307. LCtx,
  2308. /*CausedByPointerEscape*/true,
  2309. /*Symbols=*/nullptr);
  2310. SVal ResultVal = UnknownVal();
  2311. State = State->BindExpr(AE, LCtx, ResultVal);
  2312. Bldr.generateNode(AE, I, State, nullptr,
  2313. ProgramPoint::PostStmtKind);
  2314. }
  2315. getCheckerManager().runCheckersForPostStmt(Dst, AfterInvalidateSet, AE, *this);
  2316. }
  2317. // A value escapes in four possible cases:
  2318. // (1) We are binding to something that is not a memory region.
  2319. // (2) We are binding to a MemRegion that does not have stack storage.
  2320. // (3) We are binding to a top-level parameter region with a non-trivial
  2321. // destructor. We won't see the destructor during analysis, but it's there.
  2322. // (4) We are binding to a MemRegion with stack storage that the store
  2323. // does not understand.
  2324. ProgramStateRef
  2325. ExprEngine::processPointerEscapedOnBind(ProgramStateRef State, SVal Loc,
  2326. SVal Val, const LocationContext *LCtx) {
  2327. // Cases (1) and (2).
  2328. const MemRegion *MR = Loc.getAsRegion();
  2329. if (!MR || !MR->hasStackStorage())
  2330. return escapeValue(State, Val, PSK_EscapeOnBind);
  2331. // Case (3).
  2332. if (const auto *VR = dyn_cast<VarRegion>(MR->getBaseRegion()))
  2333. if (VR->hasStackParametersStorage() && VR->getStackFrame()->inTopFrame())
  2334. if (const auto *RD = VR->getValueType()->getAsCXXRecordDecl())
  2335. if (!RD->hasTrivialDestructor())
  2336. return escapeValue(State, Val, PSK_EscapeOnBind);
  2337. // Case (4): in order to test that, generate a new state with the binding
  2338. // added. If it is the same state, then it escapes (since the store cannot
  2339. // represent the binding).
  2340. // Do this only if we know that the store is not supposed to generate the
  2341. // same state.
  2342. SVal StoredVal = State->getSVal(MR);
  2343. if (StoredVal != Val)
  2344. if (State == (State->bindLoc(loc::MemRegionVal(MR), Val, LCtx)))
  2345. return escapeValue(State, Val, PSK_EscapeOnBind);
  2346. return State;
  2347. }
  2348. ProgramStateRef
  2349. ExprEngine::notifyCheckersOfPointerEscape(ProgramStateRef State,
  2350. const InvalidatedSymbols *Invalidated,
  2351. ArrayRef<const MemRegion *> ExplicitRegions,
  2352. const CallEvent *Call,
  2353. RegionAndSymbolInvalidationTraits &ITraits) {
  2354. if (!Invalidated || Invalidated->empty())
  2355. return State;
  2356. if (!Call)
  2357. return getCheckerManager().runCheckersForPointerEscape(State,
  2358. *Invalidated,
  2359. nullptr,
  2360. PSK_EscapeOther,
  2361. &ITraits);
  2362. // If the symbols were invalidated by a call, we want to find out which ones
  2363. // were invalidated directly due to being arguments to the call.
  2364. InvalidatedSymbols SymbolsDirectlyInvalidated;
  2365. for (const auto I : ExplicitRegions) {
  2366. if (const SymbolicRegion *R = I->StripCasts()->getAs<SymbolicRegion>())
  2367. SymbolsDirectlyInvalidated.insert(R->getSymbol());
  2368. }
  2369. InvalidatedSymbols SymbolsIndirectlyInvalidated;
  2370. for (const auto &sym : *Invalidated) {
  2371. if (SymbolsDirectlyInvalidated.count(sym))
  2372. continue;
  2373. SymbolsIndirectlyInvalidated.insert(sym);
  2374. }
  2375. if (!SymbolsDirectlyInvalidated.empty())
  2376. State = getCheckerManager().runCheckersForPointerEscape(State,
  2377. SymbolsDirectlyInvalidated, Call, PSK_DirectEscapeOnCall, &ITraits);
  2378. // Notify about the symbols that get indirectly invalidated by the call.
  2379. if (!SymbolsIndirectlyInvalidated.empty())
  2380. State = getCheckerManager().runCheckersForPointerEscape(State,
  2381. SymbolsIndirectlyInvalidated, Call, PSK_IndirectEscapeOnCall, &ITraits);
  2382. return State;
  2383. }
  2384. /// evalBind - Handle the semantics of binding a value to a specific location.
  2385. /// This method is used by evalStore and (soon) VisitDeclStmt, and others.
  2386. void ExprEngine::evalBind(ExplodedNodeSet &Dst, const Stmt *StoreE,
  2387. ExplodedNode *Pred,
  2388. SVal location, SVal Val,
  2389. bool atDeclInit, const ProgramPoint *PP) {
  2390. const LocationContext *LC = Pred->getLocationContext();
  2391. PostStmt PS(StoreE, LC);
  2392. if (!PP)
  2393. PP = &PS;
  2394. // Do a previsit of the bind.
  2395. ExplodedNodeSet CheckedSet;
  2396. getCheckerManager().runCheckersForBind(CheckedSet, Pred, location, Val,
  2397. StoreE, *this, *PP);
  2398. StmtNodeBuilder Bldr(CheckedSet, Dst, *currBldrCtx);
  2399. // If the location is not a 'Loc', it will already be handled by
  2400. // the checkers. There is nothing left to do.
  2401. if (!location.getAs<Loc>()) {
  2402. const ProgramPoint L = PostStore(StoreE, LC, /*Loc*/nullptr,
  2403. /*tag*/nullptr);
  2404. ProgramStateRef state = Pred->getState();
  2405. state = processPointerEscapedOnBind(state, location, Val, LC);
  2406. Bldr.generateNode(L, state, Pred);
  2407. return;
  2408. }
  2409. for (const auto PredI : CheckedSet) {
  2410. ProgramStateRef state = PredI->getState();
  2411. state = processPointerEscapedOnBind(state, location, Val, LC);
  2412. // When binding the value, pass on the hint that this is a initialization.
  2413. // For initializations, we do not need to inform clients of region
  2414. // changes.
  2415. state = state->bindLoc(location.castAs<Loc>(),
  2416. Val, LC, /* notifyChanges = */ !atDeclInit);
  2417. const MemRegion *LocReg = nullptr;
  2418. if (Optional<loc::MemRegionVal> LocRegVal =
  2419. location.getAs<loc::MemRegionVal>()) {
  2420. LocReg = LocRegVal->getRegion();
  2421. }
  2422. const ProgramPoint L = PostStore(StoreE, LC, LocReg, nullptr);
  2423. Bldr.generateNode(L, state, PredI);
  2424. }
  2425. }
  2426. /// evalStore - Handle the semantics of a store via an assignment.
  2427. /// @param Dst The node set to store generated state nodes
  2428. /// @param AssignE The assignment expression if the store happens in an
  2429. /// assignment.
  2430. /// @param LocationE The location expression that is stored to.
  2431. /// @param state The current simulation state
  2432. /// @param location The location to store the value
  2433. /// @param Val The value to be stored
  2434. void ExprEngine::evalStore(ExplodedNodeSet &Dst, const Expr *AssignE,
  2435. const Expr *LocationE,
  2436. ExplodedNode *Pred,
  2437. ProgramStateRef state, SVal location, SVal Val,
  2438. const ProgramPointTag *tag) {
  2439. // Proceed with the store. We use AssignE as the anchor for the PostStore
  2440. // ProgramPoint if it is non-NULL, and LocationE otherwise.
  2441. const Expr *StoreE = AssignE ? AssignE : LocationE;
  2442. // Evaluate the location (checks for bad dereferences).
  2443. ExplodedNodeSet Tmp;
  2444. evalLocation(Tmp, AssignE, LocationE, Pred, state, location, false);
  2445. if (Tmp.empty())
  2446. return;
  2447. if (location.isUndef())
  2448. return;
  2449. for (const auto I : Tmp)
  2450. evalBind(Dst, StoreE, I, location, Val, false);
  2451. }
  2452. void ExprEngine::evalLoad(ExplodedNodeSet &Dst,
  2453. const Expr *NodeEx,
  2454. const Expr *BoundEx,
  2455. ExplodedNode *Pred,
  2456. ProgramStateRef state,
  2457. SVal location,
  2458. const ProgramPointTag *tag,
  2459. QualType LoadTy) {
  2460. assert(!location.getAs<NonLoc>() && "location cannot be a NonLoc.");
  2461. assert(NodeEx);
  2462. assert(BoundEx);
  2463. // Evaluate the location (checks for bad dereferences).
  2464. ExplodedNodeSet Tmp;
  2465. evalLocation(Tmp, NodeEx, BoundEx, Pred, state, location, true);
  2466. if (Tmp.empty())
  2467. return;
  2468. StmtNodeBuilder Bldr(Tmp, Dst, *currBldrCtx);
  2469. if (location.isUndef())
  2470. return;
  2471. // Proceed with the load.
  2472. for (const auto I : Tmp) {
  2473. state = I->getState();
  2474. const LocationContext *LCtx = I->getLocationContext();
  2475. SVal V = UnknownVal();
  2476. if (location.isValid()) {
  2477. if (LoadTy.isNull())
  2478. LoadTy = BoundEx->getType();
  2479. V = state->getSVal(location.castAs<Loc>(), LoadTy);
  2480. }
  2481. Bldr.generateNode(NodeEx, I, state->BindExpr(BoundEx, LCtx, V), tag,
  2482. ProgramPoint::PostLoadKind);
  2483. }
  2484. }
  2485. void ExprEngine::evalLocation(ExplodedNodeSet &Dst,
  2486. const Stmt *NodeEx,
  2487. const Stmt *BoundEx,
  2488. ExplodedNode *Pred,
  2489. ProgramStateRef state,
  2490. SVal location,
  2491. bool isLoad) {
  2492. StmtNodeBuilder BldrTop(Pred, Dst, *currBldrCtx);
  2493. // Early checks for performance reason.
  2494. if (location.isUnknown()) {
  2495. return;
  2496. }
  2497. ExplodedNodeSet Src;
  2498. BldrTop.takeNodes(Pred);
  2499. StmtNodeBuilder Bldr(Pred, Src, *currBldrCtx);
  2500. if (Pred->getState() != state) {
  2501. // Associate this new state with an ExplodedNode.
  2502. // FIXME: If I pass null tag, the graph is incorrect, e.g for
  2503. // int *p;
  2504. // p = 0;
  2505. // *p = 0xDEADBEEF;
  2506. // "p = 0" is not noted as "Null pointer value stored to 'p'" but
  2507. // instead "int *p" is noted as
  2508. // "Variable 'p' initialized to a null pointer value"
  2509. static SimpleProgramPointTag tag(TagProviderName, "Location");
  2510. Bldr.generateNode(NodeEx, Pred, state, &tag);
  2511. }
  2512. ExplodedNodeSet Tmp;
  2513. getCheckerManager().runCheckersForLocation(Tmp, Src, location, isLoad,
  2514. NodeEx, BoundEx, *this);
  2515. BldrTop.addNodes(Tmp);
  2516. }
  2517. std::pair<const ProgramPointTag *, const ProgramPointTag*>
  2518. ExprEngine::geteagerlyAssumeBinOpBifurcationTags() {
  2519. static SimpleProgramPointTag
  2520. eagerlyAssumeBinOpBifurcationTrue(TagProviderName,
  2521. "Eagerly Assume True"),
  2522. eagerlyAssumeBinOpBifurcationFalse(TagProviderName,
  2523. "Eagerly Assume False");
  2524. return std::make_pair(&eagerlyAssumeBinOpBifurcationTrue,
  2525. &eagerlyAssumeBinOpBifurcationFalse);
  2526. }
  2527. void ExprEngine::evalEagerlyAssumeBinOpBifurcation(ExplodedNodeSet &Dst,
  2528. ExplodedNodeSet &Src,
  2529. const Expr *Ex) {
  2530. StmtNodeBuilder Bldr(Src, Dst, *currBldrCtx);
  2531. for (const auto Pred : Src) {
  2532. // Test if the previous node was as the same expression. This can happen
  2533. // when the expression fails to evaluate to anything meaningful and
  2534. // (as an optimization) we don't generate a node.
  2535. ProgramPoint P = Pred->getLocation();
  2536. if (!P.getAs<PostStmt>() || P.castAs<PostStmt>().getStmt() != Ex) {
  2537. continue;
  2538. }
  2539. ProgramStateRef state = Pred->getState();
  2540. SVal V = state->getSVal(Ex, Pred->getLocationContext());
  2541. Optional<nonloc::SymbolVal> SEV = V.getAs<nonloc::SymbolVal>();
  2542. if (SEV && SEV->isExpression()) {
  2543. const std::pair<const ProgramPointTag *, const ProgramPointTag*> &tags =
  2544. geteagerlyAssumeBinOpBifurcationTags();
  2545. ProgramStateRef StateTrue, StateFalse;
  2546. std::tie(StateTrue, StateFalse) = state->assume(*SEV);
  2547. // First assume that the condition is true.
  2548. if (StateTrue) {
  2549. SVal Val = svalBuilder.makeIntVal(1U, Ex->getType());
  2550. StateTrue = StateTrue->BindExpr(Ex, Pred->getLocationContext(), Val);
  2551. Bldr.generateNode(Ex, Pred, StateTrue, tags.first);
  2552. }
  2553. // Next, assume that the condition is false.
  2554. if (StateFalse) {
  2555. SVal Val = svalBuilder.makeIntVal(0U, Ex->getType());
  2556. StateFalse = StateFalse->BindExpr(Ex, Pred->getLocationContext(), Val);
  2557. Bldr.generateNode(Ex, Pred, StateFalse, tags.second);
  2558. }
  2559. }
  2560. }
  2561. }
  2562. void ExprEngine::VisitGCCAsmStmt(const GCCAsmStmt *A, ExplodedNode *Pred,
  2563. ExplodedNodeSet &Dst) {
  2564. StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
  2565. // We have processed both the inputs and the outputs. All of the outputs
  2566. // should evaluate to Locs. Nuke all of their values.
  2567. // FIXME: Some day in the future it would be nice to allow a "plug-in"
  2568. // which interprets the inline asm and stores proper results in the
  2569. // outputs.
  2570. ProgramStateRef state = Pred->getState();
  2571. for (const Expr *O : A->outputs()) {
  2572. SVal X = state->getSVal(O, Pred->getLocationContext());
  2573. assert(!X.getAs<NonLoc>()); // Should be an Lval, or unknown, undef.
  2574. if (Optional<Loc> LV = X.getAs<Loc>())
  2575. state = state->bindLoc(*LV, UnknownVal(), Pred->getLocationContext());
  2576. }
  2577. Bldr.generateNode(A, Pred, state);
  2578. }
  2579. void ExprEngine::VisitMSAsmStmt(const MSAsmStmt *A, ExplodedNode *Pred,
  2580. ExplodedNodeSet &Dst) {
  2581. StmtNodeBuilder Bldr(Pred, Dst, *currBldrCtx);
  2582. Bldr.generateNode(A, Pred, Pred->getState());
  2583. }
  2584. //===----------------------------------------------------------------------===//
  2585. // Visualization.
  2586. //===----------------------------------------------------------------------===//
  2587. #ifndef NDEBUG
  2588. namespace llvm {
  2589. template<>
  2590. struct DOTGraphTraits<ExplodedGraph*> : public DefaultDOTGraphTraits {
  2591. DOTGraphTraits (bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
  2592. static bool nodeHasBugReport(const ExplodedNode *N) {
  2593. BugReporter &BR = static_cast<ExprEngine &>(
  2594. N->getState()->getStateManager().getOwningEngine()).getBugReporter();
  2595. const auto EQClasses =
  2596. llvm::make_range(BR.EQClasses_begin(), BR.EQClasses_end());
  2597. for (const auto &EQ : EQClasses) {
  2598. for (const auto &I : EQ.getReports()) {
  2599. const auto *PR = dyn_cast<PathSensitiveBugReport>(I.get());
  2600. if (!PR)
  2601. continue;
  2602. const ExplodedNode *EN = PR->getErrorNode();
  2603. if (EN->getState() == N->getState() &&
  2604. EN->getLocation() == N->getLocation())
  2605. return true;
  2606. }
  2607. }
  2608. return false;
  2609. }
  2610. /// \p PreCallback: callback before break.
  2611. /// \p PostCallback: callback after break.
  2612. /// \p Stop: stop iteration if returns {@code true}
  2613. /// \return Whether {@code Stop} ever returned {@code true}.
  2614. static bool traverseHiddenNodes(
  2615. const ExplodedNode *N,
  2616. llvm::function_ref<void(const ExplodedNode *)> PreCallback,
  2617. llvm::function_ref<void(const ExplodedNode *)> PostCallback,
  2618. llvm::function_ref<bool(const ExplodedNode *)> Stop) {
  2619. const ExplodedNode *FirstHiddenNode = N;
  2620. while (FirstHiddenNode->pred_size() == 1 &&
  2621. isNodeHidden(*FirstHiddenNode->pred_begin())) {
  2622. FirstHiddenNode = *FirstHiddenNode->pred_begin();
  2623. }
  2624. const ExplodedNode *OtherNode = FirstHiddenNode;
  2625. while (true) {
  2626. PreCallback(OtherNode);
  2627. if (Stop(OtherNode))
  2628. return true;
  2629. if (OtherNode == N)
  2630. break;
  2631. PostCallback(OtherNode);
  2632. OtherNode = *OtherNode->succ_begin();
  2633. }
  2634. return false;
  2635. }
  2636. static bool isNodeHidden(const ExplodedNode *N) {
  2637. return N->isTrivial();
  2638. }
  2639. static std::string getNodeLabel(const ExplodedNode *N, ExplodedGraph *G){
  2640. std::string Buf;
  2641. llvm::raw_string_ostream Out(Buf);
  2642. const bool IsDot = true;
  2643. const unsigned int Space = 1;
  2644. ProgramStateRef State = N->getState();
  2645. auto Noop = [](const ExplodedNode*){};
  2646. bool HasReport = traverseHiddenNodes(
  2647. N, Noop, Noop, &nodeHasBugReport);
  2648. bool IsSink = traverseHiddenNodes(
  2649. N, Noop, Noop, [](const ExplodedNode *N) { return N->isSink(); });
  2650. Out << "{ \"node_id\": " << N->getID(G) << ", \"pointer\": \""
  2651. << (const void *)N << "\", \"state_id\": " << State->getID()
  2652. << ", \"has_report\": " << (HasReport ? "true" : "false")
  2653. << ", \"is_sink\": " << (IsSink ? "true" : "false")
  2654. << ",\\l";
  2655. Indent(Out, Space, IsDot) << "\"program_points\": [\\l";
  2656. // Dump program point for all the previously skipped nodes.
  2657. traverseHiddenNodes(
  2658. N,
  2659. [&](const ExplodedNode *OtherNode) {
  2660. Indent(Out, Space + 1, IsDot) << "{ ";
  2661. OtherNode->getLocation().printJson(Out, /*NL=*/"\\l");
  2662. Out << ", \"tag\": ";
  2663. if (const ProgramPointTag *Tag = OtherNode->getLocation().getTag())
  2664. Out << '\"' << Tag->getTagDescription() << "\" }";
  2665. else
  2666. Out << "null }";
  2667. },
  2668. // Adds a comma and a new-line between each program point.
  2669. [&](const ExplodedNode *) { Out << ",\\l"; },
  2670. [&](const ExplodedNode *) { return false; });
  2671. Out << "\\l"; // Adds a new-line to the last program point.
  2672. Indent(Out, Space, IsDot) << "],\\l";
  2673. bool SameAsAllPredecessors =
  2674. std::all_of(N->pred_begin(), N->pred_end(), [&](const ExplodedNode *P) {
  2675. return P->getState() == State;
  2676. });
  2677. if (!SameAsAllPredecessors) {
  2678. State->printDOT(Out, N->getLocationContext(), Space);
  2679. } else {
  2680. Indent(Out, Space, IsDot) << "\"program_state\": null";
  2681. }
  2682. Out << "\\l}\\l";
  2683. return Out.str();
  2684. }
  2685. };
  2686. } // namespace llvm
  2687. #endif
  2688. void ExprEngine::ViewGraph(bool trim) {
  2689. #ifndef NDEBUG
  2690. std::string Filename = DumpGraph(trim);
  2691. llvm::DisplayGraph(Filename, false, llvm::GraphProgram::DOT);
  2692. #endif
  2693. llvm::errs() << "Warning: viewing graph requires assertions" << "\n";
  2694. }
  2695. void ExprEngine::ViewGraph(ArrayRef<const ExplodedNode*> Nodes) {
  2696. #ifndef NDEBUG
  2697. std::string Filename = DumpGraph(Nodes);
  2698. llvm::DisplayGraph(Filename, false, llvm::GraphProgram::DOT);
  2699. #endif
  2700. llvm::errs() << "Warning: viewing graph requires assertions" << "\n";
  2701. }
  2702. std::string ExprEngine::DumpGraph(bool trim, StringRef Filename) {
  2703. #ifndef NDEBUG
  2704. if (trim) {
  2705. std::vector<const ExplodedNode *> Src;
  2706. // Iterate through the reports and get their nodes.
  2707. for (BugReporter::EQClasses_iterator
  2708. EI = BR.EQClasses_begin(), EE = BR.EQClasses_end(); EI != EE; ++EI) {
  2709. const auto *R =
  2710. dyn_cast<PathSensitiveBugReport>(EI->getReports()[0].get());
  2711. if (!R)
  2712. continue;
  2713. const auto *N = const_cast<ExplodedNode *>(R->getErrorNode());
  2714. Src.push_back(N);
  2715. }
  2716. return DumpGraph(Src, Filename);
  2717. } else {
  2718. return llvm::WriteGraph(&G, "ExprEngine", /*ShortNames=*/false,
  2719. /*Title=*/"Exploded Graph", /*Filename=*/Filename);
  2720. }
  2721. #endif
  2722. llvm::errs() << "Warning: dumping graph requires assertions" << "\n";
  2723. return "";
  2724. }
  2725. std::string ExprEngine::DumpGraph(ArrayRef<const ExplodedNode*> Nodes,
  2726. StringRef Filename) {
  2727. #ifndef NDEBUG
  2728. std::unique_ptr<ExplodedGraph> TrimmedG(G.trim(Nodes));
  2729. if (!TrimmedG.get()) {
  2730. llvm::errs() << "warning: Trimmed ExplodedGraph is empty.\n";
  2731. } else {
  2732. return llvm::WriteGraph(TrimmedG.get(), "TrimmedExprEngine",
  2733. /*ShortNames=*/false,
  2734. /*Title=*/"Trimmed Exploded Graph",
  2735. /*Filename=*/Filename);
  2736. }
  2737. #endif
  2738. llvm::errs() << "Warning: dumping graph requires assertions" << "\n";
  2739. return "";
  2740. }
  2741. void *ProgramStateTrait<ReplayWithoutInlining>::GDMIndex() {
  2742. static int index = 0;
  2743. return &index;
  2744. }