likelyadjust.go

     1  // Copyright 2016 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package ssa
     6  
     7  import (
     8  	"fmt"
     9  )
    10  
    11  type loop struct {
    12  	header *Block // The header node of this (reducible) loop
    13  	outer  *loop  // loop containing this loop
    14  
    15  	// Next three fields used by regalloc and/or
    16  	// aid in computation of inner-ness and list of blocks.
    17  	nBlocks int32 // Number of blocks in this loop but not within inner loops
    18  	depth   int16 // Nesting depth of the loop; 1 is outermost.
    19  	isInner bool  // True if never discovered to contain a loop
    20  
    21  	// True if all paths through the loop have a call.
    22  	// Computed and used by regalloc; stored here for convenience.
    23  	containsUnavoidableCall bool
    24  }
    25  
    26  // outerinner records that outer contains inner
    27  func (sdom SparseTree) outerinner(outer, inner *loop) {
    28  	// There could be other outer loops found in some random order,
    29  	// locate the new outer loop appropriately among them.
    30  
    31  	// Outer loop headers dominate inner loop headers.
    32  	// Use this to put the "new" "outer" loop in the right place.
    33  	oldouter := inner.outer
    34  	for oldouter != nil && sdom.isAncestor(outer.header, oldouter.header) {
    35  		inner = oldouter
    36  		oldouter = inner.outer
    37  	}
    38  	if outer == oldouter {
    39  		return
    40  	}
    41  	if oldouter != nil {
    42  		sdom.outerinner(oldouter, outer)
    43  	}
    44  
    45  	inner.outer = outer
    46  	outer.isInner = false
    47  }
    48  
    49  type loopnest struct {
    50  	f              *Func
    51  	b2l            []*loop
    52  	po             []*Block
    53  	sdom           SparseTree
    54  	loops          []*loop
    55  	hasIrreducible bool // TODO current treatment of irreducible loops is very flaky, if accurate loops are needed, must punt at function level.
    56  }
    57  
    58  const (
    59  	blDEFAULT = 0
    60  	blMin     = blDEFAULT
    61  	blCALL    = 1
    62  	blRET     = 2
    63  	blEXIT    = 3
    64  )
    65  
    66  var bllikelies = [4]string{"default", "call", "ret", "exit"}
    67  
    68  func describePredictionAgrees(b *Block, prediction BranchPrediction) string {
    69  	s := ""
    70  	if prediction == b.Likely {
    71  		s = " (agrees with previous)"
    72  	} else if b.Likely != BranchUnknown {
    73  		s = " (disagrees with previous, ignored)"
    74  	}
    75  	return s
    76  }
    77  
    78  func describeBranchPrediction(f *Func, b *Block, likely, not int8, prediction BranchPrediction) {
    79  	f.Warnl(b.Pos, "Branch prediction rule %s < %s%s",
    80  		bllikelies[likely-blMin], bllikelies[not-blMin], describePredictionAgrees(b, prediction))
    81  }
    82  
    83  func likelyadjust(f *Func) {
    84  	// The values assigned to certain and local only matter
    85  	// in their rank order.  0 is default, more positive
    86  	// is less likely. It's possible to assign a negative
    87  	// unlikeliness (though not currently the case).
    88  	certain := f.Cache.allocInt8Slice(f.NumBlocks()) // In the long run, all outcomes are at least this bad. Mainly for Exit
    89  	defer f.Cache.freeInt8Slice(certain)
    90  	local := f.Cache.allocInt8Slice(f.NumBlocks()) // for our immediate predecessors.
    91  	defer f.Cache.freeInt8Slice(local)
    92  
    93  	po := f.postorder()
    94  	nest := f.loopnest()
    95  	b2l := nest.b2l
    96  
    97  	for _, b := range po {
    98  		switch b.Kind {
    99  		case BlockExit:
   100  			// Very unlikely.
   101  			local[b.ID] = blEXIT
   102  			certain[b.ID] = blEXIT
   103  
   104  			// Ret, it depends.
   105  		case BlockRet, BlockRetJmp:
   106  			local[b.ID] = blRET
   107  			certain[b.ID] = blRET
   108  
   109  			// Calls. TODO not all calls are equal, names give useful clues.
   110  			// Any name-based heuristics are only relative to other calls,
   111  			// and less influential than inferences from loop structure.
   112  		case BlockDefer:
   113  			local[b.ID] = blCALL
   114  			certain[b.ID] = max(blCALL, certain[b.Succs[0].b.ID])
   115  
   116  		default:
   117  			if len(b.Succs) == 1 {
   118  				certain[b.ID] = certain[b.Succs[0].b.ID]
   119  			} else if len(b.Succs) == 2 {
   120  				// If successor is an unvisited backedge, it's in loop and we don't care.
   121  				// Its default unlikely is also zero which is consistent with favoring loop edges.
   122  				// Notice that this can act like a "reset" on unlikeliness at loops; the
   123  				// default "everything returns" unlikeliness is erased by min with the
   124  				// backedge likeliness; however a loop with calls on every path will be
   125  				// tagged with call cost. Net effect is that loop entry is favored.
   126  				b0 := b.Succs[0].b.ID
   127  				b1 := b.Succs[1].b.ID
   128  				certain[b.ID] = min(certain[b0], certain[b1])
   129  
   130  				l := b2l[b.ID]
   131  				l0 := b2l[b0]
   132  				l1 := b2l[b1]
   133  
   134  				prediction := b.Likely
   135  				// Weak loop heuristic -- both source and at least one dest are in loops,
   136  				// and there is a difference in the destinations.
   137  				// TODO what is best arrangement for nested loops?
   138  				if l != nil && l0 != l1 {
   139  					noprediction := false
   140  					switch {
   141  					// prefer not to exit loops
   142  					case l1 == nil:
   143  						prediction = BranchLikely
   144  					case l0 == nil:
   145  						prediction = BranchUnlikely
   146  
   147  						// prefer to stay in loop, not exit to outer.
   148  					case l == l0:
   149  						prediction = BranchLikely
   150  					case l == l1:
   151  						prediction = BranchUnlikely
   152  					default:
   153  						noprediction = true
   154  					}
   155  					if f.pass.debug > 0 && !noprediction {
   156  						f.Warnl(b.Pos, "Branch prediction rule stay in loop%s",
   157  							describePredictionAgrees(b, prediction))
   158  					}
   159  
   160  				} else {
   161  					// Lacking loop structure, fall back on heuristics.
   162  					if certain[b1] > certain[b0] {
   163  						prediction = BranchLikely
   164  						if f.pass.debug > 0 {
   165  							describeBranchPrediction(f, b, certain[b0], certain[b1], prediction)
   166  						}
   167  					} else if certain[b0] > certain[b1] {
   168  						prediction = BranchUnlikely
   169  						if f.pass.debug > 0 {
   170  							describeBranchPrediction(f, b, certain[b1], certain[b0], prediction)
   171  						}
   172  					} else if local[b1] > local[b0] {
   173  						prediction = BranchLikely
   174  						if f.pass.debug > 0 {
   175  							describeBranchPrediction(f, b, local[b0], local[b1], prediction)
   176  						}
   177  					} else if local[b0] > local[b1] {
   178  						prediction = BranchUnlikely
   179  						if f.pass.debug > 0 {
   180  							describeBranchPrediction(f, b, local[b1], local[b0], prediction)
   181  						}
   182  					}
   183  				}
   184  				if b.Likely != prediction {
   185  					if b.Likely == BranchUnknown {
   186  						b.Likely = prediction
   187  					}
   188  				}
   189  			}
   190  			// Look for calls in the block.  If there is one, make this block unlikely.
   191  			for _, v := range b.Values {
   192  				if opcodeTable[v.Op].call {
   193  					local[b.ID] = blCALL
   194  					certain[b.ID] = max(blCALL, certain[b.Succs[0].b.ID])
   195  					break
   196  				}
   197  			}
   198  		}
   199  		if f.pass.debug > 2 {
   200  			f.Warnl(b.Pos, "BP: Block %s, local=%s, certain=%s", b, bllikelies[local[b.ID]-blMin], bllikelies[certain[b.ID]-blMin])
   201  		}
   202  
   203  	}
   204  }
   205  
   206  func (l *loop) String() string {
   207  	return fmt.Sprintf("hdr:%s", l.header)
   208  }
   209  
   210  func (l *loop) LongString() string {
   211  	i := ""
   212  	o := ""
   213  	if l.isInner {
   214  		i = ", INNER"
   215  	}
   216  	if l.outer != nil {
   217  		o = ", o=" + l.outer.header.String()
   218  	}
   219  	return fmt.Sprintf("hdr:%s%s%s", l.header, i, o)
   220  }
   221  
   222  func (l *loop) isWithinOrEq(ll *loop) bool {
   223  	if ll == nil { // nil means whole program
   224  		return true
   225  	}
   226  	for ; l != nil; l = l.outer {
   227  		if l == ll {
   228  			return true
   229  		}
   230  	}
   231  	return false
   232  }
   233  
   234  // nearestOuterLoop returns the outer loop of loop most nearly
   235  // containing block b; the header must dominate b.  loop itself
   236  // is assumed to not be that loop. For acceptable performance,
   237  // we're relying on loop nests to not be terribly deep.
   238  func (l *loop) nearestOuterLoop(sdom SparseTree, b *Block) *loop {
   239  	var o *loop
   240  	for o = l.outer; o != nil && !sdom.IsAncestorEq(o.header, b); o = o.outer {
   241  	}
   242  	return o
   243  }
   244  
   245  func loopnestfor(f *Func) *loopnest {
   246  	po := f.postorder()
   247  	sdom := f.Sdom()
   248  	b2l := make([]*loop, f.NumBlocks())
   249  	loops := make([]*loop, 0)
   250  	visited := f.Cache.allocBoolSlice(f.NumBlocks())
   251  	defer f.Cache.freeBoolSlice(visited)
   252  	sawIrred := false
   253  
   254  	if f.pass.debug > 2 {
   255  		fmt.Printf("loop finding in %s\n", f.Name)
   256  	}
   257  
   258  	// Reducible-loop-nest-finding.
   259  	for _, b := range po {
   260  		if f.pass != nil && f.pass.debug > 3 {
   261  			fmt.Printf("loop finding at %s\n", b)
   262  		}
   263  
   264  		var innermost *loop // innermost header reachable from this block
   265  
   266  		// IF any successor s of b is in a loop headed by h
   267  		// AND h dominates b
   268  		// THEN b is in the loop headed by h.
   269  		//
   270  		// Choose the first/innermost such h.
   271  		//
   272  		// IF s itself dominates b, then s is a loop header;
   273  		// and there may be more than one such s.
   274  		// Since there's at most 2 successors, the inner/outer ordering
   275  		// between them can be established with simple comparisons.
   276  		for _, e := range b.Succs {
   277  			bb := e.b
   278  			l := b2l[bb.ID]
   279  
   280  			if sdom.IsAncestorEq(bb, b) { // Found a loop header
   281  				if f.pass != nil && f.pass.debug > 4 {
   282  					fmt.Printf("loop finding    succ %s of %s is header\n", bb.String(), b.String())
   283  				}
   284  				if l == nil {
   285  					l = &loop{header: bb, isInner: true}
   286  					loops = append(loops, l)
   287  					b2l[bb.ID] = l
   288  				}
   289  			} else if !visited[bb.ID] { // Found an irreducible loop
   290  				sawIrred = true
   291  				if f.pass != nil && f.pass.debug > 4 {
   292  					fmt.Printf("loop finding    succ %s of %s is IRRED, in %s\n", bb.String(), b.String(), f.Name)
   293  				}
   294  			} else if l != nil {
   295  				// TODO handle case where l is irreducible.
   296  				// Perhaps a loop header is inherited.
   297  				// is there any loop containing our successor whose
   298  				// header dominates b?
   299  				if !sdom.IsAncestorEq(l.header, b) {
   300  					l = l.nearestOuterLoop(sdom, b)
   301  				}
   302  				if f.pass != nil && f.pass.debug > 4 {
   303  					if l == nil {
   304  						fmt.Printf("loop finding    succ %s of %s has no loop\n", bb.String(), b.String())
   305  					} else {
   306  						fmt.Printf("loop finding    succ %s of %s provides loop with header %s\n", bb.String(), b.String(), l.header.String())
   307  					}
   308  				}
   309  			} else { // No loop
   310  				if f.pass != nil && f.pass.debug > 4 {
   311  					fmt.Printf("loop finding    succ %s of %s has no loop\n", bb.String(), b.String())
   312  				}
   313  
   314  			}
   315  
   316  			if l == nil || innermost == l {
   317  				continue
   318  			}
   319  
   320  			if innermost == nil {
   321  				innermost = l
   322  				continue
   323  			}
   324  
   325  			if sdom.isAncestor(innermost.header, l.header) {
   326  				sdom.outerinner(innermost, l)
   327  				innermost = l
   328  			} else if sdom.isAncestor(l.header, innermost.header) {
   329  				sdom.outerinner(l, innermost)
   330  			}
   331  		}
   332  
   333  		if innermost != nil {
   334  			b2l[b.ID] = innermost
   335  			innermost.nBlocks++
   336  		}
   337  		visited[b.ID] = true
   338  	}
   339  
   340  	// Compute depths.
   341  	for _, l := range loops {
   342  		if l.depth != 0 {
   343  			// Already computed because it is an ancestor of
   344  			// a previous loop.
   345  			continue
   346  		}
   347  		// Find depth by walking up the loop tree.
   348  		d := int16(0)
   349  		for x := l; x != nil; x = x.outer {
   350  			if x.depth != 0 {
   351  				d += x.depth
   352  				break
   353  			}
   354  			d++
   355  		}
   356  		// Set depth for every ancestor.
   357  		for x := l; x != nil; x = x.outer {
   358  			if x.depth != 0 {
   359  				break
   360  			}
   361  			x.depth = d
   362  			d--
   363  		}
   364  	}
   365  	// Double-check depths.
   366  	for _, l := range loops {
   367  		want := int16(1)
   368  		if l.outer != nil {
   369  			want = l.outer.depth + 1
   370  		}
   371  		if l.depth != want {
   372  			l.header.Fatalf("bad depth calculation for loop %s: got %d want %d", l.header, l.depth, want)
   373  		}
   374  	}
   375  
   376  	ln := &loopnest{f: f, b2l: b2l, po: po, sdom: sdom, loops: loops, hasIrreducible: sawIrred}
   377  
   378  	// Curious about the loopiness? "-d=ssa/likelyadjust/stats"
   379  	if f.pass != nil && f.pass.stats > 0 && len(loops) > 0 {
   380  
   381  		// Note stats for non-innermost loops are slightly flawed because
   382  		// they don't account for inner loop exits that span multiple levels.
   383  
   384  		for _, l := range loops {
   385  			inner := 0
   386  			if l.isInner {
   387  				inner++
   388  			}
   389  
   390  			f.LogStat("loopstats in "+f.Name+":",
   391  				l.depth, "depth",
   392  				inner, "is_inner", l.nBlocks, "n_blocks")
   393  		}
   394  	}
   395  
   396  	if f.pass != nil && f.pass.debug > 1 && len(loops) > 0 {
   397  		fmt.Printf("Loops in %s:\n", f.Name)
   398  		for _, l := range loops {
   399  			fmt.Printf("%s, b=", l.LongString())
   400  			for _, b := range f.Blocks {
   401  				if b2l[b.ID] == l {
   402  					fmt.Printf(" %s", b)
   403  				}
   404  			}
   405  			fmt.Print("\n")
   406  		}
   407  		fmt.Printf("Nonloop blocks in %s:", f.Name)
   408  		for _, b := range f.Blocks {
   409  			if b2l[b.ID] == nil {
   410  				fmt.Printf(" %s", b)
   411  			}
   412  		}
   413  		fmt.Print("\n")
   414  	}
   415  	return ln
   416  }
   417  
   418  // depth returns the loop nesting level of block b.
   419  func (ln *loopnest) depth(b ID) int16 {
   420  	if l := ln.b2l[b]; l != nil {
   421  		return l.depth
   422  	}
   423  	return 0
   424  }
   425
View as plain text