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" 201ead68d769f27f6d68d4aaeffe4199fa2cacbc95Jakob Stoklund Olesen#include "llvm/CodeGen/VirtRegMap.h" 2105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen#include "LiveDebugVariables.h" 22d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/STLExtras.h" 23d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 2405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen#include "llvm/CodeGen/LiveIntervalAnalysis.h" 25bb36a438722d4d56febc07c6472c8446bb6faafeEvan Cheng#include "llvm/CodeGen/LiveStackAnalysis.h" 2634d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos#include "llvm/CodeGen/MachineFrameInfo.h" 278c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner#include "llvm/CodeGen/MachineFunction.h" 284cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng#include "llvm/CodeGen/MachineInstrBuilder.h" 2984bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner#include "llvm/CodeGen/MachineRegisterInfo.h" 3005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen#include "llvm/CodeGen/Passes.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" 35d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetInstrInfo.h" 36d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetMachine.h" 37d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetRegisterInfo.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 80980bddfb1c26e2e9374d1645f9ae26c44742606fJakob Stoklund Olesenbool VirtRegMap::hasPreferredPhys(unsigned VirtReg) { 81980bddfb1c26e2e9374d1645f9ae26c44742606fJakob Stoklund Olesen unsigned Hint = MRI->getSimpleHint(VirtReg); 82980bddfb1c26e2e9374d1645f9ae26c44742606fJakob Stoklund Olesen if (!Hint) 83980bddfb1c26e2e9374d1645f9ae26c44742606fJakob Stoklund Olesen return 0; 84980bddfb1c26e2e9374d1645f9ae26c44742606fJakob Stoklund Olesen if (TargetRegisterInfo::isVirtualRegister(Hint)) 85980bddfb1c26e2e9374d1645f9ae26c44742606fJakob Stoklund Olesen Hint = getPhys(Hint); 86980bddfb1c26e2e9374d1645f9ae26c44742606fJakob Stoklund Olesen return getPhys(VirtReg) == Hint; 87980bddfb1c26e2e9374d1645f9ae26c44742606fJakob Stoklund Olesen} 88980bddfb1c26e2e9374d1645f9ae26c44742606fJakob Stoklund Olesen 89fc6374439edf2f74da4026f4cea8e341d092be5cJakob Stoklund Olesenbool VirtRegMap::hasKnownPreference(unsigned VirtReg) { 90fc6374439edf2f74da4026f4cea8e341d092be5cJakob Stoklund Olesen std::pair<unsigned, unsigned> Hint = MRI->getRegAllocationHint(VirtReg); 91fc6374439edf2f74da4026f4cea8e341d092be5cJakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Hint.second)) 92fc6374439edf2f74da4026f4cea8e341d092be5cJakob Stoklund Olesen return true; 93fc6374439edf2f74da4026f4cea8e341d092be5cJakob Stoklund Olesen if (TargetRegisterInfo::isVirtualRegister(Hint.second)) 94fc6374439edf2f74da4026f4cea8e341d092be5cJakob Stoklund Olesen return hasPhys(Hint.second); 95fc6374439edf2f74da4026f4cea8e341d092be5cJakob Stoklund Olesen return false; 96fc6374439edf2f74da4026f4cea8e341d092be5cJakob Stoklund Olesen} 97fc6374439edf2f74da4026f4cea8e341d092be5cJakob Stoklund Olesen 988c4d88d3697835371ecf6823f4142af13603ad2dChris Lattnerint VirtRegMap::assignVirt2StackSlot(unsigned virtReg) { 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"); 10249c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson const TargetRegisterClass* RC = MF->getRegInfo().getRegClass(virtReg); 103b55e91e08738b804f17109a49881e51b69e91299Jakob Stoklund Olesen return Virt2StackSlotMap[virtReg] = createSpillSlot(RC); 10434d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos} 10534d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos 106d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Chengvoid VirtRegMap::assignVirt2StackSlot(unsigned virtReg, int SS) { 1076f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman assert(TargetRegisterInfo::isVirtualRegister(virtReg)); 1087f690e625807b9320bf4ae437b8f35258acc99deChris Lattner assert(Virt2StackSlotMap[virtReg] == NO_STACK_SLOT && 1098c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner "attempt to assign stack slot to already spilled register"); 110d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng assert((SS >= 0 || 11149c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson (SS >= MF->getFrameInfo()->getObjectIndexBegin())) && 1129193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng "illegal fixed frame index"); 113d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng Virt2StackSlotMap[virtReg] = SS; 11438af59a43c4176d8f34bd26faeb18b23080a1d9bAlkis Evlogimenos} 11538af59a43c4176d8f34bd26faeb18b23080a1d9bAlkis Evlogimenos 11605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesenvoid VirtRegMap::print(raw_ostream &OS, const Module*) const { 11705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen OS << "********** REGISTER MAP **********\n"; 11805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 11905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 12005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen if (Virt2PhysMap[Reg] != (unsigned)VirtRegMap::NO_PHYS_REG) { 12105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen OS << '[' << PrintReg(Reg, TRI) << " -> " 12205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen << PrintReg(Virt2PhysMap[Reg], TRI) << "] " 12305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen << MRI->getRegClass(Reg)->getName() << "\n"; 12405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen } 12505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen } 12605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 12705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) { 12805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen unsigned Reg = TargetRegisterInfo::index2VirtReg(i); 12905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen if (Virt2StackSlotMap[Reg] != VirtRegMap::NO_STACK_SLOT) { 13005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen OS << '[' << PrintReg(Reg, TRI) << " -> fi#" << Virt2StackSlotMap[Reg] 13105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen << "] " << MRI->getRegClass(Reg)->getName() << "\n"; 13205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen } 13305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen } 13405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen OS << '\n'; 13505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen} 13605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 137b720be6a50f4e1b3280d2b029ee38dda14577525Manman Ren#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 13805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesenvoid VirtRegMap::dump() const { 13905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen print(dbgs()); 14005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen} 14177e300e8f0b8db8eec448cae9c87d7c5bfad9757Manman Ren#endif 14205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 14305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 14405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen// VirtRegRewriter 14505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 14605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen// 14705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen// The VirtRegRewriter is the last of the register allocator passes. 14805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen// It rewrites virtual registers to physical registers as specified in the 14905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen// VirtRegMap analysis. It also updates live-in information on basic blocks 15005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen// according to LiveIntervals. 15105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen// 15205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesennamespace { 15305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesenclass VirtRegRewriter : public MachineFunctionPass { 15405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen MachineFunction *MF; 15505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen const TargetMachine *TM; 15605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen const TargetRegisterInfo *TRI; 15705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen const TargetInstrInfo *TII; 15805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen MachineRegisterInfo *MRI; 15905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen SlotIndexes *Indexes; 16005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen LiveIntervals *LIS; 16105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen VirtRegMap *VRM; 16205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 16305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen void rewrite(); 16405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen void addMBBLiveIns(); 16505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesenpublic: 16605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen static char ID; 16705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen VirtRegRewriter() : MachineFunctionPass(ID) {} 16805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 16905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen virtual void getAnalysisUsage(AnalysisUsage &AU) const; 17005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 17105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen virtual bool runOnMachineFunction(MachineFunction&); 17205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen}; 17305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen} // end anonymous namespace 17405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 17505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesenchar &llvm::VirtRegRewriterID = VirtRegRewriter::ID; 17605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 17705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund OlesenINITIALIZE_PASS_BEGIN(VirtRegRewriter, "virtregrewriter", 17805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen "Virtual Register Rewriter", false, false) 17905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund OlesenINITIALIZE_PASS_DEPENDENCY(SlotIndexes) 18005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund OlesenINITIALIZE_PASS_DEPENDENCY(LiveIntervals) 18105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund OlesenINITIALIZE_PASS_DEPENDENCY(LiveDebugVariables) 182bb36a438722d4d56febc07c6472c8446bb6faafeEvan ChengINITIALIZE_PASS_DEPENDENCY(LiveStacks) 18305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund OlesenINITIALIZE_PASS_DEPENDENCY(VirtRegMap) 18405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund OlesenINITIALIZE_PASS_END(VirtRegRewriter, "virtregrewriter", 18505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen "Virtual Register Rewriter", false, false) 18605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 18705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesenchar VirtRegRewriter::ID = 0; 18805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 18905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesenvoid VirtRegRewriter::getAnalysisUsage(AnalysisUsage &AU) const { 19005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen AU.setPreservesCFG(); 19105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen AU.addRequired<LiveIntervals>(); 19205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen AU.addRequired<SlotIndexes>(); 19305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen AU.addPreserved<SlotIndexes>(); 19405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen AU.addRequired<LiveDebugVariables>(); 195bb36a438722d4d56febc07c6472c8446bb6faafeEvan Cheng AU.addRequired<LiveStacks>(); 196bb36a438722d4d56febc07c6472c8446bb6faafeEvan Cheng AU.addPreserved<LiveStacks>(); 19705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen AU.addRequired<VirtRegMap>(); 19805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen MachineFunctionPass::getAnalysisUsage(AU); 19905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen} 20005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 20105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesenbool VirtRegRewriter::runOnMachineFunction(MachineFunction &fn) { 20205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen MF = &fn; 20305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen TM = &MF->getTarget(); 20405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen TRI = TM->getRegisterInfo(); 20505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen TII = TM->getInstrInfo(); 20605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen MRI = &MF->getRegInfo(); 20705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen Indexes = &getAnalysis<SlotIndexes>(); 20805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen LIS = &getAnalysis<LiveIntervals>(); 20905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen VRM = &getAnalysis<VirtRegMap>(); 210ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen DEBUG(dbgs() << "********** REWRITE VIRTUAL REGISTERS **********\n" 211ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen << "********** Function: " 21296601ca332ab388754ca4673be8973396fea2dddCraig Topper << MF->getName() << '\n'); 21305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen DEBUG(VRM->dump()); 21405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 21505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen // Add kill flags while we still have virtual registers. 216e617ccb80da76821379bbff4a2fdcd09e8401e8bJakob Stoklund Olesen LIS->addKillFlags(VRM); 21705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 218fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen // Live-in lists on basic blocks are required for physregs. 219fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen addMBBLiveIns(); 220fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen 22105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen // Rewrite virtual registers. 22205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen rewrite(); 22305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 22405ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen // Write out new DBG_VALUE instructions. 22505ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen getAnalysis<LiveDebugVariables>().emitDebugValues(VRM); 22605ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 22705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen // All machine operands and other references to virtual registers have been 22805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen // replaced. Remove the virtual registers and release all the transient data. 22905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen VRM->clearAllVirt(); 23005ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen MRI->clearVirtRegs(); 23105ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen return true; 23205ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen} 23305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen 234fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen// Compute MBB live-in lists from virtual register live ranges and their 235fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen// assignments. 236fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesenvoid VirtRegRewriter::addMBBLiveIns() { 237fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen SmallVector<MachineBasicBlock*, 16> LiveIn; 238fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen for (unsigned Idx = 0, IdxE = MRI->getNumVirtRegs(); Idx != IdxE; ++Idx) { 239fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen unsigned VirtReg = TargetRegisterInfo::index2VirtReg(Idx); 240fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen if (MRI->reg_nodbg_empty(VirtReg)) 241fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen continue; 242fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen LiveInterval &LI = LIS->getInterval(VirtReg); 243fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen if (LI.empty() || LIS->intervalIsInOneMBB(LI)) 244fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen continue; 245fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen // This is a virtual register that is live across basic blocks. Its 246fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen // assigned PhysReg must be marked as live-in to those blocks. 247fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen unsigned PhysReg = VRM->getPhys(VirtReg); 248fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen assert(PhysReg != VirtRegMap::NO_PHYS_REG && "Unmapped virtual register."); 249fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen 250fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen // Scan the segments of LI. 251fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen for (LiveInterval::const_iterator I = LI.begin(), E = LI.end(); I != E; 252fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen ++I) { 253fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen if (!Indexes->findLiveInMBBs(I->start, I->end, LiveIn)) 254fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen continue; 255fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen for (unsigned i = 0, e = LiveIn.size(); i != e; ++i) 256fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen if (!LiveIn[i]->isLiveIn(PhysReg)) 257fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen LiveIn[i]->addLiveIn(PhysReg); 258fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen LiveIn.clear(); 259fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen } 260fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen } 261fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen} 262fe17bdbb50efe2f7f68d0b99e55ae52bd9477978Jakob Stoklund Olesen 26305ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesenvoid VirtRegRewriter::rewrite() { 26493e110ba344ddc901dfb2af61d9c21002d8d3080Jakob Stoklund Olesen SmallVector<unsigned, 8> SuperDeads; 26593e110ba344ddc901dfb2af61d9c21002d8d3080Jakob Stoklund Olesen SmallVector<unsigned, 8> SuperDefs; 266ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen SmallVector<unsigned, 8> SuperKills; 267ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen 268ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen for (MachineFunction::iterator MBBI = MF->begin(), MBBE = MF->end(); 269ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen MBBI != MBBE; ++MBBI) { 270ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen DEBUG(MBBI->print(dbgs(), Indexes)); 2713f9c251e40dac7503f7ae455fab89bdc359c7b85Evan Cheng for (MachineBasicBlock::instr_iterator 2723f9c251e40dac7503f7ae455fab89bdc359c7b85Evan Cheng MII = MBBI->instr_begin(), MIE = MBBI->instr_end(); MII != MIE;) { 273ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen MachineInstr *MI = MII; 274ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen ++MII; 275ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen 276ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen for (MachineInstr::mop_iterator MOI = MI->operands_begin(), 277ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen MOE = MI->operands_end(); MOI != MOE; ++MOI) { 278ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen MachineOperand &MO = *MOI; 279d9f0ff56a1878347fe5a0f162ef8c2ef2b63aeb5Jakob Stoklund Olesen 280d9f0ff56a1878347fe5a0f162ef8c2ef2b63aeb5Jakob Stoklund Olesen // Make sure MRI knows about registers clobbered by regmasks. 281d9f0ff56a1878347fe5a0f162ef8c2ef2b63aeb5Jakob Stoklund Olesen if (MO.isRegMask()) 282d9f0ff56a1878347fe5a0f162ef8c2ef2b63aeb5Jakob Stoklund Olesen MRI->addPhysRegsUsedFromRegMask(MO.getRegMask()); 283d9f0ff56a1878347fe5a0f162ef8c2ef2b63aeb5Jakob Stoklund Olesen 284ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg())) 285ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen continue; 286ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen unsigned VirtReg = MO.getReg(); 28705ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen unsigned PhysReg = VRM->getPhys(VirtReg); 28805ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen assert(PhysReg != VirtRegMap::NO_PHYS_REG && 28905ec712e7f75635abbdd84dced69f4a45fe0f541Jakob Stoklund Olesen "Instruction uses unmapped VirtReg"); 290fb9ebbf236974beac31705eaeb9f50ab585af6abJakob Stoklund Olesen assert(!MRI->isReserved(PhysReg) && "Reserved register assignment"); 291ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen 292ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen // Preserve semantics of sub-register operands. 293ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen if (MO.getSubReg()) { 294ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen // A virtual register kill refers to the whole register, so we may 295200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen // have to add <imp-use,kill> operands for the super-register. A 296200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen // partial redef always kills and redefines the super-register. 297200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen if (MO.readsReg() && (MO.isDef() || MO.isKill())) 298200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen SuperKills.push_back(PhysReg); 299200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen 300200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen if (MO.isDef()) { 301200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen // The <def,undef> flag only makes sense for sub-register defs, and 302200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen // we are substituting a full physreg. An <imp-use,kill> operand 303200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen // from the SuperKills list will represent the partial read of the 304200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen // super-register. 305200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen MO.setIsUndef(false); 306200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen 307200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen // Also add implicit defs for the super-register. 308200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen if (MO.isDead()) 309200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen SuperDeads.push_back(PhysReg); 310200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen else 311200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen SuperDefs.push_back(PhysReg); 312200a8cef256f6aade13692752a8fa8f6120cf04fJakob Stoklund Olesen } 313ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen 314ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen // PhysReg operands cannot have subregister indexes. 315ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen PhysReg = TRI->getSubReg(PhysReg, MO.getSubReg()); 316ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen assert(PhysReg && "Invalid SubReg for physical register"); 317ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen MO.setSubReg(0); 318ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen } 319ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen // Rewrite. Note we could have used MachineOperand::substPhysReg(), but 320ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen // we need the inlining here. 321ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen MO.setReg(PhysReg); 322ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen } 323ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen 324ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen // Add any missing super-register kills after rewriting the whole 325ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen // instruction. 326ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen while (!SuperKills.empty()) 327ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen MI->addRegisterKilled(SuperKills.pop_back_val(), TRI, true); 328ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen 32993e110ba344ddc901dfb2af61d9c21002d8d3080Jakob Stoklund Olesen while (!SuperDeads.empty()) 33093e110ba344ddc901dfb2af61d9c21002d8d3080Jakob Stoklund Olesen MI->addRegisterDead(SuperDeads.pop_back_val(), TRI, true); 33193e110ba344ddc901dfb2af61d9c21002d8d3080Jakob Stoklund Olesen 33293e110ba344ddc901dfb2af61d9c21002d8d3080Jakob Stoklund Olesen while (!SuperDefs.empty()) 33393e110ba344ddc901dfb2af61d9c21002d8d3080Jakob Stoklund Olesen MI->addRegisterDefined(SuperDefs.pop_back_val(), TRI); 33493e110ba344ddc901dfb2af61d9c21002d8d3080Jakob Stoklund Olesen 335ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen DEBUG(dbgs() << "> " << *MI); 336ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen 337ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen // Finally, remove any identity copies. 338ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen if (MI->isIdentityCopy()) { 339cf5e5f3cc08a3c7ede5b423ee4b18586cb1079e9Jakob Stoklund Olesen ++NumIdCopies; 340280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen if (MI->getNumOperands() == 2) { 341280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen DEBUG(dbgs() << "Deleting identity copy.\n"); 342280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen if (Indexes) 343280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen Indexes->removeMachineInstrFromMaps(MI); 344280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen // It's safe to erase MI because MII has already been incremented. 345280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen MI->eraseFromParent(); 346280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen } else { 347280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen // Transform identity copy to a KILL to deal with subregisters. 348280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen MI->setDesc(TII->get(TargetOpcode::KILL)); 349280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen DEBUG(dbgs() << "Identity copy: " << *MI); 350280ea1a7466751c6d27ff343072c65e59a950053Jakob Stoklund Olesen } 351ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen } 352ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen } 353ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen } 354ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen 355ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen // Tell MRI about physical registers in use. 356ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen for (unsigned Reg = 1, RegE = TRI->getNumRegs(); Reg != RegE; ++Reg) 357ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen if (!MRI->reg_nodbg_empty(Reg)) 358ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen MRI->setPhysRegUsed(Reg); 359ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen} 360