1fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner//===-- LiveInterval.cpp - Live Interval Representation -------------------===// 2fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 3fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// The LLVM Compiler Infrastructure 4fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 8fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner//===----------------------------------------------------------------------===// 9fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 10fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// This file implements the LiveRange and LiveInterval classes. Given some 11fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// numbering of each the machine instructions an interval [i, j) is said to be a 12fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// live interval for register v if there is no instruction with number j' > j 1386af65552172c9149996600bc3f55bed6f949c8aBob Wilson// such that v is live at j' and there is no instruction with number i' < i such 14fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// that v is live at i'. In this implementation intervals can have holes, 15fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// i.e. an interval might look like [1,20), [50,65), [1000,1001). Each 16fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// individual range is represented as an instance of LiveRange, and the whole 17fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// interval is represented as an instance of LiveInterval. 18fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 19fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner//===----------------------------------------------------------------------===// 20fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 21d9fd2acc1f172e4b8c33c3562667102f9af4d28dBill Wendling#include "llvm/CodeGen/LiveInterval.h" 22d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "RegisterCoalescer.h" 230adb527d169e1f557676fda35bc9abb735e5c912Evan Cheng#include "llvm/ADT/DenseMap.h" 2438b0e7bbf2590f99122a2535d16f34bd12c3bb24Bill Wendling#include "llvm/ADT/STLExtras.h" 25d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallSet.h" 26d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/LiveIntervalAnalysis.h" 27d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineRegisterInfo.h" 285242154b558f0783830938f18153e0a7964fb4faDavid Greene#include "llvm/Support/Debug.h" 29a717b7be8886c4c6ae261ee553c5cbcae29c1e52Daniel Dunbar#include "llvm/Support/raw_ostream.h" 306f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman#include "llvm/Target/TargetRegisterInfo.h" 31c4d3b918165461bc6f5d395bca8d9d9d8a84413dAlkis Evlogimenos#include <algorithm> 32fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattnerusing namespace llvm; 33fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 34f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund OlesenLiveInterval::iterator LiveInterval::find(SlotIndex Pos) { 3555768d763d3d955c07d5819c3ef2e9d1ca6d2bafJakob Stoklund Olesen // This algorithm is basically std::upper_bound. 3655768d763d3d955c07d5819c3ef2e9d1ca6d2bafJakob Stoklund Olesen // Unfortunately, std::upper_bound cannot be used with mixed types until we 3755768d763d3d955c07d5819c3ef2e9d1ca6d2bafJakob Stoklund Olesen // adopt C++0x. Many libraries can do it, but not all. 3855768d763d3d955c07d5819c3ef2e9d1ca6d2bafJakob Stoklund Olesen if (empty() || Pos >= endIndex()) 3955768d763d3d955c07d5819c3ef2e9d1ca6d2bafJakob Stoklund Olesen return end(); 4055768d763d3d955c07d5819c3ef2e9d1ca6d2bafJakob Stoklund Olesen iterator I = begin(); 4155768d763d3d955c07d5819c3ef2e9d1ca6d2bafJakob Stoklund Olesen size_t Len = ranges.size(); 4255768d763d3d955c07d5819c3ef2e9d1ca6d2bafJakob Stoklund Olesen do { 4355768d763d3d955c07d5819c3ef2e9d1ca6d2bafJakob Stoklund Olesen size_t Mid = Len >> 1; 4455768d763d3d955c07d5819c3ef2e9d1ca6d2bafJakob Stoklund Olesen if (Pos < I[Mid].end) 4555768d763d3d955c07d5819c3ef2e9d1ca6d2bafJakob Stoklund Olesen Len = Mid; 4655768d763d3d955c07d5819c3ef2e9d1ca6d2bafJakob Stoklund Olesen else 4755768d763d3d955c07d5819c3ef2e9d1ca6d2bafJakob Stoklund Olesen I += Mid + 1, Len -= Mid + 1; 4855768d763d3d955c07d5819c3ef2e9d1ca6d2bafJakob Stoklund Olesen } while (Len); 4955768d763d3d955c07d5819c3ef2e9d1ca6d2bafJakob Stoklund Olesen return I; 5015a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen} 5115a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen 524e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund OlesenVNInfo *LiveInterval::createDeadDef(SlotIndex Def, 534e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen VNInfo::Allocator &VNInfoAllocator) { 544e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen assert(!Def.isDead() && "Cannot define a value at the dead slot"); 554e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen iterator I = find(Def); 564e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen if (I == end()) { 574e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen VNInfo *VNI = getNextValue(Def, VNInfoAllocator); 584e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen ranges.push_back(LiveRange(Def, Def.getDeadSlot(), VNI)); 594e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen return VNI; 604e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen } 614e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen if (SlotIndex::isSameInstr(Def, I->start)) { 62e42561ad0c98b132515db89f2994c96d93e9587bJakob Stoklund Olesen assert(I->valno->def == I->start && "Inconsistent existing value def"); 63e42561ad0c98b132515db89f2994c96d93e9587bJakob Stoklund Olesen 64e42561ad0c98b132515db89f2994c96d93e9587bJakob Stoklund Olesen // It is possible to have both normal and early-clobber defs of the same 65e42561ad0c98b132515db89f2994c96d93e9587bJakob Stoklund Olesen // register on an instruction. It doesn't make a lot of sense, but it is 66e42561ad0c98b132515db89f2994c96d93e9587bJakob Stoklund Olesen // possible to specify in inline assembly. 67e42561ad0c98b132515db89f2994c96d93e9587bJakob Stoklund Olesen // 68e42561ad0c98b132515db89f2994c96d93e9587bJakob Stoklund Olesen // Just convert everything to early-clobber. 69e42561ad0c98b132515db89f2994c96d93e9587bJakob Stoklund Olesen Def = std::min(Def, I->start); 70e42561ad0c98b132515db89f2994c96d93e9587bJakob Stoklund Olesen if (Def != I->start) 71e42561ad0c98b132515db89f2994c96d93e9587bJakob Stoklund Olesen I->start = I->valno->def = Def; 724e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen return I->valno; 734e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen } 744e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen assert(SlotIndex::isEarlierInstr(Def, I->start) && "Already live at def"); 754e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen VNInfo *VNI = getNextValue(Def, VNInfoAllocator); 764e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen ranges.insert(I, LiveRange(Def, Def.getDeadSlot(), VNI)); 774e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen return VNI; 784e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen} 794e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen 80bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner// overlaps - Return true if the intersection of the two live intervals is 81bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner// not empty. 82bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner// 83fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// An example for overlaps(): 84fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 85fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 0: A = ... 86fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 4: B = ... 87fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 8: C = A + B ;; last use of A 88fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 89fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// The live intervals should look like: 90fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 91fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// A = [3, 11) 92fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// B = [7, x) 93fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// C = [11, y) 94fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 95fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// A->overlaps(C) should return false since we want to be able to join 96fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// A and C. 97bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner// 98bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattnerbool LiveInterval::overlapsFrom(const LiveInterval& other, 99bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator StartPos) const { 1006382d2caddb98f30f556b43faa898ff675affaf7Jakob Stoklund Olesen assert(!empty() && "empty interval"); 101bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator i = begin(); 102bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator ie = end(); 103bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator j = StartPos; 104bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator je = other.end(); 105bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner 106bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner assert((StartPos->start <= i->start || StartPos == other.begin()) && 1078c68b6a226ce46b35eafda972e04bf53128c2615Chris Lattner StartPos != other.end() && "Bogus start position hint!"); 108f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner 109fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i->start < j->start) { 110aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner i = std::upper_bound(i, ie, j->start); 111fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i != ranges.begin()) --i; 112aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner } else if (j->start < i->start) { 113ead1b3f0bb70cd9c1ba7a853a79070cb47db9344Chris Lattner ++StartPos; 114ead1b3f0bb70cd9c1ba7a853a79070cb47db9344Chris Lattner if (StartPos != other.end() && StartPos->start <= i->start) { 115ead1b3f0bb70cd9c1ba7a853a79070cb47db9344Chris Lattner assert(StartPos < other.end() && i < end()); 1168c68b6a226ce46b35eafda972e04bf53128c2615Chris Lattner j = std::upper_bound(j, je, i->start); 1178c68b6a226ce46b35eafda972e04bf53128c2615Chris Lattner if (j != other.ranges.begin()) --j; 1188c68b6a226ce46b35eafda972e04bf53128c2615Chris Lattner } 119aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner } else { 120aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner return true; 121fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 122fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 1239fddc12c9b16a5526b0ee2e6f1da252f7974d7d0Chris Lattner if (j == je) return false; 1249fddc12c9b16a5526b0ee2e6f1da252f7974d7d0Chris Lattner 1259fddc12c9b16a5526b0ee2e6f1da252f7974d7d0Chris Lattner while (i != ie) { 126fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i->start > j->start) { 127a1613db62fec94845aa8306232fb665273615badAlkis Evlogimenos std::swap(i, j); 128a1613db62fec94845aa8306232fb665273615badAlkis Evlogimenos std::swap(ie, je); 129fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 130fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 131fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i->end > j->start) 132fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return true; 133fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner ++i; 134fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 135fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 136fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return false; 137fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 138fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 13945c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesenbool LiveInterval::overlaps(const LiveInterval &Other, 14045c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen const CoalescerPair &CP, 14145c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen const SlotIndexes &Indexes) const { 14245c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen assert(!empty() && "empty interval"); 14345c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen if (Other.empty()) 14445c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen return false; 14545c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen 14645c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen // Use binary searches to find initial positions. 14745c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen const_iterator I = find(Other.beginIndex()); 14845c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen const_iterator IE = end(); 14945c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen if (I == IE) 15045c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen return false; 15145c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen const_iterator J = Other.find(I->start); 15245c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen const_iterator JE = Other.end(); 15345c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen if (J == JE) 15445c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen return false; 15545c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen 15645c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen for (;;) { 15745c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen // J has just been advanced to satisfy: 15845c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen assert(J->end >= I->start); 15945c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen // Check for an overlap. 16045c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen if (J->start < I->end) { 16145c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen // I and J are overlapping. Find the later start. 16245c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen SlotIndex Def = std::max(I->start, J->start); 16345c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen // Allow the overlap if Def is a coalescable copy. 16445c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen if (Def.isBlock() || 16545c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen !CP.isCoalescable(Indexes.getInstructionFromIndex(Def))) 16645c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen return true; 16745c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen } 16845c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen // Advance the iterator that ends first to check for more overlaps. 16945c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen if (J->end > I->end) { 17045c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen std::swap(I, J); 17145c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen std::swap(IE, JE); 17245c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen } 17345c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen // Advance J until J->end >= I->start. 17445c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen do 17545c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen if (++J == JE) 17645c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen return false; 17745c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen while (J->end < I->start); 17845c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen } 17945c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen} 18045c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen 181cccdb2b602cf421d8890130308945163620ebc68Evan Cheng/// overlaps - Return true if the live interval overlaps a range specified 182cccdb2b602cf421d8890130308945163620ebc68Evan Cheng/// by [Start, End). 183233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesbool LiveInterval::overlaps(SlotIndex Start, SlotIndex End) const { 184cccdb2b602cf421d8890130308945163620ebc68Evan Cheng assert(Start < End && "Invalid range"); 185186eb73845c29547cc837341f0c8c0f6d9284e67Jakob Stoklund Olesen const_iterator I = std::lower_bound(begin(), end(), End); 186186eb73845c29547cc837341f0c8c0f6d9284e67Jakob Stoklund Olesen return I != begin() && (--I)->end > Start; 187cccdb2b602cf421d8890130308945163620ebc68Evan Cheng} 188cccdb2b602cf421d8890130308945163620ebc68Evan Cheng 1896f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames 1906f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames/// ValNo is dead, remove it. If it is the largest value number, just nuke it 1916f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames/// (and any other deleted values neighboring it), otherwise mark it as ~1U so 1926f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames/// it can be nuked later. 1936f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hamesvoid LiveInterval::markValNoForDeletion(VNInfo *ValNo) { 1946f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames if (ValNo->id == getNumValNums()-1) { 1956f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames do { 1966f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames valnos.pop_back(); 1976f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames } while (!valnos.empty() && valnos.back()->isUnused()); 1986f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames } else { 199b2beac2b9671f7d9773329d62c2821c8ac449ac5Jakob Stoklund Olesen ValNo->markUnused(); 2006f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames } 2016f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames} 2026f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames 20323436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen/// RenumberValues - Renumber all values in order of appearance and delete the 20423436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen/// remaining unused values. 205fff2c4726baa0d6c9cb184c815677e33c0357c93Jakob Stoklund Olesenvoid LiveInterval::RenumberValues(LiveIntervals &lis) { 20623436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen SmallPtrSet<VNInfo*, 8> Seen; 20723436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen valnos.clear(); 20823436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen for (const_iterator I = begin(), E = end(); I != E; ++I) { 20923436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen VNInfo *VNI = I->valno; 21023436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen if (!Seen.insert(VNI)) 21123436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen continue; 21223436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen assert(!VNI->isUnused() && "Unused valno used by live range"); 21323436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen VNI->id = (unsigned)valnos.size(); 21423436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen valnos.push_back(VNI); 21523436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen } 21623436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen} 21723436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen 218b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// extendIntervalEndTo - This method is used when we want to extend the range 219b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// specified by I to end at the specified endpoint. To do this, we should 220b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// merge and eliminate all ranges that this will overlap with. The iterator is 221b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// not invalidated. 222233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesvoid LiveInterval::extendIntervalEndTo(Ranges::iterator I, SlotIndex NewEnd) { 223b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner assert(I != ranges.end() && "Not a valid interval!"); 2247ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo = I->valno; 225b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 226b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Search for the first interval that we can't merge with. 227ee56c42168f6c4271593f6018c4409b6a5910302Oscar Fuentes Ranges::iterator MergeTo = llvm::next(I); 228abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner for (; MergeTo != ranges.end() && NewEnd >= MergeTo->end; ++MergeTo) { 2297ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); 230abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 231b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 232b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // If NewEnd was in the middle of an interval, make sure to get its endpoint. 233b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner I->end = std::max(NewEnd, prior(MergeTo)->end); 234b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 235b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner // If the newly formed range now touches the range after it and if they have 236b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner // the same value number, merge the two ranges into one range. 23795c88b8cb210ffad127519a143fade685ab21f5bChandler Carruth if (MergeTo != ranges.end() && MergeTo->start <= I->end && 23895c88b8cb210ffad127519a143fade685ab21f5bChandler Carruth MergeTo->valno == ValNo) { 23995c88b8cb210ffad127519a143fade685ab21f5bChandler Carruth I->end = MergeTo->end; 24095c88b8cb210ffad127519a143fade685ab21f5bChandler Carruth ++MergeTo; 241b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner } 24295c88b8cb210ffad127519a143fade685ab21f5bChandler Carruth 24395c88b8cb210ffad127519a143fade685ab21f5bChandler Carruth // Erase any dead ranges. 24495c88b8cb210ffad127519a143fade685ab21f5bChandler Carruth ranges.erase(llvm::next(I), MergeTo); 245fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 246fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 247fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 248b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// extendIntervalStartTo - This method is used when we want to extend the range 249b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// specified by I to start at the specified endpoint. To do this, we should 250b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// merge and eliminate all ranges that this will overlap with. 251edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha BrukmanLiveInterval::Ranges::iterator 252233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang HamesLiveInterval::extendIntervalStartTo(Ranges::iterator I, SlotIndex NewStart) { 253b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner assert(I != ranges.end() && "Not a valid interval!"); 2547ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo = I->valno; 255b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 256b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Search for the first interval that we can't merge with. 257b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner Ranges::iterator MergeTo = I; 258b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner do { 259b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner if (MergeTo == ranges.begin()) { 260b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner I->start = NewStart; 261abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner ranges.erase(MergeTo, I); 262b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner return I; 263b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } 2647ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); 265b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner --MergeTo; 266b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } while (NewStart <= MergeTo->start); 267b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 268b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // If we start in the middle of another interval, just delete a range and 269b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // extend that interval. 2707ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (MergeTo->end >= NewStart && MergeTo->valno == ValNo) { 271b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner MergeTo->end = I->end; 272b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } else { 273b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Otherwise, extend the interval right after. 274b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner ++MergeTo; 275b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner MergeTo->start = NewStart; 276b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner MergeTo->end = I->end; 277fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 278b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 279ee56c42168f6c4271593f6018c4409b6a5910302Oscar Fuentes ranges.erase(llvm::next(MergeTo), llvm::next(I)); 280b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner return MergeTo; 281fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 282fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 283c114b2cad7293d98686d380273085f5c32966b52Chris LattnerLiveInterval::iterator 284c114b2cad7293d98686d380273085f5c32966b52Chris LattnerLiveInterval::addRangeFrom(LiveRange LR, iterator From) { 285233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Start = LR.start, End = LR.end; 286c114b2cad7293d98686d380273085f5c32966b52Chris Lattner iterator it = std::upper_bound(From, ranges.end(), Start); 287b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 288b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // If the inserted interval starts in the middle or right at the end of 289b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // another interval, just extend that interval to contain the range of LR. 290b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner if (it != ranges.begin()) { 291c114b2cad7293d98686d380273085f5c32966b52Chris Lattner iterator B = prior(it); 2927ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (LR.valno == B->valno) { 293abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (B->start <= Start && B->end >= Start) { 294abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner extendIntervalEndTo(B, End); 295abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return B; 296abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 297abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } else { 298abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Check to make sure that we are not overlapping two live ranges with 2997ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng // different valno's. 300abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner assert(B->end <= Start && 3018311befb6968a581a3abdce1e13b5d63922662f7Brian Gaeke "Cannot overlap two LiveRanges with differing ValID's" 3028311befb6968a581a3abdce1e13b5d63922662f7Brian Gaeke " (did you def the same reg twice in a MachineInstr?)"); 303b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } 304fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 305b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 306b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Otherwise, if this range ends in the middle of, or right next to, another 307b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // interval, merge it into that interval. 3084c71dfe356716e6bc1993ef5efdced08b68fe612Anton Korobeynikov if (it != ranges.end()) { 3097ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (LR.valno == it->valno) { 310abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (it->start <= End) { 311abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner it = extendIntervalStartTo(it, Start); 312abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 313abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // If LR is a complete superset of an interval, we may need to grow its 314abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // endpoint as well. 315abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (End > it->end) 316abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner extendIntervalEndTo(it, End); 317abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return it; 318abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 319abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } else { 320abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Check to make sure that we are not overlapping two live ranges with 3217ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng // different valno's. 322abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner assert(it->start >= End && 323abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner "Cannot overlap two LiveRanges with differing ValID's"); 324abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 3254c71dfe356716e6bc1993ef5efdced08b68fe612Anton Korobeynikov } 326b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 327b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Otherwise, this is just a new range that doesn't interact with anything. 328b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Insert it. 329b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner return ranges.insert(it, LR); 330fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 331fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 332ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen/// extendInBlock - If this interval is live before Kill in the basic 333ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen/// block that starts at StartIdx, extend it to be live up to Kill and return 334ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen/// the value. If there is no live range before Kill, return NULL. 335ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund OlesenVNInfo *LiveInterval::extendInBlock(SlotIndex StartIdx, SlotIndex Kill) { 3369763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen if (empty()) 3379763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen return 0; 338ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen iterator I = std::upper_bound(begin(), end(), Kill.getPrevSlot()); 3399763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen if (I == begin()) 3409763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen return 0; 3419763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen --I; 3429763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen if (I->end <= StartIdx) 3439763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen return 0; 344ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen if (I->end < Kill) 345ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen extendIntervalEndTo(I, Kill); 3469763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen return I->valno; 3479763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen} 348abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 349abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner/// removeRange - Remove the specified range from this interval. Note that 35042cc6e33ec0f63560c31f1928c56b4b0465d537cEvan Cheng/// the range must be in a single LiveRange in its entirety. 351233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesvoid LiveInterval::removeRange(SlotIndex Start, SlotIndex End, 352d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng bool RemoveDeadValNo) { 353abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Find the LiveRange containing this span. 354f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen Ranges::iterator I = find(Start); 355f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen assert(I != ranges.end() && "Range is not in interval!"); 3568651125d2885f74546b6e2a556082111d5b75da3Lang Hames assert(I->containsRange(Start, End) && "Range is not entirely in interval!"); 357abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 358abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // If the span we are removing is at the start of the LiveRange, adjust it. 359d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng VNInfo *ValNo = I->valno; 360abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (I->start == Start) { 3614f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng if (I->end == End) { 362d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (RemoveDeadValNo) { 363d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng // Check if val# is dead. 364d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng bool isDead = true; 365d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng for (const_iterator II = begin(), EE = end(); II != EE; ++II) 366d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (II != I && II->valno == ValNo) { 367d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng isDead = false; 368d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng break; 36915a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen } 370d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (isDead) { 3716f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames // Now that ValNo is dead, remove it. 3726f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames markValNoForDeletion(ValNo); 373d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng } 374d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng } 375d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng 376abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner ranges.erase(I); // Removed the whole LiveRange. 3774f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng } else 378abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner I->start = End; 379abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return; 380abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 381abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 382abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Otherwise if the span we are removing is at the end of the LiveRange, 383abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // adjust the other way. 384abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (I->end == End) { 3856925a9f9cc0b9d34cfbc19d9208c416e293ca516Chris Lattner I->end = Start; 386abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return; 387abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 388abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 389abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Otherwise, we are splitting the LiveRange into two pieces. 390233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex OldEnd = I->end; 391abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner I->end = Start; // Trim the old interval. 392abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 393abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Insert the new one. 394ee56c42168f6c4271593f6018c4409b6a5910302Oscar Fuentes ranges.insert(llvm::next(I), LiveRange(End, OldEnd, ValNo)); 395abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner} 396abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 397d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng/// removeValNo - Remove all the ranges defined by the specified value#. 398d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng/// Also remove the value# from value# list. 399d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Chengvoid LiveInterval::removeValNo(VNInfo *ValNo) { 400d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (empty()) return; 401d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng Ranges::iterator I = ranges.end(); 402d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng Ranges::iterator E = ranges.begin(); 403d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng do { 404d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng --I; 405d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (I->valno == ValNo) 406d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng ranges.erase(I); 407d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng } while (I != E); 4086f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames // Now that ValNo is dead, remove it. 4096f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames markValNoForDeletion(ValNo); 410d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng} 4118651125d2885f74546b6e2a556082111d5b75da3Lang Hames 4126d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// join - Join two live intervals (this, and other) together. This applies 4136d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// mappings to the value numbers in the LHS/RHS intervals as specified. If 4146d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// the intervals are not joinable, this aborts. 415233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesvoid LiveInterval::join(LiveInterval &Other, 416233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames const int *LHSValNoAssignments, 4171b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen const int *RHSValNoAssignments, 4189e639e8fd95488cb4c8ef2f7f3a41919acb29ac4Craig Topper SmallVectorImpl<VNInfo *> &NewVNInfo, 41990f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng MachineRegisterInfo *MRI) { 420261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth verify(); 421261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth 4226d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // Determine if any of our live range values are mapped. This is uncommon, so 4231b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen // we want to avoid the interval scan if not. 4246d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner bool MustMapCurValNos = false; 425343013538f72f2202338f57161c0bd92344ca407Evan Cheng unsigned NumVals = getNumValNums(); 426343013538f72f2202338f57161c0bd92344ca407Evan Cheng unsigned NumNewVals = NewVNInfo.size(); 427343013538f72f2202338f57161c0bd92344ca407Evan Cheng for (unsigned i = 0; i != NumVals; ++i) { 428343013538f72f2202338f57161c0bd92344ca407Evan Cheng unsigned LHSValID = LHSValNoAssignments[i]; 429343013538f72f2202338f57161c0bd92344ca407Evan Cheng if (i != LHSValID || 430d88710a3e0847baec0847b802637a48b71718d4dLang Hames (NewVNInfo[LHSValID] && NewVNInfo[LHSValID] != getValNumInfo(i))) { 4316d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner MustMapCurValNos = true; 432d88710a3e0847baec0847b802637a48b71718d4dLang Hames break; 433d88710a3e0847baec0847b802637a48b71718d4dLang Hames } 4346d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 4357ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng 4366d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // If we have to apply a mapping to our base interval assignment, rewrite it 4376d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // now. 438657720bc6ed1f214c4e7f45f80dcc15b2e168288Jakob Stoklund Olesen if (MustMapCurValNos && !empty()) { 4396d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // Map the first live range. 44002e08d5b4d9d368418debaf9ff2b3f07425ee0b6Lang Hames 4416d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner iterator OutIt = begin(); 4427ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng OutIt->valno = NewVNInfo[LHSValNoAssignments[OutIt->valno->id]]; 443fdf45175a8444c421c03627c139777d1de48e516David Blaikie for (iterator I = llvm::next(OutIt), E = end(); I != E; ++I) { 44402e08d5b4d9d368418debaf9ff2b3f07425ee0b6Lang Hames VNInfo* nextValNo = NewVNInfo[LHSValNoAssignments[I->valno->id]]; 44502e08d5b4d9d368418debaf9ff2b3f07425ee0b6Lang Hames assert(nextValNo != 0 && "Huh?"); 4461b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 4476d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // If this live range has the same value # as its immediate predecessor, 4486d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // and if they are neighbors, remove one LiveRange. This happens when we 44902e08d5b4d9d368418debaf9ff2b3f07425ee0b6Lang Hames // have [0,4:0)[4,7:1) and map 0/1 onto the same value #. 45002e08d5b4d9d368418debaf9ff2b3f07425ee0b6Lang Hames if (OutIt->valno == nextValNo && OutIt->end == I->start) { 45102e08d5b4d9d368418debaf9ff2b3f07425ee0b6Lang Hames OutIt->end = I->end; 4526d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } else { 45302e08d5b4d9d368418debaf9ff2b3f07425ee0b6Lang Hames // Didn't merge. Move OutIt to the next interval, 45402e08d5b4d9d368418debaf9ff2b3f07425ee0b6Lang Hames ++OutIt; 45502e08d5b4d9d368418debaf9ff2b3f07425ee0b6Lang Hames OutIt->valno = nextValNo; 45602e08d5b4d9d368418debaf9ff2b3f07425ee0b6Lang Hames if (OutIt != I) { 4576d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner OutIt->start = I->start; 4586d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner OutIt->end = I->end; 4596d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 4606d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 4616d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 4626d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // If we merge some live ranges, chop off the end. 46302e08d5b4d9d368418debaf9ff2b3f07425ee0b6Lang Hames ++OutIt; 4646d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner ranges.erase(OutIt, end()); 465deb9971061cfb9c57930724fcf8d62fb26dc2213Chris Lattner } 4664f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 4679bd7c3cc1306b6b2abc472d1e6ca2f7d0f3f3fbbJakob Stoklund Olesen // Rewrite Other values before changing the VNInfo ids. 4689bd7c3cc1306b6b2abc472d1e6ca2f7d0f3f3fbbJakob Stoklund Olesen // This can leave Other in an invalid state because we're not coalescing 4699bd7c3cc1306b6b2abc472d1e6ca2f7d0f3f3fbbJakob Stoklund Olesen // touching segments that now have identical values. That's OK since Other is 4709bd7c3cc1306b6b2abc472d1e6ca2f7d0f3f3fbbJakob Stoklund Olesen // not supposed to be valid after calling join(); 4717ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng for (iterator I = Other.begin(), E = Other.end(); I != E; ++I) 4729bd7c3cc1306b6b2abc472d1e6ca2f7d0f3f3fbbJakob Stoklund Olesen I->valno = NewVNInfo[RHSValNoAssignments[I->valno->id]]; 4737ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng 4747ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng // Update val# info. Renumber them and make sure they all belong to this 475f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng // LiveInterval now. Also remove dead val#'s. 476f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng unsigned NumValNos = 0; 477f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng for (unsigned i = 0; i < NumNewVals; ++i) { 478343013538f72f2202338f57161c0bd92344ca407Evan Cheng VNInfo *VNI = NewVNInfo[i]; 479f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng if (VNI) { 48030590f502325321958b35bec7295159e3948291aEvan Cheng if (NumValNos >= NumVals) 481f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng valnos.push_back(VNI); 4821b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen else 483f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng valnos[NumValNos] = VNI; 484f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng VNI->id = NumValNos++; // Renumber val#. 485343013538f72f2202338f57161c0bd92344ca407Evan Cheng } 4867ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng } 487343013538f72f2202338f57161c0bd92344ca407Evan Cheng if (NumNewVals < NumVals) 488343013538f72f2202338f57161c0bd92344ca407Evan Cheng valnos.resize(NumNewVals); // shrinkify 4894f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 4906d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // Okay, now insert the RHS live ranges into the LHS. 491d983d4c6ed5ef69ca2d2e07350cc346245f35b87Jakob Stoklund Olesen LiveRangeUpdater Updater(this); 4929bd7c3cc1306b6b2abc472d1e6ca2f7d0f3f3fbbJakob Stoklund Olesen for (iterator I = Other.begin(), E = Other.end(); I != E; ++I) 4939bd7c3cc1306b6b2abc472d1e6ca2f7d0f3f3fbbJakob Stoklund Olesen Updater.add(*I); 494f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner} 495f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 496e585e75612ef5fd32e2bb2c9f635496791a20f8bChandler Carruth/// MergeRangesInAsValue - Merge all of the intervals in RHS into this live 497e585e75612ef5fd32e2bb2c9f635496791a20f8bChandler Carruth/// interval as the specified value number. The LiveRanges in RHS are 498e585e75612ef5fd32e2bb2c9f635496791a20f8bChandler Carruth/// allowed to overlap with LiveRanges in the current interval, but only if 499e585e75612ef5fd32e2bb2c9f635496791a20f8bChandler Carruth/// the overlapping LiveRanges have the specified value number. 500e585e75612ef5fd32e2bb2c9f635496791a20f8bChandler Carruthvoid LiveInterval::MergeRangesInAsValue(const LiveInterval &RHS, 501e585e75612ef5fd32e2bb2c9f635496791a20f8bChandler Carruth VNInfo *LHSValNo) { 502d983d4c6ed5ef69ca2d2e07350cc346245f35b87Jakob Stoklund Olesen LiveRangeUpdater Updater(this); 503d983d4c6ed5ef69ca2d2e07350cc346245f35b87Jakob Stoklund Olesen for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) 504d983d4c6ed5ef69ca2d2e07350cc346245f35b87Jakob Stoklund Olesen Updater.add(I->start, I->end, LHSValNo); 505e585e75612ef5fd32e2bb2c9f635496791a20f8bChandler Carruth} 506f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 50732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng/// MergeValueInAsValue - Merge all of the live ranges of a specific val# 50832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng/// in RHS into this live interval as the specified value number. 50932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng/// The LiveRanges in RHS are allowed to overlap with LiveRanges in the 5103c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng/// current interval, it will replace the value numbers of the overlaped 5113c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng/// live ranges with the specified value number. 512e585e75612ef5fd32e2bb2c9f635496791a20f8bChandler Carruthvoid LiveInterval::MergeValueInAsValue(const LiveInterval &RHS, 513e585e75612ef5fd32e2bb2c9f635496791a20f8bChandler Carruth const VNInfo *RHSValNo, 514e585e75612ef5fd32e2bb2c9f635496791a20f8bChandler Carruth VNInfo *LHSValNo) { 515d983d4c6ed5ef69ca2d2e07350cc346245f35b87Jakob Stoklund Olesen LiveRangeUpdater Updater(this); 516d983d4c6ed5ef69ca2d2e07350cc346245f35b87Jakob Stoklund Olesen for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) 517d983d4c6ed5ef69ca2d2e07350cc346245f35b87Jakob Stoklund Olesen if (I->valno == RHSValNo) 518d983d4c6ed5ef69ca2d2e07350cc346245f35b87Jakob Stoklund Olesen Updater.add(I->start, I->end, LHSValNo); 51932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng} 52032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng 521f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// MergeValueNumberInto - This method is called when two value nubmers 522f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// are found to be equivalent. This eliminates V1, replacing all 523f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// LiveRanges with the V1 value number with the V2 value number. This can 524f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// cause merging of V1/V2 values numbers and compaction of the value space. 5255b93f6fa82e33b17d618b3e24da513f547861481Owen AndersonVNInfo* LiveInterval::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) { 526f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner assert(V1 != V2 && "Identical value#'s are always equivalent!"); 527f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 528f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // This code actually merges the (numerically) larger value number into the 529f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // smaller value number, which is likely to allow us to compactify the value 530f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // space. The only thing we have to be careful of is to preserve the 531f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // instruction that defines the result value. 532f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 533f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Make sure V2 is smaller than V1. 5347ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (V1->id < V2->id) { 53552c1afcaea61440950a11a4ccadac4354420d727Lang Hames V1->copyFrom(*V2); 536f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner std::swap(V1, V2); 537f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 538f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 539f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Merge V1 live ranges into V2. 540f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner for (iterator I = begin(); I != end(); ) { 541f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner iterator LR = I++; 5427ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (LR->valno != V1) continue; // Not a V1 LiveRange. 5431b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 544f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Okay, we found a V1 live range. If it had a previous, touching, V2 live 545f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // range, extend it. 546f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (LR != begin()) { 547f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner iterator Prev = LR-1; 5487ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (Prev->valno == V2 && Prev->end == LR->start) { 549f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner Prev->end = LR->end; 550f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 551f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Erase this live-range. 552f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner ranges.erase(LR); 553f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner I = Prev+1; 554f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner LR = Prev; 555f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 556f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 5571b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 558f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Okay, now we have a V1 or V2 live range that is maximally merged forward. 559f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Ensure that it is a V2 live-range. 5607ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LR->valno = V2; 5611b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 562f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // If we can merge it into later V2 live ranges, do so now. We ignore any 563f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // following V1 live ranges, as they will be merged in subsequent iterations 564f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // of the loop. 565f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (I != end()) { 5667ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (I->start == LR->end && I->valno == V2) { 567f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner LR->end = I->end; 568f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner ranges.erase(I); 569f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner I = LR+1; 570f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 571f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 572f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 5731b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 5746f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames // Now that V1 is dead, remove it. 5756f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames markValNoForDeletion(V1); 5761b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 5775b93f6fa82e33b17d618b3e24da513f547861481Owen Anderson return V2; 578f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner} 579f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 580e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Chengunsigned LiveInterval::getSize() const { 581e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng unsigned Sum = 0; 582e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng for (const_iterator I = begin(), E = end(); I != E; ++I) 5838651125d2885f74546b6e2a556082111d5b75da3Lang Hames Sum += I->start.distance(I->end); 584e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng return Sum; 585e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng} 586e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng 5871cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbarraw_ostream& llvm::operator<<(raw_ostream& os, const LiveRange &LR) { 5881cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar return os << '[' << LR.start << ',' << LR.end << ':' << LR.valno->id << ")"; 5891cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar} 590abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 591b720be6a50f4e1b3280d2b029ee38dda14577525Manman Ren#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 592abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattnervoid LiveRange::dump() const { 5935242154b558f0783830938f18153e0a7964fb4faDavid Greene dbgs() << *this << "\n"; 594fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 59577e300e8f0b8db8eec448cae9c87d7c5bfad9757Manman Ren#endif 596fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 597b77ec7d26405125fa5685370af5f17fcc9edbecdJakob Stoklund Olesenvoid LiveInterval::print(raw_ostream &OS) const { 59838135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner if (empty()) 599b77ec7d26405125fa5685370af5f17fcc9edbecdJakob Stoklund Olesen OS << "EMPTY"; 60038135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner else { 60138135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner for (LiveInterval::Ranges::const_iterator I = ranges.begin(), 602014b8631c0df0c5a91ccee2485bcd408844ed377Jakob Stoklund Olesen E = ranges.end(); I != E; ++I) { 603014b8631c0df0c5a91ccee2485bcd408844ed377Jakob Stoklund Olesen OS << *I; 604014b8631c0df0c5a91ccee2485bcd408844ed377Jakob Stoklund Olesen assert(I->valno == getValNumInfo(I->valno->id) && "Bad VNInfo"); 605014b8631c0df0c5a91ccee2485bcd408844ed377Jakob Stoklund Olesen } 60638135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner } 60715a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen 608be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Print value number info. 6096d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (getNumValNums()) { 610be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner OS << " "; 6111a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng unsigned vnum = 0; 6121a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng for (const_vni_iterator i = vni_begin(), e = vni_end(); i != e; 6131a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng ++i, ++vnum) { 6147ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng const VNInfo *vni = *i; 6151a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng if (vnum) OS << " "; 6161a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng OS << vnum << "@"; 617857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (vni->isUnused()) { 6188df786012dc6b875f31ba4152e09c6e0098082eeEvan Cheng OS << "x"; 619be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner } else { 6206e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames OS << vni->def; 621a818c072af2f94704d08776d5bc7c50a012e40c2Jakob Stoklund Olesen if (vni->isPHIDef()) 622bf60aa9db5953dd99c561dfa9323b1e3293a5a85Jakob Stoklund Olesen OS << "-phi"; 623a8d94f1315f722de056af03763664b77a5baac26Evan Cheng } 624be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner } 625be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner } 626fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 627abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 628b720be6a50f4e1b3280d2b029ee38dda14577525Manman Ren#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 629abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattnervoid LiveInterval::dump() const { 6305242154b558f0783830938f18153e0a7964fb4faDavid Greene dbgs() << *this << "\n"; 631abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner} 63277e300e8f0b8db8eec448cae9c87d7c5bfad9757Manman Ren#endif 633c21c5eeb4f56f160e79522df2d3aab5cfe73c05dJeff Cohen 634261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth#ifndef NDEBUG 635261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruthvoid LiveInterval::verify() const { 636261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth for (const_iterator I = begin(), E = end(); I != E; ++I) { 637261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth assert(I->start.isValid()); 638261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth assert(I->end.isValid()); 639261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth assert(I->start < I->end); 640261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth assert(I->valno != 0); 641261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth assert(I->valno == valnos[I->valno->id]); 642261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth if (llvm::next(I) != E) { 643261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth assert(I->end <= llvm::next(I)->start); 644261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth if (I->end == llvm::next(I)->start) 645261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth assert(I->valno != llvm::next(I)->valno); 646261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth } 647261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth } 648261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth} 649261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth#endif 650261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth 651c21c5eeb4f56f160e79522df2d3aab5cfe73c05dJeff Cohen 6521cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbarvoid LiveRange::print(raw_ostream &os) const { 6531cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar os << *this; 6541cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar} 6550253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 6561a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen//===----------------------------------------------------------------------===// 6571a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// LiveRangeUpdater class 6581a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen//===----------------------------------------------------------------------===// 6591a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// 6601a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// The LiveRangeUpdater class always maintains these invariants: 6611a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// 6621a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// - When LastStart is invalid, Spills is empty and the iterators are invalid. 6631a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// This is the initial state, and the state created by flush(). 6641a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// In this state, isDirty() returns false. 6651a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// 6661a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// Otherwise, segments are kept in three separate areas: 6671a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// 6681a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// 1. [begin; WriteI) at the front of LI. 6691a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// 2. [ReadI; end) at the back of LI. 6701a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// 3. Spills. 6711a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// 6721a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// - LI.begin() <= WriteI <= ReadI <= LI.end(). 6731a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// - Segments in all three areas are fully ordered and coalesced. 6741a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// - Segments in area 1 precede and can't coalesce with segments in area 2. 6751a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// - Segments in Spills precede and can't coalesce with segments in area 2. 6761a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// - No coalescing is possible between segments in Spills and segments in area 6771a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// 1, and there are no overlapping segments. 6781a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// 6791a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// The segments in Spills are not ordered with respect to the segments in area 6801a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// 1. They need to be merged. 6811a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// 6821a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// When they exist, Spills.back().start <= LastStart, 6831a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// and WriteI[-1].start <= LastStart. 6841a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 6851a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesenvoid LiveRangeUpdater::print(raw_ostream &OS) const { 6861a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (!isDirty()) { 6871a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (LI) 6881a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen OS << "Clean " << PrintReg(LI->reg) << " updater: " << *LI << '\n'; 6891a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen else 6901a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen OS << "Null updater.\n"; 6911a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen return; 6921a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen } 6931a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen assert(LI && "Can't have null LI in dirty updater."); 6941a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen OS << PrintReg(LI->reg) << " updater with gap = " << (ReadI - WriteI) 6951a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen << ", last start = " << LastStart 6961a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen << ":\n Area 1:"; 6971a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen for (LiveInterval::const_iterator I = LI->begin(); I != WriteI; ++I) 6981a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen OS << ' ' << *I; 6991a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen OS << "\n Spills:"; 7001a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen for (unsigned I = 0, E = Spills.size(); I != E; ++I) 7011a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen OS << ' ' << Spills[I]; 7021a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen OS << "\n Area 2:"; 7031a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen for (LiveInterval::const_iterator I = ReadI, E = LI->end(); I != E; ++I) 7041a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen OS << ' ' << *I; 7051a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen OS << '\n'; 7061a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen} 7071a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 7081a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesenvoid LiveRangeUpdater::dump() const 7091a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen{ 7101a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen print(errs()); 7111a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen} 7121a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 7131a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// Determine if A and B should be coalesced. 7141a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesenstatic inline bool coalescable(const LiveRange &A, const LiveRange &B) { 7151a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen assert(A.start <= B.start && "Unordered live ranges."); 7161a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (A.end == B.start) 7171a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen return A.valno == B.valno; 7181a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (A.end < B.start) 7191a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen return false; 7201a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen assert(A.valno == B.valno && "Cannot overlap different values"); 7211a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen return true; 7221a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen} 7231a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 7241a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesenvoid LiveRangeUpdater::add(LiveRange Seg) { 7251a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen assert(LI && "Cannot add to a null destination"); 7261a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 7271a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Flush the state if Start moves backwards. 7281a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (!LastStart.isValid() || LastStart > Seg.start) { 7291a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (isDirty()) 7301a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen flush(); 7311a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // This brings us to an uninitialized state. Reinitialize. 7321a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen assert(Spills.empty() && "Leftover spilled segments"); 7331a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen WriteI = ReadI = LI->begin(); 7341a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen } 7351a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 7361a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Remember start for next time. 7371a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen LastStart = Seg.start; 7381a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 7391a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Advance ReadI until it ends after Seg.start. 7401a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen LiveInterval::iterator E = LI->end(); 7411a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (ReadI != E && ReadI->end <= Seg.start) { 7421a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // First try to close the gap between WriteI and ReadI with spills. 7431a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (ReadI != WriteI) 7441a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen mergeSpills(); 7451a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Then advance ReadI. 7461a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (ReadI == WriteI) 7471a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen ReadI = WriteI = LI->find(Seg.start); 7481a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen else 7491a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen while (ReadI != E && ReadI->end <= Seg.start) 7501a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen *WriteI++ = *ReadI++; 7511a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen } 7521a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 7531a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen assert(ReadI == E || ReadI->end > Seg.start); 7541a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 7551a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Check if the ReadI segment begins early. 7561a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (ReadI != E && ReadI->start <= Seg.start) { 7571a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen assert(ReadI->valno == Seg.valno && "Cannot overlap different values"); 7581a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Bail if Seg is completely contained in ReadI. 7591a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (ReadI->end >= Seg.end) 7601a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen return; 7611a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Coalesce into Seg. 7621a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen Seg.start = ReadI->start; 7631a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen ++ReadI; 7641a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen } 7651a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 7661a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Coalesce as much as possible from ReadI into Seg. 7671a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen while (ReadI != E && coalescable(Seg, *ReadI)) { 7681a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen Seg.end = std::max(Seg.end, ReadI->end); 7691a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen ++ReadI; 7701a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen } 7711a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 7721a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Try coalescing Spills.back() into Seg. 7731a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (!Spills.empty() && coalescable(Spills.back(), Seg)) { 7741a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen Seg.start = Spills.back().start; 7751a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen Seg.end = std::max(Spills.back().end, Seg.end); 7761a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen Spills.pop_back(); 7771a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen } 7781a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 7791a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Try coalescing Seg into WriteI[-1]. 7801a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (WriteI != LI->begin() && coalescable(WriteI[-1], Seg)) { 7811a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen WriteI[-1].end = std::max(WriteI[-1].end, Seg.end); 7821a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen return; 7831a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen } 7841a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 7851a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Seg doesn't coalesce with anything, and needs to be inserted somewhere. 7861a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (WriteI != ReadI) { 7871a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen *WriteI++ = Seg; 7881a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen return; 7891a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen } 7901a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 7911a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Finally, append to LI or Spills. 7921a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (WriteI == E) { 7931a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen LI->ranges.push_back(Seg); 7941a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen WriteI = ReadI = LI->ranges.end(); 7951a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen } else 7961a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen Spills.push_back(Seg); 7971a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen} 7981a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 7991a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// Merge as many spilled segments as possible into the gap between WriteI 8001a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// and ReadI. Advance WriteI to reflect the inserted instructions. 8011a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesenvoid LiveRangeUpdater::mergeSpills() { 8021a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Perform a backwards merge of Spills and [SpillI;WriteI). 8031a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen size_t GapSize = ReadI - WriteI; 8041a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen size_t NumMoved = std::min(Spills.size(), GapSize); 8051a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen LiveInterval::iterator Src = WriteI; 8061a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen LiveInterval::iterator Dst = Src + NumMoved; 8071a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen LiveInterval::iterator SpillSrc = Spills.end(); 8081a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen LiveInterval::iterator B = LI->begin(); 8091a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 8101a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // This is the new WriteI position after merging spills. 8111a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen WriteI = Dst; 8121a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 8131a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Now merge Src and Spills backwards. 8141a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen while (Src != Dst) { 8151a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (Src != B && Src[-1].start > SpillSrc[-1].start) 8161a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen *--Dst = *--Src; 8171a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen else 8181a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen *--Dst = *--SpillSrc; 8191a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen } 8201a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen assert(NumMoved == size_t(Spills.end() - SpillSrc)); 8211a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen Spills.erase(SpillSrc, Spills.end()); 8221a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen} 8231a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 8241a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesenvoid LiveRangeUpdater::flush() { 8251a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (!isDirty()) 8261a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen return; 8271a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Clear the dirty state. 8281a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen LastStart = SlotIndex(); 8291a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 8301a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen assert(LI && "Cannot add to a null destination"); 8311a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 8321a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Nothing to merge? 8331a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (Spills.empty()) { 8341a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen LI->ranges.erase(WriteI, ReadI); 8351a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen LI->verify(); 8361a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen return; 8371a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen } 8381a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 8391a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Resize the WriteI - ReadI gap to match Spills. 8401a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen size_t GapSize = ReadI - WriteI; 8411a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (GapSize < Spills.size()) { 8421a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // The gap is too small. Make some room. 8431a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen size_t WritePos = WriteI - LI->begin(); 8441a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen LI->ranges.insert(ReadI, Spills.size() - GapSize, LiveRange()); 8451a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // This also invalidated ReadI, but it is recomputed below. 8461a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen WriteI = LI->ranges.begin() + WritePos; 8471a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen } else { 8481a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Shrink the gap if necessary. 8491a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen LI->ranges.erase(WriteI + Spills.size(), ReadI); 8501a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen } 8511a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen ReadI = WriteI + Spills.size(); 8521a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen mergeSpills(); 8531a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen LI->verify(); 8541a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen} 8551a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 8560253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesenunsigned ConnectedVNInfoEqClasses::Classify(const LiveInterval *LI) { 85754f32e6575d0c1b920ae5151c229f1187bae0cbfJakob Stoklund Olesen // Create initial equivalence classes. 8582254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen EqClass.clear(); 8592254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen EqClass.grow(LI->getNumValNums()); 86054f32e6575d0c1b920ae5151c229f1187bae0cbfJakob Stoklund Olesen 8616d309059a7d6257ddeb3b07e6c4b8b71cce2f707Jakob Stoklund Olesen const VNInfo *used = 0, *unused = 0; 8626d309059a7d6257ddeb3b07e6c4b8b71cce2f707Jakob Stoklund Olesen 86354f32e6575d0c1b920ae5151c229f1187bae0cbfJakob Stoklund Olesen // Determine connections. 8640253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen for (LiveInterval::const_vni_iterator I = LI->vni_begin(), E = LI->vni_end(); 8650253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen I != E; ++I) { 8660253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen const VNInfo *VNI = *I; 8676d309059a7d6257ddeb3b07e6c4b8b71cce2f707Jakob Stoklund Olesen // Group all unused values into one class. 8686d309059a7d6257ddeb3b07e6c4b8b71cce2f707Jakob Stoklund Olesen if (VNI->isUnused()) { 8696d309059a7d6257ddeb3b07e6c4b8b71cce2f707Jakob Stoklund Olesen if (unused) 8702254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen EqClass.join(unused->id, VNI->id); 8716d309059a7d6257ddeb3b07e6c4b8b71cce2f707Jakob Stoklund Olesen unused = VNI; 8726d309059a7d6257ddeb3b07e6c4b8b71cce2f707Jakob Stoklund Olesen continue; 8736d309059a7d6257ddeb3b07e6c4b8b71cce2f707Jakob Stoklund Olesen } 8746d309059a7d6257ddeb3b07e6c4b8b71cce2f707Jakob Stoklund Olesen used = VNI; 8750253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen if (VNI->isPHIDef()) { 8762254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen const MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def); 8770253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen assert(MBB && "Phi-def has no defining MBB"); 8780253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // Connect to values live out of predecessors. 8790253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 8800253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) 881194eb71a11a77c7fb576780783a77e64924dfb10Jakob Stoklund Olesen if (const VNInfo *PVNI = LI->getVNInfoBefore(LIS.getMBBEndIdx(*PI))) 8822254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen EqClass.join(VNI->id, PVNI->id); 8830253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen } else { 8840253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // Normal value defined by an instruction. Check for two-addr redef. 8850253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // FIXME: This could be coincidental. Should we really check for a tied 8860253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // operand constraint? 887b907e8a2d40dc546f21ff7e122a80b121653851aJakob Stoklund Olesen // Note that VNI->def may be a use slot for an early clobber def. 888194eb71a11a77c7fb576780783a77e64924dfb10Jakob Stoklund Olesen if (const VNInfo *UVNI = LI->getVNInfoBefore(VNI->def)) 8892254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen EqClass.join(VNI->id, UVNI->id); 8900253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen } 8910253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen } 8926d309059a7d6257ddeb3b07e6c4b8b71cce2f707Jakob Stoklund Olesen 8936d309059a7d6257ddeb3b07e6c4b8b71cce2f707Jakob Stoklund Olesen // Lump all the unused values in with the last used value. 8946d309059a7d6257ddeb3b07e6c4b8b71cce2f707Jakob Stoklund Olesen if (used && unused) 8952254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen EqClass.join(used->id, unused->id); 8966d309059a7d6257ddeb3b07e6c4b8b71cce2f707Jakob Stoklund Olesen 8972254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen EqClass.compress(); 8982254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen return EqClass.getNumClasses(); 8990253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen} 9000253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 9012254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesenvoid ConnectedVNInfoEqClasses::Distribute(LiveInterval *LIV[], 9022254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen MachineRegisterInfo &MRI) { 9030253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen assert(LIV[0] && "LIV[0] must be set"); 9040253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen LiveInterval &LI = *LIV[0]; 9050253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 9062254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen // Rewrite instructions. 9072254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(LI.reg), 9082254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen RE = MRI.reg_end(); RI != RE;) { 9092254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen MachineOperand &MO = RI.getOperand(); 9102254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen MachineInstr *MI = MO.getParent(); 9112254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen ++RI; 912e0b59774cba9eb89ffba114635f3a1fa075910b1Jakob Stoklund Olesen // DBG_VALUE instructions don't have slot indexes, so get the index of the 913e0b59774cba9eb89ffba114635f3a1fa075910b1Jakob Stoklund Olesen // instruction before them. 914e0b59774cba9eb89ffba114635f3a1fa075910b1Jakob Stoklund Olesen // Normally, DBG_VALUE instructions are removed before this function is 915e0b59774cba9eb89ffba114635f3a1fa075910b1Jakob Stoklund Olesen // called, but it is not a requirement. 916e0b59774cba9eb89ffba114635f3a1fa075910b1Jakob Stoklund Olesen SlotIndex Idx; 917e0b59774cba9eb89ffba114635f3a1fa075910b1Jakob Stoklund Olesen if (MI->isDebugValue()) 918e0b59774cba9eb89ffba114635f3a1fa075910b1Jakob Stoklund Olesen Idx = LIS.getSlotIndexes()->getIndexBefore(MI); 919e0b59774cba9eb89ffba114635f3a1fa075910b1Jakob Stoklund Olesen else 920e0b59774cba9eb89ffba114635f3a1fa075910b1Jakob Stoklund Olesen Idx = LIS.getInstructionIndex(MI); 921e0b59774cba9eb89ffba114635f3a1fa075910b1Jakob Stoklund Olesen LiveRangeQuery LRQ(LI, Idx); 92284315f03cb6127ac92a5b02239c6edc2a347069aJakob Stoklund Olesen const VNInfo *VNI = MO.readsReg() ? LRQ.valueIn() : LRQ.valueDefined(); 92384315f03cb6127ac92a5b02239c6edc2a347069aJakob Stoklund Olesen // In the case of an <undef> use that isn't tied to any def, VNI will be 92484315f03cb6127ac92a5b02239c6edc2a347069aJakob Stoklund Olesen // NULL. If the use is tied to a def, VNI will be the defined value. 925bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen if (!VNI) 926bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen continue; 9272254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen MO.setReg(LIV[getEqClass(VNI)]->reg); 9282254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen } 9292254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen 9302254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen // Move runs to new intervals. 9310253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen LiveInterval::iterator J = LI.begin(), E = LI.end(); 9322254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen while (J != E && EqClass[J->valno->id] == 0) 9330253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen ++J; 9340253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen for (LiveInterval::iterator I = J; I != E; ++I) { 9352254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen if (unsigned eq = EqClass[I->valno->id]) { 936ccefe32141c96faa05445bce0b26f1acd8bdc1b8Benjamin Kramer assert((LIV[eq]->empty() || LIV[eq]->expiredAt(I->start)) && 9370253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen "New intervals should be empty"); 9380253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen LIV[eq]->ranges.push_back(*I); 9390253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen } else 9400253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen *J++ = *I; 9410253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen } 9420253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen LI.ranges.erase(J, E); 9430253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 9440253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // Transfer VNInfos to their new owners and renumber them. 9450253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen unsigned j = 0, e = LI.getNumValNums(); 9462254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen while (j != e && EqClass[j] == 0) 9470253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen ++j; 9480253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen for (unsigned i = j; i != e; ++i) { 9490253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen VNInfo *VNI = LI.getValNumInfo(i); 9502254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen if (unsigned eq = EqClass[i]) { 9510253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen VNI->id = LIV[eq]->getNumValNums(); 9520253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen LIV[eq]->valnos.push_back(VNI); 9530253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen } else { 9540253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen VNI->id = j; 9550253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen LI.valnos[j++] = VNI; 9560253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen } 9570253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen } 9580253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen LI.valnos.resize(j); 9590253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen} 960