popt.go

// Derived from Inferno utils/6c/gc.h
// http://code.google.com/p/inferno-os/source/browse/utils/6c/gc.h
//
//	Copyright © 1994-1999 Lucent Technologies Inc.  All rights reserved.
//	Portions Copyright © 1995-1997 C H Forsyth (forsyth@terzarima.net)
//	Portions Copyright © 1997-1999 Vita Nuova Limited
//	Portions Copyright © 2000-2007 Vita Nuova Holdings Limited (www.vitanuova.com)
//	Portions Copyright © 2004,2006 Bruce Ellis
//	Portions Copyright © 2005-2007 C H Forsyth (forsyth@terzarima.net)
//	Revisions Copyright © 2000-2007 Lucent Technologies Inc. and others
//	Portions Copyright © 2009 The Go Authors.  All rights reserved.
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.

// "Portable" optimizations.

package gc

import (
	"cmd/internal/obj"
	"fmt"
	"sort"
	"strings"
)

type OptStats struct {
	Ncvtreg int32
	Nspill  int32
	Nreload int32
	Ndelmov int32
	Nvar    int32
	Naddr   int32
}

var Ostats OptStats

var noreturn_symlist [10]*Sym

// p is a call instruction. Does the call fail to return?
func Noreturn(p *obj.Prog) bool {
	if noreturn_symlist[0] == nil {
		noreturn_symlist[0] = Pkglookup("panicindex", Runtimepkg)
		noreturn_symlist[1] = Pkglookup("panicslice", Runtimepkg)
		noreturn_symlist[2] = Pkglookup("throwinit", Runtimepkg)
		noreturn_symlist[3] = Pkglookup("gopanic", Runtimepkg)
		noreturn_symlist[4] = Pkglookup("panicwrap", Runtimepkg)
		noreturn_symlist[5] = Pkglookup("throwreturn", Runtimepkg)
		noreturn_symlist[6] = Pkglookup("selectgo", Runtimepkg)
		noreturn_symlist[7] = Pkglookup("block", Runtimepkg)
	}

	if p.To.Node == nil {
		return false
	}
	s := ((p.To.Node).(*Node)).Sym
	if s == nil {
		return false
	}
	for i := 0; noreturn_symlist[i] != nil; i++ {
		if s == noreturn_symlist[i] {
			return true
		}
	}
	return false
}

// JMP chasing and removal.
//
// The code generator depends on being able to write out jump
// instructions that it can jump to now but fill in later.
// the linker will resolve them nicely, but they make the code
// longer and more difficult to follow during debugging.
// Remove them.

// what instruction does a JMP to p eventually land on?
func chasejmp(p *obj.Prog, jmploop *int) *obj.Prog {
	n := 0
	for p != nil && p.As == obj.AJMP && p.To.Type == obj.TYPE_BRANCH {
		n++
		if n > 10 {
			*jmploop = 1
			break
		}

		p = p.To.Val.(*obj.Prog)
	}

	return p
}

// reuse reg pointer for mark/sweep state.
// leave reg==nil at end because alive==nil.
var alive interface{} = nil
var dead interface{} = 1

// mark all code reachable from firstp as alive
func mark(firstp *obj.Prog) {
	for p := firstp; p != nil; p = p.Link {
		if p.Opt != dead {
			break
		}
		p.Opt = alive
		if p.As != obj.ACALL && p.To.Type == obj.TYPE_BRANCH && p.To.Val.(*obj.Prog) != nil {
			mark(p.To.Val.(*obj.Prog))
		}
		if p.As == obj.AJMP || p.As == obj.ARET || p.As == obj.AUNDEF {
			break
		}
	}
}

