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 ssa
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.Index = -1
25	for _, succ := range b.Succs {
26		if succ.Index == 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.Index temporarily as the mark bit.
38	for _, b := range f.Blocks {
39		b.Index = white
40	}
41	markReachable(f.Blocks[0])
42	if f.Recover != nil {
43		markReachable(f.Recover)
44	}
45	for i, b := range f.Blocks {
46		if b.Index == white {
47			for _, c := range b.Succs {
48				if c.Index == black {
49					c.removePred(b) // delete white->black edge
50				}
51			}
52			if debugBlockOpt {
53				fmt.Fprintln(os.Stderr, "unreachable", b)
54			}
55			f.Blocks[i] = nil // delete b
56		}
57	}
58	f.removeNilBlocks()
59}
60
61// jumpThreading attempts to apply simple jump-threading to block b,
62// in which a->b->c become a->c if b is just a Jump.
63// The result is true if the optimization was applied.
64//
65func jumpThreading(f *Function, b *BasicBlock) bool {
66	if b.Index == 0 {
67		return false // don't apply to entry block
68	}
69	if b.Instrs == nil {
70		return false
71	}
72	if _, ok := b.Instrs[0].(*Jump); !ok {
73		return false // not just a jump
74	}
75	c := b.Succs[0]
76	if c == b {
77		return false // don't apply to degenerate jump-to-self.
78	}
79	if c.hasPhi() {
80		return false // not sound without more effort
81	}
82	for j, a := range b.Preds {
83		a.replaceSucc(b, c)
84
85		// If a now has two edges to c, replace its degenerate If by Jump.
86		if len(a.Succs) == 2 && a.Succs[0] == c && a.Succs[1] == c {
87			jump := new(Jump)
88			jump.setBlock(a)
89			a.Instrs[len(a.Instrs)-1] = jump
90			a.Succs = a.Succs[:1]
91			c.removePred(b)
92		} else {
93			if j == 0 {
94				c.replacePred(b, a)
95			} else {
96				c.Preds = append(c.Preds, a)
97			}
98		}
99
100		if debugBlockOpt {
101			fmt.Fprintln(os.Stderr, "jumpThreading", a, b, c)
102		}
103	}
104	f.Blocks[b.Index] = nil // delete b
105	return true
106}
107
108// fuseBlocks attempts to apply the block fusion optimization to block
109// a, in which a->b becomes ab if len(a.Succs)==len(b.Preds)==1.
110// The result is true if the optimization was applied.
111//
112func fuseBlocks(f *Function, a *BasicBlock) bool {
113	if len(a.Succs) != 1 {
114		return false
115	}
116	b := a.Succs[0]
117	if len(b.Preds) != 1 {
118		return false
119	}
120
121	// Degenerate &&/|| ops may result in a straight-line CFG
122	// containing φ-nodes. (Ideally we'd replace such them with
123	// their sole operand but that requires Referrers, built later.)
124	if b.hasPhi() {
125		return false // not sound without further effort
126	}
127
128	// Eliminate jump at end of A, then copy all of B across.
129	a.Instrs = append(a.Instrs[:len(a.Instrs)-1], b.Instrs...)
130	for _, instr := range b.Instrs {
131		instr.setBlock(a)
132	}
133
134	// A inherits B's successors
135	a.Succs = append(a.succs2[:0], b.Succs...)
136
137	// Fix up Preds links of all successors of B.
138	for _, c := range b.Succs {
139		c.replacePred(b, a)
140	}
141
142	if debugBlockOpt {
143		fmt.Fprintln(os.Stderr, "fuseBlocks", a, b)
144	}
145
146	f.Blocks[b.Index] = nil // delete b
147	return true
148}
149
150// optimizeBlocks() performs some simple block optimizations on a
151// completed function: dead block elimination, block fusion, jump
152// threading.
153//
154func optimizeBlocks(f *Function) {
155	deleteUnreachableBlocks(f)
156
157	// Loop until no further progress.
158	changed := true
159	for changed {
160		changed = false
161
162		if debugBlockOpt {
163			f.WriteTo(os.Stderr)
164			mustSanityCheck(f, nil)
165		}
166
167		for _, b := range f.Blocks {
168			// f.Blocks will temporarily contain nils to indicate
169			// deleted blocks; we remove them at the end.
170			if b == nil {
171				continue
172			}
173
174			// Fuse blocks.  b->c becomes bc.
175			if fuseBlocks(f, b) {
176				changed = true
177			}
178
179			// a->b->c becomes a->c if b contains only a Jump.
180			if jumpThreading(f, b) {
181				changed = true
182				continue // (b was disconnected)
183			}
184		}
185	}
186	f.removeNilBlocks()
187}
188