LLVM  6.0.0svn
Classes | Namespaces | Macros | Functions | Variables
SROA.cpp File Reference

This transformation implements the well known scalar replacement of aggregates transformation. More...

#include "llvm/Transforms/Scalar/SROA.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/PointerIntPair.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/Twine.h"
#include "llvm/ADT/iterator.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/PtrUseVisitor.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/ConstantFolder.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DIBuilder.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/GetElementPtrTypeIterator.h"
#include "llvm/IR/GlobalAlias.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/IntrinsicInst.h"
#include "llvm/IR/Intrinsics.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Use.h"
#include "llvm/IR/User.h"
#include "llvm/IR/Value.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/PromoteMemToReg.h"
#include <algorithm>
#include <cassert>
#include <chrono>
#include <cstddef>
#include <cstdint>
#include <cstring>
#include <iterator>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
#include <random>

Go to the source code of this file.

Classes

struct  llvm::isPodLike< T >
 isPodLike - This is a type trait that is used to determine whether a given type can be copied around with memcpy instead of running ctors etc. More...
 
struct  llvm::isPodLike< Slice >
 
class  llvm::sroa::AllocaSlices
 Representation of the alloca slices. More...
 
class  llvm::sroa::Partition
 A partition of the slices. More...
 
class  AllocaSlices::partition_iterator
 An iterator over partitions of the alloca's slices. More...
 
class  AllocaSlices::SliceBuilder
 Builder for the alloca slices. More...
 
class  llvm::sroa::AllocaSliceRewriter
 Visitor to rewrite instructions using p particular slice of an alloca to use a new alloca. More...
 
class  llvm::sroa::SROALegacyPass
 A legacy pass for the legacy pass manager that wraps the SROA pass. More...
 

Namespaces

 llvm
 Compute iterated dominance frontiers using a linear time algorithm.
 

Macros

#define DEBUG_TYPE   "sroa"
 

Functions

 STATISTIC (NumAllocasAnalyzed, "Number of allocas analyzed for replacement")
 
 STATISTIC (NumAllocaPartitions, "Number of alloca partitions formed")
 
 STATISTIC (MaxPartitionsPerAlloca, "Maximum number of partitions per alloca")
 
 STATISTIC (NumAllocaPartitionUses, "Number of alloca partition uses rewritten")
 
 STATISTIC (MaxUsesPerAllocaPartition, "Maximum number of uses of a partition")
 
 STATISTIC (NumNewAllocas, "Number of new, smaller allocas introduced")
 
 STATISTIC (NumPromoted, "Number of allocas promoted to SSA values")
 
 STATISTIC (NumLoadsSpeculated, "Number of loads speculated to allow promotion")
 
 STATISTIC (NumDeleted, "Number of instructions deleted")
 
 STATISTIC (NumVectorized, "Number of vectorized aggregates")
 
static ValuefoldSelectInst (SelectInst &SI)
 
static ValuefoldPHINodeOrSelectInst (Instruction &I)
 A helper that folds a PHI node or a select. More...
 
static TypefindCommonType (AllocaSlices::const_iterator B, AllocaSlices::const_iterator E, uint64_t EndOffset)
 Walk the range of a partitioning looking for a common type to cover this sequence of slices. More...
 
static bool isSafePHIToSpeculate (PHINode &PN)
 PHI instructions that use an alloca and are subsequently loaded can be rewritten to load both input pointers in the pred blocks and then PHI the results, allowing the load of the alloca to be promoted. More...
 
static void speculatePHINodeLoads (PHINode &PN)
 
static bool isSafeSelectToSpeculate (SelectInst &SI)
 Select instructions that use an alloca and are subsequently loaded can be rewritten to load both input pointers and then select between the result, allowing the load of the alloca to be promoted. More...
 
static void speculateSelectInstLoads (SelectInst &SI)
 
static ValuebuildGEP (IRBuilderTy &IRB, Value *BasePtr, SmallVectorImpl< Value *> &Indices, Twine NamePrefix)
 Build a GEP out of a base pointer and indices. More...
 
