[clang][dataflow] Centralize expression skipping logic

[li.zhe.hua]

Summary

A follow-up to 62b2a47 to centralize the logic that skips expressions
that the CFG does not emit. This allows client code to avoid
sprinkling this logic everywhere.

Add redirects in the transfer function to similarly skip such
expressions by forwarding the visit to the sub-expression.

[ymandel]

Thanks!

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

368

maybe bind to a temporary to avoid doing this twice (in debug code, that is)? arguably not that important to optimize debug mode but may also improve readability.

clang/lib/Analysis/FlowSensitive/Transfer.cpp

38–41

Is the idea that the skipping is now built into getValue via getStorageLocation?

545–561

I thought this is the default behavior?

[li.zhe.hua]

Address reviewer comments

clang/lib/Analysis/FlowSensitive/Transfer.cpp

38–41

I don't believe I fixed this. d002495 addressed this by having integral casts route to the sub-expression.

545–561

The default behavior of StmtVisitor is that VisitFoo will call VisitFooBase where Foo derives from FooBase (e.g. the default implementation of VisitExprWithCleanups calls VisitFullExpr). The base case is a VisitStmt implementation that does approximately nothing, especially if RetTy = void.

So in this case, I'm changing this to automatically ignore ParenExpr and ExprWithCleanups and visit the sub-expression, which is not the default behavior.

This isn't used when we call the transfer function from CFG-provided statements, because the CFG doesn't emit these nodes. However, this is relevant when we manually call the transfer function, e.g. from here.

[ymandel]

clang/lib/Analysis/FlowSensitive/Transfer.cpp

38–41

Great. Just to be sure I understand: you mean that the IgnoreCasts() calls were already redundant because of d002495?

545–561

Interesting. Thanks for the explanation!

[li.zhe.hua]

clang/lib/Analysis/FlowSensitive/Transfer.cpp

38–41

