Avoid strict aliasing violation on type punning inside llvm::PointerIntPair

[brenoguim]

Summary

llvm::PointerIntPair has methods that when used together can invoke undefined behavior by violating strict aliasing.

getPointer() uses the underlying storage as it's declared: intptr_t
getAddrOfPointer() casts the underlying storage as if it was a PointerTy

This violates strict aliasing, so depending on how they are used, it's possible to have the compiler to optimize the code in unwanted ways.
See the unit test in the patch. We declare a PointerIntPair and use the getAddrOfPointer method to fill in the a pointer value.
Then, when we use getPointer the compiler is thrown off, thinking that intptr_t storage could not have possibly be changed, and the check fails.

I have no experience with llvm codebase, so I expect feedback on operational things like where to put the new class, how to format it and so on.

The solution is use a char buffer which is blessed by the standard for type punning. That alone is not enough. When accessing the intptr_t modeling, one also has to use std::memcpy to let the compiler know we are creating a new intptr_t using the bit pattern in the array of chars.

I recommend using the compiler explorer to play around with different solutions. There are a bunch of examples in the issue I reported in github: https://github.com/llvm/llvm-project/issues/55103

I must say, I'm not entirely sure the solution is correct, even though it works. It could be that the code still invokes undefined behavior, but has been fiddled in a way that the compiler cannot optimize based on UB. After all, you will see that the issue is fragile. Even seemingly harmless simplifications like commenting out the line with ++pairAddr will make the code work again.

[brenoguim]

llvm/unittests/ADT/PointerIntPairTest.cpp

114

Variables names should start with upper case

[brenoguim]

I created a compiler explorer example without PointerIntPair to show the core of the issue: https://godbolt.org/z/xvofbdYP8
I also added options in this example to use memcpy for reading the pointer and show that it solves the issue. I added an option to show that using "char" as underlying storage is not enough to solve the issue, though I still think it may be the correct thing to do.

[akyrtzi]

llvm/include/llvm/ADT/PointerIntPair.h

48

there should be a private: line to make Data inaccessible from outside.

49

I believe this can just be Ptr Data;, it doesn't need to be a char buffer, the memcpys should keep this in "defined behavior land" even if you are copying from a pointer type.

Then getPointerAddress() becomes

Ptr *getPointerAddress() { return &Data; }

[brenoguim]

llvm/include/llvm/ADT/PointerIntPair.h

49

True, I can't find any issue with that reasoning. I'll apply this change.

[akyrtzi]

llvm/include/llvm/ADT/PointerIntPair.h

28

I'd recommend to also add

static_assert(sizeof(Ptr) == sizeof(intptr_t), "");

for sanity checking.

[rjmccall]

llvm/include/llvm/ADT/PointerIntPair.h

49

I think Ptr is not actually required to be a pointer type — for example, it can be another PointerIntPair — which might interfere with being able to just store a Ptr.

[brenoguim]

• Updated variable names on test to start with upper case
• Added static_assert to check sizeof(Ptr) == sizeof(intptr)
• Added constexpr to toInt method so all are constexpr now, just in case
• Changed the underlying storage to be Ptr, removing the interpret cast

[brenoguim]

Oh, I didn't realize the some tests had failed. I'll get to it.

[brenoguim]

The plot thickens.

With my patch, the code below (extracted from a failing test about LLParser.cpp) aborts with all versions of clang *except* v14. Moreover, it passes with gcc (all versions I tested).

static llvm::PointerIntPair<double*, 3> ptr {(double*)-8};
int main()
{
    if (!ptr.getPointer())
        std::abort();
}

