RegAllocFast.cpp revision 82b07dc4995d48065bd95affff4d8513a5cad4f2
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 59bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Virt2PhysMap - This map contains entries for each virtual register 6000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // that is currently available in a physical register. 61bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen DenseMap<unsigned, unsigned> Virt2PhysMap; 6200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 63bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // RegState - Track the state of a physical register. 64bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen enum RegState { 65bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // A disabled register is not available for allocation, but an alias may 66bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // be in use. A register can only be moved out of the disabled state if 67bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // all aliases are disabled. 68bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen regDisabled, 69bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 70bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // A free register is not currently in use and can be allocated 71bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // immediately without checking aliases. 72bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen regFree, 73bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 74bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // A reserved register has been assigned expolicitly (e.g., setting up a 75bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // call parameter), and it remains reserved until it is used. 76bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen regReserved 7700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 78bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // A register state may also be a virtual register number, indication that 79bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // the physical register is currently allocated to a virtual register. In 80bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // that case, Virt2PhysMap contains the inverse mapping. 81bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen }; 82bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 83bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // PhysRegState - One of the RegState enums, or a virtreg. 84bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen std::vector<unsigned> PhysRegState; 8500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 8600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // UsedInInstr - BitVector of physregs that are used in the current 8700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // instruction, and so cannot be allocated. 8800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen BitVector UsedInInstr; 8900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 90bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // PhysRegDirty - A bit is set for each physreg that holds a dirty virtual 91bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // register. Bits for physregs that are not mapped to a virtual register are 92bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // invalid. 93bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen BitVector PhysRegDirty; 9400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 95bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // ReservedRegs - vector of reserved physical registers. 96bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen BitVector ReservedRegs; 9700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 9800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen public: 9900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen virtual const char *getPassName() const { 10000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return "Fast Register Allocator"; 10100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 10200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 10300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen virtual void getAnalysisUsage(AnalysisUsage &AU) const { 10400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen AU.setPreservesCFG(); 10500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen AU.addRequiredID(PHIEliminationID); 10600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen AU.addRequiredID(TwoAddressInstructionPassID); 10700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineFunctionPass::getAnalysisUsage(AU); 10800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 10900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 11000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen private: 11100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen bool runOnMachineFunction(MachineFunction &Fn); 11200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen void AllocateBasicBlock(MachineBasicBlock &MBB); 11300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen int getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC); 114bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen void killVirtReg(unsigned VirtReg); 11500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen void spillVirtReg(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, 116bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned VirtReg, bool isKill); 117bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen void killPhysReg(unsigned PhysReg); 11800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen void spillPhysReg(MachineBasicBlock &MBB, MachineInstr *I, 119bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned PhysReg, bool isKill); 12000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen void assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg); 121bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned allocVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, 122bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned VirtReg); 123bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned defineVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, 124bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned VirtReg); 125bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, 126bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned VirtReg); 127bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen void reservePhysReg(MachineBasicBlock &MBB, MachineInstr *MI, 128bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned PhysReg); 129bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen void spillAll(MachineBasicBlock &MBB, MachineInstr *MI); 130bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen void setPhysReg(MachineOperand &MO, unsigned PhysReg); 13100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen }; 13200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen char RAFast::ID = 0; 13300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 13400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 13500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// getStackSpaceFor - This allocates space for the specified virtual register 13600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// to be held on the stack. 13700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenint RAFast::getStackSpaceFor(unsigned VirtReg, const TargetRegisterClass *RC) { 13800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Find the location Reg would belong... 13900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen int SS = StackSlotForVirtReg[VirtReg]; 14000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen if (SS != -1) 14100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return SS; // Already has space allocated? 14200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 14300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Allocate a new stack object for this spill location... 14400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen int FrameIdx = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(), 14500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen RC->getAlignment()); 14600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 14700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Assign the slot. 14800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen StackSlotForVirtReg[VirtReg] = FrameIdx; 14900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return FrameIdx; 15000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 15100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 152bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// killVirtReg - Mark virtreg as no longer available. 153bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesenvoid RAFast::killVirtReg(unsigned VirtReg) { 154bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 155bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "killVirtReg needs a virtual register"); 156bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen DEBUG(dbgs() << " Killing %reg" << VirtReg << "\n"); 157bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen DenseMap<unsigned,unsigned>::iterator i = Virt2PhysMap.find(VirtReg); 158bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (i == Virt2PhysMap.end()) return; 159bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned PhysReg = i->second; 160bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(PhysRegState[PhysReg] == VirtReg && "Broken RegState mapping"); 161bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[PhysReg] = regFree; 162bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen Virt2PhysMap.erase(i); 16300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 16400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 165bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// spillVirtReg - This method spills the value specified by VirtReg into the 166bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// corresponding stack slot if needed. If isKill is set, the register is also 167bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// killed. 16800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenvoid RAFast::spillVirtReg(MachineBasicBlock &MBB, 169bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen MachineBasicBlock::iterator I, 170bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned VirtReg, bool isKill) { 171bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 172bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Spilling a physical register is illegal!"); 173bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen DenseMap<unsigned,unsigned>::iterator i = Virt2PhysMap.find(VirtReg); 174bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(i != Virt2PhysMap.end() && "Spilling unmapped virtual register"); 175bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned PhysReg = i->second; 176bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(PhysRegState[PhysReg] == VirtReg && "Broken RegState mapping"); 177bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 178bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (PhysRegDirty.test(PhysReg)) { 179bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegDirty.reset(PhysReg); 180bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen DEBUG(dbgs() << " Spilling register " << TRI->getName(PhysReg) 181bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen << " containing %reg" << VirtReg); 18200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); 18300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen int FrameIndex = getStackSpaceFor(VirtReg, RC); 184bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen DEBUG(dbgs() << " to stack slot #" << FrameIndex << "\n"); 185746ad69e088176819981b4b2c5ac8dcd49f5e60eEvan Cheng TII->storeRegToStackSlot(MBB, I, PhysReg, isKill, FrameIndex, RC, TRI); 18600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen ++NumStores; // Update statistics 18700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 18800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 189bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (isKill) { 190bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[PhysReg] = regFree; 191bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen Virt2PhysMap.erase(i); 192bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 19300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 19400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 195bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// spillAll - Spill all dirty virtregs without killing them. 196bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesenvoid RAFast::spillAll(MachineBasicBlock &MBB, MachineInstr *MI) { 197bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen SmallVector<unsigned, 16> Dirty; 198bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (DenseMap<unsigned,unsigned>::iterator i = Virt2PhysMap.begin(), 199bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen e = Virt2PhysMap.end(); i != e; ++i) 200bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (PhysRegDirty.test(i->second)) 201bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen Dirty.push_back(i->first); 202bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned i = 0, e = Dirty.size(); i != e; ++i) 203bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen spillVirtReg(MBB, MI, Dirty[i], false); 204bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 20500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 206bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// killPhysReg - Kill any virtual register aliased by PhysReg. 207bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesenvoid RAFast::killPhysReg(unsigned PhysReg) { 208bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Fast path for the normal case. 209bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[PhysReg]) { 210bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 211bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 212bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 213bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 214bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 215bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[PhysReg] = regFree; 216bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 217bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 218bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen killVirtReg(VirtReg); 21900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return; 22000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 22100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 222bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // This is a disabled register, we have to check aliases. 223bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(PhysReg); 224bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) { 225bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[Alias]) { 226bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 227bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 228bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 229bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 230bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[Alias] = regFree; 231bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 232bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 233bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen killVirtReg(VirtReg); 234bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 235bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 23600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 23700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 23800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 239bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// spillPhysReg - Spill any dirty virtual registers that aliases PhysReg. If 240bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// isKill is set, they are also killed. 241bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesenvoid RAFast::spillPhysReg(MachineBasicBlock &MBB, MachineInstr *MI, 242bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned PhysReg, bool isKill) { 243bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[PhysReg]) { 244bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 245bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 246bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 247bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 248bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 249bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (isKill) 250bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[PhysReg] = regFree; 251bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 252bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 253bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen spillVirtReg(MBB, MI, VirtReg, isKill); 254bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 255bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 256bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 257bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // This is a disabled register, we have to check aliases. 258bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(PhysReg); 259bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) { 260bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[Alias]) { 261bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 262bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 263bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 264bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 265bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (isKill) 266bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[Alias] = regFree; 267bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 268bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 269bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen spillVirtReg(MBB, MI, VirtReg, isKill); 270bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 271bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 272bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 273bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 27400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 27500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// assignVirtToPhysReg - This method updates local state so that we know 27600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// that PhysReg is the proper container for VirtReg now. The physical 27700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// register must not be used for anything else when this is called. 27800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// 27900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenvoid RAFast::assignVirtToPhysReg(unsigned VirtReg, unsigned PhysReg) { 280bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen DEBUG(dbgs() << " Assigning %reg" << VirtReg << " to " 281bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen << TRI->getName(PhysReg) << "\n"); 282bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen Virt2PhysMap.insert(std::make_pair(VirtReg, PhysReg)); 283bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[PhysReg] = VirtReg; 28400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 28500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 286bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// allocVirtReg - Allocate a physical register for VirtReg. 287bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesenunsigned RAFast::allocVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, 288bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned VirtReg) { 289bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen const unsigned spillCost = 100; 290bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 291bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Can only allocate virtual registers"); 29200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 293bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); 294bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen TargetRegisterClass::iterator AOB = RC->allocation_order_begin(*MF); 295bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen TargetRegisterClass::iterator AOE = RC->allocation_order_end(*MF); 296bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 297bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // First try to find a completely free register. 298bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned BestCost = 0, BestReg = 0; 299bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen bool hasDisabled = false; 300bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (TargetRegisterClass::iterator I = AOB; I != AOE; ++I) { 301bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned PhysReg = *I; 302bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch(PhysRegState[PhysReg]) { 303bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 304bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen hasDisabled = true; 305bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 306bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 307bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 308bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!UsedInInstr.test(PhysReg)) { 309bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assignVirtToPhysReg(VirtReg, PhysReg); 310bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return PhysReg; 311bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 312bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 313bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 314bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Grab the first spillable register we meet. 315bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!BestReg && !UsedInInstr.test(PhysReg)) { 316bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen BestReg = PhysReg; 317bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen BestCost = PhysRegDirty.test(PhysReg) ? spillCost : 1; 318bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 319bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 32000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 321bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 32200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 323bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen DEBUG(dbgs() << " Allocating %reg" << VirtReg << " from " << RC->getName() 324bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen << " candidate=" << TRI->getName(BestReg) << "\n"); 32500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 326bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Try to extend the working set for RC if there were any disabled registers. 327bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (hasDisabled && (!BestReg || BestCost >= spillCost)) { 328bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (TargetRegisterClass::iterator I = AOB; I != AOE; ++I) { 329bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned PhysReg = *I; 330bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (PhysRegState[PhysReg] != regDisabled || UsedInInstr.test(PhysReg)) 331bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 33200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 333bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Calculate the cost of bringing PhysReg into the working set. 334bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Cost=0; 335bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen bool Impossible = false; 336bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(PhysReg); 337bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) { 338bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (UsedInInstr.test(Alias)) { 339bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen Impossible = true; 340bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 341bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 342bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (PhysRegState[Alias]) { 343bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 344bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 345bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 346bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen Impossible = true; 347bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 348bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 349bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen Cost++; 350bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 351bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 352bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen Cost += PhysRegDirty.test(Alias) ? spillCost : 1; 353bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 354bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 355bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 356bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (Impossible) continue; 357bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen DEBUG(dbgs() << " - candidate " << TRI->getName(PhysReg) 358bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen << " cost=" << Cost << "\n"); 359bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!BestReg || Cost < BestCost) { 360bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen BestReg = PhysReg; 361bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen BestCost = Cost; 362bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (Cost < spillCost) break; 363bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 364bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 36500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 36600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 367bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (BestReg) { 368bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // BestCost is 0 when all aliases are already disabled. 369bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (BestCost) { 370bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (PhysRegState[BestReg] != regDisabled) 371bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen spillVirtReg(MBB, MI, PhysRegState[BestReg], true); 372bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen else { 373bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Make sure all aliases are disabled. 374bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(BestReg); 375bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) { 376bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (PhysRegState[Alias]) { 377bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 378bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 379bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 380bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[Alias] = regDisabled; 381bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 382bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 383bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen spillVirtReg(MBB, MI, PhysRegState[Alias], true); 384bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[Alias] = regDisabled; 385bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 386bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 387bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 388bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 38900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 390bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assignVirtToPhysReg(VirtReg, BestReg); 391bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return BestReg; 392bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 39300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 394bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Nothing we can do. 395bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen std::string msg; 396bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen raw_string_ostream Msg(msg); 397bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen Msg << "Ran out of registers during register allocation!"; 398bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MI->isInlineAsm()) { 399bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen Msg << "\nPlease check your inline asm statement for " 400bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen << "invalid constraints:\n"; 401bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen MI->print(Msg, TM); 402bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 403bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen report_fatal_error(Msg.str()); 404bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return 0; 40500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 40600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 407bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// defineVirtReg - Allocate a register for VirtReg and mark it as dirty. 408bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesenunsigned RAFast::defineVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, 409bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned VirtReg) { 410bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 411bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Not a virtual register"); 412bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned PhysReg = Virt2PhysMap.lookup(VirtReg); 413bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!PhysReg) 414bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysReg = allocVirtReg(MBB, MI, VirtReg); 415bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen UsedInInstr.set(PhysReg); 416bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegDirty.set(PhysReg); 417bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return PhysReg; 418bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 41900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 420bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// reloadVirtReg - Make sure VirtReg is available in a physreg and return it. 421bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesenunsigned RAFast::reloadVirtReg(MachineBasicBlock &MBB, MachineInstr *MI, 422bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned VirtReg) { 423bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(VirtReg) && 424bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Not a virtual register"); 425bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned PhysReg = Virt2PhysMap.lookup(VirtReg); 426bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!PhysReg) { 427bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysReg = allocVirtReg(MBB, MI, VirtReg); 428bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegDirty.reset(PhysReg); 429bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(VirtReg); 430bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen int FrameIndex = getStackSpaceFor(VirtReg, RC); 431bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen DEBUG(dbgs() << " Reloading %reg" << VirtReg << " into " 432bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen << TRI->getName(PhysReg) << "\n"); 433bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen TII->loadRegFromStackSlot(MBB, MI, PhysReg, FrameIndex, RC, TRI); 434bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen ++NumLoads; 43500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 436bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen UsedInInstr.set(PhysReg); 437bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return PhysReg; 438bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen} 43900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 440bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// reservePhysReg - Mark PhysReg as reserved. This is very similar to 441bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen/// defineVirtReg except the physreg is reverved instead of allocated. 442bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesenvoid RAFast::reservePhysReg(MachineBasicBlock &MBB, MachineInstr *MI, 443bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned PhysReg) { 44482b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen UsedInInstr.set(PhysReg); 445bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[PhysReg]) { 446bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 447bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 448bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 449bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[PhysReg] = regReserved; 450bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 451bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 452bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 453bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 454bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen spillVirtReg(MBB, MI, VirtReg, true); 455bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[PhysReg] = regReserved; 456bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 45700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 45800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 459bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // This is a disabled register, disable all aliases. 460bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(PhysReg); 461bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) { 46282b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen UsedInInstr.set(Alias); 463bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch (unsigned VirtReg = PhysRegState[Alias]) { 464bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regDisabled: 465bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 466bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 467bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 468bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // is a super register already reserved? 469bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (TRI->isSuperRegister(PhysReg, Alias)) 470bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen return; 471bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 472bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 473bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen spillVirtReg(MBB, MI, VirtReg, true); 474bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 47500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 476bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[Alias] = regDisabled; 47700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 478bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState[PhysReg] = regReserved; 47900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 48000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 481bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen// setPhysReg - Change MO the refer the PhysReg, considering subregs. 482bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesenvoid RAFast::setPhysReg(MachineOperand &MO, unsigned PhysReg) { 483bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (unsigned Idx = MO.getSubReg()) { 484bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen MO.setReg(PhysReg ? TRI->getSubReg(PhysReg, Idx) : 0); 485bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen MO.setSubReg(0); 486bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } else 487bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen MO.setReg(PhysReg); 48800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 48900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 49000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenvoid RAFast::AllocateBasicBlock(MachineBasicBlock &MBB) { 491bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen DEBUG(dbgs() << "\nBB#" << MBB.getNumber() << ", "<< MBB.getName() << "\n"); 49200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 493bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegState.assign(TRI->getNumRegs(), regDisabled); 494bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(Virt2PhysMap.empty() && "Mapping not cleared form last block?"); 495bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegDirty.reset(); 49600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 497bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen MachineBasicBlock::iterator MII = MBB.begin(); 498bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 499bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Add live-in registers as live. 50000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen for (MachineBasicBlock::livein_iterator I = MBB.livein_begin(), 501bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen E = MBB.livein_end(); I != E; ++I) 502bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen reservePhysReg(MBB, MII, *I); 503bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 504bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen SmallVector<unsigned, 8> VirtKills, PhysKills, PhysDefs; 50500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 50600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Otherwise, sequentially allocate each instruction in the MBB. 50700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen while (MII != MBB.end()) { 50800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineInstr *MI = MII++; 50900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen const TargetInstrDesc &TID = MI->getDesc(); 51000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen DEBUG({ 511bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen dbgs() << "\nStarting RegAlloc of: " << *MI << "Working set:"; 512bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned Reg = 1, E = TRI->getNumRegs(); Reg != E; ++Reg) { 513bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (PhysRegState[Reg] == regDisabled) continue; 514bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen dbgs() << " " << TRI->getName(Reg); 515bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen switch(PhysRegState[Reg]) { 516bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regFree: 517bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 518bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen case regReserved: 519bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen dbgs() << "(resv)"; 520bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 521bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen default: 522bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen dbgs() << "=%reg" << PhysRegState[Reg]; 523bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (PhysRegDirty.test(Reg)) 524bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen dbgs() << "*"; 525bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(Virt2PhysMap.lookup(PhysRegState[Reg]) == Reg && 526bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Bad inverse map"); 527bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen break; 528bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 529bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 53000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen dbgs() << '\n'; 531bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Check that Virt2PhysMap is the inverse. 532bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (DenseMap<unsigned,unsigned>::iterator i = Virt2PhysMap.begin(), 533bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen e = Virt2PhysMap.end(); i != e; ++i) { 534bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(i->first) && 535bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Bad map key"); 536bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(TargetRegisterInfo::isPhysicalRegister(i->second) && 537bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen "Bad map value"); 538bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen assert(PhysRegState[i->second] == i->first && "Bad inverse map"); 539bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } 54000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen }); 54100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 542bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Debug values are not allowed to change codegen in any way. 543bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MI->isDebugValue()) { 54400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 54500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 546bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!MO.isReg()) continue; 547bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 548bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 549bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // This may be 0 if the register is currently spilled. Tough. 550bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen setPhysReg(MO, Virt2PhysMap.lookup(Reg)); 55100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 552bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Next instruction. 553bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 55400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 55500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 556bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Track registers used by instruction. 557bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen UsedInInstr.reset(); 558bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysDefs.clear(); 55900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 560bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // First scan. 561bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Mark physreg uses and early clobbers as used. 562bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Collect PhysKills. 563bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 56400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 565bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!MO.isReg()) continue; 56600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 567bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // FIXME: For now, don't trust kill flags 568bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MO.isUse()) MO.setIsKill(false); 56900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 570bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 571bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!Reg || !TargetRegisterInfo::isPhysicalRegister(Reg) || 572bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen ReservedRegs.test(Reg)) continue; 573bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MO.isUse()) { 574bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysKills.push_back(Reg); // Any clean physreg use is a kill. 575bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen UsedInInstr.set(Reg); 576bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } else if (MO.isEarlyClobber()) { 577bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen spillPhysReg(MBB, MI, Reg, true); 578bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen UsedInInstr.set(Reg); 579bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysDefs.push_back(Reg); 58000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 58100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 58200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 583bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Second scan. 584bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Allocate virtreg uses and early clobbers. 585bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Collect VirtKills 58600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 58700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 588bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!MO.isReg()) continue; 58900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen unsigned Reg = MO.getReg(); 590bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!Reg || TargetRegisterInfo::isPhysicalRegister(Reg)) continue; 591bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MO.isUse()) { 592bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen setPhysReg(MO, reloadVirtReg(MBB, MI, Reg)); 593bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MO.isKill()) 594bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen VirtKills.push_back(Reg); 595bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen } else if (MO.isEarlyClobber()) { 596bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned PhysReg = defineVirtReg(MBB, MI, Reg); 597bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen setPhysReg(MO, PhysReg); 598bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysDefs.push_back(PhysReg); 59900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 60000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 60100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 602bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Process virtreg kills 603bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned i = 0, e = VirtKills.size(); i != e; ++i) 604bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen killVirtReg(VirtKills[i]); 605bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen VirtKills.clear(); 60600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 607bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Process physreg kills 608bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned i = 0, e = PhysKills.size(); i != e; ++i) 609bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen killPhysReg(PhysKills[i]); 610bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysKills.clear(); 61100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 61282b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen MF->getRegInfo().addPhysRegsUsed(UsedInInstr); 61382b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen 614bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Track registers defined by instruction - early clobbers at this point. 615bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen UsedInInstr.reset(); 616bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned i = 0, e = PhysDefs.size(); i != e; ++i) { 617bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned PhysReg = PhysDefs[i]; 618bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen UsedInInstr.set(PhysReg); 619bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(PhysReg); 620bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Alias = *AS; ++AS) 621bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen UsedInInstr.set(Alias); 62200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 62300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 624bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Third scan. 625bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Allocate defs and collect dead defs. 62600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 62700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineOperand &MO = MI->getOperand(i); 628bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (!MO.isReg() || !MO.isDef() || !MO.getReg()) continue; 629bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen unsigned Reg = MO.getReg(); 63000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 631bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Reg)) { 632bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (ReservedRegs.test(Reg)) continue; 633bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MO.isImplicit()) 634bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen spillPhysReg(MBB, MI, Reg, true); 635bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen else 636bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen reservePhysReg(MBB, MI, Reg); 637bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MO.isDead()) 638bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysKills.push_back(Reg); 639bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen continue; 64000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 641bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (MO.isDead()) 642bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen VirtKills.push_back(Reg); 643bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen setPhysReg(MO, defineVirtReg(MBB, MI, Reg)); 64400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 64500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 646bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Spill all dirty virtregs before a call, in case of an exception. 647bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen if (TID.isCall()) { 648bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen DEBUG(dbgs() << " Spilling remaining registers before call.\n"); 649bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen spillAll(MBB, MI); 65000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 65100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 652bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Process virtreg deads. 653bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned i = 0, e = VirtKills.size(); i != e; ++i) 654bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen killVirtReg(VirtKills[i]); 655bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen VirtKills.clear(); 656bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen 657bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Process physreg deads. 658bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen for (unsigned i = 0, e = PhysKills.size(); i != e; ++i) 659bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen killPhysReg(PhysKills[i]); 660bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysKills.clear(); 66182b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen 66282b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen MF->getRegInfo().addPhysRegsUsed(UsedInInstr); 66300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen } 66400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 665bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen // Spill all physical registers holding virtual registers now. 666bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen DEBUG(dbgs() << "Killing live registers at end of block.\n"); 66700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MachineBasicBlock::iterator MI = MBB.getFirstTerminator(); 668bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen while (!Virt2PhysMap.empty()) 669bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen spillVirtReg(MBB, MI, Virt2PhysMap.begin()->first, true); 67000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 671bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen DEBUG(MBB.dump()); 67200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 67300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 67400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// runOnMachineFunction - Register allocate the whole function 67500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen/// 67600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesenbool RAFast::runOnMachineFunction(MachineFunction &Fn) { 67700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen DEBUG(dbgs() << "Machine Function\n"); 678bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen DEBUG(Fn.dump()); 67900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MF = &Fn; 68000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen TM = &Fn.getTarget(); 68100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen TRI = TM->getRegisterInfo(); 68200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen TII = TM->getInstrInfo(); 68300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 684bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen PhysRegDirty.resize(TRI->getNumRegs()); 68500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen UsedInInstr.resize(TRI->getNumRegs()); 686bbf33b38aaaa6cdbdd2c6a595aa081734308ce83Jakob Stoklund Olesen ReservedRegs = TRI->getReservedRegs(*MF); 68700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 68800207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // initialize the virtual->physical register map to have a 'null' 68900207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // mapping for all virtual registers 69000207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen unsigned LastVirtReg = MF->getRegInfo().getLastVirtReg(); 69100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen StackSlotForVirtReg.grow(LastVirtReg); 69200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 69300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen // Loop over all of the basic blocks, eliminating virtual register references 69400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); 69500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen MBB != MBBe; ++MBB) 69600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen AllocateBasicBlock(*MBB); 69700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 69882b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen // Make sure the set of used physregs is closed under subreg operations. 69982b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen MF->getRegInfo().closePhysRegsUsed(*TRI); 70082b07dc4995d48065bd95affff4d8513a5cad4f2Jakob Stoklund Olesen 70100207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen StackSlotForVirtReg.clear(); 70200207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return true; 70300207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 70400207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen 70500207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund OlesenFunctionPass *llvm::createFastRegisterAllocator() { 70600207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen return new RAFast(); 70700207237ddfffe93b275914d086a0c7da1bbf63bJakob Stoklund Olesen} 708