include/llvm/Support/PatternMatch.h

   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 template<typename Class>
  44 struct leaf_ty {
  45   template<typename ITy>
  46   bool match(ITy *V) { return isa<Class>(V); }
  47 };
  48
  49 /// m_Value() - Match an arbitrary value and ignore it.
  50 inline leaf_ty<Value> m_Value() { return leaf_ty<Value>(); }
  51 /// m_ConstantInt() - Match an arbitrary ConstantInt and ignore it.
  52 inline leaf_ty<ConstantInt> m_ConstantInt() { return leaf_ty<ConstantInt>(); }
  53
  54 template<int64_t Val>
  55 struct constantint_ty {
  56   template<typename ITy>
  57   bool match(ITy *V) {
  58     if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
  59       const APInt &CIV = CI->getValue();
  60       if (Val >= 0)
  61         return CIV == static_cast<uint64_t>(Val);
  62       // If Val is negative, and CI is shorter than it, truncate to the right
  63       // number of bits.  If it is larger, then we have to sign extend.  Just
  64       // compare their negated values.
  65       return -CIV == -Val;
  66     }
  67     return false;
  68   }
  69 };
  70
  71 /// m_ConstantInt(int64_t) - Match a ConstantInt with a specific value
  72 /// and ignore it.
  73 template<int64_t Val>
  74 inline constantint_ty<Val> m_ConstantInt() {
  75   return constantint_ty<Val>();
  76 }
  77
  78 struct undef_ty {
  79   template<typename ITy>
  80   bool match(ITy *V) {
  81     return isa<UndefValue>(V);
  82   }
  83 };
  84
  85 /// m_Undef() - Match an arbitrary undef constant.
  86 inline undef_ty m_Undef() { return undef_ty(); }
  87
  88 struct zero_ty {
  89   template<typename ITy>
  90   bool match(ITy *V) {
  91     if (const Constant *C = dyn_cast<Constant>(V))
  92       return C->isNullValue();
  93     return false;
  94   }
  95 };
  96
  97 /// m_Zero() - Match an arbitrary zero/null constant.
  98 inline zero_ty m_Zero() { return zero_ty(); }
  99
 100 struct one_ty {
 101   template<typename ITy>
 102   bool match(ITy *V) {
 103     if (const ConstantInt *CI = dyn_cast<ConstantInt>(V))
 104       return CI->isOne();
 105     if (const ConstantVector *CV = dyn_cast<ConstantVector>(V))
 106       if (ConstantInt *CI = cast_or_null<ConstantInt>(CV->getSplatValue()))
 107         return CI->isOne();
 108     return false;
 109   }
 110 };
 111
 112 /// m_One() - Match an integer 1 or a vector with all elements equal to 1.
 113 inline one_ty m_One() { return one_ty(); }
 114
 115 struct all_ones_ty {
 116   template<typename ITy>
 117   bool match(ITy *V) {
 118     if (const ConstantInt *C = dyn_cast<ConstantInt>(V))
 119       return C->isAllOnesValue();
 120     if (const ConstantVector *C = dyn_cast<ConstantVector>(V))
 121       return C->isAllOnesValue();
 122     return false;
 123   }
 124 };
 125
 126 /// m_AllOnes() - Match an integer or vector with all bits set to true.
 127 inline all_ones_ty m_AllOnes() { return all_ones_ty(); }
 128
 129 struct signbit_ty {
 130   template<typename ITy>
 131   bool match(ITy *V) {
 132     if (const ConstantInt *CI = dyn_cast<ConstantInt>(V))
 133       return CI->getValue().isSignBit();
 134     if (const ConstantVector *CV = dyn_cast<ConstantVector>(V))
 135       if (ConstantInt *CI = cast_or_null<ConstantInt>(CV->getSplatValue()))
 136         return CI->getValue().isSignBit();
 137     return false;
 138   }
 139 };
 140
 141 /// m_SignBit() - Match an integer or vector with only the sign bit(s) set.
 142 inline signbit_ty m_SignBit() { return signbit_ty(); }
 143
 144
 145 template<typename Class>
 146 struct bind_ty {
 147   Class *&VR;
 148   bind_ty(Class *&V) : VR(V) {}
 149
 150   template<typename ITy>
 151   bool match(ITy *V) {
 152     if (Class *CV = dyn_cast<Class>(V)) {
 153       VR = CV;
 154       return true;
 155     }
 156     return false;
 157   }
 158 };
 159
 160 /// m_Value - Match a value, capturing it if we match.
 161 inline bind_ty<Value> m_Value(Value *&V) { return V; }
 162
 163 /// m_ConstantInt - Match a ConstantInt, capturing the value if we match.
 164 inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
 165
 166 /// specificval_ty - Match a specified Value*.
 167 struct specificval_ty {
 168   const Value *Val;
 169   specificval_ty(const Value *V) : Val(V) {}
 170
 171   template<typename ITy>
 172   bool match(ITy *V) {
 173     return V == Val;
 174   }
 175 };
 176
 177 /// m_Specific - Match if we have a specific specified value.
 178 inline specificval_ty m_Specific(const Value *V) { return V; }
 179
 180
 181 //===----------------------------------------------------------------------===//
 182 // Matchers for specific binary operators.
 183 //
 184
 185 template<typename LHS_t, typename RHS_t,
 186          unsigned Opcode, typename ConcreteTy = BinaryOperator>
 187 struct BinaryOp_match {
 188   LHS_t L;
 189   RHS_t R;
 190
 191   BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
 192
 193   template<typename OpTy>
 194   bool match(OpTy *V) {
 195     if (V->getValueID() == Value::InstructionVal + Opcode) {
 196       ConcreteTy *I = cast<ConcreteTy>(V);
 197       return I->getOpcode() == Opcode && L.match(I->getOperand(0)) &&
 198              R.match(I->getOperand(1));
 199     }
 200     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
 201       return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
 202              R.match(CE->getOperand(1));
 203     return false;
 204   }
 205 };
 206
 207 template<typename LHS, typename RHS>
 208 inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L,
 209                                                         const RHS &R) {
 210   return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);
 211 }
 212
 213 template<typename LHS, typename RHS>
 214 inline BinaryOp_match<LHS, RHS, Instruction::FAdd> m_FAdd(const LHS &L,
 215                                                           const RHS &R) {
 216   return BinaryOp_match<LHS, RHS, Instruction::FAdd>(L, R);
 217 }
 218
 219 template<typename LHS, typename RHS>
 220 inline BinaryOp_match<LHS, RHS, Instruction::Sub> m_Sub(const LHS &L,
 221                                                         const RHS &R) {
 222   return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R);
 223 }
 224
 225 template<typename LHS, typename RHS>
 226 inline BinaryOp_match<LHS, RHS, Instruction::FSub> m_FSub(const LHS &L,
 227                                                           const RHS &R) {
 228   return BinaryOp_match<LHS, RHS, Instruction::FSub>(L, R);
 229 }
 230
 231 template<typename LHS, typename RHS>
 232 inline BinaryOp_match<LHS, RHS, Instruction::Mul> m_Mul(const LHS &L,
 233                                                         const RHS &R) {
 234   return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R);
 235 }
 236
 237 template<typename LHS, typename RHS>
 238 inline BinaryOp_match<LHS, RHS, Instruction::FMul> m_FMul(const LHS &L,
 239                                                           const RHS &R) {
 240   return BinaryOp_match<LHS, RHS, Instruction::FMul>(L, R);
 241 }
 242
 243 template<typename LHS, typename RHS>
 244 inline BinaryOp_match<LHS, RHS, Instruction::UDiv> m_UDiv(const LHS &L,
 245                                                         const RHS &R) {
 246   return BinaryOp_match<LHS, RHS, Instruction::UDiv>(L, R);
 247 }
 248
 249 template<typename LHS, typename RHS>
 250 inline BinaryOp_match<LHS, RHS, Instruction::SDiv> m_SDiv(const LHS &L,
 251                                                         const RHS &R) {
 252   return BinaryOp_match<LHS, RHS, Instruction::SDiv>(L, R);
 253 }
 254
 255 template<typename LHS, typename RHS>
 256 inline BinaryOp_match<LHS, RHS, Instruction::FDiv> m_FDiv(const LHS &L,
 257                                                         const RHS &R) {
 258   return BinaryOp_match<LHS, RHS, Instruction::FDiv>(L, R);
 259 }
 260
 261 template<typename LHS, typename RHS>
 262 inline BinaryOp_match<LHS, RHS, Instruction::URem> m_URem(const LHS &L,
 263                                                           const RHS &R) {
 264   return BinaryOp_match<LHS, RHS, Instruction::URem>(L, R);
 265 }
 266
 267 template<typename LHS, typename RHS>
 268 inline BinaryOp_match<LHS, RHS, Instruction::SRem> m_SRem(const LHS &L,
 269                                                           const RHS &R) {
 270   return BinaryOp_match<LHS, RHS, Instruction::SRem>(L, R);
 271 }
 272
 273 template<typename LHS, typename RHS>
 274 inline BinaryOp_match<LHS, RHS, Instruction::FRem> m_FRem(const LHS &L,
 275                                                         const RHS &R) {
 276   return BinaryOp_match<LHS, RHS, Instruction::FRem>(L, R);
 277 }
 278
 279 template<typename LHS, typename RHS>
 280 inline BinaryOp_match<LHS, RHS, Instruction::And> m_And(const LHS &L,
 281                                                         const RHS &R) {
 282   return BinaryOp_match<LHS, RHS, Instruction::And>(L, R);
 283 }
 284
 285 template<typename LHS, typename RHS>
 286 inline BinaryOp_match<LHS, RHS, Instruction::Or> m_Or(const LHS &L,
 287                                                       const RHS &R) {
 288   return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R);
 289 }
 290
 291 template<typename LHS, typename RHS>
 292 inline BinaryOp_match<LHS, RHS, Instruction::Xor> m_Xor(const LHS &L,
 293                                                         const RHS &R) {
 294   return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R);
 295 }
 296
 297 template<typename LHS, typename RHS>
 298 inline BinaryOp_match<LHS, RHS, Instruction::Shl> m_Shl(const LHS &L,
 299                                                         const RHS &R) {
 300   return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R);
 301 }
 302
 303 template<typename LHS, typename RHS>
 304 inline BinaryOp_match<LHS, RHS, Instruction::LShr> m_LShr(const LHS &L,
 305                                                           const RHS &R) {
 306   return BinaryOp_match<LHS, RHS, Instruction::LShr>(L, R);
 307 }
 308
 309 template<typename LHS, typename RHS>
 310 inline BinaryOp_match<LHS, RHS, Instruction::AShr> m_AShr(const LHS &L,
 311                                                           const RHS &R) {
 312   return BinaryOp_match<LHS, RHS, Instruction::AShr>(L, R);
 313 }
 314
 315 //===----------------------------------------------------------------------===//
 316 // Matchers for either AShr or LShr .. for convenience
 317 //
 318 template<typename LHS_t, typename RHS_t, typename ConcreteTy = BinaryOperator>
 319 struct Shr_match {
 320   LHS_t L;
 321   RHS_t R;
 322
 323   Shr_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
 324
 325   template<typename OpTy>
 326   bool match(OpTy *V) {
 327     if (V->getValueID() == Value::InstructionVal + Instruction::LShr ||
 328         V->getValueID() == Value::InstructionVal + Instruction::AShr) {
 329       ConcreteTy *I = cast<ConcreteTy>(V);
 330       return (I->getOpcode() == Instruction::AShr ||
 331               I->getOpcode() == Instruction::LShr) &&
 332              L.match(I->getOperand(0)) &&
 333              R.match(I->getOperand(1));
 334     }
 335     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
 336       return (CE->getOpcode() == Instruction::LShr ||
 337               CE->getOpcode() == Instruction::AShr) &&
 338              L.match(CE->getOperand(0)) &&
 339              R.match(CE->getOperand(1));
 340     return false;
 341   }
 342 };
 343
 344 template<typename LHS, typename RHS>
 345 inline Shr_match<LHS, RHS> m_Shr(const LHS &L, const RHS &R) {
 346   return Shr_match<LHS, RHS>(L, R);
 347 }
 348
 349 //===----------------------------------------------------------------------===//
 350 // Matchers for binary classes
 351 //
 352
 353 template<typename LHS_t, typename RHS_t, typename Class, typename OpcType>
 354 struct BinaryOpClass_match {
 355   OpcType *Opcode;
 356   LHS_t L;
 357   RHS_t R;
 358
 359   BinaryOpClass_match(OpcType &Op, const LHS_t &LHS,
 360                       const RHS_t &RHS)
 361     : Opcode(&Op), L(LHS), R(RHS) {}
 362   BinaryOpClass_match(const LHS_t &LHS, const RHS_t &RHS)
 363     : Opcode(0), L(LHS), R(RHS) {}
 364
 365   template<typename OpTy>
 366   bool match(OpTy *V) {
 367     if (Class *I = dyn_cast<Class>(V))
 368       if (L.match(I->getOperand(0)) &&
 369           R.match(I->getOperand(1))) {
 370         if (Opcode)
 371           *Opcode = I->getOpcode();
 372         return true;
 373       }
 374 #if 0  // Doesn't handle constantexprs yet!
 375     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
 376       return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
 377              R.match(CE->getOperand(1));
 378 #endif
 379     return false;
 380   }
 381 };
 382
 383 template<typename LHS, typename RHS>
 384 inline BinaryOpClass_match<LHS, RHS, BinaryOperator, Instruction::BinaryOps>
 385 m_Shift(Instruction::BinaryOps &Op, const LHS &L, const RHS &R) {
 386   return BinaryOpClass_match<LHS, RHS,
 387                              BinaryOperator, Instruction::BinaryOps>(Op, L, R);
 388 }
 389
 390 template<typename LHS, typename RHS>
 391 inline BinaryOpClass_match<LHS, RHS, BinaryOperator, Instruction::BinaryOps>
 392 m_Shift(const LHS &L, const RHS &R) {
 393   return BinaryOpClass_match<LHS, RHS,
 394                              BinaryOperator, Instruction::BinaryOps>(L, R);
 395 }
 396
 397 //===----------------------------------------------------------------------===//
 398 // Matchers for CmpInst classes
 399 //
 400
 401 template<typename LHS_t, typename RHS_t, typename Class, typename PredicateTy>
 402 struct CmpClass_match {
 403   PredicateTy &Predicate;
 404   LHS_t L;
 405   RHS_t R;
 406
 407   CmpClass_match(PredicateTy &Pred, const LHS_t &LHS,
 408                  const RHS_t &RHS)
 409     : Predicate(Pred), L(LHS), R(RHS) {}
 410
 411   template<typename OpTy>
 412   bool match(OpTy *V) {
 413     if (Class *I = dyn_cast<Class>(V))
 414       if (L.match(I->getOperand(0)) &&
 415           R.match(I->getOperand(1))) {
 416         Predicate = I->getPredicate();
 417         return true;
 418       }
 419     return false;
 420   }
 421 };
 422
 423 template<typename LHS, typename RHS>
 424 inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>
 425 m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
 426   return CmpClass_match<LHS, RHS,
 427                         ICmpInst, ICmpInst::Predicate>(Pred, L, R);
 428 }
 429
 430 template<typename LHS, typename RHS>
 431 inline CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>
 432 m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
 433   return CmpClass_match<LHS, RHS,
 434                         FCmpInst, FCmpInst::Predicate>(Pred, L, R);
 435 }
 436
 437 //===----------------------------------------------------------------------===//
 438 // Matchers for SelectInst classes
 439 //
 440
 441 template<typename Cond_t, typename LHS_t, typename RHS_t>
 442 struct SelectClass_match {
 443   Cond_t C;
 444   LHS_t L;
 445   RHS_t R;
 446
 447   SelectClass_match(const Cond_t &Cond, const LHS_t &LHS,
 448                     const RHS_t &RHS)
 449     : C(Cond), L(LHS), R(RHS) {}
 450
 451   template<typename OpTy>
 452   bool match(OpTy *V) {
 453     if (SelectInst *I = dyn_cast<SelectInst>(V))
 454       return C.match(I->getOperand(0)) &&
 455              L.match(I->getOperand(1)) &&
 456              R.match(I->getOperand(2));
 457     return false;
 458   }
 459 };
 460
 461 template<typename Cond, typename LHS, typename RHS>
 462 inline SelectClass_match<Cond, LHS, RHS>
 463 m_Select(const Cond &C, const LHS &L, const RHS &R) {
 464   return SelectClass_match<Cond, LHS, RHS>(C, L, R);
 465 }
 466
 467 /// m_SelectCst - This matches a select of two constants, e.g.:
 468 ///    m_SelectCst<-1, 0>(m_Value(V))
 469 template<int64_t L, int64_t R, typename Cond>
 470 inline SelectClass_match<Cond, constantint_ty<L>, constantint_ty<R> >
 471 m_SelectCst(const Cond &C) {
 472   return SelectClass_match<Cond, constantint_ty<L>,
 473                            constantint_ty<R> >(C, m_ConstantInt<L>(),
 474                                            m_ConstantInt<R>());
 475 }
 476
 477
 478 //===----------------------------------------------------------------------===//
 479 // Matchers for CastInst classes
 480 //
 481
 482 template<typename Op_t, unsigned Opcode>
 483 struct CastClass_match {
 484   Op_t Op;
 485
 486   CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {}
 487
 488   template<typename OpTy>
 489   bool match(OpTy *V) {
 490     if (CastInst *I = dyn_cast<CastInst>(V))
 491       return I->getOpcode() == Opcode && Op.match(I->getOperand(0));
 492     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
 493       return CE->getOpcode() == Opcode && Op.match(CE->getOperand(0));
 494     return false;
 495   }
 496 };
 497
 498 /// m_BitCast
 499 template<typename OpTy>
 500 inline CastClass_match<OpTy, Instruction::BitCast>
 501 m_BitCast(const OpTy &Op) {
 502   return CastClass_match<OpTy, Instruction::BitCast>(Op);
 503 }
 504
 505 /// m_PtrToInt
 506 template<typename OpTy>
 507 inline CastClass_match<OpTy, Instruction::PtrToInt>
 508 m_PtrToInt(const OpTy &Op) {
 509   return CastClass_match<OpTy, Instruction::PtrToInt>(Op);
 510 }
 511
 512 /// m_Trunc
 513 template<typename OpTy>
 514 inline CastClass_match<OpTy, Instruction::Trunc>
 515 m_Trunc(const OpTy &Op) {
 516   return CastClass_match<OpTy, Instruction::Trunc>(Op);
 517 }
 518
 519 /// m_SExt
 520 template<typename OpTy>
 521 inline CastClass_match<OpTy, Instruction::SExt>
 522 m_SExt(const OpTy &Op) {
 523   return CastClass_match<OpTy, Instruction::SExt>(Op);
 524 }
 525
 526 /// m_ZExt
 527 template<typename OpTy>
 528 inline CastClass_match<OpTy, Instruction::ZExt>
 529 m_ZExt(const OpTy &Op) {
 530   return CastClass_match<OpTy, Instruction::ZExt>(Op);
 531 }
 532
 533
 534 //===----------------------------------------------------------------------===//
 535 // Matchers for unary operators
 536 //
 537
 538 template<typename LHS_t>
 539 struct not_match {
 540   LHS_t L;
 541
 542   not_match(const LHS_t &LHS) : L(LHS) {}
 543
 544   template<typename OpTy>
 545   bool match(OpTy *V) {
 546     if (Instruction *I = dyn_cast<Instruction>(V))
 547       if (I->getOpcode() == Instruction::Xor)
 548         return matchIfNot(I->getOperand(0), I->getOperand(1));
 549     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
 550       if (CE->getOpcode() == Instruction::Xor)
 551         return matchIfNot(CE->getOperand(0), CE->getOperand(1));
 552     return false;
 553   }
 554 private:
 555   bool matchIfNot(Value *LHS, Value *RHS) {
 556     if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
 557       return CI->isAllOnesValue() && L.match(LHS);
 558     if (ConstantInt *CI = dyn_cast<ConstantInt>(LHS))
 559       return CI->isAllOnesValue() && L.match(RHS);
 560     if (ConstantVector *CV = dyn_cast<ConstantVector>(RHS))
 561       return CV->isAllOnesValue() && L.match(LHS);
 562     if (ConstantVector *CV = dyn_cast<ConstantVector>(LHS))
 563       return CV->isAllOnesValue() && L.match(RHS);
 564     return false;
 565   }
 566 };
 567
 568 template<typename LHS>
 569 inline not_match<LHS> m_Not(const LHS &L) { return L; }
 570
 571
 572 template<typename LHS_t>
 573 struct neg_match {
 574   LHS_t L;
 575
 576   neg_match(const LHS_t &LHS) : L(LHS) {}
 577
 578   template<typename OpTy>
 579   bool match(OpTy *V) {
 580     if (Instruction *I = dyn_cast<Instruction>(V))
 581       if (I->getOpcode() == Instruction::Sub)
 582         return matchIfNeg(I->getOperand(0), I->getOperand(1));
 583     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
 584       if (CE->getOpcode() == Instruction::Sub)
 585         return matchIfNeg(CE->getOperand(0), CE->getOperand(1));
 586     return false;
 587   }
 588 private:
 589   bool matchIfNeg(Value *LHS, Value *RHS) {
 590     return LHS == ConstantFP::getZeroValueForNegation(LHS->getType()) &&
 591            L.match(RHS);
 592   }
 593 };
 594
 595 template<typename LHS>
 596 inline neg_match<LHS> m_Neg(const LHS &L) { return L; }
 597
 598
 599 template<typename LHS_t>
 600 struct fneg_match {
 601   LHS_t L;
 602
 603   fneg_match(const LHS_t &LHS) : L(LHS) {}
 604
 605   template<typename OpTy>
 606   bool match(OpTy *V) {
 607     if (Instruction *I = dyn_cast<Instruction>(V))
 608       if (I->getOpcode() == Instruction::FSub)
 609         return matchIfFNeg(I->getOperand(0), I->getOperand(1));
 610     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
 611       if (CE->getOpcode() == Instruction::FSub)
 612         return matchIfFNeg(CE->getOperand(0), CE->getOperand(1));
 613     if (ConstantFP *CF = dyn_cast<ConstantFP>(V))
 614       return L.match(ConstantExpr::getFNeg(CF));
 615     return false;
 616   }
 617 private:
 618   bool matchIfFNeg(Value *LHS, Value *RHS) {
 619     return LHS == ConstantFP::getZeroValueForNegation(LHS->getType()) &&
 620            L.match(RHS);
 621   }
 622 };
 623
 624 template<typename LHS>
 625 inline fneg_match<LHS> m_FNeg(const LHS &L) { return L; }
 626
 627
 628 //===----------------------------------------------------------------------===//
 629 // Matchers for control flow
 630 //
 631
 632 template<typename Cond_t>
 633 struct brc_match {
 634   Cond_t Cond;
 635   BasicBlock *&T, *&F;
 636   brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f)
 637     : Cond(C), T(t), F(f) {
 638   }
 639
 640   template<typename OpTy>
 641   bool match(OpTy *V) {
 642     if (BranchInst *BI = dyn_cast<BranchInst>(V))
 643       if (BI->isConditional()) {
 644         if (Cond.match(BI->getCondition())) {
 645           T = BI->getSuccessor(0);
 646           F = BI->getSuccessor(1);
 647           return true;
 648         }
 649       }
 650     return false;
 651   }
 652 };
 653
 654 template<typename Cond_t>
 655 inline brc_match<Cond_t> m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) {
 656   return brc_match<Cond_t>(C, T, F);
 657 }
 658
 659 } // end namespace PatternMatch
 660 } // end namespace llvm
 661
 662 #endif