1327952Sdim//===- HexagonBlockRanges.h -------------------------------------*- C++ -*-===// 2303231Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6303231Sdim// 7303231Sdim//===----------------------------------------------------------------------===// 8303231Sdim 9327952Sdim#ifndef LLVM_LIB_TARGET_HEXAGON_HEXAGONBLOCKRANGES_H 10327952Sdim#define LLVM_LIB_TARGET_HEXAGON_HEXAGONBLOCKRANGES_H 11327952Sdim 12303231Sdim#include "llvm/ADT/BitVector.h" 13314564Sdim#include <cassert> 14303231Sdim#include <map> 15303231Sdim#include <set> 16321369Sdim#include <utility> 17303231Sdim#include <vector> 18303231Sdim 19303231Sdimnamespace llvm { 20303231Sdim 21314564Sdimclass HexagonSubtarget; 22314564Sdimclass MachineBasicBlock; 23314564Sdimclass MachineFunction; 24314564Sdimclass MachineInstr; 25327952Sdimclass MachineRegisterInfo; 26314564Sdimclass raw_ostream; 27314564Sdimclass TargetInstrInfo; 28314564Sdimclass TargetRegisterInfo; 29314564Sdim 30303231Sdimstruct HexagonBlockRanges { 31303231Sdim HexagonBlockRanges(MachineFunction &MF); 32303231Sdim 33303231Sdim struct RegisterRef { 34303231Sdim unsigned Reg, Sub; 35327952Sdim 36303231Sdim bool operator<(RegisterRef R) const { 37303231Sdim return Reg < R.Reg || (Reg == R.Reg && Sub < R.Sub); 38303231Sdim } 39303231Sdim }; 40327952Sdim using RegisterSet = std::set<RegisterRef>; 41303231Sdim 42303231Sdim // This is to represent an "index", which is an abstraction of a position 43303231Sdim // of an instruction within a basic block. 44303231Sdim class IndexType { 45303231Sdim public: 46303231Sdim enum : unsigned { 47303231Sdim None = 0, 48303231Sdim Entry = 1, 49303231Sdim Exit = 2, 50303231Sdim First = 11 // 10th + 1st 51303231Sdim }; 52303231Sdim 53327952Sdim IndexType() {} 54303231Sdim IndexType(unsigned Idx) : Index(Idx) {} 55314564Sdim 56314564Sdim static bool isInstr(IndexType X) { return X.Index >= First; } 57314564Sdim 58303231Sdim operator unsigned() const; 59303231Sdim bool operator== (unsigned x) const; 60303231Sdim bool operator== (IndexType Idx) const; 61303231Sdim bool operator!= (unsigned x) const; 62303231Sdim bool operator!= (IndexType Idx) const; 63303231Sdim IndexType operator++ (); 64303231Sdim bool operator< (unsigned Idx) const; 65303231Sdim bool operator< (IndexType Idx) const; 66303231Sdim bool operator<= (IndexType Idx) const; 67303231Sdim 68303231Sdim private: 69303231Sdim bool operator> (IndexType Idx) const; 70303231Sdim bool operator>= (IndexType Idx) const; 71303231Sdim 72327952Sdim unsigned Index = None; 73303231Sdim }; 74303231Sdim 75303231Sdim // A range of indices, essentially a representation of a live range. 76303231Sdim // This is also used to represent "dead ranges", i.e. ranges where a 77303231Sdim // register is dead. 78303231Sdim class IndexRange : public std::pair<IndexType,IndexType> { 79303231Sdim public: 80314564Sdim IndexRange() = default; 81303231Sdim IndexRange(IndexType Start, IndexType End, bool F = false, bool T = false) 82303231Sdim : std::pair<IndexType,IndexType>(Start, End), Fixed(F), TiedEnd(T) {} 83314564Sdim 84303231Sdim IndexType start() const { return first; } 85303231Sdim IndexType end() const { return second; } 86303231Sdim 87303231Sdim bool operator< (const IndexRange &A) const { 88303231Sdim return start() < A.start(); 89303231Sdim } 90314564Sdim 91303231Sdim bool overlaps(const IndexRange &A) const; 92303231Sdim bool contains(const IndexRange &A) const; 93303231Sdim void merge(const IndexRange &A); 94303231Sdim 95314564Sdim bool Fixed = false; // Can be renamed? "Fixed" means "no". 96314564Sdim bool TiedEnd = false; // The end is not a use, but a dead def tied to a use. 97303231Sdim 98303231Sdim private: 99303231Sdim void setStart(const IndexType &S) { first = S; } 100303231Sdim void setEnd(const IndexType &E) { second = E; } 101303231Sdim }; 102303231Sdim 103303231Sdim // A list of index ranges. This represents liveness of a register 104303231Sdim // in a basic block. 105303231Sdim class RangeList : public std::vector<IndexRange> { 106303231Sdim public: 107303231Sdim void add(IndexType Start, IndexType End, bool Fixed, bool TiedEnd) { 108303231Sdim push_back(IndexRange(Start, End, Fixed, TiedEnd)); 109303231Sdim } 110303231Sdim void add(const IndexRange &Range) { 111303231Sdim push_back(Range); 112303231Sdim } 113314564Sdim 114303231Sdim void include(const RangeList &RL); 115303231Sdim void unionize(bool MergeAdjacent = false); 116303231Sdim void subtract(const IndexRange &Range); 117303231Sdim 118303231Sdim private: 119303231Sdim void addsub(const IndexRange &A, const IndexRange &B); 120303231Sdim }; 121303231Sdim 122303231Sdim class InstrIndexMap { 123303231Sdim public: 124303231Sdim InstrIndexMap(MachineBasicBlock &B); 125314564Sdim 126303231Sdim MachineInstr *getInstr(IndexType Idx) const; 127303231Sdim IndexType getIndex(MachineInstr *MI) const; 128303231Sdim MachineBasicBlock &getBlock() const { return Block; } 129303231Sdim IndexType getPrevIndex(IndexType Idx) const; 130303231Sdim IndexType getNextIndex(IndexType Idx) const; 131303231Sdim void replaceInstr(MachineInstr *OldMI, MachineInstr *NewMI); 132303231Sdim 133303231Sdim friend raw_ostream &operator<< (raw_ostream &OS, const InstrIndexMap &Map); 134314564Sdim 135303231Sdim IndexType First, Last; 136303231Sdim 137303231Sdim private: 138303231Sdim MachineBasicBlock &Block; 139303231Sdim std::map<IndexType,MachineInstr*> Map; 140303231Sdim }; 141303231Sdim 142327952Sdim using RegToRangeMap = std::map<RegisterRef, RangeList>; 143327952Sdim 144303231Sdim RegToRangeMap computeLiveMap(InstrIndexMap &IndexMap); 145303231Sdim RegToRangeMap computeDeadMap(InstrIndexMap &IndexMap, RegToRangeMap &LiveMap); 146303231Sdim static RegisterSet expandToSubRegs(RegisterRef R, 147303231Sdim const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI); 148303231Sdim 149303231Sdim struct PrintRangeMap { 150303231Sdim PrintRangeMap(const RegToRangeMap &M, const TargetRegisterInfo &I) 151303231Sdim : Map(M), TRI(I) {} 152303231Sdim 153303231Sdim friend raw_ostream &operator<< (raw_ostream &OS, const PrintRangeMap &P); 154314564Sdim 155303231Sdim private: 156303231Sdim const RegToRangeMap ⤅ 157303231Sdim const TargetRegisterInfo &TRI; 158303231Sdim }; 159303231Sdim 160303231Sdimprivate: 161314564Sdim RegisterSet getLiveIns(const MachineBasicBlock &B, 162314564Sdim const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI); 163303231Sdim 164303231Sdim void computeInitialLiveRanges(InstrIndexMap &IndexMap, 165303231Sdim RegToRangeMap &LiveMap); 166303231Sdim 167303231Sdim MachineFunction &MF; 168303231Sdim const HexagonSubtarget &HST; 169303231Sdim const TargetInstrInfo &TII; 170303231Sdim const TargetRegisterInfo &TRI; 171303231Sdim BitVector Reserved; 172303231Sdim}; 173303231Sdim 174303231Sdiminline HexagonBlockRanges::IndexType::operator unsigned() const { 175303231Sdim assert(Index >= First); 176303231Sdim return Index; 177303231Sdim} 178303231Sdim 179303231Sdiminline bool HexagonBlockRanges::IndexType::operator== (unsigned x) const { 180303231Sdim return Index == x; 181303231Sdim} 182303231Sdim 183303231Sdiminline bool HexagonBlockRanges::IndexType::operator== (IndexType Idx) const { 184303231Sdim return Index == Idx.Index; 185303231Sdim} 186303231Sdim 187303231Sdiminline bool HexagonBlockRanges::IndexType::operator!= (unsigned x) const { 188303231Sdim return Index != x; 189303231Sdim} 190303231Sdim 191303231Sdiminline bool HexagonBlockRanges::IndexType::operator!= (IndexType Idx) const { 192303231Sdim return Index != Idx.Index; 193303231Sdim} 194303231Sdim 195303231Sdiminline 196303231SdimHexagonBlockRanges::IndexType HexagonBlockRanges::IndexType::operator++ () { 197303231Sdim assert(Index != None); 198303231Sdim assert(Index != Exit); 199303231Sdim if (Index == Entry) 200303231Sdim Index = First; 201303231Sdim else 202303231Sdim ++Index; 203303231Sdim return *this; 204303231Sdim} 205303231Sdim 206303231Sdiminline bool HexagonBlockRanges::IndexType::operator< (unsigned Idx) const { 207303231Sdim return operator< (IndexType(Idx)); 208303231Sdim} 209303231Sdim 210303231Sdiminline bool HexagonBlockRanges::IndexType::operator< (IndexType Idx) const { 211303231Sdim // !(x < x). 212303231Sdim if (Index == Idx.Index) 213303231Sdim return false; 214303231Sdim // !(None < x) for all x. 215303231Sdim // !(x < None) for all x. 216303231Sdim if (Index == None || Idx.Index == None) 217303231Sdim return false; 218303231Sdim // !(Exit < x) for all x. 219303231Sdim // !(x < Entry) for all x. 220303231Sdim if (Index == Exit || Idx.Index == Entry) 221303231Sdim return false; 222303231Sdim // Entry < x for all x != Entry. 223303231Sdim // x < Exit for all x != Exit. 224303231Sdim if (Index == Entry || Idx.Index == Exit) 225303231Sdim return true; 226303231Sdim 227303231Sdim return Index < Idx.Index; 228303231Sdim} 229303231Sdim 230303231Sdiminline bool HexagonBlockRanges::IndexType::operator<= (IndexType Idx) const { 231303231Sdim return operator==(Idx) || operator<(Idx); 232303231Sdim} 233303231Sdim 234303231Sdimraw_ostream &operator<< (raw_ostream &OS, HexagonBlockRanges::IndexType Idx); 235303231Sdimraw_ostream &operator<< (raw_ostream &OS, 236303231Sdim const HexagonBlockRanges::IndexRange &IR); 237303231Sdimraw_ostream &operator<< (raw_ostream &OS, 238303231Sdim const HexagonBlockRanges::RangeList &RL); 239303231Sdimraw_ostream &operator<< (raw_ostream &OS, 240303231Sdim const HexagonBlockRanges::InstrIndexMap &M); 241303231Sdimraw_ostream &operator<< (raw_ostream &OS, 242303231Sdim const HexagonBlockRanges::PrintRangeMap &P); 243303231Sdim 244314564Sdim} // end namespace llvm 245303231Sdim 246327952Sdim#endif // LLVM_LIB_TARGET_HEXAGON_HEXAGONBLOCKRANGES_H 247