Correct, that's my understanding. This diff hunk could be separately committed first. (And maybe it should, for blame clarity.)

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h

 #include <memory>
 #include <type_traits>
 #include <utility>
 #include <vector>
 
 namespace clang {
 namespace dataflow {
 
+/// Skip past nodes that the CFG does not emit. These nodes are invisible to
+/// flow-sensitive analysis, and should be ignored as they will effectively not
+/// exist.
+///
+///   * `ParenExpr` - The CFG takes the operator precedence into account, but
+///   otherwise omits the node afterwards.
+///
+///   * `ExprWithCleanups` - The CFG will generate the appropriate calls to
+///   destructors and then omit the node.
+///
+const Expr &ignoreCFGOmittedNodes(const Expr &E);
+const Stmt &ignoreCFGOmittedNodes(const Stmt &S);
+
 /// Owns objects that encompass the state of a program and stores context that
 /// is used during dataflow analysis.
 class DataflowAnalysisContext {
 public:
   /// Constructs a dataflow analysis context.
   ///
   /// Requirements:
   ///
public:
   }
 
   /// Assigns `Loc` as the storage location of `E`.
   ///
   /// Requirements:
   ///
   ///  `E` must not be assigned a storage location.
   void setStorageLocation(const Expr &E, StorageLocation &Loc) {
-    assert(ExprToLoc.find(&E) == ExprToLoc.end());
-    ExprToLoc[&E] = &Loc;
+    assert(ExprToLoc.find(&ignoreCFGOmittedNodes(E)) == ExprToLoc.end());
+    ExprToLoc[&ignoreCFGOmittedNodes(E)] = &Loc;
   }
 
   /// Returns the storage location assigned to `E` or null if `E` has no
   /// assigned storage location.
   StorageLocation *getStorageLocation(const Expr &E) const {
-    auto It = ExprToLoc.find(&E);
+    auto It = ExprToLoc.find(&ignoreCFGOmittedNodes(E));
     return It == ExprToLoc.end() ? nullptr : It->second;
   }
 
   /// Assigns `Loc` as the storage location of the `this` pointee.
   ///
   /// Requirements:
   ///
   ///  The `this` pointee must not be assigned a storage location.

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

public:
   /// Creates a storage location for `D`. Does not assign the returned storage
   /// location to `D` in the environment. Does not assign a value to the
   /// returned storage location in the environment.
   StorageLocation &createStorageLocation(const VarDecl &D);
 
   /// Creates a storage location for `E`. Does not assign the returned storage
   /// location to `E` in the environment. Does not assign a value to the
   /// returned storage location in the environment.
-  ///
-  /// Requirements:
-  ///
-  ///  `E` must not be a `ExprWithCleanups`.
   StorageLocation &createStorageLocation(const Expr &E);
 
   /// Assigns `Loc` as the storage location of `D` in the environment.
   ///
   /// Requirements:
   ///
   ///  `D` must not be assigned a storage location in the environment.
   void setStorageLocation(const ValueDecl &D, StorageLocation &Loc);
 
   /// Returns the storage location assigned to `D` in the environment, applying
   /// the `SP` policy for skipping past indirections, or null if `D` isn't
   /// assigned a storage location in the environment.
   StorageLocation *getStorageLocation(const ValueDecl &D, SkipPast SP) const;
 
   /// Assigns `Loc` as the storage location of `E` in the environment.
   ///
   /// Requirements:
   ///
   ///  `E` must not be assigned a storage location in the environment.
-  ///  `E` must not be a `ExprWithCleanups`.
   void setStorageLocation(const Expr &E, StorageLocation &Loc);
 
   /// Returns the storage location assigned to `E` in the environment, applying
   /// the `SP` policy for skipping past indirections, or null if `E` isn't
   /// assigned a storage location in the environment.
-  ///
-  /// Requirements:
-  ///
-  ///  `E` must not be a `ExprWithCleanups`.
   StorageLocation *getStorageLocation(const Expr &E, SkipPast SP) const;
 
   /// Returns the storage location assigned to the `this` pointee in the
   /// environment or null if the `this` pointee has no assigned storage location
   /// in the environment.
   StorageLocation *getThisPointeeStorageLocation() const;
 
   /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise
public:
   Value *getValue(const StorageLocation &Loc) const;
 
   /// Equivalent to `getValue(getStorageLocation(D, SP), SkipPast::None)` if `D`
   /// is assigned a storage location in the environment, otherwise returns null.
   Value *getValue(const ValueDecl &D, SkipPast SP) const;
 
   /// Equivalent to `getValue(getStorageLocation(E, SP), SkipPast::None)` if `E`
   /// is assigned a storage location in the environment, otherwise returns null.
-  ///
-  /// Requirements:
-  ///
-  ///  `E` must not be a `ExprWithCleanups`.
-  ///
-  /// FIXME: `Environment` should ignore any `ExprWithCleanups` it sees.
   Value *getValue(const Expr &E, SkipPast SP) const;
 
   /// Transfers ownership of `Loc` to the analysis context and returns a
   /// reference to it.
   ///
   /// Requirements:
   ///
   ///  `Loc` must not be null.

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

 
 /// Evaluates `S` and updates `Env` accordingly.
 ///
 /// Requirements:
 ///
 ///  `S` must not be `ParenExpr` or `ExprWithCleanups`.
 void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env);
 
-/// Skip past a `ExprWithCleanups` which might surround `E`. Returns null if `E`
-/// is null.
-///
-/// The CFG omits `ExprWithCleanups` nodes (as it does with `ParenExpr`), and so
-/// the transfer function doesn't accept them as valid input. Manual traversal
-/// of the AST should skip and unwrap any `ExprWithCleanups` it might expect to
-/// see. They are safe to skip, as the CFG will emit calls to destructors as
-/// appropriate.
-const Expr *ignoreExprWithCleanups(const Expr *E);
-
 } // namespace dataflow
 } // namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_TRANSFER_H

clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp

 //===-- DataflowAnalysisContext.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 a DataflowAnalysisContext class that owns objects that
 //  encompass the state of a program and stores context that is used during
 //  dataflow analysis.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
+#include "clang/AST/ExprCXX.h"
 #include "clang/Analysis/FlowSensitive/Value.h"
 #include <cassert>
 #include <memory>
 #include <utility>
 
 namespace clang {
 namespace dataflow {
 
if (DepsIT != FlowConditionDeps.end()) {
     for (AtomicBoolValue *DepToken : DepsIT->second)
       addTransitiveFlowConditionConstraints(*DepToken, Constraints,
                                             VisitedTokens);
   }
 }
 
 } // namespace dataflow
 } // namespace clang
+
+using namespace clang;
+
+const Expr &clang::dataflow::ignoreCFGOmittedNodes(const Expr &E) {
+  const Expr *Current = &E;
+  if (auto *EWC = dyn_cast<ExprWithCleanups>(Current)) {
+    Current = EWC->getSubExpr();
+    assert(Current != nullptr);
+  }
+  Current = Current->IgnoreParens();
+  assert(Current != nullptr);
+  return *Current;
+}
+
+const Stmt &clang::dataflow::ignoreCFGOmittedNodes(const Stmt &S) {
+  if (auto *E = dyn_cast<Expr>(&S))
+    return ignoreCFGOmittedNodes(*E);
+  return S;
+}

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

