llvm/Analysis/ScalarEvolutionPatternMatch.h

0001 //===----------------------------------------------------------------------===//
0002 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0003 // See https://llvm.org/LICENSE.txt for license information.
0004 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0005 //
0006 //===----------------------------------------------------------------------===//
0007 //
0008 // This file provides a simple and efficient mechanism for performing general
0009 // tree-based pattern matches on SCEVs, based on LLVM's IR pattern matchers.
0010 //
0011 //===----------------------------------------------------------------------===//
0012
0013 #ifndef LLVM_ANALYSIS_SCALAREVOLUTIONPATTERNMATCH_H
0014 #define LLVM_ANALYSIS_SCALAREVOLUTIONPATTERNMATCH_H
0015
0016 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
0017
0018 namespace llvm {
0019 namespace SCEVPatternMatch {
0020
0021 template <typename Val, typename Pattern>
0022 bool match(const SCEV *S, const Pattern &P) {
0023   return P.match(S);
0024 }
0025
0026 template <typename Predicate> struct cst_pred_ty : public Predicate {
0027   bool match(const SCEV *S) {
0028     assert((isa<SCEVCouldNotCompute>(S) || !S->getType()->isVectorTy()) &&
0029            "no vector types expected from SCEVs");
0030     auto *C = dyn_cast<SCEVConstant>(S);
0031     return C && this->isValue(C->getAPInt());
0032   }
0033 };
0034
0035 struct is_zero {
0036   bool isValue(const APInt &C) { return C.isZero(); }
0037 };
0038 /// Match an integer 0.
0039 inline cst_pred_ty<is_zero> m_scev_Zero() { return cst_pred_ty<is_zero>(); }
0040
0041 struct is_one {
0042   bool isValue(const APInt &C) { return C.isOne(); }
0043 };
0044 /// Match an integer 1.
0045 inline cst_pred_ty<is_one> m_scev_One() { return cst_pred_ty<is_one>(); }
0046
0047 struct is_all_ones {
0048   bool isValue(const APInt &C) { return C.isAllOnes(); }
0049 };
0050 /// Match an integer with all bits set.
0051 inline cst_pred_ty<is_all_ones> m_scev_AllOnes() {
0052   return cst_pred_ty<is_all_ones>();
0053 }
0054
0055 template <typename Class> struct class_match {
0056   template <typename ITy> bool match(ITy *V) const { return isa<Class>(V); }
0057 };
0058
0059 template <typename Class> struct bind_ty {
0060   Class *&VR;
0061
0062   bind_ty(Class *&V) : VR(V) {}
0063
0064   template <typename ITy> bool match(ITy *V) const {
0065     if (auto *CV = dyn_cast<Class>(V)) {
0066       VR = CV;
0067       return true;
0068     }
0069     return false;
0070   }
0071 };
0072
0073 /// Match a SCEV, capturing it if we match.
0074 inline bind_ty<const SCEV> m_SCEV(const SCEV *&V) { return V; }
0075 inline bind_ty<const SCEVConstant> m_SCEVConstant(const SCEVConstant *&V) {
0076   return V;
0077 }
0078 inline bind_ty<const SCEVUnknown> m_SCEVUnknown(const SCEVUnknown *&V) {
0079   return V;
0080 }
0081
0082 /// Match a specified const SCEV *.
0083 struct specificscev_ty {
0084   const SCEV *Expr;
0085
0086   specificscev_ty(const SCEV *Expr) : Expr(Expr) {}
0087
0088   template <typename ITy> bool match(ITy *S) { return S == Expr; }
0089 };
0090
0091 /// Match if we have a specific specified SCEV.
0092 inline specificscev_ty m_Specific(const SCEV *S) { return S; }
0093
0094 /// Match a unary SCEV.
0095 template <typename SCEVTy, typename Op0_t> struct SCEVUnaryExpr_match {
0096   Op0_t Op0;
0097
0098   SCEVUnaryExpr_match(Op0_t Op0) : Op0(Op0) {}
0099
0100   bool match(const SCEV *S) {
0101     auto *E = dyn_cast<SCEVTy>(S);
0102     return E && E->getNumOperands() == 1 && Op0.match(E->getOperand(0));
0103   }
0104 };
0105
0106 template <typename SCEVTy, typename Op0_t>
0107 inline SCEVUnaryExpr_match<SCEVTy, Op0_t> m_scev_Unary(const Op0_t &Op0) {
0108   return SCEVUnaryExpr_match<SCEVTy, Op0_t>(Op0);
0109 }
0110
0111 template <typename Op0_t>
0112 inline SCEVUnaryExpr_match<SCEVSignExtendExpr, Op0_t>
0113 m_scev_SExt(const Op0_t &Op0) {
0114   return m_scev_Unary<SCEVSignExtendExpr>(Op0);
0115 }
0116
0117 template <typename Op0_t>
0118 inline SCEVUnaryExpr_match<SCEVZeroExtendExpr, Op0_t>
0119 m_scev_ZExt(const Op0_t &Op0) {
0120   return m_scev_Unary<SCEVZeroExtendExpr>(Op0);
0121 }
0122
0123 /// Match a binary SCEV.
0124 template <typename SCEVTy, typename Op0_t, typename Op1_t>
0125 struct SCEVBinaryExpr_match {
0126   Op0_t Op0;
0127   Op1_t Op1;
0128
0129   SCEVBinaryExpr_match(Op0_t Op0, Op1_t Op1) : Op0(Op0), Op1(Op1) {}
0130
0131   bool match(const SCEV *S) {
0132     auto *E = dyn_cast<SCEVTy>(S);
0133     return E && E->getNumOperands() == 2 && Op0.match(E->getOperand(0)) &&
0134            Op1.match(E->getOperand(1));
0135   }
0136 };
0137
0138 template <typename SCEVTy, typename Op0_t, typename Op1_t>
0139 inline SCEVBinaryExpr_match<SCEVTy, Op0_t, Op1_t>
0140 m_scev_Binary(const Op0_t &Op0, const Op1_t &Op1) {
0141   return SCEVBinaryExpr_match<SCEVTy, Op0_t, Op1_t>(Op0, Op1);
0142 }
0143
0144 template <typename Op0_t, typename Op1_t>
0145 inline SCEVBinaryExpr_match<SCEVAddExpr, Op0_t, Op1_t>
0146 m_scev_Add(const Op0_t &Op0, const Op1_t &Op1) {
0147   return m_scev_Binary<SCEVAddExpr>(Op0, Op1);
0148 }
0149
0150 } // namespace SCEVPatternMatch
0151 } // namespace llvm
0152
0153 #endif