wiki:LongInteger

Version 2 (modified by cameron, 3 years ago) (diff)

--

The LLVM Long Integer Project

This project involves the systematic support of the i128 and i256 integer types.

Ideally, we want two levels of support:

  • generic long integer support that works on any architecture supporting i64, and
  • support using efficient SIMD operations on 128-bit and 256-bit registers for architectures having such facilities.

The operations to be supported for these long integer types are all of the following, as documented in the LLVM IR reference manual:

  • add, sub
  • mul, udiv, sdiv
  • shl, lshr, ashr
  • and, or, xor
  • load, store
  • trunc, sext, zext
  • bitcast both bitcast-to long integer types and bitcast from.
  • icmp with the 10 different comparison types:
    • eq, ne
    • ugt, uge, ult, ule
    • sgt, sge, slt, sle
  • Byte swap intrinsics: @llvm.bswap.i128, @llvm.bswap.i256
  • Count intrinsics for population count, leading and trailing zeroes:
    • @llvm.popcount.i128, @llvm.popcount.i256
    • @llvm.ctlz.i128, @llvm.ctlz.i256
    • @llvm.cttz.i128, @llvm.cttz.i256
  • Overflow intrinsics
    • @llvm.sadd.with.overflow.i128, @llvm.sadd.with.overflow.i128 @llvm.uadd.with.overflow.i128, @llvm.uadd.with.overflow.i128
    • @llvm.ssub.with.overflow.i128, @llvm.ssub.with.overflow.i128 @llvm.usub.with.overflow.i128, @llvm.usub.with.overflow.i128
    • @llvm.smul.with.overflow.i128, @llvm.smul.with.overflow.i128 @llvm.umul.with.overflow.i128, @llvm.umul.with.overflow.i128

These types and operations may already be supported for some architectures. Investigate and document the support. Evaluate the code generation. Arrange to generate efficient SIMD implementations wherever possible.

Special AVX2 Instructions

The add and sub operations for i256, as well as the overflow intrinsics, should be implemented using the long string addition technique documented in source:docs/Working/re/re-main.pdf

Count Leading/Trailing Zeroes Instructions

Use a two-level scanning technique following the pattern of BitStreamScanner in source:trunk/lib/bitblock_iterator.hpp@101