1//===-- RegisterScavenging.h - Machine register scavenging ------*- C++ -*-===//
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//
10// This file declares the machine register scavenger class. It can provide
11// information such as unused register at any point in a machine basic block.
12// It also provides a mechanism to make registers availbale by evicting them
13// to spill slots.
14//
15//===----------------------------------------------------------------------===//
16
17#ifndef LLVM_CODEGEN_REGISTERSCAVENGING_H
18#define LLVM_CODEGEN_REGISTERSCAVENGING_H
19
20#include "llvm/ADT/BitVector.h"
21#include "llvm/CodeGen/MachineBasicBlock.h"
22#include "llvm/CodeGen/MachineRegisterInfo.h"
23
24namespace llvm {
25
26class MachineRegisterInfo;
27class TargetRegisterInfo;
28class TargetInstrInfo;
29class TargetRegisterClass;
30
31class RegScavenger {
32  const TargetRegisterInfo *TRI;
33  const TargetInstrInfo *TII;
34  MachineRegisterInfo* MRI;
35  MachineBasicBlock *MBB;
36  MachineBasicBlock::iterator MBBI;
37  unsigned NumRegUnits;
38
39  /// Tracking - True if RegScavenger is currently tracking the liveness of
40  /// registers.
41  bool Tracking;
42
43  /// Information on scavenged registers (held in a spill slot).
44  struct ScavengedInfo {
45    ScavengedInfo(int FI = -1) : FrameIndex(FI), Reg(0), Restore(nullptr) {}
46
47    /// A spill slot used for scavenging a register post register allocation.
48    int FrameIndex;
49
50    /// If non-zero, the specific register is currently being
51    /// scavenged. That is, it is spilled to this scavenging stack slot.
52    unsigned Reg;
53
54    /// The instruction that restores the scavenged register from stack.
55    const MachineInstr *Restore;
56  };
57
58  /// A vector of information on scavenged registers.
59  SmallVector<ScavengedInfo, 2> Scavenged;
60
61  /// RegUnitsAvailable - The current state of each reg unit immediatelly
62  /// before MBBI. One bit per register unit. If bit is not set it means any
63  /// register containing that register unit is currently being used.
64  BitVector RegUnitsAvailable;
65
66  // These BitVectors are only used internally to forward(). They are members
67  // to avoid frequent reallocations.
68  BitVector KillRegUnits, DefRegUnits;
69  BitVector TmpRegUnits;
70
71public:
72  RegScavenger()
73    : MBB(nullptr), NumRegUnits(0), Tracking(false) {}
74
75  /// enterBasicBlock - Start tracking liveness from the begin of the specific
76  /// basic block.
77  void enterBasicBlock(MachineBasicBlock *mbb);
78
79  /// initRegState - allow resetting register state info for multiple
80  /// passes over/within the same function.
81  void initRegState();
82
83  /// forward - Move the internal MBB iterator and update register states.
84  void forward();
85
86  /// forward - Move the internal MBB iterator and update register states until
87  /// it has processed the specific iterator.
88  void forward(MachineBasicBlock::iterator I) {
89    if (!Tracking && MBB->begin() != I) forward();
90    while (MBBI != I) forward();
91  }
92
93  /// Invert the behavior of forward() on the current instruction (undo the
94  /// changes to the available registers made by forward()).
95  void unprocess();
96
97  /// Unprocess instructions until you reach the provided iterator.
98  void unprocess(MachineBasicBlock::iterator I) {
99    while (MBBI != I) unprocess();
100  }
101
102  /// skipTo - Move the internal MBB iterator but do not update register states.
103  void skipTo(MachineBasicBlock::iterator I) {
104    if (I == MachineBasicBlock::iterator(nullptr))
105      Tracking = false;
106    MBBI = I;
107  }
108
109  MachineBasicBlock::iterator getCurrentPosition() const {
110    return MBBI;
111  }
112
113  /// isRegUsed - return if a specific register is currently used.
114  bool isRegUsed(unsigned Reg, bool includeReserved = true) const;
115
116  /// getRegsAvailable - Return all available registers in the register class
117  /// in Mask.
118  BitVector getRegsAvailable(const TargetRegisterClass *RC);
119
120  /// FindUnusedReg - Find a unused register of the specified register class.
121  /// Return 0 if none is found.
122  unsigned FindUnusedReg(const TargetRegisterClass *RegClass) const;
123
124  /// Add a scavenging frame index.
125  void addScavengingFrameIndex(int FI) {
126    Scavenged.push_back(ScavengedInfo(FI));
127  }
128
129  /// Query whether a frame index is a scavenging frame index.
130  bool isScavengingFrameIndex(int FI) const {
131    for (SmallVectorImpl<ScavengedInfo>::const_iterator I = Scavenged.begin(),
132         IE = Scavenged.end(); I != IE; ++I)
133      if (I->FrameIndex == FI)
134        return true;
135
136    return false;
137  }
138
139  /// Get an array of scavenging frame indices.
140  void getScavengingFrameIndices(SmallVectorImpl<int> &A) const {
141    for (SmallVectorImpl<ScavengedInfo>::const_iterator I = Scavenged.begin(),
142         IE = Scavenged.end(); I != IE; ++I)
143      if (I->FrameIndex >= 0)
144        A.push_back(I->FrameIndex);
145  }
146
147  /// scavengeRegister - Make a register of the specific register class
148  /// available and do the appropriate bookkeeping. SPAdj is the stack
149  /// adjustment due to call frame, it's passed along to eliminateFrameIndex().
150  /// Returns the scavenged register.
151  unsigned scavengeRegister(const TargetRegisterClass *RegClass,
152                            MachineBasicBlock::iterator I, int SPAdj);
153  unsigned scavengeRegister(const TargetRegisterClass *RegClass, int SPAdj) {
154    return scavengeRegister(RegClass, MBBI, SPAdj);
155  }
156
157  /// setRegUsed - Tell the scavenger a register is used.
158  ///
159  void setRegUsed(unsigned Reg);
160private:
161  /// isReserved - Returns true if a register is reserved. It is never "unused".
162  bool isReserved(unsigned Reg) const { return MRI->isReserved(Reg); }
163
164  /// setUsed / setUnused - Mark the state of one or a number of register units.
165  ///
166  void setUsed(BitVector &RegUnits) {
167    RegUnitsAvailable.reset(RegUnits);
168  }
169  void setUnused(BitVector &RegUnits) {
170    RegUnitsAvailable |= RegUnits;
171  }
172
173  /// Processes the current instruction and fill the KillRegUnits and
174  /// DefRegUnits bit vectors.
175  void determineKillsAndDefs();
176
177  /// Add all Reg Units that Reg contains to BV.
178  void addRegUnits(BitVector &BV, unsigned Reg);
179
180  /// findSurvivorReg - Return the candidate register that is unused for the
181  /// longest after StartMI. UseMI is set to the instruction where the search
182  /// stopped.
183  ///
184  /// No more than InstrLimit instructions are inspected.
185  unsigned findSurvivorReg(MachineBasicBlock::iterator StartMI,
186                           BitVector &Candidates,
187                           unsigned InstrLimit,
188                           MachineBasicBlock::iterator &UseMI);
189
190};
191
192} // End llvm namespace
193
194#endif
195