llvm dev - Jun 2010 - [LLVMdev] Adding support to LLVM for data & code layout (needed by GHC)

Yes, the global structure is constant. This is indeed a side-table.
Overriding section of global to be in text is simple -- LLVM already
supports section attribute on globals and functions. However we also
need a specific ordering in text.
With some extra work this ordering can be achieved with gnu linker (I
posted example implementation earlier) without any changes to LLVM, so
the main points for having a direct support for side-tables in LLVM is
1) Not relying on external tool
2) Optimizer issues

Eugene

On Tue, Jun 8, 2010 at 10:35 PM, Andrew Lenharth <andrewl at lenharth.org>
wrote:
> On Tue, Jun 8, 2010 at 4:15 PM, Eugene Toder <eltoder at gmail.com>
wrote:
>> Let me point out that projects using standard toolchain (e.g.
>> binutils) can already reorder code and data pretty much arbitrary
>> using sections and linker scripts.
>> I think it's still attractive to have reordering in LLVM to be
>> independent from external toolchain. This will allow reordering in JIT
>> and other interesting things.
>>
>> I agree with John that special global with ordered list looks like the
>> clean approach. However, for the specific need in GHC I'm not sure
>> that this is enough.
>> What it's trying to do is placing a global variable (a struct) and
a
>> function next to each other, so that it can use pointer arithmetic to
>> go from one address to another.
>> So, say, we take the address of the struct, add it's size and call
>> into resulting address. Sufficiently smart optimizer can spot that we
>> dereference a pointer pointing outside of the object. This probably
>> has undefined semantics and can be replaced with unreachable?
>> It's also a missed opportunity for optimizations -- if optimizer
knew
>> where outside-of-the-struct pointer is really going it could make
>> direct call instead of indirect -- however, I don't know if this is
a
>> big deal.
>
> If I understand, you want more than just ordering within a section,
> you want to override the section of a global to be in the text (or
> equivalent) section.  Is the global structure constant?  It seems a
> way to splat constants directly before/after/in a function and refer
> to them as a global would be useful for all manner of side-tables.
> Being able to just order output of globals and functions make picking
> sections for them fairly hackish.
>
> Andrew
>
>
>> Eugene
>>
>> On Tue, Jun 8, 2010 at 3:50 PM, Sebastian Redl
>> <sebastian.redl at getdesigned.at> wrote:
>>>
>>> On Tue, 8 Jun 2010 11:42:41 +0100, David Terei <davidterei at
gmail.com>
>>> wrote:
>>>> Hi All,
>>>>
>>>> The GHC developers would like to add support to llvm to enable
the
>>>> order that code and data are laid out in, in the resulting
assembly
>>>> code produced by llvm to be defined by the user. The reason we
would
>>>> like to have this feature is explained in the blog post on
GHC's use
>>>> of llvm here:
>>>>
http://blog.llvm.org/2010/05/glasgow-haskell-compiler-and-llvm.html,
>>>> specifically under the title, 'Problems with backend'.
>>>>
>>>
>>> Whichever way is chosen, the ability to reorder and intermingle
functions
>>> and data arbitrarily is interesting to more than just GHC. In
particular, I
>>> would like to point out the efforts by Mozilla to make Firefox
startup
>>> faster, which essentially came down to reordering stuff in the
executables
>>> so that everything is ordered by the sequence of accesses during
program
>>> startup. This means that programs can be read sequentially from the
front
>>> to the end, thus reducing I/O latency.
>>>
>>> Tools for automating this process would probably benefit from being
able
>>> to specify the layout this way.
>>>
>>> Sebastian
>>>
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>
>

On Wed, Jun 9, 2010 at 4:16 PM, Eugene Toder <eltoder at gmail.com>
wrote:
> Yes, the global structure is constant. This is indeed a side-table.
> Overriding section of global to be in text is simple -- LLVM already
> supports section attribute on globals and functions. However we also
> need a specific ordering in text.
> With some extra work this ordering can be achieved with gnu linker (I
> posted example implementation earlier) without any changes to LLVM, so
> the main points for having a direct support for side-tables in LLVM is
> 1) Not relying on external tool
> 2) Optimizer issues
My argument amounts to express side tables as side tables in the IR
rather than as an ordering on globals.  I think that would simplify
the backend (a side table is something you discover form the function
rather than having to check another global).  Also, if well specified,
I think you could allow basic block labels into structures which makes
them more interesting for other uses.

