blob: 19bb7e34d25b32276a935516612a7a1be6a52b73 [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"
Jakob Stoklund Oleseneb9f0402011-02-14 23:15:38 +000023#include "llvm/CodeGen/CalcSpillWeights.h"
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000024#include "llvm/CodeGen/LiveVariables.h"
25#include "llvm/CodeGen/MachineFrameInfo.h"
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000026#include "llvm/CodeGen/MachineInstr.h"
Evan Cheng2578ba22009-07-01 01:59:31 +000027#include "llvm/CodeGen/MachineInstrBuilder.h"
Evan Cheng22f07ff2007-12-11 02:09:15 +000028#include "llvm/CodeGen/MachineLoopInfo.h"
Dan Gohmanc76909a2009-09-25 20:36:54 +000029#include "llvm/CodeGen/MachineMemOperand.h"
Chris Lattner84bc5422007-12-31 04:13:23 +000030#include "llvm/CodeGen/MachineRegisterInfo.h"
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000031#include "llvm/CodeGen/Passes.h"
Lang Hames233a60e2009-11-03 23:52:08 +000032#include "llvm/CodeGen/ProcessImplicitDefs.h"
Dan Gohman6f0d0242008-02-10 18:45:23 +000033#include "llvm/Target/TargetRegisterInfo.h"
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000034#include "llvm/Target/TargetInstrInfo.h"
35#include "llvm/Target/TargetMachine.h"
Owen Anderson95dad832008-10-07 20:22:28 +000036#include "llvm/Target/TargetOptions.h"
Reid Spencer551ccae2004-09-01 22:55:40 +000037#include "llvm/Support/CommandLine.h"
38#include "llvm/Support/Debug.h"
Torok Edwin7d696d82009-07-11 13:10:19 +000039#include "llvm/Support/ErrorHandling.h"
40#include "llvm/Support/raw_ostream.h"
Evan Cheng2578ba22009-07-01 01:59:31 +000041#include "llvm/ADT/DepthFirstIterator.h"
42#include "llvm/ADT/SmallSet.h"
Reid Spencer551ccae2004-09-01 22:55:40 +000043#include "llvm/ADT/Statistic.h"
44#include "llvm/ADT/STLExtras.h"
Alkis Evlogimenos20aa4742004-09-03 18:19:51 +000045#include <algorithm>
Lang Hamesf41538d2009-06-02 16:53:25 +000046#include <limits>
Jeff Cohen97af7512006-12-02 02:22:01 +000047#include <cmath>
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000048using namespace llvm;
49
Dan Gohman844731a2008-05-13 00:00:25 +000050// Hidden options for help debugging.
Jakob Stoklund Olesen1b293202010-08-12 20:01:23 +000051static cl::opt<bool> DisableReMat("disable-rematerialization",
Dan Gohman844731a2008-05-13 00:00:25 +000052 cl::init(false), cl::Hidden);
Evan Cheng81a03822007-11-17 00:40:40 +000053
Evan Cheng752195e2009-09-14 21:33:42 +000054STATISTIC(numIntervals , "Number of original intervals");
55STATISTIC(numFolds , "Number of loads/stores folded into instructions");
56STATISTIC(numSplits , "Number of intervals split");
Chris Lattnercd3245a2006-12-19 22:41:21 +000057
Devang Patel19974732007-05-03 01:11:54 +000058char LiveIntervals::ID = 0;
Owen Anderson2ab36d32010-10-12 19:48:12 +000059INITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals",
60 "Live Interval Analysis", false, false)
61INITIALIZE_PASS_DEPENDENCY(LiveVariables)
62INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
63INITIALIZE_PASS_DEPENDENCY(PHIElimination)
64INITIALIZE_PASS_DEPENDENCY(TwoAddressInstructionPass)
65INITIALIZE_PASS_DEPENDENCY(ProcessImplicitDefs)
66INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
67INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
68INITIALIZE_PASS_END(LiveIntervals, "liveintervals",
Owen Andersonce665bd2010-10-07 22:25:06 +000069 "Live Interval Analysis", false, false)
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000070
Chris Lattnerf7da2c72006-08-24 22:43:55 +000071void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
Dan Gohman845012e2009-07-31 23:37:33 +000072 AU.setPreservesCFG();
Dan Gohman6d69ba82008-07-25 00:02:30 +000073 AU.addRequired<AliasAnalysis>();
74 AU.addPreserved<AliasAnalysis>();
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +000075 AU.addRequired<LiveVariables>();
Evan Cheng148341c2010-08-17 21:00:37 +000076 AU.addPreserved<LiveVariables>();
77 AU.addRequired<MachineLoopInfo>();
78 AU.addPreserved<MachineLoopInfo>();
Bill Wendling67d65bb2008-01-04 20:54:55 +000079 AU.addPreservedID(MachineDominatorsID);
Jakob Stoklund Olesen1b293202010-08-12 20:01:23 +000080
Owen Anderson95dad832008-10-07 20:22:28 +000081 if (!StrongPHIElim) {
82 AU.addPreservedID(PHIEliminationID);
83 AU.addRequiredID(PHIEliminationID);
84 }
Jakob Stoklund Olesen1b293202010-08-12 20:01:23 +000085
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +000086 AU.addRequiredID(TwoAddressInstructionPassID);
Lang Hames233a60e2009-11-03 23:52:08 +000087 AU.addPreserved<ProcessImplicitDefs>();
88 AU.addRequired<ProcessImplicitDefs>();
89 AU.addPreserved<SlotIndexes>();
90 AU.addRequiredTransitive<SlotIndexes>();
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +000091 MachineFunctionPass::getAnalysisUsage(AU);
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000092}
93
Chris Lattnerf7da2c72006-08-24 22:43:55 +000094void LiveIntervals::releaseMemory() {
Owen Anderson03857b22008-08-13 21:49:13 +000095 // Free the live intervals themselves.
Owen Anderson20e28392008-08-13 22:08:30 +000096 for (DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.begin(),
Bob Wilsond6a6b3b2010-03-24 20:25:25 +000097 E = r2iMap_.end(); I != E; ++I)
Owen Anderson03857b22008-08-13 21:49:13 +000098 delete I->second;
Jakob Stoklund Olesen1b293202010-08-12 20:01:23 +000099
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000100 r2iMap_.clear();
Lang Hamesffd13262009-07-09 03:57:02 +0000101
Benjamin Kramerce9a20b2010-06-26 11:30:59 +0000102 // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd.
103 VNInfoAllocator.Reset();
Evan Cheng752195e2009-09-14 21:33:42 +0000104 while (!CloneMIs.empty()) {
105 MachineInstr *MI = CloneMIs.back();
106 CloneMIs.pop_back();
Evan Cheng1ed99222008-07-19 00:37:25 +0000107 mf_->DeleteMachineInstr(MI);
108 }
Alkis Evlogimenos08cec002004-01-31 19:59:32 +0000109}
110
Owen Anderson80b3ce62008-05-28 20:54:50 +0000111/// runOnMachineFunction - Register allocate the whole function
112///
113bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
114 mf_ = &fn;
115 mri_ = &mf_->getRegInfo();
116 tm_ = &fn.getTarget();
117 tri_ = tm_->getRegisterInfo();
118 tii_ = tm_->getInstrInfo();
Dan Gohman6d69ba82008-07-25 00:02:30 +0000119 aa_ = &getAnalysis<AliasAnalysis>();
Owen Anderson80b3ce62008-05-28 20:54:50 +0000120 lv_ = &getAnalysis<LiveVariables>();
Lang Hames233a60e2009-11-03 23:52:08 +0000121 indexes_ = &getAnalysis<SlotIndexes>();
Owen Anderson80b3ce62008-05-28 20:54:50 +0000122 allocatableRegs_ = tri_->getAllocatableSet(fn);
123
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000124 computeIntervals();
Alkis Evlogimenos843b1602004-02-15 10:24:21 +0000125
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000126 numIntervals += getNumIntervals();
127
Chris Lattner70ca3582004-09-30 15:59:17 +0000128 DEBUG(dump());
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000129 return true;
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000130}
131
Chris Lattner70ca3582004-09-30 15:59:17 +0000132/// print - Implement the dump method.
Chris Lattner45cfe542009-08-23 06:03:38 +0000133void LiveIntervals::print(raw_ostream &OS, const Module* ) const {
Chris Lattner705e07f2009-08-23 03:41:05 +0000134 OS << "********** INTERVALS **********\n";
Chris Lattner8e7a7092005-07-27 23:03:38 +0000135 for (const_iterator I = begin(), E = end(); I != E; ++I) {
Chris Lattner705e07f2009-08-23 03:41:05 +0000136 I->second->print(OS, tri_);
137 OS << "\n";
Chris Lattner8e7a7092005-07-27 23:03:38 +0000138 }
Chris Lattner70ca3582004-09-30 15:59:17 +0000139
Evan Cheng752195e2009-09-14 21:33:42 +0000140 printInstrs(OS);
141}
142
143void LiveIntervals::printInstrs(raw_ostream &OS) const {
Chris Lattner705e07f2009-08-23 03:41:05 +0000144 OS << "********** MACHINEINSTRS **********\n";
Jakob Stoklund Olesenf4a1e1a2010-10-26 20:21:46 +0000145 mf_->print(OS, indexes_);
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
Jakob Stoklund Olesen8ea32402010-07-09 20:55:49 +0000191 if (MI.isCopy())
192 if (MI.getOperand(0).getReg() == li.reg ||
193 MI.getOperand(1).getReg() == li.reg)
194 continue;
Jakob Stoklund Olesencf970362009-12-10 17:48:32 +0000195
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
Evan Chengafff40a2010-05-04 20:26:52 +0000249static
Evan Cheng37499432010-05-05 18:27:40 +0000250bool MultipleDefsBySameMI(const MachineInstr &MI, unsigned MOIdx) {
Evan Chengafff40a2010-05-04 20:26:52 +0000251 unsigned Reg = MI.getOperand(MOIdx).getReg();
252 for (unsigned i = MOIdx+1, e = MI.getNumOperands(); i < e; ++i) {
253 const MachineOperand &MO = MI.getOperand(i);
254 if (!MO.isReg())
255 continue;
256 if (MO.getReg() == Reg && MO.isDef()) {
257 assert(MI.getOperand(MOIdx).getSubReg() != MO.getSubReg() &&
258 MI.getOperand(MOIdx).getSubReg() &&
Jakob Stoklund Olesened2185e2010-07-06 23:26:25 +0000259 (MO.getSubReg() || MO.isImplicit()));
Evan Chengafff40a2010-05-04 20:26:52 +0000260 return true;
261 }
262 }
263 return false;
264}
265
Evan Cheng37499432010-05-05 18:27:40 +0000266/// isPartialRedef - Return true if the specified def at the specific index is
267/// partially re-defining the specified live interval. A common case of this is
Jakob Stoklund Olesen1b293202010-08-12 20:01:23 +0000268/// a definition of the sub-register.
Evan Cheng37499432010-05-05 18:27:40 +0000269bool LiveIntervals::isPartialRedef(SlotIndex MIIdx, MachineOperand &MO,
270 LiveInterval &interval) {
271 if (!MO.getSubReg() || MO.isEarlyClobber())
272 return false;
273
274 SlotIndex RedefIndex = MIIdx.getDefIndex();
275 const LiveRange *OldLR =
276 interval.getLiveRangeContaining(RedefIndex.getUseIndex());
Lang Hames6e2968c2010-09-25 12:04:16 +0000277 MachineInstr *DefMI = getInstructionFromIndex(OldLR->valno->def);
278 if (DefMI != 0) {
Evan Cheng37499432010-05-05 18:27:40 +0000279 return DefMI->findRegisterDefOperandIdx(interval.reg) != -1;
280 }
281 return false;
282}
283
Chris Lattnerbe4f88a2006-08-22 18:19:46 +0000284void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000285 MachineBasicBlock::iterator mi,
Lang Hames233a60e2009-11-03 23:52:08 +0000286 SlotIndex MIIdx,
Lang Hames86511252009-09-04 20:41:11 +0000287 MachineOperand& MO,
Evan Chengef0732d2008-07-10 07:35:43 +0000288 unsigned MOIdx,
Chris Lattnerbe4f88a2006-08-22 18:19:46 +0000289 LiveInterval &interval) {
Jakob Stoklund Olesen43142682011-01-09 03:05:53 +0000290 DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_));
Evan Cheng419852c2008-04-03 16:39:43 +0000291
Alkis Evlogimenos70651572004-08-04 09:46:56 +0000292 // Virtual registers may be defined multiple times (due to phi
293 // elimination and 2-addr elimination). Much of what we do only has to be
294 // done once for the vreg. We use an empty interval to detect the first
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000295 // time we see a vreg.
Evan Chengd129d732009-07-17 19:43:40 +0000296 LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000297 if (interval.empty()) {
298 // Get the Idx of the defining instructions.
Lang Hames233a60e2009-11-03 23:52:08 +0000299 SlotIndex defIndex = MIIdx.getDefIndex();
Dale Johannesen39faac22009-09-20 00:36:41 +0000300 // Earlyclobbers move back one, so that they overlap the live range
301 // of inputs.
Dale Johannesen86b49f82008-09-24 01:07:17 +0000302 if (MO.isEarlyClobber())
Lang Hames233a60e2009-11-03 23:52:08 +0000303 defIndex = MIIdx.getUseIndex();
Jakob Stoklund Olesen63e6a482010-05-21 16:32:16 +0000304
305 // Make sure the first definition is not a partial redefinition. Add an
306 // <imp-def> of the full register.
307 if (MO.getSubReg())
308 mi->addRegisterDefined(interval.reg);
309
Evan Chengc8d044e2008-02-15 18:24:29 +0000310 MachineInstr *CopyMI = NULL;
Jakob Stoklund Olesen04c528a2010-07-16 04:45:42 +0000311 if (mi->isCopyLike()) {
Evan Chengc8d044e2008-02-15 18:24:29 +0000312 CopyMI = mi;
Jakob Stoklund Olesen0465bcf2010-06-18 22:29:44 +0000313 }
314
Lang Hames6e2968c2010-09-25 12:04:16 +0000315 VNInfo *ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator);
Evan Cheng7ecb38b2007-08-29 20:45:00 +0000316 assert(ValNo->id == 0 && "First value in interval is not 0?");
Chris Lattner7ac2d312004-07-24 02:59:07 +0000317
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000318 // Loop over all of the blocks that the vreg is defined in. There are
319 // two cases we have to handle here. The most common case is a vreg
320 // whose lifetime is contained within a basic block. In this case there
321 // will be a single kill, in MBB, which comes after the definition.
322 if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) {
323 // FIXME: what about dead vars?
Lang Hames233a60e2009-11-03 23:52:08 +0000324 SlotIndex killIdx;
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000325 if (vi.Kills[0] != mi)
Lang Hames233a60e2009-11-03 23:52:08 +0000326 killIdx = getInstructionIndex(vi.Kills[0]).getDefIndex();
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000327 else
Lang Hames233a60e2009-11-03 23:52:08 +0000328 killIdx = defIndex.getStoreIndex();
Chris Lattner6097d132004-07-19 02:15:56 +0000329
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000330 // If the kill happens after the definition, we have an intra-block
331 // live range.
332 if (killIdx > defIndex) {
Jeffrey Yasskin493a3d02009-05-26 18:27:15 +0000333 assert(vi.AliveBlocks.empty() &&
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000334 "Shouldn't be alive across any blocks!");
Evan Cheng7ecb38b2007-08-29 20:45:00 +0000335 LiveRange LR(defIndex, killIdx, ValNo);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000336 interval.addRange(LR);
David Greene8a342292010-01-04 22:49:02 +0000337 DEBUG(dbgs() << " +" << LR << "\n");
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000338 return;
339 }
Alkis Evlogimenosdd2cc652003-12-18 08:48:48 +0000340 }
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000341
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000342 // The other case we handle is when a virtual register lives to the end
343 // of the defining block, potentially live across some blocks, then is
344 // live into some number of blocks, but gets killed. Start by adding a
345 // range that goes from this definition to the end of the defining block.
Lang Hames74ab5ee2009-12-22 00:11:50 +0000346 LiveRange NewLR(defIndex, getMBBEndIdx(mbb), ValNo);
David Greene8a342292010-01-04 22:49:02 +0000347 DEBUG(dbgs() << " +" << NewLR);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000348 interval.addRange(NewLR);
349
Jakob Stoklund Olesendcfe5f32010-02-23 22:43:58 +0000350 bool PHIJoin = lv_->isPHIJoin(interval.reg);
351
352 if (PHIJoin) {
353 // A phi join register is killed at the end of the MBB and revived as a new
354 // valno in the killing blocks.
355 assert(vi.AliveBlocks.empty() && "Phi join can't pass through blocks");
356 DEBUG(dbgs() << " phi-join");
Jakob Stoklund Olesendcfe5f32010-02-23 22:43:58 +0000357 ValNo->setHasPHIKill(true);
358 } else {
359 // Iterate over all of the blocks that the variable is completely
360 // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the
361 // live interval.
362 for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(),
363 E = vi.AliveBlocks.end(); I != E; ++I) {
364 MachineBasicBlock *aliveBlock = mf_->getBlockNumbered(*I);
365 LiveRange LR(getMBBStartIdx(aliveBlock), getMBBEndIdx(aliveBlock), ValNo);
366 interval.addRange(LR);
367 DEBUG(dbgs() << " +" << LR);
368 }
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000369 }
370
371 // Finally, this virtual register is live from the start of any killing
372 // block to the 'use' slot of the killing instruction.
373 for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
374 MachineInstr *Kill = vi.Kills[i];
Jakob Stoklund Olesendcfe5f32010-02-23 22:43:58 +0000375 SlotIndex Start = getMBBStartIdx(Kill->getParent());
376 SlotIndex killIdx = getInstructionIndex(Kill).getDefIndex();
377
378 // Create interval with one of a NEW value number. Note that this value
379 // number isn't actually defined by an instruction, weird huh? :)
380 if (PHIJoin) {
Lang Hames6e2968c2010-09-25 12:04:16 +0000381 assert(getInstructionFromIndex(Start) == 0 &&
382 "PHI def index points at actual instruction.");
383 ValNo = interval.getNextValue(Start, 0, VNInfoAllocator);
Jakob Stoklund Olesendcfe5f32010-02-23 22:43:58 +0000384 ValNo->setIsPHIDef(true);
385 }
386 LiveRange LR(Start, killIdx, ValNo);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000387 interval.addRange(LR);
David Greene8a342292010-01-04 22:49:02 +0000388 DEBUG(dbgs() << " +" << LR);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000389 }
390
391 } else {
Evan Cheng37499432010-05-05 18:27:40 +0000392 if (MultipleDefsBySameMI(*mi, MOIdx))
Nick Lewycky761fd4c2010-05-20 03:30:09 +0000393 // Multiple defs of the same virtual register by the same instruction.
394 // e.g. %reg1031:5<def>, %reg1031:6<def> = VLD1q16 %reg1024<kill>, ...
Evan Chengafff40a2010-05-04 20:26:52 +0000395 // This is likely due to elimination of REG_SEQUENCE instructions. Return
396 // here since there is nothing to do.
397 return;
398
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000399 // If this is the second time we see a virtual register definition, it
400 // must be due to phi elimination or two addr elimination. If this is
Evan Chengbf105c82006-11-03 03:04:46 +0000401 // the result of two address elimination, then the vreg is one of the
402 // def-and-use register operand.
Evan Cheng37499432010-05-05 18:27:40 +0000403
404 // It may also be partial redef like this:
Jakob Stoklund Olesen1b293202010-08-12 20:01:23 +0000405 // 80 %reg1041:6<def> = VSHRNv4i16 %reg1034<kill>, 12, pred:14, pred:%reg0
406 // 120 %reg1041:5<def> = VSHRNv4i16 %reg1039<kill>, 12, pred:14, pred:%reg0
Evan Cheng37499432010-05-05 18:27:40 +0000407 bool PartReDef = isPartialRedef(MIIdx, MO, interval);
408 if (PartReDef || mi->isRegTiedToUseOperand(MOIdx)) {
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000409 // If this is a two-address definition, then we have already processed
410 // the live range. The only problem is that we didn't realize there
411 // are actually two values in the live interval. Because of this we
412 // need to take the LiveRegion that defines this register and split it
413 // into two values.
Lang Hames233a60e2009-11-03 23:52:08 +0000414 SlotIndex RedefIndex = MIIdx.getDefIndex();
Evan Chengfb112882009-03-23 08:01:15 +0000415 if (MO.isEarlyClobber())
Lang Hames233a60e2009-11-03 23:52:08 +0000416 RedefIndex = MIIdx.getUseIndex();
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000417
Lang Hames35f291d2009-09-12 03:34:03 +0000418 const LiveRange *OldLR =
Lang Hames233a60e2009-11-03 23:52:08 +0000419 interval.getLiveRangeContaining(RedefIndex.getUseIndex());
Evan Cheng7ecb38b2007-08-29 20:45:00 +0000420 VNInfo *OldValNo = OldLR->valno;
Jakob Stoklund Olesenc66d0f22010-06-16 21:29:40 +0000421 SlotIndex DefIndex = OldValNo->def.getDefIndex();
Evan Cheng4f8ff162007-08-11 00:59:19 +0000422
Jakob Stoklund Olesenc66d0f22010-06-16 21:29:40 +0000423 // Delete the previous value, which should be short and continuous,
Chris Lattnerbe4f88a2006-08-22 18:19:46 +0000424 // because the 2-addr copy must be in the same MBB as the redef.
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000425 interval.removeRange(DefIndex, RedefIndex);
Alkis Evlogimenos70651572004-08-04 09:46:56 +0000426
Chris Lattner91725b72006-08-31 05:54:43 +0000427 // The new value number (#1) is defined by the instruction we claimed
428 // defined value #0.
Lang Hames6e2968c2010-09-25 12:04:16 +0000429 VNInfo *ValNo = interval.createValueCopy(OldValNo, VNInfoAllocator);
Lang Hames857c4e02009-06-17 21:01:20 +0000430
Chris Lattner91725b72006-08-31 05:54:43 +0000431 // Value#0 is now defined by the 2-addr instruction.
Evan Chengc8d044e2008-02-15 18:24:29 +0000432 OldValNo->def = RedefIndex;
Evan Chengad6c5a22010-05-17 01:47:47 +0000433 OldValNo->setCopy(0);
434
435 // A re-def may be a copy. e.g. %reg1030:6<def> = VMOVD %reg1026, ...
Jakob Stoklund Olesen04c528a2010-07-16 04:45:42 +0000436 if (PartReDef && mi->isCopyLike())
Evan Chengad6c5a22010-05-17 01:47:47 +0000437 OldValNo->setCopy(&*mi);
Jakob Stoklund Olesen1b293202010-08-12 20:01:23 +0000438
Chris Lattnerbe4f88a2006-08-22 18:19:46 +0000439 // Add the new live interval which replaces the range for the input copy.
440 LiveRange LR(DefIndex, RedefIndex, ValNo);
David Greene8a342292010-01-04 22:49:02 +0000441 DEBUG(dbgs() << " replace range with " << LR);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000442 interval.addRange(LR);
443
444 // If this redefinition is dead, we need to add a dummy unit live
445 // range covering the def slot.
Owen Anderson6b098de2008-06-25 23:39:39 +0000446 if (MO.isDead())
Lang Hames233a60e2009-11-03 23:52:08 +0000447 interval.addRange(LiveRange(RedefIndex, RedefIndex.getStoreIndex(),
448 OldValNo));
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000449
Bill Wendling8e6179f2009-08-22 20:18:03 +0000450 DEBUG({
David Greene8a342292010-01-04 22:49:02 +0000451 dbgs() << " RESULT: ";
452 interval.print(dbgs(), tri_);
Bill Wendling8e6179f2009-08-22 20:18:03 +0000453 });
Evan Cheng37499432010-05-05 18:27:40 +0000454 } else if (lv_->isPHIJoin(interval.reg)) {
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000455 // In the case of PHI elimination, each variable definition is only
456 // live until the end of the block. We've already taken care of the
457 // rest of the live range.
Jakob Stoklund Olesendcfe5f32010-02-23 22:43:58 +0000458
Lang Hames233a60e2009-11-03 23:52:08 +0000459 SlotIndex defIndex = MIIdx.getDefIndex();
Evan Chengfb112882009-03-23 08:01:15 +0000460 if (MO.isEarlyClobber())
Lang Hames233a60e2009-11-03 23:52:08 +0000461 defIndex = MIIdx.getUseIndex();
Evan Cheng752195e2009-09-14 21:33:42 +0000462
Evan Cheng7ecb38b2007-08-29 20:45:00 +0000463 VNInfo *ValNo;
Evan Chengc8d044e2008-02-15 18:24:29 +0000464 MachineInstr *CopyMI = NULL;
Jakob Stoklund Olesen04c528a2010-07-16 04:45:42 +0000465 if (mi->isCopyLike())
Evan Chengc8d044e2008-02-15 18:24:29 +0000466 CopyMI = mi;
Lang Hames6e2968c2010-09-25 12:04:16 +0000467 ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator);
Jakob Stoklund Olesen1b293202010-08-12 20:01:23 +0000468
Lang Hames74ab5ee2009-12-22 00:11:50 +0000469 SlotIndex killIndex = getMBBEndIdx(mbb);
Evan Cheng7ecb38b2007-08-29 20:45:00 +0000470 LiveRange LR(defIndex, killIndex, ValNo);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000471 interval.addRange(LR);
Lang Hames857c4e02009-06-17 21:01:20 +0000472 ValNo->setHasPHIKill(true);
Jakob Stoklund Olesendcfe5f32010-02-23 22:43:58 +0000473 DEBUG(dbgs() << " phi-join +" << LR);
Evan Cheng37499432010-05-05 18:27:40 +0000474 } else {
475 llvm_unreachable("Multiply defined register");
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000476 }
477 }
478
David Greene8a342292010-01-04 22:49:02 +0000479 DEBUG(dbgs() << '\n');
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000480}
481
Chris Lattnerf35fef72004-07-23 21:24:19 +0000482void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000483 MachineBasicBlock::iterator mi,
Lang Hames233a60e2009-11-03 23:52:08 +0000484 SlotIndex MIIdx,
Owen Anderson6b098de2008-06-25 23:39:39 +0000485 MachineOperand& MO,
Chris Lattner91725b72006-08-31 05:54:43 +0000486 LiveInterval &interval,
Evan Chengc8d044e2008-02-15 18:24:29 +0000487 MachineInstr *CopyMI) {
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000488 // A physical register cannot be live across basic block, so its
489 // lifetime must end somewhere in its defining basic block.
Jakob Stoklund Olesen43142682011-01-09 03:05:53 +0000490 DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_));
Alkis Evlogimenos02ba13c2004-01-31 23:13:30 +0000491
Lang Hames233a60e2009-11-03 23:52:08 +0000492 SlotIndex baseIndex = MIIdx;
493 SlotIndex start = baseIndex.getDefIndex();
Dale Johannesen86b49f82008-09-24 01:07:17 +0000494 // Earlyclobbers move back one.
495 if (MO.isEarlyClobber())
Lang Hames233a60e2009-11-03 23:52:08 +0000496 start = MIIdx.getUseIndex();
497 SlotIndex end = start;
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000498
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000499 // If it is not used after definition, it is considered dead at
500 // the instruction defining it. Hence its interval is:
501 // [defSlot(def), defSlot(def)+1)
Dale Johannesen39faac22009-09-20 00:36:41 +0000502 // For earlyclobbers, the defSlot was pushed back one; the extra
503 // advance below compensates.
Owen Anderson6b098de2008-06-25 23:39:39 +0000504 if (MO.isDead()) {
David Greene8a342292010-01-04 22:49:02 +0000505 DEBUG(dbgs() << " dead");
Lang Hames233a60e2009-11-03 23:52:08 +0000506 end = start.getStoreIndex();
Chris Lattnerab4b66d2005-08-23 22:51:41 +0000507 goto exit;
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000508 }
509
510 // If it is not dead on definition, it must be killed by a
511 // subsequent instruction. Hence its interval is:
512 // [defSlot(def), useSlot(kill)+1)
Lang Hames233a60e2009-11-03 23:52:08 +0000513 baseIndex = baseIndex.getNextIndex();
Chris Lattner5ab6f5f2005-09-02 00:20:32 +0000514 while (++mi != MBB->end()) {
Lang Hames233a60e2009-11-03 23:52:08 +0000515
Dale Johannesenbd635202010-02-10 00:55:42 +0000516 if (mi->isDebugValue())
517 continue;
Lang Hames233a60e2009-11-03 23:52:08 +0000518 if (getInstructionFromIndex(baseIndex) == 0)
519 baseIndex = indexes_->getNextNonNullIndex(baseIndex);
520
Evan Cheng6130f662008-03-05 00:59:57 +0000521 if (mi->killsRegister(interval.reg, tri_)) {
David Greene8a342292010-01-04 22:49:02 +0000522 DEBUG(dbgs() << " killed");
Lang Hames233a60e2009-11-03 23:52:08 +0000523 end = baseIndex.getDefIndex();
Chris Lattnerab4b66d2005-08-23 22:51:41 +0000524 goto exit;
Evan Chengc45288e2009-04-27 20:42:46 +0000525 } else {
Evan Cheng1015ba72010-05-21 20:53:24 +0000526 int DefIdx = mi->findRegisterDefOperandIdx(interval.reg,false,false,tri_);
Evan Chengc45288e2009-04-27 20:42:46 +0000527 if (DefIdx != -1) {
528 if (mi->isRegTiedToUseOperand(DefIdx)) {
529 // Two-address instruction.
Lang Hames233a60e2009-11-03 23:52:08 +0000530 end = baseIndex.getDefIndex();
Evan Chengc45288e2009-04-27 20:42:46 +0000531 } else {
532 // Another instruction redefines the register before it is ever read.
Dale Johannesenbd635202010-02-10 00:55:42 +0000533 // Then the register is essentially dead at the instruction that
534 // defines it. Hence its interval is:
Evan Chengc45288e2009-04-27 20:42:46 +0000535 // [defSlot(def), defSlot(def)+1)
David Greene8a342292010-01-04 22:49:02 +0000536 DEBUG(dbgs() << " dead");
Lang Hames233a60e2009-11-03 23:52:08 +0000537 end = start.getStoreIndex();
Evan Chengc45288e2009-04-27 20:42:46 +0000538 }
539 goto exit;
540 }
Alkis Evlogimenosaf254732004-01-13 22:26:14 +0000541 }
Jakob Stoklund Olesen1b293202010-08-12 20:01:23 +0000542
Lang Hames233a60e2009-11-03 23:52:08 +0000543 baseIndex = baseIndex.getNextIndex();
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000544 }
Jakob Stoklund Olesen1b293202010-08-12 20:01:23 +0000545
Chris Lattner5ab6f5f2005-09-02 00:20:32 +0000546 // The only case we should have a dead physreg here without a killing or
547 // instruction where we know it's dead is if it is live-in to the function
Evan Chengd521bc92009-04-27 17:36:47 +0000548 // and never used. Another possible case is the implicit use of the
549 // physical register has been deleted by two-address pass.
Lang Hames233a60e2009-11-03 23:52:08 +0000550 end = start.getStoreIndex();
Alkis Evlogimenos02ba13c2004-01-31 23:13:30 +0000551
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000552exit:
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000553 assert(start < end && "did not find end of interval?");
Chris Lattnerf768bba2005-03-09 23:05:19 +0000554
Evan Cheng24a3cc42007-04-25 07:30:23 +0000555 // Already exists? Extend old live interval.
Jakob Stoklund Olesen31cc3ec2010-10-11 21:45:03 +0000556 VNInfo *ValNo = interval.getVNInfoAt(start);
557 bool Extend = ValNo != 0;
558 if (!Extend)
559 ValNo = interval.getNextValue(start, CopyMI, VNInfoAllocator);
560 if (Extend && MO.isEarlyClobber())
Lang Hames857c4e02009-06-17 21:01:20 +0000561 ValNo->setHasRedefByEC(true);
Evan Cheng7ecb38b2007-08-29 20:45:00 +0000562 LiveRange LR(start, end, ValNo);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000563 interval.addRange(LR);
David Greene8a342292010-01-04 22:49:02 +0000564 DEBUG(dbgs() << " +" << LR << '\n');
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000565}
566
Chris Lattnerf35fef72004-07-23 21:24:19 +0000567void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
568 MachineBasicBlock::iterator MI,
Lang Hames233a60e2009-11-03 23:52:08 +0000569 SlotIndex MIIdx,
Evan Chengef0732d2008-07-10 07:35:43 +0000570 MachineOperand& MO,
571 unsigned MOIdx) {
Owen Anderson6b098de2008-06-25 23:39:39 +0000572 if (TargetRegisterInfo::isVirtualRegister(MO.getReg()))
Evan Chengef0732d2008-07-10 07:35:43 +0000573 handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx,
Owen Anderson6b098de2008-06-25 23:39:39 +0000574 getOrCreateInterval(MO.getReg()));
Jakob Stoklund Olesen4662a9f2011-04-04 21:00:03 +0000575 else {
Evan Chengc8d044e2008-02-15 18:24:29 +0000576 MachineInstr *CopyMI = NULL;
Jakob Stoklund Olesen04c528a2010-07-16 04:45:42 +0000577 if (MI->isCopyLike())
Evan Chengc8d044e2008-02-15 18:24:29 +0000578 CopyMI = MI;
Evan Chengc45288e2009-04-27 20:42:46 +0000579 handlePhysicalRegisterDef(MBB, MI, MIIdx, MO,
Owen Anderson6b098de2008-06-25 23:39:39 +0000580 getOrCreateInterval(MO.getReg()), CopyMI);
Chris Lattnerf35fef72004-07-23 21:24:19 +0000581 }
Alkis Evlogimenos4d46e1e2004-01-31 14:37:41 +0000582}
583
Evan Chengb371f452007-02-19 21:49:54 +0000584void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
Lang Hames233a60e2009-11-03 23:52:08 +0000585 SlotIndex MIIdx,
Evan Cheng24a3cc42007-04-25 07:30:23 +0000586 LiveInterval &interval, bool isAlias) {
Jakob Stoklund Olesen43142682011-01-09 03:05:53 +0000587 DEBUG(dbgs() << "\t\tlivein register: " << PrintReg(interval.reg, tri_));
Evan Chengb371f452007-02-19 21:49:54 +0000588
589 // Look for kills, if it reaches a def before it's killed, then it shouldn't
590 // be considered a livein.
591 MachineBasicBlock::iterator mi = MBB->begin();
Evan Cheng4507f082010-03-16 21:51:27 +0000592 MachineBasicBlock::iterator E = MBB->end();
593 // Skip over DBG_VALUE at the start of the MBB.
594 if (mi != E && mi->isDebugValue()) {
595 while (++mi != E && mi->isDebugValue())
596 ;
597 if (mi == E)
598 // MBB is empty except for DBG_VALUE's.
599 return;
600 }
601
Lang Hames233a60e2009-11-03 23:52:08 +0000602 SlotIndex baseIndex = MIIdx;
603 SlotIndex start = baseIndex;
604 if (getInstructionFromIndex(baseIndex) == 0)
605 baseIndex = indexes_->getNextNonNullIndex(baseIndex);
606
607 SlotIndex end = baseIndex;
Evan Cheng0076c612009-03-05 03:34:26 +0000608 bool SeenDefUse = false;
Evan Chengb371f452007-02-19 21:49:54 +0000609
Dale Johannesenbd635202010-02-10 00:55:42 +0000610 while (mi != E) {
Dale Johannesen1d0aeab2010-02-10 01:31:26 +0000611 if (mi->killsRegister(interval.reg, tri_)) {
612 DEBUG(dbgs() << " killed");
613 end = baseIndex.getDefIndex();
614 SeenDefUse = true;
615 break;
Evan Cheng1015ba72010-05-21 20:53:24 +0000616 } else if (mi->definesRegister(interval.reg, tri_)) {
Dale Johannesen1d0aeab2010-02-10 01:31:26 +0000617 // Another instruction redefines the register before it is ever read.
618 // Then the register is essentially dead at the instruction that defines
619 // it. Hence its interval is:
620 // [defSlot(def), defSlot(def)+1)
621 DEBUG(dbgs() << " dead");
622 end = start.getStoreIndex();
623 SeenDefUse = true;
624 break;
625 }
626
Evan Cheng4507f082010-03-16 21:51:27 +0000627 while (++mi != E && mi->isDebugValue())
628 // Skip over DBG_VALUE.
629 ;
630 if (mi != E)
Lang Hames233a60e2009-11-03 23:52:08 +0000631 baseIndex = indexes_->getNextNonNullIndex(baseIndex);
Evan Chengb371f452007-02-19 21:49:54 +0000632 }
633
Evan Cheng75611fb2007-06-27 01:16:36 +0000634 // Live-in register might not be used at all.
Evan Cheng0076c612009-03-05 03:34:26 +0000635 if (!SeenDefUse) {
Evan Cheng292da942007-06-27 18:47:28 +0000636 if (isAlias) {
David Greene8a342292010-01-04 22:49:02 +0000637 DEBUG(dbgs() << " dead");
Lang Hames233a60e2009-11-03 23:52:08 +0000638 end = MIIdx.getStoreIndex();
Evan Cheng292da942007-06-27 18:47:28 +0000639 } else {
David Greene8a342292010-01-04 22:49:02 +0000640 DEBUG(dbgs() << " live through");
Evan Cheng292da942007-06-27 18:47:28 +0000641 end = baseIndex;
642 }
Evan Cheng24a3cc42007-04-25 07:30:23 +0000643 }
644
Lang Hames6e2968c2010-09-25 12:04:16 +0000645 SlotIndex defIdx = getMBBStartIdx(MBB);
646 assert(getInstructionFromIndex(defIdx) == 0 &&
647 "PHI def index points at actual instruction.");
Lang Hames10382fb2009-06-19 02:17:53 +0000648 VNInfo *vni =
Lang Hames6e2968c2010-09-25 12:04:16 +0000649 interval.getNextValue(defIdx, 0, VNInfoAllocator);
Lang Hamesd21c3162009-06-18 22:01:47 +0000650 vni->setIsPHIDef(true);
651 LiveRange LR(start, end, vni);
Jakob Stoklund Olesen3de23e62009-11-07 01:58:40 +0000652
Jim Laskey9b25b8c2007-02-21 22:41:17 +0000653 interval.addRange(LR);
David Greene8a342292010-01-04 22:49:02 +0000654 DEBUG(dbgs() << " +" << LR << '\n');
Evan Chengb371f452007-02-19 21:49:54 +0000655}
656
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000657/// computeIntervals - computes the live intervals for virtual
Alkis Evlogimenos4d46e1e2004-01-31 14:37:41 +0000658/// registers. for some ordering of the machine instructions [1,N] a
Alkis Evlogimenos08cec002004-01-31 19:59:32 +0000659/// live interval is an interval [i, j) where 1 <= i <= j < N for
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000660/// which a variable is live
Jakob Stoklund Olesen1b293202010-08-12 20:01:23 +0000661void LiveIntervals::computeIntervals() {
David Greene8a342292010-01-04 22:49:02 +0000662 DEBUG(dbgs() << "********** COMPUTING LIVE INTERVALS **********\n"
Bill Wendling8e6179f2009-08-22 20:18:03 +0000663 << "********** Function: "
664 << ((Value*)mf_->getFunction())->getName() << '\n');
Evan Chengd129d732009-07-17 19:43:40 +0000665
666 SmallVector<unsigned, 8> UndefUses;
Chris Lattner428b92e2006-09-15 03:57:23 +0000667 for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end();
668 MBBI != E; ++MBBI) {
669 MachineBasicBlock *MBB = MBBI;
Evan Cheng00a99a32010-02-06 09:07:11 +0000670 if (MBB->empty())
671 continue;
672
Owen Anderson134eb732008-09-21 20:43:24 +0000673 // Track the index of the current machine instr.
Lang Hames233a60e2009-11-03 23:52:08 +0000674 SlotIndex MIIndex = getMBBStartIdx(MBB);
Bob Wilsonad98f792010-05-03 21:38:11 +0000675 DEBUG(dbgs() << "BB#" << MBB->getNumber()
676 << ":\t\t# derived from " << MBB->getName() << "\n");
Alkis Evlogimenos6b4edba2003-12-21 20:19:10 +0000677
Dan Gohmancb406c22007-10-03 19:26:29 +0000678 // Create intervals for live-ins to this BB first.
Dan Gohman81bf03e2010-04-13 16:57:55 +0000679 for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(),
Dan Gohmancb406c22007-10-03 19:26:29 +0000680 LE = MBB->livein_end(); LI != LE; ++LI) {
681 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI));
682 // Multiple live-ins can alias the same register.
Dan Gohman6f0d0242008-02-10 18:45:23 +0000683 for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS)
Dan Gohmancb406c22007-10-03 19:26:29 +0000684 if (!hasInterval(*AS))
685 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS),
686 true);
Chris Lattnerdffb2e82006-09-04 18:27:40 +0000687 }
Jakob Stoklund Olesen1b293202010-08-12 20:01:23 +0000688
Owen Anderson99500ae2008-09-15 22:00:38 +0000689 // Skip over empty initial indices.
Lang Hames233a60e2009-11-03 23:52:08 +0000690 if (getInstructionFromIndex(MIIndex) == 0)
691 MIIndex = indexes_->getNextNonNullIndex(MIIndex);
Jakob Stoklund Olesen1b293202010-08-12 20:01:23 +0000692
Dale Johannesen1caedd02010-01-22 22:38:21 +0000693 for (MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
694 MI != miEnd; ++MI) {
David Greene8a342292010-01-04 22:49:02 +0000695 DEBUG(dbgs() << MIIndex << "\t" << *MI);
Chris Lattner518bb532010-02-09 19:54:29 +0000696 if (MI->isDebugValue())
Dale Johannesen1caedd02010-01-22 22:38:21 +0000697 continue;
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000698
Evan Cheng438f7bc2006-11-10 08:43:01 +0000699 // Handle defs.
Chris Lattner428b92e2006-09-15 03:57:23 +0000700 for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
701 MachineOperand &MO = MI->getOperand(i);
Evan Chengd129d732009-07-17 19:43:40 +0000702 if (!MO.isReg() || !MO.getReg())
703 continue;
704
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000705 // handle register defs - build intervals
Evan Chengd129d732009-07-17 19:43:40 +0000706 if (MO.isDef())
Evan Chengef0732d2008-07-10 07:35:43 +0000707 handleRegisterDef(MBB, MI, MIIndex, MO, i);
Evan Chengd129d732009-07-17 19:43:40 +0000708 else if (MO.isUndef())
709 UndefUses.push_back(MO.getReg());
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000710 }
Jakob Stoklund Olesen1b293202010-08-12 20:01:23 +0000711
Lang Hames233a60e2009-11-03 23:52:08 +0000712 // Move to the next instr slot.
713 MIIndex = indexes_->getNextNonNullIndex(MIIndex);
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000714 }
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000715 }
Evan Chengd129d732009-07-17 19:43:40 +0000716
717 // Create empty intervals for registers defined by implicit_def's (except
718 // for those implicit_def that define values which are liveout of their
719 // blocks.
720 for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) {
721 unsigned UndefReg = UndefUses[i];
722 (void)getOrCreateInterval(UndefReg);
723 }
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000724}
Alkis Evlogimenosb27ef242003-12-05 10:38:28 +0000725
Owen Anderson03857b22008-08-13 21:49:13 +0000726LiveInterval* LiveIntervals::createInterval(unsigned reg) {
Evan Cheng0a1fcce2009-02-08 11:04:35 +0000727 float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F;
Owen Anderson03857b22008-08-13 21:49:13 +0000728 return new LiveInterval(reg, Weight);
Alkis Evlogimenos9a8b4902004-04-09 18:07:57 +0000729}
Evan Chengf2fbca62007-11-12 06:35:08 +0000730
Evan Cheng0a1fcce2009-02-08 11:04:35 +0000731/// dupInterval - Duplicate a live interval. The caller is responsible for
732/// managing the allocated memory.
733LiveInterval* LiveIntervals::dupInterval(LiveInterval *li) {
734 LiveInterval *NewLI = createInterval(li->reg);
Evan Cheng90f95f82009-06-14 20:22:55 +0000735 NewLI->Copy(*li, mri_, getVNInfoAllocator());
Evan Cheng0a1fcce2009-02-08 11:04:35 +0000736 return NewLI;
737}
738
Jakob Stoklund Olesen11513e52011-02-08 00:03:05 +0000739/// shrinkToUses - After removing some uses of a register, shrink its live
740/// range to just the remaining uses. This method does not compute reaching
741/// defs for new uses, and it doesn't remove dead defs.
Jakob Stoklund Olesen6a3dbd32011-03-17 20:37:07 +0000742bool LiveIntervals::shrinkToUses(LiveInterval *li,
Jakob Stoklund Olesen0d8ccaa2011-03-07 23:29:10 +0000743 SmallVectorImpl<MachineInstr*> *dead) {
Jakob Stoklund Olesen11513e52011-02-08 00:03:05 +0000744 DEBUG(dbgs() << "Shrink: " << *li << '\n');
745 assert(TargetRegisterInfo::isVirtualRegister(li->reg)
746 && "Can't only shrink physical registers");
747 // Find all the values used, including PHI kills.
748 SmallVector<std::pair<SlotIndex, VNInfo*>, 16> WorkList;
749
750 // Visit all instructions reading li->reg.
751 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li->reg);
752 MachineInstr *UseMI = I.skipInstruction();) {
753 if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg))
754 continue;
755 SlotIndex Idx = getInstructionIndex(UseMI).getUseIndex();
756 VNInfo *VNI = li->getVNInfoAt(Idx);
Jakob Stoklund Olesen9ef931e2011-03-18 03:06:04 +0000757 if (!VNI) {
758 // This shouldn't happen: readsVirtualRegister returns true, but there is
759 // no live value. It is likely caused by a target getting <undef> flags
760 // wrong.
761 DEBUG(dbgs() << Idx << '\t' << *UseMI
762 << "Warning: Instr claims to read non-existent value in "
763 << *li << '\n');
764 continue;
765 }
Jakob Stoklund Olesen11513e52011-02-08 00:03:05 +0000766 if (VNI->def == Idx) {
767 // Special case: An early-clobber tied operand reads and writes the
768 // register one slot early.
769 Idx = Idx.getPrevSlot();
770 VNI = li->getVNInfoAt(Idx);
771 assert(VNI && "Early-clobber tied value not available");
772 }
773 WorkList.push_back(std::make_pair(Idx, VNI));
774 }
775
776 // Create a new live interval with only minimal live segments per def.
777 LiveInterval NewLI(li->reg, 0);
778 for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end();
779 I != E; ++I) {
780 VNInfo *VNI = *I;
781 if (VNI->isUnused())
782 continue;
Jakob Stoklund Olesene815dab2011-04-07 18:43:14 +0000783 // We may eliminate PHI values, so recompute PHIKill flags.
784 VNI->setHasPHIKill(false);
Jakob Stoklund Olesen11513e52011-02-08 00:03:05 +0000785 NewLI.addRange(LiveRange(VNI->def, VNI->def.getNextSlot(), VNI));
Jakob Stoklund Olesena9d5c272011-03-07 18:56:16 +0000786
787 // A use tied to an early-clobber def ends at the load slot and isn't caught
788 // above. Catch it here instead. This probably only ever happens for inline
789 // assembly.
790 if (VNI->def.isUse())
791 if (VNInfo *UVNI = li->getVNInfoAt(VNI->def.getLoadIndex()))
792 WorkList.push_back(std::make_pair(VNI->def.getLoadIndex(), UVNI));
Jakob Stoklund Olesen11513e52011-02-08 00:03:05 +0000793 }
794
Jakob Stoklund Olesene0ab2452011-03-02 00:33:03 +0000795 // Keep track of the PHIs that are in use.
796 SmallPtrSet<VNInfo*, 8> UsedPHIs;
797
Jakob Stoklund Olesen11513e52011-02-08 00:03:05 +0000798 // Extend intervals to reach all uses in WorkList.
799 while (!WorkList.empty()) {
800 SlotIndex Idx = WorkList.back().first;
801 VNInfo *VNI = WorkList.back().second;
802 WorkList.pop_back();
Jakob Stoklund Olesen11513e52011-02-08 00:03:05 +0000803 const MachineBasicBlock *MBB = getMBBFromIndex(Idx);
804 SlotIndex BlockStart = getMBBStartIdx(MBB);
Jakob Stoklund Olesene0ab2452011-03-02 00:33:03 +0000805
806 // Extend the live range for VNI to be live at Idx.
807 if (VNInfo *ExtVNI = NewLI.extendInBlock(BlockStart, Idx)) {
Nick Lewycky4b11a702011-03-02 01:43:30 +0000808 (void)ExtVNI;
Jakob Stoklund Olesene0ab2452011-03-02 00:33:03 +0000809 assert(ExtVNI == VNI && "Unexpected existing value number");
810 // Is this a PHIDef we haven't seen before?
Jakob Stoklund Olesenc29d9b32011-03-03 00:20:51 +0000811 if (!VNI->isPHIDef() || VNI->def != BlockStart || !UsedPHIs.insert(VNI))
Jakob Stoklund Olesene0ab2452011-03-02 00:33:03 +0000812 continue;
813 // The PHI is live, make sure the predecessors are live-out.
814 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
815 PE = MBB->pred_end(); PI != PE; ++PI) {
816 SlotIndex Stop = getMBBEndIdx(*PI).getPrevSlot();
817 VNInfo *PVNI = li->getVNInfoAt(Stop);
818 // A predecessor is not required to have a live-out value for a PHI.
819 if (PVNI) {
Jakob Stoklund Olesene815dab2011-04-07 18:43:14 +0000820 PVNI->setHasPHIKill(true);
Jakob Stoklund Olesene0ab2452011-03-02 00:33:03 +0000821 WorkList.push_back(std::make_pair(Stop, PVNI));
Jakob Stoklund Olesen11513e52011-02-08 00:03:05 +0000822 }
823 }
Jakob Stoklund Olesen11513e52011-02-08 00:03:05 +0000824 continue;
825 }
826
827 // VNI is live-in to MBB.
828 DEBUG(dbgs() << " live-in at " << BlockStart << '\n');
829 NewLI.addRange(LiveRange(BlockStart, Idx.getNextSlot(), VNI));
830
831 // Make sure VNI is live-out from the predecessors.
832 for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(),
833 PE = MBB->pred_end(); PI != PE; ++PI) {
834 SlotIndex Stop = getMBBEndIdx(*PI).getPrevSlot();
835 assert(li->getVNInfoAt(Stop) == VNI && "Wrong value out of predecessor");
836 WorkList.push_back(std::make_pair(Stop, VNI));
837 }
838 }
839
840 // Handle dead values.
Jakob Stoklund Olesen6a3dbd32011-03-17 20:37:07 +0000841 bool CanSeparate = false;
Jakob Stoklund Olesen11513e52011-02-08 00:03:05 +0000842 for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end();
843 I != E; ++I) {
844 VNInfo *VNI = *I;
845 if (VNI->isUnused())
846 continue;
847 LiveInterval::iterator LII = NewLI.FindLiveRangeContaining(VNI->def);
848 assert(LII != NewLI.end() && "Missing live range for PHI");
849 if (LII->end != VNI->def.getNextSlot())
850 continue;
Jakob Stoklund Olesena4d34732011-03-02 00:33:01 +0000851 if (VNI->isPHIDef()) {
Jakob Stoklund Olesen11513e52011-02-08 00:03:05 +0000852 // This is a dead PHI. Remove it.
853 VNI->setIsUnused(true);
854 NewLI.removeRange(*LII);
Jakob Stoklund Olesen6a3dbd32011-03-17 20:37:07 +0000855 DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n");
856 CanSeparate = true;
Jakob Stoklund Olesen11513e52011-02-08 00:03:05 +0000857 } else {
858 // This is a dead def. Make sure the instruction knows.
859 MachineInstr *MI = getInstructionFromIndex(VNI->def);
860 assert(MI && "No instruction defining live value");
861 MI->addRegisterDead(li->reg, tri_);
Jakob Stoklund Olesen0d8ccaa2011-03-07 23:29:10 +0000862 if (dead && MI->allDefsAreDead()) {
Jakob Stoklund Olesenc46570d2011-03-16 22:56:08 +0000863 DEBUG(dbgs() << "All defs dead: " << VNI->def << '\t' << *MI);
Jakob Stoklund Olesen0d8ccaa2011-03-07 23:29:10 +0000864 dead->push_back(MI);
865 }
Jakob Stoklund Olesen11513e52011-02-08 00:03:05 +0000866 }
867 }
868
869 // Move the trimmed ranges back.
870 li->ranges.swap(NewLI.ranges);
Jakob Stoklund Olesenc46570d2011-03-16 22:56:08 +0000871 DEBUG(dbgs() << "Shrunk: " << *li << '\n');
Jakob Stoklund Olesen6a3dbd32011-03-17 20:37:07 +0000872 return CanSeparate;
Jakob Stoklund Olesen11513e52011-02-08 00:03:05 +0000873}
874
875
Evan Chengf2fbca62007-11-12 06:35:08 +0000876//===----------------------------------------------------------------------===//
877// Register allocator hooks.
878//
879
Jakob Stoklund Olesencb640472011-02-04 19:33:11 +0000880MachineBasicBlock::iterator
881LiveIntervals::getLastSplitPoint(const LiveInterval &li,
Jakob Stoklund Olesenf0ac26c2011-02-09 22:50:26 +0000882 MachineBasicBlock *mbb) const {
Jakob Stoklund Olesencb640472011-02-04 19:33:11 +0000883 const MachineBasicBlock *lpad = mbb->getLandingPadSuccessor();
884
885 // If li is not live into a landing pad, we can insert spill code before the
886 // first terminator.
887 if (!lpad || !isLiveInToMBB(li, lpad))
888 return mbb->getFirstTerminator();
889
890 // When there is a landing pad, spill code must go before the call instruction
891 // that can throw.
892 MachineBasicBlock::iterator I = mbb->end(), B = mbb->begin();
893 while (I != B) {
894 --I;
895 if (I->getDesc().isCall())
896 return I;
897 }
Jakob Stoklund Olesen45e53972011-02-04 23:11:13 +0000898 // The block contains no calls that can throw, so use the first terminator.
Jakob Stoklund Olesencb640472011-02-04 19:33:11 +0000899 return mbb->getFirstTerminator();
900}
901
Jakob Stoklund Olesen8a61da82011-02-08 21:13:03 +0000902void LiveIntervals::addKillFlags() {
903 for (iterator I = begin(), E = end(); I != E; ++I) {
904 unsigned Reg = I->first;
905 if (TargetRegisterInfo::isPhysicalRegister(Reg))
906 continue;
907 if (mri_->reg_nodbg_empty(Reg))
908 continue;
909 LiveInterval *LI = I->second;
910
911 // Every instruction that kills Reg corresponds to a live range end point.
912 for (LiveInterval::iterator RI = LI->begin(), RE = LI->end(); RI != RE;
913 ++RI) {
914 // A LOAD index indicates an MBB edge.
915 if (RI->end.isLoad())
916 continue;
917 MachineInstr *MI = getInstructionFromIndex(RI->end);
918 if (!MI)
919 continue;
920 MI->addRegisterKilled(Reg, NULL);
921 }
922 }
923}
924
Evan Chengd70dbb52008-02-22 09:24:50 +0000925/// getReMatImplicitUse - If the remat definition MI has one (for now, we only
926/// allow one) virtual register operand, then its uses are implicitly using
927/// the register. Returns the virtual register.
928unsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li,
929 MachineInstr *MI) const {
930 unsigned RegOp = 0;
931 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
932 MachineOperand &MO = MI->getOperand(i);
Dan Gohmand735b802008-10-03 15:45:36 +0000933 if (!MO.isReg() || !MO.isUse())
Evan Chengd70dbb52008-02-22 09:24:50 +0000934 continue;
935 unsigned Reg = MO.getReg();
936 if (Reg == 0 || Reg == li.reg)
937 continue;
Jakob Stoklund Olesen1b293202010-08-12 20:01:23 +0000938
Chris Lattner1873d0c2009-06-27 04:06:41 +0000939 if (TargetRegisterInfo::isPhysicalRegister(Reg) &&
940 !allocatableRegs_[Reg])
941 continue;
Evan Chengd70dbb52008-02-22 09:24:50 +0000942 // FIXME: For now, only remat MI with at most one register operand.
943 assert(!RegOp &&
944 "Can't rematerialize instruction with multiple register operand!");
945 RegOp = MO.getReg();
Dan Gohman6d69ba82008-07-25 00:02:30 +0000946#ifndef NDEBUG
Evan Chengd70dbb52008-02-22 09:24:50 +0000947 break;
Dan Gohman6d69ba82008-07-25 00:02:30 +0000948#endif
Evan Chengd70dbb52008-02-22 09:24:50 +0000949 }
950 return RegOp;
951}
952
953/// isValNoAvailableAt - Return true if the val# of the specified interval
954/// which reaches the given instruction also reaches the specified use index.
955bool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI,
Lang Hames233a60e2009-11-03 23:52:08 +0000956 SlotIndex UseIdx) const {
Jakob Stoklund Olesen31cc3ec2010-10-11 21:45:03 +0000957 VNInfo *UValNo = li.getVNInfoAt(UseIdx);
958 return UValNo && UValNo == li.getVNInfoAt(getInstructionIndex(MI));
Evan Chengd70dbb52008-02-22 09:24:50 +0000959}
960
Evan Chengf2fbca62007-11-12 06:35:08 +0000961/// isReMaterializable - Returns true if the definition MI of the specified
962/// val# of the specified interval is re-materializable.
Andrew Trickf4baeaf2010-11-10 19:18:47 +0000963bool
964LiveIntervals::isReMaterializable(const LiveInterval &li,
965 const VNInfo *ValNo, MachineInstr *MI,
Jakob Stoklund Olesen38f6bd02011-03-10 01:21:58 +0000966 const SmallVectorImpl<LiveInterval*> *SpillIs,
Andrew Trickf4baeaf2010-11-10 19:18:47 +0000967 bool &isLoad) {
Evan Chengf2fbca62007-11-12 06:35:08 +0000968 if (DisableReMat)
969 return false;
970
Dan Gohmana70dca12009-10-09 23:27:56 +0000971 if (!tii_->isTriviallyReMaterializable(MI, aa_))
972 return false;
Evan Chengdd3465e2008-02-23 01:44:27 +0000973
Dan Gohmana70dca12009-10-09 23:27:56 +0000974 // Target-specific code can mark an instruction as being rematerializable
975 // if it has one virtual reg use, though it had better be something like
976 // a PIC base register which is likely to be live everywhere.
Dan Gohman6d69ba82008-07-25 00:02:30 +0000977 unsigned ImpUse = getReMatImplicitUse(li, MI);
978 if (ImpUse) {
979 const LiveInterval &ImpLi = getInterval(ImpUse);
Evan Cheng28a1e482010-03-30 05:49:07 +0000980 for (MachineRegisterInfo::use_nodbg_iterator
981 ri = mri_->use_nodbg_begin(li.reg), re = mri_->use_nodbg_end();
982 ri != re; ++ri) {
Dan Gohman6d69ba82008-07-25 00:02:30 +0000983 MachineInstr *UseMI = &*ri;
Lang Hames233a60e2009-11-03 23:52:08 +0000984 SlotIndex UseIdx = getInstructionIndex(UseMI);
Jakob Stoklund Olesen31cc3ec2010-10-11 21:45:03 +0000985 if (li.getVNInfoAt(UseIdx) != ValNo)
Dan Gohman6d69ba82008-07-25 00:02:30 +0000986 continue;
987 if (!isValNoAvailableAt(ImpLi, MI, UseIdx))
988 return false;
989 }
Evan Chengdc377862008-09-30 15:44:16 +0000990
991 // If a register operand of the re-materialized instruction is going to
992 // be spilled next, then it's not legal to re-materialize this instruction.
Jakob Stoklund Olesen38f6bd02011-03-10 01:21:58 +0000993 if (SpillIs)
994 for (unsigned i = 0, e = SpillIs->size(); i != e; ++i)
995 if (ImpUse == (*SpillIs)[i]->reg)
996 return false;
Dan Gohman6d69ba82008-07-25 00:02:30 +0000997 }
998 return true;
Evan Cheng5ef3a042007-12-06 00:01:56 +0000999}
1000
Evan Cheng06587492008-10-24 02:05:00 +00001001/// isReMaterializable - Returns true if the definition MI of the specified
1002/// val# of the specified interval is re-materializable.
1003bool LiveIntervals::isReMaterializable(const LiveInterval &li,
1004 const VNInfo *ValNo, MachineInstr *MI) {
Evan Cheng06587492008-10-24 02:05:00 +00001005 bool Dummy2;
Jakob Stoklund Olesen38f6bd02011-03-10 01:21:58 +00001006 return isReMaterializable(li, ValNo, MI, 0, Dummy2);
Evan Cheng06587492008-10-24 02:05:00 +00001007}
1008
Evan Cheng5ef3a042007-12-06 00:01:56 +00001009/// isReMaterializable - Returns true if every definition of MI of every
1010/// val# of the specified interval is re-materializable.
Andrew Trickf4baeaf2010-11-10 19:18:47 +00001011bool
1012LiveIntervals::isReMaterializable(const LiveInterval &li,
Jakob Stoklund Olesen38f6bd02011-03-10 01:21:58 +00001013 const SmallVectorImpl<LiveInterval*> *SpillIs,
Andrew Trickf4baeaf2010-11-10 19:18:47 +00001014 bool &isLoad) {
Evan Cheng5ef3a042007-12-06 00:01:56 +00001015 isLoad = false;
1016 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
1017 i != e; ++i) {
1018 const VNInfo *VNI = *i;
Lang Hames857c4e02009-06-17 21:01:20 +00001019 if (VNI->isUnused())
Evan Cheng5ef3a042007-12-06 00:01:56 +00001020 continue; // Dead val#.
1021 // Is the def for the val# rematerializable?
Lang Hames857c4e02009-06-17 21:01:20 +00001022 MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def);
Lang Hames6e2968c2010-09-25 12:04:16 +00001023 if (!ReMatDefMI)
1024 return false;
Evan Cheng5ef3a042007-12-06 00:01:56 +00001025 bool DefIsLoad = false;
Evan Chengd70dbb52008-02-22 09:24:50 +00001026 if (!ReMatDefMI ||
Evan Chengdc377862008-09-30 15:44:16 +00001027 !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad))
Evan Cheng5ef3a042007-12-06 00:01:56 +00001028 return false;
1029 isLoad |= DefIsLoad;
Evan Chengf2fbca62007-11-12 06:35:08 +00001030 }
1031 return true;
1032}
1033
Evan Cheng79a0c1e2008-02-25 08:50:41 +00001034/// FilterFoldedOps - Filter out two-address use operands. Return
1035/// true if it finds any issue with the operands that ought to prevent
1036/// folding.
1037static bool FilterFoldedOps(MachineInstr *MI,
1038 SmallVector<unsigned, 2> &Ops,
1039 unsigned &MRInfo,
1040 SmallVector<unsigned, 2> &FoldOps) {
Evan Cheng79a0c1e2008-02-25 08:50:41 +00001041 MRInfo = 0;
Evan Chengaee4af62007-12-02 08:30:39 +00001042 for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
1043 unsigned OpIdx = Ops[i];
Evan Chengd70dbb52008-02-22 09:24:50 +00001044 MachineOperand &MO = MI->getOperand(OpIdx);
Evan Chengaee4af62007-12-02 08:30:39 +00001045 // FIXME: fold subreg use.
Evan Chengd70dbb52008-02-22 09:24:50 +00001046 if (MO.getSubReg())
Evan Cheng79a0c1e2008-02-25 08:50:41 +00001047 return true;
Evan Chengd70dbb52008-02-22 09:24:50 +00001048 if (MO.isDef())
Evan Chengaee4af62007-12-02 08:30:39 +00001049 MRInfo |= (unsigned)VirtRegMap::isMod;
1050 else {
1051 // Filter out two-address use operand(s).
Evan Chenga24752f2009-03-19 20:30:06 +00001052 if (MI->isRegTiedToDefOperand(OpIdx)) {
Evan Chengaee4af62007-12-02 08:30:39 +00001053 MRInfo = VirtRegMap::isModRef;
1054 continue;
1055 }
1056 MRInfo |= (unsigned)VirtRegMap::isRef;
1057 }
1058 FoldOps.push_back(OpIdx);
Evan Chenge62f97c2007-12-01 02:07:52 +00001059 }
Evan Cheng79a0c1e2008-02-25 08:50:41 +00001060 return false;
1061}
Jakob Stoklund Olesen1b293202010-08-12 20:01:23 +00001062
Evan Cheng79a0c1e2008-02-25 08:50:41 +00001063
1064/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from
1065/// slot / to reg or any rematerialized load into ith operand of specified
1066/// MI. If it is successul, MI is updated with the newly created MI and
1067/// returns true.
1068bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI,
1069 VirtRegMap &vrm, MachineInstr *DefMI,
Lang Hames233a60e2009-11-03 23:52:08 +00001070 SlotIndex InstrIdx,
Evan Cheng79a0c1e2008-02-25 08:50:41 +00001071 SmallVector<unsigned, 2> &Ops,
1072 bool isSS, int Slot, unsigned Reg) {
Evan Cheng79a0c1e2008-02-25 08:50:41 +00001073 // If it is an implicit def instruction, just delete it.
Chris Lattner518bb532010-02-09 19:54:29 +00001074 if (MI->isImplicitDef()) {
Evan Cheng79a0c1e2008-02-25 08:50:41 +00001075 RemoveMachineInstrFromMaps(MI);
1076 vrm.RemoveMachineInstrFromMaps(MI);
1077 MI->eraseFromParent();
1078 ++numFolds;
1079 return true;
1080 }
1081
1082 // Filter the list of operand indexes that are to be folded. Abort if
1083 // any operand will prevent folding.
1084 unsigned MRInfo = 0;
1085 SmallVector<unsigned, 2> FoldOps;
1086 if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps))
1087 return false;
Evan Chenge62f97c2007-12-01 02:07:52 +00001088
Evan Cheng427f4c12008-03-31 23:19:51 +00001089 // The only time it's safe to fold into a two address instruction is when
1090 // it's folding reload and spill from / into a spill stack slot.
1091 if (DefMI && (MRInfo & VirtRegMap::isMod))
Evan Cheng249ded32008-02-23 03:38:34 +00001092 return false;
1093
Jakob Stoklund Olesene05442d2010-07-09 17:29:08 +00001094 MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(MI, FoldOps, Slot)
1095 : tii_->foldMemoryOperand(MI, FoldOps, DefMI);
Evan Chengf2fbca62007-11-12 06:35:08 +00001096 if (fmi) {
Evan Chengd3653122008-02-27 03:04:06 +00001097 // Remember this instruction uses the spill slot.
1098 if (isSS) vrm.addSpillSlotUse(Slot, fmi);
1099
Evan Chengf2fbca62007-11-12 06:35:08 +00001100 // Attempt to fold the memory reference into the instruction. If
1101 // we can do this, we don't need to insert spill code.
Evan Cheng84802932008-01-10 08:24:38 +00001102 if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot))
Evan Chengaee4af62007-12-02 08:30:39 +00001103 vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo);
Evan Cheng81a03822007-11-17 00:40:40 +00001104 vrm.transferSpillPts(MI, fmi);
Evan Cheng0cbb1162007-11-29 01:06:25 +00001105 vrm.transferRestorePts(MI, fmi);
Evan Chengc1f53c72008-03-11 21:34:46 +00001106 vrm.transferEmergencySpills(MI, fmi);
Lang Hames233a60e2009-11-03 23:52:08 +00001107 ReplaceMachineInstrInMaps(MI, fmi);
Jakob Stoklund Olesene05442d2010-07-09 17:29:08 +00001108 MI->eraseFromParent();
1109 MI = fmi;
Evan Cheng0cbb1162007-11-29 01:06:25 +00001110 ++numFolds;
Evan Chengf2fbca62007-11-12 06:35:08 +00001111 return true;
1112 }
1113 return false;
1114}
1115
Evan Cheng018f9b02007-12-05 03:22:34 +00001116/// canFoldMemoryOperand - Returns true if the specified load / store
1117/// folding is possible.
1118bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI,
Evan Cheng79a0c1e2008-02-25 08:50:41 +00001119 SmallVector<unsigned, 2> &Ops,
Evan Cheng3c75ba82008-04-01 21:37:32 +00001120 bool ReMat) const {
Evan Cheng79a0c1e2008-02-25 08:50:41 +00001121 // Filter the list of operand indexes that are to be folded. Abort if
1122 // any operand will prevent folding.
1123 unsigned MRInfo = 0;
Evan Cheng018f9b02007-12-05 03:22:34 +00001124 SmallVector<unsigned, 2> FoldOps;
Evan Cheng79a0c1e2008-02-25 08:50:41 +00001125 if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps))
1126 return false;
Evan Cheng018f9b02007-12-05 03:22:34 +00001127
Evan Cheng3c75ba82008-04-01 21:37:32 +00001128 // It's only legal to remat for a use, not a def.
1129 if (ReMat && (MRInfo & VirtRegMap::isMod))
Evan Cheng79a0c1e2008-02-25 08:50:41 +00001130 return false;
Evan Cheng018f9b02007-12-05 03:22:34 +00001131
Evan Chengd70dbb52008-02-22 09:24:50 +00001132 return tii_->canFoldMemoryOperand(MI, FoldOps);
1133}
1134
Evan Cheng81a03822007-11-17 00:40:40 +00001135bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const {
Lang Hames233a60e2009-11-03 23:52:08 +00001136 LiveInterval::Ranges::const_iterator itr = li.ranges.begin();
1137
1138 MachineBasicBlock *mbb = indexes_->getMBBCoveringRange(itr->start, itr->end);
1139
1140 if (mbb == 0)
1141 return false;
1142
1143 for (++itr; itr != li.ranges.end(); ++itr) {
1144 MachineBasicBlock *mbb2 =
1145 indexes_->getMBBCoveringRange(itr->start, itr->end);
1146
1147 if (mbb2 != mbb)
Evan Cheng81a03822007-11-17 00:40:40 +00001148 return false;
1149 }
Lang Hames233a60e2009-11-03 23:52:08 +00001150
Evan Cheng81a03822007-11-17 00:40:40 +00001151 return true;
1152}
1153
Evan Chengd70dbb52008-02-22 09:24:50 +00001154/// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of
1155/// interval on to-be re-materialized operands of MI) with new register.
1156void LiveIntervals::rewriteImplicitOps(const LiveInterval &li,
1157 MachineInstr *MI, unsigned NewVReg,
1158 VirtRegMap &vrm) {
1159 // There is an implicit use. That means one of the other operand is
1160 // being remat'ed and the remat'ed instruction has li.reg as an
1161 // use operand. Make sure we rewrite that as well.
1162 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1163 MachineOperand &MO = MI->getOperand(i);
Dan Gohmand735b802008-10-03 15:45:36 +00001164 if (!MO.isReg())
Evan Chengd70dbb52008-02-22 09:24:50 +00001165 continue;
1166 unsigned Reg = MO.getReg();
Jakob Stoklund Olesenc9df0252011-01-10 02:58:51 +00001167 if (!TargetRegisterInfo::isVirtualRegister(Reg))
Evan Chengd70dbb52008-02-22 09:24:50 +00001168 continue;
1169 if (!vrm.isReMaterialized(Reg))
1170 continue;
1171 MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg);
Evan Cheng6130f662008-03-05 00:59:57 +00001172 MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg);
1173 if (UseMO)
1174 UseMO->setReg(NewVReg);
Evan Chengd70dbb52008-02-22 09:24:50 +00001175 }
1176}
1177
Evan Chengf2fbca62007-11-12 06:35:08 +00001178/// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions
1179/// for addIntervalsForSpills to rewrite uses / defs for the given live range.
Evan Cheng018f9b02007-12-05 03:22:34 +00001180bool LiveIntervals::
Evan Chengd70dbb52008-02-22 09:24:50 +00001181rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI,
Jakob Stoklund Olesen1b293202010-08-12 20:01:23 +00001182 bool TrySplit, SlotIndex index, SlotIndex end,
Lang Hames86511252009-09-04 20:41:11 +00001183 MachineInstr *MI,
Evan Cheng81a03822007-11-17 00:40:40 +00001184 MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
Evan Chengf2fbca62007-11-12 06:35:08 +00001185 unsigned Slot, int LdSlot,
1186 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
Evan Chengd70dbb52008-02-22 09:24:50 +00001187 VirtRegMap &vrm,
Evan Chengf2fbca62007-11-12 06:35:08 +00001188 const TargetRegisterClass* rc,
1189 SmallVector<int, 4> &ReMatIds,
Evan Cheng22f07ff2007-12-11 02:09:15 +00001190 const MachineLoopInfo *loopInfo,
Evan Cheng313d4b82008-02-23 00:33:04 +00001191 unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse,
Owen Anderson28998312008-08-13 22:28:50 +00001192 DenseMap<unsigned,unsigned> &MBBVRegsMap,
Evan Chengc781a242009-05-03 18:32:42 +00001193 std::vector<LiveInterval*> &NewLIs) {
Evan Cheng018f9b02007-12-05 03:22:34 +00001194 bool CanFold = false;
Evan Chengf2fbca62007-11-12 06:35:08 +00001195 RestartInstruction:
1196 for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
1197 MachineOperand& mop = MI->getOperand(i);
Dan Gohmand735b802008-10-03 15:45:36 +00001198 if (!mop.isReg())
Evan Chengf2fbca62007-11-12 06:35:08 +00001199 continue;
1200 unsigned Reg = mop.getReg();
Jakob Stoklund Olesenc9df0252011-01-10 02:58:51 +00001201 if (!TargetRegisterInfo::isVirtualRegister(Reg))
Evan Chengf2fbca62007-11-12 06:35:08 +00001202 continue;
Evan Chengf2fbca62007-11-12 06:35:08 +00001203 if (Reg != li.reg)
1204 continue;
1205
1206 bool TryFold = !DefIsReMat;
Evan Chengcb3c3302007-11-29 23:02:50 +00001207 bool FoldSS = true; // Default behavior unless it's a remat.
Evan Chengf2fbca62007-11-12 06:35:08 +00001208 int FoldSlot = Slot;
1209 if (DefIsReMat) {
1210 // If this is the rematerializable definition MI itself and
1211 // all of its uses are rematerialized, simply delete it.
Evan Cheng81a03822007-11-17 00:40:40 +00001212 if (MI == ReMatOrigDefMI && CanDelete) {
Dale Johannesenbd635202010-02-10 00:55:42 +00001213 DEBUG(dbgs() << "\t\t\t\tErasing re-materializable def: "
Evan Cheng28a1e482010-03-30 05:49:07 +00001214 << *MI << '\n');
Evan Chengf2fbca62007-11-12 06:35:08 +00001215 RemoveMachineInstrFromMaps(MI);
Evan Chengcada2452007-11-28 01:28:46 +00001216 vrm.RemoveMachineInstrFromMaps(MI);
Evan Chengf2fbca62007-11-12 06:35:08 +00001217 MI->eraseFromParent();
1218 break;
1219 }
1220
1221 // If def for this use can't be rematerialized, then try folding.
Evan Cheng0cbb1162007-11-29 01:06:25 +00001222 // If def is rematerializable and it's a load, also try folding.
Evan Chengcb3c3302007-11-29 23:02:50 +00001223 TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad));
Evan Chengf2fbca62007-11-12 06:35:08 +00001224 if (isLoad) {
1225 // Try fold loads (from stack slot, constant pool, etc.) into uses.
1226 FoldSS = isLoadSS;
1227 FoldSlot = LdSlot;
1228 }
1229 }
1230
Evan Chengf2fbca62007-11-12 06:35:08 +00001231 // Scan all of the operands of this instruction rewriting operands
1232 // to use NewVReg instead of li.reg as appropriate. We do this for
1233 // two reasons:
1234 //
1235 // 1. If the instr reads the same spilled vreg multiple times, we
1236 // want to reuse the NewVReg.
1237 // 2. If the instr is a two-addr instruction, we are required to
1238 // keep the src/dst regs pinned.
1239 //
1240 // Keep track of whether we replace a use and/or def so that we can
Jakob Stoklund Olesen1b293202010-08-12 20:01:23 +00001241 // create the spill interval with the appropriate range.
Evan Chengaee4af62007-12-02 08:30:39 +00001242 SmallVector<unsigned, 2> Ops;
Jakob Stoklund Olesenead06be2010-06-03 00:07:47 +00001243 tie(HasUse, HasDef) = MI->readsWritesVirtualRegister(Reg, &Ops);
Evan Chengf2fbca62007-11-12 06:35:08 +00001244
David Greene26b86a02008-10-27 17:38:59 +00001245 // Create a new virtual register for the spill interval.
1246 // Create the new register now so we can map the fold instruction
1247 // to the new register so when it is unfolded we get the correct
1248 // answer.
1249 bool CreatedNewVReg = false;
1250 if (NewVReg == 0) {
1251 NewVReg = mri_->createVirtualRegister(rc);
1252 vrm.grow();
1253 CreatedNewVReg = true;
Jakob Stoklund Olesence7a6632009-11-30 22:55:54 +00001254
1255 // The new virtual register should get the same allocation hints as the
1256 // old one.
1257 std::pair<unsigned, unsigned> Hint = mri_->getRegAllocationHint(Reg);
1258 if (Hint.first || Hint.second)
1259 mri_->setRegAllocationHint(NewVReg, Hint.first, Hint.second);
David Greene26b86a02008-10-27 17:38:59 +00001260 }
1261
Evan Cheng9c3c2212008-06-06 07:54:39 +00001262 if (!TryFold)
1263 CanFold = false;
1264 else {
Evan Cheng018f9b02007-12-05 03:22:34 +00001265 // Do not fold load / store here if we are splitting. We'll find an
1266 // optimal point to insert a load / store later.
1267 if (!TrySplit) {
1268 if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
David Greene26b86a02008-10-27 17:38:59 +00001269 Ops, FoldSS, FoldSlot, NewVReg)) {
Evan Cheng018f9b02007-12-05 03:22:34 +00001270 // Folding the load/store can completely change the instruction in
1271 // unpredictable ways, rescan it from the beginning.
David Greene26b86a02008-10-27 17:38:59 +00001272
1273 if (FoldSS) {
1274 // We need to give the new vreg the same stack slot as the
1275 // spilled interval.
1276 vrm.assignVirt2StackSlot(NewVReg, FoldSlot);
1277 }
1278
Evan Cheng018f9b02007-12-05 03:22:34 +00001279 HasUse = false;
1280 HasDef = false;
1281 CanFold = false;
Evan Chengc781a242009-05-03 18:32:42 +00001282 if (isNotInMIMap(MI))
Evan Cheng7e073ba2008-04-09 20:57:25 +00001283 break;
Evan Cheng018f9b02007-12-05 03:22:34 +00001284 goto RestartInstruction;
1285 }
1286 } else {
Evan Cheng9c3c2212008-06-06 07:54:39 +00001287 // We'll try to fold it later if it's profitable.
Evan Cheng3c75ba82008-04-01 21:37:32 +00001288 CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat);
Evan Cheng018f9b02007-12-05 03:22:34 +00001289 }
Evan Cheng9c3c2212008-06-06 07:54:39 +00001290 }
Evan Chengcddbb832007-11-30 21:23:43 +00001291
Evan Chengcddbb832007-11-30 21:23:43 +00001292 mop.setReg(NewVReg);
Evan Chengd70dbb52008-02-22 09:24:50 +00001293 if (mop.isImplicit())
1294 rewriteImplicitOps(li, MI, NewVReg, vrm);
Evan Chengcddbb832007-11-30 21:23:43 +00001295
1296 // Reuse NewVReg for other reads.
Jakob Stoklund Olesen7c2e4a82010-11-16 00:40:59 +00001297 bool HasEarlyClobber = false;
Evan Chengd70dbb52008-02-22 09:24:50 +00001298 for (unsigned j = 0, e = Ops.size(); j != e; ++j) {
1299 MachineOperand &mopj = MI->getOperand(Ops[j]);
1300 mopj.setReg(NewVReg);
1301 if (mopj.isImplicit())
1302 rewriteImplicitOps(li, MI, NewVReg, vrm);
Jakob Stoklund Olesen7c2e4a82010-11-16 00:40:59 +00001303 if (mopj.isEarlyClobber())
1304 HasEarlyClobber = true;
Evan Chengd70dbb52008-02-22 09:24:50 +00001305 }
Jakob Stoklund Olesen1b293202010-08-12 20:01:23 +00001306
Evan Cheng81a03822007-11-17 00:40:40 +00001307 if (CreatedNewVReg) {
1308 if (DefIsReMat) {
Evan Cheng37844532009-07-16 09:20:10 +00001309 vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI);
Evan Chengd70dbb52008-02-22 09:24:50 +00001310 if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) {
Evan Cheng81a03822007-11-17 00:40:40 +00001311 // Each valnum may have its own remat id.
Evan Chengd70dbb52008-02-22 09:24:50 +00001312 ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg);
Evan Cheng81a03822007-11-17 00:40:40 +00001313 } else {
Evan Chengd70dbb52008-02-22 09:24:50 +00001314 vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]);
Evan Cheng81a03822007-11-17 00:40:40 +00001315 }
1316 if (!CanDelete || (HasUse && HasDef)) {
1317 // If this is a two-addr instruction then its use operands are
1318 // rematerializable but its def is not. It should be assigned a
1319 // stack slot.
1320 vrm.assignVirt2StackSlot(NewVReg, Slot);
1321 }
Evan Chengf2fbca62007-11-12 06:35:08 +00001322 } else {
Evan Chengf2fbca62007-11-12 06:35:08 +00001323 vrm.assignVirt2StackSlot(NewVReg, Slot);
1324 }
Evan Chengcb3c3302007-11-29 23:02:50 +00001325 } else if (HasUse && HasDef &&
1326 vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) {
1327 // If this interval hasn't been assigned a stack slot (because earlier
1328 // def is a deleted remat def), do it now.
1329 assert(Slot != VirtRegMap::NO_STACK_SLOT);
1330 vrm.assignVirt2StackSlot(NewVReg, Slot);
Evan Chengf2fbca62007-11-12 06:35:08 +00001331 }
1332
Evan Cheng313d4b82008-02-23 00:33:04 +00001333 // Re-matting an instruction with virtual register use. Add the
1334 // register as an implicit use on the use MI.
1335 if (DefIsReMat && ImpUse)
1336 MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
1337
Evan Cheng5b69eba2009-04-21 22:46:52 +00001338 // Create a new register interval for this spill / remat.
Evan Chengf2fbca62007-11-12 06:35:08 +00001339 LiveInterval &nI = getOrCreateInterval(NewVReg);
Evan Cheng81a03822007-11-17 00:40:40 +00001340 if (CreatedNewVReg) {
1341 NewLIs.push_back(&nI);
Evan Cheng1953d0c2007-11-29 10:12:14 +00001342 MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg));
Evan Cheng81a03822007-11-17 00:40:40 +00001343 if (TrySplit)
1344 vrm.setIsSplitFromReg(NewVReg, li.reg);
1345 }
Evan Chengf2fbca62007-11-12 06:35:08 +00001346
1347 if (HasUse) {
Evan Cheng81a03822007-11-17 00:40:40 +00001348 if (CreatedNewVReg) {
Lang Hames233a60e2009-11-03 23:52:08 +00001349 LiveRange LR(index.getLoadIndex(), index.getDefIndex(),
Lang Hames6e2968c2010-09-25 12:04:16 +00001350 nI.getNextValue(SlotIndex(), 0, VNInfoAllocator));
David Greene8a342292010-01-04 22:49:02 +00001351 DEBUG(dbgs() << " +" << LR);
Evan Cheng81a03822007-11-17 00:40:40 +00001352 nI.addRange(LR);
1353 } else {
1354 // Extend the split live interval to this def / use.
Lang Hames233a60e2009-11-03 23:52:08 +00001355 SlotIndex End = index.getDefIndex();
Evan Cheng81a03822007-11-17 00:40:40 +00001356 LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End,
1357 nI.getValNumInfo(nI.getNumValNums()-1));
David Greene8a342292010-01-04 22:49:02 +00001358 DEBUG(dbgs() << " +" << LR);
Evan Cheng81a03822007-11-17 00:40:40 +00001359 nI.addRange(LR);
1360 }
Evan Chengf2fbca62007-11-12 06:35:08 +00001361 }
1362 if (HasDef) {
Jakob Stoklund Olesen7c2e4a82010-11-16 00:40:59 +00001363 // An early clobber starts at the use slot, except for an early clobber
1364 // tied to a use operand (yes, that is a thing).
1365 LiveRange LR(HasEarlyClobber && !HasUse ?
1366 index.getUseIndex() : index.getDefIndex(),
1367 index.getStoreIndex(),
Lang Hames6e2968c2010-09-25 12:04:16 +00001368 nI.getNextValue(SlotIndex(), 0, VNInfoAllocator));
David Greene8a342292010-01-04 22:49:02 +00001369 DEBUG(dbgs() << " +" << LR);
Evan Chengf2fbca62007-11-12 06:35:08 +00001370 nI.addRange(LR);
1371 }
Evan Cheng81a03822007-11-17 00:40:40 +00001372
Bill Wendling8e6179f2009-08-22 20:18:03 +00001373 DEBUG({
David Greene8a342292010-01-04 22:49:02 +00001374 dbgs() << "\t\t\t\tAdded new interval: ";
1375 nI.print(dbgs(), tri_);
1376 dbgs() << '\n';
Bill Wendling8e6179f2009-08-22 20:18:03 +00001377 });
Evan Chengf2fbca62007-11-12 06:35:08 +00001378 }
Evan Cheng018f9b02007-12-05 03:22:34 +00001379 return CanFold;
Evan Chengf2fbca62007-11-12 06:35:08 +00001380}
Evan Cheng81a03822007-11-17 00:40:40 +00001381bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li,
Evan Cheng0cbb1162007-11-29 01:06:25 +00001382 const VNInfo *VNI,
Lang Hames86511252009-09-04 20:41:11 +00001383 MachineBasicBlock *MBB,
Lang Hames233a60e2009-11-03 23:52:08 +00001384 SlotIndex Idx) const {
Jakob Stoklund Olesen15a57142010-06-25 22:53:05 +00001385 return li.killedInRange(Idx.getNextSlot(), getMBBEndIdx(MBB));
Evan Cheng81a03822007-11-17 00:40:40 +00001386}
1387
Evan Cheng063284c2008-02-21 00:34:19 +00001388/// RewriteInfo - Keep track of machine instrs that will be rewritten
1389/// during spilling.
Dan Gohman844731a2008-05-13 00:00:25 +00001390namespace {
1391 struct RewriteInfo {
Lang Hames233a60e2009-11-03 23:52:08 +00001392 SlotIndex Index;
Dan Gohman844731a2008-05-13 00:00:25 +00001393 MachineInstr *MI;
Jakob Stoklund Olesenead06be2010-06-03 00:07:47 +00001394 RewriteInfo(SlotIndex i, MachineInstr *mi) : Index(i), MI(mi) {}
Dan Gohman844731a2008-05-13 00:00:25 +00001395 };
Evan Cheng063284c2008-02-21 00:34:19 +00001396
Dan Gohman844731a2008-05-13 00:00:25 +00001397 struct RewriteInfoCompare {
1398 bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const {
1399 return LHS.Index < RHS.Index;
1400 }
1401 };
1402}
Evan Cheng063284c2008-02-21 00:34:19 +00001403
Evan Chengf2fbca62007-11-12 06:35:08 +00001404void LiveIntervals::
Evan Cheng81a03822007-11-17 00:40:40 +00001405rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
Evan Chengf2fbca62007-11-12 06:35:08 +00001406 LiveInterval::Ranges::const_iterator &I,
Evan Cheng81a03822007-11-17 00:40:40 +00001407 MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
Evan Chengf2fbca62007-11-12 06:35:08 +00001408 unsigned Slot, int LdSlot,
1409 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
Evan Chengd70dbb52008-02-22 09:24:50 +00001410 VirtRegMap &vrm,
Evan Chengf2fbca62007-11-12 06:35:08 +00001411 const TargetRegisterClass* rc,
1412 SmallVector<int, 4> &ReMatIds,
Evan Cheng22f07ff2007-12-11 02:09:15 +00001413 const MachineLoopInfo *loopInfo,
Evan Cheng81a03822007-11-17 00:40:40 +00001414 BitVector &SpillMBBs,
Owen Anderson28998312008-08-13 22:28:50 +00001415 DenseMap<unsigned, std::vector<SRInfo> > &SpillIdxes,
Evan Cheng0cbb1162007-11-29 01:06:25 +00001416 BitVector &RestoreMBBs,
Owen Anderson28998312008-08-13 22:28:50 +00001417 DenseMap<unsigned, std::vector<SRInfo> > &RestoreIdxes,
1418 DenseMap<unsigned,unsigned> &MBBVRegsMap,
Evan Chengc781a242009-05-03 18:32:42 +00001419 std::vector<LiveInterval*> &NewLIs) {
Evan Cheng018f9b02007-12-05 03:22:34 +00001420 bool AllCanFold = true;
Evan Cheng81a03822007-11-17 00:40:40 +00001421 unsigned NewVReg = 0;
Lang Hames233a60e2009-11-03 23:52:08 +00001422 SlotIndex start = I->start.getBaseIndex();
1423 SlotIndex end = I->end.getPrevSlot().getBaseIndex().getNextIndex();
Evan Chengf2fbca62007-11-12 06:35:08 +00001424
Evan Cheng063284c2008-02-21 00:34:19 +00001425 // First collect all the def / use in this live range that will be rewritten.
Evan Cheng7e073ba2008-04-09 20:57:25 +00001426 // Make sure they are sorted according to instruction index.
Evan Cheng063284c2008-02-21 00:34:19 +00001427 std::vector<RewriteInfo> RewriteMIs;
Evan Chengd70dbb52008-02-22 09:24:50 +00001428 for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
1429 re = mri_->reg_end(); ri != re; ) {
Evan Cheng419852c2008-04-03 16:39:43 +00001430 MachineInstr *MI = &*ri;
Evan Cheng063284c2008-02-21 00:34:19 +00001431 MachineOperand &O = ri.getOperand();
1432 ++ri;
Dale Johannesenbd635202010-02-10 00:55:42 +00001433 if (MI->isDebugValue()) {
Evan Cheng962021b2010-04-26 07:38:55 +00001434 // Modify DBG_VALUE now that the value is in a spill slot.
Evan Cheng6691a892010-04-28 23:52:26 +00001435 if (Slot != VirtRegMap::MAX_STACK_SLOT || isLoadSS) {
Evan Cheng6fa76362010-04-26 18:37:21 +00001436 uint64_t Offset = MI->getOperand(1).getImm();
1437 const MDNode *MDPtr = MI->getOperand(2).getMetadata();
1438 DebugLoc DL = MI->getDebugLoc();
Evan Cheng6691a892010-04-28 23:52:26 +00001439 int FI = isLoadSS ? LdSlot : (int)Slot;
1440 if (MachineInstr *NewDV = tii_->emitFrameIndexDebugValue(*mf_, FI,
Evan Cheng6fa76362010-04-26 18:37:21 +00001441 Offset, MDPtr, DL)) {
1442 DEBUG(dbgs() << "Modifying debug info due to spill:" << "\t" << *MI);
1443 ReplaceMachineInstrInMaps(MI, NewDV);
1444 MachineBasicBlock *MBB = MI->getParent();
1445 MBB->insert(MBB->erase(MI), NewDV);
1446 continue;
1447 }
Evan Cheng962021b2010-04-26 07:38:55 +00001448 }
Evan Cheng6fa76362010-04-26 18:37:21 +00001449
1450 DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI);
1451 RemoveMachineInstrFromMaps(MI);
1452 vrm.RemoveMachineInstrFromMaps(MI);
1453 MI->eraseFromParent();
Dale Johannesenbd635202010-02-10 00:55:42 +00001454 continue;
1455 }
Jakob Stoklund Olesen63e6a482010-05-21 16:32:16 +00001456 assert(!(O.isImplicit() && O.isUse()) &&
1457 "Spilling register that's used as implicit use?");
Lang Hames233a60e2009-11-03 23:52:08 +00001458 SlotIndex index = getInstructionIndex(MI);
Evan Cheng063284c2008-02-21 00:34:19 +00001459 if (index < start || index >= end)
1460 continue;
Evan Chengd129d732009-07-17 19:43:40 +00001461
1462 if (O.isUndef())
Evan Cheng79a796c2008-07-12 01:56:02 +00001463 // Must be defined by an implicit def. It should not be spilled. Note,
1464 // this is for correctness reason. e.g.
1465 // 8 %reg1024<def> = IMPLICIT_DEF
1466 // 12 %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2
1467 // The live range [12, 14) are not part of the r1024 live interval since
1468 // it's defined by an implicit def. It will not conflicts with live
1469 // interval of r1025. Now suppose both registers are spilled, you can
Evan Chengb9890ae2008-07-12 02:22:07 +00001470 // easily see a situation where both registers are reloaded before
Evan Cheng79a796c2008-07-12 01:56:02 +00001471 // the INSERT_SUBREG and both target registers that would overlap.
1472 continue;
Jakob Stoklund Olesenead06be2010-06-03 00:07:47 +00001473 RewriteMIs.push_back(RewriteInfo(index, MI));
Evan Cheng063284c2008-02-21 00:34:19 +00001474 }
1475 std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare());
1476
Evan Cheng313d4b82008-02-23 00:33:04 +00001477 unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0;
Evan Cheng063284c2008-02-21 00:34:19 +00001478 // Now rewrite the defs and uses.
1479 for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) {
1480 RewriteInfo &rwi = RewriteMIs[i];
1481 ++i;
Lang Hames233a60e2009-11-03 23:52:08 +00001482 SlotIndex index = rwi.Index;
Evan Cheng063284c2008-02-21 00:34:19 +00001483 MachineInstr *MI = rwi.MI;
1484 // If MI def and/or use the same register multiple times, then there
1485 // are multiple entries.
1486 while (i != e && RewriteMIs[i].MI == MI) {
1487 assert(RewriteMIs[i].Index == index);
Evan Cheng063284c2008-02-21 00:34:19 +00001488 ++i;
1489 }
Evan Cheng81a03822007-11-17 00:40:40 +00001490 MachineBasicBlock *MBB = MI->getParent();
Evan Cheng313d4b82008-02-23 00:33:04 +00001491
Evan Cheng0a891ed2008-05-23 23:00:04 +00001492 if (ImpUse && MI != ReMatDefMI) {
Jakob Stoklund Olesene5d90412010-03-01 20:59:38 +00001493 // Re-matting an instruction with virtual register use. Prevent interval
1494 // from being spilled.
1495 getInterval(ImpUse).markNotSpillable();
Evan Cheng313d4b82008-02-23 00:33:04 +00001496 }
1497
Evan Cheng063284c2008-02-21 00:34:19 +00001498 unsigned MBBId = MBB->getNumber();
Evan Cheng018f9b02007-12-05 03:22:34 +00001499 unsigned ThisVReg = 0;
Evan Cheng70306f82007-12-03 09:58:48 +00001500 if (TrySplit) {
Owen Anderson28998312008-08-13 22:28:50 +00001501 DenseMap<unsigned,unsigned>::iterator NVI = MBBVRegsMap.find(MBBId);
Evan Cheng1953d0c2007-11-29 10:12:14 +00001502 if (NVI != MBBVRegsMap.end()) {
Evan Cheng018f9b02007-12-05 03:22:34 +00001503 ThisVReg = NVI->second;
Evan Cheng1953d0c2007-11-29 10:12:14 +00001504 // One common case:
1505 // x = use
1506 // ...
1507 // ...
1508 // def = ...
1509 // = use
Chris Lattner7a2bdde2011-04-15 05:18:47 +00001510 // It's better to start a new interval to avoid artificially
Evan Cheng1953d0c2007-11-29 10:12:14 +00001511 // extend the new interval.
Jakob Stoklund Olesenead06be2010-06-03 00:07:47 +00001512 if (MI->readsWritesVirtualRegister(li.reg) ==
1513 std::make_pair(false,true)) {
Evan Cheng1953d0c2007-11-29 10:12:14 +00001514 MBBVRegsMap.erase(MBB->getNumber());
Evan Cheng018f9b02007-12-05 03:22:34 +00001515 ThisVReg = 0;
Evan Cheng1953d0c2007-11-29 10:12:14 +00001516 }
1517 }
Evan Chengcada2452007-11-28 01:28:46 +00001518 }
Evan Cheng018f9b02007-12-05 03:22:34 +00001519
1520 bool IsNew = ThisVReg == 0;
1521 if (IsNew) {
1522 // This ends the previous live interval. If all of its def / use
1523 // can be folded, give it a low spill weight.
1524 if (NewVReg && TrySplit && AllCanFold) {
1525 LiveInterval &nI = getOrCreateInterval(NewVReg);
1526 nI.weight /= 10.0F;
1527 }
1528 AllCanFold = true;
1529 }
1530 NewVReg = ThisVReg;
1531
Evan Cheng81a03822007-11-17 00:40:40 +00001532 bool HasDef = false;
1533 bool HasUse = false;
Evan Chengd70dbb52008-02-22 09:24:50 +00001534 bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit,
Evan Cheng9c3c2212008-06-06 07:54:39 +00001535 index, end, MI, ReMatOrigDefMI, ReMatDefMI,
1536 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
1537 CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg,
Evan Chengc781a242009-05-03 18:32:42 +00001538 ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs);
Evan Cheng81a03822007-11-17 00:40:40 +00001539 if (!HasDef && !HasUse)
1540 continue;
1541
Evan Cheng018f9b02007-12-05 03:22:34 +00001542 AllCanFold &= CanFold;
1543
Evan Cheng81a03822007-11-17 00:40:40 +00001544 // Update weight of spill interval.
1545 LiveInterval &nI = getOrCreateInterval(NewVReg);
Evan Cheng70306f82007-12-03 09:58:48 +00001546 if (!TrySplit) {
Evan Cheng81a03822007-11-17 00:40:40 +00001547 // The spill weight is now infinity as it cannot be spilled again.
Jakob Stoklund Olesene5d90412010-03-01 20:59:38 +00001548 nI.markNotSpillable();
Evan Cheng0cbb1162007-11-29 01:06:25 +00001549 continue;
Evan Cheng81a03822007-11-17 00:40:40 +00001550 }
Evan Cheng0cbb1162007-11-29 01:06:25 +00001551
1552 // Keep track of the last def and first use in each MBB.
Evan Cheng0cbb1162007-11-29 01:06:25 +00001553 if (HasDef) {
1554 if (MI != ReMatOrigDefMI || !CanDelete) {
Evan Cheng0cbb1162007-11-29 01:06:25 +00001555 bool HasKill = false;
1556 if (!HasUse)
Lang Hames233a60e2009-11-03 23:52:08 +00001557 HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, index.getDefIndex());
Evan Cheng0cbb1162007-11-29 01:06:25 +00001558 else {
Evan Cheng1953d0c2007-11-29 10:12:14 +00001559 // If this is a two-address code, then this index starts a new VNInfo.
Lang Hames233a60e2009-11-03 23:52:08 +00001560 const VNInfo *VNI = li.findDefinedVNInfoForRegInt(index.getDefIndex());
Evan Cheng0cbb1162007-11-29 01:06:25 +00001561 if (VNI)
Lang Hames233a60e2009-11-03 23:52:08 +00001562 HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, index.getDefIndex());
Evan Cheng0cbb1162007-11-29 01:06:25 +00001563 }
Owen Anderson28998312008-08-13 22:28:50 +00001564 DenseMap<unsigned, std::vector<SRInfo> >::iterator SII =
Evan Chenge3110d02007-12-01 04:42:39 +00001565 SpillIdxes.find(MBBId);
Evan Cheng0cbb1162007-11-29 01:06:25 +00001566 if (!HasKill) {
Evan Cheng1953d0c2007-11-29 10:12:14 +00001567 if (SII == SpillIdxes.end()) {
1568 std::vector<SRInfo> S;
1569 S.push_back(SRInfo(index, NewVReg, true));
1570 SpillIdxes.insert(std::make_pair(MBBId, S));
1571 } else if (SII->second.back().vreg != NewVReg) {
1572 SII->second.push_back(SRInfo(index, NewVReg, true));
Lang Hames86511252009-09-04 20:41:11 +00001573 } else if (index > SII->second.back().index) {
Evan Cheng0cbb1162007-11-29 01:06:25 +00001574 // If there is an earlier def and this is a two-address
1575 // instruction, then it's not possible to fold the store (which
1576 // would also fold the load).
Evan Cheng1953d0c2007-11-29 10:12:14 +00001577 SRInfo &Info = SII->second.back();
1578 Info.index = index;
1579 Info.canFold = !HasUse;
Evan Cheng0cbb1162007-11-29 01:06:25 +00001580 }
1581 SpillMBBs.set(MBBId);
Evan Chenge3110d02007-12-01 04:42:39 +00001582 } else if (SII != SpillIdxes.end() &&
1583 SII->second.back().vreg == NewVReg &&
Lang Hames86511252009-09-04 20:41:11 +00001584 index > SII->second.back().index) {
Evan Chenge3110d02007-12-01 04:42:39 +00001585 // There is an earlier def that's not killed (must be two-address).
1586 // The spill is no longer needed.
1587 SII->second.pop_back();
1588 if (SII->second.empty()) {
1589 SpillIdxes.erase(MBBId);
1590 SpillMBBs.reset(MBBId);
1591 }
Evan Cheng0cbb1162007-11-29 01:06:25 +00001592 }
1593 }
Evan Cheng0cbb1162007-11-29 01:06:25 +00001594 }
1595
1596 if (HasUse) {
Owen Anderson28998312008-08-13 22:28:50 +00001597 DenseMap<unsigned, std::vector<SRInfo> >::iterator SII =
Evan Cheng0cbb1162007-11-29 01:06:25 +00001598 SpillIdxes.find(MBBId);
Evan Cheng1953d0c2007-11-29 10:12:14 +00001599 if (SII != SpillIdxes.end() &&
1600 SII->second.back().vreg == NewVReg &&
Lang Hames86511252009-09-04 20:41:11 +00001601 index > SII->second.back().index)
Evan Cheng0cbb1162007-11-29 01:06:25 +00001602 // Use(s) following the last def, it's not safe to fold the spill.
Evan Cheng1953d0c2007-11-29 10:12:14 +00001603 SII->second.back().canFold = false;
Owen Anderson28998312008-08-13 22:28:50 +00001604 DenseMap<unsigned, std::vector<SRInfo> >::iterator RII =
Evan Cheng0cbb1162007-11-29 01:06:25 +00001605 RestoreIdxes.find(MBBId);
Evan Cheng1953d0c2007-11-29 10:12:14 +00001606 if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg)
Evan Cheng0cbb1162007-11-29 01:06:25 +00001607 // If we are splitting live intervals, only fold if it's the first
1608 // use and there isn't another use later in the MBB.
Evan Cheng1953d0c2007-11-29 10:12:14 +00001609 RII->second.back().canFold = false;
Evan Cheng0cbb1162007-11-29 01:06:25 +00001610 else if (IsNew) {
1611 // Only need a reload if there isn't an earlier def / use.
Evan Cheng1953d0c2007-11-29 10:12:14 +00001612 if (RII == RestoreIdxes.end()) {
1613 std::vector<SRInfo> Infos;
1614 Infos.push_back(SRInfo(index, NewVReg, true));
1615 RestoreIdxes.insert(std::make_pair(MBBId, Infos));
1616 } else {
1617 RII->second.push_back(SRInfo(index, NewVReg, true));
1618 }
Evan Cheng0cbb1162007-11-29 01:06:25 +00001619 RestoreMBBs.set(MBBId);
1620 }
1621 }
1622
1623 // Update spill weight.
Evan Cheng22f07ff2007-12-11 02:09:15 +00001624 unsigned loopDepth = loopInfo->getLoopDepth(MBB);
Evan Chengc3417602008-06-21 06:45:54 +00001625 nI.weight += getSpillWeight(HasDef, HasUse, loopDepth);
Evan Chengf2fbca62007-11-12 06:35:08 +00001626 }
Evan Cheng018f9b02007-12-05 03:22:34 +00001627
1628 if (NewVReg && TrySplit && AllCanFold) {
1629 // If all of its def / use can be folded, give it a low spill weight.
1630 LiveInterval &nI = getOrCreateInterval(NewVReg);
1631 nI.weight /= 10.0F;
1632 }
Evan Chengf2fbca62007-11-12 06:35:08 +00001633}
1634
Lang Hames233a60e2009-11-03 23:52:08 +00001635bool LiveIntervals::alsoFoldARestore(int Id, SlotIndex index,
Lang Hames86511252009-09-04 20:41:11 +00001636 unsigned vr, BitVector &RestoreMBBs,
Owen Anderson28998312008-08-13 22:28:50 +00001637 DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
Evan Cheng1953d0c2007-11-29 10:12:14 +00001638 if (!RestoreMBBs[Id])
1639 return false;
1640 std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1641 for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1642 if (Restores[i].index == index &&
1643 Restores[i].vreg == vr &&
1644 Restores[i].canFold)
1645 return true;
1646 return false;
1647}
1648
Lang Hames233a60e2009-11-03 23:52:08 +00001649void LiveIntervals::eraseRestoreInfo(int Id, SlotIndex index,
Lang Hames86511252009-09-04 20:41:11 +00001650 unsigned vr, BitVector &RestoreMBBs,
Owen Anderson28998312008-08-13 22:28:50 +00001651 DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
Evan Cheng1953d0c2007-11-29 10:12:14 +00001652 if (!RestoreMBBs[Id])
1653 return;
1654 std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1655 for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1656 if (Restores[i].index == index && Restores[i].vreg)
Lang Hames233a60e2009-11-03 23:52:08 +00001657 Restores[i].index = SlotIndex();
Evan Cheng1953d0c2007-11-29 10:12:14 +00001658}
Evan Cheng81a03822007-11-17 00:40:40 +00001659
Evan Cheng4cce6b42008-04-11 17:53:36 +00001660/// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being
1661/// spilled and create empty intervals for their uses.
1662void
1663LiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm,
1664 const TargetRegisterClass* rc,
1665 std::vector<LiveInterval*> &NewLIs) {
Evan Cheng419852c2008-04-03 16:39:43 +00001666 for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg),
1667 re = mri_->reg_end(); ri != re; ) {
Evan Cheng4cce6b42008-04-11 17:53:36 +00001668 MachineOperand &O = ri.getOperand();
Evan Cheng419852c2008-04-03 16:39:43 +00001669 MachineInstr *MI = &*ri;
1670 ++ri;
Evan Cheng28a1e482010-03-30 05:49:07 +00001671 if (MI->isDebugValue()) {
1672 // Remove debug info for now.
1673 O.setReg(0U);
1674 DEBUG(dbgs() << "Removing debug info due to spill:" << "\t" << *MI);
1675 continue;
1676 }
Evan Cheng4cce6b42008-04-11 17:53:36 +00001677 if (O.isDef()) {
Chris Lattner518bb532010-02-09 19:54:29 +00001678 assert(MI->isImplicitDef() &&
Evan Cheng4cce6b42008-04-11 17:53:36 +00001679 "Register def was not rewritten?");
1680 RemoveMachineInstrFromMaps(MI);
1681 vrm.RemoveMachineInstrFromMaps(MI);
1682 MI->eraseFromParent();
1683 } else {
1684 // This must be an use of an implicit_def so it's not part of the live
1685 // interval. Create a new empty live interval for it.
1686 // FIXME: Can we simply erase some of the instructions? e.g. Stores?
1687 unsigned NewVReg = mri_->createVirtualRegister(rc);
1688 vrm.grow();
1689 vrm.setIsImplicitlyDefined(NewVReg);
1690 NewLIs.push_back(&getOrCreateInterval(NewVReg));
1691 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
1692 MachineOperand &MO = MI->getOperand(i);
Evan Cheng4784f1f2009-06-30 08:49:04 +00001693 if (MO.isReg() && MO.getReg() == li.reg) {
Evan Cheng4cce6b42008-04-11 17:53:36 +00001694 MO.setReg(NewVReg);
Evan Cheng4784f1f2009-06-30 08:49:04 +00001695 MO.setIsUndef();
Evan Cheng4784f1f2009-06-30 08:49:04 +00001696 }
Evan Cheng4cce6b42008-04-11 17:53:36 +00001697 }
1698 }
Evan Cheng419852c2008-04-03 16:39:43 +00001699 }
1700}
1701
Jakob Stoklund Olesene5d90412010-03-01 20:59:38 +00001702float
1703LiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) {
1704 // Limit the loop depth ridiculousness.
1705 if (loopDepth > 200)
1706 loopDepth = 200;
1707
1708 // The loop depth is used to roughly estimate the number of times the
1709 // instruction is executed. Something like 10^d is simple, but will quickly
1710 // overflow a float. This expression behaves like 10^d for small d, but is
1711 // more tempered for large d. At d=200 we get 6.7e33 which leaves a bit of
1712 // headroom before overflow.
NAKAMURA Takumidc5198b2011-03-31 12:11:33 +00001713 // By the way, powf() might be unavailable here. For consistency,
1714 // We may take pow(double,double).
1715 float lc = std::pow(1 + (100.0 / (loopDepth + 10)), (double)loopDepth);
Jakob Stoklund Olesene5d90412010-03-01 20:59:38 +00001716
1717 return (isDef + isUse) * lc;
1718}
1719
Jakob Stoklund Oleseneb9f0402011-02-14 23:15:38 +00001720static void normalizeSpillWeights(std::vector<LiveInterval*> &NewLIs) {
Jakob Stoklund Olesen352d3522010-02-18 21:33:05 +00001721 for (unsigned i = 0, e = NewLIs.size(); i != e; ++i)
Jakob Stoklund Oleseneb9f0402011-02-14 23:15:38 +00001722 NewLIs[i]->weight =
1723 normalizeSpillWeight(NewLIs[i]->weight, NewLIs[i]->getSize());
Jakob Stoklund Olesen352d3522010-02-18 21:33:05 +00001724}
1725
Evan Chengf2fbca62007-11-12 06:35:08 +00001726std::vector<LiveInterval*> LiveIntervals::
Evan Cheng81a03822007-11-17 00:40:40 +00001727addIntervalsForSpills(const LiveInterval &li,
Jakob Stoklund Olesen38f6bd02011-03-10 01:21:58 +00001728 const SmallVectorImpl<LiveInterval*> *SpillIs,
Evan Chengc781a242009-05-03 18:32:42 +00001729 const MachineLoopInfo *loopInfo, VirtRegMap &vrm) {
Jakob Stoklund Olesene5d90412010-03-01 20:59:38 +00001730 assert(li.isSpillable() && "attempt to spill already spilled interval!");
Evan Chengf2fbca62007-11-12 06:35:08 +00001731
Bill Wendling8e6179f2009-08-22 20:18:03 +00001732 DEBUG({
David Greene8a342292010-01-04 22:49:02 +00001733 dbgs() << "\t\t\t\tadding intervals for spills for interval: ";
1734 li.print(dbgs(), tri_);
1735 dbgs() << '\n';
Bill Wendling8e6179f2009-08-22 20:18:03 +00001736 });
Evan Chengf2fbca62007-11-12 06:35:08 +00001737
Evan Cheng72eeb942008-12-05 17:00:16 +00001738 // Each bit specify whether a spill is required in the MBB.
Evan Cheng81a03822007-11-17 00:40:40 +00001739 BitVector SpillMBBs(mf_->getNumBlockIDs());
Owen Anderson28998312008-08-13 22:28:50 +00001740 DenseMap<unsigned, std::vector<SRInfo> > SpillIdxes;
Evan Cheng0cbb1162007-11-29 01:06:25 +00001741 BitVector RestoreMBBs(mf_->getNumBlockIDs());
Owen Anderson28998312008-08-13 22:28:50 +00001742 DenseMap<unsigned, std::vector<SRInfo> > RestoreIdxes;
1743 DenseMap<unsigned,unsigned> MBBVRegsMap;
Evan Chengf2fbca62007-11-12 06:35:08 +00001744 std::vector<LiveInterval*> NewLIs;
Evan Chengd70dbb52008-02-22 09:24:50 +00001745 const TargetRegisterClass* rc = mri_->getRegClass(li.reg);
Evan Chengf2fbca62007-11-12 06:35:08 +00001746
1747 unsigned NumValNums = li.getNumValNums();
1748 SmallVector<MachineInstr*, 4> ReMatDefs;
1749 ReMatDefs.resize(NumValNums, NULL);
1750 SmallVector<MachineInstr*, 4> ReMatOrigDefs;
1751 ReMatOrigDefs.resize(NumValNums, NULL);
1752 SmallVector<int, 4> ReMatIds;
1753 ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT);
1754 BitVector ReMatDelete(NumValNums);
1755 unsigned Slot = VirtRegMap::MAX_STACK_SLOT;
1756
Evan Cheng81a03822007-11-17 00:40:40 +00001757 // Spilling a split live interval. It cannot be split any further. Also,
1758 // it's also guaranteed to be a single val# / range interval.
1759 if (vrm.getPreSplitReg(li.reg)) {
1760 vrm.setIsSplitFromReg(li.reg, 0);
Evan Chengd120ffd2007-12-05 10:24:35 +00001761 // Unset the split kill marker on the last use.
Lang Hames233a60e2009-11-03 23:52:08 +00001762 SlotIndex KillIdx = vrm.getKillPoint(li.reg);
1763 if (KillIdx != SlotIndex()) {
Evan Chengd120ffd2007-12-05 10:24:35 +00001764 MachineInstr *KillMI = getInstructionFromIndex(KillIdx);
1765 assert(KillMI && "Last use disappeared?");
1766 int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true);
1767 assert(KillOp != -1 && "Last use disappeared?");
Chris Lattnerf7382302007-12-30 21:56:09 +00001768 KillMI->getOperand(KillOp).setIsKill(false);
Evan Chengd120ffd2007-12-05 10:24:35 +00001769 }
Evan Chengadf85902007-12-05 09:51:10 +00001770 vrm.removeKillPoint(li.reg);
Evan Cheng81a03822007-11-17 00:40:40 +00001771 bool DefIsReMat = vrm.isReMaterialized(li.reg);
1772 Slot = vrm.getStackSlot(li.reg);
1773 assert(Slot != VirtRegMap::MAX_STACK_SLOT);
1774 MachineInstr *ReMatDefMI = DefIsReMat ?
1775 vrm.getReMaterializedMI(li.reg) : NULL;
1776 int LdSlot = 0;
1777 bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1778 bool isLoad = isLoadSS ||
Dan Gohman15511cf2008-12-03 18:15:48 +00001779 (DefIsReMat && (ReMatDefMI->getDesc().canFoldAsLoad()));
Evan Cheng81a03822007-11-17 00:40:40 +00001780 bool IsFirstRange = true;
1781 for (LiveInterval::Ranges::const_iterator
1782 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
1783 // If this is a split live interval with multiple ranges, it means there
1784 // are two-address instructions that re-defined the value. Only the
1785 // first def can be rematerialized!
1786 if (IsFirstRange) {
Evan Chengcb3c3302007-11-29 23:02:50 +00001787 // Note ReMatOrigDefMI has already been deleted.
Evan Cheng81a03822007-11-17 00:40:40 +00001788 rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI,
1789 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
Evan Chengd70dbb52008-02-22 09:24:50 +00001790 false, vrm, rc, ReMatIds, loopInfo,
Evan Cheng0cbb1162007-11-29 01:06:25 +00001791 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
Evan Chengc781a242009-05-03 18:32:42 +00001792 MBBVRegsMap, NewLIs);
Evan Cheng81a03822007-11-17 00:40:40 +00001793 } else {
1794 rewriteInstructionsForSpills(li, false, I, NULL, 0,
1795 Slot, 0, false, false, false,
Evan Chengd70dbb52008-02-22 09:24:50 +00001796 false, vrm, rc, ReMatIds, loopInfo,
Evan Cheng0cbb1162007-11-29 01:06:25 +00001797 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
Evan Chengc781a242009-05-03 18:32:42 +00001798 MBBVRegsMap, NewLIs);
Evan Cheng81a03822007-11-17 00:40:40 +00001799 }
1800 IsFirstRange = false;
1801 }
Evan Cheng419852c2008-04-03 16:39:43 +00001802
Evan Cheng4cce6b42008-04-11 17:53:36 +00001803 handleSpilledImpDefs(li, vrm, rc, NewLIs);
Jakob Stoklund Olesen352d3522010-02-18 21:33:05 +00001804 normalizeSpillWeights(NewLIs);
Evan Cheng81a03822007-11-17 00:40:40 +00001805 return NewLIs;
1806 }
1807
Evan Cheng752195e2009-09-14 21:33:42 +00001808 bool TrySplit = !intervalIsInOneMBB(li);
Evan Cheng0cbb1162007-11-29 01:06:25 +00001809 if (TrySplit)
1810 ++numSplits;
Evan Chengf2fbca62007-11-12 06:35:08 +00001811 bool NeedStackSlot = false;
1812 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
1813 i != e; ++i) {
1814 const VNInfo *VNI = *i;
1815 unsigned VN = VNI->id;
Lang Hames857c4e02009-06-17 21:01:20 +00001816 if (VNI->isUnused())
Evan Chengf2fbca62007-11-12 06:35:08 +00001817 continue; // Dead val#.
1818 // Is the def for the val# rematerializable?
Lang Hames6e2968c2010-09-25 12:04:16 +00001819 MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def);
Evan Cheng5ef3a042007-12-06 00:01:56 +00001820 bool dummy;
Evan Chengdc377862008-09-30 15:44:16 +00001821 if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, SpillIs, dummy)) {
Evan Chengf2fbca62007-11-12 06:35:08 +00001822 // Remember how to remat the def of this val#.
Evan Cheng81a03822007-11-17 00:40:40 +00001823 ReMatOrigDefs[VN] = ReMatDefMI;
Dan Gohman2c3f7ae2008-07-17 23:49:46 +00001824 // Original def may be modified so we have to make a copy here.
Evan Cheng1ed99222008-07-19 00:37:25 +00001825 MachineInstr *Clone = mf_->CloneMachineInstr(ReMatDefMI);
Evan Cheng752195e2009-09-14 21:33:42 +00001826 CloneMIs.push_back(Clone);
Evan Cheng1ed99222008-07-19 00:37:25 +00001827 ReMatDefs[VN] = Clone;
Evan Chengf2fbca62007-11-12 06:35:08 +00001828
1829 bool CanDelete = true;
Lang Hames857c4e02009-06-17 21:01:20 +00001830 if (VNI->hasPHIKill()) {
Evan Chengc3fc7d92007-11-29 09:49:23 +00001831 // A kill is a phi node, not all of its uses can be rematerialized.
Evan Chengf2fbca62007-11-12 06:35:08 +00001832 // It must not be deleted.
Evan Chengc3fc7d92007-11-29 09:49:23 +00001833 CanDelete = false;
1834 // Need a stack slot if there is any live range where uses cannot be
1835 // rematerialized.
1836 NeedStackSlot = true;
Evan Chengf2fbca62007-11-12 06:35:08 +00001837 }
Evan Chengf2fbca62007-11-12 06:35:08 +00001838 if (CanDelete)
1839 ReMatDelete.set(VN);
1840 } else {
1841 // Need a stack slot if there is any live range where uses cannot be
1842 // rematerialized.
1843 NeedStackSlot = true;
1844 }
1845 }
1846
1847 // One stack slot per live interval.
Owen Andersonb98bbb72009-03-26 18:53:38 +00001848 if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) {
1849 if (vrm.getStackSlot(li.reg) == VirtRegMap::NO_STACK_SLOT)
1850 Slot = vrm.assignVirt2StackSlot(li.reg);
Jakob Stoklund Olesen1b293202010-08-12 20:01:23 +00001851
Owen Andersonb98bbb72009-03-26 18:53:38 +00001852 // This case only occurs when the prealloc splitter has already assigned
1853 // a stack slot to this vreg.
1854 else
1855 Slot = vrm.getStackSlot(li.reg);
1856 }
Evan Chengf2fbca62007-11-12 06:35:08 +00001857
1858 // Create new intervals and rewrite defs and uses.
1859 for (LiveInterval::Ranges::const_iterator
1860 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
Evan Cheng81a03822007-11-17 00:40:40 +00001861 MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id];
1862 MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id];
1863 bool DefIsReMat = ReMatDefMI != NULL;
Evan Chengf2fbca62007-11-12 06:35:08 +00001864 bool CanDelete = ReMatDelete[I->valno->id];
1865 int LdSlot = 0;
Evan Cheng81a03822007-11-17 00:40:40 +00001866 bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
Evan Chengf2fbca62007-11-12 06:35:08 +00001867 bool isLoad = isLoadSS ||
Dan Gohman15511cf2008-12-03 18:15:48 +00001868 (DefIsReMat && ReMatDefMI->getDesc().canFoldAsLoad());
Evan Cheng81a03822007-11-17 00:40:40 +00001869 rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI,
Evan Cheng0cbb1162007-11-29 01:06:25 +00001870 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
Evan Chengd70dbb52008-02-22 09:24:50 +00001871 CanDelete, vrm, rc, ReMatIds, loopInfo,
Evan Cheng0cbb1162007-11-29 01:06:25 +00001872 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
Evan Chengc781a242009-05-03 18:32:42 +00001873 MBBVRegsMap, NewLIs);
Evan Chengf2fbca62007-11-12 06:35:08 +00001874 }
1875
Evan Cheng0cbb1162007-11-29 01:06:25 +00001876 // Insert spills / restores if we are splitting.
Evan Cheng419852c2008-04-03 16:39:43 +00001877 if (!TrySplit) {
Evan Cheng4cce6b42008-04-11 17:53:36 +00001878 handleSpilledImpDefs(li, vrm, rc, NewLIs);
Jakob Stoklund Olesen352d3522010-02-18 21:33:05 +00001879 normalizeSpillWeights(NewLIs);
Evan Cheng1953d0c2007-11-29 10:12:14 +00001880 return NewLIs;
Evan Cheng419852c2008-04-03 16:39:43 +00001881 }
Evan Cheng1953d0c2007-11-29 10:12:14 +00001882
Evan Chengb50bb8c2007-12-05 08:16:32 +00001883 SmallPtrSet<LiveInterval*, 4> AddedKill;
Evan Chengaee4af62007-12-02 08:30:39 +00001884 SmallVector<unsigned, 2> Ops;
Evan Cheng1953d0c2007-11-29 10:12:14 +00001885 if (NeedStackSlot) {
1886 int Id = SpillMBBs.find_first();
1887 while (Id != -1) {
1888 std::vector<SRInfo> &spills = SpillIdxes[Id];
1889 for (unsigned i = 0, e = spills.size(); i != e; ++i) {
Lang Hames233a60e2009-11-03 23:52:08 +00001890 SlotIndex index = spills[i].index;
Evan Cheng1953d0c2007-11-29 10:12:14 +00001891 unsigned VReg = spills[i].vreg;
Evan Cheng597d10d2007-12-04 00:32:23 +00001892 LiveInterval &nI = getOrCreateInterval(VReg);
Evan Cheng0cbb1162007-11-29 01:06:25 +00001893 bool isReMat = vrm.isReMaterialized(VReg);
1894 MachineInstr *MI = getInstructionFromIndex(index);
Evan Chengaee4af62007-12-02 08:30:39 +00001895 bool CanFold = false;
1896 bool FoundUse = false;
1897 Ops.clear();
Evan Chengcddbb832007-11-30 21:23:43 +00001898 if (spills[i].canFold) {
Evan Chengaee4af62007-12-02 08:30:39 +00001899 CanFold = true;
Evan Cheng0cbb1162007-11-29 01:06:25 +00001900 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
1901 MachineOperand &MO = MI->getOperand(j);
Dan Gohmand735b802008-10-03 15:45:36 +00001902 if (!MO.isReg() || MO.getReg() != VReg)
Evan Cheng0cbb1162007-11-29 01:06:25 +00001903 continue;
Evan Chengaee4af62007-12-02 08:30:39 +00001904
1905 Ops.push_back(j);
1906 if (MO.isDef())
Evan Chengcddbb832007-11-30 21:23:43 +00001907 continue;
Jakob Stoklund Olesen1b293202010-08-12 20:01:23 +00001908 if (isReMat ||
Evan Chengaee4af62007-12-02 08:30:39 +00001909 (!FoundUse && !alsoFoldARestore(Id, index, VReg,
1910 RestoreMBBs, RestoreIdxes))) {
1911 // MI has two-address uses of the same register. If the use
1912 // isn't the first and only use in the BB, then we can't fold
1913 // it. FIXME: Move this to rewriteInstructionsForSpills.
1914 CanFold = false;
Evan Chengcddbb832007-11-30 21:23:43 +00001915 break;
1916 }
Evan Chengaee4af62007-12-02 08:30:39 +00001917 FoundUse = true;
Evan Cheng0cbb1162007-11-29 01:06:25 +00001918 }
1919 }
1920 // Fold the store into the def if possible.
Evan Chengcddbb832007-11-30 21:23:43 +00001921 bool Folded = false;
Evan Chengaee4af62007-12-02 08:30:39 +00001922 if (CanFold && !Ops.empty()) {
1923 if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){
Evan Chengcddbb832007-11-30 21:23:43 +00001924 Folded = true;
Sebastian Redl48fe6352009-03-19 23:26:52 +00001925 if (FoundUse) {
Evan Chengaee4af62007-12-02 08:30:39 +00001926 // Also folded uses, do not issue a load.
1927 eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes);
Lang Hames233a60e2009-11-03 23:52:08 +00001928 nI.removeRange(index.getLoadIndex(), index.getDefIndex());
Evan Chengf38d14f2007-12-05 09:05:34 +00001929 }
Lang Hames233a60e2009-11-03 23:52:08 +00001930 nI.removeRange(index.getDefIndex(), index.getStoreIndex());
Evan Chengcddbb832007-11-30 21:23:43 +00001931 }
Evan Cheng0cbb1162007-11-29 01:06:25 +00001932 }
1933
Evan Cheng7e073ba2008-04-09 20:57:25 +00001934 // Otherwise tell the spiller to issue a spill.
Evan Chengb50bb8c2007-12-05 08:16:32 +00001935 if (!Folded) {
1936 LiveRange *LR = &nI.ranges[nI.ranges.size()-1];
Lang Hames233a60e2009-11-03 23:52:08 +00001937 bool isKill = LR->end == index.getStoreIndex();
Evan Chengb0a6f622008-05-20 08:10:37 +00001938 if (!MI->registerDefIsDead(nI.reg))
1939 // No need to spill a dead def.
1940 vrm.addSpillPoint(VReg, isKill, MI);
Evan Chengb50bb8c2007-12-05 08:16:32 +00001941 if (isKill)
1942 AddedKill.insert(&nI);
1943 }
Evan Cheng0cbb1162007-11-29 01:06:25 +00001944 }
Evan Cheng1953d0c2007-11-29 10:12:14 +00001945 Id = SpillMBBs.find_next(Id);
Evan Cheng0cbb1162007-11-29 01:06:25 +00001946 }
Evan Cheng1953d0c2007-11-29 10:12:14 +00001947 }
Evan Cheng0cbb1162007-11-29 01:06:25 +00001948
Evan Cheng1953d0c2007-11-29 10:12:14 +00001949 int Id = RestoreMBBs.find_first();
1950 while (Id != -1) {
1951 std::vector<SRInfo> &restores = RestoreIdxes[Id];
1952 for (unsigned i = 0, e = restores.size(); i != e; ++i) {
Lang Hames233a60e2009-11-03 23:52:08 +00001953 SlotIndex index = restores[i].index;
1954 if (index == SlotIndex())
Evan Cheng1953d0c2007-11-29 10:12:14 +00001955 continue;
1956 unsigned VReg = restores[i].vreg;
Evan Cheng597d10d2007-12-04 00:32:23 +00001957 LiveInterval &nI = getOrCreateInterval(VReg);
Evan Cheng9c3c2212008-06-06 07:54:39 +00001958 bool isReMat = vrm.isReMaterialized(VReg);
Evan Cheng81a03822007-11-17 00:40:40 +00001959 MachineInstr *MI = getInstructionFromIndex(index);
Evan Chengaee4af62007-12-02 08:30:39 +00001960 bool CanFold = false;
1961 Ops.clear();
Evan Chengcddbb832007-11-30 21:23:43 +00001962 if (restores[i].canFold) {
Evan Chengaee4af62007-12-02 08:30:39 +00001963 CanFold = true;
Evan Cheng81a03822007-11-17 00:40:40 +00001964 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
1965 MachineOperand &MO = MI->getOperand(j);
Dan Gohmand735b802008-10-03 15:45:36 +00001966 if (!MO.isReg() || MO.getReg() != VReg)
Evan Cheng81a03822007-11-17 00:40:40 +00001967 continue;
Evan Chengaee4af62007-12-02 08:30:39 +00001968
Evan Cheng0cbb1162007-11-29 01:06:25 +00001969 if (MO.isDef()) {
Evan Chengaee4af62007-12-02 08:30:39 +00001970 // If this restore were to be folded, it would have been folded
1971 // already.
1972 CanFold = false;
Evan Cheng81a03822007-11-17 00:40:40 +00001973 break;
1974 }
Evan Chengaee4af62007-12-02 08:30:39 +00001975 Ops.push_back(j);
Evan Cheng81a03822007-11-17 00:40:40 +00001976 }
1977 }
Evan Cheng0cbb1162007-11-29 01:06:25 +00001978
1979 // Fold the load into the use if possible.
Evan Chengcddbb832007-11-30 21:23:43 +00001980 bool Folded = false;
Evan Chengaee4af62007-12-02 08:30:39 +00001981 if (CanFold && !Ops.empty()) {
Evan Cheng9c3c2212008-06-06 07:54:39 +00001982 if (!isReMat)
Evan Chengaee4af62007-12-02 08:30:39 +00001983 Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg);
1984 else {
Evan Cheng0cbb1162007-11-29 01:06:25 +00001985 MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg);
1986 int LdSlot = 0;
1987 bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1988 // If the rematerializable def is a load, also try to fold it.
Dan Gohman15511cf2008-12-03 18:15:48 +00001989 if (isLoadSS || ReMatDefMI->getDesc().canFoldAsLoad())
Evan Chengaee4af62007-12-02 08:30:39 +00001990 Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
1991 Ops, isLoadSS, LdSlot, VReg);
Evan Cheng650d7f32008-12-05 17:41:31 +00001992 if (!Folded) {
1993 unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI);
1994 if (ImpUse) {
1995 // Re-matting an instruction with virtual register use. Add the
Jakob Stoklund Olesene5d90412010-03-01 20:59:38 +00001996 // register as an implicit use on the use MI and mark the register
1997 // interval as unspillable.
Evan Cheng650d7f32008-12-05 17:41:31 +00001998 LiveInterval &ImpLi = getInterval(ImpUse);
Jakob Stoklund Olesene5d90412010-03-01 20:59:38 +00001999 ImpLi.markNotSpillable();
Evan Cheng650d7f32008-12-05 17:41:31 +00002000 MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true));
2001 }
Evan Chengd70dbb52008-02-22 09:24:50 +00002002 }
Evan Chengaee4af62007-12-02 08:30:39 +00002003 }
Evan Cheng0cbb1162007-11-29 01:06:25 +00002004 }
2005 // If folding is not possible / failed, then tell the spiller to issue a
2006 // load / rematerialization for us.
Evan Cheng597d10d2007-12-04 00:32:23 +00002007 if (Folded)
Lang Hames233a60e2009-11-03 23:52:08 +00002008 nI.removeRange(index.getLoadIndex(), index.getDefIndex());
Evan Chengb50bb8c2007-12-05 08:16:32 +00002009 else
Evan Cheng0cbb1162007-11-29 01:06:25 +00002010 vrm.addRestorePoint(VReg, MI);
Evan Cheng81a03822007-11-17 00:40:40 +00002011 }
Evan Cheng1953d0c2007-11-29 10:12:14 +00002012 Id = RestoreMBBs.find_next(Id);
Evan Cheng81a03822007-11-17 00:40:40 +00002013 }
2014
Evan Chengb50bb8c2007-12-05 08:16:32 +00002015 // Finalize intervals: add kills, finalize spill weights, and filter out
2016 // dead intervals.
Evan Cheng597d10d2007-12-04 00:32:23 +00002017 std::vector<LiveInterval*> RetNewLIs;
2018 for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) {
2019 LiveInterval *LI = NewLIs[i];
2020 if (!LI->empty()) {
Evan Chengb50bb8c2007-12-05 08:16:32 +00002021 if (!AddedKill.count(LI)) {
2022 LiveRange *LR = &LI->ranges[LI->ranges.size()-1];
Lang Hames233a60e2009-11-03 23:52:08 +00002023 SlotIndex LastUseIdx = LR->end.getBaseIndex();
Evan Chengd120ffd2007-12-05 10:24:35 +00002024 MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx);
Evan Cheng6130f662008-03-05 00:59:57 +00002025 int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false);
Evan Chengb50bb8c2007-12-05 08:16:32 +00002026 assert(UseIdx != -1);
Evan Chenga24752f2009-03-19 20:30:06 +00002027 if (!LastUse->isRegTiedToDefOperand(UseIdx)) {
Evan Chengb50bb8c2007-12-05 08:16:32 +00002028 LastUse->getOperand(UseIdx).setIsKill();
Evan Chengd120ffd2007-12-05 10:24:35 +00002029 vrm.addKillPoint(LI->reg, LastUseIdx);
Evan Chengadf85902007-12-05 09:51:10 +00002030 }
Evan Chengb50bb8c2007-12-05 08:16:32 +00002031 }
Evan Cheng597d10d2007-12-04 00:32:23 +00002032 RetNewLIs.push_back(LI);
2033 }
2034 }
Evan Cheng81a03822007-11-17 00:40:40 +00002035
Evan Cheng4cce6b42008-04-11 17:53:36 +00002036 handleSpilledImpDefs(li, vrm, rc, RetNewLIs);
Jakob Stoklund Olesen352d3522010-02-18 21:33:05 +00002037 normalizeSpillWeights(RetNewLIs);
Evan Cheng597d10d2007-12-04 00:32:23 +00002038 return RetNewLIs;
Evan Chengf2fbca62007-11-12 06:35:08 +00002039}
Evan Cheng676dd7c2008-03-11 07:19:34 +00002040
2041/// hasAllocatableSuperReg - Return true if the specified physical register has
2042/// any super register that's allocatable.
2043bool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const {
2044 for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS)
2045 if (allocatableRegs_[*AS] && hasInterval(*AS))
2046 return true;
2047 return false;
2048}
2049
2050/// getRepresentativeReg - Find the largest super register of the specified
2051/// physical register.
2052unsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const {
Jakob Stoklund Olesen1b293202010-08-12 20:01:23 +00002053 // Find the largest super-register that is allocatable.
Evan Cheng676dd7c2008-03-11 07:19:34 +00002054 unsigned BestReg = Reg;
2055 for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) {
2056 unsigned SuperReg = *AS;
2057 if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) {
2058 BestReg = SuperReg;
2059 break;
2060 }
2061 }
2062 return BestReg;
2063}
2064
2065/// getNumConflictsWithPhysReg - Return the number of uses and defs of the
2066/// specified interval that conflicts with the specified physical register.
2067unsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li,
2068 unsigned PhysReg) const {
2069 unsigned NumConflicts = 0;
2070 const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg));
2071 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
2072 E = mri_->reg_end(); I != E; ++I) {
2073 MachineOperand &O = I.getOperand();
2074 MachineInstr *MI = O.getParent();
Evan Cheng28a1e482010-03-30 05:49:07 +00002075 if (MI->isDebugValue())
2076 continue;
Lang Hames233a60e2009-11-03 23:52:08 +00002077 SlotIndex Index = getInstructionIndex(MI);
Evan Cheng676dd7c2008-03-11 07:19:34 +00002078 if (pli.liveAt(Index))
2079 ++NumConflicts;
2080 }
2081 return NumConflicts;
2082}
2083
2084/// spillPhysRegAroundRegDefsUses - Spill the specified physical register
Evan Cheng2824a652009-03-23 18:24:37 +00002085/// around all defs and uses of the specified interval. Return true if it
2086/// was able to cut its interval.
2087bool LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li,
Evan Cheng676dd7c2008-03-11 07:19:34 +00002088 unsigned PhysReg, VirtRegMap &vrm) {
2089 unsigned SpillReg = getRepresentativeReg(PhysReg);
2090
Jakob Stoklund Olesenf4840c02010-11-16 19:55:14 +00002091 DEBUG(dbgs() << "spillPhysRegAroundRegDefsUses " << tri_->getName(PhysReg)
2092 << " represented by " << tri_->getName(SpillReg) << '\n');
2093
Evan Cheng676dd7c2008-03-11 07:19:34 +00002094 for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS)
2095 // If there are registers which alias PhysReg, but which are not a
2096 // sub-register of the chosen representative super register. Assert
2097 // since we can't handle it yet.
Dan Gohman70f2f652009-04-13 15:22:29 +00002098 assert(*AS == SpillReg || !allocatableRegs_[*AS] || !hasInterval(*AS) ||
Evan Cheng676dd7c2008-03-11 07:19:34 +00002099 tri_->isSuperRegister(*AS, SpillReg));
2100
Evan Cheng2824a652009-03-23 18:24:37 +00002101 bool Cut = false;
Evan Cheng0222a8c2009-10-20 01:31:09 +00002102 SmallVector<unsigned, 4> PRegs;
2103 if (hasInterval(SpillReg))
2104 PRegs.push_back(SpillReg);
Jakob Stoklund Olesenf4840c02010-11-16 19:55:14 +00002105 for (const unsigned *SR = tri_->getSubRegisters(SpillReg); *SR; ++SR)
2106 if (hasInterval(*SR))
2107 PRegs.push_back(*SR);
2108
2109 DEBUG({
2110 dbgs() << "Trying to spill:";
2111 for (unsigned i = 0, e = PRegs.size(); i != e; ++i)
2112 dbgs() << ' ' << tri_->getName(PRegs[i]);
2113 dbgs() << '\n';
2114 });
Evan Cheng0222a8c2009-10-20 01:31:09 +00002115
Evan Cheng676dd7c2008-03-11 07:19:34 +00002116 SmallPtrSet<MachineInstr*, 8> SeenMIs;
2117 for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg),
2118 E = mri_->reg_end(); I != E; ++I) {
2119 MachineOperand &O = I.getOperand();
2120 MachineInstr *MI = O.getParent();
Evan Cheng28a1e482010-03-30 05:49:07 +00002121 if (MI->isDebugValue() || SeenMIs.count(MI))
Evan Cheng676dd7c2008-03-11 07:19:34 +00002122 continue;
2123 SeenMIs.insert(MI);
Lang Hames233a60e2009-11-03 23:52:08 +00002124 SlotIndex Index = getInstructionIndex(MI);
Jakob Stoklund Olesenf4840c02010-11-16 19:55:14 +00002125 bool LiveReg = false;
Evan Cheng0222a8c2009-10-20 01:31:09 +00002126 for (unsigned i = 0, e = PRegs.size(); i != e; ++i) {
2127 unsigned PReg = PRegs[i];
2128 LiveInterval &pli = getInterval(PReg);
2129 if (!pli.liveAt(Index))
2130 continue;
Jakob Stoklund Olesenf4840c02010-11-16 19:55:14 +00002131 LiveReg = true;
Lang Hames233a60e2009-11-03 23:52:08 +00002132 SlotIndex StartIdx = Index.getLoadIndex();
2133 SlotIndex EndIdx = Index.getNextIndex().getBaseIndex();
Jakob Stoklund Olesenf4840c02010-11-16 19:55:14 +00002134 if (!pli.isInOneLiveRange(StartIdx, EndIdx)) {
Torok Edwin7d696d82009-07-11 13:10:19 +00002135 std::string msg;
2136 raw_string_ostream Msg(msg);
2137 Msg << "Ran out of registers during register allocation!";
Chris Lattner518bb532010-02-09 19:54:29 +00002138 if (MI->isInlineAsm()) {
Torok Edwin7d696d82009-07-11 13:10:19 +00002139 Msg << "\nPlease check your inline asm statement for invalid "
Evan Cheng0222a8c2009-10-20 01:31:09 +00002140 << "constraints:\n";
Torok Edwin7d696d82009-07-11 13:10:19 +00002141 MI->print(Msg, tm_);
Evan Cheng5a3c6a82009-01-29 02:20:59 +00002142 }
Chris Lattner75361b62010-04-07 22:58:41 +00002143 report_fatal_error(Msg.str());
Evan Cheng5a3c6a82009-01-29 02:20:59 +00002144 }
Jakob Stoklund Olesenf4840c02010-11-16 19:55:14 +00002145 pli.removeRange(StartIdx, EndIdx);
2146 LiveReg = true;
Evan Cheng676dd7c2008-03-11 07:19:34 +00002147 }
Jakob Stoklund Olesenf4840c02010-11-16 19:55:14 +00002148 if (!LiveReg)
2149 continue;
2150 DEBUG(dbgs() << "Emergency spill around " << Index << '\t' << *MI);
2151 vrm.addEmergencySpill(SpillReg, MI);
2152 Cut = true;
Evan Cheng676dd7c2008-03-11 07:19:34 +00002153 }
Evan Cheng2824a652009-03-23 18:24:37 +00002154 return Cut;
Evan Cheng676dd7c2008-03-11 07:19:34 +00002155}
Owen Andersonc4dc1322008-06-05 17:15:43 +00002156
2157LiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg,
Lang Hamesffd13262009-07-09 03:57:02 +00002158 MachineInstr* startInst) {
Owen Andersonc4dc1322008-06-05 17:15:43 +00002159 LiveInterval& Interval = getOrCreateInterval(reg);
2160 VNInfo* VN = Interval.getNextValue(
Lang Hames233a60e2009-11-03 23:52:08 +00002161 SlotIndex(getInstructionIndex(startInst).getDefIndex()),
Lang Hames6e2968c2010-09-25 12:04:16 +00002162 startInst, getVNInfoAllocator());
Lang Hames857c4e02009-06-17 21:01:20 +00002163 VN->setHasPHIKill(true);
Lang Hames86511252009-09-04 20:41:11 +00002164 LiveRange LR(
Lang Hames233a60e2009-11-03 23:52:08 +00002165 SlotIndex(getInstructionIndex(startInst).getDefIndex()),
Lang Hames74ab5ee2009-12-22 00:11:50 +00002166 getMBBEndIdx(startInst->getParent()), VN);
Owen Andersonc4dc1322008-06-05 17:15:43 +00002167 Interval.addRange(LR);
Jakob Stoklund Olesen1b293202010-08-12 20:01:23 +00002168
Owen Andersonc4dc1322008-06-05 17:15:43 +00002169 return LR;
2170}
David Greeneb5257662009-08-03 21:55:09 +00002171