RegAllocPBQP.cpp Source File (original) (raw)

64#include "llvm/Config/llvm-config.h"

74#include

75#include

76#include

77#include

78#include

79#include

80#include

81#include

82#include

83#include

84#include <system_error>

85#include

86#include

87#include

89using namespace llvm;

91#define DEBUG_TYPE "regalloc"

99 cl::desc("Attempt coalescing during PBQP register allocation."),

101

102#ifndef NDEBUG

105 cl::desc("Dump graphs for each function/round in the compilation unit."),

107#endif

108

109namespace {

110

111

112

113

114

116public:

117 static char ID;

118

119

120 RegAllocPBQP(char *cPassID = nullptr)

126 }

127

128

129 StringRef getPassName() const override { return "PBQP Register Allocator"; }

130

131

132 void getAnalysisUsage(AnalysisUsage &au) const override;

133

134

135 bool runOnMachineFunction(MachineFunction &MF) override;

136

137 MachineFunctionProperties getRequiredProperties() const override {

138 return MachineFunctionProperties().setNoPHIs();

139 }

140

141 MachineFunctionProperties getClearedProperties() const override {

142 return MachineFunctionProperties().setIsSSA();

143 }

144

145private:

146 using RegSet = std::set;

147

148 char *customPassID;

149

150 RegSet VRegsToAlloc, EmptyIntervalVRegs;

151

152

153

154

155

156 SmallPtrSet<MachineInstr *, 32> DeadRemats;

157

158

159 void findVRegIntervalsToAlloc(const MachineFunction &MF, LiveIntervals &LIS);

160

161

162 void initializeGraph(PBQPRAGraph &G, VirtRegMap &VRM, Spiller &VRegSpiller);

163

164

165 void spillVReg(Register VReg, SmallVectorImpl &NewIntervals,

166 MachineFunction &MF, LiveIntervals &LIS, VirtRegMap &VRM,

167 Spiller &VRegSpiller);

168

169

170

172 const PBQP::Solution &Solution,

173 VirtRegMap &VRM,

174 Spiller &VRegSpiller);

175

176

177

178 void finalizeAlloc(MachineFunction &MF, LiveIntervals &LIS,

179 VirtRegMap &VRM) const;

180

181 void postOptimization(Spiller &VRegSpiller, LiveIntervals &LIS);

182};

183

184char RegAllocPBQP::ID = 0;

185

186

188public:

190 LiveIntervals &LIS = G.getMetadata().LIS;

191

192

193

195

196 for (auto NId : G.nodeIds()) {

199 if (SpillCost == 0.0)

200 SpillCost = std::numeric_limitsPBQP::PBQPNum::min();

201 else

202 SpillCost += MinSpillCost;

205 G.setNodeCosts(NId, std::move(NodeCosts));

206 }

207 }

208};

209

210

212private:

213 using AllowedRegVecPtr = const PBQP::RegAlloc::AllowedRegVector *;

214 using IKey = std::pair<AllowedRegVecPtr, AllowedRegVecPtr>;

215 using IMatrixCache = DenseMap<IKey, PBQPRAGraph::MatrixPtr>;

216 using DisjointAllowedRegsCache = DenseSet;

217 using IEdgeKey = std::pair<PBQP::GraphBase::NodeId, PBQP::GraphBase::NodeId>;

218 using IEdgeCache = DenseSet;

219

222 const DisjointAllowedRegsCache &D) const {

223 const auto *NRegs = &G.getNodeMetadata(NId).getAllowedRegs();

224 const auto *MRegs = &G.getNodeMetadata(MId).getAllowedRegs();

225

226 if (NRegs == MRegs)

227 return false;

228

229 if (NRegs < MRegs)

230 return D.contains(IKey(NRegs, MRegs));

231

232 return D.contains(IKey(MRegs, NRegs));

233 }

234

237 DisjointAllowedRegsCache &D) {

238 const auto *NRegs = &G.getNodeMetadata(NId).getAllowedRegs();

239 const auto *MRegs = &G.getNodeMetadata(MId).getAllowedRegs();

240

241 assert(NRegs != MRegs && "AllowedRegs can not be disjoint with itself");

242

243 if (NRegs < MRegs)

244 D.insert(IKey(NRegs, MRegs));

245 else

246 D.insert(IKey(MRegs, NRegs));

247 }

