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