DependenceGraphBuilder.h Source File (original) (raw)

14#ifndef LLVM_ANALYSIS_DEPENDENCEGRAPHBUILDER_H

15#define LLVM_ANALYSIS_DEPENDENCEGRAPHBUILDER_H

22namespace llvm {

33protected:

36private:

37 using NodeType = typename GraphType::NodeType;

38 using EdgeType = typename GraphType::EdgeType;

40public:

75 void computeInstructionOrdinals();

79 void createFineGrainedNodes();

83 void createDefUseEdges();

87 void createMemoryDependencyEdges();

91 void createAndConnectRootNode();

98 void createPiBlocks();

100

101

102

103

104

105

106

108

109

110 void sortNodesTopologically();

111

112protected:

113

115

116

118

119

120

122

123

125

126

128

129

131

132

133

135

136

138

139

141

142

143

145

146

147

149

150

152 const NodeType &B) const = 0;

153

154

155

157

158

161 "No ordinal computed for this instruction.");

163 }

164

165

170

171

173

174

177

178

179

181

182

183

185

186

188

189

191

192

193

195

196

197

199};

200

201}

202

203#endif

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

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

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

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

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

This file defines the DenseMap class.

Generic implementation of equivalence classes through the use Tarjan's efficient union-find algorithm...

This file defines the SmallVector class.

void createAndConnectRootNode()

Create a root node and add edges such that each node in the graph is reachable from the root.

void computeInstructionOrdinals()

Compute ordinal numbers for each instruction and store them in a map for future look up.

virtual const NodeListType & getNodesInPiBlock(const NodeType &N)=0

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

virtual void destroyEdge(EdgeType &E)

Deallocate memory of edge E.

Definition DependenceGraphBuilder.h:137

virtual EdgeType & createMemoryEdge(NodeType &Src, NodeType &Tgt)=0

Create a memory dependence edge going from Src to Tgt.

virtual bool shouldCreatePiBlocks() const

Return true if creation of pi-blocks are supported and desired, and false otherwise.

Definition DependenceGraphBuilder.h:144

virtual bool shouldSimplify() const

Return true if graph simplification step is requested, and false otherwise.

Definition DependenceGraphBuilder.h:148

DenseMap< Instruction *, NodeType * > InstToNodeMap

Map types to map instructions to nodes used when populating the graph.

Definition DependenceGraphBuilder.h:172

void sortNodesTopologically()

Topologically sort the graph nodes.

SmallVectorImpl< BasicBlock * > BasicBlockListType

Definition DependenceGraphBuilder.h:34

virtual NodeType & createFineGrainedNode(Instruction &I)=0

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

virtual EdgeType & createRootedEdge(NodeType &Src, NodeType &Tgt)=0

Create a rooted edge going from Src to Tgt .

void createFineGrainedNodes()

Create fine grained nodes.

virtual NodeType & createPiBlock(const NodeListType &L)=0

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

virtual NodeType & createRootNode()=0

Create the root node of the graph.

InstToOrdinalMap InstOrdinalMap

A mapping from each instruction to an ordinal number.

Definition DependenceGraphBuilder.h:194

DenseMap< NodeType *, size_t > NodeToOrdinalMap

Definition DependenceGraphBuilder.h:176

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

Definition DependenceGraphBuilder.h:44

virtual EdgeType & createDefUseEdge(NodeType &Src, NodeType &Tgt)=0

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

virtual ~AbstractDependenceGraphBuilder()=default

EquivalenceClasses< BasicBlock * > ClassesType

Definition DependenceGraphBuilder.h:41

void createMemoryDependencyEdges()

Analyze data dependencies that exist between memory loads or stores, in the graph nodes and create ed...

virtual void mergeNodes(NodeType &A, NodeType &B)=0

Append the content of node B into node A and remove B and the edge between A and B from the graph.

DependenceInfo & DI

Dependence information used to create memory dependence edges in the graph.

Definition DependenceGraphBuilder.h:184

void populate()

The main entry to the graph construction algorithm.

Definition DependenceGraphBuilder.h:60

const BasicBlockListType & BBList

The list of basic blocks to consider when building the graph.

Definition DependenceGraphBuilder.h:187

InstToNodeMap IMap

A mapping from instructions to the corresponding nodes in the graph.

Definition DependenceGraphBuilder.h:190

virtual void destroyNode(NodeType &N)

Deallocate memory of node N.

Definition DependenceGraphBuilder.h:140

size_t getOrdinal(Instruction &I)

Given an instruction I return its associated ordinal number.

Definition DependenceGraphBuilder.h:159

SmallVector< NodeType *, 4 > NodeListType

Definition DependenceGraphBuilder.h:42

void createDefUseEdges()

Analyze the def-use chains and create edges from the nodes containing definitions to the nodes contai...

size_t getOrdinal(NodeType &N)

Given a node N return its associated ordinal number.

Definition DependenceGraphBuilder.h:166

NodeToOrdinalMap NodeOrdinalMap

A mapping from nodes to an ordinal number.

Definition DependenceGraphBuilder.h:198

GraphType & Graph

Reference to the graph that gets built by a concrete implementation of this builder.

Definition DependenceGraphBuilder.h:180

DenseMap< Instruction *, size_t > InstToOrdinalMap

Map Types to map instruction/nodes to an ordinal number.

Definition DependenceGraphBuilder.h:175

virtual bool areNodesMergeable(const NodeType &A, const NodeType &B) const =0

Return true if it's safe to merge the two nodes.

void createPiBlocks()

Apply graph abstraction to groups of nodes that belong to a strongly connected component of the graph...

LLVM Basic Block Representation.

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

EquivalenceClasses - This represents a collection of equivalence classes and supports three efficient...

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

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

This is an optimization pass for GlobalISel generic memory operations.