| 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 |
} |