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
208
209
210
211
212
213
214
215
216
217
218
219
|
//===- RegAllocEvictionAdvisor.h - Interference resolution ------*- C++ -*-===//
//
// 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
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_CODEGEN_REGALLOCEVICTIONADVISOR_H
#define LLVM_CODEGEN_REGALLOCEVICTIONADVISOR_H
#include "AllocationOrder.h"
#include "llvm/ADT/IndexedMap.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/CodeGen/LiveInterval.h"
#include "llvm/CodeGen/LiveIntervals.h"
#include "llvm/CodeGen/LiveRegMatrix.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Register.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/Pass.h"
namespace llvm {
using SmallVirtRegSet = SmallSet<Register, 16>;
// Live ranges pass through a number of stages as we try to allocate them.
// Some of the stages may also create new live ranges:
//
// - Region splitting.
// - Per-block splitting.
// - Local splitting.
// - Spilling.
//
// Ranges produced by one of the stages skip the previous stages when they are
// dequeued. This improves performance because we can skip interference checks
// that are unlikely to give any results. It also guarantees that the live
// range splitting algorithm terminates, something that is otherwise hard to
// ensure.
enum LiveRangeStage {
/// Newly created live range that has never been queued.
RS_New,
/// Only attempt assignment and eviction. Then requeue as RS_Split.
RS_Assign,
/// Attempt live range splitting if assignment is impossible.
RS_Split,
/// Attempt more aggressive live range splitting that is guaranteed to make
/// progress. This is used for split products that may not be making
/// progress.
RS_Split2,
/// Live range will be spilled. No more splitting will be attempted.
RS_Spill,
/// Live range is in memory. Because of other evictions, it might get moved
/// in a register in the end.
RS_Memory,
/// There is nothing more we can do to this live range. Abort compilation
/// if it can't be assigned.
RS_Done
};
/// Cost of evicting interference - used by default advisor, and the eviction
/// chain heuristic in RegAllocGreedy.
// FIXME: this can be probably made an implementation detail of the default
// advisor, if the eviction chain logic can be refactored.
struct EvictionCost {
unsigned BrokenHints = 0; ///< Total number of broken hints.
float MaxWeight = 0; ///< Maximum spill weight evicted.
EvictionCost() = default;
bool isMax() const { return BrokenHints == ~0u; }
void setMax() { BrokenHints = ~0u; }
void setBrokenHints(unsigned NHints) { BrokenHints = NHints; }
bool operator<(const EvictionCost &O) const {
return std::tie(BrokenHints, MaxWeight) <
std::tie(O.BrokenHints, O.MaxWeight);
}
};
/// Interface to the eviction advisor, which is responsible for making a
/// decision as to which live ranges should be evicted (if any).
class RAGreedy;
class RegAllocEvictionAdvisor {
public:
RegAllocEvictionAdvisor(const RegAllocEvictionAdvisor &) = delete;
RegAllocEvictionAdvisor(RegAllocEvictionAdvisor &&) = delete;
virtual ~RegAllocEvictionAdvisor() = default;
/// Find a physical register that can be freed by evicting the FixedRegisters,
/// or return NoRegister. The eviction decision is assumed to be correct (i.e.
/// no fixed live ranges are evicted) and profitable.
virtual MCRegister
tryFindEvictionCandidate(LiveInterval &VirtReg, const AllocationOrder &Order,
uint8_t CostPerUseLimit,
const SmallVirtRegSet &FixedRegisters) const = 0;
/// Find out if we can evict the live ranges occupying the given PhysReg,
/// which is a hint (preferred register) for VirtReg.
virtual bool
canEvictHintInterference(LiveInterval &VirtReg, MCRegister PhysReg,
const SmallVirtRegSet &FixedRegisters) const = 0;
/// Returns true if the given \p PhysReg is a callee saved register and has
/// not been used for allocation yet.
bool isUnusedCalleeSavedReg(MCRegister PhysReg) const;
protected:
RegAllocEvictionAdvisor(MachineFunction &MF, const RAGreedy &RA);
Register canReassign(LiveInterval &VirtReg, Register PrevReg) const;
// Get the upper limit of elements in the given Order we need to analize.
// TODO: is this heuristic, we could consider learning it.
Optional<unsigned> getOrderLimit(const LiveInterval &VirtReg,
const AllocationOrder &Order,
unsigned CostPerUseLimit) const;
// Determine if it's worth trying to allocate this reg, given the
// CostPerUseLimit
// TODO: this is a heuristic component we could consider learning, too.
bool canAllocatePhysReg(unsigned CostPerUseLimit, MCRegister PhysReg) const;
const MachineFunction &MF;
const RAGreedy &RA;
LiveRegMatrix *const Matrix;
LiveIntervals *const LIS;
VirtRegMap *const VRM;
MachineRegisterInfo *const MRI;
const TargetRegisterInfo *const TRI;
const RegisterClassInfo &RegClassInfo;
const ArrayRef<uint8_t> RegCosts;
/// Run or not the local reassignment heuristic. This information is
/// obtained from the TargetSubtargetInfo.
const bool EnableLocalReassign;
private:
unsigned NextCascade = 1;
};
/// ImmutableAnalysis abstraction for fetching the Eviction Advisor. We model it
/// as an analysis to decouple the user from the implementation insofar as
/// dependencies on other analyses goes. The motivation for it being an
/// immutable pass is twofold:
/// - in the ML implementation case, the evaluator is stateless but (especially
/// in the development mode) expensive to set up. With an immutable pass, we set
/// it up once.
/// - in the 'development' mode ML case, we want to capture the training log
/// during allocation (this is a log of features encountered and decisions
/// made), and then measure a score, potentially a few steps after allocation
/// completes. So we need the properties of an immutable pass to keep the logger
/// state around until we can make that measurement.
///
/// Because we need to offer additional services in 'development' mode, the
/// implementations of this analysis need to implement RTTI support.
class RegAllocEvictionAdvisorAnalysis : public ImmutablePass {
public:
enum class AdvisorMode : int { Default, Release, Development };
RegAllocEvictionAdvisorAnalysis(AdvisorMode Mode)
: ImmutablePass(ID), Mode(Mode){};
static char ID;
/// Get an advisor for the given context (i.e. machine function, etc)
virtual std::unique_ptr<RegAllocEvictionAdvisor>
getAdvisor(MachineFunction &MF, const RAGreedy &RA) = 0;
AdvisorMode getAdvisorMode() const { return Mode; }
protected:
// This analysis preserves everything, and subclasses may have additional
// requirements.
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.setPreservesAll();
}
private:
StringRef getPassName() const override;
const AdvisorMode Mode;
};
/// Specialization for the API used by the analysis infrastructure to create
/// an instance of the eviction advisor.
template <> Pass *callDefaultCtor<RegAllocEvictionAdvisorAnalysis>();
RegAllocEvictionAdvisorAnalysis *createReleaseModeAdvisor();
RegAllocEvictionAdvisorAnalysis *createDevelopmentModeAdvisor();
// TODO: move to RegAllocEvictionAdvisor.cpp when we move implementation
// out of RegAllocGreedy.cpp
class DefaultEvictionAdvisor : public RegAllocEvictionAdvisor {
public:
DefaultEvictionAdvisor(MachineFunction &MF, const RAGreedy &RA)
: RegAllocEvictionAdvisor(MF, RA) {}
private:
MCRegister tryFindEvictionCandidate(LiveInterval &, const AllocationOrder &,
uint8_t,
const SmallVirtRegSet &) const override;
bool canEvictHintInterference(LiveInterval &, MCRegister,
const SmallVirtRegSet &) const override;
bool canEvictInterferenceBasedOnCost(LiveInterval &, MCRegister, bool,
EvictionCost &,
const SmallVirtRegSet &) const;
bool shouldEvict(LiveInterval &A, bool, LiveInterval &B, bool) const;
};
} // namespace llvm
#endif // LLVM_CODEGEN_REGALLOCEVICTIONADVISOR_H
|
