← Back to branch summary

~ubuntu-branches/ubuntu/saucy/clamav/saucy

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/lib/Support/DAGDeltaAlgorithm.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Leonel Nunez
  • Date: 2008-02-11 22:52:13 UTC
  • mfrom: (1.1.6 upstream)
  • mto: This revision was merged to the branch mainline in revision 38.
  • Revision ID: james.westby@ubuntu.com-20080211225213-p2uwj4czso1w2f8h
Tags: upstream-0.92~dfsg
Import upstream version 0.92~dfsg

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/lib/Support/DAGDeltaAlgorithm.cpp
1
 
//===--- DAGDeltaAlgorithm.cpp - A DAG Minimization Algorithm --*- C++ -*--===//
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
 
// The algorithm we use attempts to exploit the dependency information by
10
 
// minimizing top-down. We start by constructing an initial root set R, and
11
 
// then iteratively:
12
 
//
13
 
//   1. Minimize the set R using the test predicate:
14
 
//       P'(S) = P(S union pred*(S))
15
 
//
16
 
//   2. Extend R to R' = R union pred(R).
17
 
//
18
 
// until a fixed point is reached.
19
 
//
20
 
// The idea is that we want to quickly prune entire portions of the graph, so we
21
 
// try to find high-level nodes that can be eliminated with all of their
22
 
// dependents.
23
 
//
24
 
// FIXME: The current algorithm doesn't actually provide a strong guarantee
25
 
// about the minimality of the result. The problem is that after adding nodes to
26
 
// the required set, we no longer consider them for elimination. For strictly
27
 
// well formed predicates, this doesn't happen, but it commonly occurs in
28
 
// practice when there are unmodelled dependencies. I believe we can resolve
29
 
// this by allowing the required set to be minimized as well, but need more test
30
 
// cases first.
31
 
//
32
 
//===----------------------------------------------------------------------===//
33
 
 
34
 
#include "llvm/ADT/DAGDeltaAlgorithm.h"
35
 
#include "llvm/ADT/DeltaAlgorithm.h"
36
 
#include "llvm/Support/Debug.h"
37
 
#include "llvm/Support/Format.h"
38
 
#include "llvm/Support/raw_ostream.h"
39
 
#include <algorithm>
40
 
#include <cassert>
41
 
#include <iterator>
42
 
#include <map>
43
 
using namespace llvm;
44
 
 
45
 
namespace {
46
 
 
47
 
class DAGDeltaAlgorithmImpl {
48
 
  friend class DeltaActiveSetHelper;
49
 
 
50
 
public:
51
 
  typedef DAGDeltaAlgorithm::change_ty change_ty;
52
 
  typedef DAGDeltaAlgorithm::changeset_ty changeset_ty;
53
 
  typedef DAGDeltaAlgorithm::changesetlist_ty changesetlist_ty;
54
 
  typedef DAGDeltaAlgorithm::edge_ty edge_ty;
55
 
 
56
 
private:
57
 
  typedef std::vector<change_ty>::iterator pred_iterator_ty;
58
 
  typedef std::vector<change_ty>::iterator succ_iterator_ty;
59
 
  typedef std::set<change_ty>::iterator pred_closure_iterator_ty;
60
 
  typedef std::set<change_ty>::iterator succ_closure_iterator_ty;
61
 
 
62
 
  DAGDeltaAlgorithm &DDA;
63
 
 
64
 
  const changeset_ty &Changes;
65
 
  const std::vector<edge_ty> &Dependencies;
66
 
 
67
 
  std::vector<change_ty> Roots;
68
 
 
69
 
  /// Cache of failed test results. Successful test results are never cached
70
 
  /// since we always reduce following a success. We maintain an independent
71
 
  /// cache from that used by the individual delta passes because we may get
72
 
  /// hits across multiple individual delta invocations.
73
 
  mutable std::set<changeset_ty> FailedTestsCache;
74
 
 
75
 
  // FIXME: Gross.
76
 
  std::map<change_ty, std::vector<change_ty> > Predecessors;
77
 
  std::map<change_ty, std::vector<change_ty> > Successors;
78
 
 
79
 
  std::map<change_ty, std::set<change_ty> > PredClosure;
80
 
  std::map<change_ty, std::set<change_ty> > SuccClosure;
81
 
 
82
 
private:
83
 
  pred_iterator_ty pred_begin(change_ty Node) {
84
 
    assert(Predecessors.count(Node) && "Invalid node!");
85
 
    return Predecessors[Node].begin();
86
 
  }
87
 
