This is an archive of the discontinued LLVM Phabricator instance.

[ConstantFolding] Fold ptrtoint(gep i8 null, x) -> x
ClosedPublic

Authored by arichardson on Sep 22 2021, 6:56 AM.

Details

Summary

I was looking at some missed optimizations in CHERI-enabled targets and
noticed that we weren't removing vtable indirection for calls via known
pointers-to-members. The underlying reason for this is that we represent
pointers-to-function-members as {i8 addrspace(200)*, i64} and generate the
constant offsets using (gep i8 null, <index>). We use a constant GEP here
since inttoptr should be avoided for CHERI capabilities. The pointer-to-member
call uses ptrtoint to extract the index, due to this missing fold we can't
infer the actual value loaded from the vtable.
This is the initial constant folding change for this pattern, I will add
InstSimplify/InstCombine folds as a follow-up.

We could fold all ptrtoint(inbounds GEP) to zero here since that is the
only valid offset for an inbounds GEP. If the offset is not zero, that GEP
is poison so returning 0 is valid (https://alive2.llvm.org/ce/z/Gzb5iH).
However, Clang currently generates inbounds GEPs on NULL for hand-written
offsetof() expressions, so this could result in miscompilation.

Diff Detail

Event Timeline

arichardson created this revision.Sep 22 2021, 6:56 AM
arichardson requested review of this revision.Sep 22 2021, 6:56 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 22 2021, 6:56 AM
nikic added inline comments.Sep 22 2021, 7:13 AM
llvm/lib/Analysis/ConstantFolding.cpp
1376

This doesn't belong here. If we'd like to make this fold, it should work directly on gep null, x -> null, without requiring a ptrtoint around it. (Also note that this fold is not correct if null is defined, e.g. in non-zero address space).

Drop unnncessary code and replace it with a comment explaining why we can ignore inbounds.

arichardson added inline comments.Sep 23 2021, 1:50 AM
llvm/lib/Analysis/ConstantFolding.cpp
1376

Yes I agree. I added that fold locally later but it caused lots of undesirable changes.

Langref has the following sentence:
The only in bounds address for a null pointer in the default address-space is the null pointer itself., and

null_pointer_is_valid
If null_pointer_is_valid is set, then the null address in address-space 0 is considered to be a valid address for memory loads and stores. Any analysis or optimization should not treat dereferencing a pointer to null as undefined behavior in this function. Note: Comparing address of a global variable to null may still evaluate to false because of a limitation in querying this attribute inside constant expressions.

So I guess that implies gep inbounds null is valid if that attribute is set? Should the GEP section be changed to something like
The only in bounds address for a null pointer in the default address-space is the null pointer itself. This does not apply if the null_pointer_is_valid attribute was used.

lebedev.ri added inline comments.Sep 23 2021, 1:53 AM
llvm/lib/Analysis/ConstantFolding.cpp
1353–1367

I don't think this is correct.
In int -> ptr -> int, the width can be different at all three stages,
so i'd expect two sextOrTruncOrSelf casts back to back.

arichardson added inline comments.Sep 23 2021, 2:09 AM
llvm/lib/Analysis/ConstantFolding.cpp
1353–1367

I believe the current code manually does a trunc if the inttoptr input type is larger than pointer size:
with a p:64:64:64:32 datalayout, ptrtoint (inttoptr i256 -1 to i8*) to i128 should result in
trunc ((i256)-1 & UINT64_MAX) to i128. The new code now does zext (trunc i256 -1 to i64) to i128 which I believe yields the same value? No existing tests were affected by this refactoring so it's either equivalent or we are missing test coverage.

Slightly unrelated: For our (CHERI) usecase pointer size in bits is wrong since we have 128-bit pointers but only 64-bit address range. I would like to change it to index size, but I am not sure if that is acceptable upstream. If not I could add another datalayout field for pointers that specifies the address range (defaulting to index size). For now this works for us since we have patched DL.getIntPtrType() to return i64 for our addrspace(200) pointers, but I would prefer to be explicit whether we care about address range or pointer type size. This might also help with non-integral pointers that have additional metadata (e.g. bounds) like our CHERI capabilities.

lebedev.ri added inline comments.Sep 23 2021, 2:18 AM
llvm/lib/Analysis/ConstantFolding.cpp
1353–1367

Ah, the reply i should have gotten is: "what are you talking about? there is a second cast, later on"

1355
1365

How do you know the result is a constant?

1366
1367
1371
arichardson marked an inline comment as done.Sep 23 2021, 2:25 AM
arichardson added inline comments.
llvm/lib/Analysis/ConstantFolding.cpp
1365

Don't all inputs need to be constants if the GEP is a ConstantExpr? I couldn't think of a counter-example:

Even for globals this cast works fine:

@a = external addrspace(1) global i16

define i64 @nofold_ptrtoint_gep_global(i32 %x) {
  %ptr = getelementptr i16, i16 addrspace(1)* @a, i32 1
  %ret = ptrtoint i16 addrspace(1)* %ptr to i64
  ret i64 %ret
}
1365

If this is not true, I'm obviously happy to change it to dyn_cast and add the check.

arichardson marked 3 inline comments as done.Sep 23 2021, 2:27 AM
arichardson added inline comments.
llvm/lib/Analysis/ConstantFolding.cpp
1353–1367

If this is not clear enough I can add a comment?

Add missing /*Param=*/

Looks reasonable with nits.

llvm/lib/Analysis/ConstantFolding.cpp
1365

Err, right,
This also answers my further unanswered question as to why we need to special-handle this in instsimplify too.

lebedev.ri accepted this revision.Sep 23 2021, 2:33 AM

LG

llvm/lib/Analysis/ConstantFolding.cpp
1371–1373

I don't think matters what is "safer", that mentioned code is UB, and UBSan will catch it.

This revision is now accepted and ready to land.Sep 23 2021, 2:33 AM
nikic added inline comments.Sep 23 2021, 2:35 AM
llvm/lib/Analysis/ConstantFolding.cpp
1371–1373

I think this comment should just be dropped entirely. Any optimization that is valid without inbounds is valid with inbounds and does not require explicit justification.

arichardson added inline comments.Sep 23 2021, 2:40 AM
llvm/lib/Analysis/ConstantFolding.cpp
1371–1373

Sounds good to me. I added this comment since I only recently looked into the detailed semantics of inbounds/non-inbounds GEPs. But for someone familiar with it that is indeed obvious.

If there isn't a fold gep inbounds null, ??? --> bitcast(null) it might be interesting to add one though.

arichardson marked 7 inline comments as done.

Drop inbounds comment

arichardson marked an inline comment as not done.Sep 23 2021, 2:48 AM

If there isn't a fold gep inbounds null, ??? --> bitcast(null) it might be interesting to add one though.

I tried adding a (gep inbounds null, nonzero) -> poison fold, but that broke lots of tests. (gep inbounds null, ..) -> null is a bit safer but will break &((TYPE *)0)->MEMBER) __builtin_offsetof fallbacks since they are constant-folded to null before UBSAN can handle it.

