1//===- SLPCompatibilityAnalysis.cpp - SLP same-opcode helpers -------------===//
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#include "SLPCompatibilityAnalysis.h"
10#include "SLPUtils.h"
11
12#include "llvm/ADT/APInt.h"
13#include "llvm/ADT/ArrayRef.h"
14#include "llvm/ADT/STLExtras.h"
15#include "llvm/ADT/SetVector.h"
16#include "llvm/ADT/SmallVector.h"
17#include "llvm/ADT/SmallVectorExtras.h"
18#include "llvm/ADT/bit.h"
19#include "llvm/Analysis/VectorUtils.h"
20#include "llvm/IR/Constants.h"
21#include "llvm/IR/InstrTypes.h"
22#include "llvm/IR/Instruction.h"
23#include "llvm/IR/Instructions.h"
24#include "llvm/IR/IntrinsicInst.h"
25#include "llvm/IR/Intrinsics.h"
26#include "llvm/IR/PatternMatch.h"
27#include "llvm/IR/Value.h"
28#include "llvm/Support/Casting.h"
29#include "llvm/Support/ErrorHandling.h"
30
31#include <algorithm>
32#include <array>
33#include <cassert>
34#include <optional>
35#include <utility>
36
37using namespace llvm;
38using namespace llvm::PatternMatch;
39
40namespace llvm::slpvectorizer {
41
42bool isValidForAlternation(unsigned Opcode) {
43 return !Instruction::isIntDivRem(Opcode);
44}
45
46std::pair<Constant *, unsigned>
47BinOpSameOpcodeHelper::isBinOpWithConstant(const Instruction *I) {
48 [[maybe_unused]] unsigned Opcode = I->getOpcode();
49 assert(binary_search(SupportedOp, Opcode) && "Unsupported opcode.");
50 (void)SupportedOp;
51 auto *BinOp = cast<BinaryOperator>(Val: I);
52 auto GetConstant = [](Value *V) -> Constant * {
53 if (auto *CI = dyn_cast<ConstantInt>(Val: V))
54 return CI;
55 return dyn_cast<ConstantFP>(Val: V);
56 };
57 if (Constant *C = GetConstant(BinOp->getOperand(i_nocapture: 1)))
58 return {C, 1};
59 if (!isCommutative(I))
60 return {nullptr, 0};
61 if (Constant *C = GetConstant(BinOp->getOperand(i_nocapture: 0)))
62 return {C, 0};
63 return {nullptr, 0};
64}
65
66bool BinOpSameOpcodeHelper::InterchangeableInfo::trySet(
67 MaskType OpcodeInMaskForm, MaskType InterchangeableMask) {
68 if (Mask & InterchangeableMask) {
69 SeenBefore |= OpcodeInMaskForm;
70 Mask &= InterchangeableMask;
71 return true;
72 }
73 return false;
74}
75
76unsigned BinOpSameOpcodeHelper::InterchangeableInfo::getOpcode() const {
77 MaskType Candidate = Mask & SeenBefore;
78 if (Candidate & MainOpBIT)
79 return I->getOpcode();
80 if (Candidate & ShlBIT)
81 return Instruction::Shl;
82 if (Candidate & AShrBIT)
83 return Instruction::AShr;
84 if (Candidate & MulBIT)
85 return Instruction::Mul;
86 if (Candidate & AddBIT)
87 return Instruction::Add;
88 if (Candidate & SubBIT)
89 return Instruction::Sub;
90 if (Candidate & FAddBIT)
91 return Instruction::FAdd;
92 if (Candidate & FSubBIT)
93 return Instruction::FSub;
94 if (Candidate & AndBIT)
95 return Instruction::And;
96 if (Candidate & OrBIT)
97 return Instruction::Or;
98 if (Candidate & XorBIT)
99 return Instruction::Xor;
100 llvm_unreachable("Cannot find interchangeable instruction.");
101}
102
103bool BinOpSameOpcodeHelper::InterchangeableInfo::hasCandidateOpcode(
104 unsigned Opcode) const {
105 MaskType Candidate = Mask & SeenBefore;
106 switch (Opcode) {
107 case Instruction::Shl:
108 return Candidate & ShlBIT;
109 case Instruction::AShr:
110 return Candidate & AShrBIT;
111 case Instruction::Mul:
112 return Candidate & MulBIT;
113 case Instruction::Add:
114 return Candidate & AddBIT;
115 case Instruction::Sub:
116 return Candidate & SubBIT;
117 case Instruction::And:
118 return Candidate & AndBIT;
119 case Instruction::Or:
120 return Candidate & OrBIT;
121 case Instruction::Xor:
122 return Candidate & XorBIT;
123 case Instruction::FAdd:
124 return Candidate & FAddBIT;
125 case Instruction::FSub:
126 return Candidate & FSubBIT;
127 case Instruction::LShr:
128 case Instruction::FMul:
129 case Instruction::SDiv:
130 case Instruction::UDiv:
131 case Instruction::FDiv:
132 case Instruction::SRem:
133 case Instruction::URem:
134 case Instruction::FRem:
135 return false;
136 default:
137 break;
138 }
139 llvm_unreachable("Cannot find interchangeable instruction.");
140}
141
142SmallVector<Value *> BinOpSameOpcodeHelper::InterchangeableInfo::getOperand(
143 const Instruction *To) const {
144 unsigned ToOpcode = To->getOpcode();
145 unsigned FromOpcode = I->getOpcode();
146 if (FromOpcode == ToOpcode)
147 return SmallVector<Value *>(I->operands());
148 assert(binary_search(SupportedOp, ToOpcode) && "Unsupported opcode.");
149 auto [C, Pos] = isBinOpWithConstant(I);
150 Type *RHSType = I->getOperand(i: Pos)->getType();
151 Constant *RHS;
152 if (auto *CFP = dyn_cast<ConstantFP>(Val: C)) {
153 // fsub(x, c) == fadd(x, -c) for every FP constant c, since IEEE 754
154 // defines subtraction as addition of the negated operand.
155 assert(is_contained({Instruction::FAdd, Instruction::FSub}, ToOpcode) &&
156 "Cannot convert the instruction.");
157 RHS = ConstantFP::get(Ty: RHSType, V: -CFP->getValueAPF());
158 } else {
159 auto *CI = cast<ConstantInt>(Val: C);
160 const APInt &FromCIValue = CI->getValue();
161 unsigned FromCIValueBitWidth = FromCIValue.getBitWidth();
162 switch (FromOpcode) {
163 case Instruction::Shl:
164 if (ToOpcode == Instruction::Add && FromCIValue.isOne())
165 return {I->getOperand(i: 0), I->getOperand(i: 0)};
166 if (ToOpcode == Instruction::Mul) {
167 RHS = ConstantInt::get(Ty: RHSType,
168 V: APInt::getOneBitSet(numBits: FromCIValueBitWidth,
169 BitNo: FromCIValue.getZExtValue()));
170 } else {
171 assert(FromCIValue.isZero() && "Cannot convert the instruction.");
172 RHS = ConstantExpr::getBinOpIdentity(Opcode: ToOpcode, Ty: RHSType,
173 /*AllowRHSConstant=*/true);
174 }
175 break;
176 case Instruction::Mul:
177 assert(FromCIValue.isPowerOf2() && "Cannot convert the instruction.");
178 if (ToOpcode == Instruction::Shl) {
179 RHS = ConstantInt::get(
180 Ty: RHSType, V: APInt(FromCIValueBitWidth, FromCIValue.logBase2()));
181 } else {
182 assert(FromCIValue.isOne() && "Cannot convert the instruction.");
183 RHS = ConstantExpr::getBinOpIdentity(Opcode: ToOpcode, Ty: RHSType,
184 /*AllowRHSConstant=*/true);
185 }
186 break;
187 case Instruction::Add:
188 case Instruction::Sub:
189 if (FromCIValue.isZero()) {
190 RHS = ConstantExpr::getBinOpIdentity(Opcode: ToOpcode, Ty: RHSType,
191 /*AllowRHSConstant=*/true);
192 } else {
193 assert(is_contained({Instruction::Add, Instruction::Sub}, ToOpcode) &&
194 "Cannot convert the instruction.");
195 APInt NegatedVal = APInt(FromCIValue);
196 NegatedVal.negate();
197 RHS = ConstantInt::get(Ty: RHSType, V: NegatedVal);
198 }
199 break;
200 case Instruction::And:
201 assert(FromCIValue.isAllOnes() && "Cannot convert the instruction.");
202 RHS = ConstantExpr::getBinOpIdentity(Opcode: ToOpcode, Ty: RHSType,
203 /*AllowRHSConstant=*/true);
204 break;
205 default:
206 assert(FromCIValue.isZero() && "Cannot convert the instruction.");
207 RHS = ConstantExpr::getBinOpIdentity(Opcode: ToOpcode, Ty: RHSType,
208 /*AllowRHSConstant=*/true);
209 break;
210 }
211 }
212 Value *LHS = I->getOperand(i: 1 - Pos);
213 // If the target opcode is non-commutative (e.g., shl, sub),
214 // force the variable to the left and the constant to the right.
215 if (Pos == 1 || !Instruction::isCommutative(Opcode: ToOpcode))
216 return SmallVector<Value *>({LHS, RHS});
217
218 return SmallVector<Value *>({RHS, LHS});
219}
220
221bool BinOpSameOpcodeHelper::isValidForAlternation(const Instruction *I) const {
222 return slpvectorizer::isValidForAlternation(Opcode: MainOp.I->getOpcode()) &&
223 slpvectorizer::isValidForAlternation(Opcode: I->getOpcode());
224}
225
226bool BinOpSameOpcodeHelper::initializeAltOp(const Instruction *I) {
227 if (AltOp.I)
228 return true;
229 if (!isValidForAlternation(I))
230 return false;
231 AltOp.I = I;
232 return true;
233}
234
235bool BinOpSameOpcodeHelper::add(const Instruction *I) {
236 assert(isa<BinaryOperator>(I) &&
237 "BinOpSameOpcodeHelper only accepts BinaryOperator.");
238 unsigned Opcode = I->getOpcode();
239 MaskType OpcodeInMaskForm;
240 // Prefer Shl, AShr, Mul, Add, Sub, And, Or, Xor, FAdd and FSub over
241 // MainOp.
242 switch (Opcode) {
243 case Instruction::Shl:
244 OpcodeInMaskForm = ShlBIT;
245 break;
246 case Instruction::AShr:
247 OpcodeInMaskForm = AShrBIT;
248 break;
249 case Instruction::Mul:
250 OpcodeInMaskForm = MulBIT;
251 break;
252 case Instruction::Add:
253 OpcodeInMaskForm = AddBIT;
254 break;
255 case Instruction::Sub:
256 OpcodeInMaskForm = SubBIT;
257 break;
258 case Instruction::And:
259 OpcodeInMaskForm = AndBIT;
260 break;
261 case Instruction::Or:
262 OpcodeInMaskForm = OrBIT;
263 break;
264 case Instruction::Xor:
265 OpcodeInMaskForm = XorBIT;
266 break;
267 case Instruction::FAdd:
268 OpcodeInMaskForm = FAddBIT;
269 break;
270 case Instruction::FSub:
271 OpcodeInMaskForm = FSubBIT;
272 break;
273 default:
274 return MainOp.equal(Opcode) || (initializeAltOp(I) && AltOp.equal(Opcode));
275 }
276 MaskType InterchangeableMask = OpcodeInMaskForm;
277 auto [C, Pos] = isBinOpWithConstant(I);
278 if (auto *CI = dyn_cast_if_present<ConstantInt>(Val: C)) {
279 constexpr MaskType CanBeAll =
280 XorBIT | OrBIT | AndBIT | SubBIT | AddBIT | MulBIT | AShrBIT | ShlBIT;
281 const APInt &CIValue = CI->getValue();
282 switch (Opcode) {
283 case Instruction::Shl:
284 if (CIValue.ult(RHS: CIValue.getBitWidth()))
285 InterchangeableMask = CIValue.isZero() ? CanBeAll : MulBIT | ShlBIT;
286 if (CIValue.isOne())
287 InterchangeableMask |= AddBIT;
288 break;
289 case Instruction::Mul:
290 if (CIValue.isOne()) {
291 InterchangeableMask = CanBeAll;
292 break;
293 }
294 if (CIValue.isPowerOf2())
295 InterchangeableMask = MulBIT | ShlBIT;
296 break;
297 case Instruction::Add:
298 case Instruction::Sub:
299 InterchangeableMask = CIValue.isZero() ? CanBeAll : SubBIT | AddBIT;
300 break;
301 case Instruction::And:
302 if (CIValue.isAllOnes())
303 InterchangeableMask = CanBeAll;
304 break;
305 case Instruction::Xor:
306 if (CIValue.isZero())
307 InterchangeableMask = XorBIT | OrBIT | SubBIT | AddBIT;
308 break;
309 default:
310 if (CIValue.isZero())
311 InterchangeableMask = CanBeAll;
312 break;
313 }
314 } else if (C && Pos == 1) {
315 // FAdd/FSub with a constant RHS: negating the constant always
316 // converts one into the other, so no value check is needed. A
317 // constant LHS (Pos == 0, e.g. "0.0 - x") is excluded: unlike a
318 // constant RHS, it cannot be moved to the other opcode without also
319 // swapping the variable operand, which would misalign it against
320 // lanes that keep their native opcode (their variable operand stays
321 // on the other side).
322 InterchangeableMask = FSubBIT | FAddBIT;
323 }
324 return MainOp.trySet(OpcodeInMaskForm, InterchangeableMask) ||
325 (initializeAltOp(I) &&
326 AltOp.trySet(OpcodeInMaskForm, InterchangeableMask));
327}
328
329/// If the comparison (Pred, X, C) is a single-element or single-complement
330/// range check, returns its boundary family: false + K for the singleton
331/// {K} (eq forms), true + K for the complement of {K} (ne forms).
332static std::optional<std::pair<bool, APInt>>
333getCmpBoundaryFamily(CmpInst::Predicate Pred, const APInt &C) {
334 const unsigned BW = C.getBitWidth();
335 const bool IsSigned = CmpInst::isSigned(Pred);
336 const APInt Min = IsSigned ? APInt::getSignedMinValue(numBits: BW) : APInt(BW, 0);
337 const APInt Max =
338 IsSigned ? APInt::getSignedMaxValue(numBits: BW) : APInt::getMaxValue(numBits: BW);
339 switch (Pred) {
340 case CmpInst::ICMP_EQ:
341 return std::make_pair(x: false, y: C);
342 case CmpInst::ICMP_NE:
343 return std::make_pair(x: true, y: C);
344 case CmpInst::ICMP_ULT:
345 case CmpInst::ICMP_SLT:
346 if (C == Min + 1)
347 return std::make_pair(x: false, y: Min);
348 if (C == Max)
349 return std::make_pair(x: true, y: C);
350 break;
351 case CmpInst::ICMP_ULE:
352 case CmpInst::ICMP_SLE:
353 if (C == Min)
354 return std::make_pair(x: false, y: C);
355 if (C == Max - 1)
356 return std::make_pair(x: true, y: Max);
357 break;
358 case CmpInst::ICMP_UGT:
359 case CmpInst::ICMP_SGT:
360 if (C == Min)
361 return std::make_pair(x: true, y: C);
362 if (C == Max - 1)
363 return std::make_pair(x: false, y: Max);
364 break;
365 case CmpInst::ICMP_UGE:
366 case CmpInst::ICMP_SGE:
367 if (C == Min + 1)
368 return std::make_pair(x: true, y: Min);
369 if (C == Max)
370 return std::make_pair(x: false, y: C);
371 break;
372 default:
373 break;
374 }
375 return std::nullopt;
376}
377
378CmpSamePredicateHelper::MaskType
379CmpSamePredicateHelper::getFormsMask(CmpInst::Predicate Pred, const APInt &C) {
380 MaskType M = getBit(P: Pred);
381 std::optional<std::pair<bool, APInt>> Family = getCmpBoundaryFamily(Pred, C);
382 if (!Family)
383 return M;
384 const auto &[IsComplement, K] = *Family;
385 // At each type boundary the two range checks covering exactly {K}; the
386 // complement family uses their inverses, covering everything but {K}.
387 const MaskType LoU = getBit(P: CmpInst::ICMP_ULT) | getBit(P: CmpInst::ICMP_ULE);
388 const MaskType HiU = getBit(P: CmpInst::ICMP_UGT) | getBit(P: CmpInst::ICMP_UGE);
389 const MaskType LoS = getBit(P: CmpInst::ICMP_SLT) | getBit(P: CmpInst::ICMP_SLE);
390 const MaskType HiS = getBit(P: CmpInst::ICMP_SGT) | getBit(P: CmpInst::ICMP_SGE);
391 if (K.isZero())
392 M |= IsComplement ? HiU : LoU;
393 if (K.isMaxValue())
394 M |= IsComplement ? LoU : HiU;
395 if (K.isMinSignedValue())
396 M |= IsComplement ? HiS : LoS;
397 if (K.isMaxSignedValue())
398 M |= IsComplement ? LoS : HiS;
399 return M | getBit(P: IsComplement ? CmpInst::ICMP_NE : CmpInst::ICMP_EQ);
400}
401
402APInt CmpSamePredicateHelper::getFamilyConstant(bool IsComplement,
403 const APInt &K,
404 CmpInst::Predicate Pred) {
405 if (Pred == CmpInst::ICMP_EQ || Pred == CmpInst::ICMP_NE)
406 return K;
407 // The complement form uses the singleton constant of the inverse
408 // predicate.
409 if (IsComplement)
410 Pred = CmpInst::getInversePredicate(pred: Pred);
411 switch (Pred) {
412 case CmpInst::ICMP_ULT:
413 case CmpInst::ICMP_SLT:
414 return K + 1;
415 case CmpInst::ICMP_UGT:
416 case CmpInst::ICMP_SGT:
417 return K - 1;
418 default:
419 return K;
420 }
421}
422
423bool CmpSamePredicateHelper::add(const ICmpInst *CI) {
424 MaskType LaneMask = getBit(P: CI->getPredicate());
425 if (auto *C = dyn_cast<ConstantInt>(Val: CI->getOperand(i_nocapture: 1)))
426 LaneMask = getFormsMask(Pred: CI->getPredicate(), C: C->getValue());
427 SeenBefore |= getBit(P: CI->getPredicate());
428 Mask &= LaneMask;
429 return Mask != 0;
430}
431
432CmpInst::Predicate
433CmpSamePredicateHelper::getPredicate(const ICmpInst *Preferred) const {
434 MaskType Candidate = Mask & SeenBefore;
435 if (!Candidate)
436 return CmpInst::BAD_ICMP_PREDICATE;
437 if (Candidate & getBit(P: Preferred->getPredicate()))
438 return Preferred->getPredicate();
439 return static_cast<CmpInst::Predicate>(CmpInst::ICMP_EQ +
440 countr_zero(Val: Candidate));
441}
442
443CmpInst::Predicate
444CmpSamePredicateHelper::getSharedPredicate(ArrayRef<Value *> VL,
445 const ICmpInst *Preferred) {
446 CmpSamePredicateHelper Helper;
447 if (!all_of(Range&: VL, P: [&](Value *V) {
448 auto *CI = dyn_cast<ICmpInst>(Val: V);
449 return isa<PoisonValue>(Val: V) || (CI && Helper.add(CI));
450 }))
451 return CmpInst::BAD_ICMP_PREDICATE;
452 return Helper.getPredicate(Preferred);
453}
454
455bool CmpSamePredicateHelper::canConvertTo(const CmpInst *CI,
456 CmpInst::Predicate Pred) {
457 auto *ICI = dyn_cast<ICmpInst>(Val: CI);
458 if (!ICI || !CmpInst::isIntPredicate(P: Pred))
459 return false;
460 if (ICI->getPredicate() == Pred)
461 return true;
462 auto *C = dyn_cast<ConstantInt>(Val: ICI->getOperand(i_nocapture: 1));
463 return C &&
464 (getFormsMask(Pred: ICI->getPredicate(), C: C->getValue()) & getBit(P: Pred)) != 0;
465}
466
467ConstantInt *
468CmpSamePredicateHelper::getAdjustedConstant(const CmpInst *CI,
469 CmpInst::Predicate Pred) {
470 if (!canConvertTo(CI, Pred))
471 return nullptr;
472 auto *ICI = cast<ICmpInst>(Val: CI);
473 if (ICI->getPredicate() == Pred)
474 return nullptr;
475 auto *C = cast<ConstantInt>(Val: ICI->getOperand(i_nocapture: 1));
476 std::optional<std::pair<bool, APInt>> Family =
477 getCmpBoundaryFamily(Pred: ICI->getPredicate(), C: C->getValue());
478 assert(Family && "Expected a boundary family for a convertible compare.");
479 const auto &[IsComplement, K] = *Family;
480 return ConstantInt::get(Context&: CI->getContext(),
481 V: getFamilyConstant(IsComplement, K, Pred));
482}
483
484bool InstructionsState::isSameOperation(const Instruction *I,
485 const Instruction *Op) {
486 if (I->getOpcode() != Op->getOpcode())
487 return false;
488 const auto *II = dyn_cast<IntrinsicInst>(Val: I);
489 const auto *IOp = dyn_cast<IntrinsicInst>(Val: Op);
490 if (II || IOp)
491 return II && IOp &&
492 isEquivalentIntrinsicID(LHS: II->getIntrinsicID(),
493 RHS: IOp->getIntrinsicID()) !=
494 Intrinsic::not_intrinsic;
495 return true;
496}
497
498Instruction *InstructionsState::getMatchingMainOpOrAltOp(Instruction *I) const {
499 assert(MainOp && "MainOp cannot be nullptr.");
500 if (isSameOperation(I, Op: MainOp))
501 return MainOp;
502 if (MainOp->getOpcode() == Instruction::Select &&
503 I->getOpcode() == Instruction::ZExt && !isAltShuffle())
504 return MainOp;
505 // Prefer AltOp instead of interchangeable instruction of MainOp.
506 assert(AltOp && "AltOp cannot be nullptr.");
507 if (isSameOperation(I, Op: AltOp))
508 return AltOp;
509 // BinOpSameOpcodeHelper handles only BinaryOperators; a call cannot match.
510 if (!I->isBinaryOp() || !MainOp->isBinaryOp())
511 return nullptr;
512 BinOpSameOpcodeHelper Converter(MainOp);
513 if (!Converter.add(I) || !Converter.add(I: MainOp))
514 return nullptr;
515 if (isAltShuffle() && !Converter.hasCandidateOpcode(Opcode: MainOp->getOpcode())) {
516 BinOpSameOpcodeHelper AltConverter(AltOp);
517 if (AltConverter.add(I) && AltConverter.add(I: AltOp) &&
518 AltConverter.hasCandidateOpcode(Opcode: AltOp->getOpcode()))
519 return AltOp;
520 }
521 if (Converter.hasAltOp() && !isAltShuffle())
522 return nullptr;
523 return Converter.hasAltOp() ? AltOp : MainOp;
524}
525
526bool InstructionsState::isMulDivLikeOp() const {
527 constexpr std::array<unsigned, 8> MulDiv = {
528 Instruction::Mul, Instruction::FMul, Instruction::SDiv,
529 Instruction::UDiv, Instruction::FDiv, Instruction::SRem,
530 Instruction::URem, Instruction::FRem};
531 return is_contained(Range: MulDiv, Element: getOpcode()) &&
532 is_contained(Range: MulDiv, Element: getAltOpcode());
533}
534
535bool InstructionsState::isAddSubLikeOp() const {
536 constexpr std::array<unsigned, 4> AddSub = {
537 Instruction::Add, Instruction::Sub, Instruction::FAdd, Instruction::FSub};
538 return is_contained(Range: AddSub, Element: getOpcode()) &&
539 is_contained(Range: AddSub, Element: getAltOpcode());
540}
541
542bool InstructionsState::isAddSubOrFNegLikeOp() const {
543 return isAddSubLikeOp() || getOpcode() == Instruction::FNeg;
544}
545
546bool InstructionsState::isCopyableElement(Value *V) const {
547 assert(valid() && "InstructionsState is invalid.");
548 if (!HasCopyables)
549 return false;
550 if (isAltShuffle())
551 return false;
552 auto *I = dyn_cast<Instruction>(Val: V);
553 // Copyable lanes of a cast node are limited to constants representable as
554 // the cast of a source-type constant.
555 if (isa<CastInst>(Val: MainOp)) {
556 if (I || isa<PoisonValue>(Val: V))
557 return false;
558 if (isa<UndefValue>(Val: V))
559 return true;
560 auto *C = dyn_cast<ConstantInt>(Val: V);
561 return C && C->getValue().getActiveBits() <=
562 cast<CastInst>(Val: MainOp)->getSrcTy()->getIntegerBitWidth();
563 }
564 if (!I)
565 return !isa<PoisonValue>(Val: V);
566 // For a GEP main op only single-index GEPs with the same source element
567 // type can be matching lanes; GEPs with a different shape are copyable.
568 if (getOpcode() == Instruction::GetElementPtr)
569 if (auto *GEP = dyn_cast<GetElementPtrInst>(Val: I);
570 GEP && (GEP->getNumOperands() != 2 ||
571 GEP->getSourceElementType() !=
572 cast<GetElementPtrInst>(Val: MainOp)->getSourceElementType()))
573 return true;
574 if (I->getParent() != MainOp->getParent() &&
575 (!isVectorLikeInstWithConstOps(V: I) ||
576 !isVectorLikeInstWithConstOps(V: MainOp)))
577 return true;
578 if (isSameOperation(I, Op: MainOp))
579 return false;
580 // BinOpSameOpcodeHelper handles only BinaryOperators; a call is copyable.
581 if (!I->isBinaryOp() || !MainOp->isBinaryOp())
582 return true;
583 BinOpSameOpcodeHelper Converter(MainOp);
584 return !Converter.add(I) || !Converter.add(I: MainOp) || Converter.hasAltOp() ||
585 !Converter.hasCandidateOpcode(Opcode: getOpcode());
586}
587
588bool isAbsorbableFMulOrFAdd(ArrayRef<Value *> VL, Value *V) {
589 auto *I = dyn_cast<Instruction>(Val: V);
590 return I &&
591 (I->getOpcode() == Instruction::FMul ||
592 I->getOpcode() == Instruction::FAdd) &&
593 I->hasOneUse() && none_of(Range: I->operands(), P: [&](Value *Op) {
594 return is_contained(Range&: VL, Element: Op);
595 });
596}
597
598bool isAbsorbableCopyableFMulOrFAdd(const InstructionsState &S, Value *V) {
599 auto *I = dyn_cast<Instruction>(Val: V);
600 return I && S.isCopyableElement(V: I) &&
601 (I->getOpcode() == Instruction::FMul ||
602 I->getOpcode() == Instruction::FAdd) &&
603 I->hasOneUse();
604}
605
606bool hasOnlyAbsorbableCopyableFMulOrFAdds(ArrayRef<Value *> VL) {
607 bool HasFMulOrFAdd = false;
608 for (Value *V :
609 make_filter_range(Range&: VL, Pred: [](Value *V) { return !isa<PoisonValue>(Val: V); })) {
610 auto *I = dyn_cast<Instruction>(Val: V);
611 if (I && RecurrenceDescriptor::isFMulAddIntrinsic(I))
612 continue;
613 if (!isAbsorbableFMulOrFAdd(VL, V))
614 return false;
615 HasFMulOrFAdd = true;
616 }
617 return HasFMulOrFAdd;
618}
619
620bool InstructionsState::isExpandedBinOp(Value *V) const {
621 assert(valid() && "InstructionsState is invalid.");
622 if (isCopyableElement(V))
623 return false;
624 auto *ExpandingOp = dyn_cast<Instruction>(Val: V);
625 if (!ExpandingOp)
626 return false;
627 auto CheckForTransformedOpcode = [](const Instruction *RefOp,
628 const Instruction *ExpandingOp) {
629 switch (RefOp->getOpcode()) {
630 case Instruction::Add:
631 switch (ExpandingOp->getOpcode()) {
632 case Instruction::Shl:
633 return match(V: ExpandingOp, P: m_Shl(L: m_Value(), R: m_One()));
634 default:
635 break;
636 }
637 break;
638 default:
639 break;
640 }
641 return false;
642 };
643 // getMatchingMainOpOrAltOp() may legitimately return nullptr, e.g. for a
644 // split node, whose Scalars combine two unrelated operations (main/alt
645 // ops of the split state), so V is not required to match either of them.
646 Instruction *MainOp = getMatchingMainOpOrAltOp(I: ExpandingOp);
647 if (!MainOp)
648 return false;
649 return CheckForTransformedOpcode(MainOp, ExpandingOp);
650}
651
652bool InstructionsState::isExpandedOperand(Instruction *I, unsigned Idx) const {
653 assert(isExpandedBinOp(I) && "Expected an expanded binop.");
654 switch (I->getOpcode()) {
655 case Instruction::Shl:
656 assert(match(I, m_Shl(m_Value(), m_One())) && "Expected shl x, 1 only.");
657 return Idx == 1;
658 default:
659 llvm_unreachable("Unexpected opcode for an expanded operand.");
660 }
661}
662
663bool InstructionsState::isNonSchedulable(Value *V) const {
664 assert(valid() && "InstructionsState is invalid.");
665 auto *I = dyn_cast<Instruction>(Val: V);
666 if (!HasCopyables)
667 return !I || isa<PHINode>(Val: I) || isVectorLikeInstWithConstOps(V: I) ||
668 doesNotNeedToBeScheduled(V);
669 // MainOp for copyables always schedulable to correctly identify
670 // non-schedulable copyables.
671 if (getMainOp() == V)
672 return false;
673 if (isCopyableElement(V)) {
674 auto IsNonSchedulableCopyableElement = [this](Value *V) {
675 auto *I = dyn_cast<Instruction>(Val: V);
676 return !I || isa<PHINode>(Val: I) || I->getParent() != MainOp->getParent() ||
677 (doesNotNeedToBeScheduled(V: I) &&
678 // If the copyable instructions comes after MainOp
679 // (non-schedulable, but used in the block) - cannot vectorize
680 // it, will possibly generate use before def.
681 !MainOp->comesBefore(Other: I));
682 };
683
684 return IsNonSchedulableCopyableElement(V);
685 }
686 return !I || isa<PHINode>(Val: I) || isVectorLikeInstWithConstOps(V: I) ||
687 doesNotNeedToBeScheduled(V);
688}
689
690/// Find an instruction with a specific opcode in VL.
691/// \param VL Array of values to search through. Must contain only Instructions
692/// and PoisonValues.
693/// \param Opcode The instruction opcode to search for
694/// \returns
695/// - The first instruction found with matching opcode
696/// - nullptr if no matching instruction is found
697static Instruction *findInstructionWithOpcode(ArrayRef<Value *> VL,
698 unsigned Opcode) {
699 for (Value *V :
700 make_filter_range(Range&: VL, Pred: [](Value *V) { return !isa<PoisonValue>(Val: V); })) {
701 assert(isa<Instruction>(V) && "Only accepts PoisonValue and Instruction.");
702 auto *Inst = cast<Instruction>(Val: V);
703 if (Inst->getOpcode() == Opcode)
704 return Inst;
705 }
706 return nullptr;
707}
708
709/// Checks if the provided operands of 2 cmp instructions are compatible, i.e.
710/// compatible instructions or constants, or just some other regular values.
711static bool areCompatibleCmpOps(Value *BaseOp0, Value *BaseOp1, Value *Op0,
712 Value *Op1, const TargetLibraryInfo &TLI) {
713 return (isConstant(V: BaseOp0) && isConstant(V: Op0)) ||
714 (isConstant(V: BaseOp1) && isConstant(V: Op1)) ||
715 (!isa<Instruction>(Val: BaseOp0) && !isa<Instruction>(Val: Op0) &&
716 !isa<Instruction>(Val: BaseOp1) && !isa<Instruction>(Val: Op1)) ||
717 BaseOp0 == Op0 || BaseOp1 == Op1 ||
718 getSameOpcode(VL: {BaseOp0, Op0}, TLI) ||
719 getSameOpcode(VL: {BaseOp1, Op1}, TLI);
720}
721
722/// \returns true if a compare instruction \p CI has similar "look" and
723/// same predicate as \p BaseCI, "as is" or with its operands and predicate
724/// swapped, false otherwise.
725static bool isCmpSameOrSwapped(const CmpInst *BaseCI, const CmpInst *CI,
726 const TargetLibraryInfo &TLI) {
727 assert(BaseCI->getOperand(0)->getType() == CI->getOperand(0)->getType() &&
728 "Assessing comparisons of different types?");
729 CmpInst::Predicate BasePred = BaseCI->getPredicate();
730 CmpInst::Predicate Pred = CI->getPredicate();
731 CmpInst::Predicate SwappedPred = CmpInst::getSwappedPredicate(pred: Pred);
732
733 Value *BaseOp0 = BaseCI->getOperand(i_nocapture: 0);
734 Value *BaseOp1 = BaseCI->getOperand(i_nocapture: 1);
735 Value *Op0 = CI->getOperand(i_nocapture: 0);
736 Value *Op1 = CI->getOperand(i_nocapture: 1);
737
738 return (BasePred == Pred &&
739 areCompatibleCmpOps(BaseOp0, BaseOp1, Op0, Op1, TLI)) ||
740 (BasePred == SwappedPred &&
741 areCompatibleCmpOps(BaseOp0, BaseOp1, Op0: Op1, Op1: Op0, TLI));
742}
743
744InstructionsState getSameOpcode(ArrayRef<Value *> VL,
745 const TargetLibraryInfo &TLI) {
746 // Make sure these are all Instructions.
747 if (!all_of(Range&: VL, P: IsaPred<Instruction, PoisonValue>))
748 return InstructionsState::invalid();
749
750 auto *It = find_if(Range&: VL, P: IsaPred<Instruction>);
751 if (It == VL.end())
752 return InstructionsState::invalid();
753
754 Instruction *MainOp = cast<Instruction>(Val: *It);
755 unsigned InstCnt = std::count_if(first: It, last: VL.end(), pred: IsaPred<Instruction>);
756 if ((VL.size() > 2 && !isa<PHINode>(Val: MainOp) && InstCnt < VL.size() / 2) ||
757 (VL.size() == 2 && InstCnt < 2))
758 return InstructionsState::invalid();
759
760 bool IsCastOp = isa<CastInst>(Val: MainOp);
761 bool IsBinOp = isa<BinaryOperator>(Val: MainOp);
762 bool IsCmpOp = isa<CmpInst>(Val: MainOp);
763 CmpInst::Predicate BasePred = IsCmpOp ? cast<CmpInst>(Val: MainOp)->getPredicate()
764 : CmpInst::BAD_ICMP_PREDICATE;
765 Instruction *AltOp = MainOp;
766 unsigned Opcode = MainOp->getOpcode();
767 unsigned AltOpcode = Opcode;
768
769 BinOpSameOpcodeHelper BinOpHelper(MainOp);
770 bool SwappedPredsCompatible = IsCmpOp && [&]() {
771 SetVector<unsigned> UniquePreds, UniqueNonSwappedPreds;
772 UniquePreds.insert(X: BasePred);
773 UniqueNonSwappedPreds.insert(X: BasePred);
774 for (Value *V : VL) {
775 auto *I = dyn_cast<CmpInst>(Val: V);
776 if (!I)
777 return false;
778 CmpInst::Predicate CurrentPred = I->getPredicate();
779 CmpInst::Predicate SwappedCurrentPred =
780 CmpInst::getSwappedPredicate(pred: CurrentPred);
781 UniqueNonSwappedPreds.insert(X: CurrentPred);
782 if (!UniquePreds.contains(key: CurrentPred) &&
783 !UniquePreds.contains(key: SwappedCurrentPred))
784 UniquePreds.insert(X: CurrentPred);
785 }
786 // Total number of predicates > 2, but if consider swapped predicates
787 // compatible only 2, consider swappable predicates as compatible opcodes,
788 // not alternate.
789 return UniqueNonSwappedPreds.size() > 2 && UniquePreds.size() == 2;
790 }();
791 // Find the predicate the whole bundle can share, if any, treating
792 // boundary comparisons canonicalized to eq/ne as interchangeable.
793 CmpInst::Predicate InterchangeablePred = CmpInst::BAD_ICMP_PREDICATE;
794 if (IsCmpOp && isa<ICmpInst>(Val: MainOp))
795 InterchangeablePred =
796 CmpSamePredicateHelper::getSharedPredicate(VL, Preferred: cast<ICmpInst>(Val: MainOp));
797 // Check for one alternate opcode from another BinaryOperator.
798 // TODO - generalize to support all operators (types, calls etc.).
799 Intrinsic::ID BaseID = 0;
800 SmallVector<VFInfo, 4> BaseMappings;
801 if (auto *CallBase = dyn_cast<CallInst>(Val: MainOp)) {
802 BaseID = getVectorIntrinsicIDForCall(CI: CallBase, TLI: &TLI);
803 BaseMappings = VFDatabase(*CallBase).getMappings(CI: *CallBase);
804 if (!isTriviallyVectorizable(ID: BaseID) && BaseMappings.empty())
805 return InstructionsState::invalid();
806 }
807 bool AnyPoison = InstCnt != VL.size();
808 // Check MainOp too to be sure that it matches the requirements for the
809 // instructions.
810 for (Instruction *I :
811 make_isa_range<Instruction>(Range: iterator_range(It, VL.end()))) {
812 // Cannot combine poison and divisions.
813 // TODO: do some smart analysis of the CallInsts to exclude divide-like
814 // intrinsics/functions only.
815 if (AnyPoison && (I->isIntDivRem() || I->isFPDivRem() || isa<CallInst>(Val: I)))
816 return InstructionsState::invalid();
817 unsigned InstOpcode = I->getOpcode();
818 if (IsBinOp && isa<BinaryOperator>(Val: I)) {
819 if (BinOpHelper.add(I))
820 continue;
821 } else if (IsCastOp && isa<CastInst>(Val: I)) {
822 Value *Op0 = MainOp->getOperand(i: 0);
823 Type *Ty0 = Op0->getType();
824 Value *Op1 = I->getOperand(i: 0);
825 Type *Ty1 = Op1->getType();
826 if (Ty0 == Ty1) {
827 if (InstOpcode == Opcode || InstOpcode == AltOpcode)
828 continue;
829 if (Opcode == AltOpcode) {
830 assert(isValidForAlternation(Opcode) &&
831 isValidForAlternation(InstOpcode) &&
832 "Cast isn't safe for alternation, logic needs to be updated!");
833 AltOpcode = InstOpcode;
834 AltOp = I;
835 continue;
836 }
837 }
838 } else if (auto *Inst = dyn_cast<CmpInst>(Val: I); Inst && IsCmpOp) {
839 auto *BaseInst = cast<CmpInst>(Val: MainOp);
840 Type *Ty0 = BaseInst->getOperand(i_nocapture: 0)->getType();
841 Type *Ty1 = Inst->getOperand(i_nocapture: 0)->getType();
842 if (Ty0 == Ty1) {
843 assert(InstOpcode == Opcode && "Expected same CmpInst opcode.");
844 assert(InstOpcode == AltOpcode &&
845 "Alternate instructions are only supported by BinaryOperator "
846 "and CastInst.");
847 // Check for compatible operands. If the corresponding operands are not
848 // compatible - need to perform alternate vectorization.
849 CmpInst::Predicate CurrentPred = Inst->getPredicate();
850 CmpInst::Predicate SwappedCurrentPred =
851 CmpInst::getSwappedPredicate(pred: CurrentPred);
852
853 if ((VL.size() == 2 || SwappedPredsCompatible) &&
854 (BasePred == CurrentPred || BasePred == SwappedCurrentPred))
855 continue;
856
857 if (isCmpSameOrSwapped(BaseCI: BaseInst, CI: Inst, TLI))
858 continue;
859 if (CmpSamePredicateHelper::canConvertTo(CI: Inst, Pred: InterchangeablePred))
860 continue;
861 auto *AltInst = cast<CmpInst>(Val: AltOp);
862 if (MainOp != AltOp) {
863 if (isCmpSameOrSwapped(BaseCI: AltInst, CI: Inst, TLI))
864 continue;
865 } else if (BasePred != CurrentPred) {
866 assert(
867 isValidForAlternation(InstOpcode) &&
868 "CmpInst isn't safe for alternation, logic needs to be updated!");
869 AltOp = I;
870 continue;
871 }
872 CmpInst::Predicate AltPred = AltInst->getPredicate();
873 if (BasePred == CurrentPred || BasePred == SwappedCurrentPred ||
874 AltPred == CurrentPred || AltPred == SwappedCurrentPred)
875 continue;
876 }
877 } else if (InstOpcode == Opcode) {
878 assert(InstOpcode == AltOpcode &&
879 "Alternate instructions are only supported by BinaryOperator and "
880 "CastInst.");
881 if (auto *Gep = dyn_cast<GetElementPtrInst>(Val: I)) {
882 if (Gep->getNumOperands() != 2 ||
883 Gep->getOperand(i_nocapture: 0)->getType() != MainOp->getOperand(i: 0)->getType())
884 return InstructionsState::invalid();
885 } else if (auto *EI = dyn_cast<ExtractElementInst>(Val: I)) {
886 if (!isVectorLikeInstWithConstOps(V: EI))
887 return InstructionsState::invalid();
888 } else if (auto *LI = dyn_cast<LoadInst>(Val: I)) {
889 auto *BaseLI = cast<LoadInst>(Val: MainOp);
890 if (!LI->isSimple() || !BaseLI->isSimple())
891 return InstructionsState::invalid();
892 } else if (auto *Call = dyn_cast<CallInst>(Val: I)) {
893 auto *CallBase = cast<CallInst>(Val: MainOp);
894 Intrinsic::ID ID = getVectorIntrinsicIDForCall(CI: Call, TLI: &TLI);
895 Intrinsic::ID Equivalent = isEquivalentIntrinsicID(LHS: ID, RHS: BaseID);
896 if (Call->getCalledFunction() != CallBase->getCalledFunction() &&
897 isEquivalentIntrinsicID(LHS: Equivalent, RHS: Intrinsic::fmuladd) ==
898 Intrinsic::not_intrinsic)
899 return InstructionsState::invalid();
900 if (Call->hasOperandBundles() &&
901 (!CallBase->hasOperandBundles() ||
902 !std::equal(first1: Call->op_begin() + Call->getBundleOperandsStartIndex(),
903 last1: Call->op_begin() + Call->getBundleOperandsEndIndex(),
904 first2: CallBase->op_begin() +
905 CallBase->getBundleOperandsStartIndex())))
906 return InstructionsState::invalid();
907 if (ID != BaseID && Equivalent == Intrinsic::not_intrinsic)
908 return InstructionsState::invalid();
909 if (!ID) {
910 SmallVector<VFInfo, 4> Mappings =
911 VFDatabase(*Call).getMappings(CI: *Call);
912 if (Mappings.size() != BaseMappings.size() ||
913 Mappings.front().ISA != BaseMappings.front().ISA ||
914 Mappings.front().ScalarName != BaseMappings.front().ScalarName ||
915 Mappings.front().VectorName != BaseMappings.front().VectorName ||
916 Mappings.front().Shape.VF != BaseMappings.front().Shape.VF ||
917 Mappings.front().Shape.Parameters !=
918 BaseMappings.front().Shape.Parameters)
919 return InstructionsState::invalid();
920 }
921 }
922 continue;
923 }
924 return InstructionsState::invalid();
925 }
926
927 if (IsBinOp) {
928 if (!BinOpHelper.hasDefinedMainOpcode() ||
929 !BinOpHelper.hasDefinedAltOpcode())
930 return InstructionsState::invalid();
931 MainOp = findInstructionWithOpcode(VL, Opcode: BinOpHelper.getMainOpcode());
932 assert(MainOp && "Cannot find MainOp with Opcode from BinOpHelper.");
933 AltOp = findInstructionWithOpcode(VL, Opcode: BinOpHelper.getAltOpcode());
934 assert(AltOp && "Cannot find AltOp with Opcode from BinOpHelper.");
935 } else if (auto *CB = dyn_cast<CallInst>(Val: MainOp);
936 CB &&
937 getVectorIntrinsicIDForCall(CI: CB, TLI: &TLI) == Intrinsic::fmuladd) {
938 // fma and fmuladd share a single vector fma node; use the fma as the
939 // representative so the fused form is not weakened to fmuladd.
940 auto *It = find_if(Range&: VL, P: [&](Value *V) {
941 auto *CI = dyn_cast<CallInst>(Val: V);
942 return CI && getVectorIntrinsicIDForCall(CI, TLI: &TLI) == Intrinsic::fma;
943 });
944 if (It != VL.end())
945 MainOp = AltOp = cast<Instruction>(Val: *It);
946 }
947 if (IsCmpOp && InterchangeablePred != CmpInst::BAD_ICMP_PREDICATE &&
948 InterchangeablePred != BasePred) {
949 // Every lane is convertible to the shared predicate, so the alternate
950 // operation is never set for such bundles.
951 auto *SharedIt = find_if(Range&: VL, P: [&](Value *V) {
952 auto *CI = dyn_cast<ICmpInst>(Val: V);
953 return CI && CI->getPredicate() == InterchangeablePred;
954 });
955 assert(SharedIt != VL.end() &&
956 "Expected an instruction with the shared predicate.");
957 MainOp = AltOp = cast<Instruction>(Val: *SharedIt);
958 }
959 assert((MainOp == AltOp || !allSameOpcode(VL)) &&
960 "Incorrect implementation of allSameOpcode.");
961 InstructionsState S(MainOp, AltOp);
962 assert(all_of(VL,
963 [&](Value *V) {
964 return isa<PoisonValue>(V) ||
965 S.getMatchingMainOpOrAltOp(cast<Instruction>(V));
966 }) &&
967 "Invalid InstructionsState.");
968 return S;
969}
970
971std::pair<Instruction *, SmallVector<Value *>>
972convertTo(Instruction *I, const InstructionsState &S) {
973 Instruction *SelectedOp = S.getMatchingMainOpOrAltOp(I);
974 assert(SelectedOp && "Cannot convert the instruction.");
975 if (I->isBinaryOp()) {
976 BinOpSameOpcodeHelper Converter(I);
977 return std::make_pair(x&: SelectedOp, y: Converter.getOperand(I: SelectedOp));
978 }
979 // Use args() to skip the trailing callee operand in CallInst::operands().
980 if (auto *CI = dyn_cast<CallInst>(Val: I))
981 return std::make_pair(x&: SelectedOp, y: SmallVector<Value *>(CI->args()));
982 // A comparison lane interchangeable with the main operation (e.g. x == 0
983 // in an x <u C bundle) is emitted with the main predicate and the
984 // adjusted constant.
985 if (auto *MainCI = dyn_cast<ICmpInst>(Val: SelectedOp);
986 MainCI && !S.isAltShuffle())
987 if (ConstantInt *C = CmpSamePredicateHelper::getAdjustedConstant(
988 CI: cast<ICmpInst>(Val: I), Pred: MainCI->getPredicate()))
989 return std::make_pair(x&: SelectedOp,
990 y: SmallVector<Value *>{I->getOperand(i: 0), C});
991 return std::make_pair(x&: SelectedOp, y: SmallVector<Value *>(I->operands()));
992}
993
994bool isAlternateInstruction(Instruction *I, Instruction *MainOp,
995 Instruction *AltOp, const TargetLibraryInfo &TLI) {
996 if (auto *MainCI = dyn_cast<CmpInst>(Val: MainOp)) {
997 auto *AltCI = cast<CmpInst>(Val: AltOp);
998 CmpInst::Predicate MainP = MainCI->getPredicate();
999 [[maybe_unused]] CmpInst::Predicate AltP = AltCI->getPredicate();
1000 assert(MainP != AltP && "Expected different main/alternate predicates.");
1001 auto *CI = cast<CmpInst>(Val: I);
1002 if (isCmpSameOrSwapped(BaseCI: MainCI, CI, TLI))
1003 return false;
1004 if (isCmpSameOrSwapped(BaseCI: AltCI, CI, TLI))
1005 return true;
1006 CmpInst::Predicate P = CI->getPredicate();
1007 CmpInst::Predicate SwappedP = CmpInst::getSwappedPredicate(pred: P);
1008
1009 assert((MainP == P || AltP == P || MainP == SwappedP || AltP == SwappedP) &&
1010 "CmpInst expected to match either main or alternate predicate or "
1011 "their swap.");
1012 return MainP != P && MainP != SwappedP;
1013 }
1014 return InstructionsState(MainOp, AltOp).getMatchingMainOpOrAltOp(I) == AltOp;
1015}
1016
1017SmallVector<SmallVector<Value *>> scanAltAssociativeOperands(
1018 const InstructionsState &S, const TargetLibraryInfo &TLI,
1019 ArrayRef<Value *> VL, ArrayRef<Value *> Op0, ArrayRef<Value *> Op1,
1020 SmallVectorImpl<Value *> &ReassocScalars, SmallBitVector &SubLanes) {
1021 assert(S.isAltShuffle() && "Expected an alternate node.");
1022 const unsigned NumLanes = VL.size();
1023 SmallVector<unsigned> LaneOpcodes =
1024 map_to_vector(C: seq<unsigned>(Size: NumLanes), F: [&](unsigned Lane) {
1025 return isAlternateInstruction(I: cast<Instruction>(Val: VL[Lane]),
1026 MainOp: S.getMainOp(), AltOp: S.getAltOp(), TLI)
1027 ? S.getAltOpcode()
1028 : S.getOpcode();
1029 });
1030 // A lane value peels only as a single-use chain link with the lane's own
1031 // opcode, keeping every combine level on the same main/alt pattern.
1032 auto GetChainLink = [&](unsigned Lane, Value *V) -> Instruction * {
1033 auto *I = dyn_cast<Instruction>(Val: V);
1034 if (!I || !I->hasOneUse() || I->getOpcode() != LaneOpcodes[Lane] ||
1035 !isReassocChainLink(I))
1036 return nullptr;
1037 return I;
1038 };
1039 SmallVector<SmallVector<Value *>> Columns;
1040 Columns.emplace_back(Args: Op0.begin(), Args: Op0.end());
1041 Columns.emplace_back(Args: Op1.begin(), Args: Op1.end());
1042 // The chain link of a commutative lane may sit in the second column;
1043 // normalize so every lane's link leads.
1044 for (unsigned Lane : seq<unsigned>(Size: NumLanes)) {
1045 if (GetChainLink(Lane, Columns[0][Lane]))
1046 continue;
1047 Instruction *Link = GetChainLink(Lane, Columns[1][Lane]);
1048 if (!Link || !Link->isCommutative())
1049 return {};
1050 std::swap(a&: Columns[0][Lane], b&: Columns[1][Lane]);
1051 }
1052 // Peel the leading column while every lane stays a matching chain link.
1053 while (all_of(Range: seq<unsigned>(Size: NumLanes), P: [&](unsigned Lane) {
1054 return GetChainLink(Lane, Columns[0][Lane]) != nullptr;
1055 })) {
1056 SmallVector<Value *> NewColumn(NumLanes);
1057 for (unsigned Lane : seq<unsigned>(Size: NumLanes)) {
1058 Instruction *Link = GetChainLink(Lane, Columns[0][Lane]);
1059 ReassocScalars.push_back(Elt: Link);
1060 // The chain of a commutative lane may continue in the second operand;
1061 // keep the chain link as the running value.
1062 unsigned RunningOp = Link->isCommutative() &&
1063 !GetChainLink(Lane, Link->getOperand(i: 0)) &&
1064 GetChainLink(Lane, Link->getOperand(i: 1))
1065 ? 1
1066 : 0;
1067 NewColumn[Lane] = Link->getOperand(i: 1 - RunningOp);
1068 Columns[0][Lane] = Link->getOperand(i: RunningOp);
1069 }
1070 Columns.insert(I: std::next(x: Columns.begin()), Elt: std::move(NewColumn));
1071 }
1072 assert(!ReassocScalars.empty() &&
1073 "Normalization guarantees at least one peeled level.");
1074 SubLanes.resize(N: NumLanes);
1075 for (unsigned Lane : seq<unsigned>(Size: NumLanes))
1076 if (LaneOpcodes[Lane] == Instruction::Sub ||
1077 LaneOpcodes[Lane] == Instruction::FSub)
1078 SubLanes.set(Lane);
1079 return Columns;
1080}
1081} // namespace llvm::slpvectorizer
1082