1 //===-- llvm/CodeGen/LiveInterval.h - Interval representation ---*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements the LiveRange and LiveInterval classes. Given some 11 // numbering of each the machine instructions an interval [i, j) is said to be a 12 // live interval for register v if there is no instruction with number j' >= j 13 // such that v is live at j' and there is no instruction with number i' < i such 14 // that v is live at i'. In this implementation intervals can have holes, 15 // i.e. an interval might look like [1,20), [50,65), [1000,1001). Each 16 // individual range is represented as an instance of LiveRange, and the whole 17 // interval is represented as an instance of LiveInterval. 18 // 19 //===----------------------------------------------------------------------===// 20 21 #ifndef LLVM_CODEGEN_LIVEINTERVAL_H 22 #define LLVM_CODEGEN_LIVEINTERVAL_H 23 24 #include "llvm/ADT/IntEqClasses.h" 25 #include "llvm/Support/Allocator.h" 26 #include "llvm/Support/AlignOf.h" 27 #include "llvm/CodeGen/SlotIndexes.h" 28 #include <cassert> 29 #include <climits> 30 31 namespace llvm { 32 class LiveIntervals; 33 class MachineInstr; 34 class MachineRegisterInfo; 35 class TargetRegisterInfo; 36 class raw_ostream; 37 38 /// VNInfo - Value Number Information. 39 /// This class holds information about a machine level values, including 40 /// definition and use points. 41 /// 42 class VNInfo { 43 private: 44 enum { 45 HAS_PHI_KILL = 1, 46 IS_PHI_DEF = 1 << 1, 47 IS_UNUSED = 1 << 2 48 }; 49 50 unsigned char flags; 51 52 public: 53 typedef BumpPtrAllocator Allocator; 54 55 /// The ID number of this value. 56 unsigned id; 57 58 /// The index of the defining instruction. 59 SlotIndex def; 60 61 /// VNInfo constructor. 62 VNInfo(unsigned i, SlotIndex d) 63 : flags(0), id(i), def(d) 64 { } 65 66 /// VNInfo construtor, copies values from orig, except for the value number. 67 VNInfo(unsigned i, const VNInfo &orig) 68 : flags(orig.flags), id(i), def(orig.def) 69 { } 70 71 /// Copy from the parameter into this VNInfo. 72 void copyFrom(VNInfo &src) { 73 flags = src.flags; 74 def = src.def; 75 } 76 77 /// Used for copying value number info. 78 unsigned getFlags() const { return flags; } 79 void setFlags(unsigned flags) { this->flags = flags; } 80 81 /// Merge flags from another VNInfo 82 void mergeFlags(const VNInfo *VNI) { 83 flags = (flags | VNI->flags) & ~IS_UNUSED; 84 } 85 86 /// Returns true if one or more kills are PHI nodes. 87 /// Obsolete, do not use! 88 bool hasPHIKill() const { return flags & HAS_PHI_KILL; } 89 /// Set the PHI kill flag on this value. 90 void setHasPHIKill(bool hasKill) { 91 if (hasKill) 92 flags |= HAS_PHI_KILL; 93 else 94 flags &= ~HAS_PHI_KILL; 95 } 96 97 /// Returns true if this value is defined by a PHI instruction (or was, 98 /// PHI instrucions may have been eliminated). 99 bool isPHIDef() const { return flags & IS_PHI_DEF; } 100 /// Set the "phi def" flag on this value. 101 void setIsPHIDef(bool phiDef) { 102 if (phiDef) 103 flags |= IS_PHI_DEF; 104 else 105 flags &= ~IS_PHI_DEF; 106 } 107 108 /// Returns true if this value is unused. 109 bool isUnused() const { return flags & IS_UNUSED; } 110 /// Set the "is unused" flag on this value. 111 void setIsUnused(bool unused) { 112 if (unused) 113 flags |= IS_UNUSED; 114 else 115 flags &= ~IS_UNUSED; 116 } 117 }; 118 119 /// LiveRange structure - This represents a simple register range in the 120 /// program, with an inclusive start point and an exclusive end point. 121 /// These ranges are rendered as [start,end). 122 struct LiveRange { 123 SlotIndex start; // Start point of the interval (inclusive) 124 SlotIndex end; // End point of the interval (exclusive) 125 VNInfo *valno; // identifier for the value contained in this interval. 126 127 LiveRange(SlotIndex S, SlotIndex E, VNInfo *V) 128 : start(S), end(E), valno(V) { 129 130 assert(S < E && "Cannot create empty or backwards range"); 131 } 132 133 /// contains - Return true if the index is covered by this range. 134 /// 135 bool contains(SlotIndex I) const { 136 return start <= I && I < end; 137 } 138 139 /// containsRange - Return true if the given range, [S, E), is covered by 140 /// this range. 141 bool containsRange(SlotIndex S, SlotIndex E) const { 142 assert((S < E) && "Backwards interval?"); 143 return (start <= S && S < end) && (start < E && E <= end); 144 } 145 146 bool operator<(const LiveRange &LR) const { 147 return start < LR.start || (start == LR.start && end < LR.end); 148 } 149 bool operator==(const LiveRange &LR) const { 150 return start == LR.start && end == LR.end; 151 } 152 153 void dump() const; 154 void print(raw_ostream &os) const; 155 156 private: 157 LiveRange(); // DO NOT IMPLEMENT 158 }; 159 160 template <> struct isPodLike<LiveRange> { static const bool value = true; }; 161 162 raw_ostream& operator<<(raw_ostream& os, const LiveRange &LR); 163 164 165 inline bool operator<(SlotIndex V, const LiveRange &LR) { 166 return V < LR.start; 167 } 168 169 inline bool operator<(const LiveRange &LR, SlotIndex V) { 170 return LR.start < V; 171 } 172 173 /// LiveInterval - This class represents some number of live ranges for a 174 /// register or value. This class also contains a bit of register allocator 175 /// state. 176 class LiveInterval { 177 public: 178 179 typedef SmallVector<LiveRange,4> Ranges; 180 typedef SmallVector<VNInfo*,4> VNInfoList; 181 182 const unsigned reg; // the register or stack slot of this interval. 183 float weight; // weight of this interval 184 Ranges ranges; // the ranges in which this register is live 185 VNInfoList valnos; // value#'s 186 187 struct InstrSlots { 188 enum { 189 LOAD = 0, 190 USE = 1, 191 DEF = 2, 192 STORE = 3, 193 NUM = 4 194 }; 195 196 }; 197 198 LiveInterval(unsigned Reg, float Weight) 199 : reg(Reg), weight(Weight) {} 200 201 typedef Ranges::iterator iterator; 202 iterator begin() { return ranges.begin(); } 203 iterator end() { return ranges.end(); } 204 205 typedef Ranges::const_iterator const_iterator; 206 const_iterator begin() const { return ranges.begin(); } 207 const_iterator end() const { return ranges.end(); } 208 209 typedef VNInfoList::iterator vni_iterator; 210 vni_iterator vni_begin() { return valnos.begin(); } 211 vni_iterator vni_end() { return valnos.end(); } 212 213 typedef VNInfoList::const_iterator const_vni_iterator; 214 const_vni_iterator vni_begin() const { return valnos.begin(); } 215 const_vni_iterator vni_end() const { return valnos.end(); } 216 217 /// advanceTo - Advance the specified iterator to point to the LiveRange 218 /// containing the specified position, or end() if the position is past the 219 /// end of the interval. If no LiveRange contains this position, but the 220 /// position is in a hole, this method returns an iterator pointing to the 221 /// LiveRange immediately after the hole. 222 iterator advanceTo(iterator I, SlotIndex Pos) { 223 assert(I != end()); 224 if (Pos >= endIndex()) 225 return end(); 226 while (I->end <= Pos) ++I; 227 return I; 228 } 229 230 /// find - Return an iterator pointing to the first range that ends after 231 /// Pos, or end(). This is the same as advanceTo(begin(), Pos), but faster 232 /// when searching large intervals. 233 /// 234 /// If Pos is contained in a LiveRange, that range is returned. 235 /// If Pos is in a hole, the following LiveRange is returned. 236 /// If Pos is beyond endIndex, end() is returned. 237 iterator find(SlotIndex Pos); 238 239 const_iterator find(SlotIndex Pos) const { 240 return const_cast<LiveInterval*>(this)->find(Pos); 241 } 242 243 void clear() { 244 valnos.clear(); 245 ranges.clear(); 246 } 247 248 bool hasAtLeastOneValue() const { return !valnos.empty(); } 249 250 bool containsOneValue() const { return valnos.size() == 1; } 251 252 unsigned getNumValNums() const { return (unsigned)valnos.size(); } 253 254 /// getValNumInfo - Returns pointer to the specified val#. 255 /// 256 inline VNInfo *getValNumInfo(unsigned ValNo) { 257 return valnos[ValNo]; 258 } 259 inline const VNInfo *getValNumInfo(unsigned ValNo) const { 260 return valnos[ValNo]; 261 } 262 263 /// containsValue - Returns true if VNI belongs to this interval. 264 bool containsValue(const VNInfo *VNI) const { 265 return VNI && VNI->id < getNumValNums() && VNI == getValNumInfo(VNI->id); 266 } 267 268 /// getNextValue - Create a new value number and return it. MIIdx specifies 269 /// the instruction that defines the value number. 270 VNInfo *getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator) { 271 VNInfo *VNI = 272 new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), def); 273 valnos.push_back(VNI); 274 return VNI; 275 } 276 277 /// Create a copy of the given value. The new value will be identical except 278 /// for the Value number. 279 VNInfo *createValueCopy(const VNInfo *orig, 280 VNInfo::Allocator &VNInfoAllocator) { 281 VNInfo *VNI = 282 new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), *orig); 283 valnos.push_back(VNI); 284 return VNI; 285 } 286 287 /// RenumberValues - Renumber all values in order of appearance and remove 288 /// unused values. 289 void RenumberValues(LiveIntervals &lis); 290 291 /// isOnlyLROfValNo - Return true if the specified live range is the only 292 /// one defined by the its val#. 293 bool isOnlyLROfValNo(const LiveRange *LR) { 294 for (const_iterator I = begin(), E = end(); I != E; ++I) { 295 const LiveRange *Tmp = I; 296 if (Tmp != LR && Tmp->valno == LR->valno) 297 return false; 298 } 299 return true; 300 } 301 302 /// MergeValueNumberInto - This method is called when two value nubmers 303 /// are found to be equivalent. This eliminates V1, replacing all 304 /// LiveRanges with the V1 value number with the V2 value number. This can 305 /// cause merging of V1/V2 values numbers and compaction of the value space. 306 VNInfo* MergeValueNumberInto(VNInfo *V1, VNInfo *V2); 307 308 /// MergeValueInAsValue - Merge all of the live ranges of a specific val# 309 /// in RHS into this live interval as the specified value number. 310 /// The LiveRanges in RHS are allowed to overlap with LiveRanges in the 311 /// current interval, it will replace the value numbers of the overlaped 312 /// live ranges with the specified value number. 313 void MergeRangesInAsValue(const LiveInterval &RHS, VNInfo *LHSValNo); 314 315 /// MergeValueInAsValue - Merge all of the live ranges of a specific val# 316 /// in RHS into this live interval as the specified value number. 317 /// The LiveRanges in RHS are allowed to overlap with LiveRanges in the 318 /// current interval, but only if the overlapping LiveRanges have the 319 /// specified value number. 320 void MergeValueInAsValue(const LiveInterval &RHS, 321 const VNInfo *RHSValNo, VNInfo *LHSValNo); 322 323 /// Copy - Copy the specified live interval. This copies all the fields 324 /// except for the register of the interval. 325 void Copy(const LiveInterval &RHS, MachineRegisterInfo *MRI, 326 VNInfo::Allocator &VNInfoAllocator); 327 328 bool empty() const { return ranges.empty(); } 329 330 /// beginIndex - Return the lowest numbered slot covered by interval. 331 SlotIndex beginIndex() const { 332 assert(!empty() && "Call to beginIndex() on empty interval."); 333 return ranges.front().start; 334 } 335 336 /// endNumber - return the maximum point of the interval of the whole, 337 /// exclusive. 338 SlotIndex endIndex() const { 339 assert(!empty() && "Call to endIndex() on empty interval."); 340 return ranges.back().end; 341 } 342 343 bool expiredAt(SlotIndex index) const { 344 return index >= endIndex(); 345 } 346 347 bool liveAt(SlotIndex index) const { 348 const_iterator r = find(index); 349 return r != end() && r->start <= index; 350 } 351 352 /// killedAt - Return true if a live range ends at index. Note that the kill 353 /// point is not contained in the half-open live range. It is usually the 354 /// getDefIndex() slot following its last use. 355 bool killedAt(SlotIndex index) const { 356 const_iterator r = find(index.getRegSlot(true)); 357 return r != end() && r->end == index; 358 } 359 360 /// killedInRange - Return true if the interval has kills in [Start,End). 361 /// Note that the kill point is considered the end of a live range, so it is 362 /// not contained in the live range. If a live range ends at End, it won't 363 /// be counted as a kill by this method. 364 bool killedInRange(SlotIndex Start, SlotIndex End) const; 365 366 /// getLiveRangeContaining - Return the live range that contains the 367 /// specified index, or null if there is none. 368 const LiveRange *getLiveRangeContaining(SlotIndex Idx) const { 369 const_iterator I = FindLiveRangeContaining(Idx); 370 return I == end() ? 0 : &*I; 371 } 372 373 /// getLiveRangeContaining - Return the live range that contains the 374 /// specified index, or null if there is none. 375 LiveRange *getLiveRangeContaining(SlotIndex Idx) { 376 iterator I = FindLiveRangeContaining(Idx); 377 return I == end() ? 0 : &*I; 378 } 379 380 const LiveRange *getLiveRangeBefore(SlotIndex Idx) const { 381 return getLiveRangeContaining(Idx.getPrevSlot()); 382 } 383 384 LiveRange *getLiveRangeBefore(SlotIndex Idx) { 385 return getLiveRangeContaining(Idx.getPrevSlot()); 386 } 387 388 /// getVNInfoAt - Return the VNInfo that is live at Idx, or NULL. 389 VNInfo *getVNInfoAt(SlotIndex Idx) const { 390 const_iterator I = FindLiveRangeContaining(Idx); 391 return I == end() ? 0 : I->valno; 392 } 393 394 /// getVNInfoBefore - Return the VNInfo that is live up to but not 395 /// necessarilly including Idx, or NULL. Use this to find the reaching def 396 /// used by an instruction at this SlotIndex position. 397 VNInfo *getVNInfoBefore(SlotIndex Idx) const { 398 const_iterator I = FindLiveRangeContaining(Idx.getPrevSlot()); 399 return I == end() ? 0 : I->valno; 400 } 401 402 /// FindLiveRangeContaining - Return an iterator to the live range that 403 /// contains the specified index, or end() if there is none. 404 iterator FindLiveRangeContaining(SlotIndex Idx) { 405 iterator I = find(Idx); 406 return I != end() && I->start <= Idx ? I : end(); 407 } 408 409 const_iterator FindLiveRangeContaining(SlotIndex Idx) const { 410 const_iterator I = find(Idx); 411 return I != end() && I->start <= Idx ? I : end(); 412 } 413 414 /// findDefinedVNInfo - Find the by the specified 415 /// index (register interval) or defined 416 VNInfo *findDefinedVNInfoForRegInt(SlotIndex Idx) const; 417 418 419 /// overlaps - Return true if the intersection of the two live intervals is 420 /// not empty. 421 bool overlaps(const LiveInterval& other) const { 422 if (other.empty()) 423 return false; 424 return overlapsFrom(other, other.begin()); 425 } 426 427 /// overlaps - Return true if the live interval overlaps a range specified 428 /// by [Start, End). 429 bool overlaps(SlotIndex Start, SlotIndex End) const; 430 431 /// overlapsFrom - Return true if the intersection of the two live intervals 432 /// is not empty. The specified iterator is a hint that we can begin 433 /// scanning the Other interval starting at I. 434 bool overlapsFrom(const LiveInterval& other, const_iterator I) const; 435 436 /// addRange - Add the specified LiveRange to this interval, merging 437 /// intervals as appropriate. This returns an iterator to the inserted live 438 /// range (which may have grown since it was inserted. 439 void addRange(LiveRange LR) { 440 addRangeFrom(LR, ranges.begin()); 441 } 442 443 /// extendInBlock - If this interval is live before Kill in the basic block 444 /// that starts at StartIdx, extend it to be live up to Kill, and return 445 /// the value. If there is no live range before Kill, return NULL. 446 VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Kill); 447 448 /// join - Join two live intervals (this, and other) together. This applies 449 /// mappings to the value numbers in the LHS/RHS intervals as specified. If 450 /// the intervals are not joinable, this aborts. 451 void join(LiveInterval &Other, 452 const int *ValNoAssignments, 453 const int *RHSValNoAssignments, 454 SmallVector<VNInfo*, 16> &NewVNInfo, 455 MachineRegisterInfo *MRI); 456 457 /// isInOneLiveRange - Return true if the range specified is entirely in the 458 /// a single LiveRange of the live interval. 459 bool isInOneLiveRange(SlotIndex Start, SlotIndex End) const { 460 const_iterator r = find(Start); 461 return r != end() && r->containsRange(Start, End); 462 } 463 464 /// removeRange - Remove the specified range from this interval. Note that 465 /// the range must be a single LiveRange in its entirety. 466 void removeRange(SlotIndex Start, SlotIndex End, 467 bool RemoveDeadValNo = false); 468 469 void removeRange(LiveRange LR, bool RemoveDeadValNo = false) { 470 removeRange(LR.start, LR.end, RemoveDeadValNo); 471 } 472 473 /// removeValNo - Remove all the ranges defined by the specified value#. 474 /// Also remove the value# from value# list. 475 void removeValNo(VNInfo *ValNo); 476 477 /// getSize - Returns the sum of sizes of all the LiveRange's. 478 /// 479 unsigned getSize() const; 480 481 /// Returns true if the live interval is zero length, i.e. no live ranges 482 /// span instructions. It doesn't pay to spill such an interval. 483 bool isZeroLength(SlotIndexes *Indexes) const { 484 for (const_iterator i = begin(), e = end(); i != e; ++i) 485 if (Indexes->getNextNonNullIndex(i->start).getBaseIndex() < 486 i->end.getBaseIndex()) 487 return false; 488 return true; 489 } 490 491 /// isSpillable - Can this interval be spilled? 492 bool isSpillable() const { 493 return weight != HUGE_VALF; 494 } 495 496 /// markNotSpillable - Mark interval as not spillable 497 void markNotSpillable() { 498 weight = HUGE_VALF; 499 } 500 501 /// ComputeJoinedWeight - Set the weight of a live interval after 502 /// Other has been merged into it. 503 void ComputeJoinedWeight(const LiveInterval &Other); 504 505 bool operator<(const LiveInterval& other) const { 506 const SlotIndex &thisIndex = beginIndex(); 507 const SlotIndex &otherIndex = other.beginIndex(); 508 return (thisIndex < otherIndex || 509 (thisIndex == otherIndex && reg < other.reg)); 510 } 511 512 void print(raw_ostream &OS, const TargetRegisterInfo *TRI = 0) const; 513 void dump() const; 514 515 private: 516 517 Ranges::iterator addRangeFrom(LiveRange LR, Ranges::iterator From); 518 void extendIntervalEndTo(Ranges::iterator I, SlotIndex NewEnd); 519 Ranges::iterator extendIntervalStartTo(Ranges::iterator I, SlotIndex NewStr); 520 void markValNoForDeletion(VNInfo *V); 521 522 LiveInterval& operator=(const LiveInterval& rhs); // DO NOT IMPLEMENT 523 524 }; 525 526 inline raw_ostream &operator<<(raw_ostream &OS, const LiveInterval &LI) { 527 LI.print(OS); 528 return OS; 529 } 530 531 /// ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a 532 /// LiveInterval into equivalence clases of connected components. A 533 /// LiveInterval that has multiple connected components can be broken into 534 /// multiple LiveIntervals. 535 /// 536 /// Given a LiveInterval that may have multiple connected components, run: 537 /// 538 /// unsigned numComps = ConEQ.Classify(LI); 539 /// if (numComps > 1) { 540 /// // allocate numComps-1 new LiveIntervals into LIS[1..] 541 /// ConEQ.Distribute(LIS); 542 /// } 543 544 class ConnectedVNInfoEqClasses { 545 LiveIntervals &LIS; 546 IntEqClasses EqClass; 547 548 // Note that values a and b are connected. 549 void Connect(unsigned a, unsigned b); 550 551 unsigned Renumber(); 552 553 public: 554 explicit ConnectedVNInfoEqClasses(LiveIntervals &lis) : LIS(lis) {} 555 556 /// Classify - Classify the values in LI into connected components. 557 /// Return the number of connected components. 558 unsigned Classify(const LiveInterval *LI); 559 560 /// getEqClass - Classify creates equivalence classes numbered 0..N. Return 561 /// the equivalence class assigned the VNI. 562 unsigned getEqClass(const VNInfo *VNI) const { return EqClass[VNI->id]; } 563 564 /// Distribute - Distribute values in LIV[0] into a separate LiveInterval 565 /// for each connected component. LIV must have a LiveInterval for each 566 /// connected component. The LiveIntervals in Liv[1..] must be empty. 567 /// Instructions using LIV[0] are rewritten. 568 void Distribute(LiveInterval *LIV[], MachineRegisterInfo &MRI); 569 570 }; 571 572 } 573 #endif 574