Source file src/pkg/cmd/compile/internal/ssa/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	// 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