]>
git.proxmox.com Git - rustc.git/blob - src/llvm/lib/CodeGen/VirtRegMap.cpp
1 //===-- llvm/CodeGen/VirtRegMap.cpp - Virtual Register Map ----------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the VirtRegMap class.
12 // It also contains implementations of the Spiller interface, which, given a
13 // virtual register map and a machine function, eliminates all virtual
14 // references by replacing them with physical register references - adding spill
17 //===----------------------------------------------------------------------===//
19 #include "llvm/CodeGen/VirtRegMap.h"
20 #include "LiveDebugVariables.h"
21 #include "llvm/ADT/STLExtras.h"
22 #include "llvm/ADT/SparseSet.h"
23 #include "llvm/ADT/Statistic.h"
24 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
25 #include "llvm/CodeGen/LiveStackAnalysis.h"
26 #include "llvm/CodeGen/MachineFrameInfo.h"
27 #include "llvm/CodeGen/MachineFunction.h"
28 #include "llvm/CodeGen/MachineInstrBuilder.h"
29 #include "llvm/CodeGen/MachineRegisterInfo.h"
30 #include "llvm/CodeGen/Passes.h"
31 #include "llvm/IR/Function.h"
32 #include "llvm/Support/CommandLine.h"
33 #include "llvm/Support/Compiler.h"
34 #include "llvm/Support/Debug.h"
35 #include "llvm/Support/raw_ostream.h"
36 #include "llvm/Target/TargetInstrInfo.h"
37 #include "llvm/Target/TargetMachine.h"
38 #include "llvm/Target/TargetRegisterInfo.h"
39 #include "llvm/Target/TargetSubtargetInfo.h"
43 #define DEBUG_TYPE "regalloc"
45 STATISTIC(NumSpillSlots
, "Number of spill slots allocated");
46 STATISTIC(NumIdCopies
, "Number of identity moves eliminated after rewriting");
48 //===----------------------------------------------------------------------===//
49 // VirtRegMap implementation
50 //===----------------------------------------------------------------------===//
52 char VirtRegMap::ID
= 0;
54 INITIALIZE_PASS(VirtRegMap
, "virtregmap", "Virtual Register Map", false, false)
56 bool VirtRegMap::runOnMachineFunction(MachineFunction
&mf
) {
57 MRI
= &mf
.getRegInfo();
58 TII
= mf
.getSubtarget().getInstrInfo();
59 TRI
= mf
.getSubtarget().getRegisterInfo();
63 Virt2StackSlotMap
.clear();
64 Virt2SplitMap
.clear();
70 void VirtRegMap::grow() {
71 unsigned NumRegs
= MF
->getRegInfo().getNumVirtRegs();
72 Virt2PhysMap
.resize(NumRegs
);
73 Virt2StackSlotMap
.resize(NumRegs
);
74 Virt2SplitMap
.resize(NumRegs
);
77 unsigned VirtRegMap::createSpillSlot(const TargetRegisterClass
*RC
) {
78 int SS
= MF
->getFrameInfo()->CreateSpillStackObject(RC
->getSize(),
84 bool VirtRegMap::hasPreferredPhys(unsigned VirtReg
) {
85 unsigned Hint
= MRI
->getSimpleHint(VirtReg
);
88 if (TargetRegisterInfo::isVirtualRegister(Hint
))
90 return getPhys(VirtReg
) == Hint
;
93 bool VirtRegMap::hasKnownPreference(unsigned VirtReg
) {
94 std::pair
<unsigned, unsigned> Hint
= MRI
->getRegAllocationHint(VirtReg
);
95 if (TargetRegisterInfo::isPhysicalRegister(Hint
.second
))
97 if (TargetRegisterInfo::isVirtualRegister(Hint
.second
))
98 return hasPhys(Hint
.second
);
102 int VirtRegMap::assignVirt2StackSlot(unsigned virtReg
) {
103 assert(TargetRegisterInfo::isVirtualRegister(virtReg
));
104 assert(Virt2StackSlotMap
[virtReg
] == NO_STACK_SLOT
&&
105 "attempt to assign stack slot to already spilled register");
106 const TargetRegisterClass
* RC
= MF
->getRegInfo().getRegClass(virtReg
);
107 return Virt2StackSlotMap
[virtReg
] = createSpillSlot(RC
);
110 void VirtRegMap::assignVirt2StackSlot(unsigned virtReg
, int SS
) {
111 assert(TargetRegisterInfo::isVirtualRegister(virtReg
));
112 assert(Virt2StackSlotMap
[virtReg
] == NO_STACK_SLOT
&&
113 "attempt to assign stack slot to already spilled register");
115 (SS
>= MF
->getFrameInfo()->getObjectIndexBegin())) &&
116 "illegal fixed frame index");
117 Virt2StackSlotMap
[virtReg
] = SS
;
120 void VirtRegMap::print(raw_ostream
&OS
, const Module
*) const {
121 OS
<< "********** REGISTER MAP **********\n";
122 for (unsigned i
= 0, e
= MRI
->getNumVirtRegs(); i
!= e
; ++i
) {
123 unsigned Reg
= TargetRegisterInfo::index2VirtReg(i
);
124 if (Virt2PhysMap
[Reg
] != (unsigned)VirtRegMap::NO_PHYS_REG
) {
125 OS
<< '[' << PrintReg(Reg
, TRI
) << " -> "
126 << PrintReg(Virt2PhysMap
[Reg
], TRI
) << "] "
127 << TRI
->getRegClassName(MRI
->getRegClass(Reg
)) << "\n";
131 for (unsigned i
= 0, e
= MRI
->getNumVirtRegs(); i
!= e
; ++i
) {
132 unsigned Reg
= TargetRegisterInfo::index2VirtReg(i
);
133 if (Virt2StackSlotMap
[Reg
] != VirtRegMap::NO_STACK_SLOT
) {
134 OS
<< '[' << PrintReg(Reg
, TRI
) << " -> fi#" << Virt2StackSlotMap
[Reg
]
135 << "] " << TRI
->getRegClassName(MRI
->getRegClass(Reg
)) << "\n";
141 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
142 void VirtRegMap::dump() const {
147 //===----------------------------------------------------------------------===//
149 //===----------------------------------------------------------------------===//
151 // The VirtRegRewriter is the last of the register allocator passes.
152 // It rewrites virtual registers to physical registers as specified in the
153 // VirtRegMap analysis. It also updates live-in information on basic blocks
154 // according to LiveIntervals.
157 class VirtRegRewriter
: public MachineFunctionPass
{
159 const TargetMachine
*TM
;
160 const TargetRegisterInfo
*TRI
;
161 const TargetInstrInfo
*TII
;
162 MachineRegisterInfo
*MRI
;
163 SlotIndexes
*Indexes
;
166 SparseSet
<unsigned> PhysRegs
;
169 void addMBBLiveIns();
172 VirtRegRewriter() : MachineFunctionPass(ID
) {}
174 void getAnalysisUsage(AnalysisUsage
&AU
) const override
;
176 bool runOnMachineFunction(MachineFunction
&) override
;
178 } // end anonymous namespace
180 char &llvm::VirtRegRewriterID
= VirtRegRewriter::ID
;
182 INITIALIZE_PASS_BEGIN(VirtRegRewriter
, "virtregrewriter",
183 "Virtual Register Rewriter", false, false)
184 INITIALIZE_PASS_DEPENDENCY(SlotIndexes
)
185 INITIALIZE_PASS_DEPENDENCY(LiveIntervals
)
186 INITIALIZE_PASS_DEPENDENCY(LiveDebugVariables
)
187 INITIALIZE_PASS_DEPENDENCY(LiveStacks
)
188 INITIALIZE_PASS_DEPENDENCY(VirtRegMap
)
189 INITIALIZE_PASS_END(VirtRegRewriter
, "virtregrewriter",
190 "Virtual Register Rewriter", false, false)
192 char VirtRegRewriter::ID
= 0;
194 void VirtRegRewriter::getAnalysisUsage(AnalysisUsage
&AU
) const {
195 AU
.setPreservesCFG();
196 AU
.addRequired
<LiveIntervals
>();
197 AU
.addRequired
<SlotIndexes
>();
198 AU
.addPreserved
<SlotIndexes
>();
199 AU
.addRequired
<LiveDebugVariables
>();
200 AU
.addRequired
<LiveStacks
>();
201 AU
.addPreserved
<LiveStacks
>();
202 AU
.addRequired
<VirtRegMap
>();
203 MachineFunctionPass::getAnalysisUsage(AU
);
206 bool VirtRegRewriter::runOnMachineFunction(MachineFunction
&fn
) {
208 TM
= &MF
->getTarget();
209 TRI
= MF
->getSubtarget().getRegisterInfo();
210 TII
= MF
->getSubtarget().getInstrInfo();
211 MRI
= &MF
->getRegInfo();
212 Indexes
= &getAnalysis
<SlotIndexes
>();
213 LIS
= &getAnalysis
<LiveIntervals
>();
214 VRM
= &getAnalysis
<VirtRegMap
>();
215 DEBUG(dbgs() << "********** REWRITE VIRTUAL REGISTERS **********\n"
216 << "********** Function: "
217 << MF
->getName() << '\n');
220 // Add kill flags while we still have virtual registers.
221 LIS
->addKillFlags(VRM
);
223 // Live-in lists on basic blocks are required for physregs.
226 // Rewrite virtual registers.
229 // Write out new DBG_VALUE instructions.
230 getAnalysis
<LiveDebugVariables
>().emitDebugValues(VRM
);
232 // All machine operands and other references to virtual registers have been
233 // replaced. Remove the virtual registers and release all the transient data.
235 MRI
->clearVirtRegs();
239 // Compute MBB live-in lists from virtual register live ranges and their
241 void VirtRegRewriter::addMBBLiveIns() {
242 SmallVector
<MachineBasicBlock
*, 16> LiveIn
;
243 for (unsigned Idx
= 0, IdxE
= MRI
->getNumVirtRegs(); Idx
!= IdxE
; ++Idx
) {
244 unsigned VirtReg
= TargetRegisterInfo::index2VirtReg(Idx
);
245 if (MRI
->reg_nodbg_empty(VirtReg
))
247 LiveInterval
&LI
= LIS
->getInterval(VirtReg
);
248 if (LI
.empty() || LIS
->intervalIsInOneMBB(LI
))
250 // This is a virtual register that is live across basic blocks. Its
251 // assigned PhysReg must be marked as live-in to those blocks.
252 unsigned PhysReg
= VRM
->getPhys(VirtReg
);
253 assert(PhysReg
!= VirtRegMap::NO_PHYS_REG
&& "Unmapped virtual register.");
255 if (LI
.hasSubRanges()) {
256 for (LiveInterval::SubRange
&S
: LI
.subranges()) {
257 for (const auto &Seg
: S
.segments
) {
258 if (!Indexes
->findLiveInMBBs(Seg
.start
, Seg
.end
, LiveIn
))
260 for (MCSubRegIndexIterator
SR(PhysReg
, TRI
); SR
.isValid(); ++SR
) {
261 unsigned SubReg
= SR
.getSubReg();
262 unsigned SubRegIndex
= SR
.getSubRegIndex();
263 unsigned SubRegLaneMask
= TRI
->getSubRegIndexLaneMask(SubRegIndex
);
264 if ((SubRegLaneMask
& S
.LaneMask
) == 0)
266 for (unsigned i
= 0, e
= LiveIn
.size(); i
!= e
; ++i
) {
267 if (!LiveIn
[i
]->isLiveIn(SubReg
))
268 LiveIn
[i
]->addLiveIn(SubReg
);
275 // Scan the segments of LI.
276 for (const auto &Seg
: LI
.segments
) {
277 if (!Indexes
->findLiveInMBBs(Seg
.start
, Seg
.end
, LiveIn
))
279 for (unsigned i
= 0, e
= LiveIn
.size(); i
!= e
; ++i
)
280 if (!LiveIn
[i
]->isLiveIn(PhysReg
))
281 LiveIn
[i
]->addLiveIn(PhysReg
);
288 void VirtRegRewriter::rewrite() {
289 bool NoSubRegLiveness
= !MRI
->tracksSubRegLiveness();
290 SmallVector
<unsigned, 8> SuperDeads
;
291 SmallVector
<unsigned, 8> SuperDefs
;
292 SmallVector
<unsigned, 8> SuperKills
;
293 SmallPtrSet
<const MachineInstr
*, 4> NoReturnInsts
;
295 // Here we have a SparseSet to hold which PhysRegs are actually encountered
296 // in the MF we are about to iterate over so that later when we call
297 // setPhysRegUsed, we are only doing it for physRegs that were actually found
298 // in the program and not for all of the possible physRegs for the given
299 // target architecture. If the target has a lot of physRegs, then for a small
300 // program there will be a significant compile time reduction here.
302 PhysRegs
.setUniverse(TRI
->getNumRegs());
304 // The function with uwtable should guarantee that the stack unwinder
305 // can unwind the stack to the previous frame. Thus, we can't apply the
306 // noreturn optimization if the caller function has uwtable attribute.
307 bool HasUWTable
= MF
->getFunction()->hasFnAttribute(Attribute::UWTable
);
309 for (MachineFunction::iterator MBBI
= MF
->begin(), MBBE
= MF
->end();
310 MBBI
!= MBBE
; ++MBBI
) {
311 DEBUG(MBBI
->print(dbgs(), Indexes
));
312 bool IsExitBB
= MBBI
->succ_empty();
313 for (MachineBasicBlock::instr_iterator
314 MII
= MBBI
->instr_begin(), MIE
= MBBI
->instr_end(); MII
!= MIE
;) {
315 MachineInstr
*MI
= MII
;
318 // Check if this instruction is a call to a noreturn function. If this
319 // is a call to noreturn function and we don't need the stack unwinding
320 // functionality (i.e. this function does not have uwtable attribute and
321 // the callee function has the nounwind attribute), then we can ignore
322 // the definitions set by this instruction.
323 if (!HasUWTable
&& IsExitBB
&& MI
->isCall()) {
324 for (MachineInstr::mop_iterator MOI
= MI
->operands_begin(),
325 MOE
= MI
->operands_end(); MOI
!= MOE
; ++MOI
) {
326 MachineOperand
&MO
= *MOI
;
329 const Function
*Func
= dyn_cast
<Function
>(MO
.getGlobal());
330 if (!Func
|| !Func
->hasFnAttribute(Attribute::NoReturn
) ||
331 // We need to keep correct unwind information
332 // even if the function will not return, since the
333 // runtime may need it.
334 !Func
->hasFnAttribute(Attribute::NoUnwind
))
336 NoReturnInsts
.insert(MI
);
341 for (MachineInstr::mop_iterator MOI
= MI
->operands_begin(),
342 MOE
= MI
->operands_end(); MOI
!= MOE
; ++MOI
) {
343 MachineOperand
&MO
= *MOI
;
345 // Make sure MRI knows about registers clobbered by regmasks.
347 MRI
->addPhysRegsUsedFromRegMask(MO
.getRegMask());
349 // If we encounter a VirtReg or PhysReg then get at the PhysReg and add
350 // it to the physreg bitset. Later we use only the PhysRegs that were
351 // actually encountered in the MF to populate the MRI's used physregs.
352 if (MO
.isReg() && MO
.getReg())
354 TargetRegisterInfo::isVirtualRegister(MO
.getReg()) ?
355 VRM
->getPhys(MO
.getReg()) :
358 if (!MO
.isReg() || !TargetRegisterInfo::isVirtualRegister(MO
.getReg()))
360 unsigned VirtReg
= MO
.getReg();
361 unsigned PhysReg
= VRM
->getPhys(VirtReg
);
362 assert(PhysReg
!= VirtRegMap::NO_PHYS_REG
&&
363 "Instruction uses unmapped VirtReg");
364 assert(!MRI
->isReserved(PhysReg
) && "Reserved register assignment");
366 // Preserve semantics of sub-register operands.
367 if (MO
.getSubReg()) {
368 // A virtual register kill refers to the whole register, so we may
369 // have to add <imp-use,kill> operands for the super-register. A
370 // partial redef always kills and redefines the super-register.
371 if (NoSubRegLiveness
&& MO
.readsReg()
372 && (MO
.isDef() || MO
.isKill()))
373 SuperKills
.push_back(PhysReg
);
376 // The <def,undef> flag only makes sense for sub-register defs, and
377 // we are substituting a full physreg. An <imp-use,kill> operand
378 // from the SuperKills list will represent the partial read of the
380 MO
.setIsUndef(false);
382 // Also add implicit defs for the super-register.
383 if (NoSubRegLiveness
) {
385 SuperDeads
.push_back(PhysReg
);
387 SuperDefs
.push_back(PhysReg
);
391 // PhysReg operands cannot have subregister indexes.
392 PhysReg
= TRI
->getSubReg(PhysReg
, MO
.getSubReg());
393 assert(PhysReg
&& "Invalid SubReg for physical register");
396 // Rewrite. Note we could have used MachineOperand::substPhysReg(), but
397 // we need the inlining here.
401 // Add any missing super-register kills after rewriting the whole
403 while (!SuperKills
.empty())
404 MI
->addRegisterKilled(SuperKills
.pop_back_val(), TRI
, true);
406 while (!SuperDeads
.empty())
407 MI
->addRegisterDead(SuperDeads
.pop_back_val(), TRI
, true);
409 while (!SuperDefs
.empty())
410 MI
->addRegisterDefined(SuperDefs
.pop_back_val(), TRI
);
412 DEBUG(dbgs() << "> " << *MI
);
414 // Finally, remove any identity copies.
415 if (MI
->isIdentityCopy()) {
417 if (MI
->getNumOperands() == 2) {
418 DEBUG(dbgs() << "Deleting identity copy.\n");
420 Indexes
->removeMachineInstrFromMaps(MI
);
421 // It's safe to erase MI because MII has already been incremented.
422 MI
->eraseFromParent();
424 // Transform identity copy to a KILL to deal with subregisters.
425 MI
->setDesc(TII
->get(TargetOpcode::KILL
));
426 DEBUG(dbgs() << "Identity copy: " << *MI
);
432 // Tell MRI about physical registers in use.
433 if (NoReturnInsts
.empty()) {
434 for (SparseSet
<unsigned>::iterator
435 RegI
= PhysRegs
.begin(), E
= PhysRegs
.end(); RegI
!= E
; ++RegI
)
436 if (!MRI
->reg_nodbg_empty(*RegI
))
437 MRI
->setPhysRegUsed(*RegI
);
439 for (SparseSet
<unsigned>::iterator
440 I
= PhysRegs
.begin(), E
= PhysRegs
.end(); I
!= E
; ++I
) {
442 if (MRI
->reg_nodbg_empty(Reg
))
444 // Check if this register has a use that will impact the rest of the
445 // code. Uses in debug and noreturn instructions do not impact the
447 for (MachineInstr
&It
: MRI
->reg_nodbg_instructions(Reg
)) {
448 if (!NoReturnInsts
.count(&It
)) {
449 MRI
->setPhysRegUsed(Reg
);