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