blob: bc1c8b0059c09909901f757ea41e7e0c2ec1e05d [file] [log] [blame]
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +00001//===---------- SplitKit.cpp - Toolkit for splitting live ranges ----------===//
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// This file contains the SplitAnalysis class as well as mutator functions for
11// live range splitting.
12//
13//===----------------------------------------------------------------------===//
14
Jakob Stoklund Olesen376dcbd2010-11-03 20:39:23 +000015#define DEBUG_TYPE "regalloc"
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +000016#include "SplitKit.h"
Jakob Stoklund Olesena17768f2010-10-14 23:49:52 +000017#include "LiveRangeEdit.h"
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +000018#include "VirtRegMap.h"
Jakob Stoklund Olesen08e93b12010-08-10 17:07:22 +000019#include "llvm/CodeGen/CalcSpillWeights.h"
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +000020#include "llvm/CodeGen/LiveIntervalAnalysis.h"
Jakob Stoklund Olesend68f4582010-10-28 20:34:50 +000021#include "llvm/CodeGen/MachineDominators.h"
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +000022#include "llvm/CodeGen/MachineInstrBuilder.h"
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +000023#include "llvm/CodeGen/MachineRegisterInfo.h"
Jakob Stoklund Olesen6a0dc072010-07-20 21:46:58 +000024#include "llvm/Support/CommandLine.h"
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +000025#include "llvm/Support/Debug.h"
26#include "llvm/Support/raw_ostream.h"
Jakob Stoklund Olesen6a0dc072010-07-20 21:46:58 +000027#include "llvm/Target/TargetInstrInfo.h"
28#include "llvm/Target/TargetMachine.h"
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +000029
30using namespace llvm;
31
Jakob Stoklund Olesen6a0dc072010-07-20 21:46:58 +000032static cl::opt<bool>
33AllowSplit("spiller-splits-edges",
34 cl::desc("Allow critical edge splitting during spilling"));
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +000035
36//===----------------------------------------------------------------------===//
37// Split Analysis
38//===----------------------------------------------------------------------===//
39
Jakob Stoklund Olesen1b847de2011-02-19 00:53:42 +000040SplitAnalysis::SplitAnalysis(const VirtRegMap &vrm,
Jakob Stoklund Olesenf2c6e362010-07-20 23:50:15 +000041 const LiveIntervals &lis,
42 const MachineLoopInfo &mli)
Jakob Stoklund Olesen1b847de2011-02-19 00:53:42 +000043 : MF(vrm.getMachineFunction()),
44 VRM(vrm),
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +000045 LIS(lis),
46 Loops(mli),
Jakob Stoklund Olesen1b847de2011-02-19 00:53:42 +000047 TII(*MF.getTarget().getInstrInfo()),
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +000048 CurLI(0) {}
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +000049
50void SplitAnalysis::clear() {
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +000051 UseSlots.clear();
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +000052 UsingInstrs.clear();
53 UsingBlocks.clear();
Jakob Stoklund Olesenf0ac26c2011-02-09 22:50:26 +000054 LiveBlocks.clear();
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +000055 CurLI = 0;
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +000056}
57
Jakob Stoklund Olesen6a0dc072010-07-20 21:46:58 +000058bool SplitAnalysis::canAnalyzeBranch(const MachineBasicBlock *MBB) {
59 MachineBasicBlock *T, *F;
60 SmallVector<MachineOperand, 4> Cond;
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +000061 return !TII.AnalyzeBranch(const_cast<MachineBasicBlock&>(*MBB), T, F, Cond);
Jakob Stoklund Olesen6a0dc072010-07-20 21:46:58 +000062}
63
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +000064/// analyzeUses - Count instructions, basic blocks, and loops using CurLI.
Jakob Stoklund Olesenabff2802010-07-20 16:12:37 +000065void SplitAnalysis::analyzeUses() {
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +000066 const MachineRegisterInfo &MRI = MF.getRegInfo();
Jakob Stoklund Olesena372d162011-02-09 21:52:09 +000067 for (MachineRegisterInfo::reg_iterator I = MRI.reg_begin(CurLI->reg),
68 E = MRI.reg_end(); I != E; ++I) {
69 MachineOperand &MO = I.getOperand();
70 if (MO.isUse() && MO.isUndef())
71 continue;
72 MachineInstr *MI = MO.getParent();
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +000073 if (MI->isDebugValue() || !UsingInstrs.insert(MI))
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +000074 continue;
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +000075 UseSlots.push_back(LIS.getInstructionIndex(MI).getDefIndex());
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +000076 MachineBasicBlock *MBB = MI->getParent();
Jakob Stoklund Olesen4f5c9d22011-02-09 23:56:18 +000077 UsingBlocks[MBB]++;
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +000078 }
Jakob Stoklund Olesenb5fa9332011-01-18 21:13:27 +000079 array_pod_sort(UseSlots.begin(), UseSlots.end());
Jakob Stoklund Olesenf0ac26c2011-02-09 22:50:26 +000080 calcLiveBlockInfo();
Jakob Stoklund Olesene1f543f2010-08-12 18:50:55 +000081 DEBUG(dbgs() << " counted "
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +000082 << UsingInstrs.size() << " instrs, "
Jakob Stoklund Olesen4f5c9d22011-02-09 23:56:18 +000083 << UsingBlocks.size() << " blocks.\n");
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +000084}
85
Jakob Stoklund Olesenf0ac26c2011-02-09 22:50:26 +000086/// calcLiveBlockInfo - Fill the LiveBlocks array with information about blocks
87/// where CurLI is live.
88void SplitAnalysis::calcLiveBlockInfo() {
89 if (CurLI->empty())
90 return;
91
92 LiveInterval::const_iterator LVI = CurLI->begin();
93 LiveInterval::const_iterator LVE = CurLI->end();
94
95 SmallVectorImpl<SlotIndex>::const_iterator UseI, UseE;
96 UseI = UseSlots.begin();
97 UseE = UseSlots.end();
98
99 // Loop over basic blocks where CurLI is live.
100 MachineFunction::iterator MFI = LIS.getMBBFromIndex(LVI->start);
101 for (;;) {
102 BlockInfo BI;
103 BI.MBB = MFI;
104 SlotIndex Start, Stop;
105 tie(Start, Stop) = LIS.getSlotIndexes()->getMBBRange(BI.MBB);
106
107 // The last split point is the latest possible insertion point that dominates
108 // all successor blocks. If interference reaches LastSplitPoint, it is not
109 // possible to insert a split or reload that makes CurLI live in the
110 // outgoing bundle.
111 MachineBasicBlock::iterator LSP = LIS.getLastSplitPoint(*CurLI, BI.MBB);
112 if (LSP == BI.MBB->end())
113 BI.LastSplitPoint = Stop;
114 else
115 BI.LastSplitPoint = LIS.getInstructionIndex(LSP);
116
117 // LVI is the first live segment overlapping MBB.
118 BI.LiveIn = LVI->start <= Start;
119 if (!BI.LiveIn)
120 BI.Def = LVI->start;
121
122 // Find the first and last uses in the block.
123 BI.Uses = hasUses(MFI);
124 if (BI.Uses && UseI != UseE) {
125 BI.FirstUse = *UseI;
126 assert(BI.FirstUse >= Start);
127 do ++UseI;
128 while (UseI != UseE && *UseI < Stop);
129 BI.LastUse = UseI[-1];
130 assert(BI.LastUse < Stop);
131 }
132
133 // Look for gaps in the live range.
134 bool hasGap = false;
135 BI.LiveOut = true;
136 while (LVI->end < Stop) {
137 SlotIndex LastStop = LVI->end;
138 if (++LVI == LVE || LVI->start >= Stop) {
139 BI.Kill = LastStop;
140 BI.LiveOut = false;
141 break;
142 }
143 if (LastStop < LVI->start) {
144 hasGap = true;
145 BI.Kill = LastStop;
146 BI.Def = LVI->start;
147 }
148 }
149
150 // Don't set LiveThrough when the block has a gap.
151 BI.LiveThrough = !hasGap && BI.LiveIn && BI.LiveOut;
152 LiveBlocks.push_back(BI);
153
154 // LVI is now at LVE or LVI->end >= Stop.
155 if (LVI == LVE)
156 break;
157
158 // Live segment ends exactly at Stop. Move to the next segment.
159 if (LVI->end == Stop && ++LVI == LVE)
160 break;
161
162 // Pick the next basic block.
163 if (LVI->start < Stop)
164 ++MFI;
165 else
166 MFI = LIS.getMBBFromIndex(LVI->start);
167 }
168}
169
Jakob Stoklund Olesen06c0f252011-02-21 23:09:46 +0000170bool SplitAnalysis::isOriginalEndpoint(SlotIndex Idx) const {
171 unsigned OrigReg = VRM.getOriginal(CurLI->reg);
172 const LiveInterval &Orig = LIS.getInterval(OrigReg);
173 assert(!Orig.empty() && "Splitting empty interval?");
174 LiveInterval::const_iterator I = Orig.find(Idx);
175
176 // Range containing Idx should begin at Idx.
177 if (I != Orig.end() && I->start <= Idx)
178 return I->start == Idx;
179
180 // Range does not contain Idx, previous must end at Idx.
181 return I != Orig.begin() && (--I)->end == Idx;
182}
183
Jakob Stoklund Olesen532de3d2010-10-22 20:28:21 +0000184void SplitAnalysis::print(const BlockPtrSet &B, raw_ostream &OS) const {
185 for (BlockPtrSet::const_iterator I = B.begin(), E = B.end(); I != E; ++I) {
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000186 unsigned count = UsingBlocks.lookup(*I);
Jakob Stoklund Olesen532de3d2010-10-22 20:28:21 +0000187 OS << " BB#" << (*I)->getNumber();
188 if (count)
189 OS << '(' << count << ')';
190 }
191}
192
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +0000193void SplitAnalysis::analyze(const LiveInterval *li) {
194 clear();
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000195 CurLI = li;
Jakob Stoklund Olesenabff2802010-07-20 16:12:37 +0000196 analyzeUses();
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +0000197}
198
Jakob Stoklund Olesen697483a2010-12-15 17:49:52 +0000199
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +0000200//===----------------------------------------------------------------------===//
Jakob Stoklund Olesen1407c842010-08-18 19:00:08 +0000201// LiveIntervalMap
202//===----------------------------------------------------------------------===//
203
Jakob Stoklund Olesenb3e96812010-09-13 21:29:45 +0000204// Work around the fact that the std::pair constructors are broken for pointer
205// pairs in some implementations. makeVV(x, 0) works.
206static inline std::pair<const VNInfo*, VNInfo*>
207makeVV(const VNInfo *a, VNInfo *b) {
208 return std::make_pair(a, b);
209}
210
Jakob Stoklund Olesen9ca2aeb2010-09-13 23:29:09 +0000211void LiveIntervalMap::reset(LiveInterval *li) {
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000212 LI = li;
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000213 LiveOutCache.clear();
Jakob Stoklund Olesen9ca2aeb2010-09-13 23:29:09 +0000214}
215
Jakob Stoklund Olesen5fa42a42010-09-21 22:32:21 +0000216
Jakob Stoklund Olesen1407c842010-08-18 19:00:08 +0000217// mapValue - Find the mapped value for ParentVNI at Idx.
218// Potentially create phi-def values.
Jakob Stoklund Olesen5fa42a42010-09-21 22:32:21 +0000219VNInfo *LiveIntervalMap::mapValue(const VNInfo *ParentVNI, SlotIndex Idx,
220 bool *simple) {
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000221 assert(LI && "call reset first");
Jakob Stoklund Olesen1407c842010-08-18 19:00:08 +0000222 assert(ParentVNI && "Mapping NULL value");
223 assert(Idx.isValid() && "Invalid SlotIndex");
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000224 assert(ParentLI.getVNInfoAt(Idx) == ParentVNI && "Bad ParentVNI");
Jakob Stoklund Olesen1407c842010-08-18 19:00:08 +0000225
Jakob Stoklund Olesen1407c842010-08-18 19:00:08 +0000226 // This is a complex mapped value. There may be multiple defs, and we may need
227 // to create phi-defs.
Jakob Stoklund Olesen5fa42a42010-09-21 22:32:21 +0000228 if (simple) *simple = false;
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000229 MachineBasicBlock *IdxMBB = LIS.getMBBFromIndex(Idx);
Jakob Stoklund Olesen1407c842010-08-18 19:00:08 +0000230 assert(IdxMBB && "No MBB at Idx");
231
232 // Is there a def in the same MBB we can extend?
233 if (VNInfo *VNI = extendTo(IdxMBB, Idx))
234 return VNI;
235
236 // Now for the fun part. We know that ParentVNI potentially has multiple defs,
237 // and we may need to create even more phi-defs to preserve VNInfo SSA form.
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000238 // Perform a search for all predecessor blocks where we know the dominating
239 // VNInfo. Insert phi-def VNInfos along the path back to IdxMBB.
240 DEBUG(dbgs() << "\n Reaching defs for BB#" << IdxMBB->getNumber()
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000241 << " at " << Idx << " in " << *LI << '\n');
Jakob Stoklund Olesen1407c842010-08-18 19:00:08 +0000242
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000243 // Blocks where LI should be live-in.
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000244 SmallVector<MachineDomTreeNode*, 16> LiveIn;
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000245 LiveIn.push_back(MDT[IdxMBB]);
Jakob Stoklund Olesen1407c842010-08-18 19:00:08 +0000246
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000247 // Using LiveOutCache as a visited set, perform a BFS for all reaching defs.
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000248 for (unsigned i = 0; i != LiveIn.size(); ++i) {
249 MachineBasicBlock *MBB = LiveIn[i]->getBlock();
250 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
251 PE = MBB->pred_end(); PI != PE; ++PI) {
252 MachineBasicBlock *Pred = *PI;
253 // Is this a known live-out block?
254 std::pair<LiveOutMap::iterator,bool> LOIP =
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000255 LiveOutCache.insert(std::make_pair(Pred, LiveOutPair()));
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000256 // Yes, we have been here before.
257 if (!LOIP.second) {
Benjamin Kramer8a8e26f2010-10-29 17:40:05 +0000258 DEBUG(if (VNInfo *VNI = LOIP.first->second.first)
259 dbgs() << " known valno #" << VNI->id
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000260 << " at BB#" << Pred->getNumber() << '\n');
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000261 continue;
262 }
Jakob Stoklund Olesen1407c842010-08-18 19:00:08 +0000263
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000264 // Does Pred provide a live-out value?
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000265 SlotIndex Last = LIS.getMBBEndIdx(Pred).getPrevSlot();
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000266 if (VNInfo *VNI = extendTo(Pred, Last)) {
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000267 MachineBasicBlock *DefMBB = LIS.getMBBFromIndex(VNI->def);
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000268 DEBUG(dbgs() << " found valno #" << VNI->id
Jakob Stoklund Olesenc94fcb12010-10-29 17:37:25 +0000269 << " from BB#" << DefMBB->getNumber()
270 << " at BB#" << Pred->getNumber() << '\n');
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000271 LiveOutPair &LOP = LOIP.first->second;
272 LOP.first = VNI;
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000273 LOP.second = MDT[DefMBB];
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000274 continue;
275 }
276 // No, we need a live-in value for Pred as well
277 if (Pred != IdxMBB)
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000278 LiveIn.push_back(MDT[Pred]);
Jakob Stoklund Olesen1407c842010-08-18 19:00:08 +0000279 }
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000280 }
Jakob Stoklund Olesen1407c842010-08-18 19:00:08 +0000281
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000282 // We may need to add phi-def values to preserve the SSA form.
283 // This is essentially the same iterative algorithm that SSAUpdater uses,
284 // except we already have a dominator tree, so we don't have to recompute it.
285 VNInfo *IdxVNI = 0;
286 unsigned Changes;
287 do {
288 Changes = 0;
289 DEBUG(dbgs() << " Iterating over " << LiveIn.size() << " blocks.\n");
290 // Propagate live-out values down the dominator tree, inserting phi-defs when
291 // necessary. Since LiveIn was created by a BFS, going backwards makes it more
292 // likely for us to visit immediate dominators before their children.
293 for (unsigned i = LiveIn.size(); i; --i) {
294 MachineDomTreeNode *Node = LiveIn[i-1];
295 MachineBasicBlock *MBB = Node->getBlock();
296 MachineDomTreeNode *IDom = Node->getIDom();
297 LiveOutPair IDomValue;
298 // We need a live-in value to a block with no immediate dominator?
299 // This is probably an unreachable block that has survived somehow.
300 bool needPHI = !IDom;
Jakob Stoklund Olesen1407c842010-08-18 19:00:08 +0000301
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000302 // Get the IDom live-out value.
303 if (!needPHI) {
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000304 LiveOutMap::iterator I = LiveOutCache.find(IDom->getBlock());
305 if (I != LiveOutCache.end())
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000306 IDomValue = I->second;
307 else
308 // If IDom is outside our set of live-out blocks, there must be new
309 // defs, and we need a phi-def here.
310 needPHI = true;
311 }
Jakob Stoklund Olesen984a7fc2010-10-05 20:36:28 +0000312
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000313 // IDom dominates all of our predecessors, but it may not be the immediate
314 // dominator. Check if any of them have live-out values that are properly
315 // dominated by IDom. If so, we need a phi-def here.
316 if (!needPHI) {
317 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
318 PE = MBB->pred_end(); PI != PE; ++PI) {
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000319 LiveOutPair Value = LiveOutCache[*PI];
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000320 if (!Value.first || Value.first == IDomValue.first)
321 continue;
322 // This predecessor is carrying something other than IDomValue.
323 // It could be because IDomValue hasn't propagated yet, or it could be
324 // because MBB is in the dominance frontier of that value.
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000325 if (MDT.dominates(IDom, Value.second)) {
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000326 needPHI = true;
327 break;
328 }
329 }
330 }
Jakob Stoklund Olesenff3ae862010-08-18 20:29:53 +0000331
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000332 // Create a phi-def if required.
333 if (needPHI) {
334 ++Changes;
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000335 SlotIndex Start = LIS.getMBBStartIdx(MBB);
336 VNInfo *VNI = LI->getNextValue(Start, 0, LIS.getVNInfoAllocator());
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000337 VNI->setIsPHIDef(true);
338 DEBUG(dbgs() << " - BB#" << MBB->getNumber()
339 << " phi-def #" << VNI->id << " at " << Start << '\n');
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000340 // We no longer need LI to be live-in.
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000341 LiveIn.erase(LiveIn.begin()+(i-1));
342 // Blocks in LiveIn are either IdxMBB, or have a value live-through.
343 if (MBB == IdxMBB)
344 IdxVNI = VNI;
345 // Check if we need to update live-out info.
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000346 LiveOutMap::iterator I = LiveOutCache.find(MBB);
347 if (I == LiveOutCache.end() || I->second.second == Node) {
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000348 // We already have a live-out defined in MBB, so this must be IdxMBB.
349 assert(MBB == IdxMBB && "Adding phi-def to known live-out");
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000350 LI->addRange(LiveRange(Start, Idx.getNextSlot(), VNI));
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000351 } else {
352 // This phi-def is also live-out, so color the whole block.
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000353 LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI));
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000354 I->second = LiveOutPair(VNI, Node);
355 }
356 } else if (IDomValue.first) {
Jakob Stoklund Olesenc94fcb12010-10-29 17:37:25 +0000357 // No phi-def here. Remember incoming value for IdxMBB.
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000358 if (MBB == IdxMBB)
359 IdxVNI = IDomValue.first;
Jakob Stoklund Olesenc94fcb12010-10-29 17:37:25 +0000360 // Propagate IDomValue if needed:
361 // MBB is live-out and doesn't define its own value.
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000362 LiveOutMap::iterator I = LiveOutCache.find(MBB);
363 if (I != LiveOutCache.end() && I->second.second != Node &&
Jakob Stoklund Olesenc94fcb12010-10-29 17:37:25 +0000364 I->second.first != IDomValue.first) {
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000365 ++Changes;
366 I->second = IDomValue;
367 DEBUG(dbgs() << " - BB#" << MBB->getNumber()
368 << " idom valno #" << IDomValue.first->id
369 << " from BB#" << IDom->getBlock()->getNumber() << '\n');
370 }
Jakob Stoklund Olesenff3ae862010-08-18 20:29:53 +0000371 }
Jakob Stoklund Olesen1407c842010-08-18 19:00:08 +0000372 }
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000373 DEBUG(dbgs() << " - made " << Changes << " changes.\n");
374 } while (Changes);
Jakob Stoklund Olesen1407c842010-08-18 19:00:08 +0000375
376 assert(IdxVNI && "Didn't find value for Idx");
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000377
378#ifndef NDEBUG
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000379 // Check the LiveOutCache invariants.
380 for (LiveOutMap::iterator I = LiveOutCache.begin(), E = LiveOutCache.end();
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000381 I != E; ++I) {
382 assert(I->first && "Null MBB entry in cache");
383 assert(I->second.first && "Null VNInfo in cache");
384 assert(I->second.second && "Null DomTreeNode in cache");
385 if (I->second.second->getBlock() == I->first)
386 continue;
387 for (MachineBasicBlock::pred_iterator PI = I->first->pred_begin(),
388 PE = I->first->pred_end(); PI != PE; ++PI)
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000389 assert(LiveOutCache.lookup(*PI) == I->second && "Bad invariant");
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000390 }
391#endif
392
393 // Since we went through the trouble of a full BFS visiting all reaching defs,
394 // the values in LiveIn are now accurate. No more phi-defs are needed
395 // for these blocks, so we can color the live ranges.
396 // This makes the next mapValue call much faster.
397 for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) {
398 MachineBasicBlock *MBB = LiveIn[i]->getBlock();
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000399 SlotIndex Start = LIS.getMBBStartIdx(MBB);
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000400 VNInfo *VNI = LiveOutCache.lookup(MBB).first;
Jakob Stoklund Olesen08eb8dd2011-02-03 20:29:36 +0000401
402 // Anything in LiveIn other than IdxMBB is live-through.
403 // In IdxMBB, we should stop at Idx unless the same value is live-out.
404 if (MBB == IdxMBB && IdxVNI != VNI)
405 LI->addRange(LiveRange(Start, Idx.getNextSlot(), IdxVNI));
406 else
407 LI->addRange(LiveRange(Start, LIS.getMBBEndIdx(MBB), VNI));
Jakob Stoklund Olesene1dde7b2010-10-28 20:34:52 +0000408 }
409
Jakob Stoklund Olesen1407c842010-08-18 19:00:08 +0000410 return IdxVNI;
411}
412
Jakob Stoklund Olesend7ca5772011-01-20 17:45:20 +0000413#ifndef NDEBUG
414void LiveIntervalMap::dumpCache() {
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000415 for (LiveOutMap::iterator I = LiveOutCache.begin(), E = LiveOutCache.end();
Jakob Stoklund Olesend7ca5772011-01-20 17:45:20 +0000416 I != E; ++I) {
417 assert(I->first && "Null MBB entry in cache");
418 assert(I->second.first && "Null VNInfo in cache");
419 assert(I->second.second && "Null DomTreeNode in cache");
420 dbgs() << " cache: BB#" << I->first->getNumber()
421 << " has valno #" << I->second.first->id << " from BB#"
422 << I->second.second->getBlock()->getNumber() << ", preds";
423 for (MachineBasicBlock::pred_iterator PI = I->first->pred_begin(),
424 PE = I->first->pred_end(); PI != PE; ++PI)
425 dbgs() << " BB#" << (*PI)->getNumber();
426 dbgs() << '\n';
427 }
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000428 dbgs() << " cache: " << LiveOutCache.size() << " entries.\n";
Jakob Stoklund Olesend7ca5772011-01-20 17:45:20 +0000429}
430#endif
431
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000432// extendTo - Find the last LI value defined in MBB at or before Idx. The
433// ParentLI is assumed to be live at Idx. Extend the live range to Idx.
Jakob Stoklund Olesen1407c842010-08-18 19:00:08 +0000434// Return the found VNInfo, or NULL.
Jakob Stoklund Olesenc95c1462010-10-27 00:39:07 +0000435VNInfo *LiveIntervalMap::extendTo(const MachineBasicBlock *MBB, SlotIndex Idx) {
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000436 assert(LI && "call reset first");
437 LiveInterval::iterator I = std::upper_bound(LI->begin(), LI->end(), Idx);
438 if (I == LI->begin())
Jakob Stoklund Olesen1407c842010-08-18 19:00:08 +0000439 return 0;
440 --I;
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000441 if (I->end <= LIS.getMBBStartIdx(MBB))
Jakob Stoklund Olesen1407c842010-08-18 19:00:08 +0000442 return 0;
Jakob Stoklund Olesenf6a129a2010-09-16 00:01:36 +0000443 if (I->end <= Idx)
444 I->end = Idx.getNextSlot();
Jakob Stoklund Olesen1407c842010-08-18 19:00:08 +0000445 return I->valno;
446}
447
Jakob Stoklund Olesenf6a129a2010-09-16 00:01:36 +0000448
Jakob Stoklund Olesen1407c842010-08-18 19:00:08 +0000449//===----------------------------------------------------------------------===//
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +0000450// Split Editor
451//===----------------------------------------------------------------------===//
452
453/// Create a new SplitEditor for editing the LiveInterval analyzed by SA.
Jakob Stoklund Olesend68f4582010-10-28 20:34:50 +0000454SplitEditor::SplitEditor(SplitAnalysis &sa,
455 LiveIntervals &lis,
456 VirtRegMap &vrm,
457 MachineDominatorTree &mdt,
Jakob Stoklund Olesena17768f2010-10-14 23:49:52 +0000458 LiveRangeEdit &edit)
Jakob Stoklund Olesen0eeca442011-02-19 00:42:33 +0000459 : SA(sa), LIS(lis), VRM(vrm),
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000460 MRI(vrm.getMachineFunction().getRegInfo()),
Eric Christopher0f438112011-02-03 06:18:29 +0000461 MDT(mdt),
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000462 TII(*vrm.getMachineFunction().getTarget().getInstrInfo()),
463 TRI(*vrm.getMachineFunction().getTarget().getRegisterInfo()),
464 Edit(edit),
Eric Christopher0f438112011-02-03 06:18:29 +0000465 OpenIdx(0),
466 RegAssign(Allocator)
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +0000467{
Jakob Stoklund Olesencfa71342010-11-10 19:31:50 +0000468 // We don't need an AliasAnalysis since we will only be performing
469 // cheap-as-a-copy remats anyway.
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000470 Edit.anyRematerializable(LIS, TII, 0);
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +0000471}
472
Eric Christopher0f438112011-02-03 06:18:29 +0000473void SplitEditor::dump() const {
474 if (RegAssign.empty()) {
475 dbgs() << " empty\n";
476 return;
477 }
478
479 for (RegAssignMap::const_iterator I = RegAssign.begin(); I.valid(); ++I)
480 dbgs() << " [" << I.start() << ';' << I.stop() << "):" << I.value();
481 dbgs() << '\n';
Jakob Stoklund Olesen5fa42a42010-09-21 22:32:21 +0000482}
483
Jakob Stoklund Olesen670ccd12011-03-01 23:14:53 +0000484VNInfo *SplitEditor::defValue(unsigned RegIdx,
485 const VNInfo *ParentVNI,
486 SlotIndex Idx) {
487 assert(ParentVNI && "Mapping NULL value");
488 assert(Idx.isValid() && "Invalid SlotIndex");
489 assert(Edit.getParent().getVNInfoAt(Idx) == ParentVNI && "Bad Parent VNI");
490 LiveInterval *LI = Edit.get(RegIdx);
491
492 // Create a new value.
493 VNInfo *VNI = LI->getNextValue(Idx, 0, LIS.getVNInfoAllocator());
494
495 // Preserve the PHIDef bit.
496 if (ParentVNI->isPHIDef() && Idx == ParentVNI->def)
497 VNI->setIsPHIDef(true);
498
499 // Use insert for lookup, so we can add missing values with a second lookup.
500 std::pair<ValueMap::iterator, bool> InsP =
501 Values.insert(std::make_pair(std::make_pair(RegIdx, ParentVNI->id), VNI));
502
503 // This was the first time (RegIdx, ParentVNI) was mapped.
504 // Keep it as a simple def without any liveness.
505 if (InsP.second)
506 return VNI;
507
508 // If the previous value was a simple mapping, add liveness for it now.
509 if (VNInfo *OldVNI = InsP.first->second) {
510 SlotIndex Def = OldVNI->def;
511 LI->addRange(LiveRange(Def, Def.getNextSlot(), OldVNI));
512 // No longer a simple mapping.
513 InsP.first->second = 0;
514 }
515
516 // This is a complex mapping, add liveness for VNI
517 SlotIndex Def = VNI->def;
518 LI->addRange(LiveRange(Def, Def.getNextSlot(), VNI));
519
520 return VNI;
521}
522
523void SplitEditor::markComplexMapped(unsigned RegIdx, const VNInfo *ParentVNI) {
524 assert(ParentVNI && "Mapping NULL value");
525 VNInfo *&VNI = Values[std::make_pair(RegIdx, ParentVNI->id)];
526
527 // ParentVNI was either unmapped or already complex mapped. Either way.
528 if (!VNI)
529 return;
530
531 // This was previously a single mapping. Make sure the old def is represented
532 // by a trivial live range.
533 SlotIndex Def = VNI->def;
534 Edit.get(RegIdx)->addRange(LiveRange(Def, Def.getNextSlot(), VNI));
535 VNI = 0;
536}
537
Eric Christopher0f438112011-02-03 06:18:29 +0000538VNInfo *SplitEditor::defFromParent(unsigned RegIdx,
Jakob Stoklund Olesencfa71342010-11-10 19:31:50 +0000539 VNInfo *ParentVNI,
540 SlotIndex UseIdx,
541 MachineBasicBlock &MBB,
542 MachineBasicBlock::iterator I) {
Jakob Stoklund Olesencfa71342010-11-10 19:31:50 +0000543 MachineInstr *CopyMI = 0;
544 SlotIndex Def;
Eric Christopher0f438112011-02-03 06:18:29 +0000545 LiveInterval *LI = Edit.get(RegIdx);
Jakob Stoklund Olesencfa71342010-11-10 19:31:50 +0000546
547 // Attempt cheap-as-a-copy rematerialization.
548 LiveRangeEdit::Remat RM(ParentVNI);
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000549 if (Edit.canRematerializeAt(RM, UseIdx, true, LIS)) {
Eric Christopher0f438112011-02-03 06:18:29 +0000550 Def = Edit.rematerializeAt(MBB, I, LI->reg, RM, LIS, TII, TRI);
Jakob Stoklund Olesencfa71342010-11-10 19:31:50 +0000551 } else {
552 // Can't remat, just insert a copy from parent.
Eric Christopher0f438112011-02-03 06:18:29 +0000553 CopyMI = BuildMI(MBB, I, DebugLoc(), TII.get(TargetOpcode::COPY), LI->reg)
554 .addReg(Edit.getReg());
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000555 Def = LIS.InsertMachineInstrInMaps(CopyMI).getDefIndex();
Jakob Stoklund Olesencfa71342010-11-10 19:31:50 +0000556 }
557
Jakob Stoklund Olesen670ccd12011-03-01 23:14:53 +0000558 // Temporarily mark all values as complex mapped.
559 markComplexMapped(RegIdx, ParentVNI);
Jakob Stoklund Olesencfa71342010-11-10 19:31:50 +0000560
Jakob Stoklund Olesen670ccd12011-03-01 23:14:53 +0000561 // Define the value in Reg.
562 VNInfo *VNI = defValue(RegIdx, ParentVNI, Def);
563 VNI->setCopy(CopyMI);
Jakob Stoklund Olesencfa71342010-11-10 19:31:50 +0000564 return VNI;
565}
566
Jakob Stoklund Olesen7536f722010-08-04 22:08:39 +0000567/// Create a new virtual register and live interval.
568void SplitEditor::openIntv() {
Eric Christopher0f438112011-02-03 06:18:29 +0000569 assert(!OpenIdx && "Previous LI not closed before openIntv");
Jakob Stoklund Olesenf6a129a2010-09-16 00:01:36 +0000570
Eric Christopher0f438112011-02-03 06:18:29 +0000571 // Create the complement as index 0.
572 if (Edit.empty()) {
573 Edit.create(MRI, LIS, VRM);
574 LIMappers.push_back(LiveIntervalMap(LIS, MDT, Edit.getParent()));
575 LIMappers.back().reset(Edit.get(0));
576 }
577
578 // Create the open interval.
579 OpenIdx = Edit.size();
580 Edit.create(MRI, LIS, VRM);
581 LIMappers.push_back(LiveIntervalMap(LIS, MDT, Edit.getParent()));
582 LIMappers[OpenIdx].reset(Edit.get(OpenIdx));
Jakob Stoklund Olesen7536f722010-08-04 22:08:39 +0000583}
584
Jakob Stoklund Olesen207c8682011-02-03 17:04:16 +0000585SlotIndex SplitEditor::enterIntvBefore(SlotIndex Idx) {
Eric Christopher0f438112011-02-03 06:18:29 +0000586 assert(OpenIdx && "openIntv not called before enterIntvBefore");
Jakob Stoklund Olesen9b24afe2010-10-07 17:56:35 +0000587 DEBUG(dbgs() << " enterIntvBefore " << Idx);
Jakob Stoklund Olesen207c8682011-02-03 17:04:16 +0000588 Idx = Idx.getBaseIndex();
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000589 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx);
Jakob Stoklund Olesenf6a129a2010-09-16 00:01:36 +0000590 if (!ParentVNI) {
Jakob Stoklund Olesen9b24afe2010-10-07 17:56:35 +0000591 DEBUG(dbgs() << ": not live\n");
Jakob Stoklund Olesen207c8682011-02-03 17:04:16 +0000592 return Idx;
Jakob Stoklund Olesenf1b05f22010-08-12 17:07:14 +0000593 }
Jakob Stoklund Olesen207c8682011-02-03 17:04:16 +0000594 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000595 MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
Jakob Stoklund Olesenf6a129a2010-09-16 00:01:36 +0000596 assert(MI && "enterIntvBefore called with invalid index");
Jakob Stoklund Olesencfa71342010-11-10 19:31:50 +0000597
Jakob Stoklund Olesen207c8682011-02-03 17:04:16 +0000598 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Idx, *MI->getParent(), MI);
599 return VNI->def;
Jakob Stoklund Olesenf1b05f22010-08-12 17:07:14 +0000600}
601
Jakob Stoklund Olesen207c8682011-02-03 17:04:16 +0000602SlotIndex SplitEditor::enterIntvAtEnd(MachineBasicBlock &MBB) {
Eric Christopher0f438112011-02-03 06:18:29 +0000603 assert(OpenIdx && "openIntv not called before enterIntvAtEnd");
Jakob Stoklund Olesen207c8682011-02-03 17:04:16 +0000604 SlotIndex End = LIS.getMBBEndIdx(&MBB);
605 SlotIndex Last = End.getPrevSlot();
606 DEBUG(dbgs() << " enterIntvAtEnd BB#" << MBB.getNumber() << ", " << Last);
607 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Last);
Jakob Stoklund Olesenf6a129a2010-09-16 00:01:36 +0000608 if (!ParentVNI) {
Jakob Stoklund Olesen9b24afe2010-10-07 17:56:35 +0000609 DEBUG(dbgs() << ": not live\n");
Jakob Stoklund Olesen207c8682011-02-03 17:04:16 +0000610 return End;
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +0000611 }
Jakob Stoklund Olesen9b24afe2010-10-07 17:56:35 +0000612 DEBUG(dbgs() << ": valno " << ParentVNI->id);
Jakob Stoklund Olesen207c8682011-02-03 17:04:16 +0000613 VNInfo *VNI = defFromParent(OpenIdx, ParentVNI, Last, MBB,
Jakob Stoklund Olesencb640472011-02-04 19:33:11 +0000614 LIS.getLastSplitPoint(Edit.getParent(), &MBB));
Jakob Stoklund Olesen207c8682011-02-03 17:04:16 +0000615 RegAssign.insert(VNI->def, End, OpenIdx);
Eric Christopher0f438112011-02-03 06:18:29 +0000616 DEBUG(dump());
Jakob Stoklund Olesen207c8682011-02-03 17:04:16 +0000617 return VNI->def;
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +0000618}
619
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000620/// useIntv - indicate that all instructions in MBB should use OpenLI.
Jakob Stoklund Olesen7536f722010-08-04 22:08:39 +0000621void SplitEditor::useIntv(const MachineBasicBlock &MBB) {
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000622 useIntv(LIS.getMBBStartIdx(&MBB), LIS.getMBBEndIdx(&MBB));
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +0000623}
624
Jakob Stoklund Olesen7536f722010-08-04 22:08:39 +0000625void SplitEditor::useIntv(SlotIndex Start, SlotIndex End) {
Eric Christopher0f438112011-02-03 06:18:29 +0000626 assert(OpenIdx && "openIntv not called before useIntv");
627 DEBUG(dbgs() << " useIntv [" << Start << ';' << End << "):");
628 RegAssign.insert(Start, End, OpenIdx);
629 DEBUG(dump());
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +0000630}
631
Jakob Stoklund Olesen207c8682011-02-03 17:04:16 +0000632SlotIndex SplitEditor::leaveIntvAfter(SlotIndex Idx) {
Eric Christopher0f438112011-02-03 06:18:29 +0000633 assert(OpenIdx && "openIntv not called before leaveIntvAfter");
Jakob Stoklund Olesen9b24afe2010-10-07 17:56:35 +0000634 DEBUG(dbgs() << " leaveIntvAfter " << Idx);
Jakob Stoklund Olesenf1b05f22010-08-12 17:07:14 +0000635
Jakob Stoklund Olesenf6a129a2010-09-16 00:01:36 +0000636 // The interval must be live beyond the instruction at Idx.
Jakob Stoklund Olesencfa71342010-11-10 19:31:50 +0000637 Idx = Idx.getBoundaryIndex();
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000638 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx);
Jakob Stoklund Olesenf6a129a2010-09-16 00:01:36 +0000639 if (!ParentVNI) {
Jakob Stoklund Olesen9b24afe2010-10-07 17:56:35 +0000640 DEBUG(dbgs() << ": not live\n");
Jakob Stoklund Olesen207c8682011-02-03 17:04:16 +0000641 return Idx.getNextSlot();
Jakob Stoklund Olesenf1b05f22010-08-12 17:07:14 +0000642 }
Jakob Stoklund Olesen207c8682011-02-03 17:04:16 +0000643 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
Jakob Stoklund Olesenf1b05f22010-08-12 17:07:14 +0000644
Jakob Stoklund Olesen01cb34b2011-02-08 18:50:18 +0000645 MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
646 assert(MI && "No instruction at index");
647 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(),
648 llvm::next(MachineBasicBlock::iterator(MI)));
Jakob Stoklund Olesen207c8682011-02-03 17:04:16 +0000649 return VNI->def;
Jakob Stoklund Olesenf1b05f22010-08-12 17:07:14 +0000650}
651
Jakob Stoklund Olesen9b057772011-02-09 23:30:25 +0000652SlotIndex SplitEditor::leaveIntvBefore(SlotIndex Idx) {
653 assert(OpenIdx && "openIntv not called before leaveIntvBefore");
654 DEBUG(dbgs() << " leaveIntvBefore " << Idx);
655
656 // The interval must be live into the instruction at Idx.
657 Idx = Idx.getBoundaryIndex();
658 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx);
659 if (!ParentVNI) {
660 DEBUG(dbgs() << ": not live\n");
661 return Idx.getNextSlot();
662 }
663 DEBUG(dbgs() << ": valno " << ParentVNI->id << '\n');
664
665 MachineInstr *MI = LIS.getInstructionFromIndex(Idx);
666 assert(MI && "No instruction at index");
667 VNInfo *VNI = defFromParent(0, ParentVNI, Idx, *MI->getParent(), MI);
668 return VNI->def;
669}
670
Jakob Stoklund Olesen207c8682011-02-03 17:04:16 +0000671SlotIndex SplitEditor::leaveIntvAtTop(MachineBasicBlock &MBB) {
Eric Christopher0f438112011-02-03 06:18:29 +0000672 assert(OpenIdx && "openIntv not called before leaveIntvAtTop");
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000673 SlotIndex Start = LIS.getMBBStartIdx(&MBB);
Jakob Stoklund Olesen9b24afe2010-10-07 17:56:35 +0000674 DEBUG(dbgs() << " leaveIntvAtTop BB#" << MBB.getNumber() << ", " << Start);
Jakob Stoklund Olesen7536f722010-08-04 22:08:39 +0000675
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000676 VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Start);
Jakob Stoklund Olesenf6a129a2010-09-16 00:01:36 +0000677 if (!ParentVNI) {
Jakob Stoklund Olesen9b24afe2010-10-07 17:56:35 +0000678 DEBUG(dbgs() << ": not live\n");
Jakob Stoklund Olesen207c8682011-02-03 17:04:16 +0000679 return Start;
Jakob Stoklund Olesen7536f722010-08-04 22:08:39 +0000680 }
681
Eric Christopher0f438112011-02-03 06:18:29 +0000682 VNInfo *VNI = defFromParent(0, ParentVNI, Start, MBB,
Jakob Stoklund Olesencfa71342010-11-10 19:31:50 +0000683 MBB.SkipPHIsAndLabels(MBB.begin()));
Eric Christopher0f438112011-02-03 06:18:29 +0000684 RegAssign.insert(Start, VNI->def, OpenIdx);
685 DEBUG(dump());
Jakob Stoklund Olesen207c8682011-02-03 17:04:16 +0000686 return VNI->def;
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +0000687}
688
Jakob Stoklund Olesen5c716bd2011-02-08 18:50:21 +0000689void SplitEditor::overlapIntv(SlotIndex Start, SlotIndex End) {
690 assert(OpenIdx && "openIntv not called before overlapIntv");
691 assert(Edit.getParent().getVNInfoAt(Start) ==
692 Edit.getParent().getVNInfoAt(End.getPrevSlot()) &&
693 "Parent changes value in extended range");
694 assert(Edit.get(0)->getVNInfoAt(Start) && "Start must come from leaveIntv*");
695 assert(LIS.getMBBFromIndex(Start) == LIS.getMBBFromIndex(End) &&
696 "Range cannot span basic blocks");
697
698 // Treat this as useIntv() for now. The complement interval will be extended
699 // as needed by mapValue().
700 DEBUG(dbgs() << " overlapIntv [" << Start << ';' << End << "):");
701 RegAssign.insert(Start, End, OpenIdx);
702 DEBUG(dump());
703}
704
Jakob Stoklund Olesen7536f722010-08-04 22:08:39 +0000705/// closeIntv - Indicate that we are done editing the currently open
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +0000706/// LiveInterval, and ranges can be trimmed.
Jakob Stoklund Olesen7536f722010-08-04 22:08:39 +0000707void SplitEditor::closeIntv() {
Eric Christopher0f438112011-02-03 06:18:29 +0000708 assert(OpenIdx && "openIntv not called before closeIntv");
709 OpenIdx = 0;
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +0000710}
711
Eric Christopher0f438112011-02-03 06:18:29 +0000712/// rewriteAssigned - Rewrite all uses of Edit.getReg().
713void SplitEditor::rewriteAssigned() {
714 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Edit.getReg()),
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000715 RE = MRI.reg_end(); RI != RE;) {
Jakob Stoklund Olesen74669272010-10-08 23:42:21 +0000716 MachineOperand &MO = RI.getOperand();
717 MachineInstr *MI = MO.getParent();
718 ++RI;
Eric Christopher0f438112011-02-03 06:18:29 +0000719 // LiveDebugVariables should have handled all DBG_VALUE instructions.
Jakob Stoklund Olesen74669272010-10-08 23:42:21 +0000720 if (MI->isDebugValue()) {
721 DEBUG(dbgs() << "Zapping " << *MI);
Jakob Stoklund Olesen74669272010-10-08 23:42:21 +0000722 MO.setReg(0);
723 continue;
724 }
Jakob Stoklund Olesena372d162011-02-09 21:52:09 +0000725
726 // <undef> operands don't really read the register, so just assign them to
727 // the complement.
728 if (MO.isUse() && MO.isUndef()) {
729 MO.setReg(Edit.get(0)->reg);
730 continue;
731 }
732
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000733 SlotIndex Idx = LIS.getInstructionIndex(MI);
Jakob Stoklund Olesen74669272010-10-08 23:42:21 +0000734 Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex();
Eric Christopher0f438112011-02-03 06:18:29 +0000735
736 // Rewrite to the mapped register at Idx.
737 unsigned RegIdx = RegAssign.lookup(Idx);
738 MO.setReg(Edit.get(RegIdx)->reg);
739 DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t'
740 << Idx << ':' << RegIdx << '\t' << *MI);
741
742 // Extend liveness to Idx.
743 const VNInfo *ParentVNI = Edit.getParent().getVNInfoAt(Idx);
744 LIMappers[RegIdx].mapValue(ParentVNI, Idx);
Jakob Stoklund Olesen74669272010-10-08 23:42:21 +0000745 }
746}
747
Eric Christopher0f438112011-02-03 06:18:29 +0000748/// rewriteSplit - Rewrite uses of Intvs[0] according to the ConEQ mapping.
749void SplitEditor::rewriteComponents(const SmallVectorImpl<LiveInterval*> &Intvs,
750 const ConnectedVNInfoEqClasses &ConEq) {
751 for (MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(Intvs[0]->reg),
752 RE = MRI.reg_end(); RI != RE;) {
753 MachineOperand &MO = RI.getOperand();
754 MachineInstr *MI = MO.getParent();
755 ++RI;
756 if (MO.isUse() && MO.isUndef())
Jakob Stoklund Olesen9d999772010-10-21 18:47:08 +0000757 continue;
Eric Christopher0f438112011-02-03 06:18:29 +0000758 // DBG_VALUE instructions should have been eliminated earlier.
759 SlotIndex Idx = LIS.getInstructionIndex(MI);
760 Idx = MO.isUse() ? Idx.getUseIndex() : Idx.getDefIndex();
761 DEBUG(dbgs() << " rewr BB#" << MI->getParent()->getNumber() << '\t'
762 << Idx << ':');
763 const VNInfo *VNI = Intvs[0]->getVNInfoAt(Idx);
764 assert(VNI && "Interval not live at use.");
765 MO.setReg(Intvs[ConEq.getEqClass(VNI)]->reg);
766 DEBUG(dbgs() << VNI->id << '\t' << *MI);
Eric Christopher463a2972011-02-03 05:40:54 +0000767 }
Eric Christopher463a2972011-02-03 05:40:54 +0000768}
Jakob Stoklund Olesen2cd21112011-02-03 00:54:23 +0000769
Eric Christopher463a2972011-02-03 05:40:54 +0000770void SplitEditor::finish() {
Eric Christopher0f438112011-02-03 06:18:29 +0000771 assert(OpenIdx == 0 && "Previous LI not closed before rewrite");
Eric Christopher463a2972011-02-03 05:40:54 +0000772
Eric Christopher0f438112011-02-03 06:18:29 +0000773 // At this point, the live intervals in Edit contain VNInfos corresponding to
774 // the inserted copies.
775
776 // Add the original defs from the parent interval.
777 for (LiveInterval::const_vni_iterator I = Edit.getParent().vni_begin(),
778 E = Edit.getParent().vni_end(); I != E; ++I) {
779 const VNInfo *ParentVNI = *I;
Jakob Stoklund Olesen9ecd1e72011-02-04 00:59:23 +0000780 if (ParentVNI->isUnused())
781 continue;
Jakob Stoklund Olesen670ccd12011-03-01 23:14:53 +0000782 unsigned RegIdx = RegAssign.lookup(ParentVNI->def);
Eric Christopher0f438112011-02-03 06:18:29 +0000783 // Mark all values as complex to force liveness computation.
784 // This should really only be necessary for remat victims, but we are lazy.
Jakob Stoklund Olesen670ccd12011-03-01 23:14:53 +0000785 markComplexMapped(RegIdx, ParentVNI);
786 defValue(RegIdx, ParentVNI, ParentVNI->def);
Eric Christopher0f438112011-02-03 06:18:29 +0000787 }
788
789#ifndef NDEBUG
790 // Every new interval must have a def by now, otherwise the split is bogus.
791 for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I)
792 assert((*I)->hasAtLeastOneValue() && "Split interval has no value");
793#endif
794
795 // FIXME: Don't recompute the liveness of all values, infer it from the
796 // overlaps between the parent live interval and RegAssign.
797 // The mapValue algorithm is only necessary when:
798 // - The parent value maps to multiple defs, and new phis are needed, or
799 // - The value has been rematerialized before some uses, and we want to
800 // minimize the live range so it only reaches the remaining uses.
801 // All other values have simple liveness that can be computed from RegAssign
802 // and the parent live interval.
803
804 // Extend live ranges to be live-out for successor PHI values.
805 for (LiveInterval::const_vni_iterator I = Edit.getParent().vni_begin(),
806 E = Edit.getParent().vni_end(); I != E; ++I) {
807 const VNInfo *PHIVNI = *I;
Jakob Stoklund Olesen9ecd1e72011-02-04 00:59:23 +0000808 if (PHIVNI->isUnused() || !PHIVNI->isPHIDef())
Eric Christopher0f438112011-02-03 06:18:29 +0000809 continue;
Jakob Stoklund Olesenc50f0772011-02-03 20:29:39 +0000810 unsigned RegIdx = RegAssign.lookup(PHIVNI->def);
811 LiveIntervalMap &LIM = LIMappers[RegIdx];
Eric Christopher0f438112011-02-03 06:18:29 +0000812 MachineBasicBlock *MBB = LIS.getMBBFromIndex(PHIVNI->def);
Jakob Stoklund Olesenc50f0772011-02-03 20:29:39 +0000813 DEBUG(dbgs() << " map phi in BB#" << MBB->getNumber() << '@' << PHIVNI->def
814 << " -> " << RegIdx << '\n');
Eric Christopher0f438112011-02-03 06:18:29 +0000815 for (MachineBasicBlock::pred_iterator PI = MBB->pred_begin(),
816 PE = MBB->pred_end(); PI != PE; ++PI) {
817 SlotIndex End = LIS.getMBBEndIdx(*PI).getPrevSlot();
Jakob Stoklund Olesenc50f0772011-02-03 20:29:39 +0000818 DEBUG(dbgs() << " pred BB#" << (*PI)->getNumber() << '@' << End);
Eric Christopher0f438112011-02-03 06:18:29 +0000819 // The predecessor may not have a live-out value. That is OK, like an
820 // undef PHI operand.
Jakob Stoklund Olesenc50f0772011-02-03 20:29:39 +0000821 if (VNInfo *VNI = Edit.getParent().getVNInfoAt(End)) {
822 DEBUG(dbgs() << " has parent valno #" << VNI->id << " live out\n");
823 assert(RegAssign.lookup(End) == RegIdx &&
824 "Different register assignment in phi predecessor");
Eric Christopher0f438112011-02-03 06:18:29 +0000825 LIM.mapValue(VNI, End);
Jakob Stoklund Olesenc50f0772011-02-03 20:29:39 +0000826 }
827 else
828 DEBUG(dbgs() << " is not live-out\n");
Eric Christopher0f438112011-02-03 06:18:29 +0000829 }
Jakob Stoklund Olesenc50f0772011-02-03 20:29:39 +0000830 DEBUG(dbgs() << " " << *LIM.getLI() << '\n');
Eric Christopher0f438112011-02-03 06:18:29 +0000831 }
832
833 // Rewrite instructions.
834 rewriteAssigned();
835
836 // FIXME: Delete defs that were rematted everywhere.
Jakob Stoklund Olesen5fa42a42010-09-21 22:32:21 +0000837
Jakob Stoklund Olesen0253df92010-10-07 23:34:34 +0000838 // Get rid of unused values and set phi-kill flags.
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000839 for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I)
840 (*I)->RenumberValues(LIS);
Jakob Stoklund Olesen5fa42a42010-09-21 22:32:21 +0000841
Jakob Stoklund Olesen3a0e0712010-10-26 22:36:09 +0000842 // Now check if any registers were separated into multiple components.
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000843 ConnectedVNInfoEqClasses ConEQ(LIS);
844 for (unsigned i = 0, e = Edit.size(); i != e; ++i) {
Jakob Stoklund Olesen3a0e0712010-10-26 22:36:09 +0000845 // Don't use iterators, they are invalidated by create() below.
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000846 LiveInterval *li = Edit.get(i);
Jakob Stoklund Olesen3a0e0712010-10-26 22:36:09 +0000847 unsigned NumComp = ConEQ.Classify(li);
848 if (NumComp <= 1)
849 continue;
850 DEBUG(dbgs() << " " << NumComp << " components: " << *li << '\n');
851 SmallVector<LiveInterval*, 8> dups;
852 dups.push_back(li);
853 for (unsigned i = 1; i != NumComp; ++i)
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000854 dups.push_back(&Edit.create(MRI, LIS, VRM));
Eric Christopher0f438112011-02-03 06:18:29 +0000855 rewriteComponents(dups, ConEQ);
Jakob Stoklund Olesen3a0e0712010-10-26 22:36:09 +0000856 ConEQ.Distribute(&dups[0]);
Jakob Stoklund Olesen3a0e0712010-10-26 22:36:09 +0000857 }
858
Jakob Stoklund Olesen08e93b12010-08-10 17:07:22 +0000859 // Calculate spill weight and allocation hints for new intervals.
Jakob Stoklund Olesen0eeca442011-02-19 00:42:33 +0000860 VirtRegAuxInfo vrai(VRM.getMachineFunction(), LIS, SA.Loops);
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000861 for (LiveRangeEdit::iterator I = Edit.begin(), E = Edit.end(); I != E; ++I){
Jakob Stoklund Olesena17768f2010-10-14 23:49:52 +0000862 LiveInterval &li = **I;
Jakob Stoklund Olesen9db3ea42010-08-10 18:37:40 +0000863 vrai.CalculateRegClass(li.reg);
Jakob Stoklund Olesen08e93b12010-08-10 17:07:22 +0000864 vrai.CalculateWeightAndHint(li);
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000865 DEBUG(dbgs() << " new interval " << MRI.getRegClass(li.reg)->getName()
Jakob Stoklund Olesene1f543f2010-08-12 18:50:55 +0000866 << ":" << li << '\n');
Jakob Stoklund Olesen08e93b12010-08-10 17:07:22 +0000867 }
Jakob Stoklund Olesenf0179002010-07-26 23:44:11 +0000868}
869
870
Jakob Stoklund Olesen8ae02632010-07-20 15:41:07 +0000871//===----------------------------------------------------------------------===//
Jakob Stoklund Olesenf1b05f22010-08-12 17:07:14 +0000872// Single Block Splitting
873//===----------------------------------------------------------------------===//
874
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000875/// getMultiUseBlocks - if CurLI has more than one use in a basic block, it
876/// may be an advantage to split CurLI for the duration of the block.
Jakob Stoklund Olesen2bfb3242010-10-22 22:48:56 +0000877bool SplitAnalysis::getMultiUseBlocks(BlockPtrSet &Blocks) {
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000878 // If CurLI is local to one block, there is no point to splitting it.
Jakob Stoklund Olesen9b057772011-02-09 23:30:25 +0000879 if (LiveBlocks.size() <= 1)
Jakob Stoklund Olesen2bfb3242010-10-22 22:48:56 +0000880 return false;
881 // Add blocks with multiple uses.
Jakob Stoklund Olesen9b057772011-02-09 23:30:25 +0000882 for (unsigned i = 0, e = LiveBlocks.size(); i != e; ++i) {
883 const BlockInfo &BI = LiveBlocks[i];
884 if (!BI.Uses)
Jakob Stoklund Olesen2bfb3242010-10-22 22:48:56 +0000885 continue;
Jakob Stoklund Olesen9b057772011-02-09 23:30:25 +0000886 unsigned Instrs = UsingBlocks.lookup(BI.MBB);
887 if (Instrs <= 1)
888 continue;
889 if (Instrs == 2 && BI.LiveIn && BI.LiveOut && !BI.LiveThrough)
890 continue;
891 Blocks.insert(BI.MBB);
892 }
Jakob Stoklund Olesen2bfb3242010-10-22 22:48:56 +0000893 return !Blocks.empty();
894}
895
Jakob Stoklund Olesen07862842011-01-26 00:50:53 +0000896/// splitSingleBlocks - Split CurLI into a separate live interval inside each
Jakob Stoklund Olesen57d0f2d2010-10-05 22:19:33 +0000897/// basic block in Blocks.
898void SplitEditor::splitSingleBlocks(const SplitAnalysis::BlockPtrSet &Blocks) {
Jakob Stoklund Olesene1f543f2010-08-12 18:50:55 +0000899 DEBUG(dbgs() << " splitSingleBlocks for " << Blocks.size() << " blocks.\n");
Jakob Stoklund Olesenf1b05f22010-08-12 17:07:14 +0000900
Jakob Stoklund Olesen0eeca442011-02-19 00:42:33 +0000901 for (unsigned i = 0, e = SA.LiveBlocks.size(); i != e; ++i) {
902 const SplitAnalysis::BlockInfo &BI = SA.LiveBlocks[i];
Jakob Stoklund Olesen9b057772011-02-09 23:30:25 +0000903 if (!BI.Uses || !Blocks.count(BI.MBB))
904 continue;
Jakob Stoklund Olesenf1b05f22010-08-12 17:07:14 +0000905
906 openIntv();
Jakob Stoklund Olesen9b057772011-02-09 23:30:25 +0000907 SlotIndex SegStart = enterIntvBefore(BI.FirstUse);
Jakob Stoklund Olesenc70f6872011-02-23 18:26:31 +0000908 if (!BI.LiveOut || BI.LastUse < BI.LastSplitPoint) {
Jakob Stoklund Olesen9b057772011-02-09 23:30:25 +0000909 useIntv(SegStart, leaveIntvAfter(BI.LastUse));
910 } else {
Jakob Stoklund Olesenc70f6872011-02-23 18:26:31 +0000911 // The last use is after the last valid split point.
Jakob Stoklund Olesen9b057772011-02-09 23:30:25 +0000912 SlotIndex SegStop = leaveIntvBefore(BI.LastSplitPoint);
913 useIntv(SegStart, SegStop);
914 overlapIntv(SegStop, BI.LastUse);
915 }
Jakob Stoklund Olesenf1b05f22010-08-12 17:07:14 +0000916 closeIntv();
917 }
Jakob Stoklund Olesen74669272010-10-08 23:42:21 +0000918 finish();
Jakob Stoklund Olesenf1b05f22010-08-12 17:07:14 +0000919}