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 ssa
     6  
     7  import (
     8  	"cmd/internal/src"
     9  )
    10  
    11  // fuseEarly runs fuse(f, fuseTypePlain|fuseTypeIntInRange).
    12  func fuseEarly(f *Func) { fuse(f, fuseTypePlain|fuseTypeIntInRange) }
    13  
    14  // fuseLate runs fuse(f, fuseTypePlain|fuseTypeIf|fuseTypeBranchRedirect).
    15  func fuseLate(f *Func) { fuse(f, fuseTypePlain|fuseTypeIf|fuseTypeBranchRedirect) }
    16  
    17  type fuseType uint8
    18  
    19  const (
    20  	fuseTypePlain fuseType = 1 << iota
    21  	fuseTypeIf
    22  	fuseTypeIntInRange
    23  	fuseTypeBranchRedirect
    24  	fuseTypeShortCircuit
    25  )
    26  
    27  // fuse simplifies control flow by joining basic blocks.
    28  func fuse(f *Func, typ fuseType) {
    29  	for changed := true; changed; {
    30  		changed = false
    31  		// Fuse from end to beginning, to avoid quadratic behavior in fuseBlockPlain. See issue 13554.
    32  		for i := len(f.Blocks) - 1; i >= 0; i-- {
    33  			b := f.Blocks[i]
    34  			if typ&fuseTypeIf != 0 {
    35  				changed = fuseBlockIf(b) || changed
    36  			}
    37  			if typ&fuseTypeIntInRange != 0 {
    38  				changed = fuseIntegerComparisons(b) || changed
    39  			}
    40  			if typ&fuseTypePlain != 0 {
    41  				changed = fuseBlockPlain(b) || changed
    42  			}
    43  			if typ&fuseTypeShortCircuit != 0 {
    44  				changed = shortcircuitBlock(b) || changed
    45  			}
    46  		}
    47  		if typ&fuseTypeBranchRedirect != 0 {
    48  			changed = fuseBranchRedirect(f) || changed
    49  		}
    50  		if changed {
    51  			f.invalidateCFG()
    52  		}
    53  	}
    54  }
    55  
    56  // fuseBlockIf handles the following cases where s0 and s1 are empty blocks.
    57  //
    58  //       b        b           b       b
    59  //    \ / \ /    | \  /    \ / |     | |
    60  //     s0  s1    |  s1      s0 |     | |
    61  //      \ /      | /         \ |     | |
    62  //       ss      ss           ss      ss
    63  //
    64  // If all Phi ops in ss have identical variables for slots corresponding to
    65  // s0, s1 and b then the branch can be dropped.
    66  // This optimization often comes up in switch statements with multiple
    67  // expressions in a case clause:
    68  //   switch n {
    69  //     case 1,2,3: return 4
    70  //   }
    71  // TODO: If ss doesn't contain any OpPhis, are s0 and s1 dead code anyway.
    72  func fuseBlockIf(b *Block) bool {
    73  	if b.Kind != BlockIf {
    74  		return false
    75  	}
    76  	// It doesn't matter how much Preds does s0 or s1 have.
    77  	var ss0, ss1 *Block
    78  	s0 := b.Succs[0].b
    79  	i0 := b.Succs[0].i
    80  	if s0.Kind != BlockPlain || !isEmpty(s0) {
    81  		s0, ss0 = b, s0
    82  	} else {
    83  		ss0 = s0.Succs[0].b
    84  		i0 = s0.Succs[0].i
    85  	}
    86  	s1 := b.Succs[1].b
    87  	i1 := b.Succs[1].i
    88  	if s1.Kind != BlockPlain || !isEmpty(s1) {
    89  		s1, ss1 = b, s1
    90  	} else {
    91  		ss1 = s1.Succs[0].b
    92  		i1 = s1.Succs[0].i
    93  	}
    94  	if ss0 != ss1 {
    95  		if s0.Kind == BlockPlain && isEmpty(s0) && s1.Kind == BlockPlain && isEmpty(s1) {
    96  			// Two special cases where both s0, s1 and ss are empty blocks.
    97  			if s0 == ss1 {
    98  				s0, ss0 = b, ss1
    99  			} else if ss0 == s1 {
   100  				s1, ss1 = b, ss0
   101  			} else {
   102  				return false
   103  			}
   104  		} else {
   105  			return false
   106  		}
   107  	}
   108  	ss := ss0
   109  
   110  	// s0 and s1 are equal with b if the corresponding block is missing
   111  	// (2nd, 3rd and 4th case in the figure).
   112  
   113  	for _, v := range ss.Values {
   114  		if v.Op == OpPhi && v.Uses > 0 && v.Args[i0] != v.Args[i1] {
   115  			return false
   116  		}
   117  	}
   118  
   119  	// We do not need to redirect the Preds of s0 and s1 to ss,
   120  	// the following optimization will do this.
   121  	b.removeEdge(0)
   122  	if s0 != b && len(s0.Preds) == 0 {
   123  		s0.removeEdge(0)
   124  		// Move any (dead) values in s0 to b,
   125  		// where they will be eliminated by the next deadcode pass.
   126  		for _, v := range s0.Values {
   127  			v.Block = b
   128  		}
   129  		b.Values = append(b.Values, s0.Values...)
   130  		// Clear s0.
   131  		s0.Kind = BlockInvalid
   132  		s0.Values = nil
   133  		s0.Succs = nil
   134  		s0.Preds = nil
   135  	}
   136  
   137  	b.Kind = BlockPlain
   138  	b.Likely = BranchUnknown
   139  	b.ResetControls()
   140  	// The values in b may be dead codes, and clearing them in time may
   141  	// obtain new optimization opportunities.
   142  	// First put dead values that can be deleted into a slice walkValues.
   143  	// Then put their arguments in walkValues before resetting the dead values
   144  	// in walkValues, because the arguments may also become dead values.
   145  	walkValues := []*Value{}
   146  	for _, v := range b.Values {
   147  		if v.Uses == 0 && v.removeable() {
   148  			walkValues = append(walkValues, v)
   149  		}
   150  	}
   151  	for len(walkValues) != 0 {
   152  		v := walkValues[len(walkValues)-1]
   153  		walkValues = walkValues[:len(walkValues)-1]
   154  		if v.Uses == 0 && v.removeable() {
   155  			walkValues = append(walkValues, v.Args...)
   156  			v.reset(OpInvalid)
   157  		}
   158  	}
   159  	return true
   160  }
   161  
   162  // isEmpty reports whether b contains any live values.
   163  // There may be false positives.
   164  func isEmpty(b *Block) bool {
   165  	for _, v := range b.Values {
   166  		if v.Uses > 0 || v.Op.IsCall() || v.Op.HasSideEffects() || v.Type.IsVoid() {
   167  			return false
   168  		}
   169  	}
   170  	return true
   171  }
   172  
   173  func fuseBlockPlain(b *Block) bool {
   174  	if b.Kind != BlockPlain {
   175  		return false
   176  	}
   177  
   178  	c := b.Succs[0].b
   179  	if len(c.Preds) != 1 {
   180  		return false
   181  	}
   182  
   183  	// If a block happened to end in a statement marker,
   184  	// try to preserve it.
   185  	if b.Pos.IsStmt() == src.PosIsStmt {
   186  		l := b.Pos.Line()
   187  		for _, v := range c.Values {
   188  			if v.Pos.IsStmt() == src.PosNotStmt {
   189  				continue
   190  			}
   191  			if l == v.Pos.Line() {
   192  				v.Pos = v.Pos.WithIsStmt()
   193  				l = 0
   194  				break
   195  			}
   196  		}
   197  		if l != 0 && c.Pos.Line() == l {
   198  			c.Pos = c.Pos.WithIsStmt()
   199  		}
   200  	}
   201  
   202  	// move all of b's values to c.
   203  	for _, v := range b.Values {
   204  		v.Block = c
   205  	}
   206  	// Use whichever value slice is larger, in the hopes of avoiding growth.
   207  	// However, take care to avoid c.Values pointing to b.valstorage.
   208  	// See golang.org/issue/18602.
   209  	// It's important to keep the elements in the same order; maintenance of
   210  	// debugging information depends on the order of *Values in Blocks.
   211  	// This can also cause changes in the order (which may affect other
   212  	// optimizations and possibly compiler output) for 32-vs-64 bit compilation
   213  	// platforms (word size affects allocation bucket size affects slice capacity).
   214  	if cap(c.Values) >= cap(b.Values) || len(b.Values) <= len(b.valstorage) {
   215  		bl := len(b.Values)
   216  		cl := len(c.Values)
   217  		var t []*Value // construct t = b.Values followed-by c.Values, but with attention to allocation.
   218  		if cap(c.Values) < bl+cl {
   219  			// reallocate
   220  			t = make([]*Value, bl+cl)
   221  		} else {
   222  			// in place.
   223  			t = c.Values[0 : bl+cl]
   224  		}
   225  		copy(t[bl:], c.Values) // possibly in-place
   226  		c.Values = t
   227  		copy(c.Values, b.Values)
   228  	} else {
   229  		c.Values = append(b.Values, c.Values...)
   230  	}
   231  
   232  	// replace b->c edge with preds(b) -> c
   233  	c.predstorage[0] = Edge{}
   234  	if len(b.Preds) > len(b.predstorage) {
   235  		c.Preds = b.Preds
   236  	} else {
   237  		c.Preds = append(c.predstorage[:0], b.Preds...)
   238  	}
   239  	for i, e := range c.Preds {
   240  		p := e.b
   241  		p.Succs[e.i] = Edge{c, i}
   242  	}
   243  	f := b.Func
   244  	if f.Entry == b {
   245  		f.Entry = c
   246  	}
   247  
   248  	// trash b, just in case
   249  	b.Kind = BlockInvalid
   250  	b.Values = nil
   251  	b.Preds = nil
   252  	b.Succs = nil
   253  	return true
   254  }
   255
View as plain text