aboutsummaryrefslogtreecommitdiffstats
path: root/lib/Support/DAGDeltaAlgorithm.cpp
blob: 34e82cf44169f27c6a39f88bd79eb0123d8c6505 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
//===--- DAGDeltaAlgorithm.cpp - A DAG Minimization Algorithm --*- C++ -*--===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//===----------------------------------------------------------------------===//
//
// The algorithm we use attempts to exploit the dependency information by
// minimizing top-down. We start by constructing an initial root set R, and
// then iteratively:
//
//   1. Minimize the set R using the test predicate:
//       P'(S) = P(S union pred*(S))
//
//   2. Extend R to R' = R union pred(R).
//
// until a fixed point is reached.
//
// The idea is that we want to quickly prune entire portions of the graph, so we
// try to find high-level nodes that can be eliminated with all of their
// dependents.
//
// FIXME: The current algorithm doesn't actually provide a strong guarantee
// about the minimality of the result. The problem is that after adding nodes to
// the required set, we no longer consider them for elimination. For strictly
// well formed predicates, this doesn't happen, but it commonly occurs in
// practice when there are unmodelled dependencies. I believe we can resolve
// this by allowing the required set to be minimized as well, but need more test
// cases first.
//
//===----------------------------------------------------------------------===//

#include "llvm/ADT/DAGDeltaAlgorithm.h"
#include "llvm/ADT/DeltaAlgorithm.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Format.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <iterator>
#include <map>
using namespace llvm;

namespace {

class DAGDeltaAlgorithmImpl {
  friend class DeltaActiveSetHelper;

public:
  typedef DAGDeltaAlgorithm::change_ty change_ty;
  typedef DAGDeltaAlgorithm::changeset_ty changeset_ty;
  typedef DAGDeltaAlgorithm::changesetlist_ty changesetlist_ty;
  typedef DAGDeltaAlgorithm::edge_ty edge_ty;

private:
  typedef std::vector<change_ty>::iterator pred_iterator_ty;
  typedef std::vector<change_ty>::iterator succ_iterator_ty;
  typedef std::set<change_ty>::iterator pred_closure_iterator_ty;
  typedef std::set<change_ty>::iterator succ_closure_iterator_ty;

  DAGDeltaAlgorithm &DDA;

  const changeset_ty &Changes;
  const std::vector<edge_ty> &Dependencies;

  std::vector<change_ty> Roots;

  /// Cache of failed test results. Successful test results are never cached
  /// since we always reduce following a success. We maintain an independent
  /// cache from that used by the individual delta passes because we may get
  /// hits across multiple individual delta invocations.
  mutable std::set<changeset_ty> FailedTestsCache;

  // FIXME: Gross.
  std::map<change_ty, std::vector<change_ty> > Predecessors;
  std::map<change_ty, std::vector<change_ty> > Successors;

  std::map<change_ty, std::set<change_ty> > PredClosure;
  std::map<change_ty, std::set<change_ty> > SuccClosure;

private:
  pred_iterator_ty pred_begin(change_ty Node) {
    assert(Predecessors.count(Node) && "Invalid node!");
    return Predecessors[Node].begin();
  }
  pred_iterator_ty pred_end(change_ty Node) {
    assert(Predecessors.count(Node) && "Invalid node!");
    return Predecessors[Node].end();
  }

  pred_closure_iterator_ty pred_closure_begin(change_ty Node) {
    assert(PredClosure.count(Node) && "Invalid node!");
    return PredClosure[Node].begin();
  }
  pred_closure_iterator_ty pred_closure_end(change_ty Node) {
    assert(PredClosure.count(Node) && "Invalid node!");
    return PredClosure[Node].end();
  }
  
  succ_iterator_ty succ_begin(change_ty Node) {
    assert(Successors.count(Node) && "Invalid node!");
    return Successors[Node].begin();
  }
  succ_iterator_ty succ_end(change_ty Node) {
    assert(Successors.count(Node) && "Invalid node!");
    return Successors[Node].end();
  }

  succ_closure_iterator_ty succ_closure_begin(change_ty Node) {
    assert(SuccClosure.count(Node) && "Invalid node!");
    return SuccClosure[Node].begin();
  }
  succ_closure_iterator_ty succ_closure_end(change_ty Node) {
    assert(SuccClosure.count(Node) && "Invalid node!");
    return SuccClosure[Node].end();
  }

  void UpdatedSearchState(const changeset_ty &Changes,
                          const changesetlist_ty &Sets,
                          const changeset_ty &Required) {
    DDA.UpdatedSearchState(Changes, Sets, Required);
  }

