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
  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