LiveInterval.cpp revision ebd7e6c54dce754a88d8f38df4ac2f388f35435e
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// 33ebd7e6c54dce754a88d8f38df4ac2f388f35435eChris Lattnerbool LiveInterval::liveAt(unsigned I) const { 34ebd7e6c54dce754a88d8f38df4ac2f388f35435eChris Lattner Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I); 35ebd7e6c54dce754a88d8f38df4ac2f388f35435eChris Lattner 36fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (r == ranges.begin()) 37fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return false; 38fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 39fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner --r; 40ebd7e6c54dce754a88d8f38df4ac2f388f35435eChris Lattner return I >= r->start && I < r->end; 41fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 42fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 43fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// An example for overlaps(): 44fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 45fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 0: A = ... 46fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 4: B = ... 47fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 8: C = A + B ;; last use of A 48fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 49fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// The live intervals should look like: 50fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 51fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// A = [3, 11) 52fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// B = [7, x) 53fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// C = [11, y) 54fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 55fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// A->overlaps(C) should return false since we want to be able to join 56fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// A and C. 57fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattnerbool LiveInterval::overlaps(const LiveInterval& other) const { 58fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner Ranges::const_iterator i = ranges.begin(); 59fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner Ranges::const_iterator ie = ranges.end(); 60fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner Ranges::const_iterator j = other.ranges.begin(); 61fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner Ranges::const_iterator je = other.ranges.end(); 62fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i->start < j->start) { 63fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner i = std::upper_bound(i, ie, *j); 64fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i != ranges.begin()) --i; 65fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 66fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner else if (j->start < i->start) { 67fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner j = std::upper_bound(j, je, *i); 68fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (j != other.ranges.begin()) --j; 69fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 70fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 71fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner while (i != ie && j != je) { 72fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i->start == j->start) 73fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return true; 74fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 75fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i->start > j->start) { 76fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner swap(i, j); 77fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner swap(ie, je); 78fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 79fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner assert(i->start < j->start); 80fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 81fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (i->end > j->start) 82fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return true; 83fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner ++i; 84fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 85fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 86fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return false; 87fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 88fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 89fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattnervoid LiveInterval::addRange(LiveRange LR) { 90fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner Ranges::iterator it = 91fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner ranges.insert(std::upper_bound(ranges.begin(), ranges.end(), LR), LR); 92fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 93fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner mergeRangesBackward(mergeRangesForward(it)); 94fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 95fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 96fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattnervoid LiveInterval::join(const LiveInterval& other) { 97fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner Ranges::iterator cur = ranges.begin(); 98fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner isDefinedOnce &= other.isDefinedOnce; 99fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 100fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner for (Ranges::const_iterator i = other.ranges.begin(), 101fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner e = other.ranges.end(); i != e; ++i) { 102fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner cur = ranges.insert(std::upper_bound(cur, ranges.end(), *i), *i); 103fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner cur = mergeRangesBackward(mergeRangesForward(cur)); 104fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 105fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner weight += other.weight; 106fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 107fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 108fb449b9ea5a37fb411aee7d42f6a76119602288dChris LattnerLiveInterval::Ranges::iterator 109fb449b9ea5a37fb411aee7d42f6a76119602288dChris LattnerLiveInterval::mergeRangesForward(Ranges::iterator it) { 110fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner Ranges::iterator n; 111fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner while ((n = next(it)) != ranges.end()) { 112fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (n->start > it->end) 113fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner break; 114fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner it->end = std::max(it->end, n->end); 115fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner n = ranges.erase(n); 116fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 117fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return it; 118fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 119fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 120fb449b9ea5a37fb411aee7d42f6a76119602288dChris LattnerLiveInterval::Ranges::iterator 121fb449b9ea5a37fb411aee7d42f6a76119602288dChris LattnerLiveInterval::mergeRangesBackward(Ranges::iterator it) { 122fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner while (it != ranges.begin()) { 123fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner Ranges::iterator p = prior(it); 124fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (it->start > p->end) 125fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner break; 126fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 127fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner it->start = std::min(it->start, p->start); 128fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner it->end = std::max(it->end, p->end); 129fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner it = ranges.erase(p); 130fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 131fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 132fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return it; 133fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 134fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 135fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattnerstd::ostream& llvm::operator<<(std::ostream& os, const LiveRange &LR) { 136fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return os << "[" << LR.start << "," << LR.end << ")"; 137fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 138fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 139fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattnerstd::ostream& llvm::operator<<(std::ostream& os, const LiveInterval& li) { 140fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner os << "%reg" << li.reg << ',' << li.weight; 141fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner if (li.empty()) 142fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return os << "EMPTY"; 143fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 144fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner os << " = "; 145fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner for (LiveInterval::Ranges::const_iterator i = li.ranges.begin(), 146fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner e = li.ranges.end(); i != e; ++i) 147fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner os << *i; 148fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return os; 149fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner} 150