1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
|
/* NSC -- new scala compiler
* Copyright 2005-2013 LAMP/EPFL
* @author Martin Odersky
*/
package scala
package tools.nsc
package backend
package icode
import scala.collection.{ mutable, immutable }
import mutable.ListBuffer
trait Linearizers {
self: ICodes =>
import global.debuglog
import opcodes._
abstract class Linearizer {
def linearize(c: IMethod): List[BasicBlock]
def linearizeAt(c: IMethod, start: BasicBlock): List[BasicBlock]
}
/**
* A simple linearizer which predicts all branches to
* take the 'success' branch and tries to schedule those
* blocks immediately after the test. This is in sync with
* how 'while' statements are translated (if the test is
* 'true', the loop continues).
*/
class NormalLinearizer extends Linearizer with WorklistAlgorithm {
type Elem = BasicBlock
val worklist: WList = new mutable.Stack()
var blocks: List[BasicBlock] = Nil
def linearize(m: IMethod): List[BasicBlock] = {
val b = m.startBlock
blocks = Nil
run {
worklist pushAll (m.exh map (_.startBlock))
worklist.push(b)
}
blocks.reverse
}
def linearizeAt(m: IMethod, start: BasicBlock): List[BasicBlock] = {
blocks = Nil
worklist.clear()
linearize(start)
}
/** Linearize another subtree and append it to the existing blocks. */
def linearize(startBlock: BasicBlock): List[BasicBlock] = {
//blocks = startBlock :: Nil;
run( { worklist.push(startBlock); } )
blocks.reverse
}
def processElement(b: BasicBlock) =
if (b.nonEmpty) {
add(b)
b.lastInstruction match {
case JUMP(whereto) =>
add(whereto)
case CJUMP(success, failure, _, _) =>
add(success)
add(failure)
case CZJUMP(success, failure, _, _) =>
add(success)
add(failure)
case SWITCH(_, labels) =>
add(labels)
case RETURN(_) => ()
case THROW(clasz) => ()
}
}
def dequeue: Elem = worklist.pop()
/**
* Prepend b to the list, if not already scheduled.
* TODO: use better test than linear search
*/
def add(b: BasicBlock) {
if (blocks.contains(b))
()
else {
blocks = b :: blocks
worklist push b
}
}
def add(bs: List[BasicBlock]): Unit = bs foreach add
}
/**
* Linearize code using a depth first traversal.
*/
class DepthFirstLinerizer extends Linearizer {
var blocks: List[BasicBlock] = Nil
def linearize(m: IMethod): List[BasicBlock] = {
blocks = Nil
dfs(m.startBlock)
m.exh foreach (b => dfs(b.startBlock))
blocks.reverse
}
def linearizeAt(m: IMethod, start: BasicBlock): List[BasicBlock] = {
blocks = Nil
dfs(start)
blocks.reverse
}
def dfs(b: BasicBlock): Unit =
if (b.nonEmpty && add(b))
b.successors foreach dfs
/**
* Prepend b to the list, if not already scheduled.
* TODO: use better test than linear search
* @return Returns true if the block was added.
*/
def add(b: BasicBlock): Boolean =
!(blocks contains b) && {
blocks = b :: blocks
true
}
}
/**
* Linearize code in reverse post order. In fact, it does
* a post order traversal, prepending visited nodes to the list.
* This way, it is constructed already in reverse post order.
*/
class ReversePostOrderLinearizer extends Linearizer {
var blocks: List[BasicBlock] = Nil
val visited = new mutable.HashSet[BasicBlock]
val added = new mutable.BitSet
def linearize(m: IMethod): List[BasicBlock] = {
blocks = Nil
visited.clear()
added.clear()
m.exh foreach (b => rpo(b.startBlock))
rpo(m.startBlock)
// if the start block has predecessors, it won't be the first one
// in the linearization, so we need to enforce it here
if (m.startBlock.predecessors eq Nil)
blocks
else
m.startBlock :: (blocks.filterNot(_ == m.startBlock))
}
def linearizeAt(m: IMethod, start: BasicBlock): List[BasicBlock] = {
blocks = Nil
visited.clear()
added.clear()
rpo(start)
blocks
}
def rpo(b: BasicBlock): Unit =
if (b.nonEmpty && !visited(b)) {
visited += b
b.successors foreach rpo
add(b)
}
/**
* Prepend b to the list, if not already scheduled.
* @return Returns true if the block was added.
*/
def add(b: BasicBlock) = {
debuglog("Linearizer adding block " + b.label)
if (!added(b.label)) {
added += b.label
blocks = b :: blocks
}
}
}
/** A 'dump' of the blocks in this method, which does not
* require any well-formedness of the basic blocks (like
* the last instruction being a jump).
*/
class DumpLinearizer extends Linearizer {
def linearize(m: IMethod): List[BasicBlock] = m.blocks
def linearizeAt(m: IMethod, start: BasicBlock): List[BasicBlock] = sys.error("not implemented")
}
}
|
