LLVM: include/llvm/ExecutionEngine/Orc/WaitingOnGraph.h Source File (original) (raw)

82template <typename ContainerIdT, typename ElementIdT> class WaitingOnGraph {

84

85public:

90

94

95 public:

102

103 private:

106 };

107

108private:

109 using ElemToSuperNodeMap =

111

113

115 public:

118 auto H = getHash(Deps);

119 if (auto *ExistingSN = findCanonicalSuperNode(H, Deps)) {

120 for (auto &[Container, Elems] : Defs) {

121 auto &DstCElems = ExistingSN->Defs[Container];

122 [[maybe_unused]] size_t ExpectedSize =

123 DstCElems.size() + Elems.size();

124 DstCElems.insert(Elems.begin(), Elems.end());

125 assert(DstCElems.size() == ExpectedSize);

126 }

127 return nullptr;

128 }

129

130 auto NewSN =

131 std::make_unique(std::move(Defs), std::move(Deps));

132 CanonicalSNs[H].push_back(NewSN.get());

133 return NewSN;

134 }

135

136 void coalesce(std::vector<std::unique_ptr> &SNs,

137 ElemToSuperNodeMap &ElemToSN) {

138 for (size_t I = 0; I != SNs.size();) {

139 auto &SN = SNs[I];

140 auto H = getHash(SN->Deps);

141 if (auto *CanonicalSN = findCanonicalSuperNode(H, SN->Deps)) {

142 for (auto &[Container, Elems] : SN->Defs) {

143 CanonicalSN->Defs[Container].insert(Elems.begin(), Elems.end());

144 auto &ContainerElemToSN = ElemToSN[Container];

145 for (auto &Elem : Elems)

146 ContainerElemToSN[Elem] = CanonicalSN;

147 }

149 SNs.pop_back();

150 } else {

151 CanonicalSNs[H].push_back(SN.get());

152 ++I;

153 }

154 }

155 }

156

157 template void remove(Pred &&Remove) {

158 std::vector<hash_code> HashesToErase;

159 for (auto &[Hash, SNs] : CanonicalSNs) {

160 for (size_t I = 0; I != SNs.size();) {

161 if (Remove(SNs[I])) {

163 SNs.pop_back();

164 } else

165 ++I;

166 }

167 if (SNs.empty())

168 HashesToErase.push_back(Hash);

169 }

170 for (auto Hash : HashesToErase)

171 CanonicalSNs.erase(Hash);

172 }

173

174 private:

177 SortedContainers.reserve(M.size());

178 for (auto &[Container, Elems] : M)

179 SortedContainers.push_back(Container);

181 hash_code Hash(0);

182 for (auto &Container : SortedContainers) {

183 auto &ContainerElems = M.at(Container);

185 ContainerElems.end());

188 }

189 return Hash;

190 }

191

192 SuperNode *findCanonicalSuperNode(hash_code H,

194 for (auto *SN : CanonicalSNs[H])

195 if (SN->Deps == M)

196 return SN;

197 return nullptr;

198 }

199

200 DenseMap<hash_code, SmallVector<SuperNode *>> CanonicalSNs;

201 };

202

203public:

204

205

206

208 public:

210 if (Defs.empty())

211 return;

212

214 for (auto &[Container, Elems] : Defs) {

215 assert(!Elems.empty() && "Defs for container must not be empty");

216 auto I = Deps.find(Container);

217 if (I == Deps.end())

218 continue;

219 auto &DepsForContainer = I->second;

220 for (auto &Elem : Elems)

221 DepsForContainer.erase(Elem);

222 if (DepsForContainer.empty())

223 ToRemove.push_back(Container);

224 }

225 for (auto &Container : ToRemove)

226 Deps.erase(Container);

227 if (auto SN = C.addOrCreateSuperNode(std::move(Defs), std::move(Deps)))

228 SNs.push_back(std::move(SN));

229 }

231 return std::move(SNs);

232 }

233

234 private:

235 Coalescer C;

236 std::vector<std::unique_ptr> SNs;

237 };

238

239 class SimplifyResult {

242

243 public:

244 const std::vector<std::unique_ptr> &superNodes() const {

245 return SNs;

246 }

247

248 private:

249 SimplifyResult(std::vector<std::unique_ptr> SNs,

250 ElemToSuperNodeMap ElemToSN)

251 : SNs(std::move(SNs)), ElemToSN(std::move(ElemToSN)) {}

252 std::vector<std::unique_ptr> SNs;

253 ElemToSuperNodeMap ElemToSN;

254 };