static ValuegetNaturalGEPWithType (IRBuilderTy &IRB, const DataLayout &DL, Value *BasePtr, Type *Ty, Type *TargetTy, SmallVectorImpl< Value *> &Indices, Twine NamePrefix)
 Get a natural GEP off of the BasePtr walking through Ty toward TargetTy without changing the offset of the pointer. More...
 
static ValuegetNaturalGEPRecursively (IRBuilderTy &IRB, const DataLayout &DL, Value *Ptr, Type *Ty, APInt &Offset, Type *TargetTy, SmallVectorImpl< Value *> &Indices, Twine NamePrefix)
 Recursively compute indices for a natural GEP. More...
 
static ValuegetNaturalGEPWithOffset (IRBuilderTy &IRB, const DataLayout &DL, Value *Ptr, APInt Offset, Type *TargetTy, SmallVectorImpl< Value *> &Indices, Twine NamePrefix)
 Get a natural GEP from a base pointer to a particular offset and resulting in a particular type. More...
 
static ValuegetAdjustedPtr (IRBuilderTy &IRB, const DataLayout &DL, Value *Ptr, APInt Offset, Type *PointerTy, Twine NamePrefix)
 Compute an adjusted pointer from Ptr by Offset bytes where the resulting pointer has PointerTy. More...
 
static unsigned getAdjustedAlignment (Instruction *I, uint64_t Offset, const DataLayout &DL)
 Compute the adjusted alignment for a load or store from an offset. More...
 
static bool canConvertValue (const DataLayout &DL, Type *OldTy, Type *NewTy)
 Test whether we can convert a value from the old to the new type. More...
 
static ValueconvertValue (const DataLayout &DL, IRBuilderTy &IRB, Value *V, Type *NewTy)
 Generic routine to convert an SSA value to a value of a different type. More...
 
static bool isVectorPromotionViableForSlice (Partition &P, const Slice &S, VectorType *Ty, uint64_t ElementSize, const DataLayout &DL)
 Test whether the given slice use can be promoted to a vector. More...
 
static VectorTypeisVectorPromotionViable (Partition &P, const DataLayout &DL)
 Test whether the given alloca partitioning and range of slices can be promoted to a vector. More...
 
static bool isIntegerWideningViableForSlice (const Slice &S, uint64_t AllocBeginOffset, Type *AllocaTy, const DataLayout &DL, bool &WholeAllocaOp)
 Test whether a slice of an alloca is valid for integer widening. More...
 
static bool isIntegerWideningViable (Partition &P, Type *AllocaTy, const DataLayout &DL)
 Test whether the given alloca partition's integer operations can be widened to promotable ones. More...
 
static ValueextractInteger (const DataLayout &DL, IRBuilderTy &IRB, Value *V, IntegerType *Ty, uint64_t Offset, const Twine &Name)
 
static ValueinsertInteger (const DataLayout &DL, IRBuilderTy &IRB, Value *Old, Value *V, uint64_t Offset, const Twine &Name)
 
static ValueextractVector (IRBuilderTy &IRB, Value *V, unsigned BeginIndex, unsigned EndIndex, const Twine &Name)
 
static ValueinsertVector (IRBuilderTy &IRB, Value *Old, Value *V, unsigned BeginIndex, const Twine &Name)
 
static TypestripAggregateTypeWrapping (const DataLayout &DL, Type *Ty)
 Strip aggregate type wrapping. More...
 
