copyelim.go

     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 ssacompile
     6  
     7  import (
     8  	"cmd/compile/internal/ssa"
     9  	"cmd/compile/internal/ssa/ssaop"
    10  )
    11  
    12  // combine copyelim and phielim into a single pass.
    13  // copyelim removes all uses of OpCopy values from f.
    14  // A subsequent deadcode pass is needed to actually remove the copies.
    15  func copyelim(f *ssa.Func) {
    16  	phielim(f)
    17  
    18  	// loop of copyelimValue(v) process has been done in phielim() pass.
    19  	// Update block control values.
    20  	for _, b := range f.Blocks {
    21  		for i, v := range b.ControlValues() {
    22  			if v.Op == ssaop.OpCopy {
    23  				b.ReplaceControl(i, v.Args[0])
    24  			}
    25  		}
    26  	}
    27  
    28  	// Update named values.
    29  	for _, name := range f.Names {
    30  		values := f.NamedValues[name]
    31  		for i, v := range values {
    32  			if v.Op == ssaop.OpCopy {
    33  				values[i] = v.Args[0]
    34  			}
    35  		}
    36  	}
    37  }
    38  
    39  // copySource returns the (non-copy) op which is the
    40  // ultimate source of v.  v must be a copy op.
    41  func copySource(v *ssa.Value) *ssa.Value {
    42  	w := v.Args[0]
    43  
    44  	// This loop is just:
    45  	// for w.Op == OpCopy {
    46  	//     w = w.Args[0]
    47  	// }
    48  	// but we take some extra care to make sure we
    49  	// don't get stuck in an infinite loop.
    50  	// Infinite copy loops may happen in unreachable code.
    51  	// (TODO: or can they? Needs a test.)
    52  	slow := w
    53  	var advance bool
    54  	for w.Op == ssaop.OpCopy {
    55  		w = w.Args[0]
    56  		if w == slow {
    57  			w.Reset(ssaop.OpUnknown)
    58  			break
    59  		}
    60  		if advance {
    61  			slow = slow.Args[0]
    62  		}
    63  		advance = !advance
    64  	}
    65  
    66  	// The answer is w.  Update all the copies we saw
    67  	// to point directly to w.  Doing this update makes
    68  	// sure that we don't end up doing O(n^2) work
    69  	// for a chain of n copies.
    70  	for v != w {
    71  		x := v.Args[0]
    72  		v.SetArg(0, w)
    73  		v = x
    74  	}
    75  	return w
    76  }
    77  
    78  // copyelimValue ensures that no args of v are copies.
    79  func copyelimValue(v *ssa.Value) {
    80  	for i, a := range v.Args {
    81  		if a.Op == ssaop.OpCopy {
    82  			v.SetArg(i, copySource(a))
    83  		}
    84  	}
    85  }
    86  
    87  // phielim eliminates redundant phi values from f.
    88  // A phi is redundant if its arguments are all equal. For
    89  // purposes of counting, ignore the phi itself. Both of
    90  // these phis are redundant:
    91  //
    92  //	v = phi(x,x,x)
    93  //	v = phi(x,v,x,v)
    94  //
    95  // We repeat this process to also catch situations like:
    96  //
    97  //	v = phi(x, phi(x, x), phi(x, v))
    98  //
    99  // TODO: Can we also simplify cases like:
   100  //
   101  //	v = phi(v, w, x)
   102  //	w = phi(v, w, x)
   103  //
   104  // and would that be useful?
   105  func phielim(f *ssa.Func) {
   106  	for {
   107  		change := false
   108  		for _, b := range f.Blocks {
   109  			for _, v := range b.Values {
   110  				// This is an early place in SSA where all values are examined.
   111  				// Rewrite all 0-sized Go values to remove accessors, dereferences, loads, etc.
   112  				if t := v.Type; (t.IsStruct() || t.IsArray()) && t.Size() == 0 {
   113  					v.Reset(ssaop.OpEmpty)
   114  				}
   115  				// Modify all values so no arg (including args
   116  				// of OpCopy) is a copy.
   117  				copyelimValue(v)
   118  				change = ssa.PhiElimValue(v) || change
   119  			}
   120  		}
   121  		if !change {
   122  			break
   123  		}
   124  	}
   125  }
   126
View as plain text