RegAllocPBQP.h Source File (original) (raw)

15#ifndef LLVM_CODEGEN_REGALLOCPBQP_H

16#define LLVM_CODEGEN_REGALLOCPBQP_H

28#include

29#include

30#include

31#include

32#include

33#include

34#include

36namespace llvm {

44namespace PBQP {

54public:

56 : UnsafeRows(new bool[M.getRows() - 1]()),

57 UnsafeCols(new bool[M.getCols() - 1]()) {

58 unsigned* ColCounts = new unsigned[M.getCols() - 1]();

60 for (unsigned i = 1; i < M.getRows(); ++i) {

61 unsigned RowCount = 0;

62 for (unsigned j = 1; j < M.getCols(); ++j) {

63 if (M[i][j] == std::numeric_limits::infinity()) {

64 ++RowCount;

65 ++ColCounts[j - 1];

66 UnsafeRows[i - 1] = true;

67 UnsafeCols[j - 1] = true;

68 }

69 }

70 WorstRow = std::max(WorstRow, RowCount);

71 }

72 unsigned WorstColCountForCurRow =

73 *std::max_element(ColCounts, ColCounts + M.getCols() - 1);

74 WorstCol = std::max(WorstCol, WorstColCountForCurRow);

75 delete[] ColCounts;

76 }

83 const bool* getUnsafeRows() const { return UnsafeRows.get(); }

84 const bool* getUnsafeCols() const { return UnsafeCols.get(); }

86private:

87 unsigned WorstRow = 0;

88 unsigned WorstCol = 0;

89 std::unique_ptr<bool[]> UnsafeRows;

90 std::unique_ptr<bool[]> UnsafeCols;

91};

97public:

100

105

106 unsigned size() const { return NumOpts; }

108

110 if (NumOpts != Other.NumOpts)

111 return false;

112 return std::equal(Opts.get(), Opts.get() + NumOpts, Other.Opts.get());

113 }

114

116 return !(*this == Other);

117 }

118

119private:

120 unsigned NumOpts = 0;

121 std::unique_ptr<MCRegister[]> Opts;

122};

123

125 MCRegister *OStart = OptRegs.Opts.get();

126 MCRegister *OEnd = OptRegs.Opts.get() + OptRegs.NumOpts;

129}

130

131

133private:

135

136public:

138

143

147

149 VRegToNodeId[VReg.id()] = NId;

150 }

151

153 auto VRegItr = VRegToNodeId.find(VReg);

154 if (VRegItr == VRegToNodeId.end())

156 return VRegItr->second;

157 }

158

160 return AllowedRegVecs.getValue(std::move(Allowed));

161 }

162

163private:

165 AllowedRegVecPool AllowedRegVecs;

166};

167

168

170public:

172

173

174

175

177 Unprocessed,

178 NotProvablyAllocatable,

179 ConservativelyAllocatable,

180 OptimallyReducible

181 };

182

184

186 : RS(Other.RS), NumOpts(Other.NumOpts), DeniedOpts(Other.DeniedOpts),

187 OptUnsafeEdges(new unsigned[NumOpts]), VReg(Other.VReg),

188 AllowedRegs(Other.AllowedRegs)

189#if LLVM_ENABLE_ABI_BREAKING_CHECKS

190 ,

191 everConservativelyAllocatable(Other.everConservativelyAllocatable)

192#endif

193 {

194 if (NumOpts > 0) {

195 std::copy(&Other.OptUnsafeEdges[0], &Other.OptUnsafeEdges[NumOpts],

196 &OptUnsafeEdges[0]);

197 }

198 }

199

202

205

207 this->AllowedRegs = std::move(AllowedRegs);

208 }

210

213 OptUnsafeEdges = std::unique_ptr<unsigned[]>(new unsigned[NumOpts]());

214 }

215

218 assert(RS >= this->RS && "A node's reduction state can not be downgraded");

219 this->RS = RS;

220

