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_or_null<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::isCopyableElement(Value *V) const {
543 assert(valid() && "InstructionsState is invalid.");
544 if (!HasCopyables)
545 return false;
546 if (isAltShuffle() || getOpcode() == Instruction::GetElementPtr)
547 return false;
548 auto *I = dyn_cast<Instruction>(Val: V);
549 if (!I)
550 return !isa<PoisonValue>(Val: V);
551 if (I->getParent() != MainOp->getParent() &&
552 (!isVectorLikeInstWithConstOps(V: I) ||
553 !isVectorLikeInstWithConstOps(V: MainOp)))
554 return true;
555 if (isSameOperation(I, Op: MainOp))
556 return false;
557 // BinOpSameOpcodeHelper handles only BinaryOperators; a call is copyable.
558 if (!I->isBinaryOp() || !MainOp->isBinaryOp())
559 return true;
560 BinOpSameOpcodeHelper Converter(MainOp);
561 return !Converter.add(I) || !Converter.add(I: MainOp) || Converter.hasAltOp() ||
562 !Converter.hasCandidateOpcode(Opcode: getOpcode());
563}
564
565bool isAbsorbableFMulOrFAdd(ArrayRef<Value *> VL, Value *V) {
566 auto *I = dyn_cast<Instruction>(Val: V);
567 return I &&
568 (I->getOpcode() == Instruction::FMul ||
569 I->getOpcode() == Instruction::FAdd) &&
570 I->hasOneUse() && none_of(Range: I->operands(), P: [&](Value *Op) {
571 return is_contained(Range&: VL, Element: Op);
572 });
573}
574
575bool isAbsorbableCopyableFMulOrFAdd(const InstructionsState &S, Value *V) {
576 auto *I = dyn_cast<Instruction>(Val: V);
577 return I && S.isCopyableElement(V: I) &&
578 (I->getOpcode() == Instruction::FMul ||
579 I->getOpcode() == Instruction::FAdd) &&
580 I->hasOneUse();
581}
582
583bool hasOnlyAbsorbableCopyableFMulOrFAdds(ArrayRef<Value *> VL) {
584 bool HasFMulOrFAdd = false;
585 for (Value *V : VL) {
586 if (isa<PoisonValue>(Val: V))
587 continue;
588 auto *I = dyn_cast<Instruction>(Val: V);
589 if (I && RecurrenceDescriptor::isFMulAddIntrinsic(I))
590 continue;
591 if (!isAbsorbableFMulOrFAdd(VL, V))
592 return false;
593 HasFMulOrFAdd = true;
594 }
595 return HasFMulOrFAdd;
596}
597
598bool InstructionsState::isExpandedBinOp(Value *V) const {
599 assert(valid() && "InstructionsState is invalid.");
600 if (isCopyableElement(V))
601 return false;
602 auto *ExpandingOp = dyn_cast<Instruction>(Val: V);
603 if (!ExpandingOp)
604 return false;
605 auto CheckForTransformedOpcode = [](const Instruction *RefOp,
606 const Instruction *ExpandingOp) {
607 switch (RefOp->getOpcode()) {
608 case Instruction::Add:
609 switch (ExpandingOp->getOpcode()) {
610 case Instruction::Shl:
611 return match(V: ExpandingOp, P: m_Shl(L: m_Value(), R: m_One()));
612 default:
613 break;
614 }
615 break;
616 default:
617 break;
618 }
619 return false;
620 };
621 // getMatchingMainOpOrAltOp() may legitimately return nullptr, e.g. for a
622 // split node, whose Scalars combine two unrelated operations (main/alt
623 // ops of the split state), so V is not required to match either of them.
624 Instruction *MainOp = getMatchingMainOpOrAltOp(I: ExpandingOp);
625 if (!MainOp)
626 return false;
627 return CheckForTransformedOpcode(MainOp, ExpandingOp);
628}
629
630bool InstructionsState::isExpandedOperand(Instruction *I, unsigned Idx) const {
631 assert(isExpandedBinOp(I) && "Expected an expanded binop.");
632 switch (I->getOpcode()) {
633 case Instruction::Shl:
634 assert(match(I, m_Shl(m_Value(), m_One())) && "Expected shl x, 1 only.");
635 return Idx == 1;
636 default:
637 llvm_unreachable("Unexpected opcode for an expanded operand.");
638 }
639}
640
641bool InstructionsState::isNonSchedulable(Value *V) const {
642 assert(valid() && "InstructionsState is invalid.");
643 auto *I = dyn_cast<Instruction>(Val: V);
644 if (!HasCopyables)
645 return !I || isa<PHINode>(Val: I) || isVectorLikeInstWithConstOps(V: I) ||
646 doesNotNeedToBeScheduled(V);
647 // MainOp for copyables always schedulable to correctly identify
648 // non-schedulable copyables.
649 if (getMainOp() == V)
650 return false;
651 if (isCopyableElement(V)) {
652 auto IsNonSchedulableCopyableElement = [this](Value *V) {
653 auto *I = dyn_cast<Instruction>(Val: V);
654 return !I || isa<PHINode>(Val: I) || I->getParent() != MainOp->getParent() ||
655 (doesNotNeedToBeScheduled(V: I) &&
656 // If the copyable instructions comes after MainOp
657 // (non-schedulable, but used in the block) - cannot vectorize
658 // it, will possibly generate use before def.
659 !MainOp->comesBefore(Other: I));
660 };
661
662 return IsNonSchedulableCopyableElement(V);
663 }
664 return !I || isa<PHINode>(Val: I) || isVectorLikeInstWithConstOps(V: I) ||
665 doesNotNeedToBeScheduled(V);
666}
667
668/// Find an instruction with a specific opcode in VL.
669/// \param VL Array of values to search through. Must contain only Instructions
670/// and PoisonValues.
671/// \param Opcode The instruction opcode to search for
672/// \returns
673/// - The first instruction found with matching opcode
674/// - nullptr if no matching instruction is found
675static Instruction *findInstructionWithOpcode(ArrayRef<Value *> VL,
676 unsigned Opcode) {
677 for (Value *V : VL) {
678 if (isa<PoisonValue>(Val: V))
679 continue;
680 assert(isa<Instruction>(V) && "Only accepts PoisonValue and Instruction.");
681 auto *Inst = cast<Instruction>(Val: V);
682 if (Inst->getOpcode() == Opcode)
683 return Inst;
684 }
685 return nullptr;
686}
687
688/// Checks if the provided operands of 2 cmp instructions are compatible, i.e.
689/// compatible instructions or constants, or just some other regular values.
690static bool areCompatibleCmpOps(Value *BaseOp0, Value *BaseOp1, Value *Op0,
691 Value *Op1, const TargetLibraryInfo &TLI) {
692 return (isConstant(V: BaseOp0) && isConstant(V: Op0)) ||
693 (isConstant(V: BaseOp1) && isConstant(V: Op1)) ||
694 (!isa<Instruction>(Val: BaseOp0) && !isa<Instruction>(Val: Op0) &&
695 !isa<Instruction>(Val: BaseOp1) && !isa<Instruction>(Val: Op1)) ||
696 BaseOp0 == Op0 || BaseOp1 == Op1 ||
697 getSameOpcode(VL: {BaseOp0, Op0}, TLI) ||
698 getSameOpcode(VL: {BaseOp1, Op1}, TLI);
699}
700
701/// \returns true if a compare instruction \p CI has similar "look" and
702/// same predicate as \p BaseCI, "as is" or with its operands and predicate
703/// swapped, false otherwise.
704static bool isCmpSameOrSwapped(const CmpInst *BaseCI, const CmpInst *CI,
705 const TargetLibraryInfo &TLI) {
706 assert(BaseCI->getOperand(0)->getType() == CI->getOperand(0)->getType() &&
707 "Assessing comparisons of different types?");
708 CmpInst::Predicate BasePred = BaseCI->getPredicate();
709 CmpInst::Predicate Pred = CI->getPredicate();
710 CmpInst::Predicate SwappedPred = CmpInst::getSwappedPredicate(pred: Pred);
711
712 Value *BaseOp0 = BaseCI->getOperand(i_nocapture: 0);
713 Value *BaseOp1 = BaseCI->getOperand(i_nocapture: 1);
714 Value *Op0 = CI->getOperand(i_nocapture: 0);
715 Value *Op1 = CI->getOperand(i_nocapture: 1);
716
717 return (BasePred == Pred &&
718 areCompatibleCmpOps(BaseOp0, BaseOp1, Op0, Op1, TLI)) ||
719 (BasePred == SwappedPred &&
720 areCompatibleCmpOps(BaseOp0, BaseOp1, Op0: Op1, Op1: Op0, TLI));
721}
722
723InstructionsState getSameOpcode(ArrayRef<Value *> VL,
724 const TargetLibraryInfo &TLI) {
725 // Make sure these are all Instructions.
726 if (!all_of(Range&: VL, P: IsaPred<Instruction, PoisonValue>))
727 return InstructionsState::invalid();
728
729 auto *It = find_if(Range&: VL, P: IsaPred<Instruction>);
730 if (It == VL.end())
731 return InstructionsState::invalid();
732
733 Instruction *MainOp = cast<Instruction>(Val: *It);
734 unsigned InstCnt = std::count_if(first: It, last: VL.end(), pred: IsaPred<Instruction>);
735 if ((VL.size() > 2 && !isa<PHINode>(Val: MainOp) && InstCnt < VL.size() / 2) ||
736 (VL.size() == 2 && InstCnt < 2))
737 return InstructionsState::invalid();
738
739 bool IsCastOp = isa<CastInst>(Val: MainOp);
740 bool IsBinOp = isa<BinaryOperator>(Val: MainOp);
741 bool IsCmpOp = isa<CmpInst>(Val: MainOp);
742 CmpInst::Predicate BasePred = IsCmpOp ? cast<CmpInst>(Val: MainOp)->getPredicate()
743 : CmpInst::BAD_ICMP_PREDICATE;
744 Instruction *AltOp = MainOp;
745 unsigned Opcode = MainOp->getOpcode();
746 unsigned AltOpcode = Opcode;
747
748 BinOpSameOpcodeHelper BinOpHelper(MainOp);
749 bool SwappedPredsCompatible = IsCmpOp && [&]() {
750 SetVector<unsigned> UniquePreds, UniqueNonSwappedPreds;
751 UniquePreds.insert(X: BasePred);
752 UniqueNonSwappedPreds.insert(X: BasePred);
753 for (Value *V : VL) {
754 auto *I = dyn_cast<CmpInst>(Val: V);
755 if (!I)
756 return false;
757 CmpInst::Predicate CurrentPred = I->getPredicate();
758 CmpInst::Predicate SwappedCurrentPred =
759 CmpInst::getSwappedPredicate(pred: CurrentPred);
760 UniqueNonSwappedPreds.insert(X: CurrentPred);
761 if (!UniquePreds.contains(key: CurrentPred) &&
762 !UniquePreds.contains(key: SwappedCurrentPred))
763 UniquePreds.insert(X: CurrentPred);
764 }
765 // Total number of predicates > 2, but if consider swapped predicates
766 // compatible only 2, consider swappable predicates as compatible opcodes,
767 // not alternate.
768 return UniqueNonSwappedPreds.size() > 2 && UniquePreds.size() == 2;
769 }();
770 // Find the predicate the whole bundle can share, if any, treating
771 // boundary comparisons canonicalized to eq/ne as interchangeable.
772 CmpInst::Predicate InterchangeablePred = CmpInst::BAD_ICMP_PREDICATE;
773 if (IsCmpOp && isa<ICmpInst>(Val: MainOp))
774 InterchangeablePred =
775 CmpSamePredicateHelper::getSharedPredicate(VL, Preferred: cast<ICmpInst>(Val: MainOp));
776 // Check for one alternate opcode from another BinaryOperator.
777 // TODO - generalize to support all operators (types, calls etc.).
778 Intrinsic::ID BaseID = 0;
779 SmallVector<VFInfo, 4> BaseMappings;
780 if (auto *CallBase = dyn_cast<CallInst>(Val: MainOp)) {
781 BaseID = getVectorIntrinsicIDForCall(CI: CallBase, TLI: &TLI);
782 BaseMappings = VFDatabase(*CallBase).getMappings(CI: *CallBase);
783 if (!isTriviallyVectorizable(ID: BaseID) && BaseMappings.empty())
784 return InstructionsState::invalid();
785 }
786 bool AnyPoison = InstCnt != VL.size();
787 // Check MainOp too to be sure that it matches the requirements for the
788 // instructions.
789 for (Value *V : iterator_range(It, VL.end())) {
790 auto *I = dyn_cast<Instruction>(Val: V);
791 if (!I)
792 continue;
793
794 // Cannot combine poison and divisions.
795 // TODO: do some smart analysis of the CallInsts to exclude divide-like
796 // intrinsics/functions only.
797 if (AnyPoison && (I->isIntDivRem() || I->isFPDivRem() || isa<CallInst>(Val: I)))
798 return InstructionsState::invalid();
799 unsigned InstOpcode = I->getOpcode();
800 if (IsBinOp && isa<BinaryOperator>(Val: I)) {
801 if (BinOpHelper.add(I))
802 continue;
803 } else if (IsCastOp && isa<CastInst>(Val: I)) {
804 Value *Op0 = MainOp->getOperand(i: 0);
805 Type *Ty0 = Op0->getType();
806 Value *Op1 = I->getOperand(i: 0);
807 Type *Ty1 = Op1->getType();
808 if (Ty0 == Ty1) {
809 if (InstOpcode == Opcode || InstOpcode == AltOpcode)
810 continue;
811 if (Opcode == AltOpcode) {
812 assert(isValidForAlternation(Opcode) &&
813 isValidForAlternation(InstOpcode) &&
814 "Cast isn't safe for alternation, logic needs to be updated!");
815 AltOpcode = InstOpcode;
816 AltOp = I;
817 continue;
818 }
819 }
820 } else if (auto *Inst = dyn_cast<CmpInst>(Val: I); Inst && IsCmpOp) {
821 auto *BaseInst = cast<CmpInst>(Val: MainOp);
822 Type *Ty0 = BaseInst->getOperand(i_nocapture: 0)->getType();
823 Type *Ty1 = Inst->getOperand(i_nocapture: 0)->getType();
824 if (Ty0 == Ty1) {
825 assert(InstOpcode == Opcode && "Expected same CmpInst opcode.");
826 assert(InstOpcode == AltOpcode &&
827 "Alternate instructions are only supported by BinaryOperator "
828 "and CastInst.");
829 // Check for compatible operands. If the corresponding operands are not
830 // compatible - need to perform alternate vectorization.
831 CmpInst::Predicate CurrentPred = Inst->getPredicate();
832 CmpInst::Predicate SwappedCurrentPred =
833 CmpInst::getSwappedPredicate(pred: CurrentPred);
834
835 if ((VL.size() == 2 || SwappedPredsCompatible) &&
836 (BasePred == CurrentPred || BasePred == SwappedCurrentPred))
837 continue;
838
839 if (isCmpSameOrSwapped(BaseCI: BaseInst, CI: Inst, TLI))
840 continue;
841 if (CmpSamePredicateHelper::canConvertTo(CI: Inst, Pred: InterchangeablePred))
842 continue;
843 auto *AltInst = cast<CmpInst>(Val: AltOp);
844 if (MainOp != AltOp) {
845 if (isCmpSameOrSwapped(BaseCI: AltInst, CI: Inst, TLI))
846 continue;
847 } else if (BasePred != CurrentPred) {
848 assert(
849 isValidForAlternation(InstOpcode) &&
850 "CmpInst isn't safe for alternation, logic needs to be updated!");
851 AltOp = I;
852 continue;
853 }
854 CmpInst::Predicate AltPred = AltInst->getPredicate();
855 if (BasePred == CurrentPred || BasePred == SwappedCurrentPred ||
856 AltPred == CurrentPred || AltPred == SwappedCurrentPred)
857 continue;
858 }
859 } else if (InstOpcode == Opcode) {
860 assert(InstOpcode == AltOpcode &&
861 "Alternate instructions are only supported by BinaryOperator and "
862 "CastInst.");
863 if (auto *Gep = dyn_cast<GetElementPtrInst>(Val: I)) {
864 if (Gep->getNumOperands() != 2 ||
865 Gep->getOperand(i_nocapture: 0)->getType() != MainOp->getOperand(i: 0)->getType())
866 return InstructionsState::invalid();
867 } else if (auto *EI = dyn_cast<ExtractElementInst>(Val: I)) {
868 if (!isVectorLikeInstWithConstOps(V: EI))
869 return InstructionsState::invalid();
870 } else if (auto *LI = dyn_cast<LoadInst>(Val: I)) {
871 auto *BaseLI = cast<LoadInst>(Val: MainOp);
872 if (!LI->isSimple() || !BaseLI->isSimple())
873 return InstructionsState::invalid();
874 } else if (auto *Call = dyn_cast<CallInst>(Val: I)) {
875 auto *CallBase = cast<CallInst>(Val: MainOp);
876 Intrinsic::ID ID = getVectorIntrinsicIDForCall(CI: Call, TLI: &TLI);
877 Intrinsic::ID Equivalent = isEquivalentIntrinsicID(LHS: ID, RHS: BaseID);
878 if (Call->getCalledFunction() != CallBase->getCalledFunction() &&
879 isEquivalentIntrinsicID(LHS: Equivalent, RHS: Intrinsic::fmuladd) ==
880 Intrinsic::not_intrinsic)
881 return InstructionsState::invalid();
882 if (Call->hasOperandBundles() &&
883 (!CallBase->hasOperandBundles() ||
884 !std::equal(first1: Call->op_begin() + Call->getBundleOperandsStartIndex(),
885 last1: Call->op_begin() + Call->getBundleOperandsEndIndex(),
886 first2: CallBase->op_begin() +
887 CallBase->getBundleOperandsStartIndex())))
888 return InstructionsState::invalid();
889 if (ID != BaseID && Equivalent == Intrinsic::not_intrinsic)
890 return InstructionsState::invalid();
891 if (!ID) {
892 SmallVector<VFInfo, 4> Mappings =
893 VFDatabase(*Call).getMappings(CI: *Call);
894 if (Mappings.size() != BaseMappings.size() ||
895 Mappings.front().ISA != BaseMappings.front().ISA ||
896 Mappings.front().ScalarName != BaseMappings.front().ScalarName ||
897 Mappings.front().VectorName != BaseMappings.front().VectorName ||
898 Mappings.front().Shape.VF != BaseMappings.front().Shape.VF ||
899 Mappings.front().Shape.Parameters !=
900 BaseMappings.front().Shape.Parameters)
901 return InstructionsState::invalid();
902 }
903 }
904 continue;
905 }
906 return InstructionsState::invalid();
907 }
908
909 if (IsBinOp) {
910 if (!BinOpHelper.hasDefinedMainOpcode() ||
911 !BinOpHelper.hasDefinedAltOpcode())
912 return InstructionsState::invalid();
913 MainOp = findInstructionWithOpcode(VL, Opcode: BinOpHelper.getMainOpcode());
914 assert(MainOp && "Cannot find MainOp with Opcode from BinOpHelper.");
915 AltOp = findInstructionWithOpcode(VL, Opcode: BinOpHelper.getAltOpcode());
916 assert(AltOp && "Cannot find AltOp with Opcode from BinOpHelper.");
917 } else if (auto *CB = dyn_cast<CallInst>(Val: MainOp);
918 CB &&
919 getVectorIntrinsicIDForCall(CI: CB, TLI: &TLI) == Intrinsic::fmuladd) {
920 // fma and fmuladd share a single vector fma node; use the fma as the
921 // representative so the fused form is not weakened to fmuladd.
922 auto *It = find_if(Range&: VL, P: [&](Value *V) {
923 auto *CI = dyn_cast<CallInst>(Val: V);
924 return CI && getVectorIntrinsicIDForCall(CI, TLI: &TLI) == Intrinsic::fma;
925 });
926 if (It != VL.end())
927 MainOp = AltOp = cast<Instruction>(Val: *It);
928 }
929 if (IsCmpOp && InterchangeablePred != CmpInst::BAD_ICMP_PREDICATE &&
930 InterchangeablePred != BasePred) {
931 // Every lane is convertible to the shared predicate, so the alternate
932 // operation is never set for such bundles.
933 auto *SharedIt = find_if(Range&: VL, P: [&](Value *V) {
934 auto *CI = dyn_cast<ICmpInst>(Val: V);
935 return CI && CI->getPredicate() == InterchangeablePred;
936 });
937 assert(SharedIt != VL.end() &&
938 "Expected an instruction with the shared predicate.");
939 MainOp = AltOp = cast<Instruction>(Val: *SharedIt);
940 }
941 assert((MainOp == AltOp || !allSameOpcode(VL)) &&
942 "Incorrect implementation of allSameOpcode.");
943 InstructionsState S(MainOp, AltOp);
944 assert(all_of(VL,
945 [&](Value *V) {
946 return isa<PoisonValue>(V) ||
947 S.getMatchingMainOpOrAltOp(cast<Instruction>(V));
948 }) &&
949 "Invalid InstructionsState.");
950 return S;
951}
952
953std::pair<Instruction *, SmallVector<Value *>>
954convertTo(Instruction *I, const InstructionsState &S) {
955 Instruction *SelectedOp = S.getMatchingMainOpOrAltOp(I);
956 assert(SelectedOp && "Cannot convert the instruction.");
957 if (I->isBinaryOp()) {
958 BinOpSameOpcodeHelper Converter(I);
959 return std::make_pair(x&: SelectedOp, y: Converter.getOperand(I: SelectedOp));
960 }
961 // Use args() to skip the trailing callee operand in CallInst::operands().
962 if (auto *CI = dyn_cast<CallInst>(Val: I))
963 return std::make_pair(x&: SelectedOp, y: SmallVector<Value *>(CI->args()));
964 // A comparison lane interchangeable with the main operation (e.g. x == 0
965 // in an x <u C bundle) is emitted with the main predicate and the
966 // adjusted constant.
967 if (auto *MainCI = dyn_cast<ICmpInst>(Val: SelectedOp);
968 MainCI && !S.isAltShuffle())
969 if (ConstantInt *C = CmpSamePredicateHelper::getAdjustedConstant(
970 CI: cast<ICmpInst>(Val: I), Pred: MainCI->getPredicate()))
971 return std::make_pair(x&: SelectedOp,
972 y: SmallVector<Value *>{I->getOperand(i: 0), C});
973 return std::make_pair(x&: SelectedOp, y: SmallVector<Value *>(I->operands()));
974}
975
976bool isAlternateInstruction(Instruction *I, Instruction *MainOp,
977 Instruction *AltOp, const TargetLibraryInfo &TLI) {
978 if (auto *MainCI = dyn_cast<CmpInst>(Val: MainOp)) {
979 auto *AltCI = cast<CmpInst>(Val: AltOp);
980 CmpInst::Predicate MainP = MainCI->getPredicate();
981 [[maybe_unused]] CmpInst::Predicate AltP = AltCI->getPredicate();
982 assert(MainP != AltP && "Expected different main/alternate predicates.");
983 auto *CI = cast<CmpInst>(Val: I);
984 if (isCmpSameOrSwapped(BaseCI: MainCI, CI, TLI))
985 return false;
986 if (isCmpSameOrSwapped(BaseCI: AltCI, CI, TLI))
987 return true;
988 CmpInst::Predicate P = CI->getPredicate();
989 CmpInst::Predicate SwappedP = CmpInst::getSwappedPredicate(pred: P);
990
991 assert((MainP == P || AltP == P || MainP == SwappedP || AltP == SwappedP) &&
992 "CmpInst expected to match either main or alternate predicate or "
993 "their swap.");
994 return MainP != P && MainP != SwappedP;
995 }
996 return InstructionsState(MainOp, AltOp).getMatchingMainOpOrAltOp(I) == AltOp;
997}
998
999SmallVector<SmallVector<Value *>> scanAltAssociativeOperands(
1000 const InstructionsState &S, const TargetLibraryInfo &TLI,
1001 ArrayRef<Value *> VL, ArrayRef<Value *> Op0, ArrayRef<Value *> Op1,
1002 SmallVectorImpl<Value *> &ReassocScalars, SmallBitVector &SubLanes) {
1003 assert(S.isAltShuffle() && "Expected an alternate node.");
1004 const unsigned NumLanes = VL.size();
1005 SmallVector<unsigned> LaneOpcodes =
1006 map_to_vector(C: seq<unsigned>(Size: NumLanes), F: [&](unsigned Lane) {
1007 return isAlternateInstruction(I: cast<Instruction>(Val: VL[Lane]),
1008 MainOp: S.getMainOp(), AltOp: S.getAltOp(), TLI)
1009 ? S.getAltOpcode()
1010 : S.getOpcode();
1011 });
1012 // A lane value peels only as a single-use chain link with the lane's own
1013 // opcode, keeping every combine level on the same main/alt pattern.
1014 auto GetChainLink = [&](unsigned Lane, Value *V) -> Instruction * {
1015 auto *I = dyn_cast<Instruction>(Val: V);
1016 if (!I || !I->hasOneUse() || I->getOpcode() != LaneOpcodes[Lane] ||
1017 !isReassocChainLink(I))
1018 return nullptr;
1019 return I;
1020 };
1021 SmallVector<SmallVector<Value *>> Columns;
1022 Columns.emplace_back(Args: Op0.begin(), Args: Op0.end());
1023 Columns.emplace_back(Args: Op1.begin(), Args: Op1.end());
1024 // The chain link of a commutative lane may sit in the second column;
1025 // normalize so every lane's link leads.
1026 for (unsigned Lane : seq<unsigned>(Size: NumLanes)) {
1027 if (GetChainLink(Lane, Columns[0][Lane]))
1028 continue;
1029 Instruction *Link = GetChainLink(Lane, Columns[1][Lane]);
1030 if (!Link || !Link->isCommutative())
1031 return {};
1032 std::swap(a&: Columns[0][Lane], b&: Columns[1][Lane]);
1033 }
1034 // Peel the leading column while every lane stays a matching chain link.
1035 while (all_of(Range: seq<unsigned>(Size: NumLanes), P: [&](unsigned Lane) {
1036 return GetChainLink(Lane, Columns[0][Lane]) != nullptr;
1037 })) {
1038 SmallVector<Value *> NewColumn(NumLanes);
1039 for (unsigned Lane : seq<unsigned>(Size: NumLanes)) {
1040 Instruction *Link = GetChainLink(Lane, Columns[0][Lane]);
1041 ReassocScalars.push_back(Elt: Link);
1042 // The chain of a commutative lane may continue in the second operand;
1043 // keep the chain link as the running value.
1044 unsigned RunningOp = Link->isCommutative() &&
1045 !GetChainLink(Lane, Link->getOperand(i: 0)) &&
1046 GetChainLink(Lane, Link->getOperand(i: 1))
1047 ? 1
1048 : 0;
1049 NewColumn[Lane] = Link->getOperand(i: 1 - RunningOp);
1050 Columns[0][Lane] = Link->getOperand(i: RunningOp);
1051 }
1052 Columns.insert(I: std::next(x: Columns.begin()), Elt: std::move(NewColumn));
1053 }
1054 assert(!ReassocScalars.empty() &&
1055 "Normalization guarantees at least one peeled level.");
1056 SubLanes.resize(N: NumLanes);
1057 for (unsigned Lane : seq<unsigned>(Size: NumLanes))
1058 if (LaneOpcodes[Lane] == Instruction::Sub ||
1059 LaneOpcodes[Lane] == Instruction::FSub)
1060 SubLanes.set(Lane);
1061 return Columns;
1062}
1063} // namespace llvm::slpvectorizer
1064