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