From d8a65672f8605d9d51fd90996162ab8d79a4aa32 Mon Sep 17 00:00:00 2001 From: Keith Randall Date: Mon, 25 Jan 2016 09:21:17 -0800 Subject: [PATCH] [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 --- src/cmd/compile/internal/ssa/compile.go | 1 + .../compile/internal/ssa/gen/genericOps.go | 31 ++-- src/cmd/compile/internal/ssa/shortcircuit.go | 144 ++++++++++++++++++ .../compile/internal/ssa/shortcircuit_test.go | 50 ++++++ 4 files changed, 208 insertions(+), 18 deletions(-) create mode 100644 src/cmd/compile/internal/ssa/shortcircuit.go create mode 100644 src/cmd/compile/internal/ssa/shortcircuit_test.go diff --git a/src/cmd/compile/internal/ssa/compile.go b/src/cmd/compile/internal/ssa/compile.go index 121c1e1a37..75c73eb24f 100644 --- a/src/cmd/compile/internal/ssa/compile.go +++ b/src/cmd/compile/internal/ssa/compile.go @@ -89,6 +89,7 @@ var passes = [...]pass{ {"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 107c145dac..36dd58cd1d 100644 --- a/src/cmd/compile/internal/ssa/gen/genericOps.go +++ b/src/cmd/compile/internal/ssa/gen/genericOps.go @@ -245,24 +245,19 @@ var genericOps = []opData{ // 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 0000000000..d22a61a0af --- /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 0000000000..d518dfbabf --- /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) + } + } + } +} -- 2.48.1