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// phiopt eliminates boolean Phis based on the previous if.
8//
9// Main use case is to transform:
10//
11//	x := false
12//	if b {
13//	  x = true
14//	}
15//
16// into x = b.
17//
18// In SSA code this appears as
19//
20//	b0
21//	  If b -> b1 b2
22//	b1
23//	  Plain -> b2
24//	b2
25//	  x = (OpPhi (ConstBool [true]) (ConstBool [false]))
26//
27// In this case we can replace x with a copy of b.
28func phiopt(f *Func) {
29	sdom := f.Sdom()
30	for _, b := range f.Blocks {
31		if len(b.Preds) != 2 || len(b.Values) == 0 {
32			// TODO: handle more than 2 predecessors, e.g. a || b || c.
33			continue
34		}
35
36		pb0, b0 := b, b.Preds[0].b
37		for len(b0.Succs) == 1 && len(b0.Preds) == 1 {
38			pb0, b0 = b0, b0.Preds[0].b
39		}
40		if b0.Kind != BlockIf {
41			continue
42		}
43		pb1, b1 := b, b.Preds[1].b
44		for len(b1.Succs) == 1 && len(b1.Preds) == 1 {
45			pb1, b1 = b1, b1.Preds[0].b
46		}
47		if b1 != b0 {
48			continue
49		}
50		// b0 is the if block giving the boolean value.
51		// reverse is the predecessor from which the truth value comes.
52		var reverse int
53		if b0.Succs[0].b == pb0 && b0.Succs[1].b == pb1 {
54			reverse = 0
55		} else if b0.Succs[0].b == pb1 && b0.Succs[1].b == pb0 {
56			reverse = 1
57		} else {
58			b.Fatalf("invalid predecessors\n")
59		}
60
61		for _, v := range b.Values {
62			if v.Op != OpPhi {
63				continue
64			}
65
66			// Look for conversions from bool to 0/1.
67			if v.Type.IsInteger() {
68				phioptint(v, b0, reverse)
69			}
70
71			if !v.Type.IsBoolean() {
72				continue
73			}
74
75			// Replaces
76			//   if a { x = true } else { x = false } with x = a
77			// and
78			//   if a { x = false } else { x = true } with x = !a
79			if v.Args[0].Op == OpConstBool && v.Args[1].Op == OpConstBool {
80				if v.Args[reverse].AuxInt != v.Args[1-reverse].AuxInt {
81					ops := [2]Op{OpNot, OpCopy}
82					v.reset(ops[v.Args[reverse].AuxInt])
83					v.AddArg(b0.Controls[0])
84					if f.pass.debug > 0 {
85						f.Warnl(b.Pos, "converted OpPhi to %v", v.Op)
86					}
87					continue
88				}
89			}
90
91			// Replaces
92			//   if a { x = true } else { x = value } with x = a || value.
93			// Requires that value dominates x, meaning that regardless of a,
94			// value is always computed. This guarantees that the side effects
95			// of value are not seen if a is false.
96			if v.Args[reverse].Op == OpConstBool && v.Args[reverse].AuxInt == 1 {
97				if tmp := v.Args[1-reverse]; sdom.IsAncestorEq(tmp.Block, b) {
98					v.reset(OpOrB)
99					v.SetArgs2(b0.Controls[0], tmp)
100					if f.pass.debug > 0 {
101						f.Warnl(b.Pos, "converted OpPhi to %v", v.Op)
102					}
103					continue
104				}
105			}
106
107			// Replaces
108			//   if a { x = value } else { x = false } with x = a && value.
109			// Requires that value dominates x, meaning that regardless of a,
110			// value is always computed. This guarantees that the side effects
111			// of value are not seen if a is false.
112			if v.Args[1-reverse].Op == OpConstBool && v.Args[1-reverse].AuxInt == 0 {
113				if tmp := v.Args[reverse]; sdom.IsAncestorEq(tmp.Block, b) {
114					v.reset(OpAndB)
115					v.SetArgs2(b0.Controls[0], tmp)
116					if f.pass.debug > 0 {
117						f.Warnl(b.Pos, "converted OpPhi to %v", v.Op)
118					}
119					continue
120				}
121			}
122		}
123	}
124	// strengthen phi optimization.
125	// Main use case is to transform:
126	//   x := false
127	//   if c {
128	//     x = true
129	//     ...
130	//   }
131	// into
132	//   x := c
133	//   if x { ... }
134	//
135	// For example, in SSA code a case appears as
136	// b0
137	//   If c -> b, sb0
138	// sb0
139	//   If d -> sd0, sd1
140	// sd1
141	//   ...
142	// sd0
143	//   Plain -> b
144	// b
145	//   x = (OpPhi (ConstBool [true]) (ConstBool [false]))
146	//
147	// In this case we can also replace x with a copy of c.
148	//
149	// The optimization idea:
150	// 1. block b has a phi value x, x = OpPhi (ConstBool [true]) (ConstBool [false]),
151	//    and len(b.Preds) is equal to 2.
152	// 2. find the common dominator(b0) of the predecessors(pb0, pb1) of block b, and the
153	//    dominator(b0) is a If block.
154	//    Special case: one of the predecessors(pb0 or pb1) is the dominator(b0).
155	// 3. the successors(sb0, sb1) of the dominator need to dominate the predecessors(pb0, pb1)
156	//    of block b respectively.
157	// 4. replace this boolean Phi based on dominator block.
158	//
159	//     b0(pb0)            b0(pb1)          b0
160	//    |  \               /  |             /  \
161	//    |  sb1           sb0  |           sb0  sb1
162	//    |  ...           ...  |           ...   ...
163	//    |  pb1           pb0  |           pb0  pb1
164	//    |  /               \  |            \   /
165	//     b                   b               b
166	//
167	var lca *lcaRange
168	for _, b := range f.Blocks {
169		if len(b.Preds) != 2 || len(b.Values) == 0 {
170			// TODO: handle more than 2 predecessors, e.g. a || b || c.
171			continue
172		}
173
174		for _, v := range b.Values {
175			// find a phi value v = OpPhi (ConstBool [true]) (ConstBool [false]).
176			// TODO: v = OpPhi (ConstBool [true]) (Arg <bool> {value})
177			if v.Op != OpPhi {
178				continue
179			}
180			if v.Args[0].Op != OpConstBool || v.Args[1].Op != OpConstBool {
181				continue
182			}
183			if v.Args[0].AuxInt == v.Args[1].AuxInt {
184				continue
185			}
186
187			pb0 := b.Preds[0].b
188			pb1 := b.Preds[1].b
189			if pb0.Kind == BlockIf && pb0 == sdom.Parent(b) {
190				// special case: pb0 is the dominator block b0.
191				//     b0(pb0)
192				//    |  \
193				//    |  sb1
194				//    |  ...
195				//    |  pb1
196				//    |  /
197				//     b
198				// if another successor sb1 of b0(pb0) dominates pb1, do replace.
199				ei := b.Preds[0].i
200				sb1 := pb0.Succs[1-ei].b
201				if sdom.IsAncestorEq(sb1, pb1) {
202					convertPhi(pb0, v, ei)
203					break
204				}
205			} else if pb1.Kind == BlockIf && pb1 == sdom.Parent(b) {
206				// special case: pb1 is the dominator block b0.
207				//       b0(pb1)
208				//     /   |
209				//    sb0  |
210				//    ...  |
211				//    pb0  |
212				//      \  |
213				//        b
214				// if another successor sb0 of b0(pb0) dominates pb0, do replace.
215				ei := b.Preds[1].i
216				sb0 := pb1.Succs[1-ei].b
217				if sdom.IsAncestorEq(sb0, pb0) {
218					convertPhi(pb1, v, 1-ei)
219					break
220				}
221			} else {
222				//      b0
223				//     /   \
224				//    sb0  sb1
225				//    ...  ...
226				//    pb0  pb1
227				//      \   /
228				//        b
229				//
230				// Build data structure for fast least-common-ancestor queries.
231				if lca == nil {
232					lca = makeLCArange(f)
233				}
234				b0 := lca.find(pb0, pb1)
235				if b0.Kind != BlockIf {
236					break
237				}
238				sb0 := b0.Succs[0].b
239				sb1 := b0.Succs[1].b
240				var reverse int
241				if sdom.IsAncestorEq(sb0, pb0) && sdom.IsAncestorEq(sb1, pb1) {
242					reverse = 0
243				} else if sdom.IsAncestorEq(sb1, pb0) && sdom.IsAncestorEq(sb0, pb1) {
244					reverse = 1
245				} else {
246					break
247				}
248				if len(sb0.Preds) != 1 || len(sb1.Preds) != 1 {
249					// we can not replace phi value x in the following case.
250					//   if gp == nil || sp < lo { x = true}
251					//   if a || b { x = true }
252					// so the if statement can only have one condition.
253					break
254				}
255				convertPhi(b0, v, reverse)
256			}
257		}
258	}
259}
260
261func phioptint(v *Value, b0 *Block, reverse int) {
262	a0 := v.Args[0]
263	a1 := v.Args[1]
264	if a0.Op != a1.Op {
265		return
266	}
267
268	switch a0.Op {
269	case OpConst8, OpConst16, OpConst32, OpConst64:
270	default:
271		return
272	}
273
274	negate := false
275	switch {
276	case a0.AuxInt == 0 && a1.AuxInt == 1:
277		negate = true
278	case a0.AuxInt == 1 && a1.AuxInt == 0:
279	default:
280		return
281	}
282
283	if reverse == 1 {
284		negate = !negate
285	}
286
287	a := b0.Controls[0]
288	if negate {
289		a = v.Block.NewValue1(v.Pos, OpNot, a.Type, a)
290	}
291	v.AddArg(a)
292
293	cvt := v.Block.NewValue1(v.Pos, OpCvtBoolToUint8, v.Block.Func.Config.Types.UInt8, a)
294	switch v.Type.Size() {
295	case 1:
296		v.reset(OpCopy)
297	case 2:
298		v.reset(OpZeroExt8to16)
299	case 4:
300		v.reset(OpZeroExt8to32)
301	case 8:
302		v.reset(OpZeroExt8to64)
303	default:
304		v.Fatalf("bad int size %d", v.Type.Size())
305	}
306	v.AddArg(cvt)
307
308	f := b0.Func
309	if f.pass.debug > 0 {
310		f.Warnl(v.Block.Pos, "converted OpPhi bool -> int%d", v.Type.Size()*8)
311	}
312}
313
314// b is the If block giving the boolean value.
315// v is the phi value v = (OpPhi (ConstBool [true]) (ConstBool [false])).
316// reverse is the predecessor from which the truth value comes.
317func convertPhi(b *Block, v *Value, reverse int) {
318	f := b.Func
319	ops := [2]Op{OpNot, OpCopy}
320	v.reset(ops[v.Args[reverse].AuxInt])
321	v.AddArg(b.Controls[0])
322	if f.pass.debug > 0 {
323		f.Warnl(b.Pos, "converted OpPhi to %v", v.Op)
324	}
325}
326