cmd/compile/ssa: duplicate block elim

[josharian]

package p

func g_ssa(a, b int) int {
    if a < 5 {
        return 1
    }
    if b < 5 {
        return 1
    }
    return 0
}

At the end of the layout pass (chosen for readability--this remains true at the end of compilation), the SSA looks like:

g_ssa <nil>
  b1:
    v1 = Arg <mem> [.mem]
    v2 = FP <uint64>
    v18 = MOVQconst <int> [1]
    v22 = MOVQconst <int> [0]
    v28 = MOVQload <int> [0] v2 v1
    v32 = MOVQload <int> [8] v2 v1
    v24 = CMPQconst <flags> [5] v28
    v7 = MOVQstore <mem> [16] v2 v22 v1
    LT v24 -> b3 b4
  b3:
    v14 = MOVQstore <mem> [16] v2 v18 v7
    Plain -> b2
  b2:
    v29 = Phi <mem> v14 v21 v25
    Exit v29
  b4:
    v20 = CMPQconst <flags> [5] v32
    LT v20 -> b5 b6
  b5:
    v21 = MOVQstore <mem> [16] v2 v18 v7
    Plain -> b2
  b6:
    v25 = MOVQstore <mem> [16] v2 v22 v7
    Plain -> b2

Note that blocks b3 and b5 are effectively identical. One of them could be eliminated.

This happens fairly often in practice. For example, our generated equality code looks like:

func eq(a, b T) {
    if a.X != b.X {
        return false
    }
    if a.Y != b.Y {
        return false
    }
    return true
}

This ought to produce code that is just as efficient as:

func eq(a, b T) {
    return a.X == b.X && a.Y == b.Y
}

Right now it doesn't, but we can do better. There's also a lot of code in the compiler that looks like this. Also complex Less methods for sort.Interface.

Is this worth doing? Ought this to occur as part of an existing pass, or as a new one?

[randall77]

It might be worth doing. I have 2 hesitations:

1. How expensive would it be to detect this situation? Would you need to compute some hash of the block contents and then compare blocks with equal hashes? Maybe, but it seems hard to guarantee that there aren't too many collisions.
2. How do you decide what line number(s) the deduped block gets? It might affect performance sampling stack traces, for example. Maybe this isn't a terribly big deal, similar issues come up with inlining (which we already do).

[dr2chase]

We could use 64-bit numbers for our hashes, and use a good hash function, and collisions would be rather improbable. I am inclined to say that we should at least code this up, maybe as a separate pass right now so that we can turn it on and off and measure its effects. I have a bee in my bonnet to look into how we do stack traces already so that we can improve our inlining story (i.e., so we can inline functions that are not inlineable all-the-way-down) and perhaps we can also concoct some better way to talk about the line numbers of commoned code.

[josharian]

Oh, right. Line numbers are definitely a problem. Sigh. Thanks, @randall77.

@dr2chase inlining non-leaf functions could be a significant win, if you can figure out the stack trace / profiling / etc. story to everyone's satisfaction. See #4735 and #8421 and #9337 (comment).

Unless and until that gets figured out, I'm marking this as unplanned.

[randall77]

The hash is tricky, and not because of the hash function itself. Use SHA256 if you want. The trick is figuring out what data to hash.

Consider these two blocks:

b1:
v3 = Add v1 v2
v4 = Add [1] v3

b2:
v5 = Add v1 v2
v6 = Add [1] v5

What do I hash here? The blocks are equivalent, but the values aren't identical. Something simple like sorting and hashing the opcodes will work, but may have lots of false positives. We'd really like to hash the "dataflow" also, whatever that means. And even if the hashes match, determining equality isn't easy. This basically boils down to a graph isomorphism problem. We have the luxury of failing if it isn't obvious, but even so I don't think it is trivial.

[josharian]

cc @quasilyte -- is this a dup of your more recent work? If so, feel free to close it as wontfix.

[quasilyte]

I've used sequential (and naive) flow comparison, so different value names were handled.
This doesn't seem to affect performance that much if performed only on BlockRet that don't have unsafe (things that can panic) values.

The idea does sound like something I've tried to do in CL107895. For some functions, size reduction is great (can cut 20-25% of code), but for others it's close to zero. The main problem is effect on debug info (some discussion available at https://golang.org/issue/24936).