AArch64: Replace a RegScavenger instance with LivePhysRegs

[MatzeB]

Summary

findScratchNonCalleeSaveRegister() just needs a simple liveness
analysis, use LivePhysRegs for that as it is simpler and does not depend
on the kill flags. This is part of an initiative to rely less on kill flags.

This commit adds a convenience function available() to LivePhysRegs:
This function returns true if the given register is not reserved and
neither the register nor any of its aliases are alive.

[t.p.northover]

This looks good to me.

Tim.

include/llvm/CodeGen/LivePhysRegs.h

for (MCRegAliasIterator R(Reg, TRI, true); R.isValid(); ++R)
       LiveRegs.erase(*R);
   }
 
   /// \brief Removes physical registers clobbered by the regmask operand @p MO.
   void removeRegsInMask(const MachineOperand &MO,
         SmallVectorImpl<std::pair<unsigned, const MachineOperand*>> *Clobbers);
 
   /// \brief Returns true if register @p Reg is contained in the set. This also
-  /// works if only the super register of @p Reg has been defined, because we
-  /// always add also all sub-registers to the set.
+  /// works if only the super register of @p Reg has been defined, because
+  /// addReg() always adds all sub-registers to the set as well.
+  /// Note: Returns false if just some sub registers are live, use available()
+  /// when searching a free register.
   bool contains(unsigned Reg) const { return LiveRegs.count(Reg); }
 
+  /// Returns true if register \p Reg and no aliasing register is in the set.
+  bool available(const MachineRegisterInfo &MRI, unsigned Reg) const;
+
   /// \brief Simulates liveness when stepping backwards over an
   /// instruction(bundle): Remove Defs, add uses. This is the recommended way of
   /// calculating liveness.
   void stepBackward(const MachineInstr &MI);
 
   /// \brief Simulates liveness when stepping forward over an
   /// instruction(bundle): Remove killed-uses, add defs. This is the not
   /// recommended way, because it depends on accurate kill flags. If possible

lib/CodeGen/LivePhysRegs.cpp

 // A more detailed description can be found in the corresponding header file.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/LivePhysRegs.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstrBundle.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 using namespace llvm;
 
 
 /// \brief Remove all registers from the set that get clobbered by the register
 /// mask.
 /// The clobbers set will be the list of live registers clobbered

 
 /// Dumps the currently live registers to the debug output.
 LLVM_DUMP_METHOD void LivePhysRegs::dump() const {
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   dbgs() << "  " << *this;
 #endif
 }
 
+bool LivePhysRegs::available(const MachineRegisterInfo &MRI,
+                             unsigned Reg) const {
+  if (LiveRegs.count(Reg))
+    return false;
+  if (MRI.isReserved(Reg))
+    return false;
+  for (MCRegAliasIterator R(Reg, TRI, false); R.isValid(); ++R) {
+    if (LiveRegs.count(*R))
+      return false;
+  }
+  return true;
+}
+
 /// Add live-in registers of basic block \p MBB to \p LiveRegs.
 static void addLiveIns(LivePhysRegs &LiveRegs, const MachineBasicBlock &MBB) {
   for (const auto &LI : MBB.liveins())
     LiveRegs.addReg(LI.PhysReg);
 }
 
 /// Add pristine registers to the given \p LiveRegs. This function removes
 /// actually saved callee save registers when \p InPrologueEpilogue is false.

lib/Target/AArch64/AArch64FrameLowering.cpp

 //===----------------------------------------------------------------------===//
 
 #include "AArch64FrameLowering.h"
 #include "AArch64InstrInfo.h"
 #include "AArch64MachineFunctionInfo.h"
 #include "AArch64Subtarget.h"
 #include "AArch64TargetMachine.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/CodeGen/LivePhysRegs.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/RegisterScavenging.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Function.h"

 // doesn't seem worth the benefit.
 static unsigned findScratchNonCalleeSaveRegister(MachineBasicBlock *MBB) {
   MachineFunction *MF = MBB->getParent();
 
   // If MBB is an entry block, use X9 as the scratch register
   if (&MF->front() == MBB)
     return AArch64::X9;
 
-  RegScavenger RS;
-  RS.enterBasicBlock(*MBB);
+  const TargetRegisterInfo &TRI = *MF->getSubtarget().getRegisterInfo();
+  LivePhysRegs LiveRegs(&TRI);
+  LiveRegs.addLiveIns(*MBB);
 
-  // Prefer X9 since it was historically used for the prologue scratch reg.
-  if (!RS.isRegUsed(AArch64::X9))
-    return AArch64::X9;
-
-  // Find a free non callee-save reg.
+  // Mark callee saved registers as used so we will not choose them.
   const AArch64Subtarget &Subtarget = MF->getSubtarget<AArch64Subtarget>();
   const AArch64RegisterInfo *RegInfo = Subtarget.getRegisterInfo();
   const MCPhysReg *CSRegs = RegInfo->getCalleeSavedRegs(MF);
-  BitVector CalleeSaveRegs(RegInfo->getNumRegs());
   for (unsigned i = 0; CSRegs[i]; ++i)
-    CalleeSaveRegs.set(CSRegs[i]);
+    LiveRegs.addReg(CSRegs[i]);
 
-  BitVector Available = RS.getRegsAvailable(&AArch64::GPR64RegClass);
-  for (int AvailReg = Available.find_first(); AvailReg != -1;
-       AvailReg = Available.find_next(AvailReg))
-    if (!CalleeSaveRegs.test(AvailReg))
-      return AvailReg;
+  // Prefer X9 since it was historically used for the prologue scratch reg.
+  const MachineRegisterInfo &MRI = MF->getRegInfo();
+  if (LiveRegs.available(MRI, AArch64::X9))
+    return AArch64::X9;
 
+  for (unsigned Reg : AArch64::GPR64RegClass) {
+    if (LiveRegs.available(MRI, Reg))
+      return Reg;
+  }
   return AArch64::NoRegister;
 }
 
 bool AArch64FrameLowering::canUseAsPrologue(
     const MachineBasicBlock &MBB) const {
   const MachineFunction *MF = MBB.getParent();
   MachineBasicBlock *TmpMBB = const_cast<MachineBasicBlock *>(&MBB);
   const AArch64Subtarget &Subtarget = MF->getSubtarget<AArch64Subtarget>();