[analyzer][WIP] Attempt to fix traversing bindings of non-base regions in ClusterAnalysis

[xazax.hun]

Summary

Follow up for a problem described in https://reviews.llvm.org/D57230

I think the ClusterAnalysis is fundamentally flawed at this point and it does not support non-base regions properly. The reason we could get away with this so far is that it is very rare to have non-base regions there.

I made an attempt to fix this and I successfully fixes the false positive described by Artem in https://reviews.llvm.org/D57230.
While I am not completely sure yet whether this is the most desirable solution, I wanted to share the work in progress solution to get some feedback about the directions.

[xazax.hun]

• Fix test failures.

[NoQ]

After staring at this for an hour or two, i didn't manage to force myself to understand how our cluster analysis works here, but i totally agree that it's most likely broken; i guess, we should eventually move away from the idea that everything works through base regions, but for now this idea seems to be hardcoded in a lot of places.

That said, the patch does fix the test case that i provided, but it doesn't fix my original regression :( so i'll run the reduce again to see if i have more to say. And i'll also try harder to understand what's going on.

lib/StaticAnalyzer/Core/RegionStore.cpp

1039

The patch introduces a whitespace error here :p

[NoQ]

Ugh, it takes forever to debug, because it gets reduced to a true positive now, and the original unprunned report is ~1300 pieces long (the normal report being completely worthless) and the exploded graph is too slow to view. While i find myself parsing dot files with regular expressions, i'll be totally happy if you simply add the test and commit, but i'll definitely keep trying to understand what's going on, because it's still a problem down there.

[NoQ]

Ok, got it! Yeah, this sounds like a valid way of supporting non-base-region-based worklist items, i'm seeing no problems with it and i don't immediately see a solution that'd be better than gradually supporting non-base-regions in more and more places.

Here's the slight modification of the original test case (D57230#1389766) that my problem finally boiled down to:

typedef __typeof(sizeof(int)) size_t;
void *malloc(size_t);

struct S {
  int x; // Make sure ptr has a non-zero offset within baseR.
  int *ptr;
};

struct T {
  struct S s; // This is baseR.
};

void escape(struct S *);

void foo() {
  struct T t; // This is realBaseR.
  t.s.ptr = malloc(sizeof(int));
  escape(&t.s);
}

This happens because in this patch you're pin-pointing the value by trying to look it up via an exact binding key (up to default/direct), however it may also reside at a non-zero offset within baseR. In my case the offset was also symbolic - which kept me confused for a while because i was thinking that symbolic offsets are the root of all evil. I think you may be able to generalize the patch to cover this scenario by replacing the exact offset lookup with a collectSubRegionBindings() (it might be cute to make some sort of iterSubRegionBindings() that takes a lambda, and/or combine it with iterBindings()).

I'm still worried about D57230#1434161 though. It kinda sounds like a good idea to suppress store invalidation but not escaping, but it's a very annoying thing to implement because our invalidation traits are very inflexible. In order to express complex requirements like "please don't invalidate this region, except this sub-region", the whole data structure has to be changed. This is slightly similar to this problem we have in:

void escape(int *x, const int *y);
// ...
escape(&a, &a);

where the value of a would not be invalidated because y is a const pointer, even though it is passed through a non-const pointer x. @xazax.hun, do you have enough time/inspiration to dig that deeply into this stuff?

[xazax.hun]

First of all, sorry for the inactivity regarding this patch.

In D58121#1437433, @NoQ wrote:

Ok, got it! Yeah, this sounds like a valid way of supporting non-base-region-based worklist items, i'm seeing no problems with it and i don't immediately see a solution that'd be better than gradually supporting non-base-regions in more and more places.

Here's the slight modification of the original test case (D57230#1389766) that my problem finally boiled down to:

typedef __typeof(sizeof(int)) size_t;
void *malloc(size_t);

struct S {
  int x; // Make sure ptr has a non-zero offset within baseR.
  int *ptr;
};

struct T {
  struct S s; // This is baseR.
};

void escape(struct S *);

void foo() {
  struct T t; // This is realBaseR.
  t.s.ptr = malloc(sizeof(int));
  escape(&t.s);
}

This happens because in this patch you're pin-pointing the value by trying to look it up via an exact binding key (up to default/direct), however it may also reside at a non-zero offset within baseR. In my case the offset was also symbolic - which kept me confused for a while because i was thinking that symbolic offsets are the root of all evil. I think you may be able to generalize the patch to cover this scenario by replacing the exact offset lookup with a collectSubRegionBindings() (it might be cute to make some sort of iterSubRegionBindings() that takes a lambda, and/or combine it with iterBindings()).

Oh, I see. Thank you for tracking this down! Your proposed solution sounds reasonable to me. I hope there will be no significant performance hit.

I'm still worried about D57230#1434161 though. It kinda sounds like a good idea to suppress store invalidation but not escaping, but it's a very annoying thing to implement because our invalidation traits are very inflexible. In order to express complex requirements like "please don't invalidate this region, except this sub-region", the whole data structure has to be changed. This is slightly similar to this problem we have in:

void escape(int *x, const int *y);
// ...
escape(&a, &a);

where the value of a would not be invalidated because y is a const pointer, even though it is passed through a non-const pointer x. @xazax.hun, do you have enough time/inspiration to dig that deeply into this stuff?

I totally agree that invalidation and escaping are orthogonal. I really glad you found this example, I think you are right, the current data structure is not flexible enough. Unfortunately, I have some unrelated deadlines coming up, so it is very likely that I can only start working on this problem around early May. If you have some time to work on these problems feel free to commandeer this patch and I will definitely try to find time to review your patches.

[NoQ]

