cmd/compile: lay out exit post-dominated blocks at the end

Complete a long-standing TODO in the code.

Exit blocks are cold code, so we lay them out at the end of the function.
Blocks that are post-dominated by exit blocks are also ipso facto exit blocks.
Treat them as such.

Implement using a simple loop, because there are generally very few exit blocks.

In addition to improved instruction cache, this empirically yields
better register allocation.

Binary size impact:

file    before    after     Δ       %       
cgo     4812872   4808776   -4096   -0.085% 
fix     3370072   3365976   -4096   -0.122% 
vet     8252280   8248184   -4096   -0.050% 
total   115052984 115040696 -12288  -0.011% 

This also appears to improve compiler performance
(-0.15% geomean time/op, -1.20% geomean user time/op),
but that could just be alignment effects.
Compiler benchmarking hasn't been super reliably recently,
and there's no particular reason to think this should
speed up the compiler that much.

Change-Id: I3d262c4f5cb80626a67a5c17285e2fa09f423c00
Reviewed-on: https://go-review.googlesource.com/c/go/+/227217
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: David Chase <drchase@google.com>

1 files changed, 34 insertions, 3 deletions

diff --git a/src/cmd/compile/internal/ssa/layout.go b/src/cmd/compile/internal/ssa/layout.go
index 338cd91c47..30b7b97d04 100644
--- a/src/cmd/compile/internal/ssa/layout.go
+++ b/src/cmd/compile/internal/ssa/layout.go
@@ -46,13 +46,44 @@ func layoutOrder(f *Func) []*Block {
 	exit := f.newSparseSet(f.NumBlocks()) // exit blocks
 	defer f.retSparseSet(exit)
 
-	// Initialize indegree of each block
+	// Populate idToBlock and find exit blocks.
 	for _, b := range f.Blocks {
 		idToBlock[b.ID] = b
 		if b.Kind == BlockExit {
-			// exit blocks are always scheduled last
-			// TODO: also add blocks post-dominated by exit blocks
 			exit.add(b.ID)
+		}
+	}
+
+	// Expand exit to include blocks post-dominated by exit blocks.
+	for {
+		changed := false
+		for _, id := range exit.contents() {
+			b := idToBlock[id]
+		NextPred:
+			for _, pe := range b.Preds {
+				p := pe.b
+				if exit.contains(p.ID) {
+					continue
+				}
+				for _, s := range p.Succs {
+					if !exit.contains(s.b.ID) {
+						continue NextPred
+					}
+				}
+				// All Succs are in exit; add p.
+				exit.add(p.ID)
+				changed = true
+			}
+		}
+		if !changed {
+			break
+		}
+	}
+
+	// Initialize indegree of each block
+	for _, b := range f.Blocks {
+		if exit.contains(b.ID) {
+			// exit blocks are always scheduled last
 			continue
 		}
 		indegree[b.ID] = len(b.Preds)