Diff 373788

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

//===- DeadStoreElimination.cpp - MemorySSA Backed Dead Store Elimination -===//		//===- DeadStoreElimination.cpp - MemorySSA Backed Dead Store Elimination -===//
//		//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.		// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.		// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception		// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//		//
//===----------------------------------------------------------------------===//		//===----------------------------------------------------------------------===//
//		//
// The code below implements dead store elimination using MemorySSA. It uses		// The code below implements dead store elimination using MemorySSA. It uses
// the following general approach: given a MemoryDef, walk upwards to find		// the following general approach: given a MemoryDef, walk upwards to find
// clobbering MemoryDefs that may be killed by the starting def. Then check		// clobbering MemoryDefs that may be killed by the starting def. Then check
// that there are no uses that may read the location of the original MemoryDef		// that there are no uses that may read the location of the original MemoryDef
// in between both MemoryDefs. A bit more concretely:		// in between both MemoryDefs. A bit more concretely:
//		//
// For all MemoryDefs StartDef:		// For all MemoryDefs StartDef:
// 1. Get the next dominating clobbering MemoryDef (EarlierAccess) by walking		// 1. Get the next dominating clobbering MemoryDef (MaybeDeadAccess) by walking
// upwards.		// upwards.
// 2. Check that there are no reads between EarlierAccess and the StartDef by		// 2. Check that there are no reads between MaybeDeadAccess and the StartDef by
// checking all uses starting at EarlierAccess and walking until we see		// checking all uses starting at MaybeDeadAccess and walking until we see
// StartDef.		// StartDef.
// 3. For each found CurrentDef, check that:		// 3. For each found CurrentDef, check that:
// 1. There are no barrier instructions between CurrentDef and StartDef (like		// 1. There are no barrier instructions between CurrentDef and StartDef (like
// throws or stores with ordering constraints).		// throws or stores with ordering constraints).
// 2. StartDef is executed whenever CurrentDef is executed.		// 2. StartDef is executed whenever CurrentDef is executed.
// 3. StartDef completely overwrites CurrentDef.		// 3. StartDef completely overwrites CurrentDef.
// 4. Erase CurrentDef from the function and MemorySSA.		// 4. Erase CurrentDef from the function and MemorySSA.
//		//
▲ Show 20 Lines • Show All 302 Lines • ▼ Show 20 Lines	enum OverwriteResult {
OW_PartialEarlierWithFullLater,		OW_PartialEarlierWithFullLater,
OW_MaybePartial,		OW_MaybePartial,
OW_Unknown		OW_Unknown
};		};

} // end anonymous namespace		} // end anonymous namespace

/// Check if two instruction are masked stores that completely		/// Check if two instruction are masked stores that completely
/// overwrite one another. More specifically, \p Later has to		/// overwrite one another. More specifically, \p KillingI has to
/// overwrite \p Earlier.		/// overwrite \p DeadI.
		asbirleaUnsubmitted Not Done Reply Inline Actions s/DeadII/DeadI asbirlea: s/DeadII/DeadI
		ebrevnovAuthorUnsubmitted Done Reply Inline Actions Fixed. Thanks for noting. ebrevnov: Fixed. Thanks for noting.
		fhahnUnsubmitted Done Reply Inline Actions Looks like this is still `DeadII`? fhahn: Looks like this is still `DeadII`?
		ebrevnovAuthorUnsubmitted Done Reply Inline Actions It was fixed locally. Uploading now. ebrevnov: It was fixed locally. Uploading now.
static OverwriteResult isMaskedStoreOverwrite(const Instruction *Later,		static OverwriteResult isMaskedStoreOverwrite(const Instruction *KillingI,
const Instruction *Earlier,		const Instruction *DeadI,
BatchAAResults &AA) {		BatchAAResults &AA) {
const auto *IIL = dyn_cast<IntrinsicInst>(Later);		const auto *KillingII = dyn_cast<IntrinsicInst>(KillingI);
const auto *IIE = dyn_cast<IntrinsicInst>(Earlier);		const auto *DeadII = dyn_cast<IntrinsicInst>(DeadI);
if (IIL == nullptr \|\| IIE == nullptr)		if (KillingII == nullptr \|\| DeadII == nullptr)
return OW_Unknown;		return OW_Unknown;
if (IIL->getIntrinsicID() != Intrinsic::masked_store \|\|		if (KillingII->getIntrinsicID() != Intrinsic::masked_store \|\|
IIE->getIntrinsicID() != Intrinsic::masked_store)		DeadII->getIntrinsicID() != Intrinsic::masked_store)
return OW_Unknown;		return OW_Unknown;
// Pointers.		// Pointers.
Value *LP = IIL->getArgOperand(1)->stripPointerCasts();		Value *KillingPtr = KillingII->getArgOperand(1)->stripPointerCasts();
Value *EP = IIE->getArgOperand(1)->stripPointerCasts();		Value *DeadPtr = DeadII->getArgOperand(1)->stripPointerCasts();
if (LP != EP && !AA.isMustAlias(LP, EP))		if (KillingPtr != DeadPtr && !AA.isMustAlias(KillingPtr, DeadPtr))
return OW_Unknown;		return OW_Unknown;
// Masks.		// Masks.
// TODO: check that Later's mask is a superset of the Earlier's mask.		// TODO: check that KillingII's mask is a superset of the DeadII's mask.
if (IIL->getArgOperand(3) != IIE->getArgOperand(3))		if (KillingII->getArgOperand(3) != DeadII->getArgOperand(3))
		fhahnUnsubmitted Done Reply Inline Actions `KillingI's mask`? fhahn: `KillingI's mask`?
return OW_Unknown;		return OW_Unknown;
return OW_Complete;		return OW_Complete;
}		}

/// Return 'OW_Complete' if a store to the 'Later' location completely		/// Return 'OW_Complete' if a store to the 'KillingLoc' location completely
/// overwrites a store to the 'Earlier' location, 'OW_End' if the end of the		/// overwrites a store to the 'DeadLoc' location, 'OW_End' if the end of the
/// 'Earlier' location is completely overwritten by 'Later', 'OW_Begin' if the		/// 'DeadLoc' location is completely overwritten by 'KillingLoc', 'OW_Begin'
/// beginning of the 'Earlier' location is overwritten by 'Later'.		/// if the beginning of the 'DeadLoc' location is overwritten by 'KillingLoc'.
/// 'OW_PartialEarlierWithFullLater' means that an earlier (big) store was		/// 'OW_PartialEarlierWithFullLater' means that a dead (big) store was
		fhahnUnsubmitted Done Reply Inline Actions `a dead (big) store`? fhahn: `a dead (big) store`?
