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>

1 files changed, 33 insertions, 3 deletions

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
 }