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