InstCombineVectorOps.cpp | Explore in Territory

//===- InstCombineVectorOps.cpp -------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements instcombine for ExtractElement, InsertElement and
// ShuffleVector.
//
//===----------------------------------------------------------------------===//

#include "InstCombineInternal.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallBitVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/VectorUtils.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Transforms/InstCombine/InstCombiner.h"
#include <cassert>
#include <cstdint>
#include <iterator>
#include <utility>

#define DEBUG_TYPE …

usingnamespacellvm;
usingnamespacePatternMatch;

STATISTIC(NumAggregateReconstructionsSimplified,
          "Number of aggregate reconstructions turned into reuse of the "
          "original aggregate");

/// Return true if the value is cheaper to scalarize than it is to leave as a
/// vector operation. If the extract index \p EI is a constant integer then
/// some operations may be cheap to scalarize.
///
/// FIXME: It's possible to create more instructions than previously existed.
static bool cheapToScalarize(Value *V, Value *EI) { … }

// If we have a PHI node with a vector type that is only used to feed
// itself and be an operand of extractelement at a constant location,
// try to replace the PHI of the vector type with a PHI of a scalar type.
Instruction *InstCombinerImpl::scalarizePHI(ExtractElementInst &EI,
                                            PHINode *PN) { … }

Instruction *InstCombinerImpl::foldBitcastExtElt(ExtractElementInst &Ext) { … }

/// Find elements of V demanded by UserInstr.
static APInt findDemandedEltsBySingleUser(Value *V, Instruction *UserInstr) { … }

/// Find union of elements of V demanded by all its users.
/// If it is known by querying findDemandedEltsBySingleUser that
/// no user demands an element of V, then the corresponding bit
/// remains unset in the returned value.
static APInt findDemandedEltsByAllUsers(Value *V) { … }

/// Given a constant index for a extractelement or insertelement instruction,
/// return it with the canonical type if it isn't already canonical.  We
/// arbitrarily pick 64 bit as our canonical type.  The actual bitwidth doesn't
/// matter, we just want a consistent type to simplify CSE.
static ConstantInt *getPreferredVectorIndex(ConstantInt *IndexC) { … }

Instruction *InstCombinerImpl::visitExtractElementInst(ExtractElementInst &EI) { … }

/// If V is a shuffle of values that ONLY returns elements from either LHS or
/// RHS, return the shuffle mask and true. Otherwise, return false.
static bool collectSingleShuffleElements(Value *V, Value *LHS, Value *RHS,
                                         SmallVectorImpl<int> &Mask) { … }

/// If we have insertion into a vector that is wider than the vector that we
/// are extracting from, try to widen the source vector to allow a single
/// shufflevector to replace one or more insert/extract pairs.
static bool replaceExtractElements(InsertElementInst *InsElt,
                                   ExtractElementInst *ExtElt,
                                   InstCombinerImpl &IC) { … }

/// We are building a shuffle to create V, which is a sequence of insertelement,
/// extractelement pairs. If PermittedRHS is set, then we must either use it or
/// not rely on the second vector source. Return a std::pair containing the
/// left and right vectors of the proposed shuffle (or 0), and set the Mask
/// parameter as required.
///
/// Note: we intentionally don't try to fold earlier shuffles since they have
/// often been chosen carefully to be efficiently implementable on the target.
ShuffleOps;

static ShuffleOps collectShuffleElements(Value *V, SmallVectorImpl<int> &Mask,
                                         Value *PermittedRHS,
                                         InstCombinerImpl &IC, bool &Rerun) { … }

/// Look for chain of insertvalue's that fully define an aggregate, and trace
/// back the values inserted, see if they are all were extractvalue'd from
/// the same source aggregate from the exact same element indexes.
/// If they were, just reuse the source aggregate.
/// This potentially deals with PHI indirections.
Instruction *InstCombinerImpl::foldAggregateConstructionIntoAggregateReuse(
    InsertValueInst &OrigIVI) { … }

/// Try to find redundant insertvalue instructions, like the following ones:
///  %0 = insertvalue { i8, i32 } undef, i8 %x, 0
///  %1 = insertvalue { i8, i32 } %0,    i8 %y, 0
/// Here the second instruction inserts values at the same indices, as the
/// first one, making the first one redundant.
/// It should be transformed to:
///  %0 = insertvalue { i8, i32 } undef, i8 %y, 0
Instruction *InstCombinerImpl::visitInsertValueInst(InsertValueInst &I) { … }

static bool isShuffleEquivalentToSelect(ShuffleVectorInst &Shuf) { … }

/// Turn a chain of inserts that splats a value into an insert + shuffle:
/// insertelt(insertelt(insertelt(insertelt X, %k, 0), %k, 1), %k, 2) ... ->
/// shufflevector(insertelt(X, %k, 0), poison, zero)
static Instruction *foldInsSequenceIntoSplat(InsertElementInst &InsElt) { … }

/// Try to fold an insert element into an existing splat shuffle by changing
/// the shuffle's mask to include the index of this insert element.
static Instruction *foldInsEltIntoSplat(InsertElementInst &InsElt) { … }

/// Try to fold an extract+insert element into an existing identity shuffle by
/// changing the shuffle's mask to include the index of this insert element.
static Instruction *foldInsEltIntoIdentityShuffle(InsertElementInst &InsElt) { … }

/// If we have an insertelement instruction feeding into another insertelement
/// and the 2nd is inserting a constant into the vector, canonicalize that
/// constant insertion before the insertion of a variable:
///
/// insertelement (insertelement X, Y, IdxC1), ScalarC, IdxC2 -->
/// insertelement (insertelement X, ScalarC, IdxC2), Y, IdxC1
///
/// This has the potential of eliminating the 2nd insertelement instruction
/// via constant folding of the scalar constant into a vector constant.
static Instruction *hoistInsEltConst(InsertElementInst &InsElt2,
                                     InstCombiner::BuilderTy &Builder) { … }

