[clang][dataflow] Analyze calls to in-TU functions

[samestep]

Summary

This patch adds initial support for context-sensitive analysis of simple functions whose definition is available in the translation unit, guarded by the ContextSensitive flag in the new TransferOptions struct. When this option is true, the VisitCallExpr case in the builtin transfer function has a fallthrough case which checks for a direct callee with a body. In that case, it constructs a CFG from that callee body, uses the new pushCall method on the Environment to make an environment to analyze the callee, and then calls runDataflowAnalysis with a NoopAnalysis (disabling context-sensitive analysis on that sub-analysis, to avoid problems with recursion). After the sub-analysis completes, the Environment from its exit block is simply assigned back to the environment at the callsite.

The pushCall method (which currently only supports non-method functions with some restrictions) maps the SourceLocations for all the parameters to the existing source locations for the corresponding arguments from the callsite.

This patch adds a few tests to check that this context-sensitive analysis works on simple functions. More sophisticated functionality will be added later; the most important next step is to explicitly model context in some fields of the DataflowAnalysisContext class, as mentioned in a FIXME comment in the pushCall implementation.

[xazax.hun]

There are many ways to introduce context sensitivity into the framework, this patch seems to take the "inline substitution" approach, the same approach the Clang Static Analyzer is taking. While this approach is relatively easy to implement and has great precision, it also has some scalability problems. Did you also consider a summary-based approach? In general, I believe the inline substitution approach results in an easier to use interface for the users of the framework, but I am a bit concerned about the scalability problems.

Some other related questions:

• Why call noop analysis? As far as I understand, this would only update the environment but not the lattice of the current analysis, i.e., if the analysis is computing some information like liveness, that information would not be context sensitive. Do I miss something?
• Why limit the call depth to 1? The patch mentions recursive functions. In case of the Clang Static Analyzer, the call depth is 4. I think if we go with the inline substitution approach, we want this parameter to be tunable, because different analyses might have different sweet spots for the call stack depth.
• The CSA also has other tunables, e.g., small functions are always inlined and large functions are never inlined.
• Currently, it looks like the framework assumes functions that cannot be inlined are not doing anything. This is an unsound assumption, and I wonder if we should change that before we try to settle on the best values for the tunable parameters.
• The current code might do a bit too much work. E.g. consider:

while (...) {
  inlinableCall();
}

As far as I understand, the current approach would start the analysis of inlinableCall from scratch in each iteration. I wonder if we actually want to preserve the state between the iterations, so we do not always reevaluate the call from scratch. Currently, it might not be a big deal as the fixed-point iteration part is disabled. But this could be a perf problem in the future, unless I miss something.

• I think the environment currently is not really up to context-sensitive evaluation. Consider a recursive function:

void f(int a) {
  ++a;
  if (a < 10)
      f(a);
}

Here, when the recursive call is evaluated, it is ambiguous what a refers to. Is it the argument of the caller or the callee? To solve this ambiguity, the calling context needs to be the part of the keys in the environment.

[ymandel]

Sam, this is a great start! I'm really excited to see that you have a core working so quickly.

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

208

220

I wonder how this will work between caller and callee. Do we need separate global var state in the frame? If so, maybe mention that as well in the FIXME above.

237

I'm pretty sure we want SkipPast::Reference. That will ensure that the parameter and argument share the same underlying location. Otherwise, in the case of references, the parameter will point to the reference location object rather than just directly to the location.

clang/lib/Analysis/FlowSensitive/Transfer.cpp

517

here and below: s/TODO/FIXME.

524

This seems worth a FIXME or, at least, an explanation. It implies that with the current design, we can't support general-purpose analyses, which we should probably fix. Given our goal of supporting models that don't involve specialized lattices, I think this is a good compromise for the short term, but not a stable solution for the framework (hence FIXME sounds right).

[samestep]

Update parent patch

[samestep]

In D130306#3670259, @xazax.hun wrote:

There are many ways to introduce context sensitivity into the framework, this patch seems to take the "inline substitution" approach, the same approach the Clang Static Analyzer is taking. While this approach is relatively easy to implement and has great precision, it also has some scalability problems. Did you also consider a summary-based approach? In general, I believe the inline substitution approach results in an easier to use interface for the users of the framework, but I am a bit concerned about the scalability problems.

Good point, thanks! Yes, we considered a summary-based approach, but we decided not to use it because (as you mentioned) it would be much more difficult to implement, especially for callees with nontrivial CFGs, which would result in a nontrivial flow condition instead of just Values in the Environment.

Could you elaborate on what specific scalability problems you are concerned about? The main one that comes to mind for me is unpredictable cost due to the potential for arbitrary callee bodies to be present in the translation unit. While this particular patch doesn't address that concern, we definitely have plans to do so: I'm guessing that will take the form of providing the analysis an allowlist of symbols of which it is allowed to analyze the bodies, so it would treat any symbols not in that list as if their bodies are not available in the TU regardless.

