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 // Scratch space. Allocated here to avoid repeated malloc calls in
54 // selectOrSplit().
55 BitVector UsableRegs;
56
57 bool LRE_CanEraseVirtReg(Register) override;
58 void LRE_WillShrinkVirtReg(Register) override;
59
60public:
61 RABasic(const RegAllocFilterFunc F = nullptr);
62
63 /// Return the pass name.
64 StringRef getPassName() const override { return "Basic Register Allocator"; }
65
66 /// RABasic analysis usage.
67 void getAnalysisUsage(AnalysisUsage &AU) const override;
68
69 void releaseMemory() override;
70
71 Spiller &spiller() override { return *SpillerInstance; }
72
73 void enqueueImpl(const LiveInterval *LI) override { Queue.push(x: LI); }
74
75 const LiveInterval *dequeue() override {
76 if (Queue.empty())
77 return nullptr;
78 const LiveInterval *LI = Queue.top();
79 Queue.pop();
80 return LI;
81 }
82
83 MCRegister selectOrSplit(const LiveInterval &VirtReg,
84 SmallVectorImpl<Register> &SplitVRegs) override;
85
86 /// Perform register allocation.
87 bool runOnMachineFunction(MachineFunction &mf) override;
88
89 MachineFunctionProperties getRequiredProperties() const override {
90 return MachineFunctionProperties().set(
91 MachineFunctionProperties::Property::NoPHIs);
92 }
93
94 MachineFunctionProperties getClearedProperties() const override {
95 return MachineFunctionProperties().set(
96 MachineFunctionProperties::Property::IsSSA);
97 }
98
99 // Helper for spilling all live virtual registers currently unified under preg
100 // that interfere with the most recently queried lvr. Return true if spilling
101 // was successful, and append any new spilled/split intervals to splitLVRs.
102 bool spillInterferences(const LiveInterval &VirtReg, MCRegister PhysReg,
103 SmallVectorImpl<Register> &SplitVRegs);
104
105 static char ID;
106};
107} // namespace llvm
108#endif
109