/build/source/llvm/lib/Transforms/Vectorize/VectorCombine.cpp

Bug Summary

File:	build/source/llvm/lib/Transforms/Vectorize/VectorCombine.cpp
Warning:	line 299, column 19 Called C++ object pointer is null
Annotated Source Code

Press '?' to see keyboard shortcuts
Show analyzer invocation
clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name VectorCombine.cpp -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/source/build-llvm -resource-dir /usr/lib/llvm-17/lib/clang/17 -I lib/Transforms/Vectorize -I /build/source/llvm/lib/Transforms/Vectorize -I include -I /build/source/llvm/include -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -D _FORTIFY_SOURCE=2 -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-17/lib/clang/17/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -fmacro-prefix-map=/build/source/build-llvm=build-llvm -fmacro-prefix-map=/build/source/= -fcoverage-prefix-map=/build/source/build-llvm=build-llvm -fcoverage-prefix-map=/build/source/= -source-date-epoch 1675721604 -O3 -Wno-unused-command-line-argument -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -Wno-misleading-indentation -std=c++17 -fdeprecated-macro -fdebug-compilation-dir=/build/source/build-llvm -fdebug-prefix-map=/build/source/build-llvm=build-llvm -fdebug-prefix-map=/build/source/= -fdebug-prefix-map=/build/source/build-llvm=build-llvm -fdebug-prefix-map=/build/source/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2023-02-07-030702-17298-1 -x c++ /build/source/llvm/lib/Transforms/Vectorize/VectorCombine.cpp
1//===------- VectorCombine.cpp - Optimize partial vector operations -------===//
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// This pass optimizes scalar/vector interactions using target cost models. The
10// transforms implemented here may not fit in traditional loop-based or SLP
11// vectorization passes.
12//
13//===----------------------------------------------------------------------===//

15#include "llvm/Transforms/Vectorize/VectorCombine.h"
16#include "llvm/ADT/Statistic.h"
17#include "llvm/Analysis/AssumptionCache.h"
18#include "llvm/Analysis/BasicAliasAnalysis.h"
19#include "llvm/Analysis/GlobalsModRef.h"
20#include "llvm/Analysis/Loads.h"
21#include "llvm/Analysis/TargetTransformInfo.h"
22#include "llvm/Analysis/ValueTracking.h"
23#include "llvm/Analysis/VectorUtils.h"
24#include "llvm/IR/Dominators.h"
25#include "llvm/IR/Function.h"
26#include "llvm/IR/IRBuilder.h"
27#include "llvm/IR/PatternMatch.h"
28#include "llvm/InitializePasses.h"
29#include "llvm/Pass.h"
30#include "llvm/Support/CommandLine.h"
31#include "llvm/Transforms/Utils/Local.h"
32#include "llvm/Transforms/Vectorize.h"
33#include <numeric>

35#define DEBUG_TYPE"vector-combine" "vector-combine"
36#include "llvm/Transforms/Utils/InstructionWorklist.h"

38using namespace llvm;
39using namespace llvm::PatternMatch;

41STATISTIC(NumVecLoad, "Number of vector loads formed")static llvm::Statistic NumVecLoad = {"vector-combine", "NumVecLoad"
, "Number of vector loads formed"};
42STATISTIC(NumVecCmp, "Number of vector compares formed")static llvm::Statistic NumVecCmp = {"vector-combine", "NumVecCmp"
, "Number of vector compares formed"};
43STATISTIC(NumVecBO, "Number of vector binops formed")static llvm::Statistic NumVecBO = {"vector-combine", "NumVecBO"
, "Number of vector binops formed"};
44STATISTIC(NumVecCmpBO, "Number of vector compare + binop formed")static llvm::Statistic NumVecCmpBO = {"vector-combine", "NumVecCmpBO"
, "Number of vector compare + binop formed"};
45STATISTIC(NumShufOfBitcast, "Number of shuffles moved after bitcast")static llvm::Statistic NumShufOfBitcast = {"vector-combine", "NumShufOfBitcast"
, "Number of shuffles moved after bitcast"};
46STATISTIC(NumScalarBO, "Number of scalar binops formed")static llvm::Statistic NumScalarBO = {"vector-combine", "NumScalarBO"
, "Number of scalar binops formed"};
47STATISTIC(NumScalarCmp, "Number of scalar compares formed")static llvm::Statistic NumScalarCmp = {"vector-combine", "NumScalarCmp"
, "Number of scalar compares formed"};

49static cl::opt<bool> DisableVectorCombine(
  "disable-vector-combine", cl::init(false), cl::Hidden,
  cl::desc("Disable all vector combine transforms"));

53static cl::opt<bool> DisableBinopExtractShuffle(
  "disable-binop-extract-shuffle", cl::init(false), cl::Hidden,
  cl::desc("Disable binop extract to shuffle transforms"));

57static cl::opt<unsigned> MaxInstrsToScan(
  "vector-combine-max-scan-instrs", cl::init(30), cl::Hidden,
  cl::desc("Max number of instructions to scan for vector combining."));

61static const unsigned InvalidIndex = std::numeric_limits<unsigned>::max();

63namespace {
64class VectorCombine {
65public:
VectorCombine(Function &F, const TargetTransformInfo &TTI,
              const DominatorTree &DT, AAResults &AA, AssumptionCache &AC,
              bool TryEarlyFoldsOnly)
    : F(F), Builder(F.getContext()), TTI(TTI), DT(DT), AA(AA), AC(AC),
      TryEarlyFoldsOnly(TryEarlyFoldsOnly) {}

bool run();

74private:
Function &F;
IRBuilder<> Builder;
const TargetTransformInfo &TTI;
const DominatorTree &DT;
AAResults &AA;
AssumptionCache &AC;

/// If true, only perform beneficial early IR transforms. Do not introduce new
/// vector operations.
bool TryEarlyFoldsOnly;

InstructionWorklist Worklist;

// TODO: Direct calls from the top-level "run" loop use a plain "Instruction"
//       parameter. That should be updated to specific sub-classes because the
//       run loop was changed to dispatch on opcode.
bool vectorizeLoadInsert(Instruction &I);
bool widenSubvectorLoad(Instruction &I);
ExtractElementInst *getShuffleExtract(ExtractElementInst *Ext0,
                                      ExtractElementInst *Ext1,
                                      unsigned PreferredExtractIndex) const;
bool isExtractExtractCheap(ExtractElementInst *Ext0, ExtractElementInst *Ext1,
                           const Instruction &I,
                           ExtractElementInst *&ConvertToShuffle,
                           unsigned PreferredExtractIndex);
void foldExtExtCmp(ExtractElementInst *Ext0, ExtractElementInst *Ext1,
                   Instruction &I);
void foldExtExtBinop(ExtractElementInst *Ext0, ExtractElementInst *Ext1,
                     Instruction &I);
bool foldExtractExtract(Instruction &I);
bool foldInsExtFNeg(Instruction &I);
bool foldBitcastShuf(Instruction &I);
bool scalarizeBinopOrCmp(Instruction &I);
bool foldExtractedCmps(Instruction &I);
bool foldSingleElementStore(Instruction &I);
bool scalarizeLoadExtract(Instruction &I);
bool foldShuffleOfBinops(Instruction &I);
bool foldShuffleFromReductions(Instruction &I);
bool foldSelectShuffle(Instruction &I, bool FromReduction = false);

void replaceValue(Value &Old, Value &New) {
  Old.replaceAllUsesWith(&New);
  if (auto *NewI = dyn_cast<Instruction>(&New)) {
    New.takeName(&Old);
    Worklist.pushUsersToWorkList(*NewI);
    Worklist.pushValue(NewI);
  }
  Worklist.pushValue(&Old);
}

void eraseInstruction(Instruction &I) {
  for (Value *Op : I.operands())
    Worklist.pushValue(Op);
  Worklist.remove(&I);
  I.eraseFromParent();
}
131};
132} // namespace

134static bool canWidenLoad(LoadInst *Load, const TargetTransformInfo &TTI) {
// Do not widen load if atomic/volatile or under asan/hwasan/memtag/tsan.
// The widened load may load data from dirty regions or create data races
// non-existent in the source.
if (!Load || !Load->isSimple() || !Load->hasOneUse() ||
    Load->getFunction()->hasFnAttribute(Attribute::SanitizeMemTag) ||
    mustSuppressSpeculation(*Load))
  return false;

// We are potentially transforming byte-sized (8-bit) memory accesses, so make
// sure we have all of our type-based constraints in place for this target.
Type *ScalarTy = Load->getType()->getScalarType();
uint64_t ScalarSize = ScalarTy->getPrimitiveSizeInBits();
unsigned MinVectorSize = TTI.getMinVectorRegisterBitWidth();
if (!ScalarSize || !MinVectorSize || MinVectorSize % ScalarSize != 0 ||
    ScalarSize % 8 != 0)
  return false;

return true;
153}

155bool VectorCombine::vectorizeLoadInsert(Instruction &I) {
// Match insert into fixed vector of scalar value.
// TODO: Handle non-zero insert index.
Value *Scalar;
if (!match(&I, m_InsertElt(m_Undef(), m_Value(Scalar), m_ZeroInt())) ||
    !Scalar->hasOneUse())
  return false;

// Optionally match an extract from another vector.
Value *X;
bool HasExtract = match(Scalar, m_ExtractElt(m_Value(X), m_ZeroInt()));
if (!HasExtract)
  X = Scalar;

auto *Load = dyn_cast<LoadInst>(X);
if (!canWidenLoad(Load, TTI))
  return false;

Type *ScalarTy = Scalar->getType();
uint64_t ScalarSize = ScalarTy->getPrimitiveSizeInBits();
unsigned MinVectorSize = TTI.getMinVectorRegisterBitWidth();

// Check safety of replacing the scalar load with a larger vector load.
// We use minimal alignment (maximum flexibility) because we only care about
// the dereferenceable region. When calculating cost and creating a new op,
// we may use a larger value based on alignment attributes.
const DataLayout &DL = I.getModule()->getDataLayout();
Value *SrcPtr = Load->getPointerOperand()->stripPointerCasts();
assert(isa<PointerType>(SrcPtr->getType()) && "Expected a pointer type")(static_cast <bool> (isa<PointerType>(SrcPtr->
getType()) && "Expected a pointer type") ? void (0) :
 __assert_fail ("isa<PointerType>(SrcPtr->getType()) && \"Expected a pointer type\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 183, __extension__
 __PRETTY_FUNCTION__));

unsigned MinVecNumElts = MinVectorSize / ScalarSize;
auto *MinVecTy = VectorType::get(ScalarTy, MinVecNumElts, false);
unsigned OffsetEltIndex = 0;
Align Alignment = Load->getAlign();
if (!isSafeToLoadUnconditionally(SrcPtr, MinVecTy, Align(1), DL, Load, &AC,
                                 &DT)) {
  // It is not safe to load directly from the pointer, but we can still peek
  // through gep offsets and check if it safe to load from a base address with
  // updated alignment. If it is, we can shuffle the element(s) into place
  // after loading.
  unsigned OffsetBitWidth = DL.getIndexTypeSizeInBits(SrcPtr->getType());
  APInt Offset(OffsetBitWidth, 0);
  SrcPtr = SrcPtr->stripAndAccumulateInBoundsConstantOffsets(DL, Offset);

  // We want to shuffle the result down from a high element of a vector, so
  // the offset must be positive.
  if (Offset.isNegative())
    return false;

  // The offset must be a multiple of the scalar element to shuffle cleanly
  // in the element's size.
  uint64_t ScalarSizeInBytes = ScalarSize / 8;
  if (Offset.urem(ScalarSizeInBytes) != 0)
    return false;

  // If we load MinVecNumElts, will our target element still be loaded?
  OffsetEltIndex = Offset.udiv(ScalarSizeInBytes).getZExtValue();
  if (OffsetEltIndex >= MinVecNumElts)
    return false;

  if (!isSafeToLoadUnconditionally(SrcPtr, MinVecTy, Align(1), DL, Load, &AC,
                                   &DT))
    return false;

  // Update alignment with offset value. Note that the offset could be negated
  // to more accurately represent "(new) SrcPtr - Offset = (old) SrcPtr", but
  // negation does not change the result of the alignment calculation.
  Alignment = commonAlignment(Alignment, Offset.getZExtValue());
}

// Original pattern: insertelt undef, load [free casts of] PtrOp, 0
// Use the greater of the alignment on the load or its source pointer.
Alignment = std::max(SrcPtr->getPointerAlignment(DL), Alignment);
Type *LoadTy = Load->getType();
unsigned AS = Load->getPointerAddressSpace();
InstructionCost OldCost =
    TTI.getMemoryOpCost(Instruction::Load, LoadTy, Alignment, AS);
APInt DemandedElts = APInt::getOneBitSet(MinVecNumElts, 0);
TTI::TargetCostKind CostKind = TTI::TCK_RecipThroughput;
OldCost +=
    TTI.getScalarizationOverhead(MinVecTy, DemandedElts,
                                 /* Insert */ true, HasExtract, CostKind);

// New pattern: load VecPtr
InstructionCost NewCost =
    TTI.getMemoryOpCost(Instruction::Load, MinVecTy, Alignment, AS);
// Optionally, we are shuffling the loaded vector element(s) into place.
// For the mask set everything but element 0 to undef to prevent poison from
// propagating from the extra loaded memory. This will also optionally
// shrink/grow the vector from the loaded size to the output size.
// We assume this operation has no cost in codegen if there was no offset.
// Note that we could use freeze to avoid poison problems, but then we might
// still need a shuffle to change the vector size.
auto *Ty = cast<FixedVectorType>(I.getType());
unsigned OutputNumElts = Ty->getNumElements();
SmallVector<int, 16> Mask(OutputNumElts, UndefMaskElem);
assert(OffsetEltIndex < MinVecNumElts && "Address offset too big")(static_cast <bool> (OffsetEltIndex < MinVecNumElts &&
 "Address offset too big") ? void (0) : __assert_fail ("OffsetEltIndex < MinVecNumElts && \"Address offset too big\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 251, __extension__
 __PRETTY_FUNCTION__));
Mask[0] = OffsetEltIndex;
if (OffsetEltIndex)
  NewCost += TTI.getShuffleCost(TTI::SK_PermuteSingleSrc, MinVecTy, Mask);

// We can aggressively convert to the vector form because the backend can
// invert this transform if it does not result in a performance win.
if (OldCost < NewCost || !NewCost.isValid())
  return false;

// It is safe and potentially profitable to load a vector directly:
// inselt undef, load Scalar, 0 --> load VecPtr
IRBuilder<> Builder(Load);
Value *CastedPtr = Builder.CreatePointerBitCastOrAddrSpaceCast(
    SrcPtr, MinVecTy->getPointerTo(AS));
Value *VecLd = Builder.CreateAlignedLoad(MinVecTy, CastedPtr, Alignment);
VecLd = Builder.CreateShuffleVector(VecLd, Mask);

replaceValue(I, *VecLd);
++NumVecLoad;
return true;
272}

