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 class_match<Value> m_Value() { return class_match<Value>(); }
51 /// m_ConstantInt() - Match an arbitrary ConstantInt and ignore it.
52 inline class_match<ConstantInt> m_ConstantInt() {
53 return class_match<ConstantInt>();
55 /// m_Undef() - Match an arbitrary undef constant.
56 inline class_match<UndefValue> m_Undef() { return class_match<UndefValue>(); }
58 inline class_match<Constant> m_Constant() { return class_match<Constant>(); }
61 template<typename ITy>
63 if (const Constant *C = dyn_cast<Constant>(V))
64 return C->isNullValue();
69 /// m_Zero() - Match an arbitrary zero/null constant. This includes
70 /// zero_initializer for vectors and ConstantPointerNull for pointers.
71 inline match_zero m_Zero() { return match_zero(); }
76 apint_match(const APInt *&R) : Res(R) {}
77 template<typename ITy>
79 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
80 Res = &CI->getValue();
83 if (ConstantVector *CV = dyn_cast<ConstantVector>(V))
85 dyn_cast_or_null<ConstantInt>(CV->getSplatValue())) {
86 Res = &CI->getValue();
93 /// m_APInt - Match a ConstantInt or splatted ConstantVector, binding the
94 /// specified pointer to the contained APInt.
95 inline apint_match m_APInt(const APInt *&Res) { return Res; }
99 struct constantint_match {
100 template<typename ITy>
102 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
103 const APInt &CIV = CI->getValue();
105 return CIV == static_cast<uint64_t>(Val);
106 // If Val is negative, and CI is shorter than it, truncate to the right
107 // number of bits. If it is larger, then we have to sign extend. Just
108 // compare their negated values.
115 /// m_ConstantInt<int64_t> - Match a ConstantInt with a specific value.
116 template<int64_t Val>
117 inline constantint_match<Val> m_ConstantInt() {
118 return constantint_match<Val>();
121 /// cst_pred_ty - This helper class is used to match scalar and vector constants
122 /// that satisfy a specified predicate.
123 template<typename Predicate>
124 struct cst_pred_ty : public Predicate {
125 template<typename ITy>
127 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V))
128 return this->isValue(CI->getValue());
129 if (const ConstantVector *CV = dyn_cast<ConstantVector>(V))
130 if (ConstantInt *CI = dyn_cast_or_null<ConstantInt>(CV->getSplatValue()))
131 return this->isValue(CI->getValue());
136 /// api_pred_ty - This helper class is used to match scalar and vector constants
137 /// that satisfy a specified predicate, and bind them to an APInt.
138 template<typename Predicate>
139 struct api_pred_ty : public Predicate {
141 api_pred_ty(const APInt *&R) : Res(R) {}
142 template<typename ITy>
144 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V))
145 if (this->isValue(CI->getValue())) {
146 Res = &CI->getValue();
149 if (const ConstantVector *CV = dyn_cast<ConstantVector>(V))
150 if (ConstantInt *CI = dyn_cast_or_null<ConstantInt>(CV->getSplatValue()))
151 if (this->isValue(CI->getValue())) {
152 Res = &CI->getValue();
161 bool isValue(const APInt &C) { return C == 1; }
164 /// m_One() - Match an integer 1 or a vector with all elements equal to 1.
165 inline cst_pred_ty<is_one> m_One() { return cst_pred_ty<is_one>(); }
166 inline api_pred_ty<is_one> m_One(const APInt *&V) { return V; }
169 bool isValue(const APInt &C) { return C.isAllOnesValue(); }
172 /// m_AllOnes() - Match an integer or vector with all bits set to true.
173 inline cst_pred_ty<is_all_ones> m_AllOnes() {return cst_pred_ty<is_all_ones>();}
174 inline api_pred_ty<is_all_ones> m_AllOnes(const APInt *&V) { return V; }
177 bool isValue(const APInt &C) { return C.isSignBit(); }
180 /// m_SignBit() - Match an integer or vector with only the sign bit(s) set.
181 inline cst_pred_ty<is_sign_bit> m_SignBit() {return cst_pred_ty<is_sign_bit>();}
182 inline api_pred_ty<is_sign_bit> m_SignBit(const APInt *&V) { return V; }
185 bool isValue(const APInt &C) { return C.isPowerOf2(); }
188 /// m_Power2() - Match an integer or vector power of 2.
189 inline cst_pred_ty<is_power2> m_Power2() { return cst_pred_ty<is_power2>(); }
190 inline api_pred_ty<is_power2> m_Power2(const APInt *&V) { return V; }
192 template<typename Class>
195 bind_ty(Class *&V) : VR(V) {}
197 template<typename ITy>
199 if (Class *CV = dyn_cast<Class>(V)) {
207 /// m_Value - Match a value, capturing it if we match.
208 inline bind_ty<Value> m_Value(Value *&V) { return V; }
210 /// m_ConstantInt - Match a ConstantInt, capturing the value if we match.
211 inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
213 /// m_Constant - Match a Constant, capturing the value if we match.
214 inline bind_ty<Constant> m_Constant(Constant *&C) { return C; }
216 /// specificval_ty - Match a specified Value*.
217 struct specificval_ty {
219 specificval_ty(const Value *V) : Val(V) {}
221 template<typename ITy>
227 /// m_Specific - Match if we have a specific specified value.
228 inline specificval_ty m_Specific(const Value *V) { return V; }
231 //===----------------------------------------------------------------------===//
232 // Matchers for specific binary operators.
235 template<typename LHS_t, typename RHS_t, unsigned Opcode>
236 struct BinaryOp_match {
240 BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
242 template<typename OpTy>
243 bool match(OpTy *V) {
244 if (V->getValueID() == Value::InstructionVal + Opcode) {
245 BinaryOperator *I = cast<BinaryOperator>(V);
246 return L.match(I->getOperand(0)) && R.match(I->getOperand(1));
248 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
249 return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
250 R.match(CE->getOperand(1));
255 template<typename LHS, typename RHS>
256 inline BinaryOp_match<LHS, RHS, Instruction::Add>
257 m_Add(const LHS &L, const RHS &R) {
258 return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);
261 template<typename LHS, typename RHS>
262 inline BinaryOp_match<LHS, RHS, Instruction::FAdd>
263 m_FAdd(const LHS &L, const RHS &R) {
264 return BinaryOp_match<LHS, RHS, Instruction::FAdd>(L, R);
267 template<typename LHS, typename RHS>
268 inline BinaryOp_match<LHS, RHS, Instruction::Sub>
269 m_Sub(const LHS &L, const RHS &R) {
270 return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R);
273 template<typename LHS, typename RHS>
274 inline BinaryOp_match<LHS, RHS, Instruction::FSub>
275 m_FSub(const LHS &L, const RHS &R) {
276 return BinaryOp_match<LHS, RHS, Instruction::FSub>(L, R);
279 template<typename LHS, typename RHS>
280 inline BinaryOp_match<LHS, RHS, Instruction::Mul>
281 m_Mul(const LHS &L, const RHS &R) {
282 return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R);
285 template<typename LHS, typename RHS>
286 inline BinaryOp_match<LHS, RHS, Instruction::FMul>
287 m_FMul(const LHS &L, const RHS &R) {
288 return BinaryOp_match<LHS, RHS, Instruction::FMul>(L, R);
291 template<typename LHS, typename RHS>
292 inline BinaryOp_match<LHS, RHS, Instruction::UDiv>
293 m_UDiv(const LHS &L, const RHS &R) {
294 return BinaryOp_match<LHS, RHS, Instruction::UDiv>(L, R);
297 template<typename LHS, typename RHS>
298 inline BinaryOp_match<LHS, RHS, Instruction::SDiv>
299 m_SDiv(const LHS &L, const RHS &R) {
300 return BinaryOp_match<LHS, RHS, Instruction::SDiv>(L, R);
303 template<typename LHS, typename RHS>
304 inline BinaryOp_match<LHS, RHS, Instruction::FDiv>
305 m_FDiv(const LHS &L, const RHS &R) {
306 return BinaryOp_match<LHS, RHS, Instruction::FDiv>(L, R);
309 template<typename LHS, typename RHS>
310 inline BinaryOp_match<LHS, RHS, Instruction::URem>
311 m_URem(const LHS &L, const RHS &R) {
312 return BinaryOp_match<LHS, RHS, Instruction::URem>(L, R);
315 template<typename LHS, typename RHS>
316 inline BinaryOp_match<LHS, RHS, Instruction::SRem>
317 m_SRem(const LHS &L, const RHS &R) {
318 return BinaryOp_match<LHS, RHS, Instruction::SRem>(L, R);
321 template<typename LHS, typename RHS>
322 inline BinaryOp_match<LHS, RHS, Instruction::FRem>
323 m_FRem(const LHS &L, const RHS &R) {
324 return BinaryOp_match<LHS, RHS, Instruction::FRem>(L, R);
327 template<typename LHS, typename RHS>
328 inline BinaryOp_match<LHS, RHS, Instruction::And>
329 m_And(const LHS &L, const RHS &R) {
330 return BinaryOp_match<LHS, RHS, Instruction::And>(L, R);
333 template<typename LHS, typename RHS>
334 inline BinaryOp_match<LHS, RHS, Instruction::Or>
335 m_Or(const LHS &L, const RHS &R) {
336 return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R);
339 template<typename LHS, typename RHS>
340 inline BinaryOp_match<LHS, RHS, Instruction::Xor>
341 m_Xor(const LHS &L, const RHS &R) {
342 return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R);
345 template<typename LHS, typename RHS>
346 inline BinaryOp_match<LHS, RHS, Instruction::Shl>
347 m_Shl(const LHS &L, const RHS &R) {
348 return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R);
351 template<typename LHS, typename RHS>
352 inline BinaryOp_match<LHS, RHS, Instruction::LShr>
353 m_LShr(const LHS &L, const RHS &R) {
354 return BinaryOp_match<LHS, RHS, Instruction::LShr>(L, R);
357 template<typename LHS, typename RHS>
358 inline BinaryOp_match<LHS, RHS, Instruction::AShr>
359 m_AShr(const LHS &L, const RHS &R) {
360 return BinaryOp_match<LHS, RHS, Instruction::AShr>(L, R);
363 //===----------------------------------------------------------------------===//
364 // Class that matches two different binary ops.
366 template<typename LHS_t, typename RHS_t, unsigned Opc1, unsigned Opc2>
367 struct BinOp2_match {
371 BinOp2_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
373 template<typename OpTy>
374 bool match(OpTy *V) {
375 if (V->getValueID() == Value::InstructionVal + Opc1 ||
376 V->getValueID() == Value::InstructionVal + Opc2) {
377 BinaryOperator *I = cast<BinaryOperator>(V);
378 return L.match(I->getOperand(0)) && R.match(I->getOperand(1));
380 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
381 return (CE->getOpcode() == Opc1 || CE->getOpcode() == Opc2) &&
382 L.match(CE->getOperand(0)) && R.match(CE->getOperand(1));
387 /// m_Shr - Matches LShr or AShr.
388 template<typename LHS, typename RHS>
389 inline BinOp2_match<LHS, RHS, Instruction::LShr, Instruction::AShr>
390 m_Shr(const LHS &L, const RHS &R) {
391 return BinOp2_match<LHS, RHS, Instruction::LShr, Instruction::AShr>(L, R);
394 /// m_LogicalShift - Matches LShr or Shl.
395 template<typename LHS, typename RHS>
396 inline BinOp2_match<LHS, RHS, Instruction::LShr, Instruction::Shl>
397 m_LogicalShift(const LHS &L, const RHS &R) {
398 return BinOp2_match<LHS, RHS, Instruction::LShr, Instruction::Shl>(L, R);
401 /// m_IDiv - Matches UDiv and SDiv.
402 template<typename LHS, typename RHS>
403 inline BinOp2_match<LHS, RHS, Instruction::SDiv, Instruction::UDiv>
404 m_IDiv(const LHS &L, const RHS &R) {
405 return BinOp2_match<LHS, RHS, Instruction::SDiv, Instruction::UDiv>(L, R);
408 //===----------------------------------------------------------------------===//
409 // Matchers for CmpInst classes
412 template<typename LHS_t, typename RHS_t, typename Class, typename PredicateTy>
413 struct CmpClass_match {
414 PredicateTy &Predicate;
418 CmpClass_match(PredicateTy &Pred, const LHS_t &LHS, const RHS_t &RHS)
419 : Predicate(Pred), L(LHS), R(RHS) {}
421 template<typename OpTy>
422 bool match(OpTy *V) {
423 if (Class *I = dyn_cast<Class>(V))
424 if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) {
425 Predicate = I->getPredicate();
432 template<typename LHS, typename RHS>
433 inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>
434 m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
435 return CmpClass_match<LHS, RHS,
436 ICmpInst, ICmpInst::Predicate>(Pred, L, R);
439 template<typename LHS, typename RHS>
440 inline CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>
441 m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
442 return CmpClass_match<LHS, RHS,
443 FCmpInst, FCmpInst::Predicate>(Pred, L, R);
446 //===----------------------------------------------------------------------===//
447 // Matchers for SelectInst classes
450 template<typename Cond_t, typename LHS_t, typename RHS_t>
451 struct SelectClass_match {
456 SelectClass_match(const Cond_t &Cond, const LHS_t &LHS,
458 : C(Cond), L(LHS), R(RHS) {}
460 template<typename OpTy>
461 bool match(OpTy *V) {
462 if (SelectInst *I = dyn_cast<SelectInst>(V))
463 return C.match(I->getOperand(0)) &&
464 L.match(I->getOperand(1)) &&
465 R.match(I->getOperand(2));
470 template<typename Cond, typename LHS, typename RHS>
471 inline SelectClass_match<Cond, LHS, RHS>
472 m_Select(const Cond &C, const LHS &L, const RHS &R) {
473 return SelectClass_match<Cond, LHS, RHS>(C, L, R);
476 /// m_SelectCst - This matches a select of two constants, e.g.:
477 /// m_SelectCst<-1, 0>(m_Value(V))
478 template<int64_t L, int64_t R, typename Cond>
479 inline SelectClass_match<Cond, constantint_match<L>, constantint_match<R> >
480 m_SelectCst(const Cond &C) {
481 return m_Select(C, m_ConstantInt<L>(), m_ConstantInt<R>());
485 //===----------------------------------------------------------------------===//
486 // Matchers for CastInst classes
489 template<typename Op_t, unsigned Opcode>
490 struct CastClass_match {
493 CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {}
495 template<typename OpTy>
496 bool match(OpTy *V) {
497 if (CastInst *I = dyn_cast<CastInst>(V))
498 return I->getOpcode() == Opcode && Op.match(I->getOperand(0));
499 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
500 return CE->getOpcode() == Opcode && Op.match(CE->getOperand(0));
506 template<typename OpTy>
507 inline CastClass_match<OpTy, Instruction::BitCast>
508 m_BitCast(const OpTy &Op) {
509 return CastClass_match<OpTy, Instruction::BitCast>(Op);
513 template<typename OpTy>
514 inline CastClass_match<OpTy, Instruction::PtrToInt>
515 m_PtrToInt(const OpTy &Op) {
516 return CastClass_match<OpTy, Instruction::PtrToInt>(Op);
520 template<typename OpTy>
521 inline CastClass_match<OpTy, Instruction::Trunc>
522 m_Trunc(const OpTy &Op) {
523 return CastClass_match<OpTy, Instruction::Trunc>(Op);
527 template<typename OpTy>
528 inline CastClass_match<OpTy, Instruction::SExt>
529 m_SExt(const OpTy &Op) {
530 return CastClass_match<OpTy, Instruction::SExt>(Op);
534 template<typename OpTy>
535 inline CastClass_match<OpTy, Instruction::ZExt>
536 m_ZExt(const OpTy &Op) {
537 return CastClass_match<OpTy, Instruction::ZExt>(Op);
541 //===----------------------------------------------------------------------===//
542 // Matchers for unary operators
545 template<typename LHS_t>
549 not_match(const LHS_t &LHS) : L(LHS) {}
551 template<typename OpTy>
552 bool match(OpTy *V) {
553 if (Instruction *I = dyn_cast<Instruction>(V))
554 if (I->getOpcode() == Instruction::Xor)
555 return matchIfNot(I->getOperand(0), I->getOperand(1));
556 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
557 if (CE->getOpcode() == Instruction::Xor)
558 return matchIfNot(CE->getOperand(0), CE->getOperand(1));
562 bool matchIfNot(Value *LHS, Value *RHS) {
563 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
564 return CI->isAllOnesValue() && L.match(LHS);
565 if (ConstantVector *CV = dyn_cast<ConstantVector>(RHS))
566 return CV->isAllOnesValue() && L.match(LHS);
571 template<typename LHS>
572 inline not_match<LHS> m_Not(const LHS &L) { return L; }
575 template<typename LHS_t>
579 neg_match(const LHS_t &LHS) : L(LHS) {}
581 template<typename OpTy>
582 bool match(OpTy *V) {
583 if (Instruction *I = dyn_cast<Instruction>(V))
584 if (I->getOpcode() == Instruction::Sub)
585 return matchIfNeg(I->getOperand(0), I->getOperand(1));
586 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
587 if (CE->getOpcode() == Instruction::Sub)
588 return matchIfNeg(CE->getOperand(0), CE->getOperand(1));
592 bool matchIfNeg(Value *LHS, Value *RHS) {
593 if (ConstantInt *C = dyn_cast<ConstantInt>(LHS))
594 return C->isZero() && L.match(RHS);
599 /// m_Neg - Match an integer negate.
600 template<typename LHS>
601 inline neg_match<LHS> m_Neg(const LHS &L) { return L; }
604 template<typename LHS_t>
608 fneg_match(const LHS_t &LHS) : L(LHS) {}
610 template<typename OpTy>
611 bool match(OpTy *V) {
612 if (Instruction *I = dyn_cast<Instruction>(V))
613 if (I->getOpcode() == Instruction::FSub)
614 return matchIfFNeg(I->getOperand(0), I->getOperand(1));
615 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
616 if (CE->getOpcode() == Instruction::FSub)
617 return matchIfFNeg(CE->getOperand(0), CE->getOperand(1));
621 bool matchIfFNeg(Value *LHS, Value *RHS) {
622 if (ConstantFP *C = dyn_cast<ConstantFP>(LHS))
623 return C->isNegativeZeroValue() && L.match(RHS);
628 /// m_FNeg - Match a floating point negate.
629 template<typename LHS>
630 inline fneg_match<LHS> m_FNeg(const LHS &L) { return L; }
633 //===----------------------------------------------------------------------===//
634 // Matchers for control flow.
637 template<typename Cond_t>
641 brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f)
642 : Cond(C), T(t), F(f) {
645 template<typename OpTy>
646 bool match(OpTy *V) {
647 if (BranchInst *BI = dyn_cast<BranchInst>(V))
648 if (BI->isConditional() && Cond.match(BI->getCondition())) {
649 T = BI->getSuccessor(0);
650 F = BI->getSuccessor(1);
657 template<typename Cond_t>
658 inline brc_match<Cond_t> m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) {
659 return brc_match<Cond_t>(C, T, F);
662 } // end namespace PatternMatch
663 } // end namespace llvm