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"
34 #include "llvm/LLVMContext.h"
37 namespace PatternMatch {
39 template<typename Val, typename Pattern>
40 bool match(Val *V, const Pattern &P, LLVMContext &Context) {
41 return const_cast<Pattern&>(P).match(V, Context);
44 template<typename Class>
46 template<typename ITy>
47 bool match(ITy *V, LLVMContext&) { return isa<Class>(V); }
50 /// m_Value() - Match an arbitrary value and ignore it.
51 inline leaf_ty<Value> m_Value() { return leaf_ty<Value>(); }
52 /// m_ConstantInt() - Match an arbitrary ConstantInt and ignore it.
53 inline leaf_ty<ConstantInt> m_ConstantInt() { return leaf_ty<ConstantInt>(); }
56 struct constantint_ty {
57 template<typename ITy>
58 bool match(ITy *V, LLVMContext&) {
59 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
60 const APInt &CIV = CI->getValue();
63 // If Val is negative, and CI is shorter than it, truncate to the right
64 // number of bits. If it is larger, then we have to sign extend. Just
65 // compare their negated values.
72 /// m_ConstantInt(int64_t) - Match a ConstantInt with a specific value
75 inline constantint_ty<Val> m_ConstantInt() {
76 return constantint_ty<Val>();
80 template<typename ITy>
81 bool match(ITy *V, LLVMContext&) {
82 if (const Constant *C = dyn_cast<Constant>(V))
83 return C->isNullValue();
88 /// m_Zero() - Match an arbitrary zero/null constant.
89 inline zero_ty m_Zero() { return zero_ty(); }
92 template<typename Class>
95 bind_ty(Class *&V) : VR(V) {}
97 template<typename ITy>
98 bool match(ITy *V, LLVMContext&) {
99 if (Class *CV = dyn_cast<Class>(V)) {
107 /// m_Value - Match a value, capturing it if we match.
108 inline bind_ty<Value> m_Value(Value *&V) { return V; }
110 /// m_ConstantInt - Match a ConstantInt, capturing the value if we match.
111 inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
113 /// specificval_ty - Match a specified Value*.
114 struct specificval_ty {
116 specificval_ty(const Value *V) : Val(V) {}
118 template<typename ITy>
119 bool match(ITy *V, LLVMContext&) {
124 /// m_Specific - Match if we have a specific specified value.
125 inline specificval_ty m_Specific(const Value *V) { return V; }
128 //===----------------------------------------------------------------------===//
129 // Matchers for specific binary operators.
132 template<typename LHS_t, typename RHS_t,
133 unsigned Opcode, typename ConcreteTy = BinaryOperator>
134 struct BinaryOp_match {
138 BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
140 template<typename OpTy>
141 bool match(OpTy *V, LLVMContext &Context) {
142 if (V->getValueID() == Value::InstructionVal + Opcode) {
143 ConcreteTy *I = cast<ConcreteTy>(V);
144 return I->getOpcode() == Opcode && L.match(I->getOperand(0), Context) &&
145 R.match(I->getOperand(1), Context);
147 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
148 return CE->getOpcode() == Opcode && L.match(CE->getOperand(0), Context) &&
149 R.match(CE->getOperand(1), Context);
154 template<typename LHS, typename RHS>
155 inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L,
157 return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);
160 template<typename LHS, typename RHS>
161 inline BinaryOp_match<LHS, RHS, Instruction::FAdd> m_FAdd(const LHS &L,
163 return BinaryOp_match<LHS, RHS, Instruction::FAdd>(L, R);
166 template<typename LHS, typename RHS>
167 inline BinaryOp_match<LHS, RHS, Instruction::Sub> m_Sub(const LHS &L,
169 return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R);
172 template<typename LHS, typename RHS>
173 inline BinaryOp_match<LHS, RHS, Instruction::FSub> m_FSub(const LHS &L,
175 return BinaryOp_match<LHS, RHS, Instruction::FSub>(L, R);
178 template<typename LHS, typename RHS>
179 inline BinaryOp_match<LHS, RHS, Instruction::Mul> m_Mul(const LHS &L,
181 return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R);
184 template<typename LHS, typename RHS>
185 inline BinaryOp_match<LHS, RHS, Instruction::FMul> m_FMul(const LHS &L,
187 return BinaryOp_match<LHS, RHS, Instruction::FMul>(L, R);
190 template<typename LHS, typename RHS>
191 inline BinaryOp_match<LHS, RHS, Instruction::UDiv> m_UDiv(const LHS &L,
193 return BinaryOp_match<LHS, RHS, Instruction::UDiv>(L, R);
196 template<typename LHS, typename RHS>
197 inline BinaryOp_match<LHS, RHS, Instruction::SDiv> m_SDiv(const LHS &L,
199 return BinaryOp_match<LHS, RHS, Instruction::SDiv>(L, R);
202 template<typename LHS, typename RHS>
203 inline BinaryOp_match<LHS, RHS, Instruction::FDiv> m_FDiv(const LHS &L,
205 return BinaryOp_match<LHS, RHS, Instruction::FDiv>(L, R);
208 template<typename LHS, typename RHS>
209 inline BinaryOp_match<LHS, RHS, Instruction::URem> m_URem(const LHS &L,
211 return BinaryOp_match<LHS, RHS, Instruction::URem>(L, R);
214 template<typename LHS, typename RHS>
215 inline BinaryOp_match<LHS, RHS, Instruction::SRem> m_SRem(const LHS &L,
217 return BinaryOp_match<LHS, RHS, Instruction::SRem>(L, R);
220 template<typename LHS, typename RHS>
221 inline BinaryOp_match<LHS, RHS, Instruction::FRem> m_FRem(const LHS &L,
223 return BinaryOp_match<LHS, RHS, Instruction::FRem>(L, R);
226 template<typename LHS, typename RHS>
227 inline BinaryOp_match<LHS, RHS, Instruction::And> m_And(const LHS &L,
229 return BinaryOp_match<LHS, RHS, Instruction::And>(L, R);
232 template<typename LHS, typename RHS>
233 inline BinaryOp_match<LHS, RHS, Instruction::Or> m_Or(const LHS &L,
235 return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R);
238 template<typename LHS, typename RHS>
239 inline BinaryOp_match<LHS, RHS, Instruction::Xor> m_Xor(const LHS &L,
241 return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R);
244 template<typename LHS, typename RHS>
245 inline BinaryOp_match<LHS, RHS, Instruction::Shl> m_Shl(const LHS &L,
247 return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R);
250 template<typename LHS, typename RHS>
251 inline BinaryOp_match<LHS, RHS, Instruction::LShr> m_LShr(const LHS &L,
253 return BinaryOp_match<LHS, RHS, Instruction::LShr>(L, R);
256 template<typename LHS, typename RHS>
257 inline BinaryOp_match<LHS, RHS, Instruction::AShr> m_AShr(const LHS &L,
259 return BinaryOp_match<LHS, RHS, Instruction::AShr>(L, R);
262 //===----------------------------------------------------------------------===//
263 // Matchers for either AShr or LShr .. for convenience
265 template<typename LHS_t, typename RHS_t, typename ConcreteTy = BinaryOperator>
270 Shr_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
272 template<typename OpTy>
273 bool match(OpTy *V, LLVMContext &Context) {
274 if (V->getValueID() == Value::InstructionVal + Instruction::LShr ||
275 V->getValueID() == Value::InstructionVal + Instruction::AShr) {
276 ConcreteTy *I = cast<ConcreteTy>(V);
277 return (I->getOpcode() == Instruction::AShr ||
278 I->getOpcode() == Instruction::LShr) &&
279 L.match(I->getOperand(0), Context) &&
280 R.match(I->getOperand(1), Context);
282 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
283 return (CE->getOpcode() == Instruction::LShr ||
284 CE->getOpcode() == Instruction::AShr) &&
285 L.match(CE->getOperand(0), Context) &&
286 R.match(CE->getOperand(1), Context);
291 template<typename LHS, typename RHS>
292 inline Shr_match<LHS, RHS> m_Shr(const LHS &L, const RHS &R) {
293 return Shr_match<LHS, RHS>(L, R);
296 //===----------------------------------------------------------------------===//
297 // Matchers for binary classes
300 template<typename LHS_t, typename RHS_t, typename Class, typename OpcType>
301 struct BinaryOpClass_match {
306 BinaryOpClass_match(OpcType &Op, const LHS_t &LHS,
308 : Opcode(&Op), L(LHS), R(RHS) {}
309 BinaryOpClass_match(const LHS_t &LHS, const RHS_t &RHS)
310 : Opcode(0), L(LHS), R(RHS) {}
312 template<typename OpTy>
313 bool match(OpTy *V, LLVMContext &Context) {
314 if (Class *I = dyn_cast<Class>(V))
315 if (L.match(I->getOperand(0), Context) &&
316 R.match(I->getOperand(1), Context)) {
318 *Opcode = I->getOpcode();
321 #if 0 // Doesn't handle constantexprs yet!
322 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
323 return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
324 R.match(CE->getOperand(1));
330 template<typename LHS, typename RHS>
331 inline BinaryOpClass_match<LHS, RHS, BinaryOperator, Instruction::BinaryOps>
332 m_Shift(Instruction::BinaryOps &Op, const LHS &L, const RHS &R) {
333 return BinaryOpClass_match<LHS, RHS,
334 BinaryOperator, Instruction::BinaryOps>(Op, L, R);
337 template<typename LHS, typename RHS>
338 inline BinaryOpClass_match<LHS, RHS, BinaryOperator, Instruction::BinaryOps>
339 m_Shift(const LHS &L, const RHS &R) {
340 return BinaryOpClass_match<LHS, RHS,
341 BinaryOperator, Instruction::BinaryOps>(L, R);
344 //===----------------------------------------------------------------------===//
345 // Matchers for CmpInst classes
348 template<typename LHS_t, typename RHS_t, typename Class, typename PredicateTy>
349 struct CmpClass_match {
350 PredicateTy &Predicate;
354 CmpClass_match(PredicateTy &Pred, const LHS_t &LHS,
356 : Predicate(Pred), L(LHS), R(RHS) {}
358 template<typename OpTy>
359 bool match(OpTy *V, LLVMContext &Context) {
360 if (Class *I = dyn_cast<Class>(V))
361 if (L.match(I->getOperand(0), Context) &&
362 R.match(I->getOperand(1), Context)) {
363 Predicate = I->getPredicate();
370 template<typename LHS, typename RHS>
371 inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>
372 m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
373 return CmpClass_match<LHS, RHS,
374 ICmpInst, ICmpInst::Predicate>(Pred, L, R);
377 template<typename LHS, typename RHS>
378 inline CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>
379 m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
380 return CmpClass_match<LHS, RHS,
381 FCmpInst, FCmpInst::Predicate>(Pred, L, R);
384 //===----------------------------------------------------------------------===//
385 // Matchers for SelectInst classes
388 template<typename Cond_t, typename LHS_t, typename RHS_t>
389 struct SelectClass_match {
394 SelectClass_match(const Cond_t &Cond, const LHS_t &LHS,
396 : C(Cond), L(LHS), R(RHS) {}
398 template<typename OpTy>
399 bool match(OpTy *V, LLVMContext &Context) {
400 if (SelectInst *I = dyn_cast<SelectInst>(V))
401 return C.match(I->getOperand(0), Context) &&
402 L.match(I->getOperand(1), Context) &&
403 R.match(I->getOperand(2), Context);
408 template<typename Cond, typename LHS, typename RHS>
409 inline SelectClass_match<Cond, LHS, RHS>
410 m_Select(const Cond &C, const LHS &L, const RHS &R) {
411 return SelectClass_match<Cond, LHS, RHS>(C, L, R);
414 /// m_SelectCst - This matches a select of two constants, e.g.:
415 /// m_SelectCst(m_Value(V), -1, 0)
416 template<int64_t L, int64_t R, typename Cond>
417 inline SelectClass_match<Cond, constantint_ty<L>, constantint_ty<R> >
418 m_SelectCst(const Cond &C) {
419 return SelectClass_match<Cond, constantint_ty<L>,
420 constantint_ty<R> >(C, m_ConstantInt<L>(),
425 //===----------------------------------------------------------------------===//
426 // Matchers for CastInst classes
429 template<typename Op_t, typename Class>
430 struct CastClass_match {
433 CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {}
435 template<typename OpTy>
436 bool match(OpTy *V, LLVMContext &Context) {
437 if (Class *I = dyn_cast<Class>(V))
438 return Op.match(I->getOperand(0), Context);
443 template<typename Class, typename OpTy>
444 inline CastClass_match<OpTy, Class> m_Cast(const OpTy &Op) {
445 return CastClass_match<OpTy, Class>(Op);
449 //===----------------------------------------------------------------------===//
450 // Matchers for unary operators
453 template<typename LHS_t>
457 not_match(const LHS_t &LHS) : L(LHS) {}
459 template<typename OpTy>
460 bool match(OpTy *V, LLVMContext &Context) {
461 if (Instruction *I = dyn_cast<Instruction>(V))
462 if (I->getOpcode() == Instruction::Xor)
463 return matchIfNot(I->getOperand(0), I->getOperand(1), Context);
464 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
465 if (CE->getOpcode() == Instruction::Xor)
466 return matchIfNot(CE->getOperand(0), CE->getOperand(1), Context);
467 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
468 return L.match(Context.getConstantExprNot(CI), Context);
472 bool matchIfNot(Value *LHS, Value *RHS, LLVMContext &Context) {
473 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
474 return CI->isAllOnesValue() && L.match(LHS, Context);
475 if (ConstantInt *CI = dyn_cast<ConstantInt>(LHS))
476 return CI->isAllOnesValue() && L.match(RHS, Context);
477 if (ConstantVector *CV = dyn_cast<ConstantVector>(RHS))
478 return CV->isAllOnesValue() && L.match(LHS, Context);
479 if (ConstantVector *CV = dyn_cast<ConstantVector>(LHS))
480 return CV->isAllOnesValue() && L.match(RHS, Context);
485 template<typename LHS>
486 inline not_match<LHS> m_Not(const LHS &L) { return L; }
489 template<typename LHS_t>
493 neg_match(const LHS_t &LHS) : L(LHS) {}
495 template<typename OpTy>
496 bool match(OpTy *V, LLVMContext &Context) {
497 if (Instruction *I = dyn_cast<Instruction>(V))
498 if (I->getOpcode() == Instruction::Sub)
499 return matchIfNeg(I->getOperand(0), I->getOperand(1), Context);
500 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
501 if (CE->getOpcode() == Instruction::Sub)
502 return matchIfNeg(CE->getOperand(0), CE->getOperand(1), Context);
503 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
504 return L.match(Context.getConstantExprNeg(CI), Context);
508 bool matchIfNeg(Value *LHS, Value *RHS, LLVMContext &Context) {
509 return LHS == Context.getZeroValueForNegation(LHS->getType()) &&
510 L.match(RHS, Context);
514 template<typename LHS>
515 inline neg_match<LHS> m_Neg(const LHS &L) { return L; }
518 template<typename LHS_t>
522 fneg_match(const LHS_t &LHS) : L(LHS) {}
524 template<typename OpTy>
525 bool match(OpTy *V, LLVMContext &Context) {
526 if (Instruction *I = dyn_cast<Instruction>(V))
527 if (I->getOpcode() == Instruction::FSub)
528 return matchIfFNeg(I->getOperand(0), I->getOperand(1), Context);
529 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
530 if (CE->getOpcode() == Instruction::FSub)
531 return matchIfFNeg(CE->getOperand(0), CE->getOperand(1), Context);
532 if (ConstantFP *CF = dyn_cast<ConstantFP>(V))
533 return L.match(Context.getConstantExprFNeg(CF), Context);
537 bool matchIfFNeg(Value *LHS, Value *RHS, LLVMContext &Context) {
538 return LHS == Context.getZeroValueForNegation(LHS->getType()) &&
539 L.match(RHS, Context);
543 template<typename LHS>
544 inline fneg_match<LHS> m_FNeg(const LHS &L) { return L; }
547 //===----------------------------------------------------------------------===//
548 // Matchers for control flow
551 template<typename Cond_t>
555 brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f)
556 : Cond(C), T(t), F(f) {
559 template<typename OpTy>
560 bool match(OpTy *V, LLVMContext &Context) {
561 if (BranchInst *BI = dyn_cast<BranchInst>(V))
562 if (BI->isConditional()) {
563 if (Cond.match(BI->getCondition(), Context)) {
564 T = BI->getSuccessor(0);
565 F = BI->getSuccessor(1);
573 template<typename Cond_t>
574 inline brc_match<Cond_t> m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) {
575 return brc_match<Cond_t>(C, T, F);
578 } // end namespace PatternMatch
579 } // end namespace llvm