1 | //===- DDGTest.cpp - DDGAnalysis unit tests -------------------------------===// |
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 | |
9 | #include "llvm/Analysis/DDG.h" |
10 | #include "llvm/Analysis/AliasAnalysis.h" |
11 | #include "llvm/Analysis/AssumptionCache.h" |
12 | #include "llvm/Analysis/BasicAliasAnalysis.h" |
13 | #include "llvm/Analysis/LoopInfo.h" |
14 | #include "llvm/Analysis/ScalarEvolution.h" |
15 | #include "llvm/Analysis/TargetLibraryInfo.h" |
16 | #include "llvm/AsmParser/Parser.h" |
17 | #include "llvm/IR/Dominators.h" |
18 | #include "llvm/Support/SourceMgr.h" |
19 | #include "gtest/gtest.h" |
20 | |
21 | using namespace llvm; |
22 | |
23 | /// Build the DDG analysis for a loop and run the given test \p Test. |
24 | static void runTest(Module &M, StringRef FuncName, |
25 | function_ref<void(Function &F, LoopInfo &LI, |
26 | DependenceInfo &DI, ScalarEvolution &SE)> |
27 | Test) { |
28 | auto *F = M.getFunction(Name: FuncName); |
29 | ASSERT_NE(F, nullptr) << "Could not find " << FuncName; |
30 | |
31 | TargetLibraryInfoImpl TLII; |
32 | TargetLibraryInfo TLI(TLII); |
33 | AssumptionCache AC(*F); |
34 | DominatorTree DT(*F); |
35 | LoopInfo LI(DT); |
36 | ScalarEvolution SE(*F, TLI, AC, DT, LI); |
37 | AAResults AA(TLI); |
38 | DependenceInfo DI(F, &AA, &SE, &LI); |
39 | Test(*F, LI, DI, SE); |
40 | } |
41 | |
42 | static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context, |
43 | const char *ModuleStr) { |
44 | SMDiagnostic Err; |
45 | return parseAssemblyString(AsmString: ModuleStr, Err, Context); |
46 | } |
47 | |
48 | TEST(DDGTest, getDependencies) { |
49 | const char *ModuleStr = |
50 | "target datalayout = \"e-m:e-i64:64-n32:64\"\n" |
51 | "target triple = \"powerpc64le-unknown-linux-gnu\"\n" |
52 | "\n" |
53 | "define dso_local void @foo(i32 signext %n, i32* noalias %A, i32* " |
54 | "noalias %B) {\n" |
55 | "entry:\n" |
56 | " %cmp1 = icmp sgt i32 %n, 0\n" |
57 | " br i1 %cmp1, label %for.body.preheader, label %for.end\n" |
58 | "\n" |
59 | "for.body.preheader:\n" |
60 | " %wide.trip.count = zext i32 %n to i64\n" |
61 | " br label %for.body\n" |
62 | " \n" |
63 | " for.body:\n" |
64 | " %indvars.iv = phi i64 [ 0, %for.body.preheader ], [ " |
65 | "%indvars.iv.next, %for.body ]\n" |
66 | " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv\n" |
67 | " %0 = trunc i64 %indvars.iv to i32\n" |
68 | " store i32 %0, i32* %arrayidx, align 4\n" |
69 | " %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1\n" |
70 | " %arrayidx2 = getelementptr inbounds i32, i32* %A, i64 " |
71 | "%indvars.iv.next\n" |
72 | " %1 = load i32, i32* %arrayidx2, align 4\n" |
73 | " %add3 = add nsw i32 %1, 1\n" |
74 | " %arrayidx5 = getelementptr inbounds i32, i32* %B, i64 %indvars.iv\n" |
75 | " store i32 %add3, i32* %arrayidx5, align 4\n" |
76 | " %exitcond = icmp ne i64 %indvars.iv.next, %wide.trip.count\n" |
77 | " br i1 %exitcond, label %for.body, label %for.end.loopexit\n" |
78 | "\n" |
79 | "for.end.loopexit:\n" |
80 | " br label %for.end\n" |
81 | "\n" |
82 | "for.end:\n" |
83 | " ret void\n" |
84 | "}\n" ; |
85 | |
86 | LLVMContext Context; |
87 | std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); |
88 | |
89 | runTest( |
90 | M&: *M, FuncName: "foo" , |
91 | Test: [&](Function &F, LoopInfo &LI, DependenceInfo &DI, ScalarEvolution &SE) { |
92 | Loop *L = *LI.begin(); |
93 | assert(L && "expected the loop to be identified." ); |
94 | |
95 | DataDependenceGraph DDG(*L, LI, DI); |
96 | |
97 | // Collect all the nodes that have an outgoing memory edge |
98 | // while collecting all memory edges as well. There should |
99 | // only be one node with an outgoing memory edge and there |
100 | // should only be one memory edge in the entire graph. |
101 | std::vector<DDGNode *> DependenceSourceNodes; |
102 | std::vector<DDGEdge *> MemoryEdges; |
103 | for (DDGNode *N : DDG) { |
104 | for (DDGEdge *E : *N) { |
105 | bool SourceAdded = false; |
106 | if (E->isMemoryDependence()) { |
107 | MemoryEdges.push_back(x: E); |
108 | if (!SourceAdded) { |
109 | DependenceSourceNodes.push_back(x: N); |
110 | SourceAdded = true; |
111 | } |
112 | } |
113 | } |
114 | } |
115 | |
116 | EXPECT_EQ(DependenceSourceNodes.size(), 1ull); |
117 | EXPECT_EQ(MemoryEdges.size(), 1ull); |
118 | |
119 | DataDependenceGraph::DependenceList DL; |
120 | DDG.getDependencies(Src: *DependenceSourceNodes.back(), |
121 | Dst: MemoryEdges.back()->getTargetNode(), Deps&: DL); |
122 | |
123 | EXPECT_EQ(DL.size(), 1ull); |
124 | EXPECT_TRUE(DL.back()->isAnti()); |
125 | EXPECT_EQ(DL.back()->getLevels(), 1u); |
126 | EXPECT_NE(DL.back()->getDistance(1), nullptr); |
127 | EXPECT_EQ(DL.back()->getDistance(1), |
128 | SE.getOne(DL.back()->getDistance(1)->getType())); |
129 | }); |
130 | } |
131 | |
132 | /// Test to make sure that when pi-blocks are formed, multiple edges of the same |
133 | /// kind and direction are collapsed into a single edge. |
134 | /// In the test below, %loadASubI belongs to an outside node, which has input |
135 | /// dependency with multiple load instructions in the pi-block containing |
136 | /// %loadBSubI. We expect a single memory dependence edge from the outside node |
137 | /// to this pi-block. The pi-block also contains %add and %add7 both of which |
138 | /// feed a phi in an outside node. We expect a single def-use edge from the |
139 | /// pi-block to the node containing that phi. |
140 | TEST(DDGTest, avoidDuplicateEdgesToFromPiBlocks) { |
141 | const char *ModuleStr = |
142 | "target datalayout = \"e-m:e-i64:64-n32:64-v256:256:256-v512:512:512\"\n" |
143 | "\n" |
144 | "define void @foo(float* noalias %A, float* noalias %B, float* noalias " |
145 | "%C, float* noalias %D, i32 signext %n) {\n" |
146 | "entry:\n" |
147 | " %cmp1 = icmp sgt i32 %n, 0\n" |
148 | " br i1 %cmp1, label %for.body.preheader, label %for.end\n" |
149 | "\n" |
150 | "for.body.preheader: ; preds = %entry\n" |
151 | " %wide.trip.count = zext i32 %n to i64\n" |
152 | " br label %for.body\n" |
153 | "\n" |
154 | "for.body: ; preds = " |
155 | "%for.body.preheader, %if.end\n" |
156 | " %indvars.iv = phi i64 [ 0, %for.body.preheader ], [ %indvars.iv.next, " |
157 | "%if.end ]\n" |
158 | " %arrayidx = getelementptr inbounds float, float* %A, i64 %indvars.iv\n" |
159 | " %loadASubI = load float, float* %arrayidx, align 4\n" |
160 | " %arrayidx2 = getelementptr inbounds float, float* %B, i64 " |
161 | "%indvars.iv\n" |
162 | " %loadBSubI = load float, float* %arrayidx2, align 4\n" |
163 | " %add = fadd fast float %loadASubI, %loadBSubI\n" |
164 | " %arrayidx4 = getelementptr inbounds float, float* %A, i64 " |
165 | "%indvars.iv\n" |
166 | " store float %add, float* %arrayidx4, align 4\n" |
167 | " %arrayidx6 = getelementptr inbounds float, float* %A, i64 " |
168 | "%indvars.iv\n" |
169 | " %0 = load float, float* %arrayidx6, align 4\n" |
170 | " %add7 = fadd fast float %0, 1.000000e+00\n" |
171 | " %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1\n" |
172 | " %arrayidx10 = getelementptr inbounds float, float* %B, i64 " |
173 | "%indvars.iv.next\n" |
174 | " store float %add7, float* %arrayidx10, align 4\n" |
175 | " %arrayidx12 = getelementptr inbounds float, float* %A, i64 " |
176 | "%indvars.iv\n" |
177 | " %1 = load float, float* %arrayidx12, align 4\n" |
178 | " %cmp13 = fcmp fast ogt float %1, 1.000000e+02\n" |
179 | " br i1 %cmp13, label %if.then, label %if.else\n" |
180 | "\n" |
181 | "if.then: ; preds = %for.body\n" |
182 | " br label %if.end\n" |
183 | "\n" |
184 | "if.else: ; preds = %for.body\n" |
185 | " br label %if.end\n" |
186 | "\n" |
187 | "if.end: ; preds = %if.else, " |
188 | "%if.then\n" |
189 | " %ff.0 = phi float [ %add, %if.then ], [ %add7, %if.else ]\n" |
190 | " store float %ff.0, float* %C, align 4\n" |
191 | " %exitcond = icmp ne i64 %indvars.iv.next, %wide.trip.count\n" |
192 | " br i1 %exitcond, label %for.body, label %for.end.loopexit\n" |
193 | "\n" |
194 | "for.end.loopexit: ; preds = %if.end\n" |
195 | " br label %for.end\n" |
196 | "\n" |
197 | "for.end: ; preds = " |
198 | "%for.end.loopexit, %entry\n" |
199 | " ret void\n" |
200 | "}\n" ; |
201 | |
202 | LLVMContext Context; |
203 | std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); |
204 | |
205 | runTest( |
206 | M&: *M, FuncName: "foo" , |
207 | Test: [&](Function &F, LoopInfo &LI, DependenceInfo &DI, ScalarEvolution &SE) { |
208 | Loop *L = *LI.begin(); |
209 | assert(L && "expected the loop to be identified." ); |
210 | |
211 | DataDependenceGraph DDG(*L, LI, DI); |
212 | |
213 | const DDGNode *LoadASubI = nullptr; |
214 | for (DDGNode *N : DDG) { |
215 | if (!isa<SimpleDDGNode>(Val: N)) |
216 | continue; |
217 | SmallVector<Instruction *, 8> IList; |
218 | N->collectInstructions(Pred: [](const Instruction *I) { return true; }, |
219 | IList); |
220 | if (llvm::any_of(Range&: IList, P: [](Instruction *I) { |
221 | return I->getName() == "loadASubI" ; |
222 | })) { |
223 | LoadASubI = N; |
224 | break; |
225 | } |
226 | } |
227 | assert(LoadASubI && "Did not find load of A[i]" ); |
228 | |
229 | const PiBlockDDGNode *PiBlockWithBSubI = nullptr; |
230 | for (DDGNode *N : DDG) { |
231 | if (!isa<PiBlockDDGNode>(Val: N)) |
232 | continue; |
233 | for (DDGNode *M : cast<PiBlockDDGNode>(Val: N)->getNodes()) { |
234 | SmallVector<Instruction *, 8> IList; |
235 | M->collectInstructions(Pred: [](const Instruction *I) { return true; }, |
236 | IList); |
237 | if (llvm::any_of(Range&: IList, P: [](Instruction *I) { |
238 | return I->getName() == "loadBSubI" ; |
239 | })) { |
240 | PiBlockWithBSubI = static_cast<PiBlockDDGNode *>(N); |
241 | break; |
242 | } |
243 | } |
244 | if (PiBlockWithBSubI) |
245 | break; |
246 | } |
247 | assert(PiBlockWithBSubI && |
248 | "Did not find pi-block containing load of B[i]" ); |
249 | |
250 | const DDGNode *FFPhi = nullptr; |
251 | for (DDGNode *N : DDG) { |
252 | if (!isa<SimpleDDGNode>(Val: N)) |
253 | continue; |
254 | SmallVector<Instruction *, 8> IList; |
255 | N->collectInstructions(Pred: [](const Instruction *I) { return true; }, |
256 | IList); |
257 | if (llvm::any_of(Range&: IList, P: [](Instruction *I) { |
258 | return I->getName() == "ff.0" ; |
259 | })) { |
260 | FFPhi = N; |
261 | break; |
262 | } |
263 | } |
264 | assert(FFPhi && "Did not find ff.0 phi instruction" ); |
265 | |
266 | // Expect a single memory edge from '%0 = A[i]' to the pi-block. This |
267 | // means the duplicate incoming memory edges are removed during pi-block |
268 | // formation. |
269 | SmallVector<DDGEdge *, 4> EL; |
270 | LoadASubI->findEdgesTo(N: *PiBlockWithBSubI, EL); |
271 | unsigned NumMemoryEdges = llvm::count_if( |
272 | Range&: EL, P: [](DDGEdge *Edge) { return Edge->isMemoryDependence(); }); |
273 | EXPECT_EQ(NumMemoryEdges, 1ull); |
274 | |
275 | /// Expect a single def-use edge from the pi-block to '%ff.0 = phi...`. |
276 | /// This means the duplicate outgoing def-use edges are removed during |
277 | /// pi-block formation. |
278 | EL.clear(); |
279 | PiBlockWithBSubI->findEdgesTo(N: *FFPhi, EL); |
280 | NumMemoryEdges = |
281 | llvm::count_if(Range&: EL, P: [](DDGEdge *Edge) { return Edge->isDefUse(); }); |
282 | EXPECT_EQ(NumMemoryEdges, 1ull); |
283 | }); |
284 | } |
285 | |