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// tighten moves Values closer to the Blocks in which they are used.
8// This can reduce the amount of register spilling required,
9// if it doesn't also create more live values.
10// A Value can be moved to any block that
11// dominates all blocks in which it is used.
12func tighten(f *Func) {
13	canMove := make([]bool, f.NumValues())
14	for _, b := range f.Blocks {
15		for _, v := range b.Values {
16			if v.Op.isLoweredGetClosurePtr() {
17				// Must stay in the entry block.
18				continue
19			}
20			switch v.Op {
21			case OpPhi, OpArg, OpArgIntReg, OpArgFloatReg, OpSelect0, OpSelect1, OpSelectN:
22				// Phis need to stay in their block.
23				// Arg must stay in the entry block.
24				// Tuple selectors must stay with the tuple generator.
25				// SelectN is typically, ultimately, a register.
26				continue
27			}
28			if v.MemoryArg() != nil {
29				// We can't move values which have a memory arg - it might
30				// make two memory values live across a block boundary.
31				continue
32			}
33			// Count arguments which will need a register.
34			narg := 0
35			for _, a := range v.Args {
36				if !a.rematerializeable() {
37					narg++
38				}
39			}
40			if narg >= 2 && !v.Type.IsFlags() {
41				// Don't move values with more than one input, as that may
42				// increase register pressure.
43				// We make an exception for flags, as we want flag generators
44				// moved next to uses (because we only have 1 flag register).
45				continue
46			}
47			canMove[v.ID] = true
48		}
49	}
50
51	// Build data structure for fast least-common-ancestor queries.
52	lca := makeLCArange(f)
53
54	// For each moveable value, record the block that dominates all uses found so far.
55	target := make([]*Block, f.NumValues())
56
57	// Grab loop information.
58	// We use this to make sure we don't tighten a value into a (deeper) loop.
59	idom := f.Idom()
60	loops := f.loopnest()
61	loops.calculateDepths()
62
63	changed := true
64	for changed {
65		changed = false
66
67		// Reset target
68		for i := range target {
69			target[i] = nil
70		}
71
72		// Compute target locations (for moveable values only).
73		// target location = the least common ancestor of all uses in the dominator tree.
74		for _, b := range f.Blocks {
75			for _, v := range b.Values {
76				for i, a := range v.Args {
77					if !canMove[a.ID] {
78						continue
79					}
80					use := b
81					if v.Op == OpPhi {
82						use = b.Preds[i].b
83					}
84					if target[a.ID] == nil {
85						target[a.ID] = use
86					} else {
87						target[a.ID] = lca.find(target[a.ID], use)
88					}
89				}
90			}
91			for _, c := range b.ControlValues() {
92				if !canMove[c.ID] {
93					continue
94				}
95				if target[c.ID] == nil {
96					target[c.ID] = b
97				} else {
98					target[c.ID] = lca.find(target[c.ID], b)
99				}
100			}
101		}
102
103		// If the target location is inside a loop,
104		// move the target location up to just before the loop head.
105		for _, b := range f.Blocks {
106			origloop := loops.b2l[b.ID]
107			for _, v := range b.Values {
108				t := target[v.ID]
109				if t == nil {
110					continue
111				}
112				targetloop := loops.b2l[t.ID]
113				for targetloop != nil && (origloop == nil || targetloop.depth > origloop.depth) {
114					t = idom[targetloop.header.ID]
115					target[v.ID] = t
116					targetloop = loops.b2l[t.ID]
117				}
118			}
119		}
120
121		// Move values to target locations.
122		for _, b := range f.Blocks {
123			for i := 0; i < len(b.Values); i++ {
124				v := b.Values[i]
125				t := target[v.ID]
126				if t == nil || t == b {
127					// v is not moveable, or is already in correct place.
128					continue
129				}
130				// Move v to the block which dominates its uses.
131				t.Values = append(t.Values, v)
132				v.Block = t
133				last := len(b.Values) - 1
134				b.Values[i] = b.Values[last]
135				b.Values[last] = nil
136				b.Values = b.Values[:last]
137				changed = true
138				i--
139			}
140		}
141	}
142}
143
144// phiTighten moves constants closer to phi users.
145// This pass avoids having lots of constants live for lots of the program.
146// See issue 16407.
147func phiTighten(f *Func) {
148	for _, b := range f.Blocks {
149		for _, v := range b.Values {
150			if v.Op != OpPhi {
151				continue
152			}
153			for i, a := range v.Args {
154				if !a.rematerializeable() {
155					continue // not a constant we can move around
156				}
157				if a.Block == b.Preds[i].b {
158					continue // already in the right place
159				}
160				// Make a copy of a, put in predecessor block.
161				v.SetArg(i, a.copyInto(b.Preds[i].b))
162			}
163		}
164	}
165}
166