133965Sjdp//===--- DeltaAlgorithm.cpp - A Set Minimization Algorithm -----*- C++ -*--===// 260484Sobrien// 333965Sjdp// The LLVM Compiler Infrastructure 433965Sjdp// 533965Sjdp// This file is distributed under the University of Illinois Open Source 633965Sjdp// License. See LICENSE.TXT for details. 733965Sjdp//===----------------------------------------------------------------------===// 833965Sjdp 933965Sjdp#include "llvm/ADT/DeltaAlgorithm.h" 1033965Sjdp#include <algorithm> 1133965Sjdp#include <iterator> 1233965Sjdpusing namespace llvm; 1333965Sjdp 1433965SjdpDeltaAlgorithm::~DeltaAlgorithm() { 1533965Sjdp} 1633965Sjdp 1733965Sjdpbool DeltaAlgorithm::GetTestResult(const changeset_ty &Changes) { 1833965Sjdp if (FailedTestsCache.count(Changes)) 1933965Sjdp return false; 2033965Sjdp 2133965Sjdp bool Result = ExecuteOneTest(Changes); 2233965Sjdp if (!Result) 2333965Sjdp FailedTestsCache.insert(Changes); 2433965Sjdp 2533965Sjdp return Result; 2633965Sjdp} 2733965Sjdp 2833965Sjdpvoid DeltaAlgorithm::Split(const changeset_ty &S, changesetlist_ty &Res) { 2933965Sjdp // FIXME: Allow clients to provide heuristics for improved splitting. 3033965Sjdp 3133965Sjdp // FIXME: This is really slow. 3233965Sjdp changeset_ty LHS, RHS; 3333965Sjdp unsigned idx = 0, N = S.size() / 2; 3433965Sjdp for (changeset_ty::const_iterator it = S.begin(), 3533965Sjdp ie = S.end(); it != ie; ++it, ++idx) 3633965Sjdp ((idx < N) ? LHS : RHS).insert(*it); 3733965Sjdp if (!LHS.empty()) 3833965Sjdp Res.push_back(LHS); 3933965Sjdp if (!RHS.empty()) 4033965Sjdp Res.push_back(RHS); 4133965Sjdp} 4233965Sjdp 4333965SjdpDeltaAlgorithm::changeset_ty 4433965SjdpDeltaAlgorithm::Delta(const changeset_ty &Changes, 4533965Sjdp const changesetlist_ty &Sets) { 4677298Sobrien // Invariant: union(Res) == Changes 4733965Sjdp UpdatedSearchState(Changes, Sets); 4833965Sjdp 4933965Sjdp // If there is nothing left we can remove, we are done. 5033965Sjdp if (Sets.size() <= 1) 5133965Sjdp return Changes; 5233965Sjdp 5333965Sjdp // Look for a passing subset. 5433965Sjdp changeset_ty Res; 5533965Sjdp if (Search(Changes, Sets, Res)) 5633965Sjdp return Res; 5733965Sjdp 5833965Sjdp // Otherwise, partition the sets if possible; if not we are done. 5933965Sjdp changesetlist_ty SplitSets; 6060484Sobrien for (changesetlist_ty::const_iterator it = Sets.begin(), 6133965Sjdp ie = Sets.end(); it != ie; ++it) 6233965Sjdp Split(*it, SplitSets); 6333965Sjdp if (SplitSets.size() == Sets.size()) 6433965Sjdp return Changes; 6533965Sjdp 6633965Sjdp return Delta(Changes, SplitSets); 6733965Sjdp} 6833965Sjdp 6933965Sjdpbool DeltaAlgorithm::Search(const changeset_ty &Changes, 7033965Sjdp const changesetlist_ty &Sets, 7133965Sjdp changeset_ty &Res) { 7233965Sjdp // FIXME: Parallelize. 7333965Sjdp for (changesetlist_ty::const_iterator it = Sets.begin(), 7433965Sjdp ie = Sets.end(); it != ie; ++it) { 7533965Sjdp // If the test passes on this subset alone, recurse. 7633965Sjdp if (GetTestResult(*it)) { 7733965Sjdp changesetlist_ty Sets; 7833965Sjdp Split(*it, Sets); 7933965Sjdp Res = Delta(*it, Sets); 8033965Sjdp return true; 8133965Sjdp } 8233965Sjdp 8333965Sjdp // Otherwise, if we have more than two sets, see if test passes on the 8433965Sjdp // complement. 8533965Sjdp if (Sets.size() > 2) { 8633965Sjdp // FIXME: This is really slow. 8777298Sobrien changeset_ty Complement; 8877298Sobrien std::set_difference( 8933965Sjdp Changes.begin(), Changes.end(), it->begin(), it->end(), 9033965Sjdp std::insert_iterator<changeset_ty>(Complement, Complement.begin())); 9133965Sjdp if (GetTestResult(Complement)) { 9233965Sjdp changesetlist_ty ComplementSets; 9333965Sjdp ComplementSets.insert(ComplementSets.end(), Sets.begin(), it); 9433965Sjdp ComplementSets.insert(ComplementSets.end(), it + 1, Sets.end()); 9533965Sjdp Res = Delta(Complement, ComplementSets); 9633965Sjdp return true; 9733965Sjdp } 9833965Sjdp } 9933965Sjdp } 10033965Sjdp 10133965Sjdp return false; 10238889Sjdp} 10377298Sobrien 10477298SobrienDeltaAlgorithm::changeset_ty DeltaAlgorithm::Run(const changeset_ty &Changes) { 10577298Sobrien // Check empty set first to quickly find poor test functions. 10660484Sobrien if (GetTestResult(changeset_ty())) 10760484Sobrien return changeset_ty(); 10860484Sobrien 10938889Sjdp // Otherwise run the real delta algorithm. 11038889Sjdp changesetlist_ty Sets; 11138889Sjdp Split(Changes, Sets); 11238889Sjdp 11333965Sjdp return Delta(Changes, Sets); 11433965Sjdp} 11533965Sjdp