1 //===- llvm/unittests/Transforms/Vectorize/VPlanDominatorTreeTest.cpp -----===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 #include "../lib/Transforms/Vectorize/VPlanHCFGBuilder.h" 11 #include "VPlanTestBase.h" 12 #include "gtest/gtest.h" 13 14 namespace llvm { 15 namespace { 16 17 class VPlanDominatorTreeTest : public VPlanTestBase {}; 18 19 TEST_F(VPlanDominatorTreeTest, BasicVPBBDomination) { 20 const char *ModuleString = 21 "define void @f(i32* %a, i32* %b, i32* %c, i32 %N, i32 %M, i32 %K) {\n" 22 "entry:\n" 23 " br label %for.body\n" 24 "for.body:\n" 25 " %iv = phi i64 [ 0, %entry ], [ %iv.next, %for.inc ]\n" 26 " br i1 true, label %if.then, label %if.else\n" 27 "if.then:\n" 28 " br label %for.inc\n" 29 "if.else:\n" 30 " br label %for.inc\n" 31 "for.inc:\n" 32 " %iv.next = add nuw nsw i64 %iv, 1\n" 33 " %exitcond = icmp eq i64 %iv.next, 300\n" 34 " br i1 %exitcond, label %for.end, label %for.body\n" 35 "for.end:\n" 36 " ret void\n" 37 "}\n"; 38 39 Module &M = parseModule(ModuleString); 40 41 Function *F = M.getFunction("f"); 42 BasicBlock *LoopHeader = F->getEntryBlock().getSingleSuccessor(); 43 auto Plan = buildPlainCFG(LoopHeader); 44 45 // Build VPlan domination tree analysis. 46 VPRegionBlock *TopRegion = cast<VPRegionBlock>(Plan->getEntry()); 47 VPDominatorTree VPDT; 48 VPDT.recalculate(*TopRegion); 49 50 VPBlockBase *PH = TopRegion->getEntry(); 51 VPBlockBase *H = PH->getSingleSuccessor(); 52 VPBlockBase *IfThen = H->getSuccessors()[0]; 53 VPBlockBase *IfElse = H->getSuccessors()[1]; 54 VPBlockBase *Latch = IfThen->getSingleSuccessor(); 55 VPBlockBase *Exit = Latch->getSuccessors()[0] != H 56 ? Latch->getSuccessors()[0] 57 : Latch->getSuccessors()[1]; 58 // Reachability. 59 EXPECT_TRUE(VPDT.isReachableFromEntry(PH)); 60 EXPECT_TRUE(VPDT.isReachableFromEntry(H)); 61 EXPECT_TRUE(VPDT.isReachableFromEntry(IfThen)); 62 EXPECT_TRUE(VPDT.isReachableFromEntry(IfElse)); 63 EXPECT_TRUE(VPDT.isReachableFromEntry(Latch)); 64 EXPECT_TRUE(VPDT.isReachableFromEntry(Exit)); 65 66 // VPBB dominance. 67 EXPECT_TRUE(VPDT.dominates(PH, PH)); 68 EXPECT_TRUE(VPDT.dominates(PH, H)); 69 EXPECT_TRUE(VPDT.dominates(PH, IfThen)); 70 EXPECT_TRUE(VPDT.dominates(PH, IfElse)); 71 EXPECT_TRUE(VPDT.dominates(PH, Latch)); 72 EXPECT_TRUE(VPDT.dominates(PH, Exit)); 73 74 EXPECT_FALSE(VPDT.dominates(H, PH)); 75 EXPECT_TRUE(VPDT.dominates(H, H)); 76 EXPECT_TRUE(VPDT.dominates(H, IfThen)); 77 EXPECT_TRUE(VPDT.dominates(H, IfElse)); 78 EXPECT_TRUE(VPDT.dominates(H, Latch)); 79 EXPECT_TRUE(VPDT.dominates(H, Exit)); 80 81 EXPECT_FALSE(VPDT.dominates(IfThen, PH)); 82 EXPECT_FALSE(VPDT.dominates(IfThen, H)); 83 EXPECT_TRUE(VPDT.dominates(IfThen, IfThen)); 84 EXPECT_FALSE(VPDT.dominates(IfThen, IfElse)); 85 EXPECT_FALSE(VPDT.dominates(IfThen, Latch)); 86 EXPECT_FALSE(VPDT.dominates(IfThen, Exit)); 87 88 EXPECT_FALSE(VPDT.dominates(IfElse, PH)); 89 EXPECT_FALSE(VPDT.dominates(IfElse, H)); 90 EXPECT_FALSE(VPDT.dominates(IfElse, IfThen)); 91 EXPECT_TRUE(VPDT.dominates(IfElse, IfElse)); 92 EXPECT_FALSE(VPDT.dominates(IfElse, Latch)); 93 EXPECT_FALSE(VPDT.dominates(IfElse, Exit)); 94 95 EXPECT_FALSE(VPDT.dominates(Latch, PH)); 96 EXPECT_FALSE(VPDT.dominates(Latch, H)); 97 EXPECT_FALSE(VPDT.dominates(Latch, IfThen)); 98 EXPECT_FALSE(VPDT.dominates(Latch, IfElse)); 99 EXPECT_TRUE(VPDT.dominates(Latch, Latch)); 100 EXPECT_TRUE(VPDT.dominates(Latch, Exit)); 101 102 EXPECT_FALSE(VPDT.dominates(Exit, PH)); 103 EXPECT_FALSE(VPDT.dominates(Exit, H)); 104 EXPECT_FALSE(VPDT.dominates(Exit, IfThen)); 105 EXPECT_FALSE(VPDT.dominates(Exit, IfElse)); 106 EXPECT_FALSE(VPDT.dominates(Exit, Latch)); 107 EXPECT_TRUE(VPDT.dominates(Exit, Exit)); 108 109 // VPBB proper dominance. 110 EXPECT_FALSE(VPDT.properlyDominates(PH, PH)); 111 EXPECT_TRUE(VPDT.properlyDominates(PH, H)); 112 EXPECT_TRUE(VPDT.properlyDominates(PH, IfThen)); 113 EXPECT_TRUE(VPDT.properlyDominates(PH, IfElse)); 114 EXPECT_TRUE(VPDT.properlyDominates(PH, Latch)); 115 EXPECT_TRUE(VPDT.properlyDominates(PH, Exit)); 116 117 EXPECT_FALSE(VPDT.properlyDominates(H, PH)); 118 EXPECT_FALSE(VPDT.properlyDominates(H, H)); 119 EXPECT_TRUE(VPDT.properlyDominates(H, IfThen)); 120 EXPECT_TRUE(VPDT.properlyDominates(H, IfElse)); 121 EXPECT_TRUE(VPDT.properlyDominates(H, Latch)); 122 EXPECT_TRUE(VPDT.properlyDominates(H, Exit)); 123 124 EXPECT_FALSE(VPDT.properlyDominates(IfThen, PH)); 125 EXPECT_FALSE(VPDT.properlyDominates(IfThen, H)); 126 EXPECT_FALSE(VPDT.properlyDominates(IfThen, IfThen)); 127 EXPECT_FALSE(VPDT.properlyDominates(IfThen, IfElse)); 128 EXPECT_FALSE(VPDT.properlyDominates(IfThen, Latch)); 129 EXPECT_FALSE(VPDT.properlyDominates(IfThen, Exit)); 130 131 EXPECT_FALSE(VPDT.properlyDominates(IfElse, PH)); 132 EXPECT_FALSE(VPDT.properlyDominates(IfElse, H)); 133 EXPECT_FALSE(VPDT.properlyDominates(IfElse, IfThen)); 134 EXPECT_FALSE(VPDT.properlyDominates(IfElse, IfElse)); 135 EXPECT_FALSE(VPDT.properlyDominates(IfElse, Latch)); 136 EXPECT_FALSE(VPDT.properlyDominates(IfElse, Exit)); 137 138 EXPECT_FALSE(VPDT.properlyDominates(Latch, PH)); 139 EXPECT_FALSE(VPDT.properlyDominates(Latch, H)); 140 EXPECT_FALSE(VPDT.properlyDominates(Latch, IfThen)); 141 EXPECT_FALSE(VPDT.properlyDominates(Latch, IfElse)); 142 EXPECT_FALSE(VPDT.properlyDominates(Latch, Latch)); 143 EXPECT_TRUE(VPDT.properlyDominates(Latch, Exit)); 144 145 EXPECT_FALSE(VPDT.properlyDominates(Exit, PH)); 146 EXPECT_FALSE(VPDT.properlyDominates(Exit, H)); 147 EXPECT_FALSE(VPDT.properlyDominates(Exit, IfThen)); 148 EXPECT_FALSE(VPDT.properlyDominates(Exit, IfElse)); 149 EXPECT_FALSE(VPDT.properlyDominates(Exit, Latch)); 150 EXPECT_FALSE(VPDT.properlyDominates(Exit, Exit)); 151 152 // VPBB nearest common dominator. 153 EXPECT_EQ(PH, VPDT.findNearestCommonDominator(PH, PH)); 154 EXPECT_EQ(PH, VPDT.findNearestCommonDominator(PH, H)); 155 EXPECT_EQ(PH, VPDT.findNearestCommonDominator(PH, IfThen)); 156 EXPECT_EQ(PH, VPDT.findNearestCommonDominator(PH, IfElse)); 157 EXPECT_EQ(PH, VPDT.findNearestCommonDominator(PH, Latch)); 158 EXPECT_EQ(PH, VPDT.findNearestCommonDominator(PH, Exit)); 159 160 EXPECT_EQ(PH, VPDT.findNearestCommonDominator(H, PH)); 161 EXPECT_EQ(H, VPDT.findNearestCommonDominator(H, H)); 162 EXPECT_EQ(H, VPDT.findNearestCommonDominator(H, IfThen)); 163 EXPECT_EQ(H, VPDT.findNearestCommonDominator(H, IfElse)); 164 EXPECT_EQ(H, VPDT.findNearestCommonDominator(H, Latch)); 165 EXPECT_EQ(H, VPDT.findNearestCommonDominator(H, Exit)); 166 167 EXPECT_EQ(PH, VPDT.findNearestCommonDominator(IfThen, PH)); 168 EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfThen, H)); 169 EXPECT_EQ(IfThen, VPDT.findNearestCommonDominator(IfThen, IfThen)); 170 EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfThen, IfElse)); 171 EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfThen, Latch)); 172 EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfThen, Exit)); 173 174 EXPECT_EQ(PH, VPDT.findNearestCommonDominator(IfElse, PH)); 175 EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfElse, H)); 176 EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfElse, IfThen)); 177 EXPECT_EQ(IfElse, VPDT.findNearestCommonDominator(IfElse, IfElse)); 178 EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfElse, Latch)); 179 EXPECT_EQ(H, VPDT.findNearestCommonDominator(IfElse, Exit)); 180 181 EXPECT_EQ(PH, VPDT.findNearestCommonDominator(Latch, PH)); 182 EXPECT_EQ(H, VPDT.findNearestCommonDominator(Latch, H)); 183 EXPECT_EQ(H, VPDT.findNearestCommonDominator(Latch, IfThen)); 184 EXPECT_EQ(H, VPDT.findNearestCommonDominator(Latch, IfElse)); 185 EXPECT_EQ(Latch, VPDT.findNearestCommonDominator(Latch, Latch)); 186 EXPECT_EQ(Latch, VPDT.findNearestCommonDominator(Latch, Exit)); 187 188 EXPECT_EQ(PH, VPDT.findNearestCommonDominator(Exit, PH)); 189 EXPECT_EQ(H, VPDT.findNearestCommonDominator(Exit, H)); 190 EXPECT_EQ(H, VPDT.findNearestCommonDominator(Exit, IfThen)); 191 EXPECT_EQ(H, VPDT.findNearestCommonDominator(Exit, IfElse)); 192 EXPECT_EQ(Latch, VPDT.findNearestCommonDominator(Exit, Latch)); 193 EXPECT_EQ(Exit, VPDT.findNearestCommonDominator(Exit, Exit)); 194 } 195 } // namespace 196 } // namespace llvm 197
