DDG.h Source File (original) (raw)

13#ifndef LLVM_ANALYSIS_DDG_H

14#define LLVM_ANALYSIS_DDG_H

23namespace llvm {

46public:

66 DGNode::operator=(std::move(N));

67 Kind = N.Kind;

68 return *this;

69 }

80protected:

84private:

86};

103

104

107

108public:

114

116

119 InstList = std::move(N.InstList);

120 return *this;

121 }

122

123

125 assert(!InstList.empty() && "Instruction List is empty.");

126 return InstList;

127 }

130 static_cast<const SimpleDDGNode *>(this)->getInstructions());

131 }

132

133

136

137

143

144private:

145

147 setKind((InstList.size() == 0 && Input.size() == 1)

148 ? NodeKind::SingleInstruction

149 : NodeKind::MultiInstruction);

151 }

152 void appendInstructions(const SimpleDDGNode &Input) {

153 appendInstructions(Input.getInstructions());

154 }

155

156

157 SmallVector<Instruction *, 2> InstList;

158};

159

160

161

162

163

164

165

166

168public:

170

176

178

181 NodeList = std::move(N.NodeList);

182 return *this;

183 }

184

185

187 assert(!NodeList.empty() && "Node list is empty.");

188 return NodeList;

189 }

194

195

199

200private:

201

203};

204

205

206

207

208

209

211public:

212

220

226

229 Kind = E.Kind;

230 return *this;

231 }

232

233

235

236

238

239

241

242

243

245

246private:

247 EdgeKind Kind;

248};

249

250

251

253public:

255

263

264

266

267

269 assert(Root && "Root node is not available yet. Graph construction may "

270 "still be in progress\n");

271 return *Root;

272 }

273

274

275

276

279

280

281

282

284 const NodeType &Dst) const;

285

286protected:

287

289

290

291

292

294

295

296

297 NodeType *Root = nullptr;

298};

299

301

302

306

307public:

310

318

319

320

321 const PiBlockDDGNode *getPiBlock(const NodeType &N) const;

322

323protected:

324

325

326

327 bool addNode(NodeType &N);

328

329private:

331

332

333

334 PiBlockMapType PiBlockMap;

335};

336

337

338

339

340

341

342

345public:

351 assert(RN && "Failed to allocate memory for DDG root node.");

352 Graph.addNode(*RN);

353 return *RN;

354 }

357 assert(SN && "Failed to allocate memory for simple DDG node.");

358 Graph.addNode(*SN);

359 return *SN;

360 }

363 assert(Pi && "Failed to allocate memory for pi-block node.");

364 Graph.addNode(*Pi);

365 return *Pi;

366 }

369 assert(E && "Failed to allocate memory for edge");

370 Graph.connect(Src, Tgt, *E);

371 return *E;

372 }

375 assert(E && "Failed to allocate memory for edge");

376 Graph.connect(Src, Tgt, *E);

377 return *E;

378 }

381 assert(E && "Failed to allocate memory for edge");

383 Graph.connect(Src, Tgt, *E);

384 return *E;

385 }

386

389 assert(PiNode && "Expected a pi-block node.");

390 return PiNode->getNodes();

391 }

392

393

394

395 bool areNodesMergeable(const DDGNode &Src, const DDGNode &Tgt) const final;

397 bool shouldSimplify() const final;

398 bool shouldCreatePiBlocks() const final;

399};

400

406

407

408

409

410

411

413public:

414 using Result = std::unique_ptr;

417

418private:

421};

422

423

425public:

431

432private:

434};

435

436

437

438

439

440template

442 const NodeType &Src, const NodeType &Dst, DependenceList &Deps) const {

443 assert(Deps.empty() && "Expected empty output list at the start.");

444

445

447 auto isMemoryAccess = [](const Instruction *I) {

448 return I->mayReadOrWriteMemory();

449 };

450 Src.collectInstructions(isMemoryAccess, SrcIList);

451 Dst.collectInstructions(isMemoryAccess, DstIList);

452

453 for (auto *SrcI : SrcIList)

454 for (auto *DstI : DstIList)

455 if (auto Dep =

458

459 return !Deps.empty();

460}

461

462template

463std::string

465 const NodeType &Dst) const {

466 std::string Str;

470 return Str;

471 interleaveComma(Deps, OS, [&](const std::unique_ptr &D) {

472 D->dump(OS);

473

474

475 if (Str.back() == '\n')

476 Str.pop_back();

477 });

478

479 return Str;

480}