To clarify, the main reason we want context-sensitive analysis is to allow us to simplify our definitions of some models, such as the optional checker model. The goal is to provide the analysis a mock implementation of an optional type, and then use context-sensitive analysis (probably just one or two layers deep) to model the constructors and methods.

Some other related questions:

• Why call noop analysis? As far as I understand, this would only update the environment but not the lattice of the current analysis, i.e., if the analysis is computing some information like liveness, that information would not be context sensitive. Do I miss something?

The alternative in this case would be to use the same analysis for the callee that is already being used for the caller? I agree that would be nicer to serve a broader category of use cases. I didn't do that in this patch for a couple reasons:

1. In the short term, that would require threading more information through to the builtin transfer function, while this patch was meant to just be a minimum viable product.
2. In the longer term, we probably don't need that for our specific goals (just modeling simple fields of mock classes) mentioned above.

However, if you have a suggestion for a way to construct an instance of the outer analysis here, that would definitely be useful.

• Why limit the call depth to 1? The patch mentions recursive functions. In case of the Clang Static Analyzer, the call depth is 4. I think if we go with the inline substitution approach, we want this parameter to be tunable, because different analyses might have different sweet spots for the call stack depth.

There's no particular reason for this. We plan to support more call stack depth soon. This would probably make sense as a field in the TransferOptions struct.

• The CSA also has other tunables, e.g., small functions are always inlined and large functions are never inlined.

See my response earlier about an allowlist for symbols to inline.

• Currently, it looks like the framework assumes functions that cannot be inlined are not doing anything. This is an unsound assumption, and I wonder if we should change that before we try to settle on the best values for the tunable parameters.

Agreed, this assumption is unsound. However, the framework already makes many other unsound assumptions in a similar spirit, so this one doesn't immediately strike me as one that needs to change. I'll defer to people with more context.

• The current code might do a bit too much work. E.g. consider:

while (...) {
  inlinableCall();
}

As far as I understand, the current approach would start the analysis of inlinableCall from scratch in each iteration. I wonder if we actually want to preserve the state between the iterations, so we do not always reevaluate the call from scratch. Currently, it might not be a big deal as the fixed-point iteration part is disabled. But this could be a perf problem in the future, unless I miss something.

Agreed, this is somewhat wasteful. Note that not everything is thrown away, because the same DataflowAnalysisContext is reused when analyzing the callee. Still, we would like to handle this in a smarter way in the future, as you mention. For now, though, while just building up functionality behind a feature flag, we don't plan to worry as much about this particular performance concern.

• I think the environment currently is not really up to context-sensitive evaluation. Consider a recursive function:

void f(int a) {
  ++a;
  if (a < 10)
      f(a);
}

Here, when the recursive call is evaluated, it is ambiguous what a refers to. Is it the argument of the caller or the callee? To solve this ambiguity, the calling context needs to be the part of the keys in the environment.

Yes, I mentioned this in the patch description and in a comment in the pushCall implementation: we plan to do this by modifying the set of fields in the DataflowAnalysisContext class. I plan to do this in my next patch, once this one is landed.

[samestep]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

208

OK, I'll change this; would you like for me to replace all the other TODOs with FIXMEs, as well?

220

Could you clarify what you mean? Perhaps I just don't understand exactly what is meant by "global vars" here.

237

OK, thank you! I'll make that change.

clang/lib/Analysis/FlowSensitive/Transfer.cpp

517

Will do.

524

Good point, and @xazax.hun pointed this out as well. I'll add a FIXME here, at least.

[ymandel]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

208

Just those in this patch.

220

https://github.com/llvm/llvm-project/blob/main/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp#L131-L135

/// 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.

Since this already mentions a need to reset after function calls, seemed relevant here.

[samestep]

Address Yitzie's comments

[samestep]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

220

Hmm, OK. I pretty much just pattern-matched from the Environment constructor right above this method implementation. Would it be better for me to instead just remove this initGlobalVars call for now and replace it with a FIXME saying that we'll probably need to call this but it's unclear how exactly to do so?

[samestep]

Fix typo in comment

[ymandel]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

220

SGTM. We can note this constraint on models' reference implementations. Specifically, that they cannot reference globals.

[gribozavr2]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

231

The Clang AST includes argument expressions for defaulted arguments, so I believe there shouldn't be anything left to do here, it should just work.

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

3896

[samestep]

Don't allow globals

[samestep]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

220

Done.

231

Oh nice! I'm updating this comment, thanks.

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

3896

Good idea, done.

[samestep]

Update comment about default parameters

[li.zhe.hua]

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

64

Nit: -Wmissing-field-initializers is apparently enabled, and starts warning on this.

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

42–44

For the purposes of the test, there's really only 3 states:

