LLVM  15.0.0git
MLRegallocEvictAdvisor.cpp
Go to the documentation of this file.
1 //===- MLRegAllocEvictAdvisor.cpp - ML eviction advisor -------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Implementation of the ML eviction advisor and reward injection pass
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "AllocationOrder.h"
15 #include "RegAllocGreedy.h"
19 #if defined(LLVM_HAVE_TF_AOT_REGALLOCEVICTMODEL) || defined(LLVM_HAVE_TF_API)
22 #endif
30 #include "llvm/CodeGen/Passes.h"
33 #include "llvm/InitializePasses.h"
34 #include "llvm/Pass.h"
35 #include "llvm/PassRegistry.h"
38 
39 #include <array>
40 #include <memory>
41 
42 using namespace llvm;
43 
44 #define DEBUG_TYPE "ml-regalloc"
45 
46 // Generated header in release (AOT) mode
47 #if defined(LLVM_HAVE_TF_AOT_REGALLOCEVICTMODEL)
48 #include "RegallocEvictModel.h"
49 using CompiledModelType = RegallocEvictModel;
50 #else
52 #endif
53 
54 // Options that only make sense in development mode
55 #ifdef LLVM_HAVE_TF_API
56 #include "RegAllocScore.h"
58 
59 static cl::opt<std::string> TrainingLog(
60  "regalloc-training-log", cl::Hidden,
61  cl::desc("Training log for the register allocator eviction model"));
62 
63 static cl::opt<std::string> ModelUnderTraining(
64  "regalloc-model", cl::Hidden,
65  cl::desc("The model being trained for register allocation eviction"));
66 
67 #endif // #ifdef LLVM_HAVE_TF_API
68 
70 
71 /// The score injection pass.
72 /// This pass calculates the score for a function and inserts it in the log, but
73 /// this happens only in development mode. It's a no-op otherwise.
74 namespace llvm {
76 public:
77  static char ID;
78 
81  }
82 
83  ~RegAllocScoring() override = default;
84 
85  StringRef getPassName() const override {
86  return "Register Allocation Pass Scoring";
87  }
88 
89  /// RegAllocReward analysis usage.
90  void getAnalysisUsage(AnalysisUsage &AU) const override {
91  AU.setPreservesAll();
96  }
97 
98  /// Performs this pass
99  bool runOnMachineFunction(MachineFunction &) override;
100 };
101 
102 char RegAllocScoring::ID = 0;
104 
105 } // namespace llvm
106 
107 INITIALIZE_PASS(RegAllocScoring, "regallocscoringpass",
108  "Register Allocation Scoring Pass", false, false)
109 
110 // ===================================
111 // Common ML Advisor declarations
112 // ===================================
113 namespace {
114 // This is the maximum number of interfererring ranges. That's the number of
115 // distinct AllocationOrder values, which comes from MCRegisterClass::RegsSize.
116 // For X86, that's 32.
117 // TODO: find a way to get this, statically, in a programmatic way.
118 static const int64_t MaxInterferences = 32;
119 
120 // Logically, we can think of the feature set given to the evaluator as a 2D
121 // matrix. The rows are the features (see next). The columns correspond to the
122 // interferences. We treat the candidate virt reg as an 'interference', too, as
123 // its feature set is the same as that of the interferring ranges. So we'll have
124 // MaxInterferences + 1 columns and by convention, we will use the last column
125 // for the virt reg seeking allocation.
126 static const int64_t CandidateVirtRegPos = MaxInterferences;
127 static const int64_t NumberOfInterferences = CandidateVirtRegPos + 1;
128 
129 // Most features are as described above, so we'll reuse this vector in defining
130 // them.
131 static const std::vector<int64_t> PerLiveRangeShape{1, NumberOfInterferences};
132 
133 // --------------
134 // Features table
135 // --------------
136 // For each interfering live range (incl. the candidate) we collect a number of
137 // features. However, because the features are of different types (and because
138 // of ML best practices), we organize the tensors per feature, not per
139 // candidate. Each such tensor has a scalar value corresponding to the
140 // interferring live range at that position, in the order in AllocationOrder.
141 // The last position corresponds to the virt reg seeking allocation.
142 // Exception to all that is the progression feature, which is just a scalar (see
143 // its documentation for details).
144 // Note on naming: the "_by_max" are normalized using the largest value of that
145 // tensor, as observed in the current decision making stage (i.e. for the
146 // current call to the advisor's tryFindEvictionCandidate)
147 //
148 // The feature list format: type, name, shape, documentation.
149 // Note: we can really just use int64 and float, hence the modeling of some
150 // bools as int64 values.
151 #define RA_EVICT_FEATURES_LIST(M) \
152  M(int64_t, mask, PerLiveRangeShape, \
153  "boolean values, 0 for unavailable candidates (i.e. if a position is 0, " \
154  "it " \
155  "can't be evicted)") \
156  M(int64_t, is_free, PerLiveRangeShape, \
157  "boolean values, 1 if this phys reg is actually free (no interferences)") \
158  M(float, nr_urgent, PerLiveRangeShape, \
159  "number of 'urgent' intervals, normalized. Urgent are those that are OK " \
160  "to break cascades") \
161  M(float, nr_broken_hints, PerLiveRangeShape, \
162  "if this position were evicted, how many broken hints would there be") \
163  M(int64_t, is_hint, PerLiveRangeShape, \
164  "is this a preferred phys reg for the candidate") \
165  M(int64_t, is_local, PerLiveRangeShape, \
166  "is this live range local to a basic block") \
167  M(float, nr_rematerializable, PerLiveRangeShape, \
168  "nr rematerializable ranges") \
169  M(float, nr_defs_and_uses, PerLiveRangeShape, \
170  "bb freq - weighed nr defs and uses") \
171  M(float, weighed_reads_by_max, PerLiveRangeShape, \
172  "bb freq - weighed nr of reads, normalized") \
173  M(float, weighed_writes_by_max, PerLiveRangeShape, \
174  "bb feq - weighed nr of writes, normalized") \
175  M(float, weighed_read_writes_by_max, PerLiveRangeShape, \
176  "bb freq - weighed nr of uses that are both read and writes, normalized") \
177  M(float, weighed_indvars_by_max, PerLiveRangeShape, \
178  "bb freq - weighed nr of uses that are indvars, normalized") \
179  M(float, hint_weights_by_max, PerLiveRangeShape, \
180  "bb freq - weighed nr of uses that are hints, normalized") \
181  M(float, start_bb_freq_by_max, PerLiveRangeShape, \
182  "the freq in the start block, normalized") \
183  M(float, end_bb_freq_by_max, PerLiveRangeShape, \
184  "freq of end block, normalized") \
185  M(float, hottest_bb_freq_by_max, PerLiveRangeShape, \
186  "hottest BB freq, normalized") \
187  M(float, liverange_size, PerLiveRangeShape, \
188  "size (instr index diff) of the LR") \
189  M(float, use_def_density, PerLiveRangeShape, \
190  "the max weight, as computed by the manual heuristic") \
191  M(int64_t, max_stage, PerLiveRangeShape, \
192  "largest stage of an interval in this LR") \
193  M(int64_t, min_stage, PerLiveRangeShape, \
194  "lowest stage of an interval in this LR") \
195  M(float, progress, {1}, "ratio of current queue size to initial size")
196 
197 // The model learns to pick one of the mask == 1 interferences. This is the name
198 // of the output tensor.
199 // The contract with the model is that the output will be guaranteed to be to a
200 // mask == 1 position.
201 // Using a macro here to avoid 'not used' warnings (and keep cond compilation to
202 // a minimum)
203 #define DecisionName "index_to_evict"
204 
205 // Named features index.
206 enum FeatureIDs {
207 #define _FEATURE_IDX(_, name, __, ___) name,
209 #undef _FEATURE_IDX
210  FeatureCount
211 };
212 
213 // The ML advisor will typically have a sparse input to the evaluator, because
214 // various phys regs won't be available. It's easier (maintenance-wise) to
215 // bulk-reset the state of the evaluator each time we are about to use it again.
216 template <typename T> size_t getTotalSize(const std::vector<int64_t> &Shape) {
217  size_t Ret = sizeof(T);
218  for (const auto V : Shape)
219  Ret *= V;
220  return Ret;
221 }
222 
223 void resetInputs(MLModelRunner &Runner) {
224 #define _RESET(TYPE, NAME, SHAPE, __) \
225  std::memset(Runner.getTensorUntyped(FeatureIDs::NAME), 0, \
226  getTotalSize<TYPE>(SHAPE));
228 #undef _RESET
229 }
230 
231 // Per-live interval components that get aggregated into the feature values that
232 // will be passed to the evaluator.
233 struct LIFeatureComponents {
234  double R = 0;
235  double W = 0;
236  double RW = 0;
237  double IndVarUpdates = 0;
238  double HintWeights = 0.0;
239  int64_t NrDefsAndUses = 0;
240  float HottestBlockFreq = 0.0;
241  bool IsRemat = false;
242 };
243 
244 using CandidateRegList =
245  std::array<std::pair<MCRegister, bool>, NumberOfInterferences>;
246 using FeaturesListNormalizer = std::array<float, FeatureIDs::FeatureCount>;
247 
248 /// The ML evictor (commonalities between release and development mode)
249 class MLEvictAdvisor : public RegAllocEvictionAdvisor {
250 public:
251  MLEvictAdvisor(const MachineFunction &MF, const RAGreedy &RA,
252  MLModelRunner *Runner, const MachineBlockFrequencyInfo &MBFI,
253  const MachineLoopInfo &Loops);
254 
255 protected:
256  const RegAllocEvictionAdvisor &getDefaultAdvisor() const {
257  return static_cast<const RegAllocEvictionAdvisor &>(DefaultAdvisor);
258  }
259 
260  // The assumption is that if the Runner could not be constructed, we emit-ed
261  // error, and we shouldn't be asking for it here.
262  const MLModelRunner &getRunner() const { return *Runner; }
263 
264  /// This just calls Evaluate on the Runner, but in the development mode case,
265  /// if we're just capturing the log of the default advisor, it needs to call
266  /// the latter instead, so we need to pass all the necessary parameters for
267  /// it. In the development case, it will also log.
268  virtual int64_t
269  tryFindEvictionCandidatePosition(const LiveInterval &VirtReg,
270  const AllocationOrder &Order,
271  unsigned OrderLimit, uint8_t CostPerUseLimit,
272  const SmallVirtRegSet &FixedRegisters) const;
273 
274  /// Load the features of the given VirtReg (allocated or not) at column Pos,
275  /// but if that can't be evicted, return false instead.
276  bool
277  loadInterferenceFeatures(const LiveInterval &VirtReg, MCRegister PhysReg,
278  bool IsHint, const SmallVirtRegSet &FixedRegisters,
279  std::array<float, FeatureIDs::FeatureCount> &Largest,
280  size_t Pos) const;
281 
282 private:
283  static float getInitialQueueSize(const MachineFunction &MF);
284 
285  MCRegister tryFindEvictionCandidate(
286  const LiveInterval &VirtReg, const AllocationOrder &Order,
287  uint8_t CostPerUseLimit,
288  const SmallVirtRegSet &FixedRegisters) const override;
289 
290  void extractFeatures(const SmallVectorImpl<const LiveInterval *> &Intervals,
291  std::array<float, FeatureIDs::FeatureCount> &Largest,
292  size_t Pos, int64_t IsHint, int64_t LocalIntfsCount,
293  float NrUrgent) const;
294 
295  // Point-in-time: we didn't learn this, so we always delegate to the default.
296  bool canEvictHintInterference(
297  const LiveInterval &VirtReg, MCRegister PhysReg,
298  const SmallVirtRegSet &FixedRegisters) const override {
299  return getDefaultAdvisor().canEvictHintInterference(VirtReg, PhysReg,
300  FixedRegisters);
301  }
302 
303  const LIFeatureComponents &
304  getLIFeatureComponents(const LiveInterval &LI) const;
305 
306  // Hold on to a default advisor for:
307  // 1) the implementation of canEvictHintInterference, because we didn't learn
308  // that nuance yet;
309  // 2) for bootstrapping (logging) in the development mode case.
310  const DefaultEvictionAdvisor DefaultAdvisor;
311  MLModelRunner *const Runner;
312  const MachineBlockFrequencyInfo &MBFI;
313  const MachineLoopInfo &Loops;
314 
315  // Indices of those features we don't want to normalize.
316  // This could be static and shared, but its initialization is non-trivial.
317  std::bitset<FeatureIDs::FeatureCount> DoNotNormalize;
318  const float InitialQSize;
319 
320  using RegID = unsigned;
321  mutable DenseMap<RegID, LIFeatureComponents> CachedFeatures;
322 };
323 
324 #define _DECL_FEATURES(type, name, shape, _) \
325  TensorSpec::createSpec<type>(#name, shape),
326 
327 static const std::vector<TensorSpec> InputFeatures{
329 };
330 #undef _DECL_FEATURES
331 // ===================================
332 // Release (AOT) - specifics
333 // ===================================
334 class ReleaseModeEvictionAdvisorAnalysis final
336 public:
337  ReleaseModeEvictionAdvisorAnalysis()
338  : RegAllocEvictionAdvisorAnalysis(AdvisorMode::Release) {}
339  // support for isa<> and dyn_cast.
340  static bool classof(const RegAllocEvictionAdvisorAnalysis *R) {
341  return R->getAdvisorMode() == AdvisorMode::Release;
342  }
343 
344 private:
345  void getAnalysisUsage(AnalysisUsage &AU) const override {
349  }
350 
351  std::unique_ptr<RegAllocEvictionAdvisor>
352  getAdvisor(const MachineFunction &MF, const RAGreedy &RA) override {
353  if (!Runner)
354  Runner = std::make_unique<ReleaseModeModelRunner<CompiledModelType>>(
355  MF.getFunction().getContext(), InputFeatures, DecisionName);
356  return std::make_unique<MLEvictAdvisor>(
357  MF, RA, Runner.get(), getAnalysis<MachineBlockFrequencyInfo>(),
358  getAnalysis<MachineLoopInfo>());
359  }
360  std::unique_ptr<ReleaseModeModelRunner<CompiledModelType>> Runner;
361 };
362 
363 // ===================================
364 // Development mode-specifics
365 // ===================================
366 //
367 // Features we log
368 #ifdef LLVM_HAVE_TF_API
369 static const TensorSpec Output =
370  TensorSpec::createSpec<int64_t>(DecisionName, {1});
371 static const TensorSpec Reward = TensorSpec::createSpec<float>("reward", {1});
372 
373 // Features we bind on the model. The tensor names have a prefix, and we also
374 // need to include some tensors that are expected to be present by the training
375 // algo.
376 // TODO: can we just get rid of these?
377 #define _DECL_TRAIN_FEATURES(type, name, shape, _) \
378  TensorSpec::createSpec<type>(std::string("action_") + #name, shape),
379 
380 static const std::vector<TensorSpec> TrainingInputFeatures{
381  {RA_EVICT_FEATURES_LIST(_DECL_TRAIN_FEATURES)
382  TensorSpec::createSpec<float>("action_discount", {1}),
383  TensorSpec::createSpec<int32_t>("action_step_type", {1}),
384  TensorSpec::createSpec<float>("action_reward", {1})}};
385 #undef _DECL_TRAIN_FEATURES
386 
387 class DevelopmentModeEvictAdvisor : public MLEvictAdvisor {
388 public:
389  DevelopmentModeEvictAdvisor(const MachineFunction &MF, const RAGreedy &RA,
390  MLModelRunner *Runner,
391  const MachineBlockFrequencyInfo &MBFI,
392  const MachineLoopInfo &Loops, Logger *Log)
393  : MLEvictAdvisor(MF, RA, Runner, MBFI, Loops), Log(Log) {}
394 
395 private:
396  int64_t tryFindEvictionCandidatePosition(
397  const LiveInterval &VirtReg, const AllocationOrder &Order,
398  unsigned OrderLimit, uint8_t CostPerUseLimit,
399  const SmallVirtRegSet &FixedRegisters) const override;
400 
401  Logger *const Log;
402 };
403 
404 class DevelopmentModeEvictionAdvisorAnalysis final
406 public:
407  DevelopmentModeEvictionAdvisorAnalysis()
408  : RegAllocEvictionAdvisorAnalysis(AdvisorMode::Development) {}
409  // support for isa<> and dyn_cast.
410  static bool classof(const RegAllocEvictionAdvisorAnalysis *R) {
411  return R->getAdvisorMode() == AdvisorMode::Development;
412  }
413 
414  /// get the logger for the given function, or nullptr if we didn't collect
415  /// one. This is used to inject the score by the RegAllocScoring pass.
416  Logger *getLogger(const MachineFunction &MF) const {
417  auto I = LogMap.find(MF.getName());
418  if (I == LogMap.end())
419  return nullptr;
420  return I->second.get();
421  }
422 
423 private:
424  void getAnalysisUsage(AnalysisUsage &AU) const override {
428  }
429 
430  // Save all the logs (when requested).
431  bool doFinalization(Module &M) override {
432  if (TrainingLog.empty())
433  return false;
434  std::error_code EC;
435  auto OS = std::make_unique<raw_fd_ostream>(TrainingLog, EC);
436  if (EC) {
437  M.getContext().emitError(EC.message() + ":" + TrainingLog);
438  return false;
439  }
440  Logger::flushLogs(*OS, LogMap);
441  return false;
442  }
443 
444  std::unique_ptr<RegAllocEvictionAdvisor>
445  getAdvisor(const MachineFunction &MF, const RAGreedy &RA) override {
446  LLVMContext &Ctx = MF.getFunction().getContext();
447  if (ModelUnderTraining.empty() && TrainingLog.empty()) {
448  Ctx.emitError("Regalloc development mode should be requested with at "
449  "least logging enabled and/or a training model");
450  return nullptr;
451  }
452  if (!Runner) {
453  if (ModelUnderTraining.empty())
454  Runner = std::make_unique<NoInferenceModelRunner>(Ctx, InputFeatures);
455  else
456  Runner = ModelUnderTrainingRunner::createAndEnsureValid(
457  Ctx, ModelUnderTraining, DecisionName, TrainingInputFeatures);
458  if (!Runner) {
459  Ctx.emitError("Regalloc: could not set up the model runner");
460  return nullptr;
461  }
462  }
463 
464  Logger *Log = nullptr;
465  if (!TrainingLog.empty()) {
466  std::vector<LoggedFeatureSpec> LFS;
467  for (const auto &FS : InputFeatures)
468  LFS.push_back({FS, None});
469  if (auto *MUTR = dyn_cast<ModelUnderTrainingRunner>(Runner.get()))
470  if (MUTR->outputLoggedFeatureSpecs().size() > 1)
471  append_range(LFS, drop_begin(MUTR->outputLoggedFeatureSpecs()));
472  // We always log the output; in particular, if we're not evaluating, we
473  // don't have an output spec json file. That's why we handle the
474  // 'normal' output separately.
475  LFS.push_back({Output, None});
476  auto I = LogMap.insert(std::make_pair(
477  MF.getFunction().getName(),
478  std::make_unique<Logger>(LFS, Reward, /*IncludeReward*/ true)));
479  assert(I.second);
480  Log = I.first->second.get();
481  }
482  return std::make_unique<DevelopmentModeEvictAdvisor>(
483  MF, RA, Runner.get(), getAnalysis<MachineBlockFrequencyInfo>(),
484  getAnalysis<MachineLoopInfo>(), Log);
485  }
486 
487  std::unique_ptr<MLModelRunner> Runner;
489 };
490 #endif //#ifdef LLVM_HAVE_TF_API
491 } // namespace
492 
493 float MLEvictAdvisor::getInitialQueueSize(const MachineFunction &MF) {
494  auto &MRI = MF.getRegInfo();
495  float Ret = 0.0;
496  for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
498  if (MRI.reg_nodbg_empty(Reg))
499  continue;
500  ++Ret;
501  }
502  return Ret;
503 }
504 
505 MLEvictAdvisor::MLEvictAdvisor(const MachineFunction &MF, const RAGreedy &RA,
506  MLModelRunner *Runner,
507  const MachineBlockFrequencyInfo &MBFI,
508  const MachineLoopInfo &Loops)
509  : RegAllocEvictionAdvisor(MF, RA), DefaultAdvisor(MF, RA),
510  Runner(std::move(Runner)), MBFI(MBFI), Loops(Loops),
511  InitialQSize(MLEvictAdvisor::getInitialQueueSize(MF)) {
512  assert(this->Runner);
513  DoNotNormalize.set(FeatureIDs::mask);
514  DoNotNormalize.set(FeatureIDs::is_free);
515  DoNotNormalize.set(FeatureIDs::is_hint);
516  DoNotNormalize.set(FeatureIDs::is_local);
517  DoNotNormalize.set(FeatureIDs::min_stage);
518  DoNotNormalize.set(FeatureIDs::max_stage);
519  DoNotNormalize.set(FeatureIDs::progress);
520 }
521 
522 int64_t MLEvictAdvisor::tryFindEvictionCandidatePosition(
523  const LiveInterval &, const AllocationOrder &, unsigned, uint8_t,
524  const SmallVirtRegSet &) const {
525  int64_t Ret = Runner->evaluate<int64_t>();
526  assert(Ret >= 0);
527  assert(Ret <= CandidateVirtRegPos);
528  return Ret;
529 }
530 
531 bool MLEvictAdvisor::loadInterferenceFeatures(
532  const LiveInterval &VirtReg, MCRegister PhysReg, bool IsHint,
533  const SmallVirtRegSet &FixedRegisters, FeaturesListNormalizer &Largest,
534  size_t Pos) const {
535  // It is only possible to evict virtual register interference.
536  if (Matrix->checkInterference(VirtReg, PhysReg) > LiveRegMatrix::IK_VirtReg) {
537  // leave unavailable
538  return false;
539  }
540 
541  const bool IsLocal = LIS->intervalIsInOneMBB(VirtReg);
542  int64_t LocalIntfs = 0;
543  float NrUrgent = 0.0f;
544 
545  // The cascade tracking is the same as in the default advisor
546  unsigned Cascade = RA.getExtraInfo().getCascadeOrCurrentNext(VirtReg.reg());
547 
549  for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) {
550  LiveIntervalUnion::Query &Q = Matrix->query(VirtReg, *Units);
551  // Different from the default heuristic, we don't make any assumptions about
552  // what having more than 10 results in the query may mean.
553  const auto &IFIntervals = Q.interferingVRegs(EvictInterferenceCutoff);
554  if (IFIntervals.empty() && InterferingIntervals.empty())
555  continue;
556  if (IFIntervals.size() >= EvictInterferenceCutoff)
557  return false;
558  InterferingIntervals.append(IFIntervals.begin(), IFIntervals.end());
559  for (const LiveInterval *Intf : reverse(IFIntervals)) {
560  assert(Register::isVirtualRegister(Intf->reg()) &&
561  "Only expecting virtual register interference from query");
562  // This is the same set of legality checks as in the default case: don't
563  // try to evict fixed regs or 'done' ones. Also don't break cascades,
564  // except in the urgent case, with the same nuances used in the default
565  // heuristic.
566  // We could try sharing this between the advisors, but it may end up
567  // more complex than it is right now.
568  if (FixedRegisters.count(Intf->reg()))
569  return false;
570  if (RA.getExtraInfo().getStage(*Intf) == RS_Done)
571  return false;
572  bool Urgent =
573  !VirtReg.isSpillable() &&
574  (Intf->isSpillable() ||
575  RegClassInfo.getNumAllocatableRegs(MRI->getRegClass(VirtReg.reg())) <
576  RegClassInfo.getNumAllocatableRegs(
577  MRI->getRegClass(Intf->reg())));
578  // Only evict older cascades or live ranges without a cascade.
579  unsigned IntfCascade = RA.getExtraInfo().getCascade(Intf->reg());
580  if (Cascade <= IntfCascade) {
581  if (!Urgent)
582  return false;
583  ++NrUrgent;
584  }
585 
586  LocalIntfs += (IsLocal && LIS->intervalIsInOneMBB(*Intf) &&
587  (!EnableLocalReassign || !canReassign(*Intf, PhysReg)));
588  }
589  }
590  // OK, so if we made it this far, this LR is an eviction candidate, load its
591  // features.
592  extractFeatures(InterferingIntervals, Largest, Pos, IsHint, LocalIntfs,
593  NrUrgent);
594  return true;
595 }
596 
597 MCRegister MLEvictAdvisor::tryFindEvictionCandidate(
598  const LiveInterval &VirtReg, const AllocationOrder &Order,
599  uint8_t CostPerUseLimit, const SmallVirtRegSet &FixedRegisters) const {
600  auto MaybeOrderLimit = getOrderLimit(VirtReg, Order, CostPerUseLimit);
601  if (!MaybeOrderLimit)
602  return MCRegister::NoRegister;
603  unsigned OrderLimit = *MaybeOrderLimit;
604 
605  // The heuristic sets initial costs such as, if CostPerUseLimit is
606  // max<uint8_t>, then any of the costs of the legally-evictable intervals
607  // would be lower. When that happens, one of those will be selected.
608  // Therefore, we allow the candidate be selected, unless the candidate is
609  // unspillable, in which case it would be incorrect to not find a register for
610  // it.
611  const bool MustFindEviction =
612  (!VirtReg.isSpillable() && CostPerUseLimit == static_cast<uint8_t>(~0u));
613  // Number of available candidates - if 0, no need to continue.
614  size_t Available = 0;
615  // Make sure we don't have leftover partial state from an attempt where we had
616  // no available candidates and bailed out early.
617  resetInputs(*Runner);
618 
619  // Track the index->register mapping because AllocationOrder doesn't do that
620  // and we'd have to scan it.
621  // Also track their mask, to write asserts/debug.
622  CandidateRegList Regs;
623  Regs.fill({0, false});
624 
625  // Track the largest value of features seen during this eviction session. We
626  // only normalize (some of) the float features, but it's just simpler to
627  // dimension 'Largest' to all the features, especially since we have the
628  // 'DoNotNormalize' list.
629  FeaturesListNormalizer Largest;
630  Largest.fill(0.0);
631 
632  // Same overal idea as in the default eviction policy - we visit the values of
633  // AllocationOrder one at a time. If it's not legally available, we mask off
634  // the corresponding feature column (==do nothing because we already reset all
635  // the features to 0)
636  // Use Pos to capture the column we load features at - in AllocationOrder
637  // order.
638  size_t Pos = 0;
639  for (auto I = Order.begin(), E = Order.getOrderLimitEnd(OrderLimit); I != E;
640  ++I, ++Pos) {
641  MCRegister PhysReg = *I;
642  assert(!Regs[Pos].second);
643  assert(PhysReg);
644  if (!canAllocatePhysReg(CostPerUseLimit, PhysReg)) {
645  continue;
646  }
647  if (loadInterferenceFeatures(VirtReg, PhysReg, I.isHint(), FixedRegisters,
648  Largest, Pos)) {
649  ++Available;
650  Regs[Pos] = std::make_pair(PhysReg, true);
651  }
652  }
653  if (Available == 0) {
654  // Nothing to decide, nothing to learn.
655  assert(!MustFindEviction);
656  return MCRegister::NoRegister;
657  }
658  const size_t ValidPosLimit = Pos;
659  // If we must find eviction, the candidate should be masked out of the
660  // decision making process.
661  Regs[CandidateVirtRegPos].second = !MustFindEviction;
662  if (!MustFindEviction)
663  extractFeatures(SmallVector<const LiveInterval *, 1>(1, &VirtReg), Largest,
664  CandidateVirtRegPos, /*IsHint*/ 0, /*LocalIntfsCount*/ 0,
665  /*NrUrgent*/ 0.0);
666  assert(InitialQSize > 0.0 && "We couldn't have gotten here if we had "
667  "nothing to allocate initially.");
668  // Normalize the features.
669  for (auto &V : Largest)
670  V = V ? V : 1.0;
671  for (size_t FeatureIndex = 0; FeatureIndex < FeatureIDs::FeatureCount;
672  ++FeatureIndex) {
673  if (DoNotNormalize.test(FeatureIndex))
674  continue;
675  for (size_t Pos = 0; Pos < NumberOfInterferences; ++Pos) {
676  Runner->getTensor<float>(FeatureIndex)[Pos] /= Largest[FeatureIndex];
677  }
678  }
679  *Runner->getTensor<float>(FeatureIDs::progress) =
680  static_cast<float>(RA.getQueueSize()) / InitialQSize;
681 
682  // Get a decision.
683  size_t CandidatePos = tryFindEvictionCandidatePosition(
684  VirtReg, Order, OrderLimit, CostPerUseLimit, FixedRegisters);
685  // The contract with the ML side is that CandidatePos is mask == 1 (i.e.
686  // Regs[CandidatePos].second)
687  assert(Regs[CandidatePos].second);
688  if (CandidatePos == CandidateVirtRegPos) {
689  assert(!MustFindEviction);
690  return MCRegister::NoRegister;
691  }
692  assert(CandidatePos < ValidPosLimit);
693  (void)ValidPosLimit;
694  return Regs[CandidatePos].first;
695 }
696 
697 const LIFeatureComponents &
698 MLEvictAdvisor::getLIFeatureComponents(const LiveInterval &LI) const {
699  RegID ID = LI.reg().id();
700  LIFeatureComponents Empty;
701  auto I = CachedFeatures.insert(std::make_pair(ID, Empty));
702  LIFeatureComponents &Ret = I.first->getSecond();
703  if (!I.second)
704  return Ret;
705 
708 
710  I = MRI->reg_instr_nodbg_begin(LI.reg()),
712  I != E;) {
713  MachineInstr *MI = &*(I++);
714 
715  ++Ret.NrDefsAndUses;
716  if (!Visited.insert(MI).second)
717  continue;
718 
719  if (MI->isIdentityCopy() || MI->isImplicitDef())
720  continue;
721 
722  bool Reads, Writes;
723  std::tie(Reads, Writes) = MI->readsWritesVirtualRegister(LI.reg());
724 
725  float Freq = MBFI.getBlockFreqRelativeToEntryBlock(MI->getParent());
726  Ret.HottestBlockFreq = std::max(Freq, Ret.HottestBlockFreq);
727 
728  Ret.R += (Reads && !Writes) * Freq;
729  Ret.W += (!Reads && Writes) * Freq;
730  Ret.RW += (Reads && Writes) * Freq;
731 
732  auto *MBB = MI->getParent();
733  auto *Loop = Loops.getLoopFor(MBB);
734  bool IsExiting = Loop ? Loop->isLoopExiting(MBB) : false;
735 
736  if (Writes && IsExiting && LIS->isLiveOutOfMBB(LI, MBB))
737  Ret.IndVarUpdates += Freq;
738 
739  if (MI->isCopy() && VirtRegAuxInfo::copyHint(MI, LI.reg(), TRI, *MRI))
740  Ret.HintWeights += Freq;
741  }
742  Ret.IsRemat = VirtRegAuxInfo::isRematerializable(
743  LI, *LIS, *VRM, *MF.getSubtarget().getInstrInfo());
744  return Ret;
745 }
746 
747 // Overall, this currently mimics what we do for weight calculation, but instead
748 // of accummulating the various features, we keep them separate.
749 void MLEvictAdvisor::extractFeatures(
750  const SmallVectorImpl<const LiveInterval *> &Intervals,
751  std::array<float, FeatureIDs::FeatureCount> &Largest, size_t Pos,
752  int64_t IsHint, int64_t LocalIntfsCount, float NrUrgent) const {
753  int64_t NrDefsAndUses = 0;
754  int64_t NrBrokenHints = 0;
755  double R = 0.0;
756  double W = 0.0;
757  double RW = 0.0;
758  double IndVarUpdates = 0.0;
759  double HintWeights = 0.0;
760  float StartBBFreq = 0.0;
761  float EndBBFreq = 0.0;
762  float HottestBlockFreq = 0.0;
763  int32_t NrRematerializable = 0;
764  float TotalWeight = 0.0;
765 
766  SlotIndex EndSI = LIS->getSlotIndexes()->getZeroIndex();
767  SlotIndex StartSI = LIS->getSlotIndexes()->getLastIndex();
768  int64_t MaxStage = 0;
769  int64_t MinStage =
770  Intervals.empty() ? 0 : std::numeric_limits<int64_t>::max();
771 
772  for (const auto *L : Intervals) {
773  const LiveInterval &LI = *L;
774  MaxStage = std::max<int64_t>(
775  MaxStage, static_cast<int64_t>(RA.getExtraInfo().getStage(LI)));
776  MinStage = std::min<int64_t>(
777  MinStage, static_cast<int64_t>(RA.getExtraInfo().getStage(LI)));
778 
779  TotalWeight = std::max(TotalWeight, LI.weight());
780 
781  if (LI.beginIndex() < StartSI)
782  StartSI = LI.beginIndex();
783 
784  if (LI.endIndex() > EndSI)
785  EndSI = LI.endIndex();
786  const LIFeatureComponents &LIFC = getLIFeatureComponents(LI);
787  NrBrokenHints += VRM->hasPreferredPhys(LI.reg());
788 
789  NrDefsAndUses += LIFC.NrDefsAndUses;
790  HottestBlockFreq = std::max(HottestBlockFreq, LIFC.HottestBlockFreq);
791  R += LIFC.R;
792  W += LIFC.W;
793  RW += LIFC.RW;
794 
795  IndVarUpdates += LIFC.IndVarUpdates;
796 
797  HintWeights += LIFC.HintWeights;
798  NrRematerializable += LIFC.IsRemat;
799  }
800  size_t Size = 0;
801  if (!Intervals.empty()) {
802  StartBBFreq =
803  MBFI.getBlockFreqRelativeToEntryBlock(LIS->getMBBFromIndex(StartSI));
804  if (EndSI >= LIS->getSlotIndexes()->getLastIndex())
805  EndSI = LIS->getSlotIndexes()->getLastIndex().getPrevIndex();
806  EndBBFreq =
807  MBFI.getBlockFreqRelativeToEntryBlock(LIS->getMBBFromIndex(EndSI));
808  Size = StartSI.distance(EndSI);
809  }
810  // Set the features at the column 'Pos'.
811 #define SET(ID, TYPE, VAL) \
812  do { \
813  Runner->getTensor<TYPE>(FeatureIDs::ID)[Pos] = static_cast<TYPE>(VAL); \
814  if (!DoNotNormalize.test(FeatureIDs::ID)) \
815  Largest[FeatureIDs::ID] = \
816  std::max(Largest[FeatureIDs::ID], static_cast<float>(VAL)); \
817  } while (false)
818  SET(mask, int64_t, 1);
819  SET(is_free, int64_t, Intervals.empty());
820  SET(nr_urgent, float, NrUrgent);
821  SET(nr_broken_hints, float, NrBrokenHints);
822  SET(is_hint, int64_t, IsHint);
823  SET(is_local, int64_t, LocalIntfsCount);
824  SET(nr_rematerializable, float, NrRematerializable);
825  SET(nr_defs_and_uses, float, NrDefsAndUses);
826  SET(weighed_reads_by_max, float, R);
827  SET(weighed_writes_by_max, float, W);
828  SET(weighed_read_writes_by_max, float, RW);
829  SET(weighed_indvars_by_max, float, IndVarUpdates);
830  SET(hint_weights_by_max, float, HintWeights);
831  SET(start_bb_freq_by_max, float, StartBBFreq);
832  SET(end_bb_freq_by_max, float, EndBBFreq);
833  SET(hottest_bb_freq_by_max, float, HottestBlockFreq);
834  SET(liverange_size, float, Size);
835  SET(use_def_density, float, TotalWeight);
836  SET(max_stage, int64_t, MaxStage);
837  SET(min_stage, int64_t, MinStage);
838 #undef SET
839 }
840 
841 // Development mode-specific implementations
842 #ifdef LLVM_HAVE_TF_API
844  return new DevelopmentModeEvictionAdvisorAnalysis();
845 }
846 
847 int64_t DevelopmentModeEvictAdvisor::tryFindEvictionCandidatePosition(
848  const LiveInterval &VirtReg, const AllocationOrder &Order,
849  unsigned OrderLimit, uint8_t CostPerUseLimit,
850  const SmallVirtRegSet &FixedRegisters) const {
851  int64_t Ret = 0;
852  if (isa<ModelUnderTrainingRunner>(getRunner())) {
853  Ret = MLEvictAdvisor::tryFindEvictionCandidatePosition(
854  VirtReg, Order, OrderLimit, CostPerUseLimit, FixedRegisters);
855  } else {
856  MCRegister PhysReg = getDefaultAdvisor().tryFindEvictionCandidate(
857  VirtReg, Order, CostPerUseLimit, FixedRegisters);
858  // Find the index of the selected PhysReg. We need it for logging, otherwise
859  // this is wasted cycles (but so would starting development mode without a
860  // model nor logging)
861  if (!PhysReg)
862  Ret = CandidateVirtRegPos;
863  else
864  for (auto I = Order.begin(), E = Order.getOrderLimitEnd(OrderLimit);
865  I != E; ++I, ++Ret)
866  if (*I == PhysReg)
867  break;
868  }
869  if (TrainingLog.empty())
870  return Ret;
871  size_t CurrentFeature = 0;
872  for (; CurrentFeature < FeatureIDs::FeatureCount; ++CurrentFeature) {
873  Log->logSpecifiedTensorValue(
874  CurrentFeature, reinterpret_cast<const char *>(
875  getRunner().getTensorUntyped(CurrentFeature)));
876  }
877  if (auto *MUTR = dyn_cast<ModelUnderTrainingRunner>(&getRunner()))
878  for (size_t I = 1; I < MUTR->outputLoggedFeatureSpecs().size();
879  ++I, ++CurrentFeature)
880  Log->logSpecifiedTensorValue(
881  CurrentFeature,
882  reinterpret_cast<const char *>(
883  MUTR->lastEvaluationResult()->getUntypedTensorValue(I)));
884  // The output is right after the features and the extra outputs
885  Log->logInt64Value(CurrentFeature, &Ret);
886  return Ret;
887 }
888 
889 bool RegAllocScoring::runOnMachineFunction(MachineFunction &MF) {
890  if (auto *DevModeAnalysis = dyn_cast<DevelopmentModeEvictionAdvisorAnalysis>(
891  &getAnalysis<RegAllocEvictionAdvisorAnalysis>()))
892  if (auto *Log = DevModeAnalysis->getLogger(MF))
893  Log->logFloatFinalReward(static_cast<float>(
895  MF, getAnalysis<MachineBlockFrequencyInfo>(),
896  getAnalysis<AAResultsWrapperPass>().getAAResults())
897  .getScore()));
898 
899  return false;
900 }
901 #endif // #ifdef LLVM_HAVE_TF_API
902 
904  return new ReleaseModeEvictionAdvisorAnalysis();
905 }
906 
907 // In all cases except development mode, we don't need scoring.
908 #if !defined(LLVM_HAVE_TF_API)
910 #endif
llvm::Check::Size
@ Size
Definition: FileCheck.h:76
LiveRegMatrix.h
NoInferenceModelRunner.h
TFUtils.h
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:104
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
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:266
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:280
llvm::RegAllocEvictionAdvisorAnalysis
ImmutableAnalysis abstraction for fetching the Eviction Advisor.
Definition: RegAllocEvictionAdvisor.h:171
AllocationOrder.h
T
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
Pass.h
llvm::TargetSubtargetInfo::getInstrInfo
virtual const TargetInstrInfo * getInstrInfo() const
Definition: TargetSubtargetInfo.h:93
llvm::Register::id
unsigned id() const
Definition: Register.h:111
MLModelRunner.h
TensorSpec.h
Loops
Hexagon Hardware Loops
Definition: HexagonHardwareLoops.cpp:372
llvm::RegAllocScoring::~RegAllocScoring
~RegAllocScoring() override=default
llvm::LiveInterval::isSpillable
bool isSpillable() const
isSpillable - Can this interval be spilled?
Definition: LiveInterval.h:819
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::RISCVFenceField::W
@ W
Definition: RISCVBaseInfo.h:241
llvm::LiveInterval::weight
float weight() const
Definition: LiveInterval.h:718
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:62
RegisterClassInfo.h
llvm::TargetSubtargetInfo::getRegisterInfo
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
Definition: TargetSubtargetInfo.h:125
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:139
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:234
llvm::Function::getContext
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
Definition: Function.cpp:319
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:380
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::MachineRegisterInfo::getNumVirtRegs
unsigned getNumVirtRegs() const
getNumVirtRegs - Return the number of virtual registers created.
Definition: MachineRegisterInfo.h:765
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::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:85
EvictInterferenceCutoff
cl::opt< unsigned > EvictInterferenceCutoff
PassRegistry.h
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1620
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:103
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:240
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:89
MachineRegisterInfo.h
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
AliasAnalysis.h
CommandLine.h
llvm::MachineFunction::getRegInfo
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Definition: MachineFunction.h:650
_FEATURE_IDX
#define _FEATURE_IDX(_, name, __, ___)
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:31
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:67
llvm::MLModelRunner::evaluate
T evaluate()
Definition: MLModelRunner.h:31
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::SmallVectorImpl::append
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:667
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()
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:187
llvm::RegAllocScoring::runOnMachineFunction
bool runOnMachineFunction(MachineFunction &) override
Performs this pass.
Definition: MLRegallocEvictAdvisor.cpp:909
llvm::createRegAllocScoringPass
FunctionPass * createRegAllocScoringPass()
When learning an eviction policy, extract score(reward) information, otherwise this does nothing.
Definition: MLRegallocEvictAdvisor.cpp:103
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::None
const NoneType None
Definition: None.h:24
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
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:642
Passes.h
llvm::SlotIndex::getPrevIndex
SlotIndex getPrevIndex() const
Returns the previous index.
Definition: SlotIndexes.h:298
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:640
llvm::cl::opt
Definition: CommandLine.h:1392
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:166
INITIALIZE_PASS
INITIALIZE_PASS(RegAllocScoring, "regallocscoringpass", "Register Allocation Scoring Pass", false, false) namespace
Definition: MLRegallocEvictAdvisor.cpp:107
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:90
llvm::RegAllocScoring
Definition: MLRegallocEvictAdvisor.cpp:75
VirtRegMap.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:68
ReleaseModeModelRunner.h
llvm::DenseMap
Definition: DenseMap.h:716
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:1665
llvm::FeatureIndex
FeatureIndex
Definition: InlineModelFeatureMaps.h:109
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:241
Matrix
Live Register Matrix
Definition: LiveRegMatrix.cpp:44
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
if
if(llvm_vc STREQUAL "") set(fake_version_inc "$
Definition: CMakeLists.txt:14
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1813
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:305
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:903
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::DefaultEvictionAdvisor
Definition: RegAllocEvictionAdvisor.h:206
std
Definition: BitVector.h:851
llvm::MachineFunction::getFunction
Function & getFunction()
Return the LLVM function that this machine code represents.
Definition: MachineFunction.h:606
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
llvm::calculateRegAllocScore
RegAllocScore calculateRegAllocScore(const MachineFunction &MF, const MachineBlockFrequencyInfo &MBFI, AAResults &AAResults)
Calculate a score.
Definition: RegAllocScore.cpp:76
RegAllocGreedy.h
RegAllocEvictionAdvisor.h
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::MCRegisterInfo::DiffListIterator::isValid
bool isValid() const
isValid - returns true if this iterator is not yet at the end.
Definition: MCRegisterInfo.h:224
llvm::AAResultsWrapperPass
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Definition: AliasAnalysis.h:1347
llvm::LiveInterval::reg
Register reg() const
Definition: LiveInterval.h:717
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::RegAllocScoring::ID
static char ID
Definition: MLRegallocEvictAdvisor.cpp:77
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
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:225
llvm::SlotIndex::distance
int distance(SlotIndex other) const
Return the distance from this index to the given one.
Definition: SlotIndexes.h:213
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
CalcSpillWeights.h
llvm::RegAllocScoring::RegAllocScoring
RegAllocScoring()
Definition: MLRegallocEvictAdvisor.cpp:79
llvm::cl::desc
Definition: CommandLine.h:405
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
llvm::X86AS::FS
@ FS
Definition: X86.h:192
MachineFunction.h
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:52
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 &)