func fixjmp(firstp *obj.Prog) {
	if Debug['R'] != 0 && Debug['v'] != 0 {
		fmt.Printf("\nfixjmp\n")
	}

	// pass 1: resolve jump to jump, mark all code as dead.
	jmploop := 0

	for p := firstp; p != nil; p = p.Link {
		if Debug['R'] != 0 && Debug['v'] != 0 {
			fmt.Printf("%v\n", p)
		}
		if p.As != obj.ACALL && p.To.Type == obj.TYPE_BRANCH && p.To.Val.(*obj.Prog) != nil && p.To.Val.(*obj.Prog).As == obj.AJMP {
			p.To.Val = chasejmp(p.To.Val.(*obj.Prog), &jmploop)
			if Debug['R'] != 0 && Debug['v'] != 0 {
				fmt.Printf("->%v\n", p)
			}
		}

		p.Opt = dead
	}

	if Debug['R'] != 0 && Debug['v'] != 0 {
		fmt.Printf("\n")
	}

	// pass 2: mark all reachable code alive
	mark(firstp)

	// pass 3: delete dead code (mostly JMPs).
	var last *obj.Prog

	for p := firstp; p != nil; p = p.Link {
		if p.Opt == dead {
			if p.Link == nil && p.As == obj.ARET && last != nil && last.As != obj.ARET {
				// This is the final ARET, and the code so far doesn't have one.
				// Let it stay. The register allocator assumes that all live code in
				// the function can be traversed by starting at all the RET instructions
				// and following predecessor links. If we remove the final RET,
				// this assumption will not hold in the case of an infinite loop
				// at the end of a function.
				// Keep the RET but mark it dead for the liveness analysis.
				p.Mode = 1
			} else {
				if Debug['R'] != 0 && Debug['v'] != 0 {
					fmt.Printf("del %v\n", p)
				}
				continue
			}
		}

		if last != nil {
			last.Link = p
		}
		last = p
	}

	last.Link = nil

	// pass 4: elide JMP to next instruction.
	// only safe if there are no jumps to JMPs anymore.
	if jmploop == 0 {
		var last *obj.Prog
		for p := firstp; p != nil; p = p.Link {
			if p.As == obj.AJMP && p.To.Type == obj.TYPE_BRANCH && p.To.Val == p.Link {
				if Debug['R'] != 0 && Debug['v'] != 0 {
					fmt.Printf("del %v\n", p)
				}
				continue
			}

			if last != nil {
				last.Link = p
			}
			last = p
		}

		last.Link = nil
	}

	if Debug['R'] != 0 && Debug['v'] != 0 {
		fmt.Printf("\n")
		for p := firstp; p != nil; p = p.Link {
			fmt.Printf("%v\n", p)
		}
		fmt.Printf("\n")
	}
}

// Control flow analysis. The Flow structures hold predecessor and successor
// information as well as basic loop analysis.
//
//	graph = flowstart(firstp, 0);
//	... use flow graph ...
//	flowend(graph); // free graph
//
// Typical uses of the flow graph are to iterate over all the flow-relevant instructions:
//
//	for(f = graph->start; f != nil; f = f->link)
//
// or, given an instruction f, to iterate over all the predecessors, which is
// f->p1 and this list:
//
//	for(f2 = f->p2; f2 != nil; f2 = f2->p2link)
//
// The size argument to flowstart specifies an amount of zeroed memory
// to allocate in every f->data field, for use by the client.
// If size == 0, f->data will be nil.

var flowmark int

// MaxFlowProg is the maximum size program (counted in instructions)
// for which the flow code will build a graph. Functions larger than this limit
// will not have flow graphs and consequently will not be optimized.
const MaxFlowProg = 50000

