llvm dev - May 2014 - [LLVMdev] GHC, aliases, and LLVM HEAD

Peter: Please feel free to correct me if there are any inaccuracies
       below.

For a while now LLVM has started rejecting aliases referring to things
other than definitions[1]. This unfortunately breaks GHC's LLVM code
generator which referes to most symbols through aliases. This is done in
two situations,

  1. As place-holders for external symbols. As the code generator does
     not know the type of these symbols until the point of usage (nor
     does it need to), i8* aliases are defined at the end of the
     compilation unit,

         @newCAF = external global i8
         @newCAF$alias = alias private i8* @newCAF

     and functions in the current compilation unit calling `newCAF` invoke
     it through `@newCAF$alias$`,

         ...
         %lnYi = bitcast i8* @newCAF$alias to i8* (i8*, i8*)*
         ...

  2. As place-holders for local symbols. All symbol references in
     emitted functions are replaced with references to aliases.  This is
     done so that the compiler can emit LLVM IR definitions for
     functions without waiting for symbols they reference to become
     available (as our internal representation, Core, allows references
     in any order without forward declarations). This theoretically
     offers a performance improvement and somewhat simplifies the code
     generator. Here we emit aliases like,

         @SWn_srt$alias = alias private i8* bitcast (%SWn_srt_struct* @SWn_srt
to i8*)

     again, using the `$alias` in all references,


Unfortunately, recent LLVMs reject both of these uses. The first is
rejected as aliases can no longer reference items other than
definitions, e.g.

    opt: hi.ll:414:36: error: Alias must point to function or variable
    @SWn_srt$alias = alias private i8* bitcast (%SWn_srt_struct* @SWn_srt to
i8*)

The second is rejected as aliasees must[2] be global objects, which
bitcasts are not,

    /home/ben/trees/root-llvm-head/bin/opt:
utils/hpc/dist-install/build/HpcParser.ll:44714:37: error: Alias must point to
function or variable
    @c3rB_str$alias = alias private i8* bitcast (%c3rB_str_struct* @c3rB_str to
i8*)
                                        ^

Is our (ab)use of aliases reasonable? If so, what options do we have to
fix this before LLVM 3.5? If not, what other mechanisms are there for
addressing the use-cases above in GHC?

Thanks,

- Ben


[1]
https://github.com/llvm-mirror/llvm/commit/38048cdb1c016e1429004ddf4adfa40a8d853cbf
[2]
https://github.com/llvm-mirror/llvm/blob/68b0d1d2b47f1be8eec2ce57c8119906c354ccd8/lib/AsmParser/LLParser.cpp#L692
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 472 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140525/d17a8b96/attachment.sig>

On 25 May 2014 21:29, Ben Gamari <bgamari.foss at gmail.com>
wrote:
>
> Peter: Please feel free to correct me if there are any inaccuracies
>        below.
>
> For a while now LLVM has started rejecting aliases referring to things
> other than definitions[1].
We started checking for it. Aliases are just another label in an
object file. The linker itself doesn't know they exist and therefore
there is no way to represent an alias from foo to bar if bar is
undefined.
> This unfortunately breaks GHC's LLVM code
> generator which referes to most symbols through aliases. This is done in
> two situations,
>
>   1. As place-holders for external symbols. As the code generator does
>      not know the type of these symbols until the point of usage (nor
>      does it need to), i8* aliases are defined at the end of the
>      compilation unit,
>
>          @newCAF = external global i8
>          @newCAF$alias = alias private i8* @newCAF
>
>      and functions in the current compilation unit calling `newCAF` invoke
>      it through `@newCAF$alias$`,
>
>          ...
>          %lnYi = bitcast i8* @newCAF$alias to i8* (i8*, i8*)*
>          ...
Sorry, I don't see what this buys you. The types of newFAC and
newCAF$alias are the same.
>   2. As place-holders for local symbols. All symbol references in
>      emitted functions are replaced with references to aliases.  This is
>      done so that the compiler can emit LLVM IR definitions for
>      functions without waiting for symbols they reference to become
>      available (as our internal representation, Core, allows references
>      in any order without forward declarations). This theoretically
>      offers a performance improvement and somewhat simplifies the code
>      generator. Here we emit aliases like,
>
>          @SWn_srt$alias = alias private i8* bitcast (%SWn_srt_struct*
@SWn_srt to i8*)
>
>      again, using the `$alias` in all references,
That should also work in llvm IR. You can create a function without a
body or a GlobalVariable without an initializer and add it afterwards.
Check for example what llvm-as does when a variable or a function is
used before it is defined. Doesn't that work for you?
>
> Unfortunately, recent LLVMs reject both of these uses. The first is
> rejected as aliases can no longer reference items other than
> definitions, e.g.
>
>     opt: hi.ll:414:36: error: Alias must point to function or variable
>     @SWn_srt$alias = alias private i8* bitcast (%SWn_srt_struct* @SWn_srt
to i8*)
>
> The second is rejected as aliasees must[2] be global objects, which
> bitcasts are not,
>
>     /home/ben/trees/root-llvm-head/bin/opt:
utils/hpc/dist-install/build/HpcParser.ll:44714:37: error: Alias must point to
function or variable
>     @c3rB_str$alias = alias private i8* bitcast (%c3rB_str_struct*
@c3rB_str to i8*)
>                                         ^
>
> Is our (ab)use of aliases reasonable? If so, what options do we have to
> fix this before LLVM 3.5? If not, what other mechanisms are there for
> addressing the use-cases above in GHC?
It looks fairly likely llvm will accept arbitrary expressions as
aliasees again (see thread on llvmdev), but the restrictions inherent
from what alias are at the object level will remain, just be reworded
a bit. For example, we will have something along the lines of "the
aliasee expression cannot contain an undefined GlobalValue".

