[clang][dataflow] Restructure loops to call widen on back edges

[li.zhe.hua]

Summary

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 issue: #56931

Depends on D131645

[ymandel]

Nice!

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

180

Might it be worth simply returning the backedge when you find it? Or is the assertion (above) sufficiently important to keep it as is?

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

275

Might a (googletest) assertion here be better than llvm::cantFail? I would think that this line is the crux of checking whether it converges or not.

[li.zhe.hua]

Address comments

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

180

So, I couldn't prove to myself that a block couldn't have two backedge predecessors from staring at the CFG code, but it seems conceptually unlikely enough that I'm OK simplifying this.

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

275

Ah, yes. I hadn't thought to look for llvm::Expected matchers; good call.

[xazax.hun]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

168–169

Is this also true when we have multiple continue statements in the loop?

231–237

Could you elaborate on this? Let's consider this loop:

Pred
  |
  v
LoopHeader <---BackEdge

Do we ignore the state coming from Pred on purpose? Is that sound?

I would expect the analysis to always compute join(PredState, BackEdgeState), and I would expect the widening to happen between the previous iteration of BackEdgeState and the current iteration of BackEdgeState. So, I wonder if we already invoke the widening operator along back edges, wouldn't the regular logic work just fine? Do I miss something?

[li.zhe.hua]

Fix incorrect assumption that back edge blocks have an empty body.

[li.zhe.hua]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

168–169

Yes. The end of the loop, and each of the continue statements, target the back edge block. They all get funneled through that back edge to Block, such that Block only has two predecessors. However, I haven't verified this in the CFG code, only by not finding a counterexample.

231–237

Do we ignore the state coming from Pred on purpose? Is that sound?

We don't, and this is what the comment

// For the first iteration of loop, the "zeroth" iteration state is set up by
// `prepareBackEdges`.

failed to explain. After transferring PredState, we copy PredState into BackEdgeState, which is done in prepareBackEdges.

I would expect the analysis to always compute join(PredState, BackEdgeState)

I'm not sure I see that we should always join PredState and BackEdgeState. Execution doesn't go from Pred into the Nth iteration of the loop, it only goes from Pred into the first iteration of the loop, e.g. the predecessor for the 4th iteration of the loop is only the back-edge from the 3rd iteration of the loop, not Pred.

Let me know if this makes sense.

[xazax.hun]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

231–237

I'm not sure I see that we should always join PredState and BackEdgeState. Execution doesn't go from Pred into the Nth iteration of the loop, it only goes from Pred into the first iteration of the loop, e.g. the predecessor for the 4th iteration of the loop is only the back-edge from the 3rd iteration of the loop, not Pred.

Let me know if this makes sense.

The analysis state of the dataflow analysis supposed to overestimate all of the paths. Consider the following loop and imagine we want to calculate intervals for integer variables:

int i = 0;
while (...) {
  [[program point A]];
  ++i;
}

During the analysis of this loop, the value i ==0 flows to [[program point A]]. This is the motivation to join the state from the back edge and from PredState. As far as I understand, you want to achieve this by copying PredState to the BackEdgeState before the first iteration. But this also means that we will use the widening operator to combine PredState with the state after N iterations instead of the regular join operation. I am not entirely sure whether these two approaches always produce the same results.

[xazax.hun]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

231–237

A contrived example (just came up with this in a couple minutes so feel free to double check if it is OK):
Consider:

int i = 0;
while (...) {
  if (i == 0)
    i = -2;
  ++i;
}

Some states:

PredState = i : [0, 0]
BackEdgeState (after first iteration) = i : [-1, -1]

And the results of join vs widen:

PredState.join(BackEdgeState) = i : [-1, 0]
PredState.widen(BackEdge) = i : [-inf, 0]

The extra widening with the PredState can result in extra imprecision.

[sgatev]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

157

Let's start function comments with /// throughout the file.

164

167–168

168–169

Does that hold for back edges stemming from goto statements?

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

269

There's already a set of "widening" tests - http://google3/third_party/llvm/llvm-project/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp;l=527-712;rcl=462638952

What do you think about refactoring those so that we have tests that exercise the framework with both join and widen?

[li.zhe.hua]

Address comments

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

168–169

Ah, goto does throw a wrench in all of this. Specifically, it is problematic only for do ... while loops, where the labeled statement is the first statement of the do block.

I took out the sentence, took out the assert, and added a FIXME for prepareBackEdges.

231–237

So, my understanding is that widening introduces imprecision as a trade-off for convergence. Yes, in the contrived example, joining converges after a few iterations, but in other cases it never converges.

---

Looking at the Rival and Yi book, there are no intervening joins with the predecessor for the first loop as we analyze the loop. This is roughly where I drew from in terms of this implementation.

