RegAllocFast.cpp revision 76b4d5a0210f161c08543f00f355955c94d3f2ec
100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen//===-- RegAllocFast.cpp - A fast register allocator for debug code -------===// 200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen// 300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen// The LLVM Compiler Infrastructure 400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen// 500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen// This file is distributed under the University of Illinois Open Source 600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen// License. See LICENSE.TXT for details. 700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen// 800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen//===----------------------------------------------------------------------===// 900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen// 1000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen// This register allocator allocates registers to a basic block at a time, 1100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen// attempting to keep values in registers and reusing registers as appropriate. 1200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen// 1300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 1500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#define DEBUG_TYPE "regalloc" 1600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/BasicBlock.h" 1700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/CodeGen/MachineFunctionPass.h" 1800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/CodeGen/MachineInstr.h" 1900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/CodeGen/MachineFrameInfo.h" 2000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 2100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/CodeGen/Passes.h" 2200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/CodeGen/RegAllocRegistry.h" 2300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/Target/TargetInstrInfo.h" 2400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/Target/TargetMachine.h" 2500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/Support/CommandLine.h" 2600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/Support/Debug.h" 2700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/Support/ErrorHandling.h" 2800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/Support/raw_ostream.h" 2900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/ADT/DenseMap.h" 3000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/ADT/IndexedMap.h" 3100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/ADT/SmallSet.h" 3200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/ADT/SmallVector.h" 3300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/ADT/Statistic.h" 3400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include "llvm/ADT/STLExtras.h" 3500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen#include <algorithm> 3600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenusing namespace llvm; 3700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 3800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund OlesenSTATISTIC(NumStores, "Number of stores added"); 3900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund OlesenSTATISTIC(NumLoads , "Number of loads added"); 4000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 4100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenstatic RegisterRegAlloc 4200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen fastRegAlloc("fast", "fast register allocator", createFastRegisterAllocator); 4300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 4400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesennamespace { 4500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen class RAFast : public MachineFunctionPass { 4600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen public: 4700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen static char ID; 4800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen RAFast() : MachineFunctionPass(&ID), StackSlotForVirtReg(-1) {} 4900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen private: 5000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen const TargetMachine *TM; 5100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineFunction *MF; 5200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen const TargetRegisterInfo *TRI; 5300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen const TargetInstrInfo *TII; 5400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 5500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // StackSlotForVirtReg - Maps virtual regs to the frame index where these 5600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // values are spilled. 5700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen IndexedMap<int, VirtReg2IndexFunctor> StackSlotForVirtReg; 5800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 5976b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen // Everything we know about a live virtual register. 6076b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen struct LiveReg { 6176b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen MachineInstr *LastUse; // Last instr to use reg. 6276b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen unsigned PhysReg; // Currently held here. 6376b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen unsigned LastOpNum; // OpNum on LastUse. 6476b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 6576b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen LiveReg(unsigned p=0) : LastUse(0), PhysReg(p), LastOpNum(0) { 6676b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen assert(p && "Don't create LiveRegs without a PhysReg"); 6776b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen } 6876b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen }; 6976b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 7076b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen typedef DenseMap<unsigned, LiveReg> LiveRegMap; 7176b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 7276b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen // LiveVirtRegs - This map contains entries for each virtual register 7300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // that is currently available in a physical register. 7476b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen LiveRegMap LiveVirtRegs; 7500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 76bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // RegState - Track the state of a physical register. 77bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen enum RegState { 78bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // A disabled register is not available for allocation, but an alias may 79bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // be in use. A register can only be moved out of the disabled state if 80bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // all aliases are disabled. 81bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen regDisabled, 82bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 83bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // A free register is not currently in use and can be allocated 84bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // immediately without checking aliases. 85bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen regFree, 86bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 87bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // A reserved register has been assigned expolicitly (e.g., setting up a 88bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // call parameter), and it remains reserved until it is used. 89bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen regReserved 9000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 91bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // A register state may also be a virtual register number, indication that 92bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // the physical register is currently allocated to a virtual register. In 9376b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen // that case, LiveVirtRegs contains the inverse mapping. 94bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen }; 95bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 96bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // PhysRegState - One of the RegState enums, or a virtreg. 97bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen std::vector<unsigned> PhysRegState; 9800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 9900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // UsedInInstr - BitVector of physregs that are used in the current 10000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // instruction, and so cannot be allocated. 10100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen BitVector UsedInInstr; 10200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 103bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // PhysRegDirty - A bit is set for each physreg that holds a dirty virtual 104bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // register. Bits for physregs that are not mapped to a virtual register are 105bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // invalid. 106bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen BitVector PhysRegDirty; 10700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 108bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // ReservedRegs - vector of reserved physical registers. 109bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen BitVector ReservedRegs; 11000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 11100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen public: 11200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen virtual const char *getPassName() const { 11300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return "Fast Register Allocator"; 11400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 11500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 11600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen virtual void getAnalysisUsage(AnalysisUsage &AU) const { 11700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen AU.setPreservesCFG(); 11800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen AU.addRequiredID(PHIEliminationID); 11900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen AU.addRequiredID(TwoAddressInstructionPassID); 12000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineFunctionPass::getAnalysisUsage(AU); 12100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 12200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 12300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen private: 12400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen bool runOnMachineFunction(MachineFunction &Fn); 12500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen void AllocateBasicBlock(MachineBasicBlock &MBB); 12600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC); 127bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen void killVirtReg(unsigned VirtReg); 12876b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen void killVirtReg(LiveRegMap::iterator i); 12900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, 130bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned VirtReg, bool isKill); 131bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen void killPhysReg(unsigned PhysReg); 13200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen void spillPhysReg(MachineBasicBlock &MBB, MachineInstr *I, 133bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned PhysReg, bool isKill); 13476b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen LiveRegMap::iterator assignVirtToPhysReg(unsigned VirtReg, 13576b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen unsigned PhysReg); 13676b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen LiveRegMap::iterator allocVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, 13776b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen unsigned VirtReg); 138bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned defineVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, 13976b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen unsigned OpNum, unsigned VirtReg); 140bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, 14176b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen unsigned OpNum, unsigned VirtReg); 142bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen void reservePhysReg(MachineBasicBlock &MBB, MachineInstr *MI, 143bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned PhysReg); 144bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen void spillAll(MachineBasicBlock &MBB, MachineInstr *MI); 145bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen void setPhysReg(MachineOperand &MO, unsigned PhysReg); 14600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen }; 14700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen char RAFast::ID = 0; 14800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 14900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 15000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// getStackSpaceFor - This allocates space for the specified virtual register 15100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// to be held on the stack. 15200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenint RAFast::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) { 15300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Find the location Reg would belong... 15400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen int SS = StackSlotForVirtReg[VirtReg]; 15500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen if (SS != -1) 15600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return SS; // Already has space allocated? 15700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 15800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Allocate a new stack object for this spill location... 15900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen int FrameIdx = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(), 16000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen RC->getAlignment()); 16100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 16200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Assign the slot. 16300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen StackSlotForVirtReg[VirtReg] = FrameIdx; 16400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return FrameIdx; 16500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 16600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 167bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// killVirtReg - Mark virtreg as no longer available. 16876b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesenvoid RAFast::killVirtReg(LiveRegMap::iterator i) { 16976b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen assert(i != LiveVirtRegs.end() && "Killing unmapped virtual register"); 17076b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen unsigned VirtReg = i->first; 17176b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen const LiveReg &LR = i->second; 17276b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen assert(PhysRegState[LR.PhysReg] == VirtReg && "Broken RegState mapping"); 17376b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen PhysRegState[LR.PhysReg] = regFree; 17476b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen if (LR.LastUse) { 17576b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen MachineOperand &MO = LR.LastUse->getOperand(LR.LastOpNum); 17676b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen if (MO.isUse()) MO.setIsKill(); 17776b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen else MO.setIsDead(); 17876b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen DEBUG(dbgs() << " - last seen here: " << *LR.LastUse); 17976b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen } 18076b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen LiveVirtRegs.erase(i); 18176b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen} 18276b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 18376b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen/// killVirtReg - Mark virtreg as no longer available. 184bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesenvoid RAFast::killVirtReg(unsigned VirtReg) { 185bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 186bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "killVirtReg needs a virtual register"); 187bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen DEBUG(dbgs() << " Killing %reg" << VirtReg << "\n"); 18876b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen LiveRegMap::iterator i = LiveVirtRegs.find(VirtReg); 18976b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen if (i != LiveVirtRegs.end()) 19076b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen killVirtReg(i); 19100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 19200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 193bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// spillVirtReg - This method spills the value specified by VirtReg into the 194bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// corresponding stack slot if needed. If isKill is set, the register is also 195bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// killed. 19600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenvoid RAFast::spillVirtReg(MachineBasicBlock &MBB, 19776b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen MachineBasicBlock::iterator MI, 198bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned VirtReg, bool isKill) { 199bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 200bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Spilling a physical register is illegal!"); 20176b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen LiveRegMap::iterator i = LiveVirtRegs.find(VirtReg); 20276b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen assert(i != LiveVirtRegs.end() && "Spilling unmapped virtual register"); 20376b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen const LiveReg &LR = i->second; 20476b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen assert(PhysRegState[LR.PhysReg] == VirtReg && "Broken RegState mapping"); 20576b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 20676b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen // If this physreg is used by the instruction, we want to kill it on the 20776b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen // instruction, not on the spill. 20876b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen bool spillKill = isKill && LR.LastUse != MI; 20976b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 21076b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen if (PhysRegDirty.test(LR.PhysReg)) { 21176b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen PhysRegDirty.reset(LR.PhysReg); 21276b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen DEBUG(dbgs() << " Spilling register " << TRI->getName(LR.PhysReg) 213bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen << " containing %reg" << VirtReg); 21400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); 21500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen int FrameIndex = getStackSpaceFor(VirtReg, RC); 216bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen DEBUG(dbgs() << " to stack slot #" << FrameIndex << "\n"); 21776b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen TII->storeRegToStackSlot(MBB, MI, LR.PhysReg, spillKill, 21876b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen FrameIndex, RC, TRI); 21900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen ++NumStores; // Update statistics 22000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 22176b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen if (spillKill) 22276b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen i->second.LastUse = 0; // Don't kill register again 22376b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen else if (!isKill) { 22476b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen MachineInstr *Spill = llvm::prior(MI); 22576b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen i->second.LastUse = Spill; 22676b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen i->second.LastOpNum = Spill->findRegisterUseOperandIdx(LR.PhysReg); 22776b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen } 228bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 22976b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen 23076b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen if (isKill) 23176b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen killVirtReg(i); 23200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 23300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 234bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// spillAll - Spill all dirty virtregs without killing them. 235bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesenvoid RAFast::spillAll(MachineBasicBlock &MBB, MachineInstr *MI) { 236bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen SmallVector<unsigned, 16> Dirty; 23776b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen for (LiveRegMap::iterator i = LiveVirtRegs.begin(), 23876b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen e = LiveVirtRegs.end(); i != e; ++i) 23976b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen if (PhysRegDirty.test(i->second.PhysReg)) 240bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen Dirty.push_back(i->first); 241bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned i = 0, e = Dirty.size(); i != e; ++i) 242bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen spillVirtReg(MBB, MI, Dirty[i], false); 243bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 24400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 245bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// killPhysReg - Kill any virtual register aliased by PhysReg. 246bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesenvoid RAFast::killPhysReg(unsigned PhysReg) { 247bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Fast path for the normal case. 248bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[PhysReg]) { 249bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 250bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 251bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 252bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 253bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 254bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[PhysReg] = regFree; 255bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 256bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 257bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen killVirtReg(VirtReg); 25800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return; 25900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 26000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 261bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // This is a disabled register, we have to check aliases. 262bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(PhysReg); 263bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) { 264bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[Alias]) { 265bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 266bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 267bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 268bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 269bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[Alias] = regFree; 270bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 271bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 272bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen killVirtReg(VirtReg); 273bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 274bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 27500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 27600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 27700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 278bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// spillPhysReg - Spill any dirty virtual registers that aliases PhysReg. If 279bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// isKill is set, they are also killed. 280bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesenvoid RAFast::spillPhysReg(MachineBasicBlock &MBB, MachineInstr *MI, 281bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned PhysReg, bool isKill) { 282bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[PhysReg]) { 283bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 284bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 285bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 286bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 287bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 288bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (isKill) 289bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[PhysReg] = regFree; 290bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 291bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 292bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen spillVirtReg(MBB, MI, VirtReg, isKill); 293bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 294bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 295bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 296bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // This is a disabled register, we have to check aliases. 297bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(PhysReg); 298bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) { 299bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[Alias]) { 300bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 301bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 302bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 303bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 304bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (isKill) 305bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[Alias] = regFree; 306bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 307bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 308bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen spillVirtReg(MBB, MI, VirtReg, isKill); 309bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 310bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 311bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 312bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 31300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 31400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// assignVirtToPhysReg - This method updates local state so that we know 31500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// that PhysReg is the proper container for VirtReg now. The physical 31600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// register must not be used for anything else when this is called. 31700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// 31876b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund OlesenRAFast::LiveRegMap::iterator 31976b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund OlesenRAFast::assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) { 320bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen DEBUG(dbgs() << " Assigning %reg" << VirtReg << " to " 321bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen << TRI->getName(PhysReg) << "\n"); 322bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[PhysReg] = VirtReg; 32376b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen return LiveVirtRegs.insert(std::make_pair(VirtReg, PhysReg)).first; 32400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 32500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 326bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// allocVirtReg - Allocate a physical register for VirtReg. 32776b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund OlesenRAFast::LiveRegMap::iterator RAFast::allocVirtReg(MachineBasicBlock &MBB, 32876b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen MachineInstr *MI, 32976b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen unsigned VirtReg) { 330bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen const unsigned spillCost = 100; 331bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 332bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Can only allocate virtual registers"); 33300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 334bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); 335bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen TargetRegisterClass::iterator AOB = RC->allocation_order_begin(*MF); 336bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen TargetRegisterClass::iterator AOE = RC->allocation_order_end(*MF); 337bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 338bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // First try to find a completely free register. 339bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned BestCost = 0, BestReg = 0; 340bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen bool hasDisabled = false; 341bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (TargetRegisterClass::iterator I = AOB; I != AOE; ++I) { 342bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned PhysReg = *I; 343bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch(PhysRegState[PhysReg]) { 344bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 345bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen hasDisabled = true; 346bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 347bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 348bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 34976b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen if (!UsedInInstr.test(PhysReg)) 35076b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen return assignVirtToPhysReg(VirtReg, PhysReg); 351bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 352bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 353bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Grab the first spillable register we meet. 354bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!BestReg && !UsedInInstr.test(PhysReg)) { 355bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen BestReg = PhysReg; 356bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen BestCost = PhysRegDirty.test(PhysReg) ? spillCost : 1; 357bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 358bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 35900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 360bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 36100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 362bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen DEBUG(dbgs() << " Allocating %reg" << VirtReg << " from " << RC->getName() 363bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen << " candidate=" << TRI->getName(BestReg) << "\n"); 36400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 365bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Try to extend the working set for RC if there were any disabled registers. 366bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (hasDisabled && (!BestReg || BestCost >= spillCost)) { 367bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (TargetRegisterClass::iterator I = AOB; I != AOE; ++I) { 368bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned PhysReg = *I; 369bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (PhysRegState[PhysReg] != regDisabled || UsedInInstr.test(PhysReg)) 370bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 37100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 372bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Calculate the cost of bringing PhysReg into the working set. 373bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Cost=0; 374bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen bool Impossible = false; 375bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(PhysReg); 376bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) { 377bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (UsedInInstr.test(Alias)) { 378bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen Impossible = true; 379bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 380bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 381bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (PhysRegState[Alias]) { 382bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 383bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 384bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 385bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen Impossible = true; 386bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 387bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 388bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen Cost++; 389bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 390bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 391bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen Cost += PhysRegDirty.test(Alias) ? spillCost : 1; 392bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 393bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 394bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 395bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (Impossible) continue; 396bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen DEBUG(dbgs() << " - candidate " << TRI->getName(PhysReg) 397bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen << " cost=" << Cost << "\n"); 398bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!BestReg || Cost < BestCost) { 399bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen BestReg = PhysReg; 400bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen BestCost = Cost; 401bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (Cost < spillCost) break; 402bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 403bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 40400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 40500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 406bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (BestReg) { 407bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // BestCost is 0 when all aliases are already disabled. 408bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (BestCost) { 409bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (PhysRegState[BestReg] != regDisabled) 410bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen spillVirtReg(MBB, MI, PhysRegState[BestReg], true); 411bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen else { 412bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Make sure all aliases are disabled. 413bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(BestReg); 414bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) { 415bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (PhysRegState[Alias]) { 416bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 417bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 418bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 419bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[Alias] = regDisabled; 420bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 421bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 422bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen spillVirtReg(MBB, MI, PhysRegState[Alias], true); 423bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[Alias] = regDisabled; 424bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 425bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 426bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 427bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 42800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 42976b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen return assignVirtToPhysReg(VirtReg, BestReg); 430bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 43100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 432bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Nothing we can do. 433bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen std::string msg; 434bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen raw_string_ostream Msg(msg); 435bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen Msg << "Ran out of registers during register allocation!"; 436bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MI->isInlineAsm()) { 437bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen Msg << "\nPlease check your inline asm statement for " 438bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen << "invalid constraints:\n"; 439bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen MI->print(Msg, TM); 440bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 441bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen report_fatal_error(Msg.str()); 44276b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen return LiveVirtRegs.end(); 44300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 44400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 445bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// defineVirtReg - Allocate a register for VirtReg and mark it as dirty. 446bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesenunsigned RAFast::defineVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, 44776b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen unsigned OpNum, unsigned VirtReg) { 448bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 449bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Not a virtual register"); 45076b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen LiveRegMap::iterator i = LiveVirtRegs.find(VirtReg); 45176b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen if (i == LiveVirtRegs.end()) 45276b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen i = allocVirtReg(MBB, MI, VirtReg); 45376b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen i->second.LastUse = MI; 45476b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen i->second.LastOpNum = OpNum; 45576b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen UsedInInstr.set(i->second.PhysReg); 45676b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen PhysRegDirty.set(i->second.PhysReg); 45776b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen return i->second.PhysReg; 458bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 45900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 460bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// reloadVirtReg - Make sure VirtReg is available in a physreg and return it. 461bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesenunsigned RAFast::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, 46276b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen unsigned OpNum, unsigned VirtReg) { 463bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 464bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Not a virtual register"); 46576b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen LiveRegMap::iterator i = LiveVirtRegs.find(VirtReg); 46676b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen if (i == LiveVirtRegs.end()) { 46776b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen i = allocVirtReg(MBB, MI, VirtReg); 46876b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen PhysRegDirty.reset(i->second.PhysReg); 469bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); 470bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen int FrameIndex = getStackSpaceFor(VirtReg, RC); 471bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen DEBUG(dbgs() << " Reloading %reg" << VirtReg << " into " 47276b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen << TRI->getName(i->second.PhysReg) << "\n"); 47376b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen TII->loadRegFromStackSlot(MBB, MI, i->second.PhysReg, FrameIndex, RC, TRI); 474bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen ++NumLoads; 47500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 47676b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen i->second.LastUse = MI; 47776b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen i->second.LastOpNum = OpNum; 47876b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen UsedInInstr.set(i->second.PhysReg); 47976b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen return i->second.PhysReg; 480bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 48100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 482bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// reservePhysReg - Mark PhysReg as reserved. This is very similar to 483bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// defineVirtReg except the physreg is reverved instead of allocated. 484bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesenvoid RAFast::reservePhysReg(MachineBasicBlock &MBB, MachineInstr *MI, 485bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned PhysReg) { 48682b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen UsedInInstr.set(PhysReg); 487bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[PhysReg]) { 488bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 489bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 490bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 491bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[PhysReg] = regReserved; 492bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 493bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 494bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 495bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 496bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen spillVirtReg(MBB, MI, VirtReg, true); 497bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[PhysReg] = regReserved; 498bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 49900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 50000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 501bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // This is a disabled register, disable all aliases. 502bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(PhysReg); 503bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) { 50482b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen UsedInInstr.set(Alias); 505bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[Alias]) { 506bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 507bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 508bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 509bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 510bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // is a super register already reserved? 511bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (TRI->isSuperRegister(PhysReg, Alias)) 512bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 513bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 514bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 515bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen spillVirtReg(MBB, MI, VirtReg, true); 516bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 51700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 518bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[Alias] = regDisabled; 51900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 520bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[PhysReg] = regReserved; 52100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 52200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 523bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen// setPhysReg - Change MO the refer the PhysReg, considering subregs. 524bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesenvoid RAFast::setPhysReg(MachineOperand &MO, unsigned PhysReg) { 525bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (unsigned Idx = MO.getSubReg()) { 526bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen MO.setReg(PhysReg ? TRI->getSubReg(PhysReg, Idx) : 0); 527bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen MO.setSubReg(0); 528bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } else 529bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen MO.setReg(PhysReg); 53000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 53100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 53200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenvoid RAFast::AllocateBasicBlock(MachineBasicBlock &MBB) { 533bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen DEBUG(dbgs() << "\nBB#" << MBB.getNumber() << ", "<< MBB.getName() << "\n"); 53400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 535bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState.assign(TRI->getNumRegs(), regDisabled); 53676b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen assert(LiveVirtRegs.empty() && "Mapping not cleared form last block?"); 537bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegDirty.reset(); 53800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 539bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen MachineBasicBlock::iterator MII = MBB.begin(); 540bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 541bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Add live-in registers as live. 54200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen for (MachineBasicBlock::livein_iterator I = MBB.livein_begin(), 543bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen E = MBB.livein_end(); I != E; ++I) 544bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen reservePhysReg(MBB, MII, *I); 545bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 546bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen SmallVector<unsigned, 8> VirtKills, PhysKills, PhysDefs; 54700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 54800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Otherwise, sequentially allocate each instruction in the MBB. 54900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen while (MII != MBB.end()) { 55000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineInstr *MI = MII++; 55100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen const TargetInstrDesc &TID = MI->getDesc(); 55200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen DEBUG({ 553bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen dbgs() << "\nStarting RegAlloc of: " << *MI << "Working set:"; 554bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned Reg = 1, E = TRI->getNumRegs(); Reg != E; ++Reg) { 555bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (PhysRegState[Reg] == regDisabled) continue; 556bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen dbgs() << " " << TRI->getName(Reg); 557bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch(PhysRegState[Reg]) { 558bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 559bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 560bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 561bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen dbgs() << "(resv)"; 562bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 563bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 564bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen dbgs() << "=%reg" << PhysRegState[Reg]; 565bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (PhysRegDirty.test(Reg)) 566bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen dbgs() << "*"; 56776b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen assert(LiveVirtRegs[PhysRegState[Reg]].PhysReg == Reg && 568bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Bad inverse map"); 569bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 570bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 571bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 57200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen dbgs() << '\n'; 57376b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen // Check that LiveVirtRegs is the inverse. 57476b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen for (LiveRegMap::iterator i = LiveVirtRegs.begin(), 57576b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen e = LiveVirtRegs.end(); i != e; ++i) { 576bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(i->first) && 577bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Bad map key"); 57876b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen assert(TargetRegisterInfo::isPhysicalRegister(i->second.PhysReg) && 579bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Bad map value"); 58076b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen assert(PhysRegState[i->second.PhysReg] == i->first && 58176b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen "Bad inverse map"); 582bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 58300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen }); 58400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 585bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Debug values are not allowed to change codegen in any way. 586bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MI->isDebugValue()) { 58700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 58800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 589bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!MO.isReg()) continue; 590bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 591bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 59276b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen LiveRegMap::iterator i = LiveVirtRegs.find(Reg); 59376b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen if (i != LiveVirtRegs.end()) 59476b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen setPhysReg(MO, i->second.PhysReg); 59576b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen else 59676b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen MO.setReg(0); // We can't allocate a physreg for a DebugValue, sorry! 59700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 598bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Next instruction. 599bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 60000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 60100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 602bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Track registers used by instruction. 603bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen UsedInInstr.reset(); 604bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysDefs.clear(); 60500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 606bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // First scan. 607bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Mark physreg uses and early clobbers as used. 608bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Collect PhysKills. 609bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 61000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 611bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!MO.isReg()) continue; 61200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 613bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // FIXME: For now, don't trust kill flags 614bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MO.isUse()) MO.setIsKill(false); 61500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 616bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 617bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg) || 618bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen ReservedRegs.test(Reg)) continue; 619bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MO.isUse()) { 620bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysKills.push_back(Reg); // Any clean physreg use is a kill. 621bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen UsedInInstr.set(Reg); 622bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } else if (MO.isEarlyClobber()) { 623bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen spillPhysReg(MBB, MI, Reg, true); 624bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen UsedInInstr.set(Reg); 625bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysDefs.push_back(Reg); 62600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 62700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 62800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 629bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Second scan. 630bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Allocate virtreg uses and early clobbers. 631bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Collect VirtKills 63200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 63300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 634bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!MO.isReg()) continue; 63500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen unsigned Reg = MO.getReg(); 636bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 637bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MO.isUse()) { 63876b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen setPhysReg(MO, reloadVirtReg(MBB, MI, i, Reg)); 639bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MO.isKill()) 640bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen VirtKills.push_back(Reg); 641bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } else if (MO.isEarlyClobber()) { 64276b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen unsigned PhysReg = defineVirtReg(MBB, MI, i, Reg); 643bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen setPhysReg(MO, PhysReg); 644bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysDefs.push_back(PhysReg); 64500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 64600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 64700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 648bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Process virtreg kills 649bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned i = 0, e = VirtKills.size(); i != e; ++i) 650bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen killVirtReg(VirtKills[i]); 651bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen VirtKills.clear(); 65200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 653bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Process physreg kills 654bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned i = 0, e = PhysKills.size(); i != e; ++i) 655bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen killPhysReg(PhysKills[i]); 656bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysKills.clear(); 65700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 65882b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen MF->getRegInfo().addPhysRegsUsed(UsedInInstr); 65982b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen 660bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Track registers defined by instruction - early clobbers at this point. 661bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen UsedInInstr.reset(); 662bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned i = 0, e = PhysDefs.size(); i != e; ++i) { 663bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned PhysReg = PhysDefs[i]; 664bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen UsedInInstr.set(PhysReg); 665bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(PhysReg); 666bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) 667bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen UsedInInstr.set(Alias); 66800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 66900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 670bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Third scan. 671bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Allocate defs and collect dead defs. 67200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 67300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 674bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!MO.isReg() || !MO.isDef() || !MO.getReg()) continue; 675bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 67600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 677bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 678bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (ReservedRegs.test(Reg)) continue; 679bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MO.isImplicit()) 680bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen spillPhysReg(MBB, MI, Reg, true); 681bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen else 682bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen reservePhysReg(MBB, MI, Reg); 683bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MO.isDead()) 684bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysKills.push_back(Reg); 685bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 68600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 687bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MO.isDead()) 688bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen VirtKills.push_back(Reg); 68976b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen setPhysReg(MO, defineVirtReg(MBB, MI, i, Reg)); 69000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 69100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 692bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Spill all dirty virtregs before a call, in case of an exception. 693bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (TID.isCall()) { 694bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen DEBUG(dbgs() << " Spilling remaining registers before call.\n"); 695bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen spillAll(MBB, MI); 69600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 69700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 698bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Process virtreg deads. 699bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned i = 0, e = VirtKills.size(); i != e; ++i) 700bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen killVirtReg(VirtKills[i]); 701bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen VirtKills.clear(); 702bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 703bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Process physreg deads. 704bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned i = 0, e = PhysKills.size(); i != e; ++i) 705bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen killPhysReg(PhysKills[i]); 706bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysKills.clear(); 70782b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen 70882b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen MF->getRegInfo().addPhysRegsUsed(UsedInInstr); 70900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 71000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 711bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Spill all physical registers holding virtual registers now. 712bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen DEBUG(dbgs() << "Killing live registers at end of block.\n"); 71300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineBasicBlock::iterator MI = MBB.getFirstTerminator(); 71476b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen while (!LiveVirtRegs.empty()) 71576b4d5a0210f161c08543f00f355955c94d3f2ecJakob Stoklund Olesen spillVirtReg(MBB, MI, LiveVirtRegs.begin()->first, true); 71600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 717bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen DEBUG(MBB.dump()); 71800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 71900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 72000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// runOnMachineFunction - Register allocate the whole function 72100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// 72200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenbool RAFast::runOnMachineFunction(MachineFunction &Fn) { 72300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen DEBUG(dbgs() << "Machine Function\n"); 724bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen DEBUG(Fn.dump()); 72500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MF = &Fn; 72600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen TM = &Fn.getTarget(); 72700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen TRI = TM->getRegisterInfo(); 72800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen TII = TM->getInstrInfo(); 72900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 730bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegDirty.resize(TRI->getNumRegs()); 73100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen UsedInInstr.resize(TRI->getNumRegs()); 732bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen ReservedRegs = TRI->getReservedRegs(*MF); 73300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 73400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // initialize the virtual->physical register map to have a 'null' 73500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // mapping for all virtual registers 73600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen unsigned LastVirtReg = MF->getRegInfo().getLastVirtReg(); 73700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen StackSlotForVirtReg.grow(LastVirtReg); 73800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 73900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Loop over all of the basic blocks, eliminating virtual register references 74000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); 74100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MBB != MBBe; ++MBB) 74200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen AllocateBasicBlock(*MBB); 74300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 74482b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen // Make sure the set of used physregs is closed under subreg operations. 74582b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen MF->getRegInfo().closePhysRegsUsed(*TRI); 74682b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen 74700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen StackSlotForVirtReg.clear(); 74800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return true; 74900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 75000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 75100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund OlesenFunctionPass *llvm::createFastRegisterAllocator() { 75200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return new RAFast(); 75300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 754