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
5package ssa
6
7import "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.
14func 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.
57type 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.
66func 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