← Back to branch summary

~ubuntu-branches/ubuntu/feisty/clamav/feisty

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/lib/CodeGen/PBQP/Heuristics/Briggs.h

  • Committer: Bazaar Package Importer
  • Author(s): Kees Cook
  • Date: 2007-02-20 10:33:44 UTC
  • mto: This revision was merged to the branch mainline in revision 16.
  • Revision ID: james.westby@ubuntu.com-20070220103344-zgcu2psnx9d98fpa
Tags: upstream-0.90
Import upstream version 0.90

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/lib/CodeGen/PBQP/Heuristics/Briggs.h
1
 
//===-- Briggs.h --- Briggs Heuristic for PBQP ------------------*- 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
 
//
10
 
// This class implements the Briggs test for "allocability" of nodes in a
11
 
// PBQP graph representing a register allocation problem. Nodes which can be
12
 
// proven allocable (by a safe and relatively accurate test) are removed from
13
 
// the PBQP graph first. If no provably allocable node is present in the graph
14
 
// then the node with the minimal spill-cost to degree ratio is removed.
15
 
//
16
 
//===----------------------------------------------------------------------===//
17
 
 
18
 
#ifndef LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H
19
 
#define LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H
20
 
 
21
 
#include "../HeuristicSolver.h"
22
 
#include "../HeuristicBase.h"
23
 
 
24
 
#include <set>
25
 
#include <limits>
26
 
 
27
 
namespace PBQP {
28
 
  namespace Heuristics {
29
 
 
30
 
    /// \brief PBQP Heuristic which applies an allocability test based on
31
 
    ///        Briggs.
32
 
    /// 
33
 
    /// This heuristic assumes that the elements of cost vectors in the PBQP
34
 
    /// problem represent storage options, with the first being the spill
35
 
    /// option and subsequent elements representing legal registers for the
36
 
    /// corresponding node. Edge cost matrices are likewise assumed to represent
37
 
    /// register constraints.
38
 
    /// If one or more nodes can be proven allocable by this heuristic (by
39
 
    /// inspection of their constraint matrices) then the allocable node of
40
 
    /// highest degree is selected for the next reduction and pushed to the
41
 
    /// solver stack. If no nodes can be proven allocable then the node with
42
 
    /// the lowest estimated spill cost is selected and push to the solver stack
43
 
    /// instead.
44
 
    /// 
45
 
    /// This implementation is built on top of HeuristicBase.       
46
 
    class Briggs : public HeuristicBase<Briggs> {
47
 
    private:
48
 
 
49
 
      class LinkDegreeComparator {
50
 
      public:
51
 
        LinkDegreeComparator(HeuristicSolverImpl<Briggs> &s) : s(&s) {}
52
 
        bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const {
53
 
          if (s->getSolverDegree(n1Itr) > s->getSolverDegree(n2Itr))
54
 
            return true;
55
 
          return false;
56
 
        }
57
 
      private:
58
 
        HeuristicSolverImpl<Briggs> *s;
59
 
      };
60
 
 
61
 
      class SpillCostComparator {
62
 
      public:
63
 
        SpillCostComparator(HeuristicSolverImpl<Briggs> &s)
64
 
          : s(&s), g(&s.getGraph()) {}
65
 
        bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const {
66
 
          PBQPNum cost1 = g->getNodeCosts(n1Itr)[0] / s->getSolverDegree(n1Itr),
67
 
                  cost2 = g->getNodeCosts(n2Itr)[0] / s->getSolverDegree(n2Itr);
68
 
          if (cost1 < cost2)
69
 
            return true;
70
 
          return false;
71
 
        }
72
 
 
73
 
      private:
74
 
        HeuristicSolverImpl<Briggs> *s;
75
 
        Graph *g;
76
 
      };
77
 
 
78
 
      typedef std::list<Graph::NodeItr> RNAllocableList;
79
 
      typedef RNAllocableList::iterator RNAllocableListItr;
80
 
 
81
 
      typedef std::list<Graph::NodeItr> RNUnallocableList;  
82
 
      typedef RNUnallocableList::iterator RNUnallocableListItr;
83
 
 
84
 
    public:
85
 
 
86
 
      struct NodeData {
87
 
        typedef std::vector<unsigned> UnsafeDegreesArray;
88
 
        bool isHeuristic, isAllocable, isInitialized;
89
 