221#if LLVM_ENABLE_ABI_BREAKING_CHECKS

222

223

224 if (RS == ConservativelyAllocatable)

225 everConservativelyAllocatable = true;

226#endif

227 }

228

231 const bool* UnsafeOpts =

233 for (unsigned i = 0; i < NumOpts; ++i)

234 OptUnsafeEdges[i] += UnsafeOpts[i];

235 }

236

239 const bool* UnsafeOpts =

241 for (unsigned i = 0; i < NumOpts; ++i)

242 OptUnsafeEdges[i] -= UnsafeOpts[i];

243 }

244

246 return (DeniedOpts < NumOpts) ||

247 (std::find(&OptUnsafeEdges[0], &OptUnsafeEdges[NumOpts], 0) !=

248 &OptUnsafeEdges[NumOpts]);

249 }

250

251#if LLVM_ENABLE_ABI_BREAKING_CHECKS

252 bool wasConservativelyAllocatable() const {

253 return everConservativelyAllocatable;

254 }

255#endif

256

257private:

259 unsigned NumOpts = 0;

260 unsigned DeniedOpts = 0;

261 std::unique_ptr<unsigned[]> OptUnsafeEdges;

264

265#if LLVM_ENABLE_ABI_BREAKING_CHECKS

266 bool everConservativelyAllocatable = false;

267#endif

268};

269

271private:

273

274public:

280

283

287

289

291

293 G.setSolver(*this);

295 setup();

297 G.unsetSolver();

298 return S;

299 }

300

302 assert(G.getNodeCosts(NId).getLength() > 1 &&

303 "PBQP Graph should not contain single or zero-option nodes");

304 G.getNodeMetadata(NId).setup(G.getNodeCosts(NId));

305 }

306

309

314

317 const MatrixMetadata& MMd = G.getEdgeCosts(EId).getMetadata();

319 promote(NId, NMd);

320 }

321

327

329 NodeId N1Id = G.getEdgeNode1Id(EId);

330 NodeId N2Id = G.getEdgeNode2Id(EId);

331 NodeMetadata& N1Md = G.getNodeMetadata(N1Id);

332 NodeMetadata& N2Md = G.getNodeMetadata(N2Id);

333 bool Transpose = N1Id != G.getEdgeNode1Id(EId);

334

335

336

337 const MatrixMetadata& OldMMd = G.getEdgeCosts(EId).getMetadata();

340

341

345

346

347

348 promote(N1Id, N1Md);

349 promote(N2Id, N2Md);

350 }

351

352private:

353 void promote(NodeId NId, NodeMetadata& NMd) {

354 if (G.getNodeDegree(NId) == 3) {

355

356 moveToOptimallyReducibleNodes(NId);

358 NodeMetadata::NotProvablyAllocatable &&

360

361 moveToConservativelyAllocatableNodes(NId);

362 }

363 }

364

365 void removeFromCurrentSet(NodeId NId) {

366 switch (G.getNodeMetadata(NId).getReductionState()) {

367 case NodeMetadata::Unprocessed: break;

368 case NodeMetadata::OptimallyReducible:

369 assert(OptimallyReducibleNodes.find(NId) !=

370 OptimallyReducibleNodes.end() &&

371 "Node not in optimally reducible set.");

372 OptimallyReducibleNodes.erase(NId);

373 break;

374 case NodeMetadata::ConservativelyAllocatable:

375 assert(ConservativelyAllocatableNodes.find(NId) !=

376 ConservativelyAllocatableNodes.end() &&

377 "Node not in conservatively allocatable set.");

378 ConservativelyAllocatableNodes.erase(NId);

379 break;

380 case NodeMetadata::NotProvablyAllocatable:

381 assert(NotProvablyAllocatableNodes.find(NId) !=

382 NotProvablyAllocatableNodes.end() &&

383 "Node not in not-provably-allocatable set.");

384 NotProvablyAllocatableNodes.erase(NId);

385 break;

386 }

387 }

