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