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