unittests/Transforms/Vectorize/VPlanPredicatorTest.cpp

   1 //===- llvm/unittests/Transforms/Vectorize/VPlanPredicatorTest.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/VPlanPredicator.h"
  10 #include "VPlanTestBase.h"
  11 #include "gtest/gtest.h"
  12
  13 namespace llvm {
  14 namespace {
  15
  16 class VPlanPredicatorTest : public VPlanTestBase {};
  17
  18 TEST_F(VPlanPredicatorTest, BasicPredicatorTest) {
  19   const char *ModuleString =
  20       "@arr = common global [8 x [8 x i64]] "
  21       "zeroinitializer, align 16\n"
  22       "@arr2 = common global [8 x [8 x i64]] "
  23       "zeroinitializer, align 16\n"
  24       "@arr3 = common global [8 x [8 x i64]] "
  25       "zeroinitializer, align 16\n"
  26       "define void @f(i64 %n1) {\n"
  27       "entry:\n"
  28       "  br label %for.cond1.preheader\n"
  29       "for.cond1.preheader:                              \n"
  30       "  %i1.029 = phi i64 [ 0, %entry ], [ %inc14, %for.inc13 ]\n"
  31       "  br label %for.body3\n"
  32       "for.body3:                                        \n"
  33       "  %i2.028 = phi i64 [ 0, %for.cond1.preheader ], [ %inc, %for.inc ]\n"
  34       "  %arrayidx4 = getelementptr inbounds [8 x [8 x i64]], [8 x [8 x i64]]* "
  35       "@arr, i64 0, i64 %i2.028, i64 %i1.029\n"
  36       "  %0 = load i64, i64* %arrayidx4, align 8\n"
  37       "  %cmp5 = icmp ugt i64 %0, 10\n"
  38       "  br i1 %cmp5, label %if.then, label %for.inc\n"
  39       "if.then:                                          \n"
  40       "  %arrayidx7 = getelementptr inbounds [8 x [8 x i64]], [8 x [8 x i64]]* "
  41       "@arr2, i64 0, i64 %i2.028, i64 %i1.029\n"
  42       "  %1 = load i64, i64* %arrayidx7, align 8\n"
  43       "  %cmp8 = icmp ugt i64 %1, 100\n"
  44       "  br i1 %cmp8, label %if.then9, label %for.inc\n"
  45       "if.then9:                                         \n"
  46       "  %add = add nuw nsw i64 %i2.028, %i1.029\n"
  47       "  %arrayidx11 = getelementptr inbounds [8 x [8 x i64]], [8 x [8 x "
  48       "i64]]* @arr3, i64 0, i64 %i2.028, i64 %i1.029\n"
  49       "  store i64 %add, i64* %arrayidx11, align 8\n"
  50       "  br label %for.inc\n"
  51       "for.inc:                                          \n"
  52       "  %inc = add nuw nsw i64 %i2.028, 1\n"
  53       "  %exitcond = icmp eq i64 %inc, 8\n"
  54       "  br i1 %exitcond, label %for.inc13, label %for.body3\n"
  55       "for.inc13:                                        \n"
  56       "  %inc14 = add nuw nsw i64 %i1.029, 1\n"
  57       "  %exitcond30 = icmp eq i64 %inc14, 8\n"
  58       "  br i1 %exitcond30, label %for.end15, label %for.cond1.preheader\n"
  59       "for.end15:                                        \n"
  60       "  ret void\n"
  61       "}\n";
  62
  63   Module &M = parseModule(ModuleString);
  64
  65   Function *F = M.getFunction("f");
  66   BasicBlock *LoopHeader = F->getEntryBlock().getSingleSuccessor();
  67   auto Plan = buildHCFG(LoopHeader);
  68
  69   VPRegionBlock *TopRegion = cast<VPRegionBlock>(Plan->getEntry());
  70   VPBlockBase *PH = TopRegion->getEntry();
  71   VPBlockBase *H = PH->getSingleSuccessor();
  72   VPBlockBase *InnerLoopH = H->getSingleSuccessor();
  73   VPBlockBase *OuterIf = InnerLoopH->getSuccessors()[0];
  74   VPBlockBase *InnerLoopLatch = InnerLoopH->getSuccessors()[1];
  75   VPBlockBase *InnerIf = OuterIf->getSuccessors()[0];
  76   VPValue *CBV1 = InnerLoopH->getCondBit();
  77   VPValue *CBV2 = OuterIf->getCondBit();
  78
  79   // Apply predication.
  80   VPlanPredicator VPP(*Plan);
  81   VPP.predicate();
  82
  83   VPBlockBase *InnerLoopLinSucc = InnerLoopH->getSingleSuccessor();
  84   VPBlockBase *OuterIfLinSucc = OuterIf->getSingleSuccessor();
  85   VPBlockBase *InnerIfLinSucc = InnerIf->getSingleSuccessor();
  86   VPValue *OuterIfPred = OuterIf->getPredicate();
  87   VPInstruction *InnerAnd =
  88       cast<VPInstruction>(InnerIf->getEntryBasicBlock()->begin());
  89   VPValue *InnerIfPred = InnerIf->getPredicate();
  90
  91   // Test block predicates
  92   EXPECT_NE(nullptr, CBV1);
  93   EXPECT_NE(nullptr, CBV2);
  94   EXPECT_NE(nullptr, InnerAnd);
  95   EXPECT_EQ(CBV1, OuterIfPred);
  96   EXPECT_EQ(InnerAnd->getOpcode(), Instruction::And);
  97   EXPECT_EQ(InnerAnd->getOperand(0), CBV1);
  98   EXPECT_EQ(InnerAnd->getOperand(1), CBV2);
  99   EXPECT_EQ(InnerIfPred, InnerAnd);
 100
 101   // Test Linearization
 102   EXPECT_EQ(InnerLoopLinSucc, OuterIf);
 103   EXPECT_EQ(OuterIfLinSucc, InnerIf);
 104   EXPECT_EQ(InnerIfLinSucc, InnerLoopLatch);
 105 }
 106
 107 // Test generation of Not and Or during predication.
 108 TEST_F(VPlanPredicatorTest, PredicatorNegOrTest) {
 109   const char *ModuleString =
 110       "@arr = common global [100 x [100 x i32]] zeroinitializer, align 16\n"
 111       "@arr2 = common global [100 x [100 x i32]] zeroinitializer, align 16\n"
 112       "@arr3 = common global [100 x [100 x i32]] zeroinitializer, align 16\n"
 113       "define void @foo() {\n"
 114       "entry:\n"
 115       "  br label %for.cond1.preheader\n"
 116       "for.cond1.preheader:                              \n"
 117       "  %indvars.iv42 = phi i64 [ 0, %entry ], [ %indvars.iv.next43, "
 118       "%for.inc22 ]\n"
 119       "  br label %for.body3\n"
 120       "for.body3:                                        \n"
 121       "  %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ "
 122       "%indvars.iv.next, %if.end21 ]\n"
 123       "  %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 "
 124       "x i32]]* @arr, i64 0, i64 %indvars.iv, i64 %indvars.iv42\n"
 125       "  %0 = load i32, i32* %arrayidx5, align 4\n"
 126       "  %cmp6 = icmp slt i32 %0, 100\n"
 127       "  br i1 %cmp6, label %if.then, label %if.end21\n"
 128       "if.then:                                          \n"
 129       "  %cmp7 = icmp sgt i32 %0, 10\n"
 130       "  br i1 %cmp7, label %if.then8, label %if.else\n"
 131       "if.then8:                                         \n"
 132       "  %add = add nsw i32 %0, 10\n"
 133       "  %arrayidx12 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 "
 134       "x i32]]* @arr2, i64 0, i64 %indvars.iv, i64 %indvars.iv42\n"
 135       "  store i32 %add, i32* %arrayidx12, align 4\n"
 136       "  br label %if.end\n"
 137       "if.else:                                          \n"
 138       "  %sub = add nsw i32 %0, -10\n"
 139       "  %arrayidx16 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 "
 140       "x i32]]* @arr3, i64 0, i64 %indvars.iv, i64 %indvars.iv42\n"
 141       "  store i32 %sub, i32* %arrayidx16, align 4\n"
 142       "  br label %if.end\n"
 143       "if.end:                                           \n"
 144       "  store i32 222, i32* %arrayidx5, align 4\n"
 145       "  br label %if.end21\n"
 146       "if.end21:                                         \n"
 147       "  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1\n"
 148       "  %exitcond = icmp eq i64 %indvars.iv.next, 100\n"
 149       "  br i1 %exitcond, label %for.inc22, label %for.body3\n"
 150       "for.inc22:                                        \n"
 151       "  %indvars.iv.next43 = add nuw nsw i64 %indvars.iv42, 1\n"
 152       "  %exitcond44 = icmp eq i64 %indvars.iv.next43, 100\n"
 153       "  br i1 %exitcond44, label %for.end24, label %for.cond1.preheader\n"
 154       "for.end24:                                        \n"
 155       "  ret void\n"
 156       "}\n";
 157
 158   Module &M = parseModule(ModuleString);
 159   Function *F = M.getFunction("foo");
 160   BasicBlock *LoopHeader = F->getEntryBlock().getSingleSuccessor();
 161   auto Plan = buildHCFG(LoopHeader);
 162
 163   VPRegionBlock *TopRegion = cast<VPRegionBlock>(Plan->getEntry());
 164   VPBlockBase *PH = TopRegion->getEntry();
 165   VPBlockBase *H = PH->getSingleSuccessor();
 166   VPBlockBase *OuterIfCmpBlk = H->getSingleSuccessor();
 167   VPBlockBase *InnerIfCmpBlk = OuterIfCmpBlk->getSuccessors()[0];
 168   VPBlockBase *InnerIfTSucc = InnerIfCmpBlk->getSuccessors()[0];
 169   VPBlockBase *InnerIfFSucc = InnerIfCmpBlk->getSuccessors()[1];
 170   VPBlockBase *TSuccSucc = InnerIfTSucc->getSingleSuccessor();
 171   VPBlockBase *FSuccSucc = InnerIfFSucc->getSingleSuccessor();
 172
 173   VPValue *OuterCBV = OuterIfCmpBlk->getCondBit();
 174   VPValue *InnerCBV = InnerIfCmpBlk->getCondBit();
 175
 176   // Apply predication.
 177   VPlanPredicator VPP(*Plan);
 178   VPP.predicate();
 179
 180   VPInstruction *And =
 181       cast<VPInstruction>(InnerIfTSucc->getEntryBasicBlock()->begin());
 182   VPInstruction *Not =
 183       cast<VPInstruction>(InnerIfFSucc->getEntryBasicBlock()->begin());
 184   VPInstruction *NotAnd = cast<VPInstruction>(
 185       &*std::next(InnerIfFSucc->getEntryBasicBlock()->begin(), 1));
 186   VPInstruction *Or =
 187       cast<VPInstruction>(TSuccSucc->getEntryBasicBlock()->begin());
 188
 189   // Test block predicates
 190   EXPECT_NE(nullptr, OuterCBV);
 191   EXPECT_NE(nullptr, InnerCBV);
 192   EXPECT_NE(nullptr, And);
 193   EXPECT_NE(nullptr, Not);
 194   EXPECT_NE(nullptr, NotAnd);
 195
 196   EXPECT_EQ(And->getOpcode(), Instruction::And);
 197   EXPECT_EQ(NotAnd->getOpcode(), Instruction::And);
 198   EXPECT_EQ(Not->getOpcode(), VPInstruction::Not);
 199
 200   EXPECT_EQ(And->getOperand(0), OuterCBV);
 201   EXPECT_EQ(And->getOperand(1), InnerCBV);
 202
 203   EXPECT_EQ(Not->getOperand(0), InnerCBV);
 204
 205   EXPECT_EQ(NotAnd->getOperand(0), OuterCBV);
 206   EXPECT_EQ(NotAnd->getOperand(1), Not);
 207
 208   EXPECT_EQ(InnerIfTSucc->getPredicate(), And);
 209   EXPECT_EQ(InnerIfFSucc->getPredicate(), NotAnd);
 210
 211   EXPECT_EQ(TSuccSucc, FSuccSucc);
 212   EXPECT_EQ(Or->getOpcode(), Instruction::Or);
 213   EXPECT_EQ(TSuccSucc->getPredicate(), Or);
 214
 215   // Test operands of the Or - account for differences in predecessor block
 216   // ordering.
 217   VPInstruction *OrOp0Inst = cast<VPInstruction>(Or->getOperand(0));
 218   VPInstruction *OrOp1Inst = cast<VPInstruction>(Or->getOperand(1));
 219
 220   bool ValidOrOperands = false;
 221   if (((OrOp0Inst == And) && (OrOp1Inst == NotAnd)) ||
 222       ((OrOp0Inst == NotAnd) && (OrOp1Inst == And)))
 223     ValidOrOperands = true;
 224
 225   EXPECT_TRUE(ValidOrOperands);
 226 }
 227
 228 } // namespace
 229 } // namespace llvm