xref: /llvm-project/llvm/unittests/Transforms/Vectorize/VPlanHCFGTest.cpp (revision 1395cd015f2edf26f8c2567870183d63f4fdd753) 
1 //===- llvm/unittest/Transforms/Vectorize/VPlanHCFGTest.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/VPlan.h"
10 #include "../lib/Transforms/Vectorize/VPlanTransforms.h"
11 #include "VPlanTestBase.h"
12 #include "llvm/Analysis/TargetLibraryInfo.h"
13 #include "llvm/TargetParser/Triple.h"
14 #include "gtest/gtest.h"
15 #include <string>
16 
17 namespace llvm {
18 namespace {
19 
20 class VPlanHCFGTest : public VPlanTestIRBase {};
21 
22 TEST_F(VPlanHCFGTest, testBuildHCFGInnerLoop) {
23   const char *ModuleString =
24       "define void @f(ptr %A, i64 %N) {\n"
25       "entry:\n"
26       "  br label %for.body\n"
27       "for.body:\n"
28       "  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]\n"
29       "  %arr.idx = getelementptr inbounds i32, ptr %A, i64 %indvars.iv\n"
30       "  %l1 = load i32, ptr %arr.idx, align 4\n"
31       "  %res = add i32 %l1, 10\n"
32       "  store i32 %res, ptr %arr.idx, align 4\n"
33       "  %indvars.iv.next = add i64 %indvars.iv, 1\n"
34       "  %exitcond = icmp ne i64 %indvars.iv.next, %N\n"
35       "  br i1 %exitcond, label %for.body, label %for.end\n"
36       "for.end:\n"
37       "  ret void\n"
38       "}\n";
39 
40   Module &M = parseModule(ModuleString);
41 
42   Function *F = M.getFunction("f");
43   BasicBlock *LoopHeader = F->getEntryBlock().getSingleSuccessor();
44   auto Plan = buildHCFG(LoopHeader);
45 
46   VPBasicBlock *Entry = Plan->getEntry()->getEntryBasicBlock();
47   EXPECT_NE(nullptr, Entry->getSingleSuccessor());
48   EXPECT_EQ(0u, Entry->getNumPredecessors());
49   EXPECT_EQ(1u, Entry->getNumSuccessors());
50 
51   // Check that the region following the preheader consists of a block for the
52   // original header and a separate latch.
53   VPBasicBlock *VecBB = Plan->getVectorLoopRegion()->getEntryBasicBlock();
54   EXPECT_EQ(7u, VecBB->size());
55   EXPECT_EQ(0u, VecBB->getNumPredecessors());
56   EXPECT_EQ(1u, VecBB->getNumSuccessors());
57   EXPECT_EQ(VecBB->getParent()->getEntryBasicBlock(), VecBB);
58   EXPECT_EQ(&*Plan, VecBB->getPlan());
59 
60   VPBlockBase *VecLatch = VecBB->getSingleSuccessor();
61   EXPECT_EQ(VecLatch->getParent()->getExitingBasicBlock(), VecLatch);
62   EXPECT_EQ(0u, VecLatch->getNumSuccessors());
63 
64   auto Iter = VecBB->begin();
65   VPWidenPHIRecipe *Phi = dyn_cast<VPWidenPHIRecipe>(&*Iter++);
66   EXPECT_NE(nullptr, Phi);
67 
68   VPInstruction *Idx = dyn_cast<VPInstruction>(&*Iter++);
69   EXPECT_EQ(Instruction::GetElementPtr, Idx->getOpcode());
70   EXPECT_EQ(2u, Idx->getNumOperands());
71   EXPECT_EQ(Phi, Idx->getOperand(1));
72 
73   VPInstruction *Load = dyn_cast<VPInstruction>(&*Iter++);
74   EXPECT_EQ(Instruction::Load, Load->getOpcode());
75   EXPECT_EQ(1u, Load->getNumOperands());
76   EXPECT_EQ(Idx, Load->getOperand(0));
77 
78   VPInstruction *Add = dyn_cast<VPInstruction>(&*Iter++);
79   EXPECT_EQ(Instruction::Add, Add->getOpcode());
80   EXPECT_EQ(2u, Add->getNumOperands());
81   EXPECT_EQ(Load, Add->getOperand(0));
82 
83   VPInstruction *Store = dyn_cast<VPInstruction>(&*Iter++);
84   EXPECT_EQ(Instruction::Store, Store->getOpcode());
85   EXPECT_EQ(2u, Store->getNumOperands());
86   EXPECT_EQ(Add, Store->getOperand(0));
87   EXPECT_EQ(Idx, Store->getOperand(1));
88 
89   VPInstruction *IndvarAdd = dyn_cast<VPInstruction>(&*Iter++);
90   EXPECT_EQ(Instruction::Add, IndvarAdd->getOpcode());
91   EXPECT_EQ(2u, IndvarAdd->getNumOperands());
92   EXPECT_EQ(Phi, IndvarAdd->getOperand(0));
93 
94   VPInstruction *ICmp = dyn_cast<VPInstruction>(&*Iter++);
95   EXPECT_EQ(Instruction::ICmp, ICmp->getOpcode());
96   EXPECT_EQ(2u, ICmp->getNumOperands());
97   EXPECT_EQ(IndvarAdd, ICmp->getOperand(0));
98 
99 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
100   // Add an external value to check we do not print the list of external values,
101   // as this is not required with the new printing.
102   Plan->getOrAddLiveIn(&*F->arg_begin());
103   std::string FullDump;
104   raw_string_ostream OS(FullDump);
105   Plan->printDOT(OS);
106   const char *ExpectedStr = R"(digraph VPlan {
107 graph [labelloc=t, fontsize=30; label="Vectorization Plan\n for UF\>=1\nLive-in vp\<%0\> = vector-trip-count\nLive-in ir\<%N\> = original trip-count\n"]
108 node [shape=rect, fontname=Courier, fontsize=30]
109 edge [fontname=Courier, fontsize=30]
110 compound=true
111   N0 [label =
112     "ir-bb\<entry\>:\l" +
113     "Successor(s): vector.ph\l"
114   ]
115   N0 -> N1 [ label=""]
116   N1 [label =
117     "vector.ph:\l" +
118     "Successor(s): vector loop\l"
119   ]
120   N1 -> N2 [ label="" lhead=cluster_N3]
121   subgraph cluster_N3 {
122     fontname=Courier
123     label="\<x1\> vector loop"
124     N2 [label =
125       "vector.body:\l" +
126       "  WIDEN-PHI ir\<%indvars.iv\> = phi ir\<0\>, ir\<%indvars.iv.next\>\l" +
127       "  EMIT ir\<%arr.idx\> = getelementptr ir\<%A\>, ir\<%indvars.iv\>\l" +
128       "  EMIT ir\<%l1\> = load ir\<%arr.idx\>\l" +
129       "  EMIT ir\<%res\> = add ir\<%l1\>, ir\<10\>\l" +
130       "  EMIT store ir\<%res\>, ir\<%arr.idx\>\l" +
131       "  EMIT ir\<%indvars.iv.next\> = add ir\<%indvars.iv\>, ir\<1\>\l" +
132       "  EMIT ir\<%exitcond\> = icmp ir\<%indvars.iv.next\>, ir\<%N\>\l" +
133       "Successor(s): vector.latch\l"
134     ]
135     N2 -> N4 [ label=""]
136     N4 [label =
137       "vector.latch:\l" +
138       "No successors\l"
139     ]
140   }
141   N4 -> N5 [ label="" ltail=cluster_N3]
142   N5 [label =
143     "middle.block:\l" +
144     "  EMIT vp\<%cmp.n\> = icmp eq ir\<%N\>, vp\<%0\>\l" +
145     "  EMIT branch-on-cond vp\<%cmp.n\>\l" +
146     "Successor(s): ir-bb\<for.end\>, scalar.ph\l"
147   ]
148   N5 -> N6 [ label="T"]
149   N5 -> N7 [ label="F"]
150   N6 [label =
151     "ir-bb\<for.end\>:\l" +
152     "No successors\l"
153   ]
154   N7 [label =
155     "scalar.ph:\l" +
156     "Successor(s): ir-bb\<for.body\>\l"
157   ]
158   N7 -> N8 [ label=""]
159   N8 [label =
160     "ir-bb\<for.body\>:\l" +
161     "  IR   %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]\l" +
162     "  IR   %arr.idx = getelementptr inbounds i32, ptr %A, i64 %indvars.iv\l" +
163     "  IR   %l1 = load i32, ptr %arr.idx, align 4\l" +
164     "  IR   %res = add i32 %l1, 10\l" +
165     "  IR   store i32 %res, ptr %arr.idx, align 4\l" +
166     "  IR   %indvars.iv.next = add i64 %indvars.iv, 1\l" +
167     "  IR   %exitcond = icmp ne i64 %indvars.iv.next, %N\l" +
168     "No successors\l"
169   ]
170 }
171 )";
172   EXPECT_EQ(ExpectedStr, FullDump);
173 #endif
174   TargetLibraryInfoImpl TLII(Triple(M.getTargetTriple()));
175   TargetLibraryInfo TLI(TLII);
176   VPlanTransforms::VPInstructionsToVPRecipes(
177       Plan, [](PHINode *P) { return nullptr; }, *SE, TLI);
178 }
179 
180 TEST_F(VPlanHCFGTest, testVPInstructionToVPRecipesInner) {
181   const char *ModuleString =
182       "define void @f(ptr %A, i64 %N) {\n"
183       "entry:\n"
184       "  br label %for.body\n"
185       "for.body:\n"
186       "  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]\n"
187       "  %arr.idx = getelementptr inbounds i32, ptr %A, i64 %indvars.iv\n"
188       "  %l1 = load i32, ptr %arr.idx, align 4\n"
189       "  %res = add i32 %l1, 10\n"
190       "  store i32 %res, ptr %arr.idx, align 4\n"
191       "  %indvars.iv.next = add i64 %indvars.iv, 1\n"
192       "  %exitcond = icmp ne i64 %indvars.iv.next, %N\n"
193       "  br i1 %exitcond, label %for.body, label %for.end\n"
194       "for.end:\n"
195       "  ret void\n"
196       "}\n";
197 
198   Module &M = parseModule(ModuleString);
199 
200   Function *F = M.getFunction("f");
201   BasicBlock *LoopHeader = F->getEntryBlock().getSingleSuccessor();
202   auto Plan = buildHCFG(LoopHeader);
203 
204   TargetLibraryInfoImpl TLII(Triple(M.getTargetTriple()));
205   TargetLibraryInfo TLI(TLII);
206   VPlanTransforms::VPInstructionsToVPRecipes(
207       Plan, [](PHINode *P) { return nullptr; }, *SE, TLI);
208 
209   VPBlockBase *Entry = Plan->getEntry()->getEntryBasicBlock();
210   EXPECT_NE(nullptr, Entry->getSingleSuccessor());
211   EXPECT_EQ(0u, Entry->getNumPredecessors());
212   EXPECT_EQ(1u, Entry->getNumSuccessors());
213 
214   // Check that the region following the preheader consists of a block for the
215   // original header and a separate latch.
216   VPBasicBlock *VecBB = Plan->getVectorLoopRegion()->getEntryBasicBlock();
217   EXPECT_EQ(7u, VecBB->size());
218   EXPECT_EQ(0u, VecBB->getNumPredecessors());
219   EXPECT_EQ(1u, VecBB->getNumSuccessors());
220   EXPECT_EQ(VecBB->getParent()->getEntryBasicBlock(), VecBB);
221 
222   VPBlockBase *VecLatch = VecBB->getSingleSuccessor();
223   EXPECT_EQ(VecLatch->getParent()->getExitingBasicBlock(), VecLatch);
224   EXPECT_EQ(0u, VecLatch->getNumSuccessors());
225 
226   auto Iter = VecBB->begin();
227   EXPECT_NE(nullptr, dyn_cast<VPWidenPHIRecipe>(&*Iter++));
228   EXPECT_NE(nullptr, dyn_cast<VPWidenGEPRecipe>(&*Iter++));
229   EXPECT_NE(nullptr, dyn_cast<VPWidenMemoryRecipe>(&*Iter++));
230   EXPECT_NE(nullptr, dyn_cast<VPWidenRecipe>(&*Iter++));
231   EXPECT_NE(nullptr, dyn_cast<VPWidenMemoryRecipe>(&*Iter++));
232   EXPECT_NE(nullptr, dyn_cast<VPWidenRecipe>(&*Iter++));
233   EXPECT_NE(nullptr, dyn_cast<VPWidenRecipe>(&*Iter++));
234   EXPECT_EQ(VecBB->end(), Iter);
235 }
236 
237 TEST_F(VPlanHCFGTest, testBuildHCFGInnerLoopMultiExit) {
238   const char *ModuleString =
239       "define void @f(ptr %A, i64 %N) {\n"
240       "entry:\n"
241       "  br label %loop.header\n"
242       "loop.header:\n"
243       "  %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]\n"
244       "  %arr.idx = getelementptr inbounds i32, ptr %A, i64 %iv\n"
245       "  %l1 = load i32, ptr %arr.idx, align 4\n"
246       "  %c = icmp eq i32 %l1, 0\n"
247       "  br i1 %c, label %exit.1, label %loop.latch\n"
248       "loop.latch:\n"
249       "  %res = add i32 %l1, 10\n"
250       "  store i32 %res, ptr %arr.idx, align 4\n"
251       "  %iv.next = add i64 %iv, 1\n"
252       "  %exitcond = icmp ne i64 %iv.next, %N\n"
253       "  br i1 %exitcond, label %loop.header, label %exit.2\n"
254       "exit.1:\n"
255       "  ret void\n"
256       "exit.2:\n"
257       "  ret void\n"
258       "}\n";
259 
260   Module &M = parseModule(ModuleString);
261 
262   Function *F = M.getFunction("f");
263   BasicBlock *LoopHeader = F->getEntryBlock().getSingleSuccessor();
264   auto Plan = buildHCFG(LoopHeader);
265 
266 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
267   // Add an external value to check we do not print the list of external values,
268   // as this is not required with the new printing.
269   Plan->getOrAddLiveIn(&*F->arg_begin());
270   std::string FullDump;
271   raw_string_ostream OS(FullDump);
272   Plan->printDOT(OS);
273   const char *ExpectedStr = R"(digraph VPlan {
274 graph [labelloc=t, fontsize=30; label="Vectorization Plan\n for UF\>=1\nLive-in vp\<%0\> = vector-trip-count\nLive-in ir\<%N\> = original trip-count\n"]
275 node [shape=rect, fontname=Courier, fontsize=30]
276 edge [fontname=Courier, fontsize=30]
277 compound=true
278   N0 [label =
279     "ir-bb\<entry\>:\l" +
280     "Successor(s): vector.ph\l"
281   ]
282   N0 -> N1 [ label=""]
283   N1 [label =
284     "vector.ph:\l" +
285     "Successor(s): vector loop\l"
286   ]
287   N1 -> N2 [ label="" lhead=cluster_N3]
288   subgraph cluster_N3 {
289     fontname=Courier
290     label="\<x1\> vector loop"
291     N2 [label =
292       "vector.body:\l" +
293       "  WIDEN-PHI ir\<%iv\> = phi ir\<0\>, ir\<%iv.next\>\l" +
294       "  EMIT ir\<%arr.idx\> = getelementptr ir\<%A\>, ir\<%iv\>\l" +
295       "  EMIT ir\<%l1\> = load ir\<%arr.idx\>\l" +
296       "  EMIT ir\<%c\> = icmp ir\<%l1\>, ir\<0\>\l" +
297       "Successor(s): loop.latch\l"
298     ]
299     N2 -> N4 [ label=""]
300     N4 [label =
301       "loop.latch:\l" +
302       "  EMIT ir\<%res\> = add ir\<%l1\>, ir\<10\>\l" +
303       "  EMIT store ir\<%res\>, ir\<%arr.idx\>\l" +
304       "  EMIT ir\<%iv.next\> = add ir\<%iv\>, ir\<1\>\l" +
305       "  EMIT ir\<%exitcond\> = icmp ir\<%iv.next\>, ir\<%N\>\l" +
306       "Successor(s): vector.latch\l"
307     ]
308     N4 -> N5 [ label=""]
309     N5 [label =
310       "vector.latch:\l" +
311       "No successors\l"
312     ]
313   }
314   N5 -> N6 [ label="" ltail=cluster_N3]
315   N6 [label =
316     "middle.block:\l" +
317     "  EMIT vp\<%cmp.n\> = icmp eq ir\<%N\>, vp\<%0\>\l" +
318     "  EMIT branch-on-cond vp\<%cmp.n\>\l" +
319     "Successor(s): ir-bb\<exit.2\>, scalar.ph\l"
320   ]
321   N6 -> N7 [ label="T"]
322   N6 -> N8 [ label="F"]
323   N7 [label =
324     "ir-bb\<exit.2\>:\l" +
325     "No successors\l"
326   ]
327   N8 [label =
328     "scalar.ph:\l" +
329     "Successor(s): ir-bb\<loop.header\>\l"
330   ]
331   N8 -> N9 [ label=""]
332   N9 [label =
333     "ir-bb\<loop.header\>:\l" +
334     "  IR   %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ]\l" +
335     "  IR   %arr.idx = getelementptr inbounds i32, ptr %A, i64 %iv\l" +
336     "  IR   %l1 = load i32, ptr %arr.idx, align 4\l" +
337     "  IR   %c = icmp eq i32 %l1, 0\l" +
338     "No successors\l"
339   ]
340 }
341 )";
342   EXPECT_EQ(ExpectedStr, FullDump);
343 #endif
344 }
345 
346 } // namespace
347 } // namespace llvm
348