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 template<typename ITy>
57 if (const Constant *C = dyn_cast<Constant>(V))
58 return C->isNullValue();
63 /// m_Zero() - Match an arbitrary zero/null constant.
64 inline zero_ty m_Zero() { return zero_ty(); }
67 template<typename Class>
70 bind_ty(Class *&V) : VR(V) {}
72 template<typename ITy>
74 if (Class *CV = dyn_cast<Class>(V)) {
82 /// m_Value - Match a value, capturing it if we match.
83 inline bind_ty<Value> m_Value(Value *&V) { return V; }
85 /// m_ConstantInt - Match a ConstantInt, capturing the value if we match.
86 inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
88 //===----------------------------------------------------------------------===//
89 // Matchers for specific binary operators.
92 template<typename LHS_t, typename RHS_t,
93 unsigned Opcode, typename ConcreteTy = BinaryOperator>
94 struct BinaryOp_match {
98 BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
100 template<typename OpTy>
101 bool match(OpTy *V) {
102 if (V->getValueID() == Value::InstructionVal + Opcode) {
103 ConcreteTy *I = cast<ConcreteTy>(V);
104 return I->getOpcode() == Opcode && L.match(I->getOperand(0)) &&
105 R.match(I->getOperand(1));
107 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
108 return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
109 R.match(CE->getOperand(1));
114 template<typename LHS, typename RHS>
115 inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L,
117 return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);
120 template<typename LHS, typename RHS>
121 inline BinaryOp_match<LHS, RHS, Instruction::Sub> m_Sub(const LHS &L,
123 return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R);
126 template<typename LHS, typename RHS>
127 inline BinaryOp_match<LHS, RHS, Instruction::Mul> m_Mul(const LHS &L,
129 return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R);
132 template<typename LHS, typename RHS>
133 inline BinaryOp_match<LHS, RHS, Instruction::UDiv> m_UDiv(const LHS &L,
135 return BinaryOp_match<LHS, RHS, Instruction::UDiv>(L, R);
138 template<typename LHS, typename RHS>
139 inline BinaryOp_match<LHS, RHS, Instruction::SDiv> m_SDiv(const LHS &L,
141 return BinaryOp_match<LHS, RHS, Instruction::SDiv>(L, R);
144 template<typename LHS, typename RHS>
145 inline BinaryOp_match<LHS, RHS, Instruction::FDiv> m_FDiv(const LHS &L,
147 return BinaryOp_match<LHS, RHS, Instruction::FDiv>(L, R);
150 template<typename LHS, typename RHS>
151 inline BinaryOp_match<LHS, RHS, Instruction::URem> m_URem(const LHS &L,
153 return BinaryOp_match<LHS, RHS, Instruction::URem>(L, R);
156 template<typename LHS, typename RHS>
157 inline BinaryOp_match<LHS, RHS, Instruction::SRem> m_SRem(const LHS &L,
159 return BinaryOp_match<LHS, RHS, Instruction::SRem>(L, R);
162 template<typename LHS, typename RHS>
163 inline BinaryOp_match<LHS, RHS, Instruction::FRem> m_FRem(const LHS &L,
165 return BinaryOp_match<LHS, RHS, Instruction::FRem>(L, R);
168 template<typename LHS, typename RHS>
169 inline BinaryOp_match<LHS, RHS, Instruction::And> m_And(const LHS &L,
171 return BinaryOp_match<LHS, RHS, Instruction::And>(L, R);
174 template<typename LHS, typename RHS>
175 inline BinaryOp_match<LHS, RHS, Instruction::Or> m_Or(const LHS &L,
177 return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R);
180 template<typename LHS, typename RHS>
181 inline BinaryOp_match<LHS, RHS, Instruction::Xor> m_Xor(const LHS &L,
183 return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R);
186 template<typename LHS, typename RHS>
187 inline BinaryOp_match<LHS, RHS, Instruction::Shl> m_Shl(const LHS &L,
189 return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R);
192 template<typename LHS, typename RHS>
193 inline BinaryOp_match<LHS, RHS, Instruction::LShr> m_LShr(const LHS &L,
195 return BinaryOp_match<LHS, RHS, Instruction::LShr>(L, R);
198 template<typename LHS, typename RHS>
199 inline BinaryOp_match<LHS, RHS, Instruction::AShr> m_AShr(const LHS &L,
201 return BinaryOp_match<LHS, RHS, Instruction::AShr>(L, R);
204 //===----------------------------------------------------------------------===//
205 // Matchers for either AShr or LShr .. for convenience
207 template<typename LHS_t, typename RHS_t, typename ConcreteTy = BinaryOperator>
212 Shr_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
214 template<typename OpTy>
215 bool match(OpTy *V) {
216 if (V->getValueID() == Value::InstructionVal + Instruction::LShr ||
217 V->getValueID() == Value::InstructionVal + Instruction::AShr) {
218 ConcreteTy *I = cast<ConcreteTy>(V);
219 return (I->getOpcode() == Instruction::AShr ||
220 I->getOpcode() == Instruction::LShr) &&
221 L.match(I->getOperand(0)) &&
222 R.match(I->getOperand(1));
224 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
225 return (CE->getOpcode() == Instruction::LShr ||
226 CE->getOpcode() == Instruction::AShr) &&
227 L.match(CE->getOperand(0)) &&
228 R.match(CE->getOperand(1));
233 template<typename LHS, typename RHS>
234 inline Shr_match<LHS, RHS> m_Shr(const LHS &L, const RHS &R) {
235 return Shr_match<LHS, RHS>(L, R);
238 //===----------------------------------------------------------------------===//
239 // Matchers for binary classes
242 template<typename LHS_t, typename RHS_t, typename Class, typename OpcType>
243 struct BinaryOpClass_match {
248 BinaryOpClass_match(OpcType &Op, const LHS_t &LHS,
250 : Opcode(&Op), L(LHS), R(RHS) {}
251 BinaryOpClass_match(const LHS_t &LHS, const RHS_t &RHS)
252 : Opcode(0), L(LHS), R(RHS) {}
254 template<typename OpTy>
255 bool match(OpTy *V) {
256 if (Class *I = dyn_cast<Class>(V))
257 if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) {
259 *Opcode = I->getOpcode();
262 #if 0 // Doesn't handle constantexprs yet!
263 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
264 return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
265 R.match(CE->getOperand(1));
271 template<typename LHS, typename RHS>
272 inline BinaryOpClass_match<LHS, RHS, BinaryOperator, Instruction::BinaryOps>
273 m_Shift(Instruction::BinaryOps &Op, const LHS &L, const RHS &R) {
274 return BinaryOpClass_match<LHS, RHS,
275 BinaryOperator, Instruction::BinaryOps>(Op, L, R);
278 template<typename LHS, typename RHS>
279 inline BinaryOpClass_match<LHS, RHS, BinaryOperator, Instruction::BinaryOps>
280 m_Shift(const LHS &L, const RHS &R) {
281 return BinaryOpClass_match<LHS, RHS,
282 BinaryOperator, Instruction::BinaryOps>(L, R);
285 //===----------------------------------------------------------------------===//
286 // Matchers for CmpInst classes
289 template<typename LHS_t, typename RHS_t, typename Class, typename PredicateTy>
290 struct CmpClass_match {
291 PredicateTy &Predicate;
295 CmpClass_match(PredicateTy &Pred, const LHS_t &LHS,
297 : Predicate(Pred), L(LHS), R(RHS) {}
299 template<typename OpTy>
300 bool match(OpTy *V) {
301 if (Class *I = dyn_cast<Class>(V))
302 if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) {
303 Predicate = I->getPredicate();
310 template<typename LHS, typename RHS>
311 inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>
312 m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
313 return CmpClass_match<LHS, RHS,
314 ICmpInst, ICmpInst::Predicate>(Pred, L, R);
317 template<typename LHS, typename RHS>
318 inline CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>
319 m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
320 return CmpClass_match<LHS, RHS,
321 FCmpInst, FCmpInst::Predicate>(Pred, L, R);
324 //===----------------------------------------------------------------------===//
325 // Matchers for CastInst classes
328 template<typename Op_t, typename Class>
329 struct CastClass_match {
332 CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {}
334 template<typename OpTy>
335 bool match(OpTy *V) {
336 if (Class *I = dyn_cast<Class>(V))
337 return Op.match(I->getOperand(0));
342 template<typename Class, typename OpTy>
343 inline CastClass_match<OpTy, Class> m_Cast(const OpTy &Op) {
344 return CastClass_match<OpTy, Class>(Op);
348 //===----------------------------------------------------------------------===//
349 // Matchers for unary operators
352 template<typename LHS_t>
356 not_match(const LHS_t &LHS) : L(LHS) {}
358 template<typename OpTy>
359 bool match(OpTy *V) {
360 if (Instruction *I = dyn_cast<Instruction>(V))
361 if (I->getOpcode() == Instruction::Xor)
362 return matchIfNot(I->getOperand(0), I->getOperand(1));
363 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
364 if (CE->getOpcode() == Instruction::Xor)
365 return matchIfNot(CE->getOperand(0), CE->getOperand(1));
366 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
367 return L.match(ConstantExpr::getNot(CI));
371 bool matchIfNot(Value *LHS, Value *RHS) {
372 if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
373 return CI->isAllOnesValue() && L.match(LHS);
374 if (ConstantInt *CI = dyn_cast<ConstantInt>(LHS))
375 return CI->isAllOnesValue() && L.match(RHS);
376 if (ConstantVector *CV = dyn_cast<ConstantVector>(RHS))
377 return CV->isAllOnesValue() && L.match(LHS);
378 if (ConstantVector *CV = dyn_cast<ConstantVector>(LHS))
379 return CV->isAllOnesValue() && L.match(RHS);
384 template<typename LHS>
385 inline not_match<LHS> m_Not(const LHS &L) { return L; }
388 template<typename LHS_t>
392 neg_match(const LHS_t &LHS) : L(LHS) {}
394 template<typename OpTy>
395 bool match(OpTy *V) {
396 if (Instruction *I = dyn_cast<Instruction>(V))
397 if (I->getOpcode() == Instruction::Sub)
398 return matchIfNeg(I->getOperand(0), I->getOperand(1));
399 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
400 if (CE->getOpcode() == Instruction::Sub)
401 return matchIfNeg(CE->getOperand(0), CE->getOperand(1));
402 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
403 return L.match(ConstantExpr::getNeg(CI));
407 bool matchIfNeg(Value *LHS, Value *RHS) {
408 return LHS == ConstantExpr::getZeroValueForNegationExpr(LHS->getType()) &&
413 template<typename LHS>
414 inline neg_match<LHS> m_Neg(const LHS &L) { return L; }
417 //===----------------------------------------------------------------------===//
418 // Matchers for control flow
421 template<typename Cond_t>
425 brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f)
426 : Cond(C), T(t), F(f) {
429 template<typename OpTy>
430 bool match(OpTy *V) {
431 if (BranchInst *BI = dyn_cast<BranchInst>(V))
432 if (BI->isConditional()) {
433 if (Cond.match(BI->getCondition())) {
434 T = BI->getSuccessor(0);
435 F = BI->getSuccessor(1);
443 template<typename Cond_t>
444 inline brc_match<Cond_t> m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F){
445 return brc_match<Cond_t>(C, T, F);
449 }} // end llvm::match