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
|
// SPDX-License-Identifier: GPL-3.0-or-later
#include "rcc/CodeGen/SlotIndexes.h"
#include "rcc/CodeGen/MachineBasicBlock.h"
#include "rcc/CodeGen/MachineFunction.h"
#include "rcc/CodeGen/MachineInstr.h"
#include <cstdint>
#include <limits>
namespace rcc {
namespace {
constexpr std::uint64_t SlotSpacing = 16;
constexpr std::uint64_t SlotAlignmentMask = 3;
} // namespace
SlotIndex
SlotIndexesAnalysis::Result::instructionIndex(const MachineInstr &Instruction) const noexcept {
const auto Position = InstructionSlots.find(Instruction.stableID());
return Position == InstructionSlots.end() ? SlotIndex{} : Position->second;
}
SlotIndex SlotIndexesAnalysis::Result::blockStart(const MachineBasicBlock &Block) const noexcept {
const auto Position = BlockStarts.find(&Block);
return Position == BlockStarts.end() ? SlotIndex{} : Position->second;
}
SlotIndex SlotIndexesAnalysis::Result::blockEnd(const MachineBasicBlock &Block) const noexcept {
const auto Position = BlockEnds.find(&Block);
return Position == BlockEnds.end() ? SlotIndex{} : Position->second;
}
const MachineInstr *
SlotIndexesAnalysis::Result::instructionFromIndex(SlotIndex Index) const noexcept {
if (!Index.isValid())
return nullptr;
const auto Position = SlotToInstruction.find(Index.baseIndex().value());
return Position == SlotToInstruction.end() ? nullptr : Position->second;
}
const MachineBasicBlock *
SlotIndexesAnalysis::Result::blockFromIndex(SlotIndex Index) const noexcept {
if (!Index.isValid())
return nullptr;
for (const MachineBasicBlock *Block : BlocksByStart) {
const SlotIndex Start = blockStart(*Block);
const SlotIndex End = blockEnd(*Block);
if (!(Index < Start) && Index < End)
return Block;
}
return nullptr;
}
Expected<void> SlotIndexesAnalysis::Result::insertInstruction(const MachineInstr &Instruction) {
const MachineBasicBlock *Block = Instruction.parent();
if (Block == nullptr || !BlockStarts.contains(Block) || !BlockEnds.contains(Block)) {
return makeUnexpected(ErrorCode::InvalidArgument,
"SlotIndex insertion requires a linked indexed instruction");
}
if (InstructionSlots.contains(Instruction.stableID())) {
return makeUnexpected(ErrorCode::InvalidArgument, "instruction already has a SlotIndex");
}
const MachineInstr *Previous = Instruction.previous();
const MachineInstr *Next = Instruction.next();
const SlotIndex LowerIndex =
Previous == nullptr ? blockStart(*Block) : instructionIndex(*Previous);
const SlotIndex UpperIndex = Next == nullptr ? blockEnd(*Block) : instructionIndex(*Next);
if (!LowerIndex.isValid() || !UpperIndex.isValid()) {
return makeUnexpected(ErrorCode::InvalidArgument,
"adjacent instructions are missing SlotIndexes");
}
const std::uint64_t Lower = LowerIndex.baseIndex().value();
const std::uint64_t Upper = UpperIndex.baseIndex().value();
if (Upper <= Lower || Upper - Lower <= SlotAlignmentMask + 1U) {
return makeUnexpected(ErrorCode::Unsupported,
"local SlotIndex space is exhausted; renumbering is required");
}
std::uint64_t Candidate = ((Lower + Upper) / 2U) & ~SlotAlignmentMask;
if (Candidate <= Lower)
Candidate = Lower + SlotAlignmentMask + 1U;
if (Candidate >= Upper) {
return makeUnexpected(ErrorCode::Unsupported,
"local SlotIndex space is exhausted; renumbering is required");
}
const SlotIndex Index = SlotIndex::fromValue(Candidate).registerSlot();
InstructionSlots.emplace(Instruction.stableID(), Index);
SlotToInstruction.emplace(Index.baseIndex().value(), &Instruction);
return {};
}
Expected<void> SlotIndexesAnalysis::Result::eraseInstruction(const MachineInstr &Instruction) {
const auto Position = InstructionSlots.find(Instruction.stableID());
if (Position == InstructionSlots.end())
return makeUnexpected(ErrorCode::InvalidArgument, "instruction has no SlotIndex");
SlotToInstruction.erase(Position->second.baseIndex().value());
InstructionSlots.erase(Position);
return {};
}
Expected<void> SlotIndexesAnalysis::Result::renumber(MachineFunction &Function) {
Result NewResult;
std::uint64_t Position = SlotSpacing;
auto Advance = [&Position]() -> Expected<void> {
if (Position > std::numeric_limits<std::uint64_t>::max() - SlotSpacing) {
return makeUnexpected(ErrorCode::Unsupported, "machine SlotIndex space is exhausted");
}
Position += SlotSpacing;
return {};
};
for (MachineBasicBlock *Block = Function.firstBlock(); Block != nullptr; Block = Block->next()) {
const SlotIndex Start = SlotIndex::fromValue(Position).withKind(SlotIndexKind::Block);
NewResult.BlockStarts.emplace(Block, Start);
NewResult.BlocksByStart.push_back(Block);
auto Advanced = Advance();
if (!Advanced)
return std::unexpected(Advanced.error());
for (MachineInstr *Instruction = Block->firstInstruction(); Instruction != nullptr;
Instruction = Instruction->next()) {
const SlotIndex Index = SlotIndex::fromValue(Position).registerSlot();
if (!NewResult.InstructionSlots.emplace(Instruction->stableID(), Index).second ||
!NewResult.SlotToInstruction.emplace(Index.baseIndex().value(), Instruction).second) {
return makeUnexpected(ErrorCode::VerificationError,
"duplicate instruction identity during SlotIndex construction");
}
Advanced = Advance();
if (!Advanced)
return std::unexpected(Advanced.error());
}
NewResult.BlockEnds.emplace(Block,
SlotIndex::fromValue(Position).withKind(SlotIndexKind::Block));
Advanced = Advance();
if (!Advanced)
return std::unexpected(Advanced.error());
}
*this = std::move(NewResult);
return {};
}
bool SlotIndexesAnalysis::Result::invalidate(const MachineFunction &,
const PreservedAnalyses &Preserved) const noexcept {
return !Preserved.preserves(MachineAnalysisManager::id<SlotIndexesAnalysis>());
}
Expected<SlotIndexesAnalysis::Result> SlotIndexesAnalysis::run(MachineFunction &Function,
const TargetDescription &,
MachineAnalysisManager &) {
Result ResultValue;
auto Numbered = ResultValue.renumber(Function);
if (!Numbered)
return std::unexpected(Numbered.error());
return ResultValue;
}
} // namespace rcc
|