/// overwritten by a latter (smaller) store which doesn't write outside the big		/// overwritten by a killing (smaller) store which doesn't write outside the big
/// store's memory locations. Returns 'OW_Unknown' if nothing can be determined.		/// store's memory locations. Returns 'OW_Unknown' if nothing can be determined.
/// NOTE: This function must only be called if both \p Later and \p Earlier		/// NOTE: This function must only be called if both \p KillingLoc and \p
/// write to the same underlying object with valid \p EarlierOff and \p		/// DeadLoc belong to the same underlying object with valid \p KillingOff and
/// LaterOff.		/// \p DeadOff.
static OverwriteResult isPartialOverwrite(const MemoryLocation &Later,		static OverwriteResult isPartialOverwrite(const MemoryLocation &KillingLoc,
const MemoryLocation &Earlier,		const MemoryLocation &DeadLoc,
int64_t EarlierOff, int64_t LaterOff,		int64_t KillingOff, int64_t DeadOff,
Instruction *DepWrite,		Instruction *DeadI,
InstOverlapIntervalsTy &IOL) {		InstOverlapIntervalsTy &IOL) {
const uint64_t LaterSize = Later.Size.getValue();		const uint64_t KillingSize = KillingLoc.Size.getValue();
const uint64_t EarlierSize = Earlier.Size.getValue();		const uint64_t DeadSize = DeadLoc.Size.getValue();
// We may now overlap, although the overlap is not complete. There might also		// We may now overlap, although the overlap is not complete. There might also
// be other incomplete overlaps, and together, they might cover the complete		// be other incomplete overlaps, and together, they might cover the complete
// earlier write.		// dead store.
// Note: The correctness of this logic depends on the fact that this function		// Note: The correctness of this logic depends on the fact that this function
// is not even called providing DepWrite when there are any intervening reads.		// is not even called providing DepWrite when there are any intervening reads.
if (EnablePartialOverwriteTracking &&		if (EnablePartialOverwriteTracking &&
LaterOff < int64_t(EarlierOff + EarlierSize) &&		KillingOff < int64_t(DeadOff + DeadSize) &&
int64_t(LaterOff + LaterSize) >= EarlierOff) {		int64_t(KillingOff + KillingSize) >= DeadOff) {

// Insert our part of the overlap into the map.		// Insert our part of the overlap into the map.
auto &IM = IOL[DepWrite];		auto &IM = IOL[DeadI];
LLVM_DEBUG(dbgs() << "DSE: Partial overwrite: Earlier [" << EarlierOff		LLVM_DEBUG(dbgs() << "DSE: Partial overwrite: DeadLoc [" << DeadOff << ", "
<< ", " << int64_t(EarlierOff + EarlierSize)		<< int64_t(DeadOff + DeadSize) << ") KillingLoc ["
<< ") Later [" << LaterOff << ", "		<< KillingOff << ", " << int64_t(KillingOff + KillingSize)
<< int64_t(LaterOff + LaterSize) << ")\n");		<< ")\n");

// Make sure that we only insert non-overlapping intervals and combine		// Make sure that we only insert non-overlapping intervals and combine
// adjacent intervals. The intervals are stored in the map with the ending		// adjacent intervals. The intervals are stored in the map with the ending
// offset as the key (in the half-open sense) and the starting offset as		// offset as the key (in the half-open sense) and the starting offset as
// the value.		// the value.
int64_t LaterIntStart = LaterOff, LaterIntEnd = LaterOff + LaterSize;		int64_t KillingIntStart = KillingOff;
		int64_t KillingIntEnd = KillingOff + KillingSize;

// Find any intervals ending at, or after, LaterIntStart which start		// Find any intervals ending at, or after, KillingIntStart which start
// before LaterIntEnd.		// before KillingIntEnd.
auto ILI = IM.lower_bound(LaterIntStart);		auto ILI = IM.lower_bound(KillingIntStart);
if (ILI != IM.end() && ILI->second <= LaterIntEnd) {		if (ILI != IM.end() && ILI->second <= KillingIntEnd) {
// This existing interval is overlapped with the current store somewhere		// This existing interval is overlapped with the current store somewhere
// in [LaterIntStart, LaterIntEnd]. Merge them by erasing the existing		// in [KillingIntStart, KillingIntEnd]. Merge them by erasing the existing
// intervals and adjusting our start and end.		// intervals and adjusting our start and end.
LaterIntStart = std::min(LaterIntStart, ILI->second);		KillingIntStart = std::min(KillingIntStart, ILI->second);
LaterIntEnd = std::max(LaterIntEnd, ILI->first);		KillingIntEnd = std::max(KillingIntEnd, ILI->first);
ILI = IM.erase(ILI);		ILI = IM.erase(ILI);

// Continue erasing and adjusting our end in case other previous		// Continue erasing and adjusting our end in case other previous
// intervals are also overlapped with the current store.		// intervals are also overlapped with the current store.
//		//
// \|--- ealier 1 ---\| \|--- ealier 2 ---\|		// \|--- dead 1 ---\| \|--- dead 2 ---\|
// \|------- later---------\|		// \|------- killing---------\|
//		//
while (ILI != IM.end() && ILI->second <= LaterIntEnd) {		while (ILI != IM.end() && ILI->second <= KillingIntEnd) {
assert(ILI->second > LaterIntStart && "Unexpected interval");		assert(ILI->second > KillingIntStart && "Unexpected interval");
LaterIntEnd = std::max(LaterIntEnd, ILI->first);		KillingIntEnd = std::max(KillingIntEnd, ILI->first);
ILI = IM.erase(ILI);		ILI = IM.erase(ILI);
}		}
}		}

IM[LaterIntEnd] = LaterIntStart;		IM[KillingIntEnd] = KillingIntStart;

ILI = IM.begin();		ILI = IM.begin();
if (ILI->second <= EarlierOff &&		if (ILI->second <= DeadOff && ILI->first >= int64_t(DeadOff + DeadSize)) {
ILI->first >= int64_t(EarlierOff + EarlierSize)) {		LLVM_DEBUG(dbgs() << "DSE: Full overwrite from partials: DeadLoc ["
LLVM_DEBUG(dbgs() << "DSE: Full overwrite from partials: Earlier ["		<< DeadOff << ", " << int64_t(DeadOff + DeadSize)
<< EarlierOff << ", "		<< ") Composite KillingLoc [" << ILI->second << ", "
<< int64_t(EarlierOff + EarlierSize)
<< ") Composite Later [" << ILI->second << ", "
<< ILI->first << ")\n");		<< ILI->first << ")\n");
++NumCompletePartials;		++NumCompletePartials;
return OW_Complete;		return OW_Complete;
}		}
}		}

// Check for an earlier store which writes to all the memory locations that		// Check for a dead store which writes to all the memory locations that
// the later store writes to.		// the killing store writes to.
if (EnablePartialStoreMerging && LaterOff >= EarlierOff &&		if (EnablePartialStoreMerging && KillingOff >= DeadOff &&
int64_t(EarlierOff + EarlierSize) > LaterOff &&		int64_t(DeadOff + DeadSize) > KillingOff &&
uint64_t(LaterOff - EarlierOff) + LaterSize <= EarlierSize) {		uint64_t(KillingOff - DeadOff) + KillingSize <= DeadSize) {
LLVM_DEBUG(dbgs() << "DSE: Partial overwrite an earlier load ["		LLVM_DEBUG(dbgs() << "DSE: Partial overwrite a dead load [" << DeadOff
		fhahnUnsubmitted Done Reply Inline Actions `a dead load`. fhahn: `a dead load`.
<< EarlierOff << ", "		<< ", " << int64_t(DeadOff + DeadSize)
<< int64_t(EarlierOff + EarlierSize)		<< ") by a killing store [" << KillingOff << ", "
<< ") by a later store [" << LaterOff << ", "		<< int64_t(KillingOff + KillingSize) << ")\n");
		fhahnUnsubmitted Done Reply Inline Actions `a dead store` fhahn: `a dead store`
<< int64_t(LaterOff + LaterSize) << ")\n");
// TODO: Maybe come up with a better name?		// TODO: Maybe come up with a better name?
return OW_PartialEarlierWithFullLater;		return OW_PartialEarlierWithFullLater;
}		}

// Another interesting case is if the later store overwrites the end of the		// Another interesting case is if the killing store overwrites the end of the
// earlier store.		// dead store.
//		//
// \|--earlier--\|		// \|--dead--\|
// \|-- later --\|		// \|-- killing --\|
//		//
// In this case we may want to trim the size of earlier to avoid generating		// In this case we may want to trim the size of dead store to avoid
// writes to addresses which will definitely be overwritten later		// generating stores to addresses which will definitely be overwritten killing
		// store.
if (!EnablePartialOverwriteTracking &&		if (!EnablePartialOverwriteTracking &&
(LaterOff > EarlierOff && LaterOff < int64_t(EarlierOff + EarlierSize) &&		(KillingOff > DeadOff && KillingOff < int64_t(DeadOff + DeadSize) &&
int64_t(LaterOff + LaterSize) >= int64_t(EarlierOff + EarlierSize)))		int64_t(KillingOff + KillingSize) >= int64_t(DeadOff + DeadSize)))
return OW_End;		return OW_End;

// Finally, we also need to check if the later store overwrites the beginning		// Finally, we also need to check if the killing store overwrites the
// of the earlier store.		// beginning of the dead store.
//		//
// \|--earlier--\|		// \|--dead--\|
// \|-- later --\|		// \|-- killing --\|
//		//
// In this case we may want to move the destination address and trim the size		// In this case we may want to move the destination address and trim the size
// of earlier to avoid generating writes to addresses which will definitely		// of dead store to avoid generating stores to addresses which will definitely
// be overwritten later.		// be overwritten killing store.
if (!EnablePartialOverwriteTracking &&		if (!EnablePartialOverwriteTracking &&
(LaterOff <= EarlierOff && int64_t(LaterOff + LaterSize) > EarlierOff)) {		(KillingOff <= DeadOff && int64_t(KillingOff + KillingSize) > DeadOff)) {
assert(int64_t(LaterOff + LaterSize) < int64_t(EarlierOff + EarlierSize) &&		assert(int64_t(KillingOff + KillingSize) < int64_t(DeadOff + DeadSize) &&
"Expect to be handled as OW_Complete");		"Expect to be handled as OW_Complete");
return OW_Begin;		return OW_Begin;
}		}
// Otherwise, they don't completely overlap.		// Otherwise, they don't completely overlap.
return OW_Unknown;		return OW_Unknown;
}		}

/// Returns true if the memory which is accessed by the second instruction is not		/// Returns true if the memory which is accessed by the second instruction is not
▲ Show 20 Lines • Show All 83 Lines • ▼ Show 20 Lines	if (B != FirstBB) {
}		}
WorkList.push_back(std::make_pair(Pred, PredAddr));		WorkList.push_back(std::make_pair(Pred, PredAddr));
}		}
}		}
}		}
return true;		return true;
}		}

static bool tryToShorten(Instruction *EarlierWrite, int64_t &EarlierStart,		static bool tryToShorten(Instruction *DeadI, int64_t &DeadStart,
uint64_t &EarlierSize, int64_t LaterStart,		uint64_t &DeadSize, int64_t KillingStart,
uint64_t LaterSize, bool IsOverwriteEnd) {		uint64_t KillingSize, bool IsOverwriteEnd) {
auto *EarlierIntrinsic = cast<AnyMemIntrinsic>(EarlierWrite);		auto *DeadIntrinsic = cast<AnyMemIntrinsic>(DeadI);
Align PrefAlign = EarlierIntrinsic->getDestAlign().valueOrOne();		Align PrefAlign = DeadIntrinsic->getDestAlign().valueOrOne();

// We assume that memet/memcpy operates in chunks of the "largest" native		// We assume that memet/memcpy operates in chunks of the "largest" native
// type size and aligned on the same value. That means optimal start and size		// type size and aligned on the same value. That means optimal start and size
// of memset/memcpy should be modulo of preferred alignment of that type. That		// of memset/memcpy should be modulo of preferred alignment of that type. That
// is it there is no any sense in trying to reduce store size any further		// is it there is no any sense in trying to reduce store size any further
// since any "extra" stores comes for free anyway.		// since any "extra" stores comes for free anyway.
// On the other hand, maximum alignment we can achieve is limited by alignment		// On the other hand, maximum alignment we can achieve is limited by alignment
// of initial store.		// of initial store.

// TODO: Limit maximum alignment by preferred (or abi?) alignment of the		// TODO: Limit maximum alignment by preferred (or abi?) alignment of the
// "largest" native type.		// "largest" native type.
// Note: What is the proper way to get that value?		// Note: What is the proper way to get that value?
// Should TargetTransformInfo::getRegisterBitWidth be used or anything else?		// Should TargetTransformInfo::getRegisterBitWidth be used or anything else?
// PrefAlign = std::min(DL.getPrefTypeAlign(LargestType), PrefAlign);		// PrefAlign = std::min(DL.getPrefTypeAlign(LargestType), PrefAlign);

int64_t ToRemoveStart = 0;		int64_t ToRemoveStart = 0;
uint64_t ToRemoveSize = 0;		uint64_t ToRemoveSize = 0;
// Compute start and size of the region to remove. Make sure 'PrefAlign' is		// Compute start and size of the region to remove. Make sure 'PrefAlign' is
// maintained on the remaining store.		// maintained on the remaining store.
if (IsOverwriteEnd) {		if (IsOverwriteEnd) {
// Calculate required adjustment for 'LaterStart'in order to keep remaining		// Calculate required adjustment for 'KillingStart' in order to keep
// store size aligned on 'PerfAlign'.		// remaining store size aligned on 'PerfAlign'.
uint64_t Off =		uint64_t Off =
offsetToAlignment(uint64_t(LaterStart - EarlierStart), PrefAlign);		offsetToAlignment(uint64_t(KillingStart - DeadStart), PrefAlign);
ToRemoveStart = LaterStart + Off;		ToRemoveStart = KillingStart + Off;
if (EarlierSize <= uint64_t(ToRemoveStart - EarlierStart))		if (DeadSize <= uint64_t(ToRemoveStart - DeadStart))
return false;		return false;
ToRemoveSize = EarlierSize - uint64_t(ToRemoveStart - EarlierStart);		ToRemoveSize = DeadSize - uint64_t(ToRemoveStart - DeadStart);
} else {		} else {
ToRemoveStart = EarlierStart;		ToRemoveStart = DeadStart;
assert(LaterSize >= uint64_t(EarlierStart - LaterStart) &&		assert(KillingSize >= uint64_t(DeadStart - KillingStart) &&
"Not overlapping accesses?");		"Not overlapping accesses?");
ToRemoveSize = LaterSize - uint64_t(EarlierStart - LaterStart);		ToRemoveSize = KillingSize - uint64_t(DeadStart - KillingStart);
// Calculate required adjustment for 'ToRemoveSize'in order to keep		// Calculate required adjustment for 'ToRemoveSize'in order to keep
// start of the remaining store aligned on 'PerfAlign'.		// start of the remaining store aligned on 'PerfAlign'.
uint64_t Off = offsetToAlignment(ToRemoveSize, PrefAlign);		uint64_t Off = offsetToAlignment(ToRemoveSize, PrefAlign);
if (Off != 0) {		if (Off != 0) {
if (ToRemoveSize <= (PrefAlign.value() - Off))		if (ToRemoveSize <= (PrefAlign.value() - Off))
return false;		return false;
ToRemoveSize -= PrefAlign.value() - Off;		ToRemoveSize -= PrefAlign.value() - Off;
}		}
assert(isAligned(PrefAlign, ToRemoveSize) &&		assert(isAligned(PrefAlign, ToRemoveSize) &&
"Should preserve selected alignment");		"Should preserve selected alignment");
}		}

assert(ToRemoveSize > 0 && "Shouldn't reach here if nothing to remove");		assert(ToRemoveSize > 0 && "Shouldn't reach here if nothing to remove");
assert(EarlierSize > ToRemoveSize && "Can't remove more than original size");		assert(DeadSize > ToRemoveSize && "Can't remove more than original size");

uint64_t NewSize = EarlierSize - ToRemoveSize;		uint64_t NewSize = DeadSize - ToRemoveSize;
if (auto *AMI = dyn_cast<AtomicMemIntrinsic>(EarlierWrite)) {		if (auto *AMI = dyn_cast<AtomicMemIntrinsic>(DeadI)) {
// When shortening an atomic memory intrinsic, the newly shortened		// When shortening an atomic memory intrinsic, the newly shortened
// length must remain an integer multiple of the element size.		// length must remain an integer multiple of the element size.
const uint32_t ElementSize = AMI->getElementSizeInBytes();		const uint32_t ElementSize = AMI->getElementSizeInBytes();
if (0 != NewSize % ElementSize)		if (0 != NewSize % ElementSize)
return false;		return false;
}		}

LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n OW "		LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n OW "
<< (IsOverwriteEnd ? "END" : "BEGIN") << ": "		<< (IsOverwriteEnd ? "END" : "BEGIN") << ": " << *DeadI
<< *EarlierWrite << "\n KILLER [" << ToRemoveStart << ", "		<< "\n KILLER [" << ToRemoveStart << ", "
<< int64_t(ToRemoveStart + ToRemoveSize) << ")\n");		<< int64_t(ToRemoveStart + ToRemoveSize) << ")\n");

