LCOV - code coverage report
Current view: top level - include/llvm/CodeGen - LiveIntervalUnion.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 24 24 100.0 %
Date: 2017-09-14 15:23:50 Functions: 1 1 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- LiveIntervalUnion.h - Live interval union data struct ---*- 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             : // LiveIntervalUnion is a union of live segments across multiple live virtual
      11             : // registers. This may be used during coalescing to represent a congruence
      12             : // class, or during register allocation to model liveness of a physical
      13             : // register.
      14             : //
      15             : //===----------------------------------------------------------------------===//
      16             : 
      17             : #ifndef LLVM_CODEGEN_LIVEINTERVALUNION_H
      18             : #define LLVM_CODEGEN_LIVEINTERVALUNION_H
      19             : 
      20             : #include "llvm/ADT/IntervalMap.h"
      21             : #include "llvm/ADT/SmallVector.h"
      22             : #include "llvm/CodeGen/LiveInterval.h"
      23             : #include "llvm/CodeGen/SlotIndexes.h"
      24             : #include <cassert>
      25             : #include <limits>
      26             : 
      27             : namespace llvm {
      28             : 
      29             : class raw_ostream;
      30             : class TargetRegisterInfo;
      31             : 
      32             : #ifndef NDEBUG
      33             : // forward declaration
      34             : template <unsigned Element> class SparseBitVector;
      35             : 
      36             : using LiveVirtRegBitSet = SparseBitVector<128>;
      37             : #endif
      38             : 
      39             : /// Union of live intervals that are strong candidates for coalescing into a
      40             : /// single register (either physical or virtual depending on the context).  We
      41             : /// expect the constituent live intervals to be disjoint, although we may
      42             : /// eventually make exceptions to handle value-based interference.
      43     9274404 : class LiveIntervalUnion {
      44             :   // A set of live virtual register segments that supports fast insertion,
      45             :   // intersection, and removal.
      46             :   // Mapping SlotIndex intervals to virtual register numbers.
      47             :   using LiveSegments = IntervalMap<SlotIndex, LiveInterval*>;
      48             : 
      49             : public:
      50             :   // SegmentIter can advance to the next segment ordered by starting position
      51             :   // which may belong to a different live virtual register. We also must be able
      52             :   // to reach the current segment's containing virtual register.
      53             :   using SegmentIter = LiveSegments::iterator;
      54             : 
      55             :   /// Const version of SegmentIter.
      56             :   using ConstSegmentIter = LiveSegments::const_iterator;
      57             : 
      58             :   // LiveIntervalUnions share an external allocator.
      59             :   using Allocator = LiveSegments::Allocator;
      60             : 
      61             : private:
      62             :   unsigned Tag = 0;       // unique tag for current contents.
      63             :   LiveSegments Segments;  // union of virtual reg segments
      64             : 
      65             : public:
      66     4640876 :   explicit LiveIntervalUnion(Allocator &a) : Segments(a) {}
      67             : 
      68             :   // Iterate over all segments in the union of live virtual registers ordered
      69             :   // by their starting position.
      70             :   SegmentIter begin() { return Segments.begin(); }
      71             :   SegmentIter end() { return Segments.end(); }
      72      169056 :   SegmentIter find(SlotIndex x) { return Segments.find(x); }
      73             :   ConstSegmentIter begin() const { return Segments.begin(); }
      74             :   ConstSegmentIter end() const { return Segments.end(); }
      75             :   ConstSegmentIter find(SlotIndex x) const { return Segments.find(x); }
      76             : 
      77    19444119 :   bool empty() const { return Segments.empty(); }
      78             :   SlotIndex startIndex() const { return Segments.start(); }
      79             : 
      80             :   // Provide public access to the underlying map to allow overlap iteration.
      81             :   using Map = LiveSegments;
      82    18668199 :   const Map &getMap() const { return Segments; }
      83             : 
      84             :   /// getTag - Return an opaque tag representing the current state of the union.
      85             :   unsigned getTag() const { return Tag; }
      86             : 
      87             :   /// changedSince - Return true if the union change since getTag returned tag.
      88             :   bool changedSince(unsigned tag) const { return tag != Tag; }
      89             : 
      90             :   // Add a live virtual register to this union and merge its segments.
      91             :   void unify(LiveInterval &VirtReg, const LiveRange &Range);
      92             : 
      93             :   // Remove a live virtual register's segments from this union.
      94             :   void extract(LiveInterval &VirtReg, const LiveRange &Range);
      95             : 
      96             :   // Remove all inserted virtual registers.
      97    45161826 :   void clear() { Segments.clear(); ++Tag; }
      98             : 
      99             :   // Print union, using TRI to translate register names
     100             :   void print(raw_ostream &OS, const TargetRegisterInfo *TRI) const;
     101             : 
     102             : #ifndef NDEBUG
     103             :   // Verify the live intervals in this union and add them to the visited set.
     104             :   void verify(LiveVirtRegBitSet& VisitedVRegs);
     105             : #endif
     106             : 
     107             :   /// Query interferences between a single live virtual register and a live
     108             :   /// interval union.
     109    58676835 :   class Query {
     110             :     const LiveIntervalUnion *LiveUnion = nullptr;
     111             :     const LiveRange *LR = nullptr;
     112             :     LiveRange::const_iterator LRI;  ///< current position in LR
     113             :     ConstSegmentIter LiveUnionI;    ///< current position in LiveUnion
     114             :     SmallVector<LiveInterval*,4> InterferingVRegs;
     115             :     bool CheckedFirstInterference = false;
     116             :     bool SeenAllInterferences = false;
     117             :     unsigned Tag = 0;
     118             :     unsigned UserTag = 0;
     119             : 
     120             :     void reset(unsigned NewUserTag, const LiveRange &NewLR,
     121             :                const LiveIntervalUnion &NewLiveUnion) {
     122     4470657 :       LiveUnion = &NewLiveUnion;
     123     4470657 :       LR = &NewLR;
     124     8941314 :       InterferingVRegs.clear();
     125     4470657 :       CheckedFirstInterference = false;
     126     4470657 :       SeenAllInterferences = false;
     127     4470657 :       Tag = NewLiveUnion.getTag();
     128     4470657 :       UserTag = NewUserTag;
     129             :     }
     130             : 
     131             :   public:
     132    13922235 :     Query() = default;
     133    14921865 :     Query(const LiveRange &LR, const LiveIntervalUnion &LIU):
     134    44765595 :       LiveUnion(&LIU), LR(&LR) {}
     135             :     Query(const Query &) = delete;
     136             :     Query &operator=(const Query &) = delete;
     137             : 
     138             :     void init(unsigned NewUserTag, const LiveRange &NewLR,
     139             :               const LiveIntervalUnion &NewLiveUnion) {
     140     7459924 :       if (UserTag == NewUserTag && LR == &NewLR && LiveUnion == &NewLiveUnion &&
     141     1494635 :           !NewLiveUnion.changedSince(Tag)) {
     142             :         // Retain cached results, e.g. firstInterference.
     143             :         return;
     144             :       }
     145             :       reset(NewUserTag, NewLR, NewLiveUnion);
     146             :     }
     147             : 
     148             :     // Does this live virtual register interfere with the union?
     149    19990691 :     bool checkInterference() { return collectInterferingVRegs(1); }
     150             : 
     151             :     // Count the virtual registers in this union that interfere with this
     152             :     // query's live virtual register, up to maxInterferingRegs.
     153             :     unsigned collectInterferingVRegs(
     154             :         unsigned MaxInterferingRegs = std::numeric_limits<unsigned>::max());
     155             : 
     156             :     // Was this virtual register visited during collectInterferingVRegs?
     157             :     bool isSeenInterference(LiveInterval *VReg) const;
     158             : 
     159             :     // Did collectInterferingVRegs collect all interferences?
     160             :     bool seenAllInterferences() const { return SeenAllInterferences; }
     161             : 
     162             :     // Vector generated by collectInterferingVRegs.
     163             :     const SmallVectorImpl<LiveInterval*> &interferingVRegs() const {
     164             :       return InterferingVRegs;
     165             :     }
     166             :   };
     167             : 
     168             :   // Array of LiveIntervalUnions.
     169             :   class Array {
     170             :     unsigned Size = 0;
     171             :     LiveIntervalUnion *LIUs = nullptr;
     172             : 
     173             :   public:
     174       15349 :     Array() = default;
     175       15257 :     ~Array() { clear(); }
     176             : 
     177             :     // Initialize the array to have Size entries.
     178             :     // Reuse an existing allocation if the size matches.
     179             :     void init(LiveIntervalUnion::Allocator&, unsigned Size);
     180             : 
     181             :     unsigned size() const { return Size; }
     182             : 
     183             :     void clear();
     184             : 
     185             :     LiveIntervalUnion& operator[](unsigned idx) {
     186             :       assert(idx <  Size && "idx out of bounds");
     187    52803169 :       return LIUs[idx];
     188             :     }
     189             : 
     190             :     const LiveIntervalUnion& operator[](unsigned Idx) const {
     191             :       assert(Idx < Size && "Idx out of bounds");
     192       51597 :       return LIUs[Idx];
     193             :     }
     194             :   };
     195             : };
     196             : 
     197             : } // end namespace llvm
     198             : 
     199             : #endif // LLVM_CODEGEN_LIVEINTERVALUNION_H

Generated by: LCOV version 1.13