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//   x := false
11//   if b {
12//     x = true
13//   }
14// into x = b.
15//
16// In SSA code this appears as
17//
18// b0
19//   If b -> b1 b2
20// b1
21//   Plain -> b2
22// b2
23//   x = (OpPhi (ConstBool [true]) (ConstBool [false]))
24//
25// In this case we can replace x with a copy of b.
26func phiopt(f *Func) {
27	sdom := f.Sdom()
28	for _, b := range f.Blocks {
29		if len(b.Preds) != 2 || len(b.Values) == 0 {
30			// TODO: handle more than 2 predecessors, e.g. a || b || c.
31			continue
32		}
33
34		pb0, b0 := b, b.Preds[0].b
35		for len(b0.Succs) == 1 && len(b0.Preds) == 1 {
36			pb0, b0 = b0, b0.Preds[0].b
37		}
38		if b0.Kind != BlockIf {
39			continue
40		}
41		pb1, b1 := b, b.Preds[1].b
42		for len(b1.Succs) == 1 && len(b1.Preds) == 1 {
43			pb1, b1 = b1, b1.Preds[0].b
44		}
45		if b1 != b0 {
46			continue
47		}
48		// b0 is the if block giving the boolean value.
49
50		// reverse is the predecessor from which the truth value comes.
51		var reverse int
52		if b0.Succs[0].b == pb0 && b0.Succs[1].b == pb1 {
53			reverse = 0
54		} else if b0.Succs[0].b == pb1 && b0.Succs[1].b == pb0 {
55			reverse = 1
56		} else {
57			b.Fatalf("invalid predecessors\n")
58		}
59
60		for _, v := range b.Values {
61			if v.Op != OpPhi {
62				continue
63			}
64
65			// Look for conversions from bool to 0/1.
66			if v.Type.IsInteger() {
67				phioptint(v, b0, reverse)
68			}
69
70			if !v.Type.IsBoolean() {
71				continue
72			}
73
74			// Replaces
75			//   if a { x = true } else { x = false } with x = a
76			// and
77			//   if a { x = false } else { x = true } with x = !a
78			if v.Args[0].Op == OpConstBool && v.Args[1].Op == OpConstBool {
79				if v.Args[reverse].AuxInt != v.Args[1-reverse].AuxInt {
80					ops := [2]Op{OpNot, OpCopy}
81					v.reset(ops[v.Args[reverse].AuxInt])
82					v.AddArg(b0.Controls[0])
83					if f.pass.debug > 0 {
84						f.Warnl(b.Pos, "converted OpPhi to %v", v.Op)
85					}
86					continue
87				}
88			}
89
90			// Replaces
91			//   if a { x = true } else { x = value } with x = a || value.
92			// Requires that value dominates x, meaning that regardless of a,
93			// value is always computed. This guarantees that the side effects
94			// of value are not seen if a is false.
95			if v.Args[reverse].Op == OpConstBool && v.Args[reverse].AuxInt == 1 {
96				if tmp := v.Args[1-reverse]; sdom.IsAncestorEq(tmp.Block, b) {
97					v.reset(OpOrB)
98					v.SetArgs2(b0.Controls[0], tmp)
99					if f.pass.debug > 0 {
100						f.Warnl(b.Pos, "converted OpPhi to %v", v.Op)
101					}
102					continue
103				}
104			}
105
106			// Replaces
107			//   if a { x = value } else { x = false } with x = a && value.
108			// Requires that value dominates x, meaning that regardless of a,
109			// value is always computed. This guarantees that the side effects
110			// of value are not seen if a is false.
111			if v.Args[1-reverse].Op == OpConstBool && v.Args[1-reverse].AuxInt == 0 {
112				if tmp := v.Args[reverse]; sdom.IsAncestorEq(tmp.Block, b) {
113					v.reset(OpAndB)
114					v.SetArgs2(b0.Controls[0], tmp)
115					if f.pass.debug > 0 {
116						f.Warnl(b.Pos, "converted OpPhi to %v", v.Op)
117					}
118					continue
119				}
120			}
121		}
122	}
123}
124
125func phioptint(v *Value, b0 *Block, reverse int) {
126	a0 := v.Args[0]
127	a1 := v.Args[1]
128	if a0.Op != a1.Op {
129		return
130	}
131
132	switch a0.Op {
133	case OpConst8, OpConst16, OpConst32, OpConst64:
134	default:
135		return
136	}
137
138	negate := false
139	switch {
140	case a0.AuxInt == 0 && a1.AuxInt == 1:
141		negate = true
142	case a0.AuxInt == 1 && a1.AuxInt == 0:
143	default:
144		return
145	}
146
147	if reverse == 1 {
148		negate = !negate
149	}
150
151	switch v.Type.Size() {
152	case 1:
153		v.reset(OpCopy)
154	case 2:
155		v.reset(OpZeroExt8to16)
156	case 4:
157		v.reset(OpZeroExt8to32)
158	case 8:
159		v.reset(OpZeroExt8to64)
160	default:
161		v.Fatalf("bad int size %d", v.Type.Size())
162	}
163
164	a := b0.Controls[0]
165	if negate {
166		a = v.Block.NewValue1(v.Pos, OpNot, a.Type, a)
167	}
168	v.AddArg(a)
169
170	f := b0.Func
171	if f.pass.debug > 0 {
172		f.Warnl(v.Block.Pos, "converted OpPhi bool -> int%d", v.Type.Size()*8)
173	}
174}
175