DAGDeltaAlgorithmTest.cpp revision c437bd577f2ba29934b22816731ac996790d0d39
1bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant//===- llvm/unittest/ADT/DAGDeltaAlgorithmTest.cpp ------------------------===// 2bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// 3f5256e16dfc425c1d466f6308d4026d529ce9e0bHoward Hinnant// The LLVM Compiler Infrastructure 4bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// 5b64f8b07c104c6cc986570ac8ee0ed16a9f23976Howard Hinnant// This file is distributed under the University of Illinois Open Source 6b64f8b07c104c6cc986570ac8ee0ed16a9f23976Howard Hinnant// License. See LICENSE.TXT for details. 7bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant// 8bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant//===----------------------------------------------------------------------===// 9bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 10bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant#include "gtest/gtest.h" 11bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant#include "llvm/ADT/DAGDeltaAlgorithm.h" 12bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant#include <algorithm> 13bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant#include <cstdarg> 14bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnantusing namespace llvm; 15bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 16bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnantnamespace { 17bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 18bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnanttypedef DAGDeltaAlgorithm::edge_ty edge_ty; 19bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 20bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnantclass FixedDAGDeltaAlgorithm : public DAGDeltaAlgorithm { 21bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant changeset_ty FailingSet; 22bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned NumTests; 23bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 24bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnantprotected: 25bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant virtual bool ExecuteOneTest(const changeset_ty &Changes) { 26bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant ++NumTests; 27bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant return std::includes(Changes.begin(), Changes.end(), 28bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant FailingSet.begin(), FailingSet.end()); 29bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant } 30bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 31bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnantpublic: 32bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant FixedDAGDeltaAlgorithm(const changeset_ty &_FailingSet) 33bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant : FailingSet(_FailingSet), 34bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant NumTests(0) {} 35bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 36bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant unsigned getNumTests() const { return NumTests; } 37bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant}; 38bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 39bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnantstd::set<unsigned> fixed_set(unsigned N, ...) { 40bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant std::set<unsigned> S; 41bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant va_list ap; 42bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant va_start(ap, N); 43bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant for (unsigned i = 0; i != N; ++i) 44bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant S.insert(va_arg(ap, unsigned)); 45bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant va_end(ap); 46bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant return S; 47bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant} 48bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 49bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnantstd::set<unsigned> range(unsigned Start, unsigned End) { 50bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant std::set<unsigned> S; 51bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant while (Start != End) 52bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant S.insert(Start++); 53bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant return S; 54bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant} 55bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 56bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnantstd::set<unsigned> range(unsigned N) { 57bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant return range(0, N); 58bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant} 59bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 60bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard HinnantTEST(DAGDeltaAlgorithmTest, Basic) { 61bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant std::vector<edge_ty> Deps; 62bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 63bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant // Dependencies: 64bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant // 1 - 3 65bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant Deps.clear(); 66bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant Deps.push_back(std::make_pair(3, 1)); 67bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 68bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant // P = {3,5,7} \in S, 69bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant // [0, 20), 70bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant // should minimize to {1,3,5,7} in a reasonable number of tests. 71bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant FixedDAGDeltaAlgorithm FDA(fixed_set(3, 3, 5, 7)); 72bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant EXPECT_EQ(fixed_set(4, 1, 3, 5, 7), FDA.Run(range(20), Deps)); 73bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant EXPECT_GE(46U, FDA.getNumTests()); 74bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 75bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant // Dependencies: 76bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant // 0 - 1 77bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant // \- 2 - 3 78bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant // \- 4 79bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant Deps.clear(); 80bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant Deps.push_back(std::make_pair(1, 0)); 81bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant Deps.push_back(std::make_pair(2, 0)); 82bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant Deps.push_back(std::make_pair(4, 0)); 83bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant Deps.push_back(std::make_pair(3, 2)); 84bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 85bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant // This is a case where we must hold required changes. 86bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant // 87bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant // P = {1,3} \in S, 88bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant // [0, 5), 89bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant // should minimize to {0,1,2,3} in a small number of tests. 90bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant FixedDAGDeltaAlgorithm FDA2(fixed_set(2, 1, 3)); 91bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant EXPECT_EQ(fixed_set(4, 0, 1, 2, 3), FDA2.Run(range(5), Deps)); 92bc8d3f97eb5c958007f2713238472e0c1c8fe02Howard Hinnant 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