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 // Either constexpr if or renaming ConstantFP::getValueAPF to
238 // ConstantFP::getValue is needed to do it via single template
239 // function for both apint/apfloat.
241  const APFloat *&Res;
242  apfloat_match(const APFloat *&R) : Res(R) {}
243  template <typename ITy> bool match(ITy *V) {
244  if (auto *CI = dyn_cast<ConstantFP>(V)) {
245  Res = &CI->getValueAPF();
246  return true;
247  }
248  if (V->getType()->isVectorTy())
249  if (const auto *C = dyn_cast<Constant>(V))
250  if (auto *CI = dyn_cast_or_null<ConstantFP>(C->getSplatValue())) {
251  Res = &CI->getValueAPF();
252  return true;
253  }
254  return false;
255  }
256 };
257 
258 /// \brief Match a ConstantInt or splatted ConstantVector, binding the
259 /// specified pointer to the contained APInt.
260 inline apint_match m_APInt(const APInt *&Res) { return Res; }
261 
262 /// \brief Match a ConstantFP or splatted ConstantVector, binding the
263 /// specified pointer to the contained APFloat.
264 inline apfloat_match m_APFloat(const APFloat *&Res) { return Res; }
265 
266 template <int64_t Val> struct constantint_match {
267  template <typename ITy> bool match(ITy *V) {
268  if (const auto *CI = dyn_cast<ConstantInt>(V)) {
269  const APInt &CIV = CI->getValue();
270  if (Val >= 0)
271  return CIV == static_cast<uint64_t>(Val);
272  // If Val is negative, and CI is shorter than it, truncate to the right
273  // number of bits. If it is larger, then we have to sign extend. Just
274  // compare their negated values.
275  return -CIV == -Val;
276  }
277  return false;
278  }
279 };
280 
281 /// \brief Match a ConstantInt with a specific value.
282 template <int64_t Val> inline constantint_match<Val> m_ConstantInt() {
283  return constantint_match<Val>();
284 }
285 
286 /// \brief This helper class is used to match scalar and vector constants that
287 /// satisfy a specified predicate.
288 template <typename Predicate> struct cst_pred_ty : public Predicate {
289  template <typename ITy> bool match(ITy *V) {
290  if (const auto *CI = dyn_cast<ConstantInt>(V))
291  return this->isValue(CI->getValue());
292  if (V->getType()->isVectorTy())
293  if (const auto *C = dyn_cast<Constant>(V))
294  if (const auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue()))
295  return this->isValue(CI->getValue());
296  return false;
297  }
298 };
299 
300 /// \brief This helper class is used to match scalar and vector constants that
301 /// satisfy a specified predicate, and bind them to an APInt.
302 template <typename Predicate> struct api_pred_ty : public Predicate {
303  const APInt *&Res;
304 
305  api_pred_ty(const APInt *&R) : Res(R) {}
306 
307  template <typename ITy> bool match(ITy *V) {
308  if (const auto *CI = dyn_cast<ConstantInt>(V))
309  if (this->isValue(CI->getValue())) {
310  Res = &CI->getValue();
311  return true;
312  }
313  if (V->getType()->isVectorTy())
314  if (const auto *C = dyn_cast<Constant>(V))
315  if (auto *CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue()))
316  if (this->isValue(CI->getValue())) {
317  Res = &CI->getValue();
318  return true;
319  }
320 
321  return false;
322  }
323 };
324 
325 struct is_power2 {
326  bool isValue(const APInt &C) { return C.isPowerOf2(); }
327 };
328 
329 /// \brief Match an integer or vector power of 2.
331 inline api_pred_ty<is_power2> m_Power2(const APInt *&V) { return V; }
332 
334  bool isValue(const APInt &C) { return C.isMaxSignedValue(); }
335 };
336 
339 
340 template <typename Class> struct bind_ty {
341  Class *&VR;
342 
343  bind_ty(Class *&V) : VR(V) {}
344 
345  template <typename ITy> bool match(ITy *V) {
346  if (auto *CV = dyn_cast<Class>(V)) {
347  VR = CV;
348  return true;
349  }
350  return false;
351  }
352 };
353 
354 /// \brief Match a value, capturing it if we match.
355 inline bind_ty<Value> m_Value(Value *&V) { return V; }
356 inline bind_ty<const Value> m_Value(const Value *&V) { return V; }
357 
358 /// \brief Match an instruction, capturing it if we match.
360 /// \brief Match a binary operator, capturing it if we match.
362 
363 /// \brief Match a ConstantInt, capturing the value if we match.
364 inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
365 
366 /// \brief Match a Constant, capturing the value if we match.
367 inline bind_ty<Constant> m_Constant(Constant *&C) { return C; }
368 
369 /// \brief Match a ConstantFP, capturing the value if we match.
371 
372 /// \brief Match a specified Value*.
374  const Value *Val;
375 
376  specificval_ty(const Value *V) : Val(V) {}
377 
378  template <typename ITy> bool match(ITy *V) { return V == Val; }
379 };
380 
381 /// \brief Match if we have a specific specified value.
382 inline specificval_ty m_Specific(const Value *V) { return V; }
383 
384 /// \brief Match a specified floating point value or vector of all elements of
385 /// that value.
387  double Val;
388 
389  specific_fpval(double V) : Val(V) {}
390 
391  template <typename ITy> bool match(ITy *V) {
392  if (const auto *CFP = dyn_cast<ConstantFP>(V))
393  return CFP->isExactlyValue(Val);
394  if (V->getType()->isVectorTy())
395  if (const auto *C = dyn_cast<Constant>(V))
396  if (auto *CFP = dyn_cast_or_null<ConstantFP>(C->getSplatValue()))
397  return CFP->isExactlyValue(Val);
398  return false;
399  }
400 };
401 
402 /// \brief Match a specific floating point value or vector with all elements
403 /// equal to the value.
404 inline specific_fpval m_SpecificFP(double V) { return specific_fpval(V); }
405 
406 /// \brief Match a float 1.0 or vector with all elements equal to 1.0.
407 inline specific_fpval m_FPOne() { return m_SpecificFP(1.0); }
408 
410  uint64_t &VR;
411 
412  bind_const_intval_ty(uint64_t &V) : VR(V) {}
413 
414  template <typename ITy> bool match(ITy *V) {
415  if (const auto *CV = dyn_cast<ConstantInt>(V))
416  if (CV->getValue().ule(UINT64_MAX)) {
417  VR = CV->getZExtValue();
418  return true;
419  }
420  return false;
421  }
422 };
423 
424 /// \brief Match a specified integer value or vector of all elements of that
425 // value.
427  uint64_t Val;
428 
429  specific_intval(uint64_t V) : Val(V) {}
430 
431  template <typename ITy> bool match(ITy *V) {
432  const auto *CI = dyn_cast<ConstantInt>(V);
433  if (!CI && V->getType()->isVectorTy())
434  if (const auto *C = dyn_cast<Constant>(V))
435  CI = dyn_cast_or_null<ConstantInt>(C->getSplatValue());
436 
437  return CI && CI->getValue() == Val;
438  }
439 };
440 
441 /// \brief Match a specific integer value or vector with all elements equal to
442 /// the value.
443 inline specific_intval m_SpecificInt(uint64_t V) { return specific_intval(V); }
444 
445 /// \brief Match a ConstantInt and bind to its value. This does not match
446 /// ConstantInts wider than 64-bits.
447 inline bind_const_intval_ty m_ConstantInt(uint64_t &V) { return V; }
448 
449 //===----------------------------------------------------------------------===//
450 // Matcher for any binary operator.
451 //
452 template <typename LHS_t, typename RHS_t, bool Commutable = false>
454  LHS_t L;
455  RHS_t R;
456 
457  AnyBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
458 
459  template <typename OpTy> bool match(OpTy *V) {
460  if (auto *I = dyn_cast<BinaryOperator>(V))
461  return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
462  (Commutable && R.match(I->getOperand(0)) &&
463  L.match(I->getOperand(1)));
464  return false;
465  }
466 };
467 
468 template <typename LHS, typename RHS>
469 inline AnyBinaryOp_match<LHS, RHS> m_BinOp(const LHS &L, const RHS &R) {
470  return AnyBinaryOp_match<LHS, RHS>(L, R);
471 }
472 
473 //===----------------------------------------------------------------------===//
474 // Matchers for specific binary operators.
475 //
476 
477 template <typename LHS_t, typename RHS_t, unsigned Opcode,
478  bool Commutable = false>
480  LHS_t L;
481  RHS_t R;
482 
483  BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
484 
485  template <typename OpTy> bool match(OpTy *V) {
486  if (V->getValueID() == Value::InstructionVal + Opcode) {
487  auto *I = cast<BinaryOperator>(V);
488  return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
489  (Commutable && R.match(I->getOperand(0)) &&
490  L.match(I->getOperand(1)));
491  }
492  if (auto *CE = dyn_cast<ConstantExpr>(V))
493  return CE->getOpcode() == Opcode &&
494  ((L.match(CE->getOperand(0)) && R.match(CE->getOperand(1))) ||
495  (Commutable && R.match(CE->getOperand(0)) &&
496  L.match(CE->getOperand(1))));
497  return false;
498  }
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, typename RHS>
587  const RHS &R) {
589 }
590 
591 template <typename LHS, typename RHS>
593  const RHS &R) {
595 }
596 
597 template <typename LHS, typename RHS>
599  const RHS &R) {
601 }
602 
603 template <typename LHS, typename RHS>
605  const RHS &R) {
607 }
608 
609 template <typename LHS_t, typename RHS_t, unsigned Opcode,
610  unsigned WrapFlags = 0>
612  LHS_t L;
613  RHS_t R;
614 
615  OverflowingBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS)
616  : L(LHS), R(RHS) {}
617 
618  template <typename OpTy> bool match(OpTy *V) {
619  if (auto *Op = dyn_cast<OverflowingBinaryOperator>(V)) {
620  if (Op->getOpcode() != Opcode)
621  return false;
623  !Op->hasNoUnsignedWrap())
624  return false;
625  if (WrapFlags & OverflowingBinaryOperator::NoSignedWrap &&
626  !Op->hasNoSignedWrap())
627  return false;
628  return L.match(Op->getOperand(0)) && R.match(Op->getOperand(1));
629  }
630  return false;
631  }
632 };
633 
634 template <typename LHS, typename RHS>
637 m_NSWAdd(const LHS &L, const RHS &R) {
640  L, R);
641 }
642 template <typename LHS, typename RHS>
643 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
645 m_NSWSub(const LHS &L, const RHS &R) {
646  return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
648  L, R);
649 }
650 template <typename LHS, typename RHS>
651 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
653 m_NSWMul(const LHS &L, const RHS &R) {
654  return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
656  L, R);
657 }
658 template <typename LHS, typename RHS>
659 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
661 m_NSWShl(const LHS &L, const RHS &R) {
662  return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
664  L, R);
665 }
666 
667 template <typename LHS, typename RHS>
670 m_NUWAdd(const LHS &L, const RHS &R) {
673  L, R);
674 }
675 template <typename LHS, typename RHS>
676 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
678 m_NUWSub(const LHS &L, const RHS &R) {
679  return OverflowingBinaryOp_match<LHS, RHS, Instruction::Sub,
681  L, R);
682 }
683 template <typename LHS, typename RHS>
684 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
686 m_NUWMul(const LHS &L, const RHS &R) {
687  return OverflowingBinaryOp_match<LHS, RHS, Instruction::Mul,
689  L, R);
690 }
691 template <typename LHS, typename RHS>
692 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
694 m_NUWShl(const LHS &L, const RHS &R) {
695  return OverflowingBinaryOp_match<LHS, RHS, Instruction::Shl,
697  L, R);
698 }
699 
700 //===----------------------------------------------------------------------===//
701 // Class that matches a group of binary opcodes.
702 //
703 template <typename LHS_t, typename RHS_t, typename Predicate>
705  LHS_t L;
706  RHS_t R;
707 
708  BinOpPred_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
709 
710  template <typename OpTy> bool match(OpTy *V) {
711  if (auto *I = dyn_cast<Instruction>(V))
712  return this->isOpType(I->getOpcode()) && L.match(I->getOperand(0)) &&
713  R.match(I->getOperand(1));
714  if (auto *CE = dyn_cast<ConstantExpr>(V))
715  return this->isOpType(CE->getOpcode()) && L.match(CE->getOperand(0)) &&
716  R.match(CE->getOperand(1));
717  return false;
718  }
719 };
720 
721 struct is_shift_op {
722  bool isOpType(unsigned Opcode) { return Instruction::isShift(Opcode); }
723 };
724 
726  bool isOpType(unsigned Opcode) {
727  return Opcode == Instruction::LShr || Opcode == Instruction::AShr;
728  }
729 };
730 
732  bool isOpType(unsigned Opcode) {
733  return Opcode == Instruction::LShr || Opcode == Instruction::Shl;
734  }
735 };
736 
738  bool isOpType(unsigned Opcode) {
739  return Instruction::isBitwiseLogicOp(Opcode);
740  }
741 };
742 
743 struct is_idiv_op {
744  bool isOpType(unsigned Opcode) {
745  return Opcode == Instruction::SDiv || Opcode == Instruction::UDiv;
746  }
747 };
748 
749 /// \brief Matches shift operations.
750 template <typename LHS, typename RHS>
752  const RHS &R) {
754 }
755 
756 /// \brief Matches logical shift operations.
757 template <typename LHS, typename RHS>
759  const RHS &R) {
761 }
762 
763 /// \brief Matches logical shift operations.
764 template <typename LHS, typename RHS>
766 m_LogicalShift(const LHS &L, const RHS &R) {
768 }
769 
770 /// \brief Matches bitwise logic operations.
771 template <typename LHS, typename RHS>
773 m_BitwiseLogic(const LHS &L, const RHS &R) {
775 }
776 
777 /// \brief Matches integer division operations.
778 template <typename LHS, typename RHS>
780  const RHS &R) {
782 }
783 
784 //===----------------------------------------------------------------------===//
785 // Class that matches exact binary ops.
786 //
787 template <typename SubPattern_t> struct Exact_match {
788  SubPattern_t SubPattern;
789 
790  Exact_match(const SubPattern_t &SP) : SubPattern(SP) {}
791 
792  template <typename OpTy> bool match(OpTy *V) {
793  if (auto *PEO = dyn_cast<PossiblyExactOperator>(V))
794  return PEO->isExact() && SubPattern.match(V);
795  return false;
796  }
797 };
798 
799 template <typename T> inline Exact_match<T> m_Exact(const T &SubPattern) {
800  return SubPattern;
801 }
802 
803 //===----------------------------------------------------------------------===//
804 // Matchers for CmpInst classes
805 //
806 
807 template <typename LHS_t, typename RHS_t, typename Class, typename PredicateTy,
808  bool Commutable = false>
810  PredicateTy &Predicate;
811  LHS_t L;
812  RHS_t R;
813 
814  CmpClass_match(PredicateTy &Pred, const LHS_t &LHS, const RHS_t &RHS)
815  : Predicate(Pred), L(LHS), R(RHS) {}
816 
817  template <typename OpTy> bool match(OpTy *V) {
818  if (auto *I = dyn_cast<Class>(V))
819  if ((L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
820  (Commutable && R.match(I->getOperand(0)) &&
821  L.match(I->getOperand(1)))) {
822  Predicate = I->getPredicate();
823  return true;
824  }
825  return false;
826  }
827 };
828 
829 template <typename LHS, typename RHS>
831 m_Cmp(CmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
833 }
834 
835 template <typename LHS, typename RHS>
837 m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
839 }
840 
841 template <typename LHS, typename RHS>
843 m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
845 }
846 
847 //===----------------------------------------------------------------------===//
848 // Matchers for SelectInst classes
849 //
850 
851 template <typename Cond_t, typename LHS_t, typename RHS_t>
853  Cond_t C;
854  LHS_t L;
855  RHS_t R;
856 
857  SelectClass_match(const Cond_t &Cond, const LHS_t &LHS, const RHS_t &RHS)
858  : C(Cond), L(LHS), R(RHS) {}
859 
860  template <typename OpTy> bool match(OpTy *V) {
861  if (auto *I = dyn_cast<SelectInst>(V))
862  return C.match(I->getOperand(0)) && L.match(I->getOperand(1)) &&
863  R.match(I->getOperand(2));
864  return false;
865  }
866 };
867 
868 template <typename Cond, typename LHS, typename RHS>
869 inline SelectClass_match<Cond, LHS, RHS> m_Select(const Cond &C, const LHS &L,
870  const RHS &R) {
871  return SelectClass_match<Cond, LHS, RHS>(C, L, R);
872 }
873 
874 /// \brief This matches a select of two constants, e.g.:
875 /// m_SelectCst<-1, 0>(m_Value(V))
876 template <int64_t L, int64_t R, typename Cond>
878 m_SelectCst(const Cond &C) {
879  return m_Select(C, m_ConstantInt<L>(), m_ConstantInt<R>());
880 }
881 
882 //===----------------------------------------------------------------------===//
883 // Matchers for CastInst classes
884 //
885 
886 template <typename Op_t, unsigned Opcode> struct CastClass_match {
887  Op_t Op;
888 
889  CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {}
890 
891  template <typename OpTy> bool match(OpTy *V) {
892  if (auto *O = dyn_cast<Operator>(V))
893  return O->getOpcode() == Opcode && Op.match(O->getOperand(0));
894  return false;
895  }
896 };
897 
898 /// \brief Matches BitCast.
899 template <typename OpTy>
902 }
903 
904 /// \brief Matches PtrToInt.
905 template <typename OpTy>
908 }
909 
910 /// \brief Matches Trunc.
911 template <typename OpTy>
914 }
915 
916 /// \brief Matches SExt.
917 template <typename OpTy>
920 }
921 
922 /// \brief Matches ZExt.
923 template <typename OpTy>
926 }
927 
928 template <typename OpTy>
931 m_ZExtOrSExt(const OpTy &Op) {
932  return m_CombineOr(m_ZExt(Op), m_SExt(Op));
933 }
934 
935 /// \brief Matches UIToFP.
936 template <typename OpTy>
939 }
940 
941 /// \brief Matches SIToFP.
942 template <typename OpTy>
945 }
946 
947 /// \brief Matches FPTrunc
948 template <typename OpTy>
951 }
952 
953 /// \brief Matches FPExt
954 template <typename OpTy>
957 }
958 
959 //===----------------------------------------------------------------------===//
960 // Matchers for unary operators
961 //
962 
963 template <typename LHS_t> struct not_match {
964  LHS_t L;
965 
966  not_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::Xor) {
971  if (isAllOnes(O->getOperand(1)))
972  return L.match(O->getOperand(0));
973  if (isAllOnes(O->getOperand(0)))
974  return L.match(O->getOperand(1));
975  }
976  return false;
977  }
978 
979 private:
980  bool isAllOnes(Value *V) {
981  return isa<Constant>(V) && cast<Constant>(V)->isAllOnesValue();
982  }
983 };
984 
985 template <typename LHS> inline not_match<LHS> m_Not(const LHS &L) { return L; }
986 
987 template <typename LHS_t> struct neg_match {
988  LHS_t L;
989 
990  neg_match(const LHS_t &LHS) : L(LHS) {}
991 
992  template <typename OpTy> bool match(OpTy *V) {
993  if (auto *O = dyn_cast<Operator>(V))
994  if (O->getOpcode() == Instruction::Sub)
995  return matchIfNeg(O->getOperand(0), O->getOperand(1));
996  return false;
997  }
998 
999 private:
1000  bool matchIfNeg(Value *LHS, Value *RHS) {
1001  return ((isa<ConstantInt>(LHS) && cast<ConstantInt>(LHS)->isZero()) ||
1002  isa<ConstantAggregateZero>(LHS)) &&
1003  L.match(RHS);
1004  }
1005 };
1006 
1007 /// \brief Match an integer negate.
1008 template <typename LHS> inline neg_match<LHS> m_Neg(const LHS &L) { return L; }
1009 
1010 template <typename LHS_t> struct fneg_match {
1011  LHS_t L;
1012 
1013  fneg_match(const LHS_t &LHS) : L(LHS) {}
1014 
1015  template <typename OpTy> bool match(OpTy *V) {
1016  if (auto *O = dyn_cast<Operator>(V))
1017  if (O->getOpcode() == Instruction::FSub)
1018  return matchIfFNeg(O->getOperand(0), O->getOperand(1));
1019  return false;
1020  }
1021 
1022 private:
1023  bool matchIfFNeg(Value *LHS, Value *RHS) {
1024  if (const auto *C = dyn_cast<ConstantFP>(LHS))
1025  return C->isNegativeZeroValue() && L.match(RHS);
1026  return false;
1027  }
1028 };
1029 
1030 /// \brief Match a floating point negate.
1031 template <typename LHS> inline fneg_match<LHS> m_FNeg(const LHS &L) {
1032  return L;
1033 }
1034 
1035 //===----------------------------------------------------------------------===//
1036 // Matchers for control flow.
1037 //
1038 
1039 struct br_match {
1041 
1042  br_match(BasicBlock *&Succ) : Succ(Succ) {}
1043 
1044  template <typename OpTy> bool match(OpTy *V) {
1045  if (auto *BI = dyn_cast<BranchInst>(V))
1046  if (BI->isUnconditional()) {
1047  Succ = BI->getSuccessor(0);
1048  return true;
1049  }
1050  return false;
1051  }
1052 };
1053 
1054 inline br_match m_UnconditionalBr(BasicBlock *&Succ) { return br_match(Succ); }
1055 
1056 template <typename Cond_t> struct brc_match {
1057  Cond_t Cond;
1059 
1060  brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f)
1061  : Cond(C), T(t), F(f) {}
1062 
1063  template <typename OpTy> bool match(OpTy *V) {
1064  if (auto *BI = dyn_cast<BranchInst>(V))
1065  if (BI->isConditional() && Cond.match(BI->getCondition())) {
1066  T = BI->getSuccessor(0);
1067  F = BI->getSuccessor(1);
1068  return true;
1069  }
1070  return false;
1071  }
1072 };
1073 
1074 template <typename Cond_t>
1075 inline brc_match<Cond_t> m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) {
1076  return brc_match<Cond_t>(C, T, F);
1077 }
1078 
1079 //===----------------------------------------------------------------------===//
1080 // Matchers for max/min idioms, eg: "select (sgt x, y), x, y" -> smax(x,y).
1081 //
1082 
1083 template <typename CmpInst_t, typename LHS_t, typename RHS_t, typename Pred_t,
1084  bool Commutable = false>
1086  LHS_t L;
1087  RHS_t R;
1088 
1089  MaxMin_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
1090 
1091  template <typename OpTy> bool match(OpTy *V) {
1092  // Look for "(x pred y) ? x : y" or "(x pred y) ? y : x".
1093  auto *SI = dyn_cast<SelectInst>(V);
1094  if (!SI)
1095  return false;
1096  auto *Cmp = dyn_cast<CmpInst_t>(SI->getCondition());
1097  if (!Cmp)
1098  return false;
1099  // At this point we have a select conditioned on a comparison. Check that
1100  // it is the values returned by the select that are being compared.
1101  Value *TrueVal = SI->getTrueValue();
1102  Value *FalseVal = SI->getFalseValue();
1103  Value *LHS = Cmp->getOperand(0);
1104  Value *RHS = Cmp->getOperand(1);
1105  if ((TrueVal != LHS || FalseVal != RHS) &&
1106  (TrueVal != RHS || FalseVal != LHS))
1107  return false;
1108  typename CmpInst_t::Predicate Pred =
1109  LHS == TrueVal ? Cmp->getPredicate() : Cmp->getInversePredicate();
1110  // Does "(x pred y) ? x : y" represent the desired max/min operation?
1111  if (!Pred_t::match(Pred))
1112  return false;
1113  // It does! Bind the operands.
1114  return (L.match(LHS) && R.match(RHS)) ||
1115  (Commutable && R.match(LHS) && L.match(RHS));
1116  }
1117 };
1118 
1119 /// \brief Helper class for identifying signed max predicates.
1121  static bool match(ICmpInst::Predicate Pred) {
1122  return Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE;
1123  }
1124 };
1125 
1126 /// \brief Helper class for identifying signed min predicates.
1128  static bool match(ICmpInst::Predicate Pred) {
1129  return Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_SLE;
1130  }
1131 };
1132 
1133 /// \brief Helper class for identifying unsigned max predicates.
1135  static bool match(ICmpInst::Predicate Pred) {
1136  return Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE;
1137  }
1138 };
1139 
1140 /// \brief Helper class for identifying unsigned min predicates.
1142  static bool match(ICmpInst::Predicate Pred) {
1143  return Pred == CmpInst::ICMP_ULT || Pred == CmpInst::ICMP_ULE;
1144  }
1145 };
1146 
1147 /// \brief Helper class for identifying ordered max predicates.
1149  static bool match(FCmpInst::Predicate Pred) {
1150  return Pred == CmpInst::FCMP_OGT || Pred == CmpInst::FCMP_OGE;
1151  }
1152 };
1153 
1154 /// \brief Helper class for identifying ordered min predicates.
1156  static bool match(FCmpInst::Predicate Pred) {
1157  return Pred == CmpInst::FCMP_OLT || Pred == CmpInst::FCMP_OLE;
1158  }
1159 };
1160 
1161 /// \brief Helper class for identifying unordered max predicates.
1163  static bool match(FCmpInst::Predicate Pred) {
1164  return Pred == CmpInst::FCMP_UGT || Pred == CmpInst::FCMP_UGE;
1165  }
1166 };
1167 
1168 /// \brief Helper class for identifying unordered min predicates.
1170  static bool match(FCmpInst::Predicate Pred) {
1171  return Pred == CmpInst::FCMP_ULT || Pred == CmpInst::FCMP_ULE;
1172  }
1173 };
1174 
1175 template <typename LHS, typename RHS>
1177  const RHS &R) {
1179 }
1180 
1181 template <typename LHS, typename RHS>
1183  const RHS &R) {
1185 }
1186 
1187 template <typename LHS, typename RHS>
1189  const RHS &R) {
1191 }
1192 
1193 template <typename LHS, typename RHS>
1195  const RHS &R) {
1197 }
1198 
1199 /// \brief Match an 'ordered' floating point maximum function.
1200 /// Floating point has one special value 'NaN'. Therefore, there is no total
1201 /// order. However, if we can ignore the 'NaN' value (for example, because of a
1202 /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum'
1203 /// semantics. In the presence of 'NaN' we have to preserve the original
1204 /// select(fcmp(ogt/ge, L, R), L, R) semantics matched by this predicate.
1205 ///
1206 /// max(L, R) iff L and R are not NaN
1207 /// m_OrdFMax(L, R) = R iff L or R are NaN
1208 template <typename LHS, typename RHS>
1210  const RHS &R) {
1212 }
1213 
1214 /// \brief Match an 'ordered' floating point minimum function.
1215 /// Floating point has one special value 'NaN'. Therefore, there is no total
1216 /// order. However, if we can ignore the 'NaN' value (for example, because of a
1217 /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum'
1218 /// semantics. In the presence of 'NaN' we have to preserve the original
1219 /// select(fcmp(olt/le, L, R), L, R) semantics matched by this predicate.
1220 ///
1221 /// min(L, R) iff L and R are not NaN
1222 /// m_OrdFMin(L, R) = R iff L or R are NaN
1223 template <typename LHS, typename RHS>
1225  const RHS &R) {
1227 }
1228 
1229 /// \brief Match an 'unordered' floating point maximum function.
1230 /// Floating point has one special value 'NaN'. Therefore, there is no total
1231 /// order. However, if we can ignore the 'NaN' value (for example, because of a
1232 /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'maximum'
1233 /// semantics. In the presence of 'NaN' we have to preserve the original
1234 /// select(fcmp(ugt/ge, L, R), L, R) semantics matched by this predicate.
1235 ///
1236 /// max(L, R) iff L and R are not NaN
1237 /// m_UnordFMax(L, R) = L iff L or R are NaN
1238 template <typename LHS, typename RHS>
1240 m_UnordFMax(const LHS &L, const RHS &R) {
1242 }
1243 
1244 /// \brief Match an 'unordered' floating point minimum function.
1245 /// Floating point has one special value 'NaN'. Therefore, there is no total
1246 /// order. However, if we can ignore the 'NaN' value (for example, because of a
1247 /// 'no-nans-float-math' flag) a combination of a fcmp and select has 'minimum'
1248 /// semantics. In the presence of 'NaN' we have to preserve the original
1249 /// select(fcmp(ult/le, L, R), L, R) semantics matched by this predicate.
1250 ///
1251 /// min(L, R) iff L and R are not NaN
1252 /// m_UnordFMin(L, R) = L iff L or R are NaN
1253 template <typename LHS, typename RHS>
1255 m_UnordFMin(const LHS &L, const RHS &R) {
1257 }
1258 
1259 //===----------------------------------------------------------------------===//
1260 // Matchers for overflow check patterns: e.g. (a + b) u< a
1261 //
1262 
1263 template <typename LHS_t, typename RHS_t, typename Sum_t>
1265  LHS_t L;
1266  RHS_t R;
1267  Sum_t S;
1268 
1269  UAddWithOverflow_match(const LHS_t &L, const RHS_t &R, const Sum_t &S)
1270  : L(L), R(R), S(S) {}
1271 
1272  template <typename OpTy> bool match(OpTy *V) {
1273  Value *ICmpLHS, *ICmpRHS;
1274  ICmpInst::Predicate Pred;
1275  if (!m_ICmp(Pred, m_Value(ICmpLHS), m_Value(ICmpRHS)).match(V))
1276  return false;
1277 
1278  Value *AddLHS, *AddRHS;
1279  auto AddExpr = m_Add(m_Value(AddLHS), m_Value(AddRHS));
1280 
1281  // (a + b) u< a, (a + b) u< b
1282  if (Pred == ICmpInst::ICMP_ULT)
1283  if (AddExpr.match(ICmpLHS) && (ICmpRHS == AddLHS || ICmpRHS == AddRHS))
1284  return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS);
1285 
1286  // a >u (a + b), b >u (a + b)
1287  if (Pred == ICmpInst::ICMP_UGT)
1288  if (AddExpr.match(ICmpRHS) && (ICmpLHS == AddLHS || ICmpLHS == AddRHS))
1289  return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS);
1290 
1291  return false;
1292  }
1293 };
1294 
1295 /// \brief Match an icmp instruction checking for unsigned overflow on addition.
1296 ///
1297 /// S is matched to the addition whose result is being checked for overflow, and
1298 /// L and R are matched to the LHS and RHS of S.
1299 template <typename LHS_t, typename RHS_t, typename Sum_t>
1301 m_UAddWithOverflow(const LHS_t &L, const RHS_t &R, const Sum_t &S) {
1303 }
1304 
1305 template <typename Opnd_t> struct Argument_match {
1306  unsigned OpI;
1307  Opnd_t Val;
1308 
1309  Argument_match(unsigned OpIdx, const Opnd_t &V) : OpI(OpIdx), Val(V) {}
1310 
1311  template <typename OpTy> bool match(OpTy *V) {
1312  CallSite CS(V);
1313  return CS.isCall() && Val.match(CS.getArgument(OpI));
1314  }
1315 };
1316 
1317 /// \brief Match an argument.
1318 template <unsigned OpI, typename Opnd_t>
1319 inline Argument_match<Opnd_t> m_Argument(const Opnd_t &Op) {
1320  return Argument_match<Opnd_t>(OpI, Op);
1321 }
1322 
1323 /// \brief Intrinsic matchers.
1325  unsigned ID;
1326 
1327  IntrinsicID_match(Intrinsic::ID IntrID) : ID(IntrID) {}
1328 
1329  template <typename OpTy> bool match(OpTy *V) {
1330  if (const auto *CI = dyn_cast<CallInst>(V))
1331  if (const auto *F = CI->getCalledFunction())
1332  return F->getIntrinsicID() == ID;
1333  return false;
1334  }
1335 };
1336 
1337 /// Intrinsic matches are combinations of ID matchers, and argument
1338 /// matchers. Higher arity matcher are defined recursively in terms of and-ing
1339 /// them with lower arity matchers. Here's some convenient typedefs for up to
1340 /// several arguments, and more can be added as needed
1341 template <typename T0 = void, typename T1 = void, typename T2 = void,
1342  typename T3 = void, typename T4 = void, typename T5 = void,
1343  typename T6 = void, typename T7 = void, typename T8 = void,
1344  typename T9 = void, typename T10 = void>
1346 template <typename T0> struct m_Intrinsic_Ty<T0> {
1348 };
1349 template <typename T0, typename T1> struct m_Intrinsic_Ty<T0, T1> {
1350  using Ty =
1352 };
1353 template <typename T0, typename T1, typename T2>
1354 struct m_Intrinsic_Ty<T0, T1, T2> {
1355  using Ty =
1358 };
1359 template <typename T0, typename T1, typename T2, typename T3>
1360 struct m_Intrinsic_Ty<T0, T1, T2, T3> {
1361  using Ty =
1364 };
1365 
1366 /// \brief Match intrinsic calls like this:
1367 /// m_Intrinsic<Intrinsic::fabs>(m_Value(X))
1368 template <Intrinsic::ID IntrID> inline IntrinsicID_match m_Intrinsic() {
1369  return IntrinsicID_match(IntrID);
1370 }
1371 
1372 template <Intrinsic::ID IntrID, typename T0>
1373 inline typename m_Intrinsic_Ty<T0>::Ty m_Intrinsic(const T0 &Op0) {
1374  return m_CombineAnd(m_Intrinsic<IntrID>(), m_Argument<0>(Op0));
1375 }
1376 
1377 template <Intrinsic::ID IntrID, typename T0, typename T1>
1378 inline typename m_Intrinsic_Ty<T0, T1>::Ty m_Intrinsic(const T0 &Op0,
1379  const T1 &Op1) {
1380  return m_CombineAnd(m_Intrinsic<IntrID>(Op0), m_Argument<1>(Op1));
1381 }
1382 
1383 template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2>
1384 inline typename m_Intrinsic_Ty<T0, T1, T2>::Ty
1385 m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2) {
1386  return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1), m_Argument<2>(Op2));
1387 }
1388 
1389 template <Intrinsic::ID IntrID, typename T0, typename T1, typename T2,
1390  typename T3>
1391 inline typename m_Intrinsic_Ty<T0, T1, T2, T3>::Ty
1392 m_Intrinsic(const T0 &Op0, const T1 &Op1, const T2 &Op2, const T3 &Op3) {
1393  return m_CombineAnd(m_Intrinsic<IntrID>(Op0, Op1, Op2), m_Argument<3>(Op3));
1394 }
1395 
1396 // Helper intrinsic matching specializations.
1397 template <typename Opnd0>
1398 inline typename m_Intrinsic_Ty<Opnd0>::Ty m_BitReverse(const Opnd0 &Op0) {
1399  return m_Intrinsic<Intrinsic::bitreverse>(Op0);
1400 }
1401 
1402 template <typename Opnd0>
1403 inline typename m_Intrinsic_Ty<Opnd0>::Ty m_BSwap(const Opnd0 &Op0) {
1404  return m_Intrinsic<Intrinsic::bswap>(Op0);
1405 }
1406 
1407 template <typename Opnd0, typename Opnd1>
1408 inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMin(const Opnd0 &Op0,
1409  const Opnd1 &Op1) {
1410  return m_Intrinsic<Intrinsic::minnum>(Op0, Op1);
1411 }
1412 
1413 template <typename Opnd0, typename Opnd1>
1414 inline typename m_Intrinsic_Ty<Opnd0, Opnd1>::Ty m_FMax(const Opnd0 &Op0,
1415  const Opnd1 &Op1) {
1416  return m_Intrinsic<Intrinsic::maxnum>(Op0, Op1);
1417 }
1418 
1419 template <typename Opnd_t> struct Signum_match {
1420  Opnd_t Val;
1421  Signum_match(const Opnd_t &V) : Val(V) {}
1422 
1423  template <typename OpTy> bool match(OpTy *V) {
1424  unsigned TypeSize = V->getType()->getScalarSizeInBits();
1425  if (TypeSize == 0)
1426  return false;
1427 
1428  unsigned ShiftWidth = TypeSize - 1;
1429  Value *OpL = nullptr, *OpR = nullptr;
1430 
1431  // This is the representation of signum we match:
1432  //
1433  // signum(x) == (x >> 63) | (-x >>u 63)
1434  //
1435  // An i1 value is its own signum, so it's correct to match
1436  //
1437  // signum(x) == (x >> 0) | (-x >>u 0)
1438  //
1439  // for i1 values.
1440 
1441  auto LHS = m_AShr(m_Value(OpL), m_SpecificInt(ShiftWidth));
1442  auto RHS = m_LShr(m_Neg(m_Value(OpR)), m_SpecificInt(ShiftWidth));
1443  auto Signum = m_Or(LHS, RHS);
1444 
1445  return Signum.match(V) && OpL == OpR && Val.match(OpL);
1446  }
1447 };
1448 
1449 /// \brief Matches a signum pattern.
1450 ///
1451 /// signum(x) =
1452 /// x > 0 -> 1
1453 /// x == 0 -> 0
1454 /// x < 0 -> -1
1455 template <typename Val_t> inline Signum_match<Val_t> m_Signum(const Val_t &V) {
1456  return Signum_match<Val_t>(V);
1457 }
1458 
1459 //===----------------------------------------------------------------------===//
1460 // Matchers for two-operands operators with the operators in either order
1461 //
1462 
1463 /// \brief Matches a BinaryOperator with LHS and RHS in either order.
1464 template <typename LHS, typename RHS>
1465 inline AnyBinaryOp_match<LHS, RHS, true> m_c_BinOp(const LHS &L, const RHS &R) {
1466  return AnyBinaryOp_match<LHS, RHS, true>(L, R);
1467 }
1468 
1469 /// \brief Matches an ICmp with a predicate over LHS and RHS in either order.
1470 /// Does not swap the predicate.
1471 template <typename LHS, typename RHS>
1473 m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
1475  R);
1476 }
1477 
1478 /// \brief Matches a Add with LHS and RHS in either order.
1479 template <typename LHS, typename RHS>
1481  const RHS &R) {
1483 }
1484 
1485 /// \brief Matches a Mul with LHS and RHS in either order.
1486 template <typename LHS, typename RHS>
1488  const RHS &R) {
1490 }
1491 
1492 /// \brief Matches an And with LHS and RHS in either order.
1493 template <typename LHS, typename RHS>
1495  const RHS &R) {
1497 }
1498 
1499 /// \brief Matches an Or with LHS and RHS in either order.
1500 template <typename LHS, typename RHS>
1502  const RHS &R) {
1504 }
1505 
1506 /// \brief Matches an Xor with LHS and RHS in either order.
1507 template <typename LHS, typename RHS>
1509  const RHS &R) {
1511 }
1512 
1513 /// Matches an SMin with LHS and RHS in either order.
1514 template <typename LHS, typename RHS>
1516 m_c_SMin(const LHS &L, const RHS &R) {
1518 }
1519 /// Matches an SMax with LHS and RHS in either order.
1520 template <typename LHS, typename RHS>
1522 m_c_SMax(const LHS &L, const RHS &R) {
1524 }
1525 /// Matches a UMin with LHS and RHS in either order.
1526 template <typename LHS, typename RHS>
1528 m_c_UMin(const LHS &L, const RHS &R) {
1530 }
1531 /// Matches a UMax with LHS and RHS in either order.
1532 template <typename LHS, typename RHS>
1534 m_c_UMax(const LHS &L, const RHS &R) {
1536 }
1537 
1538 } // end namespace PatternMatch
1539 } // end namespace llvm
1540 
1541 #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:574
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:758
OverflowingBinaryOp_match< LHS, RHS, Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap > m_NSWSub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:645
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:426
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:514
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:508
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:386
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:550
BinaryOp_match< LHS, RHS, Instruction::SRem > m_SRem(const LHS &L, const RHS &R)
Definition: PatternMatch.h:562
match_zero m_Zero()
Match an arbitrary zero/null constant.
Definition: PatternMatch.h:145
Exact_match(const SubPattern_t &SP)
Definition: PatternMatch.h:790
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:526
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:879
unsigned less than
Definition: InstrTypes.h:878
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
Definition: PatternMatch.h:604
static bool match(ICmpInst::Predicate Pred)
0 1 0 0 True if ordered and less than
Definition: InstrTypes.h:859
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
F(f)
BinaryOp_match< LHS, RHS, Instruction::FSub > m_FSub(const LHS &L, const RHS &R)
Definition: PatternMatch.h:520
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:766
specific_fpval m_SpecificFP(double V)
Match a specific floating point value or vector with all elements equal to the value.
Definition: PatternMatch.h:404
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:843
Helper class for identifying signed min predicates.
BinaryOp_match< LHS, RHS, Instruction::Xor > m_Xor(const LHS &L, const RHS &R)
Definition: PatternMatch.h:586
This class represents the LLVM &#39;select&#39; instruction.
Exact_match< T > m_Exact(const T &SubPattern)
Definition: PatternMatch.h:799
CastClass_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
Definition: PatternMatch.h:912
cst_pred_ty< is_maxsignedvalue > m_MaxSignedValue()
Definition: PatternMatch.h:337
0 1 0 1 True if ordered and less than or equal
Definition: InstrTypes.h:860
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:985
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:502
bind_ty< ConstantFP > m_ConstantFP(ConstantFP *&C)
Match a ConstantFP, capturing the value if we match.
Definition: PatternMatch.h:370
bool isBitwiseLogicOp() const
Return true if this is and/or/xor.
Definition: Instruction.h:165
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWAdd(const LHS &L, const RHS &R)
Definition: PatternMatch.h:670
apfloat_match m_APFloat(const APFloat *&Res)
Match a ConstantFP or splatted ConstantVector, binding the specified pointer to the contained APFloat...
Definition: PatternMatch.h:264
CastClass_match< OpTy, Instruction::FPExt > m_FPExt(const OpTy &Op)
Matches FPExt.
Definition: PatternMatch.h:955
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:889
CastClass_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
Definition: PatternMatch.h:924
#define T
CastClass_match< OpTy, Instruction::FPTrunc > m_FPTrunc(const OpTy &Op)
Matches FPTrunc.
Definition: PatternMatch.h:949
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:869
cst_pred_ty< is_power2 > m_Power2()
Match an integer or vector power of 2.
Definition: PatternMatch.h:330
OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWMul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:686
bool isCall() const
Return true if a CallInst is enclosed.
Definition: CallSite.h:87
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:598
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:260
BinaryOp_match< LHS, RHS, Instruction::SDiv > m_SDiv(const LHS &L, const RHS &R)
Definition: PatternMatch.h:544
This helper class is used to match scalar and vector constants that satisfy a specified predicate...
Definition: PatternMatch.h:288
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:694
BinaryOp_match< LHS, RHS, Instruction::FRem > m_FRem(const LHS &L, const RHS &R)
Definition: PatternMatch.h:568
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:580
CastClass_match< OpTy, Instruction::BitCast > m_BitCast(const OpTy &Op)
Matches BitCast.
Definition: PatternMatch.h:900
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:382
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:592
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:853
match_combine_or< CastClass_match< OpTy, Instruction::ZExt >, CastClass_match< OpTy, Instruction::SExt > > m_ZExtOrSExt(const OpTy &Op)
Definition: PatternMatch.h:931
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:773
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:457
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:779
Helper class for identifying unordered min predicates.
1 1 0 1 True if unordered, less than, or equal
Definition: InstrTypes.h:868
BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS)
Definition: PatternMatch.h:483
signed greater than
Definition: InstrTypes.h:880
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.
CastClass_match< OpTy, Instruction::SExt > m_SExt(const OpTy &Op)
Matches SExt.
Definition: PatternMatch.h:918
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:857
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:326
ValTy * getArgument(unsigned ArgNo) const
Definition: CallSite.h:186
Match a specified Value*.
Definition: PatternMatch.h:373
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:867
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:556
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:538
signed less than
Definition: InstrTypes.h:882
bool isOpType(unsigned Opcode)
Definition: PatternMatch.h:744
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:937
BinaryOp_match< LHS, RHS, Instruction::FMul > m_FMul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:532
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoSignedWrap > m_NSWAdd(const LHS &L, const RHS &R)
Definition: PatternMatch.h:637
signed less or equal
Definition: InstrTypes.h:883
Class for arbitrary precision integers.
Definition: APInt.h:69
not_match(const LHS_t &LHS)
Definition: PatternMatch.h:966
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:906
BinOpPred_match< LHS, RHS, is_shift_op > m_Shift(const LHS &L, const RHS &R)
Matches shift operations.
Definition: PatternMatch.h:751
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:678
specific_fpval m_FPOne()
Match a float 1.0 or vector with all elements equal to 1.0.
Definition: PatternMatch.h:407
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Definition: Lint.cpp:538
neg_match(const LHS_t &LHS)
Definition: PatternMatch.h:990
unsigned greater or equal
Definition: InstrTypes.h:877
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:814
#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:661
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:943
1 0 1 0 True if unordered or greater than
Definition: InstrTypes.h:865
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:878
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:615
bool isOpType(unsigned Opcode)
Definition: PatternMatch.h:722
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
apfloat_match(const APFloat *&R)
Definition: PatternMatch.h:242
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:866
OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoSignedWrap > m_NSWMul(const LHS &L, const RHS &R)
Definition: PatternMatch.h:653
static bool match(ICmpInst::Predicate Pred)
BinOpPred_match(const LHS_t &LHS, const RHS_t &RHS)
Definition: PatternMatch.h:708
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:876
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:443
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:857
0 0 1 1 True if ordered and greater than or equal
Definition: InstrTypes.h:858
This helper class is used to match scalar and vector constants that satisfy a specified predicate...
Definition: PatternMatch.h:302
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
Definition: PatternMatch.h:359
#define T1
signed greater or equal
Definition: InstrTypes.h:881
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:837