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