215 lines · cpp
1//===- llvm/unittests/Transforms/Vectorize/VPDomTreeTests.cpp - -----------===//2//3//4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.5// See https://llvm.org/LICENSE.txt for license information.6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception7//8//===----------------------------------------------------------------------===//9 10#include "../lib/Transforms/Vectorize/VPlan.h"11#include "../lib/Transforms/Vectorize/VPlanDominatorTree.h"12#include "VPlanTestBase.h"13#include "gtest/gtest.h"14 15namespace llvm {16namespace {17 18using VPDominatorTreeTest = VPlanTestBase;19 20TEST_F(VPDominatorTreeTest, DominanceNoRegionsTest) {21 // VPBB022 // |23 // R1 {24 // VPBB125 // / \26 // VPBB2 VPBB327 // \ /28 // VPBB429 // }30 VPlan &Plan = getPlan();31 VPBasicBlock *VPBB0 = Plan.getEntry();32 VPBasicBlock *VPBB1 = Plan.createVPBasicBlock("VPBB1");33 VPBasicBlock *VPBB2 = Plan.createVPBasicBlock("VPBB2");34 VPBasicBlock *VPBB3 = Plan.createVPBasicBlock("VPBB3");35 VPBasicBlock *VPBB4 = Plan.createVPBasicBlock("VPBB4");36 VPRegionBlock *R1 = Plan.createLoopRegion("R1", VPBB1, VPBB4);37 VPBB2->setParent(R1);38 VPBB3->setParent(R1);39 40 VPBlockUtils::connectBlocks(VPBB0, R1);41 VPBlockUtils::connectBlocks(VPBB1, VPBB2);42 VPBlockUtils::connectBlocks(VPBB1, VPBB3);43 VPBlockUtils::connectBlocks(VPBB2, VPBB4);44 VPBlockUtils::connectBlocks(VPBB3, VPBB4);45 46 VPBlockUtils::connectBlocks(R1, Plan.getScalarHeader());47 48 VPDominatorTree VPDT(Plan);49 50 EXPECT_TRUE(VPDT.dominates(VPBB1, VPBB4));51 EXPECT_FALSE(VPDT.dominates(VPBB4, VPBB1));52 53 EXPECT_TRUE(VPDT.dominates(VPBB1, VPBB2));54 EXPECT_FALSE(VPDT.dominates(VPBB2, VPBB1));55 56 EXPECT_TRUE(VPDT.dominates(VPBB1, VPBB3));57 EXPECT_FALSE(VPDT.dominates(VPBB3, VPBB1));58 59 EXPECT_EQ(VPDT.findNearestCommonDominator(VPBB2, VPBB3), VPBB1);60 EXPECT_EQ(VPDT.findNearestCommonDominator(VPBB2, VPBB4), VPBB1);61 EXPECT_EQ(VPDT.findNearestCommonDominator(VPBB4, VPBB4), VPBB4);62}63 64static void65checkDomChildren(VPDominatorTree &VPDT, VPBlockBase *Src,66 std::initializer_list<VPBlockBase *> ExpectedChildren) {67 SmallVector<VPDomTreeNode *> Children(VPDT.getNode(Src)->children());68 SmallVector<VPDomTreeNode *> ExpectedNodes;69 for (VPBlockBase *C : ExpectedChildren)70 ExpectedNodes.push_back(VPDT.getNode(C));71 72 EXPECT_EQ(Children, ExpectedNodes);73}74 75TEST_F(VPDominatorTreeTest, DominanceRegionsTest) {76 {77 // 2 consecutive regions.78 // VPBB079 // |80 // R1 {81 // \82 // R1BB1 _83 // / \ / \84 // R1BB2 R1BB3 |85 // \ / \_/86 // R1BB487 // }88 // |89 // R2 {90 // \91 // R2BB192 // |93 // R2BB294 // }95 //96 VPlan &Plan = getPlan();97 VPBasicBlock *VPBB0 = Plan.getEntry();98 VPBasicBlock *R1BB1 = Plan.createVPBasicBlock("");99 VPBasicBlock *R1BB2 = Plan.createVPBasicBlock("");100 VPBasicBlock *R1BB3 = Plan.createVPBasicBlock("");101 VPBasicBlock *R1BB4 = Plan.createVPBasicBlock("");102 VPRegionBlock *R1 = Plan.createLoopRegion("R1", R1BB1, R1BB4);103 R1BB2->setParent(R1);104 R1BB3->setParent(R1);105 VPBlockUtils::connectBlocks(VPBB0, R1);106 VPBlockUtils::connectBlocks(R1BB1, R1BB2);107 VPBlockUtils::connectBlocks(R1BB1, R1BB3);108 VPBlockUtils::connectBlocks(R1BB2, R1BB4);109 VPBlockUtils::connectBlocks(R1BB3, R1BB4);110 // Cycle.111 VPBlockUtils::connectBlocks(R1BB3, R1BB3);112 113 VPBasicBlock *R2BB1 = Plan.createVPBasicBlock("");114 VPBasicBlock *R2BB2 = Plan.createVPBasicBlock("");115 VPRegionBlock *R2 = Plan.createLoopRegion("R2", R2BB1, R2BB2);116 VPBlockUtils::connectBlocks(R2BB1, R2BB2);117 VPBlockUtils::connectBlocks(R1, R2);118 119 VPBlockUtils::connectBlocks(R2, Plan.getScalarHeader());120 VPDominatorTree VPDT(Plan);121 122 checkDomChildren(VPDT, R1, {R1BB1});123 checkDomChildren(VPDT, R1BB1, {R1BB2, R1BB4, R1BB3});124 checkDomChildren(VPDT, R1BB2, {});125 checkDomChildren(VPDT, R1BB3, {});126 checkDomChildren(VPDT, R1BB4, {R2});127 checkDomChildren(VPDT, R2, {R2BB1});128 checkDomChildren(VPDT, R2BB1, {R2BB2});129 130 EXPECT_TRUE(VPDT.dominates(R1, R2));131 EXPECT_FALSE(VPDT.dominates(R2, R1));132 133 EXPECT_TRUE(VPDT.dominates(R1BB1, R1BB4));134 EXPECT_FALSE(VPDT.dominates(R1BB4, R1BB1));135 136 EXPECT_TRUE(VPDT.dominates(R2BB1, R2BB2));137 EXPECT_FALSE(VPDT.dominates(R2BB2, R2BB1));138 139 EXPECT_TRUE(VPDT.dominates(R1BB1, R2BB1));140 EXPECT_FALSE(VPDT.dominates(R2BB1, R1BB1));141 142 EXPECT_TRUE(VPDT.dominates(R1BB4, R2BB1));143 EXPECT_FALSE(VPDT.dominates(R1BB3, R2BB1));144 145 EXPECT_TRUE(VPDT.dominates(R1, R2BB1));146 EXPECT_FALSE(VPDT.dominates(R2BB1, R1));147 }148 149 {150 // 2 nested regions.151 // VPBB1152 // |153 // R1 {154 // R1BB1155 // / \156 // R2 { |157 // \ |158 // R2BB1 |159 // | \ R1BB2160 // R2BB2-/ |161 // \ |162 // R2BB3 |163 // } /164 // \ /165 // R1BB3166 // }167 // |168 // VPBB2169 //170 VPlan &Plan = getPlan();171 VPBasicBlock *R1BB1 = Plan.createVPBasicBlock("R1BB1");172 VPBasicBlock *R1BB2 = Plan.createVPBasicBlock("R1BB2");173 VPBasicBlock *R1BB3 = Plan.createVPBasicBlock("R1BB3");174 VPRegionBlock *R1 = Plan.createLoopRegion("R1", R1BB1, R1BB3);175 176 VPBasicBlock *R2BB1 = Plan.createVPBasicBlock("R2BB1");177 VPBasicBlock *R2BB2 = Plan.createVPBasicBlock("R2BB2");178 VPBasicBlock *R2BB3 = Plan.createVPBasicBlock("R2BB#");179 VPRegionBlock *R2 = Plan.createLoopRegion("R2", R2BB1, R2BB3);180 R2BB2->setParent(R2);181 VPBlockUtils::connectBlocks(R2BB1, R2BB2);182 VPBlockUtils::connectBlocks(R2BB2, R2BB1);183 VPBlockUtils::connectBlocks(R2BB2, R2BB3);184 185 R2->setParent(R1);186 VPBlockUtils::connectBlocks(R1BB1, R2);187 R1BB2->setParent(R1);188 VPBlockUtils::connectBlocks(R1BB1, R1BB2);189 VPBlockUtils::connectBlocks(R1BB2, R1BB3);190 VPBlockUtils::connectBlocks(R2, R1BB3);191 192 VPBasicBlock *VPBB1 = Plan.getEntry();193 VPBlockUtils::connectBlocks(VPBB1, R1);194 VPBasicBlock *VPBB2 = Plan.createVPBasicBlock("VPBB2");195 VPBlockUtils::connectBlocks(R1, VPBB2);196 197 VPBlockUtils::connectBlocks(VPBB2, Plan.getScalarHeader());198 VPDominatorTree VPDT(Plan);199 200 checkDomChildren(VPDT, VPBB1, {R1});201 checkDomChildren(VPDT, R1, {R1BB1});202 checkDomChildren(VPDT, R1BB1, {R2, R1BB3, R1BB2});203 checkDomChildren(VPDT, R1BB2, {});204 checkDomChildren(VPDT, R2, {R2BB1});205 checkDomChildren(VPDT, R2BB1, {R2BB2});206 checkDomChildren(VPDT, R2BB2, {R2BB3});207 checkDomChildren(VPDT, R2BB3, {});208 checkDomChildren(VPDT, R1BB3, {VPBB2});209 checkDomChildren(VPDT, VPBB2, {Plan.getScalarHeader()});210 }211}212 213} // namespace214} // namespace llvm215