func Flowstart(firstp *obj.Prog, newData func() interface{}) *Graph {
	// Count and mark instructions to annotate.
	nf := 0

	for p := firstp; p != nil; p = p.Link {
		p.Opt = nil // should be already, but just in case
		Thearch.Proginfo(p)
		if p.Info.Flags&Skip != 0 {
			continue
		}
		p.Opt = &flowmark
		nf++
	}

	if nf == 0 {
		return nil
	}

	if nf >= MaxFlowProg {
		if Debug['v'] != 0 {
			Warn("%v is too big (%d instructions)", Curfn.Func.Nname.Sym, nf)
		}
		return nil
	}

	// Allocate annotations and assign to instructions.
	graph := new(Graph)
	ff := make([]Flow, nf)
	start := &ff[0]
	id := 0
	var last *Flow
	for p := firstp; p != nil; p = p.Link {
		if p.Opt == nil {
			continue
		}
		f := &ff[0]
		ff = ff[1:]
		p.Opt = f
		f.Prog = p
		if last != nil {
			last.Link = f
		}
		last = f
		if newData != nil {
			f.Data = newData()
		}
		f.Id = int32(id)
		id++
	}

	// Fill in pred/succ information.
	var f1 *Flow
	var p *obj.Prog
	for f := start; f != nil; f = f.Link {
		p = f.Prog
		if p.Info.Flags&Break == 0 {
			f1 = f.Link
			f.S1 = f1
			f1.P1 = f
		}

		if p.To.Type == obj.TYPE_BRANCH {
			if p.To.Val == nil {
				Fatalf("pnil %v", p)
			}
			f1 = p.To.Val.(*obj.Prog).Opt.(*Flow)
			if f1 == nil {
				Fatalf("fnil %v / %v", p, p.To.Val.(*obj.Prog))
			}
			if f1 == f {
				//fatal("self loop %v", p);
				continue
			}

			f.S2 = f1
			f.P2link = f1.P2
			f1.P2 = f
		}
	}

	graph.Start = start
	graph.Num = nf
	return graph
}

func Flowend(graph *Graph) {
	for f := graph.Start; f != nil; f = f.Link {
		f.Prog.Info.Flags = 0 // drop cached proginfo
		f.Prog.Opt = nil
	}
}

// find looping structure
//
// 1) find reverse postordering
// 2) find approximate dominators,
//	the actual dominators if the flow graph is reducible
//	otherwise, dominators plus some other non-dominators.
//	See Matthew S. Hecht and Jeffrey D. Ullman,
//	"Analysis of a Simple Algorithm for Global Data Flow Problems",
//	Conf.  Record of ACM Symp. on Principles of Prog. Langs, Boston, Massachusetts,
//	Oct. 1-3, 1973, pp.  207-217.
// 3) find all nodes with a predecessor dominated by the current node.
//	such a node is a loop head.
//	recursively, all preds with a greater rpo number are in the loop
func postorder(r *Flow, rpo2r []*Flow, n int32) int32 {
	r.Rpo = 1
	r1 := r.S1
	if r1 != nil && r1.Rpo == 0 {
		n = postorder(r1, rpo2r, n)
	}
	r1 = r.S2
	if r1 != nil && r1.Rpo == 0 {
		n = postorder(r1, rpo2r, n)
	}
	rpo2r[n] = r
	n++
	return n
}

func rpolca(idom []int32, rpo1 int32, rpo2 int32) int32 {
	if rpo1 == -1 {
		return rpo2
	}
	var t int32
	for rpo1 != rpo2 {
		if rpo1 > rpo2 {
			t = rpo2
			rpo2 = rpo1
			rpo1 = t
		}

		for rpo1 < rpo2 {
			t = idom[rpo2]
			if t >= rpo2 {
				Fatalf("bad idom")
			}
			rpo2 = t
		}
	}

	return rpo1
}

func doms(idom []int32, r int32, s int32) bool {
	for s > r {
		s = idom[s]
	}
	return s == r
}

func loophead(idom []int32, r *Flow) bool {
	src := r.Rpo
	if r.P1 != nil && doms(idom, src, r.P1.Rpo) {
		return true
	}
	for r = r.P2; r != nil; r = r.P2link {
		if doms(idom, src, r.Rpo) {
			return true
		}
	}
	return false
}

