LLVM 17.0.0git
MLRegallocEvictAdvisor.cpp
Go to the documentation of this file.
1//===- MLRegAllocEvictAdvisor.cpp - ML eviction advisor -------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// Implementation of the ML eviction advisor and reward injection pass
10//
11//===----------------------------------------------------------------------===//
12
13#include "AllocationOrder.h"
15#include "RegAllocGreedy.h"
19#if defined(LLVM_HAVE_TF_AOT_REGALLOCEVICTMODEL) || defined(LLVM_HAVE_TFLITE)
23#endif
32#include "llvm/CodeGen/Passes.h"
36#include "llvm/Pass.h"
37#include "llvm/PassRegistry.h"
40
41#include <array>
42#include <memory>
43
44using namespace llvm;
45
46#define DEBUG_TYPE "ml-regalloc"
47
48// Generated header in release (AOT) mode
49#if defined(LLVM_HAVE_TF_AOT_REGALLOCEVICTMODEL)
50#include "RegallocEvictModel.h"
51using CompiledModelType = RegallocEvictModel;
52#else
54#endif
55
57 "regalloc-evict-interactive-channel-base", cl::Hidden,
59 "Base file path for the interactive mode. The incoming filename should "
60 "have the name <regalloc-evict-interactive-channel-base>.in, while the "
61 "outgoing name should be "
62 "<regalloc-evict-interactive-channel-base>.out"));
63
64// Options that only make sense in development mode
65#ifdef LLVM_HAVE_TFLITE
66#include "RegAllocScore.h"
68
69static cl::opt<std::string> TrainingLog(
70 "regalloc-training-log", cl::Hidden,
71 cl::desc("Training log for the register allocator eviction model"));
72
73static cl::opt<std::string> ModelUnderTraining(
74 "regalloc-model", cl::Hidden,
75 cl::desc("The model being trained for register allocation eviction"));
76
78 "regalloc-enable-development-features", cl::Hidden,
79 cl::desc("Whether or not to enable features under development for the ML "
80 "regalloc advisor"));
81
82#else
83static const bool EnableDevelopmentFeatures = false;
84#endif // #ifdef LLVM_HAVE_TFLITE
85
86/// The score injection pass.
87/// This pass calculates the score for a function and inserts it in the log, but
88/// this happens only in development mode. It's a no-op otherwise.
89namespace llvm {
91
93public:
94 static char ID;
95
98 }
99
100 ~RegAllocScoring() override = default;
101
102 StringRef getPassName() const override {
103 return "Register Allocation Pass Scoring";
104 }
105
106 /// RegAllocReward analysis usage.
107 void getAnalysisUsage(AnalysisUsage &AU) const override {
108 AU.setPreservesAll();
113 }
114
115 /// Performs this pass
116 bool runOnMachineFunction(MachineFunction &) override;
117};
118
119char RegAllocScoring::ID = 0;
121
122} // namespace llvm
123
124INITIALIZE_PASS(RegAllocScoring, "regallocscoringpass",
125 "Register Allocation Scoring Pass", false, false)
126
127// ===================================
128// Common ML Advisor declarations
129// ===================================
130namespace {
131// The model can only accept a specified number of opcodes and will error it if
132// fed an opcode it hasn't seen before. This constant sets the current cutoff.
133static const int OpcodeValueCutoff = 17716;
134
135// Most features are as described above, so we'll reuse this vector in defining
136// them.
137static const std::vector<int64_t> PerLiveRangeShape{1, NumberOfInterferences};
138
139// --------------
140// Features table
141// --------------
142// For each interfering live range (incl. the candidate) we collect a number of
143// features. However, because the features are of different types (and because
144// of ML best practices), we organize the tensors per feature, not per
145// candidate. Each such tensor has a scalar value corresponding to the
146// interferring live range at that position, in the order in AllocationOrder.
147// The last position corresponds to the virt reg seeking allocation.
148// Exception to all that is the progression feature, which is just a scalar (see
149// its documentation for details).
150// Note on naming: the "_by_max" are normalized using the largest value of that
151// tensor, as observed in the current decision making stage (i.e. for the
152// current call to the advisor's tryFindEvictionCandidate)
153//
154// The feature list format: type, name, shape, documentation.
155// Note: we can really just use int64 and float, hence the modeling of some
156// bools as int64 values.
157#define RA_EVICT_FEATURES_LIST(M) \
158 M(int64_t, mask, PerLiveRangeShape, \
159 "boolean values, 0 for unavailable candidates (i.e. if a position is 0, " \
160 "it " \
161 "can't be evicted)") \
162 M(int64_t, is_free, PerLiveRangeShape, \
163 "boolean values, 1 if this phys reg is actually free (no interferences)") \
164 M(float, nr_urgent, PerLiveRangeShape, \
165 "number of 'urgent' intervals, normalized. Urgent are those that are OK " \
166 "to break cascades") \
167 M(float, nr_broken_hints, PerLiveRangeShape, \
168 "if this position were evicted, how many broken hints would there be") \
169 M(int64_t, is_hint, PerLiveRangeShape, \
170 "is this a preferred phys reg for the candidate") \
171 M(int64_t, is_local, PerLiveRangeShape, \
172 "is this live range local to a basic block") \
173 M(float, nr_rematerializable, PerLiveRangeShape, \
174 "nr rematerializable ranges") \
175 M(float, nr_defs_and_uses, PerLiveRangeShape, \
176 "bb freq - weighed nr defs and uses") \
177 M(float, weighed_reads_by_max, PerLiveRangeShape, \
178 "bb freq - weighed nr of reads, normalized") \
179 M(float, weighed_writes_by_max, PerLiveRangeShape, \
180 "bb feq - weighed nr of writes, normalized") \
181 M(float, weighed_read_writes_by_max, PerLiveRangeShape, \
182 "bb freq - weighed nr of uses that are both read and writes, normalized") \
183 M(float, weighed_indvars_by_max, PerLiveRangeShape, \
184 "bb freq - weighed nr of uses that are indvars, normalized") \
185 M(float, hint_weights_by_max, PerLiveRangeShape, \
186 "bb freq - weighed nr of uses that are hints, normalized") \
187 M(float, start_bb_freq_by_max, PerLiveRangeShape, \
188 "the freq in the start block, normalized") \
189 M(float, end_bb_freq_by_max, PerLiveRangeShape, \
190 "freq of end block, normalized") \
191 M(float, hottest_bb_freq_by_max, PerLiveRangeShape, \
192 "hottest BB freq, normalized") \
193 M(float, liverange_size, PerLiveRangeShape, \
194 "size (instr index diff) of the LR") \
195 M(float, use_def_density, PerLiveRangeShape, \
196 "the max weight, as computed by the manual heuristic") \
197 M(int64_t, max_stage, PerLiveRangeShape, \
198 "largest stage of an interval in this LR") \
199 M(int64_t, min_stage, PerLiveRangeShape, \
200 "lowest stage of an interval in this LR") \
201 M(float, progress, {1}, "ratio of current queue size to initial size")
202
203#ifdef LLVM_HAVE_TFLITE
204#define RA_EVICT_FIRST_DEVELOPMENT_FEATURE(M) \
205 M(int64_t, instructions, InstructionsShape, \
206 "Opcodes of the instructions covered by the eviction problem")
207
208#define RA_EVICT_REST_DEVELOPMENT_FEATURES(M) \
209 M(int64_t, instructions_mapping, InstructionsMappingShape, \
210 "A binary matrix mapping LRs to instruction opcodes") \
211 M(float, mbb_frequencies, MBBFrequencyShape, \
212 "A vector of machine basic block frequencies") \
213 M(int64_t, mbb_mapping, InstructionsShape, \
214 "A vector of indicies mapping instructions to MBBs")
215#else
216#define RA_EVICT_FIRST_DEVELOPMENT_FEATURE(M)
217#define RA_EVICT_REST_DEVELOPMENT_FEATURES(M)
218#endif
219
220// The model learns to pick one of the mask == 1 interferences. This is the
221// name of the output tensor. The contract with the model is that the output
222// will be guaranteed to be to a mask == 1 position. Using a macro here to
223// avoid 'not used' warnings (and keep cond compilation to a minimum)
224#define DecisionName "index_to_evict"
225static const TensorSpec DecisionSpec =
226 TensorSpec::createSpec<int64_t>(DecisionName, {1});
227
228// Named features index.
229enum FeatureIDs {
230#define _FEATURE_IDX_SIMPLE(_, name, __, ___) name
231#define _FEATURE_IDX(A, B, C, D) _FEATURE_IDX_SIMPLE(A, B, C, D),
233#ifdef LLVM_HAVE_TFLITE
235#else
237#endif // #ifdef LLVM_HAVE_TFLITE
238 RA_EVICT_REST_DEVELOPMENT_FEATURES(_FEATURE_IDX) FeaturesWithDevelopmentCount
239#undef _FEATURE_IDX
240#undef _FEATURE_IDX_SIMPLE
241};
242
243// The ML advisor will typically have a sparse input to the evaluator, because
244// various phys regs won't be available. It's easier (maintenance-wise) to
245// bulk-reset the state of the evaluator each time we are about to use it
246// again.
247template <typename T> size_t getTotalSize(const std::vector<int64_t> &Shape) {
248 size_t Ret = sizeof(T);
249 for (const auto V : Shape)
250 Ret *= V;
251 return Ret;
252}
253
254void resetInputs(MLModelRunner &Runner) {
255#define _RESET(TYPE, NAME, SHAPE, __) \
256 std::memset(Runner.getTensorUntyped(FeatureIDs::NAME), 0, \
257 getTotalSize<TYPE>(SHAPE));
262#undef _RESET
263 }
264}
265
266// Per-live interval components that get aggregated into the feature values
267// that will be passed to the evaluator.
268struct LIFeatureComponents {
269 double R = 0;
270 double W = 0;
271 double RW = 0;
272 double IndVarUpdates = 0;
273 double HintWeights = 0.0;
274 int64_t NrDefsAndUses = 0;
275 float HottestBlockFreq = 0.0;
276 bool IsRemat = false;
277};
278
279using CandidateRegList =
280 std::array<std::pair<MCRegister, bool>, NumberOfInterferences>;
281using FeaturesListNormalizer =
283
284/// The ML evictor (commonalities between release and development mode)
285class MLEvictAdvisor : public RegAllocEvictionAdvisor {
286public:
287 MLEvictAdvisor(const MachineFunction &MF, const RAGreedy &RA,
288 MLModelRunner *Runner, const MachineBlockFrequencyInfo &MBFI,
289 const MachineLoopInfo &Loops);
290
291protected:
292 const RegAllocEvictionAdvisor &getDefaultAdvisor() const {
293 return static_cast<const RegAllocEvictionAdvisor &>(DefaultAdvisor);
294 }
295
296 // The assumption is that if the Runner could not be constructed, we emit-ed
297 // error, and we shouldn't be asking for it here.
298 const MLModelRunner &getRunner() const { return *Runner; }
299
300 /// This just calls Evaluate on the Runner, but in the development mode
301 /// case, if we're just capturing the log of the default advisor, it needs
302 /// to call the latter instead, so we need to pass all the necessary
303 /// parameters for it. In the development case, it will also log.
304 virtual int64_t
305 tryFindEvictionCandidatePosition(const LiveInterval &VirtReg,
306 const AllocationOrder &Order,
307 unsigned OrderLimit, uint8_t CostPerUseLimit,
308 const SmallVirtRegSet &FixedRegisters) const;
309
310 /// Load the features of the given VirtReg (allocated or not) at column Pos,
311 /// but if that can't be evicted, return false instead.
312 bool
313 loadInterferenceFeatures(const LiveInterval &VirtReg, MCRegister PhysReg,
314 bool IsHint, const SmallVirtRegSet &FixedRegisters,
315 llvm::SmallVectorImpl<float> &Largest, size_t Pos,
316 SmallVectorImpl<LRStartEndInfo> &LRPosInfo) const;
317
318private:
319 static float getInitialQueueSize(const MachineFunction &MF);
320
322 const LiveInterval &VirtReg, const AllocationOrder &Order,
323 uint8_t CostPerUseLimit,
324 const SmallVirtRegSet &FixedRegisters) const override;
325
326 void extractFeatures(const SmallVectorImpl<const LiveInterval *> &Intervals,
327 llvm::SmallVectorImpl<float> &Largest, size_t Pos,
328 int64_t IsHint, int64_t LocalIntfsCount, float NrUrgent,
329 SmallVectorImpl<LRStartEndInfo> &LRPosInfo) const;
330
331 // Point-in-time: we didn't learn this, so we always delegate to the
332 // default.
334 const LiveInterval &VirtReg, MCRegister PhysReg,
335 const SmallVirtRegSet &FixedRegisters) const override {
336 return getDefaultAdvisor().canEvictHintInterference(VirtReg, PhysReg,
337 FixedRegisters);
338 }
339
340 const LIFeatureComponents &
341 getLIFeatureComponents(const LiveInterval &LI) const;
342
343 // Hold on to a default advisor for:
344 // 1) the implementation of canEvictHintInterference, because we didn't
345 // learn that nuance yet; 2) for bootstrapping (logging) in the development
346 // mode case.
347 const DefaultEvictionAdvisor DefaultAdvisor;
348 MLModelRunner *const Runner;
349 const MachineBlockFrequencyInfo &MBFI;
350 const MachineLoopInfo &Loops;
351
352 // Indices of those features we don't want to normalize.
353 // This could be static and shared, but its initialization is non-trivial.
354 std::bitset<FeatureIDs::FeatureCount> DoNotNormalize;
355 const float InitialQSize;
356
357 using RegID = unsigned;
358 mutable DenseMap<RegID, LIFeatureComponents> CachedFeatures;
359};
360
361#define _DECL_FEATURES(type, name, shape, _) \
362 TensorSpec::createSpec<type>(#name, shape),
363
364// ===================================
365// Release (AOT) - specifics
366// ===================================
367class ReleaseModeEvictionAdvisorAnalysis final
369public:
370 ReleaseModeEvictionAdvisorAnalysis()
371 : RegAllocEvictionAdvisorAnalysis(AdvisorMode::Release) {
376 } else {
378 }
379 }
380 // support for isa<> and dyn_cast.
381 static bool classof(const RegAllocEvictionAdvisorAnalysis *R) {
382 return R->getAdvisorMode() == AdvisorMode::Release;
383 }
384
385private:
386 std::vector<TensorSpec> InputFeatures;
387
388 void getAnalysisUsage(AnalysisUsage &AU) const override {
392 }
393
394 std::unique_ptr<RegAllocEvictionAdvisor>
395 getAdvisor(const MachineFunction &MF, const RAGreedy &RA) override {
396 if (!Runner) {
397 if (InteractiveChannelBaseName.empty())
398 Runner = std::make_unique<ReleaseModeModelRunner<CompiledModelType>>(
400 else
401 Runner = std::make_unique<InteractiveModelRunner>(
405 }
406 return std::make_unique<MLEvictAdvisor>(
407 MF, RA, Runner.get(), getAnalysis<MachineBlockFrequencyInfo>(),
408 getAnalysis<MachineLoopInfo>());
409 }
410 std::unique_ptr<MLModelRunner> Runner;
411};
412
413// ===================================
414// Development mode-specifics
415// ===================================
416//
417// Features we log
418#ifdef LLVM_HAVE_TFLITE
419static const TensorSpec Reward = TensorSpec::createSpec<float>("reward", {1});
420
421// Features we bind on the model. The tensor names have a prefix, and we also
422// need to include some tensors that are expected to be present by the
423// training algo.
424// TODO: can we just get rid of these?
425#define _DECL_TRAIN_FEATURES(type, name, shape, _) \
426 TensorSpec::createSpec<type>(std::string("action_") + #name, shape),
427
428class DevelopmentModeEvictAdvisor : public MLEvictAdvisor {
429public:
430 DevelopmentModeEvictAdvisor(const MachineFunction &MF, const RAGreedy &RA,
431 MLModelRunner *Runner,
432 const MachineBlockFrequencyInfo &MBFI,
433 const MachineLoopInfo &Loops, Logger *Log)
434 : MLEvictAdvisor(MF, RA, Runner, MBFI, Loops), Log(Log) {}
435
436private:
437 int64_t tryFindEvictionCandidatePosition(
438 const LiveInterval &VirtReg, const AllocationOrder &Order,
439 unsigned OrderLimit, uint8_t CostPerUseLimit,
440 const SmallVirtRegSet &FixedRegisters) const override;
441
442 Logger *const Log;
443};
444
445class DevelopmentModeEvictionAdvisorAnalysis final
447public:
448 DevelopmentModeEvictionAdvisorAnalysis()
449 : RegAllocEvictionAdvisorAnalysis(AdvisorMode::Development) {
454 TrainingInputFeatures = {
455 RA_EVICT_FEATURES_LIST(_DECL_TRAIN_FEATURES)
456 RA_EVICT_FIRST_DEVELOPMENT_FEATURE(_DECL_TRAIN_FEATURES)
457 RA_EVICT_REST_DEVELOPMENT_FEATURES(_DECL_TRAIN_FEATURES)
458 TensorSpec::createSpec<float>("action_discount", {1}),
459 TensorSpec::createSpec<int32_t>("action_step_type", {1}),
460 TensorSpec::createSpec<float>("action_reward", {1})};
461 } else {
463 TrainingInputFeatures = {
464 RA_EVICT_FEATURES_LIST(_DECL_TRAIN_FEATURES)
465 TensorSpec::createSpec<float>("action_discount", {1}),
466 TensorSpec::createSpec<int32_t>("action_step_type", {1}),
467 TensorSpec::createSpec<float>("action_reward", {1})};
468 }
469 }
470 // support for isa<> and dyn_cast.
471 static bool classof(const RegAllocEvictionAdvisorAnalysis *R) {
472 return R->getAdvisorMode() == AdvisorMode::Development;
473 }
474
475 void logRewardIfNeeded(const MachineFunction &MF,
476 llvm::function_ref<float()> GetReward) override {
477 if (!Log || !Log->hasAnyObservationForContext(MF.getName()))
478 return;
479 // The function pass manager would run all the function passes for a
480 // function, so we assume the last context belongs to this function. If
481 // this invariant ever changes, we can implement at that time switching
482 // contexts. At this point, it'd be an error
483 if (Log->currentContext() != MF.getName()) {
485 "The training log context shouldn't have had changed.");
486 }
487 if (Log->hasObservationInProgress())
488 Log->logReward<float>(GetReward());
489 }
490
491private:
492 std::vector<TensorSpec> InputFeatures;
493 std::vector<TensorSpec> TrainingInputFeatures;
494
495 void getAnalysisUsage(AnalysisUsage &AU) const override {
499 }
500
501 bool doInitialization(Module &M) override {
502 LLVMContext &Ctx = M.getContext();
503 if (ModelUnderTraining.empty() && TrainingLog.empty()) {
504 Ctx.emitError("Regalloc development mode should be requested with at "
505 "least logging enabled and/or a training model");
506 return false;
507 }
508 if (ModelUnderTraining.empty())
509 Runner = std::make_unique<NoInferenceModelRunner>(Ctx, InputFeatures);
510 else
511 Runner = ModelUnderTrainingRunner::createAndEnsureValid(
512 Ctx, ModelUnderTraining, DecisionName, TrainingInputFeatures);
513 if (!Runner) {
514 Ctx.emitError("Regalloc: could not set up the model runner");
515 return false;
516 }
517 if (TrainingLog.empty())
518 return false;
519 std::error_code EC;
520 auto OS = std::make_unique<raw_fd_ostream>(TrainingLog, EC);
521 if (EC) {
522 M.getContext().emitError(EC.message() + ":" + TrainingLog);
523 return false;
524 }
525 std::vector<TensorSpec> LFS = InputFeatures;
526 if (auto *MUTR = dyn_cast<ModelUnderTrainingRunner>(Runner.get()))
527 append_range(LFS, MUTR->extraOutputsForLoggingSpecs());
528 // We always log the output; in particular, if we're not evaluating, we
529 // don't have an output spec json file. That's why we handle the
530 // 'normal' output separately.
531 LFS.push_back(DecisionSpec);
532
533 Log = std::make_unique<Logger>(std::move(OS), LFS, Reward,
534 /*IncludeReward*/ true);
535 return false;
536 }
537
538 std::unique_ptr<RegAllocEvictionAdvisor>
539 getAdvisor(const MachineFunction &MF, const RAGreedy &RA) override {
540 if (!Runner)
541 return nullptr;
542 if (Log)
543 Log->switchContext(MF.getName());
544 return std::make_unique<DevelopmentModeEvictAdvisor>(
545 MF, RA, Runner.get(), getAnalysis<MachineBlockFrequencyInfo>(),
546 getAnalysis<MachineLoopInfo>(), Log.get());
547 }
548
549 std::unique_ptr<MLModelRunner> Runner;
550 std::unique_ptr<Logger> Log;
551};
552
553#endif //#ifdef LLVM_HAVE_TFLITE
554} // namespace
555
556float MLEvictAdvisor::getInitialQueueSize(const MachineFunction &MF) {
557 auto &MRI = MF.getRegInfo();
558 float Ret = 0.0;
559 for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
561 if (MRI.reg_nodbg_empty(Reg))
562 continue;
563 ++Ret;
564 }
565 return Ret;
566}
567
568MLEvictAdvisor::MLEvictAdvisor(const MachineFunction &MF, const RAGreedy &RA,
569 MLModelRunner *Runner,
570 const MachineBlockFrequencyInfo &MBFI,
571 const MachineLoopInfo &Loops)
572 : RegAllocEvictionAdvisor(MF, RA), DefaultAdvisor(MF, RA),
573 Runner(std::move(Runner)), MBFI(MBFI), Loops(Loops),
574 InitialQSize(MLEvictAdvisor::getInitialQueueSize(MF)) {
575 assert(this->Runner);
576 Runner->switchContext(MF.getName());
577 DoNotNormalize.set(FeatureIDs::mask);
578 DoNotNormalize.set(FeatureIDs::is_free);
579 DoNotNormalize.set(FeatureIDs::is_hint);
580 DoNotNormalize.set(FeatureIDs::is_local);
581 DoNotNormalize.set(FeatureIDs::min_stage);
582 DoNotNormalize.set(FeatureIDs::max_stage);
583 DoNotNormalize.set(FeatureIDs::progress);
584}
585
586int64_t MLEvictAdvisor::tryFindEvictionCandidatePosition(
587 const LiveInterval &, const AllocationOrder &, unsigned, uint8_t,
588 const SmallVirtRegSet &) const {
589 int64_t Ret = Runner->evaluate<int64_t>();
590 assert(Ret >= 0);
592 return Ret;
593}
594
595bool MLEvictAdvisor::loadInterferenceFeatures(
596 const LiveInterval &VirtReg, MCRegister PhysReg, bool IsHint,
597 const SmallVirtRegSet &FixedRegisters,
598 llvm::SmallVectorImpl<float> &Largest, size_t Pos,
599 llvm::SmallVectorImpl<LRStartEndInfo> &LRPosInfo) const {
600 // It is only possible to evict virtual register interference.
601 if (Matrix->checkInterference(VirtReg, PhysReg) > LiveRegMatrix::IK_VirtReg) {
602 // leave unavailable
603 return false;
604 }
605
606 const bool IsLocal = LIS->intervalIsInOneMBB(VirtReg);
607 int64_t LocalIntfs = 0;
608 float NrUrgent = 0.0f;
609
610 // The cascade tracking is the same as in the default advisor
611 unsigned Cascade = RA.getExtraInfo().getCascadeOrCurrentNext(VirtReg.reg());
612
614 for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
615 LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
616 // Different from the default heuristic, we don't make any assumptions
617 // about what having more than 10 results in the query may mean.
618 const auto &IFIntervals = Q.interferingVRegs(EvictInterferenceCutoff);
619 if (IFIntervals.empty() && InterferingIntervals.empty())
620 continue;
621 if (IFIntervals.size() >= EvictInterferenceCutoff)
622 return false;
623 InterferingIntervals.append(IFIntervals.begin(), IFIntervals.end());
624 for (const LiveInterval *Intf : reverse(IFIntervals)) {
625 assert(Intf->reg().isVirtual() &&
626 "Only expecting virtual register interference from query");
627 // This is the same set of legality checks as in the default case: don't
628 // try to evict fixed regs or 'done' ones. Also don't break cascades,
629 // except in the urgent case, with the same nuances used in the default
630 // heuristic.
631 // We could try sharing this between the advisors, but it may end up
632 // more complex than it is right now.
633 if (FixedRegisters.count(Intf->reg()))
634 return false;
635 if (RA.getExtraInfo().getStage(*Intf) == RS_Done)
636 return false;
637 bool Urgent =
638 !VirtReg.isSpillable() &&
639 (Intf->isSpillable() ||
640 RegClassInfo.getNumAllocatableRegs(MRI->getRegClass(VirtReg.reg())) <
641 RegClassInfo.getNumAllocatableRegs(
642 MRI->getRegClass(Intf->reg())));
643 // Only evict older cascades or live ranges without a cascade.
644 unsigned IntfCascade = RA.getExtraInfo().getCascade(Intf->reg());
645 if (Cascade <= IntfCascade) {
646 if (!Urgent)
647 return false;
648 ++NrUrgent;
649 }
650
651 LocalIntfs += (IsLocal && LIS->intervalIsInOneMBB(*Intf) &&
652 (!EnableLocalReassign || !canReassign(*Intf, PhysReg)));
653 }
654 }
655 // OK, so if we made it this far, this LR is an eviction candidate, load its
656 // features.
657 extractFeatures(InterferingIntervals, Largest, Pos, IsHint, LocalIntfs,
658 NrUrgent, LRPosInfo);
659 return true;
660}
661
662MCRegister MLEvictAdvisor::tryFindEvictionCandidate(
663 const LiveInterval &VirtReg, const AllocationOrder &Order,
664 uint8_t CostPerUseLimit, const SmallVirtRegSet &FixedRegisters) const {
665 auto MaybeOrderLimit = getOrderLimit(VirtReg, Order, CostPerUseLimit);
666 if (!MaybeOrderLimit)
668 unsigned OrderLimit = *MaybeOrderLimit;
669
670 // The heuristic sets initial costs such as, if CostPerUseLimit is
671 // max<uint8_t>, then any of the costs of the legally-evictable intervals
672 // would be lower. When that happens, one of those will be selected.
673 // Therefore, we allow the candidate be selected, unless the candidate is
674 // unspillable, in which case it would be incorrect to not find a register
675 // for it.
676 const bool MustFindEviction =
677 (!VirtReg.isSpillable() && CostPerUseLimit == static_cast<uint8_t>(~0u));
678 // Number of available candidates - if 0, no need to continue.
679 size_t Available = 0;
680 // Make sure we don't have leftover partial state from an attempt where we
681 // had no available candidates and bailed out early.
682 resetInputs(*Runner);
683
684 // Track the index->register mapping because AllocationOrder doesn't do that
685 // and we'd have to scan it.
686 // Also track their mask, to write asserts/debug.
687 CandidateRegList Regs;
688 Regs.fill({0, false});
689
690 // Track the largest value of features seen during this eviction session. We
691 // only normalize (some of) the float features, but it's just simpler to
692 // dimension 'Largest' to all the features, especially since we have the
693 // 'DoNotNormalize' list.
694 FeaturesListNormalizer Largest(FeatureIDs::FeatureCount, 0.0);
695
696 // Same overal idea as in the default eviction policy - we visit the values
697 // of AllocationOrder one at a time. If it's not legally available, we mask
698 // off the corresponding feature column (==do nothing because we already
699 // reset all the features to 0) Use Pos to capture the column we load
700 // features at - in AllocationOrder order.
701 size_t Pos = 0;
703 for (auto I = Order.begin(), E = Order.getOrderLimitEnd(OrderLimit); I != E;
704 ++I, ++Pos) {
705 MCRegister PhysReg = *I;
706 assert(!Regs[Pos].second);
707 assert(PhysReg);
708 if (!canAllocatePhysReg(CostPerUseLimit, PhysReg)) {
709 continue;
710 }
711 if (loadInterferenceFeatures(VirtReg, PhysReg, I.isHint(), FixedRegisters,
712 Largest, Pos, LRPosInfo)) {
713 ++Available;
714 Regs[Pos] = std::make_pair(PhysReg, true);
715 }
716 }
717 if (Available == 0) {
718 // Nothing to decide, nothing to learn.
719 assert(!MustFindEviction);
721 }
722 const size_t ValidPosLimit = Pos;
723 // If we must find eviction, the candidate should be masked out of the
724 // decision making process.
725 Regs[CandidateVirtRegPos].second = !MustFindEviction;
726 if (!MustFindEviction)
727 extractFeatures(SmallVector<const LiveInterval *, 1>(1, &VirtReg), Largest,
728 CandidateVirtRegPos, /*IsHint*/ 0,
729 /*LocalIntfsCount*/ 0,
730 /*NrUrgent*/ 0.0, LRPosInfo);
731 assert(InitialQSize > 0.0 && "We couldn't have gotten here if we had "
732 "nothing to allocate initially.");
733#ifdef LLVM_HAVE_TFLITE
736 LRPosInfo, Runner,
737 [this](SlotIndex InputIndex) -> int {
738 auto *CurrentMachineInstruction =
739 LIS->getInstructionFromIndex(InputIndex);
740 if (!CurrentMachineInstruction) {
741 return -1;
742 }
743 return CurrentMachineInstruction->getOpcode();
744 },
745 [this](SlotIndex InputIndex) -> float {
746 auto *CurrentMachineInstruction =
747 LIS->getInstructionFromIndex(InputIndex);
749 CurrentMachineInstruction->getParent());
750 },
751 [this](SlotIndex InputIndex) -> MachineBasicBlock * {
752 auto *CurrentMachineInstruction =
753 LIS->getInstructionFromIndex(InputIndex);
754 return CurrentMachineInstruction->getParent();
755 },
756 FeatureIDs::instructions, FeatureIDs::instructions_mapping,
757 FeatureIDs::mbb_frequencies, FeatureIDs::mbb_mapping,
758 LIS->getSlotIndexes()->getLastIndex());
759 }
760#endif // #ifdef LLVM_HAVE_TFLITE
761 // Normalize the features.
762 for (auto &V : Largest)
763 V = V ? V : 1.0;
764 for (size_t FeatureIndex = 0; FeatureIndex < FeatureIDs::FeatureCount;
765 ++FeatureIndex) {
766 if (DoNotNormalize.test(FeatureIndex))
767 continue;
768 for (size_t Pos = 0; Pos < NumberOfInterferences; ++Pos) {
769 Runner->getTensor<float>(FeatureIndex)[Pos] /= Largest[FeatureIndex];
770 }
771 }
772 *Runner->getTensor<float>(FeatureIDs::progress) =
773 static_cast<float>(RA.getQueueSize()) / InitialQSize;
774
775 // Get a decision.
776 size_t CandidatePos = tryFindEvictionCandidatePosition(
777 VirtReg, Order, OrderLimit, CostPerUseLimit, FixedRegisters);
778 // The contract with the ML side is that CandidatePos is mask == 1 (i.e.
779 // Regs[CandidatePos].second)
780 assert(Regs[CandidatePos].second);
781 if (CandidatePos == CandidateVirtRegPos) {
782 assert(!MustFindEviction);
784 }
785 assert(CandidatePos < ValidPosLimit);
786 (void)ValidPosLimit;
787 return Regs[CandidatePos].first;
788}
789
790const LIFeatureComponents &
791MLEvictAdvisor::getLIFeatureComponents(const LiveInterval &LI) const {
792 RegID ID = LI.reg().id();
793 LIFeatureComponents Empty;
794 auto I = CachedFeatures.insert(std::make_pair(ID, Empty));
795 LIFeatureComponents &Ret = I.first->getSecond();
796 if (!I.second)
797 return Ret;
798
801
803 I = MRI->reg_instr_nodbg_begin(LI.reg()),
804 E = MRI->reg_instr_nodbg_end();
805 I != E;) {
806 MachineInstr *MI = &*(I++);
807
808 ++Ret.NrDefsAndUses;
809 if (!Visited.insert(MI).second)
810 continue;
811
812 if (MI->isIdentityCopy() || MI->isImplicitDef())
813 continue;
814
815 bool Reads, Writes;
816 std::tie(Reads, Writes) = MI->readsWritesVirtualRegister(LI.reg());
817
818 float Freq = MBFI.getBlockFreqRelativeToEntryBlock(MI->getParent());
819 Ret.HottestBlockFreq = std::max(Freq, Ret.HottestBlockFreq);
820
821 Ret.R += (Reads && !Writes) * Freq;
822 Ret.W += (!Reads && Writes) * Freq;
823 Ret.RW += (Reads && Writes) * Freq;
824
825 auto *MBB = MI->getParent();
826 auto *Loop = Loops.getLoopFor(MBB);
827 bool IsExiting = Loop ? Loop->isLoopExiting(MBB) : false;
828
829 if (Writes && IsExiting && LIS->isLiveOutOfMBB(LI, MBB))
830 Ret.IndVarUpdates += Freq;
831
832 if (MI->isCopy() && VirtRegAuxInfo::copyHint(MI, LI.reg(), TRI, *MRI))
833 Ret.HintWeights += Freq;
834 }
836 LI, *LIS, *VRM, *MF.getSubtarget().getInstrInfo());
837 return Ret;
838}
839
840// Overall, this currently mimics what we do for weight calculation, but instead
841// of accummulating the various features, we keep them separate.
842void MLEvictAdvisor::extractFeatures(
844 llvm::SmallVectorImpl<float> &Largest, size_t Pos, int64_t IsHint,
845 int64_t LocalIntfsCount, float NrUrgent,
846 SmallVectorImpl<LRStartEndInfo> &LRPosInfo) const {
847 int64_t NrDefsAndUses = 0;
848 int64_t NrBrokenHints = 0;
849 double R = 0.0;
850 double W = 0.0;
851 double RW = 0.0;
852 double IndVarUpdates = 0.0;
853 double HintWeights = 0.0;
854 float StartBBFreq = 0.0;
855 float EndBBFreq = 0.0;
856 float HottestBlockFreq = 0.0;
857 int32_t NrRematerializable = 0;
858 float TotalWeight = 0.0;
859
860 SlotIndex EndSI = LIS->getSlotIndexes()->getZeroIndex();
861 SlotIndex StartSI = LIS->getSlotIndexes()->getLastIndex();
862 int64_t MaxStage = 0;
863 int64_t MinStage =
864 Intervals.empty() ? 0 : std::numeric_limits<int64_t>::max();
865
866 for (const auto *L : Intervals) {
867 const LiveInterval &LI = *L;
868 MaxStage = std::max<int64_t>(
869 MaxStage, static_cast<int64_t>(RA.getExtraInfo().getStage(LI)));
870 MinStage = std::min<int64_t>(
871 MinStage, static_cast<int64_t>(RA.getExtraInfo().getStage(LI)));
872
873 TotalWeight = std::max(TotalWeight, LI.weight());
874
875 if (LI.beginIndex() < StartSI)
876 StartSI = LI.beginIndex();
877
878 if (LI.endIndex() > EndSI)
879 EndSI = LI.endIndex();
880 const LIFeatureComponents &LIFC = getLIFeatureComponents(LI);
881 NrBrokenHints += VRM->hasPreferredPhys(LI.reg());
882
883 NrDefsAndUses += LIFC.NrDefsAndUses;
884 HottestBlockFreq = std::max(HottestBlockFreq, LIFC.HottestBlockFreq);
885 R += LIFC.R;
886 W += LIFC.W;
887 RW += LIFC.RW;
888
889 IndVarUpdates += LIFC.IndVarUpdates;
890
891 HintWeights += LIFC.HintWeights;
892 NrRematerializable += LIFC.IsRemat;
893
895 for (auto CurrentSegment : LI) {
896 LRPosInfo.push_back(
897 LRStartEndInfo{CurrentSegment.start, CurrentSegment.end, Pos});
898 }
899 }
900 }
901 size_t Size = 0;
902 if (!Intervals.empty()) {
903 StartBBFreq =
904 MBFI.getBlockFreqRelativeToEntryBlock(LIS->getMBBFromIndex(StartSI));
905 if (EndSI >= LIS->getSlotIndexes()->getLastIndex())
906 EndSI = LIS->getSlotIndexes()->getLastIndex().getPrevIndex();
907 EndBBFreq =
908 MBFI.getBlockFreqRelativeToEntryBlock(LIS->getMBBFromIndex(EndSI));
909 Size = StartSI.distance(EndSI);
910 }
911 // Set the features at the column 'Pos'.
912#define SET(ID, TYPE, VAL) \
913 do { \
914 Runner->getTensor<TYPE>(FeatureIDs::ID)[Pos] = static_cast<TYPE>(VAL); \
915 if (!DoNotNormalize.test(FeatureIDs::ID)) \
916 Largest[FeatureIDs::ID] = \
917 std::max(Largest[FeatureIDs::ID], static_cast<float>(VAL)); \
918 } while (false)
919 SET(mask, int64_t, 1);
920 SET(is_free, int64_t, Intervals.empty());
921 SET(nr_urgent, float, NrUrgent);
922 SET(nr_broken_hints, float, NrBrokenHints);
923 SET(is_hint, int64_t, IsHint);
924 SET(is_local, int64_t, LocalIntfsCount);
925 SET(nr_rematerializable, float, NrRematerializable);
926 SET(nr_defs_and_uses, float, NrDefsAndUses);
927 SET(weighed_reads_by_max, float, R);
928 SET(weighed_writes_by_max, float, W);
929 SET(weighed_read_writes_by_max, float, RW);
930 SET(weighed_indvars_by_max, float, IndVarUpdates);
931 SET(hint_weights_by_max, float, HintWeights);
932 SET(start_bb_freq_by_max, float, StartBBFreq);
933 SET(end_bb_freq_by_max, float, EndBBFreq);
934 SET(hottest_bb_freq_by_max, float, HottestBlockFreq);
935 SET(liverange_size, float, Size);
936 SET(use_def_density, float, TotalWeight);
937 SET(max_stage, int64_t, MaxStage);
938 SET(min_stage, int64_t, MinStage);
939#undef SET
940}
941
943 SmallVectorImpl<LRStartEndInfo> &LRPosInfo, MLModelRunner *RegallocRunner,
944 function_ref<int(SlotIndex)> GetOpcode,
945 function_ref<float(SlotIndex)> GetMBBFreq,
946 function_ref<MachineBasicBlock *(SlotIndex)> GetMBBReference,
947 const int InstructionsIndex, const int InstructionsMappingIndex,
948 const int MBBFreqIndex, const int MBBMappingIndex,
949 const SlotIndex LastIndex) {
950 // This function extracts instruction based features relevant to the eviction
951 // problem currently being solved. This function ends up extracting two
952 // tensors.
953 // 1 - A vector of size max instruction count. It contains the opcodes of the
954 // instructions spanned by all the intervals in the current instance of the
955 // eviction problem.
956 // 2 - A binary mapping matrix of size (LR count * max
957 // instruction count) which maps where the LRs are live to the actual opcodes
958 // for which they are live.
959 // 3 - A vector of size max supported MBB count storing MBB frequencies,
960 // encompassing all of the MBBs covered by the eviction problem.
961 // 4 - A vector of size max instruction count of indices to members of the MBB
962 // frequency vector, mapping each instruction to its associated MBB.
963
964 // Start off by sorting the segments based on the beginning slot index.
965 std::sort(
966 LRPosInfo.begin(), LRPosInfo.end(),
967 [](LRStartEndInfo A, LRStartEndInfo B) { return A.Begin < B.Begin; });
968 size_t InstructionIndex = 0;
969 size_t CurrentSegmentIndex = 0;
970 SlotIndex CurrentIndex = LRPosInfo[0].Begin;
971 std::map<MachineBasicBlock *, size_t> VisitedMBBs;
972 size_t CurrentMBBIndex = 0;
973 // This loop processes all the segments sequentially by starting at the
974 // beginning slot index of the first segment, iterating through all the slot
975 // indices before the end slot index of that segment (while checking for
976 // overlaps with segments that start at greater slot indices). After hitting
977 // that end index, the current segment being processed gets bumped until they
978 // are all processed or the max instruction count is hit, where everything is
979 // just truncated.
980 while (true) {
981 // If the index that we are currently at is within the current segment and
982 // we haven't hit the max instruction count, continue processing the current
983 // segment.
984 while (CurrentIndex <= LRPosInfo[CurrentSegmentIndex].End &&
985 InstructionIndex < ModelMaxSupportedInstructionCount) {
986 int CurrentOpcode = GetOpcode(CurrentIndex);
987 // If the current machine instruction is null, skip it
988 if (CurrentOpcode == -1) {
989 // If we're currently at the last index in the SlotIndex analysis,
990 // we can't go any further, so return from the function
991 if (CurrentIndex >= LastIndex) {
992 return;
993 }
994 CurrentIndex = CurrentIndex.getNextIndex();
995 continue;
996 }
997 MachineBasicBlock *CurrentMBBReference = GetMBBReference(CurrentIndex);
998 if (VisitedMBBs.count(CurrentMBBReference) == 0) {
999 VisitedMBBs[CurrentMBBReference] = CurrentMBBIndex;
1000 ++CurrentMBBIndex;
1001 }
1002 extractMBBFrequency(CurrentIndex, InstructionIndex, VisitedMBBs,
1003 GetMBBFreq, CurrentMBBReference, RegallocRunner,
1004 MBBFreqIndex, MBBMappingIndex);
1005 // Current code assumes we're not going to get any disjointed segments
1006 assert(LRPosInfo[CurrentSegmentIndex].Begin <= CurrentIndex);
1007 RegallocRunner->getTensor<int64_t>(InstructionsIndex)[InstructionIndex] =
1008 CurrentOpcode < OpcodeValueCutoff ? CurrentOpcode : 0;
1009 // set value in the binary mapping matrix for the current instruction
1010 auto CurrentSegmentPosition = LRPosInfo[CurrentSegmentIndex].Pos;
1011 RegallocRunner->getTensor<int64_t>(
1012 InstructionsMappingIndex)[CurrentSegmentPosition *
1014 InstructionIndex] = 1;
1015 // All of the segments are sorted based on the beginning slot index, but
1016 // this doesn't mean that the beginning slot index of the next segment is
1017 // after the end segment of the one being currently processed. This while
1018 // loop checks for overlapping segments and modifies the portion of the
1019 // column in the mapping matrix for the currently processed instruction
1020 // for the LR it is checking. Also make sure that the beginning of the
1021 // current segment we're checking for overlap in is less than the current
1022 // index, otherwise we're done checking overlaps.
1023 size_t OverlapCheckCurrentSegment = CurrentSegmentIndex + 1;
1024 while (OverlapCheckCurrentSegment < LRPosInfo.size() &&
1025 LRPosInfo[OverlapCheckCurrentSegment].Begin <= CurrentIndex) {
1026 auto OverlapCurrentSegmentPosition =
1027 LRPosInfo[OverlapCheckCurrentSegment].Pos;
1028 if (LRPosInfo[OverlapCheckCurrentSegment].End >= CurrentIndex) {
1029 RegallocRunner->getTensor<int64_t>(
1030 InstructionsMappingIndex)[OverlapCurrentSegmentPosition *
1032 InstructionIndex] = 1;
1033 }
1034 ++OverlapCheckCurrentSegment;
1035 }
1036 ++InstructionIndex;
1037 if (CurrentIndex >= LastIndex) {
1038 return;
1039 }
1040 CurrentIndex = CurrentIndex.getNextIndex();
1041 }
1042 // if we've just finished processing through the last segment or if we've
1043 // hit the maximum number of instructions, break out of the loop.
1044 if (CurrentSegmentIndex == LRPosInfo.size() - 1 ||
1045 InstructionIndex >= ModelMaxSupportedInstructionCount) {
1046 break;
1047 }
1048 // If the segments are not overlapping, we need to move to the beginning
1049 // index of the next segment to avoid having instructions not attached to
1050 // any register.
1051 if (LRPosInfo[CurrentSegmentIndex + 1].Begin >
1052 LRPosInfo[CurrentSegmentIndex].End) {
1053 CurrentIndex = LRPosInfo[CurrentSegmentIndex + 1].Begin;
1054 }
1055 ++CurrentSegmentIndex;
1056 }
1057}
1058
1059void extractMBBFrequency(const SlotIndex CurrentIndex,
1060 const size_t CurrentInstructionIndex,
1061 std::map<MachineBasicBlock *, size_t> &VisitedMBBs,
1062 function_ref<float(SlotIndex)> GetMBBFreq,
1063 MachineBasicBlock *CurrentMBBReference,
1064 MLModelRunner *RegallocRunner, const int MBBFreqIndex,
1065 const int MBBMappingIndex) {
1066 size_t CurrentMBBIndex = VisitedMBBs[CurrentMBBReference];
1067 float CurrentMBBFreq = GetMBBFreq(CurrentIndex);
1068 if (CurrentMBBIndex < ModelMaxSupportedMBBCount) {
1069 RegallocRunner->getTensor<float>(MBBFreqIndex)[CurrentMBBIndex] =
1070 CurrentMBBFreq;
1071 RegallocRunner->getTensor<int64_t>(
1072 MBBMappingIndex)[CurrentInstructionIndex] = CurrentMBBIndex;
1073 }
1074}
1075
1076// Development mode-specific implementations
1077#ifdef LLVM_HAVE_TFLITE
1078
1080 return new DevelopmentModeEvictionAdvisorAnalysis();
1081}
1082
1083int64_t DevelopmentModeEvictAdvisor::tryFindEvictionCandidatePosition(
1084 const LiveInterval &VirtReg, const AllocationOrder &Order,
1085 unsigned OrderLimit, uint8_t CostPerUseLimit,
1086 const SmallVirtRegSet &FixedRegisters) const {
1087 int64_t Ret = 0;
1088 if (isa<ModelUnderTrainingRunner>(getRunner())) {
1089 Ret = MLEvictAdvisor::tryFindEvictionCandidatePosition(
1090 VirtReg, Order, OrderLimit, CostPerUseLimit, FixedRegisters);
1091 } else {
1092 MCRegister PhysReg = getDefaultAdvisor().tryFindEvictionCandidate(
1093 VirtReg, Order, CostPerUseLimit, FixedRegisters);
1094 // Find the index of the selected PhysReg. We need it for logging,
1095 // otherwise this is wasted cycles (but so would starting development mode
1096 // without a model nor logging)
1097 if (!PhysReg)
1099 else
1100 for (auto I = Order.begin(), E = Order.getOrderLimitEnd(OrderLimit);
1101 I != E; ++I, ++Ret)
1102 if (*I == PhysReg)
1103 break;
1104 }
1105 if (TrainingLog.empty())
1106 return Ret;
1107 // TODO(mtrofin): when we support optional rewards, this can go away. In the
1108 // meantime, we log the "pretend" reward (0) for the previous observation
1109 // before starting a new one.
1110 if (Log->hasObservationInProgress())
1111 Log->logReward<float>(0.0);
1112
1113 Log->startObservation();
1114 size_t CurrentFeature = 0;
1116 ? FeatureIDs::FeaturesWithDevelopmentCount
1117 : FeatureIDs::FeatureCount;
1118 for (; CurrentFeature < FeatureCount; ++CurrentFeature) {
1119 Log->logTensorValue(CurrentFeature,
1120 reinterpret_cast<const char *>(
1121 getRunner().getTensorUntyped(CurrentFeature)));
1122 }
1123 if (auto *MUTR = dyn_cast<ModelUnderTrainingRunner>(&getRunner()))
1124 for (size_t I = 0; I < MUTR->extraOutputsForLoggingSpecs().size();
1125 ++I, ++CurrentFeature)
1126 Log->logTensorValue(
1127 CurrentFeature,
1128 reinterpret_cast<const char *>(MUTR->getUntypedExtraOutputValue(I)));
1129 // The output is right after the features and the extra outputs
1130 Log->logTensorValue(CurrentFeature, reinterpret_cast<const char *>(&Ret));
1131 Log->endObservation();
1132 return Ret;
1133}
1134
1136 std::optional<float> CachedReward;
1137 auto GetReward = [&]() {
1138 if (!CachedReward)
1139 CachedReward = static_cast<float>(
1140 calculateRegAllocScore(MF, getAnalysis<MachineBlockFrequencyInfo>())
1141 .getScore());
1142 return *CachedReward;
1143 };
1144
1145 getAnalysis<RegAllocEvictionAdvisorAnalysis>().logRewardIfNeeded(MF,
1146 GetReward);
1147 getAnalysis<RegAllocPriorityAdvisorAnalysis>().logRewardIfNeeded(MF,
1148 GetReward);
1149 return false;
1150}
1151#endif // #ifdef LLVM_HAVE_TFLITE
1152
1154 return llvm::isEmbeddedModelEvaluatorValid<CompiledModelType>() ||
1156 ? new ReleaseModeEvictionAdvisorAnalysis()
1157 : nullptr;
1158}
1159
1160// In all cases except development mode, we don't need scoring.
1161#if !defined(LLVM_HAVE_TFLITE)
1163#endif
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
uint64_t Size
bool End
Definition: ELF_riscv.cpp:464
SmallVector< uint32_t, 0 > Writes
Definition: ELF_riscv.cpp:481
@ Available
We know the block is fully available. This is a fixpoint.
Hexagon Hardware Loops
IRTranslator LLVM IR MI
Live Register Matrix
#define I(x, y, z)
Definition: MD5.cpp:58
static cl::opt< std::string > InteractiveChannelBaseName("inliner-interactive-channel-base", cl::Hidden, cl::desc("Base file path for the interactive mode. The incoming filename should " "have the name <inliner-interactive-channel-base>.in, while the " "outgoing name should be <inliner-interactive-channel-base>.out"))
static const bool EnableDevelopmentFeatures
void extractMBBFrequency(const SlotIndex CurrentIndex, const size_t CurrentInstructionIndex, std::map< MachineBasicBlock *, size_t > &VisitedMBBs, function_ref< float(SlotIndex)> GetMBBFreq, MachineBasicBlock *CurrentMBBReference, MLModelRunner *RegallocRunner, const int MBBFreqIndex, const int MBBMappingIndex)
#define RA_EVICT_FEATURES_LIST(M)
#define _FEATURE_IDX_SIMPLE(_, name, __, ___)
#define RA_EVICT_FIRST_DEVELOPMENT_FEATURE(M)
#define SET(ID, TYPE, VAL)
#define _RESET(TYPE, NAME, SHAPE, __)
#define RA_EVICT_REST_DEVELOPMENT_FEATURES(M)
void extractInstructionFeatures(SmallVectorImpl< LRStartEndInfo > &LRPosInfo, MLModelRunner *RegallocRunner, function_ref< int(SlotIndex)> GetOpcode, function_ref< float(SlotIndex)> GetMBBFreq, function_ref< MachineBasicBlock *(SlotIndex)> GetMBBReference, const int InstructionsIndex, const int InstructionsMappingIndex, const int MBBFreqIndex, const int MBBMappingIndex, const SlotIndex LastIndex)
static cl::opt< std::string > InteractiveChannelBaseName("regalloc-evict-interactive-channel-base", cl::Hidden, cl::desc("Base file path for the interactive mode. The incoming filename should " "have the name <regalloc-evict-interactive-channel-base>.in, while the " "outgoing name should be " "<regalloc-evict-interactive-channel-base>.out"))
#define _FEATURE_IDX(A, B, C, D)
#define _DECL_FEATURES(type, name, shape, _)
#define DecisionName
static const int ModelMaxSupportedInstructionCount
static const int64_t CandidateVirtRegPos
static const int64_t ModelMaxSupportedMBBCount
static const int64_t NumberOfInterferences
unsigned const TargetRegisterInfo * TRI
if(VerifyEach)
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI optimize exec mask operations pre RA
raw_pwrite_stream & OS
Iterator getOrderLimitEnd(unsigned OrderLimit) const
Iterator begin() const
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
void setPreservesAll()
Set by analyses that do not transform their input at all.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
Definition: Function.cpp:319
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
void emitError(uint64_t LocCookie, const Twine &ErrorStr)
emitError - Emit an error message to the currently installed error handler with optional location inf...
Query interferences between a single live virtual register and a live interval union.
const SmallVectorImpl< const LiveInterval * > & interferingVRegs(unsigned MaxInterferingRegs=std::numeric_limits< unsigned >::max())
LiveInterval - This class represents the liveness of a register, or stack slot.
Definition: LiveInterval.h:686
float weight() const
Definition: LiveInterval.h:718
Register reg() const
Definition: LiveInterval.h:717
bool isSpillable() const
isSpillable - Can this interval be spilled?
Definition: LiveInterval.h:819
SlotIndex beginIndex() const
beginIndex - Return the lowest numbered slot covered.
Definition: LiveInterval.h:385
SlotIndex endIndex() const
endNumber - return the maximum point of the range of the whole, exclusive.
Definition: LiveInterval.h:392
@ IK_VirtReg
Virtual register interference.
Definition: LiveRegMatrix.h:90
Logging utility - given an ordered specification of features, and assuming a scalar reward,...
bool isLoopExiting(const BlockT *BB) const
True if terminator in the block can branch to another block that is outside of the current loop.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:47
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
Wrapper class representing physical registers. Should be passed by value.
Definition: MCRegister.h:24
static constexpr unsigned NoRegister
Definition: MCRegister.h:43
MLModelRunner interface: abstraction of a mechanism for evaluating a tensorflow "saved model".
Definition: MLModelRunner.h:24
virtual void switchContext(StringRef Name)
Definition: MLModelRunner.h:52
T * getTensor(I FeatureID)
Definition: MLModelRunner.h:35
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
float getBlockFreqRelativeToEntryBlock(const MachineBasicBlock *MBB) const
Compute the frequency of the block, relative to the entry block.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
Representation of each machine instruction.
Definition: MachineInstr.h:68
defusechain_iterator - This class provides iterator support for machine operands in the function that...
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
A mock class satisfying the interface expected by ReleaseModeModelRunner for its TGen parameter.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual bool doInitialization(Module &)
doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...
Definition: Pass.h:119
ImmutableAnalysis abstraction for fetching the Eviction Advisor.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
virtual std::unique_ptr< RegAllocEvictionAdvisor > getAdvisor(const MachineFunction &MF, const RAGreedy &RA)=0
Get an advisor for the given context (i.e. machine function, etc)
virtual void logRewardIfNeeded(const MachineFunction &MF, llvm::function_ref< float()> GetReward)
virtual bool canEvictHintInterference(const LiveInterval &VirtReg, MCRegister PhysReg, const SmallVirtRegSet &FixedRegisters) const =0
Find out if we can evict the live ranges occupying the given PhysReg, which is a hint (preferred regi...
virtual MCRegister tryFindEvictionCandidate(const LiveInterval &VirtReg, const AllocationOrder &Order, uint8_t CostPerUseLimit, const SmallVirtRegSet &FixedRegisters) const =0
Find a physical register that can be freed by evicting the FixedRegisters, or return NoRegister.
double getScore() const
StringRef getPassName() const override
getPassName - Return a nice clean name for a pass.
void getAnalysisUsage(AnalysisUsage &AU) const override
RegAllocReward analysis usage.
~RegAllocScoring() override=default
bool runOnMachineFunction(MachineFunction &) override
Performs this pass.
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
static Register index2VirtReg(unsigned Index)
Convert a 0-based index to a virtual register number.
Definition: Register.h:84
unsigned id() const
Definition: Register.h:111
SlotIndex - An opaque wrapper around machine indexes.
Definition: SlotIndexes.h:82
SlotIndex getNextIndex() const
Returns the next index.
Definition: SlotIndexes.h:284
int distance(SlotIndex other) const
Return the distance from this index to the given one.
Definition: SlotIndexes.h:215
SlotIndex getPrevIndex() const
Returns the previous index.
Definition: SlotIndexes.h:304
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:135
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
Definition: SmallSet.h:166
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:577
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:687
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
virtual const TargetInstrInfo * getInstrInfo() const
static Register copyHint(const MachineInstr *MI, unsigned Reg, const TargetRegisterInfo &TRI, const MachineRegisterInfo &MRI)
Return the preferred allocation register for reg, given a COPY instruction.
static bool isRematerializable(const LiveInterval &LI, const LiveIntervals &LIS, const VirtRegMap &VRM, const TargetInstrInfo &TII)
Determine if all values in LI are rematerializable.
An efficient, type-erasing, non-owning reference to a callable.
Reg
All possible values of the reg field in the ModR/M byte.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:2129
static const TensorSpec DecisionSpec
RegAllocScore calculateRegAllocScore(const MachineFunction &MF, const MachineBlockFrequencyInfo &MBFI)
Calculate a score.
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:511
const char *const DecisionName
static const std::vector< TensorSpec > InputFeatures
@ RS_Done
There is nothing more we can do to this live range.
FunctionPass * createRegAllocScoringPass()
When learning an eviction policy, extract score(reward) information, otherwise this does nothing.
void initializeRegAllocScoringPass(PassRegistry &)
RegAllocEvictionAdvisorAnalysis * createReleaseModeAdvisor()
RegAllocEvictionAdvisorAnalysis * createDevelopmentModeAdvisor()
cl::opt< unsigned > EvictInterferenceCutoff
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1946
static const std::vector< int64_t > PerLiveRangeShape
Definition: BitVector.h:858