blob: ff05a04c471ce8be8311bce2c056bb9f27b51001 [file] [log] [blame]
// Copyright 2016 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
// Shortcircuit finds situations where branch directions
// are always correlated and rewrites the CFG to take
// advantage of that fact.
// This optimization is useful for compiling && and || expressions.
func shortcircuit(f *Func) {
// Step 1: Replace a phi arg with a constant if that arg
// is the control value of a preceding If block.
// b1:
// If a goto b2 else b3
// b2: <- b1 ...
// x = phi(a, ...)
//
// We can replace the "a" in the phi with the constant true.
ct := f.ConstBool(f.Entry.Line, f.Config.fe.TypeBool(), true)
cf := f.ConstBool(f.Entry.Line, f.Config.fe.TypeBool(), false)
for _, b := range f.Blocks {
for _, v := range b.Values {
if v.Op != OpPhi {
continue
}
if !v.Type.IsBoolean() {
continue
}
for i, a := range v.Args {
e := b.Preds[i]
p := e.b
if p.Kind != BlockIf {
continue
}
if p.Control != a {
continue
}
if e.i == 0 {
v.SetArg(i, ct)
} else {
v.SetArg(i, cf)
}
}
}
}
// Step 2: Compute which values are live across blocks.
live := make([]bool, f.NumValues())
for _, b := range f.Blocks {
for _, v := range b.Values {
for _, a := range v.Args {
if a.Block != v.Block {
live[a.ID] = true
}
}
}
if b.Control != nil && b.Control.Block != b {
live[b.Control.ID] = true
}
}
// Step 3: Redirect control flow around known branches.
// p:
// ... goto b ...
// b: <- p ...
// v = phi(true, ...)
// if v goto t else u
// We can redirect p to go directly to t instead of b.
// (If v is not live after b).
for _, b := range f.Blocks {
if b.Kind != BlockIf {
continue
}
if len(b.Values) != 1 {
continue
}
v := b.Values[0]
if v.Op != OpPhi {
continue
}
if b.Control != v {
continue
}
if live[v.ID] {
continue
}
for i := 0; i < len(v.Args); i++ {
a := v.Args[i]
if a.Op != OpConstBool {
continue
}
// The predecessor we come in from.
e1 := b.Preds[i]
p := e1.b
pi := e1.i
// The successor we always go to when coming in
// from that predecessor.
e2 := b.Succs[1-a.AuxInt]
t := e2.b
ti := e2.i
// Remove b's incoming edge from p.
b.removePred(i)
n := len(b.Preds)
v.Args[i].Uses--
v.Args[i] = v.Args[n]
v.Args[n] = nil
v.Args = v.Args[:n]
// Redirect p's outgoing edge to t.
p.Succs[pi] = Edge{t, len(t.Preds)}
// Fix up t to have one more predecessor.
t.Preds = append(t.Preds, Edge{p, pi})
for _, w := range t.Values {
if w.Op != OpPhi {
continue
}
w.AddArg(w.Args[ti])
}
if len(b.Preds) == 1 {
v.Op = OpCopy
// No longer a phi, stop optimizing here.
break
}
i--
}
}
}