1//===---- LiveRangeCalc.h - Calculate live ranges ---------------*- 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// The LiveRangeCalc class can be used to compute live ranges from scratch.  It
11// caches information about values in the CFG to speed up repeated operations
12// on the same live range.  The cache can be shared by non-overlapping live
13// ranges.  SplitKit uses that when computing the live range of split products.
14//
15// A low-level interface is available to clients that know where a variable is
16// live, but don't know which value it has as every point.  LiveRangeCalc will
17// propagate values down the dominator tree, and even insert PHI-defs where
18// needed.  SplitKit uses this faster interface when possible.
19//
20//===----------------------------------------------------------------------===//
21
22#ifndef LLVM_CODEGEN_LIVERANGECALC_H
23#define LLVM_CODEGEN_LIVERANGECALC_H
24
25#include "llvm/ADT/BitVector.h"
26#include "llvm/ADT/IndexedMap.h"
27#include "llvm/CodeGen/LiveInterval.h"
28
29namespace llvm {
30
31/// Forward declarations for MachineDominators.h:
32class MachineDominatorTree;
33template <class NodeT> class DomTreeNodeBase;
34typedef DomTreeNodeBase<MachineBasicBlock> MachineDomTreeNode;
35
36class LiveRangeCalc {
37  const MachineFunction *MF;
38  const MachineRegisterInfo *MRI;
39  SlotIndexes *Indexes;
40  MachineDominatorTree *DomTree;
41  VNInfo::Allocator *Alloc;
42
43  /// Seen - Bit vector of active entries in LiveOut, also used as a visited
44  /// set by findReachingDefs.  One entry per basic block, indexed by block
45  /// number.  This is kept as a separate bit vector because it can be cleared
46  /// quickly when switching live ranges.
47  BitVector Seen;
48
49  /// LiveOutPair - A value and the block that defined it.  The domtree node is
50  /// redundant, it can be computed as: MDT[Indexes.getMBBFromIndex(VNI->def)].
51  typedef std::pair<VNInfo*, MachineDomTreeNode*> LiveOutPair;
52
53  /// LiveOutMap - Map basic blocks to the value leaving the block.
54  typedef IndexedMap<LiveOutPair, MBB2NumberFunctor> LiveOutMap;
55
56  /// LiveOut - Map each basic block where a live range is live out to the
57  /// live-out value and its defining block.
58  ///
59  /// For every basic block, MBB, one of these conditions shall be true:
60  ///
61  ///  1. !Seen.count(MBB->getNumber())
62  ///     Blocks without a Seen bit are ignored.
63  ///  2. LiveOut[MBB].second.getNode() == MBB
64  ///     The live-out value is defined in MBB.
65  ///  3. forall P in preds(MBB): LiveOut[P] == LiveOut[MBB]
66  ///     The live-out value passses through MBB. All predecessors must carry
67  ///     the same value.
68  ///
69  /// The domtree node may be null, it can be computed.
70  ///
71  /// The map can be shared by multiple live ranges as long as no two are
72  /// live-out of the same block.
73  LiveOutMap LiveOut;
74
75  /// LiveInBlock - Information about a basic block where a live range is known
76  /// to be live-in, but the value has not yet been determined.
77  struct LiveInBlock {
78    // The live range set that is live-in to this block.  The algorithms can
79    // handle multiple non-overlapping live ranges simultaneously.
80    LiveRange &LR;
81
82    // DomNode - Dominator tree node for the block.
83    // Cleared when the final value has been determined and LI has been updated.
84    MachineDomTreeNode *DomNode;
85
86    // Position in block where the live-in range ends, or SlotIndex() if the
87    // range passes through the block.  When the final value has been
88    // determined, the range from the block start to Kill will be added to LI.
89    SlotIndex Kill;
90
91    // Live-in value filled in by updateSSA once it is known.
92    VNInfo *Value;
93
94    LiveInBlock(LiveRange &LR, MachineDomTreeNode *node, SlotIndex kill)
95      : LR(LR), DomNode(node), Kill(kill), Value(nullptr) {}
96  };
97
98  /// LiveIn - Work list of blocks where the live-in value has yet to be
99  /// determined.  This list is typically computed by findReachingDefs() and
100  /// used as a work list by updateSSA().  The low-level interface may also be
101  /// used to add entries directly.
102  SmallVector<LiveInBlock, 16> LiveIn;
103
104  /// Assuming that LI is live-in to KillMBB and killed at Kill, find the set
105  /// of defs that can reach it.
106  ///
107  /// If only one def can reach Kill, all paths from the def to kill are added
108  /// to LI, and the function returns true.
109  ///
110  /// If multiple values can reach Kill, the blocks that need LI to be live in
111  /// are added to the LiveIn array, and the function returns false.
112  ///
113  /// PhysReg, when set, is used to verify live-in lists on basic blocks.
114  bool findReachingDefs(LiveRange &LR, MachineBasicBlock &KillMBB,
115                        SlotIndex Kill, unsigned PhysReg);
116
117  /// updateSSA - Compute the values that will be live in to all requested
118  /// blocks in LiveIn.  Create PHI-def values as required to preserve SSA form.
119  ///
120  /// Every live-in block must be jointly dominated by the added live-out
121  /// blocks.  No values are read from the live ranges.
122  void updateSSA();
123
124  /// Add liveness as specified in the LiveIn vector.
125  void updateLiveIns();
126
127public:
128  LiveRangeCalc() : MF(nullptr), MRI(nullptr), Indexes(nullptr),
129                    DomTree(nullptr), Alloc(nullptr) {}
130
131  //===--------------------------------------------------------------------===//
132  // High-level interface.
133  //===--------------------------------------------------------------------===//
134  //
135  // Calculate live ranges from scratch.
136  //
137
138  /// reset - Prepare caches for a new set of non-overlapping live ranges.  The
139  /// caches must be reset before attempting calculations with a live range
140  /// that may overlap a previously computed live range, and before the first
141  /// live range in a function.  If live ranges are not known to be
142  /// non-overlapping, call reset before each.
143  void reset(const MachineFunction *MF,
144             SlotIndexes*,
145             MachineDominatorTree*,
146             VNInfo::Allocator*);
147
148  //===--------------------------------------------------------------------===//
149  // Mid-level interface.
150  //===--------------------------------------------------------------------===//
151  //
152  // Modify existing live ranges.
153  //
154
155  /// extend - Extend the live range of LI to reach Kill.
156  ///
157  /// The existing values in LI must be live so they jointly dominate Kill.  If
158  /// Kill is not dominated by a single existing value, PHI-defs are inserted
159  /// as required to preserve SSA form.  If Kill is known to be dominated by a
160  /// single existing value, Alloc may be null.
161  ///
162  /// PhysReg, when set, is used to verify live-in lists on basic blocks.
163  void extend(LiveRange &LR, SlotIndex Kill, unsigned PhysReg = 0);
164
165  /// createDeadDefs - Create a dead def in LI for every def operand of Reg.
166  /// Each instruction defining Reg gets a new VNInfo with a corresponding
167  /// minimal live range.
168  void createDeadDefs(LiveRange &LR, unsigned Reg);
169
170  /// createDeadDefs - Create a dead def in LI for every def of LI->reg.
171  void createDeadDefs(LiveInterval &LI) {
172    createDeadDefs(LI, LI.reg);
173  }
174
175  /// extendToUses - Extend the live range of LI to reach all uses of Reg.
176  ///
177  /// All uses must be jointly dominated by existing liveness.  PHI-defs are
178  /// inserted as needed to preserve SSA form.
179  void extendToUses(LiveRange &LR, unsigned Reg);
180
181  /// extendToUses - Extend the live range of LI to reach all uses of LI->reg.
182  void extendToUses(LiveInterval &LI) {
183    extendToUses(LI, LI.reg);
184  }
185
186  //===--------------------------------------------------------------------===//
187  // Low-level interface.
188  //===--------------------------------------------------------------------===//
189  //
190  // These functions can be used to compute live ranges where the live-in and
191  // live-out blocks are already known, but the SSA value in each block is
192  // unknown.
193  //
194  // After calling reset(), add known live-out values and known live-in blocks.
195  // Then call calculateValues() to compute the actual value that is
196  // live-in to each block, and add liveness to the live ranges.
197  //
198
199  /// setLiveOutValue - Indicate that VNI is live out from MBB.  The
200  /// calculateValues() function will not add liveness for MBB, the caller
201  /// should take care of that.
202  ///
203  /// VNI may be null only if MBB is a live-through block also passed to
204  /// addLiveInBlock().
205  void setLiveOutValue(MachineBasicBlock *MBB, VNInfo *VNI) {
206    Seen.set(MBB->getNumber());
207    LiveOut[MBB] = LiveOutPair(VNI, nullptr);
208  }
209
210  /// addLiveInBlock - Add a block with an unknown live-in value.  This
211  /// function can only be called once per basic block.  Once the live-in value
212  /// has been determined, calculateValues() will add liveness to LI.
213  ///
214  /// @param LR      The live range that is live-in to the block.
215  /// @param DomNode The domtree node for the block.
216  /// @param Kill    Index in block where LI is killed.  If the value is
217  ///                live-through, set Kill = SLotIndex() and also call
218  ///                setLiveOutValue(MBB, 0).
219  void addLiveInBlock(LiveRange &LR,
220                      MachineDomTreeNode *DomNode,
221                      SlotIndex Kill = SlotIndex()) {
222    LiveIn.push_back(LiveInBlock(LR, DomNode, Kill));
223  }
224
225  /// calculateValues - Calculate the value that will be live-in to each block
226  /// added with addLiveInBlock.  Add PHI-def values as needed to preserve SSA
227  /// form.  Add liveness to all live-in blocks up to the Kill point, or the
228  /// whole block for live-through blocks.
229  ///
230  /// Every predecessor of a live-in block must have been given a value with
231  /// setLiveOutValue, the value may be null for live-trough blocks.
232  void calculateValues();
233};
234
235} // end namespace llvm
236
237#endif
238