        unsigned numDenied, numSafe;
90
 
        UnsafeDegreesArray unsafeDegrees;
91
 
        RNAllocableListItr rnaItr;
92
 
        RNUnallocableListItr rnuItr;
93
 
 
94
 
        NodeData()
95
 
          : isHeuristic(false), isAllocable(false), isInitialized(false),
96
 
            numDenied(0), numSafe(0) { }
97
 
      };
98
 
 
99
 
      struct EdgeData {
100
 
        typedef std::vector<unsigned> UnsafeArray;
101
 
        unsigned worst, reverseWorst;
102
 
        UnsafeArray unsafe, reverseUnsafe;
103
 
        bool isUpToDate;
104
 
 
105
 
        EdgeData() : worst(0), reverseWorst(0), isUpToDate(false) {}
106
 
      };
107
 
 
108
 
      /// \brief Construct an instance of the Briggs heuristic.
109
 
      /// @param solver A reference to the solver which is using this heuristic.
110
 
      Briggs(HeuristicSolverImpl<Briggs> &solver) :
111
 
        HeuristicBase<Briggs>(solver) {}
112
 
 
113
 
      /// \brief Determine whether a node should be reduced using optimal
114
 
      ///        reduction.
115
 
      /// @param nItr Node iterator to be considered.
116
 
      /// @return True if the given node should be optimally reduced, false
117
 
      ///         otherwise.
118
 
      ///
119
 
      /// Selects nodes of degree 0, 1 or 2 for optimal reduction, with one
120
 
      /// exception. Nodes whose spill cost (element 0 of their cost vector) is
121
 
      /// infinite are checked for allocability first. Allocable nodes may be
122
 
      /// optimally reduced, but nodes whose allocability cannot be proven are
123
 
      /// selected for heuristic reduction instead.
124
 
      bool shouldOptimallyReduce(Graph::NodeItr nItr) {
125
 
        if (getSolver().getSolverDegree(nItr) < 3) {
126
 
          return true;
127
 
        }
128
 
        // else
129
 
        return false;
130
 
      }
131
 
 
132
 
      /// \brief Add a node to the heuristic reduce list.
133
 
      /// @param nItr Node iterator to add to the heuristic reduce list.
134
 
      void addToHeuristicReduceList(Graph::NodeItr nItr) {
135
 
        NodeData &nd = getHeuristicNodeData(nItr);
136
 
        initializeNode(nItr);
137
 
        nd.isHeuristic = true;
138
 
        if (nd.isAllocable) {
139
 
          nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr);
140
 
        } else {
141
 
          nd.rnuItr = rnUnallocableList.insert(rnUnallocableList.end(), nItr);
142
 
        }
143
 
      }
144
 
 
145
 
      /// \brief Heuristically reduce one of the nodes in the heuristic
146
 
      ///        reduce list.
147
 
      /// @return True if a reduction takes place, false if the heuristic reduce
148
 
      ///         list is empty.
149
 
      ///
150
 
      /// If the list of allocable nodes is non-empty a node is selected
151
 
      /// from it and pushed to the stack. Otherwise if the non-allocable list
152
 
      /// is non-empty a node is selected from it and pushed to the stack.
153
 
      /// If both lists are empty the method simply returns false with no action
154
 
      /// taken.
155
 
      bool heuristicReduce() {
156
 
        if (!rnAllocableList.empty()) {
157
 
          RNAllocableListItr rnaItr =
158
 
            min_element(rnAllocableList.begin(), rnAllocableList.end(),
159
 
                        LinkDegreeComparator(getSolver()));
160
 
          Graph::NodeItr nItr = *rnaItr;
161
 
          rnAllocableList.erase(rnaItr);
162
 
          handleRemoveNode(nItr);
163
 
          getSolver().pushToStack(nItr);
164
 
          return true;
165
 
        } else if (!rnUnallocableList.empty()) {
166
 
          RNUnallocableListItr rnuItr =
167
 
            min_element(rnUnallocableList.begin(), rnUnallocableList.end(),
168
 
                        SpillCostComparator(getSolver()));
169
 
          Graph::NodeItr nItr = *rnuItr;
170
 
          rnUnallocableList.erase(rnuItr);
171
 
          handleRemoveNode(nItr);
172
 
          getSolver().pushToStack(nItr);
173
 
          return true;
174
 
        }
175
 
        // else
176
 
        return false;
177
 
      }
178
 
 
179
 
