Add LiveRegUnits class.

[MatzeB]

Summary

This is a set of register units intended to track register liveness, it
is similar in spirit to LivePhysRegs.
You can also think of this as the liveness tracking parts of the
RegisterScavenger factored out into an own class.

This was proposed in http://llvm.org/PR27609

• Many of the current LivePhysRegs uses can be replaced by this (I will do that in upcoming patches). This patch only switches the internal RegisterScavenger state to show the concept. Using LiveRegUnits should be slightly more efficient than LivePhysRegs.
• It cannot completely LivePhysRegs right now, because some cases like %xmm0 vs. %ymm0 on x86 have the exact same register units but need to be differntiated for ABI reasons. (We may be able to introduce additional register units for this in another patch).
• I decided not to add forward walking support as that only works reliably with kill flags which are intended to be remove long term.
• This patch applies on top of http://reviews.llvm.org/D21885 but it shouldn't be too hard to rebase if

[MatzeB]

ping

[qcolombet]

Hi Matthias,

LGTM modulo nitpicks on the name of the regmask method.

Cheers,
-Quentin

include/llvm/CodeGen/LiveRegUnits.h

77

Maybe rename the method into removeRegsNotPreservedByMask because unless we read the comment each time we see an instance of that call, I believe we would infer that it does the opposite.

95

I am not sure I am happy adding the pristine register at this point. I understand why we need that, but my concern is that the name of does not convey (again without looking at the comments) that the pristine are added. Anyhow, that is consistent with LivePhysReg so fine, however, we should have a variant without the pristine.

Perhaps you wanted to add it only when we need it… and I can live with that.
The bottom line is that you can ignore that comment :P.

[MatzeB]

include/llvm/CodeGen/LiveRegUnits.h

95

Most users want the variant with the pristine registers (esp. the ones that do not know what pristine registers are), so I think it is warranted to use the simple name for this. Of course we should add the variant without pristine registers as soon as we need it.

[MatzeB]

In the interest of not having this lying around uncommitted for much longer, I am committing this without the RegisterScavenging parts (the RegisterScavenging rewrite this was based on caused build failures).

include/llvm/CodeGen/LiveRegUnits.h

