[StaticAnalyzer] Fix failures due to the iteration order of ExplodedNode

[mgrang]

Summary

This fixes failures seen in the reverse iteration builder:
http://lab.llvm.org:8011/builders/reverse-iteration/builds/26

Failing Tests (4):

Clang :: Analysis/MisusedMovedObject.cpp
Clang :: Analysis/keychainAPI.m
Clang :: Analysis/loop-unrolling.cpp
Clang :: Analysis/malloc.c

[mgrang]

The thing I am concerned with here is whether changing SmallPtrSet to a SetVector can potentially slow down the Static Analyzer? ExplodedNode seem to be used heavily in the analyzer and I can see it being iterated upon in several places.

[mgrang]

This comment was removed by mgrang.

[mgrang]

I had accidentally pushed a wrong patch to this commit. Fixed it now.

[mgrang]

Ping for reviews please.

[zaks.anna]

Thanks for addressing the non-determinism!!!

The ExplodedNodeSet is predominantly used to hold very small sets and it is used quite a bit in the analyzer. Maybe we could we use SmallSetVector here instead?

[mgrang]

Addressed comments.

[mgrang]

include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h

406

SmallSetVector size has to be a power of 2. I was split between 4 and 8. I chose 4 as it's closer to 5 :)

[zaks.anna]

Thank you!
Anna

include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h

 #include "clang/AST/Decl.h"
 #include "clang/Analysis/AnalysisContext.h"
 #include "clang/Analysis/ProgramPoint.h"
 #include "clang/Analysis/Support/BumpVector.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/GraphTraits.h"
-#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Casting.h"
 #include <memory>
 #include <utility>
 #include <vector>
 
 namespace clang {
 
public:
   static bool isInterestingLValueExpr(const Expr *Ex);
 
 private:
   bool shouldCollect(const ExplodedNode *node);
   void collectNode(ExplodedNode *node);
 };
 
 class ExplodedNodeSet {
-  typedef llvm::SmallPtrSet<ExplodedNode*,5> ImplTy;
+  typedef llvm::SetVector<ExplodedNode*> ImplTy;
   ImplTy Impl;
 
 public:
   ExplodedNodeSet(ExplodedNode *N) {
     assert (N && !static_cast<ExplodedNode*>(N)->isSink());
     Impl.insert(N);
   }
 
   ExplodedNodeSet() {}
 
   inline void Add(ExplodedNode *N) {
     if (N && !static_cast<ExplodedNode*>(N)->isSink()) Impl.insert(N);
   }
 
   typedef ImplTy::iterator       iterator;
   typedef ImplTy::const_iterator const_iterator;
 
   unsigned size() const { return Impl.size();  }
   bool empty()    const { return Impl.empty(); }
-  bool erase(ExplodedNode *N) { return Impl.erase(N); }
+  bool erase(ExplodedNode *N) { return Impl.remove(N); }
 
   void clear() { Impl.clear(); }
   void insert(const ExplodedNodeSet &S) {
     assert(&S != this);
     if (empty())
       Impl = S.Impl;
     else
       Impl.insert(S.begin(), S.end());