[clang][dataflow][NFC] Eliminate StmtToEnvMap interface.

[mboehme]

Summary

Instead, we turn StmtToEnvMap into a concrete class with the implementation that used to live in StmtToEnvMapImpl.

The layering issue that originally required the indirection through the
StmtToEnvMap interface no longer exists.

[gribozavr2]

clang/include/clang/Analysis/FlowSensitive/Transfer.h

31

Could you move the comment to the new declaration of this function?

[mboehme]

Add back comment that I inadvertently deleted.

[mboehme]

clang/include/clang/Analysis/FlowSensitive/Transfer.h

31

Oops, done. Thanks for catching!

clang/lib/Analysis/FlowSensitive/Transfer.cpp

135

I'm not changing the return type of getEnvironment() to a reference because https://reviews.llvm.org/D146514 (in review) makes a change that will cause getEnvironment() to return nullptr if S is not reachable, and I want to avoid churn on the return type. (There will be a conflict between the two changes anyway, and I'll deal with that once the first of the changes has landed.)

[mboehme]

After some offline discussion with reviewers, we've come to the conclusion that AnalysisContext isn't a sufficiently clear abstraction to warrant putting it in a header.

For the time being, I'll therefore pursue the less ambitious approach of simply eliminating the StmtToEnvMap interface and instead turning it into a concrete class with the implementation that used to be in StmtToEnvMapImpl.

[mboehme]

Pursue a less ambitious approach, as described in the previous comment.

[mboehme]

@gribozavr2 @xazax.hun Just wanted to confirm that you still regard this as ready to land now that I've changed the patch as we discussed offline?

[gribozavr2]

clang/include/clang/Analysis/FlowSensitive/Transfer.h

31

Drop virtual?

[ymandel]

thanks!

clang/include/clang/Analysis/FlowSensitive/Transfer.h

32–36

Nit: why inline vs putting the definition in Transfer.cpp? I don't have a good sense for the size cutoff on this decision but if it's only used there, then might make sense just to keep the header leaner.

[xazax.hun]

Thanks!

[mboehme]

Rebase to head

[mboehme]

Changes in response to review comments

[mboehme]

clang/include/clang/Analysis/FlowSensitive/Transfer.h

31

Duh. Thanks for catching. Done!

32–36

Good point. Done.

clang/include/clang/Analysis/FlowSensitive/Transfer.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TRANSFER_H
 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TRANSFER_H
 
 #include "clang/AST/Stmt.h"
 #include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
+#include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
 
 namespace clang {
 namespace dataflow {
 
-/// Maps statements to the environments of basic blocks that contain them.
-class StmtToEnvMap {
-public:
-  virtual ~StmtToEnvMap() = default;
-
-  /// Returns the environment of the basic block that contains `S` or nullptr if
-  /// there isn't one.
-  /// FIXME: Ensure that the result can't be null and return a const reference.
-  virtual const Environment *getEnvironment(const Stmt &S) const = 0;
-};
-
 /// Evaluates `S` and updates `Env` accordingly.
 ///
 /// Requirements:
 ///
 ///  `S` must not be `ParenExpr` or `ExprWithCleanups`.
-void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env);
+void transfer(const AnalysisContext &AC, const Stmt &S, Environment &Env);
 
 } // namespace dataflow
 } // namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TRANSFER_H

clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h

struct TypeErasedDataflowAnalysisState {
 
   /// Model of the state of the program (store and heap).
   Environment Env;
 
   TypeErasedDataflowAnalysisState(TypeErasedLattice Lattice, Environment Env)
       : Lattice(std::move(Lattice)), Env(std::move(Env)) {}
 };
 
+/// Holds data structures required for running dataflow analysis.
+struct AnalysisContext {
+  AnalysisContext(const ControlFlowContext &CFCtx,
+                  TypeErasedDataflowAnalysis &Analysis,
+                  const Environment &InitEnv,
+                  llvm::ArrayRef<std::optional<TypeErasedDataflowAnalysisState>>
+                      BlockStates)
+      : CFCtx(CFCtx), Analysis(Analysis), InitEnv(InitEnv),
+        BlockStates(BlockStates) {}
+
+  /// Contains the CFG being analyzed.
+  const ControlFlowContext &CFCtx;
+  /// The analysis to be run.
+  TypeErasedDataflowAnalysis &Analysis;
+  /// Initial state to start the analysis.
+  const Environment &InitEnv;
+  /// Stores the state of a CFG block if it has been evaluated by the analysis.
+  /// The indices correspond to the block IDs.
+  llvm::ArrayRef<std::optional<TypeErasedDataflowAnalysisState>> BlockStates;
+};
+
 /// Transfers the state of a basic block by evaluating each of its elements in
 /// the context of `Analysis` and the states of its predecessors that are
 /// available in `BlockStates`. `PostVisitCFG` (if provided) will be applied to
 /// each element in the block, after it is evaluated.
 ///
 /// Requirements:
 ///
 ///   All predecessors of `Block` except those with loop back edges must have

