1 //===- LoopRotationUtilsTest.cpp - Unit tests for LoopRotation utility ----===//
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/LoopRotationUtils.h"
10 #include "llvm/Analysis/AssumptionCache.h"
11 #include "llvm/Analysis/InstructionSimplify.h"
12 #include "llvm/Analysis/LoopInfo.h"
13 #include "llvm/Analysis/ScalarEvolution.h"
14 #include "llvm/Analysis/TargetLibraryInfo.h"
15 #include "llvm/Analysis/TargetTransformInfo.h"
16 #include "llvm/AsmParser/Parser.h"
17 #include "llvm/IR/Dominators.h"
18 #include "llvm/IR/LLVMContext.h"
19 #include "llvm/Support/SourceMgr.h"
20 #include "gtest/gtest.h"
21
22 using namespace llvm;
23
parseIR(LLVMContext & C,const char * IR)24 static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {
25 SMDiagnostic Err;
26 std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);
27 if (!Mod)
28 Err.print("LoopRotationUtilsTest", errs());
29 return Mod;
30 }
31
32 /// This test contains multi-deopt-exits pattern that might allow loop rotation
33 /// to trigger multiple times if multiple rotations are enabled.
34 /// At least one rotation should be performed, no matter what loop rotation settings are.
TEST(LoopRotate,MultiDeoptExit)35 TEST(LoopRotate, MultiDeoptExit) {
36 LLVMContext C;
37
38 std::unique_ptr<Module> M = parseIR(
39 C,
40 R"(
41 declare i32 @llvm.experimental.deoptimize.i32(...)
42
43 define i32 @test(i32 * nonnull %a, i64 %x) {
44 entry:
45 br label %for.cond1
46
47 for.cond1:
48 %idx = phi i64 [ 0, %entry ], [ %idx.next, %for.tail ]
49 %sum = phi i32 [ 0, %entry ], [ %sum.next, %for.tail ]
50 %a.idx = getelementptr inbounds i32, i32 *%a, i64 %idx
51 %val.a.idx = load i32, i32* %a.idx, align 4
52 %zero.check = icmp eq i32 %val.a.idx, 0
53 br i1 %zero.check, label %deopt.exit, label %for.cond2
54
55 for.cond2:
56 %for.check = icmp ult i64 %idx, %x
57 br i1 %for.check, label %for.body, label %return
58
59 for.body:
60 br label %for.tail
61
62 for.tail:
63 %sum.next = add i32 %sum, %val.a.idx
64 %idx.next = add nuw nsw i64 %idx, 1
65 br label %for.cond1
66
67 return:
68 ret i32 %sum
69
70 deopt.exit:
71 %deopt.val = call i32(...) @llvm.experimental.deoptimize.i32() [ "deopt"(i32 %val.a.idx) ]
72 ret i32 %deopt.val
73 })"
74 );
75
76 auto *F = M->getFunction("test");
77 DominatorTree DT(*F);
78 LoopInfo LI(DT);
79 AssumptionCache AC(*F);
80 TargetTransformInfo TTI(M->getDataLayout());
81 TargetLibraryInfoImpl TLII;
82 TargetLibraryInfo TLI(TLII);
83 ScalarEvolution SE(*F, TLI, AC, DT, LI);
84 SimplifyQuery SQ(M->getDataLayout());
85
86 Loop *L = *LI.begin();
87
88 bool ret = LoopRotation(L, &LI, &TTI,
89 &AC, &DT,
90 &SE, nullptr,
91 SQ, true, -1, false);
92 EXPECT_TRUE(ret);
93 }
94
95 /// Checking a special case of multi-deopt exit loop that can not perform
96 /// required amount of rotations due to the desired header containing
97 /// non-duplicatable code.
98 /// Similar to MultiDeoptExit test this one should do at least one rotation and
99 /// pass no matter what loop rotation settings are.
TEST(LoopRotate,MultiDeoptExit_Nondup)100 TEST(LoopRotate, MultiDeoptExit_Nondup) {
101 LLVMContext C;
102
103 std::unique_ptr<Module> M = parseIR(
104 C,
105 R"(
106 ; Rotation should be done once, attempted twice.
107 ; Second time fails due to non-duplicatable header.
108
109 declare i32 @llvm.experimental.deoptimize.i32(...)
110
111 declare void @nondup()
112
113 define i32 @test_nondup(i32 * nonnull %a, i64 %x) {
114 entry:
115 br label %for.cond1
116
117 for.cond1:
118 %idx = phi i64 [ 0, %entry ], [ %idx.next, %for.tail ]
119 %sum = phi i32 [ 0, %entry ], [ %sum.next, %for.tail ]
120 %a.idx = getelementptr inbounds i32, i32 *%a, i64 %idx
121 %val.a.idx = load i32, i32* %a.idx, align 4
122 %zero.check = icmp eq i32 %val.a.idx, 0
123 br i1 %zero.check, label %deopt.exit, label %for.cond2
124
125 for.cond2:
126 call void @nondup() noduplicate
127 %for.check = icmp ult i64 %idx, %x
128 br i1 %for.check, label %for.body, label %return
129
130 for.body:
131 br label %for.tail
132
133 for.tail:
134 %sum.next = add i32 %sum, %val.a.idx
135 %idx.next = add nuw nsw i64 %idx, 1
136 br label %for.cond1
137
138 return:
139 ret i32 %sum
140
141 deopt.exit:
142 %deopt.val = call i32(...) @llvm.experimental.deoptimize.i32() [ "deopt"(i32 %val.a.idx) ]
143 ret i32 %deopt.val
144 })"
145 );
146
147 auto *F = M->getFunction("test_nondup");
148 DominatorTree DT(*F);
149 LoopInfo LI(DT);
150 AssumptionCache AC(*F);
151 TargetTransformInfo TTI(M->getDataLayout());
152 TargetLibraryInfoImpl TLII;
153 TargetLibraryInfo TLI(TLII);
154 ScalarEvolution SE(*F, TLI, AC, DT, LI);
155 SimplifyQuery SQ(M->getDataLayout());
156
157 Loop *L = *LI.begin();
158
159 bool ret = LoopRotation(L, &LI, &TTI,
160 &AC, &DT,
161 &SE, nullptr,
162 SQ, true, -1, false);
163 /// LoopRotation should properly report "true" as we still perform the first rotation
164 /// so we do change the IR.
165 EXPECT_TRUE(ret);
166 }
167