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

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