← Back to branch summary

~ubuntu-branches/ubuntu/wily/clamav/wily-proposed

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/lib/CodeGen/RegAllocPBQP.cpp

  • Committer: Package Import Robot
  • Author(s): Scott Kitterman, Sebastian Andrzej Siewior, Andreas Cadhalpun, Scott Kitterman, Javier Fernández-Sanguino
  • Date: 2015-01-28 00:25:13 UTC
  • mfrom: (0.48.14 sid)
  • Revision ID: package-import@ubuntu.com-20150128002513-lil2oi74cooy4lzr
Tags: 0.98.6+dfsg-1
http://bugs.debian.org/774686
http://bugs.debian.org/767350
http://bugs.debian.org/775400
http://bugs.debian.org/767353
http://bugs.debian.org/773563
[ Sebastian Andrzej Siewior ]
* update "fix-ssize_t-size_t-off_t-printf-modifier", include of misc.h was
  missing but was pulled in via the systemd patch.
* Don't leak return codes from libmspack to clamav API. (Closes: #774686).

[ Andreas Cadhalpun ]
* Add patch to avoid emitting incremental progress messages when not
  outputting to a terminal. (Closes: #767350)
* Update lintian-overrides for unused-file-paragraph-in-dep5-copyright.
* clamav-base.postinst: always chown /var/log/clamav and /var/lib/clamav
  to clamav:clamav, not only on fresh installations. (Closes: #775400)
* Adapt the clamav-daemon and clamav-freshclam logrotate scripts,
  so that they correctly work under systemd.
* Move the PidFile variable from the clamd/freshclam configuration files
  to the init scripts. This makes the init scripts more robust against
  misconfiguration and avoids error messages with systemd. (Closes: #767353)
* debian/copyright: drop files from Files-Excluded only present in github
  tarballs
* Drop Workaround-a-bug-in-libc-on-Hurd.patch, because hurd got fixed.
  (see #752237)
* debian/rules: Remove useless --with-system-tommath --without-included-ltdl
  configure options.

[ Scott Kitterman ]
* Stop stripping llvm when repacking the tarball as the system llvm on some
  releases is too old to use
* New upstream bugfix release
  - Library shared object revisions.
  - Includes a patch from Sebastian Andrzej Siewior making ClamAV pid files
    compatible with systemd.
  - Fix a heap out of bounds condition with crafted Yoda's crypter files.
    This issue was discovered by Felix Groebert of the Google Security Team.
  - Fix a heap out of bounds condition with crafted mew packer files. This
    issue was discovered by Felix Groebert of the Google Security Team.
  - Fix a heap out of bounds condition with crafted upx packer files. This
    issue was discovered by Kevin Szkudlapski of Quarkslab.
  - Fix a heap out of bounds condition with crafted upack packer files. This
    issue was discovered by Sebastian Andrzej Siewior. CVE-2014-9328.
  - Compensate a crash due to incorrect compiler optimization when handling
    crafted petite packer files. This issue was discovered by Sebastian
    Andrzej Siewior.
* Update lintian override for embedded zlib to match new so version

[ Javier Fernández-Sanguino ]
* Updated Spanish Debconf template translation (Closes: #773563)

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/lib/CodeGen/RegAllocPBQP.cpp
 
1
//===------ RegAllocPBQP.cpp ---- PBQP Register Allocator -------*- 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 file contains a Partitioned Boolean Quadratic Programming (PBQP) based
 
11
// register allocator for LLVM. This allocator works by constructing a PBQP
 
12
// problem representing the register allocation problem under consideration,
 
13
// solving this using a PBQP solver, and mapping the solution back to a
 
14
// register assignment. If any variables are selected for spilling then spill
 
15
// code is inserted and the process repeated.
 
16
//
 
17
// The PBQP solver (pbqp.c) provided for this allocator uses a heuristic tuned
 
18
// for register allocation. For more information on PBQP for register
 
19
// allocation, see the following papers:
 
20
//
 
21
//   (1) Hames, L. and Scholz, B. 2006. Nearly optimal register allocation with
 
22
//   PBQP. In Proceedings of the 7th Joint Modular Languages Conference
 
23
//   (JMLC'06). LNCS, vol. 4228. Springer, New York, NY, USA. 346-361.
 
24
//
 
25
//   (2) Scholz, B., Eckstein, E. 2002. Register allocation for irregular
 
26
//   architectures. In Proceedings of the Joint Conference on Languages,
 
27
//   Compilers and Tools for Embedded Systems (LCTES'02), ACM Press, New York,
 
28
//   NY, USA, 139-148.
 
29
//
 
30
//===----------------------------------------------------------------------===//
 
31
 
 
32
#define DEBUG_TYPE "regalloc"
 
33
 
 
34
#include "PBQP/HeuristicSolver.h"
 
35
#include "PBQP/Graph.h"
 
36
#include "PBQP/Heuristics/Briggs.h"
 
37
#include "RenderMachineFunction.h"
 
38
#include "Splitter.h"
 
39
#include "VirtRegMap.h"
 
40
#include "VirtRegRewriter.h"
 
41
#include "llvm/CodeGen/CalcSpillWeights.h"
 
42
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
 
43
#include "llvm/CodeGen/LiveStackAnalysis.h"
 
44
#include "llvm/CodeGen/MachineFunctionPass.h"
 
45
#include "llvm/CodeGen/MachineLoopInfo.h"
 
46
#include "llvm/CodeGen/MachineRegisterInfo.h"
 
47
#include "llvm/CodeGen/RegAllocRegistry.h"
 
48
#include "llvm/CodeGen/RegisterCoalescer.h"
 
49
#include "llvm/Support/Debug.h"
 
50
#include "llvm/Support/raw_ostream.h"
 
51
#include "llvm/Target/TargetInstrInfo.h"
 
52
#include "llvm/Target/TargetMachine.h"
 
53
#include <limits>
 
54
#include <map>
 
55
#include <memory>
 
56
#include <set>
 
57
#include <vector>
 
58
 
 
59
using namespace llvm;
 
60
 
 
61
static RegisterRegAlloc
 
62
registerPBQPRepAlloc("pbqp", "PBQP register allocator",
 
63
                       llvm::createPBQPRegisterAllocator);
 
64
 
 
65
static cl::opt<bool>
 
66
pbqpCoalescing("pbqp-coalescing",
 
67
                cl::desc("Attempt coalescing during PBQP register allocation."),
 
68
                cl::init(false), cl::Hidden);
 
69
 
 
70
static cl::opt<bool>
 
71
pbqpPreSplitting("pbqp-pre-splitting",
 
72
                 cl::desc("Pre-splite before PBQP register allocation."),
 
73
                 cl::init(false), cl::Hidden);
 
74
 
 
75
namespace {
 
76
 
 
77
  ///
 
78
  /// PBQP based allocators solve the register allocation problem by mapping
 
79
  /// register allocation problems to Partitioned Boolean Quadratic
 
80
  /// Programming problems.
 
81
  class PBQPRegAlloc : public MachineFunctionPass {
 
82
  public:
 
83
 
 
84
    static char ID;
 
85
 
 
86
    /// Construct a PBQP register allocator.
 
87
    PBQPRegAlloc() : MachineFunctionPass(ID) {}
 
88
 
 
89
    /// Return the pass name.
 
90
    virtual const char* getPassName() const {
 
91
      return "PBQP Register Allocator";
 
92
    }
 
93
 
 
94
    /// PBQP analysis usage.
 
95
    virtual void getAnalysisUsage(AnalysisUsage &au) const {
 
96
      au.addRequired<SlotIndexes>();
 
97
      au.addPreserved<SlotIndexes>();
 
98
      au.addRequired<LiveIntervals>();
 
99
      //au.addRequiredID(SplitCriticalEdgesID);
 
100
      au.addRequired<RegisterCoalescer>();
 
101
      au.addRequired<CalculateSpillWeights>();
 
102
      au.addRequired<LiveStacks>();
 
103
      au.addPreserved<LiveStacks>();
 
104
      au.addRequired<MachineLoopInfo>();
 
105
      au.addPreserved<MachineLoopInfo>();
 
106
      if (pbqpPreSplitting)
 
107
        au.addRequired<LoopSplitter>();
 
108
      au.addRequired<VirtRegMap>();
 
109
      au.addRequired<RenderMachineFunction>();
 
110
      MachineFunctionPass::getAnalysisUsage(au);
 
111
    }
 
112
 
 
113
    /// Perform register allocation
 
114
    virtual bool runOnMachineFunction(MachineFunction &MF);
 
115
 
 
116
  private:
 
117
 
 
118
    class LIOrdering {
 
119
    public:
 
120
      bool operator()(const LiveInterval *li1, const LiveInterval *li2) const {
 
121
        return li1->reg < li2->reg;
 
122
      }
 
123
    };
 
124
 
 
125
    typedef std::map<const LiveInterval*, unsigned, LIOrdering> LI2NodeMap;
 
126
    typedef std::vector<const LiveInterval*> Node2LIMap;
 
127
    typedef std::vector<unsigned> AllowedSet;
 
128
    typedef std::vector<AllowedSet> AllowedSetMap;
 
129
    typedef std::set<unsigned> RegSet;
 
130
    typedef std::pair<unsigned, unsigned> RegPair;
 
131
    typedef std::map<RegPair, PBQP::PBQPNum> CoalesceMap;
 
132
 
 
133
    typedef std::set<LiveInterval*, LIOrdering> LiveIntervalSet;
 
134
 
 
135
    typedef std::vector<PBQP::Graph::NodeItr> NodeVector;
 
136
 
 
137
    MachineFunction *mf;
 
138
    const TargetMachine *tm;
 
139
    const TargetRegisterInfo *tri;
 
140
    const TargetInstrInfo *tii;
 
141
    const MachineLoopInfo *loopInfo;
 
142
    MachineRegisterInfo *mri;
 
143
    RenderMachineFunction *rmf;
 
144
 
 
145
    LiveIntervals *lis;
 
146
    LiveStacks *lss;
 
147
    VirtRegMap *vrm;
 
148
 
 
149
    LI2NodeMap li2Node;
 
150
    Node2LIMap node2LI;
 
151
    AllowedSetMap allowedSets;
 
152
    LiveIntervalSet vregIntervalsToAlloc,
 
153
                    emptyVRegIntervals;
 
154
    NodeVector problemNodes;
 
155
 
 
156
 
 
157
    /// Builds a PBQP cost vector.
 
158
    template <typename RegContainer>
 
159
    PBQP::Vector buildCostVector(unsigned vReg,
 
160
                                 const RegContainer &allowed,
 
161
                                 const CoalesceMap &cealesces,
 
162
                                 PBQP::PBQPNum spillCost) const;
 
163
 
 
164
    /// \brief Builds a PBQP interference matrix.
 
165
    ///
 
166
    /// @return Either a pointer to a non-zero PBQP matrix representing the
 
167
    ///         allocation option costs, or a null pointer for a zero matrix.
 
168
    ///
 
169
    /// Expects allowed sets for two interfering LiveIntervals. These allowed
 
170
    /// sets should contain only allocable registers from the LiveInterval's
 
171
    /// register class, with any interfering pre-colored registers removed.
 
172
    template <typename RegContainer>
 
173
    PBQP::Matrix* buildInterferenceMatrix(const RegContainer &allowed1,
 
174
                                          const RegContainer &allowed2) const;
 
175
 
 
176
    ///
 
177
    /// Expects allowed sets for two potentially coalescable LiveIntervals,
 
178
    /// and an estimated benefit due to coalescing. The allowed sets should
 
179
    /// contain only allocable registers from the LiveInterval's register
 
180
    /// classes, with any interfering pre-colored registers removed.
 
181
    template <typename RegContainer>
 
182
    PBQP::Matrix* buildCoalescingMatrix(const RegContainer &allowed1,
 
183
                                        const RegContainer &allowed2,
 
184
                                        PBQP::PBQPNum cBenefit) const;
 
185
 
 
186
    /// \brief Finds coalescing opportunities and returns them as a map.
 
187
    ///
 
188
    /// Any entries in the map are guaranteed coalescable, even if their
 
189
    /// corresponding live intervals overlap.
 
190
    CoalesceMap findCoalesces();
 
191
 
 
192
    /// \brief Finds the initial set of vreg intervals to allocate.
 
193
    void findVRegIntervalsToAlloc();
 
194
 
 
195
    /// \brief Constructs a PBQP problem representation of the register
 
196
    /// allocation problem for this function.
 
197
    ///
 
198
    /// @return a PBQP solver object for the register allocation problem.
 
199
    PBQP::Graph constructPBQPProblem();
 
200
 
 
201
    /// \brief Adds a stack interval if the given live interval has been
 
202
    /// spilled. Used to support stack slot coloring.
 
203
    void addStackInterval(const LiveInterval *spilled,MachineRegisterInfo* mri);
 
204
 
 
205
    /// \brief Given a solved PBQP problem maps this solution back to a register
 
206
    /// assignment.
 
207
    bool mapPBQPToRegAlloc(const PBQP::Solution &solution);
 
208
 
 
209
    /// \brief Postprocessing before final spilling. Sets basic block "live in"
 
210
    /// variables.
 
211
    void finalizeAlloc() const;
 
212
 
 
213
  };
 
214
 
 
215
  char PBQPRegAlloc::ID = 0;
 
216
}
 
217
 
 
218
 
 
219
template <typename RegContainer>
 
220
PBQP::Vector PBQPRegAlloc::buildCostVector(unsigned vReg,
 
221
                                           const RegContainer &allowed,
 
222
                                           const CoalesceMap &coalesces,
 
223
                                           PBQP::PBQPNum spillCost) const {
 
224
 
 
225
  typedef typename RegContainer::const_iterator AllowedItr;
 
226
 
 
227
  // Allocate vector. Additional element (0th) used for spill option
 
228
  PBQP::Vector v(allowed.size() + 1, 0);
 
229
 
 
230
  v[0] = spillCost;
 
231
 
 
232
  // Iterate over the allowed registers inserting coalesce benefits if there
 
233
  // are any.
 
234
  unsigned ai = 0;
 
235
  for (AllowedItr itr = allowed.begin(), end = allowed.end();
 
236
       itr != end; ++itr, ++ai) {
 
237
 
 
238
    unsigned pReg = *itr;
 
239
 
 
240
    CoalesceMap::const_iterator cmItr =
 
241
      coalesces.find(RegPair(vReg, pReg));
 
242
 
 
243
    // No coalesce - on to the next preg.
 
244
    if (cmItr == coalesces.end())
 
245
      continue;
 
246
 
 
247
    // We have a coalesce - insert the benefit.
 
248
    v[ai + 1] = -cmItr->second;
 
249
  }
 
250
 
 
251
  return v;
 
252
}
 
253
 
 
254
template <typename RegContainer>
 
255
PBQP::Matrix* PBQPRegAlloc::buildInterferenceMatrix(
 
256
      const RegContainer &allowed1, const RegContainer &allowed2) const {
 
257
 
 
258
  typedef typename RegContainer::const_iterator RegContainerIterator;
 
259
 
 
260
  // Construct a PBQP matrix representing the cost of allocation options. The
 
261
  // rows and columns correspond to the allocation options for the two live
 
262
  // intervals.  Elements will be infinite where corresponding registers alias,
 
263
  // since we cannot allocate aliasing registers to interfering live intervals.
 
264
  // All other elements (non-aliasing combinations) will have zero cost. Note
 
265
  // that the spill option (element 0,0) has zero cost, since we can allocate
 
266
  // both intervals to memory safely (the cost for each individual allocation
 
267
  // to memory is accounted for by the cost vectors for each live interval).
 
268
  PBQP::Matrix *m =
 
269
    new PBQP::Matrix(allowed1.size() + 1, allowed2.size() + 1, 0);
 
270
 
 
271
  // Assume this is a zero matrix until proven otherwise.  Zero matrices occur
 
272
  // between interfering live ranges with non-overlapping register sets (e.g.
 
273
  // non-overlapping reg classes, or disjoint sets of allowed regs within the
 
274
  // same class). The term "overlapping" is used advisedly: sets which do not
 
275
  // intersect, but contain registers which alias, will have non-zero matrices.
 
276
  // We optimize zero matrices away to improve solver speed.
 
277
  bool isZeroMatrix = true;
 
278
 
 
279
 
 
280
  // Row index. Starts at 1, since the 0th row is for the spill option, which
 
281
  // is always zero.
 
282
  unsigned ri = 1;
 
283
 
 
284
  // Iterate over allowed sets, insert infinities where required.
 
285
  for (RegContainerIterator a1Itr = allowed1.begin(), a1End = allowed1.end();
 
286
       a1Itr != a1End; ++a1Itr) {
 
287
 
 
288
    // Column index, starts at 1 as for row index.
 
289
    unsigned ci = 1;
 
290
    unsigned reg1 = *a1Itr;
 
291
 
 
292
    for (RegContainerIterator a2Itr = allowed2.begin(), a2End = allowed2.end();
 
293
         a2Itr != a2End; ++a2Itr) {
 
294
 
 
295
      unsigned reg2 = *a2Itr;
 
296
 
 
297
      // If the row/column regs are identical or alias insert an infinity.
 
298
      if (tri->regsOverlap(reg1, reg2)) {
 
299
        (*m)[ri][ci] = std::numeric_limits<PBQP::PBQPNum>::infinity();
 
300
        isZeroMatrix = false;
 
301
      }
 
302
 
 
303
      ++ci;
 
304
    }
 
305
 
 
306
    ++ri;
 
307
  }
 
308
 
 
309
  // If this turns out to be a zero matrix...
 
310
  if (isZeroMatrix) {
 
311
    // free it and return null.
 
312
    delete m;
 
313
    return 0;
 
314
  }
 
315
 
 
316
  // ...otherwise return the cost matrix.
 
317
  return m;
 
318
}
 
319
 
 
320
template <typename RegContainer>
 
321
PBQP::Matrix* PBQPRegAlloc::buildCoalescingMatrix(
 
322
      const RegContainer &allowed1, const RegContainer &allowed2,
 
323
      PBQP::PBQPNum cBenefit) const {
 
324
 
 
325
  typedef typename RegContainer::const_iterator RegContainerIterator;
 
326
 
 
327
  // Construct a PBQP Matrix representing the benefits of coalescing. As with
 
328
  // interference matrices the rows and columns represent allowed registers
 
329
  // for the LiveIntervals which are (potentially) to be coalesced. The amount
 
330
  // -cBenefit will be placed in any element representing the same register
 
331
  // for both intervals.
 
332
  PBQP::Matrix *m =
 
333
    new PBQP::Matrix(allowed1.size() + 1, allowed2.size() + 1, 0);
 
334
 
 
335
  // Reset costs to zero.
 
336
  m->reset(0);
 
337
 
 
338
  // Assume the matrix is zero till proven otherwise. Zero matrices will be
 
339
  // optimized away as in the interference case.
 
340
  bool isZeroMatrix = true;
 
341
 
 
342
  // Row index. Starts at 1, since the 0th row is for the spill option, which
 
343
  // is always zero.
 
344
  unsigned ri = 1;
 
345
 
 
346
  // Iterate over the allowed sets, insert coalescing benefits where
 
347
  // appropriate.
 
348
  for (RegContainerIterator a1Itr = allowed1.begin(), a1End = allowed1.end();
 
349
       a1Itr != a1End; ++a1Itr) {
 
350
 
 
351
    // Column index, starts at 1 as for row index.
 
352
    unsigned ci = 1;
 
353
    unsigned reg1 = *a1Itr;
 
354
 
 
355
    for (RegContainerIterator a2Itr = allowed2.begin(), a2End = allowed2.end();
 
356
         a2Itr != a2End; ++a2Itr) {
 
357
 
 
358
      // If the row and column represent the same register insert a beneficial
 
359
      // cost to preference this allocation - it would allow us to eliminate a
 
360
      // move instruction.
 
361
      if (reg1 == *a2Itr) {
 
362
        (*m)[ri][ci] = -cBenefit;
 
363
        isZeroMatrix = false;
 
364
      }
 
365
 
 
366
      ++ci;
 
367
    }
 
368
 
 
369
    ++ri;
 
370
  }
 
371
 
 
372
  // If this turns out to be a zero matrix...
 
373
  if (isZeroMatrix) {
 
374
    // ...free it and return null.
 
375
    delete m;
 
376
    return 0;
 
377
  }
 
378
 
 
379
  return m;
 
380
}
 
381
 
 
382
PBQPRegAlloc::CoalesceMap PBQPRegAlloc::findCoalesces() {
 
383
 
 
384
  typedef MachineFunction::const_iterator MFIterator;
 
385
  typedef MachineBasicBlock::const_iterator MBBIterator;
 
386
  typedef LiveInterval::const_vni_iterator VNIIterator;
 
387
 
 
388
  CoalesceMap coalescesFound;
 
389
 
 
390
  // To find coalesces we need to iterate over the function looking for
 
391
  // copy instructions.
 
392
  for (MFIterator bbItr = mf->begin(), bbEnd = mf->end();
 
393
       bbItr != bbEnd; ++bbItr) {
 
394
 
 
395
    const MachineBasicBlock *mbb = &*bbItr;
 
396
 
 
397
    for (MBBIterator iItr = mbb->begin(), iEnd = mbb->end();
 
398
         iItr != iEnd; ++iItr) {
 
399
 
 
400
      const MachineInstr *instr = &*iItr;
 
401
 
 
402
      // If this isn't a copy then continue to the next instruction.
 
403
      if (!instr->isCopy())
 
404
        continue;
 
405
 
 
406
      unsigned srcReg = instr->getOperand(1).getReg();
 
407
      unsigned dstReg = instr->getOperand(0).getReg();
 
408
 
 
409
      // If the registers are already the same our job is nice and easy.
 
410
      if (dstReg == srcReg)
 
411
        continue;
 
412
 
 
413
      bool srcRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(srcReg),
 
414
           dstRegIsPhysical = TargetRegisterInfo::isPhysicalRegister(dstReg);
 
415
 
 
416
      // If both registers are physical then we can't coalesce.
 
417
      if (srcRegIsPhysical && dstRegIsPhysical)
 
418
        continue;
 
419
 
 
420
      // If it's a copy that includes two virtual register but the source and
 
421
      // destination classes differ then we can't coalesce.
 
422
      if (!srcRegIsPhysical && !dstRegIsPhysical &&
 
423
          mri->getRegClass(srcReg) != mri->getRegClass(dstReg))
 
424
        continue;
 
425
 
 
426
      // If one is physical and one is virtual, check that the physical is
 
427
      // allocatable in the class of the virtual.
 
428
      if (srcRegIsPhysical && !dstRegIsPhysical) {
 
429
        const TargetRegisterClass *dstRegClass = mri->getRegClass(dstReg);
 
430
        if (std::find(dstRegClass->allocation_order_begin(*mf),
 
431
                      dstRegClass->allocation_order_end(*mf), srcReg) ==
 
432
            dstRegClass->allocation_order_end(*mf))
 
433
          continue;
 
434
      }
 
435
      if (!srcRegIsPhysical && dstRegIsPhysical) {
 
436
        const TargetRegisterClass *srcRegClass = mri->getRegClass(srcReg);
 
437
        if (std::find(srcRegClass->allocation_order_begin(*mf),
 
438
                      srcRegClass->allocation_order_end(*mf), dstReg) ==
 
439
            srcRegClass->allocation_order_end(*mf))
 
440
          continue;
 
441
      }
 
442
 
 
443
      // If we've made it here we have a copy with compatible register classes.
 
444
      // We can probably coalesce, but we need to consider overlap.
 
445
      const LiveInterval *srcLI = &lis->getInterval(srcReg),
 
446
                         *dstLI = &lis->getInterval(dstReg);
 
447
 
 
448
      if (srcLI->overlaps(*dstLI)) {
 
449
        // Even in the case of an overlap we might still be able to coalesce,
 
450
        // but we need to make sure that no definition of either range occurs
 
451
        // while the other range is live.
 
452
 
 
453
        // Otherwise start by assuming we're ok.
 
454
        bool badDef = false;
 
455
 
 
456
        // Test all defs of the source range.
 
457
        for (VNIIterator
 
458
               vniItr = srcLI->vni_begin(), vniEnd = srcLI->vni_end();
 
459
               vniItr != vniEnd; ++vniItr) {
 
460
 
 
461
          // If we find a poorly defined def we err on the side of caution.
 
462
          if (!(*vniItr)->def.isValid()) {
 
463
            badDef = true;
 
464
            break;
 
465
          }
 
466
 
 
467
          // If we find a def that kills the coalescing opportunity then
 
468
          // record it and break from the loop.
 
469
          if (dstLI->liveAt((*vniItr)->def)) {
 
470
            badDef = true;
 
471
            break;
 
472
          }
 
473
        }
 
474
 
 
475
        // If we have a bad def give up, continue to the next instruction.
 
476
        if (badDef)
 
477
          continue;
 
478
 
 
479
        // Otherwise test definitions of the destination range.
 
480
        for (VNIIterator
 
481
               vniItr = dstLI->vni_begin(), vniEnd = dstLI->vni_end();
 
482
               vniItr != vniEnd; ++vniItr) {
 
483
 
 
484
          // We want to make sure we skip the copy instruction itself.
 
485
          if ((*vniItr)->getCopy() == instr)
 
486
            continue;
 
487
 
 
488
          if (!(*vniItr)->def.isValid()) {
 
489
            badDef = true;
 
490
            break;
 
491
          }
 
492
 
 
493
          if (srcLI->liveAt((*vniItr)->def)) {
 
494
            badDef = true;
 
495
            break;
 
496
          }
 
497
        }
 
498
 
 
499
        // As before a bad def we give up and continue to the next instr.
 
500
        if (badDef)
 
501
          continue;
 
502
      }
 
503
 
 
504
      // If we make it to here then either the ranges didn't overlap, or they
 
505
      // did, but none of their definitions would prevent us from coalescing.
 
506
      // We're good to go with the coalesce.
 
507
 
 
508
      float cBenefit = std::pow(10.0f, (float)loopInfo->getLoopDepth(mbb)) / 5.0;
 
509
 
 
510
      coalescesFound[RegPair(srcReg, dstReg)] = cBenefit;
 
511
      coalescesFound[RegPair(dstReg, srcReg)] = cBenefit;
 
512
    }
 
513
 
 
514
  }
 
515
 
 
516
  return coalescesFound;
 
517
}
 
518
 
 
519
void PBQPRegAlloc::findVRegIntervalsToAlloc() {
 
520
 
 
521
  // Iterate over all live ranges.
 
522
  for (LiveIntervals::iterator itr = lis->begin(), end = lis->end();
 
523
       itr != end; ++itr) {
 
524
 
 
525
    // Ignore physical ones.
 
526
    if (TargetRegisterInfo::isPhysicalRegister(itr->first))
 
527
      continue;
 
528
 
 
529
    LiveInterval *li = itr->second;
 
530
 
 
531
    // If this live interval is non-empty we will use pbqp to allocate it.
 
532
    // Empty intervals we allocate in a simple post-processing stage in
 
533
    // finalizeAlloc.
 
534
    if (!li->empty()) {
 
535
      vregIntervalsToAlloc.insert(li);
 
536
    }
 
537
    else {
 
538
      emptyVRegIntervals.insert(li);
 
539
    }
 
540
  }
 
541
}
 
542
 
 
543
PBQP::Graph PBQPRegAlloc::constructPBQPProblem() {
 
544
 
 
545
  typedef std::vector<const LiveInterval*> LIVector;
 
546
  typedef std::vector<unsigned> RegVector;
 
547
 
 
548
  // This will store the physical intervals for easy reference.
 
549
  LIVector physIntervals;
 
550
 
 
551
  // Start by clearing the old node <-> live interval mappings & allowed sets
 
552
  li2Node.clear();
 
553
  node2LI.clear();
 
554
  allowedSets.clear();
 
555
 
 
556
  // Populate physIntervals, update preg use:
 
557
  for (LiveIntervals::iterator itr = lis->begin(), end = lis->end();
 
558
       itr != end; ++itr) {
 
559
 
 
560
    if (TargetRegisterInfo::isPhysicalRegister(itr->first)) {
 
561
      physIntervals.push_back(itr->second);
 
562
      mri->setPhysRegUsed(itr->second->reg);
 
563
    }
 
564
  }
 
565
 
 
566
  // Iterate over vreg intervals, construct live interval <-> node number
 
567
  //  mappings.
 
568
  for (LiveIntervalSet::const_iterator
 
569
       itr = vregIntervalsToAlloc.begin(), end = vregIntervalsToAlloc.end();
 
570
       itr != end; ++itr) {
 
571
    const LiveInterval *li = *itr;
 
572
 
 
573
    li2Node[li] = node2LI.size();
 
574
    node2LI.push_back(li);
 
575
  }
 
576
 
 
577
  // Get the set of potential coalesces.
 
578
  CoalesceMap coalesces;
 
579
 
 
580
  if (pbqpCoalescing) {
 
581
    coalesces = findCoalesces();
 
582
  }
 
583
 
 
584
  // Construct a PBQP solver for this problem
 
585
  PBQP::Graph problem;
 
586
  problemNodes.resize(vregIntervalsToAlloc.size());
 
587
 
 
588
  // Resize allowedSets container appropriately.
 
589
  allowedSets.resize(vregIntervalsToAlloc.size());
 
590
 
 
591
  BitVector ReservedRegs = tri->getReservedRegs(*mf);
 
592
 
 
593
  // Iterate over virtual register intervals to compute allowed sets...
 
594
  for (unsigned node = 0; node < node2LI.size(); ++node) {
 
595
 
 
596
    // Grab pointers to the interval and its register class.
 
597
    const LiveInterval *li = node2LI[node];
 
598
    const TargetRegisterClass *liRC = mri->getRegClass(li->reg);
 
599
 
 
600
    // Start by assuming all allocable registers in the class are allowed...
 
601
    RegVector liAllowed;
 
602
    TargetRegisterClass::iterator aob = liRC->allocation_order_begin(*mf);
 
603
    TargetRegisterClass::iterator aoe = liRC->allocation_order_end(*mf);
 
604
    for (TargetRegisterClass::iterator it = aob; it != aoe; ++it)
 
605
      if (!ReservedRegs.test(*it))
 
606
        liAllowed.push_back(*it);
 
607
 
 
608
    // Eliminate the physical registers which overlap with this range, along
 
609
    // with all their aliases.
 
610
    for (LIVector::iterator pItr = physIntervals.begin(),
 
611
       pEnd = physIntervals.end(); pItr != pEnd; ++pItr) {
 
612
 
 
613
      if (!li->overlaps(**pItr))
 
614
        continue;
 
615
 
 
616
      unsigned pReg = (*pItr)->reg;
 
617
 
 
618
      // If we get here then the live intervals overlap, but we're still ok
 
619
      // if they're coalescable.
 
620
      if (coalesces.find(RegPair(li->reg, pReg)) != coalesces.end())
 
621
        continue;
 
622
 
 
623
      // If we get here then we have a genuine exclusion.
 
624
 
 
625
      // Remove the overlapping reg...
 
626
      RegVector::iterator eraseItr =
 
627
        std::find(liAllowed.begin(), liAllowed.end(), pReg);
 
628
 
 
629
      if (eraseItr != liAllowed.end())
 
630
        liAllowed.erase(eraseItr);
 
631
 
 
632
      const unsigned *aliasItr = tri->getAliasSet(pReg);
 
633
 
 
634
      if (aliasItr != 0) {
 
635
        // ...and its aliases.
 
636
        for (; *aliasItr != 0; ++aliasItr) {
 
637
          RegVector::iterator eraseItr =
 
638
            std::find(liAllowed.begin(), liAllowed.end(), *aliasItr);
 
639
 
 
640
          if (eraseItr != liAllowed.end()) {
 
641
            liAllowed.erase(eraseItr);
 
642
          }
 
643
        }
 
644
      }
 
645
    }
 
646
 
 
647
    // Copy the allowed set into a member vector for use when constructing cost
 
648
    // vectors & matrices, and mapping PBQP solutions back to assignments.
 
649
    allowedSets[node] = AllowedSet(liAllowed.begin(), liAllowed.end());
 
650
 
 
651
    // Set the spill cost to the interval weight, or epsilon if the
 
652
    // interval weight is zero
 
653
    PBQP::PBQPNum spillCost = (li->weight != 0.0) ?
 
654
        li->weight : std::numeric_limits<PBQP::PBQPNum>::min();
 
655
 
 
656
    // Build a cost vector for this interval.
 
657
    problemNodes[node] =
 
658
      problem.addNode(
 
659
        buildCostVector(li->reg, allowedSets[node], coalesces, spillCost));
 
660
 
 
661
  }
 
662
 
 
663
 
 
664
  // Now add the cost matrices...
 
665
  for (unsigned node1 = 0; node1 < node2LI.size(); ++node1) {
 
666
    const LiveInterval *li = node2LI[node1];
 
667
 
 
668
    // Test for live range overlaps and insert interference matrices.
 
669
    for (unsigned node2 = node1 + 1; node2 < node2LI.size(); ++node2) {
 
670
      const LiveInterval *li2 = node2LI[node2];
 
671
 
 
672
      CoalesceMap::const_iterator cmItr =
 
673
        coalesces.find(RegPair(li->reg, li2->reg));
 
674
 
 
675
      PBQP::Matrix *m = 0;
 
676
 
 
677
      if (cmItr != coalesces.end()) {
 
678
        m = buildCoalescingMatrix(allowedSets[node1], allowedSets[node2],
 
679
                                  cmItr->second);
 
680
      }
 
681
      else if (li->overlaps(*li2)) {
 
682
        m = buildInterferenceMatrix(allowedSets[node1], allowedSets[node2]);
 
683
      }
 
684
 
 
685
      if (m != 0) {
 
686
        problem.addEdge(problemNodes[node1],
 
687
                        problemNodes[node2],
 
688
                        *m);
 
689
 
 
690
        delete m;
 
691
      }
 
692
    }
 
693
  }
 
694
 
 
695
  assert(problem.getNumNodes() == allowedSets.size());
 
696
/*
 
697
  std::cerr << "Allocating for " << problem.getNumNodes() << " nodes, "
 
698
            << problem.getNumEdges() << " edges.\n";
 
699
 
 
700
  problem.printDot(std::cerr);
 
701
*/
 
702
  // We're done, PBQP problem constructed - return it.
 
703
  return problem;
 
704
}
 
705
 
 
706
void PBQPRegAlloc::addStackInterval(const LiveInterval *spilled,
 
707
                                    MachineRegisterInfo* mri) {
 
708
  int stackSlot = vrm->getStackSlot(spilled->reg);
 
709
 
 
710
  if (stackSlot == VirtRegMap::NO_STACK_SLOT)
 
711
    return;
 
712
 
 
713
  const TargetRegisterClass *RC = mri->getRegClass(spilled->reg);
 
714
  LiveInterval &stackInterval = lss->getOrCreateInterval(stackSlot, RC);
 
715
 
 
716
  VNInfo *vni;
 
717
  if (stackInterval.getNumValNums() != 0)
 
718
    vni = stackInterval.getValNumInfo(0);
 
719
  else
 
720
    vni = stackInterval.getNextValue(
 
721
      SlotIndex(), 0, false, lss->getVNInfoAllocator());
 
722
 
 
723
  LiveInterval &rhsInterval = lis->getInterval(spilled->reg);
 
724
  stackInterval.MergeRangesInAsValue(rhsInterval, vni);
 
725
}
 
726
 
 
727
bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) {
 
728
 
 
729
  // Set to true if we have any spills
 
730
  bool anotherRoundNeeded = false;
 
731
 
 
732
  // Clear the existing allocation.
 
733
  vrm->clearAllVirt();
 
734
 
 
735
  // Iterate over the nodes mapping the PBQP solution to a register assignment.
 
736
  for (unsigned node = 0; node < node2LI.size(); ++node) {
 
737
    unsigned virtReg = node2LI[node]->reg,
 
738
             allocSelection = solution.getSelection(problemNodes[node]);
 
739
 
 
740
 
 
741
    // If the PBQP solution is non-zero it's a physical register...
 
742
    if (allocSelection != 0) {
 
743
      // Get the physical reg, subtracting 1 to account for the spill option.
 
744
      unsigned physReg = allowedSets[node][allocSelection - 1];
 
745
 
 
746
      DEBUG(dbgs() << "VREG " << virtReg << " -> "
 
747
                   << tri->getName(physReg) << "\n");
 
748
 
 
749
      assert(physReg != 0);
 
750
 
 
751
      // Add to the virt reg map and update the used phys regs.
 
752
      vrm->assignVirt2Phys(virtReg, physReg);
 
753
    }
 
754
    // ...Otherwise it's a spill.
 
755
    else {
 
756
 
 
757
      // Make sure we ignore this virtual reg on the next round
 
758
      // of allocation
 
759
      vregIntervalsToAlloc.erase(&lis->getInterval(virtReg));
 
760
 
 
761
      // Insert spill ranges for this live range
 
762
      const LiveInterval *spillInterval = node2LI[node];
 
763
      double oldSpillWeight = spillInterval->weight;
 
764
      SmallVector<LiveInterval*, 8> spillIs;
 
765
      rmf->rememberUseDefs(spillInterval);
 
766
      std::vector<LiveInterval*> newSpills =
 
767
        lis->addIntervalsForSpills(*spillInterval, spillIs, loopInfo, *vrm);
 
768
      addStackInterval(spillInterval, mri);
 
769
      rmf->rememberSpills(spillInterval, newSpills);
 
770
 
 
771
      (void) oldSpillWeight;
 
772
      DEBUG(dbgs() << "VREG " << virtReg << " -> SPILLED (Cost: "
 
773
                   << oldSpillWeight << ", New vregs: ");
 
774
 
 
775
      // Copy any newly inserted live intervals into the list of regs to
 
776
      // allocate.
 
777
      for (std::vector<LiveInterval*>::const_iterator
 
778
           itr = newSpills.begin(), end = newSpills.end();
 
779
           itr != end; ++itr) {
 
780
 
 
781
        assert(!(*itr)->empty() && "Empty spill range.");
 
782
 
 
783
        DEBUG(dbgs() << (*itr)->reg << " ");
 
784
 
 
785
        vregIntervalsToAlloc.insert(*itr);
 
786
      }
 
787
 
 
788
      DEBUG(dbgs() << ")\n");
 
789
 
 
790
      // We need another round if spill intervals were added.
 
791
      anotherRoundNeeded |= !newSpills.empty();
 
792
    }
 
793
  }
 
794
 
 
795
  return !anotherRoundNeeded;
 
796
}
 
797
 
 
798
void PBQPRegAlloc::finalizeAlloc() const {
 
799
  typedef LiveIntervals::iterator LIIterator;
 
800
  typedef LiveInterval::Ranges::const_iterator LRIterator;
 
801
 
 
802
  // First allocate registers for the empty intervals.
 
803
  for (LiveIntervalSet::const_iterator
 
804
         itr = emptyVRegIntervals.begin(), end = emptyVRegIntervals.end();
 
805
         itr != end; ++itr) {
 
806
    LiveInterval *li = *itr;
 
807
 
 
808
    unsigned physReg = vrm->getRegAllocPref(li->reg);
 
809
 
 
810
    if (physReg == 0) {
 
811
      const TargetRegisterClass *liRC = mri->getRegClass(li->reg);
 
812
      physReg = *liRC->allocation_order_begin(*mf);
 
813
    }
 
814
 
 
815
    vrm->assignVirt2Phys(li->reg, physReg);
 
816
  }
 
817
 
 
818
  // Finally iterate over the basic blocks to compute and set the live-in sets.
 
819
  SmallVector<MachineBasicBlock*, 8> liveInMBBs;
 
820
  MachineBasicBlock *entryMBB = &*mf->begin();
 
821
 
 
822
  for (LIIterator liItr = lis->begin(), liEnd = lis->end();
 
823
       liItr != liEnd; ++liItr) {
 
824
 
 
825
    const LiveInterval *li = liItr->second;
 
826
    unsigned reg = 0;
 
827
 
 
828
    // Get the physical register for this interval
 
829
    if (TargetRegisterInfo::isPhysicalRegister(li->reg)) {
 
830
      reg = li->reg;
 
831
    }
 
832
    else if (vrm->isAssignedReg(li->reg)) {
 
833
      reg = vrm->getPhys(li->reg);
 
834
    }
 
835
    else {
 
836
      // Ranges which are assigned a stack slot only are ignored.
 
837
      continue;
 
838
    }
 
839
 
 
840
    if (reg == 0) {
 
841
      // Filter out zero regs - they're for intervals that were spilled.
 
842
      continue;
 
843
    }
 
844
 
 
845
    // Iterate over the ranges of the current interval...
 
846
    for (LRIterator lrItr = li->begin(), lrEnd = li->end();
 
847
         lrItr != lrEnd; ++lrItr) {
 
848
 
 
849
      // Find the set of basic blocks which this range is live into...
 
850
      if (lis->findLiveInMBBs(lrItr->start, lrItr->end,  liveInMBBs)) {
 
851
        // And add the physreg for this interval to their live-in sets.
 
852
        for (unsigned i = 0; i < liveInMBBs.size(); ++i) {
 
853
          if (liveInMBBs[i] != entryMBB) {
 
854
            if (!liveInMBBs[i]->isLiveIn(reg)) {
 
855
              liveInMBBs[i]->addLiveIn(reg);
 
856
            }
 
857
          }
 
858
        }
 
859
        liveInMBBs.clear();
 
860
      }
 
861
    }
 
862
  }
 
863
 
 
864
}
 
865
 
 
866
bool PBQPRegAlloc::runOnMachineFunction(MachineFunction &MF) {
 
867
 
 
868
  mf = &MF;
 
869
  tm = &mf->getTarget();
 
870
  tri = tm->getRegisterInfo();
 
871
  tii = tm->getInstrInfo();
 
872
  mri = &mf->getRegInfo(); 
 
873
 
 
874
  lis = &getAnalysis<LiveIntervals>();
 
875
  lss = &getAnalysis<LiveStacks>();
 
876
  loopInfo = &getAnalysis<MachineLoopInfo>();
 
877
  rmf = &getAnalysis<RenderMachineFunction>();
 
878
 
 
879
  vrm = &getAnalysis<VirtRegMap>();
 
880
 
 
881
 
 
882
  DEBUG(dbgs() << "PBQP Register Allocating for " << mf->getFunction()->getName() << "\n");
 
883
 
 
884
  // Allocator main loop:
 
885
  //
 
886
  // * Map current regalloc problem to a PBQP problem
 
887
  // * Solve the PBQP problem
 
888
  // * Map the solution back to a register allocation
 
889
  // * Spill if necessary
 
890
  //
 
891
  // This process is continued till no more spills are generated.
 
892
 
 
893
  // Find the vreg intervals in need of allocation.
 
894
  findVRegIntervalsToAlloc();
 
895
 
 
896
  // If there are non-empty intervals allocate them using pbqp.
 
897
  if (!vregIntervalsToAlloc.empty()) {
 
898
 
 
899
    bool pbqpAllocComplete = false;
 
900
    unsigned round = 0;
 
901
 
 
902
    while (!pbqpAllocComplete) {
 
903
      DEBUG(dbgs() << "  PBQP Regalloc round " << round << ":\n");
 
904
 
 
905
      PBQP::Graph problem = constructPBQPProblem();
 
906
      PBQP::Solution solution =
 
907
        PBQP::HeuristicSolver<PBQP::Heuristics::Briggs>::solve(problem);
 
908
 
 
909
      pbqpAllocComplete = mapPBQPToRegAlloc(solution);
 
910
 
 
911
      ++round;
 
912
    }
 
913
  }
 
914
 
 
915
  // Finalise allocation, allocate empty ranges.
 
916
  finalizeAlloc();
 
917
 
 
918
  rmf->renderMachineFunction("After PBQP register allocation.", vrm);
 
919
 
 
920
  vregIntervalsToAlloc.clear();
 
921
  emptyVRegIntervals.clear();
 
922
  li2Node.clear();
 
923
  node2LI.clear();
 
924
  allowedSets.clear();
 
925
  problemNodes.clear();
 
926
 
 
927
  DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm << "\n");
 
928
 
 
929
  // Run rewriter
 
930
  std::auto_ptr<VirtRegRewriter> rewriter(createVirtRegRewriter());
 
931
 
 
932
  rewriter->runOnMachineFunction(*mf, *vrm, lis);
 
933
 
 
934
  return true;
 
935
}
 
936
 
 
937
FunctionPass* llvm::createPBQPRegisterAllocator() {
 
938
  return new PBQPRegAlloc();
 
939
}
 
940
 
 
941
 
 
942
#undef DEBUG_TYPE