RegisterScavenging.cpp revision 2048e4ab7fb4ed45bae2159bae600ddf610303b1
14d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner//===-- RegisterScavenging.cpp - Machine register scavenging --------------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 94d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// 104d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// This file implements the machine register scavenger. It can provide 114d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// information, such as unused registers, at any point in a machine basic block. 124d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// It also provides a mechanism to make registers available by evicting them to 134d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// spill slots. 144d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner// 154d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner//===----------------------------------------------------------------------===// 16d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth 173333e668221f52f8c708df0037ee9c4bf2417929Evgeniy Stepanov#define DEBUG_TYPE "reg-scavenging" 1858a2cbef4aac9ee7d530dfb690c78d6fc11a2371Chandler Carruth#include "llvm/CodeGen/RegisterScavenging.h" 19d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineFrameInfo.h" 20d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineFunction.h" 21d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineBasicBlock.h" 22d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineInstr.h" 23d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineRegisterInfo.h" 2406cb8ed00696eb14d1b831921452e50ec0568ea2Chandler Carruth#include "llvm/Support/Debug.h" 250bcbd1df7a204e1e512f1a27066d725309de1b13Bill Wendling#include "llvm/Support/ErrorHandling.h" 260b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/Support/raw_ostream.h" 270b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/Target/TargetRegisterInfo.h" 280b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/Target/TargetInstrInfo.h" 290b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/Target/TargetMachine.h" 300b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/ADT/DenseMap.h" 310b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/ADT/SmallPtrSet.h" 320b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/ADT/SmallVector.h" 330b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/ADT/STLExtras.h" 340b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruthusing namespace llvm; 350b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth 360b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth/// setUsed - Set the register and its sub-registers as being used. 370b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruthvoid RegScavenger::setUsed(unsigned Reg) { 38dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner RegsAvailable.reset(Reg); 39dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner 40c5f52e6da18e6e8ccb62aac2a4cb431df98e7d6dChris Lattner for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 41c5f52e6da18e6e8ccb62aac2a4cb431df98e7d6dChris Lattner unsigned SubReg = *SubRegs; ++SubRegs) 4219f2dc436df4f768484287a478973e83efd4202aChris Lattner RegsAvailable.reset(SubReg); 43dce94d92df77da125a1c1256a9294db891a9db9cChris Lattner} 44abbc2dd77908f146f73f4cd1abfdfe47faacf43dChris Lattner 45d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekebool RegScavenger::isAliasUsed(unsigned Reg) const { 464d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner if (isUsed(Reg)) 473481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner return true; 484d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner for (const unsigned *R = TRI->getAliasSet(Reg); *R; ++R) 494d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner if (isUsed(*R)) 505649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel return true; 515649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel return false; 525649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel} 535649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel 545649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommelvoid RegScavenger::initRegState() { 555649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel ScavengedReg = 0; 565649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel ScavengedRC = NULL; 578e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer ScavengeRestore = NULL; 588e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer 5976ae3445f81164aaff9f95123426109c119f27c0Chris Lattner // All registers started out unused. 6062fb3556eab41d9d66994e92d15e3e707c181988Devang Patel RegsAvailable.set(); 61fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 624d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // Reserved registers are always used. 634d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner RegsAvailable ^= ReservedRegs; 644d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 65c1bb13f1b8794aa6f3219b3ac567f569ad78a6d1Gabor Greif if (!MBB) 66c1bb13f1b8794aa6f3219b3ac567f569ad78a6d1Gabor Greif return; 674d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 686b6b6ef1677fa71b1072c2911b4c1f9524a558c9Zhou Sheng // Live-in registers are in use. 694d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(), 704d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner E = MBB->livein_end(); I != E; ++I) 71579dca12c2cfd60bc18aaadbd5331897d48fec29Reid Spencer setUsed(*I); 72579dca12c2cfd60bc18aaadbd5331897d48fec29Reid Spencer 734d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // Pristine CSRs are also unavailable. 74fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman BitVector PR = MBB->getParent()->getFrameInfo()->getPristineRegs(MBB); 75fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman for (int I = PR.find_first(); I>0; I = PR.find_next(I)) 764d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner setUsed(I); 774d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner} 784d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 794d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattnervoid RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) { 801a0390253b3e7c2327139d81e5a8c16d5bf85aa8Jay Foad MachineFunction &MF = *mbb->getParent(); 814d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner const TargetMachine &TM = MF.getTarget(); 828f9ffbd056172da470bcd3a9f1d5b4c2414fce59Jay Foad TII = TM.getInstrInfo(); 8362fb3556eab41d9d66994e92d15e3e707c181988Devang Patel TRI = TM.getRegisterInfo(); 848f9ffbd056172da470bcd3a9f1d5b4c2414fce59Jay Foad MRI = &MF.getRegInfo(); 854d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 860a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner assert((NumPhysRegs == 0 || NumPhysRegs == TRI->getNumRegs()) && 870a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner "Target changed?"); 880a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner 89fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman // Self-initialize. 904d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner if (!MBB) { 914d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner NumPhysRegs = TRI->getNumRegs(); 924d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner RegsAvailable.resize(NumPhysRegs); 934d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 944d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // Create reserved registers bitvector. 954d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner ReservedRegs = TRI->getReservedRegs(MF); 964d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 978f9ffbd056172da470bcd3a9f1d5b4c2414fce59Jay Foad // Create callee-saved registers bitvector. 9862fb3556eab41d9d66994e92d15e3e707c181988Devang Patel CalleeSavedRegs.resize(NumPhysRegs); 995649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel const unsigned *CSRegs = TRI->getCalleeSavedRegs(); 1008f9ffbd056172da470bcd3a9f1d5b4c2414fce59Jay Foad if (CSRegs != NULL) 1015649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel for (unsigned i = 0; CSRegs[i]; ++i) 1028e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer CalleeSavedRegs.set(CSRegs[i]); 1034d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner } 1044d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 1050a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner MBB = mbb; 1060a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner initRegState(); 1070a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner 1080a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner Tracking = false; 10910b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner} 11010b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner 11110b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattnervoid RegScavenger::addRegWithSubRegs(BitVector &BV, unsigned Reg) { 112c10fa6c801e48771b5eade50afc2fe6abaf08227Stepan Dyatkovskiy BV.set(Reg); 1137d6c24cdbf41522818ec9ae7b8d3b624660853c1Chris Lattner for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++) 11410b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner BV.set(*R); 1150a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner} 1163d3abe0852d5f499bed7ab014519dd582a0a795dStepan Dyatkovskiy 117c10fa6c801e48771b5eade50afc2fe6abaf08227Stepan Dyatkovskiyvoid RegScavenger::addRegWithAliases(BitVector &BV, unsigned Reg) { 11810b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner BV.set(Reg); 119c10fa6c801e48771b5eade50afc2fe6abaf08227Stepan Dyatkovskiy for (const unsigned *R = TRI->getAliasSet(Reg); *R; R++) 120c10fa6c801e48771b5eade50afc2fe6abaf08227Stepan Dyatkovskiy BV.set(*R); 12110b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner} 12210b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner 12310b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattnervoid RegScavenger::forward() { 1247d6c24cdbf41522818ec9ae7b8d3b624660853c1Chris Lattner // Move ptr forward. 1257d6c24cdbf41522818ec9ae7b8d3b624660853c1Chris Lattner if (!Tracking) { 126c10fa6c801e48771b5eade50afc2fe6abaf08227Stepan Dyatkovskiy MBBI = MBB->begin(); 127ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren Tracking = true; 128ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren } else { 129ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren assert(MBBI != MBB->end() && "Already past the end of the basic block!"); 130ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren MBBI = llvm::next(MBBI); 131ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren } 132ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren assert(MBBI != MBB->end() && "Already at the end of the basic block!"); 133ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren 134ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren MachineInstr *MI = MBBI; 135ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren 136ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren if (MI == ScavengeRestore) { 137ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren ScavengedReg = 0; 138ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren ScavengedRC = NULL; 139ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren ScavengeRestore = NULL; 140ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren } 141ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren 142ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren if (MI->isDebugValue()) 143ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren return; 144ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren 145ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren // Find out which registers are early clobbered, killed, defined, and marked 146ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren // def-dead in this instruction. 147ee99c7f1bfe115f8fe2d1b118010a82c1ce83f18Manman Ren // FIXME: The scavenger is not predication aware. If the instruction is 1480a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner // predicated, conservatively assume "kill" markers do not actually kill the 1497d6c24cdbf41522818ec9ae7b8d3b624660853c1Chris Lattner // register. Similarly ignores "dead" markers. 1507d6c24cdbf41522818ec9ae7b8d3b624660853c1Chris Lattner bool isPred = TII->isPredicated(MI); 151c10fa6c801e48771b5eade50afc2fe6abaf08227Stepan Dyatkovskiy BitVector EarlyClobberRegs(NumPhysRegs); 1527d6c24cdbf41522818ec9ae7b8d3b624660853c1Chris Lattner BitVector KillRegs(NumPhysRegs); 1537d6c24cdbf41522818ec9ae7b8d3b624660853c1Chris Lattner BitVector DefRegs(NumPhysRegs); 1547d6c24cdbf41522818ec9ae7b8d3b624660853c1Chris Lattner BitVector DeadRegs(NumPhysRegs); 15510b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 15610b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner const MachineOperand &MO = MI->getOperand(i); 15710b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner if (!MO.isReg()) 158c10fa6c801e48771b5eade50afc2fe6abaf08227Stepan Dyatkovskiy continue; 15910b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner unsigned Reg = MO.getReg(); 160694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner if (!Reg || isReserved(Reg)) 16110b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner continue; 16210b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner 16310b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner if (MO.isUse()) { 16410b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // Ignore undef uses. 165694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner if (MO.isUndef()) 166694e37f08a7c09ccc24642532106295cf7b3a1e3Chris Lattner continue; 16710b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // Two-address operands implicitly kill. 16810b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner if (!isPred && (MO.isKill() || MI->isRegTiedToDefOperand(i))) 16910b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner addRegWithSubRegs(KillRegs, Reg); 1700a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner } else { 17162fb3556eab41d9d66994e92d15e3e707c181988Devang Patel assert(MO.isDef()); 17210b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner if (!isPred && MO.isDead()) 17310b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner addRegWithSubRegs(DeadRegs, Reg); 17410b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner else 17510b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner addRegWithSubRegs(DefRegs, Reg); 17610b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner if (MO.isEarlyClobber()) 17710b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner addRegWithAliases(EarlyClobberRegs, Reg); 17810b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner } 17910b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner } 18010b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner 18110b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // Verify uses and defs. 18210b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 18310b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner const MachineOperand &MO = MI->getOperand(i); 1840a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner if (!MO.isReg() || MO.isUndef()) 1855649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel continue; 1865649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel unsigned Reg = MO.getReg(); 1875649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel if (!Reg || isReserved(Reg)) 1888e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer continue; 18910b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner if (MO.isUse()) { 1900a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner if (!isUsed(Reg)) { 1910a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner // Check if it's partial live: e.g. 19224473120a253a05f3601cd3373403b47e6d03d41Stepan Dyatkovskiy // D0 = insert_subreg D0<undef>, S0 19310b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // ... D0 19410b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner // The problem is the insert_subreg could be eliminated. The use of 1953d3abe0852d5f499bed7ab014519dd582a0a795dStepan Dyatkovskiy // D0 is using a partially undef value. This is not *incorrect* since 19647cbc4e0ee6098b7be3c60108000a979f1809949Stepan Dyatkovskiy // S1 is can be freely clobbered. 19747cbc4e0ee6098b7be3c60108000a979f1809949Stepan Dyatkovskiy // Ideally we would like a way to model this, but leaving the 198484fc93eff0295b1aa52b9a64d22346580e4b0e2Stepan Dyatkovskiy // insert_subreg around causes both correctness and performance issues. 199a2067fbe22930be8413584ae58c5ef78bd032190Stepan Dyatkovskiy bool SubUsed = false; 20047cbc4e0ee6098b7be3c60108000a979f1809949Stepan Dyatkovskiy for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 201484fc93eff0295b1aa52b9a64d22346580e4b0e2Stepan Dyatkovskiy unsigned SubReg = *SubRegs; ++SubRegs) 202a2067fbe22930be8413584ae58c5ef78bd032190Stepan Dyatkovskiy if (isUsed(SubReg)) { 203a2067fbe22930be8413584ae58c5ef78bd032190Stepan Dyatkovskiy SubUsed = true; 204ad2890760f9661fb6a3dfa3ca863a87f6aea4139Manman Ren break; 205ad2890760f9661fb6a3dfa3ca863a87f6aea4139Manman Ren } 206ad2890760f9661fb6a3dfa3ca863a87f6aea4139Manman Ren assert(SubUsed && "Using an undefined register!"); 207ad2890760f9661fb6a3dfa3ca863a87f6aea4139Manman Ren } 208ad2890760f9661fb6a3dfa3ca863a87f6aea4139Manman Ren assert((!EarlyClobberRegs.test(Reg) || MI->isRegTiedToDefOperand(i)) && 209ad2890760f9661fb6a3dfa3ca863a87f6aea4139Manman Ren "Using an early clobbered register!"); 210ad2890760f9661fb6a3dfa3ca863a87f6aea4139Manman Ren } else { 211ad2890760f9661fb6a3dfa3ca863a87f6aea4139Manman Ren assert(MO.isDef()); 212ad2890760f9661fb6a3dfa3ca863a87f6aea4139Manman Ren#if 0 213ad2890760f9661fb6a3dfa3ca863a87f6aea4139Manman Ren // FIXME: Enable this once we've figured out how to correctly transfer 214ad2890760f9661fb6a3dfa3ca863a87f6aea4139Manman Ren // implicit kills during codegen passes like the coalescer. 215ad2890760f9661fb6a3dfa3ca863a87f6aea4139Manman Ren assert((KillRegs.test(Reg) || isUnused(Reg) || 216ad2890760f9661fb6a3dfa3ca863a87f6aea4139Manman Ren isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) && 217ad2890760f9661fb6a3dfa3ca863a87f6aea4139Manman Ren "Re-defining a live register!"); 218a2067fbe22930be8413584ae58c5ef78bd032190Stepan Dyatkovskiy#endif 219a2067fbe22930be8413584ae58c5ef78bd032190Stepan Dyatkovskiy } 220a2067fbe22930be8413584ae58c5ef78bd032190Stepan Dyatkovskiy } 221a2067fbe22930be8413584ae58c5ef78bd032190Stepan Dyatkovskiy 222a2067fbe22930be8413584ae58c5ef78bd032190Stepan Dyatkovskiy // Commit the changes. 22310b1f5a94196f27c75c950ba7ed26bd0a62c91e9Chris Lattner setUnused(KillRegs); 2240a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner setUnused(DeadRegs); 2250a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner setUsed(DefRegs); 2260a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner} 2270a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner 2280a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattnervoid RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) { 2290a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner if (includeReserved) 2300a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner used = ~RegsAvailable; 2310a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner else 2320a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner used = ~RegsAvailable & ~ReservedRegs; 23362fb3556eab41d9d66994e92d15e3e707c181988Devang Patel} 2340a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner 2350a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattnerunsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const { 2360a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 2370a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner I != E; ++I) 2380a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner if (!isAliasUsed(*I)) { 2390a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner DEBUG(dbgs() << "Scavenger found unused reg: " << TRI->getName(*I) << 2400a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner "\n"); 2415649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel return *I; 2420a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner } 2435649ba70fb39f2fda4791d255ae8bb373071874fFrits van Bommel return 0; 2448e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer} 2450a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner 2460a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner/// getRegsAvailable - Return all available registers in the register class 2470a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner/// in Mask. 2480a4c6789d5adafb6eb33080fe1833b416a152d7cChris LattnerBitVector RegScavenger::getRegsAvailable(const TargetRegisterClass *RC) { 2490a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner BitVector Mask(TRI->getNumRegs()); 2500a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 2510a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner I != E; ++I) 2520a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner if (!isAliasUsed(*I)) 2530a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner Mask.set(*I); 2540a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner return Mask; 2550a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner} 2564d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner 2570a4c6789d5adafb6eb33080fe1833b416a152d7cChris Lattner/// findSurvivorReg - Return the candidate register that is unused for the 2584d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner/// longest after StargMII. UseMI is set to the instruction where the search 2594d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner/// stopped. 2604d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner/// 2614d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner/// No more than InstrLimit instructions are inspected. 2624d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner/// 26340d8c28b27377199b7465ba2c5a2c59c6fd12fa9Chris Lattnerunsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI, 2644d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner BitVector &Candidates, 2654d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner unsigned InstrLimit, 2663481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner MachineBasicBlock::iterator &UseMI) { 2673481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner int Survivor = Candidates.find_first(); 2683481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner assert(Survivor > 0 && "No candidates for scavenging"); 2698e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer 2708e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer MachineBasicBlock::iterator ME = MBB->getFirstTerminator(); 271ec710c5b12af647ae90f53917122726269c18738Chris Lattner assert(StartMI != ME && "MI already at terminator"); 27200b16889ab461b7ecef1c91ade101186b7f1fce2Jeff Cohen MachineBasicBlock::iterator RestorePointMI = StartMI; 273187b1924a4b68350a6492b116db0fb19c659222fBill Wendling MachineBasicBlock::iterator MI = StartMI; 274187b1924a4b68350a6492b116db0fb19c659222fBill Wendling 275187b1924a4b68350a6492b116db0fb19c659222fBill Wendling bool inVirtLiveRange = false; 276187b1924a4b68350a6492b116db0fb19c659222fBill Wendling for (++MI; InstrLimit > 0 && MI != ME; ++MI, --InstrLimit) { 2779c5822a966572ea78f4e818870d4229c7a855749Devang Patel if (MI->isDebugValue()) { 2789c5822a966572ea78f4e818870d4229c7a855749Devang Patel ++InstrLimit; // Don't count debug instructions 2799c5822a966572ea78f4e818870d4229c7a855749Devang Patel continue; 2803e69c13c301acee99c8bde7e692777bf856a6362Nick Lewycky } 2819c5822a966572ea78f4e818870d4229c7a855749Devang Patel bool isVirtKillInsn = false; 282b99462117ebd4be41788346246d7935fc90a11eeDevang Patel bool isVirtDefInsn = false; 2833e69c13c301acee99c8bde7e692777bf856a6362Nick Lewycky // Remove any candidates touched by instruction. 284b99462117ebd4be41788346246d7935fc90a11eeDevang Patel for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 2859c5822a966572ea78f4e818870d4229c7a855749Devang Patel const MachineOperand &MO = MI->getOperand(i); 2869c5822a966572ea78f4e818870d4229c7a855749Devang Patel if (!MO.isReg() || MO.isUndef() || !MO.getReg()) 287b99462117ebd4be41788346246d7935fc90a11eeDevang Patel continue; 2889c5822a966572ea78f4e818870d4229c7a855749Devang Patel if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) { 2899c5822a966572ea78f4e818870d4229c7a855749Devang Patel if (MO.isDef()) 2907af1c78b98d2df7d0ab9154461ca3d835706716eDuncan Sands isVirtDefInsn = true; 2917af1c78b98d2df7d0ab9154461ca3d835706716eDuncan Sands else if (MO.isKill()) 2927af1c78b98d2df7d0ab9154461ca3d835706716eDuncan Sands isVirtKillInsn = true; 2937af1c78b98d2df7d0ab9154461ca3d835706716eDuncan Sands continue; 2943e69c13c301acee99c8bde7e692777bf856a6362Nick Lewycky } 295741c0aea08feab0ebd1932aaa8dd38836b2073eaChris Lattner Candidates.reset(MO.getReg()); 296741c0aea08feab0ebd1932aaa8dd38836b2073eaChris Lattner for (const unsigned *R = TRI->getAliasSet(MO.getReg()); *R; R++) 297741c0aea08feab0ebd1932aaa8dd38836b2073eaChris Lattner Candidates.reset(*R); 2983e69c13c301acee99c8bde7e692777bf856a6362Nick Lewycky } 2993e69c13c301acee99c8bde7e692777bf856a6362Nick Lewycky // If we're not in a virtual reg's live range, this is a valid 3003e69c13c301acee99c8bde7e692777bf856a6362Nick Lewycky // restore point. 3013e69c13c301acee99c8bde7e692777bf856a6362Nick Lewycky if (!inVirtLiveRange) RestorePointMI = MI; 3023e69c13c301acee99c8bde7e692777bf856a6362Nick Lewycky 3033e69c13c301acee99c8bde7e692777bf856a6362Nick Lewycky // Update whether we're in the live range of a virtual register 3044a3935c27e5315081844a5b7ae1f7097efc234b0Nick Lewycky if (isVirtKillInsn) inVirtLiveRange = false; 3058e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer if (isVirtDefInsn) inVirtLiveRange = true; 3064a3935c27e5315081844a5b7ae1f7097efc234b0Nick Lewycky 3078e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer // Was our survivor untouched by this instruction? 3084a3935c27e5315081844a5b7ae1f7097efc234b0Nick Lewycky if (Candidates.test(Survivor)) 3094a3935c27e5315081844a5b7ae1f7097efc234b0Nick Lewycky continue; 3104a3935c27e5315081844a5b7ae1f7097efc234b0Nick Lewycky 311ec710c5b12af647ae90f53917122726269c18738Chris Lattner // All candidates gone? 3124d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner if (Candidates.none()) 3134d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner break; 3143481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner 3153481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner Survivor = Candidates.find_first(); 31690fe0bd68cdbeb980c08628c4992dffad0dc728fDan Gohman } 31790fe0bd68cdbeb980c08628c4992dffad0dc728fDan Gohman // If we ran off the end, that's where we want to restore. 3188e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer if (MI == ME) RestorePointMI = ME; 3198e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer assert (RestorePointMI != StartMI && 3208e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer "No available scavenger restore location!"); 3213481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner 3228e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer // We ran out of candidates, so stop the search. 32390fe0bd68cdbeb980c08628c4992dffad0dc728fDan Gohman UseMI = RestorePointMI; 3243481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattner return Survivor; 3257605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner} 3267605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner 3273481f24c06b3c9de48bdd99c37547471ca8e761eChris Lattnerunsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, 328321a813c536e2f1f2f05bbe78a7fbf64046f0557Dan Gohman MachineBasicBlock::iterator I, 329e9d87f49063cb1bd213d8e9c339b9b63393cc2d9Dan Gohman int SPAdj) { 3302872177834d83b42cd042a37299cb7089965f36bChris Lattner // Consider all allocatable registers in the register class initially 3317605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner BitVector Candidates = 3327605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner TRI->getAllocatableSet(*I->getParent()->getParent(), RC); 3337605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner 3347605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner // Exclude all the registers being used by the instruction. 3357605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 3367605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner MachineOperand &MO = I->getOperand(i); 3377605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner if (MO.isReg() && MO.getReg() != 0 && 3387605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner !TargetRegisterInfo::isVirtualRegister(MO.getReg())) 3397605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner Candidates.reset(MO.getReg()); 3407605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner } 3417605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner 3427605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner // Try to find a register that's unused if there is one, as then we won't 3438e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer // have to spill. Search explicitly rather than masking out based on 3447605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner // RegsAvailable, as RegsAvailable does not take aliases into account. 3457605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner // That's what getRegsAvailable() is for. 3467605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner BitVector Available = getRegsAvailable(RC); 3477605730ba8eaf248a8285bb2055e131f13c15b63Chris Lattner 348321a813c536e2f1f2f05bbe78a7fbf64046f0557Dan Gohman if ((Candidates & Available).any()) 34990fe0bd68cdbeb980c08628c4992dffad0dc728fDan Gohman Candidates &= Available; 35090fe0bd68cdbeb980c08628c4992dffad0dc728fDan Gohman 3514d1e46e7b06534cde262d32fad038135f406b6b7Chris Lattner // Find the register whose use is furthest away. 352b29714a10af94b6daae437e48a82ae32675f79cbChris Lattner MachineBasicBlock::iterator UseMI; 3531a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewycky unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI); 3541a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewycky 355b4098ba03d51a3845bde5aeb4fca893d1a90d3f8Duncan Sands // If we found an unused register there is no reason to spill it. 356b4098ba03d51a3845bde5aeb4fca893d1a90d3f8Duncan Sands if (!isAliasUsed(SReg)) { 3571a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewycky DEBUG(dbgs() << "Scavenged register: " << TRI->getName(SReg) << "\n"); 3581a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewycky return SReg; 3591a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewycky } 3601a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewycky 361b4098ba03d51a3845bde5aeb4fca893d1a90d3f8Duncan Sands assert(ScavengedReg == 0 && 3621a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewycky "Scavenger slot is live, unable to scavenge another register!"); 3631a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewycky 3641a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewycky // Avoid infinite regress 3651a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewycky ScavengedReg = SReg; 3661a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewycky 3671a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewycky // If the target knows how to save/restore the register, let it do so; 3681a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewycky // otherwise, use the emergency stack spill slot. 3691a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewycky if (!TRI->saveScavengerRegister(*MBB, I, UseMI, RC, SReg)) { 3701a4021a2be4a59e9f9010776cb6f72107241aeb5Nick Lewycky // Spill the scavenged register before I. 371afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman assert(ScavengingFrameIndex >= 0 && 372afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman "Cannot scavenge register without an emergency spill slot!"); 373afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC,TRI); 374afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman MachineBasicBlock::iterator II = prior(I); 3752cfbf018a938d14126b9cb10c600e025f9831d2dDuncan Sands TRI->eliminateFrameIndex(II, SPAdj, this); 3768e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer 3778e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer // Restore the scavenged register before its use (or first terminator). 378b4098ba03d51a3845bde5aeb4fca893d1a90d3f8Duncan Sands TII->loadRegFromStackSlot(*MBB, UseMI, SReg, ScavengingFrameIndex, RC, TRI); 379b4098ba03d51a3845bde5aeb4fca893d1a90d3f8Duncan Sands II = prior(UseMI); 380b4098ba03d51a3845bde5aeb4fca893d1a90d3f8Duncan Sands TRI->eliminateFrameIndex(II, SPAdj, this); 381b4098ba03d51a3845bde5aeb4fca893d1a90d3f8Duncan Sands } 3828e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer 383afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman ScavengeRestore = prior(UseMI); 384b4098ba03d51a3845bde5aeb4fca893d1a90d3f8Duncan Sands 385afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman // Doing this here leads to infinite regress. 386b4098ba03d51a3845bde5aeb4fca893d1a90d3f8Duncan Sands // ScavengedReg = SReg; 387b4098ba03d51a3845bde5aeb4fca893d1a90d3f8Duncan Sands ScavengedRC = RC; 388b4098ba03d51a3845bde5aeb4fca893d1a90d3f8Duncan Sands 3898e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer DEBUG(dbgs() << "Scavenged register (with spill): " << TRI->getName(SReg) << 3902cfbf018a938d14126b9cb10c600e025f9831d2dDuncan Sands "\n"); 391b4098ba03d51a3845bde5aeb4fca893d1a90d3f8Duncan Sands 392b4098ba03d51a3845bde5aeb4fca893d1a90d3f8Duncan Sands return SReg; 393b4098ba03d51a3845bde5aeb4fca893d1a90d3f8Duncan Sands} 394afc36a9520971832dfbebc0333593bf5d3098296Dan Gohman