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
7// combine copyelim and phielim into a single pass.
8// copyelim removes all uses of OpCopy values from f.
9// A subsequent deadcode pass is needed to actually remove the copies.
10func copyelim(f *Func) {
11	phielim(f)
12
13	// loop of copyelimValue(v) process has been done in phielim() pass.
14	// Update block control values.
15	for _, b := range f.Blocks {
16		for i, v := range b.ControlValues() {
17			if v.Op == OpCopy {
18				b.ReplaceControl(i, v.Args[0])
19			}
20		}
21	}
22
23	// Update named values.
24	for _, name := range f.Names {
25		values := f.NamedValues[*name]
26		for i, v := range values {
27			if v.Op == OpCopy {
28				values[i] = v.Args[0]
29			}
30		}
31	}
32}
33
34// copySource returns the (non-copy) op which is the
35// ultimate source of v.  v must be a copy op.
36func copySource(v *Value) *Value {
37	w := v.Args[0]
38
39	// This loop is just:
40	// for w.Op == OpCopy {
41	//     w = w.Args[0]
42	// }
43	// but we take some extra care to make sure we
44	// don't get stuck in an infinite loop.
45	// Infinite copy loops may happen in unreachable code.
46	// (TODO: or can they? Needs a test.)
47	slow := w
48	var advance bool
49	for w.Op == OpCopy {
50		w = w.Args[0]
51		if w == slow {
52			w.reset(OpUnknown)
53			break
54		}
55		if advance {
56			slow = slow.Args[0]
57		}
58		advance = !advance
59	}
60
61	// The answer is w.  Update all the copies we saw
62	// to point directly to w.  Doing this update makes
63	// sure that we don't end up doing O(n^2) work
64	// for a chain of n copies.
65	for v != w {
66		x := v.Args[0]
67		v.SetArg(0, w)
68		v = x
69	}
70	return w
71}
72
73// copyelimValue ensures that no args of v are copies.
74func copyelimValue(v *Value) {
75	for i, a := range v.Args {
76		if a.Op == OpCopy {
77			v.SetArg(i, copySource(a))
78		}
79	}
80}
81
82// phielim eliminates redundant phi values from f.
83// A phi is redundant if its arguments are all equal. For
84// purposes of counting, ignore the phi itself. Both of
85// these phis are redundant:
86//
87//	v = phi(x,x,x)
88//	v = phi(x,v,x,v)
89//
90// We repeat this process to also catch situations like:
91//
92//	v = phi(x, phi(x, x), phi(x, v))
93//
94// TODO: Can we also simplify cases like:
95//
96//	v = phi(v, w, x)
97//	w = phi(v, w, x)
98//
99// and would that be useful?
100func phielim(f *Func) {
101	for {
102		change := false
103		for _, b := range f.Blocks {
104			for _, v := range b.Values {
105				// This is an early place in SSA where all values are examined.
106				// Rewrite all 0-sized Go values to remove accessors, dereferences, loads, etc.
107				if t := v.Type; (t.IsStruct() || t.IsArray()) && t.Size() == 0 {
108					if t.IsStruct() {
109						v.reset(OpStructMake0)
110					} else {
111						v.reset(OpArrayMake0)
112					}
113				}
114				// Modify all values so no arg (including args
115				// of OpCopy) is a copy.
116				copyelimValue(v)
117				change = phielimValue(v) || change
118			}
119		}
120		if !change {
121			break
122		}
123	}
124}
125
126// phielimValue tries to convert the phi v to a copy.
127func phielimValue(v *Value) bool {
128	if v.Op != OpPhi {
129		return false
130	}
131
132	// If there are two distinct args of v which
133	// are not v itself, then the phi must remain.
134	// Otherwise, we can replace it with a copy.
135	var w *Value
136	for _, x := range v.Args {
137		if x == v {
138			continue
139		}
140		if x == w {
141			continue
142		}
143		if w != nil {
144			return false
145		}
146		w = x
147	}
148
149	if w == nil {
150		// v references only itself. It must be in
151		// a dead code loop. Don't bother modifying it.
152		return false
153	}
154	v.Op = OpCopy
155	v.SetArgs1(w)
156	f := v.Block.Func
157	if f.pass.debug > 0 {
158		f.Warnl(v.Pos, "eliminated phi")
159	}
160	return true
161}
162