1 //===- CodeMoverUtils.cpp - Unit tests for CodeMoverUtils ---------------===// 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/Transforms/Utils/CodeMoverUtils.h" 10 #include "llvm/Analysis/AssumptionCache.h" 11 #include "llvm/Analysis/DependenceAnalysis.h" 12 #include "llvm/Analysis/LoopInfo.h" 13 #include "llvm/Analysis/PostDominators.h" 14 #include "llvm/Analysis/ScalarEvolutionExpander.h" 15 #include "llvm/AsmParser/Parser.h" 16 #include "llvm/IR/Dominators.h" 17 #include "llvm/IR/LLVMContext.h" 18 #include "llvm/Support/SourceMgr.h" 19 #include "gtest/gtest.h" 20 21 using namespace llvm; 22 23 static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) { 24 SMDiagnostic Err; 25 std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C); 26 if (!Mod) 27 Err.print("CodeMoverUtilsTests", errs()); 28 return Mod; 29 } 30 31 static void run(Module &M, StringRef FuncName, 32 function_ref<void(Function &F, DominatorTree &DT, 33 PostDominatorTree &PDT, DependenceInfo &DI)> 34 Test) { 35 auto *F = M.getFunction(FuncName); 36 DominatorTree DT(*F); 37 PostDominatorTree PDT(*F); 38 TargetLibraryInfoImpl TLII; 39 TargetLibraryInfo TLI(TLII); 40 AssumptionCache AC(*F); 41 AliasAnalysis AA(TLI); 42 LoopInfo LI(DT); 43 ScalarEvolution SE(*F, TLI, AC, DT, LI); 44 DependenceInfo DI(F, &AA, &SE, &LI); 45 Test(*F, DT, PDT, DI); 46 } 47 48 TEST(CodeMoverUtils, BasicTest) { 49 LLVMContext C; 50 51 // void safecall() noexcept willreturn nosync; 52 // void unsafecall(); 53 // void foo(int * __restrict__ A, int * __restrict__ B, int * __restrict__ C, 54 // long N) { 55 // X = N / 1; 56 // safecall(); 57 // unsafecall1(); 58 // unsafecall2(); 59 // for (long i = 0; i < N; ++i) { 60 // A[5] = 5; 61 // A[i] = 0; 62 // B[i] = A[i]; 63 // C[i] = A[i]; 64 // A[6] = 6; 65 // } 66 // } 67 std::unique_ptr<Module> M = parseIR( 68 C, 69 "define void @foo(i32* noalias %A, i32* noalias %B, i32* noalias %C\n" 70 " , i64 %N) {\n" 71 "entry:\n" 72 " %X = sdiv i64 1, %N\n" 73 " call void @safecall()\n" 74 " %cmp1 = icmp slt i64 0, %N\n" 75 " call void @unsafecall1()\n" 76 " call void @unsafecall2()\n" 77 " br i1 %cmp1, label %for.body, label %for.end\n" 78 "for.body:\n" 79 " %i = phi i64 [ 0, %entry ], [ %inc, %for.body ]\n" 80 " %arrayidx_A5 = getelementptr inbounds i32, i32* %A, i64 5\n" 81 " store i32 5, i32* %arrayidx_A5, align 4\n" 82 " %arrayidx_A = getelementptr inbounds i32, i32* %A, i64 %i\n" 83 " store i32 0, i32* %arrayidx_A, align 4\n" 84 " %load1 = load i32, i32* %arrayidx_A, align 4\n" 85 " %arrayidx_B = getelementptr inbounds i32, i32* %B, i64 %i\n" 86 " store i32 %load1, i32* %arrayidx_B, align 4\n" 87 " %load2 = load i32, i32* %arrayidx_A, align 4\n" 88 " %arrayidx_C = getelementptr inbounds i32, i32* %C, i64 %i\n" 89 " store i32 %load2, i32* %arrayidx_C, align 4\n" 90 " %arrayidx_A6 = getelementptr inbounds i32, i32* %A, i64 6\n" 91 " store i32 6, i32* %arrayidx_A6, align 4\n" 92 " %inc = add nsw i64 %i, 1\n" 93 " %cmp = icmp slt i64 %inc, %N\n" 94 " br i1 %cmp, label %for.body, label %for.end\n" 95 "for.end:\n" 96 " ret void\n" 97 "}\n" 98 "declare void @safecall() nounwind nosync willreturn\n" 99 "declare void @unsafecall1()\n" 100 "declare void @unsafecall2()\n"); 101 102 run(*M, "foo", 103 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, 104 DependenceInfo &DI) { 105 Function::iterator FI = F.begin(); 106 BasicBlock *Entry = &*(FI++); 107 assert(Entry->getName() == "entry" && "Expecting BasicBlock entry"); 108 Instruction *CI_safecall = Entry->front().getNextNode(); 109 assert(isa<CallInst>(CI_safecall) && "Expecting CI_safecall to be a CallInst"); 110 Instruction *CI_unsafecall = CI_safecall->getNextNode()->getNextNode(); 111 assert(isa<CallInst>(CI_unsafecall) && "Expecting CI_unsafecall to be a CallInst"); 112 BasicBlock *ForBody = &*(FI++); 113 assert(ForBody->getName() == "for.body" && 114 "Expecting BasicBlock for.body"); 115 Instruction &PN = ForBody->front(); 116 assert(isa<PHINode>(PN) && "Expecting PN to be a PHINode"); 117 Instruction *SI_A5 = PN.getNextNode()->getNextNode(); 118 assert(isa<StoreInst>(SI_A5) && 119 SI_A5->getOperand(1)->getName() == "arrayidx_A5" && 120 "Expecting store to arrayidx_A5"); 121 Instruction *SI = SI_A5->getNextNode()->getNextNode(); 122 assert(isa<StoreInst>(SI) && 123 SI->getOperand(1)->getName() == "arrayidx_A" && 124 "Expecting store to arrayidx_A"); 125 Instruction *LI1 = SI->getNextNode(); 126 assert(LI1->getName() == "load1" && "Expecting LI1 to be load1"); 127 Instruction *LI2 = LI1->getNextNode()->getNextNode()->getNextNode(); 128 assert(LI2->getName() == "load2" && "Expecting LI2 to be load2"); 129 Instruction *SI_A6 = LI2->getNextNode()->getNextNode()->getNextNode()->getNextNode(); 130 assert(isa<StoreInst>(SI_A6) && 131 SI_A6->getOperand(1)->getName() == "arrayidx_A6" && 132 "Expecting store to arrayidx_A6"); 133 134 // Can move after CI_safecall, as it does not throw, not synchronize, or must return. 135 EXPECT_TRUE(isSafeToMoveBefore(*CI_safecall->getPrevNode(), *CI_safecall->getNextNode(), DT, PDT, DI)); 136 137 // Cannot move CI_unsafecall, as it may throw. 138 EXPECT_FALSE(isSafeToMoveBefore(*CI_unsafecall->getNextNode(), *CI_unsafecall, DT, PDT, DI)); 139 140 // Moving instruction to non control flow equivalent places are not 141 // supported. 142 EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *Entry->getTerminator(), DT, PDT, DI)); 143 144 // Moving PHINode is not supported. 145 EXPECT_FALSE(isSafeToMoveBefore(PN, *PN.getPrevNode(), DT, PDT, DI)); 146 147 // Cannot move non-PHINode before PHINode. 148 EXPECT_FALSE(isSafeToMoveBefore(*PN.getNextNode(), PN, DT, PDT, DI)); 149 150 // Moving Terminator is not supported. 151 EXPECT_FALSE(isSafeToMoveBefore(*Entry->getTerminator(), *PN.getNextNode(), DT, 152 PDT, DI)); 153 154 // Cannot move %arrayidx_A after SI, as SI is its user. 155 EXPECT_FALSE(isSafeToMoveBefore(*SI->getPrevNode(), *SI->getNextNode(), DT, PDT, DI)); 156 157 // Cannot move SI before %arrayidx_A, as %arrayidx_A is its operand. 158 EXPECT_FALSE(isSafeToMoveBefore(*SI, *SI->getPrevNode(), DT, PDT, DI)); 159 160 // Cannot move LI2 after SI_A6, as there is a flow dependence. 161 EXPECT_FALSE(isSafeToMoveBefore(*LI2, *SI_A6->getNextNode(), DT, PDT, DI)); 162 163 // Cannot move SI after LI1, as there is a anti dependence. 164 EXPECT_FALSE(isSafeToMoveBefore(*SI, *LI1->getNextNode(), DT, PDT, DI)); 165 166 // Cannot move SI_A5 after SI, as there is a output dependence. 167 EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *LI1, DT, PDT, DI)); 168 169 // Can move LI2 before LI1, as there is only an input dependence. 170 EXPECT_TRUE(isSafeToMoveBefore(*LI2, *LI1, DT, PDT, DI)); 171 }); 172 } 173