This is an archive of the discontinued LLVM Phabricator instance.

[libc++] Implement P1004R2 (constexpr std::vector)
ClosedPublic

Authored by philnik on Oct 2 2019, 5:42 PM.

Event Timeline

rsmith created this revision.Oct 2 2019, 5:42 PM
Herald added a project: Restricted Project. · View Herald TranscriptOct 2 2019, 5:42 PM
Herald added a subscriber: christof. · View Herald Transcript
rsmith updated this revision to Diff 222945.Oct 2 2019, 5:48 PM

Move some changes from here to the std::allocator change.

ldionne added a subscriber: ldionne.Oct 3 2019, 7:24 AM

I'll pick this up. I wasn't aware you had started working on this, but thanks!

ldionne commandeered this revision.Oct 3 2019, 7:44 AM
ldionne added a reviewer: rsmith.
ldionne updated this revision to Diff 302609.Nov 3 2020, 10:13 AM

I've had a revision locally for a long long time. It doesn't pass everything
yet, but I've managed to get it down to ~10 failing tests with a few more hacks
locally.

Herald added a reviewer: Restricted Project. · View Herald TranscriptNov 3 2020, 10:13 AM
miscco added a subscriber: miscco.Nov 3 2020, 11:14 AM

Some quick review of the the acutal changes to the headers

libcxx/include/memory
1532–1533

I am wondering whether we should reuse the simplementation of std::copy_n here (or at the call site for what its worth)

2078–2079

As said above, we should be able to reuse the internals of std::copy_n here

2249–2251

From here and below there is _LIBCPP_CONSTEXPR_AFTER_CXX11 rather than _LIBCPP_CONSTEXPR_AFTER_CXX17

Also the ordering of _LIBCPP_INLINE_VISIBILITY and _LIBCPP_CONSTEXPR_AFTER_CXX11 is swapped.

2398

I believe the inline is superfluous with the _LIBCPP_CONSTEXPR_AFTER_CXX17

Appears throughout

libcxx/include/vector
420

Many inline below here

ldionne updated this revision to Diff 427645.May 6 2022, 8:20 AM
ldionne added a subscriber: philnik.

Rebase onto main.

@miscco's comments have not been addressed yet -- I only did the minimal amount of work to fix merge conflicts with main.

Note that not all tests have been constexpr-ified yet, and the ones that have been constexpr-ified are not all passing. Transferring to @philnik as discussed offline.

Herald added a project: Restricted Project. · View Herald TranscriptMay 6 2022, 8:20 AM
Herald added a subscriber: ormris. · View Herald Transcript
philnik commandeered this revision.May 6 2022, 8:23 AM
philnik added a reviewer: ldionne.
philnik updated this revision to Diff 427760.May 6 2022, 2:51 PM
philnik marked 5 inline comments as done.
  • Fix tests
libcxx/include/memory
1532–1533

I think this and the comment below have been addressed. But I'm not 100% sure what you were referring to exactly. Could you comment again at the correct line if the comments haven't been addressed?

2249–2251

Sorry, I don't know what you are referring to again. I guess they have been addressed since I can't see any _LIBCPP_CONSTEXPR_AFTER_CXX11 of inline in the diff.

libcxx/include/vector
420

Again, I guess it has been addressed?

philnik retitled this revision from Prototype implementation of P1004R2 (making std::vector constexpr). to Implement P1004R2 (constexpr std::vector).
philnik edited the summary of this revision. (Show Details)
philnik updated this revision to Diff 427832.May 7 2022, 2:20 AM
  • Try to fix CI
philnik updated this revision to Diff 427839.May 7 2022, 3:21 AM
  • Next try
philnik updated this revision to Diff 427845.May 7 2022, 4:31 AM
  • Try to fix GCC
philnik retitled this revision from Implement P1004R2 (constexpr std::vector) to [libc++] Implement P1004R2 (constexpr std::vector).May 7 2022, 4:43 AM
philnik updated this revision to Diff 427927.May 8 2022, 5:26 AM
  • Try to fix CI
philnik updated this revision to Diff 431097.May 20 2022, 4:57 PM
  • Rebased
  • Fix parts of CI
philnik updated this revision to Diff 436255.Jun 12 2022, 2:53 PM
  • Try to fix C++03
