MLRegAllocEvictAdvisor.cpp Source File (original) (raw)

19#if defined(LLVM_HAVE_TF_AOT_REGALLOCEVICTMODEL) || defined(LLVM_HAVE_TFLITE)

23#endif

42#include

43#include

44#include

46using namespace llvm;

48#define DEBUG_TYPE "ml-regalloc"

51#if defined(LLVM_HAVE_TF_AOT_REGALLOCEVICTMODEL)

52#include "RegAllocEvictModel.h"

54#else

56#endif

59 "regalloc-evict-interactive-channel-base", cl::Hidden,

61 "Base file path for the interactive mode. The incoming filename should "

62 "have the name .in, while the "

63 "outgoing name should be "

64 ".out"));

68 cl::desc("The maximum number of times a live range can be "

69 "evicted before preventing it from being evicted"),

73#ifdef LLVM_HAVE_TFLITE

79 cl::desc("Training log for the register allocator eviction model"));

83 cl::desc("The model being trained for register allocation eviction"));

86 "regalloc-enable-development-features", cl::Hidden,

87 cl::desc("Whether or not to enable features under development for the ML "

88 "regalloc advisor"));

90#else

92#endif

97namespace llvm {

101public:

103

106 }

107

109

111 return "Register Allocation Pass Scoring";

112 }

113

114

121 }

122

123

125};

126

129

130}

131

133 "Register Allocation Scoring Pass", false, false)

134

135

136

137

138namespace {

139

140

141static const int OpcodeValueCutoff = 17716;

142

143

144

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165#define RA_EVICT_FEATURES_LIST(M) \

166 M(int64_t, mask, PerLiveRangeShape, \

167 "boolean values, 0 for unavailable candidates (i.e. if a position is 0, " \

168 "it " \

169 "can't be evicted)") \

170 M(int64_t, is_free, PerLiveRangeShape, \

171 "boolean values, 1 if this phys reg is actually free (no interferences)") \

172 M(float, nr_urgent, PerLiveRangeShape, \

173 "number of 'urgent' intervals, normalized. Urgent are those that are OK " \

174 "to break cascades") \

175 M(float, nr_broken_hints, PerLiveRangeShape, \

176 "if this position were evicted, how many broken hints would there be") \

177 M(int64_t, is_hint, PerLiveRangeShape, \

178 "is this a preferred phys reg for the candidate") \

179 M(int64_t, is_local, PerLiveRangeShape, \

180 "is this live range local to a basic block") \

181 M(float, nr_rematerializable, PerLiveRangeShape, \

182 "nr rematerializable ranges") \

183 M(float, nr_defs_and_uses, PerLiveRangeShape, \

184 "bb freq - weighed nr defs and uses") \

185 M(float, weighed_reads_by_max, PerLiveRangeShape, \

186 "bb freq - weighed nr of reads, normalized") \

187 M(float, weighed_writes_by_max, PerLiveRangeShape, \

188 "bb feq - weighed nr of writes, normalized") \

189 M(float, weighed_read_writes_by_max, PerLiveRangeShape, \

190 "bb freq - weighed nr of uses that are both read and writes, normalized") \

191 M(float, weighed_indvars_by_max, PerLiveRangeShape, \

192 "bb freq - weighed nr of uses that are indvars, normalized") \

193 M(float, hint_weights_by_max, PerLiveRangeShape, \

194 "bb freq - weighed nr of uses that are hints, normalized") \

195 M(float, start_bb_freq_by_max, PerLiveRangeShape, \

196 "the freq in the start block, normalized") \

197 M(float, end_bb_freq_by_max, PerLiveRangeShape, \

198 "freq of end block, normalized") \

199 M(float, hottest_bb_freq_by_max, PerLiveRangeShape, \

200 "hottest BB freq, normalized") \

201 M(float, liverange_size, PerLiveRangeShape, \

202 "size (instr index diff) of the LR") \

203 M(float, use_def_density, PerLiveRangeShape, \

204 "the max weight, as computed by the manual heuristic") \

205 M(int64_t, max_stage, PerLiveRangeShape, \

206 "largest stage of an interval in this LR") \

207 M(int64_t, min_stage, PerLiveRangeShape, \

208 "lowest stage of an interval in this LR") \

209 M(float, progress, {1}, "ratio of current queue size to initial size")

210

211#ifdef LLVM_HAVE_TFLITE

212#define RA_EVICT_FIRST_DEVELOPMENT_FEATURE(M) \

213 M(int64_t, instructions, InstructionsShape, \

214 "Opcodes of the instructions covered by the eviction problem")

215

216#define RA_EVICT_REST_DEVELOPMENT_FEATURES(M) \

217 M(int64_t, instructions_mapping, InstructionsMappingShape, \

218 "A binary matrix mapping LRs to instruction opcodes") \

219 M(float, mbb_frequencies, MBBFrequencyShape, \

220 "A vector of machine basic block frequencies") \

221 M(int64_t, mbb_mapping, InstructionsShape, \

222 "A vector of indices mapping instructions to MBBs")

223#else

224#define RA_EVICT_FIRST_DEVELOPMENT_FEATURE(M)

225#define RA_EVICT_REST_DEVELOPMENT_FEATURES(M)

226#endif

227

228

229

230

231

232#define DecisionName "index_to_evict"

234 TensorSpec::createSpec<int64_t>(DecisionName, {1});

235

236

238#define _FEATURE_IDX_SIMPLE(_, name, __, ___) name

239#define _FEATURE_IDX(A, B, C, D) _FEATURE_IDX_SIMPLE(A, B, C, D),

241#ifdef LLVM_HAVE_TFLITE

243#else

245#endif

247#undef _FEATURE_IDX

248#undef _FEATURE_IDX_SIMPLE

249};

