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.
7 // Simple block optimizations to simplify the control flow graph.
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])
18 // If true, perform sanity checking and show progress at each
19 // successive iteration of optimizeBlocks. Very verbose.
20 const debugBlockOpt = false
22 // markReachable sets Index=-1 for all blocks reachable from b.
23 func markReachable(b *BasicBlock) {
25 for _, succ := range b.Succs {
32 // deleteUnreachableBlocks marks all reachable blocks of f and
33 // eliminates (nils) all others, including possibly cyclic subgraphs.
35 func 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 {
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.
48 for i, b := range f.Blocks {
50 for _, c := range b.Succs {
52 c.removePred(b) // delete white->black edge
56 fmt.Fprintln(os.Stderr, "unreachable", b)
58 f.Blocks[i] = nil // delete b
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.
68 func jumpThreading(f *Function, b *BasicBlock) bool {
70 return false // don't apply to entry block
75 for _, pred := range b.Preds {
76 switch pred.Control().(type) {
78 // don't optimize away the head blocks of switch statements
82 if _, ok := b.Instrs[0].(*Jump); !ok {
83 return false // not just a jump
87 return false // don't apply to degenerate jump-to-self.
90 return false // not sound without more effort
92 for j, a := range b.Preds {
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 {
99 a.Instrs[len(a.Instrs)-1] = jump
100 a.Succs = a.Succs[:1]
106 c.Preds = append(c.Preds, a)
111 fmt.Fprintln(os.Stderr, "jumpThreading", a, b, c)
114 f.Blocks[b.Index] = nil // delete b
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.
122 func fuseBlocks(f *Function, a *BasicBlock) bool {
123 if len(a.Succs) != 1 {
126 if a.Succs[0] == f.Exit {
130 if len(b.Preds) != 1 {
133 if _, ok := a.Instrs[len(a.Instrs)-1].(*Panic); ok {
134 // panics aren't simple jumps, they have side effects.
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.)
142 return false // not sound without further effort
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 {
151 // A inherits B's successors
152 a.Succs = append(a.succs2[:0], b.Succs...)
154 // Fix up Preds links of all successors of B.
155 for _, c := range b.Succs {
160 fmt.Fprintln(os.Stderr, "fuseBlocks", a, b)
163 f.Blocks[b.Index] = nil // delete b
167 // optimizeBlocks() performs some simple block optimizations on a
168 // completed function: dead block elimination, block fusion, jump
171 func optimizeBlocks(f *Function) {
174 mustSanityCheck(f, nil)
177 deleteUnreachableBlocks(f)
179 // Loop until no further progress.
186 mustSanityCheck(f, nil)
189 for _, b := range f.Blocks {
190 // f.Blocks will temporarily contain nils to indicate
191 // deleted blocks; we remove them at the end.
196 // Fuse blocks. b->c becomes bc.
197 if fuseBlocks(f, b) {
201 // a->b->c becomes a->c if b contains only a Jump.
202 if jumpThreading(f, b) {
204 continue // (b was disconnected)