analysis(iter{p}, a) = { R <- a;
                         repeat
                             T <- R;
                             R <- widen(R, analysis(p, R));
                         until inclusion(R, T)
                         return T;

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

269

This commit implements widening only for the lattice. Those tests use the NoopLattice, so their behavior is not expected to change with this commit. Splitting merge into a join and widen is out-of-scope for this commit, and is what I am hoping to work on next.

[xazax.hun]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

231–237

So, my understanding is that widening introduces imprecision as a trade-off for convergence. Yes, in the contrived example, joining converges after a few iterations, but in other cases it never converges.

In my example I do not advocate for NOT doing widening. I am advocating for not applying the widening operator with the loop pre-state and the loop iteration state as operands. My example demonstrates how that introduces additional imprecision. Not using the widening operator for those two states, only between loop iterations would still ensure convergence, but would give you more precision. My argument is, using widening in that step is not required for the convergence but we do pay for it in precision. Or do you have an example where you need widening for those two specific states?

Looking at the Rival and Yi book, there are no intervening joins with the predecessor for the first loop as we analyze the loop. This is roughly where I drew from in terms of this implementation.

Later in the book, they talk about loop unrolling where we don't use the widening operator in the first couple of iterations. The same imprecision I was talking about here could also be solved by unrolling the first iteration. I believe the book is might not talk about this technique because the unrolling subsumes it.

The main reason I am advocating for this, because I believe if we are willing to accept the join there, we would no longer need to prepare the back edges and it would simplify the implementation while improving the precision of the analysis.

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

private:
   }
 
   const StmtToEnvMap &StmtToEnv;
   Environment &Env;
   int BlockSuccIdx;
   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.
 ///
 /// Requirements:
 ///
 ///   All predecessors of `Block` except those with loop back edges must have
 ///   already been transferred. States in `BlockStates` that are set to
 ///   `llvm::None` represent basic blocks that are not evaluated yet.
if (Block.getTerminator().isTemporaryDtorsBranch()) {
     // See `NoreturnDestructorTest` for concrete examples.
     if (Block.succ_begin()->getReachableBlock()->hasNoReturnElement()) {
       auto StmtBlock = CFCtx.getStmtToBlock().find(Block.getTerminatorStmt());
       assert(StmtBlock != CFCtx.getStmtToBlock().end());
       Preds.erase(StmtBlock->getSecond());
     }
   }
 
+  // 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();
 
   for (const CFGBlock *Pred : Preds) {
     // Skip if the `Block` is unreachable or control flow cannot get past it.
     if (!Pred || Pred->hasNoReturnElement())
       continue;
 
TypeErasedDataflowAnalysisState transferBlock(
     llvm::ArrayRef<llvm::Optional<TypeErasedDataflowAnalysisState>> BlockStates,
     const CFGBlock &Block, const Environment &InitEnv,
     TypeErasedDataflowAnalysis &Analysis,
     std::function<void(const CFGStmt &,
                        const TypeErasedDataflowAnalysisState &)>
         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:
       transferCFGStmt(CFCtx, BlockStates, *Element.getAs<CFGStmt>(), Analysis,
                       State, HandleTransferredStmt);
       break;
     case CFGElement::Initializer:
       if (Analysis.applyBuiltinTransfer())
         transferCFGInitializer(*Element.getAs<CFGInitializer>(), State);
       break;
     default:
       // FIXME: Evaluate other kinds of `CFGElement`.
       break;
     }
   }
   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,
     const Environment &InitEnv,
     std::function<void(const CFGStmt &,
                        const TypeErasedDataflowAnalysisState &)>
         PostVisitStmt) {
   PostOrderCFGView POV(&CFCtx.getCFG());
while (const CFGBlock *Block = Worklist.dequeue()) {
 
     BlockStates[Block->getBlockID()] = std::move(NewBlockState);
 
     // Do not add unreachable successor blocks to `Worklist`.
     if (Block->hasNoReturnElement())
       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.
 
   if (PostVisitStmt) {
     for (const CFGBlock *Block : CFCtx.getCFG()) {
       // Skip blocks that were not evaluated.
       if (!BlockStates[Block->getBlockID()])

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

 
 namespace {
 
 using namespace clang;
 using namespace dataflow;
 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;
 
 template <typename AnalysisT>
 llvm::Expected<std::vector<
     llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>>
 runAnalysis(llvm::StringRef Code, AnalysisT (*MakeAnalysis)(ASTContext &)) {
   std::unique_ptr<ASTUnit> AST =
std::string Code = R"(
     }
   )";
   auto Res = runAnalysis<NonConvergingAnalysis>(
       Code, [](ASTContext &C) { return NonConvergingAnalysis(C); });
   EXPECT_EQ(llvm::toString(Res.takeError()),
             "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;
 
   bool operator==(const FunctionCallLattice &Other) const {
     return CalledFunctions == Other.CalledFunctions;
   }
 
   LatticeJoinEffect join(const FunctionCallLattice &Other) {