Source file src/pkg/cmd/compile/internal/ssa/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); {
    19				v := b.Values[i]
    20				next := true
    21				if opcodeTable[v.Op].argLen == 0 {
    22					key := vkey{v.Op, keyFor(v), v.Aux, v.Type}
    23					if vals[key] == nil {
    24						vals[key] = v
    25						if b != f.Entry {
    26							// Move v to the entry block so it will dominate every block
    27							// where we might use it. This prevents the need for any dominator
    28							// calculations in this pass.
    29							v.Block = f.Entry
    30							f.Entry.Values = append(f.Entry.Values, v)
    31							last := len(b.Values) - 1
    32							b.Values[i] = b.Values[last]
    33							b.Values[last] = nil
    34							b.Values = b.Values[:last]
    35	
    36							// process b.Values[i] again
    37							next = false
    38						}
    39					}
    40				}
    41				if next {
    42					i++
    43				}
    44			}
    45		}
    46	
    47		for _, b := range f.Blocks {
    48			for _, v := range b.Values {
    49				for i, a := range v.Args {
    50					if opcodeTable[a.Op].argLen == 0 {
    51						key := vkey{a.Op, keyFor(a), a.Aux, a.Type}
    52						if rv, ok := vals[key]; ok {
    53							v.SetArg(i, rv)
    54						}
    55					}
    56				}
    57			}
    58		}
    59	}
    60	
    61	// vkey is a type used to uniquely identify a zero arg value.
    62	type vkey struct {
    63		op Op
    64		ai int64       // aux int
    65		ax interface{} // aux
    66		t  *types.Type // type
    67	}
    68	
    69	// keyFor returns the AuxInt portion of a  key structure uniquely identifying a
    70	// zero arg value for the supported ops.
    71	func keyFor(v *Value) int64 {
    72		switch v.Op {
    73		case OpConst64, OpConst64F, OpConst32F:
    74			return v.AuxInt
    75		case OpConst32:
    76			return int64(int32(v.AuxInt))
    77		case OpConst16:
    78			return int64(int16(v.AuxInt))
    79		case OpConst8, OpConstBool:
    80			return int64(int8(v.AuxInt))
    81		default:
    82			return v.AuxInt
    83		}
    84	}
    85	

View as plain text