250

251

252

253

254

255template size_t getTotalSize(const std::vector<int64_t> &Shape) {

256 size_t Ret = sizeof(T);

257 for (const auto V : Shape)

258 Ret *= V;

259 return Ret;

260}

261

263#define _RESET(TYPE, NAME, SHAPE, __) \

264 std::memset(Runner.getTensorUntyped(FeatureIDs::NAME), 0, \

265 getTotalSize(SHAPE));

270#undef _RESET

271 }

272}

273

274

275

276struct LIFeatureComponents {

277 double R = 0;

278 double W = 0;

279 double RW = 0;

280 double IndVarUpdates = 0;

281 double HintWeights = 0.0;

282 int64_t NumDefsAndUses = 0;

283 float HottestBlockFreq = 0.0;

284 bool IsRemat = false;

285};

286

287using CandidateRegList =

289using FeaturesListNormalizer =

291

292

294public:

298

299protected:

302 }

303

304

305

306 const MLModelRunner &getRunner() const { return *Runner; }

307

308

309

310

311

312 virtual int64_t

313 tryFindEvictionCandidatePosition(const LiveInterval &VirtReg,

315 unsigned OrderLimit, uint8_t CostPerUseLimit,

317

318

319

320 bool

325

326private:

327 static float getInitialQueueSize(const MachineFunction &MF);

328

333

336 int64_t IsHint, int64_t LocalIntfsCount, float NumUrgent,

338

339

340

344 return getDefaultAdvisor().canEvictHintInterference(VirtReg, PhysReg,

345 FixedRegisters);

346 }

347

348 const LIFeatureComponents &

349 getLIFeatureComponents(const LiveInterval &LI) const;

350

351

352

353

354

359

360

361

362 std::bitsetFeatureIDs::FeatureCount DoNotNormalize;

363 const float InitialQSize;

364

367};

368

369#define _DECL_FEATURES(type, name, shape, _) \

370 TensorSpec::createSpec(#name, shape),

371

372

373

374

375class ReleaseModeEvictionAdvisorAnalysis final

377public:

378 ReleaseModeEvictionAdvisorAnalysis()

384 } else {

386 }

387 }

388

391 }

392

393private:

395

400 }

401

402 std::unique_ptr

404 if (!Runner) {

406 Runner = std::make_unique<ReleaseModeModelRunner>(

408 else

409 Runner = std::make_unique(

413 }

414 return std::make_unique(

415 MF, RA, Runner.get(),

416 getAnalysis().getMBFI(),

417 getAnalysis().getLI());

418 }

419 std::unique_ptr Runner;

420};

421

422

423

424

425

426

427#ifdef LLVM_HAVE_TFLITE

428static const TensorSpec Reward = TensorSpec::createSpec("reward", {1});

429

430

431

432

433

434#define _DECL_TRAIN_FEATURES(type, name, shape, _) \

435 TensorSpec::createSpec(std::string("action_") + #name, shape),

436

437class DevelopmentModeEvictAdvisor : public MLEvictAdvisor {

438public:

443 : MLEvictAdvisor(MF, RA, Runner, MBFI, Loops), Log(Log) {}

444

445private:

446 int64_t tryFindEvictionCandidatePosition(

448 unsigned OrderLimit, uint8_t CostPerUseLimit,

450

452};

453

454class DevelopmentModeEvictionAdvisorAnalysis final

456public:

457 DevelopmentModeEvictionAdvisorAnalysis()

463 TrainingInputFeatures = {

467 TensorSpec::createSpec("action_discount", {1}),

468 TensorSpec::createSpec<int32_t>("action_step_type", {1}),

469 TensorSpec::createSpec("action_reward", {1})};

470 } else {

472 TrainingInputFeatures = {

474 TensorSpec::createSpec("action_discount", {1}),

475 TensorSpec::createSpec<int32_t>("action_step_type", {1}),

476 TensorSpec::createSpec("action_reward", {1})};

477 }

478 }

479

482 }

483

486 if (!Log || !Log->hasAnyObservationForContext(MF.getName()))

487 return;

488

489

490

491

492 if (Log->currentContext() != MF.getName()) {

494 "The training log context shouldn't have had changed.");