248

249

250

251

252

253 using IntervalInfo =

254 std::tuple<LiveInterval*, size_t, PBQP::GraphBase::NodeId>;

255

256 static SlotIndex getStartPoint(const IntervalInfo &I) {

257 return std::get<0>(I)->segments[std::get<1>(I)].start;

258 }

259

260 static SlotIndex getEndPoint(const IntervalInfo &I) {

261 return std::get<0>(I)->segments[std::get<1>(I)].end;

262 }

263

265 return std::get<2>(I);

266 }

267

268 static bool lowestStartPoint(const IntervalInfo &I1,

269 const IntervalInfo &I2) {

270

271

272 return getStartPoint(I1) > getStartPoint(I2);

273 }

274

275 static bool lowestEndPoint(const IntervalInfo &I1,

276 const IntervalInfo &I2) {

277 SlotIndex E1 = getEndPoint(I1);

278 SlotIndex E2 = getEndPoint(I2);

279

280 if (E1 < E2)

281 return true;

282

283 if (E1 > E2)

284 return false;

285

286

287

288

289 return std::get<0>(I1)->reg() < std::get<0>(I2)->reg();

290 }

291

292 static bool isAtLastSegment(const IntervalInfo &I) {

293 return std::get<1>(I) == std::get<0>(I)->size() - 1;

294 }

295

296 static IntervalInfo nextSegment(const IntervalInfo &I) {

297 return std::make_tuple(std::get<0>(I), std::get<1>(I) + 1, std::get<2>(I));

298 }

299

300public:

302

303

304

305

306

307 LiveIntervals &LIS = G.getMetadata().LIS;

308

309

310

311

312 IMatrixCache C;

313

314

315

316 IEdgeCache EC;

317

318

319 DisjointAllowedRegsCache D;

320

321 using IntervalSet = std::set<IntervalInfo, decltype(&lowestEndPoint)>;

322 using IntervalQueue =

323 std::priority_queue<IntervalInfo, std::vector,

324 decltype(&lowestStartPoint)>;

325 IntervalSet Active(lowestEndPoint);

326 IntervalQueue Inactive(lowestStartPoint);

327

328

329 for (auto NId : G.nodeIds()) {

330 Register VReg = G.getNodeMetadata(NId).getVReg();

331 LiveInterval &LI = LIS.getInterval(VReg);

332 assert(!LI.empty() && "PBQP graph contains node for empty interval");

333 Inactive.push(std::make_tuple(&LI, 0, NId));

334 }

335

336 while (!Inactive.empty()) {

337

338

339 IntervalInfo Cur = Inactive.top();

340

341

342 IntervalSet::iterator RetireItr = Active.begin();

343 while (RetireItr != Active.end() &&

344 (getEndPoint(*RetireItr) <= getStartPoint(Cur))) {

345

346

347 if (!isAtLastSegment(*RetireItr))

348 Inactive.push(nextSegment(*RetireItr));

349

350 ++RetireItr;

351 }

353

354

355

356 Cur = Inactive.top();

357 Inactive.pop();

358

359

360

362 for (const auto &A : Active) {

364

365

366

367 if (haveDisjointAllowedRegs(G, NId, MId, D))

368 continue;

369

370

371 IEdgeKey EK(std::min(NId, MId), std::max(NId, MId));

372 if (EC.count(EK))

373 continue;

374

375

376 if (!createInterferenceEdge(G, NId, MId, C))

377 setDisjointAllowedRegs(G, NId, MId, D);

378 else

379 EC.insert(EK);

380 }

381

382

384 }

385 }

386

387private:

388

389

390

391

392

