1 //===- DependenceGraphBuilder.cpp ------------------------------------------==//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
10 //===----------------------------------------------------------------------===//
25 STATISTIC(TotalDefUseEdges, "Number of def-use 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.");
37 //===--------------------------------------------------------------------===//
39 //===--------------------------------------------------------------------===//
76   // the iteration order. For example for a graph {A -> B}, an edge from the  in createAndConnectRootNode()
78   // not result in minimal number of edges, this approach saves compile-time  in createAndConnectRootNode()
95   LLVM_DEBUG(dbgs() << "==== Start of Creation of Pi-Blocks ===\n");  in createPiBlocks()
98   // 1. Identify SCCs and for each SCC create a pi-block node containing all  in createPiBlocks()
101   //    reconnect them to the pi-block node.  in createPiBlocks()
109   // those lists to create the pi-block nodes. Each element of the list is a  in createPiBlocks()
119     LLVM_DEBUG(dbgs() << "Creating pi-block node with " << NL.size()  in createPiBlocks()
137     // that are outside of the SCC and look for edges that cross the two sets.  in createPiBlocks()
152       // keep one edge from that node to the pi-block node. Similarly, if  in createPiBlocks()
154       // we only keep one edge from the pi-block node to the outside node.  in createPiBlocks()
156       // for each type of edge supported, using a two-dimensional boolean  in createPiBlocks()
181         if (!Src->hasEdgeTo(*Dst))  in createPiBlocks()
192         Src->findEdgesTo(*Dst, EL);  in createPiBlocks()
194           EdgeKind Kind = OldEdge->getKind();  in createPiBlocks()
205           Src->removeEdge(*OldEdge);  in createPiBlocks()
212         // Process incoming edges incident to the pi-block node.  in createPiBlocks()
215         // Process edges that are coming out of the pi-block node.  in createPiBlocks()
225   LLVM_DEBUG(dbgs() << "==== End of Creation of Pi-Blocks ===\n");  in createPiBlocks()
231     N->collectInstructions([](const Instruction *I) { return true; }, SrcIList);  in createDefUseEdges()
234     // duplicate def-use edges when more than one instruction in a target node  in createDefUseEdges()
239       for (User *U : II->users()) {  in createDefUseEdges()
245           DstNode = IMap.find(UI)->second;  in createDefUseEdges()
254               << "skipped def-use edge since the sink" << *UI  in createDefUseEdges()
263                      << "skipped def-use edge since the sink and the source ("  in createDefUseEdges()
281     return I->mayReadOrWriteMemory();  in createMemoryDependencyEdges()
285     (*SrcIt)->collectInstructions(isMemoryAccess, SrcIList);  in createMemoryDependencyEdges()
293       (*DstIt)->collectInstructions(isMemoryAccess, DstIList);  in createMemoryDependencyEdges()
304           // If we have a dependence with its left-most non-'=' direction  in createMemoryDependencyEdges()
339           if (D->isConfused())  in createMemoryDependencyEdges()
341           else if (D->isOrdered() && !D->isLoopIndependent()) {  in createMemoryDependencyEdges()
343             for (unsigned Level = 1; Level <= D->getLevels(); ++Level) {  in createMemoryDependencyEdges()
344               if (D->getDirection(Level) == Dependence::DVEntry::EQ)  in createMemoryDependencyEdges()
346               else if (D->getDirection(Level) == Dependence::DVEntry::GT) {  in createMemoryDependencyEdges()
351               } else if (D->getDirection(Level) == Dependence::DVEntry::LT)  in createMemoryDependencyEdges()
369         // unique edge that we can create between these two nodes, so we  in createMemoryDependencyEdges()
384   // an out-degree of one (in terms of def-use edges), and then ignoring those  in simplify()
385   // whose targets have an in-degree more than one. Each node in the resulting  in simplify()
390   // A mapping between nodes and their in-degree. To save space, this map  in simplify()
395     if (N->getEdges().size() != 1)  in simplify()
397     EdgeType &Edge = N->back();  in simplify()
402     // Insert an element into the in-degree map and initialize to zero. The  in simplify()
409            << "\nNode with single outgoing def-use edge:\n";  in simplify()
417       NodeType *Tgt = &E->getTargetNode();  in simplify()
420         ++(TgtIT->second);  in simplify()
425     dbgs() << "Size of target in-degree map:" << TargetInDegreeMap.size()  in simplify()
426            << "\nContent of in-degree map:\n";  in simplify()
428       dbgs() << I.first << " --> " << I.second << "\n";  in simplify()
445            "Expected target to be in the in-degree map.");  in simplify()
465     // {(a)->(b), (b)->(c), (c)->(d), ...} and the worklist is initially {b, a},  in simplify()
468     // {(a,b,c) -> d}  in simplify()
484   // If we don't create pi-blocks, then we may not have a DAG.  in sortNodesTopologically()
491     if (N->getKind() == NodeKind::PiBlock) {  in sortNodesTopologically()
492       // Put members of the pi-block right after the pi-block itself, for  in sortNodesTopologically()