VirtRegMap.cpp revision adf85906906ebf85c57c333e8209f37ef11a6c99
134d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos//===-- llvm/CodeGen/VirtRegMap.cpp - Virtual Register Map ----------------===// 234d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// 334d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// The LLVM Compiler Infrastructure 434d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// 534d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// This file was developed by the LLVM research group and is distributed under 634d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// the University of Illinois Open Source License. See LICENSE.TXT for details. 734d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// 834d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos//===----------------------------------------------------------------------===// 934d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// 108c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner// This file implements the VirtRegMap class. 118c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner// 128c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner// It also contains implementations of the the Spiller interface, which, given a 138c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner// virtual register map and a machine function, eliminates all virtual 148c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner// references by replacing them with physical register references - adding spill 150d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos// code as necessary. 1634d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// 1734d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos//===----------------------------------------------------------------------===// 1834d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos 198c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner#define DEBUG_TYPE "spiller" 2034d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos#include "VirtRegMap.h" 210d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos#include "llvm/Function.h" 2234d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos#include "llvm/CodeGen/MachineFrameInfo.h" 238c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner#include "llvm/CodeGen/MachineFunction.h" 248c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner#include "llvm/CodeGen/SSARegMap.h" 2534d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos#include "llvm/Target/TargetMachine.h" 260d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos#include "llvm/Target/TargetInstrInfo.h" 27551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 28551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 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), 67adf85906906ebf85c57c333e8209f37ef11a6c99Evan Cheng Virt2SplitKillMap(NULL), ReMatMap(NULL), ReMatId(MAX_STACK_SLOT+1) { 682926869b4a083fc951484de03a9867eabf81e880Chris Lattner grow(); 692926869b4a083fc951484de03a9867eabf81e880Chris Lattner} 702926869b4a083fc951484de03a9867eabf81e880Chris Lattner 718c4d88d3697835371ecf6823f4142af13603ad2dChris Lattnervoid VirtRegMap::grow() { 72549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng unsigned LastVirtReg = MF.getSSARegMap()->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"); 857f690e625807b9320bf4ae437b8f35258acc99deChris Lattner const TargetRegisterClass* RC = MF.getSSARegMap()->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, 1427f690e625807b9320bf4ae437b8f35258acc99deChris Lattner e = MF.getSSARegMap()->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, 1497f690e625807b9320bf4ae437b8f35258acc99deChris Lattner e = MF.getSSARegMap()->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(); 176b0f31bf19b9cd0107900728123d4848eae462e6cChris Lattner const MRegisterInfo &MRI = *TM.getRegisterInfo(); 1778c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 1784ea1b828ebc5d2e8711acf13c2a3fdd7c14fe339Chris Lattner // LoadedRegs - Keep track of which vregs are loaded, so that we only load 1794ea1b828ebc5d2e8711acf13c2a3fdd7c14fe339Chris Lattner // each vreg once (in the case where a spilled vreg is used by multiple 1804ea1b828ebc5d2e8711acf13c2a3fdd7c14fe339Chris Lattner // operands). This is always smaller than the number of operands to the 1814ea1b828ebc5d2e8711acf13c2a3fdd7c14fe339Chris Lattner // current machine instr, so it should be small. 1824ea1b828ebc5d2e8711acf13c2a3fdd7c14fe339Chris Lattner std::vector<unsigned> LoadedRegs; 1838c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 1840fc27ccdd374799c8d65b61e89db53ba1ea47358Chris Lattner for (MachineFunction::iterator MBBI = MF.begin(), E = MF.end(); 1850fc27ccdd374799c8d65b61e89db53ba1ea47358Chris Lattner MBBI != E; ++MBBI) { 186b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling DOUT << MBBI->getBasicBlock()->getName() << ":\n"; 1870fc27ccdd374799c8d65b61e89db53ba1ea47358Chris Lattner MachineBasicBlock &MBB = *MBBI; 1880fc27ccdd374799c8d65b61e89db53ba1ea47358Chris Lattner for (MachineBasicBlock::iterator MII = MBB.begin(), 1890fc27ccdd374799c8d65b61e89db53ba1ea47358Chris Lattner E = MBB.end(); MII != E; ++MII) { 1900fc27ccdd374799c8d65b61e89db53ba1ea47358Chris Lattner MachineInstr &MI = *MII; 1910fc27ccdd374799c8d65b61e89db53ba1ea47358Chris Lattner for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 1927fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner MachineOperand &MO = MI.getOperand(i); 193886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner if (MO.isRegister() && MO.getReg()) 194886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner if (MRegisterInfo::isVirtualRegister(MO.getReg())) { 195886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner unsigned VirtReg = MO.getReg(); 196886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner unsigned PhysReg = VRM.getPhys(VirtReg); 197549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng if (!VRM.isAssignedReg(VirtReg)) { 198886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner int StackSlot = VRM.getStackSlot(VirtReg); 199bf9716b9c48d3b0370c715cd79540945f73dc296Chris Lattner const TargetRegisterClass* RC = 200bf9716b9c48d3b0370c715cd79540945f73dc296Chris Lattner MF.getSSARegMap()->getRegClass(VirtReg); 201edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 202886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner if (MO.isUse() && 203886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner std::find(LoadedRegs.begin(), LoadedRegs.end(), VirtReg) 204886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner == LoadedRegs.end()) { 205bf9716b9c48d3b0370c715cd79540945f73dc296Chris Lattner MRI.loadRegFromStackSlot(MBB, &MI, PhysReg, StackSlot, RC); 206886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner LoadedRegs.push_back(VirtReg); 207886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner ++NumLoads; 208b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling DOUT << '\t' << *prior(MII); 209886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner } 210edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 211886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner if (MO.isDef()) { 212d64b5c82b97ad1b74eb9fd2f23257a7899b0c307Evan Cheng MRI.storeRegToStackSlot(MBB, next(MII), PhysReg, true, 213d64b5c82b97ad1b74eb9fd2f23257a7899b0c307Evan Cheng StackSlot, RC); 214886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner ++NumStores; 215886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner } 2160fc27ccdd374799c8d65b61e89db53ba1ea47358Chris Lattner } 2176c087e5585b227f3c1d8278304c7cfbc7cd4f6e8Evan Cheng MF.setPhysRegUsed(PhysReg); 218e53f4a055f74bded20d6129b4724ddd17fd199f6Chris Lattner MI.getOperand(i).setReg(PhysReg); 219886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner } else { 2206c087e5585b227f3c1d8278304c7cfbc7cd4f6e8Evan Cheng MF.setPhysRegUsed(MO.getReg()); 2218c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 2228c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 223886dd9136f4c5b4523a0958e726955272eb9dfb2Chris Lattner 224b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling DOUT << '\t' << MI; 2254ea1b828ebc5d2e8711acf13c2a3fdd7c14fe339Chris Lattner LoadedRegs.clear(); 2268c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 2278c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 2288c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner return true; 2298c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner} 2300d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 2318c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner//===----------------------------------------------------------------------===// 2328c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner// Local Spiller Implementation 2338c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner//===----------------------------------------------------------------------===// 2340d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 2358c4d88d3697835371ecf6823f4142af13603ad2dChris Lattnernamespace { 23666f716354527c5ab4687a89a1605915e5128a106Evan Cheng class AvailableSpills; 23766f716354527c5ab4687a89a1605915e5128a106Evan Cheng 2387fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner /// LocalSpiller - This spiller does a simple pass over the machine basic 2397fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner /// block to attempt to keep spills in registers as much as possible for 2407fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner /// blocks that have low register pressure (the vreg may be spilled due to 2417fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner /// register pressure in other blocks). 242f8c68f694c25b1ae8c0e5adb2a19432cb405d232Chris Lattner class VISIBILITY_HIDDEN LocalSpiller : public Spiller { 24332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng SSARegMap *RegMap; 2448c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner const MRegisterInfo *MRI; 2457fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner const TargetInstrInfo *TII; 2468c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner public: 24735f2705e3de4600c3621b883eed9b22e4607ddf4Chris Lattner bool runOnMachineFunction(MachineFunction &MF, VirtRegMap &VRM) { 24832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng RegMap = MF.getSSARegMap(); 2497fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner MRI = MF.getTarget().getRegisterInfo(); 2507fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner TII = MF.getTarget().getInstrInfo(); 251b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling DOUT << "\n**** Local spiller rewriting function '" 252b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling << MF.getFunction()->getName() << "':\n"; 25304fa32f9aa19bae12e7fd5b5564cebc345de3c58David Greene DOUT << "**** Machine Instrs (NOTE! Does not include spills and reloads!) ****\n"; 25404fa32f9aa19bae12e7fd5b5564cebc345de3c58David Greene DEBUG(MF.dump()); 2557fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner 2567fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner for (MachineFunction::iterator MBB = MF.begin(), E = MF.end(); 2577fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner MBB != E; ++MBB) 258549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng RewriteMBB(*MBB, VRM); 25904fa32f9aa19bae12e7fd5b5564cebc345de3c58David Greene 26004fa32f9aa19bae12e7fd5b5564cebc345de3c58David Greene DOUT << "**** Post Machine Instrs ****\n"; 26104fa32f9aa19bae12e7fd5b5564cebc345de3c58David Greene DEBUG(MF.dump()); 26204fa32f9aa19bae12e7fd5b5564cebc345de3c58David Greene 2637fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner return true; 2648c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 2657fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner private: 26666f716354527c5ab4687a89a1605915e5128a106Evan Cheng bool PrepForUnfoldOpti(MachineBasicBlock &MBB, 26766f716354527c5ab4687a89a1605915e5128a106Evan Cheng MachineBasicBlock::iterator &MII, 26866f716354527c5ab4687a89a1605915e5128a106Evan Cheng std::vector<MachineInstr*> &MaybeDeadStores, 26966f716354527c5ab4687a89a1605915e5128a106Evan Cheng AvailableSpills &Spills, BitVector &RegKills, 27066f716354527c5ab4687a89a1605915e5128a106Evan Cheng std::vector<MachineOperand*> &KillOps, 27166f716354527c5ab4687a89a1605915e5128a106Evan Cheng VirtRegMap &VRM); 27281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng void SpillRegToStackSlot(MachineBasicBlock &MBB, 27381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineBasicBlock::iterator &MII, 27481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng int Idx, unsigned PhysReg, int StackSlot, 27581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng const TargetRegisterClass *RC, 27635a3e4abb96a6947ec66254b72e788bacc3aadd6Evan Cheng bool isAvailable, MachineInstr *&LastStore, 27781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng AvailableSpills &Spills, 27881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng SmallSet<MachineInstr*, 4> &ReMatDefs, 27981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector &RegKills, 28081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng std::vector<MachineOperand*> &KillOps, 281e4b39007c9d3056334264eba9e2e6025e241d2c5Evan Cheng VirtRegMap &VRM); 282549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng void RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM); 2838c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner }; 2848c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner} 2858c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 28666cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner/// AvailableSpills - As the local spiller is scanning and rewriting an MBB from 287549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng/// top down, keep track of which spills slots or remat are available in each 288549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng/// register. 289593c95878b089388f9c82b8c7b1f4731af86c792Chris Lattner/// 290593c95878b089388f9c82b8c7b1f4731af86c792Chris Lattner/// Note that not all physregs are created equal here. In particular, some 291593c95878b089388f9c82b8c7b1f4731af86c792Chris Lattner/// physregs are reloads that we are allowed to clobber or ignore at any time. 292593c95878b089388f9c82b8c7b1f4731af86c792Chris Lattner/// Other physregs are values that the register allocated program is using that 293593c95878b089388f9c82b8c7b1f4731af86c792Chris Lattner/// we cannot CHANGE, but we can read if we like. We keep track of this on a 294549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng/// per-stack-slot / remat id basis as the low bit in the value of the 295549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng/// SpillSlotsAvailable entries. The predicate 'canClobberPhysReg()' checks 296549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng/// this bit and addAvailable sets it if. 297f8c68f694c25b1ae8c0e5adb2a19432cb405d232Chris Lattnernamespace { 298f8c68f694c25b1ae8c0e5adb2a19432cb405d232Chris Lattnerclass VISIBILITY_HIDDEN AvailableSpills { 29966cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner const MRegisterInfo *MRI; 30066cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner const TargetInstrInfo *TII; 30166cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner 302549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // SpillSlotsOrReMatsAvailable - This map keeps track of all of the spilled 303549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // or remat'ed virtual register values that are still available, due to being 304549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // loaded or stored to, but not invalidated yet. 305549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng std::map<int, unsigned> SpillSlotsOrReMatsAvailable; 30666cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner 307549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // PhysRegsAvailable - This is the inverse of SpillSlotsOrReMatsAvailable, 308549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // indicating which stack slot values are currently held by a physreg. This 309549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // is used to invalidate entries in SpillSlotsOrReMatsAvailable when a 310549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // physreg is modified. 31166cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner std::multimap<unsigned, int> PhysRegsAvailable; 31266cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner 3137a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng void disallowClobberPhysRegOnly(unsigned PhysReg); 3147a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng 31566cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner void ClobberPhysRegOnly(unsigned PhysReg); 31666cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattnerpublic: 31766cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner AvailableSpills(const MRegisterInfo *mri, const TargetInstrInfo *tii) 31866cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner : MRI(mri), TII(tii) { 31966cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner } 32066cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner 32191e2390818080ae2b059e3ff850a9455858e4f7bEvan Cheng const MRegisterInfo *getRegInfo() const { return MRI; } 32291e2390818080ae2b059e3ff850a9455858e4f7bEvan Cheng 323549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng /// getSpillSlotOrReMatPhysReg - If the specified stack slot or remat is 324549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng /// available in a physical register, return that PhysReg, otherwise 325549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng /// return 0. 326549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng unsigned getSpillSlotOrReMatPhysReg(int Slot) const { 327549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng std::map<int, unsigned>::const_iterator I = 328549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng SpillSlotsOrReMatsAvailable.find(Slot); 329549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng if (I != SpillSlotsOrReMatsAvailable.end()) { 330b9591c667d956d0607f7388665649fb0852a988cEvan Cheng return I->second >> 1; // Remove the CanClobber bit. 33191e2390818080ae2b059e3ff850a9455858e4f7bEvan Cheng } 33266cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner return 0; 33366cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner } 334de4e942faa12a52242915e3334c25f19687f36e2Evan Cheng 335549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng /// addAvailable - Mark that the specified stack slot / remat is available in 336549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng /// the specified physreg. If CanClobber is true, the physreg can be modified 337549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng /// at any time without changing the semantics of the program. 338549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng void addAvailable(int SlotOrReMat, MachineInstr *MI, unsigned Reg, 33991e2390818080ae2b059e3ff850a9455858e4f7bEvan Cheng bool CanClobber = true) { 3408666249ad6eca27d267f251495545bca132a9a5cChris Lattner // If this stack slot is thought to be available in some other physreg, 3418666249ad6eca27d267f251495545bca132a9a5cChris Lattner // remove its record. 342549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng ModifyStackSlotOrReMat(SlotOrReMat); 3438666249ad6eca27d267f251495545bca132a9a5cChris Lattner 344549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng PhysRegsAvailable.insert(std::make_pair(Reg, SlotOrReMat)); 34590a43c3ae385d98d19f9c858b51920552fb9ceaaEvan Cheng SpillSlotsOrReMatsAvailable[SlotOrReMat]= (Reg << 1) | (unsigned)CanClobber; 34666cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner 347549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng if (SlotOrReMat > VirtRegMap::MAX_STACK_SLOT) 348549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng DOUT << "Remembering RM#" << SlotOrReMat-VirtRegMap::MAX_STACK_SLOT-1; 3492638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng else 350549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng DOUT << "Remembering SS#" << SlotOrReMat; 3512638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng DOUT << " in physreg " << MRI->getName(Reg) << "\n"; 35266cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner } 3537a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng 354593c95878b089388f9c82b8c7b1f4731af86c792Chris Lattner /// canClobberPhysReg - Return true if the spiller is allowed to change the 355593c95878b089388f9c82b8c7b1f4731af86c792Chris Lattner /// value of the specified stackslot register if it desires. The specified 356593c95878b089388f9c82b8c7b1f4731af86c792Chris Lattner /// stack slot must be available in a physreg for this query to make sense. 357549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng bool canClobberPhysReg(int SlotOrReMat) const { 35890a43c3ae385d98d19f9c858b51920552fb9ceaaEvan Cheng assert(SpillSlotsOrReMatsAvailable.count(SlotOrReMat) && 35990a43c3ae385d98d19f9c858b51920552fb9ceaaEvan Cheng "Value not available!"); 360549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng return SpillSlotsOrReMatsAvailable.find(SlotOrReMat)->second & 1; 361593c95878b089388f9c82b8c7b1f4731af86c792Chris Lattner } 36235a3e4abb96a6947ec66254b72e788bacc3aadd6Evan Cheng 3637a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng /// disallowClobberPhysReg - Unset the CanClobber bit of the specified 3647a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng /// stackslot register. The register is still available but is no longer 3657a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng /// allowed to be modifed. 3667a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng void disallowClobberPhysReg(unsigned PhysReg); 3677a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng 36866cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner /// ClobberPhysReg - This is called when the specified physreg changes 36966f716354527c5ab4687a89a1605915e5128a106Evan Cheng /// value. We use this to invalidate any info about stuff that lives in 37066cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner /// it and any of its aliases. 37166cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner void ClobberPhysReg(unsigned PhysReg); 37266cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner 37390a43c3ae385d98d19f9c858b51920552fb9ceaaEvan Cheng /// ModifyStackSlotOrReMat - This method is called when the value in a stack 37490a43c3ae385d98d19f9c858b51920552fb9ceaaEvan Cheng /// slot changes. This removes information about which register the previous 37590a43c3ae385d98d19f9c858b51920552fb9ceaaEvan Cheng /// value for this slot lives in (as the previous value is dead now). 376549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng void ModifyStackSlotOrReMat(int SlotOrReMat); 37766cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner}; 378f8c68f694c25b1ae8c0e5adb2a19432cb405d232Chris Lattner} 37966cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner 3807a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng/// disallowClobberPhysRegOnly - Unset the CanClobber bit of the specified 3817a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng/// stackslot register. The register is still available but is no longer 3827a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng/// allowed to be modifed. 3837a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Chengvoid AvailableSpills::disallowClobberPhysRegOnly(unsigned PhysReg) { 3847a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng std::multimap<unsigned, int>::iterator I = 3857a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng PhysRegsAvailable.lower_bound(PhysReg); 3867a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng while (I != PhysRegsAvailable.end() && I->first == PhysReg) { 387549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng int SlotOrReMat = I->second; 3887a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng I++; 389549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng assert((SpillSlotsOrReMatsAvailable[SlotOrReMat] >> 1) == PhysReg && 3907a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng "Bidirectional map mismatch!"); 391549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng SpillSlotsOrReMatsAvailable[SlotOrReMat] &= ~1; 3927a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng DOUT << "PhysReg " << MRI->getName(PhysReg) 3937a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng << " copied, it is available for use but can no longer be modified\n"; 3947a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng } 3957a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng} 3967a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng 3977a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng/// disallowClobberPhysReg - Unset the CanClobber bit of the specified 3987a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng/// stackslot register and its aliases. The register and its aliases may 3997a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng/// still available but is no longer allowed to be modifed. 4007a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Chengvoid AvailableSpills::disallowClobberPhysReg(unsigned PhysReg) { 4017a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng for (const unsigned *AS = MRI->getAliasSet(PhysReg); *AS; ++AS) 4027a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng disallowClobberPhysRegOnly(*AS); 4037a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng disallowClobberPhysRegOnly(PhysReg); 4047a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng} 4057a0d51c8e3d6cdc6d961f6525f97f8926fb76c83Evan Cheng 40666cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner/// ClobberPhysRegOnly - This is called when the specified physreg changes 40766cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner/// value. We use this to invalidate any info about stuff we thing lives in it. 40866cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattnervoid AvailableSpills::ClobberPhysRegOnly(unsigned PhysReg) { 40966cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner std::multimap<unsigned, int>::iterator I = 41066cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner PhysRegsAvailable.lower_bound(PhysReg); 41107cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner while (I != PhysRegsAvailable.end() && I->first == PhysReg) { 412549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng int SlotOrReMat = I->second; 41307cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner PhysRegsAvailable.erase(I++); 414549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng assert((SpillSlotsOrReMatsAvailable[SlotOrReMat] >> 1) == PhysReg && 41566cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner "Bidirectional map mismatch!"); 416549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng SpillSlotsOrReMatsAvailable.erase(SlotOrReMat); 417b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling DOUT << "PhysReg " << MRI->getName(PhysReg) 4182638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng << " clobbered, invalidating "; 419549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng if (SlotOrReMat > VirtRegMap::MAX_STACK_SLOT) 420549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng DOUT << "RM#" << SlotOrReMat-VirtRegMap::MAX_STACK_SLOT-1 << "\n"; 4212638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng else 422549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng DOUT << "SS#" << SlotOrReMat << "\n"; 4238c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 4248c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner} 4250d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 42666cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner/// ClobberPhysReg - This is called when the specified physreg changes 42766cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner/// value. We use this to invalidate any info about stuff we thing lives in 42866cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner/// it and any of its aliases. 42966cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattnervoid AvailableSpills::ClobberPhysReg(unsigned PhysReg) { 4307fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner for (const unsigned *AS = MRI->getAliasSet(PhysReg); *AS; ++AS) 43166cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner ClobberPhysRegOnly(*AS); 43266cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner ClobberPhysRegOnly(PhysReg); 43307cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner} 43407cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner 43590a43c3ae385d98d19f9c858b51920552fb9ceaaEvan Cheng/// ModifyStackSlotOrReMat - This method is called when the value in a stack 43690a43c3ae385d98d19f9c858b51920552fb9ceaaEvan Cheng/// slot changes. This removes information about which register the previous 43790a43c3ae385d98d19f9c858b51920552fb9ceaaEvan Cheng/// value for this slot lives in (as the previous value is dead now). 438549f27d3070195d6647b796841a5291b4549e8e0Evan Chengvoid AvailableSpills::ModifyStackSlotOrReMat(int SlotOrReMat) { 43990a43c3ae385d98d19f9c858b51920552fb9ceaaEvan Cheng std::map<int, unsigned>::iterator It = 44090a43c3ae385d98d19f9c858b51920552fb9ceaaEvan Cheng SpillSlotsOrReMatsAvailable.find(SlotOrReMat); 441549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng if (It == SpillSlotsOrReMatsAvailable.end()) return; 442b9591c667d956d0607f7388665649fb0852a988cEvan Cheng unsigned Reg = It->second >> 1; 443549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng SpillSlotsOrReMatsAvailable.erase(It); 44407cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner 44507cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner // This register may hold the value of multiple stack slots, only remove this 44607cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner // stack slot from the set of values the register contains. 44707cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner std::multimap<unsigned, int>::iterator I = PhysRegsAvailable.lower_bound(Reg); 44807cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner for (; ; ++I) { 44907cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner assert(I != PhysRegsAvailable.end() && I->first == Reg && 45007cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner "Map inverse broken!"); 451549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng if (I->second == SlotOrReMat) break; 45207cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner } 45307cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner PhysRegsAvailable.erase(I); 4548c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner} 4558c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 4568c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 45707cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner 45828bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng/// InvalidateKills - MI is going to be deleted. If any of its operands are 45928bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng/// marked kill, then invalidate the information. 46028bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Chengstatic void InvalidateKills(MachineInstr &MI, BitVector &RegKills, 461c91f0b80687f0a6fafa5a5e6cd87498e2de6fc3eEvan Cheng std::vector<MachineOperand*> &KillOps, 46266f716354527c5ab4687a89a1605915e5128a106Evan Cheng SmallVector<unsigned, 2> *KillRegs = NULL) { 46328bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 46428bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng MachineOperand &MO = MI.getOperand(i); 46592dfe2001e96f6e2b6d327e8816f38033f88b295Dan Gohman if (!MO.isRegister() || !MO.isUse() || !MO.isKill()) 46628bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng continue; 46728bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng unsigned Reg = MO.getReg(); 468b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng if (KillRegs) 469b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng KillRegs->push_back(Reg); 47028bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng if (KillOps[Reg] == &MO) { 47128bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng RegKills.reset(Reg); 47228bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng KillOps[Reg] = NULL; 47328bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng } 47428bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng } 47528bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng} 47628bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng 477b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng/// InvalidateRegDef - If the def operand of the specified def MI is now dead 478b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng/// (since it's spill instruction is removed), mark it isDead. Also checks if 479b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng/// the def MI has other definition operands that are not dead. Returns it by 480b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng/// reference. 481b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Chengstatic bool InvalidateRegDef(MachineBasicBlock::iterator I, 482b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng MachineInstr &NewDef, unsigned Reg, 483b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng bool &HasLiveDef) { 484b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng // Due to remat, it's possible this reg isn't being reused. That is, 485b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng // the def of this reg (by prev MI) is now dead. 486b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng MachineInstr *DefMI = I; 487b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng MachineOperand *DefOp = NULL; 488b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng for (unsigned i = 0, e = DefMI->getNumOperands(); i != e; ++i) { 489b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng MachineOperand &MO = DefMI->getOperand(i); 49092dfe2001e96f6e2b6d327e8816f38033f88b295Dan Gohman if (MO.isRegister() && MO.isDef()) { 491b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng if (MO.getReg() == Reg) 492b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng DefOp = &MO; 493b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng else if (!MO.isDead()) 494b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng HasLiveDef = true; 495b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng } 496b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng } 497b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng if (!DefOp) 498b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng return false; 499b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng 500b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng bool FoundUse = false, Done = false; 501b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng MachineBasicBlock::iterator E = NewDef; 502b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng ++I; ++E; 503b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng for (; !Done && I != E; ++I) { 504b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng MachineInstr *NMI = I; 505b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng for (unsigned j = 0, ee = NMI->getNumOperands(); j != ee; ++j) { 506b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng MachineOperand &MO = NMI->getOperand(j); 50792dfe2001e96f6e2b6d327e8816f38033f88b295Dan Gohman if (!MO.isRegister() || MO.getReg() != Reg) 508b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng continue; 509b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng if (MO.isUse()) 510b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng FoundUse = true; 511b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng Done = true; // Stop after scanning all the operands of this MI. 512b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng } 513b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng } 514b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng if (!FoundUse) { 515b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng // Def is dead! 516b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng DefOp->setIsDead(); 517b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng return true; 518b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng } 519b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng return false; 520b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng} 521b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng 52228bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng/// UpdateKills - Track and update kill info. If a MI reads a register that is 52328bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng/// marked kill, then it must be due to register reuse. Transfer the kill info 52428bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng/// over. 52528bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Chengstatic void UpdateKills(MachineInstr &MI, BitVector &RegKills, 52628bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng std::vector<MachineOperand*> &KillOps) { 52728bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng const TargetInstrDescriptor *TID = MI.getInstrDescriptor(); 52828bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 52928bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng MachineOperand &MO = MI.getOperand(i); 53092dfe2001e96f6e2b6d327e8816f38033f88b295Dan Gohman if (!MO.isRegister() || !MO.isUse()) 53128bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng continue; 53228bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng unsigned Reg = MO.getReg(); 53328bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng if (Reg == 0) 53428bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng continue; 53528bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng 53628bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng if (RegKills[Reg]) { 53728bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng // That can't be right. Register is killed but not re-defined and it's 53828bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng // being reused. Let's fix that. 53928bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng KillOps[Reg]->unsetIsKill(); 54028bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng if (i < TID->numOperands && 54128bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng TID->getOperandConstraint(i, TOI::TIED_TO) == -1) 54228bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng // Unless it's a two-address operand, this is the new kill. 54328bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng MO.setIsKill(); 54428bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng } 54528bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng 54628bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng if (MO.isKill()) { 54728bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng RegKills.set(Reg); 54828bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng KillOps[Reg] = &MO; 54928bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng } 55028bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng } 55128bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng 55228bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 55328bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng const MachineOperand &MO = MI.getOperand(i); 55492dfe2001e96f6e2b6d327e8816f38033f88b295Dan Gohman if (!MO.isRegister() || !MO.isDef()) 55528bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng continue; 55628bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng unsigned Reg = MO.getReg(); 55728bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng RegKills.reset(Reg); 55828bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng KillOps[Reg] = NULL; 55928bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng } 56028bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng} 56128bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng 56228bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng 5637fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner// ReusedOp - For each reused operand, we keep track of a bit of information, in 5647fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner// case we need to rollback upon processing a new operand. See comments below. 5657fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattnernamespace { 5667fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner struct ReusedOp { 5677fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner // The MachineInstr operand that reused an available value. 5687fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner unsigned Operand; 569edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 570549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // StackSlotOrReMat - The spill slot or remat id of the value being reused. 571549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng unsigned StackSlotOrReMat; 572edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 5737fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner // PhysRegReused - The physical register the value was available in. 5747fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner unsigned PhysRegReused; 575edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 5767fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner // AssignedPhysReg - The physreg that was assigned for use by the reload. 5777fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner unsigned AssignedPhysReg; 5788a61a7524af19d67bd11f8e7d868ca75efbf5c91Chris Lattner 5798a61a7524af19d67bd11f8e7d868ca75efbf5c91Chris Lattner // VirtReg - The virtual register itself. 5808a61a7524af19d67bd11f8e7d868ca75efbf5c91Chris Lattner unsigned VirtReg; 5818a61a7524af19d67bd11f8e7d868ca75efbf5c91Chris Lattner 5828a61a7524af19d67bd11f8e7d868ca75efbf5c91Chris Lattner ReusedOp(unsigned o, unsigned ss, unsigned prr, unsigned apr, 5838a61a7524af19d67bd11f8e7d868ca75efbf5c91Chris Lattner unsigned vreg) 58490a43c3ae385d98d19f9c858b51920552fb9ceaaEvan Cheng : Operand(o), StackSlotOrReMat(ss), PhysRegReused(prr), 58590a43c3ae385d98d19f9c858b51920552fb9ceaaEvan Cheng AssignedPhysReg(apr), VirtReg(vreg) {} 5867fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner }; 587540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner 588540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner /// ReuseInfo - This maintains a collection of ReuseOp's for each operand that 589540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner /// is reused instead of reloaded. 590f8c68f694c25b1ae8c0e5adb2a19432cb405d232Chris Lattner class VISIBILITY_HIDDEN ReuseInfo { 591540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner MachineInstr &MI; 592540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner std::vector<ReusedOp> Reuses; 593957840b3e14938fc86c306fda99ac039d1777a4cEvan Cheng BitVector PhysRegsClobbered; 594540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner public: 595e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng ReuseInfo(MachineInstr &mi, const MRegisterInfo *mri) : MI(mi) { 596957840b3e14938fc86c306fda99ac039d1777a4cEvan Cheng PhysRegsClobbered.resize(mri->getNumRegs()); 597e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng } 598540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner 599540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner bool hasReuses() const { 600540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner return !Reuses.empty(); 601540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner } 602540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner 603540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner /// addReuse - If we choose to reuse a virtual register that is already 604540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner /// available instead of reloading it, remember that we did so. 605549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng void addReuse(unsigned OpNo, unsigned StackSlotOrReMat, 606540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner unsigned PhysRegReused, unsigned AssignedPhysReg, 607540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner unsigned VirtReg) { 608540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner // If the reload is to the assigned register anyway, no undo will be 609540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner // required. 610540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner if (PhysRegReused == AssignedPhysReg) return; 611540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner 612540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner // Otherwise, remember this. 613549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng Reuses.push_back(ReusedOp(OpNo, StackSlotOrReMat, PhysRegReused, 614540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner AssignedPhysReg, VirtReg)); 615540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner } 616e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng 617e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng void markClobbered(unsigned PhysReg) { 618957840b3e14938fc86c306fda99ac039d1777a4cEvan Cheng PhysRegsClobbered.set(PhysReg); 619e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng } 620e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng 621e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng bool isClobbered(unsigned PhysReg) const { 622957840b3e14938fc86c306fda99ac039d1777a4cEvan Cheng return PhysRegsClobbered.test(PhysReg); 623e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng } 624540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner 625540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner /// GetRegForReload - We are about to emit a reload into PhysReg. If there 626540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner /// is some other operand that is using the specified register, either pick 627540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner /// a new register to use, or evict the previous reload and use this reg. 628540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner unsigned GetRegForReload(unsigned PhysReg, MachineInstr *MI, 629540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner AvailableSpills &Spills, 630fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng std::vector<MachineInstr*> &MaybeDeadStores, 63128bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng SmallSet<unsigned, 8> &Rejected, 63228bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng BitVector &RegKills, 633549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng std::vector<MachineOperand*> &KillOps, 634549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng VirtRegMap &VRM) { 635540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner if (Reuses.empty()) return PhysReg; // This is most often empty. 636540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner 637540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner for (unsigned ro = 0, e = Reuses.size(); ro != e; ++ro) { 638540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner ReusedOp &Op = Reuses[ro]; 639540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner // If we find some other reuse that was supposed to use this register 640540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner // exactly for its reload, we can change this reload to use ITS reload 6413c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng // register. That is, unless its reload register has already been 6423c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng // considered and subsequently rejected because it has also been reused 6433c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng // by another operand. 6443c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng if (Op.PhysRegReused == PhysReg && 6453c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng Rejected.count(Op.AssignedPhysReg) == 0) { 646540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner // Yup, use the reload register that we didn't use before. 6473c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng unsigned NewReg = Op.AssignedPhysReg; 6483c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng Rejected.insert(PhysReg); 64928bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng return GetRegForReload(NewReg, MI, Spills, MaybeDeadStores, Rejected, 650549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng RegKills, KillOps, VRM); 651540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner } else { 652540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner // Otherwise, we might also have a problem if a previously reused 653540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner // value aliases the new register. If so, codegen the previous reload 654540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner // and use this one. 655540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner unsigned PRRU = Op.PhysRegReused; 656540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner const MRegisterInfo *MRI = Spills.getRegInfo(); 657540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner if (MRI->areAliases(PRRU, PhysReg)) { 658540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner // Okay, we found out that an alias of a reused register 659540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner // was used. This isn't good because it means we have 660540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner // to undo a previous reuse. 661540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner MachineBasicBlock *MBB = MI->getParent(); 662540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner const TargetRegisterClass *AliasRC = 66328bad084118a9746df95084364d7d95de00c3b67Chris Lattner MBB->getParent()->getSSARegMap()->getRegClass(Op.VirtReg); 66428bad084118a9746df95084364d7d95de00c3b67Chris Lattner 66528bad084118a9746df95084364d7d95de00c3b67Chris Lattner // Copy Op out of the vector and remove it, we're going to insert an 66628bad084118a9746df95084364d7d95de00c3b67Chris Lattner // explicit load for it. 66728bad084118a9746df95084364d7d95de00c3b67Chris Lattner ReusedOp NewOp = Op; 66828bad084118a9746df95084364d7d95de00c3b67Chris Lattner Reuses.erase(Reuses.begin()+ro); 66928bad084118a9746df95084364d7d95de00c3b67Chris Lattner 67028bad084118a9746df95084364d7d95de00c3b67Chris Lattner // Ok, we're going to try to reload the assigned physreg into the 67128bad084118a9746df95084364d7d95de00c3b67Chris Lattner // slot that we were supposed to in the first place. However, that 67228bad084118a9746df95084364d7d95de00c3b67Chris Lattner // register could hold a reuse. Check to see if it conflicts or 67328bad084118a9746df95084364d7d95de00c3b67Chris Lattner // would prefer us to use a different register. 67428bad084118a9746df95084364d7d95de00c3b67Chris Lattner unsigned NewPhysReg = GetRegForReload(NewOp.AssignedPhysReg, 67528bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng MI, Spills, MaybeDeadStores, 676549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng Rejected, RegKills, KillOps, VRM); 67728bad084118a9746df95084364d7d95de00c3b67Chris Lattner 678549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng if (NewOp.StackSlotOrReMat > VirtRegMap::MAX_STACK_SLOT) { 679549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng MRI->reMaterialize(*MBB, MI, NewPhysReg, 680549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng VRM.getReMaterializedMI(NewOp.VirtReg)); 681549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng ++NumReMats; 682549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng } else { 683549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng MRI->loadRegFromStackSlot(*MBB, MI, NewPhysReg, 684549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng NewOp.StackSlotOrReMat, AliasRC); 685fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng // Any stores to this stack slot are not dead anymore. 686fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng MaybeDeadStores[NewOp.StackSlotOrReMat] = NULL; 687549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng ++NumLoads; 688549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng } 68928bad084118a9746df95084364d7d95de00c3b67Chris Lattner Spills.ClobberPhysReg(NewPhysReg); 69028bad084118a9746df95084364d7d95de00c3b67Chris Lattner Spills.ClobberPhysReg(NewOp.PhysRegReused); 691540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner 692e53f4a055f74bded20d6129b4724ddd17fd199f6Chris Lattner MI->getOperand(NewOp.Operand).setReg(NewPhysReg); 693540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner 694549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng Spills.addAvailable(NewOp.StackSlotOrReMat, MI, NewPhysReg); 69528bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng MachineBasicBlock::iterator MII = MI; 69628bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng --MII; 69728bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng UpdateKills(*MII, RegKills, KillOps); 69828bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng DOUT << '\t' << *MII; 699540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner 700b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling DOUT << "Reuse undone!\n"; 701540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner --NumReused; 70228bad084118a9746df95084364d7d95de00c3b67Chris Lattner 70328bad084118a9746df95084364d7d95de00c3b67Chris Lattner // Finally, PhysReg is now available, go ahead and use it. 704540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner return PhysReg; 705540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner } 706540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner } 707540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner } 708540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner return PhysReg; 709540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner } 7103c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng 7113c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng /// GetRegForReload - Helper for the above GetRegForReload(). Add a 7123c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng /// 'Rejected' set to remember which registers have been considered and 7133c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng /// rejected for the reload. This avoids infinite looping in case like 7143c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng /// this: 7153c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng /// t1 := op t2, t3 7163c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng /// t2 <- assigned r0 for use by the reload but ended up reuse r1 7173c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng /// t3 <- assigned r1 for use by the reload but ended up reuse r0 7183c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng /// t1 <- desires r1 7193c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng /// sees r1 is taken by t2, tries t2's reload register r0 7203c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng /// sees r0 is taken by t3, tries t3's reload register r1 7213c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng /// sees r1 is taken by t2, tries t2's reload register r0 ... 7223c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng unsigned GetRegForReload(unsigned PhysReg, MachineInstr *MI, 7233c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng AvailableSpills &Spills, 724fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng std::vector<MachineInstr*> &MaybeDeadStores, 72528bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng BitVector &RegKills, 726549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng std::vector<MachineOperand*> &KillOps, 727549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng VirtRegMap &VRM) { 72808a4d5a343e886816b31a78d9b7e70240d9c67beChris Lattner SmallSet<unsigned, 8> Rejected; 72928bb462d4cfb8c849a0d9a1b1f3c643b77b8efc6Evan Cheng return GetRegForReload(PhysReg, MI, Spills, MaybeDeadStores, Rejected, 730549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng RegKills, KillOps, VRM); 7313c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng } 732540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner }; 7337fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner} 7347fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner 73566f716354527c5ab4687a89a1605915e5128a106Evan Cheng/// PrepForUnfoldOpti - Turn a store folding instruction into a load folding 73666f716354527c5ab4687a89a1605915e5128a106Evan Cheng/// instruction. e.g. 73766f716354527c5ab4687a89a1605915e5128a106Evan Cheng/// xorl %edi, %eax 73866f716354527c5ab4687a89a1605915e5128a106Evan Cheng/// movl %eax, -32(%ebp) 73966f716354527c5ab4687a89a1605915e5128a106Evan Cheng/// movl -36(%ebp), %eax 74066f716354527c5ab4687a89a1605915e5128a106Evan Cheng/// orl %eax, -32(%ebp) 74166f716354527c5ab4687a89a1605915e5128a106Evan Cheng/// ==> 74266f716354527c5ab4687a89a1605915e5128a106Evan Cheng/// xorl %edi, %eax 74366f716354527c5ab4687a89a1605915e5128a106Evan Cheng/// orl -36(%ebp), %eax 74466f716354527c5ab4687a89a1605915e5128a106Evan Cheng/// mov %eax, -32(%ebp) 74566f716354527c5ab4687a89a1605915e5128a106Evan Cheng/// This enables unfolding optimization for a subsequent instruction which will 74666f716354527c5ab4687a89a1605915e5128a106Evan Cheng/// also eliminate the newly introduced store instruction. 74766f716354527c5ab4687a89a1605915e5128a106Evan Chengbool LocalSpiller::PrepForUnfoldOpti(MachineBasicBlock &MBB, 74866f716354527c5ab4687a89a1605915e5128a106Evan Cheng MachineBasicBlock::iterator &MII, 74966f716354527c5ab4687a89a1605915e5128a106Evan Cheng std::vector<MachineInstr*> &MaybeDeadStores, 75066f716354527c5ab4687a89a1605915e5128a106Evan Cheng AvailableSpills &Spills, 75166f716354527c5ab4687a89a1605915e5128a106Evan Cheng BitVector &RegKills, 75266f716354527c5ab4687a89a1605915e5128a106Evan Cheng std::vector<MachineOperand*> &KillOps, 75366f716354527c5ab4687a89a1605915e5128a106Evan Cheng VirtRegMap &VRM) { 75466f716354527c5ab4687a89a1605915e5128a106Evan Cheng MachineFunction &MF = *MBB.getParent(); 75566f716354527c5ab4687a89a1605915e5128a106Evan Cheng MachineInstr &MI = *MII; 75666f716354527c5ab4687a89a1605915e5128a106Evan Cheng unsigned UnfoldedOpc = 0; 75766f716354527c5ab4687a89a1605915e5128a106Evan Cheng unsigned UnfoldPR = 0; 75866f716354527c5ab4687a89a1605915e5128a106Evan Cheng unsigned UnfoldVR = 0; 75966f716354527c5ab4687a89a1605915e5128a106Evan Cheng int FoldedSS = VirtRegMap::NO_STACK_SLOT; 76066f716354527c5ab4687a89a1605915e5128a106Evan Cheng VirtRegMap::MI2VirtMapTy::const_iterator I, End; 76166f716354527c5ab4687a89a1605915e5128a106Evan Cheng for (tie(I, End) = VRM.getFoldedVirts(&MI); I != End; ++I) { 76266f716354527c5ab4687a89a1605915e5128a106Evan Cheng // Only transform a MI that folds a single register. 76366f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (UnfoldedOpc) 76466f716354527c5ab4687a89a1605915e5128a106Evan Cheng return false; 76566f716354527c5ab4687a89a1605915e5128a106Evan Cheng UnfoldVR = I->second.first; 76666f716354527c5ab4687a89a1605915e5128a106Evan Cheng VirtRegMap::ModRef MR = I->second.second; 76766f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (VRM.isAssignedReg(UnfoldVR)) 76866f716354527c5ab4687a89a1605915e5128a106Evan Cheng continue; 76966f716354527c5ab4687a89a1605915e5128a106Evan Cheng // If this reference is not a use, any previous store is now dead. 77066f716354527c5ab4687a89a1605915e5128a106Evan Cheng // Otherwise, the store to this stack slot is not dead anymore. 77166f716354527c5ab4687a89a1605915e5128a106Evan Cheng FoldedSS = VRM.getStackSlot(UnfoldVR); 77266f716354527c5ab4687a89a1605915e5128a106Evan Cheng MachineInstr* DeadStore = MaybeDeadStores[FoldedSS]; 77366f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (DeadStore && (MR & VirtRegMap::isModRef)) { 77466f716354527c5ab4687a89a1605915e5128a106Evan Cheng unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(FoldedSS); 77566f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (!PhysReg || 77666f716354527c5ab4687a89a1605915e5128a106Evan Cheng DeadStore->findRegisterUseOperandIdx(PhysReg, true) == -1) 77766f716354527c5ab4687a89a1605915e5128a106Evan Cheng continue; 77866f716354527c5ab4687a89a1605915e5128a106Evan Cheng UnfoldPR = PhysReg; 77966f716354527c5ab4687a89a1605915e5128a106Evan Cheng UnfoldedOpc = MRI->getOpcodeAfterMemoryUnfold(MI.getOpcode(), 78066f716354527c5ab4687a89a1605915e5128a106Evan Cheng false, true); 78166f716354527c5ab4687a89a1605915e5128a106Evan Cheng } 78266f716354527c5ab4687a89a1605915e5128a106Evan Cheng } 78366f716354527c5ab4687a89a1605915e5128a106Evan Cheng 78466f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (!UnfoldedOpc) 78566f716354527c5ab4687a89a1605915e5128a106Evan Cheng return false; 78666f716354527c5ab4687a89a1605915e5128a106Evan Cheng 78766f716354527c5ab4687a89a1605915e5128a106Evan Cheng for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 78866f716354527c5ab4687a89a1605915e5128a106Evan Cheng MachineOperand &MO = MI.getOperand(i); 78966f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (!MO.isRegister() || MO.getReg() == 0 || !MO.isUse()) 79066f716354527c5ab4687a89a1605915e5128a106Evan Cheng continue; 79166f716354527c5ab4687a89a1605915e5128a106Evan Cheng unsigned VirtReg = MO.getReg(); 792c498b0281fa81bc213ad1a1228664d480936c0e6Evan Cheng if (MRegisterInfo::isPhysicalRegister(VirtReg) || MO.getSubReg()) 79366f716354527c5ab4687a89a1605915e5128a106Evan Cheng continue; 79466f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (VRM.isAssignedReg(VirtReg)) { 79566f716354527c5ab4687a89a1605915e5128a106Evan Cheng unsigned PhysReg = VRM.getPhys(VirtReg); 79666f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (PhysReg && MRI->regsOverlap(PhysReg, UnfoldPR)) 79766f716354527c5ab4687a89a1605915e5128a106Evan Cheng return false; 79866f716354527c5ab4687a89a1605915e5128a106Evan Cheng } else if (VRM.isReMaterialized(VirtReg)) 79966f716354527c5ab4687a89a1605915e5128a106Evan Cheng continue; 80066f716354527c5ab4687a89a1605915e5128a106Evan Cheng int SS = VRM.getStackSlot(VirtReg); 80166f716354527c5ab4687a89a1605915e5128a106Evan Cheng unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(SS); 80266f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (PhysReg) { 80366f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (MRI->regsOverlap(PhysReg, UnfoldPR)) 80466f716354527c5ab4687a89a1605915e5128a106Evan Cheng return false; 80566f716354527c5ab4687a89a1605915e5128a106Evan Cheng continue; 80666f716354527c5ab4687a89a1605915e5128a106Evan Cheng } 80766f716354527c5ab4687a89a1605915e5128a106Evan Cheng PhysReg = VRM.getPhys(VirtReg); 80866f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (!MRI->regsOverlap(PhysReg, UnfoldPR)) 80966f716354527c5ab4687a89a1605915e5128a106Evan Cheng continue; 81066f716354527c5ab4687a89a1605915e5128a106Evan Cheng 81166f716354527c5ab4687a89a1605915e5128a106Evan Cheng // Ok, we'll need to reload the value into a register which makes 81266f716354527c5ab4687a89a1605915e5128a106Evan Cheng // it impossible to perform the store unfolding optimization later. 81366f716354527c5ab4687a89a1605915e5128a106Evan Cheng // Let's see if it is possible to fold the load if the store is 81466f716354527c5ab4687a89a1605915e5128a106Evan Cheng // unfolded. This allows us to perform the store unfolding 81566f716354527c5ab4687a89a1605915e5128a106Evan Cheng // optimization. 81666f716354527c5ab4687a89a1605915e5128a106Evan Cheng SmallVector<MachineInstr*, 4> NewMIs; 81766f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (MRI->unfoldMemoryOperand(MF, &MI, UnfoldVR, false, false, NewMIs)) { 81866f716354527c5ab4687a89a1605915e5128a106Evan Cheng assert(NewMIs.size() == 1); 81966f716354527c5ab4687a89a1605915e5128a106Evan Cheng MachineInstr *NewMI = NewMIs.back(); 82066f716354527c5ab4687a89a1605915e5128a106Evan Cheng NewMIs.clear(); 82181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng int Idx = NewMI->findRegisterUseOperandIdx(VirtReg); 82281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng assert(Idx != -1); 823aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> Ops; 824aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(Idx); 825aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MachineInstr *FoldedMI = MRI->foldMemoryOperand(NewMI, Ops, SS); 82666f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (FoldedMI) { 827cbfb9b27efd2b4fc1fbc02addf4d41a7d8d8d8ebEvan Cheng if (!VRM.hasPhys(UnfoldVR)) 82866f716354527c5ab4687a89a1605915e5128a106Evan Cheng VRM.assignVirt2Phys(UnfoldVR, UnfoldPR); 82966f716354527c5ab4687a89a1605915e5128a106Evan Cheng VRM.virtFolded(VirtReg, FoldedMI, VirtRegMap::isRef); 83066f716354527c5ab4687a89a1605915e5128a106Evan Cheng MII = MBB.insert(MII, FoldedMI); 831cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng VRM.RemoveMachineInstrFromMaps(&MI); 83266f716354527c5ab4687a89a1605915e5128a106Evan Cheng MBB.erase(&MI); 83366f716354527c5ab4687a89a1605915e5128a106Evan Cheng return true; 83466f716354527c5ab4687a89a1605915e5128a106Evan Cheng } 83566f716354527c5ab4687a89a1605915e5128a106Evan Cheng delete NewMI; 83666f716354527c5ab4687a89a1605915e5128a106Evan Cheng } 83766f716354527c5ab4687a89a1605915e5128a106Evan Cheng } 83866f716354527c5ab4687a89a1605915e5128a106Evan Cheng return false; 83966f716354527c5ab4687a89a1605915e5128a106Evan Cheng} 8407fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner 8417277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng/// findSuperReg - Find the SubReg's super-register of given register class 8427277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng/// where its SubIdx sub-register is SubReg. 8437277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Chengstatic unsigned findSuperReg(const TargetRegisterClass *RC, unsigned SubReg, 8447277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng unsigned SubIdx, const MRegisterInfo *MRI) { 8457277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 8467277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng I != E; ++I) { 8477277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng unsigned Reg = *I; 8487277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng if (MRI->getSubReg(Reg, SubIdx) == SubReg) 8497277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng return Reg; 8507277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng } 8517277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng return 0; 8527277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng} 8537277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng 85481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng/// SpillRegToStackSlot - Spill a register to a specified stack slot. Check if 85581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng/// the last store to the same slot is now dead. If so, remove the last store. 85681a038218171860ee4c382849c647d3dc841fe8bEvan Chengvoid LocalSpiller::SpillRegToStackSlot(MachineBasicBlock &MBB, 85781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineBasicBlock::iterator &MII, 85881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng int Idx, unsigned PhysReg, int StackSlot, 85981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng const TargetRegisterClass *RC, 86035a3e4abb96a6947ec66254b72e788bacc3aadd6Evan Cheng bool isAvailable, MachineInstr *&LastStore, 86181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng AvailableSpills &Spills, 86281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng SmallSet<MachineInstr*, 4> &ReMatDefs, 86381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector &RegKills, 86481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng std::vector<MachineOperand*> &KillOps, 865e4b39007c9d3056334264eba9e2e6025e241d2c5Evan Cheng VirtRegMap &VRM) { 866d64b5c82b97ad1b74eb9fd2f23257a7899b0c307Evan Cheng MRI->storeRegToStackSlot(MBB, next(MII), PhysReg, true, StackSlot, RC); 86781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng DOUT << "Store:\t" << *next(MII); 86881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 86981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If there is a dead store to this stack slot, nuke it now. 87081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (LastStore) { 87181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng DOUT << "Removed dead store:\t" << *LastStore; 87281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ++NumDSE; 87381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng SmallVector<unsigned, 2> KillRegs; 87481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng InvalidateKills(*LastStore, RegKills, KillOps, &KillRegs); 87581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineBasicBlock::iterator PrevMII = LastStore; 87681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool CheckDef = PrevMII != MBB.begin(); 87781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CheckDef) 87881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng --PrevMII; 87981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MBB.erase(LastStore); 880cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng VRM.RemoveMachineInstrFromMaps(LastStore); 88181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CheckDef) { 88281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Look at defs of killed registers on the store. Mark the defs 88381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // as dead since the store has been deleted and they aren't 88481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // being reused. 88581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (unsigned j = 0, ee = KillRegs.size(); j != ee; ++j) { 88681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool HasOtherDef = false; 88781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (InvalidateRegDef(PrevMII, *MII, KillRegs[j], HasOtherDef)) { 88881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *DeadDef = PrevMII; 88981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (ReMatDefs.count(DeadDef) && !HasOtherDef) { 89081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // FIXME: This assumes a remat def does not have side 89181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // effects. 89281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MBB.erase(DeadDef); 893cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng VRM.RemoveMachineInstrFromMaps(DeadDef); 89481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ++NumDRM; 89581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 89681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 89781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 89881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 89981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 90081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 901e4b39007c9d3056334264eba9e2e6025e241d2c5Evan Cheng LastStore = next(MII); 90281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 90381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If the stack slot value was previously available in some other 90481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // register, change it now. Otherwise, make the register available, 90581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // in PhysReg. 90681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Spills.ModifyStackSlotOrReMat(StackSlot); 90781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Spills.ClobberPhysReg(PhysReg); 90835a3e4abb96a6947ec66254b72e788bacc3aadd6Evan Cheng Spills.addAvailable(StackSlot, LastStore, PhysReg, isAvailable); 90981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ++NumStores; 91081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 91181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 9127fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner/// rewriteMBB - Keep track of which spills are available even after the 91381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng/// register allocator is done with them. If possible, avid reloading vregs. 914549f27d3070195d6647b796841a5291b4549e8e0Evan Chengvoid LocalSpiller::RewriteMBB(MachineBasicBlock &MBB, VirtRegMap &VRM) { 915b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling DOUT << MBB.getBasicBlock()->getName() << ":\n"; 9167fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner 917fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng MachineFunction &MF = *MBB.getParent(); 918fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng 91966cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner // Spills - Keep track of which spilled values are available in physregs so 92066cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner // that we can choose to reuse the physregs instead of emitting reloads. 92166cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner AvailableSpills Spills(MRI, TII); 92266cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner 92352b25db3ef9390271bbfa0b5c6efe0a72ce7cb8eChris Lattner // MaybeDeadStores - When we need to write a value back into a stack slot, 92452b25db3ef9390271bbfa0b5c6efe0a72ce7cb8eChris Lattner // keep track of the inserted store. If the stack slot value is never read 92552b25db3ef9390271bbfa0b5c6efe0a72ce7cb8eChris Lattner // (because the value was used from some available register, for example), and 92652b25db3ef9390271bbfa0b5c6efe0a72ce7cb8eChris Lattner // subsequently stored to, the original store is dead. This map keeps track 92752b25db3ef9390271bbfa0b5c6efe0a72ce7cb8eChris Lattner // of inserted stores that are not used. If we see a subsequent store to the 92852b25db3ef9390271bbfa0b5c6efe0a72ce7cb8eChris Lattner // same stack slot, the original store is deleted. 929fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng std::vector<MachineInstr*> MaybeDeadStores; 930fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng MaybeDeadStores.resize(MF.getFrameInfo()->getObjectIndexEnd(), NULL); 93152b25db3ef9390271bbfa0b5c6efe0a72ce7cb8eChris Lattner 932b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng // ReMatDefs - These are rematerializable def MIs which are not deleted. 933b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng SmallSet<MachineInstr*, 4> ReMatDefs; 934b6ca4b370e1313b5d6bda19e86be370a3e00a38fEvan Cheng 9350c40d72b014e8c0f54552d38288a29182effba58Evan Cheng // Keep track of kill information. 9360c40d72b014e8c0f54552d38288a29182effba58Evan Cheng BitVector RegKills(MRI->getNumRegs()); 9370c40d72b014e8c0f54552d38288a29182effba58Evan Cheng std::vector<MachineOperand*> KillOps; 9380c40d72b014e8c0f54552d38288a29182effba58Evan Cheng KillOps.resize(MRI->getNumRegs(), NULL); 9390c40d72b014e8c0f54552d38288a29182effba58Evan Cheng 9407fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner for (MachineBasicBlock::iterator MII = MBB.begin(), E = MBB.end(); 9417fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner MII != E; ) { 9427fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner MachineBasicBlock::iterator NextMII = MII; ++NextMII; 9430c40d72b014e8c0f54552d38288a29182effba58Evan Cheng 94466f716354527c5ab4687a89a1605915e5128a106Evan Cheng VirtRegMap::MI2VirtMapTy::const_iterator I, End; 9450c40d72b014e8c0f54552d38288a29182effba58Evan Cheng bool Erased = false; 9460c40d72b014e8c0f54552d38288a29182effba58Evan Cheng bool BackTracked = false; 94766f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (PrepForUnfoldOpti(MBB, MII, 94866f716354527c5ab4687a89a1605915e5128a106Evan Cheng MaybeDeadStores, Spills, RegKills, KillOps, VRM)) 94966f716354527c5ab4687a89a1605915e5128a106Evan Cheng NextMII = next(MII); 9507fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner 95166f716354527c5ab4687a89a1605915e5128a106Evan Cheng MachineInstr &MI = *MII; 95286facc282850f99479584596058a5625b53caa69Evan Cheng const TargetInstrDescriptor *TID = MI.getInstrDescriptor(); 953e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng 9540cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Insert restores here if asked to. 9550cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (VRM.isRestorePt(&MI)) { 9560cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng std::vector<unsigned> &RestoreRegs = VRM.getRestorePtRestores(&MI); 9570cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng for (unsigned i = 0, e = RestoreRegs.size(); i != e; ++i) { 9580cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng unsigned VirtReg = RestoreRegs[i]; 9590cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!VRM.getPreSplitReg(VirtReg)) 9600cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng continue; // Split interval spilled again. 9610cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng unsigned Phys = VRM.getPhys(VirtReg); 9620cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MF.setPhysRegUsed(Phys); 9630cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (VRM.isReMaterialized(VirtReg)) { 9640cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MRI->reMaterialize(MBB, &MI, Phys, 9650cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng VRM.getReMaterializedMI(VirtReg)); 9660cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++NumReMats; 9670cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } else { 9680cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng const TargetRegisterClass* RC = RegMap->getRegClass(VirtReg); 9690cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MRI->loadRegFromStackSlot(MBB, &MI, Phys, VRM.getStackSlot(VirtReg), RC); 9700cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++NumLoads; 9710cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 9720cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // This invalidates Phys. 9730cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng Spills.ClobberPhysReg(Phys); 9740cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng UpdateKills(*prior(MII), RegKills, KillOps); 9750cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng DOUT << '\t' << *prior(MII); 9760cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 9770cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 9780cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 97981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Insert spills here if asked to. 980cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng if (VRM.isSpillPt(&MI)) { 981b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng std::vector<std::pair<unsigned,bool> > &SpillRegs = 982b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng VRM.getSpillPtSpills(&MI); 983cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng for (unsigned i = 0, e = SpillRegs.size(); i != e; ++i) { 984b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng unsigned VirtReg = SpillRegs[i].first; 985b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng bool isKill = SpillRegs[i].second; 986cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng if (!VRM.getPreSplitReg(VirtReg)) 987cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng continue; // Split interval spilled again. 988cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng const TargetRegisterClass *RC = RegMap->getRegClass(VirtReg); 989cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng unsigned Phys = VRM.getPhys(VirtReg); 990cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng int StackSlot = VRM.getStackSlot(VirtReg); 991b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng MRI->storeRegToStackSlot(MBB, next(MII), Phys, isKill, StackSlot, RC); 992d64b5c82b97ad1b74eb9fd2f23257a7899b0c307Evan Cheng MachineInstr *StoreMI = next(MII); 993d64b5c82b97ad1b74eb9fd2f23257a7899b0c307Evan Cheng DOUT << "Store:\t" << StoreMI; 994d64b5c82b97ad1b74eb9fd2f23257a7899b0c307Evan Cheng VRM.virtFolded(VirtReg, StoreMI, VirtRegMap::isMod); 995cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng } 996e4b39007c9d3056334264eba9e2e6025e241d2c5Evan Cheng NextMII = next(MII); 99781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 99881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 99981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng /// ReusedOperands - Keep track of operand reuse in case we need to undo 100081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng /// reuse. 100181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ReuseInfo ReusedOperands(MI, MRI); 10027fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner // Process all of the spilled uses and all non spilled reg references. 10037fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 10047fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner MachineOperand &MO = MI.getOperand(i); 100550ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner if (!MO.isRegister() || MO.getReg() == 0) 100650ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner continue; // Ignore non-register operands. 100750ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner 100832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng unsigned VirtReg = MO.getReg(); 100932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (MRegisterInfo::isPhysicalRegister(VirtReg)) { 101050ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner // Ignore physregs for spilling, but remember that it is used by this 101150ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner // function. 101232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng MF.setPhysRegUsed(VirtReg); 101350ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner continue; 101450ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner } 101550ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner 101632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng assert(MRegisterInfo::isVirtualRegister(VirtReg) && 101750ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner "Not a virtual or a physical register?"); 101870306f8348f27c61cfed5a60e2fceac0f29746a2Evan Cheng 1019c498b0281fa81bc213ad1a1228664d480936c0e6Evan Cheng unsigned SubIdx = MO.getSubReg(); 1020549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng if (VRM.isAssignedReg(VirtReg)) { 102150ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner // This virtual register was assigned a physreg! 102250ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner unsigned Phys = VRM.getPhys(VirtReg); 10236c087e5585b227f3c1d8278304c7cfbc7cd4f6e8Evan Cheng MF.setPhysRegUsed(Phys); 1024e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng if (MO.isDef()) 1025e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng ReusedOperands.markClobbered(Phys); 1026c498b0281fa81bc213ad1a1228664d480936c0e6Evan Cheng unsigned RReg = SubIdx ? MRI->getSubReg(Phys, SubIdx) : Phys; 102732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng MI.getOperand(i).setReg(RReg); 102850ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner continue; 102950ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner } 103050ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner 103150ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner // This virtual register is now known to be a spilled value. 103250ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner if (!MO.isUse()) 103350ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner continue; // Handle defs in the loop below (handle use&def here though) 103450ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner 1035549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng bool DoReMat = VRM.isReMaterialized(VirtReg); 1036549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng int SSorRMId = DoReMat 1037549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng ? VRM.getReMatId(VirtReg) : VRM.getStackSlot(VirtReg); 1038dc6be1985944716a0fb4a2706dcea9e1296e3d6aEvan Cheng int ReuseSlot = SSorRMId; 103950ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner 104050ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner // Check to see if this stack slot is available. 1041dc6be1985944716a0fb4a2706dcea9e1296e3d6aEvan Cheng unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(SSorRMId); 104232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng 104332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // If this is a sub-register use, make sure the reuse register is in the 104432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // right register class. For example, for x86 not all of the 32-bit 104532dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // registers have accessible sub-registers. 104632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // Similarly so for EXTRACT_SUBREG. Consider this: 104732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // EDI = op 104832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // MOV32_mr fi#1, EDI 104932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // ... 105032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // = EXTRACT_SUBREG fi#1 105132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // fi#1 is available in EDI, but it cannot be reused because it's not in 105232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // the right register file. 105332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (PhysReg && 1054c498b0281fa81bc213ad1a1228664d480936c0e6Evan Cheng (SubIdx || MI.getOpcode() == TargetInstrInfo::EXTRACT_SUBREG)) { 105532dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng const TargetRegisterClass* RC = RegMap->getRegClass(VirtReg); 105632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (!RC->contains(PhysReg)) 105732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng PhysReg = 0; 105832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng } 105932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng 1060dc6be1985944716a0fb4a2706dcea9e1296e3d6aEvan Cheng if (PhysReg) { 10612926869b4a083fc951484de03a9867eabf81e880Chris Lattner // This spilled operand might be part of a two-address operand. If this 10622926869b4a083fc951484de03a9867eabf81e880Chris Lattner // is the case, then changing it will necessarily require changing the 10632926869b4a083fc951484de03a9867eabf81e880Chris Lattner // def part of the instruction as well. However, in some cases, we 10642926869b4a083fc951484de03a9867eabf81e880Chris Lattner // aren't allowed to modify the reused register. If none of these cases 10652926869b4a083fc951484de03a9867eabf81e880Chris Lattner // apply, reuse it. 10662926869b4a083fc951484de03a9867eabf81e880Chris Lattner bool CanReuse = true; 106786facc282850f99479584596058a5625b53caa69Evan Cheng int ti = TID->getOperandConstraint(i, TOI::TIED_TO); 1068360c2dd25a0dc7eaed3d57af47a47ac7d12a6886Evan Cheng if (ti != -1 && 106992dfe2001e96f6e2b6d327e8816f38033f88b295Dan Gohman MI.getOperand(ti).isRegister() && 1070360c2dd25a0dc7eaed3d57af47a47ac7d12a6886Evan Cheng MI.getOperand(ti).getReg() == VirtReg) { 10712926869b4a083fc951484de03a9867eabf81e880Chris Lattner // Okay, we have a two address operand. We can reuse this physreg as 10723c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng // long as we are allowed to clobber the value and there isn't an 10733c82cab9aad8bd1ae7a9dd03548f721522db79f3Evan Cheng // earlier def that has already clobbered the physreg. 1074dc6be1985944716a0fb4a2706dcea9e1296e3d6aEvan Cheng CanReuse = Spills.canClobberPhysReg(ReuseSlot) && 1075e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng !ReusedOperands.isClobbered(PhysReg); 10762926869b4a083fc951484de03a9867eabf81e880Chris Lattner } 10772926869b4a083fc951484de03a9867eabf81e880Chris Lattner 10782926869b4a083fc951484de03a9867eabf81e880Chris Lattner if (CanReuse) { 1079addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // If this stack slot value is already available, reuse it! 1080dc6be1985944716a0fb4a2706dcea9e1296e3d6aEvan Cheng if (ReuseSlot > VirtRegMap::MAX_STACK_SLOT) 1081dc6be1985944716a0fb4a2706dcea9e1296e3d6aEvan Cheng DOUT << "Reusing RM#" << ReuseSlot-VirtRegMap::MAX_STACK_SLOT-1; 10822638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng else 1083dc6be1985944716a0fb4a2706dcea9e1296e3d6aEvan Cheng DOUT << "Reusing SS#" << ReuseSlot; 10842638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng DOUT << " from physreg " 1085b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling << MRI->getName(PhysReg) << " for vreg" 1086b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling << VirtReg <<" instead of reloading into physreg " 1087b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling << MRI->getName(VRM.getPhys(VirtReg)) << "\n"; 1088c498b0281fa81bc213ad1a1228664d480936c0e6Evan Cheng unsigned RReg = SubIdx ? MRI->getSubReg(PhysReg, SubIdx) : PhysReg; 108932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng MI.getOperand(i).setReg(RReg); 1090addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner 1091addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // The only technical detail we have is that we don't know that 1092addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // PhysReg won't be clobbered by a reloaded stack slot that occurs 1093addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // later in the instruction. In particular, consider 'op V1, V2'. 1094addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // If V1 is available in physreg R0, we would choose to reuse it 1095addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // here, instead of reloading it into the register the allocator 1096addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // indicated (say R1). However, V2 might have to be reloaded 1097addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // later, and it might indicate that it needs to live in R0. When 1098addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // this occurs, we need to have information available that 1099addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // indicates it is safe to use R1 for the reload instead of R0. 1100addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // 1101addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // To further complicate matters, we might conflict with an alias, 1102addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // or R0 and R1 might not be compatible with each other. In this 1103addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // case, we actually insert a reload for V1 in R1, ensuring that 1104addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // we can get at R0 or its alias. 1105dc6be1985944716a0fb4a2706dcea9e1296e3d6aEvan Cheng ReusedOperands.addReuse(i, ReuseSlot, PhysReg, 1106addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner VRM.getPhys(VirtReg), VirtReg); 1107e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng if (ti != -1) 1108e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng // Only mark it clobbered if this is a use&def operand. 1109e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng ReusedOperands.markClobbered(PhysReg); 1110addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner ++NumReused; 1111fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng 1112fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng if (MI.getOperand(i).isKill() && 1113fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng ReuseSlot <= VirtRegMap::MAX_STACK_SLOT) { 1114fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng // This was the last use and the spilled value is still available 1115fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng // for reuse. That means the spill was unnecessary! 1116fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng MachineInstr* DeadStore = MaybeDeadStores[ReuseSlot]; 1117fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng if (DeadStore) { 1118fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng DOUT << "Removed dead store:\t" << *DeadStore; 1119fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng InvalidateKills(*DeadStore, RegKills, KillOps); 1120cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng VRM.RemoveMachineInstrFromMaps(DeadStore); 112166f716354527c5ab4687a89a1605915e5128a106Evan Cheng MBB.erase(DeadStore); 1122fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng MaybeDeadStores[ReuseSlot] = NULL; 1123fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng ++NumDSE; 1124fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng } 1125fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng } 1126addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner continue; 112732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng } // CanReuse 1128addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner 1129addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // Otherwise we have a situation where we have a two-address instruction 1130addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // whose mod/ref operand needs to be reloaded. This reload is already 1131addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // available in some register "PhysReg", but if we used PhysReg as the 1132addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // operand to our 2-addr instruction, the instruction would modify 1133addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // PhysReg. This isn't cool if something later uses PhysReg and expects 1134addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // to get its initial value. 113550ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner // 1136addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // To avoid this problem, and to avoid doing a load right after a store, 1137addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // we emit a copy from PhysReg into the designated register for this 1138addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // operand. 1139addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner unsigned DesignatedReg = VRM.getPhys(VirtReg); 1140addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner assert(DesignatedReg && "Must map virtreg to physreg!"); 1141addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner 1142addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // Note that, if we reused a register for a previous operand, the 1143addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // register we want to reload into might not actually be 1144addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // available. If this occurs, use the register indicated by the 1145addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // reuser. 1146addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner if (ReusedOperands.hasReuses()) 1147addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner DesignatedReg = ReusedOperands.GetRegForReload(DesignatedReg, &MI, 1148549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng Spills, MaybeDeadStores, RegKills, KillOps, VRM); 1149addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner 1150ba1fc3daf757c8f880c3069eed20218c91f2c3a8Chris Lattner // If the mapped designated register is actually the physreg we have 1151ba1fc3daf757c8f880c3069eed20218c91f2c3a8Chris Lattner // incoming, we don't need to inserted a dead copy. 1152ba1fc3daf757c8f880c3069eed20218c91f2c3a8Chris Lattner if (DesignatedReg == PhysReg) { 1153ba1fc3daf757c8f880c3069eed20218c91f2c3a8Chris Lattner // If this stack slot value is already available, reuse it! 1154dc6be1985944716a0fb4a2706dcea9e1296e3d6aEvan Cheng if (ReuseSlot > VirtRegMap::MAX_STACK_SLOT) 1155dc6be1985944716a0fb4a2706dcea9e1296e3d6aEvan Cheng DOUT << "Reusing RM#" << ReuseSlot-VirtRegMap::MAX_STACK_SLOT-1; 11562638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng else 1157dc6be1985944716a0fb4a2706dcea9e1296e3d6aEvan Cheng DOUT << "Reusing SS#" << ReuseSlot; 11582638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng DOUT << " from physreg " << MRI->getName(PhysReg) << " for vreg" 1159b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling << VirtReg 1160b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling << " instead of reloading into same physreg.\n"; 1161c498b0281fa81bc213ad1a1228664d480936c0e6Evan Cheng unsigned RReg = SubIdx ? MRI->getSubReg(PhysReg, SubIdx) : PhysReg; 116232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng MI.getOperand(i).setReg(RReg); 11637277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng ReusedOperands.markClobbered(RReg); 1164ba1fc3daf757c8f880c3069eed20218c91f2c3a8Chris Lattner ++NumReused; 1165ba1fc3daf757c8f880c3069eed20218c91f2c3a8Chris Lattner continue; 1166ba1fc3daf757c8f880c3069eed20218c91f2c3a8Chris Lattner } 1167ba1fc3daf757c8f880c3069eed20218c91f2c3a8Chris Lattner 116832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng const TargetRegisterClass* RC = RegMap->getRegClass(VirtReg); 11696c087e5585b227f3c1d8278304c7cfbc7cd4f6e8Evan Cheng MF.setPhysRegUsed(DesignatedReg); 1170e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng ReusedOperands.markClobbered(DesignatedReg); 11719efce638d307b2c71bd7f0258d47501661434c27Evan Cheng MRI->copyRegToReg(MBB, &MI, DesignatedReg, PhysReg, RC, RC); 1172de4e942faa12a52242915e3334c25f19687f36e2Evan Cheng 11736b448092bff8d149769becaa14415bc1a3857e33Evan Cheng MachineInstr *CopyMI = prior(MII); 11740c40d72b014e8c0f54552d38288a29182effba58Evan Cheng UpdateKills(*CopyMI, RegKills, KillOps); 1175de4e942faa12a52242915e3334c25f19687f36e2Evan Cheng 1176addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner // This invalidates DesignatedReg. 1177addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner Spills.ClobberPhysReg(DesignatedReg); 1178addc55af6c7f8b71eedd68d48f6a93ceecff2840Chris Lattner 1179dc6be1985944716a0fb4a2706dcea9e1296e3d6aEvan Cheng Spills.addAvailable(ReuseSlot, &MI, DesignatedReg); 118032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng unsigned RReg = 1181c498b0281fa81bc213ad1a1228664d480936c0e6Evan Cheng SubIdx ? MRI->getSubReg(DesignatedReg, SubIdx) : DesignatedReg; 118232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng MI.getOperand(i).setReg(RReg); 1183b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling DOUT << '\t' << *prior(MII); 118450ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner ++NumReused; 118550ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner continue; 118666f716354527c5ab4687a89a1605915e5128a106Evan Cheng } // if (PhysReg) 118750ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner 118850ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner // Otherwise, reload it and remember that we have it. 118950ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner PhysReg = VRM.getPhys(VirtReg); 1190172c362fefe3d6e762ada119d4084ed4ed31595bChris Lattner assert(PhysReg && "Must map virtreg to physreg!"); 119150ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner 119250ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner // Note that, if we reused a register for a previous operand, the 119350ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner // register we want to reload into might not actually be 119450ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner // available. If this occurs, use the register indicated by the 119550ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner // reuser. 1196540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner if (ReusedOperands.hasReuses()) 1197540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner PhysReg = ReusedOperands.GetRegForReload(PhysReg, &MI, 1198549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng Spills, MaybeDeadStores, RegKills, KillOps, VRM); 1199540fec6b38c8107161a0db4f8a6b7cc50be38b4aChris Lattner 12006c087e5585b227f3c1d8278304c7cfbc7cd4f6e8Evan Cheng MF.setPhysRegUsed(PhysReg); 1201e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng ReusedOperands.markClobbered(PhysReg); 1202549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng if (DoReMat) { 12032638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng MRI->reMaterialize(MBB, &MI, PhysReg, VRM.getReMaterializedMI(VirtReg)); 12049193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng ++NumReMats; 12059193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng } else { 120632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng const TargetRegisterClass* RC = RegMap->getRegClass(VirtReg); 1207549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng MRI->loadRegFromStackSlot(MBB, &MI, PhysReg, SSorRMId, RC); 12089193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng ++NumLoads; 12099193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng } 121050ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner // This invalidates PhysReg. 121166cf80f226e04e6704a78da83e08c7b0af944ef1Chris Lattner Spills.ClobberPhysReg(PhysReg); 121250ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner 121350ea01ed5ba23c8988af9fed0b91178e69140a80Chris Lattner // Any stores to this stack slot are not dead anymore. 1214549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng if (!DoReMat) 1215fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng MaybeDeadStores[SSorRMId] = NULL; 1216549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng Spills.addAvailable(SSorRMId, &MI, PhysReg); 1217de4e942faa12a52242915e3334c25f19687f36e2Evan Cheng // Assumes this is the last use. IsKill will be unset if reg is reused 1218de4e942faa12a52242915e3334c25f19687f36e2Evan Cheng // unless it's a two-address operand. 1219de4e942faa12a52242915e3334c25f19687f36e2Evan Cheng if (TID->getOperandConstraint(i, TOI::TIED_TO) == -1) 1220de4e942faa12a52242915e3334c25f19687f36e2Evan Cheng MI.getOperand(i).setIsKill(); 1221c498b0281fa81bc213ad1a1228664d480936c0e6Evan Cheng unsigned RReg = SubIdx ? MRI->getSubReg(PhysReg, SubIdx) : PhysReg; 122232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng MI.getOperand(i).setReg(RReg); 12230c40d72b014e8c0f54552d38288a29182effba58Evan Cheng UpdateKills(*prior(MII), RegKills, KillOps); 1224b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling DOUT << '\t' << *prior(MII); 12258c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 12260d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 1227b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling DOUT << '\t' << MI; 12287fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner 122981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 12307fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner // If we have folded references to memory operands, make sure we clear all 12317fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner // physical registers that may contain the value of the spilled virtual 12327fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner // register 123366f716354527c5ab4687a89a1605915e5128a106Evan Cheng SmallSet<int, 2> FoldedSS; 12348f1d6402ba73b96993ffd1eb9434b28c828d8856Chris Lattner for (tie(I, End) = VRM.getFoldedVirts(&MI); I != End; ++I) { 1235bec6a9ea1281a0b3b37aece91ab0df21e086af61Chris Lattner unsigned VirtReg = I->second.first; 1236bec6a9ea1281a0b3b37aece91ab0df21e086af61Chris Lattner VirtRegMap::ModRef MR = I->second.second; 123766f716354527c5ab4687a89a1605915e5128a106Evan Cheng DOUT << "Folded vreg: " << VirtReg << " MR: " << MR; 123881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1239cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner int SS = VRM.getStackSlot(VirtReg); 124081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (SS == VirtRegMap::NO_STACK_SLOT) 124181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 124290a43c3ae385d98d19f9c858b51920552fb9ceaaEvan Cheng FoldedSS.insert(SS); 1243b2b9c20b6121a54a41ee1c583a4bff4389622da2Bill Wendling DOUT << " - StackSlot: " << SS << "\n"; 1244cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner 1245cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner // If this folded instruction is just a use, check to see if it's a 1246cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner // straight load from the virt reg slot. 1247cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner if ((MR & VirtRegMap::isRef) && !(MR & VirtRegMap::isMod)) { 1248cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner int FrameIdx; 124932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng unsigned DestReg = TII->isLoadFromStackSlot(&MI, FrameIdx); 125032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (DestReg && FrameIdx == SS) { 125132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // If this spill slot is available, turn it into a copy (or nothing) 125232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // instead of leaving it as a load! 125332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (unsigned InReg = Spills.getSpillSlotOrReMatPhysReg(SS)) { 125432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng DOUT << "Promoted Load To Copy: " << MI; 125532dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (DestReg != InReg) { 125632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng const TargetRegisterClass *RC = RegMap->getRegClass(VirtReg); 125732dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng MRI->copyRegToReg(MBB, &MI, DestReg, InReg, RC, RC); 125832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // Revisit the copy so we make sure to notice the effects of the 125932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // operation on the destreg (either needing to RA it if it's 126032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng // virtual or needing to clobber any values if it's physical). 126132dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng NextMII = &MI; 126232dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng --NextMII; // backtrack to the copy. 126332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng BackTracked = true; 126432dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng } else 126532dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng DOUT << "Removing now-noop copy: " << MI; 126632dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng 1267cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng VRM.RemoveMachineInstrFromMaps(&MI); 126832dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng MBB.erase(&MI); 126932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng Erased = true; 127032dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng goto ProcessNextInst; 1271bec6a9ea1281a0b3b37aece91ab0df21e086af61Chris Lattner } 12727f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng } else { 12737f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(SS); 12747f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng SmallVector<MachineInstr*, 4> NewMIs; 12757f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng if (PhysReg && 12767f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng MRI->unfoldMemoryOperand(MF, &MI, PhysReg, false, false, NewMIs)) { 12777f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng MBB.insert(MII, NewMIs[0]); 1278cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng VRM.RemoveMachineInstrFromMaps(&MI); 12797f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng MBB.erase(&MI); 12807f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng Erased = true; 12817f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng --NextMII; // backtrack to the unfolded instruction. 12827f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng BackTracked = true; 12837f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng goto ProcessNextInst; 12847f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng } 1285bec6a9ea1281a0b3b37aece91ab0df21e086af61Chris Lattner } 1286cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner } 128752b25db3ef9390271bbfa0b5c6efe0a72ce7cb8eChris Lattner 1288cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner // If this reference is not a use, any previous store is now dead. 1289cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner // Otherwise, the store to this stack slot is not dead anymore. 1290fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng MachineInstr* DeadStore = MaybeDeadStores[SS]; 1291fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng if (DeadStore) { 129266f716354527c5ab4687a89a1605915e5128a106Evan Cheng bool isDead = !(MR & VirtRegMap::isRef); 12937f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng MachineInstr *NewStore = NULL; 1294cbfb9b27efd2b4fc1fbc02addf4d41a7d8d8d8ebEvan Cheng if (MR & VirtRegMap::isModRef) { 12957f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng unsigned PhysReg = Spills.getSpillSlotOrReMatPhysReg(SS); 12967f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng SmallVector<MachineInstr*, 4> NewMIs; 129735a3e4abb96a6947ec66254b72e788bacc3aadd6Evan Cheng // We can reuse this physreg as long as we are allowed to clobber 129835a3e4abb96a6947ec66254b72e788bacc3aadd6Evan Cheng // the value and there isn't an earlier def that has already clobbered the 129935a3e4abb96a6947ec66254b72e788bacc3aadd6Evan Cheng // physreg. 13007f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng if (PhysReg && 13017f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng DeadStore->findRegisterUseOperandIdx(PhysReg, true) != -1 && 13027f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng MRI->unfoldMemoryOperand(MF, &MI, PhysReg, false, true, NewMIs)) { 13037f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng MBB.insert(MII, NewMIs[0]); 13047f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng NewStore = NewMIs[1]; 13057f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng MBB.insert(MII, NewStore); 1306cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng VRM.RemoveMachineInstrFromMaps(&MI); 13077f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng MBB.erase(&MI); 13087f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng Erased = true; 13097f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng --NextMII; 13107f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng --NextMII; // backtrack to the unfolded instruction. 13117f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng BackTracked = true; 131266f716354527c5ab4687a89a1605915e5128a106Evan Cheng isDead = true; 131366f716354527c5ab4687a89a1605915e5128a106Evan Cheng } 13147f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng } 13157f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng 13167f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng if (isDead) { // Previous store is dead. 1317cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner // If we get here, the store is dead, nuke it now. 1318fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng DOUT << "Removed dead store:\t" << *DeadStore; 1319fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng InvalidateKills(*DeadStore, RegKills, KillOps); 1320cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng VRM.RemoveMachineInstrFromMaps(DeadStore); 13217f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng MBB.erase(DeadStore); 13227f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng if (!NewStore) 13237f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng ++NumDSE; 1324cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner } 13257f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng 1326fff3e191b959bfc00e266b47f5c142464bb50ebfEvan Cheng MaybeDeadStores[SS] = NULL; 13277f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng if (NewStore) { 13287f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng // Treat this store as a spill merged into a copy. That makes the 13297f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng // stack slot value available. 13307f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng VRM.virtFolded(VirtReg, NewStore, VirtRegMap::isMod); 13317f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng goto ProcessNextInst; 13327f56625447b94178118f2fec732b10f9e4aa7fbfEvan Cheng } 1333cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner } 1334cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner 1335cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner // If the spill slot value is available, and this is a new definition of 1336cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner // the value, the value is not available anymore. 1337cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner if (MR & VirtRegMap::isMod) { 133807cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner // Notice that the value in this stack slot has been modified. 1339549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng Spills.ModifyStackSlotOrReMat(SS); 1340cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner 1341cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner // If this is *just* a mod of the value, check to see if this is just a 1342cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner // store to the spill slot (i.e. the spill got merged into the copy). If 1343cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner // so, realize that the vreg is available now, and add the store to the 1344cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner // MaybeDeadStore info. 1345cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner int StackSlot; 1346cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner if (!(MR & VirtRegMap::isRef)) { 1347cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner if (unsigned SrcReg = TII->isStoreToStackSlot(&MI, StackSlot)) { 1348cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner assert(MRegisterInfo::isPhysicalRegister(SrcReg) && 1349cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner "Src hasn't been allocated yet?"); 135007cf14112dcdb9c6b20a4f8e17de717b5219dad8Chris Lattner // Okay, this is certainly a store of SrcReg to [StackSlot]. Mark 1351cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner // this as a potentially dead store in case there is a subsequent 1352cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner // store into the stack slot without a read from it. 1353cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner MaybeDeadStores[StackSlot] = &MI; 1354cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner 1355cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner // If the stack slot value was previously available in some other 1356cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner // register, change it now. Otherwise, make the register available, 1357cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner // in PhysReg. 135891e2390818080ae2b059e3ff850a9455858e4f7bEvan Cheng Spills.addAvailable(StackSlot, &MI, SrcReg, false/*don't clobber*/); 1359cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner } 1360cd81639d2e3705ee13b1869d6c166b5f5b4c29c4Chris Lattner } 13617fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner } 13628c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 13630d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 13647fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner // Process all of the spilled defs. 13657fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 13667fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner MachineOperand &MO = MI.getOperand(i); 136766f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (!(MO.isRegister() && MO.getReg() && MO.isDef())) 136866f716354527c5ab4687a89a1605915e5128a106Evan Cheng continue; 13697fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner 137066f716354527c5ab4687a89a1605915e5128a106Evan Cheng unsigned VirtReg = MO.getReg(); 137166f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (!MRegisterInfo::isVirtualRegister(VirtReg)) { 137266f716354527c5ab4687a89a1605915e5128a106Evan Cheng // Check to see if this is a noop copy. If so, eliminate the 137366f716354527c5ab4687a89a1605915e5128a106Evan Cheng // instruction before considering the dest reg to be changed. 137466f716354527c5ab4687a89a1605915e5128a106Evan Cheng unsigned Src, Dst; 137566f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (TII->isMoveInstr(MI, Src, Dst) && Src == Dst) { 137666f716354527c5ab4687a89a1605915e5128a106Evan Cheng ++NumDCE; 137766f716354527c5ab4687a89a1605915e5128a106Evan Cheng DOUT << "Removing now-noop copy: " << MI; 137866f716354527c5ab4687a89a1605915e5128a106Evan Cheng MBB.erase(&MI); 137966f716354527c5ab4687a89a1605915e5128a106Evan Cheng Erased = true; 1380cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng VRM.RemoveMachineInstrFromMaps(&MI); 138166f716354527c5ab4687a89a1605915e5128a106Evan Cheng Spills.disallowClobberPhysReg(VirtReg); 138266f716354527c5ab4687a89a1605915e5128a106Evan Cheng goto ProcessNextInst; 138366f716354527c5ab4687a89a1605915e5128a106Evan Cheng } 13846ec3626be40963fa405992e219f94d9524fb6c15Chris Lattner 138566f716354527c5ab4687a89a1605915e5128a106Evan Cheng // If it's not a no-op copy, it clobbers the value in the destreg. 138666f716354527c5ab4687a89a1605915e5128a106Evan Cheng Spills.ClobberPhysReg(VirtReg); 138766f716354527c5ab4687a89a1605915e5128a106Evan Cheng ReusedOperands.markClobbered(VirtReg); 13886ec3626be40963fa405992e219f94d9524fb6c15Chris Lattner 138966f716354527c5ab4687a89a1605915e5128a106Evan Cheng // Check to see if this instruction is a load from a stack slot into 139066f716354527c5ab4687a89a1605915e5128a106Evan Cheng // a register. If so, this provides the stack slot value in the reg. 139166f716354527c5ab4687a89a1605915e5128a106Evan Cheng int FrameIdx; 139266f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (unsigned DestReg = TII->isLoadFromStackSlot(&MI, FrameIdx)) { 139366f716354527c5ab4687a89a1605915e5128a106Evan Cheng assert(DestReg == VirtReg && "Unknown load situation!"); 139466f716354527c5ab4687a89a1605915e5128a106Evan Cheng 139566f716354527c5ab4687a89a1605915e5128a106Evan Cheng // If it is a folded reference, then it's not safe to clobber. 139666f716354527c5ab4687a89a1605915e5128a106Evan Cheng bool Folded = FoldedSS.count(FrameIdx); 139766f716354527c5ab4687a89a1605915e5128a106Evan Cheng // Otherwise, if it wasn't available, remember that it is now! 139866f716354527c5ab4687a89a1605915e5128a106Evan Cheng Spills.addAvailable(FrameIdx, &MI, DestReg, !Folded); 139966f716354527c5ab4687a89a1605915e5128a106Evan Cheng goto ProcessNextInst; 1400edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman } 140166f716354527c5ab4687a89a1605915e5128a106Evan Cheng 140266f716354527c5ab4687a89a1605915e5128a106Evan Cheng continue; 140366f716354527c5ab4687a89a1605915e5128a106Evan Cheng } 14047fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner 1405c498b0281fa81bc213ad1a1228664d480936c0e6Evan Cheng unsigned SubIdx = MO.getSubReg(); 140666f716354527c5ab4687a89a1605915e5128a106Evan Cheng bool DoReMat = VRM.isReMaterialized(VirtReg); 140766f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (DoReMat) 140866f716354527c5ab4687a89a1605915e5128a106Evan Cheng ReMatDefs.insert(&MI); 140966f716354527c5ab4687a89a1605915e5128a106Evan Cheng 141066f716354527c5ab4687a89a1605915e5128a106Evan Cheng // The only vregs left are stack slot definitions. 141166f716354527c5ab4687a89a1605915e5128a106Evan Cheng int StackSlot = VRM.getStackSlot(VirtReg); 141266f716354527c5ab4687a89a1605915e5128a106Evan Cheng const TargetRegisterClass *RC = RegMap->getRegClass(VirtReg); 141366f716354527c5ab4687a89a1605915e5128a106Evan Cheng 141466f716354527c5ab4687a89a1605915e5128a106Evan Cheng // If this def is part of a two-address operand, make sure to execute 141566f716354527c5ab4687a89a1605915e5128a106Evan Cheng // the store from the correct physical register. 141666f716354527c5ab4687a89a1605915e5128a106Evan Cheng unsigned PhysReg; 141766f716354527c5ab4687a89a1605915e5128a106Evan Cheng int TiedOp = MI.getInstrDescriptor()->findTiedToSrcOperand(i); 14187277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng if (TiedOp != -1) { 141966f716354527c5ab4687a89a1605915e5128a106Evan Cheng PhysReg = MI.getOperand(TiedOp).getReg(); 1420c498b0281fa81bc213ad1a1228664d480936c0e6Evan Cheng if (SubIdx) { 14217277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng unsigned SuperReg = findSuperReg(RC, PhysReg, SubIdx, MRI); 14227277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng assert(SuperReg && MRI->getSubReg(SuperReg, SubIdx) == PhysReg && 14237277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng "Can't find corresponding super-register!"); 14247277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng PhysReg = SuperReg; 14257277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng } 14267277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng } else { 142766f716354527c5ab4687a89a1605915e5128a106Evan Cheng PhysReg = VRM.getPhys(VirtReg); 142866f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (ReusedOperands.isClobbered(PhysReg)) { 142966f716354527c5ab4687a89a1605915e5128a106Evan Cheng // Another def has taken the assigned physreg. It must have been a 143066f716354527c5ab4687a89a1605915e5128a106Evan Cheng // use&def which got it due to reuse. Undo the reuse! 143166f716354527c5ab4687a89a1605915e5128a106Evan Cheng PhysReg = ReusedOperands.GetRegForReload(PhysReg, &MI, 1432549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng Spills, MaybeDeadStores, RegKills, KillOps, VRM); 1433e077ef6e85fe0c18f135e6c2c78572a44f689b14Evan Cheng } 143466f716354527c5ab4687a89a1605915e5128a106Evan Cheng } 143584e752a8129e7a02ee6e3c6d356a8fd68fbdf698Chris Lattner 143666f716354527c5ab4687a89a1605915e5128a106Evan Cheng MF.setPhysRegUsed(PhysReg); 1437c498b0281fa81bc213ad1a1228664d480936c0e6Evan Cheng unsigned RReg = SubIdx ? MRI->getSubReg(PhysReg, SubIdx) : PhysReg; 14387277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng ReusedOperands.markClobbered(RReg); 14397277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng MI.getOperand(i).setReg(RReg); 14407277a7d031d2ccd66e2c3da0c797af0bf9f089caEvan Cheng 144166f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (!MO.isDead()) { 144266f716354527c5ab4687a89a1605915e5128a106Evan Cheng MachineInstr *&LastStore = MaybeDeadStores[StackSlot]; 144335a3e4abb96a6947ec66254b72e788bacc3aadd6Evan Cheng SpillRegToStackSlot(MBB, MII, -1, PhysReg, StackSlot, RC, true, 144435a3e4abb96a6947ec66254b72e788bacc3aadd6Evan Cheng LastStore, Spills, ReMatDefs, RegKills, KillOps, VRM); 1445e4b39007c9d3056334264eba9e2e6025e241d2c5Evan Cheng NextMII = next(MII); 144666f716354527c5ab4687a89a1605915e5128a106Evan Cheng 144766f716354527c5ab4687a89a1605915e5128a106Evan Cheng // Check to see if this is a noop copy. If so, eliminate the 144866f716354527c5ab4687a89a1605915e5128a106Evan Cheng // instruction before considering the dest reg to be changed. 144966f716354527c5ab4687a89a1605915e5128a106Evan Cheng { 145066f716354527c5ab4687a89a1605915e5128a106Evan Cheng unsigned Src, Dst; 145166f716354527c5ab4687a89a1605915e5128a106Evan Cheng if (TII->isMoveInstr(MI, Src, Dst) && Src == Dst) { 145266f716354527c5ab4687a89a1605915e5128a106Evan Cheng ++NumDCE; 145366f716354527c5ab4687a89a1605915e5128a106Evan Cheng DOUT << "Removing now-noop copy: " << MI; 145466f716354527c5ab4687a89a1605915e5128a106Evan Cheng MBB.erase(&MI); 145566f716354527c5ab4687a89a1605915e5128a106Evan Cheng Erased = true; 1456cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng VRM.RemoveMachineInstrFromMaps(&MI); 145766f716354527c5ab4687a89a1605915e5128a106Evan Cheng UpdateKills(*LastStore, RegKills, KillOps); 145866f716354527c5ab4687a89a1605915e5128a106Evan Cheng goto ProcessNextInst; 1459f50d09ad21dbb16e35460d63d23d331a2cac7a91Evan Cheng } 146066f716354527c5ab4687a89a1605915e5128a106Evan Cheng } 146166f716354527c5ab4687a89a1605915e5128a106Evan Cheng } 14628c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 1463cea8688ee4637e0f3cffc75e47f15be756f043bfChris Lattner ProcessNextInst: 146435a3e4abb96a6947ec66254b72e788bacc3aadd6Evan Cheng if (!Erased && !BackTracked) { 14650c40d72b014e8c0f54552d38288a29182effba58Evan Cheng for (MachineBasicBlock::iterator II = MI; II != NextMII; ++II) 14660c40d72b014e8c0f54552d38288a29182effba58Evan Cheng UpdateKills(*II, RegKills, KillOps); 146735a3e4abb96a6947ec66254b72e788bacc3aadd6Evan Cheng } 14687fb64347d7d1310b5f3f06f7ae97031c73a21797Chris Lattner MII = NextMII; 14698c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 14700d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos} 14710d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 14728c4d88d3697835371ecf6823f4142af13603ad2dChris Lattnerllvm::Spiller* llvm::createSpiller() { 14738c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner switch (SpillerOpt) { 14748c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner default: assert(0 && "Unreachable!"); 14758c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner case local: 14768c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner return new LocalSpiller(); 14778c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner case simple: 14788c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner return new SimpleSpiller(); 14798c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 14800d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos} 1481