DDG.cpp Source File (original) (raw)

17using namespace llvm;

22 "Simplify DDG by merging nodes that have less interesting edges."));

25 cl::desc("Create pi-block nodes."));

27#define DEBUG_TYPE "ddg"

41 assert(IList.empty() && "Expected the IList to be empty on entry.");

44 if (Pred(I))

50 PN->collectInstructions(Pred, TmpIList);

52 }

53 } else

55 return !IList.empty();

56}

59 const char *Out;

60 switch (K) {

62 Out = "single-instruction";

63 break;

65 Out = "multi-instruction";

66 break;

68 Out = "pi-block";

69 break;

71 Out = "root";

72 break;

74 Out = "?? (error)";

75 break;

76 }

77 OS << Out;

78 return OS;

79}

82 OS << "Node Address:" << &N << ":" << N.getKind() << "\n";

84 OS << " Instructions:\n";

86 OS.indent(2) << *I << "\n";

88 OS << "--- start of nodes in pi-block ---\n";

90 unsigned Count = 0;

91 for (const DDGNode *N : Nodes)

92 OS << *N << (++Count == Nodes.size() ? "" : "\n");

93 OS << "--- end of nodes in pi-block ---\n";

97 OS << (N.getEdges().empty() ? " Edges:none!\n" : " Edges:\n");

98 for (const auto &E : N.getEdges())

100 return OS;

101}

102

103

104

105

106

109 assert(InstList.empty() && "Expected empty list.");

110 InstList.push_back(&I);

111}

112

114 : DDGNode(N), InstList(N.InstList) {

117 "constructing from invalid simple node.");

118}

119

124 "constructing from invalid simple node.");

125}

126

128

129

130

131

132

135 assert(!NodeList.empty() && "pi-block node constructed with an empty list.");

136}

137

139 : DDGNode(N), NodeList(N.NodeList) {

141 "constructing from invalid pi-block node.");

142}

143

147 "constructing from invalid pi-block node.");

148}

149

151

152

153

154

155

157 const char *Out;

158 switch (K) {

160 Out = "def-use";

161 break;

163 Out = "memory";

164 break;

166 Out = "rooted";

167 break;

169 Out = "?? (error)";

170 break;

171 }

172 OS << Out;

173 return OS;

174}

175

177 OS << "[" << E.getKind() << "] to " << &E.getTargetNode() << "\n";

178 return OS;

179}

180

181

182

183

185

188

189

193 std::reverse(BBList.begin(), BBList.end());

195}

196

200 L.getHeader()->getName())

201 .str(),

202 D) {

203

204

210}

211

213 for (auto *N : Nodes) {

214 for (auto *E : *N)

215 delete E;

216 delete N;

217 }

218}

219

222 return false;

223

224

225

226

227

228

231 "Root node is already added. No more nodes can be added.");

232

235

236 if (Pi)

237 for (DDGNode *NI : Pi->getNodes())

238 PiBlockMap.insert(std::make_pair(NI, Pi));

239

240 return true;

241}

242

244 auto It = PiBlockMap.find(&N);

245 if (It == PiBlockMap.end())

246 return nullptr;

247 auto *Pi = It->second;

248 assert(!PiBlockMap.contains(Pi) && "Nested pi-blocks detected.");

249 return Pi;

250}

251

254

255

256 if (.getPiBlock(*Node))

257 OS << *Node << "\n";

258 OS << "\n";

259 return OS;

260}

261

262

263

264

265

267 const DDGNode &Tgt) const {

268

269

272 if (!SimpleSrc || !SimpleTgt)

273 return false;

274

275 return SimpleSrc->getLastInstruction()->getParent() ==

276 SimpleTgt->getFirstInstruction()->getParent();

277}

278

280 DDGEdge &EdgeToFold = A.back();

282 "Expected A to have a single edge to B.");

284 "Expected simple nodes");

285

286

288

289

291 Graph.connect(A, BE->getTargetNode(), *BE);

292

293 A.removeEdge(EdgeToFold);

297}

298

300

302

303

304

305

306

