This is an archive of the discontinued LLVM Phabricator instance.

Differential D101391

[DSE] Eliminate zero memset after calloc
ClosedPublic

Authored by xbolva00 on Apr 27 2021, 12:31 PM.

Details

Reviewers
fhahn
nikic
Commits
rGe81819377ece: [DSE] Eliminate zero memset after calloc
Summary

Solves PR11896

As noted, this can be improved futher (calloc -> malloc) in some cases. But for know, this is the first step.

Diff Detail

Event Timeline

xbolva00 created this revision.Apr 27 2021, 12:31 PM
Herald added a subscriber: hiraditya. · View Herald TranscriptApr 27 2021, 12:31 PM
xbolva00 requested review of this revision.Apr 27 2021, 12:31 PM
Herald added a project: Restricted Project. · View Herald TranscriptApr 27 2021, 12:31 PM
Herald added a subscriber: llvm-commits. · View Herald Transcript
Harbormaster completed remote builds in B101238: Diff 340942.Apr 27 2021, 12:32 PM
xbolva00 added a comment.Apr 27 2021, 12:35 PM

As I worked on this PR, I found a regression where we fail to eliminate stores/memset due to inaccessiblememonly on calloc. (store_zero_after_calloc_inaccessiblememonly & zero_memset_after_calloc_inaccessiblememonly)

Please check https://bugs.llvm.org/show_bug.cgi?id=50143 (but this patch can be reviewed and pushed separately).

nikic added a subscriber: nikic.Apr 27 2021, 1:16 PM

I think it would be good to add a negative test where there is a store to the calloc in the meantime.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp
1783

nit: unnecessary newline.

xbolva00 added a comment.Apr 27 2021, 1:32 PM
In D101391#2720758, @nikic wrote:

I think it would be good to add a negative test where there is a store to the calloc in the meantime.

zero_memset_and_store_after_calloc?
store is killed by memset and then we have a calloc with memset.

In D101391#2720758, @nikic wrote:

I think it would be good to add a negative test where there is a store to the calloc in the meantime.

Yes, good idea. Prepared partial_zero_memset_and_store_after_calloc and zero_memset_and_store_with_dyn_index_after_calloc.

xbolva00 updated this revision to Diff 340969.Apr 27 2021, 1:34 PM

New testcases + fixed nit.

Harbormaster completed remote builds in B101255: Diff 340969.Apr 27 2021, 1:35 PM
xbolva00 updated this revision to Diff 340976.Apr 27 2021, 1:43 PM

Cleanup tests for easier review.

Harbormaster completed remote builds in B101260: Diff 340976.Apr 27 2021, 1:44 PM
nikic accepted this revision.Apr 27 2021, 2:12 PM

LGTM

llvm/test/Transforms/DeadStoreElimination/noop-stores.ll
387

I'd suggest adding a variant that stores a constant but non-zero value (e.g. i8 1).

It may also be worthwhile to make sure that passing i1 true for the volatile flag will prevent DSE (this should be covered by the isRemovable check in the caller).

This revision is now accepted and ready to land.Apr 27 2021, 2:12 PM
xbolva00 updated this revision to Diff 340984.Apr 27 2021, 2:18 PM

Added suggested tests

xbolva00 marked an inline comment as done.Apr 27 2021, 2:19 PM
xbolva00 added inline comments.
llvm/test/Transforms/DeadStoreElimination/noop-stores.ll
387

Sure, I will add such tests.

Harbormaster completed remote builds in B101265: Diff 340984.Apr 27 2021, 5:44 PM
This revision was landed with ongoing or failed builds.Apr 27 2021, 6:31 PM
Closed by commit rGe81819377ece: [DSE] Eliminate zero memset after calloc (authored by xbolva00). · Explain Why
This revision was automatically updated to reflect the committed changes.
xbolva00 marked an inline comment as done.
xbolva00 added a commit: rGe81819377ece: [DSE] Eliminate zero memset after calloc.
yurai007 mentioned this in D101176: [SimplifyLibCalls] Transform malloc to calloc with redundant memsets elimination (PR25892).May 7 2021, 4:55 AM

Revision Contents

PathSize
llvm/
lib/
Transforms/
Scalar/
31 lines
test/
Transforms/
DeadStoreElimination/
73 lines

Diff 340969

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