395 IMatrixCache &C) {

396 const TargetRegisterInfo &TRI =

397 *G.getMetadata().MF.getSubtarget().getRegisterInfo();

398 const auto &NRegs = G.getNodeMetadata(NId).getAllowedRegs();

399 const auto &MRegs = G.getNodeMetadata(MId).getAllowedRegs();

400

401

402 IKey K(&NRegs, &MRegs);

404 if (I != C.end()) {

405 G.addEdgeBypassingCostAllocator(NId, MId, I->second);

406 return true;

407 }

408

410 bool NodesInterfere = false;

411 for (unsigned I = 0; I != NRegs.size(); ++I) {

412 MCRegister PRegN = NRegs[I];

413 for (unsigned J = 0; J != MRegs.size(); ++J) {

414 MCRegister PRegM = MRegs[J];

415 if (TRI.regsOverlap(PRegN, PRegM)) {

416 M[I + 1][J + 1] = std::numeric_limitsPBQP::PBQPNum::infinity();

417 NodesInterfere = true;

418 }

419 }

420 }

421

422 if (!NodesInterfere)

423 return false;

424

426 C[K] = G.getEdgeCostsPtr(EId);

427

428 return true;

429 }

430};

431

433public:

435 MachineFunction &MF = G.getMetadata().MF;

436 MachineBlockFrequencyInfo &MBFI = G.getMetadata().MBFI;

438

439

440

441 for (const auto &MBB : MF) {

442 for (const auto &MI : MBB) {

443

444 if (.setRegisters(&MI) || CP.getSrcReg() == CP.getDstReg())

445 continue;

446

449

451

452 if (CP.isPhys()) {

453 if (!MF.getRegInfo().isAllocatable(DstReg))

454 continue;

455

457

458 const PBQPRAGraph::NodeMetadata::AllowedRegVector &Allowed =

459 G.getNodeMetadata(NId).getAllowedRegs();

460

461 unsigned PRegOpt = 0;

462 while (PRegOpt < Allowed.size() && Allowed[PRegOpt].id() != DstReg)

463 ++PRegOpt;

464

465 if (PRegOpt < Allowed.size()) {

467 NewCosts[PRegOpt + 1] -= CBenefit;

468 G.setNodeCosts(NId, std::move(NewCosts));

469 }

470 } else {

473 const PBQPRAGraph::NodeMetadata::AllowedRegVector *Allowed1 =

474 &G.getNodeMetadata(N1Id).getAllowedRegs();

475 const PBQPRAGraph::NodeMetadata::AllowedRegVector *Allowed2 =

476 &G.getNodeMetadata(N2Id).getAllowedRegs();

477

479 if (EId == G.invalidEdgeId()) {

481 Allowed2->size() + 1, 0);

482 addVirtRegCoalesce(Costs, *Allowed1, *Allowed2, CBenefit);

483 G.addEdge(N1Id, N2Id, std::move(Costs));

484 } else {

485 if (G.getEdgeNode1Id(EId) == N2Id) {

488 }

490 addVirtRegCoalesce(Costs, *Allowed1, *Allowed2, CBenefit);

491 G.updateEdgeCosts(EId, std::move(Costs));

492 }

493 }

494 }

495 }

496 }

497

498private:

499 void addVirtRegCoalesce(

501 const PBQPRAGraph::NodeMetadata::AllowedRegVector &Allowed1,

502 const PBQPRAGraph::NodeMetadata::AllowedRegVector &Allowed2,

504 assert(CostMat.getRows() == Allowed1.size() + 1 && "Size mismatch.");

505 assert(CostMat.getCols() == Allowed2.size() + 1 && "Size mismatch.");

506 for (unsigned I = 0; I != Allowed1.size(); ++I) {

507 MCRegister PReg1 = Allowed1[I];

508 for (unsigned J = 0; J != Allowed2.size(); ++J) {

509 MCRegister PReg2 = Allowed2[J];

510 if (PReg1 == PReg2)

511 CostMat[I + 1][J + 1] -= Benefit;

512 }

513 }

514 }

515};

516

517

518class PBQPVirtRegAuxInfo final : public VirtRegAuxInfo {

519 float normalize(float UseDefFreq, unsigned Size, unsigned NumInstr) override {

520

521

523 }

524

525public:

526 PBQPVirtRegAuxInfo(MachineFunction &MF, LiveIntervals &LIS, VirtRegMap &VRM,

527 const MachineLoopInfo &Loops,

528 const MachineBlockFrequencyInfo &MBFI)

529 : VirtRegAuxInfo(MF, LIS, VRM, Loops, MBFI) {}

530};

