[clang][dataflow] Analyze constructor bodies

[samestep]

Summary

This patch adds the ability to context-sensitively analyze constructor bodies, by changing pushCall to allow both CallExpr and CXXConstructExpr, and extracting the main context-sensitive logic out of VisitCallExpr into a new transferInlineCall method which is now also called at the end of VisitCXXConstructExpr.

[samestep]

Tweaks

[samestep]

Fix bug

[ymandel]

Looks good overall. I want to think a bit more about potential additional tests...

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

232

i think that llvm_unreachable is preferable for this purpose.

260

same.

clang/lib/Analysis/FlowSensitive/Transfer.cpp

678–684

Why can't this stay in VisitCallExpr?

[sgatev]

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

138

How about we define overloads that take these types instead of taking an Expr here? This should remove the need for type-checking and guarding against bad input in the implementation. transferInlineCall can be a template if necessary.

[ymandel]

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

4371

What about a default constructor, including when there are field initializers like:

class MyClass {
   public:
     MyClass() = default;

     bool MyField = true;
   };

Should we expect to handle that correctly? If so, can you add some tests?

[samestep]

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

138

Hmm I guess we could; is there much of a benefit to doing this templated?

clang/lib/Analysis/FlowSensitive/Transfer.cpp

678–684

I had it there in an earlier version of this patch; it was causing tests to fail (the SelfReferential* ones, if I remember correctly).

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

4371

Good idea! I'll add a test for this.

[samestep]

Address Yitzie's comments

[samestep]

Narrow public signature of pushCall

[xazax.hun]

I feel like this is a repeated pattern. The CSA solved a very similar issue by introducing the CallEvent class hierarchy. I also remember seeing many disparate code snippets littered throughout the clang codebase that tries to deal with the problem of not having facilities to treat call-like nodes uniformly. At some point, I believe there were even some AST changes or supporting structures proposed to ameliorate this problem, but I can't find those at the moment. While I think it might be OK to introduce yet another workaround here, this is a cleanup that is long overdue, and I hope someone will have the time to actually improve the situation. Sorry for the rant, I will actually look at the code but had to vent this.

[xazax.hun]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

251–256

I think the more idiomatic solution in Clang is to create an ArrayRef for the arguments from the ConstructExpr and the CallExpr. The args should be stored in a continuous memory area in both cases so you should be able to create the ArrayRef in constant time and you would no longer need to have these pesky if statements in your loop.

[samestep]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

251–256

Ah OK, thanks! How should I do that? I was previously using iterators but it looked like the types were different between CallExpr and CXXConstructExpr, so I switched away from iterators in this patch; is there an easy way to make the ArrayRef?

[xazax.hun]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

251–256

Here is an example: https://github.com/llvm/llvm-project/blob/main/clang/lib/Sema/SemaInit.cpp#L7086

[samestep]

In D131438#3710697, @xazax.hun wrote:

I feel like this is a repeated pattern. The CSA solved a very similar issue by introducing the CallEvent class hierarchy. I also remember seeing many disparate code snippets littered throughout the clang codebase that tries to deal with the problem of not having facilities to treat call-like nodes uniformly. At some point, I believe there were even some AST changes or supporting structures proposed to ameliorate this problem, but I can't find those at the moment. While I think it might be OK to introduce yet another workaround here, this is a cleanup that is long overdue, and I hope someone will have the time to actually improve the situation. Sorry for the rant, I will actually look at the code but had to vent this.

No worries at all for the rant, I appreciate the broader context. I was definitely surprised to learn that the two types don't share a common ancestor.

[samestep]

Use ArrayRef

[ymandel]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

209–247

I think you can push all of this logic to the type-specialized pushCalls now and just have pushCallInternal take the FunctionDecl, ArrayRef, etc.. WDYT?

[xazax.hun]

Thanks!

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

209–247

+1, I like that.

[samestep]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

209–247

Great idea, thanks! Doing that now.

[samestep]

Pull type-specific logic into overloads

[xazax.hun]

