RegionInfo.h Source File (original) (raw)

36#ifndef LLVM_ANALYSIS_REGIONINFO_H

37#define LLVM_ANALYSIS_REGIONINFO_H

47#include

48#include

49#include

50#include

51#include

52#include

53#include <type_traits>

54#include

56namespace llvm {

58class DominanceFrontier;

59class Loop;

60class LoopInfo;

61class PostDominatorTree;

63template class RegionBase;

64class RegionInfo;

65template class RegionInfoBase;

66class RegionNode;

67class raw_ostream;

72template <class FuncT_>

79 using BrokenT = typename FuncT_::UnknownRegionTypeError;

80};

82template <>

99 }

100};

101

102

103

104

105

106

107

108

109template

111

112

113

114template

117

118public:

119 using BlockT = typename Tr::BlockT;

120 using RegionT = typename Tr::RegionT;

121

122private:

123

124

125

126

127

128

129

130

131

132

134

135

136

138

139protected:

140

141

142

143

144

145

146

147

150 : entry(Entry, isSubRegion), parent(Parent) {}

151

152public:

155

156

157

158

159

160

161

162

163

165

166

167

168

169

170

171

173

174

175

176

177

178

179

181

182

183

184

185

187};

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251template

254

255 using FuncT = typename Tr::FuncT;

256 using BlockT = typename Tr::BlockT;

257 using RegionInfoT = typename Tr::RegionInfoT;

258 using RegionT = typename Tr::RegionT;

259 using RegionNodeT = typename Tr::RegionNodeT;

260 using DomTreeT = typename Tr::DomTreeT;

261 using LoopT = typename Tr::LoopT;

262 using LoopInfoT = typename Tr::LoopInfoT;

263 using InstT = typename Tr::InstT;

264

267 using SuccIterTy = typename BlockTraits::ChildIteratorType;

268 using PredIterTy = typename InvBlockTraits::ChildIteratorType;

269

270

271 RegionInfoT *RI;

272 DomTreeT *DT;

273

274

275

276 BlockT *exit;

277

278 using RegionSet = std::vector<std::unique_ptr>;

279

280

281 RegionSet children;

282

283 using BBNodeMapT = std::map<BlockT *, std::unique_ptr>;

284

285

286 mutable BBNodeMapT BBNodeMap;

287

288

289

290 void verifyBBInRegion(BlockT *BB) const;

291

292

293

294

295 void verifyWalk(BlockT *BB, std::set<BlockT *> *visitedBB) const;

296

297

298 void verifyRegionNest() const;

299

300public:

301

302

303

304

305

306

307

308

309 RegionBase(BlockT *Entry, BlockT *Exit, RegionInfoT *RI, DomTreeT *DT,

310 RegionT *Parent = nullptr);

311

314

315

317

318

319

322 }

323

324

325

326

327

329

330

331

332

333

335

336

337

338

339

340

341

342

344

345

346

347

348

349

350

351

353

354

355

356

357 BlockT *getExit() const { return exit; }

358

359

360

361

364 }

365

366

367

369 return const_cast<RegionNodeT *>(

370 reinterpret_cast<const RegionNodeT *>(this));

371 }

372

373

374

375

376

377

379

380

381

382

384

385

386

387

388

389

390

392

393

394

395

396

397

399

400

401

402

403

404

406

407

408

409

411

412

413

414

415

416

418

419

420

422

423

425

426

428

429

430

431

432

433

434 void print(raw_ostream &OS, bool printTree = true, unsigned level = 0,

436

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

438

439 void dump() const;

440#endif

441

442

443

444

445

446 bool contains(const BlockT *BB) const;

447

448

449

450

451

452 bool contains(const RegionT *SubRegion) const {

453

455 return true;

456

457 return contains(SubRegion->getEntry()) &&

458 (contains(SubRegion->getExit()) ||

459 SubRegion->getExit() == getExit());

460 }

461

462

463

464

465

466

467 bool contains(const InstT *Inst) const { return contains(Inst->getParent()); }

468

469

470

471

472

473

474

475

476 bool contains(const LoopT *L) const;

477

478

479

480

481

482

483

484

485

487

488

489

490

491

492

493

494

495

496

498

499

500

501

502

504

505

506

507

508

509

510

511 RegionNodeT *getNode(BlockT *BB) const;

512

513

514

515

516

517 RegionNodeT *getBBNode(BlockT *BB) const;

518

519

520

521

522

523

524 void addSubRegion(RegionT *SubRegion, bool moveChildren = false);

525

526

527

528

529

530

532

533

534

535

537

538

539

540

541

543

544

545

546

547

548

550

551

552

553

554

555 using iterator = typename RegionSet::iterator;

557

560

563

564

565

566

567

568

569

570

571 template

574 std::conditional_t<IsConst, const BlockT, BlockT> *> {

577

578 public:

581

582

585

586

587

589 }

590

591

593

595

596

597

598

601 }