Value *EarlierWriteLength = EarlierIntrinsic->getLength();		Value *DeadWriteLength = DeadIntrinsic->getLength();
Value *TrimmedLength =		Value *TrimmedLength = ConstantInt::get(DeadWriteLength->getType(), NewSize);
ConstantInt::get(EarlierWriteLength->getType(), NewSize);		DeadIntrinsic->setLength(TrimmedLength);
EarlierIntrinsic->setLength(TrimmedLength);		DeadIntrinsic->setDestAlignment(PrefAlign);
EarlierIntrinsic->setDestAlignment(PrefAlign);

if (!IsOverwriteEnd) {		if (!IsOverwriteEnd) {
Value *OrigDest = EarlierIntrinsic->getRawDest();		Value *OrigDest = DeadIntrinsic->getRawDest();
Type *Int8PtrTy =		Type *Int8PtrTy =
Type::getInt8PtrTy(EarlierIntrinsic->getContext(),		Type::getInt8PtrTy(DeadIntrinsic->getContext(),
OrigDest->getType()->getPointerAddressSpace());		OrigDest->getType()->getPointerAddressSpace());
Value *Dest = OrigDest;		Value *Dest = OrigDest;
if (OrigDest->getType() != Int8PtrTy)		if (OrigDest->getType() != Int8PtrTy)
Dest = CastInst::CreatePointerCast(OrigDest, Int8PtrTy, "", EarlierWrite);		Dest = CastInst::CreatePointerCast(OrigDest, Int8PtrTy, "", DeadI);
Value *Indices[1] = {		Value *Indices[1] = {
ConstantInt::get(EarlierWriteLength->getType(), ToRemoveSize)};		ConstantInt::get(DeadWriteLength->getType(), ToRemoveSize)};
Instruction *NewDestGEP = GetElementPtrInst::CreateInBounds(		Instruction *NewDestGEP = GetElementPtrInst::CreateInBounds(
Type::getInt8Ty(EarlierIntrinsic->getContext()),		Type::getInt8Ty(DeadIntrinsic->getContext()), Dest, Indices, "", DeadI);
Dest, Indices, "", EarlierWrite);		NewDestGEP->setDebugLoc(DeadIntrinsic->getDebugLoc());
NewDestGEP->setDebugLoc(EarlierIntrinsic->getDebugLoc());
if (NewDestGEP->getType() != OrigDest->getType())		if (NewDestGEP->getType() != OrigDest->getType())
NewDestGEP = CastInst::CreatePointerCast(NewDestGEP, OrigDest->getType(),		NewDestGEP = CastInst::CreatePointerCast(NewDestGEP, OrigDest->getType(),
"", EarlierWrite);		"", DeadI);
EarlierIntrinsic->setDest(NewDestGEP);		DeadIntrinsic->setDest(NewDestGEP);
}		}

// Finally update start and size of earlier access.		// Finally update start and size of dead access.
if (!IsOverwriteEnd)		if (!IsOverwriteEnd)
EarlierStart += ToRemoveSize;		DeadStart += ToRemoveSize;
EarlierSize = NewSize;		DeadSize = NewSize;

return true;		return true;
}		}

static bool tryToShortenEnd(Instruction *EarlierWrite,		static bool tryToShortenEnd(Instruction *DeadI, OverlapIntervalsTy &IntervalMap,
OverlapIntervalsTy &IntervalMap,		int64_t &DeadStart, uint64_t &DeadSize) {
int64_t &EarlierStart, uint64_t &EarlierSize) {		if (IntervalMap.empty() \|\| !isShortenableAtTheEnd(DeadI))
if (IntervalMap.empty() \|\| !isShortenableAtTheEnd(EarlierWrite))
return false;		return false;

OverlapIntervalsTy::iterator OII = --IntervalMap.end();		OverlapIntervalsTy::iterator OII = --IntervalMap.end();
int64_t LaterStart = OII->second;		int64_t KillingStart = OII->second;
uint64_t LaterSize = OII->first - LaterStart;		uint64_t KillingSize = OII->first - KillingStart;

assert(OII->first - LaterStart >= 0 && "Size expected to be positive");		assert(OII->first - KillingStart >= 0 && "Size expected to be positive");

if (LaterStart > EarlierStart &&		if (KillingStart > DeadStart &&
// Note: "LaterStart - EarlierStart" is known to be positive due to		// Note: "KillingStart - KillingStart" is known to be positive due to
// preceding check.		// preceding check.
(uint64_t)(LaterStart - EarlierStart) < EarlierSize &&		(uint64_t)(KillingStart - DeadStart) < DeadSize &&
// Note: "EarlierSize - (uint64_t)(LaterStart - EarlierStart)" is known to		// Note: "DeadSize - (uint64_t)(KillingStart - DeadStart)" is known to
// be non negative due to preceding checks.		// be non negative due to preceding checks.
LaterSize >= EarlierSize - (uint64_t)(LaterStart - EarlierStart)) {		KillingSize >= DeadSize - (uint64_t)(KillingStart - DeadStart)) {
if (tryToShorten(EarlierWrite, EarlierStart, EarlierSize, LaterStart,		if (tryToShorten(DeadI, DeadStart, DeadSize, KillingStart, KillingSize,
LaterSize, true)) {		true)) {
IntervalMap.erase(OII);		IntervalMap.erase(OII);
return true;		return true;
}		}
}		}
return false;		return false;
}		}

static bool tryToShortenBegin(Instruction *EarlierWrite,		static bool tryToShortenBegin(Instruction *DeadI,
OverlapIntervalsTy &IntervalMap,		OverlapIntervalsTy &IntervalMap,
int64_t &EarlierStart, uint64_t &EarlierSize) {		int64_t &DeadStart, uint64_t &DeadSize) {
if (IntervalMap.empty() \|\| !isShortenableAtTheBeginning(EarlierWrite))		if (IntervalMap.empty() \|\| !isShortenableAtTheBeginning(DeadI))
return false;		return false;

OverlapIntervalsTy::iterator OII = IntervalMap.begin();		OverlapIntervalsTy::iterator OII = IntervalMap.begin();
int64_t LaterStart = OII->second;		int64_t KillingStart = OII->second;
uint64_t LaterSize = OII->first - LaterStart;		uint64_t KillingSize = OII->first - KillingStart;

assert(OII->first - LaterStart >= 0 && "Size expected to be positive");		assert(OII->first - KillingStart >= 0 && "Size expected to be positive");

if (LaterStart <= EarlierStart &&		if (KillingStart <= DeadStart &&
// Note: "EarlierStart - LaterStart" is known to be non negative due to		// Note: "DeadStart - KillingStart" is known to be non negative due to
// preceding check.		// preceding check.
LaterSize > (uint64_t)(EarlierStart - LaterStart)) {		KillingSize > (uint64_t)(DeadStart - KillingStart)) {
// Note: "LaterSize - (uint64_t)(EarlierStart - LaterStart)" is known to be		// Note: "KillingSize - (uint64_t)(DeadStart - DeadStart)" is known to
// positive due to preceding checks.		// be positive due to preceding checks.
assert(LaterSize - (uint64_t)(EarlierStart - LaterStart) < EarlierSize &&		assert(KillingSize - (uint64_t)(DeadStart - KillingStart) < DeadSize &&
"Should have been handled as OW_Complete");		"Should have been handled as OW_Complete");
if (tryToShorten(EarlierWrite, EarlierStart, EarlierSize, LaterStart,		if (tryToShorten(DeadI, DeadStart, DeadSize, KillingStart, KillingSize,
LaterSize, false)) {		false)) {
IntervalMap.erase(OII);		IntervalMap.erase(OII);
return true;		return true;
}		}
}		}
return false;		return false;
}		}

static bool removePartiallyOverlappedStores(const DataLayout &DL,		static bool removePartiallyOverlappedStores(const DataLayout &DL,
InstOverlapIntervalsTy &IOL,		InstOverlapIntervalsTy &IOL,
const TargetLibraryInfo &TLI) {		const TargetLibraryInfo &TLI) {
bool Changed = false;		bool Changed = false;
for (auto OI : IOL) {		for (auto OI : IOL) {
Instruction *EarlierWrite = OI.first;		Instruction *DeadI = OI.first;
MemoryLocation Loc = getLocForWrite(EarlierWrite, TLI);		MemoryLocation Loc = getLocForWrite(DeadI, TLI);
assert(isRemovable(EarlierWrite) && "Expect only removable instruction");		assert(isRemovable(DeadI) && "Expect only removable instruction");

const Value *Ptr = Loc.Ptr->stripPointerCasts();		const Value *Ptr = Loc.Ptr->stripPointerCasts();
int64_t EarlierStart = 0;		int64_t DeadStart = 0;
uint64_t EarlierSize = Loc.Size.getValue();		uint64_t DeadSize = Loc.Size.getValue();
GetPointerBaseWithConstantOffset(Ptr, EarlierStart, DL);		GetPointerBaseWithConstantOffset(Ptr, DeadStart, DL);
OverlapIntervalsTy &IntervalMap = OI.second;		OverlapIntervalsTy &IntervalMap = OI.second;
Changed \|=		Changed \|= tryToShortenEnd(DeadI, IntervalMap, DeadStart, DeadSize);
tryToShortenEnd(EarlierWrite, IntervalMap, EarlierStart, EarlierSize);
if (IntervalMap.empty())		if (IntervalMap.empty())
continue;		continue;
Changed \|=		Changed \|= tryToShortenBegin(DeadI, IntervalMap, DeadStart, DeadSize);
tryToShortenBegin(EarlierWrite, IntervalMap, EarlierStart, EarlierSize);
}		}
return Changed;		return Changed;
}		}

