unittests/Analysis/LoopPassManagerTest.cpp

   1 //===- llvm/unittest/Analysis/LoopPassManagerTest.cpp - LPM tests ---------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/Analysis/AliasAnalysis.h"
  11 #include "llvm/Analysis/AssumptionCache.h"
  12 #include "llvm/Analysis/LoopPassManager.h"
  13 #include "llvm/Analysis/ScalarEvolution.h"
  14 #include "llvm/Analysis/TargetLibraryInfo.h"
  15 #include "llvm/AsmParser/Parser.h"
  16 #include "llvm/IR/Dominators.h"
  17 #include "llvm/IR/Function.h"
  18 #include "llvm/IR/LLVMContext.h"
  19 #include "llvm/IR/Module.h"
  20 #include "llvm/IR/PassManager.h"
  21 #include "llvm/Support/SourceMgr.h"
  22 #include "gtest/gtest.h"
  23
  24 using namespace llvm;
  25
  26 namespace {
  27
  28 class TestLoopAnalysis : public AnalysisInfoMixin<TestLoopAnalysis> {
  29   friend AnalysisInfoMixin<TestLoopAnalysis>;
  30   static AnalysisKey Key;
  31
  32   int &Runs;
  33
  34 public:
  35   struct Result {
  36     Result(int Count) : BlockCount(Count) {}
  37     int BlockCount;
  38   };
  39
  40   TestLoopAnalysis(int &Runs) : Runs(Runs) {}
  41
  42   /// \brief Run the analysis pass over the loop and return a result.
  43   Result run(Loop &L, LoopAnalysisManager &AM) {
  44     ++Runs;
  45     int Count = 0;
  46
  47     for (auto I = L.block_begin(), E = L.block_end(); I != E; ++I)
  48       ++Count;
  49     return Result(Count);
  50   }
  51 };
  52
  53 AnalysisKey TestLoopAnalysis::Key;
  54
  55 class TestLoopPass {
  56   std::vector<StringRef> &VisitedLoops;
  57   int &AnalyzedBlockCount;
  58   bool OnlyUseCachedResults;
  59
  60 public:
  61   TestLoopPass(std::vector<StringRef> &VisitedLoops, int &AnalyzedBlockCount,
  62                bool OnlyUseCachedResults = false)
  63       : VisitedLoops(VisitedLoops), AnalyzedBlockCount(AnalyzedBlockCount),
  64         OnlyUseCachedResults(OnlyUseCachedResults) {}
  65
  66   PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM) {
  67     VisitedLoops.push_back(L.getName());
  68
  69     if (OnlyUseCachedResults) {
  70       // Hack to force the use of the cached interface.
  71       if (auto *AR = AM.getCachedResult<TestLoopAnalysis>(L))
  72         AnalyzedBlockCount += AR->BlockCount;
  73     } else {
  74       // Typical path just runs the analysis as needed.
  75       auto &AR = AM.getResult<TestLoopAnalysis>(L);
  76       AnalyzedBlockCount += AR.BlockCount;
  77     }
  78
  79     return PreservedAnalyses::all();
  80   }
  81
  82   static StringRef name() { return "TestLoopPass"; }
  83 };
  84
  85 // A test loop pass that invalidates the analysis for loops with the given name.
  86 class TestLoopInvalidatingPass {
  87   StringRef Name;
  88
  89 public:
  90   TestLoopInvalidatingPass(StringRef LoopName) : Name(LoopName) {}
  91
  92   PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM) {
  93     return L.getName() == Name ? getLoopPassPreservedAnalyses()
  94                                : PreservedAnalyses::all();
  95   }
  96
  97   static StringRef name() { return "TestLoopInvalidatingPass"; }
  98 };
  99
 100 std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {
 101   SMDiagnostic Err;
 102   return parseAssemblyString(IR, Err, C);
 103 }
 104
 105 class LoopPassManagerTest : public ::testing::Test {
 106 protected:
 107   LLVMContext Context;
 108   std::unique_ptr<Module> M;
 109
 110 public:
 111   LoopPassManagerTest()
 112       : M(parseIR(Context, "define void @f() {\n"
 113                            "entry:\n"
 114                            "  br label %loop.0\n"
 115                            "loop.0:\n"
 116                            "  br i1 undef, label %loop.0.0, label %end\n"
 117                            "loop.0.0:\n"
 118                            "  br i1 undef, label %loop.0.0, label %loop.0.1\n"
 119                            "loop.0.1:\n"
 120                            "  br i1 undef, label %loop.0.1, label %loop.0\n"
 121                            "end:\n"
 122                            "  ret void\n"
 123                            "}\n"
 124                            "\n"
 125                            "define void @g() {\n"
 126                            "entry:\n"
 127                            "  br label %loop.g.0\n"
 128                            "loop.g.0:\n"
 129                            "  br i1 undef, label %loop.g.0, label %end\n"
 130                            "end:\n"
 131                            "  ret void\n"
 132                            "}\n")) {}
 133 };
 134
 135 #define EXPECT_N_ELEMENTS_EQ(N, EXPECTED, ACTUAL)                              \
 136   do {                                                                         \
 137     EXPECT_EQ(N##UL, ACTUAL.size());                                           \
 138     for (int I = 0; I < N; ++I)                                                \
 139       EXPECT_TRUE(EXPECTED[I] == ACTUAL[I]) << "Element " << I << " is "       \
 140                                             << ACTUAL[I] << ". Expected "      \
 141                                             << EXPECTED[I] << ".";             \
 142   } while (0)
 143
 144 TEST_F(LoopPassManagerTest, Basic) {
 145   LoopAnalysisManager LAM(true);
 146   int LoopAnalysisRuns = 0;
 147   LAM.registerPass([&] { return TestLoopAnalysis(LoopAnalysisRuns); });
 148
 149   FunctionAnalysisManager FAM(true);
 150   // We need DominatorTreeAnalysis for LoopAnalysis.
 151   FAM.registerPass([&] { return DominatorTreeAnalysis(); });
 152   FAM.registerPass([&] { return LoopAnalysis(); });
 153   // We also allow loop passes to assume a set of other analyses and so need
 154   // those.
 155   FAM.registerPass([&] { return AAManager(); });
 156   FAM.registerPass([&] { return TargetLibraryAnalysis(); });
 157   FAM.registerPass([&] { return ScalarEvolutionAnalysis(); });
 158   FAM.registerPass([&] { return AssumptionAnalysis(); });
 159   FAM.registerPass([&] { return LoopAnalysisManagerFunctionProxy(LAM); });
 160   LAM.registerPass([&] { return FunctionAnalysisManagerLoopProxy(FAM); });
 161
 162   ModuleAnalysisManager MAM(true);
 163   MAM.registerPass([&] { return FunctionAnalysisManagerModuleProxy(FAM); });
 164   FAM.registerPass([&] { return ModuleAnalysisManagerFunctionProxy(MAM); });
 165
 166   ModulePassManager MPM(true);
 167   FunctionPassManager FPM(true);
 168
 169   // Visit all of the loops.
 170   std::vector<StringRef> VisitedLoops1;
 171   int AnalyzedBlockCount1 = 0;
 172   {
 173     LoopPassManager LPM;
 174     LPM.addPass(TestLoopPass(VisitedLoops1, AnalyzedBlockCount1));
 175
 176     FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM)));
 177   }
 178
 179   // Only use cached analyses.
 180   std::vector<StringRef> VisitedLoops2;
 181   int AnalyzedBlockCount2 = 0;
 182   {
 183     LoopPassManager LPM;
 184     LPM.addPass(TestLoopInvalidatingPass("loop.g.0"));
 185     LPM.addPass(TestLoopPass(VisitedLoops2, AnalyzedBlockCount2,
 186                              /*OnlyUseCachedResults=*/true));
 187
 188     FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM)));
 189   }
 190
 191   MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
 192   MPM.run(*M, MAM);
 193
 194   StringRef ExpectedLoops[] = {"loop.0.0", "loop.0.1", "loop.0", "loop.g.0"};
 195
 196   // Validate the counters and order of loops visited.
 197   // loop.0 has 3 blocks whereas loop.0.0, loop.0.1, and loop.g.0 each have 1.
 198   EXPECT_N_ELEMENTS_EQ(4, ExpectedLoops, VisitedLoops1);
 199   EXPECT_EQ(6, AnalyzedBlockCount1);
 200
 201   EXPECT_N_ELEMENTS_EQ(4, ExpectedLoops, VisitedLoops2);
 202   // The block from loop.g.0 won't be counted, since it wasn't cached.
 203   EXPECT_EQ(5, AnalyzedBlockCount2);
 204
 205   // The first LPM runs the loop analysis for all four loops, the second uses
 206   // cached results for everything.
 207   EXPECT_EQ(4, LoopAnalysisRuns);
 208 }
 209 }