495 }

496 if (Log->hasObservationInProgress())

497 Log->logReward<float>(GetReward());

498 }

499

500private:

502 std::vector TrainingInputFeatures;

503

508 }

509

512 if (ModelUnderTraining.empty() && TrainingLog.empty()) {

513 Ctx.emitError("Regalloc development mode should be requested with at "

514 "least logging enabled and/or a training model");

515 return false;

516 }

517 if (ModelUnderTraining.empty())

518 Runner = std::make_unique(Ctx, InputFeatures);

519 else

520 Runner = ModelUnderTrainingRunner::createAndEnsureValid(

521 Ctx, ModelUnderTraining, DecisionName, TrainingInputFeatures);

522 if (!Runner) {

523 Ctx.emitError("Regalloc: could not set up the model runner");

524 return false;

525 }

526 if (TrainingLog.empty())

527 return false;

528 std::error_code EC;

529 auto OS = std::make_unique<raw_fd_ostream>(TrainingLog, EC);

530 if (EC) {

531 M.getContext().emitError(EC.message() + ":" + TrainingLog);

532 return false;

533 }

535 if (auto *MUTR = dyn_cast(Runner.get()))

536 append_range(LFS, MUTR->extraOutputsForLoggingSpecs());

537

538

539

541

542 Log = std::make_unique(std::move(OS), LFS, Reward,

543 true);

544 return false;

545 }

546

547 std::unique_ptr

549 if (!Runner)

550 return nullptr;

551 if (Log)

552 Log->switchContext(MF.getName());

553 return std::make_unique(

554 MF, RA, Runner.get(),

555 getAnalysis().getMBFI(),

556 getAnalysis().getLI(), Log.get());

557 }

558

559 std::unique_ptr Runner;

560 std::unique_ptr Log;

561};

562

563#endif

564}

565

566float MLEvictAdvisor::getInitialQueueSize(const MachineFunction &MF) {

568 unsigned NumUsedRegs = 0;

569 for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {

571 if ( MRI .reg_nodbg_empty(Reg))

572 ++NumUsedRegs;

573 }

574 return static_cast<float>(NumUsedRegs);

575}

576

583 InitialQSize(MLEvictAdvisor::getInitialQueueSize(MF)) {

584 assert(this->Runner);

586 DoNotNormalize.set(FeatureIDs::mask);

587 DoNotNormalize.set(FeatureIDs::is_free);

588 DoNotNormalize.set(FeatureIDs::is_hint);

589 DoNotNormalize.set(FeatureIDs::is_local);

590 DoNotNormalize.set(FeatureIDs::min_stage);

591 DoNotNormalize.set(FeatureIDs::max_stage);

592 DoNotNormalize.set(FeatureIDs::progress);

593}

594

595int64_t MLEvictAdvisor::tryFindEvictionCandidatePosition(

598 int64_t Ret = Runner->evaluate<int64_t>();

601 return Ret;

602}

603

604bool MLEvictAdvisor::loadInterferenceFeatures(

609

611

612 return false;

613 }

614

615 const bool IsLocal = LIS->intervalIsInOneMBB(VirtReg);

616 int64_t LocalIntfs = 0;

617 float NumUrgent = 0.0f;

618

619

620 unsigned Cascade = RA.getExtraInfo().getCascadeOrCurrentNext(VirtReg.reg());

621

623 for (MCRegUnit Unit : TRI->regunits(PhysReg)) {

625

626

628 if (IFIntervals.empty() && InterferingIntervals.empty())

629 continue;

631 return false;

632 InterferingIntervals.append(IFIntervals.begin(), IFIntervals.end());

634 assert(Intf->reg().isVirtual() &&

635 "Only expecting virtual register interference from query");

636

637

638

639

640

641

642 if (FixedRegisters.count(Intf->reg()))

643 return false;

644 if (RA.getExtraInfo().getStage(*Intf) == RS_Done)

645 return false;

646 bool Urgent =

648 (Intf->isSpillable() ||

649 RegClassInfo.getNumAllocatableRegs(MRI->getRegClass(VirtReg.reg())) <

650 RegClassInfo.getNumAllocatableRegs(

651 MRI->getRegClass(Intf->reg())));

652

653 unsigned IntfCascade = RA.getExtraInfo().getCascade(Intf->reg());

654

655

656

657

658

659

660 if (IntfCascade >= MaxCascade && !Urgent)

661 return false;

662

663

664 if (Cascade <= IntfCascade) {

665 if (!Urgent)

666 return false;

667 ++NumUrgent;

668 }

669

670 LocalIntfs += (IsLocal && LIS->intervalIsInOneMBB(*Intf) &&

671 (!EnableLocalReassign || !canReassign(*Intf, PhysReg)));

672 }

673 }

674

675

676 extractFeatures(InterferingIntervals, Largest, Pos, IsHint, LocalIntfs,

677 NumUrgent, LRPosInfo);

678 return true;

679}

680

