1// Copyright 2015 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// critical splits critical edges (those that go from a block with
8// more than one outedge to a block with more than one inedge).
9// Regalloc wants a critical-edge-free CFG so it can implement phi values.
10func critical(f *Func) {
11	// maps from phi arg ID to the new block created for that argument
12	blocks := make([]*Block, f.NumValues())
13	// need to iterate over f.Blocks without range, as we might
14	// need to split critical edges on newly constructed blocks
15	for j := 0; j < len(f.Blocks); j++ {
16		b := f.Blocks[j]
17		if len(b.Preds) <= 1 {
18			continue
19		}
20
21		var phi *Value
22		// determine if we've only got a single phi in this
23		// block, this is easier to handle than the general
24		// case of a block with multiple phi values.
25		for _, v := range b.Values {
26			if v.Op == OpPhi {
27				if phi != nil {
28					phi = nil
29					break
30				}
31				phi = v
32			}
33		}
34
35		// reset our block map
36		if phi != nil {
37			for _, v := range phi.Args {
38				blocks[v.ID] = nil
39			}
40		}
41
42		// split input edges coming from multi-output blocks.
43		for i := 0; i < len(b.Preds); {
44			e := b.Preds[i]
45			p := e.b
46			pi := e.i
47			if p.Kind == BlockPlain {
48				i++
49				continue // only single output block
50			}
51
52			var d *Block         // new block used to remove critical edge
53			reusedBlock := false // if true, then this is not the first use of this block
54			if phi != nil {
55				argID := phi.Args[i].ID
56				// find or record the block that we used to split
57				// critical edges for this argument
58				if d = blocks[argID]; d == nil {
59					// splitting doesn't necessarily remove the critical edge,
60					// since we're iterating over len(f.Blocks) above, this forces
61					// the new blocks to be re-examined.
62					d = f.NewBlock(BlockPlain)
63					d.Pos = p.Pos
64					blocks[argID] = d
65					if f.pass.debug > 0 {
66						f.Warnl(p.Pos, "split critical edge")
67					}
68				} else {
69					reusedBlock = true
70				}
71			} else {
72				// no existing block, so allocate a new block
73				// to place on the edge
74				d = f.NewBlock(BlockPlain)
75				d.Pos = p.Pos
76				if f.pass.debug > 0 {
77					f.Warnl(p.Pos, "split critical edge")
78				}
79			}
80
81			// if this not the first argument for the
82			// block, then we need to remove the
83			// corresponding elements from the block
84			// predecessors and phi args
85			if reusedBlock {
86				// Add p->d edge
87				p.Succs[pi] = Edge{d, len(d.Preds)}
88				d.Preds = append(d.Preds, Edge{p, pi})
89
90				// Remove p as a predecessor from b.
91				b.removePred(i)
92
93				// Update corresponding phi args
94				n := len(b.Preds)
95				phi.Args[i].Uses--
96				phi.Args[i] = phi.Args[n]
97				phi.Args[n] = nil
98				phi.Args = phi.Args[:n]
99				// splitting occasionally leads to a phi having
100				// a single argument (occurs with -N)
101				if n == 1 {
102					phi.Op = OpCopy
103				}
104				// Don't increment i in this case because we moved
105				// an unprocessed predecessor down into slot i.
106			} else {
107				// splice it in
108				p.Succs[pi] = Edge{d, 0}
109				b.Preds[i] = Edge{d, 0}
110				d.Preds = append(d.Preds, Edge{p, pi})
111				d.Succs = append(d.Succs, Edge{b, i})
112				i++
113			}
114		}
115	}
116}
117