[PATCH] D56632: [analyzer] Track region liveness only through base regions.

[Phabricator via Phabricator via cfe-commits]

This revision was automatically updated to reflect the committed changes.
Closed by commit rC351499: [analyzer] Make sure base-region and its sub-regions 
are either all alive or… (authored by dergachev, committed by ).

Repository:
  rC Clang

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D56632/new/

https://reviews.llvm.org/D56632

Files:
  include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
  lib/StaticAnalyzer/Core/ExprEngine.cpp
  lib/StaticAnalyzer/Core/SymbolManager.cpp
  test/Analysis/diagnostics/dtors.cpp
  test/Analysis/symbol-reaper.cpp
  unittests/StaticAnalyzer/CMakeLists.txt
  unittests/StaticAnalyzer/SymbolReaperTest.cpp

Index: lib/StaticAnalyzer/Core/SymbolManager.cpp
===
--- lib/StaticAnalyzer/Core/SymbolManager.cpp
+++ lib/StaticAnalyzer/Core/SymbolManager.cpp
@@ -405,7 +405,7 @@
 }
 
 void SymbolReaper::markLive(const MemRegion *region) {
-  RegionRoots.insert(region);
+  RegionRoots.insert(region->getBaseRegion());
   markElementIndicesLive(region);
 }
 
@@ -426,11 +426,15 @@
 }
 
 bool SymbolReaper::isLiveRegion(const MemRegion *MR) {
+  // TODO: For now, liveness of a memory region is equivalent to liveness of its
+  // base region. In fact we can do a bit better: say, if a particular FieldDecl
+  // is not used later in the path, we can diagnose a leak of a value within
+  // that field earlier than, say, the variable that contains the field dies.
+  MR = MR->getBaseRegion();
+
   if (RegionRoots.count(MR))
 return true;
 
-  MR = MR->getBaseRegion();
-
   if (const auto *SR = dyn_cast(MR))
 return isLive(SR->getSymbol());
 
Index: lib/StaticAnalyzer/Core/ExprEngine.cpp
===
--- lib/StaticAnalyzer/Core/ExprEngine.cpp
+++ lib/StaticAnalyzer/Core/ExprEngine.cpp
@@ -198,7 +198,9 @@
mgr.getConstraintManagerCreator(), G.getAllocator(),
this),
   SymMgr(StateMgr.getSymbolManager()),
