LiveInterval.cpp revision ccefe32141c96faa05445bce0b26f1acd8bdc1b8
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" 22233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#include "llvm/CodeGen/LiveIntervalAnalysis.h" 2390f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng#include "llvm/CodeGen/MachineRegisterInfo.h" 240adb527d169e1f557676fda35bc9abb735e5c912Evan Cheng#include "llvm/ADT/DenseMap.h" 253c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng#include "llvm/ADT/SmallSet.h" 2638b0e7bbf2590f99122a2535d16f34bd12c3bb24Bill Wendling#include "llvm/ADT/STLExtras.h" 275242154b558f0783830938f18153e0a7964fb4faDavid Greene#include "llvm/Support/Debug.h" 28a717b7be8886c4c6ae261ee553c5cbcae29c1e52Daniel Dunbar#include "llvm/Support/raw_ostream.h" 296f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman#include "llvm/Target/TargetRegisterInfo.h" 30c4d3b918165461bc6f5d395bca8d9d9d8a84413dAlkis Evlogimenos#include <algorithm> 31fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattnerusing namespace llvm; 32fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 337c727072168c55493ec362e254af1cd740d7eaf2Jakob Stoklund Olesen// CompEnd - Compare LiveRange ends. 3489bfef003ec71792d078d489566655006b89bc43Jakob Stoklund Olesennamespace { 352de0e808c1fa742f3eac68b5d10d182699cbbe04Jakob Stoklund Olesenstruct CompEnd { 367c727072168c55493ec362e254af1cd740d7eaf2Jakob Stoklund Olesen bool operator()(const LiveRange &A, const LiveRange &B) const { 377c727072168c55493ec362e254af1cd740d7eaf2Jakob Stoklund Olesen return A.end < B.end; 382de0e808c1fa742f3eac68b5d10d182699cbbe04Jakob Stoklund Olesen } 392de0e808c1fa742f3eac68b5d10d182699cbbe04Jakob Stoklund Olesen}; 4089bfef003ec71792d078d489566655006b89bc43Jakob Stoklund Olesen} 41c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng 42f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund OlesenLiveInterval::iterator LiveInterval::find(SlotIndex Pos) { 43201ecfca9892b2eab2d04aa5da59f3f5e1efe49dJakob Stoklund Olesen assert(Pos.isValid() && "Cannot search for an invalid index"); 447c727072168c55493ec362e254af1cd740d7eaf2Jakob Stoklund Olesen return std::upper_bound(begin(), end(), LiveRange(SlotIndex(), Pos, 0), 457c727072168c55493ec362e254af1cd740d7eaf2Jakob Stoklund Olesen CompEnd()); 4615a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen} 4715a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen 4815a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen/// killedInRange - Return true if the interval has kills in [Start,End). 4915a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesenbool LiveInterval::killedInRange(SlotIndex Start, SlotIndex End) const { 5015a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen Ranges::const_iterator r = 5115a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen std::lower_bound(ranges.begin(), ranges.end(), End); 5215a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen 5315a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen // Now r points to the first interval with start >= End, or ranges.end(). 5415a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen if (r == ranges.begin()) 5515a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen return false; 5615a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen 5715a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen --r; 5815a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen // Now r points to the last interval with end <= End. 5915a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen // r->end is the kill point. 6015a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen return r->end >= Start && r->end < End; 6115a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen} 6215a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen 63bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner// overlaps - Return true if the intersection of the two live intervals is 64bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner// not empty. 65bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner// 66fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// An example for overlaps(): 67fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 68fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 0: A = ... 69fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 4: B = ... 70fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 8: C = A + B ;; last use of A 71fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 72fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// The live intervals should look like: 73fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 74fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// A = [3, 11) 75fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// B = [7, x) 76fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// C = [11, y) 77fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 78fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// A->overlaps(C) should return false since we want to be able to join 79fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// A and C. 80bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner// 81bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattnerbool LiveInterval::overlapsFrom(const LiveInterval& other, 82bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator StartPos) const { 836382d2caddb98f30f556b43faa898ff675affaf7Jakob Stoklund Olesen assert(!empty() && "empty interval"); 84bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator i = begin(); 85bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator ie = end(); 86bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator j = StartPos; 87bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator je = other.end(); 88bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner 89bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner assert((StartPos->start <= i->start || StartPos == other.begin()) && 908c68b6a226ce46b35eafda972e04bf53128c2615Chris Lattner StartPos != other.end() && "Bogus start position hint!"); 91f542649f1b374b1bae845e4e4f6d1e82f90a9e31Chris Lattner 92fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i->start < j->start) { 93aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner i = std::upper_bound(i, ie, j->start); 94fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i != ranges.begin()) --i; 95aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner } else if (j->start < i->start) { 96ead1b3f0bb70cd9c1ba7a853a79070cb47db9344Chris Lattner ++StartPos; 97ead1b3f0bb70cd9c1ba7a853a79070cb47db9344Chris Lattner if (StartPos != other.end() && StartPos->start <= i->start) { 98ead1b3f0bb70cd9c1ba7a853a79070cb47db9344Chris Lattner assert(StartPos < other.end() && i < end()); 998c68b6a226ce46b35eafda972e04bf53128c2615Chris Lattner j = std::upper_bound(j, je, i->start); 1008c68b6a226ce46b35eafda972e04bf53128c2615Chris Lattner if (j != other.ranges.begin()) --j; 1018c68b6a226ce46b35eafda972e04bf53128c2615Chris Lattner } 102aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner } else { 103aa14147cd6401e9c66dc9f81d1a47a90a5477159Chris Lattner return true; 104fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 105fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 1069fddc12c9b16a5526b0ee2e6f1da252f7974d7d0Chris Lattner if (j == je) return false; 1079fddc12c9b16a5526b0ee2e6f1da252f7974d7d0Chris Lattner 1089fddc12c9b16a5526b0ee2e6f1da252f7974d7d0Chris Lattner while (i != ie) { 109fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i->start > j->start) { 110a1613db62fec94845aa8306232fb665273615badAlkis Evlogimenos std::swap(i, j); 111a1613db62fec94845aa8306232fb665273615badAlkis Evlogimenos std::swap(ie, je); 112fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 113fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 114fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i->end > j->start) 115fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return true; 116fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner ++i; 117fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 118fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 119fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return false; 120fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 121fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 122cccdb2b602cf421d8890130308945163620ebc68Evan Cheng/// overlaps - Return true if the live interval overlaps a range specified 123cccdb2b602cf421d8890130308945163620ebc68Evan Cheng/// by [Start, End). 124233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesbool LiveInterval::overlaps(SlotIndex Start, SlotIndex End) const { 125cccdb2b602cf421d8890130308945163620ebc68Evan Cheng assert(Start < End && "Invalid range"); 126186eb73845c29547cc837341f0c8c0f6d9284e67Jakob Stoklund Olesen const_iterator I = std::lower_bound(begin(), end(), End); 127186eb73845c29547cc837341f0c8c0f6d9284e67Jakob Stoklund Olesen return I != begin() && (--I)->end > Start; 128cccdb2b602cf421d8890130308945163620ebc68Evan Cheng} 129cccdb2b602cf421d8890130308945163620ebc68Evan Cheng 1306f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames 1316f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames/// ValNo is dead, remove it. If it is the largest value number, just nuke it 1326f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames/// (and any other deleted values neighboring it), otherwise mark it as ~1U so 1336f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames/// it can be nuked later. 1346f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hamesvoid LiveInterval::markValNoForDeletion(VNInfo *ValNo) { 1356f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames if (ValNo->id == getNumValNums()-1) { 1366f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames do { 1376f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames valnos.pop_back(); 1386f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames } while (!valnos.empty() && valnos.back()->isUnused()); 1396f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames } else { 1406f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames ValNo->setIsUnused(true); 1416f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames } 1426f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames} 1436f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames 14423436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen/// RenumberValues - Renumber all values in order of appearance and delete the 14523436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen/// remaining unused values. 146fff2c4726baa0d6c9cb184c815677e33c0357c93Jakob Stoklund Olesenvoid LiveInterval::RenumberValues(LiveIntervals &lis) { 14723436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen SmallPtrSet<VNInfo*, 8> Seen; 148fff2c4726baa0d6c9cb184c815677e33c0357c93Jakob Stoklund Olesen bool seenPHIDef = false; 14923436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen valnos.clear(); 15023436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen for (const_iterator I = begin(), E = end(); I != E; ++I) { 15123436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen VNInfo *VNI = I->valno; 15223436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen if (!Seen.insert(VNI)) 15323436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen continue; 15423436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen assert(!VNI->isUnused() && "Unused valno used by live range"); 15523436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen VNI->id = (unsigned)valnos.size(); 15623436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen valnos.push_back(VNI); 157fff2c4726baa0d6c9cb184c815677e33c0357c93Jakob Stoklund Olesen VNI->setHasPHIKill(false); 158fff2c4726baa0d6c9cb184c815677e33c0357c93Jakob Stoklund Olesen if (VNI->isPHIDef()) 159fff2c4726baa0d6c9cb184c815677e33c0357c93Jakob Stoklund Olesen seenPHIDef = true; 160fff2c4726baa0d6c9cb184c815677e33c0357c93Jakob Stoklund Olesen } 161fff2c4726baa0d6c9cb184c815677e33c0357c93Jakob Stoklund Olesen 162fff2c4726baa0d6c9cb184c815677e33c0357c93Jakob Stoklund Olesen // Recompute phi kill flags. 163fff2c4726baa0d6c9cb184c815677e33c0357c93Jakob Stoklund Olesen if (!seenPHIDef) 164fff2c4726baa0d6c9cb184c815677e33c0357c93Jakob Stoklund Olesen return; 165fff2c4726baa0d6c9cb184c815677e33c0357c93Jakob Stoklund Olesen for (const_vni_iterator I = vni_begin(), E = vni_end(); I != E; ++I) { 166fff2c4726baa0d6c9cb184c815677e33c0357c93Jakob Stoklund Olesen VNInfo *VNI = *I; 167fff2c4726baa0d6c9cb184c815677e33c0357c93Jakob Stoklund Olesen if (!VNI->isPHIDef()) 168fff2c4726baa0d6c9cb184c815677e33c0357c93Jakob Stoklund Olesen continue; 169fff2c4726baa0d6c9cb184c815677e33c0357c93Jakob Stoklund Olesen const MachineBasicBlock *PHIBB = lis.getMBBFromIndex(VNI->def); 170fff2c4726baa0d6c9cb184c815677e33c0357c93Jakob Stoklund Olesen assert(PHIBB && "No basic block for phi-def"); 171fff2c4726baa0d6c9cb184c815677e33c0357c93Jakob Stoklund Olesen for (MachineBasicBlock::const_pred_iterator PI = PHIBB->pred_begin(), 172fff2c4726baa0d6c9cb184c815677e33c0357c93Jakob Stoklund Olesen PE = PHIBB->pred_end(); PI != PE; ++PI) { 173fff2c4726baa0d6c9cb184c815677e33c0357c93Jakob Stoklund Olesen VNInfo *KVNI = getVNInfoAt(lis.getMBBEndIdx(*PI).getPrevSlot()); 174fff2c4726baa0d6c9cb184c815677e33c0357c93Jakob Stoklund Olesen if (KVNI) 175fff2c4726baa0d6c9cb184c815677e33c0357c93Jakob Stoklund Olesen KVNI->setHasPHIKill(true); 176fff2c4726baa0d6c9cb184c815677e33c0357c93Jakob Stoklund Olesen } 17723436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen } 17823436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen} 17923436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen 180b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// extendIntervalEndTo - This method is used when we want to extend the range 181b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// specified by I to end at the specified endpoint. To do this, we should 182b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// merge and eliminate all ranges that this will overlap with. The iterator is 183b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// not invalidated. 184233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesvoid LiveInterval::extendIntervalEndTo(Ranges::iterator I, SlotIndex NewEnd) { 185b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner assert(I != ranges.end() && "Not a valid interval!"); 1867ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo = I->valno; 187b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 188b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Search for the first interval that we can't merge with. 189ee56c42168f6c4271593f6018c4409b6a5910302Oscar Fuentes Ranges::iterator MergeTo = llvm::next(I); 190abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner for (; MergeTo != ranges.end() && NewEnd >= MergeTo->end; ++MergeTo) { 1917ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); 192abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 193b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 194b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // If NewEnd was in the middle of an interval, make sure to get its endpoint. 195b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner I->end = std::max(NewEnd, prior(MergeTo)->end); 196b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 197b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner // Erase any dead ranges. 198ee56c42168f6c4271593f6018c4409b6a5910302Oscar Fuentes ranges.erase(llvm::next(I), MergeTo); 1994f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 200b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner // If the newly formed range now touches the range after it and if they have 201b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner // the same value number, merge the two ranges into one range. 202ee56c42168f6c4271593f6018c4409b6a5910302Oscar Fuentes Ranges::iterator Next = llvm::next(I); 2037ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (Next != ranges.end() && Next->start <= I->end && Next->valno == ValNo) { 204cef6010c64bc56fa2a8f1e7e9e28b8821adeceacChris Lattner I->end = Next->end; 205cef6010c64bc56fa2a8f1e7e9e28b8821adeceacChris Lattner ranges.erase(Next); 206b0fa11ca41d85e35d3c1155c6a3af1b67788fce6Chris Lattner } 207fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 208fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 209fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 210b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// extendIntervalStartTo - This method is used when we want to extend the range 211b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// specified by I to start at the specified endpoint. To do this, we should 212b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner/// merge and eliminate all ranges that this will overlap with. 213edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha BrukmanLiveInterval::Ranges::iterator 214233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang HamesLiveInterval::extendIntervalStartTo(Ranges::iterator I, SlotIndex NewStart) { 215b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner assert(I != ranges.end() && "Not a valid interval!"); 2167ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo = I->valno; 217b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 218b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Search for the first interval that we can't merge with. 219b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner Ranges::iterator MergeTo = I; 220b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner do { 221b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner if (MergeTo == ranges.begin()) { 222b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner I->start = NewStart; 223abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner ranges.erase(MergeTo, I); 224b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner return I; 225b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } 2267ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng assert(MergeTo->valno == ValNo && "Cannot merge with differing values!"); 227b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner --MergeTo; 228b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } while (NewStart <= MergeTo->start); 229b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 230b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // If we start in the middle of another interval, just delete a range and 231b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // extend that interval. 2327ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (MergeTo->end >= NewStart && MergeTo->valno == ValNo) { 233b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner MergeTo->end = I->end; 234b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } else { 235b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Otherwise, extend the interval right after. 236b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner ++MergeTo; 237b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner MergeTo->start = NewStart; 238b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner MergeTo->end = I->end; 239fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 240b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 241ee56c42168f6c4271593f6018c4409b6a5910302Oscar Fuentes ranges.erase(llvm::next(MergeTo), llvm::next(I)); 242b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner return MergeTo; 243fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 244fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 245c114b2cad7293d98686d380273085f5c32966b52Chris LattnerLiveInterval::iterator 246c114b2cad7293d98686d380273085f5c32966b52Chris LattnerLiveInterval::addRangeFrom(LiveRange LR, iterator From) { 247233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Start = LR.start, End = LR.end; 248c114b2cad7293d98686d380273085f5c32966b52Chris Lattner iterator it = std::upper_bound(From, ranges.end(), Start); 249b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 250b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // If the inserted interval starts in the middle or right at the end of 251b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // another interval, just extend that interval to contain the range of LR. 252b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner if (it != ranges.begin()) { 253c114b2cad7293d98686d380273085f5c32966b52Chris Lattner iterator B = prior(it); 2547ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (LR.valno == B->valno) { 255abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (B->start <= Start && B->end >= Start) { 256abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner extendIntervalEndTo(B, End); 257abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return B; 258abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 259abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } else { 260abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Check to make sure that we are not overlapping two live ranges with 2617ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng // different valno's. 262abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner assert(B->end <= Start && 2638311befb6968a581a3abdce1e13b5d63922662f7Brian Gaeke "Cannot overlap two LiveRanges with differing ValID's" 2648311befb6968a581a3abdce1e13b5d63922662f7Brian Gaeke " (did you def the same reg twice in a MachineInstr?)"); 265b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } 266fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 267b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 268b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Otherwise, if this range ends in the middle of, or right next to, another 269b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // interval, merge it into that interval. 2704c71dfe356716e6bc1993ef5efdced08b68fe612Anton Korobeynikov if (it != ranges.end()) { 2717ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (LR.valno == it->valno) { 272abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (it->start <= End) { 273abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner it = extendIntervalStartTo(it, Start); 274abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 275abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // If LR is a complete superset of an interval, we may need to grow its 276abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // endpoint as well. 277abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (End > it->end) 278abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner extendIntervalEndTo(it, End); 279abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return it; 280abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 281abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } else { 282abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Check to make sure that we are not overlapping two live ranges with 2837ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng // different valno's. 284abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner assert(it->start >= End && 285abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner "Cannot overlap two LiveRanges with differing ValID's"); 286abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 2874c71dfe356716e6bc1993ef5efdced08b68fe612Anton Korobeynikov } 288b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner 289b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Otherwise, this is just a new range that doesn't interact with anything. 290b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner // Insert it. 291b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner return ranges.insert(it, LR); 292fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 293fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 294abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 295abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner/// removeRange - Remove the specified range from this interval. Note that 29642cc6e33ec0f63560c31f1928c56b4b0465d537cEvan Cheng/// the range must be in a single LiveRange in its entirety. 297233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesvoid LiveInterval::removeRange(SlotIndex Start, SlotIndex End, 298d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng bool RemoveDeadValNo) { 299abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Find the LiveRange containing this span. 300f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen Ranges::iterator I = find(Start); 301f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen assert(I != ranges.end() && "Range is not in interval!"); 3028651125d2885f74546b6e2a556082111d5b75da3Lang Hames assert(I->containsRange(Start, End) && "Range is not entirely in interval!"); 303abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 304abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // If the span we are removing is at the start of the LiveRange, adjust it. 305d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng VNInfo *ValNo = I->valno; 306abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (I->start == Start) { 3074f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng if (I->end == End) { 308d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (RemoveDeadValNo) { 309d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng // Check if val# is dead. 310d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng bool isDead = true; 311d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng for (const_iterator II = begin(), EE = end(); II != EE; ++II) 312d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (II != I && II->valno == ValNo) { 313d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng isDead = false; 314d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng break; 31515a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen } 316d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (isDead) { 3176f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames // Now that ValNo is dead, remove it. 3186f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames markValNoForDeletion(ValNo); 319d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng } 320d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng } 321d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng 322abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner ranges.erase(I); // Removed the whole LiveRange. 3234f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng } else 324abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner I->start = End; 325abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return; 326abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 327abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 328abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Otherwise if the span we are removing is at the end of the LiveRange, 329abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // adjust the other way. 330abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner if (I->end == End) { 3316925a9f9cc0b9d34cfbc19d9208c416e293ca516Chris Lattner I->end = Start; 332abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner return; 333abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 334abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 335abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Otherwise, we are splitting the LiveRange into two pieces. 336233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex OldEnd = I->end; 337abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner I->end = Start; // Trim the old interval. 338abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 339abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner // Insert the new one. 340ee56c42168f6c4271593f6018c4409b6a5910302Oscar Fuentes ranges.insert(llvm::next(I), LiveRange(End, OldEnd, ValNo)); 341abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner} 342abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 343d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng/// removeValNo - Remove all the ranges defined by the specified value#. 344d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng/// Also remove the value# from value# list. 345d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Chengvoid LiveInterval::removeValNo(VNInfo *ValNo) { 346d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (empty()) return; 347d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng Ranges::iterator I = ranges.end(); 348d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng Ranges::iterator E = ranges.begin(); 349d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng do { 350d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng --I; 351d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng if (I->valno == ValNo) 352d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng ranges.erase(I); 353d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng } while (I != E); 3546f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames // Now that ValNo is dead, remove it. 3556f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames markValNoForDeletion(ValNo); 356d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng} 3578651125d2885f74546b6e2a556082111d5b75da3Lang Hames 3588651125d2885f74546b6e2a556082111d5b75da3Lang Hames/// findDefinedVNInfo - Find the VNInfo defined by the specified 3598651125d2885f74546b6e2a556082111d5b75da3Lang Hames/// index (register interval). 360233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang HamesVNInfo *LiveInterval::findDefinedVNInfoForRegInt(SlotIndex Idx) const { 3613f32d65912b4da23793dab618d981be2ce11c331Evan Cheng for (LiveInterval::const_vni_iterator i = vni_begin(), e = vni_end(); 3628651125d2885f74546b6e2a556082111d5b75da3Lang Hames i != e; ++i) { 3638651125d2885f74546b6e2a556082111d5b75da3Lang Hames if ((*i)->def == Idx) 3648651125d2885f74546b6e2a556082111d5b75da3Lang Hames return *i; 3658651125d2885f74546b6e2a556082111d5b75da3Lang Hames } 3668651125d2885f74546b6e2a556082111d5b75da3Lang Hames 3678651125d2885f74546b6e2a556082111d5b75da3Lang Hames return 0; 3688651125d2885f74546b6e2a556082111d5b75da3Lang Hames} 3698651125d2885f74546b6e2a556082111d5b75da3Lang Hames 3706d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// join - Join two live intervals (this, and other) together. This applies 3716d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// mappings to the value numbers in the LHS/RHS intervals as specified. If 3726d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner/// the intervals are not joinable, this aborts. 373233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesvoid LiveInterval::join(LiveInterval &Other, 374233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames const int *LHSValNoAssignments, 3751b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen const int *RHSValNoAssignments, 37690f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng SmallVector<VNInfo*, 16> &NewVNInfo, 37790f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng MachineRegisterInfo *MRI) { 3786d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // Determine if any of our live range values are mapped. This is uncommon, so 3791b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen // we want to avoid the interval scan if not. 3806d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner bool MustMapCurValNos = false; 381343013538f72f2202338f57161c0bd92344ca407Evan Cheng unsigned NumVals = getNumValNums(); 382343013538f72f2202338f57161c0bd92344ca407Evan Cheng unsigned NumNewVals = NewVNInfo.size(); 383343013538f72f2202338f57161c0bd92344ca407Evan Cheng for (unsigned i = 0; i != NumVals; ++i) { 384343013538f72f2202338f57161c0bd92344ca407Evan Cheng unsigned LHSValID = LHSValNoAssignments[i]; 385343013538f72f2202338f57161c0bd92344ca407Evan Cheng if (i != LHSValID || 386f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng (NewVNInfo[LHSValID] && NewVNInfo[LHSValID] != getValNumInfo(i))) 3876d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner MustMapCurValNos = true; 3886d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 3897ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng 3906d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // If we have to apply a mapping to our base interval assignment, rewrite it 3916d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // now. 3926d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (MustMapCurValNos) { 3936d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // Map the first live range. 3946d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner iterator OutIt = begin(); 3957ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng OutIt->valno = NewVNInfo[LHSValNoAssignments[OutIt->valno->id]]; 3966d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner ++OutIt; 3976d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner for (iterator I = OutIt, E = end(); I != E; ++I) { 3987ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng OutIt->valno = NewVNInfo[LHSValNoAssignments[I->valno->id]]; 3991b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 4006d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // If this live range has the same value # as its immediate predecessor, 4016d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // and if they are neighbors, remove one LiveRange. This happens when we 4026d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // have [0,3:0)[4,7:1) and map 0/1 onto the same value #. 4037ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (OutIt->valno == (OutIt-1)->valno && (OutIt-1)->end == OutIt->start) { 4046d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner (OutIt-1)->end = OutIt->end; 4056d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } else { 4066d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (I != OutIt) { 4076d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner OutIt->start = I->start; 4086d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner OutIt->end = I->end; 4096d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 4101b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 4116d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // Didn't merge, on to the next one. 4126d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner ++OutIt; 4136d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 4146d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner } 4151b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 4166d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // If we merge some live ranges, chop off the end. 4176d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner ranges.erase(OutIt, end()); 418deb9971061cfb9c57930724fcf8d62fb26dc2213Chris Lattner } 4194f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 4207ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng // Remember assignements because val# ids are changing. 421343013538f72f2202338f57161c0bd92344ca407Evan Cheng SmallVector<unsigned, 16> OtherAssignments; 4227ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng for (iterator I = Other.begin(), E = Other.end(); I != E; ++I) 4237ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng OtherAssignments.push_back(RHSValNoAssignments[I->valno->id]); 4247ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng 4257ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng // Update val# info. Renumber them and make sure they all belong to this 426f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng // LiveInterval now. Also remove dead val#'s. 427f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng unsigned NumValNos = 0; 428f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng for (unsigned i = 0; i < NumNewVals; ++i) { 429343013538f72f2202338f57161c0bd92344ca407Evan Cheng VNInfo *VNI = NewVNInfo[i]; 430f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng if (VNI) { 43130590f502325321958b35bec7295159e3948291aEvan Cheng if (NumValNos >= NumVals) 432f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng valnos.push_back(VNI); 4331b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen else 434f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng valnos[NumValNos] = VNI; 435f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng VNI->id = NumValNos++; // Renumber val#. 436343013538f72f2202338f57161c0bd92344ca407Evan Cheng } 4377ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng } 438343013538f72f2202338f57161c0bd92344ca407Evan Cheng if (NumNewVals < NumVals) 439343013538f72f2202338f57161c0bd92344ca407Evan Cheng valnos.resize(NumNewVals); // shrinkify 4404f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 4416d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner // Okay, now insert the RHS live ranges into the LHS. 442c114b2cad7293d98686d380273085f5c32966b52Chris Lattner iterator InsertPos = begin(); 4437ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng unsigned RangeNo = 0; 4447ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng for (iterator I = Other.begin(), E = Other.end(); I != E; ++I, ++RangeNo) { 4457ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng // Map the valno in the other live range to the current live range. 4467ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng I->valno = NewVNInfo[OtherAssignments[RangeNo]]; 447f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng assert(I->valno && "Adding a dead range?"); 448abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner InsertPos = addRangeFrom(*I, InsertPos); 449abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner } 4506d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner 45129ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene ComputeJoinedWeight(Other); 452fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 453fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 454f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner/// MergeRangesInAsValue - Merge all of the intervals in RHS into this live 455f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner/// interval as the specified value number. The LiveRanges in RHS are 456f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner/// allowed to overlap with LiveRanges in the current interval, but only if 457f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner/// the overlapping LiveRanges have the specified value number. 4581b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesenvoid LiveInterval::MergeRangesInAsValue(const LiveInterval &RHS, 4597ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *LHSValNo) { 460f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner // TODO: Make this more efficient. 461f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner iterator InsertPos = begin(); 462f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) { 4637ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng // Map the valno in the other live range to the current live range. 464f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner LiveRange Tmp = *I; 4657ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng Tmp.valno = LHSValNo; 466f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner InsertPos = addRangeFrom(Tmp, InsertPos); 467f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner } 468f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner} 469f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 470f21f0205b5dec61f165518887f54e01ab5aab13cChris Lattner 47132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng/// MergeValueInAsValue - Merge all of the live ranges of a specific val# 47232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng/// in RHS into this live interval as the specified value number. 47332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng/// The LiveRanges in RHS are allowed to overlap with LiveRanges in the 4743c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng/// current interval, it will replace the value numbers of the overlaped 4753c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng/// live ranges with the specified value number. 476233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hamesvoid LiveInterval::MergeValueInAsValue( 477233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames const LiveInterval &RHS, 478233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames const VNInfo *RHSValNo, VNInfo *LHSValNo) { 4793c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng SmallVector<VNInfo*, 4> ReplacedValNos; 4803c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng iterator IP = begin(); 48132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng for (const_iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) { 482014b8631c0df0c5a91ccee2485bcd408844ed377Jakob Stoklund Olesen assert(I->valno == RHS.getValNumInfo(I->valno->id) && "Bad VNInfo"); 48332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (I->valno != RHSValNo) 48432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng continue; 485233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex Start = I->start, End = I->end; 4863c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng IP = std::upper_bound(IP, end(), Start); 4873c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng // If the start of this range overlaps with an existing liverange, trim it. 4883c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng if (IP != begin() && IP[-1].end > Start) { 489294e6524916aecd874dddeede4cc074d31f5f59fEvan Cheng if (IP[-1].valno != LHSValNo) { 490294e6524916aecd874dddeede4cc074d31f5f59fEvan Cheng ReplacedValNos.push_back(IP[-1].valno); 491294e6524916aecd874dddeede4cc074d31f5f59fEvan Cheng IP[-1].valno = LHSValNo; // Update val#. 4923c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng } 4933c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng Start = IP[-1].end; 4943c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng // Trimmed away the whole range? 4953c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng if (Start >= End) continue; 4963c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng } 4973c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng // If the end of this range overlaps with an existing liverange, trim it. 4983c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng if (IP != end() && End > IP->start) { 4993c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng if (IP->valno != LHSValNo) { 5003c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng ReplacedValNos.push_back(IP->valno); 5013c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng IP->valno = LHSValNo; // Update val#. 5023c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng } 5033c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng End = IP->start; 5043c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng // If this trimmed away the whole range, ignore it. 5053c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng if (Start == End) continue; 5063c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng } 5071b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 50832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // Map the valno in the other live range to the current live range. 5093c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng IP = addRangeFrom(LiveRange(Start, End, LHSValNo), IP); 5103c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng } 5113c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng 5123c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng 5133c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng SmallSet<VNInfo*, 4> Seen; 5143c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng for (unsigned i = 0, e = ReplacedValNos.size(); i != e; ++i) { 5153c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng VNInfo *V1 = ReplacedValNos[i]; 5163c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng if (Seen.insert(V1)) { 5173c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng bool isDead = true; 5183c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng for (const_iterator I = begin(), E = end(); I != E; ++I) 5193c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng if (I->valno == V1) { 5203c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng isDead = false; 5213c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng break; 5221b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen } 5233c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng if (isDead) { 5246f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames // Now that V1 is dead, remove it. 5256f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames markValNoForDeletion(V1); 5263c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng } 5273c1f4a4d4726d1213871c9fc9b42822341fd3f55Evan Cheng } 52832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng } 52932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng} 53032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng 53132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng 532a2e6435e483f30e00382a5758f6dcc67e213b57aEvan Cheng 533f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// MergeValueNumberInto - This method is called when two value nubmers 534f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// are found to be equivalent. This eliminates V1, replacing all 535f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// LiveRanges with the V1 value number with the V2 value number. This can 536f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner/// cause merging of V1/V2 values numbers and compaction of the value space. 5375b93f6fa82e33b17d618b3e24da513f547861481Owen AndersonVNInfo* LiveInterval::MergeValueNumberInto(VNInfo *V1, VNInfo *V2) { 538f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner assert(V1 != V2 && "Identical value#'s are always equivalent!"); 539f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 540f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // This code actually merges the (numerically) larger value number into the 541f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // smaller value number, which is likely to allow us to compactify the value 542f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // space. The only thing we have to be careful of is to preserve the 543f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // instruction that defines the result value. 544f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 545f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Make sure V2 is smaller than V1. 5467ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (V1->id < V2->id) { 54752c1afcaea61440950a11a4ccadac4354420d727Lang Hames V1->copyFrom(*V2); 548f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner std::swap(V1, V2); 549f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 550f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 551f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Merge V1 live ranges into V2. 552f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner for (iterator I = begin(); I != end(); ) { 553f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner iterator LR = I++; 5547ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (LR->valno != V1) continue; // Not a V1 LiveRange. 5551b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 556f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Okay, we found a V1 live range. If it had a previous, touching, V2 live 557f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // range, extend it. 558f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (LR != begin()) { 559f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner iterator Prev = LR-1; 5607ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (Prev->valno == V2 && Prev->end == LR->start) { 561f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner Prev->end = LR->end; 562f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 563f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Erase this live-range. 564f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner ranges.erase(LR); 565f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner I = Prev+1; 566f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner LR = Prev; 567f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 568f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 5691b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 570f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Okay, now we have a V1 or V2 live range that is maximally merged forward. 571f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // Ensure that it is a V2 live-range. 5727ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LR->valno = V2; 5731b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 574f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // If we can merge it into later V2 live ranges, do so now. We ignore any 575f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // following V1 live ranges, as they will be merged in subsequent iterations 576f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner // of the loop. 577f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner if (I != end()) { 5787ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng if (I->start == LR->end && I->valno == V2) { 579f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner LR->end = I->end; 580f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner ranges.erase(I); 581f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner I = LR+1; 582f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 583f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 584f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 5851b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 586e0a73ec0a982a4213f3de9860545d9bf2814593dJakob Stoklund Olesen // Merge the relevant flags. 587e0a73ec0a982a4213f3de9860545d9bf2814593dJakob Stoklund Olesen V2->mergeFlags(V1); 588e0a73ec0a982a4213f3de9860545d9bf2814593dJakob Stoklund Olesen 5896f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames // Now that V1 is dead, remove it. 5906f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames markValNoForDeletion(V1); 5911b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 5925b93f6fa82e33b17d618b3e24da513f547861481Owen Anderson return V2; 593f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner} 594f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner 59532dfbeada7292167bb488f36a71a5a6a519ddaffEvan Chengvoid LiveInterval::Copy(const LiveInterval &RHS, 59690f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng MachineRegisterInfo *MRI, 597991de14dd62dcbab4b31357ae22dc5b053ba50a0Benjamin Kramer VNInfo::Allocator &VNInfoAllocator) { 59832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng ranges.clear(); 59932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng valnos.clear(); 600358dec51804ee52e47ea3a47c9248086e458ad7cEvan Cheng std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(RHS.reg); 60190f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng MRI->setRegAllocationHint(reg, Hint.first, Hint.second); 60290f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng 60332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng weight = RHS.weight; 60432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng for (unsigned i = 0, e = RHS.getNumValNums(); i != e; ++i) { 60532dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng const VNInfo *VNI = RHS.getValNumInfo(i); 606857c4e01f85601cf2084adb860616256ee47c177Lang Hames createValueCopy(VNI, VNInfoAllocator); 60732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng } 60832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng for (unsigned i = 0, e = RHS.ranges.size(); i != e; ++i) { 60932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng const LiveRange &LR = RHS.ranges[i]; 61032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng addRange(LiveRange(LR.start, LR.end, getValNumInfo(LR.valno->id))); 61132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng } 61232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng} 61332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng 614e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Chengunsigned LiveInterval::getSize() const { 615e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng unsigned Sum = 0; 616e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng for (const_iterator I = begin(), E = end(); I != E; ++I) 6178651125d2885f74546b6e2a556082111d5b75da3Lang Hames Sum += I->start.distance(I->end); 618e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng return Sum; 619e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng} 620e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng 62129ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene/// ComputeJoinedWeight - Set the weight of a live interval Joined 62229ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene/// after Other has been merged into it. 62329ff37f39c305455752941fbf8a426b1f4d877fcDavid Greenevoid LiveInterval::ComputeJoinedWeight(const LiveInterval &Other) { 62429ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene // If either of these intervals was spilled, the weight is the 62529ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene // weight of the non-spilled interval. This can only happen with 62629ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene // iterative coalescers. 62729ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene 62892b78bbc7f2ee919a2d09ed00fd35d1eb7f5f548David Greene if (Other.weight != HUGE_VALF) { 62992b78bbc7f2ee919a2d09ed00fd35d1eb7f5f548David Greene weight += Other.weight; 63092b78bbc7f2ee919a2d09ed00fd35d1eb7f5f548David Greene } 63192b78bbc7f2ee919a2d09ed00fd35d1eb7f5f548David Greene else if (weight == HUGE_VALF && 63229ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene !TargetRegisterInfo::isPhysicalRegister(reg)) { 63329ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene // Remove this assert if you have an iterative coalescer 63429ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene assert(0 && "Joining to spilled interval"); 63529ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene weight = Other.weight; 63629ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene } 63729ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene else { 63829ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene // Otherwise the weight stays the same 63929ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene // Remove this assert if you have an iterative coalescer 64029ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene assert(0 && "Joining from spilled interval"); 64129ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene } 64229ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene} 64329ff37f39c305455752941fbf8a426b1f4d877fcDavid Greene 6441cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbarraw_ostream& llvm::operator<<(raw_ostream& os, const LiveRange &LR) { 6451cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar return os << '[' << LR.start << ',' << LR.end << ':' << LR.valno->id << ")"; 6461cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar} 647abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 648abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattnervoid LiveRange::dump() const { 6495242154b558f0783830938f18153e0a7964fb4faDavid Greene dbgs() << *this << "\n"; 650fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 651fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 652c02497f5bae87e71fd5617db5751cb0b3a14bbedChris Lattnervoid LiveInterval::print(raw_ostream &OS, const TargetRegisterInfo *TRI) const { 65399ec779a93cf7a09ac336b63d2d67818960343a1Evan Cheng if (isStackSlot()) 65499ec779a93cf7a09ac336b63d2d67818960343a1Evan Cheng OS << "SS#" << getStackSlotIndex(); 6553f32d65912b4da23793dab618d981be2ce11c331Evan Cheng else if (TRI && TargetRegisterInfo::isPhysicalRegister(reg)) 656e6d088acc90e422451e098555d383d4d65b6ce6bBill Wendling OS << TRI->getName(reg); 65738135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner else 65838135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner OS << "%reg" << reg; 65938135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner 66038135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner OS << ',' << weight; 66138135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner 66238135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner if (empty()) 6633f32d65912b4da23793dab618d981be2ce11c331Evan Cheng OS << " EMPTY"; 66438135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner else { 66538135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner OS << " = "; 66638135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner for (LiveInterval::Ranges::const_iterator I = ranges.begin(), 667014b8631c0df0c5a91ccee2485bcd408844ed377Jakob Stoklund Olesen E = ranges.end(); I != E; ++I) { 668014b8631c0df0c5a91ccee2485bcd408844ed377Jakob Stoklund Olesen OS << *I; 669014b8631c0df0c5a91ccee2485bcd408844ed377Jakob Stoklund Olesen assert(I->valno == getValNumInfo(I->valno->id) && "Bad VNInfo"); 670014b8631c0df0c5a91ccee2485bcd408844ed377Jakob Stoklund Olesen } 67138135af219c48a8626d6af34a92e7e8bb957c81fChris Lattner } 67215a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen 673be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Print value number info. 6746d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner if (getNumValNums()) { 675be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner OS << " "; 6761a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng unsigned vnum = 0; 6771a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng for (const_vni_iterator i = vni_begin(), e = vni_end(); i != e; 6781a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng ++i, ++vnum) { 6797ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng const VNInfo *vni = *i; 6801a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng if (vnum) OS << " "; 6811a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng OS << vnum << "@"; 682857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (vni->isUnused()) { 6838df786012dc6b875f31ba4152e09c6e0098082eeEvan Cheng OS << "x"; 684be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner } else { 6856e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames OS << vni->def; 686a818c072af2f94704d08776d5bc7c50a012e40c2Jakob Stoklund Olesen if (vni->isPHIDef()) 687a818c072af2f94704d08776d5bc7c50a012e40c2Jakob Stoklund Olesen OS << "-phidef"; 688d9f6ec977a9543e88c52fa5fb3737ae03402fc4cJakob Stoklund Olesen if (vni->hasPHIKill()) 689d9f6ec977a9543e88c52fa5fb3737ae03402fc4cJakob Stoklund Olesen OS << "-phikill"; 690d9f6ec977a9543e88c52fa5fb3737ae03402fc4cJakob Stoklund Olesen if (vni->hasRedefByEC()) 691d9f6ec977a9543e88c52fa5fb3737ae03402fc4cJakob Stoklund Olesen OS << "-ec"; 692a8d94f1315f722de056af03763664b77a5baac26Evan Cheng } 693be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner } 694be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner } 695fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 696abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 697abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattnervoid LiveInterval::dump() const { 6985242154b558f0783830938f18153e0a7964fb4faDavid Greene dbgs() << *this << "\n"; 699abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner} 700c21c5eeb4f56f160e79522df2d3aab5cfe73c05dJeff Cohen 701c21c5eeb4f56f160e79522df2d3aab5cfe73c05dJeff Cohen 7021cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbarvoid LiveRange::print(raw_ostream &os) const { 7031cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar os << *this; 7041cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar} 7050253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 7060253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen/// ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a 7070253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen/// LiveInterval into equivalence clases of connected components. A 7080253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen/// LiveInterval that has multiple connected components can be broken into 7090253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen/// multiple LiveIntervals. 7100253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 7110253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesenvoid ConnectedVNInfoEqClasses::Connect(unsigned a, unsigned b) { 7120253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen unsigned eqa = eqClass_[a]; 7130253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen unsigned eqb = eqClass_[b]; 7140253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen if (eqa == eqb) 7150253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen return; 71654f32e6575d0c1b920ae5151c229f1187bae0cbfJakob Stoklund Olesen // Make sure a and b are in the same class while maintaining eqClass_[i] <= i. 7170253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen if (eqa > eqb) 71854f32e6575d0c1b920ae5151c229f1187bae0cbfJakob Stoklund Olesen eqClass_[a] = eqb; 71954f32e6575d0c1b920ae5151c229f1187bae0cbfJakob Stoklund Olesen else 72054f32e6575d0c1b920ae5151c229f1187bae0cbfJakob Stoklund Olesen eqClass_[b] = eqa; 7210253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen} 7220253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 7230253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesenunsigned ConnectedVNInfoEqClasses::Renumber() { 72454f32e6575d0c1b920ae5151c229f1187bae0cbfJakob Stoklund Olesen // Assign final class numbers. 72554f32e6575d0c1b920ae5151c229f1187bae0cbfJakob Stoklund Olesen // We use the fact that eqClass_[i] == i for class leaders. 72654f32e6575d0c1b920ae5151c229f1187bae0cbfJakob Stoklund Olesen // For others, eqClass_[i] points to an earlier value in the same class. 7270253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen unsigned count = 0; 7280253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen for (unsigned i = 0, e = eqClass_.size(); i != e; ++i) { 7290253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen unsigned q = eqClass_[i]; 73054f32e6575d0c1b920ae5151c229f1187bae0cbfJakob Stoklund Olesen assert(q <= i && "Invariant broken"); 73154f32e6575d0c1b920ae5151c229f1187bae0cbfJakob Stoklund Olesen eqClass_[i] = q == i ? count++ : eqClass_[q]; 7320253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen } 7330253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 7340253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen return count; 7350253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen} 7360253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 7370253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesenunsigned ConnectedVNInfoEqClasses::Classify(const LiveInterval *LI) { 73854f32e6575d0c1b920ae5151c229f1187bae0cbfJakob Stoklund Olesen // Create initial equivalence classes. 7390253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen eqClass_.clear(); 74054f32e6575d0c1b920ae5151c229f1187bae0cbfJakob Stoklund Olesen eqClass_.reserve(LI->getNumValNums()); 74154f32e6575d0c1b920ae5151c229f1187bae0cbfJakob Stoklund Olesen for (unsigned i = 0, e = LI->getNumValNums(); i != e; ++i) 74254f32e6575d0c1b920ae5151c229f1187bae0cbfJakob Stoklund Olesen eqClass_.push_back(i); 74354f32e6575d0c1b920ae5151c229f1187bae0cbfJakob Stoklund Olesen 74454f32e6575d0c1b920ae5151c229f1187bae0cbfJakob Stoklund Olesen // Determine connections. 7450253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen for (LiveInterval::const_vni_iterator I = LI->vni_begin(), E = LI->vni_end(); 7460253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen I != E; ++I) { 7470253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen const VNInfo *VNI = *I; 7480253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen if (VNI->id == eqClass_.size()) 7490253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen eqClass_.push_back(VNI->id); 7500253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen assert(!VNI->isUnused() && "Cannot handle unused values"); 7510253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen if (VNI->isPHIDef()) { 7520253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen const MachineBasicBlock *MBB = lis_.getMBBFromIndex(VNI->def); 7530253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen assert(MBB && "Phi-def has no defining MBB"); 7540253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // Connect to values live out of predecessors. 7550253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 7560253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) 7570253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen if (const VNInfo *PVNI = 7580253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen LI->getVNInfoAt(lis_.getMBBEndIdx(*PI).getPrevSlot())) 7590253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen Connect(VNI->id, PVNI->id); 7600253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen } else { 7610253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // Normal value defined by an instruction. Check for two-addr redef. 7620253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // FIXME: This could be coincidental. Should we really check for a tied 7630253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // operand constraint? 7640253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen if (const VNInfo *UVNI = LI->getVNInfoAt(VNI->def.getUseIndex())) 7650253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen Connect(VNI->id, UVNI->id); 7660253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen } 7670253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen } 7680253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen return Renumber(); 7690253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen} 7700253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 7710253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesenvoid ConnectedVNInfoEqClasses::Distribute(LiveInterval *LIV[]) { 7720253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen assert(LIV[0] && "LIV[0] must be set"); 7730253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen LiveInterval &LI = *LIV[0]; 7740253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // Check that they likely ran Classify() on LIV[0] first. 7750253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen assert(eqClass_.size() == LI.getNumValNums() && "Bad classification data"); 7760253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 7770253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // First move runs to new intervals. 7780253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen LiveInterval::iterator J = LI.begin(), E = LI.end(); 7790253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen while (J != E && eqClass_[J->valno->id] == 0) 7800253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen ++J; 7810253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen for (LiveInterval::iterator I = J; I != E; ++I) { 7820253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen if (unsigned eq = eqClass_[I->valno->id]) { 783ccefe32141c96faa05445bce0b26f1acd8bdc1b8Benjamin Kramer assert((LIV[eq]->empty() || LIV[eq]->expiredAt(I->start)) && 7840253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen "New intervals should be empty"); 7850253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen LIV[eq]->ranges.push_back(*I); 7860253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen } else 7870253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen *J++ = *I; 7880253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen } 7890253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen LI.ranges.erase(J, E); 7900253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 7910253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // Transfer VNInfos to their new owners and renumber them. 7920253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen unsigned j = 0, e = LI.getNumValNums(); 7930253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen while (j != e && eqClass_[j] == 0) 7940253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen ++j; 7950253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen for (unsigned i = j; i != e; ++i) { 7960253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen VNInfo *VNI = LI.getValNumInfo(i); 7970253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen if (unsigned eq = eqClass_[i]) { 7980253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen VNI->id = LIV[eq]->getNumValNums(); 7990253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen LIV[eq]->valnos.push_back(VNI); 8000253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen } else { 8010253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen VNI->id = j; 8020253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen LI.valnos[j++] = VNI; 8030253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen } 8040253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen } 8050253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen LI.valnos.resize(j); 8060253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen} 807