cmd/compile: improve domorder documentation

domorder has some non-obvious useful properties
that we’re relying on in cse.
Document them and provide an argument that they hold.
While we’re here, do some minor renaming.

The argument is a re-working of a private email
exchange with Todd Neal and David Chase.

Change-Id: Ie154e0521bde642f5f11e67fc542c5eb938258be
Reviewed-on: https://go-review.googlesource.com/23449
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Keith Randall <khr@golang.org>

2 files changed, 41 insertions, 14 deletions

diff --git a/src/cmd/compile/internal/ssa/cse.go b/src/cmd/compile/internal/ssa/cse.go
index 20ea45ab3e..ad4e416159 100644
--- a/src/cmd/compile/internal/ssa/cse.go
+++ b/src/cmd/compile/internal/ssa/cse.go
@@ -137,10 +137,9 @@ func cse(f *Func) {
 	// if v and w are in the same equivalence class and v dominates w.
 	rewrite := make([]*Value, f.NumValues())
 	for _, e := range partition {
-		sort.Sort(sortbyentry{e, f.sdom})
+		sort.Sort(partitionByDom{e, f.sdom})
 		for i := 0; i < len(e)-1; i++ {
-			// e is sorted by entry value so maximal dominant element should be
-			// found first in the slice
+			// e is sorted by domorder, so a maximal dominant element is first in the slice
 			v := e[i]
 			if v == nil {
 				continue
@@ -157,9 +156,7 @@ func cse(f *Func) {
 					rewrite[w.ID] = v
 					e[j] = nil
 				} else {
-					// since the blocks are assorted in ascending order by entry number
-					// once we know that we don't dominate a block we can't dominate any
-					// 'later' block
+					// e is sorted by domorder, so v.Block doesn't dominate any subsequent blocks in e
 					break
 				}
 			}
@@ -311,15 +308,15 @@ func (sv sortvalues) Less(i, j int) bool {
 	return v.ID < w.ID
 }
 
-type sortbyentry struct {
+type partitionByDom struct {
 	a    []*Value // array of values
 	sdom SparseTree
 }
 
-func (sv sortbyentry) Len() int      { return len(sv.a) }
-func (sv sortbyentry) Swap(i, j int) { sv.a[i], sv.a[j] = sv.a[j], sv.a[i] }
-func (sv sortbyentry) Less(i, j int) bool {
+func (sv partitionByDom) Len() int      { return len(sv.a) }
+func (sv partitionByDom) Swap(i, j int) { sv.a[i], sv.a[j] = sv.a[j], sv.a[i] }
+func (sv partitionByDom) Less(i, j int) bool {
 	v := sv.a[i]
 	w := sv.a[j]
-	return sv.sdom.maxdomorder(v.Block) < sv.sdom.maxdomorder(w.Block)
+	return sv.sdom.domorder(v.Block) < sv.sdom.domorder(w.Block)
 }
diff --git a/src/cmd/compile/internal/ssa/sparsetree.go b/src/cmd/compile/internal/ssa/sparsetree.go
index 21fe68601e..7c82a60d0f 100644
--- a/src/cmd/compile/internal/ssa/sparsetree.go
+++ b/src/cmd/compile/internal/ssa/sparsetree.go
@@ -149,8 +149,38 @@ func (t SparseTree) isAncestor(x, y *Block) bool {
 	return xx.entry < yy.entry && yy.exit < xx.exit
 }
 
-// maxdomorder returns a value to allow a maximal dominator first sort.  maxdomorder(x) < maxdomorder(y) is true
-// if x may dominate y, and false if x cannot dominate y.
-func (t SparseTree) maxdomorder(x *Block) int32 {
+// domorder returns a value for dominator-oriented sorting.
+// Block domination does not provide a total ordering,
+// but domorder two has useful properties.
+// (1) If domorder(x) > domorder(y) then x does not dominate y.
+// (2) If domorder(x) < domorder(y) and domorder(y) < domorder(z) and x does not dominate y,
+//     then x does not dominate z.
+// Property (1) means that blocks sorted by domorder always have a maximal dominant block first.
+// Property (2) allows searches for dominated blocks to exit early.
+func (t SparseTree) domorder(x *Block) int32 {
+	// Here is an argument that entry(x) provides the properties documented above.
+	//
+	// Entry and exit values are assigned in a depth-first dominator tree walk.
+	// For all blocks x and y, one of the following holds:
+	//
+	// (x-dom-y) x dominates y => entry(x) < entry(y) < exit(y) < exit(x)
+	// (y-dom-x) y dominates x => entry(y) < entry(x) < exit(x) < exit(y)
+	// (x-then-y) neither x nor y dominates the other and x walked before y => entry(x) < exit(x) < entry(y) < exit(y)
+	// (y-then-x) neither x nor y dominates the other and y walked before y => entry(y) < exit(y) < entry(x) < exit(x)
+	//
+	// entry(x) > entry(y) eliminates case x-dom-y. This provides property (1) above.
+	//
+	// For property (2), assume entry(x) < entry(y) and entry(y) < entry(z) and x does not dominate y.
+	// entry(x) < entry(y) allows cases x-dom-y and x-then-y.
+	// But by supposition, x does not dominate y. So we have x-then-y.
+	//
+	// For contractidion, assume x dominates z.
+	// Then entry(x) < entry(z) < exit(z) < exit(x).
+	// But we know x-then-y, so entry(x) < exit(x) < entry(y) < exit(y).
+	// Combining those, entry(x) < entry(z) < exit(z) < exit(x) < entry(y) < exit(y).
+	// By supposition, entry(y) < entry(z), which allows cases y-dom-z and y-then-z.
+	// y-dom-z requires entry(y) < entry(z), but we have entry(z) < entry(y).
+	// y-then-z requires exit(y) < entry(z), but we have entry(z) < exit(y).
+	// We have a contradiction, so x does not dominate z, as required.
 	return t[x.ID].entry
 }