Source file src/pkg/cmd/compile/internal/ssa/trim.go

     1	// Copyright 2016 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	// trim removes blocks with no code in them.
     8	// These blocks were inserted to remove critical edges.
     9	func trim(f *Func) {
    10		n := 0
    11		for _, b := range f.Blocks {
    12			if !trimmableBlock(b) {
    13				f.Blocks[n] = b
    14				n++
    15				continue
    16			}
    17	
    18			// Splice b out of the graph. NOTE: `mergePhi` depends on the
    19			// order, in which the predecessors edges are merged here.
    20			p, i := b.Preds[0].b, b.Preds[0].i
    21			s, j := b.Succs[0].b, b.Succs[0].i
    22			ns := len(s.Preds)
    23			p.Succs[i] = Edge{s, j}
    24			s.Preds[j] = Edge{p, i}
    25	
    26			for _, e := range b.Preds[1:] {
    27				p, i := e.b, e.i
    28				p.Succs[i] = Edge{s, len(s.Preds)}
    29				s.Preds = append(s.Preds, Edge{p, i})
    30			}
    31	
    32			// If `s` had more than one predecessor, update its phi-ops to
    33			// account for the merge.
    34			if ns > 1 {
    35				for _, v := range s.Values {
    36					if v.Op == OpPhi {
    37						mergePhi(v, j, b)
    38					}
    39				}
    40				// Remove the phi-ops from `b` if they were merged into the
    41				// phi-ops of `s`.
    42				k := 0
    43				for _, v := range b.Values {
    44					if v.Op == OpPhi {
    45						if v.Uses == 0 {
    46							v.resetArgs()
    47							continue
    48						}
    49						// Pad the arguments of the remaining phi-ops so
    50						// they match the new predecessor count of `s`.
    51						// Since s did not have a Phi op corresponding to
    52						// the phi op in b, the other edges coming into s
    53						// must be loopback edges from s, so v is the right
    54						// argument to v!
    55						args := make([]*Value, len(v.Args))
    56						copy(args, v.Args)
    57						v.resetArgs()
    58						for x := 0; x < j; x++ {
    59							v.AddArg(v)
    60						}
    61						v.AddArg(args[0])
    62						for x := j + 1; x < ns; x++ {
    63							v.AddArg(v)
    64						}
    65						for _, a := range args[1:] {
    66							v.AddArg(a)
    67						}
    68					}
    69					b.Values[k] = v
    70					k++
    71				}
    72				b.Values = b.Values[:k]
    73			}
    74	
    75			// Merge the blocks' values.
    76			for _, v := range b.Values {
    77				v.Block = s
    78			}
    79			k := len(b.Values)
    80			m := len(s.Values)
    81			for i := 0; i < k; i++ {
    82				s.Values = append(s.Values, nil)
    83			}
    84			copy(s.Values[k:], s.Values[:m])
    85			copy(s.Values, b.Values)
    86		}
    87		if n < len(f.Blocks) {
    88			f.invalidateCFG()
    89			tail := f.Blocks[n:]
    90			for i := range tail {
    91				tail[i] = nil
    92			}
    93			f.Blocks = f.Blocks[:n]
    94		}
    95	}
    96	
    97	// emptyBlock reports whether the block does not contain actual
    98	// instructions
    99	func emptyBlock(b *Block) bool {
   100		for _, v := range b.Values {
   101			if v.Op != OpPhi {
   102				return false
   103			}
   104		}
   105		return true
   106	}
   107	
   108	// trimmableBlock reports whether the block can be trimmed from the CFG,
   109	// subject to the following criteria:
   110	//  - it should not be the first block
   111	//  - it should be BlockPlain
   112	//  - it should not loop back to itself
   113	//  - it either is the single predecessor of the successor block or
   114	//    contains no actual instructions
   115	func trimmableBlock(b *Block) bool {
   116		if b.Kind != BlockPlain || b == b.Func.Entry {
   117			return false
   118		}
   119		s := b.Succs[0].b
   120		return s != b && (len(s.Preds) == 1 || emptyBlock(b))
   121	}
   122	
   123	// mergePhi adjusts the number of `v`s arguments to account for merge
   124	// of `b`, which was `i`th predecessor of the `v`s block.
   125	func mergePhi(v *Value, i int, b *Block) {
   126		u := v.Args[i]
   127		if u.Block == b {
   128			if u.Op != OpPhi {
   129				b.Func.Fatalf("value %s is not a phi operation", u.LongString())
   130			}
   131			// If the original block contained u = φ(u0, u1, ..., un) and
   132			// the current phi is
   133			//    v = φ(v0, v1, ..., u, ..., vk)
   134			// then the merged phi is
   135			//    v = φ(v0, v1, ..., u0, ..., vk, u1, ..., un)
   136			v.SetArg(i, u.Args[0])
   137			v.AddArgs(u.Args[1:]...)
   138		} else {
   139			// If the original block contained u = φ(u0, u1, ..., un) and
   140			// the current phi is
   141			//    v = φ(v0, v1, ...,  vi, ..., vk)
   142			// i.e. it does not use a value from the predecessor block,
   143			// then the merged phi is
   144			//    v = φ(v0, v1, ..., vk, vi, vi, ...)
   145			for j := 1; j < len(b.Preds); j++ {
   146				v.AddArg(v.Args[i])
   147			}
   148		}
   149	}
   150	

View as plain text