dominator.go

// Copyright 2018 The Go Authors.  All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package gocore

import (
	"fmt"
	"io"
)

// Code liberally adapted from cmd/compile/internal/ssa/dom.go and
// x/tools/go/ssa/dom.go.
//
// We use the algorithm described in Lengauer & Tarjan. 1979.  A fast
// algorithm for finding dominators in a flowgraph.
// http://doi.acm.org/10.1145/357062.357071
//
// We also apply the optimizations to SLT described in Georgiadis et
// al, Finding Dominators in Practice, JGAA 2006,
// http://jgaa.info/accepted/2006/GeorgiadisTarjanWerneck2006.10.1.pdf
// to avoid the need for buckets of size > 1.

// Vertex name, as used in the papers.
// 0 -> the pseudo-root, a made-up object that parents all the GC roots.
// 1...nRoots -> a root, found at p.rootIdx[#-1]
// nRoots+1... -> an object, with object index # - nRoots - 1
type vName int

const pseudoRoot vName = 0

// Vertex number, assigned in the DFS traversal in step 1.
type vNumber int

type ltDom struct {
	p *Process

	// mapping from object ID to object
	objs []Object

	// number -> name
	vertices []vName

	// name -> parent name
	parents []vName

	// name -> vertex number before step 2 or semidominator number after.
	semis []vNumber

	// name -> ancestor name
	ancestor []vName
	labels   []vName

	// name -> dominator name
	idom []vName

	nVertices, nRoots int
}

type dominators struct {
	p *Process

	// mapping from object ID to object
	objs []Object

	// name -> dominator name
	idom []vName

	// Reverse dominator tree edges, stored just like the ones in Process. name -> child name.
	ridx  []int
	redge []vName

	// Retained size for each vertex. name -> retained size.
	size []int64
}

func (p *Process) calculateDominators() *dominators {
	lt := runLT(p)
	d := dominators{p: p, idom: lt.idom, objs: lt.objs}
	lt = ltDom{}

	d.reverse()
	d.calcSize(p)

	return &d
}

func runLT(p *Process) ltDom {
	p.typeHeap()
	p.reverseEdges()

	nVertices := 1 + len(p.rootIdx) + p.nObj
	lt := ltDom{
		p:         p,
		nRoots:    len(p.rootIdx),
		nVertices: nVertices,
		objs:      make([]Object, p.nObj),
		vertices:  make([]vName, nVertices),
		parents:   make([]vName, nVertices),
		semis:     make([]vNumber, nVertices),
		ancestor:  make([]vName, nVertices),
		labels:    make([]vName, nVertices),
		idom:      make([]vName, nVertices),
	}
	// TODO: increment all the names and use 0 as the uninitialized value.
	for i := range lt.semis {
		lt.semis[i] = -1
	}
	for i := range lt.ancestor {
		lt.ancestor[i] = -1
	}
	for i := range lt.labels {
		lt.labels[i] = vName(i)
	}
	lt.initialize()
	lt.calculate()
	return lt
}

// initialize implements step 1 of LT.
func (d *ltDom) initialize() {
	type workItem struct {
		name       vName
		parentName vName
	}

	// Initialize objs for mapping from object index back to Object.
	i := 0
	d.p.ForEachObject(func(x Object) bool {
		d.objs[i] = x
		i++
		return true
	})

	// Add roots to the work stack, essentially pretending to visit
	// the pseudo-root, numbering it 0.
	d.semis[pseudoRoot] = 0
	d.parents[pseudoRoot] = -1
	d.vertices[0] = pseudoRoot
	var work []workItem
	for i := 1; i < 1+d.nRoots; i++ {
		work = append(work, workItem{name: vName(i), parentName: 0})
	}

	n := vNumber(1) // 0 was the pseudo-root.

	// Build the spanning tree, assigning vertex numbers to each object
	// and initializing semi and parent.
	for len(work) != 0 {
		item := work[len(work)-1]
		work = work[:len(work)-1]

		if d.semis[item.name] != -1 {
			continue
		}

		d.semis[item.name] = n
		d.parents[item.name] = item.parentName
		d.vertices[n] = item.name
		n++

		visitChild := func(_ int64, child Object, _ int64) bool {
			childIdx, _ := d.p.findObjectIndex(d.p.Addr(child))
			work = append(work, workItem{name: vName(childIdx + d.nRoots + 1), parentName: item.name})
			return true
		}

		root, object := d.findVertexByName(item.name)
		if root != nil {
			d.p.ForEachRootPtr(root, visitChild)
		} else {
			d.p.ForEachPtr(object, visitChild)
		}

	}
}

