LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

LiveInterval.cpp

Go to the documentation of this file.
00001 //===-- LiveInterval.cpp - Live Interval Representation -------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements the LiveRange and LiveInterval classes.  Given some
00011 // numbering of each the machine instructions an interval [i, j) is said to be a
00012 // live interval for register v if there is no instruction with number j' > j
00013 // such that v is live at j' abd there is no instruction with number i' < i such
00014 // that v is live at i'. In this implementation intervals can have holes,
00015 // i.e. an interval might look like [1,20), [50,65), [1000,1001).  Each
00016 // individual range is represented as an instance of LiveRange, and the whole
00017 // interval is represented as an instance of LiveInterval.
00018 //
00019 //===----------------------------------------------------------------------===//
00020 
00021 #include "LiveInterval.h"
00022 #include "llvm/ADT/STLExtras.h"
00023 #include <algorithm>
00024 #include <iostream>
00025 #include <map>
00026 using namespace llvm;
00027 
00028 // An example for liveAt():
00029 //
00030 // this = [1,4), liveAt(0) will return false. The instruction defining this
00031 // spans slots [0,3]. The interval belongs to an spilled definition of the
00032 // variable it represents. This is because slot 1 is used (def slot) and spans
00033 // up to slot 3 (store slot).
00034 //
00035 bool LiveInterval::liveAt(unsigned I) const {
00036   Ranges::const_iterator r = std::upper_bound(ranges.begin(), ranges.end(), I);
00037                                               
00038   if (r == ranges.begin())
00039     return false;
00040 
00041   --r;
00042   return r->contains(I);
00043 }
00044 
00045 // overlaps - Return true if the intersection of the two live intervals is
00046 // not empty.
00047 //
00048 // An example for overlaps():
00049 //
00050 // 0: A = ...
00051 // 4: B = ...
00052 // 8: C = A + B ;; last use of A
00053 //
00054 // The live intervals should look like:
00055 //
00056 // A = [3, 11)
00057 // B = [7, x)
00058 // C = [11, y)
00059 //
00060 // A->overlaps(C) should return false since we want to be able to join
00061 // A and C.
00062 //
00063 bool LiveInterval::overlapsFrom(const LiveInterval& other,
00064                                 const_iterator StartPos) const {
00065   const_iterator i = begin();
00066   const_iterator ie = end();
00067   const_iterator j = StartPos;
00068   const_iterator je = other.end();
00069 
00070   assert((StartPos->start <= i->start || StartPos == other.begin()) &&
00071          StartPos != other.end() && "Bogus start position hint!");
00072 
00073   if (i->start < j->start) {
00074     i = std::upper_bound(i, ie, j->start);
00075     if (i != ranges.begin()) --i;
00076   } else if (j->start < i->start) {
00077     ++StartPos;
00078     if (StartPos != other.end() && StartPos->start <= i->start) {
00079       assert(StartPos < other.end() && i < end());
00080       j = std::upper_bound(j, je, i->start);
00081       if (j != other.ranges.begin()) --j;
00082     }
00083   } else {
00084     return true;
00085   }
00086 
00087   if (j == je) return false;
00088 
00089   while (i != ie) {
00090     if (i->start > j->start) {
00091       std::swap(i, j);
00092       std::swap(ie, je);
00093     }
00094 
00095     if (i->end > j->start)
00096       return true;
00097     ++i;
00098   }
00099 
00100   return false;
00101 }
00102 
00103 /// joinable - Two intervals are joinable if the either don't overlap at all
00104 /// or if the destination of the copy is a single assignment value, and it
00105 /// only overlaps with one value in the source interval.
00106 bool LiveInterval::joinable(const LiveInterval &other, unsigned CopyIdx) const {
00107   const LiveRange *SourceLR = other.getLiveRangeContaining(CopyIdx-1);
00108   const LiveRange *DestLR = getLiveRangeContaining(CopyIdx);
00109   assert(SourceLR && DestLR && "Not joining due to a copy?");
00110   unsigned OtherValIdx = SourceLR->ValId;
00111   unsigned ThisValIdx = DestLR->ValId;
00112 
00113   Ranges::const_iterator i = ranges.begin();
00114   Ranges::const_iterator ie = ranges.end();
00115   Ranges::const_iterator j = other.ranges.begin();
00116   Ranges::const_iterator je = other.ranges.end();
00117 
00118   if (i->start < j->start) {
00119     i = std::upper_bound(i, ie, j->start);
00120     if (i != ranges.begin()) --i;
00121   } else if (j->start < i->start) {
00122     j = std::upper_bound(j, je, i->start);
00123     if (j != other.ranges.begin()) --j;
00124   }
00125 
00126   while (i != ie && j != je) {
00127     if (i->start == j->start) {
00128       // If this is not the allowed value merge, we cannot join.
00129       if (i->ValId != ThisValIdx || j->ValId != OtherValIdx)
00130         return false;
00131     } else if (i->start < j->start) {
00132       if (i->end > j->start) {
00133         if (i->ValId != ThisValIdx || j->ValId != OtherValIdx)
00134           return false;
00135       }
00136     } else {
00137       if (j->end > i->start) {
00138         if (i->ValId != ThisValIdx || j->ValId != OtherValIdx)
00139           return false;
00140       }
00141     }
00142     if (i->end < j->end)
00143       ++i;
00144     else
00145       ++j;
00146   }
00147 
00148   return true;
00149 }
00150 
00151 
00152 /// extendIntervalEndTo - This method is used when we want to extend the range
00153 /// specified by I to end at the specified endpoint.  To do this, we should
00154 /// merge and eliminate all ranges that this will overlap with.  The iterator is
00155 /// not invalidated.
00156 void LiveInterval::extendIntervalEndTo(Ranges::iterator I, unsigned NewEnd) {
00157   assert(I != ranges.end() && "Not a valid interval!");
00158   unsigned ValId = I->ValId;
00159 
00160   // Search for the first interval that we can't merge with.
00161   Ranges::iterator MergeTo = next(I);
00162   for (; MergeTo != ranges.end() && NewEnd >= MergeTo->end; ++MergeTo) {
00163     assert(MergeTo->ValId == ValId && "Cannot merge with differing values!");
00164   }
00165 
00166   // If NewEnd was in the middle of an interval, make sure to get its endpoint.
00167   I->end = std::max(NewEnd, prior(MergeTo)->end);
00168 
00169   // Erase any dead ranges
00170   ranges.erase(next(I), MergeTo);
00171 }
00172 
00173 
00174 /// extendIntervalStartTo - This method is used when we want to extend the range
00175 /// specified by I to start at the specified endpoint.  To do this, we should
00176 /// merge and eliminate all ranges that this will overlap with.
00177 LiveInterval::Ranges::iterator 
00178 LiveInterval::extendIntervalStartTo(Ranges::iterator I, unsigned NewStart) {
00179   assert(I != ranges.end() && "Not a valid interval!");
00180   unsigned ValId = I->ValId;
00181 
00182   // Search for the first interval that we can't merge with.
00183   Ranges::iterator MergeTo = I;
00184   do {
00185     if (MergeTo == ranges.begin()) {
00186       I->start = NewStart;
00187       ranges.erase(MergeTo, I);
00188       return I;
00189     }
00190     assert(MergeTo->ValId == ValId && "Cannot merge with differing values!");
00191     --MergeTo;
00192   } while (NewStart <= MergeTo->start);
00193 
00194   // If we start in the middle of another interval, just delete a range and
00195   // extend that interval.
00196   if (MergeTo->end >= NewStart && MergeTo->ValId == ValId) {
00197     MergeTo->end = I->end;
00198   } else {
00199     // Otherwise, extend the interval right after.
00200     ++MergeTo;
00201     MergeTo->start = NewStart;
00202     MergeTo->end = I->end;
00203   }
00204 
00205   ranges.erase(next(MergeTo), next(I));
00206   return MergeTo;
00207 }
00208 
00209 LiveInterval::Ranges::iterator
00210 LiveInterval::addRangeFrom(LiveRange LR, Ranges::iterator From) {
00211   unsigned Start = LR.start, End = LR.end;
00212   Ranges::iterator it = std::upper_bound(From, ranges.end(), Start);
00213 
00214   // If the inserted interval starts in the middle or right at the end of
00215   // another interval, just extend that interval to contain the range of LR.
00216   if (it != ranges.begin()) {
00217     Ranges::iterator B = prior(it);
00218     if (LR.ValId == B->ValId) {
00219       if (B->start <= Start && B->end >= Start) {
00220         extendIntervalEndTo(B, End);
00221         return B;
00222       }
00223     } else {
00224       // Check to make sure that we are not overlapping two live ranges with
00225       // different ValId's.
00226       assert(B->end <= Start &&
00227              "Cannot overlap two LiveRanges with differing ValID's"
00228              " (did you def the same reg twice in a MachineInstr?)");
00229     }
00230   }
00231 
00232   // Otherwise, if this range ends in the middle of, or right next to, another
00233   // interval, merge it into that interval.
00234   if (it != ranges.end())
00235     if (LR.ValId == it->ValId) {
00236       if (it->start <= End) {
00237         it = extendIntervalStartTo(it, Start);
00238 
00239         // If LR is a complete superset of an interval, we may need to grow its
00240         // endpoint as well.
00241         if (End > it->end)
00242           extendIntervalEndTo(it, End);
00243         return it;
00244       }
00245     } else {
00246       // Check to make sure that we are not overlapping two live ranges with
00247       // different ValId's.
00248       assert(it->start >= End &&
00249              "Cannot overlap two LiveRanges with differing ValID's");
00250     }
00251 
00252   // Otherwise, this is just a new range that doesn't interact with anything.
00253   // Insert it.
00254   return ranges.insert(it, LR);
00255 }
00256 
00257 
00258 /// removeRange - Remove the specified range from this interval.  Note that
00259 /// the range must already be in this interval in its entirety.
00260 void LiveInterval::removeRange(unsigned Start, unsigned End) {
00261   // Find the LiveRange containing this span.
00262   Ranges::iterator I = std::upper_bound(ranges.begin(), ranges.end(), Start);
00263   assert(I != ranges.begin() && "Range is not in interval!");
00264   --I;
00265   assert(I->contains(Start) && I->contains(End-1) &&
00266          "Range is not entirely in interval!");
00267 
00268   // If the span we are removing is at the start of the LiveRange, adjust it.
00269   if (I->start == Start) {
00270     if (I->end == End)
00271       ranges.erase(I);  // Removed the whole LiveRange.
00272     else
00273       I->start = End;
00274     return;
00275   }
00276 
00277   // Otherwise if the span we are removing is at the end of the LiveRange,
00278   // adjust the other way.
00279   if (I->end == End) {
00280     I->end = Start;
00281     return;
00282   }
00283 
00284   // Otherwise, we are splitting the LiveRange into two pieces.
00285   unsigned OldEnd = I->end;
00286   I->end = Start;   // Trim the old interval.
00287 
00288   // Insert the new one.
00289   ranges.insert(next(I), LiveRange(End, OldEnd, I->ValId));
00290 }
00291 
00292 /// getLiveRangeContaining - Return the live range that contains the
00293 /// specified index, or null if there is none.
00294 const LiveRange *LiveInterval::getLiveRangeContaining(unsigned Idx) const {
00295   Ranges::const_iterator It = std::upper_bound(ranges.begin(),ranges.end(),Idx);
00296   if (It != ranges.begin()) {
00297     const LiveRange &LR = *prior(It);
00298     if (LR.contains(Idx))
00299       return &LR;
00300   }
00301 
00302   return 0;
00303 }
00304 
00305 
00306 
00307 /// join - Join two live intervals (this, and other) together.  This operation
00308 /// is the result of a copy instruction in the source program, that occurs at
00309 /// index 'CopyIdx' that copies from 'Other' to 'this'.
00310 void LiveInterval::join(LiveInterval &Other, unsigned CopyIdx) {
00311   const LiveRange *SourceLR = Other.getLiveRangeContaining(CopyIdx-1);
00312   const LiveRange *DestLR = getLiveRangeContaining(CopyIdx);
00313   assert(SourceLR && DestLR && "Not joining due to a copy?");
00314   unsigned MergedSrcValIdx = SourceLR->ValId;
00315   unsigned MergedDstValIdx = DestLR->ValId;
00316 
00317   // Try to do the least amount of work possible.  In particular, if there are
00318   // more liverange chunks in the other set than there are in the 'this' set,
00319   // swap sets to merge the fewest chunks in possible.
00320   if (Other.ranges.size() > ranges.size()) {
00321     std::swap(MergedSrcValIdx, MergedDstValIdx);
00322     std::swap(ranges, Other.ranges);
00323     std::swap(NumValues, Other.NumValues);
00324   }
00325 
00326   // Join the ranges of other into the ranges of this interval.
00327   Ranges::iterator InsertPos = ranges.begin();
00328   std::map<unsigned, unsigned> Dst2SrcIdxMap;
00329   for (Ranges::iterator I = Other.ranges.begin(),
00330          E = Other.ranges.end(); I != E; ++I) {
00331     // Map the ValId in the other live range to the current live range.
00332     if (I->ValId == MergedSrcValIdx)
00333       I->ValId = MergedDstValIdx;
00334     else {
00335       unsigned &NV = Dst2SrcIdxMap[I->ValId];
00336       if (NV == 0) NV = getNextValue();
00337       I->ValId = NV;
00338     }
00339 
00340     InsertPos = addRangeFrom(*I, InsertPos);
00341   }
00342 
00343   weight += Other.weight;
00344 }
00345 
00346 std::ostream& llvm::operator<<(std::ostream& os, const LiveRange &LR) {
00347   return os << '[' << LR.start << ',' << LR.end << ':' << LR.ValId << ")";
00348 }
00349 
00350 void LiveRange::dump() const {
00351   std::cerr << *this << "\n";
00352 }
00353 
00354 
00355 std::ostream& llvm::operator<<(std::ostream& os, const LiveInterval& li) {
00356   os << "%reg" << li.reg << ',' << li.weight;
00357   if (li.empty())
00358     return os << "EMPTY";
00359 
00360   os << " = ";
00361   for (LiveInterval::Ranges::const_iterator i = li.ranges.begin(),
00362          e = li.ranges.end(); i != e; ++i)
00363     os << *i;
00364   return os;
00365 }
00366 
00367 void LiveInterval::dump() const {
00368   std::cerr << *this << "\n";
00369 }