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 "gtest/gtest.h"
13 #include <string>
14 
15 namespace llvm {
16 namespace {
17 
18 class VPlanHCFGTest : public VPlanTestBase {};
19 
TEST_F(VPlanHCFGTest,testBuildHCFGInnerLoop)20 TEST_F(VPlanHCFGTest, testBuildHCFGInnerLoop) {
21   const char *ModuleString =
22       "define void @f(i32* %A, i64 %N) {\n"
23       "entry:\n"
24       "  br label %for.body\n"
25       "for.body:\n"
26       "  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]\n"
27       "  %arr.idx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv\n"
28       "  %l1 = load i32, i32* %arr.idx, align 4\n"
29       "  %res = add i32 %l1, 10\n"
30       "  store i32 %res, i32* %arr.idx, align 4\n"
31       "  %indvars.iv.next = add i64 %indvars.iv, 1\n"
32       "  %exitcond = icmp ne i64 %indvars.iv.next, %N\n"
33       "  br i1 %exitcond, label %for.body, label %for.end\n"
34       "for.end:\n"
35       "  ret void\n"
36       "}\n";
37 
38   Module &M = parseModule(ModuleString);
39 
40   Function *F = M.getFunction("f");
41   BasicBlock *LoopHeader = F->getEntryBlock().getSingleSuccessor();
42   auto Plan = buildHCFG(LoopHeader);
43 
44   VPBasicBlock *Entry = Plan->getEntry()->getEntryBasicBlock();
45   EXPECT_NE(nullptr, Entry->getSingleSuccessor());
46   EXPECT_EQ(0u, Entry->getNumPredecessors());
47   EXPECT_EQ(1u, Entry->getNumSuccessors());
48   EXPECT_EQ(nullptr, Entry->getCondBit());
49 
50   VPBasicBlock *VecBB = Entry->getSingleSuccessor()->getEntryBasicBlock();
51   EXPECT_EQ(7u, VecBB->size());
52   EXPECT_EQ(2u, VecBB->getNumPredecessors());
53   EXPECT_EQ(2u, VecBB->getNumSuccessors());
54   EXPECT_EQ(&*Plan, VecBB->getPlan());
55 
56   auto Iter = VecBB->begin();
57   VPWidenPHIRecipe *Phi = dyn_cast<VPWidenPHIRecipe>(&*Iter++);
58   EXPECT_NE(nullptr, Phi);
59 
60   VPInstruction *Idx = dyn_cast<VPInstruction>(&*Iter++);
61   EXPECT_EQ(Instruction::GetElementPtr, Idx->getOpcode());
62   EXPECT_EQ(2u, Idx->getNumOperands());
63   EXPECT_EQ(Phi, Idx->getOperand(1));
64 
65   VPInstruction *Load = dyn_cast<VPInstruction>(&*Iter++);
66   EXPECT_EQ(Instruction::Load, Load->getOpcode());
67   EXPECT_EQ(1u, Load->getNumOperands());
68   EXPECT_EQ(Idx, Load->getOperand(0));
69 
70   VPInstruction *Add = dyn_cast<VPInstruction>(&*Iter++);
71   EXPECT_EQ(Instruction::Add, Add->getOpcode());
72   EXPECT_EQ(2u, Add->getNumOperands());
73   EXPECT_EQ(Load, Add->getOperand(0));
74 
75   VPInstruction *Store = dyn_cast<VPInstruction>(&*Iter++);
76   EXPECT_EQ(Instruction::Store, Store->getOpcode());
77   EXPECT_EQ(2u, Store->getNumOperands());
78   EXPECT_EQ(Add, Store->getOperand(0));
79   EXPECT_EQ(Idx, Store->getOperand(1));
80 
81   VPInstruction *IndvarAdd = dyn_cast<VPInstruction>(&*Iter++);
82   EXPECT_EQ(Instruction::Add, IndvarAdd->getOpcode());
83   EXPECT_EQ(2u, IndvarAdd->getNumOperands());
84   EXPECT_EQ(Phi, IndvarAdd->getOperand(0));
85 
86   VPInstruction *ICmp = dyn_cast<VPInstruction>(&*Iter++);
87   EXPECT_EQ(Instruction::ICmp, ICmp->getOpcode());
88   EXPECT_EQ(2u, ICmp->getNumOperands());
89   EXPECT_EQ(IndvarAdd, ICmp->getOperand(0));
90   EXPECT_EQ(VecBB->getCondBit(), ICmp);
91 
92 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
93   // Add an external value to check we do not print the list of external values,
94   // as this is not required with the new printing.
95   Plan->addVPValue(&*F->arg_begin());
96   std::string FullDump;
97   raw_string_ostream OS(FullDump);
98   Plan->printDOT(OS);
99   const char *ExpectedStr = R"(digraph VPlan {
100 graph [labelloc=t, fontsize=30; label="Vectorization Plan"]
101 node [shape=rect, fontname=Courier, fontsize=30]
102 edge [fontname=Courier, fontsize=30]
103 compound=true
104   subgraph cluster_N0 {
105     fontname=Courier
106     label="\<x1\> TopRegion"
107     N1 [label =
108       "entry:\l" +
109       "Successor(s): for.body\l"
110     ]
111     N1 -> N2 [ label=""]
112     N2 [label =
113       "for.body:\l" +
114       "  WIDEN-PHI ir\<%indvars.iv\> = phi ir\<0\>, ir\<%indvars.iv.next\>\l" +
115       "  EMIT ir\<%arr.idx\> = getelementptr ir\<%A\> ir\<%indvars.iv\>\l" +
116       "  EMIT ir\<%l1\> = load ir\<%arr.idx\>\l" +
117       "  EMIT ir\<%res\> = add ir\<%l1\> ir\<10\>\l" +
118       "  EMIT store ir\<%res\> ir\<%arr.idx\>\l" +
119       "  EMIT ir\<%indvars.iv.next\> = add ir\<%indvars.iv\> ir\<1\>\l" +
120       "  EMIT ir\<%exitcond\> = icmp ir\<%indvars.iv.next\> ir\<%N\>\l" +
121       "Successor(s): for.body, for.end\l" +
122       "CondBit: ir\<%exitcond\> (for.body)\l"
123     ]
124     N2 -> N2 [ label="T"]
125     N2 -> N3 [ label="F"]
126     N3 [label =
127       "for.end:\l" +
128       "  EMIT ret\l" +
129       "No successors\l"
130     ]
131   }
132 }
133 )";
134   EXPECT_EQ(ExpectedStr, FullDump);
135 #endif
136 
137   LoopVectorizationLegality::InductionList Inductions;
138   SmallPtrSet<Instruction *, 1> DeadInstructions;
139   VPlanTransforms::VPInstructionsToVPRecipes(LI->getLoopFor(LoopHeader), Plan,
140                                              Inductions, DeadInstructions, *SE);
141 }
142 
TEST_F(VPlanHCFGTest,testVPInstructionToVPRecipesInner)143 TEST_F(VPlanHCFGTest, testVPInstructionToVPRecipesInner) {
144   const char *ModuleString =
145       "define void @f(i32* %A, i64 %N) {\n"
146       "entry:\n"
147       "  br label %for.body\n"
148       "for.body:\n"
149       "  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]\n"
150       "  %arr.idx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv\n"
151       "  %l1 = load i32, i32* %arr.idx, align 4\n"
152       "  %res = add i32 %l1, 10\n"
153       "  store i32 %res, i32* %arr.idx, align 4\n"
154       "  %indvars.iv.next = add i64 %indvars.iv, 1\n"
155       "  %exitcond = icmp ne i64 %indvars.iv.next, %N\n"
156       "  br i1 %exitcond, label %for.body, label %for.end\n"
157       "for.end:\n"
158       "  ret void\n"
159       "}\n";
160 
161   Module &M = parseModule(ModuleString);
162 
163   Function *F = M.getFunction("f");
164   BasicBlock *LoopHeader = F->getEntryBlock().getSingleSuccessor();
165   auto Plan = buildHCFG(LoopHeader);
166 
167   LoopVectorizationLegality::InductionList Inductions;
168   SmallPtrSet<Instruction *, 1> DeadInstructions;
169   VPlanTransforms::VPInstructionsToVPRecipes(LI->getLoopFor(LoopHeader), Plan,
170                                              Inductions, DeadInstructions, *SE);
171 
172   VPBlockBase *Entry = Plan->getEntry()->getEntryBasicBlock();
173   EXPECT_NE(nullptr, Entry->getSingleSuccessor());
174   EXPECT_EQ(0u, Entry->getNumPredecessors());
175   EXPECT_EQ(1u, Entry->getNumSuccessors());
176 
177   VPBasicBlock *VecBB = Entry->getSingleSuccessor()->getEntryBasicBlock();
178   EXPECT_EQ(7u, VecBB->size());
179   EXPECT_EQ(2u, VecBB->getNumPredecessors());
180   EXPECT_EQ(2u, VecBB->getNumSuccessors());
181 
182   auto Iter = VecBB->begin();
183   EXPECT_NE(nullptr, dyn_cast<VPWidenPHIRecipe>(&*Iter++));
184   EXPECT_NE(nullptr, dyn_cast<VPWidenGEPRecipe>(&*Iter++));
185   EXPECT_NE(nullptr, dyn_cast<VPWidenMemoryInstructionRecipe>(&*Iter++));
186   EXPECT_NE(nullptr, dyn_cast<VPWidenRecipe>(&*Iter++));
187   EXPECT_NE(nullptr, dyn_cast<VPWidenMemoryInstructionRecipe>(&*Iter++));
188   EXPECT_NE(nullptr, dyn_cast<VPWidenRecipe>(&*Iter++));
189   EXPECT_NE(nullptr, dyn_cast<VPWidenRecipe>(&*Iter++));
190   EXPECT_EQ(VecBB->end(), Iter);
191 }
192 
193 } // namespace
194 } // namespace llvm
195