VirtRegMap.cpp revision fb9ebbf236974beac31705eaeb9f50ab585af6ab
134d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos//===-- llvm/CodeGen/VirtRegMap.cpp - Virtual Register Map ----------------===// 234d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// 334d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// The LLVM Compiler Infrastructure 434d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 734d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// 834d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos//===----------------------------------------------------------------------===// 934d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// 108c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner// This file implements the VirtRegMap class. 118c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner// 12f451cb870efcf9e0302d25ed05f4cac6bb494e42Dan Gohman// It also contains implementations of 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 194281e20aab7f1fe1b35b31c9237ad89c20937e02Jakob Stoklund Olesen#define DEBUG_TYPE "regalloc" 2034d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos#include "VirtRegMap.h" 2105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen#include "LiveDebugVariables.h" 2205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen#include "llvm/CodeGen/LiveIntervalAnalysis.h" 23bb36a438722d4d56febc07c6472c8446bb6faafeEvan Cheng#include "llvm/CodeGen/LiveStackAnalysis.h" 2434d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos#include "llvm/CodeGen/MachineFrameInfo.h" 258c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner#include "llvm/CodeGen/MachineFunction.h" 264cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng#include "llvm/CodeGen/MachineInstrBuilder.h" 2784bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner#include "llvm/CodeGen/MachineRegisterInfo.h" 2805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen#include "llvm/CodeGen/Passes.h" 2934d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos#include "llvm/Target/TargetMachine.h" 300d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos#include "llvm/Target/TargetInstrInfo.h" 31fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump#include "llvm/Target/TargetRegisterInfo.h" 32551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 33a4f0b3a084d120cfc5b5bb06f64b222f5cb72740Chris Lattner#include "llvm/Support/Compiler.h" 34752272a5e553313f7b0397a06a23b4fe8ac013c4Evan Cheng#include "llvm/Support/Debug.h" 351cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar#include "llvm/Support/raw_ostream.h" 36551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 37551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/STLExtras.h" 3827f291600b04c382c390b16fdacd52b910b9164dChris Lattner#include <algorithm> 3934d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenosusing namespace llvm; 4034d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos 4101afdb3a45f63af540b43b414c6094220a8f91e7Jakob Stoklund OlesenSTATISTIC(NumSpillSlots, "Number of spill slots allocated"); 4201afdb3a45f63af540b43b414c6094220a8f91e7Jakob Stoklund OlesenSTATISTIC(NumIdCopies, "Number of identity moves eliminated after rewriting"); 43844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 448c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner//===----------------------------------------------------------------------===// 458c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner// VirtRegMap implementation 468c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner//===----------------------------------------------------------------------===// 478c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 4849c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Andersonchar VirtRegMap::ID = 0; 4949c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson 50ce665bd2e2b581ab0858d1afe359192bac96b868Owen AndersonINITIALIZE_PASS(VirtRegMap, "virtregmap", "Virtual Register Map", false, false) 5149c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson 5249c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Andersonbool VirtRegMap::runOnMachineFunction(MachineFunction &mf) { 5390f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng MRI = &mf.getRegInfo(); 5449c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson TII = mf.getTarget().getInstrInfo(); 55fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump TRI = mf.getTarget().getRegisterInfo(); 5649c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson MF = &mf; 57233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 5849c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson Virt2PhysMap.clear(); 5949c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson Virt2StackSlotMap.clear(); 6049c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson Virt2SplitMap.clear(); 61fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump 622926869b4a083fc951484de03a9867eabf81e880Chris Lattner grow(); 6349c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson return false; 642926869b4a083fc951484de03a9867eabf81e880Chris Lattner} 652926869b4a083fc951484de03a9867eabf81e880Chris Lattner 668c4d88d3697835371ecf6823f4142af13603ad2dChris Lattnervoid VirtRegMap::grow() { 6742e9c963921776cb498c33b6c6c03f29971316f3Jakob Stoklund Olesen unsigned NumRegs = MF->getRegInfo().getNumVirtRegs(); 6842e9c963921776cb498c33b6c6c03f29971316f3Jakob Stoklund Olesen Virt2PhysMap.resize(NumRegs); 6942e9c963921776cb498c33b6c6c03f29971316f3Jakob Stoklund Olesen Virt2StackSlotMap.resize(NumRegs); 7042e9c963921776cb498c33b6c6c03f29971316f3Jakob Stoklund Olesen Virt2SplitMap.resize(NumRegs); 7134d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos} 7234d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos 73b55e91e08738b804f17109a49881e51b69e91299Jakob Stoklund Olesenunsigned VirtRegMap::createSpillSlot(const TargetRegisterClass *RC) { 74b55e91e08738b804f17109a49881e51b69e91299Jakob Stoklund Olesen int SS = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(), 75b55e91e08738b804f17109a49881e51b69e91299Jakob Stoklund Olesen RC->getAlignment()); 7601afdb3a45f63af540b43b414c6094220a8f91e7Jakob Stoklund Olesen ++NumSpillSlots; 77b55e91e08738b804f17109a49881e51b69e91299Jakob Stoklund Olesen return SS; 78b55e91e08738b804f17109a49881e51b69e91299Jakob Stoklund Olesen} 79b55e91e08738b804f17109a49881e51b69e91299Jakob Stoklund Olesen 8090f95f88c6ce09c6744777dc9d140c3c77203b92Evan Chengunsigned VirtRegMap::getRegAllocPref(unsigned virtReg) { 81358dec51804ee52e47ea3a47c9248086e458ad7cEvan Cheng std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(virtReg); 82358dec51804ee52e47ea3a47c9248086e458ad7cEvan Cheng unsigned physReg = Hint.second; 83c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (TargetRegisterInfo::isVirtualRegister(physReg) && hasPhys(physReg)) 84358dec51804ee52e47ea3a47c9248086e458ad7cEvan Cheng physReg = getPhys(physReg); 85358dec51804ee52e47ea3a47c9248086e458ad7cEvan Cheng if (Hint.first == 0) 86c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen return (TargetRegisterInfo::isPhysicalRegister(physReg)) 87358dec51804ee52e47ea3a47c9248086e458ad7cEvan Cheng ? physReg : 0; 88358dec51804ee52e47ea3a47c9248086e458ad7cEvan Cheng return TRI->ResolveRegAllocHint(Hint.first, physReg, *MF); 8990f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng} 9090f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng 918c4d88d3697835371ecf6823f4142af13603ad2dChris Lattnerint VirtRegMap::assignVirt2StackSlot(unsigned virtReg) { 926f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman assert(TargetRegisterInfo::isVirtualRegister(virtReg)); 937f690e625807b9320bf4ae437b8f35258acc99deChris Lattner assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT && 948c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner "attempt to assign stack slot to already spilled register"); 9549c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson const TargetRegisterClass* RC = MF->getRegInfo().getRegClass(virtReg); 96b55e91e08738b804f17109a49881e51b69e91299Jakob Stoklund Olesen return Virt2StackSlotMap[virtReg] = createSpillSlot(RC); 9734d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos} 9834d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos 99d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Chengvoid VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int SS) { 1006f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman assert(TargetRegisterInfo::isVirtualRegister(virtReg)); 1017f690e625807b9320bf4ae437b8f35258acc99deChris Lattner assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT && 1028c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner "attempt to assign stack slot to already spilled register"); 103d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng assert((SS >= 0 || 10449c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson (SS >= MF->getFrameInfo()->getObjectIndexBegin())) && 1059193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng "illegal fixed frame index"); 106d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng Virt2StackSlotMap[virtReg] = SS; 10738af59a43c4176d8f34bd26faeb18b23080a1d9bAlkis Evlogimenos} 10838af59a43c4176d8f34bd26faeb18b23080a1d9bAlkis Evlogimenos 10905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesenvoid VirtRegMap::print(raw_ostream &OS, const Module*) const { 11005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen OS << "********** REGISTER MAP **********\n"; 11105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 11205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 11305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen if (Virt2PhysMap[Reg] != (unsigned)VirtRegMap::NO_PHYS_REG) { 11405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen OS << '[' << PrintReg(Reg, TRI) << " -> " 11505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen << PrintReg(Virt2PhysMap[Reg], TRI) << "] " 11605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen << MRI->getRegClass(Reg)->getName() << "\n"; 11705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen } 11805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen } 11905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 12005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 12105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 12205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen if (Virt2StackSlotMap[Reg] != VirtRegMap::NO_STACK_SLOT) { 12305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen OS << '[' << PrintReg(Reg, TRI) << " -> fi#" << Virt2StackSlotMap[Reg] 12405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen << "] " << MRI->getRegClass(Reg)->getName() << "\n"; 12505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen } 12605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen } 12705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen OS << '\n'; 12805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen} 12905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 130b720be6a50f4e1b3280d2b029ee38dda14577525Manman Ren#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 13105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesenvoid VirtRegMap::dump() const { 13205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen print(dbgs()); 13305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen} 13477e300e8f0b8db8eec448cae9c87d7c5bfad9757Manman Ren#endif 13505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 13605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 13705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen// VirtRegRewriter 13805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 13905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen// 14005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen// The VirtRegRewriter is the last of the register allocator passes. 14105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen// It rewrites virtual registers to physical registers as specified in the 14205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen// VirtRegMap analysis. It also updates live-in information on basic blocks 14305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen// according to LiveIntervals. 14405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen// 14505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesennamespace { 14605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesenclass VirtRegRewriter : public MachineFunctionPass { 14705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen MachineFunction *MF; 14805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen const TargetMachine *TM; 14905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen const TargetRegisterInfo *TRI; 15005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen const TargetInstrInfo *TII; 15105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen MachineRegisterInfo *MRI; 15205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen SlotIndexes *Indexes; 15305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen LiveIntervals *LIS; 15405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen VirtRegMap *VRM; 15505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 15605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen void rewrite(); 15705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen void addMBBLiveIns(); 15805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesenpublic: 15905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen static char ID; 16005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen VirtRegRewriter() : MachineFunctionPass(ID) {} 16105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 16205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen virtual void getAnalysisUsage(AnalysisUsage &AU) const; 16305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 16405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen virtual bool runOnMachineFunction(MachineFunction&); 16505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen}; 16605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen} // end anonymous namespace 16705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 16805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesenchar &llvm::VirtRegRewriterID = VirtRegRewriter::ID; 16905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 17005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund OlesenINITIALIZE_PASS_BEGIN(VirtRegRewriter, "virtregrewriter", 17105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen "Virtual Register Rewriter", false, false) 17205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund OlesenINITIALIZE_PASS_DEPENDENCY(SlotIndexes) 17305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund OlesenINITIALIZE_PASS_DEPENDENCY(LiveIntervals) 17405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund OlesenINITIALIZE_PASS_DEPENDENCY(LiveDebugVariables) 175bb36a438722d4d56febc07c6472c8446bb6faafeEvan ChengINITIALIZE_PASS_DEPENDENCY(LiveStacks) 17605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund OlesenINITIALIZE_PASS_DEPENDENCY(VirtRegMap) 17705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund OlesenINITIALIZE_PASS_END(VirtRegRewriter, "virtregrewriter", 17805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen "Virtual Register Rewriter", false, false) 17905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 18005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesenchar VirtRegRewriter::ID = 0; 18105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 18205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesenvoid VirtRegRewriter::getAnalysisUsage(AnalysisUsage &AU) const { 18305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen AU.setPreservesCFG(); 18405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen AU.addRequired<LiveIntervals>(); 18505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen AU.addRequired<SlotIndexes>(); 18605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen AU.addPreserved<SlotIndexes>(); 18705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen AU.addRequired<LiveDebugVariables>(); 188bb36a438722d4d56febc07c6472c8446bb6faafeEvan Cheng AU.addRequired<LiveStacks>(); 189bb36a438722d4d56febc07c6472c8446bb6faafeEvan Cheng AU.addPreserved<LiveStacks>(); 19005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen AU.addRequired<VirtRegMap>(); 19105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen MachineFunctionPass::getAnalysisUsage(AU); 19205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen} 19305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 19405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesenbool VirtRegRewriter::runOnMachineFunction(MachineFunction &fn) { 19505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen MF = &fn; 19605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen TM = &MF->getTarget(); 19705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen TRI = TM->getRegisterInfo(); 19805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen TII = TM->getInstrInfo(); 19905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen MRI = &MF->getRegInfo(); 20005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen Indexes = &getAnalysis<SlotIndexes>(); 20105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen LIS = &getAnalysis<LiveIntervals>(); 20205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen VRM = &getAnalysis<VirtRegMap>(); 203ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen DEBUG(dbgs() << "********** REWRITE VIRTUAL REGISTERS **********\n" 204ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen << "********** Function: " 20596601ca332ab388754ca4673be8973396fea2dddCraig Topper << MF->getName() << '\n'); 20605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen DEBUG(VRM->dump()); 20705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 20805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen // Add kill flags while we still have virtual registers. 209e617ccb80da76821379bbff4a2fdcd09e8401e8bJakob Stoklund Olesen LIS->addKillFlags(VRM); 21005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 211fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen // Live-in lists on basic blocks are required for physregs. 212fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen addMBBLiveIns(); 213fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen 21405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen // Rewrite virtual registers. 21505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen rewrite(); 21605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 21705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen // Write out new DBG_VALUE instructions. 21805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen getAnalysis<LiveDebugVariables>().emitDebugValues(VRM); 21905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 22005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen // All machine operands and other references to virtual registers have been 22105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen // replaced. Remove the virtual registers and release all the transient data. 22205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen VRM->clearAllVirt(); 22305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen MRI->clearVirtRegs(); 22405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen return true; 22505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen} 22605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 227fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen// Compute MBB live-in lists from virtual register live ranges and their 228fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen// assignments. 229fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesenvoid VirtRegRewriter::addMBBLiveIns() { 230fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen SmallVector<MachineBasicBlock*, 16> LiveIn; 231fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen for (unsigned Idx = 0, IdxE = MRI->getNumVirtRegs(); Idx != IdxE; ++Idx) { 232fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen unsigned VirtReg = TargetRegisterInfo::index2VirtReg(Idx); 233fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen if (MRI->reg_nodbg_empty(VirtReg)) 234fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen continue; 235fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen LiveInterval &LI = LIS->getInterval(VirtReg); 236fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen if (LI.empty() || LIS->intervalIsInOneMBB(LI)) 237fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen continue; 238fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen // This is a virtual register that is live across basic blocks. Its 239fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen // assigned PhysReg must be marked as live-in to those blocks. 240fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen unsigned PhysReg = VRM->getPhys(VirtReg); 241fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen assert(PhysReg != VirtRegMap::NO_PHYS_REG && "Unmapped virtual register."); 242fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen 243fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen // Scan the segments of LI. 244fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen for (LiveInterval::const_iterator I = LI.begin(), E = LI.end(); I != E; 245fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen ++I) { 246fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen if (!Indexes->findLiveInMBBs(I->start, I->end, LiveIn)) 247fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen continue; 248fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) 249fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen if (!LiveIn[i]->isLiveIn(PhysReg)) 250fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen LiveIn[i]->addLiveIn(PhysReg); 251fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen LiveIn.clear(); 252fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen } 253fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen } 254fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen} 255fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen 25605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesenvoid VirtRegRewriter::rewrite() { 25793e110ba344ddc901dfb2af61d9c21002d8d3080Jakob Stoklund Olesen SmallVector<unsigned, 8> SuperDeads; 25893e110ba344ddc901dfb2af61d9c21002d8d3080Jakob Stoklund Olesen SmallVector<unsigned, 8> SuperDefs; 259ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen SmallVector<unsigned, 8> SuperKills; 260ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen 261ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end(); 262ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen MBBI != MBBE; ++MBBI) { 263ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen DEBUG(MBBI->print(dbgs(), Indexes)); 2643f9c251e40dac7503f7ae455fab89bdc359c7b85Evan Cheng for (MachineBasicBlock::instr_iterator 2653f9c251e40dac7503f7ae455fab89bdc359c7b85Evan Cheng MII = MBBI->instr_begin(), MIE = MBBI->instr_end(); MII != MIE;) { 266ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen MachineInstr *MI = MII; 267ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen ++MII; 268ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen 269ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen for (MachineInstr::mop_iterator MOI = MI->operands_begin(), 270ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen MOE = MI->operands_end(); MOI != MOE; ++MOI) { 271ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen MachineOperand &MO = *MOI; 272d9f0ff56a1878347fe5a0f162ef8c2ef2b63aeb5Jakob Stoklund Olesen 273d9f0ff56a1878347fe5a0f162ef8c2ef2b63aeb5Jakob Stoklund Olesen // Make sure MRI knows about registers clobbered by regmasks. 274d9f0ff56a1878347fe5a0f162ef8c2ef2b63aeb5Jakob Stoklund Olesen if (MO.isRegMask()) 275d9f0ff56a1878347fe5a0f162ef8c2ef2b63aeb5Jakob Stoklund Olesen MRI->addPhysRegsUsedFromRegMask(MO.getRegMask()); 276d9f0ff56a1878347fe5a0f162ef8c2ef2b63aeb5Jakob Stoklund Olesen 277ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg())) 278ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen continue; 279ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen unsigned VirtReg = MO.getReg(); 28005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen unsigned PhysReg = VRM->getPhys(VirtReg); 28105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen assert(PhysReg != VirtRegMap::NO_PHYS_REG && 28205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen "Instruction uses unmapped VirtReg"); 283fb9ebbf236974beac31705eaeb9f50ab585af6abJakob Stoklund Olesen assert(!MRI->isReserved(PhysReg) && "Reserved register assignment"); 284ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen 285ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen // Preserve semantics of sub-register operands. 286ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen if (MO.getSubReg()) { 287ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen // A virtual register kill refers to the whole register, so we may 288200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen // have to add <imp-use,kill> operands for the super-register. A 289200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen // partial redef always kills and redefines the super-register. 290200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen if (MO.readsReg() && (MO.isDef() || MO.isKill())) 291200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen SuperKills.push_back(PhysReg); 292200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen 293200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen if (MO.isDef()) { 294200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen // The <def,undef> flag only makes sense for sub-register defs, and 295200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen // we are substituting a full physreg. An <imp-use,kill> operand 296200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen // from the SuperKills list will represent the partial read of the 297200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen // super-register. 298200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen MO.setIsUndef(false); 299200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen 300200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen // Also add implicit defs for the super-register. 301200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen if (MO.isDead()) 302200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen SuperDeads.push_back(PhysReg); 303200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen else 304200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen SuperDefs.push_back(PhysReg); 305200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen } 306ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen 307ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen // PhysReg operands cannot have subregister indexes. 308ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen PhysReg = TRI->getSubReg(PhysReg, MO.getSubReg()); 309ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen assert(PhysReg && "Invalid SubReg for physical register"); 310ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen MO.setSubReg(0); 311ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen } 312ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen // Rewrite. Note we could have used MachineOperand::substPhysReg(), but 313ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen // we need the inlining here. 314ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen MO.setReg(PhysReg); 315ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen } 316ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen 317ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen // Add any missing super-register kills after rewriting the whole 318ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen // instruction. 319ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen while (!SuperKills.empty()) 320ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen MI->addRegisterKilled(SuperKills.pop_back_val(), TRI, true); 321ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen 32293e110ba344ddc901dfb2af61d9c21002d8d3080Jakob Stoklund Olesen while (!SuperDeads.empty()) 32393e110ba344ddc901dfb2af61d9c21002d8d3080Jakob Stoklund Olesen MI->addRegisterDead(SuperDeads.pop_back_val(), TRI, true); 32493e110ba344ddc901dfb2af61d9c21002d8d3080Jakob Stoklund Olesen 32593e110ba344ddc901dfb2af61d9c21002d8d3080Jakob Stoklund Olesen while (!SuperDefs.empty()) 32693e110ba344ddc901dfb2af61d9c21002d8d3080Jakob Stoklund Olesen MI->addRegisterDefined(SuperDefs.pop_back_val(), TRI); 32793e110ba344ddc901dfb2af61d9c21002d8d3080Jakob Stoklund Olesen 328ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen DEBUG(dbgs() << "> " << *MI); 329ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen 330ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen // Finally, remove any identity copies. 331ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen if (MI->isIdentityCopy()) { 332cf5e5f3cc08a3c7ede5b423ee4b18586cb1079e9Jakob Stoklund Olesen ++NumIdCopies; 333280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen if (MI->getNumOperands() == 2) { 334280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen DEBUG(dbgs() << "Deleting identity copy.\n"); 335280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen if (Indexes) 336280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen Indexes->removeMachineInstrFromMaps(MI); 337280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen // It's safe to erase MI because MII has already been incremented. 338280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen MI->eraseFromParent(); 339280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen } else { 340280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen // Transform identity copy to a KILL to deal with subregisters. 341280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen MI->setDesc(TII->get(TargetOpcode::KILL)); 342280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen DEBUG(dbgs() << "Identity copy: " << *MI); 343280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen } 344ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen } 345ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen } 346ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen } 347ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen 348ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen // Tell MRI about physical registers in use. 349ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen for (unsigned Reg = 1, RegE = TRI->getNumRegs(); Reg != RegE; ++Reg) 350ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen if (!MRI->reg_nodbg_empty(Reg)) 351ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen MRI->setPhysRegUsed(Reg); 352ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen} 353