1//===- llvm/CodeGen/LivePhysRegs.h - Live Physical Register Set -*- 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 implements the LivePhysRegs utility for tracking liveness of
11// physical registers. This can be used for ad-hoc liveness tracking after
12// register allocation. You can start with the live-ins/live-outs at the
13// beginning/end of a block and update the information while walking the
14// instructions inside the block. This implementation tracks the liveness on a
15// sub-register granularity.
16//
17// We assume that the high bits of a physical super-register are not preserved
18// unless the instruction has an implicit-use operand reading the super-
19// register.
20//
21// X86 Example:
22// %YMM0<def> = ...
23// %XMM0<def> = ... (Kills %XMM0, all %XMM0s sub-registers, and %YMM0)
24//
25// %YMM0<def> = ...
26// %XMM0<def> = ..., %YMM0<imp-use> (%YMM0 and all its sub-registers are alive)
27//===----------------------------------------------------------------------===//
28
29#ifndef LLVM_CODEGEN_LIVEPHYSREGS_H
30#define LLVM_CODEGEN_LIVEPHYSREGS_H
31
32#include "llvm/ADT/SparseSet.h"
33#include "llvm/CodeGen/MachineBasicBlock.h"
34#include "llvm/Target/TargetRegisterInfo.h"
35#include <cassert>
36
37namespace llvm {
38
39class MachineInstr;
40
41/// \brief A set of live physical registers with functions to track liveness
42/// when walking backward/forward through a basic block.
43class LivePhysRegs {
44  const TargetRegisterInfo *TRI;
45  SparseSet<unsigned> LiveRegs;
46
47  LivePhysRegs(const LivePhysRegs&) = delete;
48  LivePhysRegs &operator=(const LivePhysRegs&) = delete;
49public:
50  /// \brief Constructs a new empty LivePhysRegs set.
51  LivePhysRegs() : TRI(nullptr), LiveRegs() {}
52
53  /// \brief Constructs and initialize an empty LivePhysRegs set.
54  LivePhysRegs(const TargetRegisterInfo *TRI) : TRI(TRI) {
55    assert(TRI && "Invalid TargetRegisterInfo pointer.");
56    LiveRegs.setUniverse(TRI->getNumRegs());
57  }
58
59  /// \brief Clear and initialize the LivePhysRegs set.
60  void init(const TargetRegisterInfo *TRI) {
61    assert(TRI && "Invalid TargetRegisterInfo pointer.");
62    this->TRI = TRI;
63    LiveRegs.clear();
64    LiveRegs.setUniverse(TRI->getNumRegs());
65  }
66
67  /// \brief Clears the LivePhysRegs set.
68  void clear() { LiveRegs.clear(); }
69
70  /// \brief Returns true if the set is empty.
71  bool empty() const { return LiveRegs.empty(); }
72
73  /// \brief Adds a physical register and all its sub-registers to the set.
74  void addReg(unsigned Reg) {
75    assert(TRI && "LivePhysRegs is not initialized.");
76    assert(Reg <= TRI->getNumRegs() && "Expected a physical register.");
77    for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
78         SubRegs.isValid(); ++SubRegs)
79      LiveRegs.insert(*SubRegs);
80  }
81
82  /// \brief Removes a physical register, all its sub-registers, and all its
83  /// super-registers from the set.
84  void removeReg(unsigned Reg) {
85    assert(TRI && "LivePhysRegs is not initialized.");
86    assert(Reg <= TRI->getNumRegs() && "Expected a physical register.");
87    for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true);
88         SubRegs.isValid(); ++SubRegs)
89      LiveRegs.erase(*SubRegs);
90    for (MCSuperRegIterator SuperRegs(Reg, TRI, /*IncludeSelf=*/false);
91         SuperRegs.isValid(); ++SuperRegs)
92      LiveRegs.erase(*SuperRegs);
93  }
94
95  /// \brief Removes physical registers clobbered by the regmask operand @p MO.
96  void removeRegsInMask(const MachineOperand &MO);
97
98  /// \brief Returns true if register @p Reg is contained in the set. This also
99  /// works if only the super register of @p Reg has been defined, because we
100  /// always add also all sub-registers to the set.
101  bool contains(unsigned Reg) const { return LiveRegs.count(Reg); }
102
103  /// \brief Simulates liveness when stepping backwards over an
104  /// instruction(bundle): Remove Defs, add uses. This is the recommended way of
105  /// calculating liveness.
106  void stepBackward(const MachineInstr &MI);
107
108  /// \brief Simulates liveness when stepping forward over an
109  /// instruction(bundle): Remove killed-uses, add defs. This is the not
110  /// recommended way, because it depends on accurate kill flags. If possible
111  /// use stepBackwards() instead of this function.
112  void stepForward(const MachineInstr &MI);
113
114  /// \brief Adds all live-in registers of basic block @p MBB.
115  void addLiveIns(const MachineBasicBlock *MBB) {
116    for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(),
117         LE = MBB->livein_end(); LI != LE; ++LI)
118      addReg(*LI);
119  }
120
121  /// \brief Adds all live-out registers of basic block @p MBB.
122  void addLiveOuts(const MachineBasicBlock *MBB) {
123    for (MachineBasicBlock::const_succ_iterator SI = MBB->succ_begin(),
124         SE = MBB->succ_end(); SI != SE; ++SI)
125      addLiveIns(*SI);
126  }
127
128  typedef SparseSet<unsigned>::const_iterator const_iterator;
129  const_iterator begin() const { return LiveRegs.begin(); }
130  const_iterator end() const { return LiveRegs.end(); }
131
132  /// \brief Prints the currently live registers to @p OS.
133  void print(raw_ostream &OS) const;
134
135  /// \brief Dumps the currently live registers to the debug output.
136  void dump() const;
137};
138
139inline raw_ostream &operator<<(raw_ostream &OS, const LivePhysRegs& LR) {
140  LR.print(OS);
141  return OS;
142}
143
144} // namespace llvm
145
146#endif
147