1 //===- PatternMatch.h - Match on the LLVM IR --------------------*- C++ -*-===//
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 // This file provides a simple and efficient mechanism for performing general
10 // tree-based pattern matches on the LLVM IR. The power of these routines is
11 // that it allows you to write concise patterns that are expressive and easy to
12 // understand. The other major advantage of this is that it allows you to
13 // trivially capture/bind elements in the pattern to variables. For example,
14 // you can do something like this:
15 //
16 // Value *Exp = ...
17 // Value *X, *Y; ConstantInt *C1, *C2; // (X & C1) | (Y & C2)
18 // if (match(Exp, m_Or(m_And(m_Value(X), m_ConstantInt(C1)),
19 // m_And(m_Value(Y), m_ConstantInt(C2))))) {
20 // ... Pattern is matched and variables are bound ...
21 // }
22 //
23 // This is primarily useful to things like the instruction combiner, but can
24 // also be useful for static analysis tools or code generators.
25 //
26 //===----------------------------------------------------------------------===//
27
28 #ifndef LLVM_IR_PATTERNMATCH_H
29 #define LLVM_IR_PATTERNMATCH_H
30
31 #include "llvm/ADT/APFloat.h"
32 #include "llvm/ADT/APInt.h"
33 #include "llvm/IR/Constant.h"
34 #include "llvm/IR/Constants.h"
35 #include "llvm/IR/DataLayout.h"
36 #include "llvm/IR/InstrTypes.h"
37 #include "llvm/IR/Instruction.h"
38 #include "llvm/IR/Instructions.h"
39 #include "llvm/IR/IntrinsicInst.h"
40 #include "llvm/IR/Intrinsics.h"
41 #include "llvm/IR/Operator.h"
42 #include "llvm/IR/Value.h"
43 #include "llvm/Support/Casting.h"
44 #include <cstdint>
45
46 namespace llvm {
47 namespace PatternMatch {
48
match(Val * V,const Pattern & P)49 template <typename Val, typename Pattern> bool match(Val *V, const Pattern &P) {
50 return const_cast<Pattern &>(P).match(V);
51 }
52
match(ArrayRef<int> Mask,const Pattern & P)53 template <typename Pattern> bool match(ArrayRef<int> Mask, const Pattern &P) {
54 return const_cast<Pattern &>(P).match(Mask);
55 }
56
57 template <typename SubPattern_t> struct OneUse_match {
58 SubPattern_t SubPattern;
59
OneUse_matchOneUse_match60 OneUse_match(const SubPattern_t &SP) : SubPattern(SP) {}
61
matchOneUse_match62 template <typename OpTy> bool match(OpTy *V) {
63 return V->hasOneUse() && SubPattern.match(V);
64 }
65 };
66
m_OneUse(const T & SubPattern)67 template <typename T> inline OneUse_match<T> m_OneUse(const T &SubPattern) {
68 return SubPattern;
69 }
70
71 template <typename Class> struct class_match {
matchclass_match72 template <typename ITy> bool match(ITy *V) { return isa<Class>(V); }
73 };
74
75 /// Match an arbitrary value and ignore it.
m_Value()76 inline class_match<Value> m_Value() { return class_match<Value>(); }
77
78 /// Match an arbitrary unary operation and ignore it.
m_UnOp()79 inline class_match<UnaryOperator> m_UnOp() {
80 return class_match<UnaryOperator>();
81 }
82
83 /// Match an arbitrary binary operation and ignore it.
m_BinOp()84 inline class_match<BinaryOperator> m_BinOp() {
85 return class_match<BinaryOperator>();
86 }
87
88 /// Matches any compare instruction and ignore it.
m_Cmp()89 inline class_match<CmpInst> m_Cmp() { return class_match<CmpInst>(); }
90
91 /// Match an arbitrary undef constant.
m_Undef()92 inline class_match<UndefValue> m_Undef() { return class_match<UndefValue>(); }
93
94 /// Match an arbitrary poison constant.
m_Poison()95 inline class_match<PoisonValue> m_Poison() { return class_match<PoisonValue>(); }
96
97 /// Match an arbitrary Constant and ignore it.
m_Constant()98 inline class_match<Constant> m_Constant() { return class_match<Constant>(); }
99
100 /// Match an arbitrary ConstantInt and ignore it.
m_ConstantInt()101 inline class_match<ConstantInt> m_ConstantInt() {
102 return class_match<ConstantInt>();
103 }
104
105 /// Match an arbitrary ConstantFP and ignore it.
m_ConstantFP()106 inline class_match<ConstantFP> m_ConstantFP() {
107 return class_match<ConstantFP>();
108 }
109
110 /// Match an arbitrary ConstantExpr and ignore it.
m_ConstantExpr()111 inline class_match<ConstantExpr> m_ConstantExpr() {
112 return class_match<ConstantExpr>();
113 }
114
115 /// Match an arbitrary basic block value and ignore it.
m_BasicBlock()116 inline class_match<BasicBlock> m_BasicBlock() {
117 return class_match<BasicBlock>();
118 }
119
120 /// Inverting matcher
121 template <typename Ty> struct match_unless {
122 Ty M;
123
match_unlessmatch_unless124 match_unless(const Ty &Matcher) : M(Matcher) {}
125
matchmatch_unless126 template <typename ITy> bool match(ITy *V) { return !M.match(V); }
127 };
128
129 /// Match if the inner matcher does *NOT* match.
m_Unless(const Ty & M)130 template <typename Ty> inline match_unless<Ty> m_Unless(const Ty &M) {
131 return match_unless<Ty>(M);
132 }
133
134 /// Matching combinators
135 template <typename LTy, typename RTy> struct match_combine_or {
136 LTy L;
137 RTy R;
138
match_combine_ormatch_combine_or139 match_combine_or(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
140
matchmatch_combine_or141 template <typename ITy> bool match(ITy *V) {
142 if (L.match(V))
143 return true;
144 if (R.match(V))
145 return true;
146 return false;
147 }
148 };
149
150 template <typename LTy, typename RTy> struct match_combine_and {
151 LTy L;
152 RTy R;
153
match_combine_andmatch_combine_and154 match_combine_and(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
155
matchmatch_combine_and156 template <typename ITy> bool match(ITy *V) {
157 if (L.match(V))
158 if (R.match(V))
159 return true;
160 return false;
161 }
162 };
163
164 /// Combine two pattern matchers matching L || R
165 template <typename LTy, typename RTy>
m_CombineOr(const LTy & L,const RTy & R)166 inline match_combine_or<LTy, RTy> m_CombineOr(const LTy &L, const RTy &R) {
167 return match_combine_or<LTy, RTy>(L, R);
168 }
169
170 /// Combine two pattern matchers matching L && R
171 template <typename LTy, typename RTy>
m_CombineAnd(const LTy & L,const RTy & R)172 inline match_combine_and<LTy, RTy> m_CombineAnd(const LTy &L, const RTy &R) {
173 return match_combine_and<LTy, RTy>(L, R);
174 }
175
176 struct apint_match {
177 const APInt *&Res;
178 bool AllowUndef;
179
apint_matchapint_match180 apint_match(const APInt *&Res, bool AllowUndef)
181 : Res(Res), AllowUndef(AllowUndef) {}
182
matchapint_match183 template <typename ITy> bool match(ITy *V) {
184 if (auto *CI = dyn_cast<ConstantInt>(V)) {
185 Res = &CI->getValue();
186 return true;
187 }
188 if (V->getType()->isVectorTy())
189 if (const auto *C = dyn_cast<Constant>(V))
190 if (auto *CI = dyn_cast_or_null<ConstantInt>(
191 C->getSplatValue(AllowUndef))) {
192 Res = &CI->getValue();
193 return true;
194 }
195 return false;
196 }
197 };
198 // Either constexpr if or renaming ConstantFP::getValueAPF to
199 // ConstantFP::getValue is needed to do it via single template
200 // function for both apint/apfloat.
201 struct apfloat_match {
202 const APFloat *&Res;
203 bool AllowUndef;
204
apfloat_matchapfloat_match205 apfloat_match(const APFloat *&Res, bool AllowUndef)
206 : Res(Res), AllowUndef(AllowUndef) {}
207
matchapfloat_match208 template <typename ITy> bool match(ITy *V) {
209 if (auto *CI = dyn_cast<ConstantFP>(V)) {
210 Res = &CI->getValueAPF();
211 return true;
212 }
213 if (V->getType()->isVectorTy())
214 if (const auto *C = dyn_cast<Constant>(V))
215 if (auto *CI = dyn_cast_or_null<ConstantFP>(
216 C->getSplatValue(AllowUndef))) {
217 Res = &CI->getValueAPF();
218 return true;
219 }
220 return false;
221 }
222 };
223
224 /// Match a ConstantInt or splatted ConstantVector, binding the
225 /// specified pointer to the contained APInt.
m_APInt(const APInt * & Res)226 inline apint_match m_APInt(const APInt *&Res) {
227 // Forbid undefs by default to maintain previous behavior.
228 return apint_match(Res, /* AllowUndef */ false);
229 }
230
231 /// Match APInt while allowing undefs in splat vector constants.
m_APIntAllowUndef(const APInt * & Res)232 inline apint_match m_APIntAllowUndef(const APInt *&Res) {
233 return apint_match(Res, /* AllowUndef */ true);
234 }
235
236 /// Match APInt while forbidding undefs in splat vector constants.
m_APIntForbidUndef(const APInt * & Res)237 inline apint_match m_APIntForbidUndef(const APInt *&Res) {
238 return apint_match(Res, /* AllowUndef */ false);
239 }
240
241 /// Match a ConstantFP or splatted ConstantVector, binding the
242 /// specified pointer to the contained APFloat.
m_APFloat(const APFloat * & Res)243 inline apfloat_match m_APFloat(const APFloat *&Res) {
244 // Forbid undefs by default to maintain previous behavior.
245 return apfloat_match(Res, /* AllowUndef */ false);
246 }
247
248 /// Match APFloat while allowing undefs in splat vector constants.
m_APFloatAllowUndef(const APFloat * & Res)249 inline apfloat_match m_APFloatAllowUndef(const APFloat *&Res) {
250 return apfloat_match(Res, /* AllowUndef */ true);
251 }
252
253 /// Match APFloat while forbidding undefs in splat vector constants.
m_APFloatForbidUndef(const APFloat * & Res)254 inline apfloat_match m_APFloatForbidUndef(const APFloat *&Res) {
255 return apfloat_match(Res, /* AllowUndef */ false);
256 }
257
258 template <int64_t Val> struct constantint_match {
matchconstantint_match259 template <typename ITy> bool match(ITy *V) {
260 if (const auto *CI = dyn_cast<ConstantInt>(V)) {
261 const APInt &CIV = CI->getValue();
262 if (Val >= 0)
263 return CIV == static_cast<uint64_t>(Val);
264 // If Val is negative, and CI is shorter than it, truncate to the right
265 // number of bits. If it is larger, then we have to sign extend. Just
266 // compare their negated values.
267 return -CIV == -Val;
268 }
269 return false;
270 }
271 };
272
273 /// Match a ConstantInt with a specific value.
m_ConstantInt()274 template <int64_t Val> inline constantint_match<Val> m_ConstantInt() {
275 return constantint_match<Val>();
276 }
277
278 /// This helper class is used to match constant scalars, vector splats,
279 /// and fixed width vectors that satisfy a specified predicate.
280 /// For fixed width vector constants, undefined elements are ignored.
281 template <typename Predicate, typename ConstantVal>
282 struct cstval_pred_ty : public Predicate {
matchcstval_pred_ty283 template <typename ITy> bool match(ITy *V) {
284 if (const auto *CV = dyn_cast<ConstantVal>(V))
285 return this->isValue(CV->getValue());
286 if (const auto *VTy = dyn_cast<VectorType>(V->getType())) {
287 if (const auto *C = dyn_cast<Constant>(V)) {
288 if (const auto *CV = dyn_cast_or_null<ConstantVal>(C->getSplatValue()))
289 return this->isValue(CV->getValue());
290
291 // Number of elements of a scalable vector unknown at compile time
292 auto *FVTy = dyn_cast<FixedVectorType>(VTy);
293 if (!FVTy)
294 return false;
295
296 // Non-splat vector constant: check each element for a match.
297 unsigned NumElts = FVTy->getNumElements();
298 assert(NumElts != 0 && "Constant vector with no elements?");
299 bool HasNonUndefElements = false;
300 for (unsigned i = 0; i != NumElts; ++i) {
301 Constant *Elt = C->getAggregateElement(i);
302 if (!Elt)
303 return false;
304 if (isa<UndefValue>(Elt))
305 continue;
306 auto *CV = dyn_cast<ConstantVal>(Elt);
307 if (!CV || !this->isValue(CV->getValue()))
308 return false;
309 HasNonUndefElements = true;
310 }
311 return HasNonUndefElements;
312 }
313 }
314 return false;
315 }
316 };
317
318 /// specialization of cstval_pred_ty for ConstantInt
319 template <typename Predicate>
320 using cst_pred_ty = cstval_pred_ty<Predicate, ConstantInt>;
321
322 /// specialization of cstval_pred_ty for ConstantFP
323 template <typename Predicate>
324 using cstfp_pred_ty = cstval_pred_ty<Predicate, ConstantFP>;
325
326 /// This helper class is used to match scalar and vector constants that
327 /// satisfy a specified predicate, and bind them to an APInt.
328 template <typename Predicate> struct api_pred_ty : public Predicate {
329 const APInt *&Res;
330
api_pred_tyapi_pred_ty331 api_pred_ty(const APInt *&R) : Res(R) {}
332
matchapi_pred_ty333 template <typename ITy> bool match(ITy *V) {
334 if (const auto *CI = dyn_cast<ConstantInt>(V))
335 if (this->isValue(CI->getValue())) {
336 Res = &CI->getValue();
337 return true;
338 }
339 if (V->getType()->isVectorTy())
340 if (const auto *C = dyn_cast<Constant>(V))
341 if (auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue()))
342 if (this->isValue(CI->getValue())) {
343 Res = &CI->getValue();
344 return true;
345 }
346
347 return false;
348 }
349 };
350
351 /// This helper class is used to match scalar and vector constants that
352 /// satisfy a specified predicate, and bind them to an APFloat.
353 /// Undefs are allowed in splat vector constants.
354 template <typename Predicate> struct apf_pred_ty : public Predicate {
355 const APFloat *&Res;
356
apf_pred_tyapf_pred_ty357 apf_pred_ty(const APFloat *&R) : Res(R) {}
358
matchapf_pred_ty359 template <typename ITy> bool match(ITy *V) {
360 if (const auto *CI = dyn_cast<ConstantFP>(V))
361 if (this->isValue(CI->getValue())) {
362 Res = &CI->getValue();
363 return true;
364 }
365 if (V->getType()->isVectorTy())
366 if (const auto *C = dyn_cast<Constant>(V))
367 if (auto *CI = dyn_cast_or_null<ConstantFP>(
368 C->getSplatValue(/* AllowUndef */ true)))
369 if (this->isValue(CI->getValue())) {
370 Res = &CI->getValue();
371 return true;
372 }
373
374 return false;
375 }
376 };
377
378 ///////////////////////////////////////////////////////////////////////////////
379 //
380 // Encapsulate constant value queries for use in templated predicate matchers.
381 // This allows checking if constants match using compound predicates and works
382 // with vector constants, possibly with relaxed constraints. For example, ignore
383 // undef values.
384 //
385 ///////////////////////////////////////////////////////////////////////////////
386
387 struct is_any_apint {
isValueis_any_apint388 bool isValue(const APInt &C) { return true; }
389 };
390 /// Match an integer or vector with any integral constant.
391 /// For vectors, this includes constants with undefined elements.
m_AnyIntegralConstant()392 inline cst_pred_ty<is_any_apint> m_AnyIntegralConstant() {
393 return cst_pred_ty<is_any_apint>();
394 }
395
396 struct is_all_ones {
isValueis_all_ones397 bool isValue(const APInt &C) { return C.isAllOnesValue(); }
398 };
399 /// Match an integer or vector with all bits set.
400 /// For vectors, this includes constants with undefined elements.
m_AllOnes()401 inline cst_pred_ty<is_all_ones> m_AllOnes() {
402 return cst_pred_ty<is_all_ones>();
403 }
404
405 struct is_maxsignedvalue {
isValueis_maxsignedvalue406 bool isValue(const APInt &C) { return C.isMaxSignedValue(); }
407 };
408 /// Match an integer or vector with values having all bits except for the high
409 /// bit set (0x7f...).
410 /// For vectors, this includes constants with undefined elements.
m_MaxSignedValue()411 inline cst_pred_ty<is_maxsignedvalue> m_MaxSignedValue() {
412 return cst_pred_ty<is_maxsignedvalue>();
413 }
m_MaxSignedValue(const APInt * & V)414 inline api_pred_ty<is_maxsignedvalue> m_MaxSignedValue(const APInt *&V) {
415 return V;
416 }
417
418 struct is_negative {
isValueis_negative419 bool isValue(const APInt &C) { return C.isNegative(); }
420 };
421 /// Match an integer or vector of negative values.
422 /// For vectors, this includes constants with undefined elements.
m_Negative()423 inline cst_pred_ty<is_negative> m_Negative() {
424 return cst_pred_ty<is_negative>();
425 }
m_Negative(const APInt * & V)426 inline api_pred_ty<is_negative> m_Negative(const APInt *&V) {
427 return V;
428 }
429
430 struct is_nonnegative {
isValueis_nonnegative431 bool isValue(const APInt &C) { return C.isNonNegative(); }
432 };
433 /// Match an integer or vector of non-negative values.
434 /// For vectors, this includes constants with undefined elements.
m_NonNegative()435 inline cst_pred_ty<is_nonnegative> m_NonNegative() {
436 return cst_pred_ty<is_nonnegative>();
437 }
m_NonNegative(const APInt * & V)438 inline api_pred_ty<is_nonnegative> m_NonNegative(const APInt *&V) {
439 return V;
440 }
441
442 struct is_strictlypositive {
isValueis_strictlypositive443 bool isValue(const APInt &C) { return C.isStrictlyPositive(); }
444 };
445 /// Match an integer or vector of strictly positive values.
446 /// For vectors, this includes constants with undefined elements.
m_StrictlyPositive()447 inline cst_pred_ty<is_strictlypositive> m_StrictlyPositive() {
448 return cst_pred_ty<is_strictlypositive>();
449 }
m_StrictlyPositive(const APInt * & V)450 inline api_pred_ty<is_strictlypositive> m_StrictlyPositive(const APInt *&V) {
451 return V;
452 }
453
454 struct is_nonpositive {
isValueis_nonpositive455 bool isValue(const APInt &C) { return C.isNonPositive(); }
456 };
457 /// Match an integer or vector of non-positive values.
458 /// For vectors, this includes constants with undefined elements.
m_NonPositive()459 inline cst_pred_ty<is_nonpositive> m_NonPositive() {
460 return cst_pred_ty<is_nonpositive>();
461 }
m_NonPositive(const APInt * & V)462 inline api_pred_ty<is_nonpositive> m_NonPositive(const APInt *&V) { return V; }
463
464 struct is_one {
isValueis_one465 bool isValue(const APInt &C) { return C.isOneValue(); }
466 };
467 /// Match an integer 1 or a vector with all elements equal to 1.
468 /// For vectors, this includes constants with undefined elements.
m_One()469 inline cst_pred_ty<is_one> m_One() {
470 return cst_pred_ty<is_one>();
471 }
472
473 struct is_zero_int {
isValueis_zero_int474 bool isValue(const APInt &C) { return C.isNullValue(); }
475 };
476 /// Match an integer 0 or a vector with all elements equal to 0.
477 /// For vectors, this includes constants with undefined elements.
m_ZeroInt()478 inline cst_pred_ty<is_zero_int> m_ZeroInt() {
479 return cst_pred_ty<is_zero_int>();
480 }
481
482 struct is_zero {
matchis_zero483 template <typename ITy> bool match(ITy *V) {
484 auto *C = dyn_cast<Constant>(V);
485 // FIXME: this should be able to do something for scalable vectors
486 return C && (C->isNullValue() || cst_pred_ty<is_zero_int>().match(C));
487 }
488 };
489 /// Match any null constant or a vector with all elements equal to 0.
490 /// For vectors, this includes constants with undefined elements.
m_Zero()491 inline is_zero m_Zero() {
492 return is_zero();
493 }
494
495 struct is_power2 {
isValueis_power2496 bool isValue(const APInt &C) { return C.isPowerOf2(); }
497 };
498 /// Match an integer or vector power-of-2.
499 /// For vectors, this includes constants with undefined elements.
m_Power2()500 inline cst_pred_ty<is_power2> m_Power2() {
501 return cst_pred_ty<is_power2>();
502 }
m_Power2(const APInt * & V)503 inline api_pred_ty<is_power2> m_Power2(const APInt *&V) {
504 return V;
505 }
506
507 struct is_negated_power2 {
isValueis_negated_power2508 bool isValue(const APInt &C) { return (-C).isPowerOf2(); }
509 };
510 /// Match a integer or vector negated power-of-2.
511 /// For vectors, this includes constants with undefined elements.
m_NegatedPower2()512 inline cst_pred_ty<is_negated_power2> m_NegatedPower2() {
513 return cst_pred_ty<is_negated_power2>();
514 }
m_NegatedPower2(const APInt * & V)515 inline api_pred_ty<is_negated_power2> m_NegatedPower2(const APInt *&V) {
516 return V;
517 }
518
519 struct is_power2_or_zero {
isValueis_power2_or_zero520 bool isValue(const APInt &C) { return !C || C.isPowerOf2(); }
521 };
522 /// Match an integer or vector of 0 or power-of-2 values.
523 /// For vectors, this includes constants with undefined elements.
m_Power2OrZero()524 inline cst_pred_ty<is_power2_or_zero> m_Power2OrZero() {
525 return cst_pred_ty<is_power2_or_zero>();
526 }
m_Power2OrZero(const APInt * & V)527 inline api_pred_ty<is_power2_or_zero> m_Power2OrZero(const APInt *&V) {
528 return V;
529 }
530
531 struct is_sign_mask {
isValueis_sign_mask532 bool isValue(const APInt &C) { return C.isSignMask(); }
533 };
534 /// Match an integer or vector with only the sign bit(s) set.
535 /// For vectors, this includes constants with undefined elements.
m_SignMask()536 inline cst_pred_ty<is_sign_mask> m_SignMask() {
537 return cst_pred_ty<is_sign_mask>();
538 }
539
540 struct is_lowbit_mask {
isValueis_lowbit_mask541 bool isValue(const APInt &C) { return C.isMask(); }
542 };
543 /// Match an integer or vector with only the low bit(s) set.
544 /// For vectors, this includes constants with undefined elements.
m_LowBitMask()545 inline cst_pred_ty<is_lowbit_mask> m_LowBitMask() {
546 return cst_pred_ty<is_lowbit_mask>();
547 }
548
549 struct icmp_pred_with_threshold {
550 ICmpInst::Predicate Pred;
551 const APInt *Thr;
isValueicmp_pred_with_threshold552 bool isValue(const APInt &C) {
553 switch (Pred) {
554 case ICmpInst::Predicate::ICMP_EQ:
555 return C.eq(*Thr);
556 case ICmpInst::Predicate::ICMP_NE:
557 return C.ne(*Thr);
558 case ICmpInst::Predicate::ICMP_UGT:
559 return C.ugt(*Thr);
560 case ICmpInst::Predicate::ICMP_UGE:
561 return C.uge(*Thr);
562 case ICmpInst::Predicate::ICMP_ULT:
563 return C.ult(*Thr);
564 case ICmpInst::Predicate::ICMP_ULE:
565 return C.ule(*Thr);
566 case ICmpInst::Predicate::ICMP_SGT:
567 return C.sgt(*Thr);
568 case ICmpInst::Predicate::ICMP_SGE:
569 return C.sge(*Thr);
570 case ICmpInst::Predicate::ICMP_SLT:
571 return C.slt(*Thr);
572 case ICmpInst::Predicate::ICMP_SLE:
573 return C.sle(*Thr);
574 default:
575 llvm_unreachable("Unhandled ICmp predicate");
576 }
577 }
578 };
579 /// Match an integer or vector with every element comparing 'pred' (eg/ne/...)
580 /// to Threshold. For vectors, this includes constants with undefined elements.
581 inline cst_pred_ty<icmp_pred_with_threshold>
m_SpecificInt_ICMP(ICmpInst::Predicate Predicate,const APInt & Threshold)582 m_SpecificInt_ICMP(ICmpInst::Predicate Predicate, const APInt &Threshold) {
583 cst_pred_ty<icmp_pred_with_threshold> P;
584 P.Pred = Predicate;
585 P.Thr = &Threshold;
586 return P;
587 }
588
589 struct is_nan {
isValueis_nan590 bool isValue(const APFloat &C) { return C.isNaN(); }
591 };
592 /// Match an arbitrary NaN constant. This includes quiet and signalling nans.
593 /// For vectors, this includes constants with undefined elements.
m_NaN()594 inline cstfp_pred_ty<is_nan> m_NaN() {
595 return cstfp_pred_ty<is_nan>();
596 }
597
598 struct is_nonnan {
isValueis_nonnan599 bool isValue(const APFloat &C) { return !C.isNaN(); }
600 };
601 /// Match a non-NaN FP constant.
602 /// For vectors, this includes constants with undefined elements.
m_NonNaN()603 inline cstfp_pred_ty<is_nonnan> m_NonNaN() {
604 return cstfp_pred_ty<is_nonnan>();
605 }
606
607 struct is_inf {
isValueis_inf608 bool isValue(const APFloat &C) { return C.isInfinity(); }
609 };
610 /// Match a positive or negative infinity FP constant.
611 /// For vectors, this includes constants with undefined elements.
m_Inf()612 inline cstfp_pred_ty<is_inf> m_Inf() {
613 return cstfp_pred_ty<is_inf>();
614 }
615
616 struct is_noninf {
isValueis_noninf617 bool isValue(const APFloat &C) { return !C.isInfinity(); }
618 };
619 /// Match a non-infinity FP constant, i.e. finite or NaN.
620 /// For vectors, this includes constants with undefined elements.
m_NonInf()621 inline cstfp_pred_ty<is_noninf> m_NonInf() {
622 return cstfp_pred_ty<is_noninf>();
623 }
624
625 struct is_finite {
isValueis_finite626 bool isValue(const APFloat &C) { return C.isFinite(); }
627 };
628 /// Match a finite FP constant, i.e. not infinity or NaN.
629 /// For vectors, this includes constants with undefined elements.
m_Finite()630 inline cstfp_pred_ty<is_finite> m_Finite() {
631 return cstfp_pred_ty<is_finite>();
632 }
m_Finite(const APFloat * & V)633 inline apf_pred_ty<is_finite> m_Finite(const APFloat *&V) { return V; }
634
635 struct is_finitenonzero {
isValueis_finitenonzero636 bool isValue(const APFloat &C) { return C.isFiniteNonZero(); }
637 };
638 /// Match a finite non-zero FP constant.
639 /// For vectors, this includes constants with undefined elements.
m_FiniteNonZero()640 inline cstfp_pred_ty<is_finitenonzero> m_FiniteNonZero() {
641 return cstfp_pred_ty<is_finitenonzero>();
642 }
m_FiniteNonZero(const APFloat * & V)643 inline apf_pred_ty<is_finitenonzero> m_FiniteNonZero(const APFloat *&V) {
644 return V;
645 }
646
647 struct is_any_zero_fp {
isValueis_any_zero_fp648 bool isValue(const APFloat &C) { return C.isZero(); }
649 };
650 /// Match a floating-point negative zero or positive zero.
651 /// For vectors, this includes constants with undefined elements.
m_AnyZeroFP()652 inline cstfp_pred_ty<is_any_zero_fp> m_AnyZeroFP() {
653 return cstfp_pred_ty<is_any_zero_fp>();
654 }
655
656 struct is_pos_zero_fp {
isValueis_pos_zero_fp657 bool isValue(const APFloat &C) { return C.isPosZero(); }
658 };
659 /// Match a floating-point positive zero.
660 /// For vectors, this includes constants with undefined elements.
m_PosZeroFP()661 inline cstfp_pred_ty<is_pos_zero_fp> m_PosZeroFP() {
662 return cstfp_pred_ty<is_pos_zero_fp>();
663 }
664
665 struct is_neg_zero_fp {
isValueis_neg_zero_fp666 bool isValue(const APFloat &C) { return C.isNegZero(); }
667 };
668 /// Match a floating-point negative zero.
669 /// For vectors, this includes constants with undefined elements.
m_NegZeroFP()670 inline cstfp_pred_ty<is_neg_zero_fp> m_NegZeroFP() {
671 return cstfp_pred_ty<is_neg_zero_fp>();
672 }
673
674 struct is_non_zero_fp {
isValueis_non_zero_fp675 bool isValue(const APFloat &C) { return C.isNonZero(); }
676 };
677 /// Match a floating-point non-zero.
678 /// For vectors, this includes constants with undefined elements.
m_NonZeroFP()679 inline cstfp_pred_ty<is_non_zero_fp> m_NonZeroFP() {
680 return cstfp_pred_ty<is_non_zero_fp>();
681 }
682
683 ///////////////////////////////////////////////////////////////////////////////
684
685 template <typename Class> struct bind_ty {
686 Class *&VR;
687
bind_tybind_ty688 bind_ty(Class *&V) : VR(V) {}
689
matchbind_ty690 template <typename ITy> bool match(ITy *V) {
691 if (auto *CV = dyn_cast<Class>(V)) {
692 VR = CV;
693 return true;
694 }
695 return false;
696 }
697 };
698
699 /// Match a value, capturing it if we match.
m_Value(Value * & V)700 inline bind_ty<Value> m_Value(Value *&V) { return V; }
m_Value(const Value * & V)701 inline bind_ty<const Value> m_Value(const Value *&V) { return V; }
702
703 /// Match an instruction, capturing it if we match.
m_Instruction(Instruction * & I)704 inline bind_ty<Instruction> m_Instruction(Instruction *&I) { return I; }
705 /// Match a unary operator, capturing it if we match.
m_UnOp(UnaryOperator * & I)706 inline bind_ty<UnaryOperator> m_UnOp(UnaryOperator *&I) { return I; }
707 /// Match a binary operator, capturing it if we match.
m_BinOp(BinaryOperator * & I)708 inline bind_ty<BinaryOperator> m_BinOp(BinaryOperator *&I) { return I; }
709 /// Match a with overflow intrinsic, capturing it if we match.
m_WithOverflowInst(WithOverflowInst * & I)710 inline bind_ty<WithOverflowInst> m_WithOverflowInst(WithOverflowInst *&I) { return I; }
711
712 /// Match a Constant, capturing the value if we match.
m_Constant(Constant * & C)713 inline bind_ty<Constant> m_Constant(Constant *&C) { return C; }
714
715 /// Match a ConstantInt, capturing the value if we match.
m_ConstantInt(ConstantInt * & CI)716 inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
717
718 /// Match a ConstantFP, capturing the value if we match.
m_ConstantFP(ConstantFP * & C)719 inline bind_ty<ConstantFP> m_ConstantFP(ConstantFP *&C) { return C; }
720
721 /// Match a ConstantExpr, capturing the value if we match.
m_ConstantExpr(ConstantExpr * & C)722 inline bind_ty<ConstantExpr> m_ConstantExpr(ConstantExpr *&C) { return C; }
723
724 /// Match a basic block value, capturing it if we match.
m_BasicBlock(BasicBlock * & V)725 inline bind_ty<BasicBlock> m_BasicBlock(BasicBlock *&V) { return V; }
m_BasicBlock(const BasicBlock * & V)726 inline bind_ty<const BasicBlock> m_BasicBlock(const BasicBlock *&V) {
727 return V;
728 }
729
730 /// Match an arbitrary immediate Constant and ignore it.
731 inline match_combine_and<class_match<Constant>,
732 match_unless<class_match<ConstantExpr>>>
m_ImmConstant()733 m_ImmConstant() {
734 return m_CombineAnd(m_Constant(), m_Unless(m_ConstantExpr()));
735 }
736
737 /// Match an immediate Constant, capturing the value if we match.
738 inline match_combine_and<bind_ty<Constant>,
739 match_unless<class_match<ConstantExpr>>>
m_ImmConstant(Constant * & C)740 m_ImmConstant(Constant *&C) {
741 return m_CombineAnd(m_Constant(C), m_Unless(m_ConstantExpr()));
742 }
743
744 /// Match a specified Value*.
745 struct specificval_ty {
746 const Value *Val;
747
specificval_tyspecificval_ty748 specificval_ty(const Value *V) : Val(V) {}
749
matchspecificval_ty750 template <typename ITy> bool match(ITy *V) { return V == Val; }
751 };
752
753 /// Match if we have a specific specified value.
m_Specific(const Value * V)754 inline specificval_ty m_Specific(const Value *V) { return V; }
755
756 /// Stores a reference to the Value *, not the Value * itself,
757 /// thus can be used in commutative matchers.
758 template <typename Class> struct deferredval_ty {
759 Class *const &Val;
760
deferredval_tydeferredval_ty761 deferredval_ty(Class *const &V) : Val(V) {}
762
matchdeferredval_ty763 template <typename ITy> bool match(ITy *const V) { return V == Val; }
764 };
765
766 /// A commutative-friendly version of m_Specific().
m_Deferred(Value * const & V)767 inline deferredval_ty<Value> m_Deferred(Value *const &V) { return V; }
m_Deferred(const Value * const & V)768 inline deferredval_ty<const Value> m_Deferred(const Value *const &V) {
769 return V;
770 }
771
772 /// Match a specified floating point value or vector of all elements of
773 /// that value.
774 struct specific_fpval {
775 double Val;
776
specific_fpvalspecific_fpval777 specific_fpval(double V) : Val(V) {}
778
matchspecific_fpval779 template <typename ITy> bool match(ITy *V) {
780 if (const auto *CFP = dyn_cast<ConstantFP>(V))
781 return CFP->isExactlyValue(Val);
782 if (V->getType()->isVectorTy())
783 if (const auto *C = dyn_cast<Constant>(V))
784 if (auto *CFP = dyn_cast_or_null<ConstantFP>(C->getSplatValue()))
785 return CFP->isExactlyValue(Val);
786 return false;
787 }
788 };
789
790 /// Match a specific floating point value or vector with all elements
791 /// equal to the value.
m_SpecificFP(double V)792 inline specific_fpval m_SpecificFP(double V) { return specific_fpval(V); }
793
794 /// Match a float 1.0 or vector with all elements equal to 1.0.
m_FPOne()795 inline specific_fpval m_FPOne() { return m_SpecificFP(1.0); }
796
797 struct bind_const_intval_ty {
798 uint64_t &VR;
799
bind_const_intval_tybind_const_intval_ty800 bind_const_intval_ty(uint64_t &V) : VR(V) {}
801
matchbind_const_intval_ty802 template <typename ITy> bool match(ITy *V) {
803 if (const auto *CV = dyn_cast<ConstantInt>(V))
804 if (CV->getValue().ule(UINT64_MAX)) {
805 VR = CV->getZExtValue();
806 return true;
807 }
808 return false;
809 }
810 };
811
812 /// Match a specified integer value or vector of all elements of that
813 /// value.
814 template <bool AllowUndefs>
815 struct specific_intval {
816 APInt Val;
817
specific_intvalspecific_intval818 specific_intval(APInt V) : Val(std::move(V)) {}
819
matchspecific_intval820 template <typename ITy> bool match(ITy *V) {
821 const auto *CI = dyn_cast<ConstantInt>(V);
822 if (!CI && V->getType()->isVectorTy())
823 if (const auto *C = dyn_cast<Constant>(V))
824 CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue(AllowUndefs));
825
826 return CI && APInt::isSameValue(CI->getValue(), Val);
827 }
828 };
829
830 /// Match a specific integer value or vector with all elements equal to
831 /// the value.
m_SpecificInt(APInt V)832 inline specific_intval<false> m_SpecificInt(APInt V) {
833 return specific_intval<false>(std::move(V));
834 }
835
m_SpecificInt(uint64_t V)836 inline specific_intval<false> m_SpecificInt(uint64_t V) {
837 return m_SpecificInt(APInt(64, V));
838 }
839
m_SpecificIntAllowUndef(APInt V)840 inline specific_intval<true> m_SpecificIntAllowUndef(APInt V) {
841 return specific_intval<true>(std::move(V));
842 }
843
m_SpecificIntAllowUndef(uint64_t V)844 inline specific_intval<true> m_SpecificIntAllowUndef(uint64_t V) {
845 return m_SpecificIntAllowUndef(APInt(64, V));
846 }
847
848 /// Match a ConstantInt and bind to its value. This does not match
849 /// ConstantInts wider than 64-bits.
m_ConstantInt(uint64_t & V)850 inline bind_const_intval_ty m_ConstantInt(uint64_t &V) { return V; }
851
852 /// Match a specified basic block value.
853 struct specific_bbval {
854 BasicBlock *Val;
855
specific_bbvalspecific_bbval856 specific_bbval(BasicBlock *Val) : Val(Val) {}
857
matchspecific_bbval858 template <typename ITy> bool match(ITy *V) {
859 const auto *BB = dyn_cast<BasicBlock>(V);
860 return BB && BB == Val;
861 }
862 };
863
864 /// Match a specific basic block value.
m_SpecificBB(BasicBlock * BB)865 inline specific_bbval m_SpecificBB(BasicBlock *BB) {
866 return specific_bbval(BB);
867 }
868
869 /// A commutative-friendly version of m_Specific().
m_Deferred(BasicBlock * const & BB)870 inline deferredval_ty<BasicBlock> m_Deferred(BasicBlock *const &BB) {
871 return BB;
872 }
873 inline deferredval_ty<const BasicBlock>
m_Deferred(const BasicBlock * const & BB)874 m_Deferred(const BasicBlock *const &BB) {
875 return BB;
876 }
877
878 //===----------------------------------------------------------------------===//
879 // Matcher for any binary operator.
880 //
881 template <typename LHS_t, typename RHS_t, bool Commutable = false>
882 struct AnyBinaryOp_match {
883 LHS_t L;
884 RHS_t R;
885
886 // The evaluation order is always stable, regardless of Commutability.
887 // The LHS is always matched first.
AnyBinaryOp_matchAnyBinaryOp_match888 AnyBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
889
matchAnyBinaryOp_match890 template <typename OpTy> bool match(OpTy *V) {
891 if (auto *I = dyn_cast<BinaryOperator>(V))
892 return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
893 (Commutable && L.match(I->getOperand(1)) &&
894 R.match(I->getOperand(0)));
895 return false;
896 }
897 };
898
899 template <typename LHS, typename RHS>
m_BinOp(const LHS & L,const RHS & R)900 inline AnyBinaryOp_match<LHS, RHS> m_BinOp(const LHS &L, const RHS &R) {
901 return AnyBinaryOp_match<LHS, RHS>(L, R);
902 }
903
904 //===----------------------------------------------------------------------===//
905 // Matcher for any unary operator.
906 // TODO fuse unary, binary matcher into n-ary matcher
907 //
908 template <typename OP_t> struct AnyUnaryOp_match {
909 OP_t X;
910
AnyUnaryOp_matchAnyUnaryOp_match911 AnyUnaryOp_match(const OP_t &X) : X(X) {}
912
matchAnyUnaryOp_match913 template <typename OpTy> bool match(OpTy *V) {
914 if (auto *I = dyn_cast<UnaryOperator>(V))
915 return X.match(I->getOperand(0));
916 return false;
917 }
918 };
919
m_UnOp(const OP_t & X)920 template <typename OP_t> inline AnyUnaryOp_match<OP_t> m_UnOp(const OP_t &X) {
921 return AnyUnaryOp_match<OP_t>(X);
922 }
923
924 //===----------------------------------------------------------------------===//
925 // Matchers for specific binary operators.
926 //
927
928 template <typename LHS_t, typename RHS_t, unsigned Opcode,
929 bool Commutable = false>
930 struct BinaryOp_match {
931 LHS_t L;
932 RHS_t R;
933
934 // The evaluation order is always stable, regardless of Commutability.
935 // The LHS is always matched first.
BinaryOp_matchBinaryOp_match936 BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
937
matchBinaryOp_match938 template <typename OpTy> bool match(OpTy *V) {
939 if (V->getValueID() == Value::InstructionVal + Opcode) {
940 auto *I = cast<BinaryOperator>(V);
941 return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
942 (Commutable && L.match(I->getOperand(1)) &&
943 R.match(I->getOperand(0)));
944 }
945 if (auto *CE = dyn_cast<ConstantExpr>(V))
946 return CE->getOpcode() == Opcode &&
947 ((L.match(CE->getOperand(0)) && R.match(CE->getOperand(1))) ||
948 (Commutable && L.match(CE->getOperand(1)) &&
949 R.match(CE->getOperand(0))));
950 return false;
951 }
952 };
953
954 template <typename LHS, typename RHS>
m_Add(const LHS & L,const RHS & R)955 inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L,
956 const RHS &R) {
957 return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);
958 }
959
960 template <typename LHS, typename RHS>
m_FAdd(const LHS & L,const RHS & R)961 inline BinaryOp_match<LHS, RHS, Instruction::FAdd> m_FAdd(const LHS &L,
962 const RHS &R) {
963 return BinaryOp_match<LHS, RHS, Instruction::FAdd>(L, R);
964 }
965
966 template <typename LHS, typename RHS>
m_Sub(const LHS & L,const RHS & R)967 inline BinaryOp_match<LHS, RHS, Instruction::Sub> m_Sub(const LHS &L,
968 const RHS &R) {
969 return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R);
970 }
971
972 template <typename LHS, typename RHS>
m_FSub(const LHS & L,const RHS & R)973 inline BinaryOp_match<LHS, RHS, Instruction::FSub> m_FSub(const LHS &L,
974 const RHS &R) {
975 return BinaryOp_match<LHS, RHS, Instruction::FSub>(L, R);
976 }
977
978 template <typename Op_t> struct FNeg_match {
979 Op_t X;
980
FNeg_matchFNeg_match981 FNeg_match(const Op_t &Op) : X(Op) {}
matchFNeg_match982 template <typename OpTy> bool match(OpTy *V) {
983 auto *FPMO = dyn_cast<FPMathOperator>(V);
984 if (!FPMO) return false;
985
986 if (FPMO->getOpcode() == Instruction::FNeg)
987 return X.match(FPMO->getOperand(0));
988
989 if (FPMO->getOpcode() == Instruction::FSub) {
990 if (FPMO->hasNoSignedZeros()) {
991 // With 'nsz', any zero goes.
992 if (!cstfp_pred_ty<is_any_zero_fp>().match(FPMO->getOperand(0)))
993 return false;
994 } else {
995 // Without 'nsz', we need fsub -0.0, X exactly.
996 if (!cstfp_pred_ty<is_neg_zero_fp>().match(FPMO->getOperand(0)))
997 return false;
998 }
999
1000 return X.match(FPMO->getOperand(1));
1001 }
1002
1003 return false;
1004 }
1005 };
1006
1007 /// Match 'fneg X' as 'fsub -0.0, X'.
1008 template <typename OpTy>
1009 inline FNeg_match<OpTy>
m_FNeg(const OpTy & X)1010 m_FNeg(const OpTy &X) {
1011 return FNeg_match<OpTy>(X);
1012 }
1013
1014 /// Match 'fneg X' as 'fsub +-0.0, X'.
1015 template <typename RHS>
1016 inline BinaryOp_match<cstfp_pred_ty<is_any_zero_fp>, RHS, Instruction::FSub>
m_FNegNSZ(const RHS & X)1017 m_FNegNSZ(const RHS &X) {
1018 return m_FSub(m_AnyZeroFP(), X);
1019 }
1020
1021 template <typename LHS, typename RHS>
m_Mul(const LHS & L,const RHS & R)1022 inline BinaryOp_match<LHS, RHS, Instruction::Mul> m_Mul(const LHS &L,
1023 const RHS &R) {
1024 return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R);
1025 }
1026
1027 template <typename LHS, typename RHS>
m_FMul(const LHS & L,const RHS & R)1028 inline BinaryOp_match<LHS, RHS, Instruction::FMul> m_FMul(const LHS &L,
1029 const RHS &R) {
1030 return BinaryOp_match<LHS, RHS, Instruction::FMul>(L, R);
1031 }
1032
1033 template <typename LHS, typename RHS>
m_UDiv(const LHS & L,const RHS & R)1034 inline BinaryOp_match<LHS, RHS, Instruction::UDiv> m_UDiv(const LHS &L,
1035 const RHS &R) {
1036 return BinaryOp_match<LHS, RHS, Instruction::UDiv>(L, R);
1037 }
1038
1039 template <typename LHS, typename RHS>
m_SDiv(const LHS & L,const RHS & R)1040 inline BinaryOp_match<LHS, RHS, Instruction::SDiv> m_SDiv(const LHS &L,
1041 const RHS &R) {
1042 return BinaryOp_match<LHS, RHS, Instruction::SDiv>(L, R);
1043 }
1044
1045 template <typename LHS, typename RHS>
m_FDiv(const LHS & L,const RHS & R)1046 inline BinaryOp_match<LHS, RHS, Instruction::FDiv> m_FDiv(const LHS &L,
1047 const RHS &R) {
1048 return BinaryOp_match<LHS, RHS, Instruction::FDiv>(L, R);
1049 }
1050
1051 template <typename LHS, typename RHS>
m_URem(const LHS & L,const RHS & R)1052 inline BinaryOp_match<LHS, RHS, Instruction::URem> m_URem(const LHS &L,
1053 const RHS &R) {
1054 return BinaryOp_match<LHS, RHS, Instruction::URem>(L, R);
1055 }
1056
1057 template <typename LHS, typename RHS>
m_SRem(const LHS & L,const RHS & R)1058 inline BinaryOp_match<LHS, RHS, Instruction::SRem> m_SRem(const LHS &L,
1059 const RHS &R) {
1060 return BinaryOp_match<LHS, RHS, Instruction::SRem>(L, R);
1061 }
1062
1063 template <typename LHS, typename RHS>
m_FRem(const LHS & L,const RHS & R)1064 inline BinaryOp_match<LHS, RHS, Instruction::FRem> m_FRem(const LHS &L,
1065 const RHS &R) {
1066 return BinaryOp_match<LHS, RHS, Instruction::FRem>(L, R);
1067 }
1068
1069 template <typename LHS, typename RHS>
m_And(const LHS & L,const RHS & R)1070 inline BinaryOp_match<LHS, RHS, Instruction::And> m_And(const LHS &L,
1071 const RHS &R) {
1072 return BinaryOp_match<LHS, RHS, Instruction::And>(L, R);
1073 }
1074
1075 template <typename LHS, typename RHS>
m_Or(const LHS & L,const RHS & R)1076 inline BinaryOp_match<LHS, RHS, Instruction::Or> m_Or(const LHS &L,
1077 const RHS &R) {
1078 return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R);
1079 }
1080
1081 template <typename LHS, typename RHS>
m_Xor(const LHS & L,const RHS & R)1082 inline BinaryOp_match<LHS, RHS, Instruction::Xor> m_Xor(const LHS &L,
1083 const RHS &R) {
1084 return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R);
1085 }
1086
1087 template <typename LHS, typename RHS>
m_Shl(const LHS & L,const RHS & R)1088 inline BinaryOp_match<LHS, RHS, Instruction::Shl> m_Shl(const LHS &L,
1089 const RHS &R) {
1090 return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R);
1091 }
1092
1093 template <typename LHS, typename RHS>
m_LShr(const LHS & L,const RHS & R)1094 inline BinaryOp_match<LHS, RHS, Instruction::LShr> m_LShr(const LHS &L,
1095 const RHS &R) {
1096 return BinaryOp_match<LHS, RHS, Instruction::LShr>(L, R);
1097 }
1098
1099 template <typename LHS, typename RHS>
m_AShr(const LHS & L,const RHS & R)1100 inline BinaryOp_match<LHS, RHS, Instruction::AShr> m_AShr(const LHS &L,
1101 const RHS &R) {
1102 return BinaryOp_match<LHS, RHS, Instruction::AShr>(L, R);
1103 }
1104
1105 template <typename LHS_t, typename RHS_t, unsigned Opcode,
1106 unsigned WrapFlags = 0>
1107 struct OverflowingBinaryOp_match {
1108 LHS_t L;
1109 RHS_t R;
1110
OverflowingBinaryOp_matchOverflowingBinaryOp_match1111 OverflowingBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS)
1112 : L(LHS), R(RHS) {}
1113
matchOverflowingBinaryOp_match1114 template <typename OpTy> bool match(OpTy *V) {
1115 if (auto *Op = dyn_cast<OverflowingBinaryOperator>(V)) {
1116 if (Op->getOpcode() != Opcode)
1117 return false;
1118 if (WrapFlags & OverflowingBinaryOperator::NoUnsignedWrap &&
1119 !Op->hasNoUnsignedWrap())
1120 return false;
1121 if (WrapFlags & OverflowingBinaryOperator::NoSignedWrap &&
1122 !Op->hasNoSignedWrap())
1123 return false;
1124 return L.match(Op->getOperand(0)) && R.match(Op->getOperand(1));
1125 }
1126 return false;
1127 }
1128 };
1129
1130 template <typename LHS, typename RHS>
1131 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
1132 OverflowingBinaryOperator::NoSignedWrap>
m_NSWAdd(const LHS & L,const RHS & R)1133 m_NSWAdd(const LHS &L, const RHS &R) {
1134 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
1135 OverflowingBinaryOperator::NoSignedWrap>(
1136 L, R);
1137 }
1138 template <typename LHS, typename RHS>
1139 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
1140 OverflowingBinaryOperator::NoSignedWrap>
m_NSWSub(const LHS & L,const RHS & R)1141 m_NSWSub(const LHS &L, const RHS &R) {
1142 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
1143 OverflowingBinaryOperator::NoSignedWrap>(
1144 L, R);
1145 }
1146 template <typename LHS, typename RHS>
1147 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
1148 OverflowingBinaryOperator::NoSignedWrap>
m_NSWMul(const LHS & L,const RHS & R)1149 m_NSWMul(const LHS &L, const RHS &R) {
1150 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
1151 OverflowingBinaryOperator::NoSignedWrap>(
1152 L, R);
1153 }
1154 template <typename LHS, typename RHS>
1155 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
1156 OverflowingBinaryOperator::NoSignedWrap>
m_NSWShl(const LHS & L,const RHS & R)1157 m_NSWShl(const LHS &L, const RHS &R) {
1158 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
1159 OverflowingBinaryOperator::NoSignedWrap>(
1160 L, R);
1161 }
1162
1163 template <typename LHS, typename RHS>
1164 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
1165 OverflowingBinaryOperator::NoUnsignedWrap>
m_NUWAdd(const LHS & L,const RHS & R)1166 m_NUWAdd(const LHS &L, const RHS &R) {
1167 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
1168 OverflowingBinaryOperator::NoUnsignedWrap>(
1169 L, R);
1170 }
1171 template <typename LHS, typename RHS>
1172 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
1173 OverflowingBinaryOperator::NoUnsignedWrap>
m_NUWSub(const LHS & L,const RHS & R)1174 m_NUWSub(const LHS &L, const RHS &R) {
1175 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
1176 OverflowingBinaryOperator::NoUnsignedWrap>(
1177 L, R);
1178 }
1179 template <typename LHS, typename RHS>
1180 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
1181 OverflowingBinaryOperator::NoUnsignedWrap>
m_NUWMul(const LHS & L,const RHS & R)1182 m_NUWMul(const LHS &L, const RHS &R) {
1183 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
1184 OverflowingBinaryOperator::NoUnsignedWrap>(
1185 L, R);
1186 }
1187 template <typename LHS, typename RHS>
1188 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
1189 OverflowingBinaryOperator::NoUnsignedWrap>
m_NUWShl(const LHS & L,const RHS & R)1190 m_NUWShl(const LHS &L, const RHS &R) {
1191 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
1192 OverflowingBinaryOperator::NoUnsignedWrap>(
1193 L, R);
1194 }
1195
1196 //===----------------------------------------------------------------------===//
1197 // Class that matches a group of binary opcodes.
1198 //
1199 template <typename LHS_t, typename RHS_t, typename Predicate>
1200 struct BinOpPred_match : Predicate {
1201 LHS_t L;
1202 RHS_t R;
1203
BinOpPred_matchBinOpPred_match1204 BinOpPred_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
1205
matchBinOpPred_match1206 template <typename OpTy> bool match(OpTy *V) {
1207 if (auto *I = dyn_cast<Instruction>(V))
1208 return this->isOpType(I->getOpcode()) && L.match(I->getOperand(0)) &&
1209 R.match(I->getOperand(1));
1210 if (auto *CE = dyn_cast<ConstantExpr>(V))
1211 return this->isOpType(CE->getOpcode()) && L.match(CE->getOperand(0)) &&
1212 R.match(CE->getOperand(1));
1213 return false;
1214 }
1215 };
1216
1217 struct is_shift_op {
isOpTypeis_shift_op1218 bool isOpType(unsigned Opcode) { return Instruction::isShift(Opcode); }
1219 };
1220
1221 struct is_right_shift_op {
isOpTypeis_right_shift_op1222 bool isOpType(unsigned Opcode) {
1223 return Opcode == Instruction::LShr || Opcode == Instruction::AShr;
1224 }
1225 };
1226
1227 struct is_logical_shift_op {
isOpTypeis_logical_shift_op1228 bool isOpType(unsigned Opcode) {
1229 return Opcode == Instruction::LShr || Opcode == Instruction::Shl;
1230 }
1231 };
1232
1233 struct is_bitwiselogic_op {
isOpTypeis_bitwiselogic_op1234 bool isOpType(unsigned Opcode) {
1235 return Instruction::isBitwiseLogicOp(Opcode);
1236 }
1237 };
1238
1239 struct is_idiv_op {
isOpTypeis_idiv_op1240 bool isOpType(unsigned Opcode) {
1241 return Opcode == Instruction::SDiv || Opcode == Instruction::UDiv;
1242 }
1243 };
1244
1245 struct is_irem_op {
isOpTypeis_irem_op1246 bool isOpType(unsigned Opcode) {
1247 return Opcode == Instruction::SRem || Opcode == Instruction::URem;
1248 }
1249 };
1250
1251 /// Matches shift operations.
1252 template <typename LHS, typename RHS>
m_Shift(const LHS & L,const RHS & R)1253 inline BinOpPred_match<LHS, RHS, is_shift_op> m_Shift(const LHS &L,
1254 const RHS &R) {
1255 return BinOpPred_match<LHS, RHS, is_shift_op>(L, R);
1256 }
1257
1258 /// Matches logical shift operations.
1259 template <typename LHS, typename RHS>
m_Shr(const LHS & L,const RHS & R)1260 inline BinOpPred_match<LHS, RHS, is_right_shift_op> m_Shr(const LHS &L,
1261 const RHS &R) {
1262 return BinOpPred_match<LHS, RHS, is_right_shift_op>(L, R);
1263 }
1264
1265 /// Matches logical shift operations.
1266 template <typename LHS, typename RHS>
1267 inline BinOpPred_match<LHS, RHS, is_logical_shift_op>
m_LogicalShift(const LHS & L,const RHS & R)1268 m_LogicalShift(const LHS &L, const RHS &R) {
1269 return BinOpPred_match<LHS, RHS, is_logical_shift_op>(L, R);
1270 }
1271
1272 /// Matches bitwise logic operations.
1273 template <typename LHS, typename RHS>
1274 inline BinOpPred_match<LHS, RHS, is_bitwiselogic_op>
m_BitwiseLogic(const LHS & L,const RHS & R)1275 m_BitwiseLogic(const LHS &L, const RHS &R) {
1276 return BinOpPred_match<LHS, RHS, is_bitwiselogic_op>(L, R);
1277 }
1278
1279 /// Matches integer division operations.
1280 template <typename LHS, typename RHS>
m_IDiv(const LHS & L,const RHS & R)1281 inline BinOpPred_match<LHS, RHS, is_idiv_op> m_IDiv(const LHS &L,
1282 const RHS &R) {
1283 return BinOpPred_match<LHS, RHS, is_idiv_op>(L, R);
1284 }
1285
1286 /// Matches integer remainder operations.
1287 template <typename LHS, typename RHS>
m_IRem(const LHS & L,const RHS & R)1288 inline BinOpPred_match<LHS, RHS, is_irem_op> m_IRem(const LHS &L,
1289 const RHS &R) {
1290 return BinOpPred_match<LHS, RHS, is_irem_op>(L, R);
1291 }
1292
1293 //===----------------------------------------------------------------------===//
1294 // Class that matches exact binary ops.
1295 //
1296 template <typename SubPattern_t> struct Exact_match {
1297 SubPattern_t SubPattern;
1298
Exact_matchExact_match1299 Exact_match(const SubPattern_t &SP) : SubPattern(SP) {}
1300
matchExact_match1301 template <typename OpTy> bool match(OpTy *V) {
1302 if (auto *PEO = dyn_cast<PossiblyExactOperator>(V))
1303 return PEO->isExact() && SubPattern.match(V);
1304 return false;
1305 }
1306 };
1307
m_Exact(const T & SubPattern)1308 template <typename T> inline Exact_match<T> m_Exact(const T &SubPattern) {
1309 return SubPattern;
1310 }
1311
1312 //===----------------------------------------------------------------------===//
1313 // Matchers for CmpInst classes
1314 //
1315
1316 template <typename LHS_t, typename RHS_t, typename Class, typename PredicateTy,
1317 bool Commutable = false>
1318 struct CmpClass_match {
1319 PredicateTy &Predicate;
1320 LHS_t L;
1321 RHS_t R;
1322
1323 // The evaluation order is always stable, regardless of Commutability.
1324 // The LHS is always matched first.
CmpClass_matchCmpClass_match1325 CmpClass_match(PredicateTy &Pred, const LHS_t &LHS, const RHS_t &RHS)
1326 : Predicate(Pred), L(LHS), R(RHS) {}
1327
matchCmpClass_match1328 template <typename OpTy> bool match(OpTy *V) {
1329 if (auto *I = dyn_cast<Class>(V)) {
1330 if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) {
1331 Predicate = I->getPredicate();
1332 return true;
1333 } else if (Commutable && L.match(I->getOperand(1)) &&
1334 R.match(I->getOperand(0))) {
1335 Predicate = I->getSwappedPredicate();
1336 return true;
1337 }
1338 }
1339 return false;
1340 }
1341 };
1342
1343 template <typename LHS, typename RHS>
1344 inline CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate>
m_Cmp(CmpInst::Predicate & Pred,const LHS & L,const RHS & R)1345 m_Cmp(CmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1346 return CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate>(Pred, L, R);
1347 }
1348
1349 template <typename LHS, typename RHS>
1350 inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>
m_ICmp(ICmpInst::Predicate & Pred,const LHS & L,const RHS & R)1351 m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1352 return CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>(Pred, L, R);
1353 }
1354
1355 template <typename LHS, typename RHS>
1356 inline CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>
m_FCmp(FCmpInst::Predicate & Pred,const LHS & L,const RHS & R)1357 m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1358 return CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>(Pred, L, R);
1359 }
1360
1361 //===----------------------------------------------------------------------===//
1362 // Matchers for instructions with a given opcode and number of operands.
1363 //
1364
1365 /// Matches instructions with Opcode and three operands.
1366 template <typename T0, unsigned Opcode> struct OneOps_match {
1367 T0 Op1;
1368
OneOps_matchOneOps_match1369 OneOps_match(const T0 &Op1) : Op1(Op1) {}
1370
matchOneOps_match1371 template <typename OpTy> bool match(OpTy *V) {
1372 if (V->getValueID() == Value::InstructionVal + Opcode) {
1373 auto *I = cast<Instruction>(V);
1374 return Op1.match(I->getOperand(0));
1375 }
1376 return false;
1377 }
1378 };
1379
1380 /// Matches instructions with Opcode and three operands.
1381 template <typename T0, typename T1, unsigned Opcode> struct TwoOps_match {
1382 T0 Op1;
1383 T1 Op2;
1384
TwoOps_matchTwoOps_match1385 TwoOps_match(const T0 &Op1, const T1 &Op2) : Op1(Op1), Op2(Op2) {}
1386
matchTwoOps_match1387 template <typename OpTy> bool match(OpTy *V) {
1388 if (V->getValueID() == Value::InstructionVal + Opcode) {
1389 auto *I = cast<Instruction>(V);
1390 return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1));
1391 }
1392 return false;
1393 }
1394 };
1395
1396 /// Matches instructions with Opcode and three operands.
1397 template <typename T0, typename T1, typename T2, unsigned Opcode>
1398 struct ThreeOps_match {
1399 T0 Op1;
1400 T1 Op2;
1401 T2 Op3;
1402
ThreeOps_matchThreeOps_match1403 ThreeOps_match(const T0 &Op1, const T1 &Op2, const T2 &Op3)
1404 : Op1(Op1), Op2(Op2), Op3(Op3) {}
1405
matchThreeOps_match1406 template <typename OpTy> bool match(OpTy *V) {
1407 if (V->getValueID() == Value::InstructionVal + Opcode) {
1408 auto *I = cast<Instruction>(V);
1409 return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1)) &&
1410 Op3.match(I->getOperand(2));
1411 }
1412 return false;
1413 }
1414 };
1415
1416 /// Matches SelectInst.
1417 template <typename Cond, typename LHS, typename RHS>
1418 inline ThreeOps_match<Cond, LHS, RHS, Instruction::Select>
m_Select(const Cond & C,const LHS & L,const RHS & R)1419 m_Select(const Cond &C, const LHS &L, const RHS &R) {
1420 return ThreeOps_match<Cond, LHS, RHS, Instruction::Select>(C, L, R);
1421 }
1422
1423 /// This matches a select of two constants, e.g.:
1424 /// m_SelectCst<-1, 0>(m_Value(V))
1425 template <int64_t L, int64_t R, typename Cond>
1426 inline ThreeOps_match<Cond, constantint_match<L>, constantint_match<R>,
1427 Instruction::Select>
m_SelectCst(const Cond & C)1428 m_SelectCst(const Cond &C) {
1429 return m_Select(C, m_ConstantInt<L>(), m_ConstantInt<R>());
1430 }
1431
1432 /// Matches FreezeInst.
1433 template <typename OpTy>
m_Freeze(const OpTy & Op)1434 inline OneOps_match<OpTy, Instruction::Freeze> m_Freeze(const OpTy &Op) {
1435 return OneOps_match<OpTy, Instruction::Freeze>(Op);
1436 }
1437
1438 /// Matches InsertElementInst.
1439 template <typename Val_t, typename Elt_t, typename Idx_t>
1440 inline ThreeOps_match<Val_t, Elt_t, Idx_t, Instruction::InsertElement>
m_InsertElt(const Val_t & Val,const Elt_t & Elt,const Idx_t & Idx)1441 m_InsertElt(const Val_t &Val, const Elt_t &Elt, const Idx_t &Idx) {
1442 return ThreeOps_match<Val_t, Elt_t, Idx_t, Instruction::InsertElement>(
1443 Val, Elt, Idx);
1444 }
1445
1446 /// Matches ExtractElementInst.
1447 template <typename Val_t, typename Idx_t>
1448 inline TwoOps_match<Val_t, Idx_t, Instruction::ExtractElement>
m_ExtractElt(const Val_t & Val,const Idx_t & Idx)1449 m_ExtractElt(const Val_t &Val, const Idx_t &Idx) {
1450 return TwoOps_match<Val_t, Idx_t, Instruction::ExtractElement>(Val, Idx);
1451 }
1452
1453 /// Matches shuffle.
1454 template <typename T0, typename T1, typename T2> struct Shuffle_match {
1455 T0 Op1;
1456 T1 Op2;
1457 T2 Mask;
1458
Shuffle_matchShuffle_match1459 Shuffle_match(const T0 &Op1, const T1 &Op2, const T2 &Mask)
1460 : Op1(Op1), Op2(Op2), Mask(Mask) {}
1461
matchShuffle_match1462 template <typename OpTy> bool match(OpTy *V) {
1463 if (auto *I = dyn_cast<ShuffleVectorInst>(V)) {
1464 return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1)) &&
1465 Mask.match(I->getShuffleMask());
1466 }
1467 return false;
1468 }
1469 };
1470
1471 struct m_Mask {
1472 ArrayRef<int> &MaskRef;
m_Maskm_Mask1473 m_Mask(ArrayRef<int> &MaskRef) : MaskRef(MaskRef) {}
matchm_Mask1474 bool match(ArrayRef<int> Mask) {
1475 MaskRef = Mask;
1476 return true;
1477 }
1478 };
1479
1480 struct m_ZeroMask {
matchm_ZeroMask1481 bool match(ArrayRef<int> Mask) {
1482 return all_of(Mask, [](int Elem) { return Elem == 0 || Elem == -1; });
1483 }
1484 };
1485
1486 struct m_SpecificMask {
1487 ArrayRef<int> &MaskRef;
m_SpecificMaskm_SpecificMask1488 m_SpecificMask(ArrayRef<int> &MaskRef) : MaskRef(MaskRef) {}
matchm_SpecificMask1489 bool match(ArrayRef<int> Mask) { return MaskRef == Mask; }
1490 };
1491
1492 struct m_SplatOrUndefMask {
1493 int &SplatIndex;
m_SplatOrUndefMaskm_SplatOrUndefMask1494 m_SplatOrUndefMask(int &SplatIndex) : SplatIndex(SplatIndex) {}
matchm_SplatOrUndefMask1495 bool match(ArrayRef<int> Mask) {
1496 auto First = find_if(Mask, [](int Elem) { return Elem != -1; });
1497 if (First == Mask.end())
1498 return false;
1499 SplatIndex = *First;
1500 return all_of(Mask,
1501 [First](int Elem) { return Elem == *First || Elem == -1; });
1502 }
1503 };
1504
1505 /// Matches ShuffleVectorInst independently of mask value.
1506 template <typename V1_t, typename V2_t>
1507 inline TwoOps_match<V1_t, V2_t, Instruction::ShuffleVector>
m_Shuffle(const V1_t & v1,const V2_t & v2)1508 m_Shuffle(const V1_t &v1, const V2_t &v2) {
1509 return TwoOps_match<V1_t, V2_t, Instruction::ShuffleVector>(v1, v2);
1510 }
1511
1512 template <typename V1_t, typename V2_t, typename Mask_t>
1513 inline Shuffle_match<V1_t, V2_t, Mask_t>
m_Shuffle(const V1_t & v1,const V2_t & v2,const Mask_t & mask)1514 m_Shuffle(const V1_t &v1, const V2_t &v2, const Mask_t &mask) {
1515 return Shuffle_match<V1_t, V2_t, Mask_t>(v1, v2, mask);
1516 }
1517
1518 /// Matches LoadInst.
1519 template <typename OpTy>
m_Load(const OpTy & Op)1520 inline OneOps_match<OpTy, Instruction::Load> m_Load(const OpTy &Op) {
1521 return OneOps_match<OpTy, Instruction::Load>(Op);
1522 }
1523
1524 /// Matches StoreInst.
1525 template <typename ValueOpTy, typename PointerOpTy>
1526 inline TwoOps_match<ValueOpTy, PointerOpTy, Instruction::Store>
m_Store(const ValueOpTy & ValueOp,const PointerOpTy & PointerOp)1527 m_Store(const ValueOpTy &ValueOp, const PointerOpTy &PointerOp) {
1528 return TwoOps_match<ValueOpTy, PointerOpTy, Instruction::Store>(ValueOp,
1529 PointerOp);
1530 }
1531
1532 //===----------------------------------------------------------------------===//
1533 // Matchers for CastInst classes
1534 //
1535
1536 template <typename Op_t, unsigned Opcode> struct CastClass_match {
1537 Op_t Op;
1538
CastClass_matchCastClass_match1539 CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {}
1540
matchCastClass_match1541 template <typename OpTy> bool match(OpTy *V) {
1542 if (auto *O = dyn_cast<Operator>(V))
1543 return O->getOpcode() == Opcode && Op.match(O->getOperand(0));
1544 return false;
1545 }
1546 };
1547
1548 /// Matches BitCast.
1549 template <typename OpTy>
m_BitCast(const OpTy & Op)1550 inline CastClass_match<OpTy, Instruction::BitCast> m_BitCast(const OpTy &Op) {
1551 return CastClass_match<OpTy, Instruction::BitCast>(Op);
1552 }
1553
1554 /// Matches PtrToInt.
1555 template <typename OpTy>
m_PtrToInt(const OpTy & Op)1556 inline CastClass_match<OpTy, Instruction::PtrToInt> m_PtrToInt(const OpTy &Op) {
1557 return CastClass_match<OpTy, Instruction::PtrToInt>(Op);
1558 }
1559
1560 /// Matches IntToPtr.
1561 template <typename OpTy>
m_IntToPtr(const OpTy & Op)1562 inline CastClass_match<OpTy, Instruction::IntToPtr> m_IntToPtr(const OpTy &Op) {
1563 return CastClass_match<OpTy, Instruction::IntToPtr>(Op);
1564 }
1565
1566 /// Matches Trunc.
1567 template <typename OpTy>
m_Trunc(const OpTy & Op)1568 inline CastClass_match<OpTy, Instruction::Trunc> m_Trunc(const OpTy &Op) {
1569 return CastClass_match<OpTy, Instruction::Trunc>(Op);
1570 }
1571
1572 template <typename OpTy>
1573 inline match_combine_or<CastClass_match<OpTy, Instruction::Trunc>, OpTy>
m_TruncOrSelf(const OpTy & Op)1574 m_TruncOrSelf(const OpTy &Op) {
1575 return m_CombineOr(m_Trunc(Op), Op);
1576 }
1577
1578 /// Matches SExt.
1579 template <typename OpTy>
m_SExt(const OpTy & Op)1580 inline CastClass_match<OpTy, Instruction::SExt> m_SExt(const OpTy &Op) {
1581 return CastClass_match<OpTy, Instruction::SExt>(Op);
1582 }
1583
1584 /// Matches ZExt.
1585 template <typename OpTy>
m_ZExt(const OpTy & Op)1586 inline CastClass_match<OpTy, Instruction::ZExt> m_ZExt(const OpTy &Op) {
1587 return CastClass_match<OpTy, Instruction::ZExt>(Op);
1588 }
1589
1590 template <typename OpTy>
1591 inline match_combine_or<CastClass_match<OpTy, Instruction::ZExt>, OpTy>
m_ZExtOrSelf(const OpTy & Op)1592 m_ZExtOrSelf(const OpTy &Op) {
1593 return m_CombineOr(m_ZExt(Op), Op);
1594 }
1595
1596 template <typename OpTy>
1597 inline match_combine_or<CastClass_match<OpTy, Instruction::SExt>, OpTy>
m_SExtOrSelf(const OpTy & Op)1598 m_SExtOrSelf(const OpTy &Op) {
1599 return m_CombineOr(m_SExt(Op), Op);
1600 }
1601
1602 template <typename OpTy>
1603 inline match_combine_or<CastClass_match<OpTy, Instruction::ZExt>,
1604 CastClass_match<OpTy, Instruction::SExt>>
m_ZExtOrSExt(const OpTy & Op)1605 m_ZExtOrSExt(const OpTy &Op) {
1606 return m_CombineOr(m_ZExt(Op), m_SExt(Op));
1607 }
1608
1609 template <typename OpTy>
1610 inline match_combine_or<
1611 match_combine_or<CastClass_match<OpTy, Instruction::ZExt>,
1612 CastClass_match<OpTy, Instruction::SExt>>,
1613 OpTy>
m_ZExtOrSExtOrSelf(const OpTy & Op)1614 m_ZExtOrSExtOrSelf(const OpTy &Op) {
1615 return m_CombineOr(m_ZExtOrSExt(Op), Op);
1616 }
1617
1618 template <typename OpTy>
m_UIToFP(const OpTy & Op)1619 inline CastClass_match<OpTy, Instruction::UIToFP> m_UIToFP(const OpTy &Op) {
1620 return CastClass_match<OpTy, Instruction::UIToFP>(Op);
1621 }
1622
1623 template <typename OpTy>
m_SIToFP(const OpTy & Op)1624 inline CastClass_match<OpTy, Instruction::SIToFP> m_SIToFP(const OpTy &Op) {
1625 return CastClass_match<OpTy, Instruction::SIToFP>(Op);
1626 }
1627
1628 template <typename OpTy>
m_FPToUI(const OpTy & Op)1629 inline CastClass_match<OpTy, Instruction::FPToUI> m_FPToUI(const OpTy &Op) {
1630 return CastClass_match<OpTy, Instruction::FPToUI>(Op);
1631 }
1632
1633 template <typename OpTy>
m_FPToSI(const OpTy & Op)1634 inline CastClass_match<OpTy, Instruction::FPToSI> m_FPToSI(const OpTy &Op) {
1635 return CastClass_match<OpTy, Instruction::FPToSI>(Op);
1636 }
1637
1638 template <typename OpTy>
m_FPTrunc(const OpTy & Op)1639 inline CastClass_match<OpTy, Instruction::FPTrunc> m_FPTrunc(const OpTy &Op) {
1640 return CastClass_match<OpTy, Instruction::FPTrunc>(Op);
1641 }
1642
1643 template <typename OpTy>
m_FPExt(const OpTy & Op)1644 inline CastClass_match<OpTy, Instruction::FPExt> m_FPExt(const OpTy &Op) {
1645 return CastClass_match<OpTy, Instruction::FPExt>(Op);
1646 }
1647
1648 //===----------------------------------------------------------------------===//
1649 // Matchers for control flow.
1650 //
1651
1652 struct br_match {
1653 BasicBlock *&Succ;
1654
br_matchbr_match1655 br_match(BasicBlock *&Succ) : Succ(Succ) {}
1656
matchbr_match1657 template <typename OpTy> bool match(OpTy *V) {
1658 if (auto *BI = dyn_cast<BranchInst>(V))
1659 if (BI->isUnconditional()) {
1660 Succ = BI->getSuccessor(0);
1661 return true;
1662 }
1663 return false;
1664 }
1665 };
1666
m_UnconditionalBr(BasicBlock * & Succ)1667 inline br_match m_UnconditionalBr(BasicBlock *&Succ) { return br_match(Succ); }
1668
1669 template <typename Cond_t, typename TrueBlock_t, typename FalseBlock_t>
1670 struct brc_match {
1671 Cond_t Cond;
1672 TrueBlock_t T;
1673 FalseBlock_t F;
1674
brc_matchbrc_match1675 brc_match(const Cond_t &C, const TrueBlock_t &t, const FalseBlock_t &f)
1676 : Cond(C), T(t), F(f) {}
1677
matchbrc_match1678 template <typename OpTy> bool match(OpTy *V) {
1679 if (auto *BI = dyn_cast<BranchInst>(V))
1680 if (BI->isConditional() && Cond.match(BI->getCondition()))
1681 return T.match(BI->getSuccessor(0)) && F.match(BI->getSuccessor(1));
1682 return false;
1683 }
1684 };
1685
1686 template <typename Cond_t>
1687 inline brc_match<Cond_t, bind_ty<BasicBlock>, bind_ty<BasicBlock>>
m_Br(const Cond_t & C,BasicBlock * & T,BasicBlock * & F)1688 m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) {
1689 return brc_match<Cond_t, bind_ty<BasicBlock>, bind_ty<BasicBlock>>(
1690 C, m_BasicBlock(T), m_BasicBlock(F));
1691 }
1692
1693 template <typename Cond_t, typename TrueBlock_t, typename FalseBlock_t>
1694 inline brc_match<Cond_t, TrueBlock_t, FalseBlock_t>
m_Br(const Cond_t & C,const TrueBlock_t & T,const FalseBlock_t & F)1695 m_Br(const Cond_t &C, const TrueBlock_t &T, const FalseBlock_t &F) {
1696 return brc_match<Cond_t, TrueBlock_t, FalseBlock_t>(C, T, F);
1697 }
1698
1699 //===----------------------------------------------------------------------===//
1700 // Matchers for max/min idioms, eg: "select (sgt x, y), x, y" -> smax(x,y).
1701 //
1702
1703 template <typename CmpInst_t, typename LHS_t, typename RHS_t, typename Pred_t,
1704 bool Commutable = false>
1705 struct MaxMin_match {
1706 LHS_t L;
1707 RHS_t R;
1708
1709 // The evaluation order is always stable, regardless of Commutability.
1710 // The LHS is always matched first.
MaxMin_matchMaxMin_match1711 MaxMin_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
1712
matchMaxMin_match1713 template <typename OpTy> bool match(OpTy *V) {
1714 if (auto *II = dyn_cast<IntrinsicInst>(V)) {
1715 Intrinsic::ID IID = II->getIntrinsicID();
1716 if ((IID == Intrinsic::smax && Pred_t::match(ICmpInst::ICMP_SGT)) ||
1717 (IID == Intrinsic::smin && Pred_t::match(ICmpInst::ICMP_SLT)) ||
1718 (IID == Intrinsic::umax && Pred_t::match(ICmpInst::ICMP_UGT)) ||
1719 (IID == Intrinsic::umin && Pred_t::match(ICmpInst::ICMP_ULT))) {
1720 Value *LHS = II->getOperand(0), *RHS = II->getOperand(1);
1721 return (L.match(LHS) && R.match(RHS)) ||
1722 (Commutable && L.match(RHS) && R.match(LHS));
1723 }
1724 }
1725 // Look for "(x pred y) ? x : y" or "(x pred y) ? y : x".
1726 auto *SI = dyn_cast<SelectInst>(V);
1727 if (!SI)
1728 return false;
1729 auto *Cmp = dyn_cast<CmpInst_t>(SI->getCondition());
1730 if (!Cmp)
1731 return false;
1732 // At this point we have a select conditioned on a comparison. Check that
1733 // it is the values returned by the select that are being compared.
1734 Value *TrueVal = SI->getTrueValue();
1735 Value *FalseVal = SI->getFalseValue();
1736 Value *LHS = Cmp->getOperand(0);
1737 Value *RHS = Cmp->getOperand(1);
1738 if ((TrueVal != LHS || FalseVal != RHS) &&
1739 (TrueVal != RHS || FalseVal != LHS))
1740 return false;
1741 typename CmpInst_t::Predicate Pred =
1742 LHS == TrueVal ? Cmp->getPredicate() : Cmp->getInversePredicate();
1743 // Does "(x pred y) ? x : y" represent the desired max/min operation?
1744 if (!Pred_t::match(Pred))
1745 return false;
1746 // It does! Bind the operands.
1747 return (L.match(LHS) && R.match(RHS)) ||
1748 (Commutable && L.match(RHS) && R.match(LHS));
1749 }
1750 };
1751
1752 /// Helper class for identifying signed max predicates.
1753 struct smax_pred_ty {
matchsmax_pred_ty1754 static bool match(ICmpInst::Predicate Pred) {
1755 return Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE;
1756 }
1757 };
1758
1759 /// Helper class for identifying signed min predicates.
1760 struct smin_pred_ty {
matchsmin_pred_ty1761 static bool match(ICmpInst::Predicate Pred) {
1762 return Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_SLE;
1763 }
1764 };
1765
1766 /// Helper class for identifying unsigned max predicates.
1767 struct umax_pred_ty {
matchumax_pred_ty1768 static bool match(ICmpInst::Predicate Pred) {
1769 return Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE;
1770 }
1771 };
1772
1773 /// Helper class for identifying unsigned min predicates.
1774 struct umin_pred_ty {
matchumin_pred_ty1775 static bool match(ICmpInst::Predicate Pred) {
1776 return Pred == CmpInst::ICMP_ULT || Pred == CmpInst::ICMP_ULE;
1777 }
1778 };
1779
1780 /// Helper class for identifying ordered max predicates.
1781 struct ofmax_pred_ty {
matchofmax_pred_ty1782 static bool match(FCmpInst::Predicate Pred) {
1783 return Pred == CmpInst::FCMP_OGT || Pred == CmpInst::FCMP_OGE;
1784 }
1785 };
1786
1787 /// Helper class for identifying ordered min predicates.
1788 struct ofmin_pred_ty {
matchofmin_pred_ty1789 static bool match(FCmpInst::Predicate Pred) {
1790 return Pred == CmpInst::FCMP_OLT || Pred == CmpInst::FCMP_OLE;
1791 }
1792 };
1793
1794 /// Helper class for identifying unordered max predicates.
1795 struct ufmax_pred_ty {
matchufmax_pred_ty1796 static bool match(FCmpInst::Predicate Pred) {
1797 return Pred == CmpInst::FCMP_UGT || Pred == CmpInst::FCMP_UGE;
1798 }
1799 };
1800
1801 /// Helper class for identifying unordered min predicates.
1802 struct ufmin_pred_ty {
matchufmin_pred_ty1803 static bool match(FCmpInst::Predicate Pred) {
1804 return Pred == CmpInst::FCMP_ULT || Pred == CmpInst::FCMP_ULE;
1805 }
1806 };
1807
1808 template <typename LHS, typename RHS>
m_SMax(const LHS & L,const RHS & R)1809 inline MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty> m_SMax(const LHS &L,
1810 const RHS &R) {
1811 return MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty>(L, R);
1812 }
1813
1814 template <typename LHS, typename RHS>
m_SMin(const LHS & L,const RHS & R)1815 inline MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty> m_SMin(const LHS &L,
1816 const RHS &R) {
1817 return MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty>(L, R);
1818 }
1819
1820 template <typename LHS, typename RHS>
m_UMax(const LHS & L,const RHS & R)1821 inline MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty> m_UMax(const LHS &L,
1822 const RHS &R) {
1823 return MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty>(L, R);
1824 }
1825
1826 template <typename LHS, typename RHS>
m_UMin(const LHS & L,const RHS & R)1827 inline MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty> m_UMin(const LHS &L,
1828 const RHS &R) {
1829 return MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty>(L, R);
1830 }
1831
1832 template <typename LHS, typename RHS>
1833 inline match_combine_or<
1834 match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty>,
1835 MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty>>,
1836 match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty>,
1837 MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty>>>
m_MaxOrMin(const LHS & L,const RHS & R)1838 m_MaxOrMin(const LHS &L, const RHS &R) {
1839 return m_CombineOr(m_CombineOr(m_SMax(L, R), m_SMin(L, R)),
1840 m_CombineOr(m_UMax(L, R), m_UMin(L, R)));
1841 }
1842
1843 /// Match an 'ordered' floating point maximum function.
1844 /// Floating point has one special value 'NaN'. Therefore, there is no total
1845 /// order. However, if we can ignore the 'NaN' value (for example, because of a
1846 /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum'
1847 /// semantics. In the presence of 'NaN' we have to preserve the original
1848 /// select(fcmp(ogt/ge, L, R), L, R) semantics matched by this predicate.
1849 ///
1850 /// max(L, R) iff L and R are not NaN
1851 /// m_OrdFMax(L, R) = R iff L or R are NaN
1852 template <typename LHS, typename RHS>
m_OrdFMax(const LHS & L,const RHS & R)1853 inline MaxMin_match<FCmpInst, LHS, RHS, ofmax_pred_ty> m_OrdFMax(const LHS &L,
1854 const RHS &R) {
1855 return MaxMin_match<FCmpInst, LHS, RHS, ofmax_pred_ty>(L, R);
1856 }
1857
1858 /// Match an 'ordered' floating point minimum function.
1859 /// Floating point has one special value 'NaN'. Therefore, there is no total
1860 /// order. However, if we can ignore the 'NaN' value (for example, because of a
1861 /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum'
1862 /// semantics. In the presence of 'NaN' we have to preserve the original
1863 /// select(fcmp(olt/le, L, R), L, R) semantics matched by this predicate.
1864 ///
1865 /// min(L, R) iff L and R are not NaN
1866 /// m_OrdFMin(L, R) = R iff L or R are NaN
1867 template <typename LHS, typename RHS>
m_OrdFMin(const LHS & L,const RHS & R)1868 inline MaxMin_match<FCmpInst, LHS, RHS, ofmin_pred_ty> m_OrdFMin(const LHS &L,
1869 const RHS &R) {
1870 return MaxMin_match<FCmpInst, LHS, RHS, ofmin_pred_ty>(L, R);
1871 }
1872
1873 /// Match an 'unordered' floating point maximum function.
1874 /// Floating point has one special value 'NaN'. Therefore, there is no total
1875 /// order. However, if we can ignore the 'NaN' value (for example, because of a
1876 /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum'
1877 /// semantics. In the presence of 'NaN' we have to preserve the original
1878 /// select(fcmp(ugt/ge, L, R), L, R) semantics matched by this predicate.
1879 ///
1880 /// max(L, R) iff L and R are not NaN
1881 /// m_UnordFMax(L, R) = L iff L or R are NaN
1882 template <typename LHS, typename RHS>
1883 inline MaxMin_match<FCmpInst, LHS, RHS, ufmax_pred_ty>
m_UnordFMax(const LHS & L,const RHS & R)1884 m_UnordFMax(const LHS &L, const RHS &R) {
1885 return MaxMin_match<FCmpInst, LHS, RHS, ufmax_pred_ty>(L, R);
1886 }
1887
1888 /// Match an 'unordered' floating point minimum function.
1889 /// Floating point has one special value 'NaN'. Therefore, there is no total
1890 /// order. However, if we can ignore the 'NaN' value (for example, because of a
1891 /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum'
1892 /// semantics. In the presence of 'NaN' we have to preserve the original
1893 /// select(fcmp(ult/le, L, R), L, R) semantics matched by this predicate.
1894 ///
1895 /// min(L, R) iff L and R are not NaN
1896 /// m_UnordFMin(L, R) = L iff L or R are NaN
1897 template <typename LHS, typename RHS>
1898 inline MaxMin_match<FCmpInst, LHS, RHS, ufmin_pred_ty>
m_UnordFMin(const LHS & L,const RHS & R)1899 m_UnordFMin(const LHS &L, const RHS &R) {
1900 return MaxMin_match<FCmpInst, LHS, RHS, ufmin_pred_ty>(L, R);
1901 }
1902
1903 //===----------------------------------------------------------------------===//
1904 // Matchers for overflow check patterns: e.g. (a + b) u< a, (a ^ -1) <u b
1905 // Note that S might be matched to other instructions than AddInst.
1906 //
1907
1908 template <typename LHS_t, typename RHS_t, typename Sum_t>
1909 struct UAddWithOverflow_match {
1910 LHS_t L;
1911 RHS_t R;
1912 Sum_t S;
1913
UAddWithOverflow_matchUAddWithOverflow_match1914 UAddWithOverflow_match(const LHS_t &L, const RHS_t &R, const Sum_t &S)
1915 : L(L), R(R), S(S) {}
1916
matchUAddWithOverflow_match1917 template <typename OpTy> bool match(OpTy *V) {
1918 Value *ICmpLHS, *ICmpRHS;
1919 ICmpInst::Predicate Pred;
1920 if (!m_ICmp(Pred, m_Value(ICmpLHS), m_Value(ICmpRHS)).match(V))
1921 return false;
1922
1923 Value *AddLHS, *AddRHS;
1924 auto AddExpr = m_Add(m_Value(AddLHS), m_Value(AddRHS));
1925
1926 // (a + b) u< a, (a + b) u< b
1927 if (Pred == ICmpInst::ICMP_ULT)
1928 if (AddExpr.match(ICmpLHS) && (ICmpRHS == AddLHS || ICmpRHS == AddRHS))
1929 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS);
1930
1931 // a >u (a + b), b >u (a + b)
1932 if (Pred == ICmpInst::ICMP_UGT)
1933 if (AddExpr.match(ICmpRHS) && (ICmpLHS == AddLHS || ICmpLHS == AddRHS))
1934 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS);
1935
1936 Value *Op1;
1937 auto XorExpr = m_OneUse(m_Xor(m_Value(Op1), m_AllOnes()));
1938 // (a ^ -1) <u b
1939 if (Pred == ICmpInst::ICMP_ULT) {
1940 if (XorExpr.match(ICmpLHS))
1941 return L.match(Op1) && R.match(ICmpRHS) && S.match(ICmpLHS);
1942 }
1943 // b > u (a ^ -1)
1944 if (Pred == ICmpInst::ICMP_UGT) {
1945 if (XorExpr.match(ICmpRHS))
1946 return L.match(Op1) && R.match(ICmpLHS) && S.match(ICmpRHS);
1947 }
1948
1949 // Match special-case for increment-by-1.
1950 if (Pred == ICmpInst::ICMP_EQ) {
1951 // (a + 1) == 0
1952 // (1 + a) == 0
1953 if (AddExpr.match(ICmpLHS) && m_ZeroInt().match(ICmpRHS) &&
1954 (m_One().match(AddLHS) || m_One().match(AddRHS)))
1955 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS);
1956 // 0 == (a + 1)
1957 // 0 == (1 + a)
1958 if (m_ZeroInt().match(ICmpLHS) && AddExpr.match(ICmpRHS) &&
1959 (m_One().match(AddLHS) || m_One().match(AddRHS)))
1960 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS);
1961 }
1962
1963 return false;
1964 }
1965 };
1966
1967 /// Match an icmp instruction checking for unsigned overflow on addition.
1968 ///
1969 /// S is matched to the addition whose result is being checked for overflow, and
1970 /// L and R are matched to the LHS and RHS of S.
1971 template <typename LHS_t, typename RHS_t, typename Sum_t>
1972 UAddWithOverflow_match<LHS_t, RHS_t, Sum_t>
m_UAddWithOverflow(const LHS_t & L,const RHS_t & R,const Sum_t & S)1973 m_UAddWithOverflow(const LHS_t &L, const RHS_t &R, const Sum_t &S) {
1974 return UAddWithOverflow_match<LHS_t, RHS_t, Sum_t>(L, R, S);
1975 }
1976
1977 template <typename Opnd_t> struct Argument_match {
1978 unsigned OpI;
1979 Opnd_t Val;
1980
Argument_matchArgument_match1981 Argument_match(unsigned OpIdx, const Opnd_t &V) : OpI(OpIdx), Val(V) {}
1982
matchArgument_match1983 template <typename OpTy> bool match(OpTy *V) {
1984 // FIXME: Should likely be switched to use `CallBase`.
1985 if (const auto *CI = dyn_cast<CallInst>(V))
1986 return Val.match(CI->getArgOperand(OpI));
1987 return false;
1988 }
1989 };
1990
1991 /// Match an argument.
1992 template <unsigned OpI, typename Opnd_t>
m_Argument(const Opnd_t & Op)1993 inline Argument_match<Opnd_t> m_Argument(const Opnd_t &Op) {
1994 return Argument_match<Opnd_t>(OpI, Op);
1995 }
1996
1997 /// Intrinsic matchers.
1998 struct IntrinsicID_match {
1999 unsigned ID;
2000
IntrinsicID_matchIntrinsicID_match2001 IntrinsicID_match(Intrinsic::ID IntrID) : ID(IntrID) {}
2002
matchIntrinsicID_match2003 template <typename OpTy> bool match(OpTy *V) {
2004 if (const auto *CI = dyn_cast<CallInst>(V))
2005 if (const auto *F = CI->getCalledFunction())
2006 return F->getIntrinsicID() == ID;
2007 return false;
2008 }
2009 };
2010
2011 /// Intrinsic matches are combinations of ID matchers, and argument
2012 /// matchers. Higher arity matcher are defined recursively in terms of and-ing
2013 /// them with lower arity matchers. Here's some convenient typedefs for up to
2014 /// several arguments, and more can be added as needed
2015 template <typename T0 = void, typename T1 = void, typename T2 = void,
2016 typename T3 = void, typename T4 = void, typename T5 = void,
2017 typename T6 = void, typename T7 = void, typename T8 = void,
2018 typename T9 = void, typename T10 = void>
2019 struct m_Intrinsic_Ty;
2020 template <typename T0> struct m_Intrinsic_Ty<T0> {
2021 using Ty = match_combine_and<IntrinsicID_match, Argument_match<T0>>;
2022 };
2023 template <typename T0, typename T1> struct m_Intrinsic_Ty<T0, T1> {
2024 using Ty =
2025 match_combine_and<typename m_Intrinsic_Ty<T0>::Ty, Argument_match<T1>>;
2026 };
2027 template <typename T0, typename T1, typename T2>
2028 struct m_Intrinsic_Ty<T0, T1, T2> {
2029 using Ty =
2030 match_combine_and<typename m_Intrinsic_Ty<T0, T1>::Ty,
2031 Argument_match<T2>>;
2032 };
2033 template <typename T0, typename T1, typename T2, typename T3>
2034 struct m_Intrinsic_Ty<T0, T1, T2, T3> {
2035 using Ty =
2036 match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2>::Ty,
2037 Argument_match<T3>>;
2038 };
2039
2040 template <typename T0, typename T1, typename T2, typename T3, typename T4>
2041 struct m_Intrinsic_Ty<T0, T1, T2, T3, T4> {
2042 using Ty = match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2, T3>::Ty,
2043 Argument_match<T4>>;
2044 };
2045
2046 template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5>
2047 struct m_Intrinsic_Ty<T0, T1, T2, T3, T4, T5> {
2048 using Ty = match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2, T3, T4>::Ty,
2049 Argument_match<T5>>;
2050 };
2051
2052 /// Match intrinsic calls like this:
2053 /// m_Intrinsic<Intrinsic::fabs>(m_Value(X))
2054 template <Intrinsic::ID IntrID> inline IntrinsicID_match m_Intrinsic() {
2055 return IntrinsicID_match(IntrID);
2056 }
2057
2058 template <Intrinsic::ID IntrID, typename T0>
2059 inline typename m_Intrinsic_Ty<T0>::Ty m_Intrinsic(const T0 &Op0) {
2060 return m_CombineAnd(m_Intrinsic<IntrID>(), m_Argument<0>(Op0));
2061 }
2062
2063 template <Intrinsic::ID IntrID, typename T0, typename T1>
2064 inline typename m_Intrinsic_Ty<T0, T1>::Ty m_Intrinsic(const T0 &Op0,
2065 const T1 &Op1) {
2066 return m_CombineAnd(m_Intrinsic<IntrID>(Op0), m_Argument<1>(Op1));
2067 }
2068
2069 template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2>
2070 inline typename m_Intrinsic_Ty<T0, T1, T2>::Ty
2071 m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2) {
2072 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1), m_Argument<2>(Op2));
2073 }
2074
2075 template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2,
2076 typename T3>
2077 inline typename m_Intrinsic_Ty<T0, T1, T2, T3>::Ty
2078 m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3) {
2079 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2), m_Argument<3>(Op3));
2080 }
2081
2082 template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2,
2083 typename T3, typename T4>
2084 inline typename m_Intrinsic_Ty<T0, T1, T2, T3, T4>::Ty
2085 m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3,
2086 const T4 &Op4) {
2087 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2, Op3),
2088 m_Argument<4>(Op4));
2089 }
2090
2091 template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2,
2092 typename T3, typename T4, typename T5>
2093 inline typename m_Intrinsic_Ty<T0, T1, T2, T3, T4, T5>::Ty
2094 m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3,
2095 const T4 &Op4, const T5 &Op5) {
2096 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2, Op3, Op4),
2097 m_Argument<5>(Op5));
2098 }
2099
2100 // Helper intrinsic matching specializations.
2101 template <typename Opnd0>
2102 inline typename m_Intrinsic_Ty<Opnd0>::Ty m_BitReverse(const Opnd0 &Op0) {
2103 return m_Intrinsic<Intrinsic::bitreverse>(Op0);
2104 }
2105
2106 template <typename Opnd0>
2107 inline typename m_Intrinsic_Ty<Opnd0>::Ty m_BSwap(const Opnd0 &Op0) {
2108 return m_Intrinsic<Intrinsic::bswap>(Op0);
2109 }
2110
2111 template <typename Opnd0>
2112 inline typename m_Intrinsic_Ty<Opnd0>::Ty m_FAbs(const Opnd0 &Op0) {
2113 return m_Intrinsic<Intrinsic::fabs>(Op0);
2114 }
2115
2116 template <typename Opnd0>
2117 inline typename m_Intrinsic_Ty<Opnd0>::Ty m_FCanonicalize(const Opnd0 &Op0) {
2118 return m_Intrinsic<Intrinsic::canonicalize>(Op0);
2119 }
2120
2121 template <typename Opnd0, typename Opnd1>
2122 inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMin(const Opnd0 &Op0,
2123 const Opnd1 &Op1) {
2124 return m_Intrinsic<Intrinsic::minnum>(Op0, Op1);
2125 }
2126
2127 template <typename Opnd0, typename Opnd1>
2128 inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMax(const Opnd0 &Op0,
2129 const Opnd1 &Op1) {
2130 return m_Intrinsic<Intrinsic::maxnum>(Op0, Op1);
2131 }
2132
2133 template <typename Opnd0, typename Opnd1, typename Opnd2>
2134 inline typename m_Intrinsic_Ty<Opnd0, Opnd1, Opnd2>::Ty
2135 m_FShl(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2) {
2136 return m_Intrinsic<Intrinsic::fshl>(Op0, Op1, Op2);
2137 }
2138
2139 template <typename Opnd0, typename Opnd1, typename Opnd2>
2140 inline typename m_Intrinsic_Ty<Opnd0, Opnd1, Opnd2>::Ty
2141 m_FShr(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2) {
2142 return m_Intrinsic<Intrinsic::fshr>(Op0, Op1, Op2);
2143 }
2144
2145 //===----------------------------------------------------------------------===//
2146 // Matchers for two-operands operators with the operators in either order
2147 //
2148
2149 /// Matches a BinaryOperator with LHS and RHS in either order.
2150 template <typename LHS, typename RHS>
2151 inline AnyBinaryOp_match<LHS, RHS, true> m_c_BinOp(const LHS &L, const RHS &R) {
2152 return AnyBinaryOp_match<LHS, RHS, true>(L, R);
2153 }
2154
2155 /// Matches an ICmp with a predicate over LHS and RHS in either order.
2156 /// Swaps the predicate if operands are commuted.
2157 template <typename LHS, typename RHS>
2158 inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate, true>
2159 m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
2160 return CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate, true>(Pred, L,
2161 R);
2162 }
2163
2164 /// Matches a Add with LHS and RHS in either order.
2165 template <typename LHS, typename RHS>
2166 inline BinaryOp_match<LHS, RHS, Instruction::Add, true> m_c_Add(const LHS &L,
2167 const RHS &R) {
2168 return BinaryOp_match<LHS, RHS, Instruction::Add, true>(L, R);
2169 }
2170
2171 /// Matches a Mul with LHS and RHS in either order.
2172 template <typename LHS, typename RHS>
2173 inline BinaryOp_match<LHS, RHS, Instruction::Mul, true> m_c_Mul(const LHS &L,
2174 const RHS &R) {
2175 return BinaryOp_match<LHS, RHS, Instruction::Mul, true>(L, R);
2176 }
2177
2178 /// Matches an And with LHS and RHS in either order.
2179 template <typename LHS, typename RHS>
2180 inline BinaryOp_match<LHS, RHS, Instruction::And, true> m_c_And(const LHS &L,
2181 const RHS &R) {
2182 return BinaryOp_match<LHS, RHS, Instruction::And, true>(L, R);
2183 }
2184
2185 /// Matches an Or with LHS and RHS in either order.
2186 template <typename LHS, typename RHS>
2187 inline BinaryOp_match<LHS, RHS, Instruction::Or, true> m_c_Or(const LHS &L,
2188 const RHS &R) {
2189 return BinaryOp_match<LHS, RHS, Instruction::Or, true>(L, R);
2190 }
2191
2192 /// Matches an Xor with LHS and RHS in either order.
2193 template <typename LHS, typename RHS>
2194 inline BinaryOp_match<LHS, RHS, Instruction::Xor, true> m_c_Xor(const LHS &L,
2195 const RHS &R) {
2196 return BinaryOp_match<LHS, RHS, Instruction::Xor, true>(L, R);
2197 }
2198
2199 /// Matches a 'Neg' as 'sub 0, V'.
2200 template <typename ValTy>
2201 inline BinaryOp_match<cst_pred_ty<is_zero_int>, ValTy, Instruction::Sub>
2202 m_Neg(const ValTy &V) {
2203 return m_Sub(m_ZeroInt(), V);
2204 }
2205
2206 /// Matches a 'Neg' as 'sub nsw 0, V'.
2207 template <typename ValTy>
2208 inline OverflowingBinaryOp_match<cst_pred_ty<is_zero_int>, ValTy,
2209 Instruction::Sub,
2210 OverflowingBinaryOperator::NoSignedWrap>
2211 m_NSWNeg(const ValTy &V) {
2212 return m_NSWSub(m_ZeroInt(), V);
2213 }
2214
2215 /// Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
2216 template <typename ValTy>
2217 inline BinaryOp_match<ValTy, cst_pred_ty<is_all_ones>, Instruction::Xor, true>
2218 m_Not(const ValTy &V) {
2219 return m_c_Xor(V, m_AllOnes());
2220 }
2221
2222 /// Matches an SMin with LHS and RHS in either order.
2223 template <typename LHS, typename RHS>
2224 inline MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>
2225 m_c_SMin(const LHS &L, const RHS &R) {
2226 return MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>(L, R);
2227 }
2228 /// Matches an SMax with LHS and RHS in either order.
2229 template <typename LHS, typename RHS>
2230 inline MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true>
2231 m_c_SMax(const LHS &L, const RHS &R) {
2232 return MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true>(L, R);
2233 }
2234 /// Matches a UMin with LHS and RHS in either order.
2235 template <typename LHS, typename RHS>
2236 inline MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true>
2237 m_c_UMin(const LHS &L, const RHS &R) {
2238 return MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true>(L, R);
2239 }
2240 /// Matches a UMax with LHS and RHS in either order.
2241 template <typename LHS, typename RHS>
2242 inline MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true>
2243 m_c_UMax(const LHS &L, const RHS &R) {
2244 return MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true>(L, R);
2245 }
2246
2247 template <typename LHS, typename RHS>
2248 inline match_combine_or<
2249 match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true>,
2250 MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>>,
2251 match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true>,
2252 MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true>>>
2253 m_c_MaxOrMin(const LHS &L, const RHS &R) {
2254 return m_CombineOr(m_CombineOr(m_c_SMax(L, R), m_c_SMin(L, R)),
2255 m_CombineOr(m_c_UMax(L, R), m_c_UMin(L, R)));
2256 }
2257
2258 /// Matches FAdd with LHS and RHS in either order.
2259 template <typename LHS, typename RHS>
2260 inline BinaryOp_match<LHS, RHS, Instruction::FAdd, true>
2261 m_c_FAdd(const LHS &L, const RHS &R) {
2262 return BinaryOp_match<LHS, RHS, Instruction::FAdd, true>(L, R);
2263 }
2264
2265 /// Matches FMul with LHS and RHS in either order.
2266 template <typename LHS, typename RHS>
2267 inline BinaryOp_match<LHS, RHS, Instruction::FMul, true>
2268 m_c_FMul(const LHS &L, const RHS &R) {
2269 return BinaryOp_match<LHS, RHS, Instruction::FMul, true>(L, R);
2270 }
2271
2272 template <typename Opnd_t> struct Signum_match {
2273 Opnd_t Val;
2274 Signum_match(const Opnd_t &V) : Val(V) {}
2275
2276 template <typename OpTy> bool match(OpTy *V) {
2277 unsigned TypeSize = V->getType()->getScalarSizeInBits();
2278 if (TypeSize == 0)
2279 return false;
2280
2281 unsigned ShiftWidth = TypeSize - 1;
2282 Value *OpL = nullptr, *OpR = nullptr;
2283
2284 // This is the representation of signum we match:
2285 //
2286 // signum(x) == (x >> 63) | (-x >>u 63)
2287 //
2288 // An i1 value is its own signum, so it's correct to match
2289 //
2290 // signum(x) == (x >> 0) | (-x >>u 0)
2291 //
2292 // for i1 values.
2293
2294 auto LHS = m_AShr(m_Value(OpL), m_SpecificInt(ShiftWidth));
2295 auto RHS = m_LShr(m_Neg(m_Value(OpR)), m_SpecificInt(ShiftWidth));
2296 auto Signum = m_Or(LHS, RHS);
2297
2298 return Signum.match(V) && OpL == OpR && Val.match(OpL);
2299 }
2300 };
2301
2302 /// Matches a signum pattern.
2303 ///
2304 /// signum(x) =
2305 /// x > 0 -> 1
2306 /// x == 0 -> 0
2307 /// x < 0 -> -1
2308 template <typename Val_t> inline Signum_match<Val_t> m_Signum(const Val_t &V) {
2309 return Signum_match<Val_t>(V);
2310 }
2311
2312 template <int Ind, typename Opnd_t> struct ExtractValue_match {
2313 Opnd_t Val;
2314 ExtractValue_match(const Opnd_t &V) : Val(V) {}
2315
2316 template <typename OpTy> bool match(OpTy *V) {
2317 if (auto *I = dyn_cast<ExtractValueInst>(V))
2318 return I->getNumIndices() == 1 && I->getIndices()[0] == Ind &&
2319 Val.match(I->getAggregateOperand());
2320 return false;
2321 }
2322 };
2323
2324 /// Match a single index ExtractValue instruction.
2325 /// For example m_ExtractValue<1>(...)
2326 template <int Ind, typename Val_t>
2327 inline ExtractValue_match<Ind, Val_t> m_ExtractValue(const Val_t &V) {
2328 return ExtractValue_match<Ind, Val_t>(V);
2329 }
2330
2331 /// Matcher for a single index InsertValue instruction.
2332 template <int Ind, typename T0, typename T1> struct InsertValue_match {
2333 T0 Op0;
2334 T1 Op1;
2335
2336 InsertValue_match(const T0 &Op0, const T1 &Op1) : Op0(Op0), Op1(Op1) {}
2337
2338 template <typename OpTy> bool match(OpTy *V) {
2339 if (auto *I = dyn_cast<InsertValueInst>(V)) {
2340 return Op0.match(I->getOperand(0)) && Op1.match(I->getOperand(1)) &&
2341 I->getNumIndices() == 1 && Ind == I->getIndices()[0];
2342 }
2343 return false;
2344 }
2345 };
2346
2347 /// Matches a single index InsertValue instruction.
2348 template <int Ind, typename Val_t, typename Elt_t>
2349 inline InsertValue_match<Ind, Val_t, Elt_t> m_InsertValue(const Val_t &Val,
2350 const Elt_t &Elt) {
2351 return InsertValue_match<Ind, Val_t, Elt_t>(Val, Elt);
2352 }
2353
2354 /// Matches patterns for `vscale`. This can either be a call to `llvm.vscale` or
2355 /// the constant expression
2356 /// `ptrtoint(gep <vscale x 1 x i8>, <vscale x 1 x i8>* null, i32 1>`
2357 /// under the right conditions determined by DataLayout.
2358 struct VScaleVal_match {
2359 private:
2360 template <typename Base, typename Offset>
2361 inline BinaryOp_match<Base, Offset, Instruction::GetElementPtr>
2362 m_OffsetGep(const Base &B, const Offset &O) {
2363 return BinaryOp_match<Base, Offset, Instruction::GetElementPtr>(B, O);
2364 }
2365
2366 public:
2367 const DataLayout &DL;
2368 VScaleVal_match(const DataLayout &DL) : DL(DL) {}
2369
2370 template <typename ITy> bool match(ITy *V) {
2371 if (m_Intrinsic<Intrinsic::vscale>().match(V))
2372 return true;
2373
2374 if (m_PtrToInt(m_OffsetGep(m_Zero(), m_SpecificInt(1))).match(V)) {
2375 Type *PtrTy = cast<Operator>(V)->getOperand(0)->getType();
2376 auto *DerefTy = PtrTy->getPointerElementType();
2377 if (isa<ScalableVectorType>(DerefTy) &&
2378 DL.getTypeAllocSizeInBits(DerefTy).getKnownMinSize() == 8)
2379 return true;
2380 }
2381
2382 return false;
2383 }
2384 };
2385
2386 inline VScaleVal_match m_VScale(const DataLayout &DL) {
2387 return VScaleVal_match(DL);
2388 }
2389
2390 template <typename LHS, typename RHS, unsigned Opcode>
2391 struct LogicalOp_match {
2392 LHS L;
2393 RHS R;
2394
2395 LogicalOp_match(const LHS &L, const RHS &R) : L(L), R(R) {}
2396
2397 template <typename T> bool match(T *V) {
2398 if (auto *I = dyn_cast<Instruction>(V)) {
2399 if (!I->getType()->isIntOrIntVectorTy(1))
2400 return false;
2401
2402 if (I->getOpcode() == Opcode && L.match(I->getOperand(0)) &&
2403 R.match(I->getOperand(1)))
2404 return true;
2405
2406 if (auto *SI = dyn_cast<SelectInst>(I)) {
2407 if (Opcode == Instruction::And) {
2408 if (const auto *C = dyn_cast<Constant>(SI->getFalseValue()))
2409 if (C->isNullValue() && L.match(SI->getCondition()) &&
2410 R.match(SI->getTrueValue()))
2411 return true;
2412 } else {
2413 assert(Opcode == Instruction::Or);
2414 if (const auto *C = dyn_cast<Constant>(SI->getTrueValue()))
2415 if (C->isOneValue() && L.match(SI->getCondition()) &&
2416 R.match(SI->getFalseValue()))
2417 return true;
2418 }
2419 }
2420 }
2421
2422 return false;
2423 }
2424 };
2425
2426 /// Matches L && R either in the form of L & R or L ? R : false.
2427 /// Note that the latter form is poison-blocking.
2428 template <typename LHS, typename RHS>
2429 inline LogicalOp_match<LHS, RHS, Instruction::And>
2430 m_LogicalAnd(const LHS &L, const RHS &R) {
2431 return LogicalOp_match<LHS, RHS, Instruction::And>(L, R);
2432 }
2433
2434 /// Matches L || R either in the form of L | R or L ? true : R.
2435 /// Note that the latter form is poison-blocking.
2436 template <typename LHS, typename RHS>
2437 inline LogicalOp_match<LHS, RHS, Instruction::Or>
2438 m_LogicalOr(const LHS &L, const RHS &R) {
2439 return LogicalOp_match<LHS, RHS, Instruction::Or>(L, R);
2440 }
2441
2442 } // end namespace PatternMatch
2443 } // end namespace llvm
2444
2445 #endif // LLVM_IR_PATTERNMATCH_H
2446