      /// \brief Prepare a change in the costs on the given edge.
180
 
      /// @param eItr Edge iterator.    
181
 
      void preUpdateEdgeCosts(Graph::EdgeItr eItr) {
182
 
        Graph &g = getGraph();
183
 
        Graph::NodeItr n1Itr = g.getEdgeNode1(eItr),
184
 
                       n2Itr = g.getEdgeNode2(eItr);
185
 
        NodeData &n1 = getHeuristicNodeData(n1Itr),
186
 
                 &n2 = getHeuristicNodeData(n2Itr);
187
 
 
188
 
        if (n1.isHeuristic)
189
 
          subtractEdgeContributions(eItr, getGraph().getEdgeNode1(eItr));
190
 
        if (n2.isHeuristic)
191
 
          subtractEdgeContributions(eItr, getGraph().getEdgeNode2(eItr));
192
 
 
193
 
        EdgeData &ed = getHeuristicEdgeData(eItr);
194
 
        ed.isUpToDate = false;
195
 
      }
196
 
 
197
 
      /// \brief Handle the change in the costs on the given edge.
198
 
      /// @param eItr Edge iterator.
199
 
      void postUpdateEdgeCosts(Graph::EdgeItr eItr) {
200
 
        // This is effectively the same as adding a new edge now, since
201
 
        // we've factored out the costs of the old one.
202
 
        handleAddEdge(eItr);
203
 
      }
204
 
 
205
 
      /// \brief Handle the addition of a new edge into the PBQP graph.
206
 
      /// @param eItr Edge iterator for the added edge.
207
 
      ///
208
 
      /// Updates allocability of any nodes connected by this edge which are
209
 
      /// being managed by the heuristic. If allocability changes they are
210
 
      /// moved to the appropriate list.
211
 
      void handleAddEdge(Graph::EdgeItr eItr) {
212
 
        Graph &g = getGraph();
213
 
        Graph::NodeItr n1Itr = g.getEdgeNode1(eItr),
214
 
                       n2Itr = g.getEdgeNode2(eItr);
215
 
        NodeData &n1 = getHeuristicNodeData(n1Itr),
216
 
                 &n2 = getHeuristicNodeData(n2Itr);
217
 
 
218
 
        // If neither node is managed by the heuristic there's nothing to be
219
 
        // done.
220
 
        if (!n1.isHeuristic && !n2.isHeuristic)
221
 
          return;
222
 
 
223
 
        // Ok - we need to update at least one node.
224
 
        computeEdgeContributions(eItr);
225
 
 
226
 
        // Update node 1 if it's managed by the heuristic.
227
 
        if (n1.isHeuristic) {
228
 
          bool n1WasAllocable = n1.isAllocable;
229
 
          addEdgeContributions(eItr, n1Itr);
230
 
          updateAllocability(n1Itr);
231
 
          if (n1WasAllocable && !n1.isAllocable) {
232
 
            rnAllocableList.erase(n1.rnaItr);
233
 
            n1.rnuItr =
234
 
              rnUnallocableList.insert(rnUnallocableList.end(), n1Itr);
235
 
          }
236
 
        }
237
 
 
238
 
        // Likewise for node 2.
239
 
        if (n2.isHeuristic) {
240
 
          bool n2WasAllocable = n2.isAllocable;
241
 
          addEdgeContributions(eItr, n2Itr);
242
 
          updateAllocability(n2Itr);
243
 
          if (n2WasAllocable && !n2.isAllocable) {
244
 
            rnAllocableList.erase(n2.rnaItr);
245
 
            n2.rnuItr =
246
 
              rnUnallocableList.insert(rnUnallocableList.end(), n2Itr);
247
 
          }
248
 
        }
249
 
      }
250
 
 
251
 
      /// \brief Handle disconnection of an edge from a node.
252
 
      /// @param eItr Edge iterator for edge being disconnected.
253
 
      /// @param nItr Node iterator for the node being disconnected from.
254
 
      ///
255
 
      /// Updates allocability of the given node and, if appropriate, moves the
256
 
      /// node to a new list.
257
 
