From 524d8f17228b6e1dbb4735cd48e6fab50c46459f Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Fri, 30 Jul 2004 07:45:00 +0000 Subject: Check in some useful helper routines for doing ML-style pattern matching on the LLVM IR. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15341 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/PatternMatch.h | 280 ++++++++++++++++++++++++++++++++++++ 1 file changed, 280 insertions(+) create mode 100644 include/llvm/Support/PatternMatch.h (limited to 'include/llvm/Support/PatternMatch.h') diff --git a/include/llvm/Support/PatternMatch.h b/include/llvm/Support/PatternMatch.h new file mode 100644 index 0000000000..37657bdb33 --- /dev/null +++ b/include/llvm/Support/PatternMatch.h @@ -0,0 +1,280 @@ +//===-- llvm/Support/PatternMatch.h - Match on the LLVM IR ------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by the LLVM research group and is distributed under +// the University of Illinois Open Source License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file provides a simple and efficient mechanism for performing general +// tree-based pattern matches on the LLVM IR. The power of these routines is +// that it allows you to write concise patterns that are expressive and easy to +// understand. The other major advantage of this is that is allows to you +// trivially capture/bind elements in the pattern to variables. For example, +// you can do something like this: +// +// Value *Exp = ... +// Value *X, *Y; ConstantInt *C1, *C2; // (X & C1) | (Y & C2) +// if (match(Exp, m_Or(m_And(m_Value(X), m_ConstantInt(C1)), +// m_And(m_Value(Y), m_ConstantInt(C2))))) { +// ... Pattern is matched and variables are bound ... +// } +// +// This is primarily useful to things like the instruction combiner, but can +// also be useful for static analysis tools or code generators. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_SUPPORT_PATTERNMATCH_H +#define LLVM_SUPPORT_PATTERNMATCH_H + +#include "llvm/Constants.h" +#include "llvm/Instructions.h" + +namespace llvm { +namespace PatternMatch { + +template +bool match(Val *V, Pattern P) { + return P.match(V); +} + +template +struct leaf_ty { + template + bool match(ITy *V) { return isa(V); } +}; + +inline leaf_ty m_Value() { return leaf_ty(); } +inline leaf_ty m_ConstantInt() { return leaf_ty(); } + +template +struct bind_ty { + Class *&VR; + bind_ty(Class*& V) :VR(V) {} + + template + bool match(ITy *V) { + if (Class *CV = dyn_cast(V)) { + VR = CV; + return true; + } + return false; + } +}; + +inline bind_ty m_Value(Value *&V) { return V; } +inline bind_ty m_ConstantInt(ConstantInt *&CI) { return CI; } + +//===----------------------------------------------------------------------===// +// Matchers for specific binary operators +// + +template +struct BinaryOp_match { + LHS_t L; + RHS_t R; + + BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {} + + template + bool match(OpTy *V) { + if (Instruction *I = dyn_cast(V)) + return I->getOpcode() == Opcode && L.match(I->getOperand(0)) && + R.match(I->getOperand(1)); + if (ConstantExpr *CE = dyn_cast(V)) + return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) && + R.match(CE->getOperand(1)); + return false; + } +}; + +template +inline BinaryOp_match m_Add(const LHS &L, + const RHS &R) { + return BinaryOp_match(L, R); +} + +template +inline BinaryOp_match m_Sub(const LHS &L, + const RHS &R) { + return BinaryOp_match(L, R); +} + +template +inline BinaryOp_match m_Mul(const LHS &L, + const RHS &R) { + return BinaryOp_match(L, R); +} + +template +inline BinaryOp_match m_Div(const LHS &L, + const RHS &R) { + return BinaryOp_match(L, R); +} + +template +inline BinaryOp_match m_Rem(const LHS &L, + const RHS &R) { + return BinaryOp_match(L, R); +} + +template +inline BinaryOp_match m_And(const LHS &L, + const RHS &R) { + return BinaryOp_match(L, R); +} + +template +inline BinaryOp_match m_Or(const LHS &L, + const RHS &R) { + return BinaryOp_match(L, R); +} + +template +inline BinaryOp_match m_Xor(const LHS &L, + const RHS &R) { + return BinaryOp_match(L, R); +} + +//===----------------------------------------------------------------------===// +// Matchers for binary classes +// + +template +struct BinaryOpClass_match { + Instruction::BinaryOps &Opcode; + LHS_t L; + RHS_t R; + + BinaryOpClass_match(Instruction::BinaryOps &Op, const LHS_t &LHS, + const RHS_t &RHS) + : Opcode(Op), L(LHS), R(RHS) {} + + template + bool match(OpTy *V) { + if (Class *I = dyn_cast(V)) + if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) { + Opcode = I->getOpcode(); + return true; + } +#if 0 // Doesn't handle constantexprs yet! + if (ConstantExpr *CE = dyn_cast(V)) + return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) && + R.match(CE->getOperand(1)); +#endif + return false; + } +}; + +template +inline BinaryOpClass_match +m_SetCond(Instruction::BinaryOps &Op, const LHS &L, const RHS &R) { + return BinaryOpClass_match(Op, L, R); +} + + +//===----------------------------------------------------------------------===// +// Matchers for unary operators +// + +template +struct neg_match { + LHS_t L; + + neg_match(const LHS_t &LHS) : L(LHS) {} + + template + bool match(OpTy *V) { + if (Instruction *I = dyn_cast(V)) + if (I->getOpcode() == Instruction::Sub) + return matchIfNeg(I->getOperand(0), I->getOperand(1)); + if (ConstantExpr *CE = dyn_cast(V)) + if (CE->getOpcode() == Instruction::Sub) + return matchIfNeg(I->getOperand(0), I->getOperand(1)); + if (ConstantInt *CI = dyn_cast(V)) + return L.match(ConstantExpr::getNeg(CI)); + return false; + } +private: + bool matchIfNeg(Value *LHS, Value *RHS) { + if (!LHS->getType()->isFloatingPoint()) + return LHS == Constant::getNullValue(LHS->getType()) && L.match(RHS); + else + return LHS == ConstantFP::get(Bop->getType(), -0.0) && L.match(RHS); + } +}; + +template +inline neg_match m_Neg(const LHS &L) { return L; } + + +template +struct not_match { + LHS_t L; + + not_match(const LHS_t &LHS) : L(LHS) {} + + template + bool match(OpTy *V) { + if (Instruction *I = dyn_cast(V)) + if (I->getOpcode() == Instruction::Xor) + return matchIfNot(I->getOperand(0), I->getOperand(1)); + if (ConstantExpr *CE = dyn_cast(V)) + if (CE->getOpcode() == Instruction::Xor) + return matchIfNot(CE->getOperand(0), CE->getOperand(1)); + if (ConstantInt *CI = dyn_cast(V)) + return L.match(ConstantExpr::getNot(CI)); + return false; + } +private: + bool matchIfNot(Value *LHS, Value *RHS) { + if (ConstantIntegral *CI = dyn_cast(RHS)) + return CI->isAllOnesValue() && L.match(LHS); + else if (ConstantIntegral *CI = dyn_cast(LHS)) + return CI->isAllOnesValue() && L.match(RHS); + return false; + } +}; + +template +inline not_match m_Not(const LHS &L) { return L; } + +//===----------------------------------------------------------------------===// +// Matchers for control flow +// + +template +struct brc_match { + Cond_t Cond; + BasicBlock *&T, *&F; + brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f) + : Cond(C), T(t), F(f) { + } + + template + bool match(OpTy *V) { + if (BranchInst *BI = dyn_cast(V)) + if (BI->isConditional()) { + if (Cond.match(BI->getCondition())) { + T = BI->getSuccessor(0); + F = BI->getSuccessor(1); + return true; + } + } + return false; + } +}; + +template +inline brc_match m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F){ + return brc_match(C, T, F); +} + + +}} // end llvm::match + + +#endif + -- cgit v1.2.3