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>
match(Val * V,const Pattern & P)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
OneUse_matchOneUse_match48 OneUse_match(const SubPattern_t &SP) : SubPattern(SP) {}
49
50 template<typename OpTy>
matchOneUse_match51 bool match(OpTy *V) {
52 return V->hasOneUse() && SubPattern.match(V);
53 }
54 };
55
56 template<typename T>
m_OneUse(const T & SubPattern)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>
matchclass_match63 bool match(ITy *V) { return isa<Class>(V); }
64 };
65
66 /// m_Value() - Match an arbitrary value and ignore it.
m_Value()67 inline class_match<Value> m_Value() { return class_match<Value>(); }
68 /// m_ConstantInt() - Match an arbitrary ConstantInt and ignore it.
m_ConstantInt()69 inline class_match<ConstantInt> m_ConstantInt() {
70 return class_match<ConstantInt>();
71 }
72 /// m_Undef() - Match an arbitrary undef constant.
m_Undef()73 inline class_match<UndefValue> m_Undef() { return class_match<UndefValue>(); }
74
m_Constant()75 inline class_match<Constant> m_Constant() { return class_match<Constant>(); }
76
77 struct match_zero {
78 template<typename ITy>
matchmatch_zero79 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.
m_Zero()88 inline match_zero m_Zero() { return match_zero(); }
89
90
91 struct apint_match {
92 const APInt *&Res;
apint_matchapint_match93 apint_match(const APInt *&R) : Res(R) {}
94 template<typename ITy>
matchapint_match95 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.
m_APInt(const APInt * & Res)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>
matchconstantint_match118 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>
m_ConstantInt()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>
matchcst_pred_ty143 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;
api_pred_tyapi_pred_ty158 api_pred_ty(const APInt *&R) : Res(R) {}
159 template<typename ITy>
matchapi_pred_ty160 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 {
isValueis_one178 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.
m_One()182 inline cst_pred_ty<is_one> m_One() { return cst_pred_ty<is_one>(); }
m_One(const APInt * & V)183 inline api_pred_ty<is_one> m_One(const APInt *&V) { return V; }
184
185 struct is_all_ones {
isValueis_all_ones186 bool isValue(const APInt &C) { return C.isAllOnesValue(); }
187 };
188
189 /// m_AllOnes() - Match an integer or vector with all bits set to true.
m_AllOnes()190 inline cst_pred_ty<is_all_ones> m_AllOnes() {return cst_pred_ty<is_all_ones>();}
m_AllOnes(const APInt * & V)191 inline api_pred_ty<is_all_ones> m_AllOnes(const APInt *&V) { return V; }
192
193 struct is_sign_bit {
isValueis_sign_bit194 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.
m_SignBit()198 inline cst_pred_ty<is_sign_bit> m_SignBit() {return cst_pred_ty<is_sign_bit>();}
m_SignBit(const APInt * & V)199 inline api_pred_ty<is_sign_bit> m_SignBit(const APInt *&V) { return V; }
200
201 struct is_power2 {
isValueis_power2202 bool isValue(const APInt &C) { return C.isPowerOf2(); }
203 };
204
205 /// m_Power2() - Match an integer or vector power of 2.
m_Power2()206 inline cst_pred_ty<is_power2> m_Power2() { return cst_pred_ty<is_power2>(); }
m_Power2(const APInt * & V)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;
bind_tybind_ty212 bind_ty(Class *&V) : VR(V) {}
213
214 template<typename ITy>
matchbind_ty215 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.
m_Value(Value * & V)225 inline bind_ty<Value> m_Value(Value *&V) { return V; }
226
227 /// m_ConstantInt - Match a ConstantInt, capturing the value if we match.
m_ConstantInt(ConstantInt * & CI)228 inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
229
230 /// m_Constant - Match a Constant, capturing the value if we match.
m_Constant(Constant * & C)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;
specificval_tyspecificval_ty236 specificval_ty(const Value *V) : Val(V) {}
237
238 template<typename ITy>
matchspecificval_ty239 bool match(ITy *V) {
240 return V == Val;
241 }
242 };
243
244 /// m_Specific - Match if we have a specific specified value.
m_Specific(const Value * V)245 inline specificval_ty m_Specific(const Value *V) { return V; }
246
247 struct bind_const_intval_ty {
248 uint64_t &VR;
bind_const_intval_tybind_const_intval_ty249 bind_const_intval_ty(uint64_t &V) : VR(V) {}
250
251 template<typename ITy>
matchbind_const_intval_ty252 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.
m_ConstantInt(uint64_t & V)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
BinaryOp_matchBinaryOp_match275 BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
276
277 template<typename OpTy>
matchBinaryOp_match278 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>
m_Add(const LHS & L,const RHS & R)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>
m_FAdd(const LHS & L,const RHS & R)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>
m_Sub(const LHS & L,const RHS & R)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>
m_FSub(const LHS & L,const RHS & R)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>
m_Mul(const LHS & L,const RHS & R)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>
m_FMul(const LHS & L,const RHS & R)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>
m_UDiv(const LHS & L,const RHS & R)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>
m_SDiv(const LHS & L,const RHS & R)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>
m_FDiv(const LHS & L,const RHS & R)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>
m_URem(const LHS & L,const RHS & R)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>
m_SRem(const LHS & L,const RHS & R)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>
m_FRem(const LHS & L,const RHS & R)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>
m_And(const LHS & L,const RHS & R)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>
m_Or(const LHS & L,const RHS & R)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>
m_Xor(const LHS & L,const RHS & R)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>
m_Shl(const LHS & L,const RHS & R)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>
m_LShr(const LHS & L,const RHS & R)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>
m_AShr(const LHS & L,const RHS & R)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
BinOp2_matchBinOp2_match406 BinOp2_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
407
408 template<typename OpTy>
matchBinOp2_match409 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>
m_Shr(const LHS & L,const RHS & R)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>
m_LogicalShift(const LHS & L,const RHS & R)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>
m_IDiv(const LHS & L,const RHS & R)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
CmpClass_matchCmpClass_match453 CmpClass_match(PredicateTy &Pred, const LHS_t &LHS, const RHS_t &RHS)
454 : Predicate(Pred), L(LHS), R(RHS) {}
455
456 template<typename OpTy>
matchCmpClass_match457 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>
m_ICmp(ICmpInst::Predicate & Pred,const LHS & L,const RHS & R)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>
m_FCmp(FCmpInst::Predicate & Pred,const LHS & L,const RHS & R)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
SelectClass_matchSelectClass_match491 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>
matchSelectClass_match496 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>
m_Select(const Cond & C,const LHS & L,const RHS & R)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> >
m_SelectCst(const Cond & C)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
CastClass_matchCastClass_match528 CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {}
529
530 template<typename OpTy>
matchCastClass_match531 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>
m_BitCast(const OpTy & Op)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>
m_PtrToInt(const OpTy & Op)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>
m_Trunc(const OpTy & Op)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>
m_SExt(const OpTy & Op)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>
m_ZExt(const OpTy & Op)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
not_matchnot_match584 not_match(const LHS_t &LHS) : L(LHS) {}
585
586 template<typename OpTy>
matchnot_match587 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:
matchIfNotnot_match597 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>
m_Not(const LHS & L)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
neg_matchneg_match614 neg_match(const LHS_t &LHS) : L(LHS) {}
615
616 template<typename OpTy>
matchneg_match617 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:
matchIfNegneg_match627 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>
m_Neg(const LHS & L)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
fneg_matchfneg_match643 fneg_match(const LHS_t &LHS) : L(LHS) {}
644
645 template<typename OpTy>
matchfneg_match646 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:
matchIfFNegfneg_match656 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>
m_FNeg(const LHS & L)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;
brc_matchbrc_match676 brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f)
677 : Cond(C), T(t), F(f) {
678 }
679
680 template<typename OpTy>
matchbrc_match681 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>
m_Br(const Cond_t & C,BasicBlock * & T,BasicBlock * & F)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
MaxMin_matchMaxMin_match707 MaxMin_match(const LHS_t &LHS, const RHS_t &RHS)
708 : L(LHS), R(RHS) {}
709
710 template<typename OpTy>
matchMaxMin_match711 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 {
matchsmax_pred_ty740 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 {
matchsmin_pred_ty747 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 {
matchumax_pred_ty754 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 {
matchumin_pred_ty761 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>
m_SMax(const LHS & L,const RHS & R)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>
m_SMin(const LHS & L,const RHS & R)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>
m_UMax(const LHS & L,const RHS & R)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>
m_UMin(const LHS & L,const RHS & R)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
794