static Constant *tryToMergePartialOverlappingStores(		static Constant *
StoreInst Earlier, StoreInst Later, int64_t InstWriteOffset,		tryToMergePartialOverlappingStores(StoreInst KillingI, StoreInst DeadI,
int64_t DepWriteOffset, const DataLayout &DL, BatchAAResults &AA,		int64_t KillingOffset, int64_t DeadOffset,
		const DataLayout &DL, BatchAAResults &AA,
DominatorTree *DT) {		DominatorTree *DT) {

if (Earlier && isa<ConstantInt>(Earlier->getValueOperand()) &&		if (DeadI && isa<ConstantInt>(DeadI->getValueOperand()) &&
DL.typeSizeEqualsStoreSize(Earlier->getValueOperand()->getType()) &&		DL.typeSizeEqualsStoreSize(DeadI->getValueOperand()->getType()) &&
Later && isa<ConstantInt>(Later->getValueOperand()) &&		KillingI && isa<ConstantInt>(KillingI->getValueOperand()) &&
DL.typeSizeEqualsStoreSize(Later->getValueOperand()->getType()) &&		DL.typeSizeEqualsStoreSize(KillingI->getValueOperand()->getType()) &&
memoryIsNotModifiedBetween(Earlier, Later, AA, DL, DT)) {		memoryIsNotModifiedBetween(DeadI, KillingI, AA, DL, DT)) {
// If the store we find is:		// If the store we find is:
// a) partially overwritten by the store to 'Loc'		// a) partially overwritten by the store to 'Loc'
// b) the later store is fully contained in the earlier one and		// b) the killing store is fully contained in the dead one and
// c) they both have a constant value		// c) they both have a constant value
// d) none of the two stores need padding		// d) none of the two stores need padding
// Merge the two stores, replacing the earlier store's value with a		// Merge the two stores, replacing the dead store's value with a
// merge of both values.		// merge of both values.
// TODO: Deal with other constant types (vectors, etc), and probably		// TODO: Deal with other constant types (vectors, etc), and probably
// some mem intrinsics (if needed)		// some mem intrinsics (if needed)

APInt EarlierValue =		APInt DeadValue = cast<ConstantInt>(DeadI->getValueOperand())->getValue();
cast<ConstantInt>(Earlier->getValueOperand())->getValue();		APInt KillingValue =
APInt LaterValue = cast<ConstantInt>(Later->getValueOperand())->getValue();		cast<ConstantInt>(KillingI->getValueOperand())->getValue();
unsigned LaterBits = LaterValue.getBitWidth();		unsigned KillingBits = KillingValue.getBitWidth();
assert(EarlierValue.getBitWidth() > LaterValue.getBitWidth());		assert(DeadValue.getBitWidth() > KillingValue.getBitWidth());
LaterValue = LaterValue.zext(EarlierValue.getBitWidth());		KillingValue = KillingValue.zext(DeadValue.getBitWidth());

// Offset of the smaller store inside the larger store		// Offset of the smaller store inside the larger store
unsigned BitOffsetDiff = (InstWriteOffset - DepWriteOffset) * 8;		unsigned BitOffsetDiff = (KillingOffset - DeadOffset) * 8;
unsigned LShiftAmount = DL.isBigEndian() ? EarlierValue.getBitWidth() -		unsigned LShiftAmount =
BitOffsetDiff - LaterBits		DL.isBigEndian() ? DeadValue.getBitWidth() - BitOffsetDiff - KillingBits
: BitOffsetDiff;		: BitOffsetDiff;
APInt Mask = APInt::getBitsSet(EarlierValue.getBitWidth(), LShiftAmount,		APInt Mask = APInt::getBitsSet(DeadValue.getBitWidth(), LShiftAmount,
LShiftAmount + LaterBits);		LShiftAmount + KillingBits);
// Clear the bits we'll be replacing, then OR with the smaller		// Clear the bits we'll be replacing, then OR with the smaller
// store, shifted appropriately.		// store, shifted appropriately.
APInt Merged = (EarlierValue & ~Mask) \| (LaterValue << LShiftAmount);		APInt Merged = (DeadValue & ~Mask) \| (KillingValue << LShiftAmount);
LLVM_DEBUG(dbgs() << "DSE: Merge Stores:\n Earlier: " << *Earlier		LLVM_DEBUG(dbgs() << "DSE: Merge Stores:\n Dead: " << *DeadI
<< "\n Later: " << *Later		<< "\n Killing: " << *KillingI
<< "\n Merged Value: " << Merged << '\n');		<< "\n Merged Value: " << Merged << '\n');
return ConstantInt::get(Earlier->getValueOperand()->getType(), Merged);		return ConstantInt::get(DeadI->getValueOperand()->getType(), Merged);
}		}
return nullptr;		return nullptr;
}		}

namespace {		namespace {
// Returns true if \p I is an intrisnic that does not read or write memory.		// Returns true if \p I is an intrisnic that does not read or write memory.
bool isNoopIntrinsic(Instruction *I) {		bool isNoopIntrinsic(Instruction *I) {
if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {		if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
▲ Show 20 Lines • Show All 131 Lines • ▼ Show 20 Lines	for (Argument &AI : F.args())
}		}

// Collect whether there is any irreducible control flow in the function.		// Collect whether there is any irreducible control flow in the function.
State.ContainsIrreducibleLoops = mayContainIrreducibleControl(F, &LI);		State.ContainsIrreducibleLoops = mayContainIrreducibleControl(F, &LI);

return State;		return State;
}		}

/// Return 'OW_Complete' if a store to the 'Later' location (by \p LaterI		/// Return 'OW_Complete' if a store to the 'KillingLoc' location (by \p
/// instruction) completely overwrites a store to the 'Earlier' location.		/// KillingI instruction) completely overwrites a store to the 'DeadLoc'
/// (by \p EarlierI instruction).		/// location (by \p DeadI instruction).
/// Return OW_MaybePartial if \p Later does not completely overwrite		/// Return OW_MaybePartial if \p KillingI does not completely overwrite
/// \p Earlier, but they both write to the same underlying object. In that		/// \p DeadI, but they both write to the same underlying object. In that
/// case, use isPartialOverwrite to check if \p Later partially overwrites		/// case, use isPartialOverwrite to check if \p KillingI partially overwrites
/// \p Earlier. Returns 'OW_Unknown' if nothing can be determined.		/// \p DeadI. Returns 'OW_Unknown' if nothing can be determined.
OverwriteResult		OverwriteResult isOverwrite(const Instruction *KillingI,
isOverwrite(const Instruction LaterI, const Instruction EarlierI,		const Instruction *DeadI,
const MemoryLocation &Later, const MemoryLocation &Earlier,		const MemoryLocation &KillingLoc,
int64_t &EarlierOff, int64_t &LaterOff) {		const MemoryLocation &DeadLoc,
		int64_t &KillingOff, int64_t &DeadOff) {
// AliasAnalysis does not always account for loops. Limit overwrite checks		// AliasAnalysis does not always account for loops. Limit overwrite checks
// to dependencies for which we can guarantee they are independant of any		// to dependencies for which we can guarantee they are independent of any
// loops they are in.		// loops they are in.
if (!isGuaranteedLoopIndependent(EarlierI, LaterI, Earlier))		if (!isGuaranteedLoopIndependent(DeadI, KillingI, DeadLoc))
return OW_Unknown;		return OW_Unknown;

// FIXME: Vet that this works for size upper-bounds. Seems unlikely that we'll		// FIXME: Vet that this works for size upper-bounds. Seems unlikely that we'll
// get imprecise values here, though (except for unknown sizes).		// get imprecise values here, though (except for unknown sizes).
if (!Later.Size.isPrecise() \|\| !Earlier.Size.isPrecise()) {		if (!KillingLoc.Size.isPrecise() \|\| !DeadLoc.Size.isPrecise()) {
// In case no constant size is known, try to an IR values for the number		// In case no constant size is known, try to an IR values for the number
// of bytes written and check if they match.		// of bytes written and check if they match.
const auto *LaterMemI = dyn_cast<MemIntrinsic>(LaterI);		const auto *KillingMemI = dyn_cast<MemIntrinsic>(KillingI);
const auto *EarlierMemI = dyn_cast<MemIntrinsic>(EarlierI);		const auto *DeadMemI = dyn_cast<MemIntrinsic>(DeadI);
if (LaterMemI && EarlierMemI) {		if (KillingMemI && DeadMemI) {
const Value *LaterV = LaterMemI->getLength();		const Value *KillingV = KillingMemI->getLength();
const Value *EarlierV = EarlierMemI->getLength();		const Value *DeadV = DeadMemI->getLength();
if (LaterV == EarlierV && BatchAA.isMustAlias(Earlier, Later))		if (KillingV == DeadV && BatchAA.isMustAlias(DeadLoc, KillingLoc))
return OW_Complete;		return OW_Complete;
}		}

// Masked stores have imprecise locations, but we can reason about them		// Masked stores have imprecise locations, but we can reason about them
// to some extent.		// to some extent.
return isMaskedStoreOverwrite(LaterI, EarlierI, BatchAA);		return isMaskedStoreOverwrite(KillingI, DeadI, BatchAA);
}		}

const uint64_t LaterSize = Later.Size.getValue();		const uint64_t KillingSize = KillingLoc.Size.getValue();
const uint64_t EarlierSize = Earlier.Size.getValue();		const uint64_t DeadSize = DeadLoc.Size.getValue();

// Query the alias information		// Query the alias information
AliasResult AAR = BatchAA.alias(Later, Earlier);		AliasResult AAR = BatchAA.alias(KillingLoc, DeadLoc);

// If the start pointers are the same, we just have to compare sizes to see if		// If the start pointers are the same, we just have to compare sizes to see if
// the later store was larger than the earlier store.		// the killing store was larger than the dead store.
if (AAR == AliasResult::MustAlias) {		if (AAR == AliasResult::MustAlias) {
// Make sure that the Later size is >= the Earlier size.		// Make sure that the KillingSize size is >= the DeadSize size.
if (LaterSize >= EarlierSize)		if (KillingSize >= DeadSize)
return OW_Complete;		return OW_Complete;
}		}

// If we hit a partial alias we may have a full overwrite		// If we hit a partial alias we may have a full overwrite
if (AAR == AliasResult::PartialAlias && AAR.hasOffset()) {		if (AAR == AliasResult::PartialAlias && AAR.hasOffset()) {
int32_t Off = AAR.getOffset();		int32_t Off = AAR.getOffset();
if (Off >= 0 && (uint64_t)Off + EarlierSize <= LaterSize)		if (Off >= 0 && (uint64_t)Off + DeadSize <= KillingSize)
return OW_Complete;		return OW_Complete;
}		}

// Check to see if the later store is to the entire object (either a global,		// Check to see if the killing store is to the entire object (either a
// an alloca, or a byval/inalloca argument). If so, then it clearly		// global, an alloca, or a byval/inalloca argument). If so, then it clearly
// overwrites any other store to the same object.		// overwrites any other store to the same object.
const Value *P1 = Earlier.Ptr->stripPointerCasts();		const Value *DeadPtr = DeadLoc.Ptr->stripPointerCasts();
const Value *P2 = Later.Ptr->stripPointerCasts();		const Value *KillingPtr = KillingLoc.Ptr->stripPointerCasts();
const Value UO1 = getUnderlyingObject(P1), UO2 = getUnderlyingObject(P2);		const Value *DeadUndObj = getUnderlyingObject(DeadPtr);
		const Value *KillingUndObj = getUnderlyingObject(KillingPtr);

// If we can't resolve the same pointers to the same object, then we can't		// If we can't resolve the same pointers to the same object, then we can't
// analyze them at all.		// analyze them at all.
if (UO1 != UO2)		if (DeadUndObj != KillingUndObj)
return OW_Unknown;		return OW_Unknown;

// If the "Later" store is to a recognizable object, get its size.		// If the KillingI store is to a recognizable object, get its size.
uint64_t ObjectSize = getPointerSize(UO2, DL, TLI, &F);		uint64_t KillingUndObjSize = getPointerSize(KillingUndObj, DL, TLI, &F);
if (ObjectSize != MemoryLocation::UnknownSize)		if (KillingUndObjSize != MemoryLocation::UnknownSize)
if (ObjectSize == LaterSize && ObjectSize >= EarlierSize)		if (KillingUndObjSize == KillingSize && KillingUndObjSize >= DeadSize)
return OW_Complete;		return OW_Complete;

// Okay, we have stores to two completely different pointers. Try to		// Okay, we have stores to two completely different pointers. Try to
// decompose the pointer into a "base + constant_offset" form. If the base		// decompose the pointer into a "base + constant_offset" form. If the base
// pointers are equal, then we can reason about the two stores.		// pointers are equal, then we can reason about the two stores.
EarlierOff = 0;		DeadOff = 0;
LaterOff = 0;		KillingOff = 0;
const Value *BP1 = GetPointerBaseWithConstantOffset(P1, EarlierOff, DL);		const Value *DeadBasePtr =
const Value *BP2 = GetPointerBaseWithConstantOffset(P2, LaterOff, DL);		GetPointerBaseWithConstantOffset(DeadPtr, DeadOff, DL);
		const Value *KillingBasePtr =
// If the base pointers still differ, we have two completely different stores.		GetPointerBaseWithConstantOffset(KillingPtr, KillingOff, DL);
if (BP1 != BP2)
		// If the base pointers still differ, we have two completely different
		// stores.
		if (DeadBasePtr != KillingBasePtr)
return OW_Unknown;		return OW_Unknown;

// The later access completely overlaps the earlier store if and only if		// The killing access completely overlaps the dead store if and only if
// both start and end of the earlier one is "inside" the later one:		// both start and end of the dead one is "inside" the killing one:
// \|<->\|--earlier--\|<->\|		// \|<->\|--dead--\|<->\|
// \|-------later-------\|		// \|-----killing------\|
// Accesses may overlap if and only if start of one of them is "inside"		// Accesses may overlap if and only if start of one of them is "inside"
// another one:		// another one:
// \|<->\|--earlier--\|<----->\|		// \|<->\|--dead--\|<-------->\|
// \|-------later-------\|		// \|-------killing--------\|
// OR		// OR
// \|----- earlier -----\|		// \|-------dead-------\|
// \|<->\|---later---\|<----->\|		// \|<->\|---killing---\|<----->\|
//		//
// We have to be careful here as Off is signed while .Size is unsigned.		// We have to be careful here as Off is signed while .Size is unsigned.

// Check if the earlier access starts "not before" the later one.		// Check if the dead access starts "not before" the killing one.
if (EarlierOff >= LaterOff) {		if (DeadOff >= KillingOff) {
// If the earlier access ends "not after" the later access then the earlier		// If the dead access ends "not after" the killing access then the
// one is completely overwritten by the later one.		// dead one is completely overwritten by the killing one.
if (uint64_t(EarlierOff - LaterOff) + EarlierSize <= LaterSize)		if (uint64_t(DeadOff - KillingOff) + DeadSize <= KillingSize)
return OW_Complete;		return OW_Complete;
// If start of the earlier access is "before" end of the later access then		// If start of the dead access is "before" end of the killing access
// accesses overlap.		// then accesses overlap.
else if ((uint64_t)(EarlierOff - LaterOff) < LaterSize)		else if ((uint64_t)(DeadOff - KillingOff) < KillingSize)
return OW_MaybePartial;		return OW_MaybePartial;
}		}
// If start of the later access is "before" end of the earlier access then		// If start of the killing access is "before" end of the dead access then
// accesses overlap.		// accesses overlap.
else if ((uint64_t)(LaterOff - EarlierOff) < EarlierSize) {		else if ((uint64_t)(KillingOff - DeadOff) < DeadSize) {
return OW_MaybePartial;		return OW_MaybePartial;
}		}

// Can reach here only if accesses are known not to overlap. There is no		// Can reach here only if accesses are known not to overlap. There is no
// dedicated code to indicate no overlap so signal "unknown".		// dedicated code to indicate no overlap so signal "unknown".
return OW_Unknown;		return OW_Unknown;
}		}

▲ Show 20 Lines • Show All 79 Lines • ▼ Show 20 Lines	if (!UseInst->mayWriteToMemory())
return false;		return false;

if (auto *CB = dyn_cast<CallBase>(UseInst))		if (auto *CB = dyn_cast<CallBase>(UseInst))
if (CB->onlyAccessesInaccessibleMemory())		if (CB->onlyAccessesInaccessibleMemory())
return false;		return false;

int64_t InstWriteOffset, DepWriteOffset;		int64_t InstWriteOffset, DepWriteOffset;
if (auto CC = getLocForWriteEx(UseInst))		if (auto CC = getLocForWriteEx(UseInst))
return isOverwrite(UseInst, DefInst, *CC, DefLoc, DepWriteOffset,		return isOverwrite(UseInst, DefInst, *CC, DefLoc, InstWriteOffset,
InstWriteOffset) == OW_Complete;		DepWriteOffset) == OW_Complete;
return false;		return false;
}		}