// findVertexByName returns the root/object named by n, or nil,0 for the pseudo-root.
func (d *ltDom) findVertexByName(n vName) (*Root, Object) {
	if n == 0 {
		return nil, 0
	}
	if int(n) < len(d.p.rootIdx)+1 {
		return d.p.rootIdx[n-1], 0
	}
	return nil, d.objs[int(n)-len(d.p.rootIdx)-1]
}
func (d *dominators) findVertexByName(n vName) (*Root, Object) {
	if n == 0 {
		return nil, 0
	}
	if int(n) < len(d.p.rootIdx)+1 {
		return d.p.rootIdx[n-1], 0
	}
	return nil, d.objs[int(n)-len(d.p.rootIdx)-1]
}

// calculate runs the main part of LT.
func (d *ltDom) calculate() {
	// name -> bucket (a name), per Georgiadis.
	buckets := make([]vName, d.nVertices)
	for i := range buckets {
		buckets[i] = vName(i)
	}

	for i := vNumber(len(d.vertices)) - 1; i > 0; i-- {
		w := d.vertices[i]

		// Step 3. Implicitly define the immediate dominator of each node.
		for v := buckets[w]; v != w; v = buckets[v] {
			u := d.eval(v)
			if d.semis[u] < d.semis[v] {
				d.idom[v] = u
			} else {
				d.idom[v] = w
			}
		}

		// Step 2. Compute the semidominators of all nodes.
		root, obj := d.findVertexByName(w)
		// This loop never visits the pseudo-root.
		if root != nil {
			u := d.eval(pseudoRoot)
			if d.semis[u] < d.semis[w] {
				d.semis[w] = d.semis[u]
			}
		} else {
			d.p.ForEachReversePtr(obj, func(x Object, r *Root, _, _ int64) bool {
				var v int
				if r != nil {
					v = d.p.findRootIndex(r) + 1
				} else {
					v, _ = d.p.findObjectIndex(d.p.Addr(x))
					v += d.nRoots + 1
				}
				u := d.eval(vName(v))
				if d.semis[u] < d.semis[w] {
					d.semis[w] = d.semis[u]
				}
				return true
			})
		}

		d.link(d.parents[w], w)

		if d.parents[w] == d.vertices[d.semis[w]] {
			d.idom[w] = d.parents[w]
		} else {
			buckets[w] = buckets[d.vertices[d.semis[w]]]
			buckets[d.vertices[d.semis[w]]] = w
		}
	}

	// The final 'Step 3' is now outside the loop.
	for v := buckets[pseudoRoot]; v != pseudoRoot; v = buckets[v] {
		d.idom[v] = pseudoRoot
	}

	// Step 4. Explicitly define the immediate dominator of each
	// node, in preorder.
	for _, w := range d.vertices[1:] {
		if d.idom[w] != d.vertices[d.semis[w]] {
			d.idom[w] = d.idom[d.idom[w]]
		}
	}
}

// eval is EVAL from the papers.
func (d *ltDom) eval(v vName) vName {
	if d.ancestor[v] == -1 {
		return v
	}
	d.compress(v)
	return d.labels[v]
}

// compress is COMPRESS from the papers.
func (d *ltDom) compress(v vName) {
	var stackBuf [20]vName
	stack := stackBuf[:0]
	for d.ancestor[d.ancestor[v]] != -1 {
		stack = append(stack, v)
		v = d.ancestor[v]
	}

	for len(stack) != 0 {
		v := stack[len(stack)-1]
		stack = stack[:len(stack)-1]

		if d.semis[d.labels[d.ancestor[v]]] < d.semis[d.labels[v]] {
			d.labels[v] = d.labels[d.ancestor[v]]
		}
		d.ancestor[v] = d.ancestor[d.ancestor[v]]
	}
}