274/// If we are loading a vector and then inserting it into a larger vector with
275/// undefined elements, try to load the larger vector and eliminate the insert.
276/// This removes a shuffle in IR and may allow combining of other loaded values.
277bool VectorCombine::widenSubvectorLoad(Instruction &I) {
// Match subvector insert of fixed vector.
auto *Shuf = cast<ShuffleVectorInst>(&I);
18
←
The object is a 'CastReturnType'→
if (!Shuf->isIdentityWithPadding())
19
←
Assuming the condition is false→
20
←
Taking false branch→
  return false;

// Allow a non-canonical shuffle mask that is choosing elements from op1.
unsigned NumOpElts =
    cast<FixedVectorType>(Shuf->getOperand(0)->getType())->getNumElements();
21
←
The object is a 'CastReturnType'→
unsigned OpIndex = any_of(Shuf->getShuffleMask(), [&NumOpElts](int M) {
  return M >= (int)(NumOpElts);
});

auto *Load = dyn_cast<LoadInst>(Shuf->getOperand(OpIndex));
22
←
Assuming the object is not a 'CastReturnType'→
23
←
'Load' initialized to a null pointer value→
if (!canWidenLoad(Load, TTI))
24
←
Assuming the condition is false→
25
←
Taking false branch→
  return false;

// We use minimal alignment (maximum flexibility) because we only care about
// the dereferenceable region. When calculating cost and creating a new op,
// we may use a larger value based on alignment attributes.
auto *Ty = cast<FixedVectorType>(I.getType());
26
←
The object is a 'CastReturnType'→
const DataLayout &DL = I.getModule()->getDataLayout();
Value *SrcPtr = Load->getPointerOperand()->stripPointerCasts();
27
←
Called C++ object pointer is null
assert(isa<PointerType>(SrcPtr->getType()) && "Expected a pointer type")(static_cast <bool> (isa<PointerType>(SrcPtr->
getType()) && "Expected a pointer type") ? void (0) :
 __assert_fail ("isa<PointerType>(SrcPtr->getType()) && \"Expected a pointer type\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 300, __extension__
 __PRETTY_FUNCTION__));
Align Alignment = Load->getAlign();
if (!isSafeToLoadUnconditionally(SrcPtr, Ty, Align(1), DL, Load, &AC, &DT))
  return false;

Alignment = std::max(SrcPtr->getPointerAlignment(DL), Alignment);
Type *LoadTy = Load->getType();
unsigned AS = Load->getPointerAddressSpace();

// Original pattern: insert_subvector (load PtrOp)
// This conservatively assumes that the cost of a subvector insert into an
// undef value is 0. We could add that cost if the cost model accurately
// reflects the real cost of that operation.
InstructionCost OldCost =
    TTI.getMemoryOpCost(Instruction::Load, LoadTy, Alignment, AS);

// New pattern: load PtrOp
InstructionCost NewCost =
    TTI.getMemoryOpCost(Instruction::Load, Ty, Alignment, AS);

// We can aggressively convert to the vector form because the backend can
// invert this transform if it does not result in a performance win.
if (OldCost < NewCost || !NewCost.isValid())
  return false;

IRBuilder<> Builder(Load);
Value *CastedPtr =
    Builder.CreatePointerBitCastOrAddrSpaceCast(SrcPtr, Ty->getPointerTo(AS));
Value *VecLd = Builder.CreateAlignedLoad(Ty, CastedPtr, Alignment);
replaceValue(I, *VecLd);
++NumVecLoad;
return true;
332}

334/// Determine which, if any, of the inputs should be replaced by a shuffle
335/// followed by extract from a different index.
336ExtractElementInst *VectorCombine::getShuffleExtract(
  ExtractElementInst *Ext0, ExtractElementInst *Ext1,
  unsigned PreferredExtractIndex = InvalidIndex) const {
auto *Index0C = dyn_cast<ConstantInt>(Ext0->getIndexOperand());
auto *Index1C = dyn_cast<ConstantInt>(Ext1->getIndexOperand());
assert(Index0C && Index1C && "Expected constant extract indexes")(static_cast <bool> (Index0C && Index1C &&
 "Expected constant extract indexes") ? void (0) : __assert_fail
 ("Index0C && Index1C && \"Expected constant extract indexes\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 341, __extension__
 __PRETTY_FUNCTION__));

unsigned Index0 = Index0C->getZExtValue();
unsigned Index1 = Index1C->getZExtValue();

// If the extract indexes are identical, no shuffle is needed.
if (Index0 == Index1)
  return nullptr;

Type *VecTy = Ext0->getVectorOperand()->getType();
TTI::TargetCostKind CostKind = TTI::TCK_RecipThroughput;
assert(VecTy == Ext1->getVectorOperand()->getType() && "Need matching types")(static_cast <bool> (VecTy == Ext1->getVectorOperand
()->getType() && "Need matching types") ? void (0)
 : __assert_fail ("VecTy == Ext1->getVectorOperand()->getType() && \"Need matching types\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 352, __extension__
 __PRETTY_FUNCTION__));
InstructionCost Cost0 =
    TTI.getVectorInstrCost(*Ext0, VecTy, CostKind, Index0);
InstructionCost Cost1 =
    TTI.getVectorInstrCost(*Ext1, VecTy, CostKind, Index1);

// If both costs are invalid no shuffle is needed
if (!Cost0.isValid() && !Cost1.isValid())
  return nullptr;

// We are extracting from 2 different indexes, so one operand must be shuffled
// before performing a vector operation and/or extract. The more expensive
// extract will be replaced by a shuffle.
if (Cost0 > Cost1)
  return Ext0;
if (Cost1 > Cost0)
  return Ext1;

// If the costs are equal and there is a preferred extract index, shuffle the
// opposite operand.
if (PreferredExtractIndex == Index0)
  return Ext1;
if (PreferredExtractIndex == Index1)
  return Ext0;

// Otherwise, replace the extract with the higher index.
return Index0 > Index1 ? Ext0 : Ext1;
379}

381/// Compare the relative costs of 2 extracts followed by scalar operation vs.
382/// vector operation(s) followed by extract. Return true if the existing
383/// instructions are cheaper than a vector alternative. Otherwise, return false
384/// and if one of the extracts should be transformed to a shufflevector, set
385/// \p ConvertToShuffle to that extract instruction.
386bool VectorCombine::isExtractExtractCheap(ExtractElementInst *Ext0,
                                        ExtractElementInst *Ext1,
                                        const Instruction &I,
                                        ExtractElementInst *&ConvertToShuffle,
                                        unsigned PreferredExtractIndex) {
auto *Ext0IndexC = dyn_cast<ConstantInt>(Ext0->getOperand(1));
auto *Ext1IndexC = dyn_cast<ConstantInt>(Ext1->getOperand(1));
assert(Ext0IndexC && Ext1IndexC && "Expected constant extract indexes")(static_cast <bool> (Ext0IndexC && Ext1IndexC &&
 "Expected constant extract indexes") ? void (0) : __assert_fail
 ("Ext0IndexC && Ext1IndexC && \"Expected constant extract indexes\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 393, __extension__
 __PRETTY_FUNCTION__));

unsigned Opcode = I.getOpcode();
Type *ScalarTy = Ext0->getType();
auto *VecTy = cast<VectorType>(Ext0->getOperand(0)->getType());
InstructionCost ScalarOpCost, VectorOpCost;

// Get cost estimates for scalar and vector versions of the operation.
bool IsBinOp = Instruction::isBinaryOp(Opcode);
if (IsBinOp) {
  ScalarOpCost = TTI.getArithmeticInstrCost(Opcode, ScalarTy);
  VectorOpCost = TTI.getArithmeticInstrCost(Opcode, VecTy);
} else {
  assert((Opcode == Instruction::ICmp || Opcode == Instruction::FCmp) &&(static_cast <bool> ((Opcode == Instruction::ICmp || Opcode
 == Instruction::FCmp) && "Expected a compare") ? void
 (0) : __assert_fail ("(Opcode == Instruction::ICmp || Opcode == Instruction::FCmp) && \"Expected a compare\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 407, __extension__
 __PRETTY_FUNCTION__))
         "Expected a compare")(static_cast <bool> ((Opcode == Instruction::ICmp || Opcode
 == Instruction::FCmp) && "Expected a compare") ? void
 (0) : __assert_fail ("(Opcode == Instruction::ICmp || Opcode == Instruction::FCmp) && \"Expected a compare\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 407, __extension__
 __PRETTY_FUNCTION__));
  CmpInst::Predicate Pred = cast<CmpInst>(I).getPredicate();
  ScalarOpCost = TTI.getCmpSelInstrCost(
      Opcode, ScalarTy, CmpInst::makeCmpResultType(ScalarTy), Pred);
  VectorOpCost = TTI.getCmpSelInstrCost(
      Opcode, VecTy, CmpInst::makeCmpResultType(VecTy), Pred);
}

// Get cost estimates for the extract elements. These costs will factor into
// both sequences.
unsigned Ext0Index = Ext0IndexC->getZExtValue();
unsigned Ext1Index = Ext1IndexC->getZExtValue();
TTI::TargetCostKind CostKind = TTI::TCK_RecipThroughput;

InstructionCost Extract0Cost =
    TTI.getVectorInstrCost(*Ext0, VecTy, CostKind, Ext0Index);
InstructionCost Extract1Cost =
    TTI.getVectorInstrCost(*Ext1, VecTy, CostKind, Ext1Index);

// A more expensive extract will always be replaced by a splat shuffle.
// For example, if Ext0 is more expensive:
// opcode (extelt V0, Ext0), (ext V1, Ext1) -->
// extelt (opcode (splat V0, Ext0), V1), Ext1
// TODO: Evaluate whether that always results in lowest cost. Alternatively,
//       check the cost of creating a broadcast shuffle and shuffling both
//       operands to element 0.
InstructionCost CheapExtractCost = std::min(Extract0Cost, Extract1Cost);

// Extra uses of the extracts mean that we include those costs in the
// vector total because those instructions will not be eliminated.
InstructionCost OldCost, NewCost;
if (Ext0->getOperand(0) == Ext1->getOperand(0) && Ext0Index == Ext1Index) {
  // Handle a special case. If the 2 extracts are identical, adjust the
  // formulas to account for that. The extra use charge allows for either the
  // CSE'd pattern or an unoptimized form with identical values:
  // opcode (extelt V, C), (extelt V, C) --> extelt (opcode V, V), C
  bool HasUseTax = Ext0 == Ext1 ? !Ext0->hasNUses(2)
                                : !Ext0->hasOneUse() || !Ext1->hasOneUse();
  OldCost = CheapExtractCost + ScalarOpCost;
  NewCost = VectorOpCost + CheapExtractCost + HasUseTax * CheapExtractCost;
} else {
  // Handle the general case. Each extract is actually a different value:
  // opcode (extelt V0, C0), (extelt V1, C1) --> extelt (opcode V0, V1), C
  OldCost = Extract0Cost + Extract1Cost + ScalarOpCost;
  NewCost = VectorOpCost + CheapExtractCost +
            !Ext0->hasOneUse() * Extract0Cost +
            !Ext1->hasOneUse() * Extract1Cost;
}

ConvertToShuffle = getShuffleExtract(Ext0, Ext1, PreferredExtractIndex);
if (ConvertToShuffle) {
  if (IsBinOp && DisableBinopExtractShuffle)
    return true;

  // If we are extracting from 2 different indexes, then one operand must be
  // shuffled before performing the vector operation. The shuffle mask is
  // undefined except for 1 lane that is being translated to the remaining
  // extraction lane. Therefore, it is a splat shuffle. Ex:
  // ShufMask = { undef, undef, 0, undef }
  // TODO: The cost model has an option for a "broadcast" shuffle
  //       (splat-from-element-0), but no option for a more general splat.
  NewCost +=
      TTI.getShuffleCost(TargetTransformInfo::SK_PermuteSingleSrc, VecTy);
}

// Aggressively form a vector op if the cost is equal because the transform
// may enable further optimization.
// Codegen can reverse this transform (scalarize) if it was not profitable.
return OldCost < NewCost;
476}

