InstCombineLoadStoreAlloca.cpp [plain text]
#include "InstCombine.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/ADT/Statistic.h"
using namespace llvm;
STATISTIC(NumDeadStore, "Number of dead stores eliminated");
Instruction *InstCombiner::visitAllocaInst(AllocaInst &AI) {
if (TD) {
const 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())) {
const Type *NewTy =
ArrayType::get(AI.getAllocatedType(), C->getZExtValue());
assert(isa<AllocaInst>(AI) && "Unknown type of allocation inst!");
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;
Value *V = GetElementPtrInst::CreateInBounds(New, Idx, Idx + 2,
New->getName()+".sub", It);
return ReplaceInstUsesWith(AI, V);
} else if (isa<UndefValue>(AI.getArraySize())) {
return ReplaceInstUsesWith(AI, Constant::getNullValue(AI.getType()));
}
}
if (TD && isa<AllocaInst>(AI) && AI.getAllocatedType()->isSized()) {
if (TD->getTypeAllocSize(AI.getAllocatedType()) == 0)
return ReplaceInstUsesWith(AI, Constant::getNullValue(AI.getType()));
if (AI.getAlignment() == 0)
AI.setAlignment(TD->getPrefTypeAlignment(AI.getAllocatedType()));
}
return 0;
}
static Instruction *InstCombineLoadCast(InstCombiner &IC, LoadInst &LI,
const TargetData *TD) {
User *CI = cast<User>(LI.getOperand(0));
Value *CastOp = CI->getOperand(0);
const PointerType *DestTy = cast<PointerType>(CI->getType());
const Type *DestPTy = DestTy->getElementType();
if (const PointerType *SrcTy = dyn_cast<PointerType>(CastOp->getType())) {
if (DestTy->getAddressSpace() != SrcTy->getAddressSpace())
return 0;
const Type *SrcPTy = SrcTy->getElementType();
if (DestPTy->isIntegerTy() || DestPTy->isPointerTy() ||
DestPTy->isVectorTy()) {
if (const 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, 2);
SrcTy = cast<PointerType>(CastOp->getType());
SrcPTy = SrcTy->getElementType();
}
if (IC.getTargetData() &&
(SrcPTy->isIntegerTy() || SrcPTy->isPointerTy() ||
SrcPTy->isVectorTy()) &&
(SrcPTy->isPointerTy() == LI.getType()->isPointerTy()) &&
IC.getTargetData()->getTypeSizeInBits(SrcPTy) ==
IC.getTargetData()->getTypeSizeInBits(DestPTy)) {
LoadInst *NewLoad =
IC.Builder->CreateLoad(CastOp, LI.isVolatile(), CI->getName());
NewLoad->setAlignment(LI.getAlignment());
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()));
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.isVolatile()) 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);
const Type *DestPTy = cast<PointerType>(CI->getType())->getElementType();
const PointerType *SrcTy = dyn_cast<PointerType>(CastOp->getType());
if (SrcTy == 0) return 0;
const 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 (const StructType *STy = dyn_cast<StructType>(SrcPTy)) {
if (!STy->getNumElements())
break;
NewGEPIndices.push_back(Zero);
SrcPTy = STy->getElementType(0);
} else if (const 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.getTargetData() ||
SrcTy->getAddressSpace() !=
cast<PointerType>(CI->getType())->getAddressSpace() ||
IC.getTargetData()->getTypeSizeInBits(SrcPTy) !=
IC.getTargetData()->getTypeSizeInBits(DestPTy))
return 0;
Value *NewCast;
Value *SIOp0 = SI.getOperand(0);
Instruction::CastOps opcode = Instruction::BitCast;
const Type* CastSrcTy = SIOp0->getType();
const 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.begin(),
NewGEPIndices.end());
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;
}
DbgDeclareInst *InstCombiner::hasOneUsePlusDeclare(Value *V) {
if (!V->hasNUses(2))
return 0;
for (Value::use_iterator UI = V->use_begin(), E = V->use_end();
UI != E; ++UI) {
User *U = *UI;
if (DbgDeclareInst *DI = dyn_cast<DbgDeclareInst>(U))
return DI;
if (isa<BitCastInst>(U) && U->hasOneUse()) {
if (DbgDeclareInst *DI = dyn_cast<DbgDeclareInst>(*U->use_begin()))
return DI;
}
}
return 0;
}
Instruction *InstCombiner::visitStoreInst(StoreInst &SI) {
Value *Val = SI.getOperand(0);
Value *Ptr = SI.getOperand(1);
if (!SI.isVolatile()) {
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);
if (DbgDeclareInst *DI = hasOneUsePlusDeclare(GEP->getOperand(0))) {
EraseInstFromFunction(*DI);
return EraseInstFromFunction(SI);
}
}
}
}
if (DbgDeclareInst *DI = hasOneUsePlusDeclare(Ptr)) {
EraseInstFromFunction(*DI);
return EraseInstFromFunction(SI);
}
}
if (TD) {
unsigned KnownAlign =
GetOrEnforceKnownAlignment(Ptr, TD->getPrefTypeAlignment(Val->getType()));
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);
}
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->isVolatile() &&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) &&
!SI.isVolatile())
return EraseInstFromFunction(SI);
break;
}
if (BBI->mayWriteToMemory() || BBI->mayReadFromMemory())
break;
}
if (SI.isVolatile()) return 0;
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) ||
OtherStore->getAlignment() != SI.getAlignment())
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) ||
OtherStore->getAlignment() != SI.getAlignment())
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(), "storemerge");
PN->reserveOperandSpace(2);
PN->addIncoming(SI.getOperand(0), SI.getParent());
PN->addIncoming(OtherStore->getOperand(0), OtherBB);
MergedVal = InsertNewInstBefore(PN, DestBB->front());
}
BBI = DestBB->getFirstNonPHI();
InsertNewInstBefore(new StoreInst(MergedVal, SI.getOperand(1),
OtherStore->isVolatile(),
SI.getAlignment()), *BBI);
EraseInstFromFunction(SI);
EraseInstFromFunction(*OtherStore);
return true;
}