blob: 6d3fb70780591c4b7f0922f29df505d32a439518 [file] [log] [blame]
// Copyright 2015 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
import (
"cmd/internal/src"
"fmt"
)
// fuseEarly runs fuse(f, fuseTypePlain|fuseTypeIntInRange).
func fuseEarly(f *Func) { fuse(f, fuseTypePlain|fuseTypeIntInRange) }
// fuseLate runs fuse(f, fuseTypePlain|fuseTypeIf|fuseTypeBranchRedirect).
func fuseLate(f *Func) { fuse(f, fuseTypePlain|fuseTypeIf|fuseTypeBranchRedirect) }
type fuseType uint8
const (
fuseTypePlain fuseType = 1 << iota
fuseTypeIf
fuseTypeIntInRange
fuseTypeBranchRedirect
fuseTypeShortCircuit
)
// fuse simplifies control flow by joining basic blocks.
func fuse(f *Func, typ fuseType) {
for changed := true; changed; {
changed = false
// Be sure to avoid quadratic behavior in fuseBlockPlain. See issue 13554.
// Previously this was dealt with using backwards iteration, now fuseBlockPlain
// handles large runs of blocks.
for i := len(f.Blocks) - 1; i >= 0; i-- {
b := f.Blocks[i]
if typ&fuseTypeIf != 0 {
changed = fuseBlockIf(b) || changed
}
if typ&fuseTypeIntInRange != 0 {
changed = fuseIntegerComparisons(b) || changed
}
if typ&fuseTypePlain != 0 {
changed = fuseBlockPlain(b) || changed
}
if typ&fuseTypeShortCircuit != 0 {
changed = shortcircuitBlock(b) || changed
}
}
if typ&fuseTypeBranchRedirect != 0 {
changed = fuseBranchRedirect(f) || changed
}
if changed {
f.invalidateCFG()
}
}
}
// fuseBlockIf handles the following cases where s0 and s1 are empty blocks.
//
// b b b b
// \ / \ / | \ / \ / | | |
// s0 s1 | s1 s0 | | |
// \ / | / \ | | |
// ss ss ss ss
//
// If all Phi ops in ss have identical variables for slots corresponding to
// s0, s1 and b then the branch can be dropped.
// This optimization often comes up in switch statements with multiple
// expressions in a case clause:
//
// switch n {
// case 1,2,3: return 4
// }
//
// TODO: If ss doesn't contain any OpPhis, are s0 and s1 dead code anyway.
func fuseBlockIf(b *Block) bool {
if b.Kind != BlockIf {
return false
}
// It doesn't matter how much Preds does s0 or s1 have.
var ss0, ss1 *Block
s0 := b.Succs[0].b
i0 := b.Succs[0].i
if s0.Kind != BlockPlain || !isEmpty(s0) {
s0, ss0 = b, s0
} else {
ss0 = s0.Succs[0].b
i0 = s0.Succs[0].i
}
s1 := b.Succs[1].b
i1 := b.Succs[1].i
if s1.Kind != BlockPlain || !isEmpty(s1) {
s1, ss1 = b, s1
} else {
ss1 = s1.Succs[0].b
i1 = s1.Succs[0].i
}
if ss0 != ss1 {
if s0.Kind == BlockPlain && isEmpty(s0) && s1.Kind == BlockPlain && isEmpty(s1) {
// Two special cases where both s0, s1 and ss are empty blocks.
if s0 == ss1 {
s0, ss0 = b, ss1
} else if ss0 == s1 {
s1, ss1 = b, ss0
} else {
return false
}
} else {
return false
}
}
ss := ss0
// s0 and s1 are equal with b if the corresponding block is missing
// (2nd, 3rd and 4th case in the figure).
for _, v := range ss.Values {
if v.Op == OpPhi && v.Uses > 0 && v.Args[i0] != v.Args[i1] {
return false
}
}
// We do not need to redirect the Preds of s0 and s1 to ss,
// the following optimization will do this.
b.removeEdge(0)
if s0 != b && len(s0.Preds) == 0 {
s0.removeEdge(0)
// Move any (dead) values in s0 to b,
// where they will be eliminated by the next deadcode pass.
for _, v := range s0.Values {
v.Block = b
}
b.Values = append(b.Values, s0.Values...)
// Clear s0.
s0.Kind = BlockInvalid
s0.Values = nil
s0.Succs = nil
s0.Preds = nil
}
b.Kind = BlockPlain
b.Likely = BranchUnknown
b.ResetControls()
// The values in b may be dead codes, and clearing them in time may
// obtain new optimization opportunities.
// First put dead values that can be deleted into a slice walkValues.
// Then put their arguments in walkValues before resetting the dead values
// in walkValues, because the arguments may also become dead values.
walkValues := []*Value{}
for _, v := range b.Values {
if v.Uses == 0 && v.removeable() {
walkValues = append(walkValues, v)
}
}
for len(walkValues) != 0 {
v := walkValues[len(walkValues)-1]
walkValues = walkValues[:len(walkValues)-1]
if v.Uses == 0 && v.removeable() {
walkValues = append(walkValues, v.Args...)
v.reset(OpInvalid)
}
}
return true
}
// isEmpty reports whether b contains any live values.
// There may be false positives.
func isEmpty(b *Block) bool {
for _, v := range b.Values {
if v.Uses > 0 || v.Op.IsCall() || v.Op.HasSideEffects() || v.Type.IsVoid() {
return false
}
}
return true
}
// fuseBlockPlain handles a run of blocks with length >= 2,
// whose interior has single predecessors and successors,
// b must be BlockPlain, allowing it to be any node except the
// last (multiple successors means not BlockPlain).
// Cycles are handled and merged into b's successor.
func fuseBlockPlain(b *Block) bool {
if b.Kind != BlockPlain {
return false
}
c := b.Succs[0].b
if len(c.Preds) != 1 || c == b { // At least 2 distinct blocks.
return false
}
// find earliest block in run. Avoid simple cycles.
for len(b.Preds) == 1 && b.Preds[0].b != c && b.Preds[0].b.Kind == BlockPlain {
b = b.Preds[0].b
}
// find latest block in run. Still beware of simple cycles.
for {
if c.Kind != BlockPlain {
break
} // Has exactly 1 successor
cNext := c.Succs[0].b
if cNext == b {
break
} // not a cycle
if len(cNext.Preds) != 1 {
break
} // no other incoming edge
c = cNext
}
// Try to preserve any statement marks on the ends of blocks; move values to C
var b_next *Block
for bx := b; bx != c; bx = b_next {
// For each bx with an end-of-block statement marker,
// try to move it to a value in the next block,
// or to the next block's end, if possible.
b_next = bx.Succs[0].b
if bx.Pos.IsStmt() == src.PosIsStmt {
l := bx.Pos.Line() // looking for another place to mark for line l
outOfOrder := false
for _, v := range b_next.Values {
if v.Pos.IsStmt() == src.PosNotStmt {
continue
}
if l == v.Pos.Line() { // Found a Value with same line, therefore done.
v.Pos = v.Pos.WithIsStmt()
l = 0
break
}
if l < v.Pos.Line() {
// The order of values in a block is not specified so OOO in a block is not interesting,
// but they do all come before the end of the block, so this disqualifies attaching to end of b_next.
outOfOrder = true
}
}
if l != 0 && !outOfOrder && (b_next.Pos.Line() == l || b_next.Pos.IsStmt() != src.PosIsStmt) {
b_next.Pos = bx.Pos.WithIsStmt()
}
}
// move all of bx's values to c (note containing loop excludes c)
for _, v := range bx.Values {
v.Block = c
}
}
// Compute the total number of values and find the largest value slice in the run, to maximize chance of storage reuse.
total := 0
totalBeforeMax := 0 // number of elements preceding the maximum block (i.e. its position in the result).
max_b := b // block with maximum capacity
for bx := b; ; bx = bx.Succs[0].b {
if cap(bx.Values) > cap(max_b.Values) {
totalBeforeMax = total
max_b = bx
}
total += len(bx.Values)
if bx == c {
break
}
}
// Use c's storage if fused blocks will fit, else use the max if that will fit, else allocate new storage.
// Take care to avoid c.Values pointing to b.valstorage.
// See golang.org/issue/18602.
// It's important to keep the elements in the same order; maintenance of
// debugging information depends on the order of *Values in Blocks.
// This can also cause changes in the order (which may affect other
// optimizations and possibly compiler output) for 32-vs-64 bit compilation
// platforms (word size affects allocation bucket size affects slice capacity).
// figure out what slice will hold the values,
// preposition the destination elements if not allocating new storage
var t []*Value
if total <= len(c.valstorage) {
t = c.valstorage[:total]
max_b = c
totalBeforeMax = total - len(c.Values)
copy(t[totalBeforeMax:], c.Values)
} else if total <= cap(max_b.Values) { // in place, somewhere
t = max_b.Values[0:total]
copy(t[totalBeforeMax:], max_b.Values)
} else {
t = make([]*Value, total)
max_b = nil
}
// copy the values
copyTo := 0
for bx := b; ; bx = bx.Succs[0].b {
if bx != max_b {
copy(t[copyTo:], bx.Values)
} else if copyTo != totalBeforeMax { // trust but verify.
panic(fmt.Errorf("totalBeforeMax (%d) != copyTo (%d), max_b=%v, b=%v, c=%v", totalBeforeMax, copyTo, max_b, b, c))
}
if bx == c {
break
}
copyTo += len(bx.Values)
}
c.Values = t
// replace b->c edge with preds(b) -> c
c.predstorage[0] = Edge{}
if len(b.Preds) > len(b.predstorage) {
c.Preds = b.Preds
} else {
c.Preds = append(c.predstorage[:0], b.Preds...)
}
for i, e := range c.Preds {
p := e.b
p.Succs[e.i] = Edge{c, i}
}
f := b.Func
if f.Entry == b {
f.Entry = c
}
// trash b's fields, just in case
for bx := b; bx != c; bx = b_next {
b_next = bx.Succs[0].b
bx.Kind = BlockInvalid
bx.Values = nil
bx.Preds = nil
bx.Succs = nil
}
return true
}