Csaba Hruska via llvm-dev
2017-Oct-08 13:44 UTC
[llvm-dev] returning tagged union via registers
Hi, AFAIK LLVM does not have direct support for tagged unions. However I'd like to pass tagged unions to/from functions in registers. I.e. I'd like to represent to following data type in registers. With Haskell syntax it looks like:> *data AllCon = Con1Data i32 | Con2Data i32* >A possible LLVM in register representation could be the following including a *create* and *consume* function as an example. *%struct.Con1Data = type { i32 }*> *%struct.Con2Data = type { i32 }* > *%struct.AllCon = type { i1, %struct.Con1Data, %struct.Con2Data }* > > *define private fastcc %struct.AllCon @create(i1 %s) {* > *entry:* > * %X = select i1 %s,* > * %struct.AllCon {i1 true, %struct.Con1Data { i32 4 }, %struct.Con2Data > undef},* > * %struct.AllCon {i1 false, %struct.Con1Data undef, %struct.Con2Data { > i32 5 }}* > * ret %struct.AllCon %X* > *}* > > *define private fastcc i32 @consume(i1 %s) {* > *grinMain.entry:* > * %val = call fastcc %struct.AllCon @create(i1 %s)* > * %tag = extractvalue %struct.AllCon %val, 0* > > * %con1_int = extractvalue %struct.AllCon %val, 1, 0* > * %con2_int = extractvalue %struct.AllCon %val, 2, 0* > * %res = select i1 %s, i32 %con1_int, i32 %con2_int* > > * ret i32 %res* > *}* >I'd like to achieve an efficient mapping to x64 machine code. In the ideal case the *create* function result would be stored only in 2 registers. One i1 for the tag and one i32 for the argument value either come from Con1Data or Con2Data. For storing the i32 values one register would be always enough hence the constructors are mutually exclusive. As you can see in the generated code below by default LLVM allocates separate registers for Con1Data and Con2Data arguments (ecx and edx). But ideally it would use only a single register for both. Of course to achieve that the frontend have to prove somehow that these values are on mutually exclusive data flow. * .text*> * .file "node_test_reg3.ll.1"* > * .p2align 4, 0x90 # -- Begin function create* > * .type .Lcreate, at function* > *.Lcreate: # @create* > * .cfi_startproc* > *# BB#0: # %entry* > * movl %edi, %eax* > * andb $1, %al* > * movl $5, %ecx* > * cmovnel %eax, %ecx* > * testb %al, %al* > * movl $4, %eax* > * cmovnel %eax, %edx* > * movl %edi, %eax* > * retq* > *.Lfunc_end0:* > * .size .Lcreate, .Lfunc_end0-.Lcreate* > * .cfi_endproc* > * # -- End function* > * .p2align 4, 0x90 # -- Begin function consume* > * .type .Lconsume, at function* > *.Lconsume: # @consume* > * .cfi_startproc* > *# BB#0: # %grinMain.entry* > * pushq %rbx* > *.Lcfi0:* > * .cfi_def_cfa_offset 16* > *.Lcfi1:* > * .cfi_offset %rbx, -16* > * movl %edi, %ebx* > * callq .Lcreate* > * testb $1, %bl* > * cmovnel %edx, %ecx* > * movl %ecx, %eax* > * popq %rbx* > * retq* > *.Lfunc_end1:* > * .size .Lconsume, .Lfunc_end1-.Lconsume* > * .cfi_endproc* > * # -- End function* > > * .section ".note.GNU-stack","", at progbits* >Does anyone have an idea how can I achieve this in LLVM? I guess I have to extend the expressive power somehow (i.e. new metadata). What is the simplest change to support this? I'd appreciate if you'd help to figure out the complexity of this extension. Best regards, Csaba Hruska -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20171008/16b6a9ca/attachment-0001.html>
David Chisnall via llvm-dev
2017-Oct-09 08:44 UTC
[llvm-dev] returning tagged union via registers
On 8 Oct 2017, at 14:44, Csaba Hruska via llvm-dev <llvm-dev at lists.llvm.org> wrote:> > I'd like to achieve an efficient mapping to x64 machine code. In the ideal case the create function result would be stored only in 2 registers. One i1 for the tag and one i32 for the argument value either come from Con1Data or Con2Data. For storing the i32 values one register would be always enough hence the constructors are mutually exclusive. > > As you can see in the generated code below by default LLVM allocates separate registers for Con1Data and Con2Data arguments (ecx and edx). But ideally it would use only a single register for both. Of course to achieve that the frontend have to prove somehow that these values are on mutually exclusive data flow.You should probably look at how clang handles unions. Your example is roughly akin to the following in C: struct tagged_thing { bool tag; union { int data1; int data2; }; }; Clang will represent this as: %struct.tagged_thing = type { i8, %union.anon } %union.anon = type { i32 } If you look at how this is passed on x86-64: struct tagged_thing x() { return (struct tagged_thing){ 1, .data1 = 42 }; } becomes: ; Function Attrs: noinline nounwind ssp uwtable define i64 @x() #0 { %1 = alloca %struct.tagged_thing, align 4 %2 = getelementptr inbounds %struct.tagged_thing, %struct.tagged_thing* %1, i32 0, i32 0 store i8 1, i8* %2, align 4 %3 = getelementptr inbounds %struct.tagged_thing, %struct.tagged_thing* %1, i32 0, i32 1 %4 = bitcast %union.anon* %3 to i32* store i32 42, i32* %4, align 4 %5 = bitcast %struct.tagged_thing* %1 to i64* %6 = load i64, i64* %5, align 4 ret i64 %6 } Which optimises to: ; Function Attrs: norecurse nounwind readnone ssp uwtable define i64 @x() local_unnamed_addr #0 { ret i64 180388626433 } Clang is coercing the type to an i64, which ensures that it is returned in a single 64-bit register (or, on x86-32, a pair of 32-bit registers). Unfortunately, the mapping from IR constructs to registers in the back end is in the form of ad-hoc and poorly documented contracts, so you’ll need to compare the output for each version for each target that you care about. David