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// 1087a86058fa0726328de42ace85b5532d18775646Matthias Braun// This file implements the LiveRange and LiveInterval classes. Given some 1187a86058fa0726328de42ace85b5532d18775646Matthias Braun// numbering of each the machine instructions an interval [i, j) is said to be a 1287a86058fa0726328de42ace85b5532d18775646Matthias Braun// live range 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 1487a86058fa0726328de42ace85b5532d18775646Matthias Braun// that v is live at i'. In this implementation ranges can have holes, 1587a86058fa0726328de42ace85b5532d18775646Matthias Braun// i.e. a range might look like [1,20), [50,65), [1000,1001). Each 1687a86058fa0726328de42ace85b5532d18775646Matthias Braun// individual segment is represented as an instance of LiveRange::Segment, 1787a86058fa0726328de42ace85b5532d18775646Matthias Braun// and the whole range is represented as an instance of LiveRange. 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" 25233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#include "llvm/CodeGen/SlotIndexes.h" 26255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/Support/AlignOf.h" 27255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/Support/Allocator.h" 28fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner#include <cassert> 29de551f91d8816632a76a065084caab9fab6aacffDan Gohman#include <climits> 30ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#include <set> 31fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 32fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattnernamespace llvm { 3345c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen class CoalescerPair; 34233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames class LiveIntervals; 352638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng class MachineInstr; 3690f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng class MachineRegisterInfo; 376f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman class TargetRegisterInfo; 381cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar class raw_ostream; 3987a86058fa0726328de42ace85b5532d18775646Matthias Braun template <typename T, unsigned Small> class SmallPtrSet; 407ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng 41857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// VNInfo - Value Number Information. 42857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// This class holds information about a machine level values, including 43857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// definition and use points. 44857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// 45857c4e01f85601cf2084adb860616256ee47c177Lang Hames class VNInfo { 46857c4e01f85601cf2084adb860616256ee47c177Lang Hames public: 47ce9a20b808ba48adf72e0c0615f903a65e9f9eb8Benjamin Kramer typedef BumpPtrAllocator Allocator; 48ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames 49857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// The ID number of this value. 507ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng unsigned id; 5115a571436da812c7cecbc3f3423ead2edff50358Jakob Stoklund Olesen 521130d220a33a6171e408d9ec4594242907541e1bAndrew Trick /// The index of the defining instruction. 53233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex def; 5452c1afcaea61440950a11a4ccadac4354420d727Lang Hames 55857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// VNInfo constructor. 563b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen VNInfo(unsigned i, SlotIndex d) 57b2beac2b9671f7d9773329d62c2821c8ac449ac5Jakob Stoklund Olesen : id(i), def(d) 586c4329ec96fa49e42310a8fe57813a5d7b73e621Jakob Stoklund Olesen { } 59857c4e01f85601cf2084adb860616256ee47c177Lang Hames 60857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// VNInfo construtor, copies values from orig, except for the value number. 61857c4e01f85601cf2084adb860616256ee47c177Lang Hames VNInfo(unsigned i, const VNInfo &orig) 62b2beac2b9671f7d9773329d62c2821c8ac449ac5Jakob Stoklund Olesen : id(i), def(orig.def) 6352c1afcaea61440950a11a4ccadac4354420d727Lang Hames { } 6452c1afcaea61440950a11a4ccadac4354420d727Lang Hames 6552c1afcaea61440950a11a4ccadac4354420d727Lang Hames /// Copy from the parameter into this VNInfo. 6652c1afcaea61440950a11a4ccadac4354420d727Lang Hames void copyFrom(VNInfo &src) { 6752c1afcaea61440950a11a4ccadac4354420d727Lang Hames def = src.def; 6852c1afcaea61440950a11a4ccadac4354420d727Lang Hames } 69857c4e01f85601cf2084adb860616256ee47c177Lang Hames 70857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// Returns true if this value is defined by a PHI instruction (or was, 713f4f420ab7acb10221ba971543a7eed5489fb626Robert Wilhelm /// PHI instructions may have been eliminated). 72b18d779b35909cd5b753871f8bf2ff4f6c17ace1Jakob Stoklund Olesen /// PHI-defs begin at a block boundary, all other defs begin at register or 73b18d779b35909cd5b753871f8bf2ff4f6c17ace1Jakob Stoklund Olesen /// EC slots. 74b18d779b35909cd5b753871f8bf2ff4f6c17ace1Jakob Stoklund Olesen bool isPHIDef() const { return def.isBlock(); } 75857c4e01f85601cf2084adb860616256ee47c177Lang Hames 76857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// Returns true if this value is unused. 77b2beac2b9671f7d9773329d62c2821c8ac449ac5Jakob Stoklund Olesen bool isUnused() const { return !def.isValid(); } 78b2beac2b9671f7d9773329d62c2821c8ac449ac5Jakob Stoklund Olesen 79b2beac2b9671f7d9773329d62c2821c8ac449ac5Jakob Stoklund Olesen /// Mark this value as unused. 80b2beac2b9671f7d9773329d62c2821c8ac449ac5Jakob Stoklund Olesen void markUnused() { def = SlotIndex(); } 818651125d2885f74546b6e2a556082111d5b75da3Lang Hames }; 82ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames 835649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun /// Result of a LiveRange query. This class hides the implementation details 845649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun /// of live ranges, and it should be used as the primary interface for 855649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun /// examining live ranges around instructions. 865649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun class LiveQueryResult { 875649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun VNInfo *const EarlyVal; 885649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun VNInfo *const LateVal; 895649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun const SlotIndex EndPoint; 905649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun const bool Kill; 915649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun 925649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun public: 935649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun LiveQueryResult(VNInfo *EarlyVal, VNInfo *LateVal, SlotIndex EndPoint, 945649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun bool Kill) 955649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun : EarlyVal(EarlyVal), LateVal(LateVal), EndPoint(EndPoint), Kill(Kill) 965649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun {} 975649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun 985649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun /// Return the value that is live-in to the instruction. This is the value 995649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun /// that will be read by the instruction's use operands. Return NULL if no 1005649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun /// value is live-in. 1015649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun VNInfo *valueIn() const { 1025649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun return EarlyVal; 1035649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun } 1045649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun 1055649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun /// Return true if the live-in value is killed by this instruction. This 1065649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun /// means that either the live range ends at the instruction, or it changes 1075649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun /// value. 1085649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun bool isKill() const { 1095649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun return Kill; 1105649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun } 1115649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun 1125649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun /// Return true if this instruction has a dead def. 1135649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun bool isDeadDef() const { 1145649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun return EndPoint.isDead(); 1155649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun } 1165649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun 1175649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun /// Return the value leaving the instruction, if any. This can be a 1185649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun /// live-through value, or a live def. A dead def returns NULL. 1195649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun VNInfo *valueOut() const { 120dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return isDeadDef() ? nullptr : LateVal; 1215649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun } 1225649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun 123ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// Returns the value alive at the end of the instruction, if any. This can 124ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// be a live-through value, a live def or a dead def. 125ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines VNInfo *valueOutOrDead() const { 126ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return LateVal; 127ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 128ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 1295649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun /// Return the value defined by this instruction, if any. This includes 1305649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun /// dead defs, it is the value created by the instruction's def operands. 1315649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun VNInfo *valueDefined() const { 132dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return EarlyVal == LateVal ? nullptr : LateVal; 1335649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun } 1345649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun 1355649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun /// Return the end point of the last live range segment to interact with 1365649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun /// the instruction, if any. 1375649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun /// 1385649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun /// The end point is an invalid SlotIndex only if the live range doesn't 1395649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun /// intersect the instruction at all. 1405649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun /// 1415649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun /// The end point may be at or past the end of the instruction's basic 1425649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun /// block. That means the value was live out of the block. 1435649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun SlotIndex endPoint() const { 1445649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun return EndPoint; 1455649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun } 1465649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun }; 1475649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun 14887a86058fa0726328de42ace85b5532d18775646Matthias Braun /// This class represents the liveness of a register, stack slot, etc. 14987a86058fa0726328de42ace85b5532d18775646Matthias Braun /// It manages an ordered list of Segment objects. 15087a86058fa0726328de42ace85b5532d18775646Matthias Braun /// The Segments are organized in a static single assignment form: At places 15187a86058fa0726328de42ace85b5532d18775646Matthias Braun /// where a new value is defined or different values reach a CFG join a new 15287a86058fa0726328de42ace85b5532d18775646Matthias Braun /// segment with a new value number is used. 15387a86058fa0726328de42ace85b5532d18775646Matthias Braun class LiveRange { 15408759c56010aaffae5c63944230c06acd0033e5bLang Hames public: 15508759c56010aaffae5c63944230c06acd0033e5bLang Hames 156331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun /// This represents a simple continuous liveness interval for a value. 157331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun /// The start point is inclusive, the end point exclusive. These intervals 158331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun /// are rendered as [start,end). 159331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun struct Segment { 160331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun SlotIndex start; // Start point of the interval (inclusive) 161331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun SlotIndex end; // End point of the interval (exclusive) 162331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun VNInfo *valno; // identifier for the value contained in this segment. 163331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun 164dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Segment() : valno(nullptr) {} 165331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun 166331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun Segment(SlotIndex S, SlotIndex E, VNInfo *V) 167331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun : start(S), end(E), valno(V) { 168331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun assert(S < E && "Cannot create empty or backwards segment"); 169331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun } 170331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun 171331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun /// Return true if the index is covered by this segment. 172331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun bool contains(SlotIndex I) const { 173331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun return start <= I && I < end; 174331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun } 175331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun 176331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun /// Return true if the given interval, [S, E), is covered by this segment. 177331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun bool containsInterval(SlotIndex S, SlotIndex E) const { 178331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun assert((S < E) && "Backwards interval?"); 179331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun return (start <= S && S < end) && (start < E && E <= end); 180331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun } 181331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun 182331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun bool operator<(const Segment &Other) const { 18336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return std::tie(start, end) < std::tie(Other.start, Other.end); 184331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun } 185331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun bool operator==(const Segment &Other) const { 186331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun return start == Other.start && end == Other.end; 187331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun } 188331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun 189331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun void dump() const; 190331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun }; 191331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun 192331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun typedef SmallVector<Segment,4> Segments; 1937ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng typedef SmallVector<VNInfo*,4> VNInfoList; 1947ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng 19587a86058fa0726328de42ace85b5532d18775646Matthias Braun Segments segments; // the liveness segments 1967ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfoList valnos; // value#'s 1971b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 198ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // The segment set is used temporarily to accelerate initial computation 199ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // of live ranges of physical registers in computeRegUnitRange. 200ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // After that the set is flushed to the segment vector and deleted. 201ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines typedef std::set<Segment> SegmentSet; 2024c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar std::unique_ptr<SegmentSet> segmentSet; 203ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 204331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun typedef Segments::iterator iterator; 205331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun iterator begin() { return segments.begin(); } 206331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun iterator end() { return segments.end(); } 20723b71c1e1e33219327b1c0edf43034dbe4c3ae90Chris Lattner 208331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun typedef Segments::const_iterator const_iterator; 209331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun const_iterator begin() const { return segments.begin(); } 210331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun const_iterator end() const { return segments.end(); } 211bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner 2121a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng typedef VNInfoList::iterator vni_iterator; 2137ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng vni_iterator vni_begin() { return valnos.begin(); } 21487a86058fa0726328de42ace85b5532d18775646Matthias Braun vni_iterator vni_end() { return valnos.end(); } 2151a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng 2161a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng typedef VNInfoList::const_iterator const_vni_iterator; 2177ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng const_vni_iterator vni_begin() const { return valnos.begin(); } 21887a86058fa0726328de42ace85b5532d18775646Matthias Braun const_vni_iterator vni_end() const { return valnos.end(); } 2197ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng 220ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// Constructs a new LiveRange object. 2214c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar LiveRange(bool UseSegmentSet = false) 2224c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar : segmentSet(UseSegmentSet ? llvm::make_unique<SegmentSet>() 2234c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar : nullptr) {} 224ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 225ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// Constructs a new LiveRange object by copying segments and valnos from 226ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// another LiveRange. 2274c5e43da7792f75567b693105cc53e3f1992ad98Pirama Arumuga Nainar LiveRange(const LiveRange &Other, BumpPtrAllocator &Allocator) { 228ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines assert(Other.segmentSet == nullptr && 229ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines "Copying of LiveRanges with active SegmentSets is not supported"); 230ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 231ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Duplicate valnos. 232ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (const VNInfo *VNI : Other.valnos) { 233ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines createValueCopy(VNI, Allocator); 234ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 235ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Now we can copy segments and remap their valnos. 236ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (const Segment &S : Other.segments) { 237ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines segments.push_back(Segment(S.start, S.end, valnos[S.valno->id])); 238ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 239ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 240ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 241331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun /// advanceTo - Advance the specified iterator to point to the Segment 242743ef6d70e710353c1e2b6a4b23af1262f4a475bChris Lattner /// containing the specified position, or end() if the position is past the 24387a86058fa0726328de42ace85b5532d18775646Matthias Braun /// end of the range. If no Segment contains this position, but the 244f3b11aa6a72e0c31066a60c2e888e7a5eb5f2399Dan Gohman /// position is in a hole, this method returns an iterator pointing to the 245331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun /// Segment immediately after the hole. 246233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames iterator advanceTo(iterator I, SlotIndex Pos) { 2478d121404370cd57be7e72543127a1afe2faa1b10Jakob Stoklund Olesen assert(I != end()); 2488651125d2885f74546b6e2a556082111d5b75da3Lang Hames if (Pos >= endIndex()) 249743ef6d70e710353c1e2b6a4b23af1262f4a475bChris Lattner return end(); 250743ef6d70e710353c1e2b6a4b23af1262f4a475bChris Lattner while (I->end <= Pos) ++I; 251743ef6d70e710353c1e2b6a4b23af1262f4a475bChris Lattner return I; 252743ef6d70e710353c1e2b6a4b23af1262f4a475bChris Lattner } 2531b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 254ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const_iterator advanceTo(const_iterator I, SlotIndex Pos) const { 255ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines assert(I != end()); 256ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Pos >= endIndex()) 257ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return end(); 258ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines while (I->end <= Pos) ++I; 259ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return I; 260ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 261ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 262331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun /// find - Return an iterator pointing to the first segment that ends after 263f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen /// Pos, or end(). This is the same as advanceTo(begin(), Pos), but faster 26487a86058fa0726328de42ace85b5532d18775646Matthias Braun /// when searching large ranges. 265f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen /// 266331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun /// If Pos is contained in a Segment, that segment is returned. 267331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun /// If Pos is in a hole, the following Segment is returned. 268f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen /// If Pos is beyond endIndex, end() is returned. 269f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen iterator find(SlotIndex Pos); 270f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen 271f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen const_iterator find(SlotIndex Pos) const { 27287a86058fa0726328de42ace85b5532d18775646Matthias Braun return const_cast<LiveRange*>(this)->find(Pos); 273f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen } 274f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen 275169d4080277c71548de52b54c8a79f99694351c6Owen Anderson void clear() { 27601cb1b665da03e2b74c0724f71751e912ec8c2beTorok Edwin valnos.clear(); 277331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun segments.clear(); 278169d4080277c71548de52b54c8a79f99694351c6Owen Anderson } 279743ef6d70e710353c1e2b6a4b23af1262f4a475bChris Lattner 280b63db853500b3dcb46a96af3f2d5aec003e41d77Matthias Braun size_t size() const { 281331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun return segments.size(); 282b63db853500b3dcb46a96af3f2d5aec003e41d77Matthias Braun } 283b63db853500b3dcb46a96af3f2d5aec003e41d77Matthias Braun 28454898938673d2a13ce31626ec34b2d4d314b2c81Evan Cheng bool hasAtLeastOneValue() const { return !valnos.empty(); } 28554898938673d2a13ce31626ec34b2d4d314b2c81Evan Cheng 286d4e4937b79a7da789379a09117cc74f20cd60623Evan Cheng bool containsOneValue() const { return valnos.size() == 1; } 287abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 28834cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng unsigned getNumValNums() const { return (unsigned)valnos.size(); } 2891b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 290f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng /// getValNumInfo - Returns pointer to the specified val#. 2911a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng /// 292f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng inline VNInfo *getValNumInfo(unsigned ValNo) { 293f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng return valnos[ValNo]; 2941a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng } 295f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng inline const VNInfo *getValNumInfo(unsigned ValNo) const { 296f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng return valnos[ValNo]; 2971a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng } 2981a66f0a4f2348473263fab757d96588bc1e93554Evan Cheng 29987a86058fa0726328de42ace85b5532d18775646Matthias Braun /// containsValue - Returns true if VNI belongs to this range. 3006ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen bool containsValue(const VNInfo *VNI) const { 3016ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen return VNI && VNI->id < getNumValNums() && VNI == getValNumInfo(VNI->id); 3026ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen } 3036ee56e658a6f676e01a06d7a53d1d5c87710f3c3Jakob Stoklund Olesen 304be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner /// getNextValue - Create a new value number and return it. MIIdx specifies 305be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner /// the instruction that defines the value number. 3063b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen VNInfo *getNextValue(SlotIndex def, VNInfo::Allocator &VNInfoAllocator) { 307ce9a20b808ba48adf72e0c0615f903a65e9f9eb8Benjamin Kramer VNInfo *VNI = 3083b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), def); 309857c4e01f85601cf2084adb860616256ee47c177Lang Hames valnos.push_back(VNI); 310857c4e01f85601cf2084adb860616256ee47c177Lang Hames return VNI; 311857c4e01f85601cf2084adb860616256ee47c177Lang Hames } 312857c4e01f85601cf2084adb860616256ee47c177Lang Hames 31387a86058fa0726328de42ace85b5532d18775646Matthias Braun /// createDeadDef - Make sure the range has a value defined at Def. 3144e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen /// If one already exists, return it. Otherwise allocate a new value and 3154e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen /// add liveness for a dead def. 3164e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen VNInfo *createDeadDef(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator); 3174e53a40ea321c43bdf754147dd2ec064985e5b7bJakob Stoklund Olesen 318857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// Create a copy of the given value. The new value will be identical except 319857c4e01f85601cf2084adb860616256ee47c177Lang Hames /// for the Value number. 320c02497f5bae87e71fd5617db5751cb0b3a14bbedChris Lattner VNInfo *createValueCopy(const VNInfo *orig, 321991de14dd62dcbab4b31357ae22dc5b053ba50a0Benjamin Kramer VNInfo::Allocator &VNInfoAllocator) { 322ce9a20b808ba48adf72e0c0615f903a65e9f9eb8Benjamin Kramer VNInfo *VNI = 323ce9a20b808ba48adf72e0c0615f903a65e9f9eb8Benjamin Kramer new (VNInfoAllocator) VNInfo((unsigned)valnos.size(), *orig); 3247ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng valnos.push_back(VNI); 3257ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng return VNI; 3268df786012dc6b875f31ba4152e09c6e0098082eeEvan Cheng } 3274f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 32823436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen /// RenumberValues - Renumber all values in order of appearance and remove 32923436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen /// unused values. 3301c6d387dc90fba589f8effb17c72a39f966f87dfJakob Stoklund Olesen void RenumberValues(); 33123436597a8efad427059f2a6db5264e6a40d2dc7Jakob Stoklund Olesen 332256cb9eaafef2aef81121be7542e04c40d9017cbMatthias Braun /// MergeValueNumberInto - This method is called when two value numbers 333f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner /// are found to be equivalent. This eliminates V1, replacing all 334331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun /// segments with the V1 value number with the V2 value number. This can 335f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner /// cause merging of V1/V2 values numbers and compaction of the value space. 3365b93f6fa82e33b17d618b3e24da513f547861481Owen Anderson VNInfo* MergeValueNumberInto(VNInfo *V1, VNInfo *V2); 337be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 338331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun /// Merge all of the live segments of a specific val# in RHS into this live 33987a86058fa0726328de42ace85b5532d18775646Matthias Braun /// range as the specified value number. The segments in RHS are allowed 34087a86058fa0726328de42ace85b5532d18775646Matthias Braun /// to overlap with segments in the current range, it will replace the 341331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun /// value numbers of the overlaped live segments with the specified value 342331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun /// number. 34387a86058fa0726328de42ace85b5532d18775646Matthias Braun void MergeSegmentsInAsValue(const LiveRange &RHS, VNInfo *LHSValNo); 34432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng 345331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun /// MergeValueInAsValue - Merge all of the segments of a specific val# 34687a86058fa0726328de42ace85b5532d18775646Matthias Braun /// in RHS into this live range as the specified value number. 347331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun /// The segments in RHS are allowed to overlap with segments in the 34887a86058fa0726328de42ace85b5532d18775646Matthias Braun /// current range, but only if the overlapping segments have the 34932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng /// specified value number. 35087a86058fa0726328de42ace85b5532d18775646Matthias Braun void MergeValueInAsValue(const LiveRange &RHS, 35134729256e8058d4106706e9feb2dfad7893502d1Evan Cheng const VNInfo *RHSValNo, VNInfo *LHSValNo); 35232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng 353331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun bool empty() const { return segments.empty(); } 354fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 35587a86058fa0726328de42ace85b5532d18775646Matthias Braun /// beginIndex - Return the lowest numbered slot covered. 356233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex beginIndex() const { 35787a86058fa0726328de42ace85b5532d18775646Matthias Braun assert(!empty() && "Call to beginIndex() on empty range."); 358331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun return segments.front().start; 359fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 360fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 36187a86058fa0726328de42ace85b5532d18775646Matthias Braun /// endNumber - return the maximum point of the range of the whole, 362fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner /// exclusive. 363233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex endIndex() const { 36487a86058fa0726328de42ace85b5532d18775646Matthias Braun assert(!empty() && "Call to endIndex() on empty range."); 365331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun return segments.back().end; 366fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 367fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 368233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames bool expiredAt(SlotIndex index) const { 3698651125d2885f74546b6e2a556082111d5b75da3Lang Hames return index >= endIndex(); 370fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 371fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 372f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen bool liveAt(SlotIndex index) const { 373f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen const_iterator r = find(index); 374f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen return r != end() && r->start <= index; 375f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen } 376fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 377331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun /// Return the segment that contains the specified index, or null if there 378331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun /// is none. 379331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun const Segment *getSegmentContaining(SlotIndex Idx) const { 380331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun const_iterator I = FindSegmentContaining(Idx); 381dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return I == end() ? nullptr : &*I; 382f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattner } 383abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 384331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun /// Return the live segment that contains the specified index, or null if 385331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun /// there is none. 386331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun Segment *getSegmentContaining(SlotIndex Idx) { 387331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun iterator I = FindSegmentContaining(Idx); 388dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return I == end() ? nullptr : &*I; 389ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames } 390ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames 3918de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen /// getVNInfoAt - Return the VNInfo that is live at Idx, or NULL. 3928de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen VNInfo *getVNInfoAt(SlotIndex Idx) const { 393331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun const_iterator I = FindSegmentContaining(Idx); 394dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return I == end() ? nullptr : I->valno; 3958de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen } 3968de3b1eb868fc5e9b6acb334ee487d943863f810Jakob Stoklund Olesen 397b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick /// getVNInfoBefore - Return the VNInfo that is live up to but not 398b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick /// necessarilly including Idx, or NULL. Use this to find the reaching def 399b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick /// used by an instruction at this SlotIndex position. 400b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick VNInfo *getVNInfoBefore(SlotIndex Idx) const { 401331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun const_iterator I = FindSegmentContaining(Idx.getPrevSlot()); 402dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return I == end() ? nullptr : I->valno; 403b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick } 404b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick 405331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun /// Return an iterator to the segment that contains the specified index, or 406331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun /// end() if there is none. 407331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun iterator FindSegmentContaining(SlotIndex Idx) { 408f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen iterator I = find(Idx); 409f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen return I != end() && I->start <= Idx ? I : end(); 410f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen } 411abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 412331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun const_iterator FindSegmentContaining(SlotIndex Idx) const { 413f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen const_iterator I = find(Idx); 414f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen return I != end() && I->start <= Idx ? I : end(); 415f568b2706e274c7d8081cfd0a7ee9b881e5c313bJakob Stoklund Olesen } 4168651125d2885f74546b6e2a556082111d5b75da3Lang Hames 41787a86058fa0726328de42ace85b5532d18775646Matthias Braun /// overlaps - Return true if the intersection of the two live ranges is 418bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner /// not empty. 41987a86058fa0726328de42ace85b5532d18775646Matthias Braun bool overlaps(const LiveRange &other) const { 420624e0b2be6a8db6187206090ee5bc8f24cf55cb7Lang Hames if (other.empty()) 421624e0b2be6a8db6187206090ee5bc8f24cf55cb7Lang Hames return false; 422bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner return overlapsFrom(other, other.begin()); 423bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner } 424bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner 42587a86058fa0726328de42ace85b5532d18775646Matthias Braun /// overlaps - Return true if the two ranges have overlapping segments 42645c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen /// that are not coalescable according to CP. 42745c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen /// 42887a86058fa0726328de42ace85b5532d18775646Matthias Braun /// Overlapping segments where one range is defined by a coalescable 42945c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen /// copy are allowed. 43087a86058fa0726328de42ace85b5532d18775646Matthias Braun bool overlaps(const LiveRange &Other, const CoalescerPair &CP, 43145c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen const SlotIndexes&) const; 43245c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen 43387a86058fa0726328de42ace85b5532d18775646Matthias Braun /// overlaps - Return true if the live range overlaps an interval specified 43487a86058fa0726328de42ace85b5532d18775646Matthias Braun /// by [Start, End). 435233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames bool overlaps(SlotIndex Start, SlotIndex End) const; 436cccdb2b602cf421d8890130308945163620ebc68Evan Cheng 43787a86058fa0726328de42ace85b5532d18775646Matthias Braun /// overlapsFrom - Return true if the intersection of the two live ranges 438bae74d9192f04d8185c7b4580565d56cc4ef53f2Chris Lattner /// is not empty. The specified iterator is a hint that we can begin 43987a86058fa0726328de42ace85b5532d18775646Matthias Braun /// scanning the Other range starting at I. 44087a86058fa0726328de42ace85b5532d18775646Matthias Braun bool overlapsFrom(const LiveRange &Other, const_iterator I) const; 441fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 442ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// Returns true if all segments of the @p Other live range are completely 443ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// covered by this live range. 444ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// Adjacent live ranges do not affect the covering:the liverange 445ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// [1,5](5,10] covers (3,7]. 446ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool covers(const LiveRange &Other) const; 447ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 44887a86058fa0726328de42ace85b5532d18775646Matthias Braun /// Add the specified Segment to this range, merging segments as 449331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun /// appropriate. This returns an iterator to the inserted segment (which 450331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun /// may have grown since it was inserted). 451ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines iterator addSegment(Segment S); 452fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 453ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// If this range is live before @p Use in the basic block that starts at 454ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// @p StartIdx, extend it to be live up to @p Use, and return the value. If 455ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// there is no segment before @p Use, return nullptr. 456ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines VNInfo *extendInBlock(SlotIndex StartIdx, SlotIndex Use); 4579763e2bf39b84f18bd464b0cda61fe1cd98dcaaeJakob Stoklund Olesen 45887a86058fa0726328de42ace85b5532d18775646Matthias Braun /// join - Join two live ranges (this, and other) together. This applies 45987a86058fa0726328de42ace85b5532d18775646Matthias Braun /// mappings to the value numbers in the LHS/RHS ranges as specified. If 46087a86058fa0726328de42ace85b5532d18775646Matthias Braun /// the ranges are not joinable, this aborts. 46187a86058fa0726328de42ace85b5532d18775646Matthias Braun void join(LiveRange &Other, 462233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames const int *ValNoAssignments, 463af992f782fb2cac8d00b352c3dd73f6e782b5758David Greene const int *RHSValNoAssignments, 4641920156982643a1c5c28af6f4684580b516eb597Matthias Braun SmallVectorImpl<VNInfo *> &NewVNInfo); 465abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner 466331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun /// True iff this segment is a single segment that lies between the 467e38afe1e335084134f7830ba6f2208e2ddde59b4Andrew Trick /// specified boundaries, exclusively. Vregs live across a backedge are not 468e38afe1e335084134f7830ba6f2208e2ddde59b4Andrew Trick /// considered local. The boundaries are expected to lie within an extended 469e38afe1e335084134f7830ba6f2208e2ddde59b4Andrew Trick /// basic block, so vregs that are not live out should contain no holes. 470e38afe1e335084134f7830ba6f2208e2ddde59b4Andrew Trick bool isLocal(SlotIndex Start, SlotIndex End) const { 471e38afe1e335084134f7830ba6f2208e2ddde59b4Andrew Trick return beginIndex() > Start.getBaseIndex() && 472e38afe1e335084134f7830ba6f2208e2ddde59b4Andrew Trick endIndex() < End.getBoundaryIndex(); 473e38afe1e335084134f7830ba6f2208e2ddde59b4Andrew Trick } 474e38afe1e335084134f7830ba6f2208e2ddde59b4Andrew Trick 47587a86058fa0726328de42ace85b5532d18775646Matthias Braun /// Remove the specified segment from this range. Note that the segment 476331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun /// must be a single Segment in its entirety. 477331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun void removeSegment(SlotIndex Start, SlotIndex End, 478331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun bool RemoveDeadValNo = false); 479fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 480331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun void removeSegment(Segment S, bool RemoveDeadValNo = false) { 481331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun removeSegment(S.start, S.end, RemoveDeadValNo); 4821bcf7a309eb46c66adc154ad9c8f0562653a8e13Bill Wendling } 4831bcf7a309eb46c66adc154ad9c8f0562653a8e13Bill Wendling 484ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// Remove segment pointed to by iterator @p I from this range. This does 485ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// not remove dead value numbers. 486ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines iterator removeSegment(iterator I) { 487ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return segments.erase(I); 488ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 489ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 4905649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun /// Query Liveness at Idx. 4915649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun /// The sub-instruction slot of Idx doesn't matter, only the instruction 4925649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun /// it refers to is considered. 4935649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun LiveQueryResult Query(SlotIndex Idx) const { 4945649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun // Find the segment that enters the instruction. 4955649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun const_iterator I = find(Idx.getBaseIndex()); 4965649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun const_iterator E = end(); 4975649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun if (I == E) 498dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return LiveQueryResult(nullptr, nullptr, SlotIndex(), false); 4995649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun 5005649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun // Is this an instruction live-in segment? 5015649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun // If Idx is the start index of a basic block, include live-in segments 5025649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun // that start at Idx.getBaseIndex(). 503dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines VNInfo *EarlyVal = nullptr; 504dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines VNInfo *LateVal = nullptr; 5055649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun SlotIndex EndPoint; 5065649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun bool Kill = false; 5075649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun if (I->start <= Idx.getBaseIndex()) { 5085649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun EarlyVal = I->valno; 5095649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun EndPoint = I->end; 5105649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun // Move to the potentially live-out segment. 5115649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun if (SlotIndex::isSameInstr(Idx, I->end)) { 5125649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun Kill = true; 5135649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun if (++I == E) 5145649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun return LiveQueryResult(EarlyVal, LateVal, EndPoint, Kill); 5155649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun } 5165649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun // Special case: A PHIDef value can have its def in the middle of a 5175649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun // segment if the value happens to be live out of the layout 5185649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun // predecessor. 5195649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun // Such a value is not live-in. 5205649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun if (EarlyVal->def == Idx.getBaseIndex()) 521dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines EarlyVal = nullptr; 5225649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun } 5235649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun // I now points to the segment that may be live-through, or defined by 5245649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun // this instr. Ignore segments starting after the current instr. 5255649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun if (!SlotIndex::isEarlierInstr(Idx, I->start)) { 5265649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun LateVal = I->valno; 5275649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun EndPoint = I->end; 5285649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun } 5295649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun return LiveQueryResult(EarlyVal, LateVal, EndPoint, Kill); 5305649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun } 5315649e25ce86b9d89d228ae7c392413571b0f8c19Matthias Braun 532331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun /// removeValNo - Remove all the segments defined by the specified value#. 533d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng /// Also remove the value# from value# list. 534d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng void removeValNo(VNInfo *ValNo); 535d2b8d7bc51b0e41d09b32aeaa550358ccb379009Evan Cheng 53687a86058fa0726328de42ace85b5532d18775646Matthias Braun /// Returns true if the live range is zero length, i.e. no live segments 53787a86058fa0726328de42ace85b5532d18775646Matthias Braun /// span instructions. It doesn't pay to spill such a range. 538f5497fb1b474028709f0a6d8556251dc21e34c26Jakob Stoklund Olesen bool isZeroLength(SlotIndexes *Indexes) const { 539ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (const Segment &S : segments) 540ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (Indexes->getNextNonNullIndex(S.start).getBaseIndex() < 541ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines S.end.getBaseIndex()) 542df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen return false; 543df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen return true; 544df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen } 545df30cf9e61e6586b45b74d1312bef1ee758ef94fJakob Stoklund Olesen 54687a86058fa0726328de42ace85b5532d18775646Matthias Braun bool operator<(const LiveRange& other) const { 547233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames const SlotIndex &thisIndex = beginIndex(); 548233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames const SlotIndex &otherIndex = other.beginIndex(); 54987a86058fa0726328de42ace85b5532d18775646Matthias Braun return thisIndex < otherIndex; 550fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner } 551fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 552ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// Flush segment set into the regular segment vector. 553ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// The method is to be called after the live range 554ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// has been created, if use of the segment set was 555ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// activated in the constructor of the live range. 556ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void flushSegmentSet(); 557ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 558b77ec7d26405125fa5685370af5f17fcc9edbecdJakob Stoklund Olesen void print(raw_ostream &OS) const; 559abf295fc6cfb438617e8b105022ce506f56674d8Chris Lattner void dump() const; 560fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 56187a86058fa0726328de42ace85b5532d18775646Matthias Braun /// \brief Walk the range and assert if any invariants fail to hold. 562261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth /// 563261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth /// Note that this is a no-op when asserts are disabled. 564261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth#ifdef NDEBUG 565261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth void verify() const {} 566261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth#else 567261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth void verify() const; 568261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth#endif 569261b6330896736f674bdb2dd4556a0483f3cfe8dChandler Carruth 570ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines protected: 571ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// Append a segment to the list of segments. 572ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void append(const LiveRange::Segment S); 5731b8f70a0d3d72ce55c8036b79bcc80b130b5f7b2Lang Hames 574ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines private: 575ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines friend class LiveRangeUpdater; 576ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void addSegmentToSet(Segment S); 5776f4e4df1005e67917ebfcf66c8ea5bad5f587155Lang Hames void markValNoForDeletion(VNInfo *V); 578233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 57987a86058fa0726328de42ace85b5532d18775646Matthias Braun }; 58087a86058fa0726328de42ace85b5532d18775646Matthias Braun 58187a86058fa0726328de42ace85b5532d18775646Matthias Braun inline raw_ostream &operator<<(raw_ostream &OS, const LiveRange &LR) { 58287a86058fa0726328de42ace85b5532d18775646Matthias Braun LR.print(OS); 58387a86058fa0726328de42ace85b5532d18775646Matthias Braun return OS; 58487a86058fa0726328de42ace85b5532d18775646Matthias Braun } 58587a86058fa0726328de42ace85b5532d18775646Matthias Braun 58687a86058fa0726328de42ace85b5532d18775646Matthias Braun /// LiveInterval - This class represents the liveness of a register, 58787a86058fa0726328de42ace85b5532d18775646Matthias Braun /// or stack slot. 58887a86058fa0726328de42ace85b5532d18775646Matthias Braun class LiveInterval : public LiveRange { 58987a86058fa0726328de42ace85b5532d18775646Matthias Braun public: 59003d9609c6154ed91daefb4e4f89b7298c11961f3Matthias Braun typedef LiveRange super; 59103d9609c6154ed91daefb4e4f89b7298c11961f3Matthias Braun 592ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// A live range for subregisters. The LaneMask specifies which parts of the 593ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// super register are covered by the interval. 594ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// (@sa TargetRegisterInfo::getSubRegIndexLaneMask()). 595ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines class SubRange : public LiveRange { 596ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines public: 597ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SubRange *Next; 598ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines unsigned LaneMask; 599ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 600ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// Constructs a new SubRange object. 601ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SubRange(unsigned LaneMask) 602ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines : Next(nullptr), LaneMask(LaneMask) { 603ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 604ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 605ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// Constructs a new SubRange object by copying liveness from @p Other. 606ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SubRange(unsigned LaneMask, const LiveRange &Other, 607ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BumpPtrAllocator &Allocator) 608ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines : LiveRange(Other, Allocator), Next(nullptr), LaneMask(LaneMask) { 609ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 610ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines }; 611ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 612ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines private: 613ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SubRange *SubRanges; ///< Single linked list of subregister live ranges. 614ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 615ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines public: 61687a86058fa0726328de42ace85b5532d18775646Matthias Braun const unsigned reg; // the register or stack slot of this interval. 61787a86058fa0726328de42ace85b5532d18775646Matthias Braun float weight; // weight of this interval 61887a86058fa0726328de42ace85b5532d18775646Matthias Braun 61987a86058fa0726328de42ace85b5532d18775646Matthias Braun LiveInterval(unsigned Reg, float Weight) 620ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines : SubRanges(nullptr), reg(Reg), weight(Weight) {} 621ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 622ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ~LiveInterval() { 623ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines clearSubRanges(); 624ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 625ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 626ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines template<typename T> 627ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines class SingleLinkedListIterator { 628ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines T *P; 629ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines public: 630ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SingleLinkedListIterator<T>(T *P) : P(P) {} 631ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SingleLinkedListIterator<T> &operator++() { 632ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines P = P->Next; 633ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return *this; 634ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 635ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SingleLinkedListIterator<T> &operator++(int) { 636ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SingleLinkedListIterator res = *this; 637ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ++*this; 638ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return res; 639ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 640ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool operator!=(const SingleLinkedListIterator<T> &Other) { 641ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return P != Other.operator->(); 642ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 643ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool operator==(const SingleLinkedListIterator<T> &Other) { 644ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return P == Other.operator->(); 645ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 646ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines T &operator*() const { 647ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return *P; 648ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 649ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines T *operator->() const { 650ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return P; 651ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 652ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines }; 653ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 654ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines typedef SingleLinkedListIterator<SubRange> subrange_iterator; 655ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines subrange_iterator subrange_begin() { 656ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return subrange_iterator(SubRanges); 657ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 658ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines subrange_iterator subrange_end() { 659ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return subrange_iterator(nullptr); 660ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 661ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 662ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines typedef SingleLinkedListIterator<const SubRange> const_subrange_iterator; 663ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const_subrange_iterator subrange_begin() const { 664ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return const_subrange_iterator(SubRanges); 665ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 666ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const_subrange_iterator subrange_end() const { 667ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return const_subrange_iterator(nullptr); 668ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 669ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 670ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines iterator_range<subrange_iterator> subranges() { 671ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return make_range(subrange_begin(), subrange_end()); 672ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 673ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 674ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines iterator_range<const_subrange_iterator> subranges() const { 675ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return make_range(subrange_begin(), subrange_end()); 676ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 677ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 678ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// Creates a new empty subregister live range. The range is added at the 679ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// beginning of the subrange list; subrange iterators stay valid. 680ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SubRange *createSubRange(BumpPtrAllocator &Allocator, unsigned LaneMask) { 681ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SubRange *Range = new (Allocator) SubRange(LaneMask); 682ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines appendSubRange(Range); 683ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return Range; 684ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 685ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 686ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// Like createSubRange() but the new range is filled with a copy of the 687ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// liveness information in @p CopyFrom. 688ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SubRange *createSubRangeFrom(BumpPtrAllocator &Allocator, unsigned LaneMask, 689ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines const LiveRange &CopyFrom) { 690ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SubRange *Range = new (Allocator) SubRange(LaneMask, CopyFrom, Allocator); 691ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines appendSubRange(Range); 692ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return Range; 693ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 694ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 695ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// Returns true if subregister liveness information is available. 696ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines bool hasSubRanges() const { 697ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines return SubRanges != nullptr; 698ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 699ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 700ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// Removes all subregister liveness information. 701ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void clearSubRanges(); 702ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 703ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// Removes all subranges without any segments (subranges without segments 704ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// are not considered valid and should only exist temporarily). 705ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void removeEmptySubRanges(); 706ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 707ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// Construct main live range by merging the SubRanges of @p LI. 708ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void constructMainRangeFromSubranges(const SlotIndexes &Indexes, 709ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines VNInfo::Allocator &VNIAllocator); 71087a86058fa0726328de42ace85b5532d18775646Matthias Braun 71187a86058fa0726328de42ace85b5532d18775646Matthias Braun /// getSize - Returns the sum of sizes of all the LiveRange's. 71287a86058fa0726328de42ace85b5532d18775646Matthias Braun /// 71387a86058fa0726328de42ace85b5532d18775646Matthias Braun unsigned getSize() const; 71487a86058fa0726328de42ace85b5532d18775646Matthias Braun 71587a86058fa0726328de42ace85b5532d18775646Matthias Braun /// isSpillable - Can this interval be spilled? 71687a86058fa0726328de42ace85b5532d18775646Matthias Braun bool isSpillable() const { 717eb3602472026dc029beb45ccbe09bc84162ba949Aaron Ballman return weight != llvm::huge_valf; 71887a86058fa0726328de42ace85b5532d18775646Matthias Braun } 71987a86058fa0726328de42ace85b5532d18775646Matthias Braun 72087a86058fa0726328de42ace85b5532d18775646Matthias Braun /// markNotSpillable - Mark interval as not spillable 72187a86058fa0726328de42ace85b5532d18775646Matthias Braun void markNotSpillable() { 722eb3602472026dc029beb45ccbe09bc84162ba949Aaron Ballman weight = llvm::huge_valf; 72387a86058fa0726328de42ace85b5532d18775646Matthias Braun } 72487a86058fa0726328de42ace85b5532d18775646Matthias Braun 72587a86058fa0726328de42ace85b5532d18775646Matthias Braun bool operator<(const LiveInterval& other) const { 72687a86058fa0726328de42ace85b5532d18775646Matthias Braun const SlotIndex &thisIndex = beginIndex(); 72787a86058fa0726328de42ace85b5532d18775646Matthias Braun const SlotIndex &otherIndex = other.beginIndex(); 72836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return std::tie(thisIndex, reg) < std::tie(otherIndex, other.reg); 72987a86058fa0726328de42ace85b5532d18775646Matthias Braun } 73087a86058fa0726328de42ace85b5532d18775646Matthias Braun 73103d9609c6154ed91daefb4e4f89b7298c11961f3Matthias Braun void print(raw_ostream &OS) const; 73203d9609c6154ed91daefb4e4f89b7298c11961f3Matthias Braun void dump() const; 73303d9609c6154ed91daefb4e4f89b7298c11961f3Matthias Braun 734ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// \brief Walks the interval and assert if any invariants fail to hold. 735ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// 736ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// Note that this is a no-op when asserts are disabled. 737ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#ifdef NDEBUG 738ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void verify(const MachineRegisterInfo *MRI = nullptr) const {} 739ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#else 740ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void verify(const MachineRegisterInfo *MRI = nullptr) const; 741ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines#endif 742ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 74387a86058fa0726328de42ace85b5532d18775646Matthias Braun private: 744ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// Appends @p Range to SubRanges list. 745ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void appendSubRange(SubRange *Range) { 746ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Range->Next = SubRanges; 747ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SubRanges = Range; 748ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 7491b8f70a0d3d72ce55c8036b79bcc80b130b5f7b2Lang Hames 750ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines /// Free memory held by SubRange. 751ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines void freeSubRange(SubRange *S); 752fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner }; 753fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 7541cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar inline raw_ostream &operator<<(raw_ostream &OS, const LiveInterval &LI) { 7551cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar LI.print(OS); 7561cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar return OS; 7571cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar } 758fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner 75987a86058fa0726328de42ace85b5532d18775646Matthias Braun raw_ostream &operator<<(raw_ostream &OS, const LiveRange::Segment &S); 760331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun 76187a86058fa0726328de42ace85b5532d18775646Matthias Braun inline bool operator<(SlotIndex V, const LiveRange::Segment &S) { 762331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun return V < S.start; 763331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun } 764331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun 76587a86058fa0726328de42ace85b5532d18775646Matthias Braun inline bool operator<(const LiveRange::Segment &S, SlotIndex V) { 766331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun return S.start < V; 767331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun } 768331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun 76987a86058fa0726328de42ace85b5532d18775646Matthias Braun /// Helper class for performant LiveRange bulk updates. 7701a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen /// 77187a86058fa0726328de42ace85b5532d18775646Matthias Braun /// Calling LiveRange::addSegment() repeatedly can be expensive on large 7721a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen /// live ranges because segments after the insertion point may need to be 7731a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen /// shifted. The LiveRangeUpdater class can defer the shifting when adding 7741a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen /// many segments in order. 7751a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen /// 77687a86058fa0726328de42ace85b5532d18775646Matthias Braun /// The LiveRange will be in an invalid state until flush() is called. 7771a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen class LiveRangeUpdater { 77887a86058fa0726328de42ace85b5532d18775646Matthias Braun LiveRange *LR; 7791a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen SlotIndex LastStart; 78087a86058fa0726328de42ace85b5532d18775646Matthias Braun LiveRange::iterator WriteI; 78187a86058fa0726328de42ace85b5532d18775646Matthias Braun LiveRange::iterator ReadI; 78287a86058fa0726328de42ace85b5532d18775646Matthias Braun SmallVector<LiveRange::Segment, 16> Spills; 7831a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen void mergeSpills(); 7841a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 7851a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen public: 78687a86058fa0726328de42ace85b5532d18775646Matthias Braun /// Create a LiveRangeUpdater for adding segments to LR. 78787a86058fa0726328de42ace85b5532d18775646Matthias Braun /// LR will temporarily be in an invalid state until flush() is called. 788dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LiveRangeUpdater(LiveRange *lr = nullptr) : LR(lr) {} 7891a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 7901a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen ~LiveRangeUpdater() { flush(); } 7911a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 79287a86058fa0726328de42ace85b5532d18775646Matthias Braun /// Add a segment to LR and coalesce when possible, just like 79387a86058fa0726328de42ace85b5532d18775646Matthias Braun /// LR.addSegment(). Segments should be added in increasing start order for 794331de11a0acc6a095b98914b5f05ff242c9d7819Matthias Braun /// best performance. 79587a86058fa0726328de42ace85b5532d18775646Matthias Braun void add(LiveRange::Segment); 7961a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 7971a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen void add(SlotIndex Start, SlotIndex End, VNInfo *VNI) { 79887a86058fa0726328de42ace85b5532d18775646Matthias Braun add(LiveRange::Segment(Start, End, VNI)); 7991a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen } 8001a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 80187a86058fa0726328de42ace85b5532d18775646Matthias Braun /// Return true if the LR is currently in an invalid state, and flush() 8021a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen /// needs to be called. 8031a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen bool isDirty() const { return LastStart.isValid(); } 8041a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 80587a86058fa0726328de42ace85b5532d18775646Matthias Braun /// Flush the updater state to LR so it is valid and contains all added 8061a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen /// segments. 8071a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen void flush(); 8081a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 8091a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen /// Select a different destination live range. 81087a86058fa0726328de42ace85b5532d18775646Matthias Braun void setDest(LiveRange *lr) { 81187a86058fa0726328de42ace85b5532d18775646Matthias Braun if (LR != lr && isDirty()) 8121a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen flush(); 81387a86058fa0726328de42ace85b5532d18775646Matthias Braun LR = lr; 8141a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen } 8151a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 8161a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen /// Get the current destination live range. 81787a86058fa0726328de42ace85b5532d18775646Matthias Braun LiveRange *getDest() const { return LR; } 8181a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 8191a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen void dump() const; 8201a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen void print(raw_ostream&) const; 8211a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen }; 8221a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 8231a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen inline raw_ostream &operator<<(raw_ostream &OS, const LiveRangeUpdater &X) { 8241a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen X.print(OS); 8251a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen return OS; 8261a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen } 8271a41f32546019340f27a6f3854f3a73163a25dfeJakob Stoklund Olesen 8280253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// ConnectedVNInfoEqClasses - Helper class that can divide VNInfos in a 8290253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// LiveInterval into equivalence clases of connected components. A 8300253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// LiveInterval that has multiple connected components can be broken into 8310253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// multiple LiveIntervals. 8320253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// 8330253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// Given a LiveInterval that may have multiple connected components, run: 8340253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// 8350253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// unsigned numComps = ConEQ.Classify(LI); 8360253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// if (numComps > 1) { 8370253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// // allocate numComps-1 new LiveIntervals into LIS[1..] 8380253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// ConEQ.Distribute(LIS); 8390253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// } 8400253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 8410253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen class ConnectedVNInfoEqClasses { 8422254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen LiveIntervals &LIS; 8432254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen IntEqClasses EqClass; 8440253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 8450253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen // Note that values a and b are connected. 8460253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen void Connect(unsigned a, unsigned b); 8470253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 8480253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen unsigned Renumber(); 8490253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 8500253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen public: 8512254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen explicit ConnectedVNInfoEqClasses(LiveIntervals &lis) : LIS(lis) {} 8520253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 8530253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// Classify - Classify the values in LI into connected components. 8540253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen /// Return the number of connected components. 8550253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen unsigned Classify(const LiveInterval *LI); 8560253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 857cb367778c0fb3200292df4f3982f54167444d1f6Jakob Stoklund Olesen /// getEqClass - Classify creates equivalence classes numbered 0..N. Return 858cb367778c0fb3200292df4f3982f54167444d1f6Jakob Stoklund Olesen /// the equivalence class assigned the VNI. 8592254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen unsigned getEqClass(const VNInfo *VNI) const { return EqClass[VNI->id]; } 860cb367778c0fb3200292df4f3982f54167444d1f6Jakob Stoklund Olesen 861cb367778c0fb3200292df4f3982f54167444d1f6Jakob Stoklund Olesen /// Distribute - Distribute values in LIV[0] into a separate LiveInterval 862cb367778c0fb3200292df4f3982f54167444d1f6Jakob Stoklund Olesen /// for each connected component. LIV must have a LiveInterval for each 863cb367778c0fb3200292df4f3982f54167444d1f6Jakob Stoklund Olesen /// connected component. The LiveIntervals in Liv[1..] must be empty. 8642254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen /// Instructions using LIV[0] are rewritten. 8652254227791ea267426b9ac674fc6d87decb65bc1Jakob Stoklund Olesen void Distribute(LiveInterval *LIV[], MachineRegisterInfo &MRI); 866cb367778c0fb3200292df4f3982f54167444d1f6Jakob Stoklund Olesen 8670253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen }; 8680253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen 8690253df9a897ce541d56146699cedd79c464bda5eJakob Stoklund Olesen} 870fb449b9ea5a37fb411aee7d42f6a76119602288dChris Lattner#endif 871