VirtRegMap.cpp revision 6425f8be7263e625c2d7484eb2fb8f6643824f49
134d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos//===-- llvm/CodeGen/VirtRegMap.cpp - Virtual Register Map ----------------===// 234d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// 334d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// The LLVM Compiler Infrastructure 434d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// 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" 2484bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner#include "llvm/CodeGen/MachineRegisterInfo.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" 29a4f0b3a084d120cfc5b5bb06f64b222f5cb72740Chris Lattner#include "llvm/Support/Compiler.h" 30957840b3e14938fc86c306fda99ac039d1777a4cEvan Cheng#include "llvm/ADT/BitVector.h" 31551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 32551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/STLExtras.h" 3308a4d5a343e886816b31a78d9b7e70240d9c67beChris Lattner#include "llvm/ADT/SmallSet.h" 3427f291600b04c382c390b16fdacd52b910b9164dChris Lattner#include <algorithm> 3534d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenosusing namespace llvm; 3634d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos 37cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(NumSpills, "Number of register spills"); 382638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan ChengSTATISTIC(NumReMats, "Number of re-materialization"); 39b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan ChengSTATISTIC(NumDRM , "Number of re-materializable defs elided"); 40cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(NumStores, "Number of stores added"); 41cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(NumLoads , "Number of loads added"); 42cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(NumReused, "Number of values reused"); 43cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(NumDSE , "Number of dead stores elided"); 44cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(NumDCE , "Number of copies elided"); 458c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 46cd3245ac45c595da96bb768a55cddc356dff55feChris Lattnernamespace { 478c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner enum SpillerName { simple, local }; 488c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 49ed41f1bb1981a98eea63f00c5988cf62bbdd7c59Andrew Lenharth static cl::opt<SpillerName> 508c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner SpillerOpt("spiller", 517fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner cl::desc("Spiller to use: (default: local)"), 528c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner cl::Prefix, 538c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner cl::values(clEnumVal(simple, " simple spiller"), 548c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner clEnumVal(local, " local spiller"), 558c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner clEnumValEnd), 567fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner cl::init(local)); 578c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner} 588c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 598c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner//===----------------------------------------------------------------------===// 608c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner// VirtRegMap implementation 618c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner//===----------------------------------------------------------------------===// 628c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 632926869b4a083fc951484de03a9867eabf81e880Chris LattnerVirtRegMap::VirtRegMap(MachineFunction &mf) 642926869b4a083fc951484de03a9867eabf81e880Chris Lattner : TII(*mf.getTarget().getInstrInfo()), MF(mf), 652638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng Virt2PhysMap(NO_PHYS_REG), Virt2StackSlotMap(NO_STACK_SLOT), 6681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Virt2ReMatIdMap(NO_STACK_SLOT), Virt2SplitMap(0), 67d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng Virt2SplitKillMap(0), ReMatMap(NULL), ReMatId(MAX_STACK_SLOT+1) { 682926869b4a083fc951484de03a9867eabf81e880Chris Lattner grow(); 692926869b4a083fc951484de03a9867eabf81e880Chris Lattner} 702926869b4a083fc951484de03a9867eabf81e880Chris Lattner 718c4d88d3697835371ecf6823f4142af13603ad2dChris Lattnervoid VirtRegMap::grow() { 7284bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner unsigned LastVirtReg = MF.getRegInfo().getLastVirtReg(); 73549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng Virt2PhysMap.grow(LastVirtReg); 74549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng Virt2StackSlotMap.grow(LastVirtReg); 75549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng Virt2ReMatIdMap.grow(LastVirtReg); 7681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Virt2SplitMap.grow(LastVirtReg); 77adf85906906ebf85c57c333e8209f37ef11a6c99Evan Cheng Virt2SplitKillMap.grow(LastVirtReg); 78549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng ReMatMap.grow(LastVirtReg); 7934d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos} 8034d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos 818c4d88d3697835371ecf6823f4142af13603ad2dChris Lattnerint VirtRegMap::assignVirt2StackSlot(unsigned virtReg) { 828c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner assert(MRegisterInfo::isVirtualRegister(virtReg)); 837f690e625807b9320bf4ae437b8f35258acc99deChris Lattner assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT && 848c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner "attempt to assign stack slot to already spilled register"); 8584bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner const TargetRegisterClass* RC = MF.getRegInfo().getRegClass(virtReg); 867f690e625807b9320bf4ae437b8f35258acc99deChris Lattner int frameIndex = MF.getFrameInfo()->CreateStackObject(RC->getSize(), 877f690e625807b9320bf4ae437b8f35258acc99deChris Lattner RC->getAlignment()); 887f690e625807b9320bf4ae437b8f35258acc99deChris Lattner Virt2StackSlotMap[virtReg] = frameIndex; 898c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner ++NumSpills; 908c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner return frameIndex; 9134d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos} 9234d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos 938c4d88d3697835371ecf6823f4142af13603ad2dChris Lattnervoid VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int frameIndex) { 948c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner assert(MRegisterInfo::isVirtualRegister(virtReg)); 957f690e625807b9320bf4ae437b8f35258acc99deChris Lattner assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT && 968c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner "attempt to assign stack slot to already spilled register"); 979193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng assert((frameIndex >= 0 || 989193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng (frameIndex >= MF.getFrameInfo()->getObjectIndexBegin())) && 999193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng "illegal fixed frame index"); 1007f690e625807b9320bf4ae437b8f35258acc99deChris Lattner Virt2StackSlotMap[virtReg] = frameIndex; 10138af59a43c4176d8f34bd26faeb18b23080a1d9bAlkis Evlogimenos} 10238af59a43c4176d8f34bd26faeb18b23080a1d9bAlkis Evlogimenos 1032638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Chengint VirtRegMap::assignVirtReMatId(unsigned virtReg) { 1042638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng assert(MRegisterInfo::isVirtualRegister(virtReg)); 105549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng assert(Virt2ReMatIdMap[virtReg] == NO_STACK_SLOT && 1062638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng "attempt to assign re-mat id to already spilled register"); 107549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng Virt2ReMatIdMap[virtReg] = ReMatId; 1082638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng return ReMatId++; 1092638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng} 1102638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng 111549f27d3070195d6647b796841a5291b4549e8e0Evan Chengvoid VirtRegMap::assignVirtReMatId(unsigned virtReg, int id) { 112549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng assert(MRegisterInfo::isVirtualRegister(virtReg)); 113549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng assert(Virt2ReMatIdMap[virtReg] == NO_STACK_SLOT && 114549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng "attempt to assign re-mat id to already spilled register"); 115549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng Virt2ReMatIdMap[virtReg] = id; 116549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng} 117549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng 118bec6a9ea1281a0b3b37aece91ab0df21e086af61Chris Lattnervoid VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *OldMI, 119aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MachineInstr *NewMI, ModRef MRInfo) { 120bec6a9ea1281a0b3b37aece91ab0df21e086af61Chris Lattner // Move previous memory references folded to new instruction. 121bec6a9ea1281a0b3b37aece91ab0df21e086af61Chris Lattner MI2VirtMapTy::iterator IP = MI2VirtMap.lower_bound(NewMI); 122edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman for (MI2VirtMapTy::iterator I = MI2VirtMap.lower_bound(OldMI), 123bec6a9ea1281a0b3b37aece91ab0df21e086af61Chris Lattner E = MI2VirtMap.end(); I != E && I->first == OldMI; ) { 124bec6a9ea1281a0b3b37aece91ab0df21e086af61Chris Lattner MI2VirtMap.insert(IP, std::make_pair(NewMI, I->second)); 125dbea9731b12e62f70d9da40cf273cdd9105f987cChris Lattner MI2VirtMap.erase(I++); 1268c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 127dbea9731b12e62f70d9da40cf273cdd9105f987cChris Lattner 1288c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner // add new memory reference 129bec6a9ea1281a0b3b37aece91ab0df21e086af61Chris Lattner MI2VirtMap.insert(IP, std::make_pair(NewMI, std::make_pair(VirtReg, MRInfo))); 1308c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner} 1315f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos 1327f56625447b94178118f2fec732b10f9e4aa7fbfEvan Chengvoid VirtRegMap::virtFolded(unsigned VirtReg, MachineInstr *MI, ModRef MRInfo) { 1337f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng MI2VirtMapTy::iterator IP = MI2VirtMap.lower_bound(MI); 1347f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng MI2VirtMap.insert(IP, std::make_pair(MI, std::make_pair(VirtReg, MRInfo))); 1357f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng} 1367f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng 1377f690e625807b9320bf4ae437b8f35258acc99deChris Lattnervoid VirtRegMap::print(std::ostream &OS) const { 1387f690e625807b9320bf4ae437b8f35258acc99deChris Lattner const MRegisterInfo* MRI = MF.getTarget().getRegisterInfo(); 1398c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 1407f690e625807b9320bf4ae437b8f35258acc99deChris Lattner OS << "********** REGISTER MAP **********\n"; 1418c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner for (unsigned i = MRegisterInfo::FirstVirtualRegister, 14284bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner e = MF.getRegInfo().getLastVirtReg(); i <= e; ++i) { 1437f690e625807b9320bf4ae437b8f35258acc99deChris Lattner if (Virt2PhysMap[i] != (unsigned)VirtRegMap::NO_PHYS_REG) 1447f690e625807b9320bf4ae437b8f35258acc99deChris Lattner OS << "[reg" << i << " -> " << MRI->getName(Virt2PhysMap[i]) << "]\n"; 145edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 1468c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 1478c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 1488c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner for (unsigned i = MRegisterInfo::FirstVirtualRegister, 14984bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner e = MF.getRegInfo().getLastVirtReg(); i <= e; ++i) 1507f690e625807b9320bf4ae437b8f35258acc99deChris Lattner if (Virt2StackSlotMap[i] != VirtRegMap::NO_STACK_SLOT) 1517f690e625807b9320bf4ae437b8f35258acc99deChris Lattner OS << "[reg" << i << " -> fi#" << Virt2StackSlotMap[i] << "]\n"; 1527f690e625807b9320bf4ae437b8f35258acc99deChris Lattner OS << '\n'; 1535f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos} 1545f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos 155b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendlingvoid VirtRegMap::dump() const { 1565c7e326585f3a543388ba871c3425f7664cd9143Bill Wendling print(DOUT); 157b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling} 15834d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos 1590d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 1608c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner//===----------------------------------------------------------------------===// 1618c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner// Simple Spiller Implementation 1628c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner//===----------------------------------------------------------------------===// 163dd420e060accd1d773c731e77335cff65ca34013Alkis Evlogimenos 1648c4d88d3697835371ecf6823f4142af13603ad2dChris LattnerSpiller::~Spiller() {} 165dd420e060accd1d773c731e77335cff65ca34013Alkis Evlogimenos 1660d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenosnamespace { 167f8c68f694c25b1ae8c0e5adb2a19432cb405d232Chris Lattner struct VISIBILITY_HIDDEN SimpleSpiller : public Spiller { 16835f2705e3de4600c3621b883eed9b22e4607ddf4Chris Lattner bool runOnMachineFunction(MachineFunction& mf, VirtRegMap &VRM); 1698c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner }; 1708c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner} 1710d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 17235f2705e3de4600c3621b883eed9b22e4607ddf4Chris Lattnerbool SimpleSpiller::runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM) { 173b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling DOUT << "********** REWRITE MACHINE CODE **********\n"; 174b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling DOUT << "********** Function: " << MF.getFunction()->getName() << '\n'; 175b0f31bf19b9cd0107900728123d4848eae462e6cChris Lattner const TargetMachine &TM = MF.getTarget(); 176f6372aa1cc568df19da7c5023e83c75aa9404a07Owen Anderson const TargetInstrInfo &TII = *TM.getInstrInfo(); 177f6372aa1cc568df19da7c5023e83c75aa9404a07Owen Anderson 1788c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 1794ea1b828ebc5d2e8711acf13c2a3fdd7c14fe339Chris Lattner // LoadedRegs - Keep track of which vregs are loaded, so that we only load 1804ea1b828ebc5d2e8711acf13c2a3fdd7c14fe339Chris Lattner // each vreg once (in the case where a spilled vreg is used by multiple 1814ea1b828ebc5d2e8711acf13c2a3fdd7c14fe339Chris Lattner // operands). This is always smaller than the number of operands to the 1824ea1b828ebc5d2e8711acf13c2a3fdd7c14fe339Chris Lattner // current machine instr, so it should be small. 1834ea1b828ebc5d2e8711acf13c2a3fdd7c14fe339Chris Lattner std::vector<unsigned> LoadedRegs; 1848c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 1850fc27ccdd374799c8d65b61e89db53ba1ea47358Chris Lattner for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end(); 1860fc27ccdd374799c8d65b61e89db53ba1ea47358Chris Lattner MBBI != E; ++MBBI) { 187b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling DOUT << MBBI->getBasicBlock()->getName() << ":\n"; 1880fc27ccdd374799c8d65b61e89db53ba1ea47358Chris Lattner MachineBasicBlock &MBB = *MBBI; 1890fc27ccdd374799c8d65b61e89db53ba1ea47358Chris Lattner for (MachineBasicBlock::iterator MII = MBB.begin(), 1900fc27ccdd374799c8d65b61e89db53ba1ea47358Chris Lattner E = MBB.end(); MII != E; ++MII) { 1910fc27ccdd374799c8d65b61e89db53ba1ea47358Chris Lattner MachineInstr &MI = *MII; 1920fc27ccdd374799c8d65b61e89db53ba1ea47358Chris Lattner for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 1937fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner MachineOperand &MO = MI.getOperand(i); 194886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner if (MO.isRegister() && MO.getReg()) 195886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner if (MRegisterInfo::isVirtualRegister(MO.getReg())) { 196886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner unsigned VirtReg = MO.getReg(); 197886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner unsigned PhysReg = VRM.getPhys(VirtReg); 198549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng if (!VRM.isAssignedReg(VirtReg)) { 199886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner int StackSlot = VRM.getStackSlot(VirtReg); 200bf9716b9c48d3b0370c715cd79540945f73dc296Chris Lattner const TargetRegisterClass* RC = 20184bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner MF.getRegInfo().getRegClass(VirtReg); 202edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 203886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner if (MO.isUse() && 204886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner std::find(LoadedRegs.begin(), LoadedRegs.end(), VirtReg) 205886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner == LoadedRegs.end()) { 206f6372aa1cc568df19da7c5023e83c75aa9404a07Owen Anderson TII.loadRegFromStackSlot(MBB, &MI, PhysReg, StackSlot, RC); 207886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner LoadedRegs.push_back(VirtReg); 208886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner ++NumLoads; 209b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling DOUT << '\t' << *prior(MII); 210886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner } 211edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 212886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner if (MO.isDef()) { 213f6372aa1cc568df19da7c5023e83c75aa9404a07Owen Anderson TII.storeRegToStackSlot(MBB, next(MII), PhysReg, true, 214d64b5c82b97ad1b74eb9fd2f23257a7899b0c307Evan Cheng StackSlot, RC); 215886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner ++NumStores; 216886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner } 2170fc27ccdd374799c8d65b61e89db53ba1ea47358Chris Lattner } 21884bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner MF.getRegInfo().setPhysRegUsed(PhysReg); 219e53f4a055f74bded20d6129b4724ddd17fd199f6Chris Lattner MI.getOperand(i).setReg(PhysReg); 220886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner } else { 22184bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner MF.getRegInfo().setPhysRegUsed(MO.getReg()); 2228c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 2238c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 224886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner 225b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling DOUT << '\t' << MI; 2264ea1b828ebc5d2e8711acf13c2a3fdd7c14fe339Chris Lattner LoadedRegs.clear(); 2278c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 2288c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 2298c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner return true; 2308c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner} 2310d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 2328c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner//===----------------------------------------------------------------------===// 2338c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner// Local Spiller Implementation 2348c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner//===----------------------------------------------------------------------===// 2350d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 2368c4d88d3697835371ecf6823f4142af13603ad2dChris Lattnernamespace { 23766f716354527c5ab4687a89a1605915e5128a106Evan Cheng class AvailableSpills; 23866f716354527c5ab4687a89a1605915e5128a106Evan Cheng 2397fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner /// LocalSpiller - This spiller does a simple pass over the machine basic 2407fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner /// block to attempt to keep spills in registers as much as possible for 2417fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner /// blocks that have low register pressure (the vreg may be spilled due to 2427fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner /// register pressure in other blocks). 243f8c68f694c25b1ae8c0e5adb2a19432cb405d232Chris Lattner class VISIBILITY_HIDDEN LocalSpiller : public Spiller { 24484bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner MachineRegisterInfo *RegInfo; 2458c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner const MRegisterInfo *MRI; 2467fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner const TargetInstrInfo *TII; 2478c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner public: 24835f2705e3de4600c3621b883eed9b22e4607ddf4Chris Lattner bool runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM) { 24984bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner RegInfo = &MF.getRegInfo(); 2507fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner MRI = MF.getTarget().getRegisterInfo(); 2517fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner TII = MF.getTarget().getInstrInfo(); 252b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling DOUT << "\n**** Local spiller rewriting function '" 253b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling << MF.getFunction()->getName() << "':\n"; 25484bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner DOUT << "**** Machine Instrs (NOTE! Does not include spills and reloads!)" 25584bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner " ****\n"; 25604fa32f9aa19bae12e7fd5b5564cebc345de3c58David Greene DEBUG(MF.dump()); 2577fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner 2587fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner for (MachineFunction::iterator MBB = MF.begin(), E = MF.end(); 2597fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner MBB != E; ++MBB) 260549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng RewriteMBB(*MBB, VRM); 26104fa32f9aa19bae12e7fd5b5564cebc345de3c58David Greene 26204fa32f9aa19bae12e7fd5b5564cebc345de3c58David Greene DOUT << "**** Post Machine Instrs ****\n"; 26304fa32f9aa19bae12e7fd5b5564cebc345de3c58David Greene DEBUG(MF.dump()); 26404fa32f9aa19bae12e7fd5b5564cebc345de3c58David Greene 2657fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner return true; 2668c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 2677fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner private: 26866f716354527c5ab4687a89a1605915e5128a106Evan Cheng bool PrepForUnfoldOpti(MachineBasicBlock &MBB, 26966f716354527c5ab4687a89a1605915e5128a106Evan Cheng MachineBasicBlock::iterator &MII, 27066f716354527c5ab4687a89a1605915e5128a106Evan Cheng std::vector<MachineInstr*> &MaybeDeadStores, 27166f716354527c5ab4687a89a1605915e5128a106Evan Cheng AvailableSpills &Spills, BitVector &RegKills, 27266f716354527c5ab4687a89a1605915e5128a106Evan Cheng std::vector<MachineOperand*> &KillOps, 27366f716354527c5ab4687a89a1605915e5128a106Evan Cheng VirtRegMap &VRM); 27481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng void SpillRegToStackSlot(MachineBasicBlock &MBB, 27581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineBasicBlock::iterator &MII, 27681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng int Idx, unsigned PhysReg, int StackSlot, 27781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng const TargetRegisterClass *RC, 27835a3e4abb96a6947ec66254b72e788bacc3aadd6Evan Cheng bool isAvailable, MachineInstr *&LastStore, 27981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng AvailableSpills &Spills, 28081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng SmallSet<MachineInstr*, 4> &ReMatDefs, 28181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector &RegKills, 28281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng std::vector<MachineOperand*> &KillOps, 283e4b39007c9d3056334264eba9e2e6025e241d2c5Evan Cheng VirtRegMap &VRM); 284549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng void RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM); 2858c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner }; 2868c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner} 2878c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 28866cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner/// AvailableSpills - As the local spiller is scanning and rewriting an MBB from 289549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng/// top down, keep track of which spills slots or remat are available in each 290549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng/// register. 291593c95878b089388f9c82b8c7b1f4731af86c792Chris Lattner/// 292593c95878b089388f9c82b8c7b1f4731af86c792Chris Lattner/// Note that not all physregs are created equal here. In particular, some 293593c95878b089388f9c82b8c7b1f4731af86c792Chris Lattner/// physregs are reloads that we are allowed to clobber or ignore at any time. 294593c95878b089388f9c82b8c7b1f4731af86c792Chris Lattner/// Other physregs are values that the register allocated program is using that 295593c95878b089388f9c82b8c7b1f4731af86c792Chris Lattner/// we cannot CHANGE, but we can read if we like. We keep track of this on a 296549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng/// per-stack-slot / remat id basis as the low bit in the value of the 297549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng/// SpillSlotsAvailable entries. The predicate 'canClobberPhysReg()' checks 298549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng/// this bit and addAvailable sets it if. 299f8c68f694c25b1ae8c0e5adb2a19432cb405d232Chris Lattnernamespace { 300f8c68f694c25b1ae8c0e5adb2a19432cb405d232Chris Lattnerclass VISIBILITY_HIDDEN AvailableSpills { 30166cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner const MRegisterInfo *MRI; 30266cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner const TargetInstrInfo *TII; 30366cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner 304549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // SpillSlotsOrReMatsAvailable - This map keeps track of all of the spilled 305549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // or remat'ed virtual register values that are still available, due to being 306549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // loaded or stored to, but not invalidated yet. 307549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng std::map<int, unsigned> SpillSlotsOrReMatsAvailable; 30866cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner 309549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // PhysRegsAvailable - This is the inverse of SpillSlotsOrReMatsAvailable, 310549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // indicating which stack slot values are currently held by a physreg. This 311549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // is used to invalidate entries in SpillSlotsOrReMatsAvailable when a 312549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // physreg is modified. 31366cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner std::multimap<unsigned, int> PhysRegsAvailable; 31466cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner 3157a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng void disallowClobberPhysRegOnly(unsigned PhysReg); 3167a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng 31766cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner void ClobberPhysRegOnly(unsigned PhysReg); 31866cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattnerpublic: 31966cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner AvailableSpills(const MRegisterInfo *mri, const TargetInstrInfo *tii) 32066cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner : MRI(mri), TII(tii) { 32166cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner } 32266cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner 32391e2390818080ae2b059e3ff850a9455858e4f7bEvan Cheng const MRegisterInfo *getRegInfo() const { return MRI; } 32491e2390818080ae2b059e3ff850a9455858e4f7bEvan Cheng 325549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng /// getSpillSlotOrReMatPhysReg - If the specified stack slot or remat is 326549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng /// available in a physical register, return that PhysReg, otherwise 327549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng /// return 0. 328549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng unsigned getSpillSlotOrReMatPhysReg(int Slot) const { 329549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng std::map<int, unsigned>::const_iterator I = 330549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng SpillSlotsOrReMatsAvailable.find(Slot); 331549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng if (I != SpillSlotsOrReMatsAvailable.end()) { 332b9591c667d956d0607f7388665649fb0852a988cEvan Cheng return I->second >> 1; // Remove the CanClobber bit. 33391e2390818080ae2b059e3ff850a9455858e4f7bEvan Cheng } 33466cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner return 0; 33566cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner } 336de4e942faa12a52242915e3334c25f19687f36e2Evan Cheng 337549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng /// addAvailable - Mark that the specified stack slot / remat is available in 338549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng /// the specified physreg. If CanClobber is true, the physreg can be modified 339549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng /// at any time without changing the semantics of the program. 340549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng void addAvailable(int SlotOrReMat, MachineInstr *MI, unsigned Reg, 34191e2390818080ae2b059e3ff850a9455858e4f7bEvan Cheng bool CanClobber = true) { 3428666249ad6eca27d267f251495545bca132a9a5cChris Lattner // If this stack slot is thought to be available in some other physreg, 3438666249ad6eca27d267f251495545bca132a9a5cChris Lattner // remove its record. 344549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng ModifyStackSlotOrReMat(SlotOrReMat); 3458666249ad6eca27d267f251495545bca132a9a5cChris Lattner 346549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng PhysRegsAvailable.insert(std::make_pair(Reg, SlotOrReMat)); 34790a43c3ae385d98d19f9c858b51920552fb9ceaaEvan Cheng SpillSlotsOrReMatsAvailable[SlotOrReMat]= (Reg << 1) | (unsigned)CanClobber; 34866cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner 349549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng if (SlotOrReMat > VirtRegMap::MAX_STACK_SLOT) 350549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng DOUT << "Remembering RM#" << SlotOrReMat-VirtRegMap::MAX_STACK_SLOT-1; 3512638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng else 352549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng DOUT << "Remembering SS#" << SlotOrReMat; 3532638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng DOUT << " in physreg " << MRI->getName(Reg) << "\n"; 35466cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner } 3557a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng 356593c95878b089388f9c82b8c7b1f4731af86c792Chris Lattner /// canClobberPhysReg - Return true if the spiller is allowed to change the 357593c95878b089388f9c82b8c7b1f4731af86c792Chris Lattner /// value of the specified stackslot register if it desires. The specified 358593c95878b089388f9c82b8c7b1f4731af86c792Chris Lattner /// stack slot must be available in a physreg for this query to make sense. 359549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng bool canClobberPhysReg(int SlotOrReMat) const { 36090a43c3ae385d98d19f9c858b51920552fb9ceaaEvan Cheng assert(SpillSlotsOrReMatsAvailable.count(SlotOrReMat) && 36190a43c3ae385d98d19f9c858b51920552fb9ceaaEvan Cheng "Value not available!"); 362549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng return SpillSlotsOrReMatsAvailable.find(SlotOrReMat)->second & 1; 363593c95878b089388f9c82b8c7b1f4731af86c792Chris Lattner } 36435a3e4abb96a6947ec66254b72e788bacc3aadd6Evan Cheng 3657a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng /// disallowClobberPhysReg - Unset the CanClobber bit of the specified 3667a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng /// stackslot register. The register is still available but is no longer 3677a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng /// allowed to be modifed. 3687a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng void disallowClobberPhysReg(unsigned PhysReg); 3697a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng 37066cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner /// ClobberPhysReg - This is called when the specified physreg changes 37166f716354527c5ab4687a89a1605915e5128a106Evan Cheng /// value. We use this to invalidate any info about stuff that lives in 37266cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner /// it and any of its aliases. 37366cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner void ClobberPhysReg(unsigned PhysReg); 37466cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner 37590a43c3ae385d98d19f9c858b51920552fb9ceaaEvan Cheng /// ModifyStackSlotOrReMat - This method is called when the value in a stack 37690a43c3ae385d98d19f9c858b51920552fb9ceaaEvan Cheng /// slot changes. This removes information about which register the previous 37790a43c3ae385d98d19f9c858b51920552fb9ceaaEvan Cheng /// value for this slot lives in (as the previous value is dead now). 378549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng void ModifyStackSlotOrReMat(int SlotOrReMat); 37966cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner}; 380f8c68f694c25b1ae8c0e5adb2a19432cb405d232Chris Lattner} 38166cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner 3827a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng/// disallowClobberPhysRegOnly - Unset the CanClobber bit of the specified 3837a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng/// stackslot register. The register is still available but is no longer 3847a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng/// allowed to be modifed. 3857a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Chengvoid AvailableSpills::disallowClobberPhysRegOnly(unsigned PhysReg) { 3867a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng std::multimap<unsigned, int>::iterator I = 3877a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng PhysRegsAvailable.lower_bound(PhysReg); 3887a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng while (I != PhysRegsAvailable.end() && I->first == PhysReg) { 389549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng int SlotOrReMat = I->second; 3907a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng I++; 391549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng assert((SpillSlotsOrReMatsAvailable[SlotOrReMat] >> 1) == PhysReg && 3927a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng "Bidirectional map mismatch!"); 393549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng SpillSlotsOrReMatsAvailable[SlotOrReMat] &= ~1; 3947a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng DOUT << "PhysReg " << MRI->getName(PhysReg) 3957a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng << " copied, it is available for use but can no longer be modified\n"; 3967a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng } 3977a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng} 3987a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng 3997a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng/// disallowClobberPhysReg - Unset the CanClobber bit of the specified 4007a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng/// stackslot register and its aliases. The register and its aliases may 4017a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng/// still available but is no longer allowed to be modifed. 4027a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Chengvoid AvailableSpills::disallowClobberPhysReg(unsigned PhysReg) { 4037a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng for (const unsigned *AS = MRI->getAliasSet(PhysReg); *AS; ++AS) 4047a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng disallowClobberPhysRegOnly(*AS); 4057a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng disallowClobberPhysRegOnly(PhysReg); 4067a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng} 4077a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng 40866cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner/// ClobberPhysRegOnly - This is called when the specified physreg changes 40966cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner/// value. We use this to invalidate any info about stuff we thing lives in it. 41066cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattnervoid AvailableSpills::ClobberPhysRegOnly(unsigned PhysReg) { 41166cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner std::multimap<unsigned, int>::iterator I = 41266cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner PhysRegsAvailable.lower_bound(PhysReg); 41307cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner while (I != PhysRegsAvailable.end() && I->first == PhysReg) { 414549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng int SlotOrReMat = I->second; 41507cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner PhysRegsAvailable.erase(I++); 416549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng assert((SpillSlotsOrReMatsAvailable[SlotOrReMat] >> 1) == PhysReg && 41766cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner "Bidirectional map mismatch!"); 418549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng SpillSlotsOrReMatsAvailable.erase(SlotOrReMat); 419b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling DOUT << "PhysReg " << MRI->getName(PhysReg) 4202638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng << " clobbered, invalidating "; 421549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng if (SlotOrReMat > VirtRegMap::MAX_STACK_SLOT) 422549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng DOUT << "RM#" << SlotOrReMat-VirtRegMap::MAX_STACK_SLOT-1 << "\n"; 4232638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng else 424549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng DOUT << "SS#" << SlotOrReMat << "\n"; 4258c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 4268c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner} 4270d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 42866cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner/// ClobberPhysReg - This is called when the specified physreg changes 42966cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner/// value. We use this to invalidate any info about stuff we thing lives in 43066cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner/// it and any of its aliases. 43166cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattnervoid AvailableSpills::ClobberPhysReg(unsigned PhysReg) { 4327fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner for (const unsigned *AS = MRI->getAliasSet(PhysReg); *AS; ++AS) 43366cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner ClobberPhysRegOnly(*AS); 43466cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner ClobberPhysRegOnly(PhysReg); 43507cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner} 43607cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner 43790a43c3ae385d98d19f9c858b51920552fb9ceaaEvan Cheng/// ModifyStackSlotOrReMat - This method is called when the value in a stack 43890a43c3ae385d98d19f9c858b51920552fb9ceaaEvan Cheng/// slot changes. This removes information about which register the previous 43990a43c3ae385d98d19f9c858b51920552fb9ceaaEvan Cheng/// value for this slot lives in (as the previous value is dead now). 440549f27d3070195d6647b796841a5291b4549e8e0Evan Chengvoid AvailableSpills::ModifyStackSlotOrReMat(int SlotOrReMat) { 44190a43c3ae385d98d19f9c858b51920552fb9ceaaEvan Cheng std::map<int, unsigned>::iterator It = 44290a43c3ae385d98d19f9c858b51920552fb9ceaaEvan Cheng SpillSlotsOrReMatsAvailable.find(SlotOrReMat); 443549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng if (It == SpillSlotsOrReMatsAvailable.end()) return; 444b9591c667d956d0607f7388665649fb0852a988cEvan Cheng unsigned Reg = It->second >> 1; 445549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng SpillSlotsOrReMatsAvailable.erase(It); 44607cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner 44707cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner // This register may hold the value of multiple stack slots, only remove this 44807cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner // stack slot from the set of values the register contains. 44907cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner std::multimap<unsigned, int>::iterator I = PhysRegsAvailable.lower_bound(Reg); 45007cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner for (; ; ++I) { 45107cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner assert(I != PhysRegsAvailable.end() && I->first == Reg && 45207cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner "Map inverse broken!"); 453549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng if (I->second == SlotOrReMat) break; 45407cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner } 45507cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner PhysRegsAvailable.erase(I); 4568c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner} 4578c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 4588c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 45907cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner 46028bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng/// InvalidateKills - MI is going to be deleted. If any of its operands are 46128bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng/// marked kill, then invalidate the information. 46228bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Chengstatic void InvalidateKills(MachineInstr &MI, BitVector &RegKills, 463c91f0b80687f0a6fafa5a5e6cd87498e2de6fc3eEvan Cheng std::vector<MachineOperand*> &KillOps, 46466f716354527c5ab4687a89a1605915e5128a106Evan Cheng SmallVector<unsigned, 2> *KillRegs = NULL) { 46528bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 46628bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng MachineOperand &MO = MI.getOperand(i); 46792dfe2001e96f6e2b6d327e8816f38033f88b295Dan Gohman if (!MO.isRegister() || !MO.isUse() || !MO.isKill()) 46828bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng continue; 46928bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng unsigned Reg = MO.getReg(); 470b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng if (KillRegs) 471b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng KillRegs->push_back(Reg); 47228bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng if (KillOps[Reg] == &MO) { 47328bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng RegKills.reset(Reg); 47428bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng KillOps[Reg] = NULL; 47528bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng } 47628bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng } 47728bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng} 47828bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng 47939c883cfc52776fa9a553f7e7ff06816ed476adbEvan Cheng/// InvalidateKill - A MI that defines the specified register is being deleted, 48039c883cfc52776fa9a553f7e7ff06816ed476adbEvan Cheng/// invalidate the register kill information. 48139c883cfc52776fa9a553f7e7ff06816ed476adbEvan Chengstatic void InvalidateKill(unsigned Reg, BitVector &RegKills, 48239c883cfc52776fa9a553f7e7ff06816ed476adbEvan Cheng std::vector<MachineOperand*> &KillOps) { 48339c883cfc52776fa9a553f7e7ff06816ed476adbEvan Cheng if (RegKills[Reg]) { 484f73823000e2d5d6e1cf65bdf5a107297e18d35fbChris Lattner KillOps[Reg]->setIsKill(false); 48539c883cfc52776fa9a553f7e7ff06816ed476adbEvan Cheng KillOps[Reg] = NULL; 48639c883cfc52776fa9a553f7e7ff06816ed476adbEvan Cheng RegKills.reset(Reg); 48739c883cfc52776fa9a553f7e7ff06816ed476adbEvan Cheng } 48839c883cfc52776fa9a553f7e7ff06816ed476adbEvan Cheng} 48939c883cfc52776fa9a553f7e7ff06816ed476adbEvan Cheng 490b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng/// InvalidateRegDef - If the def operand of the specified def MI is now dead 491b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng/// (since it's spill instruction is removed), mark it isDead. Also checks if 492b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng/// the def MI has other definition operands that are not dead. Returns it by 493b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng/// reference. 494b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Chengstatic bool InvalidateRegDef(MachineBasicBlock::iterator I, 495b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng MachineInstr &NewDef, unsigned Reg, 496b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng bool &HasLiveDef) { 497b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng // Due to remat, it's possible this reg isn't being reused. That is, 498b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng // the def of this reg (by prev MI) is now dead. 499b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng MachineInstr *DefMI = I; 500b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng MachineOperand *DefOp = NULL; 501b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng for (unsigned i = 0, e = DefMI->getNumOperands(); i != e; ++i) { 502b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng MachineOperand &MO = DefMI->getOperand(i); 50392dfe2001e96f6e2b6d327e8816f38033f88b295Dan Gohman if (MO.isRegister() && MO.isDef()) { 504b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng if (MO.getReg() == Reg) 505b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng DefOp = &MO; 506b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng else if (!MO.isDead()) 507b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng HasLiveDef = true; 508b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng } 509b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng } 510b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng if (!DefOp) 511b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng return false; 512b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng 513b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng bool FoundUse = false, Done = false; 514b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng MachineBasicBlock::iterator E = NewDef; 515b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng ++I; ++E; 516b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng for (; !Done && I != E; ++I) { 517b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng MachineInstr *NMI = I; 518b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng for (unsigned j = 0, ee = NMI->getNumOperands(); j != ee; ++j) { 519b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng MachineOperand &MO = NMI->getOperand(j); 52092dfe2001e96f6e2b6d327e8816f38033f88b295Dan Gohman if (!MO.isRegister() || MO.getReg() != Reg) 521b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng continue; 522b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng if (MO.isUse()) 523b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng FoundUse = true; 524b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng Done = true; // Stop after scanning all the operands of this MI. 525b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng } 526b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng } 527b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng if (!FoundUse) { 528b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng // Def is dead! 529b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng DefOp->setIsDead(); 530b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng return true; 531b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng } 532b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng return false; 533b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng} 534b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng 53528bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng/// UpdateKills - Track and update kill info. If a MI reads a register that is 53628bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng/// marked kill, then it must be due to register reuse. Transfer the kill info 53728bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng/// over. 53828bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Chengstatic void UpdateKills(MachineInstr &MI, BitVector &RegKills, 53928bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng std::vector<MachineOperand*> &KillOps) { 54028bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng const TargetInstrDescriptor *TID = MI.getInstrDescriptor(); 54128bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 54228bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng MachineOperand &MO = MI.getOperand(i); 54392dfe2001e96f6e2b6d327e8816f38033f88b295Dan Gohman if (!MO.isRegister() || !MO.isUse()) 54428bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng continue; 54528bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng unsigned Reg = MO.getReg(); 54628bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng if (Reg == 0) 54728bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng continue; 54828bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng 54928bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng if (RegKills[Reg]) { 55028bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng // That can't be right. Register is killed but not re-defined and it's 55128bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng // being reused. Let's fix that. 552f73823000e2d5d6e1cf65bdf5a107297e18d35fbChris Lattner KillOps[Reg]->setIsKill(false); 55339c883cfc52776fa9a553f7e7ff06816ed476adbEvan Cheng KillOps[Reg] = NULL; 55439c883cfc52776fa9a553f7e7ff06816ed476adbEvan Cheng RegKills.reset(Reg); 55528bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng if (i < TID->numOperands && 55628bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng TID->getOperandConstraint(i, TOI::TIED_TO) == -1) 55728bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng // Unless it's a two-address operand, this is the new kill. 55828bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng MO.setIsKill(); 55928bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng } 56028bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng if (MO.isKill()) { 56128bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng RegKills.set(Reg); 56228bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng KillOps[Reg] = &MO; 56328bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng } 56428bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng } 56528bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng 56628bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 56728bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng const MachineOperand &MO = MI.getOperand(i); 56892dfe2001e96f6e2b6d327e8816f38033f88b295Dan Gohman if (!MO.isRegister() || !MO.isDef()) 56928bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng continue; 57028bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng unsigned Reg = MO.getReg(); 57128bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng RegKills.reset(Reg); 57228bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng KillOps[Reg] = NULL; 57328bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng } 57428bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng} 57528bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng 57628bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng 5777fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner// ReusedOp - For each reused operand, we keep track of a bit of information, in 5787fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner// case we need to rollback upon processing a new operand. See comments below. 5797fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattnernamespace { 5807fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner struct ReusedOp { 5817fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner // The MachineInstr operand that reused an available value. 5827fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner unsigned Operand; 583edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 584549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // StackSlotOrReMat - The spill slot or remat id of the value being reused. 585549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng unsigned StackSlotOrReMat; 586edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 5877fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner // PhysRegReused - The physical register the value was available in. 5887fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner unsigned PhysRegReused; 589edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 5907fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner // AssignedPhysReg - The physreg that was assigned for use by the reload. 5917fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner unsigned AssignedPhysReg; 5928a61a7524af19d67bd11f8e7d868ca75efbf5c91Chris Lattner 5938a61a7524af19d67bd11f8e7d868ca75efbf5c91Chris Lattner // VirtReg - The virtual register itself. 5948a61a7524af19d67bd11f8e7d868ca75efbf5c91Chris Lattner unsigned VirtReg; 5958a61a7524af19d67bd11f8e7d868ca75efbf5c91Chris Lattner 5968a61a7524af19d67bd11f8e7d868ca75efbf5c91Chris Lattner ReusedOp(unsigned o, unsigned ss, unsigned prr, unsigned apr, 5978a61a7524af19d67bd11f8e7d868ca75efbf5c91Chris Lattner unsigned vreg) 59890a43c3ae385d98d19f9c858b51920552fb9ceaaEvan Cheng : Operand(o), StackSlotOrReMat(ss), PhysRegReused(prr), 59990a43c3ae385d98d19f9c858b51920552fb9ceaaEvan Cheng AssignedPhysReg(apr), VirtReg(vreg) {} 6007fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner }; 601540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner 602540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner /// ReuseInfo - This maintains a collection of ReuseOp's for each operand that 603540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner /// is reused instead of reloaded. 604f8c68f694c25b1ae8c0e5adb2a19432cb405d232Chris Lattner class VISIBILITY_HIDDEN ReuseInfo { 605540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner MachineInstr &MI; 606540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner std::vector<ReusedOp> Reuses; 607957840b3e14938fc86c306fda99ac039d1777a4cEvan Cheng BitVector PhysRegsClobbered; 608540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner public: 609e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng ReuseInfo(MachineInstr &mi, const MRegisterInfo *mri) : MI(mi) { 610957840b3e14938fc86c306fda99ac039d1777a4cEvan Cheng PhysRegsClobbered.resize(mri->getNumRegs()); 611e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng } 612540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner 613540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner bool hasReuses() const { 614540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner return !Reuses.empty(); 615540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner } 616540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner 617540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner /// addReuse - If we choose to reuse a virtual register that is already 618540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner /// available instead of reloading it, remember that we did so. 619549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng void addReuse(unsigned OpNo, unsigned StackSlotOrReMat, 620540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner unsigned PhysRegReused, unsigned AssignedPhysReg, 621540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner unsigned VirtReg) { 622540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner // If the reload is to the assigned register anyway, no undo will be 623540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner // required. 624540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner if (PhysRegReused == AssignedPhysReg) return; 625540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner 626540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner // Otherwise, remember this. 627549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng Reuses.push_back(ReusedOp(OpNo, StackSlotOrReMat, PhysRegReused, 628540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner AssignedPhysReg, VirtReg)); 629540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner } 630e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng 631e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng void markClobbered(unsigned PhysReg) { 632957840b3e14938fc86c306fda99ac039d1777a4cEvan Cheng PhysRegsClobbered.set(PhysReg); 633e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng } 634e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng 635e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng bool isClobbered(unsigned PhysReg) const { 636957840b3e14938fc86c306fda99ac039d1777a4cEvan Cheng return PhysRegsClobbered.test(PhysReg); 637e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng } 638540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner 639540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner /// GetRegForReload - We are about to emit a reload into PhysReg. If there 640540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner /// is some other operand that is using the specified register, either pick 641540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner /// a new register to use, or evict the previous reload and use this reg. 642540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner unsigned GetRegForReload(unsigned PhysReg, MachineInstr *MI, 643540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner AvailableSpills &Spills, 644fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng std::vector<MachineInstr*> &MaybeDeadStores, 64528bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng SmallSet<unsigned, 8> &Rejected, 64628bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng BitVector &RegKills, 647549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng std::vector<MachineOperand*> &KillOps, 648549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng VirtRegMap &VRM) { 649f6372aa1cc568df19da7c5023e83c75aa9404a07Owen Anderson const TargetInstrInfo* TII = MI->getParent()->getParent()->getTarget() 650f6372aa1cc568df19da7c5023e83c75aa9404a07Owen Anderson .getInstrInfo(); 651f6372aa1cc568df19da7c5023e83c75aa9404a07Owen Anderson 652540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner if (Reuses.empty()) return PhysReg; // This is most often empty. 653540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner 654540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner for (unsigned ro = 0, e = Reuses.size(); ro != e; ++ro) { 655540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner ReusedOp &Op = Reuses[ro]; 656540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner // If we find some other reuse that was supposed to use this register 657540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner // exactly for its reload, we can change this reload to use ITS reload 6583c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng // register. That is, unless its reload register has already been 6593c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng // considered and subsequently rejected because it has also been reused 6603c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng // by another operand. 6613c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng if (Op.PhysRegReused == PhysReg && 6623c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng Rejected.count(Op.AssignedPhysReg) == 0) { 663540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner // Yup, use the reload register that we didn't use before. 6643c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng unsigned NewReg = Op.AssignedPhysReg; 6653c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng Rejected.insert(PhysReg); 66628bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng return GetRegForReload(NewReg, MI, Spills, MaybeDeadStores, Rejected, 667549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng RegKills, KillOps, VRM); 668540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner } else { 669540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner // Otherwise, we might also have a problem if a previously reused 670540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner // value aliases the new register. If so, codegen the previous reload 671540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner // and use this one. 672540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner unsigned PRRU = Op.PhysRegReused; 673540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner const MRegisterInfo *MRI = Spills.getRegInfo(); 674540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner if (MRI->areAliases(PRRU, PhysReg)) { 675540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner // Okay, we found out that an alias of a reused register 676540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner // was used. This isn't good because it means we have 677540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner // to undo a previous reuse. 678540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner MachineBasicBlock *MBB = MI->getParent(); 679540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner const TargetRegisterClass *AliasRC = 68084bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner MBB->getParent()->getRegInfo().getRegClass(Op.VirtReg); 68128bad084118a9746df95084364d7d95de00c3b67Chris Lattner 68228bad084118a9746df95084364d7d95de00c3b67Chris Lattner // Copy Op out of the vector and remove it, we're going to insert an 68328bad084118a9746df95084364d7d95de00c3b67Chris Lattner // explicit load for it. 68428bad084118a9746df95084364d7d95de00c3b67Chris Lattner ReusedOp NewOp = Op; 68528bad084118a9746df95084364d7d95de00c3b67Chris Lattner Reuses.erase(Reuses.begin()+ro); 68628bad084118a9746df95084364d7d95de00c3b67Chris Lattner 68728bad084118a9746df95084364d7d95de00c3b67Chris Lattner // Ok, we're going to try to reload the assigned physreg into the 68828bad084118a9746df95084364d7d95de00c3b67Chris Lattner // slot that we were supposed to in the first place. However, that 68928bad084118a9746df95084364d7d95de00c3b67Chris Lattner // register could hold a reuse. Check to see if it conflicts or 69028bad084118a9746df95084364d7d95de00c3b67Chris Lattner // would prefer us to use a different register. 69128bad084118a9746df95084364d7d95de00c3b67Chris Lattner unsigned NewPhysReg = GetRegForReload(NewOp.AssignedPhysReg, 69228bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng MI, Spills, MaybeDeadStores, 693549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng Rejected, RegKills, KillOps, VRM); 69428bad084118a9746df95084364d7d95de00c3b67Chris Lattner 695549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng if (NewOp.StackSlotOrReMat > VirtRegMap::MAX_STACK_SLOT) { 696549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng MRI->reMaterialize(*MBB, MI, NewPhysReg, 697549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng VRM.getReMaterializedMI(NewOp.VirtReg)); 698549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng ++NumReMats; 699549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng } else { 700f6372aa1cc568df19da7c5023e83c75aa9404a07Owen Anderson TII->loadRegFromStackSlot(*MBB, MI, NewPhysReg, 701549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng NewOp.StackSlotOrReMat, AliasRC); 702fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng // Any stores to this stack slot are not dead anymore. 703fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng MaybeDeadStores[NewOp.StackSlotOrReMat] = NULL; 704549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng ++NumLoads; 705549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng } 70628bad084118a9746df95084364d7d95de00c3b67Chris Lattner Spills.ClobberPhysReg(NewPhysReg); 70728bad084118a9746df95084364d7d95de00c3b67Chris Lattner Spills.ClobberPhysReg(NewOp.PhysRegReused); 708540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner 709e53f4a055f74bded20d6129b4724ddd17fd199f6Chris Lattner MI->getOperand(NewOp.Operand).setReg(NewPhysReg); 710540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner 711549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng Spills.addAvailable(NewOp.StackSlotOrReMat, MI, NewPhysReg); 71228bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng MachineBasicBlock::iterator MII = MI; 71328bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng --MII; 71428bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng UpdateKills(*MII, RegKills, KillOps); 71528bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng DOUT << '\t' << *MII; 716540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner 717b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling DOUT << "Reuse undone!\n"; 718540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner --NumReused; 71928bad084118a9746df95084364d7d95de00c3b67Chris Lattner 72028bad084118a9746df95084364d7d95de00c3b67Chris Lattner // Finally, PhysReg is now available, go ahead and use it. 721540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner return PhysReg; 722540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner } 723540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner } 724540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner } 725540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner return PhysReg; 726540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner } 7273c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng 7283c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng /// GetRegForReload - Helper for the above GetRegForReload(). Add a 7293c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng /// 'Rejected' set to remember which registers have been considered and 7303c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng /// rejected for the reload. This avoids infinite looping in case like 7313c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng /// this: 7323c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng /// t1 := op t2, t3 7333c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng /// t2 <- assigned r0 for use by the reload but ended up reuse r1 7343c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng /// t3 <- assigned r1 for use by the reload but ended up reuse r0 7353c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng /// t1 <- desires r1 7363c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng /// sees r1 is taken by t2, tries t2's reload register r0 7373c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng /// sees r0 is taken by t3, tries t3's reload register r1 7383c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng /// sees r1 is taken by t2, tries t2's reload register r0 ... 7393c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng unsigned GetRegForReload(unsigned PhysReg, MachineInstr *MI, 7403c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng AvailableSpills &Spills, 741fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng std::vector<MachineInstr*> &MaybeDeadStores, 74228bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng BitVector &RegKills, 743549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng std::vector<MachineOperand*> &KillOps, 744549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng VirtRegMap &VRM) { 74508a4d5a343e886816b31a78d9b7e70240d9c67beChris Lattner SmallSet<unsigned, 8> Rejected; 74628bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng return GetRegForReload(PhysReg, MI, Spills, MaybeDeadStores, Rejected, 747549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng RegKills, KillOps, VRM); 7483c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng } 749540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner }; 7507fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner} 7517fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner 75266f716354527c5ab4687a89a1605915e5128a106Evan Cheng/// PrepForUnfoldOpti - Turn a store folding instruction into a load folding 75366f716354527c5ab4687a89a1605915e5128a106Evan Cheng/// instruction. e.g. 75466f716354527c5ab4687a89a1605915e5128a106Evan Cheng/// xorl %edi, %eax 75566f716354527c5ab4687a89a1605915e5128a106Evan Cheng/// movl %eax, -32(%ebp) 75666f716354527c5ab4687a89a1605915e5128a106Evan Cheng/// movl -36(%ebp), %eax 75766f716354527c5ab4687a89a1605915e5128a106Evan Cheng/// orl %eax, -32(%ebp) 75866f716354527c5ab4687a89a1605915e5128a106Evan Cheng/// ==> 75966f716354527c5ab4687a89a1605915e5128a106Evan Cheng/// xorl %edi, %eax 76066f716354527c5ab4687a89a1605915e5128a106Evan Cheng/// orl -36(%ebp), %eax 76166f716354527c5ab4687a89a1605915e5128a106Evan Cheng/// mov %eax, -32(%ebp) 76266f716354527c5ab4687a89a1605915e5128a106Evan Cheng/// This enables unfolding optimization for a subsequent instruction which will 76366f716354527c5ab4687a89a1605915e5128a106Evan Cheng/// also eliminate the newly introduced store instruction. 76466f716354527c5ab4687a89a1605915e5128a106Evan Chengbool LocalSpiller::PrepForUnfoldOpti(MachineBasicBlock &MBB, 76566f716354527c5ab4687a89a1605915e5128a106Evan Cheng MachineBasicBlock::iterator &MII, 76666f716354527c5ab4687a89a1605915e5128a106Evan Cheng std::vector<MachineInstr*> &MaybeDeadStores, 76766f716354527c5ab4687a89a1605915e5128a106Evan Cheng AvailableSpills &Spills, 76866f716354527c5ab4687a89a1605915e5128a106Evan Cheng BitVector &RegKills, 76966f716354527c5ab4687a89a1605915e5128a106Evan Cheng std::vector<MachineOperand*> &KillOps, 77066f716354527c5ab4687a89a1605915e5128a106Evan Cheng VirtRegMap &VRM) { 77166f716354527c5ab4687a89a1605915e5128a106Evan Cheng MachineFunction &MF = *MBB.getParent(); 77266f716354527c5ab4687a89a1605915e5128a106Evan Cheng MachineInstr &MI = *MII; 77366f716354527c5ab4687a89a1605915e5128a106Evan Cheng unsigned UnfoldedOpc = 0; 77466f716354527c5ab4687a89a1605915e5128a106Evan Cheng unsigned UnfoldPR = 0; 77566f716354527c5ab4687a89a1605915e5128a106Evan Cheng unsigned UnfoldVR = 0; 77666f716354527c5ab4687a89a1605915e5128a106Evan Cheng int FoldedSS = VirtRegMap::NO_STACK_SLOT; 77766f716354527c5ab4687a89a1605915e5128a106Evan Cheng VirtRegMap::MI2VirtMapTy::const_iterator I, End; 77866f716354527c5ab4687a89a1605915e5128a106Evan Cheng for (tie(I, End) = VRM.getFoldedVirts(&MI); I != End; ++I) { 77966f716354527c5ab4687a89a1605915e5128a106Evan Cheng // Only transform a MI that folds a single register. 78066f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (UnfoldedOpc) 78166f716354527c5ab4687a89a1605915e5128a106Evan Cheng return false; 78266f716354527c5ab4687a89a1605915e5128a106Evan Cheng UnfoldVR = I->second.first; 78366f716354527c5ab4687a89a1605915e5128a106Evan Cheng VirtRegMap::ModRef MR = I->second.second; 78466f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (VRM.isAssignedReg(UnfoldVR)) 78566f716354527c5ab4687a89a1605915e5128a106Evan Cheng continue; 78666f716354527c5ab4687a89a1605915e5128a106Evan Cheng // If this reference is not a use, any previous store is now dead. 78766f716354527c5ab4687a89a1605915e5128a106Evan Cheng // Otherwise, the store to this stack slot is not dead anymore. 78866f716354527c5ab4687a89a1605915e5128a106Evan Cheng FoldedSS = VRM.getStackSlot(UnfoldVR); 78966f716354527c5ab4687a89a1605915e5128a106Evan Cheng MachineInstr* DeadStore = MaybeDeadStores[FoldedSS]; 79066f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (DeadStore && (MR & VirtRegMap::isModRef)) { 79166f716354527c5ab4687a89a1605915e5128a106Evan Cheng unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(FoldedSS); 79266f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (!PhysReg || 79366f716354527c5ab4687a89a1605915e5128a106Evan Cheng DeadStore->findRegisterUseOperandIdx(PhysReg, true) == -1) 79466f716354527c5ab4687a89a1605915e5128a106Evan Cheng continue; 79566f716354527c5ab4687a89a1605915e5128a106Evan Cheng UnfoldPR = PhysReg; 7966425f8be7263e625c2d7484eb2fb8f6643824f49Owen Anderson UnfoldedOpc = TII->getOpcodeAfterMemoryUnfold(MI.getOpcode(), 79766f716354527c5ab4687a89a1605915e5128a106Evan Cheng false, true); 79866f716354527c5ab4687a89a1605915e5128a106Evan Cheng } 79966f716354527c5ab4687a89a1605915e5128a106Evan Cheng } 80066f716354527c5ab4687a89a1605915e5128a106Evan Cheng 80166f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (!UnfoldedOpc) 80266f716354527c5ab4687a89a1605915e5128a106Evan Cheng return false; 80366f716354527c5ab4687a89a1605915e5128a106Evan Cheng 80466f716354527c5ab4687a89a1605915e5128a106Evan Cheng for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 80566f716354527c5ab4687a89a1605915e5128a106Evan Cheng MachineOperand &MO = MI.getOperand(i); 80666f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (!MO.isRegister() || MO.getReg() == 0 || !MO.isUse()) 80766f716354527c5ab4687a89a1605915e5128a106Evan Cheng continue; 80866f716354527c5ab4687a89a1605915e5128a106Evan Cheng unsigned VirtReg = MO.getReg(); 809c498b0281fa81bc213ad1a1228664d480936c0e6Evan Cheng if (MRegisterInfo::isPhysicalRegister(VirtReg) || MO.getSubReg()) 81066f716354527c5ab4687a89a1605915e5128a106Evan Cheng continue; 81166f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (VRM.isAssignedReg(VirtReg)) { 81266f716354527c5ab4687a89a1605915e5128a106Evan Cheng unsigned PhysReg = VRM.getPhys(VirtReg); 81366f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (PhysReg && MRI->regsOverlap(PhysReg, UnfoldPR)) 81466f716354527c5ab4687a89a1605915e5128a106Evan Cheng return false; 81566f716354527c5ab4687a89a1605915e5128a106Evan Cheng } else if (VRM.isReMaterialized(VirtReg)) 81666f716354527c5ab4687a89a1605915e5128a106Evan Cheng continue; 81766f716354527c5ab4687a89a1605915e5128a106Evan Cheng int SS = VRM.getStackSlot(VirtReg); 81866f716354527c5ab4687a89a1605915e5128a106Evan Cheng unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(SS); 81966f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (PhysReg) { 82066f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (MRI->regsOverlap(PhysReg, UnfoldPR)) 82166f716354527c5ab4687a89a1605915e5128a106Evan Cheng return false; 82266f716354527c5ab4687a89a1605915e5128a106Evan Cheng continue; 82366f716354527c5ab4687a89a1605915e5128a106Evan Cheng } 82466f716354527c5ab4687a89a1605915e5128a106Evan Cheng PhysReg = VRM.getPhys(VirtReg); 82566f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (!MRI->regsOverlap(PhysReg, UnfoldPR)) 82666f716354527c5ab4687a89a1605915e5128a106Evan Cheng continue; 82766f716354527c5ab4687a89a1605915e5128a106Evan Cheng 82866f716354527c5ab4687a89a1605915e5128a106Evan Cheng // Ok, we'll need to reload the value into a register which makes 82966f716354527c5ab4687a89a1605915e5128a106Evan Cheng // it impossible to perform the store unfolding optimization later. 83066f716354527c5ab4687a89a1605915e5128a106Evan Cheng // Let's see if it is possible to fold the load if the store is 83166f716354527c5ab4687a89a1605915e5128a106Evan Cheng // unfolded. This allows us to perform the store unfolding 83266f716354527c5ab4687a89a1605915e5128a106Evan Cheng // optimization. 83366f716354527c5ab4687a89a1605915e5128a106Evan Cheng SmallVector<MachineInstr*, 4> NewMIs; 8346425f8be7263e625c2d7484eb2fb8f6643824f49Owen Anderson if (TII->unfoldMemoryOperand(MF, &MI, UnfoldVR, false, false, NewMIs)) { 83566f716354527c5ab4687a89a1605915e5128a106Evan Cheng assert(NewMIs.size() == 1); 83666f716354527c5ab4687a89a1605915e5128a106Evan Cheng MachineInstr *NewMI = NewMIs.back(); 83766f716354527c5ab4687a89a1605915e5128a106Evan Cheng NewMIs.clear(); 83881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng int Idx = NewMI->findRegisterUseOperandIdx(VirtReg); 83981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng assert(Idx != -1); 840aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> Ops; 841aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(Idx); 8426425f8be7263e625c2d7484eb2fb8f6643824f49Owen Anderson MachineInstr *FoldedMI = TII->foldMemoryOperand(NewMI, Ops, SS); 84366f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (FoldedMI) { 844cbfb9b27efd2b4fc1fbc02addf4d41a7d8d8d8ebEvan Cheng if (!VRM.hasPhys(UnfoldVR)) 84566f716354527c5ab4687a89a1605915e5128a106Evan Cheng VRM.assignVirt2Phys(UnfoldVR, UnfoldPR); 84666f716354527c5ab4687a89a1605915e5128a106Evan Cheng VRM.virtFolded(VirtReg, FoldedMI, VirtRegMap::isRef); 84766f716354527c5ab4687a89a1605915e5128a106Evan Cheng MII = MBB.insert(MII, FoldedMI); 848cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng VRM.RemoveMachineInstrFromMaps(&MI); 84966f716354527c5ab4687a89a1605915e5128a106Evan Cheng MBB.erase(&MI); 85066f716354527c5ab4687a89a1605915e5128a106Evan Cheng return true; 85166f716354527c5ab4687a89a1605915e5128a106Evan Cheng } 85266f716354527c5ab4687a89a1605915e5128a106Evan Cheng delete NewMI; 85366f716354527c5ab4687a89a1605915e5128a106Evan Cheng } 85466f716354527c5ab4687a89a1605915e5128a106Evan Cheng } 85566f716354527c5ab4687a89a1605915e5128a106Evan Cheng return false; 85666f716354527c5ab4687a89a1605915e5128a106Evan Cheng} 8577fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner 8587277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng/// findSuperReg - Find the SubReg's super-register of given register class 8597277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng/// where its SubIdx sub-register is SubReg. 8607277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Chengstatic unsigned findSuperReg(const TargetRegisterClass *RC, unsigned SubReg, 8617277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng unsigned SubIdx, const MRegisterInfo *MRI) { 8627277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 8637277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng I != E; ++I) { 8647277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng unsigned Reg = *I; 8657277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng if (MRI->getSubReg(Reg, SubIdx) == SubReg) 8667277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng return Reg; 8677277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng } 8687277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng return 0; 8697277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng} 8707277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng 87181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng/// SpillRegToStackSlot - Spill a register to a specified stack slot. Check if 87281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng/// the last store to the same slot is now dead. If so, remove the last store. 87381a038218171860ee4c382849c647d3dc841fe8bEvan Chengvoid LocalSpiller::SpillRegToStackSlot(MachineBasicBlock &MBB, 87481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineBasicBlock::iterator &MII, 87581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng int Idx, unsigned PhysReg, int StackSlot, 87681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng const TargetRegisterClass *RC, 87735a3e4abb96a6947ec66254b72e788bacc3aadd6Evan Cheng bool isAvailable, MachineInstr *&LastStore, 87881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng AvailableSpills &Spills, 87981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng SmallSet<MachineInstr*, 4> &ReMatDefs, 88081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector &RegKills, 88181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng std::vector<MachineOperand*> &KillOps, 882e4b39007c9d3056334264eba9e2e6025e241d2c5Evan Cheng VirtRegMap &VRM) { 883f6372aa1cc568df19da7c5023e83c75aa9404a07Owen Anderson TII->storeRegToStackSlot(MBB, next(MII), PhysReg, true, StackSlot, RC); 88481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng DOUT << "Store:\t" << *next(MII); 88581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 88681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If there is a dead store to this stack slot, nuke it now. 88781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (LastStore) { 88881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng DOUT << "Removed dead store:\t" << *LastStore; 88981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ++NumDSE; 89081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng SmallVector<unsigned, 2> KillRegs; 89181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng InvalidateKills(*LastStore, RegKills, KillOps, &KillRegs); 89281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineBasicBlock::iterator PrevMII = LastStore; 89381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool CheckDef = PrevMII != MBB.begin(); 89481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CheckDef) 89581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng --PrevMII; 89681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MBB.erase(LastStore); 897cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng VRM.RemoveMachineInstrFromMaps(LastStore); 89881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CheckDef) { 89981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Look at defs of killed registers on the store. Mark the defs 90081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // as dead since the store has been deleted and they aren't 90181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // being reused. 90281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (unsigned j = 0, ee = KillRegs.size(); j != ee; ++j) { 90381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool HasOtherDef = false; 90481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (InvalidateRegDef(PrevMII, *MII, KillRegs[j], HasOtherDef)) { 90581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *DeadDef = PrevMII; 90681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (ReMatDefs.count(DeadDef) && !HasOtherDef) { 90781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // FIXME: This assumes a remat def does not have side 90881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // effects. 90981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MBB.erase(DeadDef); 910cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng VRM.RemoveMachineInstrFromMaps(DeadDef); 91181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ++NumDRM; 91281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 91381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 91481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 91581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 91681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 91781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 918e4b39007c9d3056334264eba9e2e6025e241d2c5Evan Cheng LastStore = next(MII); 91981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 92081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If the stack slot value was previously available in some other 92181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // register, change it now. Otherwise, make the register available, 92281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // in PhysReg. 92381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Spills.ModifyStackSlotOrReMat(StackSlot); 92481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Spills.ClobberPhysReg(PhysReg); 92535a3e4abb96a6947ec66254b72e788bacc3aadd6Evan Cheng Spills.addAvailable(StackSlot, LastStore, PhysReg, isAvailable); 92681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ++NumStores; 92781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 92881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 9297fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner/// rewriteMBB - Keep track of which spills are available even after the 93081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng/// register allocator is done with them. If possible, avid reloading vregs. 931549f27d3070195d6647b796841a5291b4549e8e0Evan Chengvoid LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { 932b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling DOUT << MBB.getBasicBlock()->getName() << ":\n"; 9337fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner 934fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng MachineFunction &MF = *MBB.getParent(); 935d10fd9791c20fd8368fa0ce94b626b769c6c8ba0Owen Anderson 93666cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner // Spills - Keep track of which spilled values are available in physregs so 93766cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner // that we can choose to reuse the physregs instead of emitting reloads. 93866cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner AvailableSpills Spills(MRI, TII); 93966cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner 94052b25db3ef9390271bbfa0b5c6efe0a72ce7cb8eChris Lattner // MaybeDeadStores - When we need to write a value back into a stack slot, 94152b25db3ef9390271bbfa0b5c6efe0a72ce7cb8eChris Lattner // keep track of the inserted store. If the stack slot value is never read 94252b25db3ef9390271bbfa0b5c6efe0a72ce7cb8eChris Lattner // (because the value was used from some available register, for example), and 94352b25db3ef9390271bbfa0b5c6efe0a72ce7cb8eChris Lattner // subsequently stored to, the original store is dead. This map keeps track 94452b25db3ef9390271bbfa0b5c6efe0a72ce7cb8eChris Lattner // of inserted stores that are not used. If we see a subsequent store to the 94552b25db3ef9390271bbfa0b5c6efe0a72ce7cb8eChris Lattner // same stack slot, the original store is deleted. 946fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng std::vector<MachineInstr*> MaybeDeadStores; 947fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng MaybeDeadStores.resize(MF.getFrameInfo()->getObjectIndexEnd(), NULL); 94852b25db3ef9390271bbfa0b5c6efe0a72ce7cb8eChris Lattner 949b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng // ReMatDefs - These are rematerializable def MIs which are not deleted. 950b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng SmallSet<MachineInstr*, 4> ReMatDefs; 951b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng 9520c40d72b014e8c0f54552d38288a29182effba58Evan Cheng // Keep track of kill information. 9530c40d72b014e8c0f54552d38288a29182effba58Evan Cheng BitVector RegKills(MRI->getNumRegs()); 9540c40d72b014e8c0f54552d38288a29182effba58Evan Cheng std::vector<MachineOperand*> KillOps; 9550c40d72b014e8c0f54552d38288a29182effba58Evan Cheng KillOps.resize(MRI->getNumRegs(), NULL); 9560c40d72b014e8c0f54552d38288a29182effba58Evan Cheng 9577fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner for (MachineBasicBlock::iterator MII = MBB.begin(), E = MBB.end(); 9587fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner MII != E; ) { 9597fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner MachineBasicBlock::iterator NextMII = MII; ++NextMII; 9600c40d72b014e8c0f54552d38288a29182effba58Evan Cheng 96166f716354527c5ab4687a89a1605915e5128a106Evan Cheng VirtRegMap::MI2VirtMapTy::const_iterator I, End; 9620c40d72b014e8c0f54552d38288a29182effba58Evan Cheng bool Erased = false; 9630c40d72b014e8c0f54552d38288a29182effba58Evan Cheng bool BackTracked = false; 96466f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (PrepForUnfoldOpti(MBB, MII, 96566f716354527c5ab4687a89a1605915e5128a106Evan Cheng MaybeDeadStores, Spills, RegKills, KillOps, VRM)) 96666f716354527c5ab4687a89a1605915e5128a106Evan Cheng NextMII = next(MII); 9677fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner 96866f716354527c5ab4687a89a1605915e5128a106Evan Cheng MachineInstr &MI = *MII; 96986facc282850f99479584596058a5625b53caa69Evan Cheng const TargetInstrDescriptor *TID = MI.getInstrDescriptor(); 970e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng 9710cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Insert restores here if asked to. 9720cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (VRM.isRestorePt(&MI)) { 9730cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng std::vector<unsigned> &RestoreRegs = VRM.getRestorePtRestores(&MI); 9740cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng for (unsigned i = 0, e = RestoreRegs.size(); i != e; ++i) { 9750cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng unsigned VirtReg = RestoreRegs[i]; 9760cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!VRM.getPreSplitReg(VirtReg)) 9770cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng continue; // Split interval spilled again. 9780cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng unsigned Phys = VRM.getPhys(VirtReg); 97984bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner RegInfo->setPhysRegUsed(Phys); 9800cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (VRM.isReMaterialized(VirtReg)) { 9810cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MRI->reMaterialize(MBB, &MI, Phys, 9820cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng VRM.getReMaterializedMI(VirtReg)); 9830cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++NumReMats; 9840cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } else { 98584bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg); 986f6372aa1cc568df19da7c5023e83c75aa9404a07Owen Anderson TII->loadRegFromStackSlot(MBB, &MI, Phys, VRM.getStackSlot(VirtReg), 98784bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner RC); 9880cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++NumLoads; 9890cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 9900cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // This invalidates Phys. 9910cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng Spills.ClobberPhysReg(Phys); 9920cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng UpdateKills(*prior(MII), RegKills, KillOps); 9930cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng DOUT << '\t' << *prior(MII); 9940cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 9950cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 9960cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 99781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Insert spills here if asked to. 998cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng if (VRM.isSpillPt(&MI)) { 999b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng std::vector<std::pair<unsigned,bool> > &SpillRegs = 1000b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng VRM.getSpillPtSpills(&MI); 1001cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng for (unsigned i = 0, e = SpillRegs.size(); i != e; ++i) { 1002b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng unsigned VirtReg = SpillRegs[i].first; 1003b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng bool isKill = SpillRegs[i].second; 1004cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng if (!VRM.getPreSplitReg(VirtReg)) 1005cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng continue; // Split interval spilled again. 100684bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner const TargetRegisterClass *RC = RegInfo->getRegClass(VirtReg); 1007cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng unsigned Phys = VRM.getPhys(VirtReg); 1008cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng int StackSlot = VRM.getStackSlot(VirtReg); 1009f6372aa1cc568df19da7c5023e83c75aa9404a07Owen Anderson TII->storeRegToStackSlot(MBB, next(MII), Phys, isKill, StackSlot, RC); 1010d64b5c82b97ad1b74eb9fd2f23257a7899b0c307Evan Cheng MachineInstr *StoreMI = next(MII); 1011d64b5c82b97ad1b74eb9fd2f23257a7899b0c307Evan Cheng DOUT << "Store:\t" << StoreMI; 1012d64b5c82b97ad1b74eb9fd2f23257a7899b0c307Evan Cheng VRM.virtFolded(VirtReg, StoreMI, VirtRegMap::isMod); 1013cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng } 1014e4b39007c9d3056334264eba9e2e6025e241d2c5Evan Cheng NextMII = next(MII); 101581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 101681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 101781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng /// ReusedOperands - Keep track of operand reuse in case we need to undo 101881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng /// reuse. 101981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ReuseInfo ReusedOperands(MI, MRI); 10207fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner // Process all of the spilled uses and all non spilled reg references. 10217fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 10227fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner MachineOperand &MO = MI.getOperand(i); 102350ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner if (!MO.isRegister() || MO.getReg() == 0) 102450ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner continue; // Ignore non-register operands. 102550ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner 102632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng unsigned VirtReg = MO.getReg(); 102732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (MRegisterInfo::isPhysicalRegister(VirtReg)) { 102850ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner // Ignore physregs for spilling, but remember that it is used by this 102950ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner // function. 103084bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner RegInfo->setPhysRegUsed(VirtReg); 103150ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner continue; 103250ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner } 103350ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner 103432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng assert(MRegisterInfo::isVirtualRegister(VirtReg) && 103550ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner "Not a virtual or a physical register?"); 103670306f8348f27c61cfed5a60e2fceac0f29746a2Evan Cheng 1037c498b0281fa81bc213ad1a1228664d480936c0e6Evan Cheng unsigned SubIdx = MO.getSubReg(); 1038549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng if (VRM.isAssignedReg(VirtReg)) { 103950ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner // This virtual register was assigned a physreg! 104050ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner unsigned Phys = VRM.getPhys(VirtReg); 104184bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner RegInfo->setPhysRegUsed(Phys); 1042e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng if (MO.isDef()) 1043e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng ReusedOperands.markClobbered(Phys); 1044c498b0281fa81bc213ad1a1228664d480936c0e6Evan Cheng unsigned RReg = SubIdx ? MRI->getSubReg(Phys, SubIdx) : Phys; 104532dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng MI.getOperand(i).setReg(RReg); 104650ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner continue; 104750ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner } 104850ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner 104950ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner // This virtual register is now known to be a spilled value. 105050ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner if (!MO.isUse()) 105150ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner continue; // Handle defs in the loop below (handle use&def here though) 105250ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner 1053549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng bool DoReMat = VRM.isReMaterialized(VirtReg); 1054549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng int SSorRMId = DoReMat 1055549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng ? VRM.getReMatId(VirtReg) : VRM.getStackSlot(VirtReg); 1056dc6be1985944716a0fb4a2706dcea9e1296e3d6aEvan Cheng int ReuseSlot = SSorRMId; 105750ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner 105850ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner // Check to see if this stack slot is available. 1059dc6be1985944716a0fb4a2706dcea9e1296e3d6aEvan Cheng unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(SSorRMId); 106032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng 106132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // If this is a sub-register use, make sure the reuse register is in the 106232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // right register class. For example, for x86 not all of the 32-bit 106332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // registers have accessible sub-registers. 106432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // Similarly so for EXTRACT_SUBREG. Consider this: 106532dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // EDI = op 106632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // MOV32_mr fi#1, EDI 106732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // ... 106832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // = EXTRACT_SUBREG fi#1 106932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // fi#1 is available in EDI, but it cannot be reused because it's not in 107032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // the right register file. 107132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (PhysReg && 1072c498b0281fa81bc213ad1a1228664d480936c0e6Evan Cheng (SubIdx || MI.getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)) { 107384bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg); 107432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (!RC->contains(PhysReg)) 107532dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng PhysReg = 0; 107632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng } 107732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng 1078dc6be1985944716a0fb4a2706dcea9e1296e3d6aEvan Cheng if (PhysReg) { 10792926869b4a083fc951484de03a9867eabf81e880Chris Lattner // This spilled operand might be part of a two-address operand. If this 10802926869b4a083fc951484de03a9867eabf81e880Chris Lattner // is the case, then changing it will necessarily require changing the 10812926869b4a083fc951484de03a9867eabf81e880Chris Lattner // def part of the instruction as well. However, in some cases, we 10822926869b4a083fc951484de03a9867eabf81e880Chris Lattner // aren't allowed to modify the reused register. If none of these cases 10832926869b4a083fc951484de03a9867eabf81e880Chris Lattner // apply, reuse it. 10842926869b4a083fc951484de03a9867eabf81e880Chris Lattner bool CanReuse = true; 108586facc282850f99479584596058a5625b53caa69Evan Cheng int ti = TID->getOperandConstraint(i, TOI::TIED_TO); 1086360c2dd25a0dc7eaed3d57af47a47ac7d12a6886Evan Cheng if (ti != -1 && 108792dfe2001e96f6e2b6d327e8816f38033f88b295Dan Gohman MI.getOperand(ti).isRegister() && 1088360c2dd25a0dc7eaed3d57af47a47ac7d12a6886Evan Cheng MI.getOperand(ti).getReg() == VirtReg) { 10892926869b4a083fc951484de03a9867eabf81e880Chris Lattner // Okay, we have a two address operand. We can reuse this physreg as 10903c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng // long as we are allowed to clobber the value and there isn't an 10913c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng // earlier def that has already clobbered the physreg. 1092dc6be1985944716a0fb4a2706dcea9e1296e3d6aEvan Cheng CanReuse = Spills.canClobberPhysReg(ReuseSlot) && 1093e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng !ReusedOperands.isClobbered(PhysReg); 10942926869b4a083fc951484de03a9867eabf81e880Chris Lattner } 10952926869b4a083fc951484de03a9867eabf81e880Chris Lattner 10962926869b4a083fc951484de03a9867eabf81e880Chris Lattner if (CanReuse) { 1097addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // If this stack slot value is already available, reuse it! 1098dc6be1985944716a0fb4a2706dcea9e1296e3d6aEvan Cheng if (ReuseSlot > VirtRegMap::MAX_STACK_SLOT) 1099dc6be1985944716a0fb4a2706dcea9e1296e3d6aEvan Cheng DOUT << "Reusing RM#" << ReuseSlot-VirtRegMap::MAX_STACK_SLOT-1; 11002638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng else 1101dc6be1985944716a0fb4a2706dcea9e1296e3d6aEvan Cheng DOUT << "Reusing SS#" << ReuseSlot; 11022638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng DOUT << " from physreg " 1103b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling << MRI->getName(PhysReg) << " for vreg" 1104b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling << VirtReg <<" instead of reloading into physreg " 1105b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling << MRI->getName(VRM.getPhys(VirtReg)) << "\n"; 1106c498b0281fa81bc213ad1a1228664d480936c0e6Evan Cheng unsigned RReg = SubIdx ? MRI->getSubReg(PhysReg, SubIdx) : PhysReg; 110732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng MI.getOperand(i).setReg(RReg); 1108addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner 1109addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // The only technical detail we have is that we don't know that 1110addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // PhysReg won't be clobbered by a reloaded stack slot that occurs 1111addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // later in the instruction. In particular, consider 'op V1, V2'. 1112addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // If V1 is available in physreg R0, we would choose to reuse it 1113addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // here, instead of reloading it into the register the allocator 1114addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // indicated (say R1). However, V2 might have to be reloaded 1115addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // later, and it might indicate that it needs to live in R0. When 1116addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // this occurs, we need to have information available that 1117addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // indicates it is safe to use R1 for the reload instead of R0. 1118addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // 1119addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // To further complicate matters, we might conflict with an alias, 1120addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // or R0 and R1 might not be compatible with each other. In this 1121addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // case, we actually insert a reload for V1 in R1, ensuring that 1122addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // we can get at R0 or its alias. 1123dc6be1985944716a0fb4a2706dcea9e1296e3d6aEvan Cheng ReusedOperands.addReuse(i, ReuseSlot, PhysReg, 1124addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner VRM.getPhys(VirtReg), VirtReg); 1125e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng if (ti != -1) 1126e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng // Only mark it clobbered if this is a use&def operand. 1127e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng ReusedOperands.markClobbered(PhysReg); 1128addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner ++NumReused; 1129fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng 1130fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng if (MI.getOperand(i).isKill() && 1131fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng ReuseSlot <= VirtRegMap::MAX_STACK_SLOT) { 1132fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng // This was the last use and the spilled value is still available 1133fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng // for reuse. That means the spill was unnecessary! 1134fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng MachineInstr* DeadStore = MaybeDeadStores[ReuseSlot]; 1135fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng if (DeadStore) { 1136fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng DOUT << "Removed dead store:\t" << *DeadStore; 1137fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng InvalidateKills(*DeadStore, RegKills, KillOps); 1138cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng VRM.RemoveMachineInstrFromMaps(DeadStore); 113966f716354527c5ab4687a89a1605915e5128a106Evan Cheng MBB.erase(DeadStore); 1140fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng MaybeDeadStores[ReuseSlot] = NULL; 1141fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng ++NumDSE; 1142fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng } 1143fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng } 1144addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner continue; 114532dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng } // CanReuse 1146addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner 1147addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // Otherwise we have a situation where we have a two-address instruction 1148addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // whose mod/ref operand needs to be reloaded. This reload is already 1149addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // available in some register "PhysReg", but if we used PhysReg as the 1150addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // operand to our 2-addr instruction, the instruction would modify 1151addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // PhysReg. This isn't cool if something later uses PhysReg and expects 1152addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // to get its initial value. 115350ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner // 1154addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // To avoid this problem, and to avoid doing a load right after a store, 1155addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // we emit a copy from PhysReg into the designated register for this 1156addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // operand. 1157addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner unsigned DesignatedReg = VRM.getPhys(VirtReg); 1158addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner assert(DesignatedReg && "Must map virtreg to physreg!"); 1159addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner 1160addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // Note that, if we reused a register for a previous operand, the 1161addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // register we want to reload into might not actually be 1162addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // available. If this occurs, use the register indicated by the 1163addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // reuser. 1164addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner if (ReusedOperands.hasReuses()) 1165addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner DesignatedReg = ReusedOperands.GetRegForReload(DesignatedReg, &MI, 1166549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng Spills, MaybeDeadStores, RegKills, KillOps, VRM); 1167addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner 1168ba1fc3daf757c8f880c3069eed20218c91f2c3a8Chris Lattner // If the mapped designated register is actually the physreg we have 1169ba1fc3daf757c8f880c3069eed20218c91f2c3a8Chris Lattner // incoming, we don't need to inserted a dead copy. 1170ba1fc3daf757c8f880c3069eed20218c91f2c3a8Chris Lattner if (DesignatedReg == PhysReg) { 1171ba1fc3daf757c8f880c3069eed20218c91f2c3a8Chris Lattner // If this stack slot value is already available, reuse it! 1172dc6be1985944716a0fb4a2706dcea9e1296e3d6aEvan Cheng if (ReuseSlot > VirtRegMap::MAX_STACK_SLOT) 1173dc6be1985944716a0fb4a2706dcea9e1296e3d6aEvan Cheng DOUT << "Reusing RM#" << ReuseSlot-VirtRegMap::MAX_STACK_SLOT-1; 11742638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng else 1175dc6be1985944716a0fb4a2706dcea9e1296e3d6aEvan Cheng DOUT << "Reusing SS#" << ReuseSlot; 11762638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng DOUT << " from physreg " << MRI->getName(PhysReg) << " for vreg" 1177b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling << VirtReg 1178b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling << " instead of reloading into same physreg.\n"; 1179c498b0281fa81bc213ad1a1228664d480936c0e6Evan Cheng unsigned RReg = SubIdx ? MRI->getSubReg(PhysReg, SubIdx) : PhysReg; 118032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng MI.getOperand(i).setReg(RReg); 11817277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng ReusedOperands.markClobbered(RReg); 1182ba1fc3daf757c8f880c3069eed20218c91f2c3a8Chris Lattner ++NumReused; 1183ba1fc3daf757c8f880c3069eed20218c91f2c3a8Chris Lattner continue; 1184ba1fc3daf757c8f880c3069eed20218c91f2c3a8Chris Lattner } 1185ba1fc3daf757c8f880c3069eed20218c91f2c3a8Chris Lattner 118684bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg); 118784bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner RegInfo->setPhysRegUsed(DesignatedReg); 1188e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng ReusedOperands.markClobbered(DesignatedReg); 1189d10fd9791c20fd8368fa0ce94b626b769c6c8ba0Owen Anderson TII->copyRegToReg(MBB, &MI, DesignatedReg, PhysReg, RC, RC); 1190de4e942faa12a52242915e3334c25f19687f36e2Evan Cheng 11916b448092bff8d149769becaa14415bc1a3857e33Evan Cheng MachineInstr *CopyMI = prior(MII); 11920c40d72b014e8c0f54552d38288a29182effba58Evan Cheng UpdateKills(*CopyMI, RegKills, KillOps); 1193de4e942faa12a52242915e3334c25f19687f36e2Evan Cheng 1194addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // This invalidates DesignatedReg. 1195addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner Spills.ClobberPhysReg(DesignatedReg); 1196addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner 1197dc6be1985944716a0fb4a2706dcea9e1296e3d6aEvan Cheng Spills.addAvailable(ReuseSlot, &MI, DesignatedReg); 119832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng unsigned RReg = 1199c498b0281fa81bc213ad1a1228664d480936c0e6Evan Cheng SubIdx ? MRI->getSubReg(DesignatedReg, SubIdx) : DesignatedReg; 120032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng MI.getOperand(i).setReg(RReg); 1201b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling DOUT << '\t' << *prior(MII); 120250ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner ++NumReused; 120350ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner continue; 120466f716354527c5ab4687a89a1605915e5128a106Evan Cheng } // if (PhysReg) 120550ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner 120650ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner // Otherwise, reload it and remember that we have it. 120750ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner PhysReg = VRM.getPhys(VirtReg); 1208172c362fefe3d6e762ada119d4084ed4ed31595bChris Lattner assert(PhysReg && "Must map virtreg to physreg!"); 120950ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner 121050ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner // Note that, if we reused a register for a previous operand, the 121150ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner // register we want to reload into might not actually be 121250ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner // available. If this occurs, use the register indicated by the 121350ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner // reuser. 1214540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner if (ReusedOperands.hasReuses()) 1215540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner PhysReg = ReusedOperands.GetRegForReload(PhysReg, &MI, 1216549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng Spills, MaybeDeadStores, RegKills, KillOps, VRM); 1217540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner 121884bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner RegInfo->setPhysRegUsed(PhysReg); 1219e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng ReusedOperands.markClobbered(PhysReg); 1220549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng if (DoReMat) { 12212638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng MRI->reMaterialize(MBB, &MI, PhysReg, VRM.getReMaterializedMI(VirtReg)); 12229193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng ++NumReMats; 12239193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng } else { 122484bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner const TargetRegisterClass* RC = RegInfo->getRegClass(VirtReg); 1225f6372aa1cc568df19da7c5023e83c75aa9404a07Owen Anderson TII->loadRegFromStackSlot(MBB, &MI, PhysReg, SSorRMId, RC); 12269193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng ++NumLoads; 12279193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng } 122850ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner // This invalidates PhysReg. 122966cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner Spills.ClobberPhysReg(PhysReg); 123050ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner 123150ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner // Any stores to this stack slot are not dead anymore. 1232549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng if (!DoReMat) 1233fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng MaybeDeadStores[SSorRMId] = NULL; 1234549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng Spills.addAvailable(SSorRMId, &MI, PhysReg); 1235de4e942faa12a52242915e3334c25f19687f36e2Evan Cheng // Assumes this is the last use. IsKill will be unset if reg is reused 1236de4e942faa12a52242915e3334c25f19687f36e2Evan Cheng // unless it's a two-address operand. 1237de4e942faa12a52242915e3334c25f19687f36e2Evan Cheng if (TID->getOperandConstraint(i, TOI::TIED_TO) == -1) 1238de4e942faa12a52242915e3334c25f19687f36e2Evan Cheng MI.getOperand(i).setIsKill(); 1239c498b0281fa81bc213ad1a1228664d480936c0e6Evan Cheng unsigned RReg = SubIdx ? MRI->getSubReg(PhysReg, SubIdx) : PhysReg; 124032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng MI.getOperand(i).setReg(RReg); 12410c40d72b014e8c0f54552d38288a29182effba58Evan Cheng UpdateKills(*prior(MII), RegKills, KillOps); 1242b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling DOUT << '\t' << *prior(MII); 12438c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 12440d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 1245b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling DOUT << '\t' << MI; 12467fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner 124781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 12487fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner // If we have folded references to memory operands, make sure we clear all 12497fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner // physical registers that may contain the value of the spilled virtual 12507fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner // register 125166f716354527c5ab4687a89a1605915e5128a106Evan Cheng SmallSet<int, 2> FoldedSS; 12528f1d6402ba73b96993ffd1eb9434b28c828d8856Chris Lattner for (tie(I, End) = VRM.getFoldedVirts(&MI); I != End; ++I) { 1253bec6a9ea1281a0b3b37aece91ab0df21e086af61Chris Lattner unsigned VirtReg = I->second.first; 1254bec6a9ea1281a0b3b37aece91ab0df21e086af61Chris Lattner VirtRegMap::ModRef MR = I->second.second; 125566f716354527c5ab4687a89a1605915e5128a106Evan Cheng DOUT << "Folded vreg: " << VirtReg << " MR: " << MR; 125681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1257cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner int SS = VRM.getStackSlot(VirtReg); 125881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (SS == VirtRegMap::NO_STACK_SLOT) 125981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 126090a43c3ae385d98d19f9c858b51920552fb9ceaaEvan Cheng FoldedSS.insert(SS); 1261b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling DOUT << " - StackSlot: " << SS << "\n"; 1262cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner 1263cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner // If this folded instruction is just a use, check to see if it's a 1264cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner // straight load from the virt reg slot. 1265cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner if ((MR & VirtRegMap::isRef) && !(MR & VirtRegMap::isMod)) { 1266cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner int FrameIdx; 126732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng unsigned DestReg = TII->isLoadFromStackSlot(&MI, FrameIdx); 126832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (DestReg && FrameIdx == SS) { 126932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // If this spill slot is available, turn it into a copy (or nothing) 127032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // instead of leaving it as a load! 127132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (unsigned InReg = Spills.getSpillSlotOrReMatPhysReg(SS)) { 127232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng DOUT << "Promoted Load To Copy: " << MI; 127332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (DestReg != InReg) { 127484bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner const TargetRegisterClass *RC = RegInfo->getRegClass(VirtReg); 1275d10fd9791c20fd8368fa0ce94b626b769c6c8ba0Owen Anderson TII->copyRegToReg(MBB, &MI, DestReg, InReg, RC, RC); 127632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // Revisit the copy so we make sure to notice the effects of the 127732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // operation on the destreg (either needing to RA it if it's 127832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // virtual or needing to clobber any values if it's physical). 127932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng NextMII = &MI; 128032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng --NextMII; // backtrack to the copy. 128132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng BackTracked = true; 128239c883cfc52776fa9a553f7e7ff06816ed476adbEvan Cheng } else { 128332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng DOUT << "Removing now-noop copy: " << MI; 128439c883cfc52776fa9a553f7e7ff06816ed476adbEvan Cheng // Unset last kill since it's being reused. 128539c883cfc52776fa9a553f7e7ff06816ed476adbEvan Cheng InvalidateKill(InReg, RegKills, KillOps); 128639c883cfc52776fa9a553f7e7ff06816ed476adbEvan Cheng } 128732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng 1288cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng VRM.RemoveMachineInstrFromMaps(&MI); 128932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng MBB.erase(&MI); 129032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng Erased = true; 129132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng goto ProcessNextInst; 1292bec6a9ea1281a0b3b37aece91ab0df21e086af61Chris Lattner } 12937f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng } else { 12947f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(SS); 12957f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng SmallVector<MachineInstr*, 4> NewMIs; 12967f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng if (PhysReg && 12976425f8be7263e625c2d7484eb2fb8f6643824f49Owen Anderson TII->unfoldMemoryOperand(MF, &MI, PhysReg, false, false, NewMIs)) { 12987f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng MBB.insert(MII, NewMIs[0]); 1299cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng VRM.RemoveMachineInstrFromMaps(&MI); 13007f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng MBB.erase(&MI); 13017f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng Erased = true; 13027f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng --NextMII; // backtrack to the unfolded instruction. 13037f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng BackTracked = true; 13047f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng goto ProcessNextInst; 13057f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng } 1306bec6a9ea1281a0b3b37aece91ab0df21e086af61Chris Lattner } 1307cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner } 130852b25db3ef9390271bbfa0b5c6efe0a72ce7cb8eChris Lattner 1309cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner // If this reference is not a use, any previous store is now dead. 1310cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner // Otherwise, the store to this stack slot is not dead anymore. 1311fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng MachineInstr* DeadStore = MaybeDeadStores[SS]; 1312fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng if (DeadStore) { 131366f716354527c5ab4687a89a1605915e5128a106Evan Cheng bool isDead = !(MR & VirtRegMap::isRef); 13147f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng MachineInstr *NewStore = NULL; 1315cbfb9b27efd2b4fc1fbc02addf4d41a7d8d8d8ebEvan Cheng if (MR & VirtRegMap::isModRef) { 13167f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(SS); 13177f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng SmallVector<MachineInstr*, 4> NewMIs; 131835a3e4abb96a6947ec66254b72e788bacc3aadd6Evan Cheng // We can reuse this physreg as long as we are allowed to clobber 131984bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner // the value and there isn't an earlier def that has already clobbered 132084bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner // the physreg. 13217f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng if (PhysReg && 132239c883cfc52776fa9a553f7e7ff06816ed476adbEvan Cheng !TII->isStoreToStackSlot(&MI, SS) && // Not profitable! 13237f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng DeadStore->findRegisterUseOperandIdx(PhysReg, true) != -1 && 13246425f8be7263e625c2d7484eb2fb8f6643824f49Owen Anderson TII->unfoldMemoryOperand(MF, &MI, PhysReg, false, true, NewMIs)) { 13257f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng MBB.insert(MII, NewMIs[0]); 13267f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng NewStore = NewMIs[1]; 13277f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng MBB.insert(MII, NewStore); 1328cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng VRM.RemoveMachineInstrFromMaps(&MI); 13297f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng MBB.erase(&MI); 13307f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng Erased = true; 13317f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng --NextMII; 13327f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng --NextMII; // backtrack to the unfolded instruction. 13337f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng BackTracked = true; 133466f716354527c5ab4687a89a1605915e5128a106Evan Cheng isDead = true; 133566f716354527c5ab4687a89a1605915e5128a106Evan Cheng } 13367f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng } 13377f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng 13387f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng if (isDead) { // Previous store is dead. 1339cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner // If we get here, the store is dead, nuke it now. 1340fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng DOUT << "Removed dead store:\t" << *DeadStore; 1341fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng InvalidateKills(*DeadStore, RegKills, KillOps); 1342cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng VRM.RemoveMachineInstrFromMaps(DeadStore); 13437f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng MBB.erase(DeadStore); 13447f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng if (!NewStore) 13457f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng ++NumDSE; 1346cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner } 13477f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng 1348fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng MaybeDeadStores[SS] = NULL; 13497f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng if (NewStore) { 13507f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng // Treat this store as a spill merged into a copy. That makes the 13517f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng // stack slot value available. 13527f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng VRM.virtFolded(VirtReg, NewStore, VirtRegMap::isMod); 13537f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng goto ProcessNextInst; 13547f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng } 1355cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner } 1356cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner 1357cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner // If the spill slot value is available, and this is a new definition of 1358cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner // the value, the value is not available anymore. 1359cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner if (MR & VirtRegMap::isMod) { 136007cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner // Notice that the value in this stack slot has been modified. 1361549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng Spills.ModifyStackSlotOrReMat(SS); 1362cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner 1363cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner // If this is *just* a mod of the value, check to see if this is just a 1364cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner // store to the spill slot (i.e. the spill got merged into the copy). If 1365cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner // so, realize that the vreg is available now, and add the store to the 1366cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner // MaybeDeadStore info. 1367cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner int StackSlot; 1368cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner if (!(MR & VirtRegMap::isRef)) { 1369cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner if (unsigned SrcReg = TII->isStoreToStackSlot(&MI, StackSlot)) { 1370cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner assert(MRegisterInfo::isPhysicalRegister(SrcReg) && 1371cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner "Src hasn't been allocated yet?"); 137207cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner // Okay, this is certainly a store of SrcReg to [StackSlot]. Mark 1373cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner // this as a potentially dead store in case there is a subsequent 1374cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner // store into the stack slot without a read from it. 1375cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner MaybeDeadStores[StackSlot] = &MI; 1376cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner 1377cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner // If the stack slot value was previously available in some other 1378cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner // register, change it now. Otherwise, make the register available, 1379cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner // in PhysReg. 138091e2390818080ae2b059e3ff850a9455858e4f7bEvan Cheng Spills.addAvailable(StackSlot, &MI, SrcReg, false/*don't clobber*/); 1381cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner } 1382cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner } 13837fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner } 13848c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 13850d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 13867fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner // Process all of the spilled defs. 13877fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 13887fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner MachineOperand &MO = MI.getOperand(i); 138966f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (!(MO.isRegister() && MO.getReg() && MO.isDef())) 139066f716354527c5ab4687a89a1605915e5128a106Evan Cheng continue; 13917fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner 139266f716354527c5ab4687a89a1605915e5128a106Evan Cheng unsigned VirtReg = MO.getReg(); 139366f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (!MRegisterInfo::isVirtualRegister(VirtReg)) { 139466f716354527c5ab4687a89a1605915e5128a106Evan Cheng // Check to see if this is a noop copy. If so, eliminate the 139566f716354527c5ab4687a89a1605915e5128a106Evan Cheng // instruction before considering the dest reg to be changed. 139666f716354527c5ab4687a89a1605915e5128a106Evan Cheng unsigned Src, Dst; 139766f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (TII->isMoveInstr(MI, Src, Dst) && Src == Dst) { 139866f716354527c5ab4687a89a1605915e5128a106Evan Cheng ++NumDCE; 139966f716354527c5ab4687a89a1605915e5128a106Evan Cheng DOUT << "Removing now-noop copy: " << MI; 140066f716354527c5ab4687a89a1605915e5128a106Evan Cheng MBB.erase(&MI); 140166f716354527c5ab4687a89a1605915e5128a106Evan Cheng Erased = true; 1402cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng VRM.RemoveMachineInstrFromMaps(&MI); 140366f716354527c5ab4687a89a1605915e5128a106Evan Cheng Spills.disallowClobberPhysReg(VirtReg); 140466f716354527c5ab4687a89a1605915e5128a106Evan Cheng goto ProcessNextInst; 140566f716354527c5ab4687a89a1605915e5128a106Evan Cheng } 14066ec3626be40963fa405992e219f94d9524fb6c15Chris Lattner 140766f716354527c5ab4687a89a1605915e5128a106Evan Cheng // If it's not a no-op copy, it clobbers the value in the destreg. 140866f716354527c5ab4687a89a1605915e5128a106Evan Cheng Spills.ClobberPhysReg(VirtReg); 140966f716354527c5ab4687a89a1605915e5128a106Evan Cheng ReusedOperands.markClobbered(VirtReg); 14106ec3626be40963fa405992e219f94d9524fb6c15Chris Lattner 141166f716354527c5ab4687a89a1605915e5128a106Evan Cheng // Check to see if this instruction is a load from a stack slot into 141266f716354527c5ab4687a89a1605915e5128a106Evan Cheng // a register. If so, this provides the stack slot value in the reg. 141366f716354527c5ab4687a89a1605915e5128a106Evan Cheng int FrameIdx; 141466f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (unsigned DestReg = TII->isLoadFromStackSlot(&MI, FrameIdx)) { 141566f716354527c5ab4687a89a1605915e5128a106Evan Cheng assert(DestReg == VirtReg && "Unknown load situation!"); 141666f716354527c5ab4687a89a1605915e5128a106Evan Cheng 141766f716354527c5ab4687a89a1605915e5128a106Evan Cheng // If it is a folded reference, then it's not safe to clobber. 141866f716354527c5ab4687a89a1605915e5128a106Evan Cheng bool Folded = FoldedSS.count(FrameIdx); 141966f716354527c5ab4687a89a1605915e5128a106Evan Cheng // Otherwise, if it wasn't available, remember that it is now! 142066f716354527c5ab4687a89a1605915e5128a106Evan Cheng Spills.addAvailable(FrameIdx, &MI, DestReg, !Folded); 142166f716354527c5ab4687a89a1605915e5128a106Evan Cheng goto ProcessNextInst; 1422edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman } 142366f716354527c5ab4687a89a1605915e5128a106Evan Cheng 142466f716354527c5ab4687a89a1605915e5128a106Evan Cheng continue; 142566f716354527c5ab4687a89a1605915e5128a106Evan Cheng } 14267fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner 1427c498b0281fa81bc213ad1a1228664d480936c0e6Evan Cheng unsigned SubIdx = MO.getSubReg(); 142866f716354527c5ab4687a89a1605915e5128a106Evan Cheng bool DoReMat = VRM.isReMaterialized(VirtReg); 142966f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (DoReMat) 143066f716354527c5ab4687a89a1605915e5128a106Evan Cheng ReMatDefs.insert(&MI); 143166f716354527c5ab4687a89a1605915e5128a106Evan Cheng 143266f716354527c5ab4687a89a1605915e5128a106Evan Cheng // The only vregs left are stack slot definitions. 143366f716354527c5ab4687a89a1605915e5128a106Evan Cheng int StackSlot = VRM.getStackSlot(VirtReg); 143484bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner const TargetRegisterClass *RC = RegInfo->getRegClass(VirtReg); 143566f716354527c5ab4687a89a1605915e5128a106Evan Cheng 143666f716354527c5ab4687a89a1605915e5128a106Evan Cheng // If this def is part of a two-address operand, make sure to execute 143766f716354527c5ab4687a89a1605915e5128a106Evan Cheng // the store from the correct physical register. 143866f716354527c5ab4687a89a1605915e5128a106Evan Cheng unsigned PhysReg; 143966f716354527c5ab4687a89a1605915e5128a106Evan Cheng int TiedOp = MI.getInstrDescriptor()->findTiedToSrcOperand(i); 14407277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng if (TiedOp != -1) { 144166f716354527c5ab4687a89a1605915e5128a106Evan Cheng PhysReg = MI.getOperand(TiedOp).getReg(); 1442c498b0281fa81bc213ad1a1228664d480936c0e6Evan Cheng if (SubIdx) { 14437277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng unsigned SuperReg = findSuperReg(RC, PhysReg, SubIdx, MRI); 14447277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng assert(SuperReg && MRI->getSubReg(SuperReg, SubIdx) == PhysReg && 14457277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng "Can't find corresponding super-register!"); 14467277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng PhysReg = SuperReg; 14477277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng } 14487277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng } else { 144966f716354527c5ab4687a89a1605915e5128a106Evan Cheng PhysReg = VRM.getPhys(VirtReg); 145066f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (ReusedOperands.isClobbered(PhysReg)) { 145166f716354527c5ab4687a89a1605915e5128a106Evan Cheng // Another def has taken the assigned physreg. It must have been a 145266f716354527c5ab4687a89a1605915e5128a106Evan Cheng // use&def which got it due to reuse. Undo the reuse! 145366f716354527c5ab4687a89a1605915e5128a106Evan Cheng PhysReg = ReusedOperands.GetRegForReload(PhysReg, &MI, 1454549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng Spills, MaybeDeadStores, RegKills, KillOps, VRM); 1455e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng } 145666f716354527c5ab4687a89a1605915e5128a106Evan Cheng } 145784e752a8129e7a02ee6e3c6d356a8fd68fbdf698Chris Lattner 145884bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner RegInfo->setPhysRegUsed(PhysReg); 1459c498b0281fa81bc213ad1a1228664d480936c0e6Evan Cheng unsigned RReg = SubIdx ? MRI->getSubReg(PhysReg, SubIdx) : PhysReg; 14607277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng ReusedOperands.markClobbered(RReg); 14617277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng MI.getOperand(i).setReg(RReg); 14627277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng 146366f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (!MO.isDead()) { 146466f716354527c5ab4687a89a1605915e5128a106Evan Cheng MachineInstr *&LastStore = MaybeDeadStores[StackSlot]; 146535a3e4abb96a6947ec66254b72e788bacc3aadd6Evan Cheng SpillRegToStackSlot(MBB, MII, -1, PhysReg, StackSlot, RC, true, 146635a3e4abb96a6947ec66254b72e788bacc3aadd6Evan Cheng LastStore, Spills, ReMatDefs, RegKills, KillOps, VRM); 1467e4b39007c9d3056334264eba9e2e6025e241d2c5Evan Cheng NextMII = next(MII); 146866f716354527c5ab4687a89a1605915e5128a106Evan Cheng 146966f716354527c5ab4687a89a1605915e5128a106Evan Cheng // Check to see if this is a noop copy. If so, eliminate the 147066f716354527c5ab4687a89a1605915e5128a106Evan Cheng // instruction before considering the dest reg to be changed. 147166f716354527c5ab4687a89a1605915e5128a106Evan Cheng { 147266f716354527c5ab4687a89a1605915e5128a106Evan Cheng unsigned Src, Dst; 147366f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (TII->isMoveInstr(MI, Src, Dst) && Src == Dst) { 147466f716354527c5ab4687a89a1605915e5128a106Evan Cheng ++NumDCE; 147566f716354527c5ab4687a89a1605915e5128a106Evan Cheng DOUT << "Removing now-noop copy: " << MI; 147666f716354527c5ab4687a89a1605915e5128a106Evan Cheng MBB.erase(&MI); 147766f716354527c5ab4687a89a1605915e5128a106Evan Cheng Erased = true; 1478cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng VRM.RemoveMachineInstrFromMaps(&MI); 147966f716354527c5ab4687a89a1605915e5128a106Evan Cheng UpdateKills(*LastStore, RegKills, KillOps); 148066f716354527c5ab4687a89a1605915e5128a106Evan Cheng goto ProcessNextInst; 1481f50d09ad21dbb16e35460d63d23d331a2cac7a91Evan Cheng } 148266f716354527c5ab4687a89a1605915e5128a106Evan Cheng } 148366f716354527c5ab4687a89a1605915e5128a106Evan Cheng } 14848c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 1485cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner ProcessNextInst: 148635a3e4abb96a6947ec66254b72e788bacc3aadd6Evan Cheng if (!Erased && !BackTracked) { 14870c40d72b014e8c0f54552d38288a29182effba58Evan Cheng for (MachineBasicBlock::iterator II = MI; II != NextMII; ++II) 14880c40d72b014e8c0f54552d38288a29182effba58Evan Cheng UpdateKills(*II, RegKills, KillOps); 148935a3e4abb96a6947ec66254b72e788bacc3aadd6Evan Cheng } 14907fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner MII = NextMII; 14918c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 14920d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos} 14930d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 14948c4d88d3697835371ecf6823f4142af13603ad2dChris Lattnerllvm::Spiller* llvm::createSpiller() { 14958c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner switch (SpillerOpt) { 14968c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner default: assert(0 && "Unreachable!"); 14978c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner case local: 14988c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner return new LocalSpiller(); 14998c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner case simple: 15008c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner return new SimpleSpiller(); 15018c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 15020d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos} 1503