GenericCycleImpl.h Source File (original) (raw)

23#ifndef LLVM_ADT_GENERICCYCLEIMPL_H

24#define LLVM_ADT_GENERICCYCLEIMPL_H

31#define DEBUG_TYPE "generic-cycle-impl"

33namespace llvm {

35template

37 if ()

38 return false;

40 if (Depth > C->Depth)

41 return false;

43 C = C->ParentCycle;

44 return this == C;

45}

47template

50 if (!ExitBlocksCache.empty()) {

51 TmpStorage = ExitBlocksCache;

52 return;

53 }

55 TmpStorage.clear();

57 size_t NumExitBlocks = 0;

61 for (size_t Idx = NumExitBlocks, End = TmpStorage.size(); Idx < End;

62 ++Idx) {

63 BlockT *Succ = TmpStorage[Idx];

65 auto ExitEndIt = TmpStorage.begin() + NumExitBlocks;

66 if (std::find(TmpStorage.begin(), ExitEndIt, Succ) == ExitEndIt)

67 TmpStorage[NumExitBlocks++] = Succ;

68 }

69 }

71 TmpStorage.resize(NumExitBlocks);

72 }

73 ExitBlocksCache.append(TmpStorage.begin(), TmpStorage.end());

74}

76template

79 TmpStorage.clear();

85 break;

86 }

87 }

88 }

89}

91template

94 if (!Predecessor)

95 return nullptr;

97 assert(isReducible() && "Cycle Predecessor must be in a reducible cycle!");

100 return nullptr;

101

102

103 if (!Predecessor->isLegalToHoistInto())

104 return nullptr;

105

106 return Predecessor;

107}

108

109template

112 return nullptr;

113

114 BlockT *Out = nullptr;

115

116

118 for (const auto Pred : predecessors(Header)) {

120 if (Out && Out != Pred)

121 return nullptr;

122 Out = Pred;

123 }

124 }

125

126 return Out;

127}

128

129

131#ifndef NDEBUG

132 assert(!Blocks.empty() && "Cycle cannot be empty.");

135 assert(Blocks.insert(BB).second);

136 }

137 assert(!Entries.empty() && "Cycle must have one or more entries.");

138

141 assert(Entries.insert(Entry).second);

143 }

144

145

150

151

153

154

158 "Cycle block has no in-cycle successors!");

159

162 "Cycle block has no in-cycle predecessors!");

163

167 OutsideCyclePreds.insert(B);

168

169 if (Entries.contains(BB)) {

170 assert(!OutsideCyclePreds.empty() && "Entry is unreachable!");

171 } else if (!OutsideCyclePreds.empty()) {

172

173

174

175 BlockT *EntryBB = &BB->getParent()->front();

177 assert(!OutsideCyclePreds.contains(CB) &&

178 "Non-entry block reachable from outside!");

179 }

181 "Cycle contains function entry block!");

182

183 VisitedBBs.insert(BB);

184 }

185

187 dbgs() << "The following blocks are unreachable in the cycle:\n ";

189 for (auto *BB : Blocks) {

190 if (!VisitedBBs.count(BB)) {

191 dbgs() << LS;

192 BB->printAsOperand(dbgs());

193 }

194 }

195 dbgs() << "\n";

197 }

198

200#endif

201}

202

203

204

205

206template

208#ifndef NDEBUG

209

210 for (GenericCycle *Child : children()) {

211

212 for (BlockT *BB : Child->blocks()) {

214 "Cycle does not contain all the blocks of a subcycle!");

215 }

216 assert(Child->Depth == Depth + 1);

217 }

218

219

220 if (ParentCycle) {

222 "Cycle is not a subcycle of its parent!");

223 }

224#endif

225}

226

227

228template class GenericCycleInfoCompute {

229 using BlockT = typename ContextT::BlockT;

231 using CycleT = typename CycleInfoT::CycleT;

232

233 CycleInfoT &Info;

234

235 struct DFSInfo {

236 unsigned Start = 0;

237 unsigned End = 0;

238

239 DFSInfo() = default;

240 explicit DFSInfo(unsigned Start) : Start(Start) {}

241

242 explicit operator bool() const { return Start; }

243

244

245

246 bool isAncestorOf(const DFSInfo &Other) const {

247 return Start <= Other.Start && Other.End <= End;

248 }

249 };

250

253

254 GenericCycleInfoCompute(const GenericCycleInfoCompute &) = delete;

255 GenericCycleInfoCompute &operator=(const GenericCycleInfoCompute &) = delete;

256

257public:

259

260 void run(BlockT *EntryBlock);

261

262 static void updateDepth(CycleT *SubTree);

263

264private:

265 void dfs(BlockT *EntryBlock);

266};