478/// Create a shuffle that translates (shifts) 1 element from the input vector
479/// to a new element location.
480static Value *createShiftShuffle(Value *Vec, unsigned OldIndex,
                               unsigned NewIndex, IRBuilder<> &Builder) {
// The shuffle mask is undefined except for 1 lane that is being translated
// to the new element index. Example for OldIndex == 2 and NewIndex == 0:
// ShufMask = { 2, undef, undef, undef }
auto *VecTy = cast<FixedVectorType>(Vec->getType());
SmallVector<int, 32> ShufMask(VecTy->getNumElements(), UndefMaskElem);
ShufMask[NewIndex] = OldIndex;
return Builder.CreateShuffleVector(Vec, ShufMask, "shift");
489}

491/// Given an extract element instruction with constant index operand, shuffle
492/// the source vector (shift the scalar element) to a NewIndex for extraction.
493/// Return null if the input can be constant folded, so that we are not creating
494/// unnecessary instructions.
495static ExtractElementInst *translateExtract(ExtractElementInst *ExtElt,
                                          unsigned NewIndex,
                                          IRBuilder<> &Builder) {
// Shufflevectors can only be created for fixed-width vectors.
if (!isa<FixedVectorType>(ExtElt->getOperand(0)->getType()))
  return nullptr;

// If the extract can be constant-folded, this code is unsimplified. Defer
// to other passes to handle that.
Value *X = ExtElt->getVectorOperand();
Value *C = ExtElt->getIndexOperand();
assert(isa<ConstantInt>(C) && "Expected a constant index operand")(static_cast <bool> (isa<ConstantInt>(C) &&
 "Expected a constant index operand") ? void (0) : __assert_fail
 ("isa<ConstantInt>(C) && \"Expected a constant index operand\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 506, __extension__
 __PRETTY_FUNCTION__));
if (isa<Constant>(X))
  return nullptr;

Value *Shuf = createShiftShuffle(X, cast<ConstantInt>(C)->getZExtValue(),
                                 NewIndex, Builder);
return cast<ExtractElementInst>(Builder.CreateExtractElement(Shuf, NewIndex));
513}

515/// Try to reduce extract element costs by converting scalar compares to vector
516/// compares followed by extract.
517/// cmp (ext0 V0, C), (ext1 V1, C)
518void VectorCombine::foldExtExtCmp(ExtractElementInst *Ext0,
                                ExtractElementInst *Ext1, Instruction &I) {
assert(isa<CmpInst>(&I) && "Expected a compare")(static_cast <bool> (isa<CmpInst>(&I) &&
 "Expected a compare") ? void (0) : __assert_fail ("isa<CmpInst>(&I) && \"Expected a compare\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 520, __extension__
 __PRETTY_FUNCTION__));
assert(cast<ConstantInt>(Ext0->getIndexOperand())->getZExtValue() ==(static_cast <bool> (cast<ConstantInt>(Ext0->getIndexOperand
())->getZExtValue() == cast<ConstantInt>(Ext1->getIndexOperand
())->getZExtValue() && "Expected matching constant extract indexes"
) ? void (0) : __assert_fail ("cast<ConstantInt>(Ext0->getIndexOperand())->getZExtValue() == cast<ConstantInt>(Ext1->getIndexOperand())->getZExtValue() && \"Expected matching constant extract indexes\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 523, __extension__
 __PRETTY_FUNCTION__))
           cast<ConstantInt>(Ext1->getIndexOperand())->getZExtValue() &&(static_cast <bool> (cast<ConstantInt>(Ext0->getIndexOperand
())->getZExtValue() == cast<ConstantInt>(Ext1->getIndexOperand
())->getZExtValue() && "Expected matching constant extract indexes"
) ? void (0) : __assert_fail ("cast<ConstantInt>(Ext0->getIndexOperand())->getZExtValue() == cast<ConstantInt>(Ext1->getIndexOperand())->getZExtValue() && \"Expected matching constant extract indexes\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 523, __extension__
 __PRETTY_FUNCTION__))
       "Expected matching constant extract indexes")(static_cast <bool> (cast<ConstantInt>(Ext0->getIndexOperand
())->getZExtValue() == cast<ConstantInt>(Ext1->getIndexOperand
())->getZExtValue() && "Expected matching constant extract indexes"
) ? void (0) : __assert_fail ("cast<ConstantInt>(Ext0->getIndexOperand())->getZExtValue() == cast<ConstantInt>(Ext1->getIndexOperand())->getZExtValue() && \"Expected matching constant extract indexes\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 523, __extension__
 __PRETTY_FUNCTION__));

// cmp Pred (extelt V0, C), (extelt V1, C) --> extelt (cmp Pred V0, V1), C
++NumVecCmp;
CmpInst::Predicate Pred = cast<CmpInst>(&I)->getPredicate();
Value *V0 = Ext0->getVectorOperand(), *V1 = Ext1->getVectorOperand();
Value *VecCmp = Builder.CreateCmp(Pred, V0, V1);
Value *NewExt = Builder.CreateExtractElement(VecCmp, Ext0->getIndexOperand());
replaceValue(I, *NewExt);
532}

534/// Try to reduce extract element costs by converting scalar binops to vector
535/// binops followed by extract.
536/// bo (ext0 V0, C), (ext1 V1, C)
537void VectorCombine::foldExtExtBinop(ExtractElementInst *Ext0,
                                  ExtractElementInst *Ext1, Instruction &I) {
assert(isa<BinaryOperator>(&I) && "Expected a binary operator")(static_cast <bool> (isa<BinaryOperator>(&I) &&
 "Expected a binary operator") ? void (0) : __assert_fail ("isa<BinaryOperator>(&I) && \"Expected a binary operator\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 539, __extension__
 __PRETTY_FUNCTION__));
assert(cast<ConstantInt>(Ext0->getIndexOperand())->getZExtValue() ==(static_cast <bool> (cast<ConstantInt>(Ext0->getIndexOperand
())->getZExtValue() == cast<ConstantInt>(Ext1->getIndexOperand
())->getZExtValue() && "Expected matching constant extract indexes"
) ? void (0) : __assert_fail ("cast<ConstantInt>(Ext0->getIndexOperand())->getZExtValue() == cast<ConstantInt>(Ext1->getIndexOperand())->getZExtValue() && \"Expected matching constant extract indexes\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 542, __extension__
 __PRETTY_FUNCTION__))
           cast<ConstantInt>(Ext1->getIndexOperand())->getZExtValue() &&(static_cast <bool> (cast<ConstantInt>(Ext0->getIndexOperand
())->getZExtValue() == cast<ConstantInt>(Ext1->getIndexOperand
())->getZExtValue() && "Expected matching constant extract indexes"
) ? void (0) : __assert_fail ("cast<ConstantInt>(Ext0->getIndexOperand())->getZExtValue() == cast<ConstantInt>(Ext1->getIndexOperand())->getZExtValue() && \"Expected matching constant extract indexes\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 542, __extension__
 __PRETTY_FUNCTION__))
       "Expected matching constant extract indexes")(static_cast <bool> (cast<ConstantInt>(Ext0->getIndexOperand
())->getZExtValue() == cast<ConstantInt>(Ext1->getIndexOperand
())->getZExtValue() && "Expected matching constant extract indexes"
) ? void (0) : __assert_fail ("cast<ConstantInt>(Ext0->getIndexOperand())->getZExtValue() == cast<ConstantInt>(Ext1->getIndexOperand())->getZExtValue() && \"Expected matching constant extract indexes\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 542, __extension__
 __PRETTY_FUNCTION__));

// bo (extelt V0, C), (extelt V1, C) --> extelt (bo V0, V1), C
++NumVecBO;
Value *V0 = Ext0->getVectorOperand(), *V1 = Ext1->getVectorOperand();
Value *VecBO =
    Builder.CreateBinOp(cast<BinaryOperator>(&I)->getOpcode(), V0, V1);

// All IR flags are safe to back-propagate because any potential poison
// created in unused vector elements is discarded by the extract.
if (auto *VecBOInst = dyn_cast<Instruction>(VecBO))
  VecBOInst->copyIRFlags(&I);

Value *NewExt = Builder.CreateExtractElement(VecBO, Ext0->getIndexOperand());
replaceValue(I, *NewExt);
557}

559/// Match an instruction with extracted vector operands.
560bool VectorCombine::foldExtractExtract(Instruction &I) {
// It is not safe to transform things like div, urem, etc. because we may
// create undefined behavior when executing those on unknown vector elements.
if (!isSafeToSpeculativelyExecute(&I))
  return false;

Instruction *I0, *I1;
CmpInst::Predicate Pred = CmpInst::BAD_ICMP_PREDICATE;
if (!match(&I, m_Cmp(Pred, m_Instruction(I0), m_Instruction(I1))) &&
    !match(&I, m_BinOp(m_Instruction(I0), m_Instruction(I1))))
  return false;

Value *V0, *V1;
uint64_t C0, C1;
if (!match(I0, m_ExtractElt(m_Value(V0), m_ConstantInt(C0))) ||
    !match(I1, m_ExtractElt(m_Value(V1), m_ConstantInt(C1))) ||
    V0->getType() != V1->getType())
  return false;

// If the scalar value 'I' is going to be re-inserted into a vector, then try
// to create an extract to that same element. The extract/insert can be
// reduced to a "select shuffle".
// TODO: If we add a larger pattern match that starts from an insert, this
//       probably becomes unnecessary.
auto *Ext0 = cast<ExtractElementInst>(I0);
auto *Ext1 = cast<ExtractElementInst>(I1);
uint64_t InsertIndex = InvalidIndex;
if (I.hasOneUse())
  match(I.user_back(),
        m_InsertElt(m_Value(), m_Value(), m_ConstantInt(InsertIndex)));

ExtractElementInst *ExtractToChange;
if (isExtractExtractCheap(Ext0, Ext1, I, ExtractToChange, InsertIndex))
  return false;

if (ExtractToChange) {
  unsigned CheapExtractIdx = ExtractToChange == Ext0 ? C1 : C0;
  ExtractElementInst *NewExtract =
      translateExtract(ExtractToChange, CheapExtractIdx, Builder);
  if (!NewExtract)
    return false;
  if (ExtractToChange == Ext0)
    Ext0 = NewExtract;
  else
    Ext1 = NewExtract;
}

if (Pred != CmpInst::BAD_ICMP_PREDICATE)
  foldExtExtCmp(Ext0, Ext1, I);
else
  foldExtExtBinop(Ext0, Ext1, I);

Worklist.push(Ext0);
Worklist.push(Ext1);
return true;
615}

