blob: db9cfee5f80710267e78bb5377be5c1836d980a5 [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"
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000022#include "llvm/CodeGen/LiveVariables.h"
23#include "llvm/CodeGen/MachineFrameInfo.h"
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000024#include "llvm/CodeGen/MachineInstr.h"
Evan Cheng22f07ff2007-12-11 02:09:15 +000025#include "llvm/CodeGen/MachineLoopInfo.h"
Chris Lattner84bc5422007-12-31 04:13:23 +000026#include "llvm/CodeGen/MachineRegisterInfo.h"
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000027#include "llvm/CodeGen/Passes.h"
Dan Gohman6f0d0242008-02-10 18:45:23 +000028#include "llvm/Target/TargetRegisterInfo.h"
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000029#include "llvm/Target/TargetInstrInfo.h"
30#include "llvm/Target/TargetMachine.h"
Reid Spencer551ccae2004-09-01 22:55:40 +000031#include "llvm/Support/CommandLine.h"
32#include "llvm/Support/Debug.h"
33#include "llvm/ADT/Statistic.h"
34#include "llvm/ADT/STLExtras.h"
Alkis Evlogimenos20aa4742004-09-03 18:19:51 +000035#include <algorithm>
Jeff Cohen97af7512006-12-02 02:22:01 +000036#include <cmath>
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000037using namespace llvm;
38
Evan Chengbc165e42007-08-16 07:24:22 +000039namespace {
40 // Hidden options for help debugging.
41 cl::opt<bool> DisableReMat("disable-rematerialization",
42 cl::init(false), cl::Hidden);
Evan Cheng81a03822007-11-17 00:40:40 +000043
44 cl::opt<bool> SplitAtBB("split-intervals-at-bb",
Evan Cheng33faddc2007-12-06 08:54:31 +000045 cl::init(true), cl::Hidden);
Evan Cheng0cbb1162007-11-29 01:06:25 +000046 cl::opt<int> SplitLimit("split-limit",
47 cl::init(-1), cl::Hidden);
Evan Chengbc165e42007-08-16 07:24:22 +000048}
49
Chris Lattnercd3245a2006-12-19 22:41:21 +000050STATISTIC(numIntervals, "Number of original intervals");
51STATISTIC(numIntervalsAfter, "Number of intervals after coalescing");
Evan Cheng0cbb1162007-11-29 01:06:25 +000052STATISTIC(numFolds , "Number of loads/stores folded into instructions");
53STATISTIC(numSplits , "Number of intervals split");
Chris Lattnercd3245a2006-12-19 22:41:21 +000054
Devang Patel19974732007-05-03 01:11:54 +000055char LiveIntervals::ID = 0;
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000056namespace {
Chris Lattner5d8925c2006-08-27 22:30:17 +000057 RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis");
Chris Lattnerd74ea2b2006-05-24 17:04:05 +000058}
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000059
Chris Lattnerf7da2c72006-08-24 22:43:55 +000060void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const {
David Greene25133302007-06-08 17:18:56 +000061 AU.addPreserved<LiveVariables>();
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +000062 AU.addRequired<LiveVariables>();
Bill Wendling67d65bb2008-01-04 20:54:55 +000063 AU.addPreservedID(MachineLoopInfoID);
64 AU.addPreservedID(MachineDominatorsID);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +000065 AU.addPreservedID(PHIEliminationID);
66 AU.addRequiredID(PHIEliminationID);
67 AU.addRequiredID(TwoAddressInstructionPassID);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +000068 MachineFunctionPass::getAnalysisUsage(AU);
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000069}
70
Chris Lattnerf7da2c72006-08-24 22:43:55 +000071void LiveIntervals::releaseMemory() {
Evan Cheng4ca980e2007-10-17 02:10:22 +000072 Idx2MBBMap.clear();
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +000073 mi2iMap_.clear();
74 i2miMap_.clear();
75 r2iMap_.clear();
Evan Chengdd199d22007-09-06 01:07:24 +000076 // Release VNInfo memroy regions after all VNInfo objects are dtor'd.
77 VNInfoAllocator.Reset();
Evan Cheng549f27d32007-08-13 23:45:17 +000078 for (unsigned i = 0, e = ClonedMIs.size(); i != e; ++i)
79 delete ClonedMIs[i];
Alkis Evlogimenos08cec002004-01-31 19:59:32 +000080}
81
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000082/// runOnMachineFunction - Register allocate the whole function
83///
84bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +000085 mf_ = &fn;
86 tm_ = &fn.getTarget();
Dan Gohman6f0d0242008-02-10 18:45:23 +000087 tri_ = tm_->getRegisterInfo();
Chris Lattnerf768bba2005-03-09 23:05:19 +000088 tii_ = tm_->getInstrInfo();
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +000089 lv_ = &getAnalysis<LiveVariables>();
Dan Gohman6f0d0242008-02-10 18:45:23 +000090 allocatableRegs_ = tri_->getAllocatableSet(fn);
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +000091
Chris Lattner428b92e2006-09-15 03:57:23 +000092 // Number MachineInstrs and MachineBasicBlocks.
93 // Initialize MBB indexes to a sentinal.
Evan Cheng549f27d32007-08-13 23:45:17 +000094 MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U));
Chris Lattner428b92e2006-09-15 03:57:23 +000095
96 unsigned MIIndex = 0;
97 for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end();
98 MBB != E; ++MBB) {
Evan Cheng549f27d32007-08-13 23:45:17 +000099 unsigned StartIdx = MIIndex;
Evan Cheng0c9f92e2007-02-13 01:30:55 +0000100
Chris Lattner428b92e2006-09-15 03:57:23 +0000101 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end();
102 I != E; ++I) {
103 bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second;
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000104 assert(inserted && "multiple MachineInstr -> index mappings");
Chris Lattner428b92e2006-09-15 03:57:23 +0000105 i2miMap_.push_back(I);
106 MIIndex += InstrSlots::NUM;
Alkis Evlogimenos843b1602004-02-15 10:24:21 +0000107 }
Evan Cheng549f27d32007-08-13 23:45:17 +0000108
109 // Set the MBB2IdxMap entry for this MBB.
110 MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1);
Evan Cheng4ca980e2007-10-17 02:10:22 +0000111 Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB));
Chris Lattner428b92e2006-09-15 03:57:23 +0000112 }
Evan Cheng4ca980e2007-10-17 02:10:22 +0000113 std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare());
Alkis Evlogimenosd6e40a62004-01-14 10:44:29 +0000114
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000115 computeIntervals();
Alkis Evlogimenos843b1602004-02-15 10:24:21 +0000116
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000117 numIntervals += getNumIntervals();
118
Bill Wendlingbdc679d2006-11-29 00:39:47 +0000119 DOUT << "********** INTERVALS **********\n";
120 for (iterator I = begin(), E = end(); I != E; ++I) {
Dan Gohman6f0d0242008-02-10 18:45:23 +0000121 I->second.print(DOUT, tri_);
Bill Wendlingbdc679d2006-11-29 00:39:47 +0000122 DOUT << "\n";
123 }
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000124
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000125 numIntervalsAfter += getNumIntervals();
Chris Lattner70ca3582004-09-30 15:59:17 +0000126 DEBUG(dump());
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000127 return true;
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000128}
129
Chris Lattner70ca3582004-09-30 15:59:17 +0000130/// print - Implement the dump method.
Reid Spencerce9653c2004-12-07 04:03:45 +0000131void LiveIntervals::print(std::ostream &O, const Module* ) const {
Chris Lattner70ca3582004-09-30 15:59:17 +0000132 O << "********** INTERVALS **********\n";
Chris Lattner8e7a7092005-07-27 23:03:38 +0000133 for (const_iterator I = begin(), E = end(); I != E; ++I) {
Dan Gohman6f0d0242008-02-10 18:45:23 +0000134 I->second.print(DOUT, tri_);
Bill Wendlingbdc679d2006-11-29 00:39:47 +0000135 DOUT << "\n";
Chris Lattner8e7a7092005-07-27 23:03:38 +0000136 }
Chris Lattner70ca3582004-09-30 15:59:17 +0000137
138 O << "********** MACHINEINSTRS **********\n";
139 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
140 mbbi != mbbe; ++mbbi) {
141 O << ((Value*)mbbi->getBasicBlock())->getName() << ":\n";
142 for (MachineBasicBlock::iterator mii = mbbi->begin(),
143 mie = mbbi->end(); mii != mie; ++mii) {
Chris Lattner477e4552004-09-30 16:10:45 +0000144 O << getInstructionIndex(mii) << '\t' << *mii;
Chris Lattner70ca3582004-09-30 15:59:17 +0000145 }
146 }
147}
148
Evan Chengc92da382007-11-03 07:20:12 +0000149/// conflictsWithPhysRegDef - Returns true if the specified register
150/// is defined during the duration of the specified interval.
151bool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li,
152 VirtRegMap &vrm, unsigned reg) {
153 for (LiveInterval::Ranges::const_iterator
154 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
155 for (unsigned index = getBaseIndex(I->start),
156 end = getBaseIndex(I->end-1) + InstrSlots::NUM; index != end;
157 index += InstrSlots::NUM) {
158 // skip deleted instructions
159 while (index != end && !getInstructionFromIndex(index))
160 index += InstrSlots::NUM;
161 if (index == end) break;
162
163 MachineInstr *MI = getInstructionFromIndex(index);
Evan Cheng5d446262007-11-15 08:13:29 +0000164 unsigned SrcReg, DstReg;
165 if (tii_->isMoveInstr(*MI, SrcReg, DstReg))
166 if (SrcReg == li.reg || DstReg == li.reg)
167 continue;
Evan Chengc92da382007-11-03 07:20:12 +0000168 for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
169 MachineOperand& mop = MI->getOperand(i);
Evan Cheng5d446262007-11-15 08:13:29 +0000170 if (!mop.isRegister())
Evan Chengc92da382007-11-03 07:20:12 +0000171 continue;
172 unsigned PhysReg = mop.getReg();
Evan Cheng5d446262007-11-15 08:13:29 +0000173 if (PhysReg == 0 || PhysReg == li.reg)
Evan Chengc92da382007-11-03 07:20:12 +0000174 continue;
Dan Gohman6f0d0242008-02-10 18:45:23 +0000175 if (TargetRegisterInfo::isVirtualRegister(PhysReg)) {
Evan Cheng5d446262007-11-15 08:13:29 +0000176 if (!vrm.hasPhys(PhysReg))
177 continue;
Evan Chengc92da382007-11-03 07:20:12 +0000178 PhysReg = vrm.getPhys(PhysReg);
Evan Cheng5d446262007-11-15 08:13:29 +0000179 }
Dan Gohman6f0d0242008-02-10 18:45:23 +0000180 if (PhysReg && tri_->regsOverlap(PhysReg, reg))
Evan Chengc92da382007-11-03 07:20:12 +0000181 return true;
182 }
183 }
184 }
185
186 return false;
187}
188
Evan Cheng549f27d32007-08-13 23:45:17 +0000189void LiveIntervals::printRegName(unsigned reg) const {
Dan Gohman6f0d0242008-02-10 18:45:23 +0000190 if (TargetRegisterInfo::isPhysicalRegister(reg))
191 cerr << tri_->getName(reg);
Evan Cheng549f27d32007-08-13 23:45:17 +0000192 else
193 cerr << "%reg" << reg;
194}
195
Chris Lattnerbe4f88a2006-08-22 18:19:46 +0000196void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000197 MachineBasicBlock::iterator mi,
Chris Lattner6b128bd2006-09-03 08:07:11 +0000198 unsigned MIIdx,
Chris Lattnerbe4f88a2006-08-22 18:19:46 +0000199 LiveInterval &interval) {
Bill Wendlingbdc679d2006-11-29 00:39:47 +0000200 DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg));
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000201 LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg);
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000202
Alkis Evlogimenos70651572004-08-04 09:46:56 +0000203 // Virtual registers may be defined multiple times (due to phi
204 // elimination and 2-addr elimination). Much of what we do only has to be
205 // done once for the vreg. We use an empty interval to detect the first
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000206 // time we see a vreg.
207 if (interval.empty()) {
208 // Get the Idx of the defining instructions.
Chris Lattner6b128bd2006-09-03 08:07:11 +0000209 unsigned defIndex = getDefIndex(MIIdx);
Evan Cheng7ecb38b2007-08-29 20:45:00 +0000210 VNInfo *ValNo;
Evan Chengc8d044e2008-02-15 18:24:29 +0000211 MachineInstr *CopyMI = NULL;
Chris Lattner91725b72006-08-31 05:54:43 +0000212 unsigned SrcReg, DstReg;
Evan Chengc8d044e2008-02-15 18:24:29 +0000213 if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
214 tii_->isMoveInstr(*mi, SrcReg, DstReg))
215 CopyMI = mi;
216 ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator);
Evan Cheng7ecb38b2007-08-29 20:45:00 +0000217
218 assert(ValNo->id == 0 && "First value in interval is not 0?");
Chris Lattner7ac2d312004-07-24 02:59:07 +0000219
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000220 // Loop over all of the blocks that the vreg is defined in. There are
221 // two cases we have to handle here. The most common case is a vreg
222 // whose lifetime is contained within a basic block. In this case there
223 // will be a single kill, in MBB, which comes after the definition.
224 if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) {
225 // FIXME: what about dead vars?
226 unsigned killIdx;
227 if (vi.Kills[0] != mi)
228 killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1;
229 else
230 killIdx = defIndex+1;
Chris Lattner6097d132004-07-19 02:15:56 +0000231
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000232 // If the kill happens after the definition, we have an intra-block
233 // live range.
234 if (killIdx > defIndex) {
Evan Cheng61de82d2007-02-15 05:59:24 +0000235 assert(vi.AliveBlocks.none() &&
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000236 "Shouldn't be alive across any blocks!");
Evan Cheng7ecb38b2007-08-29 20:45:00 +0000237 LiveRange LR(defIndex, killIdx, ValNo);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000238 interval.addRange(LR);
Bill Wendlingbdc679d2006-11-29 00:39:47 +0000239 DOUT << " +" << LR << "\n";
Evan Chengf3bb2e62007-09-05 21:46:51 +0000240 interval.addKill(ValNo, killIdx);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000241 return;
242 }
Alkis Evlogimenosdd2cc652003-12-18 08:48:48 +0000243 }
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000244
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000245 // The other case we handle is when a virtual register lives to the end
246 // of the defining block, potentially live across some blocks, then is
247 // live into some number of blocks, but gets killed. Start by adding a
248 // range that goes from this definition to the end of the defining block.
Alkis Evlogimenosd19e2902004-08-31 17:39:15 +0000249 LiveRange NewLR(defIndex,
250 getInstructionIndex(&mbb->back()) + InstrSlots::NUM,
Evan Cheng7ecb38b2007-08-29 20:45:00 +0000251 ValNo);
Bill Wendlingbdc679d2006-11-29 00:39:47 +0000252 DOUT << " +" << NewLR;
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000253 interval.addRange(NewLR);
254
255 // Iterate over all of the blocks that the variable is completely
256 // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the
257 // live interval.
258 for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) {
259 if (vi.AliveBlocks[i]) {
Chris Lattner428b92e2006-09-15 03:57:23 +0000260 MachineBasicBlock *MBB = mf_->getBlockNumbered(i);
261 if (!MBB->empty()) {
262 LiveRange LR(getMBBStartIdx(i),
263 getInstructionIndex(&MBB->back()) + InstrSlots::NUM,
Evan Cheng7ecb38b2007-08-29 20:45:00 +0000264 ValNo);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000265 interval.addRange(LR);
Bill Wendlingbdc679d2006-11-29 00:39:47 +0000266 DOUT << " +" << LR;
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000267 }
268 }
269 }
270
271 // Finally, this virtual register is live from the start of any killing
272 // block to the 'use' slot of the killing instruction.
273 for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) {
274 MachineInstr *Kill = vi.Kills[i];
Evan Cheng8df78602007-08-08 03:00:28 +0000275 unsigned killIdx = getUseIndex(getInstructionIndex(Kill))+1;
Chris Lattner428b92e2006-09-15 03:57:23 +0000276 LiveRange LR(getMBBStartIdx(Kill->getParent()),
Evan Cheng7ecb38b2007-08-29 20:45:00 +0000277 killIdx, ValNo);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000278 interval.addRange(LR);
Evan Chengf3bb2e62007-09-05 21:46:51 +0000279 interval.addKill(ValNo, killIdx);
Bill Wendlingbdc679d2006-11-29 00:39:47 +0000280 DOUT << " +" << LR;
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000281 }
282
283 } else {
284 // If this is the second time we see a virtual register definition, it
285 // must be due to phi elimination or two addr elimination. If this is
Evan Chengbf105c82006-11-03 03:04:46 +0000286 // the result of two address elimination, then the vreg is one of the
287 // def-and-use register operand.
Evan Cheng32dfbea2007-10-12 08:50:34 +0000288 if (mi->isRegReDefinedByTwoAddr(interval.reg)) {
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000289 // If this is a two-address definition, then we have already processed
290 // the live range. The only problem is that we didn't realize there
291 // are actually two values in the live interval. Because of this we
292 // need to take the LiveRegion that defines this register and split it
293 // into two values.
Evan Chenga07cec92008-01-10 08:22:10 +0000294 assert(interval.containsOneValue());
295 unsigned DefIndex = getDefIndex(interval.getValNumInfo(0)->def);
Chris Lattner6b128bd2006-09-03 08:07:11 +0000296 unsigned RedefIndex = getDefIndex(MIIdx);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000297
Evan Cheng4f8ff162007-08-11 00:59:19 +0000298 const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1);
Evan Cheng7ecb38b2007-08-29 20:45:00 +0000299 VNInfo *OldValNo = OldLR->valno;
Evan Cheng4f8ff162007-08-11 00:59:19 +0000300
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000301 // Delete the initial value, which should be short and continuous,
Chris Lattnerbe4f88a2006-08-22 18:19:46 +0000302 // because the 2-addr copy must be in the same MBB as the redef.
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000303 interval.removeRange(DefIndex, RedefIndex);
Alkis Evlogimenos70651572004-08-04 09:46:56 +0000304
Chris Lattnerbe4f88a2006-08-22 18:19:46 +0000305 // Two-address vregs should always only be redefined once. This means
306 // that at this point, there should be exactly one value number in it.
307 assert(interval.containsOneValue() && "Unexpected 2-addr liveint!");
308
Chris Lattner91725b72006-08-31 05:54:43 +0000309 // The new value number (#1) is defined by the instruction we claimed
310 // defined value #0.
Evan Chengc8d044e2008-02-15 18:24:29 +0000311 VNInfo *ValNo = interval.getNextValue(OldValNo->def, OldValNo->copy,
312 VNInfoAllocator);
Chris Lattnerbe4f88a2006-08-22 18:19:46 +0000313
Chris Lattner91725b72006-08-31 05:54:43 +0000314 // Value#0 is now defined by the 2-addr instruction.
Evan Chengc8d044e2008-02-15 18:24:29 +0000315 OldValNo->def = RedefIndex;
316 OldValNo->copy = 0;
Chris Lattnerbe4f88a2006-08-22 18:19:46 +0000317
318 // Add the new live interval which replaces the range for the input copy.
319 LiveRange LR(DefIndex, RedefIndex, ValNo);
Bill Wendlingbdc679d2006-11-29 00:39:47 +0000320 DOUT << " replace range with " << LR;
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000321 interval.addRange(LR);
Evan Chengf3bb2e62007-09-05 21:46:51 +0000322 interval.addKill(ValNo, RedefIndex);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000323
324 // If this redefinition is dead, we need to add a dummy unit live
325 // range covering the def slot.
Chris Lattnerab4b66d2005-08-23 22:51:41 +0000326 if (lv_->RegisterDefIsDead(mi, interval.reg))
Evan Cheng7ecb38b2007-08-29 20:45:00 +0000327 interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo));
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000328
Evan Cheng56fdd7a2007-03-15 21:19:28 +0000329 DOUT << " RESULT: ";
Dan Gohman6f0d0242008-02-10 18:45:23 +0000330 interval.print(DOUT, tri_);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000331
332 } else {
333 // Otherwise, this must be because of phi elimination. If this is the
334 // first redefinition of the vreg that we have seen, go back and change
335 // the live range in the PHI block to be a different value number.
336 if (interval.containsOneValue()) {
337 assert(vi.Kills.size() == 1 &&
338 "PHI elimination vreg should have one kill, the PHI itself!");
339
340 // Remove the old range that we now know has an incorrect number.
Evan Chengf3bb2e62007-09-05 21:46:51 +0000341 VNInfo *VNI = interval.getValNumInfo(0);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000342 MachineInstr *Killer = vi.Kills[0];
Chris Lattner428b92e2006-09-15 03:57:23 +0000343 unsigned Start = getMBBStartIdx(Killer->getParent());
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000344 unsigned End = getUseIndex(getInstructionIndex(Killer))+1;
Evan Cheng56fdd7a2007-03-15 21:19:28 +0000345 DOUT << " Removing [" << Start << "," << End << "] from: ";
Dan Gohman6f0d0242008-02-10 18:45:23 +0000346 interval.print(DOUT, tri_); DOUT << "\n";
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000347 interval.removeRange(Start, End);
Evan Chengc3fc7d92007-11-29 09:49:23 +0000348 VNI->hasPHIKill = true;
Dan Gohman6f0d0242008-02-10 18:45:23 +0000349 DOUT << " RESULT: "; interval.print(DOUT, tri_);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000350
Chris Lattnerbe4f88a2006-08-22 18:19:46 +0000351 // Replace the interval with one of a NEW value number. Note that this
352 // value number isn't actually defined by an instruction, weird huh? :)
Evan Chengf3bb2e62007-09-05 21:46:51 +0000353 LiveRange LR(Start, End, interval.getNextValue(~0, 0, VNInfoAllocator));
Bill Wendlingbdc679d2006-11-29 00:39:47 +0000354 DOUT << " replace range with " << LR;
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000355 interval.addRange(LR);
Evan Chengf3bb2e62007-09-05 21:46:51 +0000356 interval.addKill(LR.valno, End);
Dan Gohman6f0d0242008-02-10 18:45:23 +0000357 DOUT << " RESULT: "; interval.print(DOUT, tri_);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000358 }
359
360 // In the case of PHI elimination, each variable definition is only
361 // live until the end of the block. We've already taken care of the
362 // rest of the live range.
Chris Lattner6b128bd2006-09-03 08:07:11 +0000363 unsigned defIndex = getDefIndex(MIIdx);
Chris Lattner91725b72006-08-31 05:54:43 +0000364
Evan Cheng7ecb38b2007-08-29 20:45:00 +0000365 VNInfo *ValNo;
Evan Chengc8d044e2008-02-15 18:24:29 +0000366 MachineInstr *CopyMI = NULL;
Chris Lattner91725b72006-08-31 05:54:43 +0000367 unsigned SrcReg, DstReg;
Evan Chengc8d044e2008-02-15 18:24:29 +0000368 if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
369 tii_->isMoveInstr(*mi, SrcReg, DstReg))
370 CopyMI = mi;
371 ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator);
Chris Lattner91725b72006-08-31 05:54:43 +0000372
Evan Cheng24c2e5c2007-08-08 07:03:29 +0000373 unsigned killIndex = getInstructionIndex(&mbb->back()) + InstrSlots::NUM;
Evan Cheng7ecb38b2007-08-29 20:45:00 +0000374 LiveRange LR(defIndex, killIndex, ValNo);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000375 interval.addRange(LR);
Evan Chengc3fc7d92007-11-29 09:49:23 +0000376 interval.addKill(ValNo, killIndex);
377 ValNo->hasPHIKill = true;
Bill Wendlingbdc679d2006-11-29 00:39:47 +0000378 DOUT << " +" << LR;
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000379 }
380 }
381
Bill Wendlingbdc679d2006-11-29 00:39:47 +0000382 DOUT << '\n';
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000383}
384
Chris Lattnerf35fef72004-07-23 21:24:19 +0000385void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB,
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000386 MachineBasicBlock::iterator mi,
Chris Lattner6b128bd2006-09-03 08:07:11 +0000387 unsigned MIIdx,
Chris Lattner91725b72006-08-31 05:54:43 +0000388 LiveInterval &interval,
Evan Chengc8d044e2008-02-15 18:24:29 +0000389 MachineInstr *CopyMI) {
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000390 // A physical register cannot be live across basic block, so its
391 // lifetime must end somewhere in its defining basic block.
Bill Wendlingbdc679d2006-11-29 00:39:47 +0000392 DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg));
Alkis Evlogimenos02ba13c2004-01-31 23:13:30 +0000393
Chris Lattner6b128bd2006-09-03 08:07:11 +0000394 unsigned baseIndex = MIIdx;
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000395 unsigned start = getDefIndex(baseIndex);
396 unsigned end = start;
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000397
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000398 // If it is not used after definition, it is considered dead at
399 // the instruction defining it. Hence its interval is:
400 // [defSlot(def), defSlot(def)+1)
Chris Lattnerab4b66d2005-08-23 22:51:41 +0000401 if (lv_->RegisterDefIsDead(mi, interval.reg)) {
Bill Wendlingbdc679d2006-11-29 00:39:47 +0000402 DOUT << " dead";
Chris Lattnerab4b66d2005-08-23 22:51:41 +0000403 end = getDefIndex(start) + 1;
404 goto exit;
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000405 }
406
407 // If it is not dead on definition, it must be killed by a
408 // subsequent instruction. Hence its interval is:
409 // [defSlot(def), useSlot(kill)+1)
Chris Lattner5ab6f5f2005-09-02 00:20:32 +0000410 while (++mi != MBB->end()) {
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000411 baseIndex += InstrSlots::NUM;
Chris Lattnerab4b66d2005-08-23 22:51:41 +0000412 if (lv_->KillsRegister(mi, interval.reg)) {
Bill Wendlingbdc679d2006-11-29 00:39:47 +0000413 DOUT << " killed";
Chris Lattnerab4b66d2005-08-23 22:51:41 +0000414 end = getUseIndex(baseIndex) + 1;
415 goto exit;
Evan Cheng9a1956a2006-11-15 20:54:11 +0000416 } else if (lv_->ModifiesRegister(mi, interval.reg)) {
417 // Another instruction redefines the register before it is ever read.
418 // Then the register is essentially dead at the instruction that defines
419 // it. Hence its interval is:
420 // [defSlot(def), defSlot(def)+1)
Bill Wendlingbdc679d2006-11-29 00:39:47 +0000421 DOUT << " dead";
Evan Cheng9a1956a2006-11-15 20:54:11 +0000422 end = getDefIndex(start) + 1;
423 goto exit;
Alkis Evlogimenosaf254732004-01-13 22:26:14 +0000424 }
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000425 }
Chris Lattner5ab6f5f2005-09-02 00:20:32 +0000426
427 // The only case we should have a dead physreg here without a killing or
428 // instruction where we know it's dead is if it is live-in to the function
429 // and never used.
Evan Chengc8d044e2008-02-15 18:24:29 +0000430 assert(!CopyMI && "physreg was not killed in defining block!");
Chris Lattner5ab6f5f2005-09-02 00:20:32 +0000431 end = getDefIndex(start) + 1; // It's dead.
Alkis Evlogimenos02ba13c2004-01-31 23:13:30 +0000432
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000433exit:
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000434 assert(start < end && "did not find end of interval?");
Chris Lattnerf768bba2005-03-09 23:05:19 +0000435
Evan Cheng24a3cc42007-04-25 07:30:23 +0000436 // Already exists? Extend old live interval.
437 LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start);
Evan Cheng7ecb38b2007-08-29 20:45:00 +0000438 VNInfo *ValNo = (OldLR != interval.end())
Evan Chengc8d044e2008-02-15 18:24:29 +0000439 ? OldLR->valno : interval.getNextValue(start, CopyMI, VNInfoAllocator);
Evan Cheng7ecb38b2007-08-29 20:45:00 +0000440 LiveRange LR(start, end, ValNo);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000441 interval.addRange(LR);
Evan Chengf3bb2e62007-09-05 21:46:51 +0000442 interval.addKill(LR.valno, end);
Bill Wendlingbdc679d2006-11-29 00:39:47 +0000443 DOUT << " +" << LR << '\n';
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000444}
445
Chris Lattnerf35fef72004-07-23 21:24:19 +0000446void LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB,
447 MachineBasicBlock::iterator MI,
Chris Lattner6b128bd2006-09-03 08:07:11 +0000448 unsigned MIIdx,
Chris Lattnerf35fef72004-07-23 21:24:19 +0000449 unsigned reg) {
Dan Gohman6f0d0242008-02-10 18:45:23 +0000450 if (TargetRegisterInfo::isVirtualRegister(reg))
Chris Lattner6b128bd2006-09-03 08:07:11 +0000451 handleVirtualRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg));
Alkis Evlogimenos53278012004-08-26 22:22:38 +0000452 else if (allocatableRegs_[reg]) {
Evan Chengc8d044e2008-02-15 18:24:29 +0000453 MachineInstr *CopyMI = NULL;
Chris Lattner91725b72006-08-31 05:54:43 +0000454 unsigned SrcReg, DstReg;
Evan Chengc8d044e2008-02-15 18:24:29 +0000455 if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG ||
456 tii_->isMoveInstr(*MI, SrcReg, DstReg))
457 CopyMI = MI;
458 handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), CopyMI);
Evan Cheng24a3cc42007-04-25 07:30:23 +0000459 // Def of a register also defines its sub-registers.
Dan Gohman6f0d0242008-02-10 18:45:23 +0000460 for (const unsigned* AS = tri_->getSubRegisters(reg); *AS; ++AS)
Evan Cheng24a3cc42007-04-25 07:30:23 +0000461 // Avoid processing some defs more than once.
462 if (!MI->findRegisterDefOperand(*AS))
463 handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(*AS), 0);
Chris Lattnerf35fef72004-07-23 21:24:19 +0000464 }
Alkis Evlogimenos4d46e1e2004-01-31 14:37:41 +0000465}
466
Evan Chengb371f452007-02-19 21:49:54 +0000467void LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB,
Jim Laskey9b25b8c2007-02-21 22:41:17 +0000468 unsigned MIIdx,
Evan Cheng24a3cc42007-04-25 07:30:23 +0000469 LiveInterval &interval, bool isAlias) {
Evan Chengb371f452007-02-19 21:49:54 +0000470 DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg));
471
472 // Look for kills, if it reaches a def before it's killed, then it shouldn't
473 // be considered a livein.
474 MachineBasicBlock::iterator mi = MBB->begin();
Jim Laskey9b25b8c2007-02-21 22:41:17 +0000475 unsigned baseIndex = MIIdx;
476 unsigned start = baseIndex;
Evan Chengb371f452007-02-19 21:49:54 +0000477 unsigned end = start;
478 while (mi != MBB->end()) {
479 if (lv_->KillsRegister(mi, interval.reg)) {
480 DOUT << " killed";
481 end = getUseIndex(baseIndex) + 1;
482 goto exit;
483 } else if (lv_->ModifiesRegister(mi, interval.reg)) {
484 // Another instruction redefines the register before it is ever read.
485 // Then the register is essentially dead at the instruction that defines
486 // it. Hence its interval is:
487 // [defSlot(def), defSlot(def)+1)
488 DOUT << " dead";
489 end = getDefIndex(start) + 1;
490 goto exit;
491 }
492
493 baseIndex += InstrSlots::NUM;
494 ++mi;
495 }
496
497exit:
Evan Cheng75611fb2007-06-27 01:16:36 +0000498 // Live-in register might not be used at all.
499 if (end == MIIdx) {
Evan Cheng292da942007-06-27 18:47:28 +0000500 if (isAlias) {
501 DOUT << " dead";
Evan Cheng75611fb2007-06-27 01:16:36 +0000502 end = getDefIndex(MIIdx) + 1;
Evan Cheng292da942007-06-27 18:47:28 +0000503 } else {
504 DOUT << " live through";
505 end = baseIndex;
506 }
Evan Cheng24a3cc42007-04-25 07:30:23 +0000507 }
508
Evan Chengf3bb2e62007-09-05 21:46:51 +0000509 LiveRange LR(start, end, interval.getNextValue(start, 0, VNInfoAllocator));
Jim Laskey9b25b8c2007-02-21 22:41:17 +0000510 interval.addRange(LR);
Evan Chengf3bb2e62007-09-05 21:46:51 +0000511 interval.addKill(LR.valno, end);
Evan Cheng24c2e5c2007-08-08 07:03:29 +0000512 DOUT << " +" << LR << '\n';
Evan Chengb371f452007-02-19 21:49:54 +0000513}
514
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000515/// computeIntervals - computes the live intervals for virtual
Alkis Evlogimenos4d46e1e2004-01-31 14:37:41 +0000516/// registers. for some ordering of the machine instructions [1,N] a
Alkis Evlogimenos08cec002004-01-31 19:59:32 +0000517/// live interval is an interval [i, j) where 1 <= i <= j < N for
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000518/// which a variable is live
Chris Lattnerf7da2c72006-08-24 22:43:55 +0000519void LiveIntervals::computeIntervals() {
Bill Wendlingbdc679d2006-11-29 00:39:47 +0000520 DOUT << "********** COMPUTING LIVE INTERVALS **********\n"
521 << "********** Function: "
522 << ((Value*)mf_->getFunction())->getName() << '\n';
Chris Lattner6b128bd2006-09-03 08:07:11 +0000523 // Track the index of the current machine instr.
524 unsigned MIIndex = 0;
Chris Lattner428b92e2006-09-15 03:57:23 +0000525 for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end();
526 MBBI != E; ++MBBI) {
527 MachineBasicBlock *MBB = MBBI;
Bill Wendlingbdc679d2006-11-29 00:39:47 +0000528 DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n";
Alkis Evlogimenos6b4edba2003-12-21 20:19:10 +0000529
Chris Lattner428b92e2006-09-15 03:57:23 +0000530 MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end();
Evan Cheng0c9f92e2007-02-13 01:30:55 +0000531
Dan Gohmancb406c22007-10-03 19:26:29 +0000532 // Create intervals for live-ins to this BB first.
533 for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(),
534 LE = MBB->livein_end(); LI != LE; ++LI) {
535 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI));
536 // Multiple live-ins can alias the same register.
Dan Gohman6f0d0242008-02-10 18:45:23 +0000537 for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS)
Dan Gohmancb406c22007-10-03 19:26:29 +0000538 if (!hasInterval(*AS))
539 handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS),
540 true);
Chris Lattnerdffb2e82006-09-04 18:27:40 +0000541 }
542
Chris Lattner428b92e2006-09-15 03:57:23 +0000543 for (; MI != miEnd; ++MI) {
Bill Wendlingbdc679d2006-11-29 00:39:47 +0000544 DOUT << MIIndex << "\t" << *MI;
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000545
Evan Cheng438f7bc2006-11-10 08:43:01 +0000546 // Handle defs.
Chris Lattner428b92e2006-09-15 03:57:23 +0000547 for (int i = MI->getNumOperands() - 1; i >= 0; --i) {
548 MachineOperand &MO = MI->getOperand(i);
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000549 // handle register defs - build intervals
Chris Lattner428b92e2006-09-15 03:57:23 +0000550 if (MO.isRegister() && MO.getReg() && MO.isDef())
551 handleRegisterDef(MBB, MI, MIIndex, MO.getReg());
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000552 }
Chris Lattner6b128bd2006-09-03 08:07:11 +0000553
554 MIIndex += InstrSlots::NUM;
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000555 }
Alkis Evlogimenos1a8ea012004-08-04 09:46:26 +0000556 }
Alkis Evlogimenosff0cbe12003-11-20 03:32:25 +0000557}
Alkis Evlogimenosb27ef242003-12-05 10:38:28 +0000558
Evan Cheng4ca980e2007-10-17 02:10:22 +0000559bool LiveIntervals::findLiveInMBBs(const LiveRange &LR,
Evan Chenga5bfc972007-10-17 06:53:44 +0000560 SmallVectorImpl<MachineBasicBlock*> &MBBs) const {
Evan Cheng4ca980e2007-10-17 02:10:22 +0000561 std::vector<IdxMBBPair>::const_iterator I =
562 std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), LR.start);
563
564 bool ResVal = false;
565 while (I != Idx2MBBMap.end()) {
566 if (LR.end <= I->first)
567 break;
568 MBBs.push_back(I->second);
569 ResVal = true;
570 ++I;
571 }
572 return ResVal;
573}
574
575
Alkis Evlogimenosa1613db2004-07-24 11:44:15 +0000576LiveInterval LiveIntervals::createInterval(unsigned reg) {
Dan Gohman6f0d0242008-02-10 18:45:23 +0000577 float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ?
Jim Laskey7902c752006-11-07 12:25:45 +0000578 HUGE_VALF : 0.0F;
Alkis Evlogimenosa1613db2004-07-24 11:44:15 +0000579 return LiveInterval(reg, Weight);
Alkis Evlogimenos9a8b4902004-04-09 18:07:57 +0000580}
Evan Chengf2fbca62007-11-12 06:35:08 +0000581
Evan Chengc8d044e2008-02-15 18:24:29 +0000582/// getVNInfoSourceReg - Helper function that parses the specified VNInfo
583/// copy field and returns the source register that defines it.
584unsigned LiveIntervals::getVNInfoSourceReg(const VNInfo *VNI) const {
585 if (!VNI->copy)
586 return 0;
587
588 if (VNI->copy->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)
589 return VNI->copy->getOperand(1).getReg();
590 unsigned SrcReg, DstReg;
591 if (tii_->isMoveInstr(*VNI->copy, SrcReg, DstReg))
592 return SrcReg;
593 assert(0 && "Unrecognized copy instruction!");
594 return 0;
595}
Evan Chengf2fbca62007-11-12 06:35:08 +0000596
597//===----------------------------------------------------------------------===//
598// Register allocator hooks.
599//
600
601/// isReMaterializable - Returns true if the definition MI of the specified
602/// val# of the specified interval is re-materializable.
603bool LiveIntervals::isReMaterializable(const LiveInterval &li,
Evan Cheng5ef3a042007-12-06 00:01:56 +0000604 const VNInfo *ValNo, MachineInstr *MI,
605 bool &isLoad) {
Evan Chengf2fbca62007-11-12 06:35:08 +0000606 if (DisableReMat)
607 return false;
608
Evan Cheng5ef3a042007-12-06 00:01:56 +0000609 isLoad = false;
Chris Lattner749c6f62008-01-07 07:27:27 +0000610 const TargetInstrDesc &TID = MI->getDesc();
611 if (TID.isImplicitDef() || tii_->isTriviallyReMaterializable(MI)) {
612 isLoad = TID.isSimpleLoad();
Evan Chengf2fbca62007-11-12 06:35:08 +0000613 return true;
Evan Cheng5ef3a042007-12-06 00:01:56 +0000614 }
Evan Chengf2fbca62007-11-12 06:35:08 +0000615
616 int FrameIdx = 0;
617 if (!tii_->isLoadFromStackSlot(MI, FrameIdx) ||
Evan Cheng84802932008-01-10 08:24:38 +0000618 !mf_->getFrameInfo()->isImmutableObjectIndex(FrameIdx))
Evan Chengf2fbca62007-11-12 06:35:08 +0000619 return false;
620
621 // This is a load from fixed stack slot. It can be rematerialized unless it's
622 // re-defined by a two-address instruction.
Evan Cheng5ef3a042007-12-06 00:01:56 +0000623 isLoad = true;
Evan Chengf2fbca62007-11-12 06:35:08 +0000624 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
625 i != e; ++i) {
626 const VNInfo *VNI = *i;
627 if (VNI == ValNo)
628 continue;
629 unsigned DefIdx = VNI->def;
630 if (DefIdx == ~1U)
631 continue; // Dead val#.
632 MachineInstr *DefMI = (DefIdx == ~0u)
633 ? NULL : getInstructionFromIndex(DefIdx);
Evan Cheng5ef3a042007-12-06 00:01:56 +0000634 if (DefMI && DefMI->isRegReDefinedByTwoAddr(li.reg)) {
635 isLoad = false;
Evan Chengf2fbca62007-11-12 06:35:08 +0000636 return false;
Evan Cheng5ef3a042007-12-06 00:01:56 +0000637 }
638 }
639 return true;
640}
641
642/// isReMaterializable - Returns true if every definition of MI of every
643/// val# of the specified interval is re-materializable.
644bool LiveIntervals::isReMaterializable(const LiveInterval &li, bool &isLoad) {
645 isLoad = false;
646 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
647 i != e; ++i) {
648 const VNInfo *VNI = *i;
649 unsigned DefIdx = VNI->def;
650 if (DefIdx == ~1U)
651 continue; // Dead val#.
652 // Is the def for the val# rematerializable?
653 if (DefIdx == ~0u)
654 return false;
655 MachineInstr *ReMatDefMI = getInstructionFromIndex(DefIdx);
656 bool DefIsLoad = false;
657 if (!ReMatDefMI || !isReMaterializable(li, VNI, ReMatDefMI, DefIsLoad))
658 return false;
659 isLoad |= DefIsLoad;
Evan Chengf2fbca62007-11-12 06:35:08 +0000660 }
661 return true;
662}
663
664/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from
665/// slot / to reg or any rematerialized load into ith operand of specified
666/// MI. If it is successul, MI is updated with the newly created MI and
667/// returns true.
Evan Cheng81a03822007-11-17 00:40:40 +0000668bool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI,
Evan Chengcddbb832007-11-30 21:23:43 +0000669 VirtRegMap &vrm, MachineInstr *DefMI,
Evan Chengaee4af62007-12-02 08:30:39 +0000670 unsigned InstrIdx,
671 SmallVector<unsigned, 2> &Ops,
Evan Chengcddbb832007-11-30 21:23:43 +0000672 bool isSS, int Slot, unsigned Reg) {
Evan Chengaee4af62007-12-02 08:30:39 +0000673 unsigned MRInfo = 0;
Chris Lattner749c6f62008-01-07 07:27:27 +0000674 const TargetInstrDesc &TID = MI->getDesc();
Evan Cheng6e141fd2007-12-12 23:12:09 +0000675 // If it is an implicit def instruction, just delete it.
Chris Lattner749c6f62008-01-07 07:27:27 +0000676 if (TID.isImplicitDef()) {
Evan Cheng6e141fd2007-12-12 23:12:09 +0000677 RemoveMachineInstrFromMaps(MI);
678 vrm.RemoveMachineInstrFromMaps(MI);
679 MI->eraseFromParent();
680 ++numFolds;
681 return true;
682 }
683
Evan Chengaee4af62007-12-02 08:30:39 +0000684 SmallVector<unsigned, 2> FoldOps;
685 for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
686 unsigned OpIdx = Ops[i];
687 // FIXME: fold subreg use.
688 if (MI->getOperand(OpIdx).getSubReg())
Evan Chenge62f97c2007-12-01 02:07:52 +0000689 return false;
Evan Chengaee4af62007-12-02 08:30:39 +0000690 if (MI->getOperand(OpIdx).isDef())
691 MRInfo |= (unsigned)VirtRegMap::isMod;
692 else {
693 // Filter out two-address use operand(s).
Chris Lattner749c6f62008-01-07 07:27:27 +0000694 if (TID.getOperandConstraint(OpIdx, TOI::TIED_TO) != -1) {
Evan Chengaee4af62007-12-02 08:30:39 +0000695 MRInfo = VirtRegMap::isModRef;
696 continue;
697 }
698 MRInfo |= (unsigned)VirtRegMap::isRef;
699 }
700 FoldOps.push_back(OpIdx);
Evan Chenge62f97c2007-12-01 02:07:52 +0000701 }
702
Evan Chengf2f8c2a2008-02-08 22:05:27 +0000703 MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot)
704 : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI);
Evan Chengf2fbca62007-11-12 06:35:08 +0000705 if (fmi) {
706 // Attempt to fold the memory reference into the instruction. If
707 // we can do this, we don't need to insert spill code.
708 if (lv_)
709 lv_->instructionChanged(MI, fmi);
Evan Cheng81a03822007-11-17 00:40:40 +0000710 else
Dan Gohman6f0d0242008-02-10 18:45:23 +0000711 fmi->copyKillDeadInfo(MI, tri_);
Evan Chengf2fbca62007-11-12 06:35:08 +0000712 MachineBasicBlock &MBB = *MI->getParent();
Evan Cheng84802932008-01-10 08:24:38 +0000713 if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot))
Evan Chengaee4af62007-12-02 08:30:39 +0000714 vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo);
Evan Cheng81a03822007-11-17 00:40:40 +0000715 vrm.transferSpillPts(MI, fmi);
Evan Cheng0cbb1162007-11-29 01:06:25 +0000716 vrm.transferRestorePts(MI, fmi);
Evan Chengf2fbca62007-11-12 06:35:08 +0000717 mi2iMap_.erase(MI);
Evan Chengcddbb832007-11-30 21:23:43 +0000718 i2miMap_[InstrIdx /InstrSlots::NUM] = fmi;
719 mi2iMap_[fmi] = InstrIdx;
Evan Chengf2fbca62007-11-12 06:35:08 +0000720 MI = MBB.insert(MBB.erase(MI), fmi);
Evan Cheng0cbb1162007-11-29 01:06:25 +0000721 ++numFolds;
Evan Chengf2fbca62007-11-12 06:35:08 +0000722 return true;
723 }
724 return false;
725}
726
Evan Cheng018f9b02007-12-05 03:22:34 +0000727/// canFoldMemoryOperand - Returns true if the specified load / store
728/// folding is possible.
729bool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI,
730 SmallVector<unsigned, 2> &Ops) const {
731 SmallVector<unsigned, 2> FoldOps;
732 for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
733 unsigned OpIdx = Ops[i];
734 // FIXME: fold subreg use.
735 if (MI->getOperand(OpIdx).getSubReg())
736 return false;
737 FoldOps.push_back(OpIdx);
738 }
739
Owen Anderson6425f8b2008-01-07 01:35:56 +0000740 return tii_->canFoldMemoryOperand(MI, FoldOps);
Evan Cheng018f9b02007-12-05 03:22:34 +0000741}
742
Evan Cheng81a03822007-11-17 00:40:40 +0000743bool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const {
744 SmallPtrSet<MachineBasicBlock*, 4> MBBs;
745 for (LiveInterval::Ranges::const_iterator
746 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
747 std::vector<IdxMBBPair>::const_iterator II =
748 std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), I->start);
749 if (II == Idx2MBBMap.end())
750 continue;
751 if (I->end > II->first) // crossing a MBB.
752 return false;
753 MBBs.insert(II->second);
754 if (MBBs.size() > 1)
755 return false;
756 }
757 return true;
758}
759
Evan Chengf2fbca62007-11-12 06:35:08 +0000760/// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions
761/// for addIntervalsForSpills to rewrite uses / defs for the given live range.
Evan Cheng018f9b02007-12-05 03:22:34 +0000762bool LiveIntervals::
Evan Cheng81a03822007-11-17 00:40:40 +0000763rewriteInstructionForSpills(const LiveInterval &li, bool TrySplit,
764 unsigned id, unsigned index, unsigned end, MachineInstr *MI,
765 MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
Evan Chengf2fbca62007-11-12 06:35:08 +0000766 unsigned Slot, int LdSlot,
767 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
Chris Lattner84bc5422007-12-31 04:13:23 +0000768 VirtRegMap &vrm, MachineRegisterInfo &RegInfo,
Evan Chengf2fbca62007-11-12 06:35:08 +0000769 const TargetRegisterClass* rc,
770 SmallVector<int, 4> &ReMatIds,
Evan Cheng81a03822007-11-17 00:40:40 +0000771 unsigned &NewVReg, bool &HasDef, bool &HasUse,
Evan Cheng22f07ff2007-12-11 02:09:15 +0000772 const MachineLoopInfo *loopInfo,
Evan Cheng1953d0c2007-11-29 10:12:14 +0000773 std::map<unsigned,unsigned> &MBBVRegsMap,
Evan Chengf2fbca62007-11-12 06:35:08 +0000774 std::vector<LiveInterval*> &NewLIs) {
Evan Cheng018f9b02007-12-05 03:22:34 +0000775 bool CanFold = false;
Evan Chengf2fbca62007-11-12 06:35:08 +0000776 RestartInstruction:
777 for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
778 MachineOperand& mop = MI->getOperand(i);
779 if (!mop.isRegister())
780 continue;
781 unsigned Reg = mop.getReg();
782 unsigned RegI = Reg;
Dan Gohman6f0d0242008-02-10 18:45:23 +0000783 if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg))
Evan Chengf2fbca62007-11-12 06:35:08 +0000784 continue;
Evan Chengf2fbca62007-11-12 06:35:08 +0000785 if (Reg != li.reg)
786 continue;
787
788 bool TryFold = !DefIsReMat;
Evan Chengcb3c3302007-11-29 23:02:50 +0000789 bool FoldSS = true; // Default behavior unless it's a remat.
Evan Chengf2fbca62007-11-12 06:35:08 +0000790 int FoldSlot = Slot;
791 if (DefIsReMat) {
792 // If this is the rematerializable definition MI itself and
793 // all of its uses are rematerialized, simply delete it.
Evan Cheng81a03822007-11-17 00:40:40 +0000794 if (MI == ReMatOrigDefMI && CanDelete) {
Evan Chengcddbb832007-11-30 21:23:43 +0000795 DOUT << "\t\t\t\tErasing re-materlizable def: ";
796 DOUT << MI << '\n';
Evan Chengf2fbca62007-11-12 06:35:08 +0000797 RemoveMachineInstrFromMaps(MI);
Evan Chengcada2452007-11-28 01:28:46 +0000798 vrm.RemoveMachineInstrFromMaps(MI);
Evan Chengf2fbca62007-11-12 06:35:08 +0000799 MI->eraseFromParent();
800 break;
801 }
802
803 // If def for this use can't be rematerialized, then try folding.
Evan Cheng0cbb1162007-11-29 01:06:25 +0000804 // If def is rematerializable and it's a load, also try folding.
Evan Chengcb3c3302007-11-29 23:02:50 +0000805 TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad));
Evan Chengf2fbca62007-11-12 06:35:08 +0000806 if (isLoad) {
807 // Try fold loads (from stack slot, constant pool, etc.) into uses.
808 FoldSS = isLoadSS;
809 FoldSlot = LdSlot;
810 }
811 }
812
Evan Chengf2fbca62007-11-12 06:35:08 +0000813 // Scan all of the operands of this instruction rewriting operands
814 // to use NewVReg instead of li.reg as appropriate. We do this for
815 // two reasons:
816 //
817 // 1. If the instr reads the same spilled vreg multiple times, we
818 // want to reuse the NewVReg.
819 // 2. If the instr is a two-addr instruction, we are required to
820 // keep the src/dst regs pinned.
821 //
822 // Keep track of whether we replace a use and/or def so that we can
823 // create the spill interval with the appropriate range.
Evan Chengcddbb832007-11-30 21:23:43 +0000824
Evan Cheng81a03822007-11-17 00:40:40 +0000825 HasUse = mop.isUse();
826 HasDef = mop.isDef();
Evan Chengaee4af62007-12-02 08:30:39 +0000827 SmallVector<unsigned, 2> Ops;
828 Ops.push_back(i);
Evan Chengf2fbca62007-11-12 06:35:08 +0000829 for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) {
Evan Chengaee4af62007-12-02 08:30:39 +0000830 const MachineOperand &MOj = MI->getOperand(j);
831 if (!MOj.isRegister())
Evan Chengf2fbca62007-11-12 06:35:08 +0000832 continue;
Evan Chengaee4af62007-12-02 08:30:39 +0000833 unsigned RegJ = MOj.getReg();
Dan Gohman6f0d0242008-02-10 18:45:23 +0000834 if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ))
Evan Chengf2fbca62007-11-12 06:35:08 +0000835 continue;
836 if (RegJ == RegI) {
Evan Chengaee4af62007-12-02 08:30:39 +0000837 Ops.push_back(j);
838 HasUse |= MOj.isUse();
839 HasDef |= MOj.isDef();
Evan Chengf2fbca62007-11-12 06:35:08 +0000840 }
841 }
842
Evan Cheng018f9b02007-12-05 03:22:34 +0000843 if (TryFold) {
844 // Do not fold load / store here if we are splitting. We'll find an
845 // optimal point to insert a load / store later.
846 if (!TrySplit) {
847 if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
848 Ops, FoldSS, FoldSlot, Reg)) {
849 // Folding the load/store can completely change the instruction in
850 // unpredictable ways, rescan it from the beginning.
851 HasUse = false;
852 HasDef = false;
853 CanFold = false;
854 goto RestartInstruction;
855 }
856 } else {
857 CanFold = canFoldMemoryOperand(MI, Ops);
858 }
Evan Cheng6e141fd2007-12-12 23:12:09 +0000859 } else
860 CanFold = false;
Evan Chengcddbb832007-11-30 21:23:43 +0000861
862 // Create a new virtual register for the spill interval.
863 bool CreatedNewVReg = false;
864 if (NewVReg == 0) {
Chris Lattner84bc5422007-12-31 04:13:23 +0000865 NewVReg = RegInfo.createVirtualRegister(rc);
Evan Chengcddbb832007-11-30 21:23:43 +0000866 vrm.grow();
867 CreatedNewVReg = true;
868 }
869 mop.setReg(NewVReg);
870
871 // Reuse NewVReg for other reads.
Evan Chengaee4af62007-12-02 08:30:39 +0000872 for (unsigned j = 0, e = Ops.size(); j != e; ++j)
873 MI->getOperand(Ops[j]).setReg(NewVReg);
Evan Chengcddbb832007-11-30 21:23:43 +0000874
Evan Cheng81a03822007-11-17 00:40:40 +0000875 if (CreatedNewVReg) {
876 if (DefIsReMat) {
877 vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI/*, CanDelete*/);
878 if (ReMatIds[id] == VirtRegMap::MAX_STACK_SLOT) {
879 // Each valnum may have its own remat id.
880 ReMatIds[id] = vrm.assignVirtReMatId(NewVReg);
881 } else {
882 vrm.assignVirtReMatId(NewVReg, ReMatIds[id]);
883 }
884 if (!CanDelete || (HasUse && HasDef)) {
885 // If this is a two-addr instruction then its use operands are
886 // rematerializable but its def is not. It should be assigned a
887 // stack slot.
888 vrm.assignVirt2StackSlot(NewVReg, Slot);
889 }
Evan Chengf2fbca62007-11-12 06:35:08 +0000890 } else {
Evan Chengf2fbca62007-11-12 06:35:08 +0000891 vrm.assignVirt2StackSlot(NewVReg, Slot);
892 }
Evan Chengcb3c3302007-11-29 23:02:50 +0000893 } else if (HasUse && HasDef &&
894 vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) {
895 // If this interval hasn't been assigned a stack slot (because earlier
896 // def is a deleted remat def), do it now.
897 assert(Slot != VirtRegMap::NO_STACK_SLOT);
898 vrm.assignVirt2StackSlot(NewVReg, Slot);
Evan Chengf2fbca62007-11-12 06:35:08 +0000899 }
900
901 // create a new register interval for this spill / remat.
902 LiveInterval &nI = getOrCreateInterval(NewVReg);
Evan Cheng81a03822007-11-17 00:40:40 +0000903 if (CreatedNewVReg) {
904 NewLIs.push_back(&nI);
Evan Cheng1953d0c2007-11-29 10:12:14 +0000905 MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg));
Evan Cheng81a03822007-11-17 00:40:40 +0000906 if (TrySplit)
907 vrm.setIsSplitFromReg(NewVReg, li.reg);
908 }
Evan Chengf2fbca62007-11-12 06:35:08 +0000909
910 if (HasUse) {
Evan Cheng81a03822007-11-17 00:40:40 +0000911 if (CreatedNewVReg) {
912 LiveRange LR(getLoadIndex(index), getUseIndex(index)+1,
913 nI.getNextValue(~0U, 0, VNInfoAllocator));
914 DOUT << " +" << LR;
915 nI.addRange(LR);
916 } else {
917 // Extend the split live interval to this def / use.
918 unsigned End = getUseIndex(index)+1;
919 LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End,
920 nI.getValNumInfo(nI.getNumValNums()-1));
921 DOUT << " +" << LR;
922 nI.addRange(LR);
923 }
Evan Chengf2fbca62007-11-12 06:35:08 +0000924 }
925 if (HasDef) {
926 LiveRange LR(getDefIndex(index), getStoreIndex(index),
927 nI.getNextValue(~0U, 0, VNInfoAllocator));
928 DOUT << " +" << LR;
929 nI.addRange(LR);
930 }
Evan Cheng81a03822007-11-17 00:40:40 +0000931
Evan Chengf2fbca62007-11-12 06:35:08 +0000932 DOUT << "\t\t\t\tAdded new interval: ";
Dan Gohman6f0d0242008-02-10 18:45:23 +0000933 nI.print(DOUT, tri_);
Evan Chengf2fbca62007-11-12 06:35:08 +0000934 DOUT << '\n';
935 }
Evan Cheng018f9b02007-12-05 03:22:34 +0000936 return CanFold;
Evan Chengf2fbca62007-11-12 06:35:08 +0000937}
Evan Cheng81a03822007-11-17 00:40:40 +0000938bool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li,
Evan Cheng0cbb1162007-11-29 01:06:25 +0000939 const VNInfo *VNI,
940 MachineBasicBlock *MBB, unsigned Idx) const {
Evan Cheng81a03822007-11-17 00:40:40 +0000941 unsigned End = getMBBEndIdx(MBB);
Evan Cheng0cbb1162007-11-29 01:06:25 +0000942 for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) {
943 unsigned KillIdx = VNI->kills[j];
944 if (KillIdx > Idx && KillIdx < End)
945 return true;
Evan Cheng81a03822007-11-17 00:40:40 +0000946 }
947 return false;
948}
949
Evan Cheng1953d0c2007-11-29 10:12:14 +0000950static const VNInfo *findDefinedVNInfo(const LiveInterval &li, unsigned DefIdx) {
951 const VNInfo *VNI = NULL;
952 for (LiveInterval::const_vni_iterator i = li.vni_begin(),
953 e = li.vni_end(); i != e; ++i)
954 if ((*i)->def == DefIdx) {
955 VNI = *i;
956 break;
957 }
958 return VNI;
959}
960
Evan Chengf2fbca62007-11-12 06:35:08 +0000961void LiveIntervals::
Evan Cheng81a03822007-11-17 00:40:40 +0000962rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit,
Evan Chengf2fbca62007-11-12 06:35:08 +0000963 LiveInterval::Ranges::const_iterator &I,
Evan Cheng81a03822007-11-17 00:40:40 +0000964 MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI,
Evan Chengf2fbca62007-11-12 06:35:08 +0000965 unsigned Slot, int LdSlot,
966 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete,
Chris Lattner84bc5422007-12-31 04:13:23 +0000967 VirtRegMap &vrm, MachineRegisterInfo &RegInfo,
Evan Chengf2fbca62007-11-12 06:35:08 +0000968 const TargetRegisterClass* rc,
969 SmallVector<int, 4> &ReMatIds,
Evan Cheng22f07ff2007-12-11 02:09:15 +0000970 const MachineLoopInfo *loopInfo,
Evan Cheng81a03822007-11-17 00:40:40 +0000971 BitVector &SpillMBBs,
Evan Cheng1953d0c2007-11-29 10:12:14 +0000972 std::map<unsigned, std::vector<SRInfo> > &SpillIdxes,
Evan Cheng0cbb1162007-11-29 01:06:25 +0000973 BitVector &RestoreMBBs,
Evan Cheng1953d0c2007-11-29 10:12:14 +0000974 std::map<unsigned, std::vector<SRInfo> > &RestoreIdxes,
975 std::map<unsigned,unsigned> &MBBVRegsMap,
Evan Chengf2fbca62007-11-12 06:35:08 +0000976 std::vector<LiveInterval*> &NewLIs) {
Evan Cheng018f9b02007-12-05 03:22:34 +0000977 bool AllCanFold = true;
Evan Cheng81a03822007-11-17 00:40:40 +0000978 unsigned NewVReg = 0;
Evan Chengf2fbca62007-11-12 06:35:08 +0000979 unsigned index = getBaseIndex(I->start);
980 unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM;
981 for (; index != end; index += InstrSlots::NUM) {
982 // skip deleted instructions
983 while (index != end && !getInstructionFromIndex(index))
984 index += InstrSlots::NUM;
985 if (index == end) break;
986
987 MachineInstr *MI = getInstructionFromIndex(index);
Evan Cheng81a03822007-11-17 00:40:40 +0000988 MachineBasicBlock *MBB = MI->getParent();
Evan Cheng018f9b02007-12-05 03:22:34 +0000989 unsigned ThisVReg = 0;
Evan Cheng70306f82007-12-03 09:58:48 +0000990 if (TrySplit) {
Evan Chengcada2452007-11-28 01:28:46 +0000991 std::map<unsigned,unsigned>::const_iterator NVI =
Evan Cheng1953d0c2007-11-29 10:12:14 +0000992 MBBVRegsMap.find(MBB->getNumber());
993 if (NVI != MBBVRegsMap.end()) {
Evan Cheng018f9b02007-12-05 03:22:34 +0000994 ThisVReg = NVI->second;
Evan Cheng1953d0c2007-11-29 10:12:14 +0000995 // One common case:
996 // x = use
997 // ...
998 // ...
999 // def = ...
1000 // = use
1001 // It's better to start a new interval to avoid artifically
1002 // extend the new interval.
1003 // FIXME: Too slow? Can we fix it after rewriteInstructionsForSpills?
1004 bool MIHasUse = false;
1005 bool MIHasDef = false;
1006 for (unsigned i = 0; i != MI->getNumOperands(); ++i) {
1007 MachineOperand& mop = MI->getOperand(i);
1008 if (!mop.isRegister() || mop.getReg() != li.reg)
1009 continue;
1010 if (mop.isUse())
1011 MIHasUse = true;
1012 else
1013 MIHasDef = true;
1014 }
1015 if (MIHasDef && !MIHasUse) {
1016 MBBVRegsMap.erase(MBB->getNumber());
Evan Cheng018f9b02007-12-05 03:22:34 +00001017 ThisVReg = 0;
Evan Cheng1953d0c2007-11-29 10:12:14 +00001018 }
1019 }
Evan Chengcada2452007-11-28 01:28:46 +00001020 }
Evan Cheng018f9b02007-12-05 03:22:34 +00001021
1022 bool IsNew = ThisVReg == 0;
1023 if (IsNew) {
1024 // This ends the previous live interval. If all of its def / use
1025 // can be folded, give it a low spill weight.
1026 if (NewVReg && TrySplit && AllCanFold) {
1027 LiveInterval &nI = getOrCreateInterval(NewVReg);
1028 nI.weight /= 10.0F;
1029 }
1030 AllCanFold = true;
1031 }
1032 NewVReg = ThisVReg;
1033
Evan Cheng81a03822007-11-17 00:40:40 +00001034 bool HasDef = false;
1035 bool HasUse = false;
Evan Cheng018f9b02007-12-05 03:22:34 +00001036 bool CanFold = rewriteInstructionForSpills(li, TrySplit, I->valno->id,
1037 index, end, MI, ReMatOrigDefMI, ReMatDefMI,
1038 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
Chris Lattner84bc5422007-12-31 04:13:23 +00001039 CanDelete, vrm, RegInfo, rc, ReMatIds, NewVReg,
Evan Cheng018f9b02007-12-05 03:22:34 +00001040 HasDef, HasUse, loopInfo, MBBVRegsMap, NewLIs);
Evan Cheng81a03822007-11-17 00:40:40 +00001041 if (!HasDef && !HasUse)
1042 continue;
1043
Evan Cheng018f9b02007-12-05 03:22:34 +00001044 AllCanFold &= CanFold;
1045
Evan Cheng81a03822007-11-17 00:40:40 +00001046 // Update weight of spill interval.
1047 LiveInterval &nI = getOrCreateInterval(NewVReg);
Evan Cheng70306f82007-12-03 09:58:48 +00001048 if (!TrySplit) {
Evan Cheng81a03822007-11-17 00:40:40 +00001049 // The spill weight is now infinity as it cannot be spilled again.
1050 nI.weight = HUGE_VALF;
Evan Cheng0cbb1162007-11-29 01:06:25 +00001051 continue;
Evan Cheng81a03822007-11-17 00:40:40 +00001052 }
Evan Cheng0cbb1162007-11-29 01:06:25 +00001053
1054 // Keep track of the last def and first use in each MBB.
1055 unsigned MBBId = MBB->getNumber();
1056 if (HasDef) {
1057 if (MI != ReMatOrigDefMI || !CanDelete) {
Evan Cheng0cbb1162007-11-29 01:06:25 +00001058 bool HasKill = false;
1059 if (!HasUse)
1060 HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index));
1061 else {
Evan Cheng1953d0c2007-11-29 10:12:14 +00001062 // If this is a two-address code, then this index starts a new VNInfo.
1063 const VNInfo *VNI = findDefinedVNInfo(li, getDefIndex(index));
Evan Cheng0cbb1162007-11-29 01:06:25 +00001064 if (VNI)
1065 HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index));
1066 }
Evan Chenge3110d02007-12-01 04:42:39 +00001067 std::map<unsigned, std::vector<SRInfo> >::iterator SII =
1068 SpillIdxes.find(MBBId);
Evan Cheng0cbb1162007-11-29 01:06:25 +00001069 if (!HasKill) {
Evan Cheng1953d0c2007-11-29 10:12:14 +00001070 if (SII == SpillIdxes.end()) {
1071 std::vector<SRInfo> S;
1072 S.push_back(SRInfo(index, NewVReg, true));
1073 SpillIdxes.insert(std::make_pair(MBBId, S));
1074 } else if (SII->second.back().vreg != NewVReg) {
1075 SII->second.push_back(SRInfo(index, NewVReg, true));
1076 } else if ((int)index > SII->second.back().index) {
Evan Cheng0cbb1162007-11-29 01:06:25 +00001077 // If there is an earlier def and this is a two-address
1078 // instruction, then it's not possible to fold the store (which
1079 // would also fold the load).
Evan Cheng1953d0c2007-11-29 10:12:14 +00001080 SRInfo &Info = SII->second.back();
1081 Info.index = index;
1082 Info.canFold = !HasUse;
Evan Cheng0cbb1162007-11-29 01:06:25 +00001083 }
1084 SpillMBBs.set(MBBId);
Evan Chenge3110d02007-12-01 04:42:39 +00001085 } else if (SII != SpillIdxes.end() &&
1086 SII->second.back().vreg == NewVReg &&
1087 (int)index > SII->second.back().index) {
1088 // There is an earlier def that's not killed (must be two-address).
1089 // The spill is no longer needed.
1090 SII->second.pop_back();
1091 if (SII->second.empty()) {
1092 SpillIdxes.erase(MBBId);
1093 SpillMBBs.reset(MBBId);
1094 }
Evan Cheng0cbb1162007-11-29 01:06:25 +00001095 }
1096 }
Evan Cheng0cbb1162007-11-29 01:06:25 +00001097 }
1098
1099 if (HasUse) {
Evan Cheng1953d0c2007-11-29 10:12:14 +00001100 std::map<unsigned, std::vector<SRInfo> >::iterator SII =
Evan Cheng0cbb1162007-11-29 01:06:25 +00001101 SpillIdxes.find(MBBId);
Evan Cheng1953d0c2007-11-29 10:12:14 +00001102 if (SII != SpillIdxes.end() &&
1103 SII->second.back().vreg == NewVReg &&
1104 (int)index > SII->second.back().index)
Evan Cheng0cbb1162007-11-29 01:06:25 +00001105 // Use(s) following the last def, it's not safe to fold the spill.
Evan Cheng1953d0c2007-11-29 10:12:14 +00001106 SII->second.back().canFold = false;
1107 std::map<unsigned, std::vector<SRInfo> >::iterator RII =
Evan Cheng0cbb1162007-11-29 01:06:25 +00001108 RestoreIdxes.find(MBBId);
Evan Cheng1953d0c2007-11-29 10:12:14 +00001109 if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg)
Evan Cheng0cbb1162007-11-29 01:06:25 +00001110 // If we are splitting live intervals, only fold if it's the first
1111 // use and there isn't another use later in the MBB.
Evan Cheng1953d0c2007-11-29 10:12:14 +00001112 RII->second.back().canFold = false;
Evan Cheng0cbb1162007-11-29 01:06:25 +00001113 else if (IsNew) {
1114 // Only need a reload if there isn't an earlier def / use.
Evan Cheng1953d0c2007-11-29 10:12:14 +00001115 if (RII == RestoreIdxes.end()) {
1116 std::vector<SRInfo> Infos;
1117 Infos.push_back(SRInfo(index, NewVReg, true));
1118 RestoreIdxes.insert(std::make_pair(MBBId, Infos));
1119 } else {
1120 RII->second.push_back(SRInfo(index, NewVReg, true));
1121 }
Evan Cheng0cbb1162007-11-29 01:06:25 +00001122 RestoreMBBs.set(MBBId);
1123 }
1124 }
1125
1126 // Update spill weight.
Evan Cheng22f07ff2007-12-11 02:09:15 +00001127 unsigned loopDepth = loopInfo->getLoopDepth(MBB);
Evan Cheng0cbb1162007-11-29 01:06:25 +00001128 nI.weight += getSpillWeight(HasDef, HasUse, loopDepth);
Evan Chengf2fbca62007-11-12 06:35:08 +00001129 }
Evan Cheng018f9b02007-12-05 03:22:34 +00001130
1131 if (NewVReg && TrySplit && AllCanFold) {
1132 // If all of its def / use can be folded, give it a low spill weight.
1133 LiveInterval &nI = getOrCreateInterval(NewVReg);
1134 nI.weight /= 10.0F;
1135 }
Evan Chengf2fbca62007-11-12 06:35:08 +00001136}
1137
Evan Cheng1953d0c2007-11-29 10:12:14 +00001138bool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr,
1139 BitVector &RestoreMBBs,
1140 std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1141 if (!RestoreMBBs[Id])
1142 return false;
1143 std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1144 for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1145 if (Restores[i].index == index &&
1146 Restores[i].vreg == vr &&
1147 Restores[i].canFold)
1148 return true;
1149 return false;
1150}
1151
1152void LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr,
1153 BitVector &RestoreMBBs,
1154 std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) {
1155 if (!RestoreMBBs[Id])
1156 return;
1157 std::vector<SRInfo> &Restores = RestoreIdxes[Id];
1158 for (unsigned i = 0, e = Restores.size(); i != e; ++i)
1159 if (Restores[i].index == index && Restores[i].vreg)
1160 Restores[i].index = -1;
1161}
Evan Cheng81a03822007-11-17 00:40:40 +00001162
1163
Evan Chengf2fbca62007-11-12 06:35:08 +00001164std::vector<LiveInterval*> LiveIntervals::
Evan Cheng81a03822007-11-17 00:40:40 +00001165addIntervalsForSpills(const LiveInterval &li,
Evan Cheng22f07ff2007-12-11 02:09:15 +00001166 const MachineLoopInfo *loopInfo, VirtRegMap &vrm) {
Evan Chengf2fbca62007-11-12 06:35:08 +00001167 // Since this is called after the analysis is done we don't know if
1168 // LiveVariables is available
1169 lv_ = getAnalysisToUpdate<LiveVariables>();
1170
1171 assert(li.weight != HUGE_VALF &&
1172 "attempt to spill already spilled interval!");
1173
1174 DOUT << "\t\t\t\tadding intervals for spills for interval: ";
Dan Gohman6f0d0242008-02-10 18:45:23 +00001175 li.print(DOUT, tri_);
Evan Chengf2fbca62007-11-12 06:35:08 +00001176 DOUT << '\n';
1177
Evan Cheng81a03822007-11-17 00:40:40 +00001178 // Each bit specify whether it a spill is required in the MBB.
1179 BitVector SpillMBBs(mf_->getNumBlockIDs());
Evan Cheng1953d0c2007-11-29 10:12:14 +00001180 std::map<unsigned, std::vector<SRInfo> > SpillIdxes;
Evan Cheng0cbb1162007-11-29 01:06:25 +00001181 BitVector RestoreMBBs(mf_->getNumBlockIDs());
Evan Cheng1953d0c2007-11-29 10:12:14 +00001182 std::map<unsigned, std::vector<SRInfo> > RestoreIdxes;
1183 std::map<unsigned,unsigned> MBBVRegsMap;
Evan Chengf2fbca62007-11-12 06:35:08 +00001184 std::vector<LiveInterval*> NewLIs;
Chris Lattner84bc5422007-12-31 04:13:23 +00001185 MachineRegisterInfo &RegInfo = mf_->getRegInfo();
1186 const TargetRegisterClass* rc = RegInfo.getRegClass(li.reg);
Evan Chengf2fbca62007-11-12 06:35:08 +00001187
1188 unsigned NumValNums = li.getNumValNums();
1189 SmallVector<MachineInstr*, 4> ReMatDefs;
1190 ReMatDefs.resize(NumValNums, NULL);
1191 SmallVector<MachineInstr*, 4> ReMatOrigDefs;
1192 ReMatOrigDefs.resize(NumValNums, NULL);
1193 SmallVector<int, 4> ReMatIds;
1194 ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT);
1195 BitVector ReMatDelete(NumValNums);
1196 unsigned Slot = VirtRegMap::MAX_STACK_SLOT;
1197
Evan Cheng81a03822007-11-17 00:40:40 +00001198 // Spilling a split live interval. It cannot be split any further. Also,
1199 // it's also guaranteed to be a single val# / range interval.
1200 if (vrm.getPreSplitReg(li.reg)) {
1201 vrm.setIsSplitFromReg(li.reg, 0);
Evan Chengd120ffd2007-12-05 10:24:35 +00001202 // Unset the split kill marker on the last use.
1203 unsigned KillIdx = vrm.getKillPoint(li.reg);
1204 if (KillIdx) {
1205 MachineInstr *KillMI = getInstructionFromIndex(KillIdx);
1206 assert(KillMI && "Last use disappeared?");
1207 int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true);
1208 assert(KillOp != -1 && "Last use disappeared?");
Chris Lattnerf7382302007-12-30 21:56:09 +00001209 KillMI->getOperand(KillOp).setIsKill(false);
Evan Chengd120ffd2007-12-05 10:24:35 +00001210 }
Evan Chengadf85902007-12-05 09:51:10 +00001211 vrm.removeKillPoint(li.reg);
Evan Cheng81a03822007-11-17 00:40:40 +00001212 bool DefIsReMat = vrm.isReMaterialized(li.reg);
1213 Slot = vrm.getStackSlot(li.reg);
1214 assert(Slot != VirtRegMap::MAX_STACK_SLOT);
1215 MachineInstr *ReMatDefMI = DefIsReMat ?
1216 vrm.getReMaterializedMI(li.reg) : NULL;
1217 int LdSlot = 0;
1218 bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1219 bool isLoad = isLoadSS ||
Chris Lattner749c6f62008-01-07 07:27:27 +00001220 (DefIsReMat && (ReMatDefMI->getDesc().isSimpleLoad()));
Evan Cheng81a03822007-11-17 00:40:40 +00001221 bool IsFirstRange = true;
1222 for (LiveInterval::Ranges::const_iterator
1223 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
1224 // If this is a split live interval with multiple ranges, it means there
1225 // are two-address instructions that re-defined the value. Only the
1226 // first def can be rematerialized!
1227 if (IsFirstRange) {
Evan Chengcb3c3302007-11-29 23:02:50 +00001228 // Note ReMatOrigDefMI has already been deleted.
Evan Cheng81a03822007-11-17 00:40:40 +00001229 rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI,
1230 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
Chris Lattner84bc5422007-12-31 04:13:23 +00001231 false, vrm, RegInfo, rc, ReMatIds, loopInfo,
Evan Cheng0cbb1162007-11-29 01:06:25 +00001232 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
Evan Cheng1953d0c2007-11-29 10:12:14 +00001233 MBBVRegsMap, NewLIs);
Evan Cheng81a03822007-11-17 00:40:40 +00001234 } else {
1235 rewriteInstructionsForSpills(li, false, I, NULL, 0,
1236 Slot, 0, false, false, false,
Chris Lattner84bc5422007-12-31 04:13:23 +00001237 false, vrm, RegInfo, rc, ReMatIds, loopInfo,
Evan Cheng0cbb1162007-11-29 01:06:25 +00001238 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
Evan Cheng1953d0c2007-11-29 10:12:14 +00001239 MBBVRegsMap, NewLIs);
Evan Cheng81a03822007-11-17 00:40:40 +00001240 }
1241 IsFirstRange = false;
1242 }
1243 return NewLIs;
1244 }
1245
1246 bool TrySplit = SplitAtBB && !intervalIsInOneMBB(li);
Evan Cheng0cbb1162007-11-29 01:06:25 +00001247 if (SplitLimit != -1 && (int)numSplits >= SplitLimit)
1248 TrySplit = false;
1249 if (TrySplit)
1250 ++numSplits;
Evan Chengf2fbca62007-11-12 06:35:08 +00001251 bool NeedStackSlot = false;
1252 for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end();
1253 i != e; ++i) {
1254 const VNInfo *VNI = *i;
1255 unsigned VN = VNI->id;
1256 unsigned DefIdx = VNI->def;
1257 if (DefIdx == ~1U)
1258 continue; // Dead val#.
1259 // Is the def for the val# rematerializable?
Evan Cheng81a03822007-11-17 00:40:40 +00001260 MachineInstr *ReMatDefMI = (DefIdx == ~0u)
1261 ? 0 : getInstructionFromIndex(DefIdx);
Evan Cheng5ef3a042007-12-06 00:01:56 +00001262 bool dummy;
1263 if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, dummy)) {
Evan Chengf2fbca62007-11-12 06:35:08 +00001264 // Remember how to remat the def of this val#.
Evan Cheng81a03822007-11-17 00:40:40 +00001265 ReMatOrigDefs[VN] = ReMatDefMI;
Evan Chengf2fbca62007-11-12 06:35:08 +00001266 // Original def may be modified so we have to make a copy here. vrm must
1267 // delete these!
Evan Cheng81a03822007-11-17 00:40:40 +00001268 ReMatDefs[VN] = ReMatDefMI = ReMatDefMI->clone();
Evan Chengf2fbca62007-11-12 06:35:08 +00001269
1270 bool CanDelete = true;
Evan Chengc3fc7d92007-11-29 09:49:23 +00001271 if (VNI->hasPHIKill) {
1272 // A kill is a phi node, not all of its uses can be rematerialized.
Evan Chengf2fbca62007-11-12 06:35:08 +00001273 // It must not be deleted.
Evan Chengc3fc7d92007-11-29 09:49:23 +00001274 CanDelete = false;
1275 // Need a stack slot if there is any live range where uses cannot be
1276 // rematerialized.
1277 NeedStackSlot = true;
Evan Chengf2fbca62007-11-12 06:35:08 +00001278 }
Evan Chengf2fbca62007-11-12 06:35:08 +00001279 if (CanDelete)
1280 ReMatDelete.set(VN);
1281 } else {
1282 // Need a stack slot if there is any live range where uses cannot be
1283 // rematerialized.
1284 NeedStackSlot = true;
1285 }
1286 }
1287
1288 // One stack slot per live interval.
Evan Cheng81a03822007-11-17 00:40:40 +00001289 if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0)
Evan Chengf2fbca62007-11-12 06:35:08 +00001290 Slot = vrm.assignVirt2StackSlot(li.reg);
1291
1292 // Create new intervals and rewrite defs and uses.
1293 for (LiveInterval::Ranges::const_iterator
1294 I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) {
Evan Cheng81a03822007-11-17 00:40:40 +00001295 MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id];
1296 MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id];
1297 bool DefIsReMat = ReMatDefMI != NULL;
Evan Chengf2fbca62007-11-12 06:35:08 +00001298 bool CanDelete = ReMatDelete[I->valno->id];
1299 int LdSlot = 0;
Evan Cheng81a03822007-11-17 00:40:40 +00001300 bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
Evan Chengf2fbca62007-11-12 06:35:08 +00001301 bool isLoad = isLoadSS ||
Chris Lattner749c6f62008-01-07 07:27:27 +00001302 (DefIsReMat && ReMatDefMI->getDesc().isSimpleLoad());
Evan Cheng81a03822007-11-17 00:40:40 +00001303 rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI,
Evan Cheng0cbb1162007-11-29 01:06:25 +00001304 Slot, LdSlot, isLoad, isLoadSS, DefIsReMat,
Chris Lattner84bc5422007-12-31 04:13:23 +00001305 CanDelete, vrm, RegInfo, rc, ReMatIds, loopInfo,
Evan Cheng0cbb1162007-11-29 01:06:25 +00001306 SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes,
Evan Cheng1953d0c2007-11-29 10:12:14 +00001307 MBBVRegsMap, NewLIs);
Evan Chengf2fbca62007-11-12 06:35:08 +00001308 }
1309
Evan Cheng0cbb1162007-11-29 01:06:25 +00001310 // Insert spills / restores if we are splitting.
Evan Cheng1953d0c2007-11-29 10:12:14 +00001311 if (!TrySplit)
1312 return NewLIs;
1313
Evan Chengb50bb8c2007-12-05 08:16:32 +00001314 SmallPtrSet<LiveInterval*, 4> AddedKill;
Evan Chengaee4af62007-12-02 08:30:39 +00001315 SmallVector<unsigned, 2> Ops;
Evan Cheng1953d0c2007-11-29 10:12:14 +00001316 if (NeedStackSlot) {
1317 int Id = SpillMBBs.find_first();
1318 while (Id != -1) {
1319 std::vector<SRInfo> &spills = SpillIdxes[Id];
1320 for (unsigned i = 0, e = spills.size(); i != e; ++i) {
1321 int index = spills[i].index;
1322 unsigned VReg = spills[i].vreg;
Evan Cheng597d10d2007-12-04 00:32:23 +00001323 LiveInterval &nI = getOrCreateInterval(VReg);
Evan Cheng0cbb1162007-11-29 01:06:25 +00001324 bool isReMat = vrm.isReMaterialized(VReg);
1325 MachineInstr *MI = getInstructionFromIndex(index);
Evan Chengaee4af62007-12-02 08:30:39 +00001326 bool CanFold = false;
1327 bool FoundUse = false;
1328 Ops.clear();
Evan Chengcddbb832007-11-30 21:23:43 +00001329 if (spills[i].canFold) {
Evan Chengaee4af62007-12-02 08:30:39 +00001330 CanFold = true;
Evan Cheng0cbb1162007-11-29 01:06:25 +00001331 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
1332 MachineOperand &MO = MI->getOperand(j);
1333 if (!MO.isRegister() || MO.getReg() != VReg)
1334 continue;
Evan Chengaee4af62007-12-02 08:30:39 +00001335
1336 Ops.push_back(j);
1337 if (MO.isDef())
Evan Chengcddbb832007-11-30 21:23:43 +00001338 continue;
Evan Chengaee4af62007-12-02 08:30:39 +00001339 if (isReMat ||
1340 (!FoundUse && !alsoFoldARestore(Id, index, VReg,
1341 RestoreMBBs, RestoreIdxes))) {
1342 // MI has two-address uses of the same register. If the use
1343 // isn't the first and only use in the BB, then we can't fold
1344 // it. FIXME: Move this to rewriteInstructionsForSpills.
1345 CanFold = false;
Evan Chengcddbb832007-11-30 21:23:43 +00001346 break;
1347 }
Evan Chengaee4af62007-12-02 08:30:39 +00001348 FoundUse = true;
Evan Cheng0cbb1162007-11-29 01:06:25 +00001349 }
1350 }
1351 // Fold the store into the def if possible.
Evan Chengcddbb832007-11-30 21:23:43 +00001352 bool Folded = false;
Evan Chengaee4af62007-12-02 08:30:39 +00001353 if (CanFold && !Ops.empty()) {
1354 if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){
Evan Chengcddbb832007-11-30 21:23:43 +00001355 Folded = true;
Evan Chengf38d14f2007-12-05 09:05:34 +00001356 if (FoundUse > 0) {
Evan Chengaee4af62007-12-02 08:30:39 +00001357 // Also folded uses, do not issue a load.
1358 eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes);
Evan Chengf38d14f2007-12-05 09:05:34 +00001359 nI.removeRange(getLoadIndex(index), getUseIndex(index)+1);
1360 }
Evan Cheng597d10d2007-12-04 00:32:23 +00001361 nI.removeRange(getDefIndex(index), getStoreIndex(index));
Evan Chengcddbb832007-11-30 21:23:43 +00001362 }
Evan Cheng0cbb1162007-11-29 01:06:25 +00001363 }
1364
Evan Chengaee4af62007-12-02 08:30:39 +00001365 // Else tell the spiller to issue a spill.
Evan Chengb50bb8c2007-12-05 08:16:32 +00001366 if (!Folded) {
1367 LiveRange *LR = &nI.ranges[nI.ranges.size()-1];
1368 bool isKill = LR->end == getStoreIndex(index);
1369 vrm.addSpillPoint(VReg, isKill, MI);
1370 if (isKill)
1371 AddedKill.insert(&nI);
1372 }
Evan Cheng0cbb1162007-11-29 01:06:25 +00001373 }
Evan Cheng1953d0c2007-11-29 10:12:14 +00001374 Id = SpillMBBs.find_next(Id);
Evan Cheng0cbb1162007-11-29 01:06:25 +00001375 }
Evan Cheng1953d0c2007-11-29 10:12:14 +00001376 }
Evan Cheng0cbb1162007-11-29 01:06:25 +00001377
Evan Cheng1953d0c2007-11-29 10:12:14 +00001378 int Id = RestoreMBBs.find_first();
1379 while (Id != -1) {
1380 std::vector<SRInfo> &restores = RestoreIdxes[Id];
1381 for (unsigned i = 0, e = restores.size(); i != e; ++i) {
1382 int index = restores[i].index;
1383 if (index == -1)
1384 continue;
1385 unsigned VReg = restores[i].vreg;
Evan Cheng597d10d2007-12-04 00:32:23 +00001386 LiveInterval &nI = getOrCreateInterval(VReg);
Evan Cheng81a03822007-11-17 00:40:40 +00001387 MachineInstr *MI = getInstructionFromIndex(index);
Evan Chengaee4af62007-12-02 08:30:39 +00001388 bool CanFold = false;
1389 Ops.clear();
Evan Chengcddbb832007-11-30 21:23:43 +00001390 if (restores[i].canFold) {
Evan Chengaee4af62007-12-02 08:30:39 +00001391 CanFold = true;
Evan Cheng81a03822007-11-17 00:40:40 +00001392 for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) {
1393 MachineOperand &MO = MI->getOperand(j);
1394 if (!MO.isRegister() || MO.getReg() != VReg)
1395 continue;
Evan Chengaee4af62007-12-02 08:30:39 +00001396
Evan Cheng0cbb1162007-11-29 01:06:25 +00001397 if (MO.isDef()) {
Evan Chengaee4af62007-12-02 08:30:39 +00001398 // If this restore were to be folded, it would have been folded
1399 // already.
1400 CanFold = false;
Evan Cheng81a03822007-11-17 00:40:40 +00001401 break;
1402 }
Evan Chengaee4af62007-12-02 08:30:39 +00001403 Ops.push_back(j);
Evan Cheng81a03822007-11-17 00:40:40 +00001404 }
1405 }
Evan Cheng0cbb1162007-11-29 01:06:25 +00001406
1407 // Fold the load into the use if possible.
Evan Chengcddbb832007-11-30 21:23:43 +00001408 bool Folded = false;
Evan Chengaee4af62007-12-02 08:30:39 +00001409 if (CanFold && !Ops.empty()) {
1410 if (!vrm.isReMaterialized(VReg))
1411 Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg);
1412 else {
Evan Cheng0cbb1162007-11-29 01:06:25 +00001413 MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg);
1414 int LdSlot = 0;
1415 bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot);
1416 // If the rematerializable def is a load, also try to fold it.
Chris Lattner749c6f62008-01-07 07:27:27 +00001417 if (isLoadSS || ReMatDefMI->getDesc().isSimpleLoad())
Evan Chengaee4af62007-12-02 08:30:39 +00001418 Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index,
1419 Ops, isLoadSS, LdSlot, VReg);
1420 }
Evan Cheng0cbb1162007-11-29 01:06:25 +00001421 }
1422 // If folding is not possible / failed, then tell the spiller to issue a
1423 // load / rematerialization for us.
Evan Cheng597d10d2007-12-04 00:32:23 +00001424 if (Folded)
1425 nI.removeRange(getLoadIndex(index), getUseIndex(index)+1);
Evan Chengb50bb8c2007-12-05 08:16:32 +00001426 else
Evan Cheng0cbb1162007-11-29 01:06:25 +00001427 vrm.addRestorePoint(VReg, MI);
Evan Cheng81a03822007-11-17 00:40:40 +00001428 }
Evan Cheng1953d0c2007-11-29 10:12:14 +00001429 Id = RestoreMBBs.find_next(Id);
Evan Cheng81a03822007-11-17 00:40:40 +00001430 }
1431
Evan Chengb50bb8c2007-12-05 08:16:32 +00001432 // Finalize intervals: add kills, finalize spill weights, and filter out
1433 // dead intervals.
Evan Cheng597d10d2007-12-04 00:32:23 +00001434 std::vector<LiveInterval*> RetNewLIs;
1435 for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) {
1436 LiveInterval *LI = NewLIs[i];
1437 if (!LI->empty()) {
1438 LI->weight /= LI->getSize();
Evan Chengb50bb8c2007-12-05 08:16:32 +00001439 if (!AddedKill.count(LI)) {
1440 LiveRange *LR = &LI->ranges[LI->ranges.size()-1];
Evan Chengd120ffd2007-12-05 10:24:35 +00001441 unsigned LastUseIdx = getBaseIndex(LR->end);
1442 MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx);
Evan Chengb50bb8c2007-12-05 08:16:32 +00001443 int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg);
1444 assert(UseIdx != -1);
Chris Lattner749c6f62008-01-07 07:27:27 +00001445 if (LastUse->getDesc().getOperandConstraint(UseIdx, TOI::TIED_TO) ==
Chris Lattner69244302008-01-07 01:56:04 +00001446 -1) {
Evan Chengb50bb8c2007-12-05 08:16:32 +00001447 LastUse->getOperand(UseIdx).setIsKill();
Evan Chengd120ffd2007-12-05 10:24:35 +00001448 vrm.addKillPoint(LI->reg, LastUseIdx);
Evan Chengadf85902007-12-05 09:51:10 +00001449 }
Evan Chengb50bb8c2007-12-05 08:16:32 +00001450 }
Evan Cheng597d10d2007-12-04 00:32:23 +00001451 RetNewLIs.push_back(LI);
1452 }
1453 }
Evan Cheng81a03822007-11-17 00:40:40 +00001454
Evan Cheng597d10d2007-12-04 00:32:23 +00001455 return RetNewLIs;
Evan Chengf2fbca62007-11-12 06:35:08 +00001456}