← Back to branch summary

~ubuntu-branches/ubuntu/natty/clamav/natty-proposed

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/include/llvm/CodeGen/LiveInterval.h

  • Committer: Bazaar Package Importer
  • Author(s): Scott Kitterman
  • Date: 2010-12-02 21:04:10 UTC
  • mfrom: (0.35.17 sid)
  • Revision ID: james.westby@ubuntu.com-20101202210410-ppgyckmylngsfa8o
Tags: 0.96.5+dfsg-1ubuntu1
* Merge from debian unstable.  Remaining changes:
  - Drop initial signature definitions from clamav-base
  - Drop build-dep on electric-fence (in Universe)
  - Add apparmor profiles for clamd and freshclam along with maintainer
    script changes

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/include/llvm/CodeGen/LiveInterval.h
39
39
  /// This class holds information about a machine level values, including
40
40
  /// definition and use points.
41
41
  ///
42
 
  /// Care must be taken in interpreting the def index of the value. The 
 
42
  /// Care must be taken in interpreting the def index of the value. The
43
43
  /// following rules apply:
44
44
  ///
45
45
  /// If the isDefAccurate() method returns false then def does not contain the
53
53
  class VNInfo {
54
54
  private:
55
55
    enum {
56
 
      HAS_PHI_KILL    = 1,                         
 
56
      HAS_PHI_KILL    = 1,
57
57
      REDEF_BY_EC     = 1 << 1,
58
58
      IS_PHI_DEF      = 1 << 2,
59
59
      IS_UNUSED       = 1 << 3,
67
67
    } cr;
68
68
 
69
69
  public:
70
 
 
71
 
    typedef SmallVector<SlotIndex, 4> KillSet;
 
70
    typedef BumpPtrAllocator Allocator;
72
71
 
73
72
    /// The ID number of this value.
74
73
    unsigned id;
75
 
    
 
74
 
76
75
    /// The index of the defining instruction (if isDefAccurate() returns true).
77
76
    SlotIndex def;
78
77
 
79
 
    KillSet kills;
80
 
 
81
 
    /*
82
 
    VNInfo(LiveIntervals &li_)
83
 
      : defflags(IS_UNUSED), id(~1U) { cr.copy = 0; }
84
 
    */
85
 
 
86
78
    /// VNInfo constructor.
87
79
    /// d is presumed to point to the actual defining instr. If it doesn't
88
80
    /// setIsDefAccurate(false) should be called after construction.
91
83
 
92
84
    /// VNInfo construtor, copies values from orig, except for the value number.
93
85
    VNInfo(unsigned i, const VNInfo &orig)
94
 
      : flags(orig.flags), cr(orig.cr), id(i), def(orig.def), kills(orig.kills)
 
86
      : flags(orig.flags), cr(orig.cr), id(i), def(orig.def)
95
87
    { }
96
88
 
97
89
    /// Copy from the parameter into this VNInfo.
99
91
      flags = src.flags;
100
92
      cr = src.cr;
101
93
      def = src.def;
102
 
      kills = src.kills;
103
94
    }
104
95
 
105
96
    /// Used for copying value number info.
114
105
    /// This method should not be called on stack intervals as it may lead to
115
106
    /// undefined behavior.
116
107
    void setCopy(MachineInstr *c) { cr.copy = c; }
117
 
    
 
108
 
118
109
    /// For a stack interval, returns the reg which this stack interval was
119
110
    /// defined from.
120
 
    /// For a register interval the behaviour of this method is undefined. 
 
111
    /// For a register interval the behaviour of this method is undefined.
121
112
    unsigned getReg() const { return cr.reg; }
122
113
    /// For a stack interval, set the defining register.
123
114
    /// This method should not be called on register intervals as it may lead
144
135
      else
145
136
        flags &= ~REDEF_BY_EC;
146
137
    }
147
 
   
 
138
 
148
139
    /// Returns true if this value is defined by a PHI instruction (or was,
149
140
    /// PHI instrucions may have been eliminated).
150
141
    bool isPHIDef() const { return flags & IS_PHI_DEF; }