1. No built-in transfer
2. Built-in transfer, no context-sensitive
3. Built-in transfer, with context-sensitive

It may be more readable for tests to have a 3-state enum, that runDataFlow will then use to produce the corresponding DataflowAnalysisOptions. As is, a snippet like

{/*.ApplyBuiltinTransfer=*/true,
 /*.BuiltinTransferOptions=*/{/*.ContextSensitive=*/false}});

is rough to read. Good enum names with good comments would probably make this much better. WDYT?

67

Nit: -Wmissing-field-initializers is apparently enabled, and starts warning on this.

[samestep]

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

64

Ah thanks, will fix.

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

42–44

I agree that there are only 3 states, but I also think that conceptually this really is a multi-layered thing; either we apply the built-in transfer or not, and then if we do apply the builtin transfer, there's some set of options we pass to it. Thus, it doesn't seem right to just collapse it into a flat enum; I'm not sure though.

67

Same here; thanks!

[samestep]

Appease -Wmissing-field-initializers

[xazax.hun]

In D130306#3671852, @samestep wrote:

In D130306#3670259, @xazax.hun wrote:

Yes, we considered a summary-based approach, but we decided not to use it because (as you mentioned) it would be much more difficult to implement, especially for callees with nontrivial CFGs, which would result in a nontrivial flow condition instead of just Values in the Environment.

Thanks! I think this is a major design decision, and I'd love to see a discussion about the alternatives considered before jumping to an implementation. Specifically, I'd like to know if summaries are out of scope or something you would consider in the future. Knowing this is useful because this can influence how the code should be reviewed. E.g., if you plan to have multiple ways to do context sensitive analysis in the future, we should make sure that the current code will not lock us in in the inline substitution approach. If summaries are not planned at all, this is not a concern.

Could you elaborate on what specific scalability problems you are concerned about?

The Clang Static Analyzer is using this approach and it was a long way to iron out all the corner cases where the performance was bad. It has many cuts including maximum number of visits for a basic block, maximum call stack depth, not inlining functions after a certain size threshold and so on. Basically, it took some time to get the right performance and precision. But overall, the inline substitution approach will never scale to large call stacks/long calling contexts. On the other hand, a summary-based approach can potentially find bugs across a really large number of function calls with reasonable costs. Mainly because the same function is not reanalyzed for every context.

To clarify, the main reason we want context-sensitive analysis is to allow us to simplify our definitions of some models, such as the optional checker model. The goal is to provide the analysis a mock implementation of an optional type, and then use context-sensitive analysis (probably just one or two layers deep) to model the constructors and methods.

Thanks, this is also useful context!

Some other related questions:

• Why call noop analysis?

The alternative in this case would be to use the same analysis for the callee that is already being used for the caller? I agree that would be nicer to serve a broader category of use cases. I didn't do that in this patch for a couple reasons:

1. In the short term, that would require threading more information through to the builtin transfer function, while this patch was meant to just be a minimum viable product.
2. In the longer term, we probably don't need that for our specific goals (just modeling simple fields of mock classes) mentioned above.

I see. This was not clear to me from the description of the patch notes. It seems to me that the goal here is to simplify the modeling of certain types, not general context-sensitive analysis. I reviewed this patch with the wrong idea in mind. If that is the goal, the current approach makes sense. But I think the comments should make clear what the intended use case and the limitations of the current approach is.

• Currently, it looks like the framework assumes functions that cannot be inlined are not doing anything. This is an unsound assumption, and I wonder if we should change that before we try to settle on the best values for the tunable parameters.

Agreed, this assumption is unsound. However, the framework already makes many other unsound assumptions in a similar spirit, so this one doesn't immediately strike me as one that needs to change. I'll defer to people with more context.

The main reason I wanted to call this out because it increasingly seems to be whenever a decision needs to be made, the framework is getting less and less sound. Basically, many design decisions here are very similar to what the Clang Static Analyzer is doing. Since Clang already has an analysis framework for unsound analysis, I wanted to avoid you reinventing the wheel and doing something similar to CSA instead of providing something new for the use cases that cannot be covered by the CSA.

• I think the environment currently is not really up to context-sensitive evaluation. Consider a recursive function:

Yes, I mentioned this in the patch description and in a comment in the pushCall implementation: we plan to do this by modifying the set of fields in the DataflowAnalysisContext class. I plan to do this in my next patch, once this one is landed.

Oh, my bad! I somehow blinked and totally skipped that comment.

[samestep]

In D130306#3673120, @xazax.hun wrote:

Thanks! I think this is a major design decision, and I'd love to see a discussion about the alternatives considered before jumping to an implementation. Specifically, I'd like to know if summaries are out of scope or something you would consider in the future. Knowing this is useful because this can influence how the code should be reviewed. E.g., if you plan to have multiple ways to do context sensitive analysis in the future, we should make sure that the current code will not lock us in in the inline substitution approach. If summaries are not planned at all, this is not a concern.