clang/lib/Analysis/FlowSensitive/Transfer.cpp

 //===-- Transfer.cpp --------------------------------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 //
 //  This file defines transfer functions that evaluate program statements and
 //  update an environment accordingly.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Analysis/FlowSensitive/Transfer.h"
+#include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclBase.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/ExprCXX.h"
 #include "clang/AST/OperationKinds.h"
 #include "clang/AST/Stmt.h"
 #include "clang/AST/StmtVisitor.h"
static Value *maybeUnpackLValueExpr(const Expr &E, Environment &Env) {
 
   auto &UnpackedVal = unpackValue(*B, Env);
   if (&UnpackedVal == Val)
     return Val;
   Env.setValue(*Loc, UnpackedVal);
   return &UnpackedVal;
 }
 
+static const Environment *getEnvironment(const Stmt &S,
+                                         const AnalysisContext &AC) {
+  auto BlockIt = AC.CFCtx.getStmtToBlock().find(&ignoreCFGOmittedNodes(S));
+  assert(BlockIt != AC.CFCtx.getStmtToBlock().end());
+  const auto &State = AC.BlockStates[BlockIt->getSecond()->getBlockID()];
+  assert(State);
+  return &State->Env;
+}
+
 class TransferVisitor : public ConstStmtVisitor<TransferVisitor> {
 public:
-  TransferVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env)
-      : StmtToEnv(StmtToEnv), Env(Env) {}
+  TransferVisitor(const AnalysisContext &AC, Environment &Env)
+      : AC(AC), Env(Env) {}
 
   void VisitBinaryOperator(const BinaryOperator *S) {
     const Expr *LHS = S->getLHS();
     assert(LHS != nullptr);
 
     const Expr *RHS = S->getRHS();
     assert(RHS != nullptr);
 
void VisitExprWithCleanups(const ExprWithCleanups *S) {
     Visit(SubExpr);
   }
 
 private:
   BoolValue &getLogicOperatorSubExprValue(const Expr &SubExpr) {
     // `SubExpr` and its parent logic operator might be part of different basic
     // blocks. We try to access the value that is assigned to `SubExpr` in the
     // corresponding environment.
-    if (const Environment *SubExprEnv = StmtToEnv.getEnvironment(SubExpr)) {
+    if (const Environment *SubExprEnv = getEnvironment(SubExpr, AC)) {
       if (auto *Val = dyn_cast_or_null<BoolValue>(
               SubExprEnv->getValue(SubExpr, SkipPast::Reference)))
         return *Val;
     }
 
     if (Env.getStorageLocation(SubExpr, SkipPast::None) == nullptr) {
       // Sub-expressions that are logic operators are not added in basic blocks
       // (e.g. see CFG for `bool d = a && (b || c);`). If `SubExpr` is a logic
void transferInlineCall(const E *S, const FunctionDecl *F) {
     assert(ExitBlock < BlockToOutputState->size());
 
     auto ExitState = (*BlockToOutputState)[ExitBlock];
     assert(ExitState);
 
     Env.popCall(ExitState->Env);
   }
 
-  const StmtToEnvMap &StmtToEnv;
+  const AnalysisContext &AC;
   Environment &Env;
 };
 
-void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env) {
-  TransferVisitor(StmtToEnv, Env).Visit(&S);
+void transfer(const AnalysisContext &AC, const Stmt &S, Environment &Env) {
+  TransferVisitor(AC, Env).Visit(&S);
 }
 
 } // namespace dataflow
 } // namespace clang

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Error.h"
 
 #define DEBUG_TYPE "clang-dataflow"
 
 namespace clang {
 namespace dataflow {
 
-class StmtToEnvMapImpl : public StmtToEnvMap {
-public:
-  StmtToEnvMapImpl(
-      const ControlFlowContext &CFCtx,
-      llvm::ArrayRef<std::optional<TypeErasedDataflowAnalysisState>>
-          BlockToState)
-      : CFCtx(CFCtx), BlockToState(BlockToState) {}
-
-  const Environment *getEnvironment(const Stmt &S) const override {
-    auto BlockIt = CFCtx.getStmtToBlock().find(&ignoreCFGOmittedNodes(S));
-    assert(BlockIt != CFCtx.getStmtToBlock().end());
-    const auto &State = BlockToState[BlockIt->getSecond()->getBlockID()];
-    assert(State);
-    return &State->Env;
-  }
-
-private:
-  const ControlFlowContext &CFCtx;
-  llvm::ArrayRef<std::optional<TypeErasedDataflowAnalysisState>> BlockToState;
-};
-
 /// Returns the index of `Block` in the successors of `Pred`.
 static int blockIndexInPredecessor(const CFGBlock &Pred,
                                    const CFGBlock &Block) {
   auto BlockPos = llvm::find_if(
       Pred.succs(), [&Block](const CFGBlock::AdjacentBlock &Succ) {
         return Succ && Succ->getBlockID() == Block.getBlockID();
       });
   return BlockPos - Pred.succ_begin();

 // represents whether the condition was true or false.
 using TerminatorVisitorRetTy = std::pair<const Expr *, bool>;
 
 /// Extends the flow condition of an environment based on a terminator
 /// statement.
 class TerminatorVisitor
     : public ConstStmtVisitor<TerminatorVisitor, TerminatorVisitorRetTy> {
 public:
-  TerminatorVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env,
+  TerminatorVisitor(const AnalysisContext &AC, Environment &Env,
                     int BlockSuccIdx)
-      : StmtToEnv(StmtToEnv), Env(Env), BlockSuccIdx(BlockSuccIdx) {}
+      : AC(AC), Env(Env), BlockSuccIdx(BlockSuccIdx) {}
 
   TerminatorVisitorRetTy VisitIfStmt(const IfStmt *S) {
     auto *Cond = S->getCond();
     assert(Cond != nullptr);
     return extendFlowCondition(*Cond);
   }
 
   TerminatorVisitorRetTy VisitWhileStmt(const WhileStmt *S) {
VisitConditionalOperator(const ConditionalOperator *S) {
     assert(Cond != nullptr);
     return extendFlowCondition(*Cond);
   }
 
 private:
   TerminatorVisitorRetTy extendFlowCondition(const Expr &Cond) {
     // The terminator sub-expression might not be evaluated.
     if (Env.getStorageLocation(Cond, SkipPast::None) == nullptr)
-      transfer(StmtToEnv, Cond, Env);
+      transfer(AC, Cond, Env);
 
     // FIXME: The flow condition must be an r-value, so `SkipPast::None` should
     // suffice.
     auto *Val =
         cast_or_null<BoolValue>(Env.getValue(Cond, SkipPast::Reference));
     // Value merging depends on flow conditions from different environments
     // being mutually exclusive -- that is, they cannot both be true in their
     // entirety (even if they may share some clauses). So, we need *some* value
if (BlockSuccIdx == 1) {
       Val = &Env.makeNot(*Val);
       ConditionValue = false;
     }
 
     Env.addToFlowCondition(*Val);
     return {&Cond, ConditionValue};
   }
 
-  const StmtToEnvMap &StmtToEnv;
+  const AnalysisContext &AC;
   Environment &Env;
   int BlockSuccIdx;
 };
 
-/// Holds data structures required for running dataflow analysis.
-struct AnalysisContext {
-  AnalysisContext(const ControlFlowContext &CFCtx,
-                  TypeErasedDataflowAnalysis &Analysis,
-                  const Environment &InitEnv,
-                  llvm::ArrayRef<std::optional<TypeErasedDataflowAnalysisState>>
-                      BlockStates)
-      : CFCtx(CFCtx), Analysis(Analysis), InitEnv(InitEnv),
-        BlockStates(BlockStates) {}
-
-  /// Contains the CFG being analyzed.
-  const ControlFlowContext &CFCtx;
-  /// The analysis to be run.
-  TypeErasedDataflowAnalysis &Analysis;
-  /// Initial state to start the analysis.
-  const Environment &InitEnv;
-  /// Stores the state of a CFG block if it has been evaluated by the analysis.
-  /// The indices correspond to the block IDs.
-  llvm::ArrayRef<std::optional<TypeErasedDataflowAnalysisState>> BlockStates;
-};
-
 /// 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 `AC.BlockStates` that are set to
 ///   `std::nullopt` represent basic blocks that are not evaluated yet.
for (const CFGBlock *Pred : Preds) {
     const std::optional<TypeErasedDataflowAnalysisState> &MaybePredState =
         AC.BlockStates[Pred->getBlockID()];
     if (!MaybePredState)
       continue;
 
     TypeErasedDataflowAnalysisState PredState = *MaybePredState;
     if (Analysis.builtinOptions()) {
       if (const Stmt *PredTerminatorStmt = Pred->getTerminatorStmt()) {
-        const StmtToEnvMapImpl StmtToEnv(AC.CFCtx, AC.BlockStates);
         auto [Cond, CondValue] =
-            TerminatorVisitor(StmtToEnv, PredState.Env,
+            TerminatorVisitor(AC, PredState.Env,
                               blockIndexInPredecessor(*Pred, Block))
                 .Visit(PredTerminatorStmt);
         if (Cond != nullptr)
           // FIXME: Call transferBranchTypeErased even if BuiltinTransferOpts
           // are not set.
           Analysis.transferBranchTypeErased(CondValue, Cond, PredState.Lattice,
                                             PredState.Env);
       }

 }
 
 /// Built-in transfer function for `CFGStmt`.
 void builtinTransferStatement(const CFGStmt &Elt,
                               TypeErasedDataflowAnalysisState &InputState,
                               AnalysisContext &AC) {
   const Stmt *S = Elt.getStmt();
   assert(S != nullptr);
-  transfer(StmtToEnvMapImpl(AC.CFCtx, AC.BlockStates), *S, InputState.Env);
+  transfer(AC, *S, InputState.Env);
 }
 
 /// Built-in transfer function for `CFGInitializer`.
 void builtinTransferInitializer(const CFGInitializer &Elt,
                                 TypeErasedDataflowAnalysisState &InputState) {
   const CXXCtorInitializer *Init = Elt.getInitializer();
   assert(Init != nullptr);