blob: fbf2833756ee300894ee9c079791b51176b5d3be [file] [log] [blame]
Chris Lattnera3b8b5c2004-07-23 17:56:30 +00001//===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===//
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +00002//
3// The LLVM Compiler Infrastructure
4//
Chris Lattner4ee451d2007-12-29 20:36:04 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +00007//
8//===----------------------------------------------------------------------===//
9//
10// This file implements the LiveInterval analysis pass which is used
11// by the Linear Scan Register allocator. This pass linearizes the
12// basic blocks of the function in DFS order and uses the
13// LiveVariables pass to conservatively compute live intervals for
14// each virtual and physical register.
15//
16//===----------------------------------------------------------------------===//
17
18#define DEBUG_TYPE "liveintervals"
Chris Lattner3c3fe462005-09-21 04:19:09 +000019#include "llvm/CodeGen/LiveIntervalAnalysis.h"
Misha Brukman08a6c762004-09-03 18:25:53 +000020#include "VirtRegMap.h"
Chris Lattner015959e2004-05-01 21:24:39 +000021#include "llvm/Value.h"
Dan Gohman6d69ba82008-07-25 00:02:30 +000022#include "llvm/Analysis/AliasAnalysis.h"
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000023#include "llvm/CodeGen/LiveVariables.h"
24#include "llvm/CodeGen/MachineFrameInfo.h"
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000025#include "llvm/CodeGen/MachineInstr.h"
Evan Cheng2578ba22009-07-01 01:59:31 +000026#include "llvm/CodeGen/MachineInstrBuilder.h"
Evan Cheng22f07ff2007-12-11 02:09:15 +000027#include "llvm/CodeGen/MachineLoopInfo.h"
Dan Gohmanc76909a2009-09-25 20:36:54 +000028#include "llvm/CodeGen/MachineMemOperand.h"
Chris Lattner84bc5422007-12-31 04:13:23 +000029#include "llvm/CodeGen/MachineRegisterInfo.h"
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000030#include "llvm/CodeGen/Passes.h"
Lang Hames233a60e2009-11-03 23:52:08 +000031#include "llvm/CodeGen/ProcessImplicitDefs.h"
Dan Gohman6f0d0242008-02-10 18:45:23 +000032#include "llvm/Target/TargetRegisterInfo.h"
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000033#include "llvm/Target/TargetInstrInfo.h"
34#include "llvm/Target/TargetMachine.h"
Owen Anderson95dad832008-10-07 20:22:28 +000035#include "llvm/Target/TargetOptions.h"
Reid Spencer551ccae2004-09-01 22:55:40 +000036#include "llvm/Support/CommandLine.h"
37#include "llvm/Support/Debug.h"
Torok Edwin7d696d82009-07-11 13:10:19 +000038#include "llvm/Support/ErrorHandling.h"
39#include "llvm/Support/raw_ostream.h"
Evan Cheng2578ba22009-07-01 01:59:31 +000040#include "llvm/ADT/DepthFirstIterator.h"
41#include "llvm/ADT/SmallSet.h"
Reid Spencer551ccae2004-09-01 22:55:40 +000042#include "llvm/ADT/Statistic.h"
43#include "llvm/ADT/STLExtras.h"
Alkis Evlogimenos20aa4742004-09-03 18:19:51 +000044#include <algorithm>
Lang Hamesf41538d2009-06-02 16:53:25 +000045#include <limits>
Jeff Cohen97af7512006-12-02 02:22:01 +000046#include <cmath>
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000047using namespace llvm;
48
Dan Gohman844731a2008-05-13 00:00:25 +000049// Hidden options for help debugging.
50static cl::opt<bool> DisableReMat("disable-rematerialization",
51 cl::init(false), cl::Hidden);
Evan Cheng81a03822007-11-17 00:40:40 +000052
Evan Cheng752195e2009-09-14 21:33:42 +000053STATISTIC(numIntervals , "Number of original intervals");
54STATISTIC(numFolds , "Number of loads/stores folded into instructions");
55STATISTIC(numSplits , "Number of intervals split");
Chris Lattnercd3245a2006-12-19 22:41:21 +000056
Devang Patel19974732007-05-03 01:11:54 +000057char LiveIntervals::ID = 0;
Dan Gohman844731a2008-05-13 00:00:25 +000058static RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis");
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000059
Chris Lattnerf7da2c72006-08-24 22:43:55 +000060void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
Dan Gohman845012e2009-07-31 23:37:33 +000061 AU.setPreservesCFG();
Dan Gohman6d69ba82008-07-25 00:02:30 +000062 AU.addRequired<AliasAnalysis>();
63 AU.addPreserved<AliasAnalysis>();
David Greene25133302007-06-08 17:18:56 +000064 AU.addPreserved<LiveVariables>();
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +000065 AU.addRequired<LiveVariables>();
Bill Wendling67d65bb2008-01-04 20:54:55 +000066 AU.addPreservedID(MachineLoopInfoID);
67 AU.addPreservedID(MachineDominatorsID);
Owen Anderson95dad832008-10-07 20:22:28 +000068
69 if (!StrongPHIElim) {
70 AU.addPreservedID(PHIEliminationID);
71 AU.addRequiredID(PHIEliminationID);
72 }
73
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +000074 AU.addRequiredID(TwoAddressInstructionPassID);
Lang Hames233a60e2009-11-03 23:52:08 +000075 AU.addPreserved<ProcessImplicitDefs>();
76 AU.addRequired<ProcessImplicitDefs>();
77 AU.addPreserved<SlotIndexes>();
78 AU.addRequiredTransitive<SlotIndexes>();
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +000079 MachineFunctionPass::getAnalysisUsage(AU);
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000080}
81
Chris Lattnerf7da2c72006-08-24 22:43:55 +000082void LiveIntervals::releaseMemory() {
Owen Anderson03857b22008-08-13 21:49:13 +000083 // Free the live intervals themselves.
Owen Anderson20e28392008-08-13 22:08:30 +000084 for (DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.begin(),
Bob Wilsond6a6b3b2010-03-24 20:25:25 +000085 E = r2iMap_.end(); I != E; ++I)
Owen Anderson03857b22008-08-13 21:49:13 +000086 delete I->second;
87
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +000088 r2iMap_.clear();
Lang Hamesffd13262009-07-09 03:57:02 +000089
Evan Chengdd199d22007-09-06 01:07:24 +000090 // Release VNInfo memroy regions after all VNInfo objects are dtor'd.
Benjamin Kramer991de142010-03-30 20:16:45 +000091 VNInfoAllocator.DestroyAll();
Evan Cheng752195e2009-09-14 21:33:42 +000092 while (!CloneMIs.empty()) {
93 MachineInstr *MI = CloneMIs.back();
94 CloneMIs.pop_back();
Evan Cheng1ed99222008-07-19 00:37:25 +000095 mf_->DeleteMachineInstr(MI);
96 }
Alkis Evlogimenos08cec002004-01-31 19:59:32 +000097}
98
Owen Anderson80b3ce62008-05-28 20:54:50 +000099/// runOnMachineFunction - Register allocate the whole function
100///
101bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
102 mf_ = &fn;
103 mri_ = &mf_->getRegInfo();
104 tm_ = &fn.getTarget();
105 tri_ = tm_->getRegisterInfo();
106 tii_ = tm_->getInstrInfo();
Dan Gohman6d69ba82008-07-25 00:02:30 +0000107 aa_ = &getAnalysis<AliasAnalysis>();
Owen Anderson80b3ce62008-05-28 20:54:50 +0000108 lv_ = &getAnalysis<LiveVariables>();
Lang Hames233a60e2009-11-03 23:52:08 +0000109 indexes_ = &getAnalysis<SlotIndexes>();
Owen Anderson80b3ce62008-05-28 20:54:50 +0000110 allocatableRegs_ = tri_->getAllocatableSet(fn);
111
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000112 computeIntervals();
Alkis Evlogimenos843b1602004-02-15 10:24:21 +0000113
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000114 numIntervals += getNumIntervals();
115
Chris Lattner70ca3582004-09-30 15:59:17 +0000116 DEBUG(dump());
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000117 return true;
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000118}
119
Chris Lattner70ca3582004-09-30 15:59:17 +0000120/// print - Implement the dump method.
Chris Lattner45cfe542009-08-23 06:03:38 +0000121void LiveIntervals::print(raw_ostream &OS, const Module* ) const {
Chris Lattner705e07f2009-08-23 03:41:05 +0000122 OS << "********** INTERVALS **********\n";
Chris Lattner8e7a7092005-07-27 23:03:38 +0000123 for (const_iterator I = begin(), E = end(); I != E; ++I) {
Chris Lattner705e07f2009-08-23 03:41:05 +0000124 I->second->print(OS, tri_);
125 OS << "\n";
Chris Lattner8e7a7092005-07-27 23:03:38 +0000126 }
Chris Lattner70ca3582004-09-30 15:59:17 +0000127
Evan Cheng752195e2009-09-14 21:33:42 +0000128 printInstrs(OS);
129}
130
131void LiveIntervals::printInstrs(raw_ostream &OS) const {
Chris Lattner705e07f2009-08-23 03:41:05 +0000132 OS << "********** MACHINEINSTRS **********\n";
133
Chris Lattner3380d5c2009-07-21 21:12:58 +0000134 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
135 mbbi != mbbe; ++mbbi) {
Jakob Stoklund Olesen6cd81032009-11-20 18:54:59 +0000136 OS << "BB#" << mbbi->getNumber()
137 << ":\t\t# derived from " << mbbi->getName() << "\n";
Chris Lattner3380d5c2009-07-21 21:12:58 +0000138 for (MachineBasicBlock::iterator mii = mbbi->begin(),
139 mie = mbbi->end(); mii != mie; ++mii) {
Chris Lattner518bb532010-02-09 19:54:29 +0000140 if (mii->isDebugValue())
Evan Cheng4507f082010-03-16 21:51:27 +0000141 OS << " \t" << *mii;
Dale Johannesen1caedd02010-01-22 22:38:21 +0000142 else
143 OS << getInstructionIndex(mii) << '\t' << *mii;
Chris Lattner3380d5c2009-07-21 21:12:58 +0000144 }
145 }
Chris Lattner70ca3582004-09-30 15:59:17 +0000146}
147
Evan Cheng752195e2009-09-14 21:33:42 +0000148void LiveIntervals::dumpInstrs() const {
David Greene8a342292010-01-04 22:49:02 +0000149 printInstrs(dbgs());
Evan Cheng752195e2009-09-14 21:33:42 +0000150}
151
Jakob Stoklund Olesencf970362009-12-10 17:48:32 +0000152bool LiveIntervals::conflictsWithPhysReg(const LiveInterval &li,
153 VirtRegMap &vrm, unsigned reg) {
154 // We don't handle fancy stuff crossing basic block boundaries
155 if (li.ranges.size() != 1)
156 return true;
157 const LiveRange &range = li.ranges.front();
158 SlotIndex idx = range.start.getBaseIndex();
159 SlotIndex end = range.end.getPrevSlot().getBaseIndex().getNextIndex();
Jakob Stoklund Olesenf4811a92009-12-03 20:49:10 +0000160
Jakob Stoklund Olesencf970362009-12-10 17:48:32 +0000161 // Skip deleted instructions
162 MachineInstr *firstMI = getInstructionFromIndex(idx);
163 while (!firstMI && idx != end) {
164 idx = idx.getNextIndex();
165 firstMI = getInstructionFromIndex(idx);
166 }
167 if (!firstMI)
168 return false;
169
170 // Find last instruction in range
171 SlotIndex lastIdx = end.getPrevIndex();
172 MachineInstr *lastMI = getInstructionFromIndex(lastIdx);
173 while (!lastMI && lastIdx != idx) {
174 lastIdx = lastIdx.getPrevIndex();
175 lastMI = getInstructionFromIndex(lastIdx);
176 }
177 if (!lastMI)
178 return false;
179
180 // Range cannot cross basic block boundaries or terminators
181 MachineBasicBlock *MBB = firstMI->getParent();
182 if (MBB != lastMI->getParent() || lastMI->getDesc().isTerminator())
183 return true;
184
185 MachineBasicBlock::const_iterator E = lastMI;
186 ++E;
187 for (MachineBasicBlock::const_iterator I = firstMI; I != E; ++I) {
188 const MachineInstr &MI = *I;
189
190 // Allow copies to and from li.reg
191 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
192 if (tii_->isMoveInstr(MI, SrcReg, DstReg, SrcSubReg, DstSubReg))
193 if (SrcReg == li.reg || DstReg == li.reg)
194 continue;
195
196 // Check for operands using reg
197 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
198 const MachineOperand& mop = MI.getOperand(i);
199 if (!mop.isReg())
200 continue;
201 unsigned PhysReg = mop.getReg();
202 if (PhysReg == 0 || PhysReg == li.reg)
203 continue;
204 if (TargetRegisterInfo::isVirtualRegister(PhysReg)) {
205 if (!vrm.hasPhys(PhysReg))
Bill Wendlingdc492e02009-12-05 07:30:23 +0000206 continue;
Jakob Stoklund Olesencf970362009-12-10 17:48:32 +0000207 PhysReg = vrm.getPhys(PhysReg);
Evan Chengc92da382007-11-03 07:20:12 +0000208 }
Jakob Stoklund Olesencf970362009-12-10 17:48:32 +0000209 if (PhysReg && tri_->regsOverlap(PhysReg, reg))
210 return true;
Evan Chengc92da382007-11-03 07:20:12 +0000211 }
212 }
213
Jakob Stoklund Olesencf970362009-12-10 17:48:32 +0000214 // No conflicts found.
Evan Chengc92da382007-11-03 07:20:12 +0000215 return false;
216}
217
Jakob Stoklund Olesena24986d2010-06-24 18:15:01 +0000218bool LiveIntervals::conflictsWithAliasRef(LiveInterval &li, unsigned Reg,
Evan Cheng8f90b6e2009-01-07 02:08:57 +0000219 SmallPtrSet<MachineInstr*,32> &JoinedCopies) {
220 for (LiveInterval::Ranges::const_iterator
221 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
Lang Hames233a60e2009-11-03 23:52:08 +0000222 for (SlotIndex index = I->start.getBaseIndex(),
223 end = I->end.getPrevSlot().getBaseIndex().getNextIndex();
224 index != end;
225 index = index.getNextIndex()) {
Jakob Stoklund Olesenf4811a92009-12-03 20:49:10 +0000226 MachineInstr *MI = getInstructionFromIndex(index);
227 if (!MI)
228 continue; // skip deleted instructions
Evan Cheng8f90b6e2009-01-07 02:08:57 +0000229
230 if (JoinedCopies.count(MI))
231 continue;
232 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
233 MachineOperand& MO = MI->getOperand(i);
234 if (!MO.isReg())
235 continue;
Jakob Stoklund Olesenb8ac3b02010-06-24 00:52:22 +0000236 unsigned PhysReg = MO.getReg();
Jakob Stoklund Olesena24986d2010-06-24 18:15:01 +0000237 if (PhysReg == 0 || PhysReg == Reg ||
238 TargetRegisterInfo::isVirtualRegister(PhysReg))
Jakob Stoklund Olesenb8ac3b02010-06-24 00:52:22 +0000239 continue;
Jakob Stoklund Olesena24986d2010-06-24 18:15:01 +0000240 if (tri_->regsOverlap(Reg, PhysReg))
Evan Cheng8f90b6e2009-01-07 02:08:57 +0000241 return true;
242 }
243 }
244 }
245
246 return false;
247}
248
Daniel Dunbar504f9a62009-09-15 20:31:12 +0000249#ifndef NDEBUG
Evan Cheng752195e2009-09-14 21:33:42 +0000250static void printRegName(unsigned reg, const TargetRegisterInfo* tri_) {
Dan Gohman6f0d0242008-02-10 18:45:23 +0000251 if (TargetRegisterInfo::isPhysicalRegister(reg))
David Greene8a342292010-01-04 22:49:02 +0000252 dbgs() << tri_->getName(reg);
Evan Cheng549f27d32007-08-13 23:45:17 +0000253 else
David Greene8a342292010-01-04 22:49:02 +0000254 dbgs() << "%reg" << reg;
Evan Cheng549f27d32007-08-13 23:45:17 +0000255}
Daniel Dunbar504f9a62009-09-15 20:31:12 +0000256#endif
Evan Cheng549f27d32007-08-13 23:45:17 +0000257
Evan Chengafff40a2010-05-04 20:26:52 +0000258static
Evan Cheng37499432010-05-05 18:27:40 +0000259bool MultipleDefsBySameMI(const MachineInstr &MI, unsigned MOIdx) {
Evan Chengafff40a2010-05-04 20:26:52 +0000260 unsigned Reg = MI.getOperand(MOIdx).getReg();
261 for (unsigned i = MOIdx+1, e = MI.getNumOperands(); i < e; ++i) {
262 const MachineOperand &MO = MI.getOperand(i);
263 if (!MO.isReg())
264 continue;
265 if (MO.getReg() == Reg && MO.isDef()) {
266 assert(MI.getOperand(MOIdx).getSubReg() != MO.getSubReg() &&
267 MI.getOperand(MOIdx).getSubReg() &&
268 MO.getSubReg());
269 return true;
270 }
271 }
272 return false;
273}
274
Evan Cheng37499432010-05-05 18:27:40 +0000275/// isPartialRedef - Return true if the specified def at the specific index is
276/// partially re-defining the specified live interval. A common case of this is
277/// a definition of the sub-register.
278bool LiveIntervals::isPartialRedef(SlotIndex MIIdx, MachineOperand &MO,
279 LiveInterval &interval) {
280 if (!MO.getSubReg() || MO.isEarlyClobber())
281 return false;
282
283 SlotIndex RedefIndex = MIIdx.getDefIndex();
284 const LiveRange *OldLR =
285 interval.getLiveRangeContaining(RedefIndex.getUseIndex());
286 if (OldLR->valno->isDefAccurate()) {
287 MachineInstr *DefMI = getInstructionFromIndex(OldLR->valno->def);
288 return DefMI->findRegisterDefOperandIdx(interval.reg) != -1;
289 }
290 return false;
291}
292
Chris Lattnerbe4f88a2006-08-22 18:19:46 +0000293void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000294 MachineBasicBlock::iterator mi,
Lang Hames233a60e2009-11-03 23:52:08 +0000295 SlotIndex MIIdx,
Lang Hames86511252009-09-04 20:41:11 +0000296 MachineOperand& MO,
Evan Chengef0732d2008-07-10 07:35:43 +0000297 unsigned MOIdx,
Chris Lattnerbe4f88a2006-08-22 18:19:46 +0000298 LiveInterval &interval) {
Bill Wendling8e6179f2009-08-22 20:18:03 +0000299 DEBUG({
David Greene8a342292010-01-04 22:49:02 +0000300 dbgs() << "\t\tregister: ";
Evan Cheng752195e2009-09-14 21:33:42 +0000301 printRegName(interval.reg, tri_);
Bill Wendling8e6179f2009-08-22 20:18:03 +0000302 });
Evan Cheng419852c2008-04-03 16:39:43 +0000303
Alkis Evlogimenos70651572004-08-04 09:46:56 +0000304 // Virtual registers may be defined multiple times (due to phi
305 // elimination and 2-addr elimination). Much of what we do only has to be
306 // done once for the vreg. We use an empty interval to detect the first
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000307 // time we see a vreg.
Evan Chengd129d732009-07-17 19:43:40 +0000308 LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000309 if (interval.empty()) {
310 // Get the Idx of the defining instructions.
Lang Hames233a60e2009-11-03 23:52:08 +0000311 SlotIndex defIndex = MIIdx.getDefIndex();
Dale Johannesen39faac22009-09-20 00:36:41 +0000312 // Earlyclobbers move back one, so that they overlap the live range
313 // of inputs.
Dale Johannesen86b49f82008-09-24 01:07:17 +0000314 if (MO.isEarlyClobber())
Lang Hames233a60e2009-11-03 23:52:08 +0000315 defIndex = MIIdx.getUseIndex();
Jakob Stoklund Olesen63e6a482010-05-21 16:32:16 +0000316
317 // Make sure the first definition is not a partial redefinition. Add an
318 // <imp-def> of the full register.
319 if (MO.getSubReg())
320 mi->addRegisterDefined(interval.reg);
321
Evan Chengc8d044e2008-02-15 18:24:29 +0000322 MachineInstr *CopyMI = NULL;
Evan Cheng04ee5a12009-01-20 19:12:24 +0000323 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
Chris Lattner518bb532010-02-09 19:54:29 +0000324 if (mi->isExtractSubreg() || mi->isInsertSubreg() || mi->isSubregToReg() ||
Jakob Stoklund Olesen0465bcf2010-06-18 22:29:44 +0000325 tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg)) {
Evan Chengc8d044e2008-02-15 18:24:29 +0000326 CopyMI = mi;
Evan Cheng7ecb38b2007-08-29 20:45:00 +0000327
Jakob Stoklund Olesen0465bcf2010-06-18 22:29:44 +0000328 // Some of the REG_SEQUENCE lowering in TwoAddressInstrPass creates
329 // implicit defs without really knowing. It shows up as INSERT_SUBREG
330 // using an undefined register.
331 if (mi->isInsertSubreg())
332 mi->getOperand(1).setIsUndef();
333 }
334
Evan Cheng37499432010-05-05 18:27:40 +0000335 VNInfo *ValNo = interval.getNextValue(defIndex, CopyMI, true,
336 VNInfoAllocator);
Evan Cheng7ecb38b2007-08-29 20:45:00 +0000337 assert(ValNo->id == 0 && "First value in interval is not 0?");
Chris Lattner7ac2d312004-07-24 02:59:07 +0000338
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000339 // Loop over all of the blocks that the vreg is defined in. There are
340 // two cases we have to handle here. The most common case is a vreg
341 // whose lifetime is contained within a basic block. In this case there
342 // will be a single kill, in MBB, which comes after the definition.
343 if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) {
344 // FIXME: what about dead vars?
Lang Hames233a60e2009-11-03 23:52:08 +0000345 SlotIndex killIdx;
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000346 if (vi.Kills[0] != mi)
Lang Hames233a60e2009-11-03 23:52:08 +0000347 killIdx = getInstructionIndex(vi.Kills[0]).getDefIndex();
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000348 else
Lang Hames233a60e2009-11-03 23:52:08 +0000349 killIdx = defIndex.getStoreIndex();
Chris Lattner6097d132004-07-19 02:15:56 +0000350
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000351 // If the kill happens after the definition, we have an intra-block
352 // live range.
353 if (killIdx > defIndex) {
Jeffrey Yasskin493a3d02009-05-26 18:27:15 +0000354 assert(vi.AliveBlocks.empty() &&
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000355 "Shouldn't be alive across any blocks!");
Evan Cheng7ecb38b2007-08-29 20:45:00 +0000356 LiveRange LR(defIndex, killIdx, ValNo);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000357 interval.addRange(LR);
David Greene8a342292010-01-04 22:49:02 +0000358 DEBUG(dbgs() << " +" << LR << "\n");
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000359 return;
360 }
Alkis Evlogimenosdd2cc652003-12-18 08:48:48 +0000361 }
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000362
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000363 // The other case we handle is when a virtual register lives to the end
364 // of the defining block, potentially live across some blocks, then is
365 // live into some number of blocks, but gets killed. Start by adding a
366 // range that goes from this definition to the end of the defining block.
Lang Hames74ab5ee2009-12-22 00:11:50 +0000367 LiveRange NewLR(defIndex, getMBBEndIdx(mbb), ValNo);
David Greene8a342292010-01-04 22:49:02 +0000368 DEBUG(dbgs() << " +" << NewLR);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000369 interval.addRange(NewLR);
370
Jakob Stoklund Olesendcfe5f32010-02-23 22:43:58 +0000371 bool PHIJoin = lv_->isPHIJoin(interval.reg);
372
373 if (PHIJoin) {
374 // A phi join register is killed at the end of the MBB and revived as a new
375 // valno in the killing blocks.
376 assert(vi.AliveBlocks.empty() && "Phi join can't pass through blocks");
377 DEBUG(dbgs() << " phi-join");
Jakob Stoklund Olesendcfe5f32010-02-23 22:43:58 +0000378 ValNo->setHasPHIKill(true);
379 } else {
380 // Iterate over all of the blocks that the variable is completely
381 // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the
382 // live interval.
383 for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(),
384 E = vi.AliveBlocks.end(); I != E; ++I) {
385 MachineBasicBlock *aliveBlock = mf_->getBlockNumbered(*I);
386 LiveRange LR(getMBBStartIdx(aliveBlock), getMBBEndIdx(aliveBlock), ValNo);
387 interval.addRange(LR);
388 DEBUG(dbgs() << " +" << LR);
389 }
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000390 }
391
392 // Finally, this virtual register is live from the start of any killing
393 // block to the 'use' slot of the killing instruction.
394 for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
395 MachineInstr *Kill = vi.Kills[i];
Jakob Stoklund Olesendcfe5f32010-02-23 22:43:58 +0000396 SlotIndex Start = getMBBStartIdx(Kill->getParent());
397 SlotIndex killIdx = getInstructionIndex(Kill).getDefIndex();
398
399 // Create interval with one of a NEW value number. Note that this value
400 // number isn't actually defined by an instruction, weird huh? :)
401 if (PHIJoin) {
402 ValNo = interval.getNextValue(SlotIndex(Start, true), 0, false,
403 VNInfoAllocator);
404 ValNo->setIsPHIDef(true);
405 }
406 LiveRange LR(Start, killIdx, ValNo);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000407 interval.addRange(LR);
David Greene8a342292010-01-04 22:49:02 +0000408 DEBUG(dbgs() << " +" << LR);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000409 }
410
411 } else {
Evan Cheng37499432010-05-05 18:27:40 +0000412 if (MultipleDefsBySameMI(*mi, MOIdx))
Nick Lewycky761fd4c2010-05-20 03:30:09 +0000413 // Multiple defs of the same virtual register by the same instruction.
414 // e.g. %reg1031:5<def>, %reg1031:6<def> = VLD1q16 %reg1024<kill>, ...
Evan Chengafff40a2010-05-04 20:26:52 +0000415 // This is likely due to elimination of REG_SEQUENCE instructions. Return
416 // here since there is nothing to do.
417 return;
418
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000419 // If this is the second time we see a virtual register definition, it
420 // must be due to phi elimination or two addr elimination. If this is
Evan Chengbf105c82006-11-03 03:04:46 +0000421 // the result of two address elimination, then the vreg is one of the
422 // def-and-use register operand.
Evan Cheng37499432010-05-05 18:27:40 +0000423
424 // It may also be partial redef like this:
425 // 80 %reg1041:6<def> = VSHRNv4i16 %reg1034<kill>, 12, pred:14, pred:%reg0
426 // 120 %reg1041:5<def> = VSHRNv4i16 %reg1039<kill>, 12, pred:14, pred:%reg0
427 bool PartReDef = isPartialRedef(MIIdx, MO, interval);
428 if (PartReDef || mi->isRegTiedToUseOperand(MOIdx)) {
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000429 // If this is a two-address definition, then we have already processed
430 // the live range. The only problem is that we didn't realize there
431 // are actually two values in the live interval. Because of this we
432 // need to take the LiveRegion that defines this register and split it
433 // into two values.
Lang Hames233a60e2009-11-03 23:52:08 +0000434 SlotIndex RedefIndex = MIIdx.getDefIndex();
Evan Chengfb112882009-03-23 08:01:15 +0000435 if (MO.isEarlyClobber())
Lang Hames233a60e2009-11-03 23:52:08 +0000436 RedefIndex = MIIdx.getUseIndex();
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000437
Lang Hames35f291d2009-09-12 03:34:03 +0000438 const LiveRange *OldLR =
Lang Hames233a60e2009-11-03 23:52:08 +0000439 interval.getLiveRangeContaining(RedefIndex.getUseIndex());
Evan Cheng7ecb38b2007-08-29 20:45:00 +0000440 VNInfo *OldValNo = OldLR->valno;
Jakob Stoklund Olesenc66d0f22010-06-16 21:29:40 +0000441 SlotIndex DefIndex = OldValNo->def.getDefIndex();
Evan Cheng4f8ff162007-08-11 00:59:19 +0000442
Jakob Stoklund Olesenc66d0f22010-06-16 21:29:40 +0000443 // Delete the previous value, which should be short and continuous,
Chris Lattnerbe4f88a2006-08-22 18:19:46 +0000444 // because the 2-addr copy must be in the same MBB as the redef.
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000445 interval.removeRange(DefIndex, RedefIndex);
Alkis Evlogimenos70651572004-08-04 09:46:56 +0000446
Chris Lattner91725b72006-08-31 05:54:43 +0000447 // The new value number (#1) is defined by the instruction we claimed
448 // defined value #0.
Lang Hames52c1afc2009-08-10 23:43:28 +0000449 VNInfo *ValNo = interval.getNextValue(OldValNo->def, OldValNo->getCopy(),
Lang Hames857c4e02009-06-17 21:01:20 +0000450 false, // update at *
Evan Chengc8d044e2008-02-15 18:24:29 +0000451 VNInfoAllocator);
Lang Hames857c4e02009-06-17 21:01:20 +0000452 ValNo->setFlags(OldValNo->getFlags()); // * <- updating here
453
Chris Lattner91725b72006-08-31 05:54:43 +0000454 // Value#0 is now defined by the 2-addr instruction.
Evan Chengc8d044e2008-02-15 18:24:29 +0000455 OldValNo->def = RedefIndex;
Evan Chengad6c5a22010-05-17 01:47:47 +0000456 OldValNo->setCopy(0);
457
458 // A re-def may be a copy. e.g. %reg1030:6<def> = VMOVD %reg1026, ...
459 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
460 if (PartReDef &&
461 tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg))
462 OldValNo->setCopy(&*mi);
Chris Lattnerbe4f88a2006-08-22 18:19:46 +0000463
464 // Add the new live interval which replaces the range for the input copy.
465 LiveRange LR(DefIndex, RedefIndex, ValNo);
David Greene8a342292010-01-04 22:49:02 +0000466 DEBUG(dbgs() << " replace range with " << LR);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000467 interval.addRange(LR);
468
469 // If this redefinition is dead, we need to add a dummy unit live
470 // range covering the def slot.
Owen Anderson6b098de2008-06-25 23:39:39 +0000471 if (MO.isDead())
Lang Hames233a60e2009-11-03 23:52:08 +0000472 interval.addRange(LiveRange(RedefIndex, RedefIndex.getStoreIndex(),
473 OldValNo));
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000474
Bill Wendling8e6179f2009-08-22 20:18:03 +0000475 DEBUG({
David Greene8a342292010-01-04 22:49:02 +0000476 dbgs() << " RESULT: ";
477 interval.print(dbgs(), tri_);
Bill Wendling8e6179f2009-08-22 20:18:03 +0000478 });
Evan Cheng37499432010-05-05 18:27:40 +0000479 } else if (lv_->isPHIJoin(interval.reg)) {
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000480 // In the case of PHI elimination, each variable definition is only
481 // live until the end of the block. We've already taken care of the
482 // rest of the live range.
Jakob Stoklund Olesendcfe5f32010-02-23 22:43:58 +0000483
Lang Hames233a60e2009-11-03 23:52:08 +0000484 SlotIndex defIndex = MIIdx.getDefIndex();
Evan Chengfb112882009-03-23 08:01:15 +0000485 if (MO.isEarlyClobber())
Lang Hames233a60e2009-11-03 23:52:08 +0000486 defIndex = MIIdx.getUseIndex();
Evan Cheng752195e2009-09-14 21:33:42 +0000487
Evan Cheng7ecb38b2007-08-29 20:45:00 +0000488 VNInfo *ValNo;
Evan Chengc8d044e2008-02-15 18:24:29 +0000489 MachineInstr *CopyMI = NULL;
Evan Cheng04ee5a12009-01-20 19:12:24 +0000490 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
Chris Lattner518bb532010-02-09 19:54:29 +0000491 if (mi->isExtractSubreg() || mi->isInsertSubreg() || mi->isSubregToReg()||
Evan Cheng04ee5a12009-01-20 19:12:24 +0000492 tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg))
Evan Chengc8d044e2008-02-15 18:24:29 +0000493 CopyMI = mi;
Lang Hames857c4e02009-06-17 21:01:20 +0000494 ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator);
Chris Lattner91725b72006-08-31 05:54:43 +0000495
Lang Hames74ab5ee2009-12-22 00:11:50 +0000496 SlotIndex killIndex = getMBBEndIdx(mbb);
Evan Cheng7ecb38b2007-08-29 20:45:00 +0000497 LiveRange LR(defIndex, killIndex, ValNo);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000498 interval.addRange(LR);
Lang Hames857c4e02009-06-17 21:01:20 +0000499 ValNo->setHasPHIKill(true);
Jakob Stoklund Olesendcfe5f32010-02-23 22:43:58 +0000500 DEBUG(dbgs() << " phi-join +" << LR);
Evan Cheng37499432010-05-05 18:27:40 +0000501 } else {
502 llvm_unreachable("Multiply defined register");
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000503 }
504 }
505
David Greene8a342292010-01-04 22:49:02 +0000506 DEBUG(dbgs() << '\n');
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000507}
508
Chris Lattnerf35fef72004-07-23 21:24:19 +0000509void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000510 MachineBasicBlock::iterator mi,
Lang Hames233a60e2009-11-03 23:52:08 +0000511 SlotIndex MIIdx,
Owen Anderson6b098de2008-06-25 23:39:39 +0000512 MachineOperand& MO,
Chris Lattner91725b72006-08-31 05:54:43 +0000513 LiveInterval &interval,
Evan Chengc8d044e2008-02-15 18:24:29 +0000514 MachineInstr *CopyMI) {
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000515 // A physical register cannot be live across basic block, so its
516 // lifetime must end somewhere in its defining basic block.
Bill Wendling8e6179f2009-08-22 20:18:03 +0000517 DEBUG({
David Greene8a342292010-01-04 22:49:02 +0000518 dbgs() << "\t\tregister: ";
Evan Cheng752195e2009-09-14 21:33:42 +0000519 printRegName(interval.reg, tri_);
Bill Wendling8e6179f2009-08-22 20:18:03 +0000520 });
Alkis Evlogimenos02ba13c2004-01-31 23:13:30 +0000521
Lang Hames233a60e2009-11-03 23:52:08 +0000522 SlotIndex baseIndex = MIIdx;
523 SlotIndex start = baseIndex.getDefIndex();
Dale Johannesen86b49f82008-09-24 01:07:17 +0000524 // Earlyclobbers move back one.
525 if (MO.isEarlyClobber())
Lang Hames233a60e2009-11-03 23:52:08 +0000526 start = MIIdx.getUseIndex();
527 SlotIndex end = start;
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000528
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000529 // If it is not used after definition, it is considered dead at
530 // the instruction defining it. Hence its interval is:
531 // [defSlot(def), defSlot(def)+1)
Dale Johannesen39faac22009-09-20 00:36:41 +0000532 // For earlyclobbers, the defSlot was pushed back one; the extra
533 // advance below compensates.
Owen Anderson6b098de2008-06-25 23:39:39 +0000534 if (MO.isDead()) {
David Greene8a342292010-01-04 22:49:02 +0000535 DEBUG(dbgs() << " dead");
Lang Hames233a60e2009-11-03 23:52:08 +0000536 end = start.getStoreIndex();
Chris Lattnerab4b66d2005-08-23 22:51:41 +0000537 goto exit;
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000538 }
539
540 // If it is not dead on definition, it must be killed by a
541 // subsequent instruction. Hence its interval is:
542 // [defSlot(def), useSlot(kill)+1)
Lang Hames233a60e2009-11-03 23:52:08 +0000543 baseIndex = baseIndex.getNextIndex();
Chris Lattner5ab6f5f2005-09-02 00:20:32 +0000544 while (++mi != MBB->end()) {
Lang Hames233a60e2009-11-03 23:52:08 +0000545
Dale Johannesenbd635202010-02-10 00:55:42 +0000546 if (mi->isDebugValue())
547 continue;
Lang Hames233a60e2009-11-03 23:52:08 +0000548 if (getInstructionFromIndex(baseIndex) == 0)
549 baseIndex = indexes_->getNextNonNullIndex(baseIndex);
550
Evan Cheng6130f662008-03-05 00:59:57 +0000551 if (mi->killsRegister(interval.reg, tri_)) {
David Greene8a342292010-01-04 22:49:02 +0000552 DEBUG(dbgs() << " killed");
Lang Hames233a60e2009-11-03 23:52:08 +0000553 end = baseIndex.getDefIndex();
Chris Lattnerab4b66d2005-08-23 22:51:41 +0000554 goto exit;
Evan Chengc45288e2009-04-27 20:42:46 +0000555 } else {
Evan Cheng1015ba72010-05-21 20:53:24 +0000556 int DefIdx = mi->findRegisterDefOperandIdx(interval.reg,false,false,tri_);
Evan Chengc45288e2009-04-27 20:42:46 +0000557 if (DefIdx != -1) {
558 if (mi->isRegTiedToUseOperand(DefIdx)) {
559 // Two-address instruction.
Lang Hames233a60e2009-11-03 23:52:08 +0000560 end = baseIndex.getDefIndex();
Evan Chengc45288e2009-04-27 20:42:46 +0000561 } else {
562 // Another instruction redefines the register before it is ever read.
Dale Johannesenbd635202010-02-10 00:55:42 +0000563 // Then the register is essentially dead at the instruction that
564 // defines it. Hence its interval is:
Evan Chengc45288e2009-04-27 20:42:46 +0000565 // [defSlot(def), defSlot(def)+1)
David Greene8a342292010-01-04 22:49:02 +0000566 DEBUG(dbgs() << " dead");
Lang Hames233a60e2009-11-03 23:52:08 +0000567 end = start.getStoreIndex();
Evan Chengc45288e2009-04-27 20:42:46 +0000568 }
569 goto exit;
570 }
Alkis Evlogimenosaf254732004-01-13 22:26:14 +0000571 }
Owen Anderson7fbad272008-07-23 21:37:49 +0000572
Lang Hames233a60e2009-11-03 23:52:08 +0000573 baseIndex = baseIndex.getNextIndex();
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000574 }
Chris Lattner5ab6f5f2005-09-02 00:20:32 +0000575
576 // The only case we should have a dead physreg here without a killing or
577 // instruction where we know it's dead is if it is live-in to the function
Evan Chengd521bc92009-04-27 17:36:47 +0000578 // and never used. Another possible case is the implicit use of the
579 // physical register has been deleted by two-address pass.
Lang Hames233a60e2009-11-03 23:52:08 +0000580 end = start.getStoreIndex();
Alkis Evlogimenos02ba13c2004-01-31 23:13:30 +0000581
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000582exit:
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000583 assert(start < end && "did not find end of interval?");
Chris Lattnerf768bba2005-03-09 23:05:19 +0000584
Evan Cheng24a3cc42007-04-25 07:30:23 +0000585 // Already exists? Extend old live interval.
586 LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start);
Evan Cheng5379f412008-12-19 20:58:01 +0000587 bool Extend = OldLR != interval.end();
588 VNInfo *ValNo = Extend
Lang Hames857c4e02009-06-17 21:01:20 +0000589 ? OldLR->valno : interval.getNextValue(start, CopyMI, true, VNInfoAllocator);
Evan Cheng5379f412008-12-19 20:58:01 +0000590 if (MO.isEarlyClobber() && Extend)
Lang Hames857c4e02009-06-17 21:01:20 +0000591 ValNo->setHasRedefByEC(true);
Evan Cheng7ecb38b2007-08-29 20:45:00 +0000592 LiveRange LR(start, end, ValNo);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000593 interval.addRange(LR);
David Greene8a342292010-01-04 22:49:02 +0000594 DEBUG(dbgs() << " +" << LR << '\n');
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000595}
596
Chris Lattnerf35fef72004-07-23 21:24:19 +0000597void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
598 MachineBasicBlock::iterator MI,
Lang Hames233a60e2009-11-03 23:52:08 +0000599 SlotIndex MIIdx,
Evan Chengef0732d2008-07-10 07:35:43 +0000600 MachineOperand& MO,
601 unsigned MOIdx) {
Owen Anderson6b098de2008-06-25 23:39:39 +0000602 if (TargetRegisterInfo::isVirtualRegister(MO.getReg()))
Evan Chengef0732d2008-07-10 07:35:43 +0000603 handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx,
Owen Anderson6b098de2008-06-25 23:39:39 +0000604 getOrCreateInterval(MO.getReg()));
605 else if (allocatableRegs_[MO.getReg()]) {
Evan Chengc8d044e2008-02-15 18:24:29 +0000606 MachineInstr *CopyMI = NULL;
Evan Cheng04ee5a12009-01-20 19:12:24 +0000607 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
Chris Lattner518bb532010-02-09 19:54:29 +0000608 if (MI->isExtractSubreg() || MI->isInsertSubreg() || MI->isSubregToReg() ||
Evan Cheng04ee5a12009-01-20 19:12:24 +0000609 tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg))
Evan Chengc8d044e2008-02-15 18:24:29 +0000610 CopyMI = MI;
Evan Chengc45288e2009-04-27 20:42:46 +0000611 handlePhysicalRegisterDef(MBB, MI, MIIdx, MO,
Owen Anderson6b098de2008-06-25 23:39:39 +0000612 getOrCreateInterval(MO.getReg()), CopyMI);
Evan Cheng24a3cc42007-04-25 07:30:23 +0000613 // Def of a register also defines its sub-registers.
Owen Anderson6b098de2008-06-25 23:39:39 +0000614 for (const unsigned* AS = tri_->getSubRegisters(MO.getReg()); *AS; ++AS)
Evan Cheng6130f662008-03-05 00:59:57 +0000615 // If MI also modifies the sub-register explicitly, avoid processing it
616 // more than once. Do not pass in TRI here so it checks for exact match.
Evan Cheng1015ba72010-05-21 20:53:24 +0000617 if (!MI->definesRegister(*AS))
Evan Chengc45288e2009-04-27 20:42:46 +0000618 handlePhysicalRegisterDef(MBB, MI, MIIdx, MO,
Owen Anderson6b098de2008-06-25 23:39:39 +0000619 getOrCreateInterval(*AS), 0);
Chris Lattnerf35fef72004-07-23 21:24:19 +0000620 }
Alkis Evlogimenos4d46e1e2004-01-31 14:37:41 +0000621}
622
Evan Chengb371f452007-02-19 21:49:54 +0000623void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
Lang Hames233a60e2009-11-03 23:52:08 +0000624 SlotIndex MIIdx,
Evan Cheng24a3cc42007-04-25 07:30:23 +0000625 LiveInterval &interval, bool isAlias) {
Bill Wendling8e6179f2009-08-22 20:18:03 +0000626 DEBUG({
David Greene8a342292010-01-04 22:49:02 +0000627 dbgs() << "\t\tlivein register: ";
Evan Cheng752195e2009-09-14 21:33:42 +0000628 printRegName(interval.reg, tri_);
Bill Wendling8e6179f2009-08-22 20:18:03 +0000629 });
Evan Chengb371f452007-02-19 21:49:54 +0000630
631 // Look for kills, if it reaches a def before it's killed, then it shouldn't
632 // be considered a livein.
633 MachineBasicBlock::iterator mi = MBB->begin();
Evan Cheng4507f082010-03-16 21:51:27 +0000634 MachineBasicBlock::iterator E = MBB->end();
635 // Skip over DBG_VALUE at the start of the MBB.
636 if (mi != E && mi->isDebugValue()) {
637 while (++mi != E && mi->isDebugValue())
638 ;
639 if (mi == E)
640 // MBB is empty except for DBG_VALUE's.
641 return;
642 }
643
Lang Hames233a60e2009-11-03 23:52:08 +0000644 SlotIndex baseIndex = MIIdx;
645 SlotIndex start = baseIndex;
646 if (getInstructionFromIndex(baseIndex) == 0)
647 baseIndex = indexes_->getNextNonNullIndex(baseIndex);
648
649 SlotIndex end = baseIndex;
Evan Cheng0076c612009-03-05 03:34:26 +0000650 bool SeenDefUse = false;
Evan Chengb371f452007-02-19 21:49:54 +0000651
Dale Johannesenbd635202010-02-10 00:55:42 +0000652 while (mi != E) {
Dale Johannesen1d0aeab2010-02-10 01:31:26 +0000653 if (mi->killsRegister(interval.reg, tri_)) {
654 DEBUG(dbgs() << " killed");
655 end = baseIndex.getDefIndex();
656 SeenDefUse = true;
657 break;
Evan Cheng1015ba72010-05-21 20:53:24 +0000658 } else if (mi->definesRegister(interval.reg, tri_)) {
Dale Johannesen1d0aeab2010-02-10 01:31:26 +0000659 // Another instruction redefines the register before it is ever read.
660 // Then the register is essentially dead at the instruction that defines
661 // it. Hence its interval is:
662 // [defSlot(def), defSlot(def)+1)
663 DEBUG(dbgs() << " dead");
664 end = start.getStoreIndex();
665 SeenDefUse = true;
666 break;
667 }
668
Evan Cheng4507f082010-03-16 21:51:27 +0000669 while (++mi != E && mi->isDebugValue())
670 // Skip over DBG_VALUE.
671 ;
672 if (mi != E)
Lang Hames233a60e2009-11-03 23:52:08 +0000673 baseIndex = indexes_->getNextNonNullIndex(baseIndex);
Evan Chengb371f452007-02-19 21:49:54 +0000674 }
675
Evan Cheng75611fb2007-06-27 01:16:36 +0000676 // Live-in register might not be used at all.
Evan Cheng0076c612009-03-05 03:34:26 +0000677 if (!SeenDefUse) {
Evan Cheng292da942007-06-27 18:47:28 +0000678 if (isAlias) {
David Greene8a342292010-01-04 22:49:02 +0000679 DEBUG(dbgs() << " dead");
Lang Hames233a60e2009-11-03 23:52:08 +0000680 end = MIIdx.getStoreIndex();
Evan Cheng292da942007-06-27 18:47:28 +0000681 } else {
David Greene8a342292010-01-04 22:49:02 +0000682 DEBUG(dbgs() << " live through");
Evan Cheng292da942007-06-27 18:47:28 +0000683 end = baseIndex;
684 }
Evan Cheng24a3cc42007-04-25 07:30:23 +0000685 }
686
Lang Hames10382fb2009-06-19 02:17:53 +0000687 VNInfo *vni =
Lang Hames233a60e2009-11-03 23:52:08 +0000688 interval.getNextValue(SlotIndex(getMBBStartIdx(MBB), true),
Lang Hames86511252009-09-04 20:41:11 +0000689 0, false, VNInfoAllocator);
Lang Hamesd21c3162009-06-18 22:01:47 +0000690 vni->setIsPHIDef(true);
691 LiveRange LR(start, end, vni);
Jakob Stoklund Olesen3de23e62009-11-07 01:58:40 +0000692
Jim Laskey9b25b8c2007-02-21 22:41:17 +0000693 interval.addRange(LR);
David Greene8a342292010-01-04 22:49:02 +0000694 DEBUG(dbgs() << " +" << LR << '\n');
Evan Chengb371f452007-02-19 21:49:54 +0000695}
696
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000697/// computeIntervals - computes the live intervals for virtual
Alkis Evlogimenos4d46e1e2004-01-31 14:37:41 +0000698/// registers. for some ordering of the machine instructions [1,N] a
Alkis Evlogimenos08cec002004-01-31 19:59:32 +0000699/// live interval is an interval [i, j) where 1 <= i <= j < N for
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000700/// which a variable is live
Dale Johannesen91aac102008-09-17 21:13:11 +0000701void LiveIntervals::computeIntervals() {
David Greene8a342292010-01-04 22:49:02 +0000702 DEBUG(dbgs() << "********** COMPUTING LIVE INTERVALS **********\n"
Bill Wendling8e6179f2009-08-22 20:18:03 +0000703 << "********** Function: "
704 << ((Value*)mf_->getFunction())->getName() << '\n');
Evan Chengd129d732009-07-17 19:43:40 +0000705
706 SmallVector<unsigned, 8> UndefUses;
Chris Lattner428b92e2006-09-15 03:57:23 +0000707 for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end();
708 MBBI != E; ++MBBI) {
709 MachineBasicBlock *MBB = MBBI;
Evan Cheng00a99a32010-02-06 09:07:11 +0000710 if (MBB->empty())
711 continue;
712
Owen Anderson134eb732008-09-21 20:43:24 +0000713 // Track the index of the current machine instr.
Lang Hames233a60e2009-11-03 23:52:08 +0000714 SlotIndex MIIndex = getMBBStartIdx(MBB);
Bob Wilsonad98f792010-05-03 21:38:11 +0000715 DEBUG(dbgs() << "BB#" << MBB->getNumber()
716 << ":\t\t# derived from " << MBB->getName() << "\n");
Alkis Evlogimenos6b4edba2003-12-21 20:19:10 +0000717
Dan Gohmancb406c22007-10-03 19:26:29 +0000718 // Create intervals for live-ins to this BB first.
Dan Gohman81bf03e2010-04-13 16:57:55 +0000719 for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(),
Dan Gohmancb406c22007-10-03 19:26:29 +0000720 LE = MBB->livein_end(); LI != LE; ++LI) {
721 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI));
722 // Multiple live-ins can alias the same register.
Dan Gohman6f0d0242008-02-10 18:45:23 +0000723 for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS)
Dan Gohmancb406c22007-10-03 19:26:29 +0000724 if (!hasInterval(*AS))
725 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS),
726 true);
Chris Lattnerdffb2e82006-09-04 18:27:40 +0000727 }
728
Owen Anderson99500ae2008-09-15 22:00:38 +0000729 // Skip over empty initial indices.
Lang Hames233a60e2009-11-03 23:52:08 +0000730 if (getInstructionFromIndex(MIIndex) == 0)
731 MIIndex = indexes_->getNextNonNullIndex(MIIndex);
Owen Anderson99500ae2008-09-15 22:00:38 +0000732
Dale Johannesen1caedd02010-01-22 22:38:21 +0000733 for (MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
734 MI != miEnd; ++MI) {
David Greene8a342292010-01-04 22:49:02 +0000735 DEBUG(dbgs() << MIIndex << "\t" << *MI);
Chris Lattner518bb532010-02-09 19:54:29 +0000736 if (MI->isDebugValue())
Dale Johannesen1caedd02010-01-22 22:38:21 +0000737 continue;
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000738
Evan Cheng438f7bc2006-11-10 08:43:01 +0000739 // Handle defs.
Chris Lattner428b92e2006-09-15 03:57:23 +0000740 for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
741 MachineOperand &MO = MI->getOperand(i);
Evan Chengd129d732009-07-17 19:43:40 +0000742 if (!MO.isReg() || !MO.getReg())
743 continue;
744
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000745 // handle register defs - build intervals
Evan Chengd129d732009-07-17 19:43:40 +0000746 if (MO.isDef())
Evan Chengef0732d2008-07-10 07:35:43 +0000747 handleRegisterDef(MBB, MI, MIIndex, MO, i);
Evan Chengd129d732009-07-17 19:43:40 +0000748 else if (MO.isUndef())
749 UndefUses.push_back(MO.getReg());
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000750 }
Owen Anderson7fbad272008-07-23 21:37:49 +0000751
Lang Hames233a60e2009-11-03 23:52:08 +0000752 // Move to the next instr slot.
753 MIIndex = indexes_->getNextNonNullIndex(MIIndex);
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000754 }
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000755 }
Evan Chengd129d732009-07-17 19:43:40 +0000756
757 // Create empty intervals for registers defined by implicit_def's (except
758 // for those implicit_def that define values which are liveout of their
759 // blocks.
760 for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) {
761 unsigned UndefReg = UndefUses[i];
762 (void)getOrCreateInterval(UndefReg);
763 }
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000764}
Alkis Evlogimenosb27ef242003-12-05 10:38:28 +0000765
Owen Anderson03857b22008-08-13 21:49:13 +0000766LiveInterval* LiveIntervals::createInterval(unsigned reg) {
Evan Cheng0a1fcce2009-02-08 11:04:35 +0000767 float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F;
Owen Anderson03857b22008-08-13 21:49:13 +0000768 return new LiveInterval(reg, Weight);
Alkis Evlogimenos9a8b4902004-04-09 18:07:57 +0000769}
Evan Chengf2fbca62007-11-12 06:35:08 +0000770
Evan Cheng0a1fcce2009-02-08 11:04:35 +0000771/// dupInterval - Duplicate a live interval. The caller is responsible for
772/// managing the allocated memory.
773LiveInterval* LiveIntervals::dupInterval(LiveInterval *li) {
774 LiveInterval *NewLI = createInterval(li->reg);
Evan Cheng90f95f82009-06-14 20:22:55 +0000775 NewLI->Copy(*li, mri_, getVNInfoAllocator());
Evan Cheng0a1fcce2009-02-08 11:04:35 +0000776 return NewLI;
777}
778
Evan Chengf2fbca62007-11-12 06:35:08 +0000779//===----------------------------------------------------------------------===//
780// Register allocator hooks.
781//
782
Evan Chengd70dbb52008-02-22 09:24:50 +0000783/// getReMatImplicitUse - If the remat definition MI has one (for now, we only
784/// allow one) virtual register operand, then its uses are implicitly using
785/// the register. Returns the virtual register.
786unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li,
787 MachineInstr *MI) const {
788 unsigned RegOp = 0;
789 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
790 MachineOperand &MO = MI->getOperand(i);
Dan Gohmand735b802008-10-03 15:45:36 +0000791 if (!MO.isReg() || !MO.isUse())
Evan Chengd70dbb52008-02-22 09:24:50 +0000792 continue;
793 unsigned Reg = MO.getReg();
794 if (Reg == 0 || Reg == li.reg)
795 continue;
Chris Lattner1873d0c2009-06-27 04:06:41 +0000796
797 if (TargetRegisterInfo::isPhysicalRegister(Reg) &&
798 !allocatableRegs_[Reg])
799 continue;
Evan Chengd70dbb52008-02-22 09:24:50 +0000800 // FIXME: For now, only remat MI with at most one register operand.
801 assert(!RegOp &&
802 "Can't rematerialize instruction with multiple register operand!");
803 RegOp = MO.getReg();
Dan Gohman6d69ba82008-07-25 00:02:30 +0000804#ifndef NDEBUG
Evan Chengd70dbb52008-02-22 09:24:50 +0000805 break;
Dan Gohman6d69ba82008-07-25 00:02:30 +0000806#endif
Evan Chengd70dbb52008-02-22 09:24:50 +0000807 }
808 return RegOp;
809}
810
811/// isValNoAvailableAt - Return true if the val# of the specified interval
812/// which reaches the given instruction also reaches the specified use index.
813bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI,
Lang Hames233a60e2009-11-03 23:52:08 +0000814 SlotIndex UseIdx) const {
815 SlotIndex Index = getInstructionIndex(MI);
Evan Chengd70dbb52008-02-22 09:24:50 +0000816 VNInfo *ValNo = li.FindLiveRangeContaining(Index)->valno;
817 LiveInterval::const_iterator UI = li.FindLiveRangeContaining(UseIdx);
818 return UI != li.end() && UI->valno == ValNo;
819}
820
Evan Chengf2fbca62007-11-12 06:35:08 +0000821/// isReMaterializable - Returns true if the definition MI of the specified
822/// val# of the specified interval is re-materializable.
823bool LiveIntervals::isReMaterializable(const LiveInterval &li,
Evan Cheng5ef3a042007-12-06 00:01:56 +0000824 const VNInfo *ValNo, MachineInstr *MI,
Evan Chengdc377862008-09-30 15:44:16 +0000825 SmallVectorImpl<LiveInterval*> &SpillIs,
Evan Cheng5ef3a042007-12-06 00:01:56 +0000826 bool &isLoad) {
Evan Chengf2fbca62007-11-12 06:35:08 +0000827 if (DisableReMat)
828 return false;
829
Dan Gohmana70dca12009-10-09 23:27:56 +0000830 if (!tii_->isTriviallyReMaterializable(MI, aa_))
831 return false;
Evan Chengdd3465e2008-02-23 01:44:27 +0000832
Dan Gohmana70dca12009-10-09 23:27:56 +0000833 // Target-specific code can mark an instruction as being rematerializable
834 // if it has one virtual reg use, though it had better be something like
835 // a PIC base register which is likely to be live everywhere.
Dan Gohman6d69ba82008-07-25 00:02:30 +0000836 unsigned ImpUse = getReMatImplicitUse(li, MI);
837 if (ImpUse) {
838 const LiveInterval &ImpLi = getInterval(ImpUse);
Evan Cheng28a1e482010-03-30 05:49:07 +0000839 for (MachineRegisterInfo::use_nodbg_iterator
840 ri = mri_->use_nodbg_begin(li.reg), re = mri_->use_nodbg_end();
841 ri != re; ++ri) {
Dan Gohman6d69ba82008-07-25 00:02:30 +0000842 MachineInstr *UseMI = &*ri;
Lang Hames233a60e2009-11-03 23:52:08 +0000843 SlotIndex UseIdx = getInstructionIndex(UseMI);
Dan Gohman6d69ba82008-07-25 00:02:30 +0000844 if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo)
845 continue;
846 if (!isValNoAvailableAt(ImpLi, MI, UseIdx))
847 return false;
848 }
Evan Chengdc377862008-09-30 15:44:16 +0000849
850 // If a register operand of the re-materialized instruction is going to
851 // be spilled next, then it's not legal to re-materialize this instruction.
852 for (unsigned i = 0, e = SpillIs.size(); i != e; ++i)
853 if (ImpUse == SpillIs[i]->reg)
854 return false;
Dan Gohman6d69ba82008-07-25 00:02:30 +0000855 }
856 return true;
Evan Cheng5ef3a042007-12-06 00:01:56 +0000857}
858
Evan Cheng06587492008-10-24 02:05:00 +0000859/// isReMaterializable - Returns true if the definition MI of the specified
860/// val# of the specified interval is re-materializable.
861bool LiveIntervals::isReMaterializable(const LiveInterval &li,
862 const VNInfo *ValNo, MachineInstr *MI) {
863 SmallVector<LiveInterval*, 4> Dummy1;
864 bool Dummy2;
865 return isReMaterializable(li, ValNo, MI, Dummy1, Dummy2);
866}
867
Evan Cheng5ef3a042007-12-06 00:01:56 +0000868/// isReMaterializable - Returns true if every definition of MI of every
869/// val# of the specified interval is re-materializable.
Evan Chengdc377862008-09-30 15:44:16 +0000870bool LiveIntervals::isReMaterializable(const LiveInterval &li,
871 SmallVectorImpl<LiveInterval*> &SpillIs,
872 bool &isLoad) {
Evan Cheng5ef3a042007-12-06 00:01:56 +0000873 isLoad = false;
874 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
875 i != e; ++i) {
876 const VNInfo *VNI = *i;
Lang Hames857c4e02009-06-17 21:01:20 +0000877 if (VNI->isUnused())
Evan Cheng5ef3a042007-12-06 00:01:56 +0000878 continue; // Dead val#.
879 // Is the def for the val# rematerializable?
Lang Hames857c4e02009-06-17 21:01:20 +0000880 if (!VNI->isDefAccurate())
Evan Cheng5ef3a042007-12-06 00:01:56 +0000881 return false;
Lang Hames857c4e02009-06-17 21:01:20 +0000882 MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def);
Evan Cheng5ef3a042007-12-06 00:01:56 +0000883 bool DefIsLoad = false;
Evan Chengd70dbb52008-02-22 09:24:50 +0000884 if (!ReMatDefMI ||
Evan Chengdc377862008-09-30 15:44:16 +0000885 !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad))
Evan Cheng5ef3a042007-12-06 00:01:56 +0000886 return false;
887 isLoad |= DefIsLoad;
Evan Chengf2fbca62007-11-12 06:35:08 +0000888 }
889 return true;
890}
891
Evan Cheng79a0c1e2008-02-25 08:50:41 +0000892/// FilterFoldedOps - Filter out two-address use operands. Return
893/// true if it finds any issue with the operands that ought to prevent
894/// folding.
895static bool FilterFoldedOps(MachineInstr *MI,
896 SmallVector<unsigned, 2> &Ops,
897 unsigned &MRInfo,
898 SmallVector<unsigned, 2> &FoldOps) {
Evan Cheng79a0c1e2008-02-25 08:50:41 +0000899 MRInfo = 0;
Evan Chengaee4af62007-12-02 08:30:39 +0000900 for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
901 unsigned OpIdx = Ops[i];
Evan Chengd70dbb52008-02-22 09:24:50 +0000902 MachineOperand &MO = MI->getOperand(OpIdx);
Evan Chengaee4af62007-12-02 08:30:39 +0000903 // FIXME: fold subreg use.
Evan Chengd70dbb52008-02-22 09:24:50 +0000904 if (MO.getSubReg())
Evan Cheng79a0c1e2008-02-25 08:50:41 +0000905 return true;
Evan Chengd70dbb52008-02-22 09:24:50 +0000906 if (MO.isDef())
Evan Chengaee4af62007-12-02 08:30:39 +0000907 MRInfo |= (unsigned)VirtRegMap::isMod;
908 else {
909 // Filter out two-address use operand(s).
Evan Chenga24752f2009-03-19 20:30:06 +0000910 if (MI->isRegTiedToDefOperand(OpIdx)) {
Evan Chengaee4af62007-12-02 08:30:39 +0000911 MRInfo = VirtRegMap::isModRef;
912 continue;
913 }
914 MRInfo |= (unsigned)VirtRegMap::isRef;
915 }
916 FoldOps.push_back(OpIdx);
Evan Chenge62f97c2007-12-01 02:07:52 +0000917 }
Evan Cheng79a0c1e2008-02-25 08:50:41 +0000918 return false;
919}
920
921
922/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from
923/// slot / to reg or any rematerialized load into ith operand of specified
924/// MI. If it is successul, MI is updated with the newly created MI and
925/// returns true.
926bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI,
927 VirtRegMap &vrm, MachineInstr *DefMI,
Lang Hames233a60e2009-11-03 23:52:08 +0000928 SlotIndex InstrIdx,
Evan Cheng79a0c1e2008-02-25 08:50:41 +0000929 SmallVector<unsigned, 2> &Ops,
930 bool isSS, int Slot, unsigned Reg) {
Evan Cheng79a0c1e2008-02-25 08:50:41 +0000931 // If it is an implicit def instruction, just delete it.
Chris Lattner518bb532010-02-09 19:54:29 +0000932 if (MI->isImplicitDef()) {
Evan Cheng79a0c1e2008-02-25 08:50:41 +0000933 RemoveMachineInstrFromMaps(MI);
934 vrm.RemoveMachineInstrFromMaps(MI);
935 MI->eraseFromParent();
936 ++numFolds;
937 return true;
938 }
939
940 // Filter the list of operand indexes that are to be folded. Abort if
941 // any operand will prevent folding.
942 unsigned MRInfo = 0;
943 SmallVector<unsigned, 2> FoldOps;
944 if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps))
945 return false;
Evan Chenge62f97c2007-12-01 02:07:52 +0000946
Evan Cheng427f4c12008-03-31 23:19:51 +0000947 // The only time it's safe to fold into a two address instruction is when
948 // it's folding reload and spill from / into a spill stack slot.
949 if (DefMI && (MRInfo & VirtRegMap::isMod))
Evan Cheng249ded32008-02-23 03:38:34 +0000950 return false;
951
Evan Chengf2f8c2a2008-02-08 22:05:27 +0000952 MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot)
953 : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI);
Evan Chengf2fbca62007-11-12 06:35:08 +0000954 if (fmi) {
Evan Chengd3653122008-02-27 03:04:06 +0000955 // Remember this instruction uses the spill slot.
956 if (isSS) vrm.addSpillSlotUse(Slot, fmi);
957
Evan Chengf2fbca62007-11-12 06:35:08 +0000958 // Attempt to fold the memory reference into the instruction. If
959 // we can do this, we don't need to insert spill code.
Evan Chengf2fbca62007-11-12 06:35:08 +0000960 MachineBasicBlock &MBB = *MI->getParent();
Evan Cheng84802932008-01-10 08:24:38 +0000961 if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot))
Evan Chengaee4af62007-12-02 08:30:39 +0000962 vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo);
Evan Cheng81a03822007-11-17 00:40:40 +0000963 vrm.transferSpillPts(MI, fmi);
Evan Cheng0cbb1162007-11-29 01:06:25 +0000964 vrm.transferRestorePts(MI, fmi);
Evan Chengc1f53c72008-03-11 21:34:46 +0000965 vrm.transferEmergencySpills(MI, fmi);
Lang Hames233a60e2009-11-03 23:52:08 +0000966 ReplaceMachineInstrInMaps(MI, fmi);
Evan Chengf2fbca62007-11-12 06:35:08 +0000967 MI = MBB.insert(MBB.erase(MI), fmi);
Evan Cheng0cbb1162007-11-29 01:06:25 +0000968 ++numFolds;
Evan Chengf2fbca62007-11-12 06:35:08 +0000969 return true;
970 }
971 return false;
972}
973
Evan Cheng018f9b02007-12-05 03:22:34 +0000974/// canFoldMemoryOperand - Returns true if the specified load / store
975/// folding is possible.
976bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI,
Evan Cheng79a0c1e2008-02-25 08:50:41 +0000977 SmallVector<unsigned, 2> &Ops,
Evan Cheng3c75ba82008-04-01 21:37:32 +0000978 bool ReMat) const {
Evan Cheng79a0c1e2008-02-25 08:50:41 +0000979 // Filter the list of operand indexes that are to be folded. Abort if
980 // any operand will prevent folding.
981 unsigned MRInfo = 0;
Evan Cheng018f9b02007-12-05 03:22:34 +0000982 SmallVector<unsigned, 2> FoldOps;
Evan Cheng79a0c1e2008-02-25 08:50:41 +0000983 if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps))
984 return false;
Evan Cheng018f9b02007-12-05 03:22:34 +0000985
Evan Cheng3c75ba82008-04-01 21:37:32 +0000986 // It's only legal to remat for a use, not a def.
987 if (ReMat && (MRInfo & VirtRegMap::isMod))
Evan Cheng79a0c1e2008-02-25 08:50:41 +0000988 return false;
Evan Cheng018f9b02007-12-05 03:22:34 +0000989
Evan Chengd70dbb52008-02-22 09:24:50 +0000990 return tii_->canFoldMemoryOperand(MI, FoldOps);
991}
992
Evan Cheng81a03822007-11-17 00:40:40 +0000993bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const {
Lang Hames233a60e2009-11-03 23:52:08 +0000994 LiveInterval::Ranges::const_iterator itr = li.ranges.begin();
995
996 MachineBasicBlock *mbb = indexes_->getMBBCoveringRange(itr->start, itr->end);
997
998 if (mbb == 0)
999 return false;
1000
1001 for (++itr; itr != li.ranges.end(); ++itr) {
1002 MachineBasicBlock *mbb2 =
1003 indexes_->getMBBCoveringRange(itr->start, itr->end);
1004
1005 if (mbb2 != mbb)
Evan Cheng81a03822007-11-17 00:40:40 +00001006 return false;
1007 }
Lang Hames233a60e2009-11-03 23:52:08 +00001008
Evan Cheng81a03822007-11-17 00:40:40 +00001009 return true;
1010}
1011
Evan Chengd70dbb52008-02-22 09:24:50 +00001012/// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of
1013/// interval on to-be re-materialized operands of MI) with new register.
1014void LiveIntervals::rewriteImplicitOps(const LiveInterval &li,
1015 MachineInstr *MI, unsigned NewVReg,
1016 VirtRegMap &vrm) {
1017 // There is an implicit use. That means one of the other operand is
1018 // being remat'ed and the remat'ed instruction has li.reg as an
1019 // use operand. Make sure we rewrite that as well.
1020 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1021 MachineOperand &MO = MI->getOperand(i);
Dan Gohmand735b802008-10-03 15:45:36 +00001022 if (!MO.isReg())
Evan Chengd70dbb52008-02-22 09:24:50 +00001023 continue;
1024 unsigned Reg = MO.getReg();
1025 if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg))
1026 continue;
1027 if (!vrm.isReMaterialized(Reg))
1028 continue;
1029 MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg);
Evan Cheng6130f662008-03-05 00:59:57 +00001030 MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg);
1031 if (UseMO)
1032 UseMO->setReg(NewVReg);
Evan Chengd70dbb52008-02-22 09:24:50 +00001033 }
1034}
1035
Evan Chengf2fbca62007-11-12 06:35:08 +00001036/// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions
1037/// for addIntervalsForSpills to rewrite uses / defs for the given live range.
Evan Cheng018f9b02007-12-05 03:22:34 +00001038bool LiveIntervals::
Evan Chengd70dbb52008-02-22 09:24:50 +00001039rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
Lang Hames233a60e2009-11-03 23:52:08 +00001040 bool TrySplit, SlotIndex index, SlotIndex end,
Lang Hames86511252009-09-04 20:41:11 +00001041 MachineInstr *MI,
Evan Cheng81a03822007-11-17 00:40:40 +00001042 MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
Evan Chengf2fbca62007-11-12 06:35:08 +00001043 unsigned Slot, int LdSlot,
1044 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
Evan Chengd70dbb52008-02-22 09:24:50 +00001045 VirtRegMap &vrm,
Evan Chengf2fbca62007-11-12 06:35:08 +00001046 const TargetRegisterClass* rc,
1047 SmallVector<int, 4> &ReMatIds,
Evan Cheng22f07ff2007-12-11 02:09:15 +00001048 const MachineLoopInfo *loopInfo,
Evan Cheng313d4b82008-02-23 00:33:04 +00001049 unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse,
Owen Anderson28998312008-08-13 22:28:50 +00001050 DenseMap<unsigned,unsigned> &MBBVRegsMap,
Evan Chengc781a242009-05-03 18:32:42 +00001051 std::vector<LiveInterval*> &NewLIs) {
Evan Cheng018f9b02007-12-05 03:22:34 +00001052 bool CanFold = false;
Evan Chengf2fbca62007-11-12 06:35:08 +00001053 RestartInstruction:
1054 for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
1055 MachineOperand& mop = MI->getOperand(i);
Dan Gohmand735b802008-10-03 15:45:36 +00001056 if (!mop.isReg())
Evan Chengf2fbca62007-11-12 06:35:08 +00001057 continue;
1058 unsigned Reg = mop.getReg();
Dan Gohman6f0d0242008-02-10 18:45:23 +00001059 if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg))
Evan Chengf2fbca62007-11-12 06:35:08 +00001060 continue;
Evan Chengf2fbca62007-11-12 06:35:08 +00001061 if (Reg != li.reg)
1062 continue;
1063
1064 bool TryFold = !DefIsReMat;
Evan Chengcb3c3302007-11-29 23:02:50 +00001065 bool FoldSS = true; // Default behavior unless it's a remat.
Evan Chengf2fbca62007-11-12 06:35:08 +00001066 int FoldSlot = Slot;
1067 if (DefIsReMat) {
1068 // If this is the rematerializable definition MI itself and
1069 // all of its uses are rematerialized, simply delete it.
Evan Cheng81a03822007-11-17 00:40:40 +00001070 if (MI == ReMatOrigDefMI && CanDelete) {
Dale Johannesenbd635202010-02-10 00:55:42 +00001071 DEBUG(dbgs() << "\t\t\t\tErasing re-materializable def: "
Evan Cheng28a1e482010-03-30 05:49:07 +00001072 << *MI << '\n');
Evan Chengf2fbca62007-11-12 06:35:08 +00001073 RemoveMachineInstrFromMaps(MI);
Evan Chengcada2452007-11-28 01:28:46 +00001074 vrm.RemoveMachineInstrFromMaps(MI);
Evan Chengf2fbca62007-11-12 06:35:08 +00001075 MI->eraseFromParent();
1076 break;
1077 }
1078
1079 // If def for this use can't be rematerialized, then try folding.
Evan Cheng0cbb1162007-11-29 01:06:25 +00001080 // If def is rematerializable and it's a load, also try folding.
Evan Chengcb3c3302007-11-29 23:02:50 +00001081 TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad));
Evan Chengf2fbca62007-11-12 06:35:08 +00001082 if (isLoad) {
1083 // Try fold loads (from stack slot, constant pool, etc.) into uses.
1084 FoldSS = isLoadSS;
1085 FoldSlot = LdSlot;
1086 }
1087 }
1088
Evan Chengf2fbca62007-11-12 06:35:08 +00001089 // Scan all of the operands of this instruction rewriting operands
1090 // to use NewVReg instead of li.reg as appropriate. We do this for
1091 // two reasons:
1092 //
1093 // 1. If the instr reads the same spilled vreg multiple times, we
1094 // want to reuse the NewVReg.
1095 // 2. If the instr is a two-addr instruction, we are required to
1096 // keep the src/dst regs pinned.
1097 //
1098 // Keep track of whether we replace a use and/or def so that we can
1099 // create the spill interval with the appropriate range.
Evan Chengaee4af62007-12-02 08:30:39 +00001100 SmallVector<unsigned, 2> Ops;
Jakob Stoklund Olesenead06be2010-06-03 00:07:47 +00001101 tie(HasUse, HasDef) = MI->readsWritesVirtualRegister(Reg, &Ops);
Evan Chengf2fbca62007-11-12 06:35:08 +00001102
David Greene26b86a02008-10-27 17:38:59 +00001103 // Create a new virtual register for the spill interval.
1104 // Create the new register now so we can map the fold instruction
1105 // to the new register so when it is unfolded we get the correct
1106 // answer.
1107 bool CreatedNewVReg = false;
1108 if (NewVReg == 0) {
1109 NewVReg = mri_->createVirtualRegister(rc);
1110 vrm.grow();
1111 CreatedNewVReg = true;
Jakob Stoklund Olesence7a6632009-11-30 22:55:54 +00001112
1113 // The new virtual register should get the same allocation hints as the
1114 // old one.
1115 std::pair<unsigned, unsigned> Hint = mri_->getRegAllocationHint(Reg);
1116 if (Hint.first || Hint.second)
1117 mri_->setRegAllocationHint(NewVReg, Hint.first, Hint.second);
David Greene26b86a02008-10-27 17:38:59 +00001118 }
1119
Evan Cheng9c3c2212008-06-06 07:54:39 +00001120 if (!TryFold)
1121 CanFold = false;
1122 else {
Evan Cheng018f9b02007-12-05 03:22:34 +00001123 // Do not fold load / store here if we are splitting. We'll find an
1124 // optimal point to insert a load / store later.
1125 if (!TrySplit) {
1126 if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
David Greene26b86a02008-10-27 17:38:59 +00001127 Ops, FoldSS, FoldSlot, NewVReg)) {
Evan Cheng018f9b02007-12-05 03:22:34 +00001128 // Folding the load/store can completely change the instruction in
1129 // unpredictable ways, rescan it from the beginning.
David Greene26b86a02008-10-27 17:38:59 +00001130
1131 if (FoldSS) {
1132 // We need to give the new vreg the same stack slot as the
1133 // spilled interval.
1134 vrm.assignVirt2StackSlot(NewVReg, FoldSlot);
1135 }
1136
Evan Cheng018f9b02007-12-05 03:22:34 +00001137 HasUse = false;
1138 HasDef = false;
1139 CanFold = false;
Evan Chengc781a242009-05-03 18:32:42 +00001140 if (isNotInMIMap(MI))
Evan Cheng7e073ba2008-04-09 20:57:25 +00001141 break;
Evan Cheng018f9b02007-12-05 03:22:34 +00001142 goto RestartInstruction;
1143 }
1144 } else {
Evan Cheng9c3c2212008-06-06 07:54:39 +00001145 // We'll try to fold it later if it's profitable.
Evan Cheng3c75ba82008-04-01 21:37:32 +00001146 CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat);
Evan Cheng018f9b02007-12-05 03:22:34 +00001147 }
Evan Cheng9c3c2212008-06-06 07:54:39 +00001148 }
Evan Chengcddbb832007-11-30 21:23:43 +00001149
Evan Chengcddbb832007-11-30 21:23:43 +00001150 mop.setReg(NewVReg);
Evan Chengd70dbb52008-02-22 09:24:50 +00001151 if (mop.isImplicit())
1152 rewriteImplicitOps(li, MI, NewVReg, vrm);
Evan Chengcddbb832007-11-30 21:23:43 +00001153
1154 // Reuse NewVReg for other reads.
Evan Chengd70dbb52008-02-22 09:24:50 +00001155 for (unsigned j = 0, e = Ops.size(); j != e; ++j) {
1156 MachineOperand &mopj = MI->getOperand(Ops[j]);
1157 mopj.setReg(NewVReg);
1158 if (mopj.isImplicit())
1159 rewriteImplicitOps(li, MI, NewVReg, vrm);
1160 }
Evan Chengcddbb832007-11-30 21:23:43 +00001161
Evan Cheng81a03822007-11-17 00:40:40 +00001162 if (CreatedNewVReg) {
1163 if (DefIsReMat) {
Evan Cheng37844532009-07-16 09:20:10 +00001164 vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI);
Evan Chengd70dbb52008-02-22 09:24:50 +00001165 if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) {
Evan Cheng81a03822007-11-17 00:40:40 +00001166 // Each valnum may have its own remat id.
Evan Chengd70dbb52008-02-22 09:24:50 +00001167 ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg);
Evan Cheng81a03822007-11-17 00:40:40 +00001168 } else {
Evan Chengd70dbb52008-02-22 09:24:50 +00001169 vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]);
Evan Cheng81a03822007-11-17 00:40:40 +00001170 }
1171 if (!CanDelete || (HasUse && HasDef)) {
1172 // If this is a two-addr instruction then its use operands are
1173 // rematerializable but its def is not. It should be assigned a
1174 // stack slot.
1175 vrm.assignVirt2StackSlot(NewVReg, Slot);
1176 }
Evan Chengf2fbca62007-11-12 06:35:08 +00001177 } else {
Evan Chengf2fbca62007-11-12 06:35:08 +00001178 vrm.assignVirt2StackSlot(NewVReg, Slot);
1179 }
Evan Chengcb3c3302007-11-29 23:02:50 +00001180 } else if (HasUse && HasDef &&
1181 vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) {
1182 // If this interval hasn't been assigned a stack slot (because earlier
1183 // def is a deleted remat def), do it now.
1184 assert(Slot != VirtRegMap::NO_STACK_SLOT);
1185 vrm.assignVirt2StackSlot(NewVReg, Slot);
Evan Chengf2fbca62007-11-12 06:35:08 +00001186 }
1187
Evan Cheng313d4b82008-02-23 00:33:04 +00001188 // Re-matting an instruction with virtual register use. Add the
1189 // register as an implicit use on the use MI.
1190 if (DefIsReMat && ImpUse)
1191 MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
1192
Evan Cheng5b69eba2009-04-21 22:46:52 +00001193 // Create a new register interval for this spill / remat.
Evan Chengf2fbca62007-11-12 06:35:08 +00001194 LiveInterval &nI = getOrCreateInterval(NewVReg);
Evan Cheng81a03822007-11-17 00:40:40 +00001195 if (CreatedNewVReg) {
1196 NewLIs.push_back(&nI);
Evan Cheng1953d0c2007-11-29 10:12:14 +00001197 MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg));
Evan Cheng81a03822007-11-17 00:40:40 +00001198 if (TrySplit)
1199 vrm.setIsSplitFromReg(NewVReg, li.reg);
1200 }
Evan Chengf2fbca62007-11-12 06:35:08 +00001201
1202 if (HasUse) {
Evan Cheng81a03822007-11-17 00:40:40 +00001203 if (CreatedNewVReg) {
Lang Hames233a60e2009-11-03 23:52:08 +00001204 LiveRange LR(index.getLoadIndex(), index.getDefIndex(),
1205 nI.getNextValue(SlotIndex(), 0, false, VNInfoAllocator));
David Greene8a342292010-01-04 22:49:02 +00001206 DEBUG(dbgs() << " +" << LR);
Evan Cheng81a03822007-11-17 00:40:40 +00001207 nI.addRange(LR);
1208 } else {
1209 // Extend the split live interval to this def / use.
Lang Hames233a60e2009-11-03 23:52:08 +00001210 SlotIndex End = index.getDefIndex();
Evan Cheng81a03822007-11-17 00:40:40 +00001211 LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End,
1212 nI.getValNumInfo(nI.getNumValNums()-1));
David Greene8a342292010-01-04 22:49:02 +00001213 DEBUG(dbgs() << " +" << LR);
Evan Cheng81a03822007-11-17 00:40:40 +00001214 nI.addRange(LR);
1215 }
Evan Chengf2fbca62007-11-12 06:35:08 +00001216 }
1217 if (HasDef) {
Lang Hames233a60e2009-11-03 23:52:08 +00001218 LiveRange LR(index.getDefIndex(), index.getStoreIndex(),
1219 nI.getNextValue(SlotIndex(), 0, false, VNInfoAllocator));
David Greene8a342292010-01-04 22:49:02 +00001220 DEBUG(dbgs() << " +" << LR);
Evan Chengf2fbca62007-11-12 06:35:08 +00001221 nI.addRange(LR);
1222 }
Evan Cheng81a03822007-11-17 00:40:40 +00001223
Bill Wendling8e6179f2009-08-22 20:18:03 +00001224 DEBUG({
David Greene8a342292010-01-04 22:49:02 +00001225 dbgs() << "\t\t\t\tAdded new interval: ";
1226 nI.print(dbgs(), tri_);
1227 dbgs() << '\n';
Bill Wendling8e6179f2009-08-22 20:18:03 +00001228 });
Evan Chengf2fbca62007-11-12 06:35:08 +00001229 }
Evan Cheng018f9b02007-12-05 03:22:34 +00001230 return CanFold;
Evan Chengf2fbca62007-11-12 06:35:08 +00001231}
Evan Cheng81a03822007-11-17 00:40:40 +00001232bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li,
Evan Cheng0cbb1162007-11-29 01:06:25 +00001233 const VNInfo *VNI,
Lang Hames86511252009-09-04 20:41:11 +00001234 MachineBasicBlock *MBB,
Lang Hames233a60e2009-11-03 23:52:08 +00001235 SlotIndex Idx) const {
Jakob Stoklund Olesen15a57142010-06-25 22:53:05 +00001236 return li.killedInRange(Idx.getNextSlot(), getMBBEndIdx(MBB));
Evan Cheng81a03822007-11-17 00:40:40 +00001237}
1238
Evan Cheng063284c2008-02-21 00:34:19 +00001239/// RewriteInfo - Keep track of machine instrs that will be rewritten
1240/// during spilling.
Dan Gohman844731a2008-05-13 00:00:25 +00001241namespace {
1242 struct RewriteInfo {
Lang Hames233a60e2009-11-03 23:52:08 +00001243 SlotIndex Index;
Dan Gohman844731a2008-05-13 00:00:25 +00001244 MachineInstr *MI;
Jakob Stoklund Olesenead06be2010-06-03 00:07:47 +00001245 RewriteInfo(SlotIndex i, MachineInstr *mi) : Index(i), MI(mi) {}
Dan Gohman844731a2008-05-13 00:00:25 +00001246 };
Evan Cheng063284c2008-02-21 00:34:19 +00001247
Dan Gohman844731a2008-05-13 00:00:25 +00001248 struct RewriteInfoCompare {
1249 bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const {
1250 return LHS.Index < RHS.Index;
1251 }
1252 };
1253}
Evan Cheng063284c2008-02-21 00:34:19 +00001254
Evan Chengf2fbca62007-11-12 06:35:08 +00001255void LiveIntervals::
Evan Cheng81a03822007-11-17 00:40:40 +00001256rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
Evan Chengf2fbca62007-11-12 06:35:08 +00001257 LiveInterval::Ranges::const_iterator &I,
Evan Cheng81a03822007-11-17 00:40:40 +00001258 MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
Evan Chengf2fbca62007-11-12 06:35:08 +00001259 unsigned Slot, int LdSlot,
1260 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
Evan Chengd70dbb52008-02-22 09:24:50 +00001261 VirtRegMap &vrm,
Evan Chengf2fbca62007-11-12 06:35:08 +00001262 const TargetRegisterClass* rc,
1263 SmallVector<int, 4> &ReMatIds,
Evan Cheng22f07ff2007-12-11 02:09:15 +00001264 const MachineLoopInfo *loopInfo,
Evan Cheng81a03822007-11-17 00:40:40 +00001265 BitVector &SpillMBBs,
Owen Anderson28998312008-08-13 22:28:50 +00001266 DenseMap<unsigned, std::vector<SRInfo> > &SpillIdxes,
Evan Cheng0cbb1162007-11-29 01:06:25 +00001267 BitVector &RestoreMBBs,
Owen Anderson28998312008-08-13 22:28:50 +00001268 DenseMap<unsigned, std::vector<SRInfo> > &RestoreIdxes,
1269 DenseMap<unsigned,unsigned> &MBBVRegsMap,
Evan Chengc781a242009-05-03 18:32:42 +00001270 std::vector<LiveInterval*> &NewLIs) {
Evan Cheng018f9b02007-12-05 03:22:34 +00001271 bool AllCanFold = true;
Evan Cheng81a03822007-11-17 00:40:40 +00001272 unsigned NewVReg = 0;
Lang Hames233a60e2009-11-03 23:52:08 +00001273 SlotIndex start = I->start.getBaseIndex();
1274 SlotIndex end = I->end.getPrevSlot().getBaseIndex().getNextIndex();
Evan Chengf2fbca62007-11-12 06:35:08 +00001275
Evan Cheng063284c2008-02-21 00:34:19 +00001276 // First collect all the def / use in this live range that will be rewritten.
Evan Cheng7e073ba2008-04-09 20:57:25 +00001277 // Make sure they are sorted according to instruction index.
Evan Cheng063284c2008-02-21 00:34:19 +00001278 std::vector<RewriteInfo> RewriteMIs;
Evan Chengd70dbb52008-02-22 09:24:50 +00001279 for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
1280 re = mri_->reg_end(); ri != re; ) {
Evan Cheng419852c2008-04-03 16:39:43 +00001281 MachineInstr *MI = &*ri;
Evan Cheng063284c2008-02-21 00:34:19 +00001282 MachineOperand &O = ri.getOperand();
1283 ++ri;
Dale Johannesenbd635202010-02-10 00:55:42 +00001284 if (MI->isDebugValue()) {
Evan Cheng962021b2010-04-26 07:38:55 +00001285 // Modify DBG_VALUE now that the value is in a spill slot.
Evan Cheng6691a892010-04-28 23:52:26 +00001286 if (Slot != VirtRegMap::MAX_STACK_SLOT || isLoadSS) {
Evan Cheng6fa76362010-04-26 18:37:21 +00001287 uint64_t Offset = MI->getOperand(1).getImm();
1288 const MDNode *MDPtr = MI->getOperand(2).getMetadata();
1289 DebugLoc DL = MI->getDebugLoc();
Evan Cheng6691a892010-04-28 23:52:26 +00001290 int FI = isLoadSS ? LdSlot : (int)Slot;
1291 if (MachineInstr *NewDV = tii_->emitFrameIndexDebugValue(*mf_, FI,
Evan Cheng6fa76362010-04-26 18:37:21 +00001292 Offset, MDPtr, DL)) {
1293 DEBUG(dbgs() << "Modifying debug info due to spill:" << "\t" << *MI);
1294 ReplaceMachineInstrInMaps(MI, NewDV);
1295 MachineBasicBlock *MBB = MI->getParent();
1296 MBB->insert(MBB->erase(MI), NewDV);
1297 continue;
1298 }
Evan Cheng962021b2010-04-26 07:38:55 +00001299 }
Evan Cheng6fa76362010-04-26 18:37:21 +00001300
1301 DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI);
1302 RemoveMachineInstrFromMaps(MI);
1303 vrm.RemoveMachineInstrFromMaps(MI);
1304 MI->eraseFromParent();
Dale Johannesenbd635202010-02-10 00:55:42 +00001305 continue;
1306 }
Jakob Stoklund Olesen63e6a482010-05-21 16:32:16 +00001307 assert(!(O.isImplicit() && O.isUse()) &&
1308 "Spilling register that's used as implicit use?");
Lang Hames233a60e2009-11-03 23:52:08 +00001309 SlotIndex index = getInstructionIndex(MI);
Evan Cheng063284c2008-02-21 00:34:19 +00001310 if (index < start || index >= end)
1311 continue;
Evan Chengd129d732009-07-17 19:43:40 +00001312
1313 if (O.isUndef())
Evan Cheng79a796c2008-07-12 01:56:02 +00001314 // Must be defined by an implicit def. It should not be spilled. Note,
1315 // this is for correctness reason. e.g.
1316 // 8 %reg1024<def> = IMPLICIT_DEF
1317 // 12 %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2
1318 // The live range [12, 14) are not part of the r1024 live interval since
1319 // it's defined by an implicit def. It will not conflicts with live
1320 // interval of r1025. Now suppose both registers are spilled, you can
Evan Chengb9890ae2008-07-12 02:22:07 +00001321 // easily see a situation where both registers are reloaded before
Evan Cheng79a796c2008-07-12 01:56:02 +00001322 // the INSERT_SUBREG and both target registers that would overlap.
1323 continue;
Jakob Stoklund Olesenead06be2010-06-03 00:07:47 +00001324 RewriteMIs.push_back(RewriteInfo(index, MI));
Evan Cheng063284c2008-02-21 00:34:19 +00001325 }
1326 std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare());
1327
Evan Cheng313d4b82008-02-23 00:33:04 +00001328 unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0;
Evan Cheng063284c2008-02-21 00:34:19 +00001329 // Now rewrite the defs and uses.
1330 for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) {
1331 RewriteInfo &rwi = RewriteMIs[i];
1332 ++i;
Lang Hames233a60e2009-11-03 23:52:08 +00001333 SlotIndex index = rwi.Index;
Evan Cheng063284c2008-02-21 00:34:19 +00001334 MachineInstr *MI = rwi.MI;
1335 // If MI def and/or use the same register multiple times, then there
1336 // are multiple entries.
1337 while (i != e && RewriteMIs[i].MI == MI) {
1338 assert(RewriteMIs[i].Index == index);
Evan Cheng063284c2008-02-21 00:34:19 +00001339 ++i;
1340 }
Evan Cheng81a03822007-11-17 00:40:40 +00001341 MachineBasicBlock *MBB = MI->getParent();
Evan Cheng313d4b82008-02-23 00:33:04 +00001342
Evan Cheng0a891ed2008-05-23 23:00:04 +00001343 if (ImpUse && MI != ReMatDefMI) {
Jakob Stoklund Olesene5d90412010-03-01 20:59:38 +00001344 // Re-matting an instruction with virtual register use. Prevent interval
1345 // from being spilled.
1346 getInterval(ImpUse).markNotSpillable();
Evan Cheng313d4b82008-02-23 00:33:04 +00001347 }
1348
Evan Cheng063284c2008-02-21 00:34:19 +00001349 unsigned MBBId = MBB->getNumber();
Evan Cheng018f9b02007-12-05 03:22:34 +00001350 unsigned ThisVReg = 0;
Evan Cheng70306f82007-12-03 09:58:48 +00001351 if (TrySplit) {
Owen Anderson28998312008-08-13 22:28:50 +00001352 DenseMap<unsigned,unsigned>::iterator NVI = MBBVRegsMap.find(MBBId);
Evan Cheng1953d0c2007-11-29 10:12:14 +00001353 if (NVI != MBBVRegsMap.end()) {
Evan Cheng018f9b02007-12-05 03:22:34 +00001354 ThisVReg = NVI->second;
Evan Cheng1953d0c2007-11-29 10:12:14 +00001355 // One common case:
1356 // x = use
1357 // ...
1358 // ...
1359 // def = ...
1360 // = use
1361 // It's better to start a new interval to avoid artifically
1362 // extend the new interval.
Jakob Stoklund Olesenead06be2010-06-03 00:07:47 +00001363 if (MI->readsWritesVirtualRegister(li.reg) ==
1364 std::make_pair(false,true)) {
Evan Cheng1953d0c2007-11-29 10:12:14 +00001365 MBBVRegsMap.erase(MBB->getNumber());
Evan Cheng018f9b02007-12-05 03:22:34 +00001366 ThisVReg = 0;
Evan Cheng1953d0c2007-11-29 10:12:14 +00001367 }
1368 }
Evan Chengcada2452007-11-28 01:28:46 +00001369 }
Evan Cheng018f9b02007-12-05 03:22:34 +00001370
1371 bool IsNew = ThisVReg == 0;
1372 if (IsNew) {
1373 // This ends the previous live interval. If all of its def / use
1374 // can be folded, give it a low spill weight.
1375 if (NewVReg && TrySplit && AllCanFold) {
1376 LiveInterval &nI = getOrCreateInterval(NewVReg);
1377 nI.weight /= 10.0F;
1378 }
1379 AllCanFold = true;
1380 }
1381 NewVReg = ThisVReg;
1382
Evan Cheng81a03822007-11-17 00:40:40 +00001383 bool HasDef = false;
1384 bool HasUse = false;
Evan Chengd70dbb52008-02-22 09:24:50 +00001385 bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit,
Evan Cheng9c3c2212008-06-06 07:54:39 +00001386 index, end, MI, ReMatOrigDefMI, ReMatDefMI,
1387 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1388 CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg,
Evan Chengc781a242009-05-03 18:32:42 +00001389 ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs);
Evan Cheng81a03822007-11-17 00:40:40 +00001390 if (!HasDef && !HasUse)
1391 continue;
1392
Evan Cheng018f9b02007-12-05 03:22:34 +00001393 AllCanFold &= CanFold;
1394
Evan Cheng81a03822007-11-17 00:40:40 +00001395 // Update weight of spill interval.
1396 LiveInterval &nI = getOrCreateInterval(NewVReg);
Evan Cheng70306f82007-12-03 09:58:48 +00001397 if (!TrySplit) {
Evan Cheng81a03822007-11-17 00:40:40 +00001398 // The spill weight is now infinity as it cannot be spilled again.
Jakob Stoklund Olesene5d90412010-03-01 20:59:38 +00001399 nI.markNotSpillable();
Evan Cheng0cbb1162007-11-29 01:06:25 +00001400 continue;
Evan Cheng81a03822007-11-17 00:40:40 +00001401 }
Evan Cheng0cbb1162007-11-29 01:06:25 +00001402
1403 // Keep track of the last def and first use in each MBB.
Evan Cheng0cbb1162007-11-29 01:06:25 +00001404 if (HasDef) {
1405 if (MI != ReMatOrigDefMI || !CanDelete) {
Evan Cheng0cbb1162007-11-29 01:06:25 +00001406 bool HasKill = false;
1407 if (!HasUse)
Lang Hames233a60e2009-11-03 23:52:08 +00001408 HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, index.getDefIndex());
Evan Cheng0cbb1162007-11-29 01:06:25 +00001409 else {
Evan Cheng1953d0c2007-11-29 10:12:14 +00001410 // If this is a two-address code, then this index starts a new VNInfo.
Lang Hames233a60e2009-11-03 23:52:08 +00001411 const VNInfo *VNI = li.findDefinedVNInfoForRegInt(index.getDefIndex());
Evan Cheng0cbb1162007-11-29 01:06:25 +00001412 if (VNI)
Lang Hames233a60e2009-11-03 23:52:08 +00001413 HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, index.getDefIndex());
Evan Cheng0cbb1162007-11-29 01:06:25 +00001414 }
Owen Anderson28998312008-08-13 22:28:50 +00001415 DenseMap<unsigned, std::vector<SRInfo> >::iterator SII =
Evan Chenge3110d02007-12-01 04:42:39 +00001416 SpillIdxes.find(MBBId);
Evan Cheng0cbb1162007-11-29 01:06:25 +00001417 if (!HasKill) {
Evan Cheng1953d0c2007-11-29 10:12:14 +00001418 if (SII == SpillIdxes.end()) {
1419 std::vector<SRInfo> S;
1420 S.push_back(SRInfo(index, NewVReg, true));
1421 SpillIdxes.insert(std::make_pair(MBBId, S));
1422 } else if (SII->second.back().vreg != NewVReg) {
1423 SII->second.push_back(SRInfo(index, NewVReg, true));
Lang Hames86511252009-09-04 20:41:11 +00001424 } else if (index > SII->second.back().index) {
Evan Cheng0cbb1162007-11-29 01:06:25 +00001425 // If there is an earlier def and this is a two-address
1426 // instruction, then it's not possible to fold the store (which
1427 // would also fold the load).
Evan Cheng1953d0c2007-11-29 10:12:14 +00001428 SRInfo &Info = SII->second.back();
1429 Info.index = index;
1430 Info.canFold = !HasUse;
Evan Cheng0cbb1162007-11-29 01:06:25 +00001431 }
1432 SpillMBBs.set(MBBId);
Evan Chenge3110d02007-12-01 04:42:39 +00001433 } else if (SII != SpillIdxes.end() &&
1434 SII->second.back().vreg == NewVReg &&
Lang Hames86511252009-09-04 20:41:11 +00001435 index > SII->second.back().index) {
Evan Chenge3110d02007-12-01 04:42:39 +00001436 // There is an earlier def that's not killed (must be two-address).
1437 // The spill is no longer needed.
1438 SII->second.pop_back();
1439 if (SII->second.empty()) {
1440 SpillIdxes.erase(MBBId);
1441 SpillMBBs.reset(MBBId);
1442 }
Evan Cheng0cbb1162007-11-29 01:06:25 +00001443 }
1444 }
Evan Cheng0cbb1162007-11-29 01:06:25 +00001445 }
1446
1447 if (HasUse) {
Owen Anderson28998312008-08-13 22:28:50 +00001448 DenseMap<unsigned, std::vector<SRInfo> >::iterator SII =
Evan Cheng0cbb1162007-11-29 01:06:25 +00001449 SpillIdxes.find(MBBId);
Evan Cheng1953d0c2007-11-29 10:12:14 +00001450 if (SII != SpillIdxes.end() &&
1451 SII->second.back().vreg == NewVReg &&
Lang Hames86511252009-09-04 20:41:11 +00001452 index > SII->second.back().index)
Evan Cheng0cbb1162007-11-29 01:06:25 +00001453 // Use(s) following the last def, it's not safe to fold the spill.
Evan Cheng1953d0c2007-11-29 10:12:14 +00001454 SII->second.back().canFold = false;
Owen Anderson28998312008-08-13 22:28:50 +00001455 DenseMap<unsigned, std::vector<SRInfo> >::iterator RII =
Evan Cheng0cbb1162007-11-29 01:06:25 +00001456 RestoreIdxes.find(MBBId);
Evan Cheng1953d0c2007-11-29 10:12:14 +00001457 if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg)
Evan Cheng0cbb1162007-11-29 01:06:25 +00001458 // If we are splitting live intervals, only fold if it's the first
1459 // use and there isn't another use later in the MBB.
Evan Cheng1953d0c2007-11-29 10:12:14 +00001460 RII->second.back().canFold = false;
Evan Cheng0cbb1162007-11-29 01:06:25 +00001461 else if (IsNew) {
1462 // Only need a reload if there isn't an earlier def / use.
Evan Cheng1953d0c2007-11-29 10:12:14 +00001463 if (RII == RestoreIdxes.end()) {
1464 std::vector<SRInfo> Infos;
1465 Infos.push_back(SRInfo(index, NewVReg, true));
1466 RestoreIdxes.insert(std::make_pair(MBBId, Infos));
1467 } else {
1468 RII->second.push_back(SRInfo(index, NewVReg, true));
1469 }
Evan Cheng0cbb1162007-11-29 01:06:25 +00001470 RestoreMBBs.set(MBBId);
1471 }
1472 }
1473
1474 // Update spill weight.
Evan Cheng22f07ff2007-12-11 02:09:15 +00001475 unsigned loopDepth = loopInfo->getLoopDepth(MBB);
Evan Chengc3417602008-06-21 06:45:54 +00001476 nI.weight += getSpillWeight(HasDef, HasUse, loopDepth);
Evan Chengf2fbca62007-11-12 06:35:08 +00001477 }
Evan Cheng018f9b02007-12-05 03:22:34 +00001478
1479 if (NewVReg && TrySplit && AllCanFold) {
1480 // If all of its def / use can be folded, give it a low spill weight.
1481 LiveInterval &nI = getOrCreateInterval(NewVReg);
1482 nI.weight /= 10.0F;
1483 }
Evan Chengf2fbca62007-11-12 06:35:08 +00001484}
1485
Lang Hames233a60e2009-11-03 23:52:08 +00001486bool LiveIntervals::alsoFoldARestore(int Id, SlotIndex index,
Lang Hames86511252009-09-04 20:41:11 +00001487 unsigned vr, BitVector &RestoreMBBs,
Owen Anderson28998312008-08-13 22:28:50 +00001488 DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
Evan Cheng1953d0c2007-11-29 10:12:14 +00001489 if (!RestoreMBBs[Id])
1490 return false;
1491 std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1492 for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1493 if (Restores[i].index == index &&
1494 Restores[i].vreg == vr &&
1495 Restores[i].canFold)
1496 return true;
1497 return false;
1498}
1499
Lang Hames233a60e2009-11-03 23:52:08 +00001500void LiveIntervals::eraseRestoreInfo(int Id, SlotIndex index,
Lang Hames86511252009-09-04 20:41:11 +00001501 unsigned vr, BitVector &RestoreMBBs,
Owen Anderson28998312008-08-13 22:28:50 +00001502 DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
Evan Cheng1953d0c2007-11-29 10:12:14 +00001503 if (!RestoreMBBs[Id])
1504 return;
1505 std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1506 for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1507 if (Restores[i].index == index && Restores[i].vreg)
Lang Hames233a60e2009-11-03 23:52:08 +00001508 Restores[i].index = SlotIndex();
Evan Cheng1953d0c2007-11-29 10:12:14 +00001509}
Evan Cheng81a03822007-11-17 00:40:40 +00001510
Evan Cheng4cce6b42008-04-11 17:53:36 +00001511/// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being
1512/// spilled and create empty intervals for their uses.
1513void
1514LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm,
1515 const TargetRegisterClass* rc,
1516 std::vector<LiveInterval*> &NewLIs) {
Evan Cheng419852c2008-04-03 16:39:43 +00001517 for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
1518 re = mri_->reg_end(); ri != re; ) {
Evan Cheng4cce6b42008-04-11 17:53:36 +00001519 MachineOperand &O = ri.getOperand();
Evan Cheng419852c2008-04-03 16:39:43 +00001520 MachineInstr *MI = &*ri;
1521 ++ri;
Evan Cheng28a1e482010-03-30 05:49:07 +00001522 if (MI->isDebugValue()) {
1523 // Remove debug info for now.
1524 O.setReg(0U);
1525 DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI);
1526 continue;
1527 }
Evan Cheng4cce6b42008-04-11 17:53:36 +00001528 if (O.isDef()) {
Chris Lattner518bb532010-02-09 19:54:29 +00001529 assert(MI->isImplicitDef() &&
Evan Cheng4cce6b42008-04-11 17:53:36 +00001530 "Register def was not rewritten?");
1531 RemoveMachineInstrFromMaps(MI);
1532 vrm.RemoveMachineInstrFromMaps(MI);
1533 MI->eraseFromParent();
1534 } else {
1535 // This must be an use of an implicit_def so it's not part of the live
1536 // interval. Create a new empty live interval for it.
1537 // FIXME: Can we simply erase some of the instructions? e.g. Stores?
1538 unsigned NewVReg = mri_->createVirtualRegister(rc);
1539 vrm.grow();
1540 vrm.setIsImplicitlyDefined(NewVReg);
1541 NewLIs.push_back(&getOrCreateInterval(NewVReg));
1542 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1543 MachineOperand &MO = MI->getOperand(i);
Evan Cheng4784f1f2009-06-30 08:49:04 +00001544 if (MO.isReg() && MO.getReg() == li.reg) {
Evan Cheng4cce6b42008-04-11 17:53:36 +00001545 MO.setReg(NewVReg);
Evan Cheng4784f1f2009-06-30 08:49:04 +00001546 MO.setIsUndef();
Evan Cheng4784f1f2009-06-30 08:49:04 +00001547 }
Evan Cheng4cce6b42008-04-11 17:53:36 +00001548 }
1549 }
Evan Cheng419852c2008-04-03 16:39:43 +00001550 }
1551}
1552
Jakob Stoklund Olesene5d90412010-03-01 20:59:38 +00001553float
1554LiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) {
1555 // Limit the loop depth ridiculousness.
1556 if (loopDepth > 200)
1557 loopDepth = 200;
1558
1559 // The loop depth is used to roughly estimate the number of times the
1560 // instruction is executed. Something like 10^d is simple, but will quickly
1561 // overflow a float. This expression behaves like 10^d for small d, but is
1562 // more tempered for large d. At d=200 we get 6.7e33 which leaves a bit of
1563 // headroom before overflow.
Chris Lattner87565c12010-05-15 17:10:24 +00001564 float lc = std::pow(1 + (100.0f / (loopDepth+10)), (float)loopDepth);
Jakob Stoklund Olesene5d90412010-03-01 20:59:38 +00001565
1566 return (isDef + isUse) * lc;
1567}
1568
Jakob Stoklund Olesen352d3522010-02-18 21:33:05 +00001569void
1570LiveIntervals::normalizeSpillWeights(std::vector<LiveInterval*> &NewLIs) {
1571 for (unsigned i = 0, e = NewLIs.size(); i != e; ++i)
1572 normalizeSpillWeight(*NewLIs[i]);
1573}
1574
Evan Chengf2fbca62007-11-12 06:35:08 +00001575std::vector<LiveInterval*> LiveIntervals::
Evan Cheng81a03822007-11-17 00:40:40 +00001576addIntervalsForSpills(const LiveInterval &li,
Evan Chengdc377862008-09-30 15:44:16 +00001577 SmallVectorImpl<LiveInterval*> &SpillIs,
Evan Chengc781a242009-05-03 18:32:42 +00001578 const MachineLoopInfo *loopInfo, VirtRegMap &vrm) {
Jakob Stoklund Olesene5d90412010-03-01 20:59:38 +00001579 assert(li.isSpillable() && "attempt to spill already spilled interval!");
Evan Chengf2fbca62007-11-12 06:35:08 +00001580
Bill Wendling8e6179f2009-08-22 20:18:03 +00001581 DEBUG({
David Greene8a342292010-01-04 22:49:02 +00001582 dbgs() << "\t\t\t\tadding intervals for spills for interval: ";
1583 li.print(dbgs(), tri_);
1584 dbgs() << '\n';
Bill Wendling8e6179f2009-08-22 20:18:03 +00001585 });
Evan Chengf2fbca62007-11-12 06:35:08 +00001586
Evan Cheng72eeb942008-12-05 17:00:16 +00001587 // Each bit specify whether a spill is required in the MBB.
Evan Cheng81a03822007-11-17 00:40:40 +00001588 BitVector SpillMBBs(mf_->getNumBlockIDs());
Owen Anderson28998312008-08-13 22:28:50 +00001589 DenseMap<unsigned, std::vector<SRInfo> > SpillIdxes;
Evan Cheng0cbb1162007-11-29 01:06:25 +00001590 BitVector RestoreMBBs(mf_->getNumBlockIDs());
Owen Anderson28998312008-08-13 22:28:50 +00001591 DenseMap<unsigned, std::vector<SRInfo> > RestoreIdxes;
1592 DenseMap<unsigned,unsigned> MBBVRegsMap;
Evan Chengf2fbca62007-11-12 06:35:08 +00001593 std::vector<LiveInterval*> NewLIs;
Evan Chengd70dbb52008-02-22 09:24:50 +00001594 const TargetRegisterClass* rc = mri_->getRegClass(li.reg);
Evan Chengf2fbca62007-11-12 06:35:08 +00001595
1596 unsigned NumValNums = li.getNumValNums();
1597 SmallVector<MachineInstr*, 4> ReMatDefs;
1598 ReMatDefs.resize(NumValNums, NULL);
1599 SmallVector<MachineInstr*, 4> ReMatOrigDefs;
1600 ReMatOrigDefs.resize(NumValNums, NULL);
1601 SmallVector<int, 4> ReMatIds;
1602 ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT);
1603 BitVector ReMatDelete(NumValNums);
1604 unsigned Slot = VirtRegMap::MAX_STACK_SLOT;
1605
Evan Cheng81a03822007-11-17 00:40:40 +00001606 // Spilling a split live interval. It cannot be split any further. Also,
1607 // it's also guaranteed to be a single val# / range interval.
1608 if (vrm.getPreSplitReg(li.reg)) {
1609 vrm.setIsSplitFromReg(li.reg, 0);
Evan Chengd120ffd2007-12-05 10:24:35 +00001610 // Unset the split kill marker on the last use.
Lang Hames233a60e2009-11-03 23:52:08 +00001611 SlotIndex KillIdx = vrm.getKillPoint(li.reg);
1612 if (KillIdx != SlotIndex()) {
Evan Chengd120ffd2007-12-05 10:24:35 +00001613 MachineInstr *KillMI = getInstructionFromIndex(KillIdx);
1614 assert(KillMI && "Last use disappeared?");
1615 int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true);
1616 assert(KillOp != -1 && "Last use disappeared?");
Chris Lattnerf7382302007-12-30 21:56:09 +00001617 KillMI->getOperand(KillOp).setIsKill(false);
Evan Chengd120ffd2007-12-05 10:24:35 +00001618 }
Evan Chengadf85902007-12-05 09:51:10 +00001619 vrm.removeKillPoint(li.reg);
Evan Cheng81a03822007-11-17 00:40:40 +00001620 bool DefIsReMat = vrm.isReMaterialized(li.reg);
1621 Slot = vrm.getStackSlot(li.reg);
1622 assert(Slot != VirtRegMap::MAX_STACK_SLOT);
1623 MachineInstr *ReMatDefMI = DefIsReMat ?
1624 vrm.getReMaterializedMI(li.reg) : NULL;
1625 int LdSlot = 0;
1626 bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1627 bool isLoad = isLoadSS ||
Dan Gohman15511cf2008-12-03 18:15:48 +00001628 (DefIsReMat && (ReMatDefMI->getDesc().canFoldAsLoad()));
Evan Cheng81a03822007-11-17 00:40:40 +00001629 bool IsFirstRange = true;
1630 for (LiveInterval::Ranges::const_iterator
1631 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
1632 // If this is a split live interval with multiple ranges, it means there
1633 // are two-address instructions that re-defined the value. Only the
1634 // first def can be rematerialized!
1635 if (IsFirstRange) {
Evan Chengcb3c3302007-11-29 23:02:50 +00001636 // Note ReMatOrigDefMI has already been deleted.
Evan Cheng81a03822007-11-17 00:40:40 +00001637 rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI,
1638 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
Evan Chengd70dbb52008-02-22 09:24:50 +00001639 false, vrm, rc, ReMatIds, loopInfo,
Evan Cheng0cbb1162007-11-29 01:06:25 +00001640 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
Evan Chengc781a242009-05-03 18:32:42 +00001641 MBBVRegsMap, NewLIs);
Evan Cheng81a03822007-11-17 00:40:40 +00001642 } else {
1643 rewriteInstructionsForSpills(li, false, I, NULL, 0,
1644 Slot, 0, false, false, false,
Evan Chengd70dbb52008-02-22 09:24:50 +00001645 false, vrm, rc, ReMatIds, loopInfo,
Evan Cheng0cbb1162007-11-29 01:06:25 +00001646 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
Evan Chengc781a242009-05-03 18:32:42 +00001647 MBBVRegsMap, NewLIs);
Evan Cheng81a03822007-11-17 00:40:40 +00001648 }
1649 IsFirstRange = false;
1650 }
Evan Cheng419852c2008-04-03 16:39:43 +00001651
Evan Cheng4cce6b42008-04-11 17:53:36 +00001652 handleSpilledImpDefs(li, vrm, rc, NewLIs);
Jakob Stoklund Olesen352d3522010-02-18 21:33:05 +00001653 normalizeSpillWeights(NewLIs);
Evan Cheng81a03822007-11-17 00:40:40 +00001654 return NewLIs;
1655 }
1656
Evan Cheng752195e2009-09-14 21:33:42 +00001657 bool TrySplit = !intervalIsInOneMBB(li);
Evan Cheng0cbb1162007-11-29 01:06:25 +00001658 if (TrySplit)
1659 ++numSplits;
Evan Chengf2fbca62007-11-12 06:35:08 +00001660 bool NeedStackSlot = false;
1661 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
1662 i != e; ++i) {
1663 const VNInfo *VNI = *i;
1664 unsigned VN = VNI->id;
Lang Hames857c4e02009-06-17 21:01:20 +00001665 if (VNI->isUnused())
Evan Chengf2fbca62007-11-12 06:35:08 +00001666 continue; // Dead val#.
1667 // Is the def for the val# rematerializable?
Lang Hames857c4e02009-06-17 21:01:20 +00001668 MachineInstr *ReMatDefMI = VNI->isDefAccurate()
1669 ? getInstructionFromIndex(VNI->def) : 0;
Evan Cheng5ef3a042007-12-06 00:01:56 +00001670 bool dummy;
Evan Chengdc377862008-09-30 15:44:16 +00001671 if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, SpillIs, dummy)) {
Evan Chengf2fbca62007-11-12 06:35:08 +00001672 // Remember how to remat the def of this val#.
Evan Cheng81a03822007-11-17 00:40:40 +00001673 ReMatOrigDefs[VN] = ReMatDefMI;
Dan Gohman2c3f7ae2008-07-17 23:49:46 +00001674 // Original def may be modified so we have to make a copy here.
Evan Cheng1ed99222008-07-19 00:37:25 +00001675 MachineInstr *Clone = mf_->CloneMachineInstr(ReMatDefMI);
Evan Cheng752195e2009-09-14 21:33:42 +00001676 CloneMIs.push_back(Clone);
Evan Cheng1ed99222008-07-19 00:37:25 +00001677 ReMatDefs[VN] = Clone;
Evan Chengf2fbca62007-11-12 06:35:08 +00001678
1679 bool CanDelete = true;
Lang Hames857c4e02009-06-17 21:01:20 +00001680 if (VNI->hasPHIKill()) {
Evan Chengc3fc7d92007-11-29 09:49:23 +00001681 // A kill is a phi node, not all of its uses can be rematerialized.
Evan Chengf2fbca62007-11-12 06:35:08 +00001682 // It must not be deleted.
Evan Chengc3fc7d92007-11-29 09:49:23 +00001683 CanDelete = false;
1684 // Need a stack slot if there is any live range where uses cannot be
1685 // rematerialized.
1686 NeedStackSlot = true;
Evan Chengf2fbca62007-11-12 06:35:08 +00001687 }
Evan Chengf2fbca62007-11-12 06:35:08 +00001688 if (CanDelete)
1689 ReMatDelete.set(VN);
1690 } else {
1691 // Need a stack slot if there is any live range where uses cannot be
1692 // rematerialized.
1693 NeedStackSlot = true;
1694 }
1695 }
1696
1697 // One stack slot per live interval.
Owen Andersonb98bbb72009-03-26 18:53:38 +00001698 if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) {
1699 if (vrm.getStackSlot(li.reg) == VirtRegMap::NO_STACK_SLOT)
1700 Slot = vrm.assignVirt2StackSlot(li.reg);
1701
1702 // This case only occurs when the prealloc splitter has already assigned
1703 // a stack slot to this vreg.
1704 else
1705 Slot = vrm.getStackSlot(li.reg);
1706 }
Evan Chengf2fbca62007-11-12 06:35:08 +00001707
1708 // Create new intervals and rewrite defs and uses.
1709 for (LiveInterval::Ranges::const_iterator
1710 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
Evan Cheng81a03822007-11-17 00:40:40 +00001711 MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id];
1712 MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id];
1713 bool DefIsReMat = ReMatDefMI != NULL;
Evan Chengf2fbca62007-11-12 06:35:08 +00001714 bool CanDelete = ReMatDelete[I->valno->id];
1715 int LdSlot = 0;
Evan Cheng81a03822007-11-17 00:40:40 +00001716 bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
Evan Chengf2fbca62007-11-12 06:35:08 +00001717 bool isLoad = isLoadSS ||
Dan Gohman15511cf2008-12-03 18:15:48 +00001718 (DefIsReMat && ReMatDefMI->getDesc().canFoldAsLoad());
Evan Cheng81a03822007-11-17 00:40:40 +00001719 rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI,
Evan Cheng0cbb1162007-11-29 01:06:25 +00001720 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
Evan Chengd70dbb52008-02-22 09:24:50 +00001721 CanDelete, vrm, rc, ReMatIds, loopInfo,
Evan Cheng0cbb1162007-11-29 01:06:25 +00001722 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
Evan Chengc781a242009-05-03 18:32:42 +00001723 MBBVRegsMap, NewLIs);
Evan Chengf2fbca62007-11-12 06:35:08 +00001724 }
1725
Evan Cheng0cbb1162007-11-29 01:06:25 +00001726 // Insert spills / restores if we are splitting.
Evan Cheng419852c2008-04-03 16:39:43 +00001727 if (!TrySplit) {
Evan Cheng4cce6b42008-04-11 17:53:36 +00001728 handleSpilledImpDefs(li, vrm, rc, NewLIs);
Jakob Stoklund Olesen352d3522010-02-18 21:33:05 +00001729 normalizeSpillWeights(NewLIs);
Evan Cheng1953d0c2007-11-29 10:12:14 +00001730 return NewLIs;
Evan Cheng419852c2008-04-03 16:39:43 +00001731 }
Evan Cheng1953d0c2007-11-29 10:12:14 +00001732
Evan Chengb50bb8c2007-12-05 08:16:32 +00001733 SmallPtrSet<LiveInterval*, 4> AddedKill;
Evan Chengaee4af62007-12-02 08:30:39 +00001734 SmallVector<unsigned, 2> Ops;
Evan Cheng1953d0c2007-11-29 10:12:14 +00001735 if (NeedStackSlot) {
1736 int Id = SpillMBBs.find_first();
1737 while (Id != -1) {
1738 std::vector<SRInfo> &spills = SpillIdxes[Id];
1739 for (unsigned i = 0, e = spills.size(); i != e; ++i) {
Lang Hames233a60e2009-11-03 23:52:08 +00001740 SlotIndex index = spills[i].index;
Evan Cheng1953d0c2007-11-29 10:12:14 +00001741 unsigned VReg = spills[i].vreg;
Evan Cheng597d10d2007-12-04 00:32:23 +00001742 LiveInterval &nI = getOrCreateInterval(VReg);
Evan Cheng0cbb1162007-11-29 01:06:25 +00001743 bool isReMat = vrm.isReMaterialized(VReg);
1744 MachineInstr *MI = getInstructionFromIndex(index);
Evan Chengaee4af62007-12-02 08:30:39 +00001745 bool CanFold = false;
1746 bool FoundUse = false;
1747 Ops.clear();
Evan Chengcddbb832007-11-30 21:23:43 +00001748 if (spills[i].canFold) {
Evan Chengaee4af62007-12-02 08:30:39 +00001749 CanFold = true;
Evan Cheng0cbb1162007-11-29 01:06:25 +00001750 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
1751 MachineOperand &MO = MI->getOperand(j);
Dan Gohmand735b802008-10-03 15:45:36 +00001752 if (!MO.isReg() || MO.getReg() != VReg)
Evan Cheng0cbb1162007-11-29 01:06:25 +00001753 continue;
Evan Chengaee4af62007-12-02 08:30:39 +00001754
1755 Ops.push_back(j);
1756 if (MO.isDef())
Evan Chengcddbb832007-11-30 21:23:43 +00001757 continue;
Evan Chengaee4af62007-12-02 08:30:39 +00001758 if (isReMat ||
1759 (!FoundUse && !alsoFoldARestore(Id, index, VReg,
1760 RestoreMBBs, RestoreIdxes))) {
1761 // MI has two-address uses of the same register. If the use
1762 // isn't the first and only use in the BB, then we can't fold
1763 // it. FIXME: Move this to rewriteInstructionsForSpills.
1764 CanFold = false;
Evan Chengcddbb832007-11-30 21:23:43 +00001765 break;
1766 }
Evan Chengaee4af62007-12-02 08:30:39 +00001767 FoundUse = true;
Evan Cheng0cbb1162007-11-29 01:06:25 +00001768 }
1769 }
1770 // Fold the store into the def if possible.
Evan Chengcddbb832007-11-30 21:23:43 +00001771 bool Folded = false;
Evan Chengaee4af62007-12-02 08:30:39 +00001772 if (CanFold && !Ops.empty()) {
1773 if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){
Evan Chengcddbb832007-11-30 21:23:43 +00001774 Folded = true;
Sebastian Redl48fe6352009-03-19 23:26:52 +00001775 if (FoundUse) {
Evan Chengaee4af62007-12-02 08:30:39 +00001776 // Also folded uses, do not issue a load.
1777 eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes);
Lang Hames233a60e2009-11-03 23:52:08 +00001778 nI.removeRange(index.getLoadIndex(), index.getDefIndex());
Evan Chengf38d14f2007-12-05 09:05:34 +00001779 }
Lang Hames233a60e2009-11-03 23:52:08 +00001780 nI.removeRange(index.getDefIndex(), index.getStoreIndex());
Evan Chengcddbb832007-11-30 21:23:43 +00001781 }
Evan Cheng0cbb1162007-11-29 01:06:25 +00001782 }
1783
Evan Cheng7e073ba2008-04-09 20:57:25 +00001784 // Otherwise tell the spiller to issue a spill.
Evan Chengb50bb8c2007-12-05 08:16:32 +00001785 if (!Folded) {
1786 LiveRange *LR = &nI.ranges[nI.ranges.size()-1];
Lang Hames233a60e2009-11-03 23:52:08 +00001787 bool isKill = LR->end == index.getStoreIndex();
Evan Chengb0a6f622008-05-20 08:10:37 +00001788 if (!MI->registerDefIsDead(nI.reg))
1789 // No need to spill a dead def.
1790 vrm.addSpillPoint(VReg, isKill, MI);
Evan Chengb50bb8c2007-12-05 08:16:32 +00001791 if (isKill)
1792 AddedKill.insert(&nI);
1793 }
Evan Cheng0cbb1162007-11-29 01:06:25 +00001794 }
Evan Cheng1953d0c2007-11-29 10:12:14 +00001795 Id = SpillMBBs.find_next(Id);
Evan Cheng0cbb1162007-11-29 01:06:25 +00001796 }
Evan Cheng1953d0c2007-11-29 10:12:14 +00001797 }
Evan Cheng0cbb1162007-11-29 01:06:25 +00001798
Evan Cheng1953d0c2007-11-29 10:12:14 +00001799 int Id = RestoreMBBs.find_first();
1800 while (Id != -1) {
1801 std::vector<SRInfo> &restores = RestoreIdxes[Id];
1802 for (unsigned i = 0, e = restores.size(); i != e; ++i) {
Lang Hames233a60e2009-11-03 23:52:08 +00001803 SlotIndex index = restores[i].index;
1804 if (index == SlotIndex())
Evan Cheng1953d0c2007-11-29 10:12:14 +00001805 continue;
1806 unsigned VReg = restores[i].vreg;
Evan Cheng597d10d2007-12-04 00:32:23 +00001807 LiveInterval &nI = getOrCreateInterval(VReg);
Evan Cheng9c3c2212008-06-06 07:54:39 +00001808 bool isReMat = vrm.isReMaterialized(VReg);
Evan Cheng81a03822007-11-17 00:40:40 +00001809 MachineInstr *MI = getInstructionFromIndex(index);
Evan Chengaee4af62007-12-02 08:30:39 +00001810 bool CanFold = false;
1811 Ops.clear();
Evan Chengcddbb832007-11-30 21:23:43 +00001812 if (restores[i].canFold) {
Evan Chengaee4af62007-12-02 08:30:39 +00001813 CanFold = true;
Evan Cheng81a03822007-11-17 00:40:40 +00001814 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
1815 MachineOperand &MO = MI->getOperand(j);
Dan Gohmand735b802008-10-03 15:45:36 +00001816 if (!MO.isReg() || MO.getReg() != VReg)
Evan Cheng81a03822007-11-17 00:40:40 +00001817 continue;
Evan Chengaee4af62007-12-02 08:30:39 +00001818
Evan Cheng0cbb1162007-11-29 01:06:25 +00001819 if (MO.isDef()) {
Evan Chengaee4af62007-12-02 08:30:39 +00001820 // If this restore were to be folded, it would have been folded
1821 // already.
1822 CanFold = false;
Evan Cheng81a03822007-11-17 00:40:40 +00001823 break;
1824 }
Evan Chengaee4af62007-12-02 08:30:39 +00001825 Ops.push_back(j);
Evan Cheng81a03822007-11-17 00:40:40 +00001826 }
1827 }
Evan Cheng0cbb1162007-11-29 01:06:25 +00001828
1829 // Fold the load into the use if possible.
Evan Chengcddbb832007-11-30 21:23:43 +00001830 bool Folded = false;
Evan Chengaee4af62007-12-02 08:30:39 +00001831 if (CanFold && !Ops.empty()) {
Evan Cheng9c3c2212008-06-06 07:54:39 +00001832 if (!isReMat)
Evan Chengaee4af62007-12-02 08:30:39 +00001833 Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg);
1834 else {
Evan Cheng0cbb1162007-11-29 01:06:25 +00001835 MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg);
1836 int LdSlot = 0;
1837 bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1838 // If the rematerializable def is a load, also try to fold it.
Dan Gohman15511cf2008-12-03 18:15:48 +00001839 if (isLoadSS || ReMatDefMI->getDesc().canFoldAsLoad())
Evan Chengaee4af62007-12-02 08:30:39 +00001840 Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
1841 Ops, isLoadSS, LdSlot, VReg);
Evan Cheng650d7f32008-12-05 17:41:31 +00001842 if (!Folded) {
1843 unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI);
1844 if (ImpUse) {
1845 // Re-matting an instruction with virtual register use. Add the
Jakob Stoklund Olesene5d90412010-03-01 20:59:38 +00001846 // register as an implicit use on the use MI and mark the register
1847 // interval as unspillable.
Evan Cheng650d7f32008-12-05 17:41:31 +00001848 LiveInterval &ImpLi = getInterval(ImpUse);
Jakob Stoklund Olesene5d90412010-03-01 20:59:38 +00001849 ImpLi.markNotSpillable();
Evan Cheng650d7f32008-12-05 17:41:31 +00001850 MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
1851 }
Evan Chengd70dbb52008-02-22 09:24:50 +00001852 }
Evan Chengaee4af62007-12-02 08:30:39 +00001853 }
Evan Cheng0cbb1162007-11-29 01:06:25 +00001854 }
1855 // If folding is not possible / failed, then tell the spiller to issue a
1856 // load / rematerialization for us.
Evan Cheng597d10d2007-12-04 00:32:23 +00001857 if (Folded)
Lang Hames233a60e2009-11-03 23:52:08 +00001858 nI.removeRange(index.getLoadIndex(), index.getDefIndex());
Evan Chengb50bb8c2007-12-05 08:16:32 +00001859 else
Evan Cheng0cbb1162007-11-29 01:06:25 +00001860 vrm.addRestorePoint(VReg, MI);
Evan Cheng81a03822007-11-17 00:40:40 +00001861 }
Evan Cheng1953d0c2007-11-29 10:12:14 +00001862 Id = RestoreMBBs.find_next(Id);
Evan Cheng81a03822007-11-17 00:40:40 +00001863 }
1864
Evan Chengb50bb8c2007-12-05 08:16:32 +00001865 // Finalize intervals: add kills, finalize spill weights, and filter out
1866 // dead intervals.
Evan Cheng597d10d2007-12-04 00:32:23 +00001867 std::vector<LiveInterval*> RetNewLIs;
1868 for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) {
1869 LiveInterval *LI = NewLIs[i];
1870 if (!LI->empty()) {
Lang Hames233a60e2009-11-03 23:52:08 +00001871 LI->weight /= SlotIndex::NUM * getApproximateInstructionCount(*LI);
Evan Chengb50bb8c2007-12-05 08:16:32 +00001872 if (!AddedKill.count(LI)) {
1873 LiveRange *LR = &LI->ranges[LI->ranges.size()-1];
Lang Hames233a60e2009-11-03 23:52:08 +00001874 SlotIndex LastUseIdx = LR->end.getBaseIndex();
Evan Chengd120ffd2007-12-05 10:24:35 +00001875 MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx);
Evan Cheng6130f662008-03-05 00:59:57 +00001876 int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false);
Evan Chengb50bb8c2007-12-05 08:16:32 +00001877 assert(UseIdx != -1);
Evan Chenga24752f2009-03-19 20:30:06 +00001878 if (!LastUse->isRegTiedToDefOperand(UseIdx)) {
Evan Chengb50bb8c2007-12-05 08:16:32 +00001879 LastUse->getOperand(UseIdx).setIsKill();
Evan Chengd120ffd2007-12-05 10:24:35 +00001880 vrm.addKillPoint(LI->reg, LastUseIdx);
Evan Chengadf85902007-12-05 09:51:10 +00001881 }
Evan Chengb50bb8c2007-12-05 08:16:32 +00001882 }
Evan Cheng597d10d2007-12-04 00:32:23 +00001883 RetNewLIs.push_back(LI);
1884 }
1885 }
Evan Cheng81a03822007-11-17 00:40:40 +00001886
Evan Cheng4cce6b42008-04-11 17:53:36 +00001887 handleSpilledImpDefs(li, vrm, rc, RetNewLIs);
Jakob Stoklund Olesen352d3522010-02-18 21:33:05 +00001888 normalizeSpillWeights(RetNewLIs);
Evan Cheng597d10d2007-12-04 00:32:23 +00001889 return RetNewLIs;
Evan Chengf2fbca62007-11-12 06:35:08 +00001890}
Evan Cheng676dd7c2008-03-11 07:19:34 +00001891
1892/// hasAllocatableSuperReg - Return true if the specified physical register has
1893/// any super register that's allocatable.
1894bool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const {
1895 for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS)
1896 if (allocatableRegs_[*AS] && hasInterval(*AS))
1897 return true;
1898 return false;
1899}
1900
1901/// getRepresentativeReg - Find the largest super register of the specified
1902/// physical register.
1903unsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const {
1904 // Find the largest super-register that is allocatable.
1905 unsigned BestReg = Reg;
1906 for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) {
1907 unsigned SuperReg = *AS;
1908 if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) {
1909 BestReg = SuperReg;
1910 break;
1911 }
1912 }
1913 return BestReg;
1914}
1915
1916/// getNumConflictsWithPhysReg - Return the number of uses and defs of the
1917/// specified interval that conflicts with the specified physical register.
1918unsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li,
1919 unsigned PhysReg) const {
1920 unsigned NumConflicts = 0;
1921 const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg));
1922 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
1923 E = mri_->reg_end(); I != E; ++I) {
1924 MachineOperand &O = I.getOperand();
1925 MachineInstr *MI = O.getParent();
Evan Cheng28a1e482010-03-30 05:49:07 +00001926 if (MI->isDebugValue())
1927 continue;
Lang Hames233a60e2009-11-03 23:52:08 +00001928 SlotIndex Index = getInstructionIndex(MI);
Evan Cheng676dd7c2008-03-11 07:19:34 +00001929 if (pli.liveAt(Index))
1930 ++NumConflicts;
1931 }
1932 return NumConflicts;
1933}
1934
1935/// spillPhysRegAroundRegDefsUses - Spill the specified physical register
Evan Cheng2824a652009-03-23 18:24:37 +00001936/// around all defs and uses of the specified interval. Return true if it
1937/// was able to cut its interval.
1938bool LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li,
Evan Cheng676dd7c2008-03-11 07:19:34 +00001939 unsigned PhysReg, VirtRegMap &vrm) {
1940 unsigned SpillReg = getRepresentativeReg(PhysReg);
1941
1942 for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS)
1943 // If there are registers which alias PhysReg, but which are not a
1944 // sub-register of the chosen representative super register. Assert
1945 // since we can't handle it yet.
Dan Gohman70f2f652009-04-13 15:22:29 +00001946 assert(*AS == SpillReg || !allocatableRegs_[*AS] || !hasInterval(*AS) ||
Evan Cheng676dd7c2008-03-11 07:19:34 +00001947 tri_->isSuperRegister(*AS, SpillReg));
1948
Evan Cheng2824a652009-03-23 18:24:37 +00001949 bool Cut = false;
Evan Cheng0222a8c2009-10-20 01:31:09 +00001950 SmallVector<unsigned, 4> PRegs;
1951 if (hasInterval(SpillReg))
1952 PRegs.push_back(SpillReg);
1953 else {
1954 SmallSet<unsigned, 4> Added;
1955 for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS)
1956 if (Added.insert(*AS) && hasInterval(*AS)) {
1957 PRegs.push_back(*AS);
1958 for (const unsigned* ASS = tri_->getSubRegisters(*AS); *ASS; ++ASS)
1959 Added.insert(*ASS);
1960 }
1961 }
1962
Evan Cheng676dd7c2008-03-11 07:19:34 +00001963 SmallPtrSet<MachineInstr*, 8> SeenMIs;
1964 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
1965 E = mri_->reg_end(); I != E; ++I) {
1966 MachineOperand &O = I.getOperand();
1967 MachineInstr *MI = O.getParent();
Evan Cheng28a1e482010-03-30 05:49:07 +00001968 if (MI->isDebugValue() || SeenMIs.count(MI))
Evan Cheng676dd7c2008-03-11 07:19:34 +00001969 continue;
1970 SeenMIs.insert(MI);
Lang Hames233a60e2009-11-03 23:52:08 +00001971 SlotIndex Index = getInstructionIndex(MI);
Evan Cheng0222a8c2009-10-20 01:31:09 +00001972 for (unsigned i = 0, e = PRegs.size(); i != e; ++i) {
1973 unsigned PReg = PRegs[i];
1974 LiveInterval &pli = getInterval(PReg);
1975 if (!pli.liveAt(Index))
1976 continue;
1977 vrm.addEmergencySpill(PReg, MI);
Lang Hames233a60e2009-11-03 23:52:08 +00001978 SlotIndex StartIdx = Index.getLoadIndex();
1979 SlotIndex EndIdx = Index.getNextIndex().getBaseIndex();
Evan Cheng2824a652009-03-23 18:24:37 +00001980 if (pli.isInOneLiveRange(StartIdx, EndIdx)) {
Evan Cheng5a3c6a82009-01-29 02:20:59 +00001981 pli.removeRange(StartIdx, EndIdx);
Evan Cheng2824a652009-03-23 18:24:37 +00001982 Cut = true;
1983 } else {
Torok Edwin7d696d82009-07-11 13:10:19 +00001984 std::string msg;
1985 raw_string_ostream Msg(msg);
1986 Msg << "Ran out of registers during register allocation!";
Chris Lattner518bb532010-02-09 19:54:29 +00001987 if (MI->isInlineAsm()) {
Torok Edwin7d696d82009-07-11 13:10:19 +00001988 Msg << "\nPlease check your inline asm statement for invalid "
Evan Cheng0222a8c2009-10-20 01:31:09 +00001989 << "constraints:\n";
Torok Edwin7d696d82009-07-11 13:10:19 +00001990 MI->print(Msg, tm_);
Evan Cheng5a3c6a82009-01-29 02:20:59 +00001991 }
Chris Lattner75361b62010-04-07 22:58:41 +00001992 report_fatal_error(Msg.str());
Evan Cheng5a3c6a82009-01-29 02:20:59 +00001993 }
Evan Cheng0222a8c2009-10-20 01:31:09 +00001994 for (const unsigned* AS = tri_->getSubRegisters(PReg); *AS; ++AS) {
Evan Cheng676dd7c2008-03-11 07:19:34 +00001995 if (!hasInterval(*AS))
1996 continue;
1997 LiveInterval &spli = getInterval(*AS);
1998 if (spli.liveAt(Index))
Lang Hames233a60e2009-11-03 23:52:08 +00001999 spli.removeRange(Index.getLoadIndex(),
2000 Index.getNextIndex().getBaseIndex());
Evan Cheng676dd7c2008-03-11 07:19:34 +00002001 }
2002 }
2003 }
Evan Cheng2824a652009-03-23 18:24:37 +00002004 return Cut;
Evan Cheng676dd7c2008-03-11 07:19:34 +00002005}
Owen Andersonc4dc1322008-06-05 17:15:43 +00002006
2007LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg,
Lang Hamesffd13262009-07-09 03:57:02 +00002008 MachineInstr* startInst) {
Owen Andersonc4dc1322008-06-05 17:15:43 +00002009 LiveInterval& Interval = getOrCreateInterval(reg);
2010 VNInfo* VN = Interval.getNextValue(
Lang Hames233a60e2009-11-03 23:52:08 +00002011 SlotIndex(getInstructionIndex(startInst).getDefIndex()),
Lang Hames86511252009-09-04 20:41:11 +00002012 startInst, true, getVNInfoAllocator());
Lang Hames857c4e02009-06-17 21:01:20 +00002013 VN->setHasPHIKill(true);
Lang Hames86511252009-09-04 20:41:11 +00002014 LiveRange LR(
Lang Hames233a60e2009-11-03 23:52:08 +00002015 SlotIndex(getInstructionIndex(startInst).getDefIndex()),
Lang Hames74ab5ee2009-12-22 00:11:50 +00002016 getMBBEndIdx(startInst->getParent()), VN);
Owen Andersonc4dc1322008-06-05 17:15:43 +00002017 Interval.addRange(LR);
2018
2019 return LR;
2020}
David Greeneb5257662009-08-03 21:55:09 +00002021