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