Home | History | Annotate | Download | only in 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 // fuse simplifies control flow by joining basic blocks.
      8 func fuse(f *Func) {
      9 	for changed := true; changed; {
     10 		changed = false
     11 		// Fuse from end to beginning, to avoid quadratic behavior in fuseBlockPlain. See issue 13554.
     12 		for i := len(f.Blocks) - 1; i >= 0; i-- {
     13 			b := f.Blocks[i]
     14 			changed = fuseBlockIf(b) || changed
     15 			changed = fuseBlockPlain(b) || changed
     16 		}
     17 	}
     18 }
     19 
     20 // fuseBlockIf handles the following cases where s0 and s1 are empty blocks.
     21 //
     22 //   b        b        b      b
     23 //  / \      | \      / |    | |
     24 // s0  s1    |  s1   s0 |    | |
     25 //  \ /      | /      \ |    | |
     26 //   ss      ss        ss     ss
     27 //
     28 // If all Phi ops in ss have identical variables for slots corresponding to
     29 // s0, s1 and b then the branch can be dropped.
     30 // This optimization often comes up in switch statements with multiple
     31 // expressions in a case clause:
     32 //   switch n {
     33 //     case 1,2,3: return 4
     34 //   }
     35 // TODO: If ss doesn't contain any OpPhis, are s0 and s1 dead code anyway.
     36 func fuseBlockIf(b *Block) bool {
     37 	if b.Kind != BlockIf {
     38 		return false
     39 	}
     40 
     41 	var ss0, ss1 *Block
     42 	s0 := b.Succs[0].b
     43 	i0 := b.Succs[0].i
     44 	if s0.Kind != BlockPlain || len(s0.Preds) != 1 || len(s0.Values) != 0 {
     45 		s0, ss0 = b, s0
     46 	} else {
     47 		ss0 = s0.Succs[0].b
     48 		i0 = s0.Succs[0].i
     49 	}
     50 	s1 := b.Succs[1].b
     51 	i1 := b.Succs[1].i
     52 	if s1.Kind != BlockPlain || len(s1.Preds) != 1 || len(s1.Values) != 0 {
     53 		s1, ss1 = b, s1
     54 	} else {
     55 		ss1 = s1.Succs[0].b
     56 		i1 = s1.Succs[0].i
     57 	}
     58 
     59 	if ss0 != ss1 {
     60 		return false
     61 	}
     62 	ss := ss0
     63 
     64 	// s0 and s1 are equal with b if the corresponding block is missing
     65 	// (2nd, 3rd and 4th case in the figure).
     66 
     67 	for _, v := range ss.Values {
     68 		if v.Op == OpPhi && v.Uses > 0 && v.Args[i0] != v.Args[i1] {
     69 			return false
     70 		}
     71 	}
     72 
     73 	// Now we have two of following b->ss, b->s0->ss and b->s1->ss,
     74 	// with s0 and s1 empty if exist.
     75 	// We can replace it with b->ss without if all OpPhis in ss
     76 	// have identical predecessors (verified above).
     77 	// No critical edge is introduced because b will have one successor.
     78 	if s0 != b && s1 != b {
     79 		// Replace edge b->s0->ss with b->ss.
     80 		// We need to keep a slot for Phis corresponding to b.
     81 		b.Succs[0] = Edge{ss, i0}
     82 		ss.Preds[i0] = Edge{b, 0}
     83 		b.removeEdge(1)
     84 		s1.removeEdge(0)
     85 	} else if s0 != b {
     86 		b.removeEdge(0)
     87 		s0.removeEdge(0)
     88 	} else if s1 != b {
     89 		b.removeEdge(1)
     90 		s1.removeEdge(0)
     91 	} else {
     92 		b.removeEdge(1)
     93 	}
     94 	b.Kind = BlockPlain
     95 	b.SetControl(nil)
     96 
     97 	// Trash the empty blocks s0 & s1.
     98 	if s0 != b {
     99 		s0.Kind = BlockInvalid
    100 		s0.Values = nil
    101 		s0.Succs = nil
    102 		s0.Preds = nil
    103 	}
    104 	if s1 != b {
    105 		s1.Kind = BlockInvalid
    106 		s1.Values = nil
    107 		s1.Succs = nil
    108 		s1.Preds = nil
    109 	}
    110 	return true
    111 }
    112 
    113 func fuseBlockPlain(b *Block) bool {
    114 	if b.Kind != BlockPlain {
    115 		return false
    116 	}
    117 
    118 	c := b.Succs[0].b
    119 	if len(c.Preds) != 1 {
    120 		return false
    121 	}
    122 
    123 	// move all of b's values to c.
    124 	for _, v := range b.Values {
    125 		v.Block = c
    126 	}
    127 	// Use whichever value slice is larger, in the hopes of avoiding growth.
    128 	// However, take care to avoid c.Values pointing to b.valstorage.
    129 	// See golang.org/issue/18602.
    130 	if cap(c.Values) >= cap(b.Values) || len(b.Values) <= len(b.valstorage) {
    131 		c.Values = append(c.Values, b.Values...)
    132 	} else {
    133 		c.Values = append(b.Values, c.Values...)
    134 	}
    135 
    136 	// replace b->c edge with preds(b) -> c
    137 	c.predstorage[0] = Edge{}
    138 	if len(b.Preds) > len(b.predstorage) {
    139 		c.Preds = b.Preds
    140 	} else {
    141 		c.Preds = append(c.predstorage[:0], b.Preds...)
    142 	}
    143 	for i, e := range c.Preds {
    144 		p := e.b
    145 		p.Succs[e.i] = Edge{c, i}
    146 	}
    147 	f := b.Func
    148 	if f.Entry == b {
    149 		f.Entry = c
    150 	}
    151 	f.invalidateCFG()
    152 
    153 	// trash b, just in case
    154 	b.Kind = BlockInvalid
    155 	b.Values = nil
    156 	b.Preds = nil
    157 	b.Succs = nil
    158 	return true
    159 }
    160