307

310 Function *F = L.getHeader()->getParent();

312 return std::make_unique(L, AR.LI, DI);

313}

315

319 OS << "'DDG' for loop '" << L.getHeader()->getName() << "':\n";

322}

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

static const Function * getParent(const Value *V)

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< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

SmallVector< BasicBlock *, 8 > BasicBlockListType

Definition DDG.cpp:184

static cl::opt< bool > CreatePiBlocks("ddg-pi-blocks", cl::init(true), cl::Hidden, cl::desc("Create pi-block nodes."))

static cl::opt< bool > SimplifyDDG("ddg-simplify", cl::init(true), cl::Hidden, cl::desc("Simplify DDG by merging nodes that have less interesting edges."))

This builds on the llvm/ADT/GraphTraits.h file to find the strongly connected components (SCCs) of a ...

virtual void destroyEdge(EdgeType &E)

virtual void destroyNode(NodeType &N)

DataDependenceGraph & Graph

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

LLVM_ABI PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)

Definition DDG.cpp:316

Analysis pass that builds the DDG for a loop.

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

DDG as a loop pass.

Definition DDG.cpp:308

std::unique_ptr< DataDependenceGraph > Result

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

Return true if the two nodes \pSrc and \pTgt are both simple nodes and the consecutive instructions a...

Definition DDG.cpp:266

bool shouldCreatePiBlocks() const final

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

Definition DDG.cpp:301

bool shouldSimplify() const final

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

Definition DDG.cpp:299

void mergeNodes(DDGNode &Src, DDGNode &Tgt) final

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

Definition DDG.cpp:279

Data Dependency Graph Edge.

EdgeKind

The kind of edge in the DDG.

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

SmallVectorImpl< Instruction * > InstructionListType

NodeKind getKind() const

Getter for the kind of this node.

bool collectInstructions(llvm::function_ref< bool(Instruction *)> const &Pred, InstructionListType &IList) const

Collect a list of instructions, in IList, for which predicate Pred evaluates to true when iterating o...

Definition DDG.cpp:38

Represent an edge in the directed graph.

const NodeType & getTargetNode() const

Retrieve the target node this edge connects to.

Represent a node in the directed graph.

const PiBlockDDGNode * getPiBlock(const NodeType &N) const

If node N belongs to a pi-block return a pointer to the pi-block, otherwise return null.

Definition DDG.cpp:243

~DataDependenceGraph() override

Definition DDG.cpp:212

bool addNode(NodeType &N)

Add node N to the graph, if it's not added yet, and keep track of the root node as well as pi-blocks ...

Definition DDG.cpp:220

DataDependenceGraph()=delete

DependenceGraphInfo()=delete

StringRef getName() const

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

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

Store the result of a depth first search within basic blocks contained by a single loop.

RPOIterator beginRPO() const

Reverse iterate over the cached postorder blocks.

void perform(const LoopInfo *LI)

Traverse the loop blocks and store the DFS result.

RPOIterator endRPO() const

Represents a single loop in the control flow graph.

Subclass of DDGNode representing a pi-block.

~PiBlockDDGNode() override

Definition DDG.cpp:150

SmallVector< DDGNode *, 4 > PiNodeList

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

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

~SimpleDDGNode() override

Definition DDG.cpp:127

void push_back(const T &Elt)

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

Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...

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.

raw_ostream & indent(unsigned NumSpaces)

indent - Insert 'NumSpaces' spaces.

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

decltype(auto) dyn_cast(const From &Val)

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

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

Convenience function for iterating over sub-ranges.

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

Wrapper function to append range R to container C.

scc_iterator< T > scc_begin(const T &G)

Construct the begin iterator for a deduced graph type T.

AnalysisManager< Loop, LoopStandardAnalysisResults & > LoopAnalysisManager

The loop analysis manager.

FunctionAddr VTableAddr Count

bool isa(const From &Val)

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

scc_iterator< T > scc_end(const T &G)

Construct the end iterator for a deduced graph type T.

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.

decltype(auto) cast(const From &Val)

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

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

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

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