250 lines · c
1//===- HexagonBlockRanges.h -------------------------------------*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef LLVM_LIB_TARGET_HEXAGON_HEXAGONBLOCKRANGES_H10#define LLVM_LIB_TARGET_HEXAGON_HEXAGONBLOCKRANGES_H11 12#include "llvm/ADT/BitVector.h"13#include "llvm/CodeGen/Register.h"14#include <cassert>15#include <map>16#include <set>17#include <utility>18#include <vector>19 20namespace llvm {21 22class HexagonSubtarget;23class MachineBasicBlock;24class MachineFunction;25class MachineInstr;26class MachineRegisterInfo;27class raw_ostream;28class TargetInstrInfo;29class TargetRegisterInfo;30 31struct HexagonBlockRanges {32 HexagonBlockRanges(MachineFunction &MF);33 34 // FIXME: Consolidate duplicate definitions of RegisterRef35 struct RegisterRef {36 llvm::Register Reg;37 unsigned Sub;38 39 bool operator<(RegisterRef R) const {40 return std::tie(Reg, Sub) < std::tie(R.Reg, R.Sub);41 }42 };43 using RegisterSet = std::set<RegisterRef>;44 45 // This is to represent an "index", which is an abstraction of a position46 // of an instruction within a basic block.47 class IndexType {48 public:49 enum : unsigned {50 None = 0,51 Entry = 1,52 Exit = 2,53 First = 11 // 10th + 1st54 };55 56 IndexType() {}57 IndexType(unsigned Idx) : Index(Idx) {}58 59 static bool isInstr(IndexType X) { return X.Index >= First; }60 61 operator unsigned() const;62 bool operator== (unsigned x) const;63 bool operator== (IndexType Idx) const;64 bool operator!= (unsigned x) const;65 bool operator!= (IndexType Idx) const;66 IndexType operator++ ();67 bool operator< (unsigned Idx) const;68 bool operator< (IndexType Idx) const;69 bool operator<= (IndexType Idx) const;70 71 private:72 bool operator> (IndexType Idx) const;73 bool operator>= (IndexType Idx) const;74 75 unsigned Index = None;76 };77 78 // A range of indices, essentially a representation of a live range.79 // This is also used to represent "dead ranges", i.e. ranges where a80 // register is dead.81 class IndexRange : public std::pair<IndexType,IndexType> {82 public:83 IndexRange() = default;84 IndexRange(IndexType Start, IndexType End, bool F = false, bool T = false)85 : std::pair<IndexType,IndexType>(Start, End), Fixed(F), TiedEnd(T) {}86 87 IndexType start() const { return first; }88 IndexType end() const { return second; }89 90 bool operator< (const IndexRange &A) const {91 return start() < A.start();92 }93 94 bool overlaps(const IndexRange &A) const;95 bool contains(const IndexRange &A) const;96 void merge(const IndexRange &A);97 98 bool Fixed = false; // Can be renamed? "Fixed" means "no".99 bool TiedEnd = false; // The end is not a use, but a dead def tied to a use.100 101 private:102 void setStart(const IndexType &S) { first = S; }103 void setEnd(const IndexType &E) { second = E; }104 };105 106 // A list of index ranges. This represents liveness of a register107 // in a basic block.108 class RangeList : public std::vector<IndexRange> {109 public:110 void add(IndexType Start, IndexType End, bool Fixed, bool TiedEnd) {111 push_back(IndexRange(Start, End, Fixed, TiedEnd));112 }113 void add(const IndexRange &Range) {114 push_back(Range);115 }116 117 void include(const RangeList &RL);118 void unionize(bool MergeAdjacent = false);119 void subtract(const IndexRange &Range);120 121 private:122 void addsub(const IndexRange &A, const IndexRange &B);123 };124 125 class InstrIndexMap {126 public:127 InstrIndexMap(MachineBasicBlock &B);128 129 MachineInstr *getInstr(IndexType Idx) const;130 IndexType getIndex(MachineInstr *MI) const;131 MachineBasicBlock &getBlock() const { return Block; }132 IndexType getPrevIndex(IndexType Idx) const;133 IndexType getNextIndex(IndexType Idx) const;134 void replaceInstr(MachineInstr *OldMI, MachineInstr *NewMI);135 136 friend raw_ostream &operator<< (raw_ostream &OS, const InstrIndexMap &Map);137 138 IndexType First, Last;139 140 private:141 MachineBasicBlock &Block;142 std::map<IndexType,MachineInstr*> Map;143 };144 145 using RegToRangeMap = std::map<RegisterRef, RangeList>;146 147 RegToRangeMap computeLiveMap(InstrIndexMap &IndexMap);148 RegToRangeMap computeDeadMap(InstrIndexMap &IndexMap, RegToRangeMap &LiveMap);149 static RegisterSet expandToSubRegs(RegisterRef R,150 const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI);151 152 struct PrintRangeMap {153 PrintRangeMap(const RegToRangeMap &M, const TargetRegisterInfo &I)154 : Map(M), TRI(I) {}155 156 friend raw_ostream &operator<< (raw_ostream &OS, const PrintRangeMap &P);157 158 private:159 const RegToRangeMap ⤅160 const TargetRegisterInfo &TRI;161 };162 163private:164 RegisterSet getLiveIns(const MachineBasicBlock &B,165 const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI);166 167 void computeInitialLiveRanges(InstrIndexMap &IndexMap,168 RegToRangeMap &LiveMap);169 170 MachineFunction &MF;171 const HexagonSubtarget &HST;172 const TargetInstrInfo &TII;173 const TargetRegisterInfo &TRI;174 BitVector Reserved;175};176 177inline HexagonBlockRanges::IndexType::operator unsigned() const {178 assert(Index >= First);179 return Index;180}181 182inline bool HexagonBlockRanges::IndexType::operator== (unsigned x) const {183 return Index == x;184}185 186inline bool HexagonBlockRanges::IndexType::operator== (IndexType Idx) const {187 return Index == Idx.Index;188}189 190inline bool HexagonBlockRanges::IndexType::operator!= (unsigned x) const {191 return Index != x;192}193 194inline bool HexagonBlockRanges::IndexType::operator!= (IndexType Idx) const {195 return Index != Idx.Index;196}197 198inline199HexagonBlockRanges::IndexType HexagonBlockRanges::IndexType::operator++ () {200 assert(Index != None);201 assert(Index != Exit);202 if (Index == Entry)203 Index = First;204 else205 ++Index;206 return *this;207}208 209inline bool HexagonBlockRanges::IndexType::operator< (unsigned Idx) const {210 return operator< (IndexType(Idx));211}212 213inline bool HexagonBlockRanges::IndexType::operator< (IndexType Idx) const {214 // !(x < x).215 if (Index == Idx.Index)216 return false;217 // !(None < x) for all x.218 // !(x < None) for all x.219 if (Index == None || Idx.Index == None)220 return false;221 // !(Exit < x) for all x.222 // !(x < Entry) for all x.223 if (Index == Exit || Idx.Index == Entry)224 return false;225 // Entry < x for all x != Entry.226 // x < Exit for all x != Exit.227 if (Index == Entry || Idx.Index == Exit)228 return true;229 230 return Index < Idx.Index;231}232 233inline bool HexagonBlockRanges::IndexType::operator<= (IndexType Idx) const {234 return operator==(Idx) || operator<(Idx);235}236 237raw_ostream &operator<< (raw_ostream &OS, HexagonBlockRanges::IndexType Idx);238raw_ostream &operator<< (raw_ostream &OS,239 const HexagonBlockRanges::IndexRange &IR);240raw_ostream &operator<< (raw_ostream &OS,241 const HexagonBlockRanges::RangeList &RL);242raw_ostream &operator<< (raw_ostream &OS,243 const HexagonBlockRanges::InstrIndexMap &M);244raw_ostream &operator<< (raw_ostream &OS,245 const HexagonBlockRanges::PrintRangeMap &P);246 247} // end namespace llvm248 249#endif // LLVM_LIB_TARGET_HEXAGON_HEXAGONBLOCKRANGES_H250