681MCRegister MLEvictAdvisor::tryFindEvictionCandidate(

684 auto MaybeOrderLimit = getOrderLimit(VirtReg, Order, CostPerUseLimit);

685 if (!MaybeOrderLimit)

687 unsigned OrderLimit = *MaybeOrderLimit;

688

689

690

691

692

693

694

695 const bool MustFindEviction =

696 (!VirtReg.isSpillable() && CostPerUseLimit == static_cast<uint8_t>(~0u));

697

699

700

701 resetInputs(*Runner);

702

703

704

705

706 CandidateRegList Regs;

707 Regs.fill({0, false});

708

709

710

711

712

713 FeaturesListNormalizer Largest(FeatureIDs::FeatureCount, 0.0);

714

715

716

717

718

719

720 size_t Pos = 0;

723 ++I, ++Pos) {

725 assert(!Regs[Pos].second);

727 if (!canAllocatePhysReg(CostPerUseLimit, PhysReg)) {

728 continue;

729 }

730 if (loadInterferenceFeatures(VirtReg, PhysReg, I.isHint(), FixedRegisters,

731 Largest, Pos, LRPosInfo)) {

733 Regs[Pos] = std::make_pair(PhysReg, true);

734 }

735 }

737

738 assert(!MustFindEviction);

740 }

741 const size_t ValidPosLimit = Pos;

742

743

745 if (!MustFindEviction)

748 0,

749 0.0, LRPosInfo);

750 assert(InitialQSize > 0.0 && "We couldn't have gotten here if we had "

751 "nothing to allocate initially.");

752#ifdef LLVM_HAVE_TFLITE

755 LRPosInfo, Runner,

756 [this](SlotIndex InputIndex) -> int {

757 auto *CurrentMachineInstruction =

758 LIS->getInstructionFromIndex(InputIndex);

759 if (!CurrentMachineInstruction) {

760 return -1;

761 }

762 return CurrentMachineInstruction->getOpcode();

763 },

764 [this](SlotIndex InputIndex) -> float {

765 auto *CurrentMachineInstruction =

766 LIS->getInstructionFromIndex(InputIndex);

768 CurrentMachineInstruction->getParent());

769 },

771 auto *CurrentMachineInstruction =

772 LIS->getInstructionFromIndex(InputIndex);

773 return CurrentMachineInstruction->getParent();

774 },

775 FeatureIDs::instructions, FeatureIDs::instructions_mapping,

776 FeatureIDs::mbb_frequencies, FeatureIDs::mbb_mapping,

777 LIS->getSlotIndexes()->getLastIndex());

778 }

779#endif

780

781 for (auto &V : Largest)

782 V = V ? V : 1.0;

786 continue;

789 }

790 }

791 *Runner->getTensor<float>(FeatureIDs::progress) =

792 static_cast<float>(RA.getQueueSize()) / InitialQSize;

793

794

795 size_t CandidatePos = tryFindEvictionCandidatePosition(

796 VirtReg, Order, OrderLimit, CostPerUseLimit, FixedRegisters);

797

798

799 assert(Regs[CandidatePos].second);

801 assert(!MustFindEviction);

803 }

804 assert(CandidatePos < ValidPosLimit);

805 (void)ValidPosLimit;

806 return Regs[CandidatePos].first;

807}

808

809const LIFeatureComponents &

810MLEvictAdvisor::getLIFeatureComponents(const LiveInterval &LI) const {

811 RegID ID = LI.reg().id();

812 LIFeatureComponents Empty;

813 auto I = CachedFeatures.insert(std::make_pair(ID, Empty));

814 LIFeatureComponents &Ret = I.first->getSecond();

815 if (.second)

816 return Ret;

817

820

822 I = MRI->reg_instr_nodbg_begin(LI.reg()),

823 E = MRI->reg_instr_nodbg_end();

824 I != E;) {

826

827 ++Ret.NumDefsAndUses;

828 if (!Visited.insert(MI).second)

829 continue;

830

831 if (MI->isIdentityCopy() || MI->isImplicitDef())

832 continue;

833

835 std::tie(Reads, Writes) = MI->readsWritesVirtualRegister(LI.reg());

836

838 Ret.HottestBlockFreq = std::max(Freq, Ret.HottestBlockFreq);

839

840 Ret.R += (Reads && Writes ) * Freq;

841 Ret.W += (!Reads && Writes) * Freq;

842 Ret.RW += (Reads && Writes) * Freq;

843

844 auto *MBB = MI->getParent();

847

848 if (Writes && IsExiting && LIS->isLiveOutOfMBB(LI, MBB))

849 Ret.IndVarUpdates += Freq;

850

852 Ret.HintWeights += Freq;

853 }

856 return Ret;

857}

858

859

860

