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