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