// link is LINK from the papers.
func (d *ltDom) link(v, w vName) {
	d.ancestor[w] = v
}

// reverse computes and stores reverse edges for each vertex.
func (d *dominators) reverse() {
	// One inbound edge per vertex. Then we need an extra so that you can
	// always look at ridx[i+1], and another for working storage while
	// populating redge.
	cnt := make([]int, len(d.idom)+2)

	// Fill cnt[2:] with the number of outbound edges for each vertex.
	tmp := cnt[2:]
	for _, idom := range d.idom {
		tmp[idom]++
	}

	// Make tmp cumulative. After this step, cnt[1:] is what we want for
	// ridx, but the next step messes it up.
	var n int
	for idx, c := range tmp {
		n += c
		tmp[idx] = n
	}

	// Store outbound edges in redge, using cnt[1:] as the index to store
	// the next edge for each vertex. After we're done, everything's been
	// shifted over one, and cnt is ridx.
	redge := make([]vName, len(d.idom))
	tmp = cnt[1:]
	for i, idom := range d.idom {
		redge[tmp[idom]] = vName(i)
		tmp[idom]++
	}
	d.redge, d.ridx = redge, cnt[:len(cnt)-1]
}

type dfsMode int

const (
	down dfsMode = iota
	up
)

// calcSize calculates the total retained size for each vertex.
func (d *dominators) calcSize(p *Process) {
	d.size = make([]int64, len(d.idom))
	type workItem struct {
		v    vName
		mode dfsMode
	}
	work := []workItem{{pseudoRoot, down}}

	for len(work) > 0 {
		item := &work[len(work)-1]

		kids := d.redge[d.ridx[item.v]:d.ridx[item.v+1]]
		if item.mode == down && len(kids) != 0 {
			item.mode = up
			for _, w := range kids {
				if w == 0 {
					// bogus self-edge. Ignore.
					continue
				}
				work = append(work, workItem{w, down})
			}
			continue
		}

		work = work[:len(work)-1]

		root, obj := d.findVertexByName(item.v)
		var size int64
		switch {
		case item.v == pseudoRoot:
			break
		case root != nil:
			size += root.Type.Size
		default:
			size += p.Size(obj)
		}
		for _, w := range kids {
			size += d.size[w]
		}
		d.size[item.v] = size
	}
}

func (d *ltDom) dot(w io.Writer) {
	fmt.Fprintf(w, "digraph %s {\nrankdir=\"LR\"\n", "dominators")
	for number, name := range d.vertices {
		var label string
		root, obj := d.findVertexByName(name)

		switch {
		case name == 0:
			label = "pseudo-root"
		case root != nil:
			typeName := root.Type.Name
			if len(typeName) > 30 {
				typeName = typeName[:30]
			}
			label = fmt.Sprintf("root %s %#x (type %s)", root.Name, root.Addr, typeName)
		default:
			typ, _ := d.p.Type(obj)
			var typeName string
			if typ != nil {
				typeName = typ.Name
				if len(typeName) > 30 {
					typeName = typeName[:30]
				}
			}
			label = fmt.Sprintf("object %#x (type %s)", obj, typeName)
		}

		fmt.Fprintf(w, "\t%v [label=\"name #%04v, number #%04v: %s\"]\n", name, name, number, label)
	}

	fmt.Fprint(w, "\n\n")
	for v, parent := range d.parents {
		fmt.Fprintf(w, "\t%v -> %v [style=\"solid\"]\n", parent, v)
	}
	for v, idom := range d.idom {
		fmt.Fprintf(w, "\t%v -> %v [style=\"bold\"]\n", idom, v)
	}
	for v, sdom := range d.semis {
		fmt.Fprintf(w, "\t%v -> %v [style=\"dotted\"]\n", v, d.vertices[sdom])
	}
	fmt.Fprint(w, "}\n")
}