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