[BasicAliasAnalysis] Switch from isMallocOrCallocLikeFn to onlyAccessesInaccessibleMemory

[Bryce-MW]

Summary

Allocation functions should be marked correctly with onlyAccessesInaccessibleMemory so this change can be made (assuming the comment was accurate). In the future, this could be expanded to check inaccessiblememorargmemonly as well but that would have to ensure that the args don't alias with the memory location in question.

[Bryce-MW]

• malloc is inaccessiblememonly

[nikic]

Does anything fail if you simply remove this code? We should already be handling inaccessiblememonly generically in AA, there's no need to special-case it here again.

Something I want to note is that we currently do not set inaccessiblememonly for new in clang (we only set noalias), so maybe that should be changed first?

[Bryce-MW]

• Try removing the code

[Bryce-MW]

I'll see what happens when removing that section. It does sound like that should be added to clang. I'll take a look at that before this is landed. I don't know enough about the standards to say if op new is required to only access inaccessible memory but that sounds reasonable since I think op new is supposed to not be observable.

[reames]

In D117180#3241427, @Bryce-MW wrote:

I'll see what happens when removing that section. It does sound like that should be added to clang. I'll take a look at that before this is landed. I don't know enough about the standards to say if op new is required to only access inaccessible memory but that sounds reasonable since I think op new is supposed to not be observable.

Er, the discussion here has gone a bit off base. A couple of points:

1. The existing code does *NOT* handle operator new. It very specifically uses the accessor which does not include opnewlike.
2. The reason for this is that calls to the replaceable global allocator in C++ are *not* removable (i.e. are observable) *unless* they come from an new expression. (See the comment in isAllocRemovable for pointers to relevant sections of the spec.) Since we don't model this distinction, we must treat all as non-removable.

So, no, please do *not* mark opnew as inaccessiblememonly in clang. That would be wrong.

[Bryce-MW]

Thanks, like I said, I'm not super knowledgeable about the standards (especially for C++, I'm mostly a C person). One thing I will note is that isMallocOrCallocLikeFn does return true for op new as far as I can tell.
The test it does is

(FnData->AllocTy & MallocOrCallocLike) != FnData->AllocTy // returns true when they type doesn't match and false when it does

MallocOrCallocLike = MallocLike | CallocLike | AlignedAllocLike
MallocLike = 1<<1 | OpNewLike
OpNewLike = 1<<0
CallocLike = 1<<3
AlignedAllocLike = 1<<2
so MallocOrCallocLike = 0b1111
an OpNewLike function will be tagged OpNewLike = 1

so the test becomes:
(1 & 0b1111) != 1
(1) != 1
false

If it were true then getAllocationDataForFunction would return None causing isMallocOrCallocLikeFn to return false. But it returns false, so as long as the arguments match the check, then getAllocationDataForFunction will return some data making isMallocOrCallocLikeFn return true. This also means that for similar reasons, isAllocRemovable is going to return true for op new but it sounds like you are saying that it should not.

[reames]

Er, you're correct, but WTF? We consider an operator new "malloc like"? That's simply wrong on so many levels.

Well, then the original code is buggy.

[reames]

In D117180#3241489, @reames wrote:

Well, then the original code is buggy.

To clarify, buggy in a way you are not obligated to fix. If you want to go ahead and change how we encode the bug, and the clang folks accept that, I have no objection.

[Bryce-MW]

Based on the comments on AllocType, it seems that the original difference between OpNewLike and MallocLike was whether it returned null. In that context, it's reasonable that something that never returns null can be used in the place of something that could return null. It's obviously used for more than just that now so this has probably caused a few places to be incorrect.

It seems like this patch of just removing the condition entirely should at least make this part of the code correct even though it does change the functionality slightly.

[xbolva00]

In D117180#3241489, @reames wrote:

Er, you're correct, but WTF? We consider an operator new "malloc like"? That's simply wrong on so many levels.

Well, then the original code is buggy.

Non throwing version of new (which may return null) is malloc like.

[reames]

