1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===-- LiveInterval.cpp - Live Interval Representation -------------------===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file implements the LiveRange and LiveInterval classes. Given some 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// numbering of each the machine instructions an interval [i, j) is said to be a 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// live interval for register v if there is no instruction with number j' > j 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// such that v is live at j' and there is no instruction with number i' < i such 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// that v is live at i'. In this implementation intervals can have holes, 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// i.e. an interval might look like [1,20), [50,65), [1000,1001). Each 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// individual range is represented as an instance of LiveRange, and the whole 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// interval is represented as an instance of LiveInterval. 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 21894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/LiveInterval.h" 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/LiveIntervalAnalysis.h" 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/MachineRegisterInfo.h" 24894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/DenseMap.h" 25894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/SmallSet.h" 26894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/STLExtras.h" 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/Debug.h" 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/raw_ostream.h" 29894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Target/TargetRegisterInfo.h" 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include <algorithm> 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanusing namespace llvm; 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 3319bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanLiveInterval::iterator LiveInterval::find(SlotIndex Pos) { 3419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // This algorithm is basically std::upper_bound. 3519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Unfortunately, std::upper_bound cannot be used with mixed types until we 3619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // adopt C++0x. Many libraries can do it, but not all. 3719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (empty() || Pos >= endIndex()) 3819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return end(); 3919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman iterator I = begin(); 4019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman size_t Len = ranges.size(); 4119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman do { 4219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman size_t Mid = Len >> 1; 4319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Pos < I[Mid].end) 4419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Len = Mid; 4519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 4619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman I += Mid + 1, Len -= Mid + 1; 4719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } while (Len); 4819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return I; 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 50894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 51894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// killedInRange - Return true if the interval has kills in [Start,End). 52894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool LiveInterval::killedInRange(SlotIndex Start, SlotIndex End) const { 53894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Ranges::const_iterator r = 54894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::lower_bound(ranges.begin(), ranges.end(), End); 55894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 56894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Now r points to the first interval with start >= End, or ranges.end(). 57894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (r == ranges.begin()) 58894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 59894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 60894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman --r; 61894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Now r points to the last interval with end <= End. 62894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // r->end is the kill point. 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return r->end >= Start && r->end < End; 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// overlaps - Return true if the intersection of the two live intervals is 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// not empty. 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// An example for overlaps(): 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 0: A = ... 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 4: B = ... 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8: C = A + B ;; last use of A 74894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 75894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The live intervals should look like: 76894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// A = [3, 11) 78894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// B = [7, x) 79894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// C = [11, y) 80894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// A->overlaps(C) should return false since we want to be able to join 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// A and C. 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 84894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool LiveInterval::overlapsFrom(const LiveInterval& other, 85894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const_iterator StartPos) const { 86894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(!empty() && "empty interval"); 87894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const_iterator i = begin(); 88894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const_iterator ie = end(); 89894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const_iterator j = StartPos; 90894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const_iterator je = other.end(); 91894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 92894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert((StartPos->start <= i->start || StartPos == other.begin()) && 93894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman StartPos != other.end() && "Bogus start position hint!"); 94894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 95894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (i->start < j->start) { 96894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman i = std::upper_bound(i, ie, j->start); 97894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (i != ranges.begin()) --i; 98894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else if (j->start < i->start) { 99894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++StartPos; 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (StartPos != other.end() && StartPos->start <= i->start) { 101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(StartPos < other.end() && i < end()); 102894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman j = std::upper_bound(j, je, i->start); 103894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (j != other.ranges.begin()) --j; 104894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 106894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 107894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 108894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (j == je) return false; 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman while (i != ie) { 112894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (i->start > j->start) { 113894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::swap(i, j); 114894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::swap(ie, je); 115894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 116894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 117894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (i->end > j->start) 118894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 119894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++i; 120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 124894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 125894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// overlaps - Return true if the live interval overlaps a range specified 126894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// by [Start, End). 127894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool LiveInterval::overlaps(SlotIndex Start, SlotIndex End) const { 128894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Start < End && "Invalid range"); 129894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const_iterator I = std::lower_bound(begin(), end(), End); 130894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return I != begin() && (--I)->end > Start; 131894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 132894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 133894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 134894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// ValNo is dead, remove it. If it is the largest value number, just nuke it 135894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// (and any other deleted values neighboring it), otherwise mark it as ~1U so 136894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// it can be nuked later. 137894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid LiveInterval::markValNoForDeletion(VNInfo *ValNo) { 138894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (ValNo->id == getNumValNums()-1) { 139894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman do { 140894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman valnos.pop_back(); 141894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } while (!valnos.empty() && valnos.back()->isUnused()); 142894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 143894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ValNo->setIsUnused(true); 144894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 145894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 146894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 147894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// RenumberValues - Renumber all values in order of appearance and delete the 148894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// remaining unused values. 14919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid LiveInterval::RenumberValues(LiveIntervals &lis) { 150894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallPtrSet<VNInfo*, 8> Seen; 151894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman valnos.clear(); 152894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (const_iterator I = begin(), E = end(); I != E; ++I) { 153894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman VNInfo *VNI = I->valno; 154894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!Seen.insert(VNI)) 155894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 156894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(!VNI->isUnused() && "Unused valno used by live range"); 157894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman VNI->id = (unsigned)valnos.size(); 158894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman valnos.push_back(VNI); 159894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 160894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 161894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 162894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// extendIntervalEndTo - This method is used when we want to extend the range 163894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// specified by I to end at the specified endpoint. To do this, we should 164894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// merge and eliminate all ranges that this will overlap with. The iterator is 165894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// not invalidated. 166894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid LiveInterval::extendIntervalEndTo(Ranges::iterator I, SlotIndex NewEnd) { 167894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(I != ranges.end() && "Not a valid interval!"); 168894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman VNInfo *ValNo = I->valno; 169894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 170894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Search for the first interval that we can't merge with. 171894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Ranges::iterator MergeTo = llvm::next(I); 172894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (; MergeTo != ranges.end() && NewEnd >= MergeTo->end; ++MergeTo) { 173894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); 174894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 175894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 176894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If NewEnd was in the middle of an interval, make sure to get its endpoint. 177894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->end = std::max(NewEnd, prior(MergeTo)->end); 178894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 179894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Erase any dead ranges. 180894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ranges.erase(llvm::next(I), MergeTo); 181894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 182894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the newly formed range now touches the range after it and if they have 183894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // the same value number, merge the two ranges into one range. 184894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Ranges::iterator Next = llvm::next(I); 185894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Next != ranges.end() && Next->start <= I->end && Next->valno == ValNo) { 186894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->end = Next->end; 187894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ranges.erase(Next); 188894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 189894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 190894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 191894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 192894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// extendIntervalStartTo - This method is used when we want to extend the range 193894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// specified by I to start at the specified endpoint. To do this, we should 194894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// merge and eliminate all ranges that this will overlap with. 195894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanLiveInterval::Ranges::iterator 196894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanLiveInterval::extendIntervalStartTo(Ranges::iterator I, SlotIndex NewStart) { 197894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(I != ranges.end() && "Not a valid interval!"); 198894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman VNInfo *ValNo = I->valno; 199894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 200894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Search for the first interval that we can't merge with. 201894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Ranges::iterator MergeTo = I; 202894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman do { 203894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MergeTo == ranges.begin()) { 204894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->start = NewStart; 205894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ranges.erase(MergeTo, I); 206894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return I; 207894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 208894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); 209894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman --MergeTo; 210894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } while (NewStart <= MergeTo->start); 211894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 212894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we start in the middle of another interval, just delete a range and 213894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // extend that interval. 214894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MergeTo->end >= NewStart && MergeTo->valno == ValNo) { 215894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MergeTo->end = I->end; 216894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 217894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise, extend the interval right after. 218894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++MergeTo; 219894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MergeTo->start = NewStart; 220894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MergeTo->end = I->end; 221894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 222894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 223894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ranges.erase(llvm::next(MergeTo), llvm::next(I)); 224894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return MergeTo; 225894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 226894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 227894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanLiveInterval::iterator 228894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanLiveInterval::addRangeFrom(LiveRange LR, iterator From) { 229894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SlotIndex Start = LR.start, End = LR.end; 230894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman iterator it = std::upper_bound(From, ranges.end(), Start); 231894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 232894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the inserted interval starts in the middle or right at the end of 233894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // another interval, just extend that interval to contain the range of LR. 234894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (it != ranges.begin()) { 235894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman iterator B = prior(it); 236894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (LR.valno == B->valno) { 237894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (B->start <= Start && B->end >= Start) { 238894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman extendIntervalEndTo(B, End); 239894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return B; 240894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 241894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 242894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check to make sure that we are not overlapping two live ranges with 243894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // different valno's. 244894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(B->end <= Start && 245894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Cannot overlap two LiveRanges with differing ValID's" 246894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman " (did you def the same reg twice in a MachineInstr?)"); 247894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 248894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 249894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 250894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise, if this range ends in the middle of, or right next to, another 251894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // interval, merge it into that interval. 252894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (it != ranges.end()) { 253894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (LR.valno == it->valno) { 254894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (it->start <= End) { 255894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman it = extendIntervalStartTo(it, Start); 256894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 257894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If LR is a complete superset of an interval, we may need to grow its 258894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // endpoint as well. 259894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (End > it->end) 260894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman extendIntervalEndTo(it, End); 261894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return it; 262894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 263894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 264894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check to make sure that we are not overlapping two live ranges with 265894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // different valno's. 266894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(it->start >= End && 267894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Cannot overlap two LiveRanges with differing ValID's"); 268894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 269894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 270894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 271894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise, this is just a new range that doesn't interact with anything. 272894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Insert it. 273894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return ranges.insert(it, LR); 274894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 275894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 27619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// extendInBlock - If this interval is live before Kill in the basic 27719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// block that starts at StartIdx, extend it to be live up to Kill and return 27819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// the value. If there is no live range before Kill, return NULL. 27919bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanVNInfo *LiveInterval::extendInBlock(SlotIndex StartIdx, SlotIndex Kill) { 28019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (empty()) 28119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return 0; 28219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman iterator I = std::upper_bound(begin(), end(), Kill.getPrevSlot()); 28319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (I == begin()) 28419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return 0; 285894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman --I; 28619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (I->end <= StartIdx) 28719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return 0; 28819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (I->end < Kill) 28919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman extendIntervalEndTo(I, Kill); 29019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return I->valno; 291894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 292894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 293894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// removeRange - Remove the specified range from this interval. Note that 294894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// the range must be in a single LiveRange in its entirety. 295894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid LiveInterval::removeRange(SlotIndex Start, SlotIndex End, 296894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool RemoveDeadValNo) { 297894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Find the LiveRange containing this span. 29819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Ranges::iterator I = find(Start); 29919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(I != ranges.end() && "Range is not in interval!"); 300894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(I->containsRange(Start, End) && "Range is not entirely in interval!"); 301894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 302894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the span we are removing is at the start of the LiveRange, adjust it. 303894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman VNInfo *ValNo = I->valno; 304894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I->start == Start) { 305894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I->end == End) { 306894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (RemoveDeadValNo) { 307894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check if val# is dead. 308894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isDead = true; 309894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (const_iterator II = begin(), EE = end(); II != EE; ++II) 310894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (II != I && II->valno == ValNo) { 311894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman isDead = false; 312894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 313894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 314894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isDead) { 315894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Now that ValNo is dead, remove it. 316894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman markValNoForDeletion(ValNo); 317894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 318894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 319894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 320894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ranges.erase(I); // Removed the whole LiveRange. 321894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else 322894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->start = End; 323894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 324894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 325894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 326894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise if the span we are removing is at the end of the LiveRange, 327894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // adjust the other way. 328894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I->end == End) { 329894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->end = Start; 330894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 331894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 332894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 333894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise, we are splitting the LiveRange into two pieces. 334894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SlotIndex OldEnd = I->end; 335894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->end = Start; // Trim the old interval. 336894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 337894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Insert the new one. 338894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ranges.insert(llvm::next(I), LiveRange(End, OldEnd, ValNo)); 339894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 340894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 341894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// removeValNo - Remove all the ranges defined by the specified value#. 342894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// Also remove the value# from value# list. 343894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid LiveInterval::removeValNo(VNInfo *ValNo) { 344894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (empty()) return; 345894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Ranges::iterator I = ranges.end(); 346894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Ranges::iterator E = ranges.begin(); 347894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman do { 348894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman --I; 349894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I->valno == ValNo) 350894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ranges.erase(I); 351894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } while (I != E); 352894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Now that ValNo is dead, remove it. 353894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman markValNoForDeletion(ValNo); 354894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 355894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 356894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// findDefinedVNInfo - Find the VNInfo defined by the specified 357894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// index (register interval). 358894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanVNInfo *LiveInterval::findDefinedVNInfoForRegInt(SlotIndex Idx) const { 359894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (LiveInterval::const_vni_iterator i = vni_begin(), e = vni_end(); 360894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman i != e; ++i) { 361894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if ((*i)->def == Idx) 362894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return *i; 363894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 364894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 365894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return 0; 366894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 367894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 368894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// join - Join two live intervals (this, and other) together. This applies 369894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// mappings to the value numbers in the LHS/RHS intervals as specified. If 370894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// the intervals are not joinable, this aborts. 371894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid LiveInterval::join(LiveInterval &Other, 372894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const int *LHSValNoAssignments, 37319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const int *RHSValNoAssignments, 374894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<VNInfo*, 16> &NewVNInfo, 375894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineRegisterInfo *MRI) { 376894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Determine if any of our live range values are mapped. This is uncommon, so 37719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // we want to avoid the interval scan if not. 378894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool MustMapCurValNos = false; 379894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NumVals = getNumValNums(); 380894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NumNewVals = NewVNInfo.size(); 381894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0; i != NumVals; ++i) { 382894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned LHSValID = LHSValNoAssignments[i]; 383894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (i != LHSValID || 384894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (NewVNInfo[LHSValID] && NewVNInfo[LHSValID] != getValNumInfo(i))) 385894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MustMapCurValNos = true; 386894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 387894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 388894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we have to apply a mapping to our base interval assignment, rewrite it 389894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // now. 390894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MustMapCurValNos) { 391894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Map the first live range. 392894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman iterator OutIt = begin(); 393894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OutIt->valno = NewVNInfo[LHSValNoAssignments[OutIt->valno->id]]; 394894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++OutIt; 395894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (iterator I = OutIt, E = end(); I != E; ++I) { 396894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OutIt->valno = NewVNInfo[LHSValNoAssignments[I->valno->id]]; 39719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 398894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If this live range has the same value # as its immediate predecessor, 399894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // and if they are neighbors, remove one LiveRange. This happens when we 400894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // have [0,3:0)[4,7:1) and map 0/1 onto the same value #. 401894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (OutIt->valno == (OutIt-1)->valno && (OutIt-1)->end == OutIt->start) { 402894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman (OutIt-1)->end = OutIt->end; 403894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 404894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I != OutIt) { 405894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OutIt->start = I->start; 406894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OutIt->end = I->end; 407894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 40819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 409894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Didn't merge, on to the next one. 410894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++OutIt; 411894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 412894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 41319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 414894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we merge some live ranges, chop off the end. 415894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ranges.erase(OutIt, end()); 416894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 417894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 418894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Remember assignements because val# ids are changing. 419894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<unsigned, 16> OtherAssignments; 420894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (iterator I = Other.begin(), E = Other.end(); I != E; ++I) 421894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OtherAssignments.push_back(RHSValNoAssignments[I->valno->id]); 422894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 423894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Update val# info. Renumber them and make sure they all belong to this 424894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // LiveInterval now. Also remove dead val#'s. 425894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NumValNos = 0; 426894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0; i < NumNewVals; ++i) { 427894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman VNInfo *VNI = NewVNInfo[i]; 428894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (VNI) { 429894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (NumValNos >= NumVals) 430894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman valnos.push_back(VNI); 43119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 432894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman valnos[NumValNos] = VNI; 433894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman VNI->id = NumValNos++; // Renumber val#. 434894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 435894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 436894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (NumNewVals < NumVals) 437894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman valnos.resize(NumNewVals); // shrinkify 438894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 439894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Okay, now insert the RHS live ranges into the LHS. 440894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman iterator InsertPos = begin(); 441894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned RangeNo = 0; 442894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (iterator I = Other.begin(), E = Other.end(); I != E; ++I, ++RangeNo) { 443894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Map the valno in the other live range to the current live range. 444894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I->valno = NewVNInfo[OtherAssignments[RangeNo]]; 445894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(I->valno && "Adding a dead range?"); 446894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman InsertPos = addRangeFrom(*I, InsertPos); 447894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 448894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 449894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ComputeJoinedWeight(Other); 450894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 451894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 452894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// MergeRangesInAsValue - Merge all of the intervals in RHS into this live 453894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// interval as the specified value number. The LiveRanges in RHS are 454894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// allowed to overlap with LiveRanges in the current interval, but only if 455894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// the overlapping LiveRanges have the specified value number. 45619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid LiveInterval::MergeRangesInAsValue(const LiveInterval &RHS, 457894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman VNInfo *LHSValNo) { 458894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // TODO: Make this more efficient. 459894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman iterator InsertPos = begin(); 460894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) { 461894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Map the valno in the other live range to the current live range. 462894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LiveRange Tmp = *I; 463894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Tmp.valno = LHSValNo; 464894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman InsertPos = addRangeFrom(Tmp, InsertPos); 465894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 466894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 467894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 468894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 469894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// MergeValueInAsValue - Merge all of the live ranges of a specific val# 470894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// in RHS into this live interval as the specified value number. 471894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// The LiveRanges in RHS are allowed to overlap with LiveRanges in the 472894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// current interval, it will replace the value numbers of the overlaped 473894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// live ranges with the specified value number. 474894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid LiveInterval::MergeValueInAsValue( 475894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const LiveInterval &RHS, 476894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const VNInfo *RHSValNo, VNInfo *LHSValNo) { 47719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // TODO: Make this more efficient. 47819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman iterator InsertPos = begin(); 479894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) { 480894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I->valno != RHSValNo) 481894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 482894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Map the valno in the other live range to the current live range. 48319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveRange Tmp = *I; 48419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Tmp.valno = LHSValNo; 48519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman InsertPos = addRangeFrom(Tmp, InsertPos); 486894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 487894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 488894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 489894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 490894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// MergeValueNumberInto - This method is called when two value nubmers 491894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// are found to be equivalent. This eliminates V1, replacing all 492894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// LiveRanges with the V1 value number with the V2 value number. This can 493894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// cause merging of V1/V2 values numbers and compaction of the value space. 494894018228b0e0bdbd7aa7e8f47d4a9458789ca82John BaumanVNInfo* LiveInterval::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) { 495894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(V1 != V2 && "Identical value#'s are always equivalent!"); 496894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 497894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // This code actually merges the (numerically) larger value number into the 498894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // smaller value number, which is likely to allow us to compactify the value 499894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // space. The only thing we have to be careful of is to preserve the 500894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // instruction that defines the result value. 501894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 502894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Make sure V2 is smaller than V1. 503894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (V1->id < V2->id) { 504894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman V1->copyFrom(*V2); 505894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::swap(V1, V2); 506894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 507894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 508894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Merge V1 live ranges into V2. 509894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (iterator I = begin(); I != end(); ) { 510894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman iterator LR = I++; 511894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (LR->valno != V1) continue; // Not a V1 LiveRange. 51219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 513894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Okay, we found a V1 live range. If it had a previous, touching, V2 live 514894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // range, extend it. 515894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (LR != begin()) { 516894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman iterator Prev = LR-1; 517894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Prev->valno == V2 && Prev->end == LR->start) { 518894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Prev->end = LR->end; 519894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 520894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Erase this live-range. 521894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ranges.erase(LR); 522894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I = Prev+1; 523894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LR = Prev; 524894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 525894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 52619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 527894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Okay, now we have a V1 or V2 live range that is maximally merged forward. 528894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Ensure that it is a V2 live-range. 529894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LR->valno = V2; 53019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 531894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we can merge it into later V2 live ranges, do so now. We ignore any 532894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // following V1 live ranges, as they will be merged in subsequent iterations 533894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // of the loop. 534894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I != end()) { 535894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (I->start == LR->end && I->valno == V2) { 536894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman LR->end = I->end; 537894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ranges.erase(I); 538894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I = LR+1; 539894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 540894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 541894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 54219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 54319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Merge the relevant flags. 54419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman V2->mergeFlags(V1); 54519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 546894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Now that V1 is dead, remove it. 547894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman markValNoForDeletion(V1); 54819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 549894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return V2; 550894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 551894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 552894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid LiveInterval::Copy(const LiveInterval &RHS, 553894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineRegisterInfo *MRI, 554894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman VNInfo::Allocator &VNInfoAllocator) { 555894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ranges.clear(); 556894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman valnos.clear(); 557894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(RHS.reg); 558894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MRI->setRegAllocationHint(reg, Hint.first, Hint.second); 559894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 560894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman weight = RHS.weight; 561894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = RHS.getNumValNums(); i != e; ++i) { 562894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const VNInfo *VNI = RHS.getValNumInfo(i); 563894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman createValueCopy(VNI, VNInfoAllocator); 564894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 565894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = RHS.ranges.size(); i != e; ++i) { 566894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const LiveRange &LR = RHS.ranges[i]; 567894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman addRange(LiveRange(LR.start, LR.end, getValNumInfo(LR.valno->id))); 568894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 569894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 570894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 571894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanunsigned LiveInterval::getSize() const { 572894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Sum = 0; 573894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (const_iterator I = begin(), E = end(); I != E; ++I) 574894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Sum += I->start.distance(I->end); 575894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Sum; 576894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 577894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 578894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// ComputeJoinedWeight - Set the weight of a live interval Joined 579894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// after Other has been merged into it. 580894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid LiveInterval::ComputeJoinedWeight(const LiveInterval &Other) { 581894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If either of these intervals was spilled, the weight is the 582894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // weight of the non-spilled interval. This can only happen with 583894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // iterative coalescers. 584894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 585894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Other.weight != HUGE_VALF) { 586894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman weight += Other.weight; 587894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 588894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else if (weight == HUGE_VALF && 589894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman !TargetRegisterInfo::isPhysicalRegister(reg)) { 590894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Remove this assert if you have an iterative coalescer 591894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(0 && "Joining to spilled interval"); 592894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman weight = Other.weight; 593894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 594894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else { 595894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Otherwise the weight stays the same 596894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Remove this assert if you have an iterative coalescer 597894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(0 && "Joining from spilled interval"); 598894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 599894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 600894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 601894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanraw_ostream& llvm::operator<<(raw_ostream& os, const LiveRange &LR) { 602894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return os << '[' << LR.start << ',' << LR.end << ':' << LR.valno->id << ")"; 603894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 604894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 605894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid LiveRange::dump() const { 606894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << *this << "\n"; 607894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 608894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 609894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid LiveInterval::print(raw_ostream &OS, const TargetRegisterInfo *TRI) const { 61019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman OS << PrintReg(reg, TRI); 61119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (weight != 0) 61219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman OS << ',' << weight; 613894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 614894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (empty()) 615894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OS << " EMPTY"; 616894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else { 617894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OS << " = "; 618894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (LiveInterval::Ranges::const_iterator I = ranges.begin(), 619894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman E = ranges.end(); I != E; ++I) { 620894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OS << *I; 621894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(I->valno == getValNumInfo(I->valno->id) && "Bad VNInfo"); 622894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 623894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 624894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 625894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Print value number info. 626894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (getNumValNums()) { 627894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OS << " "; 628894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned vnum = 0; 629894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (const_vni_iterator i = vni_begin(), e = vni_end(); i != e; 630894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++i, ++vnum) { 631894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const VNInfo *vni = *i; 632894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (vnum) OS << " "; 633894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OS << vnum << "@"; 634894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (vni->isUnused()) { 635894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OS << "x"; 636894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 63719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman OS << vni->def; 63819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (vni->isPHIDef()) 63919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman OS << "-phidef"; 640894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (vni->hasPHIKill()) 641894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OS << "-phikill"; 642894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (vni->hasRedefByEC()) 643894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman OS << "-ec"; 644894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 645894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 646894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 647894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 648894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 649894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid LiveInterval::dump() const { 650894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman dbgs() << *this << "\n"; 651894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 652894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 653894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 654894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid LiveRange::print(raw_ostream &os) const { 655894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman os << *this; 656894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 65719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 65819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanunsigned ConnectedVNInfoEqClasses::Classify(const LiveInterval *LI) { 65919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Create initial equivalence classes. 66019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman EqClass.clear(); 66119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman EqClass.grow(LI->getNumValNums()); 66219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 66319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const VNInfo *used = 0, *unused = 0; 66419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 66519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Determine connections. 66619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (LiveInterval::const_vni_iterator I = LI->vni_begin(), E = LI->vni_end(); 66719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman I != E; ++I) { 66819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const VNInfo *VNI = *I; 66919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Group all unused values into one class. 67019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (VNI->isUnused()) { 67119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (unused) 67219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman EqClass.join(unused->id, VNI->id); 67319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unused = VNI; 67419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 67519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 67619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman used = VNI; 67719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (VNI->isPHIDef()) { 67819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def); 67919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(MBB && "Phi-def has no defining MBB"); 68019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Connect to values live out of predecessors. 68119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 68219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman PE = MBB->pred_end(); PI != PE; ++PI) 68319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (const VNInfo *PVNI = 68419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LI->getVNInfoAt(LIS.getMBBEndIdx(*PI).getPrevSlot())) 68519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman EqClass.join(VNI->id, PVNI->id); 68619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 68719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Normal value defined by an instruction. Check for two-addr redef. 68819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // FIXME: This could be coincidental. Should we really check for a tied 68919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // operand constraint? 69019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Note that VNI->def may be a use slot for an early clobber def. 69119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (const VNInfo *UVNI = LI->getVNInfoAt(VNI->def.getPrevSlot())) 69219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman EqClass.join(VNI->id, UVNI->id); 69319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 69419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 69519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 69619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Lump all the unused values in with the last used value. 69719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (used && unused) 69819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman EqClass.join(used->id, unused->id); 69919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 70019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman EqClass.compress(); 70119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return EqClass.getNumClasses(); 70219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 70319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 70419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid ConnectedVNInfoEqClasses::Distribute(LiveInterval *LIV[], 70519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineRegisterInfo &MRI) { 70619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(LIV[0] && "LIV[0] must be set"); 70719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval &LI = *LIV[0]; 70819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 70919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Rewrite instructions. 71019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(LI.reg), 71119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RE = MRI.reg_end(); RI != RE;) { 71219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineOperand &MO = RI.getOperand(); 71319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *MI = MO.getParent(); 71419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++RI; 71519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (MO.isUse() && MO.isUndef()) 71619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 71719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // DBG_VALUE instructions should have been eliminated earlier. 71819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex Idx = LIS.getInstructionIndex(MI); 71919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex(); 72019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const VNInfo *VNI = LI.getVNInfoAt(Idx); 72119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(VNI && "Interval not live at use."); 72219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MO.setReg(LIV[getEqClass(VNI)]->reg); 72319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 72419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 72519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Move runs to new intervals. 72619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval::iterator J = LI.begin(), E = LI.end(); 72719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (J != E && EqClass[J->valno->id] == 0) 72819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++J; 72919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (LiveInterval::iterator I = J; I != E; ++I) { 73019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (unsigned eq = EqClass[I->valno->id]) { 73119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert((LIV[eq]->empty() || LIV[eq]->expiredAt(I->start)) && 73219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "New intervals should be empty"); 73319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LIV[eq]->ranges.push_back(*I); 73419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else 73519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman *J++ = *I; 73619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 73719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LI.ranges.erase(J, E); 73819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 73919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Transfer VNInfos to their new owners and renumber them. 74019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned j = 0, e = LI.getNumValNums(); 74119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (j != e && EqClass[j] == 0) 74219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++j; 74319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = j; i != e; ++i) { 74419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo *VNI = LI.getValNumInfo(i); 74519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (unsigned eq = EqClass[i]) { 74619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNI->id = LIV[eq]->getNumValNums(); 74719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LIV[eq]->valnos.push_back(VNI); 74819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 74919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNI->id = j; 75019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LI.valnos[j++] = VNI; 75119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 75219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 75319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LI.valnos.resize(j); 75419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 755