shortcircuit.go

Documentation: cmd/compile/internal/ssa

     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