Home | History | Annotate | Download | only in Support 
      1 //===-- llvm/Support/PatternMatch.h - Match on the LLVM IR ------*- C++ -*-===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     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:
     16 //
     17 //  Value *Exp = ...
     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 ...
     22 //  }
     23 //
     24 // This is primarily useful to things like the instruction combiner, but can
     25 // also be useful for static analysis tools or code generators.
     26 //
     27 //===----------------------------------------------------------------------===//
     28 
     29 #ifndef LLVM_SUPPORT_PATTERNMATCH_H
     30 #define LLVM_SUPPORT_PATTERNMATCH_H
     31 
     32 #include "llvm/Constants.h"
     33 #include "llvm/Instructions.h"
     34 
     35 namespace llvm {
     36 namespace PatternMatch {
     37 
     38 template<typename Val, typename Pattern>
     39 bool match(Val *V, const Pattern &P) {
     40   return const_cast<Pattern&>(P).match(V);
     41 }
     42 
     43 
     44 template<typename SubPattern_t>
     45 struct OneUse_match {
     46   SubPattern_t SubPattern;
     47 
     48   OneUse_match(const SubPattern_t &SP) : SubPattern(SP) {}
     49 
     50   template<typename OpTy>
     51   bool match(OpTy *V) {
     52     return V->hasOneUse() && SubPattern.match(V);
     53   }
     54 };
     55 
     56 template<typename T>
     57 inline OneUse_match<T> m_OneUse(const T &SubPattern) { return SubPattern; }
     58 
     59 
     60 template<typename Class>
     61 struct class_match {
     62   template<typename ITy>
     63   bool match(ITy *V) { return isa<Class>(V); }
     64 };
     65 
     66 /// m_Value() - Match an arbitrary value and ignore it.
     67 inline class_match<Value> m_Value() { return class_match<Value>(); }
     68 /// m_ConstantInt() - Match an arbitrary ConstantInt and ignore it.
     69 inline class_match<ConstantInt> m_ConstantInt() {
     70   return class_match<ConstantInt>();
     71 }
     72 /// m_Undef() - Match an arbitrary undef constant.
     73 inline class_match<UndefValue> m_Undef() { return class_match<UndefValue>(); }
     74 
     75 inline class_match<Constant> m_Constant() { return class_match<Constant>(); }
     76 
     77 struct match_zero {
     78   template<typename ITy>
     79   bool match(ITy *V) {
     80     if (const Constant *C = dyn_cast<Constant>(V))
     81       return C->isNullValue();
     82     return false;
     83   }
     84 };
     85 
     86 /// m_Zero() - Match an arbitrary zero/null constant.  This includes
     87 /// zero_initializer for vectors and ConstantPointerNull for pointers.
     88 inline match_zero m_Zero() { return match_zero(); }
     89 
     90 
     91 struct apint_match {
     92   const APInt *&Res;
     93   apint_match(const APInt *&R) : Res(R) {}
     94   template<typename ITy>
     95   bool match(ITy *V) {
     96     if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
     97       Res = &CI->getValue();
     98       return true;
     99     }
    100     if (ConstantVector *CV = dyn_cast<ConstantVector>(V))
    101       if (ConstantInt *CI =
    102           dyn_cast_or_null<ConstantInt>(CV->getSplatValue())) {
    103         Res = &CI->getValue();
    104         return true;
    105       }
    106     return false;
    107   }
    108 };
    109 
    110 /// m_APInt - Match a ConstantInt or splatted ConstantVector, binding the
    111 /// specified pointer to the contained APInt.
    112 inline apint_match m_APInt(const APInt *&Res) { return Res; }
    113 
    114 
    115 template<int64_t Val>
    116 struct constantint_match {
    117   template<typename ITy>
    118   bool match(ITy *V) {
    119     if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
    120       const APInt &CIV = CI->getValue();
    121       if (Val >= 0)
    122         return CIV == static_cast<uint64_t>(Val);
    123       // If Val is negative, and CI is shorter than it, truncate to the right
    124       // number of bits.  If it is larger, then we have to sign extend.  Just
    125       // compare their negated values.
    126       return -CIV == -Val;
    127     }
    128     return false;
    129   }
    130 };
    131 
    132 /// m_ConstantInt<int64_t> - Match a ConstantInt with a specific value.
    133 template<int64_t Val>
    134 inline constantint_match<Val> m_ConstantInt() {
    135   return constantint_match<Val>();
    136 }
    137 
    138 /// cst_pred_ty - This helper class is used to match scalar and vector constants
    139 /// that satisfy a specified predicate.
    140 template<typename Predicate>
    141 struct cst_pred_ty : public Predicate {
    142   template<typename ITy>
    143   bool match(ITy *V) {
    144     if (const ConstantInt *CI = dyn_cast<ConstantInt>(V))
    145       return this->isValue(CI->getValue());
    146     if (const ConstantVector *CV = dyn_cast<ConstantVector>(V))
    147       if (ConstantInt *CI = dyn_cast_or_null<ConstantInt>(CV->getSplatValue()))
    148         return this->isValue(CI->getValue());
    149     return false;
    150   }
    151 };
    152 
    153 /// api_pred_ty - This helper class is used to match scalar and vector constants
    154 /// that satisfy a specified predicate, and bind them to an APInt.
    155 template<typename Predicate>
    156 struct api_pred_ty : public Predicate {
    157   const APInt *&Res;
    158   api_pred_ty(const APInt *&R) : Res(R) {}
    159   template<typename ITy>
    160   bool match(ITy *V) {
    161     if (const ConstantInt *CI = dyn_cast<ConstantInt>(V))
    162       if (this->isValue(CI->getValue())) {
    163         Res = &CI->getValue();
    164         return true;
    165       }
    166     if (const ConstantVector *CV = dyn_cast<ConstantVector>(V))
    167       if (ConstantInt *CI = dyn_cast_or_null<ConstantInt>(CV->getSplatValue()))
    168         if (this->isValue(CI->getValue())) {
    169           Res = &CI->getValue();
    170           return true;
    171         }
    172     return false;
    173   }
    174 };
    175 
    176 
    177 struct is_one {
    178   bool isValue(const APInt &C) { return C == 1; }
    179 };
    180 
    181 /// m_One() - Match an integer 1 or a vector with all elements equal to 1.
    182 inline cst_pred_ty<is_one> m_One() { return cst_pred_ty<is_one>(); }
    183 inline api_pred_ty<is_one> m_One(const APInt *&V) { return V; }
    184 
    185 struct is_all_ones {
    186   bool isValue(const APInt &C) { return C.isAllOnesValue(); }
    187 };
    188 
    189 /// m_AllOnes() - Match an integer or vector with all bits set to true.
    190 inline cst_pred_ty<is_all_ones> m_AllOnes() {return cst_pred_ty<is_all_ones>();}
    191 inline api_pred_ty<is_all_ones> m_AllOnes(const APInt *&V) { return V; }
    192 
    193 struct is_sign_bit {
    194   bool isValue(const APInt &C) { return C.isSignBit(); }
    195 };
    196 
    197 /// m_SignBit() - Match an integer or vector with only the sign bit(s) set.
    198 inline cst_pred_ty<is_sign_bit> m_SignBit() {return cst_pred_ty<is_sign_bit>();}
    199 inline api_pred_ty<is_sign_bit> m_SignBit(const APInt *&V) { return V; }
    200 
    201 struct is_power2 {
    202   bool isValue(const APInt &C) { return C.isPowerOf2(); }
    203 };
    204 
    205 /// m_Power2() - Match an integer or vector power of 2.
    206 inline cst_pred_ty<is_power2> m_Power2() { return cst_pred_ty<is_power2>(); }
    207 inline api_pred_ty<is_power2> m_Power2(const APInt *&V) { return V; }
    208 
    209 template<typename Class>
    210 struct bind_ty {
    211   Class *&VR;
    212   bind_ty(Class *&V) : VR(V) {}
    213 
    214   template<typename ITy>
    215   bool match(ITy *V) {
    216     if (Class *CV = dyn_cast<Class>(V)) {
    217       VR = CV;
    218       return true;
    219     }
    220     return false;
    221   }
    222 };
    223 
    224 /// m_Value - Match a value, capturing it if we match.
    225 inline bind_ty<Value> m_Value(Value *&V) { return V; }
    226 
    227 /// m_ConstantInt - Match a ConstantInt, capturing the value if we match.
    228 inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
    229 
    230 /// m_Constant - Match a Constant, capturing the value if we match.
    231 inline bind_ty<Constant> m_Constant(Constant *&C) { return C; }
    232 
    233 /// specificval_ty - Match a specified Value*.
    234 struct specificval_ty {
    235   const Value *Val;
    236   specificval_ty(const Value *V) : Val(V) {}
    237 
    238   template<typename ITy>
    239   bool match(ITy *V) {
    240     return V == Val;
    241   }
    242 };
    243 
    244 /// m_Specific - Match if we have a specific specified value.
    245 inline specificval_ty m_Specific(const Value *V) { return V; }
    246 
    247 struct bind_const_intval_ty {
    248   uint64_t &VR;
    249   bind_const_intval_ty(uint64_t &V) : VR(V) {}
    250 
    251   template<typename ITy>
    252   bool match(ITy *V) {
    253     if (ConstantInt *CV = dyn_cast<ConstantInt>(V))
    254       if (CV->getBitWidth() <= 64) {
    255         VR = CV->getZExtValue();
    256         return true;
    257       }
    258     return false;
    259   }
    260 };
    261 
    262 /// m_ConstantInt - Match a ConstantInt and bind to its value.  This does not
    263 /// match ConstantInts wider than 64-bits.
    264 inline bind_const_intval_ty m_ConstantInt(uint64_t &V) { return V; }
    265 
    266 //===----------------------------------------------------------------------===//
    267 // Matchers for specific binary operators.
    268 //
    269 
    270 template<typename LHS_t, typename RHS_t, unsigned Opcode>
    271 struct BinaryOp_match {
    272   LHS_t L;
    273   RHS_t R;
    274 
    275   BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
    276 
    277   template<typename OpTy>
    278   bool match(OpTy *V) {
    279     if (V->getValueID() == Value::InstructionVal + Opcode) {
    280       BinaryOperator *I = cast<BinaryOperator>(V);
    281       return L.match(I->getOperand(0)) && R.match(I->getOperand(1));
    282     }
    283     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
    284       return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
    285              R.match(CE->getOperand(1));
    286     return false;
    287   }
    288 };
    289 
    290 template<typename LHS, typename RHS>
    291 inline BinaryOp_match<LHS, RHS, Instruction::Add>
    292 m_Add(const LHS &L, const RHS &R) {
    293   return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);
    294 }
    295 
    296 template<typename LHS, typename RHS>
    297 inline BinaryOp_match<LHS, RHS, Instruction::FAdd>
    298 m_FAdd(const LHS &L, const RHS &R) {
    299   return BinaryOp_match<LHS, RHS, Instruction::FAdd>(L, R);
    300 }
    301 
    302 template<typename LHS, typename RHS>
    303 inline BinaryOp_match<LHS, RHS, Instruction::Sub>
    304 m_Sub(const LHS &L, const RHS &R) {
    305   return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R);
    306 }
    307 
    308 template<typename LHS, typename RHS>
    309 inline BinaryOp_match<LHS, RHS, Instruction::FSub>
    310 m_FSub(const LHS &L, const RHS &R) {
    311   return BinaryOp_match<LHS, RHS, Instruction::FSub>(L, R);
    312 }
    313 
    314 template<typename LHS, typename RHS>
    315 inline BinaryOp_match<LHS, RHS, Instruction::Mul>
    316 m_Mul(const LHS &L, const RHS &R) {
    317   return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R);
    318 }
    319 
    320 template<typename LHS, typename RHS>
    321 inline BinaryOp_match<LHS, RHS, Instruction::FMul>
    322 m_FMul(const LHS &L, const RHS &R) {
    323   return BinaryOp_match<LHS, RHS, Instruction::FMul>(L, R);
    324 }
    325 
    326 template<typename LHS, typename RHS>
    327 inline BinaryOp_match<LHS, RHS, Instruction::UDiv>
    328 m_UDiv(const LHS &L, const RHS &R) {
    329   return BinaryOp_match<LHS, RHS, Instruction::UDiv>(L, R);
    330 }
    331 
    332 template<typename LHS, typename RHS>
    333 inline BinaryOp_match<LHS, RHS, Instruction::SDiv>
    334 m_SDiv(const LHS &L, const RHS &R) {
    335   return BinaryOp_match<LHS, RHS, Instruction::SDiv>(L, R);
    336 }
    337 
    338 template<typename LHS, typename RHS>
    339 inline BinaryOp_match<LHS, RHS, Instruction::FDiv>
    340 m_FDiv(const LHS &L, const RHS &R) {
    341   return BinaryOp_match<LHS, RHS, Instruction::FDiv>(L, R);
    342 }
    343 
    344 template<typename LHS, typename RHS>
    345 inline BinaryOp_match<LHS, RHS, Instruction::URem>
    346 m_URem(const LHS &L, const RHS &R) {
    347   return BinaryOp_match<LHS, RHS, Instruction::URem>(L, R);
    348 }
    349 
    350 template<typename LHS, typename RHS>
    351 inline BinaryOp_match<LHS, RHS, Instruction::SRem>
    352 m_SRem(const LHS &L, const RHS &R) {
    353   return BinaryOp_match<LHS, RHS, Instruction::SRem>(L, R);
    354 }
    355 
    356 template<typename LHS, typename RHS>
    357 inline BinaryOp_match<LHS, RHS, Instruction::FRem>
    358 m_FRem(const LHS &L, const RHS &R) {
    359   return BinaryOp_match<LHS, RHS, Instruction::FRem>(L, R);
    360 }
    361 
    362 template<typename LHS, typename RHS>
    363 inline BinaryOp_match<LHS, RHS, Instruction::And>
    364 m_And(const LHS &L, const RHS &R) {
    365   return BinaryOp_match<LHS, RHS, Instruction::And>(L, R);
    366 }
    367 
    368 template<typename LHS, typename RHS>
    369 inline BinaryOp_match<LHS, RHS, Instruction::Or>
    370 m_Or(const LHS &L, const RHS &R) {
    371   return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R);
    372 }
    373 
    374 template<typename LHS, typename RHS>
    375 inline BinaryOp_match<LHS, RHS, Instruction::Xor>
    376 m_Xor(const LHS &L, const RHS &R) {
    377   return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R);
    378 }
    379 
    380 template<typename LHS, typename RHS>
    381 inline BinaryOp_match<LHS, RHS, Instruction::Shl>
    382 m_Shl(const LHS &L, const RHS &R) {
    383   return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R);
    384 }
    385 
    386 template<typename LHS, typename RHS>
    387 inline BinaryOp_match<LHS, RHS, Instruction::LShr>
    388 m_LShr(const LHS &L, const RHS &R) {
    389   return BinaryOp_match<LHS, RHS, Instruction::LShr>(L, R);
    390 }
    391 
    392 template<typename LHS, typename RHS>
    393 inline BinaryOp_match<LHS, RHS, Instruction::AShr>
    394 m_AShr(const LHS &L, const RHS &R) {
    395   return BinaryOp_match<LHS, RHS, Instruction::AShr>(L, R);
    396 }
    397 
    398 //===----------------------------------------------------------------------===//
    399 // Class that matches two different binary ops.
    400 //
    401 template<typename LHS_t, typename RHS_t, unsigned Opc1, unsigned Opc2>
    402 struct BinOp2_match {
    403   LHS_t L;
    404   RHS_t R;
    405 
    406   BinOp2_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
    407 
    408   template<typename OpTy>
    409   bool match(OpTy *V) {
    410     if (V->getValueID() == Value::InstructionVal + Opc1 ||
    411         V->getValueID() == Value::InstructionVal + Opc2) {
    412       BinaryOperator *I = cast<BinaryOperator>(V);
    413       return L.match(I->getOperand(0)) && R.match(I->getOperand(1));
    414     }
    415     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
    416       return (CE->getOpcode() == Opc1 || CE->getOpcode() == Opc2) &&
    417              L.match(CE->getOperand(0)) && R.match(CE->getOperand(1));
    418     return false;
    419   }
    420 };
    421 
    422 /// m_Shr - Matches LShr or AShr.
    423 template<typename LHS, typename RHS>
    424 inline BinOp2_match<LHS, RHS, Instruction::LShr, Instruction::AShr>
    425 m_Shr(const LHS &L, const RHS &R) {
    426   return BinOp2_match<LHS, RHS, Instruction::LShr, Instruction::AShr>(L, R);
    427 }
    428 
    429 /// m_LogicalShift - Matches LShr or Shl.
    430 template<typename LHS, typename RHS>
    431 inline BinOp2_match<LHS, RHS, Instruction::LShr, Instruction::Shl>
    432 m_LogicalShift(const LHS &L, const RHS &R) {
    433   return BinOp2_match<LHS, RHS, Instruction::LShr, Instruction::Shl>(L, R);
    434 }
    435 
    436 /// m_IDiv - Matches UDiv and SDiv.
    437 template<typename LHS, typename RHS>
    438 inline BinOp2_match<LHS, RHS, Instruction::SDiv, Instruction::UDiv>
    439 m_IDiv(const LHS &L, const RHS &R) {
    440   return BinOp2_match<LHS, RHS, Instruction::SDiv, Instruction::UDiv>(L, R);
    441 }
    442 
    443 //===----------------------------------------------------------------------===//
    444 // Matchers for CmpInst classes
    445 //
    446 
    447 template<typename LHS_t, typename RHS_t, typename Class, typename PredicateTy>
    448 struct CmpClass_match {
    449   PredicateTy &Predicate;
    450   LHS_t L;
    451   RHS_t R;
    452 
    453   CmpClass_match(PredicateTy &Pred, const LHS_t &LHS, const RHS_t &RHS)
    454     : Predicate(Pred), L(LHS), R(RHS) {}
    455 
    456   template<typename OpTy>
    457   bool match(OpTy *V) {
    458     if (Class *I = dyn_cast<Class>(V))
    459       if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) {
    460         Predicate = I->getPredicate();
    461         return true;
    462       }
    463     return false;
    464   }
    465 };
    466 
    467 template<typename LHS, typename RHS>
    468 inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>
    469 m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
    470   return CmpClass_match<LHS, RHS,
    471                         ICmpInst, ICmpInst::Predicate>(Pred, L, R);
    472 }
    473 
    474 template<typename LHS, typename RHS>
    475 inline CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>
    476 m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
    477   return CmpClass_match<LHS, RHS,
    478                         FCmpInst, FCmpInst::Predicate>(Pred, L, R);
    479 }
    480 
    481 //===----------------------------------------------------------------------===//
    482 // Matchers for SelectInst classes
    483 //
    484 
    485 template<typename Cond_t, typename LHS_t, typename RHS_t>
    486 struct SelectClass_match {
    487   Cond_t C;
    488   LHS_t L;
    489   RHS_t R;
    490 
    491   SelectClass_match(const Cond_t &Cond, const LHS_t &LHS,
    492                     const RHS_t &RHS)
    493     : C(Cond), L(LHS), R(RHS) {}
    494 
    495   template<typename OpTy>
    496   bool match(OpTy *V) {
    497     if (SelectInst *I = dyn_cast<SelectInst>(V))
    498       return C.match(I->getOperand(0)) &&
    499              L.match(I->getOperand(1)) &&
    500              R.match(I->getOperand(2));
    501     return false;
    502   }
    503 };
    504 
    505 template<typename Cond, typename LHS, typename RHS>
    506 inline SelectClass_match<Cond, LHS, RHS>
    507 m_Select(const Cond &C, const LHS &L, const RHS &R) {
    508   return SelectClass_match<Cond, LHS, RHS>(C, L, R);
    509 }
    510 
    511 /// m_SelectCst - This matches a select of two constants, e.g.:
    512 ///    m_SelectCst<-1, 0>(m_Value(V))
    513 template<int64_t L, int64_t R, typename Cond>
    514 inline SelectClass_match<Cond, constantint_match<L>, constantint_match<R> >
    515 m_SelectCst(const Cond &C) {
    516   return m_Select(C, m_ConstantInt<L>(), m_ConstantInt<R>());
    517 }
    518 
    519 
    520 //===----------------------------------------------------------------------===//
    521 // Matchers for CastInst classes
    522 //
    523 
    524 template<typename Op_t, unsigned Opcode>
    525 struct CastClass_match {
    526   Op_t Op;
    527 
    528   CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {}
    529 
    530   template<typename OpTy>
    531   bool match(OpTy *V) {
    532     if (CastInst *I = dyn_cast<CastInst>(V))
    533       return I->getOpcode() == Opcode && Op.match(I->getOperand(0));
    534     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
    535       return CE->getOpcode() == Opcode && Op.match(CE->getOperand(0));
    536     return false;
    537   }
    538 };
    539 
    540 /// m_BitCast
    541 template<typename OpTy>
    542 inline CastClass_match<OpTy, Instruction::BitCast>
    543 m_BitCast(const OpTy &Op) {
    544   return CastClass_match<OpTy, Instruction::BitCast>(Op);
    545 }
    546 
    547 /// m_PtrToInt
    548 template<typename OpTy>
    549 inline CastClass_match<OpTy, Instruction::PtrToInt>
    550 m_PtrToInt(const OpTy &Op) {
    551   return CastClass_match<OpTy, Instruction::PtrToInt>(Op);
    552 }
    553 
    554 /// m_Trunc
    555 template<typename OpTy>
    556 inline CastClass_match<OpTy, Instruction::Trunc>
    557 m_Trunc(const OpTy &Op) {
    558   return CastClass_match<OpTy, Instruction::Trunc>(Op);
    559 }
    560 
    561 /// m_SExt
    562 template<typename OpTy>
    563 inline CastClass_match<OpTy, Instruction::SExt>
    564 m_SExt(const OpTy &Op) {
    565   return CastClass_match<OpTy, Instruction::SExt>(Op);
    566 }
    567 
    568 /// m_ZExt
    569 template<typename OpTy>
    570 inline CastClass_match<OpTy, Instruction::ZExt>
    571 m_ZExt(const OpTy &Op) {
    572   return CastClass_match<OpTy, Instruction::ZExt>(Op);
    573 }
    574 
    575 
    576 //===----------------------------------------------------------------------===//
    577 // Matchers for unary operators
    578 //
    579 
    580 template<typename LHS_t>
    581 struct not_match {
    582   LHS_t L;
    583 
    584   not_match(const LHS_t &LHS) : L(LHS) {}
    585 
    586   template<typename OpTy>
    587   bool match(OpTy *V) {
    588     if (Instruction *I = dyn_cast<Instruction>(V))
    589       if (I->getOpcode() == Instruction::Xor)
    590         return matchIfNot(I->getOperand(0), I->getOperand(1));
    591     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
    592       if (CE->getOpcode() == Instruction::Xor)
    593         return matchIfNot(CE->getOperand(0), CE->getOperand(1));
    594     return false;
    595   }
    596 private:
    597   bool matchIfNot(Value *LHS, Value *RHS) {
    598     if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
    599       return CI->isAllOnesValue() && L.match(LHS);
    600     if (ConstantVector *CV = dyn_cast<ConstantVector>(RHS))
    601       return CV->isAllOnesValue() && L.match(LHS);
    602     return false;
    603   }
    604 };
    605 
    606 template<typename LHS>
    607 inline not_match<LHS> m_Not(const LHS &L) { return L; }
    608 
    609 
    610 template<typename LHS_t>
    611 struct neg_match {
    612   LHS_t L;
    613 
    614   neg_match(const LHS_t &LHS) : L(LHS) {}
    615 
    616   template<typename OpTy>
    617   bool match(OpTy *V) {
    618     if (Instruction *I = dyn_cast<Instruction>(V))
    619       if (I->getOpcode() == Instruction::Sub)
    620         return matchIfNeg(I->getOperand(0), I->getOperand(1));
    621     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
    622       if (CE->getOpcode() == Instruction::Sub)
    623         return matchIfNeg(CE->getOperand(0), CE->getOperand(1));
    624     return false;
    625   }
    626 private:
    627   bool matchIfNeg(Value *LHS, Value *RHS) {
    628     if (ConstantInt *C = dyn_cast<ConstantInt>(LHS))
    629       return C->isZero() && L.match(RHS);
    630     return false;
    631   }
    632 };
    633 
    634 /// m_Neg - Match an integer negate.
    635 template<typename LHS>
    636 inline neg_match<LHS> m_Neg(const LHS &L) { return L; }
    637 
    638 
    639 template<typename LHS_t>
    640 struct fneg_match {
    641   LHS_t L;
    642 
    643   fneg_match(const LHS_t &LHS) : L(LHS) {}
    644 
    645   template<typename OpTy>
    646   bool match(OpTy *V) {
    647     if (Instruction *I = dyn_cast<Instruction>(V))
    648       if (I->getOpcode() == Instruction::FSub)
    649         return matchIfFNeg(I->getOperand(0), I->getOperand(1));
    650     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
    651       if (CE->getOpcode() == Instruction::FSub)
    652         return matchIfFNeg(CE->getOperand(0), CE->getOperand(1));
    653     return false;
    654   }
    655 private:
    656   bool matchIfFNeg(Value *LHS, Value *RHS) {
    657     if (ConstantFP *C = dyn_cast<ConstantFP>(LHS))
    658       return C->isNegativeZeroValue() && L.match(RHS);
    659     return false;
    660   }
    661 };
    662 
    663 /// m_FNeg - Match a floating point negate.
    664 template<typename LHS>
    665 inline fneg_match<LHS> m_FNeg(const LHS &L) { return L; }
    666 
    667 
    668 //===----------------------------------------------------------------------===//
    669 // Matchers for control flow.
    670 //
    671 
    672 template<typename Cond_t>
    673 struct brc_match {
    674   Cond_t Cond;
    675   BasicBlock *&T, *&F;
    676   brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f)
    677     : Cond(C), T(t), F(f) {
    678   }
    679 
    680   template<typename OpTy>
    681   bool match(OpTy *V) {
    682     if (BranchInst *BI = dyn_cast<BranchInst>(V))
    683       if (BI->isConditional() && Cond.match(BI->getCondition())) {
    684         T = BI->getSuccessor(0);
    685         F = BI->getSuccessor(1);
    686         return true;
    687       }
    688     return false;
    689   }
    690 };
    691 
    692 template<typename Cond_t>
    693 inline brc_match<Cond_t> m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) {
    694   return brc_match<Cond_t>(C, T, F);
    695 }
    696 
    697 
    698 //===----------------------------------------------------------------------===//
    699 // Matchers for max/min idioms, eg: "select (sgt x, y), x, y" -> smax(x,y).
    700 //
    701 
    702 template<typename LHS_t, typename RHS_t, typename Pred_t>
    703 struct MaxMin_match {
    704   LHS_t L;
    705   RHS_t R;
    706 
    707   MaxMin_match(const LHS_t &LHS, const RHS_t &RHS)
    708     : L(LHS), R(RHS) {}
    709 
    710   template<typename OpTy>
    711   bool match(OpTy *V) {
    712     // Look for "(x pred y) ? x : y" or "(x pred y) ? y : x".
    713     SelectInst *SI = dyn_cast<SelectInst>(V);
    714     if (!SI)
    715       return false;
    716     ICmpInst *Cmp = dyn_cast<ICmpInst>(SI->getCondition());
    717     if (!Cmp)
    718       return false;
    719     // At this point we have a select conditioned on a comparison.  Check that
    720     // it is the values returned by the select that are being compared.
    721     Value *TrueVal = SI->getTrueValue();
    722     Value *FalseVal = SI->getFalseValue();
    723     Value *LHS = Cmp->getOperand(0);
    724     Value *RHS = Cmp->getOperand(1);
    725     if ((TrueVal != LHS || FalseVal != RHS) &&
    726         (TrueVal != RHS || FalseVal != LHS))
    727       return false;
    728     ICmpInst::Predicate Pred = LHS == TrueVal ?
    729       Cmp->getPredicate() : Cmp->getSwappedPredicate();
    730     // Does "(x pred y) ? x : y" represent the desired max/min operation?
    731     if (!Pred_t::match(Pred))
    732       return false;
    733     // It does!  Bind the operands.
    734     return L.match(LHS) && R.match(RHS);
    735   }
    736 };
    737 
    738 /// smax_pred_ty - Helper class for identifying signed max predicates.
    739 struct smax_pred_ty {
    740   static bool match(ICmpInst::Predicate Pred) {
    741     return Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE;
    742   }
    743 };
    744 
    745 /// smin_pred_ty - Helper class for identifying signed min predicates.
    746 struct smin_pred_ty {
    747   static bool match(ICmpInst::Predicate Pred) {
    748     return Pred == CmpInst::ICMP_SLT || Pred == CmpInst::ICMP_SLE;
    749   }
    750 };
    751 
    752 /// umax_pred_ty - Helper class for identifying unsigned max predicates.
    753 struct umax_pred_ty {
    754   static bool match(ICmpInst::Predicate Pred) {
    755     return Pred == CmpInst::ICMP_UGT || Pred == CmpInst::ICMP_UGE;
    756   }
    757 };
    758 
    759 /// umin_pred_ty - Helper class for identifying unsigned min predicates.
    760 struct umin_pred_ty {
    761   static bool match(ICmpInst::Predicate Pred) {
    762     return Pred == CmpInst::ICMP_ULT || Pred == CmpInst::ICMP_ULE;
    763   }
    764 };
    765 
    766 template<typename LHS, typename RHS>
    767 inline MaxMin_match<LHS, RHS, smax_pred_ty>
    768 m_SMax(const LHS &L, const RHS &R) {
    769   return MaxMin_match<LHS, RHS, smax_pred_ty>(L, R);
    770 }
    771 
    772 template<typename LHS, typename RHS>
    773 inline MaxMin_match<LHS, RHS, smin_pred_ty>
    774 m_SMin(const LHS &L, const RHS &R) {
    775   return MaxMin_match<LHS, RHS, smin_pred_ty>(L, R);
    776 }
    777 
    778 template<typename LHS, typename RHS>
    779 inline MaxMin_match<LHS, RHS, umax_pred_ty>
    780 m_UMax(const LHS &L, const RHS &R) {
    781   return MaxMin_match<LHS, RHS, umax_pred_ty>(L, R);
    782 }
    783 
    784 template<typename LHS, typename RHS>
    785 inline MaxMin_match<LHS, RHS, umin_pred_ty>
    786 m_UMin(const LHS &L, const RHS &R) {
    787   return MaxMin_match<LHS, RHS, umin_pred_ty>(L, R);
    788 }
    789 
    790 } // end namespace PatternMatch
    791 } // end namespace llvm
    792 
    793 #endif
    794