Nice! We went from branches in the loop to branches before the loop first. And now the branches are at compile time during overload resolution. I love it.

[ymandel]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

209–210

I'd go farther: just duplicate this line in both pushCalls and then the two if that follow can be moved out as well. at that point, I think Call is no longer needed.

[samestep]

Remove Call parameter from pushCallInternal method

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

209–210

Smart! Done.

[sgatev]

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

386

Let's add a note that unlike pushCall, this member is invoked on the environment of the callee.

387

#include "llvm/ADT/ArrayRef.h"

clang/lib/Analysis/FlowSensitive/Transfer.cpp

667–670

[samestep]

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

386

Will do, thanks!

387

When I add this, I get a warning: "Included header ArrayRef.h is not used directly"

clang/lib/Analysis/FlowSensitive/Transfer.cpp

667–670

👍

[samestep]

Address Stanislav's comments

[eugenis]

Sorry but I had to revert this because of the conflicts with another revert: https://reviews.llvm.org/D131065

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

public:
   Environment(DataflowAnalysisContext &DACtx, const DeclContext &DeclCtx);
 
   /// Creates and returns an environment to use for an inline analysis  of the
   /// callee. Uses the storage location from each argument in the `Call` as the
   /// storage location for the corresponding parameter in the callee.
   ///
   /// Requirements:
   ///
-  ///  The callee of `Call` must be a `FunctionDecl` with a body.
+  ///  The callee of `Call` must be a `FunctionDecl`.
   ///
   ///  The body of the callee must not reference globals.
   ///
   ///  The arguments of `Call` must map 1:1 to the callee's parameters.
   ///
   ///  Each argument of `Call` must already have a `StorageLocation`.
   Environment pushCall(const CallExpr *Call) const;
+  Environment pushCall(const CXXConstructExpr *Call) const;
 
   /// Moves gathered information back into `this` from a `CalleeEnv` created via
   /// `pushCall`.
   void popCall(const Environment &CalleeEnv);
 
   /// Returns true if and only if the environment is equivalent to `Other`, i.e
   /// the two environments:
   ///  - have the same mappings from declarations to storage locations,
private:
   ///  `Type` must not be null.
   Value *createValueUnlessSelfReferential(QualType Type,
                                           llvm::DenseSet<QualType> &Visited,
                                           int Depth, int &CreatedValuesCount);
 
   StorageLocation &skip(StorageLocation &Loc, SkipPast SP) const;
   const StorageLocation &skip(const StorageLocation &Loc, SkipPast SP) const;
 
+  /// Shared implementation of `pushCall` overloads. Note that unlike
+  /// `pushCall`, this member is invoked on the environment of the callee, not
+  /// of the caller.
+  void pushCallInternal(const FunctionDecl *FuncDecl,
+                        ArrayRef<const Expr *> Args);
+
   // `DACtx` is not null and not owned by this object.
   DataflowAnalysisContext *DACtx;
 
   // `DeclContext` of the block being analysed if provided.
   const DeclContext *DeclCtx;
 
   // In a properly initialized `Environment`, `ReturnLoc` should only be null if
   // its `DeclContext` could not be cast to a `FunctionDecl`.

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

