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
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
|
/* NSC -- new Scala compiler
* Copyright 2007-2010 LAMP/EPFL
* @author Anders Bach Nielsen
* @version 1.0
*/
package scala.tools.nsc
import java.io.{ BufferedWriter, FileWriter }
import scala.collection.mutable
/**
* PhaseAssembly
* Trait made to separate the constraint solving of the phase order from
* the rest of the compiler. See SIP 00002
*
*/
trait PhaseAssembly {
self: Global =>
/**
* Aux datastructure for solving the constraint system
* The depency graph container with helper methods for node and edge creation
*/
class DependencyGraph {
/**
* Simple edge with to and from refs
*/
class Edge(var frm: Node, var to: Node, var hard: Boolean)
/**
* Simple node with name and object ref for the phase object,
* also sets of in and out going dependencies
*/
class Node(name: String) {
val phasename = name
var phaseobj: Option[List[SubComponent]] = None
val after = new mutable.HashSet[Edge]()
var before = new mutable.HashSet[Edge]()
var visited = false
var level = 0
def allPhaseNames(): String = phaseobj match {
case None => phasename
case Some(lst) => lst.map(_.phaseName).reduceLeft(_+","+_)
}
}
val nodes = new mutable.HashMap[String,Node]()
val edges = new mutable.HashSet[Edge]()
/* Given a phase object, get the node for this phase object. If the
* node object does not exist, then create it.
*/
def getNodeByPhase(phs: SubComponent): Node = {
var node: Node = getNodeByPhase(phs.phaseName)
node.phaseobj match {
case None =>
node.phaseobj = Some(List[SubComponent](phs))
case _ =>
}
node
}
/* Given the name of a phase object, get the node for that name. If the
* node object does not exits, then create it.
*/
def getNodeByPhase(name: String): Node =
nodes.getOrElseUpdate(name, new Node(name))
/* Connect the frm and to nodes with an edge and make it soft.
* Also add the edge object to the set of edges, and to the dependency
* list of the nodes
*/
def softConnectNodes(frm: Node, to: Node) {
var e = new Edge(frm, to, false)
this.edges += e
frm.after += e
to.before += e
}
/* Connect the frm and to nodes with an edge and make it hard.
* Also add the edge object to the set of edges, and to the dependency
* list of the nodes
*/
def hardConnectNodes(frm: Node, to: Node) {
var e = new Edge(frm, to, true)
this.edges += e
frm.after += e
to.before += e
}
/* Given the entire graph, collect the phase objects at each level, where the phase
* names are sorted alphabetical at each level, into the compiler phase list
*/
def compilerPhaseList(): List[SubComponent] =
nodes.values.toList filter (_.level > 0) sortBy (x => (x.level, x.phasename)) flatMap (_.phaseobj) flatten
/* Test if there are cycles in the graph, assign levels to the nodes
* and collapse hard links into nodes
*/
def collapseHardLinksAndLevels(node: Node, lvl: Int) {
if (node.visited) {
throw new FatalError(
"Cycle in compiler phase dependencies detected, phase " +
node.phasename + " reacted twice!")
}
if (node.level < lvl) node.level = lvl
var hls = Nil ++ node.before.filter(_.hard)
while (hls.size > 0) {
for (hl <- hls) {
node.phaseobj = Some(node.phaseobj.get ++ hl.frm.phaseobj.get)
node.before = hl.frm.before
nodes -= hl.frm.phasename
edges -= hl
for (edge <- node.before) edge.to = node
}
hls = Nil ++ node.before.filter(_.hard)
}
node.visited = true
for (edge <- node.before) {
collapseHardLinksAndLevels( edge.frm, lvl + 1)
}
node.visited = false
}
/* Find all edges in the given graph that are hard links. For each hard link we
* need to check that its the only dependency. If not, then we will promote the
* other dependencies down
*/
def validateAndEnforceHardlinks() {
var hardlinks = edges.filter(_.hard)
for (hl <- hardlinks) {
if (hl.frm.after.size > 1) {
throw new FatalError("phase " + hl.frm.phasename + " want to run right after " + hl.to.phasename + ", but some phase has declared to run before " + hl.frm.phasename + ". Re-run with -Xgenerate-phase-graph <filename> to better see the problem.")
}
}
var rerun = true
while (rerun) {
rerun = false
hardlinks = edges.filter(_.hard)
for (hl <- hardlinks) {
var sanity = Nil ++ hl.to.before.filter(_.hard)
if (sanity.length == 0) {
throw new FatalError("There is no runs right after dependency, where there should be one! This is not supposed to happen!")
} else if (sanity.length > 1) {
var msg = "Multiple phases want to run right after the phase " + sanity.head.to.phasename + "\n"
msg += "Phases: "
sanity = sanity sortBy (_.frm.phasename)
for (edge <- sanity) {
msg += edge.frm.phasename + ", "
}
msg += "\nRe-run with -Xgenerate-phase-graph <filename> to better see the problem."
throw new FatalError(msg)
} else {
var promote = hl.to.before.filter(e => (!e.hard))
hl.to.before.clear
sanity foreach (edge => hl.to.before += edge)
for (edge <- promote) {
rerun = true
informProgress(
"promote the dependency of " + edge.frm.phasename +
": " + edge.to.phasename + " => " + hl.frm.phasename)
edge.to = hl.frm
hl.frm.before += edge
}
}
}
}
}
/** Remove all nodes in the given graph, that have no phase object
* Make sure to clean up all edges when removing the node object
* <code>Inform</code> with warnings, if an external phase has a
* dependency on something that is dropped.
*/
def removeDanglingNodes() {
for (node <- nodes.valuesIterator filter (_.phaseobj.isEmpty)) {
val msg = "dropping dependency on node with no phase object: "+node.phasename
informProgress(msg)
nodes -= node.phasename
for (edge <- node.before) {
edges -= edge
edge.frm.after -= edge
if (edge.frm.phaseobj exists (lsc => !lsc.head.internal))
warning(msg)
}
}
}
}
/* Method called from computePhaseDescriptors in class Global
*/
def buildCompilerFromPhasesSet(): List[SubComponent] = {
// Add all phases in the set to the graph
val graph = phasesSetToDepGraph(phasesSet)
// Output the phase dependency graph at this stage
if (settings.genPhaseGraph.value != "")
graphToDotFile(graph, settings.genPhaseGraph.value + "1.dot")
// Remove nodes without phaseobj
graph.removeDanglingNodes()
// Output the phase dependency graph at this stage
if (settings.genPhaseGraph.value != "")
graphToDotFile(graph, settings.genPhaseGraph.value + "2.dot")
// Validate and Enforce hardlinks / runsRightAfter and promote nodes down the tree
graph.validateAndEnforceHardlinks()
// Output the phase dependency graph at this stage
if (settings.genPhaseGraph.value != "")
graphToDotFile(graph, settings.genPhaseGraph.value + "3.dot")
// test for cycles, assign levels and collapse hard links into nodes
graph.collapseHardLinksAndLevels(graph.getNodeByPhase("parser"), 1)
// Output the phase dependency graph at this stage
if (settings.genPhaseGraph.value != "")
graphToDotFile(graph, settings.genPhaseGraph.value + "4.dot")
// assemble the compiler
graph.compilerPhaseList()
}
/** Given the phases set, will build a dependency graph from the phases set
* Using the aux. method of the DependencyGraph to create nodes and egdes.
*/
private def phasesSetToDepGraph(phsSet: mutable.HashSet[SubComponent]): DependencyGraph = {
val graph = new DependencyGraph()
for (phs <- phsSet) {
var fromnode = graph.getNodeByPhase(phs)
phs.runsRightAfter match {
case None =>
for (phsname <- phs.runsAfter) {
if (phsname != "terminal") {
val tonode = graph.getNodeByPhase(phsname)
graph.softConnectNodes(fromnode, tonode)
} else {
globalError("[phase assembly, after dependency on terminal phase not allowed: " + fromnode.phasename + " => "+ phsname + "]")
}
}
for (phsname <- phs.runsBefore) {
if (phsname != "parser") {
val tonode = graph.getNodeByPhase(phsname)
graph.softConnectNodes(tonode, fromnode)
} else {
globalError("[phase assembly, before dependency on parser phase not allowed: " + phsname + " => "+ fromnode.phasename + "]")
}
}
case Some(phsname) =>
if (phsname != "terminal") {
val tonode = graph.getNodeByPhase(phsname)
graph.hardConnectNodes(fromnode, tonode)
} else {
globalError("[phase assembly, right after dependency on terminal phase not allowed: " + fromnode.phasename + " => "+ phsname + "]")
}
}
}
graph
}
/* This is a helper method, that given a dependency graph will generate a graphviz dot
* file showing its structure.
* Plug-in supplied phases are marked as green nodes and hard links are marked as blue edges.
*/
private def graphToDotFile(graph: DependencyGraph, filename: String) {
val sbuf = new StringBuilder
val extnodes = new mutable.HashSet[graph.Node]()
val fatnodes = new mutable.HashSet[graph.Node]()
sbuf.append("digraph G {\n")
for (edge <- graph.edges) {
sbuf.append("\"" + edge.frm.allPhaseNames + "(" + edge.frm.level + ")" + "\"->\"" + edge.to.allPhaseNames + "(" + edge.to.level + ")" + "\"")
if (! edge.frm.phaseobj.get.head.internal) {
extnodes += edge.frm
}
edge.frm.phaseobj match { case None => null case Some(ln) => if(ln.size > 1) fatnodes += edge.frm }
edge.to.phaseobj match { case None => null case Some(ln) => if(ln.size > 1) fatnodes += edge.to }
if (edge.hard) {
sbuf.append(" [color=\"#0000ff\"]\n")
} else {
sbuf.append(" [color=\"#000000\"]\n")
}
}
for (node <- extnodes) {
sbuf.append("\"" + node.allPhaseNames + "(" + node.level + ")" + "\" [color=\"#00ff00\"]\n")
}
for (node <- fatnodes) {
sbuf.append("\"" + node.allPhaseNames + "(" + node.level + ")" + "\" [color=\"#0000ff\"]\n")
}
sbuf.append("}\n")
var out = new BufferedWriter(new FileWriter(filename))
out.write(sbuf.toString)
out.flush()
out.close()
}
}
|