+++ /dev/null
-// 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 ir
-
-// 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.gaps = -1
- for _, succ := range b.Succs {
- if succ.gaps == 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.gaps temporarily as the mark bit.
- for _, b := range f.Blocks {
- b.gaps = white
- }
- markReachable(f.Blocks[0])
- // In SSI form, we need the exit to be reachable for correct
- // post-dominance information. In original form, however, we
- // cannot unconditionally mark it reachable because we won't
- // be adding fake edges, and this breaks the calculation of
- // dominance information.
- markReachable(f.Exit)
- for i, b := range f.Blocks {
- if b.gaps == white {
- for _, c := range b.Succs {
- if c.gaps == 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
- }
- for _, pred := range b.Preds {
- switch pred.Control().(type) {
- case *ConstantSwitch:
- // don't optimize away the head blocks of switch statements
- 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
- }
- if a.Succs[0] == f.Exit {
- return false
- }
- b := a.Succs[0]
- if len(b.Preds) != 1 {
- return false
- }
- if _, ok := a.Instrs[len(a.Instrs)-1].(*Panic); ok {
- // panics aren't simple jumps, they have side effects.
- 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) {
- if debugBlockOpt {
- f.WriteTo(os.Stderr)
- mustSanityCheck(f, nil)
- }
-
- 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()
-}
projects / dotfiles / .git / blobdiff