  /// ExecuteOneTest - Execute a single test predicate on the change set \p S.
  bool ExecuteOneTest(const changeset_ty &S) {
    // Check dependencies invariant.
    DEBUG({
        for (changeset_ty::const_iterator it = S.begin(),
               ie = S.end(); it != ie; ++it)
          for (succ_iterator_ty it2 = succ_begin(*it),
                 ie2 = succ_end(*it); it2 != ie2; ++it2)
            assert(S.count(*it2) && "Attempt to run invalid changeset!");
      });

    return DDA.ExecuteOneTest(S);
  }

public:
  DAGDeltaAlgorithmImpl(DAGDeltaAlgorithm &_DDA,
                        const changeset_ty &_Changes,
                        const std::vector<edge_ty> &_Dependencies);

  changeset_ty Run();

  /// GetTestResult - Get the test result for the active set \p Changes with
  /// \p Required changes from the cache, executing the test if necessary.
  ///
  /// \param Changes - The set of active changes being minimized, which should
  /// have their pred closure included in the test.
  /// \param Required - The set of changes which have previously been
  /// established to be required.
  /// \return - The test result.
  bool GetTestResult(const changeset_ty &Changes, const changeset_ty &Required);
};

/// Helper object for minimizing an active set of changes.
class DeltaActiveSetHelper : public DeltaAlgorithm {
  DAGDeltaAlgorithmImpl &DDAI;

  const changeset_ty &Required;

protected:
  /// UpdatedSearchState - Callback used when the search state changes.
  virtual void UpdatedSearchState(const changeset_ty &Changes,
                                  const changesetlist_ty &Sets) LLVM_OVERRIDE {
    DDAI.UpdatedSearchState(Changes, Sets, Required);
  }

  virtual bool ExecuteOneTest(const changeset_ty &S) LLVM_OVERRIDE {
    return DDAI.GetTestResult(S, Required);
  }

public:
  DeltaActiveSetHelper(DAGDeltaAlgorithmImpl &_DDAI,
                       const changeset_ty &_Required)
    : DDAI(_DDAI), Required(_Required) {}
};

}

DAGDeltaAlgorithmImpl::DAGDeltaAlgorithmImpl(DAGDeltaAlgorithm &_DDA,
                                             const changeset_ty &_Changes,
                                             const std::vector<edge_ty>
                                               &_Dependencies)
  : DDA(_DDA),
    Changes(_Changes),
    Dependencies(_Dependencies)
{
  for (changeset_ty::const_iterator it = Changes.begin(),
         ie = Changes.end(); it != ie; ++it) {
    Predecessors.insert(std::make_pair(*it, std::vector<change_ty>()));
    Successors.insert(std::make_pair(*it, std::vector<change_ty>()));
  }
  for (std::vector<edge_ty>::const_iterator it = Dependencies.begin(),
         ie = Dependencies.end(); it != ie; ++it) {
    Predecessors[it->second].push_back(it->first);
    Successors[it->first].push_back(it->second);
  }

  // Compute the roots.
  for (changeset_ty::const_iterator it = Changes.begin(),
         ie = Changes.end(); it != ie; ++it)
    if (succ_begin(*it) == succ_end(*it))
      Roots.push_back(*it);

  // Pre-compute the closure of the successor relation.
  std::vector<change_ty> Worklist(Roots.begin(), Roots.end());
  while (!Worklist.empty()) {
    change_ty Change = Worklist.back();
    Worklist.pop_back();

    std::set<change_ty> &ChangeSuccs = SuccClosure[Change];
    for (pred_iterator_ty it = pred_begin(Change), 
           ie = pred_end(Change); it != ie; ++it) {
      SuccClosure[*it].insert(Change);
      SuccClosure[*it].insert(ChangeSuccs.begin(), ChangeSuccs.end());
      Worklist.push_back(*it);
    }
  }

  // Invert to form the predecessor closure map.
  for (changeset_ty::const_iterator it = Changes.begin(),
         ie = Changes.end(); it != ie; ++it)
    PredClosure.insert(std::make_pair(*it, std::set<change_ty>()));
  for (changeset_ty::const_iterator it = Changes.begin(),
         ie = Changes.end(); it != ie; ++it)
    for (succ_closure_iterator_ty it2 = succ_closure_begin(*it),
           ie2 = succ_closure_end(*it); it2 != ie2; ++it2)
      PredClosure[*it2].insert(*it);
  
  // Dump useful debug info.
  DEBUG({
      llvm::errs() << "-- DAGDeltaAlgorithmImpl --\n";
      llvm::errs() << "Changes: [";
      for (changeset_ty::const_iterator it = Changes.begin(),
             ie = Changes.end(); it != ie; ++it) {
        if (it != Changes.begin()) llvm::errs() << ", ";
        llvm::errs() << *it;

        if (succ_begin(*it) != succ_end(*it)) {
          llvm::errs() << "(";
          for (succ_iterator_ty it2 = succ_begin(*it),
                 ie2 = succ_end(*it); it2 != ie2; ++it2) {
            if (it2 != succ_begin(*it)) llvm::errs() << ", ";
            llvm::errs() << "->" << *it2;
          }
          llvm::errs() << ")";
        }
      }
      llvm::errs() << "]\n";

      llvm::errs() << "Roots: [";
      for (std::vector<change_ty>::const_iterator it = Roots.begin(),
             ie = Roots.end(); it != ie; ++it) {
        if (it != Roots.begin()) llvm::errs() << ", ";
        llvm::errs() << *it;
      }
      llvm::errs() << "]\n";

      llvm::errs() << "Predecessor Closure:\n";
      for (changeset_ty::const_iterator it = Changes.begin(),
             ie = Changes.end(); it != ie; ++it) {
        llvm::errs() << format("  %-4d: [", *it);
        for (pred_closure_iterator_ty it2 = pred_closure_begin(*it),
               ie2 = pred_closure_end(*it); it2 != ie2; ++it2) {
          if (it2 != pred_closure_begin(*it)) llvm::errs() << ", ";
          llvm::errs() << *it2;
        }
        llvm::errs() << "]\n";
      }
      
      llvm::errs() << "Successor Closure:\n";
      for (changeset_ty::const_iterator it = Changes.begin(),
             ie = Changes.end(); it != ie; ++it) {
        llvm::errs() << format("  %-4d: [", *it);
        for (succ_closure_iterator_ty it2 = succ_closure_begin(*it),
               ie2 = succ_closure_end(*it); it2 != ie2; ++it2) {
          if (it2 != succ_closure_begin(*it)) llvm::errs() << ", ";
          llvm::errs() << *it2;
        }
        llvm::errs() << "]\n";
      }

      llvm::errs() << "\n\n";
    });
}

