134d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos//===-- llvm/CodeGen/VirtRegMap.h - Virtual Register Map -*- C++ -*--------===// 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 a virtual register map. This maps virtual registers to 118c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner// physical registers and virtual registers to stack slots. It is created and 128c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner// updated by a register allocator and then used by a machine code rewriter that 138c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner// adds spill code and rewrites virtual into physical register references. 1434d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// 1534d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos//===----------------------------------------------------------------------===// 1634d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos 1734d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos#ifndef LLVM_CODEGEN_VIRTREGMAP_H 1834d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos#define LLVM_CODEGEN_VIRTREGMAP_H 1934d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos 2049c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson#include "llvm/CodeGen/MachineFunctionPass.h" 216f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman#include "llvm/Target/TargetRegisterInfo.h" 2294c002a190cd2e3a52b1510bc997e53d63af0b3bChris Lattner#include "llvm/ADT/IndexedMap.h" 2334d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos 2434d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenosnamespace llvm { 258c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner class MachineInstr; 267e23146ab9dd6c2d8849bacce841a2e4660305dcDavid Greene class MachineFunction; 2790f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng class MachineRegisterInfo; 282926869b4a083fc951484de03a9867eabf81e880Chris Lattner class TargetInstrInfo; 291cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar class raw_ostream; 30ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen class SlotIndexes; 318c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 3249c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson class VirtRegMap : public MachineFunctionPass { 338c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner public: 342638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng enum { 352638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng NO_PHYS_REG = 0, 369193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng NO_STACK_SLOT = (1L << 30)-1, 379193514e2e3e599e241220b72bc9add25a80a8fdEvan Cheng MAX_STACK_SLOT = (1L << 18)-1 382638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng }; 392638e1a6b9e3c0e22b398987e1db99bee81db4fbEvan Cheng 408c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner private: 4190f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng MachineRegisterInfo *MRI; 4249c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson const TargetInstrInfo *TII; 43fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump const TargetRegisterInfo *TRI; 4449c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson MachineFunction *MF; 45fe095f39e7009c51d1c86769792ccbcad8cdd2ecMike Stump 46c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// Virt2PhysMap - This is a virtual to physical register 47c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// mapping. Each virtual register is required to have an entry in 48c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// it; even spilled virtual registers (the register mapped to a 49c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// spilled register is the temporary used to load it from the 50c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// stack). 5194c002a190cd2e3a52b1510bc997e53d63af0b3bChris Lattner IndexedMap<unsigned, VirtReg2IndexFunctor> Virt2PhysMap; 5281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 53c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// Virt2StackSlotMap - This is virtual register to stack slot 54c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// mapping. Each spilled virtual register has an entry in it 55c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// which corresponds to the stack slot this register is spilled 56c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// at. 5794c002a190cd2e3a52b1510bc997e53d63af0b3bChris Lattner IndexedMap<int, VirtReg2IndexFunctor> Virt2StackSlotMap; 5881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 5981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng /// Virt2SplitMap - This is virtual register to splitted virtual register 6081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng /// mapping. 6181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng IndexedMap<unsigned, VirtReg2IndexFunctor> Virt2SplitMap; 6281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 63b55e91e08738b804f17109a49881e51b69e91299Jakob Stoklund Olesen /// createSpillSlot - Allocate a spill slot for RC from MFI. 64b55e91e08738b804f17109a49881e51b69e91299Jakob Stoklund Olesen unsigned createSpillSlot(const TargetRegisterClass *RC); 65b55e91e08738b804f17109a49881e51b69e91299Jakob Stoklund Olesen 668c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner VirtRegMap(const VirtRegMap&); // DO NOT IMPLEMENT 678c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner void operator=(const VirtRegMap&); // DO NOT IMPLEMENT 688c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 698c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner public: 7049c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson static char ID; 7190c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Anderson VirtRegMap() : MachineFunctionPass(ID), Virt2PhysMap(NO_PHYS_REG), 72cb39064e7aee2273da1d00e6b800db84ddc34b6bJakob Stoklund Olesen Virt2StackSlotMap(NO_STACK_SLOT), Virt2SplitMap(0) { } 7349c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson virtual bool runOnMachineFunction(MachineFunction &MF); 7449c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson 7549c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson virtual void getAnalysisUsage(AnalysisUsage &AU) const { 7649c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson AU.setPreservesAll(); 7749c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson MachineFunctionPass::getAnalysisUsage(AU); 7849c8aa0d8b2824c70d178c5d55cda64d6613c0d8Owen Anderson } 798c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 80f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen MachineFunction &getMachineFunction() const { 81c9672cb8bea13fcbcbdb1cf26708d831c034c089Jakob Stoklund Olesen assert(MF && "getMachineFunction called before runOnMachineFunction"); 82f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen return *MF; 83f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen } 84f0179004e94259a8adab6c48f295ea9ab18af4c3Jakob Stoklund Olesen 85c9672cb8bea13fcbcbdb1cf26708d831c034c089Jakob Stoklund Olesen MachineRegisterInfo &getRegInfo() const { return *MRI; } 86c9672cb8bea13fcbcbdb1cf26708d831c034c089Jakob Stoklund Olesen const TargetRegisterInfo &getTargetRegInfo() const { return *TRI; } 87c9672cb8bea13fcbcbdb1cf26708d831c034c089Jakob Stoklund Olesen 888c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner void grow(); 898c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 90c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// @brief returns true if the specified virtual register is 91c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// mapped to a physical register 928c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner bool hasPhys(unsigned virtReg) const { 938c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner return getPhys(virtReg) != NO_PHYS_REG; 948c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 958c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 96c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// @brief returns the physical register mapped to the specified 97c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// virtual register 988c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner unsigned getPhys(unsigned virtReg) const { 996f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman assert(TargetRegisterInfo::isVirtualRegister(virtReg)); 1007f690e625807b9320bf4ae437b8f35258acc99deChris Lattner return Virt2PhysMap[virtReg]; 1018c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 1028c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 103c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// @brief creates a mapping for the specified virtual register to 104c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// the specified physical register 1058c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner void assignVirt2Phys(unsigned virtReg, unsigned physReg) { 1066f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman assert(TargetRegisterInfo::isVirtualRegister(virtReg) && 1076f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman TargetRegisterInfo::isPhysicalRegister(physReg)); 1087f690e625807b9320bf4ae437b8f35258acc99deChris Lattner assert(Virt2PhysMap[virtReg] == NO_PHYS_REG && 1098c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner "attempt to assign physical register to already mapped " 1108c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner "virtual register"); 1117f690e625807b9320bf4ae437b8f35258acc99deChris Lattner Virt2PhysMap[virtReg] = physReg; 1128c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 1138c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 114c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// @brief clears the specified virtual register's, physical 115c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// register mapping 1168c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner void clearVirt(unsigned virtReg) { 1176f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman assert(TargetRegisterInfo::isVirtualRegister(virtReg)); 1187f690e625807b9320bf4ae437b8f35258acc99deChris Lattner assert(Virt2PhysMap[virtReg] != NO_PHYS_REG && 1198c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner "attempt to clear a not assigned virtual register"); 1207f690e625807b9320bf4ae437b8f35258acc99deChris Lattner Virt2PhysMap[virtReg] = NO_PHYS_REG; 1218c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 1228c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 123c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// @brief clears all virtual to physical register mappings 1248c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner void clearAllVirt() { 1257f690e625807b9320bf4ae437b8f35258acc99deChris Lattner Virt2PhysMap.clear(); 1268c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner grow(); 1278c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 1288c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 12990f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng /// @brief returns the register allocation preference. 13090f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng unsigned getRegAllocPref(unsigned virtReg); 13190f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng 13251458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen /// @brief returns true if VirtReg is assigned to its preferred physreg. 13351458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen bool hasPreferredPhys(unsigned VirtReg) { 13451458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen return getPhys(VirtReg) == getRegAllocPref(VirtReg); 13551458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen } 13651458ed09e6db0e424cd528e10b879f59915abe4Jakob Stoklund Olesen 13781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng /// @brief records virtReg is a split live interval from SReg. 13881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng void setIsSplitFromReg(unsigned virtReg, unsigned SReg) { 13981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Virt2SplitMap[virtReg] = SReg; 14081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 14181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 14281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng /// @brief returns the live interval virtReg is split from. 143e324f6e05ff7a157347edb48203db0250805f748Jakob Stoklund Olesen unsigned getPreSplitReg(unsigned virtReg) const { 14481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return Virt2SplitMap[virtReg]; 14581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 14681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 147fd38917d4d040759d75e9d1f4e2c885fb40ba2d7Jakob Stoklund Olesen /// getOriginal - Return the original virtual register that VirtReg descends 148fd38917d4d040759d75e9d1f4e2c885fb40ba2d7Jakob Stoklund Olesen /// from through splitting. 149fd38917d4d040759d75e9d1f4e2c885fb40ba2d7Jakob Stoklund Olesen /// A register that was not created by splitting is its own original. 150fd38917d4d040759d75e9d1f4e2c885fb40ba2d7Jakob Stoklund Olesen /// This operation is idempotent. 151fd38917d4d040759d75e9d1f4e2c885fb40ba2d7Jakob Stoklund Olesen unsigned getOriginal(unsigned VirtReg) const { 152fd38917d4d040759d75e9d1f4e2c885fb40ba2d7Jakob Stoklund Olesen unsigned Orig = getPreSplitReg(VirtReg); 153fd38917d4d040759d75e9d1f4e2c885fb40ba2d7Jakob Stoklund Olesen return Orig ? Orig : VirtReg; 154fd38917d4d040759d75e9d1f4e2c885fb40ba2d7Jakob Stoklund Olesen } 155fd38917d4d040759d75e9d1f4e2c885fb40ba2d7Jakob Stoklund Olesen 15639e33acf0aba655c96d3e37703b506cbf470c483Dan Gohman /// @brief returns true if the specified virtual register is not 157549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng /// mapped to a stack slot or rematerialized. 158549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng bool isAssignedReg(unsigned virtReg) const { 1593cb0b0edd9ec537a9415eaff97edd042a07fd16eJakob Stoklund Olesen if (getStackSlot(virtReg) == NO_STACK_SLOT) 16081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return true; 16181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Split register can be assigned a physical register as well as a 16281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // stack slot or remat id. 16381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return (Virt2SplitMap[virtReg] && Virt2PhysMap[virtReg] != NO_PHYS_REG); 1648c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 1658c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 166c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// @brief returns the stack slot mapped to the specified virtual 167c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// register 1688c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner int getStackSlot(unsigned virtReg) const { 1696f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman assert(TargetRegisterInfo::isVirtualRegister(virtReg)); 1707f690e625807b9320bf4ae437b8f35258acc99deChris Lattner return Virt2StackSlotMap[virtReg]; 1718c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 1728c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 173c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// @brief create a mapping for the specifed virtual register to 174c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// the next available stack slot 1758c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner int assignVirt2StackSlot(unsigned virtReg); 176c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// @brief create a mapping for the specified virtual register to 177c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// the specified stack slot 1788c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner void assignVirt2StackSlot(unsigned virtReg, int frameIndex); 1798c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 180ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen /// rewrite - Rewrite all instructions in MF to use only physical registers 181ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen /// by mapping all virtual register operands to their assigned physical 182ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen /// registers. 183ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen /// 184ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen /// @param Indexes Optionally remove deleted instructions from indexes. 185ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen void rewrite(SlotIndexes *Indexes); 186ba05c01dabc40373760a20c874103fc58d4377f0Jakob Stoklund Olesen 1871cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar void print(raw_ostream &OS, const Module* M = 0) const; 1888c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner void dump() const; 1898c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner }; 1908c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 1911cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar inline raw_ostream &operator<<(raw_ostream &OS, const VirtRegMap &VRM) { 1921cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar VRM.print(OS); 1931cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar return OS; 1941cd1d98232c3c3a0bd3810c3bf6c2572ea02f208Daniel Dunbar } 19534d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos} // End llvm namespace 19634d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos 19734d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos#endif 198