RegisterScavenging.cpp revision d9df5017040489303acb57bdd8697ef0f8bafc08
196fa612373e258120d351ed14361f964ad22f99dEvan Cheng//===-- RegisterScavenging.cpp - Machine register scavenging --------------===//
296fa612373e258120d351ed14361f964ad22f99dEvan Cheng//
396fa612373e258120d351ed14361f964ad22f99dEvan Cheng//                     The LLVM Compiler Infrastructure
496fa612373e258120d351ed14361f964ad22f99dEvan Cheng//
54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source
64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details.
796fa612373e258120d351ed14361f964ad22f99dEvan Cheng//
896fa612373e258120d351ed14361f964ad22f99dEvan Cheng//===----------------------------------------------------------------------===//
996fa612373e258120d351ed14361f964ad22f99dEvan Cheng//
1096fa612373e258120d351ed14361f964ad22f99dEvan Cheng// This file implements the machine register scavenger. It can provide
11ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling// information, such as unused registers, at any point in a machine basic block.
12ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling// It also provides a mechanism to make registers available by evicting them to
13ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling// spill slots.
1496fa612373e258120d351ed14361f964ad22f99dEvan Cheng//
1596fa612373e258120d351ed14361f964ad22f99dEvan Cheng//===----------------------------------------------------------------------===//
1696fa612373e258120d351ed14361f964ad22f99dEvan Cheng
1796fa612373e258120d351ed14361f964ad22f99dEvan Cheng#define DEBUG_TYPE "reg-scavenging"
1896fa612373e258120d351ed14361f964ad22f99dEvan Cheng#include "llvm/CodeGen/RegisterScavenging.h"
1996fa612373e258120d351ed14361f964ad22f99dEvan Cheng#include "llvm/CodeGen/MachineFunction.h"
2096fa612373e258120d351ed14361f964ad22f99dEvan Cheng#include "llvm/CodeGen/MachineBasicBlock.h"
2196fa612373e258120d351ed14361f964ad22f99dEvan Cheng#include "llvm/CodeGen/MachineInstr.h"
221dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng#include "llvm/CodeGen/MachineRegisterInfo.h"
236f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman#include "llvm/Target/TargetRegisterInfo.h"
2496fa612373e258120d351ed14361f964ad22f99dEvan Cheng#include "llvm/Target/TargetInstrInfo.h"
2596fa612373e258120d351ed14361f964ad22f99dEvan Cheng#include "llvm/Target/TargetMachine.h"
261dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng#include "llvm/ADT/SmallPtrSet.h"
27d68a07650cdb2e18f18f362ba533459aa10e01b6Dan Gohman#include "llvm/ADT/SmallVector.h"
28ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng#include "llvm/ADT/STLExtras.h"
2996fa612373e258120d351ed14361f964ad22f99dEvan Chengusing namespace llvm;
3096fa612373e258120d351ed14361f964ad22f99dEvan Cheng
31ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling/// RedefinesSuperRegPart - Return true if the specified register is redefining
32ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling/// part of a super-register.
33ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendlingstatic bool RedefinesSuperRegPart(const MachineInstr *MI, unsigned SubReg,
34ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling                                  const TargetRegisterInfo *TRI) {
35d68f47c6fd744e051f7f2d97b6366d40bf27c438Evan Cheng  bool SeenSuperUse = false;
36d68f47c6fd744e051f7f2d97b6366d40bf27c438Evan Cheng  bool SeenSuperDef = false;
37ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
38ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling    const MachineOperand &MO = MI->getOperand(i);
39d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman    if (!MO.isReg())
40ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling      continue;
4143e2a035309f4e353a8bd5547d10125414597e74Duncan Sands    if (TRI->isSuperRegister(SubReg, MO.getReg())) {
42d68f47c6fd744e051f7f2d97b6366d40bf27c438Evan Cheng      if (MO.isUse())
43d68f47c6fd744e051f7f2d97b6366d40bf27c438Evan Cheng        SeenSuperUse = true;
44d68f47c6fd744e051f7f2d97b6366d40bf27c438Evan Cheng      else if (MO.isImplicit())
45d68f47c6fd744e051f7f2d97b6366d40bf27c438Evan Cheng        SeenSuperDef = true;
4643e2a035309f4e353a8bd5547d10125414597e74Duncan Sands    }
47ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling  }
48ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling
49d68f47c6fd744e051f7f2d97b6366d40bf27c438Evan Cheng  return SeenSuperDef && SeenSuperUse;
50ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling}
51ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling
52ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendlingstatic bool RedefinesSuperRegPart(const MachineInstr *MI,
53ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling                                  const MachineOperand &MO,
54ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling                                  const TargetRegisterInfo *TRI) {
55d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman  assert(MO.isReg() && MO.isDef() && "Not a register def!");
56ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling  return RedefinesSuperRegPart(MI, MO.getReg(), TRI);
57ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling}
58ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling
59a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling/// setUsed - Set the register and its sub-registers as being used.
605d3600f5766e93cb459ef6108fba00c052aa6388Evan Chengvoid RegScavenger::setUsed(unsigned Reg, bool ImpDef) {
61a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling  RegsAvailable.reset(Reg);
625d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng  ImplicitDefed[Reg] = ImpDef;
63a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling
646130f66eaae89f8878590796977678afa8448926Evan Cheng  for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
655d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng       unsigned SubReg = *SubRegs; ++SubRegs) {
66a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling    RegsAvailable.reset(SubReg);
675d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng    ImplicitDefed[SubReg] = ImpDef;
685d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng  }
69a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling}
70a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling
71a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling/// setUnused - Set the register and its sub-registers as being unused.
72ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendlingvoid RegScavenger::setUnused(unsigned Reg, const MachineInstr *MI) {
73a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling  RegsAvailable.set(Reg);
745d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng  ImplicitDefed.reset(Reg);
75a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling
766130f66eaae89f8878590796977678afa8448926Evan Cheng  for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
77a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling       unsigned SubReg = *SubRegs; ++SubRegs)
785d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng    if (!RedefinesSuperRegPart(MI, Reg, TRI)) {
79ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling      RegsAvailable.set(SubReg);
805d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng      ImplicitDefed.reset(SubReg);
815d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng    }
82a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling}
83a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling
84a3756ee7fe384210eddcfd66e2934439960b13a1Evan Chengvoid RegScavenger::enterBasicBlock(MachineBasicBlock *mbb) {
854542611bb9793e8376d7d5f33b4a1e2d11712894Dan Gohman  MachineFunction &MF = *mbb->getParent();
8696fa612373e258120d351ed14361f964ad22f99dEvan Cheng  const TargetMachine &TM = MF.getTarget();
87b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng  TII = TM.getInstrInfo();
886130f66eaae89f8878590796977678afa8448926Evan Cheng  TRI = TM.getRegisterInfo();
891dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng  MRI = &MF.getRegInfo();
9096fa612373e258120d351ed14361f964ad22f99dEvan Cheng
916130f66eaae89f8878590796977678afa8448926Evan Cheng  assert((NumPhysRegs == 0 || NumPhysRegs == TRI->getNumRegs()) &&
92898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng         "Target changed?");
93898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng
94898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng  if (!MBB) {
956130f66eaae89f8878590796977678afa8448926Evan Cheng    NumPhysRegs = TRI->getNumRegs();
96c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen    RegsAvailable.resize(NumPhysRegs);
975d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng    ImplicitDefed.resize(NumPhysRegs);
98898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng
99a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng    // Create reserved registers bitvector.
1006130f66eaae89f8878590796977678afa8448926Evan Cheng    ReservedRegs = TRI->getReservedRegs(MF);
101a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng
102898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng    // Create callee-saved registers bitvector.
103898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng    CalleeSavedRegs.resize(NumPhysRegs);
1046130f66eaae89f8878590796977678afa8448926Evan Cheng    const unsigned *CSRegs = TRI->getCalleeSavedRegs();
105898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng    if (CSRegs != NULL)
106898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng      for (unsigned i = 0; CSRegs[i]; ++i)
107898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng        CalleeSavedRegs.set(CSRegs[i]);
108898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng  }
109898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng
110898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng  MBB = mbb;
111caddd590f72376aaac531c1004be0535b460992aEvan Cheng  ScavengedReg = 0;
112caddd590f72376aaac531c1004be0535b460992aEvan Cheng  ScavengedRC = NULL;
113d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng  ScavengeRestore = NULL;
114d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng  CurrDist = 0;
115d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng  DistanceMap.clear();
1161385758215bb31ba042a3d42e40d28e521616a0cDan Gohman  ImplicitDefed.reset();
117898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng
118898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng  // All registers started out unused.
119c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen  RegsAvailable.set();
12096fa612373e258120d351ed14361f964ad22f99dEvan Cheng
121a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng  // Reserved registers are always used.
122c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen  RegsAvailable ^= ReservedRegs;
12396fa612373e258120d351ed14361f964ad22f99dEvan Cheng
124403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng  // Live-in registers are in use.
125403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng  if (!MBB->livein_empty())
126403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng    for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
127403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng           E = MBB->livein_end(); I != E; ++I)
128403c45dfcc74585b02339b5f55f739672e3d141aEvan Cheng      setUsed(*I);
129a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng
130a3756ee7fe384210eddcfd66e2934439960b13a1Evan Cheng  Tracking = false;
13196fa612373e258120d351ed14361f964ad22f99dEvan Cheng}
13296fa612373e258120d351ed14361f964ad22f99dEvan Cheng
133b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Chengvoid RegScavenger::restoreScavengedReg() {
134f6372aa1cc568df19da7c5023e83c75aa9404a07Owen Anderson  TII->loadRegFromStackSlot(*MBB, MBBI, ScavengedReg,
1351dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng                            ScavengingFrameIndex, ScavengedRC);
136b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng  MachineBasicBlock::iterator II = prior(MBBI);
1376130f66eaae89f8878590796977678afa8448926Evan Cheng  TRI->eliminateFrameIndex(II, 0, this);
138b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng  setUsed(ScavengedReg);
139b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng  ScavengedReg = 0;
140b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng  ScavengedRC = NULL;
141b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng}
142b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng
1432755896fd048d189bedc5e99e776b3eca010dd4eDevang Patel#ifndef NDEBUG
1441dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng/// isLiveInButUnusedBefore - Return true if register is livein the MBB not
1451dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng/// not used before it reaches the MI that defines register.
1461dc7869025d91906e8305e921ddb82dac780d70eEvan Chengstatic bool isLiveInButUnusedBefore(unsigned Reg, MachineInstr *MI,
1471dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng                                    MachineBasicBlock *MBB,
1481dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng                                    const TargetRegisterInfo *TRI,
1491dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng                                    MachineRegisterInfo* MRI) {
1501dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng  // First check if register is livein.
1511dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng  bool isLiveIn = false;
1521dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng  for (MachineBasicBlock::const_livein_iterator I = MBB->livein_begin(),
1531dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng         E = MBB->livein_end(); I != E; ++I)
1541dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng    if (Reg == *I || TRI->isSuperRegister(Reg, *I)) {
1551dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng      isLiveIn = true;
1561dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng      break;
1571dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng    }
1581dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng  if (!isLiveIn)
1591dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng    return false;
1601dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng
1611dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng  // Is there any use of it before the specified MI?
1621dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng  SmallPtrSet<MachineInstr*, 4> UsesInMBB;
1631dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng  for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(Reg),
1641dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng         UE = MRI->use_end(); UI != UE; ++UI) {
1651dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng    MachineInstr *UseMI = &*UI;
1661dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng    if (UseMI->getParent() == MBB)
1671dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng      UsesInMBB.insert(UseMI);
1681dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng  }
1691dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng  if (UsesInMBB.empty())
1701dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng    return true;
1711dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng
1721dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng  for (MachineBasicBlock::iterator I = MBB->begin(), E = MI; I != E; ++I)
1731dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng    if (UsesInMBB.count(&*I))
1741dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng      return false;
1751dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng  return true;
1761dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng}
1772755896fd048d189bedc5e99e776b3eca010dd4eDevang Patel#endif
1781dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng
17996fa612373e258120d351ed14361f964ad22f99dEvan Chengvoid RegScavenger::forward() {
180ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng  // Move ptr forward.
181898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng  if (!Tracking) {
182898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng    MBBI = MBB->begin();
183898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng    Tracking = true;
184898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng  } else {
185898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng    assert(MBBI != MBB->end() && "Already at the end of the basic block!");
186ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng    MBBI = next(MBBI);
187898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng  }
188ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng
18996fa612373e258120d351ed14361f964ad22f99dEvan Cheng  MachineInstr *MI = MBBI;
190d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng  DistanceMap.insert(std::make_pair(MI, CurrDist++));
191b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng
192d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng  if (MI == ScavengeRestore) {
193d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng    ScavengedReg = 0;
194d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng    ScavengedRC = NULL;
195d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng    ScavengeRestore = NULL;
196d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng  }
197b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng
1989c64bf3905ea338719800008c03d95a17cb26689Evan Cheng  bool IsImpDef = MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF;
1999c64bf3905ea338719800008c03d95a17cb26689Evan Cheng
2009c64bf3905ea338719800008c03d95a17cb26689Evan Cheng  // Separate register operands into 3 classes: uses, defs, earlyclobbers.
20163a431c6704e711713b0258bd987cfb257767cf4Evan Cheng  SmallVector<std::pair<const MachineOperand*,unsigned>, 4> UseMOs;
20263a431c6704e711713b0258bd987cfb257767cf4Evan Cheng  SmallVector<std::pair<const MachineOperand*,unsigned>, 4> DefMOs;
20363a431c6704e711713b0258bd987cfb257767cf4Evan Cheng  SmallVector<std::pair<const MachineOperand*,unsigned>, 4> EarlyClobberMOs;
20496fa612373e258120d351ed14361f964ad22f99dEvan Cheng  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
20596fa612373e258120d351ed14361f964ad22f99dEvan Cheng    const MachineOperand &MO = MI->getOperand(i);
2069c64bf3905ea338719800008c03d95a17cb26689Evan Cheng    if (!MO.isReg() || MO.getReg() == 0)
20796fa612373e258120d351ed14361f964ad22f99dEvan Cheng      continue;
2089c64bf3905ea338719800008c03d95a17cb26689Evan Cheng    if (MO.isUse())
20963a431c6704e711713b0258bd987cfb257767cf4Evan Cheng      UseMOs.push_back(std::make_pair(&MO,i));
2109c64bf3905ea338719800008c03d95a17cb26689Evan Cheng    else if (MO.isEarlyClobber())
21163a431c6704e711713b0258bd987cfb257767cf4Evan Cheng      EarlyClobberMOs.push_back(std::make_pair(&MO,i));
2129c64bf3905ea338719800008c03d95a17cb26689Evan Cheng    else
21363a431c6704e711713b0258bd987cfb257767cf4Evan Cheng      DefMOs.push_back(std::make_pair(&MO,i));
2149c64bf3905ea338719800008c03d95a17cb26689Evan Cheng  }
215a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling
2169c64bf3905ea338719800008c03d95a17cb26689Evan Cheng  // Process uses first.
2179c64bf3905ea338719800008c03d95a17cb26689Evan Cheng  BitVector UseRegs(NumPhysRegs);
2189c64bf3905ea338719800008c03d95a17cb26689Evan Cheng  for (unsigned i = 0, e = UseMOs.size(); i != e; ++i) {
21963a431c6704e711713b0258bd987cfb257767cf4Evan Cheng    const MachineOperand MO = *UseMOs[i].first;
22096fa612373e258120d351ed14361f964ad22f99dEvan Cheng    unsigned Reg = MO.getReg();
221a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling
222d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng    assert(isUsed(Reg) && "Using an undefined register!");
223a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling
224a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling    if (MO.isKill() && !isReserved(Reg)) {
2259c64bf3905ea338719800008c03d95a17cb26689Evan Cheng      UseRegs.set(Reg);
226a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling
2279c64bf3905ea338719800008c03d95a17cb26689Evan Cheng      // Mark sub-registers as used.
2286130f66eaae89f8878590796977678afa8448926Evan Cheng      for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
229a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling           unsigned SubReg = *SubRegs; ++SubRegs)
2309c64bf3905ea338719800008c03d95a17cb26689Evan Cheng        UseRegs.set(SubReg);
231a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling    }
23296fa612373e258120d351ed14361f964ad22f99dEvan Cheng  }
233a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling
23496fa612373e258120d351ed14361f964ad22f99dEvan Cheng  // Change states of all registers after all the uses are processed to guard
23596fa612373e258120d351ed14361f964ad22f99dEvan Cheng  // against multiple uses.
2369c64bf3905ea338719800008c03d95a17cb26689Evan Cheng  setUnused(UseRegs);
237a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling
2389c64bf3905ea338719800008c03d95a17cb26689Evan Cheng  // Process early clobber defs then process defs. We can have a early clobber
2399c64bf3905ea338719800008c03d95a17cb26689Evan Cheng  // that is dead, it should not conflict with a def that happens one "slot"
2409c64bf3905ea338719800008c03d95a17cb26689Evan Cheng  // (see InstrSlots in LiveIntervalAnalysis.h) later.
2419c64bf3905ea338719800008c03d95a17cb26689Evan Cheng  unsigned NumECs = EarlyClobberMOs.size();
2429c64bf3905ea338719800008c03d95a17cb26689Evan Cheng  unsigned NumDefs = DefMOs.size();
243a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling
2449c64bf3905ea338719800008c03d95a17cb26689Evan Cheng  for (unsigned i = 0, e = NumECs + NumDefs; i != e; ++i) {
2459c64bf3905ea338719800008c03d95a17cb26689Evan Cheng    const MachineOperand &MO = (i < NumECs)
24663a431c6704e711713b0258bd987cfb257767cf4Evan Cheng      ? *EarlyClobberMOs[i].first : *DefMOs[i-NumECs].first;
24763a431c6704e711713b0258bd987cfb257767cf4Evan Cheng    unsigned Idx = (i < NumECs)
24863a431c6704e711713b0258bd987cfb257767cf4Evan Cheng      ? EarlyClobberMOs[i].second : DefMOs[i-NumECs].second;
2490badfea274f9612780caccbad6e1870f39ed9f40Evan Cheng    unsigned Reg = MO.getReg();
250a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling
2515de3b7f35131b3c17e0b3c711d47ab3fb2c1e9beEvan Cheng    // If it's dead upon def, then it is now free.
2525de3b7f35131b3c17e0b3c711d47ab3fb2c1e9beEvan Cheng    if (MO.isDead()) {
253ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling      setUnused(Reg, MI);
2545de3b7f35131b3c17e0b3c711d47ab3fb2c1e9beEvan Cheng      continue;
2555de3b7f35131b3c17e0b3c711d47ab3fb2c1e9beEvan Cheng    }
256a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling
25796fa612373e258120d351ed14361f964ad22f99dEvan Cheng    // Skip two-address destination operand.
258d9df5017040489303acb57bdd8697ef0f8bafc08Bob Wilson    if (MI->isRegTiedToUseOperand(Idx)) {
2595db322acefc3089c133b8f3a33fa0a3ce90e2001Evan Cheng      assert(isUsed(Reg) && "Using an undefined register!");
26096fa612373e258120d351ed14361f964ad22f99dEvan Cheng      continue;
2610badfea274f9612780caccbad6e1870f39ed9f40Evan Cheng    }
262a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling
263d118342b25eb6a3a67792cda9fce9b4c1e45a867Dan Gohman    // Skip if this is merely redefining part of a super-register.
264ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling    if (RedefinesSuperRegPart(MI, MO, TRI))
265ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling      continue;
266ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling
2675d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng    // Implicit def is allowed to "re-define" any register. Similarly,
2685d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng    // implicitly defined registers can be clobbered.
2691dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng    assert((isReserved(Reg) || isUnused(Reg) ||
2705d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng            IsImpDef || isImplicitlyDefined(Reg) ||
2711dc7869025d91906e8305e921ddb82dac780d70eEvan Cheng            isLiveInButUnusedBefore(Reg, MI, MBB, TRI, MRI)) &&
2725db322acefc3089c133b8f3a33fa0a3ce90e2001Evan Cheng           "Re-defining a live register!");
2735d3600f5766e93cb459ef6108fba00c052aa6388Evan Cheng    setUsed(Reg, IsImpDef);
27496fa612373e258120d351ed14361f964ad22f99dEvan Cheng  }
27596fa612373e258120d351ed14361f964ad22f99dEvan Cheng}
27696fa612373e258120d351ed14361f964ad22f99dEvan Cheng
27796fa612373e258120d351ed14361f964ad22f99dEvan Chengvoid RegScavenger::backward() {
278898218cc5edecea1275ee266b2cd13313ea6b67bEvan Cheng  assert(Tracking && "Not tracking states!");
279ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng  assert(MBBI != MBB->begin() && "Already at start of basic block!");
280ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng  // Move ptr backward.
281ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng  MBBI = prior(MBBI);
282ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng
283ed570dedad945e1fe9a4bfeaa47276d875f1feedEvan Cheng  MachineInstr *MI = MBBI;
284d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng  DistanceMap.erase(MI);
285d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng  --CurrDist;
2863a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng
2873a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng  // Separate register operands into 3 classes: uses, defs, earlyclobbers.
2883a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng  SmallVector<std::pair<const MachineOperand*,unsigned>, 4> UseMOs;
2893a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng  SmallVector<std::pair<const MachineOperand*,unsigned>, 4> DefMOs;
2903a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng  SmallVector<std::pair<const MachineOperand*,unsigned>, 4> EarlyClobberMOs;
29196fa612373e258120d351ed14361f964ad22f99dEvan Cheng  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
29296fa612373e258120d351ed14361f964ad22f99dEvan Cheng    const MachineOperand &MO = MI->getOperand(i);
2933a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng    if (!MO.isReg() || MO.getReg() == 0)
29496fa612373e258120d351ed14361f964ad22f99dEvan Cheng      continue;
2953a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng    if (MO.isUse())
2963a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng      UseMOs.push_back(std::make_pair(&MO,i));
2973a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng    else if (MO.isEarlyClobber())
2983a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng      EarlyClobberMOs.push_back(std::make_pair(&MO,i));
2993a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng    else
3003a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng      DefMOs.push_back(std::make_pair(&MO,i));
3013a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng  }
3023a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng
3033a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng
3043a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng  // Process defs first.
3053a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng  unsigned NumECs = EarlyClobberMOs.size();
3063a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng  unsigned NumDefs = DefMOs.size();
3073a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng  for (unsigned i = 0, e = NumECs + NumDefs; i != e; ++i) {
3083a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng    const MachineOperand &MO = (i < NumDefs)
3093a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng      ? *DefMOs[i].first : *EarlyClobberMOs[i-NumDefs].first;
3103a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng    unsigned Idx = (i < NumECs)
3113a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng      ? DefMOs[i].second : EarlyClobberMOs[i-NumDefs].second;
3123a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng
31396fa612373e258120d351ed14361f964ad22f99dEvan Cheng    // Skip two-address destination operand.
314d9df5017040489303acb57bdd8697ef0f8bafc08Bob Wilson    if (MI->isRegTiedToUseOperand(Idx))
31596fa612373e258120d351ed14361f964ad22f99dEvan Cheng      continue;
3163a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng
31796fa612373e258120d351ed14361f964ad22f99dEvan Cheng    unsigned Reg = MO.getReg();
31896fa612373e258120d351ed14361f964ad22f99dEvan Cheng    assert(isUsed(Reg));
31996fa612373e258120d351ed14361f964ad22f99dEvan Cheng    if (!isReserved(Reg))
320ed1fcd8987a7d39ca69bfa3cbf14b270738f029cBill Wendling      setUnused(Reg, MI);
32196fa612373e258120d351ed14361f964ad22f99dEvan Cheng  }
32296fa612373e258120d351ed14361f964ad22f99dEvan Cheng
32396fa612373e258120d351ed14361f964ad22f99dEvan Cheng  // Process uses.
3249c64bf3905ea338719800008c03d95a17cb26689Evan Cheng  BitVector UseRegs(NumPhysRegs);
3253a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng  for (unsigned i = 0, e = UseMOs.size(); i != e; ++i) {
3263a5b020292408421e2605cb15a4741062f2c74b6Evan Cheng    const MachineOperand MO = *UseMOs[i].first;
32796fa612373e258120d351ed14361f964ad22f99dEvan Cheng    unsigned Reg = MO.getReg();
32896fa612373e258120d351ed14361f964ad22f99dEvan Cheng    assert(isUnused(Reg) || isReserved(Reg));
3299c64bf3905ea338719800008c03d95a17cb26689Evan Cheng    UseRegs.set(Reg);
330a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling
331a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling    // Set the sub-registers as "used".
3326130f66eaae89f8878590796977678afa8448926Evan Cheng    for (const unsigned *SubRegs = TRI->getSubRegisters(Reg);
333a0a570cec647b860a724f4f70a191bc83cdcc947Bill Wendling         unsigned SubReg = *SubRegs; ++SubRegs)
3349c64bf3905ea338719800008c03d95a17cb26689Evan Cheng      UseRegs.set(SubReg);
33596fa612373e258120d351ed14361f964ad22f99dEvan Cheng  }
3369c64bf3905ea338719800008c03d95a17cb26689Evan Cheng  setUsed(UseRegs);
33796fa612373e258120d351ed14361f964ad22f99dEvan Cheng}
33896fa612373e258120d351ed14361f964ad22f99dEvan Cheng
33969cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesenvoid RegScavenger::getRegsUsed(BitVector &used, bool includeReserved) {
34069cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen  if (includeReserved)
341c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen    used = ~RegsAvailable;
34269cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen  else
343c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen    used = ~RegsAvailable & ~ReservedRegs;
34469cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen}
34569cb9b78f11d505f4351a269fc90e7b77fcda437Dale Johannesen
34696fa612373e258120d351ed14361f964ad22f99dEvan Cheng/// CreateRegClassMask - Set the bits that represent the registers in the
34796fa612373e258120d351ed14361f964ad22f99dEvan Cheng/// TargetRegisterClass.
34896fa612373e258120d351ed14361f964ad22f99dEvan Chengstatic void CreateRegClassMask(const TargetRegisterClass *RC, BitVector &Mask) {
34996fa612373e258120d351ed14361f964ad22f99dEvan Cheng  for (TargetRegisterClass::iterator I = RC->begin(), E = RC->end(); I != E;
35096fa612373e258120d351ed14361f964ad22f99dEvan Cheng       ++I)
35196fa612373e258120d351ed14361f964ad22f99dEvan Cheng    Mask.set(*I);
35296fa612373e258120d351ed14361f964ad22f99dEvan Cheng}
35396fa612373e258120d351ed14361f964ad22f99dEvan Cheng
35496fa612373e258120d351ed14361f964ad22f99dEvan Chengunsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
3555196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng                                     const BitVector &Candidates) const {
3565196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng  // Mask off the registers which are not in the TargetRegisterClass.
357c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen  BitVector RegsAvailableCopy(NumPhysRegs, false);
358c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen  CreateRegClassMask(RegClass, RegsAvailableCopy);
359c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen  RegsAvailableCopy &= RegsAvailable;
3605196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng
3615196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng  // Restrict the search to candidates.
362c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen  RegsAvailableCopy &= Candidates;
3635196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng
3645196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng  // Returns the first unused (bit is set) register, or 0 is none is found.
365c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen  int Reg = RegsAvailableCopy.find_first();
3665196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng  return (Reg == -1) ? 0 : Reg;
3675196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng}
3685196b3680cf8df32b6c763e3d97e963e45150e5aEvan Cheng
3695196b3680cf8df32b6c763e3d97e963e45150e5aEvan Chengunsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RegClass,
37096fa612373e258120d351ed14361f964ad22f99dEvan Cheng                                     bool ExCalleeSaved) const {
37196fa612373e258120d351ed14361f964ad22f99dEvan Cheng  // Mask off the registers which are not in the TargetRegisterClass.
372c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen  BitVector RegsAvailableCopy(NumPhysRegs, false);
373c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen  CreateRegClassMask(RegClass, RegsAvailableCopy);
374c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen  RegsAvailableCopy &= RegsAvailable;
37596fa612373e258120d351ed14361f964ad22f99dEvan Cheng
37696fa612373e258120d351ed14361f964ad22f99dEvan Cheng  // If looking for a non-callee-saved register, mask off all the callee-saved
37796fa612373e258120d351ed14361f964ad22f99dEvan Cheng  // registers.
37896fa612373e258120d351ed14361f964ad22f99dEvan Cheng  if (ExCalleeSaved)
379c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen    RegsAvailableCopy &= ~CalleeSavedRegs;
38096fa612373e258120d351ed14361f964ad22f99dEvan Cheng
38196fa612373e258120d351ed14361f964ad22f99dEvan Cheng  // Returns the first unused (bit is set) register, or 0 is none is found.
382c6b9ef80a890fcf75f18cabc3fe2d5f9ef2faaf5Dale Johannesen  int Reg = RegsAvailableCopy.find_first();
38396fa612373e258120d351ed14361f964ad22f99dEvan Cheng  return (Reg == -1) ? 0 : Reg;
38496fa612373e258120d351ed14361f964ad22f99dEvan Cheng}
385b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng
386d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng/// findFirstUse - Calculate the distance to the first use of the
387b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng/// specified register.
388d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan ChengMachineInstr*
389d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan ChengRegScavenger::findFirstUse(MachineBasicBlock *MBB,
390d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng                           MachineBasicBlock::iterator I, unsigned Reg,
391d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng                           unsigned &Dist) {
392d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng  MachineInstr *UseMI = 0;
393d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng  Dist = ~0U;
394d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng  for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(Reg),
395d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng         RE = MRI->reg_end(); RI != RE; ++RI) {
396d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng    MachineInstr *UDMI = &*RI;
397d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng    if (UDMI->getParent() != MBB)
398d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng      continue;
399d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng    DenseMap<MachineInstr*, unsigned>::iterator DI = DistanceMap.find(UDMI);
400d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng    if (DI == DistanceMap.end()) {
401d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng      // If it's not in map, it's below current MI, let's initialize the
402d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng      // map.
403d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng      I = next(I);
404d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng      unsigned Dist = CurrDist + 1;
405d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng      while (I != MBB->end()) {
406d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng        DistanceMap.insert(std::make_pair(I, Dist++));
407d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng        I = next(I);
408d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng      }
409d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng    }
410d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng    DI = DistanceMap.find(UDMI);
411d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng    if (DI->second > CurrDist && DI->second < Dist) {
412d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng      Dist = DI->second;
413d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng      UseMI = UDMI;
414d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng    }
415b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng  }
416d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng  return UseMI;
417b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng}
418b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng
419b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Chengunsigned RegScavenger::scavengeRegister(const TargetRegisterClass *RC,
4208e3347332120956538a6d882b02719e34b57f0cdEvan Cheng                                        MachineBasicBlock::iterator I,
4218e3347332120956538a6d882b02719e34b57f0cdEvan Cheng                                        int SPAdj) {
422b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng  assert(ScavengingFrameIndex >= 0 &&
423b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng         "Cannot scavenge a register without an emergency spill slot!");
424b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng
425b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng  // Mask off the registers which are not in the TargetRegisterClass.
426b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng  BitVector Candidates(NumPhysRegs, false);
427b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng  CreateRegClassMask(RC, Candidates);
428b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng  Candidates ^= ReservedRegs;  // Do not include reserved registers.
429b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng
430b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng  // Exclude all the registers being used by the instruction.
431b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
432b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng    MachineOperand &MO = I->getOperand(i);
433d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman    if (MO.isReg())
434b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng      Candidates.reset(MO.getReg());
435b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng  }
436b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng
437527c250a9080a5b6cf0053a6215037c3769ff4a0Bill Wendling  // Find the register whose use is furthest away.
438b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng  unsigned SReg = 0;
439b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng  unsigned MaxDist = 0;
440d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng  MachineInstr *MaxUseMI = 0;
441b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng  int Reg = Candidates.find_first();
442b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng  while (Reg != -1) {
443d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng    unsigned Dist;
444d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng    MachineInstr *UseMI = findFirstUse(MBB, I, Reg, Dist);
445d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng    for (const unsigned *AS = TRI->getAliasSet(Reg); *AS; ++AS) {
446d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng      unsigned AsDist;
447d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng      MachineInstr *AsUseMI = findFirstUse(MBB, I, *AS, AsDist);
448d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng      if (AsDist < Dist) {
449d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng        Dist = AsDist;
450d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng        UseMI = AsUseMI;
451d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng      }
452d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng    }
453b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng    if (Dist >= MaxDist) {
454b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng      MaxDist = Dist;
455d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng      MaxUseMI = UseMI;
456b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng      SReg = Reg;
457b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng    }
458b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng    Reg = Candidates.find_next(Reg);
459b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng  }
460b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng
461b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng  if (ScavengedReg != 0) {
462d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng    assert(0 && "Scavenger slot is live, unable to scavenge another register!");
463d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng    abort();
464b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng  }
465b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng
466d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng  // Spill the scavenged register before I.
467f6372aa1cc568df19da7c5023e83c75aa9404a07Owen Anderson  TII->storeRegToStackSlot(*MBB, I, SReg, true, ScavengingFrameIndex, RC);
468b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng  MachineBasicBlock::iterator II = prior(I);
4696130f66eaae89f8878590796977678afa8448926Evan Cheng  TRI->eliminateFrameIndex(II, SPAdj, this);
470d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng
471d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng  // Restore the scavenged register before its use (or first terminator).
472d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng  II = MaxUseMI
473d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng    ? MachineBasicBlock::iterator(MaxUseMI) : MBB->getFirstTerminator();
474d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng  TII->loadRegFromStackSlot(*MBB, II, SReg, ScavengingFrameIndex, RC);
475d37c13cfd1bf4b08d0b99d93c799a1caa74cf3c6Evan Cheng  ScavengeRestore = prior(II);
476b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng  ScavengedReg = SReg;
477b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng  ScavengedRC = RC;
478b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng
479b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng  return SReg;
480b74a3e6fda768eb6160559e025f8b65c46db46d9Evan Cheng}
481