1// Copyright 2013 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 ir
6
7// Simple block optimizations to simplify the control flow graph.
8
9// TODO(adonovan): opt: instead of creating several "unreachable" blocks
10// per function in the Builder, reuse a single one (e.g. at Blocks[1])
11// to reduce garbage.
12
13import (
14	"fmt"
15	"os"
16)
17
18// If true, perform sanity checking and show progress at each
19// successive iteration of optimizeBlocks.  Very verbose.
20const debugBlockOpt = false
21
22// markReachable sets Index=-1 for all blocks reachable from b.
23func markReachable(b *BasicBlock) {
24	b.gaps = -1
25	for _, succ := range b.Succs {
26		if succ.gaps == 0 {
27			markReachable(succ)
28		}
29	}
30}
31
32// deleteUnreachableBlocks marks all reachable blocks of f and
33// eliminates (nils) all others, including possibly cyclic subgraphs.
34//
35func deleteUnreachableBlocks(f *Function) {
36	const white, black = 0, -1
37	// We borrow b.gaps temporarily as the mark bit.
38	for _, b := range f.Blocks {
39		b.gaps = white
40	}
41	markReachable(f.Blocks[0])
42	// In SSI form, we need the exit to be reachable for correct
43	// post-dominance information. In original form, however, we
44	// cannot unconditionally mark it reachable because we won't
45	// be adding fake edges, and this breaks the calculation of
46	// dominance information.
47	markReachable(f.Exit)
48	for i, b := range f.Blocks {
49		if b.gaps == white {
50			for _, c := range b.Succs {
51				if c.gaps == black {
52					c.removePred(b) // delete white->black edge
53				}
54			}
55			if debugBlockOpt {
56				fmt.Fprintln(os.Stderr, "unreachable", b)
57			}
58			f.Blocks[i] = nil // delete b
59		}
60	}
61	f.removeNilBlocks()
62}
63
64// jumpThreading attempts to apply simple jump-threading to block b,
65// in which a->b->c become a->c if b is just a Jump.
66// The result is true if the optimization was applied.
67//
68func jumpThreading(f *Function, b *BasicBlock) bool {
69	if b.Index == 0 {
70		return false // don't apply to entry block
71	}
72	if b.Instrs == nil {
73		return false
74	}
75	for _, pred := range b.Preds {
76		switch pred.Control().(type) {
77		case *ConstantSwitch:
78			// don't optimize away the head blocks of switch statements
79			return false
80		}
81	}
82	if _, ok := b.Instrs[0].(*Jump); !ok {
83		return false // not just a jump
84	}
85	c := b.Succs[0]
86	if c == b {
87		return false // don't apply to degenerate jump-to-self.
88	}
89	if c.hasPhi() {
90		return false // not sound without more effort
91	}
92	for j, a := range b.Preds {
93		a.replaceSucc(b, c)
94
95		// If a now has two edges to c, replace its degenerate If by Jump.
96		if len(a.Succs) == 2 && a.Succs[0] == c && a.Succs[1] == c {
97			jump := new(Jump)
98			jump.setBlock(a)
99			a.Instrs[len(a.Instrs)-1] = jump
100			a.Succs = a.Succs[:1]
101			c.removePred(b)
102		} else {
103			if j == 0 {
104				c.replacePred(b, a)
105			} else {
106				c.Preds = append(c.Preds, a)
107			}
108		}
109
110		if debugBlockOpt {
111			fmt.Fprintln(os.Stderr, "jumpThreading", a, b, c)
112		}
113	}
114	f.Blocks[b.Index] = nil // delete b
115	return true
116}
117
118// fuseBlocks attempts to apply the block fusion optimization to block
119// a, in which a->b becomes ab if len(a.Succs)==len(b.Preds)==1.
120// The result is true if the optimization was applied.
121//
122func fuseBlocks(f *Function, a *BasicBlock) bool {
123	if len(a.Succs) != 1 {
124		return false
125	}
126	if a.Succs[0] == f.Exit {
127		return false
128	}
129	b := a.Succs[0]
130	if len(b.Preds) != 1 {
131		return false
132	}
133	if _, ok := a.Instrs[len(a.Instrs)-1].(*Panic); ok {
134		// panics aren't simple jumps, they have side effects.
135		return false
136	}
137
138	// Degenerate &&/|| ops may result in a straight-line CFG
139	// containing φ-nodes. (Ideally we'd replace such them with
140	// their sole operand but that requires Referrers, built later.)
141	if b.hasPhi() {
142		return false // not sound without further effort
143	}
144
145	// Eliminate jump at end of A, then copy all of B across.
146	a.Instrs = append(a.Instrs[:len(a.Instrs)-1], b.Instrs...)
147	for _, instr := range b.Instrs {
148		instr.setBlock(a)
149	}
150
151	// A inherits B's successors
152	a.Succs = append(a.succs2[:0], b.Succs...)
153
154	// Fix up Preds links of all successors of B.
155	for _, c := range b.Succs {
156		c.replacePred(b, a)
157	}
158
159	if debugBlockOpt {
160		fmt.Fprintln(os.Stderr, "fuseBlocks", a, b)
161	}
162
163	f.Blocks[b.Index] = nil // delete b
164	return true
165}
166
167// optimizeBlocks() performs some simple block optimizations on a
168// completed function: dead block elimination, block fusion, jump
169// threading.
170//
171func optimizeBlocks(f *Function) {
172	if debugBlockOpt {
173		f.WriteTo(os.Stderr)
174		mustSanityCheck(f, nil)
175	}
176
177	deleteUnreachableBlocks(f)
178
179	// Loop until no further progress.
180	changed := true
181	for changed {
182		changed = false
183
184		if debugBlockOpt {
185			f.WriteTo(os.Stderr)
186			mustSanityCheck(f, nil)
187		}
188
189		for _, b := range f.Blocks {
190			// f.Blocks will temporarily contain nils to indicate
191			// deleted blocks; we remove them at the end.
192			if b == nil {
193				continue
194			}
195
196			// Fuse blocks.  b->c becomes bc.
197			if fuseBlocks(f, b) {
198				changed = true
199			}
200
201			// a->b->c becomes a->c if b contains only a Jump.
202			if jumpThreading(f, b) {
203				changed = true
204				continue // (b was disconnected)
205			}
206		}
207	}
208	f.removeNilBlocks()
209}
210