[ADT] Make llvm::is_contained call member `contains` or `find` when available
authorJakub Kuderski <kubak@google.com>
Wed, 15 Mar 2023 15:56:34 +0000 (11:56 -0400)
committerJakub Kuderski <kubak@google.com>
Wed, 15 Mar 2023 16:07:56 +0000 (12:07 -0400)
commit0eaacc25bb98f50cc98bab5f6ef8d6d67e112317
tree32ba3e5a4b9646dd41ae23ad35aed0651804e163
parentd8df8710e127f8f8ff0714afdecba450ce591d9d
[ADT] Make llvm::is_contained call member `contains` or `find` when available

This makes it so that calling `llvm::is_contained` no longer degrades
performance over member contains, even though both have almost identical
names. This would be the case in most set/map classes that can check for
an element being present in O(1) or O(log n) time vs. linear scan with
`std::find`. For C++17 maps/sets without `.contains`, use `.find` when available,
falling back to a linear scan with `std::find`.

I also considered detecting member contains and triggering a
`static_assert` instead, but decided against it because it's just as easy
to do the right thing and call `.contains`. This would also make some code fail
only when compiled in the C++20 mode when more container types come with
`.contains` member functions.

This was actually already the case with `CommandLine.h` calling `is_contained`
on `SmallPtrSet` and in a recent BOLT patch.

Reviewed By: kazu, dblaikie, MaskRay

Differential Revision: https://reviews.llvm.org/D146061
llvm/include/llvm/ADT/STLExtras.h
llvm/include/llvm/Analysis/LoopInfoImpl.h
llvm/unittests/ADT/STLExtrasTest.cpp