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