func loopmark(rpo2r **Flow, head int32, r *Flow) {
	if r.Rpo < head || r.Active == head {
		return
	}
	r.Active = head
	r.Loop += LOOP
	if r.P1 != nil {
		loopmark(rpo2r, head, r.P1)
	}
	for r = r.P2; r != nil; r = r.P2link {
		loopmark(rpo2r, head, r)
	}
}

func flowrpo(g *Graph) {
	g.Rpo = make([]*Flow, g.Num)
	idom := make([]int32, g.Num)

	for r1 := g.Start; r1 != nil; r1 = r1.Link {
		r1.Active = 0
	}

	rpo2r := g.Rpo
	d := postorder(g.Start, rpo2r, 0)
	nr := int32(g.Num)
	if d > nr {
		Fatalf("too many reg nodes %d %d", d, nr)
	}
	nr = d
	var r1 *Flow
	for i := int32(0); i < nr/2; i++ {
		r1 = rpo2r[i]
		rpo2r[i] = rpo2r[nr-1-i]
		rpo2r[nr-1-i] = r1
	}

	for i := int32(0); i < nr; i++ {
		rpo2r[i].Rpo = i
	}

	idom[0] = 0
	var me int32
	for i := int32(0); i < nr; i++ {
		r1 = rpo2r[i]
		me = r1.Rpo
		d = -1

		// rpo2r[r->rpo] == r protects against considering dead code,
		// which has r->rpo == 0.
		if r1.P1 != nil && rpo2r[r1.P1.Rpo] == r1.P1 && r1.P1.Rpo < me {
			d = r1.P1.Rpo
		}
		for r1 = r1.P2; r1 != nil; r1 = r1.P2link {
			if rpo2r[r1.Rpo] == r1 && r1.Rpo < me {
				d = rpolca(idom, d, r1.Rpo)
			}
		}
		idom[i] = d
	}

	for i := int32(0); i < nr; i++ {
		r1 = rpo2r[i]
		r1.Loop++
		if r1.P2 != nil && loophead(idom, r1) {
			loopmark(&rpo2r[0], i, r1)
		}
	}

	for r1 := g.Start; r1 != nil; r1 = r1.Link {
		r1.Active = 0
	}
}

func Uniqp(r *Flow) *Flow {
	r1 := r.P1
	if r1 == nil {
		r1 = r.P2
		if r1 == nil || r1.P2link != nil {
			return nil
		}
	} else if r.P2 != nil {
		return nil
	}
	return r1
}

func Uniqs(r *Flow) *Flow {
	r1 := r.S1
	if r1 == nil {
		r1 = r.S2
		if r1 == nil {
			return nil
		}
	} else if r.S2 != nil {
		return nil
	}
	return r1
}

// The compilers assume they can generate temporary variables
// as needed to preserve the right semantics or simplify code
// generation and the back end will still generate good code.
// This results in a large number of ephemeral temporary variables.
// Merge temps with non-overlapping lifetimes and equal types using the
// greedy algorithm in Poletto and Sarkar, "Linear Scan Register Allocation",
// ACM TOPLAS 1999.

type TempVar struct {
	node    *Node
	def     *Flow    // definition of temp var
	use     *Flow    // use list, chained through Flow.data
	merge   *TempVar // merge var with this one
	start   int64    // smallest Prog.pc in live range
	end     int64    // largest Prog.pc in live range
	addr    bool     // address taken - no accurate end
	removed bool     // removed from program
}

// startcmp sorts TempVars by start, then id, then symbol name.
type startcmp []*TempVar

func (x startcmp) Len() int      { return len(x) }
func (x startcmp) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
func (x startcmp) Less(i, j int) bool {
	a := x[i]
	b := x[j]

	if a.start < b.start {
		return true
	}
	if a.start > b.start {
		return false
	}

	// Order what's left by id or symbol name,
	// just so that sort is forced into a specific ordering,
	// so that the result of the sort does not depend on
	// the sort implementation.
	if a.def != b.def {
		return int(a.def.Id-b.def.Id) < 0
	}
	if a.node != b.node {
		return a.node.Sym.Name < b.node.Sym.Name
	}
	return false
}