617/// Try to replace an extract + scalar fneg + insert with a vector fneg +
618/// shuffle.
619bool VectorCombine::foldInsExtFNeg(Instruction &I) {
// Match an insert (op (extract)) pattern.
Value *DestVec;
uint64_t Index;
Instruction *FNeg;
if (!match(&I, m_InsertElt(m_Value(DestVec), m_OneUse(m_Instruction(FNeg)),
                           m_ConstantInt(Index))))
  return false;

// Note: This handles the canonical fneg instruction and "fsub -0.0, X".
Value *SrcVec;
Instruction *Extract;
if (!match(FNeg, m_FNeg(m_CombineAnd(
                     m_Instruction(Extract),
                     m_ExtractElt(m_Value(SrcVec), m_SpecificInt(Index))))))
  return false;

// TODO: We could handle this with a length-changing shuffle.
auto *VecTy = cast<FixedVectorType>(I.getType());
if (SrcVec->getType() != VecTy)
  return false;

// Ignore bogus insert/extract index.
unsigned NumElts = VecTy->getNumElements();
if (Index >= NumElts)
  return false;

// We are inserting the negated element into the same lane that we extracted
// from. This is equivalent to a select-shuffle that chooses all but the
// negated element from the destination vector.
SmallVector<int> Mask(NumElts);
std::iota(Mask.begin(), Mask.end(), 0);
Mask[Index] = Index + NumElts;

Type *ScalarTy = VecTy->getScalarType();
TTI::TargetCostKind CostKind = TTI::TCK_RecipThroughput;
InstructionCost OldCost =
    TTI.getArithmeticInstrCost(Instruction::FNeg, ScalarTy) +
    TTI.getVectorInstrCost(I, VecTy, CostKind, Index);

// If the extract has one use, it will be eliminated, so count it in the
// original cost. If it has more than one use, ignore the cost because it will
// be the same before/after.
if (Extract->hasOneUse())
  OldCost += TTI.getVectorInstrCost(*Extract, VecTy, CostKind, Index);

InstructionCost NewCost =
    TTI.getArithmeticInstrCost(Instruction::FNeg, VecTy) +
    TTI.getShuffleCost(TargetTransformInfo::SK_Select, VecTy, Mask);

if (NewCost > OldCost)
  return false;

// insertelt DestVec, (fneg (extractelt SrcVec, Index)), Index -->
// shuffle DestVec, (fneg SrcVec), Mask
Value *VecFNeg = Builder.CreateFNegFMF(SrcVec, FNeg);
Value *Shuf = Builder.CreateShuffleVector(DestVec, VecFNeg, Mask);
replaceValue(I, *Shuf);
return true;
678}

680/// If this is a bitcast of a shuffle, try to bitcast the source vector to the
681/// destination type followed by shuffle. This can enable further transforms by
682/// moving bitcasts or shuffles together.
683bool VectorCombine::foldBitcastShuf(Instruction &I) {
Value *V;
ArrayRef<int> Mask;
if (!match(&I, m_BitCast(
                   m_OneUse(m_Shuffle(m_Value(V), m_Undef(), m_Mask(Mask))))))
  return false;

// 1) Do not fold bitcast shuffle for scalable type. First, shuffle cost for
// scalable type is unknown; Second, we cannot reason if the narrowed shuffle
// mask for scalable type is a splat or not.
// 2) Disallow non-vector casts and length-changing shuffles.
// TODO: We could allow any shuffle.
auto *SrcTy = dyn_cast<FixedVectorType>(V->getType());
if (!SrcTy || I.getOperand(0)->getType() != SrcTy)
  return false;

auto *DestTy = cast<FixedVectorType>(I.getType());
unsigned DestNumElts = DestTy->getNumElements();
unsigned SrcNumElts = SrcTy->getNumElements();
SmallVector<int, 16> NewMask;
if (SrcNumElts <= DestNumElts) {
  // The bitcast is from wide to narrow/equal elements. The shuffle mask can
  // always be expanded to the equivalent form choosing narrower elements.
  assert(DestNumElts % SrcNumElts == 0 && "Unexpected shuffle mask")(static_cast <bool> (DestNumElts % SrcNumElts == 0 &&
 "Unexpected shuffle mask") ? void (0) : __assert_fail ("DestNumElts % SrcNumElts == 0 && \"Unexpected shuffle mask\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 706, __extension__
 __PRETTY_FUNCTION__));
  unsigned ScaleFactor = DestNumElts / SrcNumElts;
  narrowShuffleMaskElts(ScaleFactor, Mask, NewMask);
} else {
  // The bitcast is from narrow elements to wide elements. The shuffle mask
  // must choose consecutive elements to allow casting first.
  assert(SrcNumElts % DestNumElts == 0 && "Unexpected shuffle mask")(static_cast <bool> (SrcNumElts % DestNumElts == 0 &&
 "Unexpected shuffle mask") ? void (0) : __assert_fail ("SrcNumElts % DestNumElts == 0 && \"Unexpected shuffle mask\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 712, __extension__
 __PRETTY_FUNCTION__));
  unsigned ScaleFactor = SrcNumElts / DestNumElts;
  if (!widenShuffleMaskElts(ScaleFactor, Mask, NewMask))
    return false;
}

// The new shuffle must not cost more than the old shuffle. The bitcast is
// moved ahead of the shuffle, so assume that it has the same cost as before.
InstructionCost DestCost = TTI.getShuffleCost(
    TargetTransformInfo::SK_PermuteSingleSrc, DestTy, NewMask);
InstructionCost SrcCost =
    TTI.getShuffleCost(TargetTransformInfo::SK_PermuteSingleSrc, SrcTy, Mask);
if (DestCost > SrcCost || !DestCost.isValid())
  return false;

// bitcast (shuf V, MaskC) --> shuf (bitcast V), MaskC'
++NumShufOfBitcast;
Value *CastV = Builder.CreateBitCast(V, DestTy);
Value *Shuf = Builder.CreateShuffleVector(CastV, NewMask);
replaceValue(I, *Shuf);
return true;
733}

735/// Match a vector binop or compare instruction with at least one inserted
736/// scalar operand and convert to scalar binop/cmp followed by insertelement.
737bool VectorCombine::scalarizeBinopOrCmp(Instruction &I) {
CmpInst::Predicate Pred = CmpInst::BAD_ICMP_PREDICATE;
Value *Ins0, *Ins1;
if (!match(&I, m_BinOp(m_Value(Ins0), m_Value(Ins1))) &&
    !match(&I, m_Cmp(Pred, m_Value(Ins0), m_Value(Ins1))))
  return false;

// Do not convert the vector condition of a vector select into a scalar
// condition. That may cause problems for codegen because of differences in
// boolean formats and register-file transfers.
// TODO: Can we account for that in the cost model?
bool IsCmp = Pred != CmpInst::Predicate::BAD_ICMP_PREDICATE;
if (IsCmp)
  for (User *U : I.users())
    if (match(U, m_Select(m_Specific(&I), m_Value(), m_Value())))
      return false;

// Match against one or both scalar values being inserted into constant
// vectors:
// vec_op VecC0, (inselt VecC1, V1, Index)
// vec_op (inselt VecC0, V0, Index), VecC1
// vec_op (inselt VecC0, V0, Index), (inselt VecC1, V1, Index)
// TODO: Deal with mismatched index constants and variable indexes?
Constant *VecC0 = nullptr, *VecC1 = nullptr;
Value *V0 = nullptr, *V1 = nullptr;
uint64_t Index0 = 0, Index1 = 0;
if (!match(Ins0, m_InsertElt(m_Constant(VecC0), m_Value(V0),
                             m_ConstantInt(Index0))) &&
    !match(Ins0, m_Constant(VecC0)))
  return false;
if (!match(Ins1, m_InsertElt(m_Constant(VecC1), m_Value(V1),
                             m_ConstantInt(Index1))) &&
    !match(Ins1, m_Constant(VecC1)))
  return false;

bool IsConst0 = !V0;
bool IsConst1 = !V1;
if (IsConst0 && IsConst1)
  return false;
if (!IsConst0 && !IsConst1 && Index0 != Index1)
  return false;

// Bail for single insertion if it is a load.
// TODO: Handle this once getVectorInstrCost can cost for load/stores.
auto *I0 = dyn_cast_or_null<Instruction>(V0);
auto *I1 = dyn_cast_or_null<Instruction>(V1);
if ((IsConst0 && I1 && I1->mayReadFromMemory()) ||
    (IsConst1 && I0 && I0->mayReadFromMemory()))
  return false;

uint64_t Index = IsConst0 ? Index1 : Index0;
Type *ScalarTy = IsConst0 ? V1->getType() : V0->getType();
Type *VecTy = I.getType();
assert(VecTy->isVectorTy() &&(static_cast <bool> (VecTy->isVectorTy() && (
IsConst0 || IsConst1 || V0->getType() == V1->getType())
 && (ScalarTy->isIntegerTy() || ScalarTy->isFloatingPointTy
() || ScalarTy->isPointerTy()) && "Unexpected types for insert element into binop or cmp"
) ? void (0) : __assert_fail ("VecTy->isVectorTy() && (IsConst0 || IsConst1 || V0->getType() == V1->getType()) && (ScalarTy->isIntegerTy() || ScalarTy->isFloatingPointTy() || ScalarTy->isPointerTy()) && \"Unexpected types for insert element into binop or cmp\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 794, __extension__
 __PRETTY_FUNCTION__))
       (IsConst0 || IsConst1 || V0->getType() == V1->getType()) &&(static_cast <bool> (VecTy->isVectorTy() && (
IsConst0 || IsConst1 || V0->getType() == V1->getType())
 && (ScalarTy->isIntegerTy() || ScalarTy->isFloatingPointTy
() || ScalarTy->isPointerTy()) && "Unexpected types for insert element into binop or cmp"
) ? void (0) : __assert_fail ("VecTy->isVectorTy() && (IsConst0 || IsConst1 || V0->getType() == V1->getType()) && (ScalarTy->isIntegerTy() || ScalarTy->isFloatingPointTy() || ScalarTy->isPointerTy()) && \"Unexpected types for insert element into binop or cmp\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 794, __extension__
 __PRETTY_FUNCTION__))
       (ScalarTy->isIntegerTy() || ScalarTy->isFloatingPointTy() ||(static_cast <bool> (VecTy->isVectorTy() && (
IsConst0 || IsConst1 || V0->getType() == V1->getType())
 && (ScalarTy->isIntegerTy() || ScalarTy->isFloatingPointTy
() || ScalarTy->isPointerTy()) && "Unexpected types for insert element into binop or cmp"
) ? void (0) : __assert_fail ("VecTy->isVectorTy() && (IsConst0 || IsConst1 || V0->getType() == V1->getType()) && (ScalarTy->isIntegerTy() || ScalarTy->isFloatingPointTy() || ScalarTy->isPointerTy()) && \"Unexpected types for insert element into binop or cmp\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 794, __extension__
 __PRETTY_FUNCTION__))
        ScalarTy->isPointerTy()) &&(static_cast <bool> (VecTy->isVectorTy() && (
IsConst0 || IsConst1 || V0->getType() == V1->getType())
 && (ScalarTy->isIntegerTy() || ScalarTy->isFloatingPointTy
() || ScalarTy->isPointerTy()) && "Unexpected types for insert element into binop or cmp"
) ? void (0) : __assert_fail ("VecTy->isVectorTy() && (IsConst0 || IsConst1 || V0->getType() == V1->getType()) && (ScalarTy->isIntegerTy() || ScalarTy->isFloatingPointTy() || ScalarTy->isPointerTy()) && \"Unexpected types for insert element into binop or cmp\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 794, __extension__
 __PRETTY_FUNCTION__))
       "Unexpected types for insert element into binop or cmp")(static_cast <bool> (VecTy->isVectorTy() && (
IsConst0 || IsConst1 || V0->getType() == V1->getType())
 && (ScalarTy->isIntegerTy() || ScalarTy->isFloatingPointTy
() || ScalarTy->isPointerTy()) && "Unexpected types for insert element into binop or cmp"
) ? void (0) : __assert_fail ("VecTy->isVectorTy() && (IsConst0 || IsConst1 || V0->getType() == V1->getType()) && (ScalarTy->isIntegerTy() || ScalarTy->isFloatingPointTy() || ScalarTy->isPointerTy()) && \"Unexpected types for insert element into binop or cmp\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 794, __extension__
 __PRETTY_FUNCTION__));

unsigned Opcode = I.getOpcode();
InstructionCost ScalarOpCost, VectorOpCost;
if (IsCmp) {
  CmpInst::Predicate Pred = cast<CmpInst>(I).getPredicate();
  ScalarOpCost = TTI.getCmpSelInstrCost(
      Opcode, ScalarTy, CmpInst::makeCmpResultType(ScalarTy), Pred);
  VectorOpCost = TTI.getCmpSelInstrCost(
      Opcode, VecTy, CmpInst::makeCmpResultType(VecTy), Pred);
} else {
  ScalarOpCost = TTI.getArithmeticInstrCost(Opcode, ScalarTy);
  VectorOpCost = TTI.getArithmeticInstrCost(Opcode, VecTy);
}

// Get cost estimate for the insert element. This cost will factor into
// both sequences.
TTI::TargetCostKind CostKind = TTI::TCK_RecipThroughput;
InstructionCost InsertCost = TTI.getVectorInstrCost(
    Instruction::InsertElement, VecTy, CostKind, Index);
InstructionCost OldCost =
    (IsConst0 ? 0 : InsertCost) + (IsConst1 ? 0 : InsertCost) + VectorOpCost;
InstructionCost NewCost = ScalarOpCost + InsertCost +
                          (IsConst0 ? 0 : !Ins0->hasOneUse() * InsertCost) +
                          (IsConst1 ? 0 : !Ins1->hasOneUse() * InsertCost);

// We want to scalarize unless the vector variant actually has lower cost.
if (OldCost < NewCost || !NewCost.isValid())
  return false;

// vec_op (inselt VecC0, V0, Index), (inselt VecC1, V1, Index) -->
// inselt NewVecC, (scalar_op V0, V1), Index
if (IsCmp)
  ++NumScalarCmp;
else
  ++NumScalarBO;

// For constant cases, extract the scalar element, this should constant fold.
if (IsConst0)
  V0 = ConstantExpr::getExtractElement(VecC0, Builder.getInt64(Index));
if (IsConst1)
  V1 = ConstantExpr::getExtractElement(VecC1, Builder.getInt64(Index));

Value *Scalar =
    IsCmp ? Builder.CreateCmp(Pred, V0, V1)
          : Builder.CreateBinOp((Instruction::BinaryOps)Opcode, V0, V1);

Scalar->setName(I.getName() + ".scalar");

// All IR flags are safe to back-propagate. There is no potential for extra
// poison to be created by the scalar instruction.
if (auto *ScalarInst = dyn_cast<Instruction>(Scalar))
  ScalarInst->copyIRFlags(&I);

// Fold the vector constants in the original vectors into a new base vector.
Value *NewVecC =
    IsCmp ? Builder.CreateCmp(Pred, VecC0, VecC1)
          : Builder.CreateBinOp((Instruction::BinaryOps)Opcode, VecC0, VecC1);
Value *Insert = Builder.CreateInsertElement(NewVecC, Scalar, Index);
replaceValue(I, *Insert);
return true;
855}

