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
|
/* NSC -- new scala compiler
* Copyright 2005 LAMP/EPFL
* @author Martin Odersky
*/
// $Id$
package scala.tools.nsc.backend.icode;
import scala.tools.nsc.ast._;
import scala.collection.mutable.{Stack, HashSet};
trait Linearizers requires ICodes {
import opcodes._;
abstract class Linearizer {
def linearize(c: IMethod): 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;
type WList = Stack[Elem];
val worklist: WList = new Stack();
var blocks: List[BasicBlock] = Nil;
def linearize(m: IMethod): List[BasicBlock] = {
val b = m.code.startBlock;
blocks = Nil;
run {
worklist ++= (m.exh map (.startBlock));
worklist.push(b);
}
blocks.reverse;
}
/** 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.size > 0) {
add(b);
b.lastInstruction match {
case JUMP(where) =>
add(where);
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() => ();
}
}
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.code.startBlock);
m.exh foreach (b => dfs(b.startBlock));
blocks.reverse
}
def dfs(b: BasicBlock): Unit =
if (b.size > 0 && 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 =
if (blocks.contains(b))
false
else {
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;
var visited: HashSet[BasicBlock] = new HashSet;
def linearize(m: IMethod): List[BasicBlock] = {
blocks = Nil;
visited.clear;
m.exh foreach (b => rpo(b.startBlock));
rpo(m.code.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.code.startBlock.predecessors eq Nil)
blocks
else
m.code.startBlock :: (blocks.remove(.==(m.code.startBlock)))
}
def rpo(b: BasicBlock): Unit =
if (b.size > 0 && !(visited contains b)) {
visited += b;
b.successors foreach rpo;
add(b);
}
/**
* 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) =
if (!blocks.contains(b))
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.code.blocks.toList;
}
}
|
