173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar//===- llvm/unittest/ADT/DAGDeltaAlgorithmTest.cpp ------------------------===// 273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// 373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// The LLVM Compiler Infrastructure 473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// 573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// This file is distributed under the University of Illinois Open Source 673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// License. See LICENSE.TXT for details. 773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar// 873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar//===----------------------------------------------------------------------===// 973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 1073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar#include "gtest/gtest.h" 1173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar#include "llvm/ADT/DAGDeltaAlgorithm.h" 1273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar#include <algorithm> 1373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar#include <cstdarg> 1473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbarusing namespace llvm; 1573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 1673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbarnamespace { 1773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 1873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbartypedef DAGDeltaAlgorithm::edge_ty edge_ty; 1973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 2073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbarclass FixedDAGDeltaAlgorithm : public DAGDeltaAlgorithm { 2173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar changeset_ty FailingSet; 2273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar unsigned NumTests; 2373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 2473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbarprotected: 2573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar virtual bool ExecuteOneTest(const changeset_ty &Changes) { 2673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar ++NumTests; 2773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return std::includes(Changes.begin(), Changes.end(), 2873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar FailingSet.begin(), FailingSet.end()); 2973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar } 3073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 3173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbarpublic: 3273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar FixedDAGDeltaAlgorithm(const changeset_ty &_FailingSet) 3373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar : FailingSet(_FailingSet), 3473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar NumTests(0) {} 3573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 3673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar unsigned getNumTests() const { return NumTests; } 3773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar}; 3873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 3973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbarstd::set<unsigned> fixed_set(unsigned N, ...) { 4073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar std::set<unsigned> S; 4173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar va_list ap; 4273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar va_start(ap, N); 4373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar for (unsigned i = 0; i != N; ++i) 4473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar S.insert(va_arg(ap, unsigned)); 4573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar va_end(ap); 4673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return S; 4773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar} 4873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 4973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbarstd::set<unsigned> range(unsigned Start, unsigned End) { 5073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar std::set<unsigned> S; 5173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar while (Start != End) 5273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar S.insert(Start++); 5373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return S; 5473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar} 5573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 5673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbarstd::set<unsigned> range(unsigned N) { 5773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar return range(0, N); 5873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar} 5973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 6073c6031a2546ad18ab0b454fe5d711715620d140Daniel DunbarTEST(DAGDeltaAlgorithmTest, Basic) { 6173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar std::vector<edge_ty> Deps; 6273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 6373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // Dependencies: 6473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // 1 - 3 6573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Deps.clear(); 6673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Deps.push_back(std::make_pair(3, 1)); 6773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 6873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // P = {3,5,7} \in S, 6973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // [0, 20), 7073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // should minimize to {1,3,5,7} in a reasonable number of tests. 7173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar FixedDAGDeltaAlgorithm FDA(fixed_set(3, 3, 5, 7)); 7273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar EXPECT_EQ(fixed_set(4, 1, 3, 5, 7), FDA.Run(range(20), Deps)); 7373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar EXPECT_GE(46U, FDA.getNumTests()); 7473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 7573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // Dependencies: 7673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // 0 - 1 7773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // \- 2 - 3 7873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // \- 4 7973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Deps.clear(); 8073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Deps.push_back(std::make_pair(1, 0)); 8173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Deps.push_back(std::make_pair(2, 0)); 8273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Deps.push_back(std::make_pair(4, 0)); 8373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar Deps.push_back(std::make_pair(3, 2)); 8473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 8573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // This is a case where we must hold required changes. 8673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // 8773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // P = {1,3} \in S, 8873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // [0, 5), 8973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // should minimize to {0,1,2,3} in a small number of tests. 9073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar FixedDAGDeltaAlgorithm FDA2(fixed_set(2, 1, 3)); 9173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar EXPECT_EQ(fixed_set(4, 0, 1, 2, 3), FDA2.Run(range(5), Deps)); 9273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar EXPECT_GE(9U, FDA2.getNumTests()); 9373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 9473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // This is a case where we should quickly prune part of the tree. 9573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // 9673c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // P = {4} \in S, 9773c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // [0, 5), 9873c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar // should minimize to {0,4} in a small number of tests. 9973c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar FixedDAGDeltaAlgorithm FDA3(fixed_set(1, 4)); 10073c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar EXPECT_EQ(fixed_set(2, 0, 4), FDA3.Run(range(5), Deps)); 10173c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar EXPECT_GE(6U, FDA3.getNumTests()); 10273c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar} 10373c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 10473c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar} 10573c6031a2546ad18ab0b454fe5d711715620d140Daniel Dunbar 106