This is a good question. I shared with you our design doc, which may help clarify somewhat; please let me know if you have further concerns.

The Clang Static Analyzer is using this approach and it was a long way to iron out all the corner cases where the performance was bad. It has many cuts including maximum number of visits for a basic block, maximum call stack depth, not inlining functions after a certain size threshold and so on. Basically, it took some time to get the right performance and precision. But overall, the inline substitution approach will never scale to large call stacks/long calling contexts. On the other hand, a summary-based approach can potentially find bugs across a really large number of function calls with reasonable costs. Mainly because the same function is not reanalyzed for every context.

That makes a lot of sense. From what you're saying, it sounds like we'll avoid that in our plan by keeping contexts small due to only context-sensitively analyzing simple models that we write ourselves.

I see. This was not clear to me from the description of the patch notes. It seems to me that the goal here is to simplify the modeling of certain types, not general context-sensitive analysis. I reviewed this patch with the wrong idea in mind. If that is the goal, the current approach makes sense. But I think the comments should make clear what the intended use case and the limitations of the current approach is.

Fair point. Hopefully the intended use case will become more clear in the code itself as I follow up with further patches; if not then I can modify the comments to clarify that. Are there any specific things you'd like to see written comments in this patch itself before landing?

The main reason I wanted to call this out because it increasingly seems to be whenever a decision needs to be made, the framework is getting less and less sound. Basically, many design decisions here are very similar to what the Clang Static Analyzer is doing. Since Clang already has an analysis framework for unsound analysis, I wanted to avoid you reinventing the wheel and doing something similar to CSA instead of providing something new for the use cases that cannot be covered by the CSA.

This makes sense; in this case, though, the unsoundness is already present (this patch does nothing to change the way we analyze calls to functions for which we can't see the body), so if anything, unsoundness is reduced here. I'll let @ymandel respond to this in more detail, though.

Oh, my bad! I somehow blinked and totally skipped that comment.

No worries! This patch is a bit large so it's easy to miss. Thanks for taking the time to review in such detail!

[ymandel]

In D130306#3676325, @samestep wrote:

The main reason I wanted to call this out because it increasingly seems to be whenever a decision needs to be made, the framework is getting less and less sound. Basically, many design decisions here are very similar to what the Clang Static Analyzer is doing. Since Clang already has an analysis framework for unsound analysis, I wanted to avoid you reinventing the wheel and doing something similar to CSA instead of providing something new for the use cases that cannot be covered by the CSA.

This makes sense; in this case, though, the unsoundness is already present (this patch does nothing to change the way we analyze calls to functions for which we can't see the body), so if anything, unsoundness is reduced here. I'll let @ymandel respond to this in more detail, though.

Gabor, I fully agree. We need to start paying down the debt on the unsoundness, reducing it where possible and otherwise giving users control over whether to incur it. However, as Sam wrote, we did not expect to be incurring any new unsoundness here.

[xazax.hun]

Thanks! Knowing the context, I am much happier with the direction overall. Is the plan to analyze a mock of std::optional instead of the actual code in the STL? How will that mock be shipped? Would that be embedded in the binary?

In D130306#3676475, @ymandel wrote:

Gabor, I fully agree. We need to start paying down the debt on the unsoundness, reducing it where possible and otherwise giving users control over whether to incur it.

I'm glad that this is still on the roadmap. I am a bit worried about how hard it will be to make the current memory model sound. Generally, I saw some researchers arguing that the access path approach approach is a better fit for dataflow analysis. See this paper as an example. Although admittedly, I do not fully agree with everything they claim, they focus on distributive problems in that paper, and I found that most actual problems that we want to solve are not distributive. But whatever model we end up using, to restore soundness we might need to introduce a way to summarize certain constructs in our memory model. There are some ideas in this survey paper.

However, as Sam wrote, we did not expect to be incurring any new unsoundness here.

I fully agree that this patch itself will not introduce new unsoundness (after the fixme mentioned in the description is resolved). My main concerns were:

• The framework started to feel more similar to symbolic execution than abstract interpretation, see the answer to this question on the differences.
• I was a bit worried that adding more features before fixing the soundness issues might make fixing those problems harder.
• I was not sure the current approach would scale to general context-sensitive analysis. But looks like that is a non-goal for now. Doing this to model certain types of interest makes sense to me and is a good first step.

Overall, I am excited for context-sensitive analysis, and some of my concerns are addressed. Looking forward to the follow-up patches :)

[samestep]

In D130306#3676672, @xazax.hun wrote:

Thanks! Knowing the context, I am much happier with the direction overall. Is the plan to analyze a mock of std::optional instead of the actual code in the STL? How will that mock be shipped? Would that be embedded in the binary?

Glad to hear it! Yes, the current plan is to analyze a mock of std::optional instead of the actual type. One reason for this is that we would like to use the same mock to model multiple different optional types (e.g. absl::optional) using the same mock. Our current plan is to embed it directly in the binary.

Overall, I am excited for context-sensitive analysis, and some of my concerns are addressed. Looking forward to the follow-up patches :)