if (MethodDecl && !MethodDecl->isStatic()) {
         if (Value *ThisPointeeVal = createValue(ThisPointeeType))
           setValue(*ThisPointeeLoc, *ThisPointeeVal);
       }
     }
   }
 }
 
 Environment Environment::pushCall(const CallExpr *Call) const {
   Environment Env(*this);
-  // FIXME: Support references here.
-  Env.ReturnLoc = Env.getStorageLocation(*Call, SkipPast::Reference);
-
-  const auto *FuncDecl = Call->getDirectCallee();
-  assert(FuncDecl != nullptr);
 
-  Env.setDeclCtx(FuncDecl);
-
-  // FIXME: In order to allow the callee to reference globals, we probably need
-  // to call `initGlobalVars` here in some way.
+  // FIXME: Support references here.
+  Env.ReturnLoc = getStorageLocation(*Call, SkipPast::Reference);
 
   if (const auto *MethodCall = dyn_cast<CXXMemberCallExpr>(Call)) {
     if (const Expr *Arg = MethodCall->getImplicitObjectArgument()) {
-      Env.ThisPointeeLoc = Env.getStorageLocation(*Arg, SkipPast::Reference);
-    }
-  }
+      Env.ThisPointeeLoc = getStorageLocation(*Arg, SkipPast::Reference);
+    }
+
+  Env.pushCallInternal(Call->getDirectCallee(),
+                       llvm::makeArrayRef(Call->getArgs(), Call->getNumArgs()));
+
+  return Env;
+}
+
+Environment Environment::pushCall(const CXXConstructExpr *Call) const {
+  Environment Env(*this);
+
+  // FIXME: Support references here.
+  Env.ReturnLoc = getStorageLocation(*Call, SkipPast::Reference);
+
+  Env.ThisPointeeLoc = Env.ReturnLoc;
+
+  Env.pushCallInternal(Call->getConstructor(),
+                       llvm::makeArrayRef(Call->getArgs(), Call->getNumArgs()));
+
+  return Env;
 
+void Environment::pushCallInternal(const FunctionDecl *FuncDecl,
+                                   ArrayRef<const Expr *> Args) {
+  setDeclCtx(FuncDecl);
+
+  // FIXME: In order to allow the callee to reference globals, we probably need
+  // to call `initGlobalVars` here in some way.
+
   auto ParamIt = FuncDecl->param_begin();
-  auto ArgIt = Call->arg_begin();
-  auto ArgEnd = Call->arg_end();
 
   // FIXME: Parameters don't always map to arguments 1:1; examples include
   // overloaded operators implemented as member functions, and parameter packs.
-  for (; ArgIt != ArgEnd; ++ParamIt, ++ArgIt) {
+  for (unsigned ArgIndex = 0; ArgIndex < Args.size(); ++ParamIt, ++ArgIndex) {
     assert(ParamIt != FuncDecl->param_end());
 
-    const Expr *Arg = *ArgIt;
-    auto *ArgLoc = Env.getStorageLocation(*Arg, SkipPast::Reference);
+    const Expr *Arg = Args[ArgIndex];
+    auto *ArgLoc = getStorageLocation(*Arg, SkipPast::Reference);
     assert(ArgLoc != nullptr);
 
     const VarDecl *Param = *ParamIt;
-    auto &Loc = Env.createStorageLocation(*Param);
-    Env.setStorageLocation(*Param, Loc);
+    auto &Loc = createStorageLocation(*Param);
+    setStorageLocation(*Param, Loc);
 
     QualType ParamType = Param->getType();
     if (ParamType->isReferenceType()) {
-      auto &Val = Env.takeOwnership(std::make_unique<ReferenceValue>(*ArgLoc));
-      Env.setValue(Loc, Val);
-    } else if (auto *ArgVal = Env.getValue(*ArgLoc)) {
-      Env.setValue(Loc, *ArgVal);
-    } else if (Value *Val = Env.createValue(ParamType)) {
-      Env.setValue(Loc, *Val);
+      auto &Val = takeOwnership(std::make_unique<ReferenceValue>(*ArgLoc));
+      setValue(Loc, Val);
+    } else if (auto *ArgVal = getValue(*ArgLoc)) {
+      setValue(Loc, *ArgVal);
+    } else if (Value *Val = createValue(ParamType)) {
+      setValue(Loc, *Val);
     }
   }
-
-  return Env;
 }
 
 void Environment::popCall(const Environment &CalleeEnv) {
   // We ignore `DACtx` because it's already the same in both. We don't want the
   // callee's `DeclCtx`, `ReturnLoc` or `ThisPointeeLoc`. We don't bring back
   // `DeclToLoc` and `ExprToLoc` because we want to be able to later analyze the
   // same callee in a different context, and `setStorageLocation` requires there
   // to not already be a storage location assigned. Conceptually, these maps

clang/lib/Analysis/FlowSensitive/Transfer.cpp

if (ConstructorDecl->isCopyOrMoveConstructor()) {
       }
       return;
     }
 
     auto &Loc = Env.createStorageLocation(*S);
     Env.setStorageLocation(*S, Loc);
     if (Value *Val = Env.createValue(S->getType()))
       Env.setValue(Loc, *Val);
+
+    transferInlineCall(S, ConstructorDecl);
   }
 
   void VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *S) {
     if (S->getOperator() == OO_Equal) {
       assert(S->getNumArgs() == 2);
 
       const Expr *Arg0 = S->getArg(0);
       assert(Arg0 != nullptr);
if (S->isCallToStdMove()) {
       assert(S->getArg(0) != nullptr);
       // `__builtin_expect` returns by-value, so strip away any potential
       // references in the argument.
       auto *ArgLoc = Env.getStorageLocation(*S->getArg(0), SkipPast::Reference);
       if (ArgLoc == nullptr)
         return;
       Env.setStorageLocation(*S, *ArgLoc);
     } else if (const FunctionDecl *F = S->getDirectCallee()) {
-      // This case is for context-sensitive analysis.
-      if (!Options.ContextSensitive)
-        return;
-
-      const ControlFlowContext *CFCtx = Env.getControlFlowContext(F);
-      if (!CFCtx)
-        return;
-
-      // FIXME: We don't support context-sensitive analysis of recursion, so
-      // we should return early here if `F` is the same as the `FunctionDecl`
-      // holding `S` itself.
-
-      auto ExitBlock = CFCtx->getCFG().getExit().getBlockID();
-
-      // Note that it is important for the storage location of `S` to be set
-      // before `pushCall`, because the latter uses it to set the storage
-      // location for `return`.
-      auto &ReturnLoc = Env.createStorageLocation(*S);
-      Env.setStorageLocation(*S, ReturnLoc);
-      auto CalleeEnv = Env.pushCall(S);
-
-      // FIXME: Use the same analysis as the caller for the callee. Note,
-      // though, that doing so would require support for changing the analysis's
-      // ASTContext.
-      assert(
-          CFCtx->getDecl() != nullptr &&
-          "ControlFlowContexts in the environment should always carry a decl");
-      auto Analysis = NoopAnalysis(CFCtx->getDecl()->getASTContext(),
-                                   DataflowAnalysisOptions());
-
-      auto BlockToOutputState =
-          dataflow::runDataflowAnalysis(*CFCtx, Analysis, CalleeEnv);
-      assert(BlockToOutputState);
-      assert(ExitBlock < BlockToOutputState->size());
-
-      auto ExitState = (*BlockToOutputState)[ExitBlock];
-      assert(ExitState);
-
-      Env.popCall(ExitState->Env);
+      transferInlineCall(S, F);
     }
   }
 
   void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *S) {
     const Expr *SubExpr = S->getSubExpr();
     assert(SubExpr != nullptr);
 
     auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
if (auto *Val = dyn_cast_or_null<BoolValue>(
             Env.getValue(SubExpr, SkipPast::Reference)))
       return *Val;
 
     // If the value of `SubExpr` is still unknown, we create a fresh symbolic
     // boolean value for it.
     return Env.makeAtomicBoolValue();
   }
 
