https://gcc.gnu.org/bugzilla/show_bug.cgi?id=128111
--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> --- Unfortunately I got the math wrong, the 4-bit splices Kronecker substitution algorithm is safe only for up to 64x64->64 bit for the non-widening ones and for up to 60x60->120 bit for the widening ones. For up to 24x24->24 bit for non-widening ones and for up to 21x21->42 bits for widening ones we could on the other side use just 3-bit splices and only 9 multiplications instead of 16. Generally for NxN->N clmul we need splice S such that N<=S(2^S) and for NxN->2N clmul we need splice S such that N<=S((2^S)-1). So 5-bit splices and 25 multiplications can do up to 160x160->160 or 155x155->310. That said, if the two arguments have different get_min_precision, I think we only care about the smaller of the two precisions but if the result needs more than twice that many bits, we still need to use N<=S((2^S)-1) because we care about more bits of the result than half of the min precision. For NxN->2N clmul using NxN->N clmul we can use clmul(x,y) for lowpart and bitreverse(clmul(bitreverse(x),bitreverse(y)))>>1 as hipart. Guess wide-int.cc should just use the naive algorithm, for software emulated multiplication it doesn't improve that much anyway. And will need to figure out what to do for _BitInt lowering (or whether to handle it in libgcc and use there some recursive algorithm or something similar).
