Source file src/pkg/cmd/compile/internal/ssa/shortcircuit.go

     1	// Copyright 2016 The Go Authors. All rights reserved.
     2	// Use of this source code is governed by a BSD-style
     3	// license that can be found in the LICENSE file.
     4	
     5	package ssa
     6	
     7	// Shortcircuit finds situations where branch directions
     8	// are always correlated and rewrites the CFG to take
     9	// advantage of that fact.
    10	// This optimization is useful for compiling && and || expressions.
    11	func shortcircuit(f *Func) {
    12		// Step 1: Replace a phi arg with a constant if that arg
    13		// is the control value of a preceding If block.
    14		// b1:
    15		//    If a goto b2 else b3
    16		// b2: <- b1 ...
    17		//    x = phi(a, ...)
    18		//
    19		// We can replace the "a" in the phi with the constant true.
    20		var ct, cf *Value
    21		for _, b := range f.Blocks {
    22			for _, v := range b.Values {
    23				if v.Op != OpPhi {
    24					continue
    25				}
    26				if !v.Type.IsBoolean() {
    27					continue
    28				}
    29				for i, a := range v.Args {
    30					e := b.Preds[i]
    31					p := e.b
    32					if p.Kind != BlockIf {
    33						continue
    34					}
    35					if p.Control != a {
    36						continue
    37					}
    38					if e.i == 0 {
    39						if ct == nil {
    40							ct = f.ConstBool(f.Config.Types.Bool, true)
    41						}
    42						v.SetArg(i, ct)
    43					} else {
    44						if cf == nil {
    45							cf = f.ConstBool(f.Config.Types.Bool, false)
    46						}
    47						v.SetArg(i, cf)
    48					}
    49				}
    50			}
    51		}
    52	
    53		// Step 2: Compute which values are live across blocks.
    54		live := make([]bool, f.NumValues())
    55		for _, b := range f.Blocks {
    56			for _, v := range b.Values {
    57				for _, a := range v.Args {
    58					if a.Block != v.Block {
    59						live[a.ID] = true
    60					}
    61				}
    62			}
    63			if b.Control != nil && b.Control.Block != b {
    64				live[b.Control.ID] = true
    65			}
    66		}
    67	
    68		// Step 3: Redirect control flow around known branches.
    69		// p:
    70		//   ... goto b ...
    71		// b: <- p ...
    72		//   v = phi(true, ...)
    73		//   if v goto t else u
    74		// We can redirect p to go directly to t instead of b.
    75		// (If v is not live after b).
    76		for _, b := range f.Blocks {
    77			if b.Kind != BlockIf {
    78				continue
    79			}
    80			if len(b.Values) != 1 {
    81				continue
    82			}
    83			v := b.Values[0]
    84			if v.Op != OpPhi {
    85				continue
    86			}
    87			if b.Control != v {
    88				continue
    89			}
    90			if live[v.ID] {
    91				continue
    92			}
    93			for i := 0; i < len(v.Args); i++ {
    94				a := v.Args[i]
    95				if a.Op != OpConstBool {
    96					continue
    97				}
    98	
    99				// The predecessor we come in from.
   100				e1 := b.Preds[i]
   101				p := e1.b
   102				pi := e1.i
   103	
   104				// The successor we always go to when coming in
   105				// from that predecessor.
   106				e2 := b.Succs[1-a.AuxInt]
   107				t := e2.b
   108				ti := e2.i
   109	
   110				// Remove b's incoming edge from p.
   111				b.removePred(i)
   112				n := len(b.Preds)
   113				v.Args[i].Uses--
   114				v.Args[i] = v.Args[n]
   115				v.Args[n] = nil
   116				v.Args = v.Args[:n]
   117	
   118				// Redirect p's outgoing edge to t.
   119				p.Succs[pi] = Edge{t, len(t.Preds)}
   120	
   121				// Fix up t to have one more predecessor.
   122				t.Preds = append(t.Preds, Edge{p, pi})
   123				for _, w := range t.Values {
   124					if w.Op != OpPhi {
   125						continue
   126					}
   127					w.AddArg(w.Args[ti])
   128				}
   129	
   130				if len(b.Preds) == 1 {
   131					v.Op = OpCopy
   132					// No longer a phi, stop optimizing here.
   133					break
   134				}
   135				i--
   136			}
   137		}
   138	}
   139	

View as plain text