li.zhe.hua created this revision.
Herald added subscribers: martong, xazax.hun.
Herald added a reviewer: NoQ.
Herald added a project: All.
li.zhe.hua requested review of this revision.
Herald added a project: clang.
Herald added a subscriber: cfe-commits.
When navigating a loop block, we call the lattice's widen operator,
which gives a lattice of infinite height the opportunity to reach
convergence.
As we enter the loop, we store the block state in the back edge block,
which represents the state after the zeroth iteration. Then, after
each loop iteration, we widen the previous iteration's state with the
new iteration's state.
Tracking bug: #56931
Depends on D131645 <https://reviews.llvm.org/D131645>
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D131646
Files:
clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
Index: clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
===================================================================
--- clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
+++ clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
@@ -43,12 +43,15 @@
using namespace test;
using namespace ast_matchers;
using ::testing::_;
+using ::testing::AllOf;
+using ::testing::Each;
using ::testing::ElementsAre;
using ::testing::IsEmpty;
-using ::testing::IsNull;
using ::testing::NotNull;
+using ::testing::Optional;
using ::testing::Pair;
using ::testing::Ref;
+using ::testing::SizeIs;
using ::testing::Test;
using ::testing::UnorderedElementsAre;
@@ -222,6 +225,58 @@
"maximum number of iterations reached");
}
+struct ConvergesOnWidenLattice {
+ int State = 0;
+ bool Top = false;
+
+ bool operator==(const ConvergesOnWidenLattice &Other) const {
+ if (Top)
+ return Other.Top;
+ return State == Other.State;
+ }
+
+ LatticeJoinEffect join(const ConvergesOnWidenLattice &Other) {
+ auto Prev = *this;
+ Top = Top || Other.Top;
+ State += Other.State;
+ return Prev == *this ? LatticeJoinEffect::Unchanged
+ : LatticeJoinEffect::Changed;
+ }
+
+ void widen(const ConvergesOnWidenLattice &Other) { Top = true; }
+
+ friend std::ostream &operator<<(std::ostream &OS,
+ const ConvergesOnWidenLattice &L) {
+ return OS << "{" << L.State << "," << (L.Top ? "true" : "false") << "}";
+ }
+};
+
+class ConvergesOnWidenAnalysis
+ : public DataflowAnalysis<ConvergesOnWidenAnalysis,
+ ConvergesOnWidenLattice> {
+public:
+ explicit ConvergesOnWidenAnalysis(ASTContext &Context)
+ : DataflowAnalysis(Context,
+ /*ApplyBuiltinTransfer=*/false) {}
+
+ static ConvergesOnWidenLattice initialElement() { return {}; }
+
+ void transfer(const Stmt *S, ConvergesOnWidenLattice &E, Environment &Env) {
+ ++E.State;
+ }
+};
+
+TEST(DataflowAnalysisTest, ConvergesOnWidenAnalysis) {
+ std::string Code = R"(
+ void target() {
+ while(true) {}
+ }
+ )";
+ auto BlockStates = llvm::cantFail(runAnalysis<ConvergesOnWidenAnalysis>(
+ Code, [](ASTContext &C) { return ConvergesOnWidenAnalysis(C); }));
+ EXPECT_THAT(BlockStates, AllOf(SizeIs(4), Each(Optional(_))));
+}
+
struct FunctionCallLattice {
llvm::SmallSet<std::string, 8> CalledFunctions;
Index: clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
===================================================================
--- clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
+++ clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp
@@ -154,6 +154,35 @@
TransferOptions TransferOpts;
};
+// Returns whether `Block` is a "back edge" in the CFG. Such a block is empty
+// and has only one successor, the start of the loop.
+static bool isBackEdge(const CFGBlock *Block) {
+ assert(Block != nullptr);
+ return Block->LoopTarget != nullptr;
+}
+
+// Returns the predecessor to `Block` that is a "back edge", if one exists.
+//
+// If this function returns a non-null pointer, that means `Block` dominates the
+// back edge block. (That is, all paths from the entry block to the back edge
+// block must go through `Block`.) It also means that there are only two
+// predecessors; the other is along the path from the entry block to `Block`.
+static const CFGBlock *findBackEdge(const CFGBlock *Block) {
+ assert(Block != nullptr);
+
+ const CFGBlock *BackEdge = nullptr;
+ for (const auto &Pred : Block->preds()) {
+ if (!Pred.isReachable())
+ continue;
+ if (isBackEdge(Pred)) {
+ assert(BackEdge == nullptr);
+ assert(Block->pred_size() == 2);
+ BackEdge = Pred;
+ }
+ }
+ return BackEdge;
+}
+
/// Computes the input state for a given basic block by joining the output
/// states of its predecessors.
///
@@ -199,6 +228,21 @@
}
}
+ // If we are at the start of a loop, we will have two precessors, but we don't
+ // want to join these two predecessors. Instead, we want to take the back edge
+ // block (i.e. the result of the previous iteration) and use that directly as
+ // the input block.
+ //
+ // For the first iteration of loop, the "zeroth" iteration state is set up by
+ // `prepareBackEdges`.
+ if (const CFGBlock *BackEdge = findBackEdge(&Block)) {
+ const llvm::Optional<TypeErasedDataflowAnalysisState> &MaybePredState =
+ BlockStates[BackEdge->getBlockID()];
+ assert(MaybePredState.has_value());
+ assert(BackEdge->getTerminatorStmt() == nullptr);
+ return *MaybePredState;
+ }
+
llvm::Optional<TypeErasedDataflowAnalysisState> MaybeState;
bool ApplyBuiltinTransfer = Analysis.applyBuiltinTransfer();
@@ -311,6 +355,23 @@
HandleTransferredStmt) {
TypeErasedDataflowAnalysisState State =
computeBlockInputState(CFCtx, BlockStates, Block, InitEnv, Analysis);
+
+ // The back edge block is where we perform a widen, allowing certain analyses
+ // to converge in finite time. The `PrevState` of the previous iteration of
+ // the loop is widened to subsume the input `State`.
+ //
+ // FIXME: Allow users to configure a certain number of iterations to unroll,
+ // to allow higher precision in their analyses.
+ if (isBackEdge(&Block)) {
+ assert(Block.empty());
+ auto PrevState = BlockStates[Block.getBlockID()];
+ assert(PrevState.has_value());
+ Analysis.widenTypeErased(PrevState->Lattice, State.Lattice);
+ // FIXME: Add a widen operator to the `Environment`.
+ PrevState->Env.join(State.Env, Analysis);
+ return *PrevState;
+ }
+
for (const CFGElement &Element : Block) {
switch (Element.getKind()) {
case CFGElement::Statement:
@@ -329,6 +390,34 @@
return State;
}
+// Given a `Block` with its state set in `BlockStates`, copies this state to the
+// back edge of all successors that are the first block of a loop.
+static void prepareBackEdges(
+ const CFGBlock &Block,
+ llvm::MutableArrayRef<llvm::Optional<TypeErasedDataflowAnalysisState>>
+ BlockStates) {
+ const auto &State = BlockStates[Block.getBlockID()];
+ assert(State.has_value());
+
+ for (const auto &Succ : Block.succs()) {
+ if (!Succ.isReachable())
+ continue;
+ if (const CFGBlock *BackEdge = findBackEdge(Succ);
+ BackEdge != nullptr && BackEdge != &Block) {
+ // `Succ` is the first block of the loop body, `Block` is the "entrance"
+ // to the loop, and `BackEdge` is the back-edge of the loop.
+ //
+ // `Block` represents the input state to the loop before any iterations
+ // have been executed. By copying this state to the back edge, we can
+ // consistently use the back edge block as the input state to the loop,
+ // even on its first iteration. This subsequently handles nested loops; if
+ // the outer loop requires additional passes to converge, the inner loop
+ // is correctly "reinitialized" once `Block` is transfered.
+ BlockStates[BackEdge->getBlockID()] = State;
+ }
+ }
+}
+
llvm::Expected<std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>>>
runTypeErasedDataflowAnalysis(
const ControlFlowContext &CFCtx, TypeErasedDataflowAnalysis &Analysis,
@@ -387,6 +476,9 @@
continue;
Worklist.enqueueSuccessors(Block);
+
+ // If we are about to enter into a loop, we set up our back edge blocks.
+ prepareBackEdges(*Block, BlockStates);
}
// FIXME: Consider evaluating unreachable basic blocks (those that have a
// state set to `llvm::None` at this point) to also analyze dead code.
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
