[llvm-dev] [RFC] Adding a -memeq-lib-function flag to allow the user to specify a memeq function.

[Finkel, Hal J. via llvm-dev]

On 1/3/19 3:29 AM, Clement Courbet via llvm-dev wrote:
Hi all,

We'd like to suggest adding a -memeq-lib-function flag to allow the user to specify a `memeq()` function to improve string equality check performance.

Hi, Clement,

We really shouldn't be adding backend flags for anything at this point (except for debugging and the like). A function attribute should be fine, or global metadata if necessary. A function attribute should play better with LTO, and so that's generally the recommended design point.


Right now, when llvm encounters a string equality check, e.g. `if (memcmp(a, b, s) == 0)`, it tries  to expand to an equality comparison if `s` is a small compile-time constant, and falls back on calling `memcmp()` else.

This is sub-optimal because memcmp has to compute much more than equality.

We propose adding a way for the user to specify a `memeq` library function (e.g. `-memeq-lib-function=user_memeq`) which will be called instead of `memcmp()` when the result of the memcmp call is only used for equality comparison.

`memeq` can be made much more efficient than `memcmp` because equality comparison is trivially parallel while lexicographic ordering has a chain dependency.

We measured an very large improvement of this approach on our internal codebase. A significant portion of this improvement comes from the stl, typically `std::string::operator==()`.

Note that this is a backend-only change. Because the c family of languages do not have a standard `memeq()` (posix used to have `bcmp()` but it was removed in 2001), c/c++ code cannot communicate the equality comparison semantics to the compiler.

We did not add an RTLIB entry for memeq because the user environment is not guaranteed to contain a `memeq()` function as the libc has no such concept.

If there is interest, we could also contribute our optimized `memeq` to compiler-rt.


That would be useful.

Thanks again,

Hal


A proof of concept patch for this for this RFC can be found here: https://reviews.llvm.org/D56248

Comments & suggestions welcome !
Thanks,

Clement



_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190103/7084a03f/attachment-0001.html>