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 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 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.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// 35func 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 { 39 b.gaps = white 40 } 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. 47 markReachable(f.Exit) 48 for i, b := range f.Blocks { 49 if b.gaps == white { 50 for _, c := range b.Succs { 51 if c.gaps == black { 52 c.removePred(b) // delete white->black edge 53 } 54 } 55 if debugBlockOpt { 56 fmt.Fprintln(os.Stderr, "unreachable", b) 57 } 58 f.Blocks[i] = nil // delete b 59 } 60 } 61 f.removeNilBlocks() 62} 63 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. 67// 68func jumpThreading(f *Function, b *BasicBlock) bool { 69 if b.Index == 0 { 70 return false // don't apply to entry block 71 } 72 if b.Instrs == nil { 73 return false 74 } 75 for _, pred := range b.Preds { 76 switch pred.Control().(type) { 77 case *ConstantSwitch: 78 // don't optimize away the head blocks of switch statements 79 return false 80 } 81 } 82 if _, ok := b.Instrs[0].(*Jump); !ok { 83 return false // not just a jump 84 } 85 c := b.Succs[0] 86 if c == b { 87 return false // don't apply to degenerate jump-to-self. 88 } 89 if c.hasPhi() { 90 return false // not sound without more effort 91 } 92 for j, a := range b.Preds { 93 a.replaceSucc(b, c) 94 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 { 97 jump := new(Jump) 98 jump.setBlock(a) 99 a.Instrs[len(a.Instrs)-1] = jump 100 a.Succs = a.Succs[:1] 101 c.removePred(b) 102 } else { 103 if j == 0 { 104 c.replacePred(b, a) 105 } else { 106 c.Preds = append(c.Preds, a) 107 } 108 } 109 110 if debugBlockOpt { 111 fmt.Fprintln(os.Stderr, "jumpThreading", a, b, c) 112 } 113 } 114 f.Blocks[b.Index] = nil // delete b 115 return true 116} 117 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. 121// 122func fuseBlocks(f *Function, a *BasicBlock) bool { 123 if len(a.Succs) != 1 { 124 return false 125 } 126 if a.Succs[0] == f.Exit { 127 return false 128 } 129 b := a.Succs[0] 130 if len(b.Preds) != 1 { 131 return false 132 } 133 if _, ok := a.Instrs[len(a.Instrs)-1].(*Panic); ok { 134 // panics aren't simple jumps, they have side effects. 135 return false 136 } 137 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.) 141 if b.hasPhi() { 142 return false // not sound without further effort 143 } 144 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 { 148 instr.setBlock(a) 149 } 150 151 // A inherits B's successors 152 a.Succs = append(a.succs2[:0], b.Succs...) 153 154 // Fix up Preds links of all successors of B. 155 for _, c := range b.Succs { 156 c.replacePred(b, a) 157 } 158 159 if debugBlockOpt { 160 fmt.Fprintln(os.Stderr, "fuseBlocks", a, b) 161 } 162 163 f.Blocks[b.Index] = nil // delete b 164 return true 165} 166 167// optimizeBlocks() performs some simple block optimizations on a 168// completed function: dead block elimination, block fusion, jump 169// threading. 170// 171func optimizeBlocks(f *Function) { 172 if debugBlockOpt { 173 f.WriteTo(os.Stderr) 174 mustSanityCheck(f, nil) 175 } 176 177 deleteUnreachableBlocks(f) 178 179 // Loop until no further progress. 180 changed := true 181 for changed { 182 changed = false 183 184 if debugBlockOpt { 185 f.WriteTo(os.Stderr) 186 mustSanityCheck(f, nil) 187 } 188 189 for _, b := range f.Blocks { 190 // f.Blocks will temporarily contain nils to indicate 191 // deleted blocks; we remove them at the end. 192 if b == nil { 193 continue 194 } 195 196 // Fuse blocks. b->c becomes bc. 197 if fuseBlocks(f, b) { 198 changed = true 199 } 200 201 // a->b->c becomes a->c if b contains only a Jump. 202 if jumpThreading(f, b) { 203 changed = true 204 continue // (b was disconnected) 205 } 206 } 207 } 208 f.removeNilBlocks() 209} 210