diff --git a/llvm/lib/CodeGen/CMakeLists.txt b/llvm/lib/CodeGen/CMakeLists.txt --- a/llvm/lib/CodeGen/CMakeLists.txt +++ b/llvm/lib/CodeGen/CMakeLists.txt @@ -171,6 +171,7 @@ RegAllocBase.cpp RegAllocBasic.cpp RegAllocEvictionAdvisor.cpp + RegAllocPriorityAdvisor.cpp RegAllocFast.cpp RegAllocGreedy.cpp RegAllocPBQP.cpp diff --git a/llvm/lib/CodeGen/RegAllocGreedy.h b/llvm/lib/CodeGen/RegAllocGreedy.h --- a/llvm/lib/CodeGen/RegAllocGreedy.h +++ b/llvm/lib/CodeGen/RegAllocGreedy.h @@ -15,6 +15,7 @@ #include "InterferenceCache.h" #include "RegAllocBase.h" #include "RegAllocEvictionAdvisor.h" +#include "RegAllocPriorityAdvisor.h" #include "SpillPlacement.h" #include "SplitKit.h" #include "llvm/ADT/ArrayRef.h" @@ -149,9 +150,14 @@ size_t getQueueSize() const { return Queue.size(); } // end (interface to eviction advisers) + // Interface to priority advisers + bool getRegClassPriorityTrumpsGlobalness() const { return RegClassPriorityTrumpsGlobalness; } + SlotIndexes *getIndexes() const { return Indexes; } + // end (interface to priority advisers) + private: // Convenient shortcuts. - using PQueue = std::priority_queue>; + using PQueue = std::priority_queue>; using SmallLISet = SmallPtrSet; // We need to track all tentative recolorings so we can roll back any @@ -183,6 +189,8 @@ Optional ExtraInfo; std::unique_ptr EvictAdvisor; + std::unique_ptr PriorityAdvisor; + // Enum CutOffStage to keep a track whether the register allocation failed // because of the cutoffs encountered in last chance recoloring. // Note: This is used as bitmask. New value should be next power of 2. 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 @@ -284,16 +284,27 @@ void RAGreedy::enqueue(PQueue &CurQueue, const LiveInterval *LI) { // Prioritize live ranges by size, assigning larger ranges first. // The queue holds (size, reg) pairs. - const unsigned Size = LI->getSize(); const Register Reg = LI->reg(); assert(Reg.isVirtual() && "Can only enqueue virtual registers"); - unsigned Prio; auto Stage = ExtraInfo->getOrInitStage(Reg); if (Stage == RS_New) { Stage = RS_Assign; ExtraInfo->setStage(Reg, Stage); } + + float Ret = PriorityAdvisor->getPriority(LI, Stage); + + // The virtual register number is a tie breaker for same-sized ranges. + // Give lower vreg numbers higher priority to assign them first. + CurQueue.push(std::make_pair(Ret, ~Reg)); +} + +float DefaultPriorityAdvisor::getPriority(const LiveInterval *LI, LiveRangeStage Stage) const { + const unsigned Size = LI->getSize(); + const Register Reg = LI->reg(); + unsigned Prio; + if (Stage == RS_Split) { // Unsplit ranges that couldn't be allocated immediately are deferred until // everything else has been allocated. @@ -347,9 +358,8 @@ if (VRM->hasKnownPreference(Reg)) Prio |= (1u << 30); } - // The virtual register number is a tie breaker for same-sized ranges. - // Give lower vreg numbers higher priority to assign them first. - CurQueue.push(std::make_pair(Prio, ~Reg)); + + return static_cast(Prio); } const LiveInterval *RAGreedy::dequeue() { return dequeue(Queue); } @@ -2712,6 +2722,8 @@ ExtraInfo.emplace(); EvictAdvisor = getAnalysis().getAdvisor(*MF, *this); + PriorityAdvisor = + std::make_unique(*MF, *this); VRAI = std::make_unique(*MF, *LIS, *VRM, *Loops, *MBFI); SpillerInstance.reset(createInlineSpiller(*this, *MF, *VRM, *VRAI)); diff --git a/llvm/lib/CodeGen/RegAllocPriorityAdvisor.h b/llvm/lib/CodeGen/RegAllocPriorityAdvisor.h new file mode 100644 --- /dev/null +++ b/llvm/lib/CodeGen/RegAllocPriorityAdvisor.h @@ -0,0 +1,59 @@ +//===- RegAllocPriorityAdvisor.h - Interference resolution ------*- C++ -*-===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_REGALLOCPRIORITYADVISOR_H +#define LLVM_CODEGEN_REGALLOCPRIORITYADVISOR_H + +#include "RegAllocEvictionAdvisor.h" +#include "llvm/CodeGen/SlotIndexes.h" +#include "llvm/Pass.h" + +namespace llvm { + +class MachineFunction; +class VirtRegMap; +class RAGreedy; + +/// Interface to the priority advisor, which is responsible for prioritizing +/// live ranges. +class RegAllocPriorityAdvisor { +public: + RegAllocPriorityAdvisor(const RegAllocPriorityAdvisor &) = delete; + RegAllocPriorityAdvisor(RegAllocPriorityAdvisor &&) = delete; + virtual ~RegAllocPriorityAdvisor() = default; + + /// Find the priority value for a live range. A float value is used since ML + /// prefers it. + virtual float getPriority(const LiveInterval *LI, + LiveRangeStage Stage) const = 0; + + RegAllocPriorityAdvisor(const MachineFunction &MF, const RAGreedy &RA); + +protected: + const RAGreedy &RA; + LiveIntervals *const LIS; + VirtRegMap *const VRM; + MachineRegisterInfo *const MRI; + const TargetRegisterInfo *const TRI; + const RegisterClassInfo &RegClassInfo; + SlotIndexes *Indexes; + bool RegClassPriorityTrumpsGlobalness; +}; + +class DefaultPriorityAdvisor : public RegAllocPriorityAdvisor { +public: + DefaultPriorityAdvisor(const MachineFunction &MF, const RAGreedy &RA) + : RegAllocPriorityAdvisor(MF, RA) {} + +private: + float getPriority(const LiveInterval *LI, + LiveRangeStage Stage) const override; +}; +} // namespace llvm + +#endif // LLVM_CODEGEN_REGALLOCPRIORITYADVISOR_H diff --git a/llvm/lib/CodeGen/RegAllocPriorityAdvisor.cpp b/llvm/lib/CodeGen/RegAllocPriorityAdvisor.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/CodeGen/RegAllocPriorityAdvisor.cpp @@ -0,0 +1,28 @@ +//===- RegAllocPriorityAdvisor.cpp - priority advisor ---------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// Implementation of the default priority advisor and of the Analysis pass. +// +//===----------------------------------------------------------------------===// + +#include "RegAllocPriorityAdvisor.h" +#include "RegAllocGreedy.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/VirtRegMap.h" +#include "llvm/InitializePasses.h" +#include "llvm/Pass.h" + +using namespace llvm; + +RegAllocPriorityAdvisor::RegAllocPriorityAdvisor(const MachineFunction &MF, + const RAGreedy &RA) + : RA(RA), LIS(RA.getLiveIntervals()), VRM(RA.getVirtRegMap()), + MRI(&VRM->getRegInfo()), TRI(MF.getSubtarget().getRegisterInfo()), + RegClassInfo(RA.getRegClassInfo()), Indexes(RA.getIndexes()), + RegClassPriorityTrumpsGlobalness( + RA.getRegClassPriorityTrumpsGlobalness()) {}