857/// Try to combine a scalar binop + 2 scalar compares of extracted elements of
858/// a vector into vector operations followed by extract. Note: The SLP pass
859/// may miss this pattern because of implementation problems.
860bool VectorCombine::foldExtractedCmps(Instruction &I) {
// We are looking for a scalar binop of booleans.
// binop i1 (cmp Pred I0, C0), (cmp Pred I1, C1)
if (!I.isBinaryOp() || !I.getType()->isIntegerTy(1))
  return false;

// The compare predicates should match, and each compare should have a
// constant operand.
// TODO: Relax the one-use constraints.
Value *B0 = I.getOperand(0), *B1 = I.getOperand(1);
Instruction *I0, *I1;
Constant *C0, *C1;
CmpInst::Predicate P0, P1;
if (!match(B0, m_OneUse(m_Cmp(P0, m_Instruction(I0), m_Constant(C0)))) ||
    !match(B1, m_OneUse(m_Cmp(P1, m_Instruction(I1), m_Constant(C1)))) ||
    P0 != P1)
  return false;

// The compare operands must be extracts of the same vector with constant
// extract indexes.
// TODO: Relax the one-use constraints.
Value *X;
uint64_t Index0, Index1;
if (!match(I0, m_OneUse(m_ExtractElt(m_Value(X), m_ConstantInt(Index0)))) ||
    !match(I1, m_OneUse(m_ExtractElt(m_Specific(X), m_ConstantInt(Index1)))))
  return false;

auto *Ext0 = cast<ExtractElementInst>(I0);
auto *Ext1 = cast<ExtractElementInst>(I1);
ExtractElementInst *ConvertToShuf = getShuffleExtract(Ext0, Ext1);
if (!ConvertToShuf)
  return false;

// The original scalar pattern is:
// binop i1 (cmp Pred (ext X, Index0), C0), (cmp Pred (ext X, Index1), C1)
CmpInst::Predicate Pred = P0;
unsigned CmpOpcode = CmpInst::isFPPredicate(Pred) ? Instruction::FCmp
                                                  : Instruction::ICmp;
auto *VecTy = dyn_cast<FixedVectorType>(X->getType());
if (!VecTy)
  return false;

TTI::TargetCostKind CostKind = TTI::TCK_RecipThroughput;
InstructionCost OldCost =
    TTI.getVectorInstrCost(*Ext0, VecTy, CostKind, Index0);
OldCost += TTI.getVectorInstrCost(*Ext1, VecTy, CostKind, Index1);
OldCost +=
    TTI.getCmpSelInstrCost(CmpOpcode, I0->getType(),
                           CmpInst::makeCmpResultType(I0->getType()), Pred) *
    2;
OldCost += TTI.getArithmeticInstrCost(I.getOpcode(), I.getType());

// The proposed vector pattern is:
// vcmp = cmp Pred X, VecC
// ext (binop vNi1 vcmp, (shuffle vcmp, Index1)), Index0
int CheapIndex = ConvertToShuf == Ext0 ? Index1 : Index0;
int ExpensiveIndex = ConvertToShuf == Ext0 ? Index0 : Index1;
auto *CmpTy = cast<FixedVectorType>(CmpInst::makeCmpResultType(X->getType()));
InstructionCost NewCost = TTI.getCmpSelInstrCost(
    CmpOpcode, X->getType(), CmpInst::makeCmpResultType(X->getType()), Pred);
SmallVector<int, 32> ShufMask(VecTy->getNumElements(), UndefMaskElem);
ShufMask[CheapIndex] = ExpensiveIndex;
NewCost += TTI.getShuffleCost(TargetTransformInfo::SK_PermuteSingleSrc, CmpTy,
                              ShufMask);
NewCost += TTI.getArithmeticInstrCost(I.getOpcode(), CmpTy);
NewCost += TTI.getVectorInstrCost(*Ext0, CmpTy, CostKind, CheapIndex);

// Aggressively form vector ops if the cost is equal because the transform
// may enable further optimization.
// Codegen can reverse this transform (scalarize) if it was not profitable.
if (OldCost < NewCost || !NewCost.isValid())
  return false;

// Create a vector constant from the 2 scalar constants.
SmallVector<Constant *, 32> CmpC(VecTy->getNumElements(),
                                 UndefValue::get(VecTy->getElementType()));
CmpC[Index0] = C0;
CmpC[Index1] = C1;
Value *VCmp = Builder.CreateCmp(Pred, X, ConstantVector::get(CmpC));

Value *Shuf = createShiftShuffle(VCmp, ExpensiveIndex, CheapIndex, Builder);
Value *VecLogic = Builder.CreateBinOp(cast<BinaryOperator>(I).getOpcode(),
                                      VCmp, Shuf);
Value *NewExt = Builder.CreateExtractElement(VecLogic, CheapIndex);
replaceValue(I, *NewExt);
++NumVecCmpBO;
return true;
947}

949// Check if memory loc modified between two instrs in the same BB
950static bool isMemModifiedBetween(BasicBlock::iterator Begin,
                               BasicBlock::iterator End,
                               const MemoryLocation &Loc, AAResults &AA) {
unsigned NumScanned = 0;
return std::any_of(Begin, End, [&](const Instruction &Instr) {
  return isModSet(AA.getModRefInfo(&Instr, Loc)) ||
         ++NumScanned > MaxInstrsToScan;
});
958}

960namespace {
961/// Helper class to indicate whether a vector index can be safely scalarized and
962/// if a freeze needs to be inserted.
963class ScalarizationResult {
enum class StatusTy { Unsafe, Safe, SafeWithFreeze };

StatusTy Status;
Value *ToFreeze;

ScalarizationResult(StatusTy Status, Value *ToFreeze = nullptr)
    : Status(Status), ToFreeze(ToFreeze) {}

972public:
ScalarizationResult(const ScalarizationResult &Other) = default;
~ScalarizationResult() {
  assert(!ToFreeze && "freeze() not called with ToFreeze being set")(static_cast <bool> (!ToFreeze && "freeze() not called with ToFreeze being set"
) ? void (0) : __assert_fail ("!ToFreeze && \"freeze() not called with ToFreeze being set\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 975, __extension__
 __PRETTY_FUNCTION__));
}

static ScalarizationResult unsafe() { return {StatusTy::Unsafe}; }
static ScalarizationResult safe() { return {StatusTy::Safe}; }
static ScalarizationResult safeWithFreeze(Value *ToFreeze) {
  return {StatusTy::SafeWithFreeze, ToFreeze};
}

/// Returns true if the index can be scalarize without requiring a freeze.
bool isSafe() const { return Status == StatusTy::Safe; }
/// Returns true if the index cannot be scalarized.
bool isUnsafe() const { return Status == StatusTy::Unsafe; }
/// Returns true if the index can be scalarize, but requires inserting a
/// freeze.
bool isSafeWithFreeze() const { return Status == StatusTy::SafeWithFreeze; }

/// Reset the state of Unsafe and clear ToFreze if set.
void discard() {
  ToFreeze = nullptr;
  Status = StatusTy::Unsafe;
}

/// Freeze the ToFreeze and update the use in \p User to use it.
void freeze(IRBuilder<> &Builder, Instruction &UserI) {
  assert(isSafeWithFreeze() &&(static_cast <bool> (isSafeWithFreeze() && "should only be used when freezing is required"
) ? void (0) : __assert_fail ("isSafeWithFreeze() && \"should only be used when freezing is required\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 1001, __extension__
 __PRETTY_FUNCTION__))
         "should only be used when freezing is required")(static_cast <bool> (isSafeWithFreeze() && "should only be used when freezing is required"
) ? void (0) : __assert_fail ("isSafeWithFreeze() && \"should only be used when freezing is required\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 1001, __extension__
 __PRETTY_FUNCTION__));
  assert(is_contained(ToFreeze->users(), &UserI) &&(static_cast <bool> (is_contained(ToFreeze->users(),
 &UserI) && "UserI must be a user of ToFreeze") ?
 void (0) : __assert_fail ("is_contained(ToFreeze->users(), &UserI) && \"UserI must be a user of ToFreeze\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 1003, __extension__
 __PRETTY_FUNCTION__))
         "UserI must be a user of ToFreeze")(static_cast <bool> (is_contained(ToFreeze->users(),
 &UserI) && "UserI must be a user of ToFreeze") ?
 void (0) : __assert_fail ("is_contained(ToFreeze->users(), &UserI) && \"UserI must be a user of ToFreeze\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 1003, __extension__
 __PRETTY_FUNCTION__));
  IRBuilder<>::InsertPointGuard Guard(Builder);
  Builder.SetInsertPoint(cast<Instruction>(&UserI));
  Value *Frozen =
      Builder.CreateFreeze(ToFreeze, ToFreeze->getName() + ".frozen");
  for (Use &U : make_early_inc_range((UserI.operands())))
    if (U.get() == ToFreeze)
      U.set(Frozen);

  ToFreeze = nullptr;
}
1014};
1015} // namespace

1017/// Check if it is legal to scalarize a memory access to \p VecTy at index \p
1018/// Idx. \p Idx must access a valid vector element.
1019static ScalarizationResult canScalarizeAccess(FixedVectorType *VecTy,
                                            Value *Idx, Instruction *CtxI,
                                            AssumptionCache &AC,
                                            const DominatorTree &DT) {
if (auto *C = dyn_cast<ConstantInt>(Idx)) {
  if (C->getValue().ult(VecTy->getNumElements()))
    return ScalarizationResult::safe();
  return ScalarizationResult::unsafe();
}

unsigned IntWidth = Idx->getType()->getScalarSizeInBits();
APInt Zero(IntWidth, 0);
APInt MaxElts(IntWidth, VecTy->getNumElements());
ConstantRange ValidIndices(Zero, MaxElts);
ConstantRange IdxRange(IntWidth, true);

if (isGuaranteedNotToBePoison(Idx, &AC)) {
  if (ValidIndices.contains(computeConstantRange(Idx, /* ForSigned */ false,
                                                 true, &AC, CtxI, &DT)))
    return ScalarizationResult::safe();
  return ScalarizationResult::unsafe();
}

// If the index may be poison, check if we can insert a freeze before the
// range of the index is restricted.
Value *IdxBase;
ConstantInt *CI;
if (match(Idx, m_And(m_Value(IdxBase), m_ConstantInt(CI)))) {
  IdxRange = IdxRange.binaryAnd(CI->getValue());
} else if (match(Idx, m_URem(m_Value(IdxBase), m_ConstantInt(CI)))) {
  IdxRange = IdxRange.urem(CI->getValue());
}

if (ValidIndices.contains(IdxRange))
  return ScalarizationResult::safeWithFreeze(IdxBase);
return ScalarizationResult::unsafe();
1055}

