VirtRegMap.cpp revision 96601ca332ab388754ca4673be8973396fea2ddd
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" 2334d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos#include "llvm/CodeGen/MachineFrameInfo.h" 248c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner#include "llvm/CodeGen/MachineFunction.h" 254cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng#include "llvm/CodeGen/MachineInstrBuilder.h" 2684bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner#include "llvm/CodeGen/MachineRegisterInfo.h" 2705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen#include "llvm/CodeGen/Passes.h" 2834d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos#include "llvm/Target/TargetMachine.h" 290d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos#include "llvm/Target/TargetInstrInfo.h" 30fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump#include "llvm/Target/TargetRegisterInfo.h" 31551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 32a4f0b3a084d120cfc5b5bb06f64b222f5cb72740Chris Lattner#include "llvm/Support/Compiler.h" 33752272a5e553313f7b0397a06a23b4fe8ac013c4Evan Cheng#include "llvm/Support/Debug.h" 341cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar#include "llvm/Support/raw_ostream.h" 35551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 36551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/STLExtras.h" 3727f291600b04c382c390b16fdacd52b910b9164dChris Lattner#include <algorithm> 3834d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenosusing namespace llvm; 3934d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos 4001afdb3a45f63af540b43b414c6094220a8f91e7Jakob Stoklund OlesenSTATISTIC(NumSpillSlots, "Number of spill slots allocated"); 4101afdb3a45f63af540b43b414c6094220a8f91e7Jakob Stoklund OlesenSTATISTIC(NumIdCopies, "Number of identity moves eliminated after rewriting"); 42844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 438c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner//===----------------------------------------------------------------------===// 448c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner// VirtRegMap implementation 458c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner//===----------------------------------------------------------------------===// 468c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 4749c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Andersonchar VirtRegMap::ID = 0; 4849c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson 49ce665bd2e2b581ab0858d1afe359192bac96b868Owen AndersonINITIALIZE_PASS(VirtRegMap, "virtregmap", "Virtual Register Map", false, false) 5049c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson 5149c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Andersonbool VirtRegMap::runOnMachineFunction(MachineFunction &mf) { 5290f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng MRI = &mf.getRegInfo(); 5349c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson TII = mf.getTarget().getInstrInfo(); 54fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump TRI = mf.getTarget().getRegisterInfo(); 5549c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson MF = &mf; 56233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 5749c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson Virt2PhysMap.clear(); 5849c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson Virt2StackSlotMap.clear(); 5949c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson Virt2SplitMap.clear(); 60fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump 612926869b4a083fc951484de03a9867eabf81e880Chris Lattner grow(); 6249c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson return false; 632926869b4a083fc951484de03a9867eabf81e880Chris Lattner} 642926869b4a083fc951484de03a9867eabf81e880Chris Lattner 658c4d88d3697835371ecf6823f4142af13603ad2dChris Lattnervoid VirtRegMap::grow() { 6642e9c963921776cb498c33b6c6c03f29971316f3Jakob Stoklund Olesen unsigned NumRegs = MF->getRegInfo().getNumVirtRegs(); 6742e9c963921776cb498c33b6c6c03f29971316f3Jakob Stoklund Olesen Virt2PhysMap.resize(NumRegs); 6842e9c963921776cb498c33b6c6c03f29971316f3Jakob Stoklund Olesen Virt2StackSlotMap.resize(NumRegs); 6942e9c963921776cb498c33b6c6c03f29971316f3Jakob Stoklund Olesen Virt2SplitMap.resize(NumRegs); 7034d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos} 7134d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos 72b55e91e08738b804f17109a49881e51b69e91299Jakob Stoklund Olesenunsigned VirtRegMap::createSpillSlot(const TargetRegisterClass *RC) { 73b55e91e08738b804f17109a49881e51b69e91299Jakob Stoklund Olesen int SS = MF->getFrameInfo()->CreateSpillStackObject(RC->getSize(), 74b55e91e08738b804f17109a49881e51b69e91299Jakob Stoklund Olesen RC->getAlignment()); 7501afdb3a45f63af540b43b414c6094220a8f91e7Jakob Stoklund Olesen ++NumSpillSlots; 76b55e91e08738b804f17109a49881e51b69e91299Jakob Stoklund Olesen return SS; 77b55e91e08738b804f17109a49881e51b69e91299Jakob Stoklund Olesen} 78b55e91e08738b804f17109a49881e51b69e91299Jakob Stoklund Olesen 7990f95f88c6ce09c6744777dc9d140c3c77203b92Evan Chengunsigned VirtRegMap::getRegAllocPref(unsigned virtReg) { 80358dec51804ee52e47ea3a47c9248086e458ad7cEvan Cheng std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(virtReg); 81358dec51804ee52e47ea3a47c9248086e458ad7cEvan Cheng unsigned physReg = Hint.second; 82c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (TargetRegisterInfo::isVirtualRegister(physReg) && hasPhys(physReg)) 83358dec51804ee52e47ea3a47c9248086e458ad7cEvan Cheng physReg = getPhys(physReg); 84358dec51804ee52e47ea3a47c9248086e458ad7cEvan Cheng if (Hint.first == 0) 85c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen return (TargetRegisterInfo::isPhysicalRegister(physReg)) 86358dec51804ee52e47ea3a47c9248086e458ad7cEvan Cheng ? physReg : 0; 87358dec51804ee52e47ea3a47c9248086e458ad7cEvan Cheng return TRI->ResolveRegAllocHint(Hint.first, physReg, *MF); 8890f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng} 8990f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng 908c4d88d3697835371ecf6823f4142af13603ad2dChris Lattnerint VirtRegMap::assignVirt2StackSlot(unsigned virtReg) { 916f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman assert(TargetRegisterInfo::isVirtualRegister(virtReg)); 927f690e625807b9320bf4ae437b8f35258acc99deChris Lattner assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT && 938c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner "attempt to assign stack slot to already spilled register"); 9449c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson const TargetRegisterClass* RC = MF->getRegInfo().getRegClass(virtReg); 95b55e91e08738b804f17109a49881e51b69e91299Jakob Stoklund Olesen return Virt2StackSlotMap[virtReg] = createSpillSlot(RC); 9634d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos} 9734d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos 98d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Chengvoid VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int SS) { 996f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman assert(TargetRegisterInfo::isVirtualRegister(virtReg)); 1007f690e625807b9320bf4ae437b8f35258acc99deChris Lattner assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT && 1018c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner "attempt to assign stack slot to already spilled register"); 102d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng assert((SS >= 0 || 10349c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson (SS >= MF->getFrameInfo()->getObjectIndexBegin())) && 1049193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng "illegal fixed frame index"); 105d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng Virt2StackSlotMap[virtReg] = SS; 10638af59a43c4176d8f34bd26faeb18b23080a1d9bAlkis Evlogimenos} 10738af59a43c4176d8f34bd26faeb18b23080a1d9bAlkis Evlogimenos 10805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesenvoid VirtRegMap::print(raw_ostream &OS, const Module*) const { 10905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen OS << "********** REGISTER MAP **********\n"; 11005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 11105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 11205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen if (Virt2PhysMap[Reg] != (unsigned)VirtRegMap::NO_PHYS_REG) { 11305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen OS << '[' << PrintReg(Reg, TRI) << " -> " 11405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen << PrintReg(Virt2PhysMap[Reg], TRI) << "] " 11505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen << MRI->getRegClass(Reg)->getName() << "\n"; 11605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen } 11705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen } 11805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 11905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 12005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 12105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen if (Virt2StackSlotMap[Reg] != VirtRegMap::NO_STACK_SLOT) { 12205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen OS << '[' << PrintReg(Reg, TRI) << " -> fi#" << Virt2StackSlotMap[Reg] 12305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen << "] " << MRI->getRegClass(Reg)->getName() << "\n"; 12405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen } 12505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen } 12605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen OS << '\n'; 12705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen} 12805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 12905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesenvoid VirtRegMap::dump() const { 13005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen print(dbgs()); 13105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen} 13205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 13305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 13405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen// VirtRegRewriter 13505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 13605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen// 13705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen// The VirtRegRewriter is the last of the register allocator passes. 13805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen// It rewrites virtual registers to physical registers as specified in the 13905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen// VirtRegMap analysis. It also updates live-in information on basic blocks 14005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen// according to LiveIntervals. 14105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen// 14205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesennamespace { 14305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesenclass VirtRegRewriter : public MachineFunctionPass { 14405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen MachineFunction *MF; 14505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen const TargetMachine *TM; 14605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen const TargetRegisterInfo *TRI; 14705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen const TargetInstrInfo *TII; 14805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen MachineRegisterInfo *MRI; 14905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen SlotIndexes *Indexes; 15005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen LiveIntervals *LIS; 15105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen VirtRegMap *VRM; 15205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 15305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen void rewrite(); 15405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen void addMBBLiveIns(); 15505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesenpublic: 15605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen static char ID; 15705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen VirtRegRewriter() : MachineFunctionPass(ID) {} 15805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 15905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen virtual void getAnalysisUsage(AnalysisUsage &AU) const; 16005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 16105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen virtual bool runOnMachineFunction(MachineFunction&); 16205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen}; 16305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen} // end anonymous namespace 16405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 16505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesenchar &llvm::VirtRegRewriterID = VirtRegRewriter::ID; 16605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 16705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund OlesenINITIALIZE_PASS_BEGIN(VirtRegRewriter, "virtregrewriter", 16805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen "Virtual Register Rewriter", false, false) 16905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund OlesenINITIALIZE_PASS_DEPENDENCY(SlotIndexes) 17005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund OlesenINITIALIZE_PASS_DEPENDENCY(LiveIntervals) 17105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund OlesenINITIALIZE_PASS_DEPENDENCY(LiveDebugVariables) 17205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund OlesenINITIALIZE_PASS_DEPENDENCY(VirtRegMap) 17305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund OlesenINITIALIZE_PASS_END(VirtRegRewriter, "virtregrewriter", 17405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen "Virtual Register Rewriter", false, false) 17505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 17605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesenchar VirtRegRewriter::ID = 0; 17705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 17805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesenvoid VirtRegRewriter::getAnalysisUsage(AnalysisUsage &AU) const { 17905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen AU.setPreservesCFG(); 18005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen AU.addRequired<LiveIntervals>(); 18105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen AU.addRequired<SlotIndexes>(); 18205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen AU.addPreserved<SlotIndexes>(); 18305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen AU.addRequired<LiveDebugVariables>(); 18405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen AU.addRequired<VirtRegMap>(); 18505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen MachineFunctionPass::getAnalysisUsage(AU); 18605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen} 18705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 18805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesenbool VirtRegRewriter::runOnMachineFunction(MachineFunction &fn) { 18905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen MF = &fn; 19005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen TM = &MF->getTarget(); 19105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen TRI = TM->getRegisterInfo(); 19205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen TII = TM->getInstrInfo(); 19305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen MRI = &MF->getRegInfo(); 19405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen Indexes = &getAnalysis<SlotIndexes>(); 19505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen LIS = &getAnalysis<LiveIntervals>(); 19605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen VRM = &getAnalysis<VirtRegMap>(); 197ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen DEBUG(dbgs() << "********** REWRITE VIRTUAL REGISTERS **********\n" 198ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen << "********** Function: " 19996601ca332ab388754ca4673be8973396fea2dddCraig Topper << MF->getName() << '\n'); 20005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen DEBUG(VRM->dump()); 20105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 20205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen // Add kill flags while we still have virtual registers. 20305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen LIS->addKillFlags(); 20405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 205fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen // Live-in lists on basic blocks are required for physregs. 206fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen addMBBLiveIns(); 207fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen 20805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen // Rewrite virtual registers. 20905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen rewrite(); 21005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 21105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen // Write out new DBG_VALUE instructions. 21205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen getAnalysis<LiveDebugVariables>().emitDebugValues(VRM); 21305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 21405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen // All machine operands and other references to virtual registers have been 21505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen // replaced. Remove the virtual registers and release all the transient data. 21605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen VRM->clearAllVirt(); 21705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen MRI->clearVirtRegs(); 21805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen return true; 21905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen} 22005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 221fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen// Compute MBB live-in lists from virtual register live ranges and their 222fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen// assignments. 223fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesenvoid VirtRegRewriter::addMBBLiveIns() { 224fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen SmallVector<MachineBasicBlock*, 16> LiveIn; 225fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen for (unsigned Idx = 0, IdxE = MRI->getNumVirtRegs(); Idx != IdxE; ++Idx) { 226fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen unsigned VirtReg = TargetRegisterInfo::index2VirtReg(Idx); 227fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen if (MRI->reg_nodbg_empty(VirtReg)) 228fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen continue; 229fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen LiveInterval &LI = LIS->getInterval(VirtReg); 230fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen if (LI.empty() || LIS->intervalIsInOneMBB(LI)) 231fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen continue; 232fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen // This is a virtual register that is live across basic blocks. Its 233fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen // assigned PhysReg must be marked as live-in to those blocks. 234fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen unsigned PhysReg = VRM->getPhys(VirtReg); 235fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen assert(PhysReg != VirtRegMap::NO_PHYS_REG && "Unmapped virtual register."); 236fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen 237fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen // Scan the segments of LI. 238fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen for (LiveInterval::const_iterator I = LI.begin(), E = LI.end(); I != E; 239fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen ++I) { 240fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen if (!Indexes->findLiveInMBBs(I->start, I->end, LiveIn)) 241fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen continue; 242fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) 243fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen if (!LiveIn[i]->isLiveIn(PhysReg)) 244fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen LiveIn[i]->addLiveIn(PhysReg); 245fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen LiveIn.clear(); 246fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen } 247fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen } 248fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen} 249fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen 25005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesenvoid VirtRegRewriter::rewrite() { 25193e110ba344ddc901dfb2af61d9c21002d8d3080Jakob Stoklund Olesen SmallVector<unsigned, 8> SuperDeads; 25293e110ba344ddc901dfb2af61d9c21002d8d3080Jakob Stoklund Olesen SmallVector<unsigned, 8> SuperDefs; 253ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen SmallVector<unsigned, 8> SuperKills; 2542d44e02533cdc2ae011121ef651dda93769ced2bJakob Stoklund Olesen#ifndef NDEBUG 2552d44e02533cdc2ae011121ef651dda93769ced2bJakob Stoklund Olesen BitVector Reserved = TRI->getReservedRegs(*MF); 2562d44e02533cdc2ae011121ef651dda93769ced2bJakob Stoklund Olesen#endif 257ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen 258ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end(); 259ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen MBBI != MBBE; ++MBBI) { 260ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen DEBUG(MBBI->print(dbgs(), Indexes)); 2613f9c251e40dac7503f7ae455fab89bdc359c7b85Evan Cheng for (MachineBasicBlock::instr_iterator 2623f9c251e40dac7503f7ae455fab89bdc359c7b85Evan Cheng MII = MBBI->instr_begin(), MIE = MBBI->instr_end(); MII != MIE;) { 263ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen MachineInstr *MI = MII; 264ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen ++MII; 265ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen 266ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen for (MachineInstr::mop_iterator MOI = MI->operands_begin(), 267ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen MOE = MI->operands_end(); MOI != MOE; ++MOI) { 268ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen MachineOperand &MO = *MOI; 269d9f0ff56a1878347fe5a0f162ef8c2ef2b63aeb5Jakob Stoklund Olesen 270d9f0ff56a1878347fe5a0f162ef8c2ef2b63aeb5Jakob Stoklund Olesen // Make sure MRI knows about registers clobbered by regmasks. 271d9f0ff56a1878347fe5a0f162ef8c2ef2b63aeb5Jakob Stoklund Olesen if (MO.isRegMask()) 272d9f0ff56a1878347fe5a0f162ef8c2ef2b63aeb5Jakob Stoklund Olesen MRI->addPhysRegsUsedFromRegMask(MO.getRegMask()); 273d9f0ff56a1878347fe5a0f162ef8c2ef2b63aeb5Jakob Stoklund Olesen 274ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg())) 275ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen continue; 276ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen unsigned VirtReg = MO.getReg(); 27705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen unsigned PhysReg = VRM->getPhys(VirtReg); 27805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen assert(PhysReg != VirtRegMap::NO_PHYS_REG && 27905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen "Instruction uses unmapped VirtReg"); 2802d44e02533cdc2ae011121ef651dda93769ced2bJakob Stoklund Olesen assert(!Reserved.test(PhysReg) && "Reserved register assignment"); 281ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen 282ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen // Preserve semantics of sub-register operands. 283ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen if (MO.getSubReg()) { 284ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen // A virtual register kill refers to the whole register, so we may 285200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen // have to add <imp-use,kill> operands for the super-register. A 286200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen // partial redef always kills and redefines the super-register. 287200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen if (MO.readsReg() && (MO.isDef() || MO.isKill())) 288200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen SuperKills.push_back(PhysReg); 289200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen 290200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen if (MO.isDef()) { 291200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen // The <def,undef> flag only makes sense for sub-register defs, and 292200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen // we are substituting a full physreg. An <imp-use,kill> operand 293200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen // from the SuperKills list will represent the partial read of the 294200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen // super-register. 295200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen MO.setIsUndef(false); 296200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen 297200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen // Also add implicit defs for the super-register. 298200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen if (MO.isDead()) 299200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen SuperDeads.push_back(PhysReg); 300200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen else 301200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen SuperDefs.push_back(PhysReg); 302200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen } 303ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen 304ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen // PhysReg operands cannot have subregister indexes. 305ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen PhysReg = TRI->getSubReg(PhysReg, MO.getSubReg()); 306ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen assert(PhysReg && "Invalid SubReg for physical register"); 307ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen MO.setSubReg(0); 308ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen } 309ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen // Rewrite. Note we could have used MachineOperand::substPhysReg(), but 310ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen // we need the inlining here. 311ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen MO.setReg(PhysReg); 312ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen } 313ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen 314ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen // Add any missing super-register kills after rewriting the whole 315ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen // instruction. 316ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen while (!SuperKills.empty()) 317ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen MI->addRegisterKilled(SuperKills.pop_back_val(), TRI, true); 318ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen 31993e110ba344ddc901dfb2af61d9c21002d8d3080Jakob Stoklund Olesen while (!SuperDeads.empty()) 32093e110ba344ddc901dfb2af61d9c21002d8d3080Jakob Stoklund Olesen MI->addRegisterDead(SuperDeads.pop_back_val(), TRI, true); 32193e110ba344ddc901dfb2af61d9c21002d8d3080Jakob Stoklund Olesen 32293e110ba344ddc901dfb2af61d9c21002d8d3080Jakob Stoklund Olesen while (!SuperDefs.empty()) 32393e110ba344ddc901dfb2af61d9c21002d8d3080Jakob Stoklund Olesen MI->addRegisterDefined(SuperDefs.pop_back_val(), TRI); 32493e110ba344ddc901dfb2af61d9c21002d8d3080Jakob Stoklund Olesen 325ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen DEBUG(dbgs() << "> " << *MI); 326ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen 327ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen // Finally, remove any identity copies. 328ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen if (MI->isIdentityCopy()) { 329cf5e5f3cc08a3c7ede5b423ee4b18586cb1079e9Jakob Stoklund Olesen ++NumIdCopies; 330280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen if (MI->getNumOperands() == 2) { 331280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen DEBUG(dbgs() << "Deleting identity copy.\n"); 332280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen if (Indexes) 333280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen Indexes->removeMachineInstrFromMaps(MI); 334280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen // It's safe to erase MI because MII has already been incremented. 335280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen MI->eraseFromParent(); 336280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen } else { 337280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen // Transform identity copy to a KILL to deal with subregisters. 338280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen MI->setDesc(TII->get(TargetOpcode::KILL)); 339280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen DEBUG(dbgs() << "Identity copy: " << *MI); 340280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen } 341ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen } 342ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen } 343ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen } 344ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen 345ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen // Tell MRI about physical registers in use. 346ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen for (unsigned Reg = 1, RegE = TRI->getNumRegs(); Reg != RegE; ++Reg) 347ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen if (!MRI->reg_nodbg_empty(Reg)) 348ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen MRI->setPhysRegUsed(Reg); 349ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen} 350