LLVM  10.0.0svn
PatternMatch.h
Go to the documentation of this file.
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/InstrTypes.h"
36 #include "llvm/IR/Instruction.h"
37 #include "llvm/IR/Instructions.h"
38 #include "llvm/IR/Intrinsics.h"
39 #include "llvm/IR/Operator.h"
40 #include "llvm/IR/Value.h"
41 #include "llvm/Support/Casting.h"
42 #include <cstdint>
43 
44 namespace llvm {
45 namespace PatternMatch {
46 
47 template <typename Val, typename Pattern> bool match(Val *V, const Pattern &P) {
48  return const_cast<Pattern &>(P).match(V);
49 }
50 
51 template <typename SubPattern_t> struct OneUse_match {
52  SubPattern_t SubPattern;
53 
54  OneUse_match(const SubPattern_t &SP) : SubPattern(SP) {}
55 
56  template <typename OpTy> bool match(OpTy *V) {
57  return V->hasOneUse() && SubPattern.match(V);
58  }
59 };
60 
61 template <typename T> inline OneUse_match<T> m_OneUse(const T &SubPattern) {
62  return SubPattern;
63 }
64 
65 template <typename Class> struct class_match {
66  template <typename ITy> bool match(ITy *V) { return isa<Class>(V); }
67 };
68 
69 /// Match an arbitrary value and ignore it.
71 
72 /// Match an arbitrary binary operation and ignore it.
75 }
76 
77 /// Matches any compare instruction and ignore it.
79 
80 /// Match an arbitrary ConstantInt and ignore it.
82  return class_match<ConstantInt>();
83 }
84 
85 /// Match an arbitrary undef constant.
87 
88 /// Match an arbitrary Constant and ignore it.
90 
91 /// Match an arbitrary basic block value and ignore it.
93  return class_match<BasicBlock>();
94 }
95 
96 /// Inverting matcher
97 template <typename Ty> struct match_unless {
98  Ty M;
99 
100  match_unless(const Ty &Matcher) : M(Matcher) {}
101 
102  template <typename ITy> bool match(ITy *V) { return !M.match(V); }
103 };
104 
105 /// Match if the inner matcher does *NOT* match.
106 template <typename Ty> inline match_unless<Ty> m_Unless(const Ty &M) {
107  return match_unless<Ty>(M);
108 }
109 
110 /// Matching combinators
111 template <typename LTy, typename RTy> struct match_combine_or {
112  LTy L;
113  RTy R;
114 
115  match_combine_or(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
116 
117  template <typename ITy> bool match(ITy *V) {
118  if (L.match(V))
119  return true;
120  if (R.match(V))
121  return true;
122  return false;
123  }
124 };
125 
126 template <typename LTy, typename RTy> struct match_combine_and {
127  LTy L;
128  RTy R;
129 
130  match_combine_and(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
131 
132  template <typename ITy> bool match(ITy *V) {
133  if (L.match(V))
134  if (R.match(V))
135  return true;
136  return false;
137  }
138 };
139 
140 /// Combine two pattern matchers matching L || R
141 template <typename LTy, typename RTy>
142 inline match_combine_or<LTy, RTy> m_CombineOr(const LTy &L, const RTy &R) {
143  return match_combine_or<LTy, RTy>(L, R);
144 }
145 
146 /// Combine two pattern matchers matching L && R
147 template <typename LTy, typename RTy>
148 inline match_combine_and<LTy, RTy> m_CombineAnd(const LTy &L, const RTy &R) {
149  return match_combine_and<LTy, RTy>(L, R);
150 }
151 
152 struct apint_match {
153  const APInt *&Res;
154 
155  apint_match(const APInt *&R) : Res(R) {}
156 
157  template <typename ITy> bool match(ITy *V) {
158  if (auto *CI = dyn_cast<ConstantInt>(V)) {
159  Res = &CI->getValue();
160  return true;
161  }
162  if (V->getType()->isVectorTy())
163  if (const auto *C = dyn_cast<Constant>(V))
164  if (auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue())) {
165  Res = &CI->getValue();
166  return true;
167  }
168  return false;
169  }
170 };
171 // Either constexpr if or renaming ConstantFP::getValueAPF to
172 // ConstantFP::getValue is needed to do it via single template
173 // function for both apint/apfloat.
175  const APFloat *&Res;
176  apfloat_match(const APFloat *&R) : Res(R) {}
177  template <typename ITy> bool match(ITy *V) {
178  if (auto *CI = dyn_cast<ConstantFP>(V)) {
179  Res = &CI->getValueAPF();
180  return true;
181  }
182  if (V->getType()->isVectorTy())
183  if (const auto *C = dyn_cast<Constant>(V))
184  if (auto *CI = dyn_cast_or_null<ConstantFP>(C->getSplatValue())) {
185  Res = &CI->getValueAPF();
186  return true;
187  }
188  return false;
189  }
190 };
191 
192 /// Match a ConstantInt or splatted ConstantVector, binding the
193 /// specified pointer to the contained APInt.
194 inline apint_match m_APInt(const APInt *&Res) { return Res; }
195 
196 /// Match a ConstantFP or splatted ConstantVector, binding the
197 /// specified pointer to the contained APFloat.
198 inline apfloat_match m_APFloat(const APFloat *&Res) { return Res; }
199 
200 template <int64_t Val> struct constantint_match {
201  template <typename ITy> bool match(ITy *V) {
202  if (const auto *CI = dyn_cast<ConstantInt>(V)) {
203  const APInt &CIV = CI->getValue();
204  if (Val >= 0)
205  return CIV == static_cast<uint64_t>(Val);
206  // If Val is negative, and CI is shorter than it, truncate to the right
207  // number of bits. If it is larger, then we have to sign extend. Just
208  // compare their negated values.
209  return -CIV == -Val;
210  }
211  return false;
212  }
213 };
214 
215 /// Match a ConstantInt with a specific value.
216 template <int64_t Val> inline constantint_match<Val> m_ConstantInt() {
217  return constantint_match<Val>();
218 }
219 
220 /// This helper class is used to match scalar and vector integer constants that
221 /// satisfy a specified predicate.
222 /// For vector constants, undefined elements are ignored.
223 template <typename Predicate> struct cst_pred_ty : public Predicate {
224  template <typename ITy> bool match(ITy *V) {
225  if (const auto *CI = dyn_cast<ConstantInt>(V))
226  return this->isValue(CI->getValue());
227  if (V->getType()->isVectorTy()) {
228  if (const auto *C = dyn_cast<Constant>(V)) {
229  if (const auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue()))
230  return this->isValue(CI->getValue());
231 
232  // Non-splat vector constant: check each element for a match.
233  unsigned NumElts = V->getType()->getVectorNumElements();
234  assert(NumElts != 0 && "Constant vector with no elements?");
235  bool HasNonUndefElements = false;
236  for (unsigned i = 0; i != NumElts; ++i) {
237  Constant *Elt = C->getAggregateElement(i);
238  if (!Elt)
239  return false;
240  if (isa<UndefValue>(Elt))
241  continue;
242  auto *CI = dyn_cast<ConstantInt>(Elt);
243  if (!CI || !this->isValue(CI->getValue()))
244  return false;
245  HasNonUndefElements = true;
246  }
247  return HasNonUndefElements;
248  }
249  }
250  return false;
251  }
252 };
253 
254 /// This helper class is used to match scalar and vector constants that
255 /// satisfy a specified predicate, and bind them to an APInt.
256 template <typename Predicate> struct api_pred_ty : public Predicate {
257  const APInt *&Res;
258 
259  api_pred_ty(const APInt *&R) : Res(R) {}
260 
261  template <typename ITy> bool match(ITy *V) {
262  if (const auto *CI = dyn_cast<ConstantInt>(V))
263  if (this->isValue(CI->getValue())) {
264  Res = &CI->getValue();
265  return true;
266  }
267  if (V->getType()->isVectorTy())
268  if (const auto *C = dyn_cast<Constant>(V))
269  if (auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue()))
270  if (this->isValue(CI->getValue())) {
271  Res = &CI->getValue();
272  return true;
273  }
274 
275  return false;
276  }
277 };
278 
279 /// This helper class is used to match scalar and vector floating-point
280 /// constants that satisfy a specified predicate.
281 /// For vector constants, undefined elements are ignored.
282 template <typename Predicate> struct cstfp_pred_ty : public Predicate {
283  template <typename ITy> bool match(ITy *V) {
284  if (const auto *CF = dyn_cast<ConstantFP>(V))
285  return this->isValue(CF->getValueAPF());
286  if (V->getType()->isVectorTy()) {
287  if (const auto *C = dyn_cast<Constant>(V)) {
288  if (const auto *CF = dyn_cast_or_null<ConstantFP>(C->getSplatValue()))
289  return this->isValue(CF->getValueAPF());
290 
291  // Non-splat vector constant: check each element for a match.
292  unsigned NumElts = V->getType()->getVectorNumElements();
293  assert(NumElts != 0 && "Constant vector with no elements?");
294  bool HasNonUndefElements = false;
295  for (unsigned i = 0; i != NumElts; ++i) {
296  Constant *Elt = C->getAggregateElement(i);
297  if (!Elt)
298  return false;
299  if (isa<UndefValue>(Elt))
300  continue;
301  auto *CF = dyn_cast<ConstantFP>(Elt);
302  if (!CF || !this->isValue(CF->getValueAPF()))
303  return false;
304  HasNonUndefElements = true;
305  }
306  return HasNonUndefElements;
307  }
308  }
309  return false;
310  }
311 };
312 
313 ///////////////////////////////////////////////////////////////////////////////
314 //
315 // Encapsulate constant value queries for use in templated predicate matchers.
316 // This allows checking if constants match using compound predicates and works
317 // with vector constants, possibly with relaxed constraints. For example, ignore
318 // undef values.
319 //
320 ///////////////////////////////////////////////////////////////////////////////
321 
322 struct is_any_apint {
323  bool isValue(const APInt &C) { return true; }
324 };
325 /// Match an integer or vector with any integral constant.
326 /// For vectors, this includes constants with undefined elements.
328  return cst_pred_ty<is_any_apint>();
329 }
330 
331 struct is_all_ones {
332  bool isValue(const APInt &C) { return C.isAllOnesValue(); }
333 };
334 /// Match an integer or vector with all bits set.
335 /// For vectors, this includes constants with undefined elements.
337  return cst_pred_ty<is_all_ones>();
338 }
339 
341  bool isValue(const APInt &C) { return C.isMaxSignedValue(); }
342 };
343 /// Match an integer or vector with values having all bits except for the high
344 /// bit set (0x7f...).
345 /// For vectors, this includes constants with undefined elements.
348 }
350  return V;
351 }
352 
353 struct is_negative {
354  bool isValue(const APInt &C) { return C.isNegative(); }
355 };
356 /// Match an integer or vector of negative values.
357 /// For vectors, this includes constants with undefined elements.
359  return cst_pred_ty<is_negative>();
360 }
362  return V;
363 }
364 
366  bool isValue(const APInt &C) { return C.isNonNegative(); }
367 };
368 /// Match an integer or vector of nonnegative values.
369 /// For vectors, this includes constants with undefined elements.
372 }
374  return V;
375 }
376 
377 struct is_one {
378  bool isValue(const APInt &C) { return C.isOneValue(); }
379 };
380 /// Match an integer 1 or a vector with all elements equal to 1.
381 /// For vectors, this includes constants with undefined elements.
383  return cst_pred_ty<is_one>();
384 }
385 
386 struct is_zero_int {
387  bool isValue(const APInt &C) { return C.isNullValue(); }
388 };
389 /// Match an integer 0 or a vector with all elements equal to 0.
390 /// For vectors, this includes constants with undefined elements.
392  return cst_pred_ty<is_zero_int>();
393 }
394 
395 struct is_zero {
396  template <typename ITy> bool match(ITy *V) {
397  auto *C = dyn_cast<Constant>(V);
398  return C && (C->isNullValue() || cst_pred_ty<is_zero_int>().match(C));
399  }
400 };
401 /// Match any null constant or a vector with all elements equal to 0.
402 /// For vectors, this includes constants with undefined elements.
403 inline is_zero m_Zero() {
404  return is_zero();
405 }
406 
407 struct is_power2 {
408  bool isValue(const APInt &C) { return C.isPowerOf2(); }
409 };
410 /// Match an integer or vector power-of-2.
411 /// For vectors, this includes constants with undefined elements.
413  return cst_pred_ty<is_power2>();
414 }
416  return V;
417 }
418 
420  bool isValue(const APInt &C) { return (-C).isPowerOf2(); }
421 };
422 /// Match a integer or vector negated power-of-2.
423 /// For vectors, this includes constants with undefined elements.
426 }
428  return V;
429 }
430 
432  bool isValue(const APInt &C) { return !C || C.isPowerOf2(); }
433 };
434 /// Match an integer or vector of 0 or power-of-2 values.
435 /// For vectors, this includes constants with undefined elements.
438 }
440  return V;
441 }
442 
443 struct is_sign_mask {
444  bool isValue(const APInt &C) { return C.isSignMask(); }
445 };
446 /// Match an integer or vector with only the sign bit(s) set.
447 /// For vectors, this includes constants with undefined elements.
449  return cst_pred_ty<is_sign_mask>();
450 }
451 
453  bool isValue(const APInt &C) { return C.isMask(); }
454 };
455 /// Match an integer or vector with only the low bit(s) set.
456 /// For vectors, this includes constants with undefined elements.
459 }
460 
463  const APInt *Thr;
464  bool isValue(const APInt &C) {
465  switch (Pred) {
466  case ICmpInst::Predicate::ICMP_EQ:
467  return C.eq(*Thr);
468  case ICmpInst::Predicate::ICMP_NE:
469  return C.ne(*Thr);
470  case ICmpInst::Predicate::ICMP_UGT:
471  return C.ugt(*Thr);
472  case ICmpInst::Predicate::ICMP_UGE:
473  return C.uge(*Thr);
474  case ICmpInst::Predicate::ICMP_ULT:
475  return C.ult(*Thr);
476  case ICmpInst::Predicate::ICMP_ULE:
477  return C.ule(*Thr);
478  case ICmpInst::Predicate::ICMP_SGT:
479  return C.sgt(*Thr);
480  case ICmpInst::Predicate::ICMP_SGE:
481  return C.sge(*Thr);
482  case ICmpInst::Predicate::ICMP_SLT:
483  return C.slt(*Thr);
484  case ICmpInst::Predicate::ICMP_SLE:
485  return C.sle(*Thr);
486  default:
487  llvm_unreachable("Unhandled ICmp predicate");
488  }
489  }
490 };
491 /// Match an integer or vector with every element comparing 'pred' (eg/ne/...)
492 /// to Threshold. For vectors, this includes constants with undefined elements.
496  P.Pred = Predicate;
497  P.Thr = &Threshold;
498  return P;
499 }
500 
501 struct is_nan {
502  bool isValue(const APFloat &C) { return C.isNaN(); }
503 };
504 /// Match an arbitrary NaN constant. This includes quiet and signalling nans.
505 /// For vectors, this includes constants with undefined elements.
507  return cstfp_pred_ty<is_nan>();
508 }
509 
511  bool isValue(const APFloat &C) { return C.isZero(); }
512 };
513 /// Match a floating-point negative zero or positive zero.
514 /// For vectors, this includes constants with undefined elements.
517 }
518 
520  bool isValue(const APFloat &C) { return C.isPosZero(); }
521 };
522 /// Match a floating-point positive zero.
523 /// For vectors, this includes constants with undefined elements.
526 }
527 
529  bool isValue(const APFloat &C) { return C.isNegZero(); }
530 };
531 /// Match a floating-point negative zero.
532 /// For vectors, this includes constants with undefined elements.
535 }
536 
537 ///////////////////////////////////////////////////////////////////////////////
538 
539 template <typename Class> struct bind_ty {
540  Class *&VR;
541 
542  bind_ty(Class *&V) : VR(V) {}
543 
544  template <typename ITy> bool match(ITy *V) {
545  if (auto *CV = dyn_cast<Class>(V)) {
546  VR = CV;
547  return true;
548  }
549  return false;
550  }
551 };
552 
553 /// Match a value, capturing it if we match.
554 inline bind_ty<Value> m_Value(Value *&V) { return V; }
555 inline bind_ty<const Value> m_Value(const Value *&V) { return V; }
556 
557 /// Match an instruction, capturing it if we match.
559 /// Match a binary operator, capturing it if we match.
561 
562 /// Match a ConstantInt, capturing the value if we match.
563 inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
564 
565 /// Match a Constant, capturing the value if we match.
566 inline bind_ty<Constant> m_Constant(Constant *&C) { return C; }
567 
568 /// Match a ConstantFP, capturing the value if we match.
570 
571 /// Match a basic block value, capturing it if we match.
572 inline bind_ty<BasicBlock> m_BasicBlock(BasicBlock *&V) { return V; }
574  return V;
575 }
576 
577 /// Match a specified Value*.
579  const Value *Val;
580 
581  specificval_ty(const Value *V) : Val(V) {}
582 
583  template <typename ITy> bool match(ITy *V) { return V == Val; }
584 };
585 
586 /// Match if we have a specific specified value.
587 inline specificval_ty m_Specific(const Value *V) { return V; }
588 
589 /// Stores a reference to the Value *, not the Value * itself,
590 /// thus can be used in commutative matchers.
591 template <typename Class> struct deferredval_ty {
592  Class *const &Val;
593 
594  deferredval_ty(Class *const &V) : Val(V) {}
595 
596  template <typename ITy> bool match(ITy *const V) { return V == Val; }
597 };
598 
599 /// A commutative-friendly version of m_Specific().
600 inline deferredval_ty<Value> m_Deferred(Value *const &V) { return V; }
602  return V;
603 }
604 
605 /// Match a specified floating point value or vector of all elements of
606 /// that value.
608  double Val;
609 
610  specific_fpval(double V) : Val(V) {}
611 
612  template <typename ITy> bool match(ITy *V) {
613  if (const auto *CFP = dyn_cast<ConstantFP>(V))
614  return CFP->isExactlyValue(Val);
615  if (V->getType()->isVectorTy())
616  if (const auto *C = dyn_cast<Constant>(V))
617  if (auto *CFP = dyn_cast_or_null<ConstantFP>(C->getSplatValue()))
618  return CFP->isExactlyValue(Val);
619  return false;
620  }
621 };
622 
623 /// Match a specific floating point value or vector with all elements
624 /// equal to the value.
625 inline specific_fpval m_SpecificFP(double V) { return specific_fpval(V); }
626 
627 /// Match a float 1.0 or vector with all elements equal to 1.0.
628 inline specific_fpval m_FPOne() { return m_SpecificFP(1.0); }
629 
631  uint64_t &VR;
632 
633  bind_const_intval_ty(uint64_t &V) : VR(V) {}
634 
635  template <typename ITy> bool match(ITy *V) {
636  if (const auto *CV = dyn_cast<ConstantInt>(V))
637  if (CV->getValue().ule(UINT64_MAX)) {
638  VR = CV->getZExtValue();
639  return true;
640  }
641  return false;
642  }
643 };
644 
645 /// Match a specified integer value or vector of all elements of that
646 /// value.
649 
650  specific_intval(APInt V) : Val(std::move(V)) {}
651 
652  template <typename ITy> bool match(ITy *V) {
653  const auto *CI = dyn_cast<ConstantInt>(V);
654  if (!CI && V->getType()->isVectorTy())
655  if (const auto *C = dyn_cast<Constant>(V))
656  CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue());
657 
658  return CI && APInt::isSameValue(CI->getValue(), Val);
659  }
660 };
661 
662 /// Match a specific integer value or vector with all elements equal to
663 /// the value.
665  return specific_intval(std::move(V));
666 }
667 
668 inline specific_intval m_SpecificInt(uint64_t V) {
669  return m_SpecificInt(APInt(64, V));
670 }
671 
672 /// Match a ConstantInt and bind to its value. This does not match
673 /// ConstantInts wider than 64-bits.
674 inline bind_const_intval_ty m_ConstantInt(uint64_t &V) { return V; }
675 
676 /// Match a specified basic block value.
679 
680  specific_bbval(BasicBlock *Val) : Val(Val) {}
681 
682  template <typename ITy> bool match(ITy *V) {
683  const auto *BB = dyn_cast<BasicBlock>(V);
684  return BB && BB == Val;
685  }
686 };
687 
688 /// Match a specific basic block value.
690  return specific_bbval(BB);
691 }
692 
693 /// A commutative-friendly version of m_Specific().
695  return BB;
696 }
698 m_Deferred(const BasicBlock *const &BB) {
699  return BB;
700 }
701 
702 //===----------------------------------------------------------------------===//
703 // Matcher for any binary operator.
704 //
705 template <typename LHS_t, typename RHS_t, bool Commutable = false>
707  LHS_t L;
708  RHS_t R;
709 
710  // The evaluation order is always stable, regardless of Commutability.
711  // The LHS is always matched first.
712  AnyBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
713 
714  template <typename OpTy> bool match(OpTy *V) {
715  if (auto *I = dyn_cast<BinaryOperator>(V))
716  return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
717  (Commutable && L.match(I->getOperand(1)) &&
718  R.match(I->getOperand(0)));
719  return false;
720  }
721 };
722 
723 template <typename LHS, typename RHS>
724 inline AnyBinaryOp_match<LHS, RHS> m_BinOp(const LHS &L, const RHS &R) {
725  return AnyBinaryOp_match<LHS, RHS>(L, R);
726 }
727 
728 //===----------------------------------------------------------------------===//
729 // Matchers for specific binary operators.
730 //
731 
732 template <typename LHS_t, typename RHS_t, unsigned Opcode,
733  bool Commutable = false>
735  LHS_t L;
736  RHS_t R;
737 
738  // The evaluation order is always stable, regardless of Commutability.
739  // The LHS is always matched first.
740  BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
741 
742  template <typename OpTy> bool match(OpTy *V) {
743  if (V->getValueID() == Value::InstructionVal + Opcode) {
744  auto *I = cast<BinaryOperator>(V);
745  return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
746  (Commutable && L.match(I->getOperand(1)) &&
747  R.match(I->getOperand(0)));
748  }
749  if (auto *CE = dyn_cast<ConstantExpr>(V))
750  return CE->getOpcode() == Opcode &&
751  ((L.match(CE->getOperand(0)) && R.match(CE->getOperand(1))) ||
752  (Commutable && L.match(CE->getOperand(1)) &&
753  R.match(CE->getOperand(0))));
754  return false;
755  }
756 };
757 
758 template <typename LHS, typename RHS>
760  const RHS &R) {
762 }
763 
764 template <typename LHS, typename RHS>
766  const RHS &R) {
768 }
769 
770 template <typename LHS, typename RHS>
772  const RHS &R) {
774 }
775 
776 template <typename LHS, typename RHS>
778  const RHS &R) {
780 }
781 
782 template <typename Op_t> struct FNeg_match {
783  Op_t X;
784 
785  FNeg_match(const Op_t &Op) : X(Op) {}
786  template <typename OpTy> bool match(OpTy *V) {
787  auto *FPMO = dyn_cast<FPMathOperator>(V);
788  if (!FPMO) return false;
789 
790  if (FPMO->getOpcode() == Instruction::FNeg)
791  return X.match(FPMO->getOperand(0));
792 
793  if (FPMO->getOpcode() == Instruction::FSub) {
794  if (FPMO->hasNoSignedZeros()) {
795  // With 'nsz', any zero goes.
796  if (!cstfp_pred_ty<is_any_zero_fp>().match(FPMO->getOperand(0)))
797  return false;
798  } else {
799  // Without 'nsz', we need fsub -0.0, X exactly.
800  if (!cstfp_pred_ty<is_neg_zero_fp>().match(FPMO->getOperand(0)))
801  return false;
802  }
803 
804  return X.match(FPMO->getOperand(1));
805  }
806 
807  return false;
808  }
809 };
810 
811 /// Match 'fneg X' as 'fsub -0.0, X'.
812 template <typename OpTy>
813 inline FNeg_match<OpTy>
814 m_FNeg(const OpTy &X) {
815  return FNeg_match<OpTy>(X);
816 }
817 
818 /// Match 'fneg X' as 'fsub +-0.0, X'.
819 template <typename RHS>
820 inline BinaryOp_match<cstfp_pred_ty<is_any_zero_fp>, RHS, Instruction::FSub>
821 m_FNegNSZ(const RHS &X) {
822  return m_FSub(m_AnyZeroFP(), X);
823 }
824 
825 template <typename LHS, typename RHS>
827  const RHS &R) {
829 }
830 
831 template <typename LHS, typename RHS>
833  const RHS &R) {
835 }
836 
837 template <typename LHS, typename RHS>
839  const RHS &R) {
841 }
842 
843 template <typename LHS, typename RHS>
845  const RHS &R) {
847 }
848 
849 template <typename LHS, typename RHS>
851  const RHS &R) {
853 }
854 
855 template <typename LHS, typename RHS>
857  const RHS &R) {
859 }
860 
861 template <typename LHS, typename RHS>
863  const RHS &R) {
865 }
866 
867 template <typename LHS, typename RHS>
869  const RHS &R) {
871 }
872 
873 template <typename LHS, typename RHS>
875  const RHS &R) {
877 }
878 
879 template <typename LHS, typename RHS>
881  const RHS &R) {
883 }
884 
885 template <typename LHS, typename RHS>
887  const RHS &R) {
889 }
890 
891 template <typename LHS, typename RHS>
893  const RHS &R) {
895 }
896 
897 template <typename LHS, typename RHS>
899  const RHS &R) {
901 }
902 
903 template <typename LHS, typename RHS>
905  const RHS &R) {
907 }
908 
909 template <typename LHS_t, typename RHS_t, unsigned Opcode,
910  unsigned WrapFlags = 0>
912  LHS_t L;
913  RHS_t R;
914 
915  OverflowingBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS)
916  : L(LHS), R(RHS) {}
917 
918  template <typename OpTy> bool match(OpTy *V) {
919  if (auto *Op = dyn_cast<OverflowingBinaryOperator>(V)) {
920  if (Op->getOpcode() != Opcode)
921  return false;
923  !Op->hasNoUnsignedWrap())
924  return false;
925  if (WrapFlags & OverflowingBinaryOperator::NoSignedWrap &&
926  !Op->hasNoSignedWrap())
927  return false;
928  return L.match(Op->getOperand(0)) && R.match(Op->getOperand(1));
929  }
930  return false;
931  }
932 };
933 
934 template <typename LHS, typename RHS>
937 m_NSWAdd(const LHS &L, const RHS &R) {
940  L, R);
941 }
942 template <typename LHS, typename RHS>
943 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
945 m_NSWSub(const LHS &L, const RHS &R) {
946  return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
948  L, R);
949 }
950 template <typename LHS, typename RHS>
951 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
953 m_NSWMul(const LHS &L, const RHS &R) {
954  return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
956  L, R);
957 }
958 template <typename LHS, typename RHS>
959 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
961 m_NSWShl(const LHS &L, const RHS &R) {
962  return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
964  L, R);
965 }
966 
967 template <typename LHS, typename RHS>
970 m_NUWAdd(const LHS &L, const RHS &R) {
973  L, R);
974 }
975 template <typename LHS, typename RHS>
976 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
978 m_NUWSub(const LHS &L, const RHS &R) {
979  return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
981  L, R);
982 }
983 template <typename LHS, typename RHS>
984 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
986 m_NUWMul(const LHS &L, const RHS &R) {
987  return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
989  L, R);
990 }
991 template <typename LHS, typename RHS>
992 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
994 m_NUWShl(const LHS &L, const RHS &R) {
995  return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
997  L, R);
998 }
999 
1000 //===----------------------------------------------------------------------===//
1001 // Class that matches a group of binary opcodes.
1002 //
1003 template <typename LHS_t, typename RHS_t, typename Predicate>
1005  LHS_t L;
1006  RHS_t R;
1007 
1008  BinOpPred_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
1009 
1010  template <typename OpTy> bool match(OpTy *V) {
1011  if (auto *I = dyn_cast<Instruction>(V))
1012  return this->isOpType(I->getOpcode()) && L.match(I->getOperand(0)) &&
1013  R.match(I->getOperand(1));
1014  if (auto *CE = dyn_cast<ConstantExpr>(V))
1015  return this->isOpType(CE->getOpcode()) && L.match(CE->getOperand(0)) &&
1016  R.match(CE->getOperand(1));
1017  return false;
1018  }
1019 };
1020 
1021 struct is_shift_op {
1022  bool isOpType(unsigned Opcode) { return Instruction::isShift(Opcode); }
1023 };
1024 
1026  bool isOpType(unsigned Opcode) {
1027  return Opcode == Instruction::LShr || Opcode == Instruction::AShr;
1028  }
1029 };
1030 
1032  bool isOpType(unsigned Opcode) {
1033  return Opcode == Instruction::LShr || Opcode == Instruction::Shl;
1034  }
1035 };
1036 
1038  bool isOpType(unsigned Opcode) {
1039  return Instruction::isBitwiseLogicOp(Opcode);
1040  }
1041 };
1042 
1043 struct is_idiv_op {
1044  bool isOpType(unsigned Opcode) {
1045  return Opcode == Instruction::SDiv || Opcode == Instruction::UDiv;
1046  }
1047 };
1048 
1049 struct is_irem_op {
1050  bool isOpType(unsigned Opcode) {
1051  return Opcode == Instruction::SRem || Opcode == Instruction::URem;
1052  }
1053 };
1054 
1055 /// Matches shift operations.
1056 template <typename LHS, typename RHS>
1058  const RHS &R) {
1060 }
1061 
1062 /// Matches logical shift operations.
1063 template <typename LHS, typename RHS>
1065  const RHS &R) {
1067 }
1068 
1069 /// Matches logical shift operations.
1070 template <typename LHS, typename RHS>
1072 m_LogicalShift(const LHS &L, const RHS &R) {
1074 }
1075 
1076 /// Matches bitwise logic operations.
1077 template <typename LHS, typename RHS>
1079 m_BitwiseLogic(const LHS &L, const RHS &R) {
1081 }
1082 
1083 /// Matches integer division operations.
1084 template <typename LHS, typename RHS>
1086  const RHS &R) {
1088 }
1089 
1090 /// Matches integer remainder operations.
1091 template <typename LHS, typename RHS>
1093  const RHS &R) {
1095 }
1096 
1097 //===----------------------------------------------------------------------===//
1098 // Class that matches exact binary ops.
1099 //
1100 template <typename SubPattern_t> struct Exact_match {
1101  SubPattern_t SubPattern;
1102 
1103  Exact_match(const SubPattern_t &SP) : SubPattern(SP) {}
1104 
1105  template <typename OpTy> bool match(OpTy *V) {
1106  if (auto *PEO = dyn_cast<PossiblyExactOperator>(V))
1107  return PEO->isExact() && SubPattern.match(V);
1108  return false;
1109  }
1110 };
1111 
1112 template <typename T> inline Exact_match<T> m_Exact(const T &SubPattern) {
1113  return SubPattern;
1114 }
1115 
1116 //===----------------------------------------------------------------------===//
1117 // Matchers for CmpInst classes
1118 //
1119 
1120 template <typename LHS_t, typename RHS_t, typename Class, typename PredicateTy,
1121  bool Commutable = false>
1123  PredicateTy &Predicate;
1124  LHS_t L;
1125  RHS_t R;
1126 
1127  // The evaluation order is always stable, regardless of Commutability.
1128  // The LHS is always matched first.
1129  CmpClass_match(PredicateTy &Pred, const LHS_t &LHS, const RHS_t &RHS)
1130  : Predicate(Pred), L(LHS), R(RHS) {}
1131 
1132  template <typename OpTy> bool match(OpTy *V) {
1133  if (auto *I = dyn_cast<Class>(V))
1134  if ((L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
1135  (Commutable && L.match(I->getOperand(1)) &&
1136  R.match(I->getOperand(0)))) {
1137  Predicate = I->getPredicate();
1138  return true;
1139  }
1140  return false;
1141  }
1142 };
1143 
1144 template <typename LHS, typename RHS>
1146 m_Cmp(CmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1148 }
1149 
1150 template <typename LHS, typename RHS>
1152 m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1154 }
1155 
1156 template <typename LHS, typename RHS>
1158 m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1160 }
1161 
1162 //===----------------------------------------------------------------------===//
1163 // Matchers for instructions with a given opcode and number of operands.
1164 //
1165 
1166 /// Matches instructions with Opcode and three operands.
1167 template <typename T0, unsigned Opcode> struct OneOps_match {
1168  T0 Op1;
1169 
1170  OneOps_match(const T0 &Op1) : Op1(Op1) {}
1171 
1172  template <typename OpTy> bool match(OpTy *V) {
1173  if (V->getValueID() == Value::InstructionVal + Opcode) {
1174  auto *I = cast<Instruction>(V);
1175  return Op1.match(I->getOperand(0));
1176  }
1177  return false;
1178  }
1179 };
1180 
1181 /// Matches instructions with Opcode and three operands.
1182 template <typename T0, typename T1, unsigned Opcode> struct TwoOps_match {
1183  T0 Op1;
1185 
1186  TwoOps_match(const T0 &Op1, const T1 &Op2) : Op1(Op1), Op2(Op2) {}
1187 
1188  template <typename OpTy> bool match(OpTy *V) {
1189  if (V->getValueID() == Value::InstructionVal + Opcode) {
1190  auto *I = cast<Instruction>(V);
1191  return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1));
1192  }
1193  return false;
1194  }
1195 };
1196 
1197 /// Matches instructions with Opcode and three operands.
1198 template <typename T0, typename T1, typename T2, unsigned Opcode>
1200  T0 Op1;
1202  T2 Op3;
1203 
1204  ThreeOps_match(const T0 &Op1, const T1 &Op2, const T2 &Op3)
1205  : Op1(Op1), Op2(Op2), Op3(Op3) {}
1206 
1207  template <typename OpTy> bool match(OpTy *V) {
1208  if (V->getValueID() == Value::InstructionVal + Opcode) {
1209  auto *I = cast<Instruction>(V);
1210  return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1)) &&
1211  Op3.match(I->getOperand(2));
1212  }
1213  return false;
1214  }
1215 };
1216 
1217 /// Matches SelectInst.
1218 template <typename Cond, typename LHS, typename RHS>
1220 m_Select(const Cond &C, const LHS &L, const RHS &R) {
1222 }
1223 
1224 /// This matches a select of two constants, e.g.:
1225 /// m_SelectCst<-1, 0>(m_Value(V))
1226 template <int64_t L, int64_t R, typename Cond>
1229 m_SelectCst(const Cond &C) {
1230  return m_Select(C, m_ConstantInt<L>(), m_ConstantInt<R>());
1231 }
1232 
1233 /// Matches InsertElementInst.
1234 template <typename Val_t, typename Elt_t, typename Idx_t>
1236 m_InsertElement(const Val_t &Val, const Elt_t &Elt, const Idx_t &Idx) {
1238  Val, Elt, Idx);
1239 }
1240 
1241 /// Matches ExtractElementInst.
1242 template <typename Val_t, typename Idx_t>
1244 m_ExtractElement(const Val_t &Val, const Idx_t &Idx) {
1246 }
1247 
1248 /// Matches ShuffleVectorInst.
1249 template <typename V1_t, typename V2_t, typename Mask_t>
1251 m_ShuffleVector(const V1_t &v1, const V2_t &v2, const Mask_t &m) {
1253  m);
1254 }
1255 
1256 /// Matches LoadInst.
1257 template <typename OpTy>
1260 }
1261 
1262 /// Matches StoreInst.
1263 template <typename ValueOpTy, typename PointerOpTy>
1265 m_Store(const ValueOpTy &ValueOp, const PointerOpTy &PointerOp) {
1267  PointerOp);
1268 }
1269 
1270 //===----------------------------------------------------------------------===//
1271 // Matchers for CastInst classes
1272 //
1273 
1274 template <typename Op_t, unsigned Opcode> struct CastClass_match {
1275  Op_t Op;
1276 
1277  CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {}
1278 
1279  template <typename OpTy> bool match(OpTy *V) {
1280  if (auto *O = dyn_cast<Operator>(V))
1281  return O->getOpcode() == Opcode && Op.match(O->getOperand(0));
1282  return false;
1283  }
1284 };
1285 
1286 /// Matches BitCast.
1287 template <typename OpTy>
1290 }
1291 
1292 /// Matches PtrToInt.
1293 template <typename OpTy>
1296 }
1297 
1298 /// Matches Trunc.
1299 template <typename OpTy>
1302 }
1303 
1304 template <typename OpTy>
1306 m_TruncOrSelf(const OpTy &Op) {
1307  return m_CombineOr(m_Trunc(Op), Op);
1308 }
1309 
1310 /// Matches SExt.
1311 template <typename OpTy>
1314 }
1315 
1316 /// Matches ZExt.
1317 template <typename OpTy>
1320 }
1321 
1322 template <typename OpTy>
1324 m_ZExtOrSelf(const OpTy &Op) {
1325  return m_CombineOr(m_ZExt(Op), Op);
1326 }
1327 
1328 template <typename OpTy>
1330 m_SExtOrSelf(const OpTy &Op) {
1331  return m_CombineOr(m_SExt(Op), Op);
1332 }
1333 
1334 template <typename OpTy>
1335 inline match_combine_or<CastClass_match<OpTy, Instruction::ZExt>,
1337 m_ZExtOrSExt(const OpTy &Op) {
1338  return m_CombineOr(m_ZExt(Op), m_SExt(Op));
1339 }
1340 
1341 template <typename OpTy>
1342 inline match_combine_or<
1343  match_combine_or<CastClass_match<OpTy, Instruction::ZExt>,
1345  OpTy>
1346 m_ZExtOrSExtOrSelf(const OpTy &Op) {
1347  return m_CombineOr(m_ZExtOrSExt(Op), Op);
1348 }
1349 
1350 /// Matches UIToFP.
1351 template <typename OpTy>
1354 }
1355 
1356 /// Matches SIToFP.
1357 template <typename OpTy>
1360 }
1361 
1362 /// Matches FPTrunc
1363 template <typename OpTy>
1366 }
1367 
1368 /// Matches FPExt
1369 template <typename OpTy>
1372 }
1373 
1374 //===----------------------------------------------------------------------===//
1375 // Matchers for control flow.
1376 //
1377 
1378 struct br_match {
1380 
1381  br_match(BasicBlock *&Succ) : Succ(Succ) {}
1382 
1383  template <typename OpTy> bool match(OpTy *V) {
1384  if (auto *BI = dyn_cast<BranchInst>(V))
1385  if (BI->isUnconditional()) {
1386  Succ = BI->getSuccessor(0);
1387  return true;
1388  }
1389  return false;
1390  }
1391 };
1392 
1393 inline br_match m_UnconditionalBr(BasicBlock *&Succ) { return br_match(Succ); }
1394 
1395 template <typename Cond_t, typename TrueBlock_t, typename FalseBlock_t>
1396 struct brc_match {
1397  Cond_t Cond;
1398  TrueBlock_t T;
1399  FalseBlock_t F;
1400 
1401  brc_match(const Cond_t &C, const TrueBlock_t &t, const FalseBlock_t &f)
1402  : Cond(C), T(t), F(f) {}
1403 
1404  template <typename OpTy> bool match(OpTy *V) {
1405  if (auto *BI = dyn_cast<BranchInst>(V))
1406  if (BI->isConditional() && Cond.match(BI->getCondition()))
1407  return T.match(BI->getSuccessor(0)) && F.match(BI->getSuccessor(1));
1408  return false;
1409  }
1410 };
1411 
1412 template <typename Cond_t>
1414 m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) {
1416  C, m_BasicBlock(T), m_BasicBlock(F));
1417 }
1418 
1419 template <typename Cond_t, typename TrueBlock_t, typename FalseBlock_t>
1421 m_Br(const Cond_t &C, const TrueBlock_t &T, const FalseBlock_t &F) {
1423 }
1424 
1425 //===----------------------------------------------------------------------===//
1426 // Matchers for max/min idioms, eg: "select (sgt x, y), x, y" -> smax(x,y).
1427 //
1428 
1429 template <typename CmpInst_t, typename LHS_t, typename RHS_t, typename Pred_t,
1430  bool Commutable = false>
1432  LHS_t L;
1433  RHS_t R;
1434 
1435  // The evaluation order is always stable, regardless of Commutability.
1436  // The LHS is always matched first.
1437  MaxMin_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
1438 
1439  template <typename OpTy> bool match(OpTy *V) {
1440  // Look for "(x pred y) ? x : y" or "(x pred y) ? y : x".
1441  auto *SI = dyn_cast<SelectInst>(V);
1442  if (!SI)
1443  return false;
1444  auto *Cmp = dyn_cast<CmpInst_t>(SI->getCondition());
1445  if (!Cmp)
1446  return false;
1447  // At this point we have a select conditioned on a comparison. Check that
1448  // it is the values returned by the select that are being compared.
1449  Value *TrueVal = SI->getTrueValue();
1450  Value *FalseVal = SI->getFalseValue();
1451  Value *LHS = Cmp->getOperand(0);
1452  Value *RHS = Cmp->getOperand(1);
1453  if ((TrueVal != LHS || FalseVal != RHS) &&
1454  (TrueVal != RHS || FalseVal != LHS))
1455  return false;
1456  typename CmpInst_t::Predicate Pred =
1457  LHS == TrueVal ? Cmp->getPredicate() : Cmp->getInversePredicate();
1458  // Does "(x pred y) ? x : y" represent the desired max/min operation?
1459  if (!Pred_t::match(Pred))
1460  return false;
1461  // It does! Bind the operands.
1462  return (L.match(LHS) && R.match(RHS)) ||
1463  (Commutable && L.match(RHS) && R.match(LHS));
1464  }
1465 };
1466 
1467 /// Helper class for identifying signed max predicates.
1469  static bool match(ICmpInst::Predicate Pred) {
1470  return Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE;
1471  }
1472 };
1473 
1474 /// Helper class for identifying signed min predicates.
1476  static bool match(ICmpInst::Predicate Pred) {
1477  return Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_SLE;
1478  }
1479 };
1480 
1481 /// Helper class for identifying unsigned max predicates.
1483  static bool match(ICmpInst::Predicate Pred) {
1484  return Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE;
1485  }
1486 };
1487 
1488 /// Helper class for identifying unsigned min predicates.
1490  static bool match(ICmpInst::Predicate Pred) {
1491  return Pred == CmpInst::ICMP_ULT || Pred == CmpInst::ICMP_ULE;
1492  }
1493 };
1494 
1495 /// Helper class for identifying ordered max predicates.
1497  static bool match(FCmpInst::Predicate Pred) {
1498  return Pred == CmpInst::FCMP_OGT || Pred == CmpInst::FCMP_OGE;
1499  }
1500 };
1501 
1502 /// Helper class for identifying ordered min predicates.
1504  static bool match(FCmpInst::Predicate Pred) {
1505  return Pred == CmpInst::FCMP_OLT || Pred == CmpInst::FCMP_OLE;
1506  }
1507 };
1508 
1509 /// Helper class for identifying unordered max predicates.
1511  static bool match(FCmpInst::Predicate Pred) {
1512  return Pred == CmpInst::FCMP_UGT || Pred == CmpInst::FCMP_UGE;
1513  }
1514 };
1515 
1516 /// Helper class for identifying unordered min predicates.
1518  static bool match(FCmpInst::Predicate Pred) {
1519  return Pred == CmpInst::FCMP_ULT || Pred == CmpInst::FCMP_ULE;
1520  }
1521 };
1522 
1523 template <typename LHS, typename RHS>
1525  const RHS &R) {
1527 }
1528 
1529 template <typename LHS, typename RHS>
1531  const RHS &R) {
1533 }
1534 
1535 template <typename LHS, typename RHS>
1537  const RHS &R) {
1539 }
1540 
1541 template <typename LHS, typename RHS>
1543  const RHS &R) {
1545 }
1546 
1547 /// Match an 'ordered' floating point maximum function.
1548 /// Floating point has one special value 'NaN'. Therefore, there is no total
1549 /// order. However, if we can ignore the 'NaN' value (for example, because of a
1550 /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum'
1551 /// semantics. In the presence of 'NaN' we have to preserve the original
1552 /// select(fcmp(ogt/ge, L, R), L, R) semantics matched by this predicate.
1553 ///
1554 /// max(L, R) iff L and R are not NaN
1555 /// m_OrdFMax(L, R) = R iff L or R are NaN
1556 template <typename LHS, typename RHS>
1558  const RHS &R) {
1560 }
1561 
1562 /// Match an 'ordered' floating point minimum function.
1563 /// Floating point has one special value 'NaN'. Therefore, there is no total
1564 /// order. However, if we can ignore the 'NaN' value (for example, because of a
1565 /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum'
1566 /// semantics. In the presence of 'NaN' we have to preserve the original
1567 /// select(fcmp(olt/le, L, R), L, R) semantics matched by this predicate.
1568 ///
1569 /// min(L, R) iff L and R are not NaN
1570 /// m_OrdFMin(L, R) = R iff L or R are NaN
1571 template <typename LHS, typename RHS>
1573  const RHS &R) {
1575 }
1576 
1577 /// Match an 'unordered' floating point maximum function.
1578 /// Floating point has one special value 'NaN'. Therefore, there is no total
1579 /// order. However, if we can ignore the 'NaN' value (for example, because of a
1580 /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum'
1581 /// semantics. In the presence of 'NaN' we have to preserve the original
1582 /// select(fcmp(ugt/ge, L, R), L, R) semantics matched by this predicate.
1583 ///
1584 /// max(L, R) iff L and R are not NaN
1585 /// m_UnordFMax(L, R) = L iff L or R are NaN
1586 template <typename LHS, typename RHS>
1588 m_UnordFMax(const LHS &L, const RHS &R) {
1590 }
1591 
1592 /// Match an 'unordered' floating point minimum function.
1593 /// Floating point has one special value 'NaN'. Therefore, there is no total
1594 /// order. However, if we can ignore the 'NaN' value (for example, because of a
1595 /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum'
1596 /// semantics. In the presence of 'NaN' we have to preserve the original
1597 /// select(fcmp(ult/le, L, R), L, R) semantics matched by this predicate.
1598 ///
1599 /// min(L, R) iff L and R are not NaN
1600 /// m_UnordFMin(L, R) = L iff L or R are NaN
1601 template <typename LHS, typename RHS>
1603 m_UnordFMin(const LHS &L, const RHS &R) {
1605 }
1606 
1607 //===----------------------------------------------------------------------===//
1608 // Matchers for overflow check patterns: e.g. (a + b) u< a
1609 //
1610 
1611 template <typename LHS_t, typename RHS_t, typename Sum_t>
1613  LHS_t L;
1614  RHS_t R;
1615  Sum_t S;
1616 
1617  UAddWithOverflow_match(const LHS_t &L, const RHS_t &R, const Sum_t &S)
1618  : L(L), R(R), S(S) {}
1619 
1620  template <typename OpTy> bool match(OpTy *V) {
1621  Value *ICmpLHS, *ICmpRHS;
1622  ICmpInst::Predicate Pred;
1623  if (!m_ICmp(Pred, m_Value(ICmpLHS), m_Value(ICmpRHS)).match(V))
1624  return false;
1625 
1626  Value *AddLHS, *AddRHS;
1627  auto AddExpr = m_Add(m_Value(AddLHS), m_Value(AddRHS));
1628 
1629  // (a + b) u< a, (a + b) u< b
1630  if (Pred == ICmpInst::ICMP_ULT)
1631  if (AddExpr.match(ICmpLHS) && (ICmpRHS == AddLHS || ICmpRHS == AddRHS))
1632  return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS);
1633 
1634  // a >u (a + b), b >u (a + b)
1635  if (Pred == ICmpInst::ICMP_UGT)
1636  if (AddExpr.match(ICmpRHS) && (ICmpLHS == AddLHS || ICmpLHS == AddRHS))
1637  return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS);
1638 
1639  // Match special-case for increment-by-1.
1640  if (Pred == ICmpInst::ICMP_EQ) {
1641  // (a + 1) == 0
1642  // (1 + a) == 0
1643  if (AddExpr.match(ICmpLHS) && m_ZeroInt().match(ICmpRHS) &&
1644  (m_One().match(AddLHS) || m_One().match(AddRHS)))
1645  return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS);
1646  // 0 == (a + 1)
1647  // 0 == (1 + a)
1648  if (m_ZeroInt().match(ICmpLHS) && AddExpr.match(ICmpRHS) &&
1649  (m_One().match(AddLHS) || m_One().match(AddRHS)))
1650  return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS);
1651  }
1652 
1653  return false;
1654  }
1655 };
1656 
1657 /// Match an icmp instruction checking for unsigned overflow on addition.
1658 ///
1659 /// S is matched to the addition whose result is being checked for overflow, and
1660 /// L and R are matched to the LHS and RHS of S.
1661 template <typename LHS_t, typename RHS_t, typename Sum_t>
1663 m_UAddWithOverflow(const LHS_t &L, const RHS_t &R, const Sum_t &S) {
1665 }
1666 
1667 template <typename Opnd_t> struct Argument_match {
1668  unsigned OpI;
1669  Opnd_t Val;
1670 
1671  Argument_match(unsigned OpIdx, const Opnd_t &V) : OpI(OpIdx), Val(V) {}
1672 
1673  template <typename OpTy> bool match(OpTy *V) {
1674  // FIXME: Should likely be switched to use `CallBase`.
1675  if (const auto *CI = dyn_cast<CallInst>(V))
1676  return Val.match(CI->getArgOperand(OpI));
1677  return false;
1678  }
1679 };
1680 
1681 /// Match an argument.
1682 template <unsigned OpI, typename Opnd_t>
1683 inline Argument_match<Opnd_t> m_Argument(const Opnd_t &Op) {
1684  return Argument_match<Opnd_t>(OpI, Op);
1685 }
1686 
1687 /// Intrinsic matchers.
1689  unsigned ID;
1690 
1691  IntrinsicID_match(Intrinsic::ID IntrID) : ID(IntrID) {}
1692 
1693  template <typename OpTy> bool match(OpTy *V) {
1694  if (const auto *CI = dyn_cast<CallInst>(V))
1695  if (const auto *F = CI->getCalledFunction())
1696  return F->getIntrinsicID() == ID;
1697  return false;
1698  }
1699 };
1700 
1701 /// Intrinsic matches are combinations of ID matchers, and argument
1702 /// matchers. Higher arity matcher are defined recursively in terms of and-ing
1703 /// them with lower arity matchers. Here's some convenient typedefs for up to
1704 /// several arguments, and more can be added as needed
1705 template <typename T0 = void, typename T1 = void, typename T2 = void,
1706  typename T3 = void, typename T4 = void, typename T5 = void,
1707  typename T6 = void, typename T7 = void, typename T8 = void,
1708  typename T9 = void, typename T10 = void>
1710 template <typename T0> struct m_Intrinsic_Ty<T0> {
1712 };
1713 template <typename T0, typename T1> struct m_Intrinsic_Ty<T0, T1> {
1714  using Ty =
1716 };
1717 template <typename T0, typename T1, typename T2>
1718 struct m_Intrinsic_Ty<T0, T1, T2> {
1719  using Ty =
1722 };
1723 template <typename T0, typename T1, typename T2, typename T3>
1724 struct m_Intrinsic_Ty<T0, T1, T2, T3> {
1725  using Ty =
1728 };
1729 
1730 /// Match intrinsic calls like this:
1731 /// m_Intrinsic<Intrinsic::fabs>(m_Value(X))
1732 template <Intrinsic::ID IntrID> inline IntrinsicID_match m_Intrinsic() {
1733  return IntrinsicID_match(IntrID);
1734 }
1735 
1736 template <Intrinsic::ID IntrID, typename T0>
1737 inline typename m_Intrinsic_Ty<T0>::Ty m_Intrinsic(const T0 &Op0) {
1738  return m_CombineAnd(m_Intrinsic<IntrID>(), m_Argument<0>(Op0));
1739 }
1740 
1741 template <Intrinsic::ID IntrID, typename T0, typename T1>
1742 inline typename m_Intrinsic_Ty<T0, T1>::Ty m_Intrinsic(const T0 &Op0,
1743  const T1 &Op1) {
1744  return m_CombineAnd(m_Intrinsic<IntrID>(Op0), m_Argument<1>(Op1));
1745 }
1746 
1747 template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2>
1748 inline typename m_Intrinsic_Ty<T0, T1, T2>::Ty
1749 m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2) {
1750  return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1), m_Argument<2>(Op2));
1751 }
1752 
1753 template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2,
1754  typename T3>
1755 inline typename m_Intrinsic_Ty<T0, T1, T2, T3>::Ty
1756 m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3) {
1757  return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2), m_Argument<3>(Op3));
1758 }
1759 
1760 // Helper intrinsic matching specializations.
1761 template <typename Opnd0>
1762 inline typename m_Intrinsic_Ty<Opnd0>::Ty m_BitReverse(const Opnd0 &Op0) {
1763  return m_Intrinsic<Intrinsic::bitreverse>(Op0);
1764 }
1765 
1766 template <typename Opnd0>
1767 inline typename m_Intrinsic_Ty<Opnd0>::Ty m_BSwap(const Opnd0 &Op0) {
1768  return m_Intrinsic<Intrinsic::bswap>(Op0);
1769 }
1770 
1771 template <typename Opnd0>
1772 inline typename m_Intrinsic_Ty<Opnd0>::Ty m_FAbs(const Opnd0 &Op0) {
1773  return m_Intrinsic<Intrinsic::fabs>(Op0);
1774 }
1775 
1776 template <typename Opnd0>
1777 inline typename m_Intrinsic_Ty<Opnd0>::Ty m_FCanonicalize(const Opnd0 &Op0) {
1778  return m_Intrinsic<Intrinsic::canonicalize>(Op0);
1779 }
1780 
1781 template <typename Opnd0, typename Opnd1>
1782 inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMin(const Opnd0 &Op0,
1783  const Opnd1 &Op1) {
1784  return m_Intrinsic<Intrinsic::minnum>(Op0, Op1);
1785 }
1786 
1787 template <typename Opnd0, typename Opnd1>
1788 inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMax(const Opnd0 &Op0,
1789  const Opnd1 &Op1) {
1790  return m_Intrinsic<Intrinsic::maxnum>(Op0, Op1);
1791 }
1792 
1793 //===----------------------------------------------------------------------===//
1794 // Matchers for two-operands operators with the operators in either order
1795 //
1796 
1797 /// Matches a BinaryOperator with LHS and RHS in either order.
1798 template <typename LHS, typename RHS>
1799 inline AnyBinaryOp_match<LHS, RHS, true> m_c_BinOp(const LHS &L, const RHS &R) {
1800  return AnyBinaryOp_match<LHS, RHS, true>(L, R);
1801 }
1802 
1803 /// Matches an ICmp with a predicate over LHS and RHS in either order.
1804 /// Does not swap the predicate.
1805 template <typename LHS, typename RHS>
1807 m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1809  R);
1810 }
1811 
1812 /// Matches a Add with LHS and RHS in either order.
1813 template <typename LHS, typename RHS>
1815  const RHS &R) {
1817 }
1818 
1819 /// Matches a Mul with LHS and RHS in either order.
1820 template <typename LHS, typename RHS>
1822  const RHS &R) {
1824 }
1825 
1826 /// Matches an And with LHS and RHS in either order.
1827 template <typename LHS, typename RHS>
1829  const RHS &R) {
1831 }
1832 
1833 /// Matches an Or with LHS and RHS in either order.
1834 template <typename LHS, typename RHS>
1836  const RHS &R) {
1838 }
1839 
1840 /// Matches an Xor with LHS and RHS in either order.
1841 template <typename LHS, typename RHS>
1843  const RHS &R) {
1845 }
1846 
1847 /// Matches a 'Neg' as 'sub 0, V'.
1848 template <typename ValTy>
1849 inline BinaryOp_match<cst_pred_ty<is_zero_int>, ValTy, Instruction::Sub>
1850 m_Neg(const ValTy &V) {
1851  return m_Sub(m_ZeroInt(), V);
1852 }
1853 
1854 /// Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
1855 template <typename ValTy>
1856 inline BinaryOp_match<ValTy, cst_pred_ty<is_all_ones>, Instruction::Xor, true>
1857 m_Not(const ValTy &V) {
1858  return m_c_Xor(V, m_AllOnes());
1859 }
1860 
1861 /// Matches an SMin with LHS and RHS in either order.
1862 template <typename LHS, typename RHS>
1864 m_c_SMin(const LHS &L, const RHS &R) {
1866 }
1867 /// Matches an SMax with LHS and RHS in either order.
1868 template <typename LHS, typename RHS>
1870 m_c_SMax(const LHS &L, const RHS &R) {
1872 }
1873 /// Matches a UMin with LHS and RHS in either order.
1874 template <typename LHS, typename RHS>
1876 m_c_UMin(const LHS &L, const RHS &R) {
1878 }
1879 /// Matches a UMax with LHS and RHS in either order.
1880 template <typename LHS, typename RHS>
1882 m_c_UMax(const LHS &L, const RHS &R) {
1884 }
1885 
1886 /// Matches FAdd with LHS and RHS in either order.
1887 template <typename LHS, typename RHS>
1889 m_c_FAdd(const LHS &L, const RHS &R) {
1891 }
1892 
1893 /// Matches FMul with LHS and RHS in either order.
1894 template <typename LHS, typename RHS>
1896 m_c_FMul(const LHS &L, const RHS &R) {
1898 }
1899 
1900 template <typename Opnd_t> struct Signum_match {
1901  Opnd_t Val;
1902  Signum_match(const Opnd_t &V) : Val(V) {}
1903 
1904  template <typename OpTy> bool match(OpTy *V) {
1905  unsigned TypeSize = V->getType()->getScalarSizeInBits();
1906  if (TypeSize == 0)
1907  return false;
1908 
1909  unsigned ShiftWidth = TypeSize - 1;
1910  Value *OpL = nullptr, *OpR = nullptr;
1911 
1912  // This is the representation of signum we match:
1913  //
1914  // signum(x) == (x >> 63) | (-x >>u 63)
1915  //
1916  // An i1 value is its own signum, so it's correct to match
1917  //
1918  // signum(x) == (x >> 0) | (-x >>u 0)
1919  //
1920  // for i1 values.
1921 
1922  auto LHS = m_AShr(m_Value(OpL), m_SpecificInt(ShiftWidth));
1923  auto RHS = m_LShr(m_Neg(m_Value(OpR)), m_SpecificInt(ShiftWidth));
1924  auto Signum = m_Or(LHS, RHS);
1925 
1926  return Signum.match(V) && OpL == OpR && Val.match(OpL);
1927  }
1928 };
1929 
1930 /// Matches a signum pattern.
1931 ///
1932 /// signum(x) =
1933 /// x > 0 -> 1
1934 /// x == 0 -> 0
1935 /// x < 0 -> -1
1936 template <typename Val_t> inline Signum_match<Val_t> m_Signum(const Val_t &V) {
1937  return Signum_match<Val_t>(V);
1938 }
1939 
1940 } // end namespace PatternMatch
1941 } // end namespace llvm
1942 
1943 #endif // LLVM_IR_PATTERNMATCH_H
MaxMin_match< ICmpInst, LHS, RHS, umin_pred_ty > m_UMin(const LHS &L, const RHS &R)
cst_pred_ty< icmp_pred_with_threshold > m_SpecificInt_ICMP(ICmpInst::Predicate Predicate, const APInt &Threshold)
Match an integer or vector with every element comparing &#39;pred&#39; (eg/ne/...) to Threshold.
Definition: PatternMatch.h:494
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:874
uint64_t CallInst * C
specific_bbval m_SpecificBB(BasicBlock *BB)
Match a specific basic block value.
Definition: PatternMatch.h:689
BinOpPred_match< LHS, RHS, is_right_shift_op > m_Shr(const LHS &L, const RHS &R)
Matches logical shift operations.
bool isValue(const APFloat &C)
Definition: PatternMatch.h:520
OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap > m_NSWSub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:945
cst_pred_ty< is_nonnegative > m_NonNegative()
Match an integer or vector of nonnegative values.
Definition: PatternMatch.h:370
m_Intrinsic_Ty< Opnd0, Opnd1 >::Ty m_FMin(const Opnd0 &Op0, const Opnd1 &Op1)
static bool match(FCmpInst::Predicate Pred)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:70
class_match< UndefValue > m_Undef()
Match an arbitrary undef constant.
Definition: PatternMatch.h:86
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
bool isSignMask() const
Check if the APInt&#39;s value is returned by getSignMask.
Definition: APInt.h:472
bool isZero() const
Definition: APFloat.h:1158
Match a specified integer value or vector of all elements of that value.
Definition: PatternMatch.h:647
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
Definition: PatternMatch.h:78
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:771
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
Definition: PatternMatch.h:403
br_match(BasicBlock *&Succ)
cst_pred_ty< is_negated_power2 > m_NegatedPower2()
Match a integer or vector negated power-of-2.
Definition: PatternMatch.h:424
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
BinaryOp_match< LHS, RHS, Instruction::Xor, true > m_c_Xor(const LHS &L, const RHS &R)
Matches an Xor with LHS and RHS in either order.
BinaryOp_match< LHS, RHS, Instruction::FAdd > m_FAdd(const LHS &L, const RHS &R)
Definition: PatternMatch.h:765
match_unless< Ty > m_Unless(const Ty &M)
Match if the inner matcher does NOT match.
Definition: PatternMatch.h:106
Matches instructions with Opcode and three operands.
m_Intrinsic_Ty< Opnd0 >::Ty m_BitReverse(const Opnd0 &Op0)
Match a specified floating point value or vector of all elements of that value.
Definition: PatternMatch.h:607
m_Intrinsic_Ty< Opnd0, Opnd1 >::Ty m_FMax(const Opnd0 &Op0, const Opnd1 &Op1)
bool isValue(const APInt &C)
Definition: PatternMatch.h:444
BinaryOp_match< LHS, RHS, Instruction::FDiv > m_FDiv(const LHS &L, const RHS &R)
Definition: PatternMatch.h:850
BinaryOp_match< LHS, RHS, Instruction::SRem > m_SRem(const LHS &L, const RHS &R)
Definition: PatternMatch.h:862
bool isValue(const APInt &C)
Definition: PatternMatch.h:387
Exact_match(const SubPattern_t &SP)
BinaryOp_match< cstfp_pred_ty< is_any_zero_fp >, RHS, Instruction::FSub > m_FNegNSZ(const RHS &X)
Match &#39;fneg X&#39; as &#39;fsub +-0.0, X&#39;.
Definition: PatternMatch.h:821
BinaryOp_match< LHS, RHS, Instruction::FAdd, true > m_c_FAdd(const LHS &L, const RHS &R)
Matches FAdd with LHS and RHS in either order.
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:826
br_match m_UnconditionalBr(BasicBlock *&Succ)
bool slt(const APInt &RHS) const
Signed less than comparison.
Definition: APInt.h:1203
This helper class is used to match scalar and vector floating-point constants that satisfy a specifie...
Definition: PatternMatch.h:282
m_Intrinsic_Ty< Opnd0 >::Ty m_FAbs(const Opnd0 &Op0)
cst_pred_ty< is_sign_mask > m_SignMask()
Match an integer or vector with only the sign bit(s) set.
Definition: PatternMatch.h:448
ThreeOps_match< Val_t, Elt_t, Idx_t, Instruction::InsertElement > m_InsertElement(const Val_t &Val, const Elt_t &Elt, const Idx_t &Idx)
Matches InsertElementInst.
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
Definition: PatternMatch.h:89
m_Intrinsic_Ty< Opnd0 >::Ty m_BSwap(const Opnd0 &Op0)
unsigned less or equal
Definition: InstrTypes.h:758
unsigned less than
Definition: InstrTypes.h:757
bool isValue(const APInt &C)
Definition: PatternMatch.h:354
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:904
static bool match(ICmpInst::Predicate Pred)
0 1 0 0 True if ordered and less than
Definition: InstrTypes.h:738
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate, true > m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Matches an ICmp with a predicate over LHS and RHS in either order.
bool sgt(const APInt &RHS) const
Signed greather than comparison.
Definition: APInt.h:1273
match_combine_or(const LTy &Left, const RTy &Right)
Definition: PatternMatch.h:115
F(f)
ThreeOps_match< V1_t, V2_t, Mask_t, Instruction::ShuffleVector > m_ShuffleVector(const V1_t &v1, const V2_t &v2, const Mask_t &m)
Matches ShuffleVectorInst.
BinaryOp_match< LHS, RHS, Instruction::FSub > m_FSub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:777
MaxMin_match< FCmpInst, LHS, RHS, ufmax_pred_ty > m_UnordFMax(const LHS &L, const RHS &R)
Match an &#39;unordered&#39; floating point maximum function.
Argument_match(unsigned OpIdx, const Opnd_t &V)
bool sle(const APInt &RHS) const
Signed less or equal comparison.
Definition: APInt.h:1238
AnyBinaryOp_match< LHS, RHS, true > m_c_BinOp(const LHS &L, const RHS &R)
Matches a BinaryOperator with LHS and RHS in either order.
cst_pred_ty< is_zero_int > m_ZeroInt()
Match an integer 0 or a vector with all elements equal to 0.
Definition: PatternMatch.h:391
Match a specified basic block value.
Definition: PatternMatch.h:677
BinOpPred_match< LHS, RHS, is_logical_shift_op > m_LogicalShift(const LHS &L, const RHS &R)
Matches logical shift operations.
Matches instructions with Opcode and three operands.
specific_fpval m_SpecificFP(double V)
Match a specific floating point value or vector with all elements equal to the value.
Definition: PatternMatch.h:625
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:47
match_combine_or< CastClass_match< OpTy, Instruction::ZExt >, OpTy > m_ZExtOrSelf(const OpTy &Op)
CmpClass_match< LHS, RHS, FCmpInst, FCmpInst::Predicate > m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Helper class for identifying signed min predicates.
Definition: BitVector.h:937
BinaryOp_match< LHS, RHS, Instruction::Xor > m_Xor(const LHS &L, const RHS &R)
Definition: PatternMatch.h:886
TwoOps_match< Val_t, Idx_t, Instruction::ExtractElement > m_ExtractElement(const Val_t &Val, const Idx_t &Idx)
Matches ExtractElementInst.
This class represents the LLVM &#39;select&#39; instruction.
bool isNonNegative() const
Determine if this APInt Value is non-negative (>= 0)
Definition: APInt.h:368
Exact_match< T > m_Exact(const T &SubPattern)
cst_pred_ty< is_lowbit_mask > m_LowBitMask()
Match an integer or vector with only the low bit(s) set.
Definition: PatternMatch.h:457
bool isValue(const APFloat &C)
Definition: PatternMatch.h:511
CastClass_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
bool isValue(const APFloat &C)
Definition: PatternMatch.h:502
cst_pred_ty< is_maxsignedvalue > m_MaxSignedValue()
Match an integer or vector with values having all bits except for the high bit set (0x7f...
Definition: PatternMatch.h:346
BinaryOp_match< LHS, RHS, Instruction::FMul, true > m_c_FMul(const LHS &L, const RHS &R)
Matches FMul with LHS and RHS in either order.
0 1 0 1 True if ordered and less than or equal
Definition: InstrTypes.h:739
ThreeOps_match(const T0 &Op1, const T1 &Op2, const T2 &Op3)
MaxMin_match< FCmpInst, LHS, RHS, ufmin_pred_ty > m_UnordFMin(const LHS &L, const RHS &R)
Match an &#39;unordered&#39; floating point minimum function.
This file implements a class to represent arbitrary precision integral constant values and operations...
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:759
bind_ty< ConstantFP > m_ConstantFP(ConstantFP *&C)
Match a ConstantFP, capturing the value if we match.
Definition: PatternMatch.h:569
bool isBitwiseLogicOp() const
Return true if this is and/or/xor.
Definition: Instruction.h:180
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWAdd(const LHS &L, const RHS &R)
Definition: PatternMatch.h:970
#define UINT64_MAX
Definition: DataTypes.h:83
cstfp_pred_ty< is_nan > m_NaN()
Match an arbitrary NaN constant.
Definition: PatternMatch.h:506
apfloat_match m_APFloat(const APFloat *&Res)
Match a ConstantFP or splatted ConstantVector, binding the specified pointer to the contained APFloat...
Definition: PatternMatch.h:198
CastClass_match< OpTy, Instruction::FPExt > m_FPExt(const OpTy &Op)
Matches FPExt.
bool ne(const APInt &RHS) const
Inequality comparison.
Definition: APInt.h:1176
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
Definition: PatternMatch.h:142
CastClass_match(const Op_t &OpMatch)
CastClass_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
CastClass_match< OpTy, Instruction::FPTrunc > m_FPTrunc(const OpTy &Op)
Matches FPTrunc.
match_combine_or< match_combine_or< CastClass_match< OpTy, Instruction::ZExt >, CastClass_match< OpTy, Instruction::SExt > >, OpTy > m_ZExtOrSExtOrSelf(const OpTy &Op)
MaxMin_match< FCmpInst, LHS, RHS, ofmin_pred_ty > m_OrdFMin(const LHS &L, const RHS &R)
Match an &#39;ordered&#39; floating point minimum function.
MaxMin_match< ICmpInst, LHS, RHS, smin_pred_ty > m_SMin(const LHS &L, const RHS &R)
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:81
UAddWithOverflow_match(const LHS_t &L, const RHS_t &R, const Sum_t &S)
cstfp_pred_ty< is_pos_zero_fp > m_PosZeroFP()
Match a floating-point positive zero.
Definition: PatternMatch.h:524
IntrinsicID_match(Intrinsic::ID IntrID)
cst_pred_ty< is_power2 > m_Power2()
Match an integer or vector power-of-2.
Definition: PatternMatch.h:412
match_combine_or< CastClass_match< OpTy, Instruction::Trunc >, OpTy > m_TruncOrSelf(const OpTy &Op)
OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWMul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:986
MaxMin_match< ICmpInst, LHS, RHS, umin_pred_ty, true > m_c_UMin(const LHS &L, const RHS &R)
Matches a UMin with LHS and RHS in either order.
static bool match(FCmpInst::Predicate Pred)
Helper class for identifying ordered min predicates.
match_combine_and(const LTy &Left, const RTy &Right)
Definition: PatternMatch.h:130
OneUse_match< T > m_OneUse(const T &SubPattern)
Definition: PatternMatch.h:61
bool isNegative() const
Determine sign of this APInt.
Definition: APInt.h:363
#define P(N)
bool isNegZero() const
Definition: APFloat.h:1174
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:898
Helper class for identifying signed max predicates.
bool isAllOnesValue() const
Determine if all bits are set.
Definition: APInt.h:395
BinOpPred_match< LHS, RHS, is_irem_op > m_IRem(const LHS &L, const RHS &R)
Matches integer remainder operations.
MaxMin_match< ICmpInst, LHS, RHS, umax_pred_ty > m_UMax(const LHS &L, const RHS &R)
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt...
Definition: PatternMatch.h:194
BinaryOp_match< LHS, RHS, Instruction::SDiv > m_SDiv(const LHS &L, const RHS &R)
Definition: PatternMatch.h:844
This helper class is used to match scalar and vector integer constants that satisfy a specified predi...
Definition: PatternMatch.h:223
BinaryOp_match< LHS, RHS, Instruction::Add, true > m_c_Add(const LHS &L, const RHS &R)
Matches a Add with LHS and RHS in either order.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWShl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:994
BinaryOp_match< LHS, RHS, Instruction::FRem > m_FRem(const LHS &L, const RHS &R)
Definition: PatternMatch.h:868
bool isOpType(unsigned Opcode)
cst_pred_ty< is_power2_or_zero > m_Power2OrZero()
Match an integer or vector of 0 or power-of-2 values.
Definition: PatternMatch.h:436
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
Definition: PatternMatch.h:880
TwoOps_match< ValueOpTy, PointerOpTy, Instruction::Store > m_Store(const ValueOpTy &ValueOp, const PointerOpTy &PointerOp)
Matches StoreInst.
bool ult(const APInt &RHS) const
Unsigned less than comparison.
Definition: APInt.h:1184
bool isNaN() const
Definition: APFloat.h:1160
CastClass_match< OpTy, Instruction::BitCast > m_BitCast(const OpTy &Op)
Matches BitCast.
This is an important base class in LLVM.
Definition: Constant.h:41
This file contains the declarations for the subclasses of Constant, which represent the different fla...
BinaryOp_match< LHS, RHS, Instruction::And, true > m_c_And(const LHS &L, const RHS &R)
Matches an And with LHS and RHS in either order.
ConstantFP - Floating Point Values [float, double].
Definition: Constants.h:263
bool isMask(unsigned numBits) const
Definition: APInt.h:494
bool isOneValue() const
Determine if this is a value of 1.
Definition: APInt.h:410
specific_intval m_SpecificInt(APInt V)
Match a specific integer value or vector with all elements equal to the value.
Definition: PatternMatch.h:664
cst_pred_ty< is_all_ones > m_AllOnes()
Match an integer or vector with all bits set.
Definition: PatternMatch.h:336
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:587
This file declares a class to represent arbitrary precision floating point values and provide a varie...
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:892
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:732
match_combine_or< CastClass_match< OpTy, Instruction::ZExt >, CastClass_match< OpTy, Instruction::SExt > > m_ZExtOrSExt(const OpTy &Op)
Helper class for identifying unsigned min predicates.
BinOpPred_match< LHS, RHS, is_bitwiselogic_op > m_BitwiseLogic(const LHS &L, const RHS &R)
Matches bitwise logic operations.
MaxMin_match< ICmpInst, LHS, RHS, smax_pred_ty, true > m_c_SMax(const LHS &L, const RHS &R)
Matches an SMax with LHS and RHS in either order.
AnyBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS)
Definition: PatternMatch.h:712
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
Definition: PatternMatch.h:73
bool eq(const APInt &RHS) const
Equality comparison.
Definition: APInt.h:1152
OneOps_match< OpTy, Instruction::Load > m_Load(const OpTy &Op)
Matches LoadInst.
Signum_match< Val_t > m_Signum(const Val_t &V)
Matches a signum pattern.
BinOpPred_match< LHS, RHS, is_idiv_op > m_IDiv(const LHS &L, const RHS &R)
Matches integer division operations.
static bool isSameValue(const APInt &I1, const APInt &I2)
Determine if two APInts have the same value, after zero-extending one of them (if needed!) to ensure ...
Definition: APInt.h:658
Helper class for identifying unordered min predicates.
1 1 0 1 True if unordered, less than, or equal
Definition: InstrTypes.h:747
BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS)
Definition: PatternMatch.h:740
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
deferredval_ty< Value > m_Deferred(Value *const &V)
A commutative-friendly version of m_Specific().
Definition: PatternMatch.h:600
signed greater than
Definition: InstrTypes.h:759
Argument_match< Opnd_t > m_Argument(const Opnd_t &Op)
Match an argument.
CastClass_match< OpTy, Instruction::SExt > m_SExt(const OpTy &Op)
Matches SExt.
MaxMin_match< ICmpInst, LHS, RHS, umax_pred_ty, true > m_c_UMax(const LHS &L, const RHS &R)
Matches a UMax with LHS and RHS in either order.
OneUse_match(const SubPattern_t &SP)
Definition: PatternMatch.h:54
0 0 1 0 True if ordered and greater than
Definition: InstrTypes.h:736
cst_pred_ty< is_negative > m_Negative()
Match an integer or vector of negative values.
Definition: PatternMatch.h:358
Intrinsic matches are combinations of ID matchers, and argument matchers.
static bool match(ICmpInst::Predicate Pred)
BinaryOp_match< LHS, RHS, Instruction::Or, true > m_c_Or(const LHS &L, const RHS &R)
Matches an Or with LHS and RHS in either order.
bool isMaxSignedValue() const
Determine if this is the largest signed value.
Definition: APInt.h:426
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
static bool match(ICmpInst::Predicate Pred)
bool isValue(const APInt &C)
Definition: PatternMatch.h:408
Match a specified Value*.
Definition: PatternMatch.h:578
1 1 0 0 True if unordered or less than
Definition: InstrTypes.h:746
Utility class for floating point operations which can have information about relaxed accuracy require...
Definition: Operator.h:245
BinaryOp_match< LHS, RHS, Instruction::URem > m_URem(const LHS &L, const RHS &R)
Definition: PatternMatch.h:856
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
Definition: PPCPredicates.h:26
BinaryOp_match< LHS, RHS, Instruction::UDiv > m_UDiv(const LHS &L, const RHS &R)
Definition: PatternMatch.h:838
signed less than
Definition: InstrTypes.h:761
bool isOpType(unsigned Opcode)
BinaryOp_match< LHS, RHS, Instruction::Mul, true > m_c_Mul(const LHS &L, const RHS &R)
Matches a Mul with LHS and RHS in either order.
Stores a reference to the Value *, not the Value * itself, thus can be used in commutative matchers...
Definition: PatternMatch.h:591
CastClass_match< OpTy, Instruction::UIToFP > m_UIToFP(const OpTy &Op)
Matches UIToFP.
brc_match(const Cond_t &C, const TrueBlock_t &t, const FalseBlock_t &f)
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
Definition: APInt.h:1292
BinaryOp_match< LHS, RHS, Instruction::FMul > m_FMul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:832
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoSignedWrap > m_NSWAdd(const LHS &L, const RHS &R)
Definition: PatternMatch.h:937
BinaryOp_match< cst_pred_ty< is_zero_int >, ValTy, Instruction::Sub > m_Neg(const ValTy &V)
Matches a &#39;Neg&#39; as &#39;sub 0, V&#39;.
signed less or equal
Definition: InstrTypes.h:762
Class for arbitrary precision integers.
Definition: APInt.h:69
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
Definition: APInt.h:1222
cstfp_pred_ty< is_neg_zero_fp > m_NegZeroFP()
Match a floating-point negative zero.
Definition: PatternMatch.h:533
bool isPowerOf2() const
Check if this APInt&#39;s value is a power of two greater than zero.
Definition: APInt.h:463
bool sge(const APInt &RHS) const
Signed greater or equal comparison.
Definition: APInt.h:1308
CastClass_match< OpTy, Instruction::PtrToInt > m_PtrToInt(const OpTy &Op)
Matches PtrToInt.
BinOpPred_match< LHS, RHS, is_shift_op > m_Shift(const LHS &L, const RHS &R)
Matches shift operations.
static cl::opt< unsigned > Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"), cl::init(100), cl::Hidden)
Helper class for identifying unsigned max predicates.
Helper class for identifying ordered max predicates.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWSub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:978
match_combine_or< CastClass_match< OpTy, Instruction::SExt >, OpTy > m_SExtOrSelf(const OpTy &Op)
specific_fpval m_FPOne()
Match a float 1.0 or vector with all elements equal to 1.0.
Definition: PatternMatch.h:628
bool ugt(const APInt &RHS) const
Unsigned greather than comparison.
Definition: APInt.h:1254
m_Intrinsic_Ty< Opnd0 >::Ty m_FCanonicalize(const Opnd0 &Op0)
FNeg_match< OpTy > m_FNeg(const OpTy &X)
Match &#39;fneg X&#39; as &#39;fsub -0.0, X&#39;.
Definition: PatternMatch.h:814
bool isPosZero() const
Definition: APFloat.h:1173
unsigned greater or equal
Definition: InstrTypes.h:756
MaxMin_match< ICmpInst, LHS, RHS, smin_pred_ty, true > m_c_SMin(const LHS &L, const RHS &R)
Matches an SMin with LHS and RHS in either order.
CmpClass_match(PredicateTy &Pred, const LHS_t &LHS, const RHS_t &RHS)
#define I(x, y, z)
Definition: MD5.cpp:58
OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoSignedWrap > m_NSWShl(const LHS &L, const RHS &R)
Definition: PatternMatch.h:961
MaxMin_match< ICmpInst, LHS, RHS, smax_pred_ty > m_SMax(const LHS &L, const RHS &R)
ThreeOps_match< Cond, constantint_match< L >, constantint_match< R >, Instruction::Select > m_SelectCst(const Cond &C)
This matches a select of two constants, e.g.
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
class_match< BasicBlock > m_BasicBlock()
Match an arbitrary basic block value and ignore it.
Definition: PatternMatch.h:92
CastClass_match< OpTy, Instruction::SIToFP > m_SIToFP(const OpTy &Op)
Matches SIToFP.
1 0 1 0 True if unordered or greater than
Definition: InstrTypes.h:744
match_unless(const Ty &Matcher)
Definition: PatternMatch.h:100
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
OverflowingBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS)
Definition: PatternMatch.h:915
Matches instructions with Opcode and three operands.
bool isOpType(unsigned Opcode)
static bool match(FCmpInst::Predicate Pred)
apfloat_match(const APFloat *&R)
Definition: PatternMatch.h:176
MaxMin_match< FCmpInst, LHS, RHS, ofmax_pred_ty > m_OrdFMax(const LHS &L, const RHS &R)
Match an &#39;ordered&#39; floating point maximum function.
Helper class for identifying unordered max predicates.
LLVM Value Representation.
Definition: Value.h:74
bool isValue(const APInt &C)
Definition: PatternMatch.h:332
bool isValue(const APInt &C)
Definition: PatternMatch.h:323
1 0 1 1 True if unordered, greater than, or equal
Definition: InstrTypes.h:745
OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoSignedWrap > m_NSWMul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:953
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
Definition: PatternMatch.h:382
static bool match(ICmpInst::Predicate Pred)
BinOpPred_match(const LHS_t &LHS, const RHS_t &RHS)
match_combine_and< LTy, RTy > m_CombineAnd(const LTy &L, const RTy &R)
Combine two pattern matchers matching L && R.
Definition: PatternMatch.h:148
static bool match(FCmpInst::Predicate Pred)
cst_pred_ty< is_any_apint > m_AnyIntegralConstant()
Match an integer or vector with any integral constant.
Definition: PatternMatch.h:327
IntrinsicID_match m_Intrinsic()
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
unsigned greater than
Definition: InstrTypes.h:755
bool isValue(const APInt &C)
Definition: PatternMatch.h:378
cstfp_pred_ty< is_any_zero_fp > m_AnyZeroFP()
Match a floating-point negative zero or positive zero.
Definition: PatternMatch.h:515
MaxMin_match(const LHS_t &LHS, const RHS_t &RHS)
0 0 1 1 True if ordered and greater than or equal
Definition: InstrTypes.h:737
bool isValue(const APFloat &C)
Definition: PatternMatch.h:529
This helper class is used to match scalar and vector constants that satisfy a specified predicate...
Definition: PatternMatch.h:256
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
Definition: PatternMatch.h:558
#define T1
BinaryOp_match< ValTy, cst_pred_ty< is_all_ones >, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a &#39;Not&#39; as &#39;xor V, -1&#39; or &#39;xor -1, V&#39;.
bool isNullValue() const
Determine if all bits are clear.
Definition: APInt.h:405
signed greater or equal
Definition: InstrTypes.h:760
TwoOps_match(const T0 &Op1, const T1 &Op2)
UAddWithOverflow_match< LHS_t, RHS_t, Sum_t > m_UAddWithOverflow(const LHS_t &L, const RHS_t &R, const Sum_t &S)
Match an icmp instruction checking for unsigned overflow on addition.
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)