lib/StaticAnalyzer/Core/WorkList.cpp

//===- WorkList.cpp - Analyzer work-list implementation--------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// Defines different worklist implementations for the static analyzer.
//
//===----------------------------------------------------------------------===//

#include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h"
#include "llvm/ADT/PriorityQueue.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/Statistic.h"
#include <deque>
#include <vector>

using namespace clang;
using namespace ento;

#define DEBUG_TYPE "WorkList"

STATISTIC(MaxQueueSize, "Maximum size of the worklist");
STATISTIC(MaxReachableSize, "Maximum size of auxiliary worklist set");

//===----------------------------------------------------------------------===//
// Worklist classes for exploration of reachable states.
//===----------------------------------------------------------------------===//

namespace {

class DFS : public WorkList {
  SmallVector<WorkListUnit, 20> Stack;

public:
  bool hasWork() const override {
    return !Stack.empty();
  }

  void enqueue(const WorkListUnit& U) override {
    Stack.push_back(U);
  }

  WorkListUnit dequeue() override {
    assert(!Stack.empty());
    const WorkListUnit& U = Stack.back();
    Stack.pop_back(); // This technically "invalidates" U, but we are fine.
    return U;
  }
};

class BFS : public WorkList {
  std::deque<WorkListUnit> Queue;

public:
  bool hasWork() const override {
    return !Queue.empty();
  }

  void enqueue(const WorkListUnit& U) override {
    Queue.push_back(U);
  }

  WorkListUnit dequeue() override {
    WorkListUnit U = Queue.front();
    Queue.pop_front();
    return U;
  }
};

} // namespace

// Place the dstor for WorkList here because it contains virtual member
// functions, and we the code for the dstor generated in one compilation unit.
WorkList::~WorkList() = default;

std::unique_ptr<WorkList> WorkList::makeDFS() {
  return std::make_unique<DFS>();
}

std::unique_ptr<WorkList> WorkList::makeBFS() {
  return std::make_unique<BFS>();
}

namespace {

  class BFSBlockDFSContents : public WorkList {
    std::deque<WorkListUnit> Queue;
    SmallVector<WorkListUnit, 20> Stack;

  public:
    bool hasWork() const override {
      return !Queue.empty() || !Stack.empty();
    }

    void enqueue(const WorkListUnit& U) override {
      if (U.getNode()->getLocation().getAs<BlockEntrance>())
        Queue.push_front(U);
      else
        Stack.push_back(U);
    }

    WorkListUnit dequeue() override {
      // Process all basic blocks to completion.
      if (!Stack.empty()) {
        const WorkListUnit& U = Stack.back();
        Stack.pop_back(); // This technically "invalidates" U, but we are fine.
        return U;
      }

      assert(!Queue.empty());
      // Don't use const reference.  The subsequent pop_back() might make it
      // unsafe.
      WorkListUnit U = Queue.front();
      Queue.pop_front();
      return U;
    }
  };

} // namespace

std::unique_ptr<WorkList> WorkList::makeBFSBlockDFSContents() {
  return std::make_unique<BFSBlockDFSContents>();
}

namespace {

class UnexploredFirstStack : public WorkList {
  /// Stack of nodes known to have statements we have not traversed yet.
  SmallVector<WorkListUnit, 20> StackUnexplored;

  /// Stack of all other nodes.
  SmallVector<WorkListUnit, 20> StackOthers;

  using BlockID = unsigned;
  using LocIdentifier = std::pair<BlockID, const StackFrameContext *>;

  llvm::DenseSet<LocIdentifier> Reachable;

public:
  bool hasWork() const override {
    return !(StackUnexplored.empty() && StackOthers.empty());
  }

  void enqueue(const WorkListUnit &U) override {
    const ExplodedNode *N = U.getNode();
    auto BE = N->getLocation().getAs<BlockEntrance>();

    if (!BE) {
      // Assume the choice of the order of the preceding block entrance was
      // correct.
      StackUnexplored.push_back(U);
    } else {
      LocIdentifier LocId = std::make_pair(
          BE->getBlock()->getBlockID(),
          N->getLocationContext()->getStackFrame());
      auto InsertInfo = Reachable.insert(LocId);

      if (InsertInfo.second) {
        StackUnexplored.push_back(U);
      } else {
        StackOthers.push_back(U);
      }
    }
    MaxReachableSize.updateMax(Reachable.size());
    MaxQueueSize.updateMax(StackUnexplored.size() + StackOthers.size());
  }

  WorkListUnit dequeue() override {
    if (!StackUnexplored.empty()) {
      WorkListUnit &U = StackUnexplored.back();
      StackUnexplored.pop_back();
      return U;
    } else {
      WorkListUnit &U = StackOthers.back();
      StackOthers.pop_back();
      return U;
    }
  }
};

} // namespace

std::unique_ptr<WorkList> WorkList::makeUnexploredFirst() {
  return std::make_unique<UnexploredFirstStack>();
}

namespace {
class UnexploredFirstPriorityQueue : public WorkList {
  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 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;

  // 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 {
    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]++;
    }

    queue.push(std::make_pair(U, std::make_pair(-NumVisited, ++Counter)));
  }

  WorkListUnit dequeue() override {
    QueueItem U = queue.top();
    queue.pop();
    return U.first;
  }
};
} // namespace

std::unique_ptr<WorkList> WorkList::makeUnexploredFirstPriorityQueue() {
  return std::make_unique<UnexploredFirstPriorityQueue>();
}

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>;

  // 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 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;

  // 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 {
    const ExplodedNode *N = U.getNode();
    unsigned NumVisited = 0;
    if (auto BE = N->getLocation().getAs<BlockEntrance>())
      NumVisited = NumReached[BE->getBlock()]++;

    queue.push(std::make_pair(U, std::make_pair(-NumVisited, ++Counter)));
  }

  WorkListUnit dequeue() override {
    QueueItem U = queue.top();
    queue.pop();
    return U.first;
  }

};

}

std::unique_ptr<WorkList> WorkList::makeUnexploredFirstPriorityLocationQueue() {
  return std::make_unique<UnexploredFirstPriorityLocationQueue>();
}