388

389 void moveToOptimallyReducibleNodes(NodeId NId) {

390 removeFromCurrentSet(NId);

391 OptimallyReducibleNodes.insert(NId);

392 G.getNodeMetadata(NId).setReductionState(

393 NodeMetadata::OptimallyReducible);

394 }

395

396 void moveToConservativelyAllocatableNodes(NodeId NId) {

397 removeFromCurrentSet(NId);

398 ConservativelyAllocatableNodes.insert(NId);

399 G.getNodeMetadata(NId).setReductionState(

400 NodeMetadata::ConservativelyAllocatable);

401 }

402

403 void moveToNotProvablyAllocatableNodes(NodeId NId) {

404 removeFromCurrentSet(NId);

405 NotProvablyAllocatableNodes.insert(NId);

406 G.getNodeMetadata(NId).setReductionState(

407 NodeMetadata::NotProvablyAllocatable);

408 }

409

410 void setup() {

411

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

413 if (G.getNodeDegree(NId) < 3)

414 moveToOptimallyReducibleNodes(NId);

415 else if (G.getNodeMetadata(NId).isConservativelyAllocatable())

416 moveToConservativelyAllocatableNodes(NId);

417 else

418 moveToNotProvablyAllocatableNodes(NId);

419 }

420 }

421

422

423

424

425

426

427

428 std::vectorGraphBase::NodeId reduce() {

429 assert(!G.empty() && "Cannot reduce empty graph.");

430

432 std::vector NodeStack;

433

434

435 while (true) {

436 if (!OptimallyReducibleNodes.empty()) {

439 OptimallyReducibleNodes.erase(NItr);

440 NodeStack.push_back(NId);

441 switch (G.getNodeDegree(NId)) {

442 case 0:

443 break;

444 case 1:

446 break;

447 case 2:

449 break;

450 default: llvm_unreachable("Not an optimally reducible node.");

451 }

452 } else if (!ConservativelyAllocatableNodes.empty()) {

453

454

455

456

457

458

461 ConservativelyAllocatableNodes.erase(NItr);

462 NodeStack.push_back(NId);

463 G.disconnectAllNeighborsFromNode(NId);

464 } else if (!NotProvablyAllocatableNodes.empty()) {

466 SpillCostComparator(G));

468 NotProvablyAllocatableNodes.erase(NItr);

469 NodeStack.push_back(NId);

470 G.disconnectAllNeighborsFromNode(NId);

471 } else

472 break;

473 }

474

475 return NodeStack;

476 }

477

478 class SpillCostComparator {

479 public:

480 SpillCostComparator(const Graph& G) : G(G) {}

481

483 PBQPNum N1SC = G.getNodeCosts(N1Id)[0];

484 PBQPNum N2SC = G.getNodeCosts(N2Id)[0];

485 if (N1SC == N2SC)

486 return G.getNodeDegree(N1Id) < G.getNodeDegree(N2Id);

487 return N1SC < N2SC;

488 }

489

490 private:

492 };

493

495 using NodeSet = std::set;

496 NodeSet OptimallyReducibleNodes;

497 NodeSet ConservativelyAllocatableNodes;

498 NodeSet NotProvablyAllocatableNodes;

499};

500

502private:

504

505public:

507

508

509 void dump() const;

510

511

512

514

515

516

518};

519

521 if (G.empty())

524 return RegAllocSolver.solve();

525}

526

527}

528}

529

530

531FunctionPass *

533

534}

535

536#endif

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

This file defines the DenseMap class.

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

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

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

SetVector< SUnit * >::const_iterator iterator

static NodeId invalidNodeId()

Returns a value representing an invalid (non-existent) node.

typename RegAllocSolverImpl::GraphMetadata GraphMetadata

const Metadata & getMetadata() const

Holds a vector of the allowed physical regs for a vreg.

Definition RegAllocPBQP.h:94

bool operator!=(const AllowedRegVector &Other) const