861void MLEvictAdvisor::extractFeatures(

864 int64_t LocalIntfsCount, float NumUrgent,

866 int64_t NumDefsAndUses = 0;

867 int64_t NumBrokenHints = 0;

868 double R = 0.0;

869 double W = 0.0;

870 double RW = 0.0;

871 double IndVarUpdates = 0.0;

872 double HintWeights = 0.0;

873 float StartBBFreq = 0.0;

874 float EndBBFreq = 0.0;

875 float HottestBlockFreq = 0.0;

876 int32_t NumRematerializable = 0;

877 float TotalWeight = 0.0;

878

879 SlotIndex EndSI = LIS->getSlotIndexes()->getZeroIndex();

880 SlotIndex StartSI = LIS->getSlotIndexes()->getLastIndex();

881 int64_t MaxStage = 0;

882 int64_t MinStage =

883 Intervals.empty() ? 0 : std::numeric_limits<int64_t>::max();

884

885 for (const auto *L : Intervals) {

887 MaxStage = std::max<int64_t>(

888 MaxStage, static_cast<int64_t>(RA.getExtraInfo().getStage(LI)));

889 MinStage = std::min<int64_t>(

890 MinStage, static_cast<int64_t>(RA.getExtraInfo().getStage(LI)));

891

892 TotalWeight = std::max(TotalWeight, LI.weight());

893

896

899 const LIFeatureComponents &LIFC = getLIFeatureComponents(LI);

900 NumBrokenHints += VRM->hasPreferredPhys(LI.reg());

901

902 NumDefsAndUses += LIFC.NumDefsAndUses;

903 HottestBlockFreq = std::max(HottestBlockFreq, LIFC.HottestBlockFreq);

904 R += LIFC.R;

905 W += LIFC.W;

906 RW += LIFC.RW;

907

908 IndVarUpdates += LIFC.IndVarUpdates;

909

910 HintWeights += LIFC.HintWeights;

911 NumRematerializable += LIFC.IsRemat;

912

914 for (auto CurrentSegment : LI) {

916 LRStartEndInfo{CurrentSegment.start, CurrentSegment.end, Pos});

917 }

918 }

919 }

920 size_t Size = 0;

921 if (!Intervals.empty()) {

922 StartBBFreq =

924 if (EndSI >= LIS->getSlotIndexes()->getLastIndex())

925 EndSI = LIS->getSlotIndexes()->getLastIndex().getPrevIndex();

926 EndBBFreq =

929 }

930

931#define SET(ID, TYPE, VAL) \

932 do { \

933 Runner->getTensor(FeatureIDs::ID)[Pos] = static_cast(VAL); \

934 if (!DoNotNormalize.test(FeatureIDs::ID)) \

935 Largest[FeatureIDs::ID] = \

936 std::max(Largest[FeatureIDs::ID], static_cast(VAL)); \

937 } while (false)

938 SET(mask, int64_t, 1);

939 SET(is_free, int64_t, Intervals.empty());

940 SET(nr_urgent, float, NumUrgent);

941 SET(nr_broken_hints, float, NumBrokenHints);

942 SET(is_hint, int64_t, IsHint);

943 SET(is_local, int64_t, LocalIntfsCount);

944 SET(nr_rematerializable, float, NumRematerializable);

945 SET(nr_defs_and_uses, float, NumDefsAndUses);

946 SET(weighed_reads_by_max, float, R);

947 SET(weighed_writes_by_max, float, W);

948 SET(weighed_read_writes_by_max, float, RW);

949 SET(weighed_indvars_by_max, float, IndVarUpdates);

950 SET(hint_weights_by_max, float, HintWeights);

951 SET(start_bb_freq_by_max, float, StartBBFreq);

952 SET(end_bb_freq_by_max, float, EndBBFreq);

953 SET(hottest_bb_freq_by_max, float, HottestBlockFreq);

954 SET(liverange_size, float, Size);

955 SET(use_def_density, float, TotalWeight);

956 SET(max_stage, int64_t, MaxStage);

957 SET(min_stage, int64_t, MinStage);

958#undef SET

959}

960

966 const int InstructionsIndex, const int InstructionsMappingIndex,

967 const int MBBFreqIndex, const int MBBMappingIndex,

969

970

971

972

973

974

975

976

977

978

979

980

981

982

983

