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/MachineFrameInfo.h"
20 #include "llvm/CodeGen/MachineRegisterInfo.h"
21 #include "llvm/CodeGen/Passes.h"
22 #include "llvm/CodeGen/RegAllocRegistry.h"
23 #include "llvm/Target/TargetInstrInfo.h"
24 #include "llvm/Target/TargetMachine.h"
25 #include "llvm/Support/CommandLine.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/ErrorHandling.h"
28 #include "llvm/Support/raw_ostream.h"
29 #include "llvm/ADT/DenseMap.h"
30 #include "llvm/ADT/IndexedMap.h"
31 #include "llvm/ADT/SmallSet.h"
32 #include "llvm/ADT/SmallVector.h"
33 #include "llvm/ADT/Statistic.h"
34 #include "llvm/ADT/STLExtras.h"
38 STATISTIC(NumStores
, "Number of stores added");
39 STATISTIC(NumLoads
, "Number of loads added");
40 STATISTIC(NumCopies
, "Number of copies coalesced");
42 static RegisterRegAlloc
43 fastRegAlloc("fast", "fast register allocator", createFastRegisterAllocator
);
46 class RAFast
: public MachineFunctionPass
{
49 RAFast() : MachineFunctionPass(&ID
), StackSlotForVirtReg(-1),
50 isBulkSpilling(false) {}
52 const TargetMachine
*TM
;
54 MachineRegisterInfo
*MRI
;
55 const TargetRegisterInfo
*TRI
;
56 const TargetInstrInfo
*TII
;
58 // Basic block currently being allocated.
59 MachineBasicBlock
*MBB
;
61 // StackSlotForVirtReg - Maps virtual regs to the frame index where these
62 // values are spilled.
63 IndexedMap
<int, VirtReg2IndexFunctor
> StackSlotForVirtReg
;
65 // Everything we know about a live virtual register.
67 MachineInstr
*LastUse
; // Last instr to use reg.
68 unsigned PhysReg
; // Currently held here.
69 unsigned short LastOpNum
; // OpNum on LastUse.
70 bool Dirty
; // Register needs spill.
72 LiveReg(unsigned p
=0) : LastUse(0), PhysReg(p
), LastOpNum(0),
76 typedef DenseMap
<unsigned, LiveReg
> LiveRegMap
;
77 typedef LiveRegMap::value_type LiveRegEntry
;
79 // LiveVirtRegs - This map contains entries for each virtual register
80 // that is currently available in a physical register.
81 LiveRegMap LiveVirtRegs
;
83 // RegState - Track the state of a physical register.
85 // A disabled register is not available for allocation, but an alias may
86 // be in use. A register can only be moved out of the disabled state if
87 // all aliases are disabled.
90 // A free register is not currently in use and can be allocated
91 // immediately without checking aliases.
94 // A reserved register has been assigned expolicitly (e.g., setting up a
95 // call parameter), and it remains reserved until it is used.
98 // A register state may also be a virtual register number, indication that
99 // the physical register is currently allocated to a virtual register. In
100 // that case, LiveVirtRegs contains the inverse mapping.
103 // PhysRegState - One of the RegState enums, or a virtreg.
104 std::vector
<unsigned> PhysRegState
;
106 // UsedInInstr - BitVector of physregs that are used in the current
107 // instruction, and so cannot be allocated.
108 BitVector UsedInInstr
;
110 // Allocatable - vector of allocatable physical registers.
111 BitVector Allocatable
;
113 // isBulkSpilling - This flag is set when LiveRegMap will be cleared
114 // completely after spilling all live registers. LiveRegMap entries should
121 spillImpossible
= ~0u
124 virtual const char *getPassName() const {
125 return "Fast Register Allocator";
128 virtual void getAnalysisUsage(AnalysisUsage
&AU
) const {
129 AU
.setPreservesCFG();
130 AU
.addRequiredID(PHIEliminationID
);
131 AU
.addRequiredID(TwoAddressInstructionPassID
);
132 MachineFunctionPass::getAnalysisUsage(AU
);
136 bool runOnMachineFunction(MachineFunction
&Fn
);
137 void AllocateBasicBlock();
138 int getStackSpaceFor(unsigned VirtReg
, const TargetRegisterClass
*RC
);
139 bool isLastUseOfLocalReg(MachineOperand
&);
141 void addKillFlag(const LiveReg
&);
142 void killVirtReg(LiveRegMap::iterator
);
143 void killVirtReg(unsigned VirtReg
);
144 void spillVirtReg(MachineBasicBlock::iterator MI
, LiveRegMap::iterator
);
145 void spillVirtReg(MachineBasicBlock::iterator MI
, unsigned VirtReg
);
147 void usePhysReg(MachineOperand
&);
148 void definePhysReg(MachineInstr
*MI
, unsigned PhysReg
, RegState NewState
);
149 unsigned calcSpillCost(unsigned PhysReg
) const;
150 void assignVirtToPhysReg(LiveRegEntry
&LRE
, unsigned PhysReg
);
151 void allocVirtReg(MachineInstr
*MI
, LiveRegEntry
&LRE
, unsigned Hint
);
152 LiveRegMap::iterator
defineVirtReg(MachineInstr
*MI
, unsigned OpNum
,
153 unsigned VirtReg
, unsigned Hint
);
154 LiveRegMap::iterator
reloadVirtReg(MachineInstr
*MI
, unsigned OpNum
,
155 unsigned VirtReg
, unsigned Hint
);
156 void spillAll(MachineInstr
*MI
);
157 bool setPhysReg(MachineOperand
&MO
, unsigned PhysReg
);
162 /// getStackSpaceFor - This allocates space for the specified virtual register
163 /// to be held on the stack.
164 int RAFast::getStackSpaceFor(unsigned VirtReg
, const TargetRegisterClass
*RC
) {
165 // Find the location Reg would belong...
166 int SS
= StackSlotForVirtReg
[VirtReg
];
168 return SS
; // Already has space allocated?
170 // Allocate a new stack object for this spill location...
171 int FrameIdx
= MF
->getFrameInfo()->CreateSpillStackObject(RC
->getSize(),
175 StackSlotForVirtReg
[VirtReg
] = FrameIdx
;
179 /// isLastUseOfLocalReg - Return true if MO is the only remaining reference to
180 /// its virtual register, and it is guaranteed to be a block-local register.
182 bool RAFast::isLastUseOfLocalReg(MachineOperand
&MO
) {
183 // Check for non-debug uses or defs following MO.
184 // This is the most likely way to fail - fast path it.
185 MachineOperand
*Next
= &MO
;
186 while ((Next
= Next
->getNextOperandForReg()))
187 if (!Next
->isDebug())
190 // If the register has ever been spilled or reloaded, we conservatively assume
191 // it is a global register used in multiple blocks.
192 if (StackSlotForVirtReg
[MO
.getReg()] != -1)
195 // Check that the use/def chain has exactly one operand - MO.
196 return &MRI
->reg_nodbg_begin(MO
.getReg()).getOperand() == &MO
;
199 /// addKillFlag - Set kill flags on last use of a virtual register.
200 void RAFast::addKillFlag(const LiveReg
&LR
) {
201 if (!LR
.LastUse
) return;
202 MachineOperand
&MO
= LR
.LastUse
->getOperand(LR
.LastOpNum
);
205 else if (!LR
.LastUse
->isRegTiedToDefOperand(LR
.LastOpNum
))
209 /// killVirtReg - Mark virtreg as no longer available.
210 void RAFast::killVirtReg(LiveRegMap::iterator LRI
) {
211 addKillFlag(LRI
->second
);
212 const LiveReg
&LR
= LRI
->second
;
213 assert(PhysRegState
[LR
.PhysReg
] == LRI
->first
&& "Broken RegState mapping");
214 PhysRegState
[LR
.PhysReg
] = regFree
;
215 // Erase from LiveVirtRegs unless we're spilling in bulk.
217 LiveVirtRegs
.erase(LRI
);
220 /// killVirtReg - Mark virtreg as no longer available.
221 void RAFast::killVirtReg(unsigned VirtReg
) {
222 assert(TargetRegisterInfo::isVirtualRegister(VirtReg
) &&
223 "killVirtReg needs a virtual register");
224 LiveRegMap::iterator LRI
= LiveVirtRegs
.find(VirtReg
);
225 if (LRI
!= LiveVirtRegs
.end())
229 /// spillVirtReg - This method spills the value specified by VirtReg into the
230 /// corresponding stack slot if needed. If isKill is set, the register is also
232 void RAFast::spillVirtReg(MachineBasicBlock::iterator MI
, unsigned VirtReg
) {
233 assert(TargetRegisterInfo::isVirtualRegister(VirtReg
) &&
234 "Spilling a physical register is illegal!");
235 LiveRegMap::iterator LRI
= LiveVirtRegs
.find(VirtReg
);
236 assert(LRI
!= LiveVirtRegs
.end() && "Spilling unmapped virtual register");
237 spillVirtReg(MI
, LRI
);
240 /// spillVirtReg - Do the actual work of spilling.
241 void RAFast::spillVirtReg(MachineBasicBlock::iterator MI
,
242 LiveRegMap::iterator LRI
) {
243 LiveReg
&LR
= LRI
->second
;
244 assert(PhysRegState
[LR
.PhysReg
] == LRI
->first
&& "Broken RegState mapping");
247 // If this physreg is used by the instruction, we want to kill it on the
248 // instruction, not on the spill.
249 bool SpillKill
= LR
.LastUse
!= MI
;
251 DEBUG(dbgs() << "Spilling %reg" << LRI
->first
252 << " in " << TRI
->getName(LR
.PhysReg
));
253 const TargetRegisterClass
*RC
= MRI
->getRegClass(LRI
->first
);
254 int FI
= getStackSpaceFor(LRI
->first
, RC
);
255 DEBUG(dbgs() << " to stack slot #" << FI
<< "\n");
256 TII
->storeRegToStackSlot(*MBB
, MI
, LR
.PhysReg
, SpillKill
, FI
, RC
, TRI
);
257 ++NumStores
; // Update statistics
260 LR
.LastUse
= 0; // Don't kill register again
265 /// spillAll - Spill all dirty virtregs without killing them.
266 void RAFast::spillAll(MachineInstr
*MI
) {
267 if (LiveVirtRegs
.empty()) return;
268 isBulkSpilling
= true;
269 // The LiveRegMap is keyed by an unsigned (the virtreg number), so the order
270 // of spilling here is deterministic, if arbitrary.
271 for (LiveRegMap::iterator i
= LiveVirtRegs
.begin(), e
= LiveVirtRegs
.end();
274 LiveVirtRegs
.clear();
275 isBulkSpilling
= false;
278 /// usePhysReg - Handle the direct use of a physical register.
279 /// Check that the register is not used by a virtreg.
280 /// Kill the physreg, marking it free.
281 /// This may add implicit kills to MO->getParent() and invalidate MO.
282 void RAFast::usePhysReg(MachineOperand
&MO
) {
283 unsigned PhysReg
= MO
.getReg();
284 assert(TargetRegisterInfo::isPhysicalRegister(PhysReg
) &&
285 "Bad usePhysReg operand");
287 switch (PhysRegState
[PhysReg
]) {
291 PhysRegState
[PhysReg
] = regFree
;
294 UsedInInstr
.set(PhysReg
);
298 // The physreg was allocated to a virtual register. That means to value we
299 // wanted has been clobbered.
300 llvm_unreachable("Instruction uses an allocated register");
303 // Maybe a superregister is reserved?
304 for (const unsigned *AS
= TRI
->getAliasSet(PhysReg
);
305 unsigned Alias
= *AS
; ++AS
) {
306 switch (PhysRegState
[Alias
]) {
310 assert(TRI
->isSuperRegister(PhysReg
, Alias
) &&
311 "Instruction is not using a subregister of a reserved register");
312 // Leave the superregister in the working set.
313 PhysRegState
[Alias
] = regFree
;
314 UsedInInstr
.set(Alias
);
315 MO
.getParent()->addRegisterKilled(Alias
, TRI
, true);
318 if (TRI
->isSuperRegister(PhysReg
, Alias
)) {
319 // Leave the superregister in the working set.
320 UsedInInstr
.set(Alias
);
321 MO
.getParent()->addRegisterKilled(Alias
, TRI
, true);
324 // Some other alias was in the working set - clear it.
325 PhysRegState
[Alias
] = regDisabled
;
328 llvm_unreachable("Instruction uses an alias of an allocated register");
332 // All aliases are disabled, bring register into working set.
333 PhysRegState
[PhysReg
] = regFree
;
334 UsedInInstr
.set(PhysReg
);
338 /// definePhysReg - Mark PhysReg as reserved or free after spilling any
339 /// virtregs. This is very similar to defineVirtReg except the physreg is
340 /// reserved instead of allocated.
341 void RAFast::definePhysReg(MachineInstr
*MI
, unsigned PhysReg
,
343 UsedInInstr
.set(PhysReg
);
344 switch (unsigned VirtReg
= PhysRegState
[PhysReg
]) {
348 spillVirtReg(MI
, VirtReg
);
352 PhysRegState
[PhysReg
] = NewState
;
356 // This is a disabled register, disable all aliases.
357 PhysRegState
[PhysReg
] = NewState
;
358 for (const unsigned *AS
= TRI
->getAliasSet(PhysReg
);
359 unsigned Alias
= *AS
; ++AS
) {
360 UsedInInstr
.set(Alias
);
361 switch (unsigned VirtReg
= PhysRegState
[Alias
]) {
365 spillVirtReg(MI
, VirtReg
);
369 PhysRegState
[Alias
] = regDisabled
;
370 if (TRI
->isSuperRegister(PhysReg
, Alias
))
378 // calcSpillCost - Return the cost of spilling clearing out PhysReg and
379 // aliases so it is free for allocation.
380 // Returns 0 when PhysReg is free or disabled with all aliases disabled - it
381 // can be allocated directly.
382 // Returns spillImpossible when PhysReg or an alias can't be spilled.
383 unsigned RAFast::calcSpillCost(unsigned PhysReg
) const {
384 if (UsedInInstr
.test(PhysReg
))
385 return spillImpossible
;
386 switch (unsigned VirtReg
= PhysRegState
[PhysReg
]) {
392 return spillImpossible
;
394 return LiveVirtRegs
.lookup(VirtReg
).Dirty
? spillDirty
: spillClean
;
397 // This is a disabled register, add up const of aliases.
399 for (const unsigned *AS
= TRI
->getAliasSet(PhysReg
);
400 unsigned Alias
= *AS
; ++AS
) {
401 if (UsedInInstr
.test(Alias
))
402 return spillImpossible
;
403 switch (unsigned VirtReg
= PhysRegState
[Alias
]) {
410 return spillImpossible
;
412 Cost
+= LiveVirtRegs
.lookup(VirtReg
).Dirty
? spillDirty
: spillClean
;
420 /// assignVirtToPhysReg - This method updates local state so that we know
421 /// that PhysReg is the proper container for VirtReg now. The physical
422 /// register must not be used for anything else when this is called.
424 void RAFast::assignVirtToPhysReg(LiveRegEntry
&LRE
, unsigned PhysReg
) {
425 DEBUG(dbgs() << "Assigning %reg" << LRE
.first
<< " to "
426 << TRI
->getName(PhysReg
) << "\n");
427 PhysRegState
[PhysReg
] = LRE
.first
;
428 assert(!LRE
.second
.PhysReg
&& "Already assigned a physreg");
429 LRE
.second
.PhysReg
= PhysReg
;
432 /// allocVirtReg - Allocate a physical register for VirtReg.
433 void RAFast::allocVirtReg(MachineInstr
*MI
, LiveRegEntry
&LRE
, unsigned Hint
) {
434 const unsigned VirtReg
= LRE
.first
;
436 assert(TargetRegisterInfo::isVirtualRegister(VirtReg
) &&
437 "Can only allocate virtual registers");
439 const TargetRegisterClass
*RC
= MRI
->getRegClass(VirtReg
);
441 // Ignore invalid hints.
442 if (Hint
&& (!TargetRegisterInfo::isPhysicalRegister(Hint
) ||
443 !RC
->contains(Hint
) || !Allocatable
.test(Hint
)))
446 // Take hint when possible.
448 switch(calcSpillCost(Hint
)) {
450 definePhysReg(MI
, Hint
, regFree
);
453 return assignVirtToPhysReg(LRE
, Hint
);
454 case spillImpossible
:
459 TargetRegisterClass::iterator AOB
= RC
->allocation_order_begin(*MF
);
460 TargetRegisterClass::iterator AOE
= RC
->allocation_order_end(*MF
);
462 // First try to find a completely free register.
463 for (TargetRegisterClass::iterator I
= AOB
; I
!= AOE
; ++I
) {
464 unsigned PhysReg
= *I
;
465 if (PhysRegState
[PhysReg
] == regFree
&& !UsedInInstr
.test(PhysReg
))
466 return assignVirtToPhysReg(LRE
, PhysReg
);
469 DEBUG(dbgs() << "Allocating %reg" << VirtReg
<< " from " << RC
->getName()
472 unsigned BestReg
= 0, BestCost
= spillImpossible
;
473 for (TargetRegisterClass::iterator I
= AOB
; I
!= AOE
; ++I
) {
474 unsigned Cost
= calcSpillCost(*I
);
475 // Cost is 0 when all aliases are already disabled.
477 return assignVirtToPhysReg(LRE
, *I
);
479 BestReg
= *I
, BestCost
= Cost
;
483 definePhysReg(MI
, BestReg
, regFree
);
484 return assignVirtToPhysReg(LRE
, BestReg
);
487 // Nothing we can do.
489 raw_string_ostream
Msg(msg
);
490 Msg
<< "Ran out of registers during register allocation!";
491 if (MI
->isInlineAsm()) {
492 Msg
<< "\nPlease check your inline asm statement for "
493 << "invalid constraints:\n";
496 report_fatal_error(Msg
.str());
499 /// defineVirtReg - Allocate a register for VirtReg and mark it as dirty.
500 RAFast::LiveRegMap::iterator
501 RAFast::defineVirtReg(MachineInstr
*MI
, unsigned OpNum
,
502 unsigned VirtReg
, unsigned Hint
) {
503 assert(TargetRegisterInfo::isVirtualRegister(VirtReg
) &&
504 "Not a virtual register");
505 LiveRegMap::iterator LRI
;
507 tie(LRI
, New
) = LiveVirtRegs
.insert(std::make_pair(VirtReg
, LiveReg()));
508 LiveReg
&LR
= LRI
->second
;
510 // If there is no hint, peek at the only use of this register.
511 if ((!Hint
|| !TargetRegisterInfo::isPhysicalRegister(Hint
)) &&
512 MRI
->hasOneNonDBGUse(VirtReg
)) {
513 unsigned SrcReg
, DstReg
, SrcSubReg
, DstSubReg
;
514 // It's a copy, use the destination register as a hint.
515 if (TII
->isMoveInstr(*MRI
->use_nodbg_begin(VirtReg
),
516 SrcReg
, DstReg
, SrcSubReg
, DstSubReg
))
519 allocVirtReg(MI
, *LRI
, Hint
);
521 addKillFlag(LR
); // Kill before redefine.
522 assert(LR
.PhysReg
&& "Register not assigned");
524 LR
.LastOpNum
= OpNum
;
526 UsedInInstr
.set(LR
.PhysReg
);
530 /// reloadVirtReg - Make sure VirtReg is available in a physreg and return it.
531 RAFast::LiveRegMap::iterator
532 RAFast::reloadVirtReg(MachineInstr
*MI
, unsigned OpNum
,
533 unsigned VirtReg
, unsigned Hint
) {
534 assert(TargetRegisterInfo::isVirtualRegister(VirtReg
) &&
535 "Not a virtual register");
536 LiveRegMap::iterator LRI
;
538 tie(LRI
, New
) = LiveVirtRegs
.insert(std::make_pair(VirtReg
, LiveReg()));
539 LiveReg
&LR
= LRI
->second
;
540 MachineOperand
&MO
= MI
->getOperand(OpNum
);
542 allocVirtReg(MI
, *LRI
, Hint
);
543 const TargetRegisterClass
*RC
= MRI
->getRegClass(VirtReg
);
544 int FrameIndex
= getStackSpaceFor(VirtReg
, RC
);
545 DEBUG(dbgs() << "Reloading %reg" << VirtReg
<< " into "
546 << TRI
->getName(LR
.PhysReg
) << "\n");
547 TII
->loadRegFromStackSlot(*MBB
, MI
, LR
.PhysReg
, FrameIndex
, RC
, TRI
);
549 } else if (LR
.Dirty
) {
550 if (isLastUseOfLocalReg(MO
)) {
551 DEBUG(dbgs() << "Killing last use: " << MO
<< "\n");
553 } else if (MO
.isKill()) {
554 DEBUG(dbgs() << "Clearing dubious kill: " << MO
<< "\n");
557 } else if (MO
.isKill()) {
558 // We must remove kill flags from uses of reloaded registers because the
559 // register would be killed immediately, and there might be a second use:
560 // %foo = OR %x<kill>, %x
561 // This would cause a second reload of %x into a different register.
562 DEBUG(dbgs() << "Clearing clean kill: " << MO
<< "\n");
565 assert(LR
.PhysReg
&& "Register not assigned");
567 LR
.LastOpNum
= OpNum
;
568 UsedInInstr
.set(LR
.PhysReg
);
572 // setPhysReg - Change MO the refer the PhysReg, considering subregs.
573 // This may invalidate MO if it is necessary to add implicit kills for a
575 // Return tru if MO kills its register.
576 bool RAFast::setPhysReg(MachineOperand
&MO
, unsigned PhysReg
) {
577 if (!MO
.getSubReg()) {
579 return MO
.isKill() || MO
.isDead();
582 // Handle subregister index.
583 MO
.setReg(PhysReg
? TRI
->getSubReg(PhysReg
, MO
.getSubReg()) : 0);
587 MO
.getParent()->addRegisterKilled(PhysReg
, TRI
, true);
592 // A subregister def implicitly defines the whole physreg.
594 MO
.getParent()->addRegisterDead(PhysReg
, TRI
, true);
597 MO
.getParent()->addRegisterDefined(PhysReg
, TRI
);
601 void RAFast::AllocateBasicBlock() {
602 DEBUG(dbgs() << "\nAllocating " << *MBB
);
604 PhysRegState
.assign(TRI
->getNumRegs(), regDisabled
);
605 assert(LiveVirtRegs
.empty() && "Mapping not cleared form last block?");
607 MachineBasicBlock::iterator MII
= MBB
->begin();
609 // Add live-in registers as live.
610 for (MachineBasicBlock::livein_iterator I
= MBB
->livein_begin(),
611 E
= MBB
->livein_end(); I
!= E
; ++I
)
612 definePhysReg(MII
, *I
, regReserved
);
614 SmallVector
<unsigned, 8> PhysECs
;
615 SmallVector
<MachineInstr
*, 32> Coalesced
;
617 // Otherwise, sequentially allocate each instruction in the MBB.
618 while (MII
!= MBB
->end()) {
619 MachineInstr
*MI
= MII
++;
620 const TargetInstrDesc
&TID
= MI
->getDesc();
622 dbgs() << "\n>> " << *MI
<< "Regs:";
623 for (unsigned Reg
= 1, E
= TRI
->getNumRegs(); Reg
!= E
; ++Reg
) {
624 if (PhysRegState
[Reg
] == regDisabled
) continue;
625 dbgs() << " " << TRI
->getName(Reg
);
626 switch(PhysRegState
[Reg
]) {
633 dbgs() << "=%reg" << PhysRegState
[Reg
];
634 if (LiveVirtRegs
[PhysRegState
[Reg
]].Dirty
)
636 assert(LiveVirtRegs
[PhysRegState
[Reg
]].PhysReg
== Reg
&&
642 // Check that LiveVirtRegs is the inverse.
643 for (LiveRegMap::iterator i
= LiveVirtRegs
.begin(),
644 e
= LiveVirtRegs
.end(); i
!= e
; ++i
) {
645 assert(TargetRegisterInfo::isVirtualRegister(i
->first
) &&
647 assert(TargetRegisterInfo::isPhysicalRegister(i
->second
.PhysReg
) &&
649 assert(PhysRegState
[i
->second
.PhysReg
] == i
->first
&&
654 // Debug values are not allowed to change codegen in any way.
655 if (MI
->isDebugValue()) {
656 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
657 MachineOperand
&MO
= MI
->getOperand(i
);
658 if (!MO
.isReg()) continue;
659 unsigned Reg
= MO
.getReg();
660 if (!Reg
|| TargetRegisterInfo::isPhysicalRegister(Reg
)) continue;
661 LiveRegMap::iterator LRI
= LiveVirtRegs
.find(Reg
);
662 if (LRI
!= LiveVirtRegs
.end())
663 setPhysReg(MO
, LRI
->second
.PhysReg
);
665 MO
.setReg(0); // We can't allocate a physreg for a DebugValue, sorry!
671 // If this is a copy, we may be able to coalesce.
672 unsigned CopySrc
, CopyDst
, CopySrcSub
, CopyDstSub
;
673 if (!TII
->isMoveInstr(*MI
, CopySrc
, CopyDst
, CopySrcSub
, CopyDstSub
))
674 CopySrc
= CopyDst
= 0;
676 // Track registers used by instruction.
681 // Mark physreg uses and early clobbers as used.
682 // Find the end of the virtreg operands
683 unsigned VirtOpEnd
= 0;
684 for (unsigned i
= 0, e
= MI
->getNumOperands(); i
!= e
; ++i
) {
685 MachineOperand
&MO
= MI
->getOperand(i
);
686 if (!MO
.isReg()) continue;
687 unsigned Reg
= MO
.getReg();
689 if (TargetRegisterInfo::isVirtualRegister(Reg
)) {
693 if (!Allocatable
.test(Reg
)) continue;
696 } else if (MO
.isEarlyClobber()) {
697 definePhysReg(MI
, Reg
, MO
.isDead() ? regFree
: regReserved
);
698 PhysECs
.push_back(Reg
);
703 // Allocate virtreg uses and early clobbers.
705 for (unsigned i
= 0; i
!= VirtOpEnd
; ++i
) {
706 MachineOperand
&MO
= MI
->getOperand(i
);
707 if (!MO
.isReg()) continue;
708 unsigned Reg
= MO
.getReg();
709 if (!Reg
|| TargetRegisterInfo::isPhysicalRegister(Reg
)) continue;
711 LiveRegMap::iterator LRI
= reloadVirtReg(MI
, i
, Reg
, CopyDst
);
712 unsigned PhysReg
= LRI
->second
.PhysReg
;
713 CopySrc
= (CopySrc
== Reg
|| CopySrc
== PhysReg
) ? PhysReg
: 0;
714 if (setPhysReg(MO
, PhysReg
))
716 } else if (MO
.isEarlyClobber()) {
717 LiveRegMap::iterator LRI
= defineVirtReg(MI
, i
, Reg
, 0);
718 unsigned PhysReg
= LRI
->second
.PhysReg
;
719 setPhysReg(MO
, PhysReg
);
720 PhysECs
.push_back(PhysReg
);
724 MRI
->addPhysRegsUsed(UsedInInstr
);
726 // Track registers defined by instruction - early clobbers at this point.
728 for (unsigned i
= 0, e
= PhysECs
.size(); i
!= e
; ++i
) {
729 unsigned PhysReg
= PhysECs
[i
];
730 UsedInInstr
.set(PhysReg
);
731 for (const unsigned *AS
= TRI
->getAliasSet(PhysReg
);
732 unsigned Alias
= *AS
; ++AS
)
733 UsedInInstr
.set(Alias
);
736 unsigned DefOpEnd
= MI
->getNumOperands();
738 // Spill all virtregs before a call. This serves two purposes: 1. If an
739 // exception is thrown, the landing pad is going to expect to find registers
740 // in their spill slots, and 2. we don't have to wade through all the
741 // <imp-def> operands on the call instruction.
742 DefOpEnd
= VirtOpEnd
;
743 DEBUG(dbgs() << " Spilling remaining registers before call.\n");
748 // Allocate defs and collect dead defs.
749 for (unsigned i
= 0; i
!= DefOpEnd
; ++i
) {
750 MachineOperand
&MO
= MI
->getOperand(i
);
751 if (!MO
.isReg() || !MO
.isDef() || !MO
.getReg()) continue;
752 unsigned Reg
= MO
.getReg();
754 if (TargetRegisterInfo::isPhysicalRegister(Reg
)) {
755 if (!Allocatable
.test(Reg
)) continue;
756 definePhysReg(MI
, Reg
, (MO
.isImplicit() || MO
.isDead()) ?
757 regFree
: regReserved
);
760 LiveRegMap::iterator LRI
= defineVirtReg(MI
, i
, Reg
, CopySrc
);
761 unsigned PhysReg
= LRI
->second
.PhysReg
;
762 if (setPhysReg(MO
, PhysReg
)) {
764 CopyDst
= 0; // cancel coalescing;
766 CopyDst
= (CopyDst
== Reg
|| CopyDst
== PhysReg
) ? PhysReg
: 0;
769 MRI
->addPhysRegsUsed(UsedInInstr
);
771 if (CopyDst
&& CopyDst
== CopySrc
&& CopyDstSub
== CopySrcSub
) {
772 DEBUG(dbgs() << "-- coalescing: " << *MI
);
773 Coalesced
.push_back(MI
);
775 DEBUG(dbgs() << "<< " << *MI
);
779 // Spill all physical registers holding virtual registers now.
780 DEBUG(dbgs() << "Spilling live registers at end of block.\n");
781 spillAll(MBB
->getFirstTerminator());
783 // Erase all the coalesced copies. We are delaying it until now because
784 // LiveVirtRegs might refer to the instrs.
785 for (unsigned i
= 0, e
= Coalesced
.size(); i
!= e
; ++i
)
786 MBB
->erase(Coalesced
[i
]);
787 NumCopies
+= Coalesced
.size();
792 /// runOnMachineFunction - Register allocate the whole function
794 bool RAFast::runOnMachineFunction(MachineFunction
&Fn
) {
795 DEBUG(dbgs() << "********** FAST REGISTER ALLOCATION **********\n"
796 << "********** Function: "
797 << ((Value
*)Fn
.getFunction())->getName() << '\n');
799 MRI
= &MF
->getRegInfo();
800 TM
= &Fn
.getTarget();
801 TRI
= TM
->getRegisterInfo();
802 TII
= TM
->getInstrInfo();
804 UsedInInstr
.resize(TRI
->getNumRegs());
805 Allocatable
= TRI
->getAllocatableSet(*MF
);
807 // initialize the virtual->physical register map to have a 'null'
808 // mapping for all virtual registers
809 unsigned LastVirtReg
= MRI
->getLastVirtReg();
810 StackSlotForVirtReg
.grow(LastVirtReg
);
812 // Loop over all of the basic blocks, eliminating virtual register references
813 for (MachineFunction::iterator MBBi
= Fn
.begin(), MBBe
= Fn
.end();
814 MBBi
!= MBBe
; ++MBBi
) {
816 AllocateBasicBlock();
819 // Make sure the set of used physregs is closed under subreg operations.
820 MRI
->closePhysRegsUsed(*TRI
);
822 StackSlotForVirtReg
.clear();
826 FunctionPass
*llvm::createFastRegisterAllocator() {