      void handleRemoveEdge(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
258
 
        NodeData &nd = getHeuristicNodeData(nItr);
259
 
 
260
 
        // If the node is not managed by the heuristic there's nothing to be
261
 
        // done.
262
 
        if (!nd.isHeuristic)
263
 
          return;
264
 
 
265
 
        EdgeData &ed = getHeuristicEdgeData(eItr);
266
 
        (void)ed;
267
 
        assert(ed.isUpToDate && "Edge data is not up to date.");
268
 
 
269
 
        // Update node.
270
 
        bool ndWasAllocable = nd.isAllocable;
271
 
        subtractEdgeContributions(eItr, nItr);
272
 
        updateAllocability(nItr);
273
 
 
274
 
        // If the node has gone optimal...
275
 
        if (shouldOptimallyReduce(nItr)) {
276
 
          nd.isHeuristic = false;
277
 
          addToOptimalReduceList(nItr);
278
 
          if (ndWasAllocable) {
279
 
            rnAllocableList.erase(nd.rnaItr);
280
 
          } else {
281
 
            rnUnallocableList.erase(nd.rnuItr);
282
 
          }
283
 
        } else {
284
 
          // Node didn't go optimal, but we might have to move it
285
 
          // from "unallocable" to "allocable".
286
 
          if (!ndWasAllocable && nd.isAllocable) {
287
 
            rnUnallocableList.erase(nd.rnuItr);
288
 
            nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr);
289
 
          }
290
 
        }
291
 
      }
292
 
 
293
 
    private:
294
 
 
295
 
      NodeData& getHeuristicNodeData(Graph::NodeItr nItr) {
296
 
        return getSolver().getHeuristicNodeData(nItr);
297
 
      }
298
 
 
299
 
      EdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) {
300
 
        return getSolver().getHeuristicEdgeData(eItr);
301
 
      }
302
 
 
303
 
      // Work out what this edge will contribute to the allocability of the
304
 
      // nodes connected to it.
305
 
      void computeEdgeContributions(Graph::EdgeItr eItr) {
306
 
        EdgeData &ed = getHeuristicEdgeData(eItr);
307
 
 
308
 
        if (ed.isUpToDate)
309
 
          return; // Edge data is already up to date.
310
 
 
311
 
        Matrix &eCosts = getGraph().getEdgeCosts(eItr);
312
 
 
313
 
        unsigned numRegs = eCosts.getRows() - 1,
314
 
                 numReverseRegs = eCosts.getCols() - 1;
315
 
 
316
 
        std::vector<unsigned> rowInfCounts(numRegs, 0),
317
 
                              colInfCounts(numReverseRegs, 0);        
318
 
 
319
 
        ed.worst = 0;
320
 
        ed.reverseWorst = 0;
321
 
        ed.unsafe.clear();
322
 
        ed.unsafe.resize(numRegs, 0);
323
 
        ed.reverseUnsafe.clear();
324
 
        ed.reverseUnsafe.resize(numReverseRegs, 0);
325
 
 
326
 
        for (unsigned i = 0; i < numRegs; ++i) {
327
 
          for (unsigned j = 0; j < numReverseRegs; ++j) {
328
 
            if (eCosts[i + 1][j + 1] ==
329
 
                  std::numeric_limits<PBQPNum>::infinity()) {
330
 
              ed.unsafe[i] = 1;
331
 
              ed.reverseUnsafe[j] = 1;
332
 
              ++rowInfCounts[i];
333
 
              ++colInfCounts[j];
334
 
 
335
 
              if (colInfCounts[j] > ed.worst) {
336
 
                ed.worst = colInfCounts[j];
337
 
              }
338
 
 
339
 
              if (rowInfCounts[i] > ed.reverseWorst) {
340
 
                ed.reverseWorst = rowInfCounts[i];
341
 
              }
342
 
            }
343
 
          }
344
 
        }
345
 
 
346
 
        ed.isUpToDate = true;
347
 
      }
348
 
 
349
 
      // Add the contributions of the given edge to the given node's 
350
 
      // numDenied and safe members. No action is taken other than to update
351
 
      // these member values. Once updated these numbers can be used by clients
352
 
      // to update the node's allocability.
353
 
      void addEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
354
 
        EdgeData &ed = getHeuristicEdgeData(eItr);
355
 
 
356
 
        assert(ed.isUpToDate && "Using out-of-date edge numbers.");
357
 
 
358
 
        NodeData &nd = getHeuristicNodeData(nItr);
