ScalarReplAggregates.cpp [plain text]
#define DEBUG_TYPE "scalarrepl"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Function.h"
#include "llvm/GlobalVariable.h"
#include "llvm/Instructions.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/LLVMContext.h"
#include "llvm/Module.h"
#include "llvm/Pass.h"
#include "llvm/Analysis/DebugInfo.h"
#include "llvm/Analysis/DIBuilder.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Transforms/Utils/PromoteMemToReg.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/SSAUpdater.h"
#include "llvm/Support/CallSite.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/Support/IRBuilder.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
using namespace llvm;
STATISTIC(NumReplaced, "Number of allocas broken up");
STATISTIC(NumPromoted, "Number of allocas promoted");
STATISTIC(NumAdjusted, "Number of scalar allocas adjusted to allow promotion");
STATISTIC(NumConverted, "Number of aggregates converted to scalar");
STATISTIC(NumGlobals, "Number of allocas copied from constant global");
namespace {
struct SROA : public FunctionPass {
SROA(int T, bool hasDT, char &ID)
: FunctionPass(ID), HasDomTree(hasDT) {
if (T == -1)
SRThreshold = 128;
else
SRThreshold = T;
}
bool runOnFunction(Function &F);
bool performScalarRepl(Function &F);
bool performPromotion(Function &F);
private:
bool HasDomTree;
TargetData *TD;
SmallVector<Value*, 32> DeadInsts;
struct AllocaInfo {
AllocaInst *AI;
SmallPtrSet<PHINode*, 8> CheckedPHIs;
bool isUnsafe : 1;
bool isMemCpySrc : 1;
bool isMemCpyDst : 1;
bool hasSubelementAccess : 1;
bool hasALoadOrStore : 1;
explicit AllocaInfo(AllocaInst *ai)
: AI(ai), isUnsafe(false), isMemCpySrc(false), isMemCpyDst(false),
hasSubelementAccess(false), hasALoadOrStore(false) {}
};
unsigned SRThreshold;
void MarkUnsafe(AllocaInfo &I, Instruction *User) {
I.isUnsafe = true;
DEBUG(dbgs() << " Transformation preventing inst: " << *User << '\n');
}
bool isSafeAllocaToScalarRepl(AllocaInst *AI);
void isSafeForScalarRepl(Instruction *I, uint64_t Offset, AllocaInfo &Info);
void isSafePHISelectUseForScalarRepl(Instruction *User, uint64_t Offset,
AllocaInfo &Info);
void isSafeGEP(GetElementPtrInst *GEPI, uint64_t &Offset, AllocaInfo &Info);
void isSafeMemAccess(uint64_t Offset, uint64_t MemSize,
Type *MemOpType, bool isStore, AllocaInfo &Info,
Instruction *TheAccess, bool AllowWholeAccess);
bool TypeHasComponent(Type *T, uint64_t Offset, uint64_t Size);
uint64_t FindElementAndOffset(Type *&T, uint64_t &Offset,
Type *&IdxTy);
void DoScalarReplacement(AllocaInst *AI,
std::vector<AllocaInst*> &WorkList);
void DeleteDeadInstructions();
void RewriteForScalarRepl(Instruction *I, AllocaInst *AI, uint64_t Offset,
SmallVector<AllocaInst*, 32> &NewElts);
void RewriteBitCast(BitCastInst *BC, AllocaInst *AI, uint64_t Offset,
SmallVector<AllocaInst*, 32> &NewElts);
void RewriteGEP(GetElementPtrInst *GEPI, AllocaInst *AI, uint64_t Offset,
SmallVector<AllocaInst*, 32> &NewElts);
void RewriteLifetimeIntrinsic(IntrinsicInst *II, AllocaInst *AI,
uint64_t Offset,
SmallVector<AllocaInst*, 32> &NewElts);
void RewriteMemIntrinUserOfAlloca(MemIntrinsic *MI, Instruction *Inst,
AllocaInst *AI,
SmallVector<AllocaInst*, 32> &NewElts);
void RewriteStoreUserOfWholeAlloca(StoreInst *SI, AllocaInst *AI,
SmallVector<AllocaInst*, 32> &NewElts);
void RewriteLoadUserOfWholeAlloca(LoadInst *LI, AllocaInst *AI,
SmallVector<AllocaInst*, 32> &NewElts);
static MemTransferInst *isOnlyCopiedFromConstantGlobal(
AllocaInst *AI, SmallVector<Instruction*, 4> &ToDelete);
};
struct SROA_DT : public SROA {
static char ID;
public:
SROA_DT(int T = -1) : SROA(T, true, ID) {
initializeSROA_DTPass(*PassRegistry::getPassRegistry());
}
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequired<DominatorTree>();
AU.setPreservesCFG();
}
};
struct SROA_SSAUp : public SROA {
static char ID;
public:
SROA_SSAUp(int T = -1) : SROA(T, false, ID) {
initializeSROA_SSAUpPass(*PassRegistry::getPassRegistry());
}
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
}
};
}
char SROA_DT::ID = 0;
char SROA_SSAUp::ID = 0;
INITIALIZE_PASS_BEGIN(SROA_DT, "scalarrepl",
"Scalar Replacement of Aggregates (DT)", false, false)
INITIALIZE_PASS_DEPENDENCY(DominatorTree)
INITIALIZE_PASS_END(SROA_DT, "scalarrepl",
"Scalar Replacement of Aggregates (DT)", false, false)
INITIALIZE_PASS_BEGIN(SROA_SSAUp, "scalarrepl-ssa",
"Scalar Replacement of Aggregates (SSAUp)", false, false)
INITIALIZE_PASS_END(SROA_SSAUp, "scalarrepl-ssa",
"Scalar Replacement of Aggregates (SSAUp)", false, false)
FunctionPass *llvm::createScalarReplAggregatesPass(int Threshold,
bool UseDomTree) {
if (UseDomTree)
return new SROA_DT(Threshold);
return new SROA_SSAUp(Threshold);
}
namespace {
class ConvertToScalarInfo {
unsigned AllocaSize;
const TargetData &TD;
bool IsNotTrivial;
enum {
Unknown,
ImplicitVector,
Vector,
Integer
} ScalarKind;
VectorType *VectorTy;
bool HadNonMemTransferAccess;
public:
explicit ConvertToScalarInfo(unsigned Size, const TargetData &td)
: AllocaSize(Size), TD(td), IsNotTrivial(false), ScalarKind(Unknown),
VectorTy(0), HadNonMemTransferAccess(false) { }
AllocaInst *TryConvert(AllocaInst *AI);
private:
bool CanConvertToScalar(Value *V, uint64_t Offset);
void MergeInTypeForLoadOrStore(Type *In, uint64_t Offset);
bool MergeInVectorType(VectorType *VInTy, uint64_t Offset);
void ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI, uint64_t Offset);
Value *ConvertScalar_ExtractValue(Value *NV, Type *ToType,
uint64_t Offset, IRBuilder<> &Builder);
Value *ConvertScalar_InsertValue(Value *StoredVal, Value *ExistingVal,
uint64_t Offset, IRBuilder<> &Builder);
};
}
AllocaInst *ConvertToScalarInfo::TryConvert(AllocaInst *AI) {
if (!CanConvertToScalar(AI, 0) || !IsNotTrivial)
return 0;
if (ScalarKind == Unknown)
ScalarKind = Integer;
if (ScalarKind == Vector && VectorTy->getBitWidth() != AllocaSize * 8)
ScalarKind = Integer;
Type *NewTy;
if (ScalarKind == Vector) {
assert(VectorTy && "Missing type for vector scalar.");
DEBUG(dbgs() << "CONVERT TO VECTOR: " << *AI << "\n TYPE = "
<< *VectorTy << '\n');
NewTy = VectorTy; } else {
unsigned BitWidth = AllocaSize * 8;
if ((ScalarKind == ImplicitVector || ScalarKind == Integer) &&
!HadNonMemTransferAccess && !TD.fitsInLegalInteger(BitWidth))
return 0;
DEBUG(dbgs() << "CONVERT TO SCALAR INTEGER: " << *AI << "\n");
NewTy = IntegerType::get(AI->getContext(), BitWidth);
}
AllocaInst *NewAI = new AllocaInst(NewTy, 0, "", AI->getParent()->begin());
ConvertUsesToScalar(AI, NewAI, 0);
return NewAI;
}
void ConvertToScalarInfo::MergeInTypeForLoadOrStore(Type *In,
uint64_t Offset) {
if (ScalarKind == Integer)
return;
if (VectorType *VInTy = dyn_cast<VectorType>(In)) {
if (MergeInVectorType(VInTy, Offset))
return;
} else if (In->isFloatTy() || In->isDoubleTy() ||
(In->isIntegerTy() && In->getPrimitiveSizeInBits() >= 8 &&
isPowerOf2_32(In->getPrimitiveSizeInBits()))) {
unsigned EltSize = In->getPrimitiveSizeInBits()/8;
if (EltSize == AllocaSize)
return;
if (Offset % EltSize == 0 && AllocaSize % EltSize == 0 &&
(!VectorTy || EltSize == VectorTy->getElementType()
->getPrimitiveSizeInBits()/8)) {
if (!VectorTy) {
ScalarKind = ImplicitVector;
VectorTy = VectorType::get(In, AllocaSize/EltSize);
}
return;
}
}
ScalarKind = Integer;
}
bool ConvertToScalarInfo::MergeInVectorType(VectorType *VInTy,
uint64_t Offset) {
if (VInTy->getBitWidth()/8 == AllocaSize && Offset == 0) {
if (!VectorTy)
VectorTy = VInTy;
ScalarKind = Vector;
return true;
}
return false;
}
bool ConvertToScalarInfo::CanConvertToScalar(Value *V, uint64_t Offset) {
for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI!=E; ++UI) {
Instruction *User = cast<Instruction>(*UI);
if (LoadInst *LI = dyn_cast<LoadInst>(User)) {
if (!LI->isSimple())
return false;
if (LI->getType()->isX86_MMXTy())
return false;
HadNonMemTransferAccess = true;
MergeInTypeForLoadOrStore(LI->getType(), Offset);
continue;
}
if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
if (SI->getOperand(0) == V || !SI->isSimple()) return false;
if (SI->getOperand(0)->getType()->isX86_MMXTy())
return false;
HadNonMemTransferAccess = true;
MergeInTypeForLoadOrStore(SI->getOperand(0)->getType(), Offset);
continue;
}
if (BitCastInst *BCI = dyn_cast<BitCastInst>(User)) {
if (!onlyUsedByLifetimeMarkers(BCI))
IsNotTrivial = true; if (!CanConvertToScalar(BCI, Offset))
return false;
continue;
}
if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) {
if (!GEP->hasAllConstantIndices())
return false;
SmallVector<Value*, 8> Indices(GEP->op_begin()+1, GEP->op_end());
if (!GEP->getPointerOperandType()->isPointerTy())
return false;
uint64_t GEPOffset = TD.getIndexedOffset(GEP->getPointerOperandType(),
Indices);
if (!CanConvertToScalar(GEP, Offset+GEPOffset))
return false;
IsNotTrivial = true; HadNonMemTransferAccess = true;
continue;
}
if (MemSetInst *MSI = dyn_cast<MemSetInst>(User)) {
if (!isa<ConstantInt>(MSI->getValue()))
return false;
ConstantInt *Len = dyn_cast<ConstantInt>(MSI->getLength());
if (!Len)
return false;
if (Len->getZExtValue() != AllocaSize || Offset != 0)
ScalarKind = Integer;
IsNotTrivial = true; HadNonMemTransferAccess = true;
continue;
}
if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(User)) {
ConstantInt *Len = dyn_cast<ConstantInt>(MTI->getLength());
if (Len == 0 || Len->getZExtValue() != AllocaSize || Offset != 0)
return false;
IsNotTrivial = true; continue;
}
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(User)) {
if (II->getIntrinsicID() == Intrinsic::lifetime_start ||
II->getIntrinsicID() == Intrinsic::lifetime_end) {
continue;
}
}
return false;
}
return true;
}
void ConvertToScalarInfo::ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI,
uint64_t Offset) {
while (!Ptr->use_empty()) {
Instruction *User = cast<Instruction>(Ptr->use_back());
if (BitCastInst *CI = dyn_cast<BitCastInst>(User)) {
ConvertUsesToScalar(CI, NewAI, Offset);
CI->eraseFromParent();
continue;
}
if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) {
SmallVector<Value*, 8> Indices(GEP->op_begin()+1, GEP->op_end());
uint64_t GEPOffset = TD.getIndexedOffset(GEP->getPointerOperandType(),
Indices);
ConvertUsesToScalar(GEP, NewAI, Offset+GEPOffset*8);
GEP->eraseFromParent();
continue;
}
IRBuilder<> Builder(User);
if (LoadInst *LI = dyn_cast<LoadInst>(User)) {
Value *LoadedVal = Builder.CreateLoad(NewAI);
Value *NewLoadVal
= ConvertScalar_ExtractValue(LoadedVal, LI->getType(), Offset, Builder);
LI->replaceAllUsesWith(NewLoadVal);
LI->eraseFromParent();
continue;
}
if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
assert(SI->getOperand(0) != Ptr && "Consistency error!");
Instruction *Old = Builder.CreateLoad(NewAI, NewAI->getName()+".in");
Value *New = ConvertScalar_InsertValue(SI->getOperand(0), Old, Offset,
Builder);
Builder.CreateStore(New, NewAI);
SI->eraseFromParent();
if (Old->use_empty())
Old->eraseFromParent();
continue;
}
if (MemSetInst *MSI = dyn_cast<MemSetInst>(User)) {
assert(MSI->getRawDest() == Ptr && "Consistency error!");
signed SNumBytes = cast<ConstantInt>(MSI->getLength())->getSExtValue();
if (SNumBytes > 0) {
unsigned NumBytes = static_cast<unsigned>(SNumBytes);
unsigned Val = cast<ConstantInt>(MSI->getValue())->getZExtValue();
APInt APVal(NumBytes*8, Val);
if (Val)
for (unsigned i = 1; i != NumBytes; ++i)
APVal |= APVal << 8;
Instruction *Old = Builder.CreateLoad(NewAI, NewAI->getName()+".in");
Value *New = ConvertScalar_InsertValue(
ConstantInt::get(User->getContext(), APVal),
Old, Offset, Builder);
Builder.CreateStore(New, NewAI);
if (Old->use_empty())
Old->eraseFromParent();
}
MSI->eraseFromParent();
continue;
}
if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(User)) {
assert(Offset == 0 && "must be store to start of alloca");
AllocaInst *OrigAI = cast<AllocaInst>(GetUnderlyingObject(Ptr, &TD, 0));
if (GetUnderlyingObject(MTI->getSource(), &TD, 0) != OrigAI) {
assert(MTI->getRawDest() == Ptr && "Neither use is of pointer?");
Value *SrcPtr = MTI->getSource();
PointerType* SPTy = cast<PointerType>(SrcPtr->getType());
PointerType* AIPTy = cast<PointerType>(NewAI->getType());
if (SPTy->getAddressSpace() != AIPTy->getAddressSpace()) {
AIPTy = PointerType::get(AIPTy->getElementType(),
SPTy->getAddressSpace());
}
SrcPtr = Builder.CreateBitCast(SrcPtr, AIPTy);
LoadInst *SrcVal = Builder.CreateLoad(SrcPtr, "srcval");
SrcVal->setAlignment(MTI->getAlignment());
Builder.CreateStore(SrcVal, NewAI);
} else if (GetUnderlyingObject(MTI->getDest(), &TD, 0) != OrigAI) {
assert(MTI->getRawSource() == Ptr && "Neither use is of pointer?");
LoadInst *SrcVal = Builder.CreateLoad(NewAI, "srcval");
PointerType* DPTy = cast<PointerType>(MTI->getDest()->getType());
PointerType* AIPTy = cast<PointerType>(NewAI->getType());
if (DPTy->getAddressSpace() != AIPTy->getAddressSpace()) {
AIPTy = PointerType::get(AIPTy->getElementType(),
DPTy->getAddressSpace());
}
Value *DstPtr = Builder.CreateBitCast(MTI->getDest(), AIPTy);
StoreInst *NewStore = Builder.CreateStore(SrcVal, DstPtr);
NewStore->setAlignment(MTI->getAlignment());
} else {
}
MTI->eraseFromParent();
continue;
}
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(User)) {
if (II->getIntrinsicID() == Intrinsic::lifetime_start ||
II->getIntrinsicID() == Intrinsic::lifetime_end) {
II->eraseFromParent();
continue;
}
}
llvm_unreachable("Unsupported operation!");
}
}
Value *ConvertToScalarInfo::
ConvertScalar_ExtractValue(Value *FromVal, Type *ToType,
uint64_t Offset, IRBuilder<> &Builder) {
Type *FromType = FromVal->getType();
if (FromType == ToType && Offset == 0)
return FromVal;
if (VectorType *VTy = dyn_cast<VectorType>(FromType)) {
unsigned FromTypeSize = TD.getTypeAllocSize(FromType);
unsigned ToTypeSize = TD.getTypeAllocSize(ToType);
if (FromTypeSize == ToTypeSize)
return Builder.CreateBitCast(FromVal, ToType);
unsigned Elt = 0;
if (Offset) {
unsigned EltSize = TD.getTypeAllocSizeInBits(VTy->getElementType());
Elt = Offset/EltSize;
assert(EltSize*Elt == Offset && "Invalid modulus in validity checking");
}
Value *V = Builder.CreateExtractElement(FromVal, Builder.getInt32(Elt));
if (V->getType() != ToType)
V = Builder.CreateBitCast(V, ToType);
return V;
}
if (StructType *ST = dyn_cast<StructType>(ToType)) {
const StructLayout &Layout = *TD.getStructLayout(ST);
Value *Res = UndefValue::get(ST);
for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) {
Value *Elt = ConvertScalar_ExtractValue(FromVal, ST->getElementType(i),
Offset+Layout.getElementOffsetInBits(i),
Builder);
Res = Builder.CreateInsertValue(Res, Elt, i);
}
return Res;
}
if (ArrayType *AT = dyn_cast<ArrayType>(ToType)) {
uint64_t EltSize = TD.getTypeAllocSizeInBits(AT->getElementType());
Value *Res = UndefValue::get(AT);
for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) {
Value *Elt = ConvertScalar_ExtractValue(FromVal, AT->getElementType(),
Offset+i*EltSize, Builder);
Res = Builder.CreateInsertValue(Res, Elt, i);
}
return Res;
}
IntegerType *NTy = cast<IntegerType>(FromVal->getType());
int ShAmt = 0;
if (TD.isBigEndian()) {
ShAmt = TD.getTypeStoreSizeInBits(NTy) -
TD.getTypeStoreSizeInBits(ToType) - Offset;
} else {
ShAmt = Offset;
}
if (ShAmt > 0 && (unsigned)ShAmt < NTy->getBitWidth())
FromVal = Builder.CreateLShr(FromVal,
ConstantInt::get(FromVal->getType(), ShAmt));
else if (ShAmt < 0 && (unsigned)-ShAmt < NTy->getBitWidth())
FromVal = Builder.CreateShl(FromVal,
ConstantInt::get(FromVal->getType(), -ShAmt));
unsigned LIBitWidth = TD.getTypeSizeInBits(ToType);
if (LIBitWidth < NTy->getBitWidth())
FromVal =
Builder.CreateTrunc(FromVal, IntegerType::get(FromVal->getContext(),
LIBitWidth));
else if (LIBitWidth > NTy->getBitWidth())
FromVal =
Builder.CreateZExt(FromVal, IntegerType::get(FromVal->getContext(),
LIBitWidth));
if (ToType->isIntegerTy()) {
} else if (ToType->isFloatingPointTy() || ToType->isVectorTy()) {
FromVal = Builder.CreateBitCast(FromVal, ToType);
} else {
FromVal = Builder.CreateIntToPtr(FromVal, ToType);
}
assert(FromVal->getType() == ToType && "Didn't convert right?");
return FromVal;
}
Value *ConvertToScalarInfo::
ConvertScalar_InsertValue(Value *SV, Value *Old,
uint64_t Offset, IRBuilder<> &Builder) {
Type *AllocaType = Old->getType();
LLVMContext &Context = Old->getContext();
if (VectorType *VTy = dyn_cast<VectorType>(AllocaType)) {
uint64_t VecSize = TD.getTypeAllocSizeInBits(VTy);
uint64_t ValSize = TD.getTypeAllocSizeInBits(SV->getType());
if (ValSize == VecSize)
return Builder.CreateBitCast(SV, AllocaType);
Type *EltTy = VTy->getElementType();
if (SV->getType() != EltTy)
SV = Builder.CreateBitCast(SV, EltTy);
uint64_t EltSize = TD.getTypeAllocSizeInBits(EltTy);
unsigned Elt = Offset/EltSize;
return Builder.CreateInsertElement(Old, SV, Builder.getInt32(Elt));
}
if (StructType *ST = dyn_cast<StructType>(SV->getType())) {
const StructLayout &Layout = *TD.getStructLayout(ST);
for (unsigned i = 0, e = ST->getNumElements(); i != e; ++i) {
Value *Elt = Builder.CreateExtractValue(SV, i);
Old = ConvertScalar_InsertValue(Elt, Old,
Offset+Layout.getElementOffsetInBits(i),
Builder);
}
return Old;
}
if (ArrayType *AT = dyn_cast<ArrayType>(SV->getType())) {
uint64_t EltSize = TD.getTypeAllocSizeInBits(AT->getElementType());
for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) {
Value *Elt = Builder.CreateExtractValue(SV, i);
Old = ConvertScalar_InsertValue(Elt, Old, Offset+i*EltSize, Builder);
}
return Old;
}
unsigned SrcWidth = TD.getTypeSizeInBits(SV->getType());
unsigned DestWidth = TD.getTypeSizeInBits(AllocaType);
unsigned SrcStoreWidth = TD.getTypeStoreSizeInBits(SV->getType());
unsigned DestStoreWidth = TD.getTypeStoreSizeInBits(AllocaType);
if (SV->getType()->isFloatingPointTy() || SV->getType()->isVectorTy())
SV = Builder.CreateBitCast(SV, IntegerType::get(SV->getContext(),SrcWidth));
else if (SV->getType()->isPointerTy())
SV = Builder.CreatePtrToInt(SV, TD.getIntPtrType(SV->getContext()));
if (SV->getType() != AllocaType) {
if (SV->getType()->getPrimitiveSizeInBits() <
AllocaType->getPrimitiveSizeInBits())
SV = Builder.CreateZExt(SV, AllocaType);
else {
SV = Builder.CreateTrunc(SV, AllocaType);
SrcWidth = DestWidth;
SrcStoreWidth = DestStoreWidth;
}
}
int ShAmt = 0;
if (TD.isBigEndian()) {
ShAmt = DestStoreWidth - SrcStoreWidth - Offset;
} else {
ShAmt = Offset;
}
APInt Mask(APInt::getLowBitsSet(DestWidth, SrcWidth));
if (ShAmt > 0 && (unsigned)ShAmt < DestWidth) {
SV = Builder.CreateShl(SV, ConstantInt::get(SV->getType(), ShAmt));
Mask <<= ShAmt;
} else if (ShAmt < 0 && (unsigned)-ShAmt < DestWidth) {
SV = Builder.CreateLShr(SV, ConstantInt::get(SV->getType(), -ShAmt));
Mask = Mask.lshr(-ShAmt);
}
if (SrcWidth != DestWidth) {
assert(DestWidth > SrcWidth);
Old = Builder.CreateAnd(Old, ConstantInt::get(Context, ~Mask), "mask");
SV = Builder.CreateOr(Old, SV, "ins");
}
return SV;
}
bool SROA::runOnFunction(Function &F) {
TD = getAnalysisIfAvailable<TargetData>();
bool Changed = performPromotion(F);
if (!TD) return Changed;
while (1) {
bool LocalChange = performScalarRepl(F);
if (!LocalChange) break; Changed = true;
LocalChange = performPromotion(F);
if (!LocalChange) break; }
return Changed;
}
namespace {
class AllocaPromoter : public LoadAndStorePromoter {
AllocaInst *AI;
DIBuilder *DIB;
SmallVector<DbgDeclareInst *, 4> DDIs;
SmallVector<DbgValueInst *, 4> DVIs;
public:
AllocaPromoter(const SmallVectorImpl<Instruction*> &Insts, SSAUpdater &S,
DIBuilder *DB)
: LoadAndStorePromoter(Insts, S), AI(0), DIB(DB) {}
void run(AllocaInst *AI, const SmallVectorImpl<Instruction*> &Insts) {
this->AI = AI;
if (MDNode *DebugNode = MDNode::getIfExists(AI->getContext(), AI)) {
for (Value::use_iterator UI = DebugNode->use_begin(),
E = DebugNode->use_end(); UI != E; ++UI)
if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(*UI))
DDIs.push_back(DDI);
else if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(*UI))
DVIs.push_back(DVI);
}
LoadAndStorePromoter::run(Insts);
AI->eraseFromParent();
for (SmallVector<DbgDeclareInst *, 4>::iterator I = DDIs.begin(),
E = DDIs.end(); I != E; ++I) {
DbgDeclareInst *DDI = *I;
DDI->eraseFromParent();
}
for (SmallVector<DbgValueInst *, 4>::iterator I = DVIs.begin(),
E = DVIs.end(); I != E; ++I) {
DbgValueInst *DVI = *I;
DVI->eraseFromParent();
}
}
virtual bool isInstInList(Instruction *I,
const SmallVectorImpl<Instruction*> &Insts) const {
if (LoadInst *LI = dyn_cast<LoadInst>(I))
return LI->getOperand(0) == AI;
return cast<StoreInst>(I)->getPointerOperand() == AI;
}
virtual void updateDebugInfo(Instruction *Inst) const {
for (SmallVector<DbgDeclareInst *, 4>::const_iterator I = DDIs.begin(),
E = DDIs.end(); I != E; ++I) {
DbgDeclareInst *DDI = *I;
if (StoreInst *SI = dyn_cast<StoreInst>(Inst))
ConvertDebugDeclareToDebugValue(DDI, SI, *DIB);
else if (LoadInst *LI = dyn_cast<LoadInst>(Inst))
ConvertDebugDeclareToDebugValue(DDI, LI, *DIB);
}
for (SmallVector<DbgValueInst *, 4>::const_iterator I = DVIs.begin(),
E = DVIs.end(); I != E; ++I) {
DbgValueInst *DVI = *I;
Value *Arg = NULL;
if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
if (ZExtInst *ZExt = dyn_cast<ZExtInst>(SI->getOperand(0)))
Arg = dyn_cast<Argument>(ZExt->getOperand(0));
if (SExtInst *SExt = dyn_cast<SExtInst>(SI->getOperand(0)))
Arg = dyn_cast<Argument>(SExt->getOperand(0));
if (!Arg)
Arg = SI->getOperand(0);
} else if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
Arg = LI->getOperand(0);
} else {
continue;
}
Instruction *DbgVal =
DIB->insertDbgValueIntrinsic(Arg, 0, DIVariable(DVI->getVariable()),
Inst);
DbgVal->setDebugLoc(DVI->getDebugLoc());
}
}
};
}
static bool isSafeSelectToSpeculate(SelectInst *SI, const TargetData *TD) {
bool TDerefable = SI->getTrueValue()->isDereferenceablePointer();
bool FDerefable = SI->getFalseValue()->isDereferenceablePointer();
for (Value::use_iterator UI = SI->use_begin(), UE = SI->use_end();
UI != UE; ++UI) {
LoadInst *LI = dyn_cast<LoadInst>(*UI);
if (LI == 0 || !LI->isSimple()) return false;
if (!TDerefable && !isSafeToLoadUnconditionally(SI->getTrueValue(), LI,
LI->getAlignment(), TD))
return false;
if (!FDerefable && !isSafeToLoadUnconditionally(SI->getFalseValue(), LI,
LI->getAlignment(), TD))
return false;
}
return true;
}
static bool isSafePHIToSpeculate(PHINode *PN, const TargetData *TD) {
BasicBlock *BB = PN->getParent();
unsigned MaxAlign = 0;
for (Value::use_iterator UI = PN->use_begin(), UE = PN->use_end();
UI != UE; ++UI) {
LoadInst *LI = dyn_cast<LoadInst>(*UI);
if (LI == 0 || !LI->isSimple()) return false;
if (LI->getParent() != BB) return false;
for (BasicBlock::iterator BBI = PN; &*BBI != LI; ++BBI)
if (BBI->mayWriteToMemory())
return false;
MaxAlign = std::max(MaxAlign, LI->getAlignment());
}
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
BasicBlock *Pred = PN->getIncomingBlock(i);
Value *InVal = PN->getIncomingValue(i);
if (Pred->getTerminator()->mayHaveSideEffects())
return false;
if (Pred->getTerminator() == InVal)
return false;
if (Pred->getTerminator()->getNumSuccessors() == 1)
continue;
if (InVal->isDereferenceablePointer() ||
isSafeToLoadUnconditionally(InVal, Pred->getTerminator(), MaxAlign, TD))
continue;
return false;
}
return true;
}
static bool tryToMakeAllocaBePromotable(AllocaInst *AI, const TargetData *TD) {
SetVector<Instruction*, SmallVector<Instruction*, 4>,
SmallPtrSet<Instruction*, 4> > InstsToRewrite;
for (Value::use_iterator UI = AI->use_begin(), UE = AI->use_end();
UI != UE; ++UI) {
User *U = *UI;
if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
if (!LI->isSimple())
return false;
continue;
}
if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
if (SI->getOperand(0) == AI || !SI->isSimple())
return false; continue;
}
if (SelectInst *SI = dyn_cast<SelectInst>(U)) {
if (ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition())) {
Value *Result = SI->getOperand(1+CI->isZero());
SI->replaceAllUsesWith(Result);
SI->eraseFromParent();
return tryToMakeAllocaBePromotable(AI, TD);
}
if (!isSafeSelectToSpeculate(SI, TD))
return false;
InstsToRewrite.insert(SI);
continue;
}
if (PHINode *PN = dyn_cast<PHINode>(U)) {
if (PN->use_empty()) { InstsToRewrite.insert(PN);
continue;
}
if (!isSafePHIToSpeculate(PN, TD))
return false;
InstsToRewrite.insert(PN);
continue;
}
if (BitCastInst *BCI = dyn_cast<BitCastInst>(U)) {
if (onlyUsedByLifetimeMarkers(BCI)) {
InstsToRewrite.insert(BCI);
continue;
}
}
return false;
}
if (InstsToRewrite.empty())
return true;
for (unsigned i = 0, e = InstsToRewrite.size(); i != e; ++i) {
if (BitCastInst *BCI = dyn_cast<BitCastInst>(InstsToRewrite[i])) {
for (BitCastInst::use_iterator I = BCI->use_begin(), E = BCI->use_end();
I != E;) {
Use &U = I.getUse();
++I;
cast<Instruction>(U.getUser())->eraseFromParent();
}
BCI->eraseFromParent();
continue;
}
if (SelectInst *SI = dyn_cast<SelectInst>(InstsToRewrite[i])) {
while (!SI->use_empty()) {
LoadInst *LI = cast<LoadInst>(SI->use_back());
IRBuilder<> Builder(LI);
LoadInst *TrueLoad =
Builder.CreateLoad(SI->getTrueValue(), LI->getName()+".t");
LoadInst *FalseLoad =
Builder.CreateLoad(SI->getFalseValue(), LI->getName()+".f");
TrueLoad->setAlignment(LI->getAlignment());
FalseLoad->setAlignment(LI->getAlignment());
if (MDNode *Tag = LI->getMetadata(LLVMContext::MD_tbaa)) {
TrueLoad->setMetadata(LLVMContext::MD_tbaa, Tag);
FalseLoad->setMetadata(LLVMContext::MD_tbaa, Tag);
}
Value *V = Builder.CreateSelect(SI->getCondition(), TrueLoad, FalseLoad);
V->takeName(LI);
LI->replaceAllUsesWith(V);
LI->eraseFromParent();
}
SI->eraseFromParent();
continue;
}
PHINode *PN = cast<PHINode>(InstsToRewrite[i]);
if (PN->use_empty()) {
PN->eraseFromParent();
continue;
}
Type *LoadTy = cast<PointerType>(PN->getType())->getElementType();
PHINode *NewPN = PHINode::Create(LoadTy, PN->getNumIncomingValues(),
PN->getName()+".ld", PN);
LoadInst *SomeLoad = cast<LoadInst>(PN->use_back());
MDNode *TBAATag = SomeLoad->getMetadata(LLVMContext::MD_tbaa);
unsigned Align = SomeLoad->getAlignment();
while (!PN->use_empty()) {
LoadInst *LI = cast<LoadInst>(PN->use_back());
LI->replaceAllUsesWith(NewPN);
LI->eraseFromParent();
}
DenseMap<BasicBlock*, LoadInst*> InsertedLoads;
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
BasicBlock *Pred = PN->getIncomingBlock(i);
LoadInst *&Load = InsertedLoads[Pred];
if (Load == 0) {
Load = new LoadInst(PN->getIncomingValue(i),
PN->getName() + "." + Pred->getName(),
Pred->getTerminator());
Load->setAlignment(Align);
if (TBAATag) Load->setMetadata(LLVMContext::MD_tbaa, TBAATag);
}
NewPN->addIncoming(Load, Pred);
}
PN->eraseFromParent();
}
++NumAdjusted;
return true;
}
bool SROA::performPromotion(Function &F) {
std::vector<AllocaInst*> Allocas;
DominatorTree *DT = 0;
if (HasDomTree)
DT = &getAnalysis<DominatorTree>();
BasicBlock &BB = F.getEntryBlock(); DIBuilder DIB(*F.getParent());
bool Changed = false;
SmallVector<Instruction*, 64> Insts;
while (1) {
Allocas.clear();
for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I)
if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) if (tryToMakeAllocaBePromotable(AI, TD))
Allocas.push_back(AI);
if (Allocas.empty()) break;
if (HasDomTree)
PromoteMemToReg(Allocas, *DT);
else {
SSAUpdater SSA;
for (unsigned i = 0, e = Allocas.size(); i != e; ++i) {
AllocaInst *AI = Allocas[i];
for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end();
UI != E; ++UI)
Insts.push_back(cast<Instruction>(*UI));
AllocaPromoter(Insts, SSA, &DIB).run(AI, Insts);
Insts.clear();
}
}
NumPromoted += Allocas.size();
Changed = true;
}
return Changed;
}
static bool ShouldAttemptScalarRepl(AllocaInst *AI) {
Type *T = AI->getAllocatedType();
if (StructType *ST = dyn_cast<StructType>(T))
return ST->getNumElements() <= 32;
if (ArrayType *AT = dyn_cast<ArrayType>(T))
return AT->getNumElements() <= 8;
return false;
}
bool SROA::performScalarRepl(Function &F) {
std::vector<AllocaInst*> WorkList;
BasicBlock &BB = F.getEntryBlock();
for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I)
if (AllocaInst *A = dyn_cast<AllocaInst>(I))
WorkList.push_back(A);
bool Changed = false;
while (!WorkList.empty()) {
AllocaInst *AI = WorkList.back();
WorkList.pop_back();
if (AI->use_empty()) {
AI->eraseFromParent();
Changed = true;
continue;
}
if (AI->isArrayAllocation() || !AI->getAllocatedType()->isSized())
continue;
SmallVector<Instruction *, 4> ToDelete;
if (MemTransferInst *Copy = isOnlyCopiedFromConstantGlobal(AI, ToDelete)) {
DEBUG(dbgs() << "Found alloca equal to global: " << *AI << '\n');
DEBUG(dbgs() << " memcpy = " << *Copy << '\n');
for (unsigned i = 0, e = ToDelete.size(); i != e; ++i)
ToDelete[i]->eraseFromParent();
Constant *TheSrc = cast<Constant>(Copy->getSource());
AI->replaceAllUsesWith(ConstantExpr::getBitCast(TheSrc, AI->getType()));
Copy->eraseFromParent(); AI->eraseFromParent();
++NumGlobals;
Changed = true;
continue;
}
uint64_t AllocaSize = TD->getTypeAllocSize(AI->getAllocatedType());
if (AllocaSize == 0) continue;
if (AllocaSize > SRThreshold) continue;
if (ShouldAttemptScalarRepl(AI) && isSafeAllocaToScalarRepl(AI)) {
DoScalarReplacement(AI, WorkList);
Changed = true;
continue;
}
if (AllocaInst *NewAI =
ConvertToScalarInfo((unsigned)AllocaSize, *TD).TryConvert(AI)) {
NewAI->takeName(AI);
AI->eraseFromParent();
++NumConverted;
Changed = true;
continue;
}
}
return Changed;
}
void SROA::DoScalarReplacement(AllocaInst *AI,
std::vector<AllocaInst*> &WorkList) {
DEBUG(dbgs() << "Found inst to SROA: " << *AI << '\n');
SmallVector<AllocaInst*, 32> ElementAllocas;
if (StructType *ST = dyn_cast<StructType>(AI->getAllocatedType())) {
ElementAllocas.reserve(ST->getNumContainedTypes());
for (unsigned i = 0, e = ST->getNumContainedTypes(); i != e; ++i) {
AllocaInst *NA = new AllocaInst(ST->getContainedType(i), 0,
AI->getAlignment(),
AI->getName() + "." + Twine(i), AI);
ElementAllocas.push_back(NA);
WorkList.push_back(NA); }
} else {
ArrayType *AT = cast<ArrayType>(AI->getAllocatedType());
ElementAllocas.reserve(AT->getNumElements());
Type *ElTy = AT->getElementType();
for (unsigned i = 0, e = AT->getNumElements(); i != e; ++i) {
AllocaInst *NA = new AllocaInst(ElTy, 0, AI->getAlignment(),
AI->getName() + "." + Twine(i), AI);
ElementAllocas.push_back(NA);
WorkList.push_back(NA); }
}
RewriteForScalarRepl(AI, AI, 0, ElementAllocas);
DeleteDeadInstructions();
AI->eraseFromParent();
++NumReplaced;
}
void SROA::DeleteDeadInstructions() {
while (!DeadInsts.empty()) {
Instruction *I = cast<Instruction>(DeadInsts.pop_back_val());
for (User::op_iterator OI = I->op_begin(), E = I->op_end(); OI != E; ++OI)
if (Instruction *U = dyn_cast<Instruction>(*OI)) {
*OI = 0;
if (isInstructionTriviallyDead(U) && !isa<AllocaInst>(U))
DeadInsts.push_back(U);
}
I->eraseFromParent();
}
}
void SROA::isSafeForScalarRepl(Instruction *I, uint64_t Offset,
AllocaInfo &Info) {
for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI!=E; ++UI) {
Instruction *User = cast<Instruction>(*UI);
if (BitCastInst *BC = dyn_cast<BitCastInst>(User)) {
isSafeForScalarRepl(BC, Offset, Info);
} else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) {
uint64_t GEPOffset = Offset;
isSafeGEP(GEPI, GEPOffset, Info);
if (!Info.isUnsafe)
isSafeForScalarRepl(GEPI, GEPOffset, Info);
} else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(User)) {
ConstantInt *Length = dyn_cast<ConstantInt>(MI->getLength());
if (Length == 0)
return MarkUnsafe(Info, User);
if (Length->isNegative())
return MarkUnsafe(Info, User);
isSafeMemAccess(Offset, Length->getZExtValue(), 0,
UI.getOperandNo() == 0, Info, MI,
true );
} else if (LoadInst *LI = dyn_cast<LoadInst>(User)) {
if (!LI->isSimple())
return MarkUnsafe(Info, User);
Type *LIType = LI->getType();
isSafeMemAccess(Offset, TD->getTypeAllocSize(LIType),
LIType, false, Info, LI, true );
Info.hasALoadOrStore = true;
} else if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
if (!SI->isSimple() || SI->getOperand(0) == I)
return MarkUnsafe(Info, User);
Type *SIType = SI->getOperand(0)->getType();
isSafeMemAccess(Offset, TD->getTypeAllocSize(SIType),
SIType, true, Info, SI, true );
Info.hasALoadOrStore = true;
} else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(User)) {
if (II->getIntrinsicID() != Intrinsic::lifetime_start &&
II->getIntrinsicID() != Intrinsic::lifetime_end)
return MarkUnsafe(Info, User);
} else if (isa<PHINode>(User) || isa<SelectInst>(User)) {
isSafePHISelectUseForScalarRepl(User, Offset, Info);
} else {
return MarkUnsafe(Info, User);
}
if (Info.isUnsafe) return;
}
}
void SROA::isSafePHISelectUseForScalarRepl(Instruction *I, uint64_t Offset,
AllocaInfo &Info) {
if (PHINode *PN = dyn_cast<PHINode>(I))
if (!Info.CheckedPHIs.insert(PN))
return;
for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI!=E; ++UI) {
Instruction *User = cast<Instruction>(*UI);
if (BitCastInst *BC = dyn_cast<BitCastInst>(User)) {
isSafePHISelectUseForScalarRepl(BC, Offset, Info);
} else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) {
if (!GEPI->hasAllZeroIndices())
return MarkUnsafe(Info, User);
isSafePHISelectUseForScalarRepl(GEPI, Offset, Info);
} else if (LoadInst *LI = dyn_cast<LoadInst>(User)) {
if (!LI->isSimple())
return MarkUnsafe(Info, User);
Type *LIType = LI->getType();
isSafeMemAccess(Offset, TD->getTypeAllocSize(LIType),
LIType, false, Info, LI, false );
Info.hasALoadOrStore = true;
} else if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
if (!SI->isSimple() || SI->getOperand(0) == I)
return MarkUnsafe(Info, User);
Type *SIType = SI->getOperand(0)->getType();
isSafeMemAccess(Offset, TD->getTypeAllocSize(SIType),
SIType, true, Info, SI, false );
Info.hasALoadOrStore = true;
} else if (isa<PHINode>(User) || isa<SelectInst>(User)) {
isSafePHISelectUseForScalarRepl(User, Offset, Info);
} else {
return MarkUnsafe(Info, User);
}
if (Info.isUnsafe) return;
}
}
void SROA::isSafeGEP(GetElementPtrInst *GEPI,
uint64_t &Offset, AllocaInfo &Info) {
gep_type_iterator GEPIt = gep_type_begin(GEPI), E = gep_type_end(GEPI);
if (GEPIt == E)
return;
for (; GEPIt != E; ++GEPIt) {
if ((*GEPIt)->isStructTy())
continue;
ConstantInt *IdxVal = dyn_cast<ConstantInt>(GEPIt.getOperand());
if (!IdxVal)
return MarkUnsafe(Info, GEPI);
}
SmallVector<Value*, 8> Indices(GEPI->op_begin() + 1, GEPI->op_end());
Offset += TD->getIndexedOffset(GEPI->getPointerOperandType(), Indices);
if (!TypeHasComponent(Info.AI->getAllocatedType(), Offset, 0))
MarkUnsafe(Info, GEPI);
}
static bool isHomogeneousAggregate(Type *T, unsigned &NumElts,
Type *&EltTy) {
if (ArrayType *AT = dyn_cast<ArrayType>(T)) {
NumElts = AT->getNumElements();
EltTy = (NumElts == 0 ? 0 : AT->getElementType());
return true;
}
if (StructType *ST = dyn_cast<StructType>(T)) {
NumElts = ST->getNumContainedTypes();
EltTy = (NumElts == 0 ? 0 : ST->getContainedType(0));
for (unsigned n = 1; n < NumElts; ++n) {
if (ST->getContainedType(n) != EltTy)
return false;
}
return true;
}
return false;
}
static bool isCompatibleAggregate(Type *T1, Type *T2) {
if (T1 == T2)
return true;
unsigned NumElts1, NumElts2;
Type *EltTy1, *EltTy2;
if (isHomogeneousAggregate(T1, NumElts1, EltTy1) &&
isHomogeneousAggregate(T2, NumElts2, EltTy2) &&
NumElts1 == NumElts2 &&
EltTy1 == EltTy2)
return true;
return false;
}
void SROA::isSafeMemAccess(uint64_t Offset, uint64_t MemSize,
Type *MemOpType, bool isStore,
AllocaInfo &Info, Instruction *TheAccess,
bool AllowWholeAccess) {
if (Offset == 0 && AllowWholeAccess &&
MemSize == TD->getTypeAllocSize(Info.AI->getAllocatedType())) {
if (!MemOpType || MemOpType->isIntegerTy()) {
if (isStore)
Info.isMemCpyDst = true;
else
Info.isMemCpySrc = true;
return;
}
if (isCompatibleAggregate(MemOpType, Info.AI->getAllocatedType())) {
Info.hasSubelementAccess = true;
return;
}
}
Type *T = Info.AI->getAllocatedType();
if (TypeHasComponent(T, Offset, MemSize)) {
Info.hasSubelementAccess = true;
return;
}
return MarkUnsafe(Info, TheAccess);
}
bool SROA::TypeHasComponent(Type *T, uint64_t Offset, uint64_t Size) {
Type *EltTy;
uint64_t EltSize;
if (StructType *ST = dyn_cast<StructType>(T)) {
const StructLayout *Layout = TD->getStructLayout(ST);
unsigned EltIdx = Layout->getElementContainingOffset(Offset);
EltTy = ST->getContainedType(EltIdx);
EltSize = TD->getTypeAllocSize(EltTy);
Offset -= Layout->getElementOffset(EltIdx);
} else if (ArrayType *AT = dyn_cast<ArrayType>(T)) {
EltTy = AT->getElementType();
EltSize = TD->getTypeAllocSize(EltTy);
if (Offset >= AT->getNumElements() * EltSize)
return false;
Offset %= EltSize;
} else {
return false;
}
if (Offset == 0 && (Size == 0 || EltSize == Size))
return true;
if (Offset + Size > EltSize)
return false;
return TypeHasComponent(EltTy, Offset, Size);
}
void SROA::RewriteForScalarRepl(Instruction *I, AllocaInst *AI, uint64_t Offset,
SmallVector<AllocaInst*, 32> &NewElts) {
for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI!=E;) {
Use &TheUse = UI.getUse();
Instruction *User = cast<Instruction>(*UI++);
if (BitCastInst *BC = dyn_cast<BitCastInst>(User)) {
RewriteBitCast(BC, AI, Offset, NewElts);
continue;
}
if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) {
RewriteGEP(GEPI, AI, Offset, NewElts);
continue;
}
if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(User)) {
ConstantInt *Length = dyn_cast<ConstantInt>(MI->getLength());
uint64_t MemSize = Length->getZExtValue();
if (Offset == 0 &&
MemSize == TD->getTypeAllocSize(AI->getAllocatedType()))
RewriteMemIntrinUserOfAlloca(MI, I, AI, NewElts);
continue;
}
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(User)) {
if (II->getIntrinsicID() == Intrinsic::lifetime_start ||
II->getIntrinsicID() == Intrinsic::lifetime_end) {
RewriteLifetimeIntrinsic(II, AI, Offset, NewElts);
}
continue;
}
if (LoadInst *LI = dyn_cast<LoadInst>(User)) {
Type *LIType = LI->getType();
if (isCompatibleAggregate(LIType, AI->getAllocatedType())) {
Value *Insert = UndefValue::get(LIType);
IRBuilder<> Builder(LI);
for (unsigned i = 0, e = NewElts.size(); i != e; ++i) {
Value *Load = Builder.CreateLoad(NewElts[i], "load");
Insert = Builder.CreateInsertValue(Insert, Load, i, "insert");
}
LI->replaceAllUsesWith(Insert);
DeadInsts.push_back(LI);
} else if (LIType->isIntegerTy() &&
TD->getTypeAllocSize(LIType) ==
TD->getTypeAllocSize(AI->getAllocatedType())) {
RewriteLoadUserOfWholeAlloca(LI, AI, NewElts);
}
continue;
}
if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
Value *Val = SI->getOperand(0);
Type *SIType = Val->getType();
if (isCompatibleAggregate(SIType, AI->getAllocatedType())) {
IRBuilder<> Builder(SI);
for (unsigned i = 0, e = NewElts.size(); i != e; ++i) {
Value *Extract = Builder.CreateExtractValue(Val, i, Val->getName());
Builder.CreateStore(Extract, NewElts[i]);
}
DeadInsts.push_back(SI);
} else if (SIType->isIntegerTy() &&
TD->getTypeAllocSize(SIType) ==
TD->getTypeAllocSize(AI->getAllocatedType())) {
RewriteStoreUserOfWholeAlloca(SI, AI, NewElts);
}
continue;
}
if (isa<SelectInst>(User) || isa<PHINode>(User)) {
if (!isa<AllocaInst>(I)) continue;
assert(Offset == 0 && NewElts[0] &&
"Direct alloca use should have a zero offset");
AllocaInst *NewAI = NewElts[0];
BitCastInst *BCI = new BitCastInst(NewAI, AI->getType(), "", NewAI);
NewAI->moveBefore(BCI);
TheUse = BCI;
continue;
}
}
}
void SROA::RewriteBitCast(BitCastInst *BC, AllocaInst *AI, uint64_t Offset,
SmallVector<AllocaInst*, 32> &NewElts) {
RewriteForScalarRepl(BC, AI, Offset, NewElts);
if (BC->getOperand(0) != AI)
return;
Type *T = AI->getAllocatedType();
uint64_t EltOffset = 0;
Type *IdxTy;
uint64_t Idx = FindElementAndOffset(T, EltOffset, IdxTy);
Instruction *Val = NewElts[Idx];
if (Val->getType() != BC->getDestTy()) {
Val = new BitCastInst(Val, BC->getDestTy(), "", BC);
Val->takeName(BC);
}
BC->replaceAllUsesWith(Val);
DeadInsts.push_back(BC);
}
uint64_t SROA::FindElementAndOffset(Type *&T, uint64_t &Offset,
Type *&IdxTy) {
uint64_t Idx = 0;
if (StructType *ST = dyn_cast<StructType>(T)) {
const StructLayout *Layout = TD->getStructLayout(ST);
Idx = Layout->getElementContainingOffset(Offset);
T = ST->getContainedType(Idx);
Offset -= Layout->getElementOffset(Idx);
IdxTy = Type::getInt32Ty(T->getContext());
return Idx;
}
ArrayType *AT = cast<ArrayType>(T);
T = AT->getElementType();
uint64_t EltSize = TD->getTypeAllocSize(T);
Idx = Offset / EltSize;
Offset -= Idx * EltSize;
IdxTy = Type::getInt64Ty(T->getContext());
return Idx;
}
void SROA::RewriteGEP(GetElementPtrInst *GEPI, AllocaInst *AI, uint64_t Offset,
SmallVector<AllocaInst*, 32> &NewElts) {
uint64_t OldOffset = Offset;
SmallVector<Value*, 8> Indices(GEPI->op_begin() + 1, GEPI->op_end());
Offset += TD->getIndexedOffset(GEPI->getPointerOperandType(), Indices);
RewriteForScalarRepl(GEPI, AI, Offset, NewElts);
Type *T = AI->getAllocatedType();
Type *IdxTy;
uint64_t OldIdx = FindElementAndOffset(T, OldOffset, IdxTy);
if (GEPI->getOperand(0) == AI)
OldIdx = ~0ULL;
T = AI->getAllocatedType();
uint64_t EltOffset = Offset;
uint64_t Idx = FindElementAndOffset(T, EltOffset, IdxTy);
if (Idx == OldIdx)
return;
Type *i32Ty = Type::getInt32Ty(AI->getContext());
SmallVector<Value*, 8> NewArgs;
NewArgs.push_back(Constant::getNullValue(i32Ty));
while (EltOffset != 0) {
uint64_t EltIdx = FindElementAndOffset(T, EltOffset, IdxTy);
NewArgs.push_back(ConstantInt::get(IdxTy, EltIdx));
}
Instruction *Val = NewElts[Idx];
if (NewArgs.size() > 1) {
Val = GetElementPtrInst::CreateInBounds(Val, NewArgs, "", GEPI);
Val->takeName(GEPI);
}
if (Val->getType() != GEPI->getType())
Val = new BitCastInst(Val, GEPI->getType(), Val->getName(), GEPI);
GEPI->replaceAllUsesWith(Val);
DeadInsts.push_back(GEPI);
}
void SROA::RewriteLifetimeIntrinsic(IntrinsicInst *II, AllocaInst *AI,
uint64_t Offset,
SmallVector<AllocaInst*, 32> &NewElts) {
ConstantInt *OldSize = cast<ConstantInt>(II->getArgOperand(0));
Type *AIType = AI->getAllocatedType();
uint64_t NewOffset = Offset;
Type *IdxTy;
uint64_t Idx = FindElementAndOffset(AIType, NewOffset, IdxTy);
IRBuilder<> Builder(II);
uint64_t Size = OldSize->getLimitedValue();
if (NewOffset) {
Value *V = Builder.CreateBitCast(NewElts[Idx], Builder.getInt8PtrTy());
V = Builder.CreateGEP(V, Builder.getInt64(NewOffset));
IdxTy = NewElts[Idx]->getAllocatedType();
uint64_t EltSize = TD->getTypeAllocSize(IdxTy) - NewOffset;
if (EltSize > Size) {
EltSize = Size;
Size = 0;
} else {
Size -= EltSize;
}
if (II->getIntrinsicID() == Intrinsic::lifetime_start)
Builder.CreateLifetimeStart(V, Builder.getInt64(EltSize));
else
Builder.CreateLifetimeEnd(V, Builder.getInt64(EltSize));
++Idx;
}
for (; Idx != NewElts.size() && Size; ++Idx) {
IdxTy = NewElts[Idx]->getAllocatedType();
uint64_t EltSize = TD->getTypeAllocSize(IdxTy);
if (EltSize > Size) {
EltSize = Size;
Size = 0;
} else {
Size -= EltSize;
}
if (II->getIntrinsicID() == Intrinsic::lifetime_start)
Builder.CreateLifetimeStart(NewElts[Idx],
Builder.getInt64(EltSize));
else
Builder.CreateLifetimeEnd(NewElts[Idx],
Builder.getInt64(EltSize));
}
DeadInsts.push_back(II);
}
void SROA::RewriteMemIntrinUserOfAlloca(MemIntrinsic *MI, Instruction *Inst,
AllocaInst *AI,
SmallVector<AllocaInst*, 32> &NewElts) {
Value *OtherPtr = 0;
unsigned MemAlignment = MI->getAlignment();
if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI)) { if (Inst == MTI->getRawDest())
OtherPtr = MTI->getRawSource();
else {
assert(Inst == MTI->getRawSource());
OtherPtr = MTI->getRawDest();
}
}
if (OtherPtr) {
unsigned AddrSpace =
cast<PointerType>(OtherPtr->getType())->getAddressSpace();
OtherPtr = OtherPtr->stripPointerCasts();
if (OtherPtr == AI || OtherPtr == NewElts[0]) {
for (SmallVector<Value*, 32>::const_iterator I = DeadInsts.begin(),
E = DeadInsts.end(); I != E; ++I)
if (*I == MI) return;
DeadInsts.push_back(MI);
return;
}
Type *NewTy =
PointerType::get(AI->getType()->getElementType(), AddrSpace);
if (OtherPtr->getType() != NewTy)
OtherPtr = new BitCastInst(OtherPtr, NewTy, OtherPtr->getName(), MI);
}
bool SROADest = MI->getRawDest() == Inst;
Constant *Zero = Constant::getNullValue(Type::getInt32Ty(MI->getContext()));
for (unsigned i = 0, e = NewElts.size(); i != e; ++i) {
Value *OtherElt = 0;
unsigned OtherEltAlign = MemAlignment;
if (OtherPtr) {
Value *Idx[2] = { Zero,
ConstantInt::get(Type::getInt32Ty(MI->getContext()), i) };
OtherElt = GetElementPtrInst::CreateInBounds(OtherPtr, Idx,
OtherPtr->getName()+"."+Twine(i),
MI);
uint64_t EltOffset;
PointerType *OtherPtrTy = cast<PointerType>(OtherPtr->getType());
Type *OtherTy = OtherPtrTy->getElementType();
if (StructType *ST = dyn_cast<StructType>(OtherTy)) {
EltOffset = TD->getStructLayout(ST)->getElementOffset(i);
} else {
Type *EltTy = cast<SequentialType>(OtherTy)->getElementType();
EltOffset = TD->getTypeAllocSize(EltTy)*i;
}
OtherEltAlign = (unsigned)MinAlign(OtherEltAlign, EltOffset);
}
Value *EltPtr = NewElts[i];
Type *EltTy = cast<PointerType>(EltPtr->getType())->getElementType();
if (EltTy->isSingleValueType()) {
if (isa<MemTransferInst>(MI)) {
if (SROADest) {
Value *Elt = new LoadInst(OtherElt, "tmp", false, OtherEltAlign, MI);
new StoreInst(Elt, EltPtr, MI);
} else {
Value *Elt = new LoadInst(EltPtr, "tmp", MI);
new StoreInst(Elt, OtherElt, false, OtherEltAlign, MI);
}
continue;
}
assert(isa<MemSetInst>(MI));
Constant *StoreVal;
if (ConstantInt *CI = dyn_cast<ConstantInt>(MI->getArgOperand(1))) {
if (CI->isZero()) {
StoreVal = Constant::getNullValue(EltTy); } else {
Type *ValTy = EltTy->getScalarType();
unsigned EltSize = TD->getTypeSizeInBits(ValTy);
APInt OneVal(EltSize, CI->getZExtValue());
APInt TotalVal(OneVal);
for (unsigned i = 0; 8*i < EltSize; ++i) {
TotalVal = TotalVal.shl(8);
TotalVal |= OneVal;
}
StoreVal = ConstantInt::get(CI->getContext(), TotalVal);
if (ValTy->isPointerTy())
StoreVal = ConstantExpr::getIntToPtr(StoreVal, ValTy);
else if (ValTy->isFloatingPointTy())
StoreVal = ConstantExpr::getBitCast(StoreVal, ValTy);
assert(StoreVal->getType() == ValTy && "Type mismatch!");
if (EltTy->isVectorTy()) {
unsigned NumElts = cast<VectorType>(EltTy)->getNumElements();
StoreVal = ConstantVector::getSplat(NumElts, StoreVal);
}
}
new StoreInst(StoreVal, EltPtr, MI);
continue;
}
}
unsigned EltSize = TD->getTypeAllocSize(EltTy);
if (!EltSize)
continue;
IRBuilder<> Builder(MI);
if (isa<MemSetInst>(MI)) {
Builder.CreateMemSet(EltPtr, MI->getArgOperand(1), EltSize,
MI->isVolatile());
} else {
assert(isa<MemTransferInst>(MI));
Value *Dst = SROADest ? EltPtr : OtherElt; Value *Src = SROADest ? OtherElt : EltPtr;
if (isa<MemCpyInst>(MI))
Builder.CreateMemCpy(Dst, Src, EltSize, OtherEltAlign,MI->isVolatile());
else
Builder.CreateMemMove(Dst, Src, EltSize,OtherEltAlign,MI->isVolatile());
}
}
DeadInsts.push_back(MI);
}
void SROA::RewriteStoreUserOfWholeAlloca(StoreInst *SI, AllocaInst *AI,
SmallVector<AllocaInst*, 32> &NewElts){
Value *SrcVal = SI->getOperand(0);
Type *AllocaEltTy = AI->getAllocatedType();
uint64_t AllocaSizeBits = TD->getTypeAllocSizeInBits(AllocaEltTy);
IRBuilder<> Builder(SI);
if (TD->getTypeSizeInBits(SrcVal->getType()) != AllocaSizeBits)
SrcVal = Builder.CreateZExt(SrcVal,
IntegerType::get(SI->getContext(), AllocaSizeBits));
DEBUG(dbgs() << "PROMOTING STORE TO WHOLE ALLOCA: " << *AI << '\n' << *SI
<< '\n');
if (StructType *EltSTy = dyn_cast<StructType>(AllocaEltTy)) {
const StructLayout *Layout = TD->getStructLayout(EltSTy);
for (unsigned i = 0, e = NewElts.size(); i != e; ++i) {
Type *FieldTy = EltSTy->getElementType(i);
uint64_t Shift = Layout->getElementOffsetInBits(i);
if (TD->isBigEndian())
Shift = AllocaSizeBits-Shift-TD->getTypeAllocSizeInBits(FieldTy);
Value *EltVal = SrcVal;
if (Shift) {
Value *ShiftVal = ConstantInt::get(EltVal->getType(), Shift);
EltVal = Builder.CreateLShr(EltVal, ShiftVal, "sroa.store.elt");
}
uint64_t FieldSizeBits = TD->getTypeSizeInBits(FieldTy);
if (FieldSizeBits == 0) continue;
if (FieldSizeBits != AllocaSizeBits)
EltVal = Builder.CreateTrunc(EltVal,
IntegerType::get(SI->getContext(), FieldSizeBits));
Value *DestField = NewElts[i];
if (EltVal->getType() == FieldTy) {
} else if (FieldTy->isFloatingPointTy() || FieldTy->isVectorTy()) {
EltVal = Builder.CreateBitCast(EltVal, FieldTy);
} else {
DestField = Builder.CreateBitCast(DestField,
PointerType::getUnqual(EltVal->getType()));
}
new StoreInst(EltVal, DestField, SI);
}
} else {
ArrayType *ATy = cast<ArrayType>(AllocaEltTy);
Type *ArrayEltTy = ATy->getElementType();
uint64_t ElementOffset = TD->getTypeAllocSizeInBits(ArrayEltTy);
uint64_t ElementSizeBits = TD->getTypeSizeInBits(ArrayEltTy);
uint64_t Shift;
if (TD->isBigEndian())
Shift = AllocaSizeBits-ElementOffset;
else
Shift = 0;
for (unsigned i = 0, e = NewElts.size(); i != e; ++i) {
if (ElementSizeBits == 0) continue;
Value *EltVal = SrcVal;
if (Shift) {
Value *ShiftVal = ConstantInt::get(EltVal->getType(), Shift);
EltVal = Builder.CreateLShr(EltVal, ShiftVal, "sroa.store.elt");
}
if (ElementSizeBits != AllocaSizeBits)
EltVal = Builder.CreateTrunc(EltVal,
IntegerType::get(SI->getContext(),
ElementSizeBits));
Value *DestField = NewElts[i];
if (EltVal->getType() == ArrayEltTy) {
} else if (ArrayEltTy->isFloatingPointTy() ||
ArrayEltTy->isVectorTy()) {
EltVal = Builder.CreateBitCast(EltVal, ArrayEltTy);
} else {
DestField = Builder.CreateBitCast(DestField,
PointerType::getUnqual(EltVal->getType()));
}
new StoreInst(EltVal, DestField, SI);
if (TD->isBigEndian())
Shift -= ElementOffset;
else
Shift += ElementOffset;
}
}
DeadInsts.push_back(SI);
}
void SROA::RewriteLoadUserOfWholeAlloca(LoadInst *LI, AllocaInst *AI,
SmallVector<AllocaInst*, 32> &NewElts) {
Type *AllocaEltTy = AI->getAllocatedType();
uint64_t AllocaSizeBits = TD->getTypeAllocSizeInBits(AllocaEltTy);
DEBUG(dbgs() << "PROMOTING LOAD OF WHOLE ALLOCA: " << *AI << '\n' << *LI
<< '\n');
const StructLayout *Layout = 0;
uint64_t ArrayEltBitOffset = 0;
if (StructType *EltSTy = dyn_cast<StructType>(AllocaEltTy)) {
Layout = TD->getStructLayout(EltSTy);
} else {
Type *ArrayEltTy = cast<ArrayType>(AllocaEltTy)->getElementType();
ArrayEltBitOffset = TD->getTypeAllocSizeInBits(ArrayEltTy);
}
Value *ResultVal =
Constant::getNullValue(IntegerType::get(LI->getContext(), AllocaSizeBits));
for (unsigned i = 0, e = NewElts.size(); i != e; ++i) {
Value *SrcField = NewElts[i];
Type *FieldTy =
cast<PointerType>(SrcField->getType())->getElementType();
uint64_t FieldSizeBits = TD->getTypeSizeInBits(FieldTy);
if (FieldSizeBits == 0) continue;
IntegerType *FieldIntTy = IntegerType::get(LI->getContext(),
FieldSizeBits);
if (!FieldTy->isIntegerTy() && !FieldTy->isFloatingPointTy() &&
!FieldTy->isVectorTy())
SrcField = new BitCastInst(SrcField,
PointerType::getUnqual(FieldIntTy),
"", LI);
SrcField = new LoadInst(SrcField, "sroa.load.elt", LI);
if (SrcField->getType() != FieldIntTy)
SrcField = new BitCastInst(SrcField, FieldIntTy, "", LI);
if (SrcField->getType() != ResultVal->getType())
SrcField = new ZExtInst(SrcField, ResultVal->getType(), "", LI);
uint64_t Shift;
if (Layout) Shift = Layout->getElementOffsetInBits(i);
else Shift = i*ArrayEltBitOffset;
if (TD->isBigEndian())
Shift = AllocaSizeBits-Shift-FieldIntTy->getBitWidth();
if (Shift) {
Value *ShiftVal = ConstantInt::get(SrcField->getType(), Shift);
SrcField = BinaryOperator::CreateShl(SrcField, ShiftVal, "", LI);
}
if (!isa<Constant>(ResultVal) ||
!cast<Constant>(ResultVal)->isNullValue())
ResultVal = BinaryOperator::CreateOr(SrcField, ResultVal, "", LI);
else
ResultVal = SrcField;
}
if (TD->getTypeSizeInBits(LI->getType()) != AllocaSizeBits)
ResultVal = new TruncInst(ResultVal, LI->getType(), "", LI);
LI->replaceAllUsesWith(ResultVal);
DeadInsts.push_back(LI);
}
static bool HasPadding(Type *Ty, const TargetData &TD) {
if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
Ty = ATy->getElementType();
return TD.getTypeSizeInBits(Ty) != TD.getTypeAllocSizeInBits(Ty);
}
StructType *STy = cast<StructType>(Ty);
const StructLayout *SL = TD.getStructLayout(STy);
unsigned PrevFieldBitOffset = 0;
for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
unsigned FieldBitOffset = SL->getElementOffsetInBits(i);
if (i) {
unsigned PrevFieldEnd =
PrevFieldBitOffset+TD.getTypeSizeInBits(STy->getElementType(i-1));
if (PrevFieldEnd < FieldBitOffset)
return true;
}
PrevFieldBitOffset = FieldBitOffset;
}
if (unsigned EltCount = STy->getNumElements()) {
unsigned PrevFieldEnd = PrevFieldBitOffset +
TD.getTypeSizeInBits(STy->getElementType(EltCount-1));
if (PrevFieldEnd < SL->getSizeInBits())
return true;
}
return false;
}
bool SROA::isSafeAllocaToScalarRepl(AllocaInst *AI) {
AllocaInfo Info(AI);
isSafeForScalarRepl(AI, 0, Info);
if (Info.isUnsafe) {
DEBUG(dbgs() << "Cannot transform: " << *AI << '\n');
return false;
}
if (Info.isMemCpySrc && Info.isMemCpyDst &&
HasPadding(AI->getAllocatedType(), *TD))
return false;
if (!Info.hasSubelementAccess && Info.hasALoadOrStore) {
if (StructType *ST = dyn_cast<StructType>(AI->getAllocatedType())) {
if (ST->getNumElements() > 1) return false;
} else {
if (cast<ArrayType>(AI->getAllocatedType())->getNumElements() > 1)
return false;
}
}
return true;
}
static bool PointsToConstantGlobal(Value *V) {
if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
return GV->isConstant();
if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
if (CE->getOpcode() == Instruction::BitCast ||
CE->getOpcode() == Instruction::GetElementPtr)
return PointsToConstantGlobal(CE->getOperand(0));
return false;
}
static bool
isOnlyCopiedFromConstantGlobal(Value *V, MemTransferInst *&TheCopy,
bool isOffset,
SmallVector<Instruction *, 4> &LifetimeMarkers) {
for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI!=E; ++UI) {
User *U = cast<Instruction>(*UI);
if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
if (!LI->isSimple()) return false;
continue;
}
if (BitCastInst *BCI = dyn_cast<BitCastInst>(U)) {
if (!isOnlyCopiedFromConstantGlobal(BCI, TheCopy, isOffset,
LifetimeMarkers))
return false;
continue;
}
if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) {
if (!isOnlyCopiedFromConstantGlobal(GEP, TheCopy,
isOffset || !GEP->hasAllZeroIndices(),
LifetimeMarkers))
return false;
continue;
}
if (CallSite CS = U) {
if (CS.isCallee(UI))
continue;
unsigned ArgNo = CS.getArgumentNo(UI);
if (CS.onlyReadsMemory() &&
(CS.getInstruction()->use_empty() || CS.doesNotCapture(ArgNo)))
continue;
if (CS.isByValArgument(ArgNo))
continue;
}
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(U)) {
if (II->getIntrinsicID() == Intrinsic::lifetime_start ||
II->getIntrinsicID() == Intrinsic::lifetime_end) {
assert(II->use_empty() && "Lifetime markers have no result to use!");
LifetimeMarkers.push_back(II);
continue;
}
}
MemTransferInst *MI = dyn_cast<MemTransferInst>(U);
if (MI == 0)
return false;
if (UI.getOperandNo() == 1) {
if (MI->isVolatile()) return false;
continue;
}
if (TheCopy) return false;
if (isOffset) return false;
if (UI.getOperandNo() != 0) return false;
if (!PointsToConstantGlobal(MI->getSource()))
return false;
TheCopy = MI;
}
return true;
}
MemTransferInst *
SROA::isOnlyCopiedFromConstantGlobal(AllocaInst *AI,
SmallVector<Instruction*, 4> &ToDelete) {
MemTransferInst *TheCopy = 0;
if (::isOnlyCopiedFromConstantGlobal(AI, TheCopy, false, ToDelete))
return TheCopy;
return 0;
}