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