Thanks Gábor! I'll let @ymandel and others respond to your other points; also, thanks for the links, those resources look very helpful.

[samestep]

@xazax.hun Do you have anything else you'd like addressed/changed (either here or in the doc we shared with you) before I land this?

[xazax.hun]

In D130306#3679294, @samestep wrote:

@xazax.hun Do you have anything else you'd like addressed/changed (either here or in the doc we shared with you) before I land this?

Nope, most of my concerns are unrelated to this patch. Sorry for hijacking the conversation with some offtopics. Feel free to land.

[ymandel]

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

64

optional, but in my experience, being explicit can help readability/findability in certain places.

[samestep]

Be explicit when constructing TransferOptions

[samestep]

Use different name for TransferOptions field

[chapuni]

A few variables cause warinings in -Asserts.

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

218

It is used only in assert.

224

ditto

[samestep]

In D130306#3680942, @chapuni wrote:

A few variables cause warinings in -Asserts.

Thanks for pointing this out! How should I address this? Should I just inline the definitions of those variables into the asserts themselves?

[ymandel]

In D130306#3681291, @samestep wrote:

In D130306#3680942, @chapuni wrote:

A few variables cause warinings in -Asserts.

Thanks for pointing this out! How should I address this? Should I just inline the definitions of those variables into the asserts themselves?

Someone took care of it: https://github.com/llvm/llvm-project/commit/1f8ae9d7e7e4afcc4e76728b28e64941660ca3eb

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

public:
   ///
   /// If `DeclCtx` is a function, initializes the environment with symbolic
   /// representations of the function parameters.
   ///
   /// If `DeclCtx` is a non-static member function, initializes the environment
   /// with a symbolic representation of the `this` pointee.
   Environment(DataflowAnalysisContext &DACtx, const DeclContext &DeclCtx);
 
+  /// Creates and returns an environment to use for context-sensitive analysis
+  /// of `Call`. 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 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;
+
   /// 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,
   ///  - have the same mappings from expressions to storage locations,
   ///  - have the same or equivalent (according to `Model`) values assigned to
   ///    the same storage locations.
   ///
   /// Requirements:

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

 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TRANSFER_H
 
 #include "clang/AST/Stmt.h"
 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
 
 namespace clang {
 namespace dataflow {
 
+struct TransferOptions {
+  /// Determines whether to analyze function bodies when present in the
+  /// translation unit.
+  bool ContextSensitive = false;
+};
+
 /// 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 StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env,
+              TransferOptions Options);
 
 } // namespace dataflow
 } // namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TRANSFER_H

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

 #include <vector>
 
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Stmt.h"
 #include "clang/Analysis/CFG.h"
 #include "clang/Analysis/FlowSensitive/ControlFlowContext.h"
 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
 #include "clang/Analysis/FlowSensitive/DataflowLattice.h"
+#include "clang/Analysis/FlowSensitive/Transfer.h"
 #include "llvm/ADT/Any.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/Support/Error.h"
 
 namespace clang {
 namespace dataflow {
 
 struct DataflowAnalysisOptions {
   /// Determines whether to apply the built-in transfer functions.
   // FIXME: Remove this option once the framework supports composing analyses
   // (at which point the built-in transfer functions can be simply a standalone
   // analysis).
   bool ApplyBuiltinTransfer = true;
+
+  /// Only has an effect if `ApplyBuiltinTransfer` is true.
+  TransferOptions BuiltinTransferOptions;
 };
 
 /// Type-erased lattice element container.
 ///
 /// Requirements:
 ///
 ///  The type of the object stored in the container must be a bounded
 ///  join-semilattice.
 struct TypeErasedLattice {
   llvm::Any Value;
 };
 
 /// Type-erased base class for dataflow analyses built on a single lattice type.
 class TypeErasedDataflowAnalysis : public Environment::ValueModel {
   DataflowAnalysisOptions Options;
 
 public:
   TypeErasedDataflowAnalysis() : Options({}) {}
 
   /// Deprecated. Use the `DataflowAnalysisOptions` constructor instead.
   TypeErasedDataflowAnalysis(bool ApplyBuiltinTransfer)
       : Options({ApplyBuiltinTransfer}) {}
 
   TypeErasedDataflowAnalysis(DataflowAnalysisOptions Options)
       : Options(Options) {}
 
   virtual ~TypeErasedDataflowAnalysis() {}
 
   /// Returns the `ASTContext` that is used by the analysis.
   virtual ASTContext &getASTContext() = 0;
public:
   /// Applies the analysis transfer function for a given statement and
   /// type-erased lattice element.
   virtual void transferTypeErased(const Stmt *, TypeErasedLattice &,
                                   Environment &) = 0;
 
   /// Determines whether to apply the built-in transfer functions, which model
   /// the heap and stack in the `Environment`.
   bool applyBuiltinTransfer() const { return Options.ApplyBuiltinTransfer; }
+
+  /// Returns the options to be passed to the built-in transfer functions.
+  TransferOptions builtinTransferOptions() const {
+    return Options.BuiltinTransferOptions;
+  }
 };
 
 /// Type-erased model of the program at a given program point.
 struct TypeErasedDataflowAnalysisState {
   /// Type-erased model of a program property.
   TypeErasedLattice Lattice;
 
   /// Model of the state of the program (store and heap).

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

if (MethodDecl && !MethodDecl->isStatic()) {
         DACtx.setThisPointeeStorageLocation(ThisPointeeLoc);
         if (Value *ThisPointeeVal = createValue(ThisPointeeType))
           setValue(ThisPointeeLoc, *ThisPointeeVal);
       }
     }
   }
 }
 