1057/// The memory operation on a vector of \p ScalarType had alignment of
1058/// \p VectorAlignment. Compute the maximal, but conservatively correct,
1059/// alignment that will be valid for the memory operation on a single scalar
1060/// element of the same type with index \p Idx.
1061static Align computeAlignmentAfterScalarization(Align VectorAlignment,
                                              Type *ScalarType, Value *Idx,
                                              const DataLayout &DL) {
if (auto *C = dyn_cast<ConstantInt>(Idx))
  return commonAlignment(VectorAlignment,
                         C->getZExtValue() * DL.getTypeStoreSize(ScalarType));
return commonAlignment(VectorAlignment, DL.getTypeStoreSize(ScalarType));
1068}

1070// Combine patterns like:
1071//   %0 = load <4 x i32>, <4 x i32>* %a
1072//   %1 = insertelement <4 x i32> %0, i32 %b, i32 1
1073//   store <4 x i32> %1, <4 x i32>* %a
1074// to:
1075//   %0 = bitcast <4 x i32>* %a to i32*
1076//   %1 = getelementptr inbounds i32, i32* %0, i64 0, i64 1
1077//   store i32 %b, i32* %1
1078bool VectorCombine::foldSingleElementStore(Instruction &I) {
auto *SI = cast<StoreInst>(&I);
if (!SI->isSimple() ||
    !isa<FixedVectorType>(SI->getValueOperand()->getType()))
  return false;

// TODO: Combine more complicated patterns (multiple insert) by referencing
// TargetTransformInfo.
Instruction *Source;
Value *NewElement;
Value *Idx;
if (!match(SI->getValueOperand(),
           m_InsertElt(m_Instruction(Source), m_Value(NewElement),
                       m_Value(Idx))))
  return false;

if (auto *Load = dyn_cast<LoadInst>(Source)) {
  auto VecTy = cast<FixedVectorType>(SI->getValueOperand()->getType());
  const DataLayout &DL = I.getModule()->getDataLayout();
  Value *SrcAddr = Load->getPointerOperand()->stripPointerCasts();
  // Don't optimize for atomic/volatile load or store. Ensure memory is not
  // modified between, vector type matches store size, and index is inbounds.
  if (!Load->isSimple() || Load->getParent() != SI->getParent() ||
      !DL.typeSizeEqualsStoreSize(Load->getType()) ||
      SrcAddr != SI->getPointerOperand()->stripPointerCasts())
    return false;

  auto ScalarizableIdx = canScalarizeAccess(VecTy, Idx, Load, AC, DT);
  if (ScalarizableIdx.isUnsafe() ||
      isMemModifiedBetween(Load->getIterator(), SI->getIterator(),
                           MemoryLocation::get(SI), AA))
    return false;

  if (ScalarizableIdx.isSafeWithFreeze())
    ScalarizableIdx.freeze(Builder, *cast<Instruction>(Idx));
  Value *GEP = Builder.CreateInBoundsGEP(
      SI->getValueOperand()->getType(), SI->getPointerOperand(),
      {ConstantInt::get(Idx->getType(), 0), Idx});
  StoreInst *NSI = Builder.CreateStore(NewElement, GEP);
  NSI->copyMetadata(*SI);
  Align ScalarOpAlignment = computeAlignmentAfterScalarization(
      std::max(SI->getAlign(), Load->getAlign()), NewElement->getType(), Idx,
      DL);
  NSI->setAlignment(ScalarOpAlignment);
  replaceValue(I, *NSI);
  eraseInstruction(I);
  return true;
}

return false;
1128}

1130/// Try to scalarize vector loads feeding extractelement instructions.
1131bool VectorCombine::scalarizeLoadExtract(Instruction &I) {
Value *Ptr;
if (!match(&I, m_Load(m_Value(Ptr))))
  return false;

auto *FixedVT = cast<FixedVectorType>(I.getType());
auto *LI = cast<LoadInst>(&I);
const DataLayout &DL = I.getModule()->getDataLayout();
if (LI->isVolatile() || !DL.typeSizeEqualsStoreSize(FixedVT))
  return false;

InstructionCost OriginalCost =
    TTI.getMemoryOpCost(Instruction::Load, FixedVT, LI->getAlign(),
                        LI->getPointerAddressSpace());
InstructionCost ScalarizedCost = 0;

Instruction *LastCheckedInst = LI;
unsigned NumInstChecked = 0;
// Check if all users of the load are extracts with no memory modifications
// between the load and the extract. Compute the cost of both the original
// code and the scalarized version.
for (User *U : LI->users()) {
  auto *UI = dyn_cast<ExtractElementInst>(U);
  if (!UI || UI->getParent() != LI->getParent())
    return false;

  if (!isGuaranteedNotToBePoison(UI->getOperand(1), &AC, LI, &DT))
    return false;

  // Check if any instruction between the load and the extract may modify
  // memory.
  if (LastCheckedInst->comesBefore(UI)) {
    for (Instruction &I :
         make_range(std::next(LI->getIterator()), UI->getIterator())) {
      // Bail out if we reached the check limit or the instruction may write
      // to memory.
      if (NumInstChecked == MaxInstrsToScan || I.mayWriteToMemory())
        return false;
      NumInstChecked++;
    }
    LastCheckedInst = UI;
  }

  auto ScalarIdx = canScalarizeAccess(FixedVT, UI->getOperand(1), &I, AC, DT);
  if (!ScalarIdx.isSafe()) {
    // TODO: Freeze index if it is safe to do so.
    ScalarIdx.discard();
    return false;
  }

  auto *Index = dyn_cast<ConstantInt>(UI->getOperand(1));
  TTI::TargetCostKind CostKind = TTI::TCK_RecipThroughput;
  OriginalCost +=
      TTI.getVectorInstrCost(Instruction::ExtractElement, FixedVT, CostKind,
                             Index ? Index->getZExtValue() : -1);
  ScalarizedCost +=
      TTI.getMemoryOpCost(Instruction::Load, FixedVT->getElementType(),
                          Align(1), LI->getPointerAddressSpace());
  ScalarizedCost += TTI.getAddressComputationCost(FixedVT->getElementType());
}

if (ScalarizedCost >= OriginalCost)
  return false;

// Replace extracts with narrow scalar loads.
for (User *U : LI->users()) {
  auto *EI = cast<ExtractElementInst>(U);
  Builder.SetInsertPoint(EI);

  Value *Idx = EI->getOperand(1);
  Value *GEP =
      Builder.CreateInBoundsGEP(FixedVT, Ptr, {Builder.getInt32(0), Idx});
  auto *NewLoad = cast<LoadInst>(Builder.CreateLoad(
      FixedVT->getElementType(), GEP, EI->getName() + ".scalar"));

  Align ScalarOpAlignment = computeAlignmentAfterScalarization(
      LI->getAlign(), FixedVT->getElementType(), Idx, DL);
  NewLoad->setAlignment(ScalarOpAlignment);

  replaceValue(*EI, *NewLoad);
}

return true;
1214}

1216/// Try to convert "shuffle (binop), (binop)" with a shared binop operand into
1217/// "binop (shuffle), (shuffle)".
1218bool VectorCombine::foldShuffleOfBinops(Instruction &I) {
auto *VecTy = cast<FixedVectorType>(I.getType());
BinaryOperator *B0, *B1;
ArrayRef<int> Mask;
if (!match(&I, m_Shuffle(m_OneUse(m_BinOp(B0)), m_OneUse(m_BinOp(B1)),
                         m_Mask(Mask))) ||
    B0->getOpcode() != B1->getOpcode() || B0->getType() != VecTy)
  return false;

// Try to replace a binop with a shuffle if the shuffle is not costly.
// The new shuffle will choose from a single, common operand, so it may be
// cheaper than the existing two-operand shuffle.
SmallVector<int> UnaryMask = createUnaryMask(Mask, Mask.size());
Instruction::BinaryOps Opcode = B0->getOpcode();
InstructionCost BinopCost = TTI.getArithmeticInstrCost(Opcode, VecTy);
InstructionCost ShufCost = TTI.getShuffleCost(
    TargetTransformInfo::SK_PermuteSingleSrc, VecTy, UnaryMask);
if (ShufCost > BinopCost)
  return false;

// If we have something like "add X, Y" and "add Z, X", swap ops to match.
Value *X = B0->getOperand(0), *Y = B0->getOperand(1);
Value *Z = B1->getOperand(0), *W = B1->getOperand(1);
if (BinaryOperator::isCommutative(Opcode) && X != Z && Y != W)
  std::swap(X, Y);

Value *Shuf0, *Shuf1;
if (X == Z) {
  // shuf (bo X, Y), (bo X, W) --> bo (shuf X), (shuf Y, W)
  Shuf0 = Builder.CreateShuffleVector(X, UnaryMask);
  Shuf1 = Builder.CreateShuffleVector(Y, W, Mask);
} else if (Y == W) {
  // shuf (bo X, Y), (bo Z, Y) --> bo (shuf X, Z), (shuf Y)
  Shuf0 = Builder.CreateShuffleVector(X, Z, Mask);
  Shuf1 = Builder.CreateShuffleVector(Y, UnaryMask);
} else {
  return false;
}

Value *NewBO = Builder.CreateBinOp(Opcode, Shuf0, Shuf1);
// Intersect flags from the old binops.
if (auto *NewInst = dyn_cast<Instruction>(NewBO)) {
  NewInst->copyIRFlags(B0);
  NewInst->andIRFlags(B1);
}
replaceValue(I, *NewBO);
return true;
1265}

1267/// Given a commutative reduction, the order of the input lanes does not alter
1268/// the results. We can use this to remove certain shuffles feeding the
1269/// reduction, removing the need to shuffle at all.
1270bool VectorCombine::foldShuffleFromReductions(Instruction &I) {
auto *II = dyn_cast<IntrinsicInst>(&I);
if (!II)
  return false;
switch (II->getIntrinsicID()) {
case Intrinsic::vector_reduce_add:
case Intrinsic::vector_reduce_mul:
case Intrinsic::vector_reduce_and:
case Intrinsic::vector_reduce_or:
case Intrinsic::vector_reduce_xor:
case Intrinsic::vector_reduce_smin:
case Intrinsic::vector_reduce_smax:
case Intrinsic::vector_reduce_umin:
case Intrinsic::vector_reduce_umax:
  break;
default:
  return false;
}

// Find all the inputs when looking through operations that do not alter the
// lane order (binops, for example). Currently we look for a single shuffle,
// and can ignore splat values.
std::queue<Value *> Worklist;
SmallPtrSet<Value *, 4> Visited;
ShuffleVectorInst *Shuffle = nullptr;
if (auto *Op = dyn_cast<Instruction>(I.getOperand(0)))
  Worklist.push(Op);

while (!Worklist.empty()) {
  Value *CV = Worklist.front();
  Worklist.pop();
  if (Visited.contains(CV))
    continue;

  // Splats don't change the order, so can be safely ignored.
  if (isSplatValue(CV))
    continue;

  Visited.insert(CV);

  if (auto *CI = dyn_cast<Instruction>(CV)) {
    if (CI->isBinaryOp()) {
      for (auto *Op : CI->operand_values())
        Worklist.push(Op);
      continue;
    } else if (auto *SV = dyn_cast<ShuffleVectorInst>(CI)) {
      if (Shuffle && Shuffle != SV)
        return false;
      Shuffle = SV;
      continue;
    }
  }

  // Anything else is currently an unknown node.
  return false;
}

if (!Shuffle)
  return false;

// Check all uses of the binary ops and shuffles are also included in the
// lane-invariant operations (Visited should be the list of lanewise
// instructions, including the shuffle that we found).
for (auto *V : Visited)
  for (auto *U : V->users())
    if (!Visited.contains(U) && U != &I)
      return false;

FixedVectorType *VecType =
    dyn_cast<FixedVectorType>(II->getOperand(0)->getType());
if (!VecType)
  return false;
FixedVectorType *ShuffleInputType =
    dyn_cast<FixedVectorType>(Shuffle->getOperand(0)->getType());
if (!ShuffleInputType)
  return false;
int NumInputElts = ShuffleInputType->getNumElements();

// Find the mask from sorting the lanes into order. This is most likely to
// become a identity or concat mask. Undef elements are pushed to the end.
SmallVector<int> ConcatMask;
Shuffle->getShuffleMask(ConcatMask);
sort(ConcatMask, [](int X, int Y) { return (unsigned)X < (unsigned)Y; });
bool UsesSecondVec =
    any_of(ConcatMask, [&](int M) { return M >= NumInputElts; });
InstructionCost OldCost = TTI.getShuffleCost(
    UsesSecondVec ? TTI::SK_PermuteTwoSrc : TTI::SK_PermuteSingleSrc, VecType,
    Shuffle->getShuffleMask());
InstructionCost NewCost = TTI.getShuffleCost(
    UsesSecondVec ? TTI::SK_PermuteTwoSrc : TTI::SK_PermuteSingleSrc, VecType,
    ConcatMask);

LLVM_DEBUG(dbgs() << "Found a reduction feeding from a shuffle: " << *Shuffledo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vector-combine")) { dbgs() << "Found a reduction feeding from a shuffle: "
 << *Shuffle << "\n"; } } while (false)
                  << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vector-combine")) { dbgs() << "Found a reduction feeding from a shuffle: "
 << *Shuffle << "\n"; } } while (false);
