Scalarizer.cpp | Explore in Territory

//===- Scalarizer.cpp - Scalarize vector operations -----------------------===//
//
// 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 pass converts vector operations into scalar operations (or, optionally,
// operations on smaller vector widths), in order to expose optimization
// opportunities on the individual scalar operations.
// It is mainly intended for targets that do not have vector units, but it
// may also be useful for revectorizing code to different vector widths.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Scalar/Scalarizer.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Twine.h"
#include "llvm/Analysis/VectorUtils.h"
#include "llvm/IR/Argument.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/InstVisitor.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Value.h"
#include "llvm/InitializePasses.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Transforms/Utils/Local.h"
#include <cassert>
#include <cstdint>
#include <iterator>
#include <map>
#include <utility>

usingnamespacellvm;

#define DEBUG_TYPE …

static cl::opt<bool> ClScalarizeVariableInsertExtract(
    "scalarize-variable-insert-extract", cl::init(true), cl::Hidden,
    cl::desc("Allow the scalarizer pass to scalarize "
             "insertelement/extractelement with variable index"));

// This is disabled by default because having separate loads and stores
// makes it more likely that the -combiner-alias-analysis limits will be
// reached.
static cl::opt<bool> ClScalarizeLoadStore(
    "scalarize-load-store", cl::init(false), cl::Hidden,
    cl::desc("Allow the scalarizer pass to scalarize loads and store"));

// Split vectors larger than this size into fragments, where each fragment is
// either a vector no larger than this size or a scalar.
//
// Instructions with operands or results of different sizes that would be split
// into a different number of fragments are currently left as-is.
static cl::opt<unsigned> ClScalarizeMinBits(
    "scalarize-min-bits", cl::init(0), cl::Hidden,
    cl::desc("Instruct the scalarizer pass to attempt to keep values of a "
             "minimum number of bits"));

namespace {

BasicBlock::iterator skipPastPhiNodesAndDbg(BasicBlock::iterator Itr) { … }

// Used to store the scattered form of a vector.
ValueVector;

// Used to map a vector Value and associated type to its scattered form.
// The associated type is only non-null for pointer values that are "scattered"
// when used as pointer operands to load or store.
//
// We use std::map because we want iterators to persist across insertion and
// because the values are relatively large.
ScatterMap;

// Lists Instructions that have been replaced with scalar implementations,
// along with a pointer to their scattered forms.
GatherList;

struct VectorSplit { … };

// Provides a very limited vector-like interface for lazily accessing one
// component of a scattered vector or vector pointer.
class Scatterer { … };

// FCmpSplitter(FCI)(Builder, X, Y, Name) uses Builder to create an FCmp
// called Name that compares X and Y in the same way as FCI.
struct FCmpSplitter { … };

// ICmpSplitter(ICI)(Builder, X, Y, Name) uses Builder to create an ICmp
// called Name that compares X and Y in the same way as ICI.
struct ICmpSplitter { … };

// UnarySplitter(UO)(Builder, X, Name) uses Builder to create
// a unary operator like UO called Name with operand X.
struct UnarySplitter { … };

// BinarySplitter(BO)(Builder, X, Y, Name) uses Builder to create
// a binary operator like BO called Name with operands X and Y.
struct BinarySplitter { … };

// Information about a load or store that we're scalarizing.
struct VectorLayout { … };

/// Concatenate the given fragments to a single vector value of the type
/// described in @p VS.
static Value *concatenate(IRBuilder<> &Builder, ArrayRef<Value *> Fragments,
                          const VectorSplit &VS, Twine Name) { … }

template <typename T>
T getWithDefaultOverride(const cl::opt<T> &ClOption,
                         const std::optional<T> &DefaultOverride) { … }

class ScalarizerVisitor : public InstVisitor<ScalarizerVisitor, bool> { … };

class ScalarizerLegacyPass : public FunctionPass { … };

} // end anonymous namespace

ScalarizerLegacyPass::ScalarizerLegacyPass(const ScalarizerPassOptions &Options)
    : … { … }

void ScalarizerLegacyPass::getAnalysisUsage(AnalysisUsage &AU) const { … }

char ScalarizerLegacyPass::ID = …;
INITIALIZE_PASS_BEGIN(ScalarizerLegacyPass, "scalarizer",
                      "Scalarize vector operations", false, false)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_END(ScalarizerLegacyPass, "scalarizer",
                    "Scalarize vector operations", false, false)

Scatterer::Scatterer(BasicBlock *bb, BasicBlock::iterator bbi, Value *v,
                     const VectorSplit &VS, ValueVector *cachePtr)
    : … { … }