/// Returns true if \p Def is not read before returning from the function.		/// Returns true if \p Def is not read before returning from the function.
bool isWriteAtEndOfFunction(MemoryDef *Def) {		bool isWriteAtEndOfFunction(MemoryDef *Def) {
LLVM_DEBUG(dbgs() << " Check if def " << *Def << " ("		LLVM_DEBUG(dbgs() << " Check if def " << *Def << " ("
<< *Def->getMemoryInst()		<< *Def->getMemoryInst()
<< ") is at the end the function \n");		<< ") is at the end the function \n");
▲ Show 20 Lines • Show All 85 Lines • ▼ Show 20 Lines	if (getUnderlyingObject(Loc.Ptr) !=
getUnderlyingObject(MaybeTermLoc->first.Ptr))		getUnderlyingObject(MaybeTermLoc->first.Ptr))
return false;		return false;

auto TermLoc = MaybeTermLoc->first;		auto TermLoc = MaybeTermLoc->first;
if (MaybeTermLoc->second) {		if (MaybeTermLoc->second) {
const Value *LocUO = getUnderlyingObject(Loc.Ptr);		const Value *LocUO = getUnderlyingObject(Loc.Ptr);
return BatchAA.isMustAlias(TermLoc.Ptr, LocUO);		return BatchAA.isMustAlias(TermLoc.Ptr, LocUO);
}		}
int64_t InstWriteOffset, DepWriteOffset;		int64_t InstWriteOffset = 0;
return isOverwrite(MaybeTerm, AccessI, TermLoc, Loc, DepWriteOffset,		int64_t DepWriteOffset = 0;
InstWriteOffset) == OW_Complete;		return isOverwrite(MaybeTerm, AccessI, TermLoc, Loc, InstWriteOffset,
		DepWriteOffset) == OW_Complete;
}		}

// Returns true if \p Use may read from \p DefLoc.		// Returns true if \p Use may read from \p DefLoc.
bool isReadClobber(const MemoryLocation &DefLoc, Instruction *UseInst) {		bool isReadClobber(const MemoryLocation &DefLoc, Instruction *UseInst) {
if (isNoopIntrinsic(UseInst))		if (isNoopIntrinsic(UseInst))
return false;		return false;

// Monotonic or weaker atomic stores can be re-ordered and do not need to be		// Monotonic or weaker atomic stores can be re-ordered and do not need to be
▲ Show 20 Lines • Show All 61 Lines • ▼ Show 20 Lines	if (auto *I = dyn_cast<Instruction>(Ptr)) {
return true;		return true;
}		}
if (auto *GEP = dyn_cast<GEPOperator>(Ptr)) {		if (auto *GEP = dyn_cast<GEPOperator>(Ptr)) {
return IsGuaranteedLoopInvariantBase(GEP->getPointerOperand()) &&		return IsGuaranteedLoopInvariantBase(GEP->getPointerOperand()) &&
GEP->hasAllConstantIndices();		GEP->hasAllConstantIndices();
}		}
return IsGuaranteedLoopInvariantBase(Ptr);		return IsGuaranteedLoopInvariantBase(Ptr);
}		}

// Find a MemoryDef writing to \p DefLoc and dominating \p StartAccess, with		// Find a MemoryDef writing to \p KillingLoc and dominating \p StartAccess,
		fhahnUnsubmitted Done Reply Inline Actions comment here needs also updating fhahn: comment here needs also updating
// no read access between them or on any other path to a function exit block		// with no read access between them or on any other path to a function exit
// if \p DefLoc is not accessible after the function returns. If there is no		// block if \p KillingLoc is not accessible after the function returns. If
// such MemoryDef, return None. The returned value may not (completely)		// there is no such MemoryDef, return None. The returned value may not
// overwrite \p DefLoc. Currently we bail out when we encounter an aliasing		// (completely) overwrite \p KillingLoc. Currently we bail out when we
// MemoryUse (read).		// encounter an aliasing MemoryUse (read).
Optional<MemoryAccess *>		Optional<MemoryAccess *>
getDomMemoryDef(MemoryDef KillingDef, MemoryAccess StartAccess,		getDomMemoryDef(MemoryDef KillingDef, MemoryAccess StartAccess,
const MemoryLocation &DefLoc, const Value *DefUO,		const MemoryLocation &KillingLoc, const Value *KillingUndObj,
unsigned &ScanLimit, unsigned &WalkerStepLimit,		unsigned &ScanLimit, unsigned &WalkerStepLimit,
bool IsMemTerm, unsigned &PartialLimit) {		bool IsMemTerm, unsigned &PartialLimit) {
if (ScanLimit == 0 \|\| WalkerStepLimit == 0) {		if (ScanLimit == 0 \|\| WalkerStepLimit == 0) {
LLVM_DEBUG(dbgs() << "\n ... hit scan limit\n");		LLVM_DEBUG(dbgs() << "\n ... hit scan limit\n");
return None;		return None;
}		}

MemoryAccess *Current = StartAccess;		MemoryAccess *Current = StartAccess;
Show All 35 Lines	for (;; Current = cast<MemoryDef>(Current)->getDefiningAccess()) {
return Current;		return Current;
}		}

// Below, check if CurrentDef is a valid candidate to be eliminated by		// Below, check if CurrentDef is a valid candidate to be eliminated by
// KillingDef. If it is not, check the next candidate.		// KillingDef. If it is not, check the next candidate.
MemoryDef *CurrentDef = cast<MemoryDef>(Current);		MemoryDef *CurrentDef = cast<MemoryDef>(Current);
Instruction *CurrentI = CurrentDef->getMemoryInst();		Instruction *CurrentI = CurrentDef->getMemoryInst();

if (canSkipDef(CurrentDef, !isInvisibleToCallerBeforeRet(DefUO), TLI))		if (canSkipDef(CurrentDef, !isInvisibleToCallerBeforeRet(KillingUndObj),
		TLI))
continue;		continue;

// Before we try to remove anything, check for any extra throwing		// Before we try to remove anything, check for any extra throwing
// instructions that block us from DSEing		// instructions that block us from DSEing
if (mayThrowBetween(KillingI, CurrentI, DefUO)) {		if (mayThrowBetween(KillingI, CurrentI, KillingUndObj)) {
LLVM_DEBUG(dbgs() << " ... skip, may throw!\n");		LLVM_DEBUG(dbgs() << " ... skip, may throw!\n");
return None;		return None;
}		}

// Check for anything that looks like it will be a barrier to further		// Check for anything that looks like it will be a barrier to further
// removal		// removal
if (isDSEBarrier(DefUO, CurrentI)) {		if (isDSEBarrier(KillingUndObj, CurrentI)) {
LLVM_DEBUG(dbgs() << " ... skip, barrier\n");		LLVM_DEBUG(dbgs() << " ... skip, barrier\n");
return None;		return None;
}		}

// If Current is known to be on path that reads DefLoc or is a read		// If Current is known to be on path that reads DefLoc or is a read
// clobber, bail out, as the path is not profitable. We skip this check		// clobber, bail out, as the path is not profitable. We skip this check
// for intrinsic calls, because the code knows how to handle memcpy		// for intrinsic calls, because the code knows how to handle memcpy
// intrinsics.		// intrinsics.
if (!isa<IntrinsicInst>(CurrentI) && isReadClobber(DefLoc, CurrentI))		if (!isa<IntrinsicInst>(CurrentI) && isReadClobber(KillingLoc, CurrentI))
return None;		return None;

// Quick check if there are direct uses that are read-clobbers.		// Quick check if there are direct uses that are read-clobbers.
if (any_of(Current->uses(), [this, &DefLoc, StartAccess](Use &U) {		if (any_of(Current->uses(), [this, &KillingLoc, StartAccess](Use &U) {
if (auto *UseOrDef = dyn_cast<MemoryUseOrDef>(U.getUser()))		if (auto *UseOrDef = dyn_cast<MemoryUseOrDef>(U.getUser()))
return !MSSA.dominates(StartAccess, UseOrDef) &&		return !MSSA.dominates(StartAccess, UseOrDef) &&
isReadClobber(DefLoc, UseOrDef->getMemoryInst());		isReadClobber(KillingLoc, UseOrDef->getMemoryInst());
return false;		return false;
})) {		})) {
LLVM_DEBUG(dbgs() << " ... found a read clobber\n");		LLVM_DEBUG(dbgs() << " ... found a read clobber\n");
return None;		return None;
}		}

// If Current cannot be analyzed or is not removable, check the next		// If Current cannot be analyzed or is not removable, check the next
// candidate.		// candidate.
Show All 16 Lines	for (;; Current = cast<MemoryDef>(Current)->getDefiningAccess()) {

if (IsMemTerm) {		if (IsMemTerm) {
// If the killing def is a memory terminator (e.g. lifetime.end), check		// If the killing def is a memory terminator (e.g. lifetime.end), check
// the next candidate if the current Current does not write the same		// the next candidate if the current Current does not write the same
// underlying object as the terminator.		// underlying object as the terminator.
if (!isMemTerminator(*CurrentLoc, CurrentI, KillingI))		if (!isMemTerminator(*CurrentLoc, CurrentI, KillingI))
continue;		continue;
} else {		} else {
int64_t InstWriteOffset, DepWriteOffset;		int64_t KillingOffset = 0;
auto OR = isOverwrite(KillingI, CurrentI, DefLoc, *CurrentLoc,		int64_t DeadOffset = 0;
DepWriteOffset, InstWriteOffset);		auto OR = isOverwrite(KillingI, CurrentI, KillingLoc, *CurrentLoc,
		KillingOffset, DeadOffset);
// If Current does not write to the same object as KillingDef, check		// If Current does not write to the same object as KillingDef, check
// the next candidate.		// the next candidate.
if (OR == OW_Unknown)		if (OR == OW_Unknown)
continue;		continue;
else if (OR == OW_MaybePartial) {		else if (OR == OW_MaybePartial) {
// If KillingDef only partially overwrites Current, check the next		// If KillingDef only partially overwrites Current, check the next
// candidate if the partial step limit is exceeded. This aggressively		// candidate if the partial step limit is exceeded. This aggressively
// limits the number of candidates for partial store elimination,		// limits the number of candidates for partial store elimination,
// which are less likely to be removable in the end.		// which are less likely to be removable in the end.
if (PartialLimit <= 1) {		if (PartialLimit <= 1) {
WalkerStepLimit -= 1;		WalkerStepLimit -= 1;
continue;		continue;
}		}
PartialLimit -= 1;		PartialLimit -= 1;
}		}
}		}
break;		break;
};		};

