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>(); }
54 struct constantint_ty {
56 explicit constantint_ty(int64_t val) : Val(val) {}
58 template<typename ITy>
60 return isa<ConstantInt>(V) && cast<ConstantInt>(V)->getSExtValue() == Val;
64 /// m_ConstantInt(int64_t) - Match a ConstantInt with a specific value
66 inline constantint_ty m_ConstantInt(int64_t Val) {
67 return constantint_ty(Val);
71 template<typename ITy>
73 if (const Constant *C = dyn_cast<Constant>(V))
74 return C->isNullValue();
79 /// m_Zero() - Match an arbitrary zero/null constant.
80 inline zero_ty m_Zero() { return zero_ty(); }
83 template<typename Class>
86 bind_ty(Class *&V) : VR(V) {}
88 template<typename ITy>
90 if (Class *CV = dyn_cast<Class>(V)) {
98 /// m_Value - Match a value, capturing it if we match.
99 inline bind_ty<Value> m_Value(Value *&V) { return V; }
101 /// m_ConstantInt - Match a ConstantInt, capturing the value if we match.
102 inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
104 //===----------------------------------------------------------------------===//
105 // Matchers for specific binary operators.
108 template<typename LHS_t, typename RHS_t,
109 unsigned Opcode, typename ConcreteTy = BinaryOperator>
110 struct BinaryOp_match {
114 BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
116 template<typename OpTy>
117 bool match(OpTy *V) {
118 if (V->getValueID() == Value::InstructionVal + Opcode) {
119 ConcreteTy *I = cast<ConcreteTy>(V);
120 return I->getOpcode() == Opcode && L.match(I->getOperand(0)) &&
121 R.match(I->getOperand(1));
123 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
124 return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
125 R.match(CE->getOperand(1));
130 template<typename LHS, typename RHS>
131 inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L,
133 return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);
136 template<typename LHS, typename RHS>
137 inline BinaryOp_match<LHS, RHS, Instruction::Sub> m_Sub(const LHS &L,
139 return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R);
142 template<typename LHS, typename RHS>
143 inline BinaryOp_match<LHS, RHS, Instruction::Mul> m_Mul(const LHS &L,
145 return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R);
148 template<typename LHS, typename RHS>
149 inline BinaryOp_match<LHS, RHS, Instruction::UDiv> m_UDiv(const LHS &L,
151 return BinaryOp_match<LHS, RHS, Instruction::UDiv>(L, R);
154 template<typename LHS, typename RHS>
155 inline BinaryOp_match<LHS, RHS, Instruction::SDiv> m_SDiv(const LHS &L,
157 return BinaryOp_match<LHS, RHS, Instruction::SDiv>(L, R);
160 template<typename LHS, typename RHS>
161 inline BinaryOp_match<LHS, RHS, Instruction::FDiv> m_FDiv(const LHS &L,
163 return BinaryOp_match<LHS, RHS, Instruction::FDiv>(L, R);
166 template<typename LHS, typename RHS>
167 inline BinaryOp_match<LHS, RHS, Instruction::URem> m_URem(const LHS &L,
169 return BinaryOp_match<LHS, RHS, Instruction::URem>(L, R);
172 template<typename LHS, typename RHS>
173 inline BinaryOp_match<LHS, RHS, Instruction::SRem> m_SRem(const LHS &L,
175 return BinaryOp_match<LHS, RHS, Instruction::SRem>(L, R);
178 template<typename LHS, typename RHS>
179 inline BinaryOp_match<LHS, RHS, Instruction::FRem> m_FRem(const LHS &L,
181 return BinaryOp_match<LHS, RHS, Instruction::FRem>(L, R);
184 template<typename LHS, typename RHS>
185 inline BinaryOp_match<LHS, RHS, Instruction::And> m_And(const LHS &L,
187 return BinaryOp_match<LHS, RHS, Instruction::And>(L, R);
190 template<typename LHS, typename RHS>
191 inline BinaryOp_match<LHS, RHS, Instruction::Or> m_Or(const LHS &L,
193 return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R);
196 template<typename LHS, typename RHS>
197 inline BinaryOp_match<LHS, RHS, Instruction::Xor> m_Xor(const LHS &L,
199 return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R);
202 template<typename LHS, typename RHS>
203 inline BinaryOp_match<LHS, RHS, Instruction::Shl> m_Shl(const LHS &L,
205 return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R);
208 template<typename LHS, typename RHS>
209 inline BinaryOp_match<LHS, RHS, Instruction::LShr> m_LShr(const LHS &L,
211 return BinaryOp_match<LHS, RHS, Instruction::LShr>(L, R);
214 template<typename LHS, typename RHS>
215 inline BinaryOp_match<LHS, RHS, Instruction::AShr> m_AShr(const LHS &L,
217 return BinaryOp_match<LHS, RHS, Instruction::AShr>(L, R);
220 //===----------------------------------------------------------------------===//
221 // Matchers for either AShr or LShr .. for convenience
223 template<typename LHS_t, typename RHS_t, typename ConcreteTy = BinaryOperator>
228 Shr_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
230 template<typename OpTy>
231 bool match(OpTy *V) {
232 if (V->getValueID() == Value::InstructionVal + Instruction::LShr ||
233 V->getValueID() == Value::InstructionVal + Instruction::AShr) {
234 ConcreteTy *I = cast<ConcreteTy>(V);
235 return (I->getOpcode() == Instruction::AShr ||
236 I->getOpcode() == Instruction::LShr) &&
237 L.match(I->getOperand(0)) &&
238 R.match(I->getOperand(1));
240 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
241 return (CE->getOpcode() == Instruction::LShr ||
242 CE->getOpcode() == Instruction::AShr) &&
243 L.match(CE->getOperand(0)) &&
244 R.match(CE->getOperand(1));
249 template<typename LHS, typename RHS>
250 inline Shr_match<LHS, RHS> m_Shr(const LHS &L, const RHS &R) {
251 return Shr_match<LHS, RHS>(L, R);
254 //===----------------------------------------------------------------------===//
255 // Matchers for binary classes
258 template<typename LHS_t, typename RHS_t, typename Class, typename OpcType>
259 struct BinaryOpClass_match {
264 BinaryOpClass_match(OpcType &Op, const LHS_t &LHS,
266 : Opcode(&Op), L(LHS), R(RHS) {}
267 BinaryOpClass_match(const LHS_t &LHS, const RHS_t &RHS)
268 : Opcode(0), L(LHS), R(RHS) {}
270 template<typename OpTy>
271 bool match(OpTy *V) {
272 if (Class *I = dyn_cast<Class>(V))
273 if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) {
275 *Opcode = I->getOpcode();
278 #if 0 // Doesn't handle constantexprs yet!
279 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
280 return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
281 R.match(CE->getOperand(1));
287 template<typename LHS, typename RHS>
288 inline BinaryOpClass_match<LHS, RHS, BinaryOperator, Instruction::BinaryOps>
289 m_Shift(Instruction::BinaryOps &Op, const LHS &L, const RHS &R) {
290 return BinaryOpClass_match<LHS, RHS,
291 BinaryOperator, Instruction::BinaryOps>(Op, L, R);
294 template<typename LHS, typename RHS>
295 inline BinaryOpClass_match<LHS, RHS, BinaryOperator, Instruction::BinaryOps>
296 m_Shift(const LHS &L, const RHS &R) {
297 return BinaryOpClass_match<LHS, RHS,
298 BinaryOperator, Instruction::BinaryOps>(L, R);
301 //===----------------------------------------------------------------------===//
302 // Matchers for CmpInst classes
305 template<typename LHS_t, typename RHS_t, typename Class, typename PredicateTy>
306 struct CmpClass_match {
307 PredicateTy &Predicate;
311 CmpClass_match(PredicateTy &Pred, const LHS_t &LHS,
313 : Predicate(Pred), L(LHS), R(RHS) {}
315 template<typename OpTy>
316 bool match(OpTy *V) {
317 if (Class *I = dyn_cast<Class>(V))
318 if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) {
319 Predicate = I->getPredicate();
326 template<typename LHS, typename RHS>
327 inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>
328 m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
329 return CmpClass_match<LHS, RHS,
330 ICmpInst, ICmpInst::Predicate>(Pred, L, R);
333 template<typename LHS, typename RHS>
334 inline CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>
335 m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
336 return CmpClass_match<LHS, RHS,
337 FCmpInst, FCmpInst::Predicate>(Pred, L, R);
340 //===----------------------------------------------------------------------===//
341 // Matchers for SelectInst classes
344 template<typename Cond_t, typename LHS_t, typename RHS_t>
345 struct SelectClass_match {
350 SelectClass_match(const Cond_t &Cond, const LHS_t &LHS,
352 : C(Cond), L(LHS), R(RHS) {}
354 template<typename OpTy>
355 bool match(OpTy *V) {
356 if (SelectInst *I = dyn_cast<SelectInst>(V))
357 return C.match(I->getOperand(0)) &&
358 L.match(I->getOperand(1)) &&
359 R.match(I->getOperand(2));
364 template<typename Cond, typename LHS, typename RHS>
365 inline SelectClass_match<Cond, RHS, LHS>
366 m_Select(const Cond &C, const LHS &L, const RHS &R) {
367 return SelectClass_match<Cond, LHS, RHS>(C, L, R);
370 /// m_SelectCst - This matches a select of two constants, e.g.:
371 /// m_SelectCst(m_Value(V), -1, 0)
372 template<typename Cond>
373 inline SelectClass_match<Cond, constantint_ty, constantint_ty>
374 m_SelectCst(const Cond &C, int64_t L, int64_t R) {
375 return SelectClass_match<Cond, constantint_ty,
376 constantint_ty>(C, m_ConstantInt(L),
381 //===----------------------------------------------------------------------===//
382 // Matchers for CastInst classes
385 template<typename Op_t, typename Class>
386 struct CastClass_match {
389 CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {}
391 template<typename OpTy>
392 bool match(OpTy *V) {
393 if (Class *I = dyn_cast<Class>(V))
394 return Op.match(I->getOperand(0));
399 template<typename Class, typename OpTy>
400 inline CastClass_match<OpTy, Class> m_Cast(const OpTy &Op) {
401 return CastClass_match<OpTy, Class>(Op);
405 //===----------------------------------------------------------------------===//
406 // Matchers for unary operators
409 template<typename LHS_t>
413 not_match(const LHS_t &LHS) : L(LHS) {}
415 template<typename OpTy>
416 bool match(OpTy *V) {
417 if (Instruction *I = dyn_cast<Instruction>(V))
418 if (I->getOpcode() == Instruction::Xor)
419 return matchIfNot(I->getOperand(0), I->getOperand(1));
420 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
421 if (CE->getOpcode() == Instruction::Xor)
422 return matchIfNot(CE->getOperand(0), CE->getOperand(1));
423 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
424 return L.match(ConstantExpr::getNot(CI));
428 bool matchIfNot(Value *LHS, Value *RHS) {
429 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
430 return CI->isAllOnesValue() && L.match(LHS);
431 if (ConstantInt *CI = dyn_cast<ConstantInt>(LHS))
432 return CI->isAllOnesValue() && L.match(RHS);
433 if (ConstantVector *CV = dyn_cast<ConstantVector>(RHS))
434 return CV->isAllOnesValue() && L.match(LHS);
435 if (ConstantVector *CV = dyn_cast<ConstantVector>(LHS))
436 return CV->isAllOnesValue() && L.match(RHS);
441 template<typename LHS>
442 inline not_match<LHS> m_Not(const LHS &L) { return L; }
445 template<typename LHS_t>
449 neg_match(const LHS_t &LHS) : L(LHS) {}
451 template<typename OpTy>
452 bool match(OpTy *V) {
453 if (Instruction *I = dyn_cast<Instruction>(V))
454 if (I->getOpcode() == Instruction::Sub)
455 return matchIfNeg(I->getOperand(0), I->getOperand(1));
456 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
457 if (CE->getOpcode() == Instruction::Sub)
458 return matchIfNeg(CE->getOperand(0), CE->getOperand(1));
459 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
460 return L.match(ConstantExpr::getNeg(CI));
464 bool matchIfNeg(Value *LHS, Value *RHS) {
465 return LHS == ConstantExpr::getZeroValueForNegationExpr(LHS->getType()) &&
470 template<typename LHS>
471 inline neg_match<LHS> m_Neg(const LHS &L) { return L; }
474 //===----------------------------------------------------------------------===//
475 // Matchers for control flow
478 template<typename Cond_t>
482 brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f)
483 : Cond(C), T(t), F(f) {
486 template<typename OpTy>
487 bool match(OpTy *V) {
488 if (BranchInst *BI = dyn_cast<BranchInst>(V))
489 if (BI->isConditional()) {
490 if (Cond.match(BI->getCondition())) {
491 T = BI->getSuccessor(0);
492 F = BI->getSuccessor(1);
500 template<typename Cond_t>
501 inline brc_match<Cond_t> m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F){
502 return brc_match<Cond_t>(C, T, F);
506 }} // end llvm::match