llvm/unittests/ADT/DAGDeltaAlgorithmTest.cpp

   1 //===- llvm/unittest/ADT/DAGDeltaAlgorithmTest.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 "llvm/ADT/DAGDeltaAlgorithm.h"
  10 #include "gtest/gtest.h"
  11 #include <algorithm>
  12 #include <cstdarg>
  13 using namespace llvm;
  14
  15 namespace {
  16
  17 typedef DAGDeltaAlgorithm::edge_ty edge_ty;
  18
  19 class FixedDAGDeltaAlgorithm : public DAGDeltaAlgorithm {
  20   changeset_ty FailingSet;
  21   unsigned NumTests;
  22
  23 protected:
  24   bool ExecuteOneTest(const changeset_ty &Changes) override {
  25     ++NumTests;
  26     return std::includes(Changes.begin(), Changes.end(),
  27                          FailingSet.begin(), FailingSet.end());
  28   }
  29
  30 public:
  31   FixedDAGDeltaAlgorithm(const changeset_ty &_FailingSet)
  32     : FailingSet(_FailingSet),
  33       NumTests(0) {}
  34
  35   unsigned getNumTests() const { return NumTests; }
  36 };
  37
  38 std::set<unsigned> fixed_set(unsigned N, ...) {
  39   std::set<unsigned> S;
  40   va_list ap;
  41   va_start(ap, N);
  42   for (unsigned i = 0; i != N; ++i)
  43     S.insert(va_arg(ap, unsigned));
  44   va_end(ap);
  45   return S;
  46 }
  47
  48 std::set<unsigned> range(unsigned Start, unsigned End) {
  49   std::set<unsigned> S;
  50   while (Start != End)
  51     S.insert(Start++);
  52   return S;
  53 }
  54
  55 std::set<unsigned> range(unsigned N) {
  56   return range(0, N);
  57 }
  58
  59 TEST(DAGDeltaAlgorithmTest, Basic) {
  60   std::vector<edge_ty> Deps;
  61
  62   // Dependencies:
  63   //  1 - 3
  64   Deps.clear();
  65   Deps.push_back(std::make_pair(3, 1));
  66
  67   // P = {3,5,7} \in S,
  68   //   [0, 20),
  69   // should minimize to {1,3,5,7} in a reasonable number of tests.
  70   FixedDAGDeltaAlgorithm FDA(fixed_set(3, 3, 5, 7));
  71   EXPECT_EQ(fixed_set(4, 1, 3, 5, 7), FDA.Run(range(20), Deps));
  72   EXPECT_GE(46U, FDA.getNumTests());
  73
  74   // Dependencies:
  75   // 0 - 1
  76   //  \- 2 - 3
  77   //  \- 4
  78   Deps.clear();
  79   Deps.push_back(std::make_pair(1, 0));
  80   Deps.push_back(std::make_pair(2, 0));
  81   Deps.push_back(std::make_pair(4, 0));
  82   Deps.push_back(std::make_pair(3, 2));
  83
  84   // This is a case where we must hold required changes.
  85   //
  86   // P = {1,3} \in S,
  87   //   [0, 5),
  88   // should minimize to {0,1,2,3} in a small number of tests.
  89   FixedDAGDeltaAlgorithm FDA2(fixed_set(2, 1, 3));
  90   EXPECT_EQ(fixed_set(4, 0, 1, 2, 3), FDA2.Run(range(5), Deps));
  91   EXPECT_GE(9U, FDA2.getNumTests());
  92
  93   // This is a case where we should quickly prune part of the tree.
  94   //
  95   // P = {4} \in S,
  96   //   [0, 5),
  97   // should minimize to {0,4} in a small number of tests.
  98   FixedDAGDeltaAlgorithm FDA3(fixed_set(1, 4));
  99   EXPECT_EQ(fixed_set(2, 0, 4), FDA3.Run(range(5), Deps));
 100   EXPECT_GE(6U, FDA3.getNumTests());
 101 }
 102
 103 }
 104