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