602 };

603

606

608

610

613 }

615

618

619

622 }

623

624

625

626

629 }

630

631

632

633

634

635

636

637

641

646

651 }

652

657 }

658

659};

660

661

662template

663inline raw_ostream &operator<<(raw_ostream &OS, const RegionNodeBase &Node);

664

665

666

667

668

669

670

671template

675

676 using BlockT = typename Tr::BlockT;

677 using FuncT = typename Tr::FuncT;

678 using RegionT = typename Tr::RegionT;

679 using RegionInfoT = typename Tr::RegionInfoT;

680 using DomTreeT = typename Tr::DomTreeT;

681 using DomTreeNodeT = typename Tr::DomTreeNodeT;

682 using PostDomTreeT = typename Tr::PostDomTreeT;

683 using DomFrontierT = typename Tr::DomFrontierT;

686 using SuccIterTy = typename BlockTraits::ChildIteratorType;

687 using PredIterTy = typename InvBlockTraits::ChildIteratorType;

688

691

693

696 TopLevelRegion(std::move(Arg.TopLevelRegion)),

697 BBtoRegion(std::move(Arg.BBtoRegion)) {

698 Arg.wipe();

699 }

700

702 DT = std::move(RHS.DT);

703 PDT = std::move(RHS.PDT);

704 DF = std::move(RHS.DF);

705 TopLevelRegion = std::move(RHS.TopLevelRegion);

706 BBtoRegion = std::move(RHS.BBtoRegion);

707 RHS.wipe();

708 return *this;

709 }

710

711 virtual ~RegionInfoBase();

712

713 DomTreeT *DT;

714 PostDomTreeT *PDT;

715 DomFrontierT *DF;

716

717

718 RegionT *TopLevelRegion = nullptr;

719

720

721 BBtoRegionMap BBtoRegion;

722

723protected:

724

725

726

727

728 template

730 if (!R)

731 return;

732 R->RI = &RI;

733 for (auto &SubR : *R)

735 }

736

737private:

738

739

740

741

742 void wipe() {

743 DT = nullptr;

744 PDT = nullptr;

745 DF = nullptr;

746 TopLevelRegion = nullptr;

747 BBtoRegion.clear();

748 }

749

750

751

752

753 void verifyBBMap(const RegionT *SR) const;

754

755

756

757

758 bool isCommonDomFrontier(BlockT *BB, BlockT *entry, BlockT *exit) const;

759

760

761

762 bool isRegion(BlockT *entry, BlockT *exit) const;

763

764

765

766 void insertShortCut(BlockT *entry, BlockT *exit, BBtoBBMap *ShortCut) const;

767

768

769

770 DomTreeNodeT *getNextPostDom(DomTreeNodeT *N, BBtoBBMap *ShortCut) const;

771

772

773 bool isTrivialRegion(BlockT *entry, BlockT *exit) const;

774

775

776 RegionT *createRegion(BlockT *entry, BlockT *exit);

777

778

779 void findRegionsWithEntry(BlockT *entry, BBtoBBMap *ShortCut);

780

781

782 void scanForRegions(FuncT &F, BBtoBBMap *ShortCut);

783

784

785 RegionT *getTopMostParent(RegionT *region);

786

787

788 void buildRegionsTree(DomTreeNodeT *N, RegionT *region);

789

790

791 virtual void updateStatistics(RegionT *R) = 0;

792

793

794 void calculate(FuncT &F);

795

796public:

799

802

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

805 void dump() const;

806#endif

807

809

810

811

812

813

814

816

817

818

819

820

822

823

824

825

826

827

828 RegionT *operator[](BlockT *BB) const;

829

830

831

832

833

835

836

837

838

839

840

842

843

844

845

846

847

850 }

851

852

853

854

855

857

858

859

860

861

863

865

866

867

868

870 if (TopLevelRegion)

871 TopLevelRegion->clearNodeCache();

872 }

873

875};

876

878public:

881

883 return this == reinterpret_cast<const RegionNode *>(&RN);

884 }

885};

886

888public:

890 Region *Parent = nullptr);

892

894 return &RN == reinterpret_cast<const RegionNode *>(this);

895 }

896};

897

899public:

901

903

906 }

907

909 Base::operator=(std::move(static_cast<Base &>(RHS)));

911 return *this;

912 }

913

915

916

919

920

922

925

926#ifndef NDEBUG

927

928

929

931

932

933

934

935

937#endif

938};

939

942

943public:

945

948

950

952

953

954

960 void dump() const;

961

962};

963

964

967

969

970public:

972

974};

975

976

979

980public:

982

984

986};

987

988

992};

993

994template <>

995template <>

998 assert(!isSubRegion() && "This is not a BasicBlock RegionNode!");