Definition RegAllocPBQP.h:115

bool operator==(const AllowedRegVector &Other) const

Definition RegAllocPBQP.h:109

MCRegister operator[](size_t I) const

Definition RegAllocPBQP.h:107

AllowedRegVector(const std::vector< MCRegister > &OptVec)

Definition RegAllocPBQP.h:101

AllowedRegVector(AllowedRegVector &&)=default

AllowedRegVector()=default

friend hash_code hash_value(const AllowedRegVector &)

Definition RegAllocPBQP.h:124

unsigned size() const

Definition RegAllocPBQP.h:106

Definition RegAllocPBQP.h:501

void printDot(raw_ostream &OS) const

Print a representation of this graph in DOT format.

void dump() const

Dump this graph to dbgs().

PBQPRAGraph(GraphMetadata Metadata)

Definition RegAllocPBQP.h:506

Definition RegAllocPBQP.h:270

GraphBase::EdgeId EdgeId

Definition RegAllocPBQP.h:282

PBQP::Matrix RawMatrix

Definition RegAllocPBQP.h:276

RegAlloc::GraphMetadata GraphMetadata

Definition RegAllocPBQP.h:286

PBQP::Vector Vector

Definition RegAllocPBQP.h:277

void handleSetNodeCosts(NodeId NId, const Vector &newCosts)

Definition RegAllocPBQP.h:308

PBQP::Graph< RegAllocSolverImpl > Graph

Definition RegAllocPBQP.h:288

void handleRemoveNode(NodeId NId)

Definition RegAllocPBQP.h:307

PBQP::PoolCostAllocator< Vector, Matrix > CostAllocator

Definition RegAllocPBQP.h:279

void handleUpdateCosts(EdgeId EId, const Matrix &NewCosts)

Definition RegAllocPBQP.h:328

void handleDisconnectEdge(EdgeId EId, NodeId NId)

Definition RegAllocPBQP.h:315

GraphBase::NodeId NodeId

Definition RegAllocPBQP.h:281

void handleAddNode(NodeId NId)

Definition RegAllocPBQP.h:301

RegAlloc::NodeMetadata NodeMetadata

Definition RegAllocPBQP.h:284

void handleAddEdge(EdgeId EId)

Definition RegAllocPBQP.h:310

RegAllocSolverImpl(Graph &G)

Definition RegAllocPBQP.h:290

PBQP::Vector RawVector

Definition RegAllocPBQP.h:275

RAMatrix Matrix

Definition RegAllocPBQP.h:278

Solution solve()

Definition RegAllocPBQP.h:292

void handleReconnectEdge(EdgeId EId, NodeId NId)

Definition RegAllocPBQP.h:322

Represents a solution to a PBQP problem.

std::shared_ptr< const AllowedRegVector > PoolRef

unsigned getLength() const

Return the length of the vector.

Wrapper class representing virtual and physical registers.

constexpr unsigned id() const

An opaque object representing a hash code.

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

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

hash_code hash_value(const AllowedRegVector &OptRegs)

Definition RegAllocPBQP.h:124

Solution solve(PBQPRAGraph &G)

Definition RegAllocPBQP.h:520

unsigned getSpillOptionIdx()

Spill option index.

Definition RegAllocPBQP.h:48

void applyR2(GraphT &G, typename GraphT::NodeId NId)

void applyR1(GraphT &G, typename GraphT::NodeId NId)

Reduce a node of degree one.

Solution backpropagate(GraphT &G, StackT stack)

This is an optimization pass for GlobalISel generic memory operations.

auto min_element(R &&Range)

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

FunctionPass * createPBQPRegisterAllocator(char *customPassID=nullptr)

Create a PBQP register allocator instance.

OutputIt copy(R &&Range, OutputIt Out)

OutputIt move(R &&Range, OutputIt Out)

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

hash_code hash_combine(const Ts &...args)

Combine values into a single hash_code.

hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)

Compute a hash_code for a sequence of values.

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