// Return fragment Frag, creating a new Value for it if necessary.
Value *Scatterer::operator[](unsigned Frag) { … }

bool ScalarizerLegacyPass::runOnFunction(Function &F) { … }

FunctionPass *llvm::createScalarizerPass(const ScalarizerPassOptions &Options) { … }

bool ScalarizerVisitor::visit(Function &F) { … }

// Return a scattered form of V that can be accessed by Point.  V must be a
// vector or a pointer to a vector.
Scatterer ScalarizerVisitor::scatter(Instruction *Point, Value *V,
                                     const VectorSplit &VS) { … }

// Replace Op with the gathered form of the components in CV.  Defer the
// deletion of Op and creation of the gathered form to the end of the pass,
// so that we can avoid creating the gathered form if all uses of Op are
// replaced with uses of CV.
void ScalarizerVisitor::gather(Instruction *Op, const ValueVector &CV,
                               const VectorSplit &VS) { … }

// Replace Op with CV and collect Op has a potentially dead instruction.
void ScalarizerVisitor::replaceUses(Instruction *Op, Value *CV) { … }

// Return true if it is safe to transfer the given metadata tag from
// vector to scalar instructions.
bool ScalarizerVisitor::canTransferMetadata(unsigned Tag) { … }

// Transfer metadata from Op to the instructions in CV if it is known
// to be safe to do so.
void ScalarizerVisitor::transferMetadataAndIRFlags(Instruction *Op,
                                                   const ValueVector &CV) { … }

// Determine how Ty is split, if at all.
std::optional<VectorSplit> ScalarizerVisitor::getVectorSplit(Type *Ty) { … }

// Try to fill in Layout from Ty, returning true on success.  Alignment is
// the alignment of the vector, or std::nullopt if the ABI default should be
// used.
std::optional<VectorLayout>
ScalarizerVisitor::getVectorLayout(Type *Ty, Align Alignment,
                                   const DataLayout &DL) { … }

// Scalarize one-operand instruction I, using Split(Builder, X, Name)
// to create an instruction like I with operand X and name Name.
template<typename Splitter>
bool ScalarizerVisitor::splitUnary(Instruction &I, const Splitter &Split) { … }

// Scalarize two-operand instruction I, using Split(Builder, X, Y, Name)
// to create an instruction like I with operands X and Y and name Name.
template<typename Splitter>
bool ScalarizerVisitor::splitBinary(Instruction &I, const Splitter &Split) { … }

static bool isTriviallyScalariable(Intrinsic::ID ID) { … }

/// If a call to a vector typed intrinsic function, split into a scalar call per
/// element if possible for the intrinsic.
bool ScalarizerVisitor::splitCall(CallInst &CI) { … }

bool ScalarizerVisitor::visitSelectInst(SelectInst &SI) { … }

bool ScalarizerVisitor::visitICmpInst(ICmpInst &ICI) { … }

bool ScalarizerVisitor::visitFCmpInst(FCmpInst &FCI) { … }

bool ScalarizerVisitor::visitUnaryOperator(UnaryOperator &UO) { … }

bool ScalarizerVisitor::visitBinaryOperator(BinaryOperator &BO) { … }

bool ScalarizerVisitor::visitGetElementPtrInst(GetElementPtrInst &GEPI) { … }

bool ScalarizerVisitor::visitCastInst(CastInst &CI) { … }

bool ScalarizerVisitor::visitBitCastInst(BitCastInst &BCI) { … }

bool ScalarizerVisitor::visitInsertElementInst(InsertElementInst &IEI) { … }

bool ScalarizerVisitor::visitExtractElementInst(ExtractElementInst &EEI) { … }

bool ScalarizerVisitor::visitShuffleVectorInst(ShuffleVectorInst &SVI) { … }

bool ScalarizerVisitor::visitPHINode(PHINode &PHI) { … }

bool ScalarizerVisitor::visitLoadInst(LoadInst &LI) { … }

bool ScalarizerVisitor::visitStoreInst(StoreInst &SI) { … }

bool ScalarizerVisitor::visitCallInst(CallInst &CI) { … }

bool ScalarizerVisitor::visitFreezeInst(FreezeInst &FI) { … }

// Delete the instructions that we scalarized.  If a full vector result
// is still needed, recreate it using InsertElements.
bool ScalarizerVisitor::finish() { … }

PreservedAnalyses ScalarizerPass::run(Function &F, FunctionAnalysisManager &AM) { … }
llvm/llvm/lib/Transforms/Scalar/Scalarizer.cpp
