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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
|
// 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 "rcc/CodeGen/LiveVariables.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,
MachineAnalysisManager &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 = {MachineFunctionProperty::NoVRegs},
.Clears = {},
.RequiredAnalyses = {MachineAnalysisManager::id<LiveIntervalsAnalysis>()},
.VerificationStage = PipelineStage::RegisterAllocated,
};
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,
MachineAnalysisManager &Analyses) {
if (Info == nullptr)
return makeUnexpected(ErrorCode::InvalidArgument, "BasicAllocator requires target behavior");
auto Required = regalloc_detail::requireAllocationProperties(Function, contract());
if (!Required)
return std::unexpected(Required.error());
auto Trial = regalloc_detail::cloneForAllocation(Function, Target);
if (!Trial)
return std::unexpected(Trial.error());
const std::vector<PhysicalRegister> FunctionReserved =
regalloc_detail::functionReservedRegisters(Function, Target, *Info);
auto TrialReserved =
regalloc_detail::reserveFunctionRegisters(*Trial->ClonedFunction, FunctionReserved);
if (!TrialReserved)
return std::unexpected(TrialReserved.error());
MachineAnalysisManager TrialAnalyses;
auto Registered = registerStage11MachineAnalyses(TrialAnalyses);
if (!Registered)
return std::unexpected(Registered.error());
BasicAllocatorEngine TrialAllocator(*Trial->ClonedFunction, Target, *Info, TrialAnalyses,
Options);
auto TrialRun = TrialAllocator.run();
if (!TrialRun)
return std::unexpected(TrialRun.error());
auto TrialVerification =
regalloc_detail::verifyAllocationTrial(*Trial->ClonedFunction, Target, contract());
if (!TrialVerification)
return std::unexpected(TrialVerification.error());
BasicAllocatorEngine Allocator(Function, Target, *Info, Analyses, Options);
auto Allocated = Allocator.run();
if (!Allocated) {
return std::unexpected(regalloc_detail::withPrefix(
Allocated.error(), "BasicAllocator diverged after a successful transaction preflight: "));
}
auto Reserved = regalloc_detail::reserveFunctionRegisters(Function, FunctionReserved);
if (!Reserved)
return std::unexpected(Reserved.error());
Allocated->Changed |= *Reserved;
return regalloc_detail::passResult(*Allocated);
}
std::unique_ptr<MachineFunctionPass>
createBasicAllocatorPass(const TargetRegisterAllocationInfo &Info,
RegisterAllocationOptions Options) {
return std::make_unique<BasicAllocatorPass>(Info, Options);
}
} // namespace rcc
|
