fuse.go

Documentation: cmd/compile/internal/ssa

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