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,
75 unsigned Opcode, typename ConcreteTy = BinaryOperator>
76 struct BinaryOp_match {
80 BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
82 template<typename OpTy>
84 if (V->getValueType() == Value::InstructionVal + Opcode) {
85 ConcreteTy *I = cast<ConcreteTy>(V);
86 return I->getOpcode() == Opcode && L.match(I->getOperand(0)) &&
87 R.match(I->getOperand(1));
89 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
90 return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
91 R.match(CE->getOperand(1));
96 template<typename LHS, typename RHS>
97 inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L,
99 return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);
102 template<typename LHS, typename RHS>
103 inline BinaryOp_match<LHS, RHS, Instruction::Sub> m_Sub(const LHS &L,
105 return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R);
108 template<typename LHS, typename RHS>
109 inline BinaryOp_match<LHS, RHS, Instruction::Mul> m_Mul(const LHS &L,
111 return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R);
114 template<typename LHS, typename RHS>
115 inline BinaryOp_match<LHS, RHS, Instruction::Div> m_Div(const LHS &L,
117 return BinaryOp_match<LHS, RHS, Instruction::Div>(L, R);
120 template<typename LHS, typename RHS>
121 inline BinaryOp_match<LHS, RHS, Instruction::Rem> m_Rem(const LHS &L,
123 return BinaryOp_match<LHS, RHS, Instruction::Rem>(L, R);
126 template<typename LHS, typename RHS>
127 inline BinaryOp_match<LHS, RHS, Instruction::And> m_And(const LHS &L,
129 return BinaryOp_match<LHS, RHS, Instruction::And>(L, R);
132 template<typename LHS, typename RHS>
133 inline BinaryOp_match<LHS, RHS, Instruction::Or> m_Or(const LHS &L,
135 return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R);
138 template<typename LHS, typename RHS>
139 inline BinaryOp_match<LHS, RHS, Instruction::Xor> m_Xor(const LHS &L,
141 return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R);
144 template<typename LHS, typename RHS>
145 inline BinaryOp_match<LHS, RHS, Instruction::Shl,
146 ShiftInst> m_Shl(const LHS &L, const RHS &R) {
147 return BinaryOp_match<LHS, RHS, Instruction::Shl, ShiftInst>(L, R);
150 template<typename LHS, typename RHS>
151 inline BinaryOp_match<LHS, RHS, Instruction::Shr,
152 ShiftInst> m_Shr(const LHS &L, const RHS &R) {
153 return BinaryOp_match<LHS, RHS, Instruction::Shr, ShiftInst>(L, R);
156 //===----------------------------------------------------------------------===//
157 // Matchers for binary classes
160 template<typename LHS_t, typename RHS_t, typename Class, typename OpcType>
161 struct BinaryOpClass_match {
166 BinaryOpClass_match(OpcType &Op, const LHS_t &LHS,
168 : Opcode(Op), L(LHS), R(RHS) {}
170 template<typename OpTy>
171 bool match(OpTy *V) {
172 if (Class *I = dyn_cast<Class>(V))
173 if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) {
174 Opcode = I->getOpcode();
177 #if 0 // Doesn't handle constantexprs yet!
178 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
179 return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
180 R.match(CE->getOperand(1));
186 template<typename LHS, typename RHS>
187 inline BinaryOpClass_match<LHS, RHS, SetCondInst, Instruction::BinaryOps>
188 m_SetCond(Instruction::BinaryOps &Op, const LHS &L, const RHS &R) {
189 return BinaryOpClass_match<LHS, RHS,
190 SetCondInst, Instruction::BinaryOps>(Op, L, R);
193 template<typename LHS, typename RHS>
194 inline BinaryOpClass_match<LHS, RHS, ShiftInst, Instruction::OtherOps>
195 m_Shift(Instruction::OtherOps &Op, const LHS &L, const RHS &R) {
196 return BinaryOpClass_match<LHS, RHS,
197 ShiftInst, Instruction::OtherOps>(Op, L, R);
200 template<typename LHS, typename RHS>
201 inline BinaryOpClass_match<LHS, RHS, ShiftInst, Instruction::OtherOps>
202 m_Shift(const LHS &L, const RHS &R) {
203 Instruction::OtherOps Op;
204 return BinaryOpClass_match<LHS, RHS,
205 ShiftInst, Instruction::OtherOps>(Op, L, R);
208 //===----------------------------------------------------------------------===//
209 // Matchers for unary operators
212 template<typename LHS_t>
216 neg_match(const LHS_t &LHS) : L(LHS) {}
218 template<typename OpTy>
219 bool match(OpTy *V) {
220 if (Instruction *I = dyn_cast<Instruction>(V))
221 if (I->getOpcode() == Instruction::Sub)
222 return matchIfNeg(I->getOperand(0), I->getOperand(1));
223 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
224 if (CE->getOpcode() == Instruction::Sub)
225 return matchIfNeg(CE->getOperand(0), CE->getOperand(1));
226 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
227 return L.match(ConstantExpr::getNeg(CI));
231 bool matchIfNeg(Value *LHS, Value *RHS) {
232 if (!LHS->getType()->isFloatingPoint())
233 return LHS == Constant::getNullValue(LHS->getType()) && L.match(RHS);
235 return LHS == ConstantFP::get(LHS->getType(), -0.0) && L.match(RHS);
239 template<typename LHS>
240 inline neg_match<LHS> m_Neg(const LHS &L) { return L; }
243 template<typename LHS_t>
247 not_match(const LHS_t &LHS) : L(LHS) {}
249 template<typename OpTy>
250 bool match(OpTy *V) {
251 if (Instruction *I = dyn_cast<Instruction>(V))
252 if (I->getOpcode() == Instruction::Xor)
253 return matchIfNot(I->getOperand(0), I->getOperand(1));
254 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
255 if (CE->getOpcode() == Instruction::Xor)
256 return matchIfNot(CE->getOperand(0), CE->getOperand(1));
257 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
258 return L.match(ConstantExpr::getNot(CI));
262 bool matchIfNot(Value *LHS, Value *RHS) {
263 if (ConstantIntegral *CI = dyn_cast<ConstantIntegral>(RHS))
264 return CI->isAllOnesValue() && L.match(LHS);
265 else if (ConstantIntegral *CI = dyn_cast<ConstantIntegral>(LHS))
266 return CI->isAllOnesValue() && L.match(RHS);
271 template<typename LHS>
272 inline not_match<LHS> m_Not(const LHS &L) { return L; }
275 template<typename Op_t>
280 cast_match(const Op_t &op, const Type **destTy) : Op(op), DestTy(destTy) {}
282 template<typename OpTy>
283 bool match(OpTy *V) {
284 if (CastInst *I = dyn_cast<CastInst>(V)) {
285 if (DestTy) *DestTy = I->getType();
286 return Op.match(I->getOperand(0));
287 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
288 if (CE->getOpcode() == Instruction::Cast) {
289 if (DestTy) *DestTy = I->getType();
290 return Op.match(CE->getOperand(0));
297 template<typename Op_t>
298 inline cast_match<Op_t> m_Cast(const Op_t &Op, const Type *&Ty) {
299 return cast_match<Op_t>(Op, &Ty);
301 template<typename Op_t>
302 inline cast_match<Op_t> m_Cast(const Op_t &Op) {
303 return cast_match<Op_t>(Op, 0);
307 //===----------------------------------------------------------------------===//
308 // Matchers for control flow
311 template<typename Cond_t>
315 brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f)
316 : Cond(C), T(t), F(f) {
319 template<typename OpTy>
320 bool match(OpTy *V) {
321 if (BranchInst *BI = dyn_cast<BranchInst>(V))
322 if (BI->isConditional()) {
323 if (Cond.match(BI->getCondition())) {
324 T = BI->getSuccessor(0);
325 F = BI->getSuccessor(1);
333 template<typename Cond_t>
334 inline brc_match<Cond_t> m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F){
335 return brc_match<Cond_t>(C, T, F);
339 }} // end llvm::match