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