267

268template

271 auto Cycle = BlockMapTopLevel.find(Block);

272 if (Cycle != BlockMapTopLevel.end())

273 return Cycle->second;

274

275 auto MapIt = BlockMap.find(Block);

276 if (MapIt == BlockMap.end())

277 return nullptr;

278

279 auto *C = MapIt->second;

280 while (C->ParentCycle)

281 C = C->ParentCycle;

282 BlockMapTopLevel.try_emplace(Block, C);

283 return C;

284}

285

286template

287void GenericCycleInfo::moveTopLevelCycleToNewParent(CycleT *NewParent,

288 CycleT *Child) {

289 assert((!Child->ParentCycle && !NewParent->ParentCycle) &&

290 "NewParent and Child must be both top level cycle!\n");

291 auto &CurrentContainer =

292 Child->ParentCycle ? Child->ParentCycle->Children : TopLevelCycles;

293 auto Pos = llvm::find_if(CurrentContainer, [=](const auto &Ptr) -> bool {

294 return Child == Ptr.get();

295 });

296 assert(Pos != CurrentContainer.end());

297 NewParent->Children.push_back(std::move(*Pos));

298 *Pos = std::move(CurrentContainer.back());

299 CurrentContainer.pop_back();

300 Child->ParentCycle = NewParent;

301

302 NewParent->Blocks.insert_range(Child->blocks());

303

304 for (auto &It : BlockMapTopLevel)

305 if (It.second == Child)

306 It.second = NewParent;

307 NewParent->clearCache();

308 Child->clearCache();

309}

310

311template

313

314

315

318

319 CycleT *ParentCycle = Cycle->getParentCycle();

320 while (ParentCycle) {

321 Cycle = ParentCycle;

323 ParentCycle = Cycle->getParentCycle();

324 }

325

326 BlockMapTopLevel.try_emplace(Block, Cycle);

327 Cycle->clearCache();

328}

329

330

331template

333 LLVM_DEBUG(errs() << "Entry block: " << Info.Context.print(EntryBlock)

334 << "\n");

335 dfs(EntryBlock);

336

338

339 for (BlockT *HeaderCandidate : llvm::reverse(BlockPreorder)) {

340 const DFSInfo CandidateInfo = BlockDFSInfo.lookup(HeaderCandidate);

341

342 for (BlockT *Pred : predecessors(HeaderCandidate)) {

343 const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred);

344

345

346 if (CandidateInfo.isAncestorOf(PredDFSInfo))

348 }

349 if (Worklist.empty()) {

350 continue;

351 }

352

353

355 << Info.Context.print(HeaderCandidate) << "\n");

356 std::unique_ptr NewCycle = std::make_unique();

357 NewCycle->appendEntry(HeaderCandidate);

358 NewCycle->appendBlock(HeaderCandidate);

359 Info.BlockMap.try_emplace(HeaderCandidate, NewCycle.get());

360

361

362

363

364 auto ProcessPredecessors = [&](BlockT *Block) {

366

367 bool IsEntry = false;

369 const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred);

370 if (CandidateInfo.isAncestorOf(PredDFSInfo)) {

372 } else if (!PredDFSInfo) {

373

374

375 LLVM_DEBUG(errs() << " skipped unreachable predecessor.\n");

376 } else {

377 IsEntry = true;

378 }

379 }

380 if (IsEntry) {

383 NewCycle->appendEntry(Block);

384 } else {

386 }

387 };

388

389 do {

391 if (Block == HeaderCandidate)

392 continue;

393

394

395

396

397 if (auto *BlockParent = Info.getTopLevelParentCycle(Block)) {

399

400 if (BlockParent != NewCycle.get()) {

402 << "discovered child cycle "

403 << Info.Context.print(BlockParent->getHeader()) << "\n");

404

405 Info.moveTopLevelCycleToNewParent(NewCycle.get(), BlockParent);

406

407 for (auto *ChildEntry : BlockParent->entries())

408 ProcessPredecessors(ChildEntry);

409 } else {

411 << "known child cycle "

412 << Info.Context.print(BlockParent->getHeader()) << "\n");

413 }

