1 //===-- RegAllocFast.cpp - A fast register allocator for debug code -------===//
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 register allocator allocates registers to a basic block at a time,
11 // attempting to keep values in registers and reusing registers as appropriate.
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "regalloc"
16 #include "llvm/BasicBlock.h"
17 #include "llvm/CodeGen/MachineFunctionPass.h"
18 #include "llvm/CodeGen/MachineInstr.h"
19 #include "llvm/CodeGen/MachineInstrBuilder.h"
20 #include "llvm/CodeGen/MachineFrameInfo.h"
21 #include "llvm/CodeGen/MachineRegisterInfo.h"
22 #include "llvm/CodeGen/Passes.h"
23 #include "llvm/CodeGen/RegAllocRegistry.h"
24 #include "llvm/Target/TargetInstrInfo.h"
25 #include "llvm/Target/TargetMachine.h"
26 #include "llvm/Support/CommandLine.h"
27 #include "llvm/Support/Debug.h"
28 #include "llvm/Support/ErrorHandling.h"
29 #include "llvm/Support/raw_ostream.h"
30 #include "llvm/ADT/DenseMap.h"
31 #include "llvm/ADT/IndexedMap.h"
32 #include "llvm/ADT/SmallSet.h"
33 #include "llvm/ADT/SmallVector.h"
34 #include "llvm/ADT/Statistic.h"
35 #include "llvm/ADT/STLExtras.h"
39 STATISTIC(NumStores
, "Number of stores added");
40 STATISTIC(NumLoads
, "Number of loads added");
41 STATISTIC(NumCopies
, "Number of copies coalesced");
43 static RegisterRegAlloc
44 fastRegAlloc("fast", "fast register allocator", createFastRegisterAllocator
);
47 class RAFast
: public MachineFunctionPass
{
50 RAFast() : MachineFunctionPass(ID
), StackSlotForVirtReg(-1),
51 isBulkSpilling(false) {}
53 const TargetMachine
*TM
;
55 MachineRegisterInfo
*MRI
;
56 const TargetRegisterInfo
*TRI
;
57 const TargetInstrInfo
*TII
;
59 // Basic block currently being allocated.
60 MachineBasicBlock
*MBB
;
62 // StackSlotForVirtReg - Maps virtual regs to the frame index where these
63 // values are spilled.
64 IndexedMap
<int, VirtReg2IndexFunctor
> StackSlotForVirtReg
;
66 // Everything we know about a live virtual register.
68 MachineInstr
*LastUse
; // Last instr to use reg.
69 unsigned PhysReg
; // Currently held here.
70 unsigned short LastOpNum
; // OpNum on LastUse.
71 bool Dirty
; // Register needs spill.
73 LiveReg(unsigned p
=0) : LastUse(0), PhysReg(p
), LastOpNum(0),
77 typedef DenseMap
<unsigned, LiveReg
> LiveRegMap
;
78 typedef LiveRegMap::value_type LiveRegEntry
;
80 // LiveVirtRegs - This map contains entries for each virtual register
81 // that is currently available in a physical register.
82 LiveRegMap LiveVirtRegs
;
84 DenseMap
<unsigned, MachineInstr
*> LiveDbgValueMap
;
86 // RegState - Track the state of a physical register.
88 // A disabled register is not available for allocation, but an alias may
89 // be in use. A register can only be moved out of the disabled state if
90 // all aliases are disabled.
93 // A free register is not currently in use and can be allocated
94 // immediately without checking aliases.
97 // A reserved register has been assigned expolicitly (e.g., setting up a
98 // call parameter), and it remains reserved until it is used.
101 // A register state may also be a virtual register number, indication that
102 // the physical register is currently allocated to a virtual register. In
103 // that case, LiveVirtRegs contains the inverse mapping.
106 // PhysRegState - One of the RegState enums, or a virtreg.
107 std::vector
<unsigned> PhysRegState
;
109 // UsedInInstr - BitVector of physregs that are used in the current
110 // instruction, and so cannot be allocated.
111 BitVector UsedInInstr
;
113 // Allocatable - vector of allocatable physical registers.
114 BitVector Allocatable
;
116 // SkippedInstrs - Descriptors of instructions whose clobber list was ignored
117 // because all registers were spilled. It is still necessary to mark all the
118 // clobbered registers as used by the function.
119 SmallPtrSet
<const TargetInstrDesc
*, 4> SkippedInstrs
;
121 // isBulkSpilling - This flag is set when LiveRegMap will be cleared
122 // completely after spilling all live registers. LiveRegMap entries should
129 spillImpossible
= ~0u
132 virtual const char *getPassName() const {
133 return "Fast Register Allocator";
136 virtual void getAnalysisUsage(AnalysisUsage
&AU
) const {
137 AU
.setPreservesCFG();
138 AU
.addRequiredID(PHIEliminationID
);
139 AU
.addRequiredID(TwoAddressInstructionPassID
);
140 MachineFunctionPass::getAnalysisUsage(AU
);
144 bool runOnMachineFunction(MachineFunction
&Fn
);
145 void AllocateBasicBlock();
146 void handleThroughOperands(MachineInstr
*MI
,
147 SmallVectorImpl
<unsigned> &VirtDead
);
148 int getStackSpaceFor(unsigned VirtReg
, const TargetRegisterClass
*RC
);
149 bool isLastUseOfLocalReg(MachineOperand
&);
151 void addKillFlag(const LiveReg
&);
152 void killVirtReg(LiveRegMap::iterator
);
153 void killVirtReg(unsigned VirtReg
);
154 void spillVirtReg(MachineBasicBlock::iterator MI
, LiveRegMap::iterator
);
155 void spillVirtReg(MachineBasicBlock::iterator MI
, unsigned VirtReg
);
157 void usePhysReg(MachineOperand
&);
158 void definePhysReg(MachineInstr
*MI
, unsigned PhysReg
, RegState NewState
);
159 unsigned calcSpillCost(unsigned PhysReg
) const;
160 void assignVirtToPhysReg(LiveRegEntry
&LRE
, unsigned PhysReg
);
161 void allocVirtReg(MachineInstr
*MI
, LiveRegEntry
&LRE
, unsigned Hint
);
162 LiveRegMap::iterator
defineVirtReg(MachineInstr
*MI
, unsigned OpNum
,
163 unsigned VirtReg
, unsigned Hint
);
164 LiveRegMap::iterator
reloadVirtReg(MachineInstr
*MI
, unsigned OpNum
,
165 unsigned VirtReg
, unsigned Hint
);
166 void spillAll(MachineInstr
*MI
);
167 bool setPhysReg(MachineInstr
*MI
, unsigned OpNum
, unsigned PhysReg
);
172 /// getStackSpaceFor - This allocates space for the specified virtual register
173 /// to be held on the stack.
174 int RAFast::getStackSpaceFor(unsigned VirtReg
, const TargetRegisterClass
*RC
) {
175 // Find the location Reg would belong...
176 int SS
= StackSlotForVirtReg
[VirtReg
];
178 return SS
; // Already has space allocated?
180 // Allocate a new stack object for this spill location...
181 int FrameIdx
= MF
->getFrameInfo()->CreateSpillStackObject(RC
->getSize(),
185 StackSlotForVirtReg
[VirtReg
] = FrameIdx
;
189 /// isLastUseOfLocalReg - Return true if MO is the only remaining reference to
190 /// its virtual register, and it is guaranteed to be a block-local register.
192 bool RAFast::isLastUseOfLocalReg(MachineOperand
&MO
) {
193 // Check for non-debug uses or defs following MO.
194 // This is the most likely way to fail - fast path it.
195 MachineOperand
*Next
= &MO
;
196 while ((Next
= Next
->getNextOperandForReg()))
197 if (!Next
->isDebug())
200 // If the register has ever been spilled or reloaded, we conservatively assume
201 // it is a global register used in multiple blocks.
202 if (StackSlotForVirtReg
[MO
.getReg()] != -1)
205 // Check that the use/def chain has exactly one operand - MO.
206 return &MRI
->reg_nodbg_begin(MO
.getReg()).getOperand() == &MO
;
209 /// addKillFlag - Set kill flags on last use of a virtual register.
210 void RAFast::addKillFlag(const LiveReg
&LR
) {
211 if (!LR
.LastUse
) return;
212 MachineOperand
&MO
= LR
.LastUse
->getOperand(LR
.LastOpNum
);
213 if (MO
.isUse() && !LR
.LastUse
->isRegTiedToDefOperand(LR
.LastOpNum
)) {
214 if (MO
.getReg() == LR
.PhysReg
)
217 LR
.LastUse
->addRegisterKilled(LR
.PhysReg
, TRI
, true);
221 /// killVirtReg - Mark virtreg as no longer available.
222 void RAFast::killVirtReg(LiveRegMap::iterator LRI
) {
223 addKillFlag(LRI
->second
);
224 const LiveReg
&LR
= LRI
->second
;
225 assert(PhysRegState
[LR
.PhysReg
] == LRI
->first
&& "Broken RegState mapping");
226 PhysRegState
[LR
.PhysReg
] = regFree
;
227 // Erase from LiveVirtRegs unless we're spilling in bulk.
229 LiveVirtRegs
.erase(LRI
);
232 /// killVirtReg - Mark virtreg as no longer available.
233 void RAFast::killVirtReg(unsigned VirtReg
) {
234 assert(TargetRegisterInfo::isVirtualRegister(VirtReg
) &&
235 "killVirtReg needs a virtual register");
236 LiveRegMap::iterator LRI
= LiveVirtRegs
.find(VirtReg
);
237 if (LRI
!= LiveVirtRegs
.end())
241 /// spillVirtReg - This method spills the value specified by VirtReg into the
242 /// corresponding stack slot if needed.
243 void RAFast::spillVirtReg(MachineBasicBlock::iterator MI
, unsigned VirtReg
) {
244 assert(TargetRegisterInfo::isVirtualRegister(VirtReg
) &&
245 "Spilling a physical register is illegal!");
246 LiveRegMap::iterator LRI
= LiveVirtRegs
.find(VirtReg
);
247 assert(LRI
!= LiveVirtRegs
.end() && "Spilling unmapped virtual register");
248 spillVirtReg(MI
, LRI
);
251 /// spillVirtReg - Do the actual work of spilling.
252 void RAFast::spillVirtReg(MachineBasicBlock::iterator MI
,
253 LiveRegMap::iterator LRI
) {
254 LiveReg
&LR
= LRI
->second
;
255 assert(PhysRegState
[LR
.PhysReg
] == LRI
->first
&& "Broken RegState mapping");
258 // If this physreg is used by the instruction, we want to kill it on the
259 // instruction, not on the spill.
260 bool SpillKill
= LR
.LastUse
!= MI
;
262 DEBUG(dbgs() << "Spilling %reg" << LRI
->first
263 << " in " << TRI
->getName(LR
.PhysReg
));
264 const TargetRegisterClass
*RC
= MRI
->getRegClass(LRI
->first
);
265 int FI
= getStackSpaceFor(LRI
->first
, RC
);
266 DEBUG(dbgs() << " to stack slot #" << FI
<< "\n");
267 TII
->storeRegToStackSlot(*MBB
, MI
, LR
.PhysReg
, SpillKill
, FI
, RC
, TRI
);
268 ++NumStores
; // Update statistics
270 // If this register is used by DBG_VALUE then insert new DBG_VALUE to
271 // identify spilled location as the place to find corresponding variable's
273 if (MachineInstr
*DBG
= LiveDbgValueMap
.lookup(LRI
->first
)) {
274 const MDNode
*MDPtr
=
275 DBG
->getOperand(DBG
->getNumOperands()-1).getMetadata();
277 if (DBG
->getOperand(1).isImm())
278 Offset
= DBG
->getOperand(1).getImm();
280 if (MI
== MBB
->end()) {
281 // If MI is at basic block end then use last instruction's location.
282 MachineBasicBlock::iterator EI
= MI
;
283 DL
= (--EI
)->getDebugLoc();
286 DL
= MI
->getDebugLoc();
287 if (MachineInstr
*NewDV
=
288 TII
->emitFrameIndexDebugValue(*MF
, FI
, Offset
, MDPtr
, DL
)) {
289 MachineBasicBlock
*MBB
= DBG
->getParent();
290 MBB
->insert(MI
, NewDV
);
291 DEBUG(dbgs() << "Inserting debug info due to spill:" << "\n" << *NewDV
);
292 LiveDbgValueMap
[LRI
->first
] = NewDV
;
296 LR
.LastUse
= 0; // Don't kill register again
301 /// spillAll - Spill all dirty virtregs without killing them.
302 void RAFast::spillAll(MachineInstr
*MI
) {
303 if (LiveVirtRegs
.empty()) return;
304 isBulkSpilling
= true;
305 // The LiveRegMap is keyed by an unsigned (the virtreg number), so the order
306 // of spilling here is deterministic, if arbitrary.
307 for (LiveRegMap::iterator i
= LiveVirtRegs
.begin(), e
= LiveVirtRegs
.end();
310 LiveVirtRegs
.clear();
311 isBulkSpilling
= false;
314 /// usePhysReg - Handle the direct use of a physical register.
315 /// Check that the register is not used by a virtreg.
316 /// Kill the physreg, marking it free.
317 /// This may add implicit kills to MO->getParent() and invalidate MO.
318 void RAFast::usePhysReg(MachineOperand
&MO
) {
319 unsigned PhysReg
= MO
.getReg();
320 assert(TargetRegisterInfo::isPhysicalRegister(PhysReg
) &&
321 "Bad usePhysReg operand");
323 switch (PhysRegState
[PhysReg
]) {
327 PhysRegState
[PhysReg
] = regFree
;
330 UsedInInstr
.set(PhysReg
);
334 // The physreg was allocated to a virtual register. That means to value we
335 // wanted has been clobbered.
336 llvm_unreachable("Instruction uses an allocated register");
339 // Maybe a superregister is reserved?
340 for (const unsigned *AS
= TRI
->getAliasSet(PhysReg
);
341 unsigned Alias
= *AS
; ++AS
) {
342 switch (PhysRegState
[Alias
]) {
346 assert(TRI
->isSuperRegister(PhysReg
, Alias
) &&
347 "Instruction is not using a subregister of a reserved register");
348 // Leave the superregister in the working set.
349 PhysRegState
[Alias
] = regFree
;
350 UsedInInstr
.set(Alias
);
351 MO
.getParent()->addRegisterKilled(Alias
, TRI
, true);
354 if (TRI
->isSuperRegister(PhysReg
, Alias
)) {
355 // Leave the superregister in the working set.
356 UsedInInstr
.set(Alias
);
357 MO
.getParent()->addRegisterKilled(Alias
, TRI
, true);
360 // Some other alias was in the working set - clear it.
361 PhysRegState
[Alias
] = regDisabled
;
364 llvm_unreachable("Instruction uses an alias of an allocated register");
368 // All aliases are disabled, bring register into working set.
369 PhysRegState
[PhysReg
] = regFree
;
370 UsedInInstr
.set(PhysReg
);
374 /// definePhysReg - Mark PhysReg as reserved or free after spilling any
375 /// virtregs. This is very similar to defineVirtReg except the physreg is
376 /// reserved instead of allocated.
377 void RAFast::definePhysReg(MachineInstr
*MI
, unsigned PhysReg
,
379 UsedInInstr
.set(PhysReg
);
380 switch (unsigned VirtReg
= PhysRegState
[PhysReg
]) {
384 spillVirtReg(MI
, VirtReg
);
388 PhysRegState
[PhysReg
] = NewState
;
392 // This is a disabled register, disable all aliases.
393 PhysRegState
[PhysReg
] = NewState
;
394 for (const unsigned *AS
= TRI
->getAliasSet(PhysReg
);
395 unsigned Alias
= *AS
; ++AS
) {
396 UsedInInstr
.set(Alias
);
397 switch (unsigned VirtReg
= PhysRegState
[Alias
]) {
401 spillVirtReg(MI
, VirtReg
);
405 PhysRegState
[Alias
] = regDisabled
;
406 if (TRI
->isSuperRegister(PhysReg
, Alias
))
414 // calcSpillCost - Return the cost of spilling clearing out PhysReg and
415 // aliases so it is free for allocation.
416 // Returns 0 when PhysReg is free or disabled with all aliases disabled - it
417 // can be allocated directly.
418 // Returns spillImpossible when PhysReg or an alias can't be spilled.
419 unsigned RAFast::calcSpillCost(unsigned PhysReg
) const {
420 if (UsedInInstr
.test(PhysReg
))
421 return spillImpossible
;
422 switch (unsigned VirtReg
= PhysRegState
[PhysReg
]) {
428 return spillImpossible
;
430 return LiveVirtRegs
.lookup(VirtReg
).Dirty
? spillDirty
: spillClean
;
433 // This is a disabled register, add up const of aliases.
435 for (const unsigned *AS
= TRI
->getAliasSet(PhysReg
);
436 unsigned Alias
= *AS
; ++AS
) {
437 if (UsedInInstr
.test(Alias
))
438 return spillImpossible
;
439 switch (unsigned VirtReg
= PhysRegState
[Alias
]) {
446 return spillImpossible
;
448 Cost
+= LiveVirtRegs
.lookup(VirtReg
).Dirty
? spillDirty
: spillClean
;
456 /// assignVirtToPhysReg - This method updates local state so that we know
457 /// that PhysReg is the proper container for VirtReg now. The physical
458 /// register must not be used for anything else when this is called.
460 void RAFast::assignVirtToPhysReg(LiveRegEntry
&LRE
, unsigned PhysReg
) {
461 DEBUG(dbgs() << "Assigning %reg" << LRE
.first
<< " to "
462 << TRI
->getName(PhysReg
) << "\n");
463 PhysRegState
[PhysReg
] = LRE
.first
;
464 assert(!LRE
.second
.PhysReg
&& "Already assigned a physreg");
465 LRE
.second
.PhysReg
= PhysReg
;
468 /// allocVirtReg - Allocate a physical register for VirtReg.
469 void RAFast::allocVirtReg(MachineInstr
*MI
, LiveRegEntry
&LRE
, unsigned Hint
) {
470 const unsigned VirtReg
= LRE
.first
;
472 assert(TargetRegisterInfo::isVirtualRegister(VirtReg
) &&
473 "Can only allocate virtual registers");
475 const TargetRegisterClass
*RC
= MRI
->getRegClass(VirtReg
);
477 // Ignore invalid hints.
478 if (Hint
&& (!TargetRegisterInfo::isPhysicalRegister(Hint
) ||
479 !RC
->contains(Hint
) || !Allocatable
.test(Hint
)))
482 // Take hint when possible.
484 switch(calcSpillCost(Hint
)) {
486 definePhysReg(MI
, Hint
, regFree
);
489 return assignVirtToPhysReg(LRE
, Hint
);
490 case spillImpossible
:
495 TargetRegisterClass::iterator AOB
= RC
->allocation_order_begin(*MF
);
496 TargetRegisterClass::iterator AOE
= RC
->allocation_order_end(*MF
);
498 // First try to find a completely free register.
499 for (TargetRegisterClass::iterator I
= AOB
; I
!= AOE
; ++I
) {
500 unsigned PhysReg
= *I
;
501 if (PhysRegState
[PhysReg
] == regFree
&& !UsedInInstr
.test(PhysReg
))
502 return assignVirtToPhysReg(LRE
, PhysReg
);
505 DEBUG(dbgs() << "Allocating %reg" << VirtReg
<< " from " << RC
->getName()
508 unsigned BestReg
= 0, BestCost
= spillImpossible
;
509 for (TargetRegisterClass::iterator I
= AOB
; I
!= AOE
; ++I
) {
510 unsigned Cost
= calcSpillCost(*I
);
511 // Cost is 0 when all aliases are already disabled.
513 return assignVirtToPhysReg(LRE
, *I
);
515 BestReg
= *I
, BestCost
= Cost
;
519 definePhysReg(MI
, BestReg
, regFree
);
520 return assignVirtToPhysReg(LRE
, BestReg
);
523 // Nothing we can do.
525 raw_string_ostream
Msg(msg
);
526 Msg
<< "Ran out of registers during register allocation!";
527 if (MI
->isInlineAsm()) {
528 Msg
<< "\nPlease check your inline asm statement for "
529 << "invalid constraints:\n";
532 report_fatal_error(Msg
.str());
535 /// defineVirtReg - Allocate a register for VirtReg and mark it as dirty.
536 RAFast::LiveRegMap::iterator
537 RAFast::defineVirtReg(MachineInstr
*MI
, unsigned OpNum
,
538 unsigned VirtReg
, unsigned Hint
) {
539 assert(TargetRegisterInfo::isVirtualRegister(VirtReg
) &&
540 "Not a virtual register");
541 LiveRegMap::iterator LRI
;
543 tie(LRI
, New
) = LiveVirtRegs
.insert(std::make_pair(VirtReg
, LiveReg()));
544 LiveReg
&LR
= LRI
->second
;
546 // If there is no hint, peek at the only use of this register.
547 if ((!Hint
|| !TargetRegisterInfo::isPhysicalRegister(Hint
)) &&
548 MRI
->hasOneNonDBGUse(VirtReg
)) {
549 const MachineInstr
&UseMI
= *MRI
->use_nodbg_begin(VirtReg
);
550 // It's a copy, use the destination register as a hint.
551 if (UseMI
.isCopyLike())
552 Hint
= UseMI
.getOperand(0).getReg();
554 allocVirtReg(MI
, *LRI
, Hint
);
555 } else if (LR
.LastUse
) {
556 // Redefining a live register - kill at the last use, unless it is this
557 // instruction defining VirtReg multiple times.
558 if (LR
.LastUse
!= MI
|| LR
.LastUse
->getOperand(LR
.LastOpNum
).isUse())
561 assert(LR
.PhysReg
&& "Register not assigned");
563 LR
.LastOpNum
= OpNum
;
565 UsedInInstr
.set(LR
.PhysReg
);
569 /// reloadVirtReg - Make sure VirtReg is available in a physreg and return it.
570 RAFast::LiveRegMap::iterator
571 RAFast::reloadVirtReg(MachineInstr
*MI
, unsigned OpNum
,
572 unsigned VirtReg
, unsigned Hint
) {
573 assert(TargetRegisterInfo::isVirtualRegister(VirtReg
) &&
574 "Not a virtual register");
575 LiveRegMap::iterator LRI
;
577 tie(LRI
, New
) = LiveVirtRegs
.insert(std::make_pair(VirtReg
, LiveReg()));
578 LiveReg
&LR
= LRI
->second
;
579 MachineOperand
&MO
= MI
->getOperand(OpNum
);
581 allocVirtReg(MI
, *LRI
, Hint
);
582 const TargetRegisterClass
*RC
= MRI
->getRegClass(VirtReg
);
583 int FrameIndex
= getStackSpaceFor(VirtReg
, RC
);
584 DEBUG(dbgs() << "Reloading %reg" << VirtReg
<< " into "
585 << TRI
->getName(LR
.PhysReg
) << "\n");
586 TII
->loadRegFromStackSlot(*MBB
, MI
, LR
.PhysReg
, FrameIndex
, RC
, TRI
);
588 } else if (LR
.Dirty
) {
589 if (isLastUseOfLocalReg(MO
)) {
590 DEBUG(dbgs() << "Killing last use: " << MO
<< "\n");
595 } else if (MO
.isKill()) {
596 DEBUG(dbgs() << "Clearing dubious kill: " << MO
<< "\n");
598 } else if (MO
.isDead()) {
599 DEBUG(dbgs() << "Clearing dubious dead: " << MO
<< "\n");
602 } else if (MO
.isKill()) {
603 // We must remove kill flags from uses of reloaded registers because the
604 // register would be killed immediately, and there might be a second use:
605 // %foo = OR %x<kill>, %x
606 // This would cause a second reload of %x into a different register.
607 DEBUG(dbgs() << "Clearing clean kill: " << MO
<< "\n");
609 } else if (MO
.isDead()) {
610 DEBUG(dbgs() << "Clearing clean dead: " << MO
<< "\n");
613 assert(LR
.PhysReg
&& "Register not assigned");
615 LR
.LastOpNum
= OpNum
;
616 UsedInInstr
.set(LR
.PhysReg
);
620 // setPhysReg - Change operand OpNum in MI the refer the PhysReg, considering
621 // subregs. This may invalidate any operand pointers.
622 // Return true if the operand kills its register.
623 bool RAFast::setPhysReg(MachineInstr
*MI
, unsigned OpNum
, unsigned PhysReg
) {
624 MachineOperand
&MO
= MI
->getOperand(OpNum
);
625 if (!MO
.getSubReg()) {
627 return MO
.isKill() || MO
.isDead();
630 // Handle subregister index.
631 MO
.setReg(PhysReg
? TRI
->getSubReg(PhysReg
, MO
.getSubReg()) : 0);
634 // A kill flag implies killing the full register. Add corresponding super
637 MI
->addRegisterKilled(PhysReg
, TRI
, true);
643 // Handle special instruction operand like early clobbers and tied ops when
644 // there are additional physreg defines.
645 void RAFast::handleThroughOperands(MachineInstr
*MI
,
646 SmallVectorImpl
<unsigned> &VirtDead
) {
647 DEBUG(dbgs() << "Scanning for through registers:");
648 SmallSet
<unsigned, 8> ThroughRegs
;
649 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
650 MachineOperand
&MO
= MI
->getOperand(i
);
651 if (!MO
.isReg()) continue;
652 unsigned Reg
= MO
.getReg();
653 if (!Reg
|| TargetRegisterInfo::isPhysicalRegister(Reg
)) continue;
654 if (MO
.isEarlyClobber() || MI
->isRegTiedToDefOperand(i
) ||
655 (MO
.getSubReg() && MI
->readsVirtualRegister(Reg
))) {
656 if (ThroughRegs
.insert(Reg
))
657 DEBUG(dbgs() << " %reg" << Reg
);
661 // If any physreg defines collide with preallocated through registers,
662 // we must spill and reallocate.
663 DEBUG(dbgs() << "\nChecking for physdef collisions.\n");
664 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
665 MachineOperand
&MO
= MI
->getOperand(i
);
666 if (!MO
.isReg() || !MO
.isDef()) continue;
667 unsigned Reg
= MO
.getReg();
668 if (!Reg
|| !TargetRegisterInfo::isPhysicalRegister(Reg
)) continue;
669 UsedInInstr
.set(Reg
);
670 if (ThroughRegs
.count(PhysRegState
[Reg
]))
671 definePhysReg(MI
, Reg
, regFree
);
672 for (const unsigned *AS
= TRI
->getAliasSet(Reg
); *AS
; ++AS
) {
673 UsedInInstr
.set(*AS
);
674 if (ThroughRegs
.count(PhysRegState
[*AS
]))
675 definePhysReg(MI
, *AS
, regFree
);
679 SmallVector
<unsigned, 8> PartialDefs
;
680 DEBUG(dbgs() << "Allocating tied uses and early clobbers.\n");
681 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
682 MachineOperand
&MO
= MI
->getOperand(i
);
683 if (!MO
.isReg()) continue;
684 unsigned Reg
= MO
.getReg();
685 if (!Reg
|| TargetRegisterInfo::isPhysicalRegister(Reg
)) continue;
688 if (!MI
->isRegTiedToDefOperand(i
, &DefIdx
)) continue;
689 DEBUG(dbgs() << "Operand " << i
<< "("<< MO
<< ") is tied to operand "
691 LiveRegMap::iterator LRI
= reloadVirtReg(MI
, i
, Reg
, 0);
692 unsigned PhysReg
= LRI
->second
.PhysReg
;
693 setPhysReg(MI
, i
, PhysReg
);
694 // Note: we don't update the def operand yet. That would cause the normal
695 // def-scan to attempt spilling.
696 } else if (MO
.getSubReg() && MI
->readsVirtualRegister(Reg
)) {
697 DEBUG(dbgs() << "Partial redefine: " << MO
<< "\n");
698 // Reload the register, but don't assign to the operand just yet.
699 // That would confuse the later phys-def processing pass.
700 LiveRegMap::iterator LRI
= reloadVirtReg(MI
, i
, Reg
, 0);
701 PartialDefs
.push_back(LRI
->second
.PhysReg
);
702 } else if (MO
.isEarlyClobber()) {
703 // Note: defineVirtReg may invalidate MO.
704 LiveRegMap::iterator LRI
= defineVirtReg(MI
, i
, Reg
, 0);
705 unsigned PhysReg
= LRI
->second
.PhysReg
;
706 if (setPhysReg(MI
, i
, PhysReg
))
707 VirtDead
.push_back(Reg
);
711 // Restore UsedInInstr to a state usable for allocating normal virtual uses.
713 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
714 MachineOperand
&MO
= MI
->getOperand(i
);
715 if (!MO
.isReg() || (MO
.isDef() && !MO
.isEarlyClobber())) continue;
716 unsigned Reg
= MO
.getReg();
717 if (!Reg
|| !TargetRegisterInfo::isPhysicalRegister(Reg
)) continue;
718 UsedInInstr
.set(Reg
);
719 for (const unsigned *AS
= TRI
->getAliasSet(Reg
); *AS
; ++AS
)
720 UsedInInstr
.set(*AS
);
723 // Also mark PartialDefs as used to avoid reallocation.
724 for (unsigned i
= 0, e
= PartialDefs
.size(); i
!= e
; ++i
)
725 UsedInInstr
.set(PartialDefs
[i
]);
728 void RAFast::AllocateBasicBlock() {
729 DEBUG(dbgs() << "\nAllocating " << *MBB
);
731 PhysRegState
.assign(TRI
->getNumRegs(), regDisabled
);
732 assert(LiveVirtRegs
.empty() && "Mapping not cleared form last block?");
734 MachineBasicBlock::iterator MII
= MBB
->begin();
736 // Add live-in registers as live.
737 for (MachineBasicBlock::livein_iterator I
= MBB
->livein_begin(),
738 E
= MBB
->livein_end(); I
!= E
; ++I
)
739 if (Allocatable
.test(*I
))
740 definePhysReg(MII
, *I
, regReserved
);
742 SmallVector
<unsigned, 8> VirtDead
;
743 SmallVector
<MachineInstr
*, 32> Coalesced
;
745 // Otherwise, sequentially allocate each instruction in the MBB.
746 while (MII
!= MBB
->end()) {
747 MachineInstr
*MI
= MII
++;
748 const TargetInstrDesc
&TID
= MI
->getDesc();
750 dbgs() << "\n>> " << *MI
<< "Regs:";
751 for (unsigned Reg
= 1, E
= TRI
->getNumRegs(); Reg
!= E
; ++Reg
) {
752 if (PhysRegState
[Reg
] == regDisabled
) continue;
753 dbgs() << " " << TRI
->getName(Reg
);
754 switch(PhysRegState
[Reg
]) {
761 dbgs() << "=%reg" << PhysRegState
[Reg
];
762 if (LiveVirtRegs
[PhysRegState
[Reg
]].Dirty
)
764 assert(LiveVirtRegs
[PhysRegState
[Reg
]].PhysReg
== Reg
&&
770 // Check that LiveVirtRegs is the inverse.
771 for (LiveRegMap::iterator i
= LiveVirtRegs
.begin(),
772 e
= LiveVirtRegs
.end(); i
!= e
; ++i
) {
773 assert(TargetRegisterInfo::isVirtualRegister(i
->first
) &&
775 assert(TargetRegisterInfo::isPhysicalRegister(i
->second
.PhysReg
) &&
777 assert(PhysRegState
[i
->second
.PhysReg
] == i
->first
&&
782 // Debug values are not allowed to change codegen in any way.
783 if (MI
->isDebugValue()) {
784 bool ScanDbgValue
= true;
785 while (ScanDbgValue
) {
786 ScanDbgValue
= false;
787 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
788 MachineOperand
&MO
= MI
->getOperand(i
);
789 if (!MO
.isReg()) continue;
790 unsigned Reg
= MO
.getReg();
791 if (!Reg
|| TargetRegisterInfo::isPhysicalRegister(Reg
)) continue;
792 LiveDbgValueMap
[Reg
] = MI
;
793 LiveRegMap::iterator LRI
= LiveVirtRegs
.find(Reg
);
794 if (LRI
!= LiveVirtRegs
.end())
795 setPhysReg(MI
, i
, LRI
->second
.PhysReg
);
797 int SS
= StackSlotForVirtReg
[Reg
];
799 MO
.setReg(0); // We can't allocate a physreg for a DebugValue, sorry!
801 // Modify DBG_VALUE now that the value is in a spill slot.
802 int64_t Offset
= MI
->getOperand(1).getImm();
803 const MDNode
*MDPtr
=
804 MI
->getOperand(MI
->getNumOperands()-1).getMetadata();
805 DebugLoc DL
= MI
->getDebugLoc();
806 if (MachineInstr
*NewDV
=
807 TII
->emitFrameIndexDebugValue(*MF
, SS
, Offset
, MDPtr
, DL
)) {
808 DEBUG(dbgs() << "Modifying debug info due to spill:" << "\t" << *MI
);
809 MachineBasicBlock
*MBB
= MI
->getParent();
810 MBB
->insert(MBB
->erase(MI
), NewDV
);
811 // Scan NewDV operands from the beginning.
816 MO
.setReg(0); // We can't allocate a physreg for a DebugValue, sorry!
825 // If this is a copy, we may be able to coalesce.
826 unsigned CopySrc
= 0, CopyDst
= 0, CopySrcSub
= 0, CopyDstSub
= 0;
828 CopyDst
= MI
->getOperand(0).getReg();
829 CopySrc
= MI
->getOperand(1).getReg();
830 CopyDstSub
= MI
->getOperand(0).getSubReg();
831 CopySrcSub
= MI
->getOperand(1).getSubReg();
834 // Track registers used by instruction.
838 // Mark physreg uses and early clobbers as used.
839 // Find the end of the virtreg operands
840 unsigned VirtOpEnd
= 0;
841 bool hasTiedOps
= false;
842 bool hasEarlyClobbers
= false;
843 bool hasPartialRedefs
= false;
844 bool hasPhysDefs
= false;
845 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
846 MachineOperand
&MO
= MI
->getOperand(i
);
847 if (!MO
.isReg()) continue;
848 unsigned Reg
= MO
.getReg();
850 if (TargetRegisterInfo::isVirtualRegister(Reg
)) {
853 hasTiedOps
= hasTiedOps
||
854 TID
.getOperandConstraint(i
, TOI::TIED_TO
) != -1;
856 if (MO
.isEarlyClobber())
857 hasEarlyClobbers
= true;
858 if (MO
.getSubReg() && MI
->readsVirtualRegister(Reg
))
859 hasPartialRedefs
= true;
863 if (!Allocatable
.test(Reg
)) continue;
866 } else if (MO
.isEarlyClobber()) {
867 definePhysReg(MI
, Reg
, (MO
.isImplicit() || MO
.isDead()) ?
868 regFree
: regReserved
);
869 hasEarlyClobbers
= true;
874 // The instruction may have virtual register operands that must be allocated
875 // the same register at use-time and def-time: early clobbers and tied
876 // operands. If there are also physical defs, these registers must avoid
877 // both physical defs and uses, making them more constrained than normal
879 // Similarly, if there are multiple defs and tied operands, we must make sure
880 // the same register is allocated to uses and defs.
881 // We didn't detect inline asm tied operands above, so just make this extra
882 // pass for all inline asm.
883 if (MI
->isInlineAsm() || hasEarlyClobbers
|| hasPartialRedefs
||
884 (hasTiedOps
&& (hasPhysDefs
|| TID
.getNumDefs() > 1))) {
885 handleThroughOperands(MI
, VirtDead
);
886 // Don't attempt coalescing when we have funny stuff going on.
888 // Pretend we have early clobbers so the use operands get marked below.
889 // This is not necessary for the common case of a single tied use.
890 hasEarlyClobbers
= true;
894 // Allocate virtreg uses.
895 for (unsigned i
= 0; i
!= VirtOpEnd
; ++i
) {
896 MachineOperand
&MO
= MI
->getOperand(i
);
897 if (!MO
.isReg()) continue;
898 unsigned Reg
= MO
.getReg();
899 if (!Reg
|| TargetRegisterInfo::isPhysicalRegister(Reg
)) continue;
901 LiveRegMap::iterator LRI
= reloadVirtReg(MI
, i
, Reg
, CopyDst
);
902 unsigned PhysReg
= LRI
->second
.PhysReg
;
903 CopySrc
= (CopySrc
== Reg
|| CopySrc
== PhysReg
) ? PhysReg
: 0;
904 if (setPhysReg(MI
, i
, PhysReg
))
909 MRI
->addPhysRegsUsed(UsedInInstr
);
911 // Track registers defined by instruction - early clobbers and tied uses at
914 if (hasEarlyClobbers
) {
915 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
916 MachineOperand
&MO
= MI
->getOperand(i
);
917 if (!MO
.isReg()) continue;
918 unsigned Reg
= MO
.getReg();
919 if (!Reg
|| !TargetRegisterInfo::isPhysicalRegister(Reg
)) continue;
920 // Look for physreg defs and tied uses.
921 if (!MO
.isDef() && !MI
->isRegTiedToDefOperand(i
)) continue;
922 UsedInInstr
.set(Reg
);
923 for (const unsigned *AS
= TRI
->getAliasSet(Reg
); *AS
; ++AS
)
924 UsedInInstr
.set(*AS
);
928 unsigned DefOpEnd
= MI
->getNumOperands();
930 // Spill all virtregs before a call. This serves two purposes: 1. If an
931 // exception is thrown, the landing pad is going to expect to find registers
932 // in their spill slots, and 2. we don't have to wade through all the
933 // <imp-def> operands on the call instruction.
934 DefOpEnd
= VirtOpEnd
;
935 DEBUG(dbgs() << " Spilling remaining registers before call.\n");
938 // The imp-defs are skipped below, but we still need to mark those
939 // registers as used by the function.
940 SkippedInstrs
.insert(&TID
);
944 // Allocate defs and collect dead defs.
945 for (unsigned i
= 0; i
!= DefOpEnd
; ++i
) {
946 MachineOperand
&MO
= MI
->getOperand(i
);
947 if (!MO
.isReg() || !MO
.isDef() || !MO
.getReg() || MO
.isEarlyClobber())
949 unsigned Reg
= MO
.getReg();
951 if (TargetRegisterInfo::isPhysicalRegister(Reg
)) {
952 if (!Allocatable
.test(Reg
)) continue;
953 definePhysReg(MI
, Reg
, (MO
.isImplicit() || MO
.isDead()) ?
954 regFree
: regReserved
);
957 LiveRegMap::iterator LRI
= defineVirtReg(MI
, i
, Reg
, CopySrc
);
958 unsigned PhysReg
= LRI
->second
.PhysReg
;
959 if (setPhysReg(MI
, i
, PhysReg
)) {
960 VirtDead
.push_back(Reg
);
961 CopyDst
= 0; // cancel coalescing;
963 CopyDst
= (CopyDst
== Reg
|| CopyDst
== PhysReg
) ? PhysReg
: 0;
966 // Kill dead defs after the scan to ensure that multiple defs of the same
967 // register are allocated identically. We didn't need to do this for uses
968 // because we are crerating our own kill flags, and they are always at the
970 for (unsigned i
= 0, e
= VirtDead
.size(); i
!= e
; ++i
)
971 killVirtReg(VirtDead
[i
]);
974 MRI
->addPhysRegsUsed(UsedInInstr
);
976 if (CopyDst
&& CopyDst
== CopySrc
&& CopyDstSub
== CopySrcSub
) {
977 DEBUG(dbgs() << "-- coalescing: " << *MI
);
978 Coalesced
.push_back(MI
);
980 DEBUG(dbgs() << "<< " << *MI
);
984 // Spill all physical registers holding virtual registers now.
985 DEBUG(dbgs() << "Spilling live registers at end of block.\n");
986 spillAll(MBB
->getFirstTerminator());
988 // Erase all the coalesced copies. We are delaying it until now because
989 // LiveVirtRegs might refer to the instrs.
990 for (unsigned i
= 0, e
= Coalesced
.size(); i
!= e
; ++i
)
991 MBB
->erase(Coalesced
[i
]);
992 NumCopies
+= Coalesced
.size();
997 /// runOnMachineFunction - Register allocate the whole function
999 bool RAFast::runOnMachineFunction(MachineFunction
&Fn
) {
1000 DEBUG(dbgs() << "********** FAST REGISTER ALLOCATION **********\n"
1001 << "********** Function: "
1002 << ((Value
*)Fn
.getFunction())->getName() << '\n');
1004 MRI
= &MF
->getRegInfo();
1005 TM
= &Fn
.getTarget();
1006 TRI
= TM
->getRegisterInfo();
1007 TII
= TM
->getInstrInfo();
1009 UsedInInstr
.resize(TRI
->getNumRegs());
1010 Allocatable
= TRI
->getAllocatableSet(*MF
);
1012 // initialize the virtual->physical register map to have a 'null'
1013 // mapping for all virtual registers
1014 unsigned LastVirtReg
= MRI
->getLastVirtReg();
1015 StackSlotForVirtReg
.grow(LastVirtReg
);
1017 // Loop over all of the basic blocks, eliminating virtual register references
1018 for (MachineFunction::iterator MBBi
= Fn
.begin(), MBBe
= Fn
.end();
1019 MBBi
!= MBBe
; ++MBBi
) {
1021 AllocateBasicBlock();
1024 // Make sure the set of used physregs is closed under subreg operations.
1025 MRI
->closePhysRegsUsed(*TRI
);
1027 // Add the clobber lists for all the instructions we skipped earlier.
1028 for (SmallPtrSet
<const TargetInstrDesc
*, 4>::const_iterator
1029 I
= SkippedInstrs
.begin(), E
= SkippedInstrs
.end(); I
!= E
; ++I
)
1030 if (const unsigned *Defs
= (*I
)->getImplicitDefs())
1032 MRI
->setPhysRegUsed(*Defs
++);
1034 SkippedInstrs
.clear();
1035 StackSlotForVirtReg
.clear();
1036 LiveDbgValueMap
.clear();
1040 FunctionPass
*llvm::createFastRegisterAllocator() {
1041 return new RAFast();