LLVM  16.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_TF_API)
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_TF_API
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_TF_API
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_TF_API
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_TF_API
224 #else
226 #endif // #ifdef LLVM_HAVE_TF_API
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_TF_API
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  /// get the logger for the given function, or nullptr if we didn't collect
460  /// one. This is used to inject the score by the RegAllocScoring pass.
461  Logger *getLogger(const MachineFunction &MF) const {
462  auto I = LogMap.find(MF.getName());
463  if (I == LogMap.end())
464  return nullptr;
465  return I->second.get();
466  }
467 
468  void logRewardIfNeeded(const MachineFunction &MF,
469  llvm::function_ref<float()> GetReward) override {
470  if (auto *Log = this->getLogger(MF))
471  Log->logFloatFinalReward(GetReward());
472  }
473 
474 private:
475  std::vector<TensorSpec> InputFeatures;
476  std::vector<TensorSpec> TrainingInputFeatures;
477 
478  void getAnalysisUsage(AnalysisUsage &AU) const override {
482  }
483 
484  // Save all the logs (when requested).
485  bool doFinalization(Module &M) override {
486  if (TrainingLog.empty())
487  return false;
488  std::error_code EC;
489  auto OS = std::make_unique<raw_fd_ostream>(TrainingLog, EC);
490  if (EC) {
491  M.getContext().emitError(EC.message() + ":" + TrainingLog);
492  return false;
493  }
494  Logger::flushLogs(*OS, LogMap);
495  return false;
496  }
497 
498  std::unique_ptr<RegAllocEvictionAdvisor>
499  getAdvisor(const MachineFunction &MF, const RAGreedy &RA) override {
500  LLVMContext &Ctx = MF.getFunction().getContext();
501  if (ModelUnderTraining.empty() && TrainingLog.empty()) {
502  Ctx.emitError("Regalloc development mode should be requested with at "
503  "least logging enabled and/or a training model");
504  return nullptr;
505  }
506  if (!Runner) {
507  if (ModelUnderTraining.empty())
508  Runner = std::make_unique<NoInferenceModelRunner>(Ctx, InputFeatures);
509  else
510  Runner = ModelUnderTrainingRunner::createAndEnsureValid(
511  Ctx, ModelUnderTraining, DecisionName, TrainingInputFeatures);
512  if (!Runner) {
513  Ctx.emitError("Regalloc: could not set up the model runner");
514  return nullptr;
515  }
516  }
517 
518  Logger *Log = nullptr;
519  if (!TrainingLog.empty()) {
520  std::vector<LoggedFeatureSpec> LFS;
521  for (const auto &FS : InputFeatures)
522  LFS.push_back({FS, None});
523  if (auto *MUTR = dyn_cast<ModelUnderTrainingRunner>(Runner.get()))
524  if (MUTR->outputLoggedFeatureSpecs().size() > 1)
525  append_range(LFS, drop_begin(MUTR->outputLoggedFeatureSpecs()));
526  // We always log the output; in particular, if we're not evaluating, we
527  // don't have an output spec json file. That's why we handle the
528  // 'normal' output separately.
529  LFS.push_back({Output, None});
530  auto I = LogMap.insert(std::make_pair(
531  MF.getFunction().getName(),
532  std::make_unique<Logger>(LFS, Reward, /*IncludeReward*/ true)));
533  assert(I.second);
534  Log = I.first->second.get();
535  }
536  return std::make_unique<DevelopmentModeEvictAdvisor>(
537  MF, RA, Runner.get(), getAnalysis<MachineBlockFrequencyInfo>(),
538  getAnalysis<MachineLoopInfo>(), Log);
539  }
540 
541  std::unique_ptr<MLModelRunner> Runner;
543 };
544 
545 #endif //#ifdef LLVM_HAVE_TF_API
546 } // namespace
547 
548 float MLEvictAdvisor::getInitialQueueSize(const MachineFunction &MF) {
549  auto &MRI = MF.getRegInfo();
550  float Ret = 0.0;
551  for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
553  if (MRI.reg_nodbg_empty(Reg))
554  continue;
555  ++Ret;
556  }
557  return Ret;
558 }
559 
560 MLEvictAdvisor::MLEvictAdvisor(const MachineFunction &MF, const RAGreedy &RA,
561  MLModelRunner *Runner,
562  const MachineBlockFrequencyInfo &MBFI,
563  const MachineLoopInfo &Loops)
564  : RegAllocEvictionAdvisor(MF, RA), DefaultAdvisor(MF, RA),
565  Runner(std::move(Runner)), MBFI(MBFI), Loops(Loops),
566  InitialQSize(MLEvictAdvisor::getInitialQueueSize(MF)) {
567  assert(this->Runner);
568  DoNotNormalize.set(FeatureIDs::mask);
569  DoNotNormalize.set(FeatureIDs::is_free);
570  DoNotNormalize.set(FeatureIDs::is_hint);
571  DoNotNormalize.set(FeatureIDs::is_local);
572  DoNotNormalize.set(FeatureIDs::min_stage);
573  DoNotNormalize.set(FeatureIDs::max_stage);
574  DoNotNormalize.set(FeatureIDs::progress);
575 }
576 
577 int64_t MLEvictAdvisor::tryFindEvictionCandidatePosition(
578  const LiveInterval &, const AllocationOrder &, unsigned, uint8_t,
579  const SmallVirtRegSet &) const {
580  int64_t Ret = Runner->evaluate<int64_t>();
581  assert(Ret >= 0);
583  return Ret;
584 }
585 
586 bool MLEvictAdvisor::loadInterferenceFeatures(
587  const LiveInterval &VirtReg, MCRegister PhysReg, bool IsHint,
588  const SmallVirtRegSet &FixedRegisters,
589  llvm::SmallVectorImpl<float> &Largest, size_t Pos,
590  llvm::SmallVectorImpl<LRStartEndInfo> &LRPosInfo) const {
591  // It is only possible to evict virtual register interference.
592  if (Matrix->checkInterference(VirtReg, PhysReg) > LiveRegMatrix::IK_VirtReg) {
593  // leave unavailable
594  return false;
595  }
596 
597  const bool IsLocal = LIS->intervalIsInOneMBB(VirtReg);
598  int64_t LocalIntfs = 0;
599  float NrUrgent = 0.0f;
600 
601  // The cascade tracking is the same as in the default advisor
602  unsigned Cascade = RA.getExtraInfo().getCascadeOrCurrentNext(VirtReg.reg());
603 
605  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
606  LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
607  // Different from the default heuristic, we don't make any assumptions
608  // about what having more than 10 results in the query may mean.
609  const auto &IFIntervals = Q.interferingVRegs(EvictInterferenceCutoff);
610  if (IFIntervals.empty() && InterferingIntervals.empty())
611  continue;
612  if (IFIntervals.size() >= EvictInterferenceCutoff)
613  return false;
614  InterferingIntervals.append(IFIntervals.begin(), IFIntervals.end());
615  for (const LiveInterval *Intf : reverse(IFIntervals)) {
616  assert(Register::isVirtualRegister(Intf->reg()) &&
617  "Only expecting virtual register interference from query");
618  // This is the same set of legality checks as in the default case: don't
619  // try to evict fixed regs or 'done' ones. Also don't break cascades,
620  // except in the urgent case, with the same nuances used in the default
621  // heuristic.
622  // We could try sharing this between the advisors, but it may end up
623  // more complex than it is right now.
624  if (FixedRegisters.count(Intf->reg()))
625  return false;
626  if (RA.getExtraInfo().getStage(*Intf) == RS_Done)
627  return false;
628  bool Urgent =
629  !VirtReg.isSpillable() &&
630  (Intf->isSpillable() ||
631  RegClassInfo.getNumAllocatableRegs(MRI->getRegClass(VirtReg.reg())) <
632  RegClassInfo.getNumAllocatableRegs(
633  MRI->getRegClass(Intf->reg())));
634  // Only evict older cascades or live ranges without a cascade.
635  unsigned IntfCascade = RA.getExtraInfo().getCascade(Intf->reg());
636  if (Cascade <= IntfCascade) {
637  if (!Urgent)
638  return false;
639  ++NrUrgent;
640  }
641 
642  LocalIntfs += (IsLocal && LIS->intervalIsInOneMBB(*Intf) &&
643  (!EnableLocalReassign || !canReassign(*Intf, PhysReg)));
644  }
645  }
646  // OK, so if we made it this far, this LR is an eviction candidate, load its
647  // features.
648  extractFeatures(InterferingIntervals, Largest, Pos, IsHint, LocalIntfs,
649  NrUrgent, LRPosInfo);
650  return true;
651 }
652 
653 MCRegister MLEvictAdvisor::tryFindEvictionCandidate(
654  const LiveInterval &VirtReg, const AllocationOrder &Order,
655  uint8_t CostPerUseLimit, const SmallVirtRegSet &FixedRegisters) const {
656  auto MaybeOrderLimit = getOrderLimit(VirtReg, Order, CostPerUseLimit);
657  if (!MaybeOrderLimit)
658  return MCRegister::NoRegister;
659  unsigned OrderLimit = *MaybeOrderLimit;
660 
661  // The heuristic sets initial costs such as, if CostPerUseLimit is
662  // max<uint8_t>, then any of the costs of the legally-evictable intervals
663  // would be lower. When that happens, one of those will be selected.
664  // Therefore, we allow the candidate be selected, unless the candidate is
665  // unspillable, in which case it would be incorrect to not find a register
666  // for it.
667  const bool MustFindEviction =
668  (!VirtReg.isSpillable() && CostPerUseLimit == static_cast<uint8_t>(~0u));
669  // Number of available candidates - if 0, no need to continue.
670  size_t Available = 0;
671  // Make sure we don't have leftover partial state from an attempt where we
672  // had no available candidates and bailed out early.
673  resetInputs(*Runner);
674 
675  // Track the index->register mapping because AllocationOrder doesn't do that
676  // and we'd have to scan it.
677  // Also track their mask, to write asserts/debug.
678  CandidateRegList Regs;
679  Regs.fill({0, false});
680 
681  // Track the largest value of features seen during this eviction session. We
682  // only normalize (some of) the float features, but it's just simpler to
683  // dimension 'Largest' to all the features, especially since we have the
684  // 'DoNotNormalize' list.
685  FeaturesListNormalizer Largest(FeatureIDs::FeatureCount, 0.0);
686 
687  // Same overal idea as in the default eviction policy - we visit the values
688  // of AllocationOrder one at a time. If it's not legally available, we mask
689  // off the corresponding feature column (==do nothing because we already
690  // reset all the features to 0) Use Pos to capture the column we load
691  // features at - in AllocationOrder order.
692  size_t Pos = 0;
694  for (auto I = Order.begin(), E = Order.getOrderLimitEnd(OrderLimit); I != E;
695  ++I, ++Pos) {
696  MCRegister PhysReg = *I;
697  assert(!Regs[Pos].second);
698  assert(PhysReg);
699  if (!canAllocatePhysReg(CostPerUseLimit, PhysReg)) {
700  continue;
701  }
702  if (loadInterferenceFeatures(VirtReg, PhysReg, I.isHint(), FixedRegisters,
703  Largest, Pos, LRPosInfo)) {
704  ++Available;
705  Regs[Pos] = std::make_pair(PhysReg, true);
706  }
707  }
708  if (Available == 0) {
709  // Nothing to decide, nothing to learn.
710  assert(!MustFindEviction);
711  return MCRegister::NoRegister;
712  }
713  const size_t ValidPosLimit = Pos;
714  // If we must find eviction, the candidate should be masked out of the
715  // decision making process.
716  Regs[CandidateVirtRegPos].second = !MustFindEviction;
717  if (!MustFindEviction)
718  extractFeatures(SmallVector<const LiveInterval *, 1>(1, &VirtReg), Largest,
719  CandidateVirtRegPos, /*IsHint*/ 0,
720  /*LocalIntfsCount*/ 0,
721  /*NrUrgent*/ 0.0, LRPosInfo);
722  assert(InitialQSize > 0.0 && "We couldn't have gotten here if we had "
723  "nothing to allocate initially.");
724 #ifdef LLVM_HAVE_TF_API
727  LRPosInfo, Runner,
728  [this](SlotIndex InputIndex) -> int {
729  auto *CurrentMachineInstruction =
730  LIS->getInstructionFromIndex(InputIndex);
731  if (!CurrentMachineInstruction) {
732  return -1;
733  }
734  return CurrentMachineInstruction->getOpcode();
735  },
736  [this](SlotIndex InputIndex) -> float {
737  auto *CurrentMachineInstruction =
738  LIS->getInstructionFromIndex(InputIndex);
740  CurrentMachineInstruction->getParent());
741  },
742  [this](SlotIndex InputIndex) -> MachineBasicBlock * {
743  auto *CurrentMachineInstruction =
744  LIS->getInstructionFromIndex(InputIndex);
745  return CurrentMachineInstruction->getParent();
746  },
747  FeatureIDs::instructions, FeatureIDs::instructions_mapping,
748  FeatureIDs::mbb_frequencies, FeatureIDs::mbb_mapping,
749  LIS->getSlotIndexes()->getLastIndex());
750  }
751 #endif // #ifdef LLVM_HAVE_TF_API
752  // Normalize the features.
753  for (auto &V : Largest)
754  V = V ? V : 1.0;
756  ++FeatureIndex) {
757  if (DoNotNormalize.test(FeatureIndex))
758  continue;
759  for (size_t Pos = 0; Pos < NumberOfInterferences; ++Pos) {
760  Runner->getTensor<float>(FeatureIndex)[Pos] /= Largest[FeatureIndex];
761  }
762  }
763  *Runner->getTensor<float>(FeatureIDs::progress) =
764  static_cast<float>(RA.getQueueSize()) / InitialQSize;
765 
766  // Get a decision.
767  size_t CandidatePos = tryFindEvictionCandidatePosition(
768  VirtReg, Order, OrderLimit, CostPerUseLimit, FixedRegisters);
769  // The contract with the ML side is that CandidatePos is mask == 1 (i.e.
770  // Regs[CandidatePos].second)
771  assert(Regs[CandidatePos].second);
772  if (CandidatePos == CandidateVirtRegPos) {
773  assert(!MustFindEviction);
774  return MCRegister::NoRegister;
775  }
776  assert(CandidatePos < ValidPosLimit);
777  (void)ValidPosLimit;
778  return Regs[CandidatePos].first;
779 }
780 
781 const LIFeatureComponents &
782 MLEvictAdvisor::getLIFeatureComponents(const LiveInterval &LI) const {
783  RegID ID = LI.reg().id();
784  LIFeatureComponents Empty;
785  auto I = CachedFeatures.insert(std::make_pair(ID, Empty));
786  LIFeatureComponents &Ret = I.first->getSecond();
787  if (!I.second)
788  return Ret;
789 
792 
794  I = MRI->reg_instr_nodbg_begin(LI.reg()),
796  I != E;) {
797  MachineInstr *MI = &*(I++);
798 
799  ++Ret.NrDefsAndUses;
800  if (!Visited.insert(MI).second)
801  continue;
802 
803  if (MI->isIdentityCopy() || MI->isImplicitDef())
804  continue;
805 
806  bool Reads, Writes;
807  std::tie(Reads, Writes) = MI->readsWritesVirtualRegister(LI.reg());
808 
809  float Freq = MBFI.getBlockFreqRelativeToEntryBlock(MI->getParent());
810  Ret.HottestBlockFreq = std::max(Freq, Ret.HottestBlockFreq);
811 
812  Ret.R += (Reads && !Writes) * Freq;
813  Ret.W += (!Reads && Writes) * Freq;
814  Ret.RW += (Reads && Writes) * Freq;
815 
816  auto *MBB = MI->getParent();
817  auto *Loop = Loops.getLoopFor(MBB);
818  bool IsExiting = Loop ? Loop->isLoopExiting(MBB) : false;
819 
820  if (Writes && IsExiting && LIS->isLiveOutOfMBB(LI, MBB))
821  Ret.IndVarUpdates += Freq;
822 
823  if (MI->isCopy() && VirtRegAuxInfo::copyHint(MI, LI.reg(), TRI, *MRI))
824  Ret.HintWeights += Freq;
825  }
826  Ret.IsRemat = VirtRegAuxInfo::isRematerializable(
827  LI, *LIS, *VRM, *MF.getSubtarget().getInstrInfo());
828  return Ret;
829 }
830 
831 // Overall, this currently mimics what we do for weight calculation, but instead
832 // of accummulating the various features, we keep them separate.
833 void MLEvictAdvisor::extractFeatures(
834  const SmallVectorImpl<const LiveInterval *> &Intervals,
835  llvm::SmallVectorImpl<float> &Largest, size_t Pos, int64_t IsHint,
836  int64_t LocalIntfsCount, float NrUrgent,
837  SmallVectorImpl<LRStartEndInfo> &LRPosInfo) const {
838  int64_t NrDefsAndUses = 0;
839  int64_t NrBrokenHints = 0;
840  double R = 0.0;
841  double W = 0.0;
842  double RW = 0.0;
843  double IndVarUpdates = 0.0;
844  double HintWeights = 0.0;
845  float StartBBFreq = 0.0;
846  float EndBBFreq = 0.0;
847  float HottestBlockFreq = 0.0;
848  int32_t NrRematerializable = 0;
849  float TotalWeight = 0.0;
850 
851  SlotIndex EndSI = LIS->getSlotIndexes()->getZeroIndex();
852  SlotIndex StartSI = LIS->getSlotIndexes()->getLastIndex();
853  int64_t MaxStage = 0;
854  int64_t MinStage =
855  Intervals.empty() ? 0 : std::numeric_limits<int64_t>::max();
856 
857  for (const auto *L : Intervals) {
858  const LiveInterval &LI = *L;
859  MaxStage = std::max<int64_t>(
860  MaxStage, static_cast<int64_t>(RA.getExtraInfo().getStage(LI)));
861  MinStage = std::min<int64_t>(
862  MinStage, static_cast<int64_t>(RA.getExtraInfo().getStage(LI)));
863 
864  TotalWeight = std::max(TotalWeight, LI.weight());
865 
866  if (LI.beginIndex() < StartSI)
867  StartSI = LI.beginIndex();
868 
869  if (LI.endIndex() > EndSI)
870  EndSI = LI.endIndex();
871  const LIFeatureComponents &LIFC = getLIFeatureComponents(LI);
872  NrBrokenHints += VRM->hasPreferredPhys(LI.reg());
873 
874  NrDefsAndUses += LIFC.NrDefsAndUses;
875  HottestBlockFreq = std::max(HottestBlockFreq, LIFC.HottestBlockFreq);
876  R += LIFC.R;
877  W += LIFC.W;
878  RW += LIFC.RW;
879 
880  IndVarUpdates += LIFC.IndVarUpdates;
881 
882  HintWeights += LIFC.HintWeights;
883  NrRematerializable += LIFC.IsRemat;
884 
886  for (auto CurrentSegment : LI) {
887  LRPosInfo.push_back(
888  LRStartEndInfo{CurrentSegment.start, CurrentSegment.end, Pos});
889  }
890  }
891  }
892  size_t Size = 0;
893  if (!Intervals.empty()) {
894  StartBBFreq =
895  MBFI.getBlockFreqRelativeToEntryBlock(LIS->getMBBFromIndex(StartSI));
896  if (EndSI >= LIS->getSlotIndexes()->getLastIndex())
897  EndSI = LIS->getSlotIndexes()->getLastIndex().getPrevIndex();
898  EndBBFreq =
899  MBFI.getBlockFreqRelativeToEntryBlock(LIS->getMBBFromIndex(EndSI));
900  Size = StartSI.distance(EndSI);
901  }
902  // Set the features at the column 'Pos'.
903 #define SET(ID, TYPE, VAL) \
904  do { \
905  Runner->getTensor<TYPE>(FeatureIDs::ID)[Pos] = static_cast<TYPE>(VAL); \
906  if (!DoNotNormalize.test(FeatureIDs::ID)) \
907  Largest[FeatureIDs::ID] = \
908  std::max(Largest[FeatureIDs::ID], static_cast<float>(VAL)); \
909  } while (false)
910  SET(mask, int64_t, 1);
911  SET(is_free, int64_t, Intervals.empty());
912  SET(nr_urgent, float, NrUrgent);
913  SET(nr_broken_hints, float, NrBrokenHints);
914  SET(is_hint, int64_t, IsHint);
915  SET(is_local, int64_t, LocalIntfsCount);
916  SET(nr_rematerializable, float, NrRematerializable);
917  SET(nr_defs_and_uses, float, NrDefsAndUses);
918  SET(weighed_reads_by_max, float, R);
919  SET(weighed_writes_by_max, float, W);
920  SET(weighed_read_writes_by_max, float, RW);
921  SET(weighed_indvars_by_max, float, IndVarUpdates);
922  SET(hint_weights_by_max, float, HintWeights);
923  SET(start_bb_freq_by_max, float, StartBBFreq);
924  SET(end_bb_freq_by_max, float, EndBBFreq);
925  SET(hottest_bb_freq_by_max, float, HottestBlockFreq);
926  SET(liverange_size, float, Size);
927  SET(use_def_density, float, TotalWeight);
928  SET(max_stage, int64_t, MaxStage);
929  SET(min_stage, int64_t, MinStage);
930 #undef SET
931 }
932 
934  SmallVectorImpl<LRStartEndInfo> &LRPosInfo, MLModelRunner *RegallocRunner,
935  function_ref<int(SlotIndex)> GetOpcode,
936  function_ref<float(SlotIndex)> GetMBBFreq,
937  function_ref<MachineBasicBlock *(SlotIndex)> GetMBBReference,
938  const int InstructionsIndex, const int InstructionsMappingIndex,
939  const int MBBFreqIndex, const int MBBMappingIndex,
940  const SlotIndex LastIndex) {
941  // This function extracts instruction based features relevant to the eviction
942  // problem currently being solved. This function ends up extracting two
943  // tensors.
944  // 1 - A vector of size max instruction count. It contains the opcodes of the
945  // instructions spanned by all the intervals in the current instance of the
946  // eviction problem.
947  // 2 - A binary mapping matrix of size (LR count * max
948  // instruction count) which maps where the LRs are live to the actual opcodes
949  // for which they are live.
950  // 3 - A vector of size max supported MBB count storing MBB frequencies,
951  // encompassing all of the MBBs covered by the eviction problem.
952  // 4 - A vector of size max instruction count of indices to members of the MBB
953  // frequency vector, mapping each instruction to its associated MBB.
954 
955  // Start off by sorting the segments based on the beginning slot index.
956  std::sort(
957  LRPosInfo.begin(), LRPosInfo.end(),
958  [](LRStartEndInfo A, LRStartEndInfo B) { return A.Begin < B.Begin; });
959  size_t InstructionIndex = 0;
960  size_t CurrentSegmentIndex = 0;
961  SlotIndex CurrentIndex = LRPosInfo[0].Begin;
962  std::map<MachineBasicBlock *, size_t> VisitedMBBs;
963  size_t CurrentMBBIndex = 0;
964  // This loop processes all the segments sequentially by starting at the
965  // beginning slot index of the first segment, iterating through all the slot
966  // indices before the end slot index of that segment (while checking for
967  // overlaps with segments that start at greater slot indices). After hitting
968  // that end index, the current segment being processed gets bumped until they
969  // are all processed or the max instruction count is hit, where everything is
970  // just truncated.
971  while (true) {
972  // If the index that we are currently at is within the current segment and
973  // we haven't hit the max instruction count, continue processing the current
974  // segment.
975  while (CurrentIndex <= LRPosInfo[CurrentSegmentIndex].End &&
976  InstructionIndex < ModelMaxSupportedInstructionCount) {
977  int CurrentOpcode = GetOpcode(CurrentIndex);
978  // If the current machine instruction is null, skip it
979  if (CurrentOpcode == -1) {
980  // If we're currently at the last index in the SlotIndex analysis,
981  // we can't go any further, so return from the function
982  if (CurrentIndex >= LastIndex) {
983  return;
984  }
985  CurrentIndex = CurrentIndex.getNextIndex();
986  continue;
987  }
988  MachineBasicBlock *CurrentMBBReference = GetMBBReference(CurrentIndex);
989  if (VisitedMBBs.count(CurrentMBBReference) == 0) {
990  VisitedMBBs[CurrentMBBReference] = CurrentMBBIndex;
991  ++CurrentMBBIndex;
992  }
993  extractMBBFrequency(CurrentIndex, InstructionIndex, VisitedMBBs,
994  GetMBBFreq, CurrentMBBReference, RegallocRunner,
995  MBBFreqIndex, MBBMappingIndex);
996  // Current code assumes we're not going to get any disjointed segments
997  assert(LRPosInfo[CurrentSegmentIndex].Begin <= CurrentIndex);
998  RegallocRunner->getTensor<int64_t>(InstructionsIndex)[InstructionIndex] =
999  CurrentOpcode < OpcodeValueCutoff ? CurrentOpcode : 0;
1000  // set value in the binary mapping matrix for the current instruction
1001  auto CurrentSegmentPosition = LRPosInfo[CurrentSegmentIndex].Pos;
1002  RegallocRunner->getTensor<int64_t>(
1003  InstructionsMappingIndex)[CurrentSegmentPosition *
1005  InstructionIndex] = 1;
1006  // All of the segments are sorted based on the beginning slot index, but
1007  // this doesn't mean that the beginning slot index of the next segment is
1008  // after the end segment of the one being currently processed. This while
1009  // loop checks for overlapping segments and modifies the portion of the
1010  // column in the mapping matrix for the currently processed instruction
1011  // for the LR it is checking. Also make sure that the beginning of the
1012  // current segment we're checking for overlap in is less than the current
1013  // index, otherwise we're done checking overlaps.
1014  size_t OverlapCheckCurrentSegment = CurrentSegmentIndex + 1;
1015  while (OverlapCheckCurrentSegment < LRPosInfo.size() &&
1016  LRPosInfo[OverlapCheckCurrentSegment].Begin <= CurrentIndex) {
1017  auto OverlapCurrentSegmentPosition =
1018  LRPosInfo[OverlapCheckCurrentSegment].Pos;
1019  if (LRPosInfo[OverlapCheckCurrentSegment].End >= CurrentIndex) {
1020  RegallocRunner->getTensor<int64_t>(
1021  InstructionsMappingIndex)[OverlapCurrentSegmentPosition *
1023  InstructionIndex] = 1;
1024  }
1025  ++OverlapCheckCurrentSegment;
1026  }
1027  ++InstructionIndex;
1028  if (CurrentIndex >= LastIndex) {
1029  return;
1030  }
1031  CurrentIndex = CurrentIndex.getNextIndex();
1032  }
1033  // if we've just finished processing through the last segment or if we've
1034  // hit the maximum number of instructions, break out of the loop.
1035  if (CurrentSegmentIndex == LRPosInfo.size() - 1 ||
1036  InstructionIndex >= ModelMaxSupportedInstructionCount) {
1037  break;
1038  }
1039  // If the segments are not overlapping, we need to move to the beginning
1040  // index of the next segment to avoid having instructions not attached to
1041  // any register.
1042  if (LRPosInfo[CurrentSegmentIndex + 1].Begin >
1043  LRPosInfo[CurrentSegmentIndex].End) {
1044  CurrentIndex = LRPosInfo[CurrentSegmentIndex + 1].Begin;
1045  }
1046  ++CurrentSegmentIndex;
1047  }
1048 }
1049 
1050 void extractMBBFrequency(const SlotIndex CurrentIndex,
1051  const size_t CurrentInstructionIndex,
1052  std::map<MachineBasicBlock *, size_t> &VisitedMBBs,
1053  function_ref<float(SlotIndex)> GetMBBFreq,
1054  MachineBasicBlock *CurrentMBBReference,
1055  MLModelRunner *RegallocRunner, const int MBBFreqIndex,
1056  const int MBBMappingIndex) {
1057  size_t CurrentMBBIndex = VisitedMBBs[CurrentMBBReference];
1058  float CurrentMBBFreq = GetMBBFreq(CurrentIndex);
1059  if (CurrentMBBIndex < ModelMaxSupportedMBBCount) {
1060  RegallocRunner->getTensor<float>(MBBFreqIndex)[CurrentMBBIndex] =
1061  CurrentMBBFreq;
1062  RegallocRunner->getTensor<int64_t>(
1063  MBBMappingIndex)[CurrentInstructionIndex] = CurrentMBBIndex;
1064  }
1065 }
1066 
1067 // Development mode-specific implementations
1068 #ifdef LLVM_HAVE_TF_API
1069 
1071  return new DevelopmentModeEvictionAdvisorAnalysis();
1072 }
1073 
1074 int64_t DevelopmentModeEvictAdvisor::tryFindEvictionCandidatePosition(
1075  const LiveInterval &VirtReg, const AllocationOrder &Order,
1076  unsigned OrderLimit, uint8_t CostPerUseLimit,
1077  const SmallVirtRegSet &FixedRegisters) const {
1078  int64_t Ret = 0;
1079  if (isa<ModelUnderTrainingRunner>(getRunner())) {
1080  Ret = MLEvictAdvisor::tryFindEvictionCandidatePosition(
1081  VirtReg, Order, OrderLimit, CostPerUseLimit, FixedRegisters);
1082  } else {
1083  MCRegister PhysReg = getDefaultAdvisor().tryFindEvictionCandidate(
1084  VirtReg, Order, CostPerUseLimit, FixedRegisters);
1085  // Find the index of the selected PhysReg. We need it for logging,
1086  // otherwise this is wasted cycles (but so would starting development mode
1087  // without a model nor logging)
1088  if (!PhysReg)
1090  else
1091  for (auto I = Order.begin(), E = Order.getOrderLimitEnd(OrderLimit);
1092  I != E; ++I, ++Ret)
1093  if (*I == PhysReg)
1094  break;
1095  }
1096  if (TrainingLog.empty())
1097  return Ret;
1098  size_t CurrentFeature = 0;
1100  ? FeatureIDs::FeaturesWithDevelopmentCount
1102  for (; CurrentFeature < FeatureCount; ++CurrentFeature) {
1103  Log->logSpecifiedTensorValue(
1104  CurrentFeature, reinterpret_cast<const char *>(
1105  getRunner().getTensorUntyped(CurrentFeature)));
1106  }
1107  if (auto *MUTR = dyn_cast<ModelUnderTrainingRunner>(&getRunner()))
1108  for (size_t I = 1; I < MUTR->outputLoggedFeatureSpecs().size();
1109  ++I, ++CurrentFeature)
1110  Log->logSpecifiedTensorValue(
1111  CurrentFeature,
1112  reinterpret_cast<const char *>(
1113  MUTR->lastEvaluationResult()->getUntypedTensorValue(I)));
1114  // The output is right after the features and the extra outputs
1115  Log->logInt64Value(CurrentFeature, &Ret);
1116  return Ret;
1117 }
1118 
1119 bool RegAllocScoring::runOnMachineFunction(MachineFunction &MF) {
1120  Optional<float> CachedReward;
1121  auto GetReward = [&]() {
1122  if (!CachedReward)
1123  CachedReward = static_cast<float>(
1124  calculateRegAllocScore(MF, getAnalysis<MachineBlockFrequencyInfo>())
1125  .getScore());
1126  return *CachedReward;
1127  };
1128 
1129  getAnalysis<RegAllocEvictionAdvisorAnalysis>().logRewardIfNeeded(MF,
1130  GetReward);
1131  getAnalysis<RegAllocPriorityAdvisorAnalysis>().logRewardIfNeeded(MF,
1132  GetReward);
1133  return false;
1134 }
1135 #endif // #ifdef LLVM_HAVE_TF_API
1136 
1138  return new ReleaseModeEvictionAdvisorAnalysis();
1139 }
1140 
1141 // In all cases except development mode, we don't need scoring.
1142 #if !defined(LLVM_HAVE_TF_API)
1144 #endif
llvm::Check::Size
@ Size
Definition: FileCheck.h:77
LiveRegMatrix.h
NoInferenceModelRunner.h
TFUtils.h
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:108
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::drop_begin
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:387
llvm::RegAllocEvictionAdvisorAnalysis
ImmutableAnalysis abstraction for fetching the Eviction Advisor.
Definition: RegAllocEvictionAdvisor.h:168
AllocationOrder.h
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:75
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:266
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:277
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:140
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:237
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:321
llvm::X86AS::FS
@ FS
Definition: X86.h:200
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:136
llvm::Optional
Definition: APInt.h:33
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::MachineRegisterInfo::getNumVirtRegs
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
Definition: MachineRegisterInfo.h:770
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:265
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:667
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:71
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:357
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:186
llvm::RegAllocScoring::runOnMachineFunction
bool runOnMachineFunction(MachineFunction &) override
Performs this pass.
Definition: MLRegallocEvictAdvisor.cpp:1143
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::StringMap
StringMap - This is an unconventional map that is specialized for handling keys that are "strings",...
Definition: StringMap.h:110
llvm::MachineRegisterInfo::getRegClass
const TargetRegisterClass * getRegClass(Register Reg) const
Return the register class of the specified virtual register.
Definition: MachineRegisterInfo.h:647
llvm::sort
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1682
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:657
llvm::cl::opt
Definition: CommandLine.h:1412
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:165
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
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:354
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:567
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:1861
llvm::FeatureIndex
FeatureIndex
Definition: InlineModelFeatureMaps.h:109
llvm::MachineBasicBlock::getParent
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
Definition: MachineBasicBlock.h:261
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:257
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:2013
llvm::RegAllocEvictionAdvisor
Definition: RegAllocEvictionAdvisor.h:99
llvm::LiveIntervalUnion::Query::interferingVRegs
const SmallVectorImpl< const LiveInterval * > & interferingVRegs(unsigned MaxInterferingRegs=std::numeric_limits< unsigned >::max())
Definition: LiveIntervalUnion.h:162
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
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:1137
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::DefaultEvictionAdvisor
Definition: RegAllocEvictionAdvisor.h:205
std
Definition: BitVector.h:851
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:623
llvm::None
constexpr std::nullopt_t None
Definition: None.h:27
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:62
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
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:1050
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:485
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:413
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:385
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:53
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:933
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 &)