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// 1087a86058fa0726328de42ace85b5532d18775646Matthias Braun// 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 1287a86058fa0726328de42ace85b5532d18775646Matthias Braun// live range 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 1487a86058fa0726328de42ace85b5532d18775646Matthias Braun// that v is live at i'. In this implementation ranges can have holes, 1587a86058fa0726328de42ace85b5532d18775646Matthias Braun// i.e. a range might look like [1,20), [50,65), [1000,1001). Each 1687a86058fa0726328de42ace85b5532d18775646Matthias Braun// individual segment is represented as an instance of LiveRange::Segment, 1787a86058fa0726328de42ace85b5532d18775646Matthias Braun// and the whole range is represented as an instance of LiveRange. 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 3487a86058fa0726328de42ace85b5532d18775646Matthias BraunLiveRange::iterator LiveRange::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(); 41b63db853500b3dcb46a96af3f2d5aec003e41d77Matthias Braun size_t Len = 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 5287a86058fa0726328de42ace85b5532d18775646Matthias BraunVNInfo *LiveRange::createDeadDef(SlotIndex Def, 5387a86058fa0726328de42ace85b5532d18775646Matthias Braun 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); 58331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun segments.push_back(Segment(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); 76331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun segments.insert(I, Segment(Def, Def.getDeadSlot(), VNI)); 774e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen return VNI; 784e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen} 794e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen 8087a86058fa0726328de42ace85b5532d18775646Matthias Braun// overlaps - Return true if the intersection of the two live ranges 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// 8987a86058fa0726328de42ace85b5532d18775646Matthias Braun// The live ranges 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// 9887a86058fa0726328de42ace85b5532d18775646Matthias Braunbool LiveRange::overlapsFrom(const LiveRange& other, 9987a86058fa0726328de42ace85b5532d18775646Matthias Braun const_iterator StartPos) const { 10087a86058fa0726328de42ace85b5532d18775646Matthias Braun assert(!empty() && "empty range"); 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); 111b63db853500b3dcb46a96af3f2d5aec003e41d77Matthias Braun if (i != 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); 117b63db853500b3dcb46a96af3f2d5aec003e41d77Matthias Braun if (j != other.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 13987a86058fa0726328de42ace85b5532d18775646Matthias Braunbool LiveRange::overlaps(const LiveRange &Other, const CoalescerPair &CP, 14087a86058fa0726328de42ace85b5532d18775646Matthias Braun const SlotIndexes &Indexes) const { 14187a86058fa0726328de42ace85b5532d18775646Matthias Braun assert(!empty() && "empty range"); 14245c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen if (Other.empty()) 14345c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen return false; 14445c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen 14545c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen // Use binary searches to find initial positions. 14645c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen const_iterator I = find(Other.beginIndex()); 14745c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen const_iterator IE = end(); 14845c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen if (I == IE) 14945c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen return false; 15045c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen const_iterator J = Other.find(I->start); 15145c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen const_iterator JE = Other.end(); 15245c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen if (J == JE) 15345c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen return false; 15445c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen 15545c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen for (;;) { 15645c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen // J has just been advanced to satisfy: 15745c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen assert(J->end >= I->start); 15845c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen // Check for an overlap. 15945c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen if (J->start < I->end) { 16045c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen // I and J are overlapping. Find the later start. 16145c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen SlotIndex Def = std::max(I->start, J->start); 16245c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen // Allow the overlap if Def is a coalescable copy. 16345c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen if (Def.isBlock() || 16445c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen !CP.isCoalescable(Indexes.getInstructionFromIndex(Def))) 16545c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen return true; 16645c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen } 16745c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen // Advance the iterator that ends first to check for more overlaps. 16845c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen if (J->end > I->end) { 16945c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen std::swap(I, J); 17045c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen std::swap(IE, JE); 17145c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen } 17245c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen // Advance J until J->end >= I->start. 17345c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen do 17445c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen if (++J == JE) 17545c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen return false; 17645c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen while (J->end < I->start); 17745c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen } 17845c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen} 17945c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen 18087a86058fa0726328de42ace85b5532d18775646Matthias Braun/// overlaps - Return true if the live range overlaps an interval specified 181cccdb2b602cf421d8890130308945163620ebc68Evan Cheng/// by [Start, End). 18287a86058fa0726328de42ace85b5532d18775646Matthias Braunbool LiveRange::overlaps(SlotIndex Start, SlotIndex End) const { 183cccdb2b602cf421d8890130308945163620ebc68Evan Cheng assert(Start < End && "Invalid range"); 184186eb73845c29547cc837341f0c8c0f6d9284e67Jakob Stoklund Olesen const_iterator I = std::lower_bound(begin(), end(), End); 185186eb73845c29547cc837341f0c8c0f6d9284e67Jakob Stoklund Olesen return I != begin() && (--I)->end > Start; 186cccdb2b602cf421d8890130308945163620ebc68Evan Cheng} 187cccdb2b602cf421d8890130308945163620ebc68Evan Cheng 1886f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames 1896f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames/// ValNo is dead, remove it. If it is the largest value number, just nuke it 1906f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames/// (and any other deleted values neighboring it), otherwise mark it as ~1U so 1916f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames/// it can be nuked later. 19287a86058fa0726328de42ace85b5532d18775646Matthias Braunvoid LiveRange::markValNoForDeletion(VNInfo *ValNo) { 1936f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames if (ValNo->id == getNumValNums()-1) { 1946f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames do { 1956f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames valnos.pop_back(); 1966f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames } while (!valnos.empty() && valnos.back()->isUnused()); 1976f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames } else { 198b2beac2b9671f7d9773329d62c2821c8ac449ac5Jakob Stoklund Olesen ValNo->markUnused(); 1996f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames } 2006f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames} 2016f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames 20223436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen/// RenumberValues - Renumber all values in order of appearance and delete the 20323436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen/// remaining unused values. 20487a86058fa0726328de42ace85b5532d18775646Matthias Braunvoid LiveRange::RenumberValues() { 20523436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen SmallPtrSet<VNInfo*, 8> Seen; 20623436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen valnos.clear(); 20723436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen for (const_iterator I = begin(), E = end(); I != E; ++I) { 20823436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen VNInfo *VNI = I->valno; 20923436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen if (!Seen.insert(VNI)) 21023436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen continue; 211331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun assert(!VNI->isUnused() && "Unused valno used by live segment"); 21223436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen VNI->id = (unsigned)valnos.size(); 21323436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen valnos.push_back(VNI); 21423436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen } 21523436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen} 21623436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen 217331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun/// This method is used when we want to extend the segment specified by I to end 218331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun/// at the specified endpoint. To do this, we should merge and eliminate all 219331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun/// segments that this will overlap with. The iterator is not invalidated. 22087a86058fa0726328de42ace85b5532d18775646Matthias Braunvoid LiveRange::extendSegmentEndTo(iterator I, SlotIndex NewEnd) { 221331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun assert(I != end() && "Not a valid segment!"); 2227ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo = I->valno; 223b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 224331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun // Search for the first segment that we can't merge with. 22536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines iterator MergeTo = std::next(I); 226b63db853500b3dcb46a96af3f2d5aec003e41d77Matthias Braun for (; MergeTo != end() && NewEnd >= MergeTo->end; ++MergeTo) { 2277ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); 228abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 229b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 23087a86058fa0726328de42ace85b5532d18775646Matthias Braun // If NewEnd was in the middle of a segment, make sure to get its endpoint. 23136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines I->end = std::max(NewEnd, std::prev(MergeTo)->end); 232b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 233331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun // If the newly formed segment now touches the segment after it and if they 234331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun // have the same value number, merge the two segments into one segment. 235b63db853500b3dcb46a96af3f2d5aec003e41d77Matthias Braun if (MergeTo != end() && MergeTo->start <= I->end && 23695c88b8cb210ffad127519a143fade685ab21f5bChandler Carruth MergeTo->valno == ValNo) { 23795c88b8cb210ffad127519a143fade685ab21f5bChandler Carruth I->end = MergeTo->end; 23895c88b8cb210ffad127519a143fade685ab21f5bChandler Carruth ++MergeTo; 239b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner } 24095c88b8cb210ffad127519a143fade685ab21f5bChandler Carruth 241331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun // Erase any dead segments. 24236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines segments.erase(std::next(I), MergeTo); 243fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 244fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 245fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 246331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun/// This method is used when we want to extend the segment specified by I to 247331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun/// start at the specified endpoint. To do this, we should merge and eliminate 248331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun/// all segments that this will overlap with. 24987a86058fa0726328de42ace85b5532d18775646Matthias BraunLiveRange::iterator 25087a86058fa0726328de42ace85b5532d18775646Matthias BraunLiveRange::extendSegmentStartTo(iterator I, SlotIndex NewStart) { 251331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun assert(I != end() && "Not a valid segment!"); 2527ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo = I->valno; 253b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 254331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun // Search for the first segment that we can't merge with. 255b63db853500b3dcb46a96af3f2d5aec003e41d77Matthias Braun iterator MergeTo = I; 256b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner do { 257b63db853500b3dcb46a96af3f2d5aec003e41d77Matthias Braun if (MergeTo == begin()) { 258b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner I->start = NewStart; 259331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun segments.erase(MergeTo, I); 260b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner return I; 261b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } 2627ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); 263b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner --MergeTo; 264b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } while (NewStart <= MergeTo->start); 265b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 266331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun // If we start in the middle of another segment, just delete a range and 267331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun // extend that segment. 2687ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (MergeTo->end >= NewStart && MergeTo->valno == ValNo) { 269b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner MergeTo->end = I->end; 270b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } else { 271331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun // Otherwise, extend the segment right after. 272b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner ++MergeTo; 273b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner MergeTo->start = NewStart; 274b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner MergeTo->end = I->end; 275fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 276b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 27736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines segments.erase(std::next(MergeTo), std::next(I)); 278b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner return MergeTo; 279fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 280fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 28187a86058fa0726328de42ace85b5532d18775646Matthias BraunLiveRange::iterator LiveRange::addSegmentFrom(Segment S, iterator From) { 282331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun SlotIndex Start = S.start, End = S.end; 283b63db853500b3dcb46a96af3f2d5aec003e41d77Matthias Braun iterator it = std::upper_bound(From, end(), Start); 284b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 285331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun // If the inserted segment starts in the middle or right at the end of 286331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun // another segment, just extend that segment to contain the segment of S. 287b63db853500b3dcb46a96af3f2d5aec003e41d77Matthias Braun if (it != begin()) { 28836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines iterator B = std::prev(it); 289331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun if (S.valno == B->valno) { 290abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (B->start <= Start && B->end >= Start) { 291331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun extendSegmentEndTo(B, End); 292abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return B; 293abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 294abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } else { 295331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun // Check to make sure that we are not overlapping two live segments with 2967ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng // different valno's. 297abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner assert(B->end <= Start && 298331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun "Cannot overlap two segments with differing ValID's" 2998311befb6968a581a3abdce1e13b5d63922662f7Brian Gaeke " (did you def the same reg twice in a MachineInstr?)"); 300b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } 301fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 302b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 303331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun // Otherwise, if this segment ends in the middle of, or right next to, another 304331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun // segment, merge it into that segment. 305b63db853500b3dcb46a96af3f2d5aec003e41d77Matthias Braun if (it != end()) { 306331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun if (S.valno == it->valno) { 307abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (it->start <= End) { 308331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun it = extendSegmentStartTo(it, Start); 309abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 310331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun // If S is a complete superset of a segment, we may need to grow its 311abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // endpoint as well. 312abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (End > it->end) 313331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun extendSegmentEndTo(it, End); 314abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return it; 315abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 316abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } else { 317331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun // Check to make sure that we are not overlapping two live segments with 3187ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng // different valno's. 319abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner assert(it->start >= End && 320331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun "Cannot overlap two segments with differing ValID's"); 321abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 3224c71dfe356716e6bc1993ef5efdced08b68fe612Anton Korobeynikov } 323b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 324331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun // Otherwise, this is just a new segment that doesn't interact with anything. 325b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Insert it. 326331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun return segments.insert(it, S); 327fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 328fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 32987a86058fa0726328de42ace85b5532d18775646Matthias Braun/// extendInBlock - If this range is live before Kill in the basic 330ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen/// block that starts at StartIdx, extend it to be live up to Kill and return 33187a86058fa0726328de42ace85b5532d18775646Matthias Braun/// the value. If there is no live range before Kill, return NULL. 33287a86058fa0726328de42ace85b5532d18775646Matthias BraunVNInfo *LiveRange::extendInBlock(SlotIndex StartIdx, SlotIndex Kill) { 3339763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen if (empty()) 334dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 335ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen iterator I = std::upper_bound(begin(), end(), Kill.getPrevSlot()); 3369763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen if (I == begin()) 337dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 3389763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen --I; 3399763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen if (I->end <= StartIdx) 340dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 341ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen if (I->end < Kill) 342331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun extendSegmentEndTo(I, Kill); 3439763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen return I->valno; 3449763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen} 345abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 34687a86058fa0726328de42ace85b5532d18775646Matthias Braun/// Remove the specified segment from this range. Note that the segment must 347331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun/// be in a single Segment in its entirety. 34887a86058fa0726328de42ace85b5532d18775646Matthias Braunvoid LiveRange::removeSegment(SlotIndex Start, SlotIndex End, 34987a86058fa0726328de42ace85b5532d18775646Matthias Braun bool RemoveDeadValNo) { 350331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun // Find the Segment containing this span. 351b63db853500b3dcb46a96af3f2d5aec003e41d77Matthias Braun iterator I = find(Start); 35287a86058fa0726328de42ace85b5532d18775646Matthias Braun assert(I != end() && "Segment is not in range!"); 353331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun assert(I->containsInterval(Start, End) 35487a86058fa0726328de42ace85b5532d18775646Matthias Braun && "Segment is not entirely in range!"); 355abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 356331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun // If the span we are removing is at the start of the Segment, adjust it. 357d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng VNInfo *ValNo = I->valno; 358abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (I->start == Start) { 3594f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng if (I->end == End) { 360d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (RemoveDeadValNo) { 361d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng // Check if val# is dead. 362d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng bool isDead = true; 363d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng for (const_iterator II = begin(), EE = end(); II != EE; ++II) 364d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (II != I && II->valno == ValNo) { 365d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng isDead = false; 366d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng break; 36715a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen } 368d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (isDead) { 3696f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames // Now that ValNo is dead, remove it. 3706f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames markValNoForDeletion(ValNo); 371d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng } 372d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng } 373d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng 374331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun segments.erase(I); // Removed the whole Segment. 3754f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng } else 376abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner I->start = End; 377abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return; 378abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 379abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 380331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun // Otherwise if the span we are removing is at the end of the Segment, 381abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // adjust the other way. 382abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (I->end == End) { 3836925a9f9cc0b9d34cfbc19d9208c416e293ca516Chris Lattner I->end = Start; 384abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return; 385abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 386abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 387331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun // Otherwise, we are splitting the Segment into two pieces. 388233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex OldEnd = I->end; 38987a86058fa0726328de42ace85b5532d18775646Matthias Braun I->end = Start; // Trim the old segment. 390abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 391abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Insert the new one. 39236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines segments.insert(std::next(I), Segment(End, OldEnd, ValNo)); 393abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner} 394abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 395331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun/// removeValNo - Remove all the segments defined by the specified value#. 396d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng/// Also remove the value# from value# list. 39787a86058fa0726328de42ace85b5532d18775646Matthias Braunvoid LiveRange::removeValNo(VNInfo *ValNo) { 398d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (empty()) return; 399b63db853500b3dcb46a96af3f2d5aec003e41d77Matthias Braun iterator I = end(); 400b63db853500b3dcb46a96af3f2d5aec003e41d77Matthias Braun iterator E = begin(); 401d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng do { 402d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng --I; 403d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (I->valno == ValNo) 404331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun segments.erase(I); 405d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng } while (I != E); 4066f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames // Now that ValNo is dead, remove it. 4076f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames markValNoForDeletion(ValNo); 408d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng} 4098651125d2885f74546b6e2a556082111d5b75da3Lang Hames 41087a86058fa0726328de42ace85b5532d18775646Matthias Braunvoid LiveRange::join(LiveRange &Other, 41187a86058fa0726328de42ace85b5532d18775646Matthias Braun const int *LHSValNoAssignments, 41287a86058fa0726328de42ace85b5532d18775646Matthias Braun const int *RHSValNoAssignments, 41387a86058fa0726328de42ace85b5532d18775646Matthias Braun SmallVectorImpl<VNInfo *> &NewVNInfo) { 414261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth verify(); 415261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth 416331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun // Determine if any of our values are mapped. This is uncommon, so we want 41787a86058fa0726328de42ace85b5532d18775646Matthias Braun // to avoid the range scan if not. 4186d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner bool MustMapCurValNos = false; 419343013538f72f2202338f57161c0bd92344ca407Evan Cheng unsigned NumVals = getNumValNums(); 420343013538f72f2202338f57161c0bd92344ca407Evan Cheng unsigned NumNewVals = NewVNInfo.size(); 421343013538f72f2202338f57161c0bd92344ca407Evan Cheng for (unsigned i = 0; i != NumVals; ++i) { 422343013538f72f2202338f57161c0bd92344ca407Evan Cheng unsigned LHSValID = LHSValNoAssignments[i]; 423343013538f72f2202338f57161c0bd92344ca407Evan Cheng if (i != LHSValID || 424d88710a3e0847baec0847b802637a48b71718d4dLang Hames (NewVNInfo[LHSValID] && NewVNInfo[LHSValID] != getValNumInfo(i))) { 4256d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner MustMapCurValNos = true; 426d88710a3e0847baec0847b802637a48b71718d4dLang Hames break; 427d88710a3e0847baec0847b802637a48b71718d4dLang Hames } 4286d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 4297ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng 43087a86058fa0726328de42ace85b5532d18775646Matthias Braun // If we have to apply a mapping to our base range assignment, rewrite it now. 431657720bc6ed1f214c4e7f45f80dcc15b2e168288Jakob Stoklund Olesen if (MustMapCurValNos && !empty()) { 4326d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // Map the first live range. 43302e08d5b4d9d368418debaf9ff2b3f07425ee0b6Lang Hames 4346d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner iterator OutIt = begin(); 4357ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng OutIt->valno = NewVNInfo[LHSValNoAssignments[OutIt->valno->id]]; 43636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (iterator I = std::next(OutIt), E = end(); I != E; ++I) { 43702e08d5b4d9d368418debaf9ff2b3f07425ee0b6Lang Hames VNInfo* nextValNo = NewVNInfo[LHSValNoAssignments[I->valno->id]]; 438dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(nextValNo && "Huh?"); 4391b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 4406d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // If this live range has the same value # as its immediate predecessor, 441331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun // and if they are neighbors, remove one Segment. This happens when we 44202e08d5b4d9d368418debaf9ff2b3f07425ee0b6Lang Hames // have [0,4:0)[4,7:1) and map 0/1 onto the same value #. 44302e08d5b4d9d368418debaf9ff2b3f07425ee0b6Lang Hames if (OutIt->valno == nextValNo && OutIt->end == I->start) { 44402e08d5b4d9d368418debaf9ff2b3f07425ee0b6Lang Hames OutIt->end = I->end; 4456d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } else { 44687a86058fa0726328de42ace85b5532d18775646Matthias Braun // Didn't merge. Move OutIt to the next segment, 44702e08d5b4d9d368418debaf9ff2b3f07425ee0b6Lang Hames ++OutIt; 44802e08d5b4d9d368418debaf9ff2b3f07425ee0b6Lang Hames OutIt->valno = nextValNo; 44902e08d5b4d9d368418debaf9ff2b3f07425ee0b6Lang Hames if (OutIt != I) { 4506d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner OutIt->start = I->start; 4516d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner OutIt->end = I->end; 4526d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 4536d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 4546d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 455331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun // If we merge some segments, chop off the end. 45602e08d5b4d9d368418debaf9ff2b3f07425ee0b6Lang Hames ++OutIt; 457331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun segments.erase(OutIt, end()); 458deb9971061cfb9c57930724fcf8d62fb26dc2213Chris Lattner } 4594f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 4609bd7c3cc1306b6b2abc472d1e6ca2f7d0f3f3fbbJakob Stoklund Olesen // Rewrite Other values before changing the VNInfo ids. 4619bd7c3cc1306b6b2abc472d1e6ca2f7d0f3f3fbbJakob Stoklund Olesen // This can leave Other in an invalid state because we're not coalescing 4629bd7c3cc1306b6b2abc472d1e6ca2f7d0f3f3fbbJakob Stoklund Olesen // touching segments that now have identical values. That's OK since Other is 4639bd7c3cc1306b6b2abc472d1e6ca2f7d0f3f3fbbJakob Stoklund Olesen // not supposed to be valid after calling join(); 4647ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng for (iterator I = Other.begin(), E = Other.end(); I != E; ++I) 4659bd7c3cc1306b6b2abc472d1e6ca2f7d0f3f3fbbJakob Stoklund Olesen I->valno = NewVNInfo[RHSValNoAssignments[I->valno->id]]; 4667ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng 4677ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng // Update val# info. Renumber them and make sure they all belong to this 46887a86058fa0726328de42ace85b5532d18775646Matthias Braun // LiveRange now. Also remove dead val#'s. 469f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng unsigned NumValNos = 0; 470f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng for (unsigned i = 0; i < NumNewVals; ++i) { 471343013538f72f2202338f57161c0bd92344ca407Evan Cheng VNInfo *VNI = NewVNInfo[i]; 472f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng if (VNI) { 47330590f502325321958b35bec7295159e3948291aEvan Cheng if (NumValNos >= NumVals) 474f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng valnos.push_back(VNI); 4751b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen else 476f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng valnos[NumValNos] = VNI; 477f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng VNI->id = NumValNos++; // Renumber val#. 478343013538f72f2202338f57161c0bd92344ca407Evan Cheng } 4797ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng } 480343013538f72f2202338f57161c0bd92344ca407Evan Cheng if (NumNewVals < NumVals) 481343013538f72f2202338f57161c0bd92344ca407Evan Cheng valnos.resize(NumNewVals); // shrinkify 4824f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 483331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun // Okay, now insert the RHS live segments into the LHS. 484d983d4c6ed5ef69ca2d2e07350cc346245f35b87Jakob Stoklund Olesen LiveRangeUpdater Updater(this); 4859bd7c3cc1306b6b2abc472d1e6ca2f7d0f3f3fbbJakob Stoklund Olesen for (iterator I = Other.begin(), E = Other.end(); I != E; ++I) 4869bd7c3cc1306b6b2abc472d1e6ca2f7d0f3f3fbbJakob Stoklund Olesen Updater.add(*I); 487f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner} 488f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 48987a86058fa0726328de42ace85b5532d18775646Matthias Braun/// Merge all of the segments in RHS into this live range as the specified 490331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun/// value number. The segments in RHS are allowed to overlap with segments in 49187a86058fa0726328de42ace85b5532d18775646Matthias Braun/// the current range, but only if the overlapping segments have the 492331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun/// specified value number. 49387a86058fa0726328de42ace85b5532d18775646Matthias Braunvoid LiveRange::MergeSegmentsInAsValue(const LiveRange &RHS, 49487a86058fa0726328de42ace85b5532d18775646Matthias Braun VNInfo *LHSValNo) { 495d983d4c6ed5ef69ca2d2e07350cc346245f35b87Jakob Stoklund Olesen LiveRangeUpdater Updater(this); 496d983d4c6ed5ef69ca2d2e07350cc346245f35b87Jakob Stoklund Olesen for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) 497d983d4c6ed5ef69ca2d2e07350cc346245f35b87Jakob Stoklund Olesen Updater.add(I->start, I->end, LHSValNo); 498e585e75612ef5fd32e2bb2c9f635496791a20f8bChandler Carruth} 499f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 500331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun/// MergeValueInAsValue - Merge all of the live segments of a specific val# 50187a86058fa0726328de42ace85b5532d18775646Matthias Braun/// in RHS into this live range as the specified value number. 502331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun/// The segments in RHS are allowed to overlap with segments in the 50387a86058fa0726328de42ace85b5532d18775646Matthias Braun/// current range, it will replace the value numbers of the overlaped 504331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun/// segments with the specified value number. 50587a86058fa0726328de42ace85b5532d18775646Matthias Braunvoid LiveRange::MergeValueInAsValue(const LiveRange &RHS, 50687a86058fa0726328de42ace85b5532d18775646Matthias Braun const VNInfo *RHSValNo, 50787a86058fa0726328de42ace85b5532d18775646Matthias Braun VNInfo *LHSValNo) { 508d983d4c6ed5ef69ca2d2e07350cc346245f35b87Jakob Stoklund Olesen LiveRangeUpdater Updater(this); 509d983d4c6ed5ef69ca2d2e07350cc346245f35b87Jakob Stoklund Olesen for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) 510d983d4c6ed5ef69ca2d2e07350cc346245f35b87Jakob Stoklund Olesen if (I->valno == RHSValNo) 511d983d4c6ed5ef69ca2d2e07350cc346245f35b87Jakob Stoklund Olesen Updater.add(I->start, I->end, LHSValNo); 51232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng} 51332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng 514f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// MergeValueNumberInto - This method is called when two value nubmers 515f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// are found to be equivalent. This eliminates V1, replacing all 516331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun/// segments with the V1 value number with the V2 value number. This can 517f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// cause merging of V1/V2 values numbers and compaction of the value space. 51887a86058fa0726328de42ace85b5532d18775646Matthias BraunVNInfo *LiveRange::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) { 519f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner assert(V1 != V2 && "Identical value#'s are always equivalent!"); 520f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 521f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // This code actually merges the (numerically) larger value number into the 522f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // smaller value number, which is likely to allow us to compactify the value 523f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // space. The only thing we have to be careful of is to preserve the 524f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // instruction that defines the result value. 525f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 526f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Make sure V2 is smaller than V1. 5277ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (V1->id < V2->id) { 52852c1afcaea61440950a11a4ccadac4354420d727Lang Hames V1->copyFrom(*V2); 529f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner std::swap(V1, V2); 530f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 531f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 532331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun // Merge V1 segments into V2. 533f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner for (iterator I = begin(); I != end(); ) { 534331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun iterator S = I++; 535331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun if (S->valno != V1) continue; // Not a V1 Segment. 5361b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 537f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Okay, we found a V1 live range. If it had a previous, touching, V2 live 538f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // range, extend it. 539331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun if (S != begin()) { 540331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun iterator Prev = S-1; 541331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun if (Prev->valno == V2 && Prev->end == S->start) { 542331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun Prev->end = S->end; 543f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 544f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Erase this live-range. 545331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun segments.erase(S); 546f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner I = Prev+1; 547331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun S = Prev; 548f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 549f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 5501b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 551f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Okay, now we have a V1 or V2 live range that is maximally merged forward. 552f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Ensure that it is a V2 live-range. 553331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun S->valno = V2; 5541b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 555331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun // If we can merge it into later V2 segments, do so now. We ignore any 556331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun // following V1 segments, as they will be merged in subsequent iterations 557f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // of the loop. 558f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (I != end()) { 559331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun if (I->start == S->end && I->valno == V2) { 560331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun S->end = I->end; 561331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun segments.erase(I); 562331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun I = S+1; 563f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 564f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 565f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 5661b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 5676f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames // Now that V1 is dead, remove it. 5686f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames markValNoForDeletion(V1); 5691b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 5705b93f6fa82e33b17d618b3e24da513f547861481Owen Anderson return V2; 571f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner} 572f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 573e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Chengunsigned LiveInterval::getSize() const { 574e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng unsigned Sum = 0; 575e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng for (const_iterator I = begin(), E = end(); I != E; ++I) 5768651125d2885f74546b6e2a556082111d5b75da3Lang Hames Sum += I->start.distance(I->end); 577e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng return Sum; 578e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng} 579e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng 58087a86058fa0726328de42ace85b5532d18775646Matthias Braunraw_ostream& llvm::operator<<(raw_ostream& os, const LiveRange::Segment &S) { 581331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun return os << '[' << S.start << ',' << S.end << ':' << S.valno->id << ")"; 5821cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar} 583abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 584b720be6a50f4e1b3280d2b029ee38dda14577525Manman Ren#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 58587a86058fa0726328de42ace85b5532d18775646Matthias Braunvoid LiveRange::Segment::dump() const { 5865242154b558f0783830938f18153e0a7964fb4faDavid Greene dbgs() << *this << "\n"; 587fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 58877e300e8f0b8db8eec448cae9c87d7c5bfad9757Manman Ren#endif 589fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 59087a86058fa0726328de42ace85b5532d18775646Matthias Braunvoid LiveRange::print(raw_ostream &OS) const { 59138135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner if (empty()) 592b77ec7d26405125fa5685370af5f17fcc9edbecdJakob Stoklund Olesen OS << "EMPTY"; 59338135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner else { 594b63db853500b3dcb46a96af3f2d5aec003e41d77Matthias Braun for (const_iterator I = begin(), E = end(); I != E; ++I) { 595014b8631c0df0c5a91ccee2485bcd408844ed377Jakob Stoklund Olesen OS << *I; 596014b8631c0df0c5a91ccee2485bcd408844ed377Jakob Stoklund Olesen assert(I->valno == getValNumInfo(I->valno->id) && "Bad VNInfo"); 597014b8631c0df0c5a91ccee2485bcd408844ed377Jakob Stoklund Olesen } 59838135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner } 59915a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen 600be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Print value number info. 6016d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (getNumValNums()) { 602be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner OS << " "; 6031a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng unsigned vnum = 0; 6041a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng for (const_vni_iterator i = vni_begin(), e = vni_end(); i != e; 6051a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng ++i, ++vnum) { 6067ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng const VNInfo *vni = *i; 6071a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng if (vnum) OS << " "; 6081a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng OS << vnum << "@"; 609857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (vni->isUnused()) { 6108df786012dc6b875f31ba4152e09c6e0098082eeEvan Cheng OS << "x"; 611be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner } else { 6126e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames OS << vni->def; 613a818c072af2f94704d08776d5bc7c50a012e40c2Jakob Stoklund Olesen if (vni->isPHIDef()) 614bf60aa9db5953dd99c561dfa9323b1e3293a5a85Jakob Stoklund Olesen OS << "-phi"; 615a8d94f1315f722de056af03763664b77a5baac26Evan Cheng } 616be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner } 617be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner } 618fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 619abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 62003d9609c6154ed91daefb4e4f89b7298c11961f3Matthias Braunvoid LiveInterval::print(raw_ostream &OS) const { 62103d9609c6154ed91daefb4e4f89b7298c11961f3Matthias Braun OS << PrintReg(reg) << ' '; 62203d9609c6154ed91daefb4e4f89b7298c11961f3Matthias Braun super::print(OS); 62303d9609c6154ed91daefb4e4f89b7298c11961f3Matthias Braun} 62403d9609c6154ed91daefb4e4f89b7298c11961f3Matthias Braun 625b720be6a50f4e1b3280d2b029ee38dda14577525Manman Ren#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 62687a86058fa0726328de42ace85b5532d18775646Matthias Braunvoid LiveRange::dump() const { 6275242154b558f0783830938f18153e0a7964fb4faDavid Greene dbgs() << *this << "\n"; 628abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner} 62903d9609c6154ed91daefb4e4f89b7298c11961f3Matthias Braun 63003d9609c6154ed91daefb4e4f89b7298c11961f3Matthias Braunvoid LiveInterval::dump() const { 63103d9609c6154ed91daefb4e4f89b7298c11961f3Matthias Braun dbgs() << *this << "\n"; 63203d9609c6154ed91daefb4e4f89b7298c11961f3Matthias Braun} 63377e300e8f0b8db8eec448cae9c87d7c5bfad9757Manman Ren#endif 634c21c5eeb4f56f160e79522df2d3aab5cfe73c05dJeff Cohen 635261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth#ifndef NDEBUG 63687a86058fa0726328de42ace85b5532d18775646Matthias Braunvoid LiveRange::verify() const { 637261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth for (const_iterator I = begin(), E = end(); I != E; ++I) { 638261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth assert(I->start.isValid()); 639261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth assert(I->end.isValid()); 640261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth assert(I->start < I->end); 641dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(I->valno != nullptr); 64287a86058fa0726328de42ace85b5532d18775646Matthias Braun assert(I->valno->id < valnos.size()); 643261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth assert(I->valno == valnos[I->valno->id]); 64436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (std::next(I) != E) { 64536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(I->end <= std::next(I)->start); 64636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (I->end == std::next(I)->start) 64736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(I->valno != std::next(I)->valno); 648261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth } 649261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth } 650261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth} 651261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth#endif 652261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth 653c21c5eeb4f56f160e79522df2d3aab5cfe73c05dJeff Cohen 6541a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen//===----------------------------------------------------------------------===// 6551a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// LiveRangeUpdater class 6561a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen//===----------------------------------------------------------------------===// 6571a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// 6581a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// The LiveRangeUpdater class always maintains these invariants: 6591a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// 6601a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// - When LastStart is invalid, Spills is empty and the iterators are invalid. 6611a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// This is the initial state, and the state created by flush(). 6621a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// In this state, isDirty() returns false. 6631a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// 6641a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// Otherwise, segments are kept in three separate areas: 6651a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// 66687a86058fa0726328de42ace85b5532d18775646Matthias Braun// 1. [begin; WriteI) at the front of LR. 66787a86058fa0726328de42ace85b5532d18775646Matthias Braun// 2. [ReadI; end) at the back of LR. 6681a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// 3. Spills. 6691a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// 67087a86058fa0726328de42ace85b5532d18775646Matthias Braun// - LR.begin() <= WriteI <= ReadI <= LR.end(). 6711a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// - Segments in all three areas are fully ordered and coalesced. 6721a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// - Segments in area 1 precede and can't coalesce with segments in area 2. 6731a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// - Segments in Spills precede and can't coalesce with segments in area 2. 6741a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// - No coalescing is possible between segments in Spills and segments in area 6751a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// 1, and there are no overlapping segments. 6761a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// 6771a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// The segments in Spills are not ordered with respect to the segments in area 6781a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// 1. They need to be merged. 6791a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// 6801a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// When they exist, Spills.back().start <= LastStart, 6811a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// and WriteI[-1].start <= LastStart. 6821a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 6831a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesenvoid LiveRangeUpdater::print(raw_ostream &OS) const { 6841a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (!isDirty()) { 68587a86058fa0726328de42ace85b5532d18775646Matthias Braun if (LR) 68687a86058fa0726328de42ace85b5532d18775646Matthias Braun OS << "Clean updater: " << *LR << '\n'; 6871a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen else 6881a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen OS << "Null updater.\n"; 6891a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen return; 6901a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen } 69187a86058fa0726328de42ace85b5532d18775646Matthias Braun assert(LR && "Can't have null LR in dirty updater."); 69287a86058fa0726328de42ace85b5532d18775646Matthias Braun OS << " updater with gap = " << (ReadI - WriteI) 6931a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen << ", last start = " << LastStart 6941a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen << ":\n Area 1:"; 69587a86058fa0726328de42ace85b5532d18775646Matthias Braun for (LiveRange::const_iterator I = LR->begin(); I != WriteI; ++I) 6961a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen OS << ' ' << *I; 6971a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen OS << "\n Spills:"; 6981a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen for (unsigned I = 0, E = Spills.size(); I != E; ++I) 6991a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen OS << ' ' << Spills[I]; 7001a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen OS << "\n Area 2:"; 70187a86058fa0726328de42ace85b5532d18775646Matthias Braun for (LiveRange::const_iterator I = ReadI, E = LR->end(); I != E; ++I) 7021a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen OS << ' ' << *I; 7031a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen OS << '\n'; 7041a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen} 7051a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 7061a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesenvoid LiveRangeUpdater::dump() const 7071a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen{ 7081a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen print(errs()); 7091a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen} 7101a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 7111a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// Determine if A and B should be coalesced. 71287a86058fa0726328de42ace85b5532d18775646Matthias Braunstatic inline bool coalescable(const LiveRange::Segment &A, 71387a86058fa0726328de42ace85b5532d18775646Matthias Braun const LiveRange::Segment &B) { 714331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun assert(A.start <= B.start && "Unordered live segments."); 7151a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (A.end == B.start) 7161a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen return A.valno == B.valno; 7171a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (A.end < B.start) 7181a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen return false; 7191a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen assert(A.valno == B.valno && "Cannot overlap different values"); 7201a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen return true; 7211a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen} 7221a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 72387a86058fa0726328de42ace85b5532d18775646Matthias Braunvoid LiveRangeUpdater::add(LiveRange::Segment Seg) { 72487a86058fa0726328de42ace85b5532d18775646Matthias Braun assert(LR && "Cannot add to a null destination"); 7251a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 7261a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Flush the state if Start moves backwards. 7271a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (!LastStart.isValid() || LastStart > Seg.start) { 7281a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (isDirty()) 7291a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen flush(); 7301a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // This brings us to an uninitialized state. Reinitialize. 7311a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen assert(Spills.empty() && "Leftover spilled segments"); 73287a86058fa0726328de42ace85b5532d18775646Matthias Braun WriteI = ReadI = LR->begin(); 7331a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen } 7341a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 7351a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Remember start for next time. 7361a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen LastStart = Seg.start; 7371a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 7381a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Advance ReadI until it ends after Seg.start. 73987a86058fa0726328de42ace85b5532d18775646Matthias Braun LiveRange::iterator E = LR->end(); 7401a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (ReadI != E && ReadI->end <= Seg.start) { 7411a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // First try to close the gap between WriteI and ReadI with spills. 7421a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (ReadI != WriteI) 7431a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen mergeSpills(); 7441a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Then advance ReadI. 7451a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (ReadI == WriteI) 74687a86058fa0726328de42ace85b5532d18775646Matthias Braun ReadI = WriteI = LR->find(Seg.start); 7471a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen else 7481a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen while (ReadI != E && ReadI->end <= Seg.start) 7491a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen *WriteI++ = *ReadI++; 7501a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen } 7511a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 7521a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen assert(ReadI == E || ReadI->end > Seg.start); 7531a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 7541a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Check if the ReadI segment begins early. 7551a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (ReadI != E && ReadI->start <= Seg.start) { 7561a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen assert(ReadI->valno == Seg.valno && "Cannot overlap different values"); 7571a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Bail if Seg is completely contained in ReadI. 7581a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (ReadI->end >= Seg.end) 7591a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen return; 7601a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Coalesce into Seg. 7611a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen Seg.start = ReadI->start; 7621a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen ++ReadI; 7631a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen } 7641a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 7651a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Coalesce as much as possible from ReadI into Seg. 7661a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen while (ReadI != E && coalescable(Seg, *ReadI)) { 7671a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen Seg.end = std::max(Seg.end, ReadI->end); 7681a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen ++ReadI; 7691a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen } 7701a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 7711a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Try coalescing Spills.back() into Seg. 7721a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (!Spills.empty() && coalescable(Spills.back(), Seg)) { 7731a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen Seg.start = Spills.back().start; 7741a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen Seg.end = std::max(Spills.back().end, Seg.end); 7751a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen Spills.pop_back(); 7761a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen } 7771a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 7781a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Try coalescing Seg into WriteI[-1]. 77987a86058fa0726328de42ace85b5532d18775646Matthias Braun if (WriteI != LR->begin() && coalescable(WriteI[-1], Seg)) { 7801a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen WriteI[-1].end = std::max(WriteI[-1].end, Seg.end); 7811a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen return; 7821a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen } 7831a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 7841a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Seg doesn't coalesce with anything, and needs to be inserted somewhere. 7851a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (WriteI != ReadI) { 7861a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen *WriteI++ = Seg; 7871a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen return; 7881a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen } 7891a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 79087a86058fa0726328de42ace85b5532d18775646Matthias Braun // Finally, append to LR or Spills. 7911a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (WriteI == E) { 79287a86058fa0726328de42ace85b5532d18775646Matthias Braun LR->segments.push_back(Seg); 79387a86058fa0726328de42ace85b5532d18775646Matthias Braun WriteI = ReadI = LR->end(); 7941a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen } else 7951a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen Spills.push_back(Seg); 7961a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen} 7971a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 7981a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// Merge as many spilled segments as possible into the gap between WriteI 7991a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen// and ReadI. Advance WriteI to reflect the inserted instructions. 8001a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesenvoid LiveRangeUpdater::mergeSpills() { 8011a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Perform a backwards merge of Spills and [SpillI;WriteI). 8021a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen size_t GapSize = ReadI - WriteI; 8031a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen size_t NumMoved = std::min(Spills.size(), GapSize); 80487a86058fa0726328de42ace85b5532d18775646Matthias Braun LiveRange::iterator Src = WriteI; 80587a86058fa0726328de42ace85b5532d18775646Matthias Braun LiveRange::iterator Dst = Src + NumMoved; 80687a86058fa0726328de42ace85b5532d18775646Matthias Braun LiveRange::iterator SpillSrc = Spills.end(); 80787a86058fa0726328de42ace85b5532d18775646Matthias Braun LiveRange::iterator B = LR->begin(); 8081a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 8091a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // This is the new WriteI position after merging spills. 8101a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen WriteI = Dst; 8111a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 8121a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Now merge Src and Spills backwards. 8131a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen while (Src != Dst) { 8141a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (Src != B && Src[-1].start > SpillSrc[-1].start) 8151a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen *--Dst = *--Src; 8161a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen else 8171a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen *--Dst = *--SpillSrc; 8181a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen } 8191a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen assert(NumMoved == size_t(Spills.end() - SpillSrc)); 8201a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen Spills.erase(SpillSrc, Spills.end()); 8211a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen} 8221a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 8231a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesenvoid LiveRangeUpdater::flush() { 8241a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (!isDirty()) 8251a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen return; 8261a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Clear the dirty state. 8271a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen LastStart = SlotIndex(); 8281a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 82987a86058fa0726328de42ace85b5532d18775646Matthias Braun assert(LR && "Cannot add to a null destination"); 8301a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 8311a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Nothing to merge? 8321a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (Spills.empty()) { 83387a86058fa0726328de42ace85b5532d18775646Matthias Braun LR->segments.erase(WriteI, ReadI); 83487a86058fa0726328de42ace85b5532d18775646Matthias Braun LR->verify(); 8351a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen return; 8361a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen } 8371a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 8381a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Resize the WriteI - ReadI gap to match Spills. 8391a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen size_t GapSize = ReadI - WriteI; 8401a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen if (GapSize < Spills.size()) { 8411a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // The gap is too small. Make some room. 84287a86058fa0726328de42ace85b5532d18775646Matthias Braun size_t WritePos = WriteI - LR->begin(); 84387a86058fa0726328de42ace85b5532d18775646Matthias Braun LR->segments.insert(ReadI, Spills.size() - GapSize, LiveRange::Segment()); 8441a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // This also invalidated ReadI, but it is recomputed below. 84587a86058fa0726328de42ace85b5532d18775646Matthias Braun WriteI = LR->begin() + WritePos; 8461a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen } else { 8471a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen // Shrink the gap if necessary. 84887a86058fa0726328de42ace85b5532d18775646Matthias Braun LR->segments.erase(WriteI + Spills.size(), ReadI); 8491a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen } 8501a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen ReadI = WriteI + Spills.size(); 8511a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen mergeSpills(); 85287a86058fa0726328de42ace85b5532d18775646Matthias Braun LR->verify(); 8531a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen} 8541a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 8550253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesenunsigned ConnectedVNInfoEqClasses::Classify(const LiveInterval *LI) { 85654f32e6575d0c1b920ae5151c229f1187bae0cbfJakob Stoklund Olesen // Create initial equivalence classes. 8572254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen EqClass.clear(); 8582254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen EqClass.grow(LI->getNumValNums()); 85954f32e6575d0c1b920ae5151c229f1187bae0cbfJakob Stoklund Olesen 860dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const VNInfo *used = nullptr, *unused = nullptr; 8616d309059a7d6257ddeb3b07e6c4b8b71cce2f707Jakob Stoklund Olesen 86254f32e6575d0c1b920ae5151c229f1187bae0cbfJakob Stoklund Olesen // Determine connections. 8630253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen for (LiveInterval::const_vni_iterator I = LI->vni_begin(), E = LI->vni_end(); 8640253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen I != E; ++I) { 8650253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen const VNInfo *VNI = *I; 8666d309059a7d6257ddeb3b07e6c4b8b71cce2f707Jakob Stoklund Olesen // Group all unused values into one class. 8676d309059a7d6257ddeb3b07e6c4b8b71cce2f707Jakob Stoklund Olesen if (VNI->isUnused()) { 8686d309059a7d6257ddeb3b07e6c4b8b71cce2f707Jakob Stoklund Olesen if (unused) 8692254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen EqClass.join(unused->id, VNI->id); 8706d309059a7d6257ddeb3b07e6c4b8b71cce2f707Jakob Stoklund Olesen unused = VNI; 8716d309059a7d6257ddeb3b07e6c4b8b71cce2f707Jakob Stoklund Olesen continue; 8726d309059a7d6257ddeb3b07e6c4b8b71cce2f707Jakob Stoklund Olesen } 8736d309059a7d6257ddeb3b07e6c4b8b71cce2f707Jakob Stoklund Olesen used = VNI; 8740253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen if (VNI->isPHIDef()) { 8752254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen const MachineBasicBlock *MBB = LIS.getMBBFromIndex(VNI->def); 8760253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen assert(MBB && "Phi-def has no defining MBB"); 8770253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // Connect to values live out of predecessors. 8780253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 8790253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) 880194eb71a11a77c7fb576780783a77e64924dfb10Jakob Stoklund Olesen if (const VNInfo *PVNI = LI->getVNInfoBefore(LIS.getMBBEndIdx(*PI))) 8812254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen EqClass.join(VNI->id, PVNI->id); 8820253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen } else { 8830253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // Normal value defined by an instruction. Check for two-addr redef. 8840253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // FIXME: This could be coincidental. Should we really check for a tied 8850253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // operand constraint? 886b907e8a2d40dc546f21ff7e122a80b121653851aJakob Stoklund Olesen // Note that VNI->def may be a use slot for an early clobber def. 887194eb71a11a77c7fb576780783a77e64924dfb10Jakob Stoklund Olesen if (const VNInfo *UVNI = LI->getVNInfoBefore(VNI->def)) 8882254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen EqClass.join(VNI->id, UVNI->id); 8890253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen } 8900253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen } 8916d309059a7d6257ddeb3b07e6c4b8b71cce2f707Jakob Stoklund Olesen 8926d309059a7d6257ddeb3b07e6c4b8b71cce2f707Jakob Stoklund Olesen // Lump all the unused values in with the last used value. 8936d309059a7d6257ddeb3b07e6c4b8b71cce2f707Jakob Stoklund Olesen if (used && unused) 8942254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen EqClass.join(used->id, unused->id); 8956d309059a7d6257ddeb3b07e6c4b8b71cce2f707Jakob Stoklund Olesen 8962254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen EqClass.compress(); 8972254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen return EqClass.getNumClasses(); 8980253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen} 8990253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 9002254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesenvoid ConnectedVNInfoEqClasses::Distribute(LiveInterval *LIV[], 9012254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen MachineRegisterInfo &MRI) { 9020253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen assert(LIV[0] && "LIV[0] must be set"); 9030253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen LiveInterval &LI = *LIV[0]; 9040253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 9052254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen // Rewrite instructions. 9062254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(LI.reg), 9072254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen RE = MRI.reg_end(); RI != RE;) { 90836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MachineOperand &MO = *RI; 90936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MachineInstr *MI = RI->getParent(); 9102254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen ++RI; 911e0b59774cba9eb89ffba114635f3a1fa075910b1Jakob Stoklund Olesen // DBG_VALUE instructions don't have slot indexes, so get the index of the 912e0b59774cba9eb89ffba114635f3a1fa075910b1Jakob Stoklund Olesen // instruction before them. 913e0b59774cba9eb89ffba114635f3a1fa075910b1Jakob Stoklund Olesen // Normally, DBG_VALUE instructions are removed before this function is 914e0b59774cba9eb89ffba114635f3a1fa075910b1Jakob Stoklund Olesen // called, but it is not a requirement. 915e0b59774cba9eb89ffba114635f3a1fa075910b1Jakob Stoklund Olesen SlotIndex Idx; 916e0b59774cba9eb89ffba114635f3a1fa075910b1Jakob Stoklund Olesen if (MI->isDebugValue()) 917e0b59774cba9eb89ffba114635f3a1fa075910b1Jakob Stoklund Olesen Idx = LIS.getSlotIndexes()->getIndexBefore(MI); 918e0b59774cba9eb89ffba114635f3a1fa075910b1Jakob Stoklund Olesen else 919e0b59774cba9eb89ffba114635f3a1fa075910b1Jakob Stoklund Olesen Idx = LIS.getInstructionIndex(MI); 9205649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun LiveQueryResult LRQ = LI.Query(Idx); 92184315f03cb6127ac92a5b02239c6edc2a347069aJakob Stoklund Olesen const VNInfo *VNI = MO.readsReg() ? LRQ.valueIn() : LRQ.valueDefined(); 92284315f03cb6127ac92a5b02239c6edc2a347069aJakob Stoklund Olesen // In the case of an <undef> use that isn't tied to any def, VNI will be 92384315f03cb6127ac92a5b02239c6edc2a347069aJakob Stoklund Olesen // NULL. If the use is tied to a def, VNI will be the defined value. 924bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen if (!VNI) 925bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen continue; 9262254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen MO.setReg(LIV[getEqClass(VNI)]->reg); 9272254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen } 9282254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen 9292254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen // Move runs to new intervals. 9300253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen LiveInterval::iterator J = LI.begin(), E = LI.end(); 9312254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen while (J != E && EqClass[J->valno->id] == 0) 9320253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen ++J; 9330253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen for (LiveInterval::iterator I = J; I != E; ++I) { 9342254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen if (unsigned eq = EqClass[I->valno->id]) { 935ccefe32141c96faa05445bce0b26f1acd8bdc1b8Benjamin Kramer assert((LIV[eq]->empty() || LIV[eq]->expiredAt(I->start)) && 9360253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen "New intervals should be empty"); 937331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun LIV[eq]->segments.push_back(*I); 9380253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen } else 9390253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen *J++ = *I; 9400253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen } 941331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun LI.segments.erase(J, E); 9420253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 9430253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // Transfer VNInfos to their new owners and renumber them. 9440253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen unsigned j = 0, e = LI.getNumValNums(); 9452254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen while (j != e && EqClass[j] == 0) 9460253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen ++j; 9470253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen for (unsigned i = j; i != e; ++i) { 9480253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen VNInfo *VNI = LI.getValNumInfo(i); 9492254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen if (unsigned eq = EqClass[i]) { 9500253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen VNI->id = LIV[eq]->getNumValNums(); 9510253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen LIV[eq]->valnos.push_back(VNI); 9520253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen } else { 9530253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen VNI->id = j; 9540253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen LI.valnos[j++] = VNI; 9550253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen } 9560253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen } 9570253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen LI.valnos.resize(j); 9580253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen} 959