blob: e79260a21a2e1cb118554752c54cc88ceb681ee4 [file] [log] [blame]
// Copyright 2013 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package ssa
// Simple block optimizations to simplify the control flow graph.
// TODO(adonovan): opt: instead of creating several "unreachable" blocks
// per function in the Builder, reuse a single one (e.g. at Blocks[1])
// to reduce garbage.
import (
"fmt"
"os"
)
// If true, perform sanity checking and show progress at each
// successive iteration of optimizeBlocks. Very verbose.
const debugBlockOpt = false
// markReachable sets Index=-1 for all blocks reachable from b.
func markReachable(b *BasicBlock) {
b.Index = -1
for _, succ := range b.Succs {
if succ.Index == 0 {
markReachable(succ)
}
}
}
// deleteUnreachableBlocks marks all reachable blocks of f and
// eliminates (nils) all others, including possibly cyclic subgraphs.
//
func deleteUnreachableBlocks(f *Function) {
const white, black = 0, -1
// We borrow b.Index temporarily as the mark bit.
for _, b := range f.Blocks {
b.Index = white
}
markReachable(f.Blocks[0])
if f.Recover != nil {
markReachable(f.Recover)
}
for i, b := range f.Blocks {
if b.Index == white {
for _, c := range b.Succs {
if c.Index == black {
c.removePred(b) // delete white->black edge
}
}
if debugBlockOpt {
fmt.Fprintln(os.Stderr, "unreachable", b)
}
f.Blocks[i] = nil // delete b
}
}
f.removeNilBlocks()
}
// jumpThreading attempts to apply simple jump-threading to block b,
// in which a->b->c become a->c if b is just a Jump.
// The result is true if the optimization was applied.
//
func jumpThreading(f *Function, b *BasicBlock) bool {
if b.Index == 0 {
return false // don't apply to entry block
}
if b.Instrs == nil {
return false
}
if _, ok := b.Instrs[0].(*Jump); !ok {
return false // not just a jump
}
c := b.Succs[0]
if c == b {
return false // don't apply to degenerate jump-to-self.
}
if c.hasPhi() {
return false // not sound without more effort
}
for j, a := range b.Preds {
a.replaceSucc(b, c)
// If a now has two edges to c, replace its degenerate If by Jump.
if len(a.Succs) == 2 && a.Succs[0] == c && a.Succs[1] == c {
jump := new(Jump)
jump.setBlock(a)
a.Instrs[len(a.Instrs)-1] = jump
a.Succs = a.Succs[:1]
c.removePred(b)
} else {
if j == 0 {
c.replacePred(b, a)
} else {
c.Preds = append(c.Preds, a)
}
}
if debugBlockOpt {
fmt.Fprintln(os.Stderr, "jumpThreading", a, b, c)
}
}
f.Blocks[b.Index] = nil // delete b
return true
}
// fuseBlocks attempts to apply the block fusion optimization to block
// a, in which a->b becomes ab if len(a.Succs)==len(b.Preds)==1.
// The result is true if the optimization was applied.
//
func fuseBlocks(f *Function, a *BasicBlock) bool {
if len(a.Succs) != 1 {
return false
}
b := a.Succs[0]
if len(b.Preds) != 1 {
return false
}
// Degenerate &&/|| ops may result in a straight-line CFG
// containing φ-nodes. (Ideally we'd replace such them with
// their sole operand but that requires Referrers, built later.)
if b.hasPhi() {
return false // not sound without further effort
}
// Eliminate jump at end of A, then copy all of B across.
a.Instrs = append(a.Instrs[:len(a.Instrs)-1], b.Instrs...)
for _, instr := range b.Instrs {
instr.setBlock(a)
}
// A inherits B's successors
a.Succs = append(a.succs2[:0], b.Succs...)
// Fix up Preds links of all successors of B.
for _, c := range b.Succs {
c.replacePred(b, a)
}
if debugBlockOpt {
fmt.Fprintln(os.Stderr, "fuseBlocks", a, b)
}
f.Blocks[b.Index] = nil // delete b
return true
}
// optimizeBlocks() performs some simple block optimizations on a
// completed function: dead block elimination, block fusion, jump
// threading.
//
func optimizeBlocks(f *Function) {
deleteUnreachableBlocks(f)
// Loop until no further progress.
changed := true
for changed {
changed = false
if debugBlockOpt {
f.WriteTo(os.Stderr)
mustSanityCheck(f, nil)
}
for _, b := range f.Blocks {
// f.Blocks will temporarily contain nils to indicate
// deleted blocks; we remove them at the end.
if b == nil {
continue
}
// Fuse blocks. b->c becomes bc.
if fuseBlocks(f, b) {
changed = true
}
// a->b->c becomes a->c if b contains only a Jump.
if jumpThreading(f, b) {
changed = true
continue // (b was disconnected)
}
}
}
f.removeNilBlocks()
}