+Environment Environment::pushCall(const CallExpr *Call) const {
+  Environment Env(*this);
+
+  // FIXME: Currently this only works if the callee is never a method and the
+  // same callee is never analyzed from multiple separate callsites. To
+  // generalize this, we'll need to store a "context" field (probably a stack of
+  // `const Call Expr *`s) in the `Environment`, and then change the
+  // `DataflowAnalysisContext` class to hold a map from contexts to "frames",
+  // where each frame stores its own version of what are currently the
+  // `DeclToLoc`, `ExprToLoc`, and `ThisPointeeLoc` fields.
+
+  const auto *FuncDecl = Call->getDirectCallee();
+  assert(FuncDecl != nullptr);
+  const auto *Body = FuncDecl->getBody();
+  assert(Body != nullptr);
+  initGlobalVars(*Body, Env);
+
+  auto ParamIt = FuncDecl->param_begin();
+  auto ParamEnd = FuncDecl->param_end();
+  auto ArgIt = Call->arg_begin();
+  auto ArgEnd = Call->arg_end();
+
+  // FIXME: We iterate through the arguments instead of the parameters with the
+  // intention that this will still work in the presence of default parameters,
+  // but in general that is probably insufficient because those default
+  // parameters still need to be given `StorageLocation`s anyway, so this code
+  // will need to be generalized later.
+  for (; ArgIt != ArgEnd; ++ParamIt, ++ArgIt) {
+    assert(ParamIt != ParamEnd);
+
+    const VarDecl *Param = *ParamIt;
+    const Expr *Arg = *ArgIt;
+    auto *ArgLoc = Env.getStorageLocation(*Arg, SkipPast::Reference);
+    assert(ArgLoc != nullptr);
+    Env.setStorageLocation(*Param, *ArgLoc);
+  }
+
+  return Env;
+}
+
 bool Environment::equivalentTo(const Environment &Other,
                                Environment::ValueModel &Model) const {
   assert(DACtx == Other.DACtx);
 
   if (DeclToLoc != Other.DeclToLoc)
     return false;
 
   if (ExprToLoc != Other.ExprToLoc)

clang/lib/Analysis/FlowSensitive/Transfer.cpp

 #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"
+#include "clang/Analysis/FlowSensitive/ControlFlowContext.h"
 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
+#include "clang/Analysis/FlowSensitive/NoopAnalysis.h"
 #include "clang/Analysis/FlowSensitive/Value.h"
 #include "clang/Basic/Builtins.h"
 #include "clang/Basic/OperatorKinds.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/Casting.h"
 #include <cassert>
 #include <memory>
 #include <tuple>
if (auto *RHSValue =
             dyn_cast_or_null<BoolValue>(Env.getValue(RHS, SkipPast::Reference)))
       return Env.makeIff(*LHSValue, *RHSValue);
 
   return Env.makeAtomicBoolValue();
 }
 
 class TransferVisitor : public ConstStmtVisitor<TransferVisitor> {
 public:
-  TransferVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env)
-      : StmtToEnv(StmtToEnv), Env(Env) {}
+  TransferVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env,
+                  TransferOptions Options)
+      : StmtToEnv(StmtToEnv), Env(Env), Options(Options) {}
 
   void VisitBinaryOperator(const BinaryOperator *S) {
     const Expr *LHS = S->getLHS();
     assert(LHS != nullptr);
 
     const Expr *RHS = S->getRHS();
     assert(RHS != nullptr);
 
if (S->isCallToStdMove()) {
       assert(S->getNumArgs() > 0);
       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, which we only do if we
+      // have the callee body available in the translation unit.
+      if (!Options.ContextSensitive || F->getBody() == nullptr)
+        return;
+
+      auto &ASTCtx = F->getASTContext();
+
+      // FIXME: Cache these CFGs.
+      auto CFCtx = ControlFlowContext::build(F, F->getBody(), &ASTCtx);
+      // FIXME: Handle errors here and below.
+      assert(CFCtx);
+      auto ExitBlock = CFCtx->getCFG().getExit().getBlockID();
+
+      auto CalleeEnv = Env.pushCall(S);
+
+      // FIXME: Use the same analysis as the caller for the callee.
+      DataflowAnalysisOptions Options;
+      auto Analysis = NoopAnalysis(ASTCtx, Options);
+
+      auto BlockToOutputState =
+          dataflow::runDataflowAnalysis(*CFCtx, Analysis, CalleeEnv);
+      assert(BlockToOutputState);
+      assert(ExitBlock < BlockToOutputState->size());
+
+      auto ExitState = (*BlockToOutputState)[ExitBlock];
+      assert(ExitState);
+
+      Env = ExitState->Env;
     }
   }
 
   void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *S) {
     const Expr *SubExpr = S->getSubExpr();
     assert(SubExpr != nullptr);
 
     auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
BoolValue &getLogicOperatorSubExprValue(const Expr &SubExpr) {
 
     // If the value of `SubExpr` is still unknown, we create a fresh symbolic
     // boolean value for it.
     return Env.makeAtomicBoolValue();
   }
 
   const StmtToEnvMap &StmtToEnv;
   Environment &Env;
+  TransferOptions Options;
 };
 
