22 #define DEBUG_TYPE "dgb"
24 STATISTIC(TotalGraphs,
"Number of dependence graphs created.");
25 STATISTIC(TotalDefUseEdges,
"Number of def-use edges created.");
26 STATISTIC(TotalMemoryEdges,
"Number of memory dependence edges created.");
27 STATISTIC(TotalFineGrainedNodes,
"Number of fine-grained nodes created.");
28 STATISTIC(TotalPiBlockNodes,
"Number of pi-block nodes created.");
30 "Number of confused memory dependencies between two nodes.");
32 "Number of times the source and sink of dependence was reversed to "
33 "expose cycles in the graph.");
44 size_t NextOrdinal = 1;
45 for (
auto *
BB : BBList)
47 InstOrdinalMap.insert(std::make_pair(&
I, NextOrdinal++));
53 assert(IMap.empty() &&
"Expected empty instruction map at start");
56 auto &NewNode = createFineGrainedNode(
I);
57 IMap.insert(std::make_pair(&
I, &NewNode));
58 NodeOrdinalMap.insert(std::make_pair(&NewNode, getOrdinal(
I)));
59 ++TotalFineGrainedNodes;
80 auto &RootNode = createRootNode();
82 for (
auto *
N : Graph) {
87 createRootedEdge(RootNode, *
N);
92 if (!shouldCreatePiBlocks())
120 <<
" nodes in it.\n");
126 return getOrdinal(*
LHS) < getOrdinal(*
RHS);
129 NodeType &PiNode = createPiBlock(
NL);
138 for (NodeType *
N : Graph) {
141 if (*
N == PiNode || NodesInSCC.
count(
N))
158 using EdgeKind =
typename EdgeType::EdgeKind;
162 auto createEdgeOfKind = [
this](NodeType &Src, NodeType &Dst,
165 case EdgeKind::RegisterDefUse:
166 createDefUseEdge(Src, Dst);
168 case EdgeKind::MemoryDependence:
169 createMemoryEdge(Src, Dst);
171 case EdgeKind::Rooted:
172 createRootedEdge(Src, Dst);
179 auto reconnectEdges = [&](NodeType *Src, NodeType *Dst, NodeType *New,
181 if (!Src->hasEdgeTo(*Dst))
184 dbgs() <<
"reconnecting("
185 << (Dir == Direction::Incoming ?
"incoming)" :
"outgoing)")
186 <<
":\nSrc:" << *Src <<
"\nDst:" << *Dst <<
"\nNew:" << *New
188 assert((Dir == Direction::Incoming || Dir == Direction::Outgoing) &&
189 "Invalid direction.");
192 Src->findEdgesTo(*Dst, EL);
193 for (EdgeType *OldEdge : EL) {
194 EdgeKind
Kind = OldEdge->getKind();
195 if (!EdgeAlreadyCreated[Dir][
Kind]) {
196 if (Dir == Direction::Incoming) {
197 createEdgeOfKind(*Src, *New,
Kind);
199 }
else if (Dir == Direction::Outgoing) {
200 createEdgeOfKind(*New, *Dst,
Kind);
203 EdgeAlreadyCreated[Dir][
Kind] =
true;
205 Src->removeEdge(*OldEdge);
206 destroyEdge(*OldEdge);
207 LLVM_DEBUG(
dbgs() <<
"removed old edge between Src and Dst.\n\n");
211 for (NodeType *SCCNode :
NL) {
213 reconnectEdges(
N, SCCNode, &PiNode, Direction::Incoming);
216 reconnectEdges(SCCNode,
N, &PiNode, Direction::Outgoing);
222 InstOrdinalMap.clear();
223 NodeOrdinalMap.clear();
229 for (NodeType *
N : Graph) {
231 N->collectInstructions([](
const Instruction *
I) {
return true; }, SrcIList);
243 NodeType *DstNode =
nullptr;
244 if (IMap.find(UI) != IMap.end())
245 DstNode = IMap.find(UI)->second;
254 <<
"skipped def-use edge since the sink" << *UI
255 <<
" is outside the range of instructions being considered.\n");
263 <<
"skipped def-use edge since the sink and the source ("
264 <<
N <<
") are the same.\n");
268 if (VisitedTargets.
insert(DstNode).second) {
269 createDefUseEdge(*
N, *DstNode);
279 using DGIterator =
typename G::iterator;
281 return I->mayReadOrWriteMemory();
283 for (DGIterator SrcIt = Graph.begin(),
E = Graph.end(); SrcIt !=
E; ++SrcIt) {
285 (*SrcIt)->collectInstructions(isMemoryAccess, SrcIList);
286 if (SrcIList.empty())
289 for (DGIterator DstIt = SrcIt; DstIt !=
E; ++DstIt) {
290 if (**SrcIt == **DstIt)
293 (*DstIt)->collectInstructions(isMemoryAccess, DstIList);
294 if (DstIList.empty())
296 bool ForwardEdgeCreated =
false;
297 bool BackwardEdgeCreated =
false;
300 auto D = DI.depends(ISrc, IDst,
true);
310 auto createConfusedEdges = [&](NodeType &Src, NodeType &Dst) {
311 if (!ForwardEdgeCreated) {
312 createMemoryEdge(Src, Dst);
315 if (!BackwardEdgeCreated) {
316 createMemoryEdge(Dst, Src);
319 ForwardEdgeCreated = BackwardEdgeCreated =
true;
320 ++TotalConfusedEdges;
323 auto createForwardEdge = [&](NodeType &Src, NodeType &Dst) {
324 if (!ForwardEdgeCreated) {
325 createMemoryEdge(Src, Dst);
328 ForwardEdgeCreated =
true;
331 auto createBackwardEdge = [&](NodeType &Src, NodeType &Dst) {
332 if (!BackwardEdgeCreated) {
333 createMemoryEdge(Dst, Src);
336 BackwardEdgeCreated =
true;
340 createConfusedEdges(**SrcIt, **DstIt);
341 else if (
D->isOrdered() && !
D->isLoopIndependent()) {
342 bool ReversedEdge =
false;
347 createBackwardEdge(**SrcIt, **DstIt);
349 ++TotalEdgeReversals;
354 createConfusedEdges(**SrcIt, **DstIt);
359 createForwardEdge(**SrcIt, **DstIt);
361 createForwardEdge(**SrcIt, **DstIt);
364 if (ForwardEdgeCreated && BackwardEdgeCreated)
371 if (ForwardEdgeCreated && BackwardEdgeCreated)
379 if (!shouldSimplify())
394 for (NodeType *
N : Graph) {
395 if (
N->getEdges().size() != 1)
397 EdgeType &Edge =
N->back();
398 if (!Edge.isDefUse())
400 CandidateSourceNodes.
insert(
N);
404 TargetInDegreeMap.
insert({&Edge.getTargetNode(), 0});
408 dbgs() <<
"Size of candidate src node list:" << CandidateSourceNodes.
size()
409 <<
"\nNode with single outgoing def-use edge:\n";
410 for (NodeType *
N : CandidateSourceNodes) {
415 for (NodeType *
N : Graph) {
416 for (EdgeType *
E : *
N) {
417 NodeType *Tgt = &
E->getTargetNode();
418 auto TgtIT = TargetInDegreeMap.
find(Tgt);
419 if (TgtIT != TargetInDegreeMap.
end())
425 dbgs() <<
"Size of target in-degree map:" << TargetInDegreeMap.
size()
426 <<
"\nContent of in-degree map:\n";
427 for (
auto &
I : TargetInDegreeMap) {
428 dbgs() <<
I.first <<
" --> " <<
I.second <<
"\n";
433 CandidateSourceNodes.
end());
434 while (!Worklist.empty()) {
435 NodeType &Src = *Worklist.pop_back_val();
438 if (!CandidateSourceNodes.
erase(&Src))
441 assert(Src.getEdges().size() == 1 &&
442 "Expected a single edge from the candidate src node.");
443 NodeType &Tgt = Src.back().getTargetNode();
444 assert(TargetInDegreeMap.
find(&Tgt) != TargetInDegreeMap.
end() &&
445 "Expected target to be in the in-degree map.");
447 if (TargetInDegreeMap[&Tgt] != 1)
450 if (!areNodesMergeable(Src, Tgt))
455 if (Tgt.hasEdgeTo(Src))
458 LLVM_DEBUG(
dbgs() <<
"Merging:" << Src <<
"\nWith:" << Tgt <<
"\n");
460 mergeNodes(Src, Tgt);
472 if (CandidateSourceNodes.
erase(&Tgt)) {
473 Worklist.push_back(&Src);
474 CandidateSourceNodes.
insert(&Src);
475 LLVM_DEBUG(
dbgs() <<
"Putting " << &Src <<
" back in the worklist.\n");
485 if (!shouldCreatePiBlocks())
491 if (
N->getKind() == NodeKind::PiBlock) {
497 NodesInPO.push_back(
N);
500 size_t OldSize = Graph.Nodes.size();
503 if (Graph.Nodes.size() != OldSize)
505 "Expected the number of nodes to stay the same after the sort");