172
163
    void setIsDefAccurate(bool defAccurate) {
173
164
      if (defAccurate)
174
165
        flags |= IS_DEF_ACCURATE;
175
 
      else 
 
166
      else
176
167
        flags &= ~IS_DEF_ACCURATE;
177
168
    }
178
 
 
179
 
    /// Returns true if the given index is a kill of this value.
180
 
    bool isKill(SlotIndex k) const {
181
 
      KillSet::const_iterator
182
 
        i = std::lower_bound(kills.begin(), kills.end(), k);
183
 
      return (i != kills.end() && *i == k);
184
 
    }
185
 
 
186
 
    /// addKill - Add a kill instruction index to the specified value
187
 
    /// number.
188
 
    void addKill(SlotIndex k) {
189
 
      if (kills.empty()) {
190
 
        kills.push_back(k);
191
 
      } else {
192
 
        KillSet::iterator
193
 
          i = std::lower_bound(kills.begin(), kills.end(), k);
194
 
        kills.insert(i, k);
195
 
      }
196
 
    }
197
 
 
198
 
    /// Remove the specified kill index from this value's kills list.
199
 
    /// Returns true if the value was present, otherwise returns false.
200
 
    bool removeKill(SlotIndex k) {
201
 
      KillSet::iterator i = std::lower_bound(kills.begin(), kills.end(), k);
202
 
      if (i != kills.end() && *i == k) {
203
 
        kills.erase(i);
204
 
        return true;
205
 
      }
206
 
      return false;
207
 
    }
208
 
 
209
 
    /// Remove all kills in the range [s, e).
210
 
    void removeKills(SlotIndex s, SlotIndex e) {
211
 
      KillSet::iterator
212
 
        si = std::lower_bound(kills.begin(), kills.end(), s),
213
 
        se = std::upper_bound(kills.begin(), kills.end(), e);
214
 
 
215
 
      kills.erase(si, se);
216
 
    }
217
 
 
218
169
  };
219
170
 
220
171
  /// LiveRange structure - This represents a simple register range in the
238
189
    }
239
190
 
240
191
    /// containsRange - Return true if the given range, [S, E), is covered by
241
 
    /// this range. 
 
192
    /// this range.
242
193
    bool containsRange(SlotIndex S, SlotIndex E) const {
243
194
      assert((S < E) && "Backwards interval?");
244
195
      return (start <= S && S < end) && (start < E && E <= end);
258
209
    LiveRange(); // DO NOT IMPLEMENT
259
210
  };
260
211
 
 
212
  template <> struct isPodLike<LiveRange> { static const bool value = true; };
 
213
 
261
214
  raw_ostream& operator<<(raw_ostream& os, const LiveRange &LR);
262
215
 
263
216
 
283
236
    float weight;        // weight of this interval
284
237
    Ranges ranges;       // the ranges in which this register is live
285
238
    VNInfoList valnos;   // value#'s
286
 
    
 
239
 
