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