Mmm. I'm also pretty pinned down (it's seasonal), so i'm thinking of temporarily reverting :( until one of us gets to fixing the accidental effect on escaping, 'cause it just keeps biting us. Like, i wholeheartedly appreciate the work and i have already noticed a few times how it makes things better and loved it, it just seems to accidentally have something missing that nobody could predict, and i'll be super eager to get it back in.

[xazax.hun]

In D58121#1452483, @NoQ wrote:

Mmm. I'm also pretty pinned down (it's seasonal), so i'm thinking of temporarily reverting :( until one of us gets to fixing the accidental effect on escaping, 'cause it just keeps biting us. Like, i wholeheartedly appreciate the work and i have already noticed a few times how it makes things better and loved it, it just seems to accidentally have something missing that nobody could predict, and i'll be super eager to get it back in.

Sounds perfectly reasonable. I was also thinking about suggesting a temporary revert.

[NoQ]

Reverted D57230 in rC357620.
(also added that offending test case with lists)

lib/StaticAnalyzer/Core/CallEvent.cpp

if (const MemRegion *MR = getArgSVal(Idx).getAsRegion()) {
         if (const auto *TVR = FR->getSuperRegion()->getAs<TypedValueRegion>()) {
           if (!TVR->getValueType()->isUnionType()) {
             ETraits.setTrait(MR, RegionAndSymbolInvalidationTraits::
                                      TK_DoNotInvalidateSuperRegion);
             UseBaseRegion = false;
           }
         }
       }
-      // todo: factor this out + handle the lower level const pointers.
+      // TODO: factor this out + handle the lower level const pointers.
       if (PreserveArgs.count(Idx))
         ETraits.setTrait(
             UseBaseRegion ? MR->getBaseRegion() : MR,
             RegionAndSymbolInvalidationTraits::TK_PreserveContents);
     }
 
     ValuesToInvalidate.push_back(getArgSVal(Idx));
 

lib/StaticAnalyzer/Core/RegionStore.cpp

enum GlobalsFilterKind {
   GFK_SystemOnly,
   /// Include all global regions.
   GFK_All
 };
 
 template <typename DERIVED>
 class ClusterAnalysis  {
 protected:
-  typedef llvm::DenseMap<const MemRegion *, const ClusterBindings *> ClusterMap;
   typedef const MemRegion * WorkListElement;
   typedef SmallVector<WorkListElement, 10> WorkList;
 
   llvm::SmallPtrSet<const ClusterBindings *, 16> Visited;
 
   WorkList WL;
 
   RegionStoreManager &RM;
bool AddToWorkList(const MemRegion *R) {
     return static_cast<DERIVED*>(this)->AddToWorkList(R);
   }
 
   void RunWorkList() {
     while (!WL.empty()) {
       WorkListElement E = WL.pop_back_val();
       const MemRegion *BaseR = E;
 
-      static_cast<DERIVED*>(this)->VisitCluster(BaseR, getCluster(BaseR));
+      static_cast<DERIVED *>(this)->VisitCluster(
+          BaseR, getCluster(BaseR->getBaseRegion()));
     }
   }
 
   void VisitAddedToCluster(const MemRegion *baseR, const ClusterBindings &C) {}
   void VisitCluster(const MemRegion *baseR, const ClusterBindings *C) {}
 
   void VisitCluster(const MemRegion *BaseR, const ClusterBindings *C,
                     bool Flag) {
public:
   bool isInitiallyIncludedGlobalRegion(const MemRegion *R);
 };
 }
 
 bool InvalidateRegionsWorker::AddToWorkList(const MemRegion *R) {
   bool doNotInvalidateSuperRegion = ITraits.hasTrait(
       R, RegionAndSymbolInvalidationTraits::TK_DoNotInvalidateSuperRegion);
   const MemRegion *BaseR = doNotInvalidateSuperRegion ? R : R->getBaseRegion();
-  return AddToWorkList(WorkListElement(BaseR), getCluster(BaseR));
+  return AddToWorkList(WorkListElement(BaseR), getCluster(R));
 }
 
 void InvalidateRegionsWorker::VisitBinding(SVal V) {
   // A symbol?  Mark it touched by the invalidation.
   if (SymbolRef Sym = V.getAsSymbol())
     IS.insert(Sym);
 
   if (const MemRegion *R = V.getAsRegion()) {

 void InvalidateRegionsWorker::VisitCluster(const MemRegion *baseR,
                                            const ClusterBindings *C) {
 
   bool PreserveRegionsContents =
       ITraits.hasTrait(baseR,
                        RegionAndSymbolInvalidationTraits::TK_PreserveContents);
 
   if (C) {
+    const MemRegion *realBase = baseR->getBaseRegion();
+    if (realBase == baseR) {
       for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I)
         VisitBinding(I.getData());
+    } else {
+      if (const SVal *Direct =
+              C->lookup(BindingKey::Make(baseR, BindingKey::Direct)))
+        VisitBinding(*Direct);
+      else if (const SVal *Default =
+                   C->lookup(BindingKey::Make(baseR, BindingKey::Default)))
+        VisitBinding(*Default);
+    }
 
     // Invalidate regions contents.
     if (!PreserveRegionsContents)
       B = B.remove(baseR);
-  }
+  } 
 
   if (const auto *TO = dyn_cast<TypedValueRegion>(baseR)) {
     if (const auto *RD = TO->getValueType()->getAsCXXRecordDecl()) {
 
       // Lambdas can affect all static local variables without explicitly
       // capturing those.
       // We invalidate all static locals referenced inside the lambda body.
       if (RD->isLambda() && RD->getLambdaCallOperator()->getBody()) {