140 lines · 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-exception6//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 27namespace clang::dataflow {28 29// Run a no-op analysis, and return a textual representation of the30// flow-condition at function exit.31std::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 54TEST(DeterminismTest, NestedSwitch) {55 // Example extracted from real-world code that had wildly nondeterministic56 // 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 121TEST(DeterminismTest, ValueMergeOrder) {122 // Artificial example whose final flow condition variable numbering depends123 // 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 else129 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::dataflow140