fuse.go

     1  // Copyright 2015 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 ssacompile
     6  
     7  import (
     8  	"fmt"
     9  
    10  	"cmd/compile/internal/ssa"
    11  	"cmd/compile/internal/ssa/block"
    12  	"cmd/compile/internal/ssa/ssaop"
    13  	"cmd/internal/src"
    14  )
    15  
    16  // fuseEarly runs fuse(f, fuseTypePlain|fuseTypeIntInRange|fuseTypeNanCheck).
    17  func fuseEarly(f *ssa.Func) {
    18  	fuse(f, fuseTypePlain|fuseTypeIntInRange|fuseTypeSingleBitDifference|fuseTypeNanCheck)
    19  }
    20  
    21  // fuseLate runs fuse(f, fuseTypePlain|fuseTypeIf|fuseTypeBranchRedirect).
    22  func fuseLate(f *ssa.Func) { fuse(f, fuseTypePlain|fuseTypeIf|fuseTypeBranchRedirect) }
    23  
    24  type fuseType uint8
    25  
    26  const (
    27  	fuseTypePlain fuseType = 1 << iota
    28  	fuseTypeIf
    29  	fuseTypeIntInRange
    30  	fuseTypeSingleBitDifference
    31  	fuseTypeNanCheck
    32  	fuseTypeBranchRedirect
    33  	fuseTypeShortCircuit
    34  )
    35  
    36  // fuse simplifies control flow by joining basic blocks.
    37  func fuse(f *ssa.Func, typ fuseType) {
    38  	for changed := true; changed; {
    39  		changed = false
    40  		// Be sure to avoid quadratic behavior in fuseBlockPlain. See issue 13554.
    41  		// Previously this was dealt with using backwards iteration, now fuseBlockPlain
    42  		// handles large runs of blocks.
    43  		for i := len(f.Blocks) - 1; i >= 0; i-- {
    44  			b := f.Blocks[i]
    45  			if typ&fuseTypeIf != 0 {
    46  				changed = fuseBlockIf(b) || changed
    47  			}
    48  			if typ&fuseTypeIntInRange != 0 {
    49  				changed = fuseIntInRange(b) || changed
    50  			}
    51  			if typ&fuseTypeSingleBitDifference != 0 {
    52  				changed = fuseSingleBitDifference(b) || changed
    53  			}
    54  			if typ&fuseTypeNanCheck != 0 {
    55  				changed = fuseNanCheck(b) || changed
    56  			}
    57  			if typ&fuseTypePlain != 0 {
    58  				changed = fuseBlockPlain(b) || changed
    59  			}
    60  			if typ&fuseTypeShortCircuit != 0 {
    61  				changed = shortcircuitBlock(b) || changed
    62  			}
    63  		}
    64  
    65  		if typ&fuseTypeBranchRedirect != 0 {
    66  			changed = fuseBranchRedirect(f) || changed
    67  		}
    68  		if changed {
    69  			f.InvalidateCFG()
    70  		}
    71  	}
    72  }
    73  
    74  // fuseBlockIf handles the following cases where s0 and s1 are empty blocks.
    75  //
    76  //	   b        b           b       b
    77  //	\ / \ /    | \  /    \ / |     | |
    78  //	 s0  s1    |  s1      s0 |     | |
    79  //	  \ /      | /         \ |     | |
    80  //	   ss      ss           ss      ss
    81  //
    82  // If all Phi ops in ss have identical variables for slots corresponding to
    83  // s0, s1 and b then the branch can be dropped.
    84  // This optimization often comes up in switch statements with multiple
    85  // expressions in a case clause:
    86  //
    87  //	switch n {
    88  //	  case 1,2,3: return 4
    89  //	}
    90  //
    91  // TODO: If ss doesn't contain any OpPhis, are s0 and s1 dead code anyway.
    92  func fuseBlockIf(b *ssa.Block) bool {
    93  	if b.Kind != block.BlockIf {
    94  		return false
    95  	}
    96  	// It doesn't matter how much Preds does s0 or s1 have.
    97  	var ss0, ss1 *ssa.Block
    98  	s0 := b.Succs[0].B
    99  	i0 := b.Succs[0].I
   100  	if s0.Kind != block.BlockPlain || !isEmpty(s0) {
   101  		s0, ss0 = b, s0
   102  	} else {
   103  		ss0 = s0.Succs[0].B
   104  		i0 = s0.Succs[0].I
   105  	}
   106  	s1 := b.Succs[1].B
   107  	i1 := b.Succs[1].I
   108  	if s1.Kind != block.BlockPlain || !isEmpty(s1) {
   109  		s1, ss1 = b, s1
   110  	} else {
   111  		ss1 = s1.Succs[0].B
   112  		i1 = s1.Succs[0].I
   113  	}
   114  	if ss0 != ss1 {
   115  		if s0.Kind == block.BlockPlain && isEmpty(s0) && s1.Kind == block.BlockPlain && isEmpty(s1) {
   116  			// Two special cases where both s0, s1 and ss are empty blocks.
   117  			if s0 == ss1 {
   118  				s0, ss0 = b, ss1
   119  			} else if ss0 == s1 {
   120  				s1, ss1 = b, ss0
   121  			} else {
   122  				return false
   123  			}
   124  		} else {
   125  			return false
   126  		}
   127  	}
   128  	ss := ss0
   129  
   130  	// s0 and s1 are equal with b if the corresponding block is missing
   131  	// (2nd, 3rd and 4th case in the figure).
   132  
   133  	for _, v := range ss.Values {
   134  		if v.Op == ssaop.OpPhi && v.Uses > 0 && v.Args[i0] != v.Args[i1] {
   135  			return false
   136  		}
   137  	}
   138  
   139  	// We do not need to redirect the Preds of s0 and s1 to ss,
   140  	// the following optimization will do this.
   141  	b.RemoveEdge(0)
   142  	if s0 != b && len(s0.Preds) == 0 {
   143  		s0.RemoveEdge(0)
   144  		// Move any (dead) values in s0 to b,
   145  		// where they will be eliminated by the next deadcode pass.
   146  		for _, v := range s0.Values {
   147  			v.Block = b
   148  		}
   149  		b.Values = append(b.Values, s0.Values...)
   150  		// Clear s0.
   151  		s0.Kind = block.BlockInvalid
   152  		s0.Values = nil
   153  		s0.Succs = nil
   154  		s0.Preds = nil
   155  	}
   156  
   157  	b.Kind = block.BlockPlain
   158  	b.Likely = ssa.BranchUnknown
   159  	b.ResetControls()
   160  	// The values in b may be dead codes, and clearing them in time may
   161  	// obtain new optimization opportunities.
   162  	// First put dead values that can be deleted into a slice walkValues.
   163  	// Then put their arguments in walkValues before resetting the dead values
   164  	// in walkValues, because the arguments may also become dead values.
   165  	walkValues := []*ssa.Value{}
   166  	for _, v := range b.Values {
   167  		if v.Uses == 0 && v.Removeable() {
   168  			walkValues = append(walkValues, v)
   169  		}
   170  	}
   171  	for len(walkValues) != 0 {
   172  		v := walkValues[len(walkValues)-1]
   173  		walkValues = walkValues[:len(walkValues)-1]
   174  		if v.Uses == 0 && v.Removeable() {
   175  			walkValues = append(walkValues, v.Args...)
   176  			v.Reset(ssaop.OpInvalid)
   177  		}
   178  	}
   179  	return true
   180  }
   181  
   182  // isEmpty reports whether b contains any live values.
   183  // There may be false positives.
   184  func isEmpty(b *ssa.Block) bool {
   185  	for _, v := range b.Values {
   186  		if v.Uses > 0 || v.Op.IsCall() || v.Op.HasSideEffects() || v.Type.IsVoid() || ssaop.OpcodeTable[v.Op].NilCheck {
   187  			return false
   188  		}
   189  	}
   190  	return true
   191  }
   192  
   193  // fuseBlockPlain handles a run of blocks with length >= 2,
   194  // whose interior has single predecessors and successors,
   195  // b must be BlockPlain, allowing it to be any node except the
   196  // last (multiple successors means not BlockPlain).
   197  // Cycles are handled and merged into b's successor.
   198  func fuseBlockPlain(b *ssa.Block) bool {
   199  	if b.Kind != block.BlockPlain {
   200  		return false
   201  	}
   202  
   203  	c := b.Succs[0].B
   204  	if len(c.Preds) != 1 || c == b { // At least 2 distinct blocks.
   205  		return false
   206  	}
   207  
   208  	// find earliest block in run.  Avoid simple cycles.
   209  	for len(b.Preds) == 1 && b.Preds[0].B != c && b.Preds[0].B.Kind == block.BlockPlain {
   210  		b = b.Preds[0].B
   211  	}
   212  
   213  	// find latest block in run.  Still beware of simple cycles.
   214  	for {
   215  		if c.Kind != block.BlockPlain {
   216  			break
   217  		} // Has exactly 1 successor
   218  		cNext := c.Succs[0].B
   219  		if cNext == b {
   220  			break
   221  		} // not a cycle
   222  		if len(cNext.Preds) != 1 {
   223  			break
   224  		} // no other incoming edge
   225  		c = cNext
   226  	}
   227  
   228  	// Try to preserve any statement marks on the ends of blocks; move values to C
   229  	var b_next *ssa.Block
   230  	for bx := b; bx != c; bx = b_next {
   231  		// For each bx with an end-of-block statement marker,
   232  		// try to move it to a value in the next block,
   233  		// or to the next block's end, if possible.
   234  		b_next = bx.Succs[0].B
   235  		if bx.Pos.IsStmt() == src.PosIsStmt {
   236  			l := bx.Pos.Line() // looking for another place to mark for line l
   237  			outOfOrder := false
   238  			for _, v := range b_next.Values {
   239  				if v.Pos.IsStmt() == src.PosNotStmt {
   240  					continue
   241  				}
   242  				if l == v.Pos.Line() { // Found a Value with same line, therefore done.
   243  					v.Pos = v.Pos.WithIsStmt()
   244  					l = 0
   245  					break
   246  				}
   247  				if l < v.Pos.Line() {
   248  					// The order of values in a block is not specified so OOO in a block is not interesting,
   249  					// but they do all come before the end of the block, so this disqualifies attaching to end of b_next.
   250  					outOfOrder = true
   251  				}
   252  			}
   253  			if l != 0 && !outOfOrder && (b_next.Pos.Line() == l || b_next.Pos.IsStmt() != src.PosIsStmt) {
   254  				b_next.Pos = bx.Pos.WithIsStmt()
   255  			}
   256  		}
   257  		// move all of bx's values to c (note containing loop excludes c)
   258  		for _, v := range bx.Values {
   259  			v.Block = c
   260  		}
   261  	}
   262  
   263  	// Compute the total number of values and find the largest value slice in the run, to maximize chance of storage reuse.
   264  	total := 0
   265  	totalBeforeMax := 0 // number of elements preceding the maximum block (i.e. its position in the result).
   266  	max_b := b          // block with maximum capacity
   267  
   268  	for bx := b; ; bx = bx.Succs[0].B {
   269  		if cap(bx.Values) > cap(max_b.Values) {
   270  			totalBeforeMax = total
   271  			max_b = bx
   272  		}
   273  		total += len(bx.Values)
   274  		if bx == c {
   275  			break
   276  		}
   277  	}
   278  
   279  	// Use c's storage if fused blocks will fit, else use the max if that will fit, else allocate new storage.
   280  
   281  	// Take care to avoid c.Values pointing to b.valstorage.
   282  	// See golang.org/issue/18602.
   283  
   284  	// It's important to keep the elements in the same order; maintenance of
   285  	// debugging information depends on the order of *Values in Blocks.
   286  	// This can also cause changes in the order (which may affect other
   287  	// optimizations and possibly compiler output) for 32-vs-64 bit compilation
   288  	// platforms (word size affects allocation bucket size affects slice capacity).
   289  
   290  	// figure out what slice will hold the values,
   291  	// preposition the destination elements if not allocating new storage
   292  	var t []*ssa.Value
   293  	if total <= len(c.Valstorage) {
   294  		t = c.Valstorage[:total]
   295  		max_b = c
   296  		totalBeforeMax = total - len(c.Values)
   297  		copy(t[totalBeforeMax:], c.Values)
   298  	} else if total <= cap(max_b.Values) { // in place, somewhere
   299  		t = max_b.Values[0:total]
   300  		copy(t[totalBeforeMax:], max_b.Values)
   301  	} else {
   302  		t = make([]*ssa.Value, total)
   303  		max_b = nil
   304  	}
   305  
   306  	// copy the values
   307  	copyTo := 0
   308  	for bx := b; ; bx = bx.Succs[0].B {
   309  		if bx != max_b {
   310  			copy(t[copyTo:], bx.Values)
   311  		} else if copyTo != totalBeforeMax { // trust but verify.
   312  			panic(fmt.Errorf("totalBeforeMax (%d) != copyTo (%d), max_b=%v, b=%v, c=%v", totalBeforeMax, copyTo, max_b, b, c))
   313  		}
   314  		if bx == c {
   315  			break
   316  		}
   317  		copyTo += len(bx.Values)
   318  	}
   319  	c.Values = t
   320  
   321  	// replace b->c edge with preds(b) -> c
   322  	c.Predstorage[0] = ssa.Edge{}
   323  	if len(b.Preds) > len(b.Predstorage) {
   324  		c.Preds = b.Preds
   325  	} else {
   326  		c.Preds = append(c.Predstorage[:0], b.Preds...)
   327  	}
   328  	for i, e := range c.Preds {
   329  		p := e.B
   330  		p.Succs[e.I] = ssa.Edge{B: c, I: i}
   331  	}
   332  	f := b.Func
   333  	if f.Entry == b {
   334  		f.Entry = c
   335  	}
   336  
   337  	// trash b's fields, just in case
   338  	for bx := b; bx != c; bx = b_next {
   339  		b_next = bx.Succs[0].B
   340  
   341  		bx.Kind = block.BlockInvalid
   342  		bx.Values = nil
   343  		bx.Preds = nil
   344  		bx.Succs = nil
   345  	}
   346  	return true
   347  }
   348
View as plain text