[llvm-dev] Using bytecode version of std::sort for JIT generated data type

[David Blaikie via llvm-dev]

That's an option, for sure - having llvm::Functions you could clone into
your module, replace the call to the Compare function to a call to the
specific comparison you want & the let the optimizers do their work.

On Wed, Jul 3, 2019 at 4:23 PM Rajesh S R <srrajesh1989 at gmail.com> wrote:

> Thanks David! I understand that std::sort doesn't exist without types
> especially at bytecode layer.
>
> What I was thinking was something like the following:
>
> Compile std::sort with a thunk function Compare(void*, void*) {rerturn
> false} into bytecode with an option say noinline and always make the
> function call or even a simple unoptimized bytecode which guarantees that
> Compare exists as a function without any inlining.
>
> At run time implement a new Compare function for your type and replace the
> Compare function with the new Compare implemented with JIT. Now the JIT
> runtime has whole program in bytecode which it can aggressively optimize.
> A good way to realize this "thunking" into LLVM JIT can enable lots of
> optimized algorithms to be ported into JIT without having to re-invent them
> for each JIT runtime.
>
> Thoughts?
>
> On Wed, Jul 3, 2019 at 3:56 PM David Blaikie <dblaikie at gmail.com> wrote:
>
>> If you consider how std::sort works - it doesn't exist in the machine (or
>> even LLVM IR) level without a specific type - so if you were to support
>> something like std::sort in your language (JITed or not), it means some
>> form of specialization of your types/functions based on other types.
>>
>> So, yes, something like "own Sort function inside JIT" - if your language
>> doesn't support a way to write this in the language itself (if it doesn't
>> have anything like C++ templates or an equivalent generic thing).
>>
>> Otherwise you can do something like qsort (which uses a function pointer
>> to parameterize the comparison) & perhaps force or encourage the optimizer
>> to inline and collapse away this indirection.
>>
>> On Wed, Jul 3, 2019 at 3:43 PM Rajesh S R via llvm-dev <
>> llvm-dev at lists.llvm.org> wrote:
>>
>>> Hi LLVM devs,
>>> The performance of C++ std::sort comes from being able to inline the
>>> comparator. For a JIT generated data type, using the comparator as a
>>> function call from std::sort may not be ideal. So, i was wondering how can
>>> we make a JIT-sort which is as good as statically compiled std::sort with
>>> comparator inlined.
>>>
>>> What is the recommended way to pass a an existing function like
>>> std::sort into JIT so that it can optimize the whole program? For example,
>>> how do we generate the bytecode for existing function (say some external
>>> tools) and give to JIT runtime. Is there some code sample?
>>>
>>> The alternative is to rollout my own Sort function inside JIT, but i
>>> don't want to do that and want to take this as an opportunity to learn the
>>> general approach of passing existing function definitions into JIT to do
>>> whole program optimization like inlining.
>>>
>>> I found this stackoverflow question
>>> <https://stackoverflow.com/questions/10587250/fast-to-compile-efficient-sort-algorithm-for-jit-compilation>which
>>> is related to what I am asking for, but I don't see any final conclusion on
>>> this beyond incurring a function call for each comparison.
>>>
>>> Thanks!
>>>
>>> Rajesh S R
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> llvm-dev at lists.llvm.org
>>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190708/3e71a321/attachment.html>