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/APSInt.h"
11 #include "llvm/ADT/STLExtras.h"
12 #include "llvm/Analysis/ValueTracking.h"
13 #include "llvm/IR/BasicBlock.h"
14 #include "llvm/IR/Constants.h"
15 #include "llvm/IR/DataLayout.h"
16 #include "llvm/IR/DerivedTypes.h"
17 #include "llvm/IR/Function.h"
18 #include "llvm/IR/IRBuilder.h"
19 #include "llvm/IR/Instructions.h"
20 #include "llvm/IR/LLVMContext.h"
21 #include "llvm/IR/MDBuilder.h"
22 #include "llvm/IR/Module.h"
23 #include "llvm/IR/NoFolder.h"
24 #include "llvm/IR/Operator.h"
25 #include "llvm/IR/Type.h"
26 #include "gtest/gtest.h"
27 
28 using namespace llvm;
29 using namespace llvm::PatternMatch;
30 
31 namespace {
32 
33 struct PatternMatchTest : ::testing::Test {
34   LLVMContext Ctx;
35   std::unique_ptr<Module> M;
36   Function *F;
37   BasicBlock *BB;
38   IRBuilder<NoFolder> IRB;
39 
40   PatternMatchTest()
41       : M(new Module("PatternMatchTestModule", Ctx)),
42         F(Function::Create(
43             FunctionType::get(Type::getVoidTy(Ctx), /* IsVarArg */ false),
44             Function::ExternalLinkage, "f", M.get())),
45         BB(BasicBlock::Create(Ctx, "entry", F)), IRB(BB) {}
46 };
47 
48 TEST_F(PatternMatchTest, OneUse) {
49   // Build up a little tree of values:
50   //
51   //   One  = (1 + 2) + 42
52   //   Two  = One + 42
53   //   Leaf = (Two + 8) + (Two + 13)
54   Value *One = IRB.CreateAdd(IRB.CreateAdd(IRB.getInt32(1), IRB.getInt32(2)),
55                              IRB.getInt32(42));
56   Value *Two = IRB.CreateAdd(One, IRB.getInt32(42));
57   Value *Leaf = IRB.CreateAdd(IRB.CreateAdd(Two, IRB.getInt32(8)),
58                               IRB.CreateAdd(Two, IRB.getInt32(13)));
59   Value *V;
60 
61   EXPECT_TRUE(m_OneUse(m_Value(V)).match(One));
62   EXPECT_EQ(One, V);
63 
64   EXPECT_FALSE(m_OneUse(m_Value()).match(Two));
65   EXPECT_FALSE(m_OneUse(m_Value()).match(Leaf));
66 }
67 
68 TEST_F(PatternMatchTest, SpecificIntEQ) {
69   Type *IntTy = IRB.getInt32Ty();
70   unsigned BitWidth = IntTy->getScalarSizeInBits();
71 
72   Value *Zero = ConstantInt::get(IntTy, 0);
73   Value *One = ConstantInt::get(IntTy, 1);
74   Value *NegOne = ConstantInt::get(IntTy, -1);
75 
76   EXPECT_TRUE(
77       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_EQ, APInt(BitWidth, 0))
78           .match(Zero));
79   EXPECT_FALSE(
80       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_EQ, APInt(BitWidth, 0))
81           .match(One));
82   EXPECT_FALSE(
83       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_EQ, APInt(BitWidth, 0))
84           .match(NegOne));
85 
86   EXPECT_FALSE(
87       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_EQ, APInt(BitWidth, 1))
88           .match(Zero));
89   EXPECT_TRUE(
90       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_EQ, APInt(BitWidth, 1))
91           .match(One));
92   EXPECT_FALSE(
93       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_EQ, APInt(BitWidth, 1))
94           .match(NegOne));
95 
96   EXPECT_FALSE(
97       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_EQ, APInt(BitWidth, -1))
98           .match(Zero));
99   EXPECT_FALSE(
100       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_EQ, APInt(BitWidth, -1))
101           .match(One));
102   EXPECT_TRUE(
103       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_EQ, APInt(BitWidth, -1))
104           .match(NegOne));
105 }
106 
107 TEST_F(PatternMatchTest, SpecificIntNE) {
108   Type *IntTy = IRB.getInt32Ty();
109   unsigned BitWidth = IntTy->getScalarSizeInBits();
110 
111   Value *Zero = ConstantInt::get(IntTy, 0);
112   Value *One = ConstantInt::get(IntTy, 1);
113   Value *NegOne = ConstantInt::get(IntTy, -1);
114 
115   EXPECT_FALSE(
116       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_NE, APInt(BitWidth, 0))
117           .match(Zero));
118   EXPECT_TRUE(
119       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_NE, APInt(BitWidth, 0))
120           .match(One));
121   EXPECT_TRUE(
122       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_NE, APInt(BitWidth, 0))
123           .match(NegOne));
124 
125   EXPECT_TRUE(
126       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_NE, APInt(BitWidth, 1))
127           .match(Zero));
128   EXPECT_FALSE(
129       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_NE, APInt(BitWidth, 1))
130           .match(One));
131   EXPECT_TRUE(
132       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_NE, APInt(BitWidth, 1))
133           .match(NegOne));
134 
135   EXPECT_TRUE(
136       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_NE, APInt(BitWidth, -1))
137           .match(Zero));
138   EXPECT_TRUE(
139       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_NE, APInt(BitWidth, -1))
140           .match(One));
141   EXPECT_FALSE(
142       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_NE, APInt(BitWidth, -1))
143           .match(NegOne));
144 }
145 
146 TEST_F(PatternMatchTest, SpecificIntUGT) {
147   Type *IntTy = IRB.getInt32Ty();
148   unsigned BitWidth = IntTy->getScalarSizeInBits();
149 
150   Value *Zero = ConstantInt::get(IntTy, 0);
151   Value *One = ConstantInt::get(IntTy, 1);
152   Value *NegOne = ConstantInt::get(IntTy, -1);
153 
154   EXPECT_FALSE(
155       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_UGT, APInt(BitWidth, 0))
156           .match(Zero));
157   EXPECT_TRUE(
158       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_UGT, APInt(BitWidth, 0))
159           .match(One));
160   EXPECT_TRUE(
161       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_UGT, APInt(BitWidth, 0))
162           .match(NegOne));
163 
164   EXPECT_FALSE(
165       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_UGT, APInt(BitWidth, 1))
166           .match(Zero));
167   EXPECT_FALSE(
168       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_UGT, APInt(BitWidth, 1))
169           .match(One));
170   EXPECT_TRUE(
171       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_UGT, APInt(BitWidth, 1))
172           .match(NegOne));
173 
174   EXPECT_FALSE(
175       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_UGT, APInt(BitWidth, -1))
176           .match(Zero));
177   EXPECT_FALSE(
178       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_UGT, APInt(BitWidth, -1))
179           .match(One));
180   EXPECT_FALSE(
181       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_UGT, APInt(BitWidth, -1))
182           .match(NegOne));
183 }
184 
185 TEST_F(PatternMatchTest, SpecificIntUGE) {
186   Type *IntTy = IRB.getInt32Ty();
187   unsigned BitWidth = IntTy->getScalarSizeInBits();
188 
189   Value *Zero = ConstantInt::get(IntTy, 0);
190   Value *One = ConstantInt::get(IntTy, 1);
191   Value *NegOne = ConstantInt::get(IntTy, -1);
192 
193   EXPECT_TRUE(
194       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_UGE, APInt(BitWidth, 0))
195           .match(Zero));
196   EXPECT_TRUE(
197       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_UGE, APInt(BitWidth, 0))
198           .match(One));
199   EXPECT_TRUE(
200       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_UGE, APInt(BitWidth, 0))
201           .match(NegOne));
202 
203   EXPECT_FALSE(
204       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_UGE, APInt(BitWidth, 1))
205           .match(Zero));
206   EXPECT_TRUE(
207       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_UGE, APInt(BitWidth, 1))
208           .match(One));
209   EXPECT_TRUE(
210       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_UGE, APInt(BitWidth, 1))
211           .match(NegOne));
212 
213   EXPECT_FALSE(
214       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_UGE, APInt(BitWidth, -1))
215           .match(Zero));
216   EXPECT_FALSE(
217       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_UGE, APInt(BitWidth, -1))
218           .match(One));
219   EXPECT_TRUE(
220       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_UGE, APInt(BitWidth, -1))
221           .match(NegOne));
222 }
223 
224 TEST_F(PatternMatchTest, SpecificIntULT) {
225   Type *IntTy = IRB.getInt32Ty();
226   unsigned BitWidth = IntTy->getScalarSizeInBits();
227 
228   Value *Zero = ConstantInt::get(IntTy, 0);
229   Value *One = ConstantInt::get(IntTy, 1);
230   Value *NegOne = ConstantInt::get(IntTy, -1);
231 
232   EXPECT_FALSE(
233       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_ULT, APInt(BitWidth, 0))
234           .match(Zero));
235   EXPECT_FALSE(
236       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_ULT, APInt(BitWidth, 0))
237           .match(One));
238   EXPECT_FALSE(
239       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_ULT, APInt(BitWidth, 0))
240           .match(NegOne));
241 
242   EXPECT_TRUE(
243       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_ULT, APInt(BitWidth, 1))
244           .match(Zero));
245   EXPECT_FALSE(
246       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_ULT, APInt(BitWidth, 1))
247           .match(One));
248   EXPECT_FALSE(
249       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_ULT, APInt(BitWidth, 1))
250           .match(NegOne));
251 
252   EXPECT_TRUE(
253       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_ULT, APInt(BitWidth, -1))
254           .match(Zero));
255   EXPECT_TRUE(
256       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_ULT, APInt(BitWidth, -1))
257           .match(One));
258   EXPECT_FALSE(
259       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_ULT, APInt(BitWidth, -1))
260           .match(NegOne));
261 }
262 
263 TEST_F(PatternMatchTest, SpecificIntULE) {
264   Type *IntTy = IRB.getInt32Ty();
265   unsigned BitWidth = IntTy->getScalarSizeInBits();
266 
267   Value *Zero = ConstantInt::get(IntTy, 0);
268   Value *One = ConstantInt::get(IntTy, 1);
269   Value *NegOne = ConstantInt::get(IntTy, -1);
270 
271   EXPECT_TRUE(
272       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_ULE, APInt(BitWidth, 0))
273           .match(Zero));
274   EXPECT_FALSE(
275       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_ULE, APInt(BitWidth, 0))
276           .match(One));
277   EXPECT_FALSE(
278       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_ULE, APInt(BitWidth, 0))
279           .match(NegOne));
280 
281   EXPECT_TRUE(
282       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_ULE, APInt(BitWidth, 1))
283           .match(Zero));
284   EXPECT_TRUE(
285       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_ULE, APInt(BitWidth, 1))
286           .match(One));
287   EXPECT_FALSE(
288       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_ULE, APInt(BitWidth, 1))
289           .match(NegOne));
290 
291   EXPECT_TRUE(
292       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_ULE, APInt(BitWidth, -1))
293           .match(Zero));
294   EXPECT_TRUE(
295       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_ULE, APInt(BitWidth, -1))
296           .match(One));
297   EXPECT_TRUE(
298       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_ULE, APInt(BitWidth, -1))
299           .match(NegOne));
300 }
301 
302 TEST_F(PatternMatchTest, SpecificIntSGT) {
303   Type *IntTy = IRB.getInt32Ty();
304   unsigned BitWidth = IntTy->getScalarSizeInBits();
305 
306   Value *Zero = ConstantInt::get(IntTy, 0);
307   Value *One = ConstantInt::get(IntTy, 1);
308   Value *NegOne = ConstantInt::get(IntTy, -1);
309 
310   EXPECT_FALSE(
311       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SGT, APInt(BitWidth, 0))
312           .match(Zero));
313   EXPECT_TRUE(
314       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SGT, APInt(BitWidth, 0))
315           .match(One));
316   EXPECT_FALSE(
317       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SGT, APInt(BitWidth, 0))
318           .match(NegOne));
319 
320   EXPECT_FALSE(
321       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SGT, APInt(BitWidth, 1))
322           .match(Zero));
323   EXPECT_FALSE(
324       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SGT, APInt(BitWidth, 1))
325           .match(One));
326   EXPECT_FALSE(
327       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SGT, APInt(BitWidth, 1))
328           .match(NegOne));
329 
330   EXPECT_TRUE(
331       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SGT, APInt(BitWidth, -1))
332           .match(Zero));
333   EXPECT_TRUE(
334       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SGT, APInt(BitWidth, -1))
335           .match(One));
336   EXPECT_FALSE(
337       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SGT, APInt(BitWidth, -1))
338           .match(NegOne));
339 }
340 
341 TEST_F(PatternMatchTest, SpecificIntSGE) {
342   Type *IntTy = IRB.getInt32Ty();
343   unsigned BitWidth = IntTy->getScalarSizeInBits();
344 
345   Value *Zero = ConstantInt::get(IntTy, 0);
346   Value *One = ConstantInt::get(IntTy, 1);
347   Value *NegOne = ConstantInt::get(IntTy, -1);
348 
349   EXPECT_TRUE(
350       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SGE, APInt(BitWidth, 0))
351           .match(Zero));
352   EXPECT_TRUE(
353       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SGE, APInt(BitWidth, 0))
354           .match(One));
355   EXPECT_FALSE(
356       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SGE, APInt(BitWidth, 0))
357           .match(NegOne));
358 
359   EXPECT_FALSE(
360       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SGE, APInt(BitWidth, 1))
361           .match(Zero));
362   EXPECT_TRUE(
363       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SGE, APInt(BitWidth, 1))
364           .match(One));
365   EXPECT_FALSE(
366       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SGE, APInt(BitWidth, 1))
367           .match(NegOne));
368 
369   EXPECT_TRUE(
370       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SGE, APInt(BitWidth, -1))
371           .match(Zero));
372   EXPECT_TRUE(
373       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SGE, APInt(BitWidth, -1))
374           .match(One));
375   EXPECT_TRUE(
376       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SGE, APInt(BitWidth, -1))
377           .match(NegOne));
378 }
379 
380 TEST_F(PatternMatchTest, SpecificIntSLT) {
381   Type *IntTy = IRB.getInt32Ty();
382   unsigned BitWidth = IntTy->getScalarSizeInBits();
383 
384   Value *Zero = ConstantInt::get(IntTy, 0);
385   Value *One = ConstantInt::get(IntTy, 1);
386   Value *NegOne = ConstantInt::get(IntTy, -1);
387 
388   EXPECT_FALSE(
389       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SLT, APInt(BitWidth, 0))
390           .match(Zero));
391   EXPECT_FALSE(
392       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SLT, APInt(BitWidth, 0))
393           .match(One));
394   EXPECT_TRUE(
395       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SLT, APInt(BitWidth, 0))
396           .match(NegOne));
397 
398   EXPECT_TRUE(
399       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SLT, APInt(BitWidth, 1))
400           .match(Zero));
401   EXPECT_FALSE(
402       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SLT, APInt(BitWidth, 1))
403           .match(One));
404   EXPECT_TRUE(
405       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SLT, APInt(BitWidth, 1))
406           .match(NegOne));
407 
408   EXPECT_FALSE(
409       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SLT, APInt(BitWidth, -1))
410           .match(Zero));
411   EXPECT_FALSE(
412       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SLT, APInt(BitWidth, -1))
413           .match(One));
414   EXPECT_FALSE(
415       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SLT, APInt(BitWidth, -1))
416           .match(NegOne));
417 }
418 
419 TEST_F(PatternMatchTest, SpecificIntSLE) {
420   Type *IntTy = IRB.getInt32Ty();
421   unsigned BitWidth = IntTy->getScalarSizeInBits();
422 
423   Value *Zero = ConstantInt::get(IntTy, 0);
424   Value *One = ConstantInt::get(IntTy, 1);
425   Value *NegOne = ConstantInt::get(IntTy, -1);
426 
427   EXPECT_TRUE(
428       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SLE, APInt(BitWidth, 0))
429           .match(Zero));
430   EXPECT_FALSE(
431       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SLE, APInt(BitWidth, 0))
432           .match(One));
433   EXPECT_TRUE(
434       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SLE, APInt(BitWidth, 0))
435           .match(NegOne));
436 
437   EXPECT_TRUE(
438       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SLE, APInt(BitWidth, 1))
439           .match(Zero));
440   EXPECT_TRUE(
441       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SLE, APInt(BitWidth, 1))
442           .match(One));
443   EXPECT_TRUE(
444       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SLE, APInt(BitWidth, 1))
445           .match(NegOne));
446 
447   EXPECT_FALSE(
448       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SLE, APInt(BitWidth, -1))
449           .match(Zero));
450   EXPECT_FALSE(
451       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SLE, APInt(BitWidth, -1))
452           .match(One));
453   EXPECT_TRUE(
454       m_SpecificInt_ICMP(ICmpInst::Predicate::ICMP_SLE, APInt(BitWidth, -1))
455           .match(NegOne));
456 }
457 
458 TEST_F(PatternMatchTest, Unless) {
459   Value *X = IRB.CreateAdd(IRB.getInt32(1), IRB.getInt32(0));
460 
461   EXPECT_TRUE(m_Add(m_One(), m_Zero()).match(X));
462   EXPECT_FALSE(m_Add(m_Zero(), m_One()).match(X));
463 
464   EXPECT_FALSE(m_Unless(m_Add(m_One(), m_Zero())).match(X));
465   EXPECT_TRUE(m_Unless(m_Add(m_Zero(), m_One())).match(X));
466 
467   EXPECT_TRUE(m_c_Add(m_One(), m_Zero()).match(X));
468   EXPECT_TRUE(m_c_Add(m_Zero(), m_One()).match(X));
469 
470   EXPECT_FALSE(m_Unless(m_c_Add(m_One(), m_Zero())).match(X));
471   EXPECT_FALSE(m_Unless(m_c_Add(m_Zero(), m_One())).match(X));
472 }
473 
474 TEST_F(PatternMatchTest, ZExtSExtSelf) {
475   LLVMContext &Ctx = IRB.getContext();
476 
477   Value *One32 = IRB.getInt32(1);
478   Value *One64Z = IRB.CreateZExt(One32, IntegerType::getInt64Ty(Ctx));
479   Value *One64S = IRB.CreateSExt(One32, IntegerType::getInt64Ty(Ctx));
480 
481   EXPECT_TRUE(m_One().match(One32));
482   EXPECT_FALSE(m_One().match(One64Z));
483   EXPECT_FALSE(m_One().match(One64S));
484 
485   EXPECT_FALSE(m_ZExt(m_One()).match(One32));
486   EXPECT_TRUE(m_ZExt(m_One()).match(One64Z));
487   EXPECT_FALSE(m_ZExt(m_One()).match(One64S));
488 
489   EXPECT_FALSE(m_SExt(m_One()).match(One32));
490   EXPECT_FALSE(m_SExt(m_One()).match(One64Z));
491   EXPECT_TRUE(m_SExt(m_One()).match(One64S));
492 
493   EXPECT_TRUE(m_ZExtOrSelf(m_One()).match(One32));
494   EXPECT_TRUE(m_ZExtOrSelf(m_One()).match(One64Z));
495   EXPECT_FALSE(m_ZExtOrSelf(m_One()).match(One64S));
496 
497   EXPECT_TRUE(m_SExtOrSelf(m_One()).match(One32));
498   EXPECT_FALSE(m_SExtOrSelf(m_One()).match(One64Z));
499   EXPECT_TRUE(m_SExtOrSelf(m_One()).match(One64S));
500 
501   EXPECT_FALSE(m_ZExtOrSExt(m_One()).match(One32));
502   EXPECT_TRUE(m_ZExtOrSExt(m_One()).match(One64Z));
503   EXPECT_TRUE(m_ZExtOrSExt(m_One()).match(One64S));
504 
505   EXPECT_TRUE(m_ZExtOrSExtOrSelf(m_One()).match(One32));
506   EXPECT_TRUE(m_ZExtOrSExtOrSelf(m_One()).match(One64Z));
507   EXPECT_TRUE(m_ZExtOrSExtOrSelf(m_One()).match(One64S));
508 }
509 
510 TEST_F(PatternMatchTest, Power2) {
511   Value *C128 = IRB.getInt32(128);
512   Value *CNeg128 = ConstantExpr::getNeg(cast<Constant>(C128));
513 
514   EXPECT_TRUE(m_Power2().match(C128));
515   EXPECT_FALSE(m_Power2().match(CNeg128));
516 
517   EXPECT_FALSE(m_NegatedPower2().match(C128));
518   EXPECT_TRUE(m_NegatedPower2().match(CNeg128));
519 
520   Value *CIntMin = IRB.getInt64(APSInt::getSignedMinValue(64).getSExtValue());
521   Value *CNegIntMin = ConstantExpr::getNeg(cast<Constant>(CIntMin));
522 
523   EXPECT_TRUE(m_Power2().match(CIntMin));
524   EXPECT_TRUE(m_Power2().match(CNegIntMin));
525 
526   EXPECT_TRUE(m_NegatedPower2().match(CIntMin));
527   EXPECT_TRUE(m_NegatedPower2().match(CNegIntMin));
528 }
529 
530 TEST_F(PatternMatchTest, CommutativeDeferredValue) {
531   Value *X = IRB.getInt32(1);
532   Value *Y = IRB.getInt32(2);
533 
534   {
535     Value *tX = X;
536     EXPECT_TRUE(match(X, m_Deferred(tX)));
537     EXPECT_FALSE(match(Y, m_Deferred(tX)));
538   }
539   {
540     const Value *tX = X;
541     EXPECT_TRUE(match(X, m_Deferred(tX)));
542     EXPECT_FALSE(match(Y, m_Deferred(tX)));
543   }
544   {
545     Value *const tX = X;
546     EXPECT_TRUE(match(X, m_Deferred(tX)));
547     EXPECT_FALSE(match(Y, m_Deferred(tX)));
548   }
549   {
550     const Value *const tX = X;
551     EXPECT_TRUE(match(X, m_Deferred(tX)));
552     EXPECT_FALSE(match(Y, m_Deferred(tX)));
553   }
554 
555   {
556     Value *tX = nullptr;
557     EXPECT_TRUE(match(IRB.CreateAnd(X, X), m_And(m_Value(tX), m_Deferred(tX))));
558     EXPECT_EQ(tX, X);
559   }
560   {
561     Value *tX = nullptr;
562     EXPECT_FALSE(
563         match(IRB.CreateAnd(X, Y), m_c_And(m_Value(tX), m_Deferred(tX))));
564   }
565 
566   auto checkMatch = [X, Y](Value *Pattern) {
567     Value *tX = nullptr, *tY = nullptr;
568     EXPECT_TRUE(match(
569         Pattern, m_c_And(m_Value(tX), m_c_And(m_Deferred(tX), m_Value(tY)))));
570     EXPECT_EQ(tX, X);
571     EXPECT_EQ(tY, Y);
572   };
573 
574   checkMatch(IRB.CreateAnd(X, IRB.CreateAnd(X, Y)));
575   checkMatch(IRB.CreateAnd(X, IRB.CreateAnd(Y, X)));
576   checkMatch(IRB.CreateAnd(IRB.CreateAnd(X, Y), X));
577   checkMatch(IRB.CreateAnd(IRB.CreateAnd(Y, X), X));
578 }
579 
580 TEST_F(PatternMatchTest, FloatingPointOrderedMin) {
581   Type *FltTy = IRB.getFloatTy();
582   Value *L = ConstantFP::get(FltTy, 1.0);
583   Value *R = ConstantFP::get(FltTy, 2.0);
584   Value *MatchL, *MatchR;
585 
586   // Test OLT.
587   EXPECT_TRUE(m_OrdFMin(m_Value(MatchL), m_Value(MatchR))
588                   .match(IRB.CreateSelect(IRB.CreateFCmpOLT(L, R), L, R)));
589   EXPECT_EQ(L, MatchL);
590   EXPECT_EQ(R, MatchR);
591 
592   // Test OLE.
593   EXPECT_TRUE(m_OrdFMin(m_Value(MatchL), m_Value(MatchR))
594                   .match(IRB.CreateSelect(IRB.CreateFCmpOLE(L, R), L, R)));
595   EXPECT_EQ(L, MatchL);
596   EXPECT_EQ(R, MatchR);
597 
598   // Test no match on OGE.
599   EXPECT_FALSE(m_OrdFMin(m_Value(MatchL), m_Value(MatchR))
600                    .match(IRB.CreateSelect(IRB.CreateFCmpOGE(L, R), L, R)));
601 
602   // Test no match on OGT.
603   EXPECT_FALSE(m_OrdFMin(m_Value(MatchL), m_Value(MatchR))
604                    .match(IRB.CreateSelect(IRB.CreateFCmpOGT(L, R), L, R)));
605 
606   // Test inverted selects. Note, that this "inverts" the ordering, e.g.:
607   // %cmp = fcmp oge L, R
608   // %min = select %cmp R, L
609   // Given L == NaN
610   // the above is expanded to %cmp == false ==> %min = L
611   // which is true for UnordFMin, not OrdFMin, so test that:
612 
613   // [OU]GE with inverted select.
614   EXPECT_FALSE(m_OrdFMin(m_Value(MatchL), m_Value(MatchR))
615                   .match(IRB.CreateSelect(IRB.CreateFCmpOGE(L, R), R, L)));
616   EXPECT_TRUE(m_OrdFMin(m_Value(MatchL), m_Value(MatchR))
617                   .match(IRB.CreateSelect(IRB.CreateFCmpUGE(L, R), R, L)));
618   EXPECT_EQ(L, MatchL);
619   EXPECT_EQ(R, MatchR);
620 
621   // [OU]GT with inverted select.
622   EXPECT_FALSE(m_OrdFMin(m_Value(MatchL), m_Value(MatchR))
623                   .match(IRB.CreateSelect(IRB.CreateFCmpOGT(L, R), R, L)));
624   EXPECT_TRUE(m_OrdFMin(m_Value(MatchL), m_Value(MatchR))
625                   .match(IRB.CreateSelect(IRB.CreateFCmpUGT(L, R), R, L)));
626   EXPECT_EQ(L, MatchL);
627   EXPECT_EQ(R, MatchR);
628 }
629 
630 TEST_F(PatternMatchTest, FloatingPointOrderedMax) {
631   Type *FltTy = IRB.getFloatTy();
632   Value *L = ConstantFP::get(FltTy, 1.0);
633   Value *R = ConstantFP::get(FltTy, 2.0);
634   Value *MatchL, *MatchR;
635 
636   // Test OGT.
637   EXPECT_TRUE(m_OrdFMax(m_Value(MatchL), m_Value(MatchR))
638                   .match(IRB.CreateSelect(IRB.CreateFCmpOGT(L, R), L, R)));
639   EXPECT_EQ(L, MatchL);
640   EXPECT_EQ(R, MatchR);
641 
642   // Test OGE.
643   EXPECT_TRUE(m_OrdFMax(m_Value(MatchL), m_Value(MatchR))
644                   .match(IRB.CreateSelect(IRB.CreateFCmpOGE(L, R), L, R)));
645   EXPECT_EQ(L, MatchL);
646   EXPECT_EQ(R, MatchR);
647 
648   // Test no match on OLE.
649   EXPECT_FALSE(m_OrdFMax(m_Value(MatchL), m_Value(MatchR))
650                    .match(IRB.CreateSelect(IRB.CreateFCmpOLE(L, R), L, R)));
651 
652   // Test no match on OLT.
653   EXPECT_FALSE(m_OrdFMax(m_Value(MatchL), m_Value(MatchR))
654                    .match(IRB.CreateSelect(IRB.CreateFCmpOLT(L, R), L, R)));
655 
656 
657   // Test inverted selects. Note, that this "inverts" the ordering, e.g.:
658   // %cmp = fcmp ole L, R
659   // %max = select %cmp, R, L
660   // Given L == NaN,
661   // the above is expanded to %cmp == false ==> %max == L
662   // which is true for UnordFMax, not OrdFMax, so test that:
663 
664   // [OU]LE with inverted select.
665   EXPECT_FALSE(m_OrdFMax(m_Value(MatchL), m_Value(MatchR))
666                    .match(IRB.CreateSelect(IRB.CreateFCmpOLE(L, R), R, L)));
667   EXPECT_TRUE(m_OrdFMax(m_Value(MatchL), m_Value(MatchR))
668                   .match(IRB.CreateSelect(IRB.CreateFCmpULE(L, R), R, L)));
669   EXPECT_EQ(L, MatchL);
670   EXPECT_EQ(R, MatchR);
671 
672   // [OUT]LT with inverted select.
673   EXPECT_FALSE(m_OrdFMax(m_Value(MatchL), m_Value(MatchR))
674                    .match(IRB.CreateSelect(IRB.CreateFCmpOLT(L, R), R, L)));
675   EXPECT_TRUE(m_OrdFMax(m_Value(MatchL), m_Value(MatchR))
676                   .match(IRB.CreateSelect(IRB.CreateFCmpULT(L, R), R, L)));
677   EXPECT_EQ(L, MatchL);
678   EXPECT_EQ(R, MatchR);
679 }
680 
681 TEST_F(PatternMatchTest, FloatingPointUnorderedMin) {
682   Type *FltTy = IRB.getFloatTy();
683   Value *L = ConstantFP::get(FltTy, 1.0);
684   Value *R = ConstantFP::get(FltTy, 2.0);
685   Value *MatchL, *MatchR;
686 
687   // Test ULT.
688   EXPECT_TRUE(m_UnordFMin(m_Value(MatchL), m_Value(MatchR))
689                   .match(IRB.CreateSelect(IRB.CreateFCmpULT(L, R), L, R)));
690   EXPECT_EQ(L, MatchL);
691   EXPECT_EQ(R, MatchR);
692 
693   // Test ULE.
694   EXPECT_TRUE(m_UnordFMin(m_Value(MatchL), m_Value(MatchR))
695                   .match(IRB.CreateSelect(IRB.CreateFCmpULE(L, R), L, R)));
696   EXPECT_EQ(L, MatchL);
697   EXPECT_EQ(R, MatchR);
698 
699   // Test no match on UGE.
700   EXPECT_FALSE(m_UnordFMin(m_Value(MatchL), m_Value(MatchR))
701                    .match(IRB.CreateSelect(IRB.CreateFCmpUGE(L, R), L, R)));
702 
703   // Test no match on UGT.
704   EXPECT_FALSE(m_UnordFMin(m_Value(MatchL), m_Value(MatchR))
705                    .match(IRB.CreateSelect(IRB.CreateFCmpUGT(L, R), L, R)));
706 
707   // Test inverted selects. Note, that this "inverts" the ordering, e.g.:
708   // %cmp = fcmp uge L, R
709   // %min = select %cmp R, L
710   // Given L == NaN
711   // the above is expanded to %cmp == true ==> %min = R
712   // which is true for OrdFMin, not UnordFMin, so test that:
713 
714   // [UO]GE with inverted select.
715   EXPECT_FALSE(m_UnordFMin(m_Value(MatchL), m_Value(MatchR))
716                   .match(IRB.CreateSelect(IRB.CreateFCmpUGE(L, R), R, L)));
717   EXPECT_TRUE(m_UnordFMin(m_Value(MatchL), m_Value(MatchR))
718                   .match(IRB.CreateSelect(IRB.CreateFCmpOGE(L, R), R, L)));
719   EXPECT_EQ(L, MatchL);
720   EXPECT_EQ(R, MatchR);
721 
722   // [UO]GT with inverted select.
723   EXPECT_FALSE(m_UnordFMin(m_Value(MatchL), m_Value(MatchR))
724                   .match(IRB.CreateSelect(IRB.CreateFCmpUGT(L, R), R, L)));
725   EXPECT_TRUE(m_UnordFMin(m_Value(MatchL), m_Value(MatchR))
726                   .match(IRB.CreateSelect(IRB.CreateFCmpOGT(L, R), R, L)));
727   EXPECT_EQ(L, MatchL);
728   EXPECT_EQ(R, MatchR);
729 }
730 
731 TEST_F(PatternMatchTest, FloatingPointUnorderedMax) {
732   Type *FltTy = IRB.getFloatTy();
733   Value *L = ConstantFP::get(FltTy, 1.0);
734   Value *R = ConstantFP::get(FltTy, 2.0);
735   Value *MatchL, *MatchR;
736 
737   // Test UGT.
738   EXPECT_TRUE(m_UnordFMax(m_Value(MatchL), m_Value(MatchR))
739                   .match(IRB.CreateSelect(IRB.CreateFCmpUGT(L, R), L, R)));
740   EXPECT_EQ(L, MatchL);
741   EXPECT_EQ(R, MatchR);
742 
743   // Test UGE.
744   EXPECT_TRUE(m_UnordFMax(m_Value(MatchL), m_Value(MatchR))
745                   .match(IRB.CreateSelect(IRB.CreateFCmpUGE(L, R), L, R)));
746   EXPECT_EQ(L, MatchL);
747   EXPECT_EQ(R, MatchR);
748 
749   // Test no match on ULE.
750   EXPECT_FALSE(m_UnordFMax(m_Value(MatchL), m_Value(MatchR))
751                    .match(IRB.CreateSelect(IRB.CreateFCmpULE(L, R), L, R)));
752 
753   // Test no match on ULT.
754   EXPECT_FALSE(m_UnordFMax(m_Value(MatchL), m_Value(MatchR))
755                    .match(IRB.CreateSelect(IRB.CreateFCmpULT(L, R), L, R)));
756 
757   // Test inverted selects. Note, that this "inverts" the ordering, e.g.:
758   // %cmp = fcmp ule L, R
759   // %max = select %cmp R, L
760   // Given L == NaN
761   // the above is expanded to %cmp == true ==> %max = R
762   // which is true for OrdFMax, not UnordFMax, so test that:
763 
764   // [UO]LE with inverted select.
765   EXPECT_FALSE(m_UnordFMax(m_Value(MatchL), m_Value(MatchR))
766                   .match(IRB.CreateSelect(IRB.CreateFCmpULE(L, R), R, L)));
767   EXPECT_TRUE(m_UnordFMax(m_Value(MatchL), m_Value(MatchR))
768                   .match(IRB.CreateSelect(IRB.CreateFCmpOLE(L, R), R, L)));
769   EXPECT_EQ(L, MatchL);
770   EXPECT_EQ(R, MatchR);
771 
772   // [UO]LT with inverted select.
773   EXPECT_FALSE(m_UnordFMax(m_Value(MatchL), m_Value(MatchR))
774                   .match(IRB.CreateSelect(IRB.CreateFCmpULT(L, R), R, L)));
775   EXPECT_TRUE(m_UnordFMax(m_Value(MatchL), m_Value(MatchR))
776                   .match(IRB.CreateSelect(IRB.CreateFCmpOLT(L, R), R, L)));
777   EXPECT_EQ(L, MatchL);
778   EXPECT_EQ(R, MatchR);
779 }
780 
781 TEST_F(PatternMatchTest, OverflowingBinOps) {
782   Value *L = IRB.getInt32(1);
783   Value *R = IRB.getInt32(2);
784   Value *MatchL, *MatchR;
785 
786   EXPECT_TRUE(
787       m_NSWAdd(m_Value(MatchL), m_Value(MatchR)).match(IRB.CreateNSWAdd(L, R)));
788   EXPECT_EQ(L, MatchL);
789   EXPECT_EQ(R, MatchR);
790   MatchL = MatchR = nullptr;
791   EXPECT_TRUE(
792       m_NSWSub(m_Value(MatchL), m_Value(MatchR)).match(IRB.CreateNSWSub(L, R)));
793   EXPECT_EQ(L, MatchL);
794   EXPECT_EQ(R, MatchR);
795   MatchL = MatchR = nullptr;
796   EXPECT_TRUE(
797       m_NSWMul(m_Value(MatchL), m_Value(MatchR)).match(IRB.CreateNSWMul(L, R)));
798   EXPECT_EQ(L, MatchL);
799   EXPECT_EQ(R, MatchR);
800   MatchL = MatchR = nullptr;
801   EXPECT_TRUE(m_NSWShl(m_Value(MatchL), m_Value(MatchR)).match(
802       IRB.CreateShl(L, R, "", /* NUW */ false, /* NSW */ true)));
803   EXPECT_EQ(L, MatchL);
804   EXPECT_EQ(R, MatchR);
805 
806   EXPECT_TRUE(
807       m_NUWAdd(m_Value(MatchL), m_Value(MatchR)).match(IRB.CreateNUWAdd(L, R)));
808   EXPECT_EQ(L, MatchL);
809   EXPECT_EQ(R, MatchR);
810   MatchL = MatchR = nullptr;
811   EXPECT_TRUE(
812       m_NUWSub(m_Value(MatchL), m_Value(MatchR)).match(IRB.CreateNUWSub(L, R)));
813   EXPECT_EQ(L, MatchL);
814   EXPECT_EQ(R, MatchR);
815   MatchL = MatchR = nullptr;
816   EXPECT_TRUE(
817       m_NUWMul(m_Value(MatchL), m_Value(MatchR)).match(IRB.CreateNUWMul(L, R)));
818   EXPECT_EQ(L, MatchL);
819   EXPECT_EQ(R, MatchR);
820   MatchL = MatchR = nullptr;
821   EXPECT_TRUE(m_NUWShl(m_Value(MatchL), m_Value(MatchR)).match(
822       IRB.CreateShl(L, R, "", /* NUW */ true, /* NSW */ false)));
823   EXPECT_EQ(L, MatchL);
824   EXPECT_EQ(R, MatchR);
825 
826   EXPECT_FALSE(m_NSWAdd(m_Value(), m_Value()).match(IRB.CreateAdd(L, R)));
827   EXPECT_FALSE(m_NSWAdd(m_Value(), m_Value()).match(IRB.CreateNUWAdd(L, R)));
828   EXPECT_FALSE(m_NSWAdd(m_Value(), m_Value()).match(IRB.CreateNSWSub(L, R)));
829   EXPECT_FALSE(m_NSWSub(m_Value(), m_Value()).match(IRB.CreateSub(L, R)));
830   EXPECT_FALSE(m_NSWSub(m_Value(), m_Value()).match(IRB.CreateNUWSub(L, R)));
831   EXPECT_FALSE(m_NSWSub(m_Value(), m_Value()).match(IRB.CreateNSWAdd(L, R)));
832   EXPECT_FALSE(m_NSWMul(m_Value(), m_Value()).match(IRB.CreateMul(L, R)));
833   EXPECT_FALSE(m_NSWMul(m_Value(), m_Value()).match(IRB.CreateNUWMul(L, R)));
834   EXPECT_FALSE(m_NSWMul(m_Value(), m_Value()).match(IRB.CreateNSWAdd(L, R)));
835   EXPECT_FALSE(m_NSWShl(m_Value(), m_Value()).match(IRB.CreateShl(L, R)));
836   EXPECT_FALSE(m_NSWShl(m_Value(), m_Value()).match(
837       IRB.CreateShl(L, R, "", /* NUW */ true, /* NSW */ false)));
838   EXPECT_FALSE(m_NSWShl(m_Value(), m_Value()).match(IRB.CreateNSWAdd(L, R)));
839 
840   EXPECT_FALSE(m_NUWAdd(m_Value(), m_Value()).match(IRB.CreateAdd(L, R)));
841   EXPECT_FALSE(m_NUWAdd(m_Value(), m_Value()).match(IRB.CreateNSWAdd(L, R)));
842   EXPECT_FALSE(m_NUWAdd(m_Value(), m_Value()).match(IRB.CreateNUWSub(L, R)));
843   EXPECT_FALSE(m_NUWSub(m_Value(), m_Value()).match(IRB.CreateSub(L, R)));
844   EXPECT_FALSE(m_NUWSub(m_Value(), m_Value()).match(IRB.CreateNSWSub(L, R)));
845   EXPECT_FALSE(m_NUWSub(m_Value(), m_Value()).match(IRB.CreateNUWAdd(L, R)));
846   EXPECT_FALSE(m_NUWMul(m_Value(), m_Value()).match(IRB.CreateMul(L, R)));
847   EXPECT_FALSE(m_NUWMul(m_Value(), m_Value()).match(IRB.CreateNSWMul(L, R)));
848   EXPECT_FALSE(m_NUWMul(m_Value(), m_Value()).match(IRB.CreateNUWAdd(L, R)));
849   EXPECT_FALSE(m_NUWShl(m_Value(), m_Value()).match(IRB.CreateShl(L, R)));
850   EXPECT_FALSE(m_NUWShl(m_Value(), m_Value()).match(
851       IRB.CreateShl(L, R, "", /* NUW */ false, /* NSW */ true)));
852   EXPECT_FALSE(m_NUWShl(m_Value(), m_Value()).match(IRB.CreateNUWAdd(L, R)));
853 }
854 
855 TEST_F(PatternMatchTest, LoadStoreOps) {
856   // Create this load/store sequence:
857   //
858   //  %p = alloca i32*
859   //  %0 = load i32*, i32** %p
860   //  store i32 42, i32* %0
861 
862   Value *Alloca = IRB.CreateAlloca(IRB.getInt32Ty());
863   Value *LoadInst = IRB.CreateLoad(IRB.getInt32Ty(), Alloca);
864   Value *FourtyTwo = IRB.getInt32(42);
865   Value *StoreInst = IRB.CreateStore(FourtyTwo, Alloca);
866   Value *MatchLoad, *MatchStoreVal, *MatchStorePointer;
867 
868   EXPECT_TRUE(m_Load(m_Value(MatchLoad)).match(LoadInst));
869   EXPECT_EQ(Alloca, MatchLoad);
870 
871   EXPECT_TRUE(m_Load(m_Specific(Alloca)).match(LoadInst));
872 
873   EXPECT_FALSE(m_Load(m_Value(MatchLoad)).match(Alloca));
874 
875   EXPECT_TRUE(m_Store(m_Value(MatchStoreVal), m_Value(MatchStorePointer))
876                 .match(StoreInst));
877   EXPECT_EQ(FourtyTwo, MatchStoreVal);
878   EXPECT_EQ(Alloca, MatchStorePointer);
879 
880   EXPECT_FALSE(m_Store(m_Value(MatchStoreVal), m_Value(MatchStorePointer))
881                 .match(Alloca));
882 
883   EXPECT_TRUE(m_Store(m_SpecificInt(42), m_Specific(Alloca))
884                 .match(StoreInst));
885   EXPECT_FALSE(m_Store(m_SpecificInt(42), m_Specific(FourtyTwo))
886                 .match(StoreInst));
887   EXPECT_FALSE(m_Store(m_SpecificInt(43), m_Specific(Alloca))
888                 .match(StoreInst));
889 }
890 
891 TEST_F(PatternMatchTest, VectorOps) {
892   // Build up small tree of vector operations
893   //
894   //   Val = 0 + 1
895   //   Val2 = Val + 3
896   //   VI1 = insertelement <2 x i8> undef, i8 1, i32 0 = <1, undef>
897   //   VI2 = insertelement <2 x i8> %VI1, i8 %Val2, i8 %Val = <1, 4>
898   //   VI3 = insertelement <2 x i8> %VI1, i8 %Val2, i32 1 = <1, 4>
899   //   VI4 = insertelement <2 x i8> %VI1, i8 2, i8 %Val = <1, 2>
900   //
901   //   SI1 = shufflevector <2 x i8> %VI1, <2 x i8> undef, zeroinitializer
902   //   SI2 = shufflevector <2 x i8> %VI3, <2 x i8> %VI4, <2 x i8> <i8 0, i8 2>
903   //   SI3 = shufflevector <2 x i8> %VI3, <2 x i8> undef, zeroinitializer
904   //   SI4 = shufflevector <2 x i8> %VI4, <2 x i8> undef, zeroinitializer
905   //
906   //   SP1 = VectorSplat(2, i8 2)
907   //   SP2 = VectorSplat(2, i8 %Val)
908   Type *VecTy = VectorType::get(IRB.getInt8Ty(), 2);
909   Type *i32 = IRB.getInt32Ty();
910   Type *i32VecTy = VectorType::get(i32, 2);
911 
912   Value *Val = IRB.CreateAdd(IRB.getInt8(0), IRB.getInt8(1));
913   Value *Val2 = IRB.CreateAdd(Val, IRB.getInt8(3));
914 
915   SmallVector<Constant *, 2> VecElemIdxs;
916   VecElemIdxs.push_back(ConstantInt::get(i32, 0));
917   VecElemIdxs.push_back(ConstantInt::get(i32, 2));
918   auto *IdxVec = ConstantVector::get(VecElemIdxs);
919 
920   Value *UndefVec = UndefValue::get(VecTy);
921   Value *VI1 = IRB.CreateInsertElement(UndefVec, IRB.getInt8(1), (uint64_t)0);
922   Value *VI2 = IRB.CreateInsertElement(VI1, Val2, Val);
923   Value *VI3 = IRB.CreateInsertElement(VI1, Val2, (uint64_t)1);
924   Value *VI4 = IRB.CreateInsertElement(VI1, IRB.getInt8(2), Val);
925 
926   Value *EX1 = IRB.CreateExtractElement(VI4, Val);
927   Value *EX2 = IRB.CreateExtractElement(VI4, (uint64_t)0);
928   Value *EX3 = IRB.CreateExtractElement(IdxVec, (uint64_t)1);
929 
930   Value *Zero = ConstantAggregateZero::get(i32VecTy);
931   Value *SI1 = IRB.CreateShuffleVector(VI1, UndefVec, Zero);
932   Value *SI2 = IRB.CreateShuffleVector(VI3, VI4, IdxVec);
933   Value *SI3 = IRB.CreateShuffleVector(VI3, UndefVec, Zero);
934   Value *SI4 = IRB.CreateShuffleVector(VI4, UndefVec, Zero);
935 
936   Value *SP1 = IRB.CreateVectorSplat(2, IRB.getInt8(2));
937   Value *SP2 = IRB.CreateVectorSplat(2, Val);
938 
939   Value *A = nullptr, *B = nullptr, *C = nullptr;
940 
941   // Test matching insertelement
942   EXPECT_TRUE(match(VI1, m_InsertElement(m_Value(), m_Value(), m_Value())));
943   EXPECT_TRUE(
944       match(VI1, m_InsertElement(m_Undef(), m_ConstantInt(), m_ConstantInt())));
945   EXPECT_TRUE(
946       match(VI1, m_InsertElement(m_Undef(), m_ConstantInt(), m_Zero())));
947   EXPECT_TRUE(
948       match(VI1, m_InsertElement(m_Undef(), m_SpecificInt(1), m_Zero())));
949   EXPECT_TRUE(match(VI2, m_InsertElement(m_Value(), m_Value(), m_Value())));
950   EXPECT_FALSE(
951       match(VI2, m_InsertElement(m_Value(), m_Value(), m_ConstantInt())));
952   EXPECT_FALSE(
953       match(VI2, m_InsertElement(m_Value(), m_ConstantInt(), m_Value())));
954   EXPECT_FALSE(match(VI2, m_InsertElement(m_Constant(), m_Value(), m_Value())));
955   EXPECT_TRUE(match(VI3, m_InsertElement(m_Value(A), m_Value(B), m_Value(C))));
956   EXPECT_TRUE(A == VI1);
957   EXPECT_TRUE(B == Val2);
958   EXPECT_TRUE(isa<ConstantInt>(C));
959   A = B = C = nullptr; // reset
960 
961   // Test matching extractelement
962   EXPECT_TRUE(match(EX1, m_ExtractElement(m_Value(A), m_Value(B))));
963   EXPECT_TRUE(A == VI4);
964   EXPECT_TRUE(B == Val);
965   A = B = C = nullptr; // reset
966   EXPECT_FALSE(match(EX1, m_ExtractElement(m_Value(), m_ConstantInt())));
967   EXPECT_TRUE(match(EX2, m_ExtractElement(m_Value(), m_ConstantInt())));
968   EXPECT_TRUE(match(EX3, m_ExtractElement(m_Constant(), m_ConstantInt())));
969 
970   // Test matching shufflevector
971   EXPECT_TRUE(match(SI1, m_ShuffleVector(m_Value(), m_Undef(), m_Zero())));
972   EXPECT_TRUE(match(SI2, m_ShuffleVector(m_Value(A), m_Value(B), m_Value(C))));
973   EXPECT_TRUE(A == VI3);
974   EXPECT_TRUE(B == VI4);
975   EXPECT_TRUE(C == IdxVec);
976   A = B = C = nullptr; // reset
977 
978   // Test matching the vector splat pattern
979   EXPECT_TRUE(match(
980       SI1,
981       m_ShuffleVector(m_InsertElement(m_Undef(), m_SpecificInt(1), m_Zero()),
982                       m_Undef(), m_Zero())));
983   EXPECT_FALSE(match(
984       SI3, m_ShuffleVector(m_InsertElement(m_Undef(), m_Value(), m_Zero()),
985                            m_Undef(), m_Zero())));
986   EXPECT_FALSE(match(
987       SI4, m_ShuffleVector(m_InsertElement(m_Undef(), m_Value(), m_Zero()),
988                            m_Undef(), m_Zero())));
989   EXPECT_TRUE(match(
990       SP1,
991       m_ShuffleVector(m_InsertElement(m_Undef(), m_SpecificInt(2), m_Zero()),
992                       m_Undef(), m_Zero())));
993   EXPECT_TRUE(match(
994       SP2, m_ShuffleVector(m_InsertElement(m_Undef(), m_Value(A), m_Zero()),
995                            m_Undef(), m_Zero())));
996   EXPECT_TRUE(A == Val);
997 }
998 
999 TEST_F(PatternMatchTest, VectorUndefInt) {
1000   Type *ScalarTy = IRB.getInt8Ty();
1001   Type *VectorTy = VectorType::get(ScalarTy, 4);
1002   Constant *ScalarUndef = UndefValue::get(ScalarTy);
1003   Constant *VectorUndef = UndefValue::get(VectorTy);
1004   Constant *ScalarZero = Constant::getNullValue(ScalarTy);
1005   Constant *VectorZero = Constant::getNullValue(VectorTy);
1006 
1007   SmallVector<Constant *, 4> Elems;
1008   Elems.push_back(ScalarUndef);
1009   Elems.push_back(ScalarZero);
1010   Elems.push_back(ScalarUndef);
1011   Elems.push_back(ScalarZero);
1012   Constant *VectorZeroUndef = ConstantVector::get(Elems);
1013 
1014   EXPECT_TRUE(match(ScalarUndef, m_Undef()));
1015   EXPECT_TRUE(match(VectorUndef, m_Undef()));
1016   EXPECT_FALSE(match(ScalarZero, m_Undef()));
1017   EXPECT_FALSE(match(VectorZero, m_Undef()));
1018   EXPECT_FALSE(match(VectorZeroUndef, m_Undef()));
1019 
1020   EXPECT_FALSE(match(ScalarUndef, m_Zero()));
1021   EXPECT_FALSE(match(VectorUndef, m_Zero()));
1022   EXPECT_TRUE(match(ScalarZero, m_Zero()));
1023   EXPECT_TRUE(match(VectorZero, m_Zero()));
1024   EXPECT_TRUE(match(VectorZeroUndef, m_Zero()));
1025 }
1026 
1027 TEST_F(PatternMatchTest, VectorUndefFloat) {
1028   Type *ScalarTy = IRB.getFloatTy();
1029   Type *VectorTy = VectorType::get(ScalarTy, 4);
1030   Constant *ScalarUndef = UndefValue::get(ScalarTy);
1031   Constant *VectorUndef = UndefValue::get(VectorTy);
1032   Constant *ScalarZero = Constant::getNullValue(ScalarTy);
1033   Constant *VectorZero = Constant::getNullValue(VectorTy);
1034 
1035   SmallVector<Constant *, 4> Elems;
1036   Elems.push_back(ScalarUndef);
1037   Elems.push_back(ScalarZero);
1038   Elems.push_back(ScalarUndef);
1039   Elems.push_back(ScalarZero);
1040   Constant *VectorZeroUndef = ConstantVector::get(Elems);
1041 
1042   EXPECT_TRUE(match(ScalarUndef, m_Undef()));
1043   EXPECT_TRUE(match(VectorUndef, m_Undef()));
1044   EXPECT_FALSE(match(ScalarZero, m_Undef()));
1045   EXPECT_FALSE(match(VectorZero, m_Undef()));
1046   EXPECT_FALSE(match(VectorZeroUndef, m_Undef()));
1047 
1048   EXPECT_FALSE(match(ScalarUndef, m_AnyZeroFP()));
1049   EXPECT_FALSE(match(VectorUndef, m_AnyZeroFP()));
1050   EXPECT_TRUE(match(ScalarZero, m_AnyZeroFP()));
1051   EXPECT_TRUE(match(VectorZero, m_AnyZeroFP()));
1052   EXPECT_TRUE(match(VectorZeroUndef, m_AnyZeroFP()));
1053 }
1054 
1055 TEST_F(PatternMatchTest, FloatingPointFNeg) {
1056   Type *FltTy = IRB.getFloatTy();
1057   Value *One = ConstantFP::get(FltTy, 1.0);
1058   Value *Z = ConstantFP::get(FltTy, 0.0);
1059   Value *NZ = ConstantFP::get(FltTy, -0.0);
1060   Value *V = IRB.CreateFNeg(One);
1061   Value *V1 = IRB.CreateFSub(NZ, One);
1062   Value *V2 = IRB.CreateFSub(Z, One);
1063   Value *V3 = IRB.CreateFAdd(NZ, One);
1064   Value *Match;
1065 
1066   // Test FNeg(1.0)
1067   EXPECT_TRUE(match(V, m_FNeg(m_Value(Match))));
1068   EXPECT_EQ(One, Match);
1069 
1070   // Test FSub(-0.0, 1.0)
1071   EXPECT_TRUE(match(V1, m_FNeg(m_Value(Match))));
1072   EXPECT_EQ(One, Match);
1073 
1074   // Test FSub(0.0, 1.0)
1075   EXPECT_FALSE(match(V2, m_FNeg(m_Value(Match))));
1076   cast<Instruction>(V2)->setHasNoSignedZeros(true);
1077   EXPECT_TRUE(match(V2, m_FNeg(m_Value(Match))));
1078   EXPECT_EQ(One, Match);
1079 
1080   // Test FAdd(-0.0, 1.0)
1081   EXPECT_FALSE(match(V3, m_FNeg(m_Value(Match))));
1082 }
1083 
1084 TEST_F(PatternMatchTest, CondBranchTest) {
1085   BasicBlock *TrueBB = BasicBlock::Create(Ctx, "TrueBB", F);
1086   BasicBlock *FalseBB = BasicBlock::Create(Ctx, "FalseBB", F);
1087   Value *Br1 = IRB.CreateCondBr(IRB.getTrue(), TrueBB, FalseBB);
1088 
1089   EXPECT_TRUE(match(Br1, m_Br(m_Value(), m_BasicBlock(), m_BasicBlock())));
1090 
1091   BasicBlock *A, *B;
1092   EXPECT_TRUE(match(Br1, m_Br(m_Value(), m_BasicBlock(A), m_BasicBlock(B))));
1093   EXPECT_EQ(TrueBB, A);
1094   EXPECT_EQ(FalseBB, B);
1095 
1096   EXPECT_FALSE(
1097       match(Br1, m_Br(m_Value(), m_SpecificBB(FalseBB), m_BasicBlock())));
1098   EXPECT_FALSE(
1099       match(Br1, m_Br(m_Value(), m_BasicBlock(), m_SpecificBB(TrueBB))));
1100   EXPECT_FALSE(
1101       match(Br1, m_Br(m_Value(), m_SpecificBB(FalseBB), m_BasicBlock(TrueBB))));
1102   EXPECT_TRUE(
1103       match(Br1, m_Br(m_Value(), m_SpecificBB(TrueBB), m_BasicBlock(FalseBB))));
1104 
1105   // Check we can use m_Deferred with branches.
1106   EXPECT_FALSE(match(Br1, m_Br(m_Value(), m_BasicBlock(A), m_Deferred(A))));
1107   Value *Br2 = IRB.CreateCondBr(IRB.getTrue(), TrueBB, TrueBB);
1108   A = nullptr;
1109   EXPECT_TRUE(match(Br2, m_Br(m_Value(), m_BasicBlock(A), m_Deferred(A))));
1110 }
1111 
1112 template <typename T> struct MutableConstTest : PatternMatchTest { };
1113 
1114 typedef ::testing::Types<std::tuple<Value*, Instruction*>,
1115                          std::tuple<const Value*, const Instruction *>>
1116     MutableConstTestTypes;
1117 TYPED_TEST_CASE(MutableConstTest, MutableConstTestTypes);
1118 
1119 TYPED_TEST(MutableConstTest, ICmp) {
1120   auto &IRB = PatternMatchTest::IRB;
1121 
1122   typedef typename std::tuple_element<0, TypeParam>::type ValueType;
1123   typedef typename std::tuple_element<1, TypeParam>::type InstructionType;
1124 
1125   Value *L = IRB.getInt32(1);
1126   Value *R = IRB.getInt32(2);
1127   ICmpInst::Predicate Pred = ICmpInst::ICMP_UGT;
1128 
1129   ValueType MatchL;
1130   ValueType MatchR;
1131   ICmpInst::Predicate MatchPred;
1132 
1133   EXPECT_TRUE(m_ICmp(MatchPred, m_Value(MatchL), m_Value(MatchR))
1134               .match((InstructionType)IRB.CreateICmp(Pred, L, R)));
1135   EXPECT_EQ(L, MatchL);
1136   EXPECT_EQ(R, MatchR);
1137 }
1138 
1139 } // anonymous namespace.
1140