Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Emacs internals: Tagged pointers vs. C++ std:variant and LLVM (Part 3)

thecloudlet.github.io

Post reply on HN
Print view View original

31–39 of 39 posts

Re: Emacs internals: Tagged pointers vs. C++ std:variant and LLVM (Part 3)

#31

Post by tialaramex »

simonask wrote: post #30
uecker wrote: post #27

Earlier quoted context omitted.

But LLVM's optimizations aren't sound and this affects Rust too.

Huh? Which optimizations?

LLVM is quite sure that, for example, two pointers to different objects are different. That's true even if in fact the objects both lived in the exact same spot on the stack (but at different times). That's... well it's not what Rust wants but it's not necessarily an unacceptable outcome and Rust could just ask for their addresses and compare those...

Except it turns out if we ask for their addresses, which are the same integer, LLVM remembers it believed the pointers were different and insists those are different too.

Until you call its bluff and do arithmetic on them. Then, in some cases, it snaps out of it and remembers that they're identical...

This is a compiler bug, but, apparently it's such a tricky bug to fix that I stopped even looking to see whether they'd fixed it after a few years... It affects C, C++, Rust, all of them as a result can be miscompiled by a compiler using LLVM [it's easiest to demonstrate this bug with Rust but it's the same in every language]. But as you've probably noticed, this doesn't have such an enormous impact that anybody stopped using LLVM.

Re: Emacs internals: Tagged pointers vs. C++ std:variant and LLVM (Part 3)

#32

Post by thecloudlet »

ndesaulniers wrote: post #21

Happy to see discussion of LLVM's interesting implementation of Static Polymorphism using CRTP. Some recommended reads: 1. https://en.wikipedia.org/wiki/Curiously_recurring_template_p... 2. https://david.alvarezrosa.com/posts/devirtualization-and-sta... 3. https://llvm.org/docs/ProgrammersManual.html#the-isa-cast-an...

Thanks for the links, Nick! It's fascinating how LLVM relies so heavily on CRTP.

Re: Emacs internals: Tagged pointers vs. C++ std:variant and LLVM (Part 3)

#33

Post by uecker »

VorpalWay wrote: post #28
jcranmer wrote: post #25

Earlier quoted context omitted.

> But the likely destiny of C++ is to inherit the provenance rules that are an adjunct to C23, PNVI-ae-udi, Provenance Not Via Integers, Addresses Exposed, User Disambiguates There's a competing proposal in C++ land to add provenance via angelic nondeterminism: if there's some provenance that makes the code non-UB, then use that provenance. (As you might imagine, I'm not a big fan of that proposal, but WG21 seems to…

Very interesting discussion. I hadn't realised that the final provenance model hadn't yet been decided for C and C++. Angelic non-determinism seems difficult to use to determine if an optimisation is valid. If I understand this correctly, it is basically the as-if rule, but in this case applied to something that potentially needs global program analysis. Would that be an accurate understanding? It sounds like both of…

No, angelic non-determinism is not related to the as-if rule. It essentially says that if there is a choice to assign provenance on backconversion from integers, the one which makes the program valid is assigned. This is basically the same as the explicit UDI rule in TS 6010, except that this is rule is very clear. The problematic with angelic non-determinism is two-fold: a) most people will not be able to reason about it at all, and b) not even formal semantics experts know what it means in complicated cases. Demonic non-determinism essentially means that all possible execution must be valid while angelic non-determinism that there must exist at least one. Formally, this translates to universal and existential quantifiers. But for quantifiers, you must know where and in which order to place them in a formula, which wasn't clear all from the wording I have seen (a while ago). The interaction with concurrency is also a can of worms.

I don't think there is a fundamental advantage to Rust regarding provenance. Yes, we lack a way to do pointer tagging without exposing the provenance in C, but we could easily add this. But this is all moot as long as compilers are still not conforming to the provenance model with respect to integer and pointer casts anyway and this breaks Rust too! Rust having decided something just means they life in fairy tale world, while C/C++ not having decided means they acknowledge the reality that compilers haven't fixed their optimizers. (Even ignoring that "deciding" means entirely different things here anyway with C/C++ having ISO standards.)

Re: Emacs internals: Tagged pointers vs. C++ std:variant and LLVM (Part 3)

#34

Post by internet_points »

Drawn in by the Emacs, learnt something new about C and C++, thank you for this! Very readable article for someone who doesn't feel too confident with low-level bits.

Btw, is this representation the reason why OCaml's ints are not as big as C ints?

Also interesting that the Haskell pointer tagging you link to[0] was done the way it was to avoid CPU branch misprediction, and that the old way which it replaced was "the source of half of the branch misprediction events". I wonder how "branch prediction friendly" current Haskell is.

[0] https://simonmar.github.io/bib/papers/ptr-tagging.pdf

Re: Emacs internals: Tagged pointers vs. C++ std:variant and LLVM (Part 3)