Show First 20 Lines • Show All 991 Lines • ▼ Show 20 Lines
return MadeChange; return MadeChange;
} }
/// \returns true if \p Def is a no-op store, either because it /// \returns true if \p Def is a no-op store, either because it
/// directly stores back a loaded value or stores zero to a calloced object. /// directly stores back a loaded value or stores zero to a calloced object.
bool storeIsNoop(MemoryDef *Def, const MemoryLocation &DefLoc, bool storeIsNoop(MemoryDef *Def, const MemoryLocation &DefLoc,
const Value *DefUO) { const Value *DefUO) {
StoreInst *Store = dyn_cast<StoreInst>(Def->getMemoryInst()); StoreInst *Store = dyn_cast<StoreInst>(Def->getMemoryInst());
MemSetInst *MemSet = dyn_cast<MemSetInst>(Def->getMemoryInst());
Constant *StoredConstant = nullptr;
if (Store)
StoredConstant = dyn_cast<Constant>(Store->getOperand(0));
if (MemSet)
StoredConstant = dyn_cast<Constant>(MemSet->getValue());
if (StoredConstant && StoredConstant->isNullValue()) {
auto *DefUOInst = dyn_cast<Instruction>(DefUO);
if (DefUOInst && isCallocLikeFn(DefUOInst, &TLI)) {
auto *UnderlyingDef = cast<MemoryDef>(MSSA.getMemoryAccess(DefUOInst));
nikicUnsubmitted
Not Done
ReplyInline Actions

nit: unnecessary newline.

nikic: nit: unnecessary newline.
// If UnderlyingDef is the clobbering access of Def, no instructions
// between them can modify the memory location.
auto *ClobberDef =
MSSA.getSkipSelfWalker()->getClobberingMemoryAccess(Def);
return UnderlyingDef == ClobberDef;
}
}
if (!Store) if (!Store)
return false; return false;
if (auto *LoadI = dyn_cast<LoadInst>(Store->getOperand(0))) { if (auto *LoadI = dyn_cast<LoadInst>(Store->getOperand(0))) {
if (LoadI->getPointerOperand() == Store->getOperand(1)) { if (LoadI->getPointerOperand() == Store->getOperand(1)) {
// Get the defining access for the load. // Get the defining access for the load.
auto *LoadAccess = MSSA.getMemoryAccess(LoadI)->getDefiningAccess(); auto *LoadAccess = MSSA.getMemoryAccess(LoadI)->getDefiningAccess();
// Fast path: the defining accesses are the same. // Fast path: the defining accesses are the same.
Show All 31 Lines
// noop. Otherwise, fail. // noop. Otherwise, fail.
if (LoadAccess != Current) if (LoadAccess != Current)
return false; return false;
} }
return true; return true;
} }
} }
Constant *StoredConstant = dyn_cast<Constant>(Store->getOperand(0));
if (StoredConstant && StoredConstant->isNullValue()) {
auto *DefUOInst = dyn_cast<Instruction>(DefUO);
if (DefUOInst && isCallocLikeFn(DefUOInst, &TLI)) {
auto *UnderlyingDef = cast<MemoryDef>(MSSA.getMemoryAccess(DefUOInst));
// If UnderlyingDef is the clobbering access of Def, no instructions
// between them can modify the memory location.
auto *ClobberDef =
MSSA.getSkipSelfWalker()->getClobberingMemoryAccess(Def);
return UnderlyingDef == ClobberDef;
}
}
return false; return false;
} }
}; };
bool eliminateDeadStores(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, bool eliminateDeadStores(Function &F, AliasAnalysis &AA, MemorySSA &MSSA,
DominatorTree &DT, PostDominatorTree &PDT, DominatorTree &DT, PostDominatorTree &PDT,
const TargetLibraryInfo &TLI) { const TargetLibraryInfo &TLI) {
bool MadeChange = false; bool MadeChange = false;
▲ Show 20 Lines • Show All 261 Lines • Show Last 20 Lines

llvm/test/Transforms/DeadStoreElimination/noop-stores.ll

Show First 20 Lines • Show All 319 Lines • ▼ Show 20 Lines;
store i8 0, i8* %call store i8 0, i8* %call
ret i8* %call ret i8* %call
} }
define i8* @zero_memset_after_calloc() { define i8* @zero_memset_after_calloc() {
; CHECK-LABEL: @zero_memset_after_calloc( ; CHECK-LABEL: @zero_memset_after_calloc(
; CHECK-NEXT: [[CALL:%.*]] = tail call i8* @calloc(i64 10000, i64 4) ; CHECK-NEXT: [[CALL:%.*]] = tail call i8* @calloc(i64 10000, i64 4)
; CHECK-NEXT: [[L0:%.*]] = bitcast i8* [[CALL]] to i32* ; CHECK-NEXT: [[L0:%.*]] = bitcast i8* [[CALL]] to i32*
; CHECK-NEXT: call void @llvm.memset.p0i8.i64(i8* [[CALL]], i8 0, i64 40000, i1 false)
; CHECK-NEXT: ret i8* [[CALL]] ; CHECK-NEXT: ret i8* [[CALL]]
; ;
%call = tail call i8* @calloc(i64 10000, i64 4) %call = tail call i8* @calloc(i64 10000, i64 4)
%l0 = bitcast i8* %call to i32* %l0 = bitcast i8* %call to i32*
call void @llvm.memset.p0i8.i64(i8* %call, i8 0, i64 40000, i1 false) call void @llvm.memset.p0i8.i64(i8* %call, i8 0, i64 40000, i1 false)
ret i8* %call ret i8* %call
} }
define i8* @zero_memset_and_store_after_calloc(i8 %v) { define i8* @zero_memset_and_store_after_calloc(i8 %v) {
; CHECK-LABEL: @zero_memset_and_store_after_calloc( ; CHECK-LABEL: @zero_memset_and_store_after_calloc(
; CHECK-NEXT: [[CALL:%.*]] = tail call i8* @calloc(i64 10000, i64 4) ; CHECK-NEXT: [[CALL:%.*]] = tail call i8* @calloc(i64 10000, i64 4)
; CHECK-NEXT: [[L0:%.*]] = bitcast i8* [[CALL]] to i32* ; CHECK-NEXT: [[L0:%.*]] = bitcast i8* [[CALL]] to i32*
; CHECK-NEXT: call void @llvm.memset.p0i8.i64(i8* [[CALL]], i8 0, i64 40000, i1 false)
; CHECK-NEXT: ret i8* [[CALL]] ; CHECK-NEXT: ret i8* [[CALL]]
; ;
%call = tail call i8* @calloc(i64 10000, i64 4) %call = tail call i8* @calloc(i64 10000, i64 4)
store i8 %v, i8* %call store i8 %v, i8* %call
%l0 = bitcast i8* %call to i32* %l0 = bitcast i8* %call to i32*
call void @llvm.memset.p0i8.i64(i8* %call, i8 0, i64 40000, i1 false) call void @llvm.memset.p0i8.i64(i8* %call, i8 0, i64 40000, i1 false)
ret i8* %call ret i8* %call
} }
define i8* @zero_memset_after_calloc_inaccessiblememonly() { define i8* @partial_zero_memset_after_calloc() {
; CHECK-LABEL: @zero_memset_after_calloc_inaccessiblememonly( ; CHECK-LABEL: @partial_zero_memset_after_calloc(
; CHECK-NEXT: [[CALL:%.*]] = tail call i8* @calloc(i64 10000, i64 4) #[[ATTR6]] ; CHECK-NEXT: [[CALL:%.*]] = tail call i8* @calloc(i64 10000, i64 4)
; CHECK-NEXT: [[L0:%.*]] = bitcast i8* [[CALL]] to i32* ; CHECK-NEXT: [[L0:%.*]] = bitcast i8* [[CALL]] to i32*
; CHECK-NEXT: call void @llvm.memset.p0i8.i64(i8* [[CALL]], i8 0, i64 40000, i1 false)
; CHECK-NEXT: ret i8* [[CALL]] ; CHECK-NEXT: ret i8* [[CALL]]
; ;
%call = tail call i8* @calloc(i64 10000, i64 4) inaccessiblememonly %call = tail call i8* @calloc(i64 10000, i64 4)
%l0 = bitcast i8* %call to i32* %l0 = bitcast i8* %call to i32*
call void @llvm.memset.p0i8.i64(i8* %call, i8 0, i64 40000, i1 false) call void @llvm.memset.p0i8.i64(i8* %call, i8 0, i64 20, i1 false)
ret i8* %call ret i8* %call
} }
define i8* @partial_zero_memset_and_store_after_calloc(i8 %v) {
; CHECK-LABEL: @partial_zero_memset_and_store_after_calloc(
; CHECK-NEXT: [[CALL:%.*]] = tail call i8* @calloc(i64 10000, i64 4)
; CHECK-NEXT: [[GEP:%.*]] = getelementptr inbounds i8, i8* [[CALL]], i64 30
; CHECK-NEXT: store i8 [[V:%.*]], i8* [[GEP]], align 1
; CHECK-NEXT: [[L0:%.*]] = bitcast i8* [[CALL]] to i32*
; CHECK-NEXT: ret i8* [[CALL]]
;
%call = tail call i8* @calloc(i64 10000, i64 4)
%gep = getelementptr inbounds i8, i8* %call, i64 30
store i8 %v, i8* %gep
%l0 = bitcast i8* %call to i32*
call void @llvm.memset.p0i8.i64(i8* %call, i8 0, i64 20, i1 false)
ret i8* %call
}
define i8* @nonzero_memset_after_calloc(i8 %v) { define i8* @zero_memset_and_store_with_dyn_index_after_calloc(i8 %v, i64 %idx) {
; CHECK-LABEL: @nonzero_memset_after_calloc( ; CHECK-LABEL: @zero_memset_and_store_with_dyn_index_after_calloc(
; CHECK-NEXT: [[CALL:%.*]] = tail call i8* @calloc(i64 10000, i64 4) ; CHECK-NEXT: [[CALL:%.*]] = tail call i8* @calloc(i64 10000, i64 4)
; CHECK-NEXT: [[L0:%.*]] = bitcast i8* [[CALL]] to i32* ; CHECK-NEXT: [[L0:%.*]] = bitcast i8* [[CALL]] to i32*
; CHECK-NEXT: call void @llvm.memset.p0i8.i64(i8* [[CALL]], i8 [[V:%.*]], i64 40000, i1 false)
; CHECK-NEXT: ret i8* [[CALL]] ; CHECK-NEXT: ret i8* [[CALL]]
; ;
%call = tail call i8* @calloc(i64 10000, i64 4) %call = tail call i8* @calloc(i64 10000, i64 4)
%gep = getelementptr i8, i8* %call, i64 %idx
store i8 %v, i8* %gep
%l0 = bitcast i8* %call to i32* %l0 = bitcast i8* %call to i32*
call void @llvm.memset.p0i8.i64(i8* %call, i8 %v, i64 40000, i1 false) call void @llvm.memset.p0i8.i64(i8* %call, i8 0, i64 40000, i1 false)
nikicUnsubmitted
Done
ReplyInline Actions

I'd suggest adding a variant that stores a constant but non-zero value (e.g. i8 1).

It may also be worthwhile to make sure that passing i1 true for the volatile flag will prevent DSE (this should be covered by the isRemovable check in the caller).

nikic: I'd suggest adding a variant that stores a constant but non-zero value (e.g. `i8 1`). It may…
xbolva00AuthorUnsubmitted
Done
ReplyInline Actions

Sure, I will add such tests.

xbolva00: Sure, I will add such tests.
ret i8* %call ret i8* %call
} }
define i8* @zero_memset_after_calloc_smaller_size() { define i8* @partial_zero_memset_and_store_with_dyn_index_after_calloc(i8 %v, i64 %idx) {
; CHECK-LABEL: @zero_memset_after_calloc_smaller_size( ; CHECK-LABEL: @partial_zero_memset_and_store_with_dyn_index_after_calloc(
; CHECK-NEXT: [[CALL:%.*]] = tail call i8* @calloc(i64 10000, i64 4) ; CHECK-NEXT: [[CALL:%.*]] = tail call i8* @calloc(i64 10000, i64 4)
; CHECK-NEXT: [[GEP:%.*]] = getelementptr i8, i8* [[CALL]], i64 [[IDX:%.*]]
; CHECK-NEXT: store i8 [[V:%.*]], i8* [[GEP]], align 1
; CHECK-NEXT: [[L0:%.*]] = bitcast i8* [[CALL]] to i32* ; CHECK-NEXT: [[L0:%.*]] = bitcast i8* [[CALL]] to i32*
; CHECK-NEXT: call void @llvm.memset.p0i8.i64(i8* [[CALL]], i8 0, i64 20, i1 false) ; CHECK-NEXT: call void @llvm.memset.p0i8.i64(i8* [[CALL]], i8 0, i64 20, i1 false)
; CHECK-NEXT: ret i8* [[CALL]] ; CHECK-NEXT: ret i8* [[CALL]]
; ;
%call = tail call i8* @calloc(i64 10000, i64 4) %call = tail call i8* @calloc(i64 10000, i64 4)
%gep = getelementptr i8, i8* %call, i64 %idx
store i8 %v, i8* %gep
%l0 = bitcast i8* %call to i32* %l0 = bitcast i8* %call to i32*
call void @llvm.memset.p0i8.i64(i8* %call, i8 0, i64 20, i1 false) call void @llvm.memset.p0i8.i64(i8* %call, i8 0, i64 20, i1 false)
ret i8* %call ret i8* %call
} }
define i8* @zero_memset_after_calloc_inaccessiblememonly() {
; CHECK-LABEL: @zero_memset_after_calloc_inaccessiblememonly(
; CHECK-NEXT: [[CALL:%.*]] = tail call i8* @calloc(i64 10000, i64 4) #[[ATTR6]]
; CHECK-NEXT: [[L0:%.*]] = bitcast i8* [[CALL]] to i32*
; CHECK-NEXT: call void @llvm.memset.p0i8.i64(i8* [[CALL]], i8 0, i64 40000, i1 false)
; CHECK-NEXT: ret i8* [[CALL]]
;
%call = tail call i8* @calloc(i64 10000, i64 4) inaccessiblememonly
%l0 = bitcast i8* %call to i32*
call void @llvm.memset.p0i8.i64(i8* %call, i8 0, i64 40000, i1 false)
ret i8* %call
}
define i8* @nonzero_memset_after_calloc(i8 %v) {
; CHECK-LABEL: @nonzero_memset_after_calloc(
; CHECK-NEXT: [[CALL:%.*]] = tail call i8* @calloc(i64 10000, i64 4)
; CHECK-NEXT: [[L0:%.*]] = bitcast i8* [[CALL]] to i32*
; CHECK-NEXT: call void @llvm.memset.p0i8.i64(i8* [[CALL]], i8 [[V:%.*]], i64 40000, i1 false)
; CHECK-NEXT: ret i8* [[CALL]]
;
%call = tail call i8* @calloc(i64 10000, i64 4)
%l0 = bitcast i8* %call to i32*
call void @llvm.memset.p0i8.i64(i8* %call, i8 %v, i64 40000, i1 false)
ret i8* %call
}
; PR11896 ; PR11896
; The first memset is dead, because calloc provides zero-filled memory. ; The first memset is dead, because calloc provides zero-filled memory.
; TODO: This could be replaced with a call to malloc + memset_pattern16. ; TODO: This could be replaced with a call to malloc + memset_pattern16.
define i8* @memset_pattern16_after_calloc(i8* %pat) { define i8* @memset_pattern16_after_calloc(i8* %pat) {
; CHECK-LABEL: @memset_pattern16_after_calloc( ; CHECK-LABEL: @memset_pattern16_after_calloc(
; CHECK-NEXT: [[CALL:%.*]] = tail call i8* @calloc(i64 10000, i64 4) ; CHECK-NEXT: [[CALL:%.*]] = tail call i8* @calloc(i64 10000, i64 4)
; CHECK-NEXT: [[L0:%.*]] = bitcast i8* [[CALL]] to i32* ; CHECK-NEXT: [[L0:%.*]] = bitcast i8* [[CALL]] to i32*
; CHECK-NEXT: call void @llvm.memset.p0i8.i64(i8* align 4 [[CALL]], i8 0, i64 40000, i1 false)
; CHECK-NEXT: call void @memset_pattern16(i8* [[CALL]], i8* [[PAT:%.*]], i64 40000) ; CHECK-NEXT: call void @memset_pattern16(i8* [[CALL]], i8* [[PAT:%.*]], i64 40000)
; CHECK-NEXT: ret i8* [[CALL]] ; CHECK-NEXT: ret i8* [[CALL]]
; ;
%call = tail call i8* @calloc(i64 10000, i64 4) #1 %call = tail call i8* @calloc(i64 10000, i64 4) #1
%l0 = bitcast i8* %call to i32* %l0 = bitcast i8* %call to i32*
call void @llvm.memset.p0i8.i64(i8* align 4 %call, i8 0, i64 40000, i1 false) call void @llvm.memset.p0i8.i64(i8* align 4 %call, i8 0, i64 40000, i1 false)
call void @memset_pattern16(i8* %call, i8* %pat, i64 40000) #1 call void @memset_pattern16(i8* %call, i8* %pat, i64 40000) #1
ret i8* %call ret i8* %call
} }