[clang][dataflow] Add support for global storage values

[sgatev]

Summary

This is part of the implementation of the dataflow analysis framework.
See "[RFC] A dataflow analysis framework for Clang AST" on cfe-dev.

[ymandel]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

74–77

80

maybe clarify that it intializes both declarations that are present *in* the substatements and those referenced *from* the sub statements?

clang/lib/Analysis/FlowSensitive/Transfer.cpp

140

305

should this be in the else branch? As is, Loc looks unused if the condition is true.

[sgatev]

Address reviewers' comments.

[sgatev]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

80

Updated.

clang/lib/Analysis/FlowSensitive/Transfer.cpp

305

Yeap, moved it.

[xazax.hun]

Shouldn't there be a functionality to invalidate all the globals at every function call by default?

clang/lib/Analysis/FlowSensitive/Transfer.cpp

141

Do we expect to ever see a global declaration in a transfer function? Or is this for static locals? If it is for the latter, I'd adjust the comment.

[sgatev]

I think we should provide such functionality and it probably should also apply to some of the pointer and reference values. Not sure what the default should be, but having the ability to choose the level of soundness for certain analyses is valuable so I think both options should be possible. We don't have that implemented yet and I think it might be better to consider this together with other improvements that we want to make such as lazy value initialization. Would you be ok with deferring this for now? I noted it with a FIXME in the code.

clang/lib/Analysis/FlowSensitive/Transfer.cpp

141

It's for static locals. Updated the comment.

[sgatev]

Address reviewers' comments.

[xazax.hun]

In D120149#3333056, @sgatev wrote:

I think we should provide such functionality and it probably should also apply to some of the pointer and reference values. Not sure what the default should be, but having the ability to choose the level of soundness for certain analyses is valuable so I think both options should be possible. We don't have that implemented yet and I think it might be better to consider this together with other improvements that we want to make such as lazy value initialization. Would you be ok with deferring this for now? I noted it with a FIXME in the code.

I think the default should be as sound as reasonably possible. If we don't do any invalidations, I'd like to see some sort of warning somewhere so early users are aware of the behavior. I'm not sure what is the best place to put the warning, maybe to the documentation of a class? With that warning in place, I think it is ok to commit this.

[sgatev]

Address reviewers' comments.

clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h

enum class SkipPast {
   /// An optional reference should be skipped past.
   Reference,
   /// An optional reference should be skipped past, then an optional pointer
   /// should be skipped past.
   ReferenceThenPointer,
 };
 
 /// Holds the state of the program (store and heap) at a given program point.
