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/BasicAliasAnalysis.h" 12 #include "llvm/Analysis/ScalarEvolution.h" 13 #include "llvm/Analysis/TargetLibraryInfo.h" 14 #include "llvm/AsmParser/Parser.h" 15 #include "llvm/IR/Dominators.h" 16 #include "llvm/Support/SourceMgr.h" 17 #include "gtest/gtest.h" 18 19 using namespace llvm; 20 21 /// Build the DDG analysis for a loop and run the given test \p Test. 22 static void runTest(Module &M, StringRef FuncName, 23 function_ref<void(Function &F, LoopInfo &LI, 24 DependenceInfo &DI, ScalarEvolution &SE)> 25 Test) { 26 auto *F = M.getFunction(FuncName); 27 ASSERT_NE(F, nullptr) << "Could not find " << FuncName; 28 29 TargetLibraryInfoImpl TLII; 30 TargetLibraryInfo TLI(TLII); 31 AssumptionCache AC(*F); 32 DominatorTree DT(*F); 33 LoopInfo LI(DT); 34 ScalarEvolution SE(*F, TLI, AC, DT, LI); 35 AAResults AA(TLI); 36 DependenceInfo DI(F, &AA, &SE, &LI); 37 Test(*F, LI, DI, SE); 38 } 39 40 static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context, 41 const char *ModuleStr) { 42 SMDiagnostic Err; 43 return parseAssemblyString(ModuleStr, Err, Context); 44 } 45 46 TEST(DDGTest, getDependencies) { 47 const char *ModuleStr = 48 "target datalayout = \"e-m:e-i64:64-n32:64\"\n" 49 "target triple = \"powerpc64le-unknown-linux-gnu\"\n" 50 "\n" 51 "define dso_local void @foo(i32 signext %n, i32* noalias %A, i32* " 52 "noalias %B) {\n" 53 "entry:\n" 54 " %cmp1 = icmp sgt i32 %n, 0\n" 55 " br i1 %cmp1, label %for.body.preheader, label %for.end\n" 56 "\n" 57 "for.body.preheader:\n" 58 " %wide.trip.count = zext i32 %n to i64\n" 59 " br label %for.body\n" 60 " \n" 61 " for.body:\n" 62 " %indvars.iv = phi i64 [ 0, %for.body.preheader ], [ " 63 "%indvars.iv.next, %for.body ]\n" 64 " %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv\n" 65 " %0 = trunc i64 %indvars.iv to i32\n" 66 " store i32 %0, i32* %arrayidx, align 4\n" 67 " %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1\n" 68 " %arrayidx2 = getelementptr inbounds i32, i32* %A, i64 " 69 "%indvars.iv.next\n" 70 " %1 = load i32, i32* %arrayidx2, align 4\n" 71 " %add3 = add nsw i32 %1, 1\n" 72 " %arrayidx5 = getelementptr inbounds i32, i32* %B, i64 %indvars.iv\n" 73 " store i32 %add3, i32* %arrayidx5, align 4\n" 74 " %exitcond = icmp ne i64 %indvars.iv.next, %wide.trip.count\n" 75 " br i1 %exitcond, label %for.body, label %for.end.loopexit\n" 76 "\n" 77 "for.end.loopexit:\n" 78 " br label %for.end\n" 79 "\n" 80 "for.end:\n" 81 " ret void\n" 82 "}\n"; 83 84 LLVMContext Context; 85 std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleStr); 86 87 runTest( 88 *M, "foo", 89 [&](Function &F, LoopInfo &LI, DependenceInfo &DI, ScalarEvolution &SE) { 90 Loop *L = *LI.begin(); 91 assert(L && "expected the loop to be identified."); 92 93 DataDependenceGraph DDG(*L, LI, DI); 94 95 // Collect all the nodes that have an outgoing memory edge 96 // while collecting all memory edges as well. There should 97 // only be one node with an outgoing memory edge and there 98 // should only be one memory edge in the entire graph. 99 std::vector<DDGNode *> DependenceSourceNodes; 100 std::vector<DDGEdge *> MemoryEdges; 101 for (DDGNode *N : DDG) { 102 for (DDGEdge *E : *N) { 103 bool SourceAdded = false; 104 if (E->isMemoryDependence()) { 105 MemoryEdges.push_back(E); 106 if (!SourceAdded) { 107 DependenceSourceNodes.push_back(N); 108 SourceAdded = true; 109 } 110 } 111 } 112 } 113 114 EXPECT_EQ(DependenceSourceNodes.size(), 1ull); 115 EXPECT_EQ(MemoryEdges.size(), 1ull); 116 117 DataDependenceGraph::DependenceList DL; 118 DDG.getDependencies(*DependenceSourceNodes.back(), 119 MemoryEdges.back()->getTargetNode(), DL); 120 121 EXPECT_EQ(DL.size(), 1ull); 122 EXPECT_TRUE(DL.back()->isAnti()); 123 EXPECT_EQ(DL.back()->getLevels(), 1u); 124 EXPECT_NE(DL.back()->getDistance(1), nullptr); 125 EXPECT_EQ(DL.back()->getDistance(1), 126 SE.getOne(DL.back()->getDistance(1)->getType())); 127 }); 128 } 129