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// layout orders basic blocks in f with the goal of minimizing control flow instructions.
8// After this phase returns, the order of f.Blocks matters and is the order
9// in which those blocks will appear in the assembly output.
10func layout(f *Func) {
11	f.Blocks = layoutOrder(f)
12}
13
14// Register allocation may use a different order which has constraints
15// imposed by the linear-scan algorithm. Note that f.pass here is
16// regalloc, so the switch is conditional on -d=ssa/regalloc/test=N
17func layoutRegallocOrder(f *Func) []*Block {
18
19	switch f.pass.test {
20	case 0: // layout order
21		return layoutOrder(f)
22	case 1: // existing block order
23		return f.Blocks
24	case 2: // reverse of postorder; legal, but usually not good.
25		po := f.postorder()
26		visitOrder := make([]*Block, len(po))
27		for i, b := range po {
28			j := len(po) - i - 1
29			visitOrder[j] = b
30		}
31		return visitOrder
32	}
33
34	return nil
35}
36
37func layoutOrder(f *Func) []*Block {
38	order := make([]*Block, 0, f.NumBlocks())
39	scheduled := make([]bool, f.NumBlocks())
40	idToBlock := make([]*Block, f.NumBlocks())
41	indegree := make([]int, f.NumBlocks())
42	posdegree := f.newSparseSet(f.NumBlocks()) // blocks with positive remaining degree
43	defer f.retSparseSet(posdegree)
44	zerodegree := f.newSparseSet(f.NumBlocks()) // blocks with zero remaining degree
45	defer f.retSparseSet(zerodegree)
46	exit := f.newSparseSet(f.NumBlocks()) // exit blocks
47	defer f.retSparseSet(exit)
48
49	// Initialize indegree of each block
50	for _, b := range f.Blocks {
51		idToBlock[b.ID] = b
52		if b.Kind == BlockExit {
53			// exit blocks are always scheduled last
54			// TODO: also add blocks post-dominated by exit blocks
55			exit.add(b.ID)
56			continue
57		}
58		indegree[b.ID] = len(b.Preds)
59		if len(b.Preds) == 0 {
60			zerodegree.add(b.ID)
61		} else {
62			posdegree.add(b.ID)
63		}
64	}
65
66	bid := f.Entry.ID
67blockloop:
68	for {
69		// add block to schedule
70		b := idToBlock[bid]
71		order = append(order, b)
72		scheduled[bid] = true
73		if len(order) == len(f.Blocks) {
74			break
75		}
76
77		for _, e := range b.Succs {
78			c := e.b
79			indegree[c.ID]--
80			if indegree[c.ID] == 0 {
81				posdegree.remove(c.ID)
82				zerodegree.add(c.ID)
83			}
84		}
85
86		// Pick the next block to schedule
87		// Pick among the successor blocks that have not been scheduled yet.
88
89		// Use likely direction if we have it.
90		var likely *Block
91		switch b.Likely {
92		case BranchLikely:
93			likely = b.Succs[0].b
94		case BranchUnlikely:
95			likely = b.Succs[1].b
96		}
97		if likely != nil && !scheduled[likely.ID] {
98			bid = likely.ID
99			continue
100		}
101
102		// Use degree for now.
103		bid = 0
104		mindegree := f.NumBlocks()
105		for _, e := range order[len(order)-1].Succs {
106			c := e.b
107			if scheduled[c.ID] || c.Kind == BlockExit {
108				continue
109			}
110			if indegree[c.ID] < mindegree {
111				mindegree = indegree[c.ID]
112				bid = c.ID
113			}
114		}
115		if bid != 0 {
116			continue
117		}
118		// TODO: improve this part
119		// No successor of the previously scheduled block works.
120		// Pick a zero-degree block if we can.
121		for zerodegree.size() > 0 {
122			cid := zerodegree.pop()
123			if !scheduled[cid] {
124				bid = cid
125				continue blockloop
126			}
127		}
128		// Still nothing, pick any non-exit block.
129		for posdegree.size() > 0 {
130			cid := posdegree.pop()
131			if !scheduled[cid] {
132				bid = cid
133				continue blockloop
134			}
135		}
136		// Pick any exit block.
137		// TODO: Order these to minimize jump distances?
138		for {
139			cid := exit.pop()
140			if !scheduled[cid] {
141				bid = cid
142				continue blockloop
143			}
144		}
145	}
146	f.laidout = true
147	return order
148	//f.Blocks = order
149}
150