[clang][analyzer][ctu] Traverse the ctu CallEnter nodes in reverse order

[martong]

Summary

This change reverses the traverse order of those nodes that had been added to
the ctu worklist during the first phase of the analysis. By reversing the order
of these nodes, we start in the ctu phase with the nodes that are closer to the
root node. Measurements show that this way the length of the bug-paths are
decreasing with roughly by 10%.

[steakhal]

clang/lib/StaticAnalyzer/Core/WorkList.cpp

204–207

Please leave a note there, of what the negative values are used for.

216–218

It seems like you are not exploiting the signedness of this variable. And a counter should never be negative anyway.

255

Raw enum would make it more convenient, and the scope is already private - thus it won't affect readability elsewhere.

[xazax.hun]

This approach fixes the worklist for the second phase. Would it be possible to create a wrapper that reverses the order of any worklist instead of committing to one and hardcode that?

[martong]

In D123784#3496981, @xazax.hun wrote:

This approach fixes the worklist for the second phase. Would it be possible to create a wrapper that reverses the order of any worklist instead of committing to one and hardcode that?

We don't want to reverse the worklist completely. We could reverse if we want to, by popping all elements and adding them to another queue which has the negated ordering function.

We'd like to have a reversed order only for those nodes that are added to the CTUWorklist during the first phase. In all other cases the normal ordering is the desired. Why? Because we'd like to keep the original algorithm once we are evaluating an inlined foreign function. The only thing we'd like to change is that which foreign function to choose for evaluation next. And we'd like that to be the one that is closer to the root node in the exploded graph (this way the overall path lengths can decrease).

Would it be possible to create a wrapper that reverses the order of any worklist instead of committing to one and hardcode that?

I don't think this is possible. I mean how could we reverse the DFS, would that be a BFS? The set of the visited nodes might change at the moment when we choose an other node as next. The only way it could work, if we first collect all the nodes that we want to visit. But the graph is being built as we do the visitation.

[martong]

clang/lib/StaticAnalyzer/Core/WorkList.cpp

216–218

It is used in the descendant class.

[martong]

Abandoning because by using a bool in ctuBifurcate, the CTUWorklist will not have more than one elements during the first phase. Details: https://reviews.llvm.org/D123773?id=426037#inline-1206493

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

public:
   BlockCounter getBlockCounter() const { return CurrentCounter; }
 
   static std::unique_ptr<WorkList> makeDFS();
   static std::unique_ptr<WorkList> makeBFS();
   static std::unique_ptr<WorkList> makeBFSBlockDFSContents();
   static std::unique_ptr<WorkList> makeUnexploredFirst();
   static std::unique_ptr<WorkList> makeUnexploredFirstPriorityQueue();
   static std::unique_ptr<WorkList> makeUnexploredFirstPriorityLocationQueue();
+  static std::unique_ptr<WorkList> makeCTUWorkList();
 };
 
 } // end ento namespace
 
 } // end clang namespace
 
 #endif

clang/lib/StaticAnalyzer/Core/CoreEngine.cpp

case ExplorationStrategyKind::UnexploredFirstLocationQueue:
       return WorkList::makeUnexploredFirstPriorityLocationQueue();
   }
   llvm_unreachable("Unknown AnalyzerOptions::ExplorationStrategyKind");
 }
 
 CoreEngine::CoreEngine(ExprEngine &exprengine, FunctionSummariesTy *FS,
                        AnalyzerOptions &Opts)
     : ExprEng(exprengine), WList(generateWorkList(Opts)),
-      CTUWList(generateWorkList(Opts)), BCounterFactory(G.getAllocator()),
+      CTUWList(WorkList::makeCTUWorkList()), BCounterFactory(G.getAllocator()),
       FunctionSummaries(FS) {}
 
 void CoreEngine::setBlockCounter(BlockCounter C) {
   WList->setBlockCounter(C);
   if (CTUWList)
     CTUWList->setBlockCounter(C);
 }
 

