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 { 3245c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen class CoalescerPair; 33233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames class LiveIntervals; 342638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng class MachineInstr; 3590f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng class MachineRegisterInfo; 366f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman class TargetRegisterInfo; 371cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar class raw_ostream; 387ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng 39857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// VNInfo - Value Number Information. 40857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// This class holds information about a machine level values, including 41857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// definition and use points. 42857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// 43857c4e01f85601cf2084adb860616256ee47c177Lang Hames class VNInfo { 44857c4e01f85601cf2084adb860616256ee47c177Lang Hames public: 45ce9a20b808ba48adf72e0c0615f903a65e9f9eb8Benjamin Kramer typedef BumpPtrAllocator Allocator; 46ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames 47857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// The ID number of this value. 487ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng unsigned id; 4915a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen 501130d220a33a6171e408d9ec4594242907541e1bAndrew Trick /// The index of the defining instruction. 51233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex def; 5252c1afcaea61440950a11a4ccadac4354420d727Lang Hames 53857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// VNInfo constructor. 543b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen VNInfo(unsigned i, SlotIndex d) 55b2beac2b9671f7d9773329d62c2821c8ac449ac5Jakob Stoklund Olesen : id(i), def(d) 566c4329ec96fa49e42310a8fe57813a5d7b73e621Jakob Stoklund Olesen { } 57857c4e01f85601cf2084adb860616256ee47c177Lang Hames 58857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// VNInfo construtor, copies values from orig, except for the value number. 59857c4e01f85601cf2084adb860616256ee47c177Lang Hames VNInfo(unsigned i, const VNInfo &orig) 60b2beac2b9671f7d9773329d62c2821c8ac449ac5Jakob Stoklund Olesen : id(i), def(orig.def) 6152c1afcaea61440950a11a4ccadac4354420d727Lang Hames { } 6252c1afcaea61440950a11a4ccadac4354420d727Lang Hames 6352c1afcaea61440950a11a4ccadac4354420d727Lang Hames /// Copy from the parameter into this VNInfo. 6452c1afcaea61440950a11a4ccadac4354420d727Lang Hames void copyFrom(VNInfo &src) { 6552c1afcaea61440950a11a4ccadac4354420d727Lang Hames def = src.def; 6652c1afcaea61440950a11a4ccadac4354420d727Lang Hames } 67857c4e01f85601cf2084adb860616256ee47c177Lang Hames 68857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// Returns true if this value is defined by a PHI instruction (or was, 69857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// PHI instrucions may have been eliminated). 70b18d779b35909cd5b753871f8bf2ff4f6c17ace1Jakob Stoklund Olesen /// PHI-defs begin at a block boundary, all other defs begin at register or 71b18d779b35909cd5b753871f8bf2ff4f6c17ace1Jakob Stoklund Olesen /// EC slots. 72b18d779b35909cd5b753871f8bf2ff4f6c17ace1Jakob Stoklund Olesen bool isPHIDef() const { return def.isBlock(); } 73857c4e01f85601cf2084adb860616256ee47c177Lang Hames 74857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// Returns true if this value is unused. 75b2beac2b9671f7d9773329d62c2821c8ac449ac5Jakob Stoklund Olesen bool isUnused() const { return !def.isValid(); } 76b2beac2b9671f7d9773329d62c2821c8ac449ac5Jakob Stoklund Olesen 77b2beac2b9671f7d9773329d62c2821c8ac449ac5Jakob Stoklund Olesen /// Mark this value as unused. 78b2beac2b9671f7d9773329d62c2821c8ac449ac5Jakob Stoklund Olesen void markUnused() { def = SlotIndex(); } 798651125d2885f74546b6e2a556082111d5b75da3Lang Hames }; 80ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames 81fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner /// LiveRange structure - This represents a simple register range in the 82fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner /// program, with an inclusive start point and an exclusive end point. 83fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner /// These ranges are rendered as [start,end). 84fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner struct LiveRange { 85233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex start; // Start point of the interval (inclusive) 86233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex end; // End point of the interval (exclusive) 877ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *valno; // identifier for the value contained in this interval. 88abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 89233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames LiveRange(SlotIndex S, SlotIndex E, VNInfo *V) 908651125d2885f74546b6e2a556082111d5b75da3Lang Hames : start(S), end(E), valno(V) { 918651125d2885f74546b6e2a556082111d5b75da3Lang Hames 92fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner assert(S < E && "Cannot create empty or backwards range"); 93fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 94fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 95e6ad392802d8643ec7efad9bb80c0c429edda499Chris Lattner /// contains - Return true if the index is covered by this range. 96e6ad392802d8643ec7efad9bb80c0c429edda499Chris Lattner /// 97233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames bool contains(SlotIndex I) const { 98e6ad392802d8643ec7efad9bb80c0c429edda499Chris Lattner return start <= I && I < end; 99e6ad392802d8643ec7efad9bb80c0c429edda499Chris Lattner } 100e6ad392802d8643ec7efad9bb80c0c429edda499Chris Lattner 1018651125d2885f74546b6e2a556082111d5b75da3Lang Hames /// containsRange - Return true if the given range, [S, E), is covered by 1021b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen /// this range. 103233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames bool containsRange(SlotIndex S, SlotIndex E) const { 1048651125d2885f74546b6e2a556082111d5b75da3Lang Hames assert((S < E) && "Backwards interval?"); 1058651125d2885f74546b6e2a556082111d5b75da3Lang Hames return (start <= S && S < end) && (start < E && E <= end); 1068651125d2885f74546b6e2a556082111d5b75da3Lang Hames } 1078651125d2885f74546b6e2a556082111d5b75da3Lang Hames 108fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner bool operator<(const LiveRange &LR) const { 109fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return start < LR.start || (start == LR.start && end < LR.end); 110fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 111fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner bool operator==(const LiveRange &LR) const { 112fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return start == LR.start && end == LR.end; 113fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 114abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 115abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner void dump() const; 1161cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar void print(raw_ostream &os) const; 117abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 118e6ad392802d8643ec7efad9bb80c0c429edda499Chris Lattner private: 119fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner LiveRange(); // DO NOT IMPLEMENT 120fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner }; 121b5ebf15b2b2ce8989caf1a1114b05d80b0f9bd48Bill Wendling 12231135c06920017efa3998723fd1993fea3d1d6c6Benjamin Kramer template <> struct isPodLike<LiveRange> { static const bool value = true; }; 12331135c06920017efa3998723fd1993fea3d1d6c6Benjamin Kramer 1241cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar raw_ostream& operator<<(raw_ostream& os, const LiveRange &LR); 1254b607748d86b44cc59e5cf3eee194dfd9b0fcd86Jeff Cohen 126fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 127233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames inline bool operator<(SlotIndex V, const LiveRange &LR) { 128ebd7e6c54dce754a88d8f38df4ac2f388f35435eChris Lattner return V < LR.start; 129ebd7e6c54dce754a88d8f38df4ac2f388f35435eChris Lattner } 130ebd7e6c54dce754a88d8f38df4ac2f388f35435eChris Lattner 131233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames inline bool operator<(const LiveRange &LR, SlotIndex V) { 1329471c8a93b117d8ac01c4ef1cb9faa583e03dec0Jeff Cohen return LR.start < V; 1339471c8a93b117d8ac01c4ef1cb9faa583e03dec0Jeff Cohen } 134ebd7e6c54dce754a88d8f38df4ac2f388f35435eChris Lattner 135fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner /// LiveInterval - This class represents some number of live ranges for a 136fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner /// register or value. This class also contains a bit of register allocator 137fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner /// state. 13808759c56010aaffae5c63944230c06acd0033e5bLang Hames class LiveInterval { 13908759c56010aaffae5c63944230c06acd0033e5bLang Hames public: 14008759c56010aaffae5c63944230c06acd0033e5bLang Hames 141969e262656066e76d59b39eb6e8b17ed9f448383Chris Lattner typedef SmallVector<LiveRange,4> Ranges; 1427ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng typedef SmallVector<VNInfo*,4> VNInfoList; 1437ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng 144be97e906e03dd9b22e14f6749157c9d5f9701dd5Jakob Stoklund Olesen const unsigned reg; // the register or stack slot of this interval. 145fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner float weight; // weight of this interval 146fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner Ranges ranges; // the ranges in which this register is live 1477ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfoList valnos; // value#'s 1481b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 149f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames struct InstrSlots { 150f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames enum { 151f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames LOAD = 0, 152f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames USE = 1, 153f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames DEF = 2, 154f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames STORE = 3, 155f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames NUM = 4 156f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames }; 157f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames 158f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames }; 159f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames 160be97e906e03dd9b22e14f6749157c9d5f9701dd5Jakob Stoklund Olesen LiveInterval(unsigned Reg, float Weight) 161be97e906e03dd9b22e14f6749157c9d5f9701dd5Jakob Stoklund Olesen : reg(Reg), weight(Weight) {} 1621a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng 16323b71c1e1e33219327b1c0edf43034dbe4c3ae90Chris Lattner typedef Ranges::iterator iterator; 16423b71c1e1e33219327b1c0edf43034dbe4c3ae90Chris Lattner iterator begin() { return ranges.begin(); } 16523b71c1e1e33219327b1c0edf43034dbe4c3ae90Chris Lattner iterator end() { return ranges.end(); } 16623b71c1e1e33219327b1c0edf43034dbe4c3ae90Chris Lattner 167bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner typedef Ranges::const_iterator const_iterator; 168bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator begin() const { return ranges.begin(); } 169bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner const_iterator end() const { return ranges.end(); } 170bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner 1711a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng typedef VNInfoList::iterator vni_iterator; 1727ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng vni_iterator vni_begin() { return valnos.begin(); } 1737ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng vni_iterator vni_end() { return valnos.end(); } 1741a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng 1751a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng typedef VNInfoList::const_iterator const_vni_iterator; 1767ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng const_vni_iterator vni_begin() const { return valnos.begin(); } 1777ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng const_vni_iterator vni_end() const { return valnos.end(); } 1787ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng 179743ef6d70e710353c1e2b6a4b23af1262f4a475bChris Lattner /// advanceTo - Advance the specified iterator to point to the LiveRange 180743ef6d70e710353c1e2b6a4b23af1262f4a475bChris Lattner /// containing the specified position, or end() if the position is past the 181743ef6d70e710353c1e2b6a4b23af1262f4a475bChris Lattner /// end of the interval. If no LiveRange contains this position, but the 182f3b11aa6a72e0c31066a60c2e888e7a5eb5f2399Dan Gohman /// position is in a hole, this method returns an iterator pointing to the 1831a3a48776340c96df5df673df1c159391d1a1cb7Chris Lattner /// LiveRange immediately after the hole. 184233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames iterator advanceTo(iterator I, SlotIndex Pos) { 1858d121404370cd57be7e72543127a1afe2faa1b10Jakob Stoklund Olesen assert(I != end()); 1868651125d2885f74546b6e2a556082111d5b75da3Lang Hames if (Pos >= endIndex()) 187743ef6d70e710353c1e2b6a4b23af1262f4a475bChris Lattner return end(); 188743ef6d70e710353c1e2b6a4b23af1262f4a475bChris Lattner while (I->end <= Pos) ++I; 189743ef6d70e710353c1e2b6a4b23af1262f4a475bChris Lattner return I; 190743ef6d70e710353c1e2b6a4b23af1262f4a475bChris Lattner } 1911b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 192f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen /// find - Return an iterator pointing to the first range that ends after 193f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen /// Pos, or end(). This is the same as advanceTo(begin(), Pos), but faster 194f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen /// when searching large intervals. 195f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen /// 196f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen /// If Pos is contained in a LiveRange, that range is returned. 197f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen /// If Pos is in a hole, the following LiveRange is returned. 198f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen /// If Pos is beyond endIndex, end() is returned. 199f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen iterator find(SlotIndex Pos); 200f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen 201f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen const_iterator find(SlotIndex Pos) const { 202f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen return const_cast<LiveInterval*>(this)->find(Pos); 203f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen } 204f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen 205169d4080277c71548de52b54c8a79f99694351c6Owen Anderson void clear() { 20601cb1b665da03e2b74c0724f71751e912ec8c2beTorok Edwin valnos.clear(); 207169d4080277c71548de52b54c8a79f99694351c6Owen Anderson ranges.clear(); 208169d4080277c71548de52b54c8a79f99694351c6Owen Anderson } 209743ef6d70e710353c1e2b6a4b23af1262f4a475bChris Lattner 21054898938673d2a13ce31626ec34b2d4d314b2c81Evan Cheng bool hasAtLeastOneValue() const { return !valnos.empty(); } 21154898938673d2a13ce31626ec34b2d4d314b2c81Evan Cheng 212d4e4937b79a7da789379a09117cc74f20cd60623Evan Cheng bool containsOneValue() const { return valnos.size() == 1; } 213abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 21434cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng unsigned getNumValNums() const { return (unsigned)valnos.size(); } 2151b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 216f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng /// getValNumInfo - Returns pointer to the specified val#. 2171a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng /// 218f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng inline VNInfo *getValNumInfo(unsigned ValNo) { 219f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng return valnos[ValNo]; 2201a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng } 221f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng inline const VNInfo *getValNumInfo(unsigned ValNo) const { 222f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng return valnos[ValNo]; 2231a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng } 2241a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng 2256ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen /// containsValue - Returns true if VNI belongs to this interval. 2266ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen bool containsValue(const VNInfo *VNI) const { 2276ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen return VNI && VNI->id < getNumValNums() && VNI == getValNumInfo(VNI->id); 2286ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen } 2296ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen 230be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner /// getNextValue - Create a new value number and return it. MIIdx specifies 231be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner /// the instruction that defines the value number. 2323b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen VNInfo *getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator) { 233ce9a20b808ba48adf72e0c0615f903a65e9f9eb8Benjamin Kramer VNInfo *VNI = 2343b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), def); 235857c4e01f85601cf2084adb860616256ee47c177Lang Hames valnos.push_back(VNI); 236857c4e01f85601cf2084adb860616256ee47c177Lang Hames return VNI; 237857c4e01f85601cf2084adb860616256ee47c177Lang Hames } 238857c4e01f85601cf2084adb860616256ee47c177Lang Hames 2394e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen /// createDeadDef - Make sure the interval has a value defined at Def. 2404e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen /// If one already exists, return it. Otherwise allocate a new value and 2414e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen /// add liveness for a dead def. 2424e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen VNInfo *createDeadDef(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator); 2434e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen 244857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// Create a copy of the given value. The new value will be identical except 245857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// for the Value number. 246c02497f5bae87e71fd5617db5751cb0b3a14bbedChris Lattner VNInfo *createValueCopy(const VNInfo *orig, 247991de14dd62dcbab4b31357ae22dc5b053ba50a0Benjamin Kramer VNInfo::Allocator &VNInfoAllocator) { 248ce9a20b808ba48adf72e0c0615f903a65e9f9eb8Benjamin Kramer VNInfo *VNI = 249ce9a20b808ba48adf72e0c0615f903a65e9f9eb8Benjamin Kramer new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), *orig); 2507ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng valnos.push_back(VNI); 2517ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng return VNI; 2528df786012dc6b875f31ba4152e09c6e0098082eeEvan Cheng } 2534f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 25423436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen /// RenumberValues - Renumber all values in order of appearance and remove 25523436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen /// unused values. 256fff2c4726baa0d6c9cb184c815677e33c0357c93Jakob Stoklund Olesen void RenumberValues(LiveIntervals &lis); 25723436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen 258f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner /// MergeValueNumberInto - This method is called when two value nubmers 259f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner /// are found to be equivalent. This eliminates V1, replacing all 260f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner /// LiveRanges with the V1 value number with the V2 value number. This can 261f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner /// cause merging of V1/V2 values numbers and compaction of the value space. 2625b93f6fa82e33b17d618b3e24da513f547861481Owen Anderson VNInfo* MergeValueNumberInto(VNInfo *V1, VNInfo *V2); 263be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 26428e9a5fe94b96570c3939c61fab18204abdd6b97Evan Cheng /// MergeValueInAsValue - Merge all of the live ranges of a specific val# 26528e9a5fe94b96570c3939c61fab18204abdd6b97Evan Cheng /// in RHS into this live interval as the specified value number. 26628e9a5fe94b96570c3939c61fab18204abdd6b97Evan Cheng /// The LiveRanges in RHS are allowed to overlap with LiveRanges in the 26728e9a5fe94b96570c3939c61fab18204abdd6b97Evan Cheng /// current interval, it will replace the value numbers of the overlaped 26828e9a5fe94b96570c3939c61fab18204abdd6b97Evan Cheng /// live ranges with the specified value number. 2697ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng void MergeRangesInAsValue(const LiveInterval &RHS, VNInfo *LHSValNo); 27032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng 27132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng /// MergeValueInAsValue - Merge all of the live ranges of a specific val# 27232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng /// in RHS into this live interval as the specified value number. 27332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng /// The LiveRanges in RHS are allowed to overlap with LiveRanges in the 27432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng /// current interval, but only if the overlapping LiveRanges have the 27532dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng /// specified value number. 27632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng void MergeValueInAsValue(const LiveInterval &RHS, 27734729256e8058d4106706e9feb2dfad7893502d1Evan Cheng const VNInfo *RHSValNo, VNInfo *LHSValNo); 27832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng 27932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng /// Copy - Copy the specified live interval. This copies all the fields 28032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng /// except for the register of the interval. 28190f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng void Copy(const LiveInterval &RHS, MachineRegisterInfo *MRI, 282991de14dd62dcbab4b31357ae22dc5b053ba50a0Benjamin Kramer VNInfo::Allocator &VNInfoAllocator); 2831b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 284fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner bool empty() const { return ranges.empty(); } 285fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 2868651125d2885f74546b6e2a556082111d5b75da3Lang Hames /// beginIndex - Return the lowest numbered slot covered by interval. 287233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex beginIndex() const { 288233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames assert(!empty() && "Call to beginIndex() on empty interval."); 289fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return ranges.front().start; 290fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 291fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 29223b71c1e1e33219327b1c0edf43034dbe4c3ae90Chris Lattner /// endNumber - return the maximum point of the interval of the whole, 293fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner /// exclusive. 294233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex endIndex() const { 295233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames assert(!empty() && "Call to endIndex() on empty interval."); 296fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner return ranges.back().end; 297fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 298fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 299233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames bool expiredAt(SlotIndex index) const { 3008651125d2885f74546b6e2a556082111d5b75da3Lang Hames return index >= endIndex(); 301fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 302fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 303f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen bool liveAt(SlotIndex index) const { 304f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen const_iterator r = find(index); 305f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen return r != end() && r->start <= index; 306f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen } 307fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 30815a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen /// killedAt - Return true if a live range ends at index. Note that the kill 30915a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen /// point is not contained in the half-open live range. It is usually the 31015a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen /// getDefIndex() slot following its last use. 311f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen bool killedAt(SlotIndex index) const { 3122debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen const_iterator r = find(index.getRegSlot(true)); 313f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen return r != end() && r->end == index; 314f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen } 31515a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen 31615a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen /// killedInRange - Return true if the interval has kills in [Start,End). 31715a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen /// Note that the kill point is considered the end of a live range, so it is 31815a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen /// not contained in the live range. If a live range ends at End, it won't 31915a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen /// be counted as a kill by this method. 32015a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen bool killedInRange(SlotIndex Start, SlotIndex End) const; 32115a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen 322abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner /// getLiveRangeContaining - Return the live range that contains the 323abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner /// specified index, or null if there is none. 324233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames const LiveRange *getLiveRangeContaining(SlotIndex Idx) const { 325f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner const_iterator I = FindLiveRangeContaining(Idx); 326f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner return I == end() ? 0 : &*I; 327f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 328abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 329ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames /// getLiveRangeContaining - Return the live range that contains the 330ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames /// specified index, or null if there is none. 331233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames LiveRange *getLiveRangeContaining(SlotIndex Idx) { 332ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames iterator I = FindLiveRangeContaining(Idx); 333ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames return I == end() ? 0 : &*I; 334ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames } 335ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames 3368de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen /// getVNInfoAt - Return the VNInfo that is live at Idx, or NULL. 3378de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen VNInfo *getVNInfoAt(SlotIndex Idx) const { 3388de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen const_iterator I = FindLiveRangeContaining(Idx); 3398de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen return I == end() ? 0 : I->valno; 3408de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen } 3418de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen 342b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick /// getVNInfoBefore - Return the VNInfo that is live up to but not 343b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick /// necessarilly including Idx, or NULL. Use this to find the reaching def 344b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick /// used by an instruction at this SlotIndex position. 345b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick VNInfo *getVNInfoBefore(SlotIndex Idx) const { 346a1dd30553da772a1702924bf1651f63fa5df7894Jakob Stoklund Olesen const_iterator I = FindLiveRangeContaining(Idx.getPrevSlot()); 347b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick return I == end() ? 0 : I->valno; 348b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick } 349b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick 350f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner /// FindLiveRangeContaining - Return an iterator to the live range that 351f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner /// contains the specified index, or end() if there is none. 352f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen iterator FindLiveRangeContaining(SlotIndex Idx) { 353f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen iterator I = find(Idx); 354f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen return I != end() && I->start <= Idx ? I : end(); 355f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen } 356abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 357f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen const_iterator FindLiveRangeContaining(SlotIndex Idx) const { 358f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen const_iterator I = find(Idx); 359f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen return I != end() && I->start <= Idx ? I : end(); 360f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen } 3618651125d2885f74546b6e2a556082111d5b75da3Lang Hames 362bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner /// overlaps - Return true if the intersection of the two live intervals is 363bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner /// not empty. 364bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner bool overlaps(const LiveInterval& other) const { 365624e0b2be6a8db6187206090ee5bc8f24cf55cb7Lang Hames if (other.empty()) 366624e0b2be6a8db6187206090ee5bc8f24cf55cb7Lang Hames return false; 367bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner return overlapsFrom(other, other.begin()); 368bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner } 369bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner 37045c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen /// overlaps - Return true if the two intervals have overlapping segments 37145c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen /// that are not coalescable according to CP. 37245c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen /// 37345c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen /// Overlapping segments where one interval is defined by a coalescable 37445c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen /// copy are allowed. 37545c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen bool overlaps(const LiveInterval &Other, const CoalescerPair &CP, 37645c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen const SlotIndexes&) const; 37745c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen 378cccdb2b602cf421d8890130308945163620ebc68Evan Cheng /// overlaps - Return true if the live interval overlaps a range specified 379cccdb2b602cf421d8890130308945163620ebc68Evan Cheng /// by [Start, End). 380233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames bool overlaps(SlotIndex Start, SlotIndex End) const; 381cccdb2b602cf421d8890130308945163620ebc68Evan Cheng 382bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner /// overlapsFrom - Return true if the intersection of the two live intervals 383bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner /// is not empty. The specified iterator is a hint that we can begin 384bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner /// scanning the Other interval starting at I. 385bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner bool overlapsFrom(const LiveInterval& other, const_iterator I) const; 386fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 387b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner /// addRange - Add the specified LiveRange to this interval, merging 388b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner /// intervals as appropriate. This returns an iterator to the inserted live 389b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner /// range (which may have grown since it was inserted. 390b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner void addRange(LiveRange LR) { 391b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner addRangeFrom(LR, ranges.begin()); 392b26c215c059d4674bd6a9a8b94da86e497e64844Chris Lattner } 393fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 394ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen /// extendInBlock - If this interval is live before Kill in the basic block 395ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen /// that starts at StartIdx, extend it to be live up to Kill, and return 396ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen /// the value. If there is no live range before Kill, return NULL. 397ee5655dca467d3812145a2f965c31edf4875c93eJakob Stoklund Olesen VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Kill); 3989763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen 3996d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner /// join - Join two live intervals (this, and other) together. This applies 4006d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner /// mappings to the value numbers in the LHS/RHS intervals as specified. If 4016d8fbef015ff836bcb8f64f52c49805e43f8ea9fChris Lattner /// the intervals are not joinable, this aborts. 402233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames void join(LiveInterval &Other, 403233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames const int *ValNoAssignments, 404af992f782fb2cac8d00b352c3dd73f6e782b5758David Greene const int *RHSValNoAssignments, 40590f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng SmallVector<VNInfo*, 16> &NewVNInfo, 40690f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng MachineRegisterInfo *MRI); 407abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 4085a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng /// isInOneLiveRange - Return true if the range specified is entirely in the 4095a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng /// a single LiveRange of the live interval. 410f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen bool isInOneLiveRange(SlotIndex Start, SlotIndex End) const { 411f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen const_iterator r = find(Start); 412f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen return r != end() && r->containsRange(Start, End); 413f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen } 4145a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng 415abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner /// removeRange - Remove the specified range from this interval. Note that 41642cc6e33ec0f63560c31f1928c56b4b0465d537cEvan Cheng /// the range must be a single LiveRange in its entirety. 417233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames void removeRange(SlotIndex Start, SlotIndex End, 4188651125d2885f74546b6e2a556082111d5b75da3Lang Hames bool RemoveDeadValNo = false); 419fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 420d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng void removeRange(LiveRange LR, bool RemoveDeadValNo = false) { 421d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng removeRange(LR.start, LR.end, RemoveDeadValNo); 4221bcf7a309eb46c66adc154ad9c8f0562653a8e13Bill Wendling } 4231bcf7a309eb46c66adc154ad9c8f0562653a8e13Bill Wendling 424d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng /// removeValNo - Remove all the ranges defined by the specified value#. 425d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng /// Also remove the value# from value# list. 426d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng void removeValNo(VNInfo *ValNo); 427d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng 428e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng /// getSize - Returns the sum of sizes of all the LiveRange's. 429e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng /// 430e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng unsigned getSize() const; 431e52eef8e9a10ada9efc1fed115e5b6eefb22b1daEvan Cheng 432df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen /// Returns true if the live interval is zero length, i.e. no live ranges 433df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen /// span instructions. It doesn't pay to spill such an interval. 434f5497fb1b474028709f0a6d8556251dc21e34c26Jakob Stoklund Olesen bool isZeroLength(SlotIndexes *Indexes) const { 435df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen for (const_iterator i = begin(), e = end(); i != e; ++i) 436f5497fb1b474028709f0a6d8556251dc21e34c26Jakob Stoklund Olesen if (Indexes->getNextNonNullIndex(i->start).getBaseIndex() < 437f5497fb1b474028709f0a6d8556251dc21e34c26Jakob Stoklund Olesen i->end.getBaseIndex()) 438df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen return false; 439df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen return true; 440df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen } 441df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen 442e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen /// isSpillable - Can this interval be spilled? 443e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen bool isSpillable() const { 444e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen return weight != HUGE_VALF; 445e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen } 446e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen 447e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen /// markNotSpillable - Mark interval as not spillable 448e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen void markNotSpillable() { 449e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen weight = HUGE_VALF; 450e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen } 451e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen 452fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner bool operator<(const LiveInterval& other) const { 453233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames const SlotIndex &thisIndex = beginIndex(); 454233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames const SlotIndex &otherIndex = other.beginIndex(); 455da4ae4be5b2b8fa35ef989e548530833428f36bfBob Wilson return (thisIndex < otherIndex || 456da4ae4be5b2b8fa35ef989e548530833428f36bfBob Wilson (thisIndex == otherIndex && reg < other.reg)); 457fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 458fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 459b77ec7d26405125fa5685370af5f17fcc9edbecdJakob Stoklund Olesen void print(raw_ostream &OS) const; 460abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner void dump() const; 461fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 462261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth /// \brief Walk the interval and assert if any invariants fail to hold. 463261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth /// 464261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth /// Note that this is a no-op when asserts are disabled. 465261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth#ifdef NDEBUG 466261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth void verify() const {} 467261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth#else 468261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth void verify() const; 469261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth#endif 470261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth 4711b8f70a0d3d72ce55c8036b79bcc80b130b5f7b2Lang Hames private: 4721b8f70a0d3d72ce55c8036b79bcc80b130b5f7b2Lang Hames 4731b8f70a0d3d72ce55c8036b79bcc80b130b5f7b2Lang Hames Ranges::iterator addRangeFrom(LiveRange LR, Ranges::iterator From); 474233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames void extendIntervalEndTo(Ranges::iterator I, SlotIndex NewEnd); 475233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames Ranges::iterator extendIntervalStartTo(Ranges::iterator I, SlotIndex NewStr); 4766f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames void markValNoForDeletion(VNInfo *V); 477e585e75612ef5fd32e2bb2c9f635496791a20f8bChandler Carruth void mergeIntervalRanges(const LiveInterval &RHS, 4784e996de58cfad27033165d8feb8f296b8cbe20caChandler Carruth VNInfo *LHSValNo = 0, 479e585e75612ef5fd32e2bb2c9f635496791a20f8bChandler Carruth const VNInfo *RHSValNo = 0); 480233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 4811b8f70a0d3d72ce55c8036b79bcc80b130b5f7b2Lang Hames LiveInterval& operator=(const LiveInterval& rhs); // DO NOT IMPLEMENT 4821b8f70a0d3d72ce55c8036b79bcc80b130b5f7b2Lang Hames 483fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner }; 484fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 4851cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar inline raw_ostream &operator<<(raw_ostream &OS, const LiveInterval &LI) { 4861cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar LI.print(OS); 4871cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar return OS; 4881cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar } 489fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 490c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// LiveRangeQuery - Query information about a live range around a given 491c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// instruction. This class hides the implementation details of live ranges, 492c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// and it should be used as the primary interface for examining live ranges 493c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// around instructions. 494c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// 495c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen class LiveRangeQuery { 496c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen VNInfo *EarlyVal; 497c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen VNInfo *LateVal; 498c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen SlotIndex EndPoint; 499c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen bool Kill; 500c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen 501c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen public: 502c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// Create a LiveRangeQuery for the given live range and instruction index. 503c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// The sub-instruction slot of Idx doesn't matter, only the instruction it 504c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// refers to is considered. 505c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen LiveRangeQuery(const LiveInterval &LI, SlotIndex Idx) 506c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen : EarlyVal(0), LateVal(0), Kill(false) { 507c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen // Find the segment that enters the instruction. 508c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen LiveInterval::const_iterator I = LI.find(Idx.getBaseIndex()); 509c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen LiveInterval::const_iterator E = LI.end(); 510c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen if (I == E) 511c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen return; 512c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen // Is this an instruction live-in segment? 513c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen if (SlotIndex::isEarlierInstr(I->start, Idx)) { 514c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen EarlyVal = I->valno; 515c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen EndPoint = I->end; 516c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen // Move to the potentially live-out segment. 517c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen if (SlotIndex::isSameInstr(Idx, I->end)) { 518c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen Kill = true; 519c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen if (++I == E) 520c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen return; 521c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen } 522c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen } 523c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen // I now points to the segment that may be live-through, or defined by 524c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen // this instr. Ignore segments starting after the current instr. 525c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen if (SlotIndex::isEarlierInstr(Idx, I->start)) 526c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen return; 527c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen LateVal = I->valno; 528c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen EndPoint = I->end; 529c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen } 530c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen 531c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// Return the value that is live-in to the instruction. This is the value 532c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// that will be read by the instruction's use operands. Return NULL if no 533c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// value is live-in. 534c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen VNInfo *valueIn() const { 535c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen return EarlyVal; 536c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen } 537c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen 538c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// Return true if the live-in value is killed by this instruction. This 539c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// means that either the live range ends at the instruction, or it changes 540c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// value. 541c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen bool isKill() const { 542c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen return Kill; 543c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen } 544c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen 545c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// Return true if this instruction has a dead def. 546c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen bool isDeadDef() const { 547c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen return EndPoint.isDead(); 548c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen } 549c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen 550c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// Return the value leaving the instruction, if any. This can be a 551c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// live-through value, or a live def. A dead def returns NULL. 552c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen VNInfo *valueOut() const { 553c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen return isDeadDef() ? 0 : LateVal; 554c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen } 555c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen 556c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// Return the value defined by this instruction, if any. This includes 557c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// dead defs, it is the value created by the instruction's def operands. 558c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen VNInfo *valueDefined() const { 559c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen return EarlyVal == LateVal ? 0 : LateVal; 560c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen } 561c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen 562c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// Return the end point of the last live range segment to interact with 563c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// the instruction, if any. 564c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// 565c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// The end point is an invalid SlotIndex only if the live range doesn't 566c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// intersect the instruction at all. 567c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// 568c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// The end point may be at or past the end of the instruction's basic 569c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen /// block. That means the value was live out of the block. 570c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen SlotIndex endPoint() const { 571c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen return EndPoint; 572c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen } 573c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen }; 574c313c6b9fffa58e88c166e50a759d689686f17f0Jakob Stoklund Olesen 5750253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a 5760253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// LiveInterval into equivalence clases of connected components. A 5770253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// LiveInterval that has multiple connected components can be broken into 5780253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// multiple LiveIntervals. 5790253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// 5800253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// Given a LiveInterval that may have multiple connected components, run: 5810253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// 5820253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// unsigned numComps = ConEQ.Classify(LI); 5830253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// if (numComps > 1) { 5840253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// // allocate numComps-1 new LiveIntervals into LIS[1..] 5850253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// ConEQ.Distribute(LIS); 5860253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// } 5870253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 5880253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen class ConnectedVNInfoEqClasses { 5892254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen LiveIntervals &LIS; 5902254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen IntEqClasses EqClass; 5910253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 5920253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // Note that values a and b are connected. 5930253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen void Connect(unsigned a, unsigned b); 5940253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 5950253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen unsigned Renumber(); 5960253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 5970253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen public: 5982254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen explicit ConnectedVNInfoEqClasses(LiveIntervals &lis) : LIS(lis) {} 5990253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 6000253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// Classify - Classify the values in LI into connected components. 6010253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// Return the number of connected components. 6020253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen unsigned Classify(const LiveInterval *LI); 6030253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 604cb367778c0fb3200292df4f3982f54167444d1f6Jakob Stoklund Olesen /// getEqClass - Classify creates equivalence classes numbered 0..N. Return 605cb367778c0fb3200292df4f3982f54167444d1f6Jakob Stoklund Olesen /// the equivalence class assigned the VNI. 6062254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen unsigned getEqClass(const VNInfo *VNI) const { return EqClass[VNI->id]; } 607cb367778c0fb3200292df4f3982f54167444d1f6Jakob Stoklund Olesen 608cb367778c0fb3200292df4f3982f54167444d1f6Jakob Stoklund Olesen /// Distribute - Distribute values in LIV[0] into a separate LiveInterval 609cb367778c0fb3200292df4f3982f54167444d1f6Jakob Stoklund Olesen /// for each connected component. LIV must have a LiveInterval for each 610cb367778c0fb3200292df4f3982f54167444d1f6Jakob Stoklund Olesen /// connected component. The LiveIntervals in Liv[1..] must be empty. 6112254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen /// Instructions using LIV[0] are rewritten. 6122254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen void Distribute(LiveInterval *LIV[], MachineRegisterInfo &MRI); 613cb367778c0fb3200292df4f3982f54167444d1f6Jakob Stoklund Olesen 6140253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen }; 6150253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 6160253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen} 617fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner#endif 618