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
5package 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.
11func 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.Controls[0] != 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: Redirect control flow around known branches.
54	// p:
55	//   ... goto b ...
56	// b: <- p ...
57	//   v = phi(true, ...)
58	//   if v goto t else u
59	// We can redirect p to go directly to t instead of b.
60	// (If v is not live after b).
61	for changed := true; changed; {
62		changed = false
63		for i := len(f.Blocks) - 1; i >= 0; i-- {
64			b := f.Blocks[i]
65			if fuseBlockPlain(b) {
66				changed = true
67				continue
68			}
69			changed = shortcircuitBlock(b) || changed
70		}
71		if changed {
72			f.invalidateCFG()
73		}
74	}
75}
76
77// shortcircuitBlock checks for a CFG of the form
78//
79//   p   other pred(s)
80//    \ /
81//     b
82//    / \
83//   s   other succ
84//
85// in which b is an If block containing a single phi value with a single use,
86// which has a ConstBool arg.
87// The only use of the phi value must be the control value of b.
88// p is the predecessor determined by the argument slot in which the ConstBool is found.
89//
90// It rewrites this into
91//
92//   p   other pred(s)
93//   |  /
94//   | b
95//   |/ \
96//   s   other succ
97//
98// and removes the appropriate phi arg(s).
99func shortcircuitBlock(b *Block) bool {
100	if b.Kind != BlockIf {
101		return false
102	}
103	// Look for control values of the form Copy(Not(Copy(Phi(const, ...)))).
104	// Those must be the only values in the b, and they each must be used only by b.
105	// Track the negations so that we can swap successors as needed later.
106	v := b.Controls[0]
107	nval := 1 // the control value
108	swap := false
109	for v.Uses == 1 && v.Block == b && (v.Op == OpCopy || v.Op == OpNot) {
110		if v.Op == OpNot {
111			swap = !swap
112		}
113		v = v.Args[0]
114		nval++ // wrapper around control value
115	}
116	if len(b.Values) != nval || v.Op != OpPhi || v.Block != b || v.Uses != 1 {
117		return false
118	}
119
120	// Check for const phi args.
121	var changed bool
122	for i := 0; i < len(v.Args); i++ {
123		a := v.Args[i]
124		if a.Op != OpConstBool {
125			continue
126		}
127		// The predecessor we come in from.
128		e1 := b.Preds[i]
129		p := e1.b
130		pi := e1.i
131
132		// The successor we always go to when coming in
133		// from that predecessor.
134		si := 1 - a.AuxInt
135		if swap {
136			si = 1 - si
137		}
138		e2 := b.Succs[si]
139		t := e2.b
140		if p == b || t == b {
141			// This is an infinite loop; we can't remove it. See issue 33903.
142			continue
143		}
144		ti := e2.i
145
146		// Update CFG and Phis.
147		changed = true
148
149		// Remove b's incoming edge from p.
150		b.removePred(i)
151		n := len(b.Preds)
152		v.Args[i].Uses--
153		v.Args[i] = v.Args[n]
154		v.Args[n] = nil
155		v.Args = v.Args[:n]
156
157		// Redirect p's outgoing edge to t.
158		p.Succs[pi] = Edge{t, len(t.Preds)}
159
160		// Fix up t to have one more predecessor.
161		t.Preds = append(t.Preds, Edge{p, pi})
162		for _, w := range t.Values {
163			if w.Op != OpPhi {
164				continue
165			}
166			w.AddArg(w.Args[ti])
167		}
168		i--
169	}
170
171	if !changed {
172		return false
173	}
174
175	if len(b.Preds) == 0 {
176		// Block is now dead.
177		b.Kind = BlockInvalid
178		return true
179	}
180
181	phielimValue(v)
182	return true
183}
184