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();
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 if (const Constant *C = dyn_cast<Constant>(V))
82 return C->isNullValue();
87 /// m_Zero() - Match an arbitrary zero/null constant.
88 inline zero_ty m_Zero() { return zero_ty(); }
91 template<typename Class>
94 bind_ty(Class *&V) : VR(V) {}
96 template<typename ITy>
98 if (Class *CV = dyn_cast<Class>(V)) {
106 /// m_Value - Match a value, capturing it if we match.
107 inline bind_ty<Value> m_Value(Value *&V) { return V; }
109 /// m_ConstantInt - Match a ConstantInt, capturing the value if we match.
110 inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
112 /// specificval_ty - Match a specified Value*.
113 struct specificval_ty {
115 specificval_ty(const Value *V) : Val(V) {}
117 template<typename ITy>
123 /// m_Specific - Match if we have a specific specified value.
124 inline specificval_ty m_Specific(const Value *V) { return V; }
127 //===----------------------------------------------------------------------===//
128 // Matchers for specific binary operators.
131 template<typename LHS_t, typename RHS_t,
132 unsigned Opcode, typename ConcreteTy = BinaryOperator>
133 struct BinaryOp_match {
137 BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
139 template<typename OpTy>
140 bool match(OpTy *V) {
141 if (V->getValueID() == Value::InstructionVal + Opcode) {
142 ConcreteTy *I = cast<ConcreteTy>(V);
143 return I->getOpcode() == Opcode && L.match(I->getOperand(0)) &&
144 R.match(I->getOperand(1));
146 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
147 return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
148 R.match(CE->getOperand(1));
153 template<typename LHS, typename RHS>
154 inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L,
156 return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);
159 template<typename LHS, typename RHS>
160 inline BinaryOp_match<LHS, RHS, Instruction::FAdd> m_FAdd(const LHS &L,
162 return BinaryOp_match<LHS, RHS, Instruction::FAdd>(L, R);
165 template<typename LHS, typename RHS>
166 inline BinaryOp_match<LHS, RHS, Instruction::Sub> m_Sub(const LHS &L,
168 return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R);
171 template<typename LHS, typename RHS>
172 inline BinaryOp_match<LHS, RHS, Instruction::FSub> m_FSub(const LHS &L,
174 return BinaryOp_match<LHS, RHS, Instruction::FSub>(L, R);
177 template<typename LHS, typename RHS>
178 inline BinaryOp_match<LHS, RHS, Instruction::Mul> m_Mul(const LHS &L,
180 return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R);
183 template<typename LHS, typename RHS>
184 inline BinaryOp_match<LHS, RHS, Instruction::FMul> m_FMul(const LHS &L,
186 return BinaryOp_match<LHS, RHS, Instruction::FMul>(L, R);
189 template<typename LHS, typename RHS>
190 inline BinaryOp_match<LHS, RHS, Instruction::UDiv> m_UDiv(const LHS &L,
192 return BinaryOp_match<LHS, RHS, Instruction::UDiv>(L, R);
195 template<typename LHS, typename RHS>
196 inline BinaryOp_match<LHS, RHS, Instruction::SDiv> m_SDiv(const LHS &L,
198 return BinaryOp_match<LHS, RHS, Instruction::SDiv>(L, R);
201 template<typename LHS, typename RHS>
202 inline BinaryOp_match<LHS, RHS, Instruction::FDiv> m_FDiv(const LHS &L,
204 return BinaryOp_match<LHS, RHS, Instruction::FDiv>(L, R);
207 template<typename LHS, typename RHS>
208 inline BinaryOp_match<LHS, RHS, Instruction::URem> m_URem(const LHS &L,
210 return BinaryOp_match<LHS, RHS, Instruction::URem>(L, R);
213 template<typename LHS, typename RHS>
214 inline BinaryOp_match<LHS, RHS, Instruction::SRem> m_SRem(const LHS &L,
216 return BinaryOp_match<LHS, RHS, Instruction::SRem>(L, R);
219 template<typename LHS, typename RHS>
220 inline BinaryOp_match<LHS, RHS, Instruction::FRem> m_FRem(const LHS &L,
222 return BinaryOp_match<LHS, RHS, Instruction::FRem>(L, R);
225 template<typename LHS, typename RHS>
226 inline BinaryOp_match<LHS, RHS, Instruction::And> m_And(const LHS &L,
228 return BinaryOp_match<LHS, RHS, Instruction::And>(L, R);
231 template<typename LHS, typename RHS>
232 inline BinaryOp_match<LHS, RHS, Instruction::Or> m_Or(const LHS &L,
234 return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R);
237 template<typename LHS, typename RHS>
238 inline BinaryOp_match<LHS, RHS, Instruction::Xor> m_Xor(const LHS &L,
240 return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R);
243 template<typename LHS, typename RHS>
244 inline BinaryOp_match<LHS, RHS, Instruction::Shl> m_Shl(const LHS &L,
246 return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R);
249 template<typename LHS, typename RHS>
250 inline BinaryOp_match<LHS, RHS, Instruction::LShr> m_LShr(const LHS &L,
252 return BinaryOp_match<LHS, RHS, Instruction::LShr>(L, R);
255 template<typename LHS, typename RHS>
256 inline BinaryOp_match<LHS, RHS, Instruction::AShr> m_AShr(const LHS &L,
258 return BinaryOp_match<LHS, RHS, Instruction::AShr>(L, R);
261 //===----------------------------------------------------------------------===//
262 // Matchers for either AShr or LShr .. for convenience
264 template<typename LHS_t, typename RHS_t, typename ConcreteTy = BinaryOperator>
269 Shr_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
271 template<typename OpTy>
272 bool match(OpTy *V) {
273 if (V->getValueID() == Value::InstructionVal + Instruction::LShr ||
274 V->getValueID() == Value::InstructionVal + Instruction::AShr) {
275 ConcreteTy *I = cast<ConcreteTy>(V);
276 return (I->getOpcode() == Instruction::AShr ||
277 I->getOpcode() == Instruction::LShr) &&
278 L.match(I->getOperand(0)) &&
279 R.match(I->getOperand(1));
281 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
282 return (CE->getOpcode() == Instruction::LShr ||
283 CE->getOpcode() == Instruction::AShr) &&
284 L.match(CE->getOperand(0)) &&
285 R.match(CE->getOperand(1));
290 template<typename LHS, typename RHS>
291 inline Shr_match<LHS, RHS> m_Shr(const LHS &L, const RHS &R) {
292 return Shr_match<LHS, RHS>(L, R);
295 //===----------------------------------------------------------------------===//
296 // Matchers for binary classes
299 template<typename LHS_t, typename RHS_t, typename Class, typename OpcType>
300 struct BinaryOpClass_match {
305 BinaryOpClass_match(OpcType &Op, const LHS_t &LHS,
307 : Opcode(&Op), L(LHS), R(RHS) {}
308 BinaryOpClass_match(const LHS_t &LHS, const RHS_t &RHS)
309 : Opcode(0), L(LHS), R(RHS) {}
311 template<typename OpTy>
312 bool match(OpTy *V) {
313 if (Class *I = dyn_cast<Class>(V))
314 if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) {
316 *Opcode = I->getOpcode();
319 #if 0 // Doesn't handle constantexprs yet!
320 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
321 return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
322 R.match(CE->getOperand(1));
328 template<typename LHS, typename RHS>
329 inline BinaryOpClass_match<LHS, RHS, BinaryOperator, Instruction::BinaryOps>
330 m_Shift(Instruction::BinaryOps &Op, const LHS &L, const RHS &R) {
331 return BinaryOpClass_match<LHS, RHS,
332 BinaryOperator, Instruction::BinaryOps>(Op, L, R);
335 template<typename LHS, typename RHS>
336 inline BinaryOpClass_match<LHS, RHS, BinaryOperator, Instruction::BinaryOps>
337 m_Shift(const LHS &L, const RHS &R) {
338 return BinaryOpClass_match<LHS, RHS,
339 BinaryOperator, Instruction::BinaryOps>(L, R);
342 //===----------------------------------------------------------------------===//
343 // Matchers for CmpInst classes
346 template<typename LHS_t, typename RHS_t, typename Class, typename PredicateTy>
347 struct CmpClass_match {
348 PredicateTy &Predicate;
352 CmpClass_match(PredicateTy &Pred, const LHS_t &LHS,
354 : Predicate(Pred), L(LHS), R(RHS) {}
356 template<typename OpTy>
357 bool match(OpTy *V) {
358 if (Class *I = dyn_cast<Class>(V))
359 if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) {
360 Predicate = I->getPredicate();
367 template<typename LHS, typename RHS>
368 inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>
369 m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
370 return CmpClass_match<LHS, RHS,
371 ICmpInst, ICmpInst::Predicate>(Pred, L, R);
374 template<typename LHS, typename RHS>
375 inline CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>
376 m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
377 return CmpClass_match<LHS, RHS,
378 FCmpInst, FCmpInst::Predicate>(Pred, L, R);
381 //===----------------------------------------------------------------------===//
382 // Matchers for SelectInst classes
385 template<typename Cond_t, typename LHS_t, typename RHS_t>
386 struct SelectClass_match {
391 SelectClass_match(const Cond_t &Cond, const LHS_t &LHS,
393 : C(Cond), L(LHS), R(RHS) {}
395 template<typename OpTy>
396 bool match(OpTy *V) {
397 if (SelectInst *I = dyn_cast<SelectInst>(V))
398 return C.match(I->getOperand(0)) &&
399 L.match(I->getOperand(1)) &&
400 R.match(I->getOperand(2));
405 template<typename Cond, typename LHS, typename RHS>
406 inline SelectClass_match<Cond, RHS, LHS>
407 m_Select(const Cond &C, const LHS &L, const RHS &R) {
408 return SelectClass_match<Cond, LHS, RHS>(C, L, R);
411 /// m_SelectCst - This matches a select of two constants, e.g.:
412 /// m_SelectCst(m_Value(V), -1, 0)
413 template<int64_t L, int64_t R, typename Cond>
414 inline SelectClass_match<Cond, constantint_ty<L>, constantint_ty<R> >
415 m_SelectCst(const Cond &C) {
416 return SelectClass_match<Cond, constantint_ty<L>,
417 constantint_ty<R> >(C, m_ConstantInt<L>(),
422 //===----------------------------------------------------------------------===//
423 // Matchers for CastInst classes
426 template<typename Op_t, typename Class>
427 struct CastClass_match {
430 CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {}
432 template<typename OpTy>
433 bool match(OpTy *V) {
434 if (Class *I = dyn_cast<Class>(V))
435 return Op.match(I->getOperand(0));
440 template<typename Class, typename OpTy>
441 inline CastClass_match<OpTy, Class> m_Cast(const OpTy &Op) {
442 return CastClass_match<OpTy, Class>(Op);
446 //===----------------------------------------------------------------------===//
447 // Matchers for unary operators
450 template<typename LHS_t>
454 not_match(const LHS_t &LHS) : L(LHS) {}
456 template<typename OpTy>
457 bool match(OpTy *V) {
458 if (Instruction *I = dyn_cast<Instruction>(V))
459 if (I->getOpcode() == Instruction::Xor)
460 return matchIfNot(I->getOperand(0), I->getOperand(1));
461 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
462 if (CE->getOpcode() == Instruction::Xor)
463 return matchIfNot(CE->getOperand(0), CE->getOperand(1));
464 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
465 return L.match(ConstantExpr::getNot(CI));
469 bool matchIfNot(Value *LHS, Value *RHS) {
470 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
471 return CI->isAllOnesValue() && L.match(LHS);
472 if (ConstantInt *CI = dyn_cast<ConstantInt>(LHS))
473 return CI->isAllOnesValue() && L.match(RHS);
474 if (ConstantVector *CV = dyn_cast<ConstantVector>(RHS))
475 return CV->isAllOnesValue() && L.match(LHS);
476 if (ConstantVector *CV = dyn_cast<ConstantVector>(LHS))
477 return CV->isAllOnesValue() && L.match(RHS);
482 template<typename LHS>
483 inline not_match<LHS> m_Not(const LHS &L) { return L; }
486 template<typename LHS_t>
490 neg_match(const LHS_t &LHS) : L(LHS) {}
492 template<typename OpTy>
493 bool match(OpTy *V) {
494 if (Instruction *I = dyn_cast<Instruction>(V))
495 if (I->getOpcode() == Instruction::Sub)
496 return matchIfNeg(I->getOperand(0), I->getOperand(1));
497 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
498 if (CE->getOpcode() == Instruction::Sub)
499 return matchIfNeg(CE->getOperand(0), CE->getOperand(1));
500 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
501 return L.match(ConstantExpr::getNeg(CI));
505 bool matchIfNeg(Value *LHS, Value *RHS) {
506 return LHS == ConstantExpr::getZeroValueForNegationExpr(LHS->getType()) &&
511 template<typename LHS>
512 inline neg_match<LHS> m_Neg(const LHS &L) { return L; }
515 template<typename LHS_t>
519 fneg_match(const LHS_t &LHS) : L(LHS) {}
521 template<typename OpTy>
522 bool match(OpTy *V) {
523 if (Instruction *I = dyn_cast<Instruction>(V))
524 if (I->getOpcode() == Instruction::FSub)
525 return matchIfFNeg(I->getOperand(0), I->getOperand(1));
526 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
527 if (CE->getOpcode() == Instruction::FSub)
528 return matchIfFNeg(CE->getOperand(0), CE->getOperand(1));
529 if (ConstantFP *CF = dyn_cast<ConstantFP>(V))
530 return L.match(ConstantExpr::getFNeg(CF));
534 bool matchIfFNeg(Value *LHS, Value *RHS) {
535 return LHS == ConstantExpr::getZeroValueForNegationExpr(LHS->getType()) &&
540 template<typename LHS>
541 inline fneg_match<LHS> m_FNeg(const LHS &L) { return L; }
544 //===----------------------------------------------------------------------===//
545 // Matchers for control flow
548 template<typename Cond_t>
552 brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f)
553 : Cond(C), T(t), F(f) {
556 template<typename OpTy>
557 bool match(OpTy *V) {
558 if (BranchInst *BI = dyn_cast<BranchInst>(V))
559 if (BI->isConditional()) {
560 if (Cond.match(BI->getCondition())) {
561 T = BI->getSuccessor(0);
562 F = BI->getSuccessor(1);
570 template<typename Cond_t>
571 inline brc_match<Cond_t> m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) {
572 return brc_match<Cond_t>(C, T, F);
575 } // end namespace PatternMatch
576 } // end namespace llvm