984 std::sort(

985 LRPosInfo.begin(), LRPosInfo.end(),

987 size_t InstructionIndex = 0;

988 size_t CurrentSegmentIndex = 0;

989 SlotIndex CurrentIndex = LRPosInfo[0].Begin;

990 std::map<MachineBasicBlock *, size_t> VisitedMBBs;

991 size_t CurrentMBBIndex = 0;

992

993

994

995

996

997

998

999 while (true) {

1000

1001

1002

1003 while (CurrentIndex <= LRPosInfo[CurrentSegmentIndex].End &&

1005 int CurrentOpcode = GetOpcode(CurrentIndex);

1006

1007 if (CurrentOpcode == -1) {

1008

1009

1010 if (CurrentIndex >= LastIndex) {

1011 return;

1012 }

1014 continue;

1015 }

1016 MachineBasicBlock *CurrentMBBReference = GetMBBReference(CurrentIndex);

1017 if (VisitedMBBs.count(CurrentMBBReference) == 0) {

1018 VisitedMBBs[CurrentMBBReference] = CurrentMBBIndex;

1019 ++CurrentMBBIndex;

1020 }

1022 GetMBBFreq, CurrentMBBReference, RegallocRunner,

1023 MBBFreqIndex, MBBMappingIndex);

1024

1025 assert(LRPosInfo[CurrentSegmentIndex].Begin <= CurrentIndex);

1026 RegallocRunner->getTensor<int64_t>(InstructionsIndex)[InstructionIndex] =

1027 CurrentOpcode < OpcodeValueCutoff ? CurrentOpcode : 0;

1028

1029 auto CurrentSegmentPosition = LRPosInfo[CurrentSegmentIndex].Pos;

1030 RegallocRunner->getTensor<int64_t>(

1031 InstructionsMappingIndex)[CurrentSegmentPosition *

1033 InstructionIndex] = 1;

1034

1035

1036

1037

1038

1039

1040

1041

1042 size_t OverlapCheckCurrentSegment = CurrentSegmentIndex + 1;

1043 while (OverlapCheckCurrentSegment < LRPosInfo.size() &&

1044 LRPosInfo[OverlapCheckCurrentSegment].Begin <= CurrentIndex) {

1045 auto OverlapCurrentSegmentPosition =

1046 LRPosInfo[OverlapCheckCurrentSegment].Pos;

1047 if (LRPosInfo[OverlapCheckCurrentSegment].End >= CurrentIndex) {

1048 RegallocRunner->getTensor<int64_t>(

1049 InstructionsMappingIndex)[OverlapCurrentSegmentPosition *

1051 InstructionIndex] = 1;

1052 }

1053 ++OverlapCheckCurrentSegment;

1054 }

1055 ++InstructionIndex;

1056 if (CurrentIndex >= LastIndex) {

1057 return;

1058 }

1060 }

1061

1062

1063 if (CurrentSegmentIndex == LRPosInfo.size() - 1 ||

1065 break;

1066 }

1067

1068

1069

1070 if (LRPosInfo[CurrentSegmentIndex + 1].Begin >

1071 LRPosInfo[CurrentSegmentIndex].End) {

1072 CurrentIndex = LRPosInfo[CurrentSegmentIndex + 1].Begin;

1073 }

1074 ++CurrentSegmentIndex;

1075 }

1076}

1077

1079 const SlotIndex CurrentIndex, const size_t CurrentInstructionIndex,

1080 std::map<MachineBasicBlock *, size_t> &VisitedMBBs,

1083 const int MBBFreqIndex, const int MBBMappingIndex) {

1084 size_t CurrentMBBIndex = VisitedMBBs[CurrentMBBReference];

1085 float CurrentMBBFreq = GetMBBFreq(CurrentIndex);

1087 RegallocRunner->getTensor<float>(MBBFreqIndex)[CurrentMBBIndex] =

1088 CurrentMBBFreq;

1089 RegallocRunner->getTensor<int64_t>(

1090 MBBMappingIndex)[CurrentInstructionIndex] = CurrentMBBIndex;

1091 }

1092}

1093

1094

1095#ifdef LLVM_HAVE_TFLITE

1096

1098 return new DevelopmentModeEvictionAdvisorAnalysis();

1099}

1100

1101int64_t DevelopmentModeEvictAdvisor::tryFindEvictionCandidatePosition(

1103 unsigned OrderLimit, uint8_t CostPerUseLimit,

1105 int64_t Ret = 0;

1106 if (isa(getRunner())) {

1107 Ret = MLEvictAdvisor::tryFindEvictionCandidatePosition(

1108 VirtReg, Order, OrderLimit, CostPerUseLimit, FixedRegisters);

1109 } else {

1110 MCRegister PhysReg = getDefaultAdvisor().tryFindEvictionCandidate(

1111 VirtReg, Order, CostPerUseLimit, FixedRegisters);

1112

1113

1114

1115 if (!PhysReg)

1117 else

1119 I != E; ++I, ++Ret)

1120 if (*I == PhysReg)

1121 break;

1122 }

1123 if (TrainingLog.empty())

1124 return Ret;

1125

1126

1127

1128 if (Log->hasObservationInProgress())

1129 Log->logReward<float>(0.0);

1130

1131 Log->startObservation();

1132 size_t CurrentFeature = 0;

1134 ? FeatureIDs::FeaturesWithDevelopmentCount

1135 : FeatureIDs::FeatureCount;

1136 for (; CurrentFeature < FeatureCount; ++CurrentFeature) {

1137 Log->logTensorValue(CurrentFeature,

1138 reinterpret_cast<const char *>(

1139 getRunner().getTensorUntyped(CurrentFeature)));

1140 }

1141 if (auto *MUTR = dyn_cast(&getRunner()))

1142 for (size_t I = 0; I < MUTR->extraOutputsForLoggingSpecs().size();

1143 ++I, ++CurrentFeature)

