sum:
; Windows x64 calling convention:
; uint128 *a in RCX, *b in RDX, *sum in R8
push rsi ; non-volatile registers
push rdi
; clear CF and OF flags, carry-in = 0 to start both chains
xor eax,eax ; before loading data into RAX
; Or less efficient but doesn't destroy a register: test eax, eax
; sub rsp, 40 would also leave OF and CF=0
;; load all the data first for example purposes only,
;; into human-friendly pairs of registers like RDX:RCX
mov rax,r8 ; sum = rax
; r11:r10 = b[1] ;; standard notation is hi:lo
mov r11,[rdx+24] ; high half
mov r10,[rdx+16] ; low half
; r9:r8 = b[0]
mov r9,[rdx+8]
mov r8,[rdx]
; rdi:rsi = a[1]
mov rdi,[rcx+24]
mov rsi,[rcx+16]
; rdx:rcx = a[0] (overwriting the input pointers)
mov rdx,[rcx+8]
mov rcx,[rcx]
;;;;;; Now the ADCX/ADOX part
; compute a_sum in rdx:rcx
; compute b_sum in r9:r8
; Lower halves
; CF=0 and OF=0 thanks to an earlier instruction
adcx rcx, rsi ; a_sum.lo = a[0].lo + a[1].lo + 0
adox r8, r10 ; b_sum.lo = b[0].lo + b[1].lo + 0
; Higher halves
; CF and OF have carry-out from low halves
adcx rdx,rdi ; a_sum.hi = a[0].hi + a[1].hi + carry-in(CF)
adox r9,r11 ; b_sum.hi = b[0].hi + b[1].hi + carry-in(OF)
; nothing uses the CF and OF outputs, but that's fine.
; sum[0] = rdx:rcx
mov [rax],rcx
mov [rax+8],rdx
; sum[1] = r9:r8
mov [rax+16],r8
mov [rax+24],r9
;; Final addition the old fashioned way
; sum[2] = rdx:rcx (a_sum + b_sum)
add rcx,r8
adc rdx,r9
mov [rax+32],rcx
mov [rax+40],rdx
; clean up
pop rdi
pop rsi
ret
3条答案
按热度按时间0ve6wy6x1#
这些指令用于加速大整数运算。
在这些指令之前,添加大量数字通常会导致如下所示的代码序列:
这里要注意的重要部分是,如果加法的结果不适合机器字,则进位标志被设置并“结转”到下一个更高的机器字。所有这些指令都相互依赖,因为它们考虑了先前的加法进位标志 *,并且 * 在执行后生成新的进位标志值。
由于x86处理器能够同时执行多条指令,这成为一个巨大的瓶颈。依赖链使得处理器无法并行执行任何算术运算。(实际上你会发现在add/adc序列之间有一个加载和存储,但性能仍然受到进位依赖性的限制)。
为了改进这一点,英特尔通过重新解释溢出标志添加了第二个进位链。
adc
指令有两个新变体:adcx
和adox
adcx
与adc
相同,只是它不再修改OF(溢出)标志。adox
与adc
相同,但它将进位信息存储在OF标志中。它也不再修改进位标志。正如您所看到的,两个新的
adc
变体在标志使用方面不会相互影响。这允许您通过交错指令并行运行两个长整数加法,并对一个序列使用adcx
,对另一个序列使用adox
。s71maibg2#
引用Intel的论文New Instructions Support Large Integer Arithmetic:
adcx和adox指令是adc指令的扩展,旨在支持两个独立的进位链。它们被定义为:
这两条指令都计算src 1和src 2的和加上进位输入,并生成输出和dest和进位输出。这两条指令之间的区别在于adcx使用CF标志进行进位输入和进位输出(保持OF标志不变),而adox指令使用OF标志进行进位输入和进位输出(保持CF标志不变)。
这些指令相对于adc的主要优点是它们支持两个独立的进位链。
本文展示了将其与BMI 2
mulx
(no-flags widening multiply)结合使用的示例,用于512位BigInt乘法,以处理生成的部分乘积。部分好处不仅仅是无序exec的并行依赖链,它能够在更接近它们生成的地方使用结果,这样你就不会用完寄存器(或需要额外的
mov
指令)来保存它们以供以后添加。或者在没有ADX指令的情况下,有时他们的示例会使用adc reg, 0
提前终止一个add/adc链,以便在执行另一个add
后重新开始。3yhwsihp3#
老问题,但补充Nils Pipenbrinck's答案,并响应Goswin von Brederlow的请求提供用法示例:
考虑以下C函数:
编译器可能会将此函数编译为:
这本身并不是一个优化;乱序执行可以使一个X1 M0 N1 X与另一个X1 M1 N1 X重叠,因为两个链都非常短。如果要添加多个非常大的整数,那么将工作与longer dependency chains进行交织可能会有一些好处,这些操作占CPU无序调度器大小的很大一部分(对于独立工作,可以提前查看未执行的uop的数量)。
如果您正在优化,您需要像
adcx r10, [rcx]
/adox r11, [rdx]
这样的内存源操作数,以便您可以使用更少的寄存器(不需要保存/恢复RSI和RDI)和更少的指令(避免一些单独的mov
加载)。因此,您可能会在每个ADCX和ADOX指令之间混合一个加载(可能还有一个存储)。我们在这里避免这样做只是为了说明的目的,所以uint 128值是在“明显的”对中,比如r9:r8而不是rax:r9或其他东西。除非数据来自其他操作,特别是BigInt乘法中的
mulx
,这是ADX指令的预期用例之一。在那里,你生成的数字需要在乘法时被相加,并且能够交错加法链有时可以避免为以后保存更多的数字,或者执行adc reg, 0
来应用进位并暂时结束一个链,或者用setc al
将进位具体化为0/1整数。(英特尔白皮书:New Instructions Supporting Large Integer Arithmetic .)