Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

LLVM arbitrary precision integer

LLVM language reference states that

The integer type is a very simple type that simply specifies an arbitrary bit width for the integer type desired. Any bit width from 1 bit to 223-1 (about 8 million) can be specified.

Does that mean that I can make use of arbitrary fixed length integers for free? That's to say, if I declare an i100, will I have a variable with 100 bits width?

like image 271
GdelP Avatar asked Mar 07 '14 16:03

GdelP


1 Answers

I'm not entirely sure what you mean by "free", but yes LLVM will let you do it and compile it on some platforms. But it's going to come at a cost as opposed to types sized on multiples of the CPU registers.

If you create a i100 it allocate a block of 100 bits on the stack. If you do operations over it you will be limited to to whatever the CPU provides for instruction set. If you want to add two 64 bit integers the IR would look like:

define i64 @add(i64 %a, i64 %b) {
  %1 = add i64 %a, %b
  ret i64 %1
}

Then we get our generated assembly which is usually one instruction:

add:                                    # @add
    .cfi_startproc
# BB#0:
    addq    %rsi, %rdi
    movq    %rdi, %rax
    ret

But for instance, if you work we wanted to add two i1024 integers in the following IR:

define i1024 @add(i1024 %a, i1024 %b) {
  %1 = add i1024 %a, %b
  ret i1024 %1
}

Then the generated assembly on for x86-64 system is this not-terribly efficient collection of instructions, a lot of which are just mov'ing memory around memory.

add:                                    # @add
    .cfi_startproc
# BB#0:
    pushq   %r15
.Ltmp5:
    .cfi_def_cfa_offset 16
    pushq   %r14
.Ltmp6:
    .cfi_def_cfa_offset 24
    pushq   %r12
.Ltmp7:
    .cfi_def_cfa_offset 32
    pushq   %rbx
.Ltmp8:
    .cfi_def_cfa_offset 40
.Ltmp9:
    .cfi_offset %rbx, -40
.Ltmp10:
    .cfi_offset %r12, -32
.Ltmp11:
    .cfi_offset %r14, -24
.Ltmp12:
    .cfi_offset %r15, -16
    movq    40(%rsp), %r10
    addq    128(%rsp), %rsi
    adcq    136(%rsp), %rdx
    adcq    144(%rsp), %rcx
    adcq    152(%rsp), %r8
    adcq    160(%rsp), %r9
    movq    96(%rsp), %r14
    movq    104(%rsp), %r11
    movq    80(%rsp), %r12
    movq    88(%rsp), %r15
    adcq    168(%rsp), %r10
    movq    64(%rsp), %rax
    movq    72(%rsp), %rbx
    movq    %rsi, (%rdi)
    movq    %rdx, 8(%rdi)
    movq    48(%rsp), %rsi
    movq    56(%rsp), %rdx
    movq    %rcx, 16(%rdi)
    movq    %r8, 24(%rdi)
    movq    %r9, 32(%rdi)
    movq    112(%rsp), %rcx
    movq    120(%rsp), %r8
    adcq    176(%rsp), %rsi
    adcq    184(%rsp), %rdx
    adcq    192(%rsp), %rax
    adcq    200(%rsp), %rbx
    adcq    208(%rsp), %r12
    adcq    216(%rsp), %r15
    adcq    224(%rsp), %r14
    movq    %r10, 40(%rdi)
    movq    %rsi, 48(%rdi)
    movq    %rdx, 56(%rdi)
    movq    %rax, 64(%rdi)
    movq    %rbx, 72(%rdi)
    movq    %r12, 80(%rdi)
    movq    %r15, 88(%rdi)
    movq    %r14, 96(%rdi)
    adcq    232(%rsp), %r11
    movq    %r11, 104(%rdi)
    adcq    240(%rsp), %rcx
    movq    %rcx, 112(%rdi)
    adcq    248(%rsp), %r8
    movq    %r8, 120(%rdi)
    popq    %rbx
    popq    %r12
    popq    %r14
    popq    %r15
    ret
like image 142
Stephen Diehl Avatar answered Oct 15 '22 09:10

Stephen Diehl