In D117180#3241544, @xbolva00 wrote:

In D117180#3241489, @reames wrote:

Er, you're correct, but WTF? We consider an operator new "malloc like"? That's simply wrong on so many levels.

Well, then the original code is buggy.

Non throwing version of new (which may return null) is malloc like.

Please see the C++ specification wording in expr.new paragraph 13.

Calls to the replaceable global allocator are not removable unless coming from a new expression. I don't believe we have enough information in IR today to tell if they're coming from new expressions or not.

[xbolva00]

In D117180#3241552, @reames wrote:

In D117180#3241544, @xbolva00 wrote:

In D117180#3241489, @reames wrote:

Er, you're correct, but WTF? We consider an operator new "malloc like"? That's simply wrong on so many levels.

Well, then the original code is buggy.

Non throwing version of new (which may return null) is malloc like.

Please see the C++ specification wording in expr.new paragraph 13.

Calls to the replaceable global allocator are not removable unless coming from a new expression. I don't believe we have enough information in IR today to tell if they're coming from new expressions or not.

Yeah I know and we have many related PRs. Everything related to C++ “new” is a mess.

[reames]

cd36b29 adjusts the code to make the fact we treat opnew like malloc slightly more explicit. This doesn't change any semantics, it just makes it easier to notice this odd case.

[reames]

In D117180#3241562, @xbolva00 wrote:

In D117180#3241552, @reames wrote:

In D117180#3241544, @xbolva00 wrote:

In D117180#3241489, @reames wrote:

Er, you're correct, but WTF? We consider an operator new "malloc like"? That's simply wrong on so many levels.

Well, then the original code is buggy.

Non throwing version of new (which may return null) is malloc like.

Please see the C++ specification wording in expr.new paragraph 13.

Calls to the replaceable global allocator are not removable unless coming from a new expression. I don't believe we have enough information in IR today to tell if they're coming from new expressions or not.

Yeah I know and we have many related PRs. Everything related to C++ “new” is a mess.

Agreed. Strongly.

[nikic]

LGTM

[nikic]

It looks like this had some very significant codegen impact, including a 13% code size regression on 7zip: https://llvm-compile-time-tracker.com/compare.php?from=cd97aaee5fef87215eebbd17a31099fe4437ce1f&to=1f2cfc4fdc1eefb2c5f562c77a5fe7e916bbf670&stat=size-text

We should probably revert this until that is investigated. I suspect that it is due to the mentioned issue with new, but I didn't expect impact to be this large.

[Bryce-MW]

I've reverted it. That's quite significant. I'm not sure what we should do here. The current situation is incorrect but as we've seen fixing it causes significant regression. I'm guessing even if op new can't technically be considered inaccessiblememonly in the general case, it probably is commonly inaccessiblememonly which is why this worked in the past. I'm not familiar enough with clang to know if it could say add the annotation if linking against a library that is known to have op new be inaccessiblememonly.

[nikic]

Yes, this is a tricky problem. See also https://github.com/llvm/llvm-project/issues/48366 for some relevant discussion, though in different context. We have a pretty fundamental problem when it comes to handling of replaceable allocator functions in LLVM. Setting inaccessiblememonly (and arguably also noalias) on them is only strictly correct if the allocator implementation (including any state it may use) is not visible to LLVM.

[Bryce-MW]

That's worse than I thought since it appears LLVM can't know if the allocator was replaced until link time it seems

[Bryce-MW]

My current thought on how this could be done is to add some sort of optimization flag to clang, say -fstrict-op-new. If off (-fno-strict-op-new), it would mark op new as inaccessiblememonly and possibly removable if we ever add a way to mark that. When they would enable that flag would be up to them. I would say disabled unless -Ofast but maybe because of the regressions we've seen, it should be disabled at -O3 or something. I can't see any easier way to solve this issue unless we basically leave this optimization to LTO where we would know if op new was globally replaced or not.

[nikic]

In D117180#3247159, @Bryce-MW wrote:

My current thought on how this could be done is to add some sort of optimization flag to clang, say -fstrict-op-new. If off (-fno-strict-op-new), it would mark op new as inaccessiblememonly and possibly removable if we ever add a way to mark that. When they would enable that flag would be up to them. I would say disabled unless -Ofast but maybe because of the regressions we've seen, it should be disabled at -O3 or something. I can't see any easier way to solve this issue unless we basically leave this optimization to LTO where we would know if op new was globally replaced or not.

We do already have something like this in the form of -fassume-sane-operator-new (enabled by default I believe). This is what currently gates the noalias addition. I don't know whether gating inaccessiblememonly under that as well would be acceptable, as we don't seem to have any documentation on what "sane" requires in that context.

[Bryce-MW]

If I can manage to find my way around the clang source code, I could put in a patch and see what people say about it?

[reames]

I'm skimming the BasicAA code, and I don't see where we handle the isNoAliasCall case inside of getModRefInfo(CB, Loc). Is it possible the effect here was because this was the only form of handling we had for noalias results?

It looks like we have support for escape based reasoning, and identified object based reasoning, but I don't see anywhere that we directly check for noalias in an analogous manner.

Another possibility: We appear to not be annotating calloc with inaccessiblememonly.

[nikic]

In D117180#3248804, @reames wrote:

I'm skimming the BasicAA code, and I don't see where we handle the isNoAliasCall case inside of getModRefInfo(CB, Loc). Is it possible the effect here was because this was the only form of handling we had for noalias results?

Noalias calls are considered local identified objects, and are considered in any code dealing with those. For calls specifically, we don't modref local identified not-captured-before objects.

Another possibility: We appear to not be annotating calloc with inaccessiblememonly.

Good point!

[xbolva00]

About calloc:

https://reviews.llvm.org/rGe20b32ff3b029f50c7237f49e5e5c97bd47ea540

[reames]

In D117180#3249247, @xbolva00 wrote:

About calloc:

https://reviews.llvm.org/rGe20b32ff3b029f50c7237f49e5e5c97bd47ea540

I don't think the conclusion reached here makes sense. On the surface, it seems like we need to tweak inaccessiblememonly to allow writes to newly allocated returned memory. Do we have a use case for the version of inaccessiblememonly which disallows that?

[Bryce-MW]

From my perspective, since the return value is noalias, I feel like that memory is inaccessible until it is returned so anything done to that memory, such as clearing it, should be fine. It seems like the issue that they had was with various bailouts for inaccessible memory in llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp. We do have a check for an allocation function in storeIsNoop. I don't know if that happens before the other checks but it seems at least worth testing to see whether the old issue still occurs on today's code: https://github.com/llvm/llvm-project/issues/49487. It probably wouldn't be hard to add a test for that

[reames]

@Bryce-MW It's a bit more complicated than just checking existing test cases. From memory, this explains some code in both AliasAnalysis.cpp and BasicAliasAnalysis.cpp which I'd thought odd when looking through it this morning. I think the attribute change is probably worthwhile, but it will require both an RFC and a number of changes to existing code.

I can drive that. I'll wait a day or two to see if anyone remembers a strong reason for the current semantic, then work up some patches and an RFC to llvm-dev.

[Bryce-MW]

That sounds reasonable to me!

[nikic]

In D117180#3249638, @reames wrote:

@Bryce-MW It's a bit more complicated than just checking existing test cases. From memory, this explains some code in both AliasAnalysis.cpp and BasicAliasAnalysis.cpp which I'd thought odd when looking through it this morning. I think the attribute change is probably worthwhile, but it will require both an RFC and a number of changes to existing code.

I can drive that. I'll wait a day or two to see if anyone remembers a strong reason for the current semantic, then work up some patches and an RFC to llvm-dev.

Not sure I understand what is being suggested here. I do think that using inaccessiblememonly for calloc is fine, as the memory is inaccessible at the time of the call, and becomes accessible after it returns. calloc isn't really different from other allocation functions here.