+//===- llvm/CodeGen/LiveRegUnits.h - Register Unit Set ----------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file
+/// A set of register units. It is intended for register liveness tracking.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_LIVEREGUNITS_H
+#define LLVM_CODEGEN_LIVEREGUNITS_H
+
+#include "llvm/ADT/BitVector.h"
+#include "llvm/Target/TargetRegisterInfo.h"
+
+namespace llvm {
+
+class MachineInstr;
+class MachineBasicBlock;
+
+/// A set of register units used to track register liveness.
+class LiveRegUnits {
+  const TargetRegisterInfo *TRI;
+  BitVector Units;
+
+public:
+  /// Constructs a new empty LiveRegUnits set.
+  LiveRegUnits() : TRI(nullptr) {}
+
+  /// Constructs and initialize an empty LiveRegUnits set.
+  LiveRegUnits(const TargetRegisterInfo *TRI) {
+    init(TRI);
+  }
+
+  /// Initialize and clear the set.
+  void init(const TargetRegisterInfo *TRI) {
+    this->TRI = TRI;
+    Units.reset();
+    Units.resize(TRI->getNumRegUnits());
+  }
+
+  /// Clears the set.
+  void clear() { Units.reset(); }
+
+  /// Returns true if the set is empty.
+  bool empty() const { return Units.empty(); }
+
+  /// Adds register units covered by physical register \p Reg.
+  void addReg(unsigned Reg) {
+    for (MCRegUnitIterator Unit(Reg, TRI); Unit.isValid(); ++Unit)
+      Units.set(*Unit);
+  }
+
+  /// \brief Adds register units covered by physical register \p Reg that are
+  /// part of the lanemask \p Mask.
+  void addRegMasked(unsigned Reg, LaneBitmask Mask) {
+    for (MCRegUnitMaskIterator Unit(Reg, TRI); Unit.isValid(); ++Unit) {
+      LaneBitmask UnitMask = (*Unit).second;
+      if (UnitMask == 0 || (UnitMask & Mask) != 0)
+        Units.set((*Unit).first);
+    }
+  }
+
+  /// Removes all register units covered by physical register \p Reg.
+  void removeReg(unsigned Reg) {
+    for (MCRegUnitIterator Unit(Reg, TRI); Unit.isValid(); ++Unit)
+      Units.reset(*Unit);
+  }
+
+  /// Removes register units not preserved by the regmask \p RegMask.
+  /// The regmask has the same format as the one in the RegMask machine operand.
+  void removeRegsInMask(const uint32_t *RegMask);
+
+  /// Returns true if no part of physical register \p Reg is live.
+  bool available(unsigned Reg) const {
+    for (MCRegUnitIterator Unit(Reg, TRI); Unit.isValid(); ++Unit) {
+      if (Units.test(*Unit))
+        return false;
+    }
+    return true;
+  }
+
+  /// Updates liveness when stepping backwards over the instruction \p MI.
+  void stepBackward(const MachineInstr &MI);
+
+  /// Adds registers living out of block \p MBB.
+  /// Live out registers are the union of the live-in registers of the successor
+  /// blocks and pristine registers. Live out registers of the end block are the
+  /// callee saved registers.
+  void addLiveOuts(const MachineBasicBlock &MBB);
+
+  /// Adds registers living into block \p MBB.
+  void addLiveIns(const MachineBasicBlock &MBB);
+
+  /// Adds all register units marked in the bitvector \p RegUnits.
+  void addUnits(const BitVector &RegUnits) {
+    Units |= RegUnits;
+  }
+  /// Removes all register units marked in the bitvector \p RegUnits.
+  void removeUnits(const BitVector &RegUnits) {
+    Units.reset(RegUnits);
+  }
+};
+
+} // namespace llvm
+
+#endif

include/llvm/CodeGen/RegisterScavenging.h

 /// to spill slots.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CODEGEN_REGISTERSCAVENGING_H
 #define LLVM_CODEGEN_REGISTERSCAVENGING_H
 
 #include "llvm/ADT/BitVector.h"