414 } else {

415 Info.BlockMap.try_emplace(Block, NewCycle.get());

417 NewCycle->Blocks.insert(Block);

418 ProcessPredecessors(Block);

419 Info.BlockMapTopLevel.try_emplace(Block, NewCycle.get());

420 }

421 } while (!Worklist.empty());

422

423 Info.TopLevelCycles.push_back(std::move(NewCycle));

424 }

425

426

427 for (auto *TLC : Info.toplevel_cycles()) {

429 << Info.Context.print(TLC->getHeader()) << "\n");

430

431 TLC->ParentCycle = nullptr;

433 }

434}

435

436

437template

440 Cycle->Depth = Cycle->ParentCycle ? Cycle->ParentCycle->Depth + 1 : 1;

441}

442

443

444

445

446template

447void GenericCycleInfoCompute::dfs(BlockT *EntryBlock) {

450 unsigned Counter = 0;

452

453 do {

454 BlockT *Block = TraverseStack.back();

456 << "\n");

457 if (BlockDFSInfo.try_emplace(Block, Counter + 1).second) {

458 ++Counter;

459

460

461

462

463

465 << TraverseStack.size() << "\n");

466

469

470 BlockPreorder.push_back(Block);

471 LLVM_DEBUG(errs() << " preorder number: " << Counter << "\n");

472 } else {

474 if (DFSTreeStack.back() == TraverseStack.size()) {

475 LLVM_DEBUG(errs() << " ended at " << Counter << "\n");

476 BlockDFSInfo.find(Block)->second.End = Counter;

478 } else {

480 }

482 }

483 } while (!TraverseStack.empty());

485

487 errs() << "Preorder:\n";

488 for (int i = 0, e = BlockPreorder.size(); i != e; ++i) {

489 errs() << " " << Info.Context.print(BlockPreorder[i]) << ": " << i << "\n";

490 }

491 );

492}

493

494

496 TopLevelCycles.clear();

497 BlockMap.clear();

498 BlockMapTopLevel.clear();

499}

500

501

502template

505 Context = ContextT(&F);

506

507 LLVM_DEBUG(errs() << "Computing cycles for function: " << F.getName()

508 << "\n");

509 Compute.run(&F.front());

510}

511

512template

515

516

519 return;

520

523}

524

525

526

527

528

529template

532 return BlockMap.lookup(Block);

533}

534

535

536

537

538

539template

543 if ( || )

544 return nullptr;

545

546

547

548 while (A->getDepth() > B->getDepth())

549 A = A->getParentCycle();

550 while (B->getDepth() > A->getDepth())

551 B = B->getParentCycle();

552

553

554

555

556 while (A != B) {

557 A = A->getParentCycle();

558 B = B->getParentCycle();

559 }

560

561 return A;

562}

563

564

565

566

567

568template

574

575

576

577

578

579template

583 return 0;

584 return Cycle->getDepth();

585}

586

587

588

589

590

591template

593#ifndef NDEBUG

595

600 if (VerifyFull)

601 Cycle->verifyCycle();

602 else

603 Cycle->verifyCycleNest();

604

606 auto MapIt = BlockMap.find(BB);

607 assert(MapIt != BlockMap.end());

609 }

610 }

611 }

612#endif

613}

614

615

619

620

621template

625 for (unsigned I = 0; I < Cycle->Depth; ++I)

626 Out << " ";

627

628 Out << Cycle->print(Context) << '\n';

629 }

630 }

631}

632

633}

634

635#undef DEBUG_TYPE

636

637#endif

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

static const Function * getParent(const Value *V)

bbsections Prepares for basic block by splitting functions into clusters of basic blocks

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

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

Analysis containing CSE Info

This file defines the DenseSet and SmallDenseSet classes.

This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.

Find all cycles in a control-flow graph, including irreducible loops.

static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)

Implements a dense probed hash-table based set.

void run(BlockT *EntryBlock)

Main function of the cycle info computations.

Definition GenericCycleImpl.h:332

GenericCycleInfoCompute(CycleInfoT &Info)

Definition GenericCycleImpl.h:258

