InstCombine nonnull annotation and free hoisting interacts badly

[smeenai]

Bugzilla Link	52110
Resolution	FIXED
Resolved on	Nov 04, 2021 19:38
Version	trunk
OS	All
CC	@dwblaikie,@jdoerfert,@jdoerfert,@aqjune,@LebedevRI,@RKSimon,@MatzeB,@glandium,@nikic,@nunoplopes,@qcolombet
Fixed by commit(s)	6404f4b

Extended Description

InstCombine attaches a nonnull attribute to a parameter it can prove is non-null, and at -Oz, it also hoists a call to free above a null check if it's profitable for size (3b2db0bcd397). The combination of the two causes problems when we mark a call to free as having a nonnull argument when it's guarded by a null check, and then hoist the free above the null check which was required for the nonnull annotation to be correct. For example, for the following C code:

void free(void *);
void f(void *p) { free(p); }
void g(void *p) { if (p) f(p); }

clang -Oz -S -emit-llvm produces:

define dso_local void @​f(i8* nocapture %p) local_unnamed_addr #​0 {
entry:
tail call void @​free(i8* %p) #​2
ret void
}

declare dso_local void @​free(i8* nocapture noundef) local_unnamed_addr #​1

define dso_local void @​g(i8* %p) local_unnamed_addr #​0 {
entry:
tail call void @​free(i8* nonnull %p) #​3
ret void
}

The IR for g retains the nonnull attribute on the argument to free, but the null check that made this attribute be valid is removed. This can then cause problems for callers of g with a null argument (which should have been valid); e.g. SimplifyCFG will remove valid checks after https://reviews.llvm.org/D94180, since it'll consider calling g with null to be UB.

(I can't repro this with C if I call free directly from g; I need the indirection through f to demonstrate the issue. That also matches the structure of our actual code which ran into this issue.)

I can think of a couple of ways to fix this, and I'd appreciate advice on the best approach:

1. Don't hoist a free above a null check if its argument is marked nonnull. The downside is that the argument might have been marked nonnull for a reason other than the null check, and we'd be unnecessarily pessimizing that case.
2. Remove the nonnull attribute from the argument (if present) after hoisting a free above a null check. I don't know if the cases this pessimizes are better or worse than 1.
3. Record that the argument to free was marked nonnull because of the null check, and use that information to decide whether to hoist the free/remove the attribute after hoisting. I have no idea if this is tractable at all.
4. Reorder InstCombine so that the free hoisting happens before the nonnull attribute addition. That seems like the cleanest solution if it's feasible, but I have no idea if it is.

[dwblaikie]

SimplifyCFG will remove valid checks after https://reviews.llvm.org/D94180, since it'll consider calling g with null to be UB.

That doesn't sound quite right. If the attribute is on an argument, rather than on the function definition's parameter - then it doesn't seem like an optimization should conclude anything about it being UB to call the function with a null parameter.

[smeenai]

SimplifyCFG will remove valid checks after https://reviews.llvm.org/D94180, since it'll consider calling g with null to be UB.

That doesn't sound quite right. If the attribute is on an argument, rather
than on the function definition's parameter - then it doesn't seem like an
optimization should conclude anything about it being UB to call the function
with a null parameter.

To be clear (since I wasn't in the original description), the issue would arise if g itself gets inlined into some other function (so that other function has a call to free with a nonnull argument), and there are control flow edges which would result in the argument being null. https://reviews.llvm.org/D94180 checks for the combination of nonnull and noundef; in this case, the nonnull is on the actual function argument, and the noundef is on the parameter in the declaration.

The intended semantics of passing a null value to a nonnull argument are unclear to me from the LangRef; I'm parsing this as "nonnull + noundef means that a null is UB", but I'm not sure about that.

This indicates that the parameter or return pointer is not null. This
attribute may only be applied to pointer typed parameters. This is not
checked or enforced by LLVM; if the parameter or return pointer is null,
poison value is returned or passed instead. The nonnull attribute should be
combined with the noundef attribute to ensure a pointer is not null or
otherwise the behavior is undefined.

[jdoerfert]

The problem is that the hoisting changed the control condition w/o changing the annotation. No need to inline or derive anything else.

nonnull null -> poison
free(poison) -> UB

This is clearly a bug in the hoisting but can be resolved by removing the annotation from the call site that is hoisted.

[smeenai]

Thank you!

I was concerned that removing the nonnull attribute after hoisting would pessimize cases where the nonnull was also guaranteed by something other than the null check (e.g. attribute((nonnull)), a previous unconditional dereference, etc.). I haven't been able to come up with such a case so far though: marking the function as attribute((nonnull)) retains the nonnull, and adding an unconditional dereference before the null check results in the argument not being marked nonnull regardless of my change. I'll put up that change and we can iterate there if need be.

[MatzeB]

I was concerned that removing the nonnull attribute after hoisting would pessimize cases where the nonnull was also guaranteed by something other than the null check (e.g. attribute((nonnull)), a previous unconditional dereference, etc.).

You're likely not wrong here. I have seen some other cases by now where code movement in LLVM must drop attributes because they may have been control dependent and as a result code gets worse.

If we ever see cases where this makes a big difference then we probably should start having control-dependent and universal attributesin LLVM or something. So you know what can be maintained or what needs to be dropped when hoisting code...

[MatzeB]

Though for the record: The solution is here is obviously to first be correct and drop the nonnull attribute. The alternative would be to not perform the optimization when a nonnull is present, but that's likely the worse solution.

[jdoerfert]

FWIW, nonnull on free is pretty useless. Given that the pointer is useless after free it also is unlikely to help in the context. This is especially true if the free was guarded as we cannot utilize the information in the more generic control condition of the predecessor. Removing nonnull is perfectly fine in this situation.

[nikic]

FYI https://reviews.llvm.org/D104641 added the necessary infrastructure for this, just need to call it.

[jdoerfert]

FYI https://reviews.llvm.org/D104641 added the necessary infrastructure for
this, just need to call it.

nonnull is not UB implying but poison implying. Not to say we should not also remove the UB implying ones, the same problem described here happens for dereferenceable(_or_null as well if you write the code properly.

[aqjune]

For poison-implying attributes, we can preserve the attributes in the call site after hoisting if the function call never raises UB.

This does not apply to the free function because free can raise UB, however.

[smeenai]

Thanks for the comments and suggestions everyone! I put up https://reviews.llvm.org/D111515 for this.

[glandium]

*** Bug llvm/llvm-bugzilla-archive#52412 has been marked as a duplicate of this bug. ***

[smeenai]

mentioned in issue llvm/llvm-bugzilla-archive#52412