[dev.ssa] cmd/compile: optimization for && and || expressions
Compiling && and || expressions often leads to control
flow of the following form:
p:
If a goto b else c
b: <- p ...
x = phi(a, ...)
If x goto t else u
Note that if we take the edge p->b, then we are guaranteed
to take the edge b->t also. So in this situation, we might
as well go directly from p to t.
Change-Id: I6974f1e6367119a2ddf2014f9741fdb490edcc12
Reviewed-on: https://go-review.googlesource.com/18910
Reviewed-by: David Chase <drchase@google.com>
diff --git a/src/cmd/compile/internal/ssa/compile.go b/src/cmd/compile/internal/ssa/compile.go
index 121c1e1..75c73eb 100644
--- a/src/cmd/compile/internal/ssa/compile.go
+++ b/src/cmd/compile/internal/ssa/compile.go
@@ -89,6 +89,7 @@
{"early phielim", phielim, false},
{"early copyelim", copyelim, false},
{"early deadcode", deadcode, false}, // remove generated dead code to avoid doing pointless work during opt
+ {"short circuit", shortcircuit, false},
{"decompose", decompose, true},
{"opt", opt, true}, // TODO: split required rules and optimizing rules
{"opt deadcode", deadcode, false}, // remove any blocks orphaned during opt
diff --git a/src/cmd/compile/internal/ssa/gen/genericOps.go b/src/cmd/compile/internal/ssa/gen/genericOps.go
index 107c145..36dd58c 100644
--- a/src/cmd/compile/internal/ssa/gen/genericOps.go
+++ b/src/cmd/compile/internal/ssa/gen/genericOps.go
@@ -245,24 +245,19 @@
// arg0=ptr/int arg1=mem, output=int/ptr
{name: "Convert"},
- // constants. Constant values are stored in the aux field.
- // booleans have a bool aux field, strings have a string aux
- // field, and so on. All integer types store their value
- // in the AuxInt field as an int64 (including int, uint64, etc.).
- // For integer types smaller than 64 bits, only the low-order
- // bits of the AuxInt field matter.
- {name: "ConstBool"},
- {name: "ConstString"},
- {name: "ConstNil", typ: "BytePtr"},
- {name: "Const8"},
- {name: "Const16"},
- {name: "Const32"},
- {name: "Const64"},
- {name: "Const32F"},
- {name: "Const64F"},
- {name: "ConstInterface"}, // nil interface
- {name: "ConstSlice"}, // nil slice
- // TODO: Const32F, ...
+ // constants. Constant values are stored in the aux or
+ // auxint fields.
+ {name: "ConstBool"}, // auxint is 0 for false and 1 for true
+ {name: "ConstString"}, // value is aux.(string)
+ {name: "ConstNil", typ: "BytePtr"}, // nil pointer
+ {name: "Const8"}, // value is low 8 bits of auxint
+ {name: "Const16"}, // value is low 16 bits of auxint
+ {name: "Const32"}, // value is low 32 bits of auxint
+ {name: "Const64"}, // value is auxint
+ {name: "Const32F"}, // value is math.Float64frombits(uint64(auxint))
+ {name: "Const64F"}, // value is math.Float64frombits(uint64(auxint))
+ {name: "ConstInterface"}, // nil interface
+ {name: "ConstSlice"}, // nil slice
// Constant-like things
{name: "InitMem"}, // memory input to the function.
diff --git a/src/cmd/compile/internal/ssa/shortcircuit.go b/src/cmd/compile/internal/ssa/shortcircuit.go
new file mode 100644
index 0000000..d22a61a
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/shortcircuit.go
@@ -0,0 +1,144 @@
+// 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 {
+ p := b.Preds[i]
+ if p.Kind != BlockIf {
+ continue
+ }
+ if p.Control != a {
+ continue
+ }
+ if p.Succs[0] == b {
+ v.Args[i] = ct
+ } else {
+ v.Args[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.
+ p := b.Preds[i]
+ // The successor we always go to when coming in
+ // from that predecessor.
+ t := b.Succs[1-a.AuxInt]
+
+ // Change the edge p->b to p->t.
+ for j, x := range p.Succs {
+ if x == b {
+ p.Succs[j] = t
+ break
+ }
+ }
+
+ // Fix up t to have one more predecessor.
+ j := predIdx(t, b)
+ t.Preds = append(t.Preds, p)
+ for _, w := range t.Values {
+ if w.Op != OpPhi {
+ continue
+ }
+ w.Args = append(w.Args, w.Args[j])
+ }
+
+ // Fix up b to have one less predecessor.
+ n := len(b.Preds) - 1
+ b.Preds[i] = b.Preds[n]
+ b.Preds[n] = nil
+ b.Preds = b.Preds[:n]
+ v.Args[i] = v.Args[n]
+ v.Args[n] = nil
+ v.Args = v.Args[:n]
+ if n == 1 {
+ v.Op = OpCopy
+ // No longer a phi, stop optimizing here.
+ break
+ }
+ i--
+ }
+ }
+}
+
+// predIdx returns the index where p appears in the predecessor list of b.
+// p must be in the predecessor list of b.
+func predIdx(b, p *Block) int {
+ for i, x := range b.Preds {
+ if x == p {
+ return i
+ }
+ }
+ panic("predecessor not found")
+}
diff --git a/src/cmd/compile/internal/ssa/shortcircuit_test.go b/src/cmd/compile/internal/ssa/shortcircuit_test.go
new file mode 100644
index 0000000..d518dfb
--- /dev/null
+++ b/src/cmd/compile/internal/ssa/shortcircuit_test.go
@@ -0,0 +1,50 @@
+// 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
+
+import "testing"
+
+func TestShortCircuit(t *testing.T) {
+ c := testConfig(t)
+
+ fun := Fun(c, "entry",
+ Bloc("entry",
+ Valu("mem", OpInitMem, TypeMem, 0, ".mem"),
+ Valu("arg1", OpArg, TypeInt64, 0, nil),
+ Valu("arg2", OpArg, TypeInt64, 0, nil),
+ Valu("arg3", OpArg, TypeInt64, 0, nil),
+ Goto("b1")),
+ Bloc("b1",
+ Valu("cmp1", OpLess64, TypeBool, 0, nil, "arg1", "arg2"),
+ If("cmp1", "b2", "b3")),
+ Bloc("b2",
+ Valu("cmp2", OpLess64, TypeBool, 0, nil, "arg2", "arg3"),
+ Goto("b3")),
+ Bloc("b3",
+ Valu("phi2", OpPhi, TypeBool, 0, nil, "cmp1", "cmp2"),
+ If("phi2", "b4", "b5")),
+ Bloc("b4",
+ Valu("cmp3", OpLess64, TypeBool, 0, nil, "arg3", "arg1"),
+ Goto("b5")),
+ Bloc("b5",
+ Valu("phi3", OpPhi, TypeBool, 0, nil, "phi2", "cmp3"),
+ If("phi3", "b6", "b7")),
+ Bloc("b6",
+ Exit("mem")),
+ Bloc("b7",
+ Exit("mem")))
+
+ CheckFunc(fun.f)
+ shortcircuit(fun.f)
+ CheckFunc(fun.f)
+
+ for _, b := range fun.f.Blocks {
+ for _, v := range b.Values {
+ if v.Op == OpPhi {
+ t.Errorf("phi %s remains", v)
+ }
+ }
+ }
+}
