VirtRegMap.cpp revision 5f37502bfbadfa65de087627bd67fd58bb03725c
134d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos//===-- llvm/CodeGen/VirtRegMap.cpp - Virtual Register Map ----------------===// 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// 100d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos// This file implements the virtual register map. It also implements 110d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos// the eliminateVirtRegs() function that given a virtual register map 120d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos// and a machine function it eliminates all virtual references by 130d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos// replacing them with physical register references and adds spill 140d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos// code as necessary. 1534d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos// 1634d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos//===----------------------------------------------------------------------===// 1734d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos 180d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos#define DEBUG_TYPE "regalloc" 1934d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos#include "VirtRegMap.h" 200d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos#include "llvm/Function.h" 2134d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos#include "llvm/CodeGen/MachineFrameInfo.h" 225f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos#include "llvm/CodeGen/MachineInstr.h" 2334d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos#include "llvm/Target/TargetMachine.h" 240d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos#include "llvm/Target/TargetInstrInfo.h" 2534d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos#include "Support/Statistic.h" 260d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos#include "Support/Debug.h" 2757af2cf6f3b1ae250891fb60272bcdb3a964fbf9Alkis Evlogimenos#include "Support/DenseMap.h" 280d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos#include "Support/STLExtras.h" 2934d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos#include <iostream> 3034d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos 3134d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenosusing namespace llvm; 3234d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos 3334d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenosnamespace { 340d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos Statistic<> numSpills("spiller", "Number of register spills"); 350d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos Statistic<> numStores("spiller", "Number of stores added"); 360d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos Statistic<> numLoads ("spiller", "Number of loads added"); 370d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 3834d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos} 3934d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos 4034d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenosint VirtRegMap::assignVirt2StackSlot(unsigned virtReg) 4134d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos{ 4234d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos assert(MRegisterInfo::isVirtualRegister(virtReg)); 434d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos assert(v2ssMap_[virtReg] == NO_STACK_SLOT && 4434d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos "attempt to assign stack slot to already spilled register"); 4534d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos const TargetRegisterClass* rc = 4634d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos mf_->getSSARegMap()->getRegClass(virtReg); 4734d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos int frameIndex = mf_->getFrameInfo()->CreateStackObject(rc); 484d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos v2ssMap_[virtReg] = frameIndex; 4934d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos ++numSpills; 5034d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos return frameIndex; 5134d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos} 5234d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos 535f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenosvoid VirtRegMap::virtFolded(unsigned virtReg, 545f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos MachineInstr* oldMI, 555f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos MachineInstr* newMI) 565f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos{ 575f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos // move previous memory references folded to new instruction 585f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos MI2VirtMap::iterator i, e; 595f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos std::vector<MI2VirtMap::mapped_type> regs; 605f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos for (tie(i, e) = mi2vMap_.equal_range(oldMI); i != e; ) { 615f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos regs.push_back(i->second); 625f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos mi2vMap_.erase(i++); 635f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos } 645f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos for (unsigned i = 0, e = regs.size(); i != e; ++i) 655f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos mi2vMap_.insert(std::make_pair(newMI, i)); 665f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos 675f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos // add new memory reference 685f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos mi2vMap_.insert(std::make_pair(newMI, virtReg)); 695f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos} 705f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos 7134d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenosstd::ostream& llvm::operator<<(std::ostream& os, const VirtRegMap& vrm) 7234d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos{ 7334d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos const MRegisterInfo* mri = vrm.mf_->getTarget().getRegisterInfo(); 7434d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos 7534d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos std::cerr << "********** REGISTER MAP **********\n"; 764d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos for (unsigned i = MRegisterInfo::FirstVirtualRegister, 774d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos e = vrm.mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) { 7834d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos if (vrm.v2pMap_[i] != VirtRegMap::NO_PHYS_REG) 794d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos std::cerr << "[reg" << i << " -> " 8034d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos << mri->getName(vrm.v2pMap_[i]) << "]\n"; 8134d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos } 824d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos for (unsigned i = MRegisterInfo::FirstVirtualRegister, 834d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos e = vrm.mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) { 8434d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos if (vrm.v2ssMap_[i] != VirtRegMap::NO_STACK_SLOT) 854d0d864be3d9a698c4edfe36961a22126f041298Alkis Evlogimenos std::cerr << "[reg" << i << " -> fi#" 8634d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos << vrm.v2ssMap_[i] << "]\n"; 8734d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos } 8834d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos return std::cerr << '\n'; 8934d9bc9f168d17c52eb57e024580bd9499695f91Alkis Evlogimenos} 900d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 910d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenosnamespace { 920d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 930d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos class Spiller { 940d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos typedef std::vector<unsigned> Phys2VirtMap; 950d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos typedef std::vector<bool> PhysFlag; 9657af2cf6f3b1ae250891fb60272bcdb3a964fbf9Alkis Evlogimenos typedef DenseMap<MachineInstr*, VirtReg2IndexFunctor> Virt2MI; 970d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 980d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos MachineFunction& mf_; 990d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos const TargetMachine& tm_; 1000d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos const TargetInstrInfo& tii_; 1010d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos const MRegisterInfo& mri_; 1020d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos const VirtRegMap& vrm_; 1030d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos Phys2VirtMap p2vMap_; 1040d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos PhysFlag dirty_; 10557af2cf6f3b1ae250891fb60272bcdb3a964fbf9Alkis Evlogimenos Virt2MI lastDef_; 1060d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 1070d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos public: 1080d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos Spiller(MachineFunction& mf, const VirtRegMap& vrm) 1090d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos : mf_(mf), 1100d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos tm_(mf_.getTarget()), 1110d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos tii_(tm_.getInstrInfo()), 1120d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos mri_(*tm_.getRegisterInfo()), 1130d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos vrm_(vrm), 1148fa16e47f88975b577fe1cafce1a366b78b2c340Alkis Evlogimenos p2vMap_(mri_.getNumRegs(), 0), 11557af2cf6f3b1ae250891fb60272bcdb3a964fbf9Alkis Evlogimenos dirty_(mri_.getNumRegs(), false), 11657af2cf6f3b1ae250891fb60272bcdb3a964fbf9Alkis Evlogimenos lastDef_() { 1170d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos DEBUG(std::cerr << "********** REWRITE MACHINE CODE **********\n"); 1180d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos DEBUG(std::cerr << "********** Function: " 1190d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos << mf_.getFunction()->getName() << '\n'); 1200d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos } 1210d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 1220d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos void eliminateVirtRegs() { 1230d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos for (MachineFunction::iterator mbbi = mf_.begin(), 1240d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos mbbe = mf_.end(); mbbi != mbbe; ++mbbi) { 12557af2cf6f3b1ae250891fb60272bcdb3a964fbf9Alkis Evlogimenos lastDef_.grow(mf_.getSSARegMap()->getLastVirtReg()); 1268fa16e47f88975b577fe1cafce1a366b78b2c340Alkis Evlogimenos DEBUG(std::cerr << mbbi->getBasicBlock()->getName() << ":\n"); 1278fa16e47f88975b577fe1cafce1a366b78b2c340Alkis Evlogimenos eliminateVirtRegsInMbb(*mbbi); 12857af2cf6f3b1ae250891fb60272bcdb3a964fbf9Alkis Evlogimenos // clear map, dirty flag and last ref 1290d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos p2vMap_.assign(p2vMap_.size(), 0); 1300d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos dirty_.assign(dirty_.size(), false); 13157af2cf6f3b1ae250891fb60272bcdb3a964fbf9Alkis Evlogimenos lastDef_.clear(); 1320d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos } 1330d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos } 1340d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 1350d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos private: 1360d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos void vacateJustPhysReg(MachineBasicBlock& mbb, 1370d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos MachineBasicBlock::iterator mii, 1380d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos unsigned physReg) { 1390d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos unsigned virtReg = p2vMap_[physReg]; 1400d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos if (dirty_[physReg] && vrm_.hasStackSlot(virtReg)) { 14157af2cf6f3b1ae250891fb60272bcdb3a964fbf9Alkis Evlogimenos assert(lastDef_[virtReg] && "virtual register is mapped " 14257af2cf6f3b1ae250891fb60272bcdb3a964fbf9Alkis Evlogimenos "to a register and but was not defined!"); 14357af2cf6f3b1ae250891fb60272bcdb3a964fbf9Alkis Evlogimenos MachineBasicBlock::iterator lastDef = lastDef_[virtReg]; 14457af2cf6f3b1ae250891fb60272bcdb3a964fbf9Alkis Evlogimenos MachineBasicBlock::iterator nextLastRef = next(lastDef); 14557af2cf6f3b1ae250891fb60272bcdb3a964fbf9Alkis Evlogimenos mri_.storeRegToStackSlot(*lastDef->getParent(), 14657af2cf6f3b1ae250891fb60272bcdb3a964fbf9Alkis Evlogimenos nextLastRef, 14757af2cf6f3b1ae250891fb60272bcdb3a964fbf9Alkis Evlogimenos physReg, 1480d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos vrm_.getStackSlot(virtReg), 1490d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos mri_.getRegClass(physReg)); 1500d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos ++numStores; 1515f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos DEBUG(std::cerr << "added: "; 15257af2cf6f3b1ae250891fb60272bcdb3a964fbf9Alkis Evlogimenos prior(nextLastRef)->print(std::cerr, tm_); 1535f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos std::cerr << "after: "; 15457af2cf6f3b1ae250891fb60272bcdb3a964fbf9Alkis Evlogimenos lastDef->print(std::cerr, tm_)); 15557af2cf6f3b1ae250891fb60272bcdb3a964fbf9Alkis Evlogimenos lastDef_[virtReg] = 0; 1560d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos } 1570d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos p2vMap_[physReg] = 0; 1580d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos dirty_[physReg] = false; 1590d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos } 1600d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 1610d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos void vacatePhysReg(MachineBasicBlock& mbb, 1620d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos MachineBasicBlock::iterator mii, 1630d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos unsigned physReg) { 1640d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos vacateJustPhysReg(mbb, mii, physReg); 1650d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos for (const unsigned* as = mri_.getAliasSet(physReg); *as; ++as) 1660d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos vacateJustPhysReg(mbb, mii, *as); 1670d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos } 1680d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 1690d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos void handleUse(MachineBasicBlock& mbb, 1700d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos MachineBasicBlock::iterator mii, 1710d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos unsigned virtReg, 1720d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos unsigned physReg) { 1730d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos // check if we are replacing a previous mapping 1740d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos if (p2vMap_[physReg] != virtReg) { 1750d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos vacatePhysReg(mbb, mii, physReg); 1760d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos p2vMap_[physReg] = virtReg; 1770d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos // load if necessary 1780d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos if (vrm_.hasStackSlot(virtReg)) { 1790d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos mri_.loadRegFromStackSlot(mbb, mii, physReg, 1800d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos vrm_.getStackSlot(virtReg), 1810d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos mri_.getRegClass(physReg)); 1820d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos ++numLoads; 1835f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos DEBUG(std::cerr << "added: "; 1845f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos prior(mii)->print(std::cerr,tm_)); 18557af2cf6f3b1ae250891fb60272bcdb3a964fbf9Alkis Evlogimenos lastDef_[virtReg] = mii; 1860d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos } 1870d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos } 1880d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos } 1890d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 1900d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos void handleDef(MachineBasicBlock& mbb, 1910d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos MachineBasicBlock::iterator mii, 1920d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos unsigned virtReg, 1930d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos unsigned physReg) { 1940d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos // check if we are replacing a previous mapping 1950d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos if (p2vMap_[physReg] != virtReg) 1960d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos vacatePhysReg(mbb, mii, physReg); 1970d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 1980d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos p2vMap_[physReg] = virtReg; 1990d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos dirty_[physReg] = true; 20057af2cf6f3b1ae250891fb60272bcdb3a964fbf9Alkis Evlogimenos lastDef_[virtReg] = mii; 2010d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos } 2020d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 2030d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos void eliminateVirtRegsInMbb(MachineBasicBlock& mbb) { 2040d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos for (MachineBasicBlock::iterator mii = mbb.begin(), 2050d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos mie = mbb.end(); mii != mie; ++mii) { 2065f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos 2075f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos // if we have references to memory operands make sure 2085f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos // we clear all physical registers that may contain 2095f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos // the value of the spilled virtual register 2105f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos VirtRegMap::MI2VirtMap::const_iterator i, e; 2115f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos for (tie(i, e) = vrm_.getFoldedVirts(mii); i != e; ++i) { 2125f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos unsigned physReg = vrm_.getPhys(i->second); 2135f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos if (physReg) vacateJustPhysReg(mbb, mii, physReg); 2145f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos } 2155f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos 2160d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos // rewrite all used operands 2170d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) { 2180d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos MachineOperand& op = mii->getOperand(i); 219e3fcabe0681fe0d759593b1bcfab527f730778d8Alkis Evlogimenos if (op.isRegister() && op.getReg() && op.isUse() && 2200d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos MRegisterInfo::isVirtualRegister(op.getReg())) { 22157af2cf6f3b1ae250891fb60272bcdb3a964fbf9Alkis Evlogimenos unsigned virtReg = op.getReg(); 22257af2cf6f3b1ae250891fb60272bcdb3a964fbf9Alkis Evlogimenos unsigned physReg = vrm_.getPhys(virtReg); 22357af2cf6f3b1ae250891fb60272bcdb3a964fbf9Alkis Evlogimenos handleUse(mbb, mii, virtReg, physReg); 2240d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos mii->SetMachineOperandReg(i, physReg); 2250d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos // mark as dirty if this is def&use 22657af2cf6f3b1ae250891fb60272bcdb3a964fbf9Alkis Evlogimenos if (op.isDef()) { 22757af2cf6f3b1ae250891fb60272bcdb3a964fbf9Alkis Evlogimenos dirty_[physReg] = true; 22857af2cf6f3b1ae250891fb60272bcdb3a964fbf9Alkis Evlogimenos lastDef_[virtReg] = mii; 22957af2cf6f3b1ae250891fb60272bcdb3a964fbf9Alkis Evlogimenos } 2300d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos } 2310d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos } 2320d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 2330d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos // spill implicit defs 2340d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos const TargetInstrDescriptor& tid =tii_.get(mii->getOpcode()); 2350d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos for (const unsigned* id = tid.ImplicitDefs; *id; ++id) 2360d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos vacatePhysReg(mbb, mii, *id); 2370d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 2380d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos // rewrite def operands (def&use was handled with the 2390d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos // uses so don't check for those here) 2400d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) { 2410d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos MachineOperand& op = mii->getOperand(i); 242e3fcabe0681fe0d759593b1bcfab527f730778d8Alkis Evlogimenos if (op.isRegister() && op.getReg() && !op.isUse()) 2430d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos if (MRegisterInfo::isPhysicalRegister(op.getReg())) 2440d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos vacatePhysReg(mbb, mii, op.getReg()); 2450d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos else { 2460d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos unsigned physReg = vrm_.getPhys(op.getReg()); 2470d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos handleDef(mbb, mii, op.getReg(), physReg); 2480d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos mii->SetMachineOperandReg(i, physReg); 2490d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos } 2500d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos } 2510d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 2520d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos DEBUG(std::cerr << '\t'; mii->print(std::cerr, tm_)); 2530d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos } 2540d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 2550d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos for (unsigned i = 1, e = p2vMap_.size(); i != e; ++i) 2560d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos vacateJustPhysReg(mbb, mbb.getFirstTerminator(), i); 2570d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 2580d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos } 2590d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos }; 2600d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos} 2610d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 2620d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos 2630d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenosvoid llvm::eliminateVirtRegs(MachineFunction& mf, const VirtRegMap& vrm) 2640d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos{ 2650d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos Spiller(mf, vrm).eliminateVirtRegs(); 2660d6c5b6489b9abb634a1506d183ba47f1bf4d1f0Alkis Evlogimenos} 267