static void updateDepth(CycleT *SubTree)

Recompute depth values of SubTree and all descendants.

Definition GenericCycleImpl.h:438

Cycle information for a function.

typename ContextT::FunctionT FunctionT

void verify() const

Verify that the entire cycle tree well-formed.

Definition GenericCycleImpl.h:616

void addBlockToCycle(BlockT *Block, CycleT *Cycle)

Assumes that Cycle is the innermost cycle containing Block.

Definition GenericCycleImpl.h:312

iterator_range< const_toplevel_iterator > toplevel_cycles() const

friend class GenericCycleInfoCompute

void print(raw_ostream &Out) const

Print the cycle info.

Definition GenericCycleImpl.h:622

CycleT * getSmallestCommonCycle(CycleT *A, CycleT *B) const

Find the innermost cycle containing both given cycles.

Definition GenericCycleImpl.h:540

void clear()

Reset the object to its initial state.

Definition GenericCycleImpl.h:495

GenericCycle< ContextT > CycleT

void compute(FunctionT &F)

Compute the cycle info for a function.

Definition GenericCycleImpl.h:503

void splitCriticalEdge(BlockT *Pred, BlockT *Succ, BlockT *New)

Definition GenericCycleImpl.h:513

unsigned getCycleDepth(const BlockT *Block) const

get the depth for the cycle which containing a given block.

Definition GenericCycleImpl.h:580

void verifyCycleNest(bool VerifyFull=false) const

Methods for debug and self-test.

Definition GenericCycleImpl.h:592

typename ContextT::BlockT BlockT

CycleT * getTopLevelParentCycle(BlockT *Block)

Definition GenericCycleImpl.h:269

CycleT * getCycle(const BlockT *Block) const

Find the innermost cycle containing a given block.

Definition GenericCycleImpl.h:530

BlockT * getHeader() const

bool isReducible() const

Whether the cycle is a natural loop.

void getExitingBlocks(SmallVectorImpl< BlockT * > &TmpStorage) const

Return all blocks of this cycle that have successor outside of this cycle.

Definition GenericCycleImpl.h:77

void verifyCycle() const

Verify that this is actually a well-formed cycle in the CFG.

Definition GenericCycleImpl.h:130

iterator_range< const_entry_iterator > entries() const

void verifyCycleNest() const

Verify the parent-child relations of this cycle.

Definition GenericCycleImpl.h:207

BlockT * getCyclePreheader() const

Return the preheader block for this cycle.

Definition GenericCycleImpl.h:92

void getExitBlocks(SmallVectorImpl< BlockT * > &TmpStorage) const

Return all of the successor blocks of this cycle.

Definition GenericCycleImpl.h:48

BlockT * getCyclePredecessor() const

If the cycle has exactly one entry with exactly one predecessor, return it, otherwise return nullptr.

Definition GenericCycleImpl.h:110

bool contains(const BlockT *Block) const

Return whether Block is contained in the cycle.

typename ContextT::BlockT BlockT

size_t getNumBlocks() const

A helper class to return the specified delimiter string after the first invocation of operator String...

size_type count(ConstPtrType Ptr) const

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

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.

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

reference emplace_back(ArgTypes &&... Args)

void push_back(const T &Elt)

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

std::pair< iterator, bool > insert(const ValueT &V)

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.

@ C

The default llvm calling convention, compatible with C.

This is an optimization pass for GlobalISel generic memory operations.

iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)

auto successors(const MachineBasicBlock *BB)

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

Wrapper function to append range R to container C.

bool any_of(R &&range, UnaryPredicate P)

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

auto reverse(ContainerTy &&C)

LLVM_ABI raw_ostream & dbgs()

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

auto succ_size(const MachineBasicBlock *BB)

LLVM_ABI raw_fd_ostream & errs()

This returns a reference to a raw_ostream for standard error.

iterator_range< typename GraphTraits< Inverse< GraphType > >::ChildIteratorType > inverse_children(const typename GraphTraits< GraphType >::NodeRef &G)

auto find_if(R &&Range, UnaryPredicate P)

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

auto predecessors(const MachineBasicBlock *BB)

iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)

bool is_contained(R &&Range, const E &Element)

Returns true if Element is found in Range.

iterator_range< df_iterator< T > > depth_first(const T &G)

std::pair< iterator, bool > insert(NodeRef N)