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 ConstantInt and ignore it.
m_ConstantInt()92 inline class_match<ConstantInt> m_ConstantInt() {
93 return class_match<ConstantInt>();
94 }
95
96 /// Match an arbitrary undef constant.
m_Undef()97 inline class_match<UndefValue> m_Undef() { return class_match<UndefValue>(); }
98
99 /// Match an arbitrary Constant and ignore it.
m_Constant()100 inline class_match<Constant> m_Constant() { return class_match<Constant>(); }
101
102 /// Match an arbitrary basic block value and ignore it.
m_BasicBlock()103 inline class_match<BasicBlock> m_BasicBlock() {
104 return class_match<BasicBlock>();
105 }
106
107 /// Inverting matcher
108 template <typename Ty> struct match_unless {
109 Ty M;
110
match_unlessmatch_unless111 match_unless(const Ty &Matcher) : M(Matcher) {}
112
matchmatch_unless113 template <typename ITy> bool match(ITy *V) { return !M.match(V); }
114 };
115
116 /// Match if the inner matcher does *NOT* match.
m_Unless(const Ty & M)117 template <typename Ty> inline match_unless<Ty> m_Unless(const Ty &M) {
118 return match_unless<Ty>(M);
119 }
120
121 /// Matching combinators
122 template <typename LTy, typename RTy> struct match_combine_or {
123 LTy L;
124 RTy R;
125
match_combine_ormatch_combine_or126 match_combine_or(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
127
matchmatch_combine_or128 template <typename ITy> bool match(ITy *V) {
129 if (L.match(V))
130 return true;
131 if (R.match(V))
132 return true;
133 return false;
134 }
135 };
136
137 template <typename LTy, typename RTy> struct match_combine_and {
138 LTy L;
139 RTy R;
140
match_combine_andmatch_combine_and141 match_combine_and(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
142
matchmatch_combine_and143 template <typename ITy> bool match(ITy *V) {
144 if (L.match(V))
145 if (R.match(V))
146 return true;
147 return false;
148 }
149 };
150
151 /// Combine two pattern matchers matching L || R
152 template <typename LTy, typename RTy>
m_CombineOr(const LTy & L,const RTy & R)153 inline match_combine_or<LTy, RTy> m_CombineOr(const LTy &L, const RTy &R) {
154 return match_combine_or<LTy, RTy>(L, R);
155 }
156
157 /// Combine two pattern matchers matching L && R
158 template <typename LTy, typename RTy>
m_CombineAnd(const LTy & L,const RTy & R)159 inline match_combine_and<LTy, RTy> m_CombineAnd(const LTy &L, const RTy &R) {
160 return match_combine_and<LTy, RTy>(L, R);
161 }
162
163 struct apint_match {
164 const APInt *&Res;
165 bool AllowUndef;
166
apint_matchapint_match167 apint_match(const APInt *&Res, bool AllowUndef)
168 : Res(Res), AllowUndef(AllowUndef) {}
169
matchapint_match170 template <typename ITy> bool match(ITy *V) {
171 if (auto *CI = dyn_cast<ConstantInt>(V)) {
172 Res = &CI->getValue();
173 return true;
174 }
175 if (V->getType()->isVectorTy())
176 if (const auto *C = dyn_cast<Constant>(V))
177 if (auto *CI = dyn_cast_or_null<ConstantInt>(
178 C->getSplatValue(AllowUndef))) {
179 Res = &CI->getValue();
180 return true;
181 }
182 return false;
183 }
184 };
185 // Either constexpr if or renaming ConstantFP::getValueAPF to
186 // ConstantFP::getValue is needed to do it via single template
187 // function for both apint/apfloat.
188 struct apfloat_match {
189 const APFloat *&Res;
190 bool AllowUndef;
191
apfloat_matchapfloat_match192 apfloat_match(const APFloat *&Res, bool AllowUndef)
193 : Res(Res), AllowUndef(AllowUndef) {}
194
matchapfloat_match195 template <typename ITy> bool match(ITy *V) {
196 if (auto *CI = dyn_cast<ConstantFP>(V)) {
197 Res = &CI->getValueAPF();
198 return true;
199 }
200 if (V->getType()->isVectorTy())
201 if (const auto *C = dyn_cast<Constant>(V))
202 if (auto *CI = dyn_cast_or_null<ConstantFP>(
203 C->getSplatValue(AllowUndef))) {
204 Res = &CI->getValueAPF();
205 return true;
206 }
207 return false;
208 }
209 };
210
211 /// Match a ConstantInt or splatted ConstantVector, binding the
212 /// specified pointer to the contained APInt.
m_APInt(const APInt * & Res)213 inline apint_match m_APInt(const APInt *&Res) {
214 // Forbid undefs by default to maintain previous behavior.
215 return apint_match(Res, /* AllowUndef */ false);
216 }
217
218 /// Match APInt while allowing undefs in splat vector constants.
m_APIntAllowUndef(const APInt * & Res)219 inline apint_match m_APIntAllowUndef(const APInt *&Res) {
220 return apint_match(Res, /* AllowUndef */ true);
221 }
222
223 /// Match APInt while forbidding undefs in splat vector constants.
m_APIntForbidUndef(const APInt * & Res)224 inline apint_match m_APIntForbidUndef(const APInt *&Res) {
225 return apint_match(Res, /* AllowUndef */ false);
226 }
227
228 /// Match a ConstantFP or splatted ConstantVector, binding the
229 /// specified pointer to the contained APFloat.
m_APFloat(const APFloat * & Res)230 inline apfloat_match m_APFloat(const APFloat *&Res) {
231 // Forbid undefs by default to maintain previous behavior.
232 return apfloat_match(Res, /* AllowUndef */ false);
233 }
234
235 /// Match APFloat while allowing undefs in splat vector constants.
m_APFloatAllowUndef(const APFloat * & Res)236 inline apfloat_match m_APFloatAllowUndef(const APFloat *&Res) {
237 return apfloat_match(Res, /* AllowUndef */ true);
238 }
239
240 /// Match APFloat while forbidding undefs in splat vector constants.
m_APFloatForbidUndef(const APFloat * & Res)241 inline apfloat_match m_APFloatForbidUndef(const APFloat *&Res) {
242 return apfloat_match(Res, /* AllowUndef */ false);
243 }
244
245 template <int64_t Val> struct constantint_match {
matchconstantint_match246 template <typename ITy> bool match(ITy *V) {
247 if (const auto *CI = dyn_cast<ConstantInt>(V)) {
248 const APInt &CIV = CI->getValue();
249 if (Val >= 0)
250 return CIV == static_cast<uint64_t>(Val);
251 // If Val is negative, and CI is shorter than it, truncate to the right
252 // number of bits. If it is larger, then we have to sign extend. Just
253 // compare their negated values.
254 return -CIV == -Val;
255 }
256 return false;
257 }
258 };
259
260 /// Match a ConstantInt with a specific value.
m_ConstantInt()261 template <int64_t Val> inline constantint_match<Val> m_ConstantInt() {
262 return constantint_match<Val>();
263 }
264
265 /// This helper class is used to match constant scalars, vector splats,
266 /// and fixed width vectors that satisfy a specified predicate.
267 /// For fixed width vector constants, undefined elements are ignored.
268 template <typename Predicate, typename ConstantVal>
269 struct cstval_pred_ty : public Predicate {
matchcstval_pred_ty270 template <typename ITy> bool match(ITy *V) {
271 if (const auto *CV = dyn_cast<ConstantVal>(V))
272 return this->isValue(CV->getValue());
273 if (const auto *VTy = dyn_cast<VectorType>(V->getType())) {
274 if (const auto *C = dyn_cast<Constant>(V)) {
275 if (const auto *CV = dyn_cast_or_null<ConstantVal>(C->getSplatValue()))
276 return this->isValue(CV->getValue());
277
278 // Number of elements of a scalable vector unknown at compile time
279 auto *FVTy = dyn_cast<FixedVectorType>(VTy);
280 if (!FVTy)
281 return false;
282
283 // Non-splat vector constant: check each element for a match.
284 unsigned NumElts = FVTy->getNumElements();
285 assert(NumElts != 0 && "Constant vector with no elements?");
286 bool HasNonUndefElements = false;
287 for (unsigned i = 0; i != NumElts; ++i) {
288 Constant *Elt = C->getAggregateElement(i);
289 if (!Elt)
290 return false;
291 if (isa<UndefValue>(Elt))
292 continue;
293 auto *CV = dyn_cast<ConstantVal>(Elt);
294 if (!CV || !this->isValue(CV->getValue()))
295 return false;
296 HasNonUndefElements = true;
297 }
298 return HasNonUndefElements;
299 }
300 }
301 return false;
302 }
303 };
304
305 /// specialization of cstval_pred_ty for ConstantInt
306 template <typename Predicate>
307 using cst_pred_ty = cstval_pred_ty<Predicate, ConstantInt>;
308
309 /// specialization of cstval_pred_ty for ConstantFP
310 template <typename Predicate>
311 using cstfp_pred_ty = cstval_pred_ty<Predicate, ConstantFP>;
312
313 /// This helper class is used to match scalar and vector constants that
314 /// satisfy a specified predicate, and bind them to an APInt.
315 template <typename Predicate> struct api_pred_ty : public Predicate {
316 const APInt *&Res;
317
api_pred_tyapi_pred_ty318 api_pred_ty(const APInt *&R) : Res(R) {}
319
matchapi_pred_ty320 template <typename ITy> bool match(ITy *V) {
321 if (const auto *CI = dyn_cast<ConstantInt>(V))
322 if (this->isValue(CI->getValue())) {
323 Res = &CI->getValue();
324 return true;
325 }
326 if (V->getType()->isVectorTy())
327 if (const auto *C = dyn_cast<Constant>(V))
328 if (auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue()))
329 if (this->isValue(CI->getValue())) {
330 Res = &CI->getValue();
331 return true;
332 }
333
334 return false;
335 }
336 };
337
338 ///////////////////////////////////////////////////////////////////////////////
339 //
340 // Encapsulate constant value queries for use in templated predicate matchers.
341 // This allows checking if constants match using compound predicates and works
342 // with vector constants, possibly with relaxed constraints. For example, ignore
343 // undef values.
344 //
345 ///////////////////////////////////////////////////////////////////////////////
346
347 struct is_any_apint {
isValueis_any_apint348 bool isValue(const APInt &C) { return true; }
349 };
350 /// Match an integer or vector with any integral constant.
351 /// For vectors, this includes constants with undefined elements.
m_AnyIntegralConstant()352 inline cst_pred_ty<is_any_apint> m_AnyIntegralConstant() {
353 return cst_pred_ty<is_any_apint>();
354 }
355
356 struct is_all_ones {
isValueis_all_ones357 bool isValue(const APInt &C) { return C.isAllOnesValue(); }
358 };
359 /// Match an integer or vector with all bits set.
360 /// For vectors, this includes constants with undefined elements.
m_AllOnes()361 inline cst_pred_ty<is_all_ones> m_AllOnes() {
362 return cst_pred_ty<is_all_ones>();
363 }
364
365 struct is_maxsignedvalue {
isValueis_maxsignedvalue366 bool isValue(const APInt &C) { return C.isMaxSignedValue(); }
367 };
368 /// Match an integer or vector with values having all bits except for the high
369 /// bit set (0x7f...).
370 /// For vectors, this includes constants with undefined elements.
m_MaxSignedValue()371 inline cst_pred_ty<is_maxsignedvalue> m_MaxSignedValue() {
372 return cst_pred_ty<is_maxsignedvalue>();
373 }
m_MaxSignedValue(const APInt * & V)374 inline api_pred_ty<is_maxsignedvalue> m_MaxSignedValue(const APInt *&V) {
375 return V;
376 }
377
378 struct is_negative {
isValueis_negative379 bool isValue(const APInt &C) { return C.isNegative(); }
380 };
381 /// Match an integer or vector of negative values.
382 /// For vectors, this includes constants with undefined elements.
m_Negative()383 inline cst_pred_ty<is_negative> m_Negative() {
384 return cst_pred_ty<is_negative>();
385 }
m_Negative(const APInt * & V)386 inline api_pred_ty<is_negative> m_Negative(const APInt *&V) {
387 return V;
388 }
389
390 struct is_nonnegative {
isValueis_nonnegative391 bool isValue(const APInt &C) { return C.isNonNegative(); }
392 };
393 /// Match an integer or vector of non-negative values.
394 /// For vectors, this includes constants with undefined elements.
m_NonNegative()395 inline cst_pred_ty<is_nonnegative> m_NonNegative() {
396 return cst_pred_ty<is_nonnegative>();
397 }
m_NonNegative(const APInt * & V)398 inline api_pred_ty<is_nonnegative> m_NonNegative(const APInt *&V) {
399 return V;
400 }
401
402 struct is_strictlypositive {
isValueis_strictlypositive403 bool isValue(const APInt &C) { return C.isStrictlyPositive(); }
404 };
405 /// Match an integer or vector of strictly positive values.
406 /// For vectors, this includes constants with undefined elements.
m_StrictlyPositive()407 inline cst_pred_ty<is_strictlypositive> m_StrictlyPositive() {
408 return cst_pred_ty<is_strictlypositive>();
409 }
m_StrictlyPositive(const APInt * & V)410 inline api_pred_ty<is_strictlypositive> m_StrictlyPositive(const APInt *&V) {
411 return V;
412 }
413
414 struct is_nonpositive {
isValueis_nonpositive415 bool isValue(const APInt &C) { return C.isNonPositive(); }
416 };
417 /// Match an integer or vector of non-positive values.
418 /// For vectors, this includes constants with undefined elements.
m_NonPositive()419 inline cst_pred_ty<is_nonpositive> m_NonPositive() {
420 return cst_pred_ty<is_nonpositive>();
421 }
m_NonPositive(const APInt * & V)422 inline api_pred_ty<is_nonpositive> m_NonPositive(const APInt *&V) { return V; }
423
424 struct is_one {
isValueis_one425 bool isValue(const APInt &C) { return C.isOneValue(); }
426 };
427 /// Match an integer 1 or a vector with all elements equal to 1.
428 /// For vectors, this includes constants with undefined elements.
m_One()429 inline cst_pred_ty<is_one> m_One() {
430 return cst_pred_ty<is_one>();
431 }
432
433 struct is_zero_int {
isValueis_zero_int434 bool isValue(const APInt &C) { return C.isNullValue(); }
435 };
436 /// Match an integer 0 or a vector with all elements equal to 0.
437 /// For vectors, this includes constants with undefined elements.
m_ZeroInt()438 inline cst_pred_ty<is_zero_int> m_ZeroInt() {
439 return cst_pred_ty<is_zero_int>();
440 }
441
442 struct is_zero {
matchis_zero443 template <typename ITy> bool match(ITy *V) {
444 auto *C = dyn_cast<Constant>(V);
445 // FIXME: this should be able to do something for scalable vectors
446 return C && (C->isNullValue() || cst_pred_ty<is_zero_int>().match(C));
447 }
448 };
449 /// Match any null constant or a vector with all elements equal to 0.
450 /// For vectors, this includes constants with undefined elements.
m_Zero()451 inline is_zero m_Zero() {
452 return is_zero();
453 }
454
455 struct is_power2 {
isValueis_power2456 bool isValue(const APInt &C) { return C.isPowerOf2(); }
457 };
458 /// Match an integer or vector power-of-2.
459 /// For vectors, this includes constants with undefined elements.
m_Power2()460 inline cst_pred_ty<is_power2> m_Power2() {
461 return cst_pred_ty<is_power2>();
462 }
m_Power2(const APInt * & V)463 inline api_pred_ty<is_power2> m_Power2(const APInt *&V) {
464 return V;
465 }
466
467 struct is_negated_power2 {
isValueis_negated_power2468 bool isValue(const APInt &C) { return (-C).isPowerOf2(); }
469 };
470 /// Match a integer or vector negated power-of-2.
471 /// For vectors, this includes constants with undefined elements.
m_NegatedPower2()472 inline cst_pred_ty<is_negated_power2> m_NegatedPower2() {
473 return cst_pred_ty<is_negated_power2>();
474 }
m_NegatedPower2(const APInt * & V)475 inline api_pred_ty<is_negated_power2> m_NegatedPower2(const APInt *&V) {
476 return V;
477 }
478
479 struct is_power2_or_zero {
isValueis_power2_or_zero480 bool isValue(const APInt &C) { return !C || C.isPowerOf2(); }
481 };
482 /// Match an integer or vector of 0 or power-of-2 values.
483 /// For vectors, this includes constants with undefined elements.
m_Power2OrZero()484 inline cst_pred_ty<is_power2_or_zero> m_Power2OrZero() {
485 return cst_pred_ty<is_power2_or_zero>();
486 }
m_Power2OrZero(const APInt * & V)487 inline api_pred_ty<is_power2_or_zero> m_Power2OrZero(const APInt *&V) {
488 return V;
489 }
490
491 struct is_sign_mask {
isValueis_sign_mask492 bool isValue(const APInt &C) { return C.isSignMask(); }
493 };
494 /// Match an integer or vector with only the sign bit(s) set.
495 /// For vectors, this includes constants with undefined elements.
m_SignMask()496 inline cst_pred_ty<is_sign_mask> m_SignMask() {
497 return cst_pred_ty<is_sign_mask>();
498 }
499
500 struct is_lowbit_mask {
isValueis_lowbit_mask501 bool isValue(const APInt &C) { return C.isMask(); }
502 };
503 /// Match an integer or vector with only the low bit(s) set.
504 /// For vectors, this includes constants with undefined elements.
m_LowBitMask()505 inline cst_pred_ty<is_lowbit_mask> m_LowBitMask() {
506 return cst_pred_ty<is_lowbit_mask>();
507 }
508
509 struct icmp_pred_with_threshold {
510 ICmpInst::Predicate Pred;
511 const APInt *Thr;
isValueicmp_pred_with_threshold512 bool isValue(const APInt &C) {
513 switch (Pred) {
514 case ICmpInst::Predicate::ICMP_EQ:
515 return C.eq(*Thr);
516 case ICmpInst::Predicate::ICMP_NE:
517 return C.ne(*Thr);
518 case ICmpInst::Predicate::ICMP_UGT:
519 return C.ugt(*Thr);
520 case ICmpInst::Predicate::ICMP_UGE:
521 return C.uge(*Thr);
522 case ICmpInst::Predicate::ICMP_ULT:
523 return C.ult(*Thr);
524 case ICmpInst::Predicate::ICMP_ULE:
525 return C.ule(*Thr);
526 case ICmpInst::Predicate::ICMP_SGT:
527 return C.sgt(*Thr);
528 case ICmpInst::Predicate::ICMP_SGE:
529 return C.sge(*Thr);
530 case ICmpInst::Predicate::ICMP_SLT:
531 return C.slt(*Thr);
532 case ICmpInst::Predicate::ICMP_SLE:
533 return C.sle(*Thr);
534 default:
535 llvm_unreachable("Unhandled ICmp predicate");
536 }
537 }
538 };
539 /// Match an integer or vector with every element comparing 'pred' (eg/ne/...)
540 /// to Threshold. For vectors, this includes constants with undefined elements.
541 inline cst_pred_ty<icmp_pred_with_threshold>
m_SpecificInt_ICMP(ICmpInst::Predicate Predicate,const APInt & Threshold)542 m_SpecificInt_ICMP(ICmpInst::Predicate Predicate, const APInt &Threshold) {
543 cst_pred_ty<icmp_pred_with_threshold> P;
544 P.Pred = Predicate;
545 P.Thr = &Threshold;
546 return P;
547 }
548
549 struct is_nan {
isValueis_nan550 bool isValue(const APFloat &C) { return C.isNaN(); }
551 };
552 /// Match an arbitrary NaN constant. This includes quiet and signalling nans.
553 /// For vectors, this includes constants with undefined elements.
m_NaN()554 inline cstfp_pred_ty<is_nan> m_NaN() {
555 return cstfp_pred_ty<is_nan>();
556 }
557
558 struct is_inf {
isValueis_inf559 bool isValue(const APFloat &C) { return C.isInfinity(); }
560 };
561 /// Match a positive or negative infinity FP constant.
562 /// For vectors, this includes constants with undefined elements.
m_Inf()563 inline cstfp_pred_ty<is_inf> m_Inf() {
564 return cstfp_pred_ty<is_inf>();
565 }
566
567 struct is_any_zero_fp {
isValueis_any_zero_fp568 bool isValue(const APFloat &C) { return C.isZero(); }
569 };
570 /// Match a floating-point negative zero or positive zero.
571 /// For vectors, this includes constants with undefined elements.
m_AnyZeroFP()572 inline cstfp_pred_ty<is_any_zero_fp> m_AnyZeroFP() {
573 return cstfp_pred_ty<is_any_zero_fp>();
574 }
575
576 struct is_pos_zero_fp {
isValueis_pos_zero_fp577 bool isValue(const APFloat &C) { return C.isPosZero(); }
578 };
579 /// Match a floating-point positive zero.
580 /// For vectors, this includes constants with undefined elements.
m_PosZeroFP()581 inline cstfp_pred_ty<is_pos_zero_fp> m_PosZeroFP() {
582 return cstfp_pred_ty<is_pos_zero_fp>();
583 }
584
585 struct is_neg_zero_fp {
isValueis_neg_zero_fp586 bool isValue(const APFloat &C) { return C.isNegZero(); }
587 };
588 /// Match a floating-point negative zero.
589 /// For vectors, this includes constants with undefined elements.
m_NegZeroFP()590 inline cstfp_pred_ty<is_neg_zero_fp> m_NegZeroFP() {
591 return cstfp_pred_ty<is_neg_zero_fp>();
592 }
593
594 ///////////////////////////////////////////////////////////////////////////////
595
596 template <typename Class> struct bind_ty {
597 Class *&VR;
598
bind_tybind_ty599 bind_ty(Class *&V) : VR(V) {}
600
matchbind_ty601 template <typename ITy> bool match(ITy *V) {
602 if (auto *CV = dyn_cast<Class>(V)) {
603 VR = CV;
604 return true;
605 }
606 return false;
607 }
608 };
609
610 /// Match a value, capturing it if we match.
m_Value(Value * & V)611 inline bind_ty<Value> m_Value(Value *&V) { return V; }
m_Value(const Value * & V)612 inline bind_ty<const Value> m_Value(const Value *&V) { return V; }
613
614 /// Match an instruction, capturing it if we match.
m_Instruction(Instruction * & I)615 inline bind_ty<Instruction> m_Instruction(Instruction *&I) { return I; }
616 /// Match a unary operator, capturing it if we match.
m_UnOp(UnaryOperator * & I)617 inline bind_ty<UnaryOperator> m_UnOp(UnaryOperator *&I) { return I; }
618 /// Match a binary operator, capturing it if we match.
m_BinOp(BinaryOperator * & I)619 inline bind_ty<BinaryOperator> m_BinOp(BinaryOperator *&I) { return I; }
620 /// Match a with overflow intrinsic, capturing it if we match.
m_WithOverflowInst(WithOverflowInst * & I)621 inline bind_ty<WithOverflowInst> m_WithOverflowInst(WithOverflowInst *&I) { return I; }
622
623 /// Match a ConstantInt, capturing the value if we match.
m_ConstantInt(ConstantInt * & CI)624 inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
625
626 /// Match a Constant, capturing the value if we match.
m_Constant(Constant * & C)627 inline bind_ty<Constant> m_Constant(Constant *&C) { return C; }
628
629 /// Match a ConstantFP, capturing the value if we match.
m_ConstantFP(ConstantFP * & C)630 inline bind_ty<ConstantFP> m_ConstantFP(ConstantFP *&C) { return C; }
631
632 /// Match a basic block value, capturing it if we match.
m_BasicBlock(BasicBlock * & V)633 inline bind_ty<BasicBlock> m_BasicBlock(BasicBlock *&V) { return V; }
m_BasicBlock(const BasicBlock * & V)634 inline bind_ty<const BasicBlock> m_BasicBlock(const BasicBlock *&V) {
635 return V;
636 }
637
638 /// Match a specified Value*.
639 struct specificval_ty {
640 const Value *Val;
641
specificval_tyspecificval_ty642 specificval_ty(const Value *V) : Val(V) {}
643
matchspecificval_ty644 template <typename ITy> bool match(ITy *V) { return V == Val; }
645 };
646
647 /// Match if we have a specific specified value.
m_Specific(const Value * V)648 inline specificval_ty m_Specific(const Value *V) { return V; }
649
650 /// Stores a reference to the Value *, not the Value * itself,
651 /// thus can be used in commutative matchers.
652 template <typename Class> struct deferredval_ty {
653 Class *const &Val;
654
deferredval_tydeferredval_ty655 deferredval_ty(Class *const &V) : Val(V) {}
656
matchdeferredval_ty657 template <typename ITy> bool match(ITy *const V) { return V == Val; }
658 };
659
660 /// A commutative-friendly version of m_Specific().
m_Deferred(Value * const & V)661 inline deferredval_ty<Value> m_Deferred(Value *const &V) { return V; }
m_Deferred(const Value * const & V)662 inline deferredval_ty<const Value> m_Deferred(const Value *const &V) {
663 return V;
664 }
665
666 /// Match a specified floating point value or vector of all elements of
667 /// that value.
668 struct specific_fpval {
669 double Val;
670
specific_fpvalspecific_fpval671 specific_fpval(double V) : Val(V) {}
672
matchspecific_fpval673 template <typename ITy> bool match(ITy *V) {
674 if (const auto *CFP = dyn_cast<ConstantFP>(V))
675 return CFP->isExactlyValue(Val);
676 if (V->getType()->isVectorTy())
677 if (const auto *C = dyn_cast<Constant>(V))
678 if (auto *CFP = dyn_cast_or_null<ConstantFP>(C->getSplatValue()))
679 return CFP->isExactlyValue(Val);
680 return false;
681 }
682 };
683
684 /// Match a specific floating point value or vector with all elements
685 /// equal to the value.
m_SpecificFP(double V)686 inline specific_fpval m_SpecificFP(double V) { return specific_fpval(V); }
687
688 /// Match a float 1.0 or vector with all elements equal to 1.0.
m_FPOne()689 inline specific_fpval m_FPOne() { return m_SpecificFP(1.0); }
690
691 struct bind_const_intval_ty {
692 uint64_t &VR;
693
bind_const_intval_tybind_const_intval_ty694 bind_const_intval_ty(uint64_t &V) : VR(V) {}
695
matchbind_const_intval_ty696 template <typename ITy> bool match(ITy *V) {
697 if (const auto *CV = dyn_cast<ConstantInt>(V))
698 if (CV->getValue().ule(UINT64_MAX)) {
699 VR = CV->getZExtValue();
700 return true;
701 }
702 return false;
703 }
704 };
705
706 /// Match a specified integer value or vector of all elements of that
707 /// value.
708 struct specific_intval {
709 APInt Val;
710
specific_intvalspecific_intval711 specific_intval(APInt V) : Val(std::move(V)) {}
712
matchspecific_intval713 template <typename ITy> bool match(ITy *V) {
714 const auto *CI = dyn_cast<ConstantInt>(V);
715 if (!CI && V->getType()->isVectorTy())
716 if (const auto *C = dyn_cast<Constant>(V))
717 CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue());
718
719 return CI && APInt::isSameValue(CI->getValue(), Val);
720 }
721 };
722
723 /// Match a specific integer value or vector with all elements equal to
724 /// the value.
m_SpecificInt(APInt V)725 inline specific_intval m_SpecificInt(APInt V) {
726 return specific_intval(std::move(V));
727 }
728
m_SpecificInt(uint64_t V)729 inline specific_intval m_SpecificInt(uint64_t V) {
730 return m_SpecificInt(APInt(64, V));
731 }
732
733 /// Match a ConstantInt and bind to its value. This does not match
734 /// ConstantInts wider than 64-bits.
m_ConstantInt(uint64_t & V)735 inline bind_const_intval_ty m_ConstantInt(uint64_t &V) { return V; }
736
737 /// Match a specified basic block value.
738 struct specific_bbval {
739 BasicBlock *Val;
740
specific_bbvalspecific_bbval741 specific_bbval(BasicBlock *Val) : Val(Val) {}
742
matchspecific_bbval743 template <typename ITy> bool match(ITy *V) {
744 const auto *BB = dyn_cast<BasicBlock>(V);
745 return BB && BB == Val;
746 }
747 };
748
749 /// Match a specific basic block value.
m_SpecificBB(BasicBlock * BB)750 inline specific_bbval m_SpecificBB(BasicBlock *BB) {
751 return specific_bbval(BB);
752 }
753
754 /// A commutative-friendly version of m_Specific().
m_Deferred(BasicBlock * const & BB)755 inline deferredval_ty<BasicBlock> m_Deferred(BasicBlock *const &BB) {
756 return BB;
757 }
758 inline deferredval_ty<const BasicBlock>
m_Deferred(const BasicBlock * const & BB)759 m_Deferred(const BasicBlock *const &BB) {
760 return BB;
761 }
762
763 //===----------------------------------------------------------------------===//
764 // Matcher for any binary operator.
765 //
766 template <typename LHS_t, typename RHS_t, bool Commutable = false>
767 struct AnyBinaryOp_match {
768 LHS_t L;
769 RHS_t R;
770
771 // The evaluation order is always stable, regardless of Commutability.
772 // The LHS is always matched first.
AnyBinaryOp_matchAnyBinaryOp_match773 AnyBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
774
matchAnyBinaryOp_match775 template <typename OpTy> bool match(OpTy *V) {
776 if (auto *I = dyn_cast<BinaryOperator>(V))
777 return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
778 (Commutable && L.match(I->getOperand(1)) &&
779 R.match(I->getOperand(0)));
780 return false;
781 }
782 };
783
784 template <typename LHS, typename RHS>
m_BinOp(const LHS & L,const RHS & R)785 inline AnyBinaryOp_match<LHS, RHS> m_BinOp(const LHS &L, const RHS &R) {
786 return AnyBinaryOp_match<LHS, RHS>(L, R);
787 }
788
789 //===----------------------------------------------------------------------===//
790 // Matcher for any unary operator.
791 // TODO fuse unary, binary matcher into n-ary matcher
792 //
793 template <typename OP_t> struct AnyUnaryOp_match {
794 OP_t X;
795
AnyUnaryOp_matchAnyUnaryOp_match796 AnyUnaryOp_match(const OP_t &X) : X(X) {}
797
matchAnyUnaryOp_match798 template <typename OpTy> bool match(OpTy *V) {
799 if (auto *I = dyn_cast<UnaryOperator>(V))
800 return X.match(I->getOperand(0));
801 return false;
802 }
803 };
804
m_UnOp(const OP_t & X)805 template <typename OP_t> inline AnyUnaryOp_match<OP_t> m_UnOp(const OP_t &X) {
806 return AnyUnaryOp_match<OP_t>(X);
807 }
808
809 //===----------------------------------------------------------------------===//
810 // Matchers for specific binary operators.
811 //
812
813 template <typename LHS_t, typename RHS_t, unsigned Opcode,
814 bool Commutable = false>
815 struct BinaryOp_match {
816 LHS_t L;
817 RHS_t R;
818
819 // The evaluation order is always stable, regardless of Commutability.
820 // The LHS is always matched first.
BinaryOp_matchBinaryOp_match821 BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
822
matchBinaryOp_match823 template <typename OpTy> bool match(OpTy *V) {
824 if (V->getValueID() == Value::InstructionVal + Opcode) {
825 auto *I = cast<BinaryOperator>(V);
826 return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
827 (Commutable && L.match(I->getOperand(1)) &&
828 R.match(I->getOperand(0)));
829 }
830 if (auto *CE = dyn_cast<ConstantExpr>(V))
831 return CE->getOpcode() == Opcode &&
832 ((L.match(CE->getOperand(0)) && R.match(CE->getOperand(1))) ||
833 (Commutable && L.match(CE->getOperand(1)) &&
834 R.match(CE->getOperand(0))));
835 return false;
836 }
837 };
838
839 template <typename LHS, typename RHS>
m_Add(const LHS & L,const RHS & R)840 inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L,
841 const RHS &R) {
842 return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);
843 }
844
845 template <typename LHS, typename RHS>
m_FAdd(const LHS & L,const RHS & R)846 inline BinaryOp_match<LHS, RHS, Instruction::FAdd> m_FAdd(const LHS &L,
847 const RHS &R) {
848 return BinaryOp_match<LHS, RHS, Instruction::FAdd>(L, R);
849 }
850
851 template <typename LHS, typename RHS>
m_Sub(const LHS & L,const RHS & R)852 inline BinaryOp_match<LHS, RHS, Instruction::Sub> m_Sub(const LHS &L,
853 const RHS &R) {
854 return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R);
855 }
856
857 template <typename LHS, typename RHS>
m_FSub(const LHS & L,const RHS & R)858 inline BinaryOp_match<LHS, RHS, Instruction::FSub> m_FSub(const LHS &L,
859 const RHS &R) {
860 return BinaryOp_match<LHS, RHS, Instruction::FSub>(L, R);
861 }
862
863 template <typename Op_t> struct FNeg_match {
864 Op_t X;
865
FNeg_matchFNeg_match866 FNeg_match(const Op_t &Op) : X(Op) {}
matchFNeg_match867 template <typename OpTy> bool match(OpTy *V) {
868 auto *FPMO = dyn_cast<FPMathOperator>(V);
869 if (!FPMO) return false;
870
871 if (FPMO->getOpcode() == Instruction::FNeg)
872 return X.match(FPMO->getOperand(0));
873
874 if (FPMO->getOpcode() == Instruction::FSub) {
875 if (FPMO->hasNoSignedZeros()) {
876 // With 'nsz', any zero goes.
877 if (!cstfp_pred_ty<is_any_zero_fp>().match(FPMO->getOperand(0)))
878 return false;
879 } else {
880 // Without 'nsz', we need fsub -0.0, X exactly.
881 if (!cstfp_pred_ty<is_neg_zero_fp>().match(FPMO->getOperand(0)))
882 return false;
883 }
884
885 return X.match(FPMO->getOperand(1));
886 }
887
888 return false;
889 }
890 };
891
892 /// Match 'fneg X' as 'fsub -0.0, X'.
893 template <typename OpTy>
894 inline FNeg_match<OpTy>
m_FNeg(const OpTy & X)895 m_FNeg(const OpTy &X) {
896 return FNeg_match<OpTy>(X);
897 }
898
899 /// Match 'fneg X' as 'fsub +-0.0, X'.
900 template <typename RHS>
901 inline BinaryOp_match<cstfp_pred_ty<is_any_zero_fp>, RHS, Instruction::FSub>
m_FNegNSZ(const RHS & X)902 m_FNegNSZ(const RHS &X) {
903 return m_FSub(m_AnyZeroFP(), X);
904 }
905
906 template <typename LHS, typename RHS>
m_Mul(const LHS & L,const RHS & R)907 inline BinaryOp_match<LHS, RHS, Instruction::Mul> m_Mul(const LHS &L,
908 const RHS &R) {
909 return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R);
910 }
911
912 template <typename LHS, typename RHS>
m_FMul(const LHS & L,const RHS & R)913 inline BinaryOp_match<LHS, RHS, Instruction::FMul> m_FMul(const LHS &L,
914 const RHS &R) {
915 return BinaryOp_match<LHS, RHS, Instruction::FMul>(L, R);
916 }
917
918 template <typename LHS, typename RHS>
m_UDiv(const LHS & L,const RHS & R)919 inline BinaryOp_match<LHS, RHS, Instruction::UDiv> m_UDiv(const LHS &L,
920 const RHS &R) {
921 return BinaryOp_match<LHS, RHS, Instruction::UDiv>(L, R);
922 }
923
924 template <typename LHS, typename RHS>
m_SDiv(const LHS & L,const RHS & R)925 inline BinaryOp_match<LHS, RHS, Instruction::SDiv> m_SDiv(const LHS &L,
926 const RHS &R) {
927 return BinaryOp_match<LHS, RHS, Instruction::SDiv>(L, R);
928 }
929
930 template <typename LHS, typename RHS>
m_FDiv(const LHS & L,const RHS & R)931 inline BinaryOp_match<LHS, RHS, Instruction::FDiv> m_FDiv(const LHS &L,
932 const RHS &R) {
933 return BinaryOp_match<LHS, RHS, Instruction::FDiv>(L, R);
934 }
935
936 template <typename LHS, typename RHS>
m_URem(const LHS & L,const RHS & R)937 inline BinaryOp_match<LHS, RHS, Instruction::URem> m_URem(const LHS &L,
938 const RHS &R) {
939 return BinaryOp_match<LHS, RHS, Instruction::URem>(L, R);
940 }
941
942 template <typename LHS, typename RHS>
m_SRem(const LHS & L,const RHS & R)943 inline BinaryOp_match<LHS, RHS, Instruction::SRem> m_SRem(const LHS &L,
944 const RHS &R) {
945 return BinaryOp_match<LHS, RHS, Instruction::SRem>(L, R);
946 }
947
948 template <typename LHS, typename RHS>
m_FRem(const LHS & L,const RHS & R)949 inline BinaryOp_match<LHS, RHS, Instruction::FRem> m_FRem(const LHS &L,
950 const RHS &R) {
951 return BinaryOp_match<LHS, RHS, Instruction::FRem>(L, R);
952 }
953
954 template <typename LHS, typename RHS>
m_And(const LHS & L,const RHS & R)955 inline BinaryOp_match<LHS, RHS, Instruction::And> m_And(const LHS &L,
956 const RHS &R) {
957 return BinaryOp_match<LHS, RHS, Instruction::And>(L, R);
958 }
959
960 template <typename LHS, typename RHS>
m_Or(const LHS & L,const RHS & R)961 inline BinaryOp_match<LHS, RHS, Instruction::Or> m_Or(const LHS &L,
962 const RHS &R) {
963 return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R);
964 }
965
966 template <typename LHS, typename RHS>
m_Xor(const LHS & L,const RHS & R)967 inline BinaryOp_match<LHS, RHS, Instruction::Xor> m_Xor(const LHS &L,
968 const RHS &R) {
969 return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R);
970 }
971
972 template <typename LHS, typename RHS>
m_Shl(const LHS & L,const RHS & R)973 inline BinaryOp_match<LHS, RHS, Instruction::Shl> m_Shl(const LHS &L,
974 const RHS &R) {
975 return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R);
976 }
977
978 template <typename LHS, typename RHS>
m_LShr(const LHS & L,const RHS & R)979 inline BinaryOp_match<LHS, RHS, Instruction::LShr> m_LShr(const LHS &L,
980 const RHS &R) {
981 return BinaryOp_match<LHS, RHS, Instruction::LShr>(L, R);
982 }
983
984 template <typename LHS, typename RHS>
m_AShr(const LHS & L,const RHS & R)985 inline BinaryOp_match<LHS, RHS, Instruction::AShr> m_AShr(const LHS &L,
986 const RHS &R) {
987 return BinaryOp_match<LHS, RHS, Instruction::AShr>(L, R);
988 }
989
990 template <typename LHS_t, typename RHS_t, unsigned Opcode,
991 unsigned WrapFlags = 0>
992 struct OverflowingBinaryOp_match {
993 LHS_t L;
994 RHS_t R;
995
OverflowingBinaryOp_matchOverflowingBinaryOp_match996 OverflowingBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS)
997 : L(LHS), R(RHS) {}
998
matchOverflowingBinaryOp_match999 template <typename OpTy> bool match(OpTy *V) {
1000 if (auto *Op = dyn_cast<OverflowingBinaryOperator>(V)) {
1001 if (Op->getOpcode() != Opcode)
1002 return false;
1003 if (WrapFlags & OverflowingBinaryOperator::NoUnsignedWrap &&
1004 !Op->hasNoUnsignedWrap())
1005 return false;
1006 if (WrapFlags & OverflowingBinaryOperator::NoSignedWrap &&
1007 !Op->hasNoSignedWrap())
1008 return false;
1009 return L.match(Op->getOperand(0)) && R.match(Op->getOperand(1));
1010 }
1011 return false;
1012 }
1013 };
1014
1015 template <typename LHS, typename RHS>
1016 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
1017 OverflowingBinaryOperator::NoSignedWrap>
m_NSWAdd(const LHS & L,const RHS & R)1018 m_NSWAdd(const LHS &L, const RHS &R) {
1019 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
1020 OverflowingBinaryOperator::NoSignedWrap>(
1021 L, R);
1022 }
1023 template <typename LHS, typename RHS>
1024 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
1025 OverflowingBinaryOperator::NoSignedWrap>
m_NSWSub(const LHS & L,const RHS & R)1026 m_NSWSub(const LHS &L, const RHS &R) {
1027 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
1028 OverflowingBinaryOperator::NoSignedWrap>(
1029 L, R);
1030 }
1031 template <typename LHS, typename RHS>
1032 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
1033 OverflowingBinaryOperator::NoSignedWrap>
m_NSWMul(const LHS & L,const RHS & R)1034 m_NSWMul(const LHS &L, const RHS &R) {
1035 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
1036 OverflowingBinaryOperator::NoSignedWrap>(
1037 L, R);
1038 }
1039 template <typename LHS, typename RHS>
1040 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
1041 OverflowingBinaryOperator::NoSignedWrap>
m_NSWShl(const LHS & L,const RHS & R)1042 m_NSWShl(const LHS &L, const RHS &R) {
1043 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
1044 OverflowingBinaryOperator::NoSignedWrap>(
1045 L, R);
1046 }
1047
1048 template <typename LHS, typename RHS>
1049 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
1050 OverflowingBinaryOperator::NoUnsignedWrap>
m_NUWAdd(const LHS & L,const RHS & R)1051 m_NUWAdd(const LHS &L, const RHS &R) {
1052 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
1053 OverflowingBinaryOperator::NoUnsignedWrap>(
1054 L, R);
1055 }
1056 template <typename LHS, typename RHS>
1057 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
1058 OverflowingBinaryOperator::NoUnsignedWrap>
m_NUWSub(const LHS & L,const RHS & R)1059 m_NUWSub(const LHS &L, const RHS &R) {
1060 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
1061 OverflowingBinaryOperator::NoUnsignedWrap>(
1062 L, R);
1063 }
1064 template <typename LHS, typename RHS>
1065 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
1066 OverflowingBinaryOperator::NoUnsignedWrap>
m_NUWMul(const LHS & L,const RHS & R)1067 m_NUWMul(const LHS &L, const RHS &R) {
1068 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
1069 OverflowingBinaryOperator::NoUnsignedWrap>(
1070 L, R);
1071 }
1072 template <typename LHS, typename RHS>
1073 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
1074 OverflowingBinaryOperator::NoUnsignedWrap>
m_NUWShl(const LHS & L,const RHS & R)1075 m_NUWShl(const LHS &L, const RHS &R) {
1076 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
1077 OverflowingBinaryOperator::NoUnsignedWrap>(
1078 L, R);
1079 }
1080
1081 //===----------------------------------------------------------------------===//
1082 // Class that matches a group of binary opcodes.
1083 //
1084 template <typename LHS_t, typename RHS_t, typename Predicate>
1085 struct BinOpPred_match : Predicate {
1086 LHS_t L;
1087 RHS_t R;
1088
BinOpPred_matchBinOpPred_match1089 BinOpPred_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
1090
matchBinOpPred_match1091 template <typename OpTy> bool match(OpTy *V) {
1092 if (auto *I = dyn_cast<Instruction>(V))
1093 return this->isOpType(I->getOpcode()) && L.match(I->getOperand(0)) &&
1094 R.match(I->getOperand(1));
1095 if (auto *CE = dyn_cast<ConstantExpr>(V))
1096 return this->isOpType(CE->getOpcode()) && L.match(CE->getOperand(0)) &&
1097 R.match(CE->getOperand(1));
1098 return false;
1099 }
1100 };
1101
1102 struct is_shift_op {
isOpTypeis_shift_op1103 bool isOpType(unsigned Opcode) { return Instruction::isShift(Opcode); }
1104 };
1105
1106 struct is_right_shift_op {
isOpTypeis_right_shift_op1107 bool isOpType(unsigned Opcode) {
1108 return Opcode == Instruction::LShr || Opcode == Instruction::AShr;
1109 }
1110 };
1111
1112 struct is_logical_shift_op {
isOpTypeis_logical_shift_op1113 bool isOpType(unsigned Opcode) {
1114 return Opcode == Instruction::LShr || Opcode == Instruction::Shl;
1115 }
1116 };
1117
1118 struct is_bitwiselogic_op {
isOpTypeis_bitwiselogic_op1119 bool isOpType(unsigned Opcode) {
1120 return Instruction::isBitwiseLogicOp(Opcode);
1121 }
1122 };
1123
1124 struct is_idiv_op {
isOpTypeis_idiv_op1125 bool isOpType(unsigned Opcode) {
1126 return Opcode == Instruction::SDiv || Opcode == Instruction::UDiv;
1127 }
1128 };
1129
1130 struct is_irem_op {
isOpTypeis_irem_op1131 bool isOpType(unsigned Opcode) {
1132 return Opcode == Instruction::SRem || Opcode == Instruction::URem;
1133 }
1134 };
1135
1136 /// Matches shift operations.
1137 template <typename LHS, typename RHS>
m_Shift(const LHS & L,const RHS & R)1138 inline BinOpPred_match<LHS, RHS, is_shift_op> m_Shift(const LHS &L,
1139 const RHS &R) {
1140 return BinOpPred_match<LHS, RHS, is_shift_op>(L, R);
1141 }
1142
1143 /// Matches logical shift operations.
1144 template <typename LHS, typename RHS>
m_Shr(const LHS & L,const RHS & R)1145 inline BinOpPred_match<LHS, RHS, is_right_shift_op> m_Shr(const LHS &L,
1146 const RHS &R) {
1147 return BinOpPred_match<LHS, RHS, is_right_shift_op>(L, R);
1148 }
1149
1150 /// Matches logical shift operations.
1151 template <typename LHS, typename RHS>
1152 inline BinOpPred_match<LHS, RHS, is_logical_shift_op>
m_LogicalShift(const LHS & L,const RHS & R)1153 m_LogicalShift(const LHS &L, const RHS &R) {
1154 return BinOpPred_match<LHS, RHS, is_logical_shift_op>(L, R);
1155 }
1156
1157 /// Matches bitwise logic operations.
1158 template <typename LHS, typename RHS>
1159 inline BinOpPred_match<LHS, RHS, is_bitwiselogic_op>
m_BitwiseLogic(const LHS & L,const RHS & R)1160 m_BitwiseLogic(const LHS &L, const RHS &R) {
1161 return BinOpPred_match<LHS, RHS, is_bitwiselogic_op>(L, R);
1162 }
1163
1164 /// Matches integer division operations.
1165 template <typename LHS, typename RHS>
m_IDiv(const LHS & L,const RHS & R)1166 inline BinOpPred_match<LHS, RHS, is_idiv_op> m_IDiv(const LHS &L,
1167 const RHS &R) {
1168 return BinOpPred_match<LHS, RHS, is_idiv_op>(L, R);
1169 }
1170
1171 /// Matches integer remainder operations.
1172 template <typename LHS, typename RHS>
m_IRem(const LHS & L,const RHS & R)1173 inline BinOpPred_match<LHS, RHS, is_irem_op> m_IRem(const LHS &L,
1174 const RHS &R) {
1175 return BinOpPred_match<LHS, RHS, is_irem_op>(L, R);
1176 }
1177
1178 //===----------------------------------------------------------------------===//
1179 // Class that matches exact binary ops.
1180 //
1181 template <typename SubPattern_t> struct Exact_match {
1182 SubPattern_t SubPattern;
1183
Exact_matchExact_match1184 Exact_match(const SubPattern_t &SP) : SubPattern(SP) {}
1185
matchExact_match1186 template <typename OpTy> bool match(OpTy *V) {
1187 if (auto *PEO = dyn_cast<PossiblyExactOperator>(V))
1188 return PEO->isExact() && SubPattern.match(V);
1189 return false;
1190 }
1191 };
1192
m_Exact(const T & SubPattern)1193 template <typename T> inline Exact_match<T> m_Exact(const T &SubPattern) {
1194 return SubPattern;
1195 }
1196
1197 //===----------------------------------------------------------------------===//
1198 // Matchers for CmpInst classes
1199 //
1200
1201 template <typename LHS_t, typename RHS_t, typename Class, typename PredicateTy,
1202 bool Commutable = false>
1203 struct CmpClass_match {
1204 PredicateTy &Predicate;
1205 LHS_t L;
1206 RHS_t R;
1207
1208 // The evaluation order is always stable, regardless of Commutability.
1209 // The LHS is always matched first.
CmpClass_matchCmpClass_match1210 CmpClass_match(PredicateTy &Pred, const LHS_t &LHS, const RHS_t &RHS)
1211 : Predicate(Pred), L(LHS), R(RHS) {}
1212
matchCmpClass_match1213 template <typename OpTy> bool match(OpTy *V) {
1214 if (auto *I = dyn_cast<Class>(V)) {
1215 if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) {
1216 Predicate = I->getPredicate();
1217 return true;
1218 } else if (Commutable && L.match(I->getOperand(1)) &&
1219 R.match(I->getOperand(0))) {
1220 Predicate = I->getSwappedPredicate();
1221 return true;
1222 }
1223 }
1224 return false;
1225 }
1226 };
1227
1228 template <typename LHS, typename RHS>
1229 inline CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate>
m_Cmp(CmpInst::Predicate & Pred,const LHS & L,const RHS & R)1230 m_Cmp(CmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1231 return CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate>(Pred, L, R);
1232 }
1233
1234 template <typename LHS, typename RHS>
1235 inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>
m_ICmp(ICmpInst::Predicate & Pred,const LHS & L,const RHS & R)1236 m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1237 return CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>(Pred, L, R);
1238 }
1239
1240 template <typename LHS, typename RHS>
1241 inline CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>
m_FCmp(FCmpInst::Predicate & Pred,const LHS & L,const RHS & R)1242 m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1243 return CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>(Pred, L, R);
1244 }
1245
1246 //===----------------------------------------------------------------------===//
1247 // Matchers for instructions with a given opcode and number of operands.
1248 //
1249
1250 /// Matches instructions with Opcode and three operands.
1251 template <typename T0, unsigned Opcode> struct OneOps_match {
1252 T0 Op1;
1253
OneOps_matchOneOps_match1254 OneOps_match(const T0 &Op1) : Op1(Op1) {}
1255
matchOneOps_match1256 template <typename OpTy> bool match(OpTy *V) {
1257 if (V->getValueID() == Value::InstructionVal + Opcode) {
1258 auto *I = cast<Instruction>(V);
1259 return Op1.match(I->getOperand(0));
1260 }
1261 return false;
1262 }
1263 };
1264
1265 /// Matches instructions with Opcode and three operands.
1266 template <typename T0, typename T1, unsigned Opcode> struct TwoOps_match {
1267 T0 Op1;
1268 T1 Op2;
1269
TwoOps_matchTwoOps_match1270 TwoOps_match(const T0 &Op1, const T1 &Op2) : Op1(Op1), Op2(Op2) {}
1271
matchTwoOps_match1272 template <typename OpTy> bool match(OpTy *V) {
1273 if (V->getValueID() == Value::InstructionVal + Opcode) {
1274 auto *I = cast<Instruction>(V);
1275 return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1));
1276 }
1277 return false;
1278 }
1279 };
1280
1281 /// Matches instructions with Opcode and three operands.
1282 template <typename T0, typename T1, typename T2, unsigned Opcode>
1283 struct ThreeOps_match {
1284 T0 Op1;
1285 T1 Op2;
1286 T2 Op3;
1287
ThreeOps_matchThreeOps_match1288 ThreeOps_match(const T0 &Op1, const T1 &Op2, const T2 &Op3)
1289 : Op1(Op1), Op2(Op2), Op3(Op3) {}
1290
matchThreeOps_match1291 template <typename OpTy> bool match(OpTy *V) {
1292 if (V->getValueID() == Value::InstructionVal + Opcode) {
1293 auto *I = cast<Instruction>(V);
1294 return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1)) &&
1295 Op3.match(I->getOperand(2));
1296 }
1297 return false;
1298 }
1299 };
1300
1301 /// Matches SelectInst.
1302 template <typename Cond, typename LHS, typename RHS>
1303 inline ThreeOps_match<Cond, LHS, RHS, Instruction::Select>
m_Select(const Cond & C,const LHS & L,const RHS & R)1304 m_Select(const Cond &C, const LHS &L, const RHS &R) {
1305 return ThreeOps_match<Cond, LHS, RHS, Instruction::Select>(C, L, R);
1306 }
1307
1308 /// This matches a select of two constants, e.g.:
1309 /// m_SelectCst<-1, 0>(m_Value(V))
1310 template <int64_t L, int64_t R, typename Cond>
1311 inline ThreeOps_match<Cond, constantint_match<L>, constantint_match<R>,
1312 Instruction::Select>
m_SelectCst(const Cond & C)1313 m_SelectCst(const Cond &C) {
1314 return m_Select(C, m_ConstantInt<L>(), m_ConstantInt<R>());
1315 }
1316
1317 /// Matches FreezeInst.
1318 template <typename OpTy>
m_Freeze(const OpTy & Op)1319 inline OneOps_match<OpTy, Instruction::Freeze> m_Freeze(const OpTy &Op) {
1320 return OneOps_match<OpTy, Instruction::Freeze>(Op);
1321 }
1322
1323 /// Matches InsertElementInst.
1324 template <typename Val_t, typename Elt_t, typename Idx_t>
1325 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)1326 m_InsertElt(const Val_t &Val, const Elt_t &Elt, const Idx_t &Idx) {
1327 return ThreeOps_match<Val_t, Elt_t, Idx_t, Instruction::InsertElement>(
1328 Val, Elt, Idx);
1329 }
1330
1331 /// Matches ExtractElementInst.
1332 template <typename Val_t, typename Idx_t>
1333 inline TwoOps_match<Val_t, Idx_t, Instruction::ExtractElement>
m_ExtractElt(const Val_t & Val,const Idx_t & Idx)1334 m_ExtractElt(const Val_t &Val, const Idx_t &Idx) {
1335 return TwoOps_match<Val_t, Idx_t, Instruction::ExtractElement>(Val, Idx);
1336 }
1337
1338 /// Matches shuffle.
1339 template <typename T0, typename T1, typename T2> struct Shuffle_match {
1340 T0 Op1;
1341 T1 Op2;
1342 T2 Mask;
1343
Shuffle_matchShuffle_match1344 Shuffle_match(const T0 &Op1, const T1 &Op2, const T2 &Mask)
1345 : Op1(Op1), Op2(Op2), Mask(Mask) {}
1346
matchShuffle_match1347 template <typename OpTy> bool match(OpTy *V) {
1348 if (auto *I = dyn_cast<ShuffleVectorInst>(V)) {
1349 return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1)) &&
1350 Mask.match(I->getShuffleMask());
1351 }
1352 return false;
1353 }
1354 };
1355
1356 struct m_Mask {
1357 ArrayRef<int> &MaskRef;
m_Maskm_Mask1358 m_Mask(ArrayRef<int> &MaskRef) : MaskRef(MaskRef) {}
matchm_Mask1359 bool match(ArrayRef<int> Mask) {
1360 MaskRef = Mask;
1361 return true;
1362 }
1363 };
1364
1365 struct m_ZeroMask {
matchm_ZeroMask1366 bool match(ArrayRef<int> Mask) {
1367 return all_of(Mask, [](int Elem) { return Elem == 0 || Elem == -1; });
1368 }
1369 };
1370
1371 struct m_SpecificMask {
1372 ArrayRef<int> &MaskRef;
m_SpecificMaskm_SpecificMask1373 m_SpecificMask(ArrayRef<int> &MaskRef) : MaskRef(MaskRef) {}
matchm_SpecificMask1374 bool match(ArrayRef<int> Mask) { return MaskRef == Mask; }
1375 };
1376
1377 struct m_SplatOrUndefMask {
1378 int &SplatIndex;
m_SplatOrUndefMaskm_SplatOrUndefMask1379 m_SplatOrUndefMask(int &SplatIndex) : SplatIndex(SplatIndex) {}
matchm_SplatOrUndefMask1380 bool match(ArrayRef<int> Mask) {
1381 auto First = find_if(Mask, [](int Elem) { return Elem != -1; });
1382 if (First == Mask.end())
1383 return false;
1384 SplatIndex = *First;
1385 return all_of(Mask,
1386 [First](int Elem) { return Elem == *First || Elem == -1; });
1387 }
1388 };
1389
1390 /// Matches ShuffleVectorInst independently of mask value.
1391 template <typename V1_t, typename V2_t>
1392 inline TwoOps_match<V1_t, V2_t, Instruction::ShuffleVector>
m_Shuffle(const V1_t & v1,const V2_t & v2)1393 m_Shuffle(const V1_t &v1, const V2_t &v2) {
1394 return TwoOps_match<V1_t, V2_t, Instruction::ShuffleVector>(v1, v2);
1395 }
1396
1397 template <typename V1_t, typename V2_t, typename Mask_t>
1398 inline Shuffle_match<V1_t, V2_t, Mask_t>
m_Shuffle(const V1_t & v1,const V2_t & v2,const Mask_t & mask)1399 m_Shuffle(const V1_t &v1, const V2_t &v2, const Mask_t &mask) {
1400 return Shuffle_match<V1_t, V2_t, Mask_t>(v1, v2, mask);
1401 }
1402
1403 /// Matches LoadInst.
1404 template <typename OpTy>
m_Load(const OpTy & Op)1405 inline OneOps_match<OpTy, Instruction::Load> m_Load(const OpTy &Op) {
1406 return OneOps_match<OpTy, Instruction::Load>(Op);
1407 }
1408
1409 /// Matches StoreInst.
1410 template <typename ValueOpTy, typename PointerOpTy>
1411 inline TwoOps_match<ValueOpTy, PointerOpTy, Instruction::Store>
m_Store(const ValueOpTy & ValueOp,const PointerOpTy & PointerOp)1412 m_Store(const ValueOpTy &ValueOp, const PointerOpTy &PointerOp) {
1413 return TwoOps_match<ValueOpTy, PointerOpTy, Instruction::Store>(ValueOp,
1414 PointerOp);
1415 }
1416
1417 //===----------------------------------------------------------------------===//
1418 // Matchers for CastInst classes
1419 //
1420
1421 template <typename Op_t, unsigned Opcode> struct CastClass_match {
1422 Op_t Op;
1423
CastClass_matchCastClass_match1424 CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {}
1425
matchCastClass_match1426 template <typename OpTy> bool match(OpTy *V) {
1427 if (auto *O = dyn_cast<Operator>(V))
1428 return O->getOpcode() == Opcode && Op.match(O->getOperand(0));
1429 return false;
1430 }
1431 };
1432
1433 /// Matches BitCast.
1434 template <typename OpTy>
m_BitCast(const OpTy & Op)1435 inline CastClass_match<OpTy, Instruction::BitCast> m_BitCast(const OpTy &Op) {
1436 return CastClass_match<OpTy, Instruction::BitCast>(Op);
1437 }
1438
1439 /// Matches PtrToInt.
1440 template <typename OpTy>
m_PtrToInt(const OpTy & Op)1441 inline CastClass_match<OpTy, Instruction::PtrToInt> m_PtrToInt(const OpTy &Op) {
1442 return CastClass_match<OpTy, Instruction::PtrToInt>(Op);
1443 }
1444
1445 /// Matches Trunc.
1446 template <typename OpTy>
m_Trunc(const OpTy & Op)1447 inline CastClass_match<OpTy, Instruction::Trunc> m_Trunc(const OpTy &Op) {
1448 return CastClass_match<OpTy, Instruction::Trunc>(Op);
1449 }
1450
1451 template <typename OpTy>
1452 inline match_combine_or<CastClass_match<OpTy, Instruction::Trunc>, OpTy>
m_TruncOrSelf(const OpTy & Op)1453 m_TruncOrSelf(const OpTy &Op) {
1454 return m_CombineOr(m_Trunc(Op), Op);
1455 }
1456
1457 /// Matches SExt.
1458 template <typename OpTy>
m_SExt(const OpTy & Op)1459 inline CastClass_match<OpTy, Instruction::SExt> m_SExt(const OpTy &Op) {
1460 return CastClass_match<OpTy, Instruction::SExt>(Op);
1461 }
1462
1463 /// Matches ZExt.
1464 template <typename OpTy>
m_ZExt(const OpTy & Op)1465 inline CastClass_match<OpTy, Instruction::ZExt> m_ZExt(const OpTy &Op) {
1466 return CastClass_match<OpTy, Instruction::ZExt>(Op);
1467 }
1468
1469 template <typename OpTy>
1470 inline match_combine_or<CastClass_match<OpTy, Instruction::ZExt>, OpTy>
m_ZExtOrSelf(const OpTy & Op)1471 m_ZExtOrSelf(const OpTy &Op) {
1472 return m_CombineOr(m_ZExt(Op), Op);
1473 }
1474
1475 template <typename OpTy>
1476 inline match_combine_or<CastClass_match<OpTy, Instruction::SExt>, OpTy>
m_SExtOrSelf(const OpTy & Op)1477 m_SExtOrSelf(const OpTy &Op) {
1478 return m_CombineOr(m_SExt(Op), Op);
1479 }
1480
1481 template <typename OpTy>
1482 inline match_combine_or<CastClass_match<OpTy, Instruction::ZExt>,
1483 CastClass_match<OpTy, Instruction::SExt>>
m_ZExtOrSExt(const OpTy & Op)1484 m_ZExtOrSExt(const OpTy &Op) {
1485 return m_CombineOr(m_ZExt(Op), m_SExt(Op));
1486 }
1487
1488 template <typename OpTy>
1489 inline match_combine_or<
1490 match_combine_or<CastClass_match<OpTy, Instruction::ZExt>,
1491 CastClass_match<OpTy, Instruction::SExt>>,
1492 OpTy>
m_ZExtOrSExtOrSelf(const OpTy & Op)1493 m_ZExtOrSExtOrSelf(const OpTy &Op) {
1494 return m_CombineOr(m_ZExtOrSExt(Op), Op);
1495 }
1496
1497 template <typename OpTy>
m_UIToFP(const OpTy & Op)1498 inline CastClass_match<OpTy, Instruction::UIToFP> m_UIToFP(const OpTy &Op) {
1499 return CastClass_match<OpTy, Instruction::UIToFP>(Op);
1500 }
1501
1502 template <typename OpTy>
m_SIToFP(const OpTy & Op)1503 inline CastClass_match<OpTy, Instruction::SIToFP> m_SIToFP(const OpTy &Op) {
1504 return CastClass_match<OpTy, Instruction::SIToFP>(Op);
1505 }
1506
1507 template <typename OpTy>
m_FPToUI(const OpTy & Op)1508 inline CastClass_match<OpTy, Instruction::FPToUI> m_FPToUI(const OpTy &Op) {
1509 return CastClass_match<OpTy, Instruction::FPToUI>(Op);
1510 }
1511
1512 template <typename OpTy>
m_FPToSI(const OpTy & Op)1513 inline CastClass_match<OpTy, Instruction::FPToSI> m_FPToSI(const OpTy &Op) {
1514 return CastClass_match<OpTy, Instruction::FPToSI>(Op);
1515 }
1516
1517 template <typename OpTy>
m_FPTrunc(const OpTy & Op)1518 inline CastClass_match<OpTy, Instruction::FPTrunc> m_FPTrunc(const OpTy &Op) {
1519 return CastClass_match<OpTy, Instruction::FPTrunc>(Op);
1520 }
1521
1522 template <typename OpTy>
m_FPExt(const OpTy & Op)1523 inline CastClass_match<OpTy, Instruction::FPExt> m_FPExt(const OpTy &Op) {
1524 return CastClass_match<OpTy, Instruction::FPExt>(Op);
1525 }
1526
1527 //===----------------------------------------------------------------------===//
1528 // Matchers for control flow.
1529 //
1530
1531 struct br_match {
1532 BasicBlock *&Succ;
1533
br_matchbr_match1534 br_match(BasicBlock *&Succ) : Succ(Succ) {}
1535
matchbr_match1536 template <typename OpTy> bool match(OpTy *V) {
1537 if (auto *BI = dyn_cast<BranchInst>(V))
1538 if (BI->isUnconditional()) {
1539 Succ = BI->getSuccessor(0);
1540 return true;
1541 }
1542 return false;
1543 }
1544 };
1545
m_UnconditionalBr(BasicBlock * & Succ)1546 inline br_match m_UnconditionalBr(BasicBlock *&Succ) { return br_match(Succ); }
1547
1548 template <typename Cond_t, typename TrueBlock_t, typename FalseBlock_t>
1549 struct brc_match {
1550 Cond_t Cond;
1551 TrueBlock_t T;
1552 FalseBlock_t F;
1553
brc_matchbrc_match1554 brc_match(const Cond_t &C, const TrueBlock_t &t, const FalseBlock_t &f)
1555 : Cond(C), T(t), F(f) {}
1556
matchbrc_match1557 template <typename OpTy> bool match(OpTy *V) {
1558 if (auto *BI = dyn_cast<BranchInst>(V))
1559 if (BI->isConditional() && Cond.match(BI->getCondition()))
1560 return T.match(BI->getSuccessor(0)) && F.match(BI->getSuccessor(1));
1561 return false;
1562 }
1563 };
1564
1565 template <typename Cond_t>
1566 inline brc_match<Cond_t, bind_ty<BasicBlock>, bind_ty<BasicBlock>>
m_Br(const Cond_t & C,BasicBlock * & T,BasicBlock * & F)1567 m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) {
1568 return brc_match<Cond_t, bind_ty<BasicBlock>, bind_ty<BasicBlock>>(
1569 C, m_BasicBlock(T), m_BasicBlock(F));
1570 }
1571
1572 template <typename Cond_t, typename TrueBlock_t, typename FalseBlock_t>
1573 inline brc_match<Cond_t, TrueBlock_t, FalseBlock_t>
m_Br(const Cond_t & C,const TrueBlock_t & T,const FalseBlock_t & F)1574 m_Br(const Cond_t &C, const TrueBlock_t &T, const FalseBlock_t &F) {
1575 return brc_match<Cond_t, TrueBlock_t, FalseBlock_t>(C, T, F);
1576 }
1577
1578 //===----------------------------------------------------------------------===//
1579 // Matchers for max/min idioms, eg: "select (sgt x, y), x, y" -> smax(x,y).
1580 //
1581
1582 template <typename CmpInst_t, typename LHS_t, typename RHS_t, typename Pred_t,
1583 bool Commutable = false>
1584 struct MaxMin_match {
1585 LHS_t L;
1586 RHS_t R;
1587
1588 // The evaluation order is always stable, regardless of Commutability.
1589 // The LHS is always matched first.
MaxMin_matchMaxMin_match1590 MaxMin_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
1591
matchMaxMin_match1592 template <typename OpTy> bool match(OpTy *V) {
1593 // Look for "(x pred y) ? x : y" or "(x pred y) ? y : x".
1594 auto *SI = dyn_cast<SelectInst>(V);
1595 if (!SI)
1596 return false;
1597 auto *Cmp = dyn_cast<CmpInst_t>(SI->getCondition());
1598 if (!Cmp)
1599 return false;
1600 // At this point we have a select conditioned on a comparison. Check that
1601 // it is the values returned by the select that are being compared.
1602 Value *TrueVal = SI->getTrueValue();
1603 Value *FalseVal = SI->getFalseValue();
1604 Value *LHS = Cmp->getOperand(0);
1605 Value *RHS = Cmp->getOperand(1);
1606 if ((TrueVal != LHS || FalseVal != RHS) &&
1607 (TrueVal != RHS || FalseVal != LHS))
1608 return false;
1609 typename CmpInst_t::Predicate Pred =
1610 LHS == TrueVal ? Cmp->getPredicate() : Cmp->getInversePredicate();
1611 // Does "(x pred y) ? x : y" represent the desired max/min operation?
1612 if (!Pred_t::match(Pred))
1613 return false;
1614 // It does! Bind the operands.
1615 return (L.match(LHS) && R.match(RHS)) ||
1616 (Commutable && L.match(RHS) && R.match(LHS));
1617 }
1618 };
1619
1620 /// Helper class for identifying signed max predicates.
1621 struct smax_pred_ty {
matchsmax_pred_ty1622 static bool match(ICmpInst::Predicate Pred) {
1623 return Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE;
1624 }
1625 };
1626
1627 /// Helper class for identifying signed min predicates.
1628 struct smin_pred_ty {
matchsmin_pred_ty1629 static bool match(ICmpInst::Predicate Pred) {
1630 return Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_SLE;
1631 }
1632 };
1633
1634 /// Helper class for identifying unsigned max predicates.
1635 struct umax_pred_ty {
matchumax_pred_ty1636 static bool match(ICmpInst::Predicate Pred) {
1637 return Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE;
1638 }
1639 };
1640
1641 /// Helper class for identifying unsigned min predicates.
1642 struct umin_pred_ty {
matchumin_pred_ty1643 static bool match(ICmpInst::Predicate Pred) {
1644 return Pred == CmpInst::ICMP_ULT || Pred == CmpInst::ICMP_ULE;
1645 }
1646 };
1647
1648 /// Helper class for identifying ordered max predicates.
1649 struct ofmax_pred_ty {
matchofmax_pred_ty1650 static bool match(FCmpInst::Predicate Pred) {
1651 return Pred == CmpInst::FCMP_OGT || Pred == CmpInst::FCMP_OGE;
1652 }
1653 };
1654
1655 /// Helper class for identifying ordered min predicates.
1656 struct ofmin_pred_ty {
matchofmin_pred_ty1657 static bool match(FCmpInst::Predicate Pred) {
1658 return Pred == CmpInst::FCMP_OLT || Pred == CmpInst::FCMP_OLE;
1659 }
1660 };
1661
1662 /// Helper class for identifying unordered max predicates.
1663 struct ufmax_pred_ty {
matchufmax_pred_ty1664 static bool match(FCmpInst::Predicate Pred) {
1665 return Pred == CmpInst::FCMP_UGT || Pred == CmpInst::FCMP_UGE;
1666 }
1667 };
1668
1669 /// Helper class for identifying unordered min predicates.
1670 struct ufmin_pred_ty {
matchufmin_pred_ty1671 static bool match(FCmpInst::Predicate Pred) {
1672 return Pred == CmpInst::FCMP_ULT || Pred == CmpInst::FCMP_ULE;
1673 }
1674 };
1675
1676 template <typename LHS, typename RHS>
m_SMax(const LHS & L,const RHS & R)1677 inline MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty> m_SMax(const LHS &L,
1678 const RHS &R) {
1679 return MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty>(L, R);
1680 }
1681
1682 template <typename LHS, typename RHS>
m_SMin(const LHS & L,const RHS & R)1683 inline MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty> m_SMin(const LHS &L,
1684 const RHS &R) {
1685 return MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty>(L, R);
1686 }
1687
1688 template <typename LHS, typename RHS>
m_UMax(const LHS & L,const RHS & R)1689 inline MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty> m_UMax(const LHS &L,
1690 const RHS &R) {
1691 return MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty>(L, R);
1692 }
1693
1694 template <typename LHS, typename RHS>
m_UMin(const LHS & L,const RHS & R)1695 inline MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty> m_UMin(const LHS &L,
1696 const RHS &R) {
1697 return MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty>(L, R);
1698 }
1699
1700 /// Match an 'ordered' floating point maximum function.
1701 /// Floating point has one special value 'NaN'. Therefore, there is no total
1702 /// order. However, if we can ignore the 'NaN' value (for example, because of a
1703 /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum'
1704 /// semantics. In the presence of 'NaN' we have to preserve the original
1705 /// select(fcmp(ogt/ge, L, R), L, R) semantics matched by this predicate.
1706 ///
1707 /// max(L, R) iff L and R are not NaN
1708 /// m_OrdFMax(L, R) = R iff L or R are NaN
1709 template <typename LHS, typename RHS>
m_OrdFMax(const LHS & L,const RHS & R)1710 inline MaxMin_match<FCmpInst, LHS, RHS, ofmax_pred_ty> m_OrdFMax(const LHS &L,
1711 const RHS &R) {
1712 return MaxMin_match<FCmpInst, LHS, RHS, ofmax_pred_ty>(L, R);
1713 }
1714
1715 /// Match an 'ordered' floating point minimum function.
1716 /// Floating point has one special value 'NaN'. Therefore, there is no total
1717 /// order. However, if we can ignore the 'NaN' value (for example, because of a
1718 /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum'
1719 /// semantics. In the presence of 'NaN' we have to preserve the original
1720 /// select(fcmp(olt/le, L, R), L, R) semantics matched by this predicate.
1721 ///
1722 /// min(L, R) iff L and R are not NaN
1723 /// m_OrdFMin(L, R) = R iff L or R are NaN
1724 template <typename LHS, typename RHS>
m_OrdFMin(const LHS & L,const RHS & R)1725 inline MaxMin_match<FCmpInst, LHS, RHS, ofmin_pred_ty> m_OrdFMin(const LHS &L,
1726 const RHS &R) {
1727 return MaxMin_match<FCmpInst, LHS, RHS, ofmin_pred_ty>(L, R);
1728 }
1729
1730 /// Match an 'unordered' floating point maximum function.
1731 /// Floating point has one special value 'NaN'. Therefore, there is no total
1732 /// order. However, if we can ignore the 'NaN' value (for example, because of a
1733 /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum'
1734 /// semantics. In the presence of 'NaN' we have to preserve the original
1735 /// select(fcmp(ugt/ge, L, R), L, R) semantics matched by this predicate.
1736 ///
1737 /// max(L, R) iff L and R are not NaN
1738 /// m_UnordFMax(L, R) = L iff L or R are NaN
1739 template <typename LHS, typename RHS>
1740 inline MaxMin_match<FCmpInst, LHS, RHS, ufmax_pred_ty>
m_UnordFMax(const LHS & L,const RHS & R)1741 m_UnordFMax(const LHS &L, const RHS &R) {
1742 return MaxMin_match<FCmpInst, LHS, RHS, ufmax_pred_ty>(L, R);
1743 }
1744
1745 /// Match an 'unordered' floating point minimum function.
1746 /// Floating point has one special value 'NaN'. Therefore, there is no total
1747 /// order. However, if we can ignore the 'NaN' value (for example, because of a
1748 /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum'
1749 /// semantics. In the presence of 'NaN' we have to preserve the original
1750 /// select(fcmp(ult/le, L, R), L, R) semantics matched by this predicate.
1751 ///
1752 /// min(L, R) iff L and R are not NaN
1753 /// m_UnordFMin(L, R) = L iff L or R are NaN
1754 template <typename LHS, typename RHS>
1755 inline MaxMin_match<FCmpInst, LHS, RHS, ufmin_pred_ty>
m_UnordFMin(const LHS & L,const RHS & R)1756 m_UnordFMin(const LHS &L, const RHS &R) {
1757 return MaxMin_match<FCmpInst, LHS, RHS, ufmin_pred_ty>(L, R);
1758 }
1759
1760 //===----------------------------------------------------------------------===//
1761 // Matchers for overflow check patterns: e.g. (a + b) u< a, (a ^ -1) <u b
1762 // Note that S might be matched to other instructions than AddInst.
1763 //
1764
1765 template <typename LHS_t, typename RHS_t, typename Sum_t>
1766 struct UAddWithOverflow_match {
1767 LHS_t L;
1768 RHS_t R;
1769 Sum_t S;
1770
UAddWithOverflow_matchUAddWithOverflow_match1771 UAddWithOverflow_match(const LHS_t &L, const RHS_t &R, const Sum_t &S)
1772 : L(L), R(R), S(S) {}
1773
matchUAddWithOverflow_match1774 template <typename OpTy> bool match(OpTy *V) {
1775 Value *ICmpLHS, *ICmpRHS;
1776 ICmpInst::Predicate Pred;
1777 if (!m_ICmp(Pred, m_Value(ICmpLHS), m_Value(ICmpRHS)).match(V))
1778 return false;
1779
1780 Value *AddLHS, *AddRHS;
1781 auto AddExpr = m_Add(m_Value(AddLHS), m_Value(AddRHS));
1782
1783 // (a + b) u< a, (a + b) u< b
1784 if (Pred == ICmpInst::ICMP_ULT)
1785 if (AddExpr.match(ICmpLHS) && (ICmpRHS == AddLHS || ICmpRHS == AddRHS))
1786 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS);
1787
1788 // a >u (a + b), b >u (a + b)
1789 if (Pred == ICmpInst::ICMP_UGT)
1790 if (AddExpr.match(ICmpRHS) && (ICmpLHS == AddLHS || ICmpLHS == AddRHS))
1791 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS);
1792
1793 Value *Op1;
1794 auto XorExpr = m_OneUse(m_Xor(m_Value(Op1), m_AllOnes()));
1795 // (a ^ -1) <u b
1796 if (Pred == ICmpInst::ICMP_ULT) {
1797 if (XorExpr.match(ICmpLHS))
1798 return L.match(Op1) && R.match(ICmpRHS) && S.match(ICmpLHS);
1799 }
1800 // b > u (a ^ -1)
1801 if (Pred == ICmpInst::ICMP_UGT) {
1802 if (XorExpr.match(ICmpRHS))
1803 return L.match(Op1) && R.match(ICmpLHS) && S.match(ICmpRHS);
1804 }
1805
1806 // Match special-case for increment-by-1.
1807 if (Pred == ICmpInst::ICMP_EQ) {
1808 // (a + 1) == 0
1809 // (1 + a) == 0
1810 if (AddExpr.match(ICmpLHS) && m_ZeroInt().match(ICmpRHS) &&
1811 (m_One().match(AddLHS) || m_One().match(AddRHS)))
1812 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS);
1813 // 0 == (a + 1)
1814 // 0 == (1 + a)
1815 if (m_ZeroInt().match(ICmpLHS) && AddExpr.match(ICmpRHS) &&
1816 (m_One().match(AddLHS) || m_One().match(AddRHS)))
1817 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS);
1818 }
1819
1820 return false;
1821 }
1822 };
1823
1824 /// Match an icmp instruction checking for unsigned overflow on addition.
1825 ///
1826 /// S is matched to the addition whose result is being checked for overflow, and
1827 /// L and R are matched to the LHS and RHS of S.
1828 template <typename LHS_t, typename RHS_t, typename Sum_t>
1829 UAddWithOverflow_match<LHS_t, RHS_t, Sum_t>
m_UAddWithOverflow(const LHS_t & L,const RHS_t & R,const Sum_t & S)1830 m_UAddWithOverflow(const LHS_t &L, const RHS_t &R, const Sum_t &S) {
1831 return UAddWithOverflow_match<LHS_t, RHS_t, Sum_t>(L, R, S);
1832 }
1833
1834 template <typename Opnd_t> struct Argument_match {
1835 unsigned OpI;
1836 Opnd_t Val;
1837
Argument_matchArgument_match1838 Argument_match(unsigned OpIdx, const Opnd_t &V) : OpI(OpIdx), Val(V) {}
1839
matchArgument_match1840 template <typename OpTy> bool match(OpTy *V) {
1841 // FIXME: Should likely be switched to use `CallBase`.
1842 if (const auto *CI = dyn_cast<CallInst>(V))
1843 return Val.match(CI->getArgOperand(OpI));
1844 return false;
1845 }
1846 };
1847
1848 /// Match an argument.
1849 template <unsigned OpI, typename Opnd_t>
m_Argument(const Opnd_t & Op)1850 inline Argument_match<Opnd_t> m_Argument(const Opnd_t &Op) {
1851 return Argument_match<Opnd_t>(OpI, Op);
1852 }
1853
1854 /// Intrinsic matchers.
1855 struct IntrinsicID_match {
1856 unsigned ID;
1857
IntrinsicID_matchIntrinsicID_match1858 IntrinsicID_match(Intrinsic::ID IntrID) : ID(IntrID) {}
1859
matchIntrinsicID_match1860 template <typename OpTy> bool match(OpTy *V) {
1861 if (const auto *CI = dyn_cast<CallInst>(V))
1862 if (const auto *F = CI->getCalledFunction())
1863 return F->getIntrinsicID() == ID;
1864 return false;
1865 }
1866 };
1867
1868 /// Intrinsic matches are combinations of ID matchers, and argument
1869 /// matchers. Higher arity matcher are defined recursively in terms of and-ing
1870 /// them with lower arity matchers. Here's some convenient typedefs for up to
1871 /// several arguments, and more can be added as needed
1872 template <typename T0 = void, typename T1 = void, typename T2 = void,
1873 typename T3 = void, typename T4 = void, typename T5 = void,
1874 typename T6 = void, typename T7 = void, typename T8 = void,
1875 typename T9 = void, typename T10 = void>
1876 struct m_Intrinsic_Ty;
1877 template <typename T0> struct m_Intrinsic_Ty<T0> {
1878 using Ty = match_combine_and<IntrinsicID_match, Argument_match<T0>>;
1879 };
1880 template <typename T0, typename T1> struct m_Intrinsic_Ty<T0, T1> {
1881 using Ty =
1882 match_combine_and<typename m_Intrinsic_Ty<T0>::Ty, Argument_match<T1>>;
1883 };
1884 template <typename T0, typename T1, typename T2>
1885 struct m_Intrinsic_Ty<T0, T1, T2> {
1886 using Ty =
1887 match_combine_and<typename m_Intrinsic_Ty<T0, T1>::Ty,
1888 Argument_match<T2>>;
1889 };
1890 template <typename T0, typename T1, typename T2, typename T3>
1891 struct m_Intrinsic_Ty<T0, T1, T2, T3> {
1892 using Ty =
1893 match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2>::Ty,
1894 Argument_match<T3>>;
1895 };
1896
1897 template <typename T0, typename T1, typename T2, typename T3, typename T4>
1898 struct m_Intrinsic_Ty<T0, T1, T2, T3, T4> {
1899 using Ty = match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2, T3>::Ty,
1900 Argument_match<T4>>;
1901 };
1902
1903 template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5>
1904 struct m_Intrinsic_Ty<T0, T1, T2, T3, T4, T5> {
1905 using Ty = match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2, T3, T4>::Ty,
1906 Argument_match<T5>>;
1907 };
1908
1909 /// Match intrinsic calls like this:
1910 /// m_Intrinsic<Intrinsic::fabs>(m_Value(X))
1911 template <Intrinsic::ID IntrID> inline IntrinsicID_match m_Intrinsic() {
1912 return IntrinsicID_match(IntrID);
1913 }
1914
1915 template <Intrinsic::ID IntrID, typename T0>
1916 inline typename m_Intrinsic_Ty<T0>::Ty m_Intrinsic(const T0 &Op0) {
1917 return m_CombineAnd(m_Intrinsic<IntrID>(), m_Argument<0>(Op0));
1918 }
1919
1920 template <Intrinsic::ID IntrID, typename T0, typename T1>
1921 inline typename m_Intrinsic_Ty<T0, T1>::Ty m_Intrinsic(const T0 &Op0,
1922 const T1 &Op1) {
1923 return m_CombineAnd(m_Intrinsic<IntrID>(Op0), m_Argument<1>(Op1));
1924 }
1925
1926 template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2>
1927 inline typename m_Intrinsic_Ty<T0, T1, T2>::Ty
1928 m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2) {
1929 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1), m_Argument<2>(Op2));
1930 }
1931
1932 template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2,
1933 typename T3>
1934 inline typename m_Intrinsic_Ty<T0, T1, T2, T3>::Ty
1935 m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3) {
1936 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2), m_Argument<3>(Op3));
1937 }
1938
1939 template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2,
1940 typename T3, typename T4>
1941 inline typename m_Intrinsic_Ty<T0, T1, T2, T3, T4>::Ty
1942 m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3,
1943 const T4 &Op4) {
1944 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2, Op3),
1945 m_Argument<4>(Op4));
1946 }
1947
1948 template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2,
1949 typename T3, typename T4, typename T5>
1950 inline typename m_Intrinsic_Ty<T0, T1, T2, T3, T4, T5>::Ty
1951 m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3,
1952 const T4 &Op4, const T5 &Op5) {
1953 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2, Op3, Op4),
1954 m_Argument<5>(Op5));
1955 }
1956
1957 // Helper intrinsic matching specializations.
1958 template <typename Opnd0>
1959 inline typename m_Intrinsic_Ty<Opnd0>::Ty m_BitReverse(const Opnd0 &Op0) {
1960 return m_Intrinsic<Intrinsic::bitreverse>(Op0);
1961 }
1962
1963 template <typename Opnd0>
1964 inline typename m_Intrinsic_Ty<Opnd0>::Ty m_BSwap(const Opnd0 &Op0) {
1965 return m_Intrinsic<Intrinsic::bswap>(Op0);
1966 }
1967
1968 template <typename Opnd0>
1969 inline typename m_Intrinsic_Ty<Opnd0>::Ty m_FAbs(const Opnd0 &Op0) {
1970 return m_Intrinsic<Intrinsic::fabs>(Op0);
1971 }
1972
1973 template <typename Opnd0>
1974 inline typename m_Intrinsic_Ty<Opnd0>::Ty m_FCanonicalize(const Opnd0 &Op0) {
1975 return m_Intrinsic<Intrinsic::canonicalize>(Op0);
1976 }
1977
1978 template <typename Opnd0, typename Opnd1>
1979 inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMin(const Opnd0 &Op0,
1980 const Opnd1 &Op1) {
1981 return m_Intrinsic<Intrinsic::minnum>(Op0, Op1);
1982 }
1983
1984 template <typename Opnd0, typename Opnd1>
1985 inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMax(const Opnd0 &Op0,
1986 const Opnd1 &Op1) {
1987 return m_Intrinsic<Intrinsic::maxnum>(Op0, Op1);
1988 }
1989
1990 //===----------------------------------------------------------------------===//
1991 // Matchers for two-operands operators with the operators in either order
1992 //
1993
1994 /// Matches a BinaryOperator with LHS and RHS in either order.
1995 template <typename LHS, typename RHS>
1996 inline AnyBinaryOp_match<LHS, RHS, true> m_c_BinOp(const LHS &L, const RHS &R) {
1997 return AnyBinaryOp_match<LHS, RHS, true>(L, R);
1998 }
1999
2000 /// Matches an ICmp with a predicate over LHS and RHS in either order.
2001 /// Swaps the predicate if operands are commuted.
2002 template <typename LHS, typename RHS>
2003 inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate, true>
2004 m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
2005 return CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate, true>(Pred, L,
2006 R);
2007 }
2008
2009 /// Matches a Add with LHS and RHS in either order.
2010 template <typename LHS, typename RHS>
2011 inline BinaryOp_match<LHS, RHS, Instruction::Add, true> m_c_Add(const LHS &L,
2012 const RHS &R) {
2013 return BinaryOp_match<LHS, RHS, Instruction::Add, true>(L, R);
2014 }
2015
2016 /// Matches a Mul with LHS and RHS in either order.
2017 template <typename LHS, typename RHS>
2018 inline BinaryOp_match<LHS, RHS, Instruction::Mul, true> m_c_Mul(const LHS &L,
2019 const RHS &R) {
2020 return BinaryOp_match<LHS, RHS, Instruction::Mul, true>(L, R);
2021 }
2022
2023 /// Matches an And with LHS and RHS in either order.
2024 template <typename LHS, typename RHS>
2025 inline BinaryOp_match<LHS, RHS, Instruction::And, true> m_c_And(const LHS &L,
2026 const RHS &R) {
2027 return BinaryOp_match<LHS, RHS, Instruction::And, true>(L, R);
2028 }
2029
2030 /// Matches an Or with LHS and RHS in either order.
2031 template <typename LHS, typename RHS>
2032 inline BinaryOp_match<LHS, RHS, Instruction::Or, true> m_c_Or(const LHS &L,
2033 const RHS &R) {
2034 return BinaryOp_match<LHS, RHS, Instruction::Or, true>(L, R);
2035 }
2036
2037 /// Matches an Xor with LHS and RHS in either order.
2038 template <typename LHS, typename RHS>
2039 inline BinaryOp_match<LHS, RHS, Instruction::Xor, true> m_c_Xor(const LHS &L,
2040 const RHS &R) {
2041 return BinaryOp_match<LHS, RHS, Instruction::Xor, true>(L, R);
2042 }
2043
2044 /// Matches a 'Neg' as 'sub 0, V'.
2045 template <typename ValTy>
2046 inline BinaryOp_match<cst_pred_ty<is_zero_int>, ValTy, Instruction::Sub>
2047 m_Neg(const ValTy &V) {
2048 return m_Sub(m_ZeroInt(), V);
2049 }
2050
2051 /// Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
2052 template <typename ValTy>
2053 inline BinaryOp_match<ValTy, cst_pred_ty<is_all_ones>, Instruction::Xor, true>
2054 m_Not(const ValTy &V) {
2055 return m_c_Xor(V, m_AllOnes());
2056 }
2057
2058 /// Matches an SMin with LHS and RHS in either order.
2059 template <typename LHS, typename RHS>
2060 inline MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>
2061 m_c_SMin(const LHS &L, const RHS &R) {
2062 return MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>(L, R);
2063 }
2064 /// Matches an SMax with LHS and RHS in either order.
2065 template <typename LHS, typename RHS>
2066 inline MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true>
2067 m_c_SMax(const LHS &L, const RHS &R) {
2068 return MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true>(L, R);
2069 }
2070 /// Matches a UMin with LHS and RHS in either order.
2071 template <typename LHS, typename RHS>
2072 inline MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true>
2073 m_c_UMin(const LHS &L, const RHS &R) {
2074 return MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true>(L, R);
2075 }
2076 /// Matches a UMax with LHS and RHS in either order.
2077 template <typename LHS, typename RHS>
2078 inline MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true>
2079 m_c_UMax(const LHS &L, const RHS &R) {
2080 return MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true>(L, R);
2081 }
2082
2083 /// Matches FAdd with LHS and RHS in either order.
2084 template <typename LHS, typename RHS>
2085 inline BinaryOp_match<LHS, RHS, Instruction::FAdd, true>
2086 m_c_FAdd(const LHS &L, const RHS &R) {
2087 return BinaryOp_match<LHS, RHS, Instruction::FAdd, true>(L, R);
2088 }
2089
2090 /// Matches FMul with LHS and RHS in either order.
2091 template <typename LHS, typename RHS>
2092 inline BinaryOp_match<LHS, RHS, Instruction::FMul, true>
2093 m_c_FMul(const LHS &L, const RHS &R) {
2094 return BinaryOp_match<LHS, RHS, Instruction::FMul, true>(L, R);
2095 }
2096
2097 template <typename Opnd_t> struct Signum_match {
2098 Opnd_t Val;
2099 Signum_match(const Opnd_t &V) : Val(V) {}
2100
2101 template <typename OpTy> bool match(OpTy *V) {
2102 unsigned TypeSize = V->getType()->getScalarSizeInBits();
2103 if (TypeSize == 0)
2104 return false;
2105
2106 unsigned ShiftWidth = TypeSize - 1;
2107 Value *OpL = nullptr, *OpR = nullptr;
2108
2109 // This is the representation of signum we match:
2110 //
2111 // signum(x) == (x >> 63) | (-x >>u 63)
2112 //
2113 // An i1 value is its own signum, so it's correct to match
2114 //
2115 // signum(x) == (x >> 0) | (-x >>u 0)
2116 //
2117 // for i1 values.
2118
2119 auto LHS = m_AShr(m_Value(OpL), m_SpecificInt(ShiftWidth));
2120 auto RHS = m_LShr(m_Neg(m_Value(OpR)), m_SpecificInt(ShiftWidth));
2121 auto Signum = m_Or(LHS, RHS);
2122
2123 return Signum.match(V) && OpL == OpR && Val.match(OpL);
2124 }
2125 };
2126
2127 /// Matches a signum pattern.
2128 ///
2129 /// signum(x) =
2130 /// x > 0 -> 1
2131 /// x == 0 -> 0
2132 /// x < 0 -> -1
2133 template <typename Val_t> inline Signum_match<Val_t> m_Signum(const Val_t &V) {
2134 return Signum_match<Val_t>(V);
2135 }
2136
2137 template <int Ind, typename Opnd_t> struct ExtractValue_match {
2138 Opnd_t Val;
2139 ExtractValue_match(const Opnd_t &V) : Val(V) {}
2140
2141 template <typename OpTy> bool match(OpTy *V) {
2142 if (auto *I = dyn_cast<ExtractValueInst>(V))
2143 return I->getNumIndices() == 1 && I->getIndices()[0] == Ind &&
2144 Val.match(I->getAggregateOperand());
2145 return false;
2146 }
2147 };
2148
2149 /// Match a single index ExtractValue instruction.
2150 /// For example m_ExtractValue<1>(...)
2151 template <int Ind, typename Val_t>
2152 inline ExtractValue_match<Ind, Val_t> m_ExtractValue(const Val_t &V) {
2153 return ExtractValue_match<Ind, Val_t>(V);
2154 }
2155
2156 /// Matches patterns for `vscale`. This can either be a call to `llvm.vscale` or
2157 /// the constant expression
2158 /// `ptrtoint(gep <vscale x 1 x i8>, <vscale x 1 x i8>* null, i32 1>`
2159 /// under the right conditions determined by DataLayout.
2160 struct VScaleVal_match {
2161 private:
2162 template <typename Base, typename Offset>
2163 inline BinaryOp_match<Base, Offset, Instruction::GetElementPtr>
2164 m_OffsetGep(const Base &B, const Offset &O) {
2165 return BinaryOp_match<Base, Offset, Instruction::GetElementPtr>(B, O);
2166 }
2167
2168 public:
2169 const DataLayout &DL;
2170 VScaleVal_match(const DataLayout &DL) : DL(DL) {}
2171
2172 template <typename ITy> bool match(ITy *V) {
2173 if (m_Intrinsic<Intrinsic::vscale>().match(V))
2174 return true;
2175
2176 if (m_PtrToInt(m_OffsetGep(m_Zero(), m_SpecificInt(1))).match(V)) {
2177 Type *PtrTy = cast<Operator>(V)->getOperand(0)->getType();
2178 auto *DerefTy = PtrTy->getPointerElementType();
2179 if (isa<ScalableVectorType>(DerefTy) &&
2180 DL.getTypeAllocSizeInBits(DerefTy).getKnownMinSize() == 8)
2181 return true;
2182 }
2183
2184 return false;
2185 }
2186 };
2187
2188 inline VScaleVal_match m_VScale(const DataLayout &DL) {
2189 return VScaleVal_match(DL);
2190 }
2191
2192 } // end namespace PatternMatch
2193 } // end namespace llvm
2194
2195 #endif // LLVM_IR_PATTERNMATCH_H
2196