// Is n available for merging?
func canmerge(n *Node) bool {
	return n.Class == PAUTO && strings.HasPrefix(n.Sym.Name, "autotmp")
}

func mergetemp(firstp *obj.Prog) {
	const (
		debugmerge = 0
	)

	g := Flowstart(firstp, nil)
	if g == nil {
		return
	}

	// Build list of all mergeable variables.
	var vars []*TempVar
	for l := Curfn.Func.Dcl; l != nil; l = l.Next {
		if n := l.N; canmerge(n) {
			v := &TempVar{}
			vars = append(vars, v)
			n.SetOpt(v)
			v.node = n
		}
	}

	// Build list of uses.
	// We assume that the earliest reference to a temporary is its definition.
	// This is not true of variables in general but our temporaries are all
	// single-use (that's why we have so many!).
	for f := g.Start; f != nil; f = f.Link {
		p := f.Prog
		if p.From.Node != nil && ((p.From.Node).(*Node)).Opt() != nil && p.To.Node != nil && ((p.To.Node).(*Node)).Opt() != nil {
			Fatalf("double node %v", p)
		}
		var v *TempVar
		n, _ := p.From.Node.(*Node)
		if n != nil {
			v, _ = n.Opt().(*TempVar)
		}
		if v == nil {
			n, _ = p.To.Node.(*Node)
			if n != nil {
				v, _ = n.Opt().(*TempVar)
			}
		}
		if v != nil {
			if v.def == nil {
				v.def = f
			}
			f.Data = v.use
			v.use = f
			if n == p.From.Node && (p.Info.Flags&LeftAddr != 0) {
				v.addr = true
			}
		}
	}

	if debugmerge > 1 && Debug['v'] != 0 {
		Dumpit("before", g.Start, 0)
	}

	nkill := 0

	// Special case.
	for _, v := range vars {
		if v.addr {
			continue
		}

		// Used in only one instruction, which had better be a write.
		f := v.use
		if f != nil && f.Data.(*Flow) == nil {
			p := f.Prog
			if p.To.Node == v.node && (p.Info.Flags&RightWrite != 0) && p.Info.Flags&RightRead == 0 {
				p.As = obj.ANOP
				p.To = obj.Addr{}
				v.removed = true
				if debugmerge > 0 && Debug['v'] != 0 {
					fmt.Printf("drop write-only %v\n", v.node.Sym)
				}
			} else {
				Fatalf("temp used and not set: %v", p)
			}
			nkill++
			continue
		}

		// Written in one instruction, read in the next, otherwise unused,
		// no jumps to the next instruction. Happens mainly in 386 compiler.
		f = v.use
		if f != nil && f.Link == f.Data.(*Flow) && (f.Data.(*Flow)).Data.(*Flow) == nil && Uniqp(f.Link) == f {
			p := f.Prog
			p1 := f.Link.Prog
			const (
				SizeAny = SizeB | SizeW | SizeL | SizeQ | SizeF | SizeD
			)
			if p.From.Node == v.node && p1.To.Node == v.node && (p.Info.Flags&Move != 0) && (p.Info.Flags|p1.Info.Flags)&(LeftAddr|RightAddr) == 0 && p.Info.Flags&SizeAny == p1.Info.Flags&SizeAny {
				p1.From = p.From
				Thearch.Excise(f)
				v.removed = true
				if debugmerge > 0 && Debug['v'] != 0 {
					fmt.Printf("drop immediate-use %v\n", v.node.Sym)
				}
			}

			nkill++
			continue
		}
	}

	// Traverse live range of each variable to set start, end.
	// Each flood uses a new value of gen so that we don't have
	// to clear all the r->active words after each variable.
	gen := uint32(0)

	for _, v := range vars {
		gen++
		for f := v.use; f != nil; f = f.Data.(*Flow) {
			mergewalk(v, f, gen)
		}
		if v.addr {
			gen++
			for f := v.use; f != nil; f = f.Data.(*Flow) {
				varkillwalk(v, f, gen)
			}
		}
	}

	// Sort variables by start.
	bystart := make([]*TempVar, len(vars))
	copy(bystart, vars)
	sort.Sort(startcmp(bystart))

	// List of in-use variables, sorted by end, so that the ones that
	// will last the longest are the earliest ones in the array.
	// The tail inuse[nfree:] holds no-longer-used variables.
	// In theory we should use a sorted tree so that insertions are
	// guaranteed O(log n) and then the loop is guaranteed O(n log n).
	// In practice, it doesn't really matter.
	inuse := make([]*TempVar, len(bystart))

	ninuse := 0
	nfree := len(bystart)
	for _, v := range bystart {
		if debugmerge > 0 && Debug['v'] != 0 {
			fmt.Printf("consider %v: removed=%t\n", Nconv(v.node, obj.FmtSharp), v.removed)
		}

		if v.removed {
			continue
		}

		// Expire no longer in use.
		for ninuse > 0 && inuse[ninuse-1].end < v.start {
			ninuse--
			nfree--
			inuse[nfree] = inuse[ninuse]
		}

		if debugmerge > 0 && Debug['v'] != 0 {
			fmt.Printf("consider %v: removed=%t nfree=%d nvar=%d\n", Nconv(v.node, obj.FmtSharp), v.removed, nfree, len(bystart))
		}

		// Find old temp to reuse if possible.
		t := v.node.Type

		for j := nfree; j < len(inuse); j++ {
			v1 := inuse[j]
			if debugmerge > 0 && Debug['v'] != 0 {
				fmt.Printf("consider %v: maybe %v: type=%v,%v addrtaken=%v,%v\n", Nconv(v.node, obj.FmtSharp), Nconv(v1.node, obj.FmtSharp), t, v1.node.Type, v.node.Addrtaken, v1.node.Addrtaken)
			}

			// Require the types to match but also require the addrtaken bits to match.
			// If a variable's address is taken, that disables registerization for the individual
			// words of the variable (for example, the base,len,cap of a slice).
			// We don't want to merge a non-addressed var with an addressed one and
			// inhibit registerization of the former.
			if Eqtype(t, v1.node.Type) && v.node.Addrtaken == v1.node.Addrtaken {
				inuse[j] = inuse[nfree]
				nfree++
				if v1.merge != nil {
					v.merge = v1.merge
				} else {
					v.merge = v1
				}
				nkill++
				break
			}
		}

		// Sort v into inuse.
		j := ninuse
		ninuse++

		for j > 0 && inuse[j-1].end < v.end {
			inuse[j] = inuse[j-1]
			j--
		}

		inuse[j] = v
	}

	if debugmerge > 0 && Debug['v'] != 0 {
		fmt.Printf("%v [%d - %d]\n", Curfn.Func.Nname.Sym, len(vars), nkill)
		for _, v := range vars {
			fmt.Printf("var %v %v %d-%d", Nconv(v.node, obj.FmtSharp), v.node.Type, v.start, v.end)
			if v.addr {
				fmt.Printf(" addr=true")
			}
			if v.removed {
				fmt.Printf(" removed=true")
			}
			if v.merge != nil {
				fmt.Printf(" merge %v", Nconv(v.merge.node, obj.FmtSharp))
			}
			if v.start == v.end && v.def != nil {
				fmt.Printf(" %v", v.def.Prog)
			}
			fmt.Printf("\n")
		}

		if debugmerge > 1 && Debug['v'] != 0 {
			Dumpit("after", g.Start, 0)
		}
	}

	// Update node references to use merged temporaries.
	for f := g.Start; f != nil; f = f.Link {
		p := f.Prog
		n, _ := p.From.Node.(*Node)
		if n != nil {
			v, _ := n.Opt().(*TempVar)
			if v != nil && v.merge != nil {
				p.From.Node = v.merge.node
			}
		}
		n, _ = p.To.Node.(*Node)
		if n != nil {
			v, _ := n.Opt().(*TempVar)
			if v != nil && v.merge != nil {
				p.To.Node = v.merge.node
			}
		}
	}

	// Delete merged nodes from declaration list.
	for lp := &Curfn.Func.Dcl; ; {
		l := *lp
		if l == nil {
			break
		}

		Curfn.Func.Dcl.End = l
		n := l.N
		v, _ := n.Opt().(*TempVar)
		if v != nil && (v.merge != nil || v.removed) {
			*lp = l.Next
			continue
		}

		lp = &l.Next
	}

	// Clear aux structures.
	for _, v := range vars {
		v.node.SetOpt(nil)
	}

	Flowend(g)
}

