[clang][dataflow] Add support for (built-in) (in)equality operators

[ymandel]

Summary

Adds logical interpretation of built-in equality operators, == and !=.

[xazax.hun]

clang/lib/Analysis/FlowSensitive/Transfer.cpp

56

I think a possible alternative way to handle this is to do some sort of "unification" for the two values. The current approach is superior in the sense that solving and generating constraints are clearly separate. Also this might be better for generating useful error messages. In case the solver ever becomes a bottleneck, I wonder whether replacing this with a unification step would speed things up a bit.
Although that would only work for the equality case.

[ymandel]

clang/lib/Analysis/FlowSensitive/Transfer.cpp

56

That's a good point. Although I wonder if we could get the best of both worlds by adding a unification pre-step to the solver itself, basically looking for iff patterns of this sort. Then, the solver could keep a record of such unifications which it could export for diagnostic purposes.

On a related note, another potential use of unification is in equivalence testing of environments. Instead of strict equality of flow conditions, for example, I could imagine equivalence up to unification (aka. renaming of atoms).

[sgatev]

clang/lib/Analysis/FlowSensitive/Transfer.cpp

53

Do we need to skip past references here? If so, then let's add a test that fails if these are changed to SkipPast::None.

109–113

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

2413

2448

[ymandel]

address comments

[ymandel]

clang/lib/Analysis/FlowSensitive/Transfer.cpp

53

Yes -- both of the new tests fail when we don't do this. It's actually hard to construct a test that passes without this, since DeclRefExprs of boolean type are ReferenceValue.

56

I think this connects to our discussion here: https://reviews.llvm.org/D122838?id=419518#inline-1175582

This seems like another example where tracking equivalences in the environment would be beneficial.

clang/lib/Analysis/FlowSensitive/Transfer.cpp

 #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/DataflowEnvironment.h"
+#include "clang/Analysis/FlowSensitive/Value.h"
 #include "clang/Basic/OperatorKinds.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/Casting.h"
 #include <cassert>
 #include <memory>
 #include <tuple>
 
 namespace clang {
 namespace dataflow {
 
 static const Expr *skipExprWithCleanups(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)))
+      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.
case BO_LOr: {
       auto &Loc = Env.createStorageLocation(*S);
       Env.setStorageLocation(*S, Loc);
       if (S->getOpcode() == BO_LAnd)
         Env.setValue(Loc, Env.makeAnd(LHSVal, RHSVal));
       else
         Env.setValue(Loc, Env.makeOr(LHSVal, RHSVal));
       break;
     }
+    case BO_NE:
+    case BO_EQ: {
+      auto &LHSAndRHSValue = evaluateBooleanEquality(*LHS, *RHS, Env);
+      auto &Loc = Env.createStorageLocation(*S);
+      Env.setStorageLocation(*S, Loc);
+      Env.setValue(Loc, S->getOpcode() == BO_EQ ? LHSAndRHSValue
+                                                : Env.makeNot(LHSAndRHSValue));
+      break;
+    }
     default:
-      // FIXME: Add support for BO_EQ, BO_NE.
       break;
     }
   }
 
   void VisitDeclRefExpr(const DeclRefExpr *S) {
     assert(S->getDecl() != nullptr);
     auto *DeclLoc = Env.getStorageLocation(*S->getDecl(), SkipPast::None);
     if (DeclLoc == nullptr)

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

runDataflow(Code,
                     cast<IntegerValue>(Env.getValue(*BarDecl, SkipPast::None));
 
                 const auto *A2Val =
                     cast<StructValue>(Env.getValue(*A2Decl, SkipPast::None));
                 EXPECT_EQ(A2Val->getChild(*FooDecl), BarVal);
               });
 }
 
+TEST_F(TransferTest, Equality) {
+  std::string Code = R"(
+    void target(bool Bar) {
+      bool Foo = true;
+      if (Bar == Foo) {
+        (void)0;
+        /*[[p-then]]*/
+      } else {
+        (void)0;
+        /*[[p-else]]*/
+      }
+    }
+  )";
+  runDataflow(
+      Code, [](llvm::ArrayRef<
+                   std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+                   Results,
+               ASTContext &ASTCtx) {
+        ASSERT_THAT(Results, ElementsAre(Pair("p-else", _), Pair("p-then", _)));
+        const Environment &EnvElse = Results[0].second.Env;
+        const Environment &EnvThen = Results[1].second.Env;
+
+        const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
+        ASSERT_THAT(BarDecl, NotNull());
+
+        auto &BarValThen =
+            *cast<BoolValue>(EnvThen.getValue(*BarDecl, SkipPast::None));
+        EXPECT_TRUE(EnvThen.flowConditionImplies(BarValThen));
+
+        auto &BarValElse =
+            *cast<BoolValue>(EnvElse.getValue(*BarDecl, SkipPast::None));
+        EXPECT_FALSE(EnvElse.flowConditionImplies(BarValElse));
+      });
+}
+
+TEST_F(TransferTest, Inequality) {
+  std::string Code = R"(
+    void target(bool Bar) {
+      bool Foo = true;
+      if (Bar != Foo) {
+        (void)0;
+        /*[[p-then]]*/
+      } else {
+        (void)0;
+        /*[[p-else]]*/
+      }
+    }
+  )";
+  runDataflow(
+      Code, [](llvm::ArrayRef<
+                   std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+                   Results,
+               ASTContext &ASTCtx) {
+        ASSERT_THAT(Results, ElementsAre(Pair("p-else", _), Pair("p-then", _)));
+        const Environment &EnvElse = Results[0].second.Env;
+        const Environment &EnvThen = Results[1].second.Env;
+
+        const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
+        ASSERT_THAT(BarDecl, NotNull());
+
+        auto &BarValThen =
+            *cast<BoolValue>(EnvThen.getValue(*BarDecl, SkipPast::None));
+        EXPECT_FALSE(EnvThen.flowConditionImplies(BarValThen));
+
+        auto &BarValElse =
+            *cast<BoolValue>(EnvElse.getValue(*BarDecl, SkipPast::None));
+        EXPECT_TRUE(EnvElse.flowConditionImplies(BarValElse));
+      });
+}
+
 } // namespace