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.
16func layoutRegallocOrder(f *Func) []*Block {
17	// remnant of an experiment; perhaps there will be another.
18	return layoutOrder(f)
19}
20
21func layoutOrder(f *Func) []*Block {
22	order := make([]*Block, 0, f.NumBlocks())
23	scheduled := f.Cache.allocBoolSlice(f.NumBlocks())
24	defer f.Cache.freeBoolSlice(scheduled)
25	idToBlock := f.Cache.allocBlockSlice(f.NumBlocks())
26	defer f.Cache.freeBlockSlice(idToBlock)
27	indegree := f.Cache.allocIntSlice(f.NumBlocks())
28	defer f.Cache.freeIntSlice(indegree)
29	posdegree := f.newSparseSet(f.NumBlocks()) // blocks with positive remaining degree
30	defer f.retSparseSet(posdegree)
31	// blocks with zero remaining degree. Use slice to simulate a LIFO queue to implement
32	// the depth-first topology sorting algorithm.
33	var zerodegree []ID
34	// LIFO queue. Track the successor blocks of the scheduled block so that when we
35	// encounter loops, we choose to schedule the successor block of the most recently
36	// scheduled block.
37	var succs []ID
38	exit := f.newSparseSet(f.NumBlocks()) // exit blocks
39	defer f.retSparseSet(exit)
40
41	// Populate idToBlock and find exit blocks.
42	for _, b := range f.Blocks {
43		idToBlock[b.ID] = b
44		if b.Kind == BlockExit {
45			exit.add(b.ID)
46		}
47	}
48
49	// Expand exit to include blocks post-dominated by exit blocks.
50	for {
51		changed := false
52		for _, id := range exit.contents() {
53			b := idToBlock[id]
54		NextPred:
55			for _, pe := range b.Preds {
56				p := pe.b
57				if exit.contains(p.ID) {
58					continue
59				}
60				for _, s := range p.Succs {
61					if !exit.contains(s.b.ID) {
62						continue NextPred
63					}
64				}
65				// All Succs are in exit; add p.
66				exit.add(p.ID)
67				changed = true
68			}
69		}
70		if !changed {
71			break
72		}
73	}
74
75	// Initialize indegree of each block
76	for _, b := range f.Blocks {
77		if exit.contains(b.ID) {
78			// exit blocks are always scheduled last
79			continue
80		}
81		indegree[b.ID] = len(b.Preds)
82		if len(b.Preds) == 0 {
83			// Push an element to the tail of the queue.
84			zerodegree = append(zerodegree, b.ID)
85		} else {
86			posdegree.add(b.ID)
87		}
88	}
89
90	bid := f.Entry.ID
91blockloop:
92	for {
93		// add block to schedule
94		b := idToBlock[bid]
95		order = append(order, b)
96		scheduled[bid] = true
97		if len(order) == len(f.Blocks) {
98			break
99		}
100
101		// Here, the order of traversing the b.Succs affects the direction in which the topological
102		// sort advances in depth. Take the following cfg as an example, regardless of other factors.
103		//           b1
104		//         0/ \1
105		//        b2   b3
106		// Traverse b.Succs in order, the right child node b3 will be scheduled immediately after
107		// b1, traverse b.Succs in reverse order, the left child node b2 will be scheduled
108		// immediately after b1. The test results show that reverse traversal performs a little
109		// better.
110		// Note: You need to consider both layout and register allocation when testing performance.
111		for i := len(b.Succs) - 1; i >= 0; i-- {
112			c := b.Succs[i].b
113			indegree[c.ID]--
114			if indegree[c.ID] == 0 {
115				posdegree.remove(c.ID)
116				zerodegree = append(zerodegree, c.ID)
117			} else {
118				succs = append(succs, c.ID)
119			}
120		}
121
122		// Pick the next block to schedule
123		// Pick among the successor blocks that have not been scheduled yet.
124
125		// Use likely direction if we have it.
126		var likely *Block
127		switch b.Likely {
128		case BranchLikely:
129			likely = b.Succs[0].b
130		case BranchUnlikely:
131			likely = b.Succs[1].b
132		}
133		if likely != nil && !scheduled[likely.ID] {
134			bid = likely.ID
135			continue
136		}
137
138		// Use degree for now.
139		bid = 0
140		// TODO: improve this part
141		// No successor of the previously scheduled block works.
142		// Pick a zero-degree block if we can.
143		for len(zerodegree) > 0 {
144			// Pop an element from the tail of the queue.
145			cid := zerodegree[len(zerodegree)-1]
146			zerodegree = zerodegree[:len(zerodegree)-1]
147			if !scheduled[cid] {
148				bid = cid
149				continue blockloop
150			}
151		}
152
153		// Still nothing, pick the unscheduled successor block encountered most recently.
154		for len(succs) > 0 {
155			// Pop an element from the tail of the queue.
156			cid := succs[len(succs)-1]
157			succs = succs[:len(succs)-1]
158			if !scheduled[cid] {
159				bid = cid
160				continue blockloop
161			}
162		}
163
164		// Still nothing, pick any non-exit block.
165		for posdegree.size() > 0 {
166			cid := posdegree.pop()
167			if !scheduled[cid] {
168				bid = cid
169				continue blockloop
170			}
171		}
172		// Pick any exit block.
173		// TODO: Order these to minimize jump distances?
174		for {
175			cid := exit.pop()
176			if !scheduled[cid] {
177				bid = cid
178				continue blockloop
179			}
180		}
181	}
182	f.laidout = true
183	return order
184	//f.Blocks = order
185}
186