  pred_iterator_ty pred_end(change_ty Node) {
88
 
    assert(Predecessors.count(Node) && "Invalid node!");
89
 
    return Predecessors[Node].end();
90
 
  }
91
 
 
92
 
  pred_closure_iterator_ty pred_closure_begin(change_ty Node) {
93
 
    assert(PredClosure.count(Node) && "Invalid node!");
94
 
    return PredClosure[Node].begin();
95
 
  }
96
 
  pred_closure_iterator_ty pred_closure_end(change_ty Node) {
97
 
    assert(PredClosure.count(Node) && "Invalid node!");
98
 
    return PredClosure[Node].end();
99
 
  }
100
 
  
101
 
  succ_iterator_ty succ_begin(change_ty Node) {
102
 
    assert(Successors.count(Node) && "Invalid node!");
103
 
    return Successors[Node].begin();
104
 
  }
105
 
  succ_iterator_ty succ_end(change_ty Node) {
106
 
    assert(Successors.count(Node) && "Invalid node!");
107
 
    return Successors[Node].end();
108
 
  }
109
 
 
110
 
  succ_closure_iterator_ty succ_closure_begin(change_ty Node) {
111
 
    assert(SuccClosure.count(Node) && "Invalid node!");
112
 
    return SuccClosure[Node].begin();
113
 
  }
114
 
  succ_closure_iterator_ty succ_closure_end(change_ty Node) {
115
 
    assert(SuccClosure.count(Node) && "Invalid node!");
116
 
    return SuccClosure[Node].end();
117
 
  }
118
 
 
119
 
  void UpdatedSearchState(const changeset_ty &Changes,
120
 
                          const changesetlist_ty &Sets,
121
 
                          const changeset_ty &Required) {
122
 
    DDA.UpdatedSearchState(Changes, Sets, Required);
123
 
  }
124
 
 
125
 
  /// ExecuteOneTest - Execute a single test predicate on the change set \arg S.
126
 
  bool ExecuteOneTest(const changeset_ty &S) {
127
 
    // Check dependencies invariant.
128
 
    DEBUG({
129
 
        for (changeset_ty::const_iterator it = S.begin(),
130
 
               ie = S.end(); it != ie; ++it)
131
 
          for (succ_iterator_ty it2 = succ_begin(*it),
132
 
                 ie2 = succ_end(*it); it2 != ie2; ++it2)
133
 
            assert(S.count(*it2) && "Attempt to run invalid changeset!");
134
 
      });
135
 
 
136
 
    return DDA.ExecuteOneTest(S);
137
 
  }
138
 
 
139
 
public:
140
 
  DAGDeltaAlgorithmImpl(DAGDeltaAlgorithm &_DDA,
141
 
                        const changeset_ty &_Changes,
142
 
                        const std::vector<edge_ty> &_Dependencies);
143
 
 
144
 
  changeset_ty Run();
145
 
 
146
 
  /// GetTestResult - Get the test result for the active set \arg Changes with
147
 
  /// \arg Required changes from the cache, executing the test if necessary.
148
 
  ///
149
 
  /// \param Changes - The set of active changes being minimized, which should
150
 
  /// have their pred closure included in the test.
151
 
  /// \param Required - The set of changes which have previously been
152
 
  /// established to be required.
153
 
  /// \return - The test result.
154
 
  bool GetTestResult(const changeset_ty &Changes, const changeset_ty &Required);
155
 
};
156
 
 
157
 
/// Helper object for minimizing an active set of changes.
158
 
class DeltaActiveSetHelper : public DeltaAlgorithm {
159
 
  DAGDeltaAlgorithmImpl &DDAI;
160
 
 
161
 
  const changeset_ty &Required;
162
 
 
163
 
protected:
164
 
  /// UpdatedSearchState - Callback used when the search state changes.
165
 
  virtual void UpdatedSearchState(const changeset_ty &Changes,
166
 
                                  const changesetlist_ty &Sets) {
167
 
    DDAI.UpdatedSearchState(Changes, Sets, Required);
168
 
  }
169
 
 
170
 
  virtual bool ExecuteOneTest(const changeset_ty &S) {
171
 
    return DDAI.GetTestResult(S, Required);
172
 
  }
173
 
 
174
 
public:
175
 
  DeltaActiveSetHelper(DAGDeltaAlgorithmImpl &_DDAI,
176
 
                       const changeset_ty &_Required)
177
 
    : DDAI(_DDAI), Required(_Required) {}
178
 
};
179
 
 
180
 
}
181
 
 
182
 