531}

532

533

535

536void PBQPRAConstraint::anchor() {}

537

538void PBQPRAConstraintList::anchor() {}

539

540void RegAllocPBQP::getAnalysisUsage(AnalysisUsage &au) const {

548

549 if (customPassID)

562}

563

564void RegAllocPBQP::findVRegIntervalsToAlloc(const MachineFunction &MF,

567

568

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

571 if (MRI.reg_nodbg_empty(Reg))

572 continue;

573 VRegsToAlloc.insert(Reg);

574 }

575}

576

581 for (unsigned i = 0; CSR[i] != 0; ++i)

582 if (TRI.regsOverlap(Reg, CSR[i]))

583 return true;

584 return false;

585}

586

590

594 *G.getMetadata().MF.getSubtarget().getRegisterInfo();

595

596 std::vector Worklist(VRegsToAlloc.begin(), VRegsToAlloc.end());

597

598 std::map<Register, std::vector> VRegAllowedMap;

599

600 while (!Worklist.empty()) {

601 Register VReg = Worklist.back();

602 Worklist.pop_back();

603

605

606

607

608 if (VRegLI.empty()) {

609 EmptyIntervalVRegs.insert(VRegLI.reg());

610 VRegsToAlloc.erase(VRegLI.reg());

611 continue;

612 }

613

615

616

619

620

621 std::vector VRegAllowed;

623 for (MCPhysReg R : RawPRegOrder) {

625 if (MRI.isReserved(PReg))

626 continue;

627

628

629 if (!RegMaskOverlaps.empty() && !RegMaskOverlaps.test(PReg))

630 continue;

631

632

633 bool Interference = false;

634 for (MCRegUnit Unit : TRI.regunits(PReg)) {

636 Interference = true;

637 break;

638 }

639 }

640 if (Interference)

641 continue;

642

643

644 VRegAllowed.push_back(PReg);

645 }

646

647

648

649 if (VRegAllowed.empty()) {

651 spillVReg(VReg, NewVRegs, MF, LIS, VRM, VRegSpiller);

653 continue;

654 }

655

656 VRegAllowedMap[VReg.id()] = std::move(VRegAllowed);

657 }

658

659 for (auto &KV : VRegAllowedMap) {

660 auto VReg = KV.first;

661

662

664 EmptyIntervalVRegs.insert(VReg);

665 VRegsToAlloc.erase(VReg);

666 continue;

667 }

668

669 auto &VRegAllowed = KV.second;

670

672

673

674

675 for (unsigned i = 0; i != VRegAllowed.size(); ++i)

677 NodeCosts[1 + i] += 1.0;

678

680 G.getNodeMetadata(NId).setVReg(VReg);

681 G.getNodeMetadata(NId).setAllowedRegs(

682 G.getMetadata().getAllowedRegs(std::move(VRegAllowed)));

683 G.getMetadata().setNodeIdForVReg(VReg, NId);

684 }

685}

686

687void RegAllocPBQP::spillVReg(Register VReg,

691 VRegsToAlloc.erase(VReg);

693 nullptr, &DeadRemats);

694 VRegSpiller.spill(LRE);

695

697 (void)TRI;

699 << LRE.getParent().weight() << ", New vregs: ");

700

701

702

703 for (const Register &R : LRE) {

705 assert(!LI.empty() && "Empty spill range.");

707 VRegsToAlloc.insert(LI.reg());

708 }

709

711}

712

713bool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAGraph &G,

720 (void)TRI;

721

722

723 bool AnotherRoundNeeded = false;

724

725

727

728

729

730 for (auto NId : G.nodeIds()) {

731 Register VReg = G.getNodeMetadata(NId).getVReg();

732 unsigned AllocOpt = Solution.getSelection(NId);

733

735 MCRegister PReg = G.getNodeMetadata(NId).getAllowedRegs()[AllocOpt - 1];

737 << TRI.getName(PReg) << "\n");

738 assert(PReg != 0 && "Invalid preg selected.");

