LiveInterval.h revision b18d779b35909cd5b753871f8bf2ff4f6c17ace1
1fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner//===-- llvm/CodeGen/LiveInterval.h - Interval representation ---*- C++ -*-===// 2fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 3fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// The LLVM Compiler Infrastructure 4fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris 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 122ad8245566a3c92d4559727a877d57ecf5d078c8Dan Gohman// live interval for register v if there is no instruction with number j' >= j 13abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner// 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 21fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner#ifndef LLVM_CODEGEN_LIVEINTERVAL_H 22fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner#define LLVM_CODEGEN_LIVEINTERVAL_H 23fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 24b907e8a2d40dc546f21ff7e122a80b121653851aJakob Stoklund Olesen#include "llvm/ADT/IntEqClasses.h" 25f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng#include "llvm/Support/Allocator.h" 26d23f0d0451a4ffc0c12d7a73559fa35587ce7abbLang Hames#include "llvm/Support/AlignOf.h" 27233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#include "llvm/CodeGen/SlotIndexes.h" 28fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner#include <cassert> 29de551f91d8816632a76a065084caab9fab6aacffDan Gohman#include <climits> 30fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 31fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattnernamespace llvm { 32233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames class LiveIntervals; 332638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng class MachineInstr; 3490f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng class MachineRegisterInfo; 356f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman class TargetRegisterInfo; 361cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar class raw_ostream; 377ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng 38857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// VNInfo - Value Number Information. 39857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// This class holds information about a machine level values, including 40857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// definition and use points. 41857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// 42857c4e01f85601cf2084adb860616256ee47c177Lang Hames class VNInfo { 43857c4e01f85601cf2084adb860616256ee47c177Lang Hames private: 44b7b39987bb1f9acc4cc0efe0f4c2d1ee5e2c9148Chris Lattner enum { 4515a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen HAS_PHI_KILL = 1, 46b18d779b35909cd5b753871f8bf2ff4f6c17ace1Jakob Stoklund Olesen IS_UNUSED = 1 << 1 47b7b39987bb1f9acc4cc0efe0f4c2d1ee5e2c9148Chris Lattner }; 48857c4e01f85601cf2084adb860616256ee47c177Lang Hames 496c4329ec96fa49e42310a8fe57813a5d7b73e621Jakob Stoklund Olesen unsigned char flags; 50857c4e01f85601cf2084adb860616256ee47c177Lang Hames 51857c4e01f85601cf2084adb860616256ee47c177Lang Hames public: 52ce9a20b808ba48adf72e0c0615f903a65e9f9eb8Benjamin Kramer typedef BumpPtrAllocator Allocator; 53ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames 54857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// The ID number of this value. 557ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng unsigned id; 5615a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen 571130d220a33a6171e408d9ec4594242907541e1bAndrew Trick /// The index of the defining instruction. 58233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex def; 5952c1afcaea61440950a11a4ccadac4354420d727Lang Hames 60857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// VNInfo constructor. 613b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen VNInfo(unsigned i, SlotIndex d) 623b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen : flags(0), id(i), def(d) 636c4329ec96fa49e42310a8fe57813a5d7b73e621Jakob Stoklund Olesen { } 64857c4e01f85601cf2084adb860616256ee47c177Lang Hames 65857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// VNInfo construtor, copies values from orig, except for the value number. 66857c4e01f85601cf2084adb860616256ee47c177Lang Hames VNInfo(unsigned i, const VNInfo &orig) 673b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen : flags(orig.flags), id(i), def(orig.def) 6852c1afcaea61440950a11a4ccadac4354420d727Lang Hames { } 6952c1afcaea61440950a11a4ccadac4354420d727Lang Hames 7052c1afcaea61440950a11a4ccadac4354420d727Lang Hames /// Copy from the parameter into this VNInfo. 7152c1afcaea61440950a11a4ccadac4354420d727Lang Hames void copyFrom(VNInfo &src) { 7252c1afcaea61440950a11a4ccadac4354420d727Lang Hames flags = src.flags; 7352c1afcaea61440950a11a4ccadac4354420d727Lang Hames def = src.def; 7452c1afcaea61440950a11a4ccadac4354420d727Lang Hames } 75857c4e01f85601cf2084adb860616256ee47c177Lang Hames 76857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// Used for copying value number info. 77857c4e01f85601cf2084adb860616256ee47c177Lang Hames unsigned getFlags() const { return flags; } 78857c4e01f85601cf2084adb860616256ee47c177Lang Hames void setFlags(unsigned flags) { this->flags = flags; } 79857c4e01f85601cf2084adb860616256ee47c177Lang Hames 80e0a73ec0a982a4213f3de9860545d9bf2814593dJakob Stoklund Olesen /// Merge flags from another VNInfo 81e0a73ec0a982a4213f3de9860545d9bf2814593dJakob Stoklund Olesen void mergeFlags(const VNInfo *VNI) { 82e0a73ec0a982a4213f3de9860545d9bf2814593dJakob Stoklund Olesen flags = (flags | VNI->flags) & ~IS_UNUSED; 83e0a73ec0a982a4213f3de9860545d9bf2814593dJakob Stoklund Olesen } 84e0a73ec0a982a4213f3de9860545d9bf2814593dJakob Stoklund Olesen 85857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// Returns true if one or more kills are PHI nodes. 86df8412c4c1a3a798c5a849ebc3f56904568d40c4Jakob Stoklund Olesen /// Obsolete, do not use! 87857c4e01f85601cf2084adb860616256ee47c177Lang Hames bool hasPHIKill() const { return flags & HAS_PHI_KILL; } 888651125d2885f74546b6e2a556082111d5b75da3Lang Hames /// Set the PHI kill flag on this value. 89857c4e01f85601cf2084adb860616256ee47c177Lang Hames void setHasPHIKill(bool hasKill) { 90857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (hasKill) 91857c4e01f85601cf2084adb860616256ee47c177Lang Hames flags |= HAS_PHI_KILL; 92857c4e01f85601cf2084adb860616256ee47c177Lang Hames else 93857c4e01f85601cf2084adb860616256ee47c177Lang Hames flags &= ~HAS_PHI_KILL; 94857c4e01f85601cf2084adb860616256ee47c177Lang Hames } 95857c4e01f85601cf2084adb860616256ee47c177Lang Hames 96857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// Returns true if this value is defined by a PHI instruction (or was, 97857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// PHI instrucions may have been eliminated). 98b18d779b35909cd5b753871f8bf2ff4f6c17ace1Jakob Stoklund Olesen /// PHI-defs begin at a block boundary, all other defs begin at register or 99b18d779b35909cd5b753871f8bf2ff4f6c17ace1Jakob Stoklund Olesen /// EC slots. 100b18d779b35909cd5b753871f8bf2ff4f6c17ace1Jakob Stoklund Olesen bool isPHIDef() const { return def.isBlock(); } 101857c4e01f85601cf2084adb860616256ee47c177Lang Hames 102857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// Returns true if this value is unused. 103857c4e01f85601cf2084adb860616256ee47c177Lang Hames bool isUnused() const { return flags & IS_UNUSED; } 1048651125d2885f74546b6e2a556082111d5b75da3Lang Hames /// Set the "is unused" flag on this value. 105857c4e01f85601cf2084adb860616256ee47c177Lang Hames void setIsUnused(bool unused) { 106857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (unused) 107857c4e01f85601cf2084adb860616256ee47c177Lang Hames flags |= IS_UNUSED; 108857c4e01f85601cf2084adb860616256ee47c177Lang Hames else 109857c4e01f85601cf2084adb860616256ee47c177Lang Hames flags &= ~IS_UNUSED; 110857c4e01f85601cf2084adb860616256ee47c177Lang Hames } 1118651125d2885f74546b6e2a556082111d5b75da3Lang Hames }; 112ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames 113fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner /// LiveRange structure - This represents a simple register range in the 114fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner /// program, with an inclusive start point and an exclusive end point. 115fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner /// These ranges are rendered as [start,end). 116fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner struct LiveRange { 117233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex start; // Start point of the interval (inclusive) 118233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex end; // End point of the interval (exclusive) 1197ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *valno; // identifier for the value contained in this interval. 120abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 121233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames LiveRange(SlotIndex S, SlotIndex E, VNInfo *V) 1228651125d2885f74546b6e2a556082111d5b75da3Lang Hames : start(S), end(E), valno(V) { 1238651125d2885f74546b6e2a556082111d5b75da3Lang Hames 124fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner assert(S < E && "Cannot create empty or backwards range"); 125fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 126fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 127e6ad392802d8643ec7efad9bb80c0c429edda499Chris Lattner /// contains - Return true if the index is covered by this range. 128e6ad392802d8643ec7efad9bb80c0c429edda499Chris Lattner /// 129233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames bool contains(SlotIndex I) const { 130e6ad392802d8643ec7efad9bb80c0c429edda499Chris Lattner return start <= I && I < end; 131e6ad392802d8643ec7efad9bb80c0c429edda499Chris Lattner } 132e6ad392802d8643ec7efad9bb80c0c429edda499Chris Lattner 1338651125d2885f74546b6e2a556082111d5b75da3Lang Hames /// containsRange - Return true if the given range, [S, E), is covered by 1341b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen /// this range. 135233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames bool containsRange(SlotIndex S, SlotIndex E) const { 1368651125d2885f74546b6e2a556082111d5b75da3Lang Hames assert((S < E) && "Backwards interval?"); 1378651125d2885f74546b6e2a556082111d5b75da3Lang Hames return (start <= S && S < end) && (start < E && E <= end); 1388651125d2885f74546b6e2a556082111d5b75da3Lang Hames } 1398651125d2885f74546b6e2a556082111d5b75da3Lang Hames 140fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner bool operator<(const LiveRange &LR) const { 141fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return start < LR.start || (start == LR.start && end < LR.end); 142fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 143fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner bool operator==(const LiveRange &LR) const { 144fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return start == LR.start && end == LR.end; 145fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 146abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 147abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner void dump() const; 1481cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar void print(raw_ostream &os) const; 149abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 150e6ad392802d8643ec7efad9bb80c0c429edda499Chris Lattner private: 151fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner LiveRange(); // DO NOT IMPLEMENT 152fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner }; 153b5ebf15b2b2ce8989caf1a1114b05d80b0f9bd48Bill Wendling 15431135c06920017efa3998723fd1993fea3d1d6c6Benjamin Kramer template <> struct isPodLike<LiveRange> { static const bool value = true; }; 15531135c06920017efa3998723fd1993fea3d1d6c6Benjamin Kramer 1561cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar raw_ostream& operator<<(raw_ostream& os, const LiveRange &LR); 1574b607748d86b44cc59e5cf3eee194dfd9b0fcd86Jeff Cohen 158fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 159233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames inline bool operator<(SlotIndex V, const LiveRange &LR) { 160ebd7e6c54dce754a88d8f38df4ac2f388f35435eChris Lattner return V < LR.start; 161ebd7e6c54dce754a88d8f38df4ac2f388f35435eChris Lattner } 162ebd7e6c54dce754a88d8f38df4ac2f388f35435eChris Lattner 163233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames inline bool operator<(const LiveRange &LR, SlotIndex V) { 1649471c8a93b117d8ac01c4ef1cb9faa583e03dec0Jeff Cohen return LR.start < V; 1659471c8a93b117d8ac01c4ef1cb9faa583e03dec0Jeff Cohen } 166ebd7e6c54dce754a88d8f38df4ac2f388f35435eChris Lattner 167fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner /// LiveInterval - This class represents some number of live ranges for a 168fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner /// register or value. This class also contains a bit of register allocator 169fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner /// state. 17008759c56010aaffae5c63944230c06acd0033e5bLang Hames class LiveInterval { 17108759c56010aaffae5c63944230c06acd0033e5bLang Hames public: 17208759c56010aaffae5c63944230c06acd0033e5bLang Hames 173969e262656066e76d59b39eb6e8b17ed9f448383Chris Lattner typedef SmallVector<LiveRange,4> Ranges; 1747ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng typedef SmallVector<VNInfo*,4> VNInfoList; 1757ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng 176be97e906e03dd9b22e14f6749157c9d5f9701dd5Jakob Stoklund Olesen const unsigned reg; // the register or stack slot of this interval. 177fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner float weight; // weight of this interval 178fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner Ranges ranges; // the ranges in which this register is live 1797ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfoList valnos; // value#'s 1801b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 181f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames struct InstrSlots { 182f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames enum { 183f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames LOAD = 0, 184f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames USE = 1, 185f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames DEF = 2, 186f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames STORE = 3, 187f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames NUM = 4 188f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames }; 189f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames 190f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames }; 191f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames 192be97e906e03dd9b22e14f6749157c9d5f9701dd5Jakob Stoklund Olesen LiveInterval(unsigned Reg, float Weight) 193be97e906e03dd9b22e14f6749157c9d5f9701dd5Jakob Stoklund Olesen : reg(Reg), weight(Weight) {} 1941a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng 19523b71c1e1e33219327b1c0edf43034dbe4c3ae90Chris Lattner typedef Ranges::iterator iterator; 19623b71c1e1e33219327b1c0edf43034dbe4c3ae90Chris Lattner iterator begin() { return ranges.begin(); } 19723b71c1e1e33219327b1c0edf43034dbe4c3ae90Chris Lattner iterator end() { return ranges.end(); } 19823b71c1e1e33219327b1c0edf43034dbe4c3ae90Chris Lattner 199bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner typedef Ranges::const_iterator const_iterator; 200bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator begin() const { return ranges.begin(); } 201bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator end() const { return ranges.end(); } 202bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner 2031a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng typedef VNInfoList::iterator vni_iterator; 2047ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng vni_iterator vni_begin() { return valnos.begin(); } 2057ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng vni_iterator vni_end() { return valnos.end(); } 2061a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng 2071a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng typedef VNInfoList::const_iterator const_vni_iterator; 2087ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng const_vni_iterator vni_begin() const { return valnos.begin(); } 2097ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng const_vni_iterator vni_end() const { return valnos.end(); } 2107ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng 211743ef6d70e710353c1e2b6a4b23af1262f4a475bChris Lattner /// advanceTo - Advance the specified iterator to point to the LiveRange 212743ef6d70e710353c1e2b6a4b23af1262f4a475bChris Lattner /// containing the specified position, or end() if the position is past the 213743ef6d70e710353c1e2b6a4b23af1262f4a475bChris Lattner /// end of the interval. If no LiveRange contains this position, but the 214f3b11aa6a72e0c31066a60c2e888e7a5eb5f2399Dan Gohman /// position is in a hole, this method returns an iterator pointing to the 2151a3a48776340c96df5df673df1c159391d1a1cb7Chris Lattner /// LiveRange immediately after the hole. 216233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames iterator advanceTo(iterator I, SlotIndex Pos) { 2178d121404370cd57be7e72543127a1afe2faa1b10Jakob Stoklund Olesen assert(I != end()); 2188651125d2885f74546b6e2a556082111d5b75da3Lang Hames if (Pos >= endIndex()) 219743ef6d70e710353c1e2b6a4b23af1262f4a475bChris Lattner return end(); 220743ef6d70e710353c1e2b6a4b23af1262f4a475bChris Lattner while (I->end <= Pos) ++I; 221743ef6d70e710353c1e2b6a4b23af1262f4a475bChris Lattner return I; 222743ef6d70e710353c1e2b6a4b23af1262f4a475bChris Lattner } 2231b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 224f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen /// find - Return an iterator pointing to the first range that ends after 225f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen /// Pos, or end(). This is the same as advanceTo(begin(), Pos), but faster 226f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen /// when searching large intervals. 227f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen /// 228f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen /// If Pos is contained in a LiveRange, that range is returned. 229f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen /// If Pos is in a hole, the following LiveRange is returned. 230f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen /// If Pos is beyond endIndex, end() is returned. 231f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen iterator find(SlotIndex Pos); 232f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen 233f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen const_iterator find(SlotIndex Pos) const { 234f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen return const_cast<LiveInterval*>(this)->find(Pos); 235f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen } 236f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen 237169d4080277c71548de52b54c8a79f99694351c6Owen Anderson void clear() { 23801cb1b665da03e2b74c0724f71751e912ec8c2beTorok Edwin valnos.clear(); 239169d4080277c71548de52b54c8a79f99694351c6Owen Anderson ranges.clear(); 240169d4080277c71548de52b54c8a79f99694351c6Owen Anderson } 241743ef6d70e710353c1e2b6a4b23af1262f4a475bChris Lattner 24254898938673d2a13ce31626ec34b2d4d314b2c81Evan Cheng bool hasAtLeastOneValue() const { return !valnos.empty(); } 24354898938673d2a13ce31626ec34b2d4d314b2c81Evan Cheng 244d4e4937b79a7da789379a09117cc74f20cd60623Evan Cheng bool containsOneValue() const { return valnos.size() == 1; } 245abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 24634cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng unsigned getNumValNums() const { return (unsigned)valnos.size(); } 2471b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 248f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng /// getValNumInfo - Returns pointer to the specified val#. 2491a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng /// 250f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng inline VNInfo *getValNumInfo(unsigned ValNo) { 251f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng return valnos[ValNo]; 2521a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng } 253f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng inline const VNInfo *getValNumInfo(unsigned ValNo) const { 254f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng return valnos[ValNo]; 2551a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng } 2561a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng 2576ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen /// containsValue - Returns true if VNI belongs to this interval. 2586ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen bool containsValue(const VNInfo *VNI) const { 2596ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen return VNI && VNI->id < getNumValNums() && VNI == getValNumInfo(VNI->id); 2606ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen } 2616ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen 262be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner /// getNextValue - Create a new value number and return it. MIIdx specifies 263be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner /// the instruction that defines the value number. 2643b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen VNInfo *getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator) { 265ce9a20b808ba48adf72e0c0615f903a65e9f9eb8Benjamin Kramer VNInfo *VNI = 2663b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), def); 267857c4e01f85601cf2084adb860616256ee47c177Lang Hames valnos.push_back(VNI); 268857c4e01f85601cf2084adb860616256ee47c177Lang Hames return VNI; 269857c4e01f85601cf2084adb860616256ee47c177Lang Hames } 270857c4e01f85601cf2084adb860616256ee47c177Lang Hames 2714e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen /// createDeadDef - Make sure the interval has a value defined at Def. 2724e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen /// If one already exists, return it. Otherwise allocate a new value and 2734e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen /// add liveness for a dead def. 2744e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen VNInfo *createDeadDef(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator); 2754e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen 276857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// Create a copy of the given value. The new value will be identical except 277857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// for the Value number. 278c02497f5bae87e71fd5617db5751cb0b3a14bbedChris Lattner VNInfo *createValueCopy(const VNInfo *orig, 279991de14dd62dcbab4b31357ae22dc5b053ba50a0Benjamin Kramer VNInfo::Allocator &VNInfoAllocator) { 280ce9a20b808ba48adf72e0c0615f903a65e9f9eb8Benjamin Kramer VNInfo *VNI = 281ce9a20b808ba48adf72e0c0615f903a65e9f9eb8Benjamin Kramer new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), *orig); 2827ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng valnos.push_back(VNI); 2837ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng return VNI; 2848df786012dc6b875f31ba4152e09c6e0098082eeEvan Cheng } 2854f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 28623436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen /// RenumberValues - Renumber all values in order of appearance and remove 28723436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen /// unused values. 288fff2c4726baa0d6c9cb184c815677e33c0357c93Jakob Stoklund Olesen void RenumberValues(LiveIntervals &lis); 28923436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen 290f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner /// MergeValueNumberInto - This method is called when two value nubmers 291f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner /// are found to be equivalent. This eliminates V1, replacing all 292f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner /// LiveRanges with the V1 value number with the V2 value number. This can 293f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner /// cause merging of V1/V2 values numbers and compaction of the value space. 2945b93f6fa82e33b17d618b3e24da513f547861481Owen Anderson VNInfo* MergeValueNumberInto(VNInfo *V1, VNInfo *V2); 295be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 29628e9a5fe94b96570c3939c61fab18204abdd6b97Evan Cheng /// MergeValueInAsValue - Merge all of the live ranges of a specific val# 29728e9a5fe94b96570c3939c61fab18204abdd6b97Evan Cheng /// in RHS into this live interval as the specified value number. 29828e9a5fe94b96570c3939c61fab18204abdd6b97Evan Cheng /// The LiveRanges in RHS are allowed to overlap with LiveRanges in the 29928e9a5fe94b96570c3939c61fab18204abdd6b97Evan Cheng /// current interval, it will replace the value numbers of the overlaped 30028e9a5fe94b96570c3939c61fab18204abdd6b97Evan Cheng /// live ranges with the specified value number. 3017ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng void MergeRangesInAsValue(const LiveInterval &RHS, VNInfo *LHSValNo); 30232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng 30332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng /// MergeValueInAsValue - Merge all of the live ranges of a specific val# 30432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng /// in RHS into this live interval as the specified value number. 30532dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng /// The LiveRanges in RHS are allowed to overlap with LiveRanges in the 30632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng /// current interval, but only if the overlapping LiveRanges have the 30732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng /// specified value number. 30832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng void MergeValueInAsValue(const LiveInterval &RHS, 30934729256e8058d4106706e9feb2dfad7893502d1Evan Cheng const VNInfo *RHSValNo, VNInfo *LHSValNo); 31032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng 31132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng /// Copy - Copy the specified live interval. This copies all the fields 31232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng /// except for the register of the interval. 31390f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng void Copy(const LiveInterval &RHS, MachineRegisterInfo *MRI, 314991de14dd62dcbab4b31357ae22dc5b053ba50a0Benjamin Kramer VNInfo::Allocator &VNInfoAllocator); 3151b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 316fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner bool empty() const { return ranges.empty(); } 317fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 3188651125d2885f74546b6e2a556082111d5b75da3Lang Hames /// beginIndex - Return the lowest numbered slot covered by interval. 319233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex beginIndex() const { 320233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames assert(!empty() && "Call to beginIndex() on empty interval."); 321fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return ranges.front().start; 322fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 323fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 32423b71c1e1e33219327b1c0edf43034dbe4c3ae90Chris Lattner /// endNumber - return the maximum point of the interval of the whole, 325fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner /// exclusive. 326233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex endIndex() const { 327233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames assert(!empty() && "Call to endIndex() on empty interval."); 328fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return ranges.back().end; 329fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 330fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 331233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames bool expiredAt(SlotIndex index) const { 3328651125d2885f74546b6e2a556082111d5b75da3Lang Hames return index >= endIndex(); 333fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 334fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 335f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen bool liveAt(SlotIndex index) const { 336f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen const_iterator r = find(index); 337f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen return r != end() && r->start <= index; 338f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen } 339fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 34015a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen /// killedAt - Return true if a live range ends at index. Note that the kill 34115a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen /// point is not contained in the half-open live range. It is usually the 34215a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen /// getDefIndex() slot following its last use. 343f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen bool killedAt(SlotIndex index) const { 3442debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen const_iterator r = find(index.getRegSlot(true)); 345f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen return r != end() && r->end == index; 346f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen } 34715a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen 34815a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen /// killedInRange - Return true if the interval has kills in [Start,End). 34915a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen /// Note that the kill point is considered the end of a live range, so it is 35015a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen /// not contained in the live range. If a live range ends at End, it won't 35115a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen /// be counted as a kill by this method. 35215a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen bool killedInRange(SlotIndex Start, SlotIndex End) const; 35315a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen 354abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner /// getLiveRangeContaining - Return the live range that contains the 355abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner /// specified index, or null if there is none. 356233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames const LiveRange *getLiveRangeContaining(SlotIndex Idx) const { 357f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner const_iterator I = FindLiveRangeContaining(Idx); 358f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner return I == end() ? 0 : &*I; 359f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 360abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 361ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames /// getLiveRangeContaining - Return the live range that contains the 362ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames /// specified index, or null if there is none. 363233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames LiveRange *getLiveRangeContaining(SlotIndex Idx) { 364ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames iterator I = FindLiveRangeContaining(Idx); 365ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames return I == end() ? 0 : &*I; 366ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames } 367ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames 3688de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen /// getVNInfoAt - Return the VNInfo that is live at Idx, or NULL. 3698de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen VNInfo *getVNInfoAt(SlotIndex Idx) const { 3708de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen const_iterator I = FindLiveRangeContaining(Idx); 3718de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen return I == end() ? 0 : I->valno; 3728de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen } 3738de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen 374b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick /// getVNInfoBefore - Return the VNInfo that is live up to but not 375b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick /// necessarilly including Idx, or NULL. Use this to find the reaching def 376b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick /// used by an instruction at this SlotIndex position. 377b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick VNInfo *getVNInfoBefore(SlotIndex Idx) const { 378a1dd30553da772a1702924bf1651f63fa5df7894Jakob Stoklund Olesen const_iterator I = FindLiveRangeContaining(Idx.getPrevSlot()); 379b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick return I == end() ? 0 : I->valno; 380b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick } 381b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick 382f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner /// FindLiveRangeContaining - Return an iterator to the live range that 383f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner /// contains the specified index, or end() if there is none. 384f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen iterator FindLiveRangeContaining(SlotIndex Idx) { 385f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen iterator I = find(Idx); 386f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen return I != end() && I->start <= Idx ? I : end(); 387f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen } 388abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 389f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen const_iterator FindLiveRangeContaining(SlotIndex Idx) const { 390f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen const_iterator I = find(Idx); 391f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen return I != end() && I->start <= Idx ? I : end(); 392f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen } 3938651125d2885f74546b6e2a556082111d5b75da3Lang Hames 394bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner /// overlaps - Return true if the intersection of the two live intervals is 395bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner /// not empty. 396bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner bool overlaps(const LiveInterval& other) const { 397624e0b2be6a8db6187206090ee5bc8f24cf55cb7Lang Hames if (other.empty()) 398624e0b2be6a8db6187206090ee5bc8f24cf55cb7Lang Hames return false; 399bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner return overlapsFrom(other, other.begin()); 400bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner } 401bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner 402cccdb2b602cf421d8890130308945163620ebc68Evan Cheng /// overlaps - Return true if the live interval overlaps a range specified 403cccdb2b602cf421d8890130308945163620ebc68Evan Cheng /// by [Start, End). 404233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames bool overlaps(SlotIndex Start, SlotIndex End) const; 405cccdb2b602cf421d8890130308945163620ebc68Evan Cheng 406bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner /// overlapsFrom - Return true if the intersection of the two live intervals 407bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner /// is not empty. The specified iterator is a hint that we can begin 408bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner /// scanning the Other interval starting at I. 409bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner bool overlapsFrom(const LiveInterval& other, const_iterator I) const; 410fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 411b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner /// addRange - Add the specified LiveRange to this interval, merging 412b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner /// intervals as appropriate. This returns an iterator to the inserted live 413b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner /// range (which may have grown since it was inserted. 414b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner void addRange(LiveRange LR) { 415b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner addRangeFrom(LR, ranges.begin()); 416b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } 417fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 418ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen /// extendInBlock - If this interval is live before Kill in the basic block 419ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen /// that starts at StartIdx, extend it to be live up to Kill, and return 420ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen /// the value. If there is no live range before Kill, return NULL. 421ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Kill); 4229763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen 4236d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner /// join - Join two live intervals (this, and other) together. This applies 4246d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner /// mappings to the value numbers in the LHS/RHS intervals as specified. If 4256d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner /// the intervals are not joinable, this aborts. 426233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames void join(LiveInterval &Other, 427233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames const int *ValNoAssignments, 428af992f782fb2cac8d00b352c3dd73f6e782b5758David Greene const int *RHSValNoAssignments, 42990f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng SmallVector<VNInfo*, 16> &NewVNInfo, 43090f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng MachineRegisterInfo *MRI); 431abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 4325a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng /// isInOneLiveRange - Return true if the range specified is entirely in the 4335a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng /// a single LiveRange of the live interval. 434f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen bool isInOneLiveRange(SlotIndex Start, SlotIndex End) const { 435f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen const_iterator r = find(Start); 436f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen return r != end() && r->containsRange(Start, End); 437f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen } 4385a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng 439abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner /// removeRange - Remove the specified range from this interval. Note that 44042cc6e33ec0f63560c31f1928c56b4b0465d537cEvan Cheng /// the range must be a single LiveRange in its entirety. 441233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames void removeRange(SlotIndex Start, SlotIndex End, 4428651125d2885f74546b6e2a556082111d5b75da3Lang Hames bool RemoveDeadValNo = false); 443fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 444d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng void removeRange(LiveRange LR, bool RemoveDeadValNo = false) { 445d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng removeRange(LR.start, LR.end, RemoveDeadValNo); 4461bcf7a309eb46c66adc154ad9c8f0562653a8e13Bill Wendling } 4471bcf7a309eb46c66adc154ad9c8f0562653a8e13Bill Wendling 448d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng /// removeValNo - Remove all the ranges defined by the specified value#. 449d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng /// Also remove the value# from value# list. 450d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng void removeValNo(VNInfo *ValNo); 451d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng 452e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng /// getSize - Returns the sum of sizes of all the LiveRange's. 453e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng /// 454e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng unsigned getSize() const; 455e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng 456df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen /// Returns true if the live interval is zero length, i.e. no live ranges 457df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen /// span instructions. It doesn't pay to spill such an interval. 458f5497fb1b474028709f0a6d8556251dc21e34c26Jakob Stoklund Olesen bool isZeroLength(SlotIndexes *Indexes) const { 459df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen for (const_iterator i = begin(), e = end(); i != e; ++i) 460f5497fb1b474028709f0a6d8556251dc21e34c26Jakob Stoklund Olesen if (Indexes->getNextNonNullIndex(i->start).getBaseIndex() < 461f5497fb1b474028709f0a6d8556251dc21e34c26Jakob Stoklund Olesen i->end.getBaseIndex()) 462df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen return false; 463df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen return true; 464df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen } 465df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen 466e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen /// isSpillable - Can this interval be spilled? 467e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen bool isSpillable() const { 468e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen return weight != HUGE_VALF; 469e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen } 470e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen 471e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen /// markNotSpillable - Mark interval as not spillable 472e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen void markNotSpillable() { 473e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen weight = HUGE_VALF; 474e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen } 475e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen 476fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner bool operator<(const LiveInterval& other) const { 477233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames const SlotIndex &thisIndex = beginIndex(); 478233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames const SlotIndex &otherIndex = other.beginIndex(); 479da4ae4be5b2b8fa35ef989e548530833428f36bfBob Wilson return (thisIndex < otherIndex || 480da4ae4be5b2b8fa35ef989e548530833428f36bfBob Wilson (thisIndex == otherIndex && reg < other.reg)); 481fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 482fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 483b77ec7d26405125fa5685370af5f17fcc9edbecdJakob Stoklund Olesen void print(raw_ostream &OS) const; 484abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner void dump() const; 485fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 486261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth /// \brief Walk the interval and assert if any invariants fail to hold. 487261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth /// 488261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth /// Note that this is a no-op when asserts are disabled. 489261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth#ifdef NDEBUG 490261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth void verify() const {} 491261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth#else 492261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth void verify() const; 493261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth#endif 494261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth 4951b8f70a0d3d72ce55c8036b79bcc80b130b5f7b2Lang Hames private: 4961b8f70a0d3d72ce55c8036b79bcc80b130b5f7b2Lang Hames 4971b8f70a0d3d72ce55c8036b79bcc80b130b5f7b2Lang Hames Ranges::iterator addRangeFrom(LiveRange LR, Ranges::iterator From); 498233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames void extendIntervalEndTo(Ranges::iterator I, SlotIndex NewEnd); 499233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames Ranges::iterator extendIntervalStartTo(Ranges::iterator I, SlotIndex NewStr); 5006f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames void markValNoForDeletion(VNInfo *V); 501e585e75612ef5fd32e2bb2c9f635496791a20f8bChandler Carruth void mergeIntervalRanges(const LiveInterval &RHS, 5024e996de58cfad27033165d8feb8f296b8cbe20caChandler Carruth VNInfo *LHSValNo = 0, 503e585e75612ef5fd32e2bb2c9f635496791a20f8bChandler Carruth const VNInfo *RHSValNo = 0); 504233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 5051b8f70a0d3d72ce55c8036b79bcc80b130b5f7b2Lang Hames LiveInterval& operator=(const LiveInterval& rhs); // DO NOT IMPLEMENT 5061b8f70a0d3d72ce55c8036b79bcc80b130b5f7b2Lang Hames 507fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner }; 508fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 5091cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar inline raw_ostream &operator<<(raw_ostream &OS, const LiveInterval &LI) { 5101cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar LI.print(OS); 5111cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar return OS; 5121cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar } 513fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 514c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// LiveRangeQuery - Query information about a live range around a given 515c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// instruction. This class hides the implementation details of live ranges, 516c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// and it should be used as the primary interface for examining live ranges 517c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// around instructions. 518c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// 519c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen class LiveRangeQuery { 520c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen VNInfo *EarlyVal; 521c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen VNInfo *LateVal; 522c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen SlotIndex EndPoint; 523c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen bool Kill; 524c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen 525c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen public: 526c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// Create a LiveRangeQuery for the given live range and instruction index. 527c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// The sub-instruction slot of Idx doesn't matter, only the instruction it 528c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// refers to is considered. 529c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen LiveRangeQuery(const LiveInterval &LI, SlotIndex Idx) 530c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen : EarlyVal(0), LateVal(0), Kill(false) { 531c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen // Find the segment that enters the instruction. 532c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen LiveInterval::const_iterator I = LI.find(Idx.getBaseIndex()); 533c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen LiveInterval::const_iterator E = LI.end(); 534c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen if (I == E) 535c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen return; 536c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen // Is this an instruction live-in segment? 537c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen if (SlotIndex::isEarlierInstr(I->start, Idx)) { 538c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen EarlyVal = I->valno; 539c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen EndPoint = I->end; 540c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen // Move to the potentially live-out segment. 541c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen if (SlotIndex::isSameInstr(Idx, I->end)) { 542c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen Kill = true; 543c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen if (++I == E) 544c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen return; 545c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen } 546c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen } 547c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen // I now points to the segment that may be live-through, or defined by 548c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen // this instr. Ignore segments starting after the current instr. 549c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen if (SlotIndex::isEarlierInstr(Idx, I->start)) 550c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen return; 551c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen LateVal = I->valno; 552c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen EndPoint = I->end; 553c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen } 554c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen 555c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// Return the value that is live-in to the instruction. This is the value 556c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// that will be read by the instruction's use operands. Return NULL if no 557c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// value is live-in. 558c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen VNInfo *valueIn() const { 559c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen return EarlyVal; 560c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen } 561c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen 562c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// Return true if the live-in value is killed by this instruction. This 563c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// means that either the live range ends at the instruction, or it changes 564c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// value. 565c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen bool isKill() const { 566c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen return Kill; 567c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen } 568c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen 569c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// Return true if this instruction has a dead def. 570c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen bool isDeadDef() const { 571c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen return EndPoint.isDead(); 572c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen } 573c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen 574c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// Return the value leaving the instruction, if any. This can be a 575c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// live-through value, or a live def. A dead def returns NULL. 576c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen VNInfo *valueOut() const { 577c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen return isDeadDef() ? 0 : LateVal; 578c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen } 579c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen 580c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// Return the value defined by this instruction, if any. This includes 581c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// dead defs, it is the value created by the instruction's def operands. 582c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen VNInfo *valueDefined() const { 583c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen return EarlyVal == LateVal ? 0 : LateVal; 584c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen } 585c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen 586c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// Return the end point of the last live range segment to interact with 587c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// the instruction, if any. 588c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// 589c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// The end point is an invalid SlotIndex only if the live range doesn't 590c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// intersect the instruction at all. 591c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// 592c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// The end point may be at or past the end of the instruction's basic 593c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// block. That means the value was live out of the block. 594c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen SlotIndex endPoint() const { 595c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen return EndPoint; 596c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen } 597c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen }; 598c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen 5990253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a 6000253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// LiveInterval into equivalence clases of connected components. A 6010253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// LiveInterval that has multiple connected components can be broken into 6020253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// multiple LiveIntervals. 6030253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// 6040253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// Given a LiveInterval that may have multiple connected components, run: 6050253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// 6060253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// unsigned numComps = ConEQ.Classify(LI); 6070253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// if (numComps > 1) { 6080253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// // allocate numComps-1 new LiveIntervals into LIS[1..] 6090253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// ConEQ.Distribute(LIS); 6100253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// } 6110253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 6120253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen class ConnectedVNInfoEqClasses { 6132254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen LiveIntervals &LIS; 6142254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen IntEqClasses EqClass; 6150253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 6160253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // Note that values a and b are connected. 6170253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen void Connect(unsigned a, unsigned b); 6180253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 6190253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen unsigned Renumber(); 6200253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 6210253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen public: 6222254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen explicit ConnectedVNInfoEqClasses(LiveIntervals &lis) : LIS(lis) {} 6230253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 6240253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// Classify - Classify the values in LI into connected components. 6250253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// Return the number of connected components. 6260253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen unsigned Classify(const LiveInterval *LI); 6270253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 628cb367778c0fb3200292df4f3982f54167444d1f6Jakob Stoklund Olesen /// getEqClass - Classify creates equivalence classes numbered 0..N. Return 629cb367778c0fb3200292df4f3982f54167444d1f6Jakob Stoklund Olesen /// the equivalence class assigned the VNI. 6302254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen unsigned getEqClass(const VNInfo *VNI) const { return EqClass[VNI->id]; } 631cb367778c0fb3200292df4f3982f54167444d1f6Jakob Stoklund Olesen 632cb367778c0fb3200292df4f3982f54167444d1f6Jakob Stoklund Olesen /// Distribute - Distribute values in LIV[0] into a separate LiveInterval 633cb367778c0fb3200292df4f3982f54167444d1f6Jakob Stoklund Olesen /// for each connected component. LIV must have a LiveInterval for each 634cb367778c0fb3200292df4f3982f54167444d1f6Jakob Stoklund Olesen /// connected component. The LiveIntervals in Liv[1..] must be empty. 6352254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen /// Instructions using LIV[0] are rewritten. 6362254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen void Distribute(LiveInterval *LIV[], MachineRegisterInfo &MRI); 637cb367778c0fb3200292df4f3982f54167444d1f6Jakob Stoklund Olesen 6380253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen }; 6390253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 6400253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen} 641fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner#endif 642