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

View as plain text