LiveInterval.cpp revision fb449b9ea5a37fb411aee7d42f6a76119602288d
1fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner//===-- LiveInterval.cpp - Live Interval Representation -------------------===// 2fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 3fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// The LLVM Compiler Infrastructure 4fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 5fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// This file was developed by the LLVM research group and is distributed under 6fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// the University of Illinois Open Source 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 13fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// such that v is live at j' abd 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 21fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner#include "LiveInterval.h" 22fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner#include "Support/STLExtras.h" 23fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner#include <ostream> 24fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattnerusing namespace llvm; 25fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 26fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// An example for liveAt(): 27fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 28fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// this = [1,4), liveAt(0) will return false. The instruction defining 29fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// this spans slots [0,3]. The interval belongs to an spilled 30fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// definition of the variable it represents. This is because slot 1 is 31fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// used (def slot) and spans up to slot 3 (store slot). 32fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 33fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattnerbool LiveInterval::liveAt(unsigned index) const { 34fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner LiveRange dummy(index, index+1); 35fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner Ranges::const_iterator r = std::upper_bound(ranges.begin(), 36fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner ranges.end(), 37fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner dummy); 38fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (r == ranges.begin()) 39fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return false; 40fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 41fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner --r; 42fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return index >= r->start && index < r->end; 43fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 44fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 45fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// An example for overlaps(): 46fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 47fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 0: A = ... 48fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 4: B = ... 49fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 8: C = A + B ;; last use of A 50fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 51fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// The live intervals should look like: 52fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 53fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// A = [3, 11) 54fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// B = [7, x) 55fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// C = [11, y) 56fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 57fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// A->overlaps(C) should return false since we want to be able to join 58fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// A and C. 59fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattnerbool LiveInterval::overlaps(const LiveInterval& other) const { 60fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner Ranges::const_iterator i = ranges.begin(); 61fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner Ranges::const_iterator ie = ranges.end(); 62fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner Ranges::const_iterator j = other.ranges.begin(); 63fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner Ranges::const_iterator je = other.ranges.end(); 64fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i->start < j->start) { 65fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner i = std::upper_bound(i, ie, *j); 66fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i != ranges.begin()) --i; 67fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 68fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner else if (j->start < i->start) { 69fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner j = std::upper_bound(j, je, *i); 70fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (j != other.ranges.begin()) --j; 71fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 72fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 73fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner while (i != ie && j != je) { 74fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i->start == j->start) 75fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return true; 76fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 77fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i->start > j->start) { 78fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner swap(i, j); 79fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner swap(ie, je); 80fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 81fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner assert(i->start < j->start); 82fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 83fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i->end > j->start) 84fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return true; 85fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner ++i; 86fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 87fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 88fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return false; 89fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 90fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 91fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattnervoid LiveInterval::addRange(LiveRange LR) { 92fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner Ranges::iterator it = 93fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner ranges.insert(std::upper_bound(ranges.begin(), ranges.end(), LR), LR); 94fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 95fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner mergeRangesBackward(mergeRangesForward(it)); 96fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 97fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 98fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattnervoid LiveInterval::join(const LiveInterval& other) { 99fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner Ranges::iterator cur = ranges.begin(); 100fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner isDefinedOnce &= other.isDefinedOnce; 101fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 102fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner for (Ranges::const_iterator i = other.ranges.begin(), 103fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner e = other.ranges.end(); i != e; ++i) { 104fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner cur = ranges.insert(std::upper_bound(cur, ranges.end(), *i), *i); 105fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner cur = mergeRangesBackward(mergeRangesForward(cur)); 106fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 107fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner weight += other.weight; 108fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 109fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 110fb449b9ea5a37fb411aee7d42f6a76119602288dChris LattnerLiveInterval::Ranges::iterator 111fb449b9ea5a37fb411aee7d42f6a76119602288dChris LattnerLiveInterval::mergeRangesForward(Ranges::iterator it) { 112fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner Ranges::iterator n; 113fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner while ((n = next(it)) != ranges.end()) { 114fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (n->start > it->end) 115fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner break; 116fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner it->end = std::max(it->end, n->end); 117fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner n = ranges.erase(n); 118fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 119fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return it; 120fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 121fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 122fb449b9ea5a37fb411aee7d42f6a76119602288dChris LattnerLiveInterval::Ranges::iterator 123fb449b9ea5a37fb411aee7d42f6a76119602288dChris LattnerLiveInterval::mergeRangesBackward(Ranges::iterator it) { 124fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner while (it != ranges.begin()) { 125fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner Ranges::iterator p = prior(it); 126fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (it->start > p->end) 127fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner break; 128fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 129fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner it->start = std::min(it->start, p->start); 130fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner it->end = std::max(it->end, p->end); 131fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner it = ranges.erase(p); 132fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 133fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 134fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return it; 135fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 136fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 137fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattnerstd::ostream& llvm::operator<<(std::ostream& os, const LiveRange &LR) { 138fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return os << "[" << LR.start << "," << LR.end << ")"; 139fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 140fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 141fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattnerstd::ostream& llvm::operator<<(std::ostream& os, const LiveInterval& li) { 142fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner os << "%reg" << li.reg << ',' << li.weight; 143fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (li.empty()) 144fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return os << "EMPTY"; 145fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 146fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner os << " = "; 147fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner for (LiveInterval::Ranges::const_iterator i = li.ranges.begin(), 148fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner e = li.ranges.end(); i != e; ++i) 149fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner os << *i; 150fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return os; 151fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 152