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/Pass.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Transforms/Utils/PromoteMemToReg.h"
#include "llvm/Transforms/Utils/Local.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/SmallVector.h"
#include "llvm/ADT/Statistic.h"
using namespace llvm;
STATISTIC(NumReplaced, "Number of allocas broken up");
STATISTIC(NumPromoted, "Number of allocas promoted");
STATISTIC(NumConverted, "Number of aggregates converted to scalar");
STATISTIC(NumGlobals, "Number of allocas copied from constant global");
namespace {
struct SROA : public FunctionPass {
static char ID; explicit SROA(signed T = -1) : FunctionPass(&ID) {
if (T == -1)
SRThreshold = 128;
else
SRThreshold = T;
}
bool runOnFunction(Function &F);
bool performScalarRepl(Function &F);
bool performPromotion(Function &F);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequired<DominatorTree>();
AU.addRequired<DominanceFrontier>();
AU.setPreservesCFG();
}
private:
TargetData *TD;
SmallVector<Value*, 32> DeadInsts;
struct AllocaInfo {
bool isUnsafe : 1;
bool isMemCpySrc : 1;
bool isMemCpyDst : 1;
AllocaInfo()
: isUnsafe(false), isMemCpySrc(false), isMemCpyDst(false) {}
};
unsigned SRThreshold;
void MarkUnsafe(AllocaInfo &I) { I.isUnsafe = true; }
bool isSafeAllocaToScalarRepl(AllocaInst *AI);
void isSafeForScalarRepl(Instruction *I, AllocaInst *AI, uint64_t Offset,
AllocaInfo &Info);
void isSafeGEP(GetElementPtrInst *GEPI, AllocaInst *AI, uint64_t &Offset,
AllocaInfo &Info);
void isSafeMemAccess(AllocaInst *AI, uint64_t Offset, uint64_t MemSize,
const Type *MemOpType, bool isStore, AllocaInfo &Info);
bool TypeHasComponent(const Type *T, uint64_t Offset, uint64_t Size);
uint64_t FindElementAndOffset(const Type *&T, uint64_t &Offset,
const Type *&IdxTy);
void DoScalarReplacement(AllocaInst *AI,
std::vector<AllocaInst*> &WorkList);
void DeleteDeadInstructions();
AllocaInst *AddNewAlloca(Function &F, const Type *Ty, AllocaInst *Base);
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 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);
bool CanConvertToScalar(Value *V, bool &IsNotTrivial, const Type *&VecTy,
bool &SawVec, uint64_t Offset, unsigned AllocaSize);
void ConvertUsesToScalar(Value *Ptr, AllocaInst *NewAI, uint64_t Offset);
Value *ConvertScalar_ExtractValue(Value *NV, const Type *ToType,
uint64_t Offset, IRBuilder<> &Builder);
Value *ConvertScalar_InsertValue(Value *StoredVal, Value *ExistingVal,
uint64_t Offset, IRBuilder<> &Builder);
static Instruction *isOnlyCopiedFromConstantGlobal(AllocaInst *AI);
};
}
char SROA::ID = 0;
static RegisterPass<SROA> X("scalarrepl", "Scalar Replacement of Aggregates");
FunctionPass *llvm::createScalarReplAggregatesPass(signed int Threshold) {
return new SROA(Threshold);
}
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;
}
bool SROA::performPromotion(Function &F) {
std::vector<AllocaInst*> Allocas;
DominatorTree &DT = getAnalysis<DominatorTree>();
DominanceFrontier &DF = getAnalysis<DominanceFrontier>();
BasicBlock &BB = F.getEntryBlock();
bool Changed = false;
while (1) {
Allocas.clear();
for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I)
if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) if (isAllocaPromotable(AI))
Allocas.push_back(AI);
if (Allocas.empty()) break;
PromoteMemToReg(Allocas, DT, DF);
NumPromoted += Allocas.size();
Changed = true;
}
return Changed;
}
static bool ShouldAttemptScalarRepl(AllocaInst *AI) {
const Type *T = AI->getAllocatedType();
if (const StructType *ST = dyn_cast<StructType>(T))
return ST->getNumElements() <= 32;
if (const ArrayType *AT = dyn_cast<ArrayType>(T))
return AT->getNumElements() <= 8;
return false;
}
static bool IsVerbotenVectorType(const VectorType *VTy) {
switch (VTy->getNumElements()) {
default: return false;
case 1: return VTy->getElementType()->isIntegerTy(64);
case 2: return VTy->getElementType()->isIntegerTy(32) ||
VTy->getElementType()->isFloatTy();
case 4: return VTy->getElementType()->isIntegerTy(16);
case 8: return VTy->getElementType()->isIntegerTy(8);
}
}
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();
continue;
}
if (AI->isArrayAllocation() || !AI->getAllocatedType()->isSized())
continue;
if (Instruction *TheCopy = isOnlyCopiedFromConstantGlobal(AI)) {
DEBUG(dbgs() << "Found alloca equal to global: " << *AI << '\n');
DEBUG(dbgs() << " memcpy = " << *TheCopy << '\n');
Constant *TheSrc = cast<Constant>(TheCopy->getOperand(2));
AI->replaceAllUsesWith(ConstantExpr::getBitCast(TheSrc, AI->getType()));
TheCopy->eraseFromParent(); AI->eraseFromParent();
++NumGlobals;
Changed = true;
continue;
}
uint64_t AllocaSize = TD->getTypeAllocSize(AI->getAllocatedType());
if (AllocaSize == 0) continue;
if (ShouldAttemptScalarRepl(AI) && isSafeAllocaToScalarRepl(AI)) {
DoScalarReplacement(AI, WorkList);
Changed = true;
continue;
}
if (AllocaSize > SRThreshold) continue;
bool IsNotTrivial = false;
const Type *VectorTy = 0;
bool HadAVector = false;
if (CanConvertToScalar(AI, IsNotTrivial, VectorTy, HadAVector,
0, unsigned(AllocaSize)) && IsNotTrivial) {
AllocaInst *NewAI;
if (VectorTy && VectorTy->isVectorTy() && HadAVector &&
!IsVerbotenVectorType(cast<VectorType>(VectorTy))) {
DEBUG(dbgs() << "CONVERT TO VECTOR: " << *AI << "\n TYPE = "
<< *VectorTy << '\n');
NewAI = new AllocaInst(VectorTy, 0, "", AI->getParent()->begin());
ConvertUsesToScalar(AI, NewAI, 0);
} else {
DEBUG(dbgs() << "CONVERT TO SCALAR INTEGER: " << *AI << "\n");
const Type *NewTy = IntegerType::get(AI->getContext(), AllocaSize*8);
NewAI = new AllocaInst(NewTy, 0, "", AI->getParent()->begin());
ConvertUsesToScalar(AI, NewAI, 0);
}
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 (const 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 {
const ArrayType *AT = cast<ArrayType>(AI->getAllocatedType());
ElementAllocas.reserve(AT->getNumElements());
const 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, AllocaInst *AI, 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, AI, Offset, Info);
} else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) {
uint64_t GEPOffset = Offset;
isSafeGEP(GEPI, AI, GEPOffset, Info);
if (!Info.isUnsafe)
isSafeForScalarRepl(GEPI, AI, GEPOffset, Info);
} else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(UI)) {
ConstantInt *Length = dyn_cast<ConstantInt>(MI->getLength());
if (Length)
isSafeMemAccess(AI, Offset, Length->getZExtValue(), 0,
UI.getOperandNo() == 1, Info);
else
MarkUnsafe(Info);
} else if (LoadInst *LI = dyn_cast<LoadInst>(User)) {
if (!LI->isVolatile()) {
const Type *LIType = LI->getType();
isSafeMemAccess(AI, Offset, TD->getTypeAllocSize(LIType),
LIType, false, Info);
} else
MarkUnsafe(Info);
} else if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
if (!SI->isVolatile() && SI->getOperand(0) != I) {
const Type *SIType = SI->getOperand(0)->getType();
isSafeMemAccess(AI, Offset, TD->getTypeAllocSize(SIType),
SIType, true, Info);
} else
MarkUnsafe(Info);
} else {
DEBUG(errs() << " Transformation preventing inst: " << *User << '\n');
MarkUnsafe(Info);
}
if (Info.isUnsafe) return;
}
}
void SROA::isSafeGEP(GetElementPtrInst *GEPI, AllocaInst *AI,
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);
}
SmallVector<Value*, 8> Indices(GEPI->op_begin() + 1, GEPI->op_end());
Offset += TD->getIndexedOffset(GEPI->getPointerOperandType(),
&Indices[0], Indices.size());
if (!TypeHasComponent(AI->getAllocatedType(), Offset, 0))
MarkUnsafe(Info);
}
void SROA::isSafeMemAccess(AllocaInst *AI, uint64_t Offset, uint64_t MemSize,
const Type *MemOpType, bool isStore,
AllocaInfo &Info) {
if (Offset == 0 && MemSize == TD->getTypeAllocSize(AI->getAllocatedType())) {
bool UsesAggregateType = (MemOpType == AI->getAllocatedType());
if (!MemOpType || MemOpType->isIntegerTy() || UsesAggregateType) {
if (!UsesAggregateType) {
if (isStore)
Info.isMemCpyDst = true;
else
Info.isMemCpySrc = true;
}
return;
}
}
const Type *T = AI->getAllocatedType();
if (TypeHasComponent(T, Offset, MemSize))
return;
return MarkUnsafe(Info);
}
bool SROA::TypeHasComponent(const Type *T, uint64_t Offset, uint64_t Size) {
const Type *EltTy;
uint64_t EltSize;
if (const 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 (const 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; ++UI) {
Instruction *User = cast<Instruction>(*UI);
if (BitCastInst *BC = dyn_cast<BitCastInst>(User)) {
RewriteBitCast(BC, AI, Offset, NewElts);
} else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) {
RewriteGEP(GEPI, AI, Offset, NewElts);
} else 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);
} else if (LoadInst *LI = dyn_cast<LoadInst>(User)) {
const Type *LIType = LI->getType();
if (LIType == AI->getAllocatedType()) {
Value *Insert = UndefValue::get(LIType);
for (unsigned i = 0, e = NewElts.size(); i != e; ++i) {
Value *Load = new LoadInst(NewElts[i], "load", LI);
Insert = InsertValueInst::Create(Insert, Load, i, "insert", LI);
}
LI->replaceAllUsesWith(Insert);
DeadInsts.push_back(LI);
} else if (LIType->isIntegerTy() &&
TD->getTypeAllocSize(LIType) ==
TD->getTypeAllocSize(AI->getAllocatedType())) {
RewriteLoadUserOfWholeAlloca(LI, AI, NewElts);
}
} else if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
Value *Val = SI->getOperand(0);
const Type *SIType = Val->getType();
if (SIType == AI->getAllocatedType()) {
for (unsigned i = 0, e = NewElts.size(); i != e; ++i) {
Value *Extract = ExtractValueInst::Create(Val, i, Val->getName(), SI);
new StoreInst(Extract, NewElts[i], SI);
}
DeadInsts.push_back(SI);
} else if (SIType->isIntegerTy() &&
TD->getTypeAllocSize(SIType) ==
TD->getTypeAllocSize(AI->getAllocatedType())) {
RewriteStoreUserOfWholeAlloca(SI, AI, NewElts);
}
}
}
}
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;
Instruction *Val = NewElts[0];
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(const Type *&T, uint64_t &Offset,
const Type *&IdxTy) {
uint64_t Idx = 0;
if (const 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;
}
const 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[0], Indices.size());
RewriteForScalarRepl(GEPI, AI, Offset, NewElts);
const Type *T = AI->getAllocatedType();
const 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;
const 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.begin(),
NewArgs.end(), "", 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::RewriteMemIntrinUserOfAlloca(MemIntrinsic *MI, Instruction *Inst,
AllocaInst *AI,
SmallVector<AllocaInst*, 32> &NewElts) {
Value *OtherPtr = 0;
LLVMContext &Context = MI->getContext();
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;
}
const Type *NewTy =
PointerType::get(AI->getType()->getElementType(), AddrSpace);
if (OtherPtr->getType() != NewTy)
OtherPtr = new BitCastInst(OtherPtr, NewTy, OtherPtr->getName(), MI);
}
Value *TheFn = MI->getOperand(0);
const Type *BytePtrTy = MI->getRawDest()->getType();
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, Idx + 2,
OtherPtr->getName()+"."+Twine(i),
MI);
uint64_t EltOffset;
const PointerType *OtherPtrTy = cast<PointerType>(OtherPtr->getType());
if (const StructType *ST =
dyn_cast<StructType>(OtherPtrTy->getElementType())) {
EltOffset = TD->getStructLayout(ST)->getElementOffset(i);
} else {
const Type *EltTy =
cast<SequentialType>(OtherPtr->getType())->getElementType();
EltOffset = TD->getTypeAllocSize(EltTy)*i;
}
OtherEltAlign = (unsigned)MinAlign(OtherEltAlign, EltOffset);
}
Value *EltPtr = NewElts[i];
const 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->getOperand(2))) {
if (CI->isZero()) {
StoreVal = Constant::getNullValue(EltTy); } else {
const 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(Context, 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 != ValTy) {
unsigned NumElts = cast<VectorType>(ValTy)->getNumElements();
SmallVector<Constant*, 16> Elts(NumElts, StoreVal);
StoreVal = ConstantVector::get(&Elts[0], NumElts);
}
}
new StoreInst(StoreVal, EltPtr, MI);
continue;
}
}
if (EltPtr->getType() != BytePtrTy)
EltPtr = new BitCastInst(EltPtr, BytePtrTy, EltPtr->getName(), MI);
if (OtherElt && OtherElt->getType() != BytePtrTy) {
const PointerType* OtherPTy = cast<PointerType>(OtherElt->getType());
const PointerType* PTy = cast<PointerType>(BytePtrTy);
if (OtherPTy->getElementType() != PTy->getElementType()) {
Type *NewOtherPTy = PointerType::get(PTy->getElementType(),
OtherPTy->getAddressSpace());
OtherElt = new BitCastInst(OtherElt, NewOtherPTy,
OtherElt->getNameStr(), MI);
}
}
unsigned EltSize = TD->getTypeAllocSize(EltTy);
if (isa<MemTransferInst>(MI)) {
Value *Ops[] = {
SROADest ? EltPtr : OtherElt, SROADest ? OtherElt : EltPtr, ConstantInt::get(MI->getOperand(3)->getType(), EltSize), ConstantInt::get(Type::getInt32Ty(MI->getContext()), OtherEltAlign),
MI->getVolatileCst()
};
const Type *Tys[] = { Ops[0]->getType(), Ops[1]->getType(),
Ops[2]->getType() };
Module *M = MI->getParent()->getParent()->getParent();
TheFn = Intrinsic::getDeclaration(M, MI->getIntrinsicID(), Tys, 3);
CallInst::Create(TheFn, Ops, Ops + 5, "", MI);
} else {
assert(isa<MemSetInst>(MI));
Value *Ops[] = {
EltPtr, MI->getOperand(2), ConstantInt::get(MI->getOperand(3)->getType(), EltSize), Zero, ConstantInt::get(Type::getInt1Ty(MI->getContext()), 0) };
const Type *Tys[] = { Ops[0]->getType(), Ops[2]->getType() };
Module *M = MI->getParent()->getParent()->getParent();
TheFn = Intrinsic::getDeclaration(M, Intrinsic::memset, Tys, 2);
CallInst::Create(TheFn, Ops, Ops + 5, "", MI);
}
}
DeadInsts.push_back(MI);
}
void SROA::RewriteStoreUserOfWholeAlloca(StoreInst *SI, AllocaInst *AI,
SmallVector<AllocaInst*, 32> &NewElts){
Value *SrcVal = SI->getOperand(0);
const Type *AllocaEltTy = AI->getAllocatedType();
uint64_t AllocaSizeBits = TD->getTypeAllocSizeInBits(AllocaEltTy);
if (TD->getTypeSizeInBits(SrcVal->getType()) != AllocaSizeBits)
SrcVal = new ZExtInst(SrcVal,
IntegerType::get(SI->getContext(), AllocaSizeBits),
"", SI);
DEBUG(dbgs() << "PROMOTING STORE TO WHOLE ALLOCA: " << *AI << '\n' << *SI
<< '\n');
if (const StructType *EltSTy = dyn_cast<StructType>(AllocaEltTy)) {
const StructLayout *Layout = TD->getStructLayout(EltSTy);
for (unsigned i = 0, e = NewElts.size(); i != e; ++i) {
const 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 = BinaryOperator::CreateLShr(EltVal, ShiftVal,
"sroa.store.elt", SI);
}
uint64_t FieldSizeBits = TD->getTypeSizeInBits(FieldTy);
if (FieldSizeBits == 0) continue;
if (FieldSizeBits != AllocaSizeBits)
EltVal = new TruncInst(EltVal,
IntegerType::get(SI->getContext(), FieldSizeBits),
"", SI);
Value *DestField = NewElts[i];
if (EltVal->getType() == FieldTy) {
} else if (FieldTy->isFloatingPointTy() || FieldTy->isVectorTy()) {
EltVal = new BitCastInst(EltVal, FieldTy, "", SI);
} else {
DestField = new BitCastInst(DestField,
PointerType::getUnqual(EltVal->getType()),
"", SI);
}
new StoreInst(EltVal, DestField, SI);
}
} else {
const ArrayType *ATy = cast<ArrayType>(AllocaEltTy);
const 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 = BinaryOperator::CreateLShr(EltVal, ShiftVal,
"sroa.store.elt", SI);
}
if (ElementSizeBits != AllocaSizeBits)
EltVal = new TruncInst(EltVal,
IntegerType::get(SI->getContext(),
ElementSizeBits),"",SI);
Value *DestField = NewElts[i];
if (EltVal->getType() == ArrayEltTy) {
} else if (ArrayEltTy->isFloatingPointTy() ||
ArrayEltTy->isVectorTy()) {
EltVal = new BitCastInst(EltVal, ArrayEltTy, "", SI);
} else {
DestField = new BitCastInst(DestField,
PointerType::getUnqual(EltVal->getType()),
"", SI);
}
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) {
const 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 (const StructType *EltSTy = dyn_cast<StructType>(AllocaEltTy)) {
Layout = TD->getStructLayout(EltSTy);
} else {
const 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];
const Type *FieldTy =
cast<PointerType>(SrcField->getType())->getElementType();
uint64_t FieldSizeBits = TD->getTypeSizeInBits(FieldTy);
if (FieldSizeBits == 0) continue;
const 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);
}
ResultVal = BinaryOperator::CreateOr(SrcField, ResultVal, "", LI);
}
if (TD->getTypeSizeInBits(LI->getType()) != AllocaSizeBits)
ResultVal = new TruncInst(ResultVal, LI->getType(), "", LI);
LI->replaceAllUsesWith(ResultVal);
DeadInsts.push_back(LI);
}
static bool HasPadding(const Type *Ty, const TargetData &TD) {
if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty))
return HasPadding(ATy->getElementType(), TD);
if (const VectorType *VTy = dyn_cast<VectorType>(Ty))
return HasPadding(VTy->getElementType(), TD);
if (const StructType *STy = dyn_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 (HasPadding(STy->getElementType(i), TD))
return true;
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 TD.getTypeSizeInBits(Ty) != TD.getTypeAllocSizeInBits(Ty);
}
bool SROA::isSafeAllocaToScalarRepl(AllocaInst *AI) {
AllocaInfo Info;
isSafeForScalarRepl(AI, 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;
return true;
}
static void MergeInType(const Type *In, uint64_t Offset, const Type *&VecTy,
unsigned AllocaSize, const TargetData &TD,
LLVMContext &Context) {
if (VecTy != Type::getVoidTy(Context)) {
if (const VectorType *VInTy = dyn_cast<VectorType>(In)) {
if (VInTy->getBitWidth()/8 == AllocaSize && Offset == 0) {
if (VecTy == 0)
VecTy = VInTy;
return;
}
} else if (In->isFloatTy() || In->isDoubleTy() ||
(In->isIntegerTy() && In->getPrimitiveSizeInBits() >= 8 &&
isPowerOf2_32(In->getPrimitiveSizeInBits()))) {
unsigned EltSize = In->getPrimitiveSizeInBits()/8;
if (Offset % EltSize == 0 &&
AllocaSize % EltSize == 0 &&
(VecTy == 0 ||
cast<VectorType>(VecTy)->getElementType()
->getPrimitiveSizeInBits()/8 == EltSize)) {
if (VecTy == 0)
VecTy = VectorType::get(In, AllocaSize/EltSize);
return;
}
}
}
VecTy = Type::getVoidTy(Context);
}
bool SROA::CanConvertToScalar(Value *V, bool &IsNotTrivial, const Type *&VecTy,
bool &SawVec, uint64_t Offset,
unsigned AllocaSize) {
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->isVolatile())
return false;
MergeInType(LI->getType(), Offset, VecTy,
AllocaSize, *TD, V->getContext());
SawVec |= LI->getType()->isVectorTy();
continue;
}
if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
if (SI->getOperand(0) == V || SI->isVolatile()) return 0;
MergeInType(SI->getOperand(0)->getType(), Offset,
VecTy, AllocaSize, *TD, V->getContext());
SawVec |= SI->getOperand(0)->getType()->isVectorTy();
continue;
}
if (BitCastInst *BCI = dyn_cast<BitCastInst>(User)) {
if (!CanConvertToScalar(BCI, IsNotTrivial, VecTy, SawVec, Offset,
AllocaSize))
return false;
IsNotTrivial = true;
continue;
}
if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(User)) {
if (!GEP->hasAllConstantIndices())
return false;
SmallVector<Value*, 8> Indices(GEP->op_begin()+1, GEP->op_end());
uint64_t GEPOffset = TD->getIndexedOffset(GEP->getPointerOperandType(),
&Indices[0], Indices.size());
if (!CanConvertToScalar(GEP, IsNotTrivial, VecTy, SawVec,Offset+GEPOffset,
AllocaSize))
return false;
IsNotTrivial = true;
continue;
}
if (MemSetInst *MSI = dyn_cast<MemSetInst>(User)) {
if (isa<ConstantInt>(MSI->getValue()) &&
isa<ConstantInt>(MSI->getLength())) {
IsNotTrivial = true;
continue;
}
}
if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(User)) {
if (ConstantInt *Len = dyn_cast<ConstantInt>(MTI->getLength()))
if (Len->getZExtValue() == AllocaSize && Offset == 0) {
IsNotTrivial = true;
continue;
}
}
return false;
}
return true;
}
void SROA::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[0], Indices.size());
ConvertUsesToScalar(GEP, NewAI, Offset+GEPOffset*8);
GEP->eraseFromParent();
continue;
}
IRBuilder<> Builder(User->getParent(), User);
if (LoadInst *LI = dyn_cast<LoadInst>(User)) {
Value *LoadedVal = Builder.CreateLoad(NewAI, "tmp");
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!");
unsigned NumBytes = cast<ConstantInt>(MSI->getLength())->getZExtValue();
if (NumBytes != 0) {
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>(Ptr->getUnderlyingObject(0));
if (MTI->getSource()->getUnderlyingObject(0) != OrigAI) {
assert(MTI->getRawDest() == Ptr && "Neither use is of pointer?");
Value *SrcPtr = MTI->getSource();
SrcPtr = Builder.CreateBitCast(SrcPtr, NewAI->getType());
LoadInst *SrcVal = Builder.CreateLoad(SrcPtr, "srcval");
SrcVal->setAlignment(MTI->getAlignment());
Builder.CreateStore(SrcVal, NewAI);
} else if (MTI->getDest()->getUnderlyingObject(0) != OrigAI) {
assert(MTI->getRawSource() == Ptr && "Neither use is of pointer?");
LoadInst *SrcVal = Builder.CreateLoad(NewAI, "srcval");
Value *DstPtr = Builder.CreateBitCast(MTI->getDest(), NewAI->getType());
StoreInst *NewStore = Builder.CreateStore(SrcVal, DstPtr);
NewStore->setAlignment(MTI->getAlignment());
} else {
}
MTI->eraseFromParent();
continue;
}
llvm_unreachable("Unsupported operation!");
}
}
Value *SROA::ConvertScalar_ExtractValue(Value *FromVal, const Type *ToType,
uint64_t Offset, IRBuilder<> &Builder) {
if (FromVal->getType() == ToType && Offset == 0)
return FromVal;
if (const VectorType *VTy = dyn_cast<VectorType>(FromVal->getType())) {
if (ToType->isVectorTy())
return Builder.CreateBitCast(FromVal, ToType, "tmp");
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, ConstantInt::get(
Type::getInt32Ty(FromVal->getContext()), Elt), "tmp");
if (V->getType() != ToType)
V = Builder.CreateBitCast(V, ToType, "tmp");
return V;
}
if (const 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, "tmp");
}
return Res;
}
if (const 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, "tmp");
}
return Res;
}
const 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), "tmp");
else if (ShAmt < 0 && (unsigned)-ShAmt < NTy->getBitWidth())
FromVal = Builder.CreateShl(FromVal,
ConstantInt::get(FromVal->getType(),
-ShAmt), "tmp");
unsigned LIBitWidth = TD->getTypeSizeInBits(ToType);
if (LIBitWidth < NTy->getBitWidth())
FromVal =
Builder.CreateTrunc(FromVal, IntegerType::get(FromVal->getContext(),
LIBitWidth), "tmp");
else if (LIBitWidth > NTy->getBitWidth())
FromVal =
Builder.CreateZExt(FromVal, IntegerType::get(FromVal->getContext(),
LIBitWidth), "tmp");
if (ToType->isIntegerTy()) {
} else if (ToType->isFloatingPointTy() || ToType->isVectorTy()) {
FromVal = Builder.CreateBitCast(FromVal, ToType, "tmp");
} else {
FromVal = Builder.CreateIntToPtr(FromVal, ToType, "tmp");
}
assert(FromVal->getType() == ToType && "Didn't convert right?");
return FromVal;
}
Value *SROA::ConvertScalar_InsertValue(Value *SV, Value *Old,
uint64_t Offset, IRBuilder<> &Builder) {
const Type *AllocaType = Old->getType();
LLVMContext &Context = Old->getContext();
if (const 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, "tmp");
uint64_t EltSize = TD->getTypeAllocSizeInBits(VTy->getElementType());
unsigned Elt = Offset/EltSize;
if (SV->getType() != VTy->getElementType())
SV = Builder.CreateBitCast(SV, VTy->getElementType(), "tmp");
SV = Builder.CreateInsertElement(Old, SV,
ConstantInt::get(Type::getInt32Ty(SV->getContext()), Elt),
"tmp");
return SV;
}
if (const 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, "tmp");
Old = ConvertScalar_InsertValue(Elt, Old,
Offset+Layout.getElementOffsetInBits(i),
Builder);
}
return Old;
}
if (const 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, "tmp");
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), "tmp");
else if (SV->getType()->isPointerTy())
SV = Builder.CreatePtrToInt(SV, TD->getIntPtrType(SV->getContext()), "tmp");
if (SV->getType() != AllocaType) {
if (SV->getType()->getPrimitiveSizeInBits() <
AllocaType->getPrimitiveSizeInBits())
SV = Builder.CreateZExt(SV, AllocaType, "tmp");
else {
SV = Builder.CreateTrunc(SV, AllocaType, "tmp");
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), "tmp");
Mask <<= ShAmt;
} else if (ShAmt < 0 && (unsigned)-ShAmt < DestWidth) {
SV = Builder.CreateLShr(SV, ConstantInt::get(SV->getType(),
-ShAmt), "tmp");
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;
}
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, Instruction *&TheCopy,
bool isOffset) {
for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI!=E; ++UI) {
if (LoadInst *LI = dyn_cast<LoadInst>(*UI))
if (!LI->isVolatile())
continue;
if (BitCastInst *BCI = dyn_cast<BitCastInst>(*UI)) {
if (!isOnlyCopiedFromConstantGlobal(BCI, TheCopy, isOffset))
return false;
continue;
}
if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(*UI)) {
if (!isOnlyCopiedFromConstantGlobal(GEP, TheCopy,
isOffset || !GEP->hasAllZeroIndices()))
return false;
continue;
}
if (!isa<MemTransferInst>(*UI))
return false;
if (TheCopy) return false;
if (isOffset) return false;
if (UI.getOperandNo() != 1) return false;
MemIntrinsic *MI = cast<MemIntrinsic>(*UI);
if (!PointsToConstantGlobal(MI->getOperand(2)))
return false;
TheCopy = MI;
}
return true;
}
Instruction *SROA::isOnlyCopiedFromConstantGlobal(AllocaInst *AI) {
Instruction *TheCopy = 0;
if (::isOnlyCopiedFromConstantGlobal(AI, TheCopy, false))
return TheCopy;
return 0;
}