740 } else {

741

742

744 spillVReg(VReg, NewVRegs, MF, LIS, VRM, VRegSpiller);

745 AnotherRoundNeeded |= !NewVRegs.empty();

746 }

747 }

748

749 return !AnotherRoundNeeded;

750}

751

756

757

758 for (const Register &R : EmptyIntervalVRegs) {

760

762

763 if (PReg == 0) {

766 for (MCRegister CandidateReg : RawPRegOrder) {

768 PReg = CandidateReg;

769 break;

770 }

771 }

773 "No un-reserved physical registers in this register class");

774 }

775

777 }

778}

779

780void RegAllocPBQP::postOptimization(Spiller &VRegSpiller, LiveIntervals &LIS) {

782

783 for (auto *DeadInst : DeadRemats) {

785 DeadInst->eraseFromParent();

786 }

787 DeadRemats.clear();

788}

789

790bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) {

791 LiveIntervals &LIS = getAnalysis().getLIS();

793 getAnalysis().getMBFI();

794

795 auto &LiveStks = getAnalysis().getLS();

796 auto &MDT = getAnalysis().getDomTree();

797

798 VirtRegMap &VRM = getAnalysis().getVRM();

799

800 PBQPVirtRegAuxInfo VRAI(

801 MF, LIS, VRM, getAnalysis().getLI(), MBFI);

802 VRAI.calculateSpillWeightsAndHints();

803

804

805

806

807

809 MF, LIS, VRM, getAnalysis().getLI(), MBFI);

810 std::unique_ptr VRegSpiller(

812

814

816

817

818

819

820

821

822

823

824

825

826

827 findVRegIntervalsToAlloc(MF, LIS);

828

829#ifndef NDEBUG

831 std::string FullyQualifiedName =

833#endif

834

835

836 if (!VRegsToAlloc.empty()) {

838 std::unique_ptr ConstraintsRoot =

839 std::make_unique();

840 ConstraintsRoot->addConstraint(std::make_unique());

841 ConstraintsRoot->addConstraint(std::make_unique());

843 ConstraintsRoot->addConstraint(std::make_unique());

845

846 bool PBQPAllocComplete = false;

847 unsigned Round = 0;

848

849 while (!PBQPAllocComplete) {

850 LLVM_DEBUG(dbgs() << " PBQP Regalloc round " << Round << ":\n");

851 (void) Round;

852

854 initializeGraph(G, VRM, *VRegSpiller);

855 ConstraintsRoot->apply(G);

856

857#ifndef NDEBUG

859 std::ostringstream RS;

860 RS << Round;

861 std::string GraphFileName = FullyQualifiedName + "." + RS.str() +

862 ".pbqpgraph";

863 std::error_code EC;

865 LLVM_DEBUG(dbgs() << "Dumping graph for round " << Round << " to \""

866 << GraphFileName << "\"\n");

867 G.dump(OS);

868 }

869#endif

870

872 PBQPAllocComplete = mapPBQPToRegAlloc(G, Solution, VRM, *VRegSpiller);

873 ++Round;

874 }

875 }

876

877

878 finalizeAlloc(MF, LIS, VRM);

879 postOptimization(*VRegSpiller, LIS);

880 VRegsToAlloc.clear();

881 EmptyIntervalVRegs.clear();

882

883 LLVM_DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << VRM << "\n");

884

885 return true;

886}

887

888

894 Register VReg = G.getNodeMetadata(NId).getVReg();

895 const char *RegClassName = TRI->getRegClassName(MRI.getRegClass(VReg));

896 OS << NId << " (" << RegClassName << ':' << printReg(VReg, TRI) << ')';

897 });

898}

899

900#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

902 for (auto NId : nodeIds()) {

904 assert(Costs.getLength() != 0 && "Empty vector in graph.");

905 OS << PrintNodeInfo(NId, *this) << ": " << Costs << '\n';

906 }

907 OS << '\n';

908

909 for (auto EId : edgeIds()) {

912 assert(N1Id != N2Id && "PBQP graphs should not have self-edges.");

914 assert(M.getRows() != 0 && "No rows in matrix.");

915 assert(M.getCols() != 0 && "No cols in matrix.");

916 OS << PrintNodeInfo(N1Id, *this) << ' ' << M.getRows() << " rows / ";

917 OS << PrintNodeInfo(N2Id, *this) << ' ' << M.getCols() << " cols:\n";

918 OS << M << '\n';

919 }

