src

blockopt.go (4484B)

---

 // 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()
 }