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