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::UDiv> m_UDiv(const LHS &L,
117 return BinaryOp_match<LHS, RHS, Instruction::UDiv>(L, R);
120 template<typename LHS, typename RHS>
121 inline BinaryOp_match<LHS, RHS, Instruction::SDiv> m_SDiv(const LHS &L,
123 return BinaryOp_match<LHS, RHS, Instruction::SDiv>(L, R);
126 template<typename LHS, typename RHS>
127 inline BinaryOp_match<LHS, RHS, Instruction::FDiv> m_FDiv(const LHS &L,
129 return BinaryOp_match<LHS, RHS, Instruction::FDiv>(L, R);
132 template<typename LHS, typename RHS>
133 inline BinaryOp_match<LHS, RHS, Instruction::URem> m_URem(const LHS &L,
135 return BinaryOp_match<LHS, RHS, Instruction::URem>(L, R);
138 template<typename LHS, typename RHS>
139 inline BinaryOp_match<LHS, RHS, Instruction::SRem> m_SRem(const LHS &L,
141 return BinaryOp_match<LHS, RHS, Instruction::SRem>(L, R);
144 template<typename LHS, typename RHS>
145 inline BinaryOp_match<LHS, RHS, Instruction::FRem> m_FRem(const LHS &L,
147 return BinaryOp_match<LHS, RHS, Instruction::FRem>(L, R);
150 template<typename LHS, typename RHS>
151 inline BinaryOp_match<LHS, RHS, Instruction::And> m_And(const LHS &L,
153 return BinaryOp_match<LHS, RHS, Instruction::And>(L, R);
156 template<typename LHS, typename RHS>
157 inline BinaryOp_match<LHS, RHS, Instruction::Or> m_Or(const LHS &L,
159 return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R);
162 template<typename LHS, typename RHS>
163 inline BinaryOp_match<LHS, RHS, Instruction::Xor> m_Xor(const LHS &L,
165 return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R);
168 template<typename LHS, typename RHS>
169 inline BinaryOp_match<LHS, RHS, Instruction::Shl,
170 ShiftInst> m_Shl(const LHS &L, const RHS &R) {
171 return BinaryOp_match<LHS, RHS, Instruction::Shl, ShiftInst>(L, R);
174 template<typename LHS, typename RHS>
175 inline BinaryOp_match<LHS, RHS, Instruction::Shr,
176 ShiftInst> m_Shr(const LHS &L, const RHS &R) {
177 return BinaryOp_match<LHS, RHS, Instruction::Shr, ShiftInst>(L, R);
180 //===----------------------------------------------------------------------===//
181 // Matchers for binary classes
184 template<typename LHS_t, typename RHS_t, typename Class, typename OpcType>
185 struct BinaryOpClass_match {
190 BinaryOpClass_match(OpcType &Op, const LHS_t &LHS,
192 : Opcode(Op), L(LHS), R(RHS) {}
194 template<typename OpTy>
195 bool match(OpTy *V) {
196 if (Class *I = dyn_cast<Class>(V))
197 if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) {
198 Opcode = I->getOpcode();
201 #if 0 // Doesn't handle constantexprs yet!
202 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
203 return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
204 R.match(CE->getOperand(1));
210 template<typename LHS, typename RHS>
211 inline BinaryOpClass_match<LHS, RHS, SetCondInst, Instruction::BinaryOps>
212 m_SetCond(Instruction::BinaryOps &Op, const LHS &L, const RHS &R) {
213 return BinaryOpClass_match<LHS, RHS,
214 SetCondInst, Instruction::BinaryOps>(Op, L, R);
217 template<typename LHS, typename RHS>
218 inline BinaryOpClass_match<LHS, RHS, ShiftInst, Instruction::OtherOps>
219 m_Shift(Instruction::OtherOps &Op, const LHS &L, const RHS &R) {
220 return BinaryOpClass_match<LHS, RHS,
221 ShiftInst, Instruction::OtherOps>(Op, L, R);
224 template<typename LHS, typename RHS>
225 inline BinaryOpClass_match<LHS, RHS, ShiftInst, Instruction::OtherOps>
226 m_Shift(const LHS &L, const RHS &R) {
227 Instruction::OtherOps Op;
228 return BinaryOpClass_match<LHS, RHS,
229 ShiftInst, Instruction::OtherOps>(Op, L, R);
232 //===----------------------------------------------------------------------===//
233 // Matchers for unary operators
236 template<typename LHS_t>
240 neg_match(const LHS_t &LHS) : L(LHS) {}
242 template<typename OpTy>
243 bool match(OpTy *V) {
244 if (Instruction *I = dyn_cast<Instruction>(V))
245 if (I->getOpcode() == Instruction::Sub)
246 return matchIfNeg(I->getOperand(0), I->getOperand(1));
247 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
248 if (CE->getOpcode() == Instruction::Sub)
249 return matchIfNeg(CE->getOperand(0), CE->getOperand(1));
250 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
251 return L.match(ConstantExpr::getNeg(CI));
255 bool matchIfNeg(Value *LHS, Value *RHS) {
256 if (!LHS->getType()->isFloatingPoint())
257 return LHS == Constant::getNullValue(LHS->getType()) && L.match(RHS);
259 return LHS == ConstantFP::get(LHS->getType(), -0.0) && L.match(RHS);
263 template<typename LHS>
264 inline neg_match<LHS> m_Neg(const LHS &L) { return L; }
267 template<typename LHS_t>
271 not_match(const LHS_t &LHS) : L(LHS) {}
273 template<typename OpTy>
274 bool match(OpTy *V) {
275 if (Instruction *I = dyn_cast<Instruction>(V))
276 if (I->getOpcode() == Instruction::Xor)
277 return matchIfNot(I->getOperand(0), I->getOperand(1));
278 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
279 if (CE->getOpcode() == Instruction::Xor)
280 return matchIfNot(CE->getOperand(0), CE->getOperand(1));
281 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
282 return L.match(ConstantExpr::getNot(CI));
286 bool matchIfNot(Value *LHS, Value *RHS) {
287 if (ConstantIntegral *CI = dyn_cast<ConstantIntegral>(RHS))
288 return CI->isAllOnesValue() && L.match(LHS);
289 else if (ConstantIntegral *CI = dyn_cast<ConstantIntegral>(LHS))
290 return CI->isAllOnesValue() && L.match(RHS);
295 template<typename LHS>
296 inline not_match<LHS> m_Not(const LHS &L) { return L; }
299 template<typename Op_t>
304 cast_match(const Op_t &op, const Type **destTy) : Op(op), DestTy(destTy) {}
306 template<typename OpTy>
307 bool match(OpTy *V) {
308 if (CastInst *I = dyn_cast<CastInst>(V)) {
309 if (DestTy) *DestTy = I->getType();
310 return Op.match(I->getOperand(0));
311 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
312 if (CE->getOpcode() == Instruction::Cast) {
313 if (DestTy) *DestTy = I->getType();
314 return Op.match(CE->getOperand(0));
321 template<typename Op_t>
322 inline cast_match<Op_t> m_Cast(const Op_t &Op, const Type *&Ty) {
323 return cast_match<Op_t>(Op, &Ty);
325 template<typename Op_t>
326 inline cast_match<Op_t> m_Cast(const Op_t &Op) {
327 return cast_match<Op_t>(Op, 0);
331 //===----------------------------------------------------------------------===//
332 // Matchers for control flow
335 template<typename Cond_t>
339 brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f)
340 : Cond(C), T(t), F(f) {
343 template<typename OpTy>
344 bool match(OpTy *V) {
345 if (BranchInst *BI = dyn_cast<BranchInst>(V))
346 if (BI->isConditional()) {
347 if (Cond.match(BI->getCondition())) {
348 T = BI->getSuccessor(0);
349 F = BI->getSuccessor(1);
357 template<typename Cond_t>
358 inline brc_match<Cond_t> m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F){
359 return brc_match<Cond_t>(C, T, F);
363 }} // end llvm::match