[clang][dataflow] In `equivalentTo()`, ignore expression locations that are unlikely to matter.

[mboehme]

Summary

The locations of some glvalue expressions are discarded or are merely used in a LValueToRValue cast. However, the corresponding entries in ExprToLoc can currently prevent convergence.

As the framework itself does not query these locations, and a particular analysis is unlikely to query them either, we ignore them for the purpose of determining whether a block has converged (in Environment::equivalentTo()).

This patch adds two tests that do not converge without the other changes in the patch.

[mboehme]

Add a FIXME noting that this is a temporary solution.

clang/include/clang/Analysis/FlowSensitive/ControlFlowContext.h

const llvm::DenseMap<const Stmt *, const CFGBlock *> &getStmtToBlock() const {
     return StmtToBlock;
   }
 
   /// Returns whether `B` is reachable from the entry block.
   bool isBlockReachable(const CFGBlock &B) const {
     return BlockReachable[B.getBlockID()];
   }
 
+  /// Returns the parent of `S` or null if the parent could not be found.
+  /// `S` must be a descendant of the function or statement passed to `build()`.
+  const Stmt *getParent(const Stmt *S) const { return StmtToParent.lookup(S); }
+
 private:
   // FIXME: Once the deprecated `build` method is removed, mark `D` as "must not
   // be null" and add an assertion.
   ControlFlowContext(const Decl *D, std::unique_ptr<CFG> Cfg,
                      llvm::DenseMap<const Stmt *, const CFGBlock *> StmtToBlock,
-                     llvm::BitVector BlockReachable)
+                     llvm::BitVector BlockReachable,
+                     llvm::DenseMap<const Stmt *, const Stmt *> StmtToParent)
       : ContainingDecl(D), Cfg(std::move(Cfg)),
         StmtToBlock(std::move(StmtToBlock)),
-        BlockReachable(std::move(BlockReachable)) {}
+        BlockReachable(std::move(BlockReachable)),
+        StmtToParent(std::move(StmtToParent)) {}
 
   /// The `Decl` containing the statement used to construct the CFG.
   const Decl *ContainingDecl;
   std::unique_ptr<CFG> Cfg;
   llvm::DenseMap<const Stmt *, const CFGBlock *> StmtToBlock;
   llvm::BitVector BlockReachable;
+  llvm::DenseMap<const Stmt *, const Stmt *> StmtToParent;
 };
 
 } // namespace dataflow
 } // namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_CONTROLFLOWCONTEXT_H

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

public:
 
   /// Returns true if the formula is always true when this point is reached.
   /// Returns false if the formula may be false, or if the flow condition isn't
   /// sufficiently precise to prove that it is true.
   bool flowConditionImplies(const Formula &) const;
 
   /// Returns the `DeclContext` of the block being analysed, if any. Otherwise,
   /// returns null.
-  const DeclContext *getDeclCtx() const { return CallStack.back(); }
+  const DeclContext *getDeclCtx() const {
+    if (CallStack.empty())
+      return nullptr;
+    return CallStack.back();
+  }
 
   /// Returns the function currently being analyzed, or null if the code being
   /// analyzed isn't part of a function.
   const FunctionDecl *getCurrentFunc() const {
-    return dyn_cast<FunctionDecl>(getDeclCtx());
+    return dyn_cast_or_null<FunctionDecl>(getDeclCtx());
   }
 
   /// Returns whether this `Environment` can be extended to analyze the given
   /// `Callee` (i.e. if `pushCall` can be used), with recursion disallowed and a
   /// given `MaxDepth`.
   bool canDescend(unsigned MaxDepth, const DeclContext *Callee) const;
 
   /// Returns the `DataflowAnalysisContext` used by the environment.

clang/lib/Analysis/FlowSensitive/ControlFlowContext.cpp

while (!BlocksToVisit.empty()) {
     for (const CFGBlock *Succ : Block->succs())
       if (Succ)
         BlocksToVisit.push_back(Succ);
   }
 
   return BlockReachable;
 }
 
