VirtRegMap.h revision e81561909d128c6e2d8033cb5465a49b2596b26a
134d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos//===-- llvm/CodeGen/VirtRegMap.h - Virtual Register Map -*- C++ -*--------===// 234d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// 334d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// The LLVM Compiler Infrastructure 434d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// 534d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// This file was developed by the LLVM research group and is distributed under 634d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// the University of Illinois Open Source License. See LICENSE.TXT for details. 734d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// 834d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos//===----------------------------------------------------------------------===// 934d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// 108c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner// This file implements 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 208c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner#include "llvm/Target/MRegisterInfo.h" 21551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/DenseMap.h" 22e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling#include "llvm/Support/Streams.h" 235f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos#include <map> 2434d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos 2534d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenosnamespace llvm { 268c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner class MachineInstr; 272926869b4a083fc951484de03a9867eabf81e880Chris Lattner class TargetInstrInfo; 288c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 298c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner class VirtRegMap { 308c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner public: 3135f2705e3de4600c3621b883eed9b22e4607ddf4Chris Lattner enum ModRef { isRef = 1, isMod = 2, isModRef = 3 }; 32bec6a9ea1281a0b3b37aece91ab0df21e086af61Chris Lattner typedef std::multimap<MachineInstr*, 33bec6a9ea1281a0b3b37aece91ab0df21e086af61Chris Lattner std::pair<unsigned, ModRef> > MI2VirtMapTy; 348c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 358c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner private: 362926869b4a083fc951484de03a9867eabf81e880Chris Lattner const TargetInstrInfo &TII; 372926869b4a083fc951484de03a9867eabf81e880Chris Lattner 387f690e625807b9320bf4ae437b8f35258acc99deChris Lattner MachineFunction &MF; 39c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// Virt2PhysMap - This is a virtual to physical register 40c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// mapping. Each virtual register is required to have an entry in 41c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// it; even spilled virtual registers (the register mapped to a 42c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// spilled register is the temporary used to load it from the 43c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// stack). 447f690e625807b9320bf4ae437b8f35258acc99deChris Lattner DenseMap<unsigned, VirtReg2IndexFunctor> Virt2PhysMap; 45c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// Virt2StackSlotMap - This is virtual register to stack slot 46c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// mapping. Each spilled virtual register has an entry in it 47c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// which corresponds to the stack slot this register is spilled 48c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// at. 497f690e625807b9320bf4ae437b8f35258acc99deChris Lattner DenseMap<int, VirtReg2IndexFunctor> Virt2StackSlotMap; 50c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// MI2VirtMap - This is MachineInstr to virtual register 51c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// mapping. In the case of memory spill code being folded into 52c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// instructions, we need to know which virtual register was 53c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// read/written by this instruction. 547f690e625807b9320bf4ae437b8f35258acc99deChris Lattner MI2VirtMapTy MI2VirtMap; 55edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 568c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner VirtRegMap(const VirtRegMap&); // DO NOT IMPLEMENT 578c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner void operator=(const VirtRegMap&); // DO NOT IMPLEMENT 588c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 598c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner enum { 608c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner NO_PHYS_REG = 0, 618c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner NO_STACK_SLOT = ~0 >> 1 62dd420e060accd1d773c731e77335cff65ca34013Alkis Evlogimenos }; 63dd420e060accd1d773c731e77335cff65ca34013Alkis Evlogimenos 648c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner public: 652926869b4a083fc951484de03a9867eabf81e880Chris Lattner VirtRegMap(MachineFunction &mf); 668c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 678c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner void grow(); 688c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 69c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// @brief returns true if the specified virtual register is 70c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// mapped to a physical register 718c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner bool hasPhys(unsigned virtReg) const { 728c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner return getPhys(virtReg) != NO_PHYS_REG; 738c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 748c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 75c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// @brief returns the physical register mapped to the specified 76c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// virtual register 778c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner unsigned getPhys(unsigned virtReg) const { 788c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner assert(MRegisterInfo::isVirtualRegister(virtReg)); 797f690e625807b9320bf4ae437b8f35258acc99deChris Lattner return Virt2PhysMap[virtReg]; 808c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 818c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 82c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// @brief creates a mapping for the specified virtual register to 83c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// the specified physical register 848c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner void assignVirt2Phys(unsigned virtReg, unsigned physReg) { 858c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner assert(MRegisterInfo::isVirtualRegister(virtReg) && 868c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner MRegisterInfo::isPhysicalRegister(physReg)); 877f690e625807b9320bf4ae437b8f35258acc99deChris Lattner assert(Virt2PhysMap[virtReg] == NO_PHYS_REG && 888c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner "attempt to assign physical register to already mapped " 898c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner "virtual register"); 907f690e625807b9320bf4ae437b8f35258acc99deChris Lattner Virt2PhysMap[virtReg] = physReg; 918c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 928c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 93c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// @brief clears the specified virtual register's, physical 94c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// register mapping 958c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner void clearVirt(unsigned virtReg) { 968c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner assert(MRegisterInfo::isVirtualRegister(virtReg)); 977f690e625807b9320bf4ae437b8f35258acc99deChris Lattner assert(Virt2PhysMap[virtReg] != NO_PHYS_REG && 988c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner "attempt to clear a not assigned virtual register"); 997f690e625807b9320bf4ae437b8f35258acc99deChris Lattner Virt2PhysMap[virtReg] = NO_PHYS_REG; 1008c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 1018c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 102c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// @brief clears all virtual to physical register mappings 1038c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner void clearAllVirt() { 1047f690e625807b9320bf4ae437b8f35258acc99deChris Lattner Virt2PhysMap.clear(); 1058c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner grow(); 1068c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 1078c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 108c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// @brief returns true is the specified virtual register is 109c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// mapped to a stack slot 1108c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner bool hasStackSlot(unsigned virtReg) const { 1118c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner return getStackSlot(virtReg) != NO_STACK_SLOT; 1128c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 1138c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 114c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// @brief returns the stack slot mapped to the specified virtual 115c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// register 1168c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner int getStackSlot(unsigned virtReg) const { 1178c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner assert(MRegisterInfo::isVirtualRegister(virtReg)); 1187f690e625807b9320bf4ae437b8f35258acc99deChris Lattner return Virt2StackSlotMap[virtReg]; 1198c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 1208c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 121c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// @brief create a mapping for the specifed virtual register to 122c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// the next available stack slot 1238c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner int assignVirt2StackSlot(unsigned virtReg); 124c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// @brief create a mapping for the specified virtual register to 125c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// the specified stack slot 1268c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner void assignVirt2StackSlot(unsigned virtReg, int frameIndex); 1278c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 128bec6a9ea1281a0b3b37aece91ab0df21e086af61Chris Lattner /// @brief Updates information about the specified virtual register's value 129bec6a9ea1281a0b3b37aece91ab0df21e086af61Chris Lattner /// folded into newMI machine instruction. The OpNum argument indicates the 130bec6a9ea1281a0b3b37aece91ab0df21e086af61Chris Lattner /// operand number of OldMI that is folded. 131bec6a9ea1281a0b3b37aece91ab0df21e086af61Chris Lattner void virtFolded(unsigned VirtReg, MachineInstr *OldMI, unsigned OpNum, 13235f2705e3de4600c3621b883eed9b22e4607ddf4Chris Lattner MachineInstr *NewMI); 1338c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 134c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// @brief returns the virtual registers' values folded in memory 135c736b3a37aa8959f9011bf0773288ba35c3f08b3Alkis Evlogimenos /// operands of this instruction 1367f690e625807b9320bf4ae437b8f35258acc99deChris Lattner std::pair<MI2VirtMapTy::const_iterator, MI2VirtMapTy::const_iterator> 1378c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner getFoldedVirts(MachineInstr* MI) const { 1387f690e625807b9320bf4ae437b8f35258acc99deChris Lattner return MI2VirtMap.equal_range(MI); 1398c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 14035f2705e3de4600c3621b883eed9b22e4607ddf4Chris Lattner 141229924a79f9a3b33b767527b9d4249e1133ceedaChris Lattner /// RemoveFromFoldedVirtMap - If the specified machine instruction is in 142229924a79f9a3b33b767527b9d4249e1133ceedaChris Lattner /// the folded instruction map, remove its entry from the map. 14335f2705e3de4600c3621b883eed9b22e4607ddf4Chris Lattner void RemoveFromFoldedVirtMap(MachineInstr *MI) { 144229924a79f9a3b33b767527b9d4249e1133ceedaChris Lattner MI2VirtMap.erase(MI); 14535f2705e3de4600c3621b883eed9b22e4607ddf4Chris Lattner } 1468c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 1478c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner void print(std::ostream &OS) const; 148e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling void print(OStream &OS) const; 1498c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner void dump() const; 1508c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner }; 1518c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 1528c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner inline std::ostream &operator<<(std::ostream &OS, const VirtRegMap &VRM) { 1538c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner VRM.print(OS); 1548c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner return OS; 1558c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner } 1568c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 1578c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner /// Spiller interface: Implementations of this interface assign spilled 1588c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner /// virtual registers to stack slots, rewriting the code. 1598c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner struct Spiller { 1608c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner virtual ~Spiller(); 1618c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner virtual bool runOnMachineFunction(MachineFunction &MF, 16235f2705e3de4600c3621b883eed9b22e4607ddf4Chris Lattner VirtRegMap &VRM) = 0; 1638c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner }; 1648c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner 1658c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner /// createSpiller - Create an return a spiller object, as specified on the 1668c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner /// command line. 1678c4d88d3697835371ecf6823f4142af13603ad2dChris Lattner Spiller* createSpiller(); 1680d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 16934d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos} // End llvm namespace 17034d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos 17134d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos#endif 172