Home | History | Annotate | Download | only in 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 	ct := f.ConstBool(f.Entry.Line, f.Config.fe.TypeBool(), true)
     21 	cf := f.ConstBool(f.Entry.Line, f.Config.fe.TypeBool(), false)
     22 	for _, b := range f.Blocks {
     23 		for _, v := range b.Values {
     24 			if v.Op != OpPhi {
     25 				continue
     26 			}
     27 			if !v.Type.IsBoolean() {
     28 				continue
     29 			}
     30 			for i, a := range v.Args {
     31 				e := b.Preds[i]
     32 				p := e.b
     33 				if p.Kind != BlockIf {
     34 					continue
     35 				}
     36 				if p.Control != a {
     37 					continue
     38 				}
     39 				if e.i == 0 {
     40 					v.SetArg(i, ct)
     41 				} else {
     42 					v.SetArg(i, cf)
     43 				}
     44 			}
     45 		}
     46 	}
     47 
     48 	// Step 2: Compute which values are live across blocks.
     49 	live := make([]bool, f.NumValues())
     50 	for _, b := range f.Blocks {
     51 		for _, v := range b.Values {
     52 			for _, a := range v.Args {
     53 				if a.Block != v.Block {
     54 					live[a.ID] = true
     55 				}
     56 			}
     57 		}
     58 		if b.Control != nil && b.Control.Block != b {
     59 			live[b.Control.ID] = true
     60 		}
     61 	}
     62 
     63 	// Step 3: Redirect control flow around known branches.
     64 	// p:
     65 	//   ... goto b ...
     66 	// b: <- p ...
     67 	//   v = phi(true, ...)
     68 	//   if v goto t else u
     69 	// We can redirect p to go directly to t instead of b.
     70 	// (If v is not live after b).
     71 	for _, b := range f.Blocks {
     72 		if b.Kind != BlockIf {
     73 			continue
     74 		}
     75 		if len(b.Values) != 1 {
     76 			continue
     77 		}
     78 		v := b.Values[0]
     79 		if v.Op != OpPhi {
     80 			continue
     81 		}
     82 		if b.Control != v {
     83 			continue
     84 		}
     85 		if live[v.ID] {
     86 			continue
     87 		}
     88 		for i := 0; i < len(v.Args); i++ {
     89 			a := v.Args[i]
     90 			if a.Op != OpConstBool {
     91 				continue
     92 			}
     93 
     94 			// The predecessor we come in from.
     95 			e1 := b.Preds[i]
     96 			p := e1.b
     97 			pi := e1.i
     98 
     99 			// The successor we always go to when coming in
    100 			// from that predecessor.
    101 			e2 := b.Succs[1-a.AuxInt]
    102 			t := e2.b
    103 			ti := e2.i
    104 
    105 			// Remove b's incoming edge from p.
    106 			b.removePred(i)
    107 			n := len(b.Preds)
    108 			v.Args[i].Uses--
    109 			v.Args[i] = v.Args[n]
    110 			v.Args[n] = nil
    111 			v.Args = v.Args[:n]
    112 
    113 			// Redirect p's outgoing edge to t.
    114 			p.Succs[pi] = Edge{t, len(t.Preds)}
    115 
    116 			// Fix up t to have one more predecessor.
    117 			t.Preds = append(t.Preds, Edge{p, pi})
    118 			for _, w := range t.Values {
    119 				if w.Op != OpPhi {
    120 					continue
    121 				}
    122 				w.AddArg(w.Args[ti])
    123 			}
    124 
    125 			if len(b.Preds) == 1 {
    126 				v.Op = OpCopy
    127 				// No longer a phi, stop optimizing here.
    128 				break
    129 			}
    130 			i--
    131 		}
    132 	}
    133 }
    134