VirtRegMap.cpp revision 7f690e625807b9320bf4ae437b8f35258acc99de
134d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos//===-- llvm/CodeGen/VirtRegMap.cpp - Virtual Register Map ----------------===// 234d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// 334d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// The LLVM Compiler Infrastructure 434d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// 534d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// This file was developed by the LLVM research group and is distributed under 634d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// the University of Illinois Open Source License. See LICENSE.TXT for details. 734d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// 834d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos//===----------------------------------------------------------------------===// 934d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// 108c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner// This file implements the VirtRegMap class. 118c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner// 128c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner// It also contains implementations of the the Spiller interface, which, given a 138c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner// virtual register map and a machine function, eliminates all virtual 148c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner// references by replacing them with physical register references - adding spill 150d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos// code as necessary. 1634d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// 1734d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos//===----------------------------------------------------------------------===// 1834d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos 198c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner#define DEBUG_TYPE "spiller" 2034d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos#include "VirtRegMap.h" 210d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos#include "llvm/Function.h" 2234d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos#include "llvm/CodeGen/MachineFrameInfo.h" 238c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner#include "llvm/CodeGen/MachineFunction.h" 248c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner#include "llvm/CodeGen/SSARegMap.h" 2534d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos#include "llvm/Target/TargetMachine.h" 260d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos#include "llvm/Target/TargetInstrInfo.h" 27551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 28551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 29551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 30551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/STLExtras.h" 3134d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenosusing namespace llvm; 3234d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos 3334d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenosnamespace { 348c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner Statistic<> NumSpills("spiller", "Number of register spills"); 358c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner Statistic<> NumStores("spiller", "Number of stores added"); 368c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner Statistic<> NumLoads ("spiller", "Number of loads added"); 378c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 388c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner enum SpillerName { simple, local }; 398c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 408c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner cl::opt<SpillerName> 418c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner SpillerOpt("spiller", 428c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner cl::desc("Spiller to use: (default: local)"), 438c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner cl::Prefix, 448c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner cl::values(clEnumVal(simple, " simple spiller"), 458c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner clEnumVal(local, " local spiller"), 468c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner clEnumValEnd), 478c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner cl::init(local)); 488c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner} 498c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 508c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner//===----------------------------------------------------------------------===// 518c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner// VirtRegMap implementation 528c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner//===----------------------------------------------------------------------===// 538c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 548c4d88d3697835371ecf6823f4142af13603ad2dChris Lattnervoid VirtRegMap::grow() { 557f690e625807b9320bf4ae437b8f35258acc99deChris Lattner Virt2PhysMap.grow(MF.getSSARegMap()->getLastVirtReg()); 567f690e625807b9320bf4ae437b8f35258acc99deChris Lattner Virt2StackSlotMap.grow(MF.getSSARegMap()->getLastVirtReg()); 5734d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos} 5834d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos 598c4d88d3697835371ecf6823f4142af13603ad2dChris Lattnerint VirtRegMap::assignVirt2StackSlot(unsigned virtReg) { 608c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner assert(MRegisterInfo::isVirtualRegister(virtReg)); 617f690e625807b9320bf4ae437b8f35258acc99deChris Lattner assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT && 628c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner "attempt to assign stack slot to already spilled register"); 637f690e625807b9320bf4ae437b8f35258acc99deChris Lattner const TargetRegisterClass* RC = MF.getSSARegMap()->getRegClass(virtReg); 647f690e625807b9320bf4ae437b8f35258acc99deChris Lattner int frameIndex = MF.getFrameInfo()->CreateStackObject(RC->getSize(), 657f690e625807b9320bf4ae437b8f35258acc99deChris Lattner RC->getAlignment()); 667f690e625807b9320bf4ae437b8f35258acc99deChris Lattner Virt2StackSlotMap[virtReg] = frameIndex; 678c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner ++NumSpills; 688c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner return frameIndex; 6934d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos} 7034d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos 718c4d88d3697835371ecf6823f4142af13603ad2dChris Lattnervoid VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int frameIndex) { 728c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner assert(MRegisterInfo::isVirtualRegister(virtReg)); 737f690e625807b9320bf4ae437b8f35258acc99deChris Lattner assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT && 748c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner "attempt to assign stack slot to already spilled register"); 757f690e625807b9320bf4ae437b8f35258acc99deChris Lattner Virt2StackSlotMap[virtReg] = frameIndex; 7638af59a43c4176d8f34bd26faeb18b23080a1d9bAlkis Evlogimenos} 7738af59a43c4176d8f34bd26faeb18b23080a1d9bAlkis Evlogimenos 785f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenosvoid VirtRegMap::virtFolded(unsigned virtReg, 795f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos MachineInstr* oldMI, 808c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner MachineInstr* newMI) { 818c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner // move previous memory references folded to new instruction 827f690e625807b9320bf4ae437b8f35258acc99deChris Lattner MI2VirtMapTy::iterator i, e; 837f690e625807b9320bf4ae437b8f35258acc99deChris Lattner std::vector<MI2VirtMapTy::mapped_type> regs; 847f690e625807b9320bf4ae437b8f35258acc99deChris Lattner for (tie(i, e) = MI2VirtMap.equal_range(oldMI); i != e; ) { 858c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner regs.push_back(i->second); 867f690e625807b9320bf4ae437b8f35258acc99deChris Lattner MI2VirtMap.erase(i++); 878c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 888c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner for (unsigned i = 0, e = regs.size(); i != e; ++i) 897f690e625807b9320bf4ae437b8f35258acc99deChris Lattner MI2VirtMap.insert(std::make_pair(newMI, i)); 908c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 918c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner // add new memory reference 927f690e625807b9320bf4ae437b8f35258acc99deChris Lattner MI2VirtMap.insert(std::make_pair(newMI, virtReg)); 938c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner} 945f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos 957f690e625807b9320bf4ae437b8f35258acc99deChris Lattnervoid VirtRegMap::print(std::ostream &OS) const { 967f690e625807b9320bf4ae437b8f35258acc99deChris Lattner const MRegisterInfo* MRI = MF.getTarget().getRegisterInfo(); 978c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 987f690e625807b9320bf4ae437b8f35258acc99deChris Lattner OS << "********** REGISTER MAP **********\n"; 998c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner for (unsigned i = MRegisterInfo::FirstVirtualRegister, 1007f690e625807b9320bf4ae437b8f35258acc99deChris Lattner e = MF.getSSARegMap()->getLastVirtReg(); i <= e; ++i) { 1017f690e625807b9320bf4ae437b8f35258acc99deChris Lattner if (Virt2PhysMap[i] != (unsigned)VirtRegMap::NO_PHYS_REG) 1027f690e625807b9320bf4ae437b8f35258acc99deChris Lattner OS << "[reg" << i << " -> " << MRI->getName(Virt2PhysMap[i]) << "]\n"; 1037f690e625807b9320bf4ae437b8f35258acc99deChris Lattner 1048c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 1058c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 1068c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner for (unsigned i = MRegisterInfo::FirstVirtualRegister, 1077f690e625807b9320bf4ae437b8f35258acc99deChris Lattner e = MF.getSSARegMap()->getLastVirtReg(); i <= e; ++i) 1087f690e625807b9320bf4ae437b8f35258acc99deChris Lattner if (Virt2StackSlotMap[i] != VirtRegMap::NO_STACK_SLOT) 1097f690e625807b9320bf4ae437b8f35258acc99deChris Lattner OS << "[reg" << i << " -> fi#" << Virt2StackSlotMap[i] << "]\n"; 1107f690e625807b9320bf4ae437b8f35258acc99deChris Lattner OS << '\n'; 1115f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos} 1125f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos 1138c4d88d3697835371ecf6823f4142af13603ad2dChris Lattnervoid VirtRegMap::dump() const { print(std::cerr); } 11434d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos 1150d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 1168c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner//===----------------------------------------------------------------------===// 1178c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner// Simple Spiller Implementation 1188c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner//===----------------------------------------------------------------------===// 119dd420e060accd1d773c731e77335cff65ca34013Alkis Evlogimenos 1208c4d88d3697835371ecf6823f4142af13603ad2dChris LattnerSpiller::~Spiller() {} 121dd420e060accd1d773c731e77335cff65ca34013Alkis Evlogimenos 1220d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenosnamespace { 1238c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner struct SimpleSpiller : public Spiller { 1248c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner bool runOnMachineFunction(MachineFunction& mf, const VirtRegMap &VRM); 1258c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner }; 1268c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner} 1270d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 1288c4d88d3697835371ecf6823f4142af13603ad2dChris Lattnerbool SimpleSpiller::runOnMachineFunction(MachineFunction& MF, 1298c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner const VirtRegMap& VRM) { 1308c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n"); 1318c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner DEBUG(std::cerr << "********** Function: " 1328c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner << MF.getFunction()->getName() << '\n'); 1338c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner const TargetMachine& TM = MF.getTarget(); 1347f690e625807b9320bf4ae437b8f35258acc99deChris Lattner const MRegisterInfo& MRI = *TM.getRegisterInfo(); 1358c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 1368c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner DenseMap<bool, VirtReg2IndexFunctor> Loaded; 1378c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 1388c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner for (MachineFunction::iterator mbbi = MF.begin(), E = MF.end(); 1398c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner mbbi != E; ++mbbi) { 1408c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n"); 1418c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner for (MachineBasicBlock::iterator mii = mbbi->begin(), 1428c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner mie = mbbi->end(); mii != mie; ++mii) { 1438c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner Loaded.grow(MF.getSSARegMap()->getLastVirtReg()); 1448c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner for (unsigned i = 0,e = mii->getNumOperands(); i != e; ++i){ 1458c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner MachineOperand& mop = mii->getOperand(i); 1468c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner if (mop.isRegister() && mop.getReg() && 1478c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner MRegisterInfo::isVirtualRegister(mop.getReg())) { 1488c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner unsigned virtReg = mop.getReg(); 1498c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner unsigned physReg = VRM.getPhys(virtReg); 1508c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner if (mop.isUse() && VRM.hasStackSlot(mop.getReg()) && 1518c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner !Loaded[virtReg]) { 1527f690e625807b9320bf4ae437b8f35258acc99deChris Lattner MRI.loadRegFromStackSlot(*mbbi, mii, physReg, 1538c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner VRM.getStackSlot(virtReg)); 1548c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner Loaded[virtReg] = true; 1558c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner DEBUG(std::cerr << '\t'; 1568c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner prior(mii)->print(std::cerr, &TM)); 1578c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner ++NumLoads; 1588c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 1598c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 1608c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner if (mop.isDef() && VRM.hasStackSlot(mop.getReg())) { 1617f690e625807b9320bf4ae437b8f35258acc99deChris Lattner MRI.storeRegToStackSlot(*mbbi, next(mii), physReg, 1628c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner VRM.getStackSlot(virtReg)); 1638c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner ++NumStores; 1648c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 1658c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner mii->SetMachineOperandReg(i, physReg); 1660d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos } 1678c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 1688c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner DEBUG(std::cerr << '\t'; mii->print(std::cerr, &TM)); 1698c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner Loaded.clear(); 1708c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 1718c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 1728c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner return true; 1738c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner} 1740d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 1758c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner//===----------------------------------------------------------------------===// 1768c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner// Local Spiller Implementation 1778c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner//===----------------------------------------------------------------------===// 1780d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 1798c4d88d3697835371ecf6823f4142af13603ad2dChris Lattnernamespace { 1808c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner class LocalSpiller : public Spiller { 1818c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner typedef std::vector<unsigned> Phys2VirtMap; 1828c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner typedef std::vector<bool> PhysFlag; 1838c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner typedef DenseMap<MachineInstr*, VirtReg2IndexFunctor> Virt2MI; 1848c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 1858c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner MachineFunction *MF; 1868c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner const TargetMachine *TM; 1878c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner const TargetInstrInfo *TII; 1888c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner const MRegisterInfo *MRI; 1898c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner const VirtRegMap *VRM; 1908c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner Phys2VirtMap p2vMap_; 1918c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner PhysFlag dirty_; 1928c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner Virt2MI lastDef_; 1938c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 1948c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner public: 1958c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner bool runOnMachineFunction(MachineFunction &MF, const VirtRegMap &VRM); 1968c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 1978c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner private: 1988c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner void vacateJustPhysReg(MachineBasicBlock& mbb, 1990d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos MachineBasicBlock::iterator mii, 2008c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner unsigned physReg); 2010d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 2028c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner void vacatePhysReg(MachineBasicBlock& mbb, 2030d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos MachineBasicBlock::iterator mii, 2040d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos unsigned physReg) { 2058c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner vacateJustPhysReg(mbb, mii, physReg); 2068c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner for (const unsigned* as = MRI->getAliasSet(physReg); *as; ++as) 2078c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner vacateJustPhysReg(mbb, mii, *as); 2088c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 2098c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 2108c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner void handleUse(MachineBasicBlock& mbb, 2118c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner MachineBasicBlock::iterator mii, 2128c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner unsigned virtReg, 2138c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner unsigned physReg) { 2148c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner // check if we are replacing a previous mapping 2158c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner if (p2vMap_[physReg] != virtReg) { 2168c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner vacatePhysReg(mbb, mii, physReg); 2178c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner p2vMap_[physReg] = virtReg; 2188c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner // load if necessary 2198c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner if (VRM->hasStackSlot(virtReg)) { 2208c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner MRI->loadRegFromStackSlot(mbb, mii, physReg, 2218c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner VRM->getStackSlot(virtReg)); 2228c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner ++NumLoads; 2238c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner DEBUG(std::cerr << "added: "; 2248c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner prior(mii)->print(std::cerr, TM)); 2258c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner lastDef_[virtReg] = mii; 2260d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos } 2278c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 2288c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 2290d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 2308c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner void handleDef(MachineBasicBlock& mbb, 2318c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner MachineBasicBlock::iterator mii, 2328c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner unsigned virtReg, 2338c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner unsigned physReg) { 2348c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner // check if we are replacing a previous mapping 2358c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner if (p2vMap_[physReg] != virtReg) 2368c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner vacatePhysReg(mbb, mii, physReg); 2378c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 2388c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner p2vMap_[physReg] = virtReg; 2398c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner dirty_[physReg] = true; 2408c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner lastDef_[virtReg] = mii; 2418c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 2428c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 2438c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner void eliminateVirtRegsInMbb(MachineBasicBlock& mbb); 2448c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner }; 2458c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner} 2468c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 2478c4d88d3697835371ecf6823f4142af13603ad2dChris Lattnerbool LocalSpiller::runOnMachineFunction(MachineFunction &mf, 2488c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner const VirtRegMap &vrm) { 2498c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner MF = &mf; 2508c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner TM = &MF->getTarget(); 2518c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner TII = TM->getInstrInfo(); 2528c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner MRI = TM->getRegisterInfo(); 2538c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner VRM = &vrm; 2548c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner p2vMap_.assign(MRI->getNumRegs(), 0); 2558c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner dirty_.assign(MRI->getNumRegs(), false); 2568c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 2578c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n"); 2588c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner DEBUG(std::cerr << "********** Function: " 2598c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner << MF->getFunction()->getName() << '\n'); 2608c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 2618c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner for (MachineFunction::iterator mbbi = MF->begin(), 2628c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner mbbe = MF->end(); mbbi != mbbe; ++mbbi) { 2638c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner lastDef_.grow(MF->getSSARegMap()->getLastVirtReg()); 2648c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n"); 2658c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner eliminateVirtRegsInMbb(*mbbi); 2668c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner // clear map, dirty flag and last ref 2678c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner p2vMap_.assign(p2vMap_.size(), 0); 2688c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner dirty_.assign(dirty_.size(), false); 2698c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner lastDef_.clear(); 2708c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 2718c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner return true; 2728c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner} 2730d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 2748c4d88d3697835371ecf6823f4142af13603ad2dChris Lattnervoid LocalSpiller::vacateJustPhysReg(MachineBasicBlock& mbb, 2758c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner MachineBasicBlock::iterator mii, 2768c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner unsigned physReg) { 2778c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner unsigned virtReg = p2vMap_[physReg]; 2788c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner if (dirty_[physReg] && VRM->hasStackSlot(virtReg)) { 2798c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner assert(lastDef_[virtReg] && "virtual register is mapped " 2808c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner "to a register and but was not defined!"); 2818c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner MachineBasicBlock::iterator lastDef = lastDef_[virtReg]; 2828c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner MachineBasicBlock::iterator nextLastRef = next(lastDef); 2838c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner MRI->storeRegToStackSlot(*lastDef->getParent(), 2848c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner nextLastRef, 2858c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner physReg, 2868c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner VRM->getStackSlot(virtReg)); 2878c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner ++NumStores; 2888c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner DEBUG(std::cerr << "added: "; 2898c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner prior(nextLastRef)->print(std::cerr, TM); 2908c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner std::cerr << "after: "; 2918c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner lastDef->print(std::cerr, TM)); 2928c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner lastDef_[virtReg] = 0; 2938c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 2948c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner p2vMap_[physReg] = 0; 2958c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner dirty_[physReg] = false; 2968c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner} 2978c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 2988c4d88d3697835371ecf6823f4142af13603ad2dChris Lattnervoid LocalSpiller::eliminateVirtRegsInMbb(MachineBasicBlock &MBB) { 2998c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner for (MachineBasicBlock::iterator MI = MBB.begin(), E = MBB.end(); 3008c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner MI != E; ++MI) { 3018c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 3028c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner // if we have references to memory operands make sure 3038c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner // we clear all physical registers that may contain 3048c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner // the value of the spilled virtual register 3057f690e625807b9320bf4ae437b8f35258acc99deChris Lattner VirtRegMap::MI2VirtMapTy::const_iterator i, e; 3068c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner for (tie(i, e) = VRM->getFoldedVirts(MI); i != e; ++i) { 3078c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner if (VRM->hasPhys(i->second)) 3088c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner vacateJustPhysReg(MBB, MI, VRM->getPhys(i->second)); 3098c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 3108c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 3118c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner // rewrite all used operands 3128c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 3138c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner MachineOperand& op = MI->getOperand(i); 3148c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner if (op.isRegister() && op.getReg() && op.isUse() && 3158c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner MRegisterInfo::isVirtualRegister(op.getReg())) { 3168c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner unsigned virtReg = op.getReg(); 3178c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner unsigned physReg = VRM->getPhys(virtReg); 3188c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner handleUse(MBB, MI, virtReg, physReg); 3198c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner MI->SetMachineOperandReg(i, physReg); 3208c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner // mark as dirty if this is def&use 3218c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner if (op.isDef()) { 3228c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner dirty_[physReg] = true; 3238c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner lastDef_[virtReg] = MI; 3240d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos } 3258c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 3268c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 3270d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 3288c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner // spill implicit physical register defs 3298c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner const TargetInstrDescriptor& tid = TII->get(MI->getOpcode()); 3308c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner for (const unsigned* id = tid.ImplicitDefs; *id; ++id) 3318c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner vacatePhysReg(MBB, MI, *id); 3328c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 3338c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner // spill explicit physical register defs 3348c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 3358c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner MachineOperand& op = MI->getOperand(i); 3368c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner if (op.isRegister() && op.getReg() && !op.isUse() && 3378c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner MRegisterInfo::isPhysicalRegister(op.getReg())) 3388c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner vacatePhysReg(MBB, MI, op.getReg()); 3398c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 3400d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 3418c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner // rewrite def operands (def&use was handled with the 3428c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner // uses so don't check for those here) 3438c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 3448c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner MachineOperand& op = MI->getOperand(i); 3458c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner if (op.isRegister() && op.getReg() && !op.isUse()) 3468c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner if (MRegisterInfo::isPhysicalRegister(op.getReg())) 3478c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner vacatePhysReg(MBB, MI, op.getReg()); 3488c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner else { 3498c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner unsigned physReg = VRM->getPhys(op.getReg()); 3508c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner handleDef(MBB, MI, op.getReg(), physReg); 3518c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner MI->SetMachineOperandReg(i, physReg); 3520d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos } 3538c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 3548c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 3558c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner DEBUG(std::cerr << '\t'; MI->print(std::cerr, TM)); 3568c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 3578c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 3588c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner for (unsigned i = 1, e = p2vMap_.size(); i != e; ++i) 3598c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner vacateJustPhysReg(MBB, MBB.getFirstTerminator(), i); 3600d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos} 3610d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 3628c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 3638c4d88d3697835371ecf6823f4142af13603ad2dChris Lattnerllvm::Spiller* llvm::createSpiller() { 3648c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner switch (SpillerOpt) { 3658c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner default: assert(0 && "Unreachable!"); 3668c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner case local: 3678c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner return new LocalSpiller(); 3688c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner case simple: 3698c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner return new SimpleSpiller(); 3708c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 3710d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos} 372