287
240
    struct InstrSlots {
288
241
      enum {
289
242
        LOAD  = 0,
328
281
      while (I->end <= Pos) ++I;
329
282
      return I;
330
283
    }
331
 
    
 
284
 
332
285
    void clear() {
333
286
      valnos.clear();
334
287
      ranges.clear();
352
305
    bool containsOneValue() const { return valnos.size() == 1; }
353
306
 
354
307
    unsigned getNumValNums() const { return (unsigned)valnos.size(); }
355
 
    
 
308
 
356
309
    /// getValNumInfo - Returns pointer to the specified val#.
357
310
    ///
358
311
    inline VNInfo *getValNumInfo(unsigned ValNo) {
365
318
    /// getNextValue - Create a new value number and return it.  MIIdx specifies
366
319
    /// the instruction that defines the value number.
367
320
    VNInfo *getNextValue(SlotIndex def, MachineInstr *CopyMI,
368
 
                         bool isDefAccurate, BumpPtrAllocator &VNInfoAllocator){
 
321
                       bool isDefAccurate, VNInfo::Allocator &VNInfoAllocator) {
369
322
      VNInfo *VNI =
370
 
        static_cast<VNInfo*>(VNInfoAllocator.Allocate((unsigned)sizeof(VNInfo),
371
 
                                                      alignof<VNInfo>()));
372
 
      new (VNI) VNInfo((unsigned)valnos.size(), def, CopyMI);
 
323
        new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), def, CopyMI);
373
324
      VNI->setIsDefAccurate(isDefAccurate);
374
325
      valnos.push_back(VNI);
375
326
      return VNI;
378
329
    /// Create a copy of the given value. The new value will be identical except
379
330
    /// for the Value number.
380
331
    VNInfo *createValueCopy(const VNInfo *orig,
381
 
                            BumpPtrAllocator &VNInfoAllocator) {
 
332
                            VNInfo::Allocator &VNInfoAllocator) {
382
333
      VNInfo *VNI =
383
 
        static_cast<VNInfo*>(VNInfoAllocator.Allocate((unsigned)sizeof(VNInfo),
384
 
                                                      alignof<VNInfo>()));
385
 
    
386
 
      new (VNI) VNInfo((unsigned)valnos.size(), *orig);
 
334
        new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), *orig);
387
335
      valnos.push_back(VNI);
388
336
      return VNI;
389
337
    }
390
338
 
391
 
    /// addKills - Add a number of kills into the VNInfo kill vector. If this
392
 
    /// interval is live at a kill point, then the kill is not added.
393
 
    void addKills(VNInfo *VNI, const VNInfo::KillSet &kills) {
394
 
      for (unsigned i = 0, e = static_cast<unsigned>(kills.size());
395
 
           i != e; ++i) {
396
 
        if (!liveBeforeAndAt(kills[i])) {
397
 
          VNI->addKill(kills[i]);
398
 
        }
399
 
      }
400
 
    }
 
339
    /// RenumberValues - Renumber all values in order of appearance and remove
 
340
    /// unused values.
 
341
    /// Recalculate phi-kill flags in case any phi-def values were removed.
 
342
    void RenumberValues(LiveIntervals &lis);
401
343
 
402
344
    /// isOnlyLROfValNo - Return true if the specified live range is the only
403
345
    /// one defined by the its val#.
409
351
      }
410
352
      return true;
411
353
    }
412
 
    
 
354
 
413
355
    /// MergeValueNumberInto - This method is called when two value nubmers
414
356
    /// are found to be equivalent.  This eliminates V1, replacing all
415
357
    /// LiveRanges with the V1 value number with the V2 value number.  This can
422
364
    /// VNInfoAllocator since it will create a new val#.
423
365
    void MergeInClobberRanges(LiveIntervals &li_,
424
366
                              const LiveInterval &Clobbers,
425
 
                              BumpPtrAllocator &VNInfoAllocator);
 
367
                              VNInfo::Allocator &VNInfoAllocator);
426
368
 
427
369
    /// MergeInClobberRange - Same as MergeInClobberRanges except it merge in a
428
370
    /// single LiveRange only.
429
371
    void MergeInClobberRange(LiveIntervals &li_,
430
372
                             SlotIndex Start,
431
373
                             SlotIndex End,
432
 
                             BumpPtrAllocator &VNInfoAllocator);
 
374
                             VNInfo::Allocator &VNInfoAllocator);
433
375
 
434
376
    /// MergeValueInAsValue - Merge all of the live ranges of a specific val#
435
377
    /// in RHS into this live interval as the specified value number.
449
391
    /// Copy - Copy the specified live interval. This copies all the fields
450
392
    /// except for the register of the interval.
451
393
    void Copy(const LiveInterval &RHS, MachineRegisterInfo *MRI,
452
 
              BumpPtrAllocator &VNInfoAllocator);
453
 
    
 
394
              VNInfo::Allocator &VNInfoAllocator);
 
395
 
454
396
    bool empty() const { return ranges.empty(); }
455
397
 
456
398
    /// beginIndex - Return the lowest numbered slot covered by interval.
