Debian Codegraph @

go/ir/blockopt.go

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