1// Copyright 2021 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// fuseBranchRedirect checks for a CFG in which the outbound branch
8// of an If block can be derived from its predecessor If block, in
9// some such cases, we can redirect the predecessor If block to the
10// corresponding successor block directly. For example:
11//
12//	p:
13//	  v11 = Less64 <bool> v10 v8
14//	  If v11 goto b else u
15//	b: <- p ...
16//	  v17 = Leq64 <bool> v10 v8
17//	  If v17 goto s else o
18//
19// We can redirect p to s directly.
20//
21// The implementation here borrows the framework of the prove pass.
22//
23//	1, Traverse all blocks of function f to find If blocks.
24//	2,   For any If block b, traverse all its predecessors to find If blocks.
25//	3,     For any If block predecessor p, update relationship p->b.
26//	4,     Traverse all successors of b.
27//	5,       For any successor s of b, try to update relationship b->s, if a
28//	         contradiction is found then redirect p to another successor of b.
29func fuseBranchRedirect(f *Func) bool {
30	ft := newFactsTable(f)
31	ft.checkpoint()
32
33	changed := false
34	for i := len(f.Blocks) - 1; i >= 0; i-- {
35		b := f.Blocks[i]
36		if b.Kind != BlockIf {
37			continue
38		}
39		// b is either empty or only contains the control value.
40		// TODO: if b contains only OpCopy or OpNot related to b.Controls,
41		// such as Copy(Not(Copy(Less64(v1, v2)))), perhaps it can be optimized.
42		bCtl := b.Controls[0]
43		if bCtl.Block != b && len(b.Values) != 0 || (len(b.Values) != 1 || bCtl.Uses != 1) && bCtl.Block == b {
44			continue
45		}
46
47		for k := 0; k < len(b.Preds); k++ {
48			pk := b.Preds[k]
49			p := pk.b
50			if p.Kind != BlockIf || p == b {
51				continue
52			}
53			pbranch := positive
54			if pk.i == 1 {
55				pbranch = negative
56			}
57			ft.checkpoint()
58			// Assume branch p->b is taken.
59			addBranchRestrictions(ft, p, pbranch)
60			// Check if any outgoing branch is unreachable based on the above condition.
61			parent := b
62			for j, bbranch := range [...]branch{positive, negative} {
63				ft.checkpoint()
64				// Try to update relationship b->child, and check if the contradiction occurs.
65				addBranchRestrictions(ft, parent, bbranch)
66				unsat := ft.unsat
67				ft.restore()
68				if !unsat {
69					continue
70				}
71				// This branch is impossible,so redirect p directly to another branch.
72				out := 1 ^ j
73				child := parent.Succs[out].b
74				if child == b {
75					continue
76				}
77				b.removePred(k)
78				p.Succs[pk.i] = Edge{child, len(child.Preds)}
79				// Fix up Phi value in b to have one less argument.
80				for _, v := range b.Values {
81					if v.Op != OpPhi {
82						continue
83					}
84					b.removePhiArg(v, k)
85				}
86				// Fix up child to have one more predecessor.
87				child.Preds = append(child.Preds, Edge{p, pk.i})
88				ai := b.Succs[out].i
89				for _, v := range child.Values {
90					if v.Op != OpPhi {
91						continue
92					}
93					v.AddArg(v.Args[ai])
94				}
95				if b.Func.pass.debug > 0 {
96					b.Func.Warnl(b.Controls[0].Pos, "Redirect %s based on %s", b.Controls[0].Op, p.Controls[0].Op)
97				}
98				changed = true
99				k--
100				break
101			}
102			ft.restore()
103		}
104		if len(b.Preds) == 0 && b != f.Entry {
105			// Block is now dead.
106			b.Kind = BlockInvalid
107		}
108	}
109	ft.restore()
110	ft.cleanup(f)
111	return changed
112}
113