zcse.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/ssaop"
    10  	"cmd/compile/internal/types"
    11  )
    12  
    13  // zcse does an initial pass of common-subexpression elimination on the
    14  // function for values with zero arguments to allow the more expensive cse
    15  // to begin with a reduced number of values. Values are just relinked,
    16  // nothing is deleted. A subsequent deadcode pass is required to actually
    17  // remove duplicate expressions.
    18  func zcse(f *ssa.Func) {
    19  	vals := make(map[vkey]*ssa.Value)
    20  
    21  	for _, b := range f.Blocks {
    22  		for i := 0; i < len(b.Values); i++ {
    23  			v := b.Values[i]
    24  			if ssaop.OpcodeTable[v.Op].ArgLen == 0 {
    25  				key := vkey{v.Op, keyFor(v), v.Aux, v.Type}
    26  				if vals[key] == nil {
    27  					vals[key] = v
    28  					if b != f.Entry {
    29  						// Move v to the entry block so it will dominate every block
    30  						// where we might use it. This prevents the need for any dominator
    31  						// calculations in this pass.
    32  						v.Block = f.Entry
    33  						f.Entry.Values = append(f.Entry.Values, v)
    34  						last := len(b.Values) - 1
    35  						b.Values[i] = b.Values[last]
    36  						b.Values[last] = nil
    37  						b.Values = b.Values[:last]
    38  
    39  						i-- // process b.Values[i] again
    40  					}
    41  				}
    42  			}
    43  		}
    44  	}
    45  
    46  	for _, b := range f.Blocks {
    47  		for _, v := range b.Values {
    48  			for i, a := range v.Args {
    49  				if ssaop.OpcodeTable[a.Op].ArgLen == 0 {
    50  					key := vkey{a.Op, keyFor(a), a.Aux, a.Type}
    51  					if rv, ok := vals[key]; ok {
    52  						v.SetArg(i, rv)
    53  					}
    54  				}
    55  			}
    56  		}
    57  	}
    58  }
    59  
    60  // vkey is a type used to uniquely identify a zero arg value.
    61  type vkey struct {
    62  	op ssaop.Op
    63  	ai int64       // aux int
    64  	ax ssa.Aux     // aux
    65  	t  *types.Type // type
    66  }
    67  
    68  // keyFor returns the AuxInt portion of a  key structure uniquely identifying a
    69  // zero arg value for the supported ops.
    70  func keyFor(v *ssa.Value) int64 {
    71  	switch v.Op {
    72  	case ssaop.OpConst64, ssaop.OpConst64F, ssaop.OpConst32F:
    73  		return v.AuxInt
    74  	case ssaop.OpConst32:
    75  		return int64(int32(v.AuxInt))
    76  	case ssaop.OpConst16:
    77  		return int64(int16(v.AuxInt))
    78  	case ssaop.OpConst8, ssaop.OpConstBool:
    79  		return int64(int8(v.AuxInt))
    80  	default:
    81  		return v.AuxInt
    82  	}
    83  }
    84
View as plain text