LLVM_DEBUG(dbgs() << "  OldCost: " << OldCost << " vs NewCost: " << NewCostdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vector-combine")) { dbgs() << "  OldCost: " << OldCost
 << " vs NewCost: " << NewCost << "\n"; } }
 while (false)
                  << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vector-combine")) { dbgs() << "  OldCost: " << OldCost
 << " vs NewCost: " << NewCost << "\n"; } }
 while (false);
if (NewCost < OldCost) {
  Builder.SetInsertPoint(Shuffle);
  Value *NewShuffle = Builder.CreateShuffleVector(
      Shuffle->getOperand(0), Shuffle->getOperand(1), ConcatMask);
  LLVM_DEBUG(dbgs() << "Created new shuffle: " << *NewShuffle << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vector-combine")) { dbgs() << "Created new shuffle: "
 << *NewShuffle << "\n"; } } while (false);
  replaceValue(*Shuffle, *NewShuffle);
}

// See if we can re-use foldSelectShuffle, getting it to reduce the size of
// the shuffle into a nicer order, as it can ignore the order of the shuffles.
return foldSelectShuffle(*Shuffle, true);
1377}

1379/// This method looks for groups of shuffles acting on binops, of the form:
1380///  %x = shuffle ...
1381///  %y = shuffle ...
1382///  %a = binop %x, %y
1383///  %b = binop %x, %y
1384///  shuffle %a, %b, selectmask
1385/// We may, especially if the shuffle is wider than legal, be able to convert
1386/// the shuffle to a form where only parts of a and b need to be computed. On
1387/// architectures with no obvious "select" shuffle, this can reduce the total
1388/// number of operations if the target reports them as cheaper.
1389bool VectorCombine::foldSelectShuffle(Instruction &I, bool FromReduction) {
auto *SVI = cast<ShuffleVectorInst>(&I);
auto *VT = cast<FixedVectorType>(I.getType());
auto *Op0 = dyn_cast<Instruction>(SVI->getOperand(0));
auto *Op1 = dyn_cast<Instruction>(SVI->getOperand(1));
if (!Op0 || !Op1 || Op0 == Op1 || !Op0->isBinaryOp() || !Op1->isBinaryOp() ||
    VT != Op0->getType())
  return false;

auto *SVI0A = dyn_cast<Instruction>(Op0->getOperand(0));
auto *SVI0B = dyn_cast<Instruction>(Op0->getOperand(1));
auto *SVI1A = dyn_cast<Instruction>(Op1->getOperand(0));
auto *SVI1B = dyn_cast<Instruction>(Op1->getOperand(1));
SmallPtrSet<Instruction *, 4> InputShuffles({SVI0A, SVI0B, SVI1A, SVI1B});
auto checkSVNonOpUses = [&](Instruction *I) {
  if (!I || I->getOperand(0)->getType() != VT)
    return true;
  return any_of(I->users(), [&](User *U) {
    return U != Op0 && U != Op1 &&
           !(isa<ShuffleVectorInst>(U) &&
             (InputShuffles.contains(cast<Instruction>(U)) ||
              isInstructionTriviallyDead(cast<Instruction>(U))));
  });
};
if (checkSVNonOpUses(SVI0A) || checkSVNonOpUses(SVI0B) ||
    checkSVNonOpUses(SVI1A) || checkSVNonOpUses(SVI1B))
  return false;

// Collect all the uses that are shuffles that we can transform together. We
// may not have a single shuffle, but a group that can all be transformed
// together profitably.
SmallVector<ShuffleVectorInst *> Shuffles;
auto collectShuffles = [&](Instruction *I) {
  for (auto *U : I->users()) {
    auto *SV = dyn_cast<ShuffleVectorInst>(U);
    if (!SV || SV->getType() != VT)
      return false;
    if ((SV->getOperand(0) != Op0 && SV->getOperand(0) != Op1) ||
        (SV->getOperand(1) != Op0 && SV->getOperand(1) != Op1))
      return false;
    if (!llvm::is_contained(Shuffles, SV))
      Shuffles.push_back(SV);
  }
  return true;
};
if (!collectShuffles(Op0) || !collectShuffles(Op1))
  return false;
// From a reduction, we need to be processing a single shuffle, otherwise the
// other uses will not be lane-invariant.
if (FromReduction && Shuffles.size() > 1)
  return false;

// Add any shuffle uses for the shuffles we have found, to include them in our
// cost calculations.
if (!FromReduction) {
  for (ShuffleVectorInst *SV : Shuffles) {
    for (auto *U : SV->users()) {
      ShuffleVectorInst *SSV = dyn_cast<ShuffleVectorInst>(U);
      if (SSV && isa<UndefValue>(SSV->getOperand(1)) && SSV->getType() == VT)
        Shuffles.push_back(SSV);
    }
  }
}

// For each of the output shuffles, we try to sort all the first vector
// elements to the beginning, followed by the second array elements at the
// end. If the binops are legalized to smaller vectors, this may reduce total
// number of binops. We compute the ReconstructMask mask needed to convert
// back to the original lane order.
SmallVector<std::pair<int, int>> V1, V2;
SmallVector<SmallVector<int>> OrigReconstructMasks;
int MaxV1Elt = 0, MaxV2Elt = 0;
unsigned NumElts = VT->getNumElements();
for (ShuffleVectorInst *SVN : Shuffles) {
  SmallVector<int> Mask;
  SVN->getShuffleMask(Mask);

  // Check the operands are the same as the original, or reversed (in which
  // case we need to commute the mask).
  Value *SVOp0 = SVN->getOperand(0);
  Value *SVOp1 = SVN->getOperand(1);
  if (isa<UndefValue>(SVOp1)) {
    auto *SSV = cast<ShuffleVectorInst>(SVOp0);
    SVOp0 = SSV->getOperand(0);
    SVOp1 = SSV->getOperand(1);
    for (unsigned I = 0, E = Mask.size(); I != E; I++) {
      if (Mask[I] >= static_cast<int>(SSV->getShuffleMask().size()))
        return false;
      Mask[I] = Mask[I] < 0 ? Mask[I] : SSV->getMaskValue(Mask[I]);
    }
  }
  if (SVOp0 == Op1 && SVOp1 == Op0) {
    std::swap(SVOp0, SVOp1);
    ShuffleVectorInst::commuteShuffleMask(Mask, NumElts);
  }
  if (SVOp0 != Op0 || SVOp1 != Op1)
    return false;

  // Calculate the reconstruction mask for this shuffle, as the mask needed to
  // take the packed values from Op0/Op1 and reconstructing to the original
  // order.
  SmallVector<int> ReconstructMask;
  for (unsigned I = 0; I < Mask.size(); I++) {
    if (Mask[I] < 0) {
      ReconstructMask.push_back(-1);
    } else if (Mask[I] < static_cast<int>(NumElts)) {
      MaxV1Elt = std::max(MaxV1Elt, Mask[I]);
      auto It = find_if(V1, [&](const std::pair<int, int> &A) {
        return Mask[I] == A.first;
      });
      if (It != V1.end())
        ReconstructMask.push_back(It - V1.begin());
      else {
        ReconstructMask.push_back(V1.size());
        V1.emplace_back(Mask[I], V1.size());
      }
    } else {
      MaxV2Elt = std::max<int>(MaxV2Elt, Mask[I] - NumElts);
      auto It = find_if(V2, [&](const std::pair<int, int> &A) {
        return Mask[I] - static_cast<int>(NumElts) == A.first;
      });
      if (It != V2.end())
        ReconstructMask.push_back(NumElts + It - V2.begin());
      else {
        ReconstructMask.push_back(NumElts + V2.size());
        V2.emplace_back(Mask[I] - NumElts, NumElts + V2.size());
      }
    }
  }

  // For reductions, we know that the lane ordering out doesn't alter the
  // result. In-order can help simplify the shuffle away.
  if (FromReduction)
    sort(ReconstructMask);
  OrigReconstructMasks.push_back(std::move(ReconstructMask));
}

// If the Maximum element used from V1 and V2 are not larger than the new
// vectors, the vectors are already packes and performing the optimization
// again will likely not help any further. This also prevents us from getting
// stuck in a cycle in case the costs do not also rule it out.
if (V1.empty() || V2.empty() ||
    (MaxV1Elt == static_cast<int>(V1.size()) - 1 &&
     MaxV2Elt == static_cast<int>(V2.size()) - 1))
  return false;

// GetBaseMaskValue takes one of the inputs, which may either be a shuffle, a
// shuffle of another shuffle, or not a shuffle (that is treated like a
// identity shuffle).
auto GetBaseMaskValue = [&](Instruction *I, int M) {
  auto *SV = dyn_cast<ShuffleVectorInst>(I);
  if (!SV)
    return M;
  if (isa<UndefValue>(SV->getOperand(1)))
    if (auto *SSV = dyn_cast<ShuffleVectorInst>(SV->getOperand(0)))
      if (InputShuffles.contains(SSV))
        return SSV->getMaskValue(SV->getMaskValue(M));
  return SV->getMaskValue(M);
};

// Attempt to sort the inputs my ascending mask values to make simpler input
// shuffles and push complex shuffles down to the uses. We sort on the first
// of the two input shuffle orders, to try and get at least one input into a
// nice order.
auto SortBase = [&](Instruction *A, std::pair<int, int> X,
                    std::pair<int, int> Y) {
  int MXA = GetBaseMaskValue(A, X.first);
  int MYA = GetBaseMaskValue(A, Y.first);
  return MXA < MYA;
};
stable_sort(V1, [&](std::pair<int, int> A, std::pair<int, int> B) {
  return SortBase(SVI0A, A, B);
});
stable_sort(V2, [&](std::pair<int, int> A, std::pair<int, int> B) {
  return SortBase(SVI1A, A, B);
});
// Calculate our ReconstructMasks from the OrigReconstructMasks and the
// modified order of the input shuffles.
SmallVector<SmallVector<int>> ReconstructMasks;
for (auto Mask : OrigReconstructMasks) {
  SmallVector<int> ReconstructMask;
  for (int M : Mask) {
    auto FindIndex = [](const SmallVector<std::pair<int, int>> &V, int M) {
      auto It = find_if(V, [M](auto A) { return A.second == M; });
      assert(It != V.end() && "Expected all entries in Mask")(static_cast <bool> (It != V.end() && "Expected all entries in Mask"
) ? void (0) : __assert_fail ("It != V.end() && \"Expected all entries in Mask\""
, "llvm/lib/Transforms/Vectorize/VectorCombine.cpp", 1573, __extension__
 __PRETTY_FUNCTION__));
      return std::distance(V.begin(), It);
    };
    if (M < 0)
      ReconstructMask.push_back(-1);
    else if (M < static_cast<int>(NumElts)) {
      ReconstructMask.push_back(FindIndex(V1, M));
    } else {
      ReconstructMask.push_back(NumElts + FindIndex(V2, M));
    }
  }
  ReconstructMasks.push_back(std::move(ReconstructMask));
}

// Calculate the masks needed for the new input shuffles, which get padded
// with undef
SmallVector<int> V1A, V1B, V2A, V2B;
for (unsigned I = 0; I < V1.size(); I++) {
  V1A.push_back(GetBaseMaskValue(SVI0A, V1[I].first));
  V1B.push_back(GetBaseMaskValue(SVI0B, V1[I].first));
}
for (unsigned I = 0; I < V2.size(); I++) {
  V2A.push_back(GetBaseMaskValue(SVI1A, V2[I].first));
  V2B.push_back(GetBaseMaskValue(SVI1B, V2[I].first));
}
while (V1A.size() < NumElts) {
  V1A.push_back(UndefMaskElem);
  V1B.push_back(UndefMaskElem);
}
while (V2A.size() < NumElts) {
  V2A.push_back(UndefMaskElem);
  V2B.push_back(UndefMaskElem);
}

auto AddShuffleCost = [&](InstructionCost C, Instruction *I) {
  auto *SV = dyn_cast<ShuffleVectorInst>(I);
  if (!SV)
    return C;
  return C + TTI.getShuffleCost(isa<UndefValue>(SV->getOperand(1))
                                    ? TTI::SK_PermuteSingleSrc
                                    : TTI::SK_PermuteTwoSrc,
                                VT, SV->getShuffleMask());
};
auto AddShuffleMaskCost = [&](InstructionCost C, ArrayRef<int> Mask) {
  return C + TTI.getShuffleCost(TTI::SK_PermuteTwoSrc, VT, Mask);
};

// Get the costs of the shuffles + binops before and after with the new
// shuffle masks.
InstructionCost CostBefore =
    TTI.getArithmeticInstrCost(Op0->getOpcode(), VT) +
    TTI.getArithmeticInstrCost(Op1->getOpcode(), VT);
CostBefore += std::accumulate(Shuffles.begin(), Shuffles.end(),
                              InstructionCost(0), AddShuffleCost);
CostBefore += std::accumulate(InputShuffles.begin(), InputShuffles.end(),
                              InstructionCost(0), AddShuffleCost);

// The new binops will be unused for lanes past the used shuffle lengths.
// These types attempt to get the correct cost for that from the target.
FixedVectorType *Op0SmallVT =
    FixedVectorType::get(VT->getScalarType(), V1.size());
FixedVectorType *Op1SmallVT =
    FixedVectorType::get(VT->getScalarType(), V2.size());
InstructionCost CostAfter =
    TTI.getArithmeticInstrCost(Op0->getOpcode(), Op0SmallVT) +
    TTI.getArithmeticInstrCost(Op1->getOpcode(), Op1SmallVT);
CostAfter += std::accumulate(ReconstructMasks.begin(), ReconstructMasks.end(),
                             InstructionCost(0), AddShuffleMaskCost);
std::set<SmallVector<int>> OutputShuffleMasks({V1A, V1B, V2A, V2B});
CostAfter +=
    std::accumulate(OutputShuffleMasks.begin(), OutputShuffleMasks.end(),
                    InstructionCost(0), AddShuffleMaskCost);

LLVM_DEBUG(dbgs() << "Found a binop select shuffle pattern: " << I << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vector-combine")) { dbgs() << "Found a binop select shuffle pattern: "
 << I << "\n"; } } while (false);