// Accesses to objects accessible after the function returns can only be		// Accesses to objects accessible after the function returns can only be
// eliminated if the access is killed along all paths to the exit. Collect		// eliminated if the access is dead along all paths to the exit. Collect
// the blocks with killing (=completely overwriting MemoryDefs) and check if		// the blocks with killing (=completely overwriting MemoryDefs) and check if
// they cover all paths from EarlierAccess to any function exit.		// they cover all paths from MaybeDeadAccess to any function exit.
SmallPtrSet<Instruction *, 16> KillingDefs;		SmallPtrSet<Instruction *, 16> KillingDefs;
KillingDefs.insert(KillingDef->getMemoryInst());		KillingDefs.insert(KillingDef->getMemoryInst());
MemoryAccess *EarlierAccess = Current;		MemoryAccess *MaybeDeadAccess = Current;
Instruction *EarlierMemInst =		MemoryLocation MaybeDeadLoc = *CurrentLoc;
cast<MemoryDef>(EarlierAccess)->getMemoryInst();		Instruction *MaybeDeadI = cast<MemoryDef>(MaybeDeadAccess)->getMemoryInst();
LLVM_DEBUG(dbgs() << " Checking for reads of " << *EarlierAccess << " ("		LLVM_DEBUG(dbgs() << " Checking for reads of " << *MaybeDeadAccess << " ("
<< *EarlierMemInst << ")\n");		<< *MaybeDeadI << ")\n");

SmallSetVector<MemoryAccess *, 32> WorkList;		SmallSetVector<MemoryAccess *, 32> WorkList;
auto PushMemUses = [&WorkList](MemoryAccess *Acc) {		auto PushMemUses = [&WorkList](MemoryAccess *Acc) {
for (Use &U : Acc->uses())		for (Use &U : Acc->uses())
WorkList.insert(cast<MemoryAccess>(U.getUser()));		WorkList.insert(cast<MemoryAccess>(U.getUser()));
};		};
PushMemUses(EarlierAccess);		PushMemUses(MaybeDeadAccess);

// Check if EarlierDef may be read.		// Check if DeadDef may be read.
for (unsigned I = 0; I < WorkList.size(); I++) {		for (unsigned I = 0; I < WorkList.size(); I++) {
MemoryAccess *UseAccess = WorkList[I];		MemoryAccess *UseAccess = WorkList[I];

LLVM_DEBUG(dbgs() << " " << *UseAccess);		LLVM_DEBUG(dbgs() << " " << *UseAccess);
// Bail out if the number of accesses to check exceeds the scan limit.		// Bail out if the number of accesses to check exceeds the scan limit.
if (ScanLimit < (WorkList.size() - I)) {		if (ScanLimit < (WorkList.size() - I)) {
LLVM_DEBUG(dbgs() << "\n ... hit scan limit\n");		LLVM_DEBUG(dbgs() << "\n ... hit scan limit\n");
return None;		return None;
Show All 21 Lines	for (unsigned I = 0; I < WorkList.size(); I++) {
return DT.dominates(KI, UseInst);		return DT.dominates(KI, UseInst);
})) {		})) {
LLVM_DEBUG(dbgs() << " ... skipping, dominated by killing def\n");		LLVM_DEBUG(dbgs() << " ... skipping, dominated by killing def\n");
continue;		continue;
}		}

// A memory terminator kills all preceeding MemoryDefs and all succeeding		// A memory terminator kills all preceeding MemoryDefs and all succeeding
// MemoryAccesses. We do not have to check it's users.		// MemoryAccesses. We do not have to check it's users.
if (isMemTerminator(*CurrentLoc, EarlierMemInst, UseInst)) {		if (isMemTerminator(MaybeDeadLoc, MaybeDeadI, UseInst)) {
LLVM_DEBUG(		LLVM_DEBUG(
dbgs()		dbgs()
<< " ... skipping, memterminator invalidates following accesses\n");		<< " ... skipping, memterminator invalidates following accesses\n");
continue;		continue;
}		}

if (isNoopIntrinsic(cast<MemoryUseOrDef>(UseAccess)->getMemoryInst())) {		if (isNoopIntrinsic(cast<MemoryUseOrDef>(UseAccess)->getMemoryInst())) {
LLVM_DEBUG(dbgs() << " ... adding uses of intrinsic\n");		LLVM_DEBUG(dbgs() << " ... adding uses of intrinsic\n");
PushMemUses(UseAccess);		PushMemUses(UseAccess);
continue;		continue;
}		}

if (UseInst->mayThrow() && !isInvisibleToCallerBeforeRet(DefUO)) {		if (UseInst->mayThrow() && !isInvisibleToCallerBeforeRet(KillingUndObj)) {
LLVM_DEBUG(dbgs() << " ... found throwing instruction\n");		LLVM_DEBUG(dbgs() << " ... found throwing instruction\n");
return None;		return None;
}		}

// Uses which may read the original MemoryDef mean we cannot eliminate the		// Uses which may read the original MemoryDef mean we cannot eliminate the
// original MD. Stop walk.		// original MD. Stop walk.
if (isReadClobber(*CurrentLoc, UseInst)) {		if (isReadClobber(MaybeDeadLoc, UseInst)) {
LLVM_DEBUG(dbgs() << " ... found read clobber\n");		LLVM_DEBUG(dbgs() << " ... found read clobber\n");
return None;		return None;
}		}

// If this worklist walks back to the original memory access (and the		// If this worklist walks back to the original memory access (and the
// pointer is not guarenteed loop invariant) then we cannot assume that a		// pointer is not guarenteed loop invariant) then we cannot assume that a
// store kills itself.		// store kills itself.
if (EarlierAccess == UseAccess &&		if (MaybeDeadAccess == UseAccess &&
!isGuaranteedLoopInvariant(CurrentLoc->Ptr)) {		!isGuaranteedLoopInvariant(MaybeDeadLoc.Ptr)) {
LLVM_DEBUG(dbgs() << " ... found not loop invariant self access\n");		LLVM_DEBUG(dbgs() << " ... found not loop invariant self access\n");
return None;		return None;
}		}
// Otherwise, for the KillingDef and EarlierAccess we only have to check		// Otherwise, for the KillingDef and MaybeDeadAccess we only have to check
// if it reads the memory location.		// if it reads the memory location.
// TODO: It would probably be better to check for self-reads before		// TODO: It would probably be better to check for self-reads before
// calling the function.		// calling the function.
if (KillingDef == UseAccess \|\| EarlierAccess == UseAccess) {		if (KillingDef == UseAccess \|\| MaybeDeadAccess == UseAccess) {
LLVM_DEBUG(dbgs() << " ... skipping killing def/dom access\n");		LLVM_DEBUG(dbgs() << " ... skipping killing def/dom access\n");
continue;		continue;
}		}

// Check all uses for MemoryDefs, except for defs completely overwriting		// Check all uses for MemoryDefs, except for defs completely overwriting
// the original location. Otherwise we have to check uses of all		// the original location. Otherwise we have to check uses of all
// MemoryDefs we discover, including non-aliasing ones. Otherwise we might		// MemoryDefs we discover, including non-aliasing ones. Otherwise we might
// miss cases like the following		// miss cases like the following
// 1 = Def(LoE) ; <----- EarlierDef stores [0,1]		// 1 = Def(LoE) ; <----- DeadDef stores [0,1]
// 2 = Def(1) ; (2, 1) = NoAlias, stores [2,3]		// 2 = Def(1) ; (2, 1) = NoAlias, stores [2,3]
// Use(2) ; MayAlias 2 and 1, loads [0, 3].		// Use(2) ; MayAlias 2 and 1, loads [0, 3].
// (The Use points to the first Def it may alias)		// (The Use points to the first Def it may alias)
// 3 = Def(1) ; <---- Current (3, 2) = NoAlias, (3,1) = MayAlias,		// 3 = Def(1) ; <---- Current (3, 2) = NoAlias, (3,1) = MayAlias,
// stores [0,1]		// stores [0,1]
if (MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess)) {		if (MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess)) {
if (isCompleteOverwrite(*CurrentLoc, EarlierMemInst, UseInst)) {		if (isCompleteOverwrite(MaybeDeadLoc, MaybeDeadI, UseInst)) {
BasicBlock *MaybeKillingBlock = UseInst->getParent();		BasicBlock *MaybeKillingBlock = UseInst->getParent();
if (PostOrderNumbers.find(MaybeKillingBlock)->second <		if (PostOrderNumbers.find(MaybeKillingBlock)->second <
PostOrderNumbers.find(EarlierAccess->getBlock())->second) {		PostOrderNumbers.find(MaybeDeadAccess->getBlock())->second) {
if (!isInvisibleToCallerAfterRet(DefUO)) {		if (!isInvisibleToCallerAfterRet(KillingUndObj)) {
LLVM_DEBUG(dbgs()		LLVM_DEBUG(dbgs()
<< " ... found killing def " << *UseInst << "\n");		<< " ... found killing def " << *UseInst << "\n");
KillingDefs.insert(UseInst);		KillingDefs.insert(UseInst);
}		}
} else {		} else {
LLVM_DEBUG(dbgs()		LLVM_DEBUG(dbgs()
<< " ... found preceeding def " << *UseInst << "\n");		<< " ... found preceeding def " << *UseInst << "\n");
return None;		return None;
}		}
} else		} else
PushMemUses(UseDef);		PushMemUses(UseDef);
}		}
}		}

