Page MenuHomePhabricator

[DSE] Eliminate store after calloc (PR50143)
AbandonedPublic

Authored by xbolva00 on Apr 28 2021, 4:06 AM.

Details

Diff Detail

Event Timeline

xbolva00 created this revision.Apr 28 2021, 4:06 AM
xbolva00 requested review of this revision.Apr 28 2021, 4:06 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 28 2021, 4:06 AM
xbolva00 retitled this revision from [DSE} Eliminate store after callo (PR50143) to [DSE} Eliminate store after calloc (PR50143).Apr 28 2021, 4:07 AM
xbolva00 retitled this revision from [DSE} Eliminate store after calloc (PR50143) to [DSE] Eliminate store after calloc (PR50143).Apr 28 2021, 4:19 AM
xbolva00 updated this revision to Diff 341150.Apr 28 2021, 4:53 AM
fhahn added inline comments.
llvm/lib/Analysis/AliasAnalysis.cpp
241

From this workaround, it seems like how inaccessiblememonly is used for calloc does not completely match AA's interpretation. Are there other cases in the code base? I'm not sure if special casing calloc here is ideal.

I think we should probably treat the AA change as a separate patch, with an AA only test as well, perhaps llvm/test/Analysis/BasicAA/libfuncs.ll?

xbolva00 added inline comments.Apr 28 2021, 7:05 AM
llvm/lib/Analysis/AliasAnalysis.cpp
241

Not only calloc, all alloc (calloc, malloc, aligned_alloc) fns have inaccessiblememonly. inaccessiblememonly was introduced long time ago but this attribute was basically dead, no libfunc used it until recently.

Sadly, inaccessiblememonly is somehow broken nowdays as the code assumes that such call does not write or read memory, but of course it returns memory.

This AA change can be separated patch (but this DSE needs it as a prerequisite)

Another solution is removal of inaccessiblememonly from alloc fns, as it caused more harm then improvements.

nikic requested changes to this revision.Apr 28 2021, 9:56 AM
nikic added inline comments.
llvm/lib/Analysis/AliasAnalysis.cpp
241

Your new implementation claims that inaccessiblememonly alloc-like fns mod all locations -- if that's what you want, just drop the attribute from the functions entirely. That will have about the same effect.

I think inaccessiblememonly is fine for modeling malloc behavior (or do you see any issues there as well?), the problem is with calloc which combines malloc (inaccessiblememonly) with a write to the location (accessible). As @jdoerfert already pointed out on the PR, properly modelling this would require "inaccessible_or_returned_memonly".

While I'm somewhat open to DSE hacks, I don't think making this change on the AA layer is acceptable. I think dropping inaccessiblememonly inference for calloc() specifically would be the right thing to do in the meantime.

This revision now requires changes to proceed.Apr 28 2021, 9:56 AM
xbolva00 added inline comments.Apr 28 2021, 12:46 PM
llvm/lib/Analysis/AliasAnalysis.cpp
241

Yeah, I will just drop it from calloc.

xbolva00 abandoned this revision.Apr 28 2021, 12:47 PM
xbolva00 added inline comments.Apr 29 2021, 2:28 PM
llvm/lib/Analysis/AliasAnalysis.cpp
241

I think inaccessiblememonly is fine for modeling malloc behavior (or do you see any issues there as well?)

Just found one I think.

Imagine you want to change malloc+memset combo to calloc

auto *UnderlyingDef =
     cast<MemoryDef>(MSSA.getMemoryAccess(MallocInst));
 // If UnderlyingDef is the clobbering access of Def, no instructions
 // between them can modify the memory location.
 auto *ClobberDef =
     MSSA.getSkipSelfWalker()->getClobberingMemoryAccess(MemsetDef);
 return UnderlyingDef == ClobberDef;

This will fail.

xbolva00 added inline comments.Apr 29 2021, 2:32 PM
llvm/lib/Analysis/AliasAnalysis.cpp
241

I am wondering whether there is other solution or should I just remove inaccessiblememonly from malloc too?

@jdoerfert @fhahn

I tried also to use memoryIsNotModifiedBetween but
MemoryLocation MemLoc = MemoryLocation::get(MemsetInst)

MemLoc is None

yurai007 added inline comments.
llvm/lib/Analysis/AliasAnalysis.cpp
241

@xbolva00:
For MemsetInst getForDest(MemSet) gives correct MemLoc.
Then DT.dominates + memoryIsNotModifiedBetween combination do the job: https://pastebin.com/iBvpdQAh
It seems to be enough to teach DSE how eliminate malloc+memset and emit calloc (I checked couple of UTs and it works).
Removing inaccessiblememonly attribute in malloc or touching AA machinery is not needed.

xbolva00 added inline comments.May 24 2021, 2:41 AM
llvm/lib/Analysis/AliasAnalysis.cpp
241

Great! Please post new patch :)

yurai007 added inline comments.May 24 2021, 3:07 AM
llvm/lib/Analysis/AliasAnalysis.cpp
241

Sure. I cannot uploaded diff to this one so created new instead: https://reviews.llvm.org/D103009