+  // If context sensitivity is enabled, try to analyze the body of the callee
+  // `F` of `S`. The type `E` must be either `CallExpr` or `CXXConstructExpr`.
+  template <typename E>
+  void transferInlineCall(const E *S, const FunctionDecl *F) {
+    if (!Options.ContextSensitive)
+      return;
+
+    const ControlFlowContext *CFCtx = Env.getControlFlowContext(F);
+    if (!CFCtx)
+      return;
+
+    // FIXME: We don't support context-sensitive analysis of recursion, so
+    // we should return early here if `F` is the same as the `FunctionDecl`
+    // holding `S` itself.
+
+    auto ExitBlock = CFCtx->getCFG().getExit().getBlockID();
+
+    if (const auto *NonConstructExpr = dyn_cast<CallExpr>(S)) {
+      // Note that it is important for the storage location of `S` to be set
+      // before `pushCall`, because the latter uses it to set the storage
+      // location for `return`.
+      auto &ReturnLoc = Env.createStorageLocation(*S);
+      Env.setStorageLocation(*S, ReturnLoc);
+    }
+    auto CalleeEnv = Env.pushCall(S);
+
+    // FIXME: Use the same analysis as the caller for the callee. Note,
+    // though, that doing so would require support for changing the analysis's
+    // ASTContext.
+    assert(CFCtx->getDecl() != nullptr &&
+           "ControlFlowContexts in the environment should always carry a decl");
+    auto Analysis = NoopAnalysis(CFCtx->getDecl()->getASTContext(),
+                                 DataflowAnalysisOptions());
+
+    auto BlockToOutputState =
+        dataflow::runDataflowAnalysis(*CFCtx, Analysis, CalleeEnv);
+    assert(BlockToOutputState);
+    assert(ExitBlock < BlockToOutputState->size());
+
+    auto ExitState = (*BlockToOutputState)[ExitBlock];
+    assert(ExitState);
+
+    Env.popCall(ExitState->Env);
+  }
+
   const StmtToEnvMap &StmtToEnv;
   Environment &Env;
   TransferOptions Options;
 };
 
 void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env,
               TransferOptions Options) {
   TransferVisitor(StmtToEnv, Env, Options).Visit(&S);
 }
 
 } // namespace dataflow
 } // namespace clang

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

