DeltaAlgorithm.cpp revision 314564
1150957Simp//===--- DeltaAlgorithm.cpp - A Set Minimization Algorithm -----*- C++ -*--===//
2150957Simp//
3150957Simp//                     The LLVM Compiler Infrastructure
4150957Simp//
5150957Simp// This file is distributed under the University of Illinois Open Source
6150957Simp// License. See LICENSE.TXT for details.
7150957Simp//===----------------------------------------------------------------------===//
8150957Simp
9150957Simp#include "llvm/ADT/DeltaAlgorithm.h"
10150957Simp#include <algorithm>
11150957Simp#include <iterator>
12150957Simp#include <set>
13150957Simpusing namespace llvm;
14150957Simp
15150957SimpDeltaAlgorithm::~DeltaAlgorithm() {
16150957Simp}
17150957Simp
18150957Simpbool DeltaAlgorithm::GetTestResult(const changeset_ty &Changes) {
19150957Simp  if (FailedTestsCache.count(Changes))
20150957Simp    return false;
21150957Simp
22150957Simp  bool Result = ExecuteOneTest(Changes);
23150957Simp  if (!Result)
24150957Simp    FailedTestsCache.insert(Changes);
25150957Simp
26150957Simp  return Result;
27150957Simp}
28150957Simp
29150957Simpvoid DeltaAlgorithm::Split(const changeset_ty &S, changesetlist_ty &Res) {
30150957Simp  // FIXME: Allow clients to provide heuristics for improved splitting.
31150957Simp
32150957Simp  // FIXME: This is really slow.
33150957Simp  changeset_ty LHS, RHS;
34150957Simp  unsigned idx = 0, N = S.size() / 2;
35150957Simp  for (changeset_ty::const_iterator it = S.begin(),
36150957Simp         ie = S.end(); it != ie; ++it, ++idx)
37150957Simp    ((idx < N) ? LHS : RHS).insert(*it);
38150957Simp  if (!LHS.empty())
39150957Simp    Res.push_back(LHS);
40150957Simp  if (!RHS.empty())
41150957Simp    Res.push_back(RHS);
42150957Simp}
43150957Simp
44150957SimpDeltaAlgorithm::changeset_ty
45150957SimpDeltaAlgorithm::Delta(const changeset_ty &Changes,
46150957Simp                      const changesetlist_ty &Sets) {
47150957Simp  // Invariant: union(Res) == Changes
48150957Simp  UpdatedSearchState(Changes, Sets);
49150957Simp
50150957Simp  // If there is nothing left we can remove, we are done.
51150957Simp  if (Sets.size() <= 1)
52150957Simp    return Changes;
53150957Simp
54150957Simp  // Look for a passing subset.
55150957Simp  changeset_ty Res;
56150957Simp  if (Search(Changes, Sets, Res))
57150957Simp    return Res;
58150957Simp
59150957Simp  // Otherwise, partition the sets if possible; if not we are done.
60150957Simp  changesetlist_ty SplitSets;
61150957Simp  for (changesetlist_ty::const_iterator it = Sets.begin(),
62150957Simp         ie = Sets.end(); it != ie; ++it)
63150957Simp    Split(*it, SplitSets);
64150957Simp  if (SplitSets.size() == Sets.size())
65150957Simp    return Changes;
66150957Simp
67150957Simp  return Delta(Changes, SplitSets);
68150957Simp}
69150957Simp
70150957Simpbool DeltaAlgorithm::Search(const changeset_ty &Changes,
71150957Simp                            const changesetlist_ty &Sets,
72150957Simp                            changeset_ty &Res) {
73150957Simp  // FIXME: Parallelize.
74150957Simp  for (changesetlist_ty::const_iterator it = Sets.begin(),
75150957Simp         ie = Sets.end(); it != ie; ++it) {
76150957Simp    // If the test passes on this subset alone, recurse.
77150957Simp    if (GetTestResult(*it)) {
78151299Simp      changesetlist_ty Sets;
79150957Simp      Split(*it, Sets);
80150957Simp      Res = Delta(*it, Sets);
81150957Simp      return true;
82150957Simp    }
83151547Simp
84151547Simp    // Otherwise, if we have more than two sets, see if test passes on the
85151547Simp    // complement.
86150957Simp    if (Sets.size() > 2) {
87150957Simp      // FIXME: This is really slow.
88150957Simp      changeset_ty Complement;
89150957Simp      std::set_difference(
90150957Simp        Changes.begin(), Changes.end(), it->begin(), it->end(),
91150957Simp        std::insert_iterator<changeset_ty>(Complement, Complement.begin()));
92150957Simp      if (GetTestResult(Complement)) {
93150957Simp        changesetlist_ty ComplementSets;
94150957Simp        ComplementSets.insert(ComplementSets.end(), Sets.begin(), it);
95150957Simp        ComplementSets.insert(ComplementSets.end(), it + 1, Sets.end());
96151299Simp        Res = Delta(Complement, ComplementSets);
97150957Simp        return true;
98150957Simp      }
99150957Simp    }
100151299Simp  }
101150957Simp
102150957Simp  return false;
103150957Simp}
104150957Simp
105150957SimpDeltaAlgorithm::changeset_ty DeltaAlgorithm::Run(const changeset_ty &Changes) {
106150957Simp  // Check empty set first to quickly find poor test functions.
107150957Simp  if (GetTestResult(changeset_ty()))
108150957Simp    return changeset_ty();
109151299Simp
110150957Simp  // Otherwise run the real delta algorithm.
111150957Simp  changesetlist_ty Sets;
112150957Simp  Split(Changes, Sets);
113150957Simp
114150957Simp  return Delta(Changes, Sets);
115150957Simp}
116150957Simp