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/AdornedCFG.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   TestInputs Inputs(Code);
  34   Inputs.Language = TestLanguage::Lang_CXX17;
  35   clang::TestAST AST(Inputs);
  36   const auto *Target =
  37       cast<FunctionDecl>(test::findValueDecl(AST.context(), "target"));
  38   Environment InitEnv(DACtx, *Target);
  39   auto ACFG = cantFail(AdornedCFG::build(*Target));
  40
  41   NoopAnalysis Analysis(AST.context(), DataflowAnalysisOptions{});
  42
  43   auto Result = runDataflowAnalysis(ACFG, Analysis, InitEnv);
  44   EXPECT_FALSE(!Result) << Result.takeError();
  45
  46   Atom FinalFC = (*Result)[ACFG.getCFG().getExit().getBlockID()]
  47                      ->Env.getFlowConditionToken();
  48   std::string Textual;
  49   llvm::raw_string_ostream OS(Textual);
  50   DACtx.dumpFlowCondition(FinalFC, OS);
  51   return Textual;
  52 }
  53
  54 TEST(DeterminismTest, NestedSwitch) {
  55   // Example extracted from real-world code that had wildly nondeterministic
  56   // analysis times.
  57   // Its flow condition depends on the order we join predecessor blocks.
  58   const char *Code = R"cpp(
  59     struct Tree;
  60     struct Rep {
  61       Tree *tree();
  62       int length;
  63     };
  64     struct Tree {
  65       int height();
  66       Rep *edge(int);
  67       int length;
  68     };
  69     struct RetVal {};
  70     int getInt();
  71     bool maybe();
  72
  73     RetVal make(int size);
  74     inline RetVal target(int size, Tree& self) {
  75       Tree* tree = &self;
  76       const int height = self.height();
  77       Tree* n1 = tree;
  78       Tree* n2 = tree;
  79       switch (height) {
  80         case 3:
  81           tree = tree->edge(0)->tree();
  82           if (maybe()) return {};
  83           n2 = tree;
  84         case 2:
  85           tree = tree->edge(0)->tree();
  86           n1 = tree;
  87           if (maybe()) return {};
  88         case 1:
  89           tree = tree->edge(0)->tree();
  90           if (maybe()) return {};
  91         case 0:
  92           Rep* edge = tree->edge(0);
  93           if (maybe()) return {};
  94           int avail = getInt();
  95           if (avail == 0) return {};
  96           int delta = getInt();
  97           RetVal span = {};
  98           edge->length += delta;
  99           switch (height) {
 100             case 3:
 101               n1->length += delta;
 102             case 2:
 103               n1->length += delta;
 104             case 1:
 105               n1->length += delta;
 106             case 0:
 107               n1->length += delta;
 108               return span;
 109           }
 110           break;
 111       }
 112       return make(size);
 113     }
 114   )cpp";
 115
 116   std::string Cond = analyzeAndPrintExitCondition(Code);
 117   for (unsigned I = 0; I < 10; ++I)
 118     EXPECT_EQ(Cond, analyzeAndPrintExitCondition(Code));
 119 }
 120
 121 TEST(DeterminismTest, ValueMergeOrder) {
 122   // Artificial example whose final flow condition variable numbering depends
 123   // on the order in which we merge a, b, and c.
 124   const char *Code = R"cpp(
 125     bool target(bool a, bool b, bool c) {
 126       if (a)
 127         b = c;
 128       else
 129         c = b;
 130       return a && b && c;
 131     }
 132   )cpp";
 133
 134   std::string Cond = analyzeAndPrintExitCondition(Code);
 135   for (unsigned I = 0; I < 10; ++I)
 136     EXPECT_EQ(Cond, analyzeAndPrintExitCondition(Code));
 137 }
 138
 139 } // namespace clang::dataflow