InstCombineLoadStoreAlloca.cpp [plain text]
#include "InstCombine.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
using namespace llvm;
STATISTIC(NumDeadStore, "Number of dead stores eliminated");
STATISTIC(NumGlobalCopies, "Number of allocas copied from constant global");
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,
SmallVectorImpl<Instruction *> &ToDelete,
bool IsOffset = false) {
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, ToDelete, IsOffset))
return false;
continue;
}
if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) {
if (!isOnlyCopiedFromConstantGlobal(GEP, TheCopy, ToDelete,
IsOffset || !GEP->hasAllZeroIndices()))
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!");
ToDelete.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;
}
static MemTransferInst *
isOnlyCopiedFromConstantGlobal(AllocaInst *AI,
SmallVectorImpl<Instruction *> &ToDelete) {
MemTransferInst *TheCopy = 0;
if (isOnlyCopiedFromConstantGlobal(AI, TheCopy, ToDelete))
return TheCopy;
return 0;
}
Instruction *InstCombiner::visitAllocaInst(AllocaInst &AI) {
if (TD) {
Type *IntPtrTy = TD->getIntPtrType(AI.getContext());
if (AI.getArraySize()->getType() != IntPtrTy) {
Value *V = Builder->CreateIntCast(AI.getArraySize(),
IntPtrTy, false);
AI.setOperand(0, V);
return &AI;
}
}
if (AI.isArrayAllocation()) { if (const ConstantInt *C = dyn_cast<ConstantInt>(AI.getArraySize())) {
Type *NewTy =
ArrayType::get(AI.getAllocatedType(), C->getZExtValue());
AllocaInst *New = Builder->CreateAlloca(NewTy, 0, AI.getName());
New->setAlignment(AI.getAlignment());
BasicBlock::iterator It = New;
while (isa<AllocaInst>(*It) || isa<DbgInfoIntrinsic>(*It)) ++It;
Value *NullIdx =Constant::getNullValue(Type::getInt32Ty(AI.getContext()));
Value *Idx[2];
Idx[0] = NullIdx;
Idx[1] = NullIdx;
Instruction *GEP =
GetElementPtrInst::CreateInBounds(New, Idx, New->getName()+".sub");
InsertNewInstBefore(GEP, *It);
return ReplaceInstUsesWith(AI, GEP);
} else if (isa<UndefValue>(AI.getArraySize())) {
return ReplaceInstUsesWith(AI, Constant::getNullValue(AI.getType()));
}
}
if (TD && AI.getAllocatedType()->isSized()) {
if (AI.getAlignment() == 0)
AI.setAlignment(TD->getPrefTypeAlignment(AI.getAllocatedType()));
if (TD->getTypeAllocSize(AI.getAllocatedType()) == 0) {
if (AI.isArrayAllocation()) {
AI.setOperand(0, ConstantInt::get(AI.getArraySize()->getType(), 1));
return &AI;
}
BasicBlock &EntryBlock = AI.getParent()->getParent()->getEntryBlock();
Instruction *FirstInst = EntryBlock.getFirstNonPHIOrDbg();
if (FirstInst != &AI) {
AllocaInst *EntryAI = dyn_cast<AllocaInst>(FirstInst);
if (!EntryAI || !EntryAI->getAllocatedType()->isSized() ||
TD->getTypeAllocSize(EntryAI->getAllocatedType()) != 0) {
AI.moveBefore(FirstInst);
return &AI;
}
if (EntryAI->getAlignment() == 0)
EntryAI->setAlignment(
TD->getPrefTypeAlignment(EntryAI->getAllocatedType()));
unsigned MaxAlign = std::max(EntryAI->getAlignment(),
AI.getAlignment());
EntryAI->setAlignment(MaxAlign);
if (AI.getType() != EntryAI->getType())
return new BitCastInst(EntryAI, AI.getType());
return ReplaceInstUsesWith(AI, EntryAI);
}
}
}
if (AI.getAlignment()) {
SmallVector<Instruction *, 4> ToDelete;
if (MemTransferInst *Copy = isOnlyCopiedFromConstantGlobal(&AI, ToDelete)) {
unsigned SourceAlign = getOrEnforceKnownAlignment(Copy->getSource(),
AI.getAlignment(), TD);
if (AI.getAlignment() <= SourceAlign) {
DEBUG(dbgs() << "Found alloca equal to global: " << AI << '\n');
DEBUG(dbgs() << " memcpy = " << *Copy << '\n');
for (unsigned i = 0, e = ToDelete.size(); i != e; ++i)
EraseInstFromFunction(*ToDelete[i]);
Constant *TheSrc = cast<Constant>(Copy->getSource());
Instruction *NewI
= ReplaceInstUsesWith(AI, ConstantExpr::getBitCast(TheSrc,
AI.getType()));
EraseInstFromFunction(*Copy);
++NumGlobalCopies;
return NewI;
}
}
}
return visitAllocSite(AI);
}
static Instruction *InstCombineLoadCast(InstCombiner &IC, LoadInst &LI,
const DataLayout *TD) {
User *CI = cast<User>(LI.getOperand(0));
Value *CastOp = CI->getOperand(0);
PointerType *DestTy = cast<PointerType>(CI->getType());
Type *DestPTy = DestTy->getElementType();
if (PointerType *SrcTy = dyn_cast<PointerType>(CastOp->getType())) {
if (DestTy->getAddressSpace() != SrcTy->getAddressSpace())
return 0;
Type *SrcPTy = SrcTy->getElementType();
if (DestPTy->isIntegerTy() || DestPTy->isPointerTy() ||
DestPTy->isVectorTy()) {
if (ArrayType *ASrcTy = dyn_cast<ArrayType>(SrcPTy))
if (Constant *CSrc = dyn_cast<Constant>(CastOp))
if (ASrcTy->getNumElements() != 0) {
Value *Idxs[2];
Idxs[0] = Constant::getNullValue(Type::getInt32Ty(LI.getContext()));
Idxs[1] = Idxs[0];
CastOp = ConstantExpr::getGetElementPtr(CSrc, Idxs);
SrcTy = cast<PointerType>(CastOp->getType());
SrcPTy = SrcTy->getElementType();
}
if (IC.getDataLayout() &&
(SrcPTy->isIntegerTy() || SrcPTy->isPointerTy() ||
SrcPTy->isVectorTy()) &&
(SrcPTy->isPointerTy() == LI.getType()->isPointerTy()) &&
IC.getDataLayout()->getTypeSizeInBits(SrcPTy) ==
IC.getDataLayout()->getTypeSizeInBits(DestPTy)) {
LoadInst *NewLoad =
IC.Builder->CreateLoad(CastOp, LI.isVolatile(), CI->getName());
NewLoad->setAlignment(LI.getAlignment());
NewLoad->setAtomic(LI.getOrdering(), LI.getSynchScope());
return new BitCastInst(NewLoad, LI.getType());
}
}
}
return 0;
}
Instruction *InstCombiner::visitLoadInst(LoadInst &LI) {
Value *Op = LI.getOperand(0);
if (TD) {
unsigned KnownAlign =
getOrEnforceKnownAlignment(Op, TD->getPrefTypeAlignment(LI.getType()),TD);
unsigned LoadAlign = LI.getAlignment();
unsigned EffectiveLoadAlign = LoadAlign != 0 ? LoadAlign :
TD->getABITypeAlignment(LI.getType());
if (KnownAlign > EffectiveLoadAlign)
LI.setAlignment(KnownAlign);
else if (LoadAlign == 0)
LI.setAlignment(EffectiveLoadAlign);
}
if (isa<CastInst>(Op))
if (Instruction *Res = InstCombineLoadCast(*this, LI, TD))
return Res;
if (!LI.isSimple()) return 0;
BasicBlock::iterator BBI = &LI;
if (Value *AvailableVal = FindAvailableLoadedValue(Op, LI.getParent(), BBI,6))
return ReplaceInstUsesWith(LI, AvailableVal);
if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(Op)) {
const Value *GEPI0 = GEPI->getOperand(0);
if (isa<ConstantPointerNull>(GEPI0) && GEPI->getPointerAddressSpace() == 0){
new StoreInst(UndefValue::get(LI.getType()),
Constant::getNullValue(Op->getType()), &LI);
return ReplaceInstUsesWith(LI, UndefValue::get(LI.getType()));
}
}
if (isa<UndefValue>(Op) ||
(isa<ConstantPointerNull>(Op) && LI.getPointerAddressSpace() == 0)) {
new StoreInst(UndefValue::get(LI.getType()),
Constant::getNullValue(Op->getType()), &LI);
return ReplaceInstUsesWith(LI, UndefValue::get(LI.getType()));
}
if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Op))
if (CE->isCast())
if (Instruction *Res = InstCombineLoadCast(*this, LI, TD))
return Res;
if (Op->hasOneUse()) {
if (SelectInst *SI = dyn_cast<SelectInst>(Op)) {
unsigned Align = LI.getAlignment();
if (isSafeToLoadUnconditionally(SI->getOperand(1), SI, Align, TD) &&
isSafeToLoadUnconditionally(SI->getOperand(2), SI, Align, TD)) {
LoadInst *V1 = Builder->CreateLoad(SI->getOperand(1),
SI->getOperand(1)->getName()+".val");
LoadInst *V2 = Builder->CreateLoad(SI->getOperand(2),
SI->getOperand(2)->getName()+".val");
V1->setAlignment(Align);
V2->setAlignment(Align);
return SelectInst::Create(SI->getCondition(), V1, V2);
}
if (Constant *C = dyn_cast<Constant>(SI->getOperand(1)))
if (C->isNullValue()) {
LI.setOperand(0, SI->getOperand(2));
return &LI;
}
if (Constant *C = dyn_cast<Constant>(SI->getOperand(2)))
if (C->isNullValue()) {
LI.setOperand(0, SI->getOperand(1));
return &LI;
}
}
}
return 0;
}
static Instruction *InstCombineStoreToCast(InstCombiner &IC, StoreInst &SI) {
User *CI = cast<User>(SI.getOperand(1));
Value *CastOp = CI->getOperand(0);
Type *DestPTy = cast<PointerType>(CI->getType())->getElementType();
PointerType *SrcTy = dyn_cast<PointerType>(CastOp->getType());
if (SrcTy == 0) return 0;
Type *SrcPTy = SrcTy->getElementType();
if (!DestPTy->isIntegerTy() && !DestPTy->isPointerTy())
return 0;
SmallVector<Value*, 4> NewGEPIndices;
if (SrcPTy->isArrayTy() || SrcPTy->isStructTy()) {
Constant *Zero = Constant::getNullValue(Type::getInt32Ty(SI.getContext()));
NewGEPIndices.push_back(Zero);
while (1) {
if (StructType *STy = dyn_cast<StructType>(SrcPTy)) {
if (!STy->getNumElements())
break;
NewGEPIndices.push_back(Zero);
SrcPTy = STy->getElementType(0);
} else if (ArrayType *ATy = dyn_cast<ArrayType>(SrcPTy)) {
NewGEPIndices.push_back(Zero);
SrcPTy = ATy->getElementType();
} else {
break;
}
}
SrcTy = PointerType::get(SrcPTy, SrcTy->getAddressSpace());
}
if (!SrcPTy->isIntegerTy() && !SrcPTy->isPointerTy())
return 0;
if (!IC.getDataLayout() ||
SrcTy->getAddressSpace() !=
cast<PointerType>(CI->getType())->getAddressSpace() ||
IC.getDataLayout()->getTypeSizeInBits(SrcPTy) !=
IC.getDataLayout()->getTypeSizeInBits(DestPTy))
return 0;
Value *NewCast;
Value *SIOp0 = SI.getOperand(0);
Instruction::CastOps opcode = Instruction::BitCast;
Type* CastSrcTy = SIOp0->getType();
Type* CastDstTy = SrcPTy;
if (CastDstTy->isPointerTy()) {
if (CastSrcTy->isIntegerTy())
opcode = Instruction::IntToPtr;
} else if (CastDstTy->isIntegerTy()) {
if (SIOp0->getType()->isPointerTy())
opcode = Instruction::PtrToInt;
}
if (!NewGEPIndices.empty())
CastOp = IC.Builder->CreateInBoundsGEP(CastOp, NewGEPIndices);
NewCast = IC.Builder->CreateCast(opcode, SIOp0, CastDstTy,
SIOp0->getName()+".c");
SI.setOperand(0, NewCast);
SI.setOperand(1, CastOp);
return &SI;
}
static bool equivalentAddressValues(Value *A, Value *B) {
if (A == B) return true;
if (isa<BinaryOperator>(A) ||
isa<CastInst>(A) ||
isa<PHINode>(A) ||
isa<GetElementPtrInst>(A))
if (Instruction *BI = dyn_cast<Instruction>(B))
if (cast<Instruction>(A)->isIdenticalToWhenDefined(BI))
return true;
return false;
}
Instruction *InstCombiner::visitStoreInst(StoreInst &SI) {
Value *Val = SI.getOperand(0);
Value *Ptr = SI.getOperand(1);
if (TD) {
unsigned KnownAlign =
getOrEnforceKnownAlignment(Ptr, TD->getPrefTypeAlignment(Val->getType()),
TD);
unsigned StoreAlign = SI.getAlignment();
unsigned EffectiveStoreAlign = StoreAlign != 0 ? StoreAlign :
TD->getABITypeAlignment(Val->getType());
if (KnownAlign > EffectiveStoreAlign)
SI.setAlignment(KnownAlign);
else if (StoreAlign == 0)
SI.setAlignment(EffectiveStoreAlign);
}
if (!SI.isSimple()) return 0;
if (Ptr->hasOneUse()) {
if (isa<AllocaInst>(Ptr))
return EraseInstFromFunction(SI);
if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr)) {
if (isa<AllocaInst>(GEP->getOperand(0))) {
if (GEP->getOperand(0)->hasOneUse())
return EraseInstFromFunction(SI);
}
}
}
BasicBlock::iterator BBI = &SI;
for (unsigned ScanInsts = 6; BBI != SI.getParent()->begin() && ScanInsts;
--ScanInsts) {
--BBI;
if (isa<DbgInfoIntrinsic>(BBI) ||
(isa<BitCastInst>(BBI) && BBI->getType()->isPointerTy())) {
ScanInsts++;
continue;
}
if (StoreInst *PrevSI = dyn_cast<StoreInst>(BBI)) {
if (PrevSI->isSimple() && equivalentAddressValues(PrevSI->getOperand(1),
SI.getOperand(1))) {
++NumDeadStore;
++BBI;
EraseInstFromFunction(*PrevSI);
continue;
}
break;
}
if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) {
if (LI == Val && equivalentAddressValues(LI->getOperand(0), Ptr) &&
LI->isSimple())
return EraseInstFromFunction(SI);
break;
}
if (BBI->mayWriteToMemory() || BBI->mayReadFromMemory())
break;
}
if (isa<ConstantPointerNull>(Ptr) && SI.getPointerAddressSpace() == 0) {
if (!isa<UndefValue>(Val)) {
SI.setOperand(0, UndefValue::get(Val->getType()));
if (Instruction *U = dyn_cast<Instruction>(Val))
Worklist.Add(U); }
return 0; }
if (isa<UndefValue>(Val))
return EraseInstFromFunction(SI);
if (isa<CastInst>(Ptr))
if (Instruction *Res = InstCombineStoreToCast(*this, SI))
return Res;
if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr))
if (CE->isCast())
if (Instruction *Res = InstCombineStoreToCast(*this, SI))
return Res;
BBI = &SI;
do {
++BBI;
} while (isa<DbgInfoIntrinsic>(BBI) ||
(isa<BitCastInst>(BBI) && BBI->getType()->isPointerTy()));
if (BranchInst *BI = dyn_cast<BranchInst>(BBI))
if (BI->isUnconditional())
if (SimplifyStoreAtEndOfBlock(SI))
return 0;
return 0;
}
bool InstCombiner::SimplifyStoreAtEndOfBlock(StoreInst &SI) {
BasicBlock *StoreBB = SI.getParent();
BasicBlock *DestBB = StoreBB->getTerminator()->getSuccessor(0);
pred_iterator PI = pred_begin(DestBB);
BasicBlock *P = *PI;
BasicBlock *OtherBB = 0;
if (P != StoreBB)
OtherBB = P;
if (++PI == pred_end(DestBB))
return false;
P = *PI;
if (P != StoreBB) {
if (OtherBB)
return false;
OtherBB = P;
}
if (++PI != pred_end(DestBB))
return false;
if (StoreBB == DestBB || OtherBB == DestBB)
return false;
BasicBlock::iterator BBI = OtherBB->getTerminator();
BranchInst *OtherBr = dyn_cast<BranchInst>(BBI);
if (!OtherBr || BBI == OtherBB->begin())
return false;
StoreInst *OtherStore = 0;
if (OtherBr->isUnconditional()) {
--BBI;
while (isa<DbgInfoIntrinsic>(BBI) ||
(isa<BitCastInst>(BBI) && BBI->getType()->isPointerTy())) {
if (BBI==OtherBB->begin())
return false;
--BBI;
}
OtherStore = dyn_cast<StoreInst>(BBI);
if (!OtherStore || OtherStore->getOperand(1) != SI.getOperand(1) ||
!SI.isSameOperationAs(OtherStore))
return false;
} else {
if (OtherBr->getSuccessor(0) != StoreBB &&
OtherBr->getSuccessor(1) != StoreBB)
return false;
for (;; --BBI) {
if ((OtherStore = dyn_cast<StoreInst>(BBI))) {
if (OtherStore->getOperand(1) != SI.getOperand(1) ||
!SI.isSameOperationAs(OtherStore))
return false;
break;
}
if (BBI->mayReadFromMemory() || BBI->mayWriteToMemory() ||
BBI == OtherBB->begin())
return false;
}
for (BasicBlock::iterator I = StoreBB->begin(); &*I != &SI; ++I) {
if (I->mayReadFromMemory() || I->mayWriteToMemory())
return false;
}
}
Value *MergedVal = OtherStore->getOperand(0);
if (MergedVal != SI.getOperand(0)) {
PHINode *PN = PHINode::Create(MergedVal->getType(), 2, "storemerge");
PN->addIncoming(SI.getOperand(0), SI.getParent());
PN->addIncoming(OtherStore->getOperand(0), OtherBB);
MergedVal = InsertNewInstBefore(PN, DestBB->front());
}
BBI = DestBB->getFirstInsertionPt();
StoreInst *NewSI = new StoreInst(MergedVal, SI.getOperand(1),
SI.isVolatile(),
SI.getAlignment(),
SI.getOrdering(),
SI.getSynchScope());
InsertNewInstBefore(NewSI, *BBI);
NewSI->setDebugLoc(OtherStore->getDebugLoc());
if (MDNode *TBAATag = SI.getMetadata(LLVMContext::MD_tbaa))
if ((TBAATag = MDNode::getMostGenericTBAA(TBAATag,
OtherStore->getMetadata(LLVMContext::MD_tbaa))))
NewSI->setMetadata(LLVMContext::MD_tbaa, TBAATag);
EraseInstFromFunction(SI);
EraseInstFromFunction(*OtherStore);
return true;
}