-void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env) {
-  TransferVisitor(StmtToEnv, Env).Visit(&S);
+void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env,
+              TransferOptions Options) {
+  TransferVisitor(StmtToEnv, Env, Options).Visit(&S);
 }
 
 } // namespace dataflow
 } // namespace clang

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

static int blockIndexInPredecessor(const CFGBlock &Pred,
   return BlockPos - Pred.succ_begin();
 }
 
 /// Extends the flow condition of an environment based on a terminator
 /// statement.
 class TerminatorVisitor : public ConstStmtVisitor<TerminatorVisitor> {
 public:
   TerminatorVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env,
-                    int BlockSuccIdx)
-      : StmtToEnv(StmtToEnv), Env(Env), BlockSuccIdx(BlockSuccIdx) {}
+                    int BlockSuccIdx, TransferOptions TransferOptions)
+      : StmtToEnv(StmtToEnv), Env(Env), BlockSuccIdx(BlockSuccIdx),
+        TransferOptions(TransferOptions) {}
 
   void VisitIfStmt(const IfStmt *S) {
     auto *Cond = S->getCond();
     assert(Cond != nullptr);
     extendFlowCondition(*Cond);
   }
 
   void VisitWhileStmt(const WhileStmt *S) {
void VisitConditionalOperator(const ConditionalOperator *S) {
     assert(Cond != nullptr);
     extendFlowCondition(*Cond);
   }
 
 private:
   void extendFlowCondition(const Expr &Cond) {
     // The terminator sub-expression might not be evaluated.
     if (Env.getStorageLocation(Cond, SkipPast::None) == nullptr)
-      transfer(StmtToEnv, Cond, Env);
+      transfer(StmtToEnv, Cond, Env, TransferOptions);
 
     // 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);
 
     Env.addToFlowCondition(*Val);
   }
 
   const StmtToEnvMap &StmtToEnv;
   Environment &Env;
   int BlockSuccIdx;
+  TransferOptions TransferOptions;
 };
 
 /// 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
