| // 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-- |
| } |
| } |
| } |