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