1144 Log->logTensorValue(

1145 CurrentFeature,

1146 reinterpret_cast<const char *>(MUTR->getUntypedExtraOutputValue(I)));

1147

1148 Log->logTensorValue(CurrentFeature, reinterpret_cast<const char *>(&Ret));

1149 Log->endObservation();

1150 return Ret;

1151}

1152

1154 std::optional CachedReward;

1155 auto GetReward = [&]() {

1156 if (!CachedReward)

1157 CachedReward = static_cast<float>(

1159 MF, getAnalysis().getMBFI())

1161 return *CachedReward;

1162 };

1163

1164 getAnalysis().logRewardIfNeeded(MF,

1165 GetReward);

1166 getAnalysis().logRewardIfNeeded(MF,

1167 GetReward);

1168 return false;

1169}

1170#endif

1171

1173 return llvm::isEmbeddedModelEvaluatorValid() ||

1175 ? new ReleaseModeEvictionAdvisorAnalysis()

1176 : nullptr;

1177}

1178

1179

1180#if !defined(LLVM_HAVE_TFLITE)

1182#endif

unsigned const MachineRegisterInfo * MRI

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

SmallVector< uint32_t, 0 > Writes

@ Available

We know the block is fully available. This is a fixpoint.

Module.h This file contains the declarations for the Module class.

static cl::opt< std::string > InteractiveChannelBaseName("inliner-interactive-channel-base", cl::Hidden, cl::desc("Base file path for the interactive mode. The incoming filename should " "have the name .in, while the " "outgoing name should be .out"))

static const bool EnableDevelopmentFeatures

#define RA_EVICT_FEATURES_LIST(M)

#define _FEATURE_IDX_SIMPLE(_, name, __, ___)

#define RA_EVICT_FIRST_DEVELOPMENT_FEATURE(M)

#define SET(ID, TYPE, VAL)

#define _RESET(TYPE, NAME, SHAPE, __)

static cl::opt< unsigned > MaxCascade("mlregalloc-max-cascade", cl::Hidden, cl::desc("The maximum number of times a live range can be " "evicted before preventing it from being evicted"), cl::init(20))

#define RA_EVICT_REST_DEVELOPMENT_FEATURES(M)

static cl::opt< std::string > InteractiveChannelBaseName("regalloc-evict-interactive-channel-base", cl::Hidden, cl::desc("Base file path for the interactive mode. The incoming filename should " "have the name .in, while the " "outgoing name should be " ".out"))

#define _FEATURE_IDX(A, B, C, D)

#define _DECL_FEATURES(type, name, shape, _)

unsigned const TargetRegisterInfo * TRI

#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

SI optimize exec mask operations pre RA

Iterator getOrderLimitEnd(unsigned OrderLimit) const

Represent the analysis usage information of a pass.

AnalysisUsage & addRequired()

void setPreservesAll()

Set by analyses that do not transform their input at all.

FunctionPass class - This class is used to implement most global optimizations.

LLVMContext & getContext() const

getContext - Return a reference to the LLVMContext associated with this function.

This is an important class for using LLVM in a threaded context.

void emitError(const Instruction *I, const Twine &ErrorStr)

emitError - Emit an error message to the currently installed error handler with optional location inf...

Query interferences between a single live virtual register and a live interval union.

const SmallVectorImpl< const LiveInterval * > & interferingVRegs(unsigned MaxInterferingRegs=std::numeric_limits< unsigned >::max())

LiveInterval - This class represents the liveness of a register, or stack slot.

bool isSpillable() const

isSpillable - Can this interval be spilled?

SlotIndex beginIndex() const

beginIndex - Return the lowest numbered slot covered.

SlotIndex endIndex() const

endNumber - return the maximum point of the range of the whole, exclusive.

@ IK_VirtReg

Virtual register interference.

Logging utility - given an ordered specification of features, and assuming a scalar reward,...

bool isLoopExiting(const BlockT *BB) const

True if terminator in the block can branch to another block that is outside of the current loop.

Represents a single loop in the control flow graph.

Wrapper class representing physical registers. Should be passed by value.

static constexpr unsigned NoRegister

MLModelRunner interface: abstraction of a mechanism for evaluating a ML model.

virtual void switchContext(StringRef Name)

T * getTensor(I FeatureID)

const MachineFunction * getParent() const

Return the MachineFunction containing this basic block.

MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...

double getBlockFreqRelativeToEntryBlock(const MachineBasicBlock *MBB) const

Compute the frequency of the block, relative to the entry block.

MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...

void getAnalysisUsage(AnalysisUsage &AU) const override

getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.

const TargetSubtargetInfo & getSubtarget() const

getSubtarget - Return the subtarget for which this machine code is being compiled.

StringRef getName() const

getName - Return the name of the corresponding LLVM function.

MachineRegisterInfo & getRegInfo()

getRegInfo - Return information about the registers currently in use.

