349 lines · cpp
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-exception6//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 17namespace llvm {18namespace {19 20class VPlanHCFGTest : public VPlanTestIRBase {};21 22TEST_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 = buildVPlan(LoopHeader);45 46 VPBasicBlock *Entry = Plan->getEntry()->getEntryBasicBlock();47 EXPECT_EQ(0u, Entry->getNumPredecessors());48 EXPECT_EQ(2u, Entry->getNumSuccessors());49 50 // Check that the region following the preheader consists of a block for the51 // original header and a separate latch.52 VPBasicBlock *VecBB = Plan->getVectorLoopRegion()->getEntryBasicBlock();53 EXPECT_EQ(11u, VecBB->size());54 EXPECT_EQ(0u, VecBB->getNumPredecessors());55 EXPECT_EQ(0u, VecBB->getNumSuccessors());56 EXPECT_EQ(VecBB->getParent()->getEntryBasicBlock(), VecBB);57 EXPECT_EQ(&*Plan, VecBB->getPlan());58 59 auto Iter = VecBB->begin();60 auto *CanIV = dyn_cast<VPCanonicalIVPHIRecipe>(&*Iter++);61 EXPECT_NE(nullptr, CanIV);62 auto *Phi = dyn_cast<VPPhi>(&*Iter++);63 EXPECT_NE(nullptr, Phi);64 65 VPInstruction *Idx = dyn_cast<VPInstruction>(&*Iter++);66 EXPECT_EQ(Instruction::GetElementPtr, Idx->getOpcode());67 EXPECT_EQ(2u, Idx->getNumOperands());68 EXPECT_EQ(Phi, Idx->getOperand(1));69 70 VPInstruction *Load = dyn_cast<VPInstruction>(&*Iter++);71 EXPECT_EQ(Instruction::Load, Load->getOpcode());72 EXPECT_EQ(1u, Load->getNumOperands());73 EXPECT_EQ(Idx, Load->getOperand(0));74 75 VPInstruction *Add = dyn_cast<VPInstruction>(&*Iter++);76 EXPECT_EQ(Instruction::Add, Add->getOpcode());77 EXPECT_EQ(2u, Add->getNumOperands());78 EXPECT_EQ(Load, Add->getOperand(0));79 80 VPInstruction *Store = dyn_cast<VPInstruction>(&*Iter++);81 EXPECT_EQ(Instruction::Store, Store->getOpcode());82 EXPECT_EQ(2u, Store->getNumOperands());83 EXPECT_EQ(Add, Store->getOperand(0));84 EXPECT_EQ(Idx, Store->getOperand(1));85 86 VPInstruction *IndvarAdd = dyn_cast<VPInstruction>(&*Iter++);87 EXPECT_EQ(Instruction::Add, IndvarAdd->getOpcode());88 EXPECT_EQ(2u, IndvarAdd->getNumOperands());89 EXPECT_EQ(Phi, IndvarAdd->getOperand(0));90 91 VPInstruction *ICmp = dyn_cast<VPInstruction>(&*Iter++);92 EXPECT_EQ(Instruction::ICmp, ICmp->getOpcode());93 EXPECT_EQ(2u, ICmp->getNumOperands());94 EXPECT_EQ(IndvarAdd, ICmp->getOperand(0));95 96#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)97 // Add an external value to check we do not print the list of external values,98 // as this is not required with the new printing.99 Plan->getOrAddLiveIn(&*F->arg_begin());100 std::string FullDump;101 raw_string_ostream OS(FullDump);102 Plan->printDOT(OS);103 const char *ExpectedStr = R"(digraph VPlan {104graph [labelloc=t, fontsize=30; label="Vectorization Plan\n for UF\>=1\nLive-in vp\<%0\> = VF * UF\nLive-in vp\<%1\> = vector-trip-count\nLive-in ir\<%N\> = original trip-count\n"]105node [shape=rect, fontname=Courier, fontsize=30]106edge [fontname=Courier, fontsize=30]107compound=true108 N0 [label =109 "ir-bb\<entry\>:\l" +110 "Successor(s): scalar.ph, vector.ph\l"111 ]112 N0 -> N1 [ label="T"]113 N0 -> N2 [ label="F"]114 N1 [label =115 "scalar.ph:\l" +116 " EMIT-SCALAR vp\<%6\> = phi [ ir\<%indvars.iv\>, middle.block ], [ ir\<0\>, ir-bb\<entry\> ]\l" +117 "Successor(s): ir-bb\<for.body\>\l"118 ]119 N1 -> N3 [ label=""]120 N3 [label =121 "ir-bb\<for.body\>:\l" +122 " IR %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ] (extra operand: vp\<%6\> from scalar.ph)\l" +123 " IR %arr.idx = getelementptr inbounds i32, ptr %A, i64 %indvars.iv\l" +124 " IR %l1 = load i32, ptr %arr.idx, align 4\l" +125 " IR %res = add i32 %l1, 10\l" +126 " IR store i32 %res, ptr %arr.idx, align 4\l" +127 " IR %indvars.iv.next = add i64 %indvars.iv, 1\l" +128 " IR %exitcond = icmp ne i64 %indvars.iv.next, %N\l" +129 "No successors\l"130 ]131 N2 [label =132 "vector.ph:\l" +133 "Successor(s): vector loop\l"134 ]135 N2 -> N4 [ label="" lhead=cluster_N5]136 subgraph cluster_N5 {137 fontname=Courier138 label="\<x1\> vector loop"139 N4 [label =140 "vector.body:\l" +141 " EMIT vp\<%2\> = CANONICAL-INDUCTION ir\<0\>, vp\<%index.next\>\l" +142 " EMIT-SCALAR ir\<%indvars.iv\> = phi [ ir\<0\>, vector.ph ], [ ir\<%indvars.iv.next\>, vector.body ]\l" +143 " EMIT ir\<%arr.idx\> = getelementptr inbounds ir\<%A\>, ir\<%indvars.iv\>\l" +144 " EMIT ir\<%l1\> = load ir\<%arr.idx\>\l" +145 " EMIT ir\<%res\> = add ir\<%l1\>, ir\<10\>\l" +146 " EMIT store ir\<%res\>, ir\<%arr.idx\>\l" +147 " EMIT ir\<%indvars.iv.next\> = add ir\<%indvars.iv\>, ir\<1\>\l" +148 " EMIT ir\<%exitcond\> = icmp ne ir\<%indvars.iv.next\>, ir\<%N\>\l" +149 " EMIT vp\<%3\> = not ir\<%exitcond\>\l" +150 " EMIT vp\<%index.next\> = add nuw vp\<%2\>, vp\<%0\>\l" +151 " EMIT branch-on-count vp\<%index.next\>, vp\<%1\>\l" +152 "No successors\l"153 ]154 }155 N4 -> N6 [ label="" ltail=cluster_N5]156 N6 [label =157 "middle.block:\l" +158 " EMIT vp\<%cmp.n\> = icmp eq ir\<%N\>, vp\<%1\>\l" +159 " EMIT branch-on-cond vp\<%cmp.n\>\l" +160 "Successor(s): ir-bb\<for.end\>, scalar.ph\l"161 ]162 N6 -> N7 [ label="T"]163 N6 -> N1 [ label="F"]164 N7 [label =165 "ir-bb\<for.end\>:\l" +166 "No successors\l"167 ]168}169)";170 EXPECT_EQ(ExpectedStr, FullDump);171#endif172}173 174TEST_F(VPlanHCFGTest, testVPInstructionToVPRecipesInner) {175 const char *ModuleString =176 "define void @f(ptr %A, i64 %N) {\n"177 "entry:\n"178 " br label %for.body\n"179 "for.body:\n"180 " %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]\n"181 " %arr.idx = getelementptr inbounds i32, ptr %A, i64 %indvars.iv\n"182 " %l1 = load i32, ptr %arr.idx, align 4\n"183 " %res = add i32 %l1, 10\n"184 " store i32 %res, ptr %arr.idx, align 4\n"185 " %indvars.iv.next = add i64 %indvars.iv, 1\n"186 " %exitcond = icmp ne i64 %indvars.iv.next, %N\n"187 " br i1 %exitcond, label %for.body, label %for.end\n"188 "for.end:\n"189 " ret void\n"190 "}\n";191 192 Module &M = parseModule(ModuleString);193 194 Function *F = M.getFunction("f");195 BasicBlock *LoopHeader = F->getEntryBlock().getSingleSuccessor();196 auto Plan = buildVPlan(LoopHeader);197 198 TargetLibraryInfoImpl TLII(M.getTargetTriple());199 TargetLibraryInfo TLI(TLII);200 // Current VPlan construction doesn't add a terminator for top-level loop201 // latches. Add it before running transform.202 cast<VPBasicBlock>(Plan->getVectorLoopRegion()->getExiting())203 ->appendRecipe(new VPInstruction(204 VPInstruction::BranchOnCond,205 {Plan->getOrAddLiveIn(ConstantInt::getTrue(F->getContext()))}));206 VPlanTransforms::tryToConvertVPInstructionsToVPRecipes(207 *Plan, [](PHINode *P) { return nullptr; }, TLI);208 209 VPBlockBase *Entry = Plan->getEntry()->getEntryBasicBlock();210 EXPECT_EQ(0u, Entry->getNumPredecessors());211 EXPECT_EQ(2u, Entry->getNumSuccessors());212 213 // Check that the region following the preheader consists of a block for the214 // original header and a separate latch.215 VPBasicBlock *VecBB = Plan->getVectorLoopRegion()->getEntryBasicBlock();216 EXPECT_EQ(12u, VecBB->size());217 EXPECT_EQ(0u, VecBB->getNumPredecessors());218 EXPECT_EQ(0u, VecBB->getNumSuccessors());219 EXPECT_EQ(VecBB->getParent()->getEntryBasicBlock(), VecBB);220 221 auto Iter = VecBB->begin();222 EXPECT_NE(nullptr, dyn_cast<VPCanonicalIVPHIRecipe>(&*Iter++));223 EXPECT_NE(nullptr, dyn_cast<VPWidenPHIRecipe>(&*Iter++));224 EXPECT_NE(nullptr, dyn_cast<VPWidenGEPRecipe>(&*Iter++));225 EXPECT_NE(nullptr, dyn_cast<VPWidenMemoryRecipe>(&*Iter++));226 EXPECT_NE(nullptr, dyn_cast<VPWidenRecipe>(&*Iter++));227 EXPECT_NE(nullptr, dyn_cast<VPWidenMemoryRecipe>(&*Iter++));228 EXPECT_NE(nullptr, dyn_cast<VPWidenRecipe>(&*Iter++));229 EXPECT_NE(nullptr, dyn_cast<VPWidenRecipe>(&*Iter++));230 EXPECT_NE(nullptr, dyn_cast<VPInstruction>(&*Iter++));231 EXPECT_NE(nullptr, dyn_cast<VPInstruction>(&*Iter++));232 EXPECT_NE(nullptr, dyn_cast<VPInstruction>(&*Iter++));233 EXPECT_NE(nullptr, dyn_cast<VPInstruction>(&*Iter++));234 EXPECT_EQ(VecBB->end(), Iter);235}236 237TEST_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 = buildVPlan(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 {274graph [labelloc=t, fontsize=30; label="Vectorization Plan\n for UF\>=1\nLive-in vp\<%0\> = VF * UF\nLive-in vp\<%1\> = vector-trip-count\nLive-in ir\<%N\> = original trip-count\n"]275node [shape=rect, fontname=Courier, fontsize=30]276edge [fontname=Courier, fontsize=30]277compound=true278 N0 [label =279 "ir-bb\<entry\>:\l" +280 "Successor(s): scalar.ph, vector.ph\l"281 ]282 N0 -> N1 [ label="T"]283 N0 -> N2 [ label="F"]284 N1 [label =285 "scalar.ph:\l" +286 " EMIT-SCALAR vp\<%6\> = phi [ ir\<%iv\>, middle.block ], [ ir\<0\>, ir-bb\<entry\> ]\l" +287 "Successor(s): ir-bb\<loop.header\>\l"288 ]289 N1 -> N3 [ label=""]290 N3 [label =291 "ir-bb\<loop.header\>:\l" +292 " IR %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop.latch ] (extra operand: vp\<%6\> from scalar.ph)\l" +293 " IR %arr.idx = getelementptr inbounds i32, ptr %A, i64 %iv\l" +294 " IR %l1 = load i32, ptr %arr.idx, align 4\l" +295 " IR %c = icmp eq i32 %l1, 0\l" +296 "No successors\l"297 ]298 N2 [label =299 "vector.ph:\l" +300 "Successor(s): vector loop\l"301 ]302 N2 -> N4 [ label="" lhead=cluster_N5]303 subgraph cluster_N5 {304 fontname=Courier305 label="\<x1\> vector loop"306 N4 [label =307 "vector.body:\l" +308 " EMIT vp\<%2\> = CANONICAL-INDUCTION ir\<0\>, vp\<%index.next\>\l" +309 " EMIT-SCALAR ir\<%iv\> = phi [ ir\<0\>, vector.ph ], [ ir\<%iv.next\>, loop.latch ]\l" +310 " EMIT ir\<%arr.idx\> = getelementptr inbounds ir\<%A\>, ir\<%iv\>\l" +311 " EMIT ir\<%l1\> = load ir\<%arr.idx\>\l" +312 " EMIT ir\<%c\> = icmp eq ir\<%l1\>, ir\<0\>\l" +313 "Successor(s): loop.latch\l"314 ]315 N4 -> N6 [ label=""]316 N6 [label =317 "loop.latch:\l" +318 " EMIT ir\<%res\> = add ir\<%l1\>, ir\<10\>\l" +319 " EMIT store ir\<%res\>, ir\<%arr.idx\>\l" +320 " EMIT ir\<%iv.next\> = add ir\<%iv\>, ir\<1\>\l" +321 " EMIT ir\<%exitcond\> = icmp ne ir\<%iv.next\>, ir\<%N\>\l" +322 " EMIT vp\<%3\> = not ir\<%exitcond\>\l" +323 " EMIT vp\<%index.next\> = add nuw vp\<%2\>, vp\<%0\>\l" +324 " EMIT branch-on-count vp\<%index.next\>, vp\<%1\>\l" +325 "No successors\l"326 ]327 }328 N6 -> N7 [ label="" ltail=cluster_N5]329 N7 [label =330 "middle.block:\l" +331 " EMIT vp\<%cmp.n\> = icmp eq ir\<%N\>, vp\<%1\>\l" +332 " EMIT branch-on-cond vp\<%cmp.n\>\l" +333 "Successor(s): ir-bb\<exit.2\>, scalar.ph\l"334 ]335 N7 -> N8 [ label="T"]336 N7 -> N1 [ label="F"]337 N8 [label =338 "ir-bb\<exit.2\>:\l" +339 "No successors\l"340 ]341}342)";343 EXPECT_EQ(ExpectedStr, FullDump);344#endif345}346 347} // namespace348} // namespace llvm349