1//===-- RegAllocBasic.h - Basic Register Allocator Header -----------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// This file declares the RABasic class, which provides a minimal
11/// implementation of the basic register allocator.
12///
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_CODEGEN_REGALLOCBASIC_H
16#define LLVM_CODEGEN_REGALLOCBASIC_H
17
18#include "RegAllocBase.h"
19#include "llvm/CodeGen/LiveRangeEdit.h"
20#include "llvm/CodeGen/MachineFunctionPass.h"
21#include "llvm/CodeGen/Spiller.h"
22#include <queue>
23#include <tuple>
24
25namespace llvm {
26
27struct CompSpillWeight {
28 bool operator()(const LiveInterval *A, const LiveInterval *B) const {
29 // Compare by weight first, then use register number as a stable tie-breaker
30 // to ensure deterministic ordering when the weights are equal.
31 return std::tuple(A->weight(), A->reg()) <
32 std::tuple(B->weight(), B->reg());
33 }
34};
35
36/// RABasic provides a minimal implementation of the basic register allocation
37/// algorithm. It prioritizes live virtual registers by spill weight and spills
38/// whenever a register is unavailable. This is not practical in production but
39/// provides a useful baseline both for measuring other allocators and comparing
40/// the speed of the basic algorithm against other styles of allocators.
41class LLVM_LIBRARY_VISIBILITY RABasic : public MachineFunctionPass,
42 public RegAllocBase,
43 private LiveRangeEdit::Delegate {
44 // context
45 MachineFunction *MF = nullptr;
46
47 // state
48 std::unique_ptr<Spiller> SpillerInstance;
49 std::priority_queue<const LiveInterval *, std::vector<const LiveInterval *>,
50 CompSpillWeight>
51 Queue;
52
53 bool LRE_CanEraseVirtReg(Register) override;
54 void LRE_WillShrinkVirtReg(Register) override;
55
56public:
57 RABasic(const RegAllocFilterFunc F = nullptr);
58
59 /// Return the pass name.
60 StringRef getPassName() const override { return "Basic Register Allocator"; }
61
62 /// RABasic analysis usage.
63 void getAnalysisUsage(AnalysisUsage &AU) const override;
64
65 void releaseMemory() override;
66
67 Spiller &spiller() override { return *SpillerInstance; }
68
69 void enqueueImpl(const LiveInterval *LI) override { Queue.push(x: LI); }
70
71 const LiveInterval *dequeue() override {
72 if (Queue.empty())
73 return nullptr;
74 const LiveInterval *LI = Queue.top();
75 Queue.pop();
76 return LI;
77 }
78
79 MCRegister selectOrSplit(const LiveInterval &VirtReg,
80 SmallVectorImpl<Register> &SplitVRegs) override;
81
82 /// Perform register allocation.
83 bool runOnMachineFunction(MachineFunction &mf) override;
84
85 MachineFunctionProperties getRequiredProperties() const override {
86 return MachineFunctionProperties().set(
87 MachineFunctionProperties::Property::NoPHIs);
88 }
89
90 MachineFunctionProperties getClearedProperties() const override {
91 return MachineFunctionProperties().set(
92 MachineFunctionProperties::Property::IsSSA);
93 }
94
95 // Helper for spilling all live virtual registers currently unified under preg
96 // that interfere with the most recently queried lvr. Return true if spilling
97 // was successful, and append any new spilled/split intervals to splitLVRs.
98 bool spillInterferences(const LiveInterval &VirtReg, MCRegister PhysReg,
99 SmallVectorImpl<Register> &SplitVRegs);
100
101 static char ID;
102};
103} // namespace llvm
104#endif
105