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
423/// Returns the predicate and the compared constant of the comparison lane
424/// \p I, treating trunc X to i1 as and X, 1 ne 0.
425static std::optional<std::pair<CmpInst::Predicate, APInt>>
426getLaneConstantCmp(const Instruction *I) {
427 if (auto *TI = dyn_cast<TruncInst>(Val: I);
428 TI && TI->getType()->isIntOrIntVectorTy(BitWidth: 1))
429 return std::make_pair(
430 x: CmpInst::ICMP_NE,
431 y: APInt::getZero(numBits: TI->getSrcTy()->getScalarSizeInBits()));
432 const APInt *C;
433 if (auto *CI = dyn_cast<ICmpInst>(Val: I);
434 CI && match(V: CI->getOperand(i_nocapture: 1), P: m_APInt(Res&: C)))
435 return std::make_pair(x: CI->getPredicate(), y: *C);
436 return std::nullopt;
437}
438
439CmpSamePredicateHelper::MaskType
440CmpSamePredicateHelper::getLaneMask(const Instruction *I) {
441 if (std::optional<std::pair<CmpInst::Predicate, APInt>> Cmp =
442 getLaneConstantCmp(I)) {
443 MaskType M = getFormsMask(Pred: Cmp->first, C: Cmp->second);
444 // trunc X to i1 is also and X, 1 eq 1.
445 return isa<TruncInst>(Val: I) ? M | getBit(P: CmpInst::ICMP_EQ) : M;
446 }
447 if (auto *CI = dyn_cast<ICmpInst>(Val: I))
448 return getBit(P: CI->getPredicate());
449 return 0;
450}
451
452bool CmpSamePredicateHelper::isBitTest(const Instruction *I) {
453 if (auto *CI = dyn_cast<ICmpInst>(Val: I);
454 CI && !match(V: CI->getOperand(i_nocapture: 0), P: m_OneUse(SubPattern: m_And(L: m_Value(), R: m_Value()))))
455 return false;
456 std::optional<std::pair<CmpInst::Predicate, APInt>> Cmp =
457 getLaneConstantCmp(I);
458 if (!Cmp)
459 return false;
460 std::optional<std::pair<bool, APInt>> Family =
461 getCmpBoundaryFamily(Pred: Cmp->first, C: Cmp->second);
462 return Family && Family->second.isZero();
463}
464
465bool CmpSamePredicateHelper::add(const Instruction *I) {
466 if (auto *CI = dyn_cast<ICmpInst>(Val: I))
467 SeenBefore |= getBit(P: CI->getPredicate());
468 Mask &= getLaneMask(I);
469 return Mask != 0;
470}
471
472CmpInst::Predicate
473CmpSamePredicateHelper::getPredicate(const ICmpInst *Preferred) const {
474 MaskType Candidate = Mask & SeenBefore;
475 if (!Candidate)
476 return CmpInst::BAD_ICMP_PREDICATE;
477 if (Candidate & getBit(P: Preferred->getPredicate()))
478 return Preferred->getPredicate();
479 return static_cast<CmpInst::Predicate>(CmpInst::ICMP_EQ +
480 countr_zero(Val: Candidate));
481}
482
483CmpInst::Predicate
484CmpSamePredicateHelper::getSharedPredicate(ArrayRef<Value *> VL,
485 const ICmpInst *Preferred) {
486 CmpSamePredicateHelper Helper;
487 if (!all_of(Range&: VL, P: [&](Value *V) {
488 auto *I = dyn_cast<Instruction>(Val: V);
489 return isa<PoisonValue>(Val: V) || (I && Helper.add(I));
490 }))
491 return CmpInst::BAD_ICMP_PREDICATE;
492 return Helper.getPredicate(Preferred);
493}
494
495bool CmpSamePredicateHelper::canConvertTo(const Instruction *I,
496 CmpInst::Predicate Pred) {
497 return CmpInst::isIntPredicate(P: Pred) && (getLaneMask(I) & getBit(P: Pred)) != 0;
498}
499
500Constant *CmpSamePredicateHelper::getAdjustedConstant(const Instruction *I,
501 CmpInst::Predicate Pred) {
502 if (!canConvertTo(I, Pred))
503 return nullptr;
504 if (auto *CI = dyn_cast<ICmpInst>(Val: I); CI && CI->getPredicate() == Pred)
505 return nullptr;
506 if (isa<TruncInst>(Val: I) && Pred == CmpInst::ICMP_EQ)
507 return ConstantInt::get(Ty: I->getOperand(i: 0)->getType(), V: 1);
508 auto [LanePred, C] = *getLaneConstantCmp(I);
509 std::optional<std::pair<bool, APInt>> Family =
510 getCmpBoundaryFamily(Pred: LanePred, C);
511 assert(Family && "Expected a boundary family for a convertible compare.");
512 const auto &[IsComplement, K] = *Family;
513 return ConstantInt::get(Ty: I->getOperand(i: 0)->getType(),
514 V: getFamilyConstant(IsComplement, K, Pred));
515}
516
517bool InstructionsState::isSameOperation(const Instruction *I,
518 const Instruction *Op) {
519 if (I->getOpcode() != Op->getOpcode())
520 return false;
521 const auto *II = dyn_cast<IntrinsicInst>(Val: I);
522 const auto *IOp = dyn_cast<IntrinsicInst>(Val: Op);
523 if (II || IOp)
524 return II && IOp &&
525 isEquivalentIntrinsicID(LHS: II->getIntrinsicID(),
526 RHS: IOp->getIntrinsicID()) !=
527 Intrinsic::not_intrinsic;
528 return true;
529}
530
531Instruction *InstructionsState::getMatchingMainOpOrAltOp(Instruction *I) const {
532 assert(MainOp && "MainOp cannot be nullptr.");
533 if (isSameOperation(I, Op: MainOp))
534 return MainOp;
535 if (MainOp->getOpcode() == Instruction::Select &&
536 I->getOpcode() == Instruction::ZExt && !isAltShuffle())
537 return MainOp;
538 if (MainOp->getOpcode() == Instruction::ICmp &&
539 I->getOpcode() == Instruction::Trunc && !isAltShuffle())
540 return MainOp;
541 // Prefer AltOp instead of interchangeable instruction of MainOp.
542 assert(AltOp && "AltOp cannot be nullptr.");
543 if (isSameOperation(I, Op: AltOp))
544 return AltOp;
545 // BinOpSameOpcodeHelper handles only BinaryOperators; a call cannot match.
546 if (!I->isBinaryOp() || !MainOp->isBinaryOp())
547 return nullptr;
548 BinOpSameOpcodeHelper Converter(MainOp);
549 if (!Converter.add(I) || !Converter.add(I: MainOp))
550 return nullptr;
551 if (isAltShuffle() && !Converter.hasCandidateOpcode(Opcode: MainOp->getOpcode())) {
552 BinOpSameOpcodeHelper AltConverter(AltOp);
553 if (AltConverter.add(I) && AltConverter.add(I: AltOp) &&
554 AltConverter.hasCandidateOpcode(Opcode: AltOp->getOpcode()))
555 return AltOp;
556 }
557 if (Converter.hasAltOp() && !isAltShuffle())
558 return nullptr;
559 return Converter.hasAltOp() ? AltOp : MainOp;
560}
561
562bool InstructionsState::isMulDivLikeOp() const {
563 constexpr std::array<unsigned, 8> MulDiv = {
564 Instruction::Mul, Instruction::FMul, Instruction::SDiv,
565 Instruction::UDiv, Instruction::FDiv, Instruction::SRem,
566 Instruction::URem, Instruction::FRem};
567 return is_contained(Range: MulDiv, Element: getOpcode()) &&
568 is_contained(Range: MulDiv, Element: getAltOpcode());
569}
570
571bool InstructionsState::isAddSubLikeOp() const {
572 constexpr std::array<unsigned, 4> AddSub = {
573 Instruction::Add, Instruction::Sub, Instruction::FAdd, Instruction::FSub};
574 return is_contained(Range: AddSub, Element: getOpcode()) &&
575 is_contained(Range: AddSub, Element: getAltOpcode());
576}
577
578bool InstructionsState::isAddSubOrFNegLikeOp() const {
579 return isAddSubLikeOp() || getOpcode() == Instruction::FNeg;
580}
581
582bool InstructionsState::isCopyableElement(Value *V) const {
583 assert(valid() && "InstructionsState is invalid.");
584 if (!HasCopyables)
585 return false;
586 if (isAltShuffle())
587 return false;
588 auto *I = dyn_cast<Instruction>(Val: V);
589 // Copyable lanes of a cast node are limited to constants representable as
590 // the cast of a source-type constant.
591 if (isa<CastInst>(Val: MainOp)) {
592 if (I || isa<PoisonValue>(Val: V))
593 return false;
594 if (isa<UndefValue>(Val: V))
595 return true;
596 auto *C = dyn_cast<ConstantInt>(Val: V);
597 return C && C->getValue().getActiveBits() <=
598 cast<CastInst>(Val: MainOp)->getSrcTy()->getIntegerBitWidth();
599 }
600 if (!I)
601 return !isa<PoisonValue>(Val: V);
602 // For a GEP main op only single-index GEPs with the same source element
603 // type can be matching lanes; GEPs with a different shape are copyable.
604 if (getOpcode() == Instruction::GetElementPtr)
605 if (auto *GEP = dyn_cast<GetElementPtrInst>(Val: I);
606 GEP && (GEP->getNumOperands() != 2 ||
607 GEP->getSourceElementType() !=
608 cast<GetElementPtrInst>(Val: MainOp)->getSourceElementType()))
609 return true;
610 if (I->getParent() != MainOp->getParent() &&
611 (!isVectorLikeInstWithConstOps(V: I) ||
612 !isVectorLikeInstWithConstOps(V: MainOp)))
613 return true;
614 if (isSameOperation(I, Op: MainOp))
615 return false;
616 // BinOpSameOpcodeHelper handles only BinaryOperators; a call is copyable.
617 if (!I->isBinaryOp() || !MainOp->isBinaryOp())
618 return true;
619 BinOpSameOpcodeHelper Converter(MainOp);
620 return !Converter.add(I) || !Converter.add(I: MainOp) || Converter.hasAltOp() ||
621 !Converter.hasCandidateOpcode(Opcode: getOpcode());
622}
623
624bool isAbsorbableFMulOrFAdd(ArrayRef<Value *> VL, Value *V) {
625 auto *I = dyn_cast<Instruction>(Val: V);
626 return I &&
627 (I->getOpcode() == Instruction::FMul ||
628 I->getOpcode() == Instruction::FAdd) &&
629 I->hasOneUse() && none_of(Range: I->operands(), P: [&](Value *Op) {
630 return is_contained(Range&: VL, Element: Op);
631 });
632}
633
634bool isAbsorbableCopyableFMulOrFAdd(const InstructionsState &S, Value *V) {
635 auto *I = dyn_cast<Instruction>(Val: V);
636 return I && S.isCopyableElement(V: I) &&
637 (I->getOpcode() == Instruction::FMul ||
638 I->getOpcode() == Instruction::FAdd) &&
639 I->hasOneUse();
640}
641
642bool hasOnlyAbsorbableCopyableFMulOrFAdds(ArrayRef<Value *> VL) {
643 bool HasFMulOrFAdd = false;
644 for (Value *V :
645 make_filter_range(Range&: VL, Pred: [](Value *V) { return !isa<PoisonValue>(Val: V); })) {
646 auto *I = dyn_cast<Instruction>(Val: V);
647 if (I && RecurrenceDescriptor::isFMulAddIntrinsic(I))
648 continue;
649 if (!isAbsorbableFMulOrFAdd(VL, V))
650 return false;
651 HasFMulOrFAdd = true;
652 }
653 return HasFMulOrFAdd;
654}
655
656bool InstructionsState::isExpandedBinOp(Value *V) const {
657 assert(valid() && "InstructionsState is invalid.");
658 if (isCopyableElement(V))
659 return false;
660 auto *ExpandingOp = dyn_cast<Instruction>(Val: V);
661 if (!ExpandingOp)
662 return false;
663 auto CheckForTransformedOpcode = [](const Instruction *RefOp,
664 const Instruction *ExpandingOp) {
665 switch (RefOp->getOpcode()) {
666 case Instruction::Add:
667 switch (ExpandingOp->getOpcode()) {
668 case Instruction::Shl:
669 return match(V: ExpandingOp, P: m_Shl(L: m_Value(), R: m_One()));
670 default:
671 break;
672 }
673 break;
674 default:
675 break;
676 }
677 return false;
678 };
679 // getMatchingMainOpOrAltOp() may legitimately return nullptr, e.g. for a
680 // split node, whose Scalars combine two unrelated operations (main/alt
681 // ops of the split state), so V is not required to match either of them.
682 Instruction *MainOp = getMatchingMainOpOrAltOp(I: ExpandingOp);
683 if (!MainOp)
684 return false;
685 return CheckForTransformedOpcode(MainOp, ExpandingOp);
686}
687
688bool InstructionsState::isExpandedOperand(Instruction *I, unsigned Idx) const {
689 assert(isExpandedBinOp(I) && "Expected an expanded binop.");
690 switch (I->getOpcode()) {
691 case Instruction::Shl:
692 assert(match(I, m_Shl(m_Value(), m_One())) && "Expected shl x, 1 only.");
693 return Idx == 1;
694 default:
695 llvm_unreachable("Unexpected opcode for an expanded operand.");
696 }
697}
698
699bool InstructionsState::isNonSchedulable(Value *V) const {
700 assert(valid() && "InstructionsState is invalid.");
701 auto *I = dyn_cast<Instruction>(Val: V);
702 if (!HasCopyables)
703 return !I || isa<PHINode>(Val: I) || isVectorLikeInstWithConstOps(V: I) ||
704 doesNotNeedToBeScheduled(V);
705 // MainOp for copyables always schedulable to correctly identify
706 // non-schedulable copyables.
707 if (getMainOp() == V)
708 return false;
709 if (isCopyableElement(V)) {
710 auto IsNonSchedulableCopyableElement = [this](Value *V) {
711 auto *I = dyn_cast<Instruction>(Val: V);
712 return !I || isa<PHINode>(Val: I) || I->getParent() != MainOp->getParent() ||
713 (doesNotNeedToBeScheduled(V: I) &&
714 // If the copyable instructions comes after MainOp
715 // (non-schedulable, but used in the block) - cannot vectorize
716 // it, will possibly generate use before def.
717 !MainOp->comesBefore(Other: I));
718 };
719
720 return IsNonSchedulableCopyableElement(V);
721 }
722 return !I || isa<PHINode>(Val: I) || isVectorLikeInstWithConstOps(V: I) ||
723 doesNotNeedToBeScheduled(V);
724}
725
726/// Find an instruction with a specific opcode in VL.
727/// \param VL Array of values to search through. Must contain only Instructions
728/// and PoisonValues.
729/// \param Opcode The instruction opcode to search for
730/// \returns
731/// - The first instruction found with matching opcode
732/// - nullptr if no matching instruction is found
733static Instruction *findInstructionWithOpcode(ArrayRef<Value *> VL,
734 unsigned Opcode) {
735 for (Value *V :
736 make_filter_range(Range&: VL, Pred: [](Value *V) { return !isa<PoisonValue>(Val: V); })) {
737 assert(isa<Instruction>(V) && "Only accepts PoisonValue and Instruction.");
738 auto *Inst = cast<Instruction>(Val: V);
739 if (Inst->getOpcode() == Opcode)
740 return Inst;
741 }
742 return nullptr;
743}
744
745/// Checks if the provided operands of 2 cmp instructions are compatible, i.e.
746/// compatible instructions or constants, or just some other regular values.
747static bool areCompatibleCmpOps(Value *BaseOp0, Value *BaseOp1, Value *Op0,
748 Value *Op1, const TargetLibraryInfo &TLI) {
749 return (isConstant(V: BaseOp0) && isConstant(V: Op0)) ||
750 (isConstant(V: BaseOp1) && isConstant(V: Op1)) ||
751 (!isa<Instruction>(Val: BaseOp0) && !isa<Instruction>(Val: Op0) &&
752 !isa<Instruction>(Val: BaseOp1) && !isa<Instruction>(Val: Op1)) ||
753 BaseOp0 == Op0 || BaseOp1 == Op1 ||
754 getSameOpcode(VL: {BaseOp0, Op0}, TLI) ||
755 getSameOpcode(VL: {BaseOp1, Op1}, TLI);
756}
757
758/// \returns true if a compare instruction \p CI has similar "look" and
759/// same predicate as \p BaseCI, "as is" or with its operands and predicate
760/// swapped, false otherwise.
761static bool isCmpSameOrSwapped(const CmpInst *BaseCI, const CmpInst *CI,
762 const TargetLibraryInfo &TLI) {
763 assert(BaseCI->getOperand(0)->getType() == CI->getOperand(0)->getType() &&
764 "Assessing comparisons of different types?");
765 CmpInst::Predicate BasePred = BaseCI->getPredicate();
766 CmpInst::Predicate Pred = CI->getPredicate();
767 CmpInst::Predicate SwappedPred = CmpInst::getSwappedPredicate(pred: Pred);
768
769 Value *BaseOp0 = BaseCI->getOperand(i_nocapture: 0);
770 Value *BaseOp1 = BaseCI->getOperand(i_nocapture: 1);
771 Value *Op0 = CI->getOperand(i_nocapture: 0);
772 Value *Op1 = CI->getOperand(i_nocapture: 1);
773
774 return (BasePred == Pred &&
775 areCompatibleCmpOps(BaseOp0, BaseOp1, Op0, Op1, TLI)) ||
776 (BasePred == SwappedPred &&
777 areCompatibleCmpOps(BaseOp0, BaseOp1, Op0: Op1, Op1: Op0, TLI));
778}
779
780InstructionsState getSameOpcode(ArrayRef<Value *> VL,
781 const TargetLibraryInfo &TLI) {
782 // Make sure these are all Instructions.
783 if (!all_of(Range&: VL, P: IsaPred<Instruction, PoisonValue>))
784 return InstructionsState::invalid();
785
786 auto *It = find_if(Range&: VL, P: IsaPred<Instruction>);
787 if (It == VL.end())
788 return InstructionsState::invalid();
789
790 Instruction *MainOp = cast<Instruction>(Val: *It);
791 unsigned InstCnt = std::count_if(first: It, last: VL.end(), pred: IsaPred<Instruction>);
792 if ((VL.size() > 2 && !isa<PHINode>(Val: MainOp) && InstCnt < VL.size() / 2) ||
793 (VL.size() == 2 && InstCnt < 2))
794 return InstructionsState::invalid();
795
796 // Match trunc X to i1 lanes against the compares.
797 if (isa<TruncInst>(Val: MainOp) && MainOp->getType()->isIntOrIntVectorTy(BitWidth: 1))
798 if (auto *CmpIt = find_if(Range&: VL, P: IsaPred<ICmpInst>); CmpIt != VL.end())
799 MainOp = cast<Instruction>(Val: *CmpIt);
800
801 bool IsCastOp = isa<CastInst>(Val: MainOp);
802 bool IsBinOp = isa<BinaryOperator>(Val: MainOp);
803 bool IsCmpOp = isa<CmpInst>(Val: MainOp);
804 CmpInst::Predicate BasePred = IsCmpOp ? cast<CmpInst>(Val: MainOp)->getPredicate()
805 : CmpInst::BAD_ICMP_PREDICATE;
806 Instruction *AltOp = MainOp;
807 unsigned Opcode = MainOp->getOpcode();
808 unsigned AltOpcode = Opcode;
809
810 BinOpSameOpcodeHelper BinOpHelper(MainOp);
811 bool SwappedPredsCompatible = IsCmpOp && [&]() {
812 SetVector<unsigned> UniquePreds, UniqueNonSwappedPreds;
813 UniquePreds.insert(X: BasePred);
814 UniqueNonSwappedPreds.insert(X: BasePred);
815 for (Value *V : VL) {
816 auto *I = dyn_cast<CmpInst>(Val: V);
817 if (!I)
818 return false;
819 CmpInst::Predicate CurrentPred = I->getPredicate();
820 CmpInst::Predicate SwappedCurrentPred =
821 CmpInst::getSwappedPredicate(pred: CurrentPred);
822 UniqueNonSwappedPreds.insert(X: CurrentPred);
823 if (!UniquePreds.contains(key: CurrentPred) &&
824 !UniquePreds.contains(key: SwappedCurrentPred))
825 UniquePreds.insert(X: CurrentPred);
826 }
827 // Total number of predicates > 2, but if consider swapped predicates
828 // compatible only 2, consider swappable predicates as compatible opcodes,
829 // not alternate.
830 return UniqueNonSwappedPreds.size() > 2 && UniquePreds.size() == 2;
831 }();
832 // Find the predicate the whole bundle can share, if any, treating
833 // boundary comparisons canonicalized to eq/ne as interchangeable.
834 CmpInst::Predicate InterchangeablePred = CmpInst::BAD_ICMP_PREDICATE;
835 if (IsCmpOp && isa<ICmpInst>(Val: MainOp))
836 InterchangeablePred =
837 CmpSamePredicateHelper::getSharedPredicate(VL, Preferred: cast<ICmpInst>(Val: MainOp));
838 // Check for one alternate opcode from another BinaryOperator.
839 // TODO - generalize to support all operators (types, calls etc.).
840 Intrinsic::ID BaseID = 0;
841 SmallVector<VFInfo, 4> BaseMappings;
842 if (auto *CallBase = dyn_cast<CallInst>(Val: MainOp)) {
843 BaseID = getVectorIntrinsicIDForCall(CI: CallBase, TLI: &TLI);
844 BaseMappings = VFDatabase(*CallBase).getMappings(CI: *CallBase);
845 if (!isTriviallyVectorizable(ID: BaseID) && BaseMappings.empty())
846 return InstructionsState::invalid();
847 }
848 bool AnyPoison = InstCnt != VL.size();
849 // Check MainOp too to be sure that it matches the requirements for the
850 // instructions.
851 for (Instruction *I :
852 make_isa_range<Instruction>(Range: iterator_range(It, VL.end()))) {
853 // Cannot combine poison and divisions.
854 // TODO: do some smart analysis of the CallInsts to exclude divide-like
855 // intrinsics/functions only.
856 if (AnyPoison && (I->isIntDivRem() || I->isFPDivRem() || isa<CallInst>(Val: I)))
857 return InstructionsState::invalid();
858 unsigned InstOpcode = I->getOpcode();
859 if (IsBinOp && isa<BinaryOperator>(Val: I)) {
860 if (BinOpHelper.add(I))
861 continue;
862 } else if (IsCastOp && isa<CastInst>(Val: I)) {
863 Value *Op0 = MainOp->getOperand(i: 0);
864 Type *Ty0 = Op0->getType();
865 Value *Op1 = I->getOperand(i: 0);
866 Type *Ty1 = Op1->getType();
867 if (Ty0 == Ty1) {
868 if (InstOpcode == Opcode || InstOpcode == AltOpcode)
869 continue;
870 if (Opcode == AltOpcode) {
871 assert(isValidForAlternation(Opcode) &&
872 isValidForAlternation(InstOpcode) &&
873 "Cast isn't safe for alternation, logic needs to be updated!");
874 AltOpcode = InstOpcode;
875 AltOp = I;
876 continue;
877 }
878 }
879 } else if (auto *Inst = dyn_cast<CmpInst>(Val: I); Inst && IsCmpOp) {
880 auto *BaseInst = cast<CmpInst>(Val: MainOp);
881 Type *Ty0 = BaseInst->getOperand(i_nocapture: 0)->getType();
882 Type *Ty1 = Inst->getOperand(i_nocapture: 0)->getType();
883 if (Ty0 == Ty1) {
884 assert(InstOpcode == Opcode && "Expected same CmpInst opcode.");
885 assert(InstOpcode == AltOpcode &&
886 "Alternate instructions are only supported by BinaryOperator "
887 "and CastInst.");
888 // Check for compatible operands. If the corresponding operands are not
889 // compatible - need to perform alternate vectorization.
890 CmpInst::Predicate CurrentPred = Inst->getPredicate();
891 CmpInst::Predicate SwappedCurrentPred =
892 CmpInst::getSwappedPredicate(pred: CurrentPred);
893
894 if ((VL.size() == 2 || SwappedPredsCompatible) &&
895 (BasePred == CurrentPred || BasePred == SwappedCurrentPred))
896 continue;
897
898 if (isCmpSameOrSwapped(BaseCI: BaseInst, CI: Inst, TLI))
899 continue;
900 if (CmpSamePredicateHelper::canConvertTo(I: Inst, Pred: InterchangeablePred))
901 continue;
902 auto *AltInst = cast<CmpInst>(Val: AltOp);
903 if (MainOp != AltOp) {
904 if (isCmpSameOrSwapped(BaseCI: AltInst, CI: Inst, TLI))
905 continue;
906 } else if (BasePred != CurrentPred) {
907 assert(
908 isValidForAlternation(InstOpcode) &&
909 "CmpInst isn't safe for alternation, logic needs to be updated!");
910 AltOp = I;
911 continue;
912 }
913 CmpInst::Predicate AltPred = AltInst->getPredicate();
914 if (BasePred == CurrentPred || BasePred == SwappedCurrentPred ||
915 AltPred == CurrentPred || AltPred == SwappedCurrentPred)
916 continue;
917 }
918 } else if (auto *TI = dyn_cast<TruncInst>(Val: I); TI && IsCmpOp) {
919 // trunc X to i1 is the bit test and X, 1 != 0 or and X, 1 == 1, so the
920 // whole list must be the bit tests of the same type sharing the
921 // predicate.
922 if (InterchangeablePred != CmpInst::BAD_ICMP_PREDICATE &&
923 TI->getSrcTy() == MainOp->getOperand(i: 0)->getType() &&
924 all_of(Range&: VL, P: [](Value *V) {
925 auto *I = dyn_cast<Instruction>(Val: V);
926 return isa<PoisonValue>(Val: V) ||
927 (I && CmpSamePredicateHelper::isBitTest(I));
928 }))
929 continue;
930 } else if (InstOpcode == Opcode) {
931 assert(InstOpcode == AltOpcode &&
932 "Alternate instructions are only supported by BinaryOperator and "
933 "CastInst.");
934 if (auto *Gep = dyn_cast<GetElementPtrInst>(Val: I)) {
935 if (Gep->getNumOperands() != 2 ||
936 Gep->getOperand(i_nocapture: 0)->getType() != MainOp->getOperand(i: 0)->getType())
937 return InstructionsState::invalid();
938 } else if (auto *EI = dyn_cast<ExtractElementInst>(Val: I)) {
939 if (!isVectorLikeInstWithConstOps(V: EI))
940 return InstructionsState::invalid();
941 } else if (auto *LI = dyn_cast<LoadInst>(Val: I)) {
942 auto *BaseLI = cast<LoadInst>(Val: MainOp);
943 if (!LI->isSimple() || !BaseLI->isSimple())
944 return InstructionsState::invalid();
945 } else if (auto *Call = dyn_cast<CallInst>(Val: I)) {
946 auto *CallBase = cast<CallInst>(Val: MainOp);
947 Intrinsic::ID ID = getVectorIntrinsicIDForCall(CI: Call, TLI: &TLI);
948 Intrinsic::ID Equivalent = isEquivalentIntrinsicID(LHS: ID, RHS: BaseID);
949 if (Call->getCalledFunction() != CallBase->getCalledFunction() &&
950 isEquivalentIntrinsicID(LHS: Equivalent, RHS: Intrinsic::fmuladd) ==
951 Intrinsic::not_intrinsic)
952 return InstructionsState::invalid();
953 if (Call->hasOperandBundles() &&
954 (!CallBase->hasOperandBundles() ||
955 !std::equal(first1: Call->op_begin() + Call->getBundleOperandsStartIndex(),
956 last1: Call->op_begin() + Call->getBundleOperandsEndIndex(),
957 first2: CallBase->op_begin() +
958 CallBase->getBundleOperandsStartIndex())))
959 return InstructionsState::invalid();
960 if (ID != BaseID && Equivalent == Intrinsic::not_intrinsic)
961 return InstructionsState::invalid();
962 if (!ID) {
963 SmallVector<VFInfo, 4> Mappings =
964 VFDatabase(*Call).getMappings(CI: *Call);
965 if (Mappings.size() != BaseMappings.size() ||
966 Mappings.front().ISA != BaseMappings.front().ISA ||
967 Mappings.front().ScalarName != BaseMappings.front().ScalarName ||
968 Mappings.front().VectorName != BaseMappings.front().VectorName ||
969 Mappings.front().Shape.VF != BaseMappings.front().Shape.VF ||
970 Mappings.front().Shape.Parameters !=
971 BaseMappings.front().Shape.Parameters)
972 return InstructionsState::invalid();
973 }
974 }
975 continue;
976 }
977 return InstructionsState::invalid();
978 }
979
980 if (IsBinOp) {
981 if (!BinOpHelper.hasDefinedMainOpcode() ||
982 !BinOpHelper.hasDefinedAltOpcode())
983 return InstructionsState::invalid();
984 MainOp = findInstructionWithOpcode(VL, Opcode: BinOpHelper.getMainOpcode());
985 assert(MainOp && "Cannot find MainOp with Opcode from BinOpHelper.");
986 AltOp = findInstructionWithOpcode(VL, Opcode: BinOpHelper.getAltOpcode());
987 assert(AltOp && "Cannot find AltOp with Opcode from BinOpHelper.");
988 } else if (auto *CB = dyn_cast<CallInst>(Val: MainOp);
989 CB &&
990 getVectorIntrinsicIDForCall(CI: CB, TLI: &TLI) == Intrinsic::fmuladd) {
991 // fma and fmuladd share a single vector fma node; use the fma as the
992 // representative so the fused form is not weakened to fmuladd.
993 auto *It = find_if(Range&: VL, P: [&](Value *V) {
994 auto *CI = dyn_cast<CallInst>(Val: V);
995 return CI && getVectorIntrinsicIDForCall(CI, TLI: &TLI) == Intrinsic::fma;
996 });
997 if (It != VL.end())
998 MainOp = AltOp = cast<Instruction>(Val: *It);
999 }
1000 if (IsCmpOp && InterchangeablePred != CmpInst::BAD_ICMP_PREDICATE &&
1001 InterchangeablePred != BasePred) {
1002 // Every lane is convertible to the shared predicate, so the alternate
1003 // operation is never set for such bundles.
1004 auto *SharedIt = find_if(Range&: VL, P: [&](Value *V) {
1005 auto *CI = dyn_cast<ICmpInst>(Val: V);
1006 return CI && CI->getPredicate() == InterchangeablePred;
1007 });
1008 assert(SharedIt != VL.end() &&
1009 "Expected an instruction with the shared predicate.");
1010 MainOp = AltOp = cast<Instruction>(Val: *SharedIt);
1011 }
1012 assert((MainOp == AltOp || !allSameOpcode(VL)) &&
1013 "Incorrect implementation of allSameOpcode.");
1014 InstructionsState S(MainOp, AltOp);
1015 assert(all_of(VL,
1016 [&](Value *V) {
1017 return isa<PoisonValue>(V) ||
1018 S.getMatchingMainOpOrAltOp(cast<Instruction>(V));
1019 }) &&
1020 "Invalid InstructionsState.");
1021 return S;
1022}
1023
1024std::pair<Instruction *, SmallVector<Value *>>
1025convertTo(Instruction *I, const InstructionsState &S) {
1026 Instruction *SelectedOp = S.getMatchingMainOpOrAltOp(I);
1027 assert(SelectedOp && "Cannot convert the instruction.");
1028 if (I->isBinaryOp()) {
1029 BinOpSameOpcodeHelper Converter(I);
1030 return std::make_pair(x&: SelectedOp, y: Converter.getOperand(I: SelectedOp));
1031 }
1032 // Use args() to skip the trailing callee operand in CallInst::operands().
1033 if (auto *CI = dyn_cast<CallInst>(Val: I))
1034 return std::make_pair(x&: SelectedOp, y: SmallVector<Value *>(CI->args()));
1035 // A comparison lane interchangeable with the main operation (e.g. x == 0
1036 // in an x <u C bundle) is emitted with the main predicate and the
1037 // adjusted constant.
1038 if (auto *MainCI = dyn_cast<ICmpInst>(Val: SelectedOp);
1039 MainCI && !S.isAltShuffle())
1040 if (Constant *C = CmpSamePredicateHelper::getAdjustedConstant(
1041 I, Pred: MainCI->getPredicate()))
1042 return std::make_pair(x&: SelectedOp,
1043 y: SmallVector<Value *>{I->getOperand(i: 0), C});
1044 return std::make_pair(x&: SelectedOp, y: SmallVector<Value *>(I->operands()));
1045}
1046
1047bool isAlternateInstruction(Instruction *I, Instruction *MainOp,
1048 Instruction *AltOp, const TargetLibraryInfo &TLI) {
1049 if (auto *MainCI = dyn_cast<CmpInst>(Val: MainOp)) {
1050 auto *AltCI = cast<CmpInst>(Val: AltOp);
1051 CmpInst::Predicate MainP = MainCI->getPredicate();
1052 [[maybe_unused]] CmpInst::Predicate AltP = AltCI->getPredicate();
1053 assert(MainP != AltP && "Expected different main/alternate predicates.");
1054 auto *CI = cast<CmpInst>(Val: I);
1055 if (isCmpSameOrSwapped(BaseCI: MainCI, CI, TLI))
1056 return false;
1057 if (isCmpSameOrSwapped(BaseCI: AltCI, CI, TLI))
1058 return true;
1059 CmpInst::Predicate P = CI->getPredicate();
1060 CmpInst::Predicate SwappedP = CmpInst::getSwappedPredicate(pred: P);
1061
1062 assert((MainP == P || AltP == P || MainP == SwappedP || AltP == SwappedP) &&
1063 "CmpInst expected to match either main or alternate predicate or "
1064 "their swap.");
1065 return MainP != P && MainP != SwappedP;
1066 }
1067 return InstructionsState(MainOp, AltOp).getMatchingMainOpOrAltOp(I) == AltOp;
1068}
1069
1070SmallVector<SmallVector<Value *>> scanAltAssociativeOperands(
1071 const InstructionsState &S, const TargetLibraryInfo &TLI,
1072 ArrayRef<Value *> VL, ArrayRef<Value *> Op0, ArrayRef<Value *> Op1,
1073 SmallVectorImpl<Value *> &ReassocScalars, SmallBitVector &SubLanes) {
1074 assert(S.isAltShuffle() && "Expected an alternate node.");
1075 const unsigned NumLanes = VL.size();
1076 SmallVector<unsigned> LaneOpcodes =
1077 map_to_vector(C: seq<unsigned>(Size: NumLanes), F: [&](unsigned Lane) {
1078 return isAlternateInstruction(I: cast<Instruction>(Val: VL[Lane]),
1079 MainOp: S.getMainOp(), AltOp: S.getAltOp(), TLI)
1080 ? S.getAltOpcode()
1081 : S.getOpcode();
1082 });
1083 // A lane value peels only as a single-use chain link with the lane's own
1084 // opcode, keeping every combine level on the same main/alt pattern.
1085 auto GetChainLink = [&](unsigned Lane, Value *V) -> Instruction * {
1086 auto *I = dyn_cast<Instruction>(Val: V);
1087 if (!I || !I->hasOneUse() || I->getOpcode() != LaneOpcodes[Lane] ||
1088 !isReassocChainLink(I))
1089 return nullptr;
1090 return I;
1091 };
1092 SmallVector<SmallVector<Value *>> Columns;
1093 Columns.emplace_back(Args: Op0.begin(), Args: Op0.end());
1094 Columns.emplace_back(Args: Op1.begin(), Args: Op1.end());
1095 // The chain link of a commutative lane may sit in the second column;
1096 // normalize so every lane's link leads.
1097 for (unsigned Lane : seq<unsigned>(Size: NumLanes)) {
1098 if (GetChainLink(Lane, Columns[0][Lane]))
1099 continue;
1100 Instruction *Link = GetChainLink(Lane, Columns[1][Lane]);
1101 if (!Link || !Link->isCommutative())
1102 return {};
1103 std::swap(a&: Columns[0][Lane], b&: Columns[1][Lane]);
1104 }
1105 // Peel the leading column while every lane stays a matching chain link.
1106 while (all_of(Range: seq<unsigned>(Size: NumLanes), P: [&](unsigned Lane) {
1107 return GetChainLink(Lane, Columns[0][Lane]) != nullptr;
1108 })) {
1109 SmallVector<Value *> NewColumn(NumLanes);
1110 for (unsigned Lane : seq<unsigned>(Size: NumLanes)) {
1111 Instruction *Link = GetChainLink(Lane, Columns[0][Lane]);
1112 ReassocScalars.push_back(Elt: Link);
1113 // The chain of a commutative lane may continue in the second operand;
1114 // keep the chain link as the running value.
1115 unsigned RunningOp = Link->isCommutative() &&
1116 !GetChainLink(Lane, Link->getOperand(i: 0)) &&
1117 GetChainLink(Lane, Link->getOperand(i: 1))
1118 ? 1
1119 : 0;
1120 NewColumn[Lane] = Link->getOperand(i: 1 - RunningOp);
1121 Columns[0][Lane] = Link->getOperand(i: RunningOp);
1122 }
1123 Columns.insert(I: std::next(x: Columns.begin()), Elt: std::move(NewColumn));
1124 }
1125 assert(!ReassocScalars.empty() &&
1126 "Normalization guarantees at least one peeled level.");
1127 SubLanes.resize(N: NumLanes);
1128 for (unsigned Lane : seq<unsigned>(Size: NumLanes))
1129 if (LaneOpcodes[Lane] == Instruction::Sub ||
1130 LaneOpcodes[Lane] == Instruction::FSub)
1131 SubLanes.set(Lane);
1132 return Columns;
1133}
1134} // namespace llvm::slpvectorizer
1135