[analyzer] Remove memoization from RunLoopAutoreleaseLeakChecker

[george.karpenkov]

Summary

Memoization dose not seem to be necessary, as other statement visitors run just fine without it,
and in fact seems to be causing memory corruptions.
Just removing it instead of investigating the root cause.

rdar://45945002

[NoQ]

Test? :)

[NoQ]

Like, i mean, is it possible to obtain a test case for the memory corruption?

[george.karpenkov]

Like, i mean, is it possible to obtain a test case for the memory corruption?

I haven't reduced it, and it only runs under ASAN

[NoQ]

So an ASAN buildbot will catch a regression. I think it's cool.

[NoQ]

Let's commit without a test because of the urgency, and add the test soon.

[NoQ]

Hmm, i think i get it. Cached is a reference. Changing Memoization will invalidate references because DenseMap doesn't provide the respective guarantee.

Here's how the code should have looked:

~  77     Optional<TriBoolTy> Cached = Memoization[C];
~  78     if (!Cached) {
   79       Cached = seenBeforeRec(C, A, B, Memoization);
+  80       Memoization[C] = Cached;
+  81     }

[george.karpenkov]

@NoQ thanks, interesting! But I thought the underlying map is not actually modified while the reference is alive?

[NoQ]

I think that it is modified, at least, when Memoization[C] is evaluated. The object needs to be created and put into the map in order to obtain a reference to it.

[NoQ]

That is, it is modified within the recursive call.

[NoQ]

Added a test in rC349000.

lib/StaticAnalyzer/Checkers/RunLoopAutoreleaseLeakChecker.cpp

public:
   void checkASTCodeBody(const Decl *D,
                         AnalysisManager &AM,
                         BugReporter &BR) const;
 
 };
 
 } // end anonymous namespace
 
-
-using TriBoolTy = Optional<bool>;
-using MemoizationMapTy = llvm::DenseMap<const Stmt *, Optional<TriBoolTy>>;
-
-static TriBoolTy
-seenBeforeRec(const Stmt *Parent, const Stmt *A, const Stmt *B,
-              MemoizationMapTy &Memoization) {
+/// \return Whether {@code A} occurs before {@code B} in traversal of
+/// {@code Parent}.
+/// Conceptually a very incomplete/unsound approximation of happens-before
+/// relationship (A is likely to be evaluated before B),
+/// but useful enough in this case.
+static bool seenBefore(const Stmt *Parent, const Stmt *A, const Stmt *B) {
   for (const Stmt *C : Parent->children()) {
     if (!C) continue;
 
     if (C == A)
       return true;
 
     if (C == B)
       return false;
 
-    Optional<TriBoolTy> &Cached = Memoization[C];
-    if (!Cached)
-      Cached = seenBeforeRec(C, A, B, Memoization);
-
-    if (Cached->hasValue())
-      return Cached->getValue();
+    return seenBefore(C, A, B);
   }
-
-  return None;
-}
-
-/// \return Whether {@code A} occurs before {@code B} in traversal of
-/// {@code Parent}.
-/// Conceptually a very incomplete/unsound approximation of happens-before
-/// relationship (A is likely to be evaluated before B),
-/// but useful enough in this case.
-static bool seenBefore(const Stmt *Parent, const Stmt *A, const Stmt *B) {
-  MemoizationMapTy Memoization;
-  TriBoolTy Val = seenBeforeRec(Parent, A, B, Memoization);
-  return Val.getValue();
+  return false;
 }
 
 static void emitDiagnostics(BoundNodes &Match,
                             const Decl *D,
                             BugReporter &BR,
                             AnalysisManager &AM,
                             const RunLoopAutoreleaseLeakChecker *Checker) {