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(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(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, "foo", 91 [&](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(E); 108 if (!SourceAdded) { 109 DependenceSourceNodes.push_back(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(*DependenceSourceNodes.back(), 121 MemoryEdges.back()->getTargetNode(), 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, "foo", 207 [&](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>(N)) 216 continue; 217 SmallVector<Instruction *, 8> IList; 218 N->collectInstructions([](const Instruction *I) { return true; }, 219 IList); 220 if (llvm::any_of(IList, [](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>(N)) 232 continue; 233 for (DDGNode *M : cast<PiBlockDDGNode>(N)->getNodes()) { 234 SmallVector<Instruction *, 8> IList; 235 M->collectInstructions([](const Instruction *I) { return true; }, 236 IList); 237 if (llvm::any_of(IList, [](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>(N)) 253 continue; 254 SmallVector<Instruction *, 8> IList; 255 N->collectInstructions([](const Instruction *I) { return true; }, 256 IList); 257 if (llvm::any_of(IList, [](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(*PiBlockWithBSubI, EL); 271 unsigned NumMemoryEdges = llvm::count_if( 272 EL, [](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(*FFPhi, EL); 280 NumMemoryEdges = 281 llvm::count_if(EL, [](DDGEdge *Edge) { return Edge->isDefUse(); }); 282 EXPECT_EQ(NumMemoryEdges, 1ull); 283 }); 284 } 285