blob: d149e428ed0f6140c12c67ceac6b37c08fde6eec [file] [log] [blame]
Jakob Stoklund Olesen8dd070e2011-01-04 21:10:05 +00001//===-------- SplitKit.h - Toolkit for splitting live ranges ----*- C++ -*-===//
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +00002//
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 contains the SplitAnalysis class as well as mutator functions for
11// live range splitting.
12//
13//===----------------------------------------------------------------------===//
14
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +000015#include "llvm/ADT/DenseMap.h"
Eric Christopher0f438112011-02-03 06:18:29 +000016#include "llvm/ADT/IntervalMap.h"
Jakob Stoklund Olesen8d0963f2010-12-21 01:50:21 +000017#include "llvm/ADT/SmallPtrSet.h"
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +000018#include "llvm/CodeGen/SlotIndexes.h"
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +000019
20namespace llvm {
21
Eric Christopher0f438112011-02-03 06:18:29 +000022class ConnectedVNInfoEqClasses;
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +000023class LiveInterval;
24class LiveIntervals;
Jakob Stoklund Olesena17768f2010-10-14 23:49:52 +000025class LiveRangeEdit;
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +000026class MachineInstr;
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +000027class MachineLoopInfo;
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +000028class MachineRegisterInfo;
Jakob Stoklund Olesen6a0dc072010-07-20 21:46:58 +000029class TargetInstrInfo;
Jakob Stoklund Olesencfa71342010-11-10 19:31:50 +000030class TargetRegisterInfo;
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +000031class VirtRegMap;
32class VNInfo;
Jakob Stoklund Olesen532de3d2010-10-22 20:28:21 +000033class raw_ostream;
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +000034
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +000035/// At some point we should just include MachineDominators.h:
36class MachineDominatorTree;
37template <class NodeT> class DomTreeNodeBase;
38typedef DomTreeNodeBase<MachineBasicBlock> MachineDomTreeNode;
39
Jakob Stoklund Olesen8d0963f2010-12-21 01:50:21 +000040
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +000041/// SplitAnalysis - Analyze a LiveInterval, looking for live range splitting
42/// opportunities.
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +000043class SplitAnalysis {
Jakob Stoklund Olesen08e93b12010-08-10 17:07:22 +000044public:
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +000045 const MachineFunction &MF;
Jakob Stoklund Olesen1b847de2011-02-19 00:53:42 +000046 const VirtRegMap &VRM;
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +000047 const LiveIntervals &LIS;
48 const MachineLoopInfo &Loops;
49 const TargetInstrInfo &TII;
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +000050
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +000051 // Instructions using the the current register.
52 typedef SmallPtrSet<const MachineInstr*, 16> InstrPtrSet;
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +000053 InstrPtrSet UsingInstrs;
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +000054
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +000055 // Sorted slot indexes of using instructions.
56 SmallVector<SlotIndex, 8> UseSlots;
57
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +000058 // The number of instructions using CurLI in each basic block.
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +000059 typedef DenseMap<const MachineBasicBlock*, unsigned> BlockCountMap;
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +000060 BlockCountMap UsingBlocks;
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +000061
Jakob Stoklund Olesenf0ac26c2011-02-09 22:50:26 +000062 /// Additional information about basic blocks where the current variable is
63 /// live. Such a block will look like one of these templates:
64 ///
65 /// 1. | o---x | Internal to block. Variable is only live in this block.
66 /// 2. |---x | Live-in, kill.
67 /// 3. | o---| Def, live-out.
68 /// 4. |---x o---| Live-in, kill, def, live-out.
69 /// 5. |---o---o---| Live-through with uses or defs.
70 /// 6. |-----------| Live-through without uses. Transparent.
71 ///
72 struct BlockInfo {
73 MachineBasicBlock *MBB;
74 SlotIndex FirstUse; ///< First instr using current reg.
75 SlotIndex LastUse; ///< Last instr using current reg.
76 SlotIndex Kill; ///< Interval end point inside block.
77 SlotIndex Def; ///< Interval start point inside block.
78 /// Last possible point for splitting live ranges.
79 SlotIndex LastSplitPoint;
80 bool Uses; ///< Current reg has uses or defs in block.
81 bool LiveThrough; ///< Live in whole block (Templ 5. or 6. above).
82 bool LiveIn; ///< Current reg is live in.
83 bool LiveOut; ///< Current reg is live out.
84
85 // Per-interference pattern scratch data.
86 bool OverlapEntry; ///< Interference overlaps entering interval.
87 bool OverlapExit; ///< Interference overlaps exiting interval.
88 };
89
90 /// Basic blocks where var is live. This array is parallel to
91 /// SpillConstraints.
92 SmallVector<BlockInfo, 8> LiveBlocks;
93
Jakob Stoklund Olesenf1b05f22010-08-12 17:07:14 +000094private:
95 // Current live interval.
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +000096 const LiveInterval *CurLI;
Jakob Stoklund Olesenf1b05f22010-08-12 17:07:14 +000097
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +000098 // Sumarize statistics by counting instructions using CurLI.
Jakob Stoklund Olesenabff2802010-07-20 16:12:37 +000099 void analyzeUses();
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +0000100
Jakob Stoklund Olesenf0ac26c2011-02-09 22:50:26 +0000101 /// calcLiveBlockInfo - Compute per-block information about CurLI.
102 void calcLiveBlockInfo();
103
Jakob Stoklund Olesen6a0dc072010-07-20 21:46:58 +0000104 /// canAnalyzeBranch - Return true if MBB ends in a branch that can be
105 /// analyzed.
106 bool canAnalyzeBranch(const MachineBasicBlock *MBB);
107
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +0000108public:
Jakob Stoklund Olesen1b847de2011-02-19 00:53:42 +0000109 SplitAnalysis(const VirtRegMap &vrm, const LiveIntervals &lis,
Jakob Stoklund Olesenf2c6e362010-07-20 23:50:15 +0000110 const MachineLoopInfo &mli);
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +0000111
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000112 /// analyze - set CurLI to the specified interval, and analyze how it may be
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +0000113 /// split.
114 void analyze(const LiveInterval *li);
115
116 /// clear - clear all data structures so SplitAnalysis is ready to analyze a
117 /// new interval.
118 void clear();
119
Jakob Stoklund Olesen034a80d2011-02-17 19:13:53 +0000120 /// getParent - Return the last analyzed interval.
121 const LiveInterval &getParent() const { return *CurLI; }
122
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000123 /// hasUses - Return true if MBB has any uses of CurLI.
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +0000124 bool hasUses(const MachineBasicBlock *MBB) const {
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000125 return UsingBlocks.lookup(MBB);
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +0000126 }
127
Jakob Stoklund Olesen06c0f252011-02-21 23:09:46 +0000128 /// isOriginalEndpoint - Return true if the original live range was killed or
129 /// (re-)defined at Idx. Idx should be the 'def' slot for a normal kill/def,
130 /// and 'use' for an early-clobber def.
131 /// This can be used to recognize code inserted by earlier live range
132 /// splitting.
133 bool isOriginalEndpoint(SlotIndex Idx) const;
134
Jakob Stoklund Olesen6a0dc072010-07-20 21:46:58 +0000135 typedef SmallPtrSet<const MachineBasicBlock*, 16> BlockPtrSet;
136
Jakob Stoklund Olesen532de3d2010-10-22 20:28:21 +0000137 // Print a set of blocks with use counts.
138 void print(const BlockPtrSet&, raw_ostream&) const;
139
Jakob Stoklund Olesenf1b05f22010-08-12 17:07:14 +0000140 /// getMultiUseBlocks - Add basic blocks to Blocks that may benefit from
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000141 /// having CurLI split to a new live interval. Return true if Blocks can be
Jakob Stoklund Olesenf1b05f22010-08-12 17:07:14 +0000142 /// passed to SplitEditor::splitSingleBlocks.
143 bool getMultiUseBlocks(BlockPtrSet &Blocks);
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +0000144};
145
Jakob Stoklund Olesen1407c842010-08-18 19:00:08 +0000146
147/// LiveIntervalMap - Map values from a large LiveInterval into a small
148/// interval that is a subset. Insert phi-def values as needed. This class is
149/// used by SplitEditor to create new smaller LiveIntervals.
150///
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000151/// ParentLI is the larger interval, LI is the subset interval. Every value
152/// in LI corresponds to exactly one value in ParentLI, and the live range
153/// of the value is contained within the live range of the ParentLI value.
154/// Values in ParentLI may map to any number of OpenLI values, including 0.
Jakob Stoklund Olesen1407c842010-08-18 19:00:08 +0000155class LiveIntervalMap {
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000156 LiveIntervals &LIS;
157 MachineDominatorTree &MDT;
Jakob Stoklund Olesen1407c842010-08-18 19:00:08 +0000158
159 // The parent interval is never changed.
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000160 const LiveInterval &ParentLI;
Jakob Stoklund Olesen1407c842010-08-18 19:00:08 +0000161
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000162 // The child interval's values are fully contained inside ParentLI values.
163 LiveInterval *LI;
Jakob Stoklund Olesen1407c842010-08-18 19:00:08 +0000164
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000165 typedef std::pair<VNInfo*, MachineDomTreeNode*> LiveOutPair;
166 typedef DenseMap<MachineBasicBlock*,LiveOutPair> LiveOutMap;
167
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000168 // LiveOutCache - Map each basic block where LI is live out to the live-out
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000169 // value and its defining block. One of these conditions shall be true:
170 //
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000171 // 1. !LiveOutCache.count(MBB)
172 // 2. LiveOutCache[MBB].second.getNode() == MBB
173 // 3. forall P in preds(MBB): LiveOutCache[P] == LiveOutCache[MBB]
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000174 //
175 // This is only a cache, the values can be computed as:
176 //
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000177 // VNI = LI->getVNInfoAt(LIS.getMBBEndIdx(MBB))
178 // Node = mbt_[LIS.getMBBFromIndex(VNI->def)]
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000179 //
180 // The cache is also used as a visiteed set by mapValue().
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000181 LiveOutMap LiveOutCache;
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000182
Jakob Stoklund Olesend7ca5772011-01-20 17:45:20 +0000183 // Dump the live-out cache to dbgs().
184 void dumpCache();
185
Jakob Stoklund Olesen1407c842010-08-18 19:00:08 +0000186public:
187 LiveIntervalMap(LiveIntervals &lis,
Jakob Stoklund Olesend68f4582010-10-28 20:34:50 +0000188 MachineDominatorTree &mdt,
Jakob Stoklund Olesen9ca2aeb2010-09-13 23:29:09 +0000189 const LiveInterval &parentli)
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000190 : LIS(lis), MDT(mdt), ParentLI(parentli), LI(0) {}
Jakob Stoklund Olesen9ca2aeb2010-09-13 23:29:09 +0000191
192 /// reset - clear all data structures and start a new live interval.
193 void reset(LiveInterval *);
194
195 /// getLI - return the current live interval.
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000196 LiveInterval *getLI() const { return LI; }
Jakob Stoklund Olesen1407c842010-08-18 19:00:08 +0000197
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000198 /// mapValue - map ParentVNI to the corresponding LI value at Idx. It is
Jakob Stoklund Olesen1407c842010-08-18 19:00:08 +0000199 /// assumed that ParentVNI is live at Idx.
200 /// If ParentVNI has not been defined by defValue, it is assumed that
201 /// ParentVNI->def dominates Idx.
202 /// If ParentVNI has been defined by defValue one or more times, a value that
203 /// dominates Idx will be returned. This may require creating extra phi-def
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000204 /// values and adding live ranges to LI.
Jakob Stoklund Olesen5fa42a42010-09-21 22:32:21 +0000205 /// If simple is not NULL, *simple will indicate if ParentVNI is a simply
206 /// mapped value.
207 VNInfo *mapValue(const VNInfo *ParentVNI, SlotIndex Idx, bool *simple = 0);
Jakob Stoklund Olesen1407c842010-08-18 19:00:08 +0000208};
209
210
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +0000211/// SplitEditor - Edit machine code and LiveIntervals for live range
212/// splitting.
213///
Jakob Stoklund Olesen5eb308b2010-08-06 22:17:33 +0000214/// - Create a SplitEditor from a SplitAnalysis.
Jakob Stoklund Olesen7536f722010-08-04 22:08:39 +0000215/// - Start a new live interval with openIntv.
216/// - Mark the places where the new interval is entered using enterIntv*
217/// - Mark the ranges where the new interval is used with useIntv*
218/// - Mark the places where the interval is exited with exitIntv*.
219/// - Finish the current interval with closeIntv and repeat from 2.
Jakob Stoklund Olesen74669272010-10-08 23:42:21 +0000220/// - Rewrite instructions with finish().
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +0000221///
222class SplitEditor {
Jakob Stoklund Olesen0eeca442011-02-19 00:42:33 +0000223 SplitAnalysis &SA;
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000224 LiveIntervals &LIS;
225 VirtRegMap &VRM;
226 MachineRegisterInfo &MRI;
Eric Christopher0f438112011-02-03 06:18:29 +0000227 MachineDominatorTree &MDT;
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000228 const TargetInstrInfo &TII;
229 const TargetRegisterInfo &TRI;
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +0000230
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000231 /// Edit - The current parent register and new intervals created.
232 LiveRangeEdit &Edit;
Jakob Stoklund Olesena17768f2010-10-14 23:49:52 +0000233
Eric Christopher0f438112011-02-03 06:18:29 +0000234 /// Index into Edit of the currently open interval.
235 /// The index 0 is used for the complement, so the first interval started by
236 /// openIntv will be 1.
237 unsigned OpenIdx;
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +0000238
Eric Christopher0f438112011-02-03 06:18:29 +0000239 typedef IntervalMap<SlotIndex, unsigned> RegAssignMap;
240
241 /// Allocator for the interval map. This will eventually be shared with
242 /// SlotIndexes and LiveIntervals.
243 RegAssignMap::Allocator Allocator;
244
245 /// RegAssign - Map of the assigned register indexes.
246 /// Edit.get(RegAssign.lookup(Idx)) is the register that should be live at
247 /// Idx.
248 RegAssignMap RegAssign;
249
250 /// LIMappers - One LiveIntervalMap or each interval in Edit.
251 SmallVector<LiveIntervalMap, 4> LIMappers;
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +0000252
Jakob Stoklund Olesen670ccd12011-03-01 23:14:53 +0000253 typedef DenseMap<std::pair<unsigned, unsigned>, VNInfo*> ValueMap;
254
255 /// Values - keep track of the mapping from parent values to values in the new
256 /// intervals. Given a pair (RegIdx, ParentVNI->id), Values contains:
257 ///
258 /// 1. No entry - the value is not mapped to Edit.get(RegIdx).
259 /// 2. Null - the value is mapped to multiple values in Edit.get(RegIdx).
260 /// Each value is represented by a minimal live range at its def.
261 /// 3. A non-null VNInfo - the value is mapped to a single new value.
262 /// The new value has no live ranges anywhere.
263 ValueMap Values;
264
265 /// defValue - define a value in RegIdx from ParentVNI at Idx.
266 /// Idx does not have to be ParentVNI->def, but it must be contained within
267 /// ParentVNI's live range in ParentLI. The new value is added to the value
268 /// map.
269 /// Return the new LI value.
270 VNInfo *defValue(unsigned RegIdx, const VNInfo *ParentVNI, SlotIndex Idx);
271
272 /// markComplexMapped - Mark ParentVNI as complex mapped in RegIdx regardless
273 /// of the number of defs.
274 void markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI);
275
Jakob Stoklund Olesencfa71342010-11-10 19:31:50 +0000276 /// defFromParent - Define Reg from ParentVNI at UseIdx using either
277 /// rematerialization or a COPY from parent. Return the new value.
Eric Christopher0f438112011-02-03 06:18:29 +0000278 VNInfo *defFromParent(unsigned RegIdx,
Jakob Stoklund Olesencfa71342010-11-10 19:31:50 +0000279 VNInfo *ParentVNI,
280 SlotIndex UseIdx,
281 MachineBasicBlock &MBB,
282 MachineBasicBlock::iterator I);
283
Eric Christopher0f438112011-02-03 06:18:29 +0000284 /// rewriteAssigned - Rewrite all uses of Edit.getReg() to assigned registers.
285 void rewriteAssigned();
Jakob Stoklund Olesen5fa42a42010-09-21 22:32:21 +0000286
Eric Christopher0f438112011-02-03 06:18:29 +0000287 /// rewriteComponents - Rewrite all uses of Intv[0] according to the eq
288 /// classes in ConEQ.
289 /// This must be done when Intvs[0] is styill live at all uses, before calling
290 /// ConEq.Distribute().
291 void rewriteComponents(const SmallVectorImpl<LiveInterval*> &Intvs,
292 const ConnectedVNInfoEqClasses &ConEq);
Jakob Stoklund Olesen74669272010-10-08 23:42:21 +0000293
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +0000294public:
295 /// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
Jakob Stoklund Olesen7536f722010-08-04 22:08:39 +0000296 /// Newly created intervals will be appended to newIntervals.
Jakob Stoklund Olesend68f4582010-10-28 20:34:50 +0000297 SplitEditor(SplitAnalysis &SA, LiveIntervals&, VirtRegMap&,
298 MachineDominatorTree&, LiveRangeEdit&);
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +0000299
Jakob Stoklund Olesen5eb308b2010-08-06 22:17:33 +0000300 /// getAnalysis - Get the corresponding analysis.
Jakob Stoklund Olesen0eeca442011-02-19 00:42:33 +0000301 SplitAnalysis &getAnalysis() { return SA; }
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +0000302
Jakob Stoklund Olesen7536f722010-08-04 22:08:39 +0000303 /// Create a new virtual register and live interval.
304 void openIntv();
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +0000305
Jakob Stoklund Olesen207c8682011-02-03 17:04:16 +0000306 /// enterIntvBefore - Enter the open interval before the instruction at Idx.
307 /// If the parent interval is not live before Idx, a COPY is not inserted.
308 /// Return the beginning of the new live range.
309 SlotIndex enterIntvBefore(SlotIndex Idx);
Jakob Stoklund Olesenf1b05f22010-08-12 17:07:14 +0000310
Jakob Stoklund Olesen207c8682011-02-03 17:04:16 +0000311 /// enterIntvAtEnd - Enter the open interval at the end of MBB.
312 /// Use the open interval from he inserted copy to the MBB end.
313 /// Return the beginning of the new live range.
314 SlotIndex enterIntvAtEnd(MachineBasicBlock &MBB);
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +0000315
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000316 /// useIntv - indicate that all instructions in MBB should use OpenLI.
Jakob Stoklund Olesen7536f722010-08-04 22:08:39 +0000317 void useIntv(const MachineBasicBlock &MBB);
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +0000318
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000319 /// useIntv - indicate that all instructions in range should use OpenLI.
Jakob Stoklund Olesen7536f722010-08-04 22:08:39 +0000320 void useIntv(SlotIndex Start, SlotIndex End);
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +0000321
Jakob Stoklund Olesen207c8682011-02-03 17:04:16 +0000322 /// leaveIntvAfter - Leave the open interval after the instruction at Idx.
323 /// Return the end of the live range.
324 SlotIndex leaveIntvAfter(SlotIndex Idx);
Jakob Stoklund Olesenf1b05f22010-08-12 17:07:14 +0000325
Jakob Stoklund Olesen9b057772011-02-09 23:30:25 +0000326 /// leaveIntvBefore - Leave the open interval before the instruction at Idx.
327 /// Return the end of the live range.
328 SlotIndex leaveIntvBefore(SlotIndex Idx);
329
Jakob Stoklund Olesen7536f722010-08-04 22:08:39 +0000330 /// leaveIntvAtTop - Leave the interval at the top of MBB.
Jakob Stoklund Olesen207c8682011-02-03 17:04:16 +0000331 /// Add liveness from the MBB top to the copy.
332 /// Return the end of the live range.
333 SlotIndex leaveIntvAtTop(MachineBasicBlock &MBB);
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +0000334
Jakob Stoklund Olesen5c716bd2011-02-08 18:50:21 +0000335 /// overlapIntv - Indicate that all instructions in range should use the open
336 /// interval, but also let the complement interval be live.
337 ///
338 /// This doubles the register pressure, but is sometimes required to deal with
339 /// register uses after the last valid split point.
340 ///
341 /// The Start index should be a return value from a leaveIntv* call, and End
342 /// should be in the same basic block. The parent interval must have the same
343 /// value across the range.
344 ///
345 void overlapIntv(SlotIndex Start, SlotIndex End);
346
Jakob Stoklund Olesen7536f722010-08-04 22:08:39 +0000347 /// closeIntv - Indicate that we are done editing the currently open
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +0000348 /// LiveInterval, and ranges can be trimmed.
Jakob Stoklund Olesen7536f722010-08-04 22:08:39 +0000349 void closeIntv();
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +0000350
Jakob Stoklund Olesen74669272010-10-08 23:42:21 +0000351 /// finish - after all the new live ranges have been created, compute the
352 /// remaining live range, and rewrite instructions to use the new registers.
353 void finish();
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +0000354
Eric Christopher0f438112011-02-03 06:18:29 +0000355 /// dump - print the current interval maping to dbgs().
356 void dump() const;
357
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +0000358 // ===--- High level methods ---===
359
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000360 /// splitSingleBlocks - Split CurLI into a separate live interval inside each
Jakob Stoklund Olesen57d0f2d2010-10-05 22:19:33 +0000361 /// basic block in Blocks.
362 void splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks);
Jakob Stoklund Olesenfc412d82010-08-13 21:18:48 +0000363};
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +0000364
365}