Số học số lớn sử dụng LLVM (từ Haskell)

Question

Câu trả lời cho số question trước đây của tôi cho biết rằng Haskell đại diện cho plusWord2# là llvm.uadd.with.overflow. Tôi đang tìm kiếm để làm bổ sung dài với carry, giống như cách thức hoạt động của lệnh x86 ADC. Lệnh này không chỉ thêm hai đối số, mà còn thêm nội dung của bit carry.

Một sau đó có thể thêm số điện thoại dài như sau:

ADD x1 y1 
ADC x2 y2 
ADC x3 y3 
... 

Hệ quả là một hướng dẫn cho mỗi chữ (không tuân thủ bất kỳ động thái xung quanh vv yêu cầu).

Tôi đã xem thư viện GMP và cách nó tự bổ sung lâu dài, trong mã C chung của nó. Dưới đây là một đoạn trích từ mpn/generic/add_n.c

sl = ul + vl; 
cy1 = sl < ul; 
rl = sl + cy; 
cy2 = rl < sl; 
cy = cy1 | cy2; 

Lưu ý rằng lưu các bit mang từ cả bổ sung gốc và bổ sung bit mang. Chỉ một trong những hoạt động này có thể mang theo, do đó, hoặc việc mang theo sau đó là đủ. Rõ ràng GMP có mã lắp ráp cụ thể cho các nền tảng cụ thể, nhưng tôi nghĩ mã chung sẽ là cơ sở tốt, vì có lẽ nó sẽ được viết để biên dịch thành mã hợp lý. Các plusWord2# hoạt động nguyên thủy có nghĩa là tôi không cần phải làm so sánh ngớ ngẩn để có được các bit thực hiện, vì vậy tôi thực hiện các mã chung GMP như sau trong Haskell:

addWithCarry :: Word# -> Word# -> Word# -> (# Word#, Word# #) 
addWithCarry x y c = 
    let 
    (# c1, r1 #) = plusWord2# x y 
    (# c2, r2 #) = plusWord2# r1 c 
    in 
    (# or# c1 c2, r2 #) 

Đáng tiếc là kết quả này trong mã x86 mà tiết kiệm carry bit vào một thanh ghi trước khi thêm bit mang vào nó, cũng như thêm hai số, dẫn đến ba hoặc bốn hướng dẫn cho mỗi từ thay vì một.

Vì vậy, những gì tôi tự hỏi là làm thế nào tôi có thể kết hợp llvm.uadd.with.overflow để tạo ra một chuỗi các hướng dẫn ADC trên x86 để thực hiện số học đa độ chính xác. Nếu tôi nhận được mã LLVM tạo ra hiệu quả bổ sung dài, tôi đã hy vọng sau đó tôi có thể chuyển đổi nó trở lại thành Haskell nguyên thủy ops để sản xuất bổ sung hiệu quả trực tiếp từ mã Haskell.

Ghi chú:

tôi có thể sử dụng tất nhiên FFI Haskell để gọi lắp ráp nội tuyến hoặc GMP, nhưng điều đó sẽ ngăn chặn nội tuyến và tôi nghi ngờ là tương đối chậm so với mã inlined cho nhỏ (ví dụ < = 256 bit) toán hạng.

Tôi đã tìm thấy rằng 'clang' có __builtin_addc, một dạng ba đối số bổ sung không chỉ có hai số mà là một bit mang, nhưng GHC không biên dịch thông qua tiếng kêu, vì vậy tôi không thấy nó như thế nào hữu ích.

Answer 1

Điều chính xác cần thực hiện ở đây là đảm bảo rằng giao diện Haskell đại diện cho số học thực của bạn trong IR của LLVM bằng cách sử dụng các mẫu tương tự được tạo bởi Clang khi sử dụng __builtin_addc của nó.

Tuy nhiên, đừng mong đợi điều này để tạo mã tốt với LLVM ngay hôm nay. Xem http://llvm.org/PR20748, tài liệu mã hoàn toàn khủng khiếp mà chúng tôi hiện đang tạo trên x86 cho các mẫu nhỏ như thế này. Nhưng khi lỗi đó được sửa, bạn sẽ nhận được mã được tạo mà bạn mong muốn.