returning tagged union via registers

Project Infrastructure LLVM Dev List Archives
#1

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,@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,@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”,"",@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

#2

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