clang/unittests/Analysis/FlowSensitive/DataflowAnalysisContextTest.cpp

   1 //===- unittests/Analysis/FlowSensitive/DataflowAnalysisContextTest.cpp ---===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
  10 #include "clang/Analysis/FlowSensitive/WatchedLiteralsSolver.h"
  11 #include "gmock/gmock.h"
  12 #include "gtest/gtest.h"
  13 #include <memory>
  14
  15 namespace {
  16
  17 using namespace clang;
  18 using namespace dataflow;
  19
  20 class DataflowAnalysisContextTest : public ::testing::Test {
  21 protected:
  22   DataflowAnalysisContextTest()
  23       : Context(std::make_unique<WatchedLiteralsSolver>()), A(Context.arena()) {
  24   }
  25
  26   DataflowAnalysisContext Context;
  27   Arena &A;
  28 };
  29
  30 TEST_F(DataflowAnalysisContextTest, DistinctTopsNotEquivalent) {
  31   auto &X = A.makeTopValue();
  32   auto &Y = A.makeTopValue();
  33   EXPECT_FALSE(Context.equivalentFormulas(X.formula(), Y.formula()));
  34 }
  35
  36 TEST_F(DataflowAnalysisContextTest, EmptyFlowCondition) {
  37   Atom FC = A.makeFlowConditionToken();
  38   auto &C = A.makeAtomRef(A.makeAtom());
  39   EXPECT_FALSE(Context.flowConditionImplies(FC, C));
  40 }
  41
  42 TEST_F(DataflowAnalysisContextTest, AddFlowConditionConstraint) {
  43   Atom FC = A.makeFlowConditionToken();
  44   auto &C = A.makeAtomRef(A.makeAtom());
  45   Context.addFlowConditionConstraint(FC, C);
  46   EXPECT_TRUE(Context.flowConditionImplies(FC, C));
  47 }
  48
  49 TEST_F(DataflowAnalysisContextTest, AddInvariant) {
  50   Atom FC = A.makeFlowConditionToken();
  51   auto &C = A.makeAtomRef(A.makeAtom());
  52   Context.addInvariant(C);
  53   EXPECT_TRUE(Context.flowConditionImplies(FC, C));
  54 }
  55
  56 TEST_F(DataflowAnalysisContextTest, InvariantAndFCConstraintInteract) {
  57   Atom FC = A.makeFlowConditionToken();
  58   auto &C = A.makeAtomRef(A.makeAtom());
  59   auto &D = A.makeAtomRef(A.makeAtom());
  60   Context.addInvariant(A.makeImplies(C, D));
  61   Context.addFlowConditionConstraint(FC, C);
  62   EXPECT_TRUE(Context.flowConditionImplies(FC, D));
  63 }
  64
  65 TEST_F(DataflowAnalysisContextTest, ForkFlowCondition) {
  66   Atom FC1 = A.makeFlowConditionToken();
  67   auto &C1 = A.makeAtomRef(A.makeAtom());
  68   Context.addFlowConditionConstraint(FC1, C1);
  69
  70   // Forked flow condition inherits the constraints of its parent flow
  71   // condition.
  72   Atom FC2 = Context.forkFlowCondition(FC1);
  73   EXPECT_TRUE(Context.flowConditionImplies(FC2, C1));
  74
  75   // Adding a new constraint to the forked flow condition does not affect its
  76   // parent flow condition.
  77   auto &C2 = A.makeAtomRef(A.makeAtom());
  78   Context.addFlowConditionConstraint(FC2, C2);
  79   EXPECT_TRUE(Context.flowConditionImplies(FC2, C2));
  80   EXPECT_FALSE(Context.flowConditionImplies(FC1, C2));
  81 }
  82
  83 TEST_F(DataflowAnalysisContextTest, JoinFlowConditions) {
  84   auto &C1 = A.makeAtomRef(A.makeAtom());
  85   auto &C2 = A.makeAtomRef(A.makeAtom());
  86   auto &C3 = A.makeAtomRef(A.makeAtom());
  87
  88   Atom FC1 = A.makeFlowConditionToken();
  89   Context.addFlowConditionConstraint(FC1, C1);
  90   Context.addFlowConditionConstraint(FC1, C3);
  91
  92   Atom FC2 = A.makeFlowConditionToken();
  93   Context.addFlowConditionConstraint(FC2, C2);
  94   Context.addFlowConditionConstraint(FC2, C3);
  95
  96   Atom FC3 = Context.joinFlowConditions(FC1, FC2);
  97   EXPECT_FALSE(Context.flowConditionImplies(FC3, C1));
  98   EXPECT_FALSE(Context.flowConditionImplies(FC3, C2));
  99   EXPECT_TRUE(Context.flowConditionImplies(FC3, C3));
 100 }
 101
 102 TEST_F(DataflowAnalysisContextTest, EquivBoolVals) {
 103   auto &X = A.makeAtomRef(A.makeAtom());
 104   auto &Y = A.makeAtomRef(A.makeAtom());
 105   auto &Z = A.makeAtomRef(A.makeAtom());
 106   auto &True = A.makeLiteral(true);
 107   auto &False = A.makeLiteral(false);
 108
 109   // X == X
 110   EXPECT_TRUE(Context.equivalentFormulas(X, X));
 111   // X != Y
 112   EXPECT_FALSE(Context.equivalentFormulas(X, Y));
 113
 114   // !X != X
 115   EXPECT_FALSE(Context.equivalentFormulas(A.makeNot(X), X));
 116   // !(!X) = X
 117   EXPECT_TRUE(Context.equivalentFormulas(A.makeNot(A.makeNot(X)), X));
 118
 119   // (X || X) == X
 120   EXPECT_TRUE(Context.equivalentFormulas(A.makeOr(X, X), X));
 121   // (X || Y) != X
 122   EXPECT_FALSE(Context.equivalentFormulas(A.makeOr(X, Y), X));
 123   // (X || True) == True
 124   EXPECT_TRUE(Context.equivalentFormulas(A.makeOr(X, True), True));
 125   // (X || False) == X
 126   EXPECT_TRUE(Context.equivalentFormulas(A.makeOr(X, False), X));
 127
 128   // (X && X) == X
 129   EXPECT_TRUE(Context.equivalentFormulas(A.makeAnd(X, X), X));
 130   // (X && Y) != X
 131   EXPECT_FALSE(Context.equivalentFormulas(A.makeAnd(X, Y), X));
 132   // (X && True) == X
 133   EXPECT_TRUE(Context.equivalentFormulas(A.makeAnd(X, True), X));
 134   // (X && False) == False
 135   EXPECT_TRUE(Context.equivalentFormulas(A.makeAnd(X, False), False));
 136
 137   // (X || Y) == (Y || X)
 138   EXPECT_TRUE(Context.equivalentFormulas(A.makeOr(X, Y), A.makeOr(Y, X)));
 139   // (X && Y) == (Y && X)
 140   EXPECT_TRUE(Context.equivalentFormulas(A.makeAnd(X, Y), A.makeAnd(Y, X)));
 141
 142   // ((X || Y) || Z) == (X || (Y || Z))
 143   EXPECT_TRUE(Context.equivalentFormulas(A.makeOr(A.makeOr(X, Y), Z),
 144                                          A.makeOr(X, A.makeOr(Y, Z))));
 145   // ((X && Y) && Z) == (X && (Y && Z))
 146   EXPECT_TRUE(Context.equivalentFormulas(A.makeAnd(A.makeAnd(X, Y), Z),
 147                                          A.makeAnd(X, A.makeAnd(Y, Z))));
 148 }
 149
 150 } // namespace