Function & getFunction()

Return the LLVM function that this machine code represents.

Representation of each machine instruction.

defusechain_iterator - This class provides iterator support for machine operands in the function that...

A Module instance is used to store all the information related to an LLVM module.

A mock class satisfying the interface expected by ReleaseModeModelRunner for its TGen parameter.

static PassRegistry * getPassRegistry()

getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...

virtual bool doInitialization(Module &)

doInitialization - Virtual method overridden by subclasses to do any necessary initialization before ...

ImmutableAnalysis abstraction for fetching the Eviction Advisor.

void getAnalysisUsage(AnalysisUsage &AU) const override

getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...

virtual std::unique_ptr< RegAllocEvictionAdvisor > getAdvisor(const MachineFunction &MF, const RAGreedy &RA)=0

Get an advisor for the given context (i.e. machine function, etc)

virtual void logRewardIfNeeded(const MachineFunction &MF, llvm::function_ref< float()> GetReward)

virtual bool canEvictHintInterference(const LiveInterval &VirtReg, MCRegister PhysReg, const SmallVirtRegSet &FixedRegisters) const =0

Find out if we can evict the live ranges occupying the given PhysReg, which is a hint (preferred regi...

virtual MCRegister tryFindEvictionCandidate(const LiveInterval &VirtReg, const AllocationOrder &Order, uint8_t CostPerUseLimit, const SmallVirtRegSet &FixedRegisters) const =0

Find a physical register that can be freed by evicting the FixedRegisters, or return NoRegister.

StringRef getPassName() const override

getPassName - Return a nice clean name for a pass.

void getAnalysisUsage(AnalysisUsage &AU) const override

RegAllocReward analysis usage.

~RegAllocScoring() override=default

bool runOnMachineFunction(MachineFunction &) override

Performs this pass.

Wrapper class representing virtual and physical registers.

static Register index2VirtReg(unsigned Index)

Convert a 0-based index to a virtual register number.

constexpr unsigned id() const

SlotIndex - An opaque wrapper around machine indexes.

SlotIndex getNextIndex() const

Returns the next index.

int distance(SlotIndex other) const

Return the distance from this index to the given one.

SlotIndex getPrevIndex() const

Returns the previous index.

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...

size_type count(const T &V) const

count - Return 1 if the element is in the set, 0 otherwise.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

void append(ItTy in_start, ItTy in_end)

Add the specified range to the end of the SmallVector.

void push_back(const T &Elt)

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

StringRef - Represent a constant reference to a string, i.e.

TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...

virtual const TargetRegisterInfo * getRegisterInfo() const

getRegisterInfo - If register information is available, return it.

virtual const TargetInstrInfo * getInstrInfo() const

static Register copyHint(const MachineInstr *MI, unsigned Reg, const TargetRegisterInfo &TRI, const MachineRegisterInfo &MRI)

Return the preferred allocation register for reg, given a COPY instruction.

static bool isRematerializable(const LiveInterval &LI, const LiveIntervals &LIS, const VirtRegMap &VRM, const TargetInstrInfo &TII)

Determine if all values in LI are rematerializable.

An efficient, type-erasing, non-owning reference to a callable.

Reg

All possible values of the reg field in the ModR/M byte.

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

static const int ModelMaxSupportedInstructionCount

static const int64_t ModelMaxSupportedMBBCount

void append_range(Container &C, Range &&R)

Wrapper function to append range R to container C.

void extractInstructionFeatures(llvm::SmallVectorImpl< LRStartEndInfo > &LRPosInfo, MLModelRunner *RegallocRunner, function_ref< int(SlotIndex)> GetOpcode, function_ref< float(SlotIndex)> GetMBBFreq, function_ref< MachineBasicBlock *(SlotIndex)> GetMBBReference, const int InstructionsIndex, const int InstructionsMappingIndex, const int MBBFreqIndex, const int MBBMappingIndex, const SlotIndex LastIndex)

static const TensorSpec DecisionSpec

RegAllocScore calculateRegAllocScore(const MachineFunction &MF, const MachineBlockFrequencyInfo &MBFI)

Calculate a score.

auto reverse(ContainerTy &&C)

const char *const DecisionName

static const std::vector< TensorSpec > InputFeatures

@ RS_Done

There is nothing more we can do to this live range.

FunctionPass * createRegAllocScoringPass()

When learning an eviction policy, extract score(reward) information, otherwise this does nothing.

void initializeRegAllocScoringPass(PassRegistry &)

RegAllocEvictionAdvisorAnalysis * createReleaseModeAdvisor()

RegAllocEvictionAdvisorAnalysis * createDevelopmentModeAdvisor()

cl::opt< unsigned > EvictInterferenceCutoff

OutputIt move(R &&Range, OutputIt Out)

Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.

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)

static const int64_t NumberOfInterferences

static const std::vector< int64_t > PerLiveRangeShape

static const int64_t CandidateVirtRegPos

Implement std::hash so that hash_code can be used in STL containers.