func mergewalk(v *TempVar, f0 *Flow, gen uint32) {
	var p *obj.Prog
	var f1 *Flow

	for f1 = f0; f1 != nil; f1 = f1.P1 {
		if uint32(f1.Active) == gen {
			break
		}
		f1.Active = int32(gen)
		p = f1.Prog
		if v.end < p.Pc {
			v.end = p.Pc
		}
		if f1 == v.def {
			v.start = p.Pc
			break
		}
	}

	var f2 *Flow
	for f := f0; f != f1; f = f.P1 {
		for f2 = f.P2; f2 != nil; f2 = f2.P2link {
			mergewalk(v, f2, gen)
		}
	}
}

func varkillwalk(v *TempVar, f0 *Flow, gen uint32) {
	var p *obj.Prog
	var f1 *Flow

	for f1 = f0; f1 != nil; f1 = f1.S1 {
		if uint32(f1.Active) == gen {
			break
		}
		f1.Active = int32(gen)
		p = f1.Prog
		if v.end < p.Pc {
			v.end = p.Pc
		}
		if v.start > p.Pc {
			v.start = p.Pc
		}
		if p.As == obj.ARET || (p.As == obj.AVARKILL && p.To.Node == v.node) {
			break
		}
	}

	for f := f0; f != f1; f = f.S1 {
		varkillwalk(v, f.S2, gen)
	}
}

