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, "define void @foo(i32* noalias %A, i32* noalias %B, i32* noalias %C\n" 69 " , i64 %N) {\n" 70 "entry:\n" 71 " %X = sdiv i64 1, %N\n" 72 " call void @safecall()\n" 73 " %cmp1 = icmp slt i64 0, %N\n" 74 " call void @unsafecall1()\n" 75 " call void @unsafecall2()\n" 76 " br i1 %cmp1, label %for.body, label %for.end\n" 77 "for.body:\n" 78 " %i = phi i64 [ 0, %entry ], [ %inc, %for.body ]\n" 79 " %arrayidx_A5 = getelementptr inbounds i32, i32* %A, i64 5\n" 80 " store i32 5, i32* %arrayidx_A5, align 4\n" 81 " %arrayidx_A = getelementptr inbounds i32, i32* %A, i64 %i\n" 82 " store i32 0, i32* %arrayidx_A, align 4\n" 83 " %load1 = load i32, i32* %arrayidx_A, align 4\n" 84 " %arrayidx_B = getelementptr inbounds i32, i32* %B, i64 %i\n" 85 " store i32 %load1, i32* %arrayidx_B, align 4\n" 86 " %load2 = load i32, i32* %arrayidx_A, align 4\n" 87 " %arrayidx_C = getelementptr inbounds i32, i32* %C, i64 %i\n" 88 " store i32 %load2, i32* %arrayidx_C, align 4\n" 89 " %arrayidx_A6 = getelementptr inbounds i32, i32* %A, i64 6\n" 90 " store i32 6, i32* %arrayidx_A6, align 4\n" 91 " %inc = add nsw i64 %i, 1\n" 92 " %cmp = icmp slt i64 %inc, %N\n" 93 " br i1 %cmp, label %for.body, label %for.end\n" 94 "for.end:\n" 95 " ret void\n" 96 "}\n" 97 "declare void @safecall() nounwind nosync willreturn\n" 98 "declare void @unsafecall1()\n" 99 "declare void @unsafecall2()\n"); 100 101 run(*M, "foo", 102 [&](Function &F, DominatorTree &DT, PostDominatorTree &PDT, 103 DependenceInfo &DI) { 104 Function::iterator FI = F.begin(); 105 BasicBlock *Entry = &*(FI++); 106 assert(Entry->getName() == "entry" && "Expecting BasicBlock entry"); 107 Instruction *CI_safecall = Entry->front().getNextNode(); 108 assert(isa<CallInst>(CI_safecall) && 109 "Expecting CI_safecall to be a CallInst"); 110 Instruction *CI_unsafecall = CI_safecall->getNextNode()->getNextNode(); 111 assert(isa<CallInst>(CI_unsafecall) && 112 "Expecting CI_unsafecall to be a CallInst"); 113 BasicBlock *ForBody = &*(FI++); 114 assert(ForBody->getName() == "for.body" && 115 "Expecting BasicBlock for.body"); 116 Instruction &PN = ForBody->front(); 117 assert(isa<PHINode>(PN) && "Expecting PN to be a PHINode"); 118 Instruction *SI_A5 = PN.getNextNode()->getNextNode(); 119 assert(isa<StoreInst>(SI_A5) && 120 SI_A5->getOperand(1)->getName() == "arrayidx_A5" && 121 "Expecting store to arrayidx_A5"); 122 Instruction *SI = SI_A5->getNextNode()->getNextNode(); 123 assert(isa<StoreInst>(SI) && 124 SI->getOperand(1)->getName() == "arrayidx_A" && 125 "Expecting store to arrayidx_A"); 126 Instruction *LI1 = SI->getNextNode(); 127 assert(LI1->getName() == "load1" && "Expecting LI1 to be load1"); 128 Instruction *LI2 = LI1->getNextNode()->getNextNode()->getNextNode(); 129 assert(LI2->getName() == "load2" && "Expecting LI2 to be load2"); 130 Instruction *SI_A6 = 131 LI2->getNextNode()->getNextNode()->getNextNode()->getNextNode(); 132 assert(isa<StoreInst>(SI_A6) && 133 SI_A6->getOperand(1)->getName() == "arrayidx_A6" && 134 "Expecting store to arrayidx_A6"); 135 136 // Can move after CI_safecall, as it does not throw, not synchronize, or 137 // must return. 138 EXPECT_TRUE(isSafeToMoveBefore(*CI_safecall->getPrevNode(), 139 *CI_safecall->getNextNode(), DT, PDT, 140 DI)); 141 142 // Cannot move CI_unsafecall, as it may throw. 143 EXPECT_FALSE(isSafeToMoveBefore(*CI_unsafecall->getNextNode(), 144 *CI_unsafecall, DT, PDT, DI)); 145 146 // Moving instruction to non control flow equivalent places are not 147 // supported. 148 EXPECT_FALSE( 149 isSafeToMoveBefore(*SI_A5, *Entry->getTerminator(), DT, PDT, DI)); 150 151 // Moving PHINode is not supported. 152 EXPECT_FALSE(isSafeToMoveBefore(PN, *PN.getNextNode()->getNextNode(), 153 DT, PDT, DI)); 154 155 // Cannot move non-PHINode before PHINode. 156 EXPECT_FALSE(isSafeToMoveBefore(*PN.getNextNode(), PN, DT, PDT, DI)); 157 158 // Moving Terminator is not supported. 159 EXPECT_FALSE(isSafeToMoveBefore(*Entry->getTerminator(), 160 *PN.getNextNode(), DT, PDT, DI)); 161 162 // Cannot move %arrayidx_A after SI, as SI is its user. 163 EXPECT_FALSE(isSafeToMoveBefore(*SI->getPrevNode(), *SI->getNextNode(), 164 DT, PDT, DI)); 165 166 // Cannot move SI before %arrayidx_A, as %arrayidx_A is its operand. 167 EXPECT_FALSE(isSafeToMoveBefore(*SI, *SI->getPrevNode(), DT, PDT, DI)); 168 169 // Cannot move LI2 after SI_A6, as there is a flow dependence. 170 EXPECT_FALSE( 171 isSafeToMoveBefore(*LI2, *SI_A6->getNextNode(), DT, PDT, DI)); 172 173 // Cannot move SI after LI1, as there is a anti dependence. 174 EXPECT_FALSE(isSafeToMoveBefore(*SI, *LI1->getNextNode(), DT, PDT, DI)); 175 176 // Cannot move SI_A5 after SI, as there is a output dependence. 177 EXPECT_FALSE(isSafeToMoveBefore(*SI_A5, *LI1, DT, PDT, DI)); 178 179 // Can move LI2 before LI1, as there is only an input dependence. 180 EXPECT_TRUE(isSafeToMoveBefore(*LI2, *LI1, DT, PDT, DI)); 181 }); 182 } 183