| 1 | //===- SLPShuffleAnalysis.h - SLP shuffle analysis base ---------*- 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 | // Internal header used by SLPVectorizer.cpp. It defines the base class for |
| 10 | // shuffle cost estimation and shuffle instruction emission. It does not depend |
| 11 | // on BoUpSLP or any other SLP-private type. |
| 12 | // |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
| 15 | #ifndef LLVM_LIB_TRANSFORMS_VECTORIZE_SLPVECTORIZER_SLPSHUFFLEANALYSIS_H |
| 16 | #define LLVM_LIB_TRANSFORMS_VECTORIZE_SLPVECTORIZER_SLPSHUFFLEANALYSIS_H |
| 17 | |
| 18 | #include "SLPUtils.h" |
| 19 | |
| 20 | #include "llvm/ADT/ArrayRef.h" |
| 21 | #include "llvm/ADT/STLExtras.h" |
| 22 | #include "llvm/ADT/STLFunctionalExtras.h" |
| 23 | #include "llvm/ADT/Sequence.h" |
| 24 | #include "llvm/ADT/SmallBitVector.h" |
| 25 | #include "llvm/ADT/SmallVector.h" |
| 26 | #include "llvm/IR/Constants.h" |
| 27 | #include "llvm/IR/DerivedTypes.h" |
| 28 | #include "llvm/IR/Instructions.h" |
| 29 | #include "llvm/Support/Casting.h" |
| 30 | |
| 31 | #include <algorithm> |
| 32 | #include <cassert> |
| 33 | #include <type_traits> |
| 34 | #include <utility> |
| 35 | |
| 36 | namespace llvm::slpvectorizer { |
| 37 | |
| 38 | /// The base class for shuffle instruction emission and shuffle cost estimation. |
| 39 | class BaseShuffleAnalysis { |
| 40 | protected: |
| 41 | Type *ScalarTy = nullptr; |
| 42 | |
| 43 | BaseShuffleAnalysis(Type *ScalarTy) : ScalarTy(ScalarTy) {} |
| 44 | |
| 45 | /// V is expected to be a vectorized value. |
| 46 | /// When REVEC is disabled, there is no difference between VF and |
| 47 | /// VNumElements. |
| 48 | /// When REVEC is enabled, VF is VNumElements / ScalarTyNumElements. |
| 49 | /// e.g., if ScalarTy is <4 x Ty> and V1 is <8 x Ty>, 2 is returned instead |
| 50 | /// of 8. |
| 51 | unsigned getVF(Value *V) const { |
| 52 | assert(V && "V cannot be nullptr" ); |
| 53 | assert(isa<FixedVectorType>(V->getType()) && |
| 54 | "V does not have FixedVectorType" ); |
| 55 | assert(ScalarTy && "ScalarTy cannot be nullptr" ); |
| 56 | unsigned ScalarTyNumElements = getNumElements(Ty: ScalarTy); |
| 57 | unsigned VNumElements = |
| 58 | cast<FixedVectorType>(Val: V->getType())->getNumElements(); |
| 59 | assert(VNumElements > ScalarTyNumElements && |
| 60 | "the number of elements of V is not large enough" ); |
| 61 | assert(VNumElements % ScalarTyNumElements == 0 && |
| 62 | "the number of elements of V is not a vectorized value" ); |
| 63 | return VNumElements / ScalarTyNumElements; |
| 64 | } |
| 65 | |
| 66 | /// Checks if the mask is an identity mask. |
| 67 | /// \param IsStrict if is true the function returns false if mask size does |
| 68 | /// not match vector size. |
| 69 | static bool isIdentityMask(ArrayRef<int> Mask, const FixedVectorType *VecTy, |
| 70 | bool IsStrict) { |
| 71 | int Limit = Mask.size(); |
| 72 | int VF = VecTy->getNumElements(); |
| 73 | int Index = -1; |
| 74 | if (VF == Limit && ShuffleVectorInst::isIdentityMask(Mask, NumSrcElts: Limit)) |
| 75 | return true; |
| 76 | if (!IsStrict) { |
| 77 | // Consider extract subvector starting from index 0. |
| 78 | if (ShuffleVectorInst::isExtractSubvectorMask(Mask, NumSrcElts: VF, Index) && |
| 79 | Index == 0) |
| 80 | return true; |
| 81 | // All VF-size submasks are identity (e.g. |
| 82 | // <poison,poison,poison,poison,0,1,2,poison,poison,1,2,3> etc. for VF 4). |
| 83 | if (Limit % VF == 0 && all_of(Range: seq<int>(Begin: 0, End: Limit / VF), P: [=](int Idx) { |
| 84 | ArrayRef<int> Slice = Mask.slice(N: Idx * VF, M: VF); |
| 85 | return all_of(Range&: Slice, P: equal_to(Arg: PoisonMaskElem)) || |
| 86 | ShuffleVectorInst::isIdentityMask(Mask: Slice, NumSrcElts: VF); |
| 87 | })) |
| 88 | return true; |
| 89 | } |
| 90 | return false; |
| 91 | } |
| 92 | |
| 93 | /// Tries to combine 2 different masks into single one. |
| 94 | /// \param LocalVF Vector length of the permuted input vector. \p Mask may |
| 95 | /// change the size of the vector, \p LocalVF is the original size of the |
| 96 | /// shuffled vector. |
| 97 | static void combineMasks(unsigned LocalVF, SmallVectorImpl<int> &Mask, |
| 98 | ArrayRef<int> ExtMask) { |
| 99 | unsigned VF = Mask.size(); |
| 100 | SmallVector<int> NewMask(ExtMask.size(), PoisonMaskElem); |
| 101 | for (int I = 0, Sz = ExtMask.size(); I < Sz; ++I) { |
| 102 | if (ExtMask[I] == PoisonMaskElem) |
| 103 | continue; |
| 104 | int MaskedIdx = Mask[ExtMask[I] % VF]; |
| 105 | NewMask[I] = |
| 106 | MaskedIdx == PoisonMaskElem ? PoisonMaskElem : MaskedIdx % LocalVF; |
| 107 | } |
| 108 | Mask.swap(RHS&: NewMask); |
| 109 | } |
| 110 | |
| 111 | /// Looks through shuffles trying to reduce final number of shuffles in the |
| 112 | /// code. The function looks through the previously emitted shuffle |
| 113 | /// instructions and properly mark indices in mask as undef. |
| 114 | /// For example, given the code |
| 115 | /// \code |
| 116 | /// %s1 = shufflevector <2 x ty> %0, poison, <1, 0> |
| 117 | /// %s2 = shufflevector <2 x ty> %1, poison, <1, 0> |
| 118 | /// \endcode |
| 119 | /// and if need to emit shuffle of %s1 and %s2 with mask <1, 0, 3, 2>, it will |
| 120 | /// look through %s1 and %s2 and select vectors %0 and %1 with mask |
| 121 | /// <0, 1, 2, 3> for the shuffle. |
| 122 | /// If 2 operands are of different size, the smallest one will be resized and |
| 123 | /// the mask recalculated properly. |
| 124 | /// For example, given the code |
| 125 | /// \code |
| 126 | /// %s1 = shufflevector <2 x ty> %0, poison, <1, 0, 1, 0> |
| 127 | /// %s2 = shufflevector <2 x ty> %1, poison, <1, 0, 1, 0> |
| 128 | /// \endcode |
| 129 | /// and if need to emit shuffle of %s1 and %s2 with mask <1, 0, 5, 4>, it will |
| 130 | /// look through %s1 and %s2 and select vectors %0 and %1 with mask |
| 131 | /// <0, 1, 2, 3> for the shuffle. |
| 132 | /// So, it tries to transform permutations to simple vector merge, if |
| 133 | /// possible. |
| 134 | /// \param V The input vector which must be shuffled using the given \p Mask. |
| 135 | /// If the better candidate is found, \p V is set to this best candidate |
| 136 | /// vector. |
| 137 | /// \param Mask The input mask for the shuffle. If the best candidate is found |
| 138 | /// during looking-through-shuffles attempt, it is updated accordingly. |
| 139 | /// \param SinglePermute true if the shuffle operation is originally a |
| 140 | /// single-value-permutation. In this case the look-through-shuffles procedure |
| 141 | /// may look for resizing shuffles as the best candidates. |
| 142 | /// \return true if the shuffle results in the non-resizing identity shuffle |
| 143 | /// (and thus can be ignored), false - otherwise. |
| 144 | static bool peekThroughShuffles(Value *&V, SmallVectorImpl<int> &Mask, |
| 145 | bool SinglePermute) { |
| 146 | Value *Op = V; |
| 147 | ShuffleVectorInst *IdentityOp = nullptr; |
| 148 | SmallVector<int> IdentityMask; |
| 149 | while (auto *SV = dyn_cast<ShuffleVectorInst>(Val: Op)) { |
| 150 | // Exit if not a fixed vector type or changing size shuffle. |
| 151 | auto *SVTy = dyn_cast<FixedVectorType>(Val: SV->getType()); |
| 152 | if (!SVTy) |
| 153 | break; |
| 154 | // Remember the identity or broadcast mask, if it is not a resizing |
| 155 | // shuffle. If no better candidates are found, this Op and Mask will be |
| 156 | // used in the final shuffle. |
| 157 | if (isIdentityMask(Mask, VecTy: SVTy, /*IsStrict=*/IsStrict: false)) { |
| 158 | if (!IdentityOp || !SinglePermute || |
| 159 | (isIdentityMask(Mask, VecTy: SVTy, /*IsStrict=*/IsStrict: true) && |
| 160 | !ShuffleVectorInst::isZeroEltSplatMask(Mask: IdentityMask, |
| 161 | NumSrcElts: IdentityMask.size()))) { |
| 162 | IdentityOp = SV; |
| 163 | // Store current mask in the IdentityMask so later we did not lost |
| 164 | // this info if IdentityOp is selected as the best candidate for the |
| 165 | // permutation. |
| 166 | IdentityMask.assign(RHS: Mask); |
| 167 | } |
| 168 | } |
| 169 | // Remember the broadcast mask. If no better candidates are found, this Op |
| 170 | // and Mask will be used in the final shuffle. |
| 171 | // Zero splat can be used as identity too, since it might be used with |
| 172 | // mask <0, 1, 2, ...>, i.e. identity mask without extra reshuffling. |
| 173 | // E.g. if need to shuffle the vector with the mask <3, 1, 2, 0>, which is |
| 174 | // expensive, the analysis founds out, that the source vector is just a |
| 175 | // broadcast, this original mask can be transformed to identity mask <0, |
| 176 | // 1, 2, 3>. |
| 177 | // \code |
| 178 | // %0 = shuffle %v, poison, zeroinitalizer |
| 179 | // %res = shuffle %0, poison, <3, 1, 2, 0> |
| 180 | // \endcode |
| 181 | // may be transformed to |
| 182 | // \code |
| 183 | // %0 = shuffle %v, poison, zeroinitalizer |
| 184 | // %res = shuffle %0, poison, <0, 1, 2, 3> |
| 185 | // \endcode |
| 186 | if (SV->isZeroEltSplat()) { |
| 187 | IdentityOp = SV; |
| 188 | IdentityMask.assign(RHS: Mask); |
| 189 | } |
| 190 | int LocalVF = Mask.size(); |
| 191 | if (auto *SVOpTy = |
| 192 | dyn_cast<FixedVectorType>(Val: SV->getOperand(i_nocapture: 0)->getType())) |
| 193 | LocalVF = SVOpTy->getNumElements(); |
| 194 | SmallVector<int> ExtMask(Mask.size(), PoisonMaskElem); |
| 195 | for (auto [Idx, I] : |
| 196 | make_filter_range(Range: enumerate(First&: Mask), Pred: [&](const auto &P) { |
| 197 | return P.value() != PoisonMaskElem && |
| 198 | static_cast<unsigned>(P.value()) < |
| 199 | SV->getShuffleMask().size(); |
| 200 | })) |
| 201 | ExtMask[Idx] = SV->getMaskValue(Elt: I); |
| 202 | bool IsOp1Undef = isUndefVector</*isPoisonOnly=*/true>( |
| 203 | V: SV->getOperand(i_nocapture: 0), |
| 204 | UseMask: buildUseMask(VF: LocalVF, Mask: ExtMask, MaskArg: UseMask::FirstArg)) |
| 205 | .all(); |
| 206 | bool IsOp2Undef = isUndefVector</*isPoisonOnly=*/true>( |
| 207 | V: SV->getOperand(i_nocapture: 1), |
| 208 | UseMask: buildUseMask(VF: LocalVF, Mask: ExtMask, MaskArg: UseMask::SecondArg)) |
| 209 | .all(); |
| 210 | if (!IsOp1Undef && !IsOp2Undef) { |
| 211 | // Update mask and mark undef elems. |
| 212 | for (int &I : make_filter_range( |
| 213 | Range&: Mask, Pred: [](int I) { return I != PoisonMaskElem; })) { |
| 214 | if (SV->getMaskValue(Elt: I % SV->getShuffleMask().size()) == |
| 215 | PoisonMaskElem) |
| 216 | I = PoisonMaskElem; |
| 217 | } |
| 218 | break; |
| 219 | } |
| 220 | SmallVector<int> ShuffleMask(SV->getShuffleMask()); |
| 221 | combineMasks(LocalVF, Mask&: ShuffleMask, ExtMask: Mask); |
| 222 | Mask.swap(RHS&: ShuffleMask); |
| 223 | if (IsOp2Undef) |
| 224 | Op = SV->getOperand(i_nocapture: 0); |
| 225 | else |
| 226 | Op = SV->getOperand(i_nocapture: 1); |
| 227 | } |
| 228 | if (auto *OpTy = dyn_cast<FixedVectorType>(Val: Op->getType()); |
| 229 | !OpTy || !isIdentityMask(Mask, VecTy: OpTy, IsStrict: SinglePermute) || |
| 230 | ShuffleVectorInst::isZeroEltSplatMask(Mask, NumSrcElts: Mask.size())) { |
| 231 | if (IdentityOp) { |
| 232 | V = IdentityOp; |
| 233 | assert(Mask.size() == IdentityMask.size() && |
| 234 | "Expected masks of same sizes." ); |
| 235 | // Clear known poison elements. |
| 236 | for (auto [I, Idx] : enumerate(First&: Mask)) |
| 237 | if (Idx == PoisonMaskElem) |
| 238 | IdentityMask[I] = PoisonMaskElem; |
| 239 | Mask.swap(RHS&: IdentityMask); |
| 240 | auto *Shuffle = dyn_cast<ShuffleVectorInst>(Val: V); |
| 241 | return SinglePermute && |
| 242 | (isIdentityMask(Mask, VecTy: cast<FixedVectorType>(Val: V->getType()), |
| 243 | /*IsStrict=*/IsStrict: true) || |
| 244 | (Shuffle && Mask.size() == Shuffle->getShuffleMask().size() && |
| 245 | Shuffle->isZeroEltSplat() && |
| 246 | ShuffleVectorInst::isZeroEltSplatMask(Mask, NumSrcElts: Mask.size()) && |
| 247 | all_of(Range: enumerate(First&: Mask), P: [&](const auto &P) { |
| 248 | return P.value() == PoisonMaskElem || |
| 249 | Shuffle->getShuffleMask()[P.index()] == 0; |
| 250 | }))); |
| 251 | } |
| 252 | V = Op; |
| 253 | return false; |
| 254 | } |
| 255 | V = Op; |
| 256 | return true; |
| 257 | } |
| 258 | |
| 259 | /// Smart shuffle instruction emission, walks through shuffles trees and |
| 260 | /// tries to find the best matching vector for the actual shuffle |
| 261 | /// instruction. |
| 262 | template <typename T, typename ShuffleBuilderTy, typename... Args> |
| 263 | static T createShuffle(Value *V1, Value *V2, ArrayRef<int> Mask, |
| 264 | ShuffleBuilderTy &Builder, Type *ScalarTy, |
| 265 | [[maybe_unused]] bool ReVec, Args... Arguments) { |
| 266 | assert(V1 && "Expected at least one vector value." ); |
| 267 | unsigned ScalarTyNumElements = getNumElements(Ty: ScalarTy); |
| 268 | SmallVector<int> NewMask(Mask); |
| 269 | if (ScalarTyNumElements != 1) { |
| 270 | assert(ReVec && "FixedVectorType is not expected." ); |
| 271 | transformScalarShuffleIndiciesToVector(VecTyNumElements: ScalarTyNumElements, Mask&: NewMask); |
| 272 | Mask = NewMask; |
| 273 | } |
| 274 | if (V2) |
| 275 | Builder.resizeToMatch(V1, V2); |
| 276 | int VF = Mask.size(); |
| 277 | if (auto *FTy = dyn_cast<FixedVectorType>(Val: V1->getType())) |
| 278 | VF = FTy->getNumElements(); |
| 279 | if (V2 && !isUndefVector</*IsPoisonOnly=*/true>( |
| 280 | V: V2, UseMask: buildUseMask(VF, Mask, MaskArg: UseMask::SecondArg)) |
| 281 | .all()) { |
| 282 | // Peek through shuffles. |
| 283 | Value *Op1 = V1; |
| 284 | Value *Op2 = V2; |
| 285 | int VF = |
| 286 | cast<VectorType>(Val: V1->getType())->getElementCount().getKnownMinValue(); |
| 287 | SmallVector<int> CombinedMask1(Mask.size(), PoisonMaskElem); |
| 288 | SmallVector<int> CombinedMask2(Mask.size(), PoisonMaskElem); |
| 289 | for (int I = 0, E = Mask.size(); I < E; ++I) { |
| 290 | if (Mask[I] < VF) |
| 291 | CombinedMask1[I] = Mask[I]; |
| 292 | else |
| 293 | CombinedMask2[I] = Mask[I] - VF; |
| 294 | } |
| 295 | Value *PrevOp1; |
| 296 | Value *PrevOp2; |
| 297 | do { |
| 298 | PrevOp1 = Op1; |
| 299 | PrevOp2 = Op2; |
| 300 | (void)peekThroughShuffles(V&: Op1, Mask&: CombinedMask1, /*SinglePermute=*/SinglePermute: false); |
| 301 | (void)peekThroughShuffles(V&: Op2, Mask&: CombinedMask2, /*SinglePermute=*/SinglePermute: false); |
| 302 | // Check if we have 2 resizing shuffles - need to peek through operands |
| 303 | // again. |
| 304 | if (auto *SV1 = dyn_cast<ShuffleVectorInst>(Val: Op1)) |
| 305 | if (auto *SV2 = dyn_cast<ShuffleVectorInst>(Val: Op2)) { |
| 306 | SmallVector<int> ExtMask1(Mask.size(), PoisonMaskElem); |
| 307 | for (const auto &P : |
| 308 | make_filter_range(enumerate(First&: CombinedMask1), [](const auto &P) { |
| 309 | return P.value() != PoisonMaskElem; |
| 310 | })) |
| 311 | ExtMask1[P.index()] = SV1->getMaskValue(Elt: P.value()); |
| 312 | SmallBitVector UseMask1 = buildUseMask( |
| 313 | VF: cast<FixedVectorType>(Val: SV1->getOperand(i_nocapture: 1)->getType()) |
| 314 | ->getNumElements(), |
| 315 | Mask: ExtMask1, MaskArg: UseMask::SecondArg); |
| 316 | SmallVector<int> ExtMask2(CombinedMask2.size(), PoisonMaskElem); |
| 317 | for (const auto &P : |
| 318 | make_filter_range(enumerate(First&: CombinedMask2), [](const auto &P) { |
| 319 | return P.value() != PoisonMaskElem; |
| 320 | })) |
| 321 | ExtMask2[P.index()] = SV2->getMaskValue(Elt: P.value()); |
| 322 | SmallBitVector UseMask2 = buildUseMask( |
| 323 | VF: cast<FixedVectorType>(Val: SV2->getOperand(i_nocapture: 1)->getType()) |
| 324 | ->getNumElements(), |
| 325 | Mask: ExtMask2, MaskArg: UseMask::SecondArg); |
| 326 | if (SV1->getOperand(i_nocapture: 0)->getType() == |
| 327 | SV2->getOperand(i_nocapture: 0)->getType() && |
| 328 | SV1->getOperand(i_nocapture: 0)->getType() != SV1->getType() && |
| 329 | isUndefVector</*IsPoisonOnly=*/true>(V: SV1->getOperand(i_nocapture: 1), |
| 330 | UseMask: UseMask1) |
| 331 | .all() && |
| 332 | isUndefVector</*IsPoisonOnly=*/true>(V: SV2->getOperand(i_nocapture: 1), |
| 333 | UseMask: UseMask2) |
| 334 | .all()) { |
| 335 | Op1 = SV1->getOperand(i_nocapture: 0); |
| 336 | Op2 = SV2->getOperand(i_nocapture: 0); |
| 337 | SmallVector<int> ShuffleMask1(SV1->getShuffleMask()); |
| 338 | int LocalVF = ShuffleMask1.size(); |
| 339 | if (auto *FTy = dyn_cast<FixedVectorType>(Val: Op1->getType())) |
| 340 | LocalVF = FTy->getNumElements(); |
| 341 | combineMasks(LocalVF, Mask&: ShuffleMask1, ExtMask: CombinedMask1); |
| 342 | CombinedMask1.swap(RHS&: ShuffleMask1); |
| 343 | SmallVector<int> ShuffleMask2(SV2->getShuffleMask()); |
| 344 | LocalVF = ShuffleMask2.size(); |
| 345 | if (auto *FTy = dyn_cast<FixedVectorType>(Val: Op2->getType())) |
| 346 | LocalVF = FTy->getNumElements(); |
| 347 | combineMasks(LocalVF, Mask&: ShuffleMask2, ExtMask: CombinedMask2); |
| 348 | CombinedMask2.swap(RHS&: ShuffleMask2); |
| 349 | } |
| 350 | } |
| 351 | } while (PrevOp1 != Op1 || PrevOp2 != Op2); |
| 352 | Builder.resizeToMatch(Op1, Op2); |
| 353 | VF = std::max(a: cast<VectorType>(Val: Op1->getType()) |
| 354 | ->getElementCount() |
| 355 | .getKnownMinValue(), |
| 356 | b: cast<VectorType>(Val: Op2->getType()) |
| 357 | ->getElementCount() |
| 358 | .getKnownMinValue()); |
| 359 | for (int I = 0, E = Mask.size(); I < E; ++I) { |
| 360 | if (CombinedMask2[I] != PoisonMaskElem) { |
| 361 | assert(CombinedMask1[I] == PoisonMaskElem && |
| 362 | "Expected undefined mask element" ); |
| 363 | CombinedMask1[I] = CombinedMask2[I] + (Op1 == Op2 ? 0 : VF); |
| 364 | } |
| 365 | } |
| 366 | if (Op1 == Op2 && |
| 367 | (ShuffleVectorInst::isIdentityMask(Mask: CombinedMask1, NumSrcElts: VF) || |
| 368 | (ShuffleVectorInst::isZeroEltSplatMask(Mask: CombinedMask1, NumSrcElts: VF) && |
| 369 | isa<ShuffleVectorInst>(Val: Op1) && |
| 370 | cast<ShuffleVectorInst>(Val: Op1)->getShuffleMask() == |
| 371 | ArrayRef(CombinedMask1)))) |
| 372 | return Builder.createIdentity(Op1); |
| 373 | return Builder.createShuffleVector( |
| 374 | Op1, Op1 == Op2 ? PoisonValue::get(T: Op1->getType()) : Op2, |
| 375 | CombinedMask1); |
| 376 | } |
| 377 | if (isa<PoisonValue>(Val: V1)) |
| 378 | return Builder.createPoison( |
| 379 | cast<VectorType>(Val: V1->getType())->getElementType(), Mask.size()); |
| 380 | bool IsIdentity = peekThroughShuffles(V&: V1, Mask&: NewMask, /*SinglePermute=*/SinglePermute: true); |
| 381 | assert(V1 && "Expected non-null value after looking through shuffles." ); |
| 382 | |
| 383 | if (!IsIdentity) |
| 384 | return Builder.createShuffleVector(V1, NewMask, Arguments...); |
| 385 | return Builder.createIdentity(V1); |
| 386 | } |
| 387 | |
| 388 | /// Transforms mask \p CommonMask per given \p Mask to make proper set after |
| 389 | /// shuffle emission. |
| 390 | static void transformMaskAfterShuffle(MutableArrayRef<int> CommonMask, |
| 391 | ArrayRef<int> Mask) { |
| 392 | for (unsigned I : seq<unsigned>(Size: CommonMask.size())) |
| 393 | if (Mask[I] != PoisonMaskElem) |
| 394 | CommonMask[I] = I; |
| 395 | } |
| 396 | }; |
| 397 | |
| 398 | /// Does the analysis of the provided shuffle masks and performs the requested |
| 399 | /// actions on the vectors with the given shuffle masks. It tries to do it in |
| 400 | /// several steps. |
| 401 | /// 1. If the Base vector is not poison vector, resizing the very first mask to |
| 402 | /// have common VF and perform action for 2 input vectors (including non-poison |
| 403 | /// Base). Other shuffle masks are combined with the resulting after the 1 stage |
| 404 | /// and processed as a shuffle of 2 elements. |
| 405 | /// 2. If the Base is poison vector and have only 1 shuffle mask, perform the |
| 406 | /// action only for 1 vector with the given mask, if it is not the identity |
| 407 | /// mask. |
| 408 | /// 3. If > 2 masks are used, perform the remaining shuffle actions for 2 |
| 409 | /// vectors, combing the masks properly between the steps. |
| 410 | template <typename T> |
| 411 | T *( |
| 412 | MutableArrayRef<std::pair<T *, SmallVector<int>>> ShuffleMask, Value *Base, |
| 413 | function_ref<unsigned(T *)> GetVF, |
| 414 | function_ref<std::pair<T *, bool>(T *, ArrayRef<int>, bool)> ResizeAction, |
| 415 | function_ref<T *(ArrayRef<int>, ArrayRef<T *>)> Action) { |
| 416 | assert(!ShuffleMask.empty() && "Empty list of shuffles for inserts." ); |
| 417 | SmallVector<int> Mask(ShuffleMask.begin()->second); |
| 418 | auto VMIt = std::next(ShuffleMask.begin()); |
| 419 | T *Prev = nullptr; |
| 420 | SmallBitVector UseMask = |
| 421 | buildUseMask(VF: Mask.size(), Mask, MaskArg: UseMask::UndefsAsMask); |
| 422 | // The undef elements of the base must be preserved, only the poison base can |
| 423 | // be dropped. |
| 424 | SmallBitVector IsBasePoison = isUndefVector<true>(V: Base, UseMask); |
| 425 | if (!IsBasePoison.all()) { |
| 426 | // Base is not poison, need to combine it with the next subvectors. |
| 427 | std::pair<T *, bool> Res = |
| 428 | ResizeAction(ShuffleMask.begin()->first, Mask, /*ForSingleMask=*/false); |
| 429 | for (unsigned Idx = 0, VF = Mask.size(); Idx < VF; ++Idx) { |
| 430 | if (Mask[Idx] == PoisonMaskElem) |
| 431 | Mask[Idx] = IsBasePoison.test(Idx) ? PoisonMaskElem : Idx; |
| 432 | else |
| 433 | Mask[Idx] = (Res.second ? Idx : Mask[Idx]) + VF; |
| 434 | } |
| 435 | if constexpr (std::is_same_v<T, Value>) |
| 436 | assert(GetVF(Base) == Mask.size() && |
| 437 | "Expected base vector of VF number of elements." ); |
| 438 | Prev = Action(Mask, {nullptr, Res.first}); |
| 439 | } else if (ShuffleMask.size() == 1) { |
| 440 | // Base is poison and only 1 vector is shuffled - perform the action only |
| 441 | // for single vector, if the mask is not the identity mask. |
| 442 | std::pair<T *, bool> Res = ResizeAction(ShuffleMask.begin()->first, Mask, |
| 443 | /*ForSingleMask=*/true); |
| 444 | if (Res.second) |
| 445 | // Identity mask is found. |
| 446 | Prev = Res.first; |
| 447 | else |
| 448 | Prev = Action(Mask, {ShuffleMask.begin()->first}); |
| 449 | } else { |
| 450 | // Base is poison and at least 2 input vectors shuffled - perform 2 vectors |
| 451 | // shuffles step by step, combining shuffle between the steps. |
| 452 | unsigned Vec1VF = GetVF(ShuffleMask.begin()->first); |
| 453 | unsigned Vec2VF = GetVF(VMIt->first); |
| 454 | if (Vec1VF == Vec2VF) { |
| 455 | // No need to resize the input vectors since they are of the same size, we |
| 456 | // can shuffle them directly. |
| 457 | ArrayRef<int> SecMask = VMIt->second; |
| 458 | for (unsigned I = 0, VF = Mask.size(); I < VF; ++I) { |
| 459 | if (SecMask[I] != PoisonMaskElem) { |
| 460 | assert(Mask[I] == PoisonMaskElem && "Multiple uses of scalars." ); |
| 461 | Mask[I] = SecMask[I] + Vec1VF; |
| 462 | } |
| 463 | } |
| 464 | Prev = Action(Mask, {ShuffleMask.begin()->first, VMIt->first}); |
| 465 | } else { |
| 466 | // Vectors of different sizes - resize and reshuffle. |
| 467 | std::pair<T *, bool> Res1 = ResizeAction(ShuffleMask.begin()->first, Mask, |
| 468 | /*ForSingleMask=*/false); |
| 469 | std::pair<T *, bool> Res2 = |
| 470 | ResizeAction(VMIt->first, VMIt->second, /*ForSingleMask=*/false); |
| 471 | ArrayRef<int> SecMask = VMIt->second; |
| 472 | for (unsigned I = 0, VF = Mask.size(); I < VF; ++I) { |
| 473 | if (Mask[I] != PoisonMaskElem) { |
| 474 | assert(SecMask[I] == PoisonMaskElem && "Multiple uses of scalars." ); |
| 475 | if (Res1.second) |
| 476 | Mask[I] = I; |
| 477 | } else if (SecMask[I] != PoisonMaskElem) { |
| 478 | assert(Mask[I] == PoisonMaskElem && "Multiple uses of scalars." ); |
| 479 | Mask[I] = (Res2.second ? I : SecMask[I]) + VF; |
| 480 | } |
| 481 | } |
| 482 | Prev = Action(Mask, {Res1.first, Res2.first}); |
| 483 | } |
| 484 | VMIt = std::next(VMIt); |
| 485 | } |
| 486 | [[maybe_unused]] bool IsBaseNotPoison = !IsBasePoison.all(); |
| 487 | // Perform requested actions for the remaining masks/vectors. |
| 488 | for (auto E = ShuffleMask.end(); VMIt != E; ++VMIt) { |
| 489 | // Shuffle other input vectors, if any. |
| 490 | std::pair<T *, bool> Res = |
| 491 | ResizeAction(VMIt->first, VMIt->second, /*ForSingleMask=*/false); |
| 492 | ArrayRef<int> SecMask = VMIt->second; |
| 493 | for (unsigned I = 0, VF = Mask.size(); I < VF; ++I) { |
| 494 | if (SecMask[I] != PoisonMaskElem) { |
| 495 | assert((Mask[I] == PoisonMaskElem || IsBaseNotPoison) && |
| 496 | "Multiple uses of scalars." ); |
| 497 | Mask[I] = (Res.second ? I : SecMask[I]) + VF; |
| 498 | } else if (Mask[I] != PoisonMaskElem) { |
| 499 | Mask[I] = I; |
| 500 | } |
| 501 | } |
| 502 | Prev = Action(Mask, {Prev, Res.first}); |
| 503 | } |
| 504 | return Prev; |
| 505 | } |
| 506 | |
| 507 | } // namespace llvm::slpvectorizer |
| 508 | |
| 509 | #endif // LLVM_LIB_TRANSFORMS_VECTORIZE_SLPVECTORIZER_SLPSHUFFLEANALYSIS_H |
| 510 | |