359
 
        unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
360
 
        
361
 
        bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr);
362
 
        EdgeData::UnsafeArray &unsafe =
363
 
          nIsNode1 ? ed.unsafe : ed.reverseUnsafe;
364
 
        nd.numDenied += nIsNode1 ? ed.worst : ed.reverseWorst;
365
 
 
366
 
        for (unsigned r = 0; r < numRegs; ++r) {
367
 
          if (unsafe[r]) {
368
 
            if (nd.unsafeDegrees[r]==0) {
369
 
              --nd.numSafe;
370
 
            }
371
 
            ++nd.unsafeDegrees[r];
372
 
          }
373
 
        }
374
 
      }
375
 
 
376
 
      // Subtract the contributions of the given edge to the given node's 
377
 
      // numDenied and safe members. No action is taken other than to update
378
 
      // these member values. Once updated these numbers can be used by clients
379
 
      // to update the node's allocability.
380
 
      void subtractEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
381
 
        EdgeData &ed = getHeuristicEdgeData(eItr);
382
 
 
383
 
        assert(ed.isUpToDate && "Using out-of-date edge numbers.");
384
 
 
385
 
        NodeData &nd = getHeuristicNodeData(nItr);
386
 
        unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
387
 
        
388
 
        bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr);
389
 
        EdgeData::UnsafeArray &unsafe =
390
 
          nIsNode1 ? ed.unsafe : ed.reverseUnsafe;
391
 
        nd.numDenied -= nIsNode1 ? ed.worst : ed.reverseWorst;
392
 
 
393
 
        for (unsigned r = 0; r < numRegs; ++r) {
394
 
          if (unsafe[r]) { 
395
 
            if (nd.unsafeDegrees[r] == 1) {
396
 
              ++nd.numSafe;
397
 
            }
398
 
            --nd.unsafeDegrees[r];
399
 
          }
400
 
        }
401
 
      }
402
 
 
403
 
      void updateAllocability(Graph::NodeItr nItr) {
404
 
        NodeData &nd = getHeuristicNodeData(nItr);
405
 
        unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
406
 
        nd.isAllocable = nd.numDenied < numRegs || nd.numSafe > 0;
407
 
      }
408
 
 
409
 
      void initializeNode(Graph::NodeItr nItr) {
410
 
        NodeData &nd = getHeuristicNodeData(nItr);
411
 
 
412
 
        if (nd.isInitialized)
413
 
          return; // Node data is already up to date.
414
 
 
415
 
        unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
416
 
 
417
 
        nd.numDenied = 0;
418
 
        nd.numSafe = numRegs;
419
 
        nd.unsafeDegrees.resize(numRegs, 0);
420
 
 
421
 
        typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr;
422
 
 
423
 
        for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(nItr),
424
 
                           aeEnd = getSolver().solverEdgesEnd(nItr);
425
 
             aeItr != aeEnd; ++aeItr) {
426
 
          
427
 
          Graph::EdgeItr eItr = *aeItr;
428
 
          computeEdgeContributions(eItr);
429
 
          addEdgeContributions(eItr, nItr);
430
 
        }
431
 
 
432
 
        updateAllocability(nItr);
433
 
        nd.isInitialized = true;
434
 
      }
435
 
 
436
 
      void handleRemoveNode(Graph::NodeItr xnItr) {
437
 
        typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr;
438
 
        std::vector<Graph::EdgeItr> edgesToRemove;
439
 
        for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(xnItr),
440
 
                           aeEnd = getSolver().solverEdgesEnd(xnItr);
441
 
             aeItr != aeEnd; ++aeItr) {
442
 
          Graph::NodeItr ynItr = getGraph().getEdgeOtherNode(*aeItr, xnItr);
443
 
          handleRemoveEdge(*aeItr, ynItr);
444
 
          edgesToRemove.push_back(*aeItr);
445
 
        }
446
 
        while (!edgesToRemove.empty()) {
447
 
          getSolver().removeSolverEdge(edgesToRemove.back());
448
 
          edgesToRemove.pop_back();
449
 
        }
450
 
      }
451
 
 
452
 
      RNAllocableList rnAllocableList;
453
 
      RNUnallocableList rnUnallocableList;
454
 
    };
455
 
 
456
 
  }
457
 
}
458
 
 
459
 
 
460
 
#endif // LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H