920}

921

925#endif

926

928 OS << "graph {\n";

929 for (auto NId : nodeIds()) {

930 OS << " node" << NId << " [ label=\""

933 }

934

935 OS << " edge [ len=" << nodeIds().size() << " ]\n";

936 for (auto EId : edgeIds()) {

939 << " [ label=\"";

941 for (unsigned i = 0; i < EdgeCosts.getRows(); ++i) {

942 OS << EdgeCosts.getRowAsVector(i) << "\\n";

943 }

944 OS << "\" ]\n";

945 }

946 OS << "}\n";

947}

948

950 return new RegAllocPBQP(customPassID);

951}

952

unsigned const MachineRegisterInfo * MRI

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

This file implements the BitVector class.

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

static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

#define LLVM_DUMP_METHOD

Mark debug helper function definitions like dump() that should not be stripped from debug builds.

This file defines the DenseMap class.

This file defines the DenseSet and SmallDenseSet classes.

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

Promote Memory to Register

static Printable PrintNodeInfo(PBQP::RegAlloc::PBQPRAGraph::NodeId NId, const PBQP::RegAlloc::PBQPRAGraph &G)

Create Printable object for node and register info.

Definition RegAllocPBQP.cpp:889

static cl::opt< bool > PBQPDumpGraphs("pbqp-dump-graphs", cl::desc("Dump graphs for each function/round in the compilation unit."), cl::init(false), cl::Hidden)

static cl::opt< bool > PBQPCoalescing("pbqp-coalescing", cl::desc("Attempt coalescing during PBQP register allocation."), cl::init(false), cl::Hidden)

static bool isACalleeSavedRegister(MCRegister Reg, const TargetRegisterInfo &TRI, const MachineFunction &MF)

Definition RegAllocPBQP.cpp:577

static RegisterRegAlloc RegisterPBQPRepAlloc("pbqp", "PBQP register allocator", createDefaultPBQPRegisterAllocator)

This file defines the SmallPtrSet class.

This file defines the SmallVector class.

A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.

Represent the analysis usage information of a pass.

LLVM_ABI AnalysisUsage & addRequiredID(const void *ID)

AnalysisUsage & addRequired()

AnalysisUsage & addPreserved()

Add the specified Pass class to the set of analyses preserved by this pass.

LLVM_ABI void setPreservesCFG()

This function should be called by the pass, iff they do not:

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

bool test(unsigned Idx) const

bool empty() const

empty - Tests whether there are no bits in this bitvector.

DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator

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

Module * getParent()

Get the module that this global value is contained inside of...

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

LLVM_ABI bool checkRegMaskInterference(const LiveInterval &LI, BitVector &UsableRegs)

Test if LI is live across any register mask instructions, and compute a bit mask of physical register...

void RemoveMachineInstrFromMaps(MachineInstr &MI)

LiveInterval & getInterval(Register Reg)

LiveRange & getRegUnit(MCRegUnit Unit)

Return the live range for register unit Unit.

bool overlaps(const LiveRange &other) const

overlaps - Return true if the intersection of the two live ranges is not empty.

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

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.

Analysis pass which computes a MachineDominatorTree.

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.

MachineRegisterInfo - Keep track of information for virtual and physical registers,...

LLVM_ABI void freezeReservedRegs()

freezeReservedRegs - Called by the register allocator to freeze the set of reserved registers before ...

bool isReserved(MCRegister PhysReg) const

isReserved - Returns true when PhysReg is a reserved register.

LLVM_ABI const MCPhysReg * getCalleeSavedRegs() const

Returns list of callee saved registers.

const std::string & getModuleIdentifier() const

Get the module identifier which is, essentially, the name of the module.