// For accesses to locations visible after the function returns, make sure		// For accesses to locations visible after the function returns, make sure
// that the location is killed (=overwritten) along all paths from		// that the location is dead (=overwritten) along all paths from
// EarlierAccess to the exit.		// MaybeDeadAccess to the exit.
if (!isInvisibleToCallerAfterRet(DefUO)) {		if (!isInvisibleToCallerAfterRet(KillingUndObj)) {
SmallPtrSet<BasicBlock *, 16> KillingBlocks;		SmallPtrSet<BasicBlock *, 16> KillingBlocks;
for (Instruction *KD : KillingDefs)		for (Instruction *KD : KillingDefs)
KillingBlocks.insert(KD->getParent());		KillingBlocks.insert(KD->getParent());
assert(!KillingBlocks.empty() &&		assert(!KillingBlocks.empty() &&
"Expected at least a single killing block");		"Expected at least a single killing block");

// Find the common post-dominator of all killing blocks.		// Find the common post-dominator of all killing blocks.
BasicBlock CommonPred = KillingBlocks.begin();		BasicBlock CommonPred = KillingBlocks.begin();
for (BasicBlock *BB : llvm::drop_begin(KillingBlocks)) {		for (BasicBlock *BB : llvm::drop_begin(KillingBlocks)) {
if (!CommonPred)		if (!CommonPred)
break;		break;
CommonPred = PDT.findNearestCommonDominator(CommonPred, BB);		CommonPred = PDT.findNearestCommonDominator(CommonPred, BB);
}		}

// If CommonPred is in the set of killing blocks, just check if it		// If CommonPred is in the set of killing blocks, just check if it
// post-dominates EarlierAccess.		// post-dominates MaybeDeadAccess.
if (KillingBlocks.count(CommonPred)) {		if (KillingBlocks.count(CommonPred)) {
if (PDT.dominates(CommonPred, EarlierAccess->getBlock()))		if (PDT.dominates(CommonPred, MaybeDeadAccess->getBlock()))
return {EarlierAccess};		return {MaybeDeadAccess};
return None;		return None;
}		}

// If the common post-dominator does not post-dominate EarlierAccess,		// If the common post-dominator does not post-dominate MaybeDeadAccess,
// there is a path from EarlierAccess to an exit not going through a		// there is a path from MaybeDeadAccess to an exit not going through a
// killing block.		// killing block.
if (PDT.dominates(CommonPred, EarlierAccess->getBlock())) {		if (PDT.dominates(CommonPred, MaybeDeadAccess->getBlock())) {
SetVector<BasicBlock *> WorkList;		SetVector<BasicBlock *> WorkList;

// If CommonPred is null, there are multiple exits from the function.		// If CommonPred is null, there are multiple exits from the function.
// They all have to be added to the worklist.		// They all have to be added to the worklist.
if (CommonPred)		if (CommonPred)
WorkList.insert(CommonPred);		WorkList.insert(CommonPred);
else		else
for (BasicBlock *R : PDT.roots())		for (BasicBlock *R : PDT.roots())
WorkList.insert(R);		WorkList.insert(R);

NumCFGTries++;		NumCFGTries++;
// Check if all paths starting from an exit node go through one of the		// Check if all paths starting from an exit node go through one of the
// killing blocks before reaching EarlierAccess.		// killing blocks before reaching MaybeDeadAccess.
for (unsigned I = 0; I < WorkList.size(); I++) {		for (unsigned I = 0; I < WorkList.size(); I++) {
NumCFGChecks++;		NumCFGChecks++;
BasicBlock *Current = WorkList[I];		BasicBlock *Current = WorkList[I];
if (KillingBlocks.count(Current))		if (KillingBlocks.count(Current))
continue;		continue;
if (Current == EarlierAccess->getBlock())		if (Current == MaybeDeadAccess->getBlock())
return None;		return None;

// EarlierAccess is reachable from the entry, so we don't have to		// MaybeDeadAccess is reachable from the entry, so we don't have to
// explore unreachable blocks further.		// explore unreachable blocks further.
if (!DT.isReachableFromEntry(Current))		if (!DT.isReachableFromEntry(Current))
continue;		continue;

for (BasicBlock *Pred : predecessors(Current))		for (BasicBlock *Pred : predecessors(Current))
WorkList.insert(Pred);		WorkList.insert(Pred);

if (WorkList.size() >= MemorySSAPathCheckLimit)		if (WorkList.size() >= MemorySSAPathCheckLimit)
return None;		return None;
}		}
NumCFGSuccess++;		NumCFGSuccess++;
return {EarlierAccess};		return {MaybeDeadAccess};
}		}
return None;		return None;
}		}

// No aliasing MemoryUses of EarlierAccess found, EarlierAccess is		// No aliasing MemoryUses of MaybeDeadAccess found, MaybeDeadAccess is
// potentially dead.		// potentially dead.
return {EarlierAccess};		return {MaybeDeadAccess};
}		}

// Delete dead memory defs		// Delete dead memory defs
void deleteDeadInstruction(Instruction *SI) {		void deleteDeadInstruction(Instruction *SI) {
MemorySSAUpdater Updater(&MSSA);		MemorySSAUpdater Updater(&MSSA);
SmallVector<Instruction *, 32> NowDeadInsts;		SmallVector<Instruction *, 32> NowDeadInsts;
NowDeadInsts.push_back(SI);		NowDeadInsts.push_back(SI);
--NumFastOther;		--NumFastOther;
Show All 24 Lines	while (!NowDeadInsts.empty()) {
if (isInstructionTriviallyDead(OpI, &TLI))		if (isInstructionTriviallyDead(OpI, &TLI))
NowDeadInsts.push_back(OpI);		NowDeadInsts.push_back(OpI);
}		}

DeadInst->eraseFromParent();		DeadInst->eraseFromParent();
}		}
}		}

// Check for any extra throws between SI and NI that block DSE. This only		// Check for any extra throws between \p KillingI and \p DeadI that block
// checks extra maythrows (those that aren't MemoryDef's). MemoryDef that may		// DSE. This only checks extra maythrows (those that aren't MemoryDef's).
// throw are handled during the walk from one def to the next.		// MemoryDef that may throw are handled during the walk from one def to the
bool mayThrowBetween(Instruction SI, Instruction NI,		// next.
const Value *SILocUnd) {		bool mayThrowBetween(Instruction KillingI, Instruction DeadI,
// First see if we can ignore it by using the fact that SI is an		const Value *KillingUndObj) {
		// First see if we can ignore it by using the fact that KillingI is an
// alloca/alloca like object that is not visible to the caller during		// alloca/alloca like object that is not visible to the caller during
// execution of the function.		// execution of the function.
if (SILocUnd && isInvisibleToCallerBeforeRet(SILocUnd))		if (KillingUndObj && isInvisibleToCallerBeforeRet(KillingUndObj))
return false;		return false;

if (SI->getParent() == NI->getParent())		if (KillingI->getParent() == DeadI->getParent())
return ThrowingBlocks.count(SI->getParent());		return ThrowingBlocks.count(KillingI->getParent());
return !ThrowingBlocks.empty();		return !ThrowingBlocks.empty();
}		}

// Check if \p NI acts as a DSE barrier for \p SI. The following instructions		// Check if \p DeadI acts as a DSE barrier for \p KillingI. The following
// act as barriers:		// instructions act as barriers:
// * A memory instruction that may throw and \p SI accesses a non-stack		// * A memory instruction that may throw and \p KillingI accesses a non-stack
// object.		// object.
// * Atomic stores stronger that monotonic.		// * Atomic stores stronger that monotonic.
bool isDSEBarrier(const Value SILocUnd, Instruction NI) {		bool isDSEBarrier(const Value KillingUndObj, Instruction DeadI) {
// If NI may throw it acts as a barrier, unless we are to an alloca/alloca		// If DeadI may throw it acts as a barrier, unless we are to an
// like object that does not escape.		// alloca/alloca like object that does not escape.
if (NI->mayThrow() && !isInvisibleToCallerBeforeRet(SILocUnd))		if (DeadI->mayThrow() && !isInvisibleToCallerBeforeRet(KillingUndObj))
return true;		return true;

// If NI is an atomic load/store stronger than monotonic, do not try to		// If DeadI is an atomic load/store stronger than monotonic, do not try to
// eliminate/reorder it.		// eliminate/reorder it.
if (NI->isAtomic()) {		if (DeadI->isAtomic()) {
if (auto *LI = dyn_cast<LoadInst>(NI))		if (auto *LI = dyn_cast<LoadInst>(DeadI))
return isStrongerThanMonotonic(LI->getOrdering());		return isStrongerThanMonotonic(LI->getOrdering());
if (auto *SI = dyn_cast<StoreInst>(NI))		if (auto *SI = dyn_cast<StoreInst>(DeadI))
return isStrongerThanMonotonic(SI->getOrdering());		return isStrongerThanMonotonic(SI->getOrdering());
if (auto *ARMW = dyn_cast<AtomicRMWInst>(NI))		if (auto *ARMW = dyn_cast<AtomicRMWInst>(DeadI))
return isStrongerThanMonotonic(ARMW->getOrdering());		return isStrongerThanMonotonic(ARMW->getOrdering());
if (auto *CmpXchg = dyn_cast<AtomicCmpXchgInst>(NI))		if (auto *CmpXchg = dyn_cast<AtomicCmpXchgInst>(DeadI))
return isStrongerThanMonotonic(CmpXchg->getSuccessOrdering()) \|\|		return isStrongerThanMonotonic(CmpXchg->getSuccessOrdering()) \|\|
isStrongerThanMonotonic(CmpXchg->getFailureOrdering());		isStrongerThanMonotonic(CmpXchg->getFailureOrdering());
llvm_unreachable("other instructions should be skipped in MemorySSA");		llvm_unreachable("other instructions should be skipped in MemorySSA");
}		}
return false;		return false;
}		}

