src/cmd/compile/internal/ssa/likelyadjust.go - go - Git at Google

 // 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 ssa

 import (
 	"fmt"
 )

 type loop struct {
 	header *Block // The header node of this (reducible) loop
 	outer  *loop  // loop containing this loop

 	// By default, children, exits, and depth are not initialized.
 	children []*loop  // loops nested directly within this loop. Initialized by assembleChildren().
 	exits    []*Block // exits records blocks reached by exits from this loop. Initialized by findExits().

 	// Next three fields used by regalloc and/or
 	// aid in computation of inner-ness and list of blocks.
 	nBlocks int32 // Number of blocks in this loop but not within inner loops
 	depth   int16 // Nesting depth of the loop; 1 is outermost. Initialized by calculateDepths().
 	isInner bool  // True if never discovered to contain a loop

 	// register allocation uses this.
 	containsUnavoidableCall bool // True if all paths through the loop have a call
 }

 // outerinner records that outer contains inner
 func (sdom SparseTree) outerinner(outer, inner *loop) {
 	// There could be other outer loops found in some random order,
 	// locate the new outer loop appropriately among them.

 	// Outer loop headers dominate inner loop headers.
 	// Use this to put the "new" "outer" loop in the right place.
 	oldouter := inner.outer
 	for oldouter != nil && sdom.isAncestor(outer.header, oldouter.header) {
 		inner = oldouter
 		oldouter = inner.outer
 	}
 	if outer == oldouter {
 		return
 	}
 	if oldouter != nil {
 		sdom.outerinner(oldouter, outer)
 	}

 	inner.outer = outer
 	outer.isInner = false
 }

 func checkContainsCall(bb *Block) bool {
 	if bb.Kind == BlockDefer {
 		return true
 	}
 	for _, v := range bb.Values {
 		if opcodeTable[v.Op].call {
 			return true
 		}
 	}
 	return false
 }

 type loopnest struct {
 	f              *Func
 	b2l            []*loop
 	po             []*Block
 	sdom           SparseTree
 	loops          []*loop
 	hasIrreducible bool // TODO current treatment of irreducible loops is very flaky, if accurate loops are needed, must punt at function level.

 	// Record which of the lazily initialized fields have actually been initialized.
 	initializedChildren, initializedDepth, initializedExits bool
 }

 func min8(a, b int8) int8 {
 	if a < b {
 		return a
 	}
 	return b
 }

 func max8(a, b int8) int8 {
 	if a > b {
 		return a
 	}
 	return b
 }

 const (
 	blDEFAULT = 0
 	blMin     = blDEFAULT
 	blCALL    = 1
 	blRET     = 2
 	blEXIT    = 3
 )

 var bllikelies = [4]string{"default", "call", "ret", "exit"}

 func describePredictionAgrees(b *Block, prediction BranchPrediction) string {
 	s := ""
 	if prediction == b.Likely {
 		s = " (agrees with previous)"
 	} else if b.Likely != BranchUnknown {
 		s = " (disagrees with previous, ignored)"
 	}
 	return s
 }

 func describeBranchPrediction(f *Func, b *Block, likely, not int8, prediction BranchPrediction) {
 	f.Warnl(b.Pos, "Branch prediction rule %s < %s%s",
 		bllikelies[likely-blMin], bllikelies[not-blMin], describePredictionAgrees(b, prediction))
 }

 func likelyadjust(f *Func) {
 	// The values assigned to certain and local only matter
 	// in their rank order.  0 is default, more positive
 	// is less likely. It's possible to assign a negative
 	// unlikeliness (though not currently the case).
 	certain := make([]int8, f.NumBlocks()) // In the long run, all outcomes are at least this bad. Mainly for Exit
 	local := make([]int8, f.NumBlocks())   // for our immediate predecessors.

 	po := f.postorder()
 	nest := f.loopnest()
 	b2l := nest.b2l

 	for _, b := range po {
 		switch b.Kind {
 		case BlockExit:
 			// Very unlikely.
 			local[b.ID] = blEXIT
 			certain[b.ID] = blEXIT

 			// Ret, it depends.
 		case BlockRet, BlockRetJmp:
 			local[b.ID] = blRET
 			certain[b.ID] = blRET

 			// Calls. TODO not all calls are equal, names give useful clues.
 			// Any name-based heuristics are only relative to other calls,
 			// and less influential than inferences from loop structure.
 		case BlockDefer:
 			local[b.ID] = blCALL
 			certain[b.ID] = max8(blCALL, certain[b.Succs[0].b.ID])

 		default:
 			if len(b.Succs) == 1 {
 				certain[b.ID] = certain[b.Succs[0].b.ID]
 			} else if len(b.Succs) == 2 {
 				// If successor is an unvisited backedge, it's in loop and we don't care.
 				// Its default unlikely is also zero which is consistent with favoring loop edges.
 				// Notice that this can act like a "reset" on unlikeliness at loops; the
 				// default "everything returns" unlikeliness is erased by min with the
 				// backedge likeliness; however a loop with calls on every path will be
 				// tagged with call cost. Net effect is that loop entry is favored.
 				b0 := b.Succs[0].b.ID
 				b1 := b.Succs[1].b.ID
 				certain[b.ID] = min8(certain[b0], certain[b1])

 				l := b2l[b.ID]
 				l0 := b2l[b0]
 				l1 := b2l[b1]

 				prediction := b.Likely
 				// Weak loop heuristic -- both source and at least one dest are in loops,
 				// and there is a difference in the destinations.
 				// TODO what is best arrangement for nested loops?
 				if l != nil && l0 != l1 {
 					noprediction := false
 					switch {
 					// prefer not to exit loops
 					case l1 == nil:
 						prediction = BranchLikely
 					case l0 == nil:
 						prediction = BranchUnlikely

 						// prefer to stay in loop, not exit to outer.
 					case l == l0:
 						prediction = BranchLikely
 					case l == l1:
 						prediction = BranchUnlikely
 					default:
 						noprediction = true
 					}
 					if f.pass.debug > 0 && !noprediction {
 						f.Warnl(b.Pos, "Branch prediction rule stay in loop%s",
 							describePredictionAgrees(b, prediction))
 					}

 				} else {
 					// Lacking loop structure, fall back on heuristics.
 					if certain[b1] > certain[b0] {
 						prediction = BranchLikely
 						if f.pass.debug > 0 {
 							describeBranchPrediction(f, b, certain[b0], certain[b1], prediction)
 						}
 					} else if certain[b0] > certain[b1] {
 						prediction = BranchUnlikely
 						if f.pass.debug > 0 {
 							describeBranchPrediction(f, b, certain[b1], certain[b0], prediction)
 						}
 					} else if local[b1] > local[b0] {
 						prediction = BranchLikely
 						if f.pass.debug > 0 {
 							describeBranchPrediction(f, b, local[b0], local[b1], prediction)
 						}
 					} else if local[b0] > local[b1] {
 						prediction = BranchUnlikely
 						if f.pass.debug > 0 {
 							describeBranchPrediction(f, b, local[b1], local[b0], prediction)
 						}
 					}
 				}
 				if b.Likely != prediction {
 					if b.Likely == BranchUnknown {
 						b.Likely = prediction
 					}
 				}
 			}
 			// Look for calls in the block.  If there is one, make this block unlikely.
 			for _, v := range b.Values {
 				if opcodeTable[v.Op].call {
 					local[b.ID] = blCALL
 					certain[b.ID] = max8(blCALL, certain[b.Succs[0].b.ID])
 				}
 			}
 		}
 		if f.pass.debug > 2 {
 			f.Warnl(b.Pos, "BP: Block %s, local=%s, certain=%s", b, bllikelies[local[b.ID]-blMin], bllikelies[certain[b.ID]-blMin])
 		}

 	}
 }

 func (l *loop) String() string {
 	return fmt.Sprintf("hdr:%s", l.header)
 }

 func (l *loop) LongString() string {
 	i := ""
 	o := ""
 	if l.isInner {
 		i = ", INNER"
 	}
 	if l.outer != nil {
 		o = ", o=" + l.outer.header.String()
 	}
 	return fmt.Sprintf("hdr:%s%s%s", l.header, i, o)
 }

 func (l *loop) isWithinOrEq(ll *loop) bool {
 	if ll == nil { // nil means whole program
 		return true
 	}
 	for ; l != nil; l = l.outer {
 		if l == ll {
 			return true
 		}
 	}
 	return false
 }

 // nearestOuterLoop returns the outer loop of loop most nearly
 // containing block b; the header must dominate b.  loop itself
 // is assumed to not be that loop. For acceptable performance,
 // we're relying on loop nests to not be terribly deep.
 func (l *loop) nearestOuterLoop(sdom SparseTree, b *Block) *loop {
 	var o *loop
 	for o = l.outer; o != nil && !sdom.IsAncestorEq(o.header, b); o = o.outer {
 	}
 	return o
 }

 func loopnestfor(f *Func) *loopnest {
 	po := f.postorder()
 	sdom := f.Sdom()
 	b2l := make([]*loop, f.NumBlocks())
 	loops := make([]*loop, 0)
 	visited := make([]bool, f.NumBlocks())
 	sawIrred := false

 	if f.pass.debug > 2 {
 		fmt.Printf("loop finding in %s\n", f.Name)
 	}

 	// Reducible-loop-nest-finding.
 	for _, b := range po {
 		if f.pass != nil && f.pass.debug > 3 {
 			fmt.Printf("loop finding at %s\n", b)
 		}

 		var innermost *loop // innermost header reachable from this block

 		// IF any successor s of b is in a loop headed by h
 		// AND h dominates b
 		// THEN b is in the loop headed by h.
 		//
 		// Choose the first/innermost such h.
 		//
 		// IF s itself dominates b, then s is a loop header;
 		// and there may be more than one such s.
 		// Since there's at most 2 successors, the inner/outer ordering
 		// between them can be established with simple comparisons.
 		for _, e := range b.Succs {
 			bb := e.b
 			l := b2l[bb.ID]

 			if sdom.IsAncestorEq(bb, b) { // Found a loop header
 				if f.pass != nil && f.pass.debug > 4 {
 					fmt.Printf("loop finding    succ %s of %s is header\n", bb.String(), b.String())
 				}
 				if l == nil {
 					l = &loop{header: bb, isInner: true}
 					loops = append(loops, l)
 					b2l[bb.ID] = l
 				}
 			} else if !visited[bb.ID] { // Found an irreducible loop
 				sawIrred = true
 				if f.pass != nil && f.pass.debug > 4 {
 					fmt.Printf("loop finding    succ %s of %s is IRRED, in %s\n", bb.String(), b.String(), f.Name)
 				}
 			} else if l != nil {
 				// TODO handle case where l is irreducible.
 				// Perhaps a loop header is inherited.
 				// is there any loop containing our successor whose
 				// header dominates b?
 				if !sdom.IsAncestorEq(l.header, b) {
 					l = l.nearestOuterLoop(sdom, b)
 				}
 				if f.pass != nil && f.pass.debug > 4 {
 					if l == nil {
 						fmt.Printf("loop finding    succ %s of %s has no loop\n", bb.String(), b.String())
 					} else {
 						fmt.Printf("loop finding    succ %s of %s provides loop with header %s\n", bb.String(), b.String(), l.header.String())
 					}
 				}
 			} else { // No loop
 				if f.pass != nil && f.pass.debug > 4 {
 					fmt.Printf("loop finding    succ %s of %s has no loop\n", bb.String(), b.String())
 				}

 			}

 			if l == nil || innermost == l {
 				continue
 			}

 			if innermost == nil {
 				innermost = l
 				continue
 			}

 			if sdom.isAncestor(innermost.header, l.header) {
 				sdom.outerinner(innermost, l)
 				innermost = l
 			} else if sdom.isAncestor(l.header, innermost.header) {
 				sdom.outerinner(l, innermost)
 			}
 		}

 		if innermost != nil {
 			b2l[b.ID] = innermost
 			innermost.nBlocks++
 		}
 		visited[b.ID] = true
 	}

 	ln := &loopnest{f: f, b2l: b2l, po: po, sdom: sdom, loops: loops, hasIrreducible: sawIrred}

 	// Calculate containsUnavoidableCall for regalloc
 	dominatedByCall := make([]bool, f.NumBlocks())
 	for _, b := range po {
 		if checkContainsCall(b) {
 			dominatedByCall[b.ID] = true
 		}
 	}
 	// Run dfs to find path through the loop that avoids all calls.
 	// Such path either escapes loop or return back to header.
 	// It isn't enough to have exit not dominated by any call, for example:
 	// ... some loop
 	// call1   call2
 	//   \      /
 	//     exit
 	// ...
 	// exit is not dominated by any call, but we don't have call-free path to it.
 	for _, l := range loops {
 		// Header contains call.
 		if dominatedByCall[l.header.ID] {
 			l.containsUnavoidableCall = true
 			continue
 		}
 		callfreepath := false
 		tovisit := make([]*Block, 0, len(l.header.Succs))
 		// Push all non-loop non-exit successors of header onto toVisit.
 		for _, s := range l.header.Succs {
 			nb := s.Block()
 			// This corresponds to loop with zero iterations.
 			if !l.iterationEnd(nb, b2l) {
 				tovisit = append(tovisit, nb)
 			}
 		}
 		for len(tovisit) > 0 {
 			cur := tovisit[len(tovisit)-1]
 			tovisit = tovisit[:len(tovisit)-1]
 			if dominatedByCall[cur.ID] {
 				continue
 			}
 			// Record visited in dominatedByCall.
 			dominatedByCall[cur.ID] = true
 			for _, s := range cur.Succs {
 				nb := s.Block()
 				if l.iterationEnd(nb, b2l) {
 					callfreepath = true
 				}
 				if !dominatedByCall[nb.ID] {
 					tovisit = append(tovisit, nb)
 				}

 			}
 			if callfreepath {
 				break
 			}
 		}
 		if !callfreepath {
 			l.containsUnavoidableCall = true
 		}
 	}

 	// Curious about the loopiness? "-d=ssa/likelyadjust/stats"
 	if f.pass != nil && f.pass.stats > 0 && len(loops) > 0 {
 		ln.assembleChildren()
 		ln.calculateDepths()
 		ln.findExits()

 		// Note stats for non-innermost loops are slightly flawed because
 		// they don't account for inner loop exits that span multiple levels.

 		for _, l := range loops {
 			x := len(l.exits)
 			cf := 0
 			if !l.containsUnavoidableCall {
 				cf = 1
 			}
 			inner := 0
 			if l.isInner {
 				inner++
 			}

 			f.LogStat("loopstats:",
 				l.depth, "depth", x, "exits",
 				inner, "is_inner", cf, "always_calls", l.nBlocks, "n_blocks")
 		}
 	}

 	if f.pass != nil && f.pass.debug > 1 && len(loops) > 0 {
 		fmt.Printf("Loops in %s:\n", f.Name)
 		for _, l := range loops {
 			fmt.Printf("%s, b=", l.LongString())
 			for _, b := range f.Blocks {
 				if b2l[b.ID] == l {
 					fmt.Printf(" %s", b)
 				}
 			}
 			fmt.Print("\n")
 		}
 		fmt.Printf("Nonloop blocks in %s:", f.Name)
 		for _, b := range f.Blocks {
 			if b2l[b.ID] == nil {
 				fmt.Printf(" %s", b)
 			}
 		}
 		fmt.Print("\n")
 	}
 	return ln
 }

 // assembleChildren initializes the children field of each
 // loop in the nest.  Loop A is a child of loop B if A is
 // directly nested within B (based on the reducible-loops
 // detection above)
 func (ln *loopnest) assembleChildren() {
 	if ln.initializedChildren {
 		return
 	}
 	for _, l := range ln.loops {
 		if l.outer != nil {
 			l.outer.children = append(l.outer.children, l)
 		}
 	}
 	ln.initializedChildren = true
 }

 // calculateDepths uses the children field of loops
 // to determine the nesting depth (outer=1) of each
 // loop.  This is helpful for finding exit edges.
 func (ln *loopnest) calculateDepths() {
 	if ln.initializedDepth {
 		return
 	}
 	ln.assembleChildren()
 	for _, l := range ln.loops {
 		if l.outer == nil {
 			l.setDepth(1)
 		}
 	}
 	ln.initializedDepth = true
 }

 // findExits uses loop depth information to find the
 // exits from a loop.
 func (ln *loopnest) findExits() {
 	if ln.initializedExits {
 		return
 	}
 	ln.calculateDepths()
 	b2l := ln.b2l
 	for _, b := range ln.po {
 		l := b2l[b.ID]
 		if l != nil && len(b.Succs) == 2 {
 			sl := b2l[b.Succs[0].b.ID]
 			if recordIfExit(l, sl, b.Succs[0].b) {
 				continue
 			}
 			sl = b2l[b.Succs[1].b.ID]
 			if recordIfExit(l, sl, b.Succs[1].b) {
 				continue
 			}
 		}
 	}
 	ln.initializedExits = true
 }

 // depth returns the loop nesting level of block b.
 func (ln *loopnest) depth(b ID) int16 {
 	if l := ln.b2l[b]; l != nil {
 		return l.depth
 	}
 	return 0
 }

 // recordIfExit checks sl (the loop containing b) to see if it
 // is outside of loop l, and if so, records b as an exit block
 // from l and returns true.
 func recordIfExit(l, sl *loop, b *Block) bool {
 	if sl != l {
 		if sl == nil || sl.depth <= l.depth {
 			l.exits = append(l.exits, b)
 			return true
 		}
 		// sl is not nil, and is deeper than l
 		// it's possible for this to be a goto into an irreducible loop made from gotos.
 		for sl.depth > l.depth {
 			sl = sl.outer
 		}
 		if sl != l {
 			l.exits = append(l.exits, b)
 			return true
 		}
 	}
 	return false
 }

 func (l *loop) setDepth(d int16) {
 	l.depth = d
 	for _, c := range l.children {
 		c.setDepth(d + 1)
 	}
 }

 // iterationEnd checks if block b ends iteration of loop l.
 // Ending iteration means either escaping to outer loop/code or
 // going back to header
 func (l *loop) iterationEnd(b *Block, b2l []*loop) bool {
 	return b == l.header || b2l[b.ID] == nil || (b2l[b.ID] != l && b2l[b.ID].depth <= l.depth)
 }
	// 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 ssa

	import (
	"fmt"
	)

	type loop struct {
	header *Block // The header node of this (reducible) loop
	outer *loop // loop containing this loop

	// By default, children, exits, and depth are not initialized.
	children []*loop // loops nested directly within this loop. Initialized by assembleChildren().
	exits []*Block // exits records blocks reached by exits from this loop. Initialized by findExits().

	// Next three fields used by regalloc and/or
	// aid in computation of inner-ness and list of blocks.
	nBlocks int32 // Number of blocks in this loop but not within inner loops
	depth int16 // Nesting depth of the loop; 1 is outermost. Initialized by calculateDepths().
	isInner bool // True if never discovered to contain a loop

	// register allocation uses this.
	containsUnavoidableCall bool // True if all paths through the loop have a call
	}

	// outerinner records that outer contains inner
	func (sdom SparseTree) outerinner(outer, inner *loop) {
	// There could be other outer loops found in some random order,
	// locate the new outer loop appropriately among them.

	// Outer loop headers dominate inner loop headers.
	// Use this to put the "new" "outer" loop in the right place.
	oldouter := inner.outer
	for oldouter != nil && sdom.isAncestor(outer.header, oldouter.header) {
	inner = oldouter
	oldouter = inner.outer
	}
	if outer == oldouter {
	return
	}
	if oldouter != nil {
	sdom.outerinner(oldouter, outer)
	}

	inner.outer = outer
	outer.isInner = false
	}

	func checkContainsCall(bb *Block) bool {
	if bb.Kind == BlockDefer {
	return true
	}
	for _, v := range bb.Values {
	if opcodeTable[v.Op].call {
	return true
	}
	}
	return false
	}

	type loopnest struct {
	f *Func
	b2l []*loop
	po []*Block
	sdom SparseTree
	loops []*loop
	hasIrreducible bool // TODO current treatment of irreducible loops is very flaky, if accurate loops are needed, must punt at function level.

	// Record which of the lazily initialized fields have actually been initialized.
	initializedChildren, initializedDepth, initializedExits bool
	}

	func min8(a, b int8) int8 {
	if a < b {
	return a
	}
	return b
	}

	func max8(a, b int8) int8 {
	if a > b {
	return a
	}
	return b
	}

	const (
	blDEFAULT = 0
	blMin = blDEFAULT
	blCALL = 1
	blRET = 2
	blEXIT = 3
	)

	var bllikelies = [4]string{"default", "call", "ret", "exit"}

	func describePredictionAgrees(b *Block, prediction BranchPrediction) string {
	s := ""
	if prediction == b.Likely {
	s = " (agrees with previous)"
	} else if b.Likely != BranchUnknown {
	s = " (disagrees with previous, ignored)"
	}
	return s
	}

	func describeBranchPrediction(f Func, b Block, likely, not int8, prediction BranchPrediction) {
	f.Warnl(b.Pos, "Branch prediction rule %s < %s%s",
	bllikelies[likely-blMin], bllikelies[not-blMin], describePredictionAgrees(b, prediction))
	}

	func likelyadjust(f *Func) {
	// The values assigned to certain and local only matter
	// in their rank order. 0 is default, more positive
	// is less likely. It's possible to assign a negative
	// unlikeliness (though not currently the case).
	certain := make([]int8, f.NumBlocks()) // In the long run, all outcomes are at least this bad. Mainly for Exit
	local := make([]int8, f.NumBlocks()) // for our immediate predecessors.

	po := f.postorder()
	nest := f.loopnest()
	b2l := nest.b2l

	for _, b := range po {
	switch b.Kind {
	case BlockExit:
	// Very unlikely.
	local[b.ID] = blEXIT
	certain[b.ID] = blEXIT

	// Ret, it depends.
	case BlockRet, BlockRetJmp:
	local[b.ID] = blRET
	certain[b.ID] = blRET

	// Calls. TODO not all calls are equal, names give useful clues.
	// Any name-based heuristics are only relative to other calls,
	// and less influential than inferences from loop structure.
	case BlockDefer:
	local[b.ID] = blCALL
	certain[b.ID] = max8(blCALL, certain[b.Succs[0].b.ID])

	default:
	if len(b.Succs) == 1 {
	certain[b.ID] = certain[b.Succs[0].b.ID]
	} else if len(b.Succs) == 2 {
	// If successor is an unvisited backedge, it's in loop and we don't care.
	// Its default unlikely is also zero which is consistent with favoring loop edges.
	// Notice that this can act like a "reset" on unlikeliness at loops; the
	// default "everything returns" unlikeliness is erased by min with the
	// backedge likeliness; however a loop with calls on every path will be
	// tagged with call cost. Net effect is that loop entry is favored.
	b0 := b.Succs[0].b.ID
	b1 := b.Succs[1].b.ID
	certain[b.ID] = min8(certain[b0], certain[b1])

	l := b2l[b.ID]
	l0 := b2l[b0]
	l1 := b2l[b1]

	prediction := b.Likely
	// Weak loop heuristic -- both source and at least one dest are in loops,
	// and there is a difference in the destinations.
	// TODO what is best arrangement for nested loops?
	if l != nil && l0 != l1 {
	noprediction := false
	switch {
	// prefer not to exit loops
	case l1 == nil:
	prediction = BranchLikely
	case l0 == nil:
	prediction = BranchUnlikely

	// prefer to stay in loop, not exit to outer.
	case l == l0:
	prediction = BranchLikely
	case l == l1:
	prediction = BranchUnlikely
	default:
	noprediction = true
	}
	if f.pass.debug > 0 && !noprediction {
	f.Warnl(b.Pos, "Branch prediction rule stay in loop%s",
	describePredictionAgrees(b, prediction))
	}

	} else {
	// Lacking loop structure, fall back on heuristics.
	if certain[b1] > certain[b0] {
	prediction = BranchLikely
	if f.pass.debug > 0 {
	describeBranchPrediction(f, b, certain[b0], certain[b1], prediction)
	}
	} else if certain[b0] > certain[b1] {
	prediction = BranchUnlikely
	if f.pass.debug > 0 {
	describeBranchPrediction(f, b, certain[b1], certain[b0], prediction)
	}
	} else if local[b1] > local[b0] {
	prediction = BranchLikely
	if f.pass.debug > 0 {
	describeBranchPrediction(f, b, local[b0], local[b1], prediction)
	}
	} else if local[b0] > local[b1] {
	prediction = BranchUnlikely
	if f.pass.debug > 0 {
	describeBranchPrediction(f, b, local[b1], local[b0], prediction)
	}
	}
	}
	if b.Likely != prediction {
	if b.Likely == BranchUnknown {
	b.Likely = prediction
	}
	}
	}
	// Look for calls in the block. If there is one, make this block unlikely.
	for _, v := range b.Values {
	if opcodeTable[v.Op].call {
	local[b.ID] = blCALL
	certain[b.ID] = max8(blCALL, certain[b.Succs[0].b.ID])
	}
	}
	}
	if f.pass.debug > 2 {
	f.Warnl(b.Pos, "BP: Block %s, local=%s, certain=%s", b, bllikelies[local[b.ID]-blMin], bllikelies[certain[b.ID]-blMin])
	}

	}
	}

	func (l *loop) String() string {
	return fmt.Sprintf("hdr:%s", l.header)
	}

	func (l *loop) LongString() string {
	i := ""
	o := ""
	if l.isInner {
	i = ", INNER"
	}
	if l.outer != nil {
	o = ", o=" + l.outer.header.String()
	}
	return fmt.Sprintf("hdr:%s%s%s", l.header, i, o)
	}

	func (l loop) isWithinOrEq(ll loop) bool {
	if ll == nil { // nil means whole program
	return true
	}
	for ; l != nil; l = l.outer {
	if l == ll {
	return true
	}
	}
	return false
	}

	// nearestOuterLoop returns the outer loop of loop most nearly
	// containing block b; the header must dominate b. loop itself
	// is assumed to not be that loop. For acceptable performance,
	// we're relying on loop nests to not be terribly deep.
	func (l loop) nearestOuterLoop(sdom SparseTree, b Block) *loop {
	var o *loop
	for o = l.outer; o != nil && !sdom.IsAncestorEq(o.header, b); o = o.outer {
	}
	return o
	}

	func loopnestfor(f Func) loopnest {
	po := f.postorder()
	sdom := f.Sdom()
	b2l := make([]*loop, f.NumBlocks())
	loops := make([]*loop, 0)
	visited := make([]bool, f.NumBlocks())
	sawIrred := false

	if f.pass.debug > 2 {
	fmt.Printf("loop finding in %s\n", f.Name)
	}

	// Reducible-loop-nest-finding.
	for _, b := range po {
	if f.pass != nil && f.pass.debug > 3 {
	fmt.Printf("loop finding at %s\n", b)
	}

	var innermost *loop // innermost header reachable from this block

	// IF any successor s of b is in a loop headed by h
	// AND h dominates b
	// THEN b is in the loop headed by h.
	//
	// Choose the first/innermost such h.
	//
	// IF s itself dominates b, then s is a loop header;
	// and there may be more than one such s.
	// Since there's at most 2 successors, the inner/outer ordering
	// between them can be established with simple comparisons.
	for _, e := range b.Succs {
	bb := e.b
	l := b2l[bb.ID]

	if sdom.IsAncestorEq(bb, b) { // Found a loop header
	if f.pass != nil && f.pass.debug > 4 {
	fmt.Printf("loop finding succ %s of %s is header\n", bb.String(), b.String())
	}
	if l == nil {
	l = &loop{header: bb, isInner: true}
	loops = append(loops, l)
	b2l[bb.ID] = l
	}
	} else if !visited[bb.ID] { // Found an irreducible loop
	sawIrred = true
	if f.pass != nil && f.pass.debug > 4 {
	fmt.Printf("loop finding succ %s of %s is IRRED, in %s\n", bb.String(), b.String(), f.Name)
	}
	} else if l != nil {
	// TODO handle case where l is irreducible.
	// Perhaps a loop header is inherited.
	// is there any loop containing our successor whose
	// header dominates b?
	if !sdom.IsAncestorEq(l.header, b) {
	l = l.nearestOuterLoop(sdom, b)
	}
	if f.pass != nil && f.pass.debug > 4 {
	if l == nil {
	fmt.Printf("loop finding succ %s of %s has no loop\n", bb.String(), b.String())
	} else {
	fmt.Printf("loop finding succ %s of %s provides loop with header %s\n", bb.String(), b.String(), l.header.String())
	}
	}
	} else { // No loop
	if f.pass != nil && f.pass.debug > 4 {
	fmt.Printf("loop finding succ %s of %s has no loop\n", bb.String(), b.String())
	}

	}

	if l == nil \|\| innermost == l {
	continue
	}

	if innermost == nil {
	innermost = l
	continue
	}

	if sdom.isAncestor(innermost.header, l.header) {
	sdom.outerinner(innermost, l)
	innermost = l
	} else if sdom.isAncestor(l.header, innermost.header) {
	sdom.outerinner(l, innermost)
	}
	}

	if innermost != nil {
	b2l[b.ID] = innermost
	innermost.nBlocks++
	}
	visited[b.ID] = true
	}

	ln := &loopnest{f: f, b2l: b2l, po: po, sdom: sdom, loops: loops, hasIrreducible: sawIrred}

	// Calculate containsUnavoidableCall for regalloc
	dominatedByCall := make([]bool, f.NumBlocks())
	for _, b := range po {
	if checkContainsCall(b) {
	dominatedByCall[b.ID] = true
	}
	}
	// Run dfs to find path through the loop that avoids all calls.
	// Such path either escapes loop or return back to header.
	// It isn't enough to have exit not dominated by any call, for example:
	// ... some loop
	// call1 call2
	// \ /
	// exit
	// ...
	// exit is not dominated by any call, but we don't have call-free path to it.
	for _, l := range loops {
	// Header contains call.
	if dominatedByCall[l.header.ID] {
	l.containsUnavoidableCall = true
	continue
	}
	callfreepath := false
	tovisit := make([]*Block, 0, len(l.header.Succs))
	// Push all non-loop non-exit successors of header onto toVisit.
	for _, s := range l.header.Succs {
	nb := s.Block()
	// This corresponds to loop with zero iterations.
	if !l.iterationEnd(nb, b2l) {
	tovisit = append(tovisit, nb)
	}
	}
	for len(tovisit) > 0 {
	cur := tovisit[len(tovisit)-1]
	tovisit = tovisit[:len(tovisit)-1]
	if dominatedByCall[cur.ID] {
	continue
	}
	// Record visited in dominatedByCall.
	dominatedByCall[cur.ID] = true
	for _, s := range cur.Succs {
	nb := s.Block()
	if l.iterationEnd(nb, b2l) {
	callfreepath = true
	}
	if !dominatedByCall[nb.ID] {
	tovisit = append(tovisit, nb)
	}

	}
	if callfreepath {
	break
	}
	}
	if !callfreepath {
	l.containsUnavoidableCall = true
	}
	}

	// Curious about the loopiness? "-d=ssa/likelyadjust/stats"
	if f.pass != nil && f.pass.stats > 0 && len(loops) > 0 {
	ln.assembleChildren()
	ln.calculateDepths()
	ln.findExits()

	// Note stats for non-innermost loops are slightly flawed because
	// they don't account for inner loop exits that span multiple levels.

	for _, l := range loops {
	x := len(l.exits)
	cf := 0
	if !l.containsUnavoidableCall {
	cf = 1
	}
	inner := 0
	if l.isInner {
	inner++
	}

	f.LogStat("loopstats:",
	l.depth, "depth", x, "exits",
	inner, "is_inner", cf, "always_calls", l.nBlocks, "n_blocks")
	}
	}

	if f.pass != nil && f.pass.debug > 1 && len(loops) > 0 {
	fmt.Printf("Loops in %s:\n", f.Name)
	for _, l := range loops {
	fmt.Printf("%s, b=", l.LongString())
	for _, b := range f.Blocks {
	if b2l[b.ID] == l {
	fmt.Printf(" %s", b)
	}
	}
	fmt.Print("\n")
	}
	fmt.Printf("Nonloop blocks in %s:", f.Name)
	for _, b := range f.Blocks {
	if b2l[b.ID] == nil {
	fmt.Printf(" %s", b)
	}
	}
	fmt.Print("\n")
	}
	return ln
	}

	// assembleChildren initializes the children field of each
	// loop in the nest. Loop A is a child of loop B if A is
	// directly nested within B (based on the reducible-loops
	// detection above)
	func (ln *loopnest) assembleChildren() {
	if ln.initializedChildren {
	return
	}
	for _, l := range ln.loops {
	if l.outer != nil {
	l.outer.children = append(l.outer.children, l)
	}
	}
	ln.initializedChildren = true
	}

	// calculateDepths uses the children field of loops
	// to determine the nesting depth (outer=1) of each
	// loop. This is helpful for finding exit edges.
	func (ln *loopnest) calculateDepths() {
	if ln.initializedDepth {
	return
	}
	ln.assembleChildren()
	for _, l := range ln.loops {
	if l.outer == nil {
	l.setDepth(1)
	}
	}
	ln.initializedDepth = true
	}

	// findExits uses loop depth information to find the
	// exits from a loop.
	func (ln *loopnest) findExits() {
	if ln.initializedExits {
	return
	}
	ln.calculateDepths()
	b2l := ln.b2l
	for _, b := range ln.po {
	l := b2l[b.ID]
	if l != nil && len(b.Succs) == 2 {
	sl := b2l[b.Succs[0].b.ID]
	if recordIfExit(l, sl, b.Succs[0].b) {
	continue
	}
	sl = b2l[b.Succs[1].b.ID]
	if recordIfExit(l, sl, b.Succs[1].b) {
	continue
	}
	}
	}
	ln.initializedExits = true
	}

	// depth returns the loop nesting level of block b.
	func (ln *loopnest) depth(b ID) int16 {
	if l := ln.b2l[b]; l != nil {
	return l.depth
	}
	return 0
	}

	// recordIfExit checks sl (the loop containing b) to see if it
	// is outside of loop l, and if so, records b as an exit block
	// from l and returns true.
	func recordIfExit(l, sl loop, b Block) bool {
	if sl != l {
	if sl == nil \|\| sl.depth <= l.depth {
	l.exits = append(l.exits, b)
	return true
	}
	// sl is not nil, and is deeper than l
	// it's possible for this to be a goto into an irreducible loop made from gotos.
	for sl.depth > l.depth {
	sl = sl.outer
	}
	if sl != l {
	l.exits = append(l.exits, b)
	return true
	}
	}
	return false
	}

	func (l *loop) setDepth(d int16) {
	l.depth = d
	for _, c := range l.children {
	c.setDepth(d + 1)
	}
	}

	// iterationEnd checks if block b ends iteration of loop l.
	// Ending iteration means either escaping to outer loop/code or
	// going back to header
	func (l loop) iterationEnd(b Block, b2l []*loop) bool {
	return b == l.header \|\| b2l[b.ID] == nil \|\| (b2l[b.ID] != l && b2l[b.ID].depth <= l.depth)
	}