sparselocatephifunctions.go

// Copyright 2016 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 gc

import (
	"cmd/compile/internal/ssa"
	"fmt"
	"math"
)

// sparseDefState contains a Go map from ONAMEs (*Node) to sparse definition trees, and
// a search helper for the CFG's dominator tree in which those definitions are embedded.
// Once initialized, given a use of an ONAME within a block, the ssa definition for
// that ONAME can be discovered in time roughly proportional to the log of the number
// of SSA definitions of that ONAME (thus avoiding pathological quadratic behavior for
// very large programs).  The helper contains state (a dominator tree numbering) common
// to all the sparse definition trees, as well as some necessary data obtained from
// the ssa package.
//
// This algorithm has improved asymptotic complexity, but the constant factor is
// rather large and thus it is only preferred for very large inputs containing
// 1000s of blocks and variables.
type sparseDefState struct {
	helper         *ssa.SparseTreeHelper // contains one copy of information needed to do sparse mapping
	defmapForOname map[*Node]*onameDefs  // for each ONAME, its definition set (normal and phi)
}

// onameDefs contains a record of definitions (ordinary and implied phi function) for a single OName.
// stm is the set of definitions for the OName.
// firstdef and lastuse are postorder block numberings that
// conservatively bracket the entire lifetime of the OName.
type onameDefs struct {
	stm *ssa.SparseTreeMap
	// firstdef and lastuse define an interval in the postorder numbering
	// that is guaranteed to include the entire lifetime of an ONAME.
	// In the postorder numbering, math.MaxInt32 is before anything,
	// and 0 is after-or-equal all exit nodes and infinite loops.
	firstdef int32 // the first definition of this ONAME *in the postorder numbering*
	lastuse  int32 // the last use of this ONAME *in the postorder numbering*
}

// defsFor finds or creates-and-inserts-in-map the definition information
// (sparse tree and live range) for a given OName.
func (m *sparseDefState) defsFor(n *Node) *onameDefs {
	d := m.defmapForOname[n]
	if d != nil {
		return d
	}
	// Reminder: firstdef/lastuse are postorder indices, not block indices,
	// so these default values define an empty interval, not the entire one.
	d = &onameDefs{stm: m.helper.NewTree(), firstdef: 0, lastuse: math.MaxInt32}
	m.defmapForOname[n] = d
	return d
}

// Insert adds a definition at b (with specified before/within/after adjustment)
// to sparse tree onameDefs.  The lifetime is extended as necessary.
func (m *sparseDefState) Insert(tree *onameDefs, b *ssa.Block, adjust int32) {
	bponum := m.helper.Ponums[b.ID]
	if bponum > tree.firstdef {
		tree.firstdef = bponum
	}
	tree.stm.Insert(b, adjust, b, m.helper)
}

// Use updates tree to record a use within b, extending the lifetime as necessary.
func (m *sparseDefState) Use(tree *onameDefs, b *ssa.Block) {
	bponum := m.helper.Ponums[b.ID]
	if bponum < tree.lastuse {
		tree.lastuse = bponum
	}
}