999 return getEntry();

1000}

1001

1002template <>

1003template <>

1006 assert(isSubRegion() && "This is not a subregion RegionNode!");

1008 return reinterpret_cast<Region *>(Unconst);

1009}

1010

1011template

1014 using BlockT = typename Tr::BlockT;

1015 using RegionT = typename Tr::RegionT;

1016

1017 if (Node.isSubRegion())

1018 return OS << Node.template getNodeAs()->getNameStr();

1019 else

1020 return OS << Node.template getNodeAs()->getName();

1021}

1022

1023extern template class RegionBase<RegionTraits>;

1024extern template class RegionNodeBase<RegionTraits>;

1025extern template class RegionInfoBase<RegionTraits>;

1026

1027}

1028

1029#endif

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

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

static RegisterPass< DebugifyFunctionPass > DF("debugify-function", "Attach debug info to a function")

This file defines the DenseMap class.

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

This file defines the little GraphTraits template class that should be specialized by classes that...

This header defines various interfaces for pass management in LLVM.

This file defines the PointerIntPair class.

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

API to communicate dependencies between analyses during invalidation.

A container for analyses that lazily runs them and caches their results.

Represent the analysis usage information of a pass.

LLVM Basic Block Representation.

const Instruction * getTerminator() const LLVM_READONLY

Returns the terminator instruction if the block is well formed or null if the block is not well forme...

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

Marker class to iterate over the elements of a Region in flat mode.

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

unsigned getNumSuccessors() const LLVM_READONLY

Return the number of successors that this instruction has.

Represents a single loop in the control flow graph.

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

PointerIntPair - This class implements a pair of a pointer and small integer.

PointerTy getPointer() const

PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...

A set of analyses that are preserved following a run of a transformation pass.

typename super::value_type value_type

BlockT * operator*() const

block_iterator_wrapper(super I)

block_iterator_wrapper(value_type Entry, value_type Exit)

A single entry single exit Region.

void replaceExit(BlockT *BB)

Replace the exit basic block of the region with the new basic block.

void clearNodeCache()

Clear the cache for BB RegionNodes.

std::string getNameStr() const

Returns the name of the Region.

block_range blocks()

Returns a range view of the basic blocks in the region.

BlockT * getExit() const

Get the exit BasicBlock of the Region.

void transferChildrenTo(RegionT *To)

Move all direct child nodes of this Region to another Region.

RegionNodeT * getBBNode(BlockT *BB) const

Get the BasicBlock RegionNode for a BasicBlock.

block_iterator_wrapper< true > const_block_iterator

block_iterator block_begin()

bool getExitingBlocks(SmallVectorImpl< BlockT * > &Exitings) const

Collect all blocks of this region's single exit edge, if existing.

RegionNodeT * getNode() const

Get the RegionNode representing the current Region.

iterator_range< element_iterator > elements()

block_iterator_wrapper< false > block_iterator

const_iterator end() const

const_block_iterator block_end() const

LoopT * outermostLoopInRegion(LoopT *L) const

Get the outermost loop in the region that contains a loop.

unsigned getDepth() const

Get the nesting level of this Region.

const_block_iterator block_begin() const

void replaceEntry(BlockT *BB)

Replace the entry basic block of the region with the new basic block.

void dump() const

Print the region to stderr.

block_iterator block_end()

void replaceEntryRecursive(BlockT *NewEntry)

Recursively replace the entry basic block of the region.

bool contains(const BlockT *BB) const

Check if the region contains a BasicBlock.

element_iterator element_begin()

void replaceExitRecursive(BlockT *NewExit)

Recursively replace the exit basic block of the region.

void verifyRegion() const

Verify if the region is a correct region.

RegionBase & operator=(const RegionBase &)=delete

RegionT * getParent() const

Get the parent of the Region.

RegionInfoT * getRegionInfo() const

Return the RegionInfo object, that belongs to this Region.

BlockT * getEntry() const

Get the entry BasicBlock of the Region.

void addSubRegion(RegionT *SubRegion, bool moveChildren=false)

Add a new subregion to this Region.

RegionBase(const RegionBase &)=delete

const_iterator begin() const

bool contains(const InstT *Inst) const

Check if the region contains an Instruction.

typename RegionSet::iterator iterator

element_iterator element_end()

df_iterator< const RegionNodeT *, df_iterator_default_set< const RegionNodeT * >, false, GraphTraits< const RegionNodeT * > > const_element_iterator

bool isSimple() const

Is this a simple region?

bool isTopLevelRegion() const

Check if a Region is the TopLevel region.

bool contains(const RegionT *SubRegion) const

Check if the region contains another region.

BlockT * getExitingBlock() const

Return the first block of this region's single exit edge, if existing.

~RegionBase()

Delete the Region and all its subregions.

iterator_range< const_block_iterator > const_block_range

