llvm dev - Jul 2019 - Using bytecode version of std::sort for JIT generated data type

On Mon, Jul 8, 2019 at 4:39 PM David Blaikie <dblaikie at gmail.com>
wrote:
> There isn't any magic command for this - you'd have to write some
C++
> code/a custom LLVM optimization pass.
>
> Though, that said - perhaps it should just be a runtime parameter where
> you rely on LLVM to inline/optimize things away? You could do some
> relatively smaller code generation - generate a function that calls into
> the generic function (that takes the functior by pointer) and have the
> generic function be always_inline, so it gets inlined into the outer,
> type-specific function, without you having to write code to create all that
> IR on every use (instead relying on the inliner to create it for you,
> essentially)
>
I don't understand what you mean here. If sort is already generated into
machine code based on Compare(void*, void*) { return false; } how can we
inject our function here?
>
> On Mon, Jul 8, 2019 at 4:33 PM Rajesh S R <srrajesh1989 at gmail.com>
wrote:
>
>> Thanks David!
>>
>> I am not clear on how to achieve this though. Could you give more info
on
>> this?
>>
>> I expect something like this:
>>
>> sort.cc file:
>>
>> bool Compare(void* a, void* b) {
>>   return false;
>> }
>>
>> void SortFunc(void* arr, int len) {
>>    std::sort(arr, len, &Compare)
>> }
>>
>> $MAGIC_COMMAND sort.cc -o a.llvm
>>
>> a.llvm is a bytecode which can be loaded at runtime in my JIT module
and
>> write some code to replace "Compare" function with our own
"Compare"
>> function.
>>
>>
>>
>> On Mon, Jul 8, 2019 at 1:17 PM David Blaikie <dblaikie at
gmail.com> wrote:
>>
>>> 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/3851191a/attachment.html>

Ah, no, sort wouldn't be compiled down to machine code - it'd be in LLVM
IR. You'd import that into the module where the user code was (or copy this
"standard library" LLVM IR module and then add the to-be-JITed code to
that
copy, then compile it all together).

On Mon, Jul 8, 2019 at 8:45 PM Rajesh S R <srrajesh1989 at gmail.com>
wrote:
>
>
> On Mon, Jul 8, 2019 at 4:39 PM David Blaikie <dblaikie at gmail.com>
wrote:
>
>> There isn't any magic command for this - you'd have to write
some C++
>> code/a custom LLVM optimization pass.
>>
>> Though, that said - perhaps it should just be a runtime parameter where
>> you rely on LLVM to inline/optimize things away? You could do some
>> relatively smaller code generation - generate a function that calls
into
>> the generic function (that takes the functior by pointer) and have the
>> generic function be always_inline, so it gets inlined into the outer,
>> type-specific function, without you having to write code to create all
that
>> IR on every use (instead relying on the inliner to create it for you,
>> essentially)
>>
>
> I don't understand what you mean here. If sort is already generated
into
> machine code based on Compare(void*, void*) { return false; } how can we
> inject our function here?
>
>>
>> On Mon, Jul 8, 2019 at 4:33 PM Rajesh S R <srrajesh1989 at
gmail.com> wrote:
>>
>>> Thanks David!
>>>
>>> I am not clear on how to achieve this though. Could you give more
info
>>> on this?
>>>
>>> I expect something like this:
>>>
>>> sort.cc file:
>>>
>>> bool Compare(void* a, void* b) {
>>>   return false;
>>> }
>>>
>>> void SortFunc(void* arr, int len) {
>>>    std::sort(arr, len, &Compare)
>>> }
>>>
>>> $MAGIC_COMMAND sort.cc -o a.llvm
>>>
>>> a.llvm is a bytecode which can be loaded at runtime in my JIT
module and
>>> write some code to replace "Compare" function with our
own "Compare"
>>> function.
>>>
>>>
>>>
>>> On Mon, Jul 8, 2019 at 1:17 PM David Blaikie <dblaikie at
gmail.com> wrote:
>>>
>>>> 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/20190709/d0548a83/attachment.html>

Do you have some pointers on how to do it? Take a file like sort.cc above
and generate a JIT module. Does llc
<https://llvm.org/docs/CommandGuide/llc.html> help with this?
What library function can we use to load an existing IR module file into my
JIT runtime module to compile them together?

On Tue, Jul 9, 2019 at 4:17 PM David Blaikie <dblaikie at gmail.com>
wrote:
> Ah, no, sort wouldn't be compiled down to machine code - it'd be in
LLVM
> IR. You'd import that into the module where the user code was (or copy
this
> "standard library" LLVM IR module and then add the to-be-JITed
code to that
> copy, then compile it all together).
>
> On Mon, Jul 8, 2019 at 8:45 PM Rajesh S R <srrajesh1989 at gmail.com>
wrote:
>
>>
>>
>> On Mon, Jul 8, 2019 at 4:39 PM David Blaikie <dblaikie at
gmail.com> wrote:
>>
>>> There isn't any magic command for this - you'd have to
write some C++
>>> code/a custom LLVM optimization pass.
>>>
>>> Though, that said - perhaps it should just be a runtime parameter
where
>>> you rely on LLVM to inline/optimize things away? You could do some
>>> relatively smaller code generation - generate a function that calls
into
>>> the generic function (that takes the functior by pointer) and have
the
>>> generic function be always_inline, so it gets inlined into the
outer,
>>> type-specific function, without you having to write code to create
all that
>>> IR on every use (instead relying on the inliner to create it for
you,
>>> essentially)
>>>
>>
>> I don't understand what you mean here. If sort is already generated
into
>> machine code based on Compare(void*, void*) { return false; } how can
we
>> inject our function here?
>>
>>>
>>> On Mon, Jul 8, 2019 at 4:33 PM Rajesh S R <srrajesh1989 at
gmail.com>
>>> wrote:
>>>
>>>> Thanks David!
>>>>
>>>> I am not clear on how to achieve this though. Could you give
more info
>>>> on this?
>>>>
>>>> I expect something like this:
>>>>
>>>> sort.cc file:
>>>>
>>>> bool Compare(void* a, void* b) {
>>>>   return false;
>>>> }
>>>>
>>>> void SortFunc(void* arr, int len) {
>>>>    std::sort(arr, len, &Compare)
>>>> }
>>>>
>>>> $MAGIC_COMMAND sort.cc -o a.llvm
>>>>
>>>> a.llvm is a bytecode which can be loaded at runtime in my JIT
module
>>>> and write some code to replace "Compare" function
with our own "Compare"
>>>> function.
>>>>
>>>>
>>>>
>>>> On Mon, Jul 8, 2019 at 1:17 PM David Blaikie <dblaikie at
gmail.com>
>>>> wrote:
>>>>
>>>>> 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/20190709/6a10e93c/attachment.html>