...
Run Format

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

Documentation: cmd/compile/internal/ssa

     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