1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===-- RegisterScavenging.cpp - Machine register scavenging --------------===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file implements the machine register scavenger. It can provide 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// information, such as unused registers, at any point in a machine basic block. 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// It also provides a mechanism to make registers available by evicting them to 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// spill slots. 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#define DEBUG_TYPE "reg-scavenging" 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/RegisterScavenging.h" 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/MachineFrameInfo.h" 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/MachineFunction.h" 21894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/MachineBasicBlock.h" 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/MachineInstr.h" 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/MachineRegisterInfo.h" 2419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/Debug.h" 25894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Support/ErrorHandling.h" 2619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/raw_ostream.h" 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Target/TargetRegisterInfo.h" 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Target/TargetInstrInfo.h" 29894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Target/TargetMachine.h" 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/DenseMap.h" 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/SmallPtrSet.h" 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/SmallVector.h" 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/STLExtras.h" 34894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanusing namespace llvm; 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 36894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// setUsed - Set the register and its sub-registers as being used. 37894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid RegScavenger::setUsed(unsigned Reg) { 38894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RegsAvailable.reset(Reg); 39894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 40894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 41894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned SubReg = *SubRegs; ++SubRegs) 42894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RegsAvailable.reset(SubReg); 43894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 45894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool RegScavenger::isAliasUsed(unsigned Reg) const { 46894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isUsed(Reg)) 47894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 48894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (const unsigned *R = TRI->getAliasSet(Reg); *R; ++R) 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isUsed(*R)) 50894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 51894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 52894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 53894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 54894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid RegScavenger::initRegState() { 55894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ScavengedReg = 0; 56894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ScavengedRC = NULL; 57894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ScavengeRestore = NULL; 58894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 59894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // All registers started out unused. 60894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RegsAvailable.set(); 61894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 62894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Reserved registers are always used. 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RegsAvailable ^= ReservedRegs; 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!MBB) 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Live-in registers are in use. 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (MachineBasicBlock::livein_iterator I = MBB->livein_begin(), 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman E = MBB->livein_end(); I != E; ++I) 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman setUsed(*I); 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Pristine CSRs are also unavailable. 74894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BitVector PR = MBB->getParent()->getFrameInfo()->getPristineRegs(MBB); 75894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (int I = PR.find_first(); I>0; I = PR.find_next(I)) 76894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman setUsed(I); 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 78894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 79894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) { 80894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineFunction &MF = *mbb->getParent(); 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const TargetMachine &TM = MF.getTarget(); 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TII = TM.getInstrInfo(); 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TRI = TM.getRegisterInfo(); 84894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MRI = &MF.getRegInfo(); 85894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 86894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert((NumPhysRegs == 0 || NumPhysRegs == TRI->getNumRegs()) && 87894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Target changed?"); 88894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 89894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Self-initialize. 90894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!MBB) { 91894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman NumPhysRegs = TRI->getNumRegs(); 92894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman RegsAvailable.resize(NumPhysRegs); 93894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 94894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Create reserved registers bitvector. 95894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ReservedRegs = TRI->getReservedRegs(MF); 96894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 97894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Create callee-saved registers bitvector. 98894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CalleeSavedRegs.resize(NumPhysRegs); 99894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const unsigned *CSRegs = TRI->getCalleeSavedRegs(); 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (CSRegs != NULL) 101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0; CSRegs[i]; ++i) 102894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CalleeSavedRegs.set(CSRegs[i]); 103894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 104894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MBB = mbb; 106894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman initRegState(); 107894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 108894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Tracking = false; 109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid RegScavenger::addRegWithSubRegs(BitVector &BV, unsigned Reg) { 112894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BV.set(Reg); 113894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (const unsigned *R = TRI->getSubRegisters(Reg); *R; R++) 114894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BV.set(*R); 115894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 116894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 117894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid RegScavenger::addRegWithAliases(BitVector &BV, unsigned Reg) { 118894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BV.set(Reg); 119894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (const unsigned *R = TRI->getAliasSet(Reg); *R; R++) 120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BV.set(*R); 121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid RegScavenger::forward() { 124894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Move ptr forward. 125894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!Tracking) { 126894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MBBI = MBB->begin(); 127894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Tracking = true; 128894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 12919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(MBBI != MBB->end() && "Already past the end of the basic block!"); 130894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MBBI = llvm::next(MBBI); 131894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 13219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(MBBI != MBB->end() && "Already at the end of the basic block!"); 133894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 134894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineInstr *MI = MBBI; 135894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 136894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MI == ScavengeRestore) { 137894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ScavengedReg = 0; 138894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ScavengedRC = NULL; 139894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ScavengeRestore = NULL; 140894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 141894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 142894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MI->isDebugValue()) 143894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return; 144894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 145894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Find out which registers are early clobbered, killed, defined, and marked 146894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // def-dead in this instruction. 147894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // FIXME: The scavenger is not predication aware. If the instruction is 148894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // predicated, conservatively assume "kill" markers do not actually kill the 149894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // register. Similarly ignores "dead" markers. 150894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isPred = TII->isPredicated(MI); 151894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BitVector EarlyClobberRegs(NumPhysRegs); 152894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BitVector KillRegs(NumPhysRegs); 153894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BitVector DefRegs(NumPhysRegs); 154894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BitVector DeadRegs(NumPhysRegs); 155894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 156894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const MachineOperand &MO = MI->getOperand(i); 15719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!MO.isReg()) 158894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 159894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Reg = MO.getReg(); 160894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!Reg || isReserved(Reg)) 161894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 162894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 163894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MO.isUse()) { 16419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Ignore undef uses. 16519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (MO.isUndef()) 16619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 167894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Two-address operands implicitly kill. 168894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!isPred && (MO.isKill() || MI->isRegTiedToDefOperand(i))) 169894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman addRegWithSubRegs(KillRegs, Reg); 170894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 171894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(MO.isDef()); 172894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!isPred && MO.isDead()) 173894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman addRegWithSubRegs(DeadRegs, Reg); 174894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else 175894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman addRegWithSubRegs(DefRegs, Reg); 176894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MO.isEarlyClobber()) 177894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman addRegWithAliases(EarlyClobberRegs, Reg); 178894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 179894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 180894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 181894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Verify uses and defs. 182894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 183894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const MachineOperand &MO = MI->getOperand(i); 18419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!MO.isReg()) 185894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 186894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Reg = MO.getReg(); 187894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!Reg || isReserved(Reg)) 188894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 189894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MO.isUse()) { 19019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (MO.isUndef()) 19119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 192894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!isUsed(Reg)) { 193894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check if it's partial live: e.g. 194894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // D0 = insert_subreg D0<undef>, S0 195894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // ... D0 196894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // The problem is the insert_subreg could be eliminated. The use of 197894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // D0 is using a partially undef value. This is not *incorrect* since 198894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // S1 is can be freely clobbered. 199894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Ideally we would like a way to model this, but leaving the 200894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // insert_subreg around causes both correctness and performance issues. 201894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool SubUsed = false; 202894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (const unsigned *SubRegs = TRI->getSubRegisters(Reg); 203894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned SubReg = *SubRegs; ++SubRegs) 204894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isUsed(SubReg)) { 205894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SubUsed = true; 206894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 207894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 208894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(SubUsed && "Using an undefined register!"); 20919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (void)SubUsed; 210894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 211894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert((!EarlyClobberRegs.test(Reg) || MI->isRegTiedToDefOperand(i)) && 212894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Using an early clobbered register!"); 213894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 214894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(MO.isDef()); 215894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#if 0 216894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // FIXME: Enable this once we've figured out how to correctly transfer 217894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // implicit kills during codegen passes like the coalescer. 218894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert((KillRegs.test(Reg) || isUnused(Reg) || 219894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) && 220894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Re-defining a live register!"); 221894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#endif 222894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 223894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 224894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 225894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Commit the changes. 226894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman setUnused(KillRegs); 227894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman setUnused(DeadRegs); 228894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman setUsed(DefRegs); 229894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 230894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 231894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanvoid RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) { 232894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (includeReserved) 233894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman used = ~RegsAvailable; 234894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else 235894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman used = ~RegsAvailable & ~ReservedRegs; 236894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 237894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 238894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanunsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const { 239894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 240894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I != E; ++I) 24119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!isAliasUsed(*I)) { 24219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "Scavenger found unused reg: " << TRI->getName(*I) << 24319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "\n"); 244894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return *I; 24519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 246894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return 0; 247894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 248894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 249894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// getRegsAvailable - Return all available registers in the register class 250894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// in Mask. 25119bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanBitVector RegScavenger::getRegsAvailable(const TargetRegisterClass *RC) { 25219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BitVector Mask(TRI->getNumRegs()); 253894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); 254894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman I != E; ++I) 255894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!isAliasUsed(*I)) 256894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Mask.set(*I); 25719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return Mask; 258894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 259894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 260894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// findSurvivorReg - Return the candidate register that is unused for the 261894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// longest after StargMII. UseMI is set to the instruction where the search 262894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// stopped. 263894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 264894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// No more than InstrLimit instructions are inspected. 265894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman/// 266894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanunsigned RegScavenger::findSurvivorReg(MachineBasicBlock::iterator StartMI, 267894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BitVector &Candidates, 268894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned InstrLimit, 269894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock::iterator &UseMI) { 270894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int Survivor = Candidates.find_first(); 271894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Survivor > 0 && "No candidates for scavenging"); 272894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 273894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock::iterator ME = MBB->getFirstTerminator(); 274894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(StartMI != ME && "MI already at terminator"); 275894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock::iterator RestorePointMI = StartMI; 276894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock::iterator MI = StartMI; 277894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 278894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool inVirtLiveRange = false; 279894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (++MI; InstrLimit > 0 && MI != ME; ++MI, --InstrLimit) { 280894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MI->isDebugValue()) { 281894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++InstrLimit; // Don't count debug instructions 282894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 283894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 284894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isVirtKillInsn = false; 285894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isVirtDefInsn = false; 286894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Remove any candidates touched by instruction. 287894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 288894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const MachineOperand &MO = MI->getOperand(i); 289894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!MO.isReg() || MO.isUndef() || !MO.getReg()) 290894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 291894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) { 292894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MO.isDef()) 293894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman isVirtDefInsn = true; 294894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else if (MO.isKill()) 295894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman isVirtKillInsn = true; 296894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 297894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 298894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Candidates.reset(MO.getReg()); 299894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (const unsigned *R = TRI->getAliasSet(MO.getReg()); *R; R++) 300894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Candidates.reset(*R); 301894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 302894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we're not in a virtual reg's live range, this is a valid 303894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // restore point. 304894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!inVirtLiveRange) RestorePointMI = MI; 305894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 306894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Update whether we're in the live range of a virtual register 307894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isVirtKillInsn) inVirtLiveRange = false; 308894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (isVirtDefInsn) inVirtLiveRange = true; 309894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 310894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Was our survivor untouched by this instruction? 311894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Candidates.test(Survivor)) 312894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman continue; 313894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 314894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // All candidates gone? 315894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Candidates.none()) 316894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 317894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 318894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Survivor = Candidates.find_first(); 319894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 320894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we ran off the end, that's where we want to restore. 321894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MI == ME) RestorePointMI = ME; 322894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert (RestorePointMI != StartMI && 323894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "No available scavenger restore location!"); 324894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 325894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // We ran out of candidates, so stop the search. 326894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman UseMI = RestorePointMI; 327894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Survivor; 328894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 329894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 330894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanunsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC, 331894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock::iterator I, 332894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman int SPAdj) { 33319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Consider all allocatable registers in the register class initially 33419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BitVector Candidates = 33519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TRI->getAllocatableSet(*I->getParent()->getParent(), RC); 336894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 337894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Exclude all the registers being used by the instruction. 338894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 339894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineOperand &MO = I->getOperand(i); 340894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MO.isReg() && MO.getReg() != 0 && 341894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman !TargetRegisterInfo::isVirtualRegister(MO.getReg())) 342894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Candidates.reset(MO.getReg()); 343894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 344894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 345894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Try to find a register that's unused if there is one, as then we won't 34619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // have to spill. Search explicitly rather than masking out based on 34719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // RegsAvailable, as RegsAvailable does not take aliases into account. 34819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // That's what getRegsAvailable() is for. 34919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BitVector Available = getRegsAvailable(RC); 35019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 35119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if ((Candidates & Available).any()) 35219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Candidates &= Available; 353894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 354894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Find the register whose use is furthest away. 355894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock::iterator UseMI; 356894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned SReg = findSurvivorReg(I, Candidates, 25, UseMI); 357894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 358894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If we found an unused register there is no reason to spill it. 35919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!isAliasUsed(SReg)) { 36019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "Scavenged register: " << TRI->getName(SReg) << "\n"); 361894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return SReg; 36219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 363894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 364894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(ScavengedReg == 0 && 365894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Scavenger slot is live, unable to scavenge another register!"); 366894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 367894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Avoid infinite regress 368894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ScavengedReg = SReg; 369894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 370894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If the target knows how to save/restore the register, let it do so; 371894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // otherwise, use the emergency stack spill slot. 372894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!TRI->saveScavengerRegister(*MBB, I, UseMI, RC, SReg)) { 373894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Spill the scavenged register before I. 374894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(ScavengingFrameIndex >= 0 && 375894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Cannot scavenge register without an emergency spill slot!"); 376894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC,TRI); 377894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock::iterator II = prior(I); 37819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TRI->eliminateFrameIndex(II, SPAdj, this); 379894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 380894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Restore the scavenged register before its use (or first terminator). 381894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman TII->loadRegFromStackSlot(*MBB, UseMI, SReg, ScavengingFrameIndex, RC, TRI); 382894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman II = prior(UseMI); 38319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TRI->eliminateFrameIndex(II, SPAdj, this); 384894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 385894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 386894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ScavengeRestore = prior(UseMI); 387894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 388894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Doing this here leads to infinite regress. 389894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // ScavengedReg = SReg; 390894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ScavengedRC = RC; 391894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 39219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "Scavenged register (with spill): " << TRI->getName(SReg) << 39319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "\n"); 39419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 395894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return SReg; 396894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 397