CHERI-valid pointer stuffing produces worse codegen than an implementation which does huge wrapping offsets

[saethlin]

I came across this here: tokio-rs/bytes#542 so I'm raising it more broadly because this seems like a portability hazard. godbolt demo

In a world where we can forget about provenance, one could set the lowest bit in a pointer with this:

pub fn old_style(a: *mut u8) -> *mut u8 {
    (a as usize | 1) as *mut u8
}

But of course we want to have a provenance model, including because we want to support architectures where pointer provenance is checked at runtime. So one might want to implement this function like so to be compatible with CHERI:

pub fn cheri_compat(a: *mut u8) -> *mut u8 {
    let old = a as usize;
    let new = old | 1;
    let diff = new.wrapping_sub(old);
    a.wrapping_add(diff)
}

But that version is slower. Instead of just mov + or, it gets compiled to mov + not + and + and. Which is very silly. We can get the original codegen back by writing this in a style which is almost certainly invalid on CHERI:

pub fn fast(a: *mut u8) -> *mut u8 {
    let old = a as usize;
    let new = old | 1;
    a.wrapping_sub(old).wrapping_add(new)
}

It doesn't make sense to me that users should have to choose between compatibility with CHERI and avoiding ptr-int-ptr casts while keeping a careful eye out for codegen regressions.

[Urgau]

I just checked with the more idiomatic way map_addr and it produce the same codegen as the cheri_compat function. godbolt.

cc @Gankra (because you're the author of the pointer provenance related stuff in std)

[Gankra]

Yes with_addr should be a compiler intrinsic so that it can just Do The Right Thing and get properly optimized. I note as much in core::ptr, but, I am not a Compiler Person.

[nikic]

We're missing this fold: https://alive2.llvm.org/ce/z/eKRvKm This is missed both on the InstCombine and the DAGCombine level.

[nikic]

https://reviews.llvm.org/D124763 for the InstCombine fold (which does not actually help here, this needs to happen on DAGCombine level).

[nikic]

https://reviews.llvm.org/D124772 is the DAGCombine fold -- which also doesn't actually help here, because demanded bits simplification interfered and reduces the width of the xor.

[nikic]

https://reviews.llvm.org/D124710 finishes the InstCombine side of this, and https://reviews.llvm.org/D124856 is another step on the DAGCombine side -- this one affects the original case, but doesn't give the result we want yet.

[nikic]

https://reviews.llvm.org/D124930 would actually fix the original case.

[RalfJung]

@nikic that's amazing. :-)
Looks like your patches have all landed by now?

[nikic]

Yes, everything has landed here, so this should be fixed with the next LLVM upgrade.

[RalfJung]

Which is the version of LLVM that will contain these patches? Looks like that would be LLVM 15?

[RalfJung]

Should we consider this fixed by #99464 ?

@saethlin can you check codegen with the latest nightly?

[saethlin]

The codegen at the godbolt link in the top-level comment is unchanged, it's still this:

example::old_style:
        mov     rax, rdi
        or      rax, 1
        ret

example::cheri_compat:
        mov     eax, edi
        not     eax
        and     eax, 1
        add     rax, rdi
        ret

example::fast:
        mov     rax, rdi
        or      rax, 1
        ret

[RalfJung]

Godbolt doesn't seem to have the update yet

rustc 1.65.0-nightly (20ffea693 2022-08-11)

[saethlin]

Ah! Looks like the playground is probably up to date? Its short links don't capture the rest of the state, so here's the disassembly it spits out for the example code:

playground::old_style: # @playground::old_style
# %bb.0:
	movq	%rdi, %rax
	orq	$1, %rax
	retq
                                        # -- End function

playground::cheri_compat: # @playground::cheri_compat
# %bb.0:
	movq	%rdi, %rax
	orq	$1, %rax
	retq
                                        # -- End function

playground::fast: # @playground::fast
# %bb.0:
	movq	%rdi, %rax
	orq	$1, %rax
	retq
                                        # -- End function

So I think we're good here! Thanks!

[RalfJung]

Is it worth adding a codegen test for this?

[saethlin]

Possibly. But we have a small problem maybe? All three of those compile to different IR:

define nonnull ptr @_ZN7example9old_style17h5807fc970566528bE(ptr %a) unnamed_addr #0 {
  %_3 = ptrtoint ptr %a to i64
  %_2 = or i64 %_3, 1
  %0 = inttoptr i64 %_2 to ptr
  ret ptr %0
}

define ptr @_ZN7example12cheri_compat17hf4c9a96c91413294E(ptr %a) unnamed_addr #0 {
  %old = ptrtoint ptr %a to i64
  %old.not = and i64 %old, 1
  %diff = xor i64 %old.not, 1
  %0 = getelementptr i8, ptr %a, i64 %diff
  ret ptr %0
}

define ptr @_ZN7example4fast17hfe789c747db55c0eE(ptr %a) unnamed_addr #0 {
  %old = ptrtoint ptr %a to i64
  %new = or i64 %old, 1
  %count = sub i64 0, %old
  %0 = getelementptr i8, ptr %a, i64 %count
  %1 = getelementptr i8, ptr %0, i64 %new
  ret ptr %1
}

So I could write a codegen test that checks that they compile to what they do right now, but I feel like it would be valid and good for LLVM to produce the same IR for all 3, and it would be a bummer if the codegen test broke when it does.

If there's a way around this, I'm happy to PR the codegen test.

[nikic]

The codegen test in this case would be an x86 assembly codegen test. The LLVM IR cannot be the same, because all of those have different semantics (in terms of provenance).

[RalfJung]

The last two should be identical in terms of provenance?