Andrew
> Eugene
>
> On Tue, Jun 8, 2010 at 10:35 PM, Andrew Lenharth <andrewl at
lenharth.org> wrote:
>> On Tue, Jun 8, 2010 at 4:15 PM, Eugene Toder <eltoder at
gmail.com> wrote:
>>> Let me point out that projects using standard toolchain (e.g.
>>> binutils) can already reorder code and data pretty much arbitrary
>>> using sections and linker scripts.
>>> I think it's still attractive to have reordering in LLVM to be
>>> independent from external toolchain. This will allow reordering in
JIT
>>> and other interesting things.
>>>
>>> I agree with John that special global with ordered list looks like
the
>>> clean approach. However, for the specific need in GHC I'm not
sure
>>> that this is enough.
>>> What it's trying to do is placing a global variable (a struct)
and a
>>> function next to each other, so that it can use pointer arithmetic
to
>>> go from one address to another.
>>> So, say, we take the address of the struct, add it's size and
call
>>> into resulting address. Sufficiently smart optimizer can spot that
we
>>> dereference a pointer pointing outside of the object. This probably
>>> has undefined semantics and can be replaced with unreachable?
>>> It's also a missed opportunity for optimizations -- if
optimizer knew
>>> where outside-of-the-struct pointer is really going it could make
>>> direct call instead of indirect -- however, I don't know if
this is a
>>> big deal.
>>
>> If I understand, you want more than just ordering within a section,
>> you want to override the section of a global to be in the text (or
>> equivalent) section.  Is the global structure constant?  It seems a
>> way to splat constants directly before/after/in a function and refer
>> to them as a global would be useful for all manner of side-tables.
>> Being able to just order output of globals and functions make picking
>> sections for them fairly hackish.
>>
>> Andrew
>>
>>
>>> Eugene
>>>
>>> On Tue, Jun 8, 2010 at 3:50 PM, Sebastian Redl
>>> <sebastian.redl at getdesigned.at> wrote:
>>>>
>>>> On Tue, 8 Jun 2010 11:42:41 +0100, David Terei <davidterei
at gmail.com>
>>>> wrote:
>>>>> Hi All,
>>>>>
>>>>> The GHC developers would like to add support to llvm to
enable the
>>>>> order that code and data are laid out in, in the resulting
assembly
>>>>> code produced by llvm to be defined by the user. The reason
we would
>>>>> like to have this feature is explained in the blog post on
GHC's use
>>>>> of llvm here:
>>>>>
http://blog.llvm.org/2010/05/glasgow-haskell-compiler-and-llvm.html,
>>>>> specifically under the title, 'Problems with
backend'.
>>>>>
>>>>
>>>> Whichever way is chosen, the ability to reorder and intermingle
functions
>>>> and data arbitrarily is interesting to more than just GHC. In
particular, I
>>>> would like to point out the efforts by Mozilla to make Firefox
startup
>>>> faster, which essentially came down to reordering stuff in the
executables
>>>> so that everything is ordered by the sequence of accesses
during program
>>>> startup. This means that programs can be read sequentially from
the front
>>>> to the end, thus reducing I/O latency.
>>>>
>>>> Tools for automating this process would probably benefit from
being able
>>>> to specify the layout this way.
>>>>
>>>> Sebastian
>>>>
>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>>
>>>
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>
>>
>

Its good to see that a feature of this nature would be useful to a
whole range of people, I wasn't aware of that.

On 9 June 2010 22:40, Andrew Lenharth <andrewl at lenharth.org>
wrote:
> My argument amounts to express side tables as side tables in the IR
> rather than as an ordering on globals.  I think that would simplify
> the backend (a side table is something you discover form the function
> rather than having to check another global).  Also, if well specified,
> I think you could allow basic block labels into structures which makes
> them more interesting for other uses.
Sure. I wasn't set on the third approach I suggested, which is to have
them expressed as side tables in the IR as I didn't realise other
users would be interested in them so I didn't think it would be
appropriate to add new language constructs for one user. I don't think
it would simpler to implement in the backend though and this approach
would need changes to the frontend, so a lot more work.

What I am hoping someone may be able to give a answer to though is
what issues there may be if the second approach was taken (using the
special glob var)? Would the optimiser be tempted at some point to
replace a load instruction to an unknown address created by a negative
offset from a function with unreachable for example as Eugene
suggested may be possible?

Also, what are you gaining going with the third approach? I guess the
optimiser could do things like constant propogation using the third
approach but not the second although I think thats unlikely do give
much benefit in the kind of code GHC produces but there is everyone
else to think of :).

Thanks for all the responses though, I'm going to start playing around
with some code and see what happens.