LCOV - code coverage report
Current view: top level - lib/CodeGen - LiveIntervalUnion.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 67 74 90.5 %
Date: 2018-06-17 00:07:59 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/CodeGen/TargetRegisterInfo.h"
      21             : #include "llvm/Support/raw_ostream.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     2261636 : void LiveIntervalUnion::unify(LiveInterval &VirtReg, const LiveRange &Range) {
      31     2261636 :   if (Range.empty())
      32      530895 :     return;
      33     2249671 :   ++Tag;
      34             : 
      35             :   // Insert each of the virtual register's live segments into the map.
      36             :   LiveRange::const_iterator RegPos = Range.begin();
      37             :   LiveRange::const_iterator RegEnd = Range.end();
      38     2249671 :   SegmentIter SegPos = Segments.find(RegPos->start);
      39             : 
      40      314043 :   while (SegPos.valid()) {
      41      832973 :     SegPos.insert(RegPos->start, RegPos->end, &VirtReg);
      42      832973 :     if (++RegPos == RegEnd)
      43             :       return;
      44      314043 :     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     1730741 :   --RegEnd;
      51     1730741 :   SegPos.insert(RegEnd->start, RegEnd->end, &VirtReg);
      52     2894533 :   for (; RegPos != RegEnd; ++RegPos, ++SegPos)
      53      581896 :     SegPos.insert(RegPos->start, RegPos->end, &VirtReg);
      54             : }
      55             : 
      56             : // Remove a live virtual register's segments from this union.
      57      153248 : void LiveIntervalUnion::extract(LiveInterval &VirtReg, const LiveRange &Range) {
      58      153248 :   if (Range.empty())
      59             :     return;
      60      153248 :   ++Tag;
      61             : 
      62             :   // Remove each of the virtual register's live segments from the map.
      63             :   LiveRange::const_iterator RegPos = Range.begin();
      64             :   LiveRange::const_iterator RegEnd = Range.end();
      65      153248 :   SegmentIter SegPos = Segments.find(RegPos->start);
      66             : 
      67             :   while (true) {
      68      168022 :     assert(SegPos.value() == &VirtReg && "Inconsistent LiveInterval");
      69      321270 :     SegPos.erase();
      70             :     if (!SegPos.valid())
      71             :       return;
      72             : 
      73             :     // Skip all segments that may have been coalesced.
      74      205480 :     RegPos = Range.advanceTo(RegPos, SegPos.start());
      75      205480 :     if (RegPos == RegEnd)
      76             :       return;
      77             : 
      78      168022 :     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    22295109 : bool LiveIntervalUnion::Query::isSeenInterference(LiveInterval *VirtReg) const {
     106    22295109 :   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    23793899 : unsigned LiveIntervalUnion::Query::
     119             : collectInterferingVRegs(unsigned MaxInterferingRegs) {
     120             :   // Fast path return if we already have the desired information.
     121    47502465 :   if (SeenAllInterferences || InterferingVRegs.size() >= MaxInterferingRegs)
     122      881217 :     return InterferingVRegs.size();
     123             : 
     124             :   // Set up iterators on the first call.
     125    22912682 :   if (!CheckedFirstInterference) {
     126    22272532 :     CheckedFirstInterference = true;
     127             : 
     128             :     // Quickly skip interference check for empty sets.
     129    66817596 :     if (LR->empty() || LiveUnion->empty()) {
     130     1058947 :       SeenAllInterferences = true;
     131     1058947 :       return 0;
     132             :     }
     133             : 
     134             :     // In most cases, the union will start before LR.
     135    21213585 :     LRI = LR->begin();
     136             :     LiveUnionI.setMap(LiveUnion->getMap());
     137    21213585 :     LiveUnionI.find(LRI->start);
     138             :   }
     139             : 
     140    21853735 :   LiveRange::const_iterator LREnd = LR->end();
     141             :   LiveInterval *RecentReg = nullptr;
     142             :   while (LiveUnionI.valid()) {
     143             :     assert(LRI != LREnd && "Reached end of LR");
     144             : 
     145             :     // Check for overlapping interference.
     146    81933077 :     while (LRI->start < LiveUnionI.stop() && LRI->end > LiveUnionI.start()) {
     147             :       // This is an overlap, record the interfering register.
     148    22416650 :       LiveInterval *VReg = LiveUnionI.value();
     149    22416650 :       if (VReg != RecentReg && !isSeenInterference(VReg)) {
     150    20831513 :         RecentReg = VReg;
     151    20831513 :         InterferingVRegs.push_back(VReg);
     152    20831513 :         if (InterferingVRegs.size() >= MaxInterferingRegs)
     153    40170960 :           return InterferingVRegs.size();
     154             :       }
     155             :       // This LiveUnion segment is no longer interesting.
     156     2649710 :       if (!(++LiveUnionI).valid()) {
     157      637080 :         SeenAllInterferences = true;
     158      637080 :         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     8446998 :     LRI = LR->advanceTo(LRI, LiveUnionI.start());
     168     4223499 :     if (LRI == LREnd)
     169             :       break;
     170             : 
     171             :     // Detect overlap, handle above.
     172     3494657 :     if (LRI->start < LiveUnionI.stop())
     173     3240802 :       continue;
     174             : 
     175             :     // Still not overlapping. Catch up LiveUnionI.
     176      253855 :     LiveUnionI.advanceTo(LRI->start);
     177             :   }
     178     1449715 :   SeenAllInterferences = true;
     179     1449715 :   return InterferingVRegs.size();
     180             : }
     181             : 
     182      179253 : void LiveIntervalUnion::Array::init(LiveIntervalUnion::Allocator &Alloc,
     183             :                                     unsigned NSize) {
     184             :   // Reuse existing allocation.
     185      179253 :   if (NSize == Size)
     186             :     return;
     187       17812 :   clear();
     188       17812 :   Size = NSize;
     189       17812 :   LIUs = static_cast<LiveIntervalUnion*>(
     190       17812 :       safe_malloc(sizeof(LiveIntervalUnion)*NSize));
     191    11629616 :   for (unsigned i = 0; i != Size; ++i)
     192     5805902 :     new(LIUs + i) LiveIntervalUnion(Alloc);
     193             : }
     194             : 
     195       36232 : void LiveIntervalUnion::Array::clear() {
     196       36232 :   if (!LIUs)
     197             :     return;
     198    11621758 :   for (unsigned i = 0; i != Size; ++i)
     199     5801981 :     LIUs[i].~LiveIntervalUnion();
     200       17796 :   free(LIUs);
     201       17796 :   Size =  0;
     202       17796 :   LIUs = nullptr;
     203             : }

Generated by: LCOV version 1.13