← Back to branch summary

~louis/ubuntu/trusty/clamav/lp799623_fix_logrotate

« 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): Scott Kitterman
  • Date: 2010-03-12 11:30:04 UTC
  • mfrom: (0.41.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20100312113004-b0fop4bkycszdd0z
Tags: 0.96~rc1+dfsg-0ubuntu1
https://launchpad.net/bugs/537636
* New upstream RC - FFE (LP: #537636):
  - Add OfficialDatabaseOnly option to clamav-base.postinst.in
  - Add LocalSocketGroup option to clamav-base.postinst.in
  - Add LocalSocketMode option to clamav-base.postinst.in
  - Add CrossFilesystems option to clamav-base.postinst.in
  - Add ClamukoScannerCount option to clamav-base.postinst.in
  - Add BytecodeSecurity opiton to clamav-base.postinst.in
  - Add DetectionStatsHostID option to clamav-freshclam.postinst.in
  - Add Bytecode option to clamav-freshclam.postinst.in
  - Add MilterSocketGroup option to clamav-milter.postinst.in
  - Add MilterSocketMode option to clamav-milter.postinst.in
  - Add ReportHostname option to clamav-milter.postinst.in
  - Bump libclamav SO version to 6.1.0 in libclamav6.install
  - Drop clamdmon from clamav.examples (no longer shipped by upstream)
  - Drop libclamav.a from libclamav-dev.install (not built by upstream)
  - Update SO version for lintian override for libclamav6
  - Add new Bytecode Testing Tool, usr/bin/clambc, to clamav.install
  - Add build-depends on python and python-setuptools for new test suite
  - Update debian/copyright for the embedded copy of llvm (using the system
    llvm is not currently feasible)

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