static TypegetTypePartition (const DataLayout &DL, Type *Ty, uint64_t Offset, uint64_t Size)
 Try to find a partition of the aggregate type passed in for a given offset and size. More...
 
 INITIALIZE_PASS_BEGIN (SROALegacyPass, "sroa", "Scalar Replacement Of Aggregates", false, false) INITIALIZE_PASS_END(SROALegacyPass
 

Variables

static cl::opt< boolSROARandomShuffleSlices ("sroa-random-shuffle-slices", cl::init(false), cl::Hidden)
 Hidden option to enable randomly shuffling the slices to help uncover instability in their order. More...
 
static cl::opt< boolSROAStrictInbounds ("sroa-strict-inbounds", cl::init(false), cl::Hidden)
 Hidden option to experiment with completely strict handling of inbounds GEPs. More...
 
 sroa
 
Scalar Replacement Of Aggregates
 
Scalar Replacement Of false
 

Detailed Description

This transformation implements the well known scalar replacement of aggregates transformation.

It tries to identify promotable elements of an aggregate alloca, and promote them to registers. It will also try to convert uses of an element (or set of elements) of an alloca into a vector or bitfield-style integer scalar if appropriate.

It works to do this with minimal slicing of the alloca so that regions which are merely transferred in and out of external memory remain unchanged and are not decomposed to scalar code.

Because this also performs alloca promotion, it can be thought of as also serving the purpose of SSA formation. The algorithm iterates on the function until all opportunities for promotion have been realized.

Definition in file SROA.cpp.

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "sroa"

Definition at line 103 of file SROA.cpp.

Function Documentation

◆ buildGEP()

static Value* buildGEP ( IRBuilderTy &  IRB,
Value BasePtr,
SmallVectorImpl< Value *> &  Indices,
Twine  NamePrefix 
)
static

Build a GEP out of a base pointer and indices.

This will return the BasePtr if that is valid, or build a new GEP instruction using the IRBuilder if GEP-ing is needed.

Definition at line 1357 of file SROA.cpp.

References llvm::SmallVectorTemplateCommon< T, typename >::back(), llvm::SmallVectorBase::empty(), isZero(), and llvm::SmallVectorTemplateCommon< T, typename >::size().

Referenced by llvm::fuzzerop::gepDescriptor(), and getNaturalGEPWithType().

◆ canConvertValue()

static bool canConvertValue ( const DataLayout DL,
Type OldTy,
Type NewTy 
)
static

Test whether we can convert a value from the old to the new type.

This predicate should be used to guard calls to convertValue in order to ensure that we only try to convert viable values. The strategy is that we will peel off single element struct and array wrappings to get to an underlying value, and convert that value.

Definition at line 1659 of file SROA.cpp.

References assert(), getBitWidth(), llvm::Type::getScalarType(), llvm::DataLayout::getTypeSizeInBits(), llvm::Type::isIntegerTy(), llvm::DataLayout::isNonIntegralPointerType(), llvm::Type::isPointerTy(), and llvm::Type::isSingleValueType().

Referenced by convertValue(), isIntegerWideningViable(), isIntegerWideningViableForSlice(), isVectorPromotionViableForSlice(), and llvm::sroa::AllocaSliceRewriter::visit().

◆ convertValue()

static Value* convertValue ( const DataLayout DL,
IRBuilderTy &  IRB,
Value V,
Type NewTy 
)
static

Generic routine to convert an SSA value to a value of a different type.

This will try various different casting techniques, such as bitcasts, inttoptr, and ptrtoint casts. Use the canConvertValue predicate to test two types for viability with this routine.

Definition at line 1710 of file SROA.cpp.

References assert(), canConvertValue(), llvm::DataLayout::getIntPtrType(), llvm::Value::getType(), llvm::Type::isIntOrIntVectorTy(), llvm::Type::isPtrOrPtrVectorTy(), and llvm::Type::isVectorTy().

Referenced by llvm::sroa::AllocaSliceRewriter::visit().

◆ extractInteger()

static Value* extractInteger ( const DataLayout DL,
IRBuilderTy &  IRB,
Value V,
IntegerType Ty,
uint64_t  Offset,
const Twine Name 
)
static

◆ extractVector()

static Value* extractVector ( IRBuilderTy &  IRB,
Value V,
unsigned  BeginIndex,
unsigned  EndIndex,
const Twine Name 
)
static

◆ findCommonType()

static Type* findCommonType ( AllocaSlices::const_iterator  B,
AllocaSlices::const_iterator  E,
uint64_t  EndOffset 
)
static

Walk the range of a partitioning looking for a common type to cover this sequence of slices.

Definition at line 1105 of file SROA.cpp.

References E, llvm::IntegerType::getBitWidth(), and I.

Referenced by getTypePartition().

◆ foldPHINodeOrSelectInst()

static Value* foldPHINodeOrSelectInst ( Instruction I)
static

A helper that folds a PHI node or a select.

Definition at line 641 of file SROA.cpp.

References foldSelectInst().

Referenced by AllocaSlices::SliceBuilder::SliceBuilder().

◆ foldSelectInst()

static Value* foldSelectInst ( SelectInst SI)
static

Definition at line 628 of file SROA.cpp.

References llvm::SelectInst::getCondition(), and llvm::User::getOperand().

Referenced by foldPHINodeOrSelectInst().

◆ getAdjustedAlignment()

static unsigned getAdjustedAlignment ( Instruction I,
uint64_t  Offset,
const DataLayout DL 
)
static

Compute the adjusted alignment for a load or store from an offset.

Definition at line 1633 of file SROA.cpp.

References llvm::DataLayout::getABITypeAlignment(), llvm_unreachable, and llvm::MinAlign().

Referenced by getTypePartition().

◆ getAdjustedPtr()

static Value* getAdjustedPtr ( IRBuilderTy &  IRB,
const DataLayout DL,
Value Ptr,
APInt  Offset,
Type PointerTy,
Twine  NamePrefix 
)
static

Compute an adjusted pointer from Ptr by Offset bytes where the resulting pointer has PointerTy.

This tries very hard to compute a "natural" GEP which arrives at the offset and produces the pointer type desired. Where it cannot, it will try to use the natural GEP to arrive at the offset and bitcast to the type. Where that fails, it will try to use an existing i8* and GEP to the byte offset and bitcast to the type.

The strategy for finding the more natural GEPs is to peel off layers of the pointer, walking back through bit casts and GEPs, searching for a base pointer from which we can compute a natural GEP with the desired properties. The algorithm tries to fold as many constant indices into a single GEP as possible, thus making each GEP more independent of the surrounding code.

Definition at line 1538 of file SROA.cpp.

References assert(), llvm::SmallVectorImpl< T >::clear(), GEP, llvm::APInt::getBitWidth(), getNaturalGEPWithOffset(), llvm::Operator::getOpcode(), llvm::Type::getPointerAddressSpace(), llvm::Type::getPointerElementType(), llvm::Value::getType(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::Type::isIntegerTy(), llvm::Type::isPointerTy(), and P.

Referenced by getTypePartition(), and llvm::sroa::AllocaSliceRewriter::visit().

◆ getNaturalGEPRecursively()

static Value* getNaturalGEPRecursively ( IRBuilderTy &  IRB,
const DataLayout DL,
Value Ptr,
Type Ty,
APInt Offset,
Type TargetTy,
SmallVectorImpl< Value *> &  Indices,
Twine  NamePrefix 
)
static

◆ getNaturalGEPWithOffset()

static Value* getNaturalGEPWithOffset ( IRBuilderTy &  IRB,
const DataLayout DL,
Value Ptr,
APInt  Offset,
Type TargetTy,
SmallVectorImpl< Value *> &  Indices,
Twine  NamePrefix 
)
static

Get a natural GEP from a base pointer to a particular offset and resulting in a particular type.

The goal is to produce a "natural" looking GEP that works with the existing composite types to arrive at the appropriate offset and element type for a pointer. TargetTy is the element type the returned GEP should point-to if possible. We recurse by decreasing Offset, adding the appropriate index to Indices, and setting Ty to the result subtype.

If no natural GEP can be constructed, this function returns null.

Definition at line 1498 of file SROA.cpp.

References llvm::PointerType::getAddressSpace(), llvm::APInt::getBitWidth(), llvm::PointerType::getElementType(), llvm::Type::getInt8PtrTy(), getNaturalGEPRecursively(), llvm::Value::getType(), llvm::DataLayout::getTypeAllocSize(), llvm::Type::isIntegerTy(), llvm::Type::isSized(), llvm::SmallVectorTemplateBase< T, isPodLike >::push_back(), and llvm::APInt::sdiv().

Referenced by getAdjustedPtr().

◆ getNaturalGEPWithType()

static Value* getNaturalGEPWithType ( IRBuilderTy &  IRB,
const DataLayout DL,
Value BasePtr,
Type Ty,
Type TargetTy,
SmallVectorImpl< Value *> &  Indices,
Twine  NamePrefix 
)
static

Get a natural GEP off of the BasePtr walking through Ty toward TargetTy without changing the offset of the pointer.

This routine assumes we've already established a properly offset GEP with Indices, and arrived at the Ty type. The goal is to continue to GEP with zero-indices down through type layers until we find one the same as TargetTy. If we can't find one with the same type, we at least try to use one with the same size. If none of that works, we just produce the GEP as indicated by Indices to have the correct offset.

Definition at line 1380 of file SROA.cpp.

References buildGEP(), llvm::SmallVectorTemplateCommon< T, typename >::end(), llvm::SmallVectorImpl< T >::erase(), llvm::DataLayout::getPointerTypeSizeInBits(), llvm::Value::getType(), llvm::Type::isPointerTy(), and llvm::SmallVectorTemplateBase< T, isPodLike >::push_back().

Referenced by getNaturalGEPRecursively().

◆ getTypePartition()

static Type* getTypePartition ( const DataLayout DL,
Type Ty,
uint64_t  Offset,
uint64_t  Size 
)
static

Try to find a partition of the aggregate type passed in for a given offset and size.

This recurses through the aggregate type and tries to compute a subtype based on the offset and size. When the offset and size span a sub-section of an array, it will even compute a new array type for that sub-section, and the same for structs.

Note that this routine is very strict and tries to find a partition of the type which produces the exact right offset and size. It is not forgiving when the size or offset cause either end of type-based partition to be off. Also, this is a best-effort routine. It is reasonable to give up and not return a type if necessary.

Definition at line 3296 of file SROA.cpp.

References llvm::PreservedAnalyses::all(), AS, assert(), llvm::SmallVectorTemplateCommon< T >::back(), llvm::BasicBlock::begin(), llvm::sroa::AllocaSlices::begin(), llvm::sroa::Partition::begin(), llvm::sroa::Partition::beginOffset(), C, llvm::SmallPtrSetImplBase::clear(), llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::clear(), llvm::Instruction::copyMetadata(), llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::count(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::DIExpression::createFragmentExpression(), llvm::dbgs(), DEBUG, llvm::dyn_cast(), E, llvm::StructType::element_begin(), llvm::StructType::element_end(), llvm::SmallVectorBase::empty(), llvm::SmallPtrSetImplBase::empty(), llvm::TinyPtrVector< EltTy >::empty(), llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::SmallVectorTemplateCommon< T >::end(), llvm::BasicBlock::end(), llvm::sroa::AllocaSlices::end(), llvm::sroa::Partition::end(), llvm::sroa::Partition::endOffset(), llvm::sroa::AllocaSlices::erase(), llvm::SmallVectorImpl< T >::erase(), llvm::Instruction::eraseFromParent(), F(), llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::find(), findCommonType(), llvm::FindDbgAddrUses(), llvm::TinyPtrVector< EltTy >::front(), llvm::StructType::get(), llvm::ArrayType::get(), llvm::UndefValue::get(), llvm::DataLayout::getABITypeAlignment(), llvm::PointerType::getAddressSpace(), getAdjustedAlignment(), getAdjustedPtr(), llvm::AllocaInst::getAlignment(), llvm::AllocaInst::getAllocatedType(), llvm::Type::getArrayElementType(), llvm::IntegerType::getBitWidth(), llvm::Type::getContext(), llvm::Function::getContext(), llvm::Module::getDataLayout(), llvm::sroa::AllocaSlices::getDeadOperands(), llvm::sroa::AllocaSlices::getDeadUsers(), llvm::Instruction::getDebugLoc(), llvm::StructLayout::getElementContainingOffset(), llvm::StructLayout::getElementOffset(), llvm::StructType::getElementType(), llvm::Function::getEntryBlock(), llvm::DbgInfoIntrinsic::getExpression(), llvm::Type::getInt8Ty(), llvm::Type::getIntNTy(), llvm::Instruction::getModule(), llvm::Value::getName(), llvm::User::getOperandUse(), llvm::LoadInst::getPointerAddressSpace(), llvm::StoreInst::getPointerAddressSpace(), llvm::LoadInst::getPointerOperand(), llvm::StoreInst::getPointerOperand(), llvm::LoadInst::getPointerOperandIndex(), llvm::StoreInst::getPointerOperandIndex(), llvm::DataLayout::getPointerSizeInBits(), llvm::Type::getPointerTo(), llvm::StructLayout::getSizeInBytes(), llvm::DataLayout::getStructLayout(), llvm::AllocaInst::getType(), llvm::Value::getType(), llvm::DataLayout::getTypeAllocSize(), llvm::DataLayout::getTypeSizeInBits(), llvm::StoreInst::getValueOperand(), llvm::DbgInfoIntrinsic::getVariable(), llvm::Value::hasOneUse(), I, llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, InlineBuckets, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::sroa::AllocaSlices::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::AllocaInst::isArrayAllocation(), llvm::Type::isArrayTy(), llvm::sroa::AllocaSlices::isEscaped(), llvm::isInstructionTriviallyDead(), llvm::Type::isIntegerTy(), isIntegerWideningViable(), llvm::DataLayout::isLegalInteger(), llvm::StructType::isPacked(), isSafePHIToSpeculate(), isSafeSelectToSpeculate(), llvm::Type::isSized(), isVectorPromotionViable(), llvm::makeArrayRef(), llvm::LLVMContext::MD_mem_parallel_loop_access, llvm::MinAlign(), llvm::RISCVFenceField::O, llvm::User::operands(), llvm::sroa::AllocaSlices::partitions(), llvm::PreservedAnalyses::preserve(), llvm::PreservedAnalyses::preserveSet(), llvm::sroa::AllocaSlices::print(), llvm::PromoteMemToReg(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::remove_if(), llvm::Value::replaceAllUsesWith(), Rewriter, SI, llvm::AMDGPU::HSAMD::Kernel::Arg::Key::Size, llvm::sroa::Partition::size(), llvm::parallel::sort(), speculatePHINodeLoads(), speculateSelectInstLoads(), llvm::sroa::Partition::splitSliceTails(), stripAggregateTypeWrapping(), llvm::Value::stripInBoundsOffsets(), llvm::Value::use_empty(), llvm::Value::user_begin(), and llvm::Value::users().

◆ INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN ( SROALegacyPass  ,
"sroa"  ,
"Scalar Replacement Of Aggregates ,
false  ,
false   
)

Referenced by llvm::createSROAPass().

◆ insertInteger()

static Value* insertInteger ( const DataLayout DL,
IRBuilderTy &  IRB,
Value Old,
Value V,
uint64_t  Offset,
const Twine Name 
)
static

◆ insertVector()

static Value* insertVector ( IRBuilderTy &  IRB,
Value Old,
Value V,
unsigned  BeginIndex,
const Twine Name 
)
static

◆ isIntegerWideningViable()

static bool isIntegerWideningViable ( Partition P,
Type AllocaTy,
const DataLayout DL 
)
static

Test whether the given alloca partition's integer operations can be widened to promotable ones.

This is a quick test to check whether we can rewrite the integer loads and stores to a particular alloca into wider loads and stores and be able to promote the resulting alloca.

Definition at line 2024 of file SROA.cpp.

References llvm::sroa::Partition::begin(), canConvertValue(), llvm::sroa::Partition::end(), false, llvm::Type::getContext(), llvm::Type::getIntNTy(), llvm::DataLayout::getTypeSizeInBits(), llvm::DataLayout::getTypeStoreSizeInBits(), isIntegerWideningViableForSlice(), llvm::DataLayout::isLegalInteger(), and llvm::IntegerType::MAX_INT_BITS.

Referenced by getTypePartition().

◆ isIntegerWideningViableForSlice()

static bool isIntegerWideningViableForSlice ( const Slice &  S,
uint64_t  AllocBeginOffset,
Type AllocaTy,
const DataLayout DL,
bool WholeAllocaOp 
)
static

Test whether a slice of an alloca is valid for integer widening.

This implements the necessary checking for the isIntegerWideningViable test below on a single slice of the alloca.

Definition at line 1944 of file SROA.cpp.

References canConvertValue(), llvm::DataLayout::getTypeStoreSize(), llvm::DataLayout::getTypeStoreSizeInBits(), MI, and llvm::AMDGPU::HSAMD::Kernel::Arg::Key::Size.

Referenced by isIntegerWideningViable().

◆ isSafePHIToSpeculate()

static bool isSafePHIToSpeculate ( PHINode PN)
static

PHI instructions that use an alloca and are subsequently loaded can be rewritten to load both input pointers in the pred blocks and then PHI the results, allowing the load of the alloca to be promoted.

From this: P2 = phi [i32* Alloca, i32* Other] V = load i32* P2 to: V1 = load i32* Alloca -> will be mem2reg'd ... V2 = load i32* Other ... V = phi [i32 V1, i32 V2]

We can do this to a select if its only uses are loads and if the operands to the select can be loaded unconditionally.

FIXME: This should be hoisted into a generic utility, likely in Transforms/Util/Local.h

Definition at line 1172 of file SROA.cpp.

References llvm::dyn_cast(), llvm::LoadInst::getAlignment(), llvm::Module::getDataLayout(), llvm::PHINode::getIncomingBlock(), llvm::PHINode::getIncomingValue(), llvm::Instruction::getModule(), llvm::PHINode::getNumIncomingValues(), llvm::TerminatorInst::getNumSuccessors(), llvm::Instruction::getParent(), llvm::BasicBlock::getTerminator(), llvm::isSafeToLoadUnconditionally(), llvm::LoadInst::isSimple(), llvm::max(), llvm::Instruction::mayHaveSideEffects(), and llvm::Value::users().

Referenced by getTypePartition().

◆ isSafeSelectToSpeculate()

static bool isSafeSelectToSpeculate ( SelectInst SI)
static

Select instructions that use an alloca and are subsequently loaded can be rewritten to load both input pointers and then select between the result, allowing the load of the alloca to be promoted.

From this: P2 = select i1 cond, i32* Alloca, i32* Other V = load i32* P2 to: V1 = load i32* Alloca -> will be mem2reg'd V2 = load i32* Other V = select i1 cond, i32 V1, i32 V2

We can do this to a select if its only uses are loads and if the operand to the select can be loaded unconditionally.

Definition at line 1292 of file SROA.cpp.

References llvm::dyn_cast(), llvm::LoadInst::getAlignment(), llvm::Module::getDataLayout(), llvm::SelectInst::getFalseValue(), llvm::Instruction::getModule(), llvm::SelectInst::getTrueValue(), llvm::isSafeToLoadUnconditionally(), llvm::LoadInst::isSimple(), and llvm::Value::users().

Referenced by getTypePartition().

◆ isVectorPromotionViable()

static VectorType* isVectorPromotionViable ( Partition P,
const DataLayout DL 
)
static

Test whether the given alloca partitioning and range of slices can be promoted to a vector.

This is a quick test to check whether we can rewrite a particular alloca partition (and its newly formed alloca) into a vector alloca with only whole-vector loads and stores such that it could be promoted to a vector SSA value. We only can ensure this for a limited set of operations, and we don't want to do the rewrites unless we are confident that the result will be promotable, so we have an early test here.

Definition at line 1836 of file SROA.cpp.

References assert(), llvm::SmallVectorTemplateCommon< T >::begin(), llvm::SmallVectorBase::empty(), llvm::SmallVectorTemplateCommon< T >::end(), llvm::SmallVectorImpl< T >::erase(), llvm::SequentialType::getElementType(), llvm::SequentialType::getNumElements(), llvm::DataLayout::getTypeSizeInBits(), llvm::Type::isIntegerTy(), isVectorPromotionViableForSlice(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::remove_if(), and llvm::parallel::sort().

Referenced by getTypePartition().

◆ isVectorPromotionViableForSlice()

static bool isVectorPromotionViableForSlice ( Partition P,
const Slice &  S,
VectorType Ty,
uint64_t  ElementSize,
const DataLayout DL 
)
static

Test whether the given slice use can be promoted to a vector.

This function is called to test each entry in a partition which is slated for a single slice.

Definition at line 1760 of file SROA.cpp.

References assert(), llvm::sroa::Partition::beginOffset(), canConvertValue(), llvm::sroa::Partition::endOffset(), llvm::VectorType::get(), llvm::Type::getContext(), llvm::SequentialType::getElementType(), llvm::Type::getIntNTy(), llvm::SequentialType::getNumElements(), llvm::Type::isIntegerTy(), llvm::max(), and MI.

Referenced by isVectorPromotionViable().

◆ speculatePHINodeLoads()

static void speculatePHINodeLoads ( PHINode PN)
static

◆ speculateSelectInstLoads()

static void speculateSelectInstLoads ( SelectInst SI)
static

◆ STATISTIC() [1/10]

STATISTIC ( NumAllocasAnalyzed  ,
"Number of allocas analyzed for replacement  
)

◆ STATISTIC() [2/10]

STATISTIC ( NumAllocaPartitions  ,
"Number of alloca partitions formed"   
)

◆ STATISTIC() [3/10]

STATISTIC ( MaxPartitionsPerAlloca  ,
"Maximum number of partitions per alloca"   
)

◆ STATISTIC() [4/10]

STATISTIC ( NumAllocaPartitionUses  ,
"Number of alloca partition uses rewritten"   
)

◆ STATISTIC() [5/10]

STATISTIC ( MaxUsesPerAllocaPartition  ,
"Maximum number of uses of a partition"   
)

◆ STATISTIC() [6/10]

STATISTIC ( NumNewAllocas  ,
"Number of  new,
smaller allocas introduced"   
)

◆ STATISTIC() [7/10]

STATISTIC ( NumPromoted  ,
"Number of allocas promoted to SSA values"   
)

◆ STATISTIC() [8/10]

STATISTIC ( NumLoadsSpeculated  ,
"Number of loads speculated to allow promotion"   
)

◆ STATISTIC() [9/10]

STATISTIC ( NumDeleted  ,
"Number of instructions deleted"   
)

◆ STATISTIC() [10/10]

STATISTIC ( NumVectorized  ,
"Number of vectorized aggregates"   
)

◆ stripAggregateTypeWrapping()

static Type* stripAggregateTypeWrapping ( const DataLayout DL,
Type Ty 
)
static

Strip aggregate type wrapping.

This removes no-op aggregate types wrapping an underlying type. It will strip as many layers of types as it can without changing either the type size or the allocated size.

Definition at line 3258 of file SROA.cpp.

References llvm::StructLayout::getElementContainingOffset(), llvm::DataLayout::getStructLayout(), llvm::DataLayout::getTypeAllocSize(), llvm::DataLayout::getTypeSizeInBits(), and llvm::Type::isSingleValueType().

Referenced by getTypePartition().

Variable Documentation

◆ Aggregates

Scalar Replacement Of Aggregates

Definition at line 4395 of file SROA.cpp.

◆ false

Scalar Replacement Of false

Definition at line 4395 of file SROA.cpp.

Referenced by isIntegerWideningViable().

◆ sroa

sroa

Definition at line 4395 of file SROA.cpp.

◆ SROARandomShuffleSlices

cl::opt<bool> SROARandomShuffleSlices("sroa-random-shuffle-slices", cl::init(false), cl::Hidden)
static

Hidden option to enable randomly shuffling the slices to help uncover instability in their order.

Referenced by AllocaSlices::SliceBuilder::SliceBuilder().

◆ SROAStrictInbounds

cl::opt<bool> SROAStrictInbounds("sroa-strict-inbounds", cl::init(false), cl::Hidden)
static

Hidden option to experiment with completely strict handling of inbounds GEPs.

Referenced by AllocaSlices::SliceBuilder::SliceBuilder().