clang/unittests/Analysis/FlowSensitive/DeterminismTest.cpp

   1 //===- unittests/Analysis/FlowSensitive/DeterminismTest.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 "TestingSupport.h"
  10 #include "clang/AST/Decl.h"
  11 #include "clang/Analysis/FlowSensitive/ControlFlowContext.h"
  12 #include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
  13 #include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
  14 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
  15 #include "clang/Analysis/FlowSensitive/Formula.h"
  16 #include "clang/Analysis/FlowSensitive/NoopAnalysis.h"
  17 #include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
  18 #include "clang/Analysis/FlowSensitive/WatchedLiteralsSolver.h"
  19 #include "clang/Basic/LLVM.h"
  20 #include "clang/Testing/TestAST.h"
  21 #include "llvm/Support/Error.h"
  22 #include "llvm/Support/raw_ostream.h"
  23 #include "gtest/gtest.h"
  24 #include <memory>
  25 #include <string>
  26
  27 namespace clang::dataflow {
  28
  29 // Run a no-op analysis, and return a textual representation of the
  30 // flow-condition at function exit.
  31 std::string analyzeAndPrintExitCondition(llvm::StringRef Code) {
  32   DataflowAnalysisContext DACtx(std::make_unique<WatchedLiteralsSolver>());
  33   clang::TestAST AST(Code);
  34   const auto *Target =
  35       cast<FunctionDecl>(test::findValueDecl(AST.context(), "target"));
  36   Environment InitEnv(DACtx, *Target);
  37   auto CFCtx = cantFail(ControlFlowContext::build(*Target));
  38
  39   NoopAnalysis Analysis(AST.context(), DataflowAnalysisOptions{});
  40
  41   auto Result = runDataflowAnalysis(CFCtx, Analysis, InitEnv);
  42   EXPECT_FALSE(!Result) << Result.takeError();
  43
  44   Atom FinalFC = (*Result)[CFCtx.getCFG().getExit().getBlockID()]
  45                      ->Env.getFlowConditionToken();
  46   std::string Textual;
  47   llvm::raw_string_ostream OS(Textual);
  48   DACtx.dumpFlowCondition(FinalFC, OS);
  49   return Textual;
  50 }
  51
  52 TEST(DeterminismTest, NestedSwitch) {
  53   // Example extracted from real-world code that had wildly nondeterministic
  54   // analysis times.
  55   // Its flow condition depends on the order we join predecessor blocks.
  56   const char *Code = R"cpp(
  57     struct Tree;
  58     struct Rep {
  59       Tree *tree();
  60       int length;
  61     };
  62     struct Tree {
  63       int height();
  64       Rep *edge(int);
  65       int length;
  66     };
  67     struct RetVal {};
  68     int getInt();
  69     bool maybe();
  70
  71     RetVal make(int size);
  72     inline RetVal target(int size, Tree& self) {
  73       Tree* tree = &self;
  74       const int height = self.height();
  75       Tree* n1 = tree;
  76       Tree* n2 = tree;
  77       switch (height) {
  78         case 3:
  79           tree = tree->edge(0)->tree();
  80           if (maybe()) return {};
  81           n2 = tree;
  82         case 2:
  83           tree = tree->edge(0)->tree();
  84           n1 = tree;
  85           if (maybe()) return {};
  86         case 1:
  87           tree = tree->edge(0)->tree();
  88           if (maybe()) return {};
  89         case 0:
  90           Rep* edge = tree->edge(0);
  91           if (maybe()) return {};
  92           int avail = getInt();
  93           if (avail == 0) return {};
  94           int delta = getInt();
  95           RetVal span = {};
  96           edge->length += delta;
  97           switch (height) {
  98             case 3:
  99               n1->length += delta;
 100             case 2:
 101               n1->length += delta;
 102             case 1:
 103               n1->length += delta;
 104             case 0:
 105               n1->length += delta;
 106               return span;
 107           }
 108           break;
 109       }
 110       return make(size);
 111     }
 112   )cpp";
 113
 114   std::string Cond = analyzeAndPrintExitCondition(Code);
 115   for (unsigned I = 0; I < 10; ++I)
 116     EXPECT_EQ(Cond, analyzeAndPrintExitCondition(Code));
 117 }
 118
 119 TEST(DeterminismTest, ValueMergeOrder) {
 120   // Artificial example whose final flow condition variable numbering depends
 121   // on the order in which we merge a, b, and c.
 122   const char *Code = R"cpp(
 123     bool target(bool a, bool b, bool c) {
 124       if (a)
 125         b = c;
 126       else
 127         c = b;
 128       return a && b && c;
 129     }
 130   )cpp";
 131
 132   std::string Cond = analyzeAndPrintExitCondition(Code);
 133   for (unsigned I = 0; I < 10; ++I)
 134     EXPECT_EQ(Cond, analyzeAndPrintExitCondition(Code));
 135 }
 136
 137 } // namespace clang::dataflow