[NFC][regalloc] Unit test for AllocationOrder iteration.

[mtrofin]

Summary

Added unittests. In the process, separated core construction - which just
needs the hits, order, and 'HardHints' values - from construction from
current register allocation state, to simplify testing.

[qcolombet]

Hi @mtrofin,

Thanks for doing this.

LGTM with one comment.

Cheers,
-Quentin

llvm/lib/CodeGen/AllocationOrder.h

46

What's the rationale for turning this constructor into a static method?

llvm/unittests/CodeGen/AllocationOrderTest.cpp

115

Please add a new line.

[mtrofin]

newline

llvm/lib/CodeGen/AllocationOrder.h

46

This allows the members of AllocationOrder to be const-ed (ArrayRef has read-only semantics, so that's the exception). This, imho, simplifies readability - one doesn't need to worry about mutation when glancing at this code.

llvm/lib/CodeGen/AllocationOrder.h

 
 namespace llvm {
 
 class RegisterClassInfo;
 class VirtRegMap;
 class LiveRegMatrix;
 
 class LLVM_LIBRARY_VISIBILITY AllocationOrder {
-  SmallVector<MCPhysReg, 16> Hints;
+  const SmallVector<MCPhysReg, 16> Hints;
   ArrayRef<MCPhysReg> Order;
-  int Pos;
+  int Pos = 0;
 
   // If HardHints is true, *only* Hints will be returned.
-  bool HardHints;
+  const bool HardHints;
 
 public:
 
   /// Create a new AllocationOrder for VirtReg.
   /// @param VirtReg      Virtual register to allocate for.
   /// @param VRM          Virtual register map for function.
   /// @param RegClassInfo Information about reserved and allocatable registers.
-  AllocationOrder(unsigned VirtReg,
-                  const VirtRegMap &VRM,
+  static AllocationOrder create(unsigned VirtReg, const VirtRegMap &VRM,
                                 const RegisterClassInfo &RegClassInfo,
                                 const LiveRegMatrix *Matrix);
 
+  /// Create an AllocationOrder given the Hits, Order, and HardHits values.
+  /// Use the create method above - the ctor is for unittests.
+  AllocationOrder(SmallVector<MCPhysReg, 16> &&Hints, ArrayRef<MCPhysReg> Order,
+                  bool HardHints)
+      : Hints(std::move(Hints)), Order(Order),
+        Pos(-static_cast<int>(this->Hints.size())), HardHints(HardHints) {}
+
   /// Get the allocation order without reordered hints.
   ArrayRef<MCPhysReg> getOrder() const { return Order; }
 
   /// Return the next physical register in the allocation order, or 0.
   /// It is safe to call next() again after it returned 0, it will keep
   /// returning 0 until rewind() is called.
-  unsigned next(unsigned Limit = 0) {
+  MCPhysReg next(unsigned Limit = 0) {
     if (Pos < 0)
       return Hints.end()[Pos++];
     if (HardHints)
       return 0;
     if (!Limit)
       Limit = Order.size();
     while (Pos < int(Limit)) {
       unsigned Reg = Order[Pos++];

llvm/lib/CodeGen/AllocationOrder.cpp

 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "regalloc"
 
 // Compare VirtRegMap::getRegAllocPref().
-AllocationOrder::AllocationOrder(unsigned VirtReg,
-                                 const VirtRegMap &VRM,
+AllocationOrder AllocationOrder::create(unsigned VirtReg, const VirtRegMap &VRM,
                                         const RegisterClassInfo &RegClassInfo,
-                                 const LiveRegMatrix *Matrix)
-  : Pos(0), HardHints(false) {
+                                        const LiveRegMatrix *Matrix) {
   const MachineFunction &MF = VRM.getMachineFunction();
   const TargetRegisterInfo *TRI = &VRM.getTargetRegInfo();
-  Order = RegClassInfo.getOrder(MF.getRegInfo().getRegClass(VirtReg));
-  if (TRI->getRegAllocationHints(VirtReg, Order, Hints, MF, &VRM, Matrix))
-    HardHints = true;
-  rewind();
+  auto Order = RegClassInfo.getOrder(MF.getRegInfo().getRegClass(VirtReg));
+  SmallVector<MCPhysReg, 16> Hints;
+  bool HardHints =
+      TRI->getRegAllocationHints(VirtReg, Order, Hints, MF, &VRM, Matrix);
 
   LLVM_DEBUG({
     if (!Hints.empty()) {
       dbgs() << "hints:";
       for (unsigned I = 0, E = Hints.size(); I != E; ++I)
         dbgs() << ' ' << printReg(Hints[I], TRI);
       dbgs() << '\n';
     }
   });
 #ifndef NDEBUG
   for (unsigned I = 0, E = Hints.size(); I != E; ++I)
     assert(is_contained(Order, Hints[I]) &&
            "Target hint is outside allocation order.");
 #endif
+  return AllocationOrder(std::move(Hints), Order, HardHints);
 }

llvm/lib/CodeGen/RegAllocBasic.cpp

 // minimal, there is no value in caching them outside the scope of
 // selectOrSplit().
 Register RABasic::selectOrSplit(LiveInterval &VirtReg,
                                 SmallVectorImpl<Register> &SplitVRegs) {
   // Populate a list of physical register spill candidates.
   SmallVector<Register, 8> PhysRegSpillCands;
 
   // Check for an available register in this class.
-  AllocationOrder Order(VirtReg.reg(), *VRM, RegClassInfo, Matrix);
+  auto Order =
+      AllocationOrder::create(VirtReg.reg(), *VRM, RegClassInfo, Matrix);
   while (Register PhysReg = Order.next()) {
     // Check for interference in PhysReg
     switch (Matrix->checkInterference(VirtReg, PhysReg)) {
     case LiveRegMatrix::IK_Free:
       // PhysReg is available, allocate it.
       return PhysReg;
 
     case LiveRegMatrix::IK_VirtReg:

llvm/lib/CodeGen/RegAllocGreedy.cpp

Register RAGreedy::tryAssign(LiveInterval &VirtReg,
   return CheapReg ? CheapReg : PhysReg;
 }
 
 //===----------------------------------------------------------------------===//
 //                         Interference eviction
 //===----------------------------------------------------------------------===//
 
 Register RAGreedy::canReassign(LiveInterval &VirtReg, Register PrevReg) {
-  AllocationOrder Order(VirtReg.reg(), *VRM, RegClassInfo, Matrix);
+  auto Order =
+      AllocationOrder::create(VirtReg.reg(), *VRM, RegClassInfo, Matrix);
   Register PhysReg;
   while ((PhysReg = Order.next())) {
     if (PhysReg == PrevReg)
       continue;
 
     MCRegUnitIterator Units(PhysReg, TRI);
     for (; Units.isValid(); ++Units) {
       // Instantiate a "subquery", not to be confused with the Queries array.

 }
 
 Register RAGreedy::selectOrSplitImpl(LiveInterval &VirtReg,
                                      SmallVectorImpl<Register> &NewVRegs,
                                      SmallVirtRegSet &FixedRegisters,
                                      unsigned Depth) {
   unsigned CostPerUseLimit = ~0u;
   // First try assigning a free register.
-  AllocationOrder Order(VirtReg.reg(), *VRM, RegClassInfo, Matrix);
+  auto Order =
+      AllocationOrder::create(VirtReg.reg(), *VRM, RegClassInfo, Matrix);
   if (unsigned PhysReg = tryAssign(VirtReg, Order, NewVRegs, FixedRegisters)) {
     // If VirtReg got an assignment, the eviction info is no longre relevant.
     LastEvicted.clearEvicteeInfo(VirtReg.reg());
     // When NewVRegs is not empty, we may have made decisions such as evicting
     // a virtual register, go with the earlier decisions and use the physical
     // register.
     if (CSRCost.getFrequency() && isUnusedCalleeSavedReg(PhysReg) &&
         NewVRegs.empty()) {

llvm/unittests/CodeGen/AllocationOrderTest.cpp

+//===- llvm/unittest/CodeGen/AllocationOrderTest.cpp - AllocationOrder tests =//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "../lib/CodeGen/AllocationOrder.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+namespace {
+std::vector<MCPhysReg> loadOrder(AllocationOrder &O, unsigned Limit = 0) {
+  std::vector<MCPhysReg> Ret;
+  O.rewind();
+  while (auto R = O.next(Limit))
+    Ret.push_back(R);
+  return Ret;
+}
+} // namespace
+
+TEST(AllocationOrderTest, Basic) {
+  SmallVector<MCPhysReg, 16> Hints = {1, 2, 3};
+  SmallVector<MCPhysReg, 16> Order = {4, 5, 6, 7};
+  AllocationOrder O(std::move(Hints), Order, false);
+  EXPECT_EQ((std::vector<MCPhysReg>{1, 2, 3, 4, 5, 6, 7}), loadOrder(O));
+}
+
+TEST(AllocationOrderTest, Duplicates) {
+  SmallVector<MCPhysReg, 16> Hints = {1, 2, 3};
+  SmallVector<MCPhysReg, 16> Order = {4, 1, 5, 6};
+  AllocationOrder O(std::move(Hints), Order, false);
+  EXPECT_EQ((std::vector<MCPhysReg>{1, 2, 3, 4, 5, 6}), loadOrder(O));
+}
+
+TEST(AllocationOrderTest, HardHints) {
+  SmallVector<MCPhysReg, 16> Hints = {1, 2, 3};
+  SmallVector<MCPhysReg, 16> Order = {4, 5, 6, 7};
+  AllocationOrder O(std::move(Hints), Order, true);
+  EXPECT_EQ((std::vector<MCPhysReg>{1, 2, 3}), loadOrder(O));
+}
+
+TEST(AllocationOrderTest, LimitsBasic) {
+  SmallVector<MCPhysReg, 16> Hints = {1, 2, 3};
+  SmallVector<MCPhysReg, 16> Order = {4, 5, 6, 7};
+  AllocationOrder O(std::move(Hints), Order, false);
+  EXPECT_EQ((std::vector<MCPhysReg>{1, 2, 3, 4, 5, 6, 7}), loadOrder(O, 0));
+  EXPECT_EQ((std::vector<MCPhysReg>{1, 2, 3, 4}), loadOrder(O, 1));
+}
+
+TEST(AllocationOrderTest, LimitsDuplicates) {
+  SmallVector<MCPhysReg, 16> Hints = {1, 2, 3};
+  SmallVector<MCPhysReg, 16> Order = {4, 1, 5, 6};
+  AllocationOrder O(std::move(Hints), Order, false);
+  EXPECT_EQ((std::vector<MCPhysReg>{1, 2, 3, 4}), loadOrder(O, 1));
+  EXPECT_EQ((std::vector<MCPhysReg>{1, 2, 3, 4}), loadOrder(O, 2));
+  EXPECT_EQ((std::vector<MCPhysReg>{1, 2, 3, 4, 5}), loadOrder(O, 3));
+  EXPECT_EQ((std::vector<MCPhysReg>{1, 2, 3, 4, 5, 6}), loadOrder(O, 4));
+}
+
+TEST(AllocationOrderTest, LimitsHardHints) {
+  SmallVector<MCPhysReg, 16> Hints = {1, 2, 3};
+  SmallVector<MCPhysReg, 16> Order = {4, 1, 5, 6};
+  AllocationOrder O(std::move(Hints), Order, true);
+  EXPECT_EQ((std::vector<MCPhysReg>{1, 2, 3}), loadOrder(O, 1));
+}
+
+TEST(AllocationOrderTest, DuplicateIsFirst) {
+  SmallVector<MCPhysReg, 16> Hints = {1, 2, 3};
+  SmallVector<MCPhysReg, 16> Order = {1, 4, 5, 6};
+  AllocationOrder O(std::move(Hints), Order, false);
+  EXPECT_EQ((std::vector<MCPhysReg>{1, 2, 3, 4, 5, 6}), loadOrder(O));
+}
+
+TEST(AllocationOrderTest, DuplicateIsFirstWithLimits) {
+  SmallVector<MCPhysReg, 16> Hints = {1, 2, 3};
+  SmallVector<MCPhysReg, 16> Order = {1, 4, 5, 6};
+  AllocationOrder O(std::move(Hints), Order, false);
+  EXPECT_EQ((std::vector<MCPhysReg>{1, 2, 3}), loadOrder(O, 1));
+  EXPECT_EQ((std::vector<MCPhysReg>{1, 2, 3, 4}), loadOrder(O, 2));
+  EXPECT_EQ((std::vector<MCPhysReg>{1, 2, 3, 4, 5}), loadOrder(O, 3));
+}
+
+TEST(AllocationOrderTest, NoHints) {
+  SmallVector<MCPhysReg, 16> Hints;
+  SmallVector<MCPhysReg, 16> Order = {1, 2, 3, 4};
+  AllocationOrder O(std::move(Hints), Order, false);
+  EXPECT_EQ((std::vector<MCPhysReg>{1, 2, 3, 4}), loadOrder(O));
+  EXPECT_EQ((std::vector<MCPhysReg>{1, 2}), loadOrder(O, 2));
+  EXPECT_EQ((std::vector<MCPhysReg>{1, 2, 3}), loadOrder(O, 3));
+}
+
+TEST(AllocationOrderTest, IsHintTest) {
+  SmallVector<MCPhysReg, 16> Hints = {1, 2, 3};
+  SmallVector<MCPhysReg, 16> Order = {4, 1, 5, 6};
+  AllocationOrder O(std::move(Hints), Order, false);
+  O.rewind();
+  auto V = O.next();
+  EXPECT_TRUE(O.isHint());
+  EXPECT_EQ(V, 1U);
+  O.next();
+  EXPECT_TRUE(O.isHint());
+  O.next();
+  EXPECT_TRUE(O.isHint());
+  V = O.next();
+  EXPECT_FALSE(O.isHint());
+  EXPECT_EQ(V, 4U);
+  V = O.next();
+  EXPECT_TRUE(O.isHint(1));
+  EXPECT_FALSE(O.isHint());
+  EXPECT_EQ(V, 5U);
+}

llvm/unittests/CodeGen/CMakeLists.txt

set(LLVM_LINK_COMPONENTS
   Passes
   SelectionDAG
   Support
   Target
   )
 
 add_llvm_unittest(CodeGenTests
   AArch64SelectionDAGTest.cpp
+  AllocationOrderTest.cpp
   AsmPrinterDwarfTest.cpp
   DIEHashTest.cpp
   DIETest.cpp
   LowLevelTypeTest.cpp
   LexicalScopesTest.cpp
   MachineInstrBundleIteratorTest.cpp
   MachineInstrTest.cpp
   MachineOperandTest.cpp