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