481

482

483

484

485

486

489

491 return &P->getTargetNode();

492 }

493

494

495

499

507

509 return N->begin();

510 }

512};

513

514template <>

521 return DG->begin();

522 }

524};

525

526

529

531 return &P->getTargetNode();

532 }

533

534

535

539

547

549 return N->begin();

550 }

552};

553

554template <>

562 return DG->begin();

563 }

565 return DG->end();

566 }

567};

568

569}

570

571#endif

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

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

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

This file defines the DenseMap class.

SmallVector< Instruction *, 2 > InstructionListType

This file defines the interface and a base class implementation for a directed graph.

This header provides classes for managing per-loop analyses.

The Input class is used to parse a yaml document into in-memory structs and vectors.

This abstract builder class defines a set of high-level steps for creating DDG-like graphs.

SmallVectorImpl< BasicBlock * > BasicBlockListType

AbstractDependenceGraphBuilder(DataDependenceGraph &G, DependenceInfo &D, const BasicBlockListType &BBs)

SmallVector< NodeType *, 4 > NodeListType

DataDependenceGraph & Graph

static bool isRequired()

Definition DDG.h:430

DDGAnalysisPrinterPass(raw_ostream &OS)

Definition DDG.h:426

Analysis pass that builds the DDG for a loop.

Definition DDG.h:412

LLVM_ABI Result run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR)

DDG as a loop pass.

std::unique_ptr< DataDependenceGraph > Result

Definition DDG.h:414

DDGNode & createPiBlock(const NodeListType &L) final

Create a pi-block node in the graph representing a group of nodes in an SCC of the graph.

Definition DDG.h:361

DDGNode & createFineGrainedNode(Instruction &I) final

Create an atomic node in the graph given a single instruction.

Definition DDG.h:355

DDGBuilder(DataDependenceGraph &G, DependenceInfo &D, const BasicBlockListType &BBs)

Definition DDG.h:346

DDGEdge & createMemoryEdge(DDGNode &Src, DDGNode &Tgt) final

Create a memory dependence edge going from Src to Tgt.

Definition DDG.h:373

DDGEdge & createRootedEdge(DDGNode &Src, DDGNode &Tgt) final

Create a rooted edge going from Src to Tgt .

Definition DDG.h:379

DDGNode & createRootNode() final

Create the root node of the graph.

Definition DDG.h:349

const NodeListType & getNodesInPiBlock(const DDGNode &N) final

Given a pi-block node, return a vector of all the nodes contained within it.

Definition DDG.h:387

DDGEdge & createDefUseEdge(DDGNode &Src, DDGNode &Tgt) final

Create a def-use edge going from Src to Tgt.

Definition DDG.h:367

Data Dependency Graph Edge.

Definition DDG.h:210

DDGEdge & operator=(DDGEdge &&E)

Definition DDG.h:227

bool isDefUse() const

Return true if this is a def-use edge, and false otherwise.

Definition DDG.h:237

bool isRooted() const

Return true if this is an edge stemming from the root node, and false otherwise.

Definition DDG.h:244

EdgeKind getKind() const

Get the edge kind.

Definition DDG.h:234

EdgeKind

The kind of edge in the DDG.

Definition DDG.h:213

@ RegisterDefUse

Definition DDG.h:215

@ Rooted

Definition DDG.h:217

@ Unknown

Definition DDG.h:214

@ MemoryDependence

Definition DDG.h:216

@ Last

Definition DDG.h:218

DDGEdge(DDGEdge &&E)

Definition DDG.h:224

bool isMemoryDependence() const

Return true if this is a memory dependence edge, and false otherwise.

Definition DDG.h:240

DDGEdge(const DDGEdge &E)

Definition DDG.h:223

DDGEdge(DDGNode &N, EdgeKind K)

Definition DDG.h:222

DDGEdge(DDGNode &N)=delete

DDGEdge & operator=(const DDGEdge &E)=default

Data Dependence Graph Node The graph can represent the following types of nodes:

Definition DDG.h:45

DDGNode & operator=(DDGNode &&N)

