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
46namespace llvm {
47namespace PatternMatch {
48
49template <typename Val, typename Pattern> bool match(Val *V, const Pattern &P) {
50 return const_cast<Pattern &>(P).match(V);
51}
52
53template <typename Pattern> bool match(ArrayRef<int> Mask, const Pattern &P) {
54 return const_cast<Pattern &>(P).match(Mask);
55}
56
57template <typename SubPattern_t> struct OneUse_match {
58 SubPattern_t SubPattern;
59
60 OneUse_match(const SubPattern_t &SP) : SubPattern(SP) {}
61
62 template <typename OpTy> bool match(OpTy *V) {
63 return V->hasOneUse() && SubPattern.match(V);
64 }
65};
66
67template <typename T> inline OneUse_match<T> m_OneUse(const T &SubPattern) {
68 return SubPattern;
69}
70
71template <typename Class> struct class_match {
72 template <typename ITy> bool match(ITy *V) { return isa<Class>(V); }
73};
74
75/// Match an arbitrary value and ignore it.
76inline class_match<Value> m_Value() { return class_match<Value>(); }
77
78/// Match an arbitrary unary operation and ignore it.
79inline class_match<UnaryOperator> m_UnOp() {
80 return class_match<UnaryOperator>();
81}
82
83/// Match an arbitrary binary operation and ignore it.
84inline class_match<BinaryOperator> m_BinOp() {
85 return class_match<BinaryOperator>();
86}
87
88/// Matches any compare instruction and ignore it.
89inline class_match<CmpInst> m_Cmp() { return class_match<CmpInst>(); }
90
91struct undef_match {
92 static bool check(const Value *V) {
93 if (isa<UndefValue>(Val: V))
94 return true;
95
96 const auto *CA = dyn_cast<ConstantAggregate>(Val: V);
97 if (!CA)
98 return false;
99
100 SmallPtrSet<const ConstantAggregate *, 8> Seen;
101 SmallVector<const ConstantAggregate *, 8> Worklist;
102
103 // Either UndefValue, PoisonValue, or an aggregate that only contains
104 // these is accepted by matcher.
105 // CheckValue returns false if CA cannot satisfy this constraint.
106 auto CheckValue = [&](const ConstantAggregate *CA) {
107 for (const Value *Op : CA->operand_values()) {
108 if (isa<UndefValue>(Val: Op))
109 continue;
110
111 const auto *CA = dyn_cast<ConstantAggregate>(Val: Op);
112 if (!CA)
113 return false;
114 if (Seen.insert(Ptr: CA).second)
115 Worklist.emplace_back(Args&: CA);
116 }
117
118 return true;
119 };
120
121 if (!CheckValue(CA))
122 return false;
123
124 while (!Worklist.empty()) {
125 if (!CheckValue(Worklist.pop_back_val()))
126 return false;
127 }
128 return true;
129 }
130 template <typename ITy> bool match(ITy *V) { return check(V); }
131};
132
133/// Match an arbitrary undef constant. This matches poison as well.
134/// If this is an aggregate and contains a non-aggregate element that is
135/// neither undef nor poison, the aggregate is not matched.
136inline auto m_Undef() { return undef_match(); }
137
138/// Match an arbitrary poison constant.
139inline class_match<PoisonValue> m_Poison() {
140 return class_match<PoisonValue>();
141}
142
143/// Match an arbitrary Constant and ignore it.
144inline class_match<Constant> m_Constant() { return class_match<Constant>(); }
145
146/// Match an arbitrary ConstantInt and ignore it.
147inline class_match<ConstantInt> m_ConstantInt() {
148 return class_match<ConstantInt>();
149}
150
151/// Match an arbitrary ConstantFP and ignore it.
152inline class_match<ConstantFP> m_ConstantFP() {
153 return class_match<ConstantFP>();
154}
155
156struct constantexpr_match {
157 template <typename ITy> bool match(ITy *V) {
158 auto *C = dyn_cast<Constant>(V);
159 return C && (isa<ConstantExpr>(C) || C->containsConstantExpression());
160 }
161};
162
163/// Match a constant expression or a constant that contains a constant
164/// expression.
165inline constantexpr_match m_ConstantExpr() { return constantexpr_match(); }
166
167/// Match an arbitrary basic block value and ignore it.
168inline class_match<BasicBlock> m_BasicBlock() {
169 return class_match<BasicBlock>();
170}
171
172/// Inverting matcher
173template <typename Ty> struct match_unless {
174 Ty M;
175
176 match_unless(const Ty &Matcher) : M(Matcher) {}
177
178 template <typename ITy> bool match(ITy *V) { return !M.match(V); }
179};
180
181/// Match if the inner matcher does *NOT* match.
182template <typename Ty> inline match_unless<Ty> m_Unless(const Ty &M) {
183 return match_unless<Ty>(M);
184}
185
186/// Matching combinators
187template <typename LTy, typename RTy> struct match_combine_or {
188 LTy L;
189 RTy R;
190
191 match_combine_or(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
192
193 template <typename ITy> bool match(ITy *V) {
194 if (L.match(V))
195 return true;
196 if (R.match(V))
197 return true;
198 return false;
199 }
200};
201
202template <typename LTy, typename RTy> struct match_combine_and {
203 LTy L;
204 RTy R;
205
206 match_combine_and(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
207
208 template <typename ITy> bool match(ITy *V) {
209 if (L.match(V))
210 if (R.match(V))
211 return true;
212 return false;
213 }
214};
215
216/// Combine two pattern matchers matching L || R
217template <typename LTy, typename RTy>
218inline match_combine_or<LTy, RTy> m_CombineOr(const LTy &L, const RTy &R) {
219 return match_combine_or<LTy, RTy>(L, R);
220}
221
222/// Combine two pattern matchers matching L && R
223template <typename LTy, typename RTy>
224inline match_combine_and<LTy, RTy> m_CombineAnd(const LTy &L, const RTy &R) {
225 return match_combine_and<LTy, RTy>(L, R);
226}
227
228struct apint_match {
229 const APInt *&Res;
230 bool AllowUndef;
231
232 apint_match(const APInt *&Res, bool AllowUndef)
233 : Res(Res), AllowUndef(AllowUndef) {}
234
235 template <typename ITy> bool match(ITy *V) {
236 if (auto *CI = dyn_cast<ConstantInt>(V)) {
237 Res = &CI->getValue();
238 return true;
239 }
240 if (V->getType()->isVectorTy())
241 if (const auto *C = dyn_cast<Constant>(V))
242 if (auto *CI =
243 dyn_cast_or_null<ConstantInt>(C->getSplatValue(AllowUndef))) {
244 Res = &CI->getValue();
245 return true;
246 }
247 return false;
248 }
249};
250// Either constexpr if or renaming ConstantFP::getValueAPF to
251// ConstantFP::getValue is needed to do it via single template
252// function for both apint/apfloat.
253struct apfloat_match {
254 const APFloat *&Res;
255 bool AllowUndef;
256
257 apfloat_match(const APFloat *&Res, bool AllowUndef)
258 : Res(Res), AllowUndef(AllowUndef) {}
259
260 template <typename ITy> bool match(ITy *V) {
261 if (auto *CI = dyn_cast<ConstantFP>(V)) {
262 Res = &CI->getValueAPF();
263 return true;
264 }
265 if (V->getType()->isVectorTy())
266 if (const auto *C = dyn_cast<Constant>(V))
267 if (auto *CI =
268 dyn_cast_or_null<ConstantFP>(C->getSplatValue(AllowUndef))) {
269 Res = &CI->getValueAPF();
270 return true;
271 }
272 return false;
273 }
274};
275
276/// Match a ConstantInt or splatted ConstantVector, binding the
277/// specified pointer to the contained APInt.
278inline apint_match m_APInt(const APInt *&Res) {
279 // Forbid undefs by default to maintain previous behavior.
280 return apint_match(Res, /* AllowUndef */ false);
281}
282
283/// Match APInt while allowing undefs in splat vector constants.
284inline apint_match m_APIntAllowUndef(const APInt *&Res) {
285 return apint_match(Res, /* AllowUndef */ true);
286}
287
288/// Match APInt while forbidding undefs in splat vector constants.
289inline apint_match m_APIntForbidUndef(const APInt *&Res) {
290 return apint_match(Res, /* AllowUndef */ false);
291}
292
293/// Match a ConstantFP or splatted ConstantVector, binding the
294/// specified pointer to the contained APFloat.
295inline apfloat_match m_APFloat(const APFloat *&Res) {
296 // Forbid undefs by default to maintain previous behavior.
297 return apfloat_match(Res, /* AllowUndef */ false);
298}
299
300/// Match APFloat while allowing undefs in splat vector constants.
301inline apfloat_match m_APFloatAllowUndef(const APFloat *&Res) {
302 return apfloat_match(Res, /* AllowUndef */ true);
303}
304
305/// Match APFloat while forbidding undefs in splat vector constants.
306inline apfloat_match m_APFloatForbidUndef(const APFloat *&Res) {
307 return apfloat_match(Res, /* AllowUndef */ false);
308}
309
310template <int64_t Val> struct constantint_match {
311 template <typename ITy> bool match(ITy *V) {
312 if (const auto *CI = dyn_cast<ConstantInt>(V)) {
313 const APInt &CIV = CI->getValue();
314 if (Val >= 0)
315 return CIV == static_cast<uint64_t>(Val);
316 // If Val is negative, and CI is shorter than it, truncate to the right
317 // number of bits. If it is larger, then we have to sign extend. Just
318 // compare their negated values.
319 return -CIV == -Val;
320 }
321 return false;
322 }
323};
324
325/// Match a ConstantInt with a specific value.
326template <int64_t Val> inline constantint_match<Val> m_ConstantInt() {
327 return constantint_match<Val>();
328}
329
330/// This helper class is used to match constant scalars, vector splats,
331/// and fixed width vectors that satisfy a specified predicate.
332/// For fixed width vector constants, undefined elements are ignored.
333template <typename Predicate, typename ConstantVal>
334struct cstval_pred_ty : public Predicate {
335 template <typename ITy> bool match(ITy *V) {
336 if (const auto *CV = dyn_cast<ConstantVal>(V))
337 return this->isValue(CV->getValue());
338 if (const auto *VTy = dyn_cast<VectorType>(V->getType())) {
339 if (const auto *C = dyn_cast<Constant>(V)) {
340 if (const auto *CV = dyn_cast_or_null<ConstantVal>(C->getSplatValue()))
341 return this->isValue(CV->getValue());
342
343 // Number of elements of a scalable vector unknown at compile time
344 auto *FVTy = dyn_cast<FixedVectorType>(VTy);
345 if (!FVTy)
346 return false;
347
348 // Non-splat vector constant: check each element for a match.
349 unsigned NumElts = FVTy->getNumElements();
350 assert(NumElts != 0 && "Constant vector with no elements?");
351 bool HasNonUndefElements = false;
352 for (unsigned i = 0; i != NumElts; ++i) {
353 Constant *Elt = C->getAggregateElement(i);
354 if (!Elt)
355 return false;
356 if (isa<UndefValue>(Val: Elt))
357 continue;
358 auto *CV = dyn_cast<ConstantVal>(Elt);
359 if (!CV || !this->isValue(CV->getValue()))
360 return false;
361 HasNonUndefElements = true;
362 }
363 return HasNonUndefElements;
364 }
365 }
366 return false;
367 }
368};
369
370/// specialization of cstval_pred_ty for ConstantInt
371template <typename Predicate>
372using cst_pred_ty = cstval_pred_ty<Predicate, ConstantInt>;
373
374/// specialization of cstval_pred_ty for ConstantFP
375template <typename Predicate>
376using cstfp_pred_ty = cstval_pred_ty<Predicate, ConstantFP>;
377
378/// This helper class is used to match scalar and vector constants that
379/// satisfy a specified predicate, and bind them to an APInt.
380template <typename Predicate> struct api_pred_ty : public Predicate {
381 const APInt *&Res;
382
383 api_pred_ty(const APInt *&R) : Res(R) {}
384
385 template <typename ITy> bool match(ITy *V) {
386 if (const auto *CI = dyn_cast<ConstantInt>(V))
387 if (this->isValue(CI->getValue())) {
388 Res = &CI->getValue();
389 return true;
390 }
391 if (V->getType()->isVectorTy())
392 if (const auto *C = dyn_cast<Constant>(V))
393 if (auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue()))
394 if (this->isValue(CI->getValue())) {
395 Res = &CI->getValue();
396 return true;
397 }
398
399 return false;
400 }
401};
402
403/// This helper class is used to match scalar and vector constants that
404/// satisfy a specified predicate, and bind them to an APFloat.
405/// Undefs are allowed in splat vector constants.
406template <typename Predicate> struct apf_pred_ty : public Predicate {
407 const APFloat *&Res;
408
409 apf_pred_ty(const APFloat *&R) : Res(R) {}
410
411 template <typename ITy> bool match(ITy *V) {
412 if (const auto *CI = dyn_cast<ConstantFP>(V))
413 if (this->isValue(CI->getValue())) {
414 Res = &CI->getValue();
415 return true;
416 }
417 if (V->getType()->isVectorTy())
418 if (const auto *C = dyn_cast<Constant>(V))
419 if (auto *CI = dyn_cast_or_null<ConstantFP>(
420 C->getSplatValue(/* AllowUndef */ true)))
421 if (this->isValue(CI->getValue())) {
422 Res = &CI->getValue();
423 return true;
424 }
425
426 return false;
427 }
428};
429
430///////////////////////////////////////////////////////////////////////////////
431//
432// Encapsulate constant value queries for use in templated predicate matchers.
433// This allows checking if constants match using compound predicates and works
434// with vector constants, possibly with relaxed constraints. For example, ignore
435// undef values.
436//
437///////////////////////////////////////////////////////////////////////////////
438
439struct is_any_apint {
440 bool isValue(const APInt &C) { return true; }
441};
442/// Match an integer or vector with any integral constant.
443/// For vectors, this includes constants with undefined elements.
444inline cst_pred_ty<is_any_apint> m_AnyIntegralConstant() {
445 return cst_pred_ty<is_any_apint>();
446}
447
448struct is_shifted_mask {
449 bool isValue(const APInt &C) { return C.isShiftedMask(); }
450};
451
452inline cst_pred_ty<is_shifted_mask> m_ShiftedMask() {
453 return cst_pred_ty<is_shifted_mask>();
454}
455
456struct is_all_ones {
457 bool isValue(const APInt &C) { return C.isAllOnes(); }
458};
459/// Match an integer or vector with all bits set.
460/// For vectors, this includes constants with undefined elements.
461inline cst_pred_ty<is_all_ones> m_AllOnes() {
462 return cst_pred_ty<is_all_ones>();
463}
464
465struct is_maxsignedvalue {
466 bool isValue(const APInt &C) { return C.isMaxSignedValue(); }
467};
468/// Match an integer or vector with values having all bits except for the high
469/// bit set (0x7f...).
470/// For vectors, this includes constants with undefined elements.
471inline cst_pred_ty<is_maxsignedvalue> m_MaxSignedValue() {
472 return cst_pred_ty<is_maxsignedvalue>();
473}
474inline api_pred_ty<is_maxsignedvalue> m_MaxSignedValue(const APInt *&V) {
475 return V;
476}
477
478struct is_negative {
479 bool isValue(const APInt &C) { return C.isNegative(); }
480};
481/// Match an integer or vector of negative values.
482/// For vectors, this includes constants with undefined elements.
483inline cst_pred_ty<is_negative> m_Negative() {
484 return cst_pred_ty<is_negative>();
485}
486inline api_pred_ty<is_negative> m_Negative(const APInt *&V) { return V; }
487
488struct is_nonnegative {
489 bool isValue(const APInt &C) { return C.isNonNegative(); }
490};
491/// Match an integer or vector of non-negative values.
492/// For vectors, this includes constants with undefined elements.
493inline cst_pred_ty<is_nonnegative> m_NonNegative() {
494 return cst_pred_ty<is_nonnegative>();
495}
496inline api_pred_ty<is_nonnegative> m_NonNegative(const APInt *&V) { return V; }
497
498struct is_strictlypositive {
499 bool isValue(const APInt &C) { return C.isStrictlyPositive(); }
500};
501/// Match an integer or vector of strictly positive values.
502/// For vectors, this includes constants with undefined elements.
503inline cst_pred_ty<is_strictlypositive> m_StrictlyPositive() {
504 return cst_pred_ty<is_strictlypositive>();
505}
506inline api_pred_ty<is_strictlypositive> m_StrictlyPositive(const APInt *&V) {
507 return V;
508}
509
510struct is_nonpositive {
511 bool isValue(const APInt &C) { return C.isNonPositive(); }
512};
513/// Match an integer or vector of non-positive values.
514/// For vectors, this includes constants with undefined elements.
515inline cst_pred_ty<is_nonpositive> m_NonPositive() {
516 return cst_pred_ty<is_nonpositive>();
517}
518inline api_pred_ty<is_nonpositive> m_NonPositive(const APInt *&V) { return V; }
519
520struct is_one {
521 bool isValue(const APInt &C) { return C.isOne(); }
522};
523/// Match an integer 1 or a vector with all elements equal to 1.
524/// For vectors, this includes constants with undefined elements.
525inline cst_pred_ty<is_one> m_One() { return cst_pred_ty<is_one>(); }
526
527struct is_zero_int {
528 bool isValue(const APInt &C) { return C.isZero(); }
529};
530/// Match an integer 0 or a vector with all elements equal to 0.
531/// For vectors, this includes constants with undefined elements.
532inline cst_pred_ty<is_zero_int> m_ZeroInt() {
533 return cst_pred_ty<is_zero_int>();
534}
535
536struct is_zero {
537 template <typename ITy> bool match(ITy *V) {
538 auto *C = dyn_cast<Constant>(V);
539 // FIXME: this should be able to do something for scalable vectors
540 return C && (C->isNullValue() || cst_pred_ty<is_zero_int>().match(C));
541 }
542};
543/// Match any null constant or a vector with all elements equal to 0.
544/// For vectors, this includes constants with undefined elements.
545inline is_zero m_Zero() { return is_zero(); }
546
547struct is_power2 {
548 bool isValue(const APInt &C) { return C.isPowerOf2(); }
549};
550/// Match an integer or vector power-of-2.
551/// For vectors, this includes constants with undefined elements.
552inline cst_pred_ty<is_power2> m_Power2() { return cst_pred_ty<is_power2>(); }
553inline api_pred_ty<is_power2> m_Power2(const APInt *&V) { return V; }
554
555struct is_negated_power2 {
556 bool isValue(const APInt &C) { return C.isNegatedPowerOf2(); }
557};
558/// Match a integer or vector negated power-of-2.
559/// For vectors, this includes constants with undefined elements.
560inline cst_pred_ty<is_negated_power2> m_NegatedPower2() {
561 return cst_pred_ty<is_negated_power2>();
562}
563inline api_pred_ty<is_negated_power2> m_NegatedPower2(const APInt *&V) {
564 return V;
565}
566
567struct is_power2_or_zero {
568 bool isValue(const APInt &C) { return !C || C.isPowerOf2(); }
569};
570/// Match an integer or vector of 0 or power-of-2 values.
571/// For vectors, this includes constants with undefined elements.
572inline cst_pred_ty<is_power2_or_zero> m_Power2OrZero() {
573 return cst_pred_ty<is_power2_or_zero>();
574}
575inline api_pred_ty<is_power2_or_zero> m_Power2OrZero(const APInt *&V) {
576 return V;
577}
578
579struct is_sign_mask {
580 bool isValue(const APInt &C) { return C.isSignMask(); }
581};
582/// Match an integer or vector with only the sign bit(s) set.
583/// For vectors, this includes constants with undefined elements.
584inline cst_pred_ty<is_sign_mask> m_SignMask() {
585 return cst_pred_ty<is_sign_mask>();
586}
587
588struct is_lowbit_mask {
589 bool isValue(const APInt &C) { return C.isMask(); }
590};
591/// Match an integer or vector with only the low bit(s) set.
592/// For vectors, this includes constants with undefined elements.
593inline cst_pred_ty<is_lowbit_mask> m_LowBitMask() {
594 return cst_pred_ty<is_lowbit_mask>();
595}
596inline api_pred_ty<is_lowbit_mask> m_LowBitMask(const APInt *&V) { return V; }
597
598struct icmp_pred_with_threshold {
599 ICmpInst::Predicate Pred;
600 const APInt *Thr;
601 bool isValue(const APInt &C) { return ICmpInst::compare(LHS: C, RHS: *Thr, Pred); }
602};
603/// Match an integer or vector with every element comparing 'pred' (eg/ne/...)
604/// to Threshold. For vectors, this includes constants with undefined elements.
605inline cst_pred_ty<icmp_pred_with_threshold>
606m_SpecificInt_ICMP(ICmpInst::Predicate Predicate, const APInt &Threshold) {
607 cst_pred_ty<icmp_pred_with_threshold> P;
608 P.Pred = Predicate;
609 P.Thr = &Threshold;
610 return P;
611}
612
613struct is_nan {
614 bool isValue(const APFloat &C) { return C.isNaN(); }
615};
616/// Match an arbitrary NaN constant. This includes quiet and signalling nans.
617/// For vectors, this includes constants with undefined elements.
618inline cstfp_pred_ty<is_nan> m_NaN() { return cstfp_pred_ty<is_nan>(); }
619
620struct is_nonnan {
621 bool isValue(const APFloat &C) { return !C.isNaN(); }
622};
623/// Match a non-NaN FP constant.
624/// For vectors, this includes constants with undefined elements.
625inline cstfp_pred_ty<is_nonnan> m_NonNaN() {
626 return cstfp_pred_ty<is_nonnan>();
627}
628
629struct is_inf {
630 bool isValue(const APFloat &C) { return C.isInfinity(); }
631};
632/// Match a positive or negative infinity FP constant.
633/// For vectors, this includes constants with undefined elements.
634inline cstfp_pred_ty<is_inf> m_Inf() { return cstfp_pred_ty<is_inf>(); }
635
636struct is_noninf {
637 bool isValue(const APFloat &C) { return !C.isInfinity(); }
638};
639/// Match a non-infinity FP constant, i.e. finite or NaN.
640/// For vectors, this includes constants with undefined elements.
641inline cstfp_pred_ty<is_noninf> m_NonInf() {
642 return cstfp_pred_ty<is_noninf>();
643}
644
645struct is_finite {
646 bool isValue(const APFloat &C) { return C.isFinite(); }
647};
648/// Match a finite FP constant, i.e. not infinity or NaN.
649/// For vectors, this includes constants with undefined elements.
650inline cstfp_pred_ty<is_finite> m_Finite() {
651 return cstfp_pred_ty<is_finite>();
652}
653inline apf_pred_ty<is_finite> m_Finite(const APFloat *&V) { return V; }
654
655struct is_finitenonzero {
656 bool isValue(const APFloat &C) { return C.isFiniteNonZero(); }
657};
658/// Match a finite non-zero FP constant.
659/// For vectors, this includes constants with undefined elements.
660inline cstfp_pred_ty<is_finitenonzero> m_FiniteNonZero() {
661 return cstfp_pred_ty<is_finitenonzero>();
662}
663inline apf_pred_ty<is_finitenonzero> m_FiniteNonZero(const APFloat *&V) {
664 return V;
665}
666
667struct is_any_zero_fp {
668 bool isValue(const APFloat &C) { return C.isZero(); }
669};
670/// Match a floating-point negative zero or positive zero.
671/// For vectors, this includes constants with undefined elements.
672inline cstfp_pred_ty<is_any_zero_fp> m_AnyZeroFP() {
673 return cstfp_pred_ty<is_any_zero_fp>();
674}
675
676struct is_pos_zero_fp {
677 bool isValue(const APFloat &C) { return C.isPosZero(); }
678};
679/// Match a floating-point positive zero.
680/// For vectors, this includes constants with undefined elements.
681inline cstfp_pred_ty<is_pos_zero_fp> m_PosZeroFP() {
682 return cstfp_pred_ty<is_pos_zero_fp>();
683}
684
685struct is_neg_zero_fp {
686 bool isValue(const APFloat &C) { return C.isNegZero(); }
687};
688/// Match a floating-point negative zero.
689/// For vectors, this includes constants with undefined elements.
690inline cstfp_pred_ty<is_neg_zero_fp> m_NegZeroFP() {
691 return cstfp_pred_ty<is_neg_zero_fp>();
692}
693
694struct is_non_zero_fp {
695 bool isValue(const APFloat &C) { return C.isNonZero(); }
696};
697/// Match a floating-point non-zero.
698/// For vectors, this includes constants with undefined elements.
699inline cstfp_pred_ty<is_non_zero_fp> m_NonZeroFP() {
700 return cstfp_pred_ty<is_non_zero_fp>();
701}
702
703///////////////////////////////////////////////////////////////////////////////
704
705template <typename Class> struct bind_ty {
706 Class *&VR;
707
708 bind_ty(Class *&V) : VR(V) {}
709
710 template <typename ITy> bool match(ITy *V) {
711 if (auto *CV = dyn_cast<Class>(V)) {
712 VR = CV;
713 return true;
714 }
715 return false;
716 }
717};
718
719/// Match a value, capturing it if we match.
720inline bind_ty<Value> m_Value(Value *&V) { return V; }
721inline bind_ty<const Value> m_Value(const Value *&V) { return V; }
722
723/// Match an instruction, capturing it if we match.
724inline bind_ty<Instruction> m_Instruction(Instruction *&I) { return I; }
725/// Match a unary operator, capturing it if we match.
726inline bind_ty<UnaryOperator> m_UnOp(UnaryOperator *&I) { return I; }
727/// Match a binary operator, capturing it if we match.
728inline bind_ty<BinaryOperator> m_BinOp(BinaryOperator *&I) { return I; }
729/// Match a with overflow intrinsic, capturing it if we match.
730inline bind_ty<WithOverflowInst> m_WithOverflowInst(WithOverflowInst *&I) {
731 return I;
732}
733inline bind_ty<const WithOverflowInst>
734m_WithOverflowInst(const WithOverflowInst *&I) {
735 return I;
736}
737
738/// Match a Constant, capturing the value if we match.
739inline bind_ty<Constant> m_Constant(Constant *&C) { return C; }
740
741/// Match a ConstantInt, capturing the value if we match.
742inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
743
744/// Match a ConstantFP, capturing the value if we match.
745inline bind_ty<ConstantFP> m_ConstantFP(ConstantFP *&C) { return C; }
746
747/// Match a ConstantExpr, capturing the value if we match.
748inline bind_ty<ConstantExpr> m_ConstantExpr(ConstantExpr *&C) { return C; }
749
750/// Match a basic block value, capturing it if we match.
751inline bind_ty<BasicBlock> m_BasicBlock(BasicBlock *&V) { return V; }
752inline bind_ty<const BasicBlock> m_BasicBlock(const BasicBlock *&V) {
753 return V;
754}
755
756/// Match an arbitrary immediate Constant and ignore it.
757inline match_combine_and<class_match<Constant>,
758 match_unless<constantexpr_match>>
759m_ImmConstant() {
760 return m_CombineAnd(L: m_Constant(), R: m_Unless(M: m_ConstantExpr()));
761}
762
763/// Match an immediate Constant, capturing the value if we match.
764inline match_combine_and<bind_ty<Constant>,
765 match_unless<constantexpr_match>>
766m_ImmConstant(Constant *&C) {
767 return m_CombineAnd(L: m_Constant(C), R: m_Unless(M: m_ConstantExpr()));
768}
769
770/// Match a specified Value*.
771struct specificval_ty {
772 const Value *Val;
773
774 specificval_ty(const Value *V) : Val(V) {}
775
776 template <typename ITy> bool match(ITy *V) { return V == Val; }
777};
778
779/// Match if we have a specific specified value.
780inline specificval_ty m_Specific(const Value *V) { return V; }
781
782/// Stores a reference to the Value *, not the Value * itself,
783/// thus can be used in commutative matchers.
784template <typename Class> struct deferredval_ty {
785 Class *const &Val;
786
787 deferredval_ty(Class *const &V) : Val(V) {}
788
789 template <typename ITy> bool match(ITy *const V) { return V == Val; }
790};
791
792/// Like m_Specific(), but works if the specific value to match is determined
793/// as part of the same match() expression. For example:
794/// m_Add(m_Value(X), m_Specific(X)) is incorrect, because m_Specific() will
795/// bind X before the pattern match starts.
796/// m_Add(m_Value(X), m_Deferred(X)) is correct, and will check against
797/// whichever value m_Value(X) populated.
798inline deferredval_ty<Value> m_Deferred(Value *const &V) { return V; }
799inline deferredval_ty<const Value> m_Deferred(const Value *const &V) {
800 return V;
801}
802
803/// Match a specified floating point value or vector of all elements of
804/// that value.
805struct specific_fpval {
806 double Val;
807
808 specific_fpval(double V) : Val(V) {}
809
810 template <typename ITy> bool match(ITy *V) {
811 if (const auto *CFP = dyn_cast<ConstantFP>(V))
812 return CFP->isExactlyValue(Val);
813 if (V->getType()->isVectorTy())
814 if (const auto *C = dyn_cast<Constant>(V))
815 if (auto *CFP = dyn_cast_or_null<ConstantFP>(C->getSplatValue()))
816 return CFP->isExactlyValue(Val);
817 return false;
818 }
819};
820
821/// Match a specific floating point value or vector with all elements
822/// equal to the value.
823inline specific_fpval m_SpecificFP(double V) { return specific_fpval(V); }
824
825/// Match a float 1.0 or vector with all elements equal to 1.0.
826inline specific_fpval m_FPOne() { return m_SpecificFP(V: 1.0); }
827
828struct bind_const_intval_ty {
829 uint64_t &VR;
830
831 bind_const_intval_ty(uint64_t &V) : VR(V) {}
832
833 template <typename ITy> bool match(ITy *V) {
834 if (const auto *CV = dyn_cast<ConstantInt>(V))
835 if (CV->getValue().ule(UINT64_MAX)) {
836 VR = CV->getZExtValue();
837 return true;
838 }
839 return false;
840 }
841};
842
843/// Match a specified integer value or vector of all elements of that
844/// value.
845template <bool AllowUndefs> struct specific_intval {
846 APInt Val;
847
848 specific_intval(APInt V) : Val(std::move(V)) {}
849
850 template <typename ITy> bool match(ITy *V) {
851 const auto *CI = dyn_cast<ConstantInt>(V);
852 if (!CI && V->getType()->isVectorTy())
853 if (const auto *C = dyn_cast<Constant>(V))
854 CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue(AllowUndefs));
855
856 return CI && APInt::isSameValue(I1: CI->getValue(), I2: Val);
857 }
858};
859
860/// Match a specific integer value or vector with all elements equal to
861/// the value.
862inline specific_intval<false> m_SpecificInt(APInt V) {
863 return specific_intval<false>(std::move(V));
864}
865
866inline specific_intval<false> m_SpecificInt(uint64_t V) {
867 return m_SpecificInt(V: APInt(64, V));
868}
869
870inline specific_intval<true> m_SpecificIntAllowUndef(APInt V) {
871 return specific_intval<true>(std::move(V));
872}
873
874inline specific_intval<true> m_SpecificIntAllowUndef(uint64_t V) {
875 return m_SpecificIntAllowUndef(V: APInt(64, V));
876}
877
878/// Match a ConstantInt and bind to its value. This does not match
879/// ConstantInts wider than 64-bits.
880inline bind_const_intval_ty m_ConstantInt(uint64_t &V) { return V; }
881
882/// Match a specified basic block value.
883struct specific_bbval {
884 BasicBlock *Val;
885
886 specific_bbval(BasicBlock *Val) : Val(Val) {}
887
888 template <typename ITy> bool match(ITy *V) {
889 const auto *BB = dyn_cast<BasicBlock>(V);
890 return BB && BB == Val;
891 }
892};
893
894/// Match a specific basic block value.
895inline specific_bbval m_SpecificBB(BasicBlock *BB) {
896 return specific_bbval(BB);
897}
898
899/// A commutative-friendly version of m_Specific().
900inline deferredval_ty<BasicBlock> m_Deferred(BasicBlock *const &BB) {
901 return BB;
902}
903inline deferredval_ty<const BasicBlock>
904m_Deferred(const BasicBlock *const &BB) {
905 return BB;
906}
907
908//===----------------------------------------------------------------------===//
909// Matcher for any binary operator.
910//
911template <typename LHS_t, typename RHS_t, bool Commutable = false>
912struct AnyBinaryOp_match {
913 LHS_t L;
914 RHS_t R;
915
916 // The evaluation order is always stable, regardless of Commutability.
917 // The LHS is always matched first.
918 AnyBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
919
920 template <typename OpTy> bool match(OpTy *V) {
921 if (auto *I = dyn_cast<BinaryOperator>(V))
922 return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
923 (Commutable && L.match(I->getOperand(1)) &&
924 R.match(I->getOperand(0)));
925 return false;
926 }
927};
928
929template <typename LHS, typename RHS>
930inline AnyBinaryOp_match<LHS, RHS> m_BinOp(const LHS &L, const RHS &R) {
931 return AnyBinaryOp_match<LHS, RHS>(L, R);
932}
933
934//===----------------------------------------------------------------------===//
935// Matcher for any unary operator.
936// TODO fuse unary, binary matcher into n-ary matcher
937//
938template <typename OP_t> struct AnyUnaryOp_match {
939 OP_t X;
940
941 AnyUnaryOp_match(const OP_t &X) : X(X) {}
942
943 template <typename OpTy> bool match(OpTy *V) {
944 if (auto *I = dyn_cast<UnaryOperator>(V))
945 return X.match(I->getOperand(0));
946 return false;
947 }
948};
949
950template <typename OP_t> inline AnyUnaryOp_match<OP_t> m_UnOp(const OP_t &X) {
951 return AnyUnaryOp_match<OP_t>(X);
952}
953
954//===----------------------------------------------------------------------===//
955// Matchers for specific binary operators.
956//
957
958template <typename LHS_t, typename RHS_t, unsigned Opcode,
959 bool Commutable = false>
960struct BinaryOp_match {
961 LHS_t L;
962 RHS_t R;
963
964 // The evaluation order is always stable, regardless of Commutability.
965 // The LHS is always matched first.
966 BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
967
968 template <typename OpTy> inline bool match(unsigned Opc, OpTy *V) {
969 if (V->getValueID() == Value::InstructionVal + Opc) {
970 auto *I = cast<BinaryOperator>(V);
971 return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
972 (Commutable && L.match(I->getOperand(1)) &&
973 R.match(I->getOperand(0)));
974 }
975 return false;
976 }
977
978 template <typename OpTy> bool match(OpTy *V) { return match(Opcode, V); }
979};
980
981template <typename LHS, typename RHS>
982inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L,
983 const RHS &R) {
984 return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);
985}
986
987template <typename LHS, typename RHS>
988inline BinaryOp_match<LHS, RHS, Instruction::FAdd> m_FAdd(const LHS &L,
989 const RHS &R) {
990 return BinaryOp_match<LHS, RHS, Instruction::FAdd>(L, R);
991}
992
993template <typename LHS, typename RHS>
994inline BinaryOp_match<LHS, RHS, Instruction::Sub> m_Sub(const LHS &L,
995 const RHS &R) {
996 return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R);
997}
998
999template <typename LHS, typename RHS>
1000inline BinaryOp_match<LHS, RHS, Instruction::FSub> m_FSub(const LHS &L,
1001 const RHS &R) {
1002 return BinaryOp_match<LHS, RHS, Instruction::FSub>(L, R);
1003}
1004
1005template <typename Op_t> struct FNeg_match {
1006 Op_t X;
1007
1008 FNeg_match(const Op_t &Op) : X(Op) {}
1009 template <typename OpTy> bool match(OpTy *V) {
1010 auto *FPMO = dyn_cast<FPMathOperator>(V);
1011 if (!FPMO)
1012 return false;
1013
1014 if (FPMO->getOpcode() == Instruction::FNeg)
1015 return X.match(FPMO->getOperand(0));
1016
1017 if (FPMO->getOpcode() == Instruction::FSub) {
1018 if (FPMO->hasNoSignedZeros()) {
1019 // With 'nsz', any zero goes.
1020 if (!cstfp_pred_ty<is_any_zero_fp>().match(FPMO->getOperand(0)))
1021 return false;
1022 } else {
1023 // Without 'nsz', we need fsub -0.0, X exactly.
1024 if (!cstfp_pred_ty<is_neg_zero_fp>().match(FPMO->getOperand(0)))
1025 return false;
1026 }
1027
1028 return X.match(FPMO->getOperand(1));
1029 }
1030
1031 return false;
1032 }
1033};
1034
1035/// Match 'fneg X' as 'fsub -0.0, X'.
1036template <typename OpTy> inline FNeg_match<OpTy> m_FNeg(const OpTy &X) {
1037 return FNeg_match<OpTy>(X);
1038}
1039
1040/// Match 'fneg X' as 'fsub +-0.0, X'.
1041template <typename RHS>
1042inline BinaryOp_match<cstfp_pred_ty<is_any_zero_fp>, RHS, Instruction::FSub>
1043m_FNegNSZ(const RHS &X) {
1044 return m_FSub(m_AnyZeroFP(), X);
1045}
1046
1047template <typename LHS, typename RHS>
1048inline BinaryOp_match<LHS, RHS, Instruction::Mul> m_Mul(const LHS &L,
1049 const RHS &R) {
1050 return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R);
1051}
1052
1053template <typename LHS, typename RHS>
1054inline BinaryOp_match<LHS, RHS, Instruction::FMul> m_FMul(const LHS &L,
1055 const RHS &R) {
1056 return BinaryOp_match<LHS, RHS, Instruction::FMul>(L, R);
1057}
1058
1059template <typename LHS, typename RHS>
1060inline BinaryOp_match<LHS, RHS, Instruction::UDiv> m_UDiv(const LHS &L,
1061 const RHS &R) {
1062 return BinaryOp_match<LHS, RHS, Instruction::UDiv>(L, R);
1063}
1064
1065template <typename LHS, typename RHS>
1066inline BinaryOp_match<LHS, RHS, Instruction::SDiv> m_SDiv(const LHS &L,
1067 const RHS &R) {
1068 return BinaryOp_match<LHS, RHS, Instruction::SDiv>(L, R);
1069}
1070
1071template <typename LHS, typename RHS>
1072inline BinaryOp_match<LHS, RHS, Instruction::FDiv> m_FDiv(const LHS &L,
1073 const RHS &R) {
1074 return BinaryOp_match<LHS, RHS, Instruction::FDiv>(L, R);
1075}
1076
1077template <typename LHS, typename RHS>
1078inline BinaryOp_match<LHS, RHS, Instruction::URem> m_URem(const LHS &L,
1079 const RHS &R) {
1080 return BinaryOp_match<LHS, RHS, Instruction::URem>(L, R);
1081}
1082
1083template <typename LHS, typename RHS>
1084inline BinaryOp_match<LHS, RHS, Instruction::SRem> m_SRem(const LHS &L,
1085 const RHS &R) {
1086 return BinaryOp_match<LHS, RHS, Instruction::SRem>(L, R);
1087}
1088
1089template <typename LHS, typename RHS>
1090inline BinaryOp_match<LHS, RHS, Instruction::FRem> m_FRem(const LHS &L,
1091 const RHS &R) {
1092 return BinaryOp_match<LHS, RHS, Instruction::FRem>(L, R);
1093}
1094
1095template <typename LHS, typename RHS>
1096inline BinaryOp_match<LHS, RHS, Instruction::And> m_And(const LHS &L,
1097 const RHS &R) {
1098 return BinaryOp_match<LHS, RHS, Instruction::And>(L, R);
1099}
1100
1101template <typename LHS, typename RHS>
1102inline BinaryOp_match<LHS, RHS, Instruction::Or> m_Or(const LHS &L,
1103 const RHS &R) {
1104 return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R);
1105}
1106
1107template <typename LHS, typename RHS>
1108inline BinaryOp_match<LHS, RHS, Instruction::Xor> m_Xor(const LHS &L,
1109 const RHS &R) {
1110 return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R);
1111}
1112
1113template <typename LHS, typename RHS>
1114inline BinaryOp_match<LHS, RHS, Instruction::Shl> m_Shl(const LHS &L,
1115 const RHS &R) {
1116 return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R);
1117}
1118
1119template <typename LHS, typename RHS>
1120inline BinaryOp_match<LHS, RHS, Instruction::LShr> m_LShr(const LHS &L,
1121 const RHS &R) {
1122 return BinaryOp_match<LHS, RHS, Instruction::LShr>(L, R);
1123}
1124
1125template <typename LHS, typename RHS>
1126inline BinaryOp_match<LHS, RHS, Instruction::AShr> m_AShr(const LHS &L,
1127 const RHS &R) {
1128 return BinaryOp_match<LHS, RHS, Instruction::AShr>(L, R);
1129}
1130
1131template <typename LHS_t, typename RHS_t, unsigned Opcode,
1132 unsigned WrapFlags = 0>
1133struct OverflowingBinaryOp_match {
1134 LHS_t L;
1135 RHS_t R;
1136
1137 OverflowingBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS)
1138 : L(LHS), R(RHS) {}
1139
1140 template <typename OpTy> bool match(OpTy *V) {
1141 if (auto *Op = dyn_cast<OverflowingBinaryOperator>(V)) {
1142 if (Op->getOpcode() != Opcode)
1143 return false;
1144 if ((WrapFlags & OverflowingBinaryOperator::NoUnsignedWrap) &&
1145 !Op->hasNoUnsignedWrap())
1146 return false;
1147 if ((WrapFlags & OverflowingBinaryOperator::NoSignedWrap) &&
1148 !Op->hasNoSignedWrap())
1149 return false;
1150 return L.match(Op->getOperand(0)) && R.match(Op->getOperand(1));
1151 }
1152 return false;
1153 }
1154};
1155
1156template <typename LHS, typename RHS>
1157inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
1158 OverflowingBinaryOperator::NoSignedWrap>
1159m_NSWAdd(const LHS &L, const RHS &R) {
1160 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
1161 OverflowingBinaryOperator::NoSignedWrap>(L,
1162 R);
1163}
1164template <typename LHS, typename RHS>
1165inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
1166 OverflowingBinaryOperator::NoSignedWrap>
1167m_NSWSub(const LHS &L, const RHS &R) {
1168 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
1169 OverflowingBinaryOperator::NoSignedWrap>(L,
1170 R);
1171}
1172template <typename LHS, typename RHS>
1173inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
1174 OverflowingBinaryOperator::NoSignedWrap>
1175m_NSWMul(const LHS &L, const RHS &R) {
1176 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
1177 OverflowingBinaryOperator::NoSignedWrap>(L,
1178 R);
1179}
1180template <typename LHS, typename RHS>
1181inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
1182 OverflowingBinaryOperator::NoSignedWrap>
1183m_NSWShl(const LHS &L, const RHS &R) {
1184 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
1185 OverflowingBinaryOperator::NoSignedWrap>(L,
1186 R);
1187}
1188
1189template <typename LHS, typename RHS>
1190inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
1191 OverflowingBinaryOperator::NoUnsignedWrap>
1192m_NUWAdd(const LHS &L, const RHS &R) {
1193 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
1194 OverflowingBinaryOperator::NoUnsignedWrap>(
1195 L, R);
1196}
1197template <typename LHS, typename RHS>
1198inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
1199 OverflowingBinaryOperator::NoUnsignedWrap>
1200m_NUWSub(const LHS &L, const RHS &R) {
1201 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
1202 OverflowingBinaryOperator::NoUnsignedWrap>(
1203 L, R);
1204}
1205template <typename LHS, typename RHS>
1206inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
1207 OverflowingBinaryOperator::NoUnsignedWrap>
1208m_NUWMul(const LHS &L, const RHS &R) {
1209 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
1210 OverflowingBinaryOperator::NoUnsignedWrap>(
1211 L, R);
1212}
1213template <typename LHS, typename RHS>
1214inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
1215 OverflowingBinaryOperator::NoUnsignedWrap>
1216m_NUWShl(const LHS &L, const RHS &R) {
1217 return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
1218 OverflowingBinaryOperator::NoUnsignedWrap>(
1219 L, R);
1220}
1221
1222template <typename LHS_t, typename RHS_t, bool Commutable = false>
1223struct SpecificBinaryOp_match
1224 : public BinaryOp_match<LHS_t, RHS_t, 0, Commutable> {
1225 unsigned Opcode;
1226
1227 SpecificBinaryOp_match(unsigned Opcode, const LHS_t &LHS, const RHS_t &RHS)
1228 : BinaryOp_match<LHS_t, RHS_t, 0, Commutable>(LHS, RHS), Opcode(Opcode) {}
1229
1230 template <typename OpTy> bool match(OpTy *V) {
1231 return BinaryOp_match<LHS_t, RHS_t, 0, Commutable>::match(Opcode, V);
1232 }
1233};
1234
1235/// Matches a specific opcode.
1236template <typename LHS, typename RHS>
1237inline SpecificBinaryOp_match<LHS, RHS> m_BinOp(unsigned Opcode, const LHS &L,
1238 const RHS &R) {
1239 return SpecificBinaryOp_match<LHS, RHS>(Opcode, L, R);
1240}
1241
1242template <typename LHS, typename RHS, bool Commutable = false>
1243struct DisjointOr_match {
1244 LHS L;
1245 RHS R;
1246
1247 DisjointOr_match(const LHS &L, const RHS &R) : L(L), R(R) {}
1248
1249 template <typename OpTy> bool match(OpTy *V) {
1250 if (auto *PDI = dyn_cast<PossiblyDisjointInst>(V)) {
1251 assert(PDI->getOpcode() == Instruction::Or && "Only or can be disjoint");
1252 if (!PDI->isDisjoint())
1253 return false;
1254 return (L.match(PDI->getOperand(0)) && R.match(PDI->getOperand(1))) ||
1255 (Commutable && L.match(PDI->getOperand(1)) &&
1256 R.match(PDI->getOperand(0)));
1257 }
1258 return false;
1259 }
1260};
1261
1262template <typename LHS, typename RHS>
1263inline DisjointOr_match<LHS, RHS> m_DisjointOr(const LHS &L, const RHS &R) {
1264 return DisjointOr_match<LHS, RHS>(L, R);
1265}
1266
1267template <typename LHS, typename RHS>
1268inline DisjointOr_match<LHS, RHS, true> m_c_DisjointOr(const LHS &L,
1269 const RHS &R) {
1270 return DisjointOr_match<LHS, RHS, true>(L, R);
1271}
1272
1273/// Match either "add" or "or disjoint".
1274template <typename LHS, typename RHS>
1275inline match_combine_or<BinaryOp_match<LHS, RHS, Instruction::Add>,
1276 DisjointOr_match<LHS, RHS>>
1277m_AddLike(const LHS &L, const RHS &R) {
1278 return m_CombineOr(m_Add(L, R), m_DisjointOr(L, R));
1279}
1280
1281//===----------------------------------------------------------------------===//
1282// Class that matches a group of binary opcodes.
1283//
1284template <typename LHS_t, typename RHS_t, typename Predicate>
1285struct BinOpPred_match : Predicate {
1286 LHS_t L;
1287 RHS_t R;
1288
1289 BinOpPred_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
1290
1291 template <typename OpTy> bool match(OpTy *V) {
1292 if (auto *I = dyn_cast<Instruction>(V))
1293 return this->isOpType(I->getOpcode()) && L.match(I->getOperand(0)) &&
1294 R.match(I->getOperand(1));
1295 return false;
1296 }
1297};
1298
1299struct is_shift_op {
1300 bool isOpType(unsigned Opcode) { return Instruction::isShift(Opcode); }
1301};
1302
1303struct is_right_shift_op {
1304 bool isOpType(unsigned Opcode) {
1305 return Opcode == Instruction::LShr || Opcode == Instruction::AShr;
1306 }
1307};
1308
1309struct is_logical_shift_op {
1310 bool isOpType(unsigned Opcode) {
1311 return Opcode == Instruction::LShr || Opcode == Instruction::Shl;
1312 }
1313};
1314
1315struct is_bitwiselogic_op {
1316 bool isOpType(unsigned Opcode) {
1317 return Instruction::isBitwiseLogicOp(Opcode);
1318 }
1319};
1320
1321struct is_idiv_op {
1322 bool isOpType(unsigned Opcode) {
1323 return Opcode == Instruction::SDiv || Opcode == Instruction::UDiv;
1324 }
1325};
1326
1327struct is_irem_op {
1328 bool isOpType(unsigned Opcode) {
1329 return Opcode == Instruction::SRem || Opcode == Instruction::URem;
1330 }
1331};
1332
1333/// Matches shift operations.
1334template <typename LHS, typename RHS>
1335inline BinOpPred_match<LHS, RHS, is_shift_op> m_Shift(const LHS &L,
1336 const RHS &R) {
1337 return BinOpPred_match<LHS, RHS, is_shift_op>(L, R);
1338}
1339
1340/// Matches logical shift operations.
1341template <typename LHS, typename RHS>
1342inline BinOpPred_match<LHS, RHS, is_right_shift_op> m_Shr(const LHS &L,
1343 const RHS &R) {
1344 return BinOpPred_match<LHS, RHS, is_right_shift_op>(L, R);
1345}
1346
1347/// Matches logical shift operations.
1348template <typename LHS, typename RHS>
1349inline BinOpPred_match<LHS, RHS, is_logical_shift_op>
1350m_LogicalShift(const LHS &L, const RHS &R) {
1351 return BinOpPred_match<LHS, RHS, is_logical_shift_op>(L, R);
1352}
1353
1354/// Matches bitwise logic operations.
1355template <typename LHS, typename RHS>
1356inline BinOpPred_match<LHS, RHS, is_bitwiselogic_op>
1357m_BitwiseLogic(const LHS &L, const RHS &R) {
1358 return BinOpPred_match<LHS, RHS, is_bitwiselogic_op>(L, R);
1359}
1360
1361/// Matches integer division operations.
1362template <typename LHS, typename RHS>
1363inline BinOpPred_match<LHS, RHS, is_idiv_op> m_IDiv(const LHS &L,
1364 const RHS &R) {
1365 return BinOpPred_match<LHS, RHS, is_idiv_op>(L, R);
1366}
1367
1368/// Matches integer remainder operations.
1369template <typename LHS, typename RHS>
1370inline BinOpPred_match<LHS, RHS, is_irem_op> m_IRem(const LHS &L,
1371 const RHS &R) {
1372 return BinOpPred_match<LHS, RHS, is_irem_op>(L, R);
1373}
1374
1375//===----------------------------------------------------------------------===//
1376// Class that matches exact binary ops.
1377//
1378template <typename SubPattern_t> struct Exact_match {
1379 SubPattern_t SubPattern;
1380
1381 Exact_match(const SubPattern_t &SP) : SubPattern(SP) {}
1382
1383 template <typename OpTy> bool match(OpTy *V) {
1384 if (auto *PEO = dyn_cast<PossiblyExactOperator>(V))
1385 return PEO->isExact() && SubPattern.match(V);
1386 return false;
1387 }
1388};
1389
1390template <typename T> inline Exact_match<T> m_Exact(const T &SubPattern) {
1391 return SubPattern;
1392}
1393
1394//===----------------------------------------------------------------------===//
1395// Matchers for CmpInst classes
1396//
1397
1398template <typename LHS_t, typename RHS_t, typename Class, typename PredicateTy,
1399 bool Commutable = false>
1400struct CmpClass_match {
1401 PredicateTy &Predicate;
1402 LHS_t L;
1403 RHS_t R;
1404
1405 // The evaluation order is always stable, regardless of Commutability.
1406 // The LHS is always matched first.
1407 CmpClass_match(PredicateTy &Pred, const LHS_t &LHS, const RHS_t &RHS)
1408 : Predicate(Pred), L(LHS), R(RHS) {}
1409
1410 template <typename OpTy> bool match(OpTy *V) {
1411 if (auto *I = dyn_cast<Class>(V)) {
1412 if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) {
1413 Predicate = I->getPredicate();
1414 return true;
1415 } else if (Commutable && L.match(I->getOperand(1)) &&
1416 R.match(I->getOperand(0))) {
1417 Predicate = I->getSwappedPredicate();
1418 return true;
1419 }
1420 }
1421 return false;
1422 }
1423};
1424
1425template <typename LHS, typename RHS>
1426inline CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate>
1427m_Cmp(CmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1428 return CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate>(Pred, L, R);
1429}
1430
1431template <typename LHS, typename RHS>
1432inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>
1433m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1434 return CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>(Pred, L, R);
1435}
1436
1437template <typename LHS, typename RHS>
1438inline CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>
1439m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1440 return CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>(Pred, L, R);
1441}
1442
1443//===----------------------------------------------------------------------===//
1444// Matchers for instructions with a given opcode and number of operands.
1445//
1446
1447/// Matches instructions with Opcode and three operands.
1448template <typename T0, unsigned Opcode> struct OneOps_match {
1449 T0 Op1;
1450
1451 OneOps_match(const T0 &Op1) : Op1(Op1) {}
1452
1453 template <typename OpTy> bool match(OpTy *V) {
1454 if (V->getValueID() == Value::InstructionVal + Opcode) {
1455 auto *I = cast<Instruction>(V);
1456 return Op1.match(I->getOperand(0));
1457 }
1458 return false;
1459 }
1460};
1461
1462/// Matches instructions with Opcode and three operands.
1463template <typename T0, typename T1, unsigned Opcode> struct TwoOps_match {
1464 T0 Op1;
1465 T1 Op2;
1466
1467 TwoOps_match(const T0 &Op1, const T1 &Op2) : Op1(Op1), Op2(Op2) {}
1468
1469 template <typename OpTy> bool match(OpTy *V) {
1470 if (V->getValueID() == Value::InstructionVal + Opcode) {
1471 auto *I = cast<Instruction>(V);
1472 return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1));
1473 }
1474 return false;
1475 }
1476};
1477
1478/// Matches instructions with Opcode and three operands.
1479template <typename T0, typename T1, typename T2, unsigned Opcode>
1480struct ThreeOps_match {
1481 T0 Op1;
1482 T1 Op2;
1483 T2 Op3;
1484
1485 ThreeOps_match(const T0 &Op1, const T1 &Op2, const T2 &Op3)
1486 : Op1(Op1), Op2(Op2), Op3(Op3) {}
1487
1488 template <typename OpTy> bool match(OpTy *V) {
1489 if (V->getValueID() == Value::InstructionVal + Opcode) {
1490 auto *I = cast<Instruction>(V);
1491 return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1)) &&
1492 Op3.match(I->getOperand(2));
1493 }
1494 return false;
1495 }
1496};
1497
1498/// Matches instructions with Opcode and any number of operands
1499template <unsigned Opcode, typename... OperandTypes> struct AnyOps_match {
1500 std::tuple<OperandTypes...> Operands;
1501
1502 AnyOps_match(const OperandTypes &...Ops) : Operands(Ops...) {}
1503
1504 // Operand matching works by recursively calling match_operands, matching the
1505 // operands left to right. The first version is called for each operand but
1506 // the last, for which the second version is called. The second version of
1507 // match_operands is also used to match each individual operand.
1508 template <int Idx, int Last>
1509 std::enable_if_t<Idx != Last, bool> match_operands(const Instruction *I) {
1510 return match_operands<Idx, Idx>(I) && match_operands<Idx + 1, Last>(I);
1511 }
1512
1513 template <int Idx, int Last>
1514 std::enable_if_t<Idx == Last, bool> match_operands(const Instruction *I) {
1515 return std::get<Idx>(Operands).match(I->getOperand(i: Idx));
1516 }
1517
1518 template <typename OpTy> bool match(OpTy *V) {
1519 if (V->getValueID() == Value::InstructionVal + Opcode) {
1520 auto *I = cast<Instruction>(V);
1521 return I->getNumOperands() == sizeof...(OperandTypes) &&
1522 match_operands<0, sizeof...(OperandTypes) - 1>(I);
1523 }
1524 return false;
1525 }
1526};
1527
1528/// Matches SelectInst.
1529template <typename Cond, typename LHS, typename RHS>
1530inline ThreeOps_match<Cond, LHS, RHS, Instruction::Select>
1531m_Select(const Cond &C, const LHS &L, const RHS &R) {
1532 return ThreeOps_match<Cond, LHS, RHS, Instruction::Select>(C, L, R);
1533}
1534
1535/// This matches a select of two constants, e.g.:
1536/// m_SelectCst<-1, 0>(m_Value(V))
1537template <int64_t L, int64_t R, typename Cond>
1538inline ThreeOps_match<Cond, constantint_match<L>, constantint_match<R>,
1539 Instruction::Select>
1540m_SelectCst(const Cond &C) {
1541 return m_Select(C, m_ConstantInt<L>(), m_ConstantInt<R>());
1542}
1543
1544/// Matches FreezeInst.
1545template <typename OpTy>
1546inline OneOps_match<OpTy, Instruction::Freeze> m_Freeze(const OpTy &Op) {
1547 return OneOps_match<OpTy, Instruction::Freeze>(Op);
1548}
1549
1550/// Matches InsertElementInst.
1551template <typename Val_t, typename Elt_t, typename Idx_t>
1552inline ThreeOps_match<Val_t, Elt_t, Idx_t, Instruction::InsertElement>
1553m_InsertElt(const Val_t &Val, const Elt_t &Elt, const Idx_t &Idx) {
1554 return ThreeOps_match<Val_t, Elt_t, Idx_t, Instruction::InsertElement>(
1555 Val, Elt, Idx);
1556}
1557
1558/// Matches ExtractElementInst.
1559template <typename Val_t, typename Idx_t>
1560inline TwoOps_match<Val_t, Idx_t, Instruction::ExtractElement>
1561m_ExtractElt(const Val_t &Val, const Idx_t &Idx) {
1562 return TwoOps_match<Val_t, Idx_t, Instruction::ExtractElement>(Val, Idx);
1563}
1564
1565/// Matches shuffle.
1566template <typename T0, typename T1, typename T2> struct Shuffle_match {
1567 T0 Op1;
1568 T1 Op2;
1569 T2 Mask;
1570
1571 Shuffle_match(const T0 &Op1, const T1 &Op2, const T2 &Mask)
1572 : Op1(Op1), Op2(Op2), Mask(Mask) {}
1573
1574 template <typename OpTy> bool match(OpTy *V) {
1575 if (auto *I = dyn_cast<ShuffleVectorInst>(V)) {
1576 return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1)) &&
1577 Mask.match(I->getShuffleMask());
1578 }
1579 return false;
1580 }
1581};
1582
1583struct m_Mask {
1584 ArrayRef<int> &MaskRef;
1585 m_Mask(ArrayRef<int> &MaskRef) : MaskRef(MaskRef) {}
1586 bool match(ArrayRef<int> Mask) {
1587 MaskRef = Mask;
1588 return true;
1589 }
1590};
1591
1592struct m_ZeroMask {
1593 bool match(ArrayRef<int> Mask) {
1594 return all_of(Range&: Mask, P: [](int Elem) { return Elem == 0 || Elem == -1; });
1595 }
1596};
1597
1598struct m_SpecificMask {
1599 ArrayRef<int> &MaskRef;
1600 m_SpecificMask(ArrayRef<int> &MaskRef) : MaskRef(MaskRef) {}
1601 bool match(ArrayRef<int> Mask) { return MaskRef == Mask; }
1602};
1603
1604struct m_SplatOrUndefMask {
1605 int &SplatIndex;
1606 m_SplatOrUndefMask(int &SplatIndex) : SplatIndex(SplatIndex) {}
1607 bool match(ArrayRef<int> Mask) {
1608 const auto *First = find_if(Range&: Mask, P: [](int Elem) { return Elem != -1; });
1609 if (First == Mask.end())
1610 return false;
1611 SplatIndex = *First;
1612 return all_of(Range&: Mask,
1613 P: [First](int Elem) { return Elem == *First || Elem == -1; });
1614 }
1615};
1616
1617template <typename PointerOpTy, typename OffsetOpTy> struct PtrAdd_match {
1618 PointerOpTy PointerOp;
1619 OffsetOpTy OffsetOp;
1620
1621 PtrAdd_match(const PointerOpTy &PointerOp, const OffsetOpTy &OffsetOp)
1622 : PointerOp(PointerOp), OffsetOp(OffsetOp) {}
1623
1624 template <typename OpTy> bool match(OpTy *V) {
1625 auto *GEP = dyn_cast<GEPOperator>(V);
1626 return GEP && GEP->getSourceElementType()->isIntegerTy(8) &&
1627 PointerOp.match(GEP->getPointerOperand()) &&
1628 OffsetOp.match(GEP->idx_begin()->get());
1629 }
1630};
1631
1632/// Matches ShuffleVectorInst independently of mask value.
1633template <typename V1_t, typename V2_t>
1634inline TwoOps_match<V1_t, V2_t, Instruction::ShuffleVector>
1635m_Shuffle(const V1_t &v1, const V2_t &v2) {
1636 return TwoOps_match<V1_t, V2_t, Instruction::ShuffleVector>(v1, v2);
1637}
1638
1639template <typename V1_t, typename V2_t, typename Mask_t>
1640inline Shuffle_match<V1_t, V2_t, Mask_t>
1641m_Shuffle(const V1_t &v1, const V2_t &v2, const Mask_t &mask) {
1642 return Shuffle_match<V1_t, V2_t, Mask_t>(v1, v2, mask);
1643}
1644
1645/// Matches LoadInst.
1646template <typename OpTy>
1647inline OneOps_match<OpTy, Instruction::Load> m_Load(const OpTy &Op) {
1648 return OneOps_match<OpTy, Instruction::Load>(Op);
1649}
1650
1651/// Matches StoreInst.
1652template <typename ValueOpTy, typename PointerOpTy>
1653inline TwoOps_match<ValueOpTy, PointerOpTy, Instruction::Store>
1654m_Store(const ValueOpTy &ValueOp, const PointerOpTy &PointerOp) {
1655 return TwoOps_match<ValueOpTy, PointerOpTy, Instruction::Store>(ValueOp,
1656 PointerOp);
1657}
1658
1659/// Matches GetElementPtrInst.
1660template <typename... OperandTypes>
1661inline auto m_GEP(const OperandTypes &...Ops) {
1662 return AnyOps_match<Instruction::GetElementPtr, OperandTypes...>(Ops...);
1663}
1664
1665/// Matches GEP with i8 source element type
1666template <typename PointerOpTy, typename OffsetOpTy>
1667inline PtrAdd_match<PointerOpTy, OffsetOpTy>
1668m_PtrAdd(const PointerOpTy &PointerOp, const OffsetOpTy &OffsetOp) {
1669 return PtrAdd_match<PointerOpTy, OffsetOpTy>(PointerOp, OffsetOp);
1670}
1671
1672//===----------------------------------------------------------------------===//
1673// Matchers for CastInst classes
1674//
1675
1676template <typename Op_t, unsigned Opcode> struct CastOperator_match {
1677 Op_t Op;
1678
1679 CastOperator_match(const Op_t &OpMatch) : Op(OpMatch) {}
1680
1681 template <typename OpTy> bool match(OpTy *V) {
1682 if (auto *O = dyn_cast<Operator>(V))
1683 return O->getOpcode() == Opcode && Op.match(O->getOperand(0));
1684 return false;
1685 }
1686};
1687
1688template <typename Op_t, typename Class> struct CastInst_match {
1689 Op_t Op;
1690
1691 CastInst_match(const Op_t &OpMatch) : Op(OpMatch) {}
1692
1693 template <typename OpTy> bool match(OpTy *V) {
1694 if (auto *I = dyn_cast<Class>(V))
1695 return Op.match(I->getOperand(0));
1696 return false;
1697 }
1698};
1699
1700template <typename Op_t> struct PtrToIntSameSize_match {
1701 const DataLayout &DL;
1702 Op_t Op;
1703
1704 PtrToIntSameSize_match(const DataLayout &DL, const Op_t &OpMatch)
1705 : DL(DL), Op(OpMatch) {}
1706
1707 template <typename OpTy> bool match(OpTy *V) {
1708 if (auto *O = dyn_cast<Operator>(V))
1709 return O->getOpcode() == Instruction::PtrToInt &&
1710 DL.getTypeSizeInBits(Ty: O->getType()) ==
1711 DL.getTypeSizeInBits(Ty: O->getOperand(0)->getType()) &&
1712 Op.match(O->getOperand(0));
1713 return false;
1714 }
1715};
1716
1717template <typename Op_t> struct NNegZExt_match {
1718 Op_t Op;
1719
1720 NNegZExt_match(const Op_t &OpMatch) : Op(OpMatch) {}
1721
1722 template <typename OpTy> bool match(OpTy *V) {
1723 if (auto *I = dyn_cast<ZExtInst>(V))
1724 return I->hasNonNeg() && Op.match(I->getOperand(0));
1725 return false;
1726 }
1727};
1728
1729/// Matches BitCast.
1730template <typename OpTy>
1731inline CastOperator_match<OpTy, Instruction::BitCast>
1732m_BitCast(const OpTy &Op) {
1733 return CastOperator_match<OpTy, Instruction::BitCast>(Op);
1734}
1735
1736template <typename Op_t> struct ElementWiseBitCast_match {
1737 Op_t Op;
1738
1739 ElementWiseBitCast_match(const Op_t &OpMatch) : Op(OpMatch) {}
1740
1741 template <typename OpTy> bool match(OpTy *V) {
1742 BitCastInst *I = dyn_cast<BitCastInst>(V);
1743 if (!I)
1744 return false;
1745 Type *SrcType = I->getSrcTy();
1746 Type *DstType = I->getType();
1747 // Make sure the bitcast doesn't change between scalar and vector and
1748 // doesn't change the number of vector elements.
1749 if (SrcType->isVectorTy() != DstType->isVectorTy())
1750 return false;
1751 if (VectorType *SrcVecTy = dyn_cast<VectorType>(Val: SrcType);
1752 SrcVecTy && SrcVecTy->getElementCount() !=
1753 cast<VectorType>(Val: DstType)->getElementCount())
1754 return false;
1755 return Op.match(I->getOperand(i_nocapture: 0));
1756 }
1757};
1758
1759template <typename OpTy>
1760inline ElementWiseBitCast_match<OpTy> m_ElementWiseBitCast(const OpTy &Op) {
1761 return ElementWiseBitCast_match<OpTy>(Op);
1762}
1763
1764/// Matches PtrToInt.
1765template <typename OpTy>
1766inline CastOperator_match<OpTy, Instruction::PtrToInt>
1767m_PtrToInt(const OpTy &Op) {
1768 return CastOperator_match<OpTy, Instruction::PtrToInt>(Op);
1769}
1770
1771template <typename OpTy>
1772inline PtrToIntSameSize_match<OpTy> m_PtrToIntSameSize(const DataLayout &DL,
1773 const OpTy &Op) {
1774 return PtrToIntSameSize_match<OpTy>(DL, Op);
1775}
1776
1777/// Matches IntToPtr.
1778template <typename OpTy>
1779inline CastOperator_match<OpTy, Instruction::IntToPtr>
1780m_IntToPtr(const OpTy &Op) {
1781 return CastOperator_match<OpTy, Instruction::IntToPtr>(Op);
1782}
1783
1784/// Matches Trunc.
1785template <typename OpTy>
1786inline CastOperator_match<OpTy, Instruction::Trunc> m_Trunc(const OpTy &Op) {
1787 return CastOperator_match<OpTy, Instruction::Trunc>(Op);
1788}
1789
1790template <typename OpTy>
1791inline match_combine_or<CastOperator_match<OpTy, Instruction::Trunc>, OpTy>
1792m_TruncOrSelf(const OpTy &Op) {
1793 return m_CombineOr(m_Trunc(Op), Op);
1794}
1795
1796/// Matches SExt.
1797template <typename OpTy>
1798inline CastInst_match<OpTy, SExtInst> m_SExt(const OpTy &Op) {
1799 return CastInst_match<OpTy, SExtInst>(Op);
1800}
1801
1802/// Matches ZExt.
1803template <typename OpTy>
1804inline CastInst_match<OpTy, ZExtInst> m_ZExt(const OpTy &Op) {
1805 return CastInst_match<OpTy, ZExtInst>(Op);
1806}
1807
1808template <typename OpTy>
1809inline NNegZExt_match<OpTy> m_NNegZExt(const OpTy &Op) {
1810 return NNegZExt_match<OpTy>(Op);
1811}
1812
1813template <typename OpTy>
1814inline match_combine_or<CastInst_match<OpTy, ZExtInst>, OpTy>
1815m_ZExtOrSelf(const OpTy &Op) {
1816 return m_CombineOr(m_ZExt(Op), Op);
1817}
1818
1819template <typename OpTy>
1820inline match_combine_or<CastInst_match<OpTy, SExtInst>, OpTy>
1821m_SExtOrSelf(const OpTy &Op) {
1822 return m_CombineOr(m_SExt(Op), Op);
1823}
1824
1825/// Match either "sext" or "zext nneg".
1826template <typename OpTy>
1827inline match_combine_or<CastInst_match<OpTy, SExtInst>, NNegZExt_match<OpTy>>
1828m_SExtLike(const OpTy &Op) {
1829 return m_CombineOr(m_SExt(Op), m_NNegZExt(Op));
1830}
1831
1832template <typename OpTy>
1833inline match_combine_or<CastInst_match<OpTy, ZExtInst>,
1834 CastInst_match<OpTy, SExtInst>>
1835m_ZExtOrSExt(const OpTy &Op) {
1836 return m_CombineOr(m_ZExt(Op), m_SExt(Op));
1837}
1838
1839template <typename OpTy>
1840inline match_combine_or<match_combine_or<CastInst_match<OpTy, ZExtInst>,
1841 CastInst_match<OpTy, SExtInst>>,
1842 OpTy>
1843m_ZExtOrSExtOrSelf(const OpTy &Op) {
1844 return m_CombineOr(m_ZExtOrSExt(Op), Op);
1845}
1846
1847template <typename OpTy>
1848inline CastInst_match<OpTy, UIToFPInst> m_UIToFP(const OpTy &Op) {
1849 return CastInst_match<OpTy, UIToFPInst>(Op);
1850}
1851
1852template <typename OpTy>
1853inline CastInst_match<OpTy, SIToFPInst> m_SIToFP(const OpTy &Op) {
1854 return CastInst_match<OpTy, SIToFPInst>(Op);
1855}
1856
1857template <typename OpTy>
1858inline CastInst_match<OpTy, FPToUIInst> m_FPToUI(const OpTy &Op) {
1859 return CastInst_match<OpTy, FPToUIInst>(Op);
1860}
1861
1862template <typename OpTy>
1863inline CastInst_match<OpTy, FPToSIInst> m_FPToSI(const OpTy &Op) {
1864 return CastInst_match<OpTy, FPToSIInst>(Op);
1865}
1866
1867template <typename OpTy>
1868inline CastInst_match<OpTy, FPTruncInst> m_FPTrunc(const OpTy &Op) {
1869 return CastInst_match<OpTy, FPTruncInst>(Op);
1870}
1871
1872template <typename OpTy>
1873inline CastInst_match<OpTy, FPExtInst> m_FPExt(const OpTy &Op) {
1874 return CastInst_match<OpTy, FPExtInst>(Op);
1875}
1876
1877//===----------------------------------------------------------------------===//
1878// Matchers for control flow.
1879//
1880
1881struct br_match {
1882 BasicBlock *&Succ;
1883
1884 br_match(BasicBlock *&Succ) : Succ(Succ) {}
1885
1886 template <typename OpTy> bool match(OpTy *V) {
1887 if (auto *BI = dyn_cast<BranchInst>(V))
1888 if (BI->isUnconditional()) {
1889 Succ = BI->getSuccessor(0);
1890 return true;
1891 }
1892 return false;
1893 }
1894};
1895
1896inline br_match m_UnconditionalBr(BasicBlock *&Succ) { return br_match(Succ); }
1897
1898template <typename Cond_t, typename TrueBlock_t, typename FalseBlock_t>
1899struct brc_match {
1900 Cond_t Cond;
1901 TrueBlock_t T;
1902 FalseBlock_t F;
1903
1904 brc_match(const Cond_t &C, const TrueBlock_t &t, const FalseBlock_t &f)
1905 : Cond(C), T(t), F(f) {}
1906
1907 template <typename OpTy> bool match(OpTy *V) {
1908 if (auto *BI = dyn_cast<BranchInst>(V))
1909 if (BI->isConditional() && Cond.match(BI->getCondition()))
1910 return T.match(BI->getSuccessor(0)) && F.match(BI->getSuccessor(1));
1911 return false;
1912 }
1913};
1914
1915template <typename Cond_t>
1916inline brc_match<Cond_t, bind_ty<BasicBlock>, bind_ty<BasicBlock>>
1917m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) {
1918 return brc_match<Cond_t, bind_ty<BasicBlock>, bind_ty<BasicBlock>>(
1919 C, m_BasicBlock(V&: T), m_BasicBlock(V&: F));
1920}
1921
1922template <typename Cond_t, typename TrueBlock_t, typename FalseBlock_t>
1923inline brc_match<Cond_t, TrueBlock_t, FalseBlock_t>
1924m_Br(const Cond_t &C, const TrueBlock_t &T, const FalseBlock_t &F) {
1925 return brc_match<Cond_t, TrueBlock_t, FalseBlock_t>(C, T, F);
1926}
1927
1928//===----------------------------------------------------------------------===//
1929// Matchers for max/min idioms, eg: "select (sgt x, y), x, y" -> smax(x,y).
1930//
1931
1932template <typename CmpInst_t, typename LHS_t, typename RHS_t, typename Pred_t,
1933 bool Commutable = false>
1934struct MaxMin_match {
1935 using PredType = Pred_t;
1936 LHS_t L;
1937 RHS_t R;
1938
1939 // The evaluation order is always stable, regardless of Commutability.
1940 // The LHS is always matched first.
1941 MaxMin_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
1942
1943 template <typename OpTy> bool match(OpTy *V) {
1944 if (auto *II = dyn_cast<IntrinsicInst>(V)) {
1945 Intrinsic::ID IID = II->getIntrinsicID();
1946 if ((IID == Intrinsic::smax && Pred_t::match(ICmpInst::ICMP_SGT)) ||
1947 (IID == Intrinsic::smin && Pred_t::match(ICmpInst::ICMP_SLT)) ||
1948 (IID == Intrinsic::umax && Pred_t::match(ICmpInst::ICMP_UGT)) ||
1949 (IID == Intrinsic::umin && Pred_t::match(ICmpInst::ICMP_ULT))) {
1950 Value *LHS = II->getOperand(0), *RHS = II->getOperand(1);
1951 return (L.match(LHS) && R.match(RHS)) ||
1952 (Commutable && L.match(RHS) && R.match(LHS));
1953 }
1954 }
1955 // Look for "(x pred y) ? x : y" or "(x pred y) ? y : x".
1956 auto *SI = dyn_cast<SelectInst>(V);
1957 if (!SI)
1958 return false;
1959 auto *Cmp = dyn_cast<CmpInst_t>(SI->getCondition());
1960 if (!Cmp)
1961 return false;
1962 // At this point we have a select conditioned on a comparison. Check that
1963 // it is the values returned by the select that are being compared.
1964 auto *TrueVal = SI->getTrueValue();
1965 auto *FalseVal = SI->getFalseValue();
1966 auto *LHS = Cmp->getOperand(0);
1967 auto *RHS = Cmp->getOperand(1);
1968 if ((TrueVal != LHS || FalseVal != RHS) &&
1969 (TrueVal != RHS || FalseVal != LHS))
1970 return false;
1971 typename CmpInst_t::Predicate Pred =
1972 LHS == TrueVal ? Cmp->getPredicate() : Cmp->getInversePredicate();
1973 // Does "(x pred y) ? x : y" represent the desired max/min operation?
1974 if (!Pred_t::match(Pred))
1975 return false;
1976 // It does! Bind the operands.
1977 return (L.match(LHS) && R.match(RHS)) ||
1978 (Commutable && L.match(RHS) && R.match(LHS));
1979 }
1980};
1981
1982/// Helper class for identifying signed max predicates.
1983struct smax_pred_ty {
1984 static bool match(ICmpInst::Predicate Pred) {
1985 return Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE;
1986 }
1987};
1988
1989/// Helper class for identifying signed min predicates.
1990struct smin_pred_ty {
1991 static bool match(ICmpInst::Predicate Pred) {
1992 return Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_SLE;
1993 }
1994};
1995
1996/// Helper class for identifying unsigned max predicates.
1997struct umax_pred_ty {
1998 static bool match(ICmpInst::Predicate Pred) {
1999 return Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE;
2000 }
2001};
2002
2003/// Helper class for identifying unsigned min predicates.
2004struct umin_pred_ty {
2005 static bool match(ICmpInst::Predicate Pred) {
2006 return Pred == CmpInst::ICMP_ULT || Pred == CmpInst::ICMP_ULE;
2007 }
2008};
2009
2010/// Helper class for identifying ordered max predicates.
2011struct ofmax_pred_ty {
2012 static bool match(FCmpInst::Predicate Pred) {
2013 return Pred == CmpInst::FCMP_OGT || Pred == CmpInst::FCMP_OGE;
2014 }
2015};
2016
2017/// Helper class for identifying ordered min predicates.
2018struct ofmin_pred_ty {
2019 static bool match(FCmpInst::Predicate Pred) {
2020 return Pred == CmpInst::FCMP_OLT || Pred == CmpInst::FCMP_OLE;
2021 }
2022};
2023
2024/// Helper class for identifying unordered max predicates.
2025struct ufmax_pred_ty {
2026 static bool match(FCmpInst::Predicate Pred) {
2027 return Pred == CmpInst::FCMP_UGT || Pred == CmpInst::FCMP_UGE;
2028 }
2029};
2030
2031/// Helper class for identifying unordered min predicates.
2032struct ufmin_pred_ty {
2033 static bool match(FCmpInst::Predicate Pred) {
2034 return Pred == CmpInst::FCMP_ULT || Pred == CmpInst::FCMP_ULE;
2035 }
2036};
2037
2038template <typename LHS, typename RHS>
2039inline MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty> m_SMax(const LHS &L,
2040 const RHS &R) {
2041 return MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty>(L, R);
2042}
2043
2044template <typename LHS, typename RHS>
2045inline MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty> m_SMin(const LHS &L,
2046 const RHS &R) {
2047 return MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty>(L, R);
2048}
2049
2050template <typename LHS, typename RHS>
2051inline MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty> m_UMax(const LHS &L,
2052 const RHS &R) {
2053 return MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty>(L, R);
2054}
2055
2056template <typename LHS, typename RHS>
2057inline MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty> m_UMin(const LHS &L,
2058 const RHS &R) {
2059 return MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty>(L, R);
2060}
2061
2062template <typename LHS, typename RHS>
2063inline match_combine_or<
2064 match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty>,
2065 MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty>>,
2066 match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty>,
2067 MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty>>>
2068m_MaxOrMin(const LHS &L, const RHS &R) {
2069 return m_CombineOr(m_CombineOr(m_SMax(L, R), m_SMin(L, R)),
2070 m_CombineOr(m_UMax(L, R), m_UMin(L, R)));
2071}
2072
2073/// Match an 'ordered' floating point maximum function.
2074/// Floating point has one special value 'NaN'. Therefore, there is no total
2075/// order. However, if we can ignore the 'NaN' value (for example, because of a
2076/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum'
2077/// semantics. In the presence of 'NaN' we have to preserve the original
2078/// select(fcmp(ogt/ge, L, R), L, R) semantics matched by this predicate.
2079///
2080/// max(L, R) iff L and R are not NaN
2081/// m_OrdFMax(L, R) = R iff L or R are NaN
2082template <typename LHS, typename RHS>
2083inline MaxMin_match<FCmpInst, LHS, RHS, ofmax_pred_ty> m_OrdFMax(const LHS &L,
2084 const RHS &R) {
2085 return MaxMin_match<FCmpInst, LHS, RHS, ofmax_pred_ty>(L, R);
2086}
2087
2088/// Match an 'ordered' floating point minimum function.
2089/// Floating point has one special value 'NaN'. Therefore, there is no total
2090/// order. However, if we can ignore the 'NaN' value (for example, because of a
2091/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum'
2092/// semantics. In the presence of 'NaN' we have to preserve the original
2093/// select(fcmp(olt/le, L, R), L, R) semantics matched by this predicate.
2094///
2095/// min(L, R) iff L and R are not NaN
2096/// m_OrdFMin(L, R) = R iff L or R are NaN
2097template <typename LHS, typename RHS>
2098inline MaxMin_match<FCmpInst, LHS, RHS, ofmin_pred_ty> m_OrdFMin(const LHS &L,
2099 const RHS &R) {
2100 return MaxMin_match<FCmpInst, LHS, RHS, ofmin_pred_ty>(L, R);
2101}
2102
2103/// Match an 'unordered' floating point maximum function.
2104/// Floating point has one special value 'NaN'. Therefore, there is no total
2105/// order. However, if we can ignore the 'NaN' value (for example, because of a
2106/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum'
2107/// semantics. In the presence of 'NaN' we have to preserve the original
2108/// select(fcmp(ugt/ge, L, R), L, R) semantics matched by this predicate.
2109///
2110/// max(L, R) iff L and R are not NaN
2111/// m_UnordFMax(L, R) = L iff L or R are NaN
2112template <typename LHS, typename RHS>
2113inline MaxMin_match<FCmpInst, LHS, RHS, ufmax_pred_ty>
2114m_UnordFMax(const LHS &L, const RHS &R) {
2115 return MaxMin_match<FCmpInst, LHS, RHS, ufmax_pred_ty>(L, R);
2116}
2117
2118/// Match an 'unordered' floating point minimum function.
2119/// Floating point has one special value 'NaN'. Therefore, there is no total
2120/// order. However, if we can ignore the 'NaN' value (for example, because of a
2121/// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum'
2122/// semantics. In the presence of 'NaN' we have to preserve the original
2123/// select(fcmp(ult/le, L, R), L, R) semantics matched by this predicate.
2124///
2125/// min(L, R) iff L and R are not NaN
2126/// m_UnordFMin(L, R) = L iff L or R are NaN
2127template <typename LHS, typename RHS>
2128inline MaxMin_match<FCmpInst, LHS, RHS, ufmin_pred_ty>
2129m_UnordFMin(const LHS &L, const RHS &R) {
2130 return MaxMin_match<FCmpInst, LHS, RHS, ufmin_pred_ty>(L, R);
2131}
2132
2133//===----------------------------------------------------------------------===//
2134// Matchers for overflow check patterns: e.g. (a + b) u< a, (a ^ -1) <u b
2135// Note that S might be matched to other instructions than AddInst.
2136//
2137
2138template <typename LHS_t, typename RHS_t, typename Sum_t>
2139struct UAddWithOverflow_match {
2140 LHS_t L;
2141 RHS_t R;
2142 Sum_t S;
2143
2144 UAddWithOverflow_match(const LHS_t &L, const RHS_t &R, const Sum_t &S)
2145 : L(L), R(R), S(S) {}
2146
2147 template <typename OpTy> bool match(OpTy *V) {
2148 Value *ICmpLHS, *ICmpRHS;
2149 ICmpInst::Predicate Pred;
2150 if (!m_ICmp(Pred, L: m_Value(V&: ICmpLHS), R: m_Value(V&: ICmpRHS)).match(V))
2151 return false;
2152
2153 Value *AddLHS, *AddRHS;
2154 auto AddExpr = m_Add(L: m_Value(V&: AddLHS), R: m_Value(V&: AddRHS));
2155
2156 // (a + b) u< a, (a + b) u< b
2157 if (Pred == ICmpInst::ICMP_ULT)
2158 if (AddExpr.match(V: ICmpLHS) && (ICmpRHS == AddLHS || ICmpRHS == AddRHS))
2159 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS);
2160
2161 // a >u (a + b), b >u (a + b)
2162 if (Pred == ICmpInst::ICMP_UGT)
2163 if (AddExpr.match(V: ICmpRHS) && (ICmpLHS == AddLHS || ICmpLHS == AddRHS))
2164 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS);
2165
2166 Value *Op1;
2167 auto XorExpr = m_OneUse(SubPattern: m_Xor(L: m_Value(V&: Op1), R: m_AllOnes()));
2168 // (a ^ -1) <u b
2169 if (Pred == ICmpInst::ICMP_ULT) {
2170 if (XorExpr.match(V: ICmpLHS))
2171 return L.match(Op1) && R.match(ICmpRHS) && S.match(ICmpLHS);
2172 }
2173 // b > u (a ^ -1)
2174 if (Pred == ICmpInst::ICMP_UGT) {
2175 if (XorExpr.match(V: ICmpRHS))
2176 return L.match(Op1) && R.match(ICmpLHS) && S.match(ICmpRHS);
2177 }
2178
2179 // Match special-case for increment-by-1.
2180 if (Pred == ICmpInst::ICMP_EQ) {
2181 // (a + 1) == 0
2182 // (1 + a) == 0
2183 if (AddExpr.match(V: ICmpLHS) && m_ZeroInt().match(V: ICmpRHS) &&
2184 (m_One().match(V: AddLHS) || m_One().match(V: AddRHS)))
2185 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS);
2186 // 0 == (a + 1)
2187 // 0 == (1 + a)
2188 if (m_ZeroInt().match(V: ICmpLHS) && AddExpr.match(V: ICmpRHS) &&
2189 (m_One().match(V: AddLHS) || m_One().match(V: AddRHS)))
2190 return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS);
2191 }
2192
2193 return false;
2194 }
2195};
2196
2197/// Match an icmp instruction checking for unsigned overflow on addition.
2198///
2199/// S is matched to the addition whose result is being checked for overflow, and
2200/// L and R are matched to the LHS and RHS of S.
2201template <typename LHS_t, typename RHS_t, typename Sum_t>
2202UAddWithOverflow_match<LHS_t, RHS_t, Sum_t>
2203m_UAddWithOverflow(const LHS_t &L, const RHS_t &R, const Sum_t &S) {
2204 return UAddWithOverflow_match<LHS_t, RHS_t, Sum_t>(L, R, S);
2205}
2206
2207template <typename Opnd_t> struct Argument_match {
2208 unsigned OpI;
2209 Opnd_t Val;
2210
2211 Argument_match(unsigned OpIdx, const Opnd_t &V) : OpI(OpIdx), Val(V) {}
2212
2213 template <typename OpTy> bool match(OpTy *V) {
2214 // FIXME: Should likely be switched to use `CallBase`.
2215 if (const auto *CI = dyn_cast<CallInst>(V))
2216 return Val.match(CI->getArgOperand(OpI));
2217 return false;
2218 }
2219};
2220
2221/// Match an argument.
2222template <unsigned OpI, typename Opnd_t>
2223inline Argument_match<Opnd_t> m_Argument(const Opnd_t &Op) {
2224 return Argument_match<Opnd_t>(OpI, Op);
2225}
2226
2227/// Intrinsic matchers.
2228struct IntrinsicID_match {
2229 unsigned ID;
2230
2231 IntrinsicID_match(Intrinsic::ID IntrID) : ID(IntrID) {}
2232
2233 template <typename OpTy> bool match(OpTy *V) {
2234 if (const auto *CI = dyn_cast<CallInst>(V))
2235 if (const auto *F = CI->getCalledFunction())
2236 return F->getIntrinsicID() == ID;
2237 return false;
2238 }
2239};
2240
2241/// Intrinsic matches are combinations of ID matchers, and argument
2242/// matchers. Higher arity matcher are defined recursively in terms of and-ing
2243/// them with lower arity matchers. Here's some convenient typedefs for up to
2244/// several arguments, and more can be added as needed
2245template <typename T0 = void, typename T1 = void, typename T2 = void,
2246 typename T3 = void, typename T4 = void, typename T5 = void,
2247 typename T6 = void, typename T7 = void, typename T8 = void,
2248 typename T9 = void, typename T10 = void>
2249struct m_Intrinsic_Ty;
2250template <typename T0> struct m_Intrinsic_Ty<T0> {
2251 using Ty = match_combine_and<IntrinsicID_match, Argument_match<T0>>;
2252};
2253template <typename T0, typename T1> struct m_Intrinsic_Ty<T0, T1> {
2254 using Ty =
2255 match_combine_and<typename m_Intrinsic_Ty<T0>::Ty, Argument_match<T1>>;
2256};
2257template <typename T0, typename T1, typename T2>
2258struct m_Intrinsic_Ty<T0, T1, T2> {
2259 using Ty = match_combine_and<typename m_Intrinsic_Ty<T0, T1>::Ty,
2260 Argument_match<T2>>;
2261};
2262template <typename T0, typename T1, typename T2, typename T3>
2263struct m_Intrinsic_Ty<T0, T1, T2, T3> {
2264 using Ty = match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2>::Ty,
2265 Argument_match<T3>>;
2266};
2267
2268template <typename T0, typename T1, typename T2, typename T3, typename T4>
2269struct m_Intrinsic_Ty<T0, T1, T2, T3, T4> {
2270 using Ty = match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2, T3>::Ty,
2271 Argument_match<T4>>;
2272};
2273
2274template <typename T0, typename T1, typename T2, typename T3, typename T4,
2275 typename T5>
2276struct m_Intrinsic_Ty<T0, T1, T2, T3, T4, T5> {
2277 using Ty = match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2, T3, T4>::Ty,
2278 Argument_match<T5>>;
2279};
2280
2281/// Match intrinsic calls like this:
2282/// m_Intrinsic<Intrinsic::fabs>(m_Value(X))
2283template <Intrinsic::ID IntrID> inline IntrinsicID_match m_Intrinsic() {
2284 return IntrinsicID_match(IntrID);
2285}
2286
2287/// Matches MaskedLoad Intrinsic.
2288template <typename Opnd0, typename Opnd1, typename Opnd2, typename Opnd3>
2289inline typename m_Intrinsic_Ty<Opnd0, Opnd1, Opnd2, Opnd3>::Ty
2290m_MaskedLoad(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2,
2291 const Opnd3 &Op3) {
2292 return m_Intrinsic<Intrinsic::masked_load>(Op0, Op1, Op2, Op3);
2293}
2294
2295/// Matches MaskedGather Intrinsic.
2296template <typename Opnd0, typename Opnd1, typename Opnd2, typename Opnd3>
2297inline typename m_Intrinsic_Ty<Opnd0, Opnd1, Opnd2, Opnd3>::Ty
2298m_MaskedGather(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2,
2299 const Opnd3 &Op3) {
2300 return m_Intrinsic<Intrinsic::masked_gather>(Op0, Op1, Op2, Op3);
2301}
2302
2303template <Intrinsic::ID IntrID, typename T0>
2304inline typename m_Intrinsic_Ty<T0>::Ty m_Intrinsic(const T0 &Op0) {
2305 return m_CombineAnd(m_Intrinsic<IntrID>(), m_Argument<0>(Op0));
2306}
2307
2308template <Intrinsic::ID IntrID, typename T0, typename T1>
2309inline typename m_Intrinsic_Ty<T0, T1>::Ty m_Intrinsic(const T0 &Op0,
2310 const T1 &Op1) {
2311 return m_CombineAnd(m_Intrinsic<IntrID>(Op0), m_Argument<1>(Op1));
2312}
2313
2314template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2>
2315inline typename m_Intrinsic_Ty<T0, T1, T2>::Ty
2316m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2) {
2317 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1), m_Argument<2>(Op2));
2318}
2319
2320template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2,
2321 typename T3>
2322inline typename m_Intrinsic_Ty<T0, T1, T2, T3>::Ty
2323m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3) {
2324 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2), m_Argument<3>(Op3));
2325}
2326
2327template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2,
2328 typename T3, typename T4>
2329inline typename m_Intrinsic_Ty<T0, T1, T2, T3, T4>::Ty
2330m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3,
2331 const T4 &Op4) {
2332 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2, Op3),
2333 m_Argument<4>(Op4));
2334}
2335
2336template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2,
2337 typename T3, typename T4, typename T5>
2338inline typename m_Intrinsic_Ty<T0, T1, T2, T3, T4, T5>::Ty
2339m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3,
2340 const T4 &Op4, const T5 &Op5) {
2341 return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2, Op3, Op4),
2342 m_Argument<5>(Op5));
2343}
2344
2345// Helper intrinsic matching specializations.
2346template <typename Opnd0>
2347inline typename m_Intrinsic_Ty<Opnd0>::Ty m_BitReverse(const Opnd0 &Op0) {
2348 return m_Intrinsic<Intrinsic::bitreverse>(Op0);
2349}
2350
2351template <typename Opnd0>
2352inline typename m_Intrinsic_Ty<Opnd0>::Ty m_BSwap(const Opnd0 &Op0) {
2353 return m_Intrinsic<Intrinsic::bswap>(Op0);
2354}
2355
2356template <typename Opnd0>
2357inline typename m_Intrinsic_Ty<Opnd0>::Ty m_FAbs(const Opnd0 &Op0) {
2358 return m_Intrinsic<Intrinsic::fabs>(Op0);
2359}
2360
2361template <typename Opnd0>
2362inline typename m_Intrinsic_Ty<Opnd0>::Ty m_FCanonicalize(const Opnd0 &Op0) {
2363 return m_Intrinsic<Intrinsic::canonicalize>(Op0);
2364}
2365
2366template <typename Opnd0, typename Opnd1>
2367inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMin(const Opnd0 &Op0,
2368 const Opnd1 &Op1) {
2369 return m_Intrinsic<Intrinsic::minnum>(Op0, Op1);
2370}
2371
2372template <typename Opnd0, typename Opnd1>
2373inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMax(const Opnd0 &Op0,
2374 const Opnd1 &Op1) {
2375 return m_Intrinsic<Intrinsic::maxnum>(Op0, Op1);
2376}
2377
2378template <typename Opnd0, typename Opnd1, typename Opnd2>
2379inline typename m_Intrinsic_Ty<Opnd0, Opnd1, Opnd2>::Ty
2380m_FShl(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2) {
2381 return m_Intrinsic<Intrinsic::fshl>(Op0, Op1, Op2);
2382}
2383
2384template <typename Opnd0, typename Opnd1, typename Opnd2>
2385inline typename m_Intrinsic_Ty<Opnd0, Opnd1, Opnd2>::Ty
2386m_FShr(const Opnd0 &Op0, const Opnd1 &Op1, const Opnd2 &Op2) {
2387 return m_Intrinsic<Intrinsic::fshr>(Op0, Op1, Op2);
2388}
2389
2390template <typename Opnd0>
2391inline typename m_Intrinsic_Ty<Opnd0>::Ty m_Sqrt(const Opnd0 &Op0) {
2392 return m_Intrinsic<Intrinsic::sqrt>(Op0);
2393}
2394
2395template <typename Opnd0, typename Opnd1>
2396inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_CopySign(const Opnd0 &Op0,
2397 const Opnd1 &Op1) {
2398 return m_Intrinsic<Intrinsic::copysign>(Op0, Op1);
2399}
2400
2401template <typename Opnd0>
2402inline typename m_Intrinsic_Ty<Opnd0>::Ty m_VecReverse(const Opnd0 &Op0) {
2403 return m_Intrinsic<Intrinsic::experimental_vector_reverse>(Op0);
2404}
2405
2406//===----------------------------------------------------------------------===//
2407// Matchers for two-operands operators with the operators in either order
2408//
2409
2410/// Matches a BinaryOperator with LHS and RHS in either order.
2411template <typename LHS, typename RHS>
2412inline AnyBinaryOp_match<LHS, RHS, true> m_c_BinOp(const LHS &L, const RHS &R) {
2413 return AnyBinaryOp_match<LHS, RHS, true>(L, R);
2414}
2415
2416/// Matches an ICmp with a predicate over LHS and RHS in either order.
2417/// Swaps the predicate if operands are commuted.
2418template <typename LHS, typename RHS>
2419inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate, true>
2420m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
2421 return CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate, true>(Pred, L,
2422 R);
2423}
2424
2425/// Matches a specific opcode with LHS and RHS in either order.
2426template <typename LHS, typename RHS>
2427inline SpecificBinaryOp_match<LHS, RHS, true>
2428m_c_BinOp(unsigned Opcode, const LHS &L, const RHS &R) {
2429 return SpecificBinaryOp_match<LHS, RHS, true>(Opcode, L, R);
2430}
2431
2432/// Matches a Add with LHS and RHS in either order.
2433template <typename LHS, typename RHS>
2434inline BinaryOp_match<LHS, RHS, Instruction::Add, true> m_c_Add(const LHS &L,
2435 const RHS &R) {
2436 return BinaryOp_match<LHS, RHS, Instruction::Add, true>(L, R);
2437}
2438
2439/// Matches a Mul with LHS and RHS in either order.
2440template <typename LHS, typename RHS>
2441inline BinaryOp_match<LHS, RHS, Instruction::Mul, true> m_c_Mul(const LHS &L,
2442 const RHS &R) {
2443 return BinaryOp_match<LHS, RHS, Instruction::Mul, true>(L, R);
2444}
2445
2446/// Matches an And with LHS and RHS in either order.
2447template <typename LHS, typename RHS>
2448inline BinaryOp_match<LHS, RHS, Instruction::And, true> m_c_And(const LHS &L,
2449 const RHS &R) {
2450 return BinaryOp_match<LHS, RHS, Instruction::And, true>(L, R);
2451}
2452
2453/// Matches an Or with LHS and RHS in either order.
2454template <typename LHS, typename RHS>
2455inline BinaryOp_match<LHS, RHS, Instruction::Or, true> m_c_Or(const LHS &L,
2456 const RHS &R) {
2457 return BinaryOp_match<LHS, RHS, Instruction::Or, true>(L, R);
2458}
2459
2460/// Matches an Xor with LHS and RHS in either order.
2461template <typename LHS, typename RHS>
2462inline BinaryOp_match<LHS, RHS, Instruction::Xor, true> m_c_Xor(const LHS &L,
2463 const RHS &R) {
2464 return BinaryOp_match<LHS, RHS, Instruction::Xor, true>(L, R);
2465}
2466
2467/// Matches a 'Neg' as 'sub 0, V'.
2468template <typename ValTy>
2469inline BinaryOp_match<cst_pred_ty<is_zero_int>, ValTy, Instruction::Sub>
2470m_Neg(const ValTy &V) {
2471 return m_Sub(m_ZeroInt(), V);
2472}
2473
2474/// Matches a 'Neg' as 'sub nsw 0, V'.
2475template <typename ValTy>
2476inline OverflowingBinaryOp_match<cst_pred_ty<is_zero_int>, ValTy,
2477 Instruction::Sub,
2478 OverflowingBinaryOperator::NoSignedWrap>
2479m_NSWNeg(const ValTy &V) {
2480 return m_NSWSub(m_ZeroInt(), V);
2481}
2482
2483/// Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
2484/// NOTE: we first match the 'Not' (by matching '-1'),
2485/// and only then match the inner matcher!
2486template <typename ValTy>
2487inline BinaryOp_match<cst_pred_ty<is_all_ones>, ValTy, Instruction::Xor, true>
2488m_Not(const ValTy &V) {
2489 return m_c_Xor(m_AllOnes(), V);
2490}
2491
2492template <typename ValTy> struct NotForbidUndef_match {
2493 ValTy Val;
2494 NotForbidUndef_match(const ValTy &V) : Val(V) {}
2495
2496 template <typename OpTy> bool match(OpTy *V) {
2497 // We do not use m_c_Xor because that could match an arbitrary APInt that is
2498 // not -1 as C and then fail to match the other operand if it is -1.
2499 // This code should still work even when both operands are constants.
2500 Value *X;
2501 const APInt *C;
2502 if (m_Xor(L: m_Value(V&: X), R: m_APIntForbidUndef(Res&: C)).match(V) && C->isAllOnes())
2503 return Val.match(X);
2504 if (m_Xor(L: m_APIntForbidUndef(Res&: C), R: m_Value(V&: X)).match(V) && C->isAllOnes())
2505 return Val.match(X);
2506 return false;
2507 }
2508};
2509
2510/// Matches a bitwise 'not' as 'xor V, -1' or 'xor -1, V'. For vectors, the
2511/// constant value must be composed of only -1 scalar elements.
2512template <typename ValTy>
2513inline NotForbidUndef_match<ValTy> m_NotForbidUndef(const ValTy &V) {
2514 return NotForbidUndef_match<ValTy>(V);
2515}
2516
2517/// Matches an SMin with LHS and RHS in either order.
2518template <typename LHS, typename RHS>
2519inline MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>
2520m_c_SMin(const LHS &L, const RHS &R) {
2521 return MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>(L, R);
2522}
2523/// Matches an SMax with LHS and RHS in either order.
2524template <typename LHS, typename RHS>
2525inline MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true>
2526m_c_SMax(const LHS &L, const RHS &R) {
2527 return MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true>(L, R);
2528}
2529/// Matches a UMin with LHS and RHS in either order.
2530template <typename LHS, typename RHS>
2531inline MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true>
2532m_c_UMin(const LHS &L, const RHS &R) {
2533 return MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true>(L, R);
2534}
2535/// Matches a UMax with LHS and RHS in either order.
2536template <typename LHS, typename RHS>
2537inline MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true>
2538m_c_UMax(const LHS &L, const RHS &R) {
2539 return MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true>(L, R);
2540}
2541
2542template <typename LHS, typename RHS>
2543inline match_combine_or<
2544 match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true>,
2545 MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>>,
2546 match_combine_or<MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true>,
2547 MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true>>>
2548m_c_MaxOrMin(const LHS &L, const RHS &R) {
2549 return m_CombineOr(m_CombineOr(m_c_SMax(L, R), m_c_SMin(L, R)),
2550 m_CombineOr(m_c_UMax(L, R), m_c_UMin(L, R)));
2551}
2552
2553template <Intrinsic::ID IntrID, typename T0, typename T1>
2554inline match_combine_or<typename m_Intrinsic_Ty<T0, T1>::Ty,
2555 typename m_Intrinsic_Ty<T1, T0>::Ty>
2556m_c_Intrinsic(const T0 &Op0, const T1 &Op1) {
2557 return m_CombineOr(m_Intrinsic<IntrID>(Op0, Op1),
2558 m_Intrinsic<IntrID>(Op1, Op0));
2559}
2560
2561/// Matches FAdd with LHS and RHS in either order.
2562template <typename LHS, typename RHS>
2563inline BinaryOp_match<LHS, RHS, Instruction::FAdd, true>
2564m_c_FAdd(const LHS &L, const RHS &R) {
2565 return BinaryOp_match<LHS, RHS, Instruction::FAdd, true>(L, R);
2566}
2567
2568/// Matches FMul with LHS and RHS in either order.
2569template <typename LHS, typename RHS>
2570inline BinaryOp_match<LHS, RHS, Instruction::FMul, true>
2571m_c_FMul(const LHS &L, const RHS &R) {
2572 return BinaryOp_match<LHS, RHS, Instruction::FMul, true>(L, R);
2573}
2574
2575template <typename Opnd_t> struct Signum_match {
2576 Opnd_t Val;
2577 Signum_match(const Opnd_t &V) : Val(V) {}
2578
2579 template <typename OpTy> bool match(OpTy *V) {
2580 unsigned TypeSize = V->getType()->getScalarSizeInBits();
2581 if (TypeSize == 0)
2582 return false;
2583
2584 unsigned ShiftWidth = TypeSize - 1;
2585 Value *OpL = nullptr, *OpR = nullptr;
2586
2587 // This is the representation of signum we match:
2588 //
2589 // signum(x) == (x >> 63) | (-x >>u 63)
2590 //
2591 // An i1 value is its own signum, so it's correct to match
2592 //
2593 // signum(x) == (x >> 0) | (-x >>u 0)
2594 //
2595 // for i1 values.
2596
2597 auto LHS = m_AShr(L: m_Value(V&: OpL), R: m_SpecificInt(V: ShiftWidth));
2598 auto RHS = m_LShr(L: m_Neg(V: m_Value(V&: OpR)), R: m_SpecificInt(V: ShiftWidth));
2599 auto Signum = m_Or(L: LHS, R: RHS);
2600
2601 return Signum.match(V) && OpL == OpR && Val.match(OpL);
2602 }
2603};
2604
2605/// Matches a signum pattern.
2606///
2607/// signum(x) =
2608/// x > 0 -> 1
2609/// x == 0 -> 0
2610/// x < 0 -> -1
2611template <typename Val_t> inline Signum_match<Val_t> m_Signum(const Val_t &V) {
2612 return Signum_match<Val_t>(V);
2613}
2614
2615template <int Ind, typename Opnd_t> struct ExtractValue_match {
2616 Opnd_t Val;
2617 ExtractValue_match(const Opnd_t &V) : Val(V) {}
2618
2619 template <typename OpTy> bool match(OpTy *V) {
2620 if (auto *I = dyn_cast<ExtractValueInst>(V)) {
2621 // If Ind is -1, don't inspect indices
2622 if (Ind != -1 &&
2623 !(I->getNumIndices() == 1 && I->getIndices()[0] == (unsigned)Ind))
2624 return false;
2625 return Val.match(I->getAggregateOperand());
2626 }
2627 return false;
2628 }
2629};
2630
2631/// Match a single index ExtractValue instruction.
2632/// For example m_ExtractValue<1>(...)
2633template <int Ind, typename Val_t>
2634inline ExtractValue_match<Ind, Val_t> m_ExtractValue(const Val_t &V) {
2635 return ExtractValue_match<Ind, Val_t>(V);
2636}
2637
2638/// Match an ExtractValue instruction with any index.
2639/// For example m_ExtractValue(...)
2640template <typename Val_t>
2641inline ExtractValue_match<-1, Val_t> m_ExtractValue(const Val_t &V) {
2642 return ExtractValue_match<-1, Val_t>(V);
2643}
2644
2645/// Matcher for a single index InsertValue instruction.
2646template <int Ind, typename T0, typename T1> struct InsertValue_match {
2647 T0 Op0;
2648 T1 Op1;
2649
2650 InsertValue_match(const T0 &Op0, const T1 &Op1) : Op0(Op0), Op1(Op1) {}
2651
2652 template <typename OpTy> bool match(OpTy *V) {
2653 if (auto *I = dyn_cast<InsertValueInst>(V)) {
2654 return Op0.match(I->getOperand(0)) && Op1.match(I->getOperand(1)) &&
2655 I->getNumIndices() == 1 && Ind == I->getIndices()[0];
2656 }
2657 return false;
2658 }
2659};
2660
2661/// Matches a single index InsertValue instruction.
2662template <int Ind, typename Val_t, typename Elt_t>
2663inline InsertValue_match<Ind, Val_t, Elt_t> m_InsertValue(const Val_t &Val,
2664 const Elt_t &Elt) {
2665 return InsertValue_match<Ind, Val_t, Elt_t>(Val, Elt);
2666}
2667
2668/// Matches patterns for `vscale`. This can either be a call to `llvm.vscale` or
2669/// the constant expression
2670/// `ptrtoint(gep <vscale x 1 x i8>, <vscale x 1 x i8>* null, i32 1>`
2671/// under the right conditions determined by DataLayout.
2672struct VScaleVal_match {
2673 template <typename ITy> bool match(ITy *V) {
2674 if (m_Intrinsic<Intrinsic::vscale>().match(V))
2675 return true;
2676
2677 Value *Ptr;
2678 if (m_PtrToInt(Op: m_Value(V&: Ptr)).match(V)) {
2679 if (auto *GEP = dyn_cast<GEPOperator>(Val: Ptr)) {
2680 auto *DerefTy =
2681 dyn_cast<ScalableVectorType>(Val: GEP->getSourceElementType());
2682 if (GEP->getNumIndices() == 1 && DerefTy &&
2683 DerefTy->getElementType()->isIntegerTy(Bitwidth: 8) &&
2684 m_Zero().match(V: GEP->getPointerOperand()) &&
2685 m_SpecificInt(V: 1).match(V: GEP->idx_begin()->get()))
2686 return true;
2687 }
2688 }
2689
2690 return false;
2691 }
2692};
2693
2694inline VScaleVal_match m_VScale() {
2695 return VScaleVal_match();
2696}
2697
2698template <typename LHS, typename RHS, unsigned Opcode, bool Commutable = false>
2699struct LogicalOp_match {
2700 LHS L;
2701 RHS R;
2702
2703 LogicalOp_match(const LHS &L, const RHS &R) : L(L), R(R) {}
2704
2705 template <typename T> bool match(T *V) {
2706 auto *I = dyn_cast<Instruction>(V);
2707 if (!I || !I->getType()->isIntOrIntVectorTy(1))
2708 return false;
2709
2710 if (I->getOpcode() == Opcode) {
2711 auto *Op0 = I->getOperand(0);
2712 auto *Op1 = I->getOperand(1);
2713 return (L.match(Op0) && R.match(Op1)) ||
2714 (Commutable && L.match(Op1) && R.match(Op0));
2715 }
2716
2717 if (auto *Select = dyn_cast<SelectInst>(I)) {
2718 auto *Cond = Select->getCondition();
2719 auto *TVal = Select->getTrueValue();
2720 auto *FVal = Select->getFalseValue();
2721
2722 // Don't match a scalar select of bool vectors.
2723 // Transforms expect a single type for operands if this matches.
2724 if (Cond->getType() != Select->getType())
2725 return false;
2726
2727 if (Opcode == Instruction::And) {
2728 auto *C = dyn_cast<Constant>(FVal);
2729 if (C && C->isNullValue())
2730 return (L.match(Cond) && R.match(TVal)) ||
2731 (Commutable && L.match(TVal) && R.match(Cond));
2732 } else {
2733 assert(Opcode == Instruction::Or);
2734 auto *C = dyn_cast<Constant>(TVal);
2735 if (C && C->isOneValue())
2736 return (L.match(Cond) && R.match(FVal)) ||
2737 (Commutable && L.match(FVal) && R.match(Cond));
2738 }
2739 }
2740
2741 return false;
2742 }
2743};
2744
2745/// Matches L && R either in the form of L & R or L ? R : false.
2746/// Note that the latter form is poison-blocking.
2747template <typename LHS, typename RHS>
2748inline LogicalOp_match<LHS, RHS, Instruction::And> m_LogicalAnd(const LHS &L,
2749 const RHS &R) {
2750 return LogicalOp_match<LHS, RHS, Instruction::And>(L, R);
2751}
2752
2753/// Matches L && R where L and R are arbitrary values.
2754inline auto m_LogicalAnd() { return m_LogicalAnd(L: m_Value(), R: m_Value()); }
2755
2756/// Matches L && R with LHS and RHS in either order.
2757template <typename LHS, typename RHS>
2758inline LogicalOp_match<LHS, RHS, Instruction::And, true>
2759m_c_LogicalAnd(const LHS &L, const RHS &R) {
2760 return LogicalOp_match<LHS, RHS, Instruction::And, true>(L, R);
2761}
2762
2763/// Matches L || R either in the form of L | R or L ? true : R.
2764/// Note that the latter form is poison-blocking.
2765template <typename LHS, typename RHS>
2766inline LogicalOp_match<LHS, RHS, Instruction::Or> m_LogicalOr(const LHS &L,
2767 const RHS &R) {
2768 return LogicalOp_match<LHS, RHS, Instruction::Or>(L, R);
2769}
2770
2771/// Matches L || R where L and R are arbitrary values.
2772inline auto m_LogicalOr() { return m_LogicalOr(L: m_Value(), R: m_Value()); }
2773
2774/// Matches L || R with LHS and RHS in either order.
2775template <typename LHS, typename RHS>
2776inline LogicalOp_match<LHS, RHS, Instruction::Or, true>
2777m_c_LogicalOr(const LHS &L, const RHS &R) {
2778 return LogicalOp_match<LHS, RHS, Instruction::Or, true>(L, R);
2779}
2780
2781/// Matches either L && R or L || R,
2782/// either one being in the either binary or logical form.
2783/// Note that the latter form is poison-blocking.
2784template <typename LHS, typename RHS, bool Commutable = false>
2785inline auto m_LogicalOp(const LHS &L, const RHS &R) {
2786 return m_CombineOr(
2787 LogicalOp_match<LHS, RHS, Instruction::And, Commutable>(L, R),
2788 LogicalOp_match<LHS, RHS, Instruction::Or, Commutable>(L, R));
2789}
2790
2791/// Matches either L && R or L || R where L and R are arbitrary values.
2792inline auto m_LogicalOp() { return m_LogicalOp(L: m_Value(), R: m_Value()); }
2793
2794/// Matches either L && R or L || R with LHS and RHS in either order.
2795template <typename LHS, typename RHS>
2796inline auto m_c_LogicalOp(const LHS &L, const RHS &R) {
2797 return m_LogicalOp<LHS, RHS, /*Commutable=*/true>(L, R);
2798}
2799
2800} // end namespace PatternMatch
2801} // end namespace llvm
2802
2803#endif // LLVM_IR_PATTERNMATCH_H
2804

source code of llvm/include/llvm/IR/PatternMatch.h