PatternMatch.h source code [llvm_projects/llvm/include/llvm/IR/PatternMatch.h]

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

Browse the source code of llvm_projects/llvm/include/llvm/IR/PatternMatch.h