1 //===-- llvm/Support/PatternMatch.h - Match on the LLVM IR ------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source 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 is allows to you
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 inline leaf_ty<Value> m_Value() { return leaf_ty<Value>(); }
50 inline leaf_ty<ConstantInt> m_ConstantInt() { return leaf_ty<ConstantInt>(); }
52 template<typename Class>
55 bind_ty(Class *&V) : VR(V) {}
57 template<typename ITy>
59 if (Class *CV = dyn_cast<Class>(V)) {
67 inline bind_ty<Value> m_Value(Value *&V) { return V; }
68 inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
70 //===----------------------------------------------------------------------===//
71 // Matchers for specific binary operators
74 template<typename LHS_t, typename RHS_t, unsigned Opcode>
75 struct BinaryOp_match {
79 BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
81 template<typename OpTy>
83 if (Instruction *I = dyn_cast<Instruction>(V))
84 return I->getOpcode() == Opcode && L.match(I->getOperand(0)) &&
85 R.match(I->getOperand(1));
86 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
87 return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
88 R.match(CE->getOperand(1));
93 template<typename LHS, typename RHS>
94 inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L,
96 return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);
99 template<typename LHS, typename RHS>
100 inline BinaryOp_match<LHS, RHS, Instruction::Sub> m_Sub(const LHS &L,
102 return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R);
105 template<typename LHS, typename RHS>
106 inline BinaryOp_match<LHS, RHS, Instruction::Mul> m_Mul(const LHS &L,
108 return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R);
111 template<typename LHS, typename RHS>
112 inline BinaryOp_match<LHS, RHS, Instruction::Div> m_Div(const LHS &L,
114 return BinaryOp_match<LHS, RHS, Instruction::Div>(L, R);
117 template<typename LHS, typename RHS>
118 inline BinaryOp_match<LHS, RHS, Instruction::Rem> m_Rem(const LHS &L,
120 return BinaryOp_match<LHS, RHS, Instruction::Rem>(L, R);
123 template<typename LHS, typename RHS>
124 inline BinaryOp_match<LHS, RHS, Instruction::And> m_And(const LHS &L,
126 return BinaryOp_match<LHS, RHS, Instruction::And>(L, R);
129 template<typename LHS, typename RHS>
130 inline BinaryOp_match<LHS, RHS, Instruction::Rem> m_Or(const LHS &L,
132 return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R);
135 template<typename LHS, typename RHS>
136 inline BinaryOp_match<LHS, RHS, Instruction::Xor> m_Xor(const LHS &L,
138 return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R);
141 template<typename LHS, typename RHS>
142 inline BinaryOp_match<LHS, RHS, Instruction::Shl> m_Shl(const LHS &L,
144 return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R);
147 template<typename LHS, typename RHS>
148 inline BinaryOp_match<LHS, RHS, Instruction::Shr> m_Shr(const LHS &L,
150 return BinaryOp_match<LHS, RHS, Instruction::Shr>(L, R);
153 //===----------------------------------------------------------------------===//
154 // Matchers for binary classes
157 template<typename LHS_t, typename RHS_t, typename Class>
158 struct BinaryOpClass_match {
159 Instruction::BinaryOps &Opcode;
163 BinaryOpClass_match(Instruction::BinaryOps &Op, const LHS_t &LHS,
165 : Opcode(Op), L(LHS), R(RHS) {}
167 template<typename OpTy>
168 bool match(OpTy *V) {
169 if (Class *I = dyn_cast<Class>(V))
170 if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) {
171 Opcode = I->getOpcode();
174 #if 0 // Doesn't handle constantexprs yet!
175 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
176 return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
177 R.match(CE->getOperand(1));
183 template<typename LHS, typename RHS>
184 inline BinaryOpClass_match<LHS, RHS, SetCondInst>
185 m_SetCond(Instruction::BinaryOps &Op, const LHS &L, const RHS &R) {
186 return BinaryOpClass_match<LHS, RHS, SetCondInst>(Op, L, R);
190 //===----------------------------------------------------------------------===//
191 // Matchers for unary operators
194 template<typename LHS_t>
198 neg_match(const LHS_t &LHS) : L(LHS) {}
200 template<typename OpTy>
201 bool match(OpTy *V) {
202 if (Instruction *I = dyn_cast<Instruction>(V))
203 if (I->getOpcode() == Instruction::Sub)
204 return matchIfNeg(I->getOperand(0), I->getOperand(1));
205 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
206 if (CE->getOpcode() == Instruction::Sub)
207 return matchIfNeg(CE->getOperand(0), CE->getOperand(1));
208 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
209 return L.match(ConstantExpr::getNeg(CI));
213 bool matchIfNeg(Value *LHS, Value *RHS) {
214 if (!LHS->getType()->isFloatingPoint())
215 return LHS == Constant::getNullValue(LHS->getType()) && L.match(RHS);
217 return LHS == ConstantFP::get(LHS->getType(), -0.0) && L.match(RHS);
221 template<typename LHS>
222 inline neg_match<LHS> m_Neg(const LHS &L) { return L; }
225 template<typename LHS_t>
229 not_match(const LHS_t &LHS) : L(LHS) {}
231 template<typename OpTy>
232 bool match(OpTy *V) {
233 if (Instruction *I = dyn_cast<Instruction>(V))
234 if (I->getOpcode() == Instruction::Xor)
235 return matchIfNot(I->getOperand(0), I->getOperand(1));
236 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
237 if (CE->getOpcode() == Instruction::Xor)
238 return matchIfNot(CE->getOperand(0), CE->getOperand(1));
239 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
240 return L.match(ConstantExpr::getNot(CI));
244 bool matchIfNot(Value *LHS, Value *RHS) {
245 if (ConstantIntegral *CI = dyn_cast<ConstantIntegral>(RHS))
246 return CI->isAllOnesValue() && L.match(LHS);
247 else if (ConstantIntegral *CI = dyn_cast<ConstantIntegral>(LHS))
248 return CI->isAllOnesValue() && L.match(RHS);
253 template<typename LHS>
254 inline not_match<LHS> m_Not(const LHS &L) { return L; }
256 //===----------------------------------------------------------------------===//
257 // Matchers for control flow
260 template<typename Cond_t>
264 brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f)
265 : Cond(C), T(t), F(f) {
268 template<typename OpTy>
269 bool match(OpTy *V) {
270 if (BranchInst *BI = dyn_cast<BranchInst>(V))
271 if (BI->isConditional()) {
272 if (Cond.match(BI->getCondition())) {
273 T = BI->getSuccessor(0);
274 F = BI->getSuccessor(1);
282 template<typename Cond_t>
283 inline brc_match<Cond_t> m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F){
284 return brc_match<Cond_t>(C, T, F);
288 }} // end llvm::match