1218885Sdim//===-- LiveIntervalUnion.cpp - Live interval union data structure --------===// 2218885Sdim// 3218885Sdim// The LLVM Compiler Infrastructure 4218885Sdim// 5218885Sdim// This file is distributed under the University of Illinois Open Source 6218885Sdim// License. See LICENSE.TXT for details. 7218885Sdim// 8218885Sdim//===----------------------------------------------------------------------===// 9218885Sdim// 10218885Sdim// LiveIntervalUnion represents a coalesced set of live intervals. This may be 11218885Sdim// used during coalescing to represent a congruence class, or during register 12218885Sdim// allocation to model liveness of a physical register. 13218885Sdim// 14218885Sdim//===----------------------------------------------------------------------===// 15218885Sdim 16218885Sdim#define DEBUG_TYPE "regalloc" 17252723Sdim#include "llvm/CodeGen/LiveIntervalUnion.h" 18218885Sdim#include "llvm/ADT/SparseBitVector.h" 19218885Sdim#include "llvm/Support/Debug.h" 20218885Sdim#include "llvm/Support/raw_ostream.h" 21218885Sdim#include "llvm/Target/TargetRegisterInfo.h" 22235633Sdim#include <algorithm> 23235633Sdim 24218885Sdimusing namespace llvm; 25218885Sdim 26218885Sdim 27218885Sdim// Merge a LiveInterval's segments. Guarantee no overlaps. 28218885Sdimvoid LiveIntervalUnion::unify(LiveInterval &VirtReg) { 29218885Sdim if (VirtReg.empty()) 30218885Sdim return; 31218885Sdim ++Tag; 32218885Sdim 33218885Sdim // Insert each of the virtual register's live segments into the map. 34218885Sdim LiveInterval::iterator RegPos = VirtReg.begin(); 35218885Sdim LiveInterval::iterator RegEnd = VirtReg.end(); 36218885Sdim SegmentIter SegPos = Segments.find(RegPos->start); 37218885Sdim 38221345Sdim while (SegPos.valid()) { 39218885Sdim SegPos.insert(RegPos->start, RegPos->end, &VirtReg); 40218885Sdim if (++RegPos == RegEnd) 41218885Sdim return; 42218885Sdim SegPos.advanceTo(RegPos->start); 43218885Sdim } 44221345Sdim 45221345Sdim // We have reached the end of Segments, so it is no longer necessary to search 46221345Sdim // for the insertion position. 47221345Sdim // It is faster to insert the end first. 48221345Sdim --RegEnd; 49221345Sdim SegPos.insert(RegEnd->start, RegEnd->end, &VirtReg); 50221345Sdim for (; RegPos != RegEnd; ++RegPos, ++SegPos) 51221345Sdim SegPos.insert(RegPos->start, RegPos->end, &VirtReg); 52218885Sdim} 53218885Sdim 54218885Sdim// Remove a live virtual register's segments from this union. 55218885Sdimvoid LiveIntervalUnion::extract(LiveInterval &VirtReg) { 56218885Sdim if (VirtReg.empty()) 57218885Sdim return; 58218885Sdim ++Tag; 59218885Sdim 60218885Sdim // Remove each of the virtual register's live segments from the map. 61218885Sdim LiveInterval::iterator RegPos = VirtReg.begin(); 62218885Sdim LiveInterval::iterator RegEnd = VirtReg.end(); 63218885Sdim SegmentIter SegPos = Segments.find(RegPos->start); 64218885Sdim 65218885Sdim for (;;) { 66218885Sdim assert(SegPos.value() == &VirtReg && "Inconsistent LiveInterval"); 67218885Sdim SegPos.erase(); 68218885Sdim if (!SegPos.valid()) 69218885Sdim return; 70218885Sdim 71218885Sdim // Skip all segments that may have been coalesced. 72218885Sdim RegPos = VirtReg.advanceTo(RegPos, SegPos.start()); 73218885Sdim if (RegPos == RegEnd) 74218885Sdim return; 75218885Sdim 76218885Sdim SegPos.advanceTo(RegPos->start); 77218885Sdim } 78218885Sdim} 79218885Sdim 80218885Sdimvoid 81218885SdimLiveIntervalUnion::print(raw_ostream &OS, const TargetRegisterInfo *TRI) const { 82218885Sdim if (empty()) { 83218885Sdim OS << " empty\n"; 84218885Sdim return; 85218885Sdim } 86218885Sdim for (LiveSegments::const_iterator SI = Segments.begin(); SI.valid(); ++SI) { 87218885Sdim OS << " [" << SI.start() << ' ' << SI.stop() << "):" 88218885Sdim << PrintReg(SI.value()->reg, TRI); 89218885Sdim } 90218885Sdim OS << '\n'; 91218885Sdim} 92218885Sdim 93218885Sdim#ifndef NDEBUG 94218885Sdim// Verify the live intervals in this union and add them to the visited set. 95218885Sdimvoid LiveIntervalUnion::verify(LiveVirtRegBitSet& VisitedVRegs) { 96218885Sdim for (SegmentIter SI = Segments.begin(); SI.valid(); ++SI) 97218885Sdim VisitedVRegs.set(SI.value()->reg); 98218885Sdim} 99218885Sdim#endif //!NDEBUG 100218885Sdim 101218885Sdim// Scan the vector of interfering virtual registers in this union. Assume it's 102218885Sdim// quite small. 103218885Sdimbool LiveIntervalUnion::Query::isSeenInterference(LiveInterval *VirtReg) const { 104218885Sdim SmallVectorImpl<LiveInterval*>::const_iterator I = 105218885Sdim std::find(InterferingVRegs.begin(), InterferingVRegs.end(), VirtReg); 106218885Sdim return I != InterferingVRegs.end(); 107218885Sdim} 108218885Sdim 109226890Sdim// Collect virtual registers in this union that interfere with this 110218885Sdim// query's live virtual register. 111218885Sdim// 112226890Sdim// The query state is one of: 113218885Sdim// 114226890Sdim// 1. CheckedFirstInterference == false: Iterators are uninitialized. 115226890Sdim// 2. SeenAllInterferences == true: InterferingVRegs complete, iterators unused. 116226890Sdim// 3. Iterators left at the last seen intersection. 117226890Sdim// 118218885Sdimunsigned LiveIntervalUnion::Query:: 119224145SdimcollectInterferingVRegs(unsigned MaxInterferingRegs) { 120226890Sdim // Fast path return if we already have the desired information. 121226890Sdim if (SeenAllInterferences || InterferingVRegs.size() >= MaxInterferingRegs) 122226890Sdim return InterferingVRegs.size(); 123218885Sdim 124226890Sdim // Set up iterators on the first call. 125226890Sdim if (!CheckedFirstInterference) { 126226890Sdim CheckedFirstInterference = true; 127218885Sdim 128226890Sdim // Quickly skip interference check for empty sets. 129226890Sdim if (VirtReg->empty() || LiveUnion->empty()) { 130226890Sdim SeenAllInterferences = true; 131226890Sdim return 0; 132226890Sdim } 133218885Sdim 134226890Sdim // In most cases, the union will start before VirtReg. 135226890Sdim VirtRegI = VirtReg->begin(); 136226890Sdim LiveUnionI.setMap(LiveUnion->getMap()); 137226890Sdim LiveUnionI.find(VirtRegI->start); 138226890Sdim } 139218885Sdim 140226890Sdim LiveInterval::iterator VirtRegEnd = VirtReg->end(); 141226890Sdim LiveInterval *RecentReg = 0; 142226890Sdim while (LiveUnionI.valid()) { 143226890Sdim assert(VirtRegI != VirtRegEnd && "Reached end of VirtReg"); 144218885Sdim 145226890Sdim // Check for overlapping interference. 146226890Sdim while (VirtRegI->start < LiveUnionI.stop() && 147226890Sdim VirtRegI->end > LiveUnionI.start()) { 148226890Sdim // This is an overlap, record the interfering register. 149226890Sdim LiveInterval *VReg = LiveUnionI.value(); 150226890Sdim if (VReg != RecentReg && !isSeenInterference(VReg)) { 151226890Sdim RecentReg = VReg; 152226890Sdim InterferingVRegs.push_back(VReg); 153226890Sdim if (InterferingVRegs.size() >= MaxInterferingRegs) 154226890Sdim return InterferingVRegs.size(); 155226890Sdim } 156226890Sdim // This LiveUnion segment is no longer interesting. 157226890Sdim if (!(++LiveUnionI).valid()) { 158226890Sdim SeenAllInterferences = true; 159226890Sdim return InterferingVRegs.size(); 160226890Sdim } 161226890Sdim } 162218885Sdim 163226890Sdim // The iterators are now not overlapping, LiveUnionI has been advanced 164226890Sdim // beyond VirtRegI. 165226890Sdim assert(VirtRegI->end <= LiveUnionI.start() && "Expected non-overlap"); 166218885Sdim 167226890Sdim // Advance the iterator that ends first. 168226890Sdim VirtRegI = VirtReg->advanceTo(VirtRegI, LiveUnionI.start()); 169226890Sdim if (VirtRegI == VirtRegEnd) 170226890Sdim break; 171218885Sdim 172226890Sdim // Detect overlap, handle above. 173226890Sdim if (VirtRegI->start < LiveUnionI.stop()) 174226890Sdim continue; 175218885Sdim 176226890Sdim // Still not overlapping. Catch up LiveUnionI. 177226890Sdim LiveUnionI.advanceTo(VirtRegI->start); 178218885Sdim } 179218885Sdim SeenAllInterferences = true; 180218885Sdim return InterferingVRegs.size(); 181218885Sdim} 182218885Sdim 183245431Sdimvoid LiveIntervalUnion::Array::init(LiveIntervalUnion::Allocator &Alloc, 184245431Sdim unsigned NSize) { 185245431Sdim // Reuse existing allocation. 186245431Sdim if (NSize == Size) 187245431Sdim return; 188245431Sdim clear(); 189245431Sdim Size = NSize; 190245431Sdim LIUs = static_cast<LiveIntervalUnion*>( 191245431Sdim malloc(sizeof(LiveIntervalUnion)*NSize)); 192245431Sdim for (unsigned i = 0; i != Size; ++i) 193245431Sdim new(LIUs + i) LiveIntervalUnion(Alloc); 194245431Sdim} 195245431Sdim 196245431Sdimvoid LiveIntervalUnion::Array::clear() { 197245431Sdim if (!LIUs) 198245431Sdim return; 199245431Sdim for (unsigned i = 0; i != Size; ++i) 200245431Sdim LIUs[i].~LiveIntervalUnion(); 201245431Sdim free(LIUs); 202245431Sdim Size = 0; 203245431Sdim LIUs = 0; 204245431Sdim} 205