llvm/lib/Analysis/ConstantFolding.cpp
1361

The only open question I have is whether this is valid for non-integral pointers? It is definitely valid for CHERI capabilities which are non-integral but with a well defined pointer->int mapping (only int->pointer isn't).

If there isn't a fold gep inbounds null, ??? --> bitcast(null) it might be interesting to add one though.

I tried adding a (gep inbounds null, nonzero) -> poison fold, but that broke lots of tests. (gep inbounds null, ..) -> null is a bit safer but will break &((TYPE *)0)->MEMBER) __builtin_offsetof fallbacks since they are constant-folded to null before UBSAN can handle it.

I personally find this approach problematic for forward progress.
https://alive2.llvm.org/ce/z/swyJHv <- gep inbounds null, ??? --> null is always fine
https://alive2.llvm.org/ce/z/fQUjCY <- (gep inbounds null, nonzero) --> undef is also fine
So anything that breaks was broken already. In case of tests, they probably just need to be updated.

If there isn't a fold gep inbounds null, ??? --> bitcast(null) it might be interesting to add one though.

I tried adding a (gep inbounds null, nonzero) -> poison fold, but that broke lots of tests. (gep inbounds null, ..) -> null is a bit safer but will break &((TYPE *)0)->MEMBER) __builtin_offsetof fallbacks since they are constant-folded to null before UBSAN can handle it.

I personally find this approach problematic for forward progress.
https://alive2.llvm.org/ce/z/swyJHv <- gep inbounds null, ??? --> null is always fine
https://alive2.llvm.org/ce/z/fQUjCY <- (gep inbounds null, nonzero) --> undef is also fine
So anything that breaks was broken already. In case of tests, they probably just need to be updated.

I would like to add this fold, but what about @nikic's comment about having a defined null pointer? I believe in that case the whole address space is inbounds of null?

If there isn't a fold gep inbounds null, ??? --> bitcast(null) it might be interesting to add one though.

I tried adding a (gep inbounds null, nonzero) -> poison fold, but that broke lots of tests. (gep inbounds null, ..) -> null is a bit safer but will break &((TYPE *)0)->MEMBER) __builtin_offsetof fallbacks since they are constant-folded to null before UBSAN can handle it.

I personally find this approach problematic for forward progress.
https://alive2.llvm.org/ce/z/swyJHv <- gep inbounds null, ??? --> null is always fine
https://alive2.llvm.org/ce/z/fQUjCY <- (gep inbounds null, nonzero) --> undef is also fine
So anything that breaks was broken already. In case of tests, they probably just need to be updated.

I would like to add this fold, but what about @nikic's comment about having a defined null pointer? I believe in that case the whole address space is inbounds of null?

Yep, these two folds i linked require !nullPointerIsDefined

rebase after baseline test change

Drop non-integral fixme. Should be safe as pointed out by @nikic in D110247

This revision was landed with ongoing or failed builds.Sep 28 2021, 9:58 AM
This revision was automatically updated to reflect the committed changes.