blockopt.go

Documentation: golang.org/x/tools/go/ssa

     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  
     5  package ssa
     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  
    13  import (
    14  	"fmt"
    15  	"os"
    16  )
    17  
    18  // If true, perform sanity checking and show progress at each
    19  // successive iteration of optimizeBlocks.  Very verbose.
    20  const debugBlockOpt = false
    21  
    22  // markReachable sets Index=-1 for all blocks reachable from b.
    23  func markReachable(b *BasicBlock) {
    24  	b.Index = -1
    25  	for _, succ := range b.Succs {
    26  		if succ.Index == 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  func deleteUnreachableBlocks(f *Function) {
    35  	const white, black = 0, -1
    36  	// We borrow b.Index temporarily as the mark bit.
    37  	for _, b := range f.Blocks {
    38  		b.Index = white
    39  	}
    40  	markReachable(f.Blocks[0])
    41  	if f.Recover != nil {
    42  		markReachable(f.Recover)
    43  	}
    44  	for i, b := range f.Blocks {
    45  		if b.Index == white {
    46  			for _, c := range b.Succs {
    47  				if c.Index == black {
    48  					c.removePred(b) // delete white->black edge
    49  				}
    50  			}
    51  			if debugBlockOpt {
    52  				fmt.Fprintln(os.Stderr, "unreachable", b)
    53  			}
    54  			f.Blocks[i] = nil // delete b
    55  		}
    56  	}
    57  	f.removeNilBlocks()
    58  }
    59  
    60  // jumpThreading attempts to apply simple jump-threading to block b,
    61  // in which a->b->c become a->c if b is just a Jump.
    62  // The result is true if the optimization was applied.
    63  func jumpThreading(f *Function, b *BasicBlock) bool {
    64  	if b.Index == 0 {
    65  		return false // don't apply to entry block
    66  	}
    67  	if b.Instrs == nil {
    68  		return false
    69  	}
    70  	if _, ok := b.Instrs[0].(*Jump); !ok {
    71  		return false // not just a jump
    72  	}
    73  	c := b.Succs[0]
    74  	if c == b {
    75  		return false // don't apply to degenerate jump-to-self.
    76  	}
    77  	if c.hasPhi() {
    78  		return false // not sound without more effort
    79  	}
    80  	for j, a := range b.Preds {
    81  		a.replaceSucc(b, c)
    82  
    83  		// If a now has two edges to c, replace its degenerate If by Jump.
    84  		if len(a.Succs) == 2 && a.Succs[0] == c && a.Succs[1] == c {
    85  			jump := new(Jump)
    86  			jump.setBlock(a)
    87  			a.Instrs[len(a.Instrs)-1] = jump
    88  			a.Succs = a.Succs[:1]
    89  			c.removePred(b)
    90  		} else {
    91  			if j == 0 {
    92  				c.replacePred(b, a)
    93  			} else {
    94  				c.Preds = append(c.Preds, a)
    95  			}
    96  		}
    97  
    98  		if debugBlockOpt {
    99  			fmt.Fprintln(os.Stderr, "jumpThreading", a, b, c)
   100  		}
   101  	}
   102  	f.Blocks[b.Index] = nil // delete b
   103  	return true
   104  }
   105  
   106  // fuseBlocks attempts to apply the block fusion optimization to block
   107  // a, in which a->b becomes ab if len(a.Succs)==len(b.Preds)==1.
   108  // The result is true if the optimization was applied.
   109  func fuseBlocks(f *Function, a *BasicBlock) bool {
   110  	if len(a.Succs) != 1 {
   111  		return false
   112  	}
   113  	b := a.Succs[0]
   114  	if len(b.Preds) != 1 {
   115  		return false
   116  	}
   117  
   118  	// Degenerate &&/|| ops may result in a straight-line CFG
   119  	// containing φ-nodes. (Ideally we'd replace such them with
   120  	// their sole operand but that requires Referrers, built later.)
   121  	if b.hasPhi() {
   122  		return false // not sound without further effort
   123  	}
   124  
   125  	// Eliminate jump at end of A, then copy all of B across.
   126  	a.Instrs = append(a.Instrs[:len(a.Instrs)-1], b.Instrs...)
   127  	for _, instr := range b.Instrs {
   128  		instr.setBlock(a)
   129  	}
   130  
   131  	// A inherits B's successors
   132  	a.Succs = append(a.succs2[:0], b.Succs...)
   133  
   134  	// Fix up Preds links of all successors of B.
   135  	for _, c := range b.Succs {
   136  		c.replacePred(b, a)
   137  	}
   138  
   139  	if debugBlockOpt {
   140  		fmt.Fprintln(os.Stderr, "fuseBlocks", a, b)
   141  	}
   142  
   143  	f.Blocks[b.Index] = nil // delete b
   144  	return true
   145  }
   146  
   147  // optimizeBlocks() performs some simple block optimizations on a
   148  // completed function: dead block elimination, block fusion, jump
   149  // threading.
   150  func optimizeBlocks(f *Function) {
   151  	deleteUnreachableBlocks(f)
   152  
   153  	// Loop until no further progress.
   154  	changed := true
   155  	for changed {
   156  		changed = false
   157  
   158  		if debugBlockOpt {
   159  			f.WriteTo(os.Stderr)
   160  			mustSanityCheck(f, nil)
   161  		}
   162  
   163  		for _, b := range f.Blocks {
   164  			// f.Blocks will temporarily contain nils to indicate
   165  			// deleted blocks; we remove them at the end.
   166  			if b == nil {
   167  				continue
   168  			}
   169  
   170  			// Fuse blocks.  b->c becomes bc.
   171  			if fuseBlocks(f, b) {
   172  				changed = true
   173  			}
   174  
   175  			// a->b->c becomes a->c if b contains only a Jump.
   176  			if jumpThreading(f, b) {
   177  				changed = true
   178  				continue // (b was disconnected)
   179  			}
   180  		}
   181  	}
   182  	f.removeNilBlocks()
   183  }
   184
View as plain text