1 //===- DependenceGraphBuilder.cpp ------------------------------------------==//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 // This file implements common steps of the build algorithm for construction
9 // of dependence graphs such as DDG and PDG.
10 //===----------------------------------------------------------------------===//
11 
12 #include "llvm/Analysis/DependenceGraphBuilder.h"
13 #include "llvm/ADT/SCCIterator.h"
14 #include "llvm/ADT/Statistic.h"
15 #include "llvm/Analysis/DDG.h"
16 
17 using namespace llvm;
18 
19 #define DEBUG_TYPE "dgb"
20 
21 STATISTIC(TotalGraphs, "Number of dependence graphs created.");
22 STATISTIC(TotalDefUseEdges, "Number of def-use edges created.");
23 STATISTIC(TotalMemoryEdges, "Number of memory dependence edges created.");
24 STATISTIC(TotalFineGrainedNodes, "Number of fine-grained nodes created.");
25 STATISTIC(TotalConfusedEdges,
26           "Number of confused memory dependencies between two nodes.");
27 STATISTIC(TotalEdgeReversals,
28           "Number of times the source and sink of dependence was reversed to "
29           "expose cycles in the graph.");
30 
31 using InstructionListType = SmallVector<Instruction *, 2>;
32 
33 //===--------------------------------------------------------------------===//
34 // AbstractDependenceGraphBuilder implementation
35 //===--------------------------------------------------------------------===//
36 
37 template <class G>
38 void AbstractDependenceGraphBuilder<G>::createFineGrainedNodes() {
39   ++TotalGraphs;
40   assert(IMap.empty() && "Expected empty instruction map at start");
41   for (BasicBlock *BB : BBList)
42     for (Instruction &I : *BB) {
43       auto &NewNode = createFineGrainedNode(I);
44       IMap.insert(std::make_pair(&I, &NewNode));
45       ++TotalFineGrainedNodes;
46     }
47 }
48 
49 template <class G> void AbstractDependenceGraphBuilder<G>::createDefUseEdges() {
50   for (NodeType *N : Graph) {
51     InstructionListType SrcIList;
52     N->collectInstructions([](const Instruction *I) { return true; }, SrcIList);
53 
54     // Use a set to mark the targets that we link to N, so we don't add
55     // duplicate def-use edges when more than one instruction in a target node
56     // use results of instructions that are contained in N.
57     SmallPtrSet<NodeType *, 4> VisitedTargets;
58 
59     for (Instruction *II : SrcIList) {
60       for (User *U : II->users()) {
61         Instruction *UI = dyn_cast<Instruction>(U);
62         if (!UI)
63           continue;
64         NodeType *DstNode = nullptr;
65         if (IMap.find(UI) != IMap.end())
66           DstNode = IMap.find(UI)->second;
67 
68         // In the case of loops, the scope of the subgraph is all the
69         // basic blocks (and instructions within them) belonging to the loop. We
70         // simply ignore all the edges coming from (or going into) instructions
71         // or basic blocks outside of this range.
72         if (!DstNode) {
73           LLVM_DEBUG(
74               dbgs()
75               << "skipped def-use edge since the sink" << *UI
76               << " is outside the range of instructions being considered.\n");
77           continue;
78         }
79 
80         // Self dependencies are ignored because they are redundant and
81         // uninteresting.
82         if (DstNode == N) {
83           LLVM_DEBUG(dbgs()
84                      << "skipped def-use edge since the sink and the source ("
85                      << N << ") are the same.\n");
86           continue;
87         }
88 
89         if (VisitedTargets.insert(DstNode).second) {
90           createDefUseEdge(*N, *DstNode);
91           ++TotalDefUseEdges;
92         }
93       }
94     }
95   }
96 }
97 
98 template <class G>
99 void AbstractDependenceGraphBuilder<G>::createMemoryDependencyEdges() {
100   using DGIterator = typename G::iterator;
101   auto isMemoryAccess = [](const Instruction *I) {
102     return I->mayReadOrWriteMemory();
103   };
104   for (DGIterator SrcIt = Graph.begin(), E = Graph.end(); SrcIt != E; ++SrcIt) {
105     InstructionListType SrcIList;
106     (*SrcIt)->collectInstructions(isMemoryAccess, SrcIList);
107     if (SrcIList.empty())
108       continue;
109 
110     for (DGIterator DstIt = SrcIt; DstIt != E; ++DstIt) {
111       if (**SrcIt == **DstIt)
112         continue;
113       InstructionListType DstIList;
114       (*DstIt)->collectInstructions(isMemoryAccess, DstIList);
115       if (DstIList.empty())
116         continue;
117       bool ForwardEdgeCreated = false;
118       bool BackwardEdgeCreated = false;
119       for (Instruction *ISrc : SrcIList) {
120         for (Instruction *IDst : DstIList) {
121           auto D = DI.depends(ISrc, IDst, true);
122           if (!D)
123             continue;
124 
125           // If we have a dependence with its left-most non-'=' direction
126           // being '>' we need to reverse the direction of the edge, because
127           // the source of the dependence cannot occur after the sink. For
128           // confused dependencies, we will create edges in both directions to
129           // represent the possibility of a cycle.
130 
131           auto createConfusedEdges = [&](NodeType &Src, NodeType &Dst) {
132             if (!ForwardEdgeCreated) {
133               createMemoryEdge(Src, Dst);
134               ++TotalMemoryEdges;
135             }
136             if (!BackwardEdgeCreated) {
137               createMemoryEdge(Dst, Src);
138               ++TotalMemoryEdges;
139             }
140             ForwardEdgeCreated = BackwardEdgeCreated = true;
141             ++TotalConfusedEdges;
142           };
143 
144           auto createForwardEdge = [&](NodeType &Src, NodeType &Dst) {
145             if (!ForwardEdgeCreated) {
146               createMemoryEdge(Src, Dst);
147               ++TotalMemoryEdges;
148             }
149             ForwardEdgeCreated = true;
150           };
151 
152           auto createBackwardEdge = [&](NodeType &Src, NodeType &Dst) {
153             if (!BackwardEdgeCreated) {
154               createMemoryEdge(Dst, Src);
155               ++TotalMemoryEdges;
156             }
157             BackwardEdgeCreated = true;
158           };
159 
160           if (D->isConfused())
161             createConfusedEdges(**SrcIt, **DstIt);
162           else if (D->isOrdered() && !D->isLoopIndependent()) {
163             bool ReversedEdge = false;
164             for (unsigned Level = 1; Level <= D->getLevels(); ++Level) {
165               if (D->getDirection(Level) == Dependence::DVEntry::EQ)
166                 continue;
167               else if (D->getDirection(Level) == Dependence::DVEntry::GT) {
168                 createBackwardEdge(**SrcIt, **DstIt);
169                 ReversedEdge = true;
170                 ++TotalEdgeReversals;
171                 break;
172               } else if (D->getDirection(Level) == Dependence::DVEntry::LT)
173                 break;
174               else {
175                 createConfusedEdges(**SrcIt, **DstIt);
176                 break;
177               }
178             }
179             if (!ReversedEdge)
180               createForwardEdge(**SrcIt, **DstIt);
181           } else
182             createForwardEdge(**SrcIt, **DstIt);
183 
184           // Avoid creating duplicate edges.
185           if (ForwardEdgeCreated && BackwardEdgeCreated)
186             break;
187         }
188 
189         // If we've created edges in both directions, there is no more
190         // unique edge that we can create between these two nodes, so we
191         // can exit early.
192         if (ForwardEdgeCreated && BackwardEdgeCreated)
193           break;
194       }
195     }
196   }
197 }
198 
199 template class llvm::AbstractDependenceGraphBuilder<DataDependenceGraph>;
200 template class llvm::DependenceGraphInfo<DDGNode>;
201