+#include "llvm/CodeGen/LiveRegUnits.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 
 namespace llvm {
 
 class MachineRegisterInfo;
 class TargetRegisterInfo;
 class TargetInstrInfo;
struct ScavengedInfo {
 
     /// The instruction that restores the scavenged register from stack.
     const MachineInstr *Restore;
   };
 
   /// A vector of information on scavenged registers.
   SmallVector<ScavengedInfo, 2> Scavenged;
 
-  /// The current state of each reg unit immediately before MBBI.
-  /// One bit per register unit. If bit is not set it means any
-  /// register containing that register unit is currently being used.
-  BitVector RegUnitsAvailable;
+  LiveRegUnits LiveUnits;
 
   // These BitVectors are only used internally to forward(). They are members
   // to avoid frequent reallocations.
   BitVector KillRegUnits, DefRegUnits;
   BitVector TmpRegUnits;
 
 public:
   RegScavenger()
public:
   /// Tell the scavenger a register is used.
   void setRegUsed(unsigned Reg, LaneBitmask LaneMask = ~0u);
 private:
   /// Returns true if a register is reserved. It is never "unused".
   bool isReserved(unsigned Reg) const { return MRI->isReserved(Reg); }
 
   /// setUsed / setUnused - Mark the state of one or a number of register units.
   ///
-  void setUsed(BitVector &RegUnits) {
-    RegUnitsAvailable.reset(RegUnits);
+  void setUsed(const BitVector &RegUnits) {
+    LiveUnits.addUnits(RegUnits);
   }
-  void setUnused(BitVector &RegUnits) {
-    RegUnitsAvailable |= RegUnits;
+  void setUnused(const BitVector &RegUnits) {
+    LiveUnits.removeUnits(RegUnits);
   }
 
   /// Processes the current instruction and fill the KillRegUnits and
   /// DefRegUnits bit vectors.
   void determineKillsAndDefs();
 
   /// Add all Reg Units that Reg contains to BV.
   void addRegUnits(BitVector &BV, unsigned Reg);

lib/CodeGen/CMakeLists.txt

add_llvm_library(LLVMCodeGen
   LiveDebugVariables.cpp
   LiveIntervalAnalysis.cpp
   LiveInterval.cpp
   LiveIntervalUnion.cpp
   LivePhysRegs.cpp
   LiveRangeCalc.cpp
   LiveRangeEdit.cpp
   LiveRegMatrix.cpp
+  LiveRegUnits.cpp
   LiveStackAnalysis.cpp
   LiveVariables.cpp
   LLVMTargetMachine.cpp
   LocalStackSlotAllocation.cpp
   LowerEmuTLS.cpp
   MachineBasicBlock.cpp
   MachineBlockFrequencyInfo.cpp
   MachineBlockPlacement.cpp

lib/CodeGen/LiveRegUnits.cpp

+//===--- LiveRegUnits.cpp - Register Unit Set -----------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+/// \file This file imlements the LiveRegUnits set.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/CodeGen/LiveRegUnits.h"
+#include "llvm/CodeGen/MachineFrameInfo.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineInstrBundle.h"
+using namespace llvm;
+
+void LiveRegUnits::removeRegsInMask(const uint32_t *RegMask) {
+  for (unsigned U = 0, E = TRI->getNumRegUnits(); U != E; ++U) {
+    for (MCRegUnitRootIterator RootReg(U, TRI); RootReg.isValid(); ++RootReg) {
+      if (MachineOperand::clobbersPhysReg(RegMask, *RootReg))
+        Units.reset(U);
+    }
+  }
+}
+
+void LiveRegUnits::stepBackward(const MachineInstr &MI) {
+  // Remove defined registers and regmask kills from the set.
+  for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
+    if (O->isReg()) {
+      if (!O->isDef())
+        continue;
+      unsigned Reg = O->getReg();
+      if (!TargetRegisterInfo::isPhysicalRegister(Reg))
+        continue;
+      removeReg(Reg);
+    } else if (O->isRegMask())
+      removeRegsInMask(O->getRegMask());
+  }
+
+  // Add uses to the set.
+  for (ConstMIBundleOperands O(MI); O.isValid(); ++O) {
+    if (!O->isReg() || !O->readsReg())
+      continue;
+    unsigned Reg = O->getReg();
+    if (!TargetRegisterInfo::isPhysicalRegister(Reg))
+      continue;
+    addReg(Reg);
+  }
+}
+
+/// Add live-in registers of basic block \p MBB to \p LiveUnits.
+static void addLiveIns(LiveRegUnits &LiveUnits, const MachineBasicBlock &MBB) {
+  for (const auto &LI : MBB.liveins())
+    LiveUnits.addRegMasked(LI.PhysReg, LI.LaneMask);
+}
+
+static void addLiveOuts(LiveRegUnits &LiveUnits, const MachineBasicBlock &MBB) {
+  // To get the live-outs we simply merge the live-ins of all successors.
+  for (const MachineBasicBlock *Succ : MBB.successors())
+    addLiveIns(LiveUnits, *Succ);
+}
+
+/// Add pristine registers to the given \p LiveUnits. This function removes
+/// actually saved callee save registers when \p InPrologueEpilogue is false.
+static void removeSavedRegs(LiveRegUnits &LiveUnits, const MachineFunction &MF,
+                            const MachineFrameInfo &MFI,
+                            const TargetRegisterInfo &TRI) {
+  for (const CalleeSavedInfo &Info : MFI.getCalleeSavedInfo())
+    LiveUnits.removeReg(Info.getReg());
+}
+
+void LiveRegUnits::addLiveOuts(const MachineBasicBlock &MBB) {
+  const MachineFunction &MF = *MBB.getParent();
+  const MachineFrameInfo &MFI = *MF.getFrameInfo();
+  if (MFI.isCalleeSavedInfoValid()) {
+    for (const MCPhysReg *I = TRI->getCalleeSavedRegs(&MF); *I; ++I)
+      addReg(*I);
+    if (!MBB.isReturnBlock())
+      removeSavedRegs(*this, MF, MFI, *TRI);
+  }
+  ::addLiveOuts(*this, MBB);
+}
+
+void LiveRegUnits::addLiveIns(const MachineBasicBlock &MBB) {
+  const MachineFunction &MF = *MBB.getParent();
+  const MachineFrameInfo &MFI = *MF.getFrameInfo();
+  if (MFI.isCalleeSavedInfoValid()) {
+    for (const MCPhysReg *I = TRI->getCalleeSavedRegs(&MF); *I; ++I)
+      addReg(*I);
+    if (&MBB != &MF.front())
+      removeSavedRegs(*this, MF, MFI, *TRI);
+  }
+  ::addLiveIns(*this, MBB);
+}

lib/CodeGen/RegisterScavenging.cpp

 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "reg-scavenging"
 
 void RegScavenger::setRegUsed(unsigned Reg, LaneBitmask LaneMask) {
-  for (MCRegUnitMaskIterator RUI(Reg, TRI); RUI.isValid(); ++RUI) {
-    LaneBitmask UnitMask = (*RUI).second;
-    if (UnitMask == 0 || (LaneMask & UnitMask) != 0)
-      RegUnitsAvailable.reset((*RUI).first);
-  }
+  LiveUnits.addRegMasked(Reg, LaneMask);
 }
 
 void RegScavenger::init(MachineBasicBlock &MBB) {
   MachineFunction &MF = *MBB.getParent();
   TII = MF.getSubtarget().getInstrInfo();
   TRI = MF.getSubtarget().getRegisterInfo();
   MRI = &MF.getRegInfo();
+  LiveUnits.init(TRI);
 
   assert((NumRegUnits == 0 || NumRegUnits == TRI->getNumRegUnits()) &&
          "Target changed?");
 
   // It is not possible to use the register scavenger after late optimization
   // passes that don't preserve accurate liveness information.
   assert(MRI->tracksLiveness() &&
          "Cannot use register scavenger with inaccurate liveness");
 
   // Self-initialize.
   if (!this->MBB) {
     NumRegUnits = TRI->getNumRegUnits();
-    RegUnitsAvailable.resize(NumRegUnits);
     KillRegUnits.resize(NumRegUnits);
     DefRegUnits.resize(NumRegUnits);
     TmpRegUnits.resize(NumRegUnits);
   }
   this->MBB = &MBB;
 
   for (SmallVectorImpl<ScavengedInfo>::iterator I = Scavenged.begin(),
          IE = Scavenged.end(); I != IE; ++I) {
     I->Reg = 0;
     I->Restore = nullptr;
   }
 
-  // All register units start out unused.
-  RegUnitsAvailable.set();
-
-  // Pristine CSRs are not available.
-  BitVector PR = MF.getFrameInfo()->getPristineRegs(MF);
-  for (int I = PR.find_first(); I>0; I = PR.find_next(I))
-    setRegUsed(I);
-
   Tracking = false;
 }
 
-void RegScavenger::setLiveInsUsed(const MachineBasicBlock &MBB) {
-  for (const auto &LI : MBB.liveins())
-    setRegUsed(LI.PhysReg, LI.LaneMask);
-}
-
 void RegScavenger::enterBasicBlock(MachineBasicBlock &MBB) {
   init(MBB);
-  setLiveInsUsed(MBB);
+  LiveUnits.addLiveIns(MBB);
 }
 
 void RegScavenger::enterBasicBlockEnd(MachineBasicBlock &MBB) {
   init(MBB);
-  // Merge live-ins of successors to get live-outs.
-  for (const MachineBasicBlock *Succ : MBB.successors())
-    setLiveInsUsed(*Succ);
+  LiveUnits.addLiveOuts(MBB);
 
   // Move internal iterator at the last instruction of the block.
   if (MBB.begin() != MBB.end()) {
     MBBI = std::prev(MBB.end());
     Tracking = true;
   }
 }
 
#endif // NDEBUG
   setUnused(KillRegUnits);
   setUsed(DefRegUnits);
 }
 
 void RegScavenger::backward() {
   assert(Tracking && "Must be tracking to determine kills and defs");
 
   const MachineInstr &MI = *MBBI;
-  // Defined or clobbered registers are available now.
-  for (const MachineOperand &MO : MI.operands()) {
-    if (MO.isRegMask()) {
-      for (unsigned RU = 0, RUEnd = TRI->getNumRegUnits(); RU != RUEnd;
-           ++RU) {
-        for (MCRegUnitRootIterator RURI(RU, TRI); RURI.isValid(); ++RURI) {
-          if (MO.clobbersPhysReg(*RURI)) {
-            RegUnitsAvailable.set(RU);
-            break;
-          }
-        }
-      }
-    } else if (MO.isReg() && MO.isDef()) {
-      unsigned Reg = MO.getReg();
-      if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) ||
-          isReserved(Reg))
-        continue;
-      addRegUnits(RegUnitsAvailable, Reg);
-    }
-  }
-  // Mark read registers as unavailable.
-  for (const MachineOperand &MO : MI.uses()) {
-    if (MO.isReg() && MO.readsReg()) {
-      unsigned Reg = MO.getReg();
-      if (!Reg || TargetRegisterInfo::isVirtualRegister(Reg) ||
-          isReserved(Reg))
-        continue;
-      removeRegUnits(RegUnitsAvailable, Reg);
-    }
-  }
+  LiveUnits.stepBackward(MI);
 
   // Expire scavenge spill frameindex uses.
   for (ScavengedInfo &I : Scavenged) {
     if (I.Restore == &MI) {
       I.Reg = 0;
       I.Restore = nullptr;
     }
   }
 
   if (MBBI == MBB->begin()) {
     MBBI = MachineBasicBlock::iterator(nullptr);
     Tracking = false;
   } else
     --MBBI;
 }
 
 bool RegScavenger::isRegUsed(unsigned Reg, bool includeReserved) const {
-  if (includeReserved && isReserved(Reg))
-    return true;
-  for (MCRegUnitIterator RUI(Reg, TRI); RUI.isValid(); ++RUI)
-    if (!RegUnitsAvailable.test(*RUI))
-      return true;
-  return false;
+  if (isReserved(Reg))
+    return includeReserved;
+  return !LiveUnits.available(Reg);
 }
 
 unsigned RegScavenger::FindUnusedReg(const TargetRegisterClass *RC) const {
   for (unsigned Reg : *RC) {
     if (!isRegUsed(Reg)) {
       DEBUG(dbgs() << "Scavenger found unused reg: " << TRI->getName(Reg) <<
             "\n");
       return Reg;
unsigned RegScavenger::scavengeRegisterBackwards(const TargetRegisterClass &RC,
   assert(Reg != 0 && "No register left to scavenge!");
   // Found an available register?
   if (!Available.test(Reg)) {
     MachineBasicBlock::iterator ReloadBefore =
       RestoreAfter ? std::next(MBBI) : MBBI;
     DEBUG(dbgs() << "Reload before: " << *ReloadBefore << '\n');
     ScavengedInfo &Scavenged = spill(Reg, &RC, SPAdj, P.second, ReloadBefore);
     Scavenged.Restore = std::prev(P.second);
-    addRegUnits(RegUnitsAvailable, Reg);
+    LiveUnits.removeReg(Reg);
     DEBUG(dbgs() << "Scavenged register with spill: " << PrintReg(Reg, TRI)
           << " until " << *P.second);
   } else {
     DEBUG(dbgs() << "Scavenged free register: " << PrintReg(Reg, TRI) << '\n');
   }
   return Reg;
 }