clang/lib/StaticAnalyzer/Core/WorkList.cpp

 
 } // namespace
 
 std::unique_ptr<WorkList> WorkList::makeUnexploredFirst() {
   return std::make_unique<UnexploredFirstStack>();
 }
 
 namespace {
+
 class UnexploredFirstPriorityQueue : public WorkList {
+protected:
   using BlockID = unsigned;
   using LocIdentifier = std::pair<BlockID, const StackFrameContext *>;
 
   // How many times each location was visited.
   // Is signed because we negate it later in order to have a reversed
   // comparison.
   using VisitedTimesMap = llvm::DenseMap<LocIdentifier, int>;
 
   // Compare by number of times the location was visited first (negated
   // to prefer less often visited locations), then by insertion time (prefer
   // expanding nodes inserted sooner first).
-  using QueuePriority = std::pair<int, unsigned long>;
+  using QueuePriority = std::pair<int, long>;
   using QueueItem = std::pair<WorkListUnit, QueuePriority>;
 
   struct ExplorationComparator {
     bool operator() (const QueueItem &LHS, const QueueItem &RHS) {
       return LHS.second < RHS.second;
     }
   };
 
   // Number of inserted nodes, used to emulate DFS ordering in the priority
   // queue when insertions are equal.
-  unsigned long Counter = 0;
+  long Counter = 0;
 
   // Number of times a current location was reached.
   VisitedTimesMap NumReached;
 
   // The top item is the largest one.
   llvm::PriorityQueue<QueueItem, std::vector<QueueItem>, ExplorationComparator>
       queue;
 
-public:
-  bool hasWork() const override {
-    return !queue.empty();
-  }
-
-  void enqueue(const WorkListUnit &U) override {
+  unsigned getNumVisited(const WorkListUnit &U) {
     const ExplodedNode *N = U.getNode();
     unsigned NumVisited = 0;
     if (auto BE = N->getLocation().getAs<BlockEntrance>()) {
       LocIdentifier LocId = std::make_pair(
           BE->getBlock()->getBlockID(),
           N->getLocationContext()->getStackFrame());
       NumVisited = NumReached[LocId]++;
     }
+    return NumVisited;
+  }
 
+public:
+  bool hasWork() const override { return !queue.empty(); }
+
+  void enqueue(const WorkListUnit &U) override {
+    unsigned NumVisited = getNumVisited(U);
     queue.push(std::make_pair(U, std::make_pair(-NumVisited, ++Counter)));
   }
 
   WorkListUnit dequeue() override {
     QueueItem U = queue.top();
     queue.pop();
     return U.first;
   }
 };
+
+class CTUWorkList : public UnexploredFirstPriorityQueue {
+  enum class SecondaryOrder { DFS = 1, ReverseDFS };
+  SecondaryOrder ScndOrd = SecondaryOrder::ReverseDFS;
+
+  long ReverseDFSCounter = 0;
+
+public:
+  void enqueue(const WorkListUnit &U) override {
+    unsigned NumVisited = getNumVisited(U);
+    queue.push(std::make_pair(
+        U, std::make_pair(-NumVisited, ScndOrd == SecondaryOrder::DFS
+                                           ? ++Counter
+                                           : --ReverseDFSCounter)));
+  }
+
+  WorkListUnit dequeue() override {
+    // During the first phase we never call dequeue(). Thus, the first call of
+    // dequeue() indicates the start of the second phase. We want to have the
+    // normal ordering during the second phase.
+    ScndOrd = SecondaryOrder::DFS;
+    return UnexploredFirstPriorityQueue::dequeue();
+  }
+};
+
 } // namespace
 
 std::unique_ptr<WorkList> WorkList::makeUnexploredFirstPriorityQueue() {
   return std::make_unique<UnexploredFirstPriorityQueue>();
 }
 
+std::unique_ptr<WorkList> WorkList::makeCTUWorkList() {
+  return std::make_unique<CTUWorkList>();
+}
+
 namespace {
 class UnexploredFirstPriorityLocationQueue : public WorkList {
   using LocIdentifier = const CFGBlock *;
 
   // How many times each location was visited.
   // Is signed because we negate it later in order to have a reversed
   // comparison.
   using VisitedTimesMap = llvm::DenseMap<LocIdentifier, int>;