+static llvm::DenseMap<const Stmt *, const Stmt *>
+buildStmtToParentMap(const Stmt &S) {
+  llvm::DenseMap<const Stmt *, const Stmt *> Result;
+
+  llvm::SmallVector<const Stmt *> StmtsToVisit = {&S};
+  while (!StmtsToVisit.empty()) {
+    const Stmt *Parent = StmtsToVisit.back();
+    StmtsToVisit.pop_back();
+
+    for (const Stmt *Child : Parent->children()) {
+      if (Child == nullptr)
+        continue;
+
+      StmtsToVisit.push_back(Child);
+      Result[Child] = Parent;
+    }
+  }
+
+  return Result;
+}
+
 llvm::Expected<ControlFlowContext>
 ControlFlowContext::build(const FunctionDecl &Func) {
   if (!Func.hasBody())
     return llvm::createStringError(
         std::make_error_code(std::errc::invalid_argument),
         "Cannot analyze function without a body");
 
   return build(Func, *Func.getBody(), Func.getASTContext());
return llvm::createStringError(
         "CFG::buildCFG failed");
 
   llvm::DenseMap<const Stmt *, const CFGBlock *> StmtToBlock =
       buildStmtToBasicBlockMap(*Cfg);
 
   llvm::BitVector BlockReachable = findReachableBlocks(*Cfg);
 
   return ControlFlowContext(&D, std::move(Cfg), std::move(StmtToBlock),
-                            std::move(BlockReachable));
+                            std::move(BlockReachable), buildStmtToParentMap(S));
 }
 
 llvm::Expected<ControlFlowContext>
 ControlFlowContext::build(const Decl *D, Stmt &S, ASTContext &C) {
   if (D == nullptr)
     return llvm::createStringError(
         std::make_error_code(std::errc::invalid_argument),
         "Declaration must not be null");
 
   return build(*D, S, C);
 }
 
 } // namespace dataflow
 } // namespace clang

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

void Environment::popCall(const CXXConstructExpr *Call,
   this->LocToVal = std::move(CalleeEnv.LocToVal);
   this->FlowConditionToken = std::move(CalleeEnv.FlowConditionToken);
 
   if (Value *Val = CalleeEnv.getValue(*CalleeEnv.ThisPointeeLoc)) {
     setValue(*Call, *Val);
   }
 }
 