255

256

257 static SimplifyResult simplify(std::vector<std::unique_ptr> SNs) {

258

259 ElemToSuperNodeMap ElemToSN;

260 for (auto &SN : SNs) {

261 for (auto &[Container, Elements] : SN->Defs) {

262 auto &ContainerElemToSN = ElemToSN[Container];

263 for (auto &E : Elements)

264 ContainerElemToSN[E] = SN.get();

265 }

266 }

267

268 SuperNodeDepsMap SuperNodeDeps;

269 hoistDeps(SuperNodeDeps, SNs, ElemToSN);

270 propagateSuperNodeDeps(SuperNodeDeps);

271 sinkDeps(SNs, SuperNodeDeps);

272

273

274 Coalescer().coalesce(SNs, ElemToSN);

275

276 return {std::move(SNs), std::move(ElemToSN)};

277 }

278

280 std::vector<std::unique_ptr> Ready;

281 std::vector<std::unique_ptr> Failed;

282 };

283

285

286

287

288

289

290

291 template

292 EmitResult emit(SimplifyResult SR, GetExternalStateFn &&GetExternalState) {

293 auto NewSNs = std::move(SR.SNs);

294 auto ElemToNewSN = std::move(SR.ElemToSN);

295

296

297 auto FailedSNs = processExternalDeps(NewSNs, GetExternalState);

298

299

300 std::vector<std::unique_ptr> ModifiedPendingSNs;

301 for (size_t I = 0; I != PendingSNs.size();) {

302 auto &SN = PendingSNs[I];

303 bool Remove = false;

304 for (auto &[Container, Elems] : SN->Deps) {

305 auto I = ElemToNewSN.find(Container);

306 if (I == ElemToNewSN.end())

307 continue;

308 for (auto Elem : Elems) {

309 if (I->second.contains(Elem)) {

310 Remove = true;

311 break;

312 }

313 }

314 if (Remove)

315 break;

316 }

317 if (Remove) {

318 ModifiedPendingSNs.push_back(std::move(SN));

319 std::swap(SN, PendingSNs.back());

320 PendingSNs.pop_back();

321 } else

322 ++I;

323 }

324

325

326 SuperNodeDepsMap SuperNodeDeps;

327 hoistDeps(SuperNodeDeps, ModifiedPendingSNs, ElemToNewSN);

328

329 CoalesceToPendingSNs.remove(

330 [&](SuperNode *SN) { return SuperNodeDeps.count(SN); });

331

332 hoistDeps(SuperNodeDeps, NewSNs, ElemToPendingSN);

333 propagateSuperNodeDeps(SuperNodeDeps);

334 sinkDeps(NewSNs, SuperNodeDeps);

335 sinkDeps(ModifiedPendingSNs, SuperNodeDeps);

336

337

338

339 std::vector<std::unique_ptr> ReadyNodes, FailedNodes;

340 processReadyOrFailed(ModifiedPendingSNs, ReadyNodes, FailedNodes,

341 SuperNodeDeps, FailedSNs, &ElemToPendingSN);

342 processReadyOrFailed(NewSNs, ReadyNodes, FailedNodes, SuperNodeDeps,

343 FailedSNs, nullptr);

344

345 CoalesceToPendingSNs.coalesce(ModifiedPendingSNs, ElemToPendingSN);

346 CoalesceToPendingSNs.coalesce(NewSNs, ElemToPendingSN);

347

348

349 for (auto &SN : ModifiedPendingSNs)

350 PendingSNs.push_back(std::move(SN));

351

352

353 for (auto &SN : NewSNs) {

354 for (auto &[Container, Elems] : SN->Defs) {

355 auto &Row = ElemToPendingSN[Container];

356 for (auto &Elem : Elems)

357 Row[Elem] = SN.get();

358 }

359 PendingSNs.push_back(std::move(SN));

360 }

361

362 return {std::move(ReadyNodes), std::move(FailedNodes)};

363 }

364

365

366

367

368

369 std::vector<std::unique_ptr>

371 std::vector<std::unique_ptr> FailedSNs;

372

