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 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299
|
//===- RegAllocEvictionAdvisor.cpp - eviction advisor ---------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// Implementation of the default eviction advisor and of the Analysis pass.
//
//===----------------------------------------------------------------------===//
#include "RegAllocEvictionAdvisor.h"
#include "RegAllocGreedy.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/RegisterClassInfo.h"
#include "llvm/CodeGen/VirtRegMap.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/PassRegistry.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Target/TargetMachine.h"
using namespace llvm;
static cl::opt<RegAllocEvictionAdvisorAnalysis::AdvisorMode> Mode(
"regalloc-enable-advisor", cl::Hidden, cl::ZeroOrMore,
cl::init(RegAllocEvictionAdvisorAnalysis::AdvisorMode::Default),
cl::desc("Enable regalloc advisor mode"),
cl::values(
clEnumValN(RegAllocEvictionAdvisorAnalysis::AdvisorMode::Default,
"default", "Default"),
clEnumValN(RegAllocEvictionAdvisorAnalysis::AdvisorMode::Release,
"release", "precompiled"),
clEnumValN(RegAllocEvictionAdvisorAnalysis::AdvisorMode::Development,
"development", "for training")));
static cl::opt<bool> EnableLocalReassignment(
"enable-local-reassign", cl::Hidden,
cl::desc("Local reassignment can yield better allocation decisions, but "
"may be compile time intensive"),
cl::init(false));
#define DEBUG_TYPE "regalloc"
#ifdef LLVM_HAVE_TF_AOT_REGALLOCEVICTMODEL
#define LLVM_HAVE_TF_AOT
#endif
char RegAllocEvictionAdvisorAnalysis::ID = 0;
INITIALIZE_PASS(RegAllocEvictionAdvisorAnalysis, "regalloc-evict",
"Regalloc eviction policy", false, true)
namespace {
class DefaultEvictionAdvisorAnalysis final
: public RegAllocEvictionAdvisorAnalysis {
public:
DefaultEvictionAdvisorAnalysis(bool NotAsRequested)
: RegAllocEvictionAdvisorAnalysis(AdvisorMode::Default),
NotAsRequested(NotAsRequested) {}
// support for isa<> and dyn_cast.
static bool classof(const RegAllocEvictionAdvisorAnalysis *R) {
return R->getAdvisorMode() == AdvisorMode::Default;
}
private:
std::unique_ptr<RegAllocEvictionAdvisor>
getAdvisor(MachineFunction &MF, const RAGreedy &RA) override {
return std::make_unique<DefaultEvictionAdvisor>(MF, RA);
}
bool doInitialization(Module &M) override {
if (NotAsRequested)
M.getContext().emitError("Requested regalloc eviction advisor analysis "
"could be created. Using default");
return RegAllocEvictionAdvisorAnalysis::doInitialization(M);
}
const bool NotAsRequested;
};
} // namespace
template <> Pass *llvm::callDefaultCtor<RegAllocEvictionAdvisorAnalysis>() {
Pass *Ret = nullptr;
switch (Mode) {
case RegAllocEvictionAdvisorAnalysis::AdvisorMode::Default:
Ret = new DefaultEvictionAdvisorAnalysis(/*NotAsRequested*/ false);
break;
case RegAllocEvictionAdvisorAnalysis::AdvisorMode::Development:
#if defined(LLVM_HAVE_TF_API)
Ret = createDevelopmentModeAdvisor();
#endif
break;
case RegAllocEvictionAdvisorAnalysis::AdvisorMode::Release:
#if defined(LLVM_HAVE_TF_AOT)
Ret = createReleaseModeAdvisor();
#endif
break;
}
if (Ret)
return Ret;
return new DefaultEvictionAdvisorAnalysis(/*NotAsRequested*/ true);
}
StringRef RegAllocEvictionAdvisorAnalysis::getPassName() const {
switch (getAdvisorMode()) {
case AdvisorMode::Default:
return "Default Regalloc Eviction Advisor";
case AdvisorMode::Release:
return "Release mode Regalloc Eviction Advisor";
case AdvisorMode::Development:
return "Development mode Regalloc Eviction Advisor";
}
llvm_unreachable("Unknown advisor kind");
}
RegAllocEvictionAdvisor::RegAllocEvictionAdvisor(MachineFunction &MF,
const RAGreedy &RA)
: MF(MF), RA(RA), Matrix(RA.getInterferenceMatrix()),
LIS(RA.getLiveIntervals()), VRM(RA.getVirtRegMap()),
MRI(&VRM->getRegInfo()), TRI(MF.getSubtarget().getRegisterInfo()),
RegClassInfo(RA.getRegClassInfo()), RegCosts(TRI->getRegisterCosts(MF)),
EnableLocalReassign(EnableLocalReassignment ||
MF.getSubtarget().enableRALocalReassignment(
MF.getTarget().getOptLevel())) {}
/// shouldEvict - determine if A should evict the assigned live range B. The
/// eviction policy defined by this function together with the allocation order
/// defined by enqueue() decides which registers ultimately end up being split
/// and spilled.
///
/// Cascade numbers are used to prevent infinite loops if this function is a
/// cyclic relation.
///
/// @param A The live range to be assigned.
/// @param IsHint True when A is about to be assigned to its preferred
/// register.
/// @param B The live range to be evicted.
/// @param BreaksHint True when B is already assigned to its preferred register.
bool DefaultEvictionAdvisor::shouldEvict(LiveInterval &A, bool IsHint,
LiveInterval &B,
bool BreaksHint) const {
bool CanSplit = RA.getExtraInfo().getStage(B) < RS_Spill;
// Be fairly aggressive about following hints as long as the evictee can be
// split.
if (CanSplit && IsHint && !BreaksHint)
return true;
if (A.weight() > B.weight()) {
LLVM_DEBUG(dbgs() << "should evict: " << B << " w= " << B.weight() << '\n');
return true;
}
return false;
}
/// canEvictHintInterference - return true if the interference for VirtReg
/// on the PhysReg, which is VirtReg's hint, can be evicted in favor of VirtReg.
bool DefaultEvictionAdvisor::canEvictHintInterference(
LiveInterval &VirtReg, MCRegister PhysReg,
const SmallVirtRegSet &FixedRegisters) const {
EvictionCost MaxCost;
MaxCost.setBrokenHints(1);
return canEvictInterferenceBasedOnCost(VirtReg, PhysReg, true, MaxCost,
FixedRegisters);
}
/// canEvictInterferenceBasedOnCost - Return true if all interferences between
/// VirtReg and PhysReg can be evicted.
///
/// @param VirtReg Live range that is about to be assigned.
/// @param PhysReg Desired register for assignment.
/// @param IsHint True when PhysReg is VirtReg's preferred register.
/// @param MaxCost Only look for cheaper candidates and update with new cost
/// when returning true.
/// @returns True when interference can be evicted cheaper than MaxCost.
bool DefaultEvictionAdvisor::canEvictInterferenceBasedOnCost(
LiveInterval &VirtReg, MCRegister PhysReg, bool IsHint,
EvictionCost &MaxCost, const SmallVirtRegSet &FixedRegisters) const {
// It is only possible to evict virtual register interference.
if (Matrix->checkInterference(VirtReg, PhysReg) > LiveRegMatrix::IK_VirtReg)
return false;
bool IsLocal = VirtReg.empty() || LIS->intervalIsInOneMBB(VirtReg);
// Find VirtReg's cascade number. This will be unassigned if VirtReg was never
// involved in an eviction before. If a cascade number was assigned, deny
// evicting anything with the same or a newer cascade number. This prevents
// infinite eviction loops.
//
// This works out so a register without a cascade number is allowed to evict
// anything, and it can be evicted by anything.
unsigned Cascade = RA.getExtraInfo().getCascadeOrCurrentNext(VirtReg.reg());
EvictionCost Cost;
for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
// If there is 10 or more interferences, chances are one is heavier.
const auto &Interferences = Q.interferingVRegs(10);
if (Interferences.size() >= 10)
return false;
// Check if any interfering live range is heavier than MaxWeight.
for (LiveInterval *Intf : reverse(Interferences)) {
assert(Register::isVirtualRegister(Intf->reg()) &&
"Only expecting virtual register interference from query");
// Do not allow eviction of a virtual register if we are in the middle
// of last-chance recoloring and this virtual register is one that we
// have scavenged a physical register for.
if (FixedRegisters.count(Intf->reg()))
return false;
// Never evict spill products. They cannot split or spill.
if (RA.getExtraInfo().getStage(*Intf) == RS_Done)
return false;
// Once a live range becomes small enough, it is urgent that we find a
// register for it. This is indicated by an infinite spill weight. These
// urgent live ranges get to evict almost anything.
//
// Also allow urgent evictions of unspillable ranges from a strictly
// larger allocation order.
bool Urgent =
!VirtReg.isSpillable() &&
(Intf->isSpillable() ||
RegClassInfo.getNumAllocatableRegs(MRI->getRegClass(VirtReg.reg())) <
RegClassInfo.getNumAllocatableRegs(
MRI->getRegClass(Intf->reg())));
// Only evict older cascades or live ranges without a cascade.
unsigned IntfCascade = RA.getExtraInfo().getCascade(Intf->reg());
if (Cascade <= IntfCascade) {
if (!Urgent)
return false;
// We permit breaking cascades for urgent evictions. It should be the
// last resort, though, so make it really expensive.
Cost.BrokenHints += 10;
}
// Would this break a satisfied hint?
bool BreaksHint = VRM->hasPreferredPhys(Intf->reg());
// Update eviction cost.
Cost.BrokenHints += BreaksHint;
Cost.MaxWeight = std::max(Cost.MaxWeight, Intf->weight());
// Abort if this would be too expensive.
if (!(Cost < MaxCost))
return false;
if (Urgent)
continue;
// Apply the eviction policy for non-urgent evictions.
if (!shouldEvict(VirtReg, IsHint, *Intf, BreaksHint))
return false;
// If !MaxCost.isMax(), then we're just looking for a cheap register.
// Evicting another local live range in this case could lead to suboptimal
// coloring.
if (!MaxCost.isMax() && IsLocal && LIS->intervalIsInOneMBB(*Intf) &&
(!EnableLocalReassign || !canReassign(*Intf, PhysReg))) {
return false;
}
}
}
MaxCost = Cost;
return true;
}
MCRegister DefaultEvictionAdvisor::tryFindEvictionCandidate(
LiveInterval &VirtReg, const AllocationOrder &Order,
uint8_t CostPerUseLimit, const SmallVirtRegSet &FixedRegisters) const {
// Keep track of the cheapest interference seen so far.
EvictionCost BestCost;
BestCost.setMax();
MCRegister BestPhys;
auto MaybeOrderLimit = getOrderLimit(VirtReg, Order, CostPerUseLimit);
if (!MaybeOrderLimit)
return MCRegister::NoRegister;
unsigned OrderLimit = *MaybeOrderLimit;
// When we are just looking for a reduced cost per use, don't break any
// hints, and only evict smaller spill weights.
if (CostPerUseLimit < uint8_t(~0u)) {
BestCost.BrokenHints = 0;
BestCost.MaxWeight = VirtReg.weight();
}
for (auto I = Order.begin(), E = Order.getOrderLimitEnd(OrderLimit); I != E;
++I) {
MCRegister PhysReg = *I;
assert(PhysReg);
if (!canAllocatePhysReg(CostPerUseLimit, PhysReg) ||
!canEvictInterferenceBasedOnCost(VirtReg, PhysReg, false, BestCost,
FixedRegisters))
continue;
// Best so far.
BestPhys = PhysReg;
// Stop if the hint can be used.
if (I.isHint())
break;
}
return BestPhys;
}
|