InstCombineLoadStoreAlloca.cpp [plain text]
#include "InstCombineInternal.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
using namespace llvm;
#define DEBUG_TYPE "instcombine"
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::AddrSpaceCast ||
CE->getOpcode() == Instruction::GetElementPtr)
return pointsToConstantGlobal(CE->getOperand(0));
}
return false;
}
static bool
isOnlyCopiedFromConstantGlobal(Value *V, MemTransferInst *&TheCopy,
SmallVectorImpl<Instruction *> &ToDelete) {
SmallVector<std::pair<Value *, bool>, 35> ValuesToInspect;
ValuesToInspect.push_back(std::make_pair(V, false));
while (!ValuesToInspect.empty()) {
auto ValuePair = ValuesToInspect.pop_back_val();
const bool IsOffset = ValuePair.second;
for (auto &U : ValuePair.first->uses()) {
Instruction *I = cast<Instruction>(U.getUser());
if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
if (!LI->isSimple()) return false;
continue;
}
if (isa<BitCastInst>(I) || isa<AddrSpaceCastInst>(I)) {
ValuesToInspect.push_back(std::make_pair(I, IsOffset));
continue;
}
if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I)) {
ValuesToInspect.push_back(
std::make_pair(I, IsOffset || !GEP->hasAllZeroIndices()));
continue;
}
if (CallSite CS = I) {
if (CS.isCallee(&U))
continue;
unsigned ArgNo = CS.getArgumentNo(&U);
if (CS.isInAllocaArgument(ArgNo))
return false;
if (CS.onlyReadsMemory() &&
(CS.getInstruction()->use_empty() || CS.doesNotCapture(ArgNo)))
continue;
if (CS.isByValArgument(ArgNo))
continue;
}
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
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>(I);
if (!MI)
return false;
if (U.getOperandNo() == 1) {
if (MI->isVolatile()) return false;
continue;
}
if (TheCopy) return false;
if (IsOffset) return false;
if (U.getOperandNo() != 0) return false;
if (!pointsToConstantGlobal(MI->getSource()))
return false;
TheCopy = MI;
}
}
return true;
}
static MemTransferInst *
isOnlyCopiedFromConstantGlobal(AllocaInst *AI,
SmallVectorImpl<Instruction *> &ToDelete) {
MemTransferInst *TheCopy = nullptr;
if (isOnlyCopiedFromConstantGlobal(AI, TheCopy, ToDelete))
return TheCopy;
return nullptr;
}
static Instruction *simplifyAllocaArraySize(InstCombiner &IC, AllocaInst &AI) {
if (!AI.isArrayAllocation()) {
if (AI.getArraySize()->getType()->isIntegerTy(32))
return nullptr;
Value *V = IC.Builder->getInt32(1);
AI.setOperand(0, V);
return &AI;
}
if (const ConstantInt *C = dyn_cast<ConstantInt>(AI.getArraySize())) {
Type *NewTy = ArrayType::get(AI.getAllocatedType(), C->getZExtValue());
AllocaInst *New = IC.Builder->CreateAlloca(NewTy, nullptr, AI.getName());
New->setAlignment(AI.getAlignment());
BasicBlock::iterator It = New;
while (isa<AllocaInst>(*It) || isa<DbgInfoIntrinsic>(*It))
++It;
Type *IdxTy = IC.getDataLayout().getIntPtrType(AI.getType());
Value *NullIdx = Constant::getNullValue(IdxTy);
Value *Idx[2] = {NullIdx, NullIdx};
Instruction *GEP =
GetElementPtrInst::CreateInBounds(New, Idx, New->getName() + ".sub");
IC.InsertNewInstBefore(GEP, *It);
return IC.ReplaceInstUsesWith(AI, GEP);
}
if (isa<UndefValue>(AI.getArraySize()))
return IC.ReplaceInstUsesWith(AI, Constant::getNullValue(AI.getType()));
Type *IntPtrTy = IC.getDataLayout().getIntPtrType(AI.getType());
if (AI.getArraySize()->getType() != IntPtrTy) {
Value *V = IC.Builder->CreateIntCast(AI.getArraySize(), IntPtrTy, false);
AI.setOperand(0, V);
return &AI;
}
return nullptr;
}
Instruction *InstCombiner::visitAllocaInst(AllocaInst &AI) {
if (auto *I = simplifyAllocaArraySize(*this, AI))
return I;
if (AI.getAllocatedType()->isSized()) {
if (AI.getAlignment() == 0)
AI.setAlignment(DL.getPrefTypeAlignment(AI.getAllocatedType()));
if (DL.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() ||
DL.getTypeAllocSize(EntryAI->getAllocatedType()) != 0) {
AI.moveBefore(FirstInst);
return &AI;
}
if (EntryAI->getAlignment() == 0)
EntryAI->setAlignment(
DL.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(), DL, &AI, AC, DT);
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());
Constant *Cast
= ConstantExpr::getPointerBitCastOrAddrSpaceCast(TheSrc, AI.getType());
Instruction *NewI = ReplaceInstUsesWith(AI, Cast);
EraseInstFromFunction(*Copy);
++NumGlobalCopies;
return NewI;
}
}
}
return visitAllocSite(AI);
}
static LoadInst *combineLoadToNewType(InstCombiner &IC, LoadInst &LI, Type *NewTy) {
Value *Ptr = LI.getPointerOperand();
unsigned AS = LI.getPointerAddressSpace();
SmallVector<std::pair<unsigned, MDNode *>, 8> MD;
LI.getAllMetadata(MD);
LoadInst *NewLoad = IC.Builder->CreateAlignedLoad(
IC.Builder->CreateBitCast(Ptr, NewTy->getPointerTo(AS)),
LI.getAlignment(), LI.getName());
for (const auto &MDPair : MD) {
unsigned ID = MDPair.first;
MDNode *N = MDPair.second;
switch (ID) {
case LLVMContext::MD_dbg:
case LLVMContext::MD_tbaa:
case LLVMContext::MD_prof:
case LLVMContext::MD_fpmath:
case LLVMContext::MD_tbaa_struct:
case LLVMContext::MD_invariant_load:
case LLVMContext::MD_alias_scope:
case LLVMContext::MD_noalias:
case LLVMContext::MD_nontemporal:
case LLVMContext::MD_mem_parallel_loop_access:
NewLoad->setMetadata(ID, N);
break;
case LLVMContext::MD_nonnull:
if (NewTy->isPointerTy())
NewLoad->setMetadata(ID, N);
break;
case LLVMContext::MD_range:
break;
}
}
return NewLoad;
}
static StoreInst *combineStoreToNewValue(InstCombiner &IC, StoreInst &SI, Value *V) {
Value *Ptr = SI.getPointerOperand();
unsigned AS = SI.getPointerAddressSpace();
SmallVector<std::pair<unsigned, MDNode *>, 8> MD;
SI.getAllMetadata(MD);
StoreInst *NewStore = IC.Builder->CreateAlignedStore(
V, IC.Builder->CreateBitCast(Ptr, V->getType()->getPointerTo(AS)),
SI.getAlignment());
for (const auto &MDPair : MD) {
unsigned ID = MDPair.first;
MDNode *N = MDPair.second;
switch (ID) {
case LLVMContext::MD_dbg:
case LLVMContext::MD_tbaa:
case LLVMContext::MD_prof:
case LLVMContext::MD_fpmath:
case LLVMContext::MD_tbaa_struct:
case LLVMContext::MD_alias_scope:
case LLVMContext::MD_noalias:
case LLVMContext::MD_nontemporal:
case LLVMContext::MD_mem_parallel_loop_access:
NewStore->setMetadata(ID, N);
break;
case LLVMContext::MD_invariant_load:
case LLVMContext::MD_nonnull:
case LLVMContext::MD_range:
break;
}
}
return NewStore;
}
static Instruction *combineLoadToOperationType(InstCombiner &IC, LoadInst &LI) {
if (!LI.isSimple())
return nullptr;
if (LI.use_empty())
return nullptr;
Type *Ty = LI.getType();
const DataLayout &DL = IC.getDataLayout();
if (!Ty->isIntegerTy() && Ty->isSized() &&
DL.isLegalInteger(DL.getTypeStoreSizeInBits(Ty)) &&
DL.getTypeStoreSizeInBits(Ty) == DL.getTypeSizeInBits(Ty)) {
if (std::all_of(LI.user_begin(), LI.user_end(), [&LI](User *U) {
auto *SI = dyn_cast<StoreInst>(U);
return SI && SI->getPointerOperand() != &LI;
})) {
LoadInst *NewLoad = combineLoadToNewType(
IC, LI,
Type::getIntNTy(LI.getContext(), DL.getTypeStoreSizeInBits(Ty)));
for (auto UI = LI.user_begin(), UE = LI.user_end(); UI != UE;) {
auto *SI = cast<StoreInst>(*UI++);
IC.Builder->SetInsertPoint(SI);
combineStoreToNewValue(IC, *SI, NewLoad);
IC.EraseInstFromFunction(*SI);
}
assert(LI.use_empty() && "Failed to remove all users of the load!");
return &LI;
}
}
if (LI.hasOneUse())
if (auto *BC = dyn_cast<BitCastInst>(LI.user_back())) {
LoadInst *NewLoad = combineLoadToNewType(IC, LI, BC->getDestTy());
BC->replaceAllUsesWith(NewLoad);
IC.EraseInstFromFunction(*BC);
return &LI;
}
return nullptr;
}
Instruction *InstCombiner::visitLoadInst(LoadInst &LI) {
Value *Op = LI.getOperand(0);
if (Instruction *Res = combineLoadToOperationType(*this, LI))
return Res;
unsigned KnownAlign = getOrEnforceKnownAlignment(
Op, DL.getPrefTypeAlignment(LI.getType()), DL, &LI, AC, DT);
unsigned LoadAlign = LI.getAlignment();
unsigned EffectiveLoadAlign =
LoadAlign != 0 ? LoadAlign : DL.getABITypeAlignment(LI.getType());
if (KnownAlign > EffectiveLoadAlign)
LI.setAlignment(KnownAlign);
else if (LoadAlign == 0)
LI.setAlignment(EffectiveLoadAlign);
if (!LI.isSimple()) return nullptr;
BasicBlock::iterator BBI = &LI;
if (Value *AvailableVal = FindAvailableLoadedValue(Op, LI.getParent(), BBI,6))
return ReplaceInstUsesWith(
LI, Builder->CreateBitOrPointerCast(AvailableVal, LI.getType(),
LI.getName() + ".cast"));
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 (Op->hasOneUse()) {
if (SelectInst *SI = dyn_cast<SelectInst>(Op)) {
unsigned Align = LI.getAlignment();
if (isSafeToLoadUnconditionally(SI->getOperand(1), SI, Align) &&
isSafeToLoadUnconditionally(SI->getOperand(2), SI, Align)) {
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 (isa<ConstantPointerNull>(SI->getOperand(1)) &&
LI.getPointerAddressSpace() == 0) {
LI.setOperand(0, SI->getOperand(2));
return &LI;
}
if (isa<ConstantPointerNull>(SI->getOperand(2)) &&
LI.getPointerAddressSpace() == 0) {
LI.setOperand(0, SI->getOperand(1));
return &LI;
}
}
}
return nullptr;
}
static bool combineStoreToValueType(InstCombiner &IC, StoreInst &SI) {
if (!SI.isSimple())
return false;
Value *V = SI.getValueOperand();
if (auto *BC = dyn_cast<BitCastInst>(V)) {
V = BC->getOperand(0);
combineStoreToNewValue(IC, SI, V);
return true;
}
return false;
}
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 (combineStoreToValueType(*this, SI))
return EraseInstFromFunction(SI);
unsigned KnownAlign = getOrEnforceKnownAlignment(
Ptr, DL.getPrefTypeAlignment(Val->getType()), DL, &SI, AC, DT);
unsigned StoreAlign = SI.getAlignment();
unsigned EffectiveStoreAlign =
StoreAlign != 0 ? StoreAlign : DL.getABITypeAlignment(Val->getType());
if (KnownAlign > EffectiveStoreAlign)
SI.setAlignment(KnownAlign);
else if (StoreAlign == 0)
SI.setAlignment(EffectiveStoreAlign);
if (!SI.isSimple()) return nullptr;
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 nullptr; }
if (isa<UndefValue>(Val))
return EraseInstFromFunction(SI);
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 nullptr;
return nullptr;
}
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 = nullptr;
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 = nullptr;
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());
AAMDNodes AATags;
SI.getAAMetadata(AATags);
if (AATags) {
OtherStore->getAAMetadata(AATags, true);
NewSI->setAAMetadata(AATags);
}
EraseInstFromFunction(SI);
EraseInstFromFunction(*OtherStore);
return true;
}