1 //===- VPlanPatternMatch.h - Match on VPValues and recipes ------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file provides a simple and efficient mechanism for performing general 10 // tree-based pattern matches on the VPlan values and recipes, based on 11 // LLVM's IR pattern matchers. 12 // 13 // Currently it provides generic matchers for unary and binary VPInstructions, 14 // and specialized matchers like m_Not, m_ActiveLaneMask, m_BranchOnCond, 15 // m_BranchOnCount to match specific VPInstructions. 16 // TODO: Add missing matchers for additional opcodes and recipes as needed. 17 // 18 //===----------------------------------------------------------------------===// 19 20 #ifndef LLVM_TRANSFORM_VECTORIZE_VPLANPATTERNMATCH_H 21 #define LLVM_TRANSFORM_VECTORIZE_VPLANPATTERNMATCH_H 22 23 #include "VPlan.h" 24 25 namespace llvm { 26 namespace VPlanPatternMatch { 27 28 template <typename Val, typename Pattern> bool match(Val *V, const Pattern &P) { 29 return P.match(V); 30 } 31 32 template <typename Pattern> bool match(VPUser *U, const Pattern &P) { 33 auto *R = dyn_cast<VPRecipeBase>(U); 34 return R && match(R, P); 35 } 36 37 template <typename Class> struct class_match { 38 template <typename ITy> bool match(ITy *V) const { return isa<Class>(V); } 39 }; 40 41 /// Match an arbitrary VPValue and ignore it. 42 inline class_match<VPValue> m_VPValue() { return class_match<VPValue>(); } 43 44 template <typename Class> struct bind_ty { 45 Class *&VR; 46 47 bind_ty(Class *&V) : VR(V) {} 48 49 template <typename ITy> bool match(ITy *V) const { 50 if (auto *CV = dyn_cast<Class>(V)) { 51 VR = CV; 52 return true; 53 } 54 return false; 55 } 56 }; 57 58 /// Match a specified VPValue. 59 struct specificval_ty { 60 const VPValue *Val; 61 62 specificval_ty(const VPValue *V) : Val(V) {} 63 64 bool match(VPValue *VPV) const { return VPV == Val; } 65 }; 66 67 inline specificval_ty m_Specific(const VPValue *VPV) { return VPV; } 68 69 /// Match a specified integer value or vector of all elements of that 70 /// value. \p BitWidth optionally specifies the bitwidth the matched constant 71 /// must have. If it is 0, the matched constant can have any bitwidth. 72 template <unsigned BitWidth = 0> struct specific_intval { 73 APInt Val; 74 75 specific_intval(APInt V) : Val(std::move(V)) {} 76 77 bool match(VPValue *VPV) const { 78 if (!VPV->isLiveIn()) 79 return false; 80 Value *V = VPV->getLiveInIRValue(); 81 if (!V) 82 return false; 83 const auto *CI = dyn_cast<ConstantInt>(V); 84 if (!CI && V->getType()->isVectorTy()) 85 if (const auto *C = dyn_cast<Constant>(V)) 86 CI = dyn_cast_or_null<ConstantInt>( 87 C->getSplatValue(/*AllowPoison=*/false)); 88 if (!CI) 89 return false; 90 91 if (BitWidth != 0 && CI->getBitWidth() != BitWidth) 92 return false; 93 return APInt::isSameValue(CI->getValue(), Val); 94 } 95 }; 96 97 inline specific_intval<0> m_SpecificInt(uint64_t V) { 98 return specific_intval<0>(APInt(64, V)); 99 } 100 101 inline specific_intval<1> m_False() { return specific_intval<1>(APInt(64, 0)); } 102 103 inline specific_intval<1> m_True() { return specific_intval<1>(APInt(64, 1)); } 104 105 /// Matching combinators 106 template <typename LTy, typename RTy> struct match_combine_or { 107 LTy L; 108 RTy R; 109 110 match_combine_or(const LTy &Left, const RTy &Right) : L(Left), R(Right) {} 111 112 template <typename ITy> bool match(ITy *V) const { 113 if (L.match(V)) 114 return true; 115 if (R.match(V)) 116 return true; 117 return false; 118 } 119 }; 120 121 template <typename LTy, typename RTy> 122 inline match_combine_or<LTy, RTy> m_CombineOr(const LTy &L, const RTy &R) { 123 return match_combine_or<LTy, RTy>(L, R); 124 } 125 126 /// Match a VPValue, capturing it if we match. 127 inline bind_ty<VPValue> m_VPValue(VPValue *&V) { return V; } 128 129 namespace detail { 130 131 /// A helper to match an opcode against multiple recipe types. 132 template <unsigned Opcode, typename...> struct MatchRecipeAndOpcode {}; 133 134 template <unsigned Opcode, typename RecipeTy> 135 struct MatchRecipeAndOpcode<Opcode, RecipeTy> { 136 static bool match(const VPRecipeBase *R) { 137 auto *DefR = dyn_cast<RecipeTy>(R); 138 // Check for recipes that do not have opcodes. 139 if constexpr (std::is_same<RecipeTy, VPScalarIVStepsRecipe>::value || 140 std::is_same<RecipeTy, VPCanonicalIVPHIRecipe>::value || 141 std::is_same<RecipeTy, VPWidenSelectRecipe>::value || 142 std::is_same<RecipeTy, VPDerivedIVRecipe>::value) 143 return DefR; 144 else 145 return DefR && DefR->getOpcode() == Opcode; 146 } 147 }; 148 149 template <unsigned Opcode, typename RecipeTy, typename... RecipeTys> 150 struct MatchRecipeAndOpcode<Opcode, RecipeTy, RecipeTys...> { 151 static bool match(const VPRecipeBase *R) { 152 return MatchRecipeAndOpcode<Opcode, RecipeTy>::match(R) || 153 MatchRecipeAndOpcode<Opcode, RecipeTys...>::match(R); 154 } 155 }; 156 template <typename TupleTy, typename Fn, std::size_t... Is> 157 bool CheckTupleElements(const TupleTy &Ops, Fn P, std::index_sequence<Is...>) { 158 return (P(std::get<Is>(Ops), Is) && ...); 159 } 160 161 /// Helper to check if predicate \p P holds on all tuple elements in \p Ops 162 template <typename TupleTy, typename Fn> 163 bool all_of_tuple_elements(const TupleTy &Ops, Fn P) { 164 return CheckTupleElements( 165 Ops, P, std::make_index_sequence<std::tuple_size<TupleTy>::value>{}); 166 } 167 } // namespace detail 168 169 template <typename Ops_t, unsigned Opcode, bool Commutative, 170 typename... RecipeTys> 171 struct Recipe_match { 172 Ops_t Ops; 173 174 Recipe_match() : Ops() { 175 static_assert(std::tuple_size<Ops_t>::value == 0 && 176 "constructor can only be used with zero operands"); 177 } 178 Recipe_match(Ops_t Ops) : Ops(Ops) {} 179 template <typename A_t, typename B_t> 180 Recipe_match(A_t A, B_t B) : Ops({A, B}) { 181 static_assert(std::tuple_size<Ops_t>::value == 2 && 182 "constructor can only be used for binary matcher"); 183 } 184 185 bool match(const VPValue *V) const { 186 auto *DefR = V->getDefiningRecipe(); 187 return DefR && match(DefR); 188 } 189 190 bool match(const VPSingleDefRecipe *R) const { 191 return match(static_cast<const VPRecipeBase *>(R)); 192 } 193 194 bool match(const VPRecipeBase *R) const { 195 if (!detail::MatchRecipeAndOpcode<Opcode, RecipeTys...>::match(R)) 196 return false; 197 assert(R->getNumOperands() == std::tuple_size<Ops_t>::value && 198 "recipe with matched opcode the expected number of operands"); 199 200 if (detail::all_of_tuple_elements(Ops, [R](auto Op, unsigned Idx) { 201 return Op.match(R->getOperand(Idx)); 202 })) 203 return true; 204 205 return Commutative && 206 detail::all_of_tuple_elements(Ops, [R](auto Op, unsigned Idx) { 207 return Op.match(R->getOperand(R->getNumOperands() - Idx - 1)); 208 }); 209 } 210 }; 211 212 template <typename Op0_t, unsigned Opcode, typename... RecipeTys> 213 using UnaryRecipe_match = 214 Recipe_match<std::tuple<Op0_t>, Opcode, false, RecipeTys...>; 215 216 template <typename Op0_t, unsigned Opcode> 217 using UnaryVPInstruction_match = 218 UnaryRecipe_match<Op0_t, Opcode, VPInstruction>; 219 220 template <typename Op0_t, unsigned Opcode> 221 using AllUnaryRecipe_match = 222 UnaryRecipe_match<Op0_t, Opcode, VPWidenRecipe, VPReplicateRecipe, 223 VPWidenCastRecipe, VPInstruction>; 224 225 template <typename Op0_t, typename Op1_t, unsigned Opcode, bool Commutative, 226 typename... RecipeTys> 227 using BinaryRecipe_match = 228 Recipe_match<std::tuple<Op0_t, Op1_t>, Opcode, Commutative, RecipeTys...>; 229 230 template <typename Op0_t, typename Op1_t, unsigned Opcode> 231 using BinaryVPInstruction_match = 232 BinaryRecipe_match<Op0_t, Op1_t, Opcode, /*Commutative*/ false, 233 VPInstruction>; 234 235 template <typename Op0_t, typename Op1_t, unsigned Opcode, 236 bool Commutative = false> 237 using AllBinaryRecipe_match = 238 BinaryRecipe_match<Op0_t, Op1_t, Opcode, Commutative, VPWidenRecipe, 239 VPReplicateRecipe, VPWidenCastRecipe, VPInstruction>; 240 241 template <unsigned Opcode, typename Op0_t> 242 inline UnaryVPInstruction_match<Op0_t, Opcode> 243 m_VPInstruction(const Op0_t &Op0) { 244 return UnaryVPInstruction_match<Op0_t, Opcode>(Op0); 245 } 246 247 template <unsigned Opcode, typename Op0_t, typename Op1_t> 248 inline BinaryVPInstruction_match<Op0_t, Op1_t, Opcode> 249 m_VPInstruction(const Op0_t &Op0, const Op1_t &Op1) { 250 return BinaryVPInstruction_match<Op0_t, Op1_t, Opcode>(Op0, Op1); 251 } 252 253 template <typename Op0_t> 254 inline UnaryVPInstruction_match<Op0_t, VPInstruction::Not> 255 m_Not(const Op0_t &Op0) { 256 return m_VPInstruction<VPInstruction::Not>(Op0); 257 } 258 259 template <typename Op0_t> 260 inline UnaryVPInstruction_match<Op0_t, VPInstruction::BranchOnCond> 261 m_BranchOnCond(const Op0_t &Op0) { 262 return m_VPInstruction<VPInstruction::BranchOnCond>(Op0); 263 } 264 265 template <typename Op0_t, typename Op1_t> 266 inline BinaryVPInstruction_match<Op0_t, Op1_t, VPInstruction::ActiveLaneMask> 267 m_ActiveLaneMask(const Op0_t &Op0, const Op1_t &Op1) { 268 return m_VPInstruction<VPInstruction::ActiveLaneMask>(Op0, Op1); 269 } 270 271 template <typename Op0_t, typename Op1_t> 272 inline BinaryVPInstruction_match<Op0_t, Op1_t, VPInstruction::BranchOnCount> 273 m_BranchOnCount(const Op0_t &Op0, const Op1_t &Op1) { 274 return m_VPInstruction<VPInstruction::BranchOnCount>(Op0, Op1); 275 } 276 277 template <unsigned Opcode, typename Op0_t> 278 inline AllUnaryRecipe_match<Op0_t, Opcode> m_Unary(const Op0_t &Op0) { 279 return AllUnaryRecipe_match<Op0_t, Opcode>(Op0); 280 } 281 282 template <typename Op0_t> 283 inline AllUnaryRecipe_match<Op0_t, Instruction::Trunc> 284 m_Trunc(const Op0_t &Op0) { 285 return m_Unary<Instruction::Trunc, Op0_t>(Op0); 286 } 287 288 template <typename Op0_t> 289 inline AllUnaryRecipe_match<Op0_t, Instruction::ZExt> m_ZExt(const Op0_t &Op0) { 290 return m_Unary<Instruction::ZExt, Op0_t>(Op0); 291 } 292 293 template <typename Op0_t> 294 inline AllUnaryRecipe_match<Op0_t, Instruction::SExt> m_SExt(const Op0_t &Op0) { 295 return m_Unary<Instruction::SExt, Op0_t>(Op0); 296 } 297 298 template <typename Op0_t> 299 inline match_combine_or<AllUnaryRecipe_match<Op0_t, Instruction::ZExt>, 300 AllUnaryRecipe_match<Op0_t, Instruction::SExt>> 301 m_ZExtOrSExt(const Op0_t &Op0) { 302 return m_CombineOr(m_ZExt(Op0), m_SExt(Op0)); 303 } 304 305 template <unsigned Opcode, typename Op0_t, typename Op1_t, 306 bool Commutative = false> 307 inline AllBinaryRecipe_match<Op0_t, Op1_t, Opcode, Commutative> 308 m_Binary(const Op0_t &Op0, const Op1_t &Op1) { 309 return AllBinaryRecipe_match<Op0_t, Op1_t, Opcode, Commutative>(Op0, Op1); 310 } 311 312 template <typename Op0_t, typename Op1_t> 313 inline AllBinaryRecipe_match<Op0_t, Op1_t, Instruction::Mul> 314 m_Mul(const Op0_t &Op0, const Op1_t &Op1) { 315 return m_Binary<Instruction::Mul, Op0_t, Op1_t>(Op0, Op1); 316 } 317 318 template <typename Op0_t, typename Op1_t> 319 inline AllBinaryRecipe_match<Op0_t, Op1_t, Instruction::Mul, 320 /* Commutative =*/true> 321 m_c_Mul(const Op0_t &Op0, const Op1_t &Op1) { 322 return m_Binary<Instruction::Mul, Op0_t, Op1_t, true>(Op0, Op1); 323 } 324 325 /// Match a binary OR operation. Note that while conceptually the operands can 326 /// be matched commutatively, \p Commutative defaults to false in line with the 327 /// IR-based pattern matching infrastructure. Use m_c_BinaryOr for a commutative 328 /// version of the matcher. 329 template <typename Op0_t, typename Op1_t, bool Commutative = false> 330 inline AllBinaryRecipe_match<Op0_t, Op1_t, Instruction::Or, Commutative> 331 m_BinaryOr(const Op0_t &Op0, const Op1_t &Op1) { 332 return m_Binary<Instruction::Or, Op0_t, Op1_t, Commutative>(Op0, Op1); 333 } 334 335 template <typename Op0_t, typename Op1_t> 336 inline AllBinaryRecipe_match<Op0_t, Op1_t, Instruction::Or, 337 /*Commutative*/ true> 338 m_c_BinaryOr(const Op0_t &Op0, const Op1_t &Op1) { 339 return m_BinaryOr<Op0_t, Op1_t, /*Commutative*/ true>(Op0, Op1); 340 } 341 342 template <typename Op0_t, typename Op1_t, typename Op2_t, unsigned Opcode> 343 using AllTernaryRecipe_match = 344 Recipe_match<std::tuple<Op0_t, Op1_t, Op2_t>, Opcode, false, 345 VPReplicateRecipe, VPInstruction, VPWidenSelectRecipe>; 346 347 template <typename Op0_t, typename Op1_t, typename Op2_t> 348 inline AllTernaryRecipe_match<Op0_t, Op1_t, Op2_t, Instruction::Select> 349 m_Select(const Op0_t &Op0, const Op1_t &Op1, const Op2_t &Op2) { 350 return AllTernaryRecipe_match<Op0_t, Op1_t, Op2_t, Instruction::Select>( 351 {Op0, Op1, Op2}); 352 } 353 354 template <typename Op0_t, typename Op1_t> 355 inline match_combine_or< 356 BinaryVPInstruction_match<Op0_t, Op1_t, VPInstruction::LogicalAnd>, 357 AllTernaryRecipe_match<Op0_t, Op1_t, specific_intval<1>, 358 Instruction::Select>> 359 m_LogicalAnd(const Op0_t &Op0, const Op1_t &Op1) { 360 return m_CombineOr( 361 m_VPInstruction<VPInstruction::LogicalAnd, Op0_t, Op1_t>(Op0, Op1), 362 m_Select(Op0, Op1, m_False())); 363 } 364 365 template <typename Op0_t, typename Op1_t> 366 inline AllTernaryRecipe_match<Op0_t, specific_intval<1>, Op1_t, 367 Instruction::Select> 368 m_LogicalOr(const Op0_t &Op0, const Op1_t &Op1) { 369 return m_Select(Op0, m_True(), Op1); 370 } 371 372 using VPCanonicalIVPHI_match = 373 Recipe_match<std::tuple<>, 0, false, VPCanonicalIVPHIRecipe>; 374 375 inline VPCanonicalIVPHI_match m_CanonicalIV() { 376 return VPCanonicalIVPHI_match(); 377 } 378 379 template <typename Op0_t, typename Op1_t> 380 using VPScalarIVSteps_match = 381 Recipe_match<std::tuple<Op0_t, Op1_t>, 0, false, VPScalarIVStepsRecipe>; 382 383 template <typename Op0_t, typename Op1_t> 384 inline VPScalarIVSteps_match<Op0_t, Op1_t> m_ScalarIVSteps(const Op0_t &Op0, 385 const Op1_t &Op1) { 386 return VPScalarIVSteps_match<Op0_t, Op1_t>(Op0, Op1); 387 } 388 389 template <typename Op0_t, typename Op1_t, typename Op2_t> 390 using VPDerivedIV_match = 391 Recipe_match<std::tuple<Op0_t, Op1_t, Op2_t>, 0, false, VPDerivedIVRecipe>; 392 393 template <typename Op0_t, typename Op1_t, typename Op2_t> 394 inline VPDerivedIV_match<Op0_t, Op1_t, Op2_t> 395 m_DerivedIV(const Op0_t &Op0, const Op1_t &Op1, const Op2_t &Op2) { 396 return VPDerivedIV_match<Op0_t, Op1_t, Op2_t>({Op0, Op1, Op2}); 397 } 398 399 } // namespace VPlanPatternMatch 400 } // namespace llvm 401 402 #endif 403