In D152152#4399937, @aartbik wrote:

In practice if there are more than 30 elements, it could and can (for example, by being a pivot and waiting for the false condition): https://stackoverflow.com/questions/38966516/should-sorting-algorithm-pass-same-element-in-the-comparison-function

I understand the general requirement for sort, but this sort is only used in particular situations by the sparse compiler. So my question is, do you have a test case that would trigger the assert at L35.
If so, we would like to understand the example code before removing the assert.

In D152152#4397561, @aartbik wrote:

In D152152#4397277, @danlark wrote:

In D152152#4397162, @Peiming wrote:

Is there any change to the std::sort that requires such a change? In these two particular cases, there should not be any duplicated item from the array (otherwise, it leads to logical bugs).

std::sort is allowed to call comparator on the same element.

But do you have a example that trigger this? The sparse compiler has a non-dup property, and we would like to see the example that leads to this?

In D152152#4397162, @Peiming wrote:

Is there any change to the std::sort that requires such a change? In these two particular cases, there should not be any duplicated item from the array (otherwise, it leads to logical bugs).

In D150264#4392972, @Mordante wrote:

In D150264#4380575, @danlark wrote:

I don't have commit rights, can you help me submit the change?

Danila Kutenin
kutdanila@yandex.ru

I tried to land this patch on your behalf, but there are some merge conflicts. Can you rebase the patch on main?

Rebase to head

Ping

I don't have commit rights, can you help me submit the change?

Ping

Ping

Fix comments

Remove arg policy

Address comments

Follow the standard library lint

Merge all changes I had about includes and tests

Fix incorrect tests and ADL lookups

Fix includes

Thanks for a thorough response and productive discussion. LGTM

Shuffling the range wouldn't help here -- the problem wasn't non-determinism in the output, it's that we literally go and read out-of-bounds when the comparator is wrong. I think this is happening in __insertion_sort_unguarded, and I think I can add an assertion check just in there to "fix" the issue but I haven't had time to get the reproducer integrated in our test suite yet.

Also to catch all strict weak ordering bugs, there are O(n^2) algorithms, for example, here. We can introduce a debug check with a square root of elements sampling. Would you be up to do this? Given how long range randomization took, I decided not to go into that direction as it seemed even harder to introduce safely. I can prioritize this work if there will be enough support from the maintainers

To catch most issues, we introduced __debug_randomize_range which is present on line 973 on the left. That can be advised to run tests. We found most out of bound bugs at Google with randomization of the input

Hi @fhahn, this is the first commit that caused a miscompilation we observed.

In D122941#3425151, @ldionne wrote:

In D122941#3425149, @danlark wrote:

@danlark
This patch will break users of the randomized unspecified behavior you added since you are most likely not shipping a debug-mode version of the library today. Has it been in used internally at Google?

Thanks for adding me.

I confirm we haven't shipped anything with randomization to the (external) users and this patch should be fine with us as we build everything from source

Just to make sure we're on the same page, here's what this change entails if you've been using randomization (even just internally): Out-of-the-box, you'll get a compiler error saying that you're using unspecified behavior randomization with a library that has been built without the debug mode. You'll need to switch to building the library with the debug mode enabled, i.e. LIBCXX_ENABLE_DEBUG_MODE=ON when configuring in CMake. However, that will also cause all the other debug mode checks to be enabled, which you may or may not want. And there will certainly be a slowdown associated to this, too. Is that fine, or do we need to make it possible to use unspecified behavior randomization without using the rest of the debug mode from the get-go? If that's a requirement for you, I'll try to think about ways to make that possible in this version of the patch and keep you up-to-date. If not, that makes my life easier since I can land this and then relax requirements once we've agreed on a design document (aiming to make it happen this week).

In D122941#3425128, @ldionne wrote:

In D122941#3425095, @philnik wrote:

Another thought: Should we change the ABI namespace to force link time errors if someone tries to link against the wrong library? - This should probably be done in the same patch where we enable some ABI flags.

We are very much on the same page, it seems :-). Quoting from my in-progress design document:

• The sanitized version of the library would have a different name, for example libc++-sanitized.dylib. A different __config_site file would also be provided to be used when compiling code against the sanitized library. Vendors could ship both the sanitized and the non-sanitized library side-by-side.
• The sanitized version of the library would use a different inline namespace to make sure that code can’t accidentally link against the wrong version of the library (which would result in runtime errors due to ABI incompatibilities).
• When -fsanitize=library is passed to the compiler, the compiler would automatically switch to using the sanitized version of the library. It would use the sanitized shared library as well as the sanitized version of the __config_site header, so that code in the headers would be built with sanitization enabled too.

I will also treat the topic of ABI compatibility between sanitized and non-sanitized versions, and also ABI stability between sanitized versions. Stay tuned, I should post it to Discourse in a couple of days.

@danlark
This patch will break users of the randomized unspecified behavior you added since you are most likely not shipping a debug-mode version of the library today. Has it been in used internally at Google?

Fix CI and linter

Remove the ifdef for __libcpp_debug_randomizer

I hope this is the last update

Improve the library build support

Improve one comment

All comments are done

@ldionne call of last hope, if I should continue the effort :)

Hi, is this still going and are you interested? I see https://reviews.llvm.org/D93233 and this infrastructure will help all users to migrate and avoid Hyrum's Law dependencies if they see problems

Thanks, LGTM!

In D102550#2761483, @lebedev.ri wrote:

I basically agree with @nikic here.
There is a huge number of low-hanging fruit like this,
but the approach just doesn't seem viable to me.

I would instead like to see the Attributor finally enabled,
there such things would be much more straight-forward.

Sorry for a very not helpful feedback.

In D102550#2761412, @nikic wrote:

I'm somewhat concerned about the general direction here. This looks through a GEP, but what about bitcasts? What about a bitcast of a GEP? A GEP of a bitcast? A longer chain of GEPs and bitcasts? We can't reasonably walk the whole use graph and this is really pushing the bounds of what it appropriate for a ValueTracking helper.

We have a more principled version of this optimization in LVI, which scans whole blocks for pointer dereferences and records their underlying objects, thus handling this in full generality. The only caveat is that LVI only uses this information to optimize the terminator instruction, because it does not store where exactly inside the block the first dereference occurs. If the motivation here is handling of non-terminator comparisons, then that might be a better avenue to explore?

Fix compilation issues

Remove unnecessary checks

Fix clang-tidy warning

Don't compute isKnownNonZero for operand

Add gep after check test to test DominatorTree

Failure looks unrelated, please submit as I don't have commit rights

• Address comment from Richard

In D102502#2759900, @rsmith wrote:

Thanks, nice catch!

Can we also add an assert when parsing a for statement that we actually find a range if the tentative parse said we were expecting one?

• Add assert of finding a for range declaration

• Add codegen and AST tests

Done, please, take a look

• Add codegen and AST tests

• Add codegen test

In D102502#2759776, @lebedev.ri wrote:

This should have codegen, and maybe AST, tests.

Sorry for not pinging for so long

Thanks!

In D96946#2571506, @ldionne wrote:

First of all, thanks for writing a design document and explaining the purpose of your patch. Let me try to understand the use case a bit better.

So basically, let's say you're trying to adopt a new implementation of std::sort internally. You change that, but then you realize that a bunch of tests break because they were relying on the exact order of equal elements after std::sort, which is really unspecified. But since those tests are failing, you can't use the new std::sort implementation until all the tests have been fixed. So, in order to make that transition easier and allow fixing tests one by one, you add this feature. You then turn it on locally for some projects/tests inside your organization, and you fix them one by one. Once you're done, you can switch the algorithm implementation, and turn off the randomization. Is that the idea?

Address comments

Fix unused parameters

Correctness

I need to double check the cold cache performance, it may happen that it is slower in that case

Provide better names than in paper

In D83547#2143840, @courbet wrote:

I have no idea what the policy is WRT size for compiler-rt. How big is the diff if you take code size into consideration ?

Fix clang format

Fix comments

Please, take a look

Update the real reference

879f4962e83f98863c83e385e956d579e131791f

Fix comments