bool DAGDeltaAlgorithmImpl::GetTestResult(const changeset_ty &Changes,
                                          const changeset_ty &Required) {
  changeset_ty Extended(Required);
  Extended.insert(Changes.begin(), Changes.end());
  for (changeset_ty::const_iterator it = Changes.begin(),
         ie = Changes.end(); it != ie; ++it)
    Extended.insert(pred_closure_begin(*it), pred_closure_end(*it));

  if (FailedTestsCache.count(Extended))
    return false;

  bool Result = ExecuteOneTest(Extended);
  if (!Result)
    FailedTestsCache.insert(Extended);

  return Result;
}

DAGDeltaAlgorithm::changeset_ty
DAGDeltaAlgorithmImpl::Run() {
  // The current set of changes we are minimizing, starting at the roots.
  changeset_ty CurrentSet(Roots.begin(), Roots.end());

  // The set of required changes.
  changeset_ty Required;

  // Iterate until the active set of changes is empty. Convergence is guaranteed
  // assuming input was a DAG.
  //
  // Invariant:  CurrentSet intersect Required == {}
  // Invariant:  Required == (Required union succ*(Required))
  while (!CurrentSet.empty()) {
    DEBUG({
        llvm::errs() << "DAG_DD - " << CurrentSet.size() << " active changes, "
                     << Required.size() << " required changes\n";
      });

    // Minimize the current set of changes.
    DeltaActiveSetHelper Helper(*this, Required);
    changeset_ty CurrentMinSet = Helper.Run(CurrentSet);

    // Update the set of required changes. Since
    //   CurrentMinSet subset CurrentSet
    // and after the last iteration,
    //   succ(CurrentSet) subset Required
    // then
    //   succ(CurrentMinSet) subset Required
    // and our invariant on Required is maintained.
    Required.insert(CurrentMinSet.begin(), CurrentMinSet.end());

    // Replace the current set with the predecssors of the minimized set of
    // active changes.
    CurrentSet.clear();
    for (changeset_ty::const_iterator it = CurrentMinSet.begin(),
           ie = CurrentMinSet.end(); it != ie; ++it)
      CurrentSet.insert(pred_begin(*it), pred_end(*it));

    // FIXME: We could enforce CurrentSet intersect Required == {} here if we
    // wanted to protect against cyclic graphs.
  }

  return Required;
}

void DAGDeltaAlgorithm::anchor() {
}

DAGDeltaAlgorithm::changeset_ty
DAGDeltaAlgorithm::Run(const changeset_ty &Changes,
                       const std::vector<edge_ty> &Dependencies) {
  return DAGDeltaAlgorithmImpl(*this, Changes, Dependencies).Run();
}