[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

276

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

276

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?

226–232

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.

226–232

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

226–232

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

226–232

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

270

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.

226–232

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

270

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

226–232

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 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 comes from 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`.
+static const CFGBlock *findBackEdge(const CFGBlock *Block) {
+  assert(Block != nullptr);
+  for (const auto &Pred : Block->preds()) {
+    if (!Pred.isReachable())
+      continue;
+    if (isBackEdge(Pred))
+      return Pred;
+  }
+  return nullptr;
+}
+
 /// 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());
     }
   }
 
   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;
 
     // Skip if `Pred` was not evaluated yet. This could happen if `Pred` has a
-    // loop back edge to `Block`.
+    // a noreturn element.
     const llvm::Optional<TypeErasedDataflowAnalysisState> &MaybePredState =
         BlockStates[Pred->getBlockID()];
     if (!MaybePredState)
       continue;
 
     TypeErasedDataflowAnalysisState PredState = MaybePredState.value();
     if (ApplyBuiltinTransfer) {
       if (const Stmt *PredTerminatorStmt = Pred->getTerminatorStmt()) {
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);
+
   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;
     }
   }
+
+  // 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)) {
+    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;
+  }
+
   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.
+///
+/// FIXME: This is unsound for a corner case where a `goto` jumps to the start
+/// of a `do ... while` 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

 #include <vector>
 
 namespace {
 
 using namespace clang;
 using namespace dataflow;
 using namespace test;
 using namespace ast_matchers;
+using ::llvm::HasValue;
 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, WhileLoopConvergesOnWidenAnalysis) {
+  std::string Code = R"(
+    void target() {
+      while(true) {}
+    }
+  )";
+  EXPECT_THAT_EXPECTED(
+      runAnalysis<ConvergesOnWidenAnalysis>(
+          Code, [](ASTContext &C) { return ConvergesOnWidenAnalysis(C); }),
+      HasValue(AllOf(SizeIs(4), Each(Optional(_)))));
+}
+
+TEST(DataflowAnalysisTest, ForLoopConvergesOnWidenAnalysis) {
+  std::string Code = R"(
+    void target() {
+      for (int i = 0; i > -1; ++i) {}
+    }
+  )";
+  EXPECT_THAT_EXPECTED(
+      runAnalysis<ConvergesOnWidenAnalysis>(
+          Code, [](ASTContext &C) { return ConvergesOnWidenAnalysis(C); }),
+      HasValue(AllOf(SizeIs(5), 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) {