unittests/IR/PatternMatch.cpp

   1 //===---- llvm/unittest/IR/PatternMatch.cpp - PatternMatch unit tests ----===//
   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 "llvm/IR/PatternMatch.h"
  10 #include "llvm/ADT/STLExtras.h"
  11 #include "llvm/Analysis/ValueTracking.h"
  12 #include "llvm/IR/BasicBlock.h"
  13 #include "llvm/IR/Constants.h"
  14 #include "llvm/IR/DataLayout.h"
  15 #include "llvm/IR/DerivedTypes.h"
  16 #include "llvm/IR/Function.h"
  17 #include "llvm/IR/IRBuilder.h"
  18 #include "llvm/IR/Instructions.h"
  19 #include "llvm/IR/LLVMContext.h"
  20 #include "llvm/IR/MDBuilder.h"
  21 #include "llvm/IR/Module.h"
  22 #include "llvm/IR/NoFolder.h"
  23 #include "llvm/IR/Operator.h"
  24 #include "llvm/IR/Type.h"
  25 #include "gtest/gtest.h"
  26
  27 using namespace llvm;
  28 using namespace llvm::PatternMatch;
  29
  30 namespace {
  31
  32 struct PatternMatchTest : ::testing::Test {
  33   LLVMContext Ctx;
  34   std::unique_ptr<Module> M;
  35   Function *F;
  36   BasicBlock *BB;
  37   IRBuilder<NoFolder> IRB;
  38
  39   PatternMatchTest()
  40       : M(new Module("PatternMatchTestModule", Ctx)),
  41         F(Function::Create(
  42             FunctionType::get(Type::getVoidTy(Ctx), /* IsVarArg */ false),
  43             Function::ExternalLinkage, "f", M.get())),
  44         BB(BasicBlock::Create(Ctx, "entry", F)), IRB(BB) {}
  45 };
  46
  47 TEST_F(PatternMatchTest, OneUse) {
  48   // Build up a little tree of values:
  49   //
  50   //   One  = (1 + 2) + 42
  51   //   Two  = One + 42
  52   //   Leaf = (Two + 8) + (Two + 13)
  53   Value *One = IRB.CreateAdd(IRB.CreateAdd(IRB.getInt32(1), IRB.getInt32(2)),
  54                              IRB.getInt32(42));
  55   Value *Two = IRB.CreateAdd(One, IRB.getInt32(42));
  56   Value *Leaf = IRB.CreateAdd(IRB.CreateAdd(Two, IRB.getInt32(8)),
  57                               IRB.CreateAdd(Two, IRB.getInt32(13)));
  58   Value *V;
  59
  60   EXPECT_TRUE(m_OneUse(m_Value(V)).match(One));
  61   EXPECT_EQ(One, V);
  62
  63   EXPECT_FALSE(m_OneUse(m_Value()).match(Two));
  64   EXPECT_FALSE(m_OneUse(m_Value()).match(Leaf));
  65 }
  66
  67 TEST_F(PatternMatchTest, CommutativeDeferredValue) {
  68   Value *X = IRB.getInt32(1);
  69   Value *Y = IRB.getInt32(2);
  70
  71   {
  72     Value *tX = X;
  73     EXPECT_TRUE(match(X, m_Deferred(tX)));
  74     EXPECT_FALSE(match(Y, m_Deferred(tX)));
  75   }
  76   {
  77     const Value *tX = X;
  78     EXPECT_TRUE(match(X, m_Deferred(tX)));
  79     EXPECT_FALSE(match(Y, m_Deferred(tX)));
  80   }
  81   {
  82     Value *const tX = X;
  83     EXPECT_TRUE(match(X, m_Deferred(tX)));
  84     EXPECT_FALSE(match(Y, m_Deferred(tX)));
  85   }
  86   {
  87     const Value *const tX = X;
  88     EXPECT_TRUE(match(X, m_Deferred(tX)));
  89     EXPECT_FALSE(match(Y, m_Deferred(tX)));
  90   }
  91
  92   {
  93     Value *tX = nullptr;
  94     EXPECT_TRUE(match(IRB.CreateAnd(X, X), m_And(m_Value(tX), m_Deferred(tX))));
  95     EXPECT_EQ(tX, X);
  96   }
  97   {
  98     Value *tX = nullptr;
  99     EXPECT_FALSE(
 100         match(IRB.CreateAnd(X, Y), m_c_And(m_Value(tX), m_Deferred(tX))));
 101   }
 102
 103   auto checkMatch = [X, Y](Value *Pattern) {
 104     Value *tX = nullptr, *tY = nullptr;
 105     EXPECT_TRUE(match(
 106         Pattern, m_c_And(m_Value(tX), m_c_And(m_Deferred(tX), m_Value(tY)))));
 107     EXPECT_EQ(tX, X);
 108     EXPECT_EQ(tY, Y);
 109   };
 110
 111   checkMatch(IRB.CreateAnd(X, IRB.CreateAnd(X, Y)));
 112   checkMatch(IRB.CreateAnd(X, IRB.CreateAnd(Y, X)));
 113   checkMatch(IRB.CreateAnd(IRB.CreateAnd(X, Y), X));
 114   checkMatch(IRB.CreateAnd(IRB.CreateAnd(Y, X), X));
 115 }
 116
 117 TEST_F(PatternMatchTest, FloatingPointOrderedMin) {
 118   Type *FltTy = IRB.getFloatTy();
 119   Value *L = ConstantFP::get(FltTy, 1.0);
 120   Value *R = ConstantFP::get(FltTy, 2.0);
 121   Value *MatchL, *MatchR;
 122
 123   // Test OLT.
 124   EXPECT_TRUE(m_OrdFMin(m_Value(MatchL), m_Value(MatchR))
 125                   .match(IRB.CreateSelect(IRB.CreateFCmpOLT(L, R), L, R)));
 126   EXPECT_EQ(L, MatchL);
 127   EXPECT_EQ(R, MatchR);
 128
 129   // Test OLE.
 130   EXPECT_TRUE(m_OrdFMin(m_Value(MatchL), m_Value(MatchR))
 131                   .match(IRB.CreateSelect(IRB.CreateFCmpOLE(L, R), L, R)));
 132   EXPECT_EQ(L, MatchL);
 133   EXPECT_EQ(R, MatchR);
 134
 135   // Test no match on OGE.
 136   EXPECT_FALSE(m_OrdFMin(m_Value(MatchL), m_Value(MatchR))
 137                    .match(IRB.CreateSelect(IRB.CreateFCmpOGE(L, R), L, R)));
 138
 139   // Test no match on OGT.
 140   EXPECT_FALSE(m_OrdFMin(m_Value(MatchL), m_Value(MatchR))
 141                    .match(IRB.CreateSelect(IRB.CreateFCmpOGT(L, R), L, R)));
 142
 143   // Test inverted selects. Note, that this "inverts" the ordering, e.g.:
 144   // %cmp = fcmp oge L, R
 145   // %min = select %cmp R, L
 146   // Given L == NaN
 147   // the above is expanded to %cmp == false ==> %min = L
 148   // which is true for UnordFMin, not OrdFMin, so test that:
 149
 150   // [OU]GE with inverted select.
 151   EXPECT_FALSE(m_OrdFMin(m_Value(MatchL), m_Value(MatchR))
 152                   .match(IRB.CreateSelect(IRB.CreateFCmpOGE(L, R), R, L)));
 153   EXPECT_TRUE(m_OrdFMin(m_Value(MatchL), m_Value(MatchR))
 154                   .match(IRB.CreateSelect(IRB.CreateFCmpUGE(L, R), R, L)));
 155   EXPECT_EQ(L, MatchL);
 156   EXPECT_EQ(R, MatchR);
 157
 158   // [OU]GT with inverted select.
 159   EXPECT_FALSE(m_OrdFMin(m_Value(MatchL), m_Value(MatchR))
 160                   .match(IRB.CreateSelect(IRB.CreateFCmpOGT(L, R), R, L)));
 161   EXPECT_TRUE(m_OrdFMin(m_Value(MatchL), m_Value(MatchR))
 162                   .match(IRB.CreateSelect(IRB.CreateFCmpUGT(L, R), R, L)));
 163   EXPECT_EQ(L, MatchL);
 164   EXPECT_EQ(R, MatchR);
 165 }
 166
 167 TEST_F(PatternMatchTest, FloatingPointOrderedMax) {
 168   Type *FltTy = IRB.getFloatTy();
 169   Value *L = ConstantFP::get(FltTy, 1.0);
 170   Value *R = ConstantFP::get(FltTy, 2.0);
 171   Value *MatchL, *MatchR;
 172
 173   // Test OGT.
 174   EXPECT_TRUE(m_OrdFMax(m_Value(MatchL), m_Value(MatchR))
 175                   .match(IRB.CreateSelect(IRB.CreateFCmpOGT(L, R), L, R)));
 176   EXPECT_EQ(L, MatchL);
 177   EXPECT_EQ(R, MatchR);
 178
 179   // Test OGE.
 180   EXPECT_TRUE(m_OrdFMax(m_Value(MatchL), m_Value(MatchR))
 181                   .match(IRB.CreateSelect(IRB.CreateFCmpOGE(L, R), L, R)));
 182   EXPECT_EQ(L, MatchL);
 183   EXPECT_EQ(R, MatchR);
 184
 185   // Test no match on OLE.
 186   EXPECT_FALSE(m_OrdFMax(m_Value(MatchL), m_Value(MatchR))
 187                    .match(IRB.CreateSelect(IRB.CreateFCmpOLE(L, R), L, R)));
 188
 189   // Test no match on OLT.
 190   EXPECT_FALSE(m_OrdFMax(m_Value(MatchL), m_Value(MatchR))
 191                    .match(IRB.CreateSelect(IRB.CreateFCmpOLT(L, R), L, R)));
 192
 193
 194   // Test inverted selects. Note, that this "inverts" the ordering, e.g.:
 195   // %cmp = fcmp ole L, R
 196   // %max = select %cmp, R, L
 197   // Given L == NaN,
 198   // the above is expanded to %cmp == false ==> %max == L
 199   // which is true for UnordFMax, not OrdFMax, so test that:
 200
 201   // [OU]LE with inverted select.
 202   EXPECT_FALSE(m_OrdFMax(m_Value(MatchL), m_Value(MatchR))
 203                    .match(IRB.CreateSelect(IRB.CreateFCmpOLE(L, R), R, L)));
 204   EXPECT_TRUE(m_OrdFMax(m_Value(MatchL), m_Value(MatchR))
 205                   .match(IRB.CreateSelect(IRB.CreateFCmpULE(L, R), R, L)));
 206   EXPECT_EQ(L, MatchL);
 207   EXPECT_EQ(R, MatchR);
 208
 209   // [OUT]LT with inverted select.
 210   EXPECT_FALSE(m_OrdFMax(m_Value(MatchL), m_Value(MatchR))
 211                    .match(IRB.CreateSelect(IRB.CreateFCmpOLT(L, R), R, L)));
 212   EXPECT_TRUE(m_OrdFMax(m_Value(MatchL), m_Value(MatchR))
 213                   .match(IRB.CreateSelect(IRB.CreateFCmpULT(L, R), R, L)));
 214   EXPECT_EQ(L, MatchL);
 215   EXPECT_EQ(R, MatchR);
 216 }
 217
 218 TEST_F(PatternMatchTest, FloatingPointUnorderedMin) {
 219   Type *FltTy = IRB.getFloatTy();
 220   Value *L = ConstantFP::get(FltTy, 1.0);
 221   Value *R = ConstantFP::get(FltTy, 2.0);
 222   Value *MatchL, *MatchR;
 223
 224   // Test ULT.
 225   EXPECT_TRUE(m_UnordFMin(m_Value(MatchL), m_Value(MatchR))
 226                   .match(IRB.CreateSelect(IRB.CreateFCmpULT(L, R), L, R)));
 227   EXPECT_EQ(L, MatchL);
 228   EXPECT_EQ(R, MatchR);
 229
 230   // Test ULE.
 231   EXPECT_TRUE(m_UnordFMin(m_Value(MatchL), m_Value(MatchR))
 232                   .match(IRB.CreateSelect(IRB.CreateFCmpULE(L, R), L, R)));
 233   EXPECT_EQ(L, MatchL);
 234   EXPECT_EQ(R, MatchR);
 235
 236   // Test no match on UGE.
 237   EXPECT_FALSE(m_UnordFMin(m_Value(MatchL), m_Value(MatchR))
 238                    .match(IRB.CreateSelect(IRB.CreateFCmpUGE(L, R), L, R)));
 239
 240   // Test no match on UGT.
 241   EXPECT_FALSE(m_UnordFMin(m_Value(MatchL), m_Value(MatchR))
 242                    .match(IRB.CreateSelect(IRB.CreateFCmpUGT(L, R), L, R)));
 243
 244   // Test inverted selects. Note, that this "inverts" the ordering, e.g.:
 245   // %cmp = fcmp uge L, R
 246   // %min = select %cmp R, L
 247   // Given L == NaN
 248   // the above is expanded to %cmp == true ==> %min = R
 249   // which is true for OrdFMin, not UnordFMin, so test that:
 250
 251   // [UO]GE with inverted select.
 252   EXPECT_FALSE(m_UnordFMin(m_Value(MatchL), m_Value(MatchR))
 253                   .match(IRB.CreateSelect(IRB.CreateFCmpUGE(L, R), R, L)));
 254   EXPECT_TRUE(m_UnordFMin(m_Value(MatchL), m_Value(MatchR))
 255                   .match(IRB.CreateSelect(IRB.CreateFCmpOGE(L, R), R, L)));
 256   EXPECT_EQ(L, MatchL);
 257   EXPECT_EQ(R, MatchR);
 258
 259   // [UO]GT with inverted select.
 260   EXPECT_FALSE(m_UnordFMin(m_Value(MatchL), m_Value(MatchR))
 261                   .match(IRB.CreateSelect(IRB.CreateFCmpUGT(L, R), R, L)));
 262   EXPECT_TRUE(m_UnordFMin(m_Value(MatchL), m_Value(MatchR))
 263                   .match(IRB.CreateSelect(IRB.CreateFCmpOGT(L, R), R, L)));
 264   EXPECT_EQ(L, MatchL);
 265   EXPECT_EQ(R, MatchR);
 266 }
 267
 268 TEST_F(PatternMatchTest, FloatingPointUnorderedMax) {
 269   Type *FltTy = IRB.getFloatTy();
 270   Value *L = ConstantFP::get(FltTy, 1.0);
 271   Value *R = ConstantFP::get(FltTy, 2.0);
 272   Value *MatchL, *MatchR;
 273
 274   // Test UGT.
 275   EXPECT_TRUE(m_UnordFMax(m_Value(MatchL), m_Value(MatchR))
 276                   .match(IRB.CreateSelect(IRB.CreateFCmpUGT(L, R), L, R)));
 277   EXPECT_EQ(L, MatchL);
 278   EXPECT_EQ(R, MatchR);
 279
 280   // Test UGE.
 281   EXPECT_TRUE(m_UnordFMax(m_Value(MatchL), m_Value(MatchR))
 282                   .match(IRB.CreateSelect(IRB.CreateFCmpUGE(L, R), L, R)));
 283   EXPECT_EQ(L, MatchL);
 284   EXPECT_EQ(R, MatchR);
 285
 286   // Test no match on ULE.
 287   EXPECT_FALSE(m_UnordFMax(m_Value(MatchL), m_Value(MatchR))
 288                    .match(IRB.CreateSelect(IRB.CreateFCmpULE(L, R), L, R)));
 289
 290   // Test no match on ULT.
 291   EXPECT_FALSE(m_UnordFMax(m_Value(MatchL), m_Value(MatchR))
 292                    .match(IRB.CreateSelect(IRB.CreateFCmpULT(L, R), L, R)));
 293
 294   // Test inverted selects. Note, that this "inverts" the ordering, e.g.:
 295   // %cmp = fcmp ule L, R
 296   // %max = select %cmp R, L
 297   // Given L == NaN
 298   // the above is expanded to %cmp == true ==> %max = R
 299   // which is true for OrdFMax, not UnordFMax, so test that:
 300
 301   // [UO]LE with inverted select.
 302   EXPECT_FALSE(m_UnordFMax(m_Value(MatchL), m_Value(MatchR))
 303                   .match(IRB.CreateSelect(IRB.CreateFCmpULE(L, R), R, L)));
 304   EXPECT_TRUE(m_UnordFMax(m_Value(MatchL), m_Value(MatchR))
 305                   .match(IRB.CreateSelect(IRB.CreateFCmpOLE(L, R), R, L)));
 306   EXPECT_EQ(L, MatchL);
 307   EXPECT_EQ(R, MatchR);
 308
 309   // [UO]LT with inverted select.
 310   EXPECT_FALSE(m_UnordFMax(m_Value(MatchL), m_Value(MatchR))
 311                   .match(IRB.CreateSelect(IRB.CreateFCmpULT(L, R), R, L)));
 312   EXPECT_TRUE(m_UnordFMax(m_Value(MatchL), m_Value(MatchR))
 313                   .match(IRB.CreateSelect(IRB.CreateFCmpOLT(L, R), R, L)));
 314   EXPECT_EQ(L, MatchL);
 315   EXPECT_EQ(R, MatchR);
 316 }
 317
 318 TEST_F(PatternMatchTest, OverflowingBinOps) {
 319   Value *L = IRB.getInt32(1);
 320   Value *R = IRB.getInt32(2);
 321   Value *MatchL, *MatchR;
 322
 323   EXPECT_TRUE(
 324       m_NSWAdd(m_Value(MatchL), m_Value(MatchR)).match(IRB.CreateNSWAdd(L, R)));
 325   EXPECT_EQ(L, MatchL);
 326   EXPECT_EQ(R, MatchR);
 327   MatchL = MatchR = nullptr;
 328   EXPECT_TRUE(
 329       m_NSWSub(m_Value(MatchL), m_Value(MatchR)).match(IRB.CreateNSWSub(L, R)));
 330   EXPECT_EQ(L, MatchL);
 331   EXPECT_EQ(R, MatchR);
 332   MatchL = MatchR = nullptr;
 333   EXPECT_TRUE(
 334       m_NSWMul(m_Value(MatchL), m_Value(MatchR)).match(IRB.CreateNSWMul(L, R)));
 335   EXPECT_EQ(L, MatchL);
 336   EXPECT_EQ(R, MatchR);
 337   MatchL = MatchR = nullptr;
 338   EXPECT_TRUE(m_NSWShl(m_Value(MatchL), m_Value(MatchR)).match(
 339       IRB.CreateShl(L, R, "", /* NUW */ false, /* NSW */ true)));
 340   EXPECT_EQ(L, MatchL);
 341   EXPECT_EQ(R, MatchR);
 342
 343   EXPECT_TRUE(
 344       m_NUWAdd(m_Value(MatchL), m_Value(MatchR)).match(IRB.CreateNUWAdd(L, R)));
 345   EXPECT_EQ(L, MatchL);
 346   EXPECT_EQ(R, MatchR);
 347   MatchL = MatchR = nullptr;
 348   EXPECT_TRUE(
 349       m_NUWSub(m_Value(MatchL), m_Value(MatchR)).match(IRB.CreateNUWSub(L, R)));
 350   EXPECT_EQ(L, MatchL);
 351   EXPECT_EQ(R, MatchR);
 352   MatchL = MatchR = nullptr;
 353   EXPECT_TRUE(
 354       m_NUWMul(m_Value(MatchL), m_Value(MatchR)).match(IRB.CreateNUWMul(L, R)));
 355   EXPECT_EQ(L, MatchL);
 356   EXPECT_EQ(R, MatchR);
 357   MatchL = MatchR = nullptr;
 358   EXPECT_TRUE(m_NUWShl(m_Value(MatchL), m_Value(MatchR)).match(
 359       IRB.CreateShl(L, R, "", /* NUW */ true, /* NSW */ false)));
 360   EXPECT_EQ(L, MatchL);
 361   EXPECT_EQ(R, MatchR);
 362
 363   EXPECT_FALSE(m_NSWAdd(m_Value(), m_Value()).match(IRB.CreateAdd(L, R)));
 364   EXPECT_FALSE(m_NSWAdd(m_Value(), m_Value()).match(IRB.CreateNUWAdd(L, R)));
 365   EXPECT_FALSE(m_NSWAdd(m_Value(), m_Value()).match(IRB.CreateNSWSub(L, R)));
 366   EXPECT_FALSE(m_NSWSub(m_Value(), m_Value()).match(IRB.CreateSub(L, R)));
 367   EXPECT_FALSE(m_NSWSub(m_Value(), m_Value()).match(IRB.CreateNUWSub(L, R)));
 368   EXPECT_FALSE(m_NSWSub(m_Value(), m_Value()).match(IRB.CreateNSWAdd(L, R)));
 369   EXPECT_FALSE(m_NSWMul(m_Value(), m_Value()).match(IRB.CreateMul(L, R)));
 370   EXPECT_FALSE(m_NSWMul(m_Value(), m_Value()).match(IRB.CreateNUWMul(L, R)));
 371   EXPECT_FALSE(m_NSWMul(m_Value(), m_Value()).match(IRB.CreateNSWAdd(L, R)));
 372   EXPECT_FALSE(m_NSWShl(m_Value(), m_Value()).match(IRB.CreateShl(L, R)));
 373   EXPECT_FALSE(m_NSWShl(m_Value(), m_Value()).match(
 374       IRB.CreateShl(L, R, "", /* NUW */ true, /* NSW */ false)));
 375   EXPECT_FALSE(m_NSWShl(m_Value(), m_Value()).match(IRB.CreateNSWAdd(L, R)));
 376
 377   EXPECT_FALSE(m_NUWAdd(m_Value(), m_Value()).match(IRB.CreateAdd(L, R)));
 378   EXPECT_FALSE(m_NUWAdd(m_Value(), m_Value()).match(IRB.CreateNSWAdd(L, R)));
 379   EXPECT_FALSE(m_NUWAdd(m_Value(), m_Value()).match(IRB.CreateNUWSub(L, R)));
 380   EXPECT_FALSE(m_NUWSub(m_Value(), m_Value()).match(IRB.CreateSub(L, R)));
 381   EXPECT_FALSE(m_NUWSub(m_Value(), m_Value()).match(IRB.CreateNSWSub(L, R)));
 382   EXPECT_FALSE(m_NUWSub(m_Value(), m_Value()).match(IRB.CreateNUWAdd(L, R)));
 383   EXPECT_FALSE(m_NUWMul(m_Value(), m_Value()).match(IRB.CreateMul(L, R)));
 384   EXPECT_FALSE(m_NUWMul(m_Value(), m_Value()).match(IRB.CreateNSWMul(L, R)));
 385   EXPECT_FALSE(m_NUWMul(m_Value(), m_Value()).match(IRB.CreateNUWAdd(L, R)));
 386   EXPECT_FALSE(m_NUWShl(m_Value(), m_Value()).match(IRB.CreateShl(L, R)));
 387   EXPECT_FALSE(m_NUWShl(m_Value(), m_Value()).match(
 388       IRB.CreateShl(L, R, "", /* NUW */ false, /* NSW */ true)));
 389   EXPECT_FALSE(m_NUWShl(m_Value(), m_Value()).match(IRB.CreateNUWAdd(L, R)));
 390 }
 391
 392 TEST_F(PatternMatchTest, LoadStoreOps) {
 393   // Create this load/store sequence:
 394   //
 395   //  %p = alloca i32*
 396   //  %0 = load i32*, i32** %p
 397   //  store i32 42, i32* %0
 398
 399   Value *Alloca = IRB.CreateAlloca(IRB.getInt32Ty());
 400   Value *LoadInst = IRB.CreateLoad(IRB.getInt32Ty(), Alloca);
 401   Value *FourtyTwo = IRB.getInt32(42);
 402   Value *StoreInst = IRB.CreateStore(FourtyTwo, Alloca);
 403   Value *MatchLoad, *MatchStoreVal, *MatchStorePointer;
 404
 405   EXPECT_TRUE(m_Load(m_Value(MatchLoad)).match(LoadInst));
 406   EXPECT_EQ(Alloca, MatchLoad);
 407
 408   EXPECT_TRUE(m_Load(m_Specific(Alloca)).match(LoadInst));
 409
 410   EXPECT_FALSE(m_Load(m_Value(MatchLoad)).match(Alloca));
 411
 412   EXPECT_TRUE(m_Store(m_Value(MatchStoreVal), m_Value(MatchStorePointer))
 413                 .match(StoreInst));
 414   EXPECT_EQ(FourtyTwo, MatchStoreVal);
 415   EXPECT_EQ(Alloca, MatchStorePointer);
 416
 417   EXPECT_FALSE(m_Store(m_Value(MatchStoreVal), m_Value(MatchStorePointer))
 418                 .match(Alloca));
 419
 420   EXPECT_TRUE(m_Store(m_SpecificInt(42), m_Specific(Alloca))
 421                 .match(StoreInst));
 422   EXPECT_FALSE(m_Store(m_SpecificInt(42), m_Specific(FourtyTwo))
 423                 .match(StoreInst));
 424   EXPECT_FALSE(m_Store(m_SpecificInt(43), m_Specific(Alloca))
 425                 .match(StoreInst));
 426 }
 427
 428 TEST_F(PatternMatchTest, VectorOps) {
 429   // Build up small tree of vector operations
 430   //
 431   //   Val = 0 + 1
 432   //   Val2 = Val + 3
 433   //   VI1 = insertelement <2 x i8> undef, i8 1, i32 0 = <1, undef>
 434   //   VI2 = insertelement <2 x i8> %VI1, i8 %Val2, i8 %Val = <1, 4>
 435   //   VI3 = insertelement <2 x i8> %VI1, i8 %Val2, i32 1 = <1, 4>
 436   //   VI4 = insertelement <2 x i8> %VI1, i8 2, i8 %Val = <1, 2>
 437   //
 438   //   SI1 = shufflevector <2 x i8> %VI1, <2 x i8> undef, zeroinitializer
 439   //   SI2 = shufflevector <2 x i8> %VI3, <2 x i8> %VI4, <2 x i8> <i8 0, i8 2>
 440   //   SI3 = shufflevector <2 x i8> %VI3, <2 x i8> undef, zeroinitializer
 441   //   SI4 = shufflevector <2 x i8> %VI4, <2 x i8> undef, zeroinitializer
 442   //
 443   //   SP1 = VectorSplat(2, i8 2)
 444   //   SP2 = VectorSplat(2, i8 %Val)
 445   Type *VecTy = VectorType::get(IRB.getInt8Ty(), 2);
 446   Type *i32 = IRB.getInt32Ty();
 447   Type *i32VecTy = VectorType::get(i32, 2);
 448
 449   Value *Val = IRB.CreateAdd(IRB.getInt8(0), IRB.getInt8(1));
 450   Value *Val2 = IRB.CreateAdd(Val, IRB.getInt8(3));
 451
 452   SmallVector<Constant *, 2> VecElemIdxs;
 453   VecElemIdxs.push_back(ConstantInt::get(i32, 0));
 454   VecElemIdxs.push_back(ConstantInt::get(i32, 2));
 455   auto *IdxVec = ConstantVector::get(VecElemIdxs);
 456
 457   Value *UndefVec = UndefValue::get(VecTy);
 458   Value *VI1 = IRB.CreateInsertElement(UndefVec, IRB.getInt8(1), (uint64_t)0);
 459   Value *VI2 = IRB.CreateInsertElement(VI1, Val2, Val);
 460   Value *VI3 = IRB.CreateInsertElement(VI1, Val2, (uint64_t)1);
 461   Value *VI4 = IRB.CreateInsertElement(VI1, IRB.getInt8(2), Val);
 462
 463   Value *EX1 = IRB.CreateExtractElement(VI4, Val);
 464   Value *EX2 = IRB.CreateExtractElement(VI4, (uint64_t)0);
 465   Value *EX3 = IRB.CreateExtractElement(IdxVec, (uint64_t)1);
 466
 467   Value *Zero = ConstantAggregateZero::get(i32VecTy);
 468   Value *SI1 = IRB.CreateShuffleVector(VI1, UndefVec, Zero);
 469   Value *SI2 = IRB.CreateShuffleVector(VI3, VI4, IdxVec);
 470   Value *SI3 = IRB.CreateShuffleVector(VI3, UndefVec, Zero);
 471   Value *SI4 = IRB.CreateShuffleVector(VI4, UndefVec, Zero);
 472
 473   Value *SP1 = IRB.CreateVectorSplat(2, IRB.getInt8(2));
 474   Value *SP2 = IRB.CreateVectorSplat(2, Val);
 475
 476   Value *A = nullptr, *B = nullptr, *C = nullptr;
 477
 478   // Test matching insertelement
 479   EXPECT_TRUE(match(VI1, m_InsertElement(m_Value(), m_Value(), m_Value())));
 480   EXPECT_TRUE(
 481       match(VI1, m_InsertElement(m_Undef(), m_ConstantInt(), m_ConstantInt())));
 482   EXPECT_TRUE(
 483       match(VI1, m_InsertElement(m_Undef(), m_ConstantInt(), m_Zero())));
 484   EXPECT_TRUE(
 485       match(VI1, m_InsertElement(m_Undef(), m_SpecificInt(1), m_Zero())));
 486   EXPECT_TRUE(match(VI2, m_InsertElement(m_Value(), m_Value(), m_Value())));
 487   EXPECT_FALSE(
 488       match(VI2, m_InsertElement(m_Value(), m_Value(), m_ConstantInt())));
 489   EXPECT_FALSE(
 490       match(VI2, m_InsertElement(m_Value(), m_ConstantInt(), m_Value())));
 491   EXPECT_FALSE(match(VI2, m_InsertElement(m_Constant(), m_Value(), m_Value())));
 492   EXPECT_TRUE(match(VI3, m_InsertElement(m_Value(A), m_Value(B), m_Value(C))));
 493   EXPECT_TRUE(A == VI1);
 494   EXPECT_TRUE(B == Val2);
 495   EXPECT_TRUE(isa<ConstantInt>(C));
 496   A = B = C = nullptr; // reset
 497
 498   // Test matching extractelement
 499   EXPECT_TRUE(match(EX1, m_ExtractElement(m_Value(A), m_Value(B))));
 500   EXPECT_TRUE(A == VI4);
 501   EXPECT_TRUE(B == Val);
 502   A = B = C = nullptr; // reset
 503   EXPECT_FALSE(match(EX1, m_ExtractElement(m_Value(), m_ConstantInt())));
 504   EXPECT_TRUE(match(EX2, m_ExtractElement(m_Value(), m_ConstantInt())));
 505   EXPECT_TRUE(match(EX3, m_ExtractElement(m_Constant(), m_ConstantInt())));
 506
 507   // Test matching shufflevector
 508   EXPECT_TRUE(match(SI1, m_ShuffleVector(m_Value(), m_Undef(), m_Zero())));
 509   EXPECT_TRUE(match(SI2, m_ShuffleVector(m_Value(A), m_Value(B), m_Value(C))));
 510   EXPECT_TRUE(A == VI3);
 511   EXPECT_TRUE(B == VI4);
 512   EXPECT_TRUE(C == IdxVec);
 513   A = B = C = nullptr; // reset
 514
 515   // Test matching the vector splat pattern
 516   EXPECT_TRUE(match(
 517       SI1,
 518       m_ShuffleVector(m_InsertElement(m_Undef(), m_SpecificInt(1), m_Zero()),
 519                       m_Undef(), m_Zero())));
 520   EXPECT_FALSE(match(
 521       SI3, m_ShuffleVector(m_InsertElement(m_Undef(), m_Value(), m_Zero()),
 522                            m_Undef(), m_Zero())));
 523   EXPECT_FALSE(match(
 524       SI4, m_ShuffleVector(m_InsertElement(m_Undef(), m_Value(), m_Zero()),
 525                            m_Undef(), m_Zero())));
 526   EXPECT_TRUE(match(
 527       SP1,
 528       m_ShuffleVector(m_InsertElement(m_Undef(), m_SpecificInt(2), m_Zero()),
 529                       m_Undef(), m_Zero())));
 530   EXPECT_TRUE(match(
 531       SP2, m_ShuffleVector(m_InsertElement(m_Undef(), m_Value(A), m_Zero()),
 532                            m_Undef(), m_Zero())));
 533   EXPECT_TRUE(A == Val);
 534 }
 535
 536 TEST_F(PatternMatchTest, VectorUndefInt) {
 537   Type *ScalarTy = IRB.getInt8Ty();
 538   Type *VectorTy = VectorType::get(ScalarTy, 4);
 539   Constant *ScalarUndef = UndefValue::get(ScalarTy);
 540   Constant *VectorUndef = UndefValue::get(VectorTy);
 541   Constant *ScalarZero = Constant::getNullValue(ScalarTy);
 542   Constant *VectorZero = Constant::getNullValue(VectorTy);
 543
 544   SmallVector<Constant *, 4> Elems;
 545   Elems.push_back(ScalarUndef);
 546   Elems.push_back(ScalarZero);
 547   Elems.push_back(ScalarUndef);
 548   Elems.push_back(ScalarZero);
 549   Constant *VectorZeroUndef = ConstantVector::get(Elems);
 550
 551   EXPECT_TRUE(match(ScalarUndef, m_Undef()));
 552   EXPECT_TRUE(match(VectorUndef, m_Undef()));
 553   EXPECT_FALSE(match(ScalarZero, m_Undef()));
 554   EXPECT_FALSE(match(VectorZero, m_Undef()));
 555   EXPECT_FALSE(match(VectorZeroUndef, m_Undef()));
 556
 557   EXPECT_FALSE(match(ScalarUndef, m_Zero()));
 558   EXPECT_FALSE(match(VectorUndef, m_Zero()));
 559   EXPECT_TRUE(match(ScalarZero, m_Zero()));
 560   EXPECT_TRUE(match(VectorZero, m_Zero()));
 561   EXPECT_TRUE(match(VectorZeroUndef, m_Zero()));
 562 }
 563
 564 TEST_F(PatternMatchTest, VectorUndefFloat) {
 565   Type *ScalarTy = IRB.getFloatTy();
 566   Type *VectorTy = VectorType::get(ScalarTy, 4);
 567   Constant *ScalarUndef = UndefValue::get(ScalarTy);
 568   Constant *VectorUndef = UndefValue::get(VectorTy);
 569   Constant *ScalarZero = Constant::getNullValue(ScalarTy);
 570   Constant *VectorZero = Constant::getNullValue(VectorTy);
 571
 572   SmallVector<Constant *, 4> Elems;
 573   Elems.push_back(ScalarUndef);
 574   Elems.push_back(ScalarZero);
 575   Elems.push_back(ScalarUndef);
 576   Elems.push_back(ScalarZero);
 577   Constant *VectorZeroUndef = ConstantVector::get(Elems);
 578
 579   EXPECT_TRUE(match(ScalarUndef, m_Undef()));
 580   EXPECT_TRUE(match(VectorUndef, m_Undef()));
 581   EXPECT_FALSE(match(ScalarZero, m_Undef()));
 582   EXPECT_FALSE(match(VectorZero, m_Undef()));
 583   EXPECT_FALSE(match(VectorZeroUndef, m_Undef()));
 584
 585   EXPECT_FALSE(match(ScalarUndef, m_AnyZeroFP()));
 586   EXPECT_FALSE(match(VectorUndef, m_AnyZeroFP()));
 587   EXPECT_TRUE(match(ScalarZero, m_AnyZeroFP()));
 588   EXPECT_TRUE(match(VectorZero, m_AnyZeroFP()));
 589   EXPECT_TRUE(match(VectorZeroUndef, m_AnyZeroFP()));
 590 }
 591
 592 template <typename T> struct MutableConstTest : PatternMatchTest { };
 593
 594 typedef ::testing::Types<std::tuple<Value*, Instruction*>,
 595                          std::tuple<const Value*, const Instruction *>>
 596     MutableConstTestTypes;
 597 TYPED_TEST_CASE(MutableConstTest, MutableConstTestTypes);
 598
 599 TYPED_TEST(MutableConstTest, ICmp) {
 600   auto &IRB = PatternMatchTest::IRB;
 601
 602   typedef typename std::tuple_element<0, TypeParam>::type ValueType;
 603   typedef typename std::tuple_element<1, TypeParam>::type InstructionType;
 604
 605   Value *L = IRB.getInt32(1);
 606   Value *R = IRB.getInt32(2);
 607   ICmpInst::Predicate Pred = ICmpInst::ICMP_UGT;
 608
 609   ValueType MatchL;
 610   ValueType MatchR;
 611   ICmpInst::Predicate MatchPred;
 612
 613   EXPECT_TRUE(m_ICmp(MatchPred, m_Value(MatchL), m_Value(MatchR))
 614               .match((InstructionType)IRB.CreateICmp(Pred, L, R)));
 615   EXPECT_EQ(L, MatchL);
 616   EXPECT_EQ(R, MatchR);
 617 }
 618
 619 } // anonymous namespace.