373 for (size_t I = 0; I != PendingSNs.size();) {

374 auto &PendingSN = PendingSNs[I];

375 bool FailPendingSN = false;

376 for (auto &[Container, Elems] : PendingSN->Deps) {

377 if (FailPendingSN)

378 break;

379 auto I = Failed.find(Container);

381 continue;

382 for (auto &Elem : Elems) {

383 if (I->second.count(Elem)) {

384 FailPendingSN = true;

385 break;

386 }

387 }

388 }

389 if (FailPendingSN) {

390 FailedSNs.push_back(std::move(PendingSN));

391 PendingSN = std::move(PendingSNs.back());

392 PendingSNs.pop_back();

393 } else

394 ++I;

395 }

396

397 CoalesceToPendingSNs.remove([&](SuperNode *SN) {

398 for (auto &E : FailedSNs)

399 if (E.get() == SN)

400 return true;

401 return false;

402 });

403

404 for (auto &SN : FailedSNs) {

405 for (auto &[Container, Elems] : SN->Defs) {

406 assert(ElemToPendingSN.count(Container));

407 auto &CElems = ElemToPendingSN[Container];

408 for (auto &Elem : Elems)

409 CElems.erase(Elem);

410 if (CElems.empty())

411 ElemToPendingSN.erase(Container);

412 }

413 }

414

415 return FailedSNs;

416 }

417

419 bool AllGood = true;

421 AllGood = false;

422 return Log;

423 };

424

425 size_t DefCount = 0;

426 for (auto &PendingSN : PendingSNs) {

427 if (PendingSN->Deps.empty())

428 ErrLog() << "Pending SN " << PendingSN.get() << " has empty dep set.\n";

429 else {

430 bool BadElem = false;

431 for (auto &[Container, Elems] : PendingSN->Deps) {

432 auto I = ElemToPendingSN.find(Container);

433 if (I == ElemToPendingSN.end())

434 continue;

435 if (Elems.empty())

436 ErrLog() << "Pending SN " << PendingSN.get()

437 << " has dependence map entry for " << Container

438 << " with empty element set.\n";

439 for (auto &Elem : Elems) {

440 if (I->second.count(Elem)) {

441 ErrLog() << "Pending SN " << PendingSN.get()

442 << " has dependence on emitted element ( " << Container

443 << ", " << Elem << ")\n";

444 BadElem = true;

445 break;

446 }

447 }

448 if (BadElem)

449 break;

450 }

451 }

452

453 for (auto &[Container, Elems] : PendingSN->Defs) {

454 if (Elems.empty())

455 ErrLog() << "Pending SN " << PendingSN.get()

456 << " has def map entry for " << Container

457 << " with empty element set.\n";

458 DefCount += Elems.size();

459 auto I = ElemToPendingSN.find(Container);

460 if (I == ElemToPendingSN.end())

461 ErrLog() << "Pending SN " << PendingSN.get() << " has "

462 << Elems.size() << " defs in container " << Container

463 << " not covered by ElemsToPendingSN.\n";

464 else {

465 for (auto &Elem : Elems) {

466 auto J = I->second.find(Elem);

467 if (J == I->second.end())

468 ErrLog() << "Pending SN " << PendingSN.get() << " has element ("

469 << Container << ", " << Elem

470 << ") not covered by ElemsToPendingSN.\n";

471 else if (J->second != PendingSN.get())

472 ErrLog() << "ElemToPendingSN value invalid for (" << Container

473 << ", " << Elem << ")\n";

474 }

475 }

476 }

477 }

478

479 size_t DefCount2 = 0;

480 for (auto &[Container, Elems] : ElemToPendingSN)

481 DefCount2 += Elems.size();

482

483 assert(DefCount2 >= DefCount);

484 if (DefCount2 != DefCount)

485 ErrLog() << "ElemToPendingSN contains extra elements.\n";

486

487 return AllGood;

488 }

489

490private:

491

492

493

494

495

496 static void hoistDeps(SuperNodeDepsMap &SuperNodeDeps,

497 std::vector<std::unique_ptr> &SNs,

498 ElemToSuperNodeMap &ElemToSN) {

499 for (auto &SN : SNs) {

500 auto &SNDeps = SuperNodeDeps[SN.get()];

501 for (auto &[DefContainer, DefElems] : ElemToSN) {

502 auto I = SN->Deps.find(DefContainer);

503 if (I == SN->Deps.end())

504 continue;

505 for (auto &[DefElem, DefSN] : DefElems)

506 if (I->second.erase(DefElem) && DefSN != SN.get())

507 SNDeps.insert(DefSN);

508 if (I->second.empty())

509 SN->Deps.erase(I);

510 }

511 }

512 }