for (const CFGBlock *Pred : Preds) {
     if (!MaybePredState)
       continue;
 
     TypeErasedDataflowAnalysisState PredState = MaybePredState.value();
     if (ApplyBuiltinTransfer) {
       if (const Stmt *PredTerminatorStmt = Pred->getTerminatorStmt()) {
         const StmtToEnvMapImpl StmtToEnv(CFCtx, BlockStates);
         TerminatorVisitor(StmtToEnv, PredState.Env,
-                          blockIndexInPredecessor(*Pred, Block))
+                          blockIndexInPredecessor(*Pred, Block),
+                          Analysis.builtinTransferOptions())
             .Visit(PredTerminatorStmt);
       }
     }
 
     if (MaybeState) {
       Analysis.joinTypeErased(MaybeState->Lattice, PredState.Lattice);
       MaybeState->Env.join(PredState.Env, Analysis);
     } else {
static void transferCFGStmt(
     TypeErasedDataflowAnalysisState &State,
     std::function<void(const CFGStmt &,
                        const TypeErasedDataflowAnalysisState &)>
         HandleTransferredStmt) {
   const Stmt *S = CfgStmt.getStmt();
   assert(S != nullptr);
 
   if (Analysis.applyBuiltinTransfer())
-    transfer(StmtToEnvMapImpl(CFCtx, BlockStates), *S, State.Env);
+    transfer(StmtToEnvMapImpl(CFCtx, BlockStates), *S, State.Env,
+             Analysis.builtinTransferOptions());
   Analysis.transferTypeErased(S, State.Lattice, State.Env);
 
   if (HandleTransferredStmt != nullptr)
     HandleTransferredStmt(CfgStmt, State);
 }
 
 /// Transfers `State` by evaluating `CfgInit`.
 static void transferCFGInitializer(const CFGInitializer &CfgInit,

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

 using ::testing::ElementsAre;
 using ::testing::IsNull;
 using ::testing::NotNull;
 using ::testing::Pair;
 using ::testing::SizeIs;
 
 template <typename Matcher>
 void runDataflow(llvm::StringRef Code, Matcher Match,
-                  LangStandard::Kind Std = LangStandard::lang_cxx17,
-                  bool ApplyBuiltinTransfer = true,
-                  llvm::StringRef TargetFun = "target") {
+                 DataflowAnalysisOptions Options,
   ASSERT_THAT_ERROR(
       test::checkDataflow<NoopAnalysis>(
           Code, TargetFun,
-          [ApplyBuiltinTransfer](ASTContext &C, Environment &) {
-            return NoopAnalysis(C, ApplyBuiltinTransfer);
+          [Options](ASTContext &C, Environment &) {
+            return NoopAnalysis(C, Options);
           },
           [&Match](
               llvm::ArrayRef<
                   std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
                   Results,
               ASTContext &ASTCtx) { Match(Results, ASTCtx); },
           {"-fsyntax-only", "-fno-delayed-template-parsing",
-            "-std=" +
-                std::string(
+           "-std=" + std::string(
                          LangStandard::getLangStandardForKind(Std).getName())}),
       llvm::Succeeded());
 }
 
+template <typename Matcher>
+void runDataflow(llvm::StringRef Code, Matcher Match,
+                 LangStandard::Kind Std = LangStandard::lang_cxx17,
+                 bool ApplyBuiltinTransfer = true,
+                 llvm::StringRef TargetFun = "target") {
+  runDataflow(Code, Match, {ApplyBuiltinTransfer}, Std, TargetFun);
+}
+
 TEST(TransferTest, IntVarDeclNotTrackedWhenTransferDisabled) {
   std::string Code = R"(
     void target() {
       int Foo;
       // [[p]]
     }
   )";
   runDataflow(
runDataflow(
         ASSERT_THAT(FooDecl, NotNull());
 
         BoolValue &LoopBodyFooVal =
             *cast<BoolValue>(LoopBodyEnv.getValue(*FooDecl, SkipPast::None));
         EXPECT_FALSE(LoopBodyEnv.flowConditionImplies(LoopBodyFooVal));
       });
 }
 
+TEST(TransferTest, ContextSensitiveOptionDisabled) {
+  std::string Code = R"(
+    bool GiveBool();
+    void SetBool(bool &Var) { Var = true; }
+
+    void target() {
+      bool Foo = GiveBool();
+      SetBool(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());
+
+                auto &FooVal =
+                    *cast<BoolValue>(Env.getValue(*FooDecl, SkipPast::None));
+                EXPECT_FALSE(Env.flowConditionImplies(FooVal));
+              },
+              {/*.ApplyBuiltinTransfer=*/true,
+               /*.BuiltinTransferOptions=*/{/*.ContextSensitive=*/false}});
+}
+
+TEST(TransferTest, ContextSensitiveSetTrue) {
+  std::string Code = R"(
+    bool GiveBool();
+    void SetBool(bool &Var) { Var = true; }
+
+    void target() {
+      bool Foo = GiveBool();
+      SetBool(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());
+
+                auto &FooVal =
+                    *cast<BoolValue>(Env.getValue(*FooDecl, SkipPast::None));
+                EXPECT_TRUE(Env.flowConditionImplies(FooVal));
+              },
+              {/*.ApplyBuiltinTransfer=*/true,
+               /*.BuiltinTransferOptions=*/{/*.ContextSensitive=*/true}});
+}
+
+TEST(TransferTest, ContextSensitiveSetFalse) {
+  std::string Code = R"(
+    bool GiveBool();
+    void SetBool(bool &Var) { Var = false; }
+
+    void target() {
+      bool Foo = GiveBool();
+      SetBool(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());
+
+                auto &FooVal =
+                    *cast<BoolValue>(Env.getValue(*FooDecl, SkipPast::None));
+                EXPECT_TRUE(Env.flowConditionImplies(Env.makeNot(FooVal)));
+              },
+              {/*.ApplyBuiltinTransfer=*/true,
+               /*.BuiltinTransferOptions=*/{/*.ContextSensitive=*/true}});
+}
+
 } // namespace