// Eliminate redundant nil pointer checks.
//
// The code generation pass emits a CHECKNIL for every possibly nil pointer.
// This pass removes a CHECKNIL if every predecessor path has already
// checked this value for nil.
//
// Simple backwards flood from check to definition.
// Run prog loop backward from end of program to beginning to avoid quadratic
// behavior removing a run of checks.
//
// Assume that stack variables with address not taken can be loaded multiple times
// from memory without being rechecked. Other variables need to be checked on
// each load.

var killed int // f->data is either nil or &killed

func nilopt(firstp *obj.Prog) {
	g := Flowstart(firstp, nil)
	if g == nil {
		return
	}

	if Debug_checknil > 1 { // || strcmp(curfn->nname->sym->name, "f1") == 0
		Dumpit("nilopt", g.Start, 0)
	}

	ncheck := 0
	nkill := 0
	var p *obj.Prog
	for f := g.Start; f != nil; f = f.Link {
		p = f.Prog
		if p.As != obj.ACHECKNIL || !Thearch.Regtyp(&p.From) {
			continue
		}
		ncheck++
		if Thearch.Stackaddr(&p.From) {
			if Debug_checknil != 0 && p.Lineno > 1 {
				Warnl(int(p.Lineno), "removed nil check of SP address")
			}
			f.Data = &killed
			continue
		}

		nilwalkfwd(f)
		if f.Data != nil {
			if Debug_checknil != 0 && p.Lineno > 1 {
				Warnl(int(p.Lineno), "removed nil check before indirect")
			}
			continue
		}

		nilwalkback(f)
		if f.Data != nil {
			if Debug_checknil != 0 && p.Lineno > 1 {
				Warnl(int(p.Lineno), "removed repeated nil check")
			}
			continue
		}
	}

	for f := g.Start; f != nil; f = f.Link {
		if f.Data != nil {
			nkill++
			Thearch.Excise(f)
		}
	}

	Flowend(g)

	if Debug_checknil > 1 {
		fmt.Printf("%v: removed %d of %d nil checks\n", Curfn.Func.Nname.Sym, nkill, ncheck)
	}
}