/// insertelt (shufflevector X, CVec, Mask|insertelt X, C1, CIndex1), C, CIndex
/// --> shufflevector X, CVec', Mask'
static Instruction *foldConstantInsEltIntoShuffle(InsertElementInst &InsElt) { … }

/// If both the base vector and the inserted element are extended from the same
/// type, do the insert element in the narrow source type followed by extend.
/// TODO: This can be extended to include other cast opcodes, but particularly
///       if we create a wider insertelement, make sure codegen is not harmed.
static Instruction *narrowInsElt(InsertElementInst &InsElt,
                                 InstCombiner::BuilderTy &Builder) { … }

/// If we are inserting 2 halves of a value into adjacent elements of a vector,
/// try to convert to a single insert with appropriate bitcasts.
static Instruction *foldTruncInsEltPair(InsertElementInst &InsElt,
                                        bool IsBigEndian,
                                        InstCombiner::BuilderTy &Builder) { … }

Instruction *InstCombinerImpl::visitInsertElementInst(InsertElementInst &IE) { … }

/// Return true if we can evaluate the specified expression tree if the vector
/// elements were shuffled in a different order.
static bool canEvaluateShuffled(Value *V, ArrayRef<int> Mask,
                                unsigned Depth = 5) { … }

/// Rebuild a new instruction just like 'I' but with the new operands given.
/// In the event of type mismatch, the type of the operands is correct.
static Value *buildNew(Instruction *I, ArrayRef<Value*> NewOps,
                       IRBuilderBase &Builder) { … }

static Value *evaluateInDifferentElementOrder(Value *V, ArrayRef<int> Mask,
                                              IRBuilderBase &Builder) { … }

// Returns true if the shuffle is extracting a contiguous range of values from
// LHS, for example:
//                 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
//   Input:        |AA|BB|CC|DD|EE|FF|GG|HH|II|JJ|KK|LL|MM|NN|OO|PP|
//   Shuffles to:  |EE|FF|GG|HH|
//                 +--+--+--+--+
static bool isShuffleExtractingFromLHS(ShuffleVectorInst &SVI,
                                       ArrayRef<int> Mask) { … }

/// These are the ingredients in an alternate form binary operator as described
/// below.
struct BinopElts { … };

/// Binops may be transformed into binops with different opcodes and operands.
/// Reverse the usual canonicalization to enable folds with the non-canonical
/// form of the binop. If a transform is possible, return the elements of the
/// new binop. If not, return invalid elements.
static BinopElts getAlternateBinop(BinaryOperator *BO, const DataLayout &DL) { … }

/// A select shuffle of a select shuffle with a shared operand can be reduced
/// to a single select shuffle. This is an obvious improvement in IR, and the
/// backend is expected to lower select shuffles efficiently.
static Instruction *foldSelectShuffleOfSelectShuffle(ShuffleVectorInst &Shuf) { … }

static Instruction *foldSelectShuffleWith1Binop(ShuffleVectorInst &Shuf,
                                                const SimplifyQuery &SQ) { … }

/// If we have an insert of a scalar to a non-zero element of an undefined
/// vector and then shuffle that value, that's the same as inserting to the zero
/// element and shuffling. Splatting from the zero element is recognized as the
/// canonical form of splat.
static Instruction *canonicalizeInsertSplat(ShuffleVectorInst &Shuf,
                                            InstCombiner::BuilderTy &Builder) { … }

/// Try to fold shuffles that are the equivalent of a vector select.
Instruction *InstCombinerImpl::foldSelectShuffle(ShuffleVectorInst &Shuf) { … }

/// Convert a narrowing shuffle of a bitcasted vector into a vector truncate.
/// Example (little endian):
/// shuf (bitcast <4 x i16> X to <8 x i8>), <0, 2, 4, 6> --> trunc X to <4 x i8>
static Instruction *foldTruncShuffle(ShuffleVectorInst &Shuf,
                                     bool IsBigEndian) { … }

/// Match a shuffle-select-shuffle pattern where the shuffles are widening and
/// narrowing (concatenating with poison and extracting back to the original
/// length). This allows replacing the wide select with a narrow select.
static Instruction *narrowVectorSelect(ShuffleVectorInst &Shuf,
                                       InstCombiner::BuilderTy &Builder) { … }

/// Canonicalize FP negate/abs after shuffle.
static Instruction *foldShuffleOfUnaryOps(ShuffleVectorInst &Shuf,
                                          InstCombiner::BuilderTy &Builder) { … }

/// Canonicalize casts after shuffle.
static Instruction *foldCastShuffle(ShuffleVectorInst &Shuf,
                                    InstCombiner::BuilderTy &Builder) { … }

/// Try to fold an extract subvector operation.
static Instruction *foldIdentityExtractShuffle(ShuffleVectorInst &Shuf) { … }

/// Try to replace a shuffle with an insertelement or try to replace a shuffle
/// operand with the operand of an insertelement.
static Instruction *foldShuffleWithInsert(ShuffleVectorInst &Shuf,
                                          InstCombinerImpl &IC) { … }

static Instruction *foldIdentityPaddedShuffles(ShuffleVectorInst &Shuf) { … }

// Splatting the first element of the result of a BinOp, where any of the
// BinOp's operands are the result of a first element splat can be simplified to
// splatting the first element of the result of the BinOp
Instruction *InstCombinerImpl::simplifyBinOpSplats(ShuffleVectorInst &SVI) { … }

Instruction *InstCombinerImpl::visitShuffleVectorInst(ShuffleVectorInst &SVI) { … }
llvm/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp
