LLVM  6.0.0svn
PatternMatch.h
Go to the documentation of this file.
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 template <typename Val, typename Pattern> bool match(Val *V, const Pattern &P) {
50  return const_cast<Pattern &>(P).match(V);
51 }
52 
53 template <typename SubPattern_t> struct OneUse_match {
54  SubPattern_t SubPattern;
55 
56  OneUse_match(const SubPattern_t &SP) : SubPattern(SP) {}
57 
58  template <typename OpTy> bool match(OpTy *V) {
59  return V->hasOneUse() && SubPattern.match(V);
60  }
61 };
62 
63 template <typename T> inline OneUse_match<T> m_OneUse(const T &SubPattern) {
64  return SubPattern;
65 }
66 
67 template <typename Class> struct class_match {
68  template <typename ITy> bool match(ITy *V) { return isa<Class>(V); }
69 };
70 
71 /// \brief Match an arbitrary value and ignore it.
73 
74 /// \brief Match an arbitrary binary operation and ignore it.
77 }
78 
79 /// \brief Matches any compare instruction and ignore it.
81 
82 /// \brief Match an arbitrary ConstantInt and ignore it.
84  return class_match<ConstantInt>();
85 }
86 
87 /// \brief Match an arbitrary undef constant.
89 
90 /// \brief Match an arbitrary Constant and ignore it.
92 
93 /// Matching combinators
94 template <typename LTy, typename RTy> struct match_combine_or {
95  LTy L;
96  RTy R;
97 
98  match_combine_or(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
99 
100  template <typename ITy> bool match(ITy *V) {
101  if (L.match(V))
102  return true;
103  if (R.match(V))
104  return true;
105  return false;
106  }
107 };
108 
109 template <typename LTy, typename RTy> struct match_combine_and {
110  LTy L;
111  RTy R;
112 
113  match_combine_and(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
114 
115  template <typename ITy> bool match(ITy *V) {
116  if (L.match(V))
117  if (R.match(V))
118  return true;
119  return false;
120  }
121 };
122 
123 /// Combine two pattern matchers matching L || R
124 template <typename LTy, typename RTy>
125 inline match_combine_or<LTy, RTy> m_CombineOr(const LTy &L, const RTy &R) {
126  return match_combine_or<LTy, RTy>(L, R);
127 }
128 
129 /// Combine two pattern matchers matching L && R
130 template <typename LTy, typename RTy>
131 inline match_combine_and<LTy, RTy> m_CombineAnd(const LTy &L, const RTy &R) {
132  return match_combine_and<LTy, RTy>(L, R);
133 }
134 
135 struct match_zero {
136  template <typename ITy> bool match(ITy *V) {
137  if (const auto *C = dyn_cast<Constant>(V))
138  return C->isNullValue();
139  return false;
140  }
141 };
142 
143 /// \brief Match an arbitrary zero/null constant. This includes
144 /// zero_initializer for vectors and ConstantPointerNull for pointers.
145 inline match_zero m_Zero() { return match_zero(); }
146 
148  template <typename ITy> bool match(ITy *V) {
149  if (const auto *C = dyn_cast<Constant>(V))
150  return C->isNegativeZeroValue();
151  return false;
152  }
153 };
154 
155 /// \brief Match an arbitrary zero/null constant. This includes
156 /// zero_initializer for vectors and ConstantPointerNull for pointers. For
157 /// floating point constants, this will match negative zero but not positive
158 /// zero
160 
162  template <typename ITy> bool match(ITy *V) {
163  if (const auto *C = dyn_cast<Constant>(V))
164  return C->isZeroValue();
165  return false;
166  }
167 };
168 
169 /// \brief - Match an arbitrary zero/null constant. This includes
170 /// zero_initializer for vectors and ConstantPointerNull for pointers. For
171 /// floating point constants, this will match negative zero and positive zero
173 
174 struct match_nan {
175  template <typename ITy> bool match(ITy *V) {
176  if (const auto *C = dyn_cast<ConstantFP>(V))
177  return C->isNaN();
178  return false;
179  }
180 };
181 
182 /// Match an arbitrary NaN constant. This includes quiet and signalling nans.
183 inline match_nan m_NaN() { return match_nan(); }
184 
185 struct match_one {
186  template <typename ITy> bool match(ITy *V) {
187  if (const auto *C = dyn_cast<Constant>(V))
188  return C->isOneValue();
189  return false;
190  }
191 };
192 
193 /// \brief Match an integer 1 or a vector with all elements equal to 1.
194 inline match_one m_One() { return match_one(); }
195 
197  template <typename ITy> bool match(ITy *V) {
198  if (const auto *C = dyn_cast<Constant>(V))
199  return C->isAllOnesValue();
200  return false;
201  }
202 };
203 
204 /// \brief Match an integer or vector with all bits set to true.
206 
208  template <typename ITy> bool match(ITy *V) {
209  if (const auto *C = dyn_cast<Constant>(V))
210  return C->isMinSignedValue();
211  return false;
212  }
213 };
214 
215 /// \brief Match an integer or vector with only the sign bit(s) set.
217 
218 struct apint_match {
219  const APInt *&Res;
220 
221  apint_match(const APInt *&R) : Res(R) {}
222 
223  template <typename ITy> bool match(ITy *V) {
224  if (auto *CI = dyn_cast<ConstantInt>(V)) {
225  Res = &CI->getValue();
226  return true;
227  }
228  if (V->getType()->isVectorTy())
229  if (const auto *C = dyn_cast<Constant>(V))
230  if (auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue())) {
231  Res = &CI->getValue();
232  return true;
233  }
234  return false;
235  }
236 };
237 
238 /// \brief Match a ConstantInt or splatted ConstantVector, binding the
239 /// specified pointer to the contained APInt.
240 inline apint_match m_APInt(const APInt *&Res) { return Res; }
241 
242 template <int64_t Val> struct constantint_match {
243  template <typename ITy> bool match(ITy *V) {
244  if (const auto *CI = dyn_cast<ConstantInt>(V)) {
245  const APInt &CIV = CI->getValue();
246  if (Val >= 0)
247  return CIV == static_cast<uint64_t>(Val);
248  // If Val is negative, and CI is shorter than it, truncate to the right
249  // number of bits. If it is larger, then we have to sign extend. Just
250  // compare their negated values.
251  return -CIV == -Val;
252  }
253  return false;
254  }
255 };
256 
257 /// \brief Match a ConstantInt with a specific value.
258 template <int64_t Val> inline constantint_match<Val> m_ConstantInt() {
259  return constantint_match<Val>();
260 }
261 
262 /// \brief This helper class is used to match scalar and vector constants that
263 /// satisfy a specified predicate.
264 template <typename Predicate> struct cst_pred_ty : public Predicate {
265  template <typename ITy> bool match(ITy *V) {
266  if (const auto *CI = dyn_cast<ConstantInt>(V))
267  return this->isValue(CI->getValue());
268  if (V->getType()->isVectorTy())
269  if (const auto *C = dyn_cast<Constant>(V))
270  if (const auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue()))
271  return this->isValue(CI->getValue());
272  return false;
273  }
274 };
275 
276 /// \brief This helper class is used to match scalar and vector constants that
277 /// satisfy a specified predicate, and bind them to an APInt.
278 template <typename Predicate> struct api_pred_ty : public Predicate {
279  const APInt *&Res;
280 
281  api_pred_ty(const APInt *&R) : Res(R) {}
282 
283  template <typename ITy> bool match(ITy *V) {
284  if (const auto *CI = dyn_cast<ConstantInt>(V))
285  if (this->isValue(CI->getValue())) {
286  Res = &CI->getValue();
287  return true;
288  }
289  if (V->getType()->isVectorTy())
290  if (const auto *C = dyn_cast<Constant>(V))
291  if (auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue()))
292  if (this->isValue(CI->getValue())) {
293  Res = &CI->getValue();
294  return true;
295  }
296 
297  return false;
298  }
299 };
300 
301 struct is_power2 {
302  bool isValue(const APInt &C) { return C.isPowerOf2(); }
303 };
304 
305 /// \brief Match an integer or vector power of 2.
307 inline api_pred_ty<is_power2> m_Power2(const APInt *&V) { return V; }
308 
310  bool isValue(const APInt &C) { return C.isMaxSignedValue(); }
311 };
312 
315 
316 template <typename Class> struct bind_ty {
317  Class *&VR;
318 
319  bind_ty(Class *&V) : VR(V) {}
320 
321  template <typename ITy> bool match(ITy *V) {
322  if (auto *CV = dyn_cast<Class>(V)) {
323  VR = CV;
324  return true;
325  }
326  return false;
327  }
328 };
329 
330 /// \brief Match a value, capturing it if we match.
331 inline bind_ty<Value> m_Value(Value *&V) { return V; }
332 inline bind_ty<const Value> m_Value(const Value *&V) { return V; }
333 
334 /// \brief Match an instruction, capturing it if we match.
336 /// \brief Match a binary operator, capturing it if we match.
338 
339 /// \brief Match a ConstantInt, capturing the value if we match.
340 inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
341 
342 /// \brief Match a Constant, capturing the value if we match.
343 inline bind_ty<Constant> m_Constant(Constant *&C) { return C; }
344 
345 /// \brief Match a ConstantFP, capturing the value if we match.
347 
348 /// \brief Match a specified Value*.
350  const Value *Val;
351 
352  specificval_ty(const Value *V) : Val(V) {}
353 
354  template <typename ITy> bool match(ITy *V) { return V == Val; }
355 };
356 
357 /// \brief Match if we have a specific specified value.
358 inline specificval_ty m_Specific(const Value *V) { return V; }
359 
360 /// \brief Match a specified floating point value or vector of all elements of
361 /// that value.
363  double Val;
364 
365  specific_fpval(double V) : Val(V) {}
366 
367  template <typename ITy> bool match(ITy *V) {
368  if (const auto *CFP = dyn_cast<ConstantFP>(V))
369  return CFP->isExactlyValue(Val);
370  if (V->getType()->isVectorTy())
371  if (const auto *C = dyn_cast<Constant>(V))
372  if (auto *CFP = dyn_cast_or_null<ConstantFP>(C->getSplatValue()))
373  return CFP->isExactlyValue(Val);
374  return false;
375  }
376 };
377 
378 /// \brief Match a specific floating point value or vector with all elements
379 /// equal to the value.
380 inline specific_fpval m_SpecificFP(double V) { return specific_fpval(V); }
381 
382 /// \brief Match a float 1.0 or vector with all elements equal to 1.0.
383 inline specific_fpval m_FPOne() { return m_SpecificFP(1.0); }
384 
386  uint64_t &VR;
387 
388  bind_const_intval_ty(uint64_t &V) : VR(V) {}
389 
390  template <typename ITy> bool match(ITy *V) {
391  if (const auto *CV = dyn_cast<ConstantInt>(V))
392  if (CV->getValue().ule(UINT64_MAX)) {
393  VR = CV->getZExtValue();
394  return true;
395  }
396  return false;
397  }
398 };
399 
400 /// \brief Match a specified integer value or vector of all elements of that
401 // value.
403  uint64_t Val;
404 
405  specific_intval(uint64_t V) : Val(V) {}
406 
407  template <typename ITy> bool match(ITy *V) {
408  const auto *CI = dyn_cast<ConstantInt>(V);
409  if (!CI && V->getType()->isVectorTy())
410  if (const auto *C = dyn_cast<Constant>(V))
411  CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue());
412 
413  return CI && CI->getValue() == Val;
414  }
415 };
416 
417 /// \brief Match a specific integer value or vector with all elements equal to
418 /// the value.
419 inline specific_intval m_SpecificInt(uint64_t V) { return specific_intval(V); }
420 
421 /// \brief Match a ConstantInt and bind to its value. This does not match
422 /// ConstantInts wider than 64-bits.
423 inline bind_const_intval_ty m_ConstantInt(uint64_t &V) { return V; }
424 
425 //===----------------------------------------------------------------------===//
426 // Matcher for any binary operator.
427 //
428 template <typename LHS_t, typename RHS_t, bool Commutable = false>
430  LHS_t L;
431  RHS_t R;
432 
433  AnyBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
434 
435  template <typename OpTy> bool match(OpTy *V) {
436  if (auto *I = dyn_cast<BinaryOperator>(V))
437  return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
438  (Commutable && R.match(I->getOperand(0)) &&
439  L.match(I->getOperand(1)));
440  return false;
441  }
442 };
443 
444 template <typename LHS, typename RHS>
445 inline AnyBinaryOp_match<LHS, RHS> m_BinOp(const LHS &L, const RHS &R) {
446  return AnyBinaryOp_match<LHS, RHS>(L, R);
447 }
448 
449 //===----------------------------------------------------------------------===//
450 // Matchers for specific binary operators.
451 //
452 
453 template <typename LHS_t, typename RHS_t, unsigned Opcode,
454  bool Commutable = false>
456  LHS_t L;
457  RHS_t R;
458 
459  BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
460 
461  template <typename OpTy> bool match(OpTy *V) {
462  if (V->getValueID() == Value::InstructionVal + Opcode) {
463  auto *I = cast<BinaryOperator>(V);
464  return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
465  (Commutable && R.match(I->getOperand(0)) &&
466  L.match(I->getOperand(1)));
467  }
468  if (auto *CE = dyn_cast<ConstantExpr>(V))
469  return CE->getOpcode() == Opcode &&
470  ((L.match(CE->getOperand(0)) && R.match(CE->getOperand(1))) ||
471  (Commutable && R.match(CE->getOperand(0)) &&
472  L.match(CE->getOperand(1))));
473  return false;
474  }
475 };
476 
477 template <typename LHS, typename RHS>
479  const RHS &R) {
481 }
482 
483 template <typename LHS, typename RHS>
485  const RHS &R) {
487 }
488 
489 template <typename LHS, typename RHS>
491  const RHS &R) {
493 }
494 
495 template <typename LHS, typename RHS>
497  const RHS &R) {
499 }
500 
501 template <typename LHS, typename RHS>
503  const RHS &R) {
505 }
506 
507 template <typename LHS, typename RHS>
509  const RHS &R) {
511 }
512 
513 template <typename LHS, typename RHS>
515  const RHS &R) {
517 }
518 
519 template <typename LHS, typename RHS>
521  const RHS &R) {
523 }
524 
525 template <typename LHS, typename RHS>
527  const RHS &R) {
529 }
530 
531 template <typename LHS, typename RHS>
533  const RHS &R) {
535 }
536 
537 template <typename LHS, typename RHS>
539  const RHS &R) {
541 }
542 
543 template <typename LHS, typename RHS>
545  const RHS &R) {
547 }
548 
549 template <typename LHS, typename RHS>
551  const RHS &R) {
553 }
554 
555 template <typename LHS, typename RHS>
557  const RHS &R) {
559 }
560 
561 template <typename LHS, typename RHS>
563  const RHS &R) {
565 }
566 
567 template <typename LHS, typename RHS>
569  const RHS &R) {
571 }
572 
573 template <typename LHS, typename RHS>
575  const RHS &R) {
577 }
578 
579 template <typename LHS, typename RHS>
581  const RHS &R) {
583 }
584 
585 template <typename LHS_t, typename RHS_t, unsigned Opcode,
586  unsigned WrapFlags = 0>
588  LHS_t L;
589  RHS_t R;
590 
591  OverflowingBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS)
592  : L(LHS), R(RHS) {}
593 
594  template <typename OpTy> bool match(OpTy *V) {
595  if (auto *Op = dyn_cast<OverflowingBinaryOperator>(V)) {
596  if (Op->getOpcode() != Opcode)
597  return false;
599  !Op->hasNoUnsignedWrap())
600  return false;
601  if (WrapFlags & OverflowingBinaryOperator::NoSignedWrap &&
602  !Op->hasNoSignedWrap())
603  return false;
604  return L.match(Op->getOperand(0)) && R.match(Op->getOperand(1));
605  }
606  return false;
607  }
608 };
609 
610 template <typename LHS, typename RHS>
613 m_NSWAdd(const LHS &L, const RHS &R) {
616  L, R);
617 }
618 template <typename LHS, typename RHS>
619 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
621 m_NSWSub(const LHS &L, const RHS &R) {
622  return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
624  L, R);
625 }
626 template <typename LHS, typename RHS>
627 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
629 m_NSWMul(const LHS &L, const RHS &R) {
630  return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
632  L, R);
633 }
634 template <typename LHS, typename RHS>
635 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
637 m_NSWShl(const LHS &L, const RHS &R) {
638  return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
640  L, R);
641 }
642 
643 template <typename LHS, typename RHS>
646 m_NUWAdd(const LHS &L, const RHS &R) {
649  L, R);
650 }
651 template <typename LHS, typename RHS>
652 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
654 m_NUWSub(const LHS &L, const RHS &R) {
655  return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
657  L, R);
658 }
659 template <typename LHS, typename RHS>
660 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
662 m_NUWMul(const LHS &L, const RHS &R) {
663  return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
665  L, R);
666 }
667 template <typename LHS, typename RHS>
668 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
670 m_NUWShl(const LHS &L, const RHS &R) {
671  return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
673  L, R);
674 }
675 
676 //===----------------------------------------------------------------------===//
677 // Class that matches a group of binary opcodes.
678 //
679 template <typename LHS_t, typename RHS_t, typename Predicate>
681  LHS_t L;
682  RHS_t R;
683 
684  BinOpPred_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
685 
686  template <typename OpTy> bool match(OpTy *V) {
687  if (auto *I = dyn_cast<Instruction>(V))
688  return this->isOpType(I->getOpcode()) && L.match(I->getOperand(0)) &&
689  R.match(I->getOperand(1));
690  if (auto *CE = dyn_cast<ConstantExpr>(V))
691  return this->isOpType(CE->getOpcode()) && L.match(CE->getOperand(0)) &&
692  R.match(CE->getOperand(1));
693  return false;
694  }
695 };
696 
697 struct is_shift_op {
698  bool isOpType(unsigned Opcode) { return Instruction::isShift(Opcode); }
699 };
700 
702  bool isOpType(unsigned Opcode) {
703  return Opcode == Instruction::LShr || Opcode == Instruction::AShr;
704  }
705 };
706 
708  bool isOpType(unsigned Opcode) {
709  return Opcode == Instruction::LShr || Opcode == Instruction::Shl;
710  }
711 };
712 
714  bool isOpType(unsigned Opcode) {
715  return Instruction::isBitwiseLogicOp(Opcode);
716  }
717 };
718 
719 struct is_idiv_op {
720  bool isOpType(unsigned Opcode) {
721  return Opcode == Instruction::SDiv || Opcode == Instruction::UDiv;
722  }
723 };
724 
725 /// \brief Matches shift operations.
726 template <typename LHS, typename RHS>
728  const RHS &R) {
730 }
731 
732 /// \brief Matches logical shift operations.
733 template <typename LHS, typename RHS>
735  const RHS &R) {
737 }
738 
739 /// \brief Matches logical shift operations.
740 template <typename LHS, typename RHS>
742 m_LogicalShift(const LHS &L, const RHS &R) {
744 }
745 
746 /// \brief Matches bitwise logic operations.
747 template <typename LHS, typename RHS>
749 m_BitwiseLogic(const LHS &L, const RHS &R) {
751 }
752 
753 /// \brief Matches integer division operations.
754 template <typename LHS, typename RHS>
756  const RHS &R) {
758 }
759 
760 //===----------------------------------------------------------------------===//
761 // Class that matches exact binary ops.
762 //
763 template <typename SubPattern_t> struct Exact_match {
764  SubPattern_t SubPattern;
765 
766  Exact_match(const SubPattern_t &SP) : SubPattern(SP) {}
767 
768  template <typename OpTy> bool match(OpTy *V) {
769  if (auto *PEO = dyn_cast<PossiblyExactOperator>(V))
770  return PEO->isExact() && SubPattern.match(V);
771  return false;
772  }
773 };
774 
775 template <typename T> inline Exact_match<T> m_Exact(const T &SubPattern) {
776  return SubPattern;
777 }
778 
779 //===----------------------------------------------------------------------===//
780 // Matchers for CmpInst classes
781 //
782 
783 template <typename LHS_t, typename RHS_t, typename Class, typename PredicateTy,
784  bool Commutable = false>
786  PredicateTy &Predicate;
787  LHS_t L;
788  RHS_t R;
789 
790  CmpClass_match(PredicateTy &Pred, const LHS_t &LHS, const RHS_t &RHS)
791  : Predicate(Pred), L(LHS), R(RHS) {}
792 
793  template <typename OpTy> bool match(OpTy *V) {
794  if (auto *I = dyn_cast<Class>(V))
795  if ((L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
796  (Commutable && R.match(I->getOperand(0)) &&
797  L.match(I->getOperand(1)))) {
798  Predicate = I->getPredicate();
799  return true;
800  }
801  return false;
802  }
803 };
804 
805 template <typename LHS, typename RHS>
807 m_Cmp(CmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
809 }
810 
811 template <typename LHS, typename RHS>
813 m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
815 }
816 
817 template <typename LHS, typename RHS>
819 m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
821 }
822 
823 //===----------------------------------------------------------------------===//
824 // Matchers for SelectInst classes
825 //
826 
827 template <typename Cond_t, typename LHS_t, typename RHS_t>
829  Cond_t C;
830  LHS_t L;
831  RHS_t R;
832 
833  SelectClass_match(const Cond_t &Cond, const LHS_t &LHS, const RHS_t &RHS)
834  : C(Cond), L(LHS), R(RHS) {}
835 
836  template <typename OpTy> bool match(OpTy *V) {
837  if (auto *I = dyn_cast<SelectInst>(V))
838  return C.match(I->getOperand(0)) && L.match(I->getOperand(1)) &&
839  R.match(I->getOperand(2));
840  return false;
841  }
842 };
843 
844 template <typename Cond, typename LHS, typename RHS>
845 inline SelectClass_match<Cond, LHS, RHS> m_Select(const Cond &C, const LHS &L,
846  const RHS &R) {
847  return SelectClass_match<Cond, LHS, RHS>(C, L, R);
848 }
849 
850 /// \brief This matches a select of two constants, e.g.:
851 /// m_SelectCst<-1, 0>(m_Value(V))
852 template <int64_t L, int64_t R, typename Cond>
854 m_SelectCst(const Cond &C) {
855  return m_Select(C, m_ConstantInt<L>(), m_ConstantInt<R>());
856 }
857 
858 //===----------------------------------------------------------------------===//
859 // Matchers for CastInst classes
860 //
861 
862 template <typename Op_t, unsigned Opcode> struct CastClass_match {
863  Op_t Op;
864 
865  CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {}
866 
867  template <typename OpTy> bool match(OpTy *V) {
868  if (auto *O = dyn_cast<Operator>(V))
869  return O->getOpcode() == Opcode && Op.match(O->getOperand(0));
870  return false;
871  }
872 };
873 
874 /// \brief Matches BitCast.
875 template <typename OpTy>
878 }
879 
880 /// \brief Matches PtrToInt.
881 template <typename OpTy>
884 }
885 
886 /// \brief Matches Trunc.
887 template <typename OpTy>
890 }
891 
892 /// \brief Matches SExt.
893 template <typename OpTy>
896 }
897 
898 /// \brief Matches ZExt.
899 template <typename OpTy>
902 }
903 
904 template <typename OpTy>
907 m_ZExtOrSExt(const OpTy &Op) {
908  return m_CombineOr(m_ZExt(Op), m_SExt(Op));
909 }
910 
911 /// \brief Matches UIToFP.
912 template <typename OpTy>
915 }
916 
917 /// \brief Matches SIToFP.
918 template <typename OpTy>
921 }
922 
923 /// \brief Matches FPTrunc
924 template <typename OpTy>
927 }
928 
929 /// \brief Matches FPExt
930 template <typename OpTy>
933 }
934 
935 //===----------------------------------------------------------------------===//
936 // Matchers for unary operators
937 //
938 
939 template <typename LHS_t> struct not_match {
940  LHS_t L;
941 
942  not_match(const LHS_t &LHS) : L(LHS) {}
943 
944  template <typename OpTy> bool match(OpTy *V) {
945  if (auto *O = dyn_cast<Operator>(V))
946  if (O->getOpcode() == Instruction::Xor) {
947  if (isAllOnes(O->getOperand(1)))
948  return L.match(O->getOperand(0));
949  if (isAllOnes(O->getOperand(0)))
950  return L.match(O->getOperand(1));
951  }
952  return false;
953  }
954 
955 private:
956  bool isAllOnes(Value *V) {
957  return isa<Constant>(V) && cast<Constant>(V)->isAllOnesValue();
958  }
959 };
960 
961 template <typename LHS> inline not_match<LHS> m_Not(const LHS &L) { return L; }
962 
963 template <typename LHS_t> struct neg_match {
964  LHS_t L;
965 
966  neg_match(const LHS_t &LHS) : L(LHS) {}
967 
968  template <typename OpTy> bool match(OpTy *V) {
969  if (auto *O = dyn_cast<Operator>(V))
970  if (O->getOpcode() == Instruction::Sub)
971  return matchIfNeg(O->getOperand(0), O->getOperand(1));
972  return false;
973  }
974 
975 private:
976  bool matchIfNeg(Value *LHS, Value *RHS) {
977  return ((isa<ConstantInt>(LHS) && cast<ConstantInt>(LHS)->isZero()) ||
978  isa<ConstantAggregateZero>(LHS)) &&
979  L.match(RHS);
980  }
981 };
982 
983 /// \brief Match an integer negate.
984 template <typename LHS> inline neg_match<LHS> m_Neg(const LHS &L) { return L; }
985 
986 template <typename LHS_t> struct fneg_match {
987  LHS_t L;
988 
989  fneg_match(const LHS_t &LHS) : L(LHS) {}
990 
991  template <typename OpTy> bool match(OpTy *V) {
992  if (auto *O = dyn_cast<Operator>(V))
993  if (O->getOpcode() == Instruction::FSub)
994  return matchIfFNeg(O->getOperand(0), O->getOperand(1));
995  return false;
996  }
997 
998 private:
999  bool matchIfFNeg(Value *LHS, Value *RHS) {
1000  if (const auto *C = dyn_cast<ConstantFP>(LHS))
1001  return C->isNegativeZeroValue() && L.match(RHS);
1002  return false;
1003  }
1004 };
1005 
1006 /// \brief Match a floating point negate.
1007 template <typename LHS> inline fneg_match<LHS> m_FNeg(const LHS &L) {
1008  return L;
1009 }
1010 
1011 //===----------------------------------------------------------------------===//
1012 // Matchers for control flow.
1013 //
1014 
1015 struct br_match {
1017 
1018  br_match(BasicBlock *&Succ) : Succ(Succ) {}
1019 
1020  template <typename OpTy> bool match(OpTy *V) {
1021  if (auto *BI = dyn_cast<BranchInst>(V))
1022  if (BI->isUnconditional()) {
1023  Succ = BI->getSuccessor(0);
1024  return true;
1025  }
1026  return false;
1027  }
1028 };
1029 
1030 inline br_match m_UnconditionalBr(BasicBlock *&Succ) { return br_match(Succ); }
1031 
1032 template <typename Cond_t> struct brc_match {
1033  Cond_t Cond;
1035 
1036  brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f)
1037  : Cond(C), T(t), F(f) {}
1038 
1039  template <typename OpTy> bool match(OpTy *V) {
1040  if (auto *BI = dyn_cast<BranchInst>(V))
1041  if (BI->isConditional() && Cond.match(BI->getCondition())) {
1042  T = BI->getSuccessor(0);
1043  F = BI->getSuccessor(1);
1044  return true;
1045  }
1046  return false;
1047  }
1048 };
1049 
1050 template <typename Cond_t>
1051 inline brc_match<Cond_t> m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) {
1052  return brc_match<Cond_t>(C, T, F);
1053 }
1054 
1055 //===----------------------------------------------------------------------===//
1056 // Matchers for max/min idioms, eg: "select (sgt x, y), x, y" -> smax(x,y).
1057 //
1058 
1059 template <typename CmpInst_t, typename LHS_t, typename RHS_t, typename Pred_t,
1060  bool Commutable = false>
1062  LHS_t L;
1063  RHS_t R;
1064 
1065  MaxMin_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
1066 
1067  template <typename OpTy> bool match(OpTy *V) {
1068  // Look for "(x pred y) ? x : y" or "(x pred y) ? y : x".
1069  auto *SI = dyn_cast<SelectInst>(V);
1070  if (!SI)
1071  return false;
1072  auto *Cmp = dyn_cast<CmpInst_t>(SI->getCondition());
1073  if (!Cmp)
1074  return false;
1075  // At this point we have a select conditioned on a comparison. Check that
1076  // it is the values returned by the select that are being compared.
1077  Value *TrueVal = SI->getTrueValue();
1078  Value *FalseVal = SI->getFalseValue();
1079  Value *LHS = Cmp->getOperand(0);
1080  Value *RHS = Cmp->getOperand(1);
1081  if ((TrueVal != LHS || FalseVal != RHS) &&
1082  (TrueVal != RHS || FalseVal != LHS))
1083  return false;
1084  typename CmpInst_t::Predicate Pred =
1085  LHS == TrueVal ? Cmp->getPredicate() : Cmp->getInversePredicate();
1086  // Does "(x pred y) ? x : y" represent the desired max/min operation?
1087  if (!Pred_t::match(Pred))
1088  return false;
1089  // It does! Bind the operands.
1090  return (L.match(LHS) && R.match(RHS)) ||
1091  (Commutable && R.match(LHS) && L.match(RHS));
1092  }
1093 };
1094 
1095 /// \brief Helper class for identifying signed max predicates.
1097  static bool match(ICmpInst::Predicate Pred) {
1098  return Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE;
1099  }
1100 };
1101 
1102 /// \brief Helper class for identifying signed min predicates.
1104  static bool match(ICmpInst::Predicate Pred) {
1105  return Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_SLE;
1106  }
1107 };
1108 
1109 /// \brief Helper class for identifying unsigned max predicates.
1111  static bool match(ICmpInst::Predicate Pred) {
1112  return Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE;
1113  }
1114 };
1115 
1116 /// \brief Helper class for identifying unsigned min predicates.
1118  static bool match(ICmpInst::Predicate Pred) {
1119  return Pred == CmpInst::ICMP_ULT || Pred == CmpInst::ICMP_ULE;
1120  }
1121 };
1122 
1123 /// \brief Helper class for identifying ordered max predicates.
1125  static bool match(FCmpInst::Predicate Pred) {
1126  return Pred == CmpInst::FCMP_OGT || Pred == CmpInst::FCMP_OGE;
1127  }
1128 };
1129 
1130 /// \brief Helper class for identifying ordered min predicates.
1132  static bool match(FCmpInst::Predicate Pred) {
1133  return Pred == CmpInst::FCMP_OLT || Pred == CmpInst::FCMP_OLE;
1134  }
1135 };
1136 
1137 /// \brief Helper class for identifying unordered max predicates.
1139  static bool match(FCmpInst::Predicate Pred) {
1140  return Pred == CmpInst::FCMP_UGT || Pred == CmpInst::FCMP_UGE;
1141  }
1142 };
1143 
1144 /// \brief Helper class for identifying unordered min predicates.
1146  static bool match(FCmpInst::Predicate Pred) {
1147  return Pred == CmpInst::FCMP_ULT || Pred == CmpInst::FCMP_ULE;
1148  }
1149 };
1150 
1151 template <typename LHS, typename RHS>
1153  const RHS &R) {
1155 }
1156 
1157 template <typename LHS, typename RHS>
1159  const RHS &R) {
1161 }
1162 
1163 template <typename LHS, typename RHS>
1165  const RHS &R) {
1167 }
1168 
1169 template <typename LHS, typename RHS>
1171  const RHS &R) {
1173 }
1174 
1175 /// \brief Match an 'ordered' floating point maximum function.
1176 /// Floating point has one special value 'NaN'. Therefore, there is no total
1177 /// order. However, if we can ignore the 'NaN' value (for example, because of a
1178 /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum'
1179 /// semantics. In the presence of 'NaN' we have to preserve the original
1180 /// select(fcmp(ogt/ge, L, R), L, R) semantics matched by this predicate.
1181 ///
1182 /// max(L, R) iff L and R are not NaN
1183 /// m_OrdFMax(L, R) = R iff L or R are NaN
1184 template <typename LHS, typename RHS>
1186  const RHS &R) {
1188 }
1189 
1190 /// \brief Match an 'ordered' floating point minimum function.
1191 /// Floating point has one special value 'NaN'. Therefore, there is no total
1192 /// order. However, if we can ignore the 'NaN' value (for example, because of a
1193 /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum'
1194 /// semantics. In the presence of 'NaN' we have to preserve the original
1195 /// select(fcmp(olt/le, L, R), L, R) semantics matched by this predicate.
1196 ///
1197 /// min(L, R) iff L and R are not NaN
1198 /// m_OrdFMin(L, R) = R iff L or R are NaN
1199 template <typename LHS, typename RHS>
1201  const RHS &R) {
1203 }
1204 
1205 /// \brief Match an 'unordered' floating point maximum function.
1206 /// Floating point has one special value 'NaN'. Therefore, there is no total
1207 /// order. However, if we can ignore the 'NaN' value (for example, because of a
1208 /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum'
1209 /// semantics. In the presence of 'NaN' we have to preserve the original
1210 /// select(fcmp(ugt/ge, L, R), L, R) semantics matched by this predicate.
1211 ///
1212 /// max(L, R) iff L and R are not NaN
1213 /// m_UnordFMax(L, R) = L iff L or R are NaN
1214 template <typename LHS, typename RHS>
1216 m_UnordFMax(const LHS &L, const RHS &R) {
1218 }
1219 
1220 /// \brief Match an 'unordered' floating point minimum function.
1221 /// Floating point has one special value 'NaN'. Therefore, there is no total
1222 /// order. However, if we can ignore the 'NaN' value (for example, because of a
1223 /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum'
1224 /// semantics. In the presence of 'NaN' we have to preserve the original
1225 /// select(fcmp(ult/le, L, R), L, R) semantics matched by this predicate.
1226 ///
1227 /// min(L, R) iff L and R are not NaN
1228 /// m_UnordFMin(L, R) = L iff L or R are NaN
1229 template <typename LHS, typename RHS>
1231 m_UnordFMin(const LHS &L, const RHS &R) {
1233 }
1234 
1235 //===----------------------------------------------------------------------===//
1236 // Matchers for overflow check patterns: e.g. (a + b) u< a
1237 //
1238 
1239 template <typename LHS_t, typename RHS_t, typename Sum_t>
1241  LHS_t L;
1242  RHS_t R;
1243  Sum_t S;
1244 
1245  UAddWithOverflow_match(const LHS_t &L, const RHS_t &R, const Sum_t &S)
1246  : L(L), R(R), S(S) {}
1247 
1248  template <typename OpTy> bool match(OpTy *V) {
1249  Value *ICmpLHS, *ICmpRHS;
1250  ICmpInst::Predicate Pred;
1251  if (!m_ICmp(Pred, m_Value(ICmpLHS), m_Value(ICmpRHS)).match(V))
1252  return false;
1253 
1254  Value *AddLHS, *AddRHS;
1255  auto AddExpr = m_Add(m_Value(AddLHS), m_Value(AddRHS));
1256 
1257  // (a + b) u< a, (a + b) u< b
1258  if (Pred == ICmpInst::ICMP_ULT)
1259  if (AddExpr.match(ICmpLHS) && (ICmpRHS == AddLHS || ICmpRHS == AddRHS))
1260  return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS);
1261 
1262  // a >u (a + b), b >u (a + b)
1263  if (Pred == ICmpInst::ICMP_UGT)
1264  if (AddExpr.match(ICmpRHS) && (ICmpLHS == AddLHS || ICmpLHS == AddRHS))
1265  return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS);
1266 
1267  return false;
1268  }
1269 };
1270 
1271 /// \brief Match an icmp instruction checking for unsigned overflow on addition.
1272 ///
1273 /// S is matched to the addition whose result is being checked for overflow, and
1274 /// L and R are matched to the LHS and RHS of S.
1275 template <typename LHS_t, typename RHS_t, typename Sum_t>
1277 m_UAddWithOverflow(const LHS_t &L, const RHS_t &R, const Sum_t &S) {
1279 }
1280 
1281 template <typename Opnd_t> struct Argument_match {
1282  unsigned OpI;
1283  Opnd_t Val;
1284 
1285  Argument_match(unsigned OpIdx, const Opnd_t &V) : OpI(OpIdx), Val(V) {}
1286 
1287  template <typename OpTy> bool match(OpTy *V) {
1288  CallSite CS(V);
1289  return CS.isCall() && Val.match(CS.getArgument(OpI));
1290  }
1291 };
1292 
1293 /// \brief Match an argument.
1294 template <unsigned OpI, typename Opnd_t>
1295 inline Argument_match<Opnd_t> m_Argument(const Opnd_t &Op) {
1296  return Argument_match<Opnd_t>(OpI, Op);
1297 }
1298 
1299 /// \brief Intrinsic matchers.
1301  unsigned ID;
1302 
1303  IntrinsicID_match(Intrinsic::ID IntrID) : ID(IntrID) {}
1304 
1305  template <typename OpTy> bool match(OpTy *V) {
1306  if (const auto *CI = dyn_cast<CallInst>(V))
1307  if (const auto *F = CI->getCalledFunction())
1308  return F->getIntrinsicID() == ID;
1309  return false;
1310  }
1311 };
1312 
1313 /// Intrinsic matches are combinations of ID matchers, and argument
1314 /// matchers. Higher arity matcher are defined recursively in terms of and-ing
1315 /// them with lower arity matchers. Here's some convenient typedefs for up to
1316 /// several arguments, and more can be added as needed
1317 template <typename T0 = void, typename T1 = void, typename T2 = void,
1318  typename T3 = void, typename T4 = void, typename T5 = void,
1319  typename T6 = void, typename T7 = void, typename T8 = void,
1320  typename T9 = void, typename T10 = void>
1322 template <typename T0> struct m_Intrinsic_Ty<T0> {
1324 };
1325 template <typename T0, typename T1> struct m_Intrinsic_Ty<T0, T1> {
1326  using Ty =
1328 };
1329 template <typename T0, typename T1, typename T2>
1330 struct m_Intrinsic_Ty<T0, T1, T2> {
1331  using Ty =
1334 };
1335 template <typename T0, typename T1, typename T2, typename T3>
1336 struct m_Intrinsic_Ty<T0, T1, T2, T3> {
1337  using Ty =
1340 };
1341 
1342 /// \brief Match intrinsic calls like this:
1343 /// m_Intrinsic<Intrinsic::fabs>(m_Value(X))
1344 template <Intrinsic::ID IntrID> inline IntrinsicID_match m_Intrinsic() {
1345  return IntrinsicID_match(IntrID);
1346 }
1347 
1348 template <Intrinsic::ID IntrID, typename T0>
1349 inline typename m_Intrinsic_Ty<T0>::Ty m_Intrinsic(const T0 &Op0) {
1350  return m_CombineAnd(m_Intrinsic<IntrID>(), m_Argument<0>(Op0));
1351 }
1352 
1353 template <Intrinsic::ID IntrID, typename T0, typename T1>
1354 inline typename m_Intrinsic_Ty<T0, T1>::Ty m_Intrinsic(const T0 &Op0,
1355  const T1 &Op1) {
1356  return m_CombineAnd(m_Intrinsic<IntrID>(Op0), m_Argument<1>(Op1));
1357 }
1358 
1359 template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2>
1360 inline typename m_Intrinsic_Ty<T0, T1, T2>::Ty
1361 m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2) {
1362  return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1), m_Argument<2>(Op2));
1363 }
1364 
1365 template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2,
1366  typename T3>
1367 inline typename m_Intrinsic_Ty<T0, T1, T2, T3>::Ty
1368 m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3) {
1369  return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2), m_Argument<3>(Op3));
1370 }
1371 
1372 // Helper intrinsic matching specializations.
1373 template <typename Opnd0>
1374 inline typename m_Intrinsic_Ty<Opnd0>::Ty m_BitReverse(const Opnd0 &Op0) {
1375  return m_Intrinsic<Intrinsic::bitreverse>(Op0);
1376 }
1377 
1378 template <typename Opnd0>
1379 inline typename m_Intrinsic_Ty<Opnd0>::Ty m_BSwap(const Opnd0 &Op0) {
1380  return m_Intrinsic<Intrinsic::bswap>(Op0);
1381 }
1382 
1383 template <typename Opnd0, typename Opnd1>
1384 inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMin(const Opnd0 &Op0,
1385  const Opnd1 &Op1) {
1386  return m_Intrinsic<Intrinsic::minnum>(Op0, Op1);
1387 }
1388 
1389 template <typename Opnd0, typename Opnd1>
1390 inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMax(const Opnd0 &Op0,
1391  const Opnd1 &Op1) {
1392  return m_Intrinsic<Intrinsic::maxnum>(Op0, Op1);
1393 }
1394 
1395 template <typename Opnd_t> struct Signum_match {
1396  Opnd_t Val;
1397  Signum_match(const Opnd_t &V) : Val(V) {}
1398 
1399  template <typename OpTy> bool match(OpTy *V) {
1400  unsigned TypeSize = V->getType()->getScalarSizeInBits();
1401  if (TypeSize == 0)
1402  return false;
1403 
1404  unsigned ShiftWidth = TypeSize - 1;
1405  Value *OpL = nullptr, *OpR = nullptr;
1406 
1407  // This is the representation of signum we match:
1408  //
1409  // signum(x) == (x >> 63) | (-x >>u 63)
1410  //
1411  // An i1 value is its own signum, so it's correct to match
1412  //
1413  // signum(x) == (x >> 0) | (-x >>u 0)
1414  //
1415  // for i1 values.
1416 
1417  auto LHS = m_AShr(m_Value(OpL), m_SpecificInt(ShiftWidth));
1418  auto RHS = m_LShr(m_Neg(m_Value(OpR)), m_SpecificInt(ShiftWidth));
1419  auto Signum = m_Or(LHS, RHS);
1420 
1421  return Signum.match(V) && OpL == OpR && Val.match(OpL);
1422  }
1423 };
1424 
1425 /// \brief Matches a signum pattern.
1426 ///
1427 /// signum(x) =
1428 /// x > 0 -> 1
1429 /// x == 0 -> 0
1430 /// x < 0 -> -1
1431 template <typename Val_t> inline Signum_match<Val_t> m_Signum(const Val_t &V) {
1432  return Signum_match<Val_t>(V);
1433 }
1434 
1435 //===----------------------------------------------------------------------===//
1436 // Matchers for two-operands operators with the operators in either order
1437 //
1438 
1439 /// \brief Matches a BinaryOperator with LHS and RHS in either order.
1440 template <typename LHS, typename RHS>
1441 inline AnyBinaryOp_match<LHS, RHS, true> m_c_BinOp(const LHS &L, const RHS &R) {
1442  return AnyBinaryOp_match<LHS, RHS, true>(L, R);
1443 }
1444 
1445 /// \brief Matches an ICmp with a predicate over LHS and RHS in either order.
1446 /// Does not swap the predicate.
1447 template <typename LHS, typename RHS>
1449 m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1451  R);
1452 }
1453 
1454 /// \brief Matches a Add with LHS and RHS in either order.
1455 template <typename LHS, typename RHS>
1457  const RHS &R) {
1459 }
1460 
1461 /// \brief Matches a Mul with LHS and RHS in either order.
1462 template <typename LHS, typename RHS>
1464  const RHS &R) {
1466 }
1467 
1468 /// \brief Matches an And with LHS and RHS in either order.
1469 template <typename LHS, typename RHS>
1471  const RHS &R) {
1473 }
1474 
1475 /// \brief Matches an Or with LHS and RHS in either order.
1476 template <typename LHS, typename RHS>
1478  const RHS &R) {
1480 }
1481 
1482 /// \brief Matches an Xor with LHS and RHS in either order.
1483 template <typename LHS, typename RHS>
1485  const RHS &R) {
1487 }
1488 
1489 /// Matches an SMin with LHS and RHS in either order.
1490 template <typename LHS, typename RHS>
1492 m_c_SMin(const LHS &L, const RHS &R) {
1494 }
1495 /// Matches an SMax with LHS and RHS in either order.
1496 template <typename LHS, typename RHS>
1498 m_c_SMax(const LHS &L, const RHS &R) {
1500 }
1501 /// Matches a UMin with LHS and RHS in either order.
1502 template <typename LHS, typename RHS>
1504 m_c_UMin(const LHS &L, const RHS &R) {
1506 }
1507 /// Matches a UMax with LHS and RHS in either order.
1508 template <typename LHS, typename RHS>
1510 m_c_UMax(const LHS &L, const RHS &R) {
1512 }
1513 
1514 } // end namespace PatternMatch
1515 } // end namespace llvm
1516 
1517 #endif // LLVM_IR_PATTERNMATCH_H
MaxMin_match< ICmpInst, LHS, RHS, umin_pred_ty > m_UMin(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
Definition: PatternMatch.h:550
uint64_t CallInst * C
BinOpPred_match< LHS, RHS, is_right_shift_op > m_Shr(const LHS &L, const RHS &R)
Matches logical shift operations.
Definition: PatternMatch.h:734
OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap > m_NSWSub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:621
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:72
class_match< UndefValue > m_Undef()
Match an arbitrary undef constant.
Definition: PatternMatch.h:88
Match a specified integer value or vector of all elements of that.
Definition: PatternMatch.h:402
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
Definition: PatternMatch.h:80
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:490
br_match(BasicBlock *&Succ)
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
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:484
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:362
m_Intrinsic_Ty< Opnd0, Opnd1 >::Ty m_FMax(const Opnd0 &Op0, const Opnd1 &Op1)
BinaryOp_match< LHS, RHS, Instruction::FDiv > m_FDiv(const LHS &L, const RHS &R)
Definition: PatternMatch.h:526
BinaryOp_match< LHS, RHS, Instruction::SRem > m_SRem(const LHS &L, const RHS &R)
Definition: PatternMatch.h:538
match_zero m_Zero()
Match an arbitrary zero/null constant.
Definition: PatternMatch.h:145
Exact_match(const SubPattern_t &SP)
Definition: PatternMatch.h:766
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:502
br_match m_UnconditionalBr(BasicBlock *&Succ)
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
Definition: PatternMatch.h:91
m_Intrinsic_Ty< Opnd0 >::Ty m_BSwap(const Opnd0 &Op0)
unsigned less or equal
Definition: InstrTypes.h:886
unsigned less than
Definition: InstrTypes.h:885
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:580
static bool match(ICmpInst::Predicate Pred)
0 1 0 0 True if ordered and less than
Definition: InstrTypes.h:866
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.
match_combine_or(const LTy &Left, const RTy &Right)
Definition: PatternMatch.h:98
BinaryOp_match< LHS, RHS, Instruction::FSub > m_FSub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:496
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.
fneg_match< LHS > m_FNeg(const LHS &L)
Match a floating point negate.
Argument_match(unsigned OpIdx, const Opnd_t &V)
AnyBinaryOp_match< LHS, RHS, true > m_c_BinOp(const LHS &L, const RHS &R)
Matches a BinaryOperator with LHS and RHS in either order.
BinOpPred_match< LHS, RHS, is_logical_shift_op > m_LogicalShift(const LHS &L, const RHS &R)
Matches logical shift operations.
Definition: PatternMatch.h:742
specific_fpval m_SpecificFP(double V)
Match a specific floating point value or vector with all elements equal to the value.
Definition: PatternMatch.h:380
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
CmpClass_match< LHS, RHS, FCmpInst, FCmpInst::Predicate > m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Definition: PatternMatch.h:819
Helper class for identifying signed min predicates.
BinaryOp_match< LHS, RHS, Instruction::Xor > m_Xor(const LHS &L, const RHS &R)
Definition: PatternMatch.h:562
This class represents the LLVM &#39;select&#39; instruction.
Exact_match< T > m_Exact(const T &SubPattern)
Definition: PatternMatch.h:775
static F t[256]
CastClass_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
Definition: PatternMatch.h:888
cst_pred_ty< is_maxsignedvalue > m_MaxSignedValue()
Definition: PatternMatch.h:313
0 1 0 1 True if ordered and less than or equal
Definition: InstrTypes.h:867
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...
not_match< LHS > m_Not(const LHS &L)
Definition: PatternMatch.h:961
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:478
bind_ty< ConstantFP > m_ConstantFP(ConstantFP *&C)
Match a ConstantFP, capturing the value if we match.
Definition: PatternMatch.h:346
bool isBitwiseLogicOp() const
Return true if this is and/or/xor.
Definition: Instruction.h:161
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWAdd(const LHS &L, const RHS &R)
Definition: PatternMatch.h:646
#define F(x, y, z)
Definition: MD5.cpp:55
CastClass_match< OpTy, Instruction::FPExt > m_FPExt(const OpTy &Op)
Matches FPExt.
Definition: PatternMatch.h:931
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
Definition: PatternMatch.h:125
CastClass_match(const Op_t &OpMatch)
Definition: PatternMatch.h:865
CastClass_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
Definition: PatternMatch.h:900
#define T
CastClass_match< OpTy, Instruction::FPTrunc > m_FPTrunc(const OpTy &Op)
Matches FPTrunc.
Definition: PatternMatch.h:925
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:83
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:138
UAddWithOverflow_match(const LHS_t &L, const RHS_t &R, const Sum_t &S)
IntrinsicID_match(Intrinsic::ID IntrID)
SelectClass_match< Cond, LHS, RHS > m_Select(const Cond &C, const LHS &L, const RHS &R)
Definition: PatternMatch.h:845
cst_pred_ty< is_power2 > m_Power2()
Match an integer or vector power of 2.
Definition: PatternMatch.h:306
OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWMul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:662
bool isCall() const
Return true if a CallInst is enclosed.
Definition: CallSite.h:84
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:113
OneUse_match< T > m_OneUse(const T &SubPattern)
Definition: PatternMatch.h:63
#define P(N)
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:574
Helper class for identifying signed max predicates.
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:240
BinaryOp_match< LHS, RHS, Instruction::SDiv > m_SDiv(const LHS &L, const RHS &R)
Definition: PatternMatch.h:520
This helper class is used to match scalar and vector constants that satisfy a specified predicate...
Definition: PatternMatch.h:264
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:670
BinaryOp_match< LHS, RHS, Instruction::FRem > m_FRem(const LHS &L, const RHS &R)
Definition: PatternMatch.h:544
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
Definition: PatternMatch.h:556
CastClass_match< OpTy, Instruction::BitCast > m_BitCast(const OpTy &Op)
Matches BitCast.
Definition: PatternMatch.h:876
This is an important base class in LLVM.
Definition: Constant.h:42
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:264
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:358
brc_match< Cond_t > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
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:568
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:860
match_combine_or< CastClass_match< OpTy, Instruction::ZExt >, CastClass_match< OpTy, Instruction::SExt > > m_ZExtOrSExt(const OpTy &Op)
Definition: PatternMatch.h:907
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.
Definition: PatternMatch.h:749
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:433
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
Definition: PatternMatch.h:75
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.
Definition: PatternMatch.h:755
Helper class for identifying unordered min predicates.
1 1 0 1 True if unordered, less than, or equal
Definition: InstrTypes.h:875
BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS)
Definition: PatternMatch.h:459
signed greater than
Definition: InstrTypes.h:887
Argument_match< Opnd_t > m_Argument(const Opnd_t &Op)
Match an argument.
neg_match< LHS > m_Neg(const LHS &L)
Match an integer negate.
Definition: PatternMatch.h:984
CastClass_match< OpTy, Instruction::SExt > m_SExt(const OpTy &Op)
Matches SExt.
Definition: PatternMatch.h:894
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:56
0 0 1 0 True if ordered and greater than
Definition: InstrTypes.h:864
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:420
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
static bool match(ICmpInst::Predicate Pred)
bool isValue(const APInt &C)
Definition: PatternMatch.h:302
ValTy * getArgument(unsigned ArgNo) const
Definition: CallSite.h:183
Match a specified Value*.
Definition: PatternMatch.h:349
match_any_zero m_AnyZero()
Match an arbitrary zero/null constant.
Definition: PatternMatch.h:172
1 1 0 0 True if unordered or less than
Definition: InstrTypes.h:874
brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f)
BinaryOp_match< LHS, RHS, Instruction::URem > m_URem(const LHS &L, const RHS &R)
Definition: PatternMatch.h:532
Predicate
Predicate - These are "(BI << 5) | BO" for various predicates.
Definition: PPCPredicates.h:27
BinaryOp_match< LHS, RHS, Instruction::UDiv > m_UDiv(const LHS &L, const RHS &R)
Definition: PatternMatch.h:514
signed less than
Definition: InstrTypes.h:889
bool isOpType(unsigned Opcode)
Definition: PatternMatch.h:720
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.
CastClass_match< OpTy, Instruction::UIToFP > m_UIToFP(const OpTy &Op)
Matches UIToFP.
Definition: PatternMatch.h:913
BinaryOp_match< LHS, RHS, Instruction::FMul > m_FMul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:508
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoSignedWrap > m_NSWAdd(const LHS &L, const RHS &R)
Definition: PatternMatch.h:613
signed less or equal
Definition: InstrTypes.h:890
Class for arbitrary precision integers.
Definition: APInt.h:69
not_match(const LHS_t &LHS)
Definition: PatternMatch.h:942
bool isPowerOf2() const
Check if this APInt&#39;s value is a power of two greater than zero.
Definition: APInt.h:457
CastClass_match< OpTy, Instruction::PtrToInt > m_PtrToInt(const OpTy &Op)
Matches PtrToInt.
Definition: PatternMatch.h:882
BinOpPred_match< LHS, RHS, is_shift_op > m_Shift(const LHS &L, const RHS &R)
Matches shift operations.
Definition: PatternMatch.h:727
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:654
specific_fpval m_FPOne()
Match a float 1.0 or vector with all elements equal to 1.0.
Definition: PatternMatch.h:383
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Definition: Lint.cpp:529
neg_match(const LHS_t &LHS)
Definition: PatternMatch.h:966
unsigned greater or equal
Definition: InstrTypes.h:884
match_one m_One()
Match an integer 1 or a vector with all elements equal to 1.
Definition: PatternMatch.h:194
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)
Definition: PatternMatch.h:790
#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:637
MaxMin_match< ICmpInst, LHS, RHS, smax_pred_ty > m_SMax(const LHS &L, const RHS &R)
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:323
CastClass_match< OpTy, Instruction::SIToFP > m_SIToFP(const OpTy &Op)
Matches SIToFP.
Definition: PatternMatch.h:919
1 0 1 0 True if unordered or greater than
Definition: InstrTypes.h:872
fneg_match(const LHS_t &LHS)
Definition: PatternMatch.h:989
SelectClass_match< Cond, constantint_match< L >, constantint_match< R > > m_SelectCst(const Cond &C)
This matches a select of two constants, e.g.
Definition: PatternMatch.h:854
match_neg_zero m_NegZero()
Match an arbitrary zero/null constant.
Definition: PatternMatch.h:159
OverflowingBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS)
Definition: PatternMatch.h:591
bool isOpType(unsigned Opcode)
Definition: PatternMatch.h:698
static bool match(FCmpInst::Predicate Pred)
match_all_ones m_AllOnes()
Match an integer or vector with all bits set to true.
Definition: PatternMatch.h:205
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.
match_sign_mask m_SignMask()
Match an integer or vector with only the sign bit(s) set.
Definition: PatternMatch.h:216
LLVM Value Representation.
Definition: Value.h:73
1 0 1 1 True if unordered, greater than, or equal
Definition: InstrTypes.h:873
OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoSignedWrap > m_NSWMul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:629
static bool match(ICmpInst::Predicate Pred)
BinOpPred_match(const LHS_t &LHS, const RHS_t &RHS)
Definition: PatternMatch.h:684
match_combine_and< LTy, RTy > m_CombineAnd(const LTy &L, const RTy &R)
Combine two pattern matchers matching L && R.
Definition: PatternMatch.h:131
static bool match(FCmpInst::Predicate Pred)
IntrinsicID_match m_Intrinsic()
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
unsigned greater than
Definition: InstrTypes.h:883
match_nan m_NaN()
Match an arbitrary NaN constant. This includes quiet and signalling nans.
Definition: PatternMatch.h:183
specific_intval m_SpecificInt(uint64_t V)
Match a specific integer value or vector with all elements equal to the value.
Definition: PatternMatch.h:419
MaxMin_match(const LHS_t &LHS, const RHS_t &RHS)
SelectClass_match(const Cond_t &Cond, const LHS_t &LHS, const RHS_t &RHS)
Definition: PatternMatch.h:833
0 0 1 1 True if ordered and greater than or equal
Definition: InstrTypes.h:865
This helper class is used to match scalar and vector constants that satisfy a specified predicate...
Definition: PatternMatch.h:278
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
Definition: PatternMatch.h:335
#define T1
signed greater or equal
Definition: InstrTypes.h:888
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)
Definition: PatternMatch.h:813