1 //===- DivergenceAnalysisTest.cpp - DivergenceAnalysis 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/ADT/SmallVector.h"
10 #include "llvm/Analysis/AssumptionCache.h"
11 #include "llvm/Analysis/DivergenceAnalysis.h"
12 #include "llvm/Analysis/LoopInfo.h"
13 #include "llvm/Analysis/PostDominators.h"
14 #include "llvm/Analysis/SyncDependenceAnalysis.h"
15 #include "llvm/Analysis/TargetLibraryInfo.h"
16 #include "llvm/AsmParser/Parser.h"
17 #include "llvm/IR/Constants.h"
18 #include "llvm/IR/Dominators.h"
19 #include "llvm/IR/GlobalVariable.h"
20 #include "llvm/IR/IRBuilder.h"
21 #include "llvm/IR/InstIterator.h"
22 #include "llvm/IR/LLVMContext.h"
23 #include "llvm/IR/LegacyPassManager.h"
24 #include "llvm/IR/Module.h"
25 #include "llvm/IR/Verifier.h"
26 #include "llvm/Support/SourceMgr.h"
27 #include "gtest/gtest.h"
28 
29 namespace llvm {
30 namespace {
31 
32 BasicBlock *GetBlockByName(StringRef BlockName, Function &F) {
33   for (auto &BB : F) {
34     if (BB.getName() != BlockName)
35       continue;
36     return &BB;
37   }
38   return nullptr;
39 }
40 
41 // We use this fixture to ensure that we clean up DivergenceAnalysisImpl before
42 // deleting the PassManager.
43 class DivergenceAnalysisTest : public testing::Test {
44 protected:
45   LLVMContext Context;
46   Module M;
47   TargetLibraryInfoImpl TLII;
48   TargetLibraryInfo TLI;
49 
50   std::unique_ptr<DominatorTree> DT;
51   std::unique_ptr<PostDominatorTree> PDT;
52   std::unique_ptr<LoopInfo> LI;
53   std::unique_ptr<SyncDependenceAnalysis> SDA;
54 
55   DivergenceAnalysisTest() : M("", Context), TLII(), TLI(TLII) {}
56 
57   DivergenceAnalysisImpl buildDA(Function &F, bool IsLCSSA) {
58     DT.reset(new DominatorTree(F));
59     PDT.reset(new PostDominatorTree(F));
60     LI.reset(new LoopInfo(*DT));
61     SDA.reset(new SyncDependenceAnalysis(*DT, *PDT, *LI));
62     return DivergenceAnalysisImpl(F, nullptr, *DT, *LI, *SDA, IsLCSSA);
63   }
64 
65   void runWithDA(
66       Module &M, StringRef FuncName, bool IsLCSSA,
67       function_ref<void(Function &F, LoopInfo &LI, DivergenceAnalysisImpl &DA)>
68           Test) {
69     auto *F = M.getFunction(FuncName);
70     ASSERT_NE(F, nullptr) << "Could not find " << FuncName;
71     DivergenceAnalysisImpl DA = buildDA(*F, IsLCSSA);
72     Test(*F, *LI, DA);
73   }
74 };
75 
76 // Simple initial state test
77 TEST_F(DivergenceAnalysisTest, DAInitialState) {
78   IntegerType *IntTy = IntegerType::getInt32Ty(Context);
79   FunctionType *FTy =
80       FunctionType::get(Type::getVoidTy(Context), {IntTy}, false);
81   Function *F = Function::Create(FTy, Function::ExternalLinkage, "f", M);
82   BasicBlock *BB = BasicBlock::Create(Context, "entry", F);
83   ReturnInst::Create(Context, nullptr, BB);
84 
85   DivergenceAnalysisImpl DA = buildDA(*F, false);
86 
87   // Whole function region
88   EXPECT_EQ(DA.getRegionLoop(), nullptr);
89 
90   // No divergence in initial state
91   EXPECT_FALSE(DA.hasDetectedDivergence());
92 
93   // No spurious divergence
94   DA.compute();
95   EXPECT_FALSE(DA.hasDetectedDivergence());
96 
97   // Detected divergence after marking
98   Argument &arg = *F->arg_begin();
99   DA.markDivergent(arg);
100 
101   EXPECT_TRUE(DA.hasDetectedDivergence());
102   EXPECT_TRUE(DA.isDivergent(arg));
103 
104   DA.compute();
105   EXPECT_TRUE(DA.hasDetectedDivergence());
106   EXPECT_TRUE(DA.isDivergent(arg));
107 }
108 
109 TEST_F(DivergenceAnalysisTest, DANoLCSSA) {
110   LLVMContext C;
111   SMDiagnostic Err;
112 
113   std::unique_ptr<Module> M = parseAssemblyString(
114       "target datalayout = \"e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128\" "
115       " "
116       "define i32 @f_1(i8* nocapture %arr, i32 %n, i32* %A, i32* %B) "
117       "    local_unnamed_addr { "
118       "entry: "
119       "  br label %loop.ph "
120       " "
121       "loop.ph: "
122       "  br label %loop "
123       " "
124       "loop: "
125       "  %iv0 = phi i32 [ %iv0.inc, %loop ], [ 0, %loop.ph ] "
126       "  %iv1 = phi i32 [ %iv1.inc, %loop ], [ -2147483648, %loop.ph ] "
127       "  %iv0.inc = add i32 %iv0, 1 "
128       "  %iv1.inc = add i32 %iv1, 3 "
129       "  %cond.cont = icmp slt i32 %iv0, %n "
130       "  br i1 %cond.cont, label %loop, label %for.end.loopexit "
131       " "
132       "for.end.loopexit: "
133       "  ret i32 %iv0 "
134       "} ",
135       Err, C);
136 
137   Function *F = M->getFunction("f_1");
138   DivergenceAnalysisImpl DA = buildDA(*F, false);
139   EXPECT_FALSE(DA.hasDetectedDivergence());
140 
141   auto ItArg = F->arg_begin();
142   ItArg++;
143   auto &NArg = *ItArg;
144 
145   // Seed divergence in argument %n
146   DA.markDivergent(NArg);
147 
148   DA.compute();
149   EXPECT_TRUE(DA.hasDetectedDivergence());
150 
151   // Verify that "ret %iv.0" is divergent
152   auto ItBlock = F->begin();
153   std::advance(ItBlock, 3);
154   auto &ExitBlock = *GetBlockByName("for.end.loopexit", *F);
155   auto &RetInst = *cast<ReturnInst>(ExitBlock.begin());
156   EXPECT_TRUE(DA.isDivergent(RetInst));
157 }
158 
159 TEST_F(DivergenceAnalysisTest, DALCSSA) {
160   LLVMContext C;
161   SMDiagnostic Err;
162 
163   std::unique_ptr<Module> M = parseAssemblyString(
164       "target datalayout = \"e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128\" "
165       " "
166       "define i32 @f_lcssa(i8* nocapture %arr, i32 %n, i32* %A, i32* %B) "
167       "    local_unnamed_addr { "
168       "entry: "
169       "  br label %loop.ph "
170       " "
171       "loop.ph: "
172       "  br label %loop "
173       " "
174       "loop: "
175       "  %iv0 = phi i32 [ %iv0.inc, %loop ], [ 0, %loop.ph ] "
176       "  %iv1 = phi i32 [ %iv1.inc, %loop ], [ -2147483648, %loop.ph ] "
177       "  %iv0.inc = add i32 %iv0, 1 "
178       "  %iv1.inc = add i32 %iv1, 3 "
179       "  %cond.cont = icmp slt i32 %iv0, %n "
180       "  br i1 %cond.cont, label %loop, label %for.end.loopexit "
181       " "
182       "for.end.loopexit: "
183       "  %val.ret = phi i32 [ %iv0, %loop ] "
184       "  br label %detached.return "
185       " "
186       "detached.return: "
187       "  ret i32 %val.ret "
188       "} ",
189       Err, C);
190 
191   Function *F = M->getFunction("f_lcssa");
192   DivergenceAnalysisImpl DA = buildDA(*F, true);
193   EXPECT_FALSE(DA.hasDetectedDivergence());
194 
195   auto ItArg = F->arg_begin();
196   ItArg++;
197   auto &NArg = *ItArg;
198 
199   // Seed divergence in argument %n
200   DA.markDivergent(NArg);
201 
202   DA.compute();
203   EXPECT_TRUE(DA.hasDetectedDivergence());
204 
205   // Verify that "ret %iv.0" is divergent
206   auto ItBlock = F->begin();
207   std::advance(ItBlock, 4);
208   auto &ExitBlock = *GetBlockByName("detached.return", *F);
209   auto &RetInst = *cast<ReturnInst>(ExitBlock.begin());
210   EXPECT_TRUE(DA.isDivergent(RetInst));
211 }
212 
213 TEST_F(DivergenceAnalysisTest, DAJoinDivergence) {
214   LLVMContext C;
215   SMDiagnostic Err;
216 
217   std::unique_ptr<Module> M = parseAssemblyString(
218       "target datalayout = \"e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128\" "
219       " "
220       "define void @f_1(i1 %a, i1 %b, i1 %c) "
221       "    local_unnamed_addr { "
222       "A: "
223       "  br i1 %a, label %B, label %C "
224       " "
225       "B: "
226       "  br i1 %b, label %C, label %D "
227       " "
228       "C: "
229       "  %c.join = phi i32 [ 0, %A ], [ 1, %B ] "
230       "  br i1 %c, label %D, label %E "
231       " "
232       "D: "
233       "  %d.join = phi i32 [ 0, %B ], [ 1, %C ] "
234       "  br label %E "
235       " "
236       "E: "
237       "  %e.join = phi i32 [ 0, %C ], [ 1, %D ] "
238       "  ret void "
239       "} "
240       " "
241       "define void @f_2(i1 %a, i1 %b, i1 %c) "
242       "    local_unnamed_addr { "
243       "A: "
244       "  br i1 %a, label %B, label %E "
245       " "
246       "B: "
247       "  br i1 %b, label %C, label %D "
248       " "
249       "C: "
250       "  br label %D "
251       " "
252       "D: "
253       "  %d.join = phi i32 [ 0, %B ], [ 1, %C ] "
254       "  br label %E "
255       " "
256       "E: "
257       "  %e.join = phi i32 [ 0, %A ], [ 1, %D ] "
258       "  ret void "
259       "} "
260       " "
261       "define void @f_3(i1 %a, i1 %b, i1 %c)"
262       "    local_unnamed_addr { "
263       "A: "
264       "  br i1 %a, label %B, label %C "
265       " "
266       "B: "
267       "  br label %C "
268       " "
269       "C: "
270       "  %c.join = phi i32 [ 0, %A ], [ 1, %B ] "
271       "  br i1 %c, label %D, label %E "
272       " "
273       "D: "
274       "  br label %E "
275       " "
276       "E: "
277       "  %e.join = phi i32 [ 0, %C ], [ 1, %D ] "
278       "  ret void "
279       "} ",
280       Err, C);
281 
282   // Maps divergent conditions to the basic blocks whose Phi nodes become
283   // divergent. Blocks need to be listed in IR order.
284   using SmallBlockVec = SmallVector<const BasicBlock *, 4>;
285   using InducedDivJoinMap = std::map<const Value *, SmallBlockVec>;
286 
287   // Actual function performing the checks.
288   auto CheckDivergenceFunc = [this](Function &F,
289                                     InducedDivJoinMap &ExpectedDivJoins) {
290     for (auto &ItCase : ExpectedDivJoins) {
291       auto *DivVal = ItCase.first;
292       auto DA = buildDA(F, false);
293       DA.markDivergent(*DivVal);
294       DA.compute();
295 
296       // List of basic blocks that shall host divergent Phi nodes.
297       auto ItDivJoins = ItCase.second.begin();
298 
299       for (auto &BB : F) {
300         auto *Phi = dyn_cast<PHINode>(BB.begin());
301         if (!Phi)
302           continue;
303 
304         if (ItDivJoins != ItCase.second.end() && &BB == *ItDivJoins) {
305           EXPECT_TRUE(DA.isDivergent(*Phi));
306           // Advance to next block with expected divergent PHI node.
307           ++ItDivJoins;
308         } else {
309           EXPECT_FALSE(DA.isDivergent(*Phi));
310         }
311       }
312     }
313   };
314 
315   {
316     auto *F = M->getFunction("f_1");
317     auto ItBlocks = F->begin();
318     ItBlocks++; // Skip A
319     ItBlocks++; // Skip B
320     auto *C = &*ItBlocks++;
321     auto *D = &*ItBlocks++;
322     auto *E = &*ItBlocks;
323 
324     auto ItArg = F->arg_begin();
325     auto *AArg = &*ItArg++;
326     auto *BArg = &*ItArg++;
327     auto *CArg = &*ItArg;
328 
329     InducedDivJoinMap DivJoins;
330     DivJoins.emplace(AArg, SmallBlockVec({C, D, E}));
331     DivJoins.emplace(BArg, SmallBlockVec({D, E}));
332     DivJoins.emplace(CArg, SmallBlockVec({E}));
333 
334     CheckDivergenceFunc(*F, DivJoins);
335   }
336 
337   {
338     auto *F = M->getFunction("f_2");
339     auto ItBlocks = F->begin();
340     ItBlocks++; // Skip A
341     ItBlocks++; // Skip B
342     ItBlocks++; // Skip C
343     auto *D = &*ItBlocks++;
344     auto *E = &*ItBlocks;
345 
346     auto ItArg = F->arg_begin();
347     auto *AArg = &*ItArg++;
348     auto *BArg = &*ItArg++;
349     auto *CArg = &*ItArg;
350 
351     InducedDivJoinMap DivJoins;
352     DivJoins.emplace(AArg, SmallBlockVec({E}));
353     DivJoins.emplace(BArg, SmallBlockVec({D}));
354     DivJoins.emplace(CArg, SmallBlockVec({}));
355 
356     CheckDivergenceFunc(*F, DivJoins);
357   }
358 
359   {
360     auto *F = M->getFunction("f_3");
361     auto ItBlocks = F->begin();
362     ItBlocks++; // Skip A
363     ItBlocks++; // Skip B
364     auto *C = &*ItBlocks++;
365     ItBlocks++; // Skip D
366     auto *E = &*ItBlocks;
367 
368     auto ItArg = F->arg_begin();
369     auto *AArg = &*ItArg++;
370     auto *BArg = &*ItArg++;
371     auto *CArg = &*ItArg;
372 
373     InducedDivJoinMap DivJoins;
374     DivJoins.emplace(AArg, SmallBlockVec({C}));
375     DivJoins.emplace(BArg, SmallBlockVec({}));
376     DivJoins.emplace(CArg, SmallBlockVec({E}));
377 
378     CheckDivergenceFunc(*F, DivJoins);
379   }
380 }
381 
382 TEST_F(DivergenceAnalysisTest, DASwitchUnreachableDefault) {
383   LLVMContext C;
384   SMDiagnostic Err;
385 
386   std::unique_ptr<Module> M = parseAssemblyString(
387       "target datalayout = \"e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128\" "
388       " "
389       "define void @switch_unreachable_default(i32 %cond) local_unnamed_addr { "
390       "entry: "
391       "  switch i32 %cond, label %sw.default [ "
392       "    i32 0, label %sw.bb0 "
393       "    i32 1, label %sw.bb1 "
394       "  ] "
395       " "
396       "sw.bb0: "
397       "  br label %sw.epilog "
398       " "
399       "sw.bb1: "
400       "  br label %sw.epilog "
401       " "
402       "sw.default: "
403       "  unreachable "
404       " "
405       "sw.epilog: "
406       "  %div.dbl = phi double [ 0.0, %sw.bb0], [ -1.0, %sw.bb1 ] "
407       "  ret void "
408       "}",
409       Err, C);
410 
411   auto *F = M->getFunction("switch_unreachable_default");
412   auto &CondArg = *F->arg_begin();
413   auto DA = buildDA(*F, false);
414 
415   EXPECT_FALSE(DA.hasDetectedDivergence());
416 
417   DA.markDivergent(CondArg);
418   DA.compute();
419 
420   // Still %CondArg is divergent.
421   EXPECT_TRUE(DA.hasDetectedDivergence());
422 
423   // The join uni.dbl is not divergent (see D52221)
424   auto &ExitBlock = *GetBlockByName("sw.epilog", *F);
425   auto &DivDblPhi = *cast<PHINode>(ExitBlock.begin());
426   EXPECT_TRUE(DA.isDivergent(DivDblPhi));
427 }
428 
429 } // end anonymous namespace
430 } // end namespace llvm
431