1 //===- llvm/unittests/Transforms/Vectorize/VPlanPredicatorTest.cpp -----===//
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 "../lib/Transforms/Vectorize/VPlanPredicator.h"
10 #include "VPlanTestBase.h"
11 #include "gtest/gtest.h"
12
13 namespace llvm {
14 namespace {
15
16 class VPlanPredicatorTest : public VPlanTestBase {};
17
TEST_F(VPlanPredicatorTest,BasicPredicatorTest)18 TEST_F(VPlanPredicatorTest, BasicPredicatorTest) {
19 const char *ModuleString =
20 "@arr = common global [8 x [8 x i64]] "
21 "zeroinitializer, align 16\n"
22 "@arr2 = common global [8 x [8 x i64]] "
23 "zeroinitializer, align 16\n"
24 "@arr3 = common global [8 x [8 x i64]] "
25 "zeroinitializer, align 16\n"
26 "define void @f(i64 %n1) {\n"
27 "entry:\n"
28 " br label %for.cond1.preheader\n"
29 "for.cond1.preheader: \n"
30 " %i1.029 = phi i64 [ 0, %entry ], [ %inc14, %for.inc13 ]\n"
31 " br label %for.body3\n"
32 "for.body3: \n"
33 " %i2.028 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.inc ]\n"
34 " %arrayidx4 = getelementptr inbounds [8 x [8 x i64]], [8 x [8 x i64]]* "
35 "@arr, i64 0, i64 %i2.028, i64 %i1.029\n"
36 " %0 = load i64, i64* %arrayidx4, align 8\n"
37 " %cmp5 = icmp ugt i64 %0, 10\n"
38 " br i1 %cmp5, label %if.then, label %for.inc\n"
39 "if.then: \n"
40 " %arrayidx7 = getelementptr inbounds [8 x [8 x i64]], [8 x [8 x i64]]* "
41 "@arr2, i64 0, i64 %i2.028, i64 %i1.029\n"
42 " %1 = load i64, i64* %arrayidx7, align 8\n"
43 " %cmp8 = icmp ugt i64 %1, 100\n"
44 " br i1 %cmp8, label %if.then9, label %for.inc\n"
45 "if.then9: \n"
46 " %add = add nuw nsw i64 %i2.028, %i1.029\n"
47 " %arrayidx11 = getelementptr inbounds [8 x [8 x i64]], [8 x [8 x "
48 "i64]]* @arr3, i64 0, i64 %i2.028, i64 %i1.029\n"
49 " store i64 %add, i64* %arrayidx11, align 8\n"
50 " br label %for.inc\n"
51 "for.inc: \n"
52 " %inc = add nuw nsw i64 %i2.028, 1\n"
53 " %exitcond = icmp eq i64 %inc, 8\n"
54 " br i1 %exitcond, label %for.inc13, label %for.body3\n"
55 "for.inc13: \n"
56 " %inc14 = add nuw nsw i64 %i1.029, 1\n"
57 " %exitcond30 = icmp eq i64 %inc14, 8\n"
58 " br i1 %exitcond30, label %for.end15, label %for.cond1.preheader\n"
59 "for.end15: \n"
60 " ret void\n"
61 "}\n";
62
63 Module &M = parseModule(ModuleString);
64
65 Function *F = M.getFunction("f");
66 BasicBlock *LoopHeader = F->getEntryBlock().getSingleSuccessor();
67 auto Plan = buildHCFG(LoopHeader);
68
69 VPRegionBlock *TopRegion = cast<VPRegionBlock>(Plan->getEntry());
70 VPBlockBase *PH = TopRegion->getEntry();
71 VPBlockBase *H = PH->getSingleSuccessor();
72 VPBlockBase *InnerLoopH = H->getSingleSuccessor();
73 VPBlockBase *OuterIf = InnerLoopH->getSuccessors()[0];
74 VPBlockBase *InnerLoopLatch = InnerLoopH->getSuccessors()[1];
75 VPBlockBase *InnerIf = OuterIf->getSuccessors()[0];
76 VPValue *CBV1 = InnerLoopH->getCondBit();
77 VPValue *CBV2 = OuterIf->getCondBit();
78
79 // Apply predication.
80 VPlanPredicator VPP(*Plan);
81 VPP.predicate();
82
83 VPBlockBase *InnerLoopLinSucc = InnerLoopH->getSingleSuccessor();
84 VPBlockBase *OuterIfLinSucc = OuterIf->getSingleSuccessor();
85 VPBlockBase *InnerIfLinSucc = InnerIf->getSingleSuccessor();
86 VPValue *OuterIfPred = OuterIf->getPredicate();
87 VPInstruction *InnerAnd =
88 cast<VPInstruction>(InnerIf->getEntryBasicBlock()->begin());
89 VPValue *InnerIfPred = InnerIf->getPredicate();
90
91 // Test block predicates
92 EXPECT_NE(nullptr, CBV1);
93 EXPECT_NE(nullptr, CBV2);
94 EXPECT_NE(nullptr, InnerAnd);
95 EXPECT_EQ(CBV1, OuterIfPred);
96 EXPECT_EQ(InnerAnd->getOpcode(), Instruction::And);
97 EXPECT_EQ(InnerAnd->getOperand(0), CBV1);
98 EXPECT_EQ(InnerAnd->getOperand(1), CBV2);
99 EXPECT_EQ(InnerIfPred, InnerAnd);
100
101 // Test Linearization
102 EXPECT_EQ(InnerLoopLinSucc, OuterIf);
103 EXPECT_EQ(OuterIfLinSucc, InnerIf);
104 EXPECT_EQ(InnerIfLinSucc, InnerLoopLatch);
105
106 // Check that the containing VPlan is set correctly.
107 EXPECT_EQ(&*Plan, InnerLoopLinSucc->getPlan());
108 EXPECT_EQ(&*Plan, OuterIfLinSucc->getPlan());
109 EXPECT_EQ(&*Plan, InnerIfLinSucc->getPlan());
110 EXPECT_EQ(&*Plan, InnerIf->getPlan());
111 EXPECT_EQ(&*Plan, InnerLoopLatch->getPlan());
112 }
113
114 // Test generation of Not and Or during predication.
TEST_F(VPlanPredicatorTest,PredicatorNegOrTest)115 TEST_F(VPlanPredicatorTest, PredicatorNegOrTest) {
116 const char *ModuleString =
117 "@arr = common global [100 x [100 x i32]] zeroinitializer, align 16\n"
118 "@arr2 = common global [100 x [100 x i32]] zeroinitializer, align 16\n"
119 "@arr3 = common global [100 x [100 x i32]] zeroinitializer, align 16\n"
120 "define void @foo() {\n"
121 "entry:\n"
122 " br label %for.cond1.preheader\n"
123 "for.cond1.preheader: \n"
124 " %indvars.iv42 = phi i64 [ 0, %entry ], [ %indvars.iv.next43, "
125 "%for.inc22 ]\n"
126 " br label %for.body3\n"
127 "for.body3: \n"
128 " %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ "
129 "%indvars.iv.next, %if.end21 ]\n"
130 " %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 "
131 "x i32]]* @arr, i64 0, i64 %indvars.iv, i64 %indvars.iv42\n"
132 " %0 = load i32, i32* %arrayidx5, align 4\n"
133 " %cmp6 = icmp slt i32 %0, 100\n"
134 " br i1 %cmp6, label %if.then, label %if.end21\n"
135 "if.then: \n"
136 " %cmp7 = icmp sgt i32 %0, 10\n"
137 " br i1 %cmp7, label %if.then8, label %if.else\n"
138 "if.then8: \n"
139 " %add = add nsw i32 %0, 10\n"
140 " %arrayidx12 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 "
141 "x i32]]* @arr2, i64 0, i64 %indvars.iv, i64 %indvars.iv42\n"
142 " store i32 %add, i32* %arrayidx12, align 4\n"
143 " br label %if.end\n"
144 "if.else: \n"
145 " %sub = add nsw i32 %0, -10\n"
146 " %arrayidx16 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 "
147 "x i32]]* @arr3, i64 0, i64 %indvars.iv, i64 %indvars.iv42\n"
148 " store i32 %sub, i32* %arrayidx16, align 4\n"
149 " br label %if.end\n"
150 "if.end: \n"
151 " store i32 222, i32* %arrayidx5, align 4\n"
152 " br label %if.end21\n"
153 "if.end21: \n"
154 " %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1\n"
155 " %exitcond = icmp eq i64 %indvars.iv.next, 100\n"
156 " br i1 %exitcond, label %for.inc22, label %for.body3\n"
157 "for.inc22: \n"
158 " %indvars.iv.next43 = add nuw nsw i64 %indvars.iv42, 1\n"
159 " %exitcond44 = icmp eq i64 %indvars.iv.next43, 100\n"
160 " br i1 %exitcond44, label %for.end24, label %for.cond1.preheader\n"
161 "for.end24: \n"
162 " ret void\n"
163 "}\n";
164
165 Module &M = parseModule(ModuleString);
166 Function *F = M.getFunction("foo");
167 BasicBlock *LoopHeader = F->getEntryBlock().getSingleSuccessor();
168 auto Plan = buildHCFG(LoopHeader);
169
170 VPRegionBlock *TopRegion = cast<VPRegionBlock>(Plan->getEntry());
171 VPBlockBase *PH = TopRegion->getEntry();
172 VPBlockBase *H = PH->getSingleSuccessor();
173 VPBlockBase *OuterIfCmpBlk = H->getSingleSuccessor();
174 VPBlockBase *InnerIfCmpBlk = OuterIfCmpBlk->getSuccessors()[0];
175 VPBlockBase *InnerIfTSucc = InnerIfCmpBlk->getSuccessors()[0];
176 VPBlockBase *InnerIfFSucc = InnerIfCmpBlk->getSuccessors()[1];
177 VPBlockBase *TSuccSucc = InnerIfTSucc->getSingleSuccessor();
178 VPBlockBase *FSuccSucc = InnerIfFSucc->getSingleSuccessor();
179
180 VPValue *OuterCBV = OuterIfCmpBlk->getCondBit();
181 VPValue *InnerCBV = InnerIfCmpBlk->getCondBit();
182
183 // Apply predication.
184 VPlanPredicator VPP(*Plan);
185 VPP.predicate();
186
187 VPInstruction *And =
188 cast<VPInstruction>(InnerIfTSucc->getEntryBasicBlock()->begin());
189 VPInstruction *Not =
190 cast<VPInstruction>(InnerIfFSucc->getEntryBasicBlock()->begin());
191 VPInstruction *NotAnd = cast<VPInstruction>(
192 &*std::next(InnerIfFSucc->getEntryBasicBlock()->begin(), 1));
193 VPInstruction *Or =
194 cast<VPInstruction>(TSuccSucc->getEntryBasicBlock()->begin());
195
196 // Test block predicates
197 EXPECT_NE(nullptr, OuterCBV);
198 EXPECT_NE(nullptr, InnerCBV);
199 EXPECT_NE(nullptr, And);
200 EXPECT_NE(nullptr, Not);
201 EXPECT_NE(nullptr, NotAnd);
202
203 EXPECT_EQ(And->getOpcode(), Instruction::And);
204 EXPECT_EQ(NotAnd->getOpcode(), Instruction::And);
205 EXPECT_EQ(Not->getOpcode(), VPInstruction::Not);
206
207 EXPECT_EQ(And->getOperand(0), OuterCBV);
208 EXPECT_EQ(And->getOperand(1), InnerCBV);
209
210 EXPECT_EQ(Not->getOperand(0), InnerCBV);
211
212 EXPECT_EQ(NotAnd->getOperand(0), OuterCBV);
213 EXPECT_EQ(NotAnd->getOperand(1), Not);
214
215 EXPECT_EQ(InnerIfTSucc->getPredicate(), And);
216 EXPECT_EQ(InnerIfFSucc->getPredicate(), NotAnd);
217
218 EXPECT_EQ(TSuccSucc, FSuccSucc);
219 EXPECT_EQ(Or->getOpcode(), Instruction::Or);
220 EXPECT_EQ(TSuccSucc->getPredicate(), Or);
221
222 // Test operands of the Or - account for differences in predecessor block
223 // ordering.
224 VPInstruction *OrOp0Inst = cast<VPInstruction>(Or->getOperand(0));
225 VPInstruction *OrOp1Inst = cast<VPInstruction>(Or->getOperand(1));
226
227 bool ValidOrOperands = false;
228 if (((OrOp0Inst == And) && (OrOp1Inst == NotAnd)) ||
229 ((OrOp0Inst == NotAnd) && (OrOp1Inst == And)))
230 ValidOrOperands = true;
231
232 EXPECT_TRUE(ValidOrOperands);
233 }
234
235 } // namespace
236 } // namespace llvm
237