diff --git a/llvm/lib/CodeGen/AllocationOrder.h b/llvm/lib/CodeGen/AllocationOrder.h --- a/llvm/lib/CodeGen/AllocationOrder.h +++ b/llvm/lib/CodeGen/AllocationOrder.h @@ -28,12 +28,12 @@ class LiveRegMatrix; class LLVM_LIBRARY_VISIBILITY AllocationOrder { - SmallVector Hints; + const SmallVector Hints; ArrayRef Order; - int Pos; + int Pos = 0; // If HardHints is true, *only* Hints will be returned. - bool HardHints; + const bool HardHints; public: @@ -41,10 +41,16 @@ /// @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, - const RegisterClassInfo &RegClassInfo, - const LiveRegMatrix *Matrix); + 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 &&Hints, ArrayRef Order, + bool HardHints) + : Hints(std::move(Hints)), Order(Order), + Pos(-static_cast(this->Hints.size())), HardHints(HardHints) {} /// Get the allocation order without reordered hints. ArrayRef getOrder() const { return Order; } @@ -52,7 +58,7 @@ /// 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) diff --git a/llvm/lib/CodeGen/AllocationOrder.cpp b/llvm/lib/CodeGen/AllocationOrder.cpp --- a/llvm/lib/CodeGen/AllocationOrder.cpp +++ b/llvm/lib/CodeGen/AllocationOrder.cpp @@ -26,17 +26,15 @@ #define DEBUG_TYPE "regalloc" // Compare VirtRegMap::getRegAllocPref(). -AllocationOrder::AllocationOrder(unsigned VirtReg, - const VirtRegMap &VRM, - const RegisterClassInfo &RegClassInfo, - const LiveRegMatrix *Matrix) - : Pos(0), HardHints(false) { +AllocationOrder AllocationOrder::create(unsigned VirtReg, const VirtRegMap &VRM, + const RegisterClassInfo &RegClassInfo, + 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 Hints; + bool HardHints = + TRI->getRegAllocationHints(VirtReg, Order, Hints, MF, &VRM, Matrix); LLVM_DEBUG({ if (!Hints.empty()) { @@ -51,4 +49,5 @@ assert(is_contained(Order, Hints[I]) && "Target hint is outside allocation order."); #endif + return AllocationOrder(std::move(Hints), Order, HardHints); } diff --git a/llvm/lib/CodeGen/RegAllocBasic.cpp b/llvm/lib/CodeGen/RegAllocBasic.cpp --- a/llvm/lib/CodeGen/RegAllocBasic.cpp +++ b/llvm/lib/CodeGen/RegAllocBasic.cpp @@ -259,7 +259,8 @@ SmallVector 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)) { diff --git a/llvm/lib/CodeGen/RegAllocGreedy.cpp b/llvm/lib/CodeGen/RegAllocGreedy.cpp --- a/llvm/lib/CodeGen/RegAllocGreedy.cpp +++ b/llvm/lib/CodeGen/RegAllocGreedy.cpp @@ -800,7 +800,8 @@ //===----------------------------------------------------------------------===// 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) @@ -3013,7 +3014,8 @@ 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()); diff --git a/llvm/unittests/CodeGen/AllocationOrderTest.cpp b/llvm/unittests/CodeGen/AllocationOrderTest.cpp new file mode 100644 --- /dev/null +++ b/llvm/unittests/CodeGen/AllocationOrderTest.cpp @@ -0,0 +1,114 @@ +//===- 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 loadOrder(AllocationOrder &O, unsigned Limit = 0) { + std::vector Ret; + O.rewind(); + while (auto R = O.next(Limit)) + Ret.push_back(R); + return Ret; +} +} // namespace + +TEST(AllocationOrderTest, Basic) { + SmallVector Hints = {1, 2, 3}; + SmallVector Order = {4, 5, 6, 7}; + AllocationOrder O(std::move(Hints), Order, false); + EXPECT_EQ((std::vector{1, 2, 3, 4, 5, 6, 7}), loadOrder(O)); +} + +TEST(AllocationOrderTest, Duplicates) { + SmallVector Hints = {1, 2, 3}; + SmallVector Order = {4, 1, 5, 6}; + AllocationOrder O(std::move(Hints), Order, false); + EXPECT_EQ((std::vector{1, 2, 3, 4, 5, 6}), loadOrder(O)); +} + +TEST(AllocationOrderTest, HardHints) { + SmallVector Hints = {1, 2, 3}; + SmallVector Order = {4, 5, 6, 7}; + AllocationOrder O(std::move(Hints), Order, true); + EXPECT_EQ((std::vector{1, 2, 3}), loadOrder(O)); +} + +TEST(AllocationOrderTest, LimitsBasic) { + SmallVector Hints = {1, 2, 3}; + SmallVector Order = {4, 5, 6, 7}; + AllocationOrder O(std::move(Hints), Order, false); + EXPECT_EQ((std::vector{1, 2, 3, 4, 5, 6, 7}), loadOrder(O, 0)); + EXPECT_EQ((std::vector{1, 2, 3, 4}), loadOrder(O, 1)); +} + +TEST(AllocationOrderTest, LimitsDuplicates) { + SmallVector Hints = {1, 2, 3}; + SmallVector Order = {4, 1, 5, 6}; + AllocationOrder O(std::move(Hints), Order, false); + EXPECT_EQ((std::vector{1, 2, 3, 4}), loadOrder(O, 1)); + EXPECT_EQ((std::vector{1, 2, 3, 4}), loadOrder(O, 2)); + EXPECT_EQ((std::vector{1, 2, 3, 4, 5}), loadOrder(O, 3)); + EXPECT_EQ((std::vector{1, 2, 3, 4, 5, 6}), loadOrder(O, 4)); +} + +TEST(AllocationOrderTest, LimitsHardHints) { + SmallVector Hints = {1, 2, 3}; + SmallVector Order = {4, 1, 5, 6}; + AllocationOrder O(std::move(Hints), Order, true); + EXPECT_EQ((std::vector{1, 2, 3}), loadOrder(O, 1)); +} + +TEST(AllocationOrderTest, DuplicateIsFirst) { + SmallVector Hints = {1, 2, 3}; + SmallVector Order = {1, 4, 5, 6}; + AllocationOrder O(std::move(Hints), Order, false); + EXPECT_EQ((std::vector{1, 2, 3, 4, 5, 6}), loadOrder(O)); +} + +TEST(AllocationOrderTest, DuplicateIsFirstWithLimits) { + SmallVector Hints = {1, 2, 3}; + SmallVector Order = {1, 4, 5, 6}; + AllocationOrder O(std::move(Hints), Order, false); + EXPECT_EQ((std::vector{1, 2, 3}), loadOrder(O, 1)); + EXPECT_EQ((std::vector{1, 2, 3, 4}), loadOrder(O, 2)); + EXPECT_EQ((std::vector{1, 2, 3, 4, 5}), loadOrder(O, 3)); +} + +TEST(AllocationOrderTest, NoHints) { + SmallVector Hints; + SmallVector Order = {1, 2, 3, 4}; + AllocationOrder O(std::move(Hints), Order, false); + EXPECT_EQ((std::vector{1, 2, 3, 4}), loadOrder(O)); + EXPECT_EQ((std::vector{1, 2}), loadOrder(O, 2)); + EXPECT_EQ((std::vector{1, 2, 3}), loadOrder(O, 3)); +} + +TEST(AllocationOrderTest, IsHintTest) { + SmallVector Hints = {1, 2, 3}; + SmallVector 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); +} diff --git a/llvm/unittests/CodeGen/CMakeLists.txt b/llvm/unittests/CodeGen/CMakeLists.txt --- a/llvm/unittests/CodeGen/CMakeLists.txt +++ b/llvm/unittests/CodeGen/CMakeLists.txt @@ -15,6 +15,7 @@ add_llvm_unittest(CodeGenTests AArch64SelectionDAGTest.cpp + AllocationOrderTest.cpp AsmPrinterDwarfTest.cpp DIEHashTest.cpp DIETest.cpp