1// Copyright 2015 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 (
8	"cmd/compile/internal/types"
9	"cmd/internal/src"
10)
11
12// dse does dead-store elimination on the Function.
13// Dead stores are those which are unconditionally followed by
14// another store to the same location, with no intervening load.
15// This implementation only works within a basic block. TODO: use something more global.
16func dse(f *Func) {
17	var stores []*Value
18	loadUse := f.newSparseSet(f.NumValues())
19	defer f.retSparseSet(loadUse)
20	storeUse := f.newSparseSet(f.NumValues())
21	defer f.retSparseSet(storeUse)
22	shadowed := newSparseMap(f.NumValues()) // TODO: cache
23	for _, b := range f.Blocks {
24		// Find all the stores in this block. Categorize their uses:
25		//  loadUse contains stores which are used by a subsequent load.
26		//  storeUse contains stores which are used by a subsequent store.
27		loadUse.clear()
28		storeUse.clear()
29		stores = stores[:0]
30		for _, v := range b.Values {
31			if v.Op == OpPhi {
32				// Ignore phis - they will always be first and can't be eliminated
33				continue
34			}
35			if v.Type.IsMemory() {
36				stores = append(stores, v)
37				for _, a := range v.Args {
38					if a.Block == b && a.Type.IsMemory() {
39						storeUse.add(a.ID)
40						if v.Op != OpStore && v.Op != OpZero && v.Op != OpVarDef && v.Op != OpVarKill {
41							// CALL, DUFFCOPY, etc. are both
42							// reads and writes.
43							loadUse.add(a.ID)
44						}
45					}
46				}
47			} else {
48				for _, a := range v.Args {
49					if a.Block == b && a.Type.IsMemory() {
50						loadUse.add(a.ID)
51					}
52				}
53			}
54		}
55		if len(stores) == 0 {
56			continue
57		}
58
59		// find last store in the block
60		var last *Value
61		for _, v := range stores {
62			if storeUse.contains(v.ID) {
63				continue
64			}
65			if last != nil {
66				b.Fatalf("two final stores - simultaneous live stores %s %s", last.LongString(), v.LongString())
67			}
68			last = v
69		}
70		if last == nil {
71			b.Fatalf("no last store found - cycle?")
72		}
73
74		// Walk backwards looking for dead stores. Keep track of shadowed addresses.
75		// An "address" is an SSA Value which encodes both the address and size of
76		// the write. This code will not remove dead stores to the same address
77		// of different types.
78		shadowed.clear()
79		v := last
80
81	walkloop:
82		if loadUse.contains(v.ID) {
83			// Someone might be reading this memory state.
84			// Clear all shadowed addresses.
85			shadowed.clear()
86		}
87		if v.Op == OpStore || v.Op == OpZero {
88			var sz int64
89			if v.Op == OpStore {
90				sz = v.Aux.(*types.Type).Size()
91			} else { // OpZero
92				sz = v.AuxInt
93			}
94			if shadowedSize := int64(shadowed.get(v.Args[0].ID)); shadowedSize != -1 && shadowedSize >= sz {
95				// Modify store into a copy
96				if v.Op == OpStore {
97					// store addr value mem
98					v.SetArgs1(v.Args[2])
99				} else {
100					// zero addr mem
101					typesz := v.Args[0].Type.ElemType().Size()
102					if sz != typesz {
103						f.Fatalf("mismatched zero/store sizes: %d and %d [%s]",
104							sz, typesz, v.LongString())
105					}
106					v.SetArgs1(v.Args[1])
107				}
108				v.Aux = nil
109				v.AuxInt = 0
110				v.Op = OpCopy
111			} else {
112				if sz > 0x7fffffff { // work around sparseMap's int32 value type
113					sz = 0x7fffffff
114				}
115				shadowed.set(v.Args[0].ID, int32(sz), src.NoXPos)
116			}
117		}
118		// walk to previous store
119		if v.Op == OpPhi {
120			// At start of block.  Move on to next block.
121			// The memory phi, if it exists, is always
122			// the first logical store in the block.
123			// (Even if it isn't the first in the current b.Values order.)
124			continue
125		}
126		for _, a := range v.Args {
127			if a.Block == b && a.Type.IsMemory() {
128				v = a
129				goto walkloop
130			}
131		}
132	}
133}
134