//===- DataflowWorklist.h ---------------------------------------*- C++ -*-===//

//

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

//

//===----------------------------------------------------------------------===//

//

// A simple and reusable worklist for flow-sensitive analyses.

//

//===----------------------------------------------------------------------===//

#ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWWORKLIST_H

#define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWWORKLIST_H

#include "clang/Analysis/Analyses/PostOrderCFGView.h"

#include "clang/Analysis/CFG.h"

#include "llvm/ADT/PriorityQueue.h"

namespace clang {

/// A worklist implementation where the enqueued blocks will be dequeued based

/// on the order defined by 'Comp'.

template <typename Comp, unsigned QueueSize> class DataflowWorklistBase {

  llvm::BitVector EnqueuedBlocks;

  PostOrderCFGView *POV;

  llvm::PriorityQueue<const CFGBlock *,

                      SmallVector<const CFGBlock *, QueueSize>, Comp>

      WorkList;

public:

  DataflowWorklistBase(const CFG &Cfg, PostOrderCFGView *POV, Comp C)

      : EnqueuedBlocks(Cfg.getNumBlockIDs()), POV(POV), WorkList(C) {}

clang::DataflowWorklistBase<clang::PostOrderCFGView::BlockOrderCompare, 20u>::DataflowWorklistBase(clang::CFG const&, clang::PostOrderCFGView*, clang::PostOrderCFGView::BlockOrderCompare)

Line

Count

Source

31

26.8k

      : EnqueuedBlocks(Cfg.getNumBlockIDs()), POV(POV), WorkList(C) {}

clang::DataflowWorklistBase<clang::ReversePostOrderCompare, 20u>::DataflowWorklistBase(clang::CFG const&, clang::PostOrderCFGView*, clang::ReversePostOrderCompare)

Line

Count

Source

31

1.59k

      : EnqueuedBlocks(Cfg.getNumBlockIDs()), POV(POV), WorkList(C) {}

  const PostOrderCFGView *getCFGView() const { return POV; }

  void enqueueBlock(const CFGBlock *Block) {

    if (Block && 
!EnqueuedBlocks[Block->getBlockID()]251k
) {

      EnqueuedBlocks[Block->getBlockID()] = true;

      WorkList.push(Block);

    }

  }

clang::DataflowWorklistBase<clang::PostOrderCFGView::BlockOrderCompare, 20u>::enqueueBlock(clang::CFGBlock const*)

Line

Count

Source

35

176k

  void enqueueBlock(const CFGBlock *Block) {

36

176k

    if (Block && 
!EnqueuedBlocks[Block->getBlockID()]174k
) {

37

99.4k

      EnqueuedBlocks[Block->getBlockID()] = true;

38

99.4k

      WorkList.push(Block);

39

99.4k

    }

40

176k

  }

clang::DataflowWorklistBase<clang::ReversePostOrderCompare, 20u>::enqueueBlock(clang::CFGBlock const*)

Line

Count

Source

35

76.6k

  void enqueueBlock(const CFGBlock *Block) {

36

76.6k

    if (Block && 
!EnqueuedBlocks[Block->getBlockID()]76.6k
) {

37

75.7k

      EnqueuedBlocks[Block->getBlockID()] = true;

38

75.7k

      WorkList.push(Block);

39

75.7k

    }

40

76.6k

  }

  const CFGBlock *dequeue() {

    if (WorkList.empty())

      return nullptr;

    const CFGBlock *B = WorkList.top();

    WorkList.pop();

    EnqueuedBlocks[B->getBlockID()] = false;

    return B;

  }

clang::DataflowWorklistBase<clang::PostOrderCFGView::BlockOrderCompare, 20u>::dequeue()

Line

Count

Source

42

126k

  const CFGBlock *dequeue() {

43

126k

    if (WorkList.empty())

44

26.8k

      return nullptr;

45

99.4k

    const CFGBlock *B = WorkList.top();

46

99.4k

    WorkList.pop();

47

99.4k

    EnqueuedBlocks[B->getBlockID()] = false;

48

99.4k

    return B;

49

126k

  }

clang::DataflowWorklistBase<clang::ReversePostOrderCompare, 20u>::dequeue()

Line

Count

Source

42

77.3k

  const CFGBlock *dequeue() {

43

77.3k

    if (WorkList.empty())

44

1.59k

      return nullptr;

45

75.7k

    const CFGBlock *B = WorkList.top();

46

75.7k

    WorkList.pop();

47

75.7k

    EnqueuedBlocks[B->getBlockID()] = false;

48

75.7k

    return B;

49

77.3k

  }

};

struct ReversePostOrderCompare {

  PostOrderCFGView::BlockOrderCompare Cmp;

  bool operator()(const CFGBlock *lhs, const CFGBlock *rhs) const {

    return Cmp(rhs, lhs);

  }

};

/// A worklist implementation for forward dataflow analysis. The enqueued

/// blocks will be dequeued in reverse post order. The worklist cannot contain

/// the same block multiple times at once.

struct ForwardDataflowWorklist

    : DataflowWorklistBase<ReversePostOrderCompare, 20> {

  ForwardDataflowWorklist(const CFG &Cfg, PostOrderCFGView *POV)

      : DataflowWorklistBase(Cfg, POV,

                             ReversePostOrderCompare{POV->getComparator()}) {}

  ForwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx)

      : ForwardDataflowWorklist(Cfg, Ctx.getAnalysis<PostOrderCFGView>()) {}

Unexecuted instantiation: clang::ForwardDataflowWorklist::ForwardDataflowWorklist(clang::CFG const&, clang::AnalysisDeclContext&)

clang::ForwardDataflowWorklist::ForwardDataflowWorklist(clang::CFG const&, clang::AnalysisDeclContext&)

Line

Count

Source

69

1.30k

      : ForwardDataflowWorklist(Cfg, Ctx.getAnalysis<PostOrderCFGView>()) {}

  void enqueueSuccessors(const CFGBlock *Block) {

    for (auto B : Block->succs())

      enqueueBlock(B);

  }

};

/// A worklist implementation for backward dataflow analysis. The enqueued

/// block will be dequeued in post order. The worklist cannot contain the same

/// block multiple times at once.

struct BackwardDataflowWorklist

    : DataflowWorklistBase<PostOrderCFGView::BlockOrderCompare, 20> {

  BackwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx)

      : DataflowWorklistBase(

            Cfg, Ctx.getAnalysis<PostOrderCFGView>(),

            Ctx.getAnalysis<PostOrderCFGView>()->getComparator()) {}

  void enqueuePredecessors(const CFGBlock *Block) {

    for (auto B : Block->preds())

      enqueueBlock(B);

  }

};

} // namespace clang

#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWWORKLIST_H