func nilwalkback(fcheck *Flow) {
	for f := fcheck; f != nil; f = Uniqp(f) {
		p := f.Prog
		if (p.Info.Flags&RightWrite != 0) && Thearch.Sameaddr(&p.To, &fcheck.Prog.From) {
			// Found initialization of value we're checking for nil.
			// without first finding the check, so this one is unchecked.
			return
		}

		if f != fcheck && p.As == obj.ACHECKNIL && Thearch.Sameaddr(&p.From, &fcheck.Prog.From) {
			fcheck.Data = &killed
			return
		}
	}
}

// Here is a more complex version that scans backward across branches.
// It assumes fcheck->kill = 1 has been set on entry, and its job is to find a reason
// to keep the check (setting fcheck->kill = 0).
// It doesn't handle copying of aggregates as well as I would like,
// nor variables with their address taken,
// and it's too subtle to turn on this late in Go 1.2. Perhaps for Go 1.3.
/*
for(f1 = f0; f1 != nil; f1 = f1->p1) {
	if(f1->active == gen)
		break;
	f1->active = gen;
	p = f1->prog;

	// If same check, stop this loop but still check
	// alternate predecessors up to this point.
	if(f1 != fcheck && p->as == ACHECKNIL && thearch.sameaddr(&p->from, &fcheck->prog->from))
		break;

	if((p.Info.flags & RightWrite) && thearch.sameaddr(&p->to, &fcheck->prog->from)) {
		// Found initialization of value we're checking for nil.
		// without first finding the check, so this one is unchecked.
		fcheck->kill = 0;
		return;
	}

	if(f1->p1 == nil && f1->p2 == nil) {
		print("lost pred for %v\n", fcheck->prog);
		for(f1=f0; f1!=nil; f1=f1->p1) {
			thearch.proginfo(&info, f1->prog);
			print("\t%v %d %d %D %D\n", r1->prog, info.flags&RightWrite, thearch.sameaddr(&f1->prog->to, &fcheck->prog->from), &f1->prog->to, &fcheck->prog->from);
		}
		fatal("lost pred trail");
	}
}

for(f = f0; f != f1; f = f->p1)
	for(f2 = f->p2; f2 != nil; f2 = f2->p2link)
		nilwalkback(fcheck, f2, gen);
*/

func nilwalkfwd(fcheck *Flow) {
	// If the path down from rcheck dereferences the address
	// (possibly with a small offset) before writing to memory
	// and before any subsequent checks, it's okay to wait for
	// that implicit check. Only consider this basic block to
	// avoid problems like:
	//	_ = *x // should panic
	//	for {} // no writes but infinite loop may be considered visible

	var last *Flow
	for f := Uniqs(fcheck); f != nil; f = Uniqs(f) {
		p := f.Prog
		if (p.Info.Flags&LeftRead != 0) && Thearch.Smallindir(&p.From, &fcheck.Prog.From) {
			fcheck.Data = &killed
			return
		}

		if (p.Info.Flags&(RightRead|RightWrite) != 0) && Thearch.Smallindir(&p.To, &fcheck.Prog.From) {
			fcheck.Data = &killed
			return
		}

		// Stop if another nil check happens.
		if p.As == obj.ACHECKNIL {
			return
		}

		// Stop if value is lost.
		if (p.Info.Flags&RightWrite != 0) && Thearch.Sameaddr(&p.To, &fcheck.Prog.From) {
			return
		}

		// Stop if memory write.
		if (p.Info.Flags&RightWrite != 0) && !Thearch.Regtyp(&p.To) {
			return
		}

		// Stop if we jump backward.
		if last != nil && f.Id <= last.Id {
			return
		}
		last = f
	}
}