LLVM  13.0.0git
LiveRangeCalc.h
Go to the documentation of this file.
1 //===- LiveRangeCalc.h - Calculate live ranges -----------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // The LiveRangeCalc class can be used to implement the computation of
10 // live ranges from scratch.
11 // It caches information about values in the CFG to speed up repeated
12 // operations on the same live range. The cache can be shared by
13 // non-overlapping live ranges. SplitKit uses that when computing the live
14 // range of split products.
15 //
16 // A low-level interface is available to clients that know where a variable is
17 // live, but don't know which value it has as every point. LiveRangeCalc will
18 // propagate values down the dominator tree, and even insert PHI-defs where
19 // needed. SplitKit uses this faster interface when possible.
20 //
21 //===----------------------------------------------------------------------===//
22 
23 #ifndef LLVM_CODEGEN_LIVERANGECALC_H
24 #define LLVM_CODEGEN_LIVERANGECALC_H
25 
26 #include "llvm/ADT/ArrayRef.h"
27 #include "llvm/ADT/BitVector.h"
28 #include "llvm/ADT/DenseMap.h"
29 #include "llvm/ADT/IndexedMap.h"
30 #include "llvm/ADT/SmallVector.h"
34 #include "llvm/MC/LaneBitmask.h"
35 #include <utility>
36 
37 namespace llvm {
38 
39 template <class NodeT> class DomTreeNodeBase;
40 class MachineDominatorTree;
41 class MachineFunction;
42 class MachineRegisterInfo;
43 
44 using MachineDomTreeNode = DomTreeNodeBase<MachineBasicBlock>;
45 
47  const MachineFunction *MF = nullptr;
48  const MachineRegisterInfo *MRI = nullptr;
49  SlotIndexes *Indexes = nullptr;
50  MachineDominatorTree *DomTree = nullptr;
51  VNInfo::Allocator *Alloc = nullptr;
52 
53  /// LiveOutPair - A value and the block that defined it. The domtree node is
54  /// redundant, it can be computed as: MDT[Indexes.getMBBFromIndex(VNI->def)].
55  using LiveOutPair = std::pair<VNInfo *, MachineDomTreeNode *>;
56 
57  /// LiveOutMap - Map basic blocks to the value leaving the block.
59 
60  /// Bit vector of active entries in LiveOut, also used as a visited set by
61  /// findReachingDefs. One entry per basic block, indexed by block number.
62  /// This is kept as a separate bit vector because it can be cleared quickly
63  /// when switching live ranges.
64  BitVector Seen;
65 
66  /// Map LiveRange to sets of blocks (represented by bit vectors) that
67  /// in the live range are defined on entry and undefined on entry.
68  /// A block is defined on entry if there is a path from at least one of
69  /// the defs in the live range to the entry of the block, and conversely,
70  /// a block is undefined on entry, if there is no such path (i.e. no
71  /// definition reaches the entry of the block). A single LiveRangeCalc
72  /// object is used to track live-out information for multiple registers
73  /// in live range splitting (which is ok, since the live ranges of these
74  /// registers do not overlap), but the defined/undefined information must
75  /// be kept separate for each individual range.
76  /// By convention, EntryInfoMap[&LR] = { Defined, Undefined }.
78  EntryInfoMap EntryInfos;
79 
80  /// Map each basic block where a live range is live out to the live-out value
81  /// and its defining block.
82  ///
83  /// For every basic block, MBB, one of these conditions shall be true:
84  ///
85  /// 1. !Seen.count(MBB->getNumber())
86  /// Blocks without a Seen bit are ignored.
87  /// 2. LiveOut[MBB].second.getNode() == MBB
88  /// The live-out value is defined in MBB.
89  /// 3. forall P in preds(MBB): LiveOut[P] == LiveOut[MBB]
90  /// The live-out value passses through MBB. All predecessors must carry
91  /// the same value.
92  ///
93  /// The domtree node may be null, it can be computed.
94  ///
95  /// The map can be shared by multiple live ranges as long as no two are
96  /// live-out of the same block.
97  LiveOutMap Map;
98 
99  /// LiveInBlock - Information about a basic block where a live range is known
100  /// to be live-in, but the value has not yet been determined.
101  struct LiveInBlock {
102  // The live range set that is live-in to this block. The algorithms can
103  // handle multiple non-overlapping live ranges simultaneously.
104  LiveRange &LR;
105 
106  // DomNode - Dominator tree node for the block.
107  // Cleared when the final value has been determined and LI has been updated.
108  MachineDomTreeNode *DomNode;
109 
110  // Position in block where the live-in range ends, or SlotIndex() if the
111  // range passes through the block. When the final value has been
112  // determined, the range from the block start to Kill will be added to LI.
113  SlotIndex Kill;
114 
115  // Live-in value filled in by updateSSA once it is known.
116  VNInfo *Value = nullptr;
117 
118  LiveInBlock(LiveRange &LR, MachineDomTreeNode *node, SlotIndex kill)
119  : LR(LR), DomNode(node), Kill(kill) {}
120  };
121 
122  /// LiveIn - Work list of blocks where the live-in value has yet to be
123  /// determined. This list is typically computed by findReachingDefs() and
124  /// used as a work list by updateSSA(). The low-level interface may also be
125  /// used to add entries directly.
127 
128  /// Check if the entry to block @p MBB can be reached by any of the defs
129  /// in @p LR. Return true if none of the defs reach the entry to @p MBB.
130  bool isDefOnEntry(LiveRange &LR, ArrayRef<SlotIndex> Undefs,
131  MachineBasicBlock &MBB, BitVector &DefOnEntry,
132  BitVector &UndefOnEntry);
133 
134  /// Find the set of defs that can reach @p Kill. @p Kill must belong to
135  /// @p UseMBB.
136  ///
137  /// If exactly one def can reach @p UseMBB, and the def dominates @p Kill,
138  /// all paths from the def to @p UseMBB are added to @p LR, and the function
139  /// returns true.
140  ///
141  /// If multiple values can reach @p UseMBB, the blocks that need @p LR to be
142  /// live in are added to the LiveIn array, and the function returns false.
143  ///
144  /// The array @p Undef provides the locations where the range @p LR becomes
145  /// undefined by <def,read-undef> operands on other subranges. If @p Undef
146  /// is non-empty and @p Kill is jointly dominated only by the entries of
147  /// @p Undef, the function returns false.
148  ///
149  /// PhysReg, when set, is used to verify live-in lists on basic blocks.
150  bool findReachingDefs(LiveRange &LR, MachineBasicBlock &UseMBB, SlotIndex Use,
151  unsigned PhysReg, ArrayRef<SlotIndex> Undefs);
152 
153  /// updateSSA - Compute the values that will be live in to all requested
154  /// blocks in LiveIn. Create PHI-def values as required to preserve SSA form.
155  ///
156  /// Every live-in block must be jointly dominated by the added live-out
157  /// blocks. No values are read from the live ranges.
158  void updateSSA();
159 
160  /// Transfer information from the LiveIn vector to the live ranges and update
161  /// the given @p LiveOuts.
162  void updateFromLiveIns();
163 
164 protected:
165  /// Some getters to expose in a read-only way some private fields to
166  /// subclasses.
167  const MachineFunction *getMachineFunction() { return MF; }
168  const MachineRegisterInfo *getRegInfo() const { return MRI; }
169  SlotIndexes *getIndexes() { return Indexes; }
170  MachineDominatorTree *getDomTree() { return DomTree; }
171  VNInfo::Allocator *getVNAlloc() { return Alloc; }
172 
173  /// Reset Map and Seen fields.
174  void resetLiveOutMap();
175 
176 public:
177  LiveRangeCalc() = default;
178 
179  //===--------------------------------------------------------------------===//
180  // High-level interface.
181  //===--------------------------------------------------------------------===//
182  //
183  // Calculate live ranges from scratch.
184  //
185 
186  /// reset - Prepare caches for a new set of non-overlapping live ranges. The
187  /// caches must be reset before attempting calculations with a live range
188  /// that may overlap a previously computed live range, and before the first
189  /// live range in a function. If live ranges are not known to be
190  /// non-overlapping, call reset before each.
191  void reset(const MachineFunction *mf, SlotIndexes *SI,
193 
194  //===--------------------------------------------------------------------===//
195  // Mid-level interface.
196  //===--------------------------------------------------------------------===//
197  //
198  // Modify existing live ranges.
199  //
200 
201  /// Extend the live range of @p LR to reach @p Use.
202  ///
203  /// The existing values in @p LR must be live so they jointly dominate @p Use.
204  /// If @p Use is not dominated by a single existing value, PHI-defs are
205  /// inserted as required to preserve SSA form.
206  ///
207  /// PhysReg, when set, is used to verify live-in lists on basic blocks.
208  void extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg,
209  ArrayRef<SlotIndex> Undefs);
210 
211  //===--------------------------------------------------------------------===//
212  // Low-level interface.
213  //===--------------------------------------------------------------------===//
214  //
215  // These functions can be used to compute live ranges where the live-in and
216  // live-out blocks are already known, but the SSA value in each block is
217  // unknown.
218  //
219  // After calling reset(), add known live-out values and known live-in blocks.
220  // Then call calculateValues() to compute the actual value that is
221  // live-in to each block, and add liveness to the live ranges.
222  //
223 
224  /// setLiveOutValue - Indicate that VNI is live out from MBB. The
225  /// calculateValues() function will not add liveness for MBB, the caller
226  /// should take care of that.
227  ///
228  /// VNI may be null only if MBB is a live-through block also passed to
229  /// addLiveInBlock().
231  Seen.set(MBB->getNumber());
232  Map[MBB] = LiveOutPair(VNI, nullptr);
233  }
234 
235  /// addLiveInBlock - Add a block with an unknown live-in value. This
236  /// function can only be called once per basic block. Once the live-in value
237  /// has been determined, calculateValues() will add liveness to LI.
238  ///
239  /// @param LR The live range that is live-in to the block.
240  /// @param DomNode The domtree node for the block.
241  /// @param Kill Index in block where LI is killed. If the value is
242  /// live-through, set Kill = SLotIndex() and also call
243  /// setLiveOutValue(MBB, 0).
245  SlotIndex Kill = SlotIndex()) {
246  LiveIn.push_back(LiveInBlock(LR, DomNode, Kill));
247  }
248 
249  /// calculateValues - Calculate the value that will be live-in to each block
250  /// added with addLiveInBlock. Add PHI-def values as needed to preserve SSA
251  /// form. Add liveness to all live-in blocks up to the Kill point, or the
252  /// whole block for live-through blocks.
253  ///
254  /// Every predecessor of a live-in block must have been given a value with
255  /// setLiveOutValue, the value may be null for live-trough blocks.
256  void calculateValues();
257 
258  /// A diagnostic function to check if the end of the block @p MBB is
259  /// jointly dominated by the blocks corresponding to the slot indices
260  /// in @p Defs. This function is mainly for use in self-verification
261  /// checks.
263  static bool isJointlyDominated(const MachineBasicBlock *MBB,
264  ArrayRef<SlotIndex> Defs,
265  const SlotIndexes &Indexes);
266 };
267 
268 } // end namespace llvm
269 
270 #endif // LLVM_CODEGEN_LIVERANGECALC_H
IndexedMap.h
llvm
Definition: AllocatorList.h:23
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:52
llvm::BitVector::set
BitVector & set()
Definition: BitVector.h:343
llvm::SmallVector< LiveInBlock, 16 >
llvm::LiveRangeCalc::extend
void extend(LiveRange &LR, SlotIndex Use, unsigned PhysReg, ArrayRef< SlotIndex > Undefs)
Extend the live range of LR to reach Use.
Definition: LiveRangeCalc.cpp:89
MachineBasicBlock.h
DenseMap.h
LLVM_ATTRIBUTE_UNUSED
#define LLVM_ATTRIBUTE_UNUSED
Definition: Compiler.h:188
llvm::LiveRangeCalc::calculateValues
void calculateValues()
calculateValues - Calculate the value that will be live-in to each block added with addLiveInBlock.
Definition: LiveRangeCalc.cpp:117
llvm::IndexedMap< LiveOutPair, MBB2NumberFunctor >
SI
@ SI
Definition: SIInstrInfo.cpp:7342
llvm::LiveRangeCalc::resetLiveOutMap
void resetLiveOutMap()
Reset Map and Seen fields.
Definition: LiveRangeCalc.cpp:43
BitVector.h
llvm::SlotIndexes
SlotIndexes pass.
Definition: SlotIndexes.h:314
llvm::BitVector
Definition: BitVector.h:74
llvm::SlotIndex
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:83
llvm::RegState::Kill
@ Kill
The last use of a register.
Definition: MachineInstrBuilder.h:49
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::MachineDomTreeNode
DomTreeNodeBase< MachineBasicBlock > MachineDomTreeNode
Definition: LiveIntervalCalc.h:26
llvm::LiveRangeCalc::getRegInfo
const MachineRegisterInfo * getRegInfo() const
Definition: LiveRangeCalc.h:168
llvm::LiveRangeCalc::addLiveInBlock
void addLiveInBlock(LiveRange &LR, MachineDomTreeNode *DomNode, SlotIndex Kill=SlotIndex())
addLiveInBlock - Add a block with an unknown live-in value.
Definition: LiveRangeCalc.h:244
llvm::LiveRange
This class represents the liveness of a register, stack slot, etc.
Definition: LiveInterval.h:157
llvm::BumpPtrAllocatorImpl
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:67
llvm::DenseMap< LiveRange *, std::pair< BitVector, BitVector > >
node
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper node
Definition: README-SSE.txt:406
llvm::LiveRangeCalc
Definition: LiveRangeCalc.h:46
ArrayRef.h
llvm::LiveRangeCalc::LiveRangeCalc
LiveRangeCalc()=default
llvm::MachineFunction
Definition: MachineFunction.h:227
llvm::LiveRangeCalc::getIndexes
SlotIndexes * getIndexes()
Definition: LiveRangeCalc.h:169
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:33
llvm::DomTreeNodeBase
Base class for the actual dominator tree node.
Definition: LiveIntervalCalc.h:24
llvm::LiveRangeCalc::getMachineFunction
const MachineFunction * getMachineFunction()
Some getters to expose in a read-only way some private fields to subclasses.
Definition: LiveRangeCalc.h:167
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::LiveRangeCalc::isJointlyDominated
static LLVM_ATTRIBUTE_UNUSED bool isJointlyDominated(const MachineBasicBlock *MBB, ArrayRef< SlotIndex > Defs, const SlotIndexes &Indexes)
A diagnostic function to check if the end of the block MBB is jointly dominated by the blocks corresp...
Definition: LiveRangeCalc.cpp:434
llvm::VNInfo
VNInfo - Value Number Information.
Definition: LiveInterval.h:53
LiveInterval.h
llvm::LiveRangeCalc::getVNAlloc
VNInfo::Allocator * getVNAlloc()
Definition: LiveRangeCalc.h:171
llvm::LiveRangeCalc::getDomTree
MachineDominatorTree * getDomTree()
Definition: LiveRangeCalc.h:170
SmallVector.h
LaneBitmask.h
llvm::LiveRangeCalc::reset
void reset(const MachineFunction *mf, SlotIndexes *SI, MachineDominatorTree *MDT, VNInfo::Allocator *VNIA)
reset - Prepare caches for a new set of non-overlapping live ranges.
Definition: LiveRangeCalc.cpp:51
llvm::LiveRangeCalc::setLiveOutValue
void setLiveOutValue(MachineBasicBlock *MBB, VNInfo *VNI)
setLiveOutValue - Indicate that VNI is live out from MBB.
Definition: LiveRangeCalc.h:230
SlotIndexes.h
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:45
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44