LLVM 20.0.0git
VPlanPatternMatch.h
Go to the documentation of this file.
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
25namespace llvm {
26namespace VPlanPatternMatch {
27
28template <typename Val, typename Pattern> bool match(Val *V, const Pattern &P) {
29 return P.match(V);
30}
31
32template <typename Pattern> bool match(VPUser *U, const Pattern &P) {
33 auto *R = dyn_cast<VPRecipeBase>(U);
34 return R && match(R, P);
35}
36
37template <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.
43
44template <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.
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
67inline 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.
72template <unsigned BitWidth = 0> struct specific_intval {
74
76
77 bool match(VPValue *VPV) const {
78 if (!VPV->isLiveIn())
79 return false;
80 Value *V = VPV->getLiveInIRValue();
81 const auto *CI = dyn_cast<ConstantInt>(V);
82 if (!CI && V->getType()->isVectorTy())
83 if (const auto *C = dyn_cast<Constant>(V))
84 CI = dyn_cast_or_null<ConstantInt>(
85 C->getSplatValue(/*AllowPoison=*/false));
86 if (!CI)
87 return false;
88
89 if (BitWidth != 0 && CI->getBitWidth() != BitWidth)
90 return false;
91 return APInt::isSameValue(CI->getValue(), Val);
92 }
93};
94
96 return specific_intval<0>(APInt(64, V));
97}
98
100
102
103/// Matching combinators
104template <typename LTy, typename RTy> struct match_combine_or {
105 LTy L;
106 RTy R;
107
108 match_combine_or(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
109
110 template <typename ITy> bool match(ITy *V) const {
111 if (L.match(V))
112 return true;
113 if (R.match(V))
114 return true;
115 return false;
116 }
117};
118
119template <typename LTy, typename RTy>
120inline match_combine_or<LTy, RTy> m_CombineOr(const LTy &L, const RTy &R) {
121 return match_combine_or<LTy, RTy>(L, R);
122}
123
124/// Match a VPValue, capturing it if we match.
125inline bind_ty<VPValue> m_VPValue(VPValue *&V) { return V; }
126
127namespace detail {
128
129/// A helper to match an opcode against multiple recipe types.
130template <unsigned Opcode, typename...> struct MatchRecipeAndOpcode {};
131
132template <unsigned Opcode, typename RecipeTy>
134 static bool match(const VPRecipeBase *R) {
135 auto *DefR = dyn_cast<RecipeTy>(R);
136 // Check for recipes that do not have opcodes.
137 if constexpr (std::is_same<RecipeTy, VPScalarIVStepsRecipe>::value ||
138 std::is_same<RecipeTy, VPCanonicalIVPHIRecipe>::value ||
139 std::is_same<RecipeTy, VPWidenSelectRecipe>::value)
140 return DefR;
141 else
142 return DefR && DefR->getOpcode() == Opcode;
143 }
144};
145
146template <unsigned Opcode, typename RecipeTy, typename... RecipeTys>
147struct MatchRecipeAndOpcode<Opcode, RecipeTy, RecipeTys...> {
148 static bool match(const VPRecipeBase *R) {
151 }
152};
153template <typename TupleTy, typename Fn, std::size_t... Is>
154bool CheckTupleElements(const TupleTy &Ops, Fn P, std::index_sequence<Is...>) {
155 return (P(std::get<Is>(Ops), Is) && ...);
156}
157
158/// Helper to check if predicate \p P holds on all tuple elements in \p Ops
159template <typename TupleTy, typename Fn>
160bool all_of_tuple_elements(const TupleTy &Ops, Fn P) {
161 return CheckTupleElements(
162 Ops, P, std::make_index_sequence<std::tuple_size<TupleTy>::value>{});
163}
164} // namespace detail
165
166template <typename Ops_t, unsigned Opcode, bool Commutative,
167 typename... RecipeTys>
169 Ops_t Ops;
170
172 static_assert(std::tuple_size<Ops_t>::value == 0 &&
173 "constructor can only be used with zero operands");
174 }
175 Recipe_match(Ops_t Ops) : Ops(Ops) {}
176 template <typename A_t, typename B_t>
177 Recipe_match(A_t A, B_t B) : Ops({A, B}) {
178 static_assert(std::tuple_size<Ops_t>::value == 2 &&
179 "constructor can only be used for binary matcher");
180 }
181
182 bool match(const VPValue *V) const {
183 auto *DefR = V->getDefiningRecipe();
184 return DefR && match(DefR);
185 }
186
187 bool match(const VPSingleDefRecipe *R) const {
188 return match(static_cast<const VPRecipeBase *>(R));
189 }
190
191 bool match(const VPRecipeBase *R) const {
193 return false;
194 assert(R->getNumOperands() == std::tuple_size<Ops_t>::value &&
195 "recipe with matched opcode the expected number of operands");
196
197 if (detail::all_of_tuple_elements(Ops, [R](auto Op, unsigned Idx) {
198 return Op.match(R->getOperand(Idx));
199 }))
200 return true;
201
202 return Commutative &&
203 detail::all_of_tuple_elements(Ops, [R](auto Op, unsigned Idx) {
204 return Op.match(R->getOperand(R->getNumOperands() - Idx - 1));
205 });
206 }
207};
208
209template <typename Op0_t, unsigned Opcode, typename... RecipeTys>
211 Recipe_match<std::tuple<Op0_t>, Opcode, false, RecipeTys...>;
212
213template <typename Op0_t, unsigned Opcode>
216
217template <typename Op0_t, unsigned Opcode>
221
222template <typename Op0_t, typename Op1_t, unsigned Opcode, bool Commutative,
223 typename... RecipeTys>
225 Recipe_match<std::tuple<Op0_t, Op1_t>, Opcode, Commutative, RecipeTys...>;
226
227template <typename Op0_t, typename Op1_t, unsigned Opcode>
229 BinaryRecipe_match<Op0_t, Op1_t, Opcode, /*Commutative*/ false,
231
232template <typename Op0_t, typename Op1_t, unsigned Opcode,
233 bool Commutative = false>
235 BinaryRecipe_match<Op0_t, Op1_t, Opcode, Commutative, VPWidenRecipe,
237
238template <unsigned Opcode, typename Op0_t>
240m_VPInstruction(const Op0_t &Op0) {
242}
243
244template <unsigned Opcode, typename Op0_t, typename Op1_t>
245inline BinaryVPInstruction_match<Op0_t, Op1_t, Opcode>
246m_VPInstruction(const Op0_t &Op0, const Op1_t &Op1) {
248}
249
250template <typename Op0_t>
251inline UnaryVPInstruction_match<Op0_t, VPInstruction::Not>
252m_Not(const Op0_t &Op0) {
253 return m_VPInstruction<VPInstruction::Not>(Op0);
254}
255
256template <typename Op0_t>
257inline UnaryVPInstruction_match<Op0_t, VPInstruction::BranchOnCond>
258m_BranchOnCond(const Op0_t &Op0) {
259 return m_VPInstruction<VPInstruction::BranchOnCond>(Op0);
260}
261
262template <typename Op0_t, typename Op1_t>
263inline BinaryVPInstruction_match<Op0_t, Op1_t, VPInstruction::ActiveLaneMask>
264m_ActiveLaneMask(const Op0_t &Op0, const Op1_t &Op1) {
265 return m_VPInstruction<VPInstruction::ActiveLaneMask>(Op0, Op1);
266}
267
268template <typename Op0_t, typename Op1_t>
269inline BinaryVPInstruction_match<Op0_t, Op1_t, VPInstruction::BranchOnCount>
270m_BranchOnCount(const Op0_t &Op0, const Op1_t &Op1) {
271 return m_VPInstruction<VPInstruction::BranchOnCount>(Op0, Op1);
272}
273
274template <unsigned Opcode, typename Op0_t>
277}
278
279template <typename Op0_t>
280inline AllUnaryRecipe_match<Op0_t, Instruction::Trunc>
281m_Trunc(const Op0_t &Op0) {
282 return m_Unary<Instruction::Trunc, Op0_t>(Op0);
283}
284
285template <typename Op0_t>
287 return m_Unary<Instruction::ZExt, Op0_t>(Op0);
288}
289
290template <typename Op0_t>
292 return m_Unary<Instruction::SExt, Op0_t>(Op0);
293}
294
295template <typename Op0_t>
297 AllUnaryRecipe_match<Op0_t, Instruction::SExt>>
298m_ZExtOrSExt(const Op0_t &Op0) {
299 return m_CombineOr(m_ZExt(Op0), m_SExt(Op0));
300}
301
302template <unsigned Opcode, typename Op0_t, typename Op1_t,
303 bool Commutative = false>
304inline AllBinaryRecipe_match<Op0_t, Op1_t, Opcode, Commutative>
305m_Binary(const Op0_t &Op0, const Op1_t &Op1) {
307}
308
309template <typename Op0_t, typename Op1_t>
310inline AllBinaryRecipe_match<Op0_t, Op1_t, Instruction::Mul>
311m_Mul(const Op0_t &Op0, const Op1_t &Op1) {
312 return m_Binary<Instruction::Mul, Op0_t, Op1_t>(Op0, Op1);
313}
314
315template <typename Op0_t, typename Op1_t>
316inline AllBinaryRecipe_match<Op0_t, Op1_t, Instruction::Mul,
317 /* Commutative =*/true>
318m_c_Mul(const Op0_t &Op0, const Op1_t &Op1) {
319 return m_Binary<Instruction::Mul, Op0_t, Op1_t, true>(Op0, Op1);
320}
321
322/// Match a binary OR operation. Note that while conceptually the operands can
323/// be matched commutatively, \p Commutative defaults to false in line with the
324/// IR-based pattern matching infrastructure. Use m_c_BinaryOr for a commutative
325/// version of the matcher.
326template <typename Op0_t, typename Op1_t, bool Commutative = false>
327inline AllBinaryRecipe_match<Op0_t, Op1_t, Instruction::Or, Commutative>
328m_BinaryOr(const Op0_t &Op0, const Op1_t &Op1) {
329 return m_Binary<Instruction::Or, Op0_t, Op1_t, Commutative>(Op0, Op1);
330}
331
332template <typename Op0_t, typename Op1_t>
333inline AllBinaryRecipe_match<Op0_t, Op1_t, Instruction::Or,
334 /*Commutative*/ true>
335m_c_BinaryOr(const Op0_t &Op0, const Op1_t &Op1) {
336 return m_BinaryOr<Op0_t, Op1_t, /*Commutative*/ true>(Op0, Op1);
337}
338
339template <typename Op0_t, typename Op1_t, typename Op2_t, unsigned Opcode>
343
344template <typename Op0_t, typename Op1_t, typename Op2_t>
346m_Select(const Op0_t &Op0, const Op1_t &Op1, const Op2_t &Op2) {
348 {Op0, Op1, Op2});
349}
350
351template <typename Op0_t, typename Op1_t>
352inline match_combine_or<
353 BinaryVPInstruction_match<Op0_t, Op1_t, VPInstruction::LogicalAnd>,
354 AllTernaryRecipe_match<Op0_t, Op1_t, specific_intval<1>,
355 Instruction::Select>>
356m_LogicalAnd(const Op0_t &Op0, const Op1_t &Op1) {
357 return m_CombineOr(
358 m_VPInstruction<VPInstruction::LogicalAnd, Op0_t, Op1_t>(Op0, Op1),
359 m_Select(Op0, Op1, m_False()));
360}
361
362template <typename Op0_t, typename Op1_t>
363inline AllTernaryRecipe_match<Op0_t, specific_intval<1>, Op1_t,
364 Instruction::Select>
365m_LogicalOr(const Op0_t &Op0, const Op1_t &Op1) {
366 return m_Select(Op0, m_True(), Op1);
367}
368
371
373 return VPCanonicalIVPHI_match();
374}
375
376template <typename Op0_t, typename Op1_t>
379
380template <typename Op0_t, typename Op1_t>
382 const Op1_t &Op1) {
384}
385} // namespace VPlanPatternMatch
386} // namespace llvm
387
388#endif
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define P(N)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains the declarations of the Vectorization Plan base classes:
Class for arbitrary precision integers.
Definition: APInt.h:78
static bool isSameValue(const APInt &I1, const APInt &I2)
Determine if two APInts have the same value, after zero-extending one of them (if needed!...
Definition: APInt.h:553
This class represents an Operation in the Expression.
Canonical scalar induction phi of the vector loop.
Definition: VPlan.h:3162
This is a concrete Recipe that models a single VPlan-level instruction.
Definition: VPlan.h:1197
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition: VPlan.h:720
VPReplicateRecipe replicates a given instruction producing multiple scalar copies of the original sca...
Definition: VPlan.h:2706
A recipe for handling phi nodes of integer and floating-point inductions, producing their scalar valu...
Definition: VPlan.h:3413
VPSingleDef is a base class for recipes for modeling a sequence of one or more output IR that define ...
Definition: VPlan.h:847
This class augments VPValue with operands which provide the inverse def-use edges from VPValue's user...
Definition: VPlanValue.h:200
Value * getLiveInIRValue()
Returns the underlying IR value, if this VPValue is defined outside the scope of VPlan.
Definition: VPlanValue.h:172
bool isLiveIn() const
Returns true if this VPValue is a live-in, i.e. defined outside the VPlan.
Definition: VPlanValue.h:167
VPWidenCastRecipe is a recipe to create vector cast instructions.
Definition: VPlan.h:1529
VPWidenRecipe is a recipe for producing a widened instruction using the opcode and operands of the re...
Definition: VPlan.h:1431
LLVM Value Representation.
Definition: Value.h:74
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
bool CheckTupleElements(const TupleTy &Ops, Fn P, std::index_sequence< Is... >)
bool all_of_tuple_elements(const TupleTy &Ops, Fn P)
Helper to check if predicate P holds on all tuple elements in Ops.
AllBinaryRecipe_match< Op0_t, Op1_t, Instruction::Or, Commutative > m_BinaryOr(const Op0_t &Op0, const Op1_t &Op1)
Match a binary OR operation.
AllTernaryRecipe_match< Op0_t, Op1_t, Op2_t, Instruction::Select > m_Select(const Op0_t &Op0, const Op1_t &Op1, const Op2_t &Op2)
AllUnaryRecipe_match< Op0_t, Opcode > m_Unary(const Op0_t &Op0)
AllBinaryRecipe_match< Op0_t, Op1_t, Instruction::Or, true > m_c_BinaryOr(const Op0_t &Op0, const Op1_t &Op1)
BinaryVPInstruction_match< Op0_t, Op1_t, VPInstruction::ActiveLaneMask > m_ActiveLaneMask(const Op0_t &Op0, const Op1_t &Op1)
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
UnaryVPInstruction_match< Op0_t, Opcode > m_VPInstruction(const Op0_t &Op0)
AllBinaryRecipe_match< Op0_t, Op1_t, Opcode, Commutative > m_Binary(const Op0_t &Op0, const Op1_t &Op1)
UnaryVPInstruction_match< Op0_t, VPInstruction::Not > m_Not(const Op0_t &Op0)
VPCanonicalIVPHI_match m_CanonicalIV()
AllUnaryRecipe_match< Op0_t, Instruction::Trunc > m_Trunc(const Op0_t &Op0)
VPScalarIVSteps_match< Op0_t, Op1_t > m_ScalarIVSteps(const Op0_t &Op0, const Op1_t &Op1)
AllBinaryRecipe_match< Op0_t, Op1_t, Instruction::Mul, true > m_c_Mul(const Op0_t &Op0, const Op1_t &Op1)
BinaryVPInstruction_match< Op0_t, Op1_t, VPInstruction::BranchOnCount > m_BranchOnCount(const Op0_t &Op0, const Op1_t &Op1)
specificval_ty m_Specific(const VPValue *VPV)
specific_intval< 1 > m_False()
specific_intval< 0 > m_SpecificInt(uint64_t V)
AllBinaryRecipe_match< Op0_t, Op1_t, Instruction::Mul > m_Mul(const Op0_t &Op0, const Op1_t &Op1)
specific_intval< 1 > m_True()
UnaryVPInstruction_match< Op0_t, VPInstruction::BranchOnCond > m_BranchOnCond(const Op0_t &Op0)
bool match(Val *V, const Pattern &P)
class_match< VPValue > m_VPValue()
Match an arbitrary VPValue and ignore it.
BinaryRecipe_match< Op0_t, Op1_t, Opcode, Commutative, VPWidenRecipe, VPReplicateRecipe, VPWidenCastRecipe, VPInstruction > AllBinaryRecipe_match
AllUnaryRecipe_match< Op0_t, Instruction::SExt > m_SExt(const Op0_t &Op0)
AllUnaryRecipe_match< Op0_t, Instruction::ZExt > m_ZExt(const Op0_t &Op0)
Recipe_match< std::tuple<>, 0, false, VPCanonicalIVPHIRecipe > VPCanonicalIVPHI_match
match_combine_or< AllUnaryRecipe_match< Op0_t, Instruction::ZExt >, AllUnaryRecipe_match< Op0_t, Instruction::SExt > > m_ZExtOrSExt(const Op0_t &Op0)
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:217
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1873
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
A recipe for widening select instructions.
Definition: VPlan.h:1813
bool match(const VPSingleDefRecipe *R) const
bool match(const VPValue *V) const
bool match(const VPRecipeBase *R) const
A helper to match an opcode against multiple recipe types.
match_combine_or(const LTy &Left, const RTy &Right)
Match a specified integer value or vector of all elements of that value.