[cfe-dev] An unlimited-width integer type

[Philip Reames via cfe-dev]

Fair warning, I'm answering a bit outside my comfort zone, so some of
this might be wrong...

If you're wanting to have an LLVM backend that targets this abstract
machine, then lowering fixed precision integers into infinite precision
integers is fairly straight forward.  You just need to manually
implement the twos complement wrapping behaviors in the integer space
w/branching.  That probably won't be the fastest thing in the world, but
if you're targeting anything other than an mature VM, you shouldn't care. 

Your challenge will be representing the infinite integer type in the
backend.  You shouldn't need to change IR at all. 

The simplest, and slowest, approach would be to custom lower to a set of
intrinsic calls.  If you type your "registers" as oddly sized pointers
into a special address space, you can probably get that working.  Your
real challenge will be representing your "integer store" memory since it
is by definition not byte addressable.  I don't really have any good
suggestions there.  I'd strongly suggest figuring this piece out before
moving on to anything else.

The harder approach to the lowering would be introducing an integer type
in into the backend.  I have no input on difficulty of that, other than
to say it's probably not worth doing unless you're pushing performance
fairly hard.  (I doubt you are.)

Philip

On 11/7/19 9:41 AM, Levi Aul via cfe-dev wrote:
> Hi, I'm considering writing an LLVM backend to target an abstract
> machine, encoding to a bytecode ISA.
>
> This abstract machine has integers, but not in the sense of having
> fixed-size machine words; rather, each abstract-machine register and
> memory location can losslessly hold onto a distinct (non-aliasing)
> unlimited bit-width value, and math/bitwise ops will operate
> losslessly on these values to produce new values of unlimited
> bit-width, without any need for overflow into neighbouring
> registers/memory locations.
>
> A VM implementing this abstract machine would, of course, use some
> kind of bignum library to implement these semantics, with each such
> integer value actually being a pointer to a VM-heap-allocated bignum;
> or, perhaps, the VM would do load-time optimization to strength-reduce
> some of the bignums to regular host-CPU integer types.
>
> But, from the perspective of a compiler targeting the abstract machine
> itself, the ISA just "has" registers and ops of an 'iUNLIMITED' type.
>
> Does LLVM, and specifically the LLVM IR type system, support anything
> like this? If not, would it be the work of days, or of months, to make
> it happen?
>
> _______________________________________________
> cfe-dev mailing list
> cfe-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20191108/75efaa7d/attachment.html>