StorageLocation &Environment::createStorageLocation(const VarDecl &D) {
   if (auto *Loc = DACtx->getStorageLocation(D))
     return *Loc;
   auto &Loc = createStorageLocation(D.getType());
   DACtx->setStorageLocation(D, Loc);
   return Loc;
 }
 
 StorageLocation &Environment::createStorageLocation(const Expr &E) {
-  assert(!isa<ExprWithCleanups>(&E));
   // Evaluated expressions are always assigned the same storage locations to
   // ensure that the environment stabilizes across loop iterations. Storage
   // locations for evaluated expressions are stored in the analysis context.
   if (auto *Loc = DACtx->getStorageLocation(E))
     return *Loc;
   auto &Loc = createStorageLocation(E.getType());
   DACtx->setStorageLocation(E, Loc);
   return Loc;
 }
 
 void Environment::setStorageLocation(const ValueDecl &D, StorageLocation &Loc) {
   assert(DeclToLoc.find(&D) == DeclToLoc.end());
   DeclToLoc[&D] = &Loc;
 }
 
 StorageLocation *Environment::getStorageLocation(const ValueDecl &D,
                                                  SkipPast SP) const {
   auto It = DeclToLoc.find(&D);
   return It == DeclToLoc.end() ? nullptr : &skip(*It->second, SP);
 }
 
 void Environment::setStorageLocation(const Expr &E, StorageLocation &Loc) {
-  assert(!isa<ExprWithCleanups>(&E));
-  assert(ExprToLoc.find(&E) == ExprToLoc.end());
-  ExprToLoc[&E] = &Loc;
+  assert(ExprToLoc.find(&ignoreCFGOmittedNodes(E)) == ExprToLoc.end());
+  ExprToLoc[&ignoreCFGOmittedNodes(E)] = &Loc;
 }
 
 StorageLocation *Environment::getStorageLocation(const Expr &E,
                                                  SkipPast SP) const {
-  assert(!isa<ExprWithCleanups>(&E));
   // FIXME: Add a test with parens.
-  auto It = ExprToLoc.find(E.IgnoreParens());
+  auto It = ExprToLoc.find(&ignoreCFGOmittedNodes(E));
   return It == ExprToLoc.end() ? nullptr : &skip(*It->second, SP);
 }
 
 StorageLocation *Environment::getThisPointeeStorageLocation() const {
   return DACtx->getThisPointeeStorageLocation();
 }
 
 void Environment::setValue(const StorageLocation &Loc, Value &Val) {

clang/lib/Analysis/FlowSensitive/Transfer.cpp

 #include "llvm/Support/Casting.h"
 #include <cassert>
 #include <memory>
 #include <tuple>
 
 namespace clang {
 namespace dataflow {
 
-const Expr *ignoreExprWithCleanups(const Expr *E) {
-  if (auto *C = dyn_cast_or_null<ExprWithCleanups>(E))
-    return C->getSubExpr();
-  return E;
-}
-
 static BoolValue &evaluateBooleanEquality(const Expr &LHS, const Expr &RHS,
                                           Environment &Env) {
-  // Equality of booleans involves implicit integral casts. Ignore these casts
-  // for now and focus on the values associated with the wrapped expressions.
-  // FIXME: Consider changing this once the framework offers better support for
-  // integral casts.
-  const Expr *LHSNorm = LHS.IgnoreCasts();
-  const Expr *RHSNorm = RHS.IgnoreCasts();
-  assert(LHSNorm != nullptr);
-  assert(RHSNorm != nullptr);
-
-  if (auto *LHSValue = dyn_cast_or_null<BoolValue>(
-          Env.getValue(*LHSNorm, SkipPast::Reference)))
-    if (auto *RHSValue = dyn_cast_or_null<BoolValue>(
-            Env.getValue(*RHSNorm, SkipPast::Reference)))
+  if (auto *LHSValue =
+          dyn_cast_or_null<BoolValue>(Env.getValue(LHS, SkipPast::Reference)))
+    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) {}
 
   void VisitBinaryOperator(const BinaryOperator *S) {
-    // The CFG does not contain `ParenExpr` as top-level statements in basic
-    // blocks, however sub-expressions can still be of that type.
-    assert(S->getLHS() != nullptr);
-    const Expr *LHS = S->getLHS()->IgnoreParens();
+    const Expr *LHS = S->getLHS();
     assert(LHS != nullptr);
 
-    assert(S->getRHS() != nullptr);
-    const Expr *RHS = S->getRHS()->IgnoreParens();
+    const Expr *RHS = S->getRHS();
     assert(RHS != nullptr);
 
     switch (S->getOpcode()) {
     case BO_Assign: {
       auto *LHSLoc = Env.getStorageLocation(*LHS, SkipPast::Reference);
       if (LHSLoc == nullptr)
         break;
 
void VisitDeclStmt(const DeclStmt *S) {
     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);
       return;
     }
 
-    InitExpr = ignoreExprWithCleanups(D.getInit());
+    InitExpr = D.getInit();
     assert(InitExpr != nullptr);
 
     if (D.getType()->isReferenceType()) {
       // Initializing a reference variable - do not create a reference to
       // reference.
       if (auto *InitExprLoc =
               Env.getStorageLocation(*InitExpr, SkipPast::Reference)) {
         auto &Val =
if (S->isCallToStdMove()) {
       Env.setStorageLocation(*S, *ArgLoc);
     } else if (S->getDirectCallee() != nullptr &&
                S->getDirectCallee()->getBuiltinID() ==
                    Builtin::BI__builtin_expect) {
       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)->IgnoreParenImpCasts(), SkipPast::Reference);
+      auto *ArgLoc = Env.getStorageLocation(*S->getArg(0), SkipPast::Reference);
       if (ArgLoc == nullptr)
         return;
       Env.setStorageLocation(*S, *ArgLoc);
     }
   }
 
   void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *S) {
     const Expr *SubExpr = S->getSubExpr();
public:
   }
 
   void VisitCXXBoolLiteralExpr(const CXXBoolLiteralExpr *S) {
     auto &Loc = Env.createStorageLocation(*S);
     Env.setStorageLocation(*S, Loc);
     Env.setValue(Loc, Env.getBoolLiteralValue(S->getValue()));
   }
 
+  void VisitParenExpr(const ParenExpr *S) {
+    // The CFG does not contain `ParenExpr` as top-level statements in basic
+    // blocks, however manual traversal to sub-expressions may encounter them.
+    // Redirect to the sub-expression.
+    auto *SubExpr = S->getSubExpr();
+    assert(SubExpr != nullptr);
+    Visit(SubExpr);
+  }
+
+  void VisitExprWithCleanups(const ExprWithCleanups *S) {
+    // The CFG does not contain `ExprWithCleanups` as top-level statements in
+    // basic blocks, however manual traversal to sub-expressions may encounter
+    // them. Redirect to the sub-expression.
+    auto *SubExpr = S->getSubExpr();
+    assert(SubExpr != nullptr);
+    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 (auto *Val = dyn_cast_or_null<BoolValue>(
               SubExprEnv->getValue(SubExpr, SkipPast::Reference)))
BoolValue &getLogicOperatorSubExprValue(const Expr &SubExpr) {
     return Env.makeAtomicBoolValue();
   }
 
   const StmtToEnvMap &StmtToEnv;
   Environment &Env;
 };
 
 void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env) {
-  assert(!(isa<ParenExpr, ExprWithCleanups>(&S)));
   TransferVisitor(StmtToEnv, Env).Visit(&S);
 }
 
 } // namespace dataflow
 } // namespace clang

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

 public:
   StmtToEnvMapImpl(
       const ControlFlowContext &CFCtx,
       llvm::ArrayRef<llvm::Optional<TypeErasedDataflowAnalysisState>>
           BlockToState)
       : CFCtx(CFCtx), BlockToState(BlockToState) {}
 
   const Environment *getEnvironment(const Stmt &S) const override {
-    auto BlockIT = CFCtx.getStmtToBlock().find(&S);
+    auto BlockIT = CFCtx.getStmtToBlock().find(&ignoreCFGOmittedNodes(S));
     assert(BlockIT != CFCtx.getStmtToBlock().end());
     const auto &State = BlockToState[BlockIT->getSecond()->getBlockID()];
     assert(State.hasValue());
     return &State.getValue().Env;
   }
 
 private:
   const ControlFlowContext &CFCtx;

 /// statement.
 class TerminatorVisitor : public ConstStmtVisitor<TerminatorVisitor> {
 public:
   TerminatorVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env,
                     int BlockSuccIdx)
       : StmtToEnv(StmtToEnv), Env(Env), BlockSuccIdx(BlockSuccIdx) {}
 
   void VisitIfStmt(const IfStmt *S) {
-    auto *Cond = ignoreExprWithCleanups(S->getCond())->IgnoreParens();
+    auto *Cond = S->getCond();
     assert(Cond != nullptr);
     extendFlowCondition(*Cond);
   }
 
   void VisitWhileStmt(const WhileStmt *S) {
-    auto *Cond = ignoreExprWithCleanups(S->getCond())->IgnoreParens();
+    auto *Cond = S->getCond();
     assert(Cond != nullptr);
     extendFlowCondition(*Cond);
   }
 
   void VisitBinaryOperator(const BinaryOperator *S) {
     assert(S->getOpcode() == BO_LAnd || S->getOpcode() == BO_LOr);
-    auto *LHS = ignoreExprWithCleanups(S->getLHS())->IgnoreParens();
+    auto *LHS = S->getLHS();
     assert(LHS != nullptr);
     extendFlowCondition(*LHS);
   }
 
   void VisitConditionalOperator(const ConditionalOperator *S) {
-    auto *Cond = ignoreExprWithCleanups(S->getCond())->IgnoreParens();
+    auto *Cond = S->getCond();
     assert(Cond != nullptr);
     extendFlowCondition(*Cond);
   }
 
 private:
   void extendFlowCondition(const Expr &Cond) {
     // The terminator sub-expression might not be evaluated.
     if (Env.getValue(Cond, SkipPast::None) == nullptr)