I think the problematic interaction with DSE is the fact that MSSA does not model object lifetime, so if a new object comes into existence (via alloca, malloc ... or calloc) it will be liveOnEntry. The accepted way to handle that right now is to check that the defining access is liveOnEntry and the underlying object is an alloca or allocation.

I've put up D117543 to show that DSE would be perfectly capable of handling inaccessiblememonly calloc, it just requires a slightly different implementation.

[reames]

In D117180#3250435, @nikic wrote:

In D117180#3249638, @reames wrote:

Not sure I understand what is being suggested here. I do think that using inaccessiblememonly for calloc is fine, as the memory is inaccessible at the time of the call, and becomes accessible after it returns. calloc isn't really different from other allocation functions here.

I agree that calloc behaves like malloc in this respect. The basic question I see being posed here is whether inaccessiblememonly is legal on any allocation routine.

I was originally thinking we needed to change the definition to explicitly allow this, but it sounds like you think this was always allowed. I put up a langref change (https://reviews.llvm.org/D117571) to make that really explicit.

I think the problematic interaction with DSE is the fact that MSSA does not model object lifetime, so if a new object comes into existence (via alloca, malloc ... or calloc) it will be liveOnEntry. The accepted way to handle that right now is to check that the defining access is liveOnEntry and the underlying object is an alloca or allocation.

I've put up D117543 to show that DSE would be perfectly capable of handling inaccessiblememonly calloc, it just requires a slightly different implementation.

I think I agree. I was originally thinking we'd need AA changes for the definition point (what you call "coming into existence"), but looking at how we handle allocas, you're proposal is more consistent than mine.

Is your change ready for review? Or do you need to do something else first?

[nikic]

In D117180#3251512, @reames wrote:

Is your change ready for review? Or do you need to do something else first?

As we seem to agree on direction, yes. Just needs to land together with the corresponding SLC change to add inaccessiblememonly to calloc.

[reames]

Once D117543 (and the associate calloc revert) land, I think it's worth seeing if the regression here still exists.

I don't see where we tag op-new as inaccessiblememonly, so we may still have a problem, but I think the calloc case is likely to help a lot.

Edit: Even if opnew still blocks removal, we can probably narrow the check to only kick in for opnew and add an explicit comment about that. Would help to confirm our theory about it being a lack of annotation on those functions specifically at least.

[Bryce-MW]

I don't think op new is annotated as inaccessible memory anywhere. I'm working on a patch in D117600. I was just about to submit it for review

[xbolva00]

In D117180#3252815, @Bryce-MW wrote:

I don't think op new is annotated as inaccessible memory anywhere. I'm working on a patch in D117600. I was just about to submit it for review

https://github.com/llvm/llvm-project/commit/ab243efb261ba7e27f4b14e1a6fbbff15a79c0bf#diff-4e887ae3fd3d1f1ad429d92733318ce1efac179eb498d9c4c1438d3255855018

llvm/lib/Analysis/BasicAliasAnalysis.cpp

if (!isa<Constant>(Object) && Call != Object &&
     // Early return if we improved mod ref information
     if (!isModAndRefSet(Result)) {
       if (isNoModRef(Result))
         return ModRefInfo::NoModRef;
       return IsMustAlias ? setMust(Result) : clearMust(Result);
     }
   }
 
-  // If the call is malloc/calloc like, we can assume that it doesn't
-  // modify any IR visible value.  This is only valid because we assume these
-  // routines do not read values visible in the IR.  TODO: Consider special
-  // casing realloc and strdup routines which access only their arguments as
-  // well.  Or alternatively, replace all of this with inaccessiblememonly once
-  // that's implemented fully.
-  if (isMallocOrCallocLikeFn(Call, &TLI)) {
-    // Be conservative if the accessed pointer may alias the allocation -
-    // fallback to the generic handling below.
-    if (getBestAAResults().alias(MemoryLocation::getBeforeOrAfter(Call), Loc,
-                                 AAQI) == AliasResult::NoAlias)
-      return ModRefInfo::NoModRef;
-  }
-
   // The semantics of memcpy intrinsics either exactly overlap or do not
   // overlap, i.e., source and destination of any given memcpy are either
   // no-alias or must-alias.
   if (auto *Inst = dyn_cast<AnyMemCpyInst>(Call)) {
     AliasResult SrcAA =
         getBestAAResults().alias(MemoryLocation::getForSource(Inst), Loc, AAQI);
     AliasResult DestAA =
         getBestAAResults().alias(MemoryLocation::getForDest(Inst), Loc, AAQI);

llvm/test/Transforms/GVN/nonescaping-malloc.ll

entry:
   %tmp2.i = getelementptr inbounds %"struct.llvm::StringRef", %"struct.llvm::StringRef"* %tmp, i64 0, i32 1
   store i64 %tmp1.i, i64* %tmp2.i, align 8
   %tmp1 = call %"struct.llvm::StringMapEntry<void*>"* @_ZN4llvm9StringMapIPvNS_15MallocAllocatorEE16GetOrCreateValueERKNS_9StringRefE(%"struct.llvm::StringMap<void*,llvm::MallocAllocator>"* %X, %"struct.llvm::StringRef"* %tmp) ssp
   ret %"struct.llvm::StringMapEntry<void*>"* %tmp1
 }
 
 declare i64 @strlen(i8* nocapture) nounwind readonly
 
-declare noalias i8* @malloc(i64) nounwind
+declare noalias i8* @malloc(i64) nounwind inaccessiblememonly
 
 declare i32 @_ZN4llvm13StringMapImpl15LookupBucketForENS_9StringRefE(%"struct.llvm::StringMapImpl"*, i64, i64)
 
 define linkonce_odr %"struct.llvm::StringMapEntry<void*>"* @_ZN4llvm9StringMapIPvNS_15MallocAllocatorEE16GetOrCreateValueERKNS_9StringRefE(%"struct.llvm::StringMap<void*,llvm::MallocAllocator>"* %this, %"struct.llvm::StringRef"* nocapture %Key) ssp align 2 {
 entry:
   %elt = bitcast %"struct.llvm::StringRef"* %Key to i64*
   %val = load i64, i64* %elt
   %tmp = getelementptr inbounds %"struct.llvm::StringRef", %"struct.llvm::StringRef"* %Key, i64 0, i32 1
bb4.i:                                            ; preds = %entry
   %tmp41.i = inttoptr i64 %val to i8*
   %tmp4.i35.i = getelementptr inbounds i8, i8* %tmp41.i, i64 %val2
   %tmp.i.i = ptrtoint i8* %tmp4.i35.i to i64
   %tmp1.i.i = trunc i64 %tmp.i.i to i32
   %tmp3.i.i = trunc i64 %val to i32
   %tmp4.i.i = sub i32 %tmp1.i.i, %tmp3.i.i
   %tmp5.i.i = add i32 %tmp4.i.i, 17
   %tmp8.i.i = zext i32 %tmp5.i.i to i64
-  %tmp.i20.i.i = tail call noalias i8* @malloc(i64 %tmp8.i.i) nounwind
+  %tmp.i20.i.i = tail call noalias i8* @malloc(i64 %tmp8.i.i) nounwind inaccessiblememonly
   %tmp10.i.i = bitcast i8* %tmp.i20.i.i to %"struct.llvm::StringMapEntry<void*>"*
   %tmp12.i.i = icmp eq i8* %tmp.i20.i.i, null
   br i1 %tmp12.i.i, label %_ZN4llvm14StringMapEntryIPvE6CreateINS_15MallocAllocatorES1_EEPS2_PKcS7_RT_T0_.exit.i, label %bb.i.i
 
 bb.i.i:                                           ; preds = %bb4.i
   %tmp.i.i.i.i = bitcast i8* %tmp.i20.i.i to i32*
   store i32 %tmp4.i.i, i32* %tmp.i.i.i.i, align 4
   %tmp1.i19.i.i = getelementptr inbounds i8, i8* %tmp.i20.i.i, i64 8