Definition DDG.h:65

DDGNode & operator=(const DDGNode &N)=default

DDGNode(const DDGNode &N)=default

DDGNode(DDGNode &&N)

Definition DDG.h:60

SmallVectorImpl< Instruction * > InstructionListType

Definition DDG.h:47

NodeKind getKind() const

Getter for the kind of this node.

Definition DDG.h:72

NodeKind

Definition DDG.h:49

@ PiBlock

Definition DDG.h:53

@ MultiInstruction

Definition DDG.h:52

@ SingleInstruction

Definition DDG.h:51

@ Unknown

Definition DDG.h:50

@ Root

Definition DDG.h:54

DDGNode(const NodeKind K)

Definition DDG.h:58

void setKind(NodeKind K)

Setter for the kind of this node.

Definition DDG.h:82

Represent an edge in the directed graph.

DGEdge< DDGNode, DDGEdge > & operator=(const DGEdge< DDGNode, DDGEdge > &E)

Represent a node in the directed graph.

typename EdgeListTy::const_iterator const_iterator

typename EdgeListTy::iterator iterator

Data Dependency Graph.

Definition DDG.h:303

DataDependenceGraph(DataDependenceGraph &&G)

Definition DDG.h:313

DataDependenceGraph(const DataDependenceGraph &G)=delete

DDGEdge EdgeType

Definition DDG.h:309

DDGNode NodeType

Definition DDG.h:308

friend class DDGBuilder

Definition DDG.h:305

DataDependenceGraph()=delete

Encapsulate some common data and functionality needed for different variations of data dependence gra...

Definition DDG.h:252

std::string getDependenceString(const NodeType &Src, const NodeType &Dst) const

Return a string representing the type of dependence that the dependence analysis identified between t...

Definition DDG.h:464

const DependenceInfo DI

Definition DDG.h:293

NodeType & getRoot() const

Return the root node of the graph.

Definition DDG.h:268

DependenceGraphInfo()=delete

DependenceGraphInfo(DependenceGraphInfo &&G)

Definition DDG.h:260

StringRef getName() const

Return the label that is used to name this graph.

Definition DDG.h:265

SmallVector< std::unique_ptr< Dependence >, 1 > DependenceList

Definition DDG.h:254

DependenceGraphInfo(const DependenceGraphInfo &G)=delete

DependenceGraphInfo(const std::string &N, const DependenceInfo &DepInfo)

Definition DDG.h:258

virtual ~DependenceGraphInfo()=default

DDGNode * Root

Definition DDG.h:297

bool getDependencies(const NodeType &Src, const NodeType &Dst, DependenceList &Deps) const

Collect all the data dependency infos coming from any pair of memory accesses from Src to Dst,...

Definition DDG.h:441

std::string Name

Definition DDG.h:288

DependenceInfo - This class is the main dependence-analysis driver.

const_iterator begin() const

const_iterator end() const

typename NodeListTy::iterator iterator

typename NodeListTy::const_iterator const_iterator

This class provides an interface for updating the loop pass manager based on mutations to the loop ne...

Represents a single loop in the control flow graph.

Subclass of DDGNode representing a pi-block.

Definition DDG.h:167

PiBlockDDGNode & operator=(PiBlockDDGNode &&N)

Definition DDG.h:179

const PiNodeList & getNodes() const

Get the list of nodes in this pi-block.

Definition DDG.h:186

static bool classof(const DDGNode *N)

Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.

Definition DDG.h:196

PiBlockDDGNode & operator=(const PiBlockDDGNode &N)=default

SmallVector< DDGNode *, 4 > PiNodeList

Definition DDG.h:169

PiNodeList & getNodes()

Definition DDG.h:190

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

Subclass of DDGNode representing the root node of the graph.

Definition DDG.h:90

RootDDGNode()

Definition DDG.h:92

static bool classof(const DDGNode *N)

Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.

Definition DDG.h:98

RootDDGNode(const RootDDGNode &N)=delete

static bool classof(const RootDDGNode *N)

Definition DDG.h:101

~RootDDGNode() override=default

RootDDGNode(RootDDGNode &&N)

Definition DDG.h:94

Subclass of DDGNode representing single or multi-instruction nodes.

Definition DDG.h:105

Instruction * getFirstInstruction() const

