Line data Source code
1 : //===- PatternMatch.h - Match on the LLVM IR --------------------*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This file provides a simple and efficient mechanism for performing general
11 : // tree-based pattern matches on the LLVM IR. The power of these routines is
12 : // that it allows you to write concise patterns that are expressive and easy to
13 : // understand. The other major advantage of this is that it allows you to
14 : // trivially capture/bind elements in the pattern to variables. For example,
15 : // you can do something like this:
16 : //
17 : // Value *Exp = ...
18 : // Value *X, *Y; ConstantInt *C1, *C2; // (X & C1) | (Y & C2)
19 : // if (match(Exp, m_Or(m_And(m_Value(X), m_ConstantInt(C1)),
20 : // m_And(m_Value(Y), m_ConstantInt(C2))))) {
21 : // ... Pattern is matched and variables are bound ...
22 : // }
23 : //
24 : // This is primarily useful to things like the instruction combiner, but can
25 : // also be useful for static analysis tools or code generators.
26 : //
27 : //===----------------------------------------------------------------------===//
28 :
29 : #ifndef LLVM_IR_PATTERNMATCH_H
30 : #define LLVM_IR_PATTERNMATCH_H
31 :
32 : #include "llvm/ADT/APFloat.h"
33 : #include "llvm/ADT/APInt.h"
34 : #include "llvm/IR/CallSite.h"
35 : #include "llvm/IR/Constant.h"
36 : #include "llvm/IR/Constants.h"
37 : #include "llvm/IR/InstrTypes.h"
38 : #include "llvm/IR/Instruction.h"
39 : #include "llvm/IR/Instructions.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 0 : template <typename Val, typename Pattern> bool match(Val *V, const Pattern &P) {
50 418816933 : return const_cast<Pattern &>(P).match(V);
51 : }
52 0 :
53 0 : template <typename SubPattern_t> struct OneUse_match {
54 : SubPattern_t SubPattern;
55 0 :
56 793120 : OneUse_match(const SubPattern_t &SP) : SubPattern(SP) {}
57 :
58 22038113 : template <typename OpTy> bool match(OpTy *V) {
59 22746182 : return V->hasOneUse() && SubPattern.match(V);
60 : }
61 2038621 : };
62 2038621 :
63 : template <typename T> inline OneUse_match<T> m_OneUse(const T &SubPattern) {
64 6282370 : return SubPattern;
65 6372888 : }
66 :
67 5101540 : template <typename Class> struct class_match {
68 5101540 : template <typename ITy> bool match(ITy *V) { return isa<Class>(V); }
69 : };
70 277002 :
71 277002 : /// Match an arbitrary value and ignore it.
72 : inline class_match<Value> m_Value() { return class_match<Value>(); }
73 53728 :
74 53728 : /// Match an arbitrary binary operation and ignore it.
75 0 : inline class_match<BinaryOperator> m_BinOp() {
76 542687 : return class_match<BinaryOperator>();
77 562560 : }
78 0 :
79 1761373 : /// Matches any compare instruction and ignore it.
80 1814296 : inline class_match<CmpInst> m_Cmp() { return class_match<CmpInst>(); }
81 0 :
82 822614 : /// Match an arbitrary ConstantInt and ignore it.
83 822614 : inline class_match<ConstantInt> m_ConstantInt() {
84 : return class_match<ConstantInt>();
85 193509 : }
86 193509 :
87 : /// Match an arbitrary undef constant.
88 606723 : inline class_match<UndefValue> m_Undef() { return class_match<UndefValue>(); }
89 606723 :
90 : /// Match an arbitrary Constant and ignore it.
91 540391 : inline class_match<Constant> m_Constant() { return class_match<Constant>(); }
92 540391 :
93 : /// Matching combinators
94 336389 : template <typename LTy, typename RTy> struct match_combine_or {
95 336389 : LTy L;
96 : RTy R;
97 84845 :
98 84845 : match_combine_or(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
99 :
100 126133 : template <typename ITy> bool match(ITy *V) {
101 126133 : if (L.match(V))
102 : return true;
103 5154175 : if (R.match(V))
104 5148971 : return true;
105 : return false;
106 91273 : }
107 91434 : };
108 0 :
109 86640 : template <typename LTy, typename RTy> struct match_combine_and {
110 218281 : LTy L;
111 0 : RTy R;
112 264594 :
113 133867 : match_combine_and(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
114 0 :
115 70003 : template <typename ITy> bool match(ITy *V) {
116 65477 : if (L.match(V))
117 204 : if (R.match(V))
118 218513 : return true;
119 218309 : return false;
120 0 : }
121 71213 : };
122 71861 :
123 8718 : /// Combine two pattern matchers matching L || R
124 1161710 : template <typename LTy, typename RTy>
125 238419 : inline match_combine_or<LTy, RTy> m_CombineOr(const LTy &L, const RTy &R) {
126 8551 : return match_combine_or<LTy, RTy>(L, R);
127 8564 : }
128 8511 :
129 : /// Combine two pattern matchers matching L && R
130 4021 : template <typename LTy, typename RTy>
131 4003 : inline match_combine_and<LTy, RTy> m_CombineAnd(const LTy &L, const RTy &R) {
132 46 : return match_combine_and<LTy, RTy>(L, R);
133 20067 : }
134 31085 :
135 0 : struct apint_match {
136 157260 : const APInt *&Res;
137 158784 :
138 1693 : apint_match(const APInt *&R) : Res(R) {}
139 136014 :
140 8545151 : template <typename ITy> bool match(ITy *V) {
141 926 : if (auto *CI = dyn_cast<ConstantInt>(V)) {
142 7461214 : Res = &CI->getValue();
143 7472278 : return true;
144 11092 : }
145 4351930 : if (V->getType()->isVectorTy())
146 42077 : if (const auto *C = dyn_cast<Constant>(V))
147 325053 : if (auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue())) {
148 1307597 : Res = &CI->getValue();
149 391723 : return true;
150 126190 : }
151 180686 : return false;
152 54482 : }
153 124982 : };
154 185 : // Either constexpr if or renaming ConstantFP::getValueAPF to
155 15 : // ConstantFP::getValue is needed to do it via single template
156 0 : // function for both apint/apfloat.
157 0 : struct apfloat_match {
158 0 : const APFloat *&Res;
159 0 : apfloat_match(const APFloat *&R) : Res(R) {}
160 55083 : template <typename ITy> bool match(ITy *V) {
161 1862825 : if (auto *CI = dyn_cast<ConstantFP>(V)) {
162 150 : Res = &CI->getValueAPF();
163 1009454 : return true;
164 1011890 : }
165 846 : if (V->getType()->isVectorTy())
166 10377291 : if (const auto *C = dyn_cast<Constant>(V))
167 54823 : if (auto *CI = dyn_cast_or_null<ConstantFP>(C->getSplatValue())) {
168 6646856 : Res = &CI->getValueAPF();
169 6649500 : return true;
170 100170 : }
171 3679607 : return false;
172 3820 : }
173 423556 : };
174 319303 :
175 319176 : /// Match a ConstantInt or splatted ConstantVector, binding the
176 0 : /// specified pointer to the contained APInt.
177 0 : inline apint_match m_APInt(const APInt *&Res) { return Res; }
178 0 :
179 0 : /// Match a ConstantFP or splatted ConstantVector, binding the
180 0 : /// specified pointer to the contained APFloat.
181 0 : inline apfloat_match m_APFloat(const APFloat *&Res) { return Res; }
182 0 :
183 0 : template <int64_t Val> struct constantint_match {
184 97400 : template <typename ITy> bool match(ITy *V) {
185 96888 : if (const auto *CI = dyn_cast<ConstantInt>(V)) {
186 9 : const APInt &CIV = CI->getValue();
187 1904683 : if (Val >= 0)
188 72 : return CIV == static_cast<uint64_t>(Val);
189 912945 : // If Val is negative, and CI is shorter than it, truncate to the right
190 914952 : // number of bits. If it is larger, then we have to sign extend. Just
191 0 : // compare their negated values.
192 1790813 : return -CIV == -Val;
193 73 : }
194 4032 : return false;
195 6664 : }
196 3368 : };
197 13 :
198 96845 : /// Match a ConstantInt with a specific value.
199 96811 : template <int64_t Val> inline constantint_match<Val> m_ConstantInt() {
200 0 : return constantint_match<Val>();
201 96287 : }
202 30996 :
203 111112 : /// This helper class is used to match scalar and vector integer constants that
204 0 : /// satisfy a specified predicate.
205 418865 : /// For vector constants, undefined elements are ignored.
206 116467645 : template <typename Predicate> struct cst_pred_ty : public Predicate {
207 12573020 : template <typename ITy> bool match(ITy *V) {
208 38384501 : if (const auto *CI = dyn_cast<ConstantInt>(V))
209 38045199 : return this->isValue(CI->getValue());
210 1956133 : if (V->getType()->isVectorTy()) {
211 156020542 : if (const auto *C = dyn_cast<Constant>(V)) {
212 553662 : if (const auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue()))
213 817148 : return this->isValue(CI->getValue());
214 798496 :
215 798325 : // Non-splat vector constant: check each element for a match.
216 4816 : unsigned NumElts = V->getType()->getVectorNumElements();
217 : assert(NumElts != 0 && "Constant vector with no elements?");
218 988714 : for (unsigned i = 0; i != NumElts; ++i) {
219 6902 : Constant *Elt = C->getAggregateElement(i);
220 5075 : if (!Elt)
221 96802 : return false;
222 5060 : if (isa<UndefValue>(Elt))
223 0 : continue;
224 0 : auto *CI = dyn_cast<ConstantInt>(Elt);
225 5464 : if (!CI || !this->isValue(CI->getValue()))
226 0 : return false;
227 144562 : }
228 1628 : return true;
229 255674 : }
230 2720 : }
231 98489 : return false;
232 98489 : }
233 19 : };
234 25326 :
235 0 : /// This helper class is used to match scalar and vector constants that
236 679 : /// satisfy a specified predicate, and bind them to an APInt.
237 572 : template <typename Predicate> struct api_pred_ty : public Predicate {
238 572 : const APInt *&Res;
239 132 :
240 0 : api_pred_ty(const APInt *&R) : Res(R) {}
241 0 :
242 1377 : template <typename ITy> bool match(ITy *V) {
243 0 : if (const auto *CI = dyn_cast<ConstantInt>(V))
244 1090 : if (this->isValue(CI->getValue())) {
245 116049474 : Res = &CI->getValue();
246 865 : return true;
247 38038795 : }
248 38086067 : if (V->getType()->isVectorTy())
249 18 : if (const auto *C = dyn_cast<Constant>(V))
250 156019970 : if (auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue()))
251 53562 : if (this->isValue(CI->getValue())) {
252 817013 : Res = &CI->getValue();
253 798272 : return true;
254 2214388 : }
255 0 :
256 73811 : return false;
257 199543 : }
258 0 : };
259 695195 :
260 45297 : /// This helper class is used to match scalar and vector floating-point
261 103 : /// constants that satisfy a specified predicate.
262 710315 : /// For vector constants, undefined elements are ignored.
263 1350370 : template <typename Predicate> struct cstfp_pred_ty : public Predicate {
264 13818 : template <typename ITy> bool match(ITy *V) {
265 588185 : if (const auto *CF = dyn_cast<ConstantFP>(V))
266 572694 : return this->isValue(CF->getValueAPF());
267 2777 : if (V->getType()->isVectorTy()) {
268 1483499 : if (const auto *C = dyn_cast<Constant>(V)) {
269 2371 : if (const auto *CF = dyn_cast_or_null<ConstantFP>(C->getSplatValue()))
270 5980 : return this->isValue(CF->getValueAPF());
271 5187 :
272 7276 : // Non-splat vector constant: check each element for a match.
273 14 : unsigned NumElts = V->getType()->getVectorNumElements();
274 1717 : assert(NumElts != 0 && "Constant vector with no elements?");
275 42 : for (unsigned i = 0; i != NumElts; ++i) {
276 28 : Constant *Elt = C->getAggregateElement(i);
277 2333 : if (!Elt)
278 0 : return false;
279 28 : if (isa<UndefValue>(Elt))
280 1628 : continue;
281 0 : auto *CF = dyn_cast<ConstantFP>(Elt);
282 14 : if (!CF || !this->isValue(CF->getValueAPF()))
283 191 : return false;
284 0 : }
285 11706564 : return true;
286 45355 : }
287 0 : }
288 1043388 : return false;
289 1348409 : }
290 497589 : };
291 585822 :
292 570157 : ///////////////////////////////////////////////////////////////////////////////
293 94 : //
294 1485231 : // Encapsulate constant value queries for use in templated predicate matchers.
295 71 : // This allows checking if constants match using compound predicates and works
296 331258 : // with vector constants, possibly with relaxed constraints. For example, ignore
297 6747 : // undef values.
298 6828 : //
299 263834 : ///////////////////////////////////////////////////////////////////////////////
300 5561 :
301 1345 : struct is_all_ones {
302 0 : bool isValue(const APInt &C) { return C.isAllOnesValue(); }
303 3232 : };
304 : /// Match an integer or vector with all bits set.
305 459 : /// For vectors, this includes constants with undefined elements.
306 0 : inline cst_pred_ty<is_all_ones> m_AllOnes() {
307 643 : return cst_pred_ty<is_all_ones>();
308 604 : }
309 727 :
310 0 : struct is_maxsignedvalue {
311 164530 : bool isValue(const APInt &C) { return C.isMaxSignedValue(); }
312 19035 : };
313 4353 : /// Match an integer or vector with values having all bits except for the high
314 294651 : /// bit set (0x7f...).
315 21731 : /// For vectors, this includes constants with undefined elements.
316 3512 : inline cst_pred_ty<is_maxsignedvalue> m_MaxSignedValue() {
317 372 : return cst_pred_ty<is_maxsignedvalue>();
318 208 : }
319 364 : inline api_pred_ty<is_maxsignedvalue> m_MaxSignedValue(const APInt *&V) {
320 91 : return V;
321 109 : }
322 173 :
323 225 : struct is_negative {
324 224 : bool isValue(const APInt &C) { return C.isNegative(); }
325 110 : };
326 126 : /// Match an integer or vector of negative values.
327 140 : /// For vectors, this includes constants with undefined elements.
328 29 : inline cst_pred_ty<is_negative> m_Negative() {
329 137 : return cst_pred_ty<is_negative>();
330 40 : }
331 28 : inline api_pred_ty<is_negative> m_Negative(const APInt *&V) {
332 0 : return V;
333 0 : }
334 14 :
335 76 : struct is_nonnegative {
336 0 : bool isValue(const APInt &C) { return C.isNonNegative(); }
337 1 : };
338 4037 : /// Match an integer or vector of nonnegative values.
339 1 : /// For vectors, this includes constants with undefined elements.
340 7 : inline cst_pred_ty<is_nonnegative> m_NonNegative() {
341 1800 : return cst_pred_ty<is_nonnegative>();
342 0 : }
343 286 : inline api_pred_ty<is_nonnegative> m_NonNegative(const APInt *&V) {
344 1 : return V;
345 0 : }
346 3 :
347 51 : struct is_one {
348 320462 : bool isValue(const APInt &C) { return C.isOneValue(); }
349 67 : };
350 68 : /// Match an integer 1 or a vector with all elements equal to 1.
351 258170 : /// For vectors, this includes constants with undefined elements.
352 14998 : inline cst_pred_ty<is_one> m_One() {
353 7401 : return cst_pred_ty<is_one>();
354 0 : }
355 1285 :
356 110011 : struct is_zero_int {
357 702 : bool isValue(const APInt &C) { return C.isNullValue(); }
358 1291627 : };
359 112280 : /// Match an integer 0 or a vector with all elements equal to 0.
360 598 : /// For vectors, this includes constants with undefined elements.
361 16638 : inline cst_pred_ty<is_zero_int> m_ZeroInt() {
362 120 : return cst_pred_ty<is_zero_int>();
363 7556 : }
364 114 :
365 175 : struct is_zero {
366 557 : template <typename ITy> bool match(ITy *V) {
367 2070 : auto *C = dyn_cast<Constant>(V);
368 300 : return C && (C->isNullValue() || cst_pred_ty<is_zero_int>().match(C));
369 2370 : }
370 2341 : };
371 2494 : /// Match any null constant or a vector with all elements equal to 0.
372 0 : /// For vectors, this includes constants with undefined elements.
373 2201 : inline is_zero m_Zero() {
374 129 : return is_zero();
375 0 : }
376 2112 :
377 7 : struct is_power2 {
378 29719 : bool isValue(const APInt &C) { return C.isPowerOf2(); }
379 21 : };
380 14 : /// Match an integer or vector power-of-2.
381 52172 : /// For vectors, this includes constants with undefined elements.
382 0 : inline cst_pred_ty<is_power2> m_Power2() {
383 245 : return cst_pred_ty<is_power2>();
384 7372 : }
385 0 : inline api_pred_ty<is_power2> m_Power2(const APInt *&V) {
386 33 : return V;
387 14698 : }
388 0 :
389 36 : struct is_power2_or_zero {
390 12 : bool isValue(const APInt &C) { return !C || C.isPowerOf2(); }
391 6 : };
392 0 : /// Match an integer or vector of 0 or power-of-2 values.
393 9 : /// For vectors, this includes constants with undefined elements.
394 0 : inline cst_pred_ty<is_power2_or_zero> m_Power2OrZero() {
395 9 : return cst_pred_ty<is_power2_or_zero>();
396 13 : }
397 7 : inline api_pred_ty<is_power2_or_zero> m_Power2OrZero(const APInt *&V) {
398 0 : return V;
399 7 : }
400 3431 :
401 0 : struct is_sign_mask {
402 6 : bool isValue(const APInt &C) { return C.isSignMask(); }
403 5730 : };
404 0 : /// Match an integer or vector with only the sign bit(s) set.
405 5806 : /// For vectors, this includes constants with undefined elements.
406 0 : inline cst_pred_ty<is_sign_mask> m_SignMask() {
407 0 : return cst_pred_ty<is_sign_mask>();
408 107795 : }
409 3 :
410 108736 : struct is_lowbit_mask {
411 111179 : bool isValue(const APInt &C) { return C.isMask(); }
412 6 : };
413 136096 : /// Match an integer or vector with only the low bit(s) set.
414 116 : /// For vectors, this includes constants with undefined elements.
415 41 : inline cst_pred_ty<is_lowbit_mask> m_LowBitMask() {
416 46 : return cst_pred_ty<is_lowbit_mask>();
417 50 : }
418 7 :
419 239 : struct is_nan {
420 248 : bool isValue(const APFloat &C) { return C.isNaN(); }
421 130 : };
422 86 : /// Match an arbitrary NaN constant. This includes quiet and signalling nans.
423 271 : /// For vectors, this includes constants with undefined elements.
424 0 : inline cstfp_pred_ty<is_nan> m_NaN() {
425 35 : return cstfp_pred_ty<is_nan>();
426 104 : }
427 0 :
428 16 : struct is_any_zero_fp {
429 7 : bool isValue(const APFloat &C) { return C.isZero(); }
430 0 : };
431 185 : /// Match a floating-point negative zero or positive zero.
432 14 : /// For vectors, this includes constants with undefined elements.
433 52847 : inline cstfp_pred_ty<is_any_zero_fp> m_AnyZeroFP() {
434 4 : return cstfp_pred_ty<is_any_zero_fp>();
435 10455 : }
436 175120 :
437 0 : struct is_pos_zero_fp {
438 75877 : bool isValue(const APFloat &C) { return C.isPosZero(); }
439 34819 : };
440 0 : /// Match a floating-point positive zero.
441 9430 : /// For vectors, this includes constants with undefined elements.
442 555 : inline cstfp_pred_ty<is_pos_zero_fp> m_PosZeroFP() {
443 3163 : return cstfp_pred_ty<is_pos_zero_fp>();
444 12521 : }
445 490 :
446 491 : struct is_neg_zero_fp {
447 80 : bool isValue(const APFloat &C) { return C.isNegZero(); }
448 494 : };
449 53 : /// Match a floating-point negative zero.
450 27 : /// For vectors, this includes constants with undefined elements.
451 435 : inline cstfp_pred_ty<is_neg_zero_fp> m_NegZeroFP() {
452 35 : return cstfp_pred_ty<is_neg_zero_fp>();
453 33 : }
454 82 :
455 0 : ///////////////////////////////////////////////////////////////////////////////
456 33 :
457 6 : template <typename Class> struct bind_ty {
458 0 : Class *&VR;
459 35 :
460 9 : bind_ty(Class *&V) : VR(V) {}
461 0 :
462 4 : template <typename ITy> bool match(ITy *V) {
463 208093 : if (auto *CV = dyn_cast<Class>(V)) {
464 291337 : VR = CV;
465 12999 : return true;
466 2 : }
467 17810 : return false;
468 12598 : }
469 14229 : };
470 18424 :
471 822 : /// Match a value, capturing it if we match.
472 48 : inline bind_ty<Value> m_Value(Value *&V) { return V; }
473 81 : inline bind_ty<const Value> m_Value(const Value *&V) { return V; }
474 54 :
475 650 : /// Match an instruction, capturing it if we match.
476 145062 : inline bind_ty<Instruction> m_Instruction(Instruction *&I) { return I; }
477 0 : /// Match a binary operator, capturing it if we match.
478 34 : inline bind_ty<BinaryOperator> m_BinOp(BinaryOperator *&I) { return I; }
479 31 :
480 31 : /// Match a ConstantInt, capturing the value if we match.
481 30 : inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
482 71 :
483 5 : /// Match a Constant, capturing the value if we match.
484 0 : inline bind_ty<Constant> m_Constant(Constant *&C) { return C; }
485 32 :
486 2194 : /// Match a ConstantFP, capturing the value if we match.
487 0 : inline bind_ty<ConstantFP> m_ConstantFP(ConstantFP *&C) { return C; }
488 4 :
489 526 : /// Match a specified Value*.
490 21964 : struct specificval_ty {
491 58 : const Value *Val;
492 2 :
493 0 : specificval_ty(const Value *V) : Val(V) {}
494 10 :
495 23 : template <typename ITy> bool match(ITy *V) { return V == Val; }
496 8 : };
497 13046 :
498 44 : /// Match if we have a specific specified value.
499 13180 : inline specificval_ty m_Specific(const Value *V) { return V; }
500 12588 :
501 12631 : /// Stores a reference to the Value *, not the Value * itself,
502 0 : /// thus can be used in commutative matchers.
503 822 : template <typename Class> struct deferredval_ty {
504 25 : Class *const &Val;
505 61 :
506 54 : deferredval_ty(Class *const &V) : Val(V) {}
507 54 :
508 54 : template <typename ITy> bool match(ITy *const V) { return V == Val; }
509 43059 : };
510 0 :
511 35039 : /// A commutative-friendly version of m_Specific().
512 68174 : inline deferredval_ty<Value> m_Deferred(Value *const &V) { return V; }
513 6502 : inline deferredval_ty<const Value> m_Deferred(const Value *const &V) {
514 42507 : return V;
515 3071 : }
516 4734 :
517 606 : /// Match a specified floating point value or vector of all elements of
518 346 : /// that value.
519 104743 : struct specific_fpval {
520 717 : double Val;
521 14894 :
522 181290 : specific_fpval(double V) : Val(V) {}
523 210 :
524 3629 : template <typename ITy> bool match(ITy *V) {
525 2388 : if (const auto *CFP = dyn_cast<ConstantFP>(V))
526 222 : return CFP->isExactlyValue(Val);
527 430 : if (V->getType()->isVectorTy())
528 518 : if (const auto *C = dyn_cast<Constant>(V))
529 189 : if (auto *CFP = dyn_cast_or_null<ConstantFP>(C->getSplatValue()))
530 618 : return CFP->isExactlyValue(Val);
531 596 : return false;
532 596 : }
533 0 : };
534 1430 :
535 22 : /// Match a specific floating point value or vector with all elements
536 0 : /// equal to the value.
537 27208 : inline specific_fpval m_SpecificFP(double V) { return specific_fpval(V); }
538 0 :
539 3939 : /// Match a float 1.0 or vector with all elements equal to 1.0.
540 45456 : inline specific_fpval m_FPOne() { return m_SpecificFP(1.0); }
541 2 :
542 1318 : struct bind_const_intval_ty {
543 1111 : uint64_t &VR;
544 0 :
545 1312 : bind_const_intval_ty(uint64_t &V) : VR(V) {}
546 40589 :
547 7 : template <typename ITy> bool match(ITy *V) {
548 2599 : if (const auto *CV = dyn_cast<ConstantInt>(V))
549 15101 : if (CV->getValue().ule(UINT64_MAX)) {
550 231 : VR = CV->getZExtValue();
551 25 : return true;
552 247 : }
553 0 : return false;
554 366 : }
555 214 : };
556 159 :
557 21 : /// Match a specified integer value or vector of all elements of that
558 19 : // value.
559 17 : struct specific_intval {
560 728 : uint64_t Val;
561 42538 :
562 17 : specific_intval(uint64_t V) : Val(V) {}
563 8760 :
564 67560 : template <typename ITy> bool match(ITy *V) {
565 1 : const auto *CI = dyn_cast<ConstantInt>(V);
566 3163 : if (!CI && V->getType()->isVectorTy())
567 2822 : if (const auto *C = dyn_cast<Constant>(V))
568 0 : CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue());
569 0 :
570 1018 : return CI && CI->getValue() == Val;
571 8 : }
572 6115 : };
573 732 :
574 3308 : /// Match a specific integer value or vector with all elements equal to
575 4974 : /// the value.
576 1263 : inline specific_intval m_SpecificInt(uint64_t V) { return specific_intval(V); }
577 18 :
578 22 : /// Match a ConstantInt and bind to its value. This does not match
579 347 : /// ConstantInts wider than 64-bits.
580 7 : inline bind_const_intval_ty m_ConstantInt(uint64_t &V) { return V; }
581 14 :
582 3 : //===----------------------------------------------------------------------===//
583 16 : // Matcher for any binary operator.
584 15 : //
585 13 : template <typename LHS_t, typename RHS_t, bool Commutable = false>
586 2 : struct AnyBinaryOp_match {
587 452 : LHS_t L;
588 0 : RHS_t R;
589 124 :
590 7114 : // The evaluation order is always stable, regardless of Commutability.
591 2448 : // The LHS is always matched first.
592 27296 : AnyBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
593 10597 :
594 0 : template <typename OpTy> bool match(OpTy *V) {
595 461 : if (auto *I = dyn_cast<BinaryOperator>(V))
596 344 : return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
597 115 : (Commutable && L.match(I->getOperand(1)) &&
598 7 : R.match(I->getOperand(0)));
599 157 : return false;
600 84 : }
601 27 : };
602 689 :
603 93 : template <typename LHS, typename RHS>
604 516 : inline AnyBinaryOp_match<LHS, RHS> m_BinOp(const LHS &L, const RHS &R) {
605 424 : return AnyBinaryOp_match<LHS, RHS>(L, R);
606 275 : }
607 2 :
608 816 : //===----------------------------------------------------------------------===//
609 12 : // Matchers for specific binary operators.
610 19 : //
611 6 :
612 10 : template <typename LHS_t, typename RHS_t, unsigned Opcode,
613 6 : bool Commutable = false>
614 0 : struct BinaryOp_match {
615 2 : LHS_t L;
616 : RHS_t R;
617 0 :
618 69 : // The evaluation order is always stable, regardless of Commutability.
619 19286 : // The LHS is always matched first.
620 77586 : BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
621 0 :
622 214206 : template <typename OpTy> bool match(OpTy *V) {
623 214213 : if (V->getValueID() == Value::InstructionVal + Opcode) {
624 89 : auto *I = cast<BinaryOperator>(V);
625 5789 : return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
626 12 : (Commutable && L.match(I->getOperand(1)) &&
627 24 : R.match(I->getOperand(0)));
628 2 : }
629 412 : if (auto *CE = dyn_cast<ConstantExpr>(V))
630 950 : return CE->getOpcode() == Opcode &&
631 84 : ((L.match(CE->getOperand(0)) && R.match(CE->getOperand(1))) ||
632 18 : (Commutable && L.match(CE->getOperand(1)) &&
633 31 : R.match(CE->getOperand(0))));
634 71 : return false;
635 14 : }
636 344135 : };
637 344281 :
638 0 : template <typename LHS, typename RHS>
639 1214 : inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L,
640 71 : const RHS &R) {
641 2 : return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);
642 6 : }
643 229332 :
644 229332 : template <typename LHS, typename RHS>
645 0 : inline BinaryOp_match<LHS, RHS, Instruction::FAdd> m_FAdd(const LHS &L,
646 29917 : const RHS &R) {
647 0 : return BinaryOp_match<LHS, RHS, Instruction::FAdd>(L, R);
648 879 : }
649 6348 :
650 366654 : template <typename LHS, typename RHS>
651 368984 : inline BinaryOp_match<LHS, RHS, Instruction::Sub> m_Sub(const LHS &L,
652 6480 : const RHS &R) {
653 7390 : return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R);
654 70 : }
655 45 :
656 2 : template <typename LHS, typename RHS>
657 229153 : inline BinaryOp_match<LHS, RHS, Instruction::FSub> m_FSub(const LHS &L,
658 229189 : const RHS &R) {
659 1 : return BinaryOp_match<LHS, RHS, Instruction::FSub>(L, R);
660 29982 : }
661 72 :
662 367304 : /// Match 'fneg X' as 'fsub -0.0, X'.
663 367232 : template <typename RHS>
664 9042 : inline BinaryOp_match<cstfp_pred_ty<is_neg_zero_fp>, RHS, Instruction::FSub>
665 29441 : m_FNeg(const RHS &X) {
666 0 : return m_FSub(m_NegZeroFP(), X);
667 71 : }
668 0 :
669 0 : /// Match 'fneg X' as 'fsub +-0.0, X'.
670 2 : template <typename RHS>
671 132 : inline BinaryOp_match<cstfp_pred_ty<is_any_zero_fp>, RHS, Instruction::FSub>
672 132 : m_FNegNSZ(const RHS &X) {
673 0 : return m_FSub(m_AnyZeroFP(), X);
674 0 : }
675 99144 :
676 2408 : template <typename LHS, typename RHS>
677 14527 : inline BinaryOp_match<LHS, RHS, Instruction::Mul> m_Mul(const LHS &L,
678 209726 : const RHS &R) {
679 35820 : return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R);
680 2864 : }
681 2736 :
682 0 : template <typename LHS, typename RHS>
683 9 : inline BinaryOp_match<LHS, RHS, Instruction::FMul> m_FMul(const LHS &L,
684 508 : const RHS &R) {
685 49 : return BinaryOp_match<LHS, RHS, Instruction::FMul>(L, R);
686 579 : }
687 530 :
688 31204 : template <typename LHS, typename RHS>
689 27292 : inline BinaryOp_match<LHS, RHS, Instruction::UDiv> m_UDiv(const LHS &L,
690 775404 : const RHS &R) {
691 3113 : return BinaryOp_match<LHS, RHS, Instruction::UDiv>(L, R);
692 848751 : }
693 849334 :
694 36 : template <typename LHS, typename RHS>
695 5178 : inline BinaryOp_match<LHS, RHS, Instruction::SDiv> m_SDiv(const LHS &L,
696 2384 : const RHS &R) {
697 4 : return BinaryOp_match<LHS, RHS, Instruction::SDiv>(L, R);
698 0 : }
699 0 :
700 5348 : template <typename LHS, typename RHS>
701 0 : inline BinaryOp_match<LHS, RHS, Instruction::FDiv> m_FDiv(const LHS &L,
702 7824 : const RHS &R) {
703 7828 : return BinaryOp_match<LHS, RHS, Instruction::FDiv>(L, R);
704 430 : }
705 454 :
706 35445 : template <typename LHS, typename RHS>
707 35480 : inline BinaryOp_match<LHS, RHS, Instruction::URem> m_URem(const LHS &L,
708 0 : const RHS &R) {
709 367 : return BinaryOp_match<LHS, RHS, Instruction::URem>(L, R);
710 7 : }
711 5255 :
712 0 : template <typename LHS, typename RHS>
713 0 : inline BinaryOp_match<LHS, RHS, Instruction::SRem> m_SRem(const LHS &L,
714 42 : const RHS &R) {
715 42 : return BinaryOp_match<LHS, RHS, Instruction::SRem>(L, R);
716 27335 : }
717 27354 :
718 11 : template <typename LHS, typename RHS>
719 375 : inline BinaryOp_match<LHS, RHS, Instruction::FRem> m_FRem(const LHS &L,
720 32773 : const RHS &R) {
721 32771 : return BinaryOp_match<LHS, RHS, Instruction::FRem>(L, R);
722 15920 : }
723 16550 :
724 16 : template <typename LHS, typename RHS>
725 1757 : inline BinaryOp_match<LHS, RHS, Instruction::And> m_And(const LHS &L,
726 0 : const RHS &R) {
727 0 : return BinaryOp_match<LHS, RHS, Instruction::And>(L, R);
728 5 : }
729 5 :
730 7057 : template <typename LHS, typename RHS>
731 7058 : inline BinaryOp_match<LHS, RHS, Instruction::Or> m_Or(const LHS &L,
732 23 : const RHS &R) {
733 39 : return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R);
734 61350 : }
735 61386 :
736 5971 : template <typename LHS, typename RHS>
737 6468 : inline BinaryOp_match<LHS, RHS, Instruction::Xor> m_Xor(const LHS &L,
738 0 : const RHS &R) {
739 7 : return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R);
740 0 : }
741 5 :
742 1309 : template <typename LHS, typename RHS>
743 22 : inline BinaryOp_match<LHS, RHS, Instruction::Shl> m_Shl(const LHS &L,
744 0 : const RHS &R) {
745 5 : return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R);
746 522 : }
747 5 :
748 25940 : template <typename LHS, typename RHS>
749 25940 : inline BinaryOp_match<LHS, RHS, Instruction::LShr> m_LShr(const LHS &L,
750 5807 : const RHS &R) {
751 6848 : return BinaryOp_match<LHS, RHS, Instruction::LShr>(L, R);
752 0 : }
753 243109 :
754 243109 : template <typename LHS, typename RHS>
755 0 : inline BinaryOp_match<LHS, RHS, Instruction::AShr> m_AShr(const LHS &L,
756 3118 : const RHS &R) {
757 17 : return BinaryOp_match<LHS, RHS, Instruction::AShr>(L, R);
758 0 : }
759 13 :
760 2 : template <typename LHS_t, typename RHS_t, unsigned Opcode,
761 214 : unsigned WrapFlags = 0>
762 25925 : struct OverflowingBinaryOp_match {
763 25930 : LHS_t L;
764 895 : RHS_t R;
765 1140 :
766 0 : OverflowingBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS)
767 9535 : : L(LHS), R(RHS) {}
768 8659 :
769 3599 : template <typename OpTy> bool match(OpTy *V) {
770 11946 : if (auto *Op = dyn_cast<OverflowingBinaryOperator>(V)) {
771 13390 : if (Op->getOpcode() != Opcode)
772 0 : return false;
773 0 : if (WrapFlags & OverflowingBinaryOperator::NoUnsignedWrap &&
774 0 : !Op->hasNoUnsignedWrap())
775 0 : return false;
776 772878 : if (WrapFlags & OverflowingBinaryOperator::NoSignedWrap &&
777 772495 : !Op->hasNoSignedWrap())
778 43 : return false;
779 5789 : return L.match(Op->getOperand(0)) && R.match(Op->getOperand(1));
780 2375 : }
781 10408 : return false;
782 10408 : }
783 0 : };
784 5298 :
785 1 : template <typename LHS, typename RHS>
786 40594 : inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
787 5106999 : OverflowingBinaryOperator::NoSignedWrap>
788 0 : m_NSWAdd(const LHS &L, const RHS &R) {
789 0 : return OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
790 12121 : OverflowingBinaryOperator::NoSignedWrap>(
791 12121 : L, R);
792 1685 : }
793 1685 : template <typename LHS, typename RHS>
794 0 : inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
795 21242 : OverflowingBinaryOperator::NoSignedWrap>
796 18854 : m_NSWSub(const LHS &L, const RHS &R) {
797 164955 : return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
798 26 : OverflowingBinaryOperator::NoSignedWrap>(
799 17975 : L, R);
800 0 : }
801 2 : template <typename LHS, typename RHS>
802 0 : inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
803 0 : OverflowingBinaryOperator::NoSignedWrap>
804 6114 : m_NSWMul(const LHS &L, const RHS &R) {
805 367 : return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
806 317072 : OverflowingBinaryOperator::NoSignedWrap>(
807 3081 : L, R);
808 315312 : }
809 335043 : template <typename LHS, typename RHS>
810 649311 : inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
811 397023 : OverflowingBinaryOperator::NoSignedWrap>
812 1261 : m_NSWShl(const LHS &L, const RHS &R) {
813 22225 : return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
814 0 : OverflowingBinaryOperator::NoSignedWrap>(
815 104768 : L, R);
816 104765 : }
817 0 :
818 12809 : template <typename LHS, typename RHS>
819 6 : inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
820 0 : OverflowingBinaryOperator::NoUnsignedWrap>
821 145 : m_NUWAdd(const LHS &L, const RHS &R) {
822 0 : return OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
823 28470 : OverflowingBinaryOperator::NoUnsignedWrap>(
824 28470 : L, R);
825 83070 : }
826 14 : template <typename LHS, typename RHS>
827 9841 : inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
828 23353 : OverflowingBinaryOperator::NoUnsignedWrap>
829 0 : m_NUWSub(const LHS &L, const RHS &R) {
830 0 : return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
831 926 : OverflowingBinaryOperator::NoUnsignedWrap>(
832 114597 : L, R);
833 367 : }
834 0 : template <typename LHS, typename RHS>
835 1185 : inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
836 17403636 : OverflowingBinaryOperator::NoUnsignedWrap>
837 17431688 : m_NUWMul(const LHS &L, const RHS &R) {
838 28052 : return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
839 32184 : OverflowingBinaryOperator::NoUnsignedWrap>(
840 6902 : L, R);
841 1 : }
842 0 : template <typename LHS, typename RHS>
843 1 : inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
844 358 : OverflowingBinaryOperator::NoUnsignedWrap>
845 0 : m_NUWShl(const LHS &L, const RHS &R) {
846 0 : return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
847 0 : OverflowingBinaryOperator::NoUnsignedWrap>(
848 0 : L, R);
849 0 : }
850 677542 :
851 734741 : //===----------------------------------------------------------------------===//
852 57199 : // Class that matches a group of binary opcodes.
853 3221 : //
854 3101 : template <typename LHS_t, typename RHS_t, typename Predicate>
855 12 : struct BinOpPred_match : Predicate {
856 85 : LHS_t L;
857 72068 : RHS_t R;
858 507 :
859 0 : BinOpPred_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
860 685 :
861 635 : template <typename OpTy> bool match(OpTy *V) {
862 0 : if (auto *I = dyn_cast<Instruction>(V))
863 0 : return this->isOpType(I->getOpcode()) && L.match(I->getOperand(0)) &&
864 8296 : R.match(I->getOperand(1));
865 8794 : if (auto *CE = dyn_cast<ConstantExpr>(V))
866 498 : return this->isOpType(CE->getOpcode()) && L.match(CE->getOperand(0)) &&
867 0 : R.match(CE->getOperand(1));
868 51 : return false;
869 6 : }
870 0 : };
871 1743 :
872 1714 : struct is_shift_op {
873 21 : bool isOpType(unsigned Opcode) { return Instruction::isShift(Opcode); }
874 20 : };
875 0 :
876 0 : struct is_right_shift_op {
877 0 : bool isOpType(unsigned Opcode) {
878 105376 : return Opcode == Instruction::LShr || Opcode == Instruction::AShr;
879 105497 : }
880 11612 : };
881 90750 :
882 239219 : struct is_logical_shift_op {
883 457168 : bool isOpType(unsigned Opcode) {
884 8 : return Opcode == Instruction::LShr || Opcode == Instruction::Shl;
885 18683 : }
886 18671 : };
887 49744 :
888 645 : struct is_bitwiselogic_op {
889 2383 : bool isOpType(unsigned Opcode) {
890 0 : return Instruction::isBitwiseLogicOp(Opcode);
891 17 : }
892 105548 : };
893 132572 :
894 27027 : struct is_idiv_op {
895 25283 : bool isOpType(unsigned Opcode) {
896 337 : return Opcode == Instruction::SDiv || Opcode == Instruction::UDiv;
897 335 : }
898 2 : };
899 18671 :
900 18671 : /// Matches shift operations.
901 0 : template <typename LHS, typename RHS>
902 1898 : inline BinOpPred_match<LHS, RHS, is_shift_op> m_Shift(const LHS &L,
903 0 : const RHS &R) {
904 85630 : return BinOpPred_match<LHS, RHS, is_shift_op>(L, R);
905 11 : }
906 135951 :
907 161868 : /// Matches logical shift operations.
908 25920 : template <typename LHS, typename RHS>
909 21608 : inline BinOpPred_match<LHS, RHS, is_right_shift_op> m_Shr(const LHS &L,
910 343 : const RHS &R) {
911 341 : return BinOpPred_match<LHS, RHS, is_right_shift_op>(L, R);
912 2 : }
913 109 :
914 109 : /// Matches logical shift operations.
915 0 : template <typename LHS, typename RHS>
916 42 : inline BinOpPred_match<LHS, RHS, is_logical_shift_op>
917 6 : m_LogicalShift(const LHS &L, const RHS &R) {
918 : return BinOpPred_match<LHS, RHS, is_logical_shift_op>(L, R);
919 6 : }
920 139627 :
921 150106 : /// Matches bitwise logic operations.
922 10298 : template <typename LHS, typename RHS>
923 3905 : inline BinOpPred_match<LHS, RHS, is_bitwiselogic_op>
924 232 : m_BitwiseLogic(const LHS &L, const RHS &R) {
925 : return BinOpPred_match<LHS, RHS, is_bitwiselogic_op>(L, R);
926 19 : }
927 8 :
928 0 : /// Matches integer division operations.
929 74 : template <typename LHS, typename RHS>
930 2 : inline BinOpPred_match<LHS, RHS, is_idiv_op> m_IDiv(const LHS &L,
931 0 : const RHS &R) {
932 269 : return BinOpPred_match<LHS, RHS, is_idiv_op>(L, R);
933 0 : }
934 51155 :
935 59906 : //===----------------------------------------------------------------------===//
936 8754 : // Class that matches exact binary ops.
937 0 : //
938 2 : template <typename SubPattern_t> struct Exact_match {
939 0 : SubPattern_t SubPattern;
940 2 :
941 13 : Exact_match(const SubPattern_t &SP) : SubPattern(SP) {}
942 13 :
943 0 : template <typename OpTy> bool match(OpTy *V) {
944 10 : if (auto *PEO = dyn_cast<PossiblyExactOperator>(V))
945 0 : return PEO->isExact() && SubPattern.match(V);
946 : return false;
947 : }
948 5389333 : };
949 5389331 :
950 5 : template <typename T> inline Exact_match<T> m_Exact(const T &SubPattern) {
951 155 : return SubPattern;
952 17 : }
953 0 :
954 0 : //===----------------------------------------------------------------------===//
955 6884 : // Matchers for CmpInst classes
956 42720 : //
957 15919317 :
958 0 : template <typename LHS_t, typename RHS_t, typename Class, typename PredicateTy,
959 15199906 : bool Commutable = false>
960 15199906 : struct CmpClass_match {
961 30399804 : PredicateTy &Predicate;
962 20596237 : LHS_t L;
963 5394942 : RHS_t R;
964 3 :
965 11142 : // The evaluation order is always stable, regardless of Commutability.
966 5071885 : // The LHS is always matched first.
967 5107123 : CmpClass_match(PredicateTy &Pred, const LHS_t &LHS, const RHS_t &RHS)
968 10132703 : : Predicate(Pred), L(LHS), R(RHS) {}
969 5078814 :
970 14139 : template <typename OpTy> bool match(OpTy *V) {
971 24383 : if (auto *I = dyn_cast<Class>(V))
972 3381 : if ((L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
973 5069618 : (Commutable && L.match(I->getOperand(1)) &&
974 5108249 : R.match(I->getOperand(0)))) {
975 10134077 : Predicate = I->getPredicate();
976 10464063 : return true;
977 5396182 : }
978 275 : return false;
979 5036 : }
980 5067402 : };
981 5070999 :
982 10138210 : template <typename LHS, typename RHS>
983 5081077 : inline CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate>
984 17709 : m_Cmp(CmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
985 2 : return CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate>(Pred, L, R);
986 3555 : }
987 408 :
988 0 : template <typename LHS, typename RHS>
989 471 : inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>
990 224 : m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
991 3 : return CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>(Pred, L, R);
992 11219 : }
993 0 :
994 17600 : template <typename LHS, typename RHS>
995 0 : inline CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>
996 43 : m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
997 10322 : return CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>(Pred, L, R);
998 21528 : }
999 146 :
1000 144 : //===----------------------------------------------------------------------===//
1001 0 : // Matchers for instructions with a given opcode and number of operands.
1002 0 : //
1003 0 :
1004 1802 : /// Matches instructions with Opcode and three operands.
1005 1 : template <typename T0, unsigned Opcode> struct OneOps_match {
1006 9848444 : T0 Op1;
1007 0 :
1008 127276511 : OneOps_match(const T0 &Op1) : Op1(Op1) {}
1009 127276539 :
1010 29 : template <typename OpTy> bool match(OpTy *V) {
1011 5231314 : if (V->getValueID() == Value::InstructionVal + Opcode) {
1012 15160 : auto *I = cast<Instruction>(V);
1013 0 : return Op1.match(I->getOperand(0));
1014 4985 : }
1015 0 : return false;
1016 146902 : }
1017 517 : };
1018 149047 :
1019 149038 : /// Matches instructions with Opcode and three operands.
1020 154646 : template <typename T0, typename T1, unsigned Opcode> struct TwoOps_match {
1021 5608 : T0 Op1;
1022 33996 : T1 Op2;
1023 33995 :
1024 430572 : TwoOps_match(const T0 &Op1, const T1 &Op2) : Op1(Op1), Op2(Op2) {}
1025 450089 :
1026 17456 : template <typename OpTy> bool match(OpTy *V) {
1027 97437 : if (V->getValueID() == Value::InstructionVal + Opcode) {
1028 8785 : auto *I = cast<Instruction>(V);
1029 0 : return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1));
1030 4 : }
1031 0 : return false;
1032 60301 : }
1033 60367 : };
1034 60301 :
1035 0 : /// Matches instructions with Opcode and three operands.
1036 33974 : template <typename T0, typename T1, typename T2, unsigned Opcode>
1037 34213 : struct ThreeOps_match {
1038 240 : T0 Op1;
1039 83197 : T1 Op2;
1040 83436 : T2 Op3;
1041 82973 :
1042 41 : ThreeOps_match(const T0 &Op1, const T1 &Op2, const T2 &Op3)
1043 31383 : : Op1(Op1), Op2(Op2), Op3(Op3) {}
1044 16306 :
1045 72 : template <typename OpTy> bool match(OpTy *V) {
1046 76956 : if (V->getValueID() == Value::InstructionVal + Opcode) {
1047 76892 : auto *I = cast<Instruction>(V);
1048 1 : return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1)) &&
1049 14517 : Op3.match(I->getOperand(2));
1050 5483231 : }
1051 5483184 : return false;
1052 40 : }
1053 44482 : };
1054 14 :
1055 27 : /// Matches SelectInst.
1056 607270 : template <typename Cond, typename LHS, typename RHS>
1057 607243 : inline ThreeOps_match<Cond, LHS, RHS, Instruction::Select>
1058 74 : m_Select(const Cond &C, const LHS &L, const RHS &R) {
1059 607243 : return ThreeOps_match<Cond, LHS, RHS, Instruction::Select>(C, L, R);
1060 617823 : }
1061 10386 :
1062 159 : /// This matches a select of two constants, e.g.:
1063 44 : /// m_SelectCst<-1, 0>(m_Value(V))
1064 986 : template <int64_t L, int64_t R, typename Cond>
1065 721506 : inline ThreeOps_match<Cond, constantint_match<L>, constantint_match<R>,
1066 46 : Instruction::Select>
1067 27944868 : m_SelectCst(const Cond &C) {
1068 27598932 : return m_Select(C, m_ConstantInt<L>(), m_ConstantInt<R>());
1069 522941 : }
1070 681546 :
1071 828402 : /// Matches InsertElementInst.
1072 520013 : template <typename Val_t, typename Elt_t, typename Idx_t>
1073 953 : inline ThreeOps_match<Val_t, Elt_t, Idx_t, Instruction::InsertElement>
1074 2562 : m_InsertElement(const Val_t &Val, const Elt_t &Elt, const Idx_t &Idx) {
1075 6636 : return ThreeOps_match<Val_t, Elt_t, Idx_t, Instruction::InsertElement>(
1076 1305 : Val, Elt, Idx);
1077 422 : }
1078 11247342 :
1079 11247924 : /// Matches ExtractElementInst.
1080 582 : template <typename Val_t, typename Idx_t>
1081 3406 : inline TwoOps_match<Val_t, Idx_t, Instruction::ExtractElement>
1082 3504 : m_ExtractElement(const Val_t &Val, const Idx_t &Idx) {
1083 0 : return TwoOps_match<Val_t, Idx_t, Instruction::ExtractElement>(Val, Idx);
1084 1 : }
1085 0 :
1086 1177 : /// Matches ShuffleVectorInst.
1087 20 : template <typename V1_t, typename V2_t, typename Mask_t>
1088 13827 : inline ThreeOps_match<V1_t, V2_t, Mask_t, Instruction::ShuffleVector>
1089 13807 : m_ShuffleVector(const V1_t &v1, const V2_t &v2, const Mask_t &m) {
1090 18909 : return ThreeOps_match<V1_t, V2_t, Mask_t, Instruction::ShuffleVector>(v1, v2,
1091 31326 : m);
1092 73472 : }
1093 55952 :
1094 0 : /// Matches LoadInst.
1095 10136382 : template <typename OpTy>
1096 1109 : inline OneOps_match<OpTy, Instruction::Load> m_Load(const OpTy &Op) {
1097 55524669 : return OneOps_match<OpTy, Instruction::Load>(Op);
1098 55523563 : }
1099 699513 :
1100 77163 : /// Matches StoreInst.
1101 32046603 : template <typename ValueOpTy, typename PointerOpTy>
1102 32053167 : inline TwoOps_match<ValueOpTy, PointerOpTy, Instruction::Store>
1103 13966 : m_Store(const ValueOpTy &ValueOp, const PointerOpTy &PointerOp) {
1104 488351 : return TwoOps_match<ValueOpTy, PointerOpTy, Instruction::Store>(ValueOp,
1105 163214 : PointerOp);
1106 56163 : }
1107 56159 :
1108 : //===----------------------------------------------------------------------===//
1109 1606 : // Matchers for CastInst classes
1110 6 : //
1111 2610401 :
1112 2610400 : template <typename Op_t, unsigned Opcode> struct CastClass_match {
1113 0 : Op_t Op;
1114 214 :
1115 347497 : CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {}
1116 347487 :
1117 7229 : template <typename OpTy> bool match(OpTy *V) {
1118 95688 : if (auto *O = dyn_cast<Operator>(V))
1119 6302 : return O->getOpcode() == Opcode && Op.match(O->getOperand(0));
1120 84863 : return false;
1121 84873 : }
1122 : };
1123 30786 :
1124 27397 : /// Matches BitCast.
1125 8190 : template <typename OpTy>
1126 62972 : inline CastClass_match<OpTy, Instruction::BitCast> m_BitCast(const OpTy &Op) {
1127 27597 : return CastClass_match<OpTy, Instruction::BitCast>(Op);
1128 668 : }
1129 77314 :
1130 77314 : /// Matches PtrToInt.
1131 48208 : template <typename OpTy>
1132 4052 : inline CastClass_match<OpTy, Instruction::PtrToInt> m_PtrToInt(const OpTy &Op) {
1133 6232096 : return CastClass_match<OpTy, Instruction::PtrToInt>(Op);
1134 9784 : }
1135 9788 :
1136 0 : /// Matches Trunc.
1137 27411 : template <typename OpTy>
1138 27387 : inline CastClass_match<OpTy, Instruction::Trunc> m_Trunc(const OpTy &Op) {
1139 11274853 : return CastClass_match<OpTy, Instruction::Trunc>(Op);
1140 11302240 : }
1141 48198 :
1142 0 : /// Matches SExt.
1143 229939 : template <typename OpTy>
1144 47260 : inline CastClass_match<OpTy, Instruction::SExt> m_SExt(const OpTy &Op) {
1145 0 : return CastClass_match<OpTy, Instruction::SExt>(Op);
1146 1415 : }
1147 1462 :
1148 707 : /// Matches ZExt.
1149 707 : template <typename OpTy>
1150 0 : inline CastClass_match<OpTy, Instruction::ZExt> m_ZExt(const OpTy &Op) {
1151 27388 : return CastClass_match<OpTy, Instruction::ZExt>(Op);
1152 27381 : }
1153 22558697 :
1154 22586078 : template <typename OpTy>
1155 0 : inline match_combine_or<CastClass_match<OpTy, Instruction::ZExt>,
1156 28162 : CastClass_match<OpTy, Instruction::SExt>>
1157 0 : m_ZExtOrSExt(const OpTy &Op) {
1158 0 : return m_CombineOr(m_ZExt(Op), m_SExt(Op));
1159 0 : }
1160 0 :
1161 112 : /// Matches UIToFP.
1162 14944 : template <typename OpTy>
1163 14944 : inline CastClass_match<OpTy, Instruction::UIToFP> m_UIToFP(const OpTy &Op) {
1164 : return CastClass_match<OpTy, Instruction::UIToFP>(Op);
1165 8714 : }
1166 642 :
1167 1178 : /// Matches SIToFP.
1168 1195 : template <typename OpTy>
1169 9 : inline CastClass_match<OpTy, Instruction::SIToFP> m_SIToFP(const OpTy &Op) {
1170 18 : return CastClass_match<OpTy, Instruction::SIToFP>(Op);
1171 4377 : }
1172 4377 :
1173 5853 : /// Matches FPTrunc
1174 2838 : template <typename OpTy>
1175 6106 : inline CastClass_match<OpTy, Instruction::FPTrunc> m_FPTrunc(const OpTy &Op) {
1176 5162742 : return CastClass_match<OpTy, Instruction::FPTrunc>(Op);
1177 5162742 : }
1178 0 :
1179 58588 : /// Matches FPExt
1180 27659 : template <typename OpTy>
1181 2587590 : inline CastClass_match<OpTy, Instruction::FPExt> m_FPExt(const OpTy &Op) {
1182 2656687 : return CastClass_match<OpTy, Instruction::FPExt>(Op);
1183 27224 : }
1184 1621 :
1185 4381 : //===----------------------------------------------------------------------===//
1186 4381 : // Matchers for control flow.
1187 758432 : //
1188 1423 :
1189 8491974 : struct br_match {
1190 18651614 : BasicBlock *&Succ;
1191 10170124 :
1192 181122 : br_match(BasicBlock *&Succ) : Succ(Succ) {}
1193 83479 :
1194 25614 : template <typename OpTy> bool match(OpTy *V) {
1195 2612553 : if (auto *BI = dyn_cast<BranchInst>(V))
1196 2663561 : if (BI->isUnconditional()) {
1197 28628 : Succ = BI->getSuccessor(0);
1198 8 : return true;
1199 0 : }
1200 444 : return false;
1201 399 : }
1202 32 : };
1203 39 :
1204 4744590 : inline br_match m_UnconditionalBr(BasicBlock *&Succ) { return br_match(Succ); }
1205 4744551 :
1206 2 : template <typename Cond_t> struct brc_match {
1207 27312 : Cond_t Cond;
1208 27270 : BasicBlock *&T, *&F;
1209 2625622 :
1210 2683260 : brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f)
1211 30386 : : Cond(C), T(t), F(f) {}
1212 0 :
1213 338891 : template <typename OpTy> bool match(OpTy *V) {
1214 341034 : if (auto *BI = dyn_cast<BranchInst>(V))
1215 10363 : if (BI->isConditional() && Cond.match(BI->getCondition())) {
1216 5119 : T = BI->getSuccessor(0);
1217 627892 : F = BI->getSuccessor(1);
1218 5689983 : return true;
1219 5066376 : }
1220 47017 : return false;
1221 5093714 : }
1222 27260 : };
1223 461 :
1224 55073 : template <typename Cond_t>
1225 27356 : inline brc_match<Cond_t> m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) {
1226 14 : return brc_match<Cond_t>(C, T, F);
1227 243046 : }
1228 202895 :
1229 2711 : //===----------------------------------------------------------------------===//
1230 98 : // Matchers for max/min idioms, eg: "select (sgt x, y), x, y" -> smax(x,y).
1231 97 : //
1232 41351 :
1233 41258 : template <typename CmpInst_t, typename LHS_t, typename RHS_t, typename Pred_t,
1234 1 : bool Commutable = false>
1235 32142 : struct MaxMin_match {
1236 27253 : LHS_t L;
1237 461 : RHS_t R;
1238 54957 :
1239 27244 : // The evaluation order is always stable, regardless of Commutability.
1240 68 : // The LHS is always matched first.
1241 0 : MaxMin_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
1242 3140 :
1243 17436 : template <typename OpTy> bool match(OpTy *V) {
1244 50573 : // Look for "(x pred y) ? x : y" or "(x pred y) ? y : x".
1245 1259783 : auto *SI = dyn_cast<SelectInst>(V);
1246 1245494 : if (!SI)
1247 8 : return false;
1248 8573 : auto *Cmp = dyn_cast<CmpInst_t>(SI->getCondition());
1249 34342 : if (!Cmp)
1250 34339 : return false;
1251 4868 : // At this point we have a select conditioned on a comparison. Check that
1252 13525 : // it is the values returned by the select that are being compared.
1253 11946 : Value *TrueVal = SI->getTrueValue();
1254 7212 : Value *FalseVal = SI->getFalseValue();
1255 210776 : Value *LHS = Cmp->getOperand(0);
1256 204160 : Value *RHS = Cmp->getOperand(1);
1257 16528 : if ((TrueVal != LHS || FalseVal != RHS) &&
1258 8203 : (TrueVal != RHS || FalseVal != LHS))
1259 6344 : return false;
1260 2 : typename CmpInst_t::Predicate Pred =
1261 2 : LHS == TrueVal ? Cmp->getPredicate() : Cmp->getInversePredicate();
1262 0 : // Does "(x pred y) ? x : y" represent the desired max/min operation?
1263 34198 : if (!Pred_t::match(Pred))
1264 34561 : return false;
1265 0 : // It does! Bind the operands.
1266 8614 : return (L.match(LHS) && R.match(RHS)) ||
1267 0 : (Commutable && L.match(RHS) && R.match(LHS));
1268 0 : }
1269 203861 : };
1270 203865 :
1271 4 : /// Helper class for identifying signed max predicates.
1272 4753 : struct smax_pred_ty {
1273 249 : static bool match(ICmpInst::Predicate Pred) {
1274 10134611 : return Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE;
1275 10134391 : }
1276 238 : };
1277 3915 :
1278 3350 : /// Helper class for identifying signed min predicates.
1279 4372 : struct smin_pred_ty {
1280 4559 : static bool match(ICmpInst::Predicate Pred) {
1281 0 : return Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_SLE;
1282 298 : }
1283 595147 : };
1284 595382 :
1285 2854 : /// Helper class for identifying unsigned max predicates.
1286 5202 : struct umax_pred_ty {
1287 8635 : static bool match(ICmpInst::Predicate Pred) {
1288 10140355 : return Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE;
1289 10134392 : }
1290 237 : };
1291 3429 :
1292 3347 : /// Helper class for identifying unsigned min predicates.
1293 4463 : struct umin_pred_ty {
1294 4453 : static bool match(ICmpInst::Predicate Pred) {
1295 2837 : return Pred == CmpInst::ICMP_ULT || Pred == CmpInst::ICMP_ULE;
1296 999255 : }
1297 5183 : };
1298 7149 :
1299 1003888 : /// Helper class for identifying ordered max predicates.
1300 332 : struct ofmax_pred_ty {
1301 101778 : static bool match(FCmpInst::Predicate Pred) {
1302 102909 : return Pred == CmpInst::FCMP_OGT || Pred == CmpInst::FCMP_OGE;
1303 1475 : }
1304 0 : };
1305 3347 :
1306 3346 : /// Helper class for identifying ordered min predicates.
1307 4468 : struct ofmin_pred_ty {
1308 4496 : static bool match(FCmpInst::Predicate Pred) {
1309 29092 : return Pred == CmpInst::FCMP_OLT || Pred == CmpInst::FCMP_OLE;
1310 544875 : }
1311 14093 : };
1312 119 :
1313 119 : /// Helper class for identifying unordered max predicates.
1314 537503 : struct ufmax_pred_ty {
1315 0 : static bool match(FCmpInst::Predicate Pred) {
1316 538334 : return Pred == CmpInst::FCMP_UGT || Pred == CmpInst::FCMP_UGE;
1317 1136 : }
1318 : };
1319 9 :
1320 0 : /// Helper class for identifying unordered min predicates.
1321 9665 : struct ufmin_pred_ty {
1322 11480 : static bool match(FCmpInst::Predicate Pred) {
1323 0 : return Pred == CmpInst::FCMP_ULT || Pred == CmpInst::FCMP_ULE;
1324 46 : }
1325 60574 : };
1326 60173 :
1327 1414 : template <typename LHS, typename RHS>
1328 3333 : inline MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty> m_SMax(const LHS &L,
1329 59245 : const RHS &R) {
1330 4796345 : return MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty>(L, R);
1331 4739235 : }
1332 76 :
1333 27467 : template <typename LHS, typename RHS>
1334 27121 : inline MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty> m_SMin(const LHS &L,
1335 9680 : const RHS &R) {
1336 11260 : return MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty>(L, R);
1337 551260 : }
1338 147 :
1339 17317 : template <typename LHS, typename RHS>
1340 31134 : inline MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty> m_UMax(const LHS &L,
1341 13806 : const RHS &R) {
1342 11 : return MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty>(L, R);
1343 3 : }
1344 5949536 :
1345 5949533 : template <typename LHS, typename RHS>
1346 3 : inline MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty> m_UMin(const LHS &L,
1347 14570 : const RHS &R) {
1348 86305 : return MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty>(L, R);
1349 0 : }
1350 8 :
1351 75480 : /// Match an 'ordered' floating point maximum function.
1352 41 : /// Floating point has one special value 'NaN'. Therefore, there is no total
1353 44332 : /// order. However, if we can ignore the 'NaN' value (for example, because of a
1354 44074 : /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum'
1355 0 : /// semantics. In the presence of 'NaN' we have to preserve the original
1356 523 : /// select(fcmp(ogt/ge, L, R), L, R) semantics matched by this predicate.
1357 244467 : ///
1358 10953586 : /// max(L, R) iff L and R are not NaN
1359 10709119 : /// m_OrdFMax(L, R) = R iff L or R are NaN
1360 : template <typename LHS, typename RHS>
1361 1358420 : inline MaxMin_match<FCmpInst, LHS, RHS, ofmax_pred_ty> m_OrdFMax(const LHS &L,
1362 1327736 : const RHS &R) {
1363 100 : return MaxMin_match<FCmpInst, LHS, RHS, ofmax_pred_ty>(L, R);
1364 42948 : }
1365 58 :
1366 73889 : /// Match an 'ordered' floating point minimum function.
1367 79409 : /// Floating point has one special value 'NaN'. Therefore, there is no total
1368 157737 : /// order. However, if we can ignore the 'NaN' value (for example, because of a
1369 6622 : /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum'
1370 2 : /// semantics. In the presence of 'NaN' we have to preserve the original
1371 72425 : /// select(fcmp(olt/le, L, R), L, R) semantics matched by this predicate.
1372 72199 : ///
1373 158 : /// min(L, R) iff L and R are not NaN
1374 167805 : /// m_OrdFMin(L, R) = R iff L or R are NaN
1375 59750 : template <typename LHS, typename RHS>
1376 59726 : inline MaxMin_match<FCmpInst, LHS, RHS, ofmin_pred_ty> m_OrdFMin(const LHS &L,
1377 10284557 : const RHS &R) {
1378 10135545 : return MaxMin_match<FCmpInst, LHS, RHS, ofmin_pred_ty>(L, R);
1379 43 : }
1380 7045 :
1381 3571 : /// Match an 'unordered' floating point maximum function.
1382 303 : /// Floating point has one special value 'NaN'. Therefore, there is no total
1383 240 : /// order. However, if we can ignore the 'NaN' value (for example, because of a
1384 2 : /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum'
1385 93939 : /// semantics. In the presence of 'NaN' we have to preserve the original
1386 9764303 : /// select(fcmp(ugt/ge, L, R), L, R) semantics matched by this predicate.
1387 9670365 : ///
1388 87430 : /// max(L, R) iff L and R are not NaN
1389 62916 : /// m_UnordFMax(L, R) = L iff L or R are NaN
1390 51465 : template <typename LHS, typename RHS>
1391 11273 : inline MaxMin_match<FCmpInst, LHS, RHS, ufmax_pred_ty>
1392 180000 : m_UnordFMax(const LHS &L, const RHS &R) {
1393 51951 : return MaxMin_match<FCmpInst, LHS, RHS, ufmax_pred_ty>(L, R);
1394 74223 : }
1395 53 :
1396 260 : /// Match an 'unordered' floating point minimum function.
1397 232 : /// Floating point has one special value 'NaN'. Therefore, there is no total
1398 12 : /// order. However, if we can ignore the 'NaN' value (for example, because of a
1399 10 : /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum'
1400 19989103 : /// semantics. In the presence of 'NaN' we have to preserve the original
1401 19837291 : /// select(fcmp(ult/le, L, R), L, R) semantics matched by this predicate.
1402 6 : ///
1403 171195 : /// min(L, R) iff L and R are not NaN
1404 1470 : /// m_UnordFMin(L, R) = L iff L or R are NaN
1405 16 : template <typename LHS, typename RHS>
1406 933 : inline MaxMin_match<FCmpInst, LHS, RHS, ufmin_pred_ty>
1407 1 : m_UnordFMin(const LHS &L, const RHS &R) {
1408 63456 : return MaxMin_match<FCmpInst, LHS, RHS, ufmin_pred_ty>(L, R);
1409 156590 : }
1410 93465 :
1411 63573 : //===----------------------------------------------------------------------===//
1412 63715 : // Matchers for overflow check patterns: e.g. (a + b) u< a
1413 225262 : //
1414 303367 :
1415 3683 : template <typename LHS_t, typename RHS_t, typename Sum_t>
1416 3 : struct UAddWithOverflow_match {
1417 1440 : LHS_t L;
1418 77793 : RHS_t R;
1419 31669 : Sum_t S;
1420 108167 :
1421 7 : UAddWithOverflow_match(const LHS_t &L, const RHS_t &R, const Sum_t &S)
1422 185 : : L(L), R(R), S(S) {}
1423 276559 :
1424 6207487 : template <typename OpTy> bool match(OpTy *V) {
1425 5930924 : Value *ICmpLHS, *ICmpRHS;
1426 151831 : ICmpInst::Predicate Pred;
1427 6496570 : if (!m_ICmp(Pred, m_Value(ICmpLHS), m_Value(ICmpRHS)).match(V))
1428 6496944 : return false;
1429 152206 :
1430 16906 : Value *AddLHS, *AddRHS;
1431 761 : auto AddExpr = m_Add(m_Value(AddLHS), m_Value(AddRHS));
1432 333 :
1433 0 : // (a + b) u< a, (a + b) u< b
1434 0 : if (Pred == ICmpInst::ICMP_ULT)
1435 436 : if (AddExpr.match(ICmpLHS) && (ICmpRHS == AddLHS || ICmpRHS == AddRHS))
1436 436 : return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS);
1437 553255 :
1438 553556 : // a >u (a + b), b >u (a + b)
1439 37 : if (Pred == ICmpInst::ICMP_UGT)
1440 73743 : if (AddExpr.match(ICmpRHS) && (ICmpLHS == AddLHS || ICmpLHS == AddRHS))
1441 672 : return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS);
1442 1225 :
1443 625900 : return false;
1444 699523 : }
1445 23608919 : };
1446 23691011 :
1447 1040135 : /// Match an icmp instruction checking for unsigned overflow on addition.
1448 1077199 : ///
1449 34141 : /// S is matched to the addition whose result is being checked for overflow, and
1450 40769 : /// L and R are matched to the LHS and RHS of S.
1451 1658 : template <typename LHS_t, typename RHS_t, typename Sum_t>
1452 153602 : UAddWithOverflow_match<LHS_t, RHS_t, Sum_t>
1453 152 : m_UAddWithOverflow(const LHS_t &L, const RHS_t &R, const Sum_t &S) {
1454 2554 : return UAddWithOverflow_match<LHS_t, RHS_t, Sum_t>(L, R, S);
1455 855234 : }
1456 703272 :
1457 37 : template <typename Opnd_t> struct Argument_match {
1458 548 : unsigned OpI;
1459 315680 : Opnd_t Val;
1460 315717 :
1461 2911 : Argument_match(unsigned OpIdx, const Opnd_t &V) : OpI(OpIdx), Val(V) {}
1462 4554 :
1463 355 : template <typename OpTy> bool match(OpTy *V) {
1464 67 : CallSite CS(V);
1465 37 : return CS.isCall() && Val.match(CS.getArgument(OpI));
1466 73861 : }
1467 2615 : };
1468 2541 :
1469 11 : /// Match an argument.
1470 74725 : template <unsigned OpI, typename Opnd_t>
1471 672 : inline Argument_match<Opnd_t> m_Argument(const Opnd_t &Op) {
1472 73807 : return Argument_match<Opnd_t>(OpI, Op);
1473 523767 : }
1474 523767 :
1475 5507496 : /// Intrinsic matchers.
1476 5507462 : struct IntrinsicID_match {
1477 37 : unsigned ID;
1478 160197 :
1479 22423411 : IntrinsicID_match(Intrinsic::ID IntrID) : ID(IntrID) {}
1480 22423388 :
1481 157471 : template <typename OpTy> bool match(OpTy *V) {
1482 11875 : if (const auto *CI = dyn_cast<CallInst>(V))
1483 569531 : if (const auto *F = CI->getCalledFunction())
1484 3499281 : return F->getIntrinsicID() == ID;
1485 1 : return false;
1486 10382 : }
1487 34 : };
1488 23 :
1489 2974 : /// Intrinsic matches are combinations of ID matchers, and argument
1490 2976 : /// matchers. Higher arity matcher are defined recursively in terms of and-ing
1491 0 : /// them with lower arity matchers. Here's some convenient typedefs for up to
1492 83443 : /// several arguments, and more can be added as needed
1493 765615 : template <typename T0 = void, typename T1 = void, typename T2 = void,
1494 761870 : typename T3 = void, typename T4 = void, typename T5 = void,
1495 0 : typename T6 = void, typename T7 = void, typename T8 = void,
1496 107937 : typename T9 = void, typename T10 = void>
1497 33 : struct m_Intrinsic_Ty;
1498 82433 : template <typename T0> struct m_Intrinsic_Ty<T0> {
1499 642 : using Ty = match_combine_and<IntrinsicID_match, Argument_match<T0>>;
1500 : };
1501 9010 : template <typename T0, typename T1> struct m_Intrinsic_Ty<T0, T1> {
1502 8990 : using Ty =
1503 2942 : match_combine_and<typename m_Intrinsic_Ty<T0>::Ty, Argument_match<T1>>;
1504 162738 : };
1505 1600 : template <typename T0, typename T1, typename T2>
1506 64 : struct m_Intrinsic_Ty<T0, T1, T2> {
1507 160347 : using Ty =
1508 0 : match_combine_and<typename m_Intrinsic_Ty<T0, T1>::Ty,
1509 1 : Argument_match<T2>>;
1510 0 : };
1511 491714 : template <typename T0, typename T1, typename T2, typename T3>
1512 491757 : struct m_Intrinsic_Ty<T0, T1, T2, T3> {
1513 0 : using Ty =
1514 579 : match_combine_and<typename m_Intrinsic_Ty<T0, T1, T2>::Ty,
1515 87508 : Argument_match<T3>>;
1516 89698 : };
1517 2976 :
1518 101031 : /// Match intrinsic calls like this:
1519 15354 : /// m_Intrinsic<Intrinsic::fabs>(m_Value(X))
1520 0 : template <Intrinsic::ID IntrID> inline IntrinsicID_match m_Intrinsic() {
1521 13 : return IntrinsicID_match(IntrID);
1522 83755 : }
1523 9 :
1524 83751 : template <Intrinsic::ID IntrID, typename T0>
1525 117151 : inline typename m_Intrinsic_Ty<T0>::Ty m_Intrinsic(const T0 &Op0) {
1526 4944647 : return m_CombineAnd(m_Intrinsic<IntrID>(), m_Argument<0>(Op0));
1527 4827451 : }
1528 47006 :
1529 50255 : template <Intrinsic::ID IntrID, typename T0, typename T1>
1530 60 : inline typename m_Intrinsic_Ty<T0, T1>::Ty m_Intrinsic(const T0 &Op0,
1531 1614 : const T1 &Op1) {
1532 112 : return m_CombineAnd(m_Intrinsic<IntrID>(Op0), m_Argument<1>(Op1));
1533 939 : }
1534 0 :
1535 108642 : template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2>
1536 34408 : inline typename m_Intrinsic_Ty<T0, T1, T2>::Ty
1537 0 : m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2) {
1538 3681 : return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1), m_Argument<2>(Op2));
1539 1673 : }
1540 2104 :
1541 431 : template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2,
1542 81858 : typename T3>
1543 42640 : inline typename m_Intrinsic_Ty<T0, T1, T2, T3>::Ty
1544 42640 : m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3) {
1545 2965 : return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2), m_Argument<3>(Op3));
1546 3491 : }
1547 410823 :
1548 341 : // Helper intrinsic matching specializations.
1549 465100 : template <typename Opnd0>
1550 1153 : inline typename m_Intrinsic_Ty<Opnd0>::Ty m_BitReverse(const Opnd0 &Op0) {
1551 0 : return m_Intrinsic<Intrinsic::bitreverse>(Op0);
1552 40 : }
1553 106 :
1554 19 : template <typename Opnd0>
1555 46 : inline typename m_Intrinsic_Ty<Opnd0>::Ty m_BSwap(const Opnd0 &Op0) {
1556 83766 : return m_Intrinsic<Intrinsic::bswap>(Op0);
1557 1343 : }
1558 1339 :
1559 2920 : template <typename Opnd0>
1560 3002 : inline typename m_Intrinsic_Ty<Opnd0>::Ty m_FAbs(const Opnd0 &Op0) {
1561 87 : return m_Intrinsic<Intrinsic::fabs>(Op0);
1562 58 : }
1563 74433 :
1564 818 : template <typename Opnd0>
1565 0 : inline typename m_Intrinsic_Ty<Opnd0>::Ty m_FCanonicalize(const Opnd0 &Op0) {
1566 5 : return m_Intrinsic<Intrinsic::canonicalize>(Op0);
1567 127 : }
1568 312 :
1569 10284117 : template <typename Opnd0, typename Opnd1>
1570 73907 : inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMin(const Opnd0 &Op0,
1571 10372167 : const Opnd1 &Op1) {
1572 147007 : return m_Intrinsic<Intrinsic::minnum>(Op0, Op1);
1573 2467 : }
1574 32091 :
1575 53 : template <typename Opnd0, typename Opnd1>
1576 25 : inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMax(const Opnd0 &Op0,
1577 128883 : const Opnd1 &Op1) {
1578 733 : return m_Intrinsic<Intrinsic::maxnum>(Op0, Op1);
1579 120957 : }
1580 3 :
1581 66 : //===----------------------------------------------------------------------===//
1582 184419 : // Matchers for two-operands operators with the operators in either order
1583 55101 : //
1584 198312 :
1585 631 : /// Matches a BinaryOperator with LHS and RHS in either order.
1586 5092 : template <typename LHS, typename RHS>
1587 123053 : inline AnyBinaryOp_match<LHS, RHS, true> m_c_BinOp(const LHS &L, const RHS &R) {
1588 9 : return AnyBinaryOp_match<LHS, RHS, true>(L, R);
1589 120292 : }
1590 1 :
1591 4189 : /// Matches an ICmp with a predicate over LHS and RHS in either order.
1592 322 : /// Does not swap the predicate.
1593 0 : template <typename LHS, typename RHS>
1594 5 : inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate, true>
1595 18552 : m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1596 55556 : return CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate, true>(Pred, L,
1597 37004 : R);
1598 : }
1599 309861 :
1600 309030 : /// Matches a Add with LHS and RHS in either order.
1601 0 : template <typename LHS, typename RHS>
1602 152006 : inline BinaryOp_match<LHS, RHS, Instruction::Add, true> m_c_Add(const LHS &L,
1603 4118 : const RHS &R) {
1604 5137416 : return BinaryOp_match<LHS, RHS, Instruction::Add, true>(L, R);
1605 4215 : }
1606 5134176 :
1607 28040 : /// Matches a Mul with LHS and RHS in either order.
1608 28147 : template <typename LHS, typename RHS>
1609 5294372 : inline BinaryOp_match<LHS, RHS, Instruction::Mul, true> m_c_Mul(const LHS &L,
1610 46579 : const RHS &R) {
1611 5124587 : return BinaryOp_match<LHS, RHS, Instruction::Mul, true>(L, R);
1612 141885 : }
1613 14969 :
1614 57 : /// Matches an And with LHS and RHS in either order.
1615 97822 : template <typename LHS, typename RHS>
1616 39121 : inline BinaryOp_match<LHS, RHS, Instruction::And, true> m_c_And(const LHS &L,
1617 154699 : const RHS &R) {
1618 7754 : return BinaryOp_match<LHS, RHS, Instruction::And, true>(L, R);
1619 3184 : }
1620 572259 :
1621 0 : /// Matches an Or with LHS and RHS in either order.
1622 2638 : template <typename LHS, typename RHS>
1623 705785 : inline BinaryOp_match<LHS, RHS, Instruction::Or, true> m_c_Or(const LHS &L,
1624 706599 : const RHS &R) {
1625 1204 : return BinaryOp_match<LHS, RHS, Instruction::Or, true>(L, R);
1626 303 : }
1627 8357 :
1628 8323 : /// Matches an Xor with LHS and RHS in either order.
1629 6929 : template <typename LHS, typename RHS>
1630 34173 : inline BinaryOp_match<LHS, RHS, Instruction::Xor, true> m_c_Xor(const LHS &L,
1631 3457 : const RHS &R) {
1632 0 : return BinaryOp_match<LHS, RHS, Instruction::Xor, true>(L, R);
1633 5641 : }
1634 5641 :
1635 17272 : /// Matches a 'Neg' as 'sub 0, V'.
1636 20025 : template <typename ValTy>
1637 706224 : inline BinaryOp_match<cst_pred_ty<is_zero_int>, ValTy, Instruction::Sub>
1638 706224 : m_Neg(const ValTy &V) {
1639 284 : return m_Sub(m_ZeroInt(), V);
1640 878 : }
1641 4787 :
1642 4348 : /// Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
1643 63 : template <typename ValTy>
1644 1076 : inline BinaryOp_match<ValTy, cst_pred_ty<is_all_ones>, Instruction::Xor, true>
1645 6 : m_Not(const ValTy &V) {
1646 13 : return m_c_Xor(V, m_AllOnes());
1647 469296 : }
1648 469290 :
1649 0 : /// Matches an SMin with LHS and RHS in either order.
1650 43 : template <typename LHS, typename RHS>
1651 706396 : inline MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>
1652 708040 : m_c_SMin(const LHS &L, const RHS &R) {
1653 1652 : return MaxMin_match<ICmpInst, LHS, RHS, smin_pred_ty, true>(L, R);
1654 23008 : }
1655 4 : /// Matches an SMax with LHS and RHS in either order.
1656 4 : template <typename LHS, typename RHS>
1657 8 : inline MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true>
1658 10 : m_c_SMax(const LHS &L, const RHS &R) {
1659 8 : return MaxMin_match<ICmpInst, LHS, RHS, smax_pred_ty, true>(L, R);
1660 0 : }
1661 469301 : /// Matches a UMin with LHS and RHS in either order.
1662 469293 : template <typename LHS, typename RHS>
1663 0 : inline MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true>
1664 9500 : m_c_UMin(const LHS &L, const RHS &R) {
1665 320416 : return MaxMin_match<ICmpInst, LHS, RHS, umin_pred_ty, true>(L, R);
1666 10453119 : }
1667 10132715 : /// Matches a UMax with LHS and RHS in either order.
1668 468 : template <typename LHS, typename RHS>
1669 51218 : inline MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true>
1670 51002 : m_c_UMax(const LHS &L, const RHS &R) {
1671 4856 : return MaxMin_match<ICmpInst, LHS, RHS, umax_pred_ty, true>(L, R);
1672 1159 : }
1673 1503 :
1674 1 : /// Matches FAdd with LHS and RHS in either order.
1675 137 : template <typename LHS, typename RHS>
1676 0 : inline BinaryOp_match<LHS, RHS, Instruction::FAdd, true>
1677 0 : m_c_FAdd(const LHS &L, const RHS &R) {
1678 0 : return BinaryOp_match<LHS, RHS, Instruction::FAdd, true>(L, R);
1679 3803 : }
1680 7565 :
1681 3767 : /// Matches FMul with LHS and RHS in either order.
1682 199 : template <typename LHS, typename RHS>
1683 223123 : inline BinaryOp_match<LHS, RHS, Instruction::FMul, true>
1684 223099 : m_c_FMul(const LHS &L, const RHS &R) {
1685 4891 : return BinaryOp_match<LHS, RHS, Instruction::FMul, true>(L, R);
1686 6306 : }
1687 1164 :
1688 1 : template <typename Opnd_t> struct Signum_match {
1689 761943 : Opnd_t Val;
1690 761885 : Signum_match(const Opnd_t &V) : Val(V) {}
1691 453 :
1692 7456 : template <typename OpTy> bool match(OpTy *V) {
1693 0 : unsigned TypeSize = V->getType()->getScalarSizeInBits();
1694 0 : if (TypeSize == 0)
1695 8 : return false;
1696 0 :
1697 34291 : unsigned ShiftWidth = TypeSize - 1;
1698 34291 : Value *OpL = nullptr, *OpR = nullptr;
1699 5502 :
1700 72407 : // This is the representation of signum we match:
1701 38116 : //
1702 3260223 : // signum(x) == (x >> 63) | (-x >>u 63)
1703 3665374 : //
1704 405151 : // An i1 value is its own signum, so it's correct to match
1705 3260223 : //
1706 3300483 : // signum(x) == (x >> 0) | (-x >>u 0)
1707 3262831 : //
1708 556139 : // for i1 values.
1709 553541 :
1710 553284 : auto LHS = m_AShr(m_Value(OpL), m_SpecificInt(ShiftWidth));
1711 149455 : auto RHS = m_LShr(m_Neg(m_Value(OpR)), m_SpecificInt(ShiftWidth));
1712 149254 : auto Signum = m_Or(LHS, RHS);
1713 1197 :
1714 1629780 : return Signum.match(V) && OpL == OpR && Val.match(OpL);
1715 1629688 : }
1716 1629194 : };
1717 551947 :
1718 551943 : /// Matches a signum pattern.
1719 550926 : ///
1720 15 : /// signum(x) =
1721 0 : /// x > 0 -> 1
1722 397 : /// x == 0 -> 0
1723 1631434 : /// x < 0 -> -1
1724 1631028 : template <typename Val_t> inline Signum_match<Val_t> m_Signum(const Val_t &V) {
1725 1647117 : return Signum_match<Val_t>(V);
1726 17889 : }
1727 7057 :
1728 5865 : } // end namespace PatternMatch
1729 4035 : } // end namespace llvm
1730 0 :
1731 2195 : #endif // LLVM_IR_PATTERNMATCH_H
|