iterator_range< const_element_iterator > elements() const

PrintStyle

PrintStyle - Print region in difference ways.

const_block_range blocks() const

Returns a range view of the basic blocks in the region.

RegionT * removeSubRegion(RegionT *SubRegion)

Remove a subregion from this Region.

typename RegionSet::const_iterator const_iterator

BlockT * getEnteringBlock() const

Return the first block of this region's single entry edge, if existing.

RegionT * getExpandedRegion() const

Return a new (non-canonical) region, that is obtained by joining this region with its predecessors.

void print(raw_ostream &OS, bool printTree=true, unsigned level=0, PrintStyle Style=PrintNone) const

Print the region.

RegionT * getSubRegionNode(BlockT *BB) const

Get the subregion that starts at a BasicBlock.

iterator_range< block_iterator > block_range

Analysis pass that exposes the RegionInfo for a function.

RegionInfo run(Function &F, FunctionAnalysisManager &AM)

Analysis that detects all canonical Regions.

RegionT * getCommonRegion(BlockT *A, BlockT *B) const

Find the smallest region that contains two basic blocks.

void updateRegionTree(RegionInfoT &RI, TheRegionT *R)

Update refences to a RegionInfoT held by the RegionT managed here.

void clearNodeCache()

Clear the Node Cache for all Regions.

BlockT * getMaxRegionExit(BlockT *BB) const

Return the exit of the maximal refined region, that starts at a BasicBlock.

static bool VerifyRegionInfo

void print(raw_ostream &OS) const

RegionT * getTopLevelRegion() const

RegionT * getRegionFor(BlockT *BB) const

Get the smallest region that contains a BasicBlock.

static RegionT::PrintStyle printStyle

RegionInfoBase & operator=(const RegionInfoBase &)=delete

void verifyAnalysis() const

void setRegionFor(BlockT *BB, RegionT *R)

Set the smallest region that surrounds a basic block.

RegionT * operator[](BlockT *BB) const

A shortcut for getRegionFor().

RegionInfoBase(const RegionInfoBase &)=delete

RegionT * getCommonRegion(RegionT *A, RegionT *B) const

Find the smallest region that contains two regions.

void releaseMemory() override

releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...

bool runOnFunction(Function &F) override

runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.

~RegionInfoPass() override

RegionInfo & getRegionInfo()

const RegionInfo & getRegionInfo() const

void verifyAnalysis() const override

verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...

void print(raw_ostream &OS, const Module *) const override

print - Print out the internal state of the pass.

void getAnalysisUsage(AnalysisUsage &AU) const override

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

Printer pass for the RegionInfo.

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

RegionInfo(RegionInfo &&Arg)

void view()

Opens a viewer to show the GraphViz visualization of the regions.

void viewOnly()

Opens a viewer to show the GraphViz visualization of this region without instructions in the BasicBlo...

void recalculate(Function &F, DominatorTree *DT, PostDominatorTree *PDT, DominanceFrontier *DF)

RegionInfo & operator=(RegionInfo &&RHS)

void updateStatistics(Region *R) final

bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)

Handle invalidation explicitly.

A RegionNode represents a subregion or a BasicBlock that is part of a Region.

typename Tr::RegionT RegionT

RegionNodeBase & operator=(const RegionNodeBase &)=delete

RegionNodeBase(RegionT *Parent, BlockT *Entry, bool isSubRegion=false)

Create a RegionNode.

bool isSubRegion() const

Is this RegionNode a subregion?

RegionT * getParent() const

Get the parent Region of this RegionNode.

T * getNodeAs() const

Get the content of this RegionNode.

RegionNodeBase(const RegionNodeBase &)=delete

typename Tr::BlockT BlockT

BlockT * getEntry() const

Get the entry BasicBlock of this RegionNode.

RegionNode(Region *Parent, BasicBlock *Entry, bool isSubRegion=false)

bool operator==(const Region &RN) const

bool operator==(const RegionNode &RN) const

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

reference operator*() const

typename GT::NodeRef value_type

A range adaptor for a pair of iterators.

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

This provides a very simple, boring adaptor for a begin and end iterator into a range type.

This is an optimization pass for GlobalISel generic memory operations.

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

df_iterator< T > df_begin(const T &G)

DomTreeNodeBase< BasicBlock > DomTreeNode

raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)

OutputIt move(R &&Range, OutputIt Out)

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

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

df_iterator< T > df_end(const T &G)

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

A CRTP mix-in that provides informational APIs needed for analysis passes.

A special type used by analysis passes to provide an address that identifies that particular analysis...

A CRTP mix-in to automatically provide informational APIs needed for passes.

Verifier pass for the RegionInfo.

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

static unsigned getNumSuccessors(BasicBlock *BB)

typename FuncT_::UnknownRegionTypeError BrokenT