/// Eliminate writes to objects that are not visible in the caller and are not		/// Eliminate writes to objects that are not visible in the caller and are not
▲ Show 20 Lines • Show All 159 Lines • ▼ Show 20 Lines	static bool eliminateDeadStores(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
bool MadeChange = false;		bool MadeChange = false;

DSEState State = DSEState::get(F, AA, MSSA, DT, PDT, TLI, LI);		DSEState State = DSEState::get(F, AA, MSSA, DT, PDT, TLI, LI);
// For each store:		// For each store:
for (unsigned I = 0; I < State.MemDefs.size(); I++) {		for (unsigned I = 0; I < State.MemDefs.size(); I++) {
MemoryDef *KillingDef = State.MemDefs[I];		MemoryDef *KillingDef = State.MemDefs[I];
if (State.SkipStores.count(KillingDef))		if (State.SkipStores.count(KillingDef))
continue;		continue;
Instruction *SI = KillingDef->getMemoryInst();		Instruction *KillingI = KillingDef->getMemoryInst();

Optional<MemoryLocation> MaybeSILoc;		Optional<MemoryLocation> MaybeKillingLoc;
if (State.isMemTerminatorInst(SI))		if (State.isMemTerminatorInst(KillingI))
MaybeSILoc = State.getLocForTerminator(SI).map(		MaybeKillingLoc = State.getLocForTerminator(KillingI).map(
[](const std::pair<MemoryLocation, bool> &P) { return P.first; });		[](const std::pair<MemoryLocation, bool> &P) { return P.first; });
else		else
MaybeSILoc = State.getLocForWriteEx(SI);		MaybeKillingLoc = State.getLocForWriteEx(KillingI);

if (!MaybeSILoc) {		if (!MaybeKillingLoc) {
LLVM_DEBUG(dbgs() << "Failed to find analyzable write location for "		LLVM_DEBUG(dbgs() << "Failed to find analyzable write location for "
<< *SI << "\n");		<< *KillingI << "\n");
continue;		continue;
}		}
MemoryLocation SILoc = *MaybeSILoc;		MemoryLocation KillingLoc = *MaybeKillingLoc;
assert(SILoc.Ptr && "SILoc should not be null");		assert(KillingLoc.Ptr && "KillingLoc should not be null");
const Value *SILocUnd = getUnderlyingObject(SILoc.Ptr);		const Value *KillingUndObj = getUnderlyingObject(KillingLoc.Ptr);

MemoryAccess *Current = KillingDef;		MemoryAccess *Current = KillingDef;
LLVM_DEBUG(dbgs() << "Trying to eliminate MemoryDefs killed by "		LLVM_DEBUG(dbgs() << "Trying to eliminate MemoryDefs killed by "
<< Current << " (" << SI << ")\n");		<< KillingDef << " (" << KillingI << ")\n");

unsigned ScanLimit = MemorySSAScanLimit;		unsigned ScanLimit = MemorySSAScanLimit;
unsigned WalkerStepLimit = MemorySSAUpwardsStepLimit;		unsigned WalkerStepLimit = MemorySSAUpwardsStepLimit;
unsigned PartialLimit = MemorySSAPartialStoreLimit;		unsigned PartialLimit = MemorySSAPartialStoreLimit;
// Worklist of MemoryAccesses that may be killed by KillingDef.		// Worklist of MemoryAccesses that may be killed by KillingDef.
SetVector<MemoryAccess *> ToCheck;		SetVector<MemoryAccess *> ToCheck;

if (SILocUnd)		if (KillingUndObj)
ToCheck.insert(KillingDef->getDefiningAccess());		ToCheck.insert(KillingDef->getDefiningAccess());

bool Shortend = false;		bool Shortend = false;
bool IsMemTerm = State.isMemTerminatorInst(SI);		bool IsMemTerm = State.isMemTerminatorInst(KillingI);
// Check if MemoryAccesses in the worklist are killed by KillingDef.		// Check if MemoryAccesses in the worklist are killed by KillingDef.
for (unsigned I = 0; I < ToCheck.size(); I++) {		for (unsigned I = 0; I < ToCheck.size(); I++) {
Current = ToCheck[I];		Current = ToCheck[I];
if (State.SkipStores.count(Current))		if (State.SkipStores.count(Current))
continue;		continue;

Optional<MemoryAccess *> Next = State.getDomMemoryDef(		Optional<MemoryAccess *> MaybeDeadAccess = State.getDomMemoryDef(
KillingDef, Current, SILoc, SILocUnd, ScanLimit, WalkerStepLimit,		KillingDef, Current, KillingLoc, KillingUndObj, ScanLimit,
IsMemTerm, PartialLimit);		WalkerStepLimit, IsMemTerm, PartialLimit);

if (!Next) {		if (!MaybeDeadAccess) {
LLVM_DEBUG(dbgs() << " finished walk\n");		LLVM_DEBUG(dbgs() << " finished walk\n");
continue;		continue;
}		}

MemoryAccess EarlierAccess = Next;		MemoryAccess DeadAccess = MaybeDeadAccess;
LLVM_DEBUG(dbgs() << " Checking if we can kill " << *EarlierAccess);		LLVM_DEBUG(dbgs() << " Checking if we can kill " << *DeadAccess);
if (isa<MemoryPhi>(EarlierAccess)) {		if (isa<MemoryPhi>(DeadAccess)) {
LLVM_DEBUG(dbgs() << "\n ... adding incoming values to worklist\n");		LLVM_DEBUG(dbgs() << "\n ... adding incoming values to worklist\n");
for (Value *V : cast<MemoryPhi>(EarlierAccess)->incoming_values()) {		for (Value *V : cast<MemoryPhi>(DeadAccess)->incoming_values()) {
MemoryAccess *IncomingAccess = cast<MemoryAccess>(V);		MemoryAccess *IncomingAccess = cast<MemoryAccess>(V);
BasicBlock *IncomingBlock = IncomingAccess->getBlock();		BasicBlock *IncomingBlock = IncomingAccess->getBlock();
BasicBlock *PhiBlock = EarlierAccess->getBlock();		BasicBlock *PhiBlock = DeadAccess->getBlock();

// We only consider incoming MemoryAccesses that come before the		// We only consider incoming MemoryAccesses that come before the
// MemoryPhi. Otherwise we could discover candidates that do not		// MemoryPhi. Otherwise we could discover candidates that do not
// strictly dominate our starting def.		// strictly dominate our starting def.
if (State.PostOrderNumbers[IncomingBlock] >		if (State.PostOrderNumbers[IncomingBlock] >
State.PostOrderNumbers[PhiBlock])		State.PostOrderNumbers[PhiBlock])
ToCheck.insert(IncomingAccess);		ToCheck.insert(IncomingAccess);
}		}
continue;		continue;
}		}
auto *NextDef = cast<MemoryDef>(EarlierAccess);		auto *DeadDefAccess = cast<MemoryDef>(DeadAccess);
Instruction *NI = NextDef->getMemoryInst();		Instruction *DeadI = DeadDefAccess->getMemoryInst();
LLVM_DEBUG(dbgs() << " (" << *NI << ")\n");		LLVM_DEBUG(dbgs() << " (" << *DeadI << ")\n");
ToCheck.insert(NextDef->getDefiningAccess());		ToCheck.insert(DeadDefAccess->getDefiningAccess());
NumGetDomMemoryDefPassed++;		NumGetDomMemoryDefPassed++;

if (!DebugCounter::shouldExecute(MemorySSACounter))		if (!DebugCounter::shouldExecute(MemorySSACounter))
continue;		continue;

MemoryLocation NILoc = *State.getLocForWriteEx(NI);		MemoryLocation DeadLoc = *State.getLocForWriteEx(DeadI);

if (IsMemTerm) {		if (IsMemTerm) {
const Value *NIUnd = getUnderlyingObject(NILoc.Ptr);		const Value *DeadUndObj = getUnderlyingObject(DeadLoc.Ptr);
if (SILocUnd != NIUnd)		if (KillingUndObj != DeadUndObj)
continue;		continue;
LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n DEAD: " << *NI		LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n DEAD: " << *DeadI
<< "\n KILLER: " << *SI << '\n');		<< "\n KILLER: " << *KillingI << '\n');
State.deleteDeadInstruction(NI);		State.deleteDeadInstruction(DeadI);
++NumFastStores;		++NumFastStores;
MadeChange = true;		MadeChange = true;
} else {		} else {
// Check if NI overwrites SI.		// Check if DeadI overwrites KillingI.
int64_t InstWriteOffset, DepWriteOffset;		int64_t KillingOffset = 0;
OverwriteResult OR = State.isOverwrite(SI, NI, SILoc, NILoc,		int64_t DeadOffset = 0;
DepWriteOffset, InstWriteOffset);		OverwriteResult OR = State.isOverwrite(
		KillingI, DeadI, KillingLoc, DeadLoc, KillingOffset, DeadOffset);
if (OR == OW_MaybePartial) {		if (OR == OW_MaybePartial) {
auto Iter = State.IOLs.insert(		auto Iter = State.IOLs.insert(
std::make_pair<BasicBlock *, InstOverlapIntervalsTy>(		std::make_pair<BasicBlock *, InstOverlapIntervalsTy>(
NI->getParent(), InstOverlapIntervalsTy()));		DeadI->getParent(), InstOverlapIntervalsTy()));
auto &IOL = Iter.first->second;		auto &IOL = Iter.first->second;
OR = isPartialOverwrite(SILoc, NILoc, DepWriteOffset, InstWriteOffset,		OR = isPartialOverwrite(KillingLoc, DeadLoc, KillingOffset,
NI, IOL);		DeadOffset, DeadI, IOL);
}		}

if (EnablePartialStoreMerging && OR == OW_PartialEarlierWithFullLater) {		if (EnablePartialStoreMerging && OR == OW_PartialEarlierWithFullLater) {
auto *Earlier = dyn_cast<StoreInst>(NI);		auto *DeadSI = dyn_cast<StoreInst>(DeadI);
auto *Later = dyn_cast<StoreInst>(SI);		auto *KillingSI = dyn_cast<StoreInst>(KillingI);
// We are re-using tryToMergePartialOverlappingStores, which requires		// We are re-using tryToMergePartialOverlappingStores, which requires
// Earlier to domiante Later.		// DeadSI to dominate DeadSI.
// TODO: implement tryToMergeParialOverlappingStores using MemorySSA.		// TODO: implement tryToMergeParialOverlappingStores using MemorySSA.
if (Earlier && Later && DT.dominates(Earlier, Later)) {		if (DeadSI && KillingSI && DT.dominates(DeadSI, KillingSI)) {
if (Constant *Merged = tryToMergePartialOverlappingStores(		if (Constant *Merged = tryToMergePartialOverlappingStores(
Earlier, Later, InstWriteOffset, DepWriteOffset, State.DL,		KillingSI, DeadSI, KillingOffset, DeadOffset, State.DL,
State.BatchAA, &DT)) {		State.BatchAA, &DT)) {

// Update stored value of earlier store to merged constant.		// Update stored value of earlier store to merged constant.
Earlier->setOperand(0, Merged);		DeadSI->setOperand(0, Merged);
++NumModifiedStores;		++NumModifiedStores;
MadeChange = true;		MadeChange = true;

Shortend = true;		Shortend = true;
// Remove later store and remove any outstanding overlap intervals		// Remove killing store and remove any outstanding overlap
// for the updated store.		// intervals for the updated store.
State.deleteDeadInstruction(Later);		State.deleteDeadInstruction(KillingSI);
auto I = State.IOLs.find(Earlier->getParent());		auto I = State.IOLs.find(DeadSI->getParent());
if (I != State.IOLs.end())		if (I != State.IOLs.end())
I->second.erase(Earlier);		I->second.erase(DeadSI);
break;		break;
}		}
}		}
}		}

if (OR == OW_Complete) {		if (OR == OW_Complete) {
LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n DEAD: " << *NI		LLVM_DEBUG(dbgs() << "DSE: Remove Dead Store:\n DEAD: " << *DeadI
<< "\n KILLER: " << *SI << '\n');		<< "\n KILLER: " << *KillingI << '\n');
State.deleteDeadInstruction(NI);		State.deleteDeadInstruction(DeadI);
++NumFastStores;		++NumFastStores;
MadeChange = true;		MadeChange = true;
}		}
}		}
}		}

// Check if the store is a no-op.		// Check if the store is a no-op.
if (!Shortend && isRemovable(SI) &&		if (!Shortend && isRemovable(KillingI) &&
State.storeIsNoop(KillingDef, SILocUnd)) {		State.storeIsNoop(KillingDef, KillingUndObj)) {
LLVM_DEBUG(dbgs() << "DSE: Remove No-Op Store:\n DEAD: " << *SI << '\n');		LLVM_DEBUG(dbgs() << "DSE: Remove No-Op Store:\n DEAD: " << *KillingI
State.deleteDeadInstruction(SI);		<< '\n');
		State.deleteDeadInstruction(KillingI);
NumRedundantStores++;		NumRedundantStores++;
MadeChange = true;		MadeChange = true;
continue;		continue;
}		}
}		}

if (EnablePartialOverwriteTracking)		if (EnablePartialOverwriteTracking)
for (auto &KV : State.IOLs)		for (auto &KV : State.IOLs)
▲ Show 20 Lines • Show All 107 Lines • Show Last 20 Lines

This is an archive of the discontinued LLVM Phabricator instance.

[DSE][NFC] Rename Later->Killing, Earlier->Dead
ClosedPublic

Details

Diff Detail

Event Timeline

Revision Contents

Diff 373788

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

This is an archive of the discontinued LLVM Phabricator instance.

[DSE][NFC] Rename Later->Killing, Earlier->DeadClosedPublic

Details

Diff Detail

Event Timeline

Revision Contents

Diff 373788

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

[DSE][NFC] Rename Later->Killing, Earlier->Dead
ClosedPublic