#35

Post by VorpalWay »

uecker wrote: post #33
VorpalWay wrote: post #28

Earlier quoted context omitted.

Very interesting discussion. I hadn't realised that the final provenance model hadn't yet been decided for C and C++. Angelic non-determinism seems difficult to use to determine if an optimisation is valid. If I understand this correctly, it is basically the as-if rule, but in this case applied to something that potentially needs global program analysis. Would that be an accurate understanding? It sounds like both of…

No, angelic non-determinism is not related to the as-if rule. It essentially says that if there is a choice to assign provenance on backconversion from integers, the one which makes the program valid is assigned. This is basically the same as the explicit UDI rule in TS 6010, except that this is rule is very clear. The problematic with angelic non-determinism is two-fold: a) most people will not be able to reason abo…

> But this is all moot as long as compilers are still not conforming to the provenance model with respect to integer and pointer casts anyway and this breaks Rust too! Rust having decided something just means they life in fairy tale world, while C/C++ not having decided means they acknowledge the reality that compilers haven't fixed their optimizers.

I think this is a bit of a mischaracterization. While there can of course be bugs in LLVM (and rustc and clang), what sort of LLVM IR you generate matters. To be able to generate IR that conforms to the provenance model of the language you first need to have such a model.

As far as I know (and this matches what I found when search the rust issue tracker) there is currently one major known LLVM bug in this area (https://github.com/rust-lang/rust/issues/147538) with partial workarounds applied on the Rust side. There is some issues with open question still, such as how certain unstable features should interact with provenance.

I think calling the current situation "fairy tale world" is a gross exaggeration. Is it perfectly free of bugs? No, but if that is the criteria, then the entirety of any compiler is a fairy tale (possibly with the exception of some formally verified compiler).

Re: Emacs internals: Tagged pointers vs. C++ std:variant and LLVM (Part 3)

#36

Post by uecker »

VorpalWay wrote: post #35
uecker wrote: post #33

Earlier quoted context omitted.

No, angelic non-determinism is not related to the as-if rule. It essentially says that if there is a choice to assign provenance on backconversion from integers, the one which makes the program valid is assigned. This is basically the same as the explicit UDI rule in TS 6010, except that this is rule is very clear. The problematic with angelic non-determinism is two-fold: a) most people will not be able to reason abo…

> But this is all moot as long as compilers are still not conforming to the provenance model with respect to integer and pointer casts anyway and this breaks Rust too! Rust having decided something just means they life in fairy tale world, while C/C++ not having decided means they acknowledge the reality that compilers haven't fixed their optimizers. I think this is a bit of a mischaracterization. While there can of…

I am not sure this is a mischaracterization. The C provenance model also exists, even as a form of an ISO TS. The Rust model copied the basic concepts and even the terminology from us. The reason the C model is is not in ISO C 23 but in a separate TS is because compilers are not able to implement correctly at this time due to bugs. But neither do they implement the Rust model correctly because of the same bugs.

One should also point out that basic provenance is already part of the ISO C standard for a long time (but not under this name). That a precise technical specification is needed is only because the exact details were not clear and there are inconsistencies and differences between and even inside compilers. Rust having a precise model does not make these problems automatically go away just as the ISO TS does not.

Re: Emacs internals: Tagged pointers vs. C++ std:variant and LLVM (Part 3)

#37

Post by ndesaulniers »

thecloudlet wrote: post #32
ndesaulniers wrote: post #21

Happy to see discussion of LLVM's interesting implementation of Static Polymorphism using CRTP. Some recommended reads: 1. https://en.wikipedia.org/wiki/Curiously_recurring_template_p... 2. https://david.alvarezrosa.com/posts/devirtualization-and-sta... 3. https://llvm.org/docs/ProgrammersManual.html#the-isa-cast-an...

Thanks for the links, Nick! It's fascinating how LLVM relies so heavily on CRTP.

Consider amending those references to your post!

Re: Emacs internals: Tagged pointers vs. C++ std:variant and LLVM (Part 3)

#38

Post by thecloudlet »

ndesaulniers wrote: post #37
thecloudlet wrote: post #32

Earlier quoted context omitted.

Thanks for the links, Nick! It's fascinating how LLVM relies so heavily on CRTP.

Consider amending those references to your post!

Sure! I have updated my post! Thanks for your reference.

Re: Emacs internals: Tagged pointers vs. C++ std:variant and LLVM (Part 3)

#39

Post by dalvrosa »

ndesaulniers wrote: post #21

Happy to see discussion of LLVM's interesting implementation of Static Polymorphism using CRTP. Some recommended reads: 1. https://en.wikipedia.org/wiki/Curiously_recurring_template_p... 2. https://david.alvarezrosa.com/posts/devirtualization-and-sta... 3. https://llvm.org/docs/ProgrammersManual.html#the-isa-cast-an...

Thanks a lot for the reference!
Post reply on HN