513

514

515 static void propagateSuperNodeDeps(SuperNodeDepsMap &SuperNodeDeps) {

516 for (auto &[SN, Deps] : SuperNodeDeps) {

517 DenseSet<SuperNode *> Reachable;

519

520 while (!Worklist.empty()) {

521 auto *DepSN = Worklist.pop_back_val();

522 if (DepSN == SN)

523 continue;

524 if (!Reachable.insert(DepSN).second)

525 continue;

526 auto I = SuperNodeDeps.find(DepSN);

527 if (I == SuperNodeDeps.end())

528 continue;

529 for (auto *DepSNDep : I->second)

530 Worklist.push_back(DepSNDep);

531 }

532

533 Deps = std::move(Reachable);

534 }

535 }

536

537

538 static void sinkDeps(std::vector<std::unique_ptr> &SNs,

539 SuperNodeDepsMap &SuperNodeDeps) {

540 for (auto &SN : SNs) {

541 auto I = SuperNodeDeps.find(SN.get());

542 if (I == SuperNodeDeps.end())

543 continue;

544

545 for (auto *DepSN : I->second) {

546 assert(DepSN != SN.get() && "Unexpected self-dependence for SN");

547 for (auto &[Container, Elems] : DepSN->Deps)

548 SN->Deps[Container].insert(Elems.begin(), Elems.end());

549 }

550 }

551 }

552

553 template

554 static std::vector<SuperNode *>

555 processExternalDeps(std::vector<std::unique_ptr> &SNs,

556 GetExternalStateFn &GetExternalState) {

557 std::vector<SuperNode *> FailedSNs;

558 for (auto &SN : SNs) {

559 bool SNHasError = false;

561 for (auto &[Container, Elems] : SN->Deps) {

563 for (auto &Elem : Elems) {

564 switch (GetExternalState(Container, Elem)) {

566 break;

568 ElemToRemove.push_back(Elem);

569 break;

571 ElemToRemove.push_back(Elem);

572 SNHasError = true;

573 break;

574 }

575 }

576 for (auto &Elem : ElemToRemove)

577 Elems.erase(Elem);

578 if (Elems.empty())

579 ContainersToRemove.push_back(Container);

580 }

581 for (auto &Container : ContainersToRemove)

582 SN->Deps.erase(Container);

583 if (SNHasError)

584 FailedSNs.push_back(SN.get());

585 }

586

587 return FailedSNs;

588 }

589

590 void processReadyOrFailed(std::vector<std::unique_ptr> &SNs,

591 std::vector<std::unique_ptr> &Ready,

592 std::vector<std::unique_ptr> &Failed,

593 SuperNodeDepsMap &SuperNodeDeps,

594 const std::vector<SuperNode *> &FailedSNs,

595 ElemToSuperNodeMap *ElemToSNs) {

596

598

599 for (size_t I = 0; I != SNs.size();) {

600 auto &SN = SNs[I];

601

602 bool SNFailed = false;

603 assert(SuperNodeDeps.count(SN.get()));

604 auto &SNSuperNodeDeps = SuperNodeDeps[SN.get()];

605 for (auto *FailedSN : FailedSNs) {

606 if (FailedSN == SN.get() || SNSuperNodeDeps.count(FailedSN)) {

607 SNFailed = true;

608 break;

609 }

610 }

611

612 bool SNReady = SN->Deps.empty();

613

614 if (SNReady || SNFailed) {

615 if (ElemToSNs)

616 ToRemoveFromElemToSNs.push_back(SN.get());

620 SNs.pop_back();

621 } else

622 ++I;

623 }

624

625

626 for (auto *SN : ToRemoveFromElemToSNs) {

627 for (auto &[Container, Elems] : SN->defs()) {

628 auto &Row = (*ElemToSNs)[Container];

629 for (auto &Elem : Elems)

630 Row.erase(Elem);

631 }

632 }

633 }

634

635 std::vector<std::unique_ptr> PendingSNs;

636 ElemToSuperNodeMap ElemToPendingSN;

637 Coalescer CoalesceToPendingSNs;

638};