runDataflow(Code,
                 auto &FooVal =
                     *cast<BoolValue>(Env.getValue(*FooDecl, SkipPast::None));
                 EXPECT_TRUE(Env.flowConditionImplies(FooVal));
               },
               {/*.ApplyBuiltinTransfer=*/true,
                /*.BuiltinTransferOptions=*/{/*.ContextSensitive=*/true}});
 }
 
+TEST(TransferTest, ContextSensitiveConstructorBody) {
+  std::string Code = R"(
+    class MyClass {
+    public:
+      MyClass() { MyField = true; }
+
+      bool MyField;
+    };
+
+    void target() {
+      MyClass MyObj;
+      bool Foo = MyObj.MyField;
+      // [[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());
+
+                auto &FooVal =
+                    *cast<BoolValue>(Env.getValue(*FooDecl, SkipPast::None));
+                EXPECT_TRUE(Env.flowConditionImplies(FooVal));
+              },
+              {/*.ApplyBuiltinTransfer=*/true,
+               /*.BuiltinTransferOptions=*/{/*.ContextSensitive=*/true}});
+}
+
+TEST(TransferTest, ContextSensitiveConstructorInitializer) {
+  std::string Code = R"(
+    class MyClass {
+    public:
+      MyClass() : MyField(true) {}
+
+      bool MyField;
+    };
+
+    void target() {
+      MyClass MyObj;
+      bool Foo = MyObj.MyField;
+      // [[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());
+
+                auto &FooVal =
+                    *cast<BoolValue>(Env.getValue(*FooDecl, SkipPast::None));
+                EXPECT_TRUE(Env.flowConditionImplies(FooVal));
+              },
+              {/*.ApplyBuiltinTransfer=*/true,
+               /*.BuiltinTransferOptions=*/{/*.ContextSensitive=*/true}});
+}
+
+TEST(TransferTest, ContextSensitiveConstructorDefault) {
+  std::string Code = R"(
+    class MyClass {
+    public:
+      MyClass() = default;
+
+      bool MyField = true;
+    };
+
+    void target() {
+      MyClass MyObj;
+      bool Foo = MyObj.MyField;
+      // [[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());
+
+                auto &FooVal =
+                    *cast<BoolValue>(Env.getValue(*FooDecl, SkipPast::None));
+                EXPECT_TRUE(Env.flowConditionImplies(FooVal));
+              },
+              {/*.ApplyBuiltinTransfer=*/true,
+               /*.BuiltinTransferOptions=*/{/*.ContextSensitive=*/true}});
+}
+
 } // namespace