DAGDeltaAlgorithmImpl::DAGDeltaAlgorithmImpl(DAGDeltaAlgorithm &_DDA,
183
 
                                             const changeset_ty &_Changes,
184
 
                                             const std::vector<edge_ty>
185
 
                                               &_Dependencies)
186
 
  : DDA(_DDA),
187
 
    Changes(_Changes),
188
 
    Dependencies(_Dependencies)
189
 
{
190
 
  for (changeset_ty::const_iterator it = Changes.begin(),
191
 
         ie = Changes.end(); it != ie; ++it) {
192
 
    Predecessors.insert(std::make_pair(*it, std::vector<change_ty>()));
193
 
    Successors.insert(std::make_pair(*it, std::vector<change_ty>()));
194
 
  }
195
 
  for (std::vector<edge_ty>::const_iterator it = Dependencies.begin(),
196
 
         ie = Dependencies.end(); it != ie; ++it) {
197
 
    Predecessors[it->second].push_back(it->first);
198
 
    Successors[it->first].push_back(it->second);
199
 
  }
200
 
 
201
 
  // Compute the roots.
202
 
  for (changeset_ty::const_iterator it = Changes.begin(),
203
 
         ie = Changes.end(); it != ie; ++it)
204
 
    if (succ_begin(*it) == succ_end(*it))
205
 
      Roots.push_back(*it);
206
 
 
207
 
  // Pre-compute the closure of the successor relation.
208
 
  std::vector<change_ty> Worklist(Roots.begin(), Roots.end());
209
 
  while (!Worklist.empty()) {
210
 
    change_ty Change = Worklist.back();
211
 
    Worklist.pop_back();
212
 
 
213
 
    std::set<change_ty> &ChangeSuccs = SuccClosure[Change];
214
 
    for (pred_iterator_ty it = pred_begin(Change), 
215
 
           ie = pred_end(Change); it != ie; ++it) {
216
 
      SuccClosure[*it].insert(Change);
217
 
      SuccClosure[*it].insert(ChangeSuccs.begin(), ChangeSuccs.end());
218
 
      Worklist.push_back(*it);
219
 
    }
220
 
  }
221
 
 
222
 
  // Invert to form the predecessor closure map.
223
 
  for (changeset_ty::const_iterator it = Changes.begin(),
224
 
         ie = Changes.end(); it != ie; ++it)
225
 
    PredClosure.insert(std::make_pair(*it, std::set<change_ty>()));
226
 
  for (changeset_ty::const_iterator it = Changes.begin(),
227
 
         ie = Changes.end(); it != ie; ++it)
228
 
    for (succ_closure_iterator_ty it2 = succ_closure_begin(*it),
229
 
           ie2 = succ_closure_end(*it); it2 != ie2; ++it2)
230
 
      PredClosure[*it2].insert(*it);
231
 
  
232
 
  // Dump useful debug info.
233
 
  DEBUG({
234
 
      llvm::errs() << "-- DAGDeltaAlgorithmImpl --\n";
235
 
      llvm::errs() << "Changes: [";
236
 
      for (changeset_ty::const_iterator it = Changes.begin(),
237
 
             ie = Changes.end(); it != ie; ++it) {
238
 
        if (it != Changes.begin()) llvm::errs() << ", ";
239
 
        llvm::errs() << *it;
240
 
 
241
 
        if (succ_begin(*it) != succ_end(*it)) {
242
 
          llvm::errs() << "(";
243
 
          for (succ_iterator_ty it2 = succ_begin(*it),
244
 
                 ie2 = succ_end(*it); it2 != ie2; ++it2) {
245
 
            if (it2 != succ_begin(*it)) llvm::errs() << ", ";
246
 
            llvm::errs() << "->" << *it2;
247
 
          }
248
 
          llvm::errs() << ")";
249
 
        }
250
 
      }
251
 
      llvm::errs() << "]\n";
252
 
 
253
 
      llvm::errs() << "Roots: [";
254
 
      for (std::vector<change_ty>::const_iterator it = Roots.begin(),
255
 
             ie = Roots.end(); it != ie; ++it) {
256
 
        if (it != Roots.begin()) llvm::errs() << ", ";
257
 
        llvm::errs() << *it;
258
 
      }
259
 
      llvm::errs() << "]\n";
260
 
 
261
 
      llvm::errs() << "Predecessor Closure:\n";
262
 
      for (changeset_ty::const_iterator it = Changes.begin(),
263
 
             ie = Changes.end(); it != ie; ++it) {
264
 
        llvm::errs() << format("  %-4d: [", *it);
265
 
        for (pred_closure_iterator_ty it2 = pred_closure_begin(*it),
266
 
               ie2 = pred_closure_end(*it); it2 != ie2; ++it2) {
267
 
          if (it2 != pred_closure_begin(*it)) llvm::errs() << ", ";
268
 
          llvm::errs() << *it2;
269
 
        }
270
 
        llvm::errs() << "]\n";
271
 
      }
272
 
      
273
 
      llvm::errs() << "Successor Closure:\n";
274
 
      for (changeset_ty::const_iterator it = Changes.begin(),
275
 
             ie = Changes.end(); it != ie; ++it) {
276
 
        llvm::errs() << format("  %-4d: [", *it);
277
 
        for (succ_closure_iterator_ty it2 = succ_closure_begin(*it),
278
 
               ie2 = succ_closure_end(*it); it2 != ie2; ++it2) {
279
 
          if (it2 != succ_closure_begin(*it)) llvm::errs() << ", ";
280
 
          llvm::errs() << *it2;
281
 
        }
282
 
        llvm::errs() << "]\n";
283
 
      }
284
 
 
285
 
      llvm::errs() << "\n\n";
286
 
    });
287
 
}
288
 
 
289
 
