This is an archive of the discontinued LLVM Phabricator instance.

[builtins] run-time support for sparse maps in llvm
AbandonedPublic

Authored by shawnl on Apr 25 2019, 8:17 AM.

Details

Summary

I am trying to move towards much more space-efficient switch statements, using popcnt, as described in PR39013. This is the run-time component. See D60673 and D60982 Code that uses this is not ready for review, and is here: https://github.com/shawnl/llvm/tree/test

I am hoping on getting some feed-back on this implementation. compiler-rt is written to be very portable, and my patch depends on popcountll, a GNU extension, as well as eSymbolTypeResolver (IFUNC when using ELF). Also, I had planned to implement a dosparsejmp() that would directly jump after a tail call, instead of possibly just using __getsparse32/64 here, and that would require special code for every supported architecture. (but it will probably be necessary with non-integer pointer arches like Mill become part of LLVM)

This is a space-saving improvement, so putting these routines here make sense.

There are three versions, in 4 sizes (8 16 32 and 64 bits). The three versions are:

Diff Detail

Event Timeline

shawnl created this revision.Apr 25 2019, 8:17 AM
Herald added projects: Restricted Project, Restricted Project. · View Herald TranscriptApr 25 2019, 8:17 AM
Herald added subscribers: Restricted Project, llvm-commits, mgorny. · View Herald Transcript
jmolloy resigned from this revision.Apr 25 2019, 8:40 AM

I am not the right person to review this change. I have never made changes in this directory and don't know enough about potential impact to LGTM.

shawnl planned changes to this revision.Apr 25 2019, 8:51 AM

Make more portable

shawnl updated this revision to Diff 196755.Apr 25 2019, 4:34 PM
shawnl edited the summary of this revision. (Show Details)
shawnl edited reviewers, added: phosek, saugustine, shiva0217; removed: jmolloy.

made more portable

shawnl edited the summary of this revision. (Show Details)Apr 25 2019, 4:36 PM
shawnl edited the summary of this revision. (Show Details)Apr 25 2019, 4:42 PM
shawnl planned changes to this revision.Apr 25 2019, 4:48 PM

I don't think this should use function pointers.

hans added a comment.Apr 26 2019, 2:20 AM

I'm also not really familiar with code in compiler-rt.

However, as pointed out in https://bugs.llvm.org/show_bug.cgi?id=39013#c4 the compiler-rt builtins are not available for most targets.

I can mostly speak for Chromium, but in those builds we use libgcc on Linux, the Windows libraries on Windows, and on Mac we use the system's compiler-rt.

This means if you want to do any switch transformation that relies on this runtime function, that transformation will have to be disabled in general, and at that point I'm not sure it makes sense to have it in tree.

I'd suggest trying to emit the runtime code that your switch transformation relies on as LLVM IR instead. That might actually be easier, because e.g. you can rely on LLVM's popcount intrinsic, and you can do lower level stuff that is maybe useful.

shawnl abandoned this revision.Jun 14 2019, 8:31 AM

This will be put directly into LLVM-IR, as llvm can't inline it otherwise anyways.