blob: f8aacdb8649d488429059976f923b22c9cc0d772 [file] [log] [blame]
Alkis Evlogimenosc794a902004-02-23 23:08:11 +00001//===-- llvm/CodeGen/VirtRegMap.cpp - Virtual Register Map ----------------===//
2//
3// The LLVM Compiler Infrastructure
4//
Chris Lattnerf3ebc3f2007-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 Evlogimenosc794a902004-02-23 23:08:11 +00007//
8//===----------------------------------------------------------------------===//
9//
Chris Lattnere2b77d52004-09-30 01:54:45 +000010// This file implements the VirtRegMap class.
11//
Dan Gohman4a618822010-02-10 16:03:48 +000012// It also contains implementations of the Spiller interface, which, given a
Chris Lattnere2b77d52004-09-30 01:54:45 +000013// virtual register map and a machine function, eliminates all virtual
14// references by replacing them with physical register references - adding spill
Alkis Evlogimenos1dd872c2004-02-24 08:58:30 +000015// code as necessary.
Alkis Evlogimenosc794a902004-02-23 23:08:11 +000016//
17//===----------------------------------------------------------------------===//
18
Jakob Stoklund Olesen26c9d702012-11-28 19:13:06 +000019#include "llvm/CodeGen/VirtRegMap.h"
Jakob Stoklund Olesen12243122012-06-08 23:44:45 +000020#include "LiveDebugVariables.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000021#include "llvm/ADT/STLExtras.h"
Chandler Carruth442f7842014-03-04 10:07:28 +000022#include "llvm/ADT/Statistic.h"
Jakob Stoklund Olesen12243122012-06-08 23:44:45 +000023#include "llvm/CodeGen/LiveIntervalAnalysis.h"
Evan Chengb53825b2012-09-21 20:04:28 +000024#include "llvm/CodeGen/LiveStackAnalysis.h"
Alkis Evlogimenosc794a902004-02-23 23:08:11 +000025#include "llvm/CodeGen/MachineFrameInfo.h"
Chris Lattnere2b77d52004-09-30 01:54:45 +000026#include "llvm/CodeGen/MachineFunction.h"
Evan Cheng499ffa92008-04-11 17:53:36 +000027#include "llvm/CodeGen/MachineInstrBuilder.h"
Chris Lattnera10fff52007-12-31 04:13:23 +000028#include "llvm/CodeGen/MachineRegisterInfo.h"
Jakob Stoklund Olesen12243122012-06-08 23:44:45 +000029#include "llvm/CodeGen/Passes.h"
Quentin Colombetfa403ab2013-09-25 00:26:17 +000030#include "llvm/IR/Function.h"
Chris Lattner3d27be12006-08-27 12:54:02 +000031#include "llvm/Support/Compiler.h"
Evan Chenga1968b02009-02-11 08:24:21 +000032#include "llvm/Support/Debug.h"
Daniel Dunbar796e43e2009-07-24 10:36:58 +000033#include "llvm/Support/raw_ostream.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000034#include "llvm/Target/TargetInstrInfo.h"
35#include "llvm/Target/TargetMachine.h"
36#include "llvm/Target/TargetRegisterInfo.h"
Eric Christopherd9134482014-08-04 21:25:23 +000037#include "llvm/Target/TargetSubtargetInfo.h"
Chris Lattnerc8b07dd2004-10-26 15:35:58 +000038#include <algorithm>
Alkis Evlogimenosc794a902004-02-23 23:08:11 +000039using namespace llvm;
40
Chandler Carruth1b9dde02014-04-22 02:02:50 +000041#define DEBUG_TYPE "regalloc"
42
Jakob Stoklund Olesen53e2e482011-09-15 18:31:13 +000043STATISTIC(NumSpillSlots, "Number of spill slots allocated");
44STATISTIC(NumIdCopies, "Number of identity moves eliminated after rewriting");
Dan Gohmand78c4002008-05-13 00:00:25 +000045
Chris Lattnere2b77d52004-09-30 01:54:45 +000046//===----------------------------------------------------------------------===//
47// VirtRegMap implementation
48//===----------------------------------------------------------------------===//
49
Owen Andersond37ddf52009-03-13 05:55:11 +000050char VirtRegMap::ID = 0;
51
Owen Andersondf7a4f22010-10-07 22:25:06 +000052INITIALIZE_PASS(VirtRegMap, "virtregmap", "Virtual Register Map", false, false)
Owen Andersond37ddf52009-03-13 05:55:11 +000053
54bool VirtRegMap::runOnMachineFunction(MachineFunction &mf) {
Evan Cheng085caf12009-06-14 20:22:55 +000055 MRI = &mf.getRegInfo();
Eric Christopherfc6de422014-08-05 02:39:49 +000056 TII = mf.getSubtarget().getInstrInfo();
57 TRI = mf.getSubtarget().getRegisterInfo();
Owen Andersond37ddf52009-03-13 05:55:11 +000058 MF = &mf;
Lang Hames05fb9632009-11-03 23:52:08 +000059
Owen Andersond37ddf52009-03-13 05:55:11 +000060 Virt2PhysMap.clear();
61 Virt2StackSlotMap.clear();
Owen Andersond37ddf52009-03-13 05:55:11 +000062 Virt2SplitMap.clear();
Evan Cheng3f778052009-05-04 03:30:11 +000063
Chris Lattner13a5dcd2006-09-05 02:12:02 +000064 grow();
Owen Andersond37ddf52009-03-13 05:55:11 +000065 return false;
Chris Lattner13a5dcd2006-09-05 02:12:02 +000066}
67
Chris Lattnere2b77d52004-09-30 01:54:45 +000068void VirtRegMap::grow() {
Jakob Stoklund Olesend82ac372011-01-09 21:58:20 +000069 unsigned NumRegs = MF->getRegInfo().getNumVirtRegs();
70 Virt2PhysMap.resize(NumRegs);
71 Virt2StackSlotMap.resize(NumRegs);
Jakob Stoklund Olesend82ac372011-01-09 21:58:20 +000072 Virt2SplitMap.resize(NumRegs);
Alkis Evlogimenosc794a902004-02-23 23:08:11 +000073}
74
Matthias Braun1ee25e02017-06-08 21:30:54 +000075void VirtRegMap::assignVirt2Phys(unsigned virtReg, MCPhysReg physReg) {
76 assert(TargetRegisterInfo::isVirtualRegister(virtReg) &&
77 TargetRegisterInfo::isPhysicalRegister(physReg));
78 assert(Virt2PhysMap[virtReg] == NO_PHYS_REG &&
79 "attempt to assign physical register to already mapped "
80 "virtual register");
81 assert(!getRegInfo().isReserved(physReg) &&
82 "Attempt to map virtReg to a reserved physReg");
83 Virt2PhysMap[virtReg] = physReg;
84}
85
Jakob Stoklund Olesen39aed732010-11-16 00:41:01 +000086unsigned VirtRegMap::createSpillSlot(const TargetRegisterClass *RC) {
Krzysztof Parzyszek44e25f32017-04-24 18:55:33 +000087 unsigned Size = TRI->getSpillSize(*RC);
88 unsigned Align = TRI->getSpillAlignment(*RC);
89 int SS = MF->getFrameInfo().CreateSpillStackObject(Size, Align);
Jakob Stoklund Olesen53e2e482011-09-15 18:31:13 +000090 ++NumSpillSlots;
Jakob Stoklund Olesen39aed732010-11-16 00:41:01 +000091 return SS;
92}
93
Jakob Stoklund Olesen1dd82dd2012-12-04 00:30:22 +000094bool VirtRegMap::hasPreferredPhys(unsigned VirtReg) {
95 unsigned Hint = MRI->getSimpleHint(VirtReg);
96 if (!Hint)
Matt Arsenault50451d42016-06-02 18:37:21 +000097 return false;
Jakob Stoklund Olesen1dd82dd2012-12-04 00:30:22 +000098 if (TargetRegisterInfo::isVirtualRegister(Hint))
99 Hint = getPhys(Hint);
100 return getPhys(VirtReg) == Hint;
101}
102
Jakob Stoklund Olesen74052b02012-12-03 23:23:50 +0000103bool VirtRegMap::hasKnownPreference(unsigned VirtReg) {
104 std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(VirtReg);
105 if (TargetRegisterInfo::isPhysicalRegister(Hint.second))
106 return true;
107 if (TargetRegisterInfo::isVirtualRegister(Hint.second))
108 return hasPhys(Hint.second);
109 return false;
110}
111
Chris Lattnere2b77d52004-09-30 01:54:45 +0000112int VirtRegMap::assignVirt2StackSlot(unsigned virtReg) {
Dan Gohman3a4be0f2008-02-10 18:45:23 +0000113 assert(TargetRegisterInfo::isVirtualRegister(virtReg));
Chris Lattner39fef8d2004-09-30 02:15:18 +0000114 assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
Chris Lattnere2b77d52004-09-30 01:54:45 +0000115 "attempt to assign stack slot to already spilled register");
Owen Andersond37ddf52009-03-13 05:55:11 +0000116 const TargetRegisterClass* RC = MF->getRegInfo().getRegClass(virtReg);
Jakob Stoklund Olesen39aed732010-11-16 00:41:01 +0000117 return Virt2StackSlotMap[virtReg] = createSpillSlot(RC);
Chris Lattnere2b77d52004-09-30 01:54:45 +0000118}
119
Evan Cheng6d563682008-02-27 03:04:06 +0000120void VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int SS) {
Dan Gohman3a4be0f2008-02-10 18:45:23 +0000121 assert(TargetRegisterInfo::isVirtualRegister(virtReg));
Chris Lattner39fef8d2004-09-30 02:15:18 +0000122 assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT &&
Chris Lattnere2b77d52004-09-30 01:54:45 +0000123 "attempt to assign stack slot to already spilled register");
Evan Cheng6d563682008-02-27 03:04:06 +0000124 assert((SS >= 0 ||
Matthias Braun941a7052016-07-28 18:40:00 +0000125 (SS >= MF->getFrameInfo().getObjectIndexBegin())) &&
Evan Cheng8be98c12007-04-04 07:40:01 +0000126 "illegal fixed frame index");
Evan Cheng6d563682008-02-27 03:04:06 +0000127 Virt2StackSlotMap[virtReg] = SS;
Alkis Evlogimenosfd735bc2004-05-29 20:38:05 +0000128}
129
Jakob Stoklund Olesen12243122012-06-08 23:44:45 +0000130void VirtRegMap::print(raw_ostream &OS, const Module*) const {
131 OS << "********** REGISTER MAP **********\n";
132 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
133 unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
134 if (Virt2PhysMap[Reg] != (unsigned)VirtRegMap::NO_PHYS_REG) {
135 OS << '[' << PrintReg(Reg, TRI) << " -> "
136 << PrintReg(Virt2PhysMap[Reg], TRI) << "] "
Craig Toppercf0444b2014-11-17 05:50:14 +0000137 << TRI->getRegClassName(MRI->getRegClass(Reg)) << "\n";
Jakob Stoklund Olesen12243122012-06-08 23:44:45 +0000138 }
139 }
140
141 for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
142 unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
143 if (Virt2StackSlotMap[Reg] != VirtRegMap::NO_STACK_SLOT) {
144 OS << '[' << PrintReg(Reg, TRI) << " -> fi#" << Virt2StackSlotMap[Reg]
Craig Toppercf0444b2014-11-17 05:50:14 +0000145 << "] " << TRI->getRegClassName(MRI->getRegClass(Reg)) << "\n";
Jakob Stoklund Olesen12243122012-06-08 23:44:45 +0000146 }
147 }
148 OS << '\n';
149}
150
Manman Ren19f49ac2012-09-11 22:23:19 +0000151#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
Yaron Kereneb2a2542016-01-29 20:50:44 +0000152LLVM_DUMP_METHOD void VirtRegMap::dump() const {
Jakob Stoklund Olesen12243122012-06-08 23:44:45 +0000153 print(dbgs());
154}
Manman Ren742534c2012-09-06 19:06:06 +0000155#endif
Jakob Stoklund Olesen12243122012-06-08 23:44:45 +0000156
157//===----------------------------------------------------------------------===//
158// VirtRegRewriter
159//===----------------------------------------------------------------------===//
160//
161// The VirtRegRewriter is the last of the register allocator passes.
162// It rewrites virtual registers to physical registers as specified in the
163// VirtRegMap analysis. It also updates live-in information on basic blocks
164// according to LiveIntervals.
165//
166namespace {
167class VirtRegRewriter : public MachineFunctionPass {
168 MachineFunction *MF;
169 const TargetMachine *TM;
170 const TargetRegisterInfo *TRI;
171 const TargetInstrInfo *TII;
172 MachineRegisterInfo *MRI;
173 SlotIndexes *Indexes;
174 LiveIntervals *LIS;
175 VirtRegMap *VRM;
176
177 void rewrite();
178 void addMBBLiveIns();
Matthias Braunca4e8422015-06-16 18:22:28 +0000179 bool readsUndefSubreg(const MachineOperand &MO) const;
Matthias Brauncc580052015-09-09 18:07:54 +0000180 void addLiveInsForSubRanges(const LiveInterval &LI, unsigned PhysReg) const;
Matthias Braun152e7c82016-07-09 00:19:07 +0000181 void handleIdentityCopy(MachineInstr &MI) const;
Matthias Braunf0b68d32017-03-17 00:41:39 +0000182 void expandCopyBundle(MachineInstr &MI) const;
Quentin Colombet647b4822017-08-16 00:17:05 +0000183 bool subRegLiveThrough(const MachineInstr &MI, unsigned SuperPhysReg) const;
Matthias Brauncc580052015-09-09 18:07:54 +0000184
Jakob Stoklund Olesen12243122012-06-08 23:44:45 +0000185public:
186 static char ID;
187 VirtRegRewriter() : MachineFunctionPass(ID) {}
188
Craig Topper4584cd52014-03-07 09:26:03 +0000189 void getAnalysisUsage(AnalysisUsage &AU) const override;
Jakob Stoklund Olesen12243122012-06-08 23:44:45 +0000190
Craig Topper4584cd52014-03-07 09:26:03 +0000191 bool runOnMachineFunction(MachineFunction&) override;
Derek Schuff42666ee2016-03-29 17:40:22 +0000192 MachineFunctionProperties getSetProperties() const override {
193 return MachineFunctionProperties().set(
Matthias Braun1eb47362016-08-25 01:27:13 +0000194 MachineFunctionProperties::Property::NoVRegs);
Derek Schuff42666ee2016-03-29 17:40:22 +0000195 }
Jakob Stoklund Olesen12243122012-06-08 23:44:45 +0000196};
197} // end anonymous namespace
198
199char &llvm::VirtRegRewriterID = VirtRegRewriter::ID;
200
201INITIALIZE_PASS_BEGIN(VirtRegRewriter, "virtregrewriter",
202 "Virtual Register Rewriter", false, false)
203INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
204INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
205INITIALIZE_PASS_DEPENDENCY(LiveDebugVariables)
Evan Chengb53825b2012-09-21 20:04:28 +0000206INITIALIZE_PASS_DEPENDENCY(LiveStacks)
Jakob Stoklund Olesen12243122012-06-08 23:44:45 +0000207INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
208INITIALIZE_PASS_END(VirtRegRewriter, "virtregrewriter",
209 "Virtual Register Rewriter", false, false)
210
211char VirtRegRewriter::ID = 0;
212
213void VirtRegRewriter::getAnalysisUsage(AnalysisUsage &AU) const {
214 AU.setPreservesCFG();
215 AU.addRequired<LiveIntervals>();
216 AU.addRequired<SlotIndexes>();
217 AU.addPreserved<SlotIndexes>();
218 AU.addRequired<LiveDebugVariables>();
Evan Chengb53825b2012-09-21 20:04:28 +0000219 AU.addRequired<LiveStacks>();
220 AU.addPreserved<LiveStacks>();
Jakob Stoklund Olesen12243122012-06-08 23:44:45 +0000221 AU.addRequired<VirtRegMap>();
222 MachineFunctionPass::getAnalysisUsage(AU);
223}
224
225bool VirtRegRewriter::runOnMachineFunction(MachineFunction &fn) {
226 MF = &fn;
227 TM = &MF->getTarget();
Eric Christopher1c5fce02014-10-13 21:57:44 +0000228 TRI = MF->getSubtarget().getRegisterInfo();
229 TII = MF->getSubtarget().getInstrInfo();
Jakob Stoklund Olesen12243122012-06-08 23:44:45 +0000230 MRI = &MF->getRegInfo();
231 Indexes = &getAnalysis<SlotIndexes>();
232 LIS = &getAnalysis<LiveIntervals>();
233 VRM = &getAnalysis<VirtRegMap>();
Jakob Stoklund Olesen5bfec692011-02-18 22:03:18 +0000234 DEBUG(dbgs() << "********** REWRITE VIRTUAL REGISTERS **********\n"
235 << "********** Function: "
Craig Toppera538d832012-08-22 06:07:19 +0000236 << MF->getName() << '\n');
Jakob Stoklund Olesen12243122012-06-08 23:44:45 +0000237 DEBUG(VRM->dump());
238
239 // Add kill flags while we still have virtual registers.
Jakob Stoklund Olesenbb4bdd82012-09-06 18:15:18 +0000240 LIS->addKillFlags(VRM);
Jakob Stoklund Olesen12243122012-06-08 23:44:45 +0000241
Jakob Stoklund Olesenbe336292012-06-09 00:14:47 +0000242 // Live-in lists on basic blocks are required for physregs.
243 addMBBLiveIns();
244
Jakob Stoklund Olesen12243122012-06-08 23:44:45 +0000245 // Rewrite virtual registers.
246 rewrite();
247
248 // Write out new DBG_VALUE instructions.
249 getAnalysis<LiveDebugVariables>().emitDebugValues(VRM);
250
251 // All machine operands and other references to virtual registers have been
252 // replaced. Remove the virtual registers and release all the transient data.
253 VRM->clearAllVirt();
254 MRI->clearVirtRegs();
255 return true;
256}
257
Matthias Brauncc580052015-09-09 18:07:54 +0000258void VirtRegRewriter::addLiveInsForSubRanges(const LiveInterval &LI,
259 unsigned PhysReg) const {
260 assert(!LI.empty());
261 assert(LI.hasSubRanges());
262
263 typedef std::pair<const LiveInterval::SubRange *,
264 LiveInterval::const_iterator> SubRangeIteratorPair;
265 SmallVector<SubRangeIteratorPair, 4> SubRanges;
266 SlotIndex First;
267 SlotIndex Last;
268 for (const LiveInterval::SubRange &SR : LI.subranges()) {
269 SubRanges.push_back(std::make_pair(&SR, SR.begin()));
270 if (!First.isValid() || SR.segments.front().start < First)
271 First = SR.segments.front().start;
272 if (!Last.isValid() || SR.segments.back().end > Last)
273 Last = SR.segments.back().end;
274 }
275
276 // Check all mbb start positions between First and Last while
277 // simulatenously advancing an iterator for each subrange.
278 for (SlotIndexes::MBBIndexIterator MBBI = Indexes->findMBBIndex(First);
279 MBBI != Indexes->MBBIndexEnd() && MBBI->first <= Last; ++MBBI) {
280 SlotIndex MBBBegin = MBBI->first;
281 // Advance all subrange iterators so that their end position is just
282 // behind MBBBegin (or the iterator is at the end).
Krzysztof Parzyszek91b5cf82016-12-15 14:36:06 +0000283 LaneBitmask LaneMask;
Matthias Brauncc580052015-09-09 18:07:54 +0000284 for (auto &RangeIterPair : SubRanges) {
285 const LiveInterval::SubRange *SR = RangeIterPair.first;
286 LiveInterval::const_iterator &SRI = RangeIterPair.second;
287 while (SRI != SR->end() && SRI->end <= MBBBegin)
288 ++SRI;
289 if (SRI == SR->end())
290 continue;
291 if (SRI->start <= MBBBegin)
292 LaneMask |= SR->LaneMask;
293 }
Krzysztof Parzyszek91b5cf82016-12-15 14:36:06 +0000294 if (LaneMask.none())
Matthias Brauncc580052015-09-09 18:07:54 +0000295 continue;
296 MachineBasicBlock *MBB = MBBI->second;
Matthias Braund9da1622015-09-09 18:08:03 +0000297 MBB->addLiveIn(PhysReg, LaneMask);
Matthias Brauncc580052015-09-09 18:07:54 +0000298 }
299}
300
Jakob Stoklund Olesenbe336292012-06-09 00:14:47 +0000301// Compute MBB live-in lists from virtual register live ranges and their
302// assignments.
303void VirtRegRewriter::addMBBLiveIns() {
Jakob Stoklund Olesenbe336292012-06-09 00:14:47 +0000304 for (unsigned Idx = 0, IdxE = MRI->getNumVirtRegs(); Idx != IdxE; ++Idx) {
305 unsigned VirtReg = TargetRegisterInfo::index2VirtReg(Idx);
306 if (MRI->reg_nodbg_empty(VirtReg))
307 continue;
308 LiveInterval &LI = LIS->getInterval(VirtReg);
309 if (LI.empty() || LIS->intervalIsInOneMBB(LI))
310 continue;
311 // This is a virtual register that is live across basic blocks. Its
312 // assigned PhysReg must be marked as live-in to those blocks.
313 unsigned PhysReg = VRM->getPhys(VirtReg);
314 assert(PhysReg != VirtRegMap::NO_PHYS_REG && "Unmapped virtual register.");
315
Matthias Braun279f8362014-12-10 01:13:08 +0000316 if (LI.hasSubRanges()) {
Matthias Brauncc580052015-09-09 18:07:54 +0000317 addLiveInsForSubRanges(LI, PhysReg);
Matthias Braun279f8362014-12-10 01:13:08 +0000318 } else {
Matthias Brauncc580052015-09-09 18:07:54 +0000319 // Go over MBB begin positions and see if we have segments covering them.
320 // The following works because segments and the MBBIndex list are both
321 // sorted by slot indexes.
322 SlotIndexes::MBBIndexIterator I = Indexes->MBBIndexBegin();
323 for (const auto &Seg : LI) {
324 I = Indexes->advanceMBBIndex(I, Seg.start);
325 for (; I != Indexes->MBBIndexEnd() && I->first < Seg.end; ++I) {
326 MachineBasicBlock *MBB = I->second;
327 MBB->addLiveIn(PhysReg);
328 }
Matthias Braun279f8362014-12-10 01:13:08 +0000329 }
Jakob Stoklund Olesenbe336292012-06-09 00:14:47 +0000330 }
331 }
Puyan Lotfibb457b92015-05-22 08:11:26 +0000332
333 // Sort and unique MBB LiveIns as we've not checked if SubReg/PhysReg were in
334 // each MBB's LiveIns set before calling addLiveIn on them.
335 for (MachineBasicBlock &MBB : *MF)
336 MBB.sortUniqueLiveIns();
Jakob Stoklund Olesenbe336292012-06-09 00:14:47 +0000337}
338
Matthias Braunca4e8422015-06-16 18:22:28 +0000339/// Returns true if the given machine operand \p MO only reads undefined lanes.
340/// The function only works for use operands with a subregister set.
341bool VirtRegRewriter::readsUndefSubreg(const MachineOperand &MO) const {
342 // Shortcut if the operand is already marked undef.
343 if (MO.isUndef())
344 return true;
345
346 unsigned Reg = MO.getReg();
347 const LiveInterval &LI = LIS->getInterval(Reg);
348 const MachineInstr &MI = *MO.getParent();
Duncan P. N. Exon Smith3ac9cc62016-02-27 06:40:41 +0000349 SlotIndex BaseIndex = LIS->getInstructionIndex(MI);
Matthias Braunca4e8422015-06-16 18:22:28 +0000350 // This code is only meant to handle reading undefined subregisters which
351 // we couldn't properly detect before.
352 assert(LI.liveAt(BaseIndex) &&
353 "Reads of completely dead register should be marked undef already");
354 unsigned SubRegIdx = MO.getSubReg();
Krzysztof Parzyszeka7ed0902016-08-24 13:37:55 +0000355 assert(SubRegIdx != 0 && LI.hasSubRanges());
Matthias Braune6a24852015-09-25 21:51:14 +0000356 LaneBitmask UseMask = TRI->getSubRegIndexLaneMask(SubRegIdx);
Matthias Braunca4e8422015-06-16 18:22:28 +0000357 // See if any of the relevant subregister liveranges is defined at this point.
358 for (const LiveInterval::SubRange &SR : LI.subranges()) {
Krzysztof Parzyszekea9f8ce2016-12-16 19:11:56 +0000359 if ((SR.LaneMask & UseMask).any() && SR.liveAt(BaseIndex))
Matthias Braunca4e8422015-06-16 18:22:28 +0000360 return false;
361 }
362 return true;
363}
364
Matthias Braun152e7c82016-07-09 00:19:07 +0000365void VirtRegRewriter::handleIdentityCopy(MachineInstr &MI) const {
366 if (!MI.isIdentityCopy())
367 return;
368 DEBUG(dbgs() << "Identity copy: " << MI);
369 ++NumIdCopies;
370
371 // Copies like:
372 // %R0 = COPY %R0<undef>
373 // %AL = COPY %AL, %EAX<imp-def>
374 // give us additional liveness information: The target (super-)register
375 // must not be valid before this point. Replace the COPY with a KILL
376 // instruction to maintain this information.
377 if (MI.getOperand(0).isUndef() || MI.getNumOperands() > 2) {
378 MI.setDesc(TII->get(TargetOpcode::KILL));
379 DEBUG(dbgs() << " replace by: " << MI);
380 return;
381 }
382
383 if (Indexes)
Matthias Braunfa289ec2017-03-17 00:41:33 +0000384 Indexes->removeSingleMachineInstrFromMaps(MI);
385 MI.eraseFromBundle();
Matthias Braun152e7c82016-07-09 00:19:07 +0000386 DEBUG(dbgs() << " deleted.\n");
387}
388
Matthias Braunf0b68d32017-03-17 00:41:39 +0000389/// The liverange splitting logic sometimes produces bundles of copies when
390/// subregisters are involved. Expand these into a sequence of copy instructions
391/// after processing the last in the bundle. Does not update LiveIntervals
392/// which we shouldn't need for this instruction anymore.
393void VirtRegRewriter::expandCopyBundle(MachineInstr &MI) const {
394 if (!MI.isCopy())
395 return;
396
397 if (MI.isBundledWithPred() && !MI.isBundledWithSucc()) {
398 // Only do this when the complete bundle is made out of COPYs.
Matthias Braun8445cbd2017-03-21 21:58:08 +0000399 MachineBasicBlock &MBB = *MI.getParent();
Matthias Braunf0b68d32017-03-17 00:41:39 +0000400 for (MachineBasicBlock::reverse_instr_iterator I =
Matthias Braun8445cbd2017-03-21 21:58:08 +0000401 std::next(MI.getReverseIterator()), E = MBB.instr_rend();
402 I != E && I->isBundledWithSucc(); ++I) {
Matthias Braunf0b68d32017-03-17 00:41:39 +0000403 if (!I->isCopy())
404 return;
405 }
406
407 for (MachineBasicBlock::reverse_instr_iterator I = MI.getReverseIterator();
408 I->isBundledWithPred(); ) {
409 MachineInstr &MI = *I;
410 ++I;
411
412 MI.unbundleFromPred();
413 if (Indexes)
414 Indexes->insertMachineInstrInMaps(MI);
415 }
416 }
417}
418
Quentin Colombet647b4822017-08-16 00:17:05 +0000419/// Check whether (part of) \p SuperPhysReg is live through \p MI.
420/// \pre \p MI defines a subregister of a virtual register that
421/// has been assigned to \p SuperPhysReg.
422bool VirtRegRewriter::subRegLiveThrough(const MachineInstr &MI,
423 unsigned SuperPhysReg) const {
424 SlotIndex MIIndex = LIS->getInstructionIndex(MI);
425 SlotIndex BeforeMIUses = MIIndex.getBaseIndex();
426 SlotIndex AfterMIDefs = MIIndex.getBoundaryIndex();
427 for (MCRegUnitIterator Unit(SuperPhysReg, TRI); Unit.isValid(); ++Unit) {
428 const LiveRange &UnitRange = LIS->getRegUnit(*Unit);
429 // If the regunit is live both before and after MI,
430 // we assume it is live through.
431 // Generally speaking, this is not true, because something like
432 // "RU = op RU" would match that description.
433 // However, we know that we are trying to assess whether
434 // a def of a virtual reg, vreg, is live at the same time of RU.
435 // If we are in the "RU = op RU" situation, that means that vreg
436 // is defined at the same time as RU (i.e., "vreg, RU = op RU").
437 // Thus, vreg and RU interferes and vreg cannot be assigned to
438 // SuperPhysReg. Therefore, this situation cannot happen.
439 if (UnitRange.liveAt(AfterMIDefs) && UnitRange.liveAt(BeforeMIUses))
440 return true;
441 }
442 return false;
443}
444
Jakob Stoklund Olesen12243122012-06-08 23:44:45 +0000445void VirtRegRewriter::rewrite() {
Matthias Brauna25e13a2015-03-19 00:21:58 +0000446 bool NoSubRegLiveness = !MRI->subRegLivenessEnabled();
Jakob Stoklund Olesen71d3b892011-04-27 17:42:31 +0000447 SmallVector<unsigned, 8> SuperDeads;
448 SmallVector<unsigned, 8> SuperDefs;
Jakob Stoklund Olesen5bfec692011-02-18 22:03:18 +0000449 SmallVector<unsigned, 8> SuperKills;
Logan Chien18583d72014-02-25 16:57:28 +0000450
Jakob Stoklund Olesen5bfec692011-02-18 22:03:18 +0000451 for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end();
452 MBBI != MBBE; ++MBBI) {
453 DEBUG(MBBI->print(dbgs(), Indexes));
Evan Chengd42aba52012-01-19 07:46:36 +0000454 for (MachineBasicBlock::instr_iterator
455 MII = MBBI->instr_begin(), MIE = MBBI->instr_end(); MII != MIE;) {
Duncan P. N. Exon Smithf1ff53e2015-10-09 22:56:24 +0000456 MachineInstr *MI = &*MII;
Jakob Stoklund Olesen5bfec692011-02-18 22:03:18 +0000457 ++MII;
458
459 for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
460 MOE = MI->operands_end(); MOI != MOE; ++MOI) {
461 MachineOperand &MO = *MOI;
Jakob Stoklund Olesena0cf42f2012-02-17 19:07:56 +0000462
463 // Make sure MRI knows about registers clobbered by regmasks.
464 if (MO.isRegMask())
465 MRI->addPhysRegsUsedFromRegMask(MO.getRegMask());
466
Jakob Stoklund Olesen5bfec692011-02-18 22:03:18 +0000467 if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
468 continue;
469 unsigned VirtReg = MO.getReg();
Jakob Stoklund Olesen12243122012-06-08 23:44:45 +0000470 unsigned PhysReg = VRM->getPhys(VirtReg);
471 assert(PhysReg != VirtRegMap::NO_PHYS_REG &&
472 "Instruction uses unmapped VirtReg");
Jakob Stoklund Olesenc30a9af2012-10-15 21:57:41 +0000473 assert(!MRI->isReserved(PhysReg) && "Reserved register assignment");
Jakob Stoklund Olesen5bfec692011-02-18 22:03:18 +0000474
475 // Preserve semantics of sub-register operands.
Matthias Braunca4e8422015-06-16 18:22:28 +0000476 unsigned SubReg = MO.getSubReg();
477 if (SubReg != 0) {
478 if (NoSubRegLiveness) {
479 // A virtual register kill refers to the whole register, so we may
480 // have to add <imp-use,kill> operands for the super-register. A
481 // partial redef always kills and redefines the super-register.
Quentin Colombet647b4822017-08-16 00:17:05 +0000482 if ((MO.readsReg() && (MO.isDef() || MO.isKill())) ||
483 (MO.isDef() && subRegLiveThrough(*MI, PhysReg)))
Matthias Braunca4e8422015-06-16 18:22:28 +0000484 SuperKills.push_back(PhysReg);
Jakob Stoklund Olesend5d39bb2011-10-05 00:01:48 +0000485
Matthias Braunca4e8422015-06-16 18:22:28 +0000486 if (MO.isDef()) {
487 // Also add implicit defs for the super-register.
Matthias Braund70caaf2014-12-10 01:13:04 +0000488 if (MO.isDead())
489 SuperDeads.push_back(PhysReg);
490 else
491 SuperDefs.push_back(PhysReg);
492 }
Matthias Braunca4e8422015-06-16 18:22:28 +0000493 } else {
494 if (MO.isUse()) {
495 if (readsUndefSubreg(MO))
496 // We need to add an <undef> flag if the subregister is
497 // completely undefined (and we are not adding super-register
498 // defs).
499 MO.setIsUndef(true);
500 } else if (!MO.isDead()) {
501 assert(MO.isDef());
Matthias Braunca4e8422015-06-16 18:22:28 +0000502 }
Jakob Stoklund Olesend5d39bb2011-10-05 00:01:48 +0000503 }
Jakob Stoklund Olesen5bfec692011-02-18 22:03:18 +0000504
Matthias Braunfa289ec2017-03-17 00:41:33 +0000505 // The <def,undef> and <def,internal> flags only make sense for
506 // sub-register defs, and we are substituting a full physreg. An
507 // <imp-use,kill> operand from the SuperKills list will represent the
508 // partial read of the super-register.
509 if (MO.isDef()) {
Matthias Braunca4e8422015-06-16 18:22:28 +0000510 MO.setIsUndef(false);
Matthias Braunfa289ec2017-03-17 00:41:33 +0000511 MO.setIsInternalRead(false);
512 }
Matthias Braunca4e8422015-06-16 18:22:28 +0000513
Jakob Stoklund Olesen5bfec692011-02-18 22:03:18 +0000514 // PhysReg operands cannot have subregister indexes.
Matthias Braunca4e8422015-06-16 18:22:28 +0000515 PhysReg = TRI->getSubReg(PhysReg, SubReg);
Jakob Stoklund Olesen5bfec692011-02-18 22:03:18 +0000516 assert(PhysReg && "Invalid SubReg for physical register");
517 MO.setSubReg(0);
518 }
519 // Rewrite. Note we could have used MachineOperand::substPhysReg(), but
520 // we need the inlining here.
521 MO.setReg(PhysReg);
522 }
523
524 // Add any missing super-register kills after rewriting the whole
525 // instruction.
526 while (!SuperKills.empty())
527 MI->addRegisterKilled(SuperKills.pop_back_val(), TRI, true);
528
Jakob Stoklund Olesen71d3b892011-04-27 17:42:31 +0000529 while (!SuperDeads.empty())
530 MI->addRegisterDead(SuperDeads.pop_back_val(), TRI, true);
531
532 while (!SuperDefs.empty())
533 MI->addRegisterDefined(SuperDefs.pop_back_val(), TRI);
534
Jakob Stoklund Olesen5bfec692011-02-18 22:03:18 +0000535 DEBUG(dbgs() << "> " << *MI);
536
Matthias Braunf0b68d32017-03-17 00:41:39 +0000537 expandCopyBundle(*MI);
538
Matthias Braun152e7c82016-07-09 00:19:07 +0000539 // We can remove identity copies right now.
540 handleIdentityCopy(*MI);
Jakob Stoklund Olesen5bfec692011-02-18 22:03:18 +0000541 }
542 }
Jakob Stoklund Olesen5bfec692011-02-18 22:03:18 +0000543}