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);
43 template<typename Class>
45 template<typename ITy>
46 bool match(ITy *V) { return isa<Class>(V); }
49 /// m_Value() - Match an arbitrary value and ignore it.
50 inline leaf_ty<Value> m_Value() { return leaf_ty<Value>(); }
51 /// m_ConstantInt() - Match an arbitrary ConstantInt and ignore it.
52 inline leaf_ty<ConstantInt> m_ConstantInt() { return leaf_ty<ConstantInt>(); }
55 struct constantint_ty {
56 template<typename ITy>
58 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
59 const APInt &CIV = CI->getValue();
61 return CIV == static_cast<uint64_t>(Val);
62 // If Val is negative, and CI is shorter than it, truncate to the right
63 // number of bits. If it is larger, then we have to sign extend. Just
64 // compare their negated values.
71 /// m_ConstantInt(int64_t) - Match a ConstantInt with a specific value
74 inline constantint_ty<Val> m_ConstantInt() {
75 return constantint_ty<Val>();
79 template<typename ITy>
81 return isa<UndefValue>(V);
85 /// m_Undef() - Match an arbitrary undef constant.
86 inline undef_ty m_Undef() { return undef_ty(); }
89 template<typename ITy>
91 if (const Constant *C = dyn_cast<Constant>(V))
92 return C->isNullValue();
97 /// m_Zero() - Match an arbitrary zero/null constant.
98 inline zero_ty m_Zero() { return zero_ty(); }
101 template<typename ITy>
103 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V))
105 if (const ConstantVector *CV = dyn_cast<ConstantVector>(V))
106 if (ConstantInt *CI = cast_or_null<ConstantInt>(CV->getSplatValue()))
112 /// m_One() - Match an integer 1 or a vector with all elements equal to 1.
113 inline one_ty m_One() { return one_ty(); }
116 template<typename ITy>
118 if (const ConstantInt *C = dyn_cast<ConstantInt>(V))
119 return C->isAllOnesValue();
120 if (const ConstantVector *C = dyn_cast<ConstantVector>(V))
121 return C->isAllOnesValue();
126 /// m_AllOnes() - Match an integer or vector with all bits set to true.
127 inline all_ones_ty m_AllOnes() { return all_ones_ty(); }
130 template<typename ITy>
132 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V))
133 return CI->getValue().isSignBit();
134 if (const ConstantVector *CV = dyn_cast<ConstantVector>(V))
135 if (ConstantInt *CI = cast_or_null<ConstantInt>(CV->getSplatValue()))
136 return CI->getValue().isSignBit();
141 /// m_SignBit() - Match an integer or vector with only the sign bit(s) set.
142 inline signbit_ty m_SignBit() { return signbit_ty(); }
145 template<typename Class>
148 bind_ty(Class *&V) : VR(V) {}
150 template<typename ITy>
152 if (Class *CV = dyn_cast<Class>(V)) {
160 /// m_Value - Match a value, capturing it if we match.
161 inline bind_ty<Value> m_Value(Value *&V) { return V; }
163 /// m_ConstantInt - Match a ConstantInt, capturing the value if we match.
164 inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
166 /// specificval_ty - Match a specified Value*.
167 struct specificval_ty {
169 specificval_ty(const Value *V) : Val(V) {}
171 template<typename ITy>
177 /// m_Specific - Match if we have a specific specified value.
178 inline specificval_ty m_Specific(const Value *V) { return V; }
181 //===----------------------------------------------------------------------===//
182 // Matchers for specific binary operators.
185 template<typename LHS_t, typename RHS_t,
186 unsigned Opcode, typename ConcreteTy = BinaryOperator>
187 struct BinaryOp_match {
191 BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
193 template<typename OpTy>
194 bool match(OpTy *V) {
195 if (V->getValueID() == Value::InstructionVal + Opcode) {
196 ConcreteTy *I = cast<ConcreteTy>(V);
197 return I->getOpcode() == Opcode && L.match(I->getOperand(0)) &&
198 R.match(I->getOperand(1));
200 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
201 return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
202 R.match(CE->getOperand(1));
207 template<typename LHS, typename RHS>
208 inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L,
210 return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);
213 template<typename LHS, typename RHS>
214 inline BinaryOp_match<LHS, RHS, Instruction::FAdd> m_FAdd(const LHS &L,
216 return BinaryOp_match<LHS, RHS, Instruction::FAdd>(L, R);
219 template<typename LHS, typename RHS>
220 inline BinaryOp_match<LHS, RHS, Instruction::Sub> m_Sub(const LHS &L,
222 return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R);
225 template<typename LHS, typename RHS>
226 inline BinaryOp_match<LHS, RHS, Instruction::FSub> m_FSub(const LHS &L,
228 return BinaryOp_match<LHS, RHS, Instruction::FSub>(L, R);
231 template<typename LHS, typename RHS>
232 inline BinaryOp_match<LHS, RHS, Instruction::Mul> m_Mul(const LHS &L,
234 return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R);
237 template<typename LHS, typename RHS>
238 inline BinaryOp_match<LHS, RHS, Instruction::FMul> m_FMul(const LHS &L,
240 return BinaryOp_match<LHS, RHS, Instruction::FMul>(L, R);
243 template<typename LHS, typename RHS>
244 inline BinaryOp_match<LHS, RHS, Instruction::UDiv> m_UDiv(const LHS &L,
246 return BinaryOp_match<LHS, RHS, Instruction::UDiv>(L, R);
249 template<typename LHS, typename RHS>
250 inline BinaryOp_match<LHS, RHS, Instruction::SDiv> m_SDiv(const LHS &L,
252 return BinaryOp_match<LHS, RHS, Instruction::SDiv>(L, R);
255 template<typename LHS, typename RHS>
256 inline BinaryOp_match<LHS, RHS, Instruction::FDiv> m_FDiv(const LHS &L,
258 return BinaryOp_match<LHS, RHS, Instruction::FDiv>(L, R);
261 template<typename LHS, typename RHS>
262 inline BinaryOp_match<LHS, RHS, Instruction::URem> m_URem(const LHS &L,
264 return BinaryOp_match<LHS, RHS, Instruction::URem>(L, R);
267 template<typename LHS, typename RHS>
268 inline BinaryOp_match<LHS, RHS, Instruction::SRem> m_SRem(const LHS &L,
270 return BinaryOp_match<LHS, RHS, Instruction::SRem>(L, R);
273 template<typename LHS, typename RHS>
274 inline BinaryOp_match<LHS, RHS, Instruction::FRem> m_FRem(const LHS &L,
276 return BinaryOp_match<LHS, RHS, Instruction::FRem>(L, R);
279 template<typename LHS, typename RHS>
280 inline BinaryOp_match<LHS, RHS, Instruction::And> m_And(const LHS &L,
282 return BinaryOp_match<LHS, RHS, Instruction::And>(L, R);
285 template<typename LHS, typename RHS>
286 inline BinaryOp_match<LHS, RHS, Instruction::Or> m_Or(const LHS &L,
288 return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R);
291 template<typename LHS, typename RHS>
292 inline BinaryOp_match<LHS, RHS, Instruction::Xor> m_Xor(const LHS &L,
294 return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R);
297 template<typename LHS, typename RHS>
298 inline BinaryOp_match<LHS, RHS, Instruction::Shl> m_Shl(const LHS &L,
300 return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R);
303 template<typename LHS, typename RHS>
304 inline BinaryOp_match<LHS, RHS, Instruction::LShr> m_LShr(const LHS &L,
306 return BinaryOp_match<LHS, RHS, Instruction::LShr>(L, R);
309 template<typename LHS, typename RHS>
310 inline BinaryOp_match<LHS, RHS, Instruction::AShr> m_AShr(const LHS &L,
312 return BinaryOp_match<LHS, RHS, Instruction::AShr>(L, R);
315 //===----------------------------------------------------------------------===//
316 // Matchers for either AShr or LShr .. for convenience
318 template<typename LHS_t, typename RHS_t, typename ConcreteTy = BinaryOperator>
323 Shr_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
325 template<typename OpTy>
326 bool match(OpTy *V) {
327 if (V->getValueID() == Value::InstructionVal + Instruction::LShr ||
328 V->getValueID() == Value::InstructionVal + Instruction::AShr) {
329 ConcreteTy *I = cast<ConcreteTy>(V);
330 return (I->getOpcode() == Instruction::AShr ||
331 I->getOpcode() == Instruction::LShr) &&
332 L.match(I->getOperand(0)) &&
333 R.match(I->getOperand(1));
335 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
336 return (CE->getOpcode() == Instruction::LShr ||
337 CE->getOpcode() == Instruction::AShr) &&
338 L.match(CE->getOperand(0)) &&
339 R.match(CE->getOperand(1));
344 template<typename LHS, typename RHS>
345 inline Shr_match<LHS, RHS> m_Shr(const LHS &L, const RHS &R) {
346 return Shr_match<LHS, RHS>(L, R);
349 //===----------------------------------------------------------------------===//
350 // Matchers for binary classes
353 template<typename LHS_t, typename RHS_t, typename Class, typename OpcType>
354 struct BinaryOpClass_match {
359 BinaryOpClass_match(OpcType &Op, const LHS_t &LHS,
361 : Opcode(&Op), L(LHS), R(RHS) {}
362 BinaryOpClass_match(const LHS_t &LHS, const RHS_t &RHS)
363 : Opcode(0), L(LHS), R(RHS) {}
365 template<typename OpTy>
366 bool match(OpTy *V) {
367 if (Class *I = dyn_cast<Class>(V))
368 if (L.match(I->getOperand(0)) &&
369 R.match(I->getOperand(1))) {
371 *Opcode = I->getOpcode();
374 #if 0 // Doesn't handle constantexprs yet!
375 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
376 return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
377 R.match(CE->getOperand(1));
383 template<typename LHS, typename RHS>
384 inline BinaryOpClass_match<LHS, RHS, BinaryOperator, Instruction::BinaryOps>
385 m_Shift(Instruction::BinaryOps &Op, const LHS &L, const RHS &R) {
386 return BinaryOpClass_match<LHS, RHS,
387 BinaryOperator, Instruction::BinaryOps>(Op, L, R);
390 template<typename LHS, typename RHS>
391 inline BinaryOpClass_match<LHS, RHS, BinaryOperator, Instruction::BinaryOps>
392 m_Shift(const LHS &L, const RHS &R) {
393 return BinaryOpClass_match<LHS, RHS,
394 BinaryOperator, Instruction::BinaryOps>(L, R);
397 //===----------------------------------------------------------------------===//
398 // Matchers for CmpInst classes
401 template<typename LHS_t, typename RHS_t, typename Class, typename PredicateTy>
402 struct CmpClass_match {
403 PredicateTy &Predicate;
407 CmpClass_match(PredicateTy &Pred, const LHS_t &LHS,
409 : Predicate(Pred), L(LHS), R(RHS) {}
411 template<typename OpTy>
412 bool match(OpTy *V) {
413 if (Class *I = dyn_cast<Class>(V))
414 if (L.match(I->getOperand(0)) &&
415 R.match(I->getOperand(1))) {
416 Predicate = I->getPredicate();
423 template<typename LHS, typename RHS>
424 inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>
425 m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
426 return CmpClass_match<LHS, RHS,
427 ICmpInst, ICmpInst::Predicate>(Pred, L, R);
430 template<typename LHS, typename RHS>
431 inline CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>
432 m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
433 return CmpClass_match<LHS, RHS,
434 FCmpInst, FCmpInst::Predicate>(Pred, L, R);
437 //===----------------------------------------------------------------------===//
438 // Matchers for SelectInst classes
441 template<typename Cond_t, typename LHS_t, typename RHS_t>
442 struct SelectClass_match {
447 SelectClass_match(const Cond_t &Cond, const LHS_t &LHS,
449 : C(Cond), L(LHS), R(RHS) {}
451 template<typename OpTy>
452 bool match(OpTy *V) {
453 if (SelectInst *I = dyn_cast<SelectInst>(V))
454 return C.match(I->getOperand(0)) &&
455 L.match(I->getOperand(1)) &&
456 R.match(I->getOperand(2));
461 template<typename Cond, typename LHS, typename RHS>
462 inline SelectClass_match<Cond, LHS, RHS>
463 m_Select(const Cond &C, const LHS &L, const RHS &R) {
464 return SelectClass_match<Cond, LHS, RHS>(C, L, R);
467 /// m_SelectCst - This matches a select of two constants, e.g.:
468 /// m_SelectCst<-1, 0>(m_Value(V))
469 template<int64_t L, int64_t R, typename Cond>
470 inline SelectClass_match<Cond, constantint_ty<L>, constantint_ty<R> >
471 m_SelectCst(const Cond &C) {
472 return SelectClass_match<Cond, constantint_ty<L>,
473 constantint_ty<R> >(C, m_ConstantInt<L>(),
478 //===----------------------------------------------------------------------===//
479 // Matchers for CastInst classes
482 template<typename Op_t, unsigned Opcode>
483 struct CastClass_match {
486 CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {}
488 template<typename OpTy>
489 bool match(OpTy *V) {
490 if (CastInst *I = dyn_cast<CastInst>(V))
491 return I->getOpcode() == Opcode && Op.match(I->getOperand(0));
492 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
493 return CE->getOpcode() == Opcode && Op.match(CE->getOperand(0));
499 template<typename OpTy>
500 inline CastClass_match<OpTy, Instruction::BitCast>
501 m_BitCast(const OpTy &Op) {
502 return CastClass_match<OpTy, Instruction::BitCast>(Op);
506 template<typename OpTy>
507 inline CastClass_match<OpTy, Instruction::PtrToInt>
508 m_PtrToInt(const OpTy &Op) {
509 return CastClass_match<OpTy, Instruction::PtrToInt>(Op);
513 template<typename OpTy>
514 inline CastClass_match<OpTy, Instruction::Trunc>
515 m_Trunc(const OpTy &Op) {
516 return CastClass_match<OpTy, Instruction::Trunc>(Op);
520 template<typename OpTy>
521 inline CastClass_match<OpTy, Instruction::SExt>
522 m_SExt(const OpTy &Op) {
523 return CastClass_match<OpTy, Instruction::SExt>(Op);
527 template<typename OpTy>
528 inline CastClass_match<OpTy, Instruction::ZExt>
529 m_ZExt(const OpTy &Op) {
530 return CastClass_match<OpTy, Instruction::ZExt>(Op);
534 //===----------------------------------------------------------------------===//
535 // Matchers for unary operators
538 template<typename LHS_t>
542 not_match(const LHS_t &LHS) : L(LHS) {}
544 template<typename OpTy>
545 bool match(OpTy *V) {
546 if (Instruction *I = dyn_cast<Instruction>(V))
547 if (I->getOpcode() == Instruction::Xor)
548 return matchIfNot(I->getOperand(0), I->getOperand(1));
549 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
550 if (CE->getOpcode() == Instruction::Xor)
551 return matchIfNot(CE->getOperand(0), CE->getOperand(1));
555 bool matchIfNot(Value *LHS, Value *RHS) {
556 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
557 return CI->isAllOnesValue() && L.match(LHS);
558 if (ConstantInt *CI = dyn_cast<ConstantInt>(LHS))
559 return CI->isAllOnesValue() && L.match(RHS);
560 if (ConstantVector *CV = dyn_cast<ConstantVector>(RHS))
561 return CV->isAllOnesValue() && L.match(LHS);
562 if (ConstantVector *CV = dyn_cast<ConstantVector>(LHS))
563 return CV->isAllOnesValue() && L.match(RHS);
568 template<typename LHS>
569 inline not_match<LHS> m_Not(const LHS &L) { return L; }
572 template<typename LHS_t>
576 neg_match(const LHS_t &LHS) : L(LHS) {}
578 template<typename OpTy>
579 bool match(OpTy *V) {
580 if (Instruction *I = dyn_cast<Instruction>(V))
581 if (I->getOpcode() == Instruction::Sub)
582 return matchIfNeg(I->getOperand(0), I->getOperand(1));
583 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
584 if (CE->getOpcode() == Instruction::Sub)
585 return matchIfNeg(CE->getOperand(0), CE->getOperand(1));
589 bool matchIfNeg(Value *LHS, Value *RHS) {
590 return LHS == ConstantFP::getZeroValueForNegation(LHS->getType()) &&
595 template<typename LHS>
596 inline neg_match<LHS> m_Neg(const LHS &L) { return L; }
599 template<typename LHS_t>
603 fneg_match(const LHS_t &LHS) : L(LHS) {}
605 template<typename OpTy>
606 bool match(OpTy *V) {
607 if (Instruction *I = dyn_cast<Instruction>(V))
608 if (I->getOpcode() == Instruction::FSub)
609 return matchIfFNeg(I->getOperand(0), I->getOperand(1));
610 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
611 if (CE->getOpcode() == Instruction::FSub)
612 return matchIfFNeg(CE->getOperand(0), CE->getOperand(1));
613 if (ConstantFP *CF = dyn_cast<ConstantFP>(V))
614 return L.match(ConstantExpr::getFNeg(CF));
618 bool matchIfFNeg(Value *LHS, Value *RHS) {
619 return LHS == ConstantFP::getZeroValueForNegation(LHS->getType()) &&
624 template<typename LHS>
625 inline fneg_match<LHS> m_FNeg(const LHS &L) { return L; }
628 //===----------------------------------------------------------------------===//
629 // Matchers for control flow
632 template<typename Cond_t>
636 brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f)
637 : Cond(C), T(t), F(f) {
640 template<typename OpTy>
641 bool match(OpTy *V) {
642 if (BranchInst *BI = dyn_cast<BranchInst>(V))
643 if (BI->isConditional()) {
644 if (Cond.match(BI->getCondition())) {
645 T = BI->getSuccessor(0);
646 F = BI->getSuccessor(1);
654 template<typename Cond_t>
655 inline brc_match<Cond_t> m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) {
656 return brc_match<Cond_t>(C, T, F);
659 } // end namespace PatternMatch
660 } // end namespace llvm