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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
|
// SPDX-License-Identifier: GPL-3.0-or-later
#include "rcc/CodeGen/MachineBranchRelaxation.h"
#include "rcc/CodeGen/LiveVariables.h"
#include "rcc/CodeGen/MachineBasicBlock.h"
#include "rcc/CodeGen/MachineFunction.h"
#include "rcc/CodeGen/MachineFunctionCloner.h"
#include "rcc/CodeGen/MachineInstr.h"
#include "rcc/CodeGen/TargetDescription.h"
#include "rcc/CodeGen/TargetInstrInfo.h"
#include <cstddef>
#include <cstdint>
#include <limits>
#include <optional>
#include <string>
#include <unordered_map>
#include <utility>
namespace rcc {
namespace {
struct MachineLayout final {
std::unordered_map<const MachineBasicBlock *, std::uint64_t> BlockOffsets;
std::unordered_map<const MachineInstr *, std::uint64_t> InstructionOffsets;
};
[[nodiscard]] const MachinePassContract &relaxationContract() {
static const MachinePassContract Contract = [] {
MachinePassContract Value{
.Name = "machine-branch-relaxation",
.Requires = {MachineFunctionProperty::Selected, MachineFunctionProperty::NoPHIs,
MachineFunctionProperty::TiedOpsRewritten, MachineFunctionProperty::NoVRegs,
MachineFunctionProperty::TracksLiveness,
MachineFunctionProperty::FrameFinalized,
MachineFunctionProperty::NoFrameIndices},
.Sets = {},
.Clears = {},
.RequiredAnalyses = {},
.VerificationStage = PipelineStage::PostRAFinalized,
};
Value.ThreadSafety = PassThreadSafety::ThreadSafe;
Value.DeclaredChanges = {MachinePassChange::Instructions, MachinePassChange::Operands};
return Value;
}();
return Contract;
}
[[nodiscard]] Error prefixedError(const Error &Failure, std::string Prefix) {
Prefix.append(Failure.message());
return Error(Failure.code(), std::move(Prefix));
}
[[nodiscard]] Expected<std::uint64_t> alignTo(std::uint64_t Value, std::uint64_t Alignment) {
if (Alignment == 0 || (Alignment & (Alignment - 1U)) != 0)
return makeUnexpected(ErrorCode::VerificationError, "block alignment is not a power of two");
const std::uint64_t Mask = Alignment - 1U;
if (Value > std::numeric_limits<std::uint64_t>::max() - Mask)
return makeUnexpected(ErrorCode::BranchRelaxationFailed, "machine layout offset overflowed");
return (Value + Mask) & ~Mask;
}
[[nodiscard]] Expected<MachineLayout> computeLayout(MachineFunction &Function,
const TargetDescription &Target,
const TargetInstrInfo &Info) {
MachineLayout Result;
std::uint64_t Offset = 0;
for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) {
auto Aligned = alignTo(Offset, Block->attributes().alignment().bytes());
if (!Aligned)
return std::unexpected(Aligned.error());
Offset = *Aligned;
Result.BlockOffsets.emplace(Block, Offset);
for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
Instruction = Instruction->next()) {
Result.InstructionOffsets.emplace(Instruction, Offset);
auto Size = Info.instructionSize(*Instruction, Function, Target);
if (!Size)
return std::unexpected(Size.error());
if (Offset > std::numeric_limits<std::uint64_t>::max() - *Size)
return makeUnexpected(ErrorCode::BranchRelaxationFailed, "machine layout size overflowed");
Offset += *Size;
}
}
return Result;
}
[[nodiscard]] Expected<std::int64_t> displacement(std::uint64_t Source, std::uint64_t Target) {
if (Target >= Source) {
const std::uint64_t Difference = Target - Source;
if (Difference > static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max()))
return makeUnexpected(ErrorCode::BranchRelaxationFailed,
"forward branch displacement overflowed");
return static_cast<std::int64_t>(Difference);
}
const std::uint64_t Difference = Source - Target;
if (Difference > static_cast<std::uint64_t>(std::numeric_limits<std::int64_t>::max()))
return makeUnexpected(ErrorCode::BranchRelaxationFailed,
"backward branch displacement overflowed");
return -static_cast<std::int64_t>(Difference);
}
} // namespace
const MachinePassContract &MachineBranchRelaxationPass::contract() const noexcept {
return relaxationContract();
}
Expected<MachinePassResult>
MachineBranchRelaxationPass::run(MachineFunction &Function, const TargetDescription &Target,
MachineFunctionAnalysisManager &Analyses) {
if (!Function.properties().containsAll(contract().Requires)) {
return makeUnexpected(ErrorCode::VerificationError,
"branch relaxation requires finalized frame and tracked liveness");
}
auto Trial = cloneMachineFunction(
Function, Target,
MachineFunctionCloneOptions{.NewStableID = Function.stableID(), .NewName = std::nullopt});
if (!Trial)
return std::unexpected(prefixedError(Trial.error(), "branch relaxation setup failed: "));
MachineActionReplay Actions(Analyses, Trial->InstructionStableIDs);
auto TrialResult = runImplementation(*Trial->ClonedFunction, Target, Actions);
if (!TrialResult)
return std::unexpected(TrialResult.error());
Actions.beginReplay();
auto Result = runImplementation(Function, Target, Actions);
if (!Result) {
return std::unexpected(prefixedError(
Result.error(), "branch relaxation diverged after a successful transaction preflight: "));
}
auto Replayed = Actions.finishReplay();
if (!Replayed)
return std::unexpected(Replayed.error());
return Result;
}
Expected<MachinePassResult>
MachineBranchRelaxationPass::runImplementation(MachineFunction &Function,
const TargetDescription &Target,
MachineActionReplay &Actions) const {
if (Options.ConvergenceWatchdog == 0)
return makeUnexpected(ErrorCode::InvalidArgument, "branch relaxation watchdog must be nonzero");
MachinePassResult Result;
for (std::size_t Iteration = 0; Iteration < Options.ConvergenceWatchdog; ++Iteration) {
auto Layout = computeLayout(Function, Target, *Info);
if (!Layout)
return std::unexpected(Layout.error());
bool Changed = false;
for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr && !Changed;
Block = Block->next()) {
for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
Instruction = Instruction->next()) {
auto BranchTarget = Info->branchTarget(*Instruction, Function, Target);
if (!BranchTarget)
return std::unexpected(BranchTarget.error());
if (*BranchTarget == nullptr)
continue;
const auto SourcePosition = Layout->InstructionOffsets.find(Instruction);
const auto TargetPosition = Layout->BlockOffsets.find(*BranchTarget);
if (SourcePosition == Layout->InstructionOffsets.end() ||
TargetPosition == Layout->BlockOffsets.end()) {
return makeUnexpected(ErrorCode::InternalError,
"branch relaxation lost an instruction or target offset");
}
auto Offset = displacement(SourcePosition->second, TargetPosition->second);
if (!Offset)
return std::unexpected(Offset.error());
if (Info->isBranchOffsetInRange(*Instruction, *Offset))
continue;
auto Accepted = Actions.request("relax-branch", Function, Instruction->stableID());
if (!Accepted)
return std::unexpected(Accepted.error());
if (!*Accepted) {
return makeUnexpected(ErrorCode::BranchRelaxationFailed,
"required branch relaxation action was rejected");
}
auto Relaxed = Info->relaxBranch(*Instruction, *Offset, Function, Target);
if (!Relaxed)
return std::unexpected(Relaxed.error());
if (!*Relaxed) {
return makeUnexpected(ErrorCode::BranchRelaxationFailed,
"target did not relax an out-of-range branch");
}
Changed = true;
Result.Changed = true;
break;
}
}
if (Changed)
continue;
if (Result.Changed) {
auto Rebuilt = rebuildMachineLiveness(Function, Target);
if (!Rebuilt)
return std::unexpected(Rebuilt.error());
Result.Changes = {MachinePassChange::Instructions, MachinePassChange::Operands};
Result.Preserved = PreservedAnalyses::none();
} else {
Result.Preserved = PreservedAnalyses::all();
}
return Result;
}
return makeUnexpected(ErrorCode::InternalError,
"branch relaxation failed to reach a monotonic fixed point");
}
} // namespace rcc
|
