Fix up the ocaml kaleidoscope example as well.
[oota-llvm.git] / include / llvm / Support / PatternMatch.h
1 //===-- llvm/Support/PatternMatch.h - Match on the LLVM IR ------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file provides a simple and efficient mechanism for performing general
11 // tree-based pattern matches on the LLVM IR.  The power of these routines is
12 // that it allows you to write concise patterns that are expressive and easy to
13 // understand.  The other major advantage of this is that it allows you to
14 // trivially capture/bind elements in the pattern to variables.  For example,
15 // you can do something like this:
16 //
17 //  Value *Exp = ...
18 //  Value *X, *Y;  ConstantInt *C1, *C2;      // (X & C1) | (Y & C2)
19 //  if (match(Exp, m_Or(m_And(m_Value(X), m_ConstantInt(C1)),
20 //                      m_And(m_Value(Y), m_ConstantInt(C2))))) {
21 //    ... Pattern is matched and variables are bound ...
22 //  }
23 //
24 // This is primarily useful to things like the instruction combiner, but can
25 // also be useful for static analysis tools or code generators.
26 //
27 //===----------------------------------------------------------------------===//
28
29 #ifndef LLVM_SUPPORT_PATTERNMATCH_H
30 #define LLVM_SUPPORT_PATTERNMATCH_H
31
32 #include "llvm/Constants.h"
33 #include "llvm/Instructions.h"
34
35 namespace llvm {
36 namespace PatternMatch {
37
38 template<typename Val, typename Pattern>
39 bool match(Val *V, const Pattern &P) {
40   return const_cast<Pattern&>(P).match(V);
41 }
42
43 template<typename Class>
44 struct leaf_ty {
45   template<typename ITy>
46   bool match(ITy *V) { return isa<Class>(V); }
47 };
48
49 /// m_Value() - Match an arbitrary value and ignore it.
50 inline leaf_ty<Value> m_Value() { return leaf_ty<Value>(); }
51 /// m_ConstantInt() - Match an arbitrary ConstantInt and ignore it.
52 inline leaf_ty<ConstantInt> m_ConstantInt() { return leaf_ty<ConstantInt>(); }
53
54 template<int64_t Val>
55 struct constantint_ty {
56   template<typename ITy>
57   bool match(ITy *V) {
58     if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
59       const APInt &CIV = CI->getValue();
60       if (Val >= 0)
61         return CIV == static_cast<uint64_t>(Val);
62       // If Val is negative, and CI is shorter than it, truncate to the right
63       // number of bits.  If it is larger, then we have to sign extend.  Just
64       // compare their negated values.
65       return -CIV == -Val;
66     }
67     return false;
68   }
69 };
70
71 /// m_ConstantInt(int64_t) - Match a ConstantInt with a specific value
72 /// and ignore it.
73 template<int64_t Val>
74 inline constantint_ty<Val> m_ConstantInt() {
75   return constantint_ty<Val>();
76 }
77
78 struct zero_ty {
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.
88 inline zero_ty m_Zero() { return zero_ty(); }
89
90 struct one_ty {
91   template<typename ITy>
92   bool match(ITy *V) {
93     if (const ConstantInt *C = dyn_cast<ConstantInt>(V))
94       return C->isOne();
95     return false;
96   }
97 };
98
99 /// m_One() - Match a an integer 1.
100 inline one_ty m_One() { return one_ty(); }
101   
102
103 template<typename Class>
104 struct bind_ty {
105   Class *&VR;
106   bind_ty(Class *&V) : VR(V) {}
107
108   template<typename ITy>
109   bool match(ITy *V) {
110     if (Class *CV = dyn_cast<Class>(V)) {
111       VR = CV;
112       return true;
113     }
114     return false;
115   }
116 };
117
118 /// m_Value - Match a value, capturing it if we match.
119 inline bind_ty<Value> m_Value(Value *&V) { return V; }
120
121 /// m_ConstantInt - Match a ConstantInt, capturing the value if we match.
122 inline bind_ty<ConstantInt> m_ConstantInt(ConstantInt *&CI) { return CI; }
123
124 /// specificval_ty - Match a specified Value*.
125 struct specificval_ty {
126   const Value *Val;
127   specificval_ty(const Value *V) : Val(V) {}
128
129   template<typename ITy>
130   bool match(ITy *V) {
131     return V == Val;
132   }
133 };
134
135 /// m_Specific - Match if we have a specific specified value.
136 inline specificval_ty m_Specific(const Value *V) { return V; }
137
138
139 //===----------------------------------------------------------------------===//
140 // Matchers for specific binary operators.
141 //
142
143 template<typename LHS_t, typename RHS_t,
144          unsigned Opcode, typename ConcreteTy = BinaryOperator>
145 struct BinaryOp_match {
146   LHS_t L;
147   RHS_t R;
148
149   BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
150
151   template<typename OpTy>
152   bool match(OpTy *V) {
153     if (V->getValueID() == Value::InstructionVal + Opcode) {
154       ConcreteTy *I = cast<ConcreteTy>(V);
155       return I->getOpcode() == Opcode && L.match(I->getOperand(0)) &&
156              R.match(I->getOperand(1));
157     }
158     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
159       return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
160              R.match(CE->getOperand(1));
161     return false;
162   }
163 };
164
165 template<typename LHS, typename RHS>
166 inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L,
167                                                         const RHS &R) {
168   return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);
169 }
170
171 template<typename LHS, typename RHS>
172 inline BinaryOp_match<LHS, RHS, Instruction::FAdd> m_FAdd(const LHS &L,
173                                                           const RHS &R) {
174   return BinaryOp_match<LHS, RHS, Instruction::FAdd>(L, R);
175 }
176
177 template<typename LHS, typename RHS>
178 inline BinaryOp_match<LHS, RHS, Instruction::Sub> m_Sub(const LHS &L,
179                                                         const RHS &R) {
180   return BinaryOp_match<LHS, RHS, Instruction::Sub>(L, R);
181 }
182
183 template<typename LHS, typename RHS>
184 inline BinaryOp_match<LHS, RHS, Instruction::FSub> m_FSub(const LHS &L,
185                                                           const RHS &R) {
186   return BinaryOp_match<LHS, RHS, Instruction::FSub>(L, R);
187 }
188
189 template<typename LHS, typename RHS>
190 inline BinaryOp_match<LHS, RHS, Instruction::Mul> m_Mul(const LHS &L,
191                                                         const RHS &R) {
192   return BinaryOp_match<LHS, RHS, Instruction::Mul>(L, R);
193 }
194
195 template<typename LHS, typename RHS>
196 inline BinaryOp_match<LHS, RHS, Instruction::FMul> m_FMul(const LHS &L,
197                                                           const RHS &R) {
198   return BinaryOp_match<LHS, RHS, Instruction::FMul>(L, R);
199 }
200
201 template<typename LHS, typename RHS>
202 inline BinaryOp_match<LHS, RHS, Instruction::UDiv> m_UDiv(const LHS &L,
203                                                         const RHS &R) {
204   return BinaryOp_match<LHS, RHS, Instruction::UDiv>(L, R);
205 }
206
207 template<typename LHS, typename RHS>
208 inline BinaryOp_match<LHS, RHS, Instruction::SDiv> m_SDiv(const LHS &L,
209                                                         const RHS &R) {
210   return BinaryOp_match<LHS, RHS, Instruction::SDiv>(L, R);
211 }
212
213 template<typename LHS, typename RHS>
214 inline BinaryOp_match<LHS, RHS, Instruction::FDiv> m_FDiv(const LHS &L,
215                                                         const RHS &R) {
216   return BinaryOp_match<LHS, RHS, Instruction::FDiv>(L, R);
217 }
218
219 template<typename LHS, typename RHS>
220 inline BinaryOp_match<LHS, RHS, Instruction::URem> m_URem(const LHS &L,
221                                                           const RHS &R) {
222   return BinaryOp_match<LHS, RHS, Instruction::URem>(L, R);
223 }
224
225 template<typename LHS, typename RHS>
226 inline BinaryOp_match<LHS, RHS, Instruction::SRem> m_SRem(const LHS &L,
227                                                           const RHS &R) {
228   return BinaryOp_match<LHS, RHS, Instruction::SRem>(L, R);
229 }
230
231 template<typename LHS, typename RHS>
232 inline BinaryOp_match<LHS, RHS, Instruction::FRem> m_FRem(const LHS &L,
233                                                         const RHS &R) {
234   return BinaryOp_match<LHS, RHS, Instruction::FRem>(L, R);
235 }
236
237 template<typename LHS, typename RHS>
238 inline BinaryOp_match<LHS, RHS, Instruction::And> m_And(const LHS &L,
239                                                         const RHS &R) {
240   return BinaryOp_match<LHS, RHS, Instruction::And>(L, R);
241 }
242
243 template<typename LHS, typename RHS>
244 inline BinaryOp_match<LHS, RHS, Instruction::Or> m_Or(const LHS &L,
245                                                       const RHS &R) {
246   return BinaryOp_match<LHS, RHS, Instruction::Or>(L, R);
247 }
248
249 template<typename LHS, typename RHS>
250 inline BinaryOp_match<LHS, RHS, Instruction::Xor> m_Xor(const LHS &L,
251                                                         const RHS &R) {
252   return BinaryOp_match<LHS, RHS, Instruction::Xor>(L, R);
253 }
254
255 template<typename LHS, typename RHS>
256 inline BinaryOp_match<LHS, RHS, Instruction::Shl> m_Shl(const LHS &L,
257                                                         const RHS &R) {
258   return BinaryOp_match<LHS, RHS, Instruction::Shl>(L, R);
259 }
260
261 template<typename LHS, typename RHS>
262 inline BinaryOp_match<LHS, RHS, Instruction::LShr> m_LShr(const LHS &L,
263                                                           const RHS &R) {
264   return BinaryOp_match<LHS, RHS, Instruction::LShr>(L, R);
265 }
266
267 template<typename LHS, typename RHS>
268 inline BinaryOp_match<LHS, RHS, Instruction::AShr> m_AShr(const LHS &L,
269                                                           const RHS &R) {
270   return BinaryOp_match<LHS, RHS, Instruction::AShr>(L, R);
271 }
272
273 //===----------------------------------------------------------------------===//
274 // Matchers for either AShr or LShr .. for convenience
275 //
276 template<typename LHS_t, typename RHS_t, typename ConcreteTy = BinaryOperator>
277 struct Shr_match {
278   LHS_t L;
279   RHS_t R;
280
281   Shr_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
282
283   template<typename OpTy>
284   bool match(OpTy *V) {
285     if (V->getValueID() == Value::InstructionVal + Instruction::LShr ||
286         V->getValueID() == Value::InstructionVal + Instruction::AShr) {
287       ConcreteTy *I = cast<ConcreteTy>(V);
288       return (I->getOpcode() == Instruction::AShr ||
289               I->getOpcode() == Instruction::LShr) &&
290              L.match(I->getOperand(0)) &&
291              R.match(I->getOperand(1));
292     }
293     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
294       return (CE->getOpcode() == Instruction::LShr ||
295               CE->getOpcode() == Instruction::AShr) &&
296              L.match(CE->getOperand(0)) &&
297              R.match(CE->getOperand(1));
298     return false;
299   }
300 };
301
302 template<typename LHS, typename RHS>
303 inline Shr_match<LHS, RHS> m_Shr(const LHS &L, const RHS &R) {
304   return Shr_match<LHS, RHS>(L, R);
305 }
306
307 //===----------------------------------------------------------------------===//
308 // Matchers for binary classes
309 //
310
311 template<typename LHS_t, typename RHS_t, typename Class, typename OpcType>
312 struct BinaryOpClass_match {
313   OpcType *Opcode;
314   LHS_t L;
315   RHS_t R;
316
317   BinaryOpClass_match(OpcType &Op, const LHS_t &LHS,
318                       const RHS_t &RHS)
319     : Opcode(&Op), L(LHS), R(RHS) {}
320   BinaryOpClass_match(const LHS_t &LHS, const RHS_t &RHS)
321     : Opcode(0), L(LHS), R(RHS) {}
322
323   template<typename OpTy>
324   bool match(OpTy *V) {
325     if (Class *I = dyn_cast<Class>(V))
326       if (L.match(I->getOperand(0)) &&
327           R.match(I->getOperand(1))) {
328         if (Opcode)
329           *Opcode = I->getOpcode();
330         return true;
331       }
332 #if 0  // Doesn't handle constantexprs yet!
333     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
334       return CE->getOpcode() == Opcode && L.match(CE->getOperand(0)) &&
335              R.match(CE->getOperand(1));
336 #endif
337     return false;
338   }
339 };
340
341 template<typename LHS, typename RHS>
342 inline BinaryOpClass_match<LHS, RHS, BinaryOperator, Instruction::BinaryOps>
343 m_Shift(Instruction::BinaryOps &Op, const LHS &L, const RHS &R) {
344   return BinaryOpClass_match<LHS, RHS,
345                              BinaryOperator, Instruction::BinaryOps>(Op, L, R);
346 }
347
348 template<typename LHS, typename RHS>
349 inline BinaryOpClass_match<LHS, RHS, BinaryOperator, Instruction::BinaryOps>
350 m_Shift(const LHS &L, const RHS &R) {
351   return BinaryOpClass_match<LHS, RHS,
352                              BinaryOperator, Instruction::BinaryOps>(L, R);
353 }
354
355 //===----------------------------------------------------------------------===//
356 // Matchers for CmpInst classes
357 //
358
359 template<typename LHS_t, typename RHS_t, typename Class, typename PredicateTy>
360 struct CmpClass_match {
361   PredicateTy &Predicate;
362   LHS_t L;
363   RHS_t R;
364
365   CmpClass_match(PredicateTy &Pred, const LHS_t &LHS,
366                  const RHS_t &RHS)
367     : Predicate(Pred), L(LHS), R(RHS) {}
368
369   template<typename OpTy>
370   bool match(OpTy *V) {
371     if (Class *I = dyn_cast<Class>(V))
372       if (L.match(I->getOperand(0)) &&
373           R.match(I->getOperand(1))) {
374         Predicate = I->getPredicate();
375         return true;
376       }
377     return false;
378   }
379 };
380
381 template<typename LHS, typename RHS>
382 inline CmpClass_match<LHS, RHS, ICmpInst, ICmpInst::Predicate>
383 m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
384   return CmpClass_match<LHS, RHS,
385                         ICmpInst, ICmpInst::Predicate>(Pred, L, R);
386 }
387
388 template<typename LHS, typename RHS>
389 inline CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>
390 m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
391   return CmpClass_match<LHS, RHS,
392                         FCmpInst, FCmpInst::Predicate>(Pred, L, R);
393 }
394
395 //===----------------------------------------------------------------------===//
396 // Matchers for SelectInst classes
397 //
398
399 template<typename Cond_t, typename LHS_t, typename RHS_t>
400 struct SelectClass_match {
401   Cond_t C;
402   LHS_t L;
403   RHS_t R;
404
405   SelectClass_match(const Cond_t &Cond, const LHS_t &LHS,
406                     const RHS_t &RHS)
407     : C(Cond), L(LHS), R(RHS) {}
408
409   template<typename OpTy>
410   bool match(OpTy *V) {
411     if (SelectInst *I = dyn_cast<SelectInst>(V))
412       return C.match(I->getOperand(0)) &&
413              L.match(I->getOperand(1)) &&
414              R.match(I->getOperand(2));
415     return false;
416   }
417 };
418
419 template<typename Cond, typename LHS, typename RHS>
420 inline SelectClass_match<Cond, LHS, RHS>
421 m_Select(const Cond &C, const LHS &L, const RHS &R) {
422   return SelectClass_match<Cond, LHS, RHS>(C, L, R);
423 }
424
425 /// m_SelectCst - This matches a select of two constants, e.g.:
426 ///    m_SelectCst<-1, 0>(m_Value(V))
427 template<int64_t L, int64_t R, typename Cond>
428 inline SelectClass_match<Cond, constantint_ty<L>, constantint_ty<R> >
429 m_SelectCst(const Cond &C) {
430   return SelectClass_match<Cond, constantint_ty<L>,
431                            constantint_ty<R> >(C, m_ConstantInt<L>(),
432                                            m_ConstantInt<R>());
433 }
434
435
436 //===----------------------------------------------------------------------===//
437 // Matchers for CastInst classes
438 //
439
440 template<typename Op_t, unsigned Opcode>
441 struct CastClass_match {
442   Op_t Op;
443
444   CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {}
445
446   template<typename OpTy>
447   bool match(OpTy *V) {
448     if (CastInst *I = dyn_cast<CastInst>(V))
449       return I->getOpcode() == Opcode && Op.match(I->getOperand(0));
450     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
451       return CE->getOpcode() == Opcode && Op.match(CE->getOperand(0));
452     return false;
453   }
454 };
455
456 /// m_PtrToInt
457 template<typename OpTy>
458 inline CastClass_match<OpTy, Instruction::PtrToInt>
459 m_PtrToInt(const OpTy &Op) {
460   return CastClass_match<OpTy, Instruction::PtrToInt>(Op);
461 }
462
463 /// m_Trunc
464 template<typename OpTy>
465 inline CastClass_match<OpTy, Instruction::Trunc>
466 m_Trunc(const OpTy &Op) {
467   return CastClass_match<OpTy, Instruction::Trunc>(Op);
468 }
469
470 /// m_SExt
471 template<typename OpTy>
472 inline CastClass_match<OpTy, Instruction::SExt>
473 m_SExt(const OpTy &Op) {
474   return CastClass_match<OpTy, Instruction::SExt>(Op);
475 }
476
477 /// m_ZExt
478 template<typename OpTy>
479 inline CastClass_match<OpTy, Instruction::ZExt>
480 m_ZExt(const OpTy &Op) {
481   return CastClass_match<OpTy, Instruction::ZExt>(Op);
482 }
483   
484
485 //===----------------------------------------------------------------------===//
486 // Matchers for unary operators
487 //
488
489 template<typename LHS_t>
490 struct not_match {
491   LHS_t L;
492
493   not_match(const LHS_t &LHS) : L(LHS) {}
494
495   template<typename OpTy>
496   bool match(OpTy *V) {
497     if (Instruction *I = dyn_cast<Instruction>(V))
498       if (I->getOpcode() == Instruction::Xor)
499         return matchIfNot(I->getOperand(0), I->getOperand(1));
500     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
501       if (CE->getOpcode() == Instruction::Xor)
502         return matchIfNot(CE->getOperand(0), CE->getOperand(1));
503     if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
504       return L.match(ConstantExpr::getNot(CI));
505     return false;
506   }
507 private:
508   bool matchIfNot(Value *LHS, Value *RHS) {
509     if (ConstantInt *CI = dyn_cast<ConstantInt>(RHS))
510       return CI->isAllOnesValue() && L.match(LHS);
511     if (ConstantInt *CI = dyn_cast<ConstantInt>(LHS))
512       return CI->isAllOnesValue() && L.match(RHS);
513     if (ConstantVector *CV = dyn_cast<ConstantVector>(RHS))
514       return CV->isAllOnesValue() && L.match(LHS);
515     if (ConstantVector *CV = dyn_cast<ConstantVector>(LHS))
516       return CV->isAllOnesValue() && L.match(RHS);
517     return false;
518   }
519 };
520
521 template<typename LHS>
522 inline not_match<LHS> m_Not(const LHS &L) { return L; }
523
524
525 template<typename LHS_t>
526 struct neg_match {
527   LHS_t L;
528
529   neg_match(const LHS_t &LHS) : L(LHS) {}
530
531   template<typename OpTy>
532   bool match(OpTy *V) {
533     if (Instruction *I = dyn_cast<Instruction>(V))
534       if (I->getOpcode() == Instruction::Sub)
535         return matchIfNeg(I->getOperand(0), I->getOperand(1));
536     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
537       if (CE->getOpcode() == Instruction::Sub)
538         return matchIfNeg(CE->getOperand(0), CE->getOperand(1));
539     if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
540       return L.match(ConstantExpr::getNeg(CI));
541     return false;
542   }
543 private:
544   bool matchIfNeg(Value *LHS, Value *RHS) {
545     return LHS == ConstantFP::getZeroValueForNegation(LHS->getType()) &&
546            L.match(RHS);
547   }
548 };
549
550 template<typename LHS>
551 inline neg_match<LHS> m_Neg(const LHS &L) { return L; }
552
553
554 template<typename LHS_t>
555 struct fneg_match {
556   LHS_t L;
557
558   fneg_match(const LHS_t &LHS) : L(LHS) {}
559
560   template<typename OpTy>
561   bool match(OpTy *V) {
562     if (Instruction *I = dyn_cast<Instruction>(V))
563       if (I->getOpcode() == Instruction::FSub)
564         return matchIfFNeg(I->getOperand(0), I->getOperand(1));
565     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
566       if (CE->getOpcode() == Instruction::FSub)
567         return matchIfFNeg(CE->getOperand(0), CE->getOperand(1));
568     if (ConstantFP *CF = dyn_cast<ConstantFP>(V))
569       return L.match(ConstantExpr::getFNeg(CF));
570     return false;
571   }
572 private:
573   bool matchIfFNeg(Value *LHS, Value *RHS) {
574     return LHS == ConstantFP::getZeroValueForNegation(LHS->getType()) &&
575            L.match(RHS);
576   }
577 };
578
579 template<typename LHS>
580 inline fneg_match<LHS> m_FNeg(const LHS &L) { return L; }
581
582
583 //===----------------------------------------------------------------------===//
584 // Matchers for control flow
585 //
586
587 template<typename Cond_t>
588 struct brc_match {
589   Cond_t Cond;
590   BasicBlock *&T, *&F;
591   brc_match(const Cond_t &C, BasicBlock *&t, BasicBlock *&f)
592     : Cond(C), T(t), F(f) {
593   }
594
595   template<typename OpTy>
596   bool match(OpTy *V) {
597     if (BranchInst *BI = dyn_cast<BranchInst>(V))
598       if (BI->isConditional()) {
599         if (Cond.match(BI->getCondition())) {
600           T = BI->getSuccessor(0);
601           F = BI->getSuccessor(1);
602           return true;
603         }
604       }
605     return false;
606   }
607 };
608
609 template<typename Cond_t>
610 inline brc_match<Cond_t> m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F) {
611   return brc_match<Cond_t>(C, T, F);
612 }
613
614 } // end namespace PatternMatch
615 } // end namespace llvm
616
617 #endif