1 //===- LoopUtilsTest.cpp - Unit tests for LoopUtils -----------------------===// 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/LoopUtils.h" 10 #include "llvm/Analysis/AssumptionCache.h" 11 #include "llvm/Analysis/LoopInfo.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/IR/Module.h" 17 #include "llvm/Support/SourceMgr.h" 18 #include "gtest/gtest.h" 19 20 using namespace llvm; 21 22 static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) { 23 SMDiagnostic Err; 24 std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C); 25 if (!Mod) 26 Err.print("LoopUtilsTests", errs()); 27 return Mod; 28 } 29 30 static void run(Module &M, StringRef FuncName, 31 function_ref<void(Function &F, DominatorTree &DT, 32 ScalarEvolution &SE, LoopInfo &LI)> 33 Test) { 34 Function *F = M.getFunction(FuncName); 35 DominatorTree DT(*F); 36 TargetLibraryInfoImpl TLII; 37 TargetLibraryInfo TLI(TLII); 38 AssumptionCache AC(*F); 39 LoopInfo LI(DT); 40 ScalarEvolution SE(*F, TLI, AC, DT, LI); 41 Test(*F, DT, SE, LI); 42 } 43 44 TEST(LoopUtils, DeleteDeadLoopNest) { 45 LLVMContext C; 46 std::unique_ptr<Module> M = 47 parseIR(C, "define void @foo() {\n" 48 "entry:\n" 49 " br label %for.i\n" 50 "for.i:\n" 51 " %i = phi i64 [ 0, %entry ], [ %inc.i, %for.i.latch ]\n" 52 " br label %for.j\n" 53 "for.j:\n" 54 " %j = phi i64 [ 0, %for.i ], [ %inc.j, %for.j ]\n" 55 " %inc.j = add nsw i64 %j, 1\n" 56 " %cmp.j = icmp slt i64 %inc.j, 100\n" 57 " br i1 %cmp.j, label %for.j, label %for.k.preheader\n" 58 "for.k.preheader:\n" 59 " br label %for.k\n" 60 "for.k:\n" 61 " %k = phi i64 [ %inc.k, %for.k ], [ 0, %for.k.preheader ]\n" 62 " %inc.k = add nsw i64 %k, 1\n" 63 " %cmp.k = icmp slt i64 %inc.k, 100\n" 64 " br i1 %cmp.k, label %for.k, label %for.i.latch\n" 65 "for.i.latch:\n" 66 " %inc.i = add nsw i64 %i, 1\n" 67 " %cmp.i = icmp slt i64 %inc.i, 100\n" 68 " br i1 %cmp.i, label %for.i, label %for.end\n" 69 "for.end:\n" 70 " ret void\n" 71 "}\n"); 72 73 run(*M, "foo", 74 [&](Function &F, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI) { 75 assert(LI.begin() != LI.end() && "Expecting loops in function F"); 76 Loop *L = *LI.begin(); 77 assert(L && L->getName() == "for.i" && "Expecting loop for.i"); 78 79 deleteDeadLoop(L, &DT, &SE, &LI); 80 81 assert(DT.verify(DominatorTree::VerificationLevel::Fast) && 82 "Expecting valid dominator tree"); 83 LI.verify(DT); 84 assert(LI.begin() == LI.end() && 85 "Expecting no loops left in function F"); 86 SE.verify(); 87 88 Function::iterator FI = F.begin(); 89 BasicBlock *Entry = &*(FI++); 90 assert(Entry->getName() == "entry" && "Expecting BasicBlock entry"); 91 const BranchInst *BI = dyn_cast<BranchInst>(Entry->getTerminator()); 92 assert(BI && "Expecting valid branch instruction"); 93 EXPECT_EQ(BI->getNumSuccessors(), (unsigned)1); 94 EXPECT_EQ(BI->getSuccessor(0)->getName(), "for.end"); 95 }); 96 } 97 98 TEST(LoopUtils, IsKnownPositiveInLoopTest) { 99 LLVMContext C; 100 std::unique_ptr<Module> M = 101 parseIR(C, "define void @foo(i32 %n, i1 %c) {\n" 102 "entry:\n" 103 " %is.positive = icmp sgt i32 %n, 0\n" 104 " br i1 %is.positive, label %loop, label %exit\n" 105 "loop:\n" 106 " br i1 %c, label %loop, label %exit\n" 107 "exit:\n" 108 " ret void\n" 109 "}\n"); 110 111 run(*M, "foo", 112 [&](Function &F, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI) { 113 assert(LI.begin() != LI.end() && "Expecting loops in function F"); 114 Loop *L = *LI.begin(); 115 assert(L && L->getName() == "loop" && "Expecting loop 'loop'"); 116 auto *Arg = F.getArg(0); 117 const SCEV *ArgSCEV = SE.getSCEV(Arg); 118 EXPECT_EQ(isKnownPositiveInLoop(ArgSCEV, L, SE), true); 119 }); 120 } 121 122 TEST(LoopUtils, IsKnownNonPositiveInLoopTest) { 123 LLVMContext C; 124 std::unique_ptr<Module> M = 125 parseIR(C, "define void @foo(i32 %n, i1 %c) {\n" 126 "entry:\n" 127 " %is.non.positive = icmp sle i32 %n, 0\n" 128 " br i1 %is.non.positive, label %loop, label %exit\n" 129 "loop:\n" 130 " br i1 %c, label %loop, label %exit\n" 131 "exit:\n" 132 " ret void\n" 133 "}\n"); 134 135 run(*M, "foo", 136 [&](Function &F, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI) { 137 assert(LI.begin() != LI.end() && "Expecting loops in function F"); 138 Loop *L = *LI.begin(); 139 assert(L && L->getName() == "loop" && "Expecting loop 'loop'"); 140 auto *Arg = F.getArg(0); 141 const SCEV *ArgSCEV = SE.getSCEV(Arg); 142 EXPECT_EQ(isKnownNonPositiveInLoop(ArgSCEV, L, SE), true); 143 }); 144 } 145