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