+/// Returns whether locations `Loc1` and `Loc2` associated with expression `E`
+/// in two different environments `Env1` and `Env2` should be considered
+/// equivalent.
+/// The idea is that the location of certain expressions is almost certainly not
+/// relevant for the result of the block, but changes in these locations may
+/// nevertheless hinder convergence.
+static bool exprLocsEquivalent(const Expr *E, StorageLocation *Loc1,
+                               StorageLocation *Loc2, const Environment &Env1,
+                               const Environment &Env2,
+                               Environment::ValueModel &Model,
+                               const ControlFlowContext *CFCtx) {
+  // prvalues have stable storage locations, so we don't need to compare them.
+  if (E->isPRValue())
+    return true;
+
+  // If we have no `ControlFlowContext`, we can't determine the parent of `E`,
+  // so we have to assume that location matters.
+  if (CFCtx == nullptr)
+    return Loc1 == Loc2;
+
+  const Stmt *Parent = CFCtx->getParent(E);
+  // An expression should always have a parent within the body of the function.
+  assert(Parent != nullptr);
+  if (Parent == nullptr)
+    return Loc1 == Loc2;
+
+  // If this an expression statement, the location is discarded.
+  if (isa<CompoundStmt>(Parent))
+    return true;
+
+  if (auto *Cast = dyn_cast<CastExpr>(Parent)) {
+    // If the expression is cast to void, its location is discarded.
+    if (Cast->getCastKind() == CK_ToVoid)
+      return true;
+
+    // If the expression is cast from an lvalue to an rvalue, its location is
+    // unlikely to matter. Instead, just compare the values.
+    if (Cast->getCastKind() == CK_LValueToRValue) {
+      if (Loc1 == nullptr || Loc2 == nullptr)
+          return Loc1 == Loc2;
+
+      Value *Val1 = Env1.getValue(*Loc1);
+      Value *Val2 = Env2.getValue(*Loc2);
+
+      if (Val1 == nullptr || Val2 == nullptr)
+          return Val1 == Val2;
+
+      return areEquivalentValues(*Val1, *Val2) ||
+             compareDistinctValues(E->getType(), *Val1, Env1, *Val2, Env2,
+                                   Model);
+    }
+  }
+
+  return Loc1 == Loc2;
+}
+
+/// Returns whether two `ExprToLoc` maps should be considered equivalent. The
+/// comparison ignores certain classes of expressions; see comments in
+/// `exprLocsEquivalent()`.
+/// FIXME: Ignoring certain classes of expressions is a temporary fix to aid
+/// convergence. As discussed in https://reviews.llvm.org/D156658, the real fix
+/// is to add widening for `PointerValue`s.
+static bool exprToLocEquivalent(
+    const llvm::DenseMap<const Expr *, StorageLocation *> &ExprToLoc1,
+    const llvm::DenseMap<const Expr *, StorageLocation *> &ExprToLoc2,
+    const Environment &Env1, const Environment &Env2,
+    Environment::ValueModel &Model) {
+  if (ExprToLoc1.size() != ExprToLoc2.size())
+    return false;
+
+  const ControlFlowContext *CFCtx = nullptr;
+  if (const FunctionDecl *Func = Env1.getCurrentFunc())
+    CFCtx = Env1.getDataflowAnalysisContext().getControlFlowContext(Func);
+
+  for (auto [E, Loc1] : ExprToLoc1) {
+    StorageLocation *Loc2 = ExprToLoc2.lookup(E);
+
+    if (!exprLocsEquivalent(E, Loc1, Loc2, Env1, Env2, Model, CFCtx))
+      return false;
+  }
+
+  return true;
+}
+
 bool Environment::equivalentTo(const Environment &Other,
                                Environment::ValueModel &Model) const {
   assert(DACtx == Other.DACtx);
 
   if (ReturnVal != Other.ReturnVal)
     return false;
 
   if (ReturnLoc != Other.ReturnLoc)
     return false;
 
   if (ThisPointeeLoc != Other.ThisPointeeLoc)
     return false;
 
   if (DeclToLoc != Other.DeclToLoc)
     return false;
 
-  if (ExprToLoc != Other.ExprToLoc)
+  if (!exprToLocEquivalent(ExprToLoc, Other.ExprToLoc, *this, Other, Model))
     return false;
 
   // Compare the contents for the intersection of their domains.
   for (auto &Entry : LocToVal) {
     const StorageLocation *Loc = Entry.first;
     assert(Loc != nullptr);
 
     Value *Val = Entry.second;

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

runDataflow(
 
         // The loop body may not have been executed, so we should not conclude
         // that `l` points to `val`.
         EXPECT_NE(&LVal->getPointeeLoc(),
                   OuterEnv.getStorageLocation(*ValDecl));
       });
 }
 
+TEST(TransferTest, LoopDereferencingChangingPointerConverges) {
+  std::string Code = R"cc(
+    bool some_condition();
+
+    void target(int i1, int i2) {
+      int *p = &i1;
+      while (true) {
+        // Dereference the pointer, producing an lvalue, in various ways where
+        // the location of the lvalue is not important.
+        *p;
+        (void)*p;
+        int unused = *p;
+
+        if (some_condition())
+          p = &i1;
+        else
+          p = &i2;
+      }
+    }
+  )cc";
+  // The key property that we are verifying is implicit in `runDataflow` --
+  // namely, that the analysis succeeds, rather than hitting the maximum number
+  // of iterations.
+  runDataflow(
+      Code,
+      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
+         ASTContext &ASTCtx) {});
+}
+
+TEST(TransferTest, LoopDereferencingChangingRecordPointerConverges) {
+  std::string Code = R"cc(
+    struct Lookup {
+      int x;
+    };
+
+    bool some_condition();
+
+    void target(Lookup l1, Lookup l2) {
+      Lookup *l = &l1;
+      while (true) {
+        // Access the member variable, producing an lvalue, in various ways
+        // where the location of the lvalue is not important.
+        l->x;
+        (void)l->x;
+        int unused = l->x;
+
+        if (some_condition())
+          l = &l1;
+        else
+          l = &l2;
+      }
+    }
+  )cc";
+  // The key property that we are verifying is implicit in `runDataflow` --
+  // namely, that the analysis succeeds, rather than hitting the maximum number
+  // of iterations.
+  runDataflow(
+      Code,
+      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
+         ASTContext &ASTCtx) {});
+}
+
 TEST(TransferTest, DoesNotCrashOnUnionThisExpr) {
   std::string Code = R"(
     union Union {
       int A;
       float B;
     };
 
     void foo() {