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