( https://godbolt.org/z/hrTqGfM65 )

It only happens with ptr being static. If it's local, then it passes with all compiler versions I tested.

So we are facing either one of:

1. The code is correct and there is a bug in clang that miscompiles it, and this bug was fixed on v14.
2. The code is still violating strict aliasing somehow neither GCC, nor Clang v14 are able to exploit it. And clang up to 14 is able to exploit it.

2 is unlikely because passing -fno-strict-aliasing on the versions that abort makes no difference.

Assuming then it's 1, my options are:

1. Rework the code with a different logic that is correct and not miscompiled on clang <v14
2. Make the test expect to fail when compiling with clang <v14

Any opinions/suggestions are welcome!

[brenoguim]

This is a reduced version of the issue: https://godbolt.org/z/zor6MhPT6
I was wrong. This only miscompiles only on clang 11, 12 and 13. It works fine on clang <v10 and on clang 14.

[efriedma]

This is a reduced version of the issue: https://godbolt.org/z/zor6MhPT6
I was wrong. This only miscompiles only on clang 11, 12 and 13. It works fine on clang <v10 and on clang 14.

That looks like a globalopt bug. I remember there was a patch in LLVM 14 related to this; I don't think it's something you can reasonably work around.

---

I think strictly speaking, to avoid UB you might need to declare "Data" as a union: otherwise, the compiler might assume the value it contains is aligned. I don't think clang does, in practice, but probably you want to be conservative.

[brenoguim]

That looks like a globalopt bug. I remember there was a patch in LLVM 14 related to this; I don't think it's something you can reasonably work around.

I thought of conditionally making PunnedPointer use aligned storage, which works even on clangs 11,12,13. Something in the lines of: https://godbolt.org/z/hv8jPceKK
That is ugly though.

I think strictly speaking, to avoid UB you might need to declare "Data" as a union: otherwise, the compiler might assume the value it contains is aligned. I don't think clang does, in practice, but probably you want to be conservative.

Do you mean that, in the current code, the compiler could see that I'm reading Data through a memcpy into intptr_t and then checking the last bits and say: "Hey, if these bits came from Data, and Data is a pointer to something that must be aligned, then those bits are certainly zero!" ?

In that case my conclusion would be to use an aligned char array instead of a pointer. I didn't understand how using a union (union with which members?) would help. I would also have to track the active member of the union to avoid tripping in another UB as well.

[efriedma]

In D124571#3489362, @brenoguim wrote:

I think strictly speaking, to avoid UB you might need to declare "Data" as a union: otherwise, the compiler might assume the value it contains is aligned. I don't think clang does, in practice, but probably you want to be conservative.

Do you mean that, in the current code, the compiler could see that I'm reading Data through a memcpy into intptr_t and then checking the last bits and say: "Hey, if these bits came from Data, and Data is a pointer to something that must be aligned, then those bits are certainly zero!" ?

I'm thinking something more like: you pass a PunnedPointer as an argument to a function. It's passed in a register, and that register can be marked up with alignment. There was a proposed clang patch for this at one point, but it didn't land because we were concerned about breaking things.

In that case my conclusion would be to use an aligned char array instead of a pointer. I didn't understand how using a union (union with which members?) would help. I would also have to track the active member of the union to avoid tripping in another UB as well.

I was thinking a union { Ptr Data; void* VoidPtr } or something like that. If you access the union via memcpy, it shouldn't matter which member of the union is active, I think?

An aligned char array is probably also fine, though.

[brenoguim]

I was thinking a union { Ptr Data; void* VoidPtr } or something like that. If you access the union via memcpy, it shouldn't matter which member of the union is active, I think?

I have no idea, maybe. But I also have to support the getPointerAddress API which doesn't use memcpy, so it would force me to know which member is active.

I think I'll go with the aligned array of char for safety, if that's alright.

[brenoguim]

Changed the underlying storage of PunnedPointer to an array of char. It doesn't trigger the bug in clang (v12, v13, v14) and seems safer with regards to UB.

[akyrtzi]

llvm/include/llvm/ADT/PointerIntPair.h

46

I'm wondering if the standard "blesses" this use of reinterpret_cast or whether it's some kind of UB..

[brenoguim]

llvm/include/llvm/ADT/PointerIntPair.h

46

I can't find an explicit blessing in the standard, but I suppose this is fine by making a parallel with allocators:

Some allocators work by creating arrays of bytes and doing placement new on those bytes to form an object. That's perfectly valid.
The allocator can at anytime retrieve a T* from the byte* it has, as long as it had allocated the object there.

That's pretty much what we do here. We create a buffer and pretend to have a Ptr there.
Although, there we might be missing two things to be truly correct:

• May need to call placement new. It's a noop being a trivial type, but still...
• May need to call std::launder to indicate an object of type Ptr is supposed to be there. But that's C++17

So in the constructor I could do new (Data) Ptr just to be extra clear to the compiler that the buffer holds a Ptr.

But It's very hard to interpret the standard, so my analysis could be way off.

[dexonsmith]

llvm/include/llvm/ADT/PointerIntPair.h

46

@hubert.reinterpretcast might know.

[efriedma]

LGTM

Although, there we might be missing two things to be truly correct:

• May need to call placement new. It's a noop being a trivial type, but still...
• May need to call std::launder to indicate an object of type Ptr is supposed to be there. But that's C++17

You could implement operator= using something like if (isAligned(V)) new (Data) Ptr(reinterpret_cast<Ptr>(V)); else new (Data) intptr_t(V);, sure. But [cstring.syn] says memcpy implicitly creates objects, so I think it's effectively the same result.

(std::launder isn't relevant here. From [ptr.launder]: "If a new object is created in storage occupied by an existing object of the same type, a pointer to the original object can be used to refer to the new object unless its complete object is a const object or it is a base class subobject [...]".)

[brenoguim]

(std::launder isn't relevant here. From [ptr.launder]: "If a new object is created in storage occupied by an existing object of the same type, a pointer to the original object can be used to refer to the new object unless its complete object is a const object or it is a base class subobject [...]".)

I was referring to the other use of std::launder. From https://en.cppreference.com/w/cpp/utility/launder :

Obtaining a pointer to an object created by placement new from a pointer to an object providing storage for that object.

But indeed we did not call placement new, so that doesn't apply.

And now, I found the blessing to not call the placement new:

The lifetime of an object of type T begins when:
(1.1) — storage with the proper alignment and size for type T is obtained, and
(1.2) — if the object has non-vacuous initialization, its initialization is complete,

So by instantiating the array of char we can say the lifetime of Ptr already started. No need for placement new.

Now I'm more confident this is the right way to go.

[brenoguim]

No, wait... We can have a PunnedPointer<PointerIntPair<int*>>, and the constructor of PointerIntPair is not trivial, because it holds a PunnedPointer which does not have a trivial constructor. Back to the drawing board.

[brenoguim]

[cstring.syn] says memcpy implicitly creates objects, so I think it's effectively the same result.

@efriedma Do you have reference to that?

[efriedma]

No, wait... We can have a PunnedPointer<PointerIntPair<int*>>, and the constructor of PointerIntPair is not trivial, because it holds a PunnedPointer which does not have a trivial constructor. Back to the drawing board.

If you want to support calling getPointerAddress() in that case, then yes, I think you need to use placement new or a union. Anything that involves "implicitly creating objects" will only work with implicit-lifetime types.

In D124571#3495535, @brenoguim wrote:

[cstring.syn] says memcpy implicitly creates objects, so I think it's effectively the same result.

@efriedma Do you have reference to that?

[cstring.syn] is a section in the standard? (You can search for the string "cstring.dyn" in the standard/a standard draft. Or online version: https://timsong-cpp.github.io/cppwp/cstring.syn .)

[brenoguim]

[cstring.syn] is a section in the standard? (You can search for the string "cstring.dyn" in the standard/a standard draft. Or online version: https://timsong-cpp.github.io/cppwp/cstring.syn .)

I was searching the C++14 standard. It seems this "memcpy creates objects" sentence was introduced in C++20.

By the way, even though we can still discuss if the code is 100% correct, I think it's definitely an improvement that fixes a bug, so I wouldn't mind having it landed like it is now.

[brenoguim]

Since PointerIntPair may hold non-trivially-constructible types (like another PointerIntPair), I added a placement new of the inner type to make sure we comply with the standard by explicitly starting the lifetime of the Ptr object in the storage. This allows me to reinterpret_cast this storage as Ptr in getPointerAddress.

I also added static asserts that the inner type is trivially copy constructible, move constructible and destructible, that gives me guarantees that the compiler generated the destructor and copy/move constructors of PunnedPointer are correct.

[efriedma]

I think the placement new call needs to be in the operator=, not the constructor, to have any effect.

If we assign a value with the low bit set, the object must be implicitly destroyed, and the memcpy must implicitly create a new object: otherwise, we have an object with an invalid value, which I don't think is valid. So the sequence "placement new, then memcpy a value with a low bit set, then memcpy a value without the low bit set, then call getPointerAddress()" doesn't work. (Not that a compiler is likely to ever exploit that, but I'm pretty sure that's how the model works.)

On the other hand, if we placement new in the assignment operator, then it's fine if the memcpy implicitly destroys the object; we'll placement new again before we need it. The sequence "placement new, then memcpy a value with a low bit set, then placement new, then memcpy a value without the low bit set, then call getPointerAddress()" works fine.

---

That said, looking again, I don't think the whole dance with placement new is necessary, given the restrictions you're placing on the contained type. A type which is trivially destructible and trivially movable must be an implicit-lifetime type. From [class.prop]: "A class S is an implicit-lifetime class if it is an aggregate or has at least one trivial eligible constructor and a trivial, non-deleted destructor." The type is allowed to have non-trivial constructors, as long as there's at least one trivial constructor (including a move constructor).

[brenoguim]

Rebasing

[brenoguim]

Hi @efriedma,

That said, looking again, I don't think the whole dance with placement new is necessary,

I think, I agree. I'll update that and I think this will be ready to land.
Sorry for the long delay to continue this work.

[brenoguim]

Remove placement new as it's not needed because Ptr must have a trivial move constructor and thus it's an implicit lifetime class.

[brenoguim]

Fixed formatting

[brenoguim]

Folks, I do not have write access to the llvm repository. I would appreciate if anyone could step up to merge this for me.
Thanks!

[vhscampos]

Hi @brenoguim, I will submit this patch for you.

[nikic]

FYI this showed up as a compile-time regression: https://llvm-compile-time-tracker.com/compare.php?from=af694df712f28f419883e322d7dc978f04bfe38f&to=875391728c11339c8a6cd3338bcaa5ec0ffc2496&stat=instructions:u

Though not sure if avoidable. I initially thought we can store the data as Ptr and use std::bit_cast for conversion to/from integer, but I guess that wouldn't work if Ptr is not actually a pointer but some non-POD data type?

[brenoguim]

The initial idea was to make Data a Ptr ( see https://reviews.llvm.org/D124571?id=425939 ) but that triggered an issue (the godbolt link there in the comment is broken): https://reviews.llvm.org/D124571#3487131
With that "better" implementation, clang <=13 miscompiles another piece of code inside llvm: https://godbolt.org/z/TG9KoxEev so I could not use it.

If the minimum version of clang to build LLVM/clang is 14+, then we can go with the former implementation and see if it improves.
Otherwise, that is the only way I got both the unit test and llvm build with clang13 to work.

llvm/include/llvm/ADT/PointerIntPair.h

 #ifndef LLVM_ADT_POINTERINTPAIR_H
 #define LLVM_ADT_POINTERINTPAIR_H
 
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/PointerLikeTypeTraits.h"
 #include "llvm/Support/type_traits.h"
 #include <cassert>
 #include <cstdint>
+#include <cstring>
 #include <limits>
 
 namespace llvm {
 
+namespace detail {
+template <typename Ptr> struct PunnedPointer {
+  static_assert(sizeof(Ptr) == sizeof(intptr_t), "");
+
+  // Asserts that allow us to let the compiler implement the destructor and
+  // copy/move constructors
+  static_assert(std::is_trivially_destructible<Ptr>::value, "");
+  static_assert(std::is_trivially_copy_constructible<Ptr>::value, "");
+  static_assert(std::is_trivially_move_constructible<Ptr>::value, "");
+
+  explicit constexpr PunnedPointer(intptr_t i = 0) { *this = i; }
+
+  constexpr intptr_t asInt() const {
+    intptr_t R = 0;
+    std::memcpy(&R, Data, sizeof(R));
+    return R;
+  }
+
+  constexpr operator intptr_t() const { return asInt(); }
+
+  constexpr PunnedPointer &operator=(intptr_t V) {
+    std::memcpy(Data, &V, sizeof(Data));
+    return *this;
+  }
+
+  Ptr *getPointerAddress() { return reinterpret_cast<Ptr *>(Data); }
+  const Ptr *getPointerAddress() const { return reinterpret_cast<Ptr *>(Data); }
+
+private:
+  alignas(Ptr) unsigned char Data[sizeof(Ptr)];
+};
+} // namespace detail
+
 template <typename T, typename Enable> struct DenseMapInfo;
 template <typename PointerT, unsigned IntBits, typename PtrTraits>
 struct PointerIntPairInfo;
 
 /// PointerIntPair - This class implements a pair of a pointer and small
 /// integer.  It is designed to represent this in the space required by one
 /// pointer by bitmangling the integer into the low part of the pointer.  This
 /// can only be done for small integers: typically up to 3 bits, but it depends
 /// on the number of bits available according to PointerLikeTypeTraits for the
 /// type.
 ///
 /// Note that PointerIntPair always puts the IntVal part in the highest bits
 /// possible.  For example, PointerIntPair<void*, 1, bool> will put the bit for
 /// the bool into bit #2, not bit #0, which allows the low two bits to be used
 /// for something else.  For example, this allows:
 ///   PointerIntPair<PointerIntPair<void*, 1, bool>, 1, bool>
 /// ... and the two bools will land in different bits.
 template <typename PointerTy, unsigned IntBits, typename IntType = unsigned,
           typename PtrTraits = PointerLikeTypeTraits<PointerTy>,
           typename Info = PointerIntPairInfo<PointerTy, IntBits, PtrTraits>>
 class PointerIntPair {
   // Used by MSVC visualizer and generally helpful for debugging/visualizing.
   using InfoTy = Info;
-  intptr_t Value = 0;
+  detail::PunnedPointer<PointerTy> Value;
 
 public:
   constexpr PointerIntPair() = default;
 
   PointerIntPair(PointerTy PtrVal, IntType IntVal) {
     setPointerAndInt(PtrVal, IntVal);
   }
 
public:
   PointerTy const *getAddrOfPointer() const {
     return const_cast<PointerIntPair *>(this)->getAddrOfPointer();
   }
 
   PointerTy *getAddrOfPointer() {
     assert(Value == reinterpret_cast<intptr_t>(getPointer()) &&
            "Can only return the address if IntBits is cleared and "
            "PtrTraits doesn't change the pointer");
-    return reinterpret_cast<PointerTy *>(&Value);
+    return Value.getPointerAddress();
   }
 
-  void *getOpaqueValue() const { return reinterpret_cast<void *>(Value); }
+  void *getOpaqueValue() const {
+    return reinterpret_cast<void *>(Value.asInt());
+  }
 
   void setFromOpaqueValue(void *Val) & {
     Value = reinterpret_cast<intptr_t>(Val);
   }
 
   static PointerIntPair getFromOpaqueValue(void *V) {
     PointerIntPair P;
     P.setFromOpaqueValue(V);

llvm/unittests/ADT/PointerIntPairTest.cpp

TEST(PointerIntPairTest, ManyUnusedBits) {
   EXPECT_EQ(FixnumPointerTraits::NumLowBitsAvailable - 1,
             (int)PointerLikeTypeTraits<decltype(pair)>::NumLowBitsAvailable);
 
   static_assert(std::is_trivially_copyable_v<
                     PointerIntPair<Fixnum31, 1, bool, FixnumPointerTraits>>,
                 "trivially copyable");
 }
 
+TEST(PointerIntPairTest, TypePunning) {
+  int I = 0;
+  int *IntPtr = &I;
+
+  int **IntPtrBegin = &IntPtr;
+  int **IntPtrEnd = IntPtrBegin + 1;
+
+  PointerIntPair<int *, 1> Pair;
+  int **PairAddr = Pair.getAddrOfPointer();
+
+  while (IntPtrBegin != IntPtrEnd) {
+    *PairAddr = *IntPtrBegin;
+    ++PairAddr;
+    ++IntPtrBegin;
+  }
+  EXPECT_EQ(Pair.getPointer(), IntPtr);
+}
+
 } // end anonymous namespace