Get the first/last instruction in the node.

Definition DDG.h:134

SimpleDDGNode & operator=(const SimpleDDGNode &N)=default

const InstructionListType & getInstructions() const

Get the list of instructions in this node.

Definition DDG.h:124

SimpleDDGNode & operator=(SimpleDDGNode &&N)

Definition DDG.h:117

static bool classof(const DDGNode *N)

Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.

Definition DDG.h:138

static bool classof(const SimpleDDGNode *N)

Definition DDG.h:142

InstructionListType & getInstructions()

Definition DDG.h:128

Instruction * getLastInstruction() const

Definition DDG.h:135

friend class DDGBuilder

Definition DDG.h:106

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

void push_back(const T &Elt)

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

StringRef - Represent a constant reference to a string, i.e.

An efficient, type-erasing, non-owning reference to a callable.

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

A raw_ostream that writes to an std::string.

This is an optimization pass for GlobalISel generic memory operations.

DGEdge< DDGNode, DDGEdge > DDGEdgeBase

Definition DDG.h:30

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

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

Wrapper function to append range R to container C.

void interleaveComma(const Container &c, StreamT &os, UnaryFunctor each_fn)

DirectedGraph< DDGNode, DDGEdge > DDGBase

Definition DDG.h:31

AnalysisManager< Loop, LoopStandardAnalysisResults & > LoopAnalysisManager

The loop analysis manager.

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

OutputIt move(R &&Range, OutputIt Out)

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

DGNode< DDGNode, DDGEdge > DDGNodeBase

Definition DDG.h:29

DependenceGraphInfo< DDGNode > DDGInfo

Definition DDG.h:300

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

Determine the kind of a node from its type.

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...

DDGNode::iterator ChildEdgeIteratorType

Definition DDG.h:498

mapped_iterator< DDGNode::iterator, decltype(&DDGGetTargetNode)> ChildIteratorType

Definition DDG.h:496

static DDGNode * DDGGetTargetNode(DGEdge< DDGNode, DDGEdge > *P)

Definition DDG.h:490

static ChildIteratorType child_end(NodeRef N)

Definition DDG.h:504

static ChildEdgeIteratorType child_edge_begin(NodeRef N)

Definition DDG.h:508

static ChildEdgeIteratorType child_edge_end(NodeRef N)

Definition DDG.h:511

static ChildIteratorType child_begin(NodeRef N)

Definition DDG.h:501

DDGNode * NodeRef

Definition DDG.h:488

static NodeRef getEntryNode(NodeRef N)

Definition DDG.h:500

static nodes_iterator nodes_end(DataDependenceGraph *DG)

Definition DDG.h:523

DataDependenceGraph::iterator nodes_iterator

Definition DDG.h:516

static nodes_iterator nodes_begin(DataDependenceGraph *DG)

Definition DDG.h:520

static NodeRef getEntryNode(DataDependenceGraph *DG)

Definition DDG.h:517

static ChildIteratorType child_end(NodeRef N)

Definition DDG.h:544

static const DDGNode * DDGGetTargetNode(const DGEdge< DDGNode, DDGEdge > *P)

Definition DDG.h:530

DDGNode::const_iterator ChildEdgeIteratorType

Definition DDG.h:538

static ChildEdgeIteratorType child_edge_end(NodeRef N)

Definition DDG.h:551

static ChildEdgeIteratorType child_edge_begin(NodeRef N)

Definition DDG.h:548

mapped_iterator< DDGNode::const_iterator, decltype(&DDGGetTargetNode)> ChildIteratorType

Definition DDG.h:536

const DDGNode * NodeRef

Definition DDG.h:528

static NodeRef getEntryNode(NodeRef N)

Definition DDG.h:540

static ChildIteratorType child_begin(NodeRef N)

Definition DDG.h:541

static nodes_iterator nodes_begin(const DataDependenceGraph *DG)

Definition DDG.h:561

DataDependenceGraph::const_iterator nodes_iterator

Definition DDG.h:557

static NodeRef getEntryNode(const DataDependenceGraph *DG)

Definition DDG.h:558

static nodes_iterator nodes_end(const DataDependenceGraph *DG)

Definition DDG.h:564

typename DataDependenceGraph *::UnknownGraphTypeError NodeRef

The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...

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