+///
+/// WARNING: Symbolic values that are created by the environment for static
+/// local and global variables are not currently invalidated on function calls.
+/// This is unsound and should be taken into account when designing dataflow
+/// analyses.
 class Environment {
 public:
   /// Supplements `Environment` with non-standard comparison and join
   /// operations.
   class ValueModel {
   public:
     virtual ~ValueModel() = default;
 

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/Type.h"
 #include "clang/Analysis/FlowSensitive/DataflowLattice.h"
 #include "clang/Analysis/FlowSensitive/StorageLocation.h"
 #include "clang/Analysis/FlowSensitive/Value.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/Support/ErrorHandling.h"
+#include <cassert>
 #include <memory>
 #include <utility>
 
 namespace clang {
 namespace dataflow {
 
 /// Returns a map consisting of key-value entries that are present in both maps.
 template <typename K, typename V>
if (auto *IndVal1 = dyn_cast<IndirectionValue>(Val1)) {
     auto *IndVal2 = cast<IndirectionValue>(Val2);
     assert(IndVal1->getKind() == IndVal2->getKind());
     return &IndVal1->getPointeeLoc() == &IndVal2->getPointeeLoc();
   }
 
   return Model.compareEquivalent(Type, *Val1, *Val2);
 }
 
+/// Initializes a global storage value.
+static void initGlobalVar(const VarDecl &D, Environment &Env) {
+  if (!D.hasGlobalStorage() ||
+      Env.getStorageLocation(D, SkipPast::None) != nullptr)
+    return;
+
+  auto &Loc = Env.createStorageLocation(D);
+  Env.setStorageLocation(D, Loc);
+  if (auto *Val = Env.createValue(D.getType()))
+    Env.setValue(Loc, *Val);
+}
+
+/// Initializes a global storage value.
+static void initGlobalVar(const Decl &D, Environment &Env) {
+  if (auto *V = dyn_cast<VarDecl>(&D))
+    initGlobalVar(*V, Env);
+}
+
+/// Initializes global storage values that are declared or referenced from
+/// sub-statements of `S`.
+// FIXME: Add support for resetting globals after function calls to enable
+// the implementation of sound analyses.
+static void initGlobalVars(const Stmt &S, Environment &Env) {
+  for (auto *Child : S.children()) {
+    if (Child != nullptr)
+      initGlobalVars(*Child, Env);
+  }
+
+  if (auto *DS = dyn_cast<DeclStmt>(&S)) {
+    if (DS->isSingleDecl()) {
+      const auto &D = *cast<VarDecl>(DS->getSingleDecl());
+      initGlobalVar(D, Env);
+    } else {
+      for (auto *D : DS->getDeclGroup())
+        initGlobalVar(*D, Env);
+    }
+  } else if (auto *E = dyn_cast<DeclRefExpr>(&S)) {
+    initGlobalVar(*E->getDecl(), Env);
+  } else if (auto *E = dyn_cast<MemberExpr>(&S)) {
+    initGlobalVar(*E->getMemberDecl(), Env);
+  }
+}
+
 Environment::Environment(DataflowAnalysisContext &DACtx,
                          const DeclContext &DeclCtx)
     : Environment(DACtx) {
   if (const auto *FuncDecl = dyn_cast<FunctionDecl>(&DeclCtx)) {
+    assert(FuncDecl->getBody() != nullptr);
+    initGlobalVars(*FuncDecl->getBody(), *this);
     for (const auto *ParamDecl : FuncDecl->parameters()) {
       assert(ParamDecl != nullptr);
       auto &ParamLoc = createStorageLocation(*ParamDecl);
       setStorageLocation(*ParamDecl, ParamLoc);
       if (Value *ParamVal = createValue(ParamDecl->getType()))
         setValue(ParamLoc, *ParamVal);
     }
   }

clang/lib/Analysis/FlowSensitive/Transfer.cpp

if (S->getDecl()->getType()->isReferenceType()) {
       Env.setValue(Loc, Val);
     }
   }
 
   void VisitDeclStmt(const DeclStmt *S) {
     // Group decls are converted into single decls in the CFG so the cast below
     // is safe.
     const auto &D = *cast<VarDecl>(S->getSingleDecl());
+
+    // Static local vars are already initialized in `Environment`.
+    if (D.hasGlobalStorage())
+      return;
+
     auto &Loc = Env.createStorageLocation(D);
     Env.setStorageLocation(D, Loc);
 
     const Expr *InitExpr = D.getInit();
     if (InitExpr == nullptr) {
       // No initializer expression - associate `Loc` with a new value.
       if (Value *Val = Env.createValue(D.getType()))
         Env.setValue(Loc, *Val);
public:
   void VisitMemberExpr(const MemberExpr *S) {
     ValueDecl *Member = S->getMemberDecl();
     assert(Member != nullptr);
 
     // FIXME: Consider assigning pointer values to function member expressions.
     if (Member->isFunctionOrFunctionTemplate())
       return;
 
+    if (auto *D = dyn_cast<VarDecl>(Member)) {
+      if (D->hasGlobalStorage()) {
+        auto *VarDeclLoc = Env.getStorageLocation(*D, SkipPast::None);
+        if (VarDeclLoc == nullptr)
+          return;
+
+        if (VarDeclLoc->getType()->isReferenceType()) {
+          Env.setStorageLocation(*S, *VarDeclLoc);
+        } else {
+          auto &Loc = Env.createStorageLocation(*S);
+          Env.setStorageLocation(*S, Loc);
+          Env.setValue(Loc, Env.takeOwnership(
+                                std::make_unique<ReferenceValue>(*VarDeclLoc)));
+        }
+        return;
+      }
+    }
+
     // The receiver can be either a value or a pointer to a value. Skip past the
     // indirection to handle both cases.
     auto *BaseLoc = cast_or_null<AggregateStorageLocation>(
         Env.getStorageLocation(*S->getBase(), SkipPast::ReferenceThenPointer));
     if (BaseLoc == nullptr)
       return;
 
     // FIXME: Add support for union types.

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

runDataflow(Code,
                 const auto *BarVal = dyn_cast_or_null<NegationValue>(
                     Env.getValue(*BarDecl, SkipPast::None));
                 ASSERT_THAT(BarVal, NotNull());
 
                 EXPECT_EQ(&BarVal->getSubVal(), FooVal);
               });
 }
 
+TEST_F(TransferTest, StaticIntSingleVarDecl) {
+  std::string Code = R"(
+    void target() {
+      static int Foo;
+      // [[p]]
+    }
+  )";
+  runDataflow(Code,
+              [](llvm::ArrayRef<
+                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+                     Results,
+                 ASTContext &ASTCtx) {
+                ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
+                const Environment &Env = Results[0].second.Env;
+
+                const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
+                ASSERT_THAT(FooDecl, NotNull());
+
+                const StorageLocation *FooLoc =
+                    Env.getStorageLocation(*FooDecl, SkipPast::None);
+                ASSERT_TRUE(isa_and_nonnull<ScalarStorageLocation>(FooLoc));
+
+                const Value *FooVal = Env.getValue(*FooLoc);
+                EXPECT_TRUE(isa_and_nonnull<IntegerValue>(FooVal));
+              });
+}
+
+TEST_F(TransferTest, StaticIntGroupVarDecl) {
+  std::string Code = R"(
+    void target() {
+      static int Foo, Bar;
+      (void)0;
+      // [[p]]
+    }
+  )";
+  runDataflow(Code,
+              [](llvm::ArrayRef<
+                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+                     Results,
+                 ASTContext &ASTCtx) {
+                ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
+                const Environment &Env = Results[0].second.Env;
+
+                const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
+                ASSERT_THAT(FooDecl, NotNull());
+
+                const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
+                ASSERT_THAT(BarDecl, NotNull());
+
+                const StorageLocation *FooLoc =
+                    Env.getStorageLocation(*FooDecl, SkipPast::None);
+                ASSERT_TRUE(isa_and_nonnull<ScalarStorageLocation>(FooLoc));
+
+                const StorageLocation *BarLoc =
+                    Env.getStorageLocation(*BarDecl, SkipPast::None);
+                ASSERT_TRUE(isa_and_nonnull<ScalarStorageLocation>(BarLoc));
+
+                const Value *FooVal = Env.getValue(*FooLoc);
+                EXPECT_TRUE(isa_and_nonnull<IntegerValue>(FooVal));
+
+                const Value *BarVal = Env.getValue(*BarLoc);
+                EXPECT_TRUE(isa_and_nonnull<IntegerValue>(BarVal));
+
+                EXPECT_NE(FooVal, BarVal);
+              });
+}
+
+TEST_F(TransferTest, GlobalIntVarDecl) {
+  std::string Code = R"(
+    static int Foo;
+
+    void target() {
+      int Bar = Foo;
+      int Baz = Foo;
+      // [[p]]
+    }
+  )";
+  runDataflow(Code,
+              [](llvm::ArrayRef<
+                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+                     Results,
+                 ASTContext &ASTCtx) {
+                ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
+                const Environment &Env = Results[0].second.Env;
+
+                const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
+                ASSERT_THAT(BarDecl, NotNull());
+
+                const ValueDecl *BazDecl = findValueDecl(ASTCtx, "Baz");
+                ASSERT_THAT(BazDecl, NotNull());
+
+                const Value *BarVal =
+                    cast<IntegerValue>(Env.getValue(*BarDecl, SkipPast::None));
+                const Value *BazVal =
+                    cast<IntegerValue>(Env.getValue(*BazDecl, SkipPast::None));
+                EXPECT_EQ(BarVal, BazVal);
+              });
+}
+
+TEST_F(TransferTest, StaticMemberIntVarDecl) {
+  std::string Code = R"(
+    struct A {
+      static int Foo;
+    };
+
+    void target(A a) {
+      int Bar = a.Foo;
+      int Baz = a.Foo;
+      // [[p]]
+    }
+  )";
+  runDataflow(Code,
+              [](llvm::ArrayRef<
+                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+                     Results,
+                 ASTContext &ASTCtx) {
+                ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
+                const Environment &Env = Results[0].second.Env;
+
+                const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
+                ASSERT_THAT(BarDecl, NotNull());
+
+                const ValueDecl *BazDecl = findValueDecl(ASTCtx, "Baz");
+                ASSERT_THAT(BazDecl, NotNull());
+
+                const Value *BarVal =
+                    cast<IntegerValue>(Env.getValue(*BarDecl, SkipPast::None));
+                const Value *BazVal =
+                    cast<IntegerValue>(Env.getValue(*BazDecl, SkipPast::None));
+                EXPECT_EQ(BarVal, BazVal);
+              });
+}
+
+TEST_F(TransferTest, StaticMemberRefVarDecl) {
+  std::string Code = R"(
+    struct A {
+      static int &Foo;
+    };
+
+    void target(A a) {
+      int Bar = a.Foo;
+      int Baz = a.Foo;
+      // [[p]]
+    }
+  )";
+  runDataflow(Code,
+              [](llvm::ArrayRef<
+                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+                     Results,
+                 ASTContext &ASTCtx) {
+                ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
+                const Environment &Env = Results[0].second.Env;
+
+                const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
+                ASSERT_THAT(BarDecl, NotNull());
+
+                const ValueDecl *BazDecl = findValueDecl(ASTCtx, "Baz");
+                ASSERT_THAT(BazDecl, NotNull());
+
+                const Value *BarVal =
+                    cast<IntegerValue>(Env.getValue(*BarDecl, SkipPast::None));
+                const Value *BazVal =
+                    cast<IntegerValue>(Env.getValue(*BazDecl, SkipPast::None));
+                EXPECT_EQ(BarVal, BazVal);
+              });
+}
+
 } // namespace