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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
// SPDX-License-Identifier: GPL-3.0-or-later
#include "RegAllocBasic.h"
#include "RegAllocBase.h"
#include "rcc/CodeGen/LiveIntervals.h"
#include "rcc/CodeGen/LiveRegMatrix.h"
#include <algorithm>
#include <memory>
#include <ranges>
namespace rcc {
namespace {
class BasicAllocatorEngine final : public RegAllocBase {
public:
BasicAllocatorEngine(MachineFunction &Function, const TargetDescription &Target,
const TargetRegisterAllocationInfo &TargetInfo,
MachineFunctionAnalysisManager &Analyses, RegisterAllocationOptions Options)
: RegAllocBase(Function, Target, TargetInfo, Analyses, Options) {}
private:
[[nodiscard]] Expected<AllocationRoundResult>
allocateRound(const LiveIntervalsAnalysis::Result &Intervals, VirtRegMap &Mapping) override {
LiveRegMatrix Matrix(Function, Target, Intervals);
AllocationRoundResult Result;
std::vector<const LiveInterval *> Worklist = orderedAllocationIntervals(Intervals, Function);
std::ranges::stable_sort(Worklist, [&](const LiveInterval *Left, const LiveInterval *Right) {
const bool LeftSpillable = Mapping.isSpillable(Left->Reg);
const bool RightSpillable = Mapping.isSpillable(Right->Reg);
if (LeftSpillable != RightSpillable)
return !LeftSpillable;
if (Left->SpillWeight != Right->SpillWeight)
return Left->SpillWeight > Right->SpillWeight;
return false;
});
for (const LiveInterval *Interval : Worklist) {
const Register VirtualReg = Interval->Reg;
if (regalloc_detail::hasTerminatorDefinition(Function, Target, VirtualReg)) {
auto Marked = Mapping.setSpillable(VirtualReg, false);
if (!Marked)
return std::unexpected(Marked.error());
}
auto Candidates = regalloc_detail::allocationOrder(Function, Target, TargetInfo, VirtualReg);
if (!Candidates)
return std::unexpected(Candidates.error());
bool Assigned = false;
for (const PhysicalRegister Candidate : *Candidates) {
if (Matrix.checkInterference(VirtualReg, Candidate).Kind != RegisterInterferenceKind::Free)
continue;
auto MatrixAssignment = Matrix.assign(VirtualReg, Candidate);
if (!MatrixAssignment)
continue;
auto MapAssignment = Mapping.assign(VirtualReg, Candidate);
if (!MapAssignment)
return std::unexpected(MapAssignment.error());
Assigned = true;
break;
}
if (!Assigned) {
if (!Mapping.isSpillable(VirtualReg)) {
return makeUnexpected(ErrorCode::RegisterAllocationFailed,
"BasicAllocator cannot assign a non-spillable virtual register");
}
Result.Spilled.push_back(VirtualReg);
}
}
return Result;
}
};
[[nodiscard]] const MachinePassContract &basicContract() {
static const MachinePassContract Contract = [] {
MachinePassContract Value{
.Name = "BasicAllocator",
.Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs,
MachineFunctionProperty::TiedOpsRewritten,
MachineFunctionProperty::TracksLiveness},
.Sets = {},
.Clears = {MachineFunctionProperty::IsSSA},
.RequiredAnalyses = {MachineFunctionAnalysisManager::id<LiveIntervalsAnalysis>(),
MachineFunctionAnalysisManager::id<VirtRegMapAnalysis>()},
.VerificationStage = std::nullopt,
};
Value.ThreadSafety = PassThreadSafety::ThreadSafe;
return Value;
}();
return Contract;
}
} // namespace
const MachinePassContract &BasicAllocatorPass::contract() const noexcept {
return basicContract();
}
Expected<MachinePassResult> BasicAllocatorPass::run(MachineFunction &Function,
const TargetDescription &Target,
MachineFunctionAnalysisManager &Analyses) {
if (Info == nullptr)
return makeUnexpected(ErrorCode::InvalidArgument, "BasicAllocator requires target behavior");
const std::vector<PhysicalRegister> FunctionReserved =
regalloc_detail::functionReservedRegisters(Function, Target, *Info);
auto Reserved = regalloc_detail::reserveFunctionRegisters(Function, FunctionReserved);
if (!Reserved)
return std::unexpected(Reserved.error());
BasicAllocatorEngine Allocator(Function, Target, *Info, Analyses, Options);
auto Mapping = Analyses.getResult<VirtRegMapAnalysis>(Function, Target);
if (!Mapping)
return std::unexpected(Mapping.error());
auto Allocated = Allocator.run(**Mapping);
if (!Allocated)
return std::unexpected(Allocated.error());
Allocated->Changed |= *Reserved;
MachinePassResult Result = regalloc_detail::passResult(*Allocated);
Result.Preserved.preserve<VirtRegMapAnalysis>();
return Result;
}
std::unique_ptr<MachineFunctionPass>
createBasicAllocatorPass(const TargetRegisterAllocationInfo &Info,
RegisterAllocationOptions Options) {
return std::make_unique<BasicAllocatorPass>(Info, Options);
}
} // namespace rcc
|
