https://gcc.gnu.org/bugzilla/show_bug.cgi?id=128111
--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> --- Created attachment 65961 --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=65961&action=edit myclmul.c Quick benchmark I've used to check whether for _BitInt it is better to use the algorithm with Kronecker substitution, or naive O(n^2) loop, or an optimized version of the naive loop. The benchmark should be compiled with -O2 -DN=64 -DmN=m4 etc., where N says it is testing unsigned _BitInt(64) and mN selects the S spacing parameter (i.e. with S * S multiplications). For non-widening clmul (which this benchmark implements) N <= S * (1 << S). >From what I can see on my x86-64 box, when it can do multiplication natively, the Kronecker substitution clearly wins, for anything larger and especially towards the N=65535, the naive implementation is always slower than the Kronecker substitution, but the optimized naive one is fastest. The reason naive is slow is that it performs in one loop a shift right, then O(1) check of the least significant bit, then if that is non-zero one loop doing left shift and another doing the xor, while the optimized version just walks the limbs of one of the operands sequentially and in each limb tests sequentially all bits and then if non-zero, performs the ^= (x << i) operation together. So, for bitint lowering, I think I'm going to go for this.
