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