477
419
    // range.If it does, then check if the previous live range ends at index-1.
478
420
    bool liveBeforeAndAt(SlotIndex index) const;
479
421
 
 
422
    /// killedAt - Return true if a live range ends at index. Note that the kill
 
423
    /// point is not contained in the half-open live range. It is usually the
 
424
    /// getDefIndex() slot following its last use.
 
425
    bool killedAt(SlotIndex index) const;
 
426
 
 
427
    /// killedInRange - Return true if the interval has kills in [Start,End).
 
428
    /// Note that the kill point is considered the end of a live range, so it is
 
429
    /// not contained in the live range. If a live range ends at End, it won't
 
430
    /// be counted as a kill by this method.
 
431
    bool killedInRange(SlotIndex Start, SlotIndex End) const;
 
432
 
480
433
    /// getLiveRangeContaining - Return the live range that contains the
481
434
    /// specified index, or null if there is none.
482
435
    const LiveRange *getLiveRangeContaining(SlotIndex Idx) const {
491
444
      return I == end() ? 0 : &*I;
492
445
    }
493
446
 
 
447
    /// getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.
 
448
    VNInfo *getVNInfoAt(SlotIndex Idx) const {
 
449
      const_iterator I = FindLiveRangeContaining(Idx);
 
450
      return I == end() ? 0 : I->valno;
 
451
    }
 
452
 
494
453
    /// FindLiveRangeContaining - Return an iterator to the live range that
495
454
    /// contains the specified index, or end() if there is none.
496
455
    const_iterator FindLiveRangeContaining(SlotIndex Idx) const;
500
459
    iterator FindLiveRangeContaining(SlotIndex Idx);
501
460
 
502
461
    /// findDefinedVNInfo - Find the by the specified
503
 
    /// index (register interval) or defined 
 
462
    /// index (register interval) or defined
504
463
    VNInfo *findDefinedVNInfoForRegInt(SlotIndex Idx) const;
505
464
 
506
465
    /// findDefinedVNInfo - Find the VNInfo that's defined by the specified
507
466
    /// register (stack inteval only).
508
467
    VNInfo *findDefinedVNInfoForStackInt(unsigned Reg) const;
509
468
 
510
 
    
 
469
 
511
470
    /// overlaps - Return true if the intersection of the two live intervals is
512
471
    /// not empty.
513
472
    bool overlaps(const LiveInterval& other) const {
 
473
      if (other.empty())
 
474
        return false;
514
475
      return overlapsFrom(other, other.begin());
515
476
    }
516
477
 
556
517
    /// Also remove the value# from value# list.
557
518
    void removeValNo(VNInfo *ValNo);
558
519
 
559
 
    /// scaleNumbering - Renumber VNI and ranges to provide gaps for new
560
 
    /// instructions.
561
 
    void scaleNumbering(unsigned factor);
562
 
 
563
520
    /// getSize - Returns the sum of sizes of all the LiveRange's.
564
521
    ///
565
522
    unsigned getSize() const;
566
523
 
 
524
    /// Returns true if the live interval is zero length, i.e. no live ranges
 
525
    /// span instructions. It doesn't pay to spill such an interval.
 
526
    bool isZeroLength() const {
 
527
      for (const_iterator i = begin(), e = end(); i != e; ++i)
 
528
        if (i->end.getPrevIndex() > i->start)
 
529
          return false;
 
530
      return true;
 
531
    }
 
532
 
567
533
    /// isSpillable - Can this interval be spilled?
568
534
    bool isSpillable() const {
569
535
      return weight != HUGE_VALF;
593
559
    Ranges::iterator addRangeFrom(LiveRange LR, Ranges::iterator From);
594
560
    void extendIntervalEndTo(Ranges::iterator I, SlotIndex NewEnd);
595
561
    Ranges::iterator extendIntervalStartTo(Ranges::iterator I, SlotIndex NewStr);
 
562
    void markValNoForDeletion(VNInfo *V);
596
563
 
597
564
    LiveInterval& operator=(const LiveInterval& rhs); // DO NOT IMPLEMENT
598
565