bool DAGDeltaAlgorithmImpl::GetTestResult(const changeset_ty &Changes,
290
 
                                          const changeset_ty &Required) {
291
 
  changeset_ty Extended(Required);
292
 
  Extended.insert(Changes.begin(), Changes.end());
293
 
  for (changeset_ty::const_iterator it = Changes.begin(),
294
 
         ie = Changes.end(); it != ie; ++it)
295
 
    Extended.insert(pred_closure_begin(*it), pred_closure_end(*it));
296
 
 
297
 
  if (FailedTestsCache.count(Extended))
298
 
    return false;
299
 
 
300
 
  bool Result = ExecuteOneTest(Extended);
301
 
  if (!Result)
302
 
    FailedTestsCache.insert(Extended);
303
 
 
304
 
  return Result;
305
 
}
306
 
 
307
 
DAGDeltaAlgorithm::changeset_ty
308
 
DAGDeltaAlgorithmImpl::Run() {
309
 
  // The current set of changes we are minimizing, starting at the roots.
310
 
  changeset_ty CurrentSet(Roots.begin(), Roots.end());
311
 
 
312
 
  // The set of required changes.
313
 
  changeset_ty Required;
314
 
 
315
 
  // Iterate until the active set of changes is empty. Convergence is guaranteed
316
 
  // assuming input was a DAG.
317
 
  //
318
 
  // Invariant:  CurrentSet intersect Required == {}
319
 
  // Invariant:  Required == (Required union succ*(Required))
320
 
  while (!CurrentSet.empty()) {
321
 
    DEBUG({
322
 
        llvm::errs() << "DAG_DD - " << CurrentSet.size() << " active changes, "
323
 
                     << Required.size() << " required changes\n";
324
 
      });
325
 
 
326
 
    // Minimize the current set of changes.
327
 
    DeltaActiveSetHelper Helper(*this, Required);
328
 
    changeset_ty CurrentMinSet = Helper.Run(CurrentSet);
329
 
 
330
 
    // Update the set of required changes. Since
331
 
    //   CurrentMinSet subset CurrentSet
332
 
    // and after the last iteration,
333
 
    //   succ(CurrentSet) subset Required
334
 
    // then
335
 
    //   succ(CurrentMinSet) subset Required
336
 
    // and our invariant on Required is maintained.
337
 
    Required.insert(CurrentMinSet.begin(), CurrentMinSet.end());
338
 
 
339
 
    // Replace the current set with the predecssors of the minimized set of
340
 
    // active changes.
341
 
    CurrentSet.clear();
342
 
    for (changeset_ty::const_iterator it = CurrentMinSet.begin(),
343
 
           ie = CurrentMinSet.end(); it != ie; ++it)
344
 
      CurrentSet.insert(pred_begin(*it), pred_end(*it));
345
 
 
346
 
    // FIXME: We could enforce CurrentSet intersect Required == {} here if we
347
 
    // wanted to protect against cyclic graphs.
348
 
  }
349
 
 
350
 
  return Required;
351
 
}
352
 
 
353
 
DAGDeltaAlgorithm::changeset_ty
354
 
DAGDeltaAlgorithm::Run(const changeset_ty &Changes,
355
 
                       const std::vector<edge_ty> &Dependencies) {
356
 
  return DAGDeltaAlgorithmImpl(*this, Changes, Dependencies).Run();
357
 
}