Yikes, good question. I thought about it for a bit:

Here's a toy example adding three-bit numbers, where all letters are bits (0 or 1) and you can normally only add one bit at a time.

      a b c
    + d e f
    -------
    g h i j

Instead of doing

    j = c ^ f
    j_carry = c & f
    i = j_carry ^ (b ^ e)

in two steps, we can condense it to

    j = c ^ f
    i = (c & f) ^ (b ^ e)

And similarly, we can get g and h combinationally from the input:

    #                   "j_carry AND one of b, e"
    i_carry = (b & e) | ( (c & f) & (b | e) )

    h = i_carry  ^ (a ^ d)
    h = ( (b & e) | ((c & f) & (b | e)) ) ^ (a ^ d)

    g = (a & d) | (i_carry & (a | d))
    g = (a & d) | ((b & e) | ( (c & f) & (b | e)) & (a | d))

So we end up directly computing

    g = (a & d) | ((b & e) | ( (c & f) & (b | e)) & (a | d))
    h = ( (b & e) | ((c & f) & (b | e)) ) ^ (a ^ d)
    i = (c & f) ^ (b ^ e)
    j = c ^ f

All of these innermost combinations like (a & d) you can get just by AND / OR of the original inputs.

But as you suggest (I think), then you need to combine these further to actually get results. In theory they're all parallelizable (if you picture this as tree), but I don't see a good way to do that quickly. Though I'm no assembly expert so maybe I'm missing something.

I guess thinking in terms of gate delays doesn't really help much at this abstraction level.