LLVM_DEBUG(dbgs() << "  CostBefore: " << CostBeforedo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vector-combine")) { dbgs() << "  CostBefore: " <<
 CostBefore << " vs CostAfter: " << CostAfter <<
 "\n"; } } while (false)
                  << " vs CostAfter: " << CostAfter << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("vector-combine")) { dbgs() << "  CostBefore: " <<
 CostBefore << " vs CostAfter: " << CostAfter <<
 "\n"; } } while (false);
if (CostBefore <= CostAfter)
  return false;

// The cost model has passed, create the new instructions.
auto GetShuffleOperand = [&](Instruction *I, unsigned Op) -> Value * {
  auto *SV = dyn_cast<ShuffleVectorInst>(I);
  if (!SV)
    return I;
  if (isa<UndefValue>(SV->getOperand(1)))
    if (auto *SSV = dyn_cast<ShuffleVectorInst>(SV->getOperand(0)))
      if (InputShuffles.contains(SSV))
        return SSV->getOperand(Op);
  return SV->getOperand(Op);
};
Builder.SetInsertPoint(SVI0A->getNextNode());
Value *NSV0A = Builder.CreateShuffleVector(GetShuffleOperand(SVI0A, 0),
                                           GetShuffleOperand(SVI0A, 1), V1A);
Builder.SetInsertPoint(SVI0B->getNextNode());
Value *NSV0B = Builder.CreateShuffleVector(GetShuffleOperand(SVI0B, 0),
                                           GetShuffleOperand(SVI0B, 1), V1B);
Builder.SetInsertPoint(SVI1A->getNextNode());
Value *NSV1A = Builder.CreateShuffleVector(GetShuffleOperand(SVI1A, 0),
                                           GetShuffleOperand(SVI1A, 1), V2A);
Builder.SetInsertPoint(SVI1B->getNextNode());
Value *NSV1B = Builder.CreateShuffleVector(GetShuffleOperand(SVI1B, 0),
                                           GetShuffleOperand(SVI1B, 1), V2B);
Builder.SetInsertPoint(Op0);
Value *NOp0 = Builder.CreateBinOp((Instruction::BinaryOps)Op0->getOpcode(),
                                  NSV0A, NSV0B);
if (auto *I = dyn_cast<Instruction>(NOp0))
  I->copyIRFlags(Op0, true);
Builder.SetInsertPoint(Op1);
Value *NOp1 = Builder.CreateBinOp((Instruction::BinaryOps)Op1->getOpcode(),
                                  NSV1A, NSV1B);
if (auto *I = dyn_cast<Instruction>(NOp1))
  I->copyIRFlags(Op1, true);

for (int S = 0, E = ReconstructMasks.size(); S != E; S++) {
  Builder.SetInsertPoint(Shuffles[S]);
  Value *NSV = Builder.CreateShuffleVector(NOp0, NOp1, ReconstructMasks[S]);
  replaceValue(*Shuffles[S], *NSV);
}

Worklist.pushValue(NSV0A);
Worklist.pushValue(NSV0B);
Worklist.pushValue(NSV1A);
Worklist.pushValue(NSV1B);
for (auto *S : Shuffles)
  Worklist.add(S);
return true;
1699}

1701/// This is the entry point for all transforms. Pass manager differences are
1702/// handled in the callers of this function.
1703bool VectorCombine::run() {
if (DisableVectorCombine)
4
←
Assuming the condition is false→
5
←
Taking false branch→
  return false;

// Don't attempt vectorization if the target does not support vectors.
if (!TTI.getNumberOfRegisters(TTI.getRegisterClassForType(/*Vector*/ true)))
6
←
Assuming the condition is false→
7
←
Taking false branch→
  return false;

bool MadeChange = false;
auto FoldInst = [this, &MadeChange](Instruction &I) {
  Builder.SetInsertPoint(&I);
  bool IsFixedVectorType = isa<FixedVectorType>(I.getType());
14
←
Assuming the object is a 'class llvm::FixedVectorType &'→
  auto Opcode = I.getOpcode();

  // These folds should be beneficial regardless of when this pass is run
  // in the optimization pipeline.
  // The type checking is for run-time efficiency. We can avoid wasting time
  // dispatching to folding functions if there's no chance of matching.
  if (IsFixedVectorType14.1
'IsFixedVectorType' is true
) {
15
←
Taking true branch→
    switch (Opcode) {
16
←
Control jumps to 'case ShuffleVector:'  at line 1726→
    case Instruction::InsertElement:
      MadeChange |= vectorizeLoadInsert(I);
      break;
    case Instruction::ShuffleVector:
      MadeChange |= widenSubvectorLoad(I);
17
←
Calling 'VectorCombine::widenSubvectorLoad'→
      break;
    case Instruction::Load:
      MadeChange |= scalarizeLoadExtract(I);
      break;
    default:
      break;
    }
  }

  // This transform works with scalable and fixed vectors
  // TODO: Identify and allow other scalable transforms
  if (isa<VectorType>(I.getType()))
    MadeChange |= scalarizeBinopOrCmp(I);

  if (Opcode == Instruction::Store)
    MadeChange |= foldSingleElementStore(I);


  // If this is an early pipeline invocation of this pass, we are done.
  if (TryEarlyFoldsOnly)
    return;

  // Otherwise, try folds that improve codegen but may interfere with
  // early IR canonicalizations.
  // The type checking is for run-time efficiency. We can avoid wasting time
  // dispatching to folding functions if there's no chance of matching.
  if (IsFixedVectorType) {
    switch (Opcode) {
    case Instruction::InsertElement:
      MadeChange |= foldInsExtFNeg(I);
      break;
    case Instruction::ShuffleVector:
      MadeChange |= foldShuffleOfBinops(I);
      MadeChange |= foldSelectShuffle(I);
      break;
    case Instruction::BitCast:
      MadeChange |= foldBitcastShuf(I);
      break;
    }
  } else {
    switch (Opcode) {
    case Instruction::Call:
      MadeChange |= foldShuffleFromReductions(I);
      break;
    case Instruction::ICmp:
    case Instruction::FCmp:
      MadeChange |= foldExtractExtract(I);
      break;
    default:
      if (Instruction::isBinaryOp(Opcode)) {
        MadeChange |= foldExtractExtract(I);
        MadeChange |= foldExtractedCmps(I);
      }
      break;
    }
  }
};

for (BasicBlock &BB : F) {
  // Ignore unreachable basic blocks.
  if (!DT.isReachableFromEntry(&BB))
    continue;
  // Use early increment range so that we can erase instructions in loop.
  for (Instruction &I : make_early_inc_range(BB)) {
    if (I.isDebugOrPseudoInst())
      continue;
    FoldInst(I);
  }
}

while (!Worklist.isEmpty()) {
8
←
Loop condition is true.  Entering loop body→
  Instruction *I = Worklist.removeOne();
  if (!I)
9
←
Assuming 'I' is non-null→
10
←
Taking false branch→
    continue;

  if (isInstructionTriviallyDead(I)) {
11
←
Assuming the condition is false→
12
←
Taking false branch→
    eraseInstruction(*I);
    continue;
  }

  FoldInst(*I);
13
←
Calling 'operator()'→
}

return MadeChange;
1812}

1814// Pass manager boilerplate below here.

1816namespace {
1817class VectorCombineLegacyPass : public FunctionPass {
1818public:
static char ID;
VectorCombineLegacyPass() : FunctionPass(ID) {
  initializeVectorCombineLegacyPassPass(*PassRegistry::getPassRegistry());
}

void getAnalysisUsage(AnalysisUsage &AU) const override {
  AU.addRequired<AssumptionCacheTracker>();
  AU.addRequired<DominatorTreeWrapperPass>();
  AU.addRequired<TargetTransformInfoWrapperPass>();
  AU.addRequired<AAResultsWrapperPass>();
  AU.setPreservesCFG();
  AU.addPreserved<DominatorTreeWrapperPass>();
  AU.addPreserved<GlobalsAAWrapperPass>();
  AU.addPreserved<AAResultsWrapperPass>();
  AU.addPreserved<BasicAAWrapperPass>();
  FunctionPass::getAnalysisUsage(AU);
}

bool runOnFunction(Function &F) override {
  if (skipFunction(F))
1
Assuming the condition is false→
2
←
Taking false branch→
    return false;
  auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
  auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
  auto &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
  VectorCombine Combiner(F, TTI, DT, AA, AC, false);
  return Combiner.run();
3
←
Calling 'VectorCombine::run'→
}
1847};
1848} // namespace

1850char VectorCombineLegacyPass::ID = 0;
1851INITIALIZE_PASS_BEGIN(VectorCombineLegacyPass, "vector-combine",static void *initializeVectorCombineLegacyPassPassOnce(PassRegistry
 &Registry) {
                    "Optimize scalar/vector ops", false,static void *initializeVectorCombineLegacyPassPassOnce(PassRegistry
 &Registry) {
                    false)static void *initializeVectorCombineLegacyPassPassOnce(PassRegistry
 &Registry) {
1854INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)initializeAssumptionCacheTrackerPass(Registry);
1855INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry);
1856INITIALIZE_PASS_END(VectorCombineLegacyPass, "vector-combine",PassInfo *PI = new PassInfo( "Optimize scalar/vector ops", "vector-combine"
, &VectorCombineLegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<VectorCombineLegacyPass>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeVectorCombineLegacyPassPassFlag
; void llvm::initializeVectorCombineLegacyPassPass(PassRegistry
 &Registry) { llvm::call_once(InitializeVectorCombineLegacyPassPassFlag
, initializeVectorCombineLegacyPassPassOnce, std::ref(Registry
)); }
                  "Optimize scalar/vector ops", false, false)PassInfo *PI = new PassInfo( "Optimize scalar/vector ops", "vector-combine"
, &VectorCombineLegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<VectorCombineLegacyPass>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeVectorCombineLegacyPassPassFlag
; void llvm::initializeVectorCombineLegacyPassPass(PassRegistry
 &Registry) { llvm::call_once(InitializeVectorCombineLegacyPassPassFlag
, initializeVectorCombineLegacyPassPassOnce, std::ref(Registry
)); }
1858Pass *llvm::createVectorCombinePass() {
return new VectorCombineLegacyPass();
1860}

1862PreservedAnalyses VectorCombinePass::run(Function &F,
                                       FunctionAnalysisManager &FAM) {
auto &AC = FAM.getResult<AssumptionAnalysis>(F);
TargetTransformInfo &TTI = FAM.getResult<TargetIRAnalysis>(F);
DominatorTree &DT = FAM.getResult<DominatorTreeAnalysis>(F);
AAResults &AA = FAM.getResult<AAManager>(F);
VectorCombine Combiner(F, TTI, DT, AA, AC, TryEarlyFoldsOnly);
if (!Combiner.run())
  return PreservedAnalyses::all();
PreservedAnalyses PA;
PA.preserveSet<CFGAnalyses>();
return PA;
1874}