LCOV - code coverage report
Current view: top level - lib/CodeGen - LiveIntervalUnion.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 75 82 91.5 %
Date: 2017-09-14 15:23:50 Functions: 6 7 85.7 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- LiveIntervalUnion.cpp - Live interval union data structure ---------===//
       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 represents a coalesced set of live intervals. This may be
      11             : // used during coalescing to represent a congruence class, or during register
      12             : // allocation to model liveness of a physical register.
      13             : //
      14             : //===----------------------------------------------------------------------===//
      15             : 
      16             : #include "llvm/CodeGen/LiveIntervalUnion.h"
      17             : #include "llvm/ADT/STLExtras.h"
      18             : #include "llvm/ADT/SparseBitVector.h"
      19             : #include "llvm/CodeGen/LiveInterval.h"
      20             : #include "llvm/Support/raw_ostream.h"
      21             : #include "llvm/Target/TargetRegisterInfo.h"
      22             : #include <cassert>
      23             : #include <cstdlib>
      24             : 
      25             : using namespace llvm;
      26             : 
      27             : #define DEBUG_TYPE "regalloc"
      28             : 
      29             : // Merge a LiveInterval's segments. Guarantee no overlaps.
      30     1619611 : void LiveIntervalUnion::unify(LiveInterval &VirtReg, const LiveRange &Range) {
      31     1619611 :   if (Range.empty())
      32      378741 :     return;
      33     1610328 :   ++Tag;
      34             : 
      35             :   // Insert each of the virtual register's live segments into the map.
      36     1610328 :   LiveRange::const_iterator RegPos = Range.begin();
      37     1610328 :   LiveRange::const_iterator RegEnd = Range.end();
      38     2851198 :   SegmentIter SegPos = Segments.find(RegPos->start);
      39             : 
      40      804016 :   while (SegPos.valid()) {
      41      586737 :     SegPos.insert(RegPos->start, RegPos->end, &VirtReg);
      42      586737 :     if (++RegPos == RegEnd)
      43             :       return;
      44      217279 :     SegPos.advanceTo(RegPos->start);
      45             :   }
      46             : 
      47             :   // We have reached the end of Segments, so it is no longer necessary to search
      48             :   // for the insertion position.
      49             :   // It is faster to insert the end first.
      50     1240870 :   --RegEnd;
      51     1240870 :   SegPos.insert(RegEnd->start, RegEnd->end, &VirtReg);
      52     2012030 :   for (; RegPos != RegEnd; ++RegPos, ++SegPos)
      53      385580 :     SegPos.insert(RegPos->start, RegPos->end, &VirtReg);
      54             : }
      55             : 
      56             : // Remove a live virtual register's segments from this union.
      57       56443 : void LiveIntervalUnion::extract(LiveInterval &VirtReg, const LiveRange &Range) {
      58       56443 :   if (Range.empty())
      59             :     return;
      60       56443 :   ++Tag;
      61             : 
      62             :   // Remove each of the virtual register's live segments from the map.
      63       56443 :   LiveRange::const_iterator RegPos = Range.begin();
      64       56443 :   LiveRange::const_iterator RegEnd = Range.end();
      65       56443 :   SegmentIter SegPos = Segments.find(RegPos->start);
      66             : 
      67             :   while (true) {
      68      105448 :     assert(SegPos.value() == &VirtReg && "Inconsistent LiveInterval");
      69      161891 :     SegPos.erase();
      70      129031 :     if (!SegPos.valid())
      71             :       return;
      72             : 
      73             :     // Skip all segments that may have been coalesced.
      74      129031 :     RegPos = Range.advanceTo(RegPos, SegPos.start());
      75      129031 :     if (RegPos == RegEnd)
      76             :       return;
      77             : 
      78      105448 :     SegPos.advanceTo(RegPos->start);
      79             :   }
      80             : }
      81             : 
      82             : void
      83           0 : LiveIntervalUnion::print(raw_ostream &OS, const TargetRegisterInfo *TRI) const {
      84           0 :   if (empty()) {
      85           0 :     OS << " empty\n";
      86           0 :     return;
      87             :   }
      88           0 :   for (LiveSegments::const_iterator SI = Segments.begin(); SI.valid(); ++SI) {
      89           0 :     OS << " [" << SI.start() << ' ' << SI.stop() << "):"
      90           0 :        << PrintReg(SI.value()->reg, TRI);
      91             :   }
      92             :   OS << '\n';
      93             : }
      94             : 
      95             : #ifndef NDEBUG
      96             : // Verify the live intervals in this union and add them to the visited set.
      97             : void LiveIntervalUnion::verify(LiveVirtRegBitSet& VisitedVRegs) {
      98             :   for (SegmentIter SI = Segments.begin(); SI.valid(); ++SI)
      99             :     VisitedVRegs.set(SI.value()->reg);
     100             : }
     101             : #endif //!NDEBUG
     102             : 
     103             : // Scan the vector of interfering virtual registers in this union. Assume it's
     104             : // quite small.
     105    19528067 : bool LiveIntervalUnion::Query::isSeenInterference(LiveInterval *VirtReg) const {
     106    39056134 :   return is_contained(InterferingVRegs, VirtReg);
     107             : }
     108             : 
     109             : // Collect virtual registers in this union that interfere with this
     110             : // query's live virtual register.
     111             : //
     112             : // The query state is one of:
     113             : //
     114             : // 1. CheckedFirstInterference == false: Iterators are uninitialized.
     115             : // 2. SeenAllInterferences == true: InterferingVRegs complete, iterators unused.
     116             : // 3. Iterators left at the last seen intersection.
     117             : //
     118    20887154 : unsigned LiveIntervalUnion::Query::
     119             : collectInterferingVRegs(unsigned MaxInterferingRegs) {
     120             :   // Fast path return if we already have the desired information.
     121    41717960 :   if (SeenAllInterferences || InterferingVRegs.size() >= MaxInterferingRegs)
     122     1789536 :     return InterferingVRegs.size();
     123             : 
     124             :   // Set up iterators on the first call.
     125    19992386 :   if (!CheckedFirstInterference) {
     126    19392522 :     CheckedFirstInterference = true;
     127             : 
     128             :     // Quickly skip interference check for empty sets.
     129    58177566 :     if (LR->empty() || LiveUnion->empty()) {
     130      724323 :       SeenAllInterferences = true;
     131      724323 :       return 0;
     132             :     }
     133             : 
     134             :     // In most cases, the union will start before LR.
     135    37336398 :     LRI = LR->begin();
     136    56004597 :     LiveUnionI.setMap(LiveUnion->getMap());
     137    18668199 :     LiveUnionI.find(LRI->start);
     138             :   }
     139             : 
     140    38536126 :   LiveRange::const_iterator LREnd = LR->end();
     141    19268063 :   LiveInterval *RecentReg = nullptr;
     142    25637768 :   while (LiveUnionI.valid()) {
     143             :     assert(LRI != LREnd && "Reached end of LR");
     144             : 
     145             :     // Check for overlapping interference.
     146   134331420 :     while (LRI->start < LiveUnionI.stop() && LRI->end > LiveUnionI.start()) {
     147             :       // This is an overlap, record the interfering register.
     148    39255170 :       LiveInterval *VReg = LiveUnionI.value();
     149    19627585 :       if (VReg != RecentReg && !isSeenInterference(VReg)) {
     150    18121572 :         RecentReg = VReg;
     151    18121572 :         InterferingVRegs.push_back(VReg);
     152    36243144 :         if (InterferingVRegs.size() >= MaxInterferingRegs)
     153    53027772 :           return InterferingVRegs.size();
     154             :       }
     155             :       // This LiveUnion segment is no longer interesting.
     156     3687914 :       if (!(++LiveUnionI).valid()) {
     157      646224 :         SeenAllInterferences = true;
     158     1292448 :         return InterferingVRegs.size();
     159             :       }
     160             :     }
     161             : 
     162             :     // The iterators are now not overlapping, LiveUnionI has been advanced
     163             :     // beyond LRI.
     164             :     assert(LRI->end <= LiveUnionI.start() && "Expected non-overlap");
     165             : 
     166             :     // Advance the iterator that ends first.
     167    13869060 :     LRI = LR->advanceTo(LRI, LiveUnionI.start());
     168     6934530 :     if (LRI == LREnd)
     169             :       break;
     170             : 
     171             :     // Detect overlap, handle above.
     172    19109115 :     if (LRI->start < LiveUnionI.stop())
     173     6126365 :       continue;
     174             : 
     175             :     // Still not overlapping. Catch up LiveUnionI.
     176      243340 :     LiveUnionI.advanceTo(LRI->start);
     177             :   }
     178     1161323 :   SeenAllInterferences = true;
     179     2322646 :   return InterferingVRegs.size();
     180             : }
     181             : 
     182      134827 : void LiveIntervalUnion::Array::init(LiveIntervalUnion::Allocator &Alloc,
     183             :                                     unsigned NSize) {
     184             :   // Reuse existing allocation.
     185      134827 :   if (NSize == Size)
     186             :     return;
     187       14923 :   clear();
     188       14923 :   Size = NSize;
     189       14923 :   LIUs = static_cast<LiveIntervalUnion*>(
     190       14923 :     malloc(sizeof(LiveIntervalUnion)*NSize));
     191     4655799 :   for (unsigned i = 0; i != Size; ++i)
     192     4640876 :     new(LIUs + i) LiveIntervalUnion(Alloc);
     193             : }
     194             : 
     195       30181 : void LiveIntervalUnion::Array::clear() {
     196       30181 :   if (!LIUs)
     197             :     return;
     198     9289312 :   for (unsigned i = 0; i != Size; ++i)
     199     9274404 :     LIUs[i].~LiveIntervalUnion();
     200       14908 :   free(LIUs);
     201       14908 :   Size =  0;
     202       14908 :   LIUs = nullptr;
     203             : }

Generated by: LCOV version 1.13