ldionne requested changes to this revision.Jun 16 2022, 12:01 PM
ldionne added a subscriber: var-const.
ldionne added inline comments.
libcxx/include/__bit_reference
358–361 ↗(On Diff #436255)

I think we should always call std::fill_n here instead. Indeed, both are equivalent, but std::fill_n is nicer for various reasons.

I know fill_n doesn't end up calling memset directly, however the compiler will end up calling memset (when optimized). IIRC, @var-const was actually about to add this optimization to fill_n explicitly, when we realized it didn't have an impact on the code generation. @var-const can you confirm?

Also, I think we need to add a comment in std::fill_n that explains this. I think it can be done in this patch since we're switching from memset to fill_n.

This comment applies elsewhere in this patch too.

503 ↗(On Diff #436255)

Why is this required?

958–961 ↗(On Diff #436255)

Instead, I would begin the lifetime of the elements inside __bit_array's constructor if we are during constant evaluation. That way you shouldn't need to change this code at all.

libcxx/include/__memory/construct_at.h
43–44 ↗(On Diff #436255)

Please match the style of the class = decltype above, just for consistency.

49 ↗(On Diff #436255)

Let's add the _LIBCPP_ASSERT here too.

libcxx/include/__utility/move.h
40–49 ↗(On Diff #436255)

I don't think this diff is needed in this patch, see my comment below.

libcxx/include/memory
2002

I don't think we *need* to make this change to enable constexpr vector, right? If not, let's pull it into a separate patch, cause I'd like to have a discussion about it. Otherwise, can you please explain why it's needed?

2070–2146

Given that __begin2 = std::__copy(__begin1, __end1, __begin2); does not compile, I think this overload is never used. Can you please confirm this by adding static_assert(sizeof(_Alloc) == 0, "") and running the tests? If the tests don't fail, then this is a dead code path and we'll need to investigate it.

Edit Well, it looks like we've got enable_if<cond>::type above as a template parameter. IOW, we're declaring a NTTP of type void, and that's never valid. 🤦🏼‍♂️ Clang should really tell us about that. Let's fix it in a separate patch prior to this one.

2147–2148

Why are we using std::__copy here? Let's use std::copy instead.

2158–2402

I think this should all just be uninitialized_copy (or a __ version of it).

This revision now requires changes to proceed.Jun 16 2022, 12:01 PM
philnik updated this revision to Diff 440151.Jun 27 2022, 3:18 AM
philnik marked 10 inline comments as done.
  • Address comments
philnik added inline comments.Jun 27 2022, 3:18 AM
libcxx/include/__bit_reference
503 ↗(On Diff #436255)

It's not. I probably changed that during some debugging.

libcxx/include/memory
2158–2402

Just for reference, this is D128146 now.

var-const added inline comments.Jul 2 2022, 2:36 PM
libcxx/include/__bit_reference
358–361 ↗(On Diff #436255)

I can confirm that working on https://reviews.llvm.org/D118329, I found that the compiler would replace uninitialized_fill{,_n} with calls to memset in an optimized build, which made it unnecessary to write that optimization explicitly. I would expect fill_n to work similarly, but I have only tried with the uninitialized algorithms. FWIW, I have a lingering suspicion that there might be some corner cases (related to aliasing, perhaps) where the compiler would fail to do the optimization, but it was absolutely reliable in all the (simple) cases I checked.

ldionne requested changes to this revision.Jul 6 2022, 2:52 PM
ldionne added inline comments.
libcxx/include/__bit_reference
388 ↗(On Diff #440151)

I think it would be more obvious if we at least used static_cast<__storage_type>(-1).

Either way we should probably add a comment.

libcxx/include/vector
1837

What happens if we remove this condition? If the issue is with comparing pointers to unrelated areas of memory, what happens when you use std::less to perform the comparison instead? std::less has a special blessing when it comes to comparing unrelated pointers (yes, it's crazy).

1947

What happens if we remove this condition?

This revision now requires changes to proceed.Jul 6 2022, 2:52 PM
philnik updated this revision to Diff 442929.Jul 7 2022, 8:18 AM
philnik marked 3 inline comments as done.
  • Address comments
libcxx/include/vector
1837

It still complains that the pointers are unrelated.

1947

Here it also complains about comparing unrelated pointers.

ldionne accepted this revision.Jul 7 2022, 8:39 AM
ldionne added inline comments.
libcxx/include/__bit_reference
388 ↗(On Diff #440151)

Marked as done, but not done?

libcxx/include/vector
1947

Can you please add a comment like

// We can't compare unrelated pointers inside constant expressions

in both places?

This revision is now accepted and ready to land.Jul 7 2022, 8:39 AM
philnik updated this revision to Diff 446247.Jul 20 2022, 1:13 PM
philnik marked 2 inline comments as done.
  • Rebased
  • Address comments
philnik updated this revision to Diff 446636.Jul 21 2022, 2:34 PM
  • Rebased
  • Try to fix CI
EricWF added inline comments.Jul 22 2022, 9:13 AM
libcxx/include/__bit_reference
358–361 ↗(On Diff #436255)

@ldionne @var-const Can we get a godbolt showing a call to fill_n that gets lowered to memset?

libcxx/include/vector
552

Is this ever constexpr with the calls to the debug functions?

796

is this function actually constexpr-able?

philnik updated this revision to Diff 447731.Jul 26 2022, 8:58 AM
philnik marked 2 inline comments as done.

Rebased

libcxx/include/vector
552

The std::__debug_db_* have if (!__libcpp_is_constant_evaluated()) in them.

796

Why wouldn't it? We're just comparing pointers in there.

ldionne added inline comments.Jul 26 2022, 1:13 PM
libcxx/include/__bit_reference
358–361 ↗(On Diff #436255)

https://godbolt.org/z/je1PGzGds

There is a test for 0 size after the patch, because we do that in fill_n. We might or might not want to look into it, but this can be tackled as a separate issue.

philnik updated this revision to Diff 448006.Jul 27 2022, 5:19 AM
  • XFAIL tests and add a reproducer
This revision was automatically updated to reflect the committed changes.
alexfh added a subscriber: alexfh.Aug 10 2022, 12:36 AM

This commit breaks some code in c++20 mode: https://gcc.godbolt.org/z/h7j93MGsb

Specifically, move assignment of a vector of incomplete type can't be compiled now. Is this expected?

#include <vector>

struct S {
  S(S&& s) { v = std::move(s.v); }
  struct Inner;
  std::vector<Inner> v;
};

struct S::Inner {
  int a;
};
In file included from <source>:1:
/opt/compiler-explorer/clang-trunk-20220809/bin/../include/c++/v1/vector:540:52: error: arithmetic on a pointer to an incomplete type 'S::Inner'
        {return static_cast<size_type>(__end_cap() - this->__begin_);}
                                       ~~~~~~~~~~~ ^
/opt/compiler-explorer/clang-trunk-20220809/bin/../include/c++/v1/vector:760:56: note: in instantiation of member function 'std::vector<S::Inner>::capacity' requested here
      __annotate_contiguous_container(data(), data() + capacity(),
                                                       ^
/opt/compiler-explorer/clang-trunk-20220809/bin/../include/c++/v1/vector:431:7: note: in instantiation of member function 'std::vector<S::Inner>::__annotate_delete' requested here
      __annotate_delete();
      ^
<source>:4:3: note: in instantiation of member function 'std::vector<S::Inner>::~vector' requested here
  S(S&& s) { v = std::move(s.v); }
  ^
<source>:5:10: note: forward declaration of 'S::Inner'
  struct Inner;
         ^
In file included from <source>:1:
/opt/compiler-explorer/clang-trunk-20220809/bin/../include/c++/v1/vector:760:54: error: arithmetic on a pointer to an incomplete type 'const value_type' (aka 'const S::Inner')
      __annotate_contiguous_container(data(), data() + capacity(),
                                              ~~~~~~ ^
/opt/compiler-explorer/clang-trunk-20220809/bin/../include/c++/v1/vector:431:7: note: in instantiation of member function 'std::vector<S::Inner>::__annotate_delete' requested here
      __annotate_delete();
      ^
<source>:4:3: note: in instantiation of member function 'std::vector<S::Inner>::~vector' requested here
  S(S&& s) { v = std::move(s.v); }
  ^
<source>:5:10: note: forward declaration of 'S::Inner'
  struct Inner;
         ^
In file included from <source>:1:
/opt/compiler-explorer/clang-trunk-20220809/bin/../include/c++/v1/vector:833:64: error: arithmetic on a pointer to an incomplete type 'S::Inner'
        __alloc_traits::destroy(__alloc(), _VSTD::__to_address(--__soon_to_be_end));
                                                               ^ ~~~~~~~~~~~~~~~~
/opt/compiler-explorer/clang-trunk-20220809/bin/../include/c++/v1/vector:827:29: note: in instantiation of member function 'std::vector<S::Inner>::__base_destruct_at_end' requested here
  void __clear() _NOEXCEPT {__base_destruct_at_end(this->__begin_);}
                            ^
/opt/compiler-explorer/clang-trunk-20220809/bin/../include/c++/v1/vector:436:9: note: in instantiation of member function 'std::vector<S::Inner>::__clear' requested here
        __clear();
        ^
<source>:4:3: note: in instantiation of member function 'std::vector<S::Inner>::~vector' requested here
  S(S&& s) { v = std::move(s.v); }
  ^
<source>:5:10: note: forward declaration of 'S::Inner'
  struct Inner;
         ^
In file included from <source>:1:
In file included from /opt/compiler-explorer/clang-trunk-20220809/bin/../include/c++/v1/vector:296:
In file included from /opt/compiler-explorer/clang-trunk-20220809/bin/../include/c++/v1/__split_buffer:20:
/opt/compiler-explorer/clang-trunk-20220809/bin/../include/c++/v1/__memory/allocator.h:128:58: error: invalid application of 'sizeof' to an incomplete type 'S::Inner'
            _VSTD::__libcpp_deallocate((void*)__p, __n * sizeof(_Tp), _LIBCPP_ALIGNOF(_Tp));
                                                         ^~~~~~~~~~~
/opt/compiler-explorer/clang-trunk-20220809/bin/../include/c++/v1/__memory/allocator_traits.h:282:13: note: in instantiation of member function 'std::allocator<S::Inner>::deallocate' requested here
        __a.deallocate(__p, __n);
            ^
/opt/compiler-explorer/clang-trunk-20220809/bin/../include/c++/v1/vector:437:25: note: in instantiation of member function 'std::allocator_traits<std::allocator<S::Inner>>::deallocate' requested here
        __alloc_traits::deallocate(__alloc(), this->__begin_, capacity());
                        ^
<source>:4:3: note: in instantiation of member function 'std::vector<S::Inner>::~vector' requested here
  S(S&& s) { v = std::move(s.v); }
  ^
<source>:5:10: note: forward declaration of 'S::Inner'
  struct Inner;
         ^
In file included from <source>:1:
/opt/compiler-explorer/clang-trunk-20220809/bin/../include/c++/v1/vector:537:53: error: arithmetic on a pointer to an incomplete type 'S::Inner'
        {return static_cast<size_type>(this->__end_ - this->__begin_);}
                                       ~~~~~~~~~~~~ ^
/opt/compiler-explorer/clang-trunk-20220809/bin/../include/c++/v1/vector:636:32: note: in instantiation of member function 'std::vector<S::Inner>::size' requested here
        size_type __old_size = size();
                               ^
/opt/compiler-explorer/clang-trunk-20220809/bin/../include/c++/v1/vector:953:9: note: in instantiation of member function 'std::vector<S::Inner>::clear' requested here
        clear();
        ^
/opt/compiler-explorer/clang-trunk-20220809/bin/../include/c++/v1/vector:1314:5: note: in instantiation of member function 'std::vector<S::Inner>::__vdeallocate' requested here
    __vdeallocate();
    ^
/opt/compiler-explorer/clang-trunk-20220809/bin/../include/c++/v1/vector:1288:5: note: in instantiation of member function 'std::vector<S::Inner>::__move_assign' requested here
    __move_assign(__x, integral_constant<bool,
    ^
<source>:4:16: note: in instantiation of member function 'std::vector<S::Inner>::operator=' requested here
  S(S&& s) { v = std::move(s.v); }
               ^
<source>:5:10: note: forward declaration of 'S::Inner'
  struct Inner;
         ^
5 errors generated.
Compiler returned: 1

@alexfh I'm not sure why this worked before, but you've definitely got UB there: http://eel.is/c++draft/vector#overview-4. Clang is probably less permissive when something is declared constexpr.

@alexfh I'm not sure why this worked before, but you've definitely got UB there: http://eel.is/c++draft/vector#overview-4. Clang is probably less permissive when something is declared constexpr.

I see. Thanks for the reference!

sberg added a subscriber: sberg.Aug 16 2022, 5:15 AM

For a -DLIBCXX_ENABLE_DEBUG_MODE=ON build this now causes

$ cat test.cc
#define _LIBCPP_DEBUG 1
#include <vector>
static std::vector<int> v;
int main() {
    v.push_back(0);
    int a = 0;
    for (auto i: v) a += i;
    return a;
}

$ clang++ -stdlib=libc++ -std=c++20 test.cc
$ ./a.out
~/llvm/inst/bin/../include/c++/v1/__iterator/wrap_iter.h:87: assertion ::std::__libcpp_is_constant_evaluated() || (__get_const_db()->__dereferenceable(this)) failed: Attempted to dereference a non-dereferenceable iteratorAborted (core dumped)

For a -DLIBCXX_ENABLE_DEBUG_MODE=ON build this now causes

$ cat test.cc
#define _LIBCPP_DEBUG 1
#include <vector>
static std::vector<int> v;
int main() {
    v.push_back(0);
    int a = 0;
    for (auto i: v) a += i;
    return a;
}

$ clang++ -stdlib=libc++ -std=c++20 test.cc
$ ./a.out
~/llvm/inst/bin/../include/c++/v1/__iterator/wrap_iter.h:87: assertion ::std::__libcpp_is_constant_evaluated() || (__get_const_db()->__dereferenceable(this)) failed: Attempted to dereference a non-dereferenceable iteratorAborted (core dumped)

We are aware of that. See https://llvm.org/PR56782.

Via Conduit