-  svalBuilder(StateMgr.getSValBuilder()), ObjCNoRet(mgr.getASTContext()),
+  MRMgr(StateMgr.getRegionManager()),
+  svalBuilder(StateMgr.getSValBuilder()),
+  ObjCNoRet(mgr.getASTContext()),
   BR(mgr, *this),
   VisitedCallees(VisitedCalleesIn), HowToInline(HowToInlineIn) {
   unsigned TrimInterval = mgr.options.GraphTrimInterval;
Index: unittests/StaticAnalyzer/SymbolReaperTest.cpp
===
--- unittests/StaticAnalyzer/SymbolReaperTest.cpp
+++ unittests/StaticAnalyzer/SymbolReaperTest.cpp
@@ -0,0 +1,121 @@
+//===- unittests/StaticAnalyzer/SymbolReaperTest.cpp --===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===--===//
+
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/Frontend/CompilerInstance.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
+#include "clang/CrossTU/CrossTranslationUnit.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
+#include "clang/StaticAnalyzer/Frontend/AnalysisConsumer.h"
+#include "clang/Tooling/Tooling.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace ento {
+namespace {
+
+using namespace ast_matchers;
+
+// A re-usable consumer that constructs ExprEngine out of CompilerInvocation.
+// TODO: Actually re-use it when we write our second test.
+class ExprEngineConsumer : public ASTConsumer {
+protected:
+  CompilerInstance 
+
+private:
+  // We need to construct all of these in order to construct ExprEngine.
+  CheckerManager ChkMgr;
+  cross_tu::CrossTranslationUnitContext CTU;
+  PathDiagnosticConsumers Consumers;
+  AnalysisManager AMgr;
+  SetOfConstDecls VisitedCallees;
+  FunctionSummariesTy FS;
+
+protected:
+  ExprEngine Eng;
+
+  // Find a declaration in the current AST by name. This has nothing to do
+  // with ExprEngine but turns out to be handy.
+  // TODO: There's probably a better place for it.
+  template 
+  const T *findDeclByName(const Decl *Where, StringRef Name) {
+auto Matcher = decl(hasDescendant(namedDecl(hasName(Name)).bind("d")));
+auto Matches = match(Matcher, *Where, Eng.getContext());
+assert(Matches.size() == 1 && "Ambiguous name!");
+const T *Node = selectFirst("d", Matches);
+assert(Node && "Name not found!");
+return Node;
+  }
+
+public:
+  ExprEngineConsumer(CompilerInstance )
+  : C(C), ChkMgr(C.getASTContext(), *C.getAnalyzerOpts()), CTU(C),
+Consumers(),
+AMgr(C.getASTContext(), C.getDiagnostics(), Consumers,
+ CreateRegionStoreManager, CreateRangeConstraintManager, ,
+ *C.getAnalyzerOpts()),
+VisitedCallees(), FS(),
+Eng(CTU, AMgr, , , 

[PATCH] D56632: [analyzer] Track region liveness only through base regions.

[Artem Dergachev via Phabricator via cfe-commits]

NoQ added a comment.

In D56632#1359215 , @NoQ wrote:

> In D56632#1356163 , 
> @baloghadamsoftware wrote:
>
> > Did you measure decrease in the false-positive rate or an increase in the 
> > true-positive rate on real code? I expect some.
>
>
> In progress :)


Moderately surprisingly, i found no changes at all. I guess it's pretty rare 
that the object dies out from Environment last in such manner while its 
original field symbol values are still important. Still worth fixing though - 
might have been worse, you never know... also peace of mind.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D56632/new/

https://reviews.llvm.org/D56632



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D56632: [analyzer] Track region liveness only through base regions.

[Artem Dergachev via Phabricator via cfe-commits]

NoQ added a comment.

In D56632#1359576 , @xazax.hun wrote:

> If you find out the reason why we need `markElementIndicesLive`, documenting 
> that would also be useful. But it is also independent of this change. 
>  Maybe something like we could learn new information regarding the indices 
> after they are dead?
> Like:
>
>   void f(int i, char *c) {
>   char e = c[i];
>   if (strlen(c) == 5) {
>// The value of `i` is no longer used, could be dead
>// but we did learn something new. Assuming no UB, `i <= 5` (if 
> null terminated).
>// So maybe having symbols for indices around for representing the 
> info above is useful?
>   use(c);
>   }
>   }
>


Yep, that was pretty much the original motivation behind adding this 
functionality in D12726 .

A more ridiculous example:

  struct rlimit rlim;
  getrlimit(RLIMIT_NOFILE, ); // Max file descriptor on the system.
  int *arr = calloc(rlim.rlim_cur, sizeof(int)); // An expensive but fast map 
from FDs to ints.
  arr[open("foo.txt", O_RDONLY)] = 1; // Remember that this descriptor is open.

After that even though the file descriptor is otherwise dead, as long as `arr` 
is alive and its contents are more or less preserved, you can close the file as 
follows:

  for (int i = 0; i < rlim.lim_cur; ++i)
if (arr[i] == 1)
  close(i);

Therefore, we kinda should not diagnose a file descriptor leak here.

> One fundamental question is, do we have one property here or two?
>  Maybe the liveness analysis we use for leaks (and other purposes?),
>  and the garbage collection of symbols are inherently two different kind of 
> things that are only slightly related?

This constantly bothers me, but surprisingly, i don't see any reasonable 
counter-examples to them being the same thing.

One of the brightest examples i have is that if the parent region of a 
`LazyCompoundVal` is an `ElementRegion` with symbolic index, constraints on its 
index ideally need to be kept alive in order to access the data within the 
`LazyCompoundVal` as accurately as possible, but it's not really accessible 
from within the program because the parent region of a `LazyCompoundVal` is 
entirely immaterial. However, this is merely a weird implementation detail of 
our `LazyCompoundVal`s: we could have implemented "eager" compound values 
instead, and in that case it wouldn't have been a problem anymore. Note that it 
is not a sufficient solution to simply make `LazyCompoundVal` capture 
constraints together with the store, because constraints might have improved 
since then (and then dropped, and only then we're trying to load the value).

So i believe that as long as our state is not over-saturated with information 
(i.e., it looks kinda like a normalized database), then the amount of 
information we need to track is going to be exactly as much as the programmer 
is able to extract from memory in run-time.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D56632/new/

https://reviews.llvm.org/D56632



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D56632: [analyzer] Track region liveness only through base regions.

[Kristóf Umann via Phabricator via cfe-commits]

Szelethus added inline comments.



Comment at: test/Analysis/symbol-reaper.cpp:31
+  clang_analyzer_eval(glob); // expected-warning{{TRUE}}
+ // expected-warning@-1{{SYMBOL DEAD}}
+}

NoQ wrote:
> Szelethus wrote:
> > N00b question: What does `SYMBOL DEAD` mean here exactly?
> It's a warning produced by `clang_analyzer_warnOnDeadSymbol(a.x)` when the 
> value that was in `a.x` (that was there when that function was called) dies. 
> This is an `ExprInspection` utility that was created in order to test 
> `SymbolReaper` more directly. See `symbol-reaper.c` for more such tests.
Oooh right. I thought it's produced by `clang_analyzer_eval(glob);`. Thanks!


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D56632/new/

https://reviews.llvm.org/D56632



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D56632: [analyzer] Track region liveness only through base regions.

[Gábor Horváth via Phabricator via cfe-commits]

xazax.hun accepted this revision.
xazax.hun added a comment.

Thanks, LGTM! It is interesting to see if we need to traverse all the super 
regions in `scanReachableSymbols`, but if we need to change something there, I 
would prefer that to be in a separate patch. 
If visiting the whole super region chain proved to be redundant I would 
recommend removing it for clarity regardless of having a performance impact.

If you find out the reason why we need `markElementIndicesLive`, documenting 
that would also be useful. But it is also independent of this change. 
Maybe something like we could learn new information regarding the indices after 
they are dead?
Like:

  void f(int i, char *c) {
  char e = c[i];
  if (strlen(c) == 5) {
   // The value of `i` is no longer used, could be dead
   // but we did learn something new. Assuming no UB, `i <= 5` (if null 
terminated).
   // So maybe having symbols for indices around for representing the 
info above is useful?
  }
  }

One fundamental question is, do we have one property here or two?
Maybe the liveness analysis we use for leaks (and other purposes?),
and the garbage collection of symbols are inherently two different kind of 
things that are only slightly related?


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D56632/new/

https://reviews.llvm.org/D56632



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D56632: [analyzer] Track region liveness only through base regions.

[Artem Dergachev via Phabricator via cfe-commits]

NoQ added inline comments.



Comment at: include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h:390
 
-  // FIXME: Remove when we migrate over to just using ValueManager.
   SymbolManager () { return SymMgr; }

baloghadamsoftware wrote:
> Is this comment intentionally deleted?
Yeah, i don't think anybody remembers what was that about and there doesn't 
seem to be an immediate need in something like that.

Hmm, why did i delete it as part of that revision? I guess because i was moving 
these helper methods around. Let me bring them back because this place is 
actually better, now that i think about it.

Also i wonder if anybody ever uses this const getter two lines below (or even 
passes `ExprEngine` by const reference anywhere). Hmm, seems to compile without 
it.



Comment at: test/Analysis/symbol-reaper.cpp:1
+// RUN: %clang_analyze_cc1 -analyzer-checker=debug.ExprInspection -verify %s
+

Szelethus wrote:
> Core intentionally left out?
Thx ^.^ No, just still have this habit since before it was decided to make it 
mandatory >.<



Comment at: test/Analysis/symbol-reaper.cpp:13
+  void foo() {
+// Ugh, maybe just let clang_analyzer_eval() work within callees already?
+// The glob variable shouldn't keep our symbol alive because

a_sidorin wrote:
> //FIXME?
Yeah, i guess it's a more polite way of expressing it :)



Comment at: test/Analysis/symbol-reaper.cpp:31
+  clang_analyzer_eval(glob); // expected-warning{{TRUE}}
+ // expected-warning@-1{{SYMBOL DEAD}}
+}

Szelethus wrote:
> N00b question: What does `SYMBOL DEAD` mean here exactly?
It's a warning produced by `clang_analyzer_warnOnDeadSymbol(a.x)` when the 
value that was in `a.x` (that was there when that function was called) dies. 
This is an `ExprInspection` utility that was created in order to test 
`SymbolReaper` more directly. See `symbol-reaper.c` for more such tests.



Comment at: unittests/StaticAnalyzer/SymbolReaperTest.cpp:52
+assert(Matches.size() == 1 && "Ambiguous name!");
+for (BoundNodes  : Matches)
+  return M.getNodeAs("d");

a_sidorin wrote:
> It looks like `selectFirst` helper is what you need here.
Wow, this one's handy.



Comment at: unittests/StaticAnalyzer/SymbolReaperTest.cpp:97
+  bool HandleTopLevelDecl(DeclGroupRef DG) override {
+for (auto D: DG)
+  performTest(D);

a_sidorin wrote:
> Nit: `const auto *D : DG`
Fxd^^


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D56632/new/

https://reviews.llvm.org/D56632



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D56632: [analyzer] Track region liveness only through base regions.

[Artem Dergachev via Phabricator via cfe-commits]

NoQ updated this revision to Diff 181961.
NoQ marked 12 inline comments as done.
NoQ added a comment.

Fix stuff.

In D56632#1356163 , 
@baloghadamsoftware wrote:

> Did you measure decrease in the false-positive rate or an increase in the 
> true-positive rate on real code? I expect some.


In progress :)

In D56632#1356249 , @xazax.hun wrote:

> > When a memory region is live, all its sub-regions and super-regions are 
> > automatically live (and vice versa), so it is only necessary to track 
> > liveness of base regions.
>
>
>
>   I think this is non-obvious. If we had all the information it would make 
> perfect sense to have a dead field in an alive struct. But since the liveness 
> analysis is intraprocedural and we cannot know what happens to a struct when 
> it escapes we have no choice but keep the field alive. A more sophisticated 
> analysis (which is also likely to be more expensive) could have dead fields 
> in an alive struct in case the struct never escapes. 


Great point indeed! I vaguely remember that some other tools do actually work 
that way. If a field is not referenced anywhere in the path and there's no 
weird pointer arithmetic going on upon the variable, we can actually diagnose a 
leak of the value within the field *before* the variable itself dies. Even 
intraprocedurally, we can just handle escapes and still do slightly better than 
we do now. This gets really valuable when the variable is, say, a non-escaping 
static (local or global). The variable never dies, but there may still be no 
deallocation for the field anywhere in the code and we may be able to see this 
within the translation unit. This doesn't have to have anything to do with 
fields though, the variable itself may carry the leaking pointer. Same with 
private fields regardless of storage. Neat food for thought.

Added a comment. Is there anything else worth documenting here, other than "the 
whole damn thing"?

>> The answer is yes, it does work correctly, because scanReachableSymbols 
>> always scans the whole super-region chain of every region. Which means that 
>> every time the Environment or the Store marks a region as live, all of its 
>> super-regions are added to RegionRoots. However, i would still like to add 
>> conversion to the base region into markLive(), because this behavior is 
>> something that should be guaranteed by SymbolReaper rather implied by 
>> callers manually, even if the callers have to do that anyway.
> 
> I did not really follow, but probably my understanding of how memory regions 
> work is not correct. If we work with base regions, why do we still need to 
> scan the whole super-region chain?

It's just that `scanReachableSymbols` is written that way, and it's used 
everywhere for these kind of purposes. I.e., we (i.e., `SymbolReaper`) don't 
(i.e., doesn't) need to scan the whole chain of regions (apart from the 
`markElementIndicesLive()` thing... wait a minute, does it work in the opposite 
direction? - i.e., if an array-typed region is live, does it automatically mean 
that all index symbols in all element regions within it are actually treated as 
live everywhere in the program state? - need to check), but this behavior is 
re-used from other users `scanReachableSymbols` (wait a minute, do any of the 
other users actually need that? - i'm not immediately seeing any user actually 
need that, it seems that *everybody* operates on base regions only - but 
probably it's anyway not that much slower than jumping to the base region 
directly - need to check).


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D56632/new/

https://reviews.llvm.org/D56632

Files:
  include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
  lib/StaticAnalyzer/Core/ExprEngine.cpp
  lib/StaticAnalyzer/Core/SymbolManager.cpp
  test/Analysis/diagnostics/dtors.cpp
  test/Analysis/symbol-reaper.cpp
  unittests/StaticAnalyzer/CMakeLists.txt
  unittests/StaticAnalyzer/SymbolReaperTest.cpp

Index: unittests/StaticAnalyzer/SymbolReaperTest.cpp
===
--- /dev/null
+++ unittests/StaticAnalyzer/SymbolReaperTest.cpp
@@ -0,0 +1,121 @@
+//===- unittests/StaticAnalyzer/SymbolReaperTest.cpp --===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===--===//
+
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/Frontend/CompilerInstance.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
+#include "clang/CrossTU/CrossTranslationUnit.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
+#include "clang/StaticAnalyzer/Frontend/AnalysisConsumer.h"

[PATCH] D56632: [analyzer] Track region liveness only through base regions.

[Aleksei Sidorin via Phabricator via cfe-commits]

a_sidorin added a comment.

Hi Artem,
This looks perfect, just some stylish issues.




Comment at: test/Analysis/symbol-reaper.cpp:13
+  void foo() {
+// Ugh, maybe just let clang_analyzer_eval() work within callees already?
+// The glob variable shouldn't keep our symbol alive because

//FIXME?



Comment at: unittests/StaticAnalyzer/SymbolReaperTest.cpp:52
+assert(Matches.size() == 1 && "Ambiguous name!");
+for (BoundNodes  : Matches)
+  return M.getNodeAs("d");

It looks like `selectFirst` helper is what you need here.



Comment at: unittests/StaticAnalyzer/SymbolReaperTest.cpp:53
+for (BoundNodes  : Matches)
+  return M.getNodeAs("d");
+llvm_unreachable("Unable to find declaration!");

This loop will be executed one time only.



Comment at: unittests/StaticAnalyzer/SymbolReaperTest.cpp:97
+  bool HandleTopLevelDecl(DeclGroupRef DG) override {
+for (auto D: DG)
+  performTest(D);

Nit: `const auto *D : DG`


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D56632/new/

https://reviews.llvm.org/D56632



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D56632: [analyzer] Track region liveness only through base regions.

[Gábor Horváth via Phabricator via cfe-commits]

xazax.hun added a comment.

I really like all this detective work and it would be sad to have it forgotten. 
I would love to see some of your comments in the documentation of symbol reaper.
More specifically:

> When a memory region is live, all its sub-regions and super-regions are 
> automatically live (and vice versa), so it is only necessary to track 
> liveness of base regions.

I think this is non-obvious. If we had all the information it would make 
perfect sense to have a dead field in an alive struct. But since the liveness 
analysis is intraprocedural and we cannot know what happens to a struct when it 
escapes we have no choice but keep the field alive. A more sophisticated 
analysis (which also likely to be more expensive) could have dead fields in an 
alive struct in case the struct never escapes.

> The answer is yes, it does work correctly, because scanReachableSymbols 
> always scans the whole super-region chain of every region. Which means that 
> every time the Environment or the Store marks a region as live, all of its 
> super-regions are added to RegionRoots. However, i would still like to add 
> conversion to the base region into markLive(), because this behavior is 
> something that should be guaranteed by SymbolReaper rather implied by callers 
> manually, even if the callers have to do that anyway.

I did not really follow, but probably my understanding if how memory regions 
work is not correct. If we work with base regions, why do we still need to scan 
the whole super-region chain?


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D56632/new/

https://reviews.llvm.org/D56632



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D56632: [analyzer] Track region liveness only through base regions.

[Kristóf Umann via Phabricator via cfe-commits]

Szelethus accepted this revision.
Szelethus added a comment.
This revision is now accepted and ready to land.

Awesome detective work! I glanced over the code, it looks great. I'd love to 
dedicate more time to your liveness-related patches, but university is a thing, 
so finding typos and the like is the best I can do for a while.

Wild thought, would `debug.DumpLiveStmts` be of any use here?




Comment at: test/Analysis/symbol-reaper.cpp:1
+// RUN: %clang_analyze_cc1 -analyzer-checker=debug.ExprInspection -verify %s
+

Core intentionally left out?



Comment at: test/Analysis/symbol-reaper.cpp:31
+  clang_analyzer_eval(glob); // expected-warning{{TRUE}}
+ // expected-warning@-1{{SYMBOL DEAD}}
+}

N00b question: What does `SYMBOL DEAD` mean here exactly?



Comment at: unittests/StaticAnalyzer/CMakeLists.txt:8
   RegisterCustomCheckersTest.cpp
+  SymbolReaperTest.cpp
   )

Woohoo!


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D56632/new/

https://reviews.llvm.org/D56632



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D56632: [analyzer] Track region liveness only through base regions.

[Balogh, Ádám via Phabricator via cfe-commits]

baloghadamsoftware added a comment.

This seems to be an important fix. Thank you!

Did you measure decrease in the false-positive rate or an increase in the 
true-positive rate on real code? I expect some.




Comment at: include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h:390
 
-  // FIXME: Remove when we migrate over to just using ValueManager.
   SymbolManager () { return SymMgr; }

Is this comment intentionally deleted?


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D56632/new/

https://reviews.llvm.org/D56632



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D56632: [analyzer] Track region liveness only through base regions.

[Artem Dergachev via Phabricator via cfe-commits]

NoQ updated this revision to Diff 181419.
NoQ marked an inline comment as done.
NoQ added a comment.

Prettify the unittest a bit, especially the `ASTMatcher` part of it.


CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D56632/new/

https://reviews.llvm.org/D56632

Files:
  include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
  lib/StaticAnalyzer/Core/ExprEngine.cpp
  lib/StaticAnalyzer/Core/SymbolManager.cpp
  test/Analysis/diagnostics/dtors.cpp
  test/Analysis/symbol-reaper.cpp
  unittests/StaticAnalyzer/CMakeLists.txt
  unittests/StaticAnalyzer/SymbolReaperTest.cpp

Index: unittests/StaticAnalyzer/SymbolReaperTest.cpp
===
--- /dev/null
+++ unittests/StaticAnalyzer/SymbolReaperTest.cpp
@@ -0,0 +1,121 @@
+//===- unittests/StaticAnalyzer/SymbolReaperTest.cpp --===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===--===//
+
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/Frontend/CompilerInstance.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
+#include "clang/CrossTU/CrossTranslationUnit.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
+#include "clang/StaticAnalyzer/Frontend/AnalysisConsumer.h"
+#include "clang/Tooling/Tooling.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace ento {
+namespace {
+
+using namespace ast_matchers;
+
+// A re-usable consumer that constructs ExprEngine out of CompilerInvocation.
+// TODO: Actually re-use it when we write our second test.
+class ExprEngineConsumer : public ASTConsumer {
+protected:
+  CompilerInstance 
+
+private:
+  // We need to construct all of these in order to construct ExprEngine.
+  CheckerManager ChkMgr;
+  cross_tu::CrossTranslationUnitContext CTU;
+  PathDiagnosticConsumers Consumers;
+  AnalysisManager AMgr;
+  SetOfConstDecls VisitedCallees;
+  FunctionSummariesTy FS;
+
+protected:
+  ExprEngine Eng;
+
+  // Find a declaration in the current AST by name. This has nothing to do
+  // with ExprEngine but turns out to be handy.
+  // TODO: There's probably a better place for it.
+  template 
+  const T *findDeclByName(const Decl *Where, StringRef Name) {
+auto Matcher = decl(hasDescendant(namedDecl(hasName(Name)).bind("d")));
+auto Matches = match(Matcher, *Where, Eng.getContext());
+assert(Matches.size() == 1 && "Ambiguous name!");
+for (BoundNodes  : Matches)
+  return M.getNodeAs("d");
+llvm_unreachable("Unable to find declaration!");
+  }
+
+public:
+  ExprEngineConsumer(CompilerInstance )
+  : C(C), ChkMgr(C.getASTContext(), *C.getAnalyzerOpts()), CTU(C),
+Consumers(),
+AMgr(C.getASTContext(), C.getDiagnostics(), Consumers,
+ CreateRegionStoreManager, CreateRangeConstraintManager, ,
+ *C.getAnalyzerOpts()),
+VisitedCallees(), FS(),
+Eng(CTU, AMgr, , , ExprEngine::Inline_Regular) {}
+};
+
+class SuperRegionLivenessConsumer : public ExprEngineConsumer {
+  void performTest(const Decl *D) {
+const auto *FD = findDeclByName(D, "x");
+const auto *VD = findDeclByName(D, "s");
+assert(FD && VD);
+
+// The variable must belong to a stack frame,
+// otherwise SymbolReaper would think it's a global.
+const StackFrameContext *SFC =
+Eng.getAnalysisDeclContextManager().getStackFrame(D);
+
+// Create regions for 's' and 's.x'.
+const VarRegion *VR = Eng.getRegionManager().getVarRegion(VD, SFC);
+const FieldRegion *FR = Eng.getRegionManager().getFieldRegion(FD, VR);
+
+// Pass a null location context to the SymbolReaper so that
+// it was thinking that the variable is dead.
+SymbolReaper SymReaper((StackFrameContext *)nullptr, (Stmt *)nullptr,
+   Eng.getSymbolManager(), Eng.getStoreManager());
+
+SymReaper.markLive(FR);
+EXPECT_TRUE(SymReaper.isLiveRegion(VR));
+  }
+
+public:
+  SuperRegionLivenessConsumer(CompilerInstance ) : ExprEngineConsumer(C) {}
+  ~SuperRegionLivenessConsumer() override {}
+
+  bool HandleTopLevelDecl(DeclGroupRef DG) override {
+for (auto D: DG)
+  performTest(D);
+return true;
+  }
+};
+
+class SuperRegionLivenessAction: public ASTFrontendAction {
+public:
+  SuperRegionLivenessAction() {}
+  std::unique_ptr CreateASTConsumer(CompilerInstance ,
+ StringRef File) override {
+auto Consumer = llvm::make_unique(Compiler);
+return Consumer;
+  }
+};
+
+// Test that marking s.x as live would also make s live.
+TEST(SymbolReaper, SuperRegionLiveness) {
+  EXPECT_TRUE(tooling::runToolOnCode(new SuperRegionLivenessAction,
+ "void foo() { struct 

[PATCH] D56632: [analyzer] Track region liveness only through base regions.

[Artem Dergachev via Phabricator via cfe-commits]

NoQ created this revision.
NoQ added reviewers: dcoughlin, xazax.hun, a_sidorin, george.karpenkov, 
rnkovacs, mikhail.ramalho, Szelethus, baloghadamsoftware.
Herald added subscribers: cfe-commits, dkrupp, donat.nagy, a.sidorin, szepet, 
mgorny.

This is a follow-up to D56042 .

When a memory region is live, all its sub-regions and super-regions are 
automatically live (and vice versa), so it is only necessary to track liveness 
of base regions. This is exactly how we imagined this to work, but it turns out 
that it didn't.

The reason why it works correctly most of the time because the reachable symbol 
scanner is automatically marks all parent regions as reachable - and therefore 
they are marked as live by adding all of them to region roots every time a 
sub-region is marked as live. However, enumerating all *child* regions this way 
is problematic (there may be infinitely many of them).

In the test from D56042 , the symbol for `p.x` 
dies because when `.get()` is called for the last time only `p` is kept alive 
by the Environment, but not `p.x`. Due to that,  `reg_$0` is believed to 
be dead - recall that `SymbolRegionValue` is kept alive by its parent region, 
and additionally notice that there are no explicit bindings anywhere else to 
keep it alive (because `SymbolRegionValue` is simply assumed to be there as 
long as the parent region is alive, rather than bound explicitly).

Now, when the `RegionRoots` test fails, `isLiveRegion()` falls through to see 
if the region is "lexically" alive. Here it correctly jumps to the base region 
`p` and looks if live variables analysis thinks it's alive. It doesn't! Because 
there's no need to compute expression 'p' anymore anywhere in the program.

What `isLiveRegion()` should have done is look up the base region in 
`RegionRoots`. But it doesn't. Hence the patch.

The newly added `test_A` demonstrates the problem even more clearly: having the 
symbol for `a.x` die before the call to `a.foo()` is definitely incorrect.

The other test, `test_B`, is an attempt to figure out whether the problem is 
also there "in the opposite direction". That is, when `b.a` is marked live, is 
`b` marked live automatically? Otherwise the lookup in `RegionRoots` would 
still fail.

The answer is yes, it does work correctly, because `scanReachableSymbols` 
always scans the whole super-region chain of every region. Which means that 
every time the Environment or the Store marks a region as live, all of its 
super-regions are added to `RegionRoots`. However, i would still like to add 
conversion to the base region into `markLive()`, because this behavior is 
something that should be guaranteed by `SymbolReaper` rather implied by callers 
manually, even if the callers have to do that anyway.

So for now the change in `markLive()` does not affect functionality at all, but 
it will be important when checkers use the `checkLiveSymbols()` functionality 
more aggressively. Additionally it slightly decreases the size of the 
`RegionRoots` map for faster lookups but adds an extra time overhead for 
marking something as live (need to ascend to the base region). I didn't try to 
figure out whether it gives a net gain in performance.

For that reason the unit test as well. Also a few convenient getters were added 
to `ExprEngine` in order to make the test more concise.


Repository:
  rC Clang

https://reviews.llvm.org/D56632

Files:
  include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h
  lib/StaticAnalyzer/Core/ExprEngine.cpp
  lib/StaticAnalyzer/Core/SymbolManager.cpp
  test/Analysis/diagnostics/dtors.cpp
  test/Analysis/symbol-reaper.cpp
  unittests/StaticAnalyzer/CMakeLists.txt
  unittests/StaticAnalyzer/SymbolReaperTest.cpp

Index: unittests/StaticAnalyzer/SymbolReaperTest.cpp
===
--- /dev/null
+++ unittests/StaticAnalyzer/SymbolReaperTest.cpp
@@ -0,0 +1,119 @@
+//===- unittests/StaticAnalyzer/SymbolReaperTest.cpp --===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===--===//
+
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/Frontend/CompilerInstance.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
+#include "clang/CrossTU/CrossTranslationUnit.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
+#include "clang/StaticAnalyzer/Frontend/AnalysisConsumer.h"
+#include "clang/Tooling/Tooling.h"
+#include "gtest/gtest.h"
+
+namespace clang {
+namespace ento {
+namespace {
+
+using namespace ast_matchers;
+
+class SuperRegionLivenessConsumer : public ASTConsumer {
+  CompilerInstance 
+
+  // We need to construct all of