Abstract base for classes implementing PBQP register allocation constraints (e.g.

virtual ~PBQPRAConstraint()=0

typename RegAllocSolverImpl::GraphMetadata GraphMetadata

typename RegAllocSolverImpl::Matrix Matrix

NodeId getEdgeNode2Id(EdgeId EId) const

NodeId getEdgeNode1Id(EdgeId EId) const

const Matrix & getEdgeCosts(EdgeId EId) const

typename RegAllocSolverImpl::Vector Vector

NodeIdSet nodeIds() const

typename RegAllocSolverImpl::RawMatrix RawMatrix

typename RegAllocSolverImpl::RawVector RawVector

const Vector & getNodeCosts(NodeId NId) const

EdgeIdSet edgeIds() const

void printDot(raw_ostream &OS) const

Print a representation of this graph in DOT format.

Definition RegAllocPBQP.cpp:927

void dump() const

Dump this graph to dbgs().

Definition RegAllocPBQP.cpp:922

Represents a solution to a PBQP problem.

unsigned getSelection(GraphBase::NodeId nodeId) const

Get a node's selection.

static LLVM_ABI PassRegistry * getPassRegistry()

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

Simple wrapper around std::function<void(raw_ostream&)>.

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

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

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

virtual void postOptimization()

virtual void spill(LiveRangeEdit &LRE, AllocationOrder *Order=nullptr)=0

spill - Spill the LRE.getParent() live interval.

ArrayRef< MCPhysReg > getRawAllocationOrder(const MachineFunction &MF, bool Rev=false) const

Returns the preferred order for allocating registers from this register class in MF.

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

TargetSubtargetInfo - Generic base class for all target subtargets.

virtual std::unique_ptr< PBQPRAConstraint > getCustomPBQPConstraints() const

Return PBQPConstraint(s) for the target.

virtual const TargetRegisterInfo * getRegisterInfo() const =0

Return the target's register information.

Calculate auxiliary information for a virtual register such as its spill weight and allocation hint.

virtual float normalize(float UseDefFreq, unsigned Size, unsigned NumInstr)

Weight normalization function.

void clearAllVirt()

clears all virtual to physical register mappings

MachineRegisterInfo & getRegInfo() const

LLVM_ABI void assignVirt2Phys(Register virtReg, MCRegister physReg)

creates a mapping for the specified virtual register to the specified physical register

A raw_ostream that writes to a file descriptor.

This class implements an extremely fast bulk output stream that can only output to a stream.

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

@ C

The default llvm calling convention, compatible with C.

Solution solve(PBQPRAGraph &G)

unsigned getSpillOptionIdx()

Spill option index.

void apply(Opt *O, const Mod &M, const Mods &... Ms)

initializer< Ty > init(const Ty &Val)

@ OF_TextWithCRLF

The file should be opened in text mode and use a carriage linefeed '\r '.

This is an optimization pass for GlobalISel generic memory operations.

void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)

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

Wrapper function to append range R to container C.

LLVM_ABI void initializeLiveIntervalsWrapperPassPass(PassRegistry &)

PBQP::RegAlloc::PBQPRAGraph PBQPRAGraph

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

LLVM_ABI FunctionPass * createDefaultPBQPRegisterAllocator()

PBQPRegisterAllocation Pass - This pass implements the Partitioned Boolean Quadratic Prograaming (PBQ...

Definition RegAllocPBQP.cpp:953

FunctionPass * createPBQPRegisterAllocator(char *customPassID=nullptr)

Create a PBQP register allocator instance.

Definition RegAllocPBQP.cpp:949

uint16_t MCPhysReg

An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...

LLVM_ABI void initializeSlotIndexesWrapperPassPass(PassRegistry &)

Spiller * createInlineSpiller(const Spiller::RequiredAnalyses &Analyses, MachineFunction &MF, VirtRegMap &VRM, VirtRegAuxInfo &VRAI, LiveRegMatrix *Matrix=nullptr)

Create and return a spiller that will insert spill code directly instead of deferring though VirtRegM...

LLVM_ABI void initializeLiveStacksWrapperLegacyPass(PassRegistry &)

LLVM_ABI void initializeVirtRegMapWrapperLegacyPass(PassRegistry &)

LLVM_ABI Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)

Prints virtual and physical registers with or without a TRI instance.

void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)

Implement std::swap in terms of BitVector swap.