Page MenuHomePhabricator

[libc++] Simplify debug iterators, and fix a couple of non-explicit constructors.
Needs RevisionPublic

Authored by Quuxplusone on Apr 18 2021, 12:17 PM.

Details

Reviewers
ldionne
krisb
Mordante
curdeius
EricWF
Group Reviewers
Restricted Project
Summary

This is actually three related commits in one:

commit 11d578daf3e499100b8126e9c8f574f58ebe6f2c (HEAD -> list-debug-mode)
Author: Arthur O'Dwyer <arthur.j.odwyer@gmail.com>
Date:   Sun Apr 18 15:15:10 2021 -0400

    [libc++] __bit_iterator's constructor needs explicit.

commit 34df8a2d303a40ef1e498f9f86d3dd1d7610d3c0
Author: Arthur O'Dwyer <arthur.j.odwyer@gmail.com>
Date:   Sun Apr 18 14:10:16 2021 -0400

    [libc++] __wrap_iter's constructor needs explicit; make it look like __list_iterator.

    The "regression test" is https://godbolt.org/z/7jv71vnjc , but in fact that test
    seems to be relying on a nonconformance in Clang's overload resolution algorithm:
    on Clang and ICC, `foo({0,0})` will prefer the public non-explicit constructor of
    `pair<int,int>` over the explicit constructor of `vector<int>::iterator`, but
    I think that's actually nonconforming.

commit 1adf6ac48d2e255ff59e1851fb2f33861464b107
Author: Arthur O'Dwyer <arthur.j.odwyer@gmail.com>
Date:   Sun Apr 18 14:02:12 2021 -0400

    [libc++] Give list::iterator the same constructor in debug and non-debug modes.
    
    Inlining will take care of the codegen; get rid of a lot of #ifs.

Diff Detail

Event Timeline

Quuxplusone requested review of this revision.Apr 18 2021, 12:17 PM
Quuxplusone created this revision.
Herald added a reviewer: Restricted Project. · View Herald TranscriptApr 18 2021, 12:17 PM
Quuxplusone added inline comments.
libcxx/include/span
346–350

@mclow.lists added the debug iterators for span. Personally I'm not convinced that span really ought to count as a "container" in the debug-iterator sense, and maybe it ought to just use plain old raw pointers as its iterators; but for the purposes of this patch, I left it as-is.

I was too lazy to add a test (especially given the previous paragraph), but this PR does incidentally fix span in debug mode. Example of current brokenness: https://godbolt.org/z/hP6sa68sM

Turns out that my regression test "proving" that {0,0} is not a vector::iterator actually may indicate a non-conformance in Clang's overload resolution rules — GCC and MSVC disagree with Clang. So I plan to just remove those two new tests (but not revert the addition of explicit to those constructors, since that's obviously a good idea).
Example of disagreement between GCC and Clang: https://godbolt.org/z/cedPxnzz1

Quuxplusone edited the summary of this revision. (Show Details)
Quuxplusone added reviewers: Mordante, curdeius.

Remove the regression tests for the explicit constructors of __wrap_iter and __bit_iterator, because they failed on GCC, which alerted me to the possibility that they're probably relying on nonconforming behavior of the Clang compiler, and therefore they might break in the future as Clang becomes more conforming.

EricWF requested changes to this revision.Apr 19 2021, 9:01 AM
EricWF added a subscriber: EricWF.

I would need to see analysis of the cost of always passing an additional parameter to these iterators constructors before I approve this.

libcxx/include/list
297

We're now always passing another parameter to the constructor, eating a register.
We don't want to pay that cost in non-debug mode.

There was a reason this code was written in this ugly manner.

This revision now requires changes to proceed.Apr 19 2021, 9:01 AM
Quuxplusone added inline comments.Apr 19 2021, 9:41 AM
libcxx/include/list
297

@EricWF: What compiler/target are you concerned about? I'm sure Clang/LLVM on x86 is smart enough to inline these inline functions — I can work on getting evidence for that — but I'm guessing you had something more obscure in mind?

Quuxplusone added inline comments.Apr 24 2021, 7:36 AM
libcxx/include/list
297

@EricWF:
Hm, I see, in non-debug mode, clang++ -O1 isn't quite smart enough to avoid eating that register. (At -O2 and up, it is smart enough, and produces identical codegen.)
OTOH, std::vector::__make_iter has existed since 2011-or-earlier, and produces the exact same symptom: it eats one more register (at -O1 or lower, in non-debug mode) than it really needs to. I verified this by adding an ifdef that "manually inlines" all the calls to __make_iter(__p), and observing the difference in codegen.

Another idea I had was to add a std::list::__make_iter method analogous to vector's, but then make it static when not in debug mode:

#if _LIBCPP_DEBUG_LEVEL == 2
    iterator __make_iter(pointer __p) { return iterator(__p, this); }
#else
    static iterator __make_iter(pointer __p) { return iterator(__p); }
#endif

However, obviously this would give worse codegen at -O0 than we have today, because it's introducing a layer of indirection. And it still isn't quite as good at -O1 as "manually inlining" __make_iter. (I tried out a static version of vector::__make_iter and could still see some tiny diffs relative to the "manually inlined" version.)

In short: You're right, this hurts register allocation at -O1.

However, I continue to think that people who care about optimization should really be using -O2, and that we should make this PR's change to simplify the code of <list> and bring its debug iterators into line with <vector> and <string>.

Here's a playground where you can (for the next few weeks at least — until I update my P1144 branch) play around with the various possibilities I've implemented via ifdefs: https://godbolt.org/z/jWhfPGjcf

Quuxplusone added inline comments.May 18 2021, 6:42 AM
libcxx/include/list
297

@EricWF ping for your thoughts? My playground is still up.