Magic-Mirror/llvm-capstone
1
0
Fork 0
mirror of https://github.com/capstone-engine/llvm-capstone.git synced 2025-05-16 10:56:21 +00:00
Code Issues Actions 1 Packages Projects Releases Wiki Activity
487,757 Commits 13 Branches 0 Tags
Commit Graph

297 Commits

Author SHA1 Message Date
Louis Dionne
615e6dd1c5
[🍒][libc++] Fix missing and incorrect push/pop macros (#79204) (#79497) 
We recently noticed that the unwrap_iter.h file was pushing macros, but
it was pushing them again instead of popping them at the end of the
file. This led to libc++ basically swallowing any custom definition of
these macros in user code:

    #define min HELLO
    #include <algorithm>
    // min is not HELLO anymore, it's not defined

While investigating this issue, I noticed that our push/pop pragmas were
actually entirely wrong too. Indeed, instead of pushing macros like
`move`, we'd push `move(int, int)` in the pragma, which is not a valid
macro name. As a result, we would not actually push macros like `move`
-- instead we'd simply undefine them. This led to the following code not
working:

    #define move HELLO
    #include <algorithm>
    // move is not HELLO anymore

Fixing the pragma push/pop incantations led to a cascade of issues
because we use identifiers like `move` in a large number of places, and
all of these headers would now need to do the push/pop dance.

This patch fixes all these issues. First, it adds a check that we don't
swallow important names like min, max, move or refresh as explained
above. This is done by augmenting the existing
system_reserved_names.gen.py test to also check that the macros are what
we expect after including each header.

Second, it fixes the push/pop pragmas to work properly and adds missing
pragmas to all the files I could detect a failure in via the newly added
test.

rdar://121365472
(cherry picked from commit 7b4622514d232ce5f7110dd8b20d90e81127c467)
 2024-02-01 17:51:34 -08:00
Konstantin Varlamov
8938bc0ad0
[libc++][hardening] Categorize assertions related to strict weak ordering (#77405) 
If a user passes a comparator that doesn't satisfy strict weak ordering
(see https://eel.is/c++draft/algorithms#alg.sorting.general) to
a sorting algorithm, the algorithm can produce an incorrect result or
even lead
to an out-of-bounds access. Unfortunately, comprehensively validating
that a given comparator indeed satisfies the strict weak ordering
requirement is prohibitively expensive (see [the related
RFC](https://discourse.llvm.org/t/rfc-strict-weak-ordering-checks-in-the-debug-libc/70217)).
As a result, we have three independent sets of checks:

- assertions that catch out-of-bounds accesses within the algorithms'
  implementation. These are relatively cheap; however, they cannot catch
  the underlying cause and cannot prevent the case where an invalid
  comparator would result in an incorrectly-sorted sequence without
  actually triggering an OOB access;

- debug comparators that wrap a given comparator and on each comparison
  check that if `(a < b)`, then `!(b < a)`, where `<` stands for the
  user-provided comparator. This performs up to 2x number of comparisons
  but doesn't affect the algorithmic complexity. While this approach can
  find more issues, it is still a heuristic;

- a comprehensive check of the comparator that validates up to 100
  elements in the resulting sorted sequence (see the RFC above for
details). The check is expensive but the 100 element limit can somewhat
  compensate for that, especially for large values of `N`.

The first set of checks is enabled in the fast hardening mode while the
other two are only enabled in the debug mode.

This patch also removes the
`_LIBCPP_DEBUG_STRICT_WEAK_ORDERING_CHECK` macro that
previously was used to selectively enable the 100-element check.
Now this check is enabled unconditionally in the debug mode.

Also, introduce a new category
`_LIBCPP_ASSERT_SEMANTIC_REQUIREMENT`. This category is
intended for checking the semantic requirements from the Standard.
Typically, these are hard or impossible to completely validate, so
these checks are expected to be heuristic in nature and potentially
quite expensive.

See https://reviews.llvm.org/D150264 for additional background.
Fixes #71496
 2024-01-22 23:31:58 -08:00
Konstantin Varlamov
dc57752031
[libc++][hardening] Categorize assertions that produce incorrect results (#77183) 
Introduce a new `argument-within-domain` category that covers cases
where the given arguments make it impossible to produce a correct result
(or create a valid object in case of constructors). While the incorrect
result doesn't create an immediate problem within the library (like e.g.
a null pointer dereference would), it always indicates a logic error in
user code and is highly likely to lead to a bug in the program once the
value is used.
 2024-01-20 23:38:02 -08:00
Konstantin Varlamov
4f215fdd62
[libc++][hardening] Categorize more assertions. (#75918) 
Also introduce `_LIBCPP_ASSERT_PEDANTIC` for assertions violating which
results in a no-op or other benign behavior, but which may nevertheless
indicate a bug in the invoking code.
 2024-01-05 16:29:23 -08:00
Nikolas Klauser
b203d5320d
[libc++] Optimize std::find if types are integral and have the same signedness (#70345) 
Fixes #70238
 2023-12-23 11:21:27 +01:00
Konstantin Varlamov
1638657dce
[libc++][hardening] Categorize more 'valid-element-access' checks. (#71620) 2023-12-20 17:24:48 -08:00
Christopher Di Bella
3903438860
[libcxx] adds ranges::fold_left_with_iter and ranges::fold_left (#75259) 
Notable things in this commit:

* refactors `__indirect_binary_left_foldable`, making it slightly
different (but equivalent) to _`indirect-binary-left-foldable`_, which
improves readability (a [patch to the Working Paper][patch] was made)
* omits `__cpo` namespace, since it is not required for implementing
niebloids (a cleanup should happen in 2024)
* puts tests ensuring invocable robustness and dangling correctness
inside the correctness testing to ensure that the algorithms' results
are still correct

[patch]: https://github.com/cplusplus/draft/pull/6734
 2023-12-19 21:57:50 -08:00
ZijunZhaoCCK
fdd089b500
[libc++] Implement ranges::contains (#65148) 
Differential Revision: https://reviews.llvm.org/D159232
```
Running ./ranges_contains.libcxx.out
Run on (10 X 24.121 MHz CPU s)
CPU Caches:
  L1 Data 64 KiB (x10)
  L1 Instruction 128 KiB (x10)
  L2 Unified 4096 KiB (x5)
Load Average: 3.37, 6.77, 5.27
--------------------------------------------------------------------
Benchmark                          Time             CPU   Iterations
--------------------------------------------------------------------
bm_contains_char/16             1.88 ns         1.87 ns    371607095
bm_contains_char/256            7.48 ns         7.47 ns     93292285
bm_contains_char/4096           99.7 ns         99.6 ns      7013185
bm_contains_char/65536          1296 ns         1294 ns       540436
bm_contains_char/1048576       23887 ns        23860 ns        29302
bm_contains_char/16777216     389420 ns       389095 ns         1796
bm_contains_int/16              7.14 ns         7.14 ns     97776288
bm_contains_int/256             90.4 ns         90.3 ns      7558089
bm_contains_int/4096            1294 ns         1290 ns       543052
bm_contains_int/65536          20482 ns        20443 ns        34334
bm_contains_int/1048576       328817 ns       327965 ns         2147
bm_contains_int/16777216     5246279 ns      5239361 ns          133
bm_contains_bool/16             2.19 ns         2.19 ns    322565780
bm_contains_bool/256            3.42 ns         3.41 ns    205025467
bm_contains_bool/4096           22.1 ns         22.1 ns     31780479
bm_contains_bool/65536           333 ns          332 ns      2106606
bm_contains_bool/1048576        5126 ns         5119 ns       135901
bm_contains_bool/16777216      81656 ns        81574 ns         8569
```

---------

Co-authored-by: Nathan Gauër <brioche@google.com>
 2023-12-19 16:34:19 -08:00
Louis Dionne
9783f28cbb
[libc++] Format the code base (#74334) 
This patch runs clang-format on all of libcxx/include and libcxx/src, in
accordance with the RFC discussed at [1]. Follow-up patches will format
the benchmarks, the test suite and remaining parts of the code. I'm
splitting this one into its own patch so the diff is a bit easier to
review.

This patch was generated with:

   find libcxx/include libcxx/src -type f \
      | grep -v 'module.modulemap.in' \
      | grep -v 'CMakeLists.txt' \
      | grep -v 'README.txt' \
      | grep -v 'libcxx.imp' \
      | grep -v '__config_site.in' \
      | xargs clang-format -i

A Git merge driver is available in libcxx/utils/clang-format-merge-driver.sh
to help resolve merge and rebase issues across these formatting changes.

[1]: https://discourse.llvm.org/t/rfc-clang-formatting-all-of-libc-once-and-for-all
 2023-12-18 14:01:33 -05:00
Nikolas Klauser
f7407411a1
[libc++] Optimize std::find for segmented iterators (#67224) 
```
--------------------------------------------------------------------------
Benchmark                                              old             new
--------------------------------------------------------------------------
bm_find<std::deque<char>>/1                        6.06 ns         10.6 ns
bm_find<std::deque<char>>/2                        15.5 ns         10.6 ns
bm_find<std::deque<char>>/3                        19.0 ns         10.6 ns
bm_find<std::deque<char>>/4                        20.8 ns         10.6 ns
bm_find<std::deque<char>>/5                        22.0 ns         10.6 ns
bm_find<std::deque<char>>/6                        23.0 ns         10.5 ns
bm_find<std::deque<char>>/7                        24.8 ns         10.7 ns
bm_find<std::deque<char>>/8                        25.7 ns         10.6 ns
bm_find<std::deque<char>>/16                       28.3 ns         10.6 ns
bm_find<std::deque<char>>/64                       44.2 ns         27.0 ns
bm_find<std::deque<char>>/512                       133 ns         37.6 ns
bm_find<std::deque<char>>/4096                      867 ns         53.1 ns
bm_find<std::deque<char>>/32768                    6838 ns          160 ns
bm_find<std::deque<char>>/262144                  52897 ns         1495 ns
bm_find<std::deque<char>>/1048576                215621 ns         6077 ns
bm_find<std::deque<short>>/1                       6.03 ns         6.28 ns
bm_find<std::deque<short>>/2                       15.8 ns         15.8 ns
bm_find<std::deque<short>>/3                       20.5 ns         20.3 ns
bm_find<std::deque<short>>/4                       21.0 ns         21.0 ns
bm_find<std::deque<short>>/5                       23.0 ns         22.1 ns
bm_find<std::deque<short>>/6                       22.6 ns         23.0 ns
bm_find<std::deque<short>>/7                       23.4 ns         23.7 ns
bm_find<std::deque<short>>/8                       24.4 ns         24.9 ns
bm_find<std::deque<short>>/16                      26.6 ns         27.2 ns
bm_find<std::deque<short>>/64                      43.2 ns         40.9 ns
bm_find<std::deque<short>>/512                      124 ns         90.7 ns
bm_find<std::deque<short>>/4096                     845 ns          525 ns
bm_find<std::deque<short>>/32768                   7273 ns         3194 ns
bm_find<std::deque<short>>/262144                 53710 ns        24385 ns
bm_find<std::deque<short>>/1048576               216086 ns        96195 ns
bm_find<std::deque<int>>/1                         6.03 ns         10.3 ns
bm_find<std::deque<int>>/2                         15.6 ns         10.3 ns
bm_find<std::deque<int>>/3                         19.1 ns         10.3 ns
bm_find<std::deque<int>>/4                         22.3 ns         10.3 ns
bm_find<std::deque<int>>/5                         23.5 ns         10.4 ns
bm_find<std::deque<int>>/6                         23.1 ns         10.3 ns
bm_find<std::deque<int>>/7                         23.7 ns         10.2 ns
bm_find<std::deque<int>>/8                         24.5 ns         10.2 ns
bm_find<std::deque<int>>/16                        27.9 ns         26.6 ns
bm_find<std::deque<int>>/64                        42.6 ns         32.2 ns
bm_find<std::deque<int>>/512                        123 ns         43.0 ns
bm_find<std::deque<int>>/4096                       874 ns         93.5 ns
bm_find<std::deque<int>>/32768                     7031 ns          751 ns
bm_find<std::deque<int>>/262144                   57723 ns         6169 ns
bm_find<std::deque<int>>/1048576                 230867 ns        35851 ns
bm_ranges_find<std::deque<char>>/1                 5.97 ns         10.6 ns
bm_ranges_find<std::deque<char>>/2                 16.0 ns         10.5 ns
bm_ranges_find<std::deque<char>>/3                 19.5 ns         10.5 ns
bm_ranges_find<std::deque<char>>/4                 21.1 ns         10.6 ns
bm_ranges_find<std::deque<char>>/5                 22.8 ns         10.5 ns
bm_ranges_find<std::deque<char>>/6                 22.8 ns         10.6 ns
bm_ranges_find<std::deque<char>>/7                 23.4 ns         10.8 ns
bm_ranges_find<std::deque<char>>/8                 24.1 ns         10.5 ns
bm_ranges_find<std::deque<char>>/16                26.9 ns         10.6 ns
bm_ranges_find<std::deque<char>>/64                50.2 ns         27.2 ns
bm_ranges_find<std::deque<char>>/512                126 ns         38.3 ns
bm_ranges_find<std::deque<char>>/4096               868 ns         53.8 ns
bm_ranges_find<std::deque<char>>/32768             6695 ns          161 ns
bm_ranges_find<std::deque<char>>/262144           54411 ns         1497 ns
bm_ranges_find<std::deque<char>>/1048576         241699 ns         6042 ns
bm_ranges_find<std::deque<short>>/1                6.39 ns         6.31 ns
bm_ranges_find<std::deque<short>>/2                15.8 ns         15.9 ns
bm_ranges_find<std::deque<short>>/3                19.0 ns         19.8 ns
bm_ranges_find<std::deque<short>>/4                20.8 ns         20.9 ns
bm_ranges_find<std::deque<short>>/5                21.8 ns         22.1 ns
bm_ranges_find<std::deque<short>>/6                23.0 ns         23.0 ns
bm_ranges_find<std::deque<short>>/7                23.2 ns         23.9 ns
bm_ranges_find<std::deque<short>>/8                23.7 ns         24.4 ns
bm_ranges_find<std::deque<short>>/16               26.6 ns         26.8 ns
bm_ranges_find<std::deque<short>>/64               43.4 ns         39.7 ns
bm_ranges_find<std::deque<short>>/512               131 ns         90.5 ns
bm_ranges_find<std::deque<short>>/4096              851 ns          523 ns
bm_ranges_find<std::deque<short>>/32768            7370 ns         3166 ns
bm_ranges_find<std::deque<short>>/262144          60778 ns        24814 ns
bm_ranges_find<std::deque<short>>/1048576        229288 ns        99273 ns
bm_ranges_find<std::deque<int>>/1                  6.43 ns         10.2 ns
bm_ranges_find<std::deque<int>>/2                  16.6 ns         10.2 ns
bm_ranges_find<std::deque<int>>/3                  19.6 ns         10.2 ns
bm_ranges_find<std::deque<int>>/4                  21.0 ns         10.2 ns
bm_ranges_find<std::deque<int>>/5                  21.9 ns         10.4 ns
bm_ranges_find<std::deque<int>>/6                  22.7 ns         10.2 ns
bm_ranges_find<std::deque<int>>/7                  23.9 ns         10.2 ns
bm_ranges_find<std::deque<int>>/8                  23.8 ns         10.2 ns
bm_ranges_find<std::deque<int>>/16                 27.2 ns         27.1 ns
bm_ranges_find<std::deque<int>>/64                 42.4 ns         32.4 ns
bm_ranges_find<std::deque<int>>/512                 122 ns         43.0 ns
bm_ranges_find<std::deque<int>>/4096                895 ns         93.7 ns
bm_ranges_find<std::deque<int>>/32768              6890 ns          756 ns
bm_ranges_find<std::deque<int>>/262144            54025 ns         6102 ns
bm_ranges_find<std::deque<int>>/1048576          221558 ns        32783 ns
```
 2023-12-15 17:10:16 +01:00
Stephan T. Lavavej
bfdc562d0c
[libc++] Fix copy-paste damage in ranges::rotate_copy and its test (#74544) 
Found while running libc++'s tests with MSVC's STL.

`ranges::rotate_copy` takes `forward_iterator`s as this test's comment
banner correctly depicts. However, this test had bogus assertions
expecting that `ranges::rotate_copy` would be constrained away for
not-quite-**bidi** iterators. @philnik777 confirmed that these were
copy-paste relics from the `ranges::reverse_copy` test.

I fixed this by replacing the assertions with the test types that aren't
quite **forward** iterators/ranges. Additionally, I noticed that the
top-level `test()` function was missing coverage with the weakest
possible `forward_iterator<int*>`.

This revealed that the product code in `ranges_rotate_copy.h` was
similarly damaged. In addition to fixing it by taking `forward_iterator`
and `forward_range` as depicted in the Standard, this drops the
inclusion of `<__iterator/reverse_iterator.h>` as this algorithm doesn't
need `std::__reverse_range`.
 2023-12-06 02:29:09 -08:00
Louis Dionne
77a00c0d54
[libc++] Replace uses of _VSTD:: by std:: (#74331) 
As part of the upcoming clang-formatting of libc++, this patch performs
the long desired removal of the _VSTD macro.

See https://discourse.llvm.org/t/rfc-clang-formatting-all-of-libc-once-and-for-all
for the clang-format proposal.
 2023-12-05 11:19:15 -05:00
Louis Dionne
4c19854222
[libc++] Rename _LIBCPP_INLINE_VISIBILITY to _LIBCPP_HIDE_FROM_ABI (#74095) 
In preparation for running clang-format on the whole code base, we are
also removing mentions of the legacy _LIBCPP_INLINE_VISIBILITY macro in
favor of the newer _LIBCPP_HIDE_FROM_ABI.

We're still leaving the definition of _LIBCPP_INLINE_VISIBILITY to avoid
creating needless breakage in case some older patches are checked-in
with mentions of the old macro. After we branch for LLVM 18, we can do
another pass to clean up remaining uses of the macro that might have
gotten introduced by mistake (if any) and remove the macro itself at the
same time. This is just a minor convenience to smooth out the transition
as much as possible.

See
https://discourse.llvm.org/t/rfc-clang-formatting-all-of-libc-once-and-for-all
for the clang-format proposal.
 2023-12-04 10:25:14 -05:00
Nikolas Klauser
ed27a4edb0
[libc++][PSTL] Implement std::equal (#72448) 
Differential Revision: https://reviews.llvm.org/D157131

Co-authored-by: Louis Dionne <ldionne.2@gmail.com>
 2023-11-28 16:02:18 -05:00
Louis Dionne
936180a5e8 [libc++][NFC] Fix typo in comment 2023-11-27 10:35:07 -05:00
philnik777
1314e8774f
[libc++] Add missing headers to the modulemap (#71127) 
I don't know when, but at some point we lost test coverage to ensue that
all the headers are in the modulemap. This adds a test to make sure all
the headers (excluding a few which shouldn't be part of the modulemap)
are at least mentioned. This also fixes a few headers which bit-rotted
while we were missing the coverage.
 2023-11-27 00:14:59 +01:00
Anton Rydahl
aea7929b0a
[libc++] Unify __is_trivial_equality_predicate and __is_trivial_plus_operation into __desugars_to (#68642) 
When working on an OpenMP offloading backend for standard parallel
algorithms (https://github.com/llvm/llvm-project/pull/66968) we noticed
the need of a generalization of `__is_trivial_plus_operation`. This patch
merges `__is_trivial_equality_predicate` and `__is_trivial_plus_operation`
into `__desugars_to`, and in the future we might extend the latter to support
other binary operations as well.

Co-authored-by: Louis Dionne <ldionne.2@gmail.com>
 2023-11-23 13:55:55 -05:00
Nikolas Klauser
c81bfc61da [libc++] Optimize for_each for segmented iterators 
```
---------------------------------------------------
Benchmark                       old             new
---------------------------------------------------
bm_for_each/1               3.00 ns         2.98 ns
bm_for_each/2               4.53 ns         4.57 ns
bm_for_each/3               5.82 ns         5.82 ns
bm_for_each/4               6.94 ns         6.91 ns
bm_for_each/5               7.55 ns         7.75 ns
bm_for_each/6               7.06 ns         7.45 ns
bm_for_each/7               6.69 ns         7.14 ns
bm_for_each/8               6.86 ns         4.06 ns
bm_for_each/16              11.5 ns         5.73 ns
bm_for_each/64              43.7 ns         4.06 ns
bm_for_each/512              356 ns         7.98 ns
bm_for_each/4096            2787 ns         53.6 ns
bm_for_each/32768          20836 ns          438 ns
bm_for_each/262144        195362 ns         4945 ns
bm_for_each/1048576       685482 ns        19822 ns
```

Reviewed By: ldionne, Mordante, #libc

Spies: bgraur, sberg, arichardson, libcxx-commits

Differential Revision: https://reviews.llvm.org/D151274
 2023-11-14 23:55:24 +01:00
Louis Dionne
acb9156266 [libc++][NFC] Fix license comment typo 
Fixes #72024
 2023-11-11 08:24:19 -10:00
Konstantin Varlamov
64d413efdd
[libc++][hardening] Rework macros for enabling the hardening mode. (#70575) 
1. Instead of using individual "boolean" macros, have an "enum" macro
`_LIBCPP_HARDENING_MODE`. This avoids issues with macros being
mutually exclusive and makes overriding the hardening mode within a TU
more straightforward.

2. Rename the safe mode to debug-lite.

This brings the code in line with the RFC:
https://discourse.llvm.org/t/rfc-hardening-in-libc/73925

Fixes #65101
 2023-11-08 09:10:00 -10:00
Louis Dionne
02540b2f6d
[libc++] Make sure ranges algorithms and views handle boolean-testable correctly (#69378) 
Before this patch, we would fail to implicitly convert the result of
predicates to bool, which means we'd potentially perform a copy or move
construction of the boolean-testable, which isn't allowed. The same
holds true for comparing iterators against sentinels, which is allowed
to return a boolean-testable type.

We already had tests aiming to ensure correct handling of these types,
but they failed to provide appropriate coverage in several cases due to
guaranteed RVO. This patch fixes the tests, adds tests for missing
algorithms and views, and fixes the actual problems in the code.

Fixes #69074
 2023-11-06 21:19:49 -10:00
Louis Dionne
979c19ab12
[libc++] Fix complexity guarantee in ranges::clamp (#68413) 
This patch prevents us from calling the projection more than 3 times in
std::clamp, as required by the Standard.

Fixes #64717
 2023-11-01 10:43:05 -04:00
Rajveer Singh Bharadwaj
dd4891318c
[libc++] Fix _CopySegment helper in ranges::copy(join_view, out) when called in a static assertion context (#69593) 
Resolves Issue #69083

The `_CopySegment` helper for `ranges::copy(join_view, out)` is not
`constexpr` causing rejection in `libc++` in a static assertion context
as in the issue snippet.
 2023-10-27 11:07:12 +02:00
Nikolas Klauser
5d7f346bd3 [libc++][PSTL] Implement std::rotate_copy 
Reviewed By: #libc, ldionne

Spies: ldionne, libcxx-commits

Differential Revision: https://reviews.llvm.org/D155025
 2023-10-24 14:02:37 +02:00
Nikolas Klauser
d2a46e6480 [libc++][PSTL] Implement std::move 
Reviewed By: #libc, ldionne

Spies: ldionne, libcxx-commits

Differential Revision: https://reviews.llvm.org/D155330
 2023-10-22 10:25:49 +02:00
Daniel Kutenin
ea9af5e7fd
[libc++] Add assertions for potential OOB reads in std::nth_element (#67023) 
Same as https://reviews.llvm.org/D147089 but for std::nth_element
 2023-10-18 20:22:17 -07:00
Louis Dionne
70fedaf89b [libc++][NFC] Fix slightly incorrect comment in PSTL documentation 2023-10-13 17:27:44 -07:00
Anton Rydahl
f2b79ed9c6
[libcxx] Refactoring SIMD function names in PSTL CPU backend (#69029) 
This PR addresses a smaller detail discussed in the code review for
https://github.com/llvm/llvm-project/pull/66968. Currently, some
functions in the `libc++` PSTL CPU backend have been appended with a
digit to indicate the number of input iterator arguments. However, there
is no need to change the name for each version as overloading can be
used instead. This PR will make the naming more consistent in the the
CPU and the proposed OpenMP backend.
 2023-10-13 17:08:15 -07:00
Nikolas Klauser
aade74675c [libc++][PSTL] Overhaul exceptions handling 
This makes exception handling a lot simpler, since we don't have to convert any exceptions this way. Is also properly handles all the user-thrown exceptions.

Reviewed By: ldionne, #libc

Spies: arichardson, mstorsjo, libcxx-commits

Differential Revision: https://reviews.llvm.org/D154238
 2023-10-06 23:01:30 +02:00
Nikolas Klauser
a9138cdb36 [libc++] Optimize ranges::count for __bit_iterators 
```
---------------------------------------------------------------
Benchmark                                    old            new
---------------------------------------------------------------
bm_vector_bool_count/1                   1.92 ns        1.92 ns
bm_vector_bool_count/2                   1.92 ns        1.92 ns
bm_vector_bool_count/3                   1.92 ns        1.92 ns
bm_vector_bool_count/4                   1.92 ns        1.92 ns
bm_vector_bool_count/5                   1.92 ns        1.92 ns
bm_vector_bool_count/6                   1.92 ns        1.92 ns
bm_vector_bool_count/7                   1.92 ns        1.92 ns
bm_vector_bool_count/8                   1.92 ns        1.92 ns
bm_vector_bool_count/16                  1.92 ns        1.92 ns
bm_vector_bool_count/64                  2.24 ns        2.25 ns
bm_vector_bool_count/512                 3.19 ns        3.20 ns
bm_vector_bool_count/4096                14.1 ns        12.3 ns
bm_vector_bool_count/32768               84.0 ns        83.6 ns
bm_vector_bool_count/262144               664 ns         661 ns
bm_vector_bool_count/1048576             2623 ns        2628 ns
bm_vector_bool_ranges_count/1            1.07 ns        1.92 ns
bm_vector_bool_ranges_count/2            1.65 ns        1.92 ns
bm_vector_bool_ranges_count/3            2.27 ns        1.92 ns
bm_vector_bool_ranges_count/4            2.68 ns        1.92 ns
bm_vector_bool_ranges_count/5            3.33 ns        1.92 ns
bm_vector_bool_ranges_count/6            3.99 ns        1.92 ns
bm_vector_bool_ranges_count/7            4.67 ns        1.92 ns
bm_vector_bool_ranges_count/8            5.19 ns        1.92 ns
bm_vector_bool_ranges_count/16           11.1 ns        1.92 ns
bm_vector_bool_ranges_count/64           52.2 ns        2.24 ns
bm_vector_bool_ranges_count/512           452 ns        3.20 ns
bm_vector_bool_ranges_count/4096         3577 ns        12.1 ns
bm_vector_bool_ranges_count/32768       28725 ns        83.7 ns
bm_vector_bool_ranges_count/262144     229676 ns         662 ns
bm_vector_bool_ranges_count/1048576    905574 ns        2625 ns
```

Reviewed By: #libc, ldionne

Spies: arichardson, ldionne, libcxx-commits

Differential Revision: https://reviews.llvm.org/D156956
 2023-10-06 22:58:41 +02:00
Louis Dionne
04b45450ac
[libc++] Explicitly pass execution policies to _LIBCPP_PSTL_CUSTOMIZATION_POINT (#68238) 
The _LIBCPP_PSTL_CUSTOMIZATION_POINT macro was assuming that the policy
was called _RawPolicy and referencing it by name. It happened to always
work but this was definitely accidental and an oversight in the original
implementation. This patch fixes that by passing the policy to the macro
explicitly. Noticed while reviewing #66968.
 2023-10-04 18:12:39 -04:00
Louis Dionne
d32edcb86d [libc++][NFC] Fix broken formatting in comment 2023-10-04 16:38:30 -04:00
Louis Dionne
7a73a2c241 [libc++][NFC] Document missing __pstl_merge function in PSTL basis operations 2023-10-04 13:39:34 -04:00
Amirreza Ashouri
b6f6fe98a8
[libc++] Remove unused defaulted template arg from __rewrap_range. (#67733) 
Template argument `_Unwrapped` is always deduced from the type of
`_Unwrapped __iter`.
 2023-10-04 11:23:36 +02:00
Zijun Zhao
0218ea4aaa [libc++] Implement ranges::ends_with 
Reviewed By: #libc, var-const

Differential Revision: https://reviews.llvm.org/D150831
 2023-09-18 11:56:10 -07:00
Jakub Mazurkiewicz
065dc485bd [libc++][ranges] Implement P2443R1: views::chunk_by 
This patch implements https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p2443r1.html (`views::chunk_by`).

Reviewed By: #libc, var-const

Differential Revision: https://reviews.llvm.org/D144767
 2023-09-05 16:19:49 -07:00
Nikolas Klauser
9f3e3efd98 [libc++][NFC] Refactor __enable_if return types to defaulted template parameters 
This brings most of the enable_ifs in libc++ to the same style. It also has the nice side-effect of reducing the size of names of these symbols, since the depedent return type is shorter.

Reviewed By: #libc, ldionne

Spies: ldionne, libcxx-commits

Differential Revision: https://reviews.llvm.org/D157787
 2023-09-01 17:52:31 -07:00
Nikolas Klauser
b6310e65f6 [libc++] Add lifetimebound attributes to clamp 
Reviewed By: #libc, ldionne

Spies: ldionne, arichardson, libcxx-commits

Differential Revision: https://reviews.llvm.org/D158327
 2023-09-01 09:04:11 -07:00
Konstantin Varlamov
ec4005ff87 [libc++][hardening] Mark the remaining stray assertions as uncategorized 
This avoids enabling them unconditionally in all hardening modes.

Reviewed By: #libc, Mordante

Differential Revision: https://reviews.llvm.org/D158970
 2023-08-29 16:32:23 -07:00
Nikolas Klauser
68b1035965 [libc++][PSTL] Add a __parallel_sort implementation to libdispatch 
Reviewed By: #libc, ldionne

Spies: ldionne, libcxx-commits

Differential Revision: https://reviews.llvm.org/D155136
 2023-08-15 12:20:40 -07:00
Nikolas Klauser
475bd19ee8 [libc++][NFC] Refactor return type enable_ifs to defaulted template arguments 
This brings most of the enable_ifs in libc++ to the same style. It also has the nice side-effect of reducing the size of names of these symbols, since the depedent return type is shorter.

Reviewed By: #libc, ldionne

Spies: ldionne, libcxx-commits

Differential Revision: https://reviews.llvm.org/D157736
 2023-08-15 12:19:21 -07:00
Nikolas Klauser
051c863012 [libc++][PSTL] Simplify the partitioning algorithm until we have better data to know how to chunk better 
The current chunking strategy is very bad for sorting, and we don't really know how to chunk in general. This fixes the performance problem for sorting.

Reviewed By: ldionne, #libc

Spies: libcxx-commits, krytarowski

Differential Revision: https://reviews.llvm.org/D155531
 2023-08-14 16:44:30 -07:00
Gonzalo Brito Gadeschi
0e2de665f3 [libc++][PSTL] Parallelize random_access_iterator 
P2408 requires this for C++23, but implementing it in C++20 is safe
because the only code impacted would be code that violated a
precondition of the parallel algorithm. It was P2408 intent to
enable implementations to backport this to C++20.

Closes #63447 .

Reviewed By: philnik, #libc

Differential Revision: https://reviews.llvm.org/D154305
 2023-08-07 17:58:27 +02:00
Mark de Wever
f0e9cd2b1c [libc++][PSTL] Adds a missing include. 
This should fix an error in the Apple CI.
 2023-08-02 18:10:58 +02:00
Nikolas Klauser
8670b53e11 [libc++] Optimize ranges::find for vector<bool> 
Benchmark results:
```
----------------------------------------------------------------
Benchmark                                    old             new
----------------------------------------------------------------
bm_vector_bool_ranges_find/1             5.64 ns         6.08 ns
bm_vector_bool_ranges_find/2             16.5 ns         6.03 ns
bm_vector_bool_ranges_find/3             20.3 ns         6.07 ns
bm_vector_bool_ranges_find/4             22.2 ns         6.08 ns
bm_vector_bool_ranges_find/5             23.5 ns         6.05 ns
bm_vector_bool_ranges_find/6             24.4 ns         6.10 ns
bm_vector_bool_ranges_find/7             26.7 ns         6.10 ns
bm_vector_bool_ranges_find/8             25.0 ns         6.08 ns
bm_vector_bool_ranges_find/16            27.9 ns         6.07 ns
bm_vector_bool_ranges_find/64            44.5 ns         5.35 ns
bm_vector_bool_ranges_find/512            243 ns         25.7 ns
bm_vector_bool_ranges_find/4096          1858 ns         35.6 ns
bm_vector_bool_ranges_find/32768        15461 ns         93.5 ns
bm_vector_bool_ranges_find/262144      126462 ns          571 ns
bm_vector_bool_ranges_find/1048576     497736 ns         2272 ns
```

Reviewed By: #libc, Mordante

Spies: var-const, Mordante, libcxx-commits

Differential Revision: https://reviews.llvm.org/D156039
 2023-08-01 10:28:25 -07:00
Nikolas Klauser
9391330293 [libc++][PSTL] Fix std::copy frontend dispatching 
Reviewed By: #libc, Mordante

Spies: Mordante, libcxx-commits

Differential Revision: https://reviews.llvm.org/D155325
 2023-07-31 18:39:02 -07:00
Ian Anderson
165841b681 [libc++][Modules] Fix a few module related warnings 
I'm getting a few -Wundefined-inline warnings, and a -Wnon-modular-include-in-module too. Fix all of those.

Reviewed By: Mordante, #libc

Differential Revision: https://reviews.llvm.org/D156508
 2023-07-29 07:33:35 -07:00
Nikolas Klauser
37e5baf318 [libc++][PSTL] Implement std::sort 
Reviewed By: #libc, ldionne

Spies: ldionne, libcxx-commits, mgrang

Differential Revision: https://reviews.llvm.org/D152860
 2023-07-20 14:45:36 -07:00
Louis Dionne
503f2ee4a8 [libc++] Make sure we use the libdispatch backend on Apple platforms 
The Apple.cmake cache wasn't set up properly, so we wouldn't enable
the libdispatch backend by default on Apple platforms. This patch
fixes the issue and adds a test.

We also need to make various drive-by fixes:
- Drop the usage of std::vector in libdispatch.h to avoid changing
  the transitive includes only on Apple platforms.
- Fix includes
- Use __construct at since construct_at is unavailable in C++17
- Get rid of the (unused) __get_memory_resource function since that
  adds a back-deployment requirement and we don't use it right now.
- Fix bugs in the chunking logic around boundary conditions.

Differential Revision: https://reviews.llvm.org/D155649
 2023-07-20 15:53:27 -04:00
Nikolas Klauser
2b2e7f6e57 [libc++][PSTL] Add a GCD backend 
Reviewed By: ldionne, #libc

Spies: arichardson, mgrang, krytarowski, libcxx-commits, h-vetinari

Differential Revision: https://reviews.llvm.org/D151717
 2023-07-12 13:27:33 -07:00