diff options
Diffstat (limited to 'vendor/golang.org/x/tools/go/ssa/blockopt.go')
-rw-r--r-- | vendor/golang.org/x/tools/go/ssa/blockopt.go | 187 |
1 files changed, 0 insertions, 187 deletions
diff --git a/vendor/golang.org/x/tools/go/ssa/blockopt.go b/vendor/golang.org/x/tools/go/ssa/blockopt.go deleted file mode 100644 index e79260a..0000000 --- a/vendor/golang.org/x/tools/go/ssa/blockopt.go +++ /dev/null @@ -1,187 +0,0 @@ -// 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() -} |