1 //===-- llvm/Support/PatternMatch.h - Match on the LLVM IR ------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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:
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 ...
24 // This is primarily useful to things like the instruction combiner, but can
25 // also be useful for static analysis tools or code generators.
27 //===----------------------------------------------------------------------===//
29 #ifndef LLVM_SUPPORT_PATTERNMATCH_H
30 #define LLVM_SUPPORT_PATTERNMATCH_H
32 #include "llvm/Constants.h"
33 #include "llvm/Instructions.h"
36 namespace PatternMatch {
38 template<typename Val, typename Pattern>
39 bool match(Val *V, const Pattern &P) {
40 return const_cast<Pattern&>(P).match(V);
44 template<typename SubPattern_t>
46 SubPattern_t SubPattern;
48 OneUse_match(const SubPattern_t &SP) : SubPattern(SP) {}
50 template<typename OpTy>
52 return V->hasOneUse() && SubPattern.match(V);
57 inline OneUse_match<T> m_OneUse(const T &SubPattern) { return SubPattern; }
60 template<typename Class>
62 template<typename ITy>
63 bool match(ITy *V) { return isa<Class>(V); }
66 /// m_Value() - Match an arbitrary value and ignore it.
67 inline class_match<Value> m_Value() { return class_match<Value>(); }
68 /// m_ConstantInt() - Match an arbitrary ConstantInt and ignore it.
69 inline class_match<ConstantInt> m_ConstantInt() {
70 return class_match<ConstantInt>();
72 /// m_Undef() - Match an arbitrary undef constant.
73 inline class_match<UndefValue> m_Undef() { return class_match<UndefValue>(); }
75 inline class_match<Constant> m_Constant() { return class_match<Constant>(); }
78 template<typename ITy>
80 if (const Constant *C = dyn_cast<Constant>(V))
81 return C->isNullValue();
86 /// m_Zero() - Match an arbitrary zero/null constant. This includes
87 /// zero_initializer for vectors and ConstantPointerNull for pointers.
88 inline match_zero m_Zero() { return match_zero(); }
93 apint_match(const APInt *&R) : Res(R) {}
94 template<typename ITy>
96 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
97 Res = &CI->getValue();
100 if (ConstantVector *CV = dyn_cast<ConstantVector>(V))
101 if (ConstantInt *CI =
102 dyn_cast_or_null<ConstantInt>(CV->getSplatValue())) {
103 Res = &CI->getValue();
110 /// m_APInt - Match a ConstantInt or splatted ConstantVector, binding the
111 /// specified pointer to the contained APInt.
112 inline apint_match m_APInt(const APInt *&Res) { return Res; }
115 template<int64_t Val>
116 struct constantint_match {
117 template<typename ITy>
119 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
120 const APInt &CIV = CI->getValue();
122 return CIV == static_cast<uint64_t>(Val);
123 // If Val is negative, and CI is shorter than it, truncate to the right
124 // number of bits. If it is larger, then we have to sign extend. Just
125 // compare their negated values.
132 /// m_ConstantInt<int64_t> - Match a ConstantInt with a specific value.
133 template<int64_t Val>
134 inline constantint_match<Val> m_ConstantInt() {
135 return constantint_match<Val>();
138 /// cst_pred_ty - This helper class is used to match scalar and vector constants
139 /// that satisfy a specified predicate.
140 template<typename Predicate>
141 struct cst_pred_ty : public Predicate {
142 template<typename ITy>
144 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V))
145 return this->isValue(CI->getValue());
146 if (const ConstantVector *CV = dyn_cast<ConstantVector>(V))
147 if (ConstantInt *CI = dyn_cast_or_null<ConstantInt>(CV->getSplatValue()))
148 return this->isValue(CI->getValue());
153 /// api_pred_ty - This helper class is used to match scalar and vector constants
154 /// that satisfy a specified predicate, and bind them to an APInt.
155 template<typename Predicate>
156 struct api_pred_ty : public Predicate {
158 api_pred_ty(const APInt *&R) : Res(R) {}
159 template<typename ITy>
161 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V))
162 if (this->isValue(CI->getValue())) {
163 Res = &CI->getValue();
166 if (const ConstantVector *CV = dyn_cast<ConstantVector>(V))
167 if (ConstantInt *CI = dyn_cast_or_null<ConstantInt>(CV->getSplatValue()))
168 if (this->isValue(CI->getValue())) {
169 Res = &CI->getValue();
178 bool isValue(const APInt &C) { return C == 1; }
181 /// m_One() - Match an integer 1 or a vector with all elements equal to 1.
182 inline cst_pred_ty<is_one> m_One() { return cst_pred_ty<is_one>(); }
183 inline api_pred_ty<is_one> m_One(const APInt *&V) { return V; }
186 bool isValue(const APInt &C) { return C.isAllOnesValue(); }
189 /// m_AllOnes() - Match an integer or vector with all bits set to true.
190 inline cst_pred_ty<is_all_ones> m_AllOnes() {return cst_pred_ty<is_all_ones>();}
191 inline api_pred_ty<is_all_ones> m_AllOnes(const APInt *&V) { return V; }
194 bool isValue(const APInt &C) { return C.isSignBit(); }
197 /// m_SignBit() - Match an integer or vector with only the sign bit(s) set.
198 inline cst_pred_ty<is_sign_bit> m_SignBit() {return cst_pred_ty<is_sign_bit>();}
199 inline api_pred_ty<is_sign_bit> m_SignBit(const APInt *&V) { return V; }
202 bool isValue(const APInt &C) { return C.isPowerOf2(); }
205 /// m_Power2() - Match an integer or vector power of 2.
206 inline cst_pred_ty<is_power2> m_Power2() { return cst_pred_ty<is_power2>(); }
207 inline api_pred_ty<is_power2> m_Power2(const APInt *&V) { return V; }
209 template<typename Class>
212 bind_ty(Class *&V) : VR(V) {}
214 template<typename ITy>
216 if (Class *CV = dyn_cast<Class>(V)) {
224 /// m_Value - Match a value, capturing it if we match.
225 inline bind_ty<Value> m_Value(Value *&V) { return V; }
227 /// m_ConstantInt - Match a ConstantInt, capturing the value if we match.
228 inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
230 /// m_Constant - Match a Constant, capturing the value if we match.
231 inline bind_ty<Constant> m_Constant(Constant *&C) { return C; }
233 /// specificval_ty - Match a specified Value*.
234 struct specificval_ty {
236 specificval_ty(const Value *V) : Val(V) {}
238 template<typename ITy>
244 /// m_Specific - Match if we have a specific specified value.
245 inline specificval_ty m_Specific(const Value *V) { return V; }
247 struct bind_const_intval_ty {
249 bind_const_intval_ty(uint64_t &V) : VR(V) {}
251 template<typename ITy>
253 if (ConstantInt *CV = dyn_cast<ConstantInt>(V))
254 if (CV->getBitWidth() <= 64) {
255 VR = CV->getZExtValue();
262 /// m_ConstantInt - Match a ConstantInt and bind to its value. This does not
263 /// match ConstantInts wider than 64-bits.
264 inline bind_const_intval_ty m_ConstantInt(uint64_t &V) { return V; }
266 //===----------------------------------------------------------------------===//
267 // Matchers for specific binary operators.
270 template<typename LHS_t, typename RHS_t, unsigned Opcode>
271 struct BinaryOp_match {
275 BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
277 template<typename OpTy>
278 bool match(OpTy *V) {
279 if (V->getValueID() == Value::InstructionVal + Opcode) {
280 BinaryOperator *I = cast<BinaryOperator>(V);
281 return L.match(I->getOperand(0)) && R.match(I->getOperand(1));
283 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
284 return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
285 R.match(CE->getOperand(1));
290 template<typename LHS, typename RHS>
291 inline BinaryOp_match<LHS, RHS, Instruction::Add>
292 m_Add(const LHS &L, const RHS &R) {
293 return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);
296 template<typename LHS, typename RHS>
297 inline BinaryOp_match<LHS, RHS, Instruction::FAdd>
298 m_FAdd(const LHS &L, const RHS &R) {
299 return BinaryOp_match<LHS, RHS, Instruction::FAdd>(L, R);
302 template<typename LHS, typename RHS>
303 inline BinaryOp_match<LHS, RHS, Instruction::Sub>
304 m_Sub(const LHS &L, const RHS &R) {
305 return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R);
308 template<typename LHS, typename RHS>
309 inline BinaryOp_match<LHS, RHS, Instruction::FSub>
310 m_FSub(const LHS &L, const RHS &R) {
311 return BinaryOp_match<LHS, RHS, Instruction::FSub>(L, R);
314 template<typename LHS, typename RHS>
315 inline BinaryOp_match<LHS, RHS, Instruction::Mul>
316 m_Mul(const LHS &L, const RHS &R) {
317 return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R);
320 template<typename LHS, typename RHS>
321 inline BinaryOp_match<LHS, RHS, Instruction::FMul>
322 m_FMul(const LHS &L, const RHS &R) {
323 return BinaryOp_match<LHS, RHS, Instruction::FMul>(L, R);
326 template<typename LHS, typename RHS>
327 inline BinaryOp_match<LHS, RHS, Instruction::UDiv>
328 m_UDiv(const LHS &L, const RHS &R) {
329 return BinaryOp_match<LHS, RHS, Instruction::UDiv>(L, R);
332 template<typename LHS, typename RHS>
333 inline BinaryOp_match<LHS, RHS, Instruction::SDiv>
334 m_SDiv(const LHS &L, const RHS &R) {
335 return BinaryOp_match<LHS, RHS, Instruction::SDiv>(L, R);
338 template<typename LHS, typename RHS>
339 inline BinaryOp_match<LHS, RHS, Instruction::FDiv>
340 m_FDiv(const LHS &L, const RHS &R) {
341 return BinaryOp_match<LHS, RHS, Instruction::FDiv>(L, R);
344 template<typename LHS, typename RHS>
345 inline BinaryOp_match<LHS, RHS, Instruction::URem>
346 m_URem(const LHS &L, const RHS &R) {
347 return BinaryOp_match<LHS, RHS, Instruction::URem>(L, R);
350 template<typename LHS, typename RHS>
351 inline BinaryOp_match<LHS, RHS, Instruction::SRem>
352 m_SRem(const LHS &L, const RHS &R) {
353 return BinaryOp_match<LHS, RHS, Instruction::SRem>(L, R);
356 template<typename LHS, typename RHS>
357 inline BinaryOp_match<LHS, RHS, Instruction::FRem>
358 m_FRem(const LHS &L, const RHS &R) {
359 return BinaryOp_match<LHS, RHS, Instruction::FRem>(L, R);
362 template<typename LHS, typename RHS>
363 inline BinaryOp_match<LHS, RHS, Instruction::And>
364 m_And(const LHS &L, const RHS &R) {
365 return BinaryOp_match<LHS, RHS, Instruction::And>(L, R);
368 template<typename LHS, typename RHS>
369 inline BinaryOp_match<LHS, RHS, Instruction::Or>
370 m_Or(const LHS &L, const RHS &R) {
371 return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R);
374 template<typename LHS, typename RHS>
375 inline BinaryOp_match<LHS, RHS, Instruction::Xor>
376 m_Xor(const LHS &L, const RHS &R) {
377 return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R);
380 template<typename LHS, typename RHS>
381 inline BinaryOp_match<LHS, RHS, Instruction::Shl>
382 m_Shl(const LHS &L, const RHS &R) {
383 return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R);
386 template<typename LHS, typename RHS>
387 inline BinaryOp_match<LHS, RHS, Instruction::LShr>
388 m_LShr(const LHS &L, const RHS &R) {
389 return BinaryOp_match<LHS, RHS, Instruction::LShr>(L, R);
392 template<typename LHS, typename RHS>
393 inline BinaryOp_match<LHS, RHS, Instruction::AShr>
394 m_AShr(const LHS &L, const RHS &R) {
395 return BinaryOp_match<LHS, RHS, Instruction::AShr>(L, R);
398 //===----------------------------------------------------------------------===//
399 // Class that matches two different binary ops.
401 template<typename LHS_t, typename RHS_t, unsigned Opc1, unsigned Opc2>
402 struct BinOp2_match {
406 BinOp2_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
408 template<typename OpTy>
409 bool match(OpTy *V) {
410 if (V->getValueID() == Value::InstructionVal + Opc1 ||
411 V->getValueID() == Value::InstructionVal + Opc2) {
412 BinaryOperator *I = cast<BinaryOperator>(V);
413 return L.match(I->getOperand(0)) && R.match(I->getOperand(1));
415 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
416 return (CE->getOpcode() == Opc1 || CE->getOpcode() == Opc2) &&
417 L.match(CE->getOperand(0)) && R.match(CE->getOperand(1));
422 /// m_Shr - Matches LShr or AShr.
423 template<typename LHS, typename RHS>
424 inline BinOp2_match<LHS, RHS, Instruction::LShr, Instruction::AShr>
425 m_Shr(const LHS &L, const RHS &R) {
426 return BinOp2_match<LHS, RHS, Instruction::LShr, Instruction::AShr>(L, R);
429 /// m_LogicalShift - Matches LShr or Shl.
430 template<typename LHS, typename RHS>
431 inline BinOp2_match<LHS, RHS, Instruction::LShr, Instruction::Shl>
432 m_LogicalShift(const LHS &L, const RHS &R) {
433 return BinOp2_match<LHS, RHS, Instruction::LShr, Instruction::Shl>(L, R);
436 /// m_IDiv - Matches UDiv and SDiv.
437 template<typename LHS, typename RHS>
438 inline BinOp2_match<LHS, RHS, Instruction::SDiv, Instruction::UDiv>
439 m_IDiv(const LHS &L, const RHS &R) {
440 return BinOp2_match<LHS, RHS, Instruction::SDiv, Instruction::UDiv>(L, R);
443 //===----------------------------------------------------------------------===//
444 // Matchers for CmpInst classes
447 template<typename LHS_t, typename RHS_t, typename Class, typename PredicateTy>
448 struct CmpClass_match {
449 PredicateTy &Predicate;
453 CmpClass_match(PredicateTy &Pred, const LHS_t &LHS, const RHS_t &RHS)
454 : Predicate(Pred), L(LHS), R(RHS) {}
456 template<typename OpTy>
457 bool match(OpTy *V) {
458 if (Class *I = dyn_cast<Class>(V))
459 if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) {
460 Predicate = I->getPredicate();
467 template<typename LHS, typename RHS>
468 inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>
469 m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
470 return CmpClass_match<LHS, RHS,
471 ICmpInst, ICmpInst::Predicate>(Pred, L, R);
474 template<typename LHS, typename RHS>
475 inline CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>
476 m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
477 return CmpClass_match<LHS, RHS,
478 FCmpInst, FCmpInst::Predicate>(Pred, L, R);
481 //===----------------------------------------------------------------------===//
482 // Matchers for SelectInst classes
485 template<typename Cond_t, typename LHS_t, typename RHS_t>
486 struct SelectClass_match {
491 SelectClass_match(const Cond_t &Cond, const LHS_t &LHS,
493 : C(Cond), L(LHS), R(RHS) {}
495 template<typename OpTy>
496 bool match(OpTy *V) {
497 if (SelectInst *I = dyn_cast<SelectInst>(V))
498 return C.match(I->getOperand(0)) &&
499 L.match(I->getOperand(1)) &&
500 R.match(I->getOperand(2));
505 template<typename Cond, typename LHS, typename RHS>
506 inline SelectClass_match<Cond, LHS, RHS>
507 m_Select(const Cond &C, const LHS &L, const RHS &R) {
508 return SelectClass_match<Cond, LHS, RHS>(C, L, R);
511 /// m_SelectCst - This matches a select of two constants, e.g.:
512 /// m_SelectCst<-1, 0>(m_Value(V))
513 template<int64_t L, int64_t R, typename Cond>
514 inline SelectClass_match<Cond, constantint_match<L>, constantint_match<R> >
515 m_SelectCst(const Cond &C) {
516 return m_Select(C, m_ConstantInt<L>(), m_ConstantInt<R>());
520 //===----------------------------------------------------------------------===//
521 // Matchers for CastInst classes
524 template<typename Op_t, unsigned Opcode>
525 struct CastClass_match {
528 CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {}
530 template<typename OpTy>
531 bool match(OpTy *V) {
532 if (CastInst *I = dyn_cast<CastInst>(V))
533 return I->getOpcode() == Opcode && Op.match(I->getOperand(0));
534 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
535 return CE->getOpcode() == Opcode && Op.match(CE->getOperand(0));
541 template<typename OpTy>
542 inline CastClass_match<OpTy, Instruction::BitCast>
543 m_BitCast(const OpTy &Op) {
544 return CastClass_match<OpTy, Instruction::BitCast>(Op);
548 template<typename OpTy>
549 inline CastClass_match<OpTy, Instruction::PtrToInt>
550 m_PtrToInt(const OpTy &Op) {
551 return CastClass_match<OpTy, Instruction::PtrToInt>(Op);
555 template<typename OpTy>
556 inline CastClass_match<OpTy, Instruction::Trunc>
557 m_Trunc(const OpTy &Op) {
558 return CastClass_match<OpTy, Instruction::Trunc>(Op);
562 template<typename OpTy>
563 inline CastClass_match<OpTy, Instruction::SExt>
564 m_SExt(const OpTy &Op) {
565 return CastClass_match<OpTy, Instruction::SExt>(Op);
569 template<typename OpTy>
570 inline CastClass_match<OpTy, Instruction::ZExt>
571 m_ZExt(const OpTy &Op) {
572 return CastClass_match<OpTy, Instruction::ZExt>(Op);
576 //===----------------------------------------------------------------------===//
577 // Matchers for unary operators
580 template<typename LHS_t>
584 not_match(const LHS_t &LHS) : L(LHS) {}
586 template<typename OpTy>
587 bool match(OpTy *V) {
588 if (Instruction *I = dyn_cast<Instruction>(V))
589 if (I->getOpcode() == Instruction::Xor)
590 return matchIfNot(I->getOperand(0), I->getOperand(1));
591 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
592 if (CE->getOpcode() == Instruction::Xor)
593 return matchIfNot(CE->getOperand(0), CE->getOperand(1));
597 bool matchIfNot(Value *LHS, Value *RHS) {
598 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
599 return CI->isAllOnesValue() && L.match(LHS);
600 if (ConstantVector *CV = dyn_cast<ConstantVector>(RHS))
601 return CV->isAllOnesValue() && L.match(LHS);
606 template<typename LHS>
607 inline not_match<LHS> m_Not(const LHS &L) { return L; }
610 template<typename LHS_t>
614 neg_match(const LHS_t &LHS) : L(LHS) {}
616 template<typename OpTy>
617 bool match(OpTy *V) {
618 if (Instruction *I = dyn_cast<Instruction>(V))
619 if (I->getOpcode() == Instruction::Sub)
620 return matchIfNeg(I->getOperand(0), I->getOperand(1));
621 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
622 if (CE->getOpcode() == Instruction::Sub)
623 return matchIfNeg(CE->getOperand(0), CE->getOperand(1));
627 bool matchIfNeg(Value *LHS, Value *RHS) {
628 if (ConstantInt *C = dyn_cast<ConstantInt>(LHS))
629 return C->isZero() && L.match(RHS);
634 /// m_Neg - Match an integer negate.
635 template<typename LHS>
636 inline neg_match<LHS> m_Neg(const LHS &L) { return L; }
639 template<typename LHS_t>
643 fneg_match(const LHS_t &LHS) : L(LHS) {}
645 template<typename OpTy>
646 bool match(OpTy *V) {
647 if (Instruction *I = dyn_cast<Instruction>(V))
648 if (I->getOpcode() == Instruction::FSub)
649 return matchIfFNeg(I->getOperand(0), I->getOperand(1));
650 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
651 if (CE->getOpcode() == Instruction::FSub)
652 return matchIfFNeg(CE->getOperand(0), CE->getOperand(1));
656 bool matchIfFNeg(Value *LHS, Value *RHS) {
657 if (ConstantFP *C = dyn_cast<ConstantFP>(LHS))
658 return C->isNegativeZeroValue() && L.match(RHS);
663 /// m_FNeg - Match a floating point negate.
664 template<typename LHS>
665 inline fneg_match<LHS> m_FNeg(const LHS &L) { return L; }
668 //===----------------------------------------------------------------------===//
669 // Matchers for control flow.
672 template<typename Cond_t>
676 brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f)
677 : Cond(C), T(t), F(f) {
680 template<typename OpTy>
681 bool match(OpTy *V) {
682 if (BranchInst *BI = dyn_cast<BranchInst>(V))
683 if (BI->isConditional() && Cond.match(BI->getCondition())) {
684 T = BI->getSuccessor(0);
685 F = BI->getSuccessor(1);
692 template<typename Cond_t>
693 inline brc_match<Cond_t> m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) {
694 return brc_match<Cond_t>(C, T, F);
697 } // end namespace PatternMatch
698 } // end namespace llvm