Cheers,
Rafael

Rafael Espíndola <rafael.espindola at gmail.com> writes:
> On 25 May 2014 21:29, Ben Gamari <bgamari.foss at gmail.com> wrote:
>>
>> For a while now LLVM has started rejecting aliases referring to things
>> other than definitions[1].
>
> We started checking for it. Aliases are just another label in an
> object file. The linker itself doesn't know they exist and therefore
> there is no way to represent an alias from foo to bar if bar is
> undefined.
>
Sure. I think the only reason our use of aliases worked previously was
that the optimizer elided them long before they could make it into an
object file.
>>
>>   1. As place-holders for external symbols. As the code generator does
>>      not know the type of these symbols until the point of usage (nor
>>      does it need to), i8* aliases are defined at the end of the
>>      compilation unit,
>>
As it turns out this wasn't quite right; there are some cases that we
don't know the type of the reference even at the point of usage (namely
when we refer to the function's entrypoint label without calling it as
only C--'s call node contains the signature).
>>          @newCAF = external global i8
>>          @newCAF$alias = alias private i8* @newCAF
>>
>>      and functions in the current compilation unit calling `newCAF`
invoke
>>      it through `@newCAF$alias$`,
>>
>>          ...
>>          %lnYi = bitcast i8* @newCAF$alias to i8* (i8*, i8*)*
>>          ...
>
> Sorry, I don't see what this buys you. The types of newCAF and
> newCAF$alias are the same.
>
It seems you are right, you could just define
the external symbol,

    @newCAF$alias = external global i8

Unfortunately this still leaves the problem of local symbols.
>>   2. As place-holders for local symbols. All symbol references in
>>      emitted functions are replaced with references to aliases.  This
is
>>      done so that the compiler can emit LLVM IR definitions for
>>      functions without waiting for symbols they reference to become
>>      available (as our internal representation, Core, allows references
>>      in any order without forward declarations). This theoretically
>>      offers a performance improvement and somewhat simplifies the code
>>      generator. Here we emit aliases like,
>>
>>          @SWn_srt$alias = alias private i8* bitcast (%SWn_srt_struct*
@SWn_srt to i8*)
>>
>>      again, using the `$alias` in all references,
>
> That should also work in llvm IR. You can create a function without a
> body or a GlobalVariable without an initializer and add it afterwards.
>
I'm not sure I follow. If I attempt to compile,

    declare i32 @main()
    define i32 @main() {
        ret i32 0
    }

It fails with,

    llc: test.ll:3:12: error: invalid redefinition of function 'main'
    define i32 @main() {
               ^
> Check for example what llvm-as does when a variable or a function is
> used before it is defined. Doesn't that work for you?
>
The problem here is that we don't know the type of the symbol at the
point of use so I need to assume it is something (e.g. i8*). Take for
instance the following example,


    define i32 @main() {
        // We don't know the type of f a priori, thus we assume
        // it is i8*
        %f = bitcast i8* f$alias to i32 ()*
        call i32 %f()
        ret i32 0
    }

Say then later in GHC's Core representation, we get a definition for
`f`. We have two ways of dealing with this,

    1. Declare it as @f and create an alias as we currently do,

           define i32 @f() {
               ret i32 0
           }
           @f$alias = alias private i8* @f

       but then we fail with recent LLVMs


    2. Declare it as @f$alias directly as I think you might be suggesting

           define i32 @f$alias() {
               ret i32 0
           }

       but then we get a type mismatch at the point of usage as we claim
       that @f$alias is of type i8*.

>>
>> Is our (ab)use of aliases reasonable? If so, what options do we have to
>> fix this before LLVM 3.5? If not, what other mechanisms are there for
>> addressing the use-cases above in GHC?
>
> It looks fairly likely llvm will accept arbitrary expressions as
> aliasees again (see thread on llvmdev), but the restrictions inherent
> from what alias are at the object level will remain, just be reworded
> a bit. For example, we will have something along the lines of "the
> aliasee expression cannot contain an undefined GlobalValue".
>
Alright. I'll put my GHC work aside until this is resolved in that
case. My current goal is to implement tables-next-to-code using the
recently merged prefix data syntax and symbol offset support that I sent
to the list yesterday. It would be great if you could ping me when this
is resolved so I know when this work can be continued.

Thanks,

- Ben
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 472 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140526/d92f16a4/attachment.sig>

> It looks fairly likely llvm will accept arbitrary expressions as
> aliasees again (see thread on llvmdev), but the restrictions inherent
> from what alias are at the object level will remain, just be reworded
> a bit. For example, we will have something along the lines of "the
> aliasee expression cannot contain an undefined GlobalValue".
And this is in: r210062.

Let us know how it looks from GHC's point of view.

Cheers,
Rafael