// locatePotentialPhiFunctions finds all the places where phi functions
// will be inserted into a program and records those and ordinary definitions
// in a "map" (not a Go map) that given an OName and use site, returns the
// SSA definition for that OName that will reach the use site (that is,
// the use site's nearest def/phi site in the dominator tree.)
func (s *state) locatePotentialPhiFunctions(fn *Node) *sparseDefState {
	// s.config.SparsePhiCutoff() is compared with product of numblocks and numvalues,
	// if product is smaller than cutoff, use old non-sparse method.
	// cutoff == 0 implies all sparse
	// cutoff == uint(-1) implies all non-sparse
	if uint64(s.f.NumValues())*uint64(s.f.NumBlocks()) < s.config.SparsePhiCutoff() {
		return nil
	}

	helper := ssa.NewSparseTreeHelper(s.f)
	po := helper.Po // index by block.ID to obtain postorder # of block.
	trees := make(map[*Node]*onameDefs)
	dm := &sparseDefState{defmapForOname: trees, helper: helper}

	// Process params, taking note of their special lifetimes
	b := s.f.Entry
	for _, n := range fn.Func.Dcl {
		switch n.Class {
		case PPARAM, PPARAMOUT:
			t := dm.defsFor(n)
			dm.Insert(t, b, ssa.AdjustBefore) // define param at entry block
			if n.Class == PPARAMOUT {
				dm.Use(t, po[0]) // Explicitly use PPARAMOUT at very last block
			}
		default:
		}
	}

	// Process memory variable.
	t := dm.defsFor(&memVar)
	dm.Insert(t, b, ssa.AdjustBefore) // define memory at entry block
	dm.Use(t, po[0])                  // Explicitly use memory at last block

	// Next load the map w/ basic definitions for ONames recorded per-block
	// Iterate over po to avoid unreachable blocks.
	for i := len(po) - 1; i >= 0; i-- {
		b := po[i]
		m := s.defvars[b.ID]
		for n := range m { // no specified order, but per-node trees are independent.
			t := dm.defsFor(n)
			dm.Insert(t, b, ssa.AdjustWithin)
		}
	}

	// Find last use of each variable
	for _, v := range s.fwdRefs {
		b := v.Block
		name := v.Aux.(*Node)
		t := dm.defsFor(name)
		dm.Use(t, b)
	}

	for _, t := range trees {
		// iterating over names in the outer loop
		for change := true; change; {
			change = false
			for i := t.firstdef; i >= t.lastuse; i-- {
				// Iterating in reverse of post-order reduces number of 'change' iterations;
				// all possible forward flow goes through each time.
				b := po[i]
				// Within tree t, would a use at b require a phi function to ensure a single definition?
				// TODO: perhaps more efficient to record specific use sites instead of range?
				if len(b.Preds) < 2 {
					continue // no phi possible
				}
				phi := t.stm.Find(b, ssa.AdjustWithin, helper) // Look for defs in earlier block or AdjustBefore in this one.
				if phi != nil && phi.(*ssa.Block) == b {
					continue // has a phi already in this block.
				}
				var defseen interface{}
				// Do preds see different definitions? if so, need a phi function.
				for _, e := range b.Preds {
					p := e.Block()
					dm.Use(t, p)                                // always count phi pred as "use"; no-op except for loop edges, which matter.
					x := t.stm.Find(p, ssa.AdjustAfter, helper) // Look for defs reaching or within predecessors.
					if x == nil {                               // nil def from a predecessor means a backedge that will be visited soon.
						continue
					}
					if defseen == nil {
						defseen = x
					}
					if defseen != x {
						// Need to insert a phi function here because predecessors's definitions differ.
						change = true
						// Phi insertion is at AdjustBefore, visible with find in same block at AdjustWithin or AdjustAfter.
						dm.Insert(t, b, ssa.AdjustBefore)
						break
					}
				}
			}
		}
	}
	return dm
}

// FindBetterDefiningBlock tries to find a better block for a definition of OName name
// reaching (or within) p than p itself.  If it cannot, it returns p instead.
// This aids in more efficient location of phi functions, since it can skip over
// branch code that might contain a definition of name if it actually does not.
func (m *sparseDefState) FindBetterDefiningBlock(name *Node, p *ssa.Block) *ssa.Block {
	if m == nil {
		return p
	}
	t := m.defmapForOname[name]
	// For now this is fail-soft, since the old algorithm still works using the unimproved block.
	if t == nil {
		return p
	}
	x := t.stm.Find(p, ssa.AdjustAfter, m.helper)
	if x == nil {
		return p
	}
	b := x.(*ssa.Block)
	if b == nil {
		return p
	}
	return b
}

